Gradient Descent

Topic — The previous page argued that a loss is a choice and that most choices have no closed form. This page is the method you use when there isn't one. It is four lines of arithmetic, and almost every confusion about it comes from three places: two completely different plots share the name "the gradient descent curve", the halting behaviour near the minimum looks like something someone programmed, and the bowl everyone draws is round only because the drawing is a special case.

---

In plain words

You are somewhere on a hillside in fog. You cannot see the valley floor, but you can feel which way the ground slopes. So you take a step downhill, feel again, step again. Keep going and you end up at the bottom. That is gradient descent, complete — there is nothing else to it.

Every symbol on this page is one of those four things:

In the fog	In the algorithm
Where you are standing	The current parameter values θ — the model's slope and intercept
How high up you are	The cost J(θ) — how badly the model currently fits
The slope under your boots	The gradient ∇J(θ) — which way the cost increases, and how fast
How big a step you take	The learning rate α

And the four things this page settles, each of which trips people up:

1. Downhill needs a minus sign. The gradient points uphill by definition. Flip that one sign and you climb instead of descend — the run destroys the model rather than fitting it.
2. "The gradient descent curve" is two different pictures. One shows the cost dropping over time (is it working?). The other shows the fitted line swinging into place (what has it learned?). People routinely show one while answering a question about the other.
3. It slows down near the bottom for free. Nobody programs a brake. Near the valley floor the ground is nearly level, so the slope you feel is tiny, so your step is tiny. The step size is always the learning rate times the steepness — the steepness does the shrinking.
4. The valley usually isn't a round bowl. Every textbook draws a neat circular bowl. Real ones are long narrow ravines, and in a ravine the downhill direction points mostly at the side wall rather than along the floor, so you zigzag and progress collapses. This is the single biggest reason a gradient-descent run is slow, and the fix is not the learning rate — it is scaling your features.

The rest of the page measures all four, and then names the mathematical objects behind point 4, because those names (Hessian, eigenvalue, condition number) are how everyone else talks about it.

Words used on this page

Term	What it means here
Gradient ∇J	One derivative per parameter, packed into a vector. Its length says how steep
Convex	Wherever you start, walking downhill reaches the bottom. No separate dips to get trapped in
Hessian H	Second derivatives — how fast the slope itself changes. For squared error it is a fixed matrix, (2/n)XᵀX, the same everywhere
Eigenvalue λ	The bowl has a steepest direction and a shallowest one. λ_max and λ_min are how sharply it curves along each
Condition number κ	λ_max / λ_min. κ = 1 is a perfect circular bowl; κ = 900000 is a canyon
Contraction	0.8 means each step removes 20% of what remained. Small is fast
OLS	The closed-form least-squares solution, used here as the known target to check against

tip

If you only take one thing from this page

κ, the condition number, is the number that decides whether gradient descent takes 40 steps or never finishes. It is set by your data, not by your optimiser — and standardising your features is what brings it down. When a run is mysteriously slow, check κ before you touch the learning rate.

---

The whole algorithm

Pick a starting point, measure the slope, step against it, repeat.

θ ← θ − α·∇J(θ)

Symbol	Name	What it is
θ	parameters	Everything being fitted — here (b, w)
J(θ)	cost	The loss summed over the data
∇J(θ)	gradient	The vector of partial derivatives, one per parameter
α	learning rate	How far to move per step

For squared error on a linear model, both pieces are one line each:

J(θ)  = (1/n) · Σ(Xθ − y)²
∇J(θ) = (2/n) · Xᵀ(Xθ − y)

That 2 is not decoration — it comes from differentiating the square. And it is the source of the single most common cross-referencing error in the whole subject.

The 1/2 convention, and why α is not portable

Many sources define the cost with a 1/2 in front, J = (1/2n)·Σ(Xθ − y)², precisely so that the 2 cancels and the gradient is the tidier (1/n)·Xᵀ(Xθ − y). That is a legitimate choice and it changes nothing about where the minimum is. What it does change is every gradient's magnitude — they are all exactly half.

