Bernstein Risk Bounds for Fixed Predictors

Why Variance Matters for Risk Bounds

A fixed predictor is evaluated on a sample, so its empirical risk fluctuates around its true risk. A range-only bound treats every possible loss value as equally influential. Bernstein’s inequality also uses the loss variance: when most losses are concentrated near their mean, the resulting confidence radius can be smaller.

The word fixed is important. The predictor must be chosen independently of the observations used to evaluate it. A bound for one fixed predictor does not automatically hold for a predictor selected after examining the same sample.

Risk, Empirical Risk, and Loss Variance

Let \(Z_1,\ldots,Z_n\) be independent and identically distributed observations with distribution \(P\). Fix a predictor \(h\), and let \(\ell_h(Z)\) be its loss on an observation \(Z\). Suppose the loss is measurable and satisfies \(0\leq \ell_h(Z)\leq B\) almost surely for a finite constant \(B>0\).

The observations are identically distributed, so each loss has mean \(R(h)\) and variance \(\sigma_h^2\). The empirical risk is an average of independent losses. In particular, this setup gives \(E[\widehat R_n(h)]=R(h)\) and \(\operatorname{Var}(\widehat R_n(h))=\sigma_h^2/n\). The variance appearing in the bound below is the variance under the data distribution, not a variance computed from the observed sample.

The Bernstein Inequality Used Here

For clarity, write the bounded-variable inequality in the form needed for this application. If \(X_1,\ldots,X_n\) are independent, mean-zero random variables with \(|X_i|\leq b\) almost surely and \(\sum_{i=1}^n\operatorname{Var}(X_i)\leq v\), then for every \(t>0\),

This is a standard Bernstein tail bound, stated with a convenient explicit threshold. Here \(b\) controls the absolute size of each centered summand, while \(v\) controls their total variance. The linear term in \(t\) remains important for very small confidence levels; the square-root term is where a small variance improves the radius.

One-Sided Bernstein Risk Bounds

Equivalently, with probability at least \(1-\delta\), the true risk is no more than the empirical risk plus the displayed radius. To prove the direction shown, center each loss and apply Bernstein to the negative centered losses.

In detail, \(\sum_{i=1}^n(-X_i)=n(R(h)-\widehat R_n(h))\). Bernstein therefore gives

Take \(t=\log(1/\delta)\), so \(e^{-t}=\delta\), and divide the threshold by \(n\). The probability that \(R(h)-\widehat R_n(h)\) exceeds the resulting radius is at most \(\delta\), proving the theorem. \(\square\)

The same reasoning applied to \(X_i\), rather than \(-X_i\), bounds the opposite deviation \(\widehat R_n(h)-R(h)\). Applying each one-sided result with failure probability \(\delta/2\) and using the union bound gives a two-sided statement.

Indeed, each tail has probability at most \(\delta/2\) when \(t=\log(2/\delta)\). The event that either tail exceeds the common radius has probability at most \(\delta/2+\delta/2=\delta\). This proves the corollary. \(\square\)

Worked Examples

What the Variance Term Does—and Does Not—Provide

For a fixed confidence level and sample size, the square-root term is proportional to \(\sigma_h\). If the loss is nearly constant, its variance is small and this term shrinks. The range-dependent linear term does not disappear, so a small variance does not make the stated radius identically zero.

The variance in these formulas is a population quantity. The theorem is directly usable when it is known or when a valid upper bound for it is available. Replacing it with the sample variance does not follow from this proof: a random estimate requires its own justification. Also, “fixed predictor” cannot be dropped casually. If \(h\) is selected using the same observations, these pointwise calculations alone do not establish a guarantee for the selected predictor.

Common Mistake: Applying the Wrong Tail

A frequent sign error is to define \(X_i=\ell_h(Z_i)-R(h)\), observe that \(\sum_i X_i=n(\widehat R_n(h)-R(h))\), and then use an upper-tail inequality to claim a bound on \(R(h)-\widehat R_n(h)\). That inequality controls the empirical risk being too large, not the true risk being too large. The correction is to apply the upper-tail inequality to \(-X_i=R(h)-\ell_h(Z_i)\) for the desired one-sided upper bound on \(R(h)\). For a two-sided statement, control both signs and combine the tail probabilities.