Convex Optimization: Gradient Descent, Nesterov Acceleration, KKT Conditions, and the ML Stack

2020-02-18 · Leonardo Benicio

Summary

A deep investigation of convex optimization—the engine of modern machine learning—from gradient descent and Nesterov momentum to KKT conditions and interior-point methods.

Convex optimization is the mathematical engine of modern machine learning. Every time you train a linear regression, a support vector machine, or a neural network with a convex loss, you are solving a convex optimization problem. The theory of convex optimization—the conditions under which local minima are global, the algorithms that converge to those minima, and the duality that connects primal and dual perspectives—is one of the crowning achievements of applied mathematics.

A convex optimization problem minimizes a convex function (f) over a convex set (\mathcal{X}):

[ \min_{x \in \mathcal{X}} f(x) ]

A function (f) is convex if its epigraph is a convex set, equivalently if (f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y)) for all (x, y) and (\lambda \in [0,1]). A differentiable function is convex iff its gradient is monotone: (\langle \nabla f(x) - \nabla f(y), x - y \rangle \geq 0), or equivalently (f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle) for all (x, y) (the first-order convexity condition). The key property: any local minimum of a convex function over a convex set is a global minimum. This eliminates the “local minima trap” that plagues non-convex optimization and makes convex problems tractable.

1. Gradient Descent and Convergence Rates

Gradient descent is the simplest and most widely used convex optimization algorithm. Starting from (x_0 \in \mathcal{X}), iterate:

[ x*{t+1} = \Pi*{\mathcal{X}}(x_t - \eta_t \nabla f(x_t)) ]

where (\Pi_{\mathcal{X}}) is the Euclidean projection onto (\mathcal{X}). For convex Lipschitz functions (where (|\nabla f(x)| \leq G)), gradient descent with step size (\eta_t = \frac{R}{G\sqrt{T}}) achieves convergence rate:

[ f\left(\frac{1}{T}\sum_{t=1}^{T} x_t\right) - f^* \leq \frac{RG}{\sqrt{T}} ]

where (R = \max_{x \in \mathcal{X}} |x - x_0|). This (O(1/\sqrt{T})) rate is optimal for Lipschitz convex functions: no first-order method can achieve better than (\Omega(1/\sqrt{T})).

For smooth convex functions (where (\nabla f) is (L)-Lipschitz), gradient descent with constant step size (\eta = 1/L) achieves (O(1/T)) rate: (f(xT) - f^ \leq \frac{2L|x0 - x^|^2}{T}). For strongly convex functions (satisfying (f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle + \frac{\mu}{2}|y - x|^2)), gradient descent achieves linear convergence: (O(e^{-T \mu / L}))—the error decays geometrically. The condition number (\kappa = L / \mu) governs the convergence speed; ill-conditioned problems ((\kappa \gg 1)) converge slowly.

2. Nesterov Acceleration and Optimal Methods

Nesterov’s accelerated gradient descent (1983) achieves the optimal convergence rate for smooth convex functions: (O(1/T^2)) instead of (O(1/T)). The update uses momentum:

[ yt = x_t + \frac{t-1}{t+2}(x_t - x{t-1}), \quad x_{t+1} = y_t - \eta \nabla f(y_t) ]

The “momentum” term (\frac{t-1}{t+2}(xt - x{t-1})) pushes the iterate in the direction of previous steps, smoothing oscillations and accelerating convergence. Nesterov proved that this rate is optimal: no first-order method can beat (O(1/T^2)) for smooth convex functions.

For strongly convex functions, Nesterov’s accelerated method achieves linear convergence with rate (O(e^{-T \sqrt{\mu / L}})), compared to (O(e^{-T \mu / L})) for gradient descent. The acceleration shaves the dependence on the condition number from (\kappa) to (\sqrt{\kappa})—a dramatic improvement for ill-conditioned problems. This is the theoretical foundation for momentum methods in deep learning (Adam, RMSprop), where the “acceleration” phenomenon persists even for non-convex objectives, though without formal guarantees.

