Applying Bounded Differences to Empirical Risk

From Replacement Sensitivity to Concentration

A sample statistic can depend on every observation without changing very much when any one observation is replaced. That limited sensitivity is enough to obtain a concentration bound, even when the statistic is not an average of independent terms. For learning problems, this gives a direct route from bounded loss to a deviation guarantee for the empirical risk of a fixed predictor.

The key is to check the effect of a replacement on the statistic itself. A bound on the range of each individual loss is not yet a bound on the whole statistic: the number of affected terms and their weights matter. Once each coordinate’s effect is bounded, McDiarmid’s inequality translates those bounds into a tail probability.

Definition: Let $Z_1,\ldots,Z_n$ be independent random variables and let $F(Z_1,\ldots,Z_n)$ be a measurable, bounded real-valued statistic. It satisfies a coordinate-wise bounded-differences condition with constants $c_1,\ldots,c_n$ if, for every $i$, changing only coordinate $i$ changes $F$ by at most $c_i$. Precisely, for all allowed input vectors $z,z'$ that agree except possibly in coordinate $i$, $$ |F(z)-F(z')|\leq c_i. $$

For example, a coordinate bound for an average is often proportional to $1/n$, because replacing one observation changes just one of its $n$ terms. The resulting concentration scale depends on the sum of the squared coordinate bounds, $\sum_{i=1}^n c_i^2$, not just on the largest $c_i$.

McDiarmid’s Inequality

The result used below is McDiarmid’s inequality. The variables must be independent; identical distributions are not required. The bounded-differences condition must hold over the possible inputs to the statistic, and the statistic must be measurable and integrable. Bounded statistics, as considered here, meet the integrability condition.

Theorem (McDiarmid’s inequality): If $Z_1,\ldots,Z_n$ are independent and $F$ satisfies the coordinate-wise bounds $c_1,\ldots,c_n$, write $S=\sum_{i=1}^n c_i^2$. When $S>0$, for every $\varepsilon>0$, $$ P\bigl(F-E[F]\geq\varepsilon\bigr)\leq \exp\left(-\frac{2\varepsilon^2}{S}\right), \qquad P\bigl(|F-E[F]|\geq\varepsilon\bigr)\leq 2\exp\left(-\frac{2\varepsilon^2}{S}\right). $$ If $S=0$, the statistic is constant over the possible inputs, so $P(|F-E[F]|\geq\varepsilon)=0$ for every $\varepsilon>0$.

The two-sided result follows by applying the one-sided inequality to $F$ and to $-F$, then using the union bound. The theorem controls deviation from the statistic’s expectation. To obtain a risk guarantee, we therefore also identify that expectation.

Fixed-Predictor Empirical Risk

Let $Z_i=(X_i,Y_i)$, $i=1,\ldots,n$, be independent and identically distributed observations, and fix a predictor $h$ before observing the sample. Let $\ell(h(X),Y)$ be its loss, assumed measurable and bounded in $[a,b]$. Define the empirical risk and population risk by

\widehat R_n(h)=\frac{1}{n}\sum_{i=1}^n \ell(h(X_i),Y_i), \qquad R(h)=E[\ell(h(X),Y)].

Because the observations have the same distribution, linearity of expectation gives $E[\widehat R_n(h)]=R(h)$. Replacing one observation changes just one loss term. Its old and new values both lie in $[a,b]$, so their difference in absolute value is at most $b-a$. After division by $n$, the coordinate bound is $(b-a)/n$.

Result: If $b>a$, then for every $\varepsilon>0$, $$ P\bigl(|\widehat R_n(h)-R(h)|\geq\varepsilon\bigr) \leq 2\exp\left(-\frac{2n\varepsilon^2}{(b-a)^2}\right). $$ If $a=b$, every loss equals $a$, so $\widehat R_n(h)=R(h)=a$ surely and the deviation probability is zero for every $\varepsilon>0$.

To verify the nondegenerate case, set $c_i=(b-a)/n$ for each $i$. Then $S=n(b-a)^2/n^2=(b-a)^2/n>0$. Substituting this into McDiarmid’s two-sided inequality gives the displayed result. In the degenerate case, the formula with denominator $(b-a)^2$ must not be used: that denominator is zero, while the statistic is simply constant.

Worked Example: A Binary Empirical Risk

Suppose $Z_1,\ldots,Z_{80}$ are independent and identically distributed, and a fixed classifier has zero-one loss $L_i=\ell(h(X_i),Y_i)\in\{0,1\}$. Suppose $P(L_i=1)=0.2$. Bound the probability that its empirical risk differs from its population risk by at least $0.15$.

The population risk is $R(h)=E[L_i]=0.2$, and the empirical risk is $\widehat R_{80}(h)=80^{-1}\sum_{i=1}^{80}L_i$. The loss range is $[0,1]$, so $b-a=1$. For $\varepsilon=0.15$, the exponent in the fixed-predictor bound is $$ -\frac{2(80)(0.15)^2}{1^2} =-160(0.0225) =-3.6. $$

Therefore, $$ P\bigl(|\widehat R_{80}(h)-0.2|\geq 0.15\bigr) \leq 2e^{-3.6}\approx 0.0546474. $$ Equivalently, the probability of a deviation strictly less than $0.15$ is at least $1-2e^{-3.6}\approx 0.9453526$. This lower bound is approximately $0.94535$, or approximately $0.9454$; the exact expression is the guarantee.

Weighted Empirical Risk

