Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation
Munsik Kim · 2026
Read Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation by Munsik Kim (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00703.txt.
Introduction
Kim sets hard limits on low-precision training in this 2026 paper. Modern AI models often train with few-bit numbers, yet past work mostly shows what can be done, not what is barred. Kim studies an oracle that hands an optimizer a B-bit sketch of each gradient, round by round.
His main move is an exact reduction: the task becomes a known hard task, estimating a Gaussian mean from squeezed messages. From it he gets two firm lower bounds, one on total bits and one on rounds. A sharp product-form bound joins them. Bits, not width, cap what can be learned, he shows. He also gives a method that nearly meets the bound. One gap stays open, for truly unbounded Gaussian noise. The bounds give a floor for any low-bit training path.
Catalog record
| CREATOR | Munsik Kim |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00703
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation Munsik Kim Abstract 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 B -bit quantized stochastic first-order oracle in which an optimizer interacts for T T rounds and receives, each round, a B B -bit adaptive, public-coin description of its stochastic gradient. Our main contribution is an exact reduction (Lemma 1 ) from optimizing a strongly convex quadratic family to interactively compressed Gaussian mean estimation: under the B 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 T B = Ω ( d ) TB=\Omega(d) (Theorem 1 ) and a statistical bound T = Ω ( σ 2 d / ε 2 ) T=\Omega(\sigma^{2}d/\varepsilon^{2}) (Theorem 2 )—and the sharp product-form bound T = Ω ( ( σ 2 d / ε 2 ) max { 1 , d / B } ) T=\Omega\!\big((\sigma^{2}d/\varepsilon^{2})\max\{1,d/B\}\big) (Theorem 3 ), also unconditional: in the Gaussian-location model the Fisher-information–mutual-information constraint of 8 —a B B -bit transcript carries at most O ( T B / σ 2 ) O(TB/\sigma^{2}) of Fisher trace about the mean, so bits rather than dimension limit the recoverable information—combined with the multivariate van Trees inequality ( 16 ) gives the bound directly, without the bounded-likelihood-ratio truncation of 11 . We give a near-matching achievability result with exact per-round bit accounting (Theorem 4 ) 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 (Appendix E ) extends the reduction to temporally correlated and drifting oracles and corrects an earlier conjecture: positive noise correlation raises the bound by 1 + ρ 1 − ρ \tfrac{1+\rho}{1-\rho} rather than relaxing it (Corollary 2 ). We are deliberately conservative about interpretation: the bounds give an information-theoretic baseline for any low-bit gradient path, not an optimality claim about deployed FP4 systems. 1 Introduction Lowering the numerical precision of gradients and weights is a leading way to reduce the cost of training large language models. Eight-bit floating point is routine, and over the past year four-bit formats have crossed from speculative to demonstrated: MXFP4 training with random Hadamard transforms and stochastic rounding reaches near-lossless quality ( 37 ) , the Quartet recipe closes the gap to FP8 with empirical scaling laws ( 13 ) , and NVFP4 has pretrained a 12B model over ten trillion tokens at FP8 parity ( 26 ) . These are all achievability statements: a particular algorithm attains a particular accuracy at a particular bit width. They do not answer the converse: given a budget of B bits per gradient, how many steps are unavoidably required to reach accuracy \varepsilon ? Recent convergence analyses under floating-point quantization ( 35 ) sharpen the upper-bound side but remain upper bounds. The two literatures that might supply a converse each stop short: classical oracle-complexity lower bounds ( 25 ; 1 ; 12 ; 5 ; 10 ) grant the algorithm real-valued gradients, while distributed estimation/optimization lower bounds ( 45 ; 11 ; 17 ; 6 ) are framed as many machines holding data rather than one optimizer receiving a low-precision description of its own gradient. This paper connects the two and is careful about where rigor stops. Contributions and their status. We state up front what is and is not ours. Our contribution is the bridge that lets the distributed-estimation literature speak about optimization, and the assembly of published Fisher-information tools into a sharp converse; the Fisher-trace and van Trees inequalities we invoke are external and cited as such. 1. Exact reduction / bridge (Lemma 1 ), the main conceptual contribution : under the B -bit oracle, optimizing f_{v}(x)=\tfrac{1}{2}\left\lVert x-\theta_{v}\right\rVert^{2} , \theta_{v}=\delta v , v\in\{\pm 1\}^{d} is equivalent to estimating v from T rounds of B -bit-compressed Gaussian observations; the query carries no information. This connects bit-constrained optimization to the distributed-estimation literature. 2. Communication bound (Theorem 1 ): TB=\Omega(d) , by chain rule and binary Fano. 3. Statistical bound (Theorem 2 ): T=\Omega(\sigma^{2}d/\varepsilon^{2}) , by Assouad with Pinsker. 4. Combined \max -form (Corollary 1 ), with the hard-instance scale made explicit. 5. Product-form bound (Theorem 3 ), unconditional : T=\Omega\!\big((\sigma^{2}d/\varepsilon^{2})\max\{1,d/B\}\big) . The reduction places us in the Gaussian-location model; the Fisher-information–mutual-information constraint of 8 bounds the transcript’s Fisher trace by O(TB/\sigma^{2}) , and the multivariate van Trees inequality ( 16 ) converts this to the minimax estimation bound, which the reduction turns into the optimization bound. The Fisher-trace and van Trees inequalities are not ours ( 8 ; 7 ; 16 ) ; the assembly and the reduction are. 6. Self-contained Fisher-trace proof and an alternative route (Appendix D ): we give a short proof of the Gaussian T=1 Fisher-trace bound via a Donsker–Varadhan centroid inequality, and record an alternative mutual-information/SDPI route (with the \chi^{2} /maximal-correlation contraction shown to be O(\mathrm{SNR}) ) together with why converting it to the needed KL contraction is harder than the Fisher route used in the main text. (centroid) / (MI route) 7. Achievability matching the lower bound up to logarithms (Theorem 4 ), under a bounded-dynamic-range oracle: public-coin rand- k sparsification + fixed-grid stochastic quantization (with an optional random rotation, used in practice but not needed for the bound), spending exactly B bits per round. We prove an unbiased B -bit compressor with second moment inflated by \omega_{B}=O(\max\{1,d\log d/B\}) (Lemma 3 ) and feed it to the strongly convex SGD rate of 9 , giving T=\widetilde{O}((\sigma^{2}d/\varepsilon^{2})\max\{1,d/B\}) . This matches Theorem 3 up to a \log d factor for a bounded-gradient oracle; the lower bound is for unbounded Gaussian gradients, so the match is up to this oracle gap, which we state rather than hide. 8. An extension and a correction (Corollary 2 , Appendix E , presented as a perspective). A dynamic counterpart of the reduction corrects an earlier conjecture: positive noise correlation raises the bound by \tfrac{1+\rho}{1-\rho} (the relaxing quantity is trajectory predictability, not noise correlation). The appendix also records a self-contained tracking lower bound and, in an expected-rate sense, an innovation-quantization achievability; the exact fixed-length gap (L3 ′ ) remains open. The sequential-RD machinery is imported; the reduction and the correction are ours. 9. Numerical sanity checks and practical reading (Section 8 , Appendix B ). Experiments in the model’s native setting confirm the product-form rate, show that the max-form scaling underestimates the cost, that several unbiased B -bit schemes all respect the lower bound, that bits (not dimension) cap the transcript Fisher trace, and that the reduction is exact; the practical reading is recorded conservatively. No claim is made about non-quadratic or transformer training. 2 Related Work Low-precision training (practice). 37 give a near-lossless MXFP4 recipe whose key device is a random Hadamard transform bounding stochastic-rounding variance; 13 present end-to-end FP4 with empirical scaling laws; the NVFP4 report ( 26 ) demonstrates trillion-token FP4 training