OptimizationGradient Descent#001

Gradient Descent

경사하강법

Gradient descent lowers a loss by stepping against the gradient by the learning rate; it is how neural networks learn. After 20 steps a learning rate of 0.18 reaches loss 0.005, while 0.205 diverges to 79. See in figures and code how the most curved direction sets the limit 0.2.

Key symbol
η
Reading time
14 min
Prerequisites
Gradient

Translated by an agent and not reviewed yet. Original: 한국어

Intuition — walking down a foggy mountain

Intuition

Imagine standing halfway up a mountain in thick fog. You can't see far, but you can feel the slope under your feet. Take one step the steepest way down, feel the slope again, and take another.

As long as your stride is not too large, repeating this eventually brings you to a valley.11 There is no guarantee it is the lowest valley (the global minimum). The example on this page is a bowl-shaped (convex) function with a single valley, and with a learning rate between 0 and 0.2 every path gathers at that one point (Eq. (4)). The height of the mountain is the loss function, your position is the parameter, the slope under your feet is the gradient, and the factor that multiplies that slope to set your stride is the learning rate.22 So with the same learning rate you step farther where the ground is steeper. The length of one step is learning rate × slope. When a neural network (deep learning) learns, it is repeating this step over and over to lower the loss.

This page follows, with numbers on a single bowl, how large that factor can get. The answer is 0.2, and that value is set by the most curved direction.

Gradient descent is an iterative rule that moves against the gradient

Gradient descent (GD) is a method that finds where a loss is smallest by repeatedly moving a little in the direction opposite to the one in which the loss grows fastest.

At the parameter θ\theta, the gradient ∇L\nabla L points in the direction where the loss LL grows fastest. So we move the other way, by η ∇L\eta\,\nabla L, the gradient multiplied by η\eta.33 Why the minus sign? The gradient points uphill, so going down means going the other way. In words: new position = current position − learning rate × gradient.

θt+1=θt−η ∇θL(θt)(1)\theta_{t+1} = \theta_t - \eta \, \nabla_\theta L(\theta_t) \tag{1}
Definition
SymbolNameMeaning
θt\theta_tparameterYour position at step tt. For a neural network, every weight laid out in one vector
η\etalearning rateThe factor (a number greater than 0) that multiplies the gradient to set the length of one step. The protagonist of this page. Also called the step size; depending on the text it is written α\alpha (Kingma and Ba), ε\varepsilon (Goodfellow et al.), or γ\gamma (MML, PyTorch docs)
∇L\nabla LgradientThe vector of partial derivatives with respect to each parameter (a partial derivative differentiates in one parameter while holding the others fixed). It points uphill. The partial derivative along one direction is the slope in that direction, and the whole vector is often loosely called the slope too. ∇θL\nabla_\theta L marks that we differentiate with respect to θ\theta
LLloss functionA value that measures how bad the parameters are. Smaller is better
ttiterationThe number of steps taken so far. L20L_{20} is the loss after 20 steps
x,yx, ycoordinatesThe two components of θ=(x,y)\theta = (x, y) in the 2-D example
kkcurvatureThe second derivative along one direction, that is, how fast the slope grows along that direction. In Eq. (2) it is 1 in the xx direction and 10 in the yy direction

Our example is a bowl that is 10 times more curved in yy than in xx.44 Curvature is how fast the steepness grows. It means that at the same distance from the bottom the slope is 10 times larger: in Eq. (2) the slope at x=1x = 1 is 1, and the slope at y=1y = 1 is 10.

L(x,y)=12(x2+10y2),∇L=(x, 10y)(2)L(x, y) = \tfrac{1}{2}\left(x^2 + 10y^2\right), \qquad \nabla L = (x,\ 10y) \tag{2}

Differentiating in xx with yy held fixed gives 12×2x=x\tfrac{1}{2} \times 2x = x, and differentiating in yy with xx held fixed gives 12×20y=10y\tfrac{1}{2} \times 20y = 10y.

Figure 1 shows the paths that three learning rates take over the contours of this bowl.

