# Technical Program

## Paper Detail

 Paper ID L.7.4 Paper Title Limits on Gradient Compression for Stochastic Optimization Authors Prathamesh Mayekar, Himanshu Tyagi, Indian Institute of Science, India Session L.7: High-dimensional Statistics Presentation Lecture Track Statistics and Learning Theory Manuscript Click here to download the manuscript Virtual Presentation Click here to watch in the Virtual Symposium Abstract We consider stochastic optimization over $\ell_p$ spaces using access to a first-order oracle. We ask: What is the minimum precision required for oracle outputs to retain the unrestricted convergence rates? We characterize this precision for every $p\geq 1$ by deriving information theoretic lower bounds and by providing quantizers that (almost) achieve these lower bounds. Our quantizers are new and easy to implement. In particular, our results are exact for $p=2$ and $p=\infty$, showing the minimum precision needed in these settings are $\Theta(d)$ and $\Theta(\log d)$, respectively. The latter result is surprising since recovering the gradient vector will require $\Omega(d)$ bits.