Why you should care: your step size is the learning rate times the gradient. Halve every gradient and every step halves too, which is indistinguishable from having halved the learning rate. So the same α = 0.1 means two different step sizes in two textbooks, and one of them will be twice the size you expected.

Three runs on the same data from the same start make the consequence concrete:

Output

2. THE 1/2 CONVENTION   (same problem, three runs)
    iter   J=(1/n) a=0.1   J=(1/2n) a=0.1   J=(1/2n) a=0.2  col1/col3
       0     29.46681475      14.73340738      14.73340738 2.00000000
       1     18.92536852      11.95163684       9.46268426 2.00000000
       2     12.17884294       9.69840271       6.08942147 2.00000000
       3      7.86106656       7.87328306       3.93053328 2.00000000
       4      5.09768968       6.39493615       2.54884484 2.00000000

The last column is 2.00000000 on every row. The 1/2n cost at α = 0.2 is tracing the same parameter path as the 1/n cost at α = 0.1, and its cost is exactly half only because the cost function itself is halved. Meanwhile the middle column — the 1/2n cost at the same α = 0.1 — is a genuinely different, slower run: by iteration 3 it is at 7.87 where the others have effectively reached 7.86 and 3.93.

danger

α = 0.1 in one source is not α = 0.1 in another

Halving the cost is arithmetically identical to halving the learning rate. So a learning rate copied from a source that uses the 1/2 convention into code that doesn't will be twice as large as intended — which, as the next page shows, is exactly the size of mistake that turns a working setting into a diverging one.

Before reusing anyone's α, check whether their cost has the 1/2. These notes use J = (1/n)Σ(·)² throughout, matching the MSE definition used for the error measures.

---

The Gradient Descent Workbench

"The gradient descent curve" refers to two completely different plots. Drag the slider below to step through a gradient descent run and watch both curves update synchronously:

• Left (Cost Descent): Shows the cost $J(\theta)$ dropping as iterations tick past (is it working?).
• Right (Fitted Line): Shows the regression line $ŷ = b_0 + b_1 x$ pivoting and rising into place on the scatter plot (what has it learned?).

Double-View Gradient Descent Workbench

Slide to step through 50 iterations. Watch the cost descent curve on the left and the fitted line pivot on the right.

Gradient Descent Iteration: 0 (b = 0.000, w = 0.000)

Cost Curve J(θ)

Current Cost: 29.4668 (‖∇J‖ = 10.8225)

Fitted Line ŷ = b + w·x

Equation: ŷ = 0.00 + 0.00x

The cost column falls 29.46681 → 0.18502 and then stops moving. The ŷ columns do something different: they travel, each to its own destination — ŷ(–2) climbs from 0 to 0.91362, ŷ(+2) from 0 to 9.10416. Both destinations are the OLS row, printed last: identical to five decimal places. Gradient descent found the exact answer the normal equation gives in one algebraic step.

tip

Which plot you want depends on the question

Debugging the optimiser — diverging, crawling, oscillating — is a cost curve question, and the next page is entirely about reading them. Explaining the model to somebody is a fitted-line question. Presenting one and answering the other is the commonest way these discussions go wrong.

The ‖∇J‖ column is worth a glance now because it does the work of two later sections: it collapses from 10.82253 to 0.00000, and it is the only quantity in the loop that changes the step size.

---

Why the surface is a bowl

Everyone draws gradient descent as a ball rolling into a bowl. The picture is doing real work — it is why the algorithm cannot get stuck part-way — so it deserves a check rather than an assertion.

The reason it matters: if the landscape really is a single bowl, then "keep walking downhill" is guaranteed to reach the one true bottom, wherever you started. If instead it has side pockets, walking downhill can drop you into a dip that is lower than its surroundings but not the lowest place around — and you will never know, because from inside the dip every direction is uphill. Bowl-shaped landscapes are called convex, and the guarantee is exactly what makes linear regression by gradient descent trustworthy.

