Extrema and optimization
Finding the best: maxima, minima, convexity and optimization under constraints. The mathematics behind training models, planning routes and allocating resources.
6 topics
Almost every problem in machine learning, operations research, robotics and engineering design can be written as minimize subject to some constraints. Calculus gives the necessary conditions (the derivative vanishes, or the gradient is a combination of constraint gradients), convexity tells when those conditions are also sufficient, and numerical methods (gradient descent, Newton) find the points that satisfy them.
Topics
Maxima and minima
A global minimum is the lowest value of anywhere; a local minimum is lowest only in a neighbourhood. In optimization the difference between the two is the difference between a good model and a stuck one.
Critical points and derivative tests
Where (or does not exist). Fermat: an interior extremum of a differentiable function is a critical point. The sign of then tells minimum (), maximum () or "look closer" ().
Convexity and concavity
is convex if the chord between any two points of its graph lies above the graph — equivalently, for smooth , if . For convex functions every local minimum is global, which is why convex problems are the ones optimization can reliably solve.
Constrained optimization
Minimize only over the points that satisfy constraints or : a budget, a physical limit, a probability that must sum to 1. The minimum can now sit on the boundary, where .
Lagrange multipliers
At a constrained optimum of subject to , the gradients are parallel: . The multiplier measures how much the optimum would improve if the constraint were relaxed.
KKT conditions
Lagrange multipliers for inequality constraints : multipliers are non-negative, and each is zero unless its constraint is active (complementary slackness). For convex problems the KKT conditions are necessary and sufficient.
Where this area leads in computing
ℒ AI and machine learning ★★★★★
- Loss function★★★★★←Maxima and minima, Convexity and concavity
- Support vector machines★★★★★←Convexity and concavity, Lagrange multipliers, KKT conditions
- Gradient descent★★★★★←Critical points and derivative tests
- Loss landscape★★★★★←Critical points and derivative tests, Convexity and concavity
- Regularization★★★★★←Lagrange multipliers