Uniform Risk Convergence Implies ERM Consistency

From Empirical Fit to Population Risk

An empirical risk minimizer is chosen using the observed sample, but its purpose is usually to perform well on new observations from the same distribution. To connect those goals, we need a condition that controls empirical risk simultaneously over every candidate, not just for a fixed candidate. Uniform convergence supplies that control. Combined with approximate empirical minimization, it yields a direct bound on how far the selected candidate’s population risk can be from the best risk available in the class.

The conclusion is consistency in excess risk: the selected candidate’s population risk approaches the infimum population risk. This conclusion concerns risk, not necessarily convergence of the candidate itself or of a parameter used to represent it.

Risks and Uniform Deviation

Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$. Let $\mathcal H$ be a nonempty class of candidates, and let $\ell(h,z)$ be a measurable loss. Assume $R(h)=E[\ell(h,Z)]$ is finite for every $h\in\mathcal H$, and define the empirical risk by averaging the observed losses.

R(h)=E[\ell(h,Z)], \qquad \widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n \ell(h,Z_i).

The best population risk in the class is an infimum, which need not be attained. The uniform deviation measures the largest absolute difference between empirical and population risk over the entire class.

R_*=\inf_{h\in\mathcal H}R(h), \qquad D_n=\sup_{h\in\mathcal H}\left|\widehat R_n(h)-R(h)\right|.

Definition: The excess risk of a candidate $h$ is $R(h)-R_*$. An estimator $\hat h_n$ has excess risk $R(\hat h_n)-R_*$, a nonnegative quantity. Uniform risk convergence means $D_n\xrightarrow{p}0$, or $D_n\xrightarrow{a.s.}0$ when almost-sure convergence is intended.

For clarity, assume the relevant suprema, infima, and selected risks are measurable, and that $\hat h_n$ is a measurable data-dependent choice. These are technical conditions needed to treat $D_n$ and the excess risk as random variables. The key inequality below is deterministic for each sample on which its conditions hold.

Definition: Given a nonnegative tolerance $\varepsilon_n$, $\hat h_n$ is an $\varepsilon_n$-approximate empirical minimizer if $$ \widehat R_n(\hat h_n)\leq \inf_{h\in\mathcal H}\widehat R_n(h)+\varepsilon_n. $$ The tolerance may be deterministic or random. Exact empirical minimization is the special case $\varepsilon_n=0$, when a minimizer exists and is selected.

Worked Examples

Worked Example: Computing the Uniform Deviation

Consider a finite class $\mathcal H=\{h_1,h_2,h_3\}$ and a loss taking values zero or one. A model for one observation is $Z=(B_1,B_2,B_3)$, where the coordinates are independent Bernoulli random variables with probabilities $0.40,0.35,0.43$, respectively, and $\ell(h_j,Z)=B_j$. Thus the population risks are $R(h_1)=0.40$, $R(h_2)=0.35$, and $R(h_3)=0.43$.

Suppose a sample of size $50$ has coordinate totals $21,18,21$. The empirical risks are therefore $0.42,0.36,0.42$. The signed empirical-minus-population differences are

0.42-0.40=0.02,\qquad 0.36-0.35=0.01,\qquad 0.42-0.43=-0.01.

Taking absolute values gives $0.02,0.01,0.01$, so $D_n=0.02$. The empirical minimizer is $h_2$, whose population risk is also the class infimum, $R_*=0.35$. Its excess risk is $0.35-0.35=0$. The uniform-deviation bound proved below gives the valid, though loose, upper bound $2D_n=0.04$.

Worked Example: The Cost of Optimization Tolerance

Let $\mathcal H=\{h_1,h_2\}$, with zero-one losses whose population risks are $R(h_1)=0.40$ and $R(h_2)=0.42$. For example, take an observation $Z=(B_1,B_2)$ with independent Bernoulli coordinates of those probabilities and set $\ell(h_j,Z)=B_j$. In a sample of size $50$, suppose the two coordinate totals are $19$ and $20$. Then $\widehat R_n(h_1)=0.38$ and $\widehat R_n(h_2)=0.40$.

The deviations are $|0.38-0.40|=0.02$ and $|0.40-0.42|=0.02$, so $D_n=0.02$. Select $h_2$, which is an approximate empirical minimizer with $\varepsilon_n=0.02$, because

\widehat R_n(h_2)=0.40=0.38+0.02 =\inf_{h\in\mathcal H}\widehat R_n(h)+\varepsilon_n.

Here $R_*=0.40$, so the selected excess risk is $0.42-0.40=0.02$. The general bound is $2D_n+\varepsilon_n=2(0.02)+0.02=0.06$, which indeed exceeds the actual excess risk. The tolerance appears additively: inaccurate optimization can use up part of the available risk guarantee.

Worked Example: Consistency Without an Attained Infimum

Let the sample space contain one point $z_0$, with $P(Z=z_0)=1$. Take the fixed class $\mathcal H=\{h_k:k=1,2,\ldots\}$ and define $\ell(h_k,z_0)=1/k$. For every sample size and every observed sample, $R(h_k)=\widehat R_n(h_k)=1/k$. Hence $R_*=0$, but no member of the class attains this infimum, and $D_n=0$.