Here is how to check it without any calculus. Pick two spots on the surface and stretch a straight string between them. If the surface always sags below the string, it is a bowl. If any part of the surface pokes above the string, there is a bump, and bumps mean pockets. Testing the midpoint of the string is enough to catch this most of the time, so: sample two random parameter vectors, evaluate the cost at each and at their midpoint, and see whether

J(midpoint)  ≤  ( J(a) + J(b) ) / 2

Two thousand random pairs, and the same test on a deliberately non-convex loss for contrast:

Output

3. CONVEXITY   (midpoint chord test, 2000 random parameter pairs)
   MSE                     0 violations of  J(mid) <= mean(J(a), J(b))
   MSE of sigmoid(Xθ)    957 violations of  J(mid) <= mean(J(a), J(b))
   Hessian (2/n)XᵀX eigenvalues = [2. 2.]   both > 0 -> a bowl

Zero violations out of 2000 for squared error on a linear model. 957 out of 2000 — 48% — once the same squared error is applied to sigmoid(Xθ) instead. Convexity is a property of the loss-and-model pair, not of optimisation in general, and the contrast is what makes that concrete.

One parameter, two parameters, and the algebraic reason

With one parameter the cost is a parabola in that parameter — J(w) = (1/n)Σ(w·xᵢ − yᵢ)² expands to Aw² + Bw + C with A = (1/n)Σxᵢ² > 0. A parabola opening upward. With two parameters it is a paraboloid: a bowl in three dimensions, with contours that are ellipses.

The general statement uses the Hessian. If the gradient tells you the slope, the Hessian tells you the curvature — how fast that slope is changing. For squared error it is one fixed matrix, identical at every point on the surface, which is exactly why the surface is a plain bowl and not something lumpier:

H = (2/n) · Xᵀ X

Two facts do all the work, and neither needs the derivation.

A bowl curves upward in every direction. The Hessian's eigenvalues are the curvature measured along each of the surface's own natural directions. All positive means it curves upward everywhere, so it is a bowl. One of them zero means there is a direction that is perfectly level — a trough with a flat floor, so infinitely many equally good answers, which is the same defect that makes the normal equation fail on a constant column. A negative one would mean a saddle, and squared error never produces one.

XᵀX can never have a negative eigenvalue. Whatever X is — any data at all, clean or filthy — this particular product is guaranteed to curve upward or be flat, never downward. (The formal name is positive semi-definite.) That one guarantee is what makes squared error on a linear model convex for every dataset, with no assumptions to check.

Here the eigenvalues are [2, 2]: equal curvature in both directions, so the bowl is perfectly round and its contours are circles rather than stretched ellipses.

warning

A round bowl is a special case, not the general picture

κ = 1.00 here is not a fact about gradient descent — it is what standardising the single feature did. With mean 0 and standard deviation 1, (1/n)XᵀX is exactly the identity, so H = 2·I.

Textbook illustrations use this case because it draws nicely. Real cost surfaces are elongated, and the last section of this page measures how much that costs.

note

The chord test is evidence, not proof

2000 samples finding no violation does not prove convexity — it fails to disprove it. The proof is the positive semi-definite Hessian. The test earns its place by being the thing that catches non-convexity: 957 violations is not a subtle signal, and running it on a loss you are unsure about is a cheap sanity check.

---

The minus sign is the whole algorithm

∇J points in the direction of steepest increase. So −∇J points downhill, and the minus sign in the update is not notation to be skimmed — it is the entire difference between fitting a model and destroying one. Same data, same start, same α, one sign flipped:

Output

4. THE MINUS SIGN   (identical init, identical alpha, opposite direction)
    iter     descent  −α∇J      ascent  +α∇J
       0       29.46681475      2.946681e+01
       5        3.32912848      1.814902e+02
      10        0.52261578      1.122779e+03
      20        0.18891189      4.303773e+04
      40        0.18502019      6.325537e+07

