Unbounded-Loss ERM Under Finite-Variance Assumptions

Why finite variance changes the ERM guarantee

For bounded losses, concentration inequalities can give finite-class ERM guarantees whose confidence dependence is logarithmic. An unbounded loss need not satisfy those tail conditions. If its variance is finite, however, Chebyshev’s inequality still controls empirical risk deviations. The resulting guarantee is generally weaker in its dependence on confidence, but it applies without a uniform bound on the loss.

The distinction matters in settings where large losses are possible but their second moments remain finite. The variance of each candidate’s loss determines how noisy its empirical risk is; the number of candidates determines how many deviations must be controlled at once. The result below makes both roles explicit.

Definition: Let $X_1,\ldots,X_n$ be independent and identically distributed observations with distribution $P$, and let $\mathcal H$ be a nonempty finite class of candidates. For $h\in\mathcal H$, let $\ell_h(X)$ be a measurable, real-valued loss. Its risk and empirical risk are $$ R(h)=E[\ell_h(X)], \qquad \widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n \ell_h(X_i). $$ Assume $E[\ell_h(X)^2]<\infty$ for every $h\in\mathcal H$. Then each risk is finite and each loss variance $v_h=\operatorname{Var}(\ell_h(X))$ is finite. An empirical risk minimizer $\hat h$ satisfies $\widehat R_n(\hat h)=\min_{h\in\mathcal H}\widehat R_n(h)$. Since the class is finite, a fixed ordering can be used to break ties measurably. Write $h^*$ for a risk minimizer, which exists because $\mathcal H$ is finite.

No independence assumption is made between the losses of different candidates on the same observation. They may be highly dependent because they are all evaluated on $X_i$. Independence is required across observations, so that each candidate’s empirical risk is an average of independent, identically distributed losses.

A uniform deviation bound from finite variances

For a fixed candidate $h$, independence across observations gives $\operatorname{Var}(\widehat R_n(h))=v_h/n$. Chebyshev’s inequality then bounds the chance that its empirical risk differs substantially from its risk. Applying a union bound controls all candidates simultaneously; this step requires no independence between candidates’ empirical risks.

Theorem: Under the assumptions in the definition, set $V=\sum_{h\in\mathcal H}v_h$. For every $t>0$, $$ P\left(\max_{h\in\mathcal H}|\widehat R_n(h)-R(h)|>t\right) \leq \frac{V}{nt^2}. $$ In particular, for $0<\delta<1$, with probability at least $1-\delta$, $$ \max_{h\in\mathcal H}|\widehat R_n(h)-R(h)| \leq \sqrt{\frac{V}{n\delta}}. $$

Proof. For each fixed $h$, the variables $\ell_h(X_i)$ are independent and identically distributed with finite variance $v_h$. Therefore, $$ \operatorname{Var}(\widehat R_n(h)) =\operatorname{Var}\left(\frac{1}{n}\sum_{i=1}^n\ell_h(X_i)\right) =\frac{1}{n^2}\sum_{i=1}^n v_h =\frac{v_h}{n}. $$ Chebyshev’s inequality gives $$ P\left(|\widehat R_n(h)-R(h)|>t\right) \leq \frac{v_h}{nt^2}. $$ Taking a union bound over the finite class, $$ P\left(\max_{h\in\mathcal H}|\widehat R_n(h)-R(h)|>t\right) \leq \sum_{h\in\mathcal H}\frac{v_h}{nt^2} =\frac{V}{nt^2}. $$ Set $t=\sqrt{V/(n\delta)}$ when $V>0$, which makes the right side $\delta$. If $V=0$, every candidate’s loss is constant almost surely, so all empirical risks equal their population risks almost surely and the deviation is zero. This proves both claims. $\square$

Worked Example: A Variance-Sum Bound for Three Candidates

Suppose $X\sim N(0,1)$, and the three candidate losses are $\ell_1(X)=0$, $\ell_2(X)=1+0.1X$, and $\ell_3(X)=2+0.2X$. Their risks are $0,1,2$, respectively. Because $\operatorname{Var}(X)=1$, their loss variances are $0,0.01,0.04$, so $V=0.05$.

For $n=100$ and $\delta=0.05$, the theorem gives the uniform deviation threshold $$ \sqrt{\frac{V}{n\delta}} =\sqrt{\frac{0.05}{100(0.05)}} =\sqrt{0.01} =0.1. $$ Thus all three empirical risks are within $0.1$ of their risks with probability at least $0.95$. The ERM excess-risk guarantee derived below is twice this threshold, or $0.2$. In this example the risk gap between the best and second-best candidates is $1$, so on the event of uniform deviation at most $0.1$, the ERM must select the first candidate.

A convenient but sometimes looser version uses $K=|\mathcal H|$ and $v_{\max}=\max_{h\in\mathcal H}v_h$. Since $V\leq Kv_{\max}$, the deviation threshold can instead be bounded by $\sqrt{Kv_{\max}/(n\delta)}$. The variance-sum version keeps the individual variances visible and may be substantially smaller when most candidates have low variance.

From uniform deviations to excess risk

The ERM’s empirical risk is no larger than that of $h^*$. On any event where every empirical risk is close to its population risk, this empirical comparison also controls the population-risk gap. The following inequality is deterministic: it holds for every sample and every empirical minimizer.

Result: For any sample, any risk minimizer $h^*$, and any empirical risk minimizer $\hat h$, $$ R(\hat h)-R(h^*) \leq 2\max_{h\in\mathcal H}|\widehat R_n(h)-R(h)|. $$ Consequently, under the theorem’s assumptions, for $0<\delta<1$, $$ P\left(R(\hat h)-R(h^*)\leq 2\sqrt{\frac{V}{n\delta}}\right)\geq 1-\delta. $$

