Momentum and Nesterov acceleration

Before this lesson: lesson 03 (the factor $\rho(\eta)$ of gradient descent on a quadratic and the best step $2/(\mu + L)$), and linear algebra 05 (eigenvalues of a $2 \times 2$ matrix, complex eigenvalues). For the folded part on conjugate gradients: linear algebra 14 (Krylov subspaces and CG). Time: about 75 minutes, plus the notebook.

---

Why this matters #

Every optimizer used to train large models has a momentum term: SGD with momentum=0.9, and Adam's $\beta_1 = 0.9$ (lesson 06). On an ill-conditioned problem gradient descent needs about $\kappa$ steps per digit of accuracy, and momentum about $\sqrt\kappa$. Nesterov's method is the version with a guarantee for all smooth convex functions, and no method that only uses gradients can be faster in the worst case. It comes back in FISTA for the lasso (lesson 09). Conjugate gradients push the same idea to the limit on quadratics: they solve the large sparse linear systems of PDE solvers and the inner systems of Newton-type methods.

1. Predict first #

2. The picture #

The zig-zag problem again. In a narrow valley the steep direction (curvature $L$) forces a step of about $1/L$, or gradient descent diverges. Along the flat direction (curvature $\mu$) such a step makes progress of only about $\mu/L = 1/\kappa$ of the distance per step.

Heavy ball. Polyak's heavy-ball method adds a fraction $\beta$ of the last step:

Here $\eta > 0$ is the step size and $0 \le \beta < 1$ is the momentum coefficient. With $\beta = 0$ it is gradient descent. Think of a heavy ball rolling in the valley. Across the valley the gradient flips sign from step to step, so the added parts cancel. Along the valley the gradient keeps its direction, so they add up.

The effective step. Suppose the gradient is a constant $g$. Write $\Delta_k = x_k - x_{k-1}$ for the step. Then $\Delta_{k+1} = \beta\Delta_k - \eta g$. The steps approach the fixed point $\Delta = \beta\Delta - \eta g$, that is,

For $\beta = 0.9$ the step becomes $10\eta g$: ten times the gradient-descent step.

Momentum as a filter. Unroll the step: $\Delta_{k+1} = -\eta\big(g_k + \beta g_{k-1} + \beta^2 g_{k-2} + \dots\big)$. The step is a weighted sum of all past gradients, with weights that decay like $\beta^j$. A part of the gradient that keeps its sign adds up to about $1/(1 - \beta)$ times its size. A part that flips sign at every step adds up to about $1/(1 + \beta)$ times its size. So momentum is a low-pass filter: it keeps the slow, consistent part of the gradient and damps the fast, oscillating part.

Interactive figure: loading…

One eigen-direction: a damped oscillator. Take $f(x) = \tfrac12\lambda x^2$. Then $\nabla f(x_k) = \lambda x_k$, and heavy ball becomes

This is a second-order recurrence: the new value depends on the two last values. Such a recurrence behaves like a damped spring. Look for solutions $x_k = z^k$. They must satisfy the characteristic polynomial

Its two roots $z_1, z_2$ decide everything: $x_k = a z_1^k + b z_2^k$ (or $(a + bk)z^k$ for a double root).

• Over-damped (too little momentum for this $\eta\lambda$): two real positive roots. $x_k$ creeps toward 0 without oscillating, like gradient descent with a small step.
• Critically damped: a double root. The fastest decay without oscillation.
• Under-damped (much momentum): complex roots. $x_k$ oscillates around 0 and the oscillation decays.

Interactive figure: loading…

A quadratic in $d$ dimensions is $d$ such oscillators, one per eigenvalue of the Hessian. They share one $\eta$ and one $\beta$. The best choice makes all of them decay at the same rate. Section 3 computes it.

3. Definitions and main results #

Throughout: $f(x) = \tfrac12 x^\top A x - b^\top x$ with $A$ symmetric and its eigenvalues in $[\mu, L]$, $\mu > 0$. The minimizer is $x^\star = A^{-1}b$, the error is $e_k = x_k - x^\star$, and $\kappa = L/\mu$.

