Question 2

Does it converge, and how fast?

From the prescribed initialization and update rule, does the optimization error or a stationarity measure vanish, and after how many iterations, samples or oracle calls?

Symptoms

Is this your question?

Sub-cases

Which version are you facing?

Case Usually start with
Smooth convex objective, rate in function value? Descent lemma, convexity and a telescoping potential.
Strongly convex or PL objective, geometric rate? Descent lemma plus the PL or strong-convexity inequality.
Non-convex objective, only stationarity needed? Sum the per-step decreases in \(f\) to control \(\sum_t \lVert \nabla f(x_t) \rVert^2\).
Stochastic gradients? Conditional expectation, a variance decomposition, and a martingale or concentration step for high probability.
Second-order stationarity? Hessian Lipschitzness, perturbation or cubic regularization, and a saddle-escape argument.
Global convergence of a neural network? Prove a local PL or NTK Gram-matrix lower bound, and that the iterates never leave the region where it holds.
The recipe

One step, one inequality, then telescope

  1. Choose the error metric first: \(f(x_t) - f^\star\), \(\lVert x_t - x^\star \rVert^2\), \(\lVert \nabla f(x_t) \rVert^2\), a gradient mapping, or second-order stationarity.
  2. Derive a one-step recursion, usually from the descent lemma.
  3. Insert geometry (convexity, PL, strong convexity, a Gram-matrix lower bound) to turn the progress term into your error metric.
  4. Telescope or solve the recurrence.
  5. Only then substitute the step size and translate iterations into gradient, oracle or sample complexity.

Neural-network proofs usually need one more step: an invariant region. A lemma saying the NTK is well conditioned at initialization is useless unless you also show the weights move little enough for that conditioning to persist.

1.00 / L
Above 2/L the steep direction blows up.
10
How stretched the valley is.
0.00
0 is full-batch gradient descent; above 0 is SGD.
The pathcontours of \(f\), first steps marked
The ratelog scale, with the bound from the toolkit
actual \(f(x_t) - f^\star\) (mean over runs when noisy) bound \((1 - \eta\mu)^t\) plus noise floor noise floor \(L\eta\sigma^2 / (2\mu)\)
Gradient descent on \(f(x) = \tfrac12(\mu x_1^2 + L x_2^2)\), which satisfies the PL inequality with constant \(\mu\). With \(\eta \le 1/L\), the descent lemma and PL give \(\mathbb{E}[f(x_t) - f^\star] \le\) \((1 - \eta\mu)^t (f(x_0) - f^\star)\) \(+\, L\eta\sigma^2/(2\mu)\). Stretch the valley and the rate slows to \(1 - 1/\kappa\) per step; add noise and the curve stalls at the floor instead of reaching zero, and a smaller step lowers the floor but slows the start.
A complete proof

From the descent lemma to a rate, by telescoping

The claim

Gradient descent \(x_{t+1} = x_t - \tfrac{1}{L}\nabla f(x_t)\) satisfies

\[\min_{0 \le t < T} \lVert \nabla f(x_t) \rVert^2 \le \frac{2L\big(f(x_0) - f^\star\big)}{T},\]

and if \(f\) also satisfies the PL inequality with constant \(\mu\), then \(f(x_t) - f^\star \le (1 - \mu/L)^t\,\big(f(x_0) - f^\star\big)\).

Assumptions
  • \(f\) is differentiable and \(\nabla f\) is \(L\)-Lipschitz on a convex set containing every iterate (the descent lemma uses the whole segment between consecutive iterates).
  • \(f\) is bounded below: \(f^\star = \inf f > -\infty\). No convexity is needed for the first statement.
First move, and why

Apply the descent lemma to a single step. The claim is about gradient norms, and the descent lemma is exactly the inequality that converts a gradient norm into a guaranteed drop in \(f\). Once each step pays for its gradient, summing the steps pays for all of them.

Show the proof, with commentary

Step 1: one step. The descent lemma with \(y = x_t - \eta \nabla f(x_t)\) gives

\[f(x_{t+1}) \le f(x_t) - \eta\Big(1 - \frac{L\eta}{2}\Big)\lVert \nabla f(x_t) \rVert^2 = f(x_t) - \frac{1}{2L}\lVert \nabla f(x_t) \rVert^2 \quad \text{at } \eta = \tfrac{1}{L}.\]

\(\eta = 1/L\) maximizes \(\eta(1 - L\eta/2)\). At \(\eta = 2/L\) the guaranteed progress drops to zero, and beyond it the lemma promises nothing; in the demo, gradient descent diverges past \(2/L\).

