Gradient Descent

To minimize a function you can't solve in closed form, walk downhill. Turn a direction and watch the slope trace a cosine, steer descent across a narrow valley, compare convex and nonconvex landscapes against Newton's method, sample mini-batches, and see why the small eigenvalues of a quadratic set the speed of learning.

Follows S. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press, 2004; free online), Chapter 9, and I. Goodfellow, Y. Bengio and A. Courville, Deep Learning (MIT Press, 2016), Chapter 8, for momentum and stochastic gradients. The questions and examples are written for this page. Gradient descent is the explicit Euler scheme for the gradient flows of the Gradient Flows page; its uses in machine learning are on the Neural Networks page. For how this subject connects to the others, see the roadmap.

InteractiveGoodfellow–Bengio–Courville, Ch. 8: Optimization for Training Deep Models

Gradient descent, momentum and mini-batches

Fitting a network means minimizing a loss over its weights. Gradient descent does it by walking downhill: from wherever you are, take a small step in the direction in which the loss decreases fastest. Which direction is that? The directional derivative answers it.

Start here: the directional derivative

Stand at a point $p$ on a surface $f(x,y)$ . In one dimension you can only go left or right, but here you can head off in any direction. Pick a unit vector $v$ . The directional derivative is the slope of $f$ in that direction:

D_vf(p)=\lim_{h\to0}\frac{f(p+hv)-f(p)}{h}=\nabla f(p)\cdot v,

the second equality by the chain rule applied to $h\mapsto f(p+hv)$ . Since $\nabla f\cdot v=\|\nabla f\|\,\|v\|\cos\phi$ , where $\phi$ is the angle between $v$ and the gradient, the slope as you turn $v$ all the way round is a cosine wave of height $\|\nabla f(p)\|$ :

it is largest, $+\|\nabla f\|$ , at $\phi=0$ : along the gradient, the steepest way up;
it is zero at $\phi=\pm\pi/2$ : along the contour line through $p$ ;
it is smallest, $-\|\nabla f\|$ , at $\phi=\pi$ : along $-\nabla f$ , the steepest way down.

That last line is the whole reason gradient descent steps along $-\nabla f$ . Try it below: drag the direction round and find the minimum of the curve on the right.

Contours of

f(x,y)=\tfrac12x^2+y^2+\tfrac13\sin(2x)\sin(y)

. Drag the point

p

, and drag the tip of

v

round the circle.

\nabla f(p)

-\nabla f(p)

The slope

D_vf(p)

for every direction

v

, by its angle. your

v

. The lowest point is

-\nabla f

The idea

The update. To decrease a loss $L$ , step in its steepest downhill direction, $-\nabla L$ , found above:

w_{t+1}=w_t-\alpha\,\nabla L(w_t).

The gradient says which way to go, not how far: the learning rate $\alpha$ is a choice. In machine learning $L(\theta)=\frac1N\sum_{i=1}^N\ell\big(f_\theta(x_i),y_i\big)$ is the average loss over the data, and computing its gradient through the network's layers is backpropagation.

Quadratics, one direction at a time. For

L(w)=\tfrac12(w-w^\star)^\top H(w-w^\star)

with

H

symmetric positive definite,

\nabla L=H(w-w^\star)

, so

w_{t+1}-w^\star=(I-\alpha H)(w_t-w^\star).

Along an eigenvector of

H

with eigenvalue

\lambda

, the error is multiplied by

1-\alpha\lambda

each step. Steep directions (large

\lambda

) need

\alpha<2/\lambda_{\max}

or the iterates blow up; flat directions (small

\lambda

) then crawl at rate

1-\alpha\lambda_{\min}

. The ratio

\kappa=\lambda_{\max}/\lambda_{\min}

sets the speed: about

\kappa

steps per factor of

e

Momentum (heavy ball). Keep part of the previous step:

w_{t+1}=w_t-\alpha\nabla L(w_t)+\beta\,(w_t-w_{t-1}).

In a flat valley the steps all point the same way and add up; across a narrow valley they alternate and cancel. Well tuned, it needs about

\sqrt\kappa

steps instead of

\kappa

Mini-batches. With millions of data points, use the average gradient over a random batch

B_t

|B|

of them:

g_t=\frac1{|B|}\sum_{i\in B_t}\nabla\ell_i

