Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

The Math Toolkit of AI

Vectors, probability, calculus and optimization in one place.

Train any model in this course and the same five tools are at work: vectors hold the data, derivatives measure sensitivity, probability models the noise, optimization fits the parameters, and cross-entropy scores the predictions. Here you derive each tool once, together with the results you will lean on for the rest of the course.

What you’ll learn

  • Work with vectors and matrices as a practitioner does: dot products, norms, linear layers and the eigendecomposition of symmetric matrices.
  • Compute gradients with the multivariable chain rule and derive the least-squares normal equations.
  • Derive a loss function from a probabilistic model by maximum likelihood.
  • Prove the descent lemma and use it, with the condition number, to choose a stable learning rate.
  • Relate entropy, cross-entropy and KL divergence, and derive the softmax cross-entropy gradient q−y\mathbf q-\mathbf y.

Vectors, matrices and the geometry of data

A data point with nn features is a vector x∈Rn\mathbf x\in\R^n, and a dataset of NN points stacks into a matrix X∈RN×nX\in\R^{N\times n}, one example per row. Two operations do most of the work in AI. The dot product w⊤x=∑iwixi\mathbf w^\top\mathbf x=\sum_iw_ix_i scores how well x\mathbf x lines up with a weight vector w\mathbf w. A matrix-vector product computes many dot products at once: a linear layer z=Wx+b\mathbf z=W\mathbf x+\mathbf b with W∈Rm×nW\in\R^{m\times n} maps nn input features to mm outputs, one row of WW per output.

Sizes are measured with norms, ∥x∥2=x⊤x\norm{\mathbf x}_2=\sqrt{\mathbf x^\top\mathbf x} and ∥x∥1=∑i∣xi∣\norm{\mathbf x}_1=\sum_i\abs{x_i}. The Cauchy–Schwarz inequality ∣w⊤x∣≤∥w∥2∥x∥2\abs{\mathbf w^\top\mathbf x}\le\norm{\mathbf w}_2\norm{\mathbf x}_2 keeps the cosine similarity w⊤x/(∥w∥2∥x∥2)\mathbf w^\top\mathbf x/(\norm{\mathbf w}_2\norm{\mathbf x}_2) inside [−1,1][-1,1], which is how embeddings are compared later in the course.

Symmetric matrices are everywhere in AI: covariance matrices, Gram matrices X⊤XX^\top X, kernel matrices and Hessians. A Gram matrix is always positive semidefinite, because v⊤X⊤Xv=∥Xv∥22≥0\mathbf v^\top X^\top X\mathbf v=\norm{X\mathbf v}_2^2\ge0. For centered data, 1NX⊤X\tfrac1NX^\top X is the covariance matrix and its eigenvectors are the principal components (PCA). Eigenvalues of this kind will decide how fast gradient descent converges in step 5.

Check your understanding

A linear layer maps 784-pixel images to 10 class scores, z=Wx+b\mathbf z=W\mathbf x+\mathbf b. What are the shapes of WW and b\mathbf b, and how many parameters does the layer have?

  1. WW is 784×10784\times10 and b∈R784\mathbf b\in\R^{784}: 8,624 parameters
  2. WW is 784×784784\times784 and b∈R10\mathbf b\in\R^{10}: 614,666 parameters
  3. WW is 10×78410\times784 and b∈R10\mathbf b\in\R^{10}: 7,850 parameters
  4. WW is 10×78410\times784 and b∈R784\mathbf b\in\R^{784}: 8,624 parameters
Show the answer

C. WW is 10×78410\times784 and b∈R10\mathbf b\in\R^{10}: 7,850 parameters

WxW\mathbf x must be a 10-vector, so WW has 10 rows (one per class) and 784 columns (one per pixel), and b\mathbf b matches the output: 10⋅784+10=7,85010\cdot784+10=7{,}850 parameters. Each row of WW is a template that the image is dot-producted with.

Gradients, Jacobians and the chain rule

