Skip to yearly menu bar Skip to main content


Supervised learning through the lens of compression

Ofir David · Shay Moran · Amir Yehudayoff

Area 5+6+7+8 #184

Keywords: [ (Other) Machine Learning Topics ] [ (Other) Regression ] [ (Other) Classification ] [ Learning Theory ]


This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. We first extend the investigation to multiclass categorization: we prove that in this case learnability is equivalent to compression of logarithmic sample size and that the uniform convergence property implies compression of constant size. We use the compressibility-learnability equivalence to show that (i) for multiclass categorization, PAC and agnostic PAC learnability are equivalent, and (ii) to derive a compactness theorem for learnability. We then consider supervised learning under general loss functions: we show that in this case, in order to maintain the compressibility-learnability equivalence, it is necessary to consider an approximate variant of compression. We use it to show that PAC and agnostic PAC are not equivalent, even when the loss function has only three values.

Live content is unavailable. Log in and register to view live content