Foundations of Smooth Optimization
Stub. The basic vocabulary for analyzing smooth optimization problems: a taxonomy of what "solving" an optimization problem can mean (global/local, exact/approximate), Taylor's theorem as the workhorse tool for every convergence proof that follows, first- and second-order characterizations of a minimum, and convex sets/functions and strongly convex functions as the regularity conditions that make guarantees possible at all.
Corresponds to Chapter 2. Fixes what a “solution” to can mean (a global minimizer is usually unattainable algorithmically for nonconvex ; a local minimizer, or even just a stationary/approximate-stationary point, is the realistic target), then builds the two technical tools everything later depends on: Taylor’s theorem (bounding near a point by its gradient/Hessian, which is where every convergence-rate proof in the book ultimately comes from) and the first- and second-order conditions characterizing a minimum (gradient zero, Hessian positive semidefinite). Convex sets and functions, and the stronger notion of strong convexity (a function sandwiched between two quadratics), are the regularity assumptions under which descent methods provably converge fast — see convex-analysis-for-bandits for the same convexity vocabulary developed independently in the online-learning setting.
Outline (TODO — flesh out each)
- A taxonomy of solutions to optimization problems
- Taylor’s theorem
- Characterizing minima of smooth functions
- Convex sets and functions
- Strongly convex functions