Comparing Stability and Localization on Least Squares

Why Compare Stability and Localization?

Regularized least squares offers two ways to understand estimation. Stability asks how much the fitted predictor changes when one observation is replaced; it controls the expected gap between test and training loss. Localization uses the quadratic geometry of least squares near its population target to bound excess risk. These are related perspectives, but the quantities and assumptions are not interchangeable.

We work through both bounds for ridge regression. The stability argument needs bounded loss gradients and strong convexity. The localized argument needs empirical curvature in the directions measured by the population curvature. Its result depends on the variance of a score vector, rather than on a worst-case loss-gradient bound.

Setup and Definitions

Let $Z=(X,Y)$, where $X\in\mathbb R^d$, and let $Z_1,\ldots,Z_n$ be independent observations with the same distribution as $Z$. The prediction at parameter $\theta\in\mathbb R^d$ is $X^\top\theta$, and the squared-error loss is

\ell_\theta(X,Y)=\frac12(Y-X^\top\theta)^2.

For a parameter set $\Theta$, define the ridge estimator as a minimizer of empirical squared-error loss plus a quadratic penalty:

\hat\theta \in\arg\min_{\theta\in\Theta} \left\{ \hat Q_\lambda(\theta) = \frac1n\sum_{i=1}^n\ell_\theta(X_i,Y_i) +\frac{\lambda}{2}\|\theta\|_2^2 \right\}, \qquad \lambda>0.

Write $R(\theta)=E[\ell_\theta(X,Y)]$ for prediction risk and $Q_\lambda(\theta)=R(\theta)+\lambda\|\theta\|_2^2/2$ for population penalized risk. Let $\theta_\lambda$ minimize $Q_\lambda$ over $\Theta$. In the localized result below, the minimizers are interior points of $\Theta$, so their gradients vanish. The population design covariance is $\Sigma=E[XX^\top]$, and the empirical design covariance is $\hat\Sigma=n^{-1}\sum_{i=1}^nX_iX_i^\top$.

Definition: The expected generalization gap of the estimator is $E[R(\hat\theta)-n^{-1}\sum_{i=1}^n\ell_{\hat\theta}(X_i,Y_i)]$. Its absolute value is controlled by uniform stability. The penalized excess risk is $Q_\lambda(\hat\theta)-Q_\lambda(\theta_\lambda)$; it measures distance from the population minimizer of the penalized objective.

Stability Bound for Ridge Least Squares

Assume $\Theta$ is convex and contained in the Euclidean ball of radius $A$; $\|X\|_2\le R$ and $|Y|\le B$ almost surely. The loss gradient is $\nabla_\theta\ell_\theta(X,Y)=X(X^\top\theta-Y)$, so on $\Theta$

\|\nabla_\theta\ell_\theta(X,Y)\|_2 \le \|X\|_2\bigl(|X^\top\theta|+|Y|\bigr) \le R(RA+B)=G.

The ridge objective is $\lambda$-strongly convex: the penalty contributes Hessian $\lambda I$, and the squared-error part has positive semidefinite Hessian. We use this curvature to compare minimizers on two data sets differing in one observation.

Theorem: Under these assumptions, replacing one observation changes the fitted parameter by at most $2G/(\lambda n)$. Consequently, the ridge estimator is uniformly stable for the loss, with stability parameter $\beta=2G^2/(\lambda n)$, and $ |E[R(\hat\theta)-\hat R(\hat\theta)]|\le\beta$, where $\hat R(\theta)=n^{-1}\sum_i\ell_\theta(X_i,Y_i)$.

Proof. Let $S,S'$ be samples differing only at index $i$, and let $\theta,\theta'$ be their respective minimizers. Denote their objectives by $F_S,F_{S'}$. Strong monotonicity of the gradient of the same objective $F_S$ gives

\lambda\|\theta'-\theta\|_2^2 \le \langle\nabla F_S(\theta')-\nabla F_S(\theta),\theta'-\theta\rangle.

The constrained optimality conditions give $\langle\nabla F_S(\theta),\theta'-\theta\rangle\ge0$ and $\langle\nabla F_{S'}(\theta'),\theta'-\theta\rangle\le0$. Substituting these inequalities into the preceding display yields

\lambda\|\theta'-\theta\|_2^2 \le \langle\nabla F_S(\theta')-\nabla F_{S'}(\theta'),\theta'-\theta\rangle \le \frac{2G}{n}\|\theta'-\theta\|_2.