Descent lands on 0.18502019. Ascent reaches 6.33e+07 at iteration 40 and is still accelerating — a factor of over 340 million between two runs whose code differs by one character.

The asymmetry is worth naming. Descent has a floor: the cost cannot go below the minimum, so the run converges. Ascent has no ceiling — the paraboloid opens upward forever — so it accelerates without limit. This is the same runaway the next page produces from an α that is merely too large, and it is why an exploding cost is the easiest of all optimiser failures to spot.

---

The braking is free

The most-asked question about gradient descent: with α fixed, what stops the algorithm shooting past the minimum and bouncing around forever? People expect the answer to be a schedule that shrinks α. It isn't. Nothing in the loop shrinks anything.

Output

5. THE BRAKING IS FREE   (nothing in the loop shrinks the step)
    iter        ‖Δθ‖        ‖∇J‖   ‖Δθ‖/‖∇J‖   shrink
       1    1.082253   10.822531       0.100        —
       2    0.865802    8.658025       0.100   0.8000
       3    0.692642    6.926420       0.100   0.8000
       4    0.554114    5.541136       0.100   0.8000
       5    0.443291    4.432909       0.100   0.8000
       6    0.354633    3.546327       0.100   0.8000
       7    0.283706    2.837062       0.100   0.8000
       8    0.226965    2.269649       0.100   0.8000
       9    0.181572    1.815719       0.100   0.8000
      10    0.145258    1.452576       0.100   0.8000
   predicted contraction  max|1 − α·λ| = 0.8000
   distance travelled: first 5 iters 3.638102, last 5 of 100 2.262e-09, ratio 1.609e+09

Read the third column first. ‖Δθ‖ / ‖∇J‖ is 0.100 on every row, exactly α, because that is what the update rule says: Δθ = −α∇J. The step length is α times the gradient length, always, with no exceptions and no bookkeeping.

So the step shrinks for one reason: the gradient shrinks. Approaching the minimum, the surface flattens, ‖∇J‖ falls, and the step falls in exact proportion. The algorithm brakes because the road levels out, not because it is watching a speedometer.

The braking rate is predictable in advance

The shrink column is 0.8000 every single iteration — the same fraction removed every time. That number is not an accident, and you can work it out before running anything.

The plain version. Call the distance still left to travel your remaining error. Each step removes a fixed percentage of it — not a fixed amount. Here it removes 20%, leaving 0.8 of what was there before, every single step. That is why the run gets close quickly and then crawls: 20% of a large gap is a big move, 20% of a tiny gap is a tiny move.

Where does the 0.8 come from? A step multiplies your remaining error by (1 − α·λ): the learning rate times the curvature, subtracted from one. With α = 0.1 and curvature λ = 2, that is 1 − 0.1 × 2 = 0.8. Larger α or steeper curvature means more of the error removed per step — up to a point, which is the whole subject of the next page.

In symbols, writing θ* for the optimum so θₜ − θ* is the remaining error:

θₜ₊₁ − θ*  =  (I − αH)(θₜ − θ*)

Each of the bowl's natural directions has its own curvature λᵢ, so each shrinks by its own factor (1 − α·λᵢ). The overall rate is set by whichever direction shrinks least — the slowest one is what you end up waiting for:

contraction  =  max_i |1 − α·λᵢ|

Here both eigenvalues are 2, so both directions shrink at 0.8 and there is no slow one. Predicted 0.8000, measured 0.8000 — identical to four decimals, which is as many as were printed.

The cumulative effect is stark: the first five iterations cover a parameter-space distance of 3.638102, the last five of a hundred cover 2.262e-09. A ratio of 1.609e+09 with α held constant the entire time.

tip

Convergence is geometric, so cost per extra digit is constant

A contraction of 0.8 per step means roughly log(10)/log(1/0.8) ≈ 10 iterations per decimal digit of accuracy, forever. This is why gradient descent gets close fast and exact slowly, and why a sensible stopping rule watches ‖∇J‖ or the change in J rather than counting iterations.

---