For f:Rn→Rf:\R^n\to\R, the gradient ∇f(x)\nabla f(\mathbf x) collects the partial derivatives and gives the best linear approximation, f(x+δ)≈f(x)+∇f(x)⊤δf(\mathbf x+\boldsymbol\delta)\approx f(\mathbf x)+\nabla f(\mathbf x)^\top\boldsymbol\delta. By Cauchy–Schwarz, among all small steps of a given length the one along −∇f-\nabla f decreases ff fastest: steepest descent. For a vector-valued g:Rn→Rm\mathbf g:\R^n\to\R^m, the Jacobian Jg∈Rm×nJ_{\mathbf g}\in\R^{m\times n} has entries ∂gi/∂xj\partial g_i/\partial x_j. The second derivatives of a scalar ff form the symmetric Hessian ∇2f\nabla^2f, which measures curvature:

f(x+δ)=f(x)+∇f(x)⊤δ+12 δ⊤∇2f(x) δ+o(∥δ∥2)f(\mathbf x+\boldsymbol\delta)=f(\mathbf x)+\nabla f(\mathbf x)^\top\boldsymbol\delta+\tfrac12\,\boldsymbol\delta^\top\nabla^2f(\mathbf x)\,\boldsymbol\delta+o\big(\norm{\boldsymbol\delta}^2\big)
The second-order Taylor expansion, for twice continuously differentiable ff. Where ∇f=0\nabla f=\mathbf 0, a positive definite Hessian certifies a strict local minimum, and a Hessian with eigenvalues of both signs certifies a saddle point.

Gradients of compositions follow the multivariable chain rule: Jacobians multiply. For f(x)=ℓ(g(x))f(\mathbf x)=\ell(\mathbf g(\mathbf x)) with ℓ:Rm→R\ell:\R^m\to\R,

∇f(x)=Jg(x)⊤ ∇ℓ(g(x)).\nabla f(\mathbf x)=J_{\mathbf g}(\mathbf x)^\top\,\nabla\ell\big(\mathbf g(\mathbf x)\big).

Backpropagation is this formula applied to a network layer by layer, from the loss back to the inputs.

f(x)f(\mathbf x)∇f(x)\nabla f(\mathbf x)Where it appears
a⊤x\mathbf a^\top\mathbf xa\mathbf alinear models, logits
x⊤Ax\mathbf x^\top A\mathbf x(A+A⊤)x(A+A^\top)\mathbf x, which is 2Ax2A\mathbf x for symmetric AAquadratic losses, Gaussian log-densities
∥Xx−y∥22\norm{X\mathbf x-\mathbf y}_2^22X⊤(Xx−y)2X^\top(X\mathbf x-\mathbf y)least squares
λ∥x∥22\lambda\norm{\mathbf x}_2^22λx2\lambda\mathbf xweight decay
log⁡∑jexj\log\sum_je^{x_j}softmax⁡(x)\softmax(\mathbf x)softmax classifiers
Gradients worth knowing by heart. Each follows from writing the function in coordinates, or from the chain rule.
DerivationLeast squares by calculus
  1. L(w)=∥Xw−y∥2=w⊤X⊤Xw−2 y⊤Xw+y⊤yL(\mathbf w)=\norm{X\mathbf w-\mathbf y}^2=\mathbf w^\top X^\top X\mathbf w-2\,\mathbf y^\top X\mathbf w+\mathbf y^\top\mathbf y

    Fit a linear model y^=Xw\hat{\mathbf y}=X\mathbf w to targets y∈RN\mathbf y\in\R^N by minimizing the squared error. Expand the loss:

  2. ∇L(w)=2X⊤Xw−2X⊤y=2X⊤(Xw−y)\nabla L(\mathbf w)=2X^\top X\mathbf w-2X^\top\mathbf y=2X^\top(X\mathbf w-\mathbf y)

    Differentiate term by term with the table (X⊤XX^\top X is symmetric):

  3. X⊤X w⋆=X⊤y⟹w⋆=(X⊤X)−1X⊤yX^\top X\,\mathbf w^\star=X^\top\mathbf y\quad\Longrightarrow\quad\mathbf w^\star=(X^\top X)^{-1}X^\top\mathbf y

    Set the gradient to zero. These are the normal equations. When XX has full column rank, X⊤XX^\top X is positive definite and hence invertible:

  4. X⊤(y−Xw⋆)=0X^\top\big(\mathbf y-X\mathbf w^\star\big)=\mathbf 0

    The Hessian ∇2L=2X⊤X\nabla^2L=2X^\top X is positive semidefinite everywhere, so LL is convex and the stationary point is a global minimum. Geometrically, the residual is orthogonal to every column of XX: the fit Xw⋆X\mathbf w^\star is the orthogonal projection of y\mathbf y onto the column space of XX.

