Back to the on-screen lesson ·
The step, the step size that decides between crawling and diverging, and why steepest is not fastest.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to take a gradient descent step by hand, say why the step goes against the gradient, and analyse on a quadratic exactly which step sizes converge, which land in one step, which oscillate and which diverge. You will also be able to explain why the method zig-zags on a badly conditioned problem, name the condition number as what governs its speed, and say what the method promises with and without convexity.
From lesson 10: at a minimum the gradient vanishes, and the argument for that named $-\nabla f$ as a direction that improves. That direction is the method. What is new is everything around it — how far to go, when to stop, and why the answer to 'how far' is harder than it looks.
Iterate: the current point $x_k$. A method is a rule for producing the next one.
Descent direction: a direction along which the objective falls, at least for a short distance. The negative gradient is one.
Step size (learning rate) $t$: how far to move along that direction.
Update rule: $x_{k+1} = x_k - t\nabla f(x_k)$.
Level set: the points sharing one objective value. Long thin level sets are what make descent zig-zag.
Condition number: how stretched those level sets are — the ratio of the largest curvature to the smallest.
Convergence: approaching the minimiser in the limit. Gradient descent converges to an answer and does not arrive at one, which is why a stopping rule is part of the method.
The method. From a point $x_k$,
$$x_{k+1} = x_k - t_k \nabla f(x_k).$$
That is all of it. The gradient points in the direction of steepest increase, so its negative is the direction of steepest decrease, and $t_k > 0$ is the step size (or learning rate).
Why it descends. For small enough $t$,
$$f(x - t\nabla f(x)) \approx f(x) - t\,\|\nabla f(x)\|^2 < f(x)$$
whenever the gradient is non-zero. The guarantee is only for small enough $t$, and the qualification is the whole difficulty: too small and the method crawls, too large and it overshoots and can diverge.
What it promises. On a convex $f$, it converges to the global minimum. On a non-convex $f$, it converges to a stationary point — which by lesson 10 may be a saddle, and by lesson 9 may be one of many local minima. The method does not know which case it is in; you do, from having checked convexity beforehand.
Steepest is not fastest. The negative gradient is the best direction for an infinitesimal step. Over a real step it can be badly wrong. On $f(x,y) = x^2 + 100y^2$ the level sets are long thin ellipses, the gradient points across the valley rather than along it, and the iterates zig-zag down while making very little progress towards the minimum. The ratio of the widest to the narrowest curvature — the condition number — governs the speed, and lessons 15 to 17 are three different answers to it.
Another way: picture
Contour lines like a long narrow valley seen from above, with a path drawn on them. The path crosses from one wall to the other and back, each crossing advancing only slightly along the valley. That zig-zag is what a badly conditioned problem does to gradient descent, and it is not a bug in the implementation.
Another way: steps
To run gradient descent:
On $f(x) = ax^2$ with $\nabla f = 2ax$, a step of size $t$ gives
$$x_{k+1} = x_k - 2at\,x_k = (1 - 2at)\,x_k.$$
So each step multiplies the position by $1 - 2at$, and the behaviour is decided by that one number:
| $1 - 2at$ | Behaviour |
|---|---|
| between $0$ and $1$ | converges steadily, no overshoot |
| exactly $0$ | lands on the minimum in one step |
| between $-1$ and $0$ | oscillates about the minimum, converging |
| less than $-1$ | oscillates and diverges |
The threshold is $t = 1/a$: past it the method blows up, on a perfectly convex problem, with a correct gradient. Nothing about convexity protects an implementation from a step size that is too large, and "the loss went to infinity" almost always means this rather than a modelling error.
The sign. $x + t\nabla f$ climbs. It is one character and it silently maximises.
A fixed step size on a badly conditioned problem. The step is limited by the narrowest direction and the distance by the widest, so progress is governed by their ratio. Scaling the variables so they have comparable ranges is the cheapest fix there is.
Stopping on the step length. Small steps can mean a small gradient or a small step size. Stop on the gradient, or on the improvement, and say which.
Expecting exact arrival. The method converges to the minimum and does not reach it. The stopping tolerance is part of the answer and belongs in the report.
The name suggests it should be, and it is: for an infinitesimally short step. Over any real step the guarantee evaporates, and on a stretched valley the steepest direction points almost perpendicular to where the minimum lies. The mental picture worth replacing is water running downhill — water is taking infinitesimal steps, and it does follow the steepest path, and it also takes a very long time to reach the bottom of a long shallow valley. Everything in the next three lessons is about choosing a direction that is worse locally and better over the step you are actually going to take.
$f(x) = x^2$, so $\nabla f = 2x$, starting at $x_0 = 1$. With $t = 0.1$: $x_1 = 0.8$, $x_2 = 0.64$ — each step multiplies by $0.8$, steady and slow.
Too small: it works and crawls.
With $t = 0.5$: $x_1 = 1 - 1 = 0$. Exactly the minimum, in one step, because $1 - 2t = 0$.
Exactly right, for this problem only.
With $t = 1.1$: $x_1 = 1 - 2.2 = -1.2$, then $x_2 = 1.44$, then $-1.728$. Growing oscillations on a convex quadratic with a correct gradient — the method diverges, and only the step size is to blame.
Too large: divergence, not slowness.
Minimise $f(x,y) = x^2 + 100y^2$. The curvatures are $2$ and $200$, a condition number of $100$.
A long thin valley.
Stability needs $t < 1/100$, set by the steep direction. But the shallow direction only shrinks by a factor $1 - 2t \approx 0.98$ per step, so it takes hundreds of steps.
One direction sets the limit, the other sets the distance.
Substituting $u = 10y$ gives $x^2 + u^2$: condition number $1$, and one step of $t = 0.5$ finishes it. Nothing about the problem changed except the units the second variable is measured in — which is why scaling is checked before any cleverer method is reached for.
A change of units, not of method.
Gradient at $4$: $6 \times 4 = 24$. Step: $4 - 24/12 = 4 - 2 = 2$.
Gradient, then step.
Gradient at $2$: $6 \times 2 = 12$. Step: $2 - 12/12 = 1$.
So $4 \to 2 \to 1$: each step halves the position, since $1 - 2at = 1 - 2 \cdot 3 \cdot \tfrac1{12} = \tfrac12$. The objective falls $48 \to 12 \to 3$, a quarter each time — the value falls as the square of the position, which is why progress looks fast early and slow later.
Match each gradient-descent observation to the correct action or conclusion.
| Step in the negative gradient direction | Reduce or reselect the step size | Expect zig-zagging and slow convergence | |
|---|---|---|---|
| $\nabla f(x)$ | |||
| The objective rises after a step | |||
| Long, thin level sets |
Minimise $2x^2$ by gradient descent from $x = 6$ with step size $1/4$. Complete the trace of the first step.
| $x$ | gradient there | objective there | |
|---|---|---|---|
| Start | 6 | ||
| After one step |
At $x = 7$ the derivative of $7x^2$ is positive. Which way should a minimising step go?
| Move in the negative coordinate direction | Move in the positive coordinate direction | A stationary-point candidate | Subtract a positive multiple of the gradient | |
|---|---|---|---|---|
| Derivative is positive | ||||
| Derivative is negative | ||||
| Gradient is zero | ||||
| A gradient-descent step |
Gradient descent on $f(x) = 5x^2$ with a fixed step size $t$ sends $x$ to $(1 - 2 \times 5 t)\,x$ at every step. For which $t > 0$ does it converge to the minimum? Give the set.
This task has no paper form; do it on a device.
On $f(x,y) = x^2 + 70y^2$ gradient descent takes many small steps. Why?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
On $f(x,y) = x^2 + 73y^2$ gradient descent takes many small steps. Why?
You can take a descent step, predict what a given step size will do on a quadratic, and explain the zig-zag. Next: choosing the step size rather than guessing it.
10. Your turn: two steps on $f(x) = 3x^2$ from $x = 4$ with $t = 1/12$, step 3