Convergence rates of gradient descent and line search

Before this lesson: lesson 01 (the gradient descent update and the 1D factor $1 - \eta\lambda$), lesson 02 ($L$-smoothness, strong convexity, the descent lemma, the PL inequality and $\kappa = L/\mu$), and linear algebra 06 (a symmetric matrix has an orthonormal basis of eigenvectors). Time: about 70 minutes, plus the notebook.

---

Why this matters #

Every optimizer you use is gradient descent plus something: SGD adds noise, momentum adds memory, Adam adds a per-coordinate scale. The theory of plain gradient descent answers three practical questions. How large can the learning rate be before training diverges? ($\eta < 2/\lambda_{\max}$.) How many steps are needed? (About $\kappa\log(1/\varepsilon)$ for strongly convex problems, about $1/\varepsilon$ for convex ones.) How do we choose the step without knowing $L$? (A line search. It is standard in full-batch problems such as scientific fits, scipy.optimize.minimize and L-BFGS. In stochastic deep learning, a hand-tuned schedule replaces it; see lesson 07.)

1. Predict first #

2. The picture #

Notation for the whole lesson: $x^\star$ is a minimizer, $f^\star = f(x^\star)$, and $e_k = x_k - x^\star$ is the error after $k$ steps.

One dimension (lesson 01). For $f(x) = \tfrac{\lambda}{2}x^2$, one step gives $x_{k+1} = x_k - \eta\lambda x_k = (1 - \eta\lambda)x_k$. So $x_k = (1 - \eta\lambda)^k x_0$. The error shrinks exactly when $|1 - \eta\lambda| < 1$, that is, when $0 < \eta < 2/\lambda$.

Two dimensions. Take $f(x) = \tfrac12 x^\top A x$ with a symmetric positive definite $A$. Write its eigenvalues as $\mu = \lambda_1 \le \lambda_2 = L$, with orthonormal eigenvectors $q_1$ (the flat direction) and $q_2$ (the steep direction). Write the error in this basis: $e_k = c_{1,k}\,q_1 + c_{2,k}\,q_2$. The gradient is $Ae_k = \lambda_1 c_{1,k}q_1 + \lambda_2 c_{2,k}q_2$, so one step gives

The two components do not interact. Each one is a 1D problem from lesson 01, with its own factor.

Interactive figure: loading…

One step size for all directions. The total error shrinks only as fast as the slowest component. So the factor per step is the larger of the two:

Plot both terms against $\eta$: each is a V shape. $|1 - \eta\mu|$ has its tip at $\eta = 1/\mu$, and $|1 - \eta L|$ has its tip at $\eta = 1/L$. A small $\eta$ makes the flat factor close to 1 (slow). A large $\eta$ makes the steep factor larger than 1 (divergence). The best compromise is where the two V's cross.

Interactive figure: loading…

From a factor to a number of steps. If $\|e_k\| \le \rho^k\|e_0\|$, then $\|e_k\| \le \varepsilon\|e_0\|$ as soon as $\rho^k \le \varepsilon$, that is, after

For $\rho = 0.9$ and $\varepsilon = 10^{-6}$ this is $13.8/0.105 \approx 131$ steps. For $\rho$ close to 1, $\ln(1/\rho) \approx 1 - \rho$, so the number of steps is about $\ln(1/\varepsilon)/(1 - \rho)$.

3. Definitions and main results #

Throughout this section $\mu$ and $L$ are the strong convexity and smoothness constants of lesson 02, and $\kappa = L/\mu$. For a quadratic with Hessian $A$, they are $\mu = \lambda_{\min}(A)$ and $L = \lambda_{\max}(A)$.

Linear and sublinear convergence #

A sequence of errors converges linearly with factor $\rho < 1$ if it is bounded by $C\rho^k$. On a log scale this is a straight line going down. Every digit of accuracy costs the same number of steps, $\ln 10/\ln(1/\rho)$. A sequence converges sublinearly if it goes to zero more slowly than every $C\rho^k$, for example like $C/k$. On a log scale the curve bends and flattens: with $C/k$, each new digit costs ten times more steps than the one before.

Theorem 1 (gradient descent on a quadratic) #

Let $f(x) = \tfrac12 x^\top A x - b^\top x$ with $A$ symmetric and all eigenvalues in $[\mu, L]$, $\mu > 0$. Gradient descent with a fixed step $\eta$ satisfies $\|e_k\| \le \rho(\eta)^k\|e_0\|$ with

It converges from every $x_0$ if and only if $0 < \eta < 2/\lambda_{\max}(A)$. The best fixed step is $\eta^\star = 2/(\mu + L)$, with factor $\rho^\star = (\kappa - 1)/(\kappa + 1)$. The step $1/L$ gives $\rho = 1 - 1/\kappa$.

Proof.