Step 2: telescope. Sum Step 1 over \(t = 0, \dots, T-1\). The \(f\) terms cancel in pairs:

\[\frac{1}{2L}\sum_{t=0}^{T-1} \lVert \nabla f(x_t) \rVert^2 \le f(x_0) - f(x_T) \le f(x_0) - f^\star .\]

The lower bound \(f^\star\) is what stops the sum from growing without limit. Without it the argument says nothing.

Step 3: minimum versus average. The minimum of \(T\) numbers is at most their average:

\[\min_{t < T} \lVert \nabla f(x_t) \rVert^2 \le \frac{1}{T}\sum_{t < T} \lVert \nabla f(x_t) \rVert^2 \le \frac{2L\big(f(x_0) - f^\star\big)}{T}. \quad \blacksquare\]

The PL corollary. Instead of summing, insert \(\lVert \nabla f(x_t) \rVert^2 \ge 2\mu\big(f(x_t) - f^\star\big)\) into Step 1 and subtract \(f^\star\) from both sides:

\[f(x_{t+1}) - f^\star \le \Big(1 - \frac{\mu}{L}\Big)\big(f(x_t) - f^\star\big),\]

and unroll the recursion \(t\) times. \(\blacksquare\)

A tempting approach that fails

Concluding from a small gradient that you are near a minimizer. \(f(x) = x_1^2 + x_2^4/4 - x_2^2/2\) is bounded below and has \(\nabla f(0) = 0\) at a saddle point, while its minimizers sit at \(x_2 = \pm 1\). The telescoping argument only ever controls \(\lVert \nabla f \rVert\); turning that into \(f(x_t) - f^\star\) needs extra geometry, such as convexity or PL.

If you relax an assumption
  • Stochastic gradients (unbiased, variance at most \(\sigma^2\), \(\eta \le 1/L\)): Step 1 gains a variance term \(L\eta^2\sigma^2/2\) per step, which gives the \(2(f(x_0) - f^\star)/(\eta T) + L\eta\sigma^2\) bound in the toolkit.
  • Smoothness only on a region: you must also prove the iterates, and the segments between them, stay in it, for instance because \(f\) decreases and its sublevel set lies inside the region.
  • Non-smooth \(f\): there is no descent lemma, so \(f\) need not decrease every step; subgradient methods give slower \(\mathcal{O}(1/\sqrt{T})\) rates.
Try it yourself

Gradient descent on a quadratic

The exercise

Let \(f(x) = \tfrac12 x^\top H x\) with \(H\) symmetric and eigenvalues in \([\mu, L]\), \(\mu > 0\).

  1. Show that \(f\) satisfies the PL inequality \(\lVert \nabla f(x) \rVert^2 \ge 2\mu\,(f(x) - f^\star)\).
  2. Conclude a rate for gradient descent with step \(1/L\) from the proof above.
  3. What happens with step \(2/L\) if \(x_0\) lies along the top eigenvector?
Hint

Write \(x\) in the eigenbasis of \(H\). Gradient descent acts on each coordinate separately.

Show a solution

1. \(f^\star = 0\) and \(\nabla f(x) = Hx\). In the eigenbasis, \(\lVert Hx \rVert^2 = \sum_i \lambda_i^2 x_i^2 \ge \mu \sum_i \lambda_i x_i^2 = 2\mu f(x)\), because each \(\lambda_i \ge \mu\).

2. \(\nabla f\) is \(L\)-Lipschitz, so the PL corollary applies: \(f(x_t) \le (1 - \mu/L)^t f(x_0)\). The number of steps to reach accuracy \(\epsilon\) grows like \((L/\mu)\log(1/\epsilon)\), linear in the condition number.

3. Along an eigenvector with eigenvalue \(\lambda\), each step multiplies the coordinate by \(1 - \eta\lambda\). With \(\eta = 2/L\) and \(\lambda = L\) that factor is \(-1\): the iterate flips sign forever and \(f\) never decreases. This is the boundary the descent lemma warned about, where the guaranteed progress \(\eta(1 - L\eta/2)\) is exactly zero.

The toolkit

What each tool gives you, and what it costs

Descent lemma

\[f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \tfrac{L}{2}\lVert y - x \rVert^2 \]

If \(\nabla f\) is \(L\)-Lipschitz. For \(y = x - \eta \nabla f(x)\): \(f(y) \le f(x) - \eta(1 - L\eta/2)\lVert \nabla f(x) \rVert^2\).

Gives
Guaranteed progress in one step.
Costs
\(L\)-smoothness along the trajectory.
Wrong tool when
The objective is non-smooth; use a proximal or subgradient argument instead.

Smooth convex gradient descent

