Slow Rates for Bounded-Loss ERM

Why Bounded Losses Give a Slow Rate

Empirical risk minimization chooses a predictor whose average loss on the observed sample is small. The population objective, however, is its average loss on new observations. The difference between these two quantities is sampling error, and the empirical minimizer can exploit fluctuations in the sample. A uniform deviation bound controls this problem by requiring empirical risks to be close to population risks across the whole candidate class.

With bounded losses, standard concentration typically makes that deviation of order $n^{-1/2}$, up to a factor reflecting the size or complexity of the class. The ERM excess-risk bound inherits this square-root scale. This is called a slow rate: boundedness by itself does not generally make the excess risk decrease at the faster order $n^{-1}$.

Definition: Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$, and let $\mathcal H$ be a class of predictors. For a loss function $\mathcal L(h,z)\in[0,1]$, define the population risk and empirical risk by $$ R(h)=E[\mathcal L(h,Z)], \qquad \widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n \mathcal L(h,Z_i). $$ The uniform deviation is $$ D_n=\sup_{h\in\mathcal H}\left|\widehat R_n(h)-R(h)\right|. $$ Write $R^*=\inf_{h\in\mathcal H}R(h)$. An exact ERM $\hat h$ satisfies $\widehat R_n(\hat h)=\inf_{h\in\mathcal H}\widehat R_n(h)$.

The class and loss are assumed measurable enough that the risks, supremum $D_n$, and selected ERM are measurable random quantities. We assume an exact ERM exists when we state results for $\hat h$. The infimum $R^*$ need not be attained; the argument below handles that case by comparison with predictors arbitrarily close to the infimum.

The Basic Excess-Risk Bound

The key argument is short: on a sample where every empirical risk is close to its population counterpart, the empirical minimizer cannot have much larger population risk than the best available predictor. The price is two deviations—one for the selected ERM and one for the comparator.

Theorem: For any sample on which $D_n$ is finite, an exact ERM satisfies $$ R(\hat h)-R^*\leq 2D_n. $$ Consequently, if $P(D_n\leq a)\geq 1-\delta$, then $$ P\bigl(R(\hat h)-R^*\leq 2a\bigr)\geq 1-\delta. $$ If $E[D_n]<\infty$, then $E[R(\hat h)-R^*]\leq 2E[D_n]$.

Proof. Fix any $h\in\mathcal H$. By the definition of $D_n$,

R(\hat h)\leq \widehat R_n(\hat h)+D_n \leq \widehat R_n(h)+D_n \leq R(h)+2D_n.

The middle inequality holds because $\hat h$ minimizes empirical risk. Since this bound holds for every $h$, take the infimum over $h\in\mathcal H$ on the right to obtain $R(\hat h)\leq R^*+2D_n$. This proves the pointwise bound. The probability statement follows because $D_n\leq a$ implies the excess risk is at most $2a$. Taking expectations in the pointwise inequality gives the expected-risk statement. $\square$

The inequality separates the ERM step from the concentration step. The proof uses no special property of the loss beyond the existence of the risks and deviation; boundedness becomes important when we seek a useful probabilistic bound on $D_n$. In particular, if a uniform deviation bound is of order $n^{-1/2}$, the excess-risk guarantee is of that same order, with a factor of two.

Worked Example: Turning a Deviation Bound into an Excess-Risk Bound

Suppose a learning procedure uses an exact ERM and a uniform deviation argument establishes $P(D_n\leq 0.04)\geq 0.95$. Find the resulting high-probability excess-risk guarantee.

On the event $D_n\leq 0.04$, the theorem gives $$ R(\hat h)-R^*\leq 2D_n\leq 2(0.04)=0.08. $$ The event has probability at least $0.95$. Thus the excess risk is at most $0.08$ with probability at least $0.95$. This conclusion is relative to the best risk in $\mathcal H$; it does not say that this best-in-class risk is zero.

Finite Classes: An Explicit Square-Root Rate

For a finite class, uniform deviation control follows by applying a concentration inequality to each predictor and taking a union bound. For any fixed $h$, the variables $\mathcal L(h,Z_i)$ are independent and lie in $[0,1]$. Hoeffding’s inequality therefore gives $$ P\left(\left|\widehat R_n(h)-R(h)\right|>t\right)\leq 2e^{-2nt^2}. $$ If $\mathcal H$ has $M$ elements, the probability that at least one of the $M$ deviations exceeds $t$ is at most the sum of their probabilities. Hence $$ P(D_n>t)\leq 2M e^{-2nt^2}. $$ Choosing $t=\sqrt{\log(2M/\delta)/(2n)}$ makes the right side equal to $\delta$. Combining this with the theorem yields the following bound.