3. Constrained Optimization and KKT Conditions

Constrained convex optimization adds equality and inequality constraints:

[ \min_x f(x) \quad \text{s.t.} \quad g_i(x) \leq 0, ; h_j(x) = 0 ]

where (f) and (g_i) are convex and (h_j) are affine. The Karush-Kuhn-Tucker (KKT) conditions are necessary and sufficient for optimality under Slater’s condition (existence of a strictly feasible point). The KKT conditions introduce Lagrange multipliers (\lambda_i \geq 0) for inequality constraints and (\nu_j) for equality constraints:

[ \nabla f(x^) + \sum_i \lambda_i \nabla g_i(x^) + \sumj \nu_j \nabla h_j(x^) = 0 \quad \text{(stationarity)} ] [ \lambdai g_i(x^) = 0 \quad \text{(complementary slackness)} ] [ gi(x^) \leq 0, ; hj(x^) = 0 \quad \text{(primal feasibility)} ] [ \lambda_i \geq 0 \quad \text{(dual feasibility)} ]

The complementary slackness condition (\lambdai g_i(x^) = 0) means that inactive constraints ((gi(x^) < 0)) have zero Lagrange multipliers: they don’t affect the solution.

The KKT conditions are the foundation of convex duality. The Lagrangian (\mathcal{L}(x, \lambda, \nu) = f(x) + \sumi \lambda_i g_i(x) + \sum_j \nu_j h_j(x)) defines the dual function (q(\lambda, \nu) = \inf_x \mathcal{L}(x, \lambda, \nu)), which is concave. The dual problem (\max{\lambda \geq 0, \nu} q(\lambda, \nu)) lower-bounds the primal; strong duality (primal optimum equals dual optimum) holds under Slater’s condition. This duality is the basis for support vector machines (where dual variables become support vectors), dual ascent methods, and the convergence analysis of distributed optimization.

4. Stochastic Gradient Descent and the Modern ML Stack

In machine learning, the objective is typically a sum over training examples: (f(x) = \frac{1}{n} \sum*{i=1}^{n} f_i(x)), where (n) is the dataset size. Computing the full gradient is expensive when (n) is large. Stochastic gradient descent (SGD) samples a mini-batch (\mathcal{B}) and uses the approximate gradient (\frac{1}{|\mathcal{B}|} \sum*{i \in \mathcal{B}} \nabla f_i(x_t)).

For convex Lipschitz functions, SGD achieves (O(1/\sqrt{T})) convergence—the same rate as full gradient descent! The key reason: the variance of the stochastic gradient decays under averaging, and the total error is governed by the squared gradient norm, which SGD estimates with controlled variance. For smooth strongly convex functions, SGD achieves (O(1/T)) convergence (with appropriate decreasing step sizes), compared to the linear convergence of full gradient descent—a penalty for using stochastic approximations.

The modern ML stack—PyTorch, TensorFlow, JAX—implements SGD and its variants (Adam, AdamW, RMSprop) with automatic differentiation. The backpropagation algorithm efficiently computes gradients of loss functions with respect to millions of parameters using the chain rule through the computation graph. While the objectives are no longer convex (deep neural networks are highly non-convex), the theory of convex optimization provides the foundation and the intuition: stochastic first-order methods, momentum, and adaptive step sizes work remarkably well even beyond the convex world.

5. Summary

Convex optimization is the theoretical backbone of machine learning. Gradient descent with (O(1/T)) convergence for smooth functions, Nesterov’s acceleration with optimal (O(1/T^2)) rate, and the KKT conditions for constrained optimization provide the algorithmic and analytical framework. Stochastic gradient descent extends these methods to the large-data regime, enabling the training of models on datasets with billions of examples. While deep learning operates in the non-convex regime, the intuitions and techniques from convex optimization—momentum, adaptive step sizes, regularization—continue to guide practice.

6. Duality in Machine Learning: SVMs, Regularization, and Fenchel Duality

