Optimization for Artificial Intelligence

An optimization problem asks for the input that minimizes (or maximizes) a given function, and the shape of that function determines how hard the problem is. A set is convex if the line segment between any two points in the set stays inside it, and a function is convex if the region above its graph forms a convex set — intuitively, a convex function curves upward everywhere, like a bowl (Boyd & Vandenberghe's Convex Optimization). The single most important consequence of convexity is that any local minimum of a convex function is automatically a global minimum, which means an algorithm that simply keeps moving downhill can never get permanently stuck in a suboptimal valley — a guarantee that does not hold for general, non-convex functions, where many different valleys of differing depth can coexist across the same landscape, some far shallower and less useful than the true global minimum an algorithm is actually searching for.

Gradient descent is the algorithm that operationalizes 'moving downhill': starting from an initial point, it repeatedly updates the input using x ← x − α∇f(x), where ∇f(x) is the gradient of the objective function and α is a small positive step size called the learning rate (Ruder's overview of gradient descent optimization algorithms). Consider minimizing f(x) = (x − 3)² starting from x₀ = 0 with learning rate α = 0.1: the gradient is f′(x) = 2(x − 3), so the first update is x₁ = 0 − 0.1 × 2(0 − 3) = 0.6; the second is x₂ = 0.6 − 0.1 × 2(0.6 − 3) = 1.08; the third is x₃ = 1.08 − 0.1 × 2(1.08 − 3) = 1.464 — each step moves closer to the true minimum at x = 3, with progressively smaller steps as the gradient itself shrinks near the minimum, illustrating how gradient descent naturally slows down as it approaches a solution.

Loss functions of deep neural networks are, in general, not convex — they can have many local minima and saddle points — yet gradient descent and its variants remain the dominant training method in practice, because empirically they tend to find parameter settings that generalize well even without a convexity guarantee (Boyd & Vandenberghe's book discusses convexity as the theoretically clean case; Ruder's survey documents how practitioners navigate non-convex loss surfaces in real training runs). The learning rate α plays an outsized role in this success: too small, and training crawls forward wastefully slowly, taking far longer than necessary to converge; too large, and updates can overshoot the minimum and even diverge entirely, which is why choosing and adapting the learning rate is one of the most consequential practical decisions in training any AI model, and why modern optimizers often shrink it automatically as training progresses.

Many optimization problems in AI are constrained: the search for a solution is restricted to inputs satisfying some equality or inequality, rather than free to roam anywhere in the input space. The method of Lagrange multipliers handles equality constraints by combining the objective and the constraint into a single new function, the Lagrangian, whose unconstrained critical points correspond to the original problem's constrained solutions (Boyd & Vandenberghe's Convex Optimization develops this alongside the more general Karush-Kuhn-Tucker, or KKT, conditions for problems that include inequality constraints as well). A classic AI example is the support vector machine, which searches for the maximum-margin decision boundary between two classes subject to the constraint that every training point be correctly classified — a constrained optimization problem solved precisely through this Lagrangian machinery, turning a geometric margin-maximization goal into a solvable algebraic problem with a unique, well-defined optimum.

When a dataset contains millions of examples, computing the exact gradient of the loss — which in principle requires summing a term over every single example — becomes prohibitively expensive to do at every optimization step. Stochastic gradient descent (SGD) solves this by estimating the gradient from a small random subset, or mini-batch, of the data at each step instead of the full dataset, trading a noisier gradient estimate for a dramatic reduction in per-step computational cost (Bottou, Curtis & Nocedal's Optimization Methods for Large-Scale Machine Learning provides a rigorous account of why this tradeoff works well in practice, even though each individual step is a worse approximation than a full-batch gradient; Ruder's overview surveys the many SGD variants — including momentum and adaptive learning-rate methods — built on this same mini-batch idea). This is precisely why virtually every large-scale neural network is trained with some flavor of SGD rather than full-batch gradient descent, since waiting to process an entire training corpus before taking even one update step would make training modern models take impractically long.

Duality offers a second, complementary perspective on a constrained optimization problem: alongside the original (primal) problem, one can construct a related dual problem, and under fairly general conditions the best value of the dual problem provides a lower bound on the best value of the primal — weak duality — while for many convex problems the two best values coincide exactly, called strong duality (Boyd & Vandenberghe). The support vector machine is again illustrative: its dual formulation, expressed entirely in terms of pairwise similarities (kernels) between training points rather than the original feature representation, is what makes the 'kernel trick' possible, letting SVMs learn nonlinear decision boundaries efficiently without ever explicitly constructing the high-dimensional features involved — a direct practical payoff of the abstract duality theory introduced here, and a reminder that reformulating a problem's dual can sometimes make an otherwise intractable computation cheap.