. It is unbiased,

\mathbb E[g_t]=\nabla L

, but noisy, with variance shrinking like

1/|B|

. The noise is the price of cheap steps, and it keeps the iterates jittering near the minimum unless

\alpha

is decreased.

Explore: descent on a valley

Steepness ratio κ Learning rate α Momentum β Batch noise

Contours of

L(w)=\tfrac12(w_1^2+\kappa w_2^2)

; the minimum is at the centre. Drag the start. the first 60 steps.

Worked example

$L(w)=\tfrac12(w_1^2+10w_2^2)$ , so $H=\mathrm{diag}(1,10)$ . Start at $w_0=(1,1)$ .

With $\alpha=0.1$ : the per-step factors in each coordinate, and $w_t$ .

$1-0.1\cdot1=0.9$ and $1-0.1\cdot10=0$ . So $w_1=(0.9,0)$ : the steep coordinate is solved in one step, and $w_t=(0.9^t,0)$ after that. Reaching $|w_1|<10^{-3}$ takes $t\ge66$ steps.
With $\alpha=0.25$ ?

Factors $0.75$ and $1-2.5=-1.5$ . The second coordinate flips sign and grows by 1.5 each step: divergence, since $\alpha>2/\lambda_{\max}=0.2$ .
What is the best fixed $\alpha$ , and how fast is it?

Balance the two factors: $1-\alpha=-(1-10\alpha)$ , so $\alpha=2/11$ and both have size $9/11=\frac{\kappa-1}{\kappa+1}\approx0.82$ . About 35 steps for three digits. Momentum improves this to roughly $\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\approx0.52$ per step.

Check your understanding

Why step against the gradient rather than along it?

$\nabla L\cdot v=\|\nabla L\|\|v\|\cos\phi$ is smallest at $\phi=\pi$ : the loss falls fastest opposite to the gradient.
Along the gradient the step would be too long.Length is set by $\alpha$ ; direction is the issue.

The gradient points uphill, in the direction of fastest increase. Gradient ascent (

+\alpha\nabla L

) maximizes, as in policy-gradient methods that maximize expected return.

On an ill-conditioned quadratic ( $\kappa=100$ ) plain gradient descent is slow because:

$\alpha$ must be below $2/\lambda_{\max}$ for the steep direction, which makes progress in the flat direction tiny.
The gradient points away from the minimum.It points downhill, just not at the minimum: it zigzags across the valley.

One learning rate serves all directions. Momentum, preconditioning and adaptive methods (Adam) are different ways around this.

Doubling the batch size $|B|$ changes the mini-batch gradient's standard deviation by a factor of:

$1/2$ That is the variance, not the standard deviation.
$1/\sqrt2$
$1$ : the noise comes from the data, not the batch.Averaging more independent samples reduces it.

The average of

|B|

independent gradients has variance

\sigma^2/|B|

. Twice the work per step buys only

\sqrt2

less noise, which is one reason small batches are popular.

Practice

The gradient of a quadraticThree lines

For $L(w)=\tfrac12w^\top Hw-q^\top w$ with $H$ symmetric, show $\nabla L=Hw-q$ , find the minimizer, and rewrite gradient descent as $w_{t+1}-w^\star=(I-\alpha H)(w_t-w^\star)$ .

Solution

$\partial_k\tfrac12\sum_{ij}H_{ij}w_iw_j=\tfrac12\sum_j(H_{kj}+H_{jk})w_j=(Hw)_k$ by symmetry, and $\partial_kq^\top w=q_k$ . The minimizer solves $Hw^\star=q$ . Then $w_{t+1}=w_t-\alpha(Hw_t-q)=w_t-\alpha H(w_t-w^\star)$ ; subtract $w^\star$ .

Momentum on a lineThe characteristic equation

Apply heavy ball to $L(w)=\tfrac\lambda2w^2$ . Show that $e_t=w_t$ satisfies $e_{t+1}=(1+\beta-\alpha\lambda)e_t-\beta e_{t-1}$ , and find when it converges for $\beta=0.5$ , $\lambda=1$ .

Solution

