Optimization

Convexity, constraints and gradient-based training.

Optimization

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 x⋆=arg⁡min⁡xf(x)x^\star = \arg\min_x f(x), the input that makes the objective ff smallest. Maximizing ff is the same as minimizing −f-f.

Gradient and Hessian – The gradient ∇f(x)\nabla f(x) is the vector of partial derivatives and points uphill. The Hessian ∇2f(x)\nabla^2 f(x) is the matrix of second derivatives and measures curvature. At an unconstrained minimum, ∇f=0\nabla f = 0.

Positive semi-definite – A symmetric matrix AA is positive semi-definite, written A⪰0A \succeq 0, if v⊤Av≥0v^\top Av \ge 0 for all vv, or equivalently if all its eigenvalues are ≥0\ge 0. A⪯BA \preceq B means B−A⪰0B - A \succeq 0.

Convexity

Convex function – ff is convex if the straight line between any two points on its graph lies on or above the graph: for θ∈[0,1]\theta \in [0, 1],

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)

For differentiable ff this is equivalent to f(y)≥f(x)+∇f(x)⊤(y−x)f(y) \ge f(x) + \nabla f(x)^\top(y - x) (the function lies above every tangent), and for twice-differentiable ff to ∇2f⪰0\nabla^2 f \succeq 0 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 x↦Ax+bx \mapsto Ax + b, and pointwise maxima of convex functions are convex. Examples: any norm, −log⁡x-\log x, log-sum-exp, the logistic loss and the hinge loss.

Smoothness and strong convexity – ff is LL-smooth if its curvature is at most LL (∇2f⪯LI\nabla^2 f \preceq LI), and μ\mu-strongly convex if its curvature is at least μ\mu (∇2f⪰μI\nabla^2 f \succeq \mu I). The condition number κ=L/μ\kappa = L/\mu measures how stretched the level sets are; large κ\kappa means slow convergence.

Constrained problems

Lagrangian – To minimize f(x)f(x) subject to inequality constraints gi(x)≤0g_i(x) \le 0 and equality constraints hj(x)=0h_j(x) = 0, attach a Lagrange multiplier to each constraint:

L(x,λ,ν)=f(x)+∑iλigi(x)+∑jνjhj(x)\mathcal{L}(x, \lambda, \nu) = f(x) + \sum_i\lambda_ig_i(x) + \sum_j\nu_jh_j(x)

KKT conditions – The Karush–Kuhn–Tucker conditions characterize a constrained optimum:

ConditionMeaning
Stationarity∇xL=0\nabla_x\mathcal{L} = 0
Primal feasibilitygi(x)≤0g_i(x) \le 0, hj(x)=0h_j(x) = 0
Dual feasibilityλi≥0\lambda_i \ge 0
Complementary slacknessλigi(x)=0\lambda_ig_i(x) = 0: 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 x⊤Axx^\top Ax subject to x⊤x=1x^\top x = 1. Stationarity of x⊤Ax−ν(x⊤x−1)x^\top Ax - \nu(x^\top x - 1) gives Ax=νxAx = \nu x, so xx is an eigenvector and the maximum is the largest eigenvalue.

First-order methods

These use only the gradient. The learning rate η>0\eta > 0 is the step size.

Gradient descent – Step downhill:

xt+1=xt−η∇f(xt)x_{t+1} = x_t - \eta\nabla f(x_t)

It is stable for η\eta less than 2/L2/L. On a strongly convex function the error shrinks by a factor of roughly 1−1/κ1 - 1/\kappa per step.

Momentum – Keep a running velocity vv so steps accumulate along consistent directions and damp oscillations: v←βv+∇f(x)v \leftarrow \beta v + \nabla f(x), then x←x−ηvx \leftarrow x - \eta v, with β≈0.9\beta \approx 0.9. Nesterov's variant improves the rate to 1−1/κ1 - 1/\sqrt\kappa 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 gg:

MethodStep for each parameterNote
AdaGraddivide by ∑tgt2\sqrt{\sum_t g_t^2}good for sparse features; steps only ever shrink
RMSPropdivide by running average of g2\sqrt{\text{running average of } g^2}forgets old gradients
Adam (adaptive moment estimation)η m^/(v^+ϵ)\eta\,\hat m/(\sqrt{\hat v} + \epsilon)momentum plus RMSProp

Adam in full – With decay rates β1,β2\beta_1, \beta_2 and step count tt:

m←β1m+(1−β1)g,v←β2v+(1−β2)g2,m^=m1−β1t,v^=v1−β2tm \leftarrow \beta_1m + (1-\beta_1)g, \quad v \leftarrow \beta_2v + (1-\beta_2)g^2, \quad \hat m = \frac{m}{1-\beta_1^t}, \quad \hat v = \frac{v}{1-\beta_2^t}

The hats correct the bias from initializing mm and vv at zero. Typical values are β1=0.9\beta_1 = 0.9, β2=0.999\beta_2 = 0.999 (often 0.950.95 for large language models) and ϵ=10−8\epsilon = 10^{-8}.

AdamW – Weight decay shrinks parameters toward zero each step: x←x−ηλxx \leftarrow x - \eta\lambda x. Adding an L2 penalty to the loss inside Adam gets rescaled per parameter by v^\sqrt{\hat v}; 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:

xt+1=xt−(∇2f(xt))−1∇f(xt)x_{t+1} = x_t - \big(\nabla^2 f(x_t)\big)^{-1}\nabla f(x_t)

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 O(n3)O(n^3) for nn 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 JJ, Gauss–Newton uses J⊤JJ^\top J 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 cc, rescale it to length cc: g←g⋅c/∥g∥g \leftarrow g\cdot c/\lVert g\rVert.

Initialization – Choose initial weight variance so activations neither grow nor shrink through the layers. Xavier initialization uses Var⁡W=2/(nin+nout)\operatorname{Var}W = 2/(n_{\text{in}} + n_{\text{out}}); He initialization uses 2/nin2/n_{\text{in}} for ReLU networks, where ninn_{\text{in}} and noutn_{\text{out}} are a layer's input and output widths.

Batch size and learning rate – When multiplying the batch size by kk, multiply the learning rate by kk for SGD (or roughly k\sqrt k 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.