Contours of L with paths from the same start (-4.4, 1.5) at different learning rates (14 steps; 6 for the diverging 0.205). η = 0.05 is slow, 0.18 converges in a zigzag, and 0.205 diverges.
Figure 1 Contours of LL with paths from the same start (−4.4, 1.5)(-4.4,\ 1.5) at different learning rates (14 steps; 6 for the diverging 0.2050.205). η=0.05\eta = 0.05 is slow, 0.180.18 converges in a zigzag, and 0.2050.205 diverges. figures/contour_paths.py

What is the learning rate?

The learning rate is a number greater than 0 that multiplies the gradient to set the length of one step. It is the η\eta of Eq. (1), and the length of one step is learning rate × size of the gradient. It is not a value the model learns but one a person sets in advance. On this bowl 0.05 is slow, 0.18 is fast, and 0.205 diverges (Figure 1).

Why does gradient descent get stuck in a local minimum?

Because at a point where the gradient is 0, the step η ∇L\eta\,\nabla L of gradient descent is 0 too, so it moves no further. A local minimum, which is only lower than its surroundings, and a saddle point are such points, and near them the steps become very small. This bowl has only one such point, the bottom (0, 0)(0,\ 0); functions with several valleys are covered in the page 'Convexity and Local Minima' (planned).

Why a learning rate above 0.2 diverges

In this example bowl, once the learning rate exceeds 0.2, a single step in the yy direction overshoots the bottom of the valley and lands higher up on the opposite side. So ∣y∣|y| grows with every step, and with η=0.205\eta = 0.205 the loss after 20 steps passes its starting value of 20.93 and reaches 79 (Figure 2).

Put the gradient from Eq. (2) into Eq. (1), and each coordinate, on its own, is multiplied by the same number at every step.

xt+1=(1−η) xt,yt+1=(1−10η) yt(3)x_{t+1} = (1 - \eta)\, x_t, \qquad y_{t+1} = (1 - 10\eta)\, y_t \tag{3}

This is Eq. (1) written coordinate by coordinate, xt+1=xt−η xtx_{t+1} = x_t - \eta\,x_t and yt+1=yt−η×10yty_{t+1} = y_t - \eta \times 10y_t, with the terms collected.

Let's follow the first step with η=0.18\eta = 0.18. x1=0.82×(−4.4)=−3.608x_1 = 0.82 \times (-4.4) = -3.608 and y1=(1−1.8)×1.5=−1.2y_1 = (1 - 1.8) \times 1.5 = -1.2. The length of the yy step, η×10∣y∣\eta \times 10|y|, is 10η=1.810\eta = 1.8 times the distance ∣y∣|y| to the bottom, so yy has crossed past the bottom to the other side.

yy only shrinks to 0 if the multiplying factor (1−10η)(1 - 10\eta) of the yy direction has absolute value below 1. When the factor turns negative (η>0.1\eta > 0.1, that is, when one step is longer than the distance to the bottom), the sign flips every step and the path zigzags; when its absolute value exceeds 1, it diverges.

∣1−10η∣<1  ⟺  0<η<0.2(4)|1 - 10\eta| < 1 \iff 0 < \eta < 0.2 \tag{4}

That is why η=0.205\eta = 0.205 diverges even though it is only 0.005 past the limit of 0.2.55 Looking at xx alone, ∣1−η∣<1|1-\eta| < 1 allows anything up to η<2\eta < 2. What sets the upper limit is the more curved yy direction.

In Eq. (3), xx and yy are each multiplied by the same number again and again, so each is a geometric sequence (common ratios 1−η1 - \eta and 1−10η1 - 10\eta). So repeating it tt times lets you jump straight from the start to step tt.

xt=(1−η)t x0,yt=(1−10η)t y0(5)x_t = (1 - \eta)^t\, x_0, \qquad y_t = (1 - 10\eta)^t\, y_0 \tag{5}

With η=0.205\eta = 0.205 the yy factor is −1.05-1.05, so ∣y∣|y| grows 1.05 times at every step while its sign flips. After 20 steps, ∣y20∣=1.0520×1.5≈3.98|y_{20}| = 1.05^{20} \times 1.5 \approx 3.98, about 2.65 times its starting value. The loss starts at L0=12(4.42+10×1.52)=20.93L_0 = \tfrac{1}{2}(4.4^2 + 10 \times 1.5^2) = 20.93 and falls to 17.52 over the first three steps. That is because the xx share shrinks quickly and hides the growth of the yy share.

