Advanced Optimization
Proximal and projected methods, duality, acceleration, Newton and quasi-Newton methods, with Lyapunov analyses.
Level 2 — Advanced
Level 3 — Graduate
- Projected, Proximal and Constrained First-Order Methods13 min
Projection, the proximal operator, mirror descent and Frank–Wolfe, and the single inequality that makes all of their proofs work.
Projection onto a convex set is non-expansiveConvergence of projected gradient descentProximal operator - Momentum and Nesterov Acceleration12 min
Heavy ball, Nesterov's method, the estimate-sequence proof of the O(1/t^2) rate, and why acceleration is fragile.
Heavy ball on a quadraticNesterov acceleration for convex smooth functionsNesterov acceleration under strong convexity - Newton, Quasi-Newton and Conjugate Gradient9 min
Local quadratic convergence, the BFGS update, L-BFGS memory, and why second-order methods are rare in deep learning.
Local quadratic convergence of Newton's methodNewton's method is affine invariantThe secant condition and the BFGS update
Problems (17)
Open in the browser| Solved | Problem | Type | Difficulty | Time |
|---|---|---|---|---|
| The proximal operator of the l1 norm | Proof | 15 min | ||
| Weak duality holds without convexity | Proof | 15 min | ||
| Complementary slackness and active constraints | Proof | 30 min | ||
| Derive the dual of a quadratic program | Proof | 30 min | ||
| Newton's method is affine invariant | Proof | 30 min | ||
| Simulate and compare convergence rates run | Coding | 1 hour | ||
| The Frank–Wolfe duality gap certificate | Proof | 30 min | ||
| A convex problem with a duality gap | Proof | 30 min | ||
| Conjugate gradient and Krylov optimality | Proof | 1 hour | ||
| Local quadratic convergence of Newton's method | Proof | 1 hour | ||
| Projection onto the probability simplex | Proof | 1 hour | ||
| The BFGS update satisfies the secant condition | Proof | 30 min |