Gradient Descent and Optimization, machine learning lesson

Suppose a model has a single weight $w$ and training means making the objective $L(w) = (w - 3)^2$ small. The current weight $w = 0$ gives $L(0) = 9$ . Should the weight go up or down, and by how much? The derivative answers the first question near the current point and a step size answers the second, yet a step in the right direction can still make the objective worse when it is too long. This lesson builds gradient descent from these two pieces, shows how the step size decides whether it converges, and uses convexity and the Hessian to tell what kind of point the iterations can stop at.

Key terms

Objective function

Definition An objective function is a real-valued function $J$ on a set $\Theta \subseteq \mathbb{R}^d$ of allowed parameter vectors, chosen so that smaller values are preferred. Optimization looks for a parameter vector $\boldsymbol{\theta}$ in $\Theta$ with the smallest value of $J(\boldsymbol{\theta})$ , and maximizing a quantity is the same as minimizing its negative. In the examples on this page $\Theta = \mathbb{R}^d$ , so the parameters are unconstrained. For training data $(x_1, y_1), \dots, (x_n, y_n)$ with one feature, the linear predictor $\hat{y} = wx + b$ and the squared error give the objective

\begin{aligned} J(w, b) &= \frac{1}{2n} \sum_{i=1}^{n} r_i^2 , \\[0.4em] r_i &= wx_i + b - y_i , \end{aligned}

where the error $r_i$ is the prediction minus the target for example $i$ . This is the average of the loss $\tfrac12 (\hat{y} - y)^2$ over the training examples, an empirical risk. The factor $\tfrac12$ only simplifies the derivatives and does not change which parameters minimize $J$ .

In plain words The objective turns “fit the training data well” into one number for each choice of parameters, and optimization can only improve what that number measures. A small or steadily falling value says that the model fits the training examples better in the chosen sense. Even a global minimum of the objective does not show that the model will predict new data well, because the expected loss on new data, the population risk, is a different quantity, estimated with data that played no part in training. The lesson on loss functions and empirical risk treats this distinction in full.

Example The objective $L(w) = (w - 3)^2$ of the opening has one parameter and its smallest value $0$ at $w = 3$ . For a regression example, two constructed training examples have inputs $x_1 = 1$ and $x_2 = 2$ with targets $y_1 = 3$ and $y_2 = 5$ . With $n = 2$ the objective is

\begin{aligned} &J(w, b) = \tfrac14 (w + b - 3)^2 \\[0.4em] &\quad + \tfrac14 (2w + b - 5)^2 . \end{aligned}

At $(w, b) = (0, 0)$ both predictions are $0$ , the errors are $-3$ and $-5$ , and $J(0, 0) = (9 + 25)/4 = 8.5$ . At $(w, b) = (2, 1)$ both predictions are exact, so $J(2, 1) = 0$ , and since $J$ is never negative this is the smallest possible value. A line can always pass through two points with different inputs, so this zero says nothing about how well the line predicts at new inputs.

Gradient descent

Definition Let $J: \mathbb{R}^d \to \mathbb{R}$ be differentiable. Gradient descent with learning rate $\alpha > 0$ starts from a chosen point $\boldsymbol{\theta}_0$ and repeats

\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \alpha \nabla J(\boldsymbol{\theta}_t)

for $t = 0, 1, 2, \dots$ until a set number of steps is done or the gradient norm falls below a chosen tolerance. Every coordinate is updated at once from the gradient at the old point $\boldsymbol{\theta}_t$ . The negative gradient is a descent direction. If $\mathbf{g} = \nabla J(\boldsymbol{\theta}) \ne \mathbf{0}$ , the function $\varphi(s) = J(\boldsymbol{\theta} - s\mathbf{g})$ has derivative $\varphi'(0) = -\lVert \mathbf{g} \rVert_2^2 < 0$ , so $J(\boldsymbol{\theta} - s\mathbf{g}) < J(\boldsymbol{\theta})$ for every sufficiently small $s > 0$ . Among unit vectors $\mathbf{u}$ , the directional derivative $\nabla J(\boldsymbol{\theta})^{\top}\mathbf{u}$ is then smallest for $\mathbf{u} = -\mathbf{g} / \lVert \mathbf{g} \rVert_2$ , so the negative gradient is the direction of steepest descent. At a stationary point, where the gradient is $\mathbf{0}$ , the update leaves the parameters unchanged.

In plain words At the current parameters, find the direction in which the objective rises fastest, take a step the opposite way, and repeat from the new point. The gradient is recomputed after every step because the slope changes as the parameters move. The guarantee is local. A short enough step goes downhill, but the direction alone does not say how long a step is safe.

