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

We construct, for every function class Fsubseteq[0,1]X and every accuracy 0<α≤ 1, an agnostic sample compression scheme for the empirical squared loss: for every finite sample S∈(X×[0,1])m with arbitrary (noisy) labels, the scheme stores at most O(fat(F,c'α)·log3(2/α)) original labeled examples and auxiliary bits, independent of the sample size m, and reconstructs a function hat f with L2(hat f,S)≤inff∈FL2(f,S)+α. This resolves, in the positive, the open problem of Attias, Hanneke, Kontorovich, and Sadigurschi (ICML 2024, Section 5), which asks for an agnostic ℓ2 compression scheme of size fat(F,cα)·polylog(c/α). All previously known bounded-size constructions, agnostic and even realizable, 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 that forces uniform approximation on the sample. By targeting only a (1-ε)-fraction of sample points, which suffices for an average-loss guarantee over a bounded range, K'egl's boosting margin bound yields O(log(1/ε)) rounds independent of m, and sparsification is never needed. The booster's synthetic target labels (values of a near-optimal f^*∈F) are transmitted through quantized side-information bits attached to stored original examples, and the cross term of the squared loss forces the weak-learning scale Theta(α), matching the same-scale form of the open problem.