Smooth Losses and Stability of Gradient Descent

Why Gradient Descent Can Be Stable

A training algorithm can react to a small data change in two ways: the changed example alters the empirical objective, and subsequent optimization steps may magnify or control that alteration. For full-batch gradient descent, convexity and smoothness give a precise control mechanism. When the step size is suitably restricted, each update on a fixed empirical objective does not increase the distance between two starting points. Replacing one example then contributes a bounded perturbation at every iteration.

The resulting bound concerns the algorithm after a specified number of iterations. It is not a claim that gradient descent has reached an empirical minimizer. It also depends on a uniform bound on individual-example gradients: without such a bound, one replaced observation can exert an arbitrarily large force.

Definition: Let $S=(z_1,\ldots,z_n)$ be a data set and let $S'$ be obtained by replacing exactly one of its observations. They are neighbors. For a differentiable loss $\ell(w;z)$, define the empirical objective $$ F_S(w)=\frac{1}{n}\sum_{i=1}^n \ell(w;z_i). $$ Full-batch gradient descent, initialized at a data-independent $w_0$, returns $w_T(S)$ after $T$ updates: $$ w_{t+1}(S)=w_t(S)-\eta\nabla F_S(w_t(S)),\qquad t=0,\ldots,T-1. $$ The algorithm has uniform loss stability $\epsilon$ if, for every neighboring $S,S'$ and every test observation $z$, $$ |\ell(w_T(S);z)-\ell(w_T(S');z)|\leq \epsilon. $$

Assumptions and the Stability Bound

Assume the parameter space is $\mathbb{R}^d$, with its Euclidean norm and inner product. For every observation $z$, assume $w\mapsto\ell(w;z)$ is convex and differentiable, and its gradient is $\beta$-Lipschitz: $$ \|\nabla\ell(u;z)-\nabla\ell(v;z)\|\leq\beta\|u-v\|. $$ Also assume there is a finite $G$ such that $\|\nabla\ell(w;z)\|\leq G$ for every $w,z$. This last condition implies that each loss is $G$-Lipschitz in its parameter. The same assumptions imply that $F_S$ is convex and $\beta$-smooth.

Theorem: Under these assumptions, run full-batch gradient descent on neighboring data sets $S,S'$ from the same initialization, using a constant step size $0\leq\eta\leq 2/\beta$. For every $t\leq T$, $$ \|w_t(S)-w_t(S')\|\leq \frac{2\eta Gt}{n}. $$ Consequently, the output is uniformly stable with $$ |\ell(w_T(S);z)-\ell(w_T(S');z)| \leq \frac{2\eta G^2T}{n} $$ for every test observation $z$. More generally, if a prediction $q_w(x)$ is $A$-Lipschitz in $w$, then $$ |q_{w_T(S)}(x)-q_{w_T(S')}(x)| \leq \frac{2A\eta GT}{n}. $$

The step-size condition is used to prevent a gradient update on one fixed objective from increasing distances. The gradient bound is used for the effect of the replaced observation and, for the loss-stability conclusion, for how much the test loss can change when its parameter changes.

Why a Convex Smooth Gradient Step Is Nonexpansive

The key fact is a consequence of convexity and smoothness. A differentiable function $f$ is $\beta$-smooth when its gradient is $\beta$-Lipschitz. For such a function, integrating the gradient along the line segment from $v$ to $u$ gives the descent inequality $$ f(u)\leq f(v)+\langle\nabla f(v),u-v\rangle+\frac{\beta}{2}\|u-v\|^2. $$ Indeed, the difference between the left side and the first two terms on the right is the integral, for $s$ from 0 to 1, of $\langle\nabla f(v+s(u-v))-\nabla f(v),u-v\rangle$. Its absolute value is at most $\int_0^1 \beta s\|u-v\|^2\,ds$.

Lemma: If $f$ is convex and differentiable with a $\beta$-Lipschitz gradient, then $$ \langle\nabla f(u)-\nabla f(v),u-v\rangle \geq \frac{1}{\beta}\|\nabla f(u)-\nabla f(v)\|^2. $$ Thus, for $0\leq\eta\leq2/\beta$, the map $G_f(w)=w-\eta\nabla f(w)$ is nonexpansive: $$ \|G_f(u)-G_f(v)\|\leq\|u-v\|. $$

To prove the lemma, define $g(x)=f(x)-\langle\nabla f(v),x\rangle$. This function is convex and $\beta$-smooth, and $\nabla g(v)=0$, so $v$ is a global minimizer of $g$. Apply the descent inequality to $g$ at $u$, using the point $u-\nabla g(u)/\beta$. It gives $$ g\left(u-\frac{\nabla g(u)}{\beta}\right) \leq g(u)-\frac{1}{2\beta}\|\nabla g(u)\|^2. $$ Since $g(v)$ is the minimum, $g(v)\leq g(u-\nabla g(u)/\beta)$. Combining these inequalities and substituting the definition of $g$ yields $$ f(u)-f(v)-\langle\nabla f(v),u-v\rangle \geq\frac{1}{2\beta}\|\nabla f(u)-\nabla f(v)\|^2. $$ Interchanging $u$ and $v$ and adding the two inequalities proves the lemma’s inner-product bound.

For nonexpansiveness, expand the squared distance between the two updated points and apply that bound: $$ \begin{aligned} \|G_f(u)-G_f(v)\|^2 &=\|u-v\|^2-2\eta\langle u-v,\nabla f(u)-\nabla f(v)\rangle\\ &\quad+\eta^2\|\nabla f(u)-\nabla f(v)\|^2\\ &\leq \|u-v\|^2-\left(\frac{2\eta}{\beta}-\eta^2\right) \|\nabla f(u)-\nabla f(v)\|^2\\ &\leq \|u-v\|^2. \end{aligned} $$ The final inequality holds because $0\leq\eta\leq2/\beta$. Taking square roots proves nonexpansiveness. $\square$

Proof of the Stability Theorem

Write $G_S(w)=w-\eta\nabla F_S(w)$ for the update map on data set $S$, and define $G_{S'}$ likewise. At any fixed $w$, the data sets differ in one summand, so the gradient bound gives $$ \|\nabla F_S(w)-\nabla F_{S'}(w)\| =\frac{1}{n}\|\nabla\ell(w;z)-\nabla\ell(w;z')\| \leq\frac{2G}{n}, $$ where $z,z'$ are the observations exchanged. Hence $\|G_S(w)-G_{S'}(w)\|\leq2\eta G/n$.

Let $\delta_t=\|w_t(S)-w_t(S')\|$. Apply the triangle inequality, then nonexpansiveness of the update on $F_S$, and then the fixed-point perturbation bound: $$ \begin{aligned} \delta_{t+1} &=\|G_S(w_t(S))-G_{S'}(w_t(S'))\|\\ &\leq\|G_S(w_t(S))-G_S(w_t(S'))\| +\|G_S(w_t(S'))-G_{S'}(w_t(S'))\|\\ &\leq\delta_t+\frac{2\eta G}{n}. \end{aligned} $$ The common initialization gives $\delta_0=0$. Repeatedly applying the last inequality yields $\delta_t\leq2\eta Gt/n$. Since the test loss has gradient norm at most $G$, integration along the segment between the two parameters gives $$ |\ell(w_T(S);z)-\ell(w_T(S');z)| \leq G\|w_T(S)-w_T(S')\| \leq\frac{2\eta G^2T}{n}. $$ If $q_w(x)$ is $A$-Lipschitz in $w$, the same distance bound gives the stated prediction inequality. $\square$

Worked Examples

Worked Example: A Linear Loss Attains the Distance Bound

Take scalar parameters and losses $\ell(w;a)=aw$, where $a\in\{-1,0,1\}$. These losses are convex, their gradients are bounded by $G=1$, and their gradients are constant, hence $0$-Lipschitz and also $\beta$-Lipschitz for $\beta=1$. Let $n=10$, initialize at $w_0=0$, and use $\eta=0.5$, which satisfies $\eta\leq2/\beta=2$. Let $S$ contain one observation with $a=1$ and nine with $a=0$; let $S'$ replace that observation by one with $a=-1$.

The empirical gradients are constant: $\nabla F_S=1/10$ and $\nabla F_{S'}=-1/10$. After $T=4$ updates, $$ w_4(S)=-4(0.5)(0.1)=-0.2,\qquad w_4(S')=-4(0.5)(-0.1)=0.2. $$ Thus the parameter distance is $0.4$, exactly $2\eta GT/n=2(0.5)(1)(4)/10=0.4$. For the test loss $\ell(w;1)=w$, the loss difference is also $0.4$. The bound can therefore be attained; it is not only a loose consequence of the proof.

Worked Example: Two Logistic-Regression Updates

For $x=1$ and $y\in\{-1,1\}$, take $\ell(w;(x,y))=\log(1+\exp(-yw x))$. Its derivative with respect to $w$ is $-yx/(1+\exp(ywx))$, so for $|x|\leq1$ its gradient magnitude is at most $G=1$. Its second derivative is at most $x^2/4$, so the loss is convex and $\beta=1/4$-smooth. Use $n=4$, $w_0=0$, and $\eta=1$, which is at most $2/\beta=8$.

Let $S$ have two positive and two negative labels, all with $x=1$. Let $S'$ replace one positive label by a negative one, giving one positive and three negative labels. At $w=0$, a positive example has gradient $-1/2$, and a negative example has gradient $1/2$. Thus $\nabla F_S(0)=0$, whereas $\nabla F_{S'}(0)=((-1/2)+3(1/2))/4=1/4$. After one update, $w_1(S)=0$ and $w_1(S')=-1/4$.

At $w=-1/4$, the positive-example gradient is $-1/(1+\exp(-1/4))$, approximately $-0.562176$. The negative-example gradient is $1/(1+\exp(1/4))$, approximately $0.437824$. Therefore $$ \nabla F_{S'}(-1/4) =\frac{-0.562176+3(0.437824)}{4} \approx0.187824, $$ and $w_2(S')\approx-0.437824$, while $w_2(S)=0$. The theorem’s parameter-distance bound after two updates is $2(1)(1)(2)/4=1$, which is larger than the observed distance $0.437824$, as required. For a positive test example, the test-loss difference is approximately $\log(1+\exp(0.437824))-\log 2\approx0.243$, also below the loss-stability bound $2(1)(1)^2(2)/4=1$.

Worked Example: Turning Parameter Stability Into Prediction Stability

Consider logistic loss with a linear score $q_w(x)=x^\mathsf{T}w$, and suppose all feature vectors satisfy $\|x\|\leq2$. The gradient is $-yx/(1+\exp(yx^\mathsf{T}w))$, so its norm is at most $G=2$. The Hessian is a scalar between 0 and $1/4$ times $xx^\mathsf{T}$; hence the gradient is $\beta$-Lipschitz with $\beta\leq\|x\|^2/4\leq1$. Choose $\eta=0.1$, $n=50$, and $T=20$. The step-size requirement holds because $0.1\leq2$.

For neighboring samples, the parameter difference is bounded by $$ \|w_{20}(S)-w_{20}(S')\| \leq\frac{2(0.1)(2)(20)}{50}=0.16. $$ For any test feature vector with norm at most 2, Cauchy–Schwarz gives $$ |x^\mathsf{T}w_{20}(S)-x^\mathsf{T}w_{20}(S')| \leq\|x\|\|w_{20}(S)-w_{20}(S')\| \leq2(0.16)=0.32. $$ Thus the score change is at most $0.32$. Since the logistic loss is also 2-Lipschitz in $w$ for these features, its change on a test example is at most $2(0.16)=0.32$.

Interpretation and a Common Pitfall

The bound grows linearly with the number of updates and the step size, and decreases inversely with sample size. It controls the output after a fixed number of full-batch updates; it does not require an optimization-convergence claim. In the stability framework, such a uniform loss bound can be used to control generalization, but it is important to keep the algorithmic assumptions attached to the result.

Pitfall: assuming smoothness alone prevents instability. Smoothness controls how gradients change with the parameter, but it does not bound the gradient contributed by a particular observation. A single replaced example can have an arbitrarily large gradient if no uniform gradient bound is imposed.
Correction: Require $\|\nabla\ell(w;z)\|\leq G$ uniformly (or establish an appropriate bound over the parameter region visited). Then the changed empirical gradient is at most $2G/n$.
Pitfall: using the same proof for any step size. The nonexpansiveness argument requires $\eta\leq2/\beta$. If the step is larger, the coefficient $2\eta/\beta-\eta^2$ in the squared-distance calculation can be negative, so that argument no longer proves contraction or nonexpansiveness.

The central distinction is between stability of an update on a fixed objective and the perturbation caused by changing the objective. Convex smoothness and the step-size restriction control the first; bounded gradients control the second. Adding these effects over the iterations yields the parameter bound, which then translates into prediction or loss stability through a Lipschitz condition.

Check Your Understanding

Answer using the assumptions and bounds developed above.

Why does replacing one observation change the empirical gradient at a fixed parameter by at most $2G/n$?
Where exactly is the condition $\eta\leq2/\beta$ used in the nonexpansiveness proof?
If the initialization depended on the data, which step of the iterate-distance argument would need an additional term?
For prediction functions that are $A$-Lipschitz in the parameter, what prediction-difference bound follows after $T$ updates?
Which assumption in the theorem would fail to justify a uniform stability bound if individual-example gradients were unbounded?