Example For $L(w) = (w - 3)^2$ the derivative is $L'(w) = 2(w - 3)$ , so $L'(0) = -6$ . With $\alpha = 0.1$ the first update is

w_1 = 0 - 0.1 \cdot (-6) = 0.6 ,

and the objective falls from $9$ to $5.76$ . The derivative at $0.6$ is $-4.8$ , so $w_2 = 0.6 + 0.48 = 1.08$ and the objective is $3.6864$ . The second step is shorter because the slope has shrunk. For the regression objective $J(w, b)$ of the previous card, the chain rule gives

\begin{aligned} \frac{\partial J}{\partial w} &= \frac{1}{n} \sum_{i=1}^{n} r_i x_i , \\[0.4em] \frac{\partial J}{\partial b} &= \frac{1}{n} \sum_{i=1}^{n} r_i , \end{aligned}

with the $2$ from the square canceling the $\tfrac12$ . At $(0, 0)$ the errors $-3$ and $-5$ give $\partial J / \partial w = (-3 - 10)/2 = -6.5$ and $\partial J / \partial b = (-3 - 5)/2 = -4$ . One step with $\alpha = 0.1$ uses both of these old partial derivatives and gives $(w, b) = (0.65, 0.4)$ . The new predictions $1.05$ and $1.7$ have errors $-1.95$ and $-3.3$ , so the objective drops from $8.5$ to $(3.8025 + 10.89)/4 = 3.673125$ . More steps are needed to approach the exact fit at $(2, 1)$ .

Learning rate

Definition The learning rate, or step size, is the number $\alpha > 0$ in the gradient descent update. The step has length $\alpha \lVert \nabla J(\boldsymbol{\theta}_t) \rVert_2$ , and whether the iterates settle depends on $\alpha$ together with how fast the gradient can change. Suppose $J: \mathbb{R}^d \to \mathbb{R}$ is differentiable and $\beta$ -smooth for some $\beta > 0$ , meaning that for all $\mathbf{a}$ and $\mathbf{b}$

\begin{aligned} &\lVert \nabla J(\mathbf{a}) - \nabla J(\mathbf{b}) \rVert_2 \\[0.4em] &\quad \le \beta \lVert \mathbf{a} - \mathbf{b} \rVert_2 . \end{aligned}

Then for every $\boldsymbol{\theta}$ , with $\mathbf{g} = \nabla J(\boldsymbol{\theta})$ ,

\begin{aligned} &J(\boldsymbol{\theta} - \alpha\mathbf{g}) \le J(\boldsymbol{\theta}) \\[0.4em] &\quad - \alpha\bigl(1 - \tfrac{\alpha\beta}{2}\bigr) \lVert \mathbf{g} \rVert_2^2 , \end{aligned}

so every learning rate in $(0, 2/\beta)$ lowers $J$ at each step where $\mathbf{g} \ne \mathbf{0}$ . If $J$ is also convex, in the sense of the card below, and has a global minimum $\boldsymbol{\theta}^*$ , then gradient descent with $0 < \alpha \le 1/\beta$ satisfies

\begin{aligned} &J(\boldsymbol{\theta}_t) - J(\boldsymbol{\theta}^*) \\[0.4em] &\quad \le \frac{\lVert \boldsymbol{\theta}_0 - \boldsymbol{\theta}^* \rVert_2^2}{2\alpha t} \end{aligned}

for every $t \ge 1$ , so the objective values converge to the minimum value. These conditions are sufficient, not necessary, and the bound concerns objective values. It does not say which minimum the iterates approach when there are several.

In plain words The gradient says which way is downhill right here, and the learning rate says how far to trust that local information. A rate that is too small makes progress slow. A rate that is too large can carry a step so far past the minimum that the objective rises, and for a bowl such as $(w - 3)^2$ the iterates then move farther away with every step. Where the gradient changes quickly, the safe steps are short.

Example For $L(w) = (w - c)^2$ with any constant $c$ , write $e_t = w_t - c$ for the error after $t$ steps. Subtracting $c$ from both sides of the update $w_{t+1} = w_t - 2\alpha(w_t - c)$ gives

e_{t+1} = (1 - 2\alpha)\, e_t .

