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

arXiv:2609.27860v1 Announce Type: new Abstract: 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)=int_{mathbb R}sqrt{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 m^2+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(mu,sigma^2) with |mu|le csigma, the equal prior on the endpoint means is least favorable and the minimax value is sigma^2Lambda_c^2. Exact Gaussian minimax optimality forces a critical heavy tail: at the endpoint means, absolute moments are finite exactly for pt)=Theta(t^{-3}/sqrt{log t}). A Cauchy-mixture robustification inflates the second moment by at most 1/(1-eta) 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 (sigma,d,B,arepsilon), and a finite-variance high-probability bound incurs only a logarithmic confidence factor.

Source: arXiv cs.LG | 2026-09-24