1. The minimizer solves $Ax^\star = b$. So $\nabla f(x_k) = Ax_k - b = A(x_k - x^\star) = Ae_k$, and $e_{k+1} = e_k - \eta A e_k = (I - \eta A)\,e_k$.
2. Write $A = Q\Lambda Q^\top$ with orthonormal eigenvectors $q_i$ and eigenvalues $\lambda_i$. The component of the error along $q_i$ is multiplied by $1 - \eta\lambda_i$ at every step. Because the $q_i$ are orthonormal, $\|e_k\|^2 = \sum_i (1 - \eta\lambda_i)^{2k} c_{i,0}^2 \le \max_i |1 - \eta\lambda_i|^{2k}\,\|e_0\|^2$. Equality holds when $e_0$ lies along the worst $q_i$.
3. $|1 - \eta\lambda|$ is a convex function of $\lambda$ (a V shape), so its maximum over $[\mu, L]$ is at an end point. This gives $\rho(\eta)$.
4. Every component goes to zero for every start exactly when $|1 - \eta\lambda_i| < 1$, that is, $0 < \eta\lambda_i < 2$, for all $i$. The strictest of these conditions is the one for $\lambda_{\max}$.
5. For $\eta \le 1/L$, $\rho = 1 - \eta\mu$, which decreases with $\eta$. For $\eta \ge 1/\mu$, $\rho = \eta L - 1$, which increases. In between, $\rho$ is the larger of the decreasing $1 - \eta\mu$ and the increasing $\eta L - 1$. It is smallest where they are equal: $1 - \eta\mu = \eta L - 1$ gives $\eta = 2/(\mu + L)$ and $\rho = (L - \mu)/(L + \mu) = (\kappa - 1)/(\kappa + 1)$.
6. For $\eta = 1/L$: $\rho = \max(1 - \mu/L,\ 0) = 1 - 1/\kappa$. $\blacksquare$

Iteration counts. For large $\kappa$, $\ln\tfrac{\kappa + 1}{\kappa - 1} \approx 2/\kappa$. So the best step needs about $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ steps, and the step $1/L$ about $\kappa\ln(1/\varepsilon)$. Both are $O(\kappa\log(1/\varepsilon))$.

$\kappa$	best step: $\lceil \ln 10^6/\ln\frac{\kappa+1}{\kappa-1} \rceil$	step $1/L$: $\lceil \ln 10^6/\ln\frac{\kappa}{\kappa-1} \rceil$
10	69	132
100	691	1,375
1,000	6,908	13,809

The function value converges twice as fast in the exponent: $f(x_k) - f^\star = \tfrac12 e_k^\top A e_k = \tfrac12\sum_i \lambda_i(1 - \eta\lambda_i)^{2k}c_{i,0}^2$, so it decays like $\rho^{2k}$.

Does the rate depend on the dimension? No. Theorem 1 uses only the two extreme eigenvalues. A quadratic with a million variables and $\kappa = 10$ needs the same 69 steps for a factor $10^6$ as a 2D one (each step costs more, of course).

Beyond quadratics. For any $L$-smooth, $\mu$-strongly convex $f$, the step $2/(\mu + L)$ still gives $\|e_k\| \le \big(\tfrac{\kappa - 1}{\kappa + 1}\big)^k\|e_0\|$ (Nesterov, Lectures on Convex Optimization, Thm 2.1.15; Bubeck, Thm 3.12). The quadratic shows that no fixed step does better on the whole class. Near a minimizer of a smooth $f$, gradient descent behaves like gradient descent on the quadratic model with $A = \nabla^2 f(x^\star)$. So local convergence needs $\eta < 2/\lambda_{\max}(\nabla^2 f(x^\star))$.

Theorem 2 (linear rate with the step $1/L$) #

Let $f$ be $L$-smooth and $\mu$-strongly convex. Gradient descent with $\eta = 1/L$ satisfies

Proof.

1. The descent lemma of lesson 02 with $y = x - \tfrac1L\nabla f(x)$ gives $f(y) \le f(x) - \tfrac1L\|\nabla f(x)\|^2 + \tfrac{L}{2}\cdot\tfrac{1}{L^2}\|\nabla f(x)\|^2$. So one step decreases $f$ by at least $\|\nabla f(x_k)\|^2/(2L)$: $\ f(x_{k+1}) \le f(x_k) - \tfrac{1}{2L}\|\nabla f(x_k)\|^2$.
2. Strong convexity implies the PL inequality (lesson 02): $\|\nabla f(x_k)\|^2 \ge 2\mu\,(f(x_k) - f^\star)$.
3. Put step 2 into step 1 and subtract $f^\star$: $f(x_{k+1}) - f^\star \le (1 - \mu/L)(f(x_k) - f^\star)$.
4. Apply step 3 $k$ times. $\blacksquare$

Since $(1 - 1/\kappa)^k \le e^{-k/\kappa}$, after $k \ge \kappa\ln\big((f(x_0) - f^\star)/\varepsilon\big)$ steps we have $f(x_k) - f^\star \le \varepsilon$. The proof uses only the descent lemma and PL. So it also holds for nonconvex functions that satisfy the PL inequality (Garrigos and Gower, Thm 3.9).