Only the replaced observation differs in the two gradients; the penalty and all common observations cancel. If $\theta'=\theta$, the desired parameter bound is immediate. Otherwise divide by $\lambda\|\theta'-\theta\|_2$ to obtain $\|\theta'-\theta\|_2\le2G/(\lambda n)$. Since each loss is $G$-Lipschitz on $\Theta$, its value at the two fitted parameters differs by at most $2G^2/(\lambda n)$. Finally, for an independent test observation $Z_i'$ distributed as $Z_i$, exchangeability gives $E[R(\hat\theta)-\hat R(\hat\theta)]=n^{-1}\sum_i E[\ell_{\hat\theta}(Z_i')-\ell_{\hat\theta}(Z_i)]$. Replace $Z_i$ by $Z_i'$ in the fitted sample; conditioning on the other observations and using the stability bound bounds the absolute value of each expected difference by $\beta$. This proves the expected-gap claim. $\square$

Worked Example: A Numerical Stability Bound

Suppose $d=1$, $\Theta=[-1,1]$, $|X|\le1$, $|Y|\le1$, $\lambda=2$, and $n=100$. Then $A=R=B=1$, so $G=1(1\cdot1+1)=2$. The parameter-change bound is $2G/(\lambda n)=4/200=0.02$. The uniform-stability bound is $\beta=2G^2/(\lambda n)=8/200=0.04$.

Thus replacing one observation can change the fitted coefficient by no more than $0.02$, and the expected generalization gap in absolute value is at most $0.04$. These are worst-case bounds: they use the largest permitted gradient, not the typical variability of the data.

A Localized Excess-Risk Bound

Now assume $E\|X\|_2^2<\infty$, $\Sigma$ is finite, and the empirical curvature satisfies the following design condition almost surely:

\hat H=\hat\Sigma+\lambda I \succeq \rho H, \qquad H=\Sigma+\lambda I, \qquad 0<\rho\le1.

Here $M\succeq N$ means $v^\top Mv\ge v^\top Nv$ for every $v\in\mathbb R^d$. This condition says that the sample objective retains a fixed fraction of the population objective's curvature. The penalty makes both matrices positive definite.

Define the centered score at the population penalized minimizer by

\psi(Z)=\nabla_\theta\ell_{\theta_\lambda}(Z) -E[\nabla_\theta\ell_{\theta_\lambda}(Z)].

The population first-order condition is $E[\nabla_\theta\ell_{\theta_\lambda}(Z)]+\lambda\theta_\lambda=0$. Consequently, the empirical gradient at $\theta_\lambda$ is $g_n=n^{-1}\sum_i\psi(Z_i)$. The following result turns the local score fluctuation into penalized excess risk.

Theorem: If $\theta_\lambda$ and $\hat\theta$ are interior minimizers and $\hat H\succeq\rho H$ almost surely, then $$ E[Q_\lambda(\hat\theta)-Q_\lambda(\theta_\lambda)] \le \frac{1}{2\rho^2 n}E[\psi(Z)^\top H^{-1}\psi(Z)]. $$ The right-hand side is a localized score-complexity bound: it measures random fluctuations in the geometry induced by the population curvature.

Proof. The ridge objectives are quadratic, with Hessians $\hat H$ and $H$, respectively. Put $\delta=\hat\theta-\theta_\lambda$. The empirical first-order condition and the expression for its gradient at $\theta_\lambda$ give $0=g_n+\hat H\delta$, hence $\delta=-\hat H^{-1}g_n$. The exact quadratic expansion of population penalized risk is

Q_\lambda(\hat\theta)-Q_\lambda(\theta_\lambda) =\frac12\delta^\top H\delta.

Since $\hat H\succeq\rho H$, we have $H\preceq\rho^{-1}\hat H$ and $\hat H^{-1}\preceq\rho^{-1}H^{-1}$. Therefore

\delta^\top H\delta \le \rho^{-1}\delta^\top\hat H\delta =\rho^{-1}g_n^\top\hat H^{-1}g_n \le \rho^{-2}g_n^\top H^{-1}g_n.

The scores are independent, identically distributed, and centered. Expanding the quadratic form in their average, every cross term has expectation zero by independence and centering. Thus $E[g_n^\top H^{-1}g_n]=n^{-1}E[\psi(Z)^\top H^{-1}\psi(Z)]$. Combining the displays proves the result. $\square$

The score term is also a Rademacher complexity in the local curvature metric. For independent signs $\varepsilon_i$, each taking values $1$ and $-1$ with probability $1/2$, conditional on the observations,

E_\varepsilon\left\| \frac1n\sum_{i=1}^n\varepsilon_i\psi(Z_i) \right\|_{H^{-1}}^2 = \frac1{n^2}\sum_{i=1}^n\psi(Z_i)^\top H^{-1}\psi(Z_i), \qquad \|v\|_{H^{-1}}^2=v^\top H^{-1}v.

Taking expectation gives $n^{-1}E[\psi^\top H^{-1}\psi]$, precisely the complexity scale in the theorem. Unlike the stability result, this bound accounts for directions with different population curvature and for the actual variability of the score.

Worked Example: Isotropic Design and an Effective Dimension

Let $X\in\mathbb R^d$ have independent Rademacher coordinates, so $\Sigma=I$ and $\|X\|_2=\sqrt d$. Take $Y=\varepsilon$, where $\varepsilon$ is independent of $X$, has mean zero, and has variance $\sigma^2$. Set $\lambda=1$ and $\Theta=\mathbb R^d$. The population penalized minimizer is $\theta_\lambda=0$, since $E[XY]=0$. The score is $\psi(Z)=-X\varepsilon$, and $H=2I$.

For every sample, $\hat H=\hat\Sigma+I\succeq I=\tfrac12H$, so $\rho=1/2$. Also,

E[\psi^\top H^{-1}\psi] =E\left[\varepsilon^2 X^\top \frac12 I X\right] =\frac12 E[\varepsilon^2]E[\|X\|_2^2] =\frac{\sigma^2 d}{2}.

The theorem therefore gives $E[Q_1(\hat\theta)-Q_1(0)]\le (1/(2(1/2)^2n))(\sigma^2d/2)=\sigma^2d/n$. The dependence on $d$ comes from the number of noisy design directions, while the bound scales with noise variance rather than the largest possible loss gradient.

What Each Bound Says—and Does Not Say

The stability theorem bounds an expected generalization gap. It is a worst-case statement over allowed observations and parameters, and its size decreases with $n$ and increases as regularization weakens. The localized theorem bounds population penalized excess risk relative to $\theta_\lambda$. It depends on the score variance measured through $H^{-1}$, and it requires empirical curvature to be comparable to population curvature. The latter assumption is substantial; it should not be silently inferred from bounded features alone.

The two conclusions are not competing estimates of the same quantity. A small expected generalization gap does not by itself imply a small excess risk relative to a population target: training and test risks can be close even when both are far from optimal. Conversely, a small excess risk bound does not directly give the stability theorem's leave-one-out comparison. Their strengths are complementary: stability is broadly interpretable and robust to the particular distribution of the score, while localization can reveal a faster or dimension-sensitive scale under its curvature and moment conditions.

For ordinary prediction risk, a correctly specified model requires an explicit condition. If $Y=X^\top\theta_0+\varepsilon$ and $E[X\varepsilon]=0$, then for every $\theta$

R(\theta)-R(\theta_0) =\frac12(\theta-\theta_0)^\top\Sigma(\theta-\theta_0).

Indeed, expanding the squared residual gives a cross term proportional to $E[X\varepsilon]$, which is zero by assumption. A mean-zero error $E[\varepsilon]=0$ alone is not enough. Also, $\theta_\lambda$ need not equal $\theta_0$: the penalty can introduce shrinkage bias. Thus a bound relative to $\theta_\lambda$ is not automatically a bound on prediction-risk excess relative to $\theta_0$.

Worked Example: Checking the Target and the Bias

Take a scalar design $X\in\{-1,1\}$ with equal probabilities and $Y=2X+\varepsilon$, where $\varepsilon$ is independent of $X$, has mean zero, and variance $1$. Then $E[X\varepsilon]=0$, $\Sigma=E[X^2]=1$, and the ordinary least-squares target is $\theta_0=2$.

With $\lambda=1$, the population penalized objective, up to a constant not depending on $\theta$, is $Q_1(\theta)=\tfrac12(2-\theta)^2+\tfrac12\theta^2$. Its derivative is $(\theta-2)+\theta=2\theta-2$, so $\theta_\lambda=1$, not $2$. The ordinary prediction-risk excess at this penalized target is $R(1)-R(2)=\tfrac12(1-2)^2\Sigma=1/2$. This illustrates why a localized bound relative to the penalized target and a bound relative to the unpenalized prediction target must be distinguished.

Common Pitfalls

Comparing gradients of different objectives at their separate minimizers. Both gradients can be zero, so strong monotonicity cannot produce a positive lower bound on their difference. Compare gradients of the same strongly convex objective at two points, then use the two optimality conditions; the remaining gradient difference is only from the replaced observation.
Reversing the signs of the replaced losses. When comparing the two objectives, keep the order consistent: the difference is the loss change from the first fitted parameter to the second on the first replaced observation, plus the reverse change on the other observation. Bounding its absolute value avoids relying on an incorrect sign.
Calling a mean-zero test error uncorrelated with the design. The cross term vanishes when $E[X\varepsilon]=0$, for example if $E[\varepsilon\mid X]=0$. The weaker condition $E[\varepsilon]=0$ does not imply this.
Equating generalization and excess risk. A train-test gap compares two evaluations of the fitted rule; excess risk compares that rule with a specified population target. State the target and the risk being bounded.

Key takeaway: Ridge stability controls sensitivity to one-observation replacement and hence the expected generalization gap. A localized score bound controls penalized excess risk through local curvature and score variability. The bounds answer different questions, and their assumptions must be checked separately.

Check Your Understanding

Use the definitions and assumptions above to answer the following.

Why does strong monotonicity need to compare gradients of the same objective in the stability proof?
For the bounded setup, how do the parameter replacement bound and the loss stability bound depend on $G$, $\lambda$, and $n$?
What empirical design condition is used to turn the localized score fluctuation into a population excess-risk bound?
Why does centering the score make the cross terms vanish when computing $E[g_n^\top H^{-1}g_n]$?
In a correctly specified regression model, why does $E[\varepsilon]=0$ alone fail to establish the ordinary risk identity?
How can $\theta_\lambda$ differ from the least-squares target even when the regression model is correctly specified?