首页 > AI前沿 > Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation

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

arXiv机器学习 2026-08-20 15:29 5 阅读 查看原文

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$.

Regular full-support sources

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.

Gaussian location family

For the Gaussian location family $\mathcal N(μ,σ^2)$ with $|μ|\le cσ$, the equal prior on the endpoint means is least favorable and the minimax value is $σ^2Λ_c^2$.

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)=Θ(t^{-3}/\sqrt{\log t})$.

Cauchy-mixture robustification

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

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.

Coordinate allocation

Finally, coordinate allocation communicates exactly $B$ bits per Gaussian-gradient query.

Kim's continuous quadratic hard family

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.