The bowl is usually a ravine

Everything above ran on a round bowl, and round bowls are produced by standardised features rather than by nature.

Picture the difference. In a round bowl, downhill from anywhere points straight at the bottom, so you walk more or less directly there. Now squash that bowl sideways into a long narrow ravine. Standing on one wall, the steepest direction is straight across at the opposite wall — barely at all along the valley floor towards the exit. So you cross, overshoot, cross back, and inch forward a little each time. The distance to the exit hasn't changed; the number of steps has exploded.

The measurement below squashes the bowl deliberately: take two standardised features, multiply one of them by a growing factor, give each version the largest α it can tolerate, and count iterations to the same tolerance.

Output

6. THE BOWL IS USUALLY A RAVINE   (feature 2 rescaled, own largest stable alpha)
     scale        kappa   2/lambda_max    iters   status
   x     1          1.6   8.199661e-01       40   converged
   x    10         92.9   1.265469e-02      413   converged
   x   100       9294.4   1.265541e-04    41674   converged
   x  1000     929437.6   1.265541e-06   200000   cap reached

The kappa column is the condition number λ_max / λ_min — how elongated the bowl is. At κ = 1 the contours are circles and −∇J points straight at the minimum. As κ grows the contours stretch into a narrow valley, the gradient points mostly across the valley rather than along it, and progress collapses.

Read the two columns together. From κ = 92.9 to κ = 9294.4 — a factor of 100 — iterations went 413 → 41674, a factor of 100.9. Iterations scale essentially linearly with the condition number. And at κ = 929437.6 the run did not finish at all: 200,000 iterations and still short of tolerance, reported as cap reached rather than dressed up as a result.

Notice also what happened to 2/lambda_max, the largest usable learning rate: 0.82 down to 1.27e-06. Rescaling one column by 1000 shrank the whole safe range for α by roughly a million.

---

The Elliptical Ravine & Conditioning (Kappa) Sandbox

Run live gradient descent simulations on a quadratic cost surface in your browser. Choose a conditioning multiplier to squash the bowl into a narrow ravine, and adjust the learning rate $\alpha$ to watch how the descent path zigzags, overshoots, or explodes!

Elliptical Contour & Zigzag Simulator

Adjust the condition number (kappa) to squash the cost surface. See why the gradient-descent ball zigzags on a ravine.

Conditioning: κ = 1.0 (Round Bowl)

Learning Rate (α): 0.15

Red dot is the start point (-0.85, -0.85); Green is the final step.

Round Bowl (κ = 1.0): Contours are circular. The gradient points directly towards the minimum. Learning is extremely rapid and reaches the center in a single straight path.

danger

An unscaled feature can make gradient descent unusable, not just slow

This is a far sharper consequence of feature scaling than the accuracy differences measured in which models actually need it. There, skipping scaling cost some points of performance. Here it is the difference between 40 iterations and never finishing, and neither the code nor the data looks wrong while it happens — the cost just descends implausibly slowly.

The normal equation is completely immune to this: κ does not appear in it. Scaling matters for the iterative solver, and that is the trade you accept in exchange for O(np) steps.

---

Common Mistakes

#	Mistake	Wrong	Right
1	Saying "the gradient descent curve"	One plot	Two — cost vs iteration, and the line in data space
2	Copying α between sources	A learning rate is a number	The 1/2 convention halves every gradient; col1/col3 = 2.00000000
3	Thinking α must decay to converge	Needs a schedule	‖Δθ‖/‖∇J‖ = 0.100 always; the gradient shrinks
4	Expecting the algorithm to overshoot and bounce forever	Fixed step, fixed overshoot	Step contracted by 0.8000 per iteration, predicted exactly
5	Treating convexity as automatic	Cost surfaces are bowls	957/2000 chord violations for MSE on a sigmoid
6	Believing the chord test proves convexity	0 violations ⇒ convex	It fails to disprove it; the proof is XᵀX ⪰ 0
7	Generalising from the round bowl	Contours are circles	κ = 1.00 came from standardising; real κ reached 929437.6
8	Flipping the sign to "maximise the fit"	Ascent improves things	Ascent hit 6.33e+07 from an identical start
9	Assuming gradient descent only approximates	Iterative ⇒ inexact	It matched the OLS optimum to all five printed decimals
10	Blaming a slow run on α alone	Tune the learning rate	Check κ first — at 929437.6 no α rescues it
11	Stopping after a fixed iteration count	1000 steps is enough	Geometric decay ⇒ watch ‖∇J‖; ~10 steps per decimal digit here
12	Forgetting the intercept column in H	H = (2/n)XᵀX on features only	The column of ones is part of X, so part of H

