Strong Convexity Stability of Regularized ERM

Why Strong Convexity Controls Stability

A regularized empirical risk minimizer depends on its training sample. Replacing one observation changes one term in the empirical objective, but the fitted parameter need not change by the same amount: the objective's curvature matters. Strong convexity ensures that moving away from its minimizer incurs a definite objective cost. If each observation can perturb the objective only gradually as the parameter moves, that curvature limits how far the new minimizer can travel.

The argument has two parts. First, compare the minimizers of two objectives that differ in one observation and bound their distance. Second, use the Lipschitz property of the loss to convert that distance into a bound on the change in loss at any test observation. The resulting guarantee is finite-sample and does not require differentiable losses.

Setup and Definitions

Let $\mathcal W$ be a convex subset of a Euclidean space, and let $\ell(w;z)$ be the loss at parameter $w\in\mathcal W$ for observation $z$. For a sample $S=(z_1,\ldots,z_n)$, define the regularized empirical objective

F_S(w)=\frac{1}{n}\sum_{i=1}^n \ell(w;z_i)+\lambda r(w), \qquad \lambda>0.

Assume each loss is convex in $w$, and that $r$ is $\kappa$-strongly convex for some $\kappa>0$. We use the convention that $r$ is $\kappa$-strongly convex if, for all $u,v\in\mathcal W$ and $t\in[0,1]$,

r((1-t)u+tv) \leq (1-t)r(u)+tr(v)-\frac{\kappa}{2}t(1-t)\|u-v\|^2.

The convexity of the losses and this condition make $F_S$ $\mu$-strongly convex with $\mu=\lambda\kappa$. Assume the objective attains its minimum on $\mathcal W$. Strong convexity implies that this minimizer is unique; denote it by $A(S)$.

Definition: Two samples $S,S'$ are replace-one neighbors if they have the same size and differ in at most one observation. A deterministic learning rule $A$ has uniform loss stability $\beta$ if, for every pair of replace-one neighbors and every test observation $z$, $$ |\ell(A(S);z)-\ell(A(S');z)|\leq \beta. $$

Suppose, in addition, that the loss is $L$-Lipschitz in its parameter, uniformly over observations:

|\ell(u;z)-\ell(v;z)|\leq L\|u-v\| \quad\text{for all }u,v\in\mathcal W,\ z.

This is a condition on how the loss changes with $w$, not a bound on the numerical size of the loss. These assumptions will give a bound on how much the optimizer changes under replacement.

A Minimizer Inequality

We first record why strong convexity gives a quantitative penalty for moving away from a minimizer. This fact applies to constrained minimization on any convex domain; the minimizer need not be an interior point.

Proposition: If $F$ is $\mu$-strongly convex on a convex set $\mathcal W$, and $x$ minimizes $F$ over $\mathcal W$, then for every $y\in\mathcal W$, $$ F(y)-F(x)\geq \frac{\mu}{2}\|y-x\|^2. $$

Proof. For $t\in(0,1)$, convexity of $\mathcal W$ puts $(1-t)x+ty$ in the domain. Since $x$ minimizes $F$, strong convexity gives

F(x)\leq F((1-t)x+ty) \leq (1-t)F(x)+tF(y)-\frac{\mu}{2}t(1-t)\|y-x\|^2.

Subtract $(1-t)F(x)$ and divide by $t$. The result is $F(y)-F(x)\geq \frac{\mu}{2}(1-t)\|y-x\|^2$. Letting $t$ decrease to zero proves the claim. $\square$

Worked Examples: Checking the Assumptions

Worked Example: Logistic Loss on a Bounded Feature

For binary labels $y\in\{-1,1\}$ and scalar features $|x|\leq 1$, consider $\ell(\theta;(x,y))=\log(1+\exp(-y\theta x))$. The derivative with respect to $\theta$ is

\frac{\partial}{\partial\theta}\ell(\theta;(x,y)) =-\frac{yx}{1+\exp(y\theta x)}.

Because $0<1/(1+\exp(y\theta x))<1$ and $|yx|\leq 1$, the derivative has absolute value at most $1$. The loss is therefore $1$-Lipschitz in $\theta$. It is also convex. Use the objective $F_S(\theta)=n^{-1}\sum_i\ell(\theta;(x_i,y_i))+\frac{\lambda}{2}\theta^2$, so $\mu=\lambda$. With $n=50$ and $\lambda=0.5$, the stability bound derived below is

\beta\leq \frac{2L^2}{\mu n} =\frac{2}{0.5\cdot 50}=0.08.

This is a worst-case guarantee over neighboring samples and test observations satisfying the feature bound; it is not a claim that every replacement changes the test loss by exactly $0.08$.

Worked Example: Hinge Loss with Bounded Feature Vectors

Let $y\in\{-1,1\}$, $w,x\in\mathbb R^d$, and $\ell(w;(x,y))=\max(0,1-y\langle w,x\rangle)$. For fixed $(x,y)$, the hinge is the maximum of two affine functions of $w$, so it is convex. The inequality $|\max(0,a)-\max(0,b)|\leq |a-b|$ gives

|\ell(w;(x,y))-\ell(v;(x,y))| \leq |\langle w-v,x\rangle| \leq \|w-v\|\|x\|.

If every feature vector satisfies $\|x\|\leq 2$, we can take $L=2$. With regularizer $\lambda\|w\|^2/2$, $\lambda=2$, and $n=100$, the resulting bound is

\beta\leq \frac{2(2)^2}{2\cdot 100}=0.04.

The feature bound is essential to this uniform Lipschitz constant. Without it, this calculation does not provide a finite $L$ over all observations.

Parameter Sensitivity Under Replacement