Think first Why does the gradient of x⊤Ax\mathbf x^\top A\mathbf x involve A+A⊤A+A^\top rather than 2A2A?

Write x⊤Ax=∑i,jAijxixj\mathbf x^\top A\mathbf x=\sum_{i,j}A_{ij}x_ix_j. The variable xkx_k appears in row kk (the terms AkjxkxjA_{kj}x_kx_j) and in column kk (the terms AikxixkA_{ik}x_ix_k), so ∂/∂xk=∑jAkjxj+∑iAikxi=((A+A⊤)x)k\partial/\partial x_k=\sum_jA_{kj}x_j+\sum_iA_{ik}x_i=\big((A+A^\top)\mathbf x\big)_k. Only the symmetric part of AA affects a quadratic form, so you can always replace AA by 12(A+A⊤)\tfrac12(A+A^\top).

Probability: from noise models to losses

A random variable XX has a distribution, its expectation E[X]\E[X] is the probability-weighted average, and its variance Var⁡(X)=E[(X−EX)2]=E[X2]−(EX)2\Var(X)=\E\big[(X-\E X)^2\big]=\E[X^2]-(\E X)^2 measures spread. Two facts carry a surprising amount of weight. Expectation is linear, E[aX+bY]=aE[X]+bE[Y]\E[aX+bY]=a\E[X]+b\E[Y], whether or not XX and YY are independent. Variances add only for uncorrelated variables, so the mean Xˉ\bar X of nn independent draws with variance σ2\sigma^2 has Var⁡(Xˉ)=σ2/n\Var(\bar X)=\sigma^2/n.

Conditional probability and Bayes' rule, p(θ∣D)=p(D∣θ) p(θ)/p(D)p(\theta\mid\data)=p(\data\mid\theta)\,p(\theta)/p(\data), turn a model of how data arise into beliefs about the parameters: the posterior is proportional to the likelihood times the prior. Most of machine learning uses the likelihood alone. Maximum likelihood picks the parameters under which the observed data are most probable. For independent examples the likelihood is a product, so you maximize its logarithm, a sum, or equivalently minimize the negative log-likelihood:

