# Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 14 references that are in the map.
- First posted on arXiv 20 Aug 2026.

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

- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms](https://mlsanity.com/paper/2001.08877/) (2020)
- [How to send a real number using a single bit (and some shared randomness)](https://mlsanity.com/paper/2010.02331/) (2020)
- [Mean Estimation from One-Bit Measurements](https://mlsanity.com/paper/1901.03403/) (2019)
- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation](https://mlsanity.com/paper/2608.02538/) (2026)
- [Information-Theoretic Lower Bounds for Bit-Constrained Stochastic Optimization via a Reduction to Compressed Gaussian Mean Estimation](https://mlsanity.com/paper/2606.00703/) (2026)

## Abstract (arXiv)

A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit. For a scalar source P with CDF F, mean m, and mathcal J(P)=intmathbb R√F(r)(1-F(r)),dr, we prove that the infimum of the source-averaged reconstruction second moment over all public-coin one-bit codes unbiased on mathbb R is m2+mathcal J(P)2. For regular full-support sources, a distribution-centered random-threshold code attains this value; a converse over arbitrary randomized binary encoders and an equality analysis characterize every attaining code up to null sets, bit relabeling, and public-seed refinement. For the Gaussian location family mathcal N(μ,σ2) with |μ|≤ cσ, the equal prior on the endpoint means is least favorable and the minimax value is σ2Lambdac2. Exact Gaussian minimax optimality forces a critical heavy tail: at the endpoint means, absolute moments are finite exactly for p<3, and Pr(W>t)=Theta(t-3/√log t). A Cauchy-mixture robustification inflates the second moment by at most 1/(1-η) while making every positive-order absolute moment finite. Finite-support public randomness with finite decoder means cannot achieve exact unbiasedness on mathbb R, but a bounded-output approximation using exactly R shared random bits has explicit bias and second-moment bounds converging to the minimax constant. Finally, coordinate allocation communicates exactly B bits per Gaussian-gradient query. On Kim's continuous quadratic hard family, the expected optimization guarantee matches the lower bound in its dependence on (σ,d,B,varepsilon), and a finite-variance high-probability bound incurs only a logarithmic confidence factor.