# Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 30 references that are in the map.
- First posted on arXiv 9 Oct 2026.

## Builds on (most cited first, 7 of 7)

- [Proper Learning, Helly Number, and an Optimal SVM Bound](https://mlsanity.com/paper/2005.11818/) (2020)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Stable Sample Compression Schemes: New Applications and an Optimal SVM Margin Bound](https://mlsanity.com/paper/2011.04586/) (2020)
- [Active Nearest-Neighbor Learning in Metric Spaces](https://mlsanity.com/paper/1605.06792/) (2016)
- [A Theory of the Risk for Optimization with Relaxation and its Application to Support Vector Machines](https://mlsanity.com/paper/2004.05839/) (2020)
- [Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions](https://mlsanity.com/paper/1705.08184/) (2017)
- [Pick-to-Learn for Systems and Control: Data-driven Synthesis with State-of-the-art Safety Guarantees](https://mlsanity.com/paper/2512.04781/) (2025)

## Abstract (arXiv)

Compression schemes provide a general framework for deriving data-dependent risk bounds for learning algorithms. For learning rules based on preferent compression, existing results upper-bound the risk in terms of a sample-dependent complexity boldsymbolk, defined as the cardinality of the compression augmented by the training examples on which the reconstructed hypothesis is inappropriate. These results, however, yield a margin of order O(√ln N/N) above boldsymbolk/N. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level 1-δ, the risk is bounded with probability at least 1-δ by  fracboldsymbolkN + Oleft(frac1√Nright),  uniformly over all possible values of boldsymbolk. Thus, risk estimates for learning algorithms based on preferent compression attain the same law-of-large-numbers rate as the empirical estimate of the probability of a fixed event. We also show that the leading term boldsymbolk/N is necessary and investigate its relation to the empirical risk. In particular, we identify regimes in which the empirical risk retains the O(1/√N) convergence rate, as well as regimes in which it converges more slowly or ceases to be consistent, while the complexity-based estimator preserves the O(1/√N) rate.