θ^ML=arg max⁡θ∏i=1Np(yi∣xi;θ)=arg min⁡θ∑i=1N−log⁡p(yi∣xi;θ)\hat\theta_{\mathrm{ML}}=\argmax_\theta\prod_{i=1}^Np(y_i\mid\mathbf x_i;\theta)=\argmin_\theta\sum_{i=1}^N-\log p(y_i\mid\mathbf x_i;\theta)
The logarithm is increasing, so it keeps the maximizer, and it turns a product of tiny numbers into a well-behaved sum.
DerivationGaussian noise gives squared error
  1. p(yi∣xi;w)=12π σexp⁡(−(yi−w⊤xi)22σ2)p(y_i\mid\mathbf x_i;\mathbf w)=\frac1{\sqrt{2\pi}\,\sigma}\exp\Big(-\frac{(y_i-\mathbf w^\top\mathbf x_i)^2}{2\sigma^2}\Big)

    Model each target as a linear prediction plus Gaussian noise, yi=w⊤xi+εiy_i=\mathbf w^\top\mathbf x_i+\varepsilon_i with independent εi∼N(0,σ2)\varepsilon_i\sim\mathcal N(0,\sigma^2). Then

  2. −log⁡p(D∣w)=12σ2∑i=1N(yi−w⊤xi)2+N2log⁡(2πσ2)-\log p(\data\mid\mathbf w)=\frac1{2\sigma^2}\sum_{i=1}^N\big(y_i-\mathbf w^\top\mathbf x_i\big)^2+\frac N2\log\big(2\pi\sigma^2\big)

    Take the negative logarithm and sum over the data:

  3. w^ML=arg min⁡w∑i=1N(yi−w⊤xi)2\hat{\mathbf w}_{\mathrm{ML}}=\argmin_{\mathbf w}\sum_{i=1}^N\big(y_i-\mathbf w^\top\mathbf x_i\big)^2

    The second term does not depend on w\mathbf w. So maximum likelihood under Gaussian noise is least squares, the mean squared error loss of the previous step:

  4. w^MAP=arg min⁡w∑i=1N(yi−w⊤xi)2+λ∥w∥2,λ=σ2τ2\hat{\mathbf w}_{\mathrm{MAP}}=\argmin_{\mathbf w}\sum_{i=1}^N\big(y_i-\mathbf w^\top\mathbf x_i\big)^2+\lambda\norm{\mathbf w}^2,\qquad\lambda=\frac{\sigma^2}{\tau^2}

    Change the model and the loss changes with it. Laplace noise gives absolute error, and a Bernoulli model of binary labels gives the cross-entropy loss of logistic regression (step 6). A Gaussian prior w∼N(0,τ2I)\mathbf w\sim\mathcal N(0,\tau^2I) adds a ridge penalty: the MAP estimate is

Think first You average nn independent measurements, each with standard deviation σ=2\sigma=2. How many do you need before the average has standard deviation 0.10.1?

Var⁡(Xˉ)=σ2/n\Var(\bar X)=\sigma^2/n, so the standard deviation of the average is σ/n\sigma/\sqrt n. From 2/n=0.12/\sqrt n=0.1 you get n=20\sqrt n=20, so n=400n=400. Halving the error costs four times the data. The same 1/n1/\sqrt n law governs mini-batch gradient noise, Monte Carlo estimates and the error bars of a test set; the Deep Layer turns it into high-probability guarantees with concentration inequalities.

Convexity and the descent lemma

Most losses have no closed-form minimizer, so you descend instead: wt+1=wt−η ∇L(wt)\mathbf w_{t+1}=\mathbf w_t-\eta\,\nabla L(\mathbf w_t) with learning rate η\eta. When is a step guaranteed to make progress, and when does gradient descent find the global minimum rather than a local one? Two properties of the loss answer those questions.

Convexity turns local search into global optimization. If ∇f(x⋆)=0\nabla f(\mathbf x^\star)=\mathbf 0, the tangent-plane inequality at x⋆\mathbf x^\star reads f(y)≥f(x⋆)f(\mathbf y)\ge f(\mathbf x^\star) for every y\mathbf y: every stationary point of a convex function is a global minimizer. Least squares and logistic regression have convex losses; neural networks do not, which is why their training is analyzed so differently. Smoothness, for its part, is what makes a gradient step safe:

