Gradient descent
Tonight's idea
You are on a hillside in fog. You cannot see the valley floor, but you feel the slope under your feet. Step downhill, feel again, repeat. That is gradient descent, and it is how machine-learning models are trained.
In one variable the slope is \(f'(x)\) and the step is
\(x_{\text{new}} = x - \eta\, f'(x)\).
The number \(\eta\) (eta) is the step size; the minus sign sends you downhill.
In two variables the gradient \(\nabla f = (f_x, f_y)\) collects the two partial slopes (\(f_x\) is the derivative in \(x\) with \(y\) held fixed). It points straight uphill, so step against it: \((x, y) \leftarrow (x, y) - \eta \nabla f\).
The step size decides everything. For \(f = x^2 + 3y^2\), \(\nabla f = (2x, 6y)\), so one step sends \(x\) to \((1 - 2\eta)x\) and \(y\) to \((1 - 6\eta)y\): each coordinate is multiplied by a fixed factor every step. A factor between \(-1\) and \(1\) shrinks it; beyond \(\pm 1\) it blows up. The steeper \(y\)-direction breaks first: once \(\eta > \tfrac13\), \(|1 - 6\eta| > 1\) and the iterates fly off. For \(\tfrac16 \lt \eta \lt \tfrac13\) the factor is negative: \(y\) overshoots the floor and lands on the far side. Shrinking, but zig-zagging.
Watch one: \(\eta = 0.3\) from \((4, 1)\)
The factors are \(1 - 0.6 = 0.4\) for \(x\) and \(1 - 1.8 = -0.8\) for \(y\). So
\[(4, 1) \to (1.6, -0.8) \to (0.64, 0.64) \to (0.256, -0.512) \to (0.1024, 0.4096).\]
The \(x\)-coordinate drops fast; the \(y\)-coordinate flips sign every step and loses only 20%. That is the zig-zag in the figure. Now nudge \(\eta\) to \(0.34\): the \(y\)-factor becomes \(-1.04\) and the \(y\) values run \(1, -1.04, 1.08, -1.12, \dots\), growing without end while \(x\) still converges. The method has diverged, and the only cure is a smaller step.
Click a start point and drag the step size: mathdetours.com/demos/gradient.html.
Your turn
- Take \(f(x) = (x - 3)^2\), start at \(x_0 = 0\) and use \(\eta = 0.25\). Compute \(x_1\), \(x_2\), \(x_3\). What fraction of the remaining distance to 3 does each step cover?
- Same \(f\), same start. Compute three steps with \(\eta = 1\), then three with \(\eta = 1.1\). Describe what happens in each case. For which \(\eta\) does the method converge from every start?
- For \(f = x^2 + 3y^2\), start at \((4, 1)\) with the small step \(\eta = 0.1\). Compute two steps. Which coordinate is converging faster, and why is that the opposite of the picture above?
- For \(f = x^2 + 3y^2\): (a) find every \(\eta\) for which both coordinates shrink from any start; (b) find the \(\eta\) that makes the slower coordinate shrink fastest. (Hint: the two factors are \(1 - 2\eta\) and \(1 - 6\eta\). Sketch their absolute values against \(\eta\).)
Stretch: the long narrow valley
Now \(f = x^2 + 100y^2\). Find the best \(\eta\) in the sense of question 4(b), the shrink factor it gives the \(x\)-coordinate, and roughly how many steps are needed to divide \(x\) by 1000. Why do machine-learning people dread valleys like this?
Answers
- \(f'(x) = 2(x - 3)\), so \(x_{\text{new}} = x - 0.5(x - 3)\): \(x_1 = 1.5\), \(x_2 = 2.25\), \(x_3 = 2.625\). Each step covers exactly half the remaining distance: the factor on \(x - 3\) is \(1 - 2\eta = 0.5\).
- With \(\eta = 1\): \(6, 0, 6, \dots\), bouncing forever between 0 and 6 (factor \(-1\)). With \(\eta = 1.1\): \(6.6, -1.32, 8.184\), growing (factor \(-1.2\)). The method converges when \(|1 - 2\eta| \lt 1\), that is \(0 \lt \eta \lt 1\).
- Factors \(0.8\) and \(0.4\): \((4, 1) \to (3.2, 0.4) \to (2.56, 0.16)\). The \(y\)-coordinate converges faster. With a small step the steep direction is a help, because the gradient there is large and each step is long. The zig-zag only appears once \(\eta\) passes \(\tfrac16\), where the step in \(y\) overshoots.
- (a) Need \(|1 - 2\eta| \lt 1\) and \(|1 - 6\eta| \lt 1\), that is \(0 \lt \eta \lt 1\) and \(0 \lt \eta \lt \tfrac13\). Both hold for \(0 \lt \eta \lt \tfrac13\). (b) The slower coordinate has the larger of \(|1 - 2\eta|\) and \(|1 - 6\eta|\). The first falls as \(\eta\) grows, the second rises again after \(\eta = \tfrac16\); the maximum is smallest where they are equal and opposite, \(1 - 2\eta = 6\eta - 1\), so \(\eta = \tfrac14\). Both factors are then \(\pm\tfrac12\): the distance to the bottom halves every step.
Stretch. Factors \(1 - 2\eta\) and \(1 - 200\eta\). Equal and opposite when \(1 - 2\eta = 200\eta - 1\), so \(\eta = \tfrac{1}{101}\). The \(x\)-factor is \(1 - \tfrac{2}{101} = \tfrac{99}{101} \approx 0.980\): \(x\) loses only 2% a step. Dividing by 1000 needs \(n\) with \((0.980)^n = 0.001\), so \(n = \ln 1000 / \ln(101/99) \approx 345\) steps. The steep direction forces a tiny step, and the flat direction then crawls. Real models have millions of directions, and the ratio of steepest to flattest (the condition number) decides how slowly they train.