The Basic Inequality For Penalized ERM

Why a Basic Inequality Appears

A penalized empirical risk minimizer is selected by minimizing a criterion computed from the observed data. Its defining property is therefore a comparison with every candidate under that same empirical criterion. The basic inequality is this comparison written in a form that can later be related to population risk. It is a starting point, not by itself a guarantee that the selected predictor has small population risk: the gap between empirical and population comparisons remains visible in the inequality.

The useful feature is its simplicity. No convexity, distributional tail condition, or special form of penalty is needed for the algebra. One needs an exact minimizer over the stated class and finite risks for the predictors being compared. Statistical conclusions require further control of the stochastic term; the basic inequality identifies precisely where that control must enter.

Setup and Definition

Let $Z_1,\ldots,Z_n$ be observed data, and let $Z$ denote a generic observation from the target distribution $P$. A predictor $f$ incurs loss $\ell_f(Z)$. Write its population risk as $R(f)=E[\ell_f(Z)]$, and its empirical risk as $P_n\ell_f=n^{-1}\sum_{i=1}^n\ell_f(Z_i)$. The empirical-risk notation is an average over the observed sample; $R(f)$ is an expectation under the target distribution.

Let $\mathcal F$ be the candidate class and let $\operatorname{pen}(f)$ be a fixed penalty assigned to each candidate. Assume the relevant empirical risks and population risks are finite. For the stochastic interpretation, it is common to take the observations to be independent draws from $P$, though the deterministic comparison below holds for any realized data.

Definition: An exact penalized empirical risk minimizer is a predictor $\hat f\in\mathcal F$ satisfying $$ P_n\ell_{\hat f}+\operatorname{pen}(\hat f) = \inf_{f\in\mathcal F}\{P_n\ell_f+\operatorname{pen}(f)\}. $$ The basic inequality is the resulting comparison of this criterion at $\hat f$ and at any comparator $g\in\mathcal F$.

The penalty need not be nonnegative for the algebraic comparison, although penalties used in applications are often nonnegative. The central requirement here is that the same criterion is used for $\hat f$ and $g$. The comparator can be a simple fixed candidate or any other member of the class.

The Basic Inequality

By the definition of a minimizer, replacing $\hat f$ by any $g\in\mathcal F$ cannot reduce the penalized empirical criterion. Subtracting terms gives the equivalent form below.

Theorem (Basic inequality): If $\hat f$ is an exact minimizer of $P_n\ell_f+\operatorname{pen}(f)$ over $\mathcal F$, then, for every $g\in\mathcal F$, $$ P_n\ell_{\hat f}-P_n\ell_g \leq \operatorname{pen}(g)-\operatorname{pen}(\hat f). $$

This is a deterministic statement about the realized sample. In particular, its proof does not need an expectation or a probability argument.

Use minimization.
For any $g\in\mathcal F$, exact minimization gives $P_n\ell_{\hat f}+\operatorname{pen}(\hat f)\leq P_n\ell_g+\operatorname{pen}(g)$.

Rearrange.
Subtract $P_n\ell_g+\operatorname{pen}(\hat f)$ from both sides to obtain the displayed inequality. No approximation or limit is involved.

The inequality also holds simultaneously for every $g\in\mathcal F$: the minimization property applies to each candidate. This does not mean that a later probabilistic bound for a single fixed $g$ automatically holds uniformly over all choices of $g$. The deterministic comparison and the control of random fluctuations are different tasks.

From Empirical Risk to Population Risk

For any two predictors $f$ and $g$, define the stochastic remainder in their risk comparison by $$ \Delta_n(f,g)=(P-P_n)(\ell_f-\ell_g) = \{R(f)-R(g)\}-\{P_n\ell_f-P_n\ell_g\}. $$ Here $P h=E[h(Z)]$, while $P_n h$ is the sample average of $h(Z_i)$. This remainder records the difference between the population and empirical comparisons, not the deviation of either risk in isolation.

Theorem (Population-risk form): Under the assumptions of the basic inequality, for every $g\in\mathcal F$, $$ R(\hat f)-R(g) \leq \operatorname{pen}(g)-\operatorname{pen}(\hat f) +\Delta_n(\hat f,g). $$

To prove the result, add and subtract the empirical risk difference:

\begin{aligned} R(\hat f)-R(g) &= \{P_n\ell_{\hat f}-P_n\ell_g\} +(P-P_n)(\ell_{\hat f}-\ell_g)\\ &\leq \operatorname{pen}(g)-\operatorname{pen}(\hat f) +\Delta_n(\hat f,g). \end{aligned}

The inequality follows from the basic inequality applied to the first term; the second term is exactly the defined remainder. This proves the population-risk form. $\square$

The three components have distinct roles: the empirical-risk comparison is bounded by minimization; the penalty difference reflects the relative charge assigned to the comparator and the selected predictor; and the stochastic remainder accounts for the difference between empirical and population risk comparisons. The remainder can be positive, zero, or negative. The basic inequality alone does not bound it.

Worked Comparisons

Worked Example: Squared-Error Risk With a Quadratic Penalty

Suppose the two observed responses are $0$ and $2$, and the predictors are constants $f_\theta$ that always predict $\theta\in\mathbb R$. Use squared-error loss and penalty $\operatorname{pen}(f_\theta)=\theta^2/2$. Find the penalized empirical minimizer and compare it with $f_1$.