Theorem 1 (heavy ball on a quadratic) #

With

every eigen-component $c_k$ of the heavy-ball error satisfies $|c_k| \le (a + bk)\,\rho^k$, with constants $a, b \ge 0$ that depend on the start, and

These are Polyak's parameters.

Why this is true, in one sentence. The product of the two roots of $z^2 - (1 + \beta - \eta\lambda)z + \beta$ is always $\beta$; when the roots are complex, both have size $\sqrt\beta$; so we choose $\eta$ and $\beta$ to make the roots complex for every $\lambda \in [\mu, L]$, with the smallest possible $\beta$.

Proof.

1. $\nabla f(x_k) = Ax_k - b = Ae_k$, so $e_{k+1} = e_k - \eta Ae_k + \beta(e_k - e_{k-1})$.
2. Write $A = Q\Lambda Q^\top$. In the eigenbasis the components do not interact. For one eigenvalue $\lambda$ with component $c_k$:

$T_\lambda$ is the iteration matrix: the second row only copies $c_k$ down. 3. The eigenvalues $z$ of $T_\lambda$ solve $\det(T_\lambda - zI) = z^2 - (1 + \beta - \eta\lambda)z + \beta = 0$. The product of the two roots is $\beta$. Complex roots are conjugates, $z$ and $\bar z$, so then $|z|^2 = z\bar z = \beta$ and $|z| = \sqrt\beta$, whatever $\lambda$ is. 4. The roots are complex (or double) when the discriminant is $\le 0$: $(1 + \beta - \eta\lambda)^2 \le 4\beta$, that is, $|1 + \beta - \eta\lambda| \le 2\sqrt\beta$. This is the band $(1 - \sqrt\beta)^2 \le \eta\lambda \le (1 + \sqrt\beta)^2$. 5. We want every $\lambda \in [\mu, L]$ in the band, with the smallest possible $\beta$. So we ask for equality at both ends: $\sqrt{\eta\mu} = 1 - \sqrt\beta$ and $\sqrt{\eta L} = 1 + \sqrt\beta$. 6. Add the two equations: $\sqrt\eta\,(\sqrt L + \sqrt\mu) = 2$, so $\eta = 4/(\sqrt L + \sqrt\mu)^2$. Divide them: $\sqrt\kappa = (1 + \sqrt\beta)/(1 - \sqrt\beta)$, so $\sqrt\beta = (\sqrt\kappa - 1)/(\sqrt\kappa + 1)$. 7. Now every $T_\lambda$ has spectral radius $\rho = \sqrt\beta$. At $\lambda = \mu$ and $\lambda = L$ the root is double, and the component there is $(a + bk)\rho^k$: the same rate, up to a factor $k$. $\blacksquare$

Interactive figure: loading…

Compare with gradient descent. For heavy ball, $\rho = (\sqrt\kappa - 1)/(\sqrt\kappa + 1) \approx 1 - 2/\sqrt\kappa$. For gradient descent with its best step, $(\kappa - 1)/(\kappa + 1) \approx 1 - 2/\kappa$. Per digit of accuracy, gradient descent needs $O(\kappa)$ steps and heavy ball $O(\sqrt\kappa)$.

Stability with momentum. Outside the band of step 4 one real root is larger than $\sqrt\beta$ in size. Heavy ball on a quadratic converges from every start exactly when

So momentum also raises the stability limit of the step, from $2/\lambda_{\max}$ to $2(1 + \beta)/\lambda_{\max}$. (These are the conditions for both roots of $z^2 - (1 + \beta - \eta\lambda)z + \beta$ to lie inside the unit circle, for every eigenvalue.)

Why the factor $k$ matters. At a double root the error is $(a + bk)\rho^k$, not $\rho^k$. The factor $k$ grows while $\rho^k$ shrinks, so the error can grow at first, and the measured count is larger than $\ln(1/\varepsilon)/\ln(1/\rho)$. In the predict-first example this is 44 steps instead of 34.

