Machine Learning from First Principles

Chapter 3 · Part I: Foundations

Optimization

Almost every model in this book is trained the same way: write down how wrong the model is, then walk downhill on that error surface. This chapter is about how to walk downhill well.

After this chapter you will be able to

  • State why training a model is an optimization problem and write down its objective.
  • Derive the gradient descent update and explain why it decreases the loss for a small enough step.
  • Predict when gradient descent converges, oscillates, or diverges, using the curvature of the loss.
  • Explain convexity and why it makes optimization easy.
  • Describe stochastic and mini-batch gradient descent and the trade-off controlled by the batch size.
  • Implement momentum and Adam in NumPy and explain what each term does.

3.1Learning as Optimization

Write the parameters of a model as a vector $\vtheta\in\R^p$ and its error on training example $i$ as a per-example loss $\ell_i(\vtheta)$. The training loss is the average

$$\Loss(\vtheta) = \frac{1}{n}\sum_{i=1}^{n}\ell_i(\vtheta). \tag{3.1}$$

Training means finding $\vtheta^\star = \argmin_{\vtheta}\Loss(\vtheta)$. A few models, such as linear regression in Chapter 4, can be solved in closed form. Almost everything else, including every neural network, needs an iterative method that starts from a guess and improves it.

Intuition: hiking down in fog

Picture the loss as a landscape: each point on the ground is a parameter vector $\vtheta$ and the altitude is $\Loss(\vtheta)$. You stand somewhere on it in thick fog. You cannot see the valley, but you can feel the slope under your feet. So you take a step in the steepest downhill direction, feel the slope again, and repeat. That is gradient descent.

3.2Gradient Descent

The gradient $\nabla\Loss(\vtheta)$ collects the partial derivatives $\pd{\Loss}{\theta_j}$. Its defining property is the first-order Taylor expansion: for a small displacement $\vv$,

$$\Loss(\vtheta+\vv) \approx \Loss(\vtheta) + \nabla\Loss(\vtheta)\T\vv. \tag{3.3}$$

Among all steps of a fixed length $\epsilon$, the one that makes $\nabla\Loss\T\vv$ most negative points straight against the gradient. (By Cauchy–Schwarz, $\nabla\Loss\T\vv \ge -\epsilon\norm{\nabla\Loss}_2$, with equality only for $\vv \propto -\nabla\Loss$.) Taking a step proportional to the negative gradient gives the update rule:

$$\vtheta_{t+1} = \vtheta_t - \eta\,\nabla\Loss(\vtheta_t) \tag{3.4}$$

The positive number $\eta$ is the learning rate. It is the most important single knob in deep learning.

Algorithm 3.1  Gradient descent
  1. Input: differentiable loss $\Loss$, start $\vtheta_0$, learning rate $\eta$, steps $T$
  2. for $t = 0,\dots,T-1$:
    1. $\vg_t \gets \nabla\Loss(\vtheta_t)$ compute the gradient
    2. $\vtheta_{t+1} \gets \vtheta_t - \eta\,\vg_t$ step downhill
  3. return $\vtheta_T$

Does each step really go down?

The Taylor approximation is only accurate for small steps, so we need to know how fast the slope can change. A loss is $L$-smooth if its gradient is $L$-Lipschitz, which for twice-differentiable functions means every eigenvalue of the Hessian lies in $[-L, L]$: the curvature is at most $L$.

Show derivation: the descent lemma

Smoothness gives a quadratic upper bound (proved in Appendix B):

$$\Loss(\vv) \le \Loss(\vu) + \nabla\Loss(\vu)\T(\vv-\vu) + \frac{L}{2}\norm{\vv-\vu}_2^2.$$

Plug in one gradient step, $\vv - \vu = -\eta\vg$ with $\vg = \nabla\Loss(\vu)$:

$$\Loss(\vtheta_{t+1}) \le \Loss(\vtheta_t) - \eta\norm{\vg}_2^2 + \frac{L\eta^2}{2}\norm{\vg}_2^2 = \Loss(\vtheta_t) - \eta\Big(1-\frac{L\eta}{2}\Big)\norm{\vg}_2^2. \tag{3.6}$$

Summing over $T$ steps with $\eta = 1/L$ gives $\min_{t < T}\norm{\nabla\Loss(\vtheta_t)}_2^2 \le 2L(\Loss(\vtheta_0)-\Loss^\star)/T$.

Key idea: the descent lemma

