Machine Learning · Lecture 2

Lecture 2
The Toolkit: Geometry, Linear Algebra, Gradients

Part I · Foundations of supervised learning  |  vectors and dot products, projections, matrices as maps, rank, eigenvectors and the spectral theorem, the singular value decomposition, gradients and Hessians, gradient descent, line search, momentum, Newton's method, stochastic gradient descent, Adam  |  reading: Deisenroth, Faisal & Ong, Mathematics for Machine Learning, ch. 2–5 and 7; Prince, Understanding Deep Learning, ch. 6; Strang, Linear Algebra and Learning from Data

Cartoon: a walker on a foggy hillsideA stick figure stands on the slope of a hill, unable to see the valley. It says: I can't see the bottom. A second figure at the foot of the hill says: feel which way is steepest, and take a small step the other way. I can't see the bottom. Feel which way is steepestand step the other way.
Gradient descent: you never see the whole landscape, only the slope under your feet
In this lecture
  1. Data as vectors
  2. Projection: the closest point on a line
  3. Matrices are maps
  4. Eigenvectors and the spectral theorem
  5. The singular value decomposition
  6. Calculus in many variables
  7. Walking downhill: gradient descent, line search, momentum, Newton and Adam
  8. Summary, exercises, projects, reading

Lecture 1 described learning as choosing a predictor that makes the training error small. To do that with real models we need two kinds of mathematics. The first is geometry: a penguin with four measurements is a point in four-dimensional space, a dataset is a cloud of such points, and a linear model is a map from one space to another. Linear algebra is the language for this, and three of its ideas, projection, eigenvectors and the singular value decomposition, appear in almost every lecture that follows. The second is calculus: the training error is a function of the model's parameters, and to make it small we follow its slope downhill. Gradient descent, in one form or another, trains nearly every model in modern machine learning.

By the end of this lecture you should be able to compute and interpret dot products, lengths, angles and projections; read a matrix as a map and say what its rank and determinant mean; state the spectral theorem and use it on a covariance matrix; explain the singular value decomposition and why truncating it gives the best low-rank approximation; compute gradients and Hessians of simple loss functions and check them numerically; and run gradient descent, choose its step size by hand or by line search, explain why badly scaled features slow it down, and explain how momentum, Newton's method, stochastic gradient descent and Adam each respond to that problem.

1 — Data as vectors

Each penguin of Lecture 1 is a list of four numbers: bill length, bill depth, flipper length and body mass. We treat such a list as a vector, an arrow from the origin to a point in \(\mathbb R^4\). Stacking the 342 penguins as rows gives the data matrix \(X\), with 342 rows and 4 columns.

definition 2.1 — dot product, length, angle

For vectors \(u,v\in\mathbb R^d\), the dot product (or inner product) is

$$\langle u,v\rangle=u^\top v=\sum_{j=1}^d u_jv_j.$$

The length (Euclidean norm) is \(\|u\|=\sqrt{\langle u,u\rangle}\).

The angle \(\theta\) between non-zero vectors is defined by

$$\cos\theta=\frac{\langle u,v\rangle}{\|u\|\,\|v\|},$$

called the cosine similarity of \(u\) and \(v\). Vectors are orthogonal when \(\langle u,v\rangle=0\).

In two or three dimensions this is the angle you can see; in higher dimensions it is a definition, and it only makes sense because the right-hand side always lies between \(-1\) and \(1\).

proposition 2.1 — Cauchy–Schwarz inequality

For all \(u,v\in\mathbb R^d\),

$$|\langle u,v\rangle|\le\|u\|\,\|v\|,$$

with equality exactly when one vector is a multiple of the other.

If \(v=0\) both sides are 0. Otherwise, for every real \(t\),

$$0\le\|u-tv\|^2=\|u\|^2-2t\langle u,v\rangle+t^2\|v\|^2.$$

A quadratic in \(t\) that is never negative has discriminant \(\le0\):

$$4\langle u,v\rangle^2-4\|u\|^2\|v\|^2\le0.$$

Equality holds exactly when the quadratic has a root, i.e. \(u=tv\) for some \(t\). \(\square\)

Distances and angles depend on the units of each coordinate, as Lecture 1 found with kNN, so we first standardise each column. Then we can ask how similar two penguins are.

code — penguins as vectors
import numpy as np
from palmerpenguins import load_penguins

cols = ['bill_length_mm', 'bill_depth_mm', 'flipper_length_mm', 'body_mass_g']
df = load_penguins().dropna(subset=cols).reset_index(drop=True)
X = df[cols].to_numpy()                            # the data matrix: one penguin per row
Z = (X - X.mean(axis=0)) / X.std(axis=0)           # standardise each column
print('X has shape', X.shape)

def cosine(u, v):
    return u @ v / (np.linalg.norm(u) * np.linalg.norm(v))

g = df.index[df.species == 'Gentoo'][0]
c = df.index[df.species == 'Chinstrap'][0]
print(df.loc[[0, 1, g, c], ['species'] + cols].to_string())
print('cos(Adelie 0, Adelie 1)  =', round(cosine(Z[0], Z[1]), 3))
print('cos(Adelie 0, Gentoo)    =', round(cosine(Z[0], Z[g]), 3))
print('cos(Adelie 0, Chinstrap) =', round(cosine(Z[0], Z[c]), 3))
X has shape (342, 4)
       species  bill_length_mm  bill_depth_mm  flipper_length_mm  body_mass_g
0       Adelie            39.1           18.7              181.0       3750.0
1       Adelie            39.5           17.4              186.0       3800.0
151     Gentoo            46.1           13.2              211.0       4500.0
274  Chinstrap            46.5           17.9              192.0       3500.0
cos(Adelie 0, Adelie 1)  = 0.942
cos(Adelie 0, Gentoo)    = -0.744
cos(Adelie 0, Chinstrap) = 0.532

The two Adélie penguins point in almost the same direction (cosine 0.942). The Gentoo points nearly the opposite way (−0.744): after standardising, an Adélie is short-billed, deep-billed, short-flippered and light, and a Gentoo is the reverse in all four. The Chinstrap is in between. Cosine similarity is how modern systems compare text and images: each item becomes a long vector (an embedding), and "similar" means "small angle".

spot check 2.1

Compute \(\langle u,v\rangle\) for \(u=(1,2,3)\) and \(v=(4,-5,6)\).

Multiply matching coordinates and add: \(1\cdot4+2\cdot(-5)+3\cdot6\).
\(4-10+18=12\). The sign tells you the angle is less than 90°.
notation you will see in papers
\(x\in\mathbb R^d\), \(\mathbf x\), \(x^\top\)
vectors are columns; \(x^\top\) is the row. Many papers write vectors in bold lower case and matrices in bold upper case.
\(\langle x,y\rangle\), \(x^\top y\), \(x\cdot y\)
three spellings of the dot product.
\(\|x\|_2\), \(\|x\|_1\), \(\|A\|_F\), \(\|A\|_2\)
Euclidean length; sum of absolute values; the Frobenius norm \(\sqrt{\sum_{ij}A_{ij}^2}\); the operator norm, the largest singular value.
\(A\in\mathbb R^{m\times n}\), \(A^{-1}\), \(A^{\dagger}\), \(\operatorname{tr}A\), \(\operatorname{diag}(\lambda)\)
an \(m\times n\) matrix; inverse; pseudo-inverse; trace (sum of the diagonal); the diagonal matrix with entries \(\lambda_1,\dots,\lambda_d\).
\(\nabla_\theta\mathcal L\), \(\partial\mathcal L/\partial\theta\), \(\nabla^2 f\), \(J\)
gradient of a loss with respect to parameters \(\theta\); the same; the Hessian; a Jacobian.
\(\odot\), \(\otimes\), \(\mathbf 1\)
entrywise (Hadamard) product; tensor (Kronecker) product; the vector of all ones.

2 — Projection: the closest point on a line

Here is a question that will turn out to be linear regression in disguise. Given a vector \(y\) and a direction \(x\), what multiple of \(x\) is closest to \(y\)? Drop a perpendicular from the tip of \(y\) to the line through \(x\). Where it lands is the projection.

theorem 2.2 — projection onto a line

Let \(x\ne0\). Among all multiples \(tx\), the one closest to \(y\) is \(p=\beta x\) with

$$\beta=\frac{\langle x,y\rangle}{\langle x,x\rangle},$$

and the residual \(r=y-p\) is orthogonal to \(x\). Moreover \(\|y\|^2=\|p\|^2+\|r\|^2\).

With \(r=y-\beta x\),

$$\langle x,r\rangle=\langle x,y\rangle-\beta\langle x,x\rangle=0$$

by the choice of \(\beta\). For any other multiple, \(y-tx=r+(\beta-t)x\), and since \(r\perp x\), Pythagoras gives

$$\|y-tx\|^2=\|r\|^2+(\beta-t)^2\|x\|^2,$$

which is smallest exactly when \(t=\beta\). Taking \(t=0\) gives

$$\|y\|^2=\|r\|^2+\beta^2\|x\|^2=\|r\|^2+\|p\|^2.\qquad\square$$

Projection by hand

Drag the tips of \(x\) (amber) and \(y\) (sky). The moss arrow is the projection \(p\) of \(y\) onto the line through \(x\); the dashed rose segment is the residual, always at a right angle to \(x\).