The key comparison is between the two objective values at the two fitted parameters. The common observations and common regularizer cancel, leaving only the replaced loss terms.

Theorem: Suppose $S$ and $S'$ differ only at one coordinate, where the observations are $z$ and $z'$. Suppose both objectives are $\mu$-strongly convex, attain their minima, and differ only through the corresponding loss term, scaled by $1/n$. If both losses are $L$-Lipschitz in $w$, then $$ \|A(S)-A(S')\|\leq \frac{2L}{\mu n}. $$

Proof. Write $w=A(S)$, $w'=A(S')$, and $d=\|w-w'\|$. Apply the minimizer inequality to $F_S$ at $w$, evaluated at $w'$, and to $F_{S'}$ at $w'$, evaluated at $w$:

F_S(w')-F_S(w)\geq \frac{\mu}{2}d^2, \qquad F_{S'}(w)-F_{S'}(w')\geq \frac{\mu}{2}d^2.

Adding these inequalities and cancelling all shared terms yields

\mu d^2 \leq \frac{1}{n}\big[ \ell(w';z)-\ell(w';z') +\ell(w;z')-\ell(w;z) \big].

Regroup the bracket as $[\ell(w';z)-\ell(w;z)]+[\ell(w;z')-\ell(w';z')]$. By the $L$-Lipschitz condition, each bracket is at most $Ld$. Thus $\mu d^2\leq 2Ld/n$. If $d=0$, the result already holds; if $d>0$, dividing by $\mu d$ proves the bound. $\square$

The factor $2$ arises because replacing an observation removes one loss and adds another. Strong convexity controls the distance between the optimizers; Lipschitz continuity controls the size of each of those two changes along the line between them.

Uniform Stability of Regularized ERM

Corollary: Under the theorem's conditions, if the same $L$-Lipschitz loss is used to evaluate predictions at every test observation, regularized ERM has uniform loss stability $$ \beta\leq \frac{2L^2}{\mu n} =\frac{2L^2}{\lambda\kappa n}. $$

Derivation. For any test observation $z_0$, the Lipschitz condition and the parameter sensitivity bound imply

|\ell(A(S);z_0)-\ell(A(S');z_0)| \leq L\|A(S)-A(S')\| \leq L\frac{2L}{\mu n} =\frac{2L^2}{\mu n}.

The bound is uniform because it does not depend on which coordinate was replaced, the particular neighboring samples, or the test observation. In the common convention $r(w)=\|w\|^2/2$, the regularizer is $1$-strongly convex, so $\kappa=1$ and the bound becomes $2L^2/(\lambda n)$.

Worked Example: A Scalar Case Attaining the Bound

Let $\mathcal W=[-1,1]$, let observations be $a\in\{-1,0,1\}$, and define $\ell(\theta;a)=1+a\theta$. This loss is convex in $\theta$, is nonnegative on the specified domain, and is $1$-Lipschitz because

|\ell(\theta;a)-\ell(\theta';a)| =|a|\,|\theta-\theta'| \leq |\theta-\theta'|.

Take $n=4$, $\lambda=2$, and $r(\theta)=\theta^2/2$. For $S=(1,0,0,0)$, the objective is $1+\theta/4+\theta^2$, whose derivative is $1/4+2\theta$. Its minimizer is $\theta_S=-1/8$, which lies in $[-1,1]$. For $S'=(-1,0,0,0)$, the objective is $1-\theta/4+\theta^2$, and its derivative is $-1/4+2\theta$, giving $\theta_{S'}=1/8$. Hence

|\theta_S-\theta_{S'}|=\frac14 =\frac{2L}{\lambda n} =\frac{2}{2\cdot4}.

At test observation $a=1$, the losses are $1-1/8=7/8$ and $1+1/8=9/8$, so their difference is $1/4$. The stability bound is $2L^2/(\lambda n)=1/4$, exactly the difference in this example. Thus the bound can be attained under the stated assumptions.

Interpretation and Common Pitfalls

The rate $2L^2/(\lambda\kappa n)$ decreases as the sample grows or as the objective becomes more strongly convex. It describes sensitivity to one replacement, not the estimator's overall predictive accuracy: increasing regularization can improve this stability guarantee while also changing the fitted solution. Stability is useful because it controls how much the learned rule's loss can respond to individual sample changes; the earlier material on high-probability generalization from stability explains how stability can be used in generalization bounds.

Common mistake: applying the bound with the wrong curvature or Lipschitz constant. It is not enough that the regularizer is strongly convex if the empirical losses are nonconvex and the full objective is not strongly convex. Nor is a loss bounded in value automatically Lipschitz as a function of the parameter. The proof requires strong convexity of the full objective and a parameter-Lipschitz condition that holds uniformly over the observations in question.

Scaling also matters. With the average-loss objective $n^{-1}\sum_i\ell(w;z_i)+\lambda r(w)$, the curvature is $\lambda\kappa$, giving the stated $1/(\lambda\kappa n)$ rate. If the loss terms are summed instead of averaged, the objective's curvature and the replacement perturbation scale differently; the formula cannot be transferred unchanged without recalculating both.

Check Your Understanding

Use the assumptions and derivations above to answer the following.

For an average-loss objective with a $\kappa$-strongly convex regularizer, what is the strong convexity parameter of the full objective?
Why does replacing one observation contribute two Lipschitz terms in the parameter sensitivity proof?
If $L=3$, $\lambda=1.5$, $\kappa=2$, and $n=90$, what uniform stability bound follows?
Why does a bounded loss value alone not establish the Lipschitz condition used in the proof?
What condition ensures that the unique minimizer exists in the stated result, and what role does strong convexity play in uniqueness?