If $\Loss$ is $L$-smooth and $0 < \eta < 2/L$, every gradient step strictly decreases the loss unless the gradient is already zero. The guaranteed decrease is largest at $\eta = 1/L$.

3.3Choosing the Learning Rate

Take the simplest possible loss, $\Loss(w) = \tfrac{\lambda}{2}w^2$, whose curvature is $\lambda$. One step gives $w_{t+1} = w_t - \eta\lambda w_t = (1-\eta\lambda)w_t$, so $w_t = (1-\eta\lambda)^t w_0$. Everything depends on the factor $r = 1-\eta\lambda$:

Learning rateFactor $r$Behavior
$0 < \eta < 1/\lambda$$0 < r < 1$smooth, monotone convergence
$\eta = 1/\lambda$$r = 0$converges in one step
$1/\lambda < \eta < 2/\lambda$$-1 < r < 0$converges while oscillating
$\eta = 2/\lambda$$r = -1$bounces forever between $\pm w_0$
$\eta > 2/\lambda$$r < -1$diverges

Many dimensions: the condition number

For a quadratic $\Loss(\vw) = \tfrac12\vw\T\mA\vw$ with eigenvalues $\lambda_{\min}\le\dots\le\lambda_{\max}$, the update $\vw_{t+1} = (\mI - \eta\mA)\vw_t$ acts independently along each eigenvector: the coordinate along $\vu_j$ shrinks by $1-\eta\lambda_j$ per step. Stability needs $\eta < 2/\lambda_{\max}$, so the steepest direction sets the speed limit, while the flattest direction decides how long you wait. The best fixed step, $\eta^\star = 2/(\lambda_{\min}+\lambda_{\max})$, gives a worst-case contraction of

$$r^\star = \frac{\kappa-1}{\kappa+1}, \qquad \kappa = \frac{\lambda_{\max}}{\lambda_{\min}}. \tag{3.7}$$

The ratio $\kappa$ is the condition number. With $\kappa = 1$ the contours are circles and one step suffices. With $\kappa = 100$, $r^\star \approx 0.98$: each step removes only 2% of the remaining error, and GD zig-zags across a long, thin valley. Standardizing input features (Chapter 12) is often the cheapest way to shrink $\kappa$.

3.4Convexity

Definition 3.1 (Convex function)

$f:\R^p\to\R$ is convex if $f(\alpha\vu+(1-\alpha)\vv) \le \alpha f(\vu) + (1-\alpha)f(\vv)$ for all $\vu,\vv$ and $\alpha\in[0,1]$: every chord lies on or above the graph.

For differentiable $f$ two equivalent tests are easier to check: every tangent plane lies below the graph, $f(\vv)\ge f(\vu)+\nabla f(\vu)\T(\vv-\vu)$; or the Hessian is positive semidefinite everywhere.

Theorem 3.1

If $f$ is convex and differentiable, any point with $\nabla f(\vu^\star)=\mathbf 0$ is a global minimizer. Proof: the tangent-plane test at $\vu^\star$ gives $f(\vv)\ge f(\vu^\star)$ for every $\vv$.

So for convex losses there are no bad local minima. For an $L$-smooth convex loss, GD with $\eta=1/L$ reaches $\Loss(\vtheta_T)-\Loss^\star\le L\norm{\vtheta_0-\vtheta^\star}^2/(2T)$. If the loss is also $\mu$-strongly convex (Hessian eigenvalues at least $\mu>0$), the error shrinks geometrically like $(1-\mu/L)^T$.

Linear and logistic regression have convex losses. Neural networks do not, but their high-dimensional loss surfaces are friendlier than worst-case theory suggests: most critical points are saddles rather than poor local minima, and noisy gradient methods escape saddles. We return to this in Chapter 16.

3.5Stochastic and Mini-Batch Gradient Descent

The exact gradient $\nabla\Loss = \frac1n\sum_i\nabla\ell_i$ costs $n$ per-example gradients for a single step. Stochastic gradient descent (SGD) estimates it from a random mini-batch $B$:

$$\hat\vg = \frac{1}{|B|}\sum_{i\in B}\nabla\ell_i(\vtheta), \qquad \vtheta\gets\vtheta-\eta\,\hat\vg. \tag{3.8}$$

Two facts make this work:

  1. Unbiased. A uniformly sampled index gives $\E[\nabla\ell_i]=\nabla\Loss$, so $\E[\hat\vg]=\nabla\Loss$. On average SGD moves in the right direction.
  2. Variance shrinks like $1/|B|$. Averaging $|B|$ independent draws divides the covariance by $|B|$, so the noise in each coordinate falls like $1/\sqrt{|B|}$.

