# On statistical learning via the lens of compression

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2016.

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

- [Open-Endedness is Essential for Artificial Superhuman Intelligence](https://mlsanity.com/paper/2406.04268/) (2024)
- [A Characterization of List Learnability](https://mlsanity.com/paper/2211.04956/) (2022)
- [Multiclass Online Learning and Uniform Convergence](https://mlsanity.com/paper/2303.17716/) (2023)
- [Multiclass Learnability Does Not Imply Sample Compression](https://mlsanity.com/paper/2308.06424/) (2023)
- [A Characterization of List Regression](https://mlsanity.com/paper/2409.19218/) (2024)
- [Semantic Communication of Learnable Concepts](https://mlsanity.com/paper/2305.08126/) (2023)
- [Smoothed Online Classification can be Harder than Batch Classification](https://mlsanity.com/paper/2405.15424/) (2024)
- [Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences](https://mlsanity.com/paper/2603.26852/) (2026)
- [Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions](https://mlsanity.com/paper/2510.08382/) (2025)
- [High-arity Sample Compression](https://mlsanity.com/paper/2605.12465/) (2026)

## Abstract (arXiv)

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. The central theme of this work is establishing equivalences between learnability and compressibility, and utilizing these equivalences in the study of statistical learning theory. We begin with the setting of multiclass categorization (zero/one loss). We prove that in this case learnability is equivalent to compression of logarithmic sample size, and that uniform convergence implies compression of constant size. We then consider Vapnik's general learning setting: we show that in order to extend the compressibility-learnability equivalence to this case, it is necessary to consider an approximate variant of compression. Finally, we provide some applications of the compressibility-learnability equivalences: (i) Agnostic-case learnability and realizable-case learnability are equivalent in multiclass categorization problems (in terms of sample complexity). (ii) This equivalence between agnostic-case learnability and realizable-case learnability does not hold for general learning problems: There exists a learning problem whose loss function takes just three values, under which agnostic-case and realizable-case learnability are not equivalent. (iii) Uniform convergence implies compression of constant size in multiclass categorization problems. Part of the argument includes an analysis of the uniform convergence rate in terms of the graph dimension, in which we improve upon previous bounds. (iv) A dichotomy for sample compression in multiclass categorization problems: If a non-trivial compression exists then a compression of logarithmic size exists. (v) A compactness theorem for multiclass categorization problems.