Optimization for data analysis
My annotations of the book "Optimization for data analysis"
Open document ↗Reading order
- 1Introduction to Optimization for Data AnalysisStub. Why data analysis is, almost always, an optimization problem in disguise — surveyed through the running examples the rest of the book builds algorithms for: least squares, matrix factorization, support vector machines, logistic regression, and deep learning.
- 2Foundations of Smooth OptimizationStub. 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.
- 3Descent Methods and MomentumStub. The steepest-descent method and its convergence rates in the general, convex, and strongly convex cases; line-search strategies for choosing a descent direction and a steplength; convergence to approximate second-order points; mirror descent and the KL/PL properties as ways to extend convergence guarantees beyond plain convexity; then momentum methods motivated by differential equations, Nesterov's accelerated method (with its matching lower bound on achievable convergence rates), convergence for strongly and weakly convex functions, and conjugate gradient methods.
- 4Stochastic Gradient and Coordinate DescentStub. Two ways to make each iteration of descent cheaper than a full gradient step: stochastic gradient (noisy gradients, the incremental gradient method, the perceptron, empirical risk minimization, the randomized Kaczmarz method, convergence analysis under several noise models, and implementation details like epochs/minibatching/momentum), and coordinate descent (updating one coordinate — or a block — at a time, with randomized, cyclic, and random-permutation sampling orders and their different convergence guarantees).
- 5First-Order Methods for Constrained OptimizationStub. Extending descent methods to problems with an explicit constraint set: optimality conditions at a constrained minimum, Euclidean projection onto the feasible set, the projected gradient algorithm (short-step and backtracking variants, the smooth strongly convex case, momentum variants, alternative search directions), and the conditional gradient (Frank-Wolfe) method, which avoids projection entirely by solving a linear subproblem over the constraint set each step.
- 6Nonsmooth Optimization — Subgradients and Proximal MethodsStub. The calculus of nonsmooth convex functions: subgradients and subdifferentials, their relationship to directional derivatives, a calculus for combining them, optimality conditions for composite nonsmooth objectives, and proximal operators/the Moreau envelope (a smoothed surrogate for a nonsmooth function); then the resulting algorithms — subgradient descent, proximal-gradient methods for regularized optimization (with a convex-case convergence rate), proximal coordinate descent, and the proximal point method.
- 7Duality and Lagrangian MethodsStub. The quadratic penalty function as a first, crude way to handle constraints; Lagrangians and duality (the dual problem as a lower bound on the primal, strong duality conditions), first-order (KKT) optimality conditions; and the dual algorithms this machinery enables — dual subgradient ascent, the augmented Lagrangian method, and ADMM — with applications to consensus optimization, utility maximization, and linear/quadratic programming; plus the supporting LP-duality and separation results from the appendix.
- 8Differentiation, Adjoints, and Automatic DifferentiationStub. Computing gradients of a nested composition of vector functions efficiently: the chain rule in that setting, the method of adjoints (computing a gradient backward through the composition, reusing intermediate results — the mathematical content behind backpropagation in deep learning), automatic differentiation as its general-purpose software realization, and alternative derivations via the Lagrangian and the implicit function theorem, with an extension to optimal control.