Uniform convergence of empirical risk: Definition & Examples

Uniform convergence of empirical risk means that sample-average loss approaches population-average loss simultaneously over a hypothesis class. It is what lets a researcher justify selecting a prediction rule after comparing rules on the same sample: a guarantee covering the whole class also covers the chosen member.

For a fixed class $\mathcal H$ , loss $\ell$ and observations $Z_1,\ldots,Z_n$ drawn independently from the same distribution $D$ , define

R(h)=\mathbb E_{Z\sim D}[\ell(h,Z)], \qquad \widehat R_n(h)=\frac1n\sum_{i=1}^n\ell(h,Z_i).

The quantity to control is

\Delta_n=\sup_{h\in\mathcal H}\lvert\widehat R_n(h)-R(h)\rvert.

Convergence in probability means

\mathbb P(\Delta_n>\epsilon)\to0

for every

\epsilon>0

. The distribution-free learning-theory property is stronger: for each accuracy

\epsilon

and failure level

\delta

, a sufficient sample size works for every admissible

D

. “Uniform” here concerns the class of rules; uniform convergence in calculus treats deterministic function sequences. MIT’s learning-theory notes formalize representative samples and this distribution-free property.

One rule, then all rules

Assume $\mathcal H$ is fixed before the sample is drawn, finite, and $0\le\ell(h,Z)\le1$ . For one preselected $h$ , Hoeffding’s inequality gives

\mathbb P\!\left(\lvert\widehat R_n(h)-R(h)\rvert>\epsilon\right) \le2e^{-2n\epsilon^2}.

That statement alone cannot be applied unchanged to a rule chosen by minimizing the same sample’s loss. Apply the union bound to all candidate failure events instead:

\mathbb P(\Delta_n>\epsilon) \le2\lvert\mathcal H\rvert e^{-2n\epsilon^2}.

The rules’ errors need not be independent of one another; they share observations. The union bound needs no independence between events. IID is used for each rule’s average loss. These are the concentration and union-bound steps in Understanding Machine Learning, §4.2, with the union-bound statement also given in Cornell’s Fact 2.3.

Solving for the radius makes the guarantee readable. With probability at least $1-\delta$ ,

\Delta_n\le\epsilon_n, \qquad \epsilon_n=\sqrt{\frac{\ln(2\lvert\mathcal H\rvert/\delta)}{2n}}.

For 10 fixed rules, 1,000 IID observations and $\delta=0.05$ , the radius is

\epsilon_n=\sqrt{\frac{\ln400}{2000}} \approx0.05473328.

Thus every rule’s empirical and population mean losses differ by at most about 0.05473 on one event with probability at least 95%. This is a bound, not an exact coverage rate or a promise that 95% of individual predictions are correct.

Illustrative simultaneous risk bands for ten fixed rules, with n equal to 1,000 and loss in [0, 1]. The common half-width is 0.05473 at confidence at least 95%. Rule 3 minimizes empirical risk at 0.18 but has population risk 0.225; rule 7 has the lowest population risk, 0.19. The excess risk 0.035 is below the theoretical bound 0.10947.

Original illustrative values on a simultaneous-coverage event, not a simulation or market experiment. The intervals are empirical risk plus or minus 0.05473; diamonds show hypothetical population risks, which are normally unknown. Coverage permits a ranking reversal.

Why ERM pays for two deviations

Let

\widehat h

minimize empirical risk exactly over this class, and let

h^*

minimize population risk within it. On the same simultaneous event,

\begin{aligned} R(\widehat h) &\le\widehat R_n(\widehat h)+\epsilon_n\\ &\le\widehat R_n(h^*)+\epsilon_n\\ &\le R(h^*)+2\epsilon_n. \end{aligned}

One deviation moves from the selected rule’s population risk to its empirical risk; the other moves from the comparator’s empirical risk to its population risk. ERM supplies the middle inequality. No second confidence penalty is needed. Here the excess-risk bound is

2\epsilon_n\approx0.10946657

; the figure’s illustrative excess risk is only

0.225-0.190=0.035

. MIT’s ERM argument gives this connection to agnostic PAC learning.

The comparator is best in $\mathcal H$ . To compare with Bayes risk

R_{\mathrm B}

, add the approximation gap

R(h^*)-R_{\mathrm B}

. Increasing data does not remove that gap while the class stays fixed.

Where a quant application needs more work

Searching within the declared class is covered; inventing extra rules after inspecting results is not covered by counting only the ten survivors. The class must encompass the search being justified. Infinite classes need complexity control, such as VC dimension, rather than substitution of infinity into the finite-class bound.

Serially dependent returns, overlapping labels and distribution changes require arguments beyond this IID result. Unbounded squared losses also fall outside its stated loss range. Even a valid guarantee concerns expected loss under $D$ ; it does not establish profitability after costs or performance under a new market regime.

Uniform convergence is a statistical property, not an efficient optimization algorithm. Finding the empirical minimizer may still be difficult; Cornell’s Definition 1.1 treats computational efficiency separately.

For the finite-class derivation and the ERM comparison, continue with Sample Complexity Bounds: Finite and Infinite Hypothesis Classes (membership required for the full lesson; public preview available).

Sources

Shalev-Shwartz and Ben-David, Understanding Machine Learning, §§4.1–4.2: representative samples, bounded-loss concentration and finite-class uniform convergence.
MIT 6.790, Learnability and VC Dimension: distribution-free uniform convergence and the ERM excess-risk argument.
Haghtalab, Cornell CS6781, Lecture 3: Fact 2.3 on the union bound and Definition 1.1 separating accuracy guarantees from computational efficiency.

One rule, then all rules

Why ERM pays for two deviations

Where a quant application needs more work

Sources

Related terms

PAC learning

Uniform convergence

VC dimension and shattering