Convex duality is not merely theoretical—it is the computational engine behind many machine learning algorithms. The Support Vector Machine (SVM) primal problem:

[ \min_{w, b} \frac{1}{2}|w|^2 + C \sum_i \max(0, 1 - y_i(w^\top x_i + b)) ]

has a dual that is a quadratic program over dual variables (\alpha_i), with constraints (0 \leq \alpha_i \leq C). The dual is often easier to solve (via SMO—Sequential Minimal Optimization), and the dual solution reveals which training examples are support vectors (those with (\alpha_i > 0)).

Fenchel duality generalizes Lagrangian duality to convex functions. The Fenchel conjugate (f^*(y) = \sup_x \langle y, x \rangle - f(x)) transforms a convex function into its dual representation. Fenchel duality is the foundation for Bregman divergences (generalized distances used in mirror descent and information geometry) and for the representer theorem in kernel methods (which shows that the optimal solution to regularized empirical risk minimization lies in the span of the training examples).

The Moreau envelope (or Moreau-Yosida regularization) (Mf(x) = \min_y f(y) + \frac{1}{2\lambda}|y - x|^2) smooths a non-smooth convex function, enabling gradient-based optimization of non-smooth objectives. The proximal operator (\operatorname{prox}{\lambda f}(x) = \arg\min_y f(y) + \frac{1}{2\lambda}|y - x|^2) is the building block of proximal gradient methods (ISTA, FISTA) used in sparse regression, compressed sensing, and image denoising.

7. Non-Convex Optimization: Escaping Saddles and the Landscape Paradigm

While convex optimization theory is mature, deep learning operates in the non-convex regime. The surprising empirical success of SGD on non-convex neural network objectives has motivated a theory of “benign non-convexity.” The key insight: while the loss landscape of neural networks is non-convex, it is often “nice” in specific ways—local minima are nearly as good as global minima, saddle points are shallow and can be escaped by adding noise, and the loss surface has a “banded” structure where most directions have similar curvature.

Jin, Ge, Netrapalli, Kakade, and Jordan (2017) showed that noisy gradient descent escapes all strict saddle points and converges to a second-order stationary point (where the gradient is zero and the Hessian is positive semidefinite) in polynomial time. This result provides theoretical justification for why SGD works on non-convex problems: it finds points that are locally optimal, and for many neural network architectures, all local minima are nearly global.

The “landscape paradigm” studies the geometry of non-convex objectives. For matrix completion, phase retrieval, and dictionary learning, the objective function has no spurious local minima—all local minima are global—and gradient descent converges to a global optimum from random initialization. For neural networks with overparameterization (more parameters than training examples), the loss landscape is “interpolating” (zero training error) with a large connected region of global minima, and SGD finds a solution with good generalization properties due to implicit regularization.

8. Summary

For further reading, Boyd and Vandenberghe’s “Convex Optimization” (2004) is the comprehensive reference. Nesterov’s “Introductory Lectures on Convex Optimization” (2004) is elegant and deep. Bubeck’s “Convex Optimization: Algorithms and Complexity” (2015) provides a modern perspective. The reader is encouraged to implement gradient descent, Nesterov acceleration, and SGD on a simple logistic regression problem and observe the convergence rates—the (O(1/T^2)) acceleration is palpable even on small problems.

9. Distributed and Federated Optimization

Modern machine learning often requires distributed optimization: the objective is a sum over data shards stored on different machines, and communication is the bottleneck. Distributed gradient descent reduces communication by computing local gradients on each machine and averaging them periodically. The parameter server architecture (Li, Andersen, Park, Smola, Ahmed, Josifovski, Long, Shekita, Su, 2014) centralizes the averaging step; decentralized architectures (Lian, Zhang, Zhang, Hsieh, Zhang, Liu, 2017) use peer-to-peer communication to reach consensus on the gradient.