Each step multiplies the error by the same factor, so from any start other than $c$ the iterates converge exactly when $\lvert 1 - 2\alpha \rvert < 1$ , that is, for $0 < \alpha < 1$ . For $\alpha < \tfrac12$ they approach $c$ from one side, at $\alpha = \tfrac12$ they reach it in one step, and for $\tfrac12 < \alpha < 1$ they jump across it every time while the error still shrinks. With $c = 3$ and $w_0 = 0$ , the rate $\alpha = 1$ sends the iterates to $6$ , back to $0$ and so on, with the objective stuck at $9$ . The rate $\alpha = 1.1$ gives $6.6$ and then $-1.32$ , and the objective climbs from $9$ to $12.96$ and then to $18.6624$ , although each step pointed downhill at its starting point. Here $L'$ changes by exactly $2$ per unit of $w$ , so $L$ is $2$ -smooth. The general results then promise a decrease for $\alpha < 1$ and the convergence bound for $\alpha \le \tfrac12$ , and the convergence for $\tfrac12 < \alpha < 1$ shows that the condition $\alpha \le 1/\beta$ is not necessary.

Local and global minima

Definition Let $J$ be a real-valued function on a set $\Theta \subseteq \mathbb{R}^d$ . A point $\boldsymbol{\theta}^*$ in $\Theta$ is a global minimum of $J$ if $J(\boldsymbol{\theta}^*) \le J(\boldsymbol{\theta})$ for every $\boldsymbol{\theta}$ in $\Theta$ . It is a local minimum if there is a radius $r > 0$ such that $J(\boldsymbol{\theta}^*) \le J(\boldsymbol{\theta})$ for every $\boldsymbol{\theta}$ in $\Theta$ with $\lVert \boldsymbol{\theta} - \boldsymbol{\theta}^* \rVert_2 < r$ . Some books call such a point a minimizer and keep the word minimum for the value $J(\boldsymbol{\theta}^*)$ . Every global minimum is a local minimum. A stationary point is a point where $J$ is differentiable and its gradient is $\mathbf{0}$ . If a local minimum lies in the interior of $\Theta$ and $J$ is differentiable there, it is a stationary point. The converse fails, because a stationary point can also be a local maximum or a saddle point, a stationary point that is neither. A function may have several global minima or none at all.

In plain words A local minimum is the lowest point of some neighborhood around it, and a global minimum is the lowest point of everything allowed. A zero gradient only says that the graph is flat at that spot. The spot may be a valley floor, a hilltop or a pass between two hills. If an iterate of gradient descent lands exactly on a stationary point, every later iterate stays there, so the fact that the iterates have stopped moving does not say which kind of point they found.

Example For $L(w) = (w - 3)^2$ the only stationary point is $w = 3$ , and it is the global minimum because a square is never negative and equals $0$ there. The function $-w^2$ has derivative $0$ at $w = 0$ , which is its global maximum. The function $w^3$ also has derivative $0$ at $w = 0$ , but it is negative to the left of $0$ and positive to the right, so $0$ is neither a minimum nor a maximum. The function $f(w) = w^3 - 3w$ has the stationary points $-1$ and $1$ . Since

\begin{aligned} &f(w) - f(1) \\[0.4em] &\quad = (w - 1)^2 (w + 2) \end{aligned}

is nonnegative for $w \ge -2$ , the point $w = 1$ is a local minimum with $f(1) = -2$ . It is not global, because $f(-3) = -18$ , and $f$ has no global minimum at all, since $f(w) \to -\infty$ as $w \to -\infty$ .

Convex function

Definition A set $C \subseteq \mathbb{R}^d$ is convex if it contains the whole line segment between any two of its points. A function $J: C \to \mathbb{R}$ on a convex set $C$ is convex if

\begin{aligned} &J\bigl(\lambda\mathbf{a} + (1 - \lambda)\mathbf{b}\bigr) \\[0.4em] &\quad \le \lambda J(\mathbf{a}) + (1 - \lambda) J(\mathbf{b}) \end{aligned}

for all $\mathbf{a}$ and $\mathbf{b}$ in $C$ and every $\lambda$ in $[0, 1]$ . For a convex function every local minimum is a global minimum. If $J$ is convex and differentiable on all of $\mathbb{R}^d$ , a point is a global minimum exactly when the gradient there is $\mathbf{0}$ . If $J$ is twice continuously differentiable on an open convex set, it is convex exactly when its Hessian is positive semidefinite at every point of that set. Convexity alone does not promise that a minimum exists, that it is unique, or that gradient descent with a particular fixed learning rate converges.

In plain words Every chord between two points of the graph lies on or above the graph, so the graph has no false bottoms. If some point $\mathbf{a}$ had a lower value than a local minimum $\boldsymbol{\theta}^*$ , the inequality would put lower values on the segment toward $\mathbf{a}$ arbitrarily close to $\boldsymbol{\theta}^*$ , which a local minimum rules out. For a convex objective a stationary point settles the optimization question. It settles nothing about prediction, since a global minimum of the training objective can still describe new data poorly. The squared-error objective of a linear model is convex in its weights and intercept, while the training objectives of neural networks with hidden layers are in general not convex.

