Home / MLF / Week 7

Week 7 · Finding the lowest point: gradient descent

Official syllabus line: Unconstrained Optimisation

About 80 minQuiz 2 material (see exam radar)BSCS2004 · Harish Guruprasad Ramaswamy, Arun Rajkumar, Prashanth LA

Before you start: Week 2 (gradient) and week 5 (positive definite matrices).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine you're blindfolded on a foggy hillside, trying to find the lowest point. You can't see, but you feel the ground's slope. To go down, you take tiny steps in the steepest downhill direction. You repeat this, stepping, feeling, stepping, until the ground feels perfectly flat and you know you've found the bottom. This simple idea helps machines learn!
This process is called gradient descent. It's how almost every machine learning model learns. We define a 'wrongness' score, called the objective function, and then steadily 'walk' it downhill. Each step uses the gradient to find the steepest downhill path. We subtract the gradient, multiplied by a small learning rate, to move towards the minimum, until the gradient is zero.
Let's try an example: minimise a function like 'x squared minus four x'. Starting at x equals 3, and taking small steps of 0.25. The gradient points to 2, so our first step moves us to 2.5. The next gradient is 1, moving us to 2.25. Notice we are moving closer to the true minimum, which is at x equals 2.
For your exams, remember the gradient descent update rule: it’s 'minus eta times gradient f'. Always use a table to avoid errors. Don't stop at zero gradient; always classify critical points with the Hessian: positive definite means minimum. Keep these tips in mind, and you'll master finding those lowest points, just like our blindfolded explorer!

The one-minute story

Think of it like this

You are on a hillside in thick fog with a blindfold-level view: you cannot see the valley, but you can feel the slope under your feet. You want to reach the lowest point. What do you do?

You feel which way the ground tilts downhill, take a small step that way, feel again, step again. Eventually the ground feels flat and you stop. That is the whole algorithm. It is called gradient descent.

Two questions decide whether it works: which way is downhill? (the gradient from week 2 tells you) and how big a step? (too small and you crawl for days; too big and you leap clean over the valley and land on the opposite slope, even higher than before).

Almost every machine learning model is trained this way: define a number that says how wrong the model is, then walk it downhill.

By the end of this week you can:

find critical points and classify them with the Hessian;
run gradient descent by hand and explain the role of the learning rate;
tell descent directions from ascent directions;
use second-order information (Newton's idea) and the Taylor expansion to explain why it all works.

Words you need

Objective (or cost, loss) $f(\mathbf x)$ - the number we want to make as small as possible.
Minimum - a point where $f$ is smallest. Local minimum: smallest nearby. Global: smallest anywhere.
Critical (stationary) point - where the gradient is zero.
Hessian $H$ - the matrix of second derivatives, $H_{ij}=\frac{\partial^2f}{\partial x_i\partial x_j}$ . It measures curvature.
Learning rate / step size $\eta$ - how far to move each step.
Descent direction - a direction that makes $f$ go down for a tiny step.
Saddle point - flat spot that is a minimum in one direction and a maximum in another.

Idea 1: Where could the minimum be?

At the lowest point of a smooth valley the ground is flat: $\nabla f(\mathbf x^*)=\mathbf 0$ . Points with zero gradient are critical points. But flat does not mean lowest: the top of a hill and the middle of a horse-saddle are flat too. To tell them apart we look at the curvature, which is the Hessian.

For two variables:

H=\begin{pmatrix}f_{xx}&f_{xy}\\f_{yx}&f_{yy}\end{pmatrix}

(symmetric, because $f_{xy}=f_{yx}$ for nice functions.)

The idea

Second-order test at a critical point $\mathbf x^*$ :

Hessian at $\mathbf x^*$	Meaning	Conclusion
positive definite (all eigenvalues $>0$ )	bowl	local minimum
negative definite (all $<0$ )	dome	local maximum
indefinite (mixed signs)	saddle	saddle point
singular (some eigenvalue $=0$ )	flat in some direction	test is inconclusive

In one variable this is just the sign of $f''$ . For a $2\times2$ Hessian use the shortcut from week 5: PD $\iff f_{xx}>0$ and $\det H>0$ .

Solved example: 1. Classify the critical points

Question. Find and classify the critical points of $f(x,y)=x^3-3x+y^2$ .

Solution.

Gradient: $f_x=3x^2-3$ , $f_y=2y$ . Set both to zero: $x=\pm1$ and $y=0$ . Critical points: $(1,0)$ and $(-1,0)$ .
Hessian: $f_{xx}=6x$ , $f_{xy}=0$ , $f_{yy}=2$ . So $H=\begin{pmatrix}6x&0\\0&2\end{pmatrix}$ .
At $(1,0)$ : $H=\operatorname{diag}(6,2)$ , both positive: local minimum.
At $(-1,0)$ : $H=\operatorname{diag}(-6,2)$ , mixed signs: saddle point.

Whatever you do, do not stop at "gradient is zero". That is only the first half.

Idea 2: Gradient descent

Start at some point $\mathbf x_0$ and repeat

\mathbf x_{t+1}=\mathbf x_t-\eta\,\nabla f(\mathbf x_t)

The minus sign matters: $\nabla f$ points uphill, so we step against it.

Why does a small step always help? By the linear approximation of week 2, for a small step $\mathbf d=-\eta\nabla f$ :

f(\mathbf x+\mathbf d)\approx f(\mathbf x)+\nabla f\cdot\mathbf d=f(\mathbf x)-\eta\|\nabla f\|^2\;<\;f(\mathbf x)

as long as the gradient is not zero. "Small" is the catch: the approximation only holds near $\mathbf x$ .

Solved example: 2. Two iterations by hand

Question. Minimise $f(x)=x^2-4x$ with gradient descent from $x_0=3$ with $\eta=0.25$ . Find $x_1$ and $x_2$ .

Solution. $f'(x)=2x-4$ .

step	$x_t$	$f'(x_t)$	$x_{t+1}=x_t-0.25\,f'(x_t)$
0	3	2	$3-0.5=\mathbf{2.5}$
1	2.5	1	$2.5-0.25=\mathbf{2.25}$

So $x_2=2.25$ . The true minimum is where $2x-4=0$ , i.e. $x=2$ . Each step cuts the remaining distance in half: $1\to0.5\to0.25$ . Always build a small table like this: it is far less error-prone than doing it in your head.

Solved example: 3. Gradient descent in two variables

Question. $f(x,y)=x^2+2y^2$ , start at $(1,1)$ , $\eta=0.1$ . Find the point after two steps.

Solution. $\nabla f=(2x,\,4y)$ .

Step 1: $\nabla f(1,1)=(2,4)$ , so $(1,1)-0.1(2,4)=(0.8,\,0.6)$ .
Step 2: $\nabla f(0.8,0.6)=(1.6,\,2.4)$ , so $(0.8,0.6)-0.1(1.6,2.4)=(\mathbf{0.64},\,\mathbf{0.36})$ .

Notice $y$ shrinks faster than $x$ (factor $0.6$ per step against $0.8$ ) because $f$ is steeper in the $y$ direction.

The learning rate

For the simple bowl $f(x)=\frac{a}{2}x^2$ , the update is $x\leftarrow x-\eta ax=(1-\eta a)x$ . Each step multiplies $x$ by $(1-\eta a)$ .

$0<\eta a<1$ : factor between 0 and 1. Smooth convergence.
$\eta a=1$ : factor 0. Perfect landing in one step.
$1<\eta a<2$ : factor between $-1$ and 0. Bouncing from side to side but still shrinking.
$\eta a=2$ : factor $-1$ . Bounces forever.
$\eta a>2$ : factor beyond $-1$ . Diverges.

So convergence needs $\eta<2/a$ , where $a$ is the curvature (the largest eigenvalue of the Hessian in many variables). When the curvature differs a lot between directions (a long thin valley), the step size must suit the steepest direction, which makes the shallow direction crawl. That is why we scale features before gradient descent (MLP week 3).

Cousins of gradient descent

Batch: use all data to compute the gradient each step. Accurate, slow.
Stochastic (SGD): use one random example per step. Noisy, fast, can escape small dips.
Mini-batch: a handful of examples per step. The usual compromise.
Newton's method: also use curvature: $\mathbf x\leftarrow\mathbf x-H^{-1}\nabla f$ . It lands on the minimum of a quadratic in one step, but needs the Hessian.

Descent directions

A direction $\mathbf d$ is a descent direction at $\mathbf x$ if $\nabla f(\mathbf x)\cdot\mathbf d<0$ : it makes an angle of more than $90^\circ$ with the uphill arrow. If the dot product is $>0$ it goes uphill; if it is $0$ you are moving along a level line.

Solved example: 4. Which directions go downhill?

Question. $f(x,y)=x^2+y^2$ at $(2,-1)$ . Which of $\mathbf d_1=(-1,1)$ , $\mathbf d_2=(1,2)$ , $\mathbf d_3=(2,-1)$ are descent directions?

Solution. $\nabla f(2,-1)=(4,-2)$ .

$\mathbf d_1$ : $4(-1)+(-2)(1)=-6<0$ : descent.
$\mathbf d_2$ : $4(1)+(-2)(2)=0$ : not descent (along the level circle).
$\mathbf d_3$ : $4(2)+(-2)(-1)=10>0$ : ascent.

Least squares is a gradient descent problem too

For $f(\mathbf w)=\|X\mathbf w-\mathbf y\|^2$ the gradient is $2X^T(X\mathbf w-\mathbf y)$ . Setting it to zero gives week 3's normal equations. When $X$ is huge you do not solve them directly: you take gradient steps instead. In MLP you will do exactly that with SGDRegressor.

Your turn

Your turn: 1. A gradient step

$f(x,y)=x^2+3y^2$ . From $(2,1)$ with $\eta=0.1$ , take one step.

Need a hint?

$\nabla f=(2x,\,6y)$ .

Show the full solution

$\nabla f(2,1)=(4,6)$ , so the new point is $(2,1)-0.1(4,6)=(\mathbf{1.6},\,\mathbf{0.4})$ .

Your turn: 2. Find and classify

Find the critical point of $f(x,y)=x^2+y^2-2x-4y$ and say what it is.

Need a hint?

Set $f_x=2x-2$ and $f_y=2y-4$ to zero.

Show the full solution

$x=1$ , $y=2$ . $H=\begin{pmatrix}2&0\\0&2\end{pmatrix}$ , positive definite, so it is a minimum. (And since the function is a bowl, it is the global minimum, value $f(1,2)=1+4-2-8=-5$ .)

Your turn: 3. How big a step is allowed?

$f(x)=3x^2$ . For which $\eta$ does gradient descent converge to $0$ ?

Need a hint?

$f'(x)=6x$ , so the update multiplies $x$ by $(1-6\eta)$ .

Show the full solution

We need $|1-6\eta|<1$ , i.e. $0<\eta<\frac13$ . At $\eta=\frac16$ it lands on 0 in a single step (the factor is 0).

Your turn: 4. Newton's method

Apply one Newton step to $f(x)=x^2-4x$ starting from $x_0=10$ .

Need a hint?

$x_1=x_0-f'(x_0)/f''(x_0)$ .

Show the full solution

$f'(10)=16$ , $f''=2$ , so $x_1=10-8=\mathbf2$ , the exact minimum, in one step. (Gradient descent with $\eta=0.25$ would take many.)

Your turn: 5. Is the minimum global?

$f(x)=x^4-2x^2$ . Find all critical points and classify them.

Need a hint?

$f'(x)=4x^3-4x=4x(x-1)(x+1)$ .

Show the full solution

Critical points $x=0,\pm1$ . $f''(x)=12x^2-4$ : at $0$ , $f''=-4<0$ (local max); at $\pm1$ , $f''=8>0$ (two local minima, both with $f=-1$ ). Here gradient descent would find different minima from different starting points: this function is not convex (next week).

Exam radar

MLF Quiz 2: (of the 30 summarised Quiz 2 papers) gradient descent in 25, gradient and Hessian in 17, update rule in 14, critical points in 18, learning rate in 10, Taylor series in 6. In the End Term: gradient-descent true/false MSQs (about 6), "point after the first iteration" and "value after the second iteration" (about 4), feasible/descent direction questions (about 4), Hessian eigenvalues $2,\,4,\,1\Rightarrow$ local minimum.

Expect one numerical gradient-descent table and one conceptual MSQ ("which statements about gradient descent are true?").

Watch out - real exam trap

Update is $\mathbf x-\eta\nabla f$ (minus). A plus sign climbs the hill.
A zero gradient is not enough: check the Hessian (or sign of $f''$ ).
"Gradient descent always converges to the global minimum" is false in general (true for convex functions with a suitable step size, next week).
A very large $\eta$ can diverge; a very small one converges but slowly. Neither is "wrong code".
Evaluate the gradient at the current point $\mathbf x_t$ , not the starting point.

Quick quiz

The gradient descent update rule is...

x + eta times the gradient
x minus eta times the gradient
x times eta
x minus the Hessian

We step against the gradient, because the gradient points uphill.

At a critical point, the Hessian has eigenvalues 2, 4 and 1. The point is...

a local minimum
a local maximum
a saddle point
not classifiable

All eigenvalues are positive, so the Hessian is positive definite: local minimum.

For f(x) = x squared, which learning rate makes gradient descent diverge?

The factor is 1 - 2*eta. For eta = 1.2 it is -1.4, so |x| grows each step. Convergence needs eta below 1.

Select all TRUE statements. (select all that apply)

A direction d with gradient dot d negative is a descent direction.
At a saddle point the gradient is zero.
A zero gradient always means a minimum.
Gradient descent with any step size always converges.

Saddle points have zero gradient but are not minima, and a big step size can make gradient descent diverge.

Recap

Remember this

Critical point: $\nabla f=0$ . Classify with the Hessian: PD $\to$ min, ND $\to$ max, indefinite $\to$ saddle.
Gradient descent: $\mathbf x_{t+1}=\mathbf x_t-\eta\nabla f(\mathbf x_t)$ . Build a table.
For $f=\frac a2x^2$ : step factor $1-\eta a$ ; converge iff $\eta<2/a$ .
Descent direction: $\nabla f\cdot\mathbf d<0$ . Newton: $\mathbf x-H^{-1}\nabla f$ .
SGD/mini-batch trade accuracy for speed; scale your features.

Formulas to keep

Critical point: $\nabla f(\mathbf x^*)=0$ ; Hessian $H_{ij}=\partial^2f/\partial x_i\partial x_j$
Gradient descent: $\mathbf x_{t+1}=\mathbf x_t-\eta\nabla f(\mathbf x_t)$
Quadratic bowl $\frac a2x^2$ : $x_{t+1}=(1-\eta a)x_t$ ; stable iff $0<\eta<2/a$
Descent direction: $\nabla f\cdot\mathbf d<0$
Newton: $\mathbf x_{t+1}=\mathbf x_t-H^{-1}\nabla f$
Least squares gradient: $\nabla\|X\mathbf w-\mathbf y\|^2=2X^T(X\mathbf w-\mathbf y)$

Connected weeks (learn them together)

MLT week 9 - Perceptron and logistic regression: Training the perceptron and logistic regression is gradient descent.
MLP week 3 - Linear regression and gradient descent in sklearn: Batch and stochastic gradient descent in scikit-learn.
MLT week 12 - Neural networks: Backpropagation is gradient descent plus the chain rule.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 14 real questions on this week All Quiz 2 papers