DerivationProof
  1. f(y)=f(x)+∇f(x)⊤(y−x)+∫01(∇f(x+t(y−x))−∇f(x))⊤(y−x) dtf(\mathbf y)=f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\int_0^1\big(\nabla f(\mathbf x+t(\mathbf y-\mathbf x))-\nabla f(\mathbf x)\big)^\top(\mathbf y-\mathbf x)\,dt

    Write f(y)−f(x)f(\mathbf y)-f(\mathbf x) as the integral of the gradient along the segment x+t(y−x)\mathbf x+t(\mathbf y-\mathbf x), t∈[0,1]t\in[0,1], and split off the gradient at x\mathbf x:

  2. f(y)≤f(x)+∇f(x)⊤(y−x)+L2∥y−x∥2f(\mathbf y)\le f(\mathbf x)+\nabla f(\mathbf x)^\top(\mathbf y-\mathbf x)+\frac L2\norm{\mathbf y-\mathbf x}^2

    By Cauchy–Schwarz and the Lipschitz condition the integrand is at most Lt∥y−x∥2Lt\norm{\mathbf y-\mathbf x}^2, and ∫01Lt dt=L/2\int_0^1Lt\,dt=L/2. So ff lies below a quadratic that touches it at x\mathbf x:

  3. f(x+)≤f(x)−η∥∇f(x)∥2+Lη22∥∇f(x)∥2=f(x)−η(1−Lη2)∥∇f(x)∥2f(\mathbf x^+)\le f(\mathbf x)-\eta\norm{\nabla f(\mathbf x)}^2+\frac{L\eta^2}2\norm{\nabla f(\mathbf x)}^2=f(\mathbf x)-\eta\Big(1-\frac{L\eta}2\Big)\norm{\nabla f(\mathbf x)}^2

    Substitute the gradient step y=x−η∇f(x)\mathbf y=\mathbf x-\eta\nabla f(\mathbf x):

  4. min⁡0≤t<T∥∇f(xt)∥2≤2L(f(x0)−f⋆)T(η=1/L)\min_{0\le t<T}\norm{\nabla f(\mathbf x_t)}^2\le\frac{2L\big(f(\mathbf x_0)-f^\star\big)}{T}\qquad(\eta=1/L)

    The bracket is positive exactly when η<2/L\eta<2/L, and the guaranteed decrease is largest at η=1/L\eta=1/L. Summing the decreases over TT steps (they telescope) bounds the gradient even for nonconvex ff with minimum value f⋆f^\star:

Learning rates and conditioning

Why exactly 2/L2/L, and what decides the speed? Take a quadratic f(x)=12x⊤Axf(\mathbf x)=\tfrac12\mathbf x^\top A\mathbf x with A=QΛQ⊤A=Q\Lambda Q^\top positive definite, so ∇f(x)=Ax\nabla f(\mathbf x)=A\mathbf x and L=λmax⁡L=\lambda_{\max}. A gradient step is xt+1=(I−ηA)xt\mathbf x_{t+1}=(I-\eta A)\mathbf x_t, and in the eigenbasis the coordinates decouple:

qi⊤xt=(1−ηλi)t qi⊤x0,soxt→0 from every start  ⟺  0<η<2λmax⁡\mathbf q_i^\top\mathbf x_t=(1-\eta\lambda_i)^t\,\mathbf q_i^\top\mathbf x_0,\qquad\text{so}\qquad\mathbf x_t\to\mathbf 0\ \text{from every start}\iff0<\eta<\frac2{\lambda_{\max}}
Each eigendirection shrinks by its own factor 1−ηλi1-\eta\lambda_i, flipping sign at every step when ηλi>1\eta\lambda_i>1.

The largest eigenvalue L=λmax⁡L=\lambda_{\max} caps the learning rate, while the smallest, μ=λmin⁡\mu=\lambda_{\min}, sets the pace along the flattest direction. The best constant step, η=2/(L+μ)\eta=2/(L+\mu), balances the two and contracts the error by a factor (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) per step, where κ=L/μ\kappa=L/\mu is the condition number. Long, thin valleys (large κ\kappa) are slow for plain gradient descent, and much of the optimizer zoo, from momentum to Adam, exists to fix exactly this. The Deep Layer proves rates of this kind for every smooth, strongly convex function.

Predict before you look

The valley in the widget below is f(x,y)=0.05x2+2y2f(x,y)=0.05x^2+2y^2. Gradient descent converges from every start exactly when the learning rate is below some threshold. What is the threshold?

Show the answer

0.5

