convex optimization
In plain wordsFinding the lowest point of a bowl-shaped landscape. Because a bowl has only one bottom, such problems can be solved reliably — unlike training a neural network, whose landscape is bumpy.
The minimization of a convex objective functionobjective function, n.: The score that an optimization process tries to push as low, or as high, as possible. For an AI, it defines what 'doing well' means during training. over a convex set, one that contains the straight segment between any two of its points. A function is convex if its graph never rises above the chord between two of its points; for twice-differentiable functions this means its HessianHessian, n.: A table of 'slopes of slopes' that describes how a surface curves: whether a point is the bottom of a bowl, the top of a hill or a mountain pass. is positive semidefinite everywhere. Convexity guarantees that every local minimumlocal minimum, n.: A spot lower than everything immediately around it, like the bottom of a small valley, even though a deeper valley may exist somewhere else. is global and that the minimizers form a convex set, and it supports duality theory (see Lagrange multiplierLagrange multiplier, n.: A mathematical device for finding the best answer when strict rules must be obeyed: each rule becomes an extra price that grows when the rule is broken.), optimality certificates and algorithms — interior-point, projected and proximal gradient methods — with provable, often polynomial-time, guarantees. Least squares (linear regressionlinear regression, n.: Fitting a straight line (or flat surface) through data points to predict one number from others — say, a house's price from its floor area — choosing the line that keeps prediction errors smallest.), logistic regressionlogistic regression, n.: A simple, widely used method for yes-or-no predictions that outputs a probability — say, a 70% chance a customer cancels — by passing a weighted sum of inputs through an S-shaped curve., support vector machinessupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too., the lassolasso, n.: A version of linear regression that keeps only the most useful inputs: it penalizes the total size of the weights so that many become exactly zero, leaving a simpler model. and linear programs are convex. Training deep networks is not, but convex analysis supplies much of the vocabulary and many of the tools used to study it.
The relaxation is convex, so the solver's answer comes with a certificate of optimality.
Origin
Convex sets and functions were studied by Hermann Minkowski around 1900 and Johan Jensen in 1906. Convex programming grew alongside linear programming from the late 1940s; R. Tyrrell Rockafellar's Convex Analysis (1970) systematized the theory, interior-point methods (Narendra Karmarkar, 1984; Yurii Nesterov and Arkadi Nemirovski, 1994) made large problems tractable, and Stephen Boyd and Lieven Vandenberghe's 2004 textbook spread the field through engineering and machine learning.
Usage note
A problem is convex only if both the objective and the feasible set are; maximizing a convex function is not convex optimization. 'Non-convex' is often used loosely to mean 'hard'.
Related
- optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible.
- objective functionobjective function, n.: The score that an optimization process tries to push as low, or as high, as possible. For an AI, it defines what 'doing well' means during training.
- local minimumlocal minimum, n.: A spot lower than everything immediately around it, like the bottom of a small valley, even though a deeper valley may exist somewhere else.
- Lagrange multiplierLagrange multiplier, n.: A mathematical device for finding the best answer when strict rules must be obeyed: each rule becomes an extra price that grows when the rule is broken.
- gradient descentgradient descent, n.: A method for training models by repeatedly nudging every setting a small step in whichever direction most reduces the error, like a hiker who cannot see the valley but keeps stepping wherever the ground tilts down.
- support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.
- loss landscapeloss landscape, n.: A way of picturing training as a journey across hilly terrain, where position stands for the model's settings and height for its error. Training searches for low valleys.
Sources
- Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
- Boyd, S. & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Mentioned in
optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible., linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input., local minimumlocal minimum, n.: A spot lower than everything immediately around it, like the bottom of a small valley, even though a deeper valley may exist somewhere else., objective functionobjective function, n.: The score that an optimization process tries to push as low, or as high, as possible. For an AI, it defines what 'doing well' means during training., Jensen's inequalityJensen's inequality, n.: A rule saying that for a bowl-shaped curve, the average of the outputs is at least the output of the average. It is the hidden step behind many proofs in machine learning., Lagrange multiplierLagrange multiplier, n.: A mathematical device for finding the best answer when strict rules must be obeyed: each rule becomes an extra price that grows when the rule is broken.