Now apply this to penguins. Centre flipper length and body mass (subtract their means) to get vectors \(x_c\) and \(y_c\) in \(\mathbb R^{342}\), one coordinate per penguin. Projecting \(y_c\) onto \(x_c\) finds the multiple \(\beta x_c\) closest to \(y_c\), that is, the slope \(\beta\) that minimises \(\sum_i(y_{c,i}-\beta x_{c,i})^2\). That is the least-squares slope of the line through the scatter plot.

code — regression is projection
x = df['flipper_length_mm'].to_numpy()
y = df['body_mass_g'].to_numpy()
xc, yc = x - x.mean(), y - y.mean()        # centre both vectors

beta = (xc @ yc) / (xc @ xc)               # coefficient of the projection of yc onto xc
p = beta * xc                              # the projection
r = yc - p                                 # what is left over: the residual
print('beta =', round(beta, 3), 'grams per mm')
print(f'residual . xc = {r @ xc:.1e}  (zero up to rounding: orthogonal)')
print('np.polyfit slope =', round(np.polyfit(x, y, 1)[0], 3))
print('cosine of the angle between xc and yc =', round(cosine(xc, yc), 4))
print('correlation of x and y                =', round(np.corrcoef(x, y)[0, 1], 4))
beta = 49.686 grams per mm
residual . xc = -1.1e-10  (zero up to rounding: orthogonal)
np.polyfit slope = 49.686
cosine of the angle between xc and yc = 0.8712
correlation of x and y                = 0.8712

Each extra millimetre of flipper goes with about 49.7 g of extra mass, the same slope np.polyfit finds by least squares. The last two lines show something worth remembering: the cosine of the angle between two centred vectors is their correlation. A correlation of 0.87 means that, in 342-dimensional space, the flipper and mass vectors are only about 29° apart. Lecture 3 extends this from one direction to many: least squares with several features is projection onto the plane (or higher-dimensional subspace) they span.

spot check 2.2

Two centred variables have correlation \(0\). What does that say about their centred data vectors?

Correlation of centred vectors is the cosine of the angle between them.
Cosine 0 means a right angle, so \(\beta=0\): the best line has zero slope. That is all it means. A U-shaped relationship can have zero correlation and be perfectly predictable.

3 — Matrices are maps

A matrix \(A\) with \(m\) rows and \(n\) columns turns a vector \(v\in\mathbb R^n\) into \(Av\in\mathbb R^m\), and does so linearly: \(A(u+v)=Au+Av\) and \(A(tv)=tAv\). The \(j\)-th column of \(A\) is where the \(j\)-th coordinate vector \(e_j\) goes, so \(Av=\sum_jv_j\,(\text{column } j)\) is a combination of the columns. Two examples run through the whole course:

definition 2.2 — column space, rank, inverse, determinant

The column space of \(A\) is the set of all \(Av\): every combination of its columns. Its dimension is the rank of \(A\), the number of independent directions \(A\) can reach.

A square \(n\times n\) matrix is invertible when it has rank \(n\); then there is a unique \(A^{-1}\) with \(A^{-1}A=AA^{-1}=I\).

For a \(2\times2\) matrix

$$\begin{pmatrix}a&b\\c&d\end{pmatrix},$$

the determinant \(ad-bc\) is the factor by which \(A\) scales areas (negative if it flips orientation), and \(A\) is invertible exactly when the determinant is non-zero.

A 2×2 matrix as a map of the plane

The faint dashed circle and square are the unit circle and unit square; the sky ellipse and amber parallelogram are their images under \(A\). The amber and rose arrows are the columns of \(A\), where \(e_1\) and \(e_2\) go. Turn on eigenvectors (moss lines: directions \(A\) only stretches) or singular directions (plum: the axes of the ellipse).

Try the presets. A rotation keeps every length, has determinant 1, and has no real eigenvectors: no direction is left pointing the same way. A shear has determinant 1 too, but stretches some directions and squashes others. The rank-1 preset squashes the whole plane onto a line: the ellipse collapses to a segment, the determinant is 0, and no inverse can undo the collapse because many inputs land on the same output.

Rank deficiency is not exotic. It happens whenever one column of a data matrix can be computed from the others. Record body mass twice, once in grams and once in kilograms:

code — a duplicated feature makes a matrix rank-deficient
ones = np.ones(len(df))
M = np.column_stack([ones, X, df['body_mass_g'] / 1000])  # intercept, 4 features, and mass again in kg
print('M has shape', M.shape, 'and rank', np.linalg.matrix_rank(M))
print(f'condition number of M^T M with the duplicate:    {np.linalg.cond(M.T @ M):.2e}')
M5 = M[:, :5]
print(f'condition number of M^T M without the duplicate: {np.linalg.cond(M5.T @ M5):.2e}')
M has shape (342, 6) and rank 5
condition number of M^T M with the duplicate:    1.83e+21
condition number of M^T M without the duplicate: 1.77e+10

Six columns, rank 5: the kilogram column adds no new direction. The condition number of a matrix, the ratio of its largest to its smallest singular value (Section 5), measures how close it is to losing rank, and how much it amplifies rounding errors when inverted. At \(10^{21}\) the matrix \(M^\top M\) is singular for all practical purposes. Even without the duplicate it is \(10^{10}\), because the columns live on wildly different scales (bill depth near 17, body mass near 4000). Lecture 3 needs to invert exactly this matrix, and Section 7 shows that the same ill-conditioning slows gradient descent.

spot check 2.3

By what factor does \(B=\begin{pmatrix}3&0\\4&5\end{pmatrix}\) scale areas? The widget's sliders stop at 2, so compute this one by hand.

The area factor is \(|ad-bc|\).
\(3\cdot5-0\cdot4=15\). The unit square becomes a parallelogram of area 15.

4 — Eigenvectors and the spectral theorem

Most directions are turned by a matrix. The special ones that are not are its eigenvectors.

definition 2.3 — eigenvalue and eigenvector

A non-zero vector \(q\) is an eigenvector of a square matrix \(A\), with eigenvalue \(\lambda\), if \(Aq=\lambda q\): \(A\) only stretches \(q\), by the factor \(\lambda\) (flipping it if \(\lambda<0\)).

The eigenvalues are the roots of

$$\det(A-\lambda I)=0.$$

In the widget, the symmetric preset has two moss eigenvector lines at right angles to each other, and they line up with the axes of the ellipse. Move \(b\) and \(c\) apart and the eigenvectors stop being perpendicular. Symmetric matrices are special, and luckily they are the ones machine learning meets most: covariance matrices, Hessians, kernel matrices and graph Laplacians are all symmetric.

theorem 2.3 — spectral theorem for real symmetric matrices

If \(S\) is a real symmetric \(d\times d\) matrix (\(S^\top=S\)), then all its eigenvalues \(\lambda_1,\dots,\lambda_d\) are real and it has an orthonormal basis of eigenvectors \(q_1,\dots,q_d\). Equivalently,

$$S=Q\Lambda Q^\top=\sum_{i=1}^d\lambda_i\,q_iq_i^\top,\qquad Q^\top Q=I,\quad \Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_d).$$

In the eigenvector coordinates, \(S\) is just a stretch along each axis.

The \(2\times2\) case. Let

$$S=\begin{pmatrix}a&b\\b&c\end{pmatrix}.$$

Its characteristic polynomial \(\lambda^2-(a+c)\lambda+(ac-b^2)\) has discriminant

$$(a+c)^2-4(ac-b^2)=(a-c)^2+4b^2\ge0,$$

so both roots are real. If \(b=0\), \(S\) is already diagonal. If \(b\ne0\), the discriminant is positive and the eigenvalues \(\lambda_1\ne\lambda_2\) are distinct.

For eigenvectors \(u,v\), symmetry gives

$$\lambda_1\langle u,v\rangle=\langle Su,v\rangle=\langle u,Sv\rangle=\lambda_2\langle u,v\rangle,$$

so \((\lambda_1-\lambda_2)\langle u,v\rangle=0\) and \(u\perp v\). Normalise them to length 1.

General case (sketch). The same symmetry argument shows that eigenvectors for different eigenvalues are orthogonal, and a short argument with complex numbers shows that eigenvalues are real.

For existence, maximise \(u^\top Su\) over unit vectors \(u\) (a continuous function on a closed bounded set, so the maximum is attained); a Lagrange-multiplier argument (Lecture 7) shows the maximiser \(q_1\) is an eigenvector. Symmetry implies \(S\) maps the subspace orthogonal to \(q_1\) into itself, so repeat inside that \((d-1)\)-dimensional subspace.

Full proofs: Strang (2019), Section I.6; Deisenroth et al. (2020), Section 4.4. \(\square\)

The most important symmetric matrix in statistics is the covariance matrix. For a centred data matrix \(X_c\) (each column has mean 0), \(S=\frac1nX_c^\top X_c\) has the variances on its diagonal and the covariances off it. For standardised data it is the correlation matrix.

code — the eigenvectors of the penguin covariance matrix
S = Z.T @ Z / len(Z)                       # covariance of the standardised data (= the correlation matrix)
print(np.round(S, 3))
lam, Q = np.linalg.eigh(S)                 # eigh: for symmetric matrices; eigenvalues in increasing order
lam, Q = lam[::-1], Q[:, ::-1]             # largest first
print('eigenvalues        ', np.round(lam, 3), ' sum =', round(lam.sum(), 3))
print('top eigenvector    ', np.round(Q[:, 0], 3))
print('Q^T Q = I ?        ', np.allclose(Q.T @ Q, np.eye(4)))
print('S = Q diag(lam) Q^T ?', np.allclose(Q @ np.diag(lam) @ Q.T, S))
[[ 1.    -0.235  0.656  0.595]
 [-0.235  1.    -0.584 -0.472]
 [ 0.656 -0.584  1.     0.871]
 [ 0.595 -0.472  0.871  1.   ]]
