SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Aug 31, 2026 · UTC

We construct, for every function class $\mathcal{F}\subseteq[0,1]^{\mathcal{X}}$ and every accuracy $0<α\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'α)\cdot\log^3(2/α))$ 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)+α$. This resolves, in the positive, the open problem of Attias, Hanneke, Kontorov

Read original source ↗ Open in workspace

recordType

paper

region

Global