Metraipolis › archive › dc_6322df1ef4f8
Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation — arXiv:2609.27860
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.27860
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T10:57:23.223Z
- SHA-256 of the archived text
f0caf7b5ceb8b4b3c9e7942195fd555ab8a53bf96618df4aed23f306bfdd3718- Stable URL of this page
https://metraipolis.com/documento/dc_6322df1ef4f8
How to cite
Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation — arXiv:2609.27860 — arXiv (en), https://arxiv.org/abs/2609.27860 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6322df1ef4f8 (Metraipolis archive dc_6322df1ef4f8, sha256 f0caf7b5ceb8b4b3c9e7942195fd555ab8a53bf96618df4aed23f306bfdd3718)
BibTeX
@misc{dc6322df1ef4f8,
title = {Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation — arXiv:2609.27860},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.27860},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6322df1ef4f8; sha256 f0caf7b5ceb8b4b3c9e7942195fd555ab8a53bf96618df4aed23f306bfdd3718},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.27860. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 c\sigma$, the equal prior on the endpoint means is least favorable and the minimax value is $\sigma^2\Lambda_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)=\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,\varepsilon)$, and a finite-variance high-probability bound incurs only a logarithmic confidence factor.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-24 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.27860 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T10:06:16.751Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-24?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).