# Information-constrained optimization: can adaptive processing of gradients help?

arXiv: https://arxiv.org/abs/2104.00979 · HTML: https://mlsanity.com/paper/2104.00979/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2021.

## Built on by (most cited first, 8 of 8)

- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [On the Statistical Complexity of Estimation and Testing under Privacy Constraints](https://mlsanity.com/paper/2210.02215/) (2022)
- [Communication-Constrained Bandits under Additive Gaussian Noise](https://mlsanity.com/paper/2304.12680/) (2023)
- [Fundamental limits of over-the-air optimization: Are analog schemes optimal?](https://mlsanity.com/paper/2109.05222/) (2021)
- [Private Statistical Estimation of Many Quantiles](https://mlsanity.com/paper/2302.06943/) (2023)
- [About the Cost of Central Privacy in Density Estimation](https://mlsanity.com/paper/2306.14535/) (2023)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)
- [Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory](https://mlsanity.com/paper/2607.24827/) (2026)

## Abstract (arXiv)

We revisit first-order optimization under local information constraints such as local privacy, gradient quantization, and computational constraints limiting access to a few coordinates of the gradient. In this setting, the optimization algorithm is not allowed to directly access the complete output of the gradient oracle, but only gets limited information about it subject to the local information constraints. We study the role of adaptivity in processing the gradient output to obtain this limited information from it.We consider optimization for both convex and strongly convex functions and obtain tight or nearly tight lower bounds for the convergence rate, when adaptive gradient processing is allowed. Prior work was restricted to convex functions and allowed only nonadaptive processing of gradients. For both of these function classes and for the three information constraints mentioned above, our lower bound implies that adaptive processing of gradients cannot outperform nonadaptive processing in most regimes of interest. We complement these results by exhibiting a natural optimization problem under information constraints for which adaptive processing of gradient strictly outperforms nonadaptive processing.