\[f(x_T) - f^\star \le \frac{L\lVert x_0 - x^\star \rVert^2}{2T}\]

For convex, \(L\)-smooth \(f\) and \(x_{t+1} = x_t - \tfrac{1}{L}\nabla f(x_t)\).

Gives
An \(\mathcal{O}(1/T)\) rate to the global optimum.
Costs
Convexity, smoothness and an existing minimizer.
Wrong tool when
Training is non-convex: stationarity is not global optimality.

Polyak–Łojasiewicz (PL) inequality

\[\tfrac12 \lVert \nabla f(x) \rVert^2 \ge \mu\big(f(x) - f^\star\big) \;\Longrightarrow\; f(x_t) - f^\star \le (1 - \mu/L)^t \big(f(x_0) - f^\star\big)\]

For \(L\)-smooth \(f\) and gradient descent with \(\eta = 1/L\).

Gives
Linear convergence in function value without convexity. PL is strictly weaker than strong convexity.
Costs
PL at every point the iterates visit.
Wrong tool when
You only have local or empirical evidence for PL but state a global theorem.

Non-convex stationarity

\[\min_{0 \le t < T} \lVert \nabla f(x_t) \rVert^2 \le \frac{2L\big(f(x_0) - f^\star\big)}{T}\]

For \(L\)-smooth \(f\) bounded below, gradient descent with \(\eta = 1/L\).

Gives
\(\mathcal{O}(\epsilon^{-2})\) iterations to reach \(\lVert \nabla f \rVert \le \epsilon\).
Costs
Smoothness and a finite lower bound.
Wrong tool when
You want to claim convergence to a global minimizer.

Stochastic descent

\[\frac{1}{T}\sum_{t < T} \mathbb{E}\lVert \nabla f(x_t) \rVert^2 \le \frac{2\big(f(x_0) - f^\star\big)}{\eta T} + L\eta\sigma^2\]

If \(\mathbb{E}[g_t \mid x_t] = \nabla f(x_t)\), \(\mathbb{E}\lVert g_t - \nabla f(x_t) \rVert^2 \le \sigma^2\) and \(\eta \le 1/L\).

Gives
The bias–variance trade-off in the step size, and the standard SGD stationarity rate.
Costs
Unbiased gradients and a variance bound.
Wrong tool when
Gradients are biased (compression, adaptive sampling) or dependent, unless that is analyzed separately.

Robbins–Siegmund lemma

\[\mathbb{E}[V_{t+1} \mid \mathcal{F}_t] \le (1 + a_t)V_t - b_t + c_t\]

For non-negative adapted \(V_t, a_t, b_t, c_t\) with \(\sum a_t < \infty\) and \(\sum c_t < \infty\) almost surely: \(V_t\) converges and \(\sum b_t < \infty\) almost surely.

Gives
Almost-sure convergence from a noisy descent recursion.
Costs
Adaptedness and the summability conditions.
Wrong tool when
A finite-time rate is your main result; this lemma is only asymptotic.
Worked examples

How published papers answer it

  1. Du, Lee, Li, Wang & Zhai, Gradient Descent Finds Global Minima of Deep Neural Networks, ICML 2019. arXiv

    Proves global convergence in an overparameterized regime by showing the relevant Gram matrix stays sufficiently positive definite during training, so the training residual contracts. Large width is the central structural assumption.

  2. Allen-Zhu, Li & Song, A Convergence Theory for Deep Learning via Over-Parameterization, ICML 2019. PMLR

    Under input normalization and separation and polynomial overparameterization, the proof controls how far the parameters drift, keeps the favorable local geometry around random initialization, and turns that geometry into descent of the training objective. A careful example of the invariant-region loop.

  3. Reddi, Hefny, Sra, Póczos & Smola, Stochastic Variance Reduction for Nonconvex Optimization, ICML 2016. arXiv

    Adapts variance reduction to non-convex finite sums and measures success by gradient norm rather than global suboptimality. The pattern (smooth descent plus a Lyapunov function that also tracks the estimator's variance) is the template for modern variance-reduced methods.

  4. Jin, Ge, Netrapalli, Kakade & Jordan, How to Escape Saddle Points Efficiently, ICML 2017. arXiv

    Perturbed gradient descent combines ordinary descent away from saddles with a local argument that a random perturbation has enough component along an escape direction. The canonical example of strengthening first-order stationarity to second-order.

Common traps

Where proofs of this kind go wrong

Resources

Where to go next

← Back to the guide

Found an error, or have a better example or a question this guide should cover? Email [email protected]. Corrections and contributions are welcome. Last updated October 5, 2026.