Optimization
Convexity, constraints and gradient-based training.
How to find the minimum of a function: when that is easy (convexity), how constraints are handled, and the iterative methods used to train models.
Setup
Optimization problem – Find , the input that makes the objective smallest. Maximizing is the same as minimizing .
Gradient and Hessian – The gradient is the vector of partial derivatives and points uphill. The Hessian is the matrix of second derivatives and measures curvature. At an unconstrained minimum, .
Positive semi-definite – A symmetric matrix is positive semi-definite, written , if for all , or equivalently if all its eigenvalues are . means .
Convexity
Convex function – is convex if the straight line between any two points on its graph lies on or above the graph: for ,
For differentiable this is equivalent to (the function lies above every tangent), and for twice-differentiable to everywhere.
For a convex function every local minimum is a global minimum, which is what makes convex problems tractable.
Building convex functions – Non-negative weighted sums, composition with an affine map , and pointwise maxima of convex functions are convex. Examples: any norm, , log-sum-exp, the logistic loss and the hinge loss.
Smoothness and strong convexity – is -smooth if its curvature is at most (), and -strongly convex if its curvature is at least (). The condition number measures how stretched the level sets are; large means slow convergence.
Constrained problems
Lagrangian – To minimize subject to inequality constraints and equality constraints , attach a Lagrange multiplier to each constraint:
KKT conditions – The Karush–Kuhn–Tucker conditions characterize a constrained optimum:
| Condition | Meaning |
|---|---|
| Stationarity | |
| Primal feasibility | , |
| Dual feasibility | |
| Complementary slackness | : a constraint either holds with equality or its multiplier is zero |
For a convex problem with a strictly feasible point (Slater's condition), the KKT conditions are necessary and sufficient.
Example: maximize subject to . Stationarity of gives , so is an eigenvector and the maximum is the largest eigenvalue.
First-order methods
These use only the gradient. The learning rate is the step size.
Gradient descent – Step downhill:
It is stable for less than . On a strongly convex function the error shrinks by a factor of roughly per step.
Momentum – Keep a running velocity so steps accumulate along consistent directions and damp oscillations: , then , with . Nesterov's variant improves the rate to per step.
Stochastic gradient descent (SGD) – Replace the full gradient with the gradient on a small random batch of data. It is an unbiased but noisy estimate; the noise needs a decaying learning rate to converge and also acts as a mild regularizer.
Adaptive methods – These give each parameter its own step size based on the size of its past gradients :
| Method | Step for each parameter | Note |
|---|---|---|
| AdaGrad | divide by | good for sparse features; steps only ever shrink |
| RMSProp | divide by | forgets old gradients |
| Adam (adaptive moment estimation) | momentum plus RMSProp |
Adam in full – With decay rates and step count :
The hats correct the bias from initializing and at zero. Typical values are , (often for large language models) and .
AdamW – Weight decay shrinks parameters toward zero each step: . Adding an L2 penalty to the loss inside Adam gets rescaled per parameter by ; AdamW applies the decay separately ("decoupled"), which works better.
Second-order methods
Newton's method – Use the curvature to jump to the minimum of the local quadratic approximation:
It converges quadratically near the optimum (the number of correct digits roughly doubles each step) and is unaffected by rescaling the inputs, but each step costs for parameters.
Approximations – Quasi-Newton methods such as BFGS (Broyden–Fletcher–Goldfarb–Shanno) and its limited-memory version L-BFGS build up an estimate of the inverse Hessian from successive gradients. For least-squares problems with Jacobian , Gauss–Newton uses as the Hessian; adding damping gives Levenberg–Marquardt. Natural gradient preconditions with the inverse Fisher information matrix.
Training neural networks
Learning-rate schedule – Warm up linearly from a small value, then decay (cosine or linear). Sudden loss spikes usually mean the learning rate is too high or the inputs are poorly scaled.
Gradient clipping – If the gradient norm exceeds a threshold , rescale it to length : .
Initialization – Choose initial weight variance so activations neither grow nor shrink through the layers. Xavier initialization uses ; He initialization uses for ReLU networks, where and are a layer's input and output widths.
Batch size and learning rate – When multiplying the batch size by , multiply the learning rate by for SGD (or roughly for Adam), up to a critical batch size beyond which larger batches stop helping.
In high dimensions, saddle points (flat in some directions, curving down in others) are far more common than bad local minima.