Gradient descent and learning rate behavior

By Better Wise

Stepping downhill with a curvature budget

In the previous lesson you found the minimizer of a function under a constraint by solving a Lagrange system: stationarity plus the constraint, solved as a system of equations. Real problems rarely have closed-form solutions, so we need an iterative method. Gradient descent is that method, and the Hessian from Module 2 is what tells you whether your step size will work.

Recall the two facts we build on: the gradient $\nabla f(\theta)$ points in the direction of steepest ascent, so $-\nabla f(\theta)$ points downhill; and the eigenvalues of the Hessian bound how fast the function curves in each direction.

By the end of this lesson you should be able to:

• Write the gradient descent update and run it on a hand-derived gradient.
• Predict the stable step-size range from the largest Hessian eigenvalue.
• Diagnose divergence, oscillation and crawling convergence from a loss trace.
• Size a learning rate against curvature instead of guessing.

The update rule and a gradient you derive by hand

Gradient descent repeats one line:

$$ \theta_{t+1} = \theta_t - \alpha \nabla f(\theta_t) $$

Here _____ is the learning rate: a scalar that converts a direction into a distance.

Take $f(x,y) = x^2 + 3y^2$. Differentiating by hand gives $\nabla f = (2x,, 6y)$ and

$$ H = \begin{pmatrix} 2 & 0 \ 0 & 6 \end{pmatrix} $$

Before running anything, verify the gradient numerically. Central differences cost two function evaluations per coordinate and catch almost every sign and factor error:

import numpy as np

def f(theta):
    x, y = theta
    return x**2 + 3*y**2

def grad(theta):                 # hand-derived
    x, y = theta
    return np.array([2*x, 6*y])

def num_grad(theta, h=1e-6):
    e = np.eye(2)
    return np.array([(f(theta + h*e[i]) - f(theta - h*e[i])) / (2*h) for i in range(2)])

theta = np.array([1.0, 1.0])
print(grad(theta), num_grad(theta))   # [2. 6.] [2. 6.]

Why curvature sets the step size

This lesson is premium content. Sign in and purchase the course to view the full content. Sign in