An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension

Abstract

We study the squared-loss sample compression question posed by Attias, Hanneke, Kontorovich, and Sadigurschi in their ICML 2024 paper. For every nonempty class $\mathcal{F}\subseteq [0,1{]}^{\mathcal{X}}$ and accuracy $0<\alpha \le 1$ with $d=\mathrm{fat}(\mathcal{F},c^{\prime }\alpha )<\infty$, where $c^{\prime }>0$ is universal, we prove the existence of a deterministic agnostic scheme of total size $O(d{\log }^3(2/\alpha ))$. Its code contains original labeled observations and auxiliary bits, and its reconstruction has empirical loss at most $\alpha$ above the infimum over $\mathcal{F}$ on every finite sample. This establishes the polylogarithmic formulation in Section 5 of arXiv:1810.01864v2. The construction approximates a near-optimal internal target by a fixed-step boosting ensemble and takes its equal-weight median. Average loss permits an accuracy-dependent number of rounds, so the entire ensemble can be retained without dual-dimension sparsification. Quantized target constraints and round-membership bits determine the reconstructed function exactly. We also prove that, when retained observations must come from the sample, a fixed class of fat-shattering dimension one requires total size $\Omega (\log (1/\alpha ))$. With observations and auxiliary bits charged together, this rules out the proceedings version's log-free formulation under its original-example restriction. The framework extends to average power loss at scale $\alpha /p$.

arXiv comment43 pages