From the seventh step on, however, the loss is above the starting 20.93, and after 20 steps L20=12(x202+10 y202)≈79L_{20} = \tfrac{1}{2}(x_{20}^2 + 10\,y_{20}^2) \approx 79. In Figure 2 this is the 0.2050.205 curve dipping briefly and then escaping upward.

Loss L against the number of steps t. After 20 steps, η = 0.18 reaches 0.005, 0.05 reaches 1.24, and 0.205 grows to 79. The arrow marks where the 0.205 curve leaves the top of the plot.
Figure 2 Loss LL against the number of steps tt. After 20 steps, η=0.18\eta = 0.18 reaches 0.005, 0.050.05 reaches 1.24, and 0.2050.205 grows to 79. The arrow marks where the 0.2050.205 curve leaves the top of the plot. figures/loss_curves.py

Why does a large learning rate cause divergence?

Because when the learning rate is too large, a step along the most curved direction overshoots the bottom of the valley and lands higher on the opposite wall, and this repeats at every step. On this page's bowl 12(x2+10y2)\tfrac{1}{2}(x^2 + 10y^2), 'too large' means above 0.2. With η=0.25\eta = 0.25 the yy factor in Eq. (3) is −1.5-1.5, so ∣y∣|y| grows 1.5 times at every step while its sign flips. Why it is exactly 0.2 is shown in the section 'The learning-rate limit 0.2 is set by the most curved direction'.

The learning-rate limit 0.2 is set by the most curved direction

0.2 is the learning rate at which one yy step is exactly twice the distance to the bottom. A step of twice the distance passes the bottom and lands at the same height on the other side; a longer one lands higher.

The yy step was 10η10\eta times the distance to the bottom. When this ratio is 1 (η=0.1\eta = 0.1) one step reaches the bottom, and when it is 2 (η=0.2\eta = 0.2) yy goes from 1.5 to −1.5-1.5, exactly on the other side. The 10 is the curvature of the yy direction: how fast the slope 10y10y grows along yy.

In a direction with curvature kk, the same calculation puts the limit at 2/k2/k.

∣1−kη∣<1  ⟺  0<η<2k(6)|1 - k\eta| < 1 \iff 0 < \eta < \frac{2}{k} \tag{6}

The xx direction has curvature 1, so its limit is 2; the yy direction has 10, so its limit is 0.2. Both directions have to shrink, so the smaller limit, the one of the more curved direction, becomes the upper limit. Eq. (6) is a condition for a fixed learning rate on a quadratic function whose curvature is constant along each direction (k>0k > 0).66 If the quadratic is not aligned with the axes, you first have to find the direction of largest curvature. In linear algebra that direction is an eigenvector of the Hessian matrix (the matrix of second partial derivatives), and the curvature along it is the largest eigenvalue. The limit is 2 divided by that value.

The left panel of Figure 3 plots the two factors against η\eta. ∣1−10η∣|1 - 10\eta| drops to 0 at 0.1 and rises above 1 past 0.2, while ∣1−η∣|1 - \eta| stays below 1 over the plotted η>0\eta > 0. On the right, L20L_{20} is smallest near 0.18 and shoots up past 0.2.

Multiplying factors (left) and the loss after 20 steps L_20 (right, log scale) against the learning rate η. The y factor |1 - 10η| is below 1 for 0 < η < 0.2 and above 1 past 0.2. The x factor |1 - η| is below 1 over the whole plotted η > 0. The horizontal dashed line on the right is the starting loss L_0 = 20.93.
Figure 3 Multiplying factors (left) and the loss after 20 steps L20L_{20} (right, log scale) against the learning rate η\eta. The yy factor ∣1−10η∣|1 - 10\eta| is below 1 for 0<η<0.20 < \eta < 0.2 and above 1 past 0.20.2. The xx factor ∣1−η∣|1 - \eta| is below 1 over the whole plotted η>0\eta > 0. The horizontal dashed line on the right is the starting loss L0=20.93L_0 = 20.93. figures/eta_boundary.py

