Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
Abstract
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 k, 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 k/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 k/N + O(1/√N), uniformly over all possible values of k. 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 k/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.
Related
BibTeX
@misc{garatti2026learning,
title = {{Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate}},
author = {Simone Garatti and Marco C. Campi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13442},
eprint = {2610.13442},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13442},
}
RIS
TY - UNPB
TI - Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate
AU - Simone Garatti
AU - Marco C. Campi
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13442
UR - https://arxiv.org/abs/2610.13442
AB - 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 k, 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 k/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 k/N + O(1/√N), uniformly over all possible values of k. 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 k/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.
ER -