Convergence Analysis

When you launch a training run, a natural question arises: How long will this take? Will the model converge in 100 iterations or 100,000? Is the algorithm making adequate progress, or is it stuck? Answering these questions requires understanding convergence theory—the mathematical framework that characterizes when, whether, and how fast gradient descent reaches a solution.

Convergence analysis isn't just academic rigor. It provides practical guidance: which algorithms to choose for different problems, how to set stopping criteria, and when to expect diminishing returns from additional training. This page develops the theory you need to reason about optimization dynamics.

Before diving into convergence rates, let's formalize the key properties of objective functions that determine convergence behavior.

Smoothness (L-Lipschitz Gradient)

A function $J$ is L-smooth if its gradient is L-Lipschitz continuous: $$| abla J(\mathbf{x}) - abla J(\mathbf{y})| \leq L |\mathbf{x} - \mathbf{y}| \quad \forall \mathbf{x}, \mathbf{y}$$

Equivalently, for twice-differentiable functions: $\lambda_{\max}(\mathbf{H}) \leq L$ (the Hessian's largest eigenvalue is bounded).

Intuition: The gradient can't change too abruptly. The surface has bounded curvature. Smaller L means flatter surface, allowing larger steps.

Convexity

A function $J$ is convex if: $$J(\lambda \mathbf{x} + (1-\lambda) \mathbf{y}) \leq \lambda J(\mathbf{x}) + (1-\lambda) J(\mathbf{y}) \quad \forall \lambda \in [0,1]$$

Equivalently: any chord lies above the function. The Hessian is positive semi-definite: $\mathbf{H} \succeq 0$.

Intuition: Bowl-shaped. Any local minimum is the global minimum. No saddle points or local maxima (except at $\infty$).

Strong Convexity (μ-strongly convex)

A function $J$ is μ-strongly convex (μ > 0) if: $$J(\mathbf{y}) \geq J(\mathbf{x}) + abla J(\mathbf{x})^T (\mathbf{y} - \mathbf{x}) + \frac{\mu}{2} |\mathbf{y} - \mathbf{x}|^2$$

Equivalently: $\lambda_{\min}(\mathbf{H}) \geq \mu$ (the Hessian's smallest eigenvalue is bounded away from zero).

Intuition: The bowl has positive curvature in every direction. The function curves upward at least quadratically. Strong convexity guarantees a unique minimum and faster convergence.

The Condition Number

For L-smooth, μ-strongly convex functions, the condition number is: $$\kappa = \frac{L}{\mu}$$

This ratio determines convergence speed:

• κ = 1: Perfectly conditioned (spherical bowl)
• κ >> 1: Ill-conditioned (elongated ellipsoid)

Let's prove the convergence rate for gradient descent on convex, L-smooth functions.

Theorem (Sublinear Convergence for Convex Functions)

Let $J$ be convex and L-smooth. Gradient descent with step size $\alpha = 1/L$ satisfies: $$J(\boldsymbol{\theta}^{(t)}) - J^* \leq \frac{L |\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^*|^2}{2t}$$

where $J^* = J(\boldsymbol{\theta}^*)$ is the minimum value.

Interpretation: The error (suboptimality) decreases as $O(1/t)$. This is sublinear convergence—to halve the error, you roughly double the iterations. After 1000 iterations, error is about 1000× smaller than initially.

Proof Sketch:

Step 1: Sufficient Decrease Lemma

For L-smooth functions with $\alpha = 1/L$: $$J(\boldsymbol{\theta}^{(t+1)}) \leq J(\boldsymbol{\theta}^{(t)}) - \frac{1}{2L} | abla J(\boldsymbol{\theta}^{(t)})|^2$$

Step 2: Convexity Bound

For convex functions: $$J(\boldsymbol{\theta}^{(t)}) - J^* \leq abla J(\boldsymbol{\theta}^{(t)})^T (\boldsymbol{\theta}^{(t)} - \boldsymbol{\theta}^*)$$

Step 3: Combine and Telescope

Using the update rule and summing over iterations: $$\sum_{k=0}^{t-1} (J(\boldsymbol{\theta}^{(k)}) - J^) \leq \frac{L}{2} |\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^|^2$$

Since $J(\boldsymbol{\theta}^{(k)})$ is non-increasing, the left side is at least $t(J(\boldsymbol{\theta}^{(t)}) - J^)$, giving: $$J(\boldsymbol{\theta}^{(t)}) - J^ \leq \frac{L |\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^*|^2}{2t}$$

QED. ∎

Strong convexity dramatically accelerates convergence from sublinear to linear (also called exponential or geometric).

Theorem (Linear Convergence for Strongly Convex Functions)

Let $J$ be μ-strongly convex and L-smooth. Gradient descent with $\alpha = 1/L$ satisfies: $$|\boldsymbol{\theta}^{(t)} - \boldsymbol{\theta}^|^2 \leq \left(1 - \frac{\mu}{L}\right)^t |\boldsymbol{\theta}^{(0)} - \boldsymbol{\theta}^|^2$$

Alternatively, in terms of function value: $$J(\boldsymbol{\theta}^{(t)}) - J^* \leq \left(1 - \frac{\mu}{L}\right)^t (J(\boldsymbol{\theta}^{(0)}) - J^*)$$

Interpretation: The error decreases by a constant factor $(1 - 1/\kappa)$ each iteration. This is linear convergence. Now, to halve the error requires only $O(\kappa \log 2)$ iterations, independent of current accuracy.

Why strong convexity helps:

Strong convexity guarantees:

1. Unique minimum: No ambiguity about the target
2. Lower bound on curvature: The function curves upward everywhere, providing "grip" for descent
3. Gradient informative about distance: Near the optimum, small gradient → small distance

The condition number κ = L/μ determines the rate:

• κ = 1: Perfect conditioning, one-step convergence
• κ = 100: Each iteration reduces error by 1%
• κ = 10,000: Each iteration reduces error by 0.01%

Proof Sketch:

The key insight is the Polyak-Łojasiewicz (PL) inequality for strongly convex functions: $$| abla J(\boldsymbol{\theta})|^2 \geq 2\mu (J(\boldsymbol{\theta}) - J^*)$$

Combined with the sufficient decrease lemma: $$J(\boldsymbol{\theta}^{(t+1)}) - J^* \leq (1 - \mu/L)(J(\boldsymbol{\theta}^{(t)}) - J^*)$$

Induction completes the proof.

Most neural network loss functions are non-convex. What can we say about convergence in this case?

For non-convex functions, we can't guarantee convergence to a global minimum—there may be many local minima and saddle points. Instead, we analyze convergence to a stationary point (where ∇J = 0).

Theorem (Convergence to Stationary Point)

Let $J$ be L-smooth (not necessarily convex). Gradient descent with $\alpha = 1/L$ satisfies: $$\min_{k=0,\ldots,t-1} | abla J(\boldsymbol{\theta}^{(k)})|^2 \leq \frac{2L(J(\boldsymbol{\theta}^{(0)}) - J_{\inf})}{t}$$

where $J_{\inf}$ is the infimum of $J$.

Interpretation: The minimum gradient norm across all iterations decreases as $O(1/t)$. After $t$ iterations, at least one iterate had gradient norm at most $O(1/\sqrt{t})$.

To find ε-stationary point (||∇J|| ≤ ε):

$$t = O\left(\frac{L(J(\boldsymbol{\theta}^{(0)}) - J_{\inf})}{\epsilon^2}\right)$$

This is $O(1/\epsilon^2)$ complexity—slower than convex optimization.

Types of stationary points:

1. Local minimum: Hessian is positive definite
2. Local maximum: Hessian is negative definite (unstable, gradient descent escapes)
3. Saddle point: Hessian has both positive and negative eigenvalues
4. Strict saddle: Saddle point with at least one negative eigenvalue

Modern insight on non-convex landscapes:

• Local minima in neural networks are often nearly as good as global minimum
• Saddle points are the real challenge in high dimensions
• Strict saddle points are unstable under gradient descent (with noise or perturbation)
• SGD noise helps escape saddle points

Let's synthesize the convergence rates across different scenarios:

Key insights:

1. Strong convexity gives logarithmic dependence on accuracy: O(log(1/ε)) vs O(1/ε). Huge practical difference.

2. Condition number κ controls everything: Factor of κ in strongly convex rate, √κ in accelerated methods.

3. Non-convex is fundamentally harder: We settle for stationary points, not global optima.

4. Acceleration (Nesterov momentum): Improves condition number dependence from O(κ) to O(√κ)—significant for ill-conditioned problems.

A natural question: can we do better than these rates with a cleverer algorithm? Information-theoretic lower bounds tell us the fundamental limits.

Theorem (Lower Bounds for First-Order Methods)

For the class of first-order methods (using only function values and gradients):

Key insight: Gradient descent is not optimal for convex optimization!

• For convex functions: GD achieves O(1/t), but O(1/t²) is possible (Nesterov)
• For strongly convex: GD contracts by (1-1/κ), but (1-1/√κ) is optimal (Nesterov)

Why does this matter practically?

For a problem with κ = 10,000:

• GD needs O(10,000) iterations for high accuracy
• Nesterov needs O(100) iterations

That's 100× fewer iterations! For large-scale problems, this translates to days vs weeks of training.

Caveat: Acceleration helps most for smooth, well-conditioned problems. For noisy gradients (SGD), non-convex landscapes (deep learning), the benefits are less clear-cut.

Convergence theory isn't just for theoreticians. Here's how to apply these insights in practice:

1. Setting Stopping Criteria

Knowing convergence rates helps set realistic stopping criteria:

• For κ = 100, expect ~100 iterations per order of magnitude of accuracy
• Plot loss on log scale: linear descent indicates linear convergence
• If progress stalls prematurely, check learning rate, data, or model

2. Regularization for Faster Convergence

Adding L2 regularization to the loss: $$J_{reg}(\boldsymbol{\theta}) = J(\boldsymbol{\theta}) + \frac{\lambda}{2} |\boldsymbol{\theta}|^2$$

makes the problem μ-strongly convex with μ ≥ λ. This:

• Guarantees linear convergence
• Improves conditioning (reduces κ)
• Prevents divergence in ill-conditioned problems

3. Diagnosing Training Dynamics