Example For $L(w) = (w - 3)^2$ and any $a$ , $b$ and $\lambda$ in $[0, 1]$ , a short computation gives

\begin{aligned} &\lambda L(a) + (1 - \lambda) L(b) \\[0.4em] &\quad - L\bigl(\lambda a + (1 - \lambda) b\bigr) \\[0.4em] &= \lambda (1 - \lambda)(a - b)^2 , \end{aligned}

which is never negative, so the bowl is convex. The function $f(w) = w^3 - 3w$ of the previous card is not convex. At the midpoint of $-2$ and $0$ its value $f(-1) = 2$ lies above the chord value $\tfrac12 \bigl(f(-2) + f(0)\bigr) = -1$ . Only a function that is not convex can have a local minimum that is not global, as this one does. The function $J(w_1, w_2) = (w_1 + w_2 - 2)^2$ is convex, and every point on the line $w_1 + w_2 = 2$ is a global minimum. Flat valleys like this one appear when a model contains the same feature twice, because then only the sum of the two weights affects the predictions. The function $e^w$ is convex and has no minimum at all.

Hessian matrix

Definition Let $J: \mathbb{R}^d \to \mathbb{R}$ have second partial derivatives at $\boldsymbol{\theta}$ . The Hessian matrix $H(\boldsymbol{\theta})$ is the $d \times d$ matrix with entries

H_{ij}(\boldsymbol{\theta}) = \frac{\partial^2 J}{\partial \theta_i \, \partial \theta_j}(\boldsymbol{\theta}) .

If the second partial derivatives are continuous near $\boldsymbol{\theta}$ , the matrix is symmetric. In one dimension it is the second derivative $J''$ . For a twice continuously differentiable $J$ ,

\begin{aligned} J(\boldsymbol{\theta} + \mathbf{v}) &\approx J(\boldsymbol{\theta}) \\[0.4em] &\quad + \nabla J(\boldsymbol{\theta})^{\top} \mathbf{v} \\[0.4em] &\quad + \tfrac12 \mathbf{v}^{\top} H(\boldsymbol{\theta}) \mathbf{v} \end{aligned}

with an error that is small compared with $\lVert \mathbf{v} \rVert_2^2$ as $\mathbf{v} \to \mathbf{0}$ . A symmetric matrix $H$ is positive definite if $\mathbf{v}^{\top} H \mathbf{v} > 0$ for every $\mathbf{v} \ne \mathbf{0}$ , and positive semidefinite if $\mathbf{v}^{\top} H \mathbf{v} \ge 0$ for every $\mathbf{v}$ . At a stationary point $\boldsymbol{\theta}^*$ of a twice continuously differentiable $J$ , a positive definite Hessian makes $\boldsymbol{\theta}^*$ a strict local minimum, a negative definite one makes it a strict local maximum, and a Hessian with both a positive and a negative eigenvalue makes it a saddle point. If the Hessian at $\boldsymbol{\theta}^*$ is semidefinite but singular, this test decides nothing.

In plain words The gradient gives the slope, and the Hessian gives how the slope changes, the curvature, in every direction. A positive value of $\mathbf{v}^{\top} H \mathbf{v}$ means that the graph bends upward along $\mathbf{v}$ . At a flat spot, upward bending in every direction makes the bottom of a bowl, and bending up in some directions and down in others makes a pass. Where the curvature is large the slope changes quickly, and that is where long steps overshoot.

Example For the regression objective $J(w, b)$ , differentiating the partial derivatives once more gives the constant Hessian

H = \frac{1}{n} \sum_{i=1}^{n} \begin{bmatrix} x_i^2 & x_i \\ x_i & 1 \end{bmatrix} ,

and for the inputs $1$ and $2$ it is

H = \begin{bmatrix} 2.5 & 1.5 \\ 1.5 & 1 \end{bmatrix} .

For any direction $\mathbf{v} = (v_w, v_b)$ ,

\begin{aligned} \mathbf{v}^{\top} H \mathbf{v} &= \frac{1}{n} \sum_{i=1}^{n} (x_i v_w + v_b)^2 \\[0.4em] &\ge 0 , \end{aligned}