Substitute $\nabla L=\lambda w$ . The roots of $z^2-(1+\beta-\alpha\lambda)z+\beta=0$ have product $\beta=0.5$ ; the iteration converges iff both have modulus below 1, which (Jury's test) means $|1+\beta-\alpha\lambda|<1+\beta$ : $0<\alpha<3$ . Momentum enlarges the stable range from $\alpha<2$ to $\alpha<2(1+\beta)$ .

InteractiveBoyd–Vandenberghe, Ch. 9: Unconstrained minimization (§§9.1–9.3, 9.5)

Convexity and convergence rates

How fast gradient descent converges, and whether it finds the best point at all, depends on the shape of the function. Three shapes cover most of what happens: strongly convex (fast and sure), convex but flat at the bottom (sure but slow), and nonconvex (fast, but maybe to the wrong place).

The idea

Convex.

f

is convex if the chord lies above the graph:

f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)

for

\theta\in[0,1]

. For differentiable

f

, equivalently, every tangent lies below:

f(y)\ge f(x)+\nabla f(x)^\top(y-x)

. Consequence: if

\nabla f(x)=0

, then

f(y)\ge f(x)

for all

y

. Every stationary point is a global minimum.

Smooth and strongly convex. Bounds on the curvature:

mI\preceq\nabla^2f(x)\preceq LI

everywhere, with

0<m\le L

L

caps how steep the slope can change (it limits the step size);

m>0

means the function curves up at least like

\tfrac m2\|x\|^2

(strongly convex). Their ratio

\kappa=L/m

is the condition number.

Rates for gradient descent with step $1/L$ (Boyd–Vandenberghe §9.3, and standard convex-optimization texts).

Strongly convex: $f(x_t)-f^\star\le\big(1-\tfrac mL\big)^t\big(f(x_0)-f^\star\big)$ . Linear convergence: a fixed number of steps per extra digit, about $\kappa\ln10$ .
Convex and $L$ -smooth only: $f(x_t)-f^\star\le\dfrac{L\|x_0-x^\star\|^2}{2t}$ . Sublinear: ten times more steps for one more digit.
Nonconvex, $L$ -smooth: $\min_{s<t}\|\nabla f(x_s)\|^2\le\dfrac{2L(f(x_0)-f^\star)}t$ . Gradients get small, so the iterates approach some stationary point, which can be a local minimum that is not global.

Newton's method (Boyd–Vandenberghe §9.5). Step

x_{t+1}=x_t-\nabla^2f(x_t)^{-1}\nabla f(x_t)

: minimize the local quadratic model exactly instead of taking a small step downhill. Near a minimum with

\nabla^2f\succ0

, it converges quadratically (the number of correct digits roughly doubles per step) and ignores the condition number. Its weaknesses show in the figure: where the curvature is zero it slows down, and where it is negative it heads for a maximum.

Explore

Function

Method

Step size α

Drag the start along the curve. the first 40 iterates. the global minimum.

f(x_t)-f^\star

on a log scale. A straight line sloping down is linear convergence; a curve that flattens is sublinear; a line that stops falling has stalled away from the global minimum.

Worked example

$f(x)=\tfrac12(x_1^2+10x_2^2)$ , so $m=1$ , $L=10$ , $\kappa=10$ , $f^\star=0$ . Gradient descent with $\alpha=1/L=0.1$ .

What does the strongly convex rate promise?

$f(x_t)\le0.9^t f(x_0)$ . To gain six digits, $0.9^t\le10^{-6}$ : $t\ge\frac{6\ln10}{-\ln0.9}\approx132$ steps.
What actually happens? (Do each coordinate separately.)

$x_2$ is multiplied by $1-0.1\cdot10=0$ : gone after one step. $x_1$ is multiplied by $0.9$ per step, so $f(x_t)=\tfrac12\,0.81^t\,x_{0,1}^2$ : six digits after about 66 steps. The bound holds, with room to spare (it assumes the worst direction for every step).
Now take $f(x)=x^4/4$ from $x_0=1$ with $\alpha=0.5$ . Is the convergence linear?

$x_{t+1}=x_t-0.5x_t^3$ . Near 0 the step shrinks with $x_t^3$ : from $x=0.1$ the next iterate is $0.0995$ . The curvature $3x^2$ vanishes at the minimum, so there is no $m>0$ , and $f(x_t)$ decays like $1/t^2$ rather than geometrically: sublinear.

Check your understanding

