{"id":"arxiv/2610.13442","url":"https://arxiv.org/abs/2610.13442","tags":["stat.ML","cs.LG","math.ST"],"score":0,"title":"Learning by Compression: Risk Estimates Attain the Law-of-Large-Numbers Rate","domain":"stat.ML","source":"arxiv","authors":["Simone Garatti","Marco C. Campi"],"reviews":0,"subject":"stat.ML","summary":"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 $\\boldsymbol{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 $\\boldsymbol{k}/N$. In this paper, we establish that the logarithmic factor is not intrinsic. We prove that, for every fixed…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}