so this squared-error objective is convex. For a linear model with several features the same computation gives the average squared change in the predictions per unit step along $\mathbf{v}$ , so its squared-error objective is convex too. With the inputs $1$ and $2$ the sum is $0$ only when $v_w + v_b = 0$ and $2v_w + v_b = 0$ , which forces $\mathbf{v} = \mathbf{0}$ . The Hessian is positive definite, and $(2, 1)$ is the unique global minimum. If all inputs were equal, the sum would vanish for some nonzero $\mathbf{v}$ and a flat valley would appear. Since the gradient changes by $H(\mathbf{a} - \mathbf{b})$ between two points, $J$ is $\beta$ -smooth with $\beta$ equal to the largest eigenvalue of $H$ . The eigenvalues $(7 \pm 3\sqrt{5})/4$ are about $3.43$ and $0.073$ , so the rate $\alpha = 0.1$ is below $1/\beta \approx 0.29$ . On this quadratic, fixed steps converge from every start when $0 < \alpha < 2/\beta \approx 0.58$ and diverge from almost every start for larger rates. For a saddle, take $f(u, v) = u^2 - v^2$ . Its gradient is $\mathbf{0}$ at the origin and its Hessian there has diagonal entries $2$ and $-2$ , so the origin is a saddle point. The functions $w^4$ and $-w^4$ both have second derivative $0$ at $0$ , yet $0$ is a minimum of the first and a maximum of the second.

Check yourself

Gradient descent minimizes $L(w) = (w - 4)^2$ from $w_0 = 1$ with learning rate $\alpha = 0.2$ . Compute the derivative at the start, the next iterate, and the objective before and after the step.

Show the answer

The derivative is $L'(w) = 2(w - 4)$ , so $L'(1) = 2 \cdot (-3) = -6$ . The update gives

w_1 = 1 - 0.2 \cdot (-6) = 2.2 .

The objective falls from $(1 - 4)^2 = 9$ to $(2.2 - 4)^2 = 3.24$ . The step moved toward the minimum at $4$ , and the remaining error $-1.8$ is $0.6$ times the starting error $-3$ .

Repeat the first step with $\alpha = 1.2$ . A classmate argues that the step must lower the objective because it follows the negative gradient. Find the new iterate and the objective, explain what went wrong, and give the learning rates for which gradient descent on this function converges from $w_0 = 1$ .

Show the answer

The derivative at the start is still $-6$ , so the new iterate is $w_1 = 1 - 1.2 \cdot (-6) = 8.2$ . The objective becomes $(8.2 - 4)^2 = 17.64$ , larger than $9$ . The negative gradient only promises a decrease for steps that are short enough. This step crosses the minimum and lands $4.2$ away from it, farther than the starting distance $3$ .

Write $e_t = w_t - 4$ for the error. Subtracting $4$ from both sides of the update gives

e_{t+1} = (1 - 2\alpha)\, e_t .

At $\alpha = 1.2$ the factor is $-1.4$ , so the error goes from $-3$ to $4.2$ to $-5.88$ , alternating in sign and growing, and the objective climbs from $9$ to $17.64$ to $34.5744$ . The starting error is not zero, so the iterates converge exactly when $\lvert 1 - 2\alpha \rvert < 1$ , that is, for $0 < \alpha < 1$ . The rate $0.2$ of the first question gives the factor $0.6$ and converges.

Find the stationary point and the Hessian of $J(u, v) = u^2 + 4uv + v^2$ . Both diagonal entries of the Hessian are positive. Is the stationary point a minimum, and is $J$ convex?

Show the answer

The gradient is $(2u + 4v, \, 4u + 2v)$ . The first entry is zero when $u = -2v$ , and then the second is $-8v + 2v = -6v$ , which is zero only for $v = 0$ . So the only stationary point is the origin. The Hessian is the same at every point,

H = \begin{bmatrix} 2 & 4 \\ 4 & 2 \end{bmatrix} ,

with eigenvalue $6$ for the direction $(1, 1)$ and eigenvalue $-2$ for the direction $(1, -1)$ . Positive diagonal entries are not enough, because the Hessian has a negative eigenvalue. Along $(1, -1)$ the function is $J(t, -t) = t^2 - 4t^2 + t^2 = -2t^2$ , which is negative for every $t \ne 0$ , while along $(1, 1)$ it is $J(t, t) = 6t^2$ . So the origin is a saddle point, not a minimum.

The function is not convex, since its Hessian is not positive semidefinite, and it has no global minimum, since $-2t^2$ decreases without bound. Gradient descent started exactly at the origin never moves. Started slightly off it along $(1, -1)$ , each step multiplies the distance from the origin by $1 + 2\alpha$ , so the iterates move away.

Gradient Descent and Optimization

Key terms

Objective function

Gradient descent

Learning rate

Local and global minima

Convex function

Hessian matrix

Check yourself

How this lesson connects

Builds on

Used later in