---

Summary

Update	θ ← θ − α·∇J(θ)
Cost (these notes)	J = (1/n)·Σ(Xθ − y)²
Gradient	∇J = (2/n)·Xᵀ(Xθ − y)
Hessian	H = (2/n)·XᵀX, positive semi-definite always
Convex because	Every eigenvalue of a Gram matrix is ≥ 0
Step length	‖Δθ‖ = α·‖∇J‖ — exactly, every iteration
Contraction per step	max_i |1 − α·λᵢ|
Elongation	κ = λ_max / λ_min; iterations grow linearly in κ
Two curves	Cost vs iteration; fitted line in data space

Key takeaways

• Gradient descent is one line, θ ← θ − α·∇J(θ), and the minus sign is the algorithm — ascent from an identical start reached 6.33e+07 where descent reached 0.18502019
• "The gradient descent curve" names two different plots. The J column fell 29.46681 → 0.18502; the ŷ columns travelled to 0.91362, 5.00889 and 9.10416
• Gradient descent reached the OLS optimum to all five printed decimals — iterative does not mean approximate
• The 1/2 cost convention halves every gradient, which is arithmetically the same as halving α: the 1/2n run at α = 0.2 tracked the 1/n run at α = 0.1 with a cost ratio of 2.00000000 on every row
• Convexity is measurable: 0 violations in 2000 chord tests for MSE, 957 for the same squared error applied to a sigmoid. Convexity belongs to the loss-and-model pair, not to optimisation
• The chord test cannot prove convexity; XᵀX being positive semi-definite does
• Nothing programs the braking. ‖Δθ‖/‖∇J‖ was 0.100 — exactly α — on every iteration; the step shrinks only because the gradient does
• The contraction rate is predictable: predicted 0.8000 from max|1 − α·λ|, measured 0.8000
• Distance covered fell from 3.638102 over the first five iterations to 2.262e-09 over the last five, a ratio of 1.609e+09, with α never changing
• κ = 1.00 is what standardisation produced, not a general truth. Rescaling one feature drove κ to 929437.6, shrank the usable α from 0.82 to 1.27e-06, and left the run unfinished after 200,000 iterations
• Iterations scale linearly with κ: a 100× rise in κ (92.9 → 9294.4) gave a 100.9× rise in iterations (413 → 41674)

Next in this section: The Learning Rate — the one knob, its four failure modes, and the fact that the boundary between "works" and "explodes" is a number you can compute from λ_max before running anything

See also: Loss Functions for why a differentiable loss is a precondition for any of this · The Matrix Formulation for when to prefer the closed form · Feature Scaling and Transformation for the transform that turned the ravine back into a bowl

---

2. Implementation Lab

tip

Lab Exercise: Gradient Descent

An interactive, fully-functional Google Colab / Jupyter Notebook is available to experiment with this concept live in your browser.

How to run the lab:

1. Click the "Open In Colab" badge above to launch the interactive notebook.
2. Click "Run all" or execute cells individually using Shift + Enter.

Things to try inside the script:

• Experiment 1 (Convexity checklist): Change sig_cost's squared error in section 3 to cross-entropy log loss and run the chord test. Observe violations return to 0, isolating L2 as the non-convex culprit.
• Experiment 2 (Braking rate): Raise the learning rate in section 5 to 0.5 and watch the contraction factor head to exactly 0.0000, landing on the OLS optimum in one step.
• Experiment 3 (Rescaling speed): In section 6, add s = 10000 to the ladder. Compute the resulting condition number and iteration count before executing.

