25  Optimization

Gradients tell us which way is downhill; optimization is the study of how to actually get to the bottom. This chapter explains why gradient descent and its accelerated, stochastic, and second-order variants work, what the adaptive per-coordinate methods that actually train today’s networks — AdaGrad, Adam, AdamW — add to them and where their guarantees break, when convexity guarantees they find the global optimum, how constraints and their multipliers reshape a problem through Lagrangian duality, and which numerical pitfalls turn a correct algorithm into a NaN. The main book’s optimization chapter is the reader’s practical first encounter: it should explain how to choose, configure, and diagnose optimizers in training. This appendix is its mathematical companion. It derives representative guarantees and failure modes, but is not intended to duplicate the main chapter’s workflow-oriented treatment.

Resources and Further Reading

A short, opinionated reading list for going deeper on optimization as it is used in machine learning: convexity, gradient and second-order methods, duality, and numerics.

Books

• Convex Optimization — Boyd & Vandenberghe — the standard reference on convex modeling, duality, and interior-point methods; the full PDF is free and the direct download is kept available by the authors.
• Numerical Optimization — Nocedal & Wright (2nd ed., Springer) — the definitive treatment of the algorithms (line search, trust region, quasi-Newton, conjugate gradient, interior-point) behind continuous optimization.
• Lectures on Convex Optimization — Nesterov (2nd ed., Springer) — the rigorous source for complexity bounds and accelerated first-order methods, by the inventor of acceleration.
• Optimization for Data Analysis — Wright & Recht (Cambridge, 2022) — a compact, modern account aimed squarely at data science: gradient, accelerated, stochastic, and coordinate methods.
• Mathematics for Machine Learning — Deisenroth, Faisal & Ong — the free continuous-optimization chapter is an excellent, self-contained bridge from calculus to gradient descent and constrained optimization.

Courses and video lectures

• Stanford EE364a: Convex Optimization I — Boyd — slides, homework, and software companion to the Boyd & Vandenberghe text; the 2023 lecture videos are on YouTube.
• CMU 10-725: Convex Optimization — Tibshirani — ML-oriented slides and scribed notes covering subgradients, proximal and stochastic methods, duality, and ADMM; matching Fall 2016 lecture videos.

Tutorials, notes, and surveys

• Optimization Methods for Large-Scale Machine Learning — Bottou, Curtis & Nocedal — the survey to read on why stochastic gradient methods dominate large-scale training, with a clean theory and practical analysis.
• An overview of gradient descent optimization algorithms — Ruder — a readable tour of momentum, Nesterov, Adagrad, RMSprop, and Adam and how they relate.
• Why Momentum Really Works — Goh (Distill) — an interactive deep dive that explains momentum and acceleration through the convex-quadratic model.
• Optimization (Chapter 5), Patterns, Predictions, and Actions — Hardt & Recht — a concise, free chapter framing optimization specifically as the engine of supervised learning.