Optimization

Optimization is finding the best possible solution of an objective function—its maximum or minimum value—perhaps subject to constraints that delimit which solutions are admissible. It is a general mathematical idea, but in artificial intelligence it holds a central place: training a model is, literally, an optimization problem. A loss function is defined that measures how wrong the model is, and training consists of adjusting its parameters to minimize it.

The ingredients

Every optimization problem has three pieces: an objective function (or cost, or loss) to be minimized or maximized; decision variables that can be adjusted—in a model, its weights—; and, sometimes, constraints that bound the region of valid solutions. A solution that respects the constraints is “feasible”; among the feasible ones, the one that optimizes the objective function is the “optimal” one.

Convex and non-convex

The most important distinction is this. In a convex problem, every local minimum is also the global minimum: there are no traps, and it can be solved with guarantees. Training neural networks, by contrast, is non-convex: by chaining linear transformations with nonlinear activation functions, the loss landscape fills with valleys, and the optimizer may stop at a local minimum that is not the best.

Gradient descent

The dominant method in deep learning is gradient descent: it computes the slope (the gradient) of the loss with respect to each parameter and takes a small step in the direction that reduces it, repeating until convergence. It has variants depending on how much data it uses per step: stochastic gradient descent (SGD), which uses a single example, and mini-batch, which uses small batches and is the standard. On top of them, adaptive optimizers such as Adam (Kingma and Ba, 2015) are built, which adjust each parameter's step by combining information from recent gradients.

No guarantee of the global optimum

It is worth being honest: in non-convex problems there is no guarantee of reaching the global minimum, and in practice good local minima are sought. It works surprisingly well because, in the extremely high dimensions of a network, many of those minima have an error similar to the optimum and the sampling noise helps escape the worst ones. It is a robust empirical observation, not a theorem.