Gradient descent on a convex function stops at a point with $\nabla f=0$ . Is it the global minimum?

Yes: for convex $f$ , $f(y)\ge f(x)+\nabla f(x)^\top(y-x)=f(x)$ for every $y$ .
Not necessarily; it could be a local minimum.That happens only without convexity.

The tangent-plane inequality is the whole reason convex problems are “easy”: there are no bad stationary points to get stuck in.

On a plot of $\log(f(x_t)-f^\star)$ against $t$ , linear convergence looks like:

A straight line sloping down.
A curve that keeps flattening.That is sublinear convergence, like $1/t$ .

f(x_t)-f^\star\approx c\,q^t

gives

\log(f-f^\star)\approx\log c+t\log q

, a straight line with slope

\log q<0

In the figure, Newton's method on the nonconvex function sometimes moves uphill. Why?

Where $f''<0$ , the Newton step $-f'/f''$ points uphill: it heads for the stationary point of a downward-curving quadratic, a maximum.
The step size is too large.Newton's method has no step size here; the direction itself is wrong.

Newton's method finds stationary points, not minima. Practical versions check the curvature, use a line search, or regularize the Hessian.

Practice

The descent lemmaWhy the step is 1/L

If $\nabla^2f\preceq LI$ , show $f(y)\le f(x)+\nabla f(x)^\top(y-x)+\frac L2\|y-x\|^2$ , and deduce that a gradient step with $\alpha=1/L$ decreases $f$ by at least $\frac1{2L}\|\nabla f(x)\|^2$ .

Solution

Taylor's theorem with remainder: $f(y)=f(x)+\nabla f(x)^\top(y-x)+\tfrac12(y-x)^\top\nabla^2f(z)(y-x)$ for some $z$ on the segment, and the last term is at most $\frac L2\|y-x\|^2$ . Put $y=x-\frac1L\nabla f(x)$ : $f(y)\le f(x)-\frac1L\|\nabla f\|^2+\frac1{2L}\|\nabla f\|^2$ . Summing these decreases over $t$ steps gives the nonconvex rate.

Linear rate from strong convexityOne line more

Strong convexity implies $\|\nabla f(x)\|^2\ge2m(f(x)-f^\star)$ . Combine with the previous problem to get $f(x_{t+1})-f^\star\le(1-\frac mL)(f(x_t)-f^\star)$ .

Solution

$f(x_{t+1})-f^\star\le f(x_t)-f^\star-\frac1{2L}\|\nabla f(x_t)\|^2\le f(x_t)-f^\star-\frac mL(f(x_t)-f^\star)$ . Iterate.

InteractiveGoodfellow–Bengio–Courville, §8.1.3 and §8.3.1

Mini-batches and stochastic gradients

The loss is an average over the whole dataset, and so is its gradient. With millions of data points, computing it exactly for every step is too expensive. Instead, pick a small random batch, average its gradients, and step. The step is now random, and that randomness is the whole story of this module.

The idea

With data $(x_i,y_i)$ , $i=1,\dots,N$ , and a per-example loss $\ell_i(\theta)=\ell(f_\theta(x_i),y_i)$ ,

L(\theta)=\frac1N\sum_{i=1}^N\ell_i(\theta),\qquad\nabla L(\theta)=\frac1N\sum_{i=1}^N\nabla\ell_i(\theta).

One full gradient step costs $N$ per-example gradients.

Mini-batch SGD. At step

t

, draw a batch

B_t

|B|

indices uniformly at random and step along

g_t=\frac1{|B|}\sum_{i\in B_t}\nabla\ell_i(\theta_t),\qquad\theta_{t+1}=\theta_t-\alpha\,g_t.

Each step costs

|B|

gradients instead of

N

Why it works, and what it costs. Where does the randomness come from? Only from which examples were picked; a different batch gives a different step. Averaged over the possible batches,

\mathbb E[g_t]=\nabla L(\theta_t)

: the step is right on average (unbiased). Its variance is

\frac{\sigma^2}{|B|}

when sampling with replacement, where

\sigma^2

is the variance of a single example's gradient (without replacement, multiply by

\frac{N-|B|}{N-1}

). So the noise shrinks like

1/\sqrt{|B|}

while the cost grows like

|B|

