# Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 21 of 21)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Pretraining Large Language Models with NVFP4](https://mlsanity.com/paper/2509.25149/) (2025)
- [Communication Complexity of Distributed Convex Learning and Optimization](https://mlsanity.com/paper/1506.01900/) (2015)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Quartet: Native FP4 Training Can Be Optimal for Large Language Models](https://mlsanity.com/paper/2505.14669/) (2025)
- [Training LLMs with MXFP4](https://mlsanity.com/paper/2502.20586/) (2025)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory](https://mlsanity.com/paper/1407.5144/) (2014)
- [Rate-cost tradeoffs in control](https://mlsanity.com/paper/1612.02126/) (2016)
- [A Convergence Analysis of Adaptive Optimizers under Floating-point Quantization](https://mlsanity.com/paper/2510.21314/) (2025)
- [Semidefinite Programming Approach to Gaussian Sequential Rate-Distortion Trade-offs](https://mlsanity.com/paper/1411.7632/) (2014)
- [The Time-Invariant Multidimensional Gaussian Sequential Rate-Distortion Problem Revisited](https://mlsanity.com/paper/1711.09853/) (2017)
- [On the Gradient Complexity of Private Optimization with Private Oracles](https://mlsanity.com/paper/2511.13999/) (2025)

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

- [Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation](https://mlsanity.com/paper/2609.27860/) (2026)

## Abstract (arXiv)

Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible. We study a B-bit quantized stochastic first-order oracle: an optimizer interacts for T rounds and receives, each round, a B-bit adaptive public-coin description of its stochastic gradient. Our main contribution is an exact reduction from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation -- under the B-bit oracle the query carries no information, so optimization collapses exactly onto a sequential distributed-estimation problem. This yields two unconditional lower bounds, a communication bound TB = Omega(d) and a statistical bound T = Omega(sigma^2 d / eps^2), and the sharp product-form bound T = Omega((sigma^2 d / eps^2) max{1, d/B}). The product form is also unconditional: a B-bit transcript carries at most O(TB / sigma^2) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information, and combined with the multivariate van Trees inequality this gives the bound directly, without bounded-likelihood-ratio truncation. We give a near-matching achievability result with exact per-round bit accounting under a bounded-dynamic-range oracle, tight up to a logarithmic factor; the lower bound is for truly Gaussian (unbounded) gradients, and closing this oracle gap is left open. A sequential rate-distortion perspective extends the reduction to correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by (1+rho)/(1-rho) rather than relaxing it. The bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems.