Optimization
Convex sets and functions, smoothness, strong convexity, and complete convergence proofs for gradient descent.
Level 1 — Core
Level 2 — Advanced
Problems (12)
Open in the browser| Solved | Problem | Type | Difficulty | Time |
|---|---|---|---|---|
| Every norm is convex, and the operator norm is a supremum of linear functions | Proof | 15 min | ||
| Existence and uniqueness of the minimiser | Proof | 15 min | ||
| First-order characterisation of convexity | Proof | 30 min | ||
| The exact step-size threshold on a quadratic | Proof | 15 min | ||
| Linear convergence under strong convexity | Proof | 30 min | ||
| Non-convex gradient descent reaches an approximate stationary point | Proof | 30 min | ||
| Separating convexity, strong convexity, smoothness and Lipschitzness | Proof | 30 min | ||
| Strong convexity implies the Polyak–Lojasiewicz inequality | Proof | 30 min | ||
| Gradient descent with exact line search on a quadratic | Proof | 1 hour | ||
| Implement gradient descent and verify all four rates run | Coding | 3 hours | ||
| Prove the O(1/t) rate for gradient descent abyss | Proof | 1 hour | ||
| Why the subgradient method needs averaging | Proof | 30 min |