The consequence: with a fixed step size $\alpha$ , SGD does not converge to the minimizer. It reaches the neighbourhood quickly and then jitters around it, at a scale set by $\alpha$ and the noise. Decreasing $\alpha$ over time (a schedule) or increasing $|B|$ shrinks the jitter.

Explore

Batch size |B| Step size α

100 data points. this step's batch and the current line

y=ax+c

Loss over

(a,c)

. full gradient descent mini-batch SGD minimizer.

Worked example

Fit $f_\theta(x)=\theta x$ to four points $x=(1,2,3,4)$ , $y=(2,3,7,8)$ with $\ell_i=\tfrac12(\theta x_i-y_i)^2$ . Take $\theta=1$ .

Compute each $\nabla\ell_i=(\theta x_i-y_i)x_i$ and the full gradient.

Residuals $\theta x_i-y_i=(-1,-1,-4,-4)$ ; gradients $(-1,-2,-12,-16)$ . Full gradient $-31/4=-7.75$ .
List the mini-batch gradients for all six batches of size 2.

$\{1,2\}:-1.5$ , $\{1,3\}:-6.5$ , $\{1,4\}:-8.5$ , $\{2,3\}:-7$ , $\{2,4\}:-9$ , $\{3,4\}:-14$ . They range from $-1.5$ to $-14$ .
Average them.

$-46.5/6=-7.75$ , the full gradient exactly. Unbiased, but any single step can be five times too short or nearly twice too long.

Check your understanding

The randomness in a mini-batch gradient comes from:

Noise in the labels $y_i$ .The data are fixed once collected; full-batch descent on them is deterministic.
Which examples happened to be drawn into the batch.
Rounding errors.Those are tiny and not the point.

Whenever a quantity is random, ask what it depends on. Here the only random input is the choice of indices, made to avoid computing all

N

gradients.

You quadruple the batch size. Per step, the gradient's standard deviation:

halves, and each step costs four times as much.
quarters, at four times the cost.That's the variance.

Standard deviation

\sigma/\sqrt{|B|}

. Diminishing returns: past some batch size, more examples per step buy little extra accuracy per unit of compute.

In the figure, with $|B|=1$ and a large step, the SGD path ends in a cloud around the minimizer rather than at it. To land closer you could:

Decrease the step size over time, or use bigger batches.
Run more steps with the same settings.The cloud has a fixed size for fixed α and |B|: more steps just wander inside it.

With step

\alpha

and noise variance

\sigma^2/|B|

, the stationary jitter has size of order

\sqrt{\alpha\sigma^2/|B|}

. Robbins–Monro step sizes (

\sum\alpha_t=\infty

\sum\alpha_t^2<\infty

) drive it to zero.

Practice

UnbiasednessProve it

Let $B$ be $|B|$ indices drawn independently and uniformly from $\{1,\dots,N\}$ . Show $\mathbb E[g]=\nabla L$ and $\mathrm{Var}(g)=\sigma^2/|B|$ (coordinatewise), where $\sigma^2=\frac1N\sum_i|\nabla\ell_i-\nabla L|^2$ is computed per coordinate.

Solution

Each draw $I$ has $\mathbb E[\nabla\ell_I]=\frac1N\sum_i\nabla\ell_i=\nabla L$ and variance $\sigma^2$ . $g$ is the average of $|B|$ independent copies: same mean, variance divided by $|B|$ .

EpochsCounting passes

With $N=50{,}000$ examples and $|B|=100$ , how many SGD steps make one pass over the data (an epoch)? How many full-gradient steps cost the same?

Solution

500 SGD steps per epoch; the same compute buys one full-gradient step. Early in training, 500 noisy steps make far more progress than one exact one, which is why mini-batches are standard.

SimulationGoodfellow–Bengio–Courville, §8.2 and §8.3.2

Quadratics, spectra and power laws

On a quadratic loss, gradient descent splits into independent one-dimensional problems, one for each eigenvector of the Hessian. Each shrinks at its own rate, and the slow ones, with small eigenvalues, set the pace. When the eigenvalues follow a power law, so does the loss: $L_t\approx t^{-\zeta}$ .

The idea

