Checking the Bernstein Condition for Squared Loss

Why Check the Loss Difference?

Fast empirical risk minimization bounds depend not only on whether losses are bounded, but also on how variable their differences are near a risk minimizer. For regression with squared loss, that variance can often be controlled by the excess prediction risk. The key is to check the comparator and the model assumptions: bounded responses alone do not guarantee the desired control.

Let $(X,Y)$ have a fixed joint distribution, and let $f$ and $g$ be measurable prediction functions. Their squared losses are $(Y-f(X))^2$ and $(Y-g(X))^2$. We study the random loss difference $D_{f,g}=(Y-f(X))^2-(Y-g(X))^2$. Its variance is the quantity used in a Bernstein condition for comparing $f$ with $g$.

Definition: The squared-loss risk of a predictor $f$ is $R(f)=E[(Y-f(X))^2]$, when this expectation is finite. Relative to a reference predictor $g$, the excess risk is $R(f)-R(g)$. A linear Bernstein condition relative to $g$ is an inequality $$ \operatorname{Var}(D_{f,g})\leq B\{R(f)-R(g)\} $$ for every predictor $f$ under consideration, with a finite constant $B$ that does not depend on $f$. The inequality is meaningful when $g$ is a risk minimizer over the comparison class, so the excess risks are nonnegative.

Algebra and an Exact Variance Formula

Write $\delta(X)=f(X)-g(X)$. Factoring a difference of squares gives

D_{f,g} =(g(X)-f(X))(2Y-f(X)-g(X)) =\delta(X)\{f(X)+g(X)-2Y\}.

This identity already shows why a bound on the response and predictions matters: it bounds the second factor. To see exactly how the response noise enters, define the conditional mean $m(X)=E[Y\mid X]$, the residual $\varepsilon=Y-m(X)$, and the conditional variance $\sigma^2(X)=\operatorname{Var}(Y\mid X)$. Assume the quantities below have finite second moments. Then $D_{f,g}=q(X)-2\delta(X)\varepsilon$, where $q(X)=\delta(X)\{f(X)+g(X)-2m(X)\}$.

Result: Under the preceding finite-moment assumptions, $$ \operatorname{Var}(D_{f,g}) =\operatorname{Var}\!\left(\delta(X)\{f(X)+g(X)-2m(X)\}\right) +4E[\delta(X)^2\sigma^2(X)]. $$ Also, $$ R(f)-R(g)=E[\delta(X)^2]+2E[\delta(X)\{g(X)-m(X)\}]. $$

Proof. Conditional on $X$, the functions $q(X)$ and $\delta(X)$ are fixed and $E[\varepsilon\mid X]=0$. Thus $E[D_{f,g}]=E[q(X)]$. In the variance of $q(X)-2\delta(X)\varepsilon$, the covariance term is zero because $E[(q(X)-E[q(X)])\delta(X)\varepsilon]=0$, by conditioning on $X$. The remaining residual term is $4E[\delta(X)^2\varepsilon^2]=4E[\delta(X)^2\sigma^2(X)]$. This proves the variance formula. For the risk difference, condition on $X$ and use $E[(Y-a)^2\mid X]=\sigma^2(X)+(m(X)-a)^2$. Subtract the expressions for $a=f(X)$ and $a=g(X)$; expanding the squares gives $\delta(X)^2+2\delta(X)\{g(X)-m(X)\}$. Taking expectations proves the second identity. $\square$

When $g=m$, the cross term in the risk difference vanishes. The excess risk is exactly $E[\delta(X)^2]$, and the variance formula simplifies to

R(f)-R(m)=E[\delta(X)^2], \qquad \operatorname{Var}(D_{f,m}) =E[\delta(X)^4]+4E[\delta(X)^2\sigma^2(X)] -\{E[\delta(X)^2]\}^2.

Worked Example: A Bernoulli Response and the Conditional Mean

Suppose $X$ is constant and $Y\sim\operatorname{Bernoulli}(1/2)$. Compare the conditional mean predictor $g=1/2$ with $f=3/4$. Here $\delta=1/4$, and both predictors and the response lie in $[0,1]$.

If $Y=1$, the loss difference is $D_{f,g}=(1-3/4)^2-(1-1/2)^2=1/16-1/4=-3/16$. If $Y=0$, it is $D_{f,g}=(0-3/4)^2-(0-1/2)^2=9/16-1/4=5/16$. Each value occurs with probability $1/2$, so $E[D_{f,g}]=(-3/16+5/16)/2=1/16$.

The variance is $\{(-3/16-1/16)^2+(5/16-1/16)^2\}/2=1/16$. The excess risk is $R(f)-R(g)=E[\delta^2]=1/16$, so the variance equals the excess risk in this example. The conditional variance is $1/4$, and the exact formula gives the same result: $4\delta^2\sigma^2=4(1/16)(1/4)=1/16$, while $\delta^4-\delta^4=0$.

When Boundedness Gives a Bernstein Bound

Suppose $|Y|\leq K$ almost surely and $|f(X)|,|g(X)|\leq K$ almost surely for all predictors being compared, where $K$ is finite. The factorization gives $|f(X)+g(X)-2Y|\leq4K$. Since variance is at most the second moment,

\operatorname{Var}(D_{f,g}) \leq E[D_{f,g}^2] \leq 16K^2E[(f(X)-g(X))^2].

Thus a linear Bernstein condition follows whenever the squared prediction distance $E[(f-g)^2]$ is controlled by excess risk. Two important cases provide this control: a realizable comparator $g=m$, and a risk minimizer in a convex class of predictors.

