Mathematical Rules of Thumb, illustrated reader · Chapter 19

19Optimization

Scale, Search, and Certify

5 demonstrations follow the chapter's rules. Choose a value, watch the figure and the numbers change, and check your prediction. Every choice is precomputed from the notebook calculations.

Ask the chapter skill

“Help me use Chapter 19 for my question. Choose a rule, check its assumptions, and show how the result changes when an input changes.”

Use math-thumb-optimization from the companion's skill package. The demonstrations below also work on their own.

Examples use constructed inputs or the book's own values, disclosed in each panel. A picture illustrates a rule; its assumptions set its scope.

1Demonstration 1 of 5

Run gradient descent on a stiff quadratic

Why can α=.25 diverge?

Follow the computed objective through thirty updates, including a step beyond the stable range.

f(x,y)=12(x2+10y2),zk+1=zk−α∇f(zk) f(x,y)=\tfrac12(x^2+10y^2),\quad z_{k+1}=z_k-\alpha\nabla f(z_k)

Gradient step α. Convex quadratic, exact gradient, initial state (2,2), largest Hessian eigenvalue 10.

Predict first. Why can α=.25 diverge?

Choose an example

Run gradient descent on a stiff quadratic. For f=(x²+10y²)/2 the largest Hessian eigenvalue is 10. Step 0.1 is exactly 1/L, the safe default: it wipes out the stiff y-direction in one step, and x then shrinks by 0.9 per step.
Gradient step α: 0.1
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Step size
0.1
Initial objective
22
Objective after 30 steps
0.00359402
Final gradient norm
0.0847823

For f=(x²+10y²)/2 the largest Hessian eigenvalue is 10. Step 0.1 is exactly 1/L, the safe default: it wipes out the stiff y-direction in one step, and x then shrinks by 0.9 per step.

Use the idea

Use rule 19.2.1 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Convex quadratic, exact gradient, initial state (2,2), largest Hessian eigenvalue 10.

Check your understanding: Why can α=.25 diverge?
The y-direction multiplies by 1−10α=−1.5, whose magnitude exceeds one.

Book source: Rule 19.2.1: Start smooth convex gradient descent at step 1 over L. Demonstration C19-D01. Worked illustration.

2Demonstration 2 of 5

Shift exponentials without changing softmax

Does adding 1000 change softmax probabilities?

The stable calculation handles large offsets while preserving the probability ratios.

log⁡∑ieai=m+log⁡∑ieai−m,m=maxiai \log\sum_i e^{a_i}=m+\log\sum_i e^{a_i-m},\quad m=\max_i a_i

Common logit offset. Three logits offset+[0,1,2], binary64; stable shift avoids overflow in the exponential sum.

Predict first. Does adding 1000 change softmax probabilities?

Choose an example

Shift exponentials without changing softmax. Subtracting the maximum protects exponentiation. Adding a common offset changes log-sum-exp by that offset but leaves softmax probabilities unchanged; direct exp(1000) would overflow.
Common logit offset: 100
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Common offset
100
Stable log-sum-exp
102.408
Probabilities
0.0900306, 0.244728, 0.665241

Subtracting the maximum protects exponentiation. Adding a common offset changes log-sum-exp by that offset but leaves softmax probabilities unchanged; direct exp(1000) would overflow.

Use the idea

Use rule 19.1.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Three logits offset+[0,1,2], binary64; stable shift avoids overflow in the exponential sum.

Check your understanding: Does adding 1000 change softmax probabilities?
No. The common exponential factor cancels; log-sum-exp increases by 1000.

Book source: Rule 19.1.3: Shift by the maximum in log-sum-exp and softmax. Demonstration C19-D02. Worked illustration.

3Demonstration 3 of 5

Use a feasible stopping test at a boundary

Why is the raw gradient nonzero at the optimum?

Projection separates an unconstrained gradient from feasible descent in a constrained problem.

Gα(x)=x−Π[0,∞)(x−αf′(x))α G_\alpha(x)=\frac{x-\Pi_{[0,\infty)}(x-\alpha f^{\prime}(x))}{\alpha}

Feasible point x. f=(x+1)², x≥0, step α=1 for the displayed mapping.

Predict first. Why is the raw gradient nonzero at the optimum?

Choose an example

Use a feasible stopping test at a boundary. At x=0.5, raw gradient is 3, while the projected-gradient mapping is 0.5. At the boundary optimum x=0 the raw gradient remains 2; feasible descent is what matters.
Feasible point x: 0.5
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Selected feasible x
0.5
Raw gradient
3
Projected-gradient mapping (step=1)
0.5

