Convexity, Smoothness, and Optimization Landscapes

One-dimensional functions separate the definitions cleanly. Each separation below is one that a published theorem later leans on.

A set is convex when the entire line segment between any two points in the set stays inside it. A function is convex when its graph lies below every chord connecting two points. This global structure has a powerful consequence. Every local minimum of a convex function is global. If the function is strictly convex, a minimizer is unique when it exists.

Most deep networks are not convex in their parameters. Convex analysis stays valuable because many subproblems, losses and local approximations inherit convex structure. But the sentence "every local minimum is global" can also be proved without convexity, and then the hypotheses are the entire content of the result. Kawaguchi proved it in 2016 for deep linear networks of any depth and widths, under “no unrealistic assumptions”: the loss is non-convex and non-concave, every local minimum is a global minimum, and every critical point that is not a global minimum is a saddle point. His deep nonlinear result needs an independence assumption on top of that.

Laurent and von Brecht reached the same conclusion in 2018 for any convex differentiable loss, provided the hidden layers are at least as wide as the input or the output layer. They also state exactly which hypothesis is holding the result up: “This result is the strongest possible in the following sense: If the loss is convex and Lipschitz but not differentiable then deep linear networks can have sub-optimal local minima.” The conclusion survives the loss of convexity. It does not survive the loss of differentiability.

Each property answers a different question about the objective, and only some of them come with a number attached. Smoothness does. The β in β-smooth is what fixes the step size η=1/β under which Bubeck's Theorem 3.3 holds, and Su and colleagues state their accelerated rate under the matching hypothesis s ≤ 1/L. Convexity carries no constant of its own. Strong convexity adds a curvature lower bound. A Lipschitz function bounds how fast the output moves, not how fast the gradient does.

For differentiable convex f, the inequality f(y) ≥ f(x)+∇f(x)ᵀ(y−x) holds for all x and y in the domain. The tangent is a global lower bound. At a point with zero gradient, the inequality immediately proves global optimality. For nonsmooth convex functions, subgradients generalize the supporting-plane idea.

Drop convexity and there is no such certificate. The loss is not merely one of convenience. Murty and Kabadi proved in 1987 that deciding whether “a given feasible solution is not a local minimum” of a smooth nonconvex program is NP-complete. Thirty-five years later Ahmadi and Zhang restate that reduction as one “which shows the NP-hardness of deciding if a given point is a local minimizer of a quadratic program”. Then, in 2022, they settle a 1992 open problem of Pardalos and Vavasis: “We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance c^n (for any constant c ≥ 0) of a local minimizer of an n-variate quadratic function over a polytope.”

A quadratic over a polytope is close to the simplest nonconvex program that can be written down. The convex tangent-plane inequality is not a nicety on top of an otherwise similar problem. It is the difference between a one-line certificate and a task no polynomial-time algorithm can even approximate.

Before repeating a guarantee, trace every assumption that makes it valid. The published theorems show what a completed trace looks like. Laurent and von Brecht require a convex differentiable loss and hidden layers at least as wide as the input or the output layer. Kawaguchi's deep nonlinear case requires an independence assumption; his deep linear case does not. Bubeck's Theorem 3.3 requires a β-smooth convex objective and the step size η=1/β. Remove any one of those lines and what remains under it is a different statement from the one that was proved.

A zero gradient begins the classification. It does not finish it. Two groups argued from random matrix theory that in high dimensions the classification usually comes out "saddle". Dauphin and colleagues put it this way in 2014: “Here we argue, based on results from statistical physics, random matrix theory, neural network theory, and empirical evidence, that a deeper and more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest.” Choromanska and colleagues reached a compatible conclusion independently the next year, through a spin-glass analysis. The lowest critical values lie in a band above the global minimum, and the number of local minima outside that band “diminishes exponentially with the size of the network”. Their abstract names the three assumptions that buy this, which is the point. It is a result about a model of the landscape, not a survey of landscapes.

The flat column needs a warning of a different kind. Dinh and colleagues showed in 2017 that flatness is not a property of the model at all: “Specifically, when focusing on deep networks with rectifier units, we can exploit the particular geometry of parameter space induced by the inherent symmetries that these architectures exhibit to build equivalent models corresponding to arbitrarily sharper minima.” Same function, same generalization, arbitrarily sharper minimum. Four years later Petzka and colleagues were still naming “reparameterizations that change certain flatness measures but leave generalization unchanged” as the open obstacle, and proposed a relative flatness measure specifically to get around it. Curvature at a stationary point is read in a coordinate system. The coordinates are a modeling choice.