Lecture 31 · Regression: computational considerations

Gradient Descent and Stochastic Gradient Descent

The closed form $w^\star=(XX^\top)^{+}Xy$ needs a $d\times d$ matrix inverse, which costs about $d^3$ operations, too slow for millions of features. Gradient descent reaches the same $w^\star$ by repeated small steps, with no inverse. When the number of data points $n$ is also huge, stochastic gradient descent uses a small random batch per step.

Source: this lecture on YouTube (≈25 min). Previous: L30 · Next: L32.

1 · The problem: the inverse is expensive

Inverting the $d\times d$ matrix $XX^\top$ takes roughly $O(d^3)$ time, as hard as computing PCA's eigenvectors. With a billion features, it's out of reach. But $w^\star$ is the minimiser of an unconstrained function, so general-purpose minimisation tools also find it.

2 · Gradient descent: walk downhill

The gradient points in the direction where the function increases fastest. So step the opposite way, scaled by a step size $\eta_t$:

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

With a good step size, repeating this reaches a point where the gradient is 0: a local minimum. For a wiggly function, that may not be the global minimum.
The squared error is a quadratic, which is convex: one bowl, so every local minimum is the global one. Gradient descent reaches $w^\star$ from any start.

For linear regression, $\nabla f(w)=2XX^\top w-2Xy$, so:

$$w_{t+1}=w_t-\eta_t\big(2XX^\top w_t-2Xy\big)\qquad\text{(no inverse anywhere)}$$ The 2 can be absorbed into $\eta_t$ (or avoided by putting a ½ in front of the error). This works even with millions of features.

3 · When n is huge too: stochastic gradient descent

Each gradient step still involves $XX^\top$, which is built from all $n$ points. With hundreds of millions of points, even one gradient is costly. SGD's idea: pretend a small random batch is the whole dataset for one step.

for t = 1 … T:
sample k points uniformly at random (k = batch size, e.g. 100)
w_t+1 = w_t − η_t · ( 2 X̃X̃⊤w_t − 2 X̃ỹ ) (X̃: d × k matrix of the sampled points)
output the average of the iterates: w̄ = (1/T) Σ_t w_t

A different random batch each round gives a noisy version of the true gradient. On average the noise cancels, and SGD heads towards the same $w^\star$, with high probability.
Output the average of the iterates, not the last one: a single unlucky last batch can push the final $w_T$ off course.
Batch size k: smaller is cheaper per step but noisier, so it needs more rounds.

Fitting $y \approx b + m\,x$ to 200 noisy points (true $b = 1$, $m = 2$). The shading is the average squared error over $(b, m)$; darker means lower. Both methods start from the same point and take 60 steps. (Errors are averaged rather than summed, which only rescales the step size.)

step size η = SGD batch size k =

gradient descent (all 200 points per step)SGD path (k points per step)SGD average of iteratesw* (closed form)

–

GD final error

–

SGD last iterate

–

SGD average

–

best possible (w*)

4 · Summary of the trade-offs

Method	Main cost	Good when
Closed form $(XX^\top)^+Xy$	forming $XX^\top$ and inverting it: $O(nd^2+d^3)$	small $d$: one exact answer
Gradient descent	each step uses all $n$ points; no inverse	large $d$, moderate $n$
SGD	each step uses only $k$ points	large $d$ and large $n$. The everyday workhorse.

Key takeaways

The closed form needs an $O(d^3)$ inverse, impractical for huge $d$.
Gradient descent $w_{t+1}=w_t-\eta\nabla f(w_t)$ avoids the inverse. The squared error is convex, so it reaches the global minimum.
SGD uses a random batch of $k$ points per step, making each step cheap even for huge $n$. Average the iterates for the final answer.
The batch size trades cost per step against noise and the number of steps needed.