Here f=12x⊤Axf=\tfrac12\mathbf x^\top A\mathbf x with A=diag⁡(0.1, 4)A=\diag(0.1,\,4), so L=4L=4, and the steep yy-direction needs ∣1−4η∣<1\abs{1-4\eta}<1, i.e. η<2/L=0.5\eta<2/L=0.5. The flat xx-direction alone would tolerate any η<20\eta<20. Even the best constant step, η=2/(L+μ)≈0.49\eta=2/(L+\mu)\approx0.49, shrinks the error only by (κ−1)/(κ+1)=39/41≈0.95(\kappa-1)/(\kappa+1)=39/41\approx0.95 per step, because κ=40\kappa=40.

Entropy, cross-entropy and KL divergence

How should you score a predicted distribution qq when outcomes actually follow pp? Information theory starts from surprise: an outcome to which you gave probability q(x)q(x) carries −log⁡q(x)-\log q(x) of it. The entropy H(p)H(p) is the average surprise of pp about its own outcomes, and the cross-entropy H(p,q)H(p,q) is the average surprise of a model qq when outcomes follow pp:

H(p)=−∑xp(x)log⁡p(x),H(p,q)=−∑xp(x)log⁡q(x)=H(p)+DKL(p ∥ q)H(p)=-\sum_xp(x)\log p(x),\qquad H(p,q)=-\sum_xp(x)\log q(x)=H(p)+\KL(p\,\|\,q)
With log⁡2\log_2 the unit is bits, with ln⁡\ln it is nats. The gap between the two is the KL divergence DKL(p ∥ q)=∑xp(x)log⁡p(x)q(x)\KL(p\,\|\,q)=\sum_xp(x)\log\frac{p(x)}{q(x)}.