Interactive figure: loading…

Nesterov's accelerated gradient #

Nesterov's method takes the gradient at an extrapolated look-ahead point $y_k$ instead of at $x_k$. Start with $y_1 = x_0$. For $k = 1, 2, \dots$:

So $x_1 = x_0 - \tfrac1L\nabla f(x_0)$ is a plain gradient step. Two choices of $\beta_k$:

• for convex $f$: $t_1 = 1$, $t_{k+1} = \big(1 + \sqrt{1 + 4t_k^2}\big)/2$, $\beta_k = (t_k - 1)/t_{k+1}$. It starts at 0 and grows toward 1;
• for $\mu$-strongly convex $f$: the constant $\beta = (\sqrt\kappa - 1)/(\sqrt\kappa + 1)$.

Compare with heavy ball: heavy ball computes the gradient at $x_k$ and then adds the momentum. Nesterov first moves with the momentum, then computes the gradient where it lands. This look-ahead corrects the step before the overshoot happens.

Theorem 2 (Nesterov's rates) #

For every $L$-smooth convex $f$ with a minimizer $x^\star$ (not only quadratics), the convex choice of $\beta_k$ gives

(Beck and Teboulle 2009, Thm 4.4). If $f$ is also $\mu$-strongly convex, the constant $\beta$ gives

(Bubeck, Thm 3.18). Since $e^{-1/\sqrt\kappa} \approx 1 - 1/\sqrt\kappa$, this is about $(1 - 1/\sqrt\kappa)^k$. Gradient descent gets only $O(L\|x_0 - x^\star\|^2/k)$ and $(1 - 1/\kappa)^k$ (lesson 03). The proofs use estimate sequences or a potential function (Bubeck, §3.7); here we only state the results.

On a quadratic you can see the $1 - 1/\sqrt\kappa$. Per eigenvalue $\lambda$, Nesterov's recursion with step $1/L$ is $c_{k+1} = (1 - \lambda/L)\big[(1 + \beta)c_k - \beta c_{k-1}\big]$. At $\lambda = \mu$ its characteristic polynomial has a double root $z = 1 - 1/\sqrt\kappa$. For larger $\lambda$ the roots are complex with $|z|^2 = \beta(1 - \lambda/L)$, and at $\lambda = L$ both roots are 0. So on quadratics the factor is exactly $1 - 1/\sqrt\kappa$ (Lessard, Recht and Packard, Prop. 1). This is slower than heavy ball's $1 - 2/(\sqrt\kappa + 1)$, but it comes with a proof for every smooth strongly convex $f$.

The loss is not monotone. Gradient descent with step $1/L$ decreases $f$ at every step. Nesterov's method does not: $f(x_k)$ can go up for a while. Example: the convex choice of $\beta_k$ on $f(x) = \tfrac12(0.01x_1^2 + x_2^2)$ from $(1, 1)$ gives $f(x_{37}) \approx 8.1 \times 10^{-8}$ and $f(x_{38}) \approx 2.2 \times 10^{-6}$ (checked in the notebook). The bound of Theorem 2 still holds at every step; only the path to it has ripples.

Lower bounds: why these rates are the best possible #

Take any method whose iterates satisfy $x_k \in x_0 + \operatorname{span}\{\nabla f(x_0), \dots, \nabla f(x_{k-1})\}$: it moves only along gradients it has seen. Gradient descent, heavy ball, Nesterov and CG all do. Bubeck (§3.5) proves:

• for $k \le (n - 1)/2$ there is an $L$-smooth convex quadratic on $\mathbb{R}^n$ with $\min_{0 \le i < k} f(x_i) - f^\star \ge 3L\|x_0 - x^\star\|^2/\big(32(k + 1)^2\big)$ (Thm 3.14);
• there is an $L$-smooth, $\mu$-strongly convex function with $f(x_k) - f^\star \ge \tfrac{\mu}{2}\big(\tfrac{\sqrt\kappa - 1}{\sqrt\kappa + 1}\big)^{2k}\|x_0 - x^\star\|^2$ (Thm 3.15). Bubeck numbers the start $x_1$; we write both bounds with the start $x_0$.

Why. The hard function is a "chain" quadratic with a tridiagonal $A$. A point that is nonzero only in its first $j$ coordinates has a gradient that is nonzero only in the first $j + 1$ coordinates. So after $k$ gradients, the iterate is still zero in all later coordinates, but $x^\star$ is not. Information travels one coordinate per step.

So Nesterov's method is optimal up to constants: in the convex case both bounds are of order $L\|x_0 - x^\star\|^2/k^2$ (their ratio tends to $64/3 \approx 21$), and in the strongly convex case both need $\Theta(\sqrt\kappa\log(1/\varepsilon))$ steps.

Why heavy ball has no global guarantee #

The proof of Theorem 1 uses one fixed matrix $T_\lambda$ per eigenvalue. On a function that is not quadratic, the curvature changes from step to step, so the error is multiplied by a different matrix each time. Each matrix has spectral radius at most $\rho < 1$, but the matrices are not symmetric, and a product of such matrices can grow.

The counterexample of Lessard, Recht and Packard (2016, §4.6). A convex 1D function with $\mu = 1$ and $L = 25$ (its second derivative is 25, then 1, then 25):

With Polyak's parameters for $\kappa = 25$, $\eta = 1/9$ and $\beta = 4/9$, and a start $x_0 \in [3.07, 3.46]$, heavy ball falls into a cycle and never converges: it repeats $2.116 \to 0.647 \to -1.802$ forever (section 5 checks it). Nesterov's method with $\eta = 1/25$ and $\beta = 2/3$ converges on the same function, as Theorem 2 promises.

Goujaud, Taylor and Dieuleveut (2023) prove more: for every choice of constant parameters, heavy ball either does not accelerate on quadratics or fails to converge on some smooth strongly convex function. Locally it is fine: if $f$ is twice differentiable and $\mu I \preceq \nabla^2 f(x^\star) \preceq LI$, heavy ball started close enough to $x^\star$ converges at a rate close to its quadratic rate (Polyak 1964). This is one reason why it works well in practice.

In PyTorch #

torch.optim.SGD(params, lr=η, momentum=β) keeps a buffer $v$ and does

This is heavy ball: $x_{k+1} - x_k = -\eta v_{k+1} = -\eta\nabla f(x_k) + \beta(-\eta v_k) = -\eta\nabla f(x_k) + \beta(x_k - x_{k-1})$. With nesterov=True it uses $x_{k+1} = x_k - \eta\,(\nabla f(x_k) + \beta v_{k+1})$. This is Nesterov's method with a constant $\beta$, written in the look-ahead variable: PyTorch's parameter after $k$ steps equals $y_{k+1}$ above (checked in the notebook). We write the momentum as $\beta$; PyTorch's documentation calls it $\mu$.

The Krylov view: gradient descent, heavy ball and conjugate gradients

Let $r_0 = Ax_0 - b = \nabla f(x_0)$ and $K_k(A, r_0) = \operatorname{span}\{r_0, Ar_0, \dots, A^{k-1}r_0\}$, the Krylov subspace. Write $\|e\|_A = \sqrt{e^\top Ae}$ for the $A$-norm.

1. Gradient descent, heavy ball and Nesterov add to the current point a gradient ($Ae_k$, or $A(y_k - x^\star)$ for Nesterov) and a multiple of the last step. By induction, $x_k - x_0 \in K_k(A, r_0)$.
2. Hence $e_k = p_k(A)\,e_0$ for a polynomial $p_k$ of degree at most $k$ with $p_k(0) = 1$. Gradient descent: $p_k(\lambda) = (1 - \eta\lambda)^k$. Heavy ball: $p_0 = 1$, $p_1 = 1 - \eta\lambda$, $p_{k+1} = (1 + \beta - \eta\lambda)p_k - \beta p_{k-1}$. This is the Chebyshev iteration with its coefficients frozen at their limit values, so $p_k$ is close to the scaled Chebyshev polynomial, the polynomial with the smallest maximum on $[\mu, L]$.
3. Expand $e_0 = \sum_i c_i q_i$ in the eigenvectors $q_i$ of $A$. Then $\|p(A)e_0\|_A^2 = \sum_i \lambda_i c_i^2\,p(\lambda_i)^2$.
4. Conjugate gradient (CG) chooses $x_k \in x_0 + K_k(A, r_0)$ to minimize $\|e_k\|_A$ (linear algebra 14). So it uses the best polynomial for this spectrum and this $e_0$. The heavy-ball polynomial is one of the candidates, so $\|e_k^{\text{CG}}\|_A \le \|e_k^{\text{HB}}\|_A$ for every $k$. The same holds against gradient descent and Nesterov.
5. Two consequences. CG has the same worst-case bound, $\|e_k\|_A \le 2\rho^k\|e_0\|_A$ with $\rho = (\sqrt\kappa - 1)/(\sqrt\kappa + 1)$, without knowing $\mu$ and $L$. And if $A$ has $m$ distinct eigenvalues, $p(\lambda) = \prod_{j=1}^m (1 - \lambda/\lambda_j)$ is zero on the whole spectrum, so CG is exact after $m$ steps.

The CG figure in linear algebra 14 shows this on a 2D quadratic: CG reaches $x^\star$ in 2 steps (two distinct eigenvalues), while steepest descent zig-zags.

Why is CG not used to train neural networks? Its optimality needs exact gradients of one fixed quadratic. Minibatch gradients are noisy and the loss is not quadratic, so conjugacy is lost. Momentum keeps working with noisy gradients and changing curvature.

Answers to section 1. (1) About 45: section 4 counts 44. The factor per step is $2/3$ instead of $12/13$; the factor $k$ from the double roots costs about 10 extra steps. (2) Not always. The Lessard–Recht–Packard function has exactly $\mu = 1$ and $L = 25$, and heavy ball with these parameters cycles on it. Nesterov's method converges on it.

4. Worked example #

$f(x) = \tfrac12(x_1^2 + 25x_2^2)$, $x^\star = 0$, $x_0 = (1, 1)$. So $\mu = 1$, $L = 25$, $\sqrt\kappa = 5$. "Steps" means the first $k$ with $\|e_k\| \le 10^{-6}\|e_0\|$.

Method	Parameters	Factor per step	Steps
gradient descent	$\eta = 2/(\mu + L) = 1/13$	$12/13 \approx 0.923$	173
heavy ball	$\eta = 4/36 = 1/9$, $\beta = (4/6)^2 = 4/9$	$\sqrt\beta = 2/3$	44
Nesterov	$\eta = 1/25$, $\beta = 4/6 = 2/3$	$1 - 1/5 = 0.8$	73
conjugate gradient	none	—	2

Gradient descent. Each coordinate is multiplied by $1 - \lambda/13$: by $12/13$ and by $1 - 25/13 = -12/13$. So $\|e_k\| = (12/13)^k\|e_0\|$, and $k \ge \ln 10^6/\ln(13/12) = 172.6$.

Heavy ball, by hand. Step 1 has no momentum yet ($x_{-1} = x_0$): $x_1 = \big(1 - \tfrac19\cdot 1,\ 1 - \tfrac19\cdot 25\big) = (8/9,\ -16/9)$. The steep coordinate overshoots. Step 2:

For $\lambda = 1$: $1 + \tfrac49 - \tfrac19 = \tfrac43$, so the polynomial is $z^2 - \tfrac43z + \tfrac49 = (z - \tfrac23)^2$. For $\lambda = 25$: $1 + \tfrac49 - \tfrac{25}{9} = -\tfrac43$, so it is $z^2 + \tfrac43z + \tfrac49 = (z + \tfrac23)^2$. Both roots are double, so each component is $(a + bk)(\pm\tfrac23)^k$. The first two values fix $a$ and $b$:

Check at $k = 2$: $\tfrac53\cdot\tfrac49 = \tfrac{20}{27}$ ✓ and $\tfrac{13}{3}\cdot\tfrac49 = \tfrac{52}{27}$ ✓. The norm first grows, to $1.46\,\|e_0\|$ at $k = 2$, then falls fast. Because of the factor $k$ we need 44 steps, not $\ln 10^6/\ln 1.5 = 34.1$.

Nesterov. The step $1/L$ multiplies the steep coordinate by $1 - 25/25 = 0$, so it is zero after one step and stays zero. The flat coordinate has the double root $0.8$: $e_{k,1} = (1 + 0.2k)\,0.8^k$, so $x_1 = (0.96, 0)$ and $x_2 = (0.896, 0)$. That gives 73 steps.

Conjugate gradient. There are two distinct eigenvalues, so the polynomial $p_2(\lambda) = (1 - \lambda)(1 - \lambda/25)$ is zero on both: $x_2 = x^\star$ exactly.

The polynomials after two steps, at $\lambda = 1$ and $\lambda = 25$. Gradient descent, $(1 - \lambda/13)^2$: 0.852 and 0.852. Heavy ball, $1 - 22\lambda/81 + \lambda^2/81$: 0.741 and 1.926. CG: 0 and 0. Early on, heavy ball is even worse than gradient descent along the steep direction; CG is never worse than either.

5. In code #

NumPy checks the worked example and the counterexample. The notebook has these cells and the exercises.

import numpy as np

mu, L = 1.0, 25.0
s = np.sqrt(L / mu)                                  # sqrt(kappa) = 5
eta = 4 / (np.sqrt(L) + np.sqrt(mu)) ** 2            # 1/9
beta = ((s - 1) / (s + 1)) ** 2                      # 4/9

# 1) spectral radius of the 2x2 heavy-ball matrix, inside and outside [mu, L]
for lam in [0.5, 1, 9, 25, 30]:
    T = np.array([[1 + beta - eta * lam, -beta], [1, 0]])
    print(lam, round(np.abs(np.linalg.eigvals(T)).max(), 4))
# 0.5 0.8889 | 1 0.6667 | 9 0.6667 | 25 0.6667 | 30 1.6134

# 2) steps until ||e_k|| <= 1e-6 ||e_0|| on diag(1, 25) from (1, 1)
lam = np.array([mu, L])
def steps(update):
    e, e_prev, y, k = np.ones(2), np.ones(2), np.ones(2), 0
    while np.linalg.norm(e) > 1e-6 * np.sqrt(2):
        e, e_prev, y = update(e, e_prev, y)
        k += 1
    return k

gd = lambda e, ep, y: ((1 - 2 / (mu + L) * lam) * e, e, y)
hb = lambda e, ep, y: (e - eta * lam * e + beta * (e - ep), e, y)
def nag(e, ep, y, b=(s - 1) / (s + 1)):
    x = y - lam * y / L                              # gradient step at the look-ahead point
    return x, e, x + b * (x - e)
print(steps(gd), steps(hb), steps(nag))              # 173 44 73

# 3) the Lessard-Recht-Packard function: mu = 1, L = 25, not a quadratic
def grad(x):
    return 25 * x if x < 1 else (x + 24 if x < 2 else 25 * x - 24)
x, x_prev = 3.3, 3.3
for k in range(1000):
    x, x_prev = x - eta * grad(x) + beta * (x - x_prev), x
print([round(float(v), 3) for v in (x_prev, x)])    # [0.647, -1.802]: part of the cycle 2.116 -> 0.647 -> -1.802

The cycle has length 3: the iterates repeat $2.116, 0.647, -1.802$ forever. The notebook also runs Nesterov's method on this function and checks that it converges.

6. Where it shows up #

• Training neural networks. torch.optim.SGD(momentum=0.9) and Adam's $\beta_1 = 0.9$: along a consistent direction the step is $\eta/(1 - \beta) = 10\eta$. With noisy minibatch gradients the gain over gradient descent is smaller, because the noise, not $\kappa$, limits the progress (Goh, "Why Momentum Really Works", section on stochastic gradients; lesson 05). nesterov=True gives Nesterov's method.
• Sparse and nonsmooth problems. FISTA (lesson 09) is Nesterov's method plus a proximal step. It is a standard solver for the lasso and for compressed sensing and imaging inverse problems.
• Scientific computing. Preconditioned CG solves the sparse symmetric positive definite systems of discretized elliptic PDEs (Poisson, implicit diffusion) and the Newton systems of Newton-CG with Hessian-vector products (lesson 10). In weather forecasting, the inner loop of incremental 4D-Var minimizes a quadratic cost with a preconditioned CG or Lanczos method.

7. Common mistakes #

• Expecting the $\sqrt\kappa$ rate of Polyak's parameters on a problem that is not quadratic. It is proven only for quadratics (and near a minimizer). For general functions heavy ball can cycle.
• Taking Nesterov's gradient at $x_k$. That is heavy ball. Nesterov uses the look-ahead point $y_k$.
• Ignoring the factor $k$. At double roots the error is $(a + bk)\rho^k$. It can grow at first, and a rate measured over a short window looks worse than $\rho$.
• Keeping the gradient-descent stability limit. With momentum the limit on a quadratic is $\eta < 2(1 + \beta)/\lambda_{\max}$, not $2/\lambda_{\max}$. And $\eta/(1 - \beta)$, not $\eta$, is the effective step along a consistent direction: when you add momentum 0.9, divide the learning rate by about 10 to keep the same effective step.
• Expecting $f(x_k)$ to decrease at every step. Heavy ball and Nesterov are not monotone.
• Calling CG "always better". It is optimal only for exact gradients of one fixed quadratic.

8. Check yourself #

1. The eigenvalues lie in $[\mu, L] = [4, 100]$. Give Polyak's $\eta$, $\beta$ and factor, and the gradient-descent factor with its best step.
   Answer

   $\kappa = 25$, $\sqrt L = 10$, $\sqrt\mu = 2$: $\eta = 4/144 = 1/36$, $\beta = (4/6)^2 = 4/9$, factor $2/3$. Gradient descent: $(25 - 1)/(25 + 1) = 12/13$. The factors depend only on $\kappa$; the step scales like $1/L$.
2. Why is $|z| = \sqrt\beta$ for every $\lambda$ inside the band $(1 - \sqrt\beta)^2 \le \eta\lambda \le (1 + \sqrt\beta)^2$?
   Answer

   The product of the two roots of $z^2 - (1 + \beta - \eta\lambda)z + \beta$ is $\beta$. Inside the band the roots are complex conjugates (or a double root), so they have the same size, and $|z|^2 = z\bar z = \beta$.
3. You run heavy ball with $\eta = 1/9$, $\beta = 4/9$ (tuned for $L = 25$), but the true largest eigenvalue is 30. What happens?
   Answer

   $\eta\lambda = 30/9 \approx 3.33$, which is above $2(1 + \beta) = 26/9 \approx 2.89$. One real root has size $1.61 > 1$, so heavy ball diverges along that eigenvector.
4. Write one step of torch.optim.SGD(lr=0.1, momentum=0.9) from $v = (1, 0)$ with gradient $(0, 2)$. What is the change in the parameters?
   Answer

   $v \leftarrow 0.9\,(1, 0) + (0, 2) = (0.9, 2)$, and the parameters change by $-0.1\,v = (-0.09, -0.2)$.
5. $A \in \mathbb{R}^{1000 \times 1000}$ is symmetric positive definite with only 3 distinct eigenvalues. How many CG steps give the exact solution, and why does this not contradict the lower bounds?
   Answer

   At most 3: $\prod_{j=1}^3(1 - \lambda/\lambda_j)$ vanishes on the spectrum. The lower bounds hold for a specific hard function with many distinct eigenvalues (and $k \le (n - 1)/2$); they are worst-case statements, not statements about every quadratic.

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. Write the heavy-ball update.

   Show answer

2. Heavy ball with $\beta = 0.9$ and a constant gradient $g$: what step does it approach?

   Show answer

3. Polyak's parameters for heavy ball on a quadratic with eigenvalues in $[\mu, L]$?

   Show answer

4. Factor per step of heavy ball with Polyak's parameters?

   Show answer

5. Why do the complex roots of $z^2 - (1 + \beta - \eta\lambda)z + \beta$ have size $\sqrt\beta$?

   Show answer

6. Steps per digit of accuracy: gradient descent against momentum?

   Show answer

7. Stability condition of heavy ball on a quadratic?

   Show answer

8. Write Nesterov's method (step $1/L$).

   Show answer

9. Nesterov's rate for an $L$-smooth convex $f$?

   Show answer

10. Why has heavy ball no global guarantee?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Why does momentum speed up gradient descent?" — On a quadratic each eigen-direction becomes a two-term recurrence. The best parameters give all roots the size $(\sqrt\kappa - 1)/(\sqrt\kappa + 1)$, so the step count per digit drops from $O(\kappa)$ to $O(\sqrt\kappa)$. Intuition: momentum averages the gradients, so the zig-zag across the valley cancels and the motion along it adds up.
• "Heavy ball or Nesterov?" — Gradient at $x_k$ or at the look-ahead point. Heavy ball's acceleration is proven only for quadratics; Nesterov is optimal for all smooth (strongly) convex functions.
• "What is the best possible first-order rate?" — $\Omega(1/k^2)$ for smooth convex functions, and $\Theta(\sqrt\kappa\log(1/\varepsilon))$ steps for smooth strongly convex ones; Nesterov reaches both up to constants.
• "What does momentum 0.9 do to the step size?" — Up to $1/(1 - \beta) = 10$ times larger along consistent directions, and the stability limit on a quadratic becomes $\eta < 2(1 + \beta)/\lambda_{\max}$.

10. Practice #

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

1. Build the $2 \times 2$ heavy-ball matrix $T_\lambda$ and check its spectral radius against $\sqrt\beta$ inside the band and outside it.
2. Implement heavy ball and Nesterov, and count steps against gradient descent for $\kappa = 10, 100, 1000$.
3. Run Nesterov's method (convex choice of $\beta_k$) on a convex least-squares problem; check the $O(1/k^2)$ bound and find the steps where $f$ goes up.
4. Implement conjugate gradients and check that CG is never worse than heavy ball in the $A$-norm.

11. Watch and read #

23. Accelerating Gradient Descent (Use Momentum)MIT OpenCourseWare · Gilbert Strang, 18.065 (2018) · 49 min

Strang derives the best momentum parameters for a quadratic from the 2×2 matrix, as in Theorem 1, and gets the factor with √κ.

Gradient Descent With Momentum (C2W2L06)DeepLearningAI · Andrew Ng · 9 min

The practical view: momentum as an exponentially weighted average of gradients that damps the oscillation across a valley.

MOMENTUM Gradient Descent (in 3 minutes)Visually Explained · 3 min

A short animation of the rolling-ball picture.

• Gabriel Goh, "Why Momentum Really Works" (Distill, 2017): interactive figures of the damped oscillator, the best parameters, and the lower bound ("the limits of descent").
• Sébastien Bubeck, Convex Optimization: Algorithms and Complexity, free: §3.5 (lower bounds, Thm 3.14–3.15) and §3.7 (Nesterov's method, Thm 3.18–3.19).
• Lessard, Recht and Packard, "Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints": §2.2 (Prop. 1, rates on quadratics) and §4.6 (the heavy-ball counterexample).
• Goujaud, Taylor and Dieuleveut, "Provable non-accelerations of the heavy-ball method" (2023).
• Beck and Teboulle, "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems", SIAM Journal on Imaging Sciences 2(1), 2009: Thm 4.4 is the $2L\|x_0 - x^\star\|^2/(k+1)^2$ bound.
• PyTorch, torch.optim.SGD: the exact update with momentum and nesterov.