Gradient descent convergence: step size and curvature: study notes

 

1.32 Gradient descent convergence: step size and curvature: study notes

Learn AI by Story

The idea in one sentence

Gradient descent only works if each step is small enough for the steepest curvature of the loss: for a one-dimensional quadratic with curvature c, any step size eta between 0 and 2/c converges, the best one is 1/c, and anything above 2/c blows up, while a bowl that is much steeper in one direction than another (a high condition number) forces slow progress along the gentle direction.

The story from the video

Meera is walking down a foggy valley. She cannot see the bottom; she can only feel the slope under her feet, and after every step she decides how far to go next. The valley is the simple curve f(x) = x squared and she starts at x = 10. If she takes tiny steps (eta = 0.05) she is still at 3.49 after ten steps. With eta = 0.2 she reaches 0.06. With eta = 0.5 she lands exactly on the bottom in one step. With eta = 0.9 she leaps from wall to wall, shrinking slowly (10, -8, 6.4), and with eta = 1.1 every jump lands higher than the last (10, -12, 14.4) and after ten steps she is at 61.9: divergence. Then the video widens the picture to a canyon with curvature 1 across x and 10 across y, where the steep wall caps the step size and the gentle direction crawls.

(The numbers in this story are illustrative toy examples, chosen so you can check them by hand.)

Key definitions