The KL divergence is never negative and is zero only when q=pq=p (Gibbs' inequality, proved in the Deep Layer). For a fixed data distribution pp, minimizing the cross-entropy over models qq therefore minimizes DKL(p ∥ q)\KL(p\,\|\,q), the mismatch between model and truth. Let pp be the empirical distribution of a training set and the cross-entropy becomes the average negative log-likelihood of step 3: minimizing cross-entropy is maximum likelihood.

DerivationThe softmax cross-entropy gradient
  1. qk=ezk∑jezj,L(z)=−∑kyklog⁡qk=−zc+log⁡∑jezjq_k=\frac{e^{z_k}}{\sum_je^{z_j}},\qquad\loss(\mathbf z)=-\sum_ky_k\log q_k=-z_c+\log\sum_je^{z_j}

    A classifier outputs scores (logits) z∈RK\mathbf z\in\R^K and turns them into probabilities with the softmax. For a one-hot label y\mathbf y with true class cc, the cross-entropy loss simplifies to a log-sum-exp:

  2. ∂L∂zk=−yk+ezk∑jezj=qk−yk\frac{\partial\loss}{\partial z_k}=-y_k+\frac{e^{z_k}}{\sum_je^{z_j}}=q_k-y_k

    Differentiate with respect to each logit. The first term contributes −yk-y_k, and the log-sum-exp contributes the softmax itself (see the table in step 2):

  3. ∇zL=q−y\nabla_{\mathbf z}\loss=\mathbf q-\mathbf y

    The gradient is prediction minus target. Each entry lies in [−1,1][-1,1], the gradient vanishes only when the prediction matches the label, and a descent step raises the true logit in proportion to 1−qc1-q_c and lowers every other logit in proportion to qkq_k:

  4. ∇wL=(σ(w⊤x)−y) x\nabla_{\mathbf w}\loss=\big(\sigma(\mathbf w^\top\mathbf x)-y\big)\,\mathbf x

    With two classes the softmax reduces to the sigmoid σ(z)=1/(1+e−z)\sigma(z)=1/(1+e^{-z}), and the same computation gives ∂L/∂z=σ(z)−y\partial\loss/\partial z=\sigma(z)-y. For logistic regression, z=w⊤xz=\mathbf w^\top\mathbf x, so by the chain rule

Check your understanding

A classifier gives probability 0.250.25 to the true class of an example. What is that example's cross-entropy loss, in bits?

  1. 0.250.25
  2. 0.750.75
  3. 22
  4. 44
Show the answer

C. 22

Only the probability of the true class enters: −log⁡20.25=2-\log_2 0.25=2 bits. A confident correct prediction (qc→1q_c\to1) costs almost nothing, while a confident wrong one (qc→0q_c\to0) costs without bound. That asymmetry is why cross-entropy rewards honest probabilities.

python
import numpy as np

def sigmoid(z):
    return 1.0 / (1.0 + np.exp(-z))

def fit_logistic(X, y, eta=0.1, steps=2000):
    """Gradient descent on the mean cross-entropy.
    X: (N, n) features, y: (N,) labels in {0, 1}."""
    N, n = X.shape
    w = np.zeros(n)
    for _ in range(steps):
        q = sigmoid(X @ w)          # predicted P(y = 1 | x)
        grad = X.T @ (q - y) / N    # mean of (q_i - y_i) x_i
        w -= eta * grad
    return w

Logistic regression uses the whole kit: a matrix-vector product, a probabilistic model, the cross-entropy gradient q−y\mathbf q-\mathbf y pushed back through X⊤X^\top, and a gradient step. The mean loss is convex and LL-smooth with L≤λmax⁡(X⊤X)/(4N)L\le\lambda_{\max}(X^\top X)/(4N), because σ′≤14\sigma'\le\tfrac14, so any η<2/L\eta<2/L is safe. If the classes are linearly separable, no minimizer exists: the loss keeps falling as ∥w∥→∞\norm{\mathbf w}\to\infty.

Key takeaways

  • Data are vectors and layers are matrices. Symmetric matrices diagonalize as QΛQ⊤Q\Lambda Q^\top, and the eigenvalues of Gram matrices, covariances and Hessians govern both geometry and optimization.
  • Gradients compose by the chain rule, ∇(ℓ∘g)=Jg⊤∇ℓ\nabla(\ell\circ\mathbf g)=J_{\mathbf g}^\top\nabla\ell; least squares has the closed form X⊤Xw⋆=X⊤yX^\top X\mathbf w^\star=X^\top\mathbf y.
  • Loss functions are negative log-likelihoods: Gaussian noise gives squared error, Bernoulli or categorical labels give cross-entropy, and a Gaussian prior adds a ridge penalty.
  • For LL-smooth ff, gradient descent decreases the loss whenever η<2/L\eta<2/L; for convex ff every stationary point is a global minimum, and the condition number κ=L/μ\kappa=L/\mu sets the pace.
  • H(p,q)=H(p)+DKL(p ∥ q)H(p,q)=H(p)+\KL(p\,\|\,q) with DKL≥0\KL\ge0, so minimizing cross-entropy is maximum likelihood, and the softmax cross-entropy gradient is q−y\mathbf q-\mathbf y.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Gradient descent on a differentiable convex function reaches a point where ∇f=0\nabla f=\mathbf 0. What can you conclude?

  1. It is a local minimizer, but possibly not a global one
  2. It is a global minimizer
  3. It could be a saddle point
  4. Nothing, until you check the Hessian
Show the answer

B. It is a global minimizer

For convex differentiable ff, the tangent plane lies below the graph: f(y)≥f(x⋆)+∇f(x⋆)⊤(y−x⋆)=f(x⋆)f(\mathbf y)\ge f(\mathbf x^\star)+\nabla f(\mathbf x^\star)^\top(\mathbf y-\mathbf x^\star)=f(\mathbf x^\star) for every y\mathbf y. A stationary point is therefore globally optimal, though the minimizer need not be unique.

Question 2

Targets are modeled as y=w⊤x+εy=\mathbf w^\top\mathbf x+\varepsilon with Laplace noise, whose density is proportional to e−∣ε∣/be^{-\abs{\varepsilon}/b}. Which loss does maximum likelihood minimize?

  1. Squared error, ∑i(yi−w⊤xi)2\sum_i(y_i-\mathbf w^\top\mathbf x_i)^2
  2. Cross-entropy
  3. Absolute error, ∑i∣yi−w⊤xi∣\sum_i\abs{y_i-\mathbf w^\top\mathbf x_i}
  4. Squared error plus λ∥w∥2\lambda\norm{\mathbf w}^2
Show the answer

C. Absolute error, ∑i∣yi−w⊤xi∣\sum_i\abs{y_i-\mathbf w^\top\mathbf x_i}

The negative log-likelihood is 1b∑i∣yi−w⊤xi∣\frac1b\sum_i\abs{y_i-\mathbf w^\top\mathbf x_i} plus a constant. Heavier-tailed noise gives a loss that grows only linearly in the residual, so outliers pull on the fit less than under squared error.

Question 3

You run gradient descent on f(x)=12x⊤Axf(\mathbf x)=\tfrac12\mathbf x^\top A\mathbf x, where AA has eigenvalues 11 and 100100. Which learning rates make it converge from every starting point?

  1. 0<η<0.020<\eta<0.02
  2. 0<η<20<\eta<2
  3. Only η=0.01\eta=0.01 exactly
  4. Any η\eta between 0.010.01 and 11
Show the answer

A. 0<η<0.020<\eta<0.02

The component along eigenvalue λ\lambda is multiplied by 1−ηλ1-\eta\lambda at every step and must shrink, so ∣1−100η∣<1\abs{1-100\eta}<1 forces η<2/100=0.02\eta<2/100=0.02. The flat direction then crawls with factor 1−η≥0.981-\eta\ge0.98 per step: the price of the condition number κ=100\kappa=100.

Question 4

Which statement about the KL divergence DKL(p ∥ q)\KL(p\,\|\,q) is true?

  1. It is symmetric: DKL(p ∥ q)=DKL(q ∥ p)\KL(p\,\|\,q)=\KL(q\,\|\,p)
  2. It is negative when qq fits the data better than pp does
  3. It is finite for every pair of distributions
  4. It equals H(p,q)−H(p)H(p,q)-H(p), so for fixed pp, minimizing the cross-entropy over qq minimizes it
Show the answer

D. It equals H(p,q)−H(p)H(p,q)-H(p), so for fixed pp, minimizing the cross-entropy over qq minimizes it

H(p,q)=H(p)+DKL(p ∥ q)H(p,q)=H(p)+\KL(p\,\|\,q), and H(p)H(p) does not depend on qq. KL is not symmetric, never negative (Gibbs' inequality), and infinite when q(x)=0q(x)=0 for some xx with p(x)>0p(x)>0.

Question 5

A 3-class softmax classifier outputs q=(0.7, 0.2, 0.1)\mathbf q=(0.7,\,0.2,\,0.1) on an example whose true class is the second one. What is the gradient of the cross-entropy loss with respect to the logits z\mathbf z?

  1. (−0.7, 0.8, −0.1)(-0.7,\,0.8,\,-0.1)
  2. (0.7, −0.8, 0.1)(0.7,\,-0.8,\,0.1)
  3. (0.7, 0.2, 0.1)(0.7,\,0.2,\,0.1)
  4. (0, −5, 0)(0,\,-5,\,0)
Show the answer

B. (0.7, −0.8, 0.1)(0.7,\,-0.8,\,0.1)

∇zL=q−y=(0.7,0.2,0.1)−(0,1,0)=(0.7,−0.8,0.1)\nabla_{\mathbf z}\loss=\mathbf q-\mathbf y=(0.7,0.2,0.1)-(0,1,0)=(0.7,-0.8,0.1). A descent step raises the true class's logit and lowers the others. The entries sum to zero because adding the same constant to every logit leaves the softmax unchanged.

Go deeper

Further reading

  • I. Goodfellow, Y. Bengio & A. Courville, Deep Learning (MIT Press, 2016), chapters 2–4.
  • M. P. Deisenroth, A. A. Faisal & C. S. Ong, Mathematics for Machine Learning (Cambridge University Press, 2020).
  • S. Boyd & L. Vandenberghe, Convex Optimization (Cambridge University Press, 2004), chapters 2, 3 and 9.
  • T. M. Cover & J. A. Thomas, Elements of Information Theory, 2nd ed. (Wiley, 2006), chapter 2.