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

arXiv:2610.13442v1 Announce Type: cross 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 oldsymbol{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(sqrt{ln N/N}) above oldsymbol{k}/N. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed confidence level 1-elta, the risk is bounded with probability at least 1-elta by $ frac{oldsymbol{k}}{N} + Oleft(frac{1}{sqrt{N}}right), uniformly over all possible values of oldsymbol{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 oldsymbol{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/sqrt{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/sqrt{N})$ rate.

Source: arXiv cs.LG | 2026-10-12