gradient descent

you're blindfolded on a hill.find the lowest point

you can't see a thing. all you can feel is the ground sliding away under your feet. tap where to step. you get 6 steps

height: 5.38
steps left: 6

that hill was a line

every spot on the hill is one line through these points. each square shows how wrong the line is about one point, and your height was their average size. shrink them

the hill is every possible line, and height is how wrong each one is

the line. drag its 2 handles

the same line, as a spot on the hill. drag the dot

from the sidefrom above

tilt-0.60

height0.30

error5.38

this is the hill you were standing on. slide to look down from above

go deeper

why squares?

a miss above the line and a miss below it would cancel out if you just added them. squaring makes every miss count, makes big misses hurt far more, and gives a smooth hill with a clear tilt everywhere. it's a choice, not a law. absolute error is common too

\text{error}(m, b) = \frac{1}{n} \sum_{i=1}^{n} (m x_i + b - y_i)^2

why can't a model just look at the whole map?

this hill has 2 directions. a real model has millions, one for each number it can adjust. checking just 10 spots along 100 directions is already $10^{100}$ spots, far more than the roughly $10^{80}$ atoms in the observable universe. so a real model is always blindfolded

why is it a perfect bowl?

the error squares every miss, and each miss is a straight-line function of the tilt and height. that always makes a bowl with one bottom, as long as the points don't all share the same x. a neural network's hill has ridges, plains and many valleys

why is the bowl stretched?

changing the tilt hurts twice as fast as changing the height here, because the points are spread out along x

\frac{\partial^2 \text{error}}{\partial m^2} = \frac{2}{n}\sum x_i^2 = 4 \qquad \frac{\partial^2 \text{error}}{\partial b^2} = 2

if there's a bottom, why not just solve for it?

for a line you can, and this formula lands on it in one go:

m^* = \frac{\sum (x_i - \bar{x})(y_i - \bar{y})}{\sum (x_i - \bar{x})^2} \qquad b^* = \bar{y} - m^*\bar{x}

gradient descent earns its keep when no such formula exists, or the model is too big to use one. that covers nearly every neural network

which way is downhill?

the model can't see this map. it can only nudge each number a tiny bit and feel whether the error drops. those nudges are called the gradient. guess first, then check

the gradient is which way the error rises. so you walk the other way

nudge the tilt: error changes by-0.065

nudge the height: error changes by-0.006

error5.38

tap around the dot: which way do you think is downhill?

go deeper

the actual calculus

a nudge that's infinitely small is a derivative. for this error:

\frac{\partial \text{error}}{\partial m} = \frac{2}{n}\sum (m x_i + b - y_i)\,x_i

\frac{\partial \text{error}}{\partial b} = \frac{2}{n}\sum (m x_i + b - y_i)

and all of gradient descent is one line:

\theta_{\text{next}} = \theta - \eta \, \nabla \text{error}(\theta)

is downhill the same as toward the bottom?

no, and this is the surprise. on a stretched bowl the steepest way down usually doesn't point at the bottom. the gradient only knows the ground under your feet. "steepest" also depends on your units: measure the tilt differently and the map stretches

every point gets a say

each point pulls the line toward itself, and the worse the miss, the harder the pull. add up all the pulls and you get the direction. drag a point

the direction comes from the data. the worst misses pull hardest

touch a part of the equation to see what it does

\text{pull}_i = -\htmlClass{term-share}{\frac{2}{n}} \cdot \htmlClass{term-miss}{r_i} \cdot \htmlClass{term-lever}{\begin{bmatrix} x_i \\ 1 \end{bmatrix}}

drag the points

what each point wants

where that sends the line

total6.46, 0.58

error5.38

point 5 is pulling hardest, with 44% of the pulling. touch the equation to see why

how big a step?

the direction says which way, not how far. too small takes forever. too big makes things worse with every step. this one setting matters more than almost anything

the gradient says which way. the step size decides if it works at all

every step, on the map

the error at each step

step: 0
error: 5.377
step size: 0.080
the limit here: 0.500

step size

small steps. safe, and slow

go deeper

where does the limit come from?

in the steepest direction, with curvature $\lambda$ , each step multiplies your distance from the bottom by $1 - \eta\lambda$ . bigger than 1 in size means you're moving away, so:

\eta < \frac{2}{\lambda_{\max}} = \frac{2}{4} = 0.5

at exactly 0.5 that number is -1, so the tilt flips side to side forever

why does wobbly still get there?