Intuition: polling instead of a census

A mini-batch gradient is an opinion poll. You do not need every voter to know which way the election leans. Quadrupling the sample only halves the error, so very large batches give diminishing returns per unit of computation.

In practice we shuffle once per epoch (one pass over the data) and cut the data into consecutive batches of 32 to a few thousand examples. With a constant learning rate, SGD keeps jittering in a region whose size grows with $\eta$ and with the gradient variance, which is why learning rates are decayed during training. The same noise helps escape saddle points and sharp minima.

3.6Momentum

On an ill-conditioned problem GD zig-zags because the gradient points mostly across the valley. Momentum keeps a velocity that accumulates past gradients:

$$\vv_{t+1} = \beta\vv_t + \nabla\Loss(\vtheta_t), \qquad \vtheta_{t+1} = \vtheta_t - \eta\,\vv_{t+1}. \tag{3.9}$$

Unrolled, $\vv_{t+1} = \sum_{k\ge0}\beta^k\nabla\Loss(\vtheta_{t-k})$: an exponentially weighted sum of past gradients, typically with $\beta = 0.9$.

Intuition: a heavy ball

Gradient components that keep flipping sign (across the valley) cancel in the sum. Components that keep pointing the same way (along the valley floor) add up. On a constant slope the velocity approaches $\vg/(1-\beta)$, so with $\beta = 0.9$ the ball moves ten times faster along a consistent direction.

For quadratics, well-tuned momentum improves the contraction factor from $(\kappa-1)/(\kappa+1)$ to about $(\sqrt\kappa-1)/(\sqrt\kappa+1)$. For $\kappa = 100$ that is 0.82 instead of 0.98 per step.

3.7Adaptive Methods: RMSProp and Adam

Momentum uses one learning rate for every parameter, but parameters often live on very different scales. RMSProp divides each coordinate's step by a running root-mean-square of its gradients:

$$\vs_{t+1} = \rho\vs_t + (1-\rho)\vg_t^2, \qquad \vtheta_{t+1} = \vtheta_t - \eta\,\frac{\vg_t}{\sqrt{\vs_{t+1}}+\epsilon},$$

with all operations element-wise. Adam (Kingma & Ba, 2015) combines this with momentum and corrects the start-up bias of both moving averages:

$$\begin{aligned} \vm_t &= \beta_1\vm_{t-1}+(1-\beta_1)\vg_t, \qquad & \vs_t &= \beta_2\vs_{t-1}+(1-\beta_2)\vg_t^2,\\ \hat\vm_t &= \frac{\vm_t}{1-\beta_1^t}, & \hat\vs_t &= \frac{\vs_t}{1-\beta_2^t},\\ \vtheta_t &= \vtheta_{t-1}-\eta\,\frac{\hat\vm_t}{\sqrt{\hat\vs_t}+\epsilon}. && \end{aligned} \tag{3.10}$$

Defaults: $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-8}$.

Show derivation: where the bias correction comes from

Starting from $\vm_0=\mathbf 0$ and unrolling, $\vm_t = (1-\beta_1)\sum_{k=1}^{t}\beta_1^{t-k}\vg_k$. If the gradients have a stationary mean $\E[\vg]$,

$$\E[\vm_t] = (1-\beta_1)\E[\vg]\sum_{k=1}^t\beta_1^{t-k} = (1-\beta_1)\E[\vg]\frac{1-\beta_1^t}{1-\beta_1} = (1-\beta_1^t)\E[\vg].$$

Dividing by $1-\beta_1^t$ removes the bias exactly; the same argument applies to $\vs_t$.

Key idea: what Adam's step size means

The ratio $\hat\vm_t/\sqrt{\hat\vs_t}$ is roughly "mean over root-mean-square" of recent gradients, so its magnitude is at most about 1 per coordinate. In Adam, $\eta$ is approximately the largest distance any parameter moves in one step, whatever the scale of the loss. That is why $\eta = 10^{-3}$ is a reasonable default across very different problems.

Adam and its variant AdamW (Chapter 16) are the default optimizers for Transformers and most modern deep learning.

3.8Newton's Method

Every method so far builds a linear model of the loss and steps along it, with a learning rate deciding how far to trust it. Newton's method uses second derivatives to build a quadratic model and jumps straight to its minimum. No learning rate is needed.