Proof. Add and subtract the empirical risks of $\hat h$ and $h^*$: $$ R(\hat h)-R(h^*) =[R(\hat h)-\widehat R_n(\hat h)] +[\widehat R_n(\hat h)-\widehat R_n(h^*)] +[\widehat R_n(h^*)-R(h^*)]. $$ The middle term is nonpositive because $\hat h$ minimizes empirical risk. Each of the other two terms is at most the maximum absolute deviation over $\mathcal H$. Hence $$ R(\hat h)-R(h^*) \leq 2\max_{h\in\mathcal H}|\widehat R_n(h)-R(h)|. $$ Combining this pointwise inequality with the uniform deviation theorem proves the probability statement. $\square$

Worked Example: An Unbounded Pareto Loss

Let $Y$ have a Pareto distribution with density $f(y)=3y^{-4}$ for $y\geq 1$, and zero otherwise. Consider two losses, $\ell_1(Y)=1.4$ and $\ell_2(Y)=Y$. The second loss is unbounded, but its first two moments are finite: $$ E[Y]=\int_1^\infty 3y^{-3}\,dy=\frac{3}{2}, \qquad E[Y^2]=\int_1^\infty 3y^{-2}\,dy=3. $$ Therefore $\operatorname{Var}(Y)=3-(3/2)^2=3/4$. The constant loss has risk $1.4$ and variance zero; the Pareto loss has risk $1.5$ and variance $0.75$. Thus $h^*$ is the constant-loss candidate and $V=0.75$.

With $n=10{,}000$ and $\delta=0.1$, the excess-risk threshold is $$ 2\sqrt{\frac{0.75}{10{,}000(0.1)}} =2\sqrt{0.00075} \approx 0.0548. $$ The ERM’s excess risk is therefore at most approximately $0.0548$ with probability at least $0.9$. Here selecting the Pareto-loss candidate would incur excess risk $1.5-1.4=0.1$, which is larger than the threshold. Thus the guarantee implies that the probability of selecting that candidate is at most $0.1$. This is a finite-variance guarantee for a genuinely unbounded loss.

Worked Example: A Direct Tail Bound for a Desired Accuracy

Suppose a class has $K=4$ candidates, each with loss variance at most $2$. Then $V\leq 4(2)=8$. We can use the theorem directly to bound the probability that the ERM has excess risk greater than $\varepsilon=0.5$. By the deterministic ERM inequality, excess risk greater than $0.5$ requires the maximum deviation to exceed $0.25$. Therefore, $$ P\big(R(\hat h)-R(h^*)>0.5\big) \leq \frac{8}{n(0.25)^2} =\frac{128}{n}. $$ For $n=2{,}560$, this is at most $128/2{,}560=0.05$. Equivalently, the ERM has excess risk at most $0.5$ with probability at least $0.95$. This calculation is valid even when the losses are unbounded, provided each has the stated finite variance and the observations meet the sampling assumptions.

What the guarantee does and does not say

For a fixed finite class with $V<\infty$, the excess-risk bound shrinks as the sample size grows. More explicitly, for every $\varepsilon>0$, the deterministic inequality and the deviation theorem imply $$ P\big(R(\hat h)-R(h^*)>\varepsilon\big) \leq \frac{4V}{n\varepsilon^2}. $$ Indeed, excess risk greater than $\varepsilon$ requires a maximum deviation greater than $\varepsilon/2$, and substituting $t=\varepsilon/2$ into the theorem gives the displayed bound. Its right side tends to zero as $n$ grows, so the ERM’s excess risk converges to zero in probability under these fixed-class, finite-variance assumptions.

The confidence dependence is important. The bound scales as $1/\sqrt{\delta}$, rather than the $\sqrt{\log(1/\delta)}$ dependence available under stronger tail conditions. Finite variance alone does not justify a Hoeffding- or Bernstein-style exponential tail bound: rare, very large losses can be compatible with finite variance. Nor is there a uniform guarantee over an infinite class from this finite union-bound argument. Additional assumptions or methods are needed for those settings.

Common pitfall

Wrong reasoning: “The losses have finite variance, so their empirical averages have exponential concentration, and I can use the same confidence dependence as for bounded losses.”
Correction: Finite variance directly gives Chebyshev’s polynomial tail bound. The theorem here has a $1/\delta$ factor inside the squared deviation threshold. Exponential concentration requires stronger tail assumptions, or a different procedure with its own justified conditions.
Another error: Bounding only the deviation for $h^*$ and concluding that the selected candidate is close to optimal. The ERM can select any candidate, so the comparison must control deviations for the class, or otherwise handle each possible selected candidate. The union bound supplies that control for a finite class.

Key takeaway: For a finite candidate class and independent, identically distributed observations, finite second moments suffice for a high-probability ERM excess-risk guarantee. Its scale is determined by the sum of candidate loss variances, and Chebyshev’s inequality—not exponential concentration—supports the claim.

Check Your Understanding

Use the assumptions and results in this tutorial to answer the following.

Why does finite $\mathcal H$ ensure that a risk minimizer exists when every candidate risk is finite?
Which independence assumption is needed to obtain $\operatorname{Var}(\widehat R_n(h))=v_h/n$? Is independence between candidates’ losses needed?
If four candidates have variances $0,1,1,2$, what is $V$, and what deviation threshold does the theorem give for sample size $n$ and confidence parameter $\delta$?
Explain why the deterministic excess-risk inequality has a factor of two.
What part of the argument fails if a candidate has infinite variance, and why does finite variance not by itself yield exponential confidence dependence?