Federated learning (McMahan, Moore, Ramage, Hampson, Agüera y Arcas, 2017) extends distributed optimization to the setting where data cannot leave the client devices (for privacy reasons). The Federated Averaging (FedAvg) algorithm runs multiple local SGD steps on each client before communicating model updates to a central server. The convergence analysis of FedAvg must account for heterogeneous data distributions across clients (non-i.i.d. data), which creates a “client drift” that can slow or prevent convergence.

The communication complexity of distributed optimization—how many bits must be exchanged to achieve a target accuracy—connects to information theory and communication complexity. Gradient quantization (Alistarh, Grubic, Li, Tomioka, Vojnovic, 2017) reduces communication by sending quantized or sparsified gradients, trading off communication for convergence speed. The theory of distributed stochastic optimization is a vibrant frontier combining convex optimization, communication complexity, and systems engineering.

10. Convex Optimization in Control Theory and Model Predictive Control

Convex optimization is the computational engine of model predictive control (MPC), where at each time step, a convex optimization problem is solved to determine the optimal control actions over a receding horizon. MPC formulations with linear dynamics and convex costs are quadratic programs solvable in milliseconds, enabling real-time control of autonomous vehicles, chemical processes, and power grids.

The connection between convex optimization and control theory runs through Lyapunov stability: the value function of a convex optimal control problem is a Lyapunov function for the closed-loop system, guaranteeing stability. The duality between optimal control and convex optimization—the maximum principle of Pontryagin being the continuous-time analog of the KKT conditions—reveals the deep unity of these fields.

11. Summary

12. Summary and Further Perspectives

Convex optimization is the theoretical backbone of machine learning. Gradient descent with O(1/T) convergence for smooth functions, Nesterov’s acceleration with optimal O(1/T^2) rate, and the KKT conditions for constrained optimization provide the algorithmic and analytical framework. Stochastic gradient descent extends these methods to the large-data regime, enabling the training of models on datasets with billions of examples. While deep learning operates in the non-convex regime, the intuitions and techniques from convex optimization—momentum, adaptive step sizes, regularization—continue to guide practice.

The intellectual architecture of convex optimization—duality, optimality conditions, convergence rates—is one of the great achievements of 20th-century mathematics. It unifies perspectives from operations research (linear programming), numerical analysis (gradient methods), and statistics (maximum likelihood). The modern synthesis, combining optimization with automatic differentiation and GPU parallelism, has produced the deep learning revolution, but the theoretical core remains convex analysis. The extensions to distributed and federated optimization, non-convex landscape analysis, and the integration with control theory and model predictive control show that convex optimization continues to be a fertile and essential field.

For further reading, Boyd and Vandenberghe’s “Convex Optimization” (2004) is the comprehensive reference. Nesterov’s “Introductory Lectures on Convex Optimization” (2004) is elegant and deep. Bubeck’s “Convex Optimization: Algorithms and Complexity” (2015) provides a modern perspective. The reader is encouraged to implement gradient descent, Nesterov acceleration, and SGD on a simple logistic regression problem and observe the convergence rates—the O(1/T^2) acceleration is palpable even on small problems.

13. Convex Optimization and the Theory of Generalization

Convex optimization connects to statistical learning theory through the lens of uniform convergence and Rademacher complexity. The empirical risk minimizer (ERM)—the solution to the convex optimization problem that minimizes training error—generalizes to unseen data if the hypothesis class has bounded Rademacher complexity. For linear models with bounded norm, the Rademacher complexity is O(1/√n), giving the standard O(1/√n) generalization bound.

The interplay between optimization accuracy and generalization is subtle. In the classical view, one should optimize the training objective to high precision and then rely on uniform convergence for generalization. In the modern “interpolating” regime (where models have more parameters than training examples and achieve zero training error), generalization occurs despite perfect fitting of noisy labels, contradicting classical generalization bounds. The “double descent” phenomenon—where test error decreases, then increases, then decreases again as model complexity grows—defies classical statistical intuition but is explained by the spectral properties of the Hessian of the training loss.

14. The Future: Differentiable Programming and Optimization as a Layer