---

3. Common Mistakes

1. One Unified Curve

• The Misconception: "The term 'gradient descent curve' refers to a single, unique plot."
• Wrong Thinking: Confusing the Cost Descent Curve ($J$ dropping over iterations) with the parameter-space fitted-line movement.
• The Right Principle: The term refers to two different plots. Cost curves are for debugging the optimizer (is cost decreasing?). Parameter lines are for explaining the model (what has it learned?). Never present one to answer a question about the other.

2. Programmed Braking

• The Misconception: "The algorithm requires an explicit decay schedule to shrink step sizes as it approaches the minimum."
• Wrong Thinking: Adding manual learning rate decay because you expect the step size to stay constant if you don't.
• The Right Principle: Braking is free. Step length $\lVert \Delta\theta \rVert$ is exactly $\alpha \lVert \nabla J \rVert$ on every iteration. As the model approaches the minimum, the loss surface flattens, the gradient length $\lVert \nabla J \rVert$ shrinks, and step size contracts in exact proportion.

3. Automatic Convexity

• The Misconception: "Any loss function on any model will yield a convex, bowl-shaped optimization surface."
• Wrong Thinking: Assuming gradient descent is guaranteed to find the absolute global minimum for any model-loss combination.
• The Right Principle: Convexity is a property of the model-and-loss pair, not optimization itself. Standard MSE on linear regression is convex ($0$ chord violations in $2000$ checks), but the exact same squared error applied to a sigmoid is highly non-convex ($957$ violations out of $2000$).

4. Condition Number Immunity

• The Misconception: "Skipping feature scaling makes my gradient descent slightly less accurate."
• Wrong Thinking: Ignoring scaling because you expect the optimizer to eventually find the minimum anyway.
• The Right Principle: Unscaled features stretch circular bowls into narrow, deep ravines, blowing up the condition number $\kappa$. This makes gradient descent zigzag wildly, taking 41,674 iterations instead of 40 to converge, or failing to converge entirely. Always scale your features.

---

4. Summary

Core Theory

• Convexity: Guarantees that any path walked downhill reaches the single global minimum. Proven by positive semi-definite Hessians.
• Hessian: $H = (2/n)X^T X$ represents second-order curvature. Eigenvalues represent steepness along natural axes.
• Condition Number: $\kappa = \lambda_{\max}/\lambda_{\min}$ measures bowl elongation. Standardised data yields a circular $\kappa \approx 1$.
• Contraction: $\max_i \lvert 1 - \alpha \lambda_i \rvert$ is the exact geometric error-reduction multiplier per iteration.

Engineering Realities

• The Minus Sign: Flipping θ - α·∇J to + converts descent into accelerating runaway ascent (reaching $6.33 \times 10^7$ cost by iteration 40).
• Free Braking: Step sizes are naturally restricted as $\lVert \nabla J \rVert$ shrinks near flat optimums, without manual schedules.
• Kappa Scaling: Iterations to converge scale linearly with the condition number ($\kappa$ rises 100×, iterations rise 100.9×).
• 1/2 Convention: Halving costs halves gradients, effectively halving step lengths. Unscaled $\alpha$ parameters are not portable.

info

Key Takeaways

• Exact Convergence: Gradient descent converges exactly to the OLS analytical optimum (matching all five decimals), proving iterative does not mean approximate.
• Matrix Immunity: The closed-form Normal Equation is completely immune to conditioning ($\kappa$ does not appear in it), whereas gradient descent is severely paralyzed by it.
• Stopping Rules: Cost $J$ flattens long before the gradient length $\lVert \nabla J \rVert$ reaches 0, meaning cost-based stopping rules halt earlier than gradient-based ones.

