Abstract:
We obtain the first positive results for bounded sample compression in the agnostic regression setting with the loss, where . 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 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 loss, , there does not exist an exact agnostic compression scheme of bounded size. This refines and generalizes a negative result of David, Moran, and Yehudayoff (2016) for the loss. We close by posing general open questions: for agnostic regression with loss, does every function class admit an exact compression scheme of polynomial size in the pseudo-dimension? For the 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 (Warmuth, 2003).
Chat is not available.