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

arXiv:2609.29696v1 Announce Type: new Abstract: We construct, for every function class Fsubseteq[0,1]^{X} and every accuracy 0<alphale 1, an agnostic sample compression scheme for the empirical squared loss: for every finite sample Sin(Ximes[0,1])^m with arbitrary (noisy) labels, the scheme stores at most O(fat(F,c'alpha)dotlog^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)leinf_{finF}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 agnostic ell_2 compression scheme of size fat(F,calpha)dotpolylog(c/alpha). 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-epsilon)-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/epsilon)) rounds independent of m, and sparsification is never needed. The booster's synthetic target labels (values of a near-optimal f^*inF) 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(alpha), matching the same-scale form of the open problem.

Source: arXiv cs.LG | 2026-09-25