Theorem: Assume $|Y|\leq K$ almost surely and every predictor in a class $\mathcal F$ satisfies $|f(X)|\leq K$ almost surely. If $g=m$ is in $\mathcal F$, then, for every $f\in\mathcal F$, $$ \operatorname{Var}(D_{f,g})\leq16K^2\{R(f)-R(g)\}. $$ The same conclusion holds if $\mathcal F$ is convex, $g\in\mathcal F$ minimizes risk over $\mathcal F$, and $|g(X)|\leq K$ almost surely.

Proof. In the realizable case $g=m$, the risk identity gives $R(f)-R(g)=E[(f-g)^2]$. Combining this identity with the boundedness inequality proves the claim.

For the convex case, $m(X)$ is bounded by $K$, since it is a conditional expectation of a response bounded in absolute value by $K$. Fix $f\in\mathcal F$. Convexity ensures that $g+t(f-g)\in\mathcal F$ for $0\leq t\leq1$. Since $g$ minimizes risk, the right derivative at zero of $R(g+t(f-g))$ is nonnegative. Expanding the squared loss gives that derivative as $2E[(g(X)-m(X))(f(X)-g(X))]$. Therefore this expectation is nonnegative. The risk identity now yields $$ R(f)-R(g) =E[(f-g)^2]+2E[(g-m)(f-g)] \geq E[(f-g)^2]. $$ Finally, the boundedness inequality gives $\operatorname{Var}(D_{f,g})\leq16K^2E[(f-g)^2]\leq16K^2\{R(f)-R(g)\}$. $\square$

Worked Example: A Best Constant Predictor in a Convex Class

Let $X$ take values $0$ and $1$ with equal probability, and let $Y=X$. Consider the convex class of constant predictors $a\in[0,1]$. The risk is $R(a)=\{a^2+(1-a)^2\}/2$. Expanding gives $R(a)=a^2-a+1/2$, which is minimized at $g=1/2$.

Take $f=3/4$. Its risk is $R(f)=\{(3/4)^2+(1/4)^2\}/2=(9/16+1/16)/2=5/16$, while $R(g)=1/4=4/16$. The excess risk is $1/16$, equal to $(f-g)^2=(1/4)^2$, as expected for this constant-prediction problem.

At $Y=0$, the loss difference is $9/16-1/4=5/16$; at $Y=1$, it is $1/16-1/4=-3/16$. The two outcomes are equally likely. Their mean difference is $1/16$, and their variance is $\{(5/16-1/16)^2+(-3/16-1/16)^2\}/2=1/16$. Thus the variance again equals the excess risk. Here $m(X)=X$, so the best constant predictor is not the conditional mean; it is the convex class and its risk minimizer that provide the required distance control.

Why the Comparator Assumption Matters

Boundedness controls the size of each loss difference, but does not by itself ensure that the loss-difference variance shrinks with excess risk. For a general comparator, the risk identity contains the cross term $2E[\delta(g-m)]$. Without a condition such as $g=m$ or the convex-minimizer argument, the risk gap need not control $E[\delta^2]$.

Worked Example: Tied Predictors Break the Linear Condition

Let $X$ be constant, $Y\sim\operatorname{Bernoulli}(1/2)$, and take the two-predictor class $\mathcal F=\{0,1\}$. Set $g=0$ and $f=1$. Both risks equal $1/2$, since $R(0)=E[Y^2]=1/2$ and $R(1)=E[(1-Y)^2]=1/2$.

The loss difference is $D_{f,g}=(1-Y)^2-Y^2$. It equals $1$ when $Y=0$ and $-1$ when $Y=1$. Consequently, $E[D_{f,g}]=0$ and $\operatorname{Var}(D_{f,g})=1$, but $R(f)-R(g)=0$. No finite $B$ can make $\operatorname{Var}(D_{f,g})\leq B\{R(f)-R(g)\}$ hold for this pair. The class is nonconvex, and its tied risk minimizers are not distinguished by excess risk.

A common mistake is to argue, “The response and predictions are bounded, so squared loss satisfies a linear Bernstein condition.” The valid conclusion from boundedness is only $\operatorname{Var}(D_{f,g})\leq16K^2E[(f-g)^2]$. To replace the squared prediction distance by excess risk, one must separately establish $E[(f-g)^2]\leq C\{R(f)-R(g)\}$ for a finite constant $C$. Realizability gives $C=1$, as does the convex-class minimizer argument above. The tied-predictor example shows why omitting this step can invalidate a fast-rate argument.

The practical check is therefore to identify the reference predictor, calculate the loss difference, use boundedness to control its second moment, and then verify that the model structure makes prediction distance no larger than a constant times excess risk. This separates the probabilistic part of the calculation from the geometric or modeling condition that connects it to risk.

Key takeaway: For bounded-response squared-loss regression, boundedness controls loss-difference variance by squared prediction distance. A linear Bernstein condition follows when excess risk controls that distance, as it does for the conditional mean or a risk minimizer over a convex predictor class. Boundedness alone is not enough.

Check Your Understanding

Use the loss-difference identity and state the assumptions needed for each conclusion.

For $D_{f,g}=(Y-f(X))^2-(Y-g(X))^2$, factor the difference using $f(X)-g(X)$.
When $g=m(X)=E[Y\mid X]$, what is $R(f)-R(g)$ in terms of $f-g$?
If $|Y|,|f(X)|,|g(X)|\leq K$, derive the bound on $\operatorname{Var}(D_{f,g})$ in terms of $E[(f-g)^2]$.
Why does a convex predictor class with a risk-minimizing $g$ imply $R(f)-R(g)\geq E[(f-g)^2]$?
In the tied Bernoulli example, what are the loss-difference variance and excess risk, and why can no finite linear Bernstein constant work?

Checking the Bernstein Condition for Squared Loss

What You'll Learn