The trend in machine learning is to embed optimization problems as layers within larger neural networks—“differentiable programming.” For example, the Sinkhorn algorithm for optimal transport is an iterative projection procedure that can be unrolled and differentiated through, enabling end-to-end learning of cost functions for matching problems. Convex optimization layers (Amos and Kolter, 2017) allow neural networks to output solutions to convex optimization problems, with gradients computed by differentiating through the KKT conditions.

This “learning to optimize” paradigm—where the parameters of an optimization problem (cost vectors, constraint matrices) are themselves learned from data—combines the rigor of convex optimization with the flexibility of deep learning. The backpropagation of gradients through convex optimization problems relies on the implicit function theorem applied to the KKT conditions, a beautiful synthesis of classical optimization theory and modern automatic differentiation.

15. Conclusion

Convex optimization is the mathematical language of machine learning. From the convergence rates of gradient descent to the duality of SVMs to the KKT conditions for constrained problems, convex analysis provides the theoretical foundation. The extensions—stochastic optimization, distributed optimization, federated learning, and differentiable programming—demonstrate the continuing vitality of convex optimization in the era of deep learning. The theory of convex optimization is not a closed chapter but an evolving framework that adapts to new computational paradigms while retaining its rigorous core.

16. Proximal Methods and Sparse Optimization

The proximal gradient method generalizes gradient descent to objectives of the form f(x) + g(x), where f is smooth and convex and g is convex but possibly non-smooth (e.g., the L1 norm for sparsity). The proximal operator generalizes the Euclidean projection: prox_g(x) = argmin_y g(y) + 1/(2λ) ||y-x||^2. For g(x) = λ||x||_1 (L1 regularization), the proximal operator is soft thresholding: [prox(x)]_i = sign(x_i) max(0, |x_i| - λ). This is the foundation of iterative shrinkage-thresholding algorithms (ISTA) and their accelerated variants (FISTA) that are widely used in compressed sensing and sparse regression.

The Alternating Direction Method of Multipliers (ADMM) decomposes a large convex optimization problem into smaller subproblems coupled through a consensus constraint. ADMM is particularly effective for distributed optimization (where data is partitioned across machines) and for problems with separable structure (e.g., the lasso with a total variation penalty in image processing). ADMM converges at a rate of O(1/T) for general convex problems and linearly for strongly convex problems, making it competitive with primal-dual interior-point methods for large-scale problems.

17. The Theory-Practice Gap in Deep Learning Optimization

Convex optimization theory provides the foundation for understanding optimization in machine learning, but deep learning operates in a non-convex regime where the classical theory does not directly apply. The “empirical risk minimization” objective of a deep neural network is highly non-convex, with many local minima and saddle points. Yet SGD with momentum and weight decay consistently finds solutions that generalize well. This “theory-practice gap” has motivated new theoretical frameworks: the “landscape analysis” of neural network objectives, the “mean-field” theory of overparameterized networks, and the “implicit regularization” of SGD.

The Neural Tangent Kernel (NTK) theory (Jacot, Gabriel, Hongler, 2018) shows that infinitely wide neural networks trained with gradient descent behave like kernel methods with a deterministic kernel—the NTK. In this regime, the optimization is convex in function space, and gradient descent converges to the global minimum. While real neural networks are finite-width, the NTK theory provides a tractable model for understanding optimization dynamics, and the insights (e.g., the importance of proper initialization and learning rate scaling) have influenced practical training recipes.

18. Conclusion

Convex optimization is the mathematical language of machine learning, providing the theoretical foundation for algorithms that train models, select features, and make predictions. The convergence rates of gradient descent, the acceleration of Nesterov, the KKT conditions for constrained problems, and the duality framework for SVMs are all convex optimization results. While deep learning challenges the convex paradigm, the concepts—gradients, momentum, regularization, duality—remain central. Convex optimization thus serves as both a rigorous theory for classical machine learning and a conceptual compass for navigating the non-convex terrain of deep learning.

