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

We construct, for every function class $\mathcal{F}\subseteq[0,1]^{\mathcal{X}}$ and every accuracy parameter $0<\alpha\le 1$, an agnostic sample compression scheme for the empirical squared loss: for every finite sample $S\in(\mathcal{X}\times[0,1])^m$ with arbitrary (noisy) labels, the scheme stores at most $O(\mathrm{fat}(\mathcal{F},c'\alpha)\cdot\log^3(2/\alpha))$ original labeled examples and auxiliary bits — independent of the sample size $m$ — and reconstructs a function $\hat f$ with $L_2(\hat f,S)\le\inf_{f\in\mathcal{F}}L_2(f,S)+\alpha$. This resolves, in the positive, the open problem of Attias, Hanneke, Kontorovich, and Sadigurschi (ICML 2024, Section 5), which asks for an $\alpha$-approximate agnostic $\ell_2$ compression scheme of size $\mathrm{fat}(\mathcal{F},c\alpha)\cdot\mathrm{polylog}(c/\alpha)$. All previously known bounded-size constructions — agnostic (Attias-Hanneke, ICML 2023; Attias et al., ICML 2024) and even realizable (Hanneke-Kontorovich-Sadigurschi, ALT 2019) — incur a multiplicative dual fat-shattering factor, which can be exponentially larger than the primal dimension. Our scheme removes the dual factor entirely, including in the realizable case. The dual factor in prior work enters solely through a sparsification step used to force uniform approximation on the sample; by targeting only a $(1-\epsilon)$-fraction of sample points — which suffices for an average-loss guarantee over a bounded range — Kégl's boosting margin bound yields a number of rounds $O(\log(1/\epsilon))$ independent of $m$, and sparsification is never needed. The booster's target labels are synthetic values of a near-optimal $f^*\in\mathcal{F}$, transmitted through quantized side-information bits attached to stored original examples, and the cross term of the squared loss forces the weak-learning scale $\eta=\Theta(\alpha)$ — exactly matching the same-scale form of the open problem.