At x=0.5, raw gradient is 3, while the projected-gradient mapping is 0.5. At the boundary optimum x=0 the raw gradient remains 2; feasible descent is what matters.

Use the idea

Use rule 19.3.3 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

f=(x+1)², x≥0, step α=1 for the displayed mapping.

Check your understanding: Why is the raw gradient nonzero at the optimum?
The decreasing direction points outside the feasible set. The projected-gradient mapping is zero at x=0.

Book source: Rule 19.3.3: Stop constrained gradient methods with a projected-gradient mapping. Demonstration C19-D03. Worked illustration.

4Demonstration 4 of 5

See why condition number sets the pace

How many steps reach 1e-6 at κ=100?

Gradient descent with step 1/L on a quadratic. The slow direction shrinks by 1−1/κ per step.

∥ek∥≤(1−1/κ)k∥e0∥ \|e_k\|\leq(1-1/\kappa)^k\|e_0\|

Condition number κ. Convex quadratic, exact gradients, step 1/L, worst-case direction.

Predict first. How many steps reach 1e-6 at κ=100?

Choose an example

See why condition number sets the pace. With step 1/L on a quadratic with κ=10, the slow direction shrinks by 1−1/κ=0.9 each step, so reaching 1e-6 takes 132 steps. Each tenfold rise in κ costs about tenfold more steps; rescaling variables can be cheaper than iterating.
Condition number κ: 10
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Condition number κ
10
Error factor per step
0.9
Steps to reach 1e-6
132

With step 1/L on a quadratic with κ=10, the slow direction shrinks by 1−1/κ=0.9 each step, so reaching 1e-6 takes 132 steps. Each tenfold rise in κ costs about tenfold more steps; rescaling variables can be cheaper than iterating.

Use the idea

Use rule 19.1.4 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Convex quadratic, exact gradients, step 1/L, worst-case direction.

Check your understanding: How many steps reach 1e-6 at κ=100?
1375 steps, versus 20 at κ=2. Rescaling variables is often cheaper than iterating.

Book source: Rule 19.1.4: Condition number predicts gradient-descent speed. Demonstration C19-D04. Worked illustration.

5Demonstration 5 of 5

See constant-step noise set a floor

Will running ten times longer at step .1 get closer to the optimum?

Noisy gradient descent on x²/2 drops quickly, then jitters around a level set by the step size, not by the number of iterations.

E[xk2]→ασ22−α E[x_k^2]\to\frac{\alpha\sigma^2}{2-\alpha}

Step size α. Gradient x plus independent N(0,1) noise, constant step, seed 1915, 20,000 iterations.

Predict first. Will running ten times longer at step .1 get closer to the optimum?

Choose an example

See constant-step noise set a floor. Minimizing x²/2 with gradient noise of SD 1 and constant step 0.1, the iterate stops improving at mean square 0.0529, close to the predicted floor α/(2−α)=0.0526. A larger step gets there fast but jitters more. To go lower, shrink the step over time or average the iterates; more iterations at a fixed step will not help.
Step size α: 0.1
Constructed teaching inputs; calculations executed locally. Supported menu choices are precomputed.

Calculated values

Step α
0.1
Gradient noise SD
1
Predicted mean-square floor
0.0526316
Observed mean square (last 10000 steps)
0.0529341
Seed
1915

Minimizing x²/2 with gradient noise of SD 1 and constant step 0.1, the iterate stops improving at mean square 0.0529, close to the predicted floor α/(2−α)=0.0526. A larger step gets there fast but jitters more. To go lower, shrink the step over time or average the iterates; more iterations at a fixed step will not help.

Use the idea

Use rule 19.1.5 when its stated conditions fit. Compare the calculation with your own decision threshold; retain the relevant error or uncertainty.

Where the conclusion applies

Gradient x plus independent N(0,1) noise, constant step, seed 1915, 20,000 iterations.

Check your understanding: Will running ten times longer at step .1 get closer to the optimum?
No. The mean square stays near .1/1.9≈.053. Shrink the step or average the iterates.

Book source: Rule 19.1.5: Expect constant-step stochastic optimization to hit a noise floor. Demonstration C19-D05. Worked illustration.

Bring the idea to a question of your own

Choose the relationship that answers your question, check its conditions, and compare the result with the accuracy or decision threshold you need.

The chapter skill can adapt these calculations to your inputs. It should name the assumptions, explain what the result supports, and say what still needs evidence. The chapter workbook adds a lab and three exercises with answers.