Optimization

Optimization is the task of choosing variables that make an objective small or large. In machine learning the variables are often parameters, the objective is a loss plus regularization, and the algorithm may be a deterministic solver, gradient descent, or a stochastic optimizer.

Defining math

A standard minimization problem is

$$\underset{x\in \mathcal{X}}{\min }f(x).$$

With equality and inequality constraints it becomes

$$\underset{x}{\min }f(x)\text{subject to}{h}_i(x)=0,g_j(x)\le 0.$$

Unconstrained differentiable optima satisfy the first-order stationarity condition $\nabla f(x^{\star })=0$, but that is only a candidate condition unless curvature or global structure is known. Convex optimization is special because local minima are global minima.

Worked example

Minimize $f(z)=(z_1-2{)}^2+(z_2+1{)}^2$. Applying the stationarity condition $\nabla f(z)=0$,

$$\nabla f(z)=\left[\begin{array}{c}2(z_1-2)\\ 2(z_2+1)\end{array}\right]=0⟹z^{\star }=(2,-1),$$

with objective $f(z^{\star })=0$. The two coordinates decouple, so each squared term is minimized independently at its own center. For nonconvex losses such as deep-network training, an optimizer may instead find only a useful stationary point, which is why optimizers are judged empirically as well as mathematically.

Caveats

The objective defines the behavior. A perfectly optimized proxy can still be misaligned with the real task, and poor scaling can make a mathematically simple problem numerically hard. Constraints, regularization, and numerical stability are part of the optimization problem, not afterthoughts.

References

• Boyd and Vandenberghe, Convex Optimization

Nav

Section — Mathematical Foundations

← Jacobians and Hessians Convex Optimization →