Why is a learning rate of 0.2 the limit for divergence?

For a fixed learning rate the divergence limit is 2 ÷ (largest curvature), and on the bowl 12(x2+10y2)\tfrac{1}{2}(x^2 + 10y^2) the most curved direction yy has curvature 10, so it is 2 ÷ 10 = 0.2 (Eq. (6)). At this learning rate yy bounces between 1.5 and −1.5-1.5, so the yy share of the loss, 12×10×1.52=11.25\tfrac{1}{2} \times 10 \times 1.5^2 = 11.25, stays the same at every step. As Eq. (4) says, for 0<η<0.20 < \eta < 0.2 this share shrinks at every step (convergence), and above 0.2 it grows (divergence).

The best learning rate is near 0.182, not just below the limit

With enough steps (asymptotically), the fastest, that is, optimal, fixed learning rate is where the two factors have equal absolute value: 1−η=10η−11 - \eta = 10\eta - 1, so η=2/11≈0.182\eta = 2/11 \approx 0.182. There both factors are 9/11≈0.8189/11 \approx 0.818 in absolute value, so the slower factor is as small as it can be.77 Looking at only 20 steps, L20L_{20} is smallest near 0.177. LeCun et al. (Section 5.1) give the fastest learning rate as 1 ÷ (largest curvature), here 0.1. That value looks only at the most curved direction; looking at both directions together gives 2 ÷ (sum of the two curvatures) = 2/11 (Try it yourself 1).

Just below the limit is actually slow. With η=0.199\eta = 0.199 the yy factor is −0.99-0.99, so ∣y∣|y| shrinks by only 1% per step, and L20L_{20} is 7.53, more than a thousand times the 0.005 of 0.18.

With the limit pinned at 0.2, the factor of the less curved xx direction is 1−η>1−2/10=0.81 - \eta > 1 - 2/10 = 0.8. xx shrinks by less than 20% per step. The ratio of the two curvatures, 10 ÷ 1 = 10, is called the condition number. The larger it is, the closer the lower bound of the xx factor, 1 − 2 ÷ condition number, gets to 1, and the slower the less curved direction becomes.

Key idea

The upper limit on the learning rate is set by the most curved direction. The more the curvature differs between directions (the larger the condition number), the slower gradient descent gets.

The first sentence is exact for a quadratic with a fixed learning rate. The second means that even with the optimal learning rate, the slower factor (condition number − 1) ÷ (condition number + 1) grows with the condition number (here 9/11). For a general loss, this holds when the region near the minimum is approximated by a quadratic.88 If the component along the most curved direction is 0 from the start (y0=0y_0 = 0 in this example), that direction never moves and the limit never applies. 'Slower' assumes that component is there.

Common misconceptions about gradient descent

  • Keeping the learning rate small costs you nothing — η=0.05\eta = 0.05 does not diverge, but xx shrinks by only 5% per step (0.95 times), so after 20 steps the loss is 1.24, more than 200 times the 0.005 of 0.18 (Figure 2).
  • A path that zigzags is diverging — For 0.1<η<0.20.1 < \eta < 0.2 the yy factor in Eq. (3) is negative, so the sign flips, but its absolute value is below 1. So η=0.18\eta = 0.18 zigzags (Figure 1) yet its loss falls at every step, to 0.005 after 20 steps (Figure 2).
  • Going slightly past the limit only makes things slightly worse — Even η=0.205\eta = 0.205, just 0.005 past 0.2, multiplies ∣y∣|y| by 1.05 at every step, and after 20 steps its loss is 79, larger than the starting 20.93.

Where gradient descent shows up in AI

When you train a neural network with SGD (stochastic gradient descent) without momentum, every step is one application of Eq. (1). The difference is that ∇L\nabla L is estimated from a part of the data (a mini-batch), not from all of it. Momentum and Adam are variants that change a term of Eq. (1) by mixing in gradients from earlier steps. Momentum and Adam continue on the same bowl in their own pages, Momentum and Adam; Mini-batch SGD continues with the effect of selecting samples.

How do the types of gradient descent (batch, stochastic SGD, mini-batch) differ?