At sample size $n$, select $\hat h_n=h_n$. Since $\inf_k\widehat R_n(h_k)=0$, this selection is an $\varepsilon_n$-approximate empirical minimizer for $\varepsilon_n=1/n$. Its excess risk is exactly $R(h_n)-R_*=1/n$, which tends to zero. This example shows why the argument can use an infimum and approximate minimizers without assuming that a best population candidate exists.

The Excess-Risk Inequality

Uniform control applies to the data-dependent choice $\hat h_n$ just as it applies to every fixed candidate. It also lets us compare the empirical infimum to the population infimum, even when neither is attained.

Theorem: Suppose $D_n<\infty$ and $\hat h_n$ satisfies the $\varepsilon_n$-approximate empirical minimization inequality for a nonnegative $\varepsilon_n$. Then, sample by sample, $$ 0\leq R(\hat h_n)-R_*\leq 2D_n+\varepsilon_n. $$

Proof. By the definition of $D_n$, every $h\in\mathcal H$ satisfies $R(h)\leq\widehat R_n(h)+D_n$. In particular,

R(\hat h_n)\leq\widehat R_n(\hat h_n)+D_n.

Approximate empirical minimization gives $\widehat R_n(\hat h_n)\leq\inf_{h\in\mathcal H}\widehat R_n(h)+\varepsilon_n$. Also, for every $h$, $\widehat R_n(h)\leq R(h)+D_n$, so taking infima over $h$ gives

\inf_{h\in\mathcal H}\widehat R_n(h) \leq \inf_{h\in\mathcal H}\bigl(R(h)+D_n\bigr) =R_*+D_n.

Combining these inequalities yields $R(\hat h_n)\leq R_*+2D_n+\varepsilon_n$. Since $R_*$ is the infimum of the population risks, $R(\hat h_n)-R_*\geq0$. This proves both bounds. $\square$

Consistency in Probability and Almost Surely

The deterministic inequality immediately gives the usual consistency conclusions. The optimization tolerance must vanish in the same mode of convergence as the uniform deviation. No independence between $D_n$ and $\varepsilon_n$ is required.

Corollary: If $D_n\xrightarrow{p}0$ and $\varepsilon_n\xrightarrow{p}0$, then $$ R(\hat h_n)-R_*\xrightarrow{p}0. $$ If instead $D_n\xrightarrow{a.s.}0$ and $\varepsilon_n\xrightarrow{a.s.}0$, then $R(\hat h_n)-R_*\xrightarrow{a.s.}0$.

Proof. Write $E_n=R(\hat h_n)-R_*$. The theorem gives $0\leq E_n\leq2D_n+\varepsilon_n$. For any $\eta>0$, if $E_n>\eta$, then at least one of $D_n>\eta/4$ or $\varepsilon_n>\eta/2$ must hold: otherwise $2D_n+\varepsilon_n\leq\eta$. Therefore

P(E_n>\eta) \leq P(D_n>\eta/4)+P(\varepsilon_n>\eta/2) \longrightarrow 0.

This proves convergence in probability. For almost-sure convergence, on every sample path where both $D_n$ and $\varepsilon_n$ tend to zero, their upper bound $2D_n+\varepsilon_n$ tends to zero as well. The squeeze $0\leq E_n\leq2D_n+\varepsilon_n$ then gives $E_n\to0$ on that path. $\square$

The inequality also makes quantitative guarantees easy to read. On any event where $D_n\leq a_n$ and $\varepsilon_n\leq b_n$, the excess risk is at most $2a_n+b_n$. Thus a generalization guarantee and an optimization guarantee contribute separate terms. Uniform convergence alone is not enough if optimization error remains large, and accurate empirical optimization alone is not enough if the empirical risks fail to track population risks uniformly.

Common Pitfall: Pointwise Is Not Uniform

A tempting but invalid argument is: “For each fixed $h$, empirical risk approaches population risk; therefore this also holds for the candidate selected from the data.” The candidate $\hat h_n$ depends on the sample. A pointwise statement controls each fixed $h$ separately, but does not by itself provide a single deviation bound that holds over all candidates, including this data-dependent one. The proof above specifically uses $D_n=\sup_{h\in\mathcal H}|\widehat R_n(h)-R(h)|$ to control $\hat h_n$ and the empirical infimum at the same time.

A second mistake is to assume that the best population candidate must exist in order to compare empirical and population risks. The proof only needs $R_*=\inf_h R(h)$; taking the infimum of the inequalities over the class is sufficient. Nor does excess-risk consistency automatically imply that a parameter estimate converges to a unique parameter. It establishes convergence of risk to the class optimum, which is the conclusion guaranteed by these assumptions.

Key takeaway: Uniform risk deviation and empirical optimization tolerance combine through $$ R(\hat h_n)-R_*\leq 2D_n+\varepsilon_n. $$ If both terms vanish in probability or almost surely, the approximate empirical minimizer is consistent in excess risk.

Check Your Understanding

Answer each question using the definitions and inequality above.

Why does the theorem compare $R(\hat h_n)$ with an infimum rather than requiring a population-risk minimizer?
If $D_n=0.03$ and $\varepsilon_n=0.01$, what upper bound does the theorem give on excess risk?
State the convergence assumptions needed to conclude excess-risk convergence in probability.
Which step in the proof uses uniform, rather than pointwise, control of empirical risk?
Does excess-risk consistency by itself imply that the selected candidate converges to a unique element of $\mathcal H$? Explain briefly.