between 0.25 and 0.5, each step overshoots the bottom along the tilt, but lands closer than it started. at 0.25 exactly, the tilt lands on the bottom in one step

how do people pick it in practice?

mostly by trying. a common recipe: start small, raise it until the error blows up, then back off. it also usually shrinks during training, so you take big steps early and careful ones at the end

what goes wrong

that bowl was friendly. real hills are messier, in 3 ways

flat doesn't mean finished, steep walls slow you down, and every step is a guess

when one direction is much steeper, you bounce between the walls instead of moving forward

stretch the data

steeper one way by50×

steps to reach the bottom49

the steep walls force tiny steps, so it bounces across and crawls forward

go deeper

why is a stretched valley slow?

the step size has to suit the steepest direction, and progress is limited by the gentlest. their ratio is the condition number:

\kappa = \frac{\lambda_{\max}}{\lambda_{\min}} \qquad \text{steps} \propto \kappa

how do real systems deal with it?

normalising inputs and batch normalisation round the bowl. momentum and adam work around the shape without changing it. newton's method uses the curvature directly, but it's far too expensive for a model with billions of numbers

are bad valleys a real problem?

less than people once feared. in millions of dimensions, a true dead end needs the ground to rise in every direction at once, and most flat spots turn out to be saddles. slow progress near them is the more common problem

the hill on the "stuck" tab

f(a, b) = (a^2 - 1)^2 + 0.4\,b^2

your turn

a new hill with 2 valleys, and the settings people really tune. drag the ring, turn the dials, or try a preset. the hill is made up. every step is real

every optimiser is a different answer to one question: how should i step?

calm and reliable, and it stops at the first bottom it meets. settled in the shallow valley, 1.32 above the deep one

learning rate0.0500momentum0.90batch sizeall data

hover or turn a dial to see what it does

height over time

go deeper

the update rules

momentum keeps a running speed:

v_{t+1} = \beta v_t + g_t \qquad x_{t+1} = x_t - \eta v_{t+1}

rmsprop divides by the recent size of the slope:

s_{t+1} = \beta_2 s_t + (1-\beta_2) g_t^2

x_{t+1} = x_t - \frac{\eta\, g_t}{\sqrt{s_{t+1}} + \epsilon}

adam does both, and corrects for starting at zero

which optimiser should i use?

adam is a solid first choice, and forgiving about the learning rate. plain sgd with momentum is still widely used and can generalise better, but needs more tuning. don't read too much into one hill: no optimiser wins everywhere

what's simplified here?

this hill is 1 dimensional, and batch noise is simulated as random error added to the slope, shrinking with batch size. in real training the noise comes from which examples you sampled. adam's real strength, a step size for every number, can't show up with only one number

so, what is gradient descent?

it's how a machine gets less wrong, one small step at a time

measure how wrong you are. find which way is less wrong. take a small step. repeat. that's how nearly every neural network on earth learns

step0

error5.377

the same bad line you started with, learning by itself. it gets to 0.076, the best any straight line can do

cheat sheet, code and further reading

cheat sheet

error: one number for how wrong the model is
gradient: which way the error rises fastest, one number per setting
update: $\theta \leftarrow \theta - \eta\,\nabla \text{error}(\theta)$
step size: stable below $2 / \lambda_{\max}$ on a bowl
slow training: a stretched valley. normalise your inputs
flat: can be a saddle or a top, not just a bottom
batches: noisier steps, far cheaper, how everything is really trained
momentum: keep some speed, roll past small bumps
adam: momentum plus a step size for each setting. a good default

the entire algorithm, in code you can run

import numpy as np

x = np.array([-2, -1, 0, 1, 2], dtype=float)
y = np.array([-1.5, -0.25, 0.7, 1.1, 2.9])

m, b = -0.6, 0.3   # a bad guess
rate = 0.2         # the step size

for step in range(50):
    miss = m * x + b - y           # how wrong is each point?
    grad_m = 2 * np.mean(miss * x) # which way is uphill?
    grad_b = 2 * np.mean(miss)
    m -= rate * grad_m             # step the other way
    b -= rate * grad_b

print(m, b)  # 1.015 0.59

where to go next

why momentum really worksgabriel goh, distill, 2017
an overview of gradient descent optimization algorithmssebastian ruder, 2016
adam: a method for stochastic optimizationkingma and ba, 2014
identifying and attacking the saddle point problemdauphin et al, 2014
learning representations by back-propagating errorsrumelhart, hinton and williams, 1986
optimization for training deep modelsgoodfellow, bengio and courville, deep learning, chapter 8