Term	Precise definition	Plain English
Gradient descent	Iteration x_new = x_old minus eta times the gradient of f at x_old	Step downhill, in proportion to how steep it is
Step size / learning rate (eta)	The positive constant multiplying the gradient in each update	How bold each step is
Curvature	The second derivative f'' in 1-D; the Hessian matrix in many dimensions	How quickly the slope itself changes; how sharply the valley bends
Contraction factor	For f = x squared, the number (1 minus 2 eta) by which x is multiplied each step	The fraction of your distance that survives one step (negative means you overshoot to the other side)
Convergence	The iterates approach a minimizer as the number of steps grows	You eventually arrive
Divergence	The iterates grow without bound	You fly off the map
Lipschitz continuous gradient (L-smooth)	There is a constant L with gradient difference norm at most L times the distance between points; for twice-differentiable f this means curvature never exceeds L	A speed limit on how fast the slope can change; L is the steepest curvature anywhere
Strong convexity (parameter m)	f minus (m/2) times the squared norm is still convex; for twice-differentiable f the curvature is at least m everywhere	The bowl is at least this curved everywhere, so there is no flat floor
Condition number	Ratio of largest to smallest curvature (eigenvalue of the Hessian), L divided by m for a quadratic	How stretched the bowl is; 1 is a perfectly round bowl, big is a long narrow canyon
Linear convergence	The error shrinks by a constant factor less than 1 every step (error at step k is about r to the power k)	Each step removes the same fraction of what is left; a straight line on a log plot
Sublinear convergence	The error shrinks more slowly than any geometric rate, for example proportional to 1/k	Progress that keeps getting slower; typical for convex but not strongly convex problems
Quadratic convergence	The new error is about a constant times the square of the old error	Correct digits double each step (this is Newton's regime, see 1.33)
Line search	A rule that picks eta at every iteration, for example by trying large values and shrinking until the loss drops enough (backtracking)	Let the algorithm test its own stride instead of guessing one
Momentum	An update that adds a fraction of the previous step to the current gradient step	A heavy ball that keeps rolling, damping zigzags across a canyon
Preconditioning	Rescaling the variables or the gradient so the problem looks rounder (condition number closer to 1)	Reshape the canyon into a bowl before walking
Learning-rate schedule	A rule that changes eta during training, for example warm-up then decay	Start gently, go bold, then slow down near the end

Step-by-step explanation

Step 1: the update rule. Gradient descent says: new x = old x minus eta times f'(old x). For f(x) = x squared the derivative is 2x, so new x = x minus 2 eta x = (1 minus 2 eta) x. This is the key simplification. Every step multiplies x by the same number, r = 1 minus 2 eta. After k steps, x_k = r^k times x_0.

Step 2: read the factor. Whether Meera converges depends only on the size of r.

• If abs(r) is below 1, the distance shrinks and she converges.
• If r is between 0 and 1 (eta below 0.5), she approaches from one side without crossing the bottom.
• If r is between -1 and 0 (eta between 0.5 and 1), she jumps across the bottom each step but lands a bit closer: a zigzag.
• If r = 0 (eta = 0.5) she lands exactly on the bottom.
• If abs(r) is above 1 (eta above 1), every jump is longer than the last and she diverges.

Step 3: the safe range. abs(1 minus 2 eta) below 1 means 0 below eta below 1. Written with the curvature c = f'' = 2, this is 0 below eta below 2/c. The best choice makes r = 0, which is eta = 1/c = 0.5.

Step 4: why curvature is the right quantity. Near any minimum a smooth function looks like a parabola with curvature c (the idea of the second-order Taylor approximation, roadmap 1.26). Near the bottom, the gradient descent step is then multiplied by roughly 1 minus eta c. So the rule "eta below 2 over the curvature" is not special to x squared. The textbook treatment (Goodfellow, Bengio and Courville, ch. 4.3) writes the same fact with the Hessian: the optimal step along a gradient g is g-transpose g divided by g-transpose H g, the worst case is 1 over the largest eigenvalue, and "the eigenvalues of the Hessian determine the scale of the learning rate".

Step 5: many directions. With many parameters the loss has a curvature in every direction. Take the canyon f(x, y) = half of (x squared plus 10 y squared). Its curvatures are 1 across x and 10 across y. The update multiplies x by (1 minus eta times 1) and y by (1 minus eta times 10). Safety in the steep y direction requires eta below 2/10 = 0.2. But with eta that small, the x direction (curvature 1) has factor 1 minus eta, close to 1, so it is slow. With eta = 0.1: the y factor is 0, so y is solved in a single step, while the x factor is 0.9. Shrinking x by 1000 times needs 0.9^k below 0.001, which is k = ln 1000 divided by ln(1/0.9) = 65.56, so 66 steps.

Step 6: the condition number. The ratio of the steepest to the gentlest curvature, 10 in this example, is the condition number. It measures how much the steepest direction handicaps the gentlest one: the step size is capped by the largest curvature but the speed along the smallest curvature is proportional to eta times that small curvature. The higher the ratio, the slower the crawl.

Everything the video skipped

The best fixed step for a canyon. For a quadratic with smallest curvature m and largest L, the best single fixed step size is 2/(m+L), which gives a factor of (L minus m)/(L plus m) per step in both directions. For m = 1 and L = 10 that is eta = 2/11 = 0.1818 and factor 9/11 = 0.818. (Standard result, stated as background.) At the edge, eta = 0.2: the y factor is 1 minus 0.2 times 10 = -1, so y flips sign forever without shrinking. That is the boundary between convergence and divergence.

Rates for general functions. The CMU Convex Optimization notes (10-725, Gradient Descent) show that for a convex function whose gradient is L-Lipschitz, a fixed step t at most 1/L gives f(x_k) minus f* at most the squared distance from the start to the optimum divided by (2 t k). That is an O(1/k) rate: sublinear. If the function is also strongly convex with parameter m, the rate becomes linear, and its constant worsens with the condition number L/m. The same notes warn that "the function can diverge if t is too big".

Line search. Instead of picking eta once, we can adapt it at every step. Backtracking line search starts with a large trial step and shrinks it until the loss decreases enough. Dive into Deep Learning (sec. 12.3.3.4, GD with Line Search) discusses this. It costs extra function evaluations per step but removes the need to know L.

Momentum. Adding a fraction of the previous update smooths out the zigzag across the steep wall and accelerates along the gentle direction. For quadratics, well-tuned momentum improves the dependence on the condition number (roughly from the ratio itself to its square root). This is standard background, not shown in the video.

Preconditioning and scaling. If the canyon can be rescaled so both curvatures are equal, the condition number becomes 1 and one well-chosen step suffices. Normalizing input features is the simplest case. Adaptive optimizers such as Adam rescale each parameter's step using running gradient statistics, which acts like a cheap diagonal preconditioner (standard background). D2L sec. 12.3.3.3 discusses preconditioning directly.

Stochastic gradients and noise. In deep learning the gradient is estimated from a mini-batch, so a fixed eta leaves a noise floor around the minimum. That is why schedules decay the rate near the end. The video's quadratic example has no noise.

Non-quadratic and non-convex losses. The 2/c rule is exact for quadratics and a local guide elsewhere. For a neural network the curvature changes from place to place, so a rate that is safe in one region can be unsafe in another. This is one reason training sometimes shows a sudden loss spike.

Limitations. The analysis assumes you know (or can bound) the curvature. In practice we do not, which is why we tune eta by trial, use schedules, or use line search.

Connections on the roadmap.

• 1.25 Jacobian and Hessian: the Hessian is the matrix of second derivatives whose eigenvalues are the curvatures.
• 1.26 Taylor approximation: the quadratic model that explains where 2/c comes from.
• 1.31 Convexity: convex means no curvature is negative, the setting where these rates are guaranteed.
• 1.33 Newton's method: divides by the curvature instead of guessing eta, the direct answer to "what is the best step?".
• Later optimization modules: momentum, Adam, learning-rate schedules and regularization build on this one fact.

Worked example 1: three step sizes on x squared from 10

Update: x becomes (1 minus 2 eta) x.

Step	eta = 0.05 (factor 0.9)	eta = 0.2 (factor 0.6)	eta = 0.5 (factor 0)
0	10	10	10
1	9.0	6.0	0
2	8.1	3.6	0
3	7.29	2.16	0
10	3.4868	0.0605	0

Check eta = 0.05: 10 times 0.9^10 = 10 times 0.34868 = 3.4868. Check eta = 0.2: 10 times 0.6^10 = 10 times 0.006047 = 0.0605. With eta = 0.5 the factor is exactly 0, so one step lands on the minimum. Each of the first two columns is linear convergence: a constant factor per step.

Worked example 2: oscillation and divergence

Step	eta = 0.9 (factor -0.8)	eta = 1.1 (factor -1.2)
0	10	10
1	-8	-12
2	6.4	14.4
3	-5.12	-17.28
10	abs value 1.0737	61.917

Check: 10 times 0.8^10 = 1.0737 (the sign after an even number of steps is positive); 10 times 1.2^10 = 61.917. Both zigzag across the bottom; the first shrinks, the second grows. The boundary is abs(factor) = 1, that is eta = 1 = 2/c.

Worked example 3: the canyon with curvatures 1 and 10

f = half of (x squared plus 10 y squared). Update: x times (1 minus eta), y times (1 minus 10 eta). Condition number 10, safe only if eta below 0.2.

eta	x factor	y factor	Behaviour
0.1	0.9	0	y solved in one step, x needs 66 steps to shrink 1000 times
2/11 = 0.1818	0.8182	-0.8182	best fixed step; about 35 steps to shrink 1000 times in both directions
0.2	0.8	-1	y flips sign forever, never settles
0.25	0.75	-1.5	y diverges

The 35-step figure: ln 1000 divided by ln(11/9) = 34.4, rounded up to 35. Even the best fixed step needs about half the steps of eta = 0.1, but both are far from the one-step ideal of the round bowl. A round bowl (both curvatures 1) with eta = 1 would finish in one step.

Comparison tables

Regime	Condition on eta (1-D, curvature c)	Factor per step	What it looks like
Too small	0 below eta below 1/c	between 0 and 1	slow, one-sided creep
Perfect	eta = 1/c	0	one step to the bottom
Overshoot but converging	1/c below eta below 2/c	between -1 and 0	zigzag, shrinking
Edge	eta = 2/c	-1	endless bouncing
Divergent	eta above 2/c	below -1	growing zigzag

Convergence type	Error behaviour	Example
Sublinear	about 1/k	convex, merely L-smooth, fixed step at most 1/L
Linear	multiplied by a constant r below 1	strongly convex quadratic with fixed good step
Quadratic	error squared each step	Newton near the optimum (1.33)

Fix for a bad condition number	How it helps	Cost
Feature scaling	rounds the bowl in input space	cheap
Momentum	damps zigzag, speeds the gentle direction	one extra vector
Adaptive optimizers	per-parameter step sizes	extra memory
Line search	picks a safe step each time	extra loss evaluations
Second-order methods	cancel the curvature (1.33)	very expensive in high dimension

Common mistakes and myths

• "Smaller learning rate is always safer, so always use it." Safe from divergence, yes, but slow. In the canyon, tiny steps just stretch the 66 steps into hundreds.
• "Divergence means a bug." Often it just means eta exceeded 2 over the steepest curvature.
• "Zigzag means it is not working." A zigzag with factor between -1 and 0 is still converging.
• "The best step is the biggest stable one." Not so: the best step is 1/c in 1-D; just under 2/c is stable but slow and oscillating.
• "One learning rate suits every direction." A high condition number means different directions want different steps.
• "The condition number is about the number of parameters." No. It is a ratio of curvatures, regardless of dimension.
• "Linear convergence is slow because of the word linear." Linear means geometric: the error falls by a constant factor, a straight line on a log plot. Sublinear is the slower one.
• Forgetting that the rule 2/c uses the steepest curvature, not the average.

Real-life uses

• Training neural networks: loss explosions are usually a step size above the stability limit; warm-up then decay schedules are a standard remedy.
• Linear and logistic regression: normalizing features lowers the condition number and speeds up gradient descent.
• Recommendation and ranking models: adaptive optimizers handle features with very different scales.
• Signal and image reconstruction: iterative solvers choose step sizes from an estimate of the largest curvature.
• Scientific computing: stiff problems are the same story, the step is capped by the steepest direction.

Self-check questions

1. For f = x squared, what is the update rule? Answer: x becomes (1 minus 2 eta) x.
2. With eta = 0.05 from x = 10, what is x after ten steps? Answer: 3.4868.
3. What eta lands on the minimum in one step, and why? Answer: 0.5, because 1 minus 2 times 0.5 = 0 (that is 1/c with c = 2).
4. What happens at eta = 1.1, and what is the factor? Answer: the factor is -1.2, so it diverges; x is about 61.9 after ten steps.
5. State the safe range of eta for curvature c. Answer: 0 below eta below 2/c.
6. In the canyon with curvatures 1 and 10, what caps eta? Answer: the steeper curvature, 10, so eta below 0.2.
7. With eta = 0.1, why does y finish at once? Answer: its factor is 1 minus 0.1 times 10 = 0.
8. How many steps shrink x by 1000 times with eta = 0.1? Answer: 66, since ln 1000 / ln(1/0.9) = 65.56.
9. What is the condition number here and what does it mean? Answer: 10; the ratio of largest to smallest curvature, how stretched the bowl is.
10. Difference between linear and sublinear convergence? Answer: linear shrinks the error by a constant factor each step; sublinear (for example 1/k) slows down as it goes.

Key takeaways

• Each gradient step on a quadratic multiplies the error by 1 minus eta times curvature.
• Safe means eta below 2/curvature; best means eta = 1/curvature.
• The steepest direction sets the speed limit; the gentlest sets the speed.
• Condition number = steepest curvature divided by gentlest curvature; high means slow.
• Scaling, momentum, schedules, adaptive methods and line search all attack this same problem.

Go deeper: read the "Convergence Analysis" and "Preconditioning" parts of D2L 12.3, and try the canyon in a few lines of code with different eta.

Next roadmap ID: 1.33 Newton's method and second-order optimization.

Sources and further reading

1. Zhang, Lipton, Li, Smola, Dive into Deep Learning, sec. 12.3 "Gradient Descent" (One-Dimensional GD, Multivariate GD, Adaptive Methods: Newton's Method, Convergence Analysis, Preconditioning, GD with Line Search). https://d2l.ai/chapter_optimization/gd.html
2. Goodfellow, Bengio, Courville, Deep Learning, ch. 4 "Numerical Computation", 4.2 Poor Conditioning and 4.3 Gradient-Based Optimization. https://www.deeplearningbook.org/contents/numerical.html
3. CMU 10-725 Convex Optimization (Fall 2016, Ryan Tibshirani), "Gradient Descent" scribe notes. https://www.stat.cmu.edu/~ryantibs/convexopt-F16/scribes/grad-descent-scribed.pdf
4. Goodfellow, Bengio, Courville, Deep Learning, ch. 8 "Optimization for Training Deep Models" (background on training difficulties). https://www.deeplearningbook.org/contents/optimization.html

Accuracy note: all numbers come from exact arithmetic on the toy examples (verified in Python); the 2/(m+L) rate is a standard result stated as background, and momentum, Adam and schedules are standard background without citations to figures.