# Agnostic Sample Compression Schemes for Regression

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2018.

## Built on by (most cited first, 7 of 7)

- [Information Complexity of Stochastic Convex Optimization: Applications to Generalization and Memorization](https://mlsanity.com/paper/2402.09327/) (2024)
- [Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses](https://mlsanity.com/paper/2409.17932/) (2024)
- [Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks](https://mlsanity.com/paper/2410.13577/) (2024)
- [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)
- [The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity](https://mlsanity.com/paper/2605.29819/) (2026)
- [An Agnostic Sample Compression Scheme for Squared Loss of Near-Linear Size in the Fat-Shattering Dimension](https://mlsanity.com/paper/2609.29696/) (2026)

## Abstract (arXiv)

We obtain the first positive results for bounded sample compression in the agnostic regression setting with the ℓp loss, where p∈ [1,∞]. We construct a generic approximate sample compression scheme for real-valued function classes exhibiting exponential size in the fat-shattering dimension but independent of the sample size. Notably, for linear regression, an approximate compression of size linear in the dimension is constructed. Moreover, for ℓ1 and ℓ_∞ losses, we can even exhibit an efficient exact sample compression scheme of size linear in the dimension. We further show that for every other ℓp loss, p∈ (1,∞), there does not exist an exact agnostic compression scheme of bounded size. This refines and generalizes a negative result of David, Moran, and Yehudayoff for the ℓ2 loss. We close by posing general open questions: for agnostic regression with ℓ1 loss, does every function class admits an exact compression scheme of size equal to its pseudo-dimension? For the ℓ2 loss, does every function class admit an approximate compression scheme of polynomial size in the fat-shattering dimension? These questions generalize Warmuth's classic sample compression conjecture for realizable-case classification.