The model. $L(w)=\tfrac12w^\top Hw-q^\top w$ . Check the objects: $w,q$ are column vectors, $H$ is a symmetric matrix, so $w^\top Hw$ and $q^\top w$ are numbers and $L$ is a number. The gradient with respect to $w$ (the variable we choose; $H$ and $q$ are given) is $Hw-q$ , so the minimizer has $Hw^\star=q$ .

Where $H$ comes from. For a linear model with squared loss, $\ell=\tfrac12(\langle w,x\rangle-y)^2$ averaged over data, the Hessian is $H=\mathbb E[xx^\top]$ . Note the order: $x^\top x$ is a number (inner product), $xx^\top$ is a matrix (outer product). $H$ is the covariance of the inputs, so its eigenvalues measure how much the data vary in each direction.

Spectral decomposition. Write

H=\sum_k\lambda_ku_ku_k^\top

with orthonormal eigenvectors

u_k

. “Decomposing” the error vector

e_t=w_t-w^\star

means writing it in this basis,

e_t=\sum_kc_k(t)u_k

. Since

e_{t+1}=(I-\alpha H)e_t

c_k(t)=(1-\alpha\lambda_k)^t\,c_k(0),\qquad L(w_t)-L(w^\star)=\tfrac12\sum_k\lambda_k(1-\alpha\lambda_k)^{2t}c_k(0)^2.

Directions with

\alpha\lambda_k

near 1 are fixed in a step or two; directions with tiny

\lambda_k

barely move.

Power laws. Suppose the error mass in small eigen-directions follows a power law:

\sum_{k:\lambda_k\le\lambda}\lambda_kc_k(0)^2\approx\lambda^{\zeta}

for small

\lambda

, with an exponent

\zeta>0

that is a property of the problem, not something you choose. Since

(1-\alpha\lambda)^{2t}\approx e^{-2\alpha\lambda t}

is near 0 when

\lambda\gg1/(\alpha t)

and near 1 when

\lambda\ll1/(\alpha t)

, after

t

steps only the directions with

\lambda\lesssim1/(\alpha t)

remain:

L(w_t)-L(w^\star)\approx\tfrac12\sum_{k:\lambda_k\lesssim1/(\alpha t)}\lambda_kc_k(0)^2\approx(\alpha t)^{-\zeta}.

Larger

\zeta

means less error hides in the flat directions, and faster learning. Power-law spectra like this are what is observed for real data and kernels, which is one reason training losses often fall like a power of the step count.

Momentum and acceleration. With constant $\alpha$ and $\beta$ , heavy ball behaves like gradient descent with step $\alpha/(1-\beta)$ on the slow directions: a constant-factor gain, the same exponent $\zeta$ . Schedules that vary $\alpha_t,\beta_t$ with $t$ (built from orthogonal polynomials such as Chebyshev or Jacobi polynomials) can roughly double the exponent to $t^{-2\zeta}$ on deterministic problems. With mini-batch noise these aggressive schedules can amplify the noise and diverge, which is an active research question.

Polynomials and contours. After $t$ steps of any such method the error is $e_t=p_t(H)e_0$ for a polynomial $p_t$ of degree $t$ with $p_t(0)=1$ (for gradient descent, $p_t(\lambda)=(1-\alpha\lambda)^t$ ). So the question “how fast can a method be?” becomes “how small can such a polynomial be on the spectrum?”. Functions of a matrix can be written with Cauchy's integral formula: for a closed curve $\Gamma$ in the complex plane enclosing all the eigenvalues,

f(H)=\frac1{2\pi i}\oint_\Gamma f(z)\,(zI-H)^{-1}\,dz,

which for diagonalizable

H

is the scalar formula

f(\lambda)=\frac1{2\pi i}\oint_\Gamma\frac{f(z)}{z-\lambda}dz

applied to each eigenvalue. Some recent work designs optimizers by choosing the contour

\Gamma

instead of the polynomial, and complex numbers are natural there: the per-direction iteration of a momentum method is a

2\times2

matrix whose eigenvalues are complex when it oscillates.

Explore

Spectrum decay ν (λₖ = k^−ν) Source exponent ζ Momentum β

A quadratic with 20,000 eigen-directions,

\lambda_k=k^{-\nu}

, step

\alpha=1

. Log–log axes. gradient descent heavy ball (constant β) slope

-\zeta

for reference.

Worked example