Batch, stochastic (SGD), and mini-batch gradient descent use the same update rule and differ only in how much data goes into computing the gradient (the ∇L\nabla L of Eq. (1)). Using all the data is batch gradient descent (this page), a single sample is stochastic gradient descent (SGD), and a subset is mini-batch gradient descent. Mini-batch SGD has an example where using only two of four samples (samples 1 and 2) turns the gradient (−4.4, 15)(-4.4,\ 15) into (−2.4, 15)(-2.4,\ 15).

One step clears the previous gradients (optimizer.zero_grad()), computes the loss (forward), gets the gradient by backpropagation (loss.backward()), and updates the weights with Eq. (1) (optimizer.step()). backward() adds its values into .grad, so the clearing step comes first. Backpropagation gets the partial derivatives of all the weights in one pass, using the rule for differentiating composite functions (the chain rule). Here θ\theta is all the weights of the model, and the learning rate η\eta is a value a person chooses.

This pagePyTorch
θ\thetamodel.parameters() — the weight tensors passed to the optimizer
η\etalr in torch.optim.SGD(params, lr=0.18) (default 1e-3; the docs' pseudocode writes it as γ)
∇L\nabla LThe value loss.backward() adds into each parameter's .grad
Eq. (1)optimizer.step() — when momentum, dampening, and weight_decay are 0 and nesterov and maximize are False (all defaults)
ttThe number of times optimizer.step() has been called

Is PyTorch's lr the learning rate η?

Yes. The lr of torch.optim.SGD is the η\eta of Eq. (1), and its default is 1e-3 (0.001). But this page's limit of 0.2 comes from a bowl whose curvature is fixed at 10. In a neural network the curvature differs from place to place, so you usually try a few values of lr and pick one by checking whether the learning curve (loss against steps) goes down.

This page keeps the learning rate fixed. There are also ways to change it during training (learning-rate schedules), which torch.optim.lr_scheduler handles in PyTorch.

Check it in code

Click a symbol to highlight it in both the formula and the code. Move the learning rate η\eta to recreate the three paths from Figure 1.

Math
θt+1=θt−η ∇L(θt)(1)\sym{theta}{\theta}_{t+1} = \sym{theta}{\theta}_t - \sym{eta}{\eta} \, \sym{grad}{\nabla L}(\theta_t) \tag{1}∇L=(x, 10y)(2)\sym{grad}{\nabla L} = (x,\ 10y) \tag{2}xt+1=(1−η) xt,yt+1=(1−10 η) yt(3)x_{t+1} = (1 - \sym{eta}{\eta})\, x_t, \qquad y_{t+1} = (1 - 10\,\sym{eta}{\eta})\, y_t \tag{3}
Code figures/gradient_descent.py
import numpy as np

def L(p):
    x, y = p
    return 0.5 * (x**2 + 10 * y**2)

def grad(p):
    x, y = p
    return np.array([x, 10 * y])    # ∇L — 식 (2)

theta = np.array([-4.4, 1.5])   # θ₀
eta   = 0.18                     # η
for t in range(21):
    if t % 5 == 0: print(f"t={t:2d}  L={L(theta):.3f}")
    theta = theta - eta * grad(theta)  # 식 (1) — 좌표마다 풀면 식 (3)
$ python gradient_descent.py
t= 0  L=20.930
t= 5  L=2.538
t=10  L=0.313
t=15  L=0.039
t=20  L=0.005

Try it yourself

  1. On the same bowl with η=0.1\eta = 0.1, what is the yy factor? After 20 steps, what fraction of its starting value does xx keep, and how does the loss compare with the 0.005 of η=0.18\eta = 0.18?
  2. For the bowl L=12(x2+100y2)L = \tfrac{1}{2}(x^2 + 100y^2), whose yy coefficient is 100 instead of 10, what is the learning-rate limit? Below that limit, what percentage does the per-step shrink of xx stay under?
Answers
  1. 1−10×0.1=01 - 10 \times 0.1 = 0, so yy reaches the bottom (0) in the first step. By Eq. (5), xx keeps 0.920≈0.120.9^{20} \approx 0.12 of its start, so L20≈0.14L_{20} \approx 0.14, more than twenty times the 0.005 of 0.18. The best learning rate for yy is not the best learning rate overall.
  2. From Eq. (6) with k=100k = 100, 0<η<2/100=0.020 < \eta < 2/100 = 0.02. In this range the xx factor 1−η1 - \eta is above 0.98, so xx shrinks by less than 2% per step. As the condition number went from 10 to 100, the cap on how much xx shrinks in one step fell from 20% to 2%. Both are values at the limit, so they are never actually reached.

Further reading

  • Deep Learning, Chapter 4 Numerical Computation — Goodfellow, Bengio, Courville, 2016. Eq. (4.5) in Section 4.3 is Eq. (1) on this page (it writes the learning rate as ε). Section 4.3.1 and Figure 4.6 explain that with poor conditioning the step size must be small enough not to overshoot the minimum and go uphill along the most curved direction, so progress along less curved directions is usually slow. The section 'The learning-rate limit 0.2 is set by the most curved direction' relies on it.
  • Deep Learning, Chapter 8 Optimization for Training Deep Models — Goodfellow, Bengio, Courville, 2016. Section 8.3.1 warns that if the learning rate is too large the learning curve oscillates violently and the cost increases, and that if it is too small learning is slow. It notes that the learning rate is usually best chosen by watching the learning curve. The section 'Common misconceptions about gradient descent' and the question 'Is PyTorch's lr the learning rate η?' rely on it.
  • Mathematics for Machine Learning, Chapter 7 Continuous Optimization — Deisenroth, Faisal, Ong, 2020. Section 7.1 covers gradient descent and the zigzag on poorly conditioned problems, and Section 7.1.1 covers how a step-size that is too large overshoots or diverges, along with the condition number. The book's PDF is available at this address. The sections 'Why a learning rate above 0.2 diverges' and 'Common misconceptions about gradient descent' rely on it.
  • Efficient BackProp — LeCun, Bottou, Orr, Müller, 1998. In Neural Networks: Tricks of the Trade (Springer), DOI 10.1007/3-540-49430-8_2. Section 5.1 shows the learning rate that reaches the minimum in one step, that up to twice that the iterates oscillate but converge and beyond it they diverge, and that with several directions the limit is 2 ÷ (largest curvature). Where it gives the fastest learning rate as 1 ÷ (largest curvature), it differs from this page's 2/11 (see the note in 'The best learning rate is near 0.182, not just below the limit'). The bottom and opposite-side explanation in 'The learning-rate limit 0.2 is set by the most curved direction' and the section 'Common misconceptions about gradient descent' rely on it.
  • torch.optim.SGD — PyTorch official documentation, checked against version 2.15. Argument defaults (lr=1e-3, momentum=0 …) and the update pseudocode. The mapping table in 'Where gradient descent shows up in AI' relies on it.
  • torch.optim — How to adjust learning rate — PyTorch official documentation, checked against version 2.15. It says torch.optim.lr_scheduler provides several methods to adjust the learning rate based on the number of epochs. The sentence on learning-rate schedules in 'Where gradient descent shows up in AI' relies on it.

Video notes

Video notes
  • 00:00 Opening question — “How do you get down a mountain in fog?”
  • 01:10 Write Eq. (1) on the board one symbol at a time — θ\theta, η\eta, ∇L\nabla L
  • 03:40 Figure 1 — the three learning rates, one step at a time
  • 06:20 Derive Eq. (4) — why 0.2 is the limit
  • 07:30 Figure 3 — η=0.1\eta = 0.1 lands on the bottom, 0.20.2 at the same height on the other side
  • 08:30 Code lab screen · wrap-up

This is the filming plan. After upload, the timestamps will be replaced with the real ones and moved into YouTube chapters.

Where this sits on the map

DerivativesCalculusVectors and Dot ProductLinear AlgebraGradientCalculusGradient DescentYou are hereBackpropagationAICondition NumberPlannedConvexity and Local MinimaPlannedLearning Rate ScheduleOptimizationLinear RegressionPlannedMini-batch SGDOptimizationMomentumMethod · OptimizationRMSPropMethod · Planned
Prerequisites
This page
Next
DonePlannedMethodThe path to this pageSee the full map →