Unit 5.2 · about 6 h
81 / 324Gradient descent, stochastic gradients and momentum
A controlled quadratic separates curvature-driven instability from gradient noise. It gives you predictions to test before trying an optimizer on a network.
- derive
- implement
You can now
- Derive the stable step-size interval and optimal fixed-step contraction for a positive definite quadratic.
- Implement gradient descent and heavy-ball momentum with explicit initial state and trajectory tests.
- Derive unbiased minibatch gradients and their covariance under independent sampling with replacement.
Covers
- Gradient descent on quadratic and general objectives
- Stochastic gradients, minibatches and noise
- Momentum and acceleration intuition
Study, in this order
4 steps
- EE364a: descent and line searchStanford EE364a - Convex Optimization
Lectures 15 and 16 notes: Descent methods (slide 10-5), Line search types (10-6), and Gradient descent method (10-7)
Depth · Stop before steepest descent and Newton's method.
- Descent on smooth objectivesConvex Optimization
Sections 9.2 and 9.3.1 (pp. 463 to 469)
Depth · Use the upper quadratic model to derive \(f(x-\eta g)\le f(x)-\eta(1-L\eta/2)\|g\|_2^2\). Distinguish this descent guarantee from the exact quadratic contraction below.
- GD, stochastic updates and minibatch noiseD2L - Optimization Algorithms
Sections 12.3.1 to 12.3.2 (Gradient Descent), 12.4.1 to 12.4.2 and 12.4.4 (Stochastic Gradient Descent; 12.4.4 compares sampling with and without replacement), and 12.5.2 (Minibatches)
Depth · Follow the adjacent GD and minibatch pages. Use the PyTorch tab for update cells only; skip datasets, training loops and timing claims.
- Heavy-ball dynamics on quadraticsD2L - Optimization Algorithms
Sections 12.6.1.2 to 12.6.1.4 and 12.6.3.1 to 12.6.3.2; PyTorch
momentum_2dcell
Focus on
- In the eigenbasis, GD errors obey \(e_{k+1,i}=(1-\eta\lambda_i)e_{k,i}\). Uniform convergence for all starts requires \(0<\eta<2/L\); \(\eta=2/(L+\mu)\) minimizes the worst factor to \((\kappa-1)/(\kappa+1)\).
- Heavy-ball uses \(x_{k+1}=x_k-\eta\operatorname{grad} f(x_k)+\beta(x_k-x_{k-1})\). Each eigenmode has characteristic polynomial \(r^2-(1+\beta-\eta\lambda)r+\beta\); repeated roots can produce a transient \(kr^k\) factor.
- For \(f=(1/n)\sum f_i\) and independent uniform indices, the minibatch average gradient is unbiased and has covariance \(\Sigma/B\). Sampling without replacement has a finite-population correction; reshuffling is not independent sampling.
- On a general \(L\)-smooth lower-bounded objective, the descent lemma controls objective decrease, not global optimality. Report full-objective residuals separately from noisy minibatch gradients.
Reproduce closed-book
float64 use \(Q=\operatorname{diag}(1,9)\), \(x_0=(1,1)\), \(x_{-1}=x_0\). After ten updates, GD with \(\eta=0.2\) has \(\|x_{10}\|_2=0.151850025\) and \(\|x_{10}\|_2/\|x_0\|_2=0.1073741824=0.8^{10}\) in exact arithmetic (measured absolute discrepancy 1.4e-17, allow 1e-12). Heavy-ball with \(\eta=0.25\) and \(\beta=0.25\) has \(\|x_{10}\|_2=0.0166875073\). At \(\eta=2/9\) GD's second coordinate alternates without shrinking; at \(\eta=0.23\) its magnitude after ten steps is 1.96715136. Then create rng=np.random.default_rng(5); make its only draw noise=rng.standard_normal((10000,4),dtype=np.float64), in array row order. np.var(noise[:,0],ddof=1) is 0.984311 and np.var(noise.mean(axis=1),ddof=1) is 0.251557. Derive the theoretical variances 1 and 1/4; these measured values are not exact theoretical equalities. Allow absolute 1e-6 for the displayed simulation values.Traps
- Including \(2/L\) in the convergent interval. The largest-curvature mode has multiplier -1 there.
- Claiming momentum contracts by its asymptotic spectral radius at every step. Repeated roots and initial state affect transients.
- Calling the squared-gradient moment a noise variance, or assuming four correlated gradients reduce variance by four. Independence matters.
Practice
D2L: momentum on multiple eigenvalues
Section 12.6.5, Exercise 2: \(f(x)=\sum\lambda_ix_i^2/2\), \(\lambda_i=2^{-i}\), \(x_i=1\)
Use \(i=0,\ldots,5\) and record all hyperparameters and initial velocity. Compare equal gradient-evaluation budgets; include an unstable GD step and explain the transient rather than claiming universal momentum acceleration. The section mini-project extends this to minibatch noise.
Self-test
-
Why is the quadratic rate a Euclidean error rate, not the same objective-gap rate?
Symmetry gives an orthonormal eigenbasis; positivity gives eigenvalues in \([\mu,L]\). Every error multiplier has magnitude at most \(\rho\), hence \(\|e_k\|_2\le\rho^k\|e_0\|_2\), including the base case \(k=0\). The quadratic gap weights squared errors, so it contracts by at most \(\rho^{2k}\). -
What happens at \(\eta=2/L\) if the initial error has no largest-eigenvalue component?
It may still converge in the remaining modes. The strict bound guarantees convergence for every initial error, rather than claiming every start fails at the boundary. -
Why does minibatch covariance divide by B?
Center each gradient and expand the covariance of their average. Independence makes cross-covariances zero; identical sampling gives \(B\) diagonal terms \(\Sigma\), divided by \(B^2\). Unbiasedness follows from uniform sampling of the average objective. -
Does constant-step SGD converge exactly when additive gradient noise persists?
Generally no. For scalar curvature \(\lambda\), independent zero-mean noise variance \(\sigma^2\) and \(|1-\eta\lambda|<1\) give limiting error variance \(\eta\sigma^2/(\lambda(2-\eta\lambda))\). The variance recurrence adds \(\eta^2\sigma^2\) at every step.
Completion criterion
Stop when
Your trajectories match the eigenmode predictions within 1e-12 in Euclidean norm, you explain one boundary failure, and you derive the minibatch covariance with its sampling assumptions.
Mark passed, then open 5.3 Only mark this when you can do it without notes.Leads to
- 3.5 Optimizers from SGD to AdamW Apply these update and state tests to neural-network training.
Resources for this unit
- Stanford EE364a - Convex Optimization Follow lectures 1-9 and 15-16; use lecture 17 only for KKT systems. Leave full interior-point treatment for later.
- Convex Optimization Read Chapters 1-5 and 9 with the course; use Chapter 10 only for equality-constrained Newton steps.
- D2L - Optimization Algorithms Use the convexity, GD, SGD, minibatch, momentum, AdaGrad, RMSProp, Adam and scheduler sections for ML derivations and code.
Also in this section
- Fundamentals of Numerical Computation Study §§1.1-1.4, 2.7-2.8, 3.2-3.4 and 4.2-4.3 for floating point, conditioning, stability, least squares and iteration error, in the Python edition.
- CVXPY basic and DCP tutorials Use as the solver oracle after deriving a constrained problem and its KKT conditions by hand.
- Proximal Algorithms Read Sections 1.1, 4.2 and the elementwise soft-thresholding formula in 6.5.2, then the lasso formulation on p. 196. Skip 7.1.1's penalty-scaling and Gram-rewrite errors on p. 197; derive the update from 4.2 and 6.5.2.
- PyTorch optimizer and gradient-clipping contracts Use AdamW's algorithm and
clip_grad_norm_'s parameters to locate weight decay and clipping precisely. Inspectstate_dictfor optimizer restart; no network training is assigned. - SciPy minimize: BFGS Read the BFGS method description and
gtol,maxiter,c1andc2options. Supply an analytic gradient and compare residuals and evaluation counts, not just iterations. - PyTorch numerical type information Read
torch.finfo'seps,maxandsmallest_normalfields and its subnormal note; inspectfloat64,float32,float16andbfloat16on CPU. - The Accuracy of Floating Point Summation Read Section 2's recursive-sum error bound and Section 3's pairwise and compensated summation algorithms. Leave the statistical error models and historical machine details aside.
- Accurately computing running variance Read the Welford mean and centered-sum recurrences. Prove the centered-sum invariant and translate the recurrence to NumPy; skip the C++ class.