Theorem 3 (the $O(1/k)$ rate for convex functions) #

Without strong convexity ($\mu = 0$) the linear rate disappears. Look at a 2D example first.

Example. $f(x) = \tfrac12(x_1^2 + \mu x_2^2)$ with a small $\mu > 0$, so $L = 1$. Use $\eta = 1$ and $x_0 = (1, 1)$. The first coordinate is solved in one step. The second one is $(1 - \mu)^k$. So $f(x_k) = \tfrac{\mu}{2}(1 - \mu)^{2k}$ for $k \ge 1$. As $\mu \to 0$ the factor $1 - \mu$ goes to 1: no linear rate holds for all $\mu$ at once. But the gap stays small. At $k = 100$ the worst $\mu$ is about $1/201$, with gap $9.2 \times 10^{-4}$. This is below the bound of the theorem below, $L\|x_0 - x^\star\|^2/(2k) = 2/200 = 0.01$. At the same time $x_{100,2} \approx 0.61$: the iterate is still far from $x^\star = 0$. Without strong convexity, $f(x_k)$ converges like $1/k$, but $x_k$ itself can converge very slowly.

Theorem 3. Let $f$ be convex and $L$-smooth with a minimizer $x^\star$. Gradient descent with $\eta = 1/L$ satisfies

Why this is true. Each step decreases $f$ (descent lemma). Convexity says: if $f(x)$ is far above $f^\star$, then the gradient points well toward $x^\star$, so the step brings $x$ closer to $x^\star$. The squared distance to $x^\star$ can only shrink a limited total amount, $\|x_0 - x^\star\|^2$. So the sum of all gaps is bounded, and the last gap is at most the average.

Proof of Theorem 3 (5 steps)

Write $x^+ = x - \tfrac1L\nabla f(x)$ for one step from $x$, and $g = \nabla f(x)$.

1. Descent lemma (step 1 of Theorem 2): $f(x^+) \le f(x) - \tfrac{1}{2L}\|g\|^2$.
2. First-order condition of convexity (lesson 02), from $x$ toward $x^\star$: $f^\star \ge f(x) + g^\top(x^\star - x)$, so $f(x) \le f^\star + g^\top(x - x^\star)$.
3. Add the two inequalities and complete the square:

$$f(x^+) - f^\star \le g^\top(x - x^\star) - \tfrac{1}{2L}\|g\|^2 = \tfrac{L}{2}\big(\|x - x^\star\|^2 - \|x^+ - x^\star\|^2\big).$$

(Expand $\|x^+ - x^\star\|^2 = \|x - x^\star\|^2 - \tfrac2L g^\top(x - x^\star) + \tfrac{1}{L^2}\|g\|^2$ to check the equality.) 4. Apply step 3 to the steps $x_i \to x_{i+1}$ for $i = 0, \dots, k-1$ and add them. The right side telescopes (each middle term appears once with $+$ and once with $-$):

$$\sum_{i=1}^{k}\big(f(x_i) - f^\star\big) \le \tfrac{L}{2}\big(\|x_0 - x^\star\|^2 - \|x_k - x^\star\|^2\big) \le \tfrac{L}{2}\|x_0 - x^\star\|^2 .$$

5. By step 1, $f(x_i)$ never increases. So the last gap is at most the average of the $k$ gaps: $f(x_k) - f^\star \le \tfrac1k\sum_{i=1}^k\big(f(x_i) - f^\star\big) \le \tfrac{L\|x_0 - x^\star\|^2}{2k}$. $\blacksquare$