eigenvalues         [2.754 0.773 0.365 0.108]  sum = 4.0
top eigenvector     [-0.455  0.4   -0.576 -0.548]
Q^T Q = I ?         True
S = Q diag(lam) Q^T ? True

The eigenvalues add up to 4, the total variance of four standardised features (the trace is preserved). The top eigenvalue, 2.754, is 69% of the total: a single direction in feature space carries more than two-thirds of the variation among penguins. Its eigenvector weighs bill length, flipper length and body mass together, against bill depth, which is roughly "big penguin with a long, shallow bill" versus the opposite, or Gentoo versus Adélie. This is principal component analysis, and Lecture 16 develops it fully. The fact behind it is that \(u^\top Su\), the variance of the data along a unit direction \(u\), is largest along the top eigenvector (Exercise 10).

spot check 2.4

Which statements are true for every real symmetric matrix? Select all that apply.

Try the widget with \(b=c\), and try the matrix with rows \((1,1)\) and \((1,1)\).
Symmetry buys real eigenvalues and orthogonal eigenvectors. Positive eigenvalues need more: covariance matrices have eigenvalues \(\ge0\) because \(u^\top Su\) is a variance. Such matrices are called positive semi-definite.
quantum — this is the language of quantum mechanics

A qubit's state is a unit vector in \(\mathbb C^2\), written \(|\psi\rangle=\alpha|0\rangle+\beta|1\rangle\) in Dirac notation: kets \(|\psi\rangle\) are column vectors, bras \(\langle\psi|\) are their conjugate transposes (rows), and \(\langle\varphi|\psi\rangle\) is the inner product. Three ideas from this lecture are the whole mathematical skeleton of quantum computing:

With \(n\) qubits the state is a vector in \(\mathbb C^{2^n}\), built by tensor products. That exponential dimension is the source of both quantum computing's promise and the cost of simulating it classically.

spot check 2.5

A qubit is in the state \(|\psi\rangle=\tfrac35|0\rangle+\tfrac45|1\rangle\). With what probability does measuring it give 0?

Project onto \(|0\rangle\) and square the length.
\(|\langle0|\psi\rangle|^2=(3/5)^2=0.36\), and outcome 1 has probability \(0.64\). The two add to \(\|\psi\|^2=1\), which is Pythagoras (Theorem 2.2).

5 — The singular value decomposition

The spectral theorem needs a square, symmetric matrix. The singular value decomposition works for every matrix, square or not, and says that every linear map is a rotation, then a stretch along the axes, then another rotation. In the widget, turn on singular directions: the plum axes of the ellipse are the stretched directions, and their lengths are the singular values.

definition 2.4 — singular value decomposition (SVD)

Every real \(m\times n\) matrix \(A\) of rank \(r\) can be written

$$A=U\Sigma V^\top=\sum_{i=1}^r\sigma_i\,u_iv_i^\top,$$

where \(u_1,\dots,u_r\in\mathbb R^m\) are orthonormal (the left singular vectors), \(v_1,\dots,v_r\in\mathbb R^n\) are orthonormal (the right singular vectors), and \(\sigma_1\ge\sigma_2\ge\dots\ge\sigma_r>0\) are the singular values.

Each term \(\sigma_iu_iv_i^\top\) is a rank-one matrix, a "layer" of \(A\). The map sends \(v_i\) to \(\sigma_iu_i\).

theorem 2.4 — the SVD exists

Every real matrix has a singular value decomposition, and its singular values are the square roots of the non-zero eigenvalues of \(A^\top A\).

\(A^\top A\) is symmetric, so by the spectral theorem \(A^\top A=V\Lambda V^\top\) with orthonormal \(v_i\). Its eigenvalues are non-negative:

$$\lambda_i=v_i^\top A^\top Av_i=\|Av_i\|^2\ge0.$$

Exactly \(r\) of them are positive, where \(r\) is the rank of \(A\). For those, set \(\sigma_i=\sqrt{\lambda_i}\) and \(u_i=Av_i/\sigma_i\). These \(u_i\) are orthonormal:

$$u_i^\top u_j=\frac{v_i^\top A^\top Av_j}{\sigma_i\sigma_j}=\frac{\lambda_j\,v_i^\top v_j}{\sigma_i\sigma_j}=\begin{cases}1&i=j\\0&i\ne j.\end{cases}$$

By construction \(Av_i=\sigma_iu_i\) for \(i\le r\), and \(Av_i=0\) for the remaining \(v_i\) (since \(\|Av_i\|^2=\lambda_i=0\)).

A matrix is determined by what it does to a basis, and \(\sum_i\sigma_iu_iv_i^\top\) does the same thing to every \(v_j\), so the two are equal. \(\square\)

The layers come in order of importance: \(\sigma_1u_1v_1^\top\) is the single rank-one matrix that captures the most of \(A\), and so on. Keeping the first \(k\) layers gives the best possible approximation of rank \(k\).

theorem 2.5 — Eckart–Young (statement)

Let

$$A_k=\sum_{i=1}^k\sigma_iu_iv_i^\top.$$

For every matrix \(B\) of rank at most \(k\),

$$\|A-B\|_F\ \ge\ \|A-A_k\|_F=\sqrt{\sigma_{k+1}^2+\dots+\sigma_r^2}.$$

The error of the best rank-\(k\) approximation is made of exactly the singular values you throw away.

(Proof in Lecture 16, where this theorem underlies PCA.)

A greyscale photograph is a matrix of pixel brightnesses, so we can watch the layers build it up.

data — a public-domain photograph

NASA's official portrait of astronaut Eileen Collins, the first woman to pilot and later command a Space Shuttle. Works of NASA are in the public domain; the image ships with scikit-image as skimage.data.astronaut(). We convert it to greyscale (512×512); the widget uses a 256×256 version.

An image, one layer at a time

Right: the rank-\(k\) approximation \(A_k\). Left: the original. Below: the singular values on a log scale; the ones to the right of the marker are thrown away.

One layer gives a blurry cross of light and dark bands, because a rank-one matrix \(\sigma_1u_1v_1^\top\) is an outer product: every row is a multiple of the same row pattern. By \(k=20\) the face is recognisable, and the approximation stores only \(k(m+n+1)\) numbers instead of \(mn\).

code — low-rank approximation of the 512×512 photograph
from skimage import data, color

A = color.rgb2gray(data.astronaut())       # 512 x 512 grey levels in [0, 1]
U, s, Vt = np.linalg.svd(A, full_matrices=False)
print('A is', A.shape, '; largest singular values', np.round(s[:4], 2))
for k in [1, 5, 20, 50, 100]:
    Ak = (U[:, :k] * s[:k]) @ Vt[:k]       # sum of the first k rank-one layers
    err = np.linalg.norm(A - Ak) / np.linalg.norm(A)
    formula = np.sqrt((s[k:] ** 2).sum() / (s ** 2).sum())   # Eckart-Young: the discarded singular values
    storage = k * (A.shape[0] + A.shape[1] + 1) / A.size
    print(f'k = {k:3d}: relative error {err:.4f} (formula {formula:.4f}), storage {storage:5.1%}')
A is (512, 512) ; largest singular values [241.26  71.12  45.98  38.01]
k =   1: relative error 0.4632 (formula 0.4632), storage  0.4%
k =   5: relative error 0.2917 (formula 0.2917), storage  2.0%
k =  20: relative error 0.1473 (formula 0.1473), storage  7.8%
k =  50: relative error 0.0807 (formula 0.0807), storage 19.6%
k = 100: relative error 0.0427 (formula 0.0427), storage 39.1%

The measured errors agree with the Eckart–Young formula to every printed digit. The first singular value is more than three times the second: most of the image's "energy" is in its overall layout, and the fine detail is spread thinly over hundreds of small layers.

spot check 2.6

The widget's image is 256×256. What fraction of the original storage does a rank-20 approximation need? (Give a decimal.)

Each layer stores \(u_i\) (256 numbers), \(v_i\) (256 numbers) and \(\sigma_i\) (1 number).
\(20\times513/65536\approx0.157\). A rank-\(k\) approximation saves storage only while \(k<mn/(m+n+1)\), here about 128.
history — the singular value decomposition

The SVD was discovered twice in two years, by Eugenio Beltrami in 1873 and Camille Jordan in 1874, as a fact about bilinear forms. Its use for approximation came from psychology: in 1936 Carl Eckart and Gale Young, working on the analysis of mental-test scores, proved the best low-rank approximation theorem above. For decades the SVD was hard to compute reliably; Gene Golub and William Kahan's 1965 algorithm, refined by Golub and Christian Reinsch in 1970, made it routine, and descendants of it run inside np.linalg.svd today.

big picture — matrix multiplication runs machine learning

Almost all the arithmetic in modern machine learning is matrix multiplication. A neural network layer multiplies a matrix of weights by a matrix of inputs; attention in a transformer (Lecture 12) is three more matrix products. GPUs and Google's TPUs are, at heart, machines for multiplying matrices quickly. Low rank appears at that scale too. LoRA (Hu et al., 2022), a standard way to adapt a large language model to a new task, freezes each huge weight matrix \(W\) and learns only a low-rank correction, \(W+BA\) with \(B\) and \(A\) of rank 8 to 64. That cuts the number of trained parameters by a factor of thousands, on the bet that the needed change has low rank, which is the Eckart–Young idea applied to fine-tuning.

6 — Calculus in many variables

A loss function takes a parameter vector \(w\in\mathbb R^d\) and returns a number. To make it small we need to know how it changes when we nudge \(w\), in every direction at once.

definition 2.5 — gradient, Hessian, Jacobian

For \(f:\mathbb R^d\to\mathbb R\), the partial derivative \(\partial f/\partial w_j\) is the derivative in \(w_j\) with the other coordinates held fixed. The gradient is the vector of partial derivatives,

$$\nabla f(w)=\Big(\frac{\partial f}{\partial w_1},\dots,\frac{\partial f}{\partial w_d}\Big)^\top,$$

and the Hessian is the symmetric \(d\times d\) matrix of second derivatives,

$$\big(\nabla^2f(w)\big)_{jk}=\partial^2f/\partial w_j\partial w_k.$$

For a vector-valued map \(g:\mathbb R^d\to\mathbb R^m\), the Jacobian \(J_g\) is the \(m\times d\) matrix with entries \(\partial g_i/\partial w_j\).

The gradient packages all the slopes into one vector, and that vector has a geometric meaning: it points uphill, as steeply as possible.

proposition 2.6 — the gradient is the direction of steepest ascent

For a differentiable \(f\) and a unit vector \(u\), the rate of change of \(f\) at \(w\) in direction \(u\) is \(\langle\nabla f(w),u\rangle\).

It is largest when \(u\) points along \(\nabla f(w)\), smallest when \(u\) points along \(-\nabla f(w)\), and zero along directions orthogonal to the gradient (the contour lines).

By the chain rule,

$$\frac{d}{dt}f(w+tu)\big|_{t=0}=\sum_j\frac{\partial f}{\partial w_j}u_j=\langle\nabla f(w),u\rangle.$$

By Cauchy–Schwarz (Proposition 2.1) this lies between \(-\|\nabla f(w)\|\) and \(\|\nabla f(w)\|\), with the extremes exactly when

$$u=\pm\nabla f(w)/\|\nabla f(w)\|.\qquad\square$$

Two tools make computing gradients routine. The chain rule in many variables says that the Jacobian of a composition is the product of Jacobians, \(J_{g\circ h}(w)=J_g(h(w))\,J_h(w)\): derivatives of composed maps multiply like the maps themselves. Backpropagation (Lecture 10) is nothing more than this rule applied efficiently. And Taylor's theorem describes \(f\) near a point \(w\):

$$f(w+\delta)\approx f(w)+\nabla f(w)^\top\delta+\tfrac12\,\delta^\top\nabla^2f(w)\,\delta.$$

The gradient gives the tilt of the landscape, the Hessian its curvature. The Hessian is symmetric, so by the spectral theorem it has orthogonal eigenvectors: the directions of greatest and least curvature.

example 2.1 — the gradient of least squares

Let \(X\) be an \(n\times d\) design matrix and \(f(w)=\frac1n\|Xw-y\|^2\). Find \(\nabla f\) and \(\nabla^2f\).

Write \(r=Xw-y\), so \(f=\frac1n\sum_ir_i^2\) and \(\partial r_i/\partial w_j=X_{ij}\). Then \(\frac{\partial f}{\partial w_j}=\frac2n\sum_ir_iX_{ij}\), which in matrix form is

$$\nabla f(w)=\tfrac2nX^\top(Xw-y),\qquad\nabla^2f(w)=\tfrac2nX^\top X.$$

The Hessian does not depend on \(w\): \(f\) is a quadratic, a bowl whose shape is set by \(X^\top X\). Setting the gradient to zero gives the normal equations \(X^\top Xw=X^\top y\), the starting point of Lecture 3.

Whenever you derive a gradient by hand, check it numerically with finite differences, \(\partial f/\partial w_j\approx\big(f(w+he_j)-f(w-he_j)\big)/2h\). We fit body mass from flipper length again, now both standardised, with an intercept.

code — checking a gradient
xs = (x - x.mean()) / x.std()              # standardised flipper length
ys = (y - y.mean()) / y.std()              # standardised body mass
Xd = np.column_stack([np.ones_like(xs), xs])   # design matrix: a column of ones for the intercept

def loss(w):
    return np.mean((Xd @ w - ys) ** 2)

def grad(w):
    return 2 / len(ys) * Xd.T @ (Xd @ w - ys)

w, h = np.array([0.5, -1.0]), 1e-6
fd = np.array([(loss(w + h * e) - loss(w - h * e)) / (2 * h) for e in np.eye(2)])
print('analytic gradient ', np.round(grad(w), 6))
print('finite differences', np.round(fd, 6))
print('Hessian 2 X^T X / n =\n', np.round(2 / len(ys) * Xd.T @ Xd, 6) + 0.0)
analytic gradient  [ 1.       -3.742404]
finite differences [ 1.       -3.742404]
Hessian 2 X^T X / n =
 [[2. 0.]
 [0. 2.]]

The analytic and numerical gradients agree to six decimals. The Hessian is exactly \(2I\): with standardised features the bowl is perfectly round. Keep that in mind for Section 7.

spot check 2.7

For \(f(w_1,w_2)=w_1^2+3w_1w_2\), compute \(\partial f/\partial w_1\) at \((w_1,w_2)=(1,2)\).

Differentiate in \(w_1\) treating \(w_2\) as a constant: \(2w_1+3w_2\).
\(2+6=8\). The full gradient there is \((8,3)\), and the Hessian is \(\begin{pmatrix}2&3\\3&0\end{pmatrix}\), which has a negative eigenvalue, so \(f\) is saddle-shaped, not a bowl.

7 — Walking downhill: gradient descent, line search, momentum, Newton and Adam

Proposition 2.6 suggests an algorithm. Stand at \(w_0\); compute the gradient; take a small step against it; repeat.

definition 2.6 — gradient descent

Given a starting point \(w_0\) and a step size (learning rate) \(\eta>0\), gradient descent iterates

$$w_{t+1}=w_t-\eta\,\nabla f(w_t).$$

Whether this works depends on the shape of \(f\) and on \(\eta\). The cleanest guarantees come for convex functions.

definition 2.7 — convex and \(L\)-smooth

\(f\) is convex if the chord between any two points on its graph lies above the graph:

$$f\big((1-t)u+tv\big)\le(1-t)f(u)+tf(v)$$

for \(t\in[0,1]\). For twice-differentiable \(f\) this means the Hessian is positive semi-definite everywhere.

\(f\) is \(L\)-smooth if its gradient cannot change too fast:

$$\|\nabla f(u)-\nabla f(v)\|\le L\|u-v\|.$$

For a quadratic, \(L\) is the largest eigenvalue of the Hessian.

For a convex function every local minimum is a global minimum, so walking downhill cannot get stuck in the wrong valley. For a quadratic we can see exactly what gradient descent does.

proposition 2.7 — gradient descent on a quadratic

Let

$$f(w)=\frac12(w-w^*)^\top H(w-w^*)$$

with \(H\) symmetric and eigenvalues \(0<\lambda_{\min}\le\dots\le\lambda_{\max}\).

Gradient descent converges to \(w^*\) from every starting point if and only if

$$0<\eta<2/\lambda_{\max}.$$

The error along the eigenvector with eigenvalue \(\lambda\) is multiplied by \(1-\eta\lambda\) at every step.

\(\nabla f(w)=H(w-w^*)\), so the error \(e_t=w_t-w^*\) satisfies

$$e_{t+1}=e_t-\eta He_t=(I-\eta H)e_t,$$

and \(e_t=(I-\eta H)^te_0\). Write \(e_0=\sum_ic_iq_i\) in the orthonormal eigenvectors of \(H\) (spectral theorem). Then

$$e_t=\sum_ic_i(1-\eta\lambda_i)^tq_i.$$

Each term goes to zero exactly when \(|1-\eta\lambda_i|<1\), i.e. \(0<\eta\lambda_i<2\). This must hold for every \(i\), and the binding constraint is the largest eigenvalue: \(\eta<2/\lambda_{\max}\). \(\square\)

Two lessons follow. The step size is capped by the steepest direction: too large and the iterates overshoot and blow up. And with \(\eta\) set safely for \(\lambda_{\max}\), the flattest direction shrinks by only \(1-\eta\lambda_{\min}\approx1-\lambda_{\min}/\lambda_{\max}\) per step. The ratio \(\kappa=\lambda_{\max}/\lambda_{\min}\), the condition number of the Hessian, controls how slow gradient descent is: it needs on the order of \(\kappa\) steps for each factor of \(e\) in accuracy.

Five ways downhill

Contours of a loss surface: the more strongly shaded a band, the lower the loss. Click or tap to choose a starting point (rose). The amber path shows each step; the moss star is the minimum. The methods are introduced one by one below: try gradient descent first, and come back for the others.

Start with the round bowl. Any step size below 1 converges (\(\lambda_{\max}=2\)), and \(\eta=0.5\) lands on the minimum in one step, because \(1-\eta\lambda=0\) in every direction. Push \(\eta\) above 1 and the path zigzags outward. Now switch to the narrow valley: the same penguin regression, but with flipper length in units of 100 mm and mass in kilograms, not centred. The Hessian's eigenvalues are 10.1 and 0.0078, a condition number of about 1300. Gradient descent drops into the valley floor in a few steps and then crawls along it.

code — step sizes on the round bowl
w_star = np.linalg.solve(Xd.T @ Xd, Xd.T @ ys)    # the exact minimiser (Lecture 3)
print('exact w* =', np.round(w_star, 4), ' loss', round(loss(w_star), 4))
for eta in [0.05, 0.5, 0.9, 1.1]:
    w = np.zeros(2)
    for t in range(100):
        w = w - eta * grad(w)                       # one gradient-descent step
    print(f'eta = {eta:4}: after 100 steps w = {np.round(w, 4)}, loss {loss(w):.4g}')

H = 2 / len(ys) * Xd.T @ Xd
w = np.zeros(2)
w = w - np.linalg.solve(H, grad(w))                 # one Newton step
print('one Newton step from 0: w =', np.round(w, 4))
exact w* = [0.     0.8712]  loss 0.241
eta = 0.05: after 100 steps w = [0.     0.8712], loss 0.241
eta =  0.5: after 100 steps w = [0.     0.8712], loss 0.241
eta =  0.9: after 100 steps w = [0.     0.8712], loss 0.241
eta =  1.1: after 100 steps w = [        0.     -72151164.8971], loss 5.206e+15
one Newton step from 0: w = [0.     0.8712]
code — the price of a narrow valley
def steps_to_converge(D, t, eta, tol=1e-8, max_steps=200_000):
    w_opt = np.linalg.solve(D.T @ D, D.T @ t)
    f = lambda w: np.mean((D @ w - t) ** 2)
    w = np.zeros(2)
    for step in range(1, max_steps + 1):
        w = w - eta * 2 / len(t) * D.T @ (D @ w - t)
        if f(w) - f(w_opt) < tol:
            return step
    return None

Xu = np.column_stack([ones, x / 100])      # flipper in units of 100 mm, NOT centred
yu = y / 1000                              # mass in kg
for name, D, t in [('standardised', Xd, ys), ('uncentred   ', Xu, yu)]:
    ev = np.linalg.eigvalsh(2 / len(t) * D.T @ D)
    print(f'{name}: Hessian eigenvalues {np.round(ev, 4)}, condition number {ev[1] / ev[0]:8.1f}, '
          f'steps with eta = 1/L: {steps_to_converge(D, t, 1 / ev[1])}')
standardised: Hessian eigenvalues [2. 2.], condition number      1.0, steps with eta = 1/L: 1
uncentred   : Hessian eigenvalues [7.8000e-03 1.0105e+01], condition number   1294.8, steps with eta = 1/L: 10920

The same data and the same model need one step or 10,920 steps, depending only on how the features are scaled and centred. This is the optimisation reason to standardise features, and it is why so much of deep learning's toolkit (momentum and Adam later in this section, batch and layer normalisation in Lectures 10 and 11) amounts to coping with narrow valleys or reshaping them into rounder bowls.

For convex functions that are not quadratic, the guarantee looks similar.

theorem 2.8 — gradient descent on convex, smooth functions

Let \(f\) be convex and \(L\)-smooth with a minimiser \(w^*\). Gradient descent with step size \(\eta\le1/L\) satisfies

$$f(w_t)-f(w^*)\ \le\ \frac{\|w_0-w^*\|^2}{2\eta t}.$$

The gap closes at rate \(O(1/t)\): to halve it, double the number of steps.

Step 1: each step goes downhill. \(L\)-smoothness implies the quadratic upper bound

$$f(v)\le f(w)+\nabla f(w)^\top(v-w)+\frac L2\|v-w\|^2.$$

Put \(v=w^+=w-\eta\nabla f(w)\):

$$f(w^+)\le f(w)-\eta\big(1-\frac{L\eta}2\big)\|\nabla f(w)\|^2\le f(w)-\frac\eta2\|\nabla f(w)\|^2,$$

using \(\eta\le1/L\).

Step 2: compare with the minimum. Convexity means the tangent plane lies below the graph:

$$f(w^*)\ge f(w)+\nabla f(w)^\top(w^*-w).$$

Combining with step 1,

$$f(w^+)-f(w^*)\le\nabla f(w)^\top(w-w^*)-\tfrac\eta2\|\nabla f(w)\|^2=\tfrac1{2\eta}\Big(\|w-w^*\|^2-\|w^+-w^*\|^2\Big),$$

where the last equality is algebra: expand \(\|w-\eta\nabla f(w)-w^*\|^2\).

Step 3: telescope. Summing over \(t=0,\dots,T-1\), the right-hand sides cancel in pairs:

$$\sum_{t=1}^T\big(f(w_t)-f(w^*)\big)\le\frac1{2\eta}\|w_0-w^*\|^2.$$

By step 1 the values \(f(w_t)\) decrease, so the last term is the smallest, and \(T\big(f(w_T)-f(w^*)\big)\) is at most the sum. \(\square\)

spot check 2.8

A quadratic loss has Hessian eigenvalues 2 and 10. Above what step size does gradient descent diverge?

Proposition 2.7: the limit is \(2/\lambda_{\max}\).
\(2/10=0.2\). At that step size the flat direction (eigenvalue 2) shrinks by \(|1-0.4|=0.6\) per step, so it is not the bottleneck here; with a condition number of 5 this bowl is easy.

Choosing the step automatically: line search

Proposition 2.7 sets the step size from the Hessian's largest eigenvalue, which we rarely know. A line search chooses the step afresh at every iteration by looking along the direction \(-\nabla f(w_t)\) and asking how far to go. The ideal is an exact line search, \(\eta_t=\arg\min_{\eta>0}f\big(w_t-\eta\nabla f(w_t)\big)\), a one-dimensional minimisation.

proposition 2.9 — exact line search on a quadratic

For \(f(w)=\tfrac12w^\top Hw-b^\top w\) with \(H\) positive definite and gradient \(g_t=Hw_t-b\), the exact line-search step is

$$\eta_t=\frac{g_t^\top g_t}{g_t^\top Hg_t},$$

and consecutive gradients are orthogonal, \(g_{t+1}^\top g_t=0\): each step turns through a right angle.

Let \(\varphi(\eta)=f(w_t-\eta g_t)\). By the chain rule

$$\varphi'(\eta)=-g_t^\top\nabla f(w_t-\eta g_t)=-g_t^\top(g_t-\eta Hg_t),$$

which is zero at \(\eta=g_t^\top g_t/g_t^\top Hg_t\); \(\varphi\) is a convex parabola, so this is its minimum. At that \(\eta\), \(\varphi'(\eta)=-g_t^\top g_{t+1}=0\). \(\square\)

Exact minimisation along a line is rarely possible for real losses, so practical codes settle for a step that decreases \(f\) "enough". Backtracking starts from a trial step \(\eta_0\) and halves it until the Armijo condition \(f(w-\eta g)\le f(w)-\tfrac12\eta\|g\|^2\) holds.

proposition 2.10 — backtracking always stops, with a safe step

If \(f\) is \(L\)-smooth, the Armijo condition holds for every \(\eta\le1/L\).

So backtracking from \(\eta_0\) stops after finitely many halvings with a step

$$\eta\ge\min(\eta_0,\frac1{2L}),$$

and each iteration decreases \(f\) by at least

$$\frac12\min(\eta_0,\frac1{2L})\,\|\nabla f(w)\|^2.$$

Step 1 of the proof of Theorem 2.8 shows

$$f(w-\eta g)\le f(w)-\eta(1-\frac{L\eta}2)\|g\|^2\le f(w)-\frac\eta2\|g\|^2$$

whenever \(\eta\le1/L\). Halving from \(\eta_0\), the first trial step at or below \(1/L\) passes, and it is at least half of \(1/L\) (otherwise the previous trial, twice as large, would also have been at most \(1/L\) and passed). If \(\eta_0\le1/L\) the first trial passes. \(\square\)

No knowledge of \(L\) is needed to run the method; it adapts to the local curvature automatically.

code — line search on the narrow valley
D, t = Xu, yu                                       # the narrow valley from the previous box
H = 2 / len(t) * D.T @ D                            # its (constant) Hessian
b = 2 / len(t) * D.T @ t
w_opt = np.linalg.solve(H, b)
f = lambda w: np.mean((D @ w - t) ** 2)
g_of = lambda w: H @ w - b                          # the gradient

def run(update, tol=1e-8, max_steps=200_000):       # steps until the loss is within tol of the minimum
    w, state = np.zeros(2), {}
    for step in range(1, max_steps + 1):
        w = update(w, state)
        if f(w) - f(w_opt) < tol:
            return step
    return None

def exact_line_search(w, s):
    g = g_of(w)
    return w - (g @ g) / (g @ H @ g) * g            # the best step along -g, for a quadratic

def backtracking(w, s):
    g, eta = g_of(w), 1.0
    while f(w - eta * g) > f(w) - 0.5 * eta * (g @ g):   # Armijo: insist on enough decrease
        eta /= 2                                    # otherwise halve the step and try again
    return w - eta * g

print('fixed step 1/L          :', run(lambda w, s: w - g_of(w) / np.linalg.eigvalsh(H)[1]), 'steps')
print('exact line search       :', run(exact_line_search), 'steps')
print('backtracking line search:', run(backtracking), 'steps')
fixed step 1/L          : 10920 steps
exact line search       : 5 steps
backtracking line search: 2814 steps

Backtracking takes larger steps than \(1/L\) where the landscape allows, and needs about a quarter as many iterations, though each one costs a few extra function evaluations. Exact line search needs only 5 steps here, an effect of having just two dimensions: the path zig-zags between the valley walls and its floor, and with only two directions to alternate between, the zig-zag dies out quickly from these starting points. In many dimensions, steepest descent with exact line search still slows down in proportion to the condition number (its worst-case error factor per step is \(\big(\tfrac{\kappa-1}{\kappa+1}\big)^2\); Nocedal & Wright, 2006, Section 3.3). Try "gradient descent + backtracking line search" in the widget on the narrow valley.

spot check 2.9

For \(f(w)=\tfrac12(w_1^2+10w_2^2)\) at \(w=(1,1)\), what step does exact line search take? (Here \(H=\operatorname{diag}(1,10)\).)

\(g=(1,10)\), so \(g^\top g=1+100\) and \(g^\top Hg=1\cdot1^2+10\cdot10^2\).
\(101/1001\approx0.1009\), just above \(1/\lambda_{\max}=0.1\). The gradient is dominated by the steep direction, so the best step is set by it.

Momentum

In a narrow valley, gradient descent bounces between the walls while making slow progress along the floor. The bouncing components of successive gradients point in opposite directions; the along-the-floor components all point the same way. So average them. Momentum keeps a running "velocity" \(v\) that accumulates past gradients:

$$v_{t+1}=\beta v_t-\eta\nabla f(w_t),\qquad w_{t+1}=w_t+v_{t+1},$$

with \(0\le\beta<1\) (often 0.9). Equivalently \(w_{t+1}=w_t-\eta\nabla f(w_t)+\beta(w_t-w_{t-1})\): a gradient step plus a fraction of the last move, like a heavy ball rolling downhill. This is Polyak's heavy-ball method (1964).

theorem 2.11 — momentum on a quadratic

Let \(f\) be a quadratic whose Hessian has eigenvalues in \([\mu,L]\), and \(\kappa=L/\mu\). With

$$\eta=\frac4{(\sqrt L+\sqrt\mu)^2},\qquad\beta=\Big(\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\Big)^2,$$

the heavy-ball error shrinks asymptotically by the factor \(\dfrac{\sqrt\kappa-1}{\sqrt\kappa+1}\) per step, compared with \(\dfrac{\kappa-1}{\kappa+1}\) for gradient descent with its best fixed step.

The number of steps needed grows like \(\sqrt\kappa\) instead of \(\kappa\).

As in Proposition 2.7, work along one eigenvector of the Hessian, with eigenvalue \(\lambda\) and error \(e_t\). The update gives

$$e_{t+1}=(1+\beta-\eta\lambda)e_t-\beta e_{t-1},$$

a linear recurrence with characteristic equation

$$r^2-(1+\beta-\eta\lambda)r+\beta=0.$$

Its roots are complex (or equal) when

$$(1-\sqrt\beta)^2\le\eta\lambda\le(1+\sqrt\beta)^2,$$

and then both have modulus \(\sqrt\beta\), because the product of the roots is \(\beta\).

With the stated choices,

$$\sqrt\beta=\frac{\sqrt L-\sqrt\mu}{\sqrt L+\sqrt\mu},$$

and one checks

$$(1-\sqrt\beta)^2=\frac{4\mu}{(\sqrt L+\sqrt\mu)^2}=\eta\mu$$

and

$$(1+\sqrt\beta)^2=\frac{4L}{(\sqrt L+\sqrt\mu)^2}=\eta L.$$

So for every eigenvalue in \([\mu,L]\) the roots have modulus \(\sqrt\beta=\frac{\sqrt\kappa-1}{\sqrt\kappa+1}\), and every error component decays at that rate (with at most a linear factor in \(t\) at the two ends).

For gradient descent, the best fixed step \(2/(L+\mu)\) gives

$$\max_\lambda|1-\eta\lambda|=\frac{\kappa-1}{\kappa+1}.\qquad\square$$
code — momentum on the narrow valley
mu_, L_ = np.linalg.eigvalsh(H)
kappa = L_ / mu_
eta = 4 / (np.sqrt(L_) + np.sqrt(mu_)) ** 2         # the best fixed parameters for heavy-ball momentum
beta = ((np.sqrt(kappa) - 1) / (np.sqrt(kappa) + 1)) ** 2

def heavy_ball(eta, beta):
    def update(w, s):
        v = beta * s.get('v', np.zeros(2)) - eta * g_of(w)   # velocity: decayed old velocity plus a gradient step
        s['v'] = v
        return w + v
    return update

print(f'condition number {kappa:.0f}; error shrinks per step by {(kappa - 1) / (kappa + 1):.5f} (best gradient descent)'
      f' vs {(np.sqrt(kappa) - 1) / (np.sqrt(kappa) + 1):.5f} (best momentum)')
print(f'momentum, eta = {eta:.4f}, beta = {beta:.4f}:', run(heavy_ball(eta, beta)), 'steps')
print('momentum, eta = 1/L, beta = 0.9        :', run(heavy_ball(1 / L_, 0.9)), 'steps')
print('momentum, eta 0.1% larger than tuned   :', run(heavy_ball(1.001 * eta, beta), max_steps=20_000), 'steps (never within tolerance)')
print('momentum, eta = 0.35, beta = 0.9       :', run(heavy_ball(0.35, 0.9)), 'steps')
condition number 1295; error shrinks per step by 0.99846 (best gradient descent) vs 0.94592 (best momentum)
momentum, eta = 0.3747, beta = 0.8948: 307 steps
momentum, eta = 1/L, beta = 0.9        : 1016 steps
momentum, eta 0.1% larger than tuned   : None steps (never within tolerance)
momentum, eta = 0.35, beta = 0.9       : 189 steps

With the tuned parameters, momentum needs 307 steps instead of 10,920: about \(\sqrt{1295}\approx36\) times fewer, as the theorem predicts. With the common default \(\beta=0.9\) and step \(1/L\) it needs 1,016. The tuned values are optimal for the worst starting point, and they sit exactly on the edge of stability: make the step 0.1% larger and the method never converges, while \(\eta=0.35\), \(\beta=0.9\) happens to need only 189 steps from this start. Momentum rewards tuning and punishes overconfidence. In the widget, choose "momentum" on the narrow valley and watch the path overshoot the valley floor, swing back and then run along it. Nesterov's accelerated gradient method (1983), a small modification that evaluates the gradient at the look-ahead point \(w_t+\beta v_t\), achieves the same \(\sqrt\kappa\) improvement for every smooth, strongly convex function, not just quadratics.

spot check 2.10

A quadratic has condition number \(\kappa=100\). By what factor does the error shrink per step with optimally tuned momentum?

\((\sqrt\kappa-1)/(\sqrt\kappa+1)\) with \(\sqrt\kappa=10\).
\(9/11\approx0.818\), against \(99/101\approx0.980\) for the best gradient descent. To shrink the error a millionfold that is about 69 steps against 691 (Exercise 11).

Newton's method

Gradient descent uses only the slope. If we also know the curvature, we can do better: minimise the quadratic Taylor approximation exactly. Setting the gradient of \(f(w)+\nabla f(w)^\top\delta+\tfrac12\delta^\top\nabla^2f(w)\delta\) to zero gives \(\nabla f(w)+\nabla^2f(w)\,\delta=0\), so

$$w_{t+1}=w_t-\big(\nabla^2f(w_t)\big)^{-1}\nabla f(w_t).$$

For a quadratic the Taylor approximation is exact, so Newton's method reaches the minimum in one step from anywhere, whatever the condition number: it rescales every direction by its own curvature. Try it on the narrow valley. On the Rosenbrock function, which is not convex, Newton's method from the default start \((-1.5,2)\) reaches the minimum at \((1,1)\) in 6 steps, though not smoothly: at step 2 it leaps far outside the picture and the loss jumps to 752, because far from the minimum the quadratic model is a poor guide. Gradient descent needs a step size below 0.002 and about 10,000 steps to get within \(10^{-6}\) of the minimum, creeping along the curved valley floor.

So why does anyone use gradient descent? Cost. For \(d\) parameters the Hessian has \(d^2\) entries and solving with it costs about \(d^3\) operations. A modern neural network has \(d\) in the billions, so even storing the Hessian is impossible, while a gradient costs about as much as evaluating \(f\) (Lecture 10). Much of optimisation research is about getting some of Newton's benefit at gradient descent's price.

spot check 2.11

On a quadratic with condition number \(\kappa\), Newton's method converges in , and gradient descent with \(\eta=1/\lambda_{\max}\) needs a number of steps that grows .

Use Proposition 2.7 with \(\eta=1/\lambda_{\max}\) for the flattest direction.
Each gradient step shrinks the flattest error component by \(1-1/\kappa\), and \((1-1/\kappa)^{\kappa}\approx e^{-1}\). The narrow valley has \(\kappa\approx1300\) and needed 10,920 steps to reach a tolerance of \(10^{-8}\), in line with the estimate \(\kappa\ln(10^{8})/2\approx12{,}000\).

Stochastic gradient descent

The gradient of a training loss is an average over training examples, \(\nabla\hat R(w)=\frac1n\sum_i\nabla\ell_i(w)\). With millions of examples, computing it exactly for every step is wasteful. Stochastic gradient descent (SGD) estimates it from a small random minibatch \(B\) of examples: \(g=\frac1{|B|}\sum_{i\in B}\nabla\ell_i(w)\). This estimate is unbiased, its expected value is the true gradient, but noisy. One pass through the data is called an epoch.

code — minibatch SGD on the penguin regression
rng = np.random.default_rng(0)
w = np.zeros(2)
for epoch in range(1, 6):
    for batch in np.array_split(rng.permutation(len(ys)), len(ys) // 10):   # minibatches of about 10 penguins
        g = 2 / len(batch) * Xd[batch].T @ (Xd[batch] @ w - ys[batch])      # gradient on the batch only
        w = w - 0.05 * g
    print(f'epoch {epoch}: w = {np.round(w, 4)}, loss on all data {loss(w):.5f}')
print('optimum loss', round(loss(w_star), 5))
epoch 1: w = [-0.0232  0.8613], loss on all data 0.24164
epoch 2: w = [0.0462 0.8498], loss on all data 0.24360
epoch 3: w = [-0.036   0.8852], loss on all data 0.24250
epoch 4: w = [0.0232 0.921 ], loss on all data 0.24403
epoch 5: w = [0.0394 0.8473], loss on all data 0.24314
optimum loss 0.24101

After one epoch, about 34 small steps, SGD is already within 0.3% of the optimal loss. Then it stops improving and jitters: with a fixed step size, the noise in each minibatch gradient keeps kicking \(w\) around the minimum. The standard cure is to shrink the step size over time; Robbins and Monro (1951) showed that step sizes with \(\sum_t\eta_t=\infty\) and \(\sum_t\eta_t^2<\infty\), such as \(\eta_t\propto1/t\), make the iterates converge. In deep learning the noise is also thought to help, by steering training toward wide, flat minima that generalise well (Lecture 10).

spot check 2.12

Why does the SGD loss in the code box bounce around 0.242–0.244 instead of settling at 0.241?

What would happen to the bouncing if the step size shrank over time?
The size of the cloud scales with the step size times the gradient noise. Decaying the step size, or growing the batch size, shrinks it.

Adaptive step sizes: AdaGrad, RMSProp and Adam

Newton's method rescales each direction by its own curvature, at a cost of \(O(d^3)\). Adaptive methods do something much cheaper: they rescale each coordinate by an estimate of how large its gradients typically are. A coordinate whose gradients are consistently large gets a small step; one whose gradients are small gets a large step. AdaGrad (Duchi, Hazan & Singer, 2011) divides by the root of the sum of all past squared gradients; RMSProp (Hinton, 2012) uses an exponentially weighted average instead, so old gradients are forgotten; and Adam combines RMSProp with momentum.

definition 2.8 — Adam (Kingma & Ba, 2015)

With \(g_k\) the (minibatch) gradient at step \(k\), all operations taken coordinate by coordinate, and \(m_0=v_0=0\):

$$m_k=\beta_1m_{k-1}+(1-\beta_1)g_k,\qquad v_k=\beta_2v_{k-1}+(1-\beta_2)g_k^2,$$ $$\hat m_k=\frac{m_k}{1-\beta_1^k},\qquad\hat v_k=\frac{v_k}{1-\beta_2^k},\qquad w_k=w_{k-1}-\eta\,\frac{\hat m_k}{\sqrt{\hat v_k}+\epsilon}.$$

Typical settings: \(\beta_1=0.9\), \(\beta_2=0.999\), \(\epsilon=10^{-8}\), and \(\eta\) around \(10^{-3}\) for neural networks.

proposition 2.12 — why Adam divides by \(1-\beta^k\)

If the gradients \(g_1,g_2,\dots\) all have the same mean \(\bar g\), then

$$\mathbb E[m_k]=(1-\beta_1^k)\,\bar g,$$

so \(\hat m_k\) is an unbiased estimate of \(\bar g\).

The same holds for \(v_k\) and the mean squared gradient.

Unrolling the recursion from \(m_0=0\),

$$m_k=(1-\beta_1)\sum_{j=1}^k\beta_1^{k-j}g_j.$$

Taking expectations,

$$\mathbb E[m_k]=(1-\beta_1)\bar g\sum_{j=0}^{k-1}\beta_1^{j}=(1-\beta_1)\bar g\,\frac{1-\beta_1^k}{1-\beta_1}=(1-\beta_1^k)\bar g.$$

Without the correction, the early averages would be pulled towards the zero starting value: after one step \(m_1=0.1\,g_1\). \(\square\)

The ratio \(\hat m_k/\sqrt{\hat v_k}\) is roughly the sign of a consistent gradient, so each coordinate moves by about \(\eta\) per step regardless of the gradient's scale. That makes Adam far less sensitive to badly scaled coordinates than gradient descent, and easy to use across the very different layers of a neural network. It does not remove the need to choose \(\eta\).

code — Adam on the narrow valley, and with minibatches
def adam(eta, b1=0.9, b2=0.999, eps=1e-8, grad=g_of):
    def update(w, s):
        k = s.get('k', 0) + 1
        g = grad(w)
        m = b1 * s.get('m', 0) + (1 - b1) * g        # running mean of gradients (momentum)
        v = b2 * s.get('v', 0) + (1 - b2) * g ** 2   # running mean of squared gradients, per coordinate
        s.update(k=k, m=m, v=v)
        m_hat, v_hat = m / (1 - b1 ** k), v / (1 - b2 ** k)    # bias corrections for the zero start
        return w - eta * m_hat / (np.sqrt(v_hat) + eps)
    return update

w_gd = np.zeros(2)
for k in range(3000):
    w_gd = w_gd - g_of(w_gd) / L_
print(f'gradient descent, eta = 1/L: after 3000 steps gap to minimum {f(w_gd) - f(w_opt):.1e}')
for eta_a in [0.1, 0.03, 0.01]:
    w, s = np.zeros(2), {}
    upd = adam(eta_a)
    for k in range(3000):
        w = upd(w, s)
    print(f'Adam, eta = {eta_a}:             after 3000 steps gap to minimum {f(w) - f(w_opt):.1e}')

rng = np.random.default_rng(0)                      # Adam with minibatches, on the standardised regression
w, s = np.zeros(2), {}
for epoch in range(1, 6):
    for batch in np.array_split(rng.permutation(len(ys)), len(ys) // 10):
        upd = adam(0.02, grad=lambda w_, B=batch: 2 / len(B) * Xd[B].T @ (Xd[B] @ w_ - ys[B]))
        w = upd(w, s)
    print(f'epoch {epoch}: Adam minibatch loss {loss(w):.5f}  (optimum {loss(w_star):.5f})')
gradient descent, eta = 1/L: after 3000 steps gap to minimum 2.1e-03
Adam, eta = 0.1:             after 3000 steps gap to minimum 9.9e-07
Adam, eta = 0.03:             after 3000 steps gap to minimum 3.0e-02
Adam, eta = 0.01:             after 3000 steps gap to minimum 1.7e-01
epoch 1: Adam minibatch loss 0.33030  (optimum 0.24101)
epoch 2: Adam minibatch loss 0.24177  (optimum 0.24101)
epoch 3: Adam minibatch loss 0.24126  (optimum 0.24101)
epoch 4: Adam minibatch loss 0.24121  (optimum 0.24101)
epoch 5: Adam minibatch loss 0.24103  (optimum 0.24101)

On the narrow valley, Adam with \(\eta=0.1\) gets within \(10^{-6}\) of the minimum in 3,000 steps, where gradient descent with step \(1/L\) is still \(2\times10^{-3}\) away; with smaller \(\eta\) Adam is slower, so the step size still matters. The valley is tilted, not aligned with the coordinate axes, so per-coordinate rescaling can only partly straighten it; momentum, which does not care about axes, did better here. With minibatches, Adam's running averages smooth the gradient noise, and the loss settles close to the optimum (0.24103 against 0.24101) instead of bouncing as plain SGD did. Adam, usually in the variant AdamW that applies weight decay separately (Lecture 10), is the default optimiser for training transformers.

spot check 2.13

One coordinate's gradients are always about 1000, another's always about 0.001. Roughly how far does Adam move each coordinate per step (after the first few steps)?

For a constant gradient \(g\), what are \(\hat m\) and \(\sqrt{\hat v}\)?
\(\hat m\approx g\) and \(\sqrt{\hat v}\approx|g|\), so the step is about \(\eta\operatorname{sign}(g)\). This scale-invariance is Adam's main appeal, and also why its effective step does not shrink near a minimum unless the gradients start to fluctuate in sign.
bayes — curvature is certainty

Suppose the loss is a negative log posterior, \(f(w)=-\log p(w\mid\text{data})\), with its minimum (the most probable parameters) at \(w^*\). There the gradient is zero, and Taylor's theorem gives \(f(w)\approx f(w^*)+\tfrac12(w-w^*)^\top H(w-w^*)\). Exponentiating, the posterior is approximately a normal distribution with mean \(w^*\) and covariance \(H^{-1}\). This is the Laplace approximation. Sharp curvature (a large eigenvalue of \(H\)) means a small posterior variance in that direction: the data pin that combination of parameters down. A flat direction means the data barely constrain it. The narrow penguin valley is exactly such a case: intercept and slope can trade off against each other along the valley floor with almost no change in fit. Lecture 3 makes this exact for linear regression, and Lecture 17a uses it to compare models.

history — descending

Augustin-Louis Cauchy proposed gradient descent in a three-page note of 1847, as a way to solve the systems of equations that arise in computing the orbits of celestial bodies. Newton's method is older: Newton described a version for polynomials around 1669, and Joseph Raphson published a simpler form in 1690. The stochastic version comes from Herbert Robbins and Sutton Monro's 1951 paper on stochastic approximation, written as a statistics problem: finding a root of a function you can only measure with noise. Its machine-learning descendant, SGD with backpropagation, has trained nearly every large neural network since the 1980s. Boris Polyak introduced the heavy-ball momentum method in 1964 and Yurii Nesterov his accelerated method in 1983; Diederik Kingma and Jimmy Ba's Adam (2015) became one of the most cited papers in all of science.

8 — Summary, exercises, projects, reading

summary

Next: Lecture 3 puts projection and gradients together for linear regression, adds regularisation, and asks what regression coefficients do and do not mean.

exercises 2
  1. Find the cosine similarity and the angle between \(u=(1,2,2)\) and \(v=(2,0,1)\).

    \(\langle u,v\rangle=2+0+2=4\), \(\|u\|=3\), \(\|v\|=\sqrt5\). So \(\cos\theta=4/(3\sqrt5)\approx0.596\) and \(\theta\approx53.4^\circ\).

  2. Project \(y=(2,3)\) onto \(x=(1,1)\). Find \(p\) and \(r\), check that \(r\perp x\), and check Pythagoras.

    \(\beta=\langle x,y\rangle/\langle x,x\rangle=5/2\), so \(p=(2.5,2.5)\) and \(r=(-0.5,0.5)\). \(\langle r,x\rangle=0\). \(\|y\|^2=13=12.5+0.5=\|p\|^2+\|r\|^2\).

  3. Show that the matrix \(P=\dfrac{xx^\top}{x^\top x}\) projects onto the line through \(x\), and that \(P^2=P\) and \(P^\top=P\). What are its eigenvalues?

    \(Py=x\,\dfrac{x^\top y}{x^\top x}=\beta x\), the projection of Theorem 2.2. \(P^2=\dfrac{x(x^\top x)x^\top}{(x^\top x)^2}=P\): projecting twice changes nothing. \(P^\top=P\) since \((xx^\top)^\top=xx^\top\). Eigenvalues: 1 (eigenvector \(x\)) and 0 (every vector orthogonal to \(x\)), as for any projection.

  4. Diagonalise \(S=\begin{pmatrix}2&1\\1&2\end{pmatrix}\) and use \(S^{10}=Q\Lambda^{10}Q^\top\) to compute \(S^{10}\) without multiplying ten matrices.

    Eigenvalues 3 and 1, with eigenvectors \((1,1)/\sqrt2\) and \((1,-1)/\sqrt2\). Then \(S^{10}=3^{10}q_1q_1^\top+1^{10}q_2q_2^\top=\tfrac12\begin{pmatrix}3^{10}+1&3^{10}-1\\3^{10}-1&3^{10}+1\end{pmatrix}=\begin{pmatrix}29525&29524\\29524&29525\end{pmatrix}\). Powers of a matrix are powers of its eigenvalues, which is why the largest eigenvalue dominates repeated application (Lectures 9 and 21).

  5. Find the singular values of \(B=\begin{pmatrix}3&0\\4&5\end{pmatrix}\) and check that their product is \(|\det B|\).

    \(B^\top B=\begin{pmatrix}25&20\\20&25\end{pmatrix}\), with eigenvalues 45 and 5. So \(\sigma_1=\sqrt{45}=3\sqrt5\approx6.708\) and \(\sigma_2=\sqrt5\approx2.236\), and \(\sigma_1\sigma_2=15=|\det B|\). The unit circle maps to an ellipse with semi-axes 6.708 and 2.236, of area \(15\pi\).

  6. Show that \(f(w)=\frac1n\|Xw-y\|^2\) is convex, using its Hessian. When is it strictly convex, with a unique minimiser?

    \(\nabla^2f=\frac2nX^\top X\), and for every \(u\), \(u^\top X^\top Xu=\|Xu\|^2\ge0\): positive semi-definite, so \(f\) is convex. It is strictly convex exactly when \(Xu\ne0\) for every \(u\ne0\), i.e. when \(X\) has full column rank. With the duplicated mass column of Section 3 it does not, and the minimiser is not unique: any amount of weight can be moved between "mass in g" and "mass in kg".

  7. Run gradient descent by hand on \(f(x)=2x^2\) from \(x_0=1\) with \(\eta=0.1\), \(0.25\), \(0.4\) and \(0.6\). Which converge, and how?

    \(f'(x)=4x\), so \(x_{t+1}=(1-4\eta)x_t\). For \(\eta=0.1\) the factor is 0.6: steady convergence. For \(\eta=0.25\) it is 0: the minimum in one step. For \(\eta=0.4\) it is −0.6: convergence, overshooting back and forth. For \(\eta=0.6\) it is −1.4: divergence. The threshold is \(2/\lambda=0.5\).

  8. Apply Newton's method to \(f(x)=x^4\). Show that \(x_{t+1}=\tfrac23x_t\), so it converges only linearly. Why is Newton slow here?

    \(x-f'(x)/f''(x)=x-4x^3/(12x^2)=\tfrac23x\). Newton's fast convergence needs a positive second derivative at the minimum; here \(f''(0)=0\), so the quadratic model is poor near the solution.

  9. For an \(m\times n\) image, how large can \(k\) be before a rank-\(k\) approximation needs more storage than the image itself? Evaluate for the 512×512 photograph.

    Storage is \(k(m+n+1)\) against \(mn\), so savings require \(k<mn/(m+n+1)\). For \(512\times512\) that is \(262144/1025\approx255.8\): useful only for \(k\le255\), and in practice for much smaller \(k\). The code box shows \(k=50\) at 19.6% of the storage with 8% relative error.

  10. (The Rayleigh quotient.) Let \(S\) be symmetric with eigenvalues \(\lambda_1\ge\dots\ge\lambda_d\). Show that \(\max_{\|u\|=1}u^\top Su=\lambda_1\), attained at the top eigenvector. What fraction of the total variance of the four standardised penguin features lies along the best single direction?

    Write \(u=\sum_ic_iq_i\) in the eigenbasis, so \(\sum_ic_i^2=1\). Then \(u^\top Su=\sum_i\lambda_ic_i^2\le\lambda_1\sum_ic_i^2=\lambda_1\), with equality when \(u=q_1\). For the penguins, \(\lambda_1/\operatorname{tr}S=2.754/4\approx68.9\%\). This is the first principal component (Lecture 16).

  11. For a quadratic with condition number \(\kappa=100\), how many steps do the best fixed-step gradient descent and the best heavy-ball method need to shrink the error by a factor of \(10^6\)?

    Gradient descent: factor \(99/101\) per step, so \(t\approx\ln10^6/\ln(101/99)=13.82/0.0200\approx691\). Momentum: factor \(9/11\), so \(t\approx13.82/\ln(11/9)=13.82/0.2007\approx69\). Ten times fewer, which is \(\sqrt{100}\).

  12. Show that with exact line search on a quadratic, the path turns through a right angle at every step, and explain why this makes the path zig-zag in a narrow valley.

    Proposition 2.9 gives \(g_{t+1}^\top g_t=0\), and each step moves along \(-g_t\), so consecutive steps are perpendicular. In a narrow valley the first gradient points mostly across the valley; the next step must be perpendicular to it, so mostly along the floor, but it overshoots the floor's tilt slightly, and the next step is across again. In two dimensions the steps alternate between just two directions; in more dimensions the zig-zag can persist for many steps.

student projects

Each project uses only this lecture's tools and public data, and has a clear result.

1. The low-rank structure of New York's complaints

question
Do a few "patterns" explain most of the variation in what New Yorkers complain about, where and when?
data
NYC 311 service requests (NYC Open Data). Build a matrix with one row per community district and one column per week, for each major complaint type (or one row per district and one column per complaint type).
method
Centre and scale the matrix, compute its SVD, plot the singular values and map the top left singular vectors across the city. Interpret the top right singular vectors as time patterns (heating season, summer noise, storms).
outcome
A short, well-illustrated paper on interpretable components of civic data, with a check of how stable the components are from year to year.

2. SVD versus JPEG

question
At equal storage, how does the best rank-\(k\) approximation compare with JPEG compression?
data
A collection of public-domain images (for example NASA images or the Library of Congress free-to-use collections).
method
For a range of storage budgets, compute rank-\(k\) approximations and JPEG files of the same size; compare them by mean squared error and by a perceptual measure such as SSIM. Try SVD on image blocks rather than the whole image.
outcome
A clear account of why block-based transforms (JPEG uses the discrete cosine transform, Lecture 18) beat a global SVD, and where SVD does well. Suits an undergraduate or mathematics-education venue.

3. How much does feature scaling matter for gradient descent?

question
On real regression datasets, how much do centring and scaling change the condition number of \(X^\top X\) and the number of gradient-descent steps needed?
data
Twenty or more regression datasets from OpenML or the UCI repository.
method
For raw, centred and standardised versions of each, compute the condition number and the steps gradient descent needs to reach a fixed tolerance; compare with the \(\kappa\ln(1/\epsilon)\) prediction of Proposition 2.7.
outcome
An empirical note connecting textbook theory to practice, with a reusable benchmarking script.

Reading and sources

Data. Palmer penguins: Gorman, Williams & Fraser, PLoS ONE 9(3), e90081 (2014); Horst, Hill & Gorman, palmerpenguins (2020), doi:10.5281/zenodo.3960218, CC0. Photograph: official NASA portrait of Eileen Collins (public domain), distributed with scikit-image: S. van der Walt et al., "scikit-image: image processing in Python", PeerJ 2, e453 (2014). Software: NumPy (C. R. Harris et al., Nature 585, 357–362, 2020).

every number in the text and widgets is computed in verify_L02.py; code-box outputs are pasted from actual runs