PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Simone Garatti, Marco C. Campi

arXiv:2610.13442v1stat.MLcs.LGmath.ST

TL;DR

Estimating risk is challenging because the failure event depends on a hypothesis learned from the data. The paper extends stable-compression risk bounds and establishes that their convergence rate matches fixed-event empirical estimation, uniformly over k.

  • Problem

    Risk estimation is more complex than estimating a fixed-event probability because a learned classifier’s failure event depends on the data-constructed classifier.

    Source: §1 · p. 2

  • Method

    The paper extends prior stable-compression analysis, using a proof approach that takes an arbitrary user-chosen margin function and returns a confidence bound.

    Source: §4 · p. 13

  • Results

    Stable-compression risk estimates attain the same convergence rate as fixed-event empirical estimation, with the margin tending to zero uniformly over k.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    Using data to learn does not slow the risk-estimation rate for the stable-compression frameworks considered.

    Source: §1 · p. 4

    The proof’s chosen margin is smallest at k-hat but may be far from smallest for substantially larger k values.

    Source: §4 · p. 17

Abstract

from arXiv · show

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 confidence level $1-δ$, the risk is bounded with probability at least $1-δ$ by $$ \frac{\boldsymbol{k}}{N} + O\left(\frac{1}{\sqrt{N}}\right), $$ uniformly over all possible values of $\boldsymbol{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 $\boldsymbol{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.

1 Introduction

The introduction frames risk estimation as harder than fixed-event probability estimation because the learned hypothesis depends on the data. It presents a stable-compression result extending the fixed-event estimator’s convergence rate to learning-based risk estimates.

1 Introduction

  • The risk of a learned hypothesis is harder to estimate than a fixed-event probability because the hypothesis is constructed from the data.The event of classifier failure therefore depends on a stochastic, data-designed classifier.Source: §1 · p. 2
  • The sample-dependent complexity k combines compression-set cardinality with training examples where the reconstructed hypothesis is inappropriate.Examples already in the compression set are excluded from the added count.Source: §1 · p. 3
  • The paper identifies k/N as the leading term in its risk bound and investigates how the complexity-based estimate relates to empirical risk.The introduction says the k/N term is necessary.Source: §1 · pp. 3–4
  • The paper establishes that stable-compression risk estimates attain the same convergence rate as empirical estimation of a fixed-event probability.The stated margin tends to zero uniformly over values of k.Source: §1 · pp. 3–4

2 Preferent compression schemes and risk evaluation

This section sets up preferent compression and risk evaluation, then reviews existing bounds whose margin scales as O(sqrt(ln(N)/N)). It motivates the paper’s question of whether a smaller margin can hold uniformly in the sample-dependent complexity k.

2.1 Notation

  • Under i.i.d. sampling, the paper represents a training set as a multiset and defines risk as the probability that a hypothesis is inappropriate for a new example.The loss is 0 for appropriate examples and 1 for inappropriate ones.Source: §2.1 · pp. 4–5

2.2 Change of compression and risk bounds

  • Preferent compression is presented as broadly applicable, including to SVM, GEM, nearest-neighbor, and Total Recall methods.A cited meta-algorithm can transform any learning algorithm into a compression scheme satisfying preference.Source: §2.2 · pp. 5–6
  • The prior bound’s margin is O(sqrt(ln(N)/N)), uniformly in compression cardinality k.Under preference, the cited result bounds probability of change of compression using compression cardinality.Source: §2.2 · p. 6
  • For risk estimation, k counts the compression set plus training examples where the reconstructed hypothesis is inappropriate, avoiding double counting.The existing result bounds risk using a margin added to k/N.Source: §2.2 · p. 7
  • The leading term k/N is necessary: for confidence levels δ < 0.5, a valid replacement must add a suitable nonnegative margin.This motivates the paper’s question of whether the margin can be O(1/sqrt(N)).Source: §2.2 · p. 7

3 New convergence results

The section derives a confidence-qualified risk bound in terms of complexity and compares it with empirical risk across excess-complexity regimes.

3 New convergence results

  • Under preference and a reconstruction function, risk is upper-bounded by k/N + µ(N,δ) with confidence at least 1−δ.Source: §3 · pp. 8–9

3.1 Form empirical risk to complexity: a natural extension

  • Writing k_i for inappropriate training examples and k_e = k − k_i, empirical risk is k_i/N and k_e/N is the excess added to form k/N.Source: §3.1 · p. 9
  • When k_e is uniformly bounded in N, empirical risk estimates risk with confidence 1−δ and margin O(1/sqrt N).Source: §3.1 · p. 9
  • In Cases 3 and 4, empirical risk is no longer a fast-converging estimator and may lose consistency, while k/N preserves fast convergence.Source: §3.1 · p. 12

4 Proof of Theorem 3

The proof uses Theorem 5 in reverse to obtain a complexity-based risk bound at user-specified confidence. An alternative choice in its construction yields the desired asymptotic convergence rate, though it is less favorable for moderate sample sizes.

4 Proof of Theorem 3

  • Theorem 5 can compute a valid complexity-based risk upper bound at user-specified confidence 1−δ, using the cardinality-dependent function ε(·).The proof applies the theorem to obtain P{ϕ_N ≤ ε_|c(z_1,...,z_N)|} ≥ 1−δ.Source: §4 · pp. 13–14
  • An alternative choice of the λ_m values yields the desired asymptotic convergence rate, although it is typically less favorable than for moderate N.The proof selects the λ_m values to construct ε(·), then bounds its margin above k/N.Source: §4 · p. 14
  • The proof derives an explicit margin function ε(·) and an explicit expression for μ(N,δ).It bounds ε_k over k=0,...,N before substituting the bound to obtain μ(N,δ).Source: §4 · p. 16
  • The construction also allows ε_k values for k other than the selected ˆk to be reduced while maintaining confidence 1−δ.The resulting ε_k values need not be individually smallest; for ˆk values much smaller than ˇk, ε_ˇk may remain far from its minimum.Source: §4 · p. 17

A Valid margin for empirical means

The section applies the Central Limit Theorem to empirical means of indicators for a fixed event. The probability in the displayed statement tends to 1/2 whenever the event probability is neither zero nor one.

A Valid margin for empirical means

B Term k/N is strictly necessary

A constructed compression scheme shows that the leading term k/N cannot be reduced for any k in its domain when δ<0.5. The argument gives probability at least 0.5 to a setup where the risk is no smaller than that term.

B Term k/N is strictly necessary

  • In the example, each z_i takes values in [0,1] with a uniform distribution; for a given N, an integer k̄ is selected from {0,...,N}, and c and A are defined on multisets of points in [0,1].Source: B Term k/N is strictly necessary · p. 20
  • For every k in {0,...,N}, the k/N term cannot be reduced when δ<0.5.With probability at least 0.5, the constructed setup has k= k̄ and risk at least k̄/N.Source: B Term k/N is strictly necessary · pp. 20–21
  • In the constructed setup, k equals the compression cardinality because all inappropriate training points are already included in the compression..Source: B Term k/N is strictly necessary · p. 21

C Proof of the results mentioned in Remark 1

The appendix proves claims about optimizing the confidence allocations λ_m and relates one result to an elementary argument in a recent article. It shows that concentrating the allocation at a suitable index minimizes ε_ˆk for a given ˆk.

C Proof of the results mentioned in Remark 1

Loading 2610.13442v1…