Convexity

A function $f$ is convex if a line segment between any two points on its graph lies above the graph:

Equivalent characterizations:

• The Hessian Matrix $H$ is positive semi-definite everywhere
• Every local minimum is a global minimum
• First-order condition: $f(y) \geq f(x) + \nabla f(x)^\top(y-x)$ (tangent plane is a global lower bound)

Strictly convex: strict inequality → unique global minimum.

Convex optimization is "easy": gradient descent converges to the global optimum with guaranteed rates. Linear regression, logistic regression, and SVMs have convex objectives.

Neural networks are non-convex:

• Multiple local minima, saddle points, flat regions
• No guarantee of finding the global optimum
• Yet SGD works well in practice — modern understanding suggests most local minima in high dimensions are nearly as good as the global minimum, and saddle points are a bigger problem than local minima

Vocabulary: convex set, convex function, convex combination, convex hull, convex relaxation. These appear throughout optimization, operations research, and ML theory.

See also: Stochastic Gradient Descent, Hessian Matrix, Taylor Expansion