Optimization for Machine Learning
The methods used to actually train every model in this chapter.
On this page
Module 1 ended on empirical risk minimization: pick the function f that minimizes average loss on the training data. That's a clean mathematical statement — but it says nothing about how to actually find that minimizer. For a simple enough model (ordinary least squares, section 2.1.6) there's a closed-form answer. For almost everything else — logistic regression, SVMs, gradient boosted trees, every neural network ever trained — there is no formula you can write down and evaluate. You have to search for the minimum, iteratively, and the entire practice of machine learning runs on a fairly small number of search strategies, each with a real mathematical reason for existing.
This module is that toolbox, built from scratch: why gradient descent works at all, why it's slow in some situations and fast in others, what momentum and Adam are actually doing differently from plain gradient descent (not just "it's better," but the precise mechanism), how second-order methods use curvature to converge in far fewer steps, how L1-regularized problems are solved despite not being differentiable everywhere, how constrained problems (like the SVM's margin maximization, a later module) get turned into unconstrained ones via duality, and how EM turns an intractable maximum-likelihood problem into a sequence of tractable ones.
Every method in this module is an answer to the same question, asked under different assumptions about the function being minimized:
Take a step from the current parameters θₖ, in some direction d_k, of some size α_k. Plain gradient descent picks d_k = -∇f(θ_k) and a fixed or decaying α_k. Every other method in this module changes one or both of those two choices — a smarter direction (momentum, Newton's method), a smarter step size (AdaGrad, Adam), or a fundamentally different notion of "step" entirely (proximal operators for non-differentiable terms, coordinate descent for high dimensions, EM for latent-variable likelihoods). Seeing every method as a variation on this one update rule is the single most useful mental model for this entire module.
- 2.2.1 Convex Optimization Basics — the property (convexity) that makes "found a minimum" mean "found the minimum," and why most of classical ML is deliberately built to have this property even when it costs some flexibility.
- 2.2.2 Gradient Descent & Variants — the workhorse algorithm itself: batch vs. stochastic vs. mini-batch, and exactly how fast each one provably converges.
- 2.2.3 Accelerated & Adaptive Optimizers — momentum, Nesterov, AdaGrad, RMSProp, and Adam: what each one changes about the plain update rule above, and the specific failure mode of vanilla GD each one was invented to fix.
- 2.2.4 Second-Order & Quasi-Newton Methods — using curvature (the Hessian) to take a far better step than the gradient alone can suggest, and the quasi-Newton trick (BFGS/L-BFGS) that gets most of the benefit without ever forming the full Hessian.
- 2.2.5 Coordinate & Proximal Methods — what to do when the objective has a non-differentiable piece (like an L1 penalty) that plain gradient descent can't handle at all.
- 2.2.6 Constrained Optimization & Duality — Lagrange multipliers and KKT conditions, which turn "minimize this subject to these constraints" into a related, often easier, unconstrained problem — directly setting up the SVM module later in this chapter.
- 2.2.7 Expectation–Maximization as Optimization — a specialized optimizer for exactly one recurring situation (a likelihood that would be easy to maximize if you could see some hidden variable), used by Gaussian mixture models and several other later modules.
- Treating "optimizer" as an interchangeable hyperparameter to grid-search over without understanding why one might suit a given loss landscape better than another — each method in this module exists because a specific, nameable failure mode of a simpler method needed fixing.
- Assuming the fanciest available optimizer (Adam, L-BFGS) is always the right choice — plain gradient descent or SGD is still the correct tool in plenty of large-scale, well-conditioned settings, and second-order methods are often too expensive per step to be worth it outside smaller, well-behaved problems.
Going deeper
Almost everything here is written for smooth or piecewise-smooth objectives. Modern deep learning optimization theory (loss landscape geometry of massively over-parameterized networks, implicit regularization of SGD, why Adam specifically dominates for transformers) is a genuinely different and still-active research area built on top of these classical foundations — this module is the prerequisite for that conversation, not a substitute for it.
Start with 2.2.1, Convex Optimization Basics — every convergence guarantee in the rest of this module is stated in terms of convexity, so it's worth having that vocabulary solid before comparing what gradient descent, Newton's method, and everything in between can actually promise you.