The empirical risk is $$ P_n\ell_{f_\theta} =\frac{(0-\theta)^2+(2-\theta)^2}{2} =\theta^2-2\theta+2. $$ Adding the penalty gives $\frac32\theta^2-2\theta+2$. Its derivative is $3\theta-2$, which is zero at $\hat\theta=2/3$; its second derivative is $3>0$, so this is the unique minimizer.

At $\hat\theta=2/3$, the squared errors are $(0-2/3)^2=4/9$ and $(2-2/3)^2=16/9$, not $4/9$ and $4/9$. Thus the empirical risk is $(4/9+16/9)/2=10/9$, and the penalty is $(2/3)^2/2=2/9$. The penalized criterion is $12/9=4/3$.

At the comparator $\theta=1$, the squared errors are $1$ and $1$, so its empirical risk is $1$; its penalty is $1/2$, and its criterion is $3/2$. The basic inequality reads $10/9-1\leq 1/2-2/9$, or $1/9\leq5/18$, which is true.

Worked Example: A Positive Stochastic Remainder

Let the outcome $Z$ be $A$ or $B$, each with probability $1/2$. A sample of size two happens to be $A,A$. Consider two predictors with losses $\ell_{f_0}(A)=0,\ell_{f_0}(B)=4$ and $\ell_{f_1}(A)=\ell_{f_1}(B)=1$. Set the penalties to $1/2$ for $f_0$ and $0$ for $f_1$.

The empirical criteria are $0+1/2=1/2$ for $f_0$ and $1+0=1$ for $f_1$, so $\hat f=f_0$. Their population risks are $R(f_0)=(0+4)/2=2$ and $R(f_1)=1$. Hence $R(\hat f)-R(f_1)=1$.

For the difference $\ell_{f_0}-\ell_{f_1}$, the values are $-1$ at $A$ and $3$ at $B$. Its population mean is $1$, while its empirical mean for $A,A$ is $-1$. Therefore $\Delta_n(f_0,f_1)=1-(-1)=2$. The population-risk inequality gives $1\leq 0-1/2+2=3/2$. The empirical minimization is exact, but the remainder is what allows the selected predictor to have higher population risk in this sample.

Worked Example: Checking More Than One Comparator

Again let $P(A)=P(B)=1/2$, and suppose the observed sample is $B,B$. Consider predictors $u,v,w$ with losses $(\ell(A),\ell(B))$ equal to $(4,0),(1,1),(0,3)$, respectively. Assign penalties $0,1/4,1/10$, respectively.

The empirical risks are $P_n\ell_u=0$, $P_n\ell_v=1$, and $P_n\ell_w=3$. The penalized criteria are therefore $0,5/4,$ and $31/10$; the minimizer is $\hat f=u$. The population risks are $R(u)=2$, $R(v)=1$, and $R(w)=3/2$.

Compare first with $v$. The population-risk difference is $2-1=1$. The loss difference $u-v$ is $3$ at $A$ and $-1$ at $B$, so its population mean is $1$, its sample mean is $-1$, and $\Delta_n(u,v)=2$. The bound is $1\leq 1/4+2=9/4$.

Compare instead with $w$. The population-risk difference is $2-3/2=1/2$. The loss difference $u-w$ is $4$ at $A$ and $-3$ at $B$, giving population mean $1/2$ and sample mean $-3$. Thus $\Delta_n(u,w)=1/2-(-3)=7/2$, and the inequality is $1/2\leq1/10+7/2=18/5$. The same selected predictor can be compared with either candidate; each comparison has its own penalty difference and stochastic remainder.

What the Inequality Does and Does Not Say

The basic inequality is useful because it reduces analysis of a selected predictor to a comparison with a chosen candidate. A candidate with a modest penalty may be attractive as a comparator, while a predictor with a large penalty pays for that in the term $-\operatorname{pen}(\hat f)$. Which comparison is most informative depends on the class, the penalty, and the stochastic remainder. There is no universal conclusion from the penalty term alone.

A common mistake is to argue: “The fitted predictor minimizes the penalized empirical criterion, so its population risk must be no larger than that of every candidate.” The minimization only compares empirical risks plus penalties. In population form, the remainder $\Delta_n(\hat f,g)$ is still present, and it may be positive—as the second worked example demonstrates. A population-risk conclusion needs a separate argument controlling that term, under assumptions suited to the setting.

A related caution concerns the comparator. The algebraic basic inequality holds for every $g\in\mathcal F$, even if one later chooses a comparator after observing the data. But a stochastic control proved only for a fixed, data-independent $g$ cannot automatically be applied to such a data-dependent choice. Uniform control over the relevant comparisons is a separate requirement.

Key takeaway: Exact penalized empirical minimization gives an immediate empirical comparison. Adding and subtracting empirical risk yields a population comparison consisting of a penalty difference and a stochastic remainder. The inequality is a foundation for further analysis, not a substitute for controlling that remainder.

Check Your Understanding

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

State the exact minimization property that leads to the basic inequality.
For a comparator $g$, write the population-risk inequality and identify its penalty and stochastic-remainder terms.
Can the stochastic remainder be assumed nonnegative? Explain what it measures.
In the squared-error example, why is the squared error at response $2$ and prediction $2/3$ equal to $16/9$, and what is the resulting empirical risk?
Why does minimizing penalized empirical risk not, by itself, establish that the selected predictor has lower population risk than every comparator?