So accuracy $\varepsilon$ needs $O(L\|x_0 - x^\star\|^2/\varepsilon)$ steps. This is not the best possible. For every method that moves only along the gradients it has seen, and every $k \le (n - 1)/2$, there are $L$-smooth convex functions on $\mathbb{R}^n$ with $f(x_k) - f^\star \ge 3L\|x_0 - x^\star\|^2/\big(32(k + 1)^2\big)$ (Nesterov's lower bound; Bubeck, Thm 3.14). Accelerated methods reach this $O(1/k^2)$ rate: lesson 04.

Line search: choosing the step along a direction #

Fix a point $x$ and a descent direction $d$, that is, a direction with $\nabla f(x)^\top d < 0$ (for gradient descent, $d = -\nabla f(x)$). Look at $f$ only along the ray from $x$:

Its slope is $\varphi'(\alpha) = \nabla f(x + \alpha d)^\top d$, and $\varphi'(0) = \nabla f(x)^\top d < 0$.

A line search chooses the step length $\alpha > 0$. We use $\alpha$ for this step and keep $\eta$ for a fixed step. A good step is not too long (the value must drop enough) and not too short (the slope must have become flatter). The Armijo and Wolfe conditions make these two words precise.

Armijo condition (sufficient decrease). With a constant $0 < c_1 < 1$:

The right side is the tangent line at 0, with its slope made less steep by the factor $c_1$. Near $\alpha = 0$ the curve lies below this line (because $c_1 < 1$). Steps that are too long go above it.

Backtracking. Choose $\alpha_0 > 0$ and a shrink factor $0 < \tau < 1$ (often $\tau = 1/2$). Try $\alpha_0, \tau\alpha_0, \tau^2\alpha_0, \dots$ and accept the first trial that satisfies Armijo.

Interactive figure: loading…

On a quadratic first. Along $d = -g$ with $g = \nabla f(x)$, a quadratic gives $\varphi(\alpha) = f(x) - \alpha\,g^\top g + \tfrac{\alpha^2}{2}\,g^\top A g$. Armijo asks $-\alpha\,g^\top g + \tfrac{\alpha^2}{2}g^\top A g \le -c_1\alpha\,g^\top g$. Divide by $\alpha > 0$: it holds exactly when

where $\alpha^\star = g^\top g/g^\top A g$ is the exact line search step (the minimizer of $\varphi$). Since $g^\top A g \le L\,g^\top g$, every $\alpha \le 2(1 - c_1)/L$ passes.

Theorem 4 (backtracking stops, with a step that is not too short) #

Let $f$ be $L$-smooth, $d = -\nabla f(x) \ne 0$, $\alpha_0 > 0$, $\tau \in (0, 1)$ and $c_1 \in (0, 1)$. Backtracking stops after finitely many trials, and the accepted step satisfies

Proof.

1. Descent lemma with $y = x - \alpha\nabla f(x)$: $f(x - \alpha\nabla f) \le f(x) - \alpha(1 - L\alpha/2)\,\|\nabla f\|^2$.
2. Armijo asks $f(x - \alpha\nabla f) \le f(x) - c_1\alpha\|\nabla f\|^2$. By step 1 this holds when $1 - L\alpha/2 \ge c_1$, that is, for every $\alpha \le 2(1 - c_1)/L$.
3. The trials $\alpha_0\tau^j$ go to 0. So after finitely many trials one is below $2(1 - c_1)/L$, and the search stops there or earlier.
4. If the accepted $\alpha$ is not $\alpha_0$, the trial before it, $\alpha/\tau$, failed. By step 2 it was larger than $2(1 - c_1)/L$. So $\alpha > 2\tau(1 - c_1)/L$. Either way, $\alpha \ge \min(\alpha_0,\ 2\tau(1 - c_1)/L)$. $\blacksquare$

Consequence. Each accepted step decreases $f$ by at least $c_1\alpha_{\min}\|\nabla f\|^2$, with $\alpha_{\min} = \min(\alpha_0, 2\tau(1 - c_1)/L)$, and we never needed to know $L$. With PL this gives the factor $1 - 2\mu c_1\alpha_{\min}$ per step, a linear rate like Theorem 2. Where $f$ is flatter, the search accepts longer steps.

The Wolfe conditions #

Armijo alone accepts tiny steps: every small enough $\alpha$ passes. The curvature condition rules them out. With a second constant $c_2$:

• weak Wolfe curvature condition: $\varphi'(\alpha) \ge c_2\,\varphi'(0)$. The slope has risen from $\varphi'(0) < 0$ to at least $c_2\varphi'(0)$, so the step went far enough to flatten the descent.
• strong Wolfe curvature condition: $|\varphi'(\alpha)| \le c_2\,|\varphi'(0)|$. Also, the slope may not be large and positive: the step may not overshoot far onto the other side of the valley.

The (weak or strong) Wolfe conditions are Armijo plus one of these, with $0 < c_1 < c_2 < 1$. The order $c_1 < c_2$ guarantees that such steps exist when $f$ is smooth and bounded below along the ray (Nocedal and Wright, Lemma 3.1). Usual values (Nocedal and Wright, §3.1): $c_1 = 10^{-4}$; $c_2 = 0.9$ for Newton and quasi-Newton methods, $c_2 = 0.1$ for nonlinear conjugate gradient. scipy.optimize.line_search and PyTorch's LBFGS(line_search_fn="strong_wolfe") use $c_1 = 10^{-4}$ and $c_2 = 0.9$.

Theorem 5 (the curvature condition gives $y^\top s > 0$) #

Let $d_k$ be a descent direction at $x_k$ and $x_{k+1} = x_k + \alpha_k d_k$ with $\alpha_k > 0$ satisfying the weak curvature condition with $c_2 < 1$. Then $s_k = x_{k+1} - x_k$ and $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$ satisfy $y_k^\top s_k > 0$.

Proof.

1. $s_k = \alpha_k d_k$, so $y_k^\top s_k = \alpha_k\big(\nabla f(x_{k+1})^\top d_k - \nabla f(x_k)^\top d_k\big)$.
2. The curvature condition says $\nabla f(x_{k+1})^\top d_k \ge c_2\,\nabla f(x_k)^\top d_k$.
3. So $y_k^\top s_k \ge \alpha_k(c_2 - 1)\,\nabla f(x_k)^\top d_k > 0$, because $c_2 - 1 < 0$ and $\nabla f(x_k)^\top d_k < 0$. $\blacksquare$

Why quasi-Newton methods need it. BFGS (lesson 10) builds a matrix $B_{k+1} \approx \nabla^2 f$ that satisfies the secant equation $B_{k+1}s_k = y_k$. If $B_{k+1}$ is positive definite, then $s_k^\top y_k = s_k^\top B_{k+1}s_k > 0$. So positive curvature along the step is necessary, and the BFGS update keeps its matrix positive definite exactly when $y^\top s > 0$. Then the next direction $-B_{k+1}^{-1}\nabla f$ is a descent direction. For strictly convex $f$, $y^\top s > 0$ holds for every step. For nonconvex $f$, Armijo alone does not guarantee it; the curvature condition does.

Fixed step against backtracking on Rosenbrock #

The Rosenbrock function $f(x, y) = (1 - x)^2 + 100(y - x^2)^2$ has its minimizer at $(1, 1)$, at the end of a long, curved, narrow valley. At the minimizer the Hessian eigenvalues are about 1001.6 and 0.399 ($\kappa \approx 2508$). So a fixed step must be below $2/1001.6 \approx 0.0019968$ to converge to $(1, 1)$.

Interactive figure: loading…

From $(-1.2, 1)$, counting steps until $f(x_k) \le 10^{-10}$ (checked in the notebook):

Method	Steps	Function evaluations
fixed $\eta = 0.001$	26,593	(none needed)
fixed $\eta = 0.0019$	13,966	(none needed)
fixed $\eta = 0.0021$	does not converge
backtracking, $\alpha_0 = 1$, $\tau = 0.5$, $c_1 = 10^{-4}$	10,616	105,522
backtracking, $\alpha_0 = 2 \times$ last step	11,966	23,940

Backtracking found a step close to the best fixed step without knowing $L$: most accepted steps are $2^{-9} \approx 0.00195$. But it does not remove the ill-conditioning. It still needs about ten thousand steps, because the problem has $\kappa \approx 2508$. Starting each search from the last step (warm start) cuts the cost from about 10 to about 2 function evaluations per step.

Answers to section 1. (1) About 350. Here $\kappa = 50$, the best factor is $49/51 \approx 0.961$, and $\ln(10^6)/\ln(51/49) \approx 345.3$, so 346 steps. The step $1/L$ needs 684 by the same formula. (2) It fails. With $\eta = 2.1/L$ the factor on $x_2$ is $|1 - 2.1| = 1.1$, so that error grows like $1.1^k$. There is a hard wall at $2/L$, not a gradual slowdown.

4. Worked example #

$f(x) = \tfrac12 x^\top A x$ with $A = \begin{pmatrix} 5 & 3 \\ 3 & 5 \end{pmatrix}$, so $x^\star = 0$ and $f^\star = 0$. The eigenvalues are $\mu = 2$ with $q_1 = (1, -1)/\sqrt2$ and $L = 8$ with $q_2 = (1, 1)/\sqrt2$. So $\kappa = 4$.

(a) Three step sizes. Steps to shrink $\|e_k\|$ by $10^6$: $\lceil\ln(10^6)/\ln(1/\rho)\rceil$.

Step $\eta$	factor on $q_1$: $\lvert 1 - 2\eta\rvert$	factor on $q_2$: $\lvert 1 - 8\eta\rvert$	$\rho$	steps
$1/L = 0.125$	0.75	0	0.75	$\lceil 48.02\rceil = 49$
$2/(\mu + L) = 0.2$	0.6	0.6	$0.6 = (\kappa - 1)/(\kappa + 1)$	$\lceil 27.05\rceil = 28$
$0.26 > 2/L = 0.25$	0.48	1.08	1.08	diverges

(b) Iterates with $\eta = 0.2$ from $x_0 = (1, 0)$. $\nabla f(x_0) = Ax_0 = (5, 3)$, so $x_1 = (1, 0) - 0.2\,(5, 3) = (0, -0.6)$. Then $\nabla f(x_1) = (-1.8, -3)$ and $x_2 = (0, -0.6) - 0.2\,(-1.8, -3) = (0.36, 0)$. In the same way $x_3 = (0, -0.216)$. Why so regular? Since $x_0 = (q_1 + q_2)/\sqrt2$, we get $x_k = 0.6^k\big(q_1 + (-1)^k q_2\big)/\sqrt2$: the norm shrinks by exactly 0.6 per step, and the $q_2$ component flips sign at every step.

(c) Theorem 2 with $\eta = 1/L$. $f(x_0) = \tfrac12 \cdot 5 = 2.5$. After one step only the $q_1$ component is left, and $f(x_k) = 0.5 \cdot 0.5625^k$ for $k \ge 1$: 0.281, 0.158, 0.089, … The bound $2.5 \cdot 0.75^k$ gives 1.875, 1.406, 1.055, … It holds, but it is loose: on a quadratic the gap decays like $\rho^2 = 0.5625$ per step, while the general bound has $1 - \mu/L = 0.75$.

(d) Backtracking from $x_0 = (1, 0)$ with $\alpha_0 = 1$, $\tau = 0.5$, $c_1 = 10^{-4}$. Here $g = (5, 3)$, $g^\top g = 34$ and $g^\top A g = 260$. So $\varphi(\alpha) = 2.5 - 34\alpha + 130\alpha^2$, and the Armijo line is $2.5 - 10^{-4}\cdot 34\,\alpha = 2.5 - 0.0034\,\alpha$.

$\alpha$	$\varphi(\alpha)$	Armijo line	accepted?	$\varphi'(\alpha) = -34 + 260\alpha$
1	98.5	2.4966	no	226
0.5	18	2.4983	no	96
0.25	2.125	2.49915	yes (first pass)	31
0.125	0.28125	2.49958	(would pass too)	−1.5

Backtracking accepts $\alpha = 0.25 = 2/L$. This is allowed: Armijo holds for every $\alpha \le 2(1 - c_1)\alpha^\star \approx 0.2615$, where $\alpha^\star = 34/260 \approx 0.1308$ is the exact step. Theorem 4 guarantees only $\alpha \ge \min(1,\ 2 \cdot 0.5 \cdot 0.9999/8) \approx 0.125$. One step of length $2/L$ is fine; the limit $2/L$ is about a fixed step repeated forever.

(e) Wolfe at $\alpha = 0.25$ with $c_2 = 0.9$ and $\varphi'(0) = -34$. Weak: $31 \ge 0.9\cdot(-34) = -30.6$ holds. Strong: $|31| \le 0.9 \cdot 34 = 30.6$ fails, just barely: the step overshoots the minimum of $\varphi$ onto a steep upward slope. At $\alpha = 0.125$, $|-1.5| \le 30.6$, so strong Wolfe holds there. scipy.optimize.line_search (strong Wolfe) returns $\alpha = 0.1308 = \alpha^\star$ here.

(f) The curvature pair of the step 0.25. $s = x_1 - x_0 = -0.25\,(5, 3) = (-1.25, -0.75)$, $y = As = (-8.5, -7.5)$, and $y^\top s = 10.625 + 5.625 = 16.25 > 0$. On a strictly convex quadratic, $y^\top s = s^\top A s > 0$ for every step. The curvature condition matters for nonconvex $f$.

5. In code #

Closed forms and SciPy check the worked example. The notebook has these cells and the exercises.

import numpy as np
from scipy.optimize import line_search

A = np.array([[5.0, 3.0], [3.0, 5.0]])
mu, L = np.linalg.eigvalsh(A)                          # 2.0 8.0
for eta in (1 / L, 2 / (mu + L), 0.26):
    T = np.eye(2) - eta * A                            # e_{k+1} = T e_k
    rho = max(abs(np.linalg.eigvals(T)))               # spectral radius of T
    k = int(np.ceil(np.log(1e6) / np.log(1 / rho))) if rho < 1 else None
    print(eta, round(rho, 4), k)                       # 0.125 0.75 49 | 0.2 0.6 28 | 0.26 1.08 None

x0 = np.array([1.0, 0.0])
T = np.eye(2) - 0.2 * A
print([np.linalg.matrix_power(T, k) @ x0 for k in (1, 2, 3)])   # (0, -0.6), (0.36, 0), (0, -0.216)

f = lambda x: 0.5 * x @ A @ x
grad = lambda x: A @ x
g = grad(x0)
phi = lambda a: f(x0 - a * g)                          # f along d = -g
dphi = lambda a: -grad(x0 - a * g) @ g                 # its slope
for a in (1, 0.5, 0.25, 0.125):                        # the backtracking table
    print(a, phi(a), phi(a) <= f(x0) - 1e-4 * a * (g @ g), dphi(a))
# 1 98.5 False 226 | 0.5 18.0 False 96 | 0.25 2.125 True 31 | 0.125 0.28125 True -1.5
alpha = line_search(f, grad, x0, -g, c1=1e-4, c2=0.9)[0]
print(alpha, g @ g / (g @ A @ g))                      # 0.13077 0.13077: the exact step

The $O(1/k)$ example of section 3, from the closed form:

import numpy as np

k = 100                                        # f = (x1^2 + mu x2^2)/2, L = 1, step 1, x0 = (1, 1)
mus = np.logspace(-6, 0, 200_001)
gap = 0.5 * mus * (1 - mus) ** (2 * k)         # f(x_k) - f*, closed form
i = gap.argmax()
print(mus[i], gap[i], 2 / (2 * k))             # 0.004975 (about 1/201)  0.000917  0.01 (bound)
print((1 - mus[i]) ** k)                       # 0.607: x_k is still far from x* = 0

6. Where it shows up #

• Learning rates in deep learning. $\eta < 2/\lambda_{\max}$ is why a learning rate that is too large makes the loss explode within a few steps. In full-batch training of neural networks, the largest Hessian eigenvalue (the sharpness) rises until it hovers near $2/\eta$: the edge of stability (Cohen et al. 2021; lesson 11).
• Preconditioning beats tuning. Making $\kappa$ ten times smaller saves about a factor 10 in steps, however well the step is tuned. This is the reason for feature scaling (lesson 02), Adam (lesson 06) and matrix preconditioners (lesson 12).
• Full-batch problems in science. With exact gradients (inverse problems, PDE-constrained fits, the L-BFGS phase after Adam in physics-informed neural networks), quasi-Newton methods with a Wolfe line search are the default: scipy.optimize.minimize(method="L-BFGS-B") or torch.optim.LBFGS(line_search_fn="strong_wolfe"). There is no learning rate to tune. For a discretized 1D Laplacian on $N$ grid points, $\kappa$ grows like $N^2$, so plain gradient descent needs $O(N^2)$ steps.
• Why not in stochastic deep learning? Armijo compares function values. With minibatch noise these values are noisy, and each trial costs a forward pass. Stochastic line searches exist for models that interpolate the data (Vaswani et al., NeurIPS 2019), but learning-rate schedules are the standard.

7. Common mistakes #

• "$1/L$ is the best step." It maximizes the guaranteed decrease of the descent lemma. On quadratics $2/(\mu + L)$ is better, and every $\eta < 2/L$ converges.
• Mixing the two rates. On a quadratic, $\|x_k - x^\star\|$ decays like $\rho^k$ and $f(x_k) - f^\star$ like $\rho^{2k}$. And $\rho = (\kappa - 1)/(\kappa + 1) \approx 1 - 2/\kappa$ means about $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ steps, not $\ln(1/\varepsilon)$.
• Reading the $O(1/k)$ bound as convergence of $x_k$. It bounds $f(x_k) - f^\star$ only. The iterate can still be far from $x^\star$.
• Choosing the step from the flat direction. $\eta = 1/\mu$ solves the flat direction and blows up the steep one. The steep direction sets the limit.
• A large $c_1$. It rejects good steps; use $c_1 = 10^{-4}$. Newton-type methods also need $c_1 < 1/2$, so that the full step $\alpha = 1$ is accepted near the minimizer.
• Weak Wolfe for nonlinear conjugate gradient. It can accept an overshooting step (the step $\alpha = 0.25$ above). The convergence theory of nonlinear CG (Fletcher–Reeves) needs strong Wolfe with $c_2 < 1/2$. For BFGS weak Wolfe is enough, but most libraries use strong Wolfe.
• Armijo alone for BFGS on a nonconvex $f$. Then $y^\top s \le 0$ can happen, and the update loses positive definiteness.
• Floating point near the minimum. When $c_1\alpha\|\nabla f\|^2$ is below the rounding error of $f$ (about $10^{-16}|f|$), Armijo cannot see the decrease, and the search stalls.

8. Check yourself #

1. A quadratic has Hessian eigenvalues 0.5, 2 and 10. Give the stability limit, the best fixed step and its factor, the factor of the step $1/L$, and the steps to reduce $\|e_k\|$ by $10^6$ with each.
   Answer

   Stability: $\eta < 2/10 = 0.2$. Best step: $2/10.5 \approx 0.190$, $\rho = 19/21 \approx 0.905$, $\lceil 138.04\rceil = 139$ steps. Step $1/L = 0.1$: $\rho = 1 - 0.5/10 = 0.95$, $\lceil 269.3\rceil = 270$ steps. The middle eigenvalue 2 does not matter.
2. In the proof of Theorem 3, where is convexity used, and where is the monotone decrease of $f(x_i)$ used?
   Answer

   Convexity in step 2, $f(x) \le f^\star + \nabla f(x)^\top(x - x^\star)$. It turns the gap into a difference of squared distances, which telescopes. The monotone decrease in step 5, to bound the last gap by the average of all gaps.
3. $f$ is convex and $L$-smooth with $L = 4$ and $\|x_0 - x^\star\| = 5$. How many steps with $\eta = 1/L$ guarantee $f(x_k) - f^\star \le 10^{-3}$?
   Answer

   $L\|x_0 - x^\star\|^2/(2k) \le 10^{-3}$ gives $k \ge 4 \cdot 25/(2 \cdot 10^{-3}) = 50{,}000$ steps.
4. For $L = 8$, $\alpha_0 = 1$, $\tau = 0.5$, $c_1 = 10^{-4}$: which step does backtracking guarantee along $-\nabla f$? Can it accept a step larger than $2/L$?
   Answer

   $\alpha \ge \min(1,\ 2 \cdot 0.5 \cdot 0.9999/8) \approx 0.125$. Yes: on a quadratic Armijo accepts every $\alpha \le 2(1 - c_1)\,g^\top g/g^\top A g$. This is larger than $2/L$ when $g$ lies mostly in flat directions. The limit $2/L$ is about a fixed step repeated forever, not about one step.
5. Why does BFGS need $y^\top s > 0$, and which line-search condition gives it?
   Answer

   The secant equation $Bs = y$ with $B \succ 0$ forces $s^\top y = s^\top B s > 0$, and the BFGS update keeps $B$ positive definite exactly when $y^\top s > 0$. The (weak or strong) Wolfe curvature condition gives $y^\top s \ge \alpha(c_2 - 1)\nabla f(x)^\top d > 0$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Convergence factor of gradient descent with step $\eta$ on a quadratic with eigenvalues in $[\mu, L]$?

   Show answer

2. For which fixed steps does gradient descent converge on a quadratic, from every start?

   Show answer

3. Best fixed step on a quadratic, and its factor?

   Show answer

4. About how many gradient descent steps does $\kappa = 100$ need for a factor $10^6$, with the best step?

   Show answer

5. Rate of gradient descent with step $1/L$ on an $L$-smooth, $\mu$-strongly convex $f$?

   Show answer

6. Rate of gradient descent with step $1/L$ on an $L$-smooth convex $f$?

   Show answer

7. State the Armijo condition.

   Show answer

8. State the weak and the strong Wolfe curvature conditions.

   Show answer

9. Usual line-search constants for quasi-Newton methods?

   Show answer

10. Why do quasi-Newton methods need the curvature condition?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Which learning rate makes gradient descent diverge on a quadratic?" — $\eta > 2/\lambda_{\max}$. At exactly $2/\lambda_{\max}$ the steepest component bounces forever without shrinking.
• "What is the convergence rate of gradient descent?" — Convex and $L$-smooth: $O(1/k)$ in $f$. Strongly convex: linear, $(1 - \mu/L)^k$, so $O(\kappa\log(1/\varepsilon))$ steps. Best fixed step on a quadratic: $2/(\mu + L)$, factor $(\kappa - 1)/(\kappa + 1)$.
• "$\kappa = 10^4$: how many steps for six digits?" — About $\tfrac{\kappa}{2}\ln 10^6 \approx 69{,}000$ with the best step, and $\kappa\ln 10^6 \approx 138{,}000$ with $1/L$.
• "What are the Wolfe conditions, and why does L-BFGS need them?" — Sufficient decrease plus curvature. The curvature condition gives $y^\top s > 0$, which keeps the BFGS matrix positive definite.
• "Why don't we use line searches to train neural networks?" — Minibatch losses are noisy and each trial costs a forward pass; schedules are cheaper and work well.

10. Practice #

The notebook for this lesson runs in Colab. It has four exercises, each with a check cell and a folded solution:

1. Run gradient descent on quadratics with $\kappa = 4, 10, 50$ and compare the measured factor per step with $(\kappa - 1)/(\kappa + 1)$.
2. Check the $O(1/k)$ bound on a convex least-squares problem that is not strongly convex (a rank-deficient design matrix).
3. Implement Armijo backtracking, reproduce the table of the worked example, and run it on Rosenbrock.
4. Write a Wolfe check (weak and strong) and test the step that scipy.optimize.line_search returns.

11. Watch and read #

22. Gradient Descent: Downhill to a MinimumMIT OpenCourseWare · Gilbert Strang, 18.065 (2018) · 53 min

Strang runs gradient descent with exact line search on $f = \tfrac12(x^2 + by^2)$ and finds the factor $(1 - b)/(1 + b)$ per step, the same factor as the best fixed step of Theorem 1.

Lecture 5: Gradient descentRyan Tibshirani · CMU 10-725 Convex Optimization · 80 min

Watch for backtracking line search and the convergence proofs for convex and strongly convex functions.

The Armijo and Wolfe conditions (DS4DS 3.07)Data Science for Dynamical Systems (DS4DS) · 17 min

The two conditions explained on the 1D function $\varphi(\alpha)$, as in the Armijo figure above.

• Lieven Vandenberghe, ECE236C, lecture "Gradient method" (slides): the $O(1/k)$ proof, backtracking, the strongly convex case and the lower bound.
• Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, free: §3.2 (Thm 3.3, the $O(1/k)$ rate) and §3.4 (Thm 3.10 and 3.12, the strongly convex case).
• Boyd and Vandenberghe, Convex Optimization, free PDF: §9.2–9.3 (backtracking line search and gradient descent on $\tfrac12(x_1^2 + \gamma x_2^2)$).
• Wolfe conditions (Wikipedia), with the constants of Nocedal and Wright, Numerical Optimization, §3.1.
• Garrigos and Gower, Handbook of Convergence Theorems for (Stochastic) Gradient Methods: §3 (gradient descent under smoothness, convexity and PL).
• SciPy, scipy.optimize.line_search (strong Wolfe, $c_1 = 10^{-4}$, $c_2 = 0.9$).