Finite-class bound: If $\mathcal H$ is a finite class of $M\geq 1$ predictors with losses in $[0,1]$, then any exact ERM satisfies, with probability at least $1-\delta$, $$ R(\hat h)-R^* \leq 2\sqrt{\frac{\log(2M/\delta)}{2n}} =\sqrt{\frac{2\log(2M/\delta)}{n}}. $$

Worked Example: A Finite-Class Guarantee

Let $M=20$, $n=1000$, and $\delta=0.05$. Calculate the finite-class excess-risk guarantee.

First, $2M/\delta=40/0.05=800$, so $\log(2M/\delta)=\log(800)\approx 6.6846$. The deviation threshold is $$ t=\sqrt{\frac{6.6846}{2(1000)}}=\sqrt{0.0033423}\approx 0.0578. $$ The excess-risk bound is twice this threshold: $$ R(\hat h)-R^*\leq 2(0.0578)\approx 0.1156. $$ Thus, with probability at least $0.95$, the ERM’s risk is no more than about $0.116$ above the best risk in the 20-predictor class. This is a guarantee, not a claim that the realized excess risk will equal the bound.

For a growing or infinite class, the finite-class calculation does not apply directly. The same ERM inequality still applies, but the deviation must be controlled using a suitable measure of the class’s complexity. If that analysis gives $D_n$ of order $\sqrt{v/n}$ with high probability, for some complexity quantity $v$, the resulting excess-risk scale is also $\sqrt{v/n}$. The form of the deviation bound depends on the setting; the factor-of-two comparison does not.

Why No Low-Noise Assumption Is Needed

The square-root conclusion needs a uniform deviation bound and the ERM comparison, not a condition that the data be easy to classify or that the best predictor be separated from its competitors. Boundedness controls how much one observation can change an empirical average. It does not ensure that two predictors with similar population risks can be reliably distinguished from a small sample.

Worked Example: A Noisy Choice Between Two Classifiers

Let $X$ carry no predictive information and let $Y$ be Bernoulli with $P(Y=1)=0.55$. Consider two constant classifiers: $h_0$ always predicts 0 and $h_1$ always predicts 1, using zero-one loss. Their risks are $$ R(h_0)=P(Y=1)=0.55,\qquad R(h_1)=P(Y=0)=0.45. $$ Thus $h_1$ is best, with $R^*=0.45$, and $h_0$ has excess risk $0.55-0.45=0.10$.

With a sample of size one, ERM chooses the classifier that predicts the observed label: if $Y=0$, it chooses $h_0$, whose observed loss is 0 rather than 1; if $Y=1$, it chooses $h_1$. Therefore the worse classifier $h_0$ is selected with probability $P(Y=0)=0.45$, and on that event the excess risk is $0.10$. The loss is bounded, but a single observation often does not identify the better classifier. This example illustrates why boundedness alone does not promise a faster rate.

In settings with a suitable additional relation between excess risk and loss variability, sharper rates can sometimes be obtained. Boundedness alone imposes no such relation: loss differences can remain variable even when population risks are close. Therefore the general deviation-based guarantee remains at the square-root scale. The absence of a low-noise condition is not a defect in the proof; it is what makes the conclusion broadly applicable.

Common Pitfall: Confusing the Comparator with the Truth

A frequent mistake is to read $R(\hat h)-R^*\leq 2D_n$ as a guarantee that ERM nearly recovers the true data-generating rule. The theorem compares $\hat h$ with the best member of $\mathcal H$, not with a predictor outside the class. If the class cannot represent an excellent predictor, its best possible risk $R^*$ may still be large. The bound controls the estimation gap within the chosen class; it does not remove approximation error.

A second mistake is to infer an $n^{-1}$ excess-risk rate just because the loss is bounded. Boundedness gives concentration for empirical averages at the square-root scale. The ERM inequality then transfers that scale to excess risk. A faster rate requires additional structure beyond bounded loss and uniform deviation control.

Key takeaway: Under bounded loss, a uniform deviation guarantee $D_n\leq a_n$ implies an ERM excess-risk guarantee of at most $2a_n$. When $a_n$ is of order $n^{-1/2}$, the general excess-risk rate is also of order $n^{-1/2}$, without any low-noise assumption.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

Why does the ERM excess-risk bound contain two copies of the uniform deviation?
If $P(D_n\leq 0.03)\geq 0.90$, what high-probability excess-risk bound follows?
For a finite class, which two ingredients produce the factor $\log(M/\delta)$ in the deviation threshold?
Does $R(\hat h)-R^*\leq 2D_n$ imply that $R(\hat h)$ is close to the risk of the true data-generating rule? Explain.
Why does bounded loss alone support a square-root rate rather than guaranteeing a faster one?