19. Optimization for Causal Inference and Decision Making

Convex optimization is increasingly used in causal inference and decision making. The problem of estimating treatment effects from observational data—central to medicine, economics, and public policy—can be formulated as a convex optimization problem: minimize the bias of the estimate subject to balance constraints on the covariates. The “synthetic control method” (Abadie, Diamond, Hainmueller, 2010), used to estimate the effect of policy interventions, solves a convex optimization problem to construct a weighted combination of control units that matches the treated unit on pre-intervention outcomes.

In reinforcement learning, the “policy gradient theorem” reduces the problem of optimizing a stochastic policy to gradient ascent on the expected return, which is a non-convex objective amenable to stochastic first-order methods. The “trust region policy optimization” (TRPO) and “proximal policy optimization” (PPO) algorithms use ideas from convex optimization—trust regions, proximal operators, natural gradients—to stabilize policy updates in deep RL. The connection between convex optimization and RL is bidirectional: RL provides challenging non-convex optimization problems that push the boundaries of optimization theory.

20. The Unreasonable Effectiveness of First-Order Methods

First-order methods—gradient descent and its variants—are remarkably effective for machine learning. Despite using only gradient information (no Hessians or higher-order derivatives), SGD and Adam train models with billions of parameters on datasets with billions of examples. The theoretical explanation is multifaceted: (1) the objectives are “nice” in ways that theory is only beginning to understand (the “landscape” paradigm), (2) overparameterization makes the optimization easier (the NTK and mean-field theories), and (3) the stochasticity of mini-batch sampling provides implicit regularization that favors solutions with good generalization.

The success of first-order methods vindicates the convex optimization perspective while transcending it. The conceptual toolkit—gradients, step sizes, momentum, convergence rates—remains indispensable. The challenges—non-convexity, stochasticity, high dimensionality, distributed computing—push the theory beyond its classical boundaries. Convex optimization provides the foundation, but the edifice built upon it—deep learning, reinforcement learning, causal inference—extends far beyond the convex world.

21. Conclusion

Convex optimization is the mathematical backbone of machine learning, providing the algorithms, the analysis, and the intuition that underlie modern AI. From the convergence rates of gradient descent to the duality of SVMs, from the KKT conditions for constrained problems to the proximal methods for sparse recovery, convex analysis is the language in which the theory of learning is written. While deep learning operates in a non-convex regime, the concepts of convex optimization—gradients, momentum, regularization, duality—remain the essential tools for understanding and improving these systems.

22. Optimization in the Age of Large Language Models

Large language models (LLMs) like GPT-4 and Claude are trained using stochastic gradient descent variants (AdamW, usually) on hundreds of billions of tokens. The optimization problem is staggeringly large—billions of parameters, trillions of floating-point operations—and yet SGD converges reliably to solutions that generalize remarkably well. Why? The theory is still catching up, but several explanations have emerged.

The “lottery ticket hypothesis” (Frankle and Carbin, 2019) posits that within a randomly initialized large network, there exists a sparse subnetwork (a “winning ticket”) that can be trained in isolation to achieve comparable performance. SGD discovers these winning tickets implicitly through the training process. The “grokking” phenomenon (Power et al., 2022) describes a sudden transition from memorization to generalization long after the training loss has plateaued—a phase transition in the optimization dynamics that is not predicted by classical convex optimization theory.

These phenomena challenge our understanding of optimization and generalization. They suggest that the optimization landscape of overparameterized neural networks has structure that we are only beginning to grasp—a structure that enables SGD to find solutions that generalize despite the non-convexity of the objective. The theory of optimization in the age of LLMs is an active and exciting frontier, where classical convex optimization provides the foundation but new ideas are needed to explain the remarkable success of deep learning.

23. Conclusion

