Stability and Optimization Dynamics

For any $L$-smooth function $f$ and any $x, y \in \mathbb{R}^d$:

$f(y) \leq f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2}\|y - x\|^2$

In particular, for a gradient step $x_{t+1} = x_t - \eta \nabla f(x_t)$ with step size $\eta \leq 1/L$:

$f(x_{t+1}) \leq f(x_t) - \frac{\eta}{2}\|\nabla f(x_t)\|^2$

Smoothness means the function cannot curve faster than a quadratic with coefficient $L/2$. A gradient step with step size $1/L$ is guaranteed to decrease the function value by at least $\|\nabla f\|^2 / (2L)$. Larger step sizes risk overshooting the quadratic upper bound.

This is the foundation of all gradient descent convergence proofs. The guaranteed per-step decrease $\eta\|\nabla f\|^2/2$ is the "currency" that convergence arguments spend. Every convergence rate is derived by telescoping this decrease over $T$ steps and relating $\sum \|\nabla f(x_t)\|^2$ to the suboptimality gap.

If $f$ is not smooth (e.g., $f(x) = |x|$), the descent lemma does not apply. The gradient can be large without implying that a gradient step decreases $f$. Non-smooth optimization requires subgradient methods, which converge at the slower rate $O(1/\sqrt{T})$ instead of $O(1/T)$.

Gradient descent with step size $\eta = 1/L$ on a convex, $L$-smooth function satisfies:

$f(x_T) - f(x^*) \leq \frac{L\|x_0 - x^*\|^2}{2T}$

The convergence rate is $O(1/T)$. After $T$ steps, suboptimality is inversely proportional to the number of iterations.

Convexity ensures that gradient steps make progress toward $x^*$, not just downhill. The $O(1/T)$ rate means doubling the accuracy requires doubling the iterations. This is the "slow" rate; strong convexity accelerates it.

This establishes the baseline convergence rate for gradient descent. Any faster rate requires additional assumptions (strong convexity) or more sophisticated algorithms (Nesterov acceleration, which achieves $O(1/T^2)$).

The $O(1/T)$ rate is tight for smooth convex functions. Without strong convexity, GD cannot converge faster. For non-convex functions, the guarantee weakens to $\min_t \|\nabla f(x_t)\|^2 \leq O(1/T)$ (convergence to a stationary point, not a minimizer).

Gradient descent with step size $\eta = 1/L$ on a $\mu$-strongly convex, $L$-smooth function converges linearly:

$f(x_T) - f(x^*) \leq \left(1 - \frac{1}{\kappa}\right)^T (f(x_0) - f(x^*))$

where $\kappa = L/\mu$ is the condition number. Equivalently:

$\|x_T - x^*\|^2 \leq \left(1 - \frac{1}{\kappa}\right)^T \|x_0 - x^*\|^2$

To achieve $\epsilon$ accuracy, $T = O(\kappa \log(1/\epsilon))$ iterations suffice.

Strong convexity ensures that gradients do not vanish near the optimum: $\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f(x^*))$. Combined with the descent lemma, each step reduces the gap by a factor of $(1 - 1/\kappa)$. The condition number $\kappa$ controls the contraction rate.

Linear convergence means the number of iterations scales logarithmically with the desired accuracy. This is exponentially faster than the $O(1/T)$ rate for merely convex functions. The condition number $\kappa$ is the key quantity: ill-conditioned problems ($\kappa \gg 1$) converge slowly. This motivates preconditioning and adaptive methods like Adam.

The learning rate $1/L$ requires knowing (or estimating) $L$. Too large a step size causes divergence. The linear rate assumes exact gradients; stochastic gradients add noise that prevents convergence below the noise floor without decreasing the step size.