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

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.