Unequal observation weights change the coordinate bounds. Let $Z_1,\ldots,Z_n$ be independent, let $w_i\geq 0$ with $\sum_{i=1}^n w_i=1$, and consider the weighted statistic $$ F=\sum_{i=1}^n w_i\ell_i(Z_i), $$ where each measurable loss $\ell_i$ takes values in $[a,b]$. The terms need not have the same distribution. Replacing $Z_i$ changes only the $i$th term, by at most $w_i(b-a)$. Thus $c_i=w_i(b-a)$ and $$ S=(b-a)^2\sum_{i=1}^n w_i^2. $$ When $b>a$ and at least one weight is positive, McDiarmid’s inequality gives $$ P\bigl(|F-E[F]|\geq\varepsilon\bigr) \leq 2\exp\left( -\frac{2\varepsilon^2}{(b-a)^2\sum_{i=1}^n w_i^2} \right). $$ This is a concentration result around $E[F]=\sum_i w_i E[\ell_i(Z_i)]$; the expectations need not be equal.

Worked Example: Three Unequally Weighted Losses

Let $Z_1,Z_2,Z_3$ be independent Bernoulli variables with success probabilities $0.2,0.5,0.8$, respectively, and take $\ell_i(Z_i)=Z_i$. Use weights $w_1=0.5$, $w_2=0.3$, and $w_3=0.2$. Find $E[F]$, the squared sensitivity sum, and a bound for a deviation of at least $0.5$.

The weights are nonnegative and sum to $1$. The expectation is $$ E[F]=0.5(0.2)+0.3(0.5)+0.2(0.8) =0.10+0.15+0.16 =0.41. $$ The losses lie in $[0,1]$, so the coordinate bounds are $0.5,0.3,0.2$, and $$ S=0.5^2+0.3^2+0.2^2=0.25+0.09+0.04=0.38. $$ Applying the two-sided inequality at $\varepsilon=0.5$ yields $$ P(|F-0.41|\geq 0.5) \leq 2\exp\left(-\frac{2(0.5)^2}{0.38}\right) =2e^{-25/19} \approx 0.537. $$ This bound is valid, though not especially informative. Sensitivity bounds provide a general guarantee; they do not promise a sharp one for every threshold or distribution.

Another Sample-Dependent Summary: Empirical Variance

The method applies beyond risk averages. Suppose $Z_1,\ldots,Z_n$ are independent observations in $[0,1]$, and define the empirical variance with divisor $n$ by $$ V_n=\frac{1}{n}\sum_{j=1}^n(Z_j-\overline Z)^2, \qquad \overline Z=\frac{1}{n}\sum_{j=1}^n Z_j. $$ We can bound its sensitivity without assuming identical distributions. Using $V_n=n^{-1}\sum_j Z_j^2-\overline Z^{\,2}$, compare two input vectors that differ only in coordinate $i$. The first term changes by at most $1/n$, since both possible squared values are in $[0,1]$. The two sample means differ by at most $1/n$; both means lie in $[0,1]$, so $$ |\overline z^{\,2}-\overline {z'}^{\,2}| =|\overline z-\overline {z'}|\,|\overline z+\overline {z'}| \leq \frac{1}{n}\cdot 2 =\frac{2}{n}. $$ By the triangle inequality, changing one coordinate changes $V_n$ by at most $3/n$. Hence $S\leq n(3/n)^2=9/n$, and for $\varepsilon>0$, $$ P(|V_n-E[V_n]|\geq\varepsilon) \leq 2\exp\left(-\frac{2n\varepsilon^2}{9}\right). $$

Worked Example: Concentration of the Empirical Variance

For independent observations in $[0,1]$ with $n=1000$, use the preceding sensitivity calculation to bound the probability that $V_n$ differs from its expectation by at least $0.1$.

Each coordinate has bound $c_i=3/1000$, giving $S=1000(3/1000)^2=9/1000$. Substitution gives $$ P(|V_n-E[V_n]|\geq 0.1) \leq 2\exp\left(-\frac{2(1000)(0.1)^2}{9}\right) =2e^{-20/9} \approx 0.217. $$ The estimate is a valid upper bound, not an assertion that the probability equals $0.217$. A sharper sensitivity calculation, if available, can improve the guarantee.

What the Bound Does—and Does Not—Establish

The essential calculation is coordinate-specific: identify what changes when one observation is replaced, bound that change, square each coordinate bound, and sum. Equal-sized effects lead to the familiar $1/n$ coordinate scale for an average. Unequal weights instead produce a sum of squared weights. For nonlinear statistics, the same workflow applies, but the sensitivity calculation must be done for the statistic itself.

A crucial qualification is that the predictor in the empirical-risk result is fixed independently of the sample used to evaluate it. If a predictor is selected using those same observations, replacing one observation can also change the selected predictor. The loss-range argument alone then does not bound the change in the resulting empirical risk. A valid application must establish a coordinate-wise bound for the entire sample-to-statistic mapping, including any data-dependent selection.

Common pitfall: It is incorrect to argue that bounded individual losses automatically give a useful $1/n$ bound for every statistic involving the sample. The correction is to replace one coordinate in the full statistic and calculate the resulting change. For empirical risk of a fixed predictor, only one summand changes, giving $(b-a)/n$. For a data-selected predictor or a nonlinear summary, that conclusion must be justified separately.

Check Your Understanding

For each question, identify the coordinate bounds before applying a concentration inequality.

For a fixed predictor with loss in $[2,5]$, what is the replacement bound for its empirical risk based on $n$ independent observations?
What happens to the empirical-risk deviation probability if the loss interval is degenerate, $a=b$?
For nonnegative weights summing to $1$ and losses in $[a,b]$, what is the sum of squared coordinate bounds?
Why does a fixed-predictor risk guarantee not automatically apply to a predictor selected using the same sample?
In the empirical-variance calculation, which two terms change when one observation is replaced, and what bounds control their changes?