Next in this section: The Learning Rate — the one knob, its four failure modes, and how the boundary between "works" and "explodes" is a number you can compute before running anything.

---

5. Active Recall

Attempt each question first, then click to reveal detailed answers, mathematical derivations, and sample explanations.

Interactive Checkpoint Quiz

Interactive Checkpoint: The Step-Shrinkage Mechanism

A student claims that because the learning rate $\alpha$ is held constant at 0.10, the step size taken on each iteration must also remain completely constant unless a decay schedule is programmed. Is this claim valid?

Review Flashcards

1. [THEORY] Why does the 1/2 convention in some cost functions make learning rates non-portable?

• The Math: If $J = \frac{1}{2n}\sum (X\theta - y)^2$, the derivative is $\nabla J = \frac{1}{n} X^T(X\theta - y)$.
• This is exactly half of the standard gradient magnitude ($\nabla J = \frac{2}{n}X^T(X\theta - y)$) used in MSE definitions.
• The Consequence: Because your step size is $\alpha \cdot \nabla J$, halving the gradient has the exact same effect as halving the learning rate. Thus, copying a stable learning rate $\alpha = 0.1$ from a $1/2n$ cost source into a standard $1/n$ OLS implementation yields twice the step length, causing immediate divergence and explosion.

2. [ANALYZE] Why do cost $J(\theta)$ and gradient length $\lVert \nabla J \rVert$ tell different stories, and what does this cost you in a stopping rule?

• The Discrepancy: Cost $J$ is a 1D scalar of the error; gradient length $\lVert \nabla J \rVert$ is the multi-dimensional vector magnitude of the slope.
• Approaching the minimum, the cost reaches $98\%$ of its final convergence limit very rapidly (e.g. iteration 20), while the gradient vector is still significant ($\approx 0.12478$).
• The Cost: If you use a cost-based stopping rule (e.g. stop when $\Delta J < 10^{-4}$), your optimizer will halt too early, leaving the coefficients and predictions unfinished. A gradient-based stopping rule is computationally more expensive but guarantees mathematical finality.

3. [THEORY] Prove why standard MSE on a linear model is guaranteed to be convex for any dataset.

• The Hessian: The second-order curvature is defined by the Hessian matrix: $H = \frac{2}{n} X^T X$
• Positive Semi-Definiteness: For any vector $v$, the quadratic form is: $v^T H v = \frac{2}{n} v^T X^T X v = \frac{2}{n} (X v)^T (X v) = \frac{2}{n} \lVert X v \rVert^2 \ge 0$
• Because the magnitude squared $\lVert X v \rVert^2$ is always greater than or equal to $0$, the Hessian's eigenvalues can never be negative. The loss surface is guaranteed to curve upward or be flat, preventing any saddle points or local pocket traps from existing.

4. [ANALYZE] Why does gradient ascent accelerate without limit while gradient descent converges?

• Descent Constraint: Gradient descent marches against the gradient. Since the quadratic paraboloid opens upward, walking down has a natural structural floor—the global minimum at the bottom, which is why descent stabilizes.
• Ascent Runaway: Gradient ascent adds the gradient, marching up the paraboloid. Because the bowl expands infinitely upward, there is no ceiling. The gradient length grows proportional to distance from the center, meaning each step is larger than the last, leading to exponential, infinite cost explosion ($6.33 \times 10^7$ by iteration 40).

5. [ANALYZE] Geometrically, why does feature scaling decide whether gradient descent takes 40 steps or never converges?

• The Ravine: Unscaled features stretch the circular cost contours into a highly elongated ravine ( condition number $\kappa \to 10^6$).
• The Cross-Over: Standing on a ravine wall, the direction of steepest descent is almost perpendicular to the floor. The gradient points directly at the opposite wall rather than along the corridor.
• The Collapse: The optimizer spends all of its steps overshooting, bouncing, and zigzagging wildly between the walls, and progress crawls to a halt. Standardizing features squeezes the ellipses back into circular bowls ($\kappa \to 1.0$), making the gradient point straight at the center.