Agnostic Sample Compression Schemes for Regression

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 realvalued 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 [16] 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 [51] . * Some of the results on linear regression presented in this paper (Sections 4.2 and 4.3) previously appeared in the unpublished manuscript titled "Agnostic sample compression for linear regression" [25] .