Risk Estimation for Learning by Compression Achieves Law of Large Numbers Convergence Rate

New Generalization Risk Results Under the Compression Framework

Compression schemes are a general framework for deriving data-dependent risk bounds for learning algorithms. The core idea is this: if a learning algorithm can "compress" and reconstruct a hypothesis using only a small subset of training samples, that compression capability itself carries a generalization guarantee. The fewer samples needed and the more accurate the reconstruction, the more likely the model is to generalize well.

This paper focuses on learning rules based on preferent compression and establishes a tighter result on the convergence rate of their risk upper bounds. The central contribution is proving that the logarithmic factors appearing in prior risk bounds are not essential, thereby lifting the convergence rate to match that of the classical law of large numbers.

From Logarithmic Factors to Law of Large Numbers Rate

In existing theoretical results for preferent compression learning rules, risk is characterized by a sample-dependent complexity measure $\boldsymbol{k}$. Here, $\boldsymbol{k}$ is defined as the cardinality of the compression set plus the number of training samples on which the reconstructed hypothesis behaves inappropriately.

The issue is that these prior results attach an additional term of order $O(\sqrt{\ln N / N})$ on top of $\boldsymbol{k}/N$. The logarithmic factor $\sqrt{\ln N}$, while growing slowly, makes the convergence rate theoretically suboptimal.

The paper's main theorem proves that for every fixed confidence level $1-\delta$, the risk is upper bounded with probability at least $1-\delta$ by:

$$\frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right)$$

Moreover, this upper bound holds uniformly over all possible values of $\boldsymbol{k}$. In other words, the logarithmic factor is entirely eliminated, and risk estimation based on preferent compression achieves the same law of large numbers convergence rate $O(1/\sqrt{N})$ as empirical estimation of fixed-event probabilities. This is a rate-optimal result that cannot be further improved.

Necessity of the Dominant Term k/N

Theoretical work often demands not only tighter upper bounds, but also a demonstration that those bounds are tight. The paper addresses this as well: the dominant term $\boldsymbol{k}/N$ is necessary and cannot be further eliminated or reduced. This means the complexity measure $\boldsymbol{k}$ is indeed an essential parameter for characterizing the risk of compression-based learning, while the $O(1/\sqrt{N})$ remainder represents the optimal range of fluctuation around it.

This two-sided argument — an achievable upper bound paired with a necessary lower bound — makes the result theoretically complete. It clearly delineates the precision boundary achievable by compression-based risk estimation.

Comparison with Empirical Risk

Another valuable direction in the paper is exploring the relationship between the complexity measure $\boldsymbol{k}/N$ and the traditional empirical risk, the most commonly used performance metric in machine learning. Empirical risk, however, exhibits very different convergence behavior across different settings.

The paper identifies several distinct regimes:

• In some regimes, empirical risk maintains the $O(1/\sqrt{N})$ convergence rate, consistent with the complexity-based estimator;
• In other regimes, empirical risk converges noticeably more slowly;
• In still other regimes, empirical risk loses consistency entirely — it can no longer converge to the true risk as the number of samples grows.

Regardless of regime, the compression-complexity-based estimator stably maintains the $O(1/\sqrt{N})$ convergence rate. This contrast highlights the robustness of the compression framework: when empirical risk breaks down due to sample structure or hypothesis complexity, complexity-type estimation still provides reliable generalization guarantees.

Significance and Positioning

This work belongs to the domain of foundational statistical learning theory. It does not address specific engineering implementations or model architectures, but rather advances the theoretical precision of generalization bounds. Lifting the convergence rate from $O(\sqrt{\ln N/N})$ to $O(1/\sqrt{N})$ may appear to be merely dropping a logarithmic factor, but theoretically it means risk estimation has reached the information-theoretically optimal rate.

For researchers working on generalization theory, PAC learning, and sample compression bounds, this result fills the last gap in the preferent compression framework's convergence rate story. By contrasting with empirical risk, it further demonstrates the theoretical advantages of compression-type complexity measures as tools for risk estimation.