Limits on Gradient Compression for Stochastic Optimization
By Prathamesh Mayekar, Himanshu Tyagi. 2020
26 citations recorded by the source corpus.
We consider stochastic optimization overℓ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≥ 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 = ∞, showing the minimum precision needed in these settings are Θ(d) and Θ(log d), respectively. The latter result is surprising since recovering the gradient vector will require Ω(d) bits.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Vitaly Feldman
- Kunal Talwar
- Peter Kairouz
- Raef Bassily
- Mark Bun
- Thomas Steinke
- Cynthia Dwork
- Florian Tramèr
Citations in the corpus
- Lossless Compression of Efficient Private Local Randomizers (2021, background): “…the communication cost of mean estimation has been studied in many works with (Agarwal et al., 2018; Girgis et al., 2020; Chen et al., 2020; Gandikota et al., 2019) or without privacy (Alistarh et al., 2017; Faghri et al., 2020; Suresh et al., 2017; Gandikota et al., 2019; Mayekar & Tyagi, 2020).”