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
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.
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.
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\).
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.
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".
Compute \(\langle u,v\rangle\) for \(u=(1,2,3)\) and \(v=(4,-5,6)\).
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.
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$$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.
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.
Two centred variables have correlation \(0\). What does that say about their centred data vectors?
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:
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.
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:
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.
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.
Most directions are turned by a matrix. The special ones that are not are its eigenvectors.
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.
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.
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).
Which statements are true for every real symmetric matrix? Select all that apply.
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.
A qubit is in the state \(|\psi\rangle=\tfrac35|0\rangle+\tfrac45|1\rangle\). With what probability does measuring it give 0?
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.
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\).
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\).
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.
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.
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\).
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.
The widget's image is 256×256. What fraction of the original storage does a rank-20 approximation need? (Give a decimal.)
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.
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.
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.
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.
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.
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.
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.
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)\).
Proposition 2.6 suggests an algorithm. Stand at \(w_0\); compute the gradient; take a small step against it; repeat.
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.
\(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.
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.
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.
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]
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.
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\)
A quadratic loss has Hessian eigenvalues 2 and 10. Above what step size does gradient descent diverge?
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.
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.
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.
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.
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)\).)
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).
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$$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.
A quadratic has condition number \(\kappa=100\). By what factor does the error shrink per step with optimally tuned momentum?
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.
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 .
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.
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).
Why does the SGD loss in the code box bounce around 0.242–0.244 instead of settling at 0.241?
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.
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.
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\).
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.
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)?
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.
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.
Next: Lecture 3 puts projection and gradients together for linear regression, adds regularisation, and asks what regression coefficients do and do not mean.
\(\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\).
\(\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\).
\(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.
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).
\(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\).
\(\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".
\(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\).
\(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.
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.
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).
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}\).
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.
Each project uses only this lecture's tools and public data, and has a clear result.
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