A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Optimization theory for machine learning analyzes the convergence rates and computational complexity of training algorithms. Gradient descent on smooth convex functions converges at rate O(1/T), where T is the number of iterations. Stochastic gradient descent (SGD) — which uses a single random sample's gradient rather than the full gradient — converges at rate O(1/sqrt(T)) for convex problems, trading per-iteration cost for slower convergence. For strongly convex functions, both rates improve to O(exp(-T)) and O(1/T) respectively. The gap between GD and SGD rates reflects the fundamental tradeoff between computation per iteration and convergence speed, and the analysis of SGD noise explains why it often generalizes better than full-batch GD despite converging more slowly.
In practice, training a machine learning model means solving an optimization problem: find the parameters that minimize a loss function over training data. Optimization theory for ML provides the convergence rate guarantees that tell us how quickly different algorithms approach the optimum and how this depends on properties of the loss function.
The baseline is gradient descent (GD) on smooth convex functions. At each step, GD moves in the direction of the negative gradient: x_{t+1} = x_t - eta * gradient(f, x_t). For a function with L-Lipschitz gradients (the gradient does not change too fast), GD with step size eta = 1/L achieves f(x_T) - f(x*) <= O(L * ||x_0 - x*||^2 / T). This O(1/T) rate means halving the error requires doubling the iterations — slow but predictable. For strongly convex functions (which curve upward like a quadratic), the rate improves to exponential: f(x_T) - f(x*) <= O(exp(-mu*T/L)), where mu is the strong convexity parameter. The condition number kappa = L/mu controls the rate — ill-conditioned problems (large kappa) converge slowly.
Stochastic gradient descent replaces the full gradient with a gradient computed on a single (or mini-batch of) randomly sampled data point(s). The per-step cost drops from O(n) to O(1), but the gradient estimate is noisy. For convex functions, SGD converges at O(1/sqrt(T)) — slower than GD's O(1/T), but each step is n times cheaper. For strongly convex functions, SGD achieves O(1/T) — matching GD's convex rate but not its exponential rate in the strongly convex case. The noise prevents SGD from exploiting strong convexity as fully as GD can.
The practical implications are profound. For large datasets (n >> 1), SGD dominates because the per-iteration cost savings outweigh the slower convergence rate. Modern deep learning training is essentially SGD (or its adaptive variants like Adam), and the noise in SGD has been shown to have beneficial regularization effects — it biases the optimization toward flatter minima that generalize better. Variance reduction methods (SVRG, SAGA) achieve the best of both worlds: O(1/T) convergence with near-SGD per-step cost by periodically computing a full gradient to correct the stochastic noise. The landscape of optimization for ML is a rich interplay between convergence speed, computational cost, noise structure, and generalization — and the theory provides the precise quantitative tradeoffs that guide algorithm selection.