Convex optimization is the mathematical language in which the theory of learning is written. From the convergence rates of gradient descent to the duality of SVMs, from the KKT conditions to the proximal methods, convex analysis provides the algorithms, the guarantees, and the intuition. While deep learning challenges the convex paradigm, the conceptual framework—gradients, momentum, regularization, convergence rates—remains essential. The future of optimization lies in extending this framework to the non-convex, high-dimensional, and overparameterized regime where modern machine learning operates.

The duality between primal and dual optimization problems is one of the most powerful ideas in convex analysis. Weak duality guarantees that the dual provides a lower bound on the primal; strong duality, under constraint qualifications like Slater’s condition, guarantees equality. The dual variables—Lagrange multipliers—have the economic interpretation of shadow prices: they measure the sensitivity of the optimal value to constraint perturbations. In machine learning, duality transforms the primal SVM problem (a constrained quadratic program) into a dual problem with simple box constraints, solvable by sequential minimal optimization. In reinforcement learning, the dual of the linear programming formulation of an MDP yields the optimal value function and policy. Duality thus provides both computational tools (dual algorithms) and conceptual insights (the interpretation of learning as optimization with constraints).

The backpropagation algorithm, which computes gradients of loss functions with respect to millions of parameters using the chain rule through a computation graph, is the computational engine of deep learning. Backpropagation is essentially automatic differentiation applied to neural networks: it computes the gradient of a scalar output with respect to all inputs in time proportional to the cost of computing the output itself. This “cheap gradient principle” is what makes gradient-based optimization feasible for deep networks: each iteration of SGD costs roughly the same as evaluating the network on a mini-batch. The development of automatic differentiation frameworks—Theano, TensorFlow, PyTorch, JAX—has made gradient computation transparent and efficient, enabling the rapid experimentation that has driven progress in deep learning. The combination of stochastic gradient descent, backpropagation, and GPU parallelism is the algorithmic triad that powers modern AI.

The AdaGrad, RMSprop, and Adam algorithms are adaptive variants of SGD that adjust the learning rate for each parameter based on the historical gradients. AdaGrad (Duchi, Hazan, Singer, 2011) accumulates the sum of squared gradients and divides the learning rate by the square root of this sum, effectively giving each parameter its own learning rate that decays over time—large for infrequent features, small for frequent ones. RMSprop (Tieleman and Hinton, 2012) replaces the sum with an exponential moving average of squared gradients, preventing the learning rate from decaying too quickly. Adam (Kingma and Ba, 2015) combines RMSprop with momentum, maintaining both a moving average of gradients (for momentum) and a moving average of squared gradients (for adaptive scaling). Adam has become the default optimizer for deep learning, striking a balance between the theoretical guarantees of SGD and the practical need for fast, robust convergence on non-stationary, non-convex objectives. The development of adaptive optimizers illustrates how theoretical insights from convex optimization (the importance of per-coordinate scaling, the role of preconditioning) can be translated into practical algorithms that work well beyond the convex regime.

The future of optimization in machine learning is likely to involve a synthesis of classical convex methods with new ideas tailored to the overparameterized regime. Second-order methods (Newton, quasi-Newton, natural gradient), which use Hessian information to precondition the gradient, offer faster theoretical convergence but are currently too expensive for large-scale deep learning. Approximate second-order methods (K-FAC, Shampoo) balance the benefits of preconditioning with computational feasibility, and they are gaining traction for training large models. The theory of optimization in the “edge of stability” regime (where the sharpness of the loss landscape hovers near 2/η, the threshold between stability and divergence) suggests that SGD operates in a qualitatively different regime than classical convex optimization, and new theoretical frameworks are needed to understand its behavior. The interplay between empirical practice and theoretical understanding continues to drive progress in optimization for machine learning. The development of optimization theory and practice thus continues to evolve, driven by the ever-growing scale and complexity of machine learning models and the need for algorithms that are both theoretically sound and practically efficient.These developments ensure that convex optimization will remain a vibrant and essential field for decades to come.The convergence of theory and practice in optimization promises continued advances in the years ahead, as new algorithms and theoretical frameworks emerge to meet the challenges of ever-larger models and datasets.