One dimension. To minimize $f$, find a zero of $f'$ by following its tangent line: $\theta_{t+1}=\theta_t-f'(\theta_t)/f''(\theta_t)$. Equivalently, $\theta_{t+1}$ minimizes the second-order Taylor model of $f$ at $\theta_t$.

Many dimensions. With gradient $\vg_t$ and Hessian $\mathbf H_t$, the model $\Loss(\vtheta_t)+\vg_t\T\vv+\frac12\vv\T\mathbf H_t\vv$ is minimized where $\mathbf H_t\vv=-\vg_t$:

$$\vtheta_{t+1}=\vtheta_t-\mathbf H_t^{-1}\nabla\Loss(\vtheta_t). \tag{3.11}$$

In code, solve $\mathbf H_t\vv=-\vg_t$; never form $\mathbf H^{-1}$.

  1. Quadratics in one step. For $\frac12\vtheta\T\mA\vtheta-\vb\T\vtheta$ one step lands on $\mA^{-1}\vb$, whatever the condition number. GD needs a number of steps proportional to $\kappa$.
  2. Invariance to scaling. Changing units $\vtheta=\mathbf T\vu$ maps Newton's iterates exactly onto each other, so no feature standardization is needed.
  3. Quadratic convergence. Near a minimizer with positive definite (Lipschitz) Hessian, $\norm{\vtheta_{t+1}-\vtheta^\star}\le c\norm{\vtheta_t-\vtheta^\star}^2$: correct digits double each step, $10^{-2}, 10^{-4}, 10^{-8}, 10^{-16}$.

Why it is not used everywhere. The Hessian has $p^2$ entries and the solve costs $O(p^3)$: cheap for logistic regression and GLMs (Chapter 6, Chapter 7), impossible for a network with $10^7$ parameters. Far from the minimum it can fail: with an indefinite Hessian the step can head for a saddle or maximum (Newton seeks $\nabla\Loss=\mathbf 0$, not a minimum), and full steps can overshoot. The fixes are a damped step $\vtheta_t-\alpha_t\mathbf H_t^{-1}\vg_t$ with a backtracking line search, and adding $\lambda\mI$ to an indefinite Hessian.

Quasi-Newton methods. BFGS approximates $\mathbf H^{-1}$ from differences of successive gradients; L-BFGS keeps only the last $m\approx10$ pairs ($O(mp)$ memory) and is scikit-learn's default solver for logistic regression. Adam's division by $\sqrt{\hat\vs}$ is a crude diagonal curvature correction, and recent optimizers such as Shampoo and Muon treat each weight matrix's gradient as a matrix rather than per coordinate.

3.9Implementing the Optimizers

All optimizers share one interface: take the parameters and gradient, return new parameters. We test them on $\Loss(\vw) = \frac12(w_1^2 + 25w_2^2)$, with $\kappa = 25$.

import numpy as np

A = np.diag([1.0, 25.0])                  # Hessian; kappa = 25
loss = lambda w: 0.5 * w @ A @ w
grad = lambda w: A @ w

class GD:
    def __init__(self, lr): self.lr = lr
    def step(self, w, g): return w - self.lr * g

class Momentum:
    def __init__(self, lr, beta=0.9): self.lr, self.beta, self.v = lr, beta, 0.0
    def step(self, w, g):
        self.v = self.beta * self.v + g
        return w - self.lr * self.v

class Adam:
    def __init__(self, lr, b1=0.9, b2=0.999, eps=1e-8):
        self.lr, self.b1, self.b2, self.eps = lr, b1, b2, eps
        self.m = self.s = 0.0
        self.t = 0
    def step(self, w, g):
        self.t += 1
        self.m = self.b1 * self.m + (1 - self.b1) * g
        self.s = self.b2 * self.s + (1 - self.b2) * g**2
        m_hat = self.m / (1 - self.b1**self.t)
        s_hat = self.s / (1 - self.b2**self.t)
        return w - self.lr * m_hat / (np.sqrt(s_hat) + self.eps)

def run(opt, w0=np.array([-4.0, 1.0]), steps=100):
    w, path = w0.copy(), [w0.copy()]
    for _ in range(steps):
        w = opt.step(w, grad(w))
        path.append(w.copy())
    return np.array(path)

for name, opt in [("GD", GD(0.07)), ("Momentum", Momentum(0.11, beta=0.44)),
                  ("Adam", Adam(0.3))]:
    path = run(opt)
    print(f"{name:9s} final loss = {loss(path[-1]):.2e}")

GD must keep $\eta$ below $2/25 = 0.08$ to stay stable, which makes progress along $w_1$ slow: after 100 steps its loss is about $4\times10^{-6}$. Momentum with the optimal settings for $\kappa = 25$, $\eta = 4/(\sqrt{\lambda_{\max}} + \sqrt{\lambda_{\min}})^2\approx 0.11$ and $\beta = \big((\sqrt\kappa - 1)/(\sqrt\kappa + 1)\big)^2\approx 0.44$, reaches about $10^{-28}$. Badly chosen momentum settings can be worse than plain GD, so $\beta$ and $\eta$ are tuned together.

3.10Common Pitfalls

Pitfall: a loss that goes up or becomes NaN

The learning rate is almost always too large for the current curvature. Divide $\eta$ by 3 and retry. If the loss explodes only late in training, use a learning-rate warm-up or gradient clipping (Chapter 16).

Pitfall: unscaled features

Meters next to millimeters stretch the loss surface and inflate $\kappa$. Standardize features to zero mean and unit variance first.

Pitfall: judging SGD by a single step

Mini-batch losses are noisy and can rise from one step to the next while training is going well. Watch a moving average, or a fixed validation set.

Pitfall: forgetting to shuffle

Sorted data (all cats, then all dogs) give biased mini-batches and oscillating training. Shuffle every epoch.

3.11Summary

  • Training a model means minimizing the average loss $\Loss(\vtheta)$.
  • Gradient descent steps against the gradient. For an $L$-smooth loss and $\eta < 2/L$, each step decreases the loss.
  • On a quadratic, GD acts independently along each Hessian eigenvector. Stability needs $\eta < 2/\lambda_{\max}$; speed is limited by $\kappa=\lambda_{\max}/\lambda_{\min}$.
  • For convex losses every stationary point is a global minimum.
  • SGD uses an unbiased mini-batch gradient whose variance falls like $1/|B|$.
  • Momentum averages gradients over time; Adam adds per-coordinate scaling and bias correction.
  • Newton's method jumps to the minimum of the local quadratic model, $\vtheta\gets\vtheta-\mathbf H^{-1}\nabla\Loss$: one step on quadratics, scale-invariant, quadratically convergent, but $O(p^3)$ per step; damping and L-BFGS make it robust and cheaper.

3.12Exercises

  1. ConceptualA colleague says, "My loss went from 0.52 to 0.53 on the last step, so my learning rate is too high." When is this conclusion justified, and when is it not?
  2. MathFor $\Loss(w)=\frac\lambda2(w-c)^2$, show that $w_t-c=(1-\eta\lambda)^t(w_0-c)$. How many steps reduce $|w_t-c|$ by $10^6$ when $\eta\lambda=0.1$? When $\eta\lambda=1.9$?
  3. MathShow that the optimal fixed learning rate for $\frac12\vw\T\mA\vw$ is $\eta^\star=2/(\lambda_{\min}+\lambda_{\max})$ by minimizing $\max_j|1-\eta\lambda_j|$, then derive Equation (3.7).
  4. MathProve that $f(\vw)=\norm{\mX\vw-\vy}_2^2$ is convex by computing its Hessian.
  5. MathLet $\hat\vg$ average $|B|$ independent draws of $\nabla\ell_i$ with $i$ uniform. Show that $\E\norm{\hat\vg-\nabla\Loss}^2 = \frac{1}{|B|}\cdot\frac1n\sum_i\norm{\nabla\ell_i-\nabla\Loss}^2$.
  6. CodingSweep $\eta$ from $10^{-3}$ to $1$ on a log grid for each optimizer above and plot the final loss after 100 steps. Which optimizer is least sensitive to $\eta$, and why?
  7. CodingRun GD on the Rosenbrock function $(1-x)^2+100(y-x^2)^2$ from $(-1.5, 2)$. Find the largest stable learning rate by experiment, then add momentum and count the steps to reach $f < 10^{-4}$.
  8. MathApply Newton's method to $\log\cosh\theta$: show the update is $\theta_{t+1}=\theta_t-\tfrac12\sinh(2\theta_t)$ and find numerically which starting values converge. Then show that on $\theta^4/4$ the iterates satisfy $\theta_{t+1}=\tfrac23\theta_t$, and explain why convergence is only linear.
Machine Learning from First Principles · Edition 2.0 · Companion site to the PDF book.