$H=\mathrm{diag}(1,\,0.01)$ , $w^\star=0$ , $w_0=(1,1)$ , step $\alpha=1$ .

Per-step factors and $w_t$ .

$1-\alpha\lambda_1=0$ and $1-\alpha\lambda_2=0.99$ : $w_1=(0,0.99)$ , then $w_t=(0,0.99^t)$ . The first direction is solved immediately.
The loss, and how many steps to reduce it by a factor of 1000.

$L_t=\tfrac12\cdot0.01\cdot0.99^{2t}$ . Need $0.99^{2t}\le10^{-3}$ : $t\ge\frac{\ln1000}{2\ln(1/0.99)}\approx344$ . All of that time is spent on the flat direction.
Could a larger step help?

Only up to $\alpha<2/\lambda_{\max}=2$ , where the steep factor is $|1-\alpha|$ . At $\alpha=1.98$ the flat factor is $0.9802$ , about 175 steps, but the steep direction now oscillates with factor $0.98$ . The best fixed step balances the two at $\alpha=2/1.01$ , giving $\frac{\kappa-1}{\kappa+1}\approx0.980$ for $\kappa=100$ . With thousands of directions spread over many scales, there is no balancing point, and the power law takes over.

Check your understanding

For a column vector $x\in\R^d$ , the object $xx^\top$ is:

The number $|x|^2$ .That is $x^\top x$ .
A $d\times d$ matrix of rank one.

A column times a row is a matrix (outer product); a row times a column is a number (inner product). Averaging the rank-one matrices

x_ix_i^\top

over the data gives the Hessian of the squared loss for a linear model.

“Spectral decomposition of the error vector $e_t$ ” means:

Computing the eigenvalues of $e_t$ .A vector has no eigenvalues; the spectrum is $H$ 's.
Writing $e_t$ as a combination of the eigenvectors of $H$ .

The spectrum belongs to the matrix. Decomposing a vector along it gives coordinates

c_k

, each of which gradient descent multiplies by its own factor

1-\alpha\lambda_k

In the figure, raising the momentum $\beta$ from 0 to 0.9 shifts the heavy-ball curve but leaves its slope at about $-\zeta$ . Why?

With constant $\alpha,\beta$ , slow directions behave like gradient descent with step $\alpha/(1-\beta)$ : a constant-factor speed-up, same exponent.
Momentum has no effect on quadratics.It moves the curve by a factor of about ten.

On a log-log plot, multiplying time by a constant shifts the curve sideways without changing its slope. Changing the exponent needs step sizes and momenta that change with

t

Practice

From ν and κ to ζBuild a power law

Let $\lambda_k=k^{-\nu}$ and $\lambda_kc_k(0)^2=k^{-1-\kappa}$ . Show that $\sum_{\lambda_k\le\lambda}\lambda_kc_k(0)^2\approx\lambda^{\kappa/\nu}$ , so $\zeta=\kappa/\nu$ .

Solution

$\lambda_k\le\lambda$ iff $k\ge\lambda^{-1/\nu}$ . The tail $\sum_{k\ge k_0}k^{-1-\kappa}\approx k_0^{-\kappa}/\kappa$ , and $k_0^{-\kappa}=\lambda^{\kappa/\nu}$ . This is how the figure builds its problem: for given $\nu$ and $\zeta$ it sets $\kappa=\zeta\nu$ .

Momentum per directionComplex eigenvalues

For one eigen-direction, heavy ball is $c_{t+1}=(1+\beta-\alpha\lambda)c_t-\beta c_{t-1}$ . Write it as $\begin{pmatrix}c_{t+1}\\c_t\end{pmatrix}=M\begin{pmatrix}c_t\\c_{t-1}\end{pmatrix}$ , and find when $M$ 's eigenvalues are complex. What is their modulus then?

Solution

$M=\begin{pmatrix}1+\beta-\alpha\lambda&-\beta\\1&0\end{pmatrix}$ with characteristic polynomial $\mu^2-(1+\beta-\alpha\lambda)\mu+\beta$ . The roots are complex when $(1+\beta-\alpha\lambda)^2<4\beta$ , and then both have modulus $\sqrt\beta$ (their product is $\beta$ ). In that regime the coordinate spirals in at rate $\sqrt\beta$ per step, whatever $\lambda$ is: this is how momentum speeds up the flat directions.