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

arXiv: https://arxiv.org/abs/2609.29696 · HTML: https://mlsanity.com/paper/2609.29696/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 14 references that are in the map.
- First posted on arXiv 31 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Sample Compression for Real-Valued Learners](https://mlsanity.com/paper/1805.08254/) (2018)
- [Adversarially Robust PAC Learnability of Real-Valued Functions](https://mlsanity.com/paper/2206.12977/) (2022)
- [Agnostic Sample Compression Schemes for Regression](https://mlsanity.com/paper/1810.01864/) (2018)
- [Sample Compression Scheme Reductions](https://mlsanity.com/paper/2410.13012/) (2024)
- [Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale](https://mlsanity.com/paper/2605.13684/) (2026)

## Abstract (arXiv)

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.