Week 1: Optimization for Learning

What Is Optimization for Learning#

Every machine learning model — whether a linear regressor, a decision tree, or a billion-parameter transformer — starts from the same template: choose a model $f_\theta$ parameterised by a vector $\theta$, measure how wrong it is with a loss $\ell(\hat y, y)$, and average that loss over a dataset of $n$ examples. The result is the objective function (also called the cost or the empirical risk):

$J(\theta) = \frac{1}{n} \sum_{i=1}^n \ell(f_\theta(x_i), y_i)$

"Training" the model means finding the $\theta$ that makes $J(\theta)$ as small as possible:

$\theta^* = \arg\min_\theta J(\theta)$

This is exactly an optimization problem. The entire machinery of this course — convexity, gradient methods, convergence rates — exists to solve equation $(\ast)$ efficiently and reliably for the kinds of objectives that appear in machine learning.

Why not just set the derivative to zero and solve? For a linear model with squared error loss, you can (that is Week 4's closed-form solution). But for most modern models — deep nets, tree ensembles, generative models — $J(\theta)$ is a complicated, nonconvex function of millions of parameters. There is no closed form. The only practical route is to start somewhere and take small steps downhill.

Empirical Risk Minimization#

The name ERMEmpirical Risk Minimization captures the idea: we empirically measure risk on the data we have, then minimise it. Two things matter:

1. The loss $\ell(\hat y, y)$ encodes what "wrong" means. For regression, $\ell(\hat y, y) = (\hat y - y)^2$ (squared error). For classification, $\ell$ is cross-entropy (Week 5).
2. The data $\{(x_i, y_i)\}$ is a finite sample from some unknown distribution. ERM minimises the average on this sample, hoping it generalises to the distribution.

The rest of this course focuses on the minimisation part. The generalisation part (why minimising training loss also minimises test loss) belongs to statistical learning theory, though we will touch it when we discuss overparameterisation in Week 13.

Worked example — Linear regression as ERM:

Take $\theta = w \in \mathbb{R}^d$, model $f_w(x) = w^T x$, and squared error loss $\ell(\hat y, y) = (\hat y - y)^2$. Then

$J(w) = \frac{1}{n}\sum_{i=1}^n (w^T x_i - y_i)^2 = \frac{1}{n}\|Xw - y\|_2^2$

where $X \in \mathbb{R}^{n \times d}$ stacks the $x_i$ as rows and $y \in \mathbb{R}^n$ stacks the labels. This is a convex quadratic in $w$ — one of the nicest possible ERM problems. We will exploit that niceness in Weeks 3–4.

Gradients and the Chain Rule#

To take steps downhill, we need to know which direction is down. For a scalar-valued function $f: \mathbb{R}^d \to \mathbb{R}$, the gradient $\nabla f(x)$ is the vector of partial derivatives:

$\nabla f(x) = \begin{pmatrix} \frac{\partial f}{\partial x_1}(x) \\ \vdots \\ \frac{\partial f}{\partial x_d}(x) \end{pmatrix}$

At any point $x$, $\nabla f(x)$ points in the direction of steepest ascent. So $-\nabla f(x)$ points downhill.

The chain rule for vector functions is the workhorse of modern ML. Suppose $f(x) = g(h(x))$ where $h: \mathbb{R}^d \to \mathbb{R}^p$ and $g: \mathbb{R}^p \to \mathbb{R}$. Then

$\nabla f(x) = \nabla h(x)^T \, \nabla g(h(x))$

where $\nabla h(x)$ is the $d \times p$ Jacobian of $h$.

Worked numeric example — Quadratic gradient:

Let $f(w) = \frac{1}{2}(w_1^2 + 2 w_2^2)$. The gradient is

$\nabla f(w) = \begin{pmatrix} \frac{\partial f}{\partial w_1} \\ \frac{\partial f}{\partial w_2} \end{pmatrix} = \begin{pmatrix} w_1 \\ 2 w_2 \end{pmatrix}$

At $w = (4, 4)$, we have $\nabla f(4,4) = (4, 8)$. The function is steeper in the $w_2$ direction.

Chain rule worked example — Linear regression gradient:

With $f(w) = \frac{1}{2}\|Xw - y\|_2^2$, let $r = Xw - y$ (the residual). Then $f = \frac{1}{2}\|r\|_2^2 = \frac{1}{2}r^T r$. By the chain rule:

$\nabla f(w) = X^T(Xw - y)$

For a single data point $f_i(w) = \frac{1}{2}(w^T x_i - y_i)^2$, we get $\nabla f_i(w) = (w^T x_i - y_i) x_i$ — a scalar times the feature vector. This simple form is why SGD (Week 6) is cheap per example.

Gradient Descent#

The gradient descent algorithm is wonderfully simple: start at $x_0$, then repeatedly move a small step in the negative gradient direction:

$x_{k+1} = x_k - \eta \nabla f(x_k)$

where $\eta > 0$ is the step size (also called the learning rate).

Choosing $\eta$ is the central tuning problem. Too small and you crawl toward the minimum (underfitting in training-budget terms). Too large and you overshoot, possibly diverging.

Worked manual iteration — 2D quadratic:

Take $f(w_1, w_2) = \frac{1}{2}(w_1^2 + 2 w_2^2)$ with gradient $\nabla f(w) = (w_1, 2w_2)$. Start at $w^{(0)} = (4, 4)$ with $\eta = 0.3$.

• $k = 0$: $w^{(0)} = (4, 4)$, gradient $= (4, 8)$
• Step: $w^{(1)} = (4, 4) - 0.3 \cdot (4, 8) = (2.8, 1.6)$
• $k = 1$: gradient at $(2.8, 1.6)$ is $(2.8, 3.2)$
• Step: $w^{(2)} = (2.8, 1.6) - 0.3 \cdot (2.8, 3.2) = (1.96, 0.64)$

The objective values: $f(4,4) = 24$, $f(2.8, 1.6) = 6.48$, $f(1.96, 0.64) = 2.33$. The minimum is $f(0,0) = 0$, and we're getting closer every step.

Notice that $w_2$ shrinks faster than $w_1$ because its gradient component is twice as large. This direction-dependent convergence speed is a preview of the condition-number story in Week 4.

Reading Loss Curves#

Plot $f(x_k)$ against iteration $k$. A healthy GD run shows a smooth, monotonically decreasing curve that flattens as it approaches the minimum:

• Smooth decrease: The step size is working; the gradient is driving consistent progress.
• Plateau: The curve is nearly flat. Either the gradient is very small (you're near the minimum) or the step size is too conservative.
• Oscillation: The curve bounces up and down. The step size may be too large — you're overshooting the valley floor each iteration.
• Divergence: The curve rises steadily. $\eta$ is far too large; the descent lemma (Week 3) is violated.

A useful diagnostic: if the loss drops quickly for the first few iterations then plateaus far from zero, you may be stuck in a shallow region. Try increasing $\eta$ slightly or adding momentum (Week 7).

Browser lab#

Perform gradient descent on a 2D quadratic $f(x,y) = x^2 + 2y^2$ and visualise the iterate trajectory overlaid on the loss contour.

import numpy as np
import matplotlib.pyplot as plt

def f(x, y):
    return 0.5 * (x**2 + 2 * y**2)

def grad(x, y):
    return np.array([x, 2 * y])

eta = 0.3
n_steps = 12
xy = np.array([4.0, 4.0])
path = [xy.copy()]

for _ in range(n_steps):
    xy = xy - eta * grad(*xy)
    path.append(xy.copy())

path = np.array(path)

xs = np.linspace(-5, 5, 200)
ys = np.linspace(-5, 5, 200)
X, Y = np.meshgrid(xs, ys)
Z = f(X, Y)

fig, ax = plt.subplots(figsize=(6, 5))
ax.contour(X, Y, Z, levels=20, cmap="viridis", alpha=0.7)
ax.plot(path[:, 0], path[:, 1], "o-", color="tab:red", markersize=4, label="GD iterates")
ax.plot(0, 0, "x", color="black", markersize=10, label="optimum (0,0)")
ax.set_xlabel("x")
ax.set_ylabel("y")
ax.set_title(f"GD with η={eta} on f(x,y) = ½(x² + 2y²)")
ax.legend()
ax.set_aspect("equal")
plt.show()

print("Final position:", path[-1])
print("Final loss:", f(*path[-1]))