Convexity: What It Guarantees, and Why Deep Learning Works Without It

Sets, functions, and the one guarantee

A set $C$ is convex if the segment between any two of its points stays inside it. A function $f$ is convex if its domain is convex and

In words: the chord never dips below the graph. Equivalently, the epigraph — everything on or above the graph — is a convex set.

The payoff is a single theorem. Every local minimum of a convex function is a global minimum. The argument is two lines: suppose $x$ is a local minimum but $f(y) < f(x)$ for some $y$. Then for small $\theta$ the point $\theta y + (1-\theta)x$ lies inside the neighbourhood where $x$ was supposed to be optimal, yet convexity bounds its value by $\theta f(y) + (1-\theta)f(x) < f(x)$ — a contradiction. That is the entire reason convex problems are considered solved: there is nowhere to get stuck.

The two characterisations you will be asked for

For differentiable $f$, convexity is equivalent to the first-order condition

The tangent plane at any point is a global underestimator. Set $\nabla f(x) = 0$ and the right-hand side becomes $f(x)$, so $f(y) \ge f(x)$ everywhere — a vanishing gradient certifies global optimality, which is exactly what fails in the non-convex case.

For twice-differentiable $f$, the second-order condition is that the Hessian is positive semi-definite everywhere, $\nabla^2 f(x) \succeq 0$: no direction of negative curvature exists anywhere. If moreover $\nabla^2 f \succeq \mu I$ with $\mu > 0$, $f$ is $\mu$-strongly convex — it is at least as curved as a quadratic bowl. If $\nabla^2 f \preceq L I$, $f$ is $L$-smooth: its gradient is Lipschitz with constant $L$.

The condition number sets the speed

Convexity guarantees you arrive; $\kappa = L/\mu$ decides when. For $L$-smooth, $\mu$-strongly convex $f$, gradient descent with a fixed step contracts the distance to the optimum geometrically, and with the best fixed step $\eta = 2/(L+\mu)$ the factor per iteration is

Without strong convexity the rate degrades to $O(1/k)$, and Nesterov’s accelerated method improves the strongly convex count to $O(\sqrt{\kappa}\log(1/\varepsilon))$ — which is optimal for first-order methods on this class.

Take $f(x,y) = \tfrac12(x^2 + 10y^2)$, so $\mu = 1$, $L = 10$, $\kappa = 10$. The optimal step is $2/11$, and the per-iteration factor is $9/11 \approx 0.818$: roughly 28 iterations to gain one digit of accuracy, for a problem in two variables. Starting from $(10, 3)$, the iterates are $(8.18, -2.45)$, $(6.69, 2.01)$, $(5.48, -1.64)$ — the second coordinate flips sign every step while the first crawls. The level sets are ellipses with axis ratio $\sqrt{\kappa} \approx 3.16$, and the gradient points across the valley rather than along it.

Constraints: Lagrange and KKT

With an equality constraint, minimise $f(x)$ subject to $h(x) = 0$. At an optimum you cannot move along the constraint surface and decrease $f$, which means $\nabla f$ has no component tangent to the surface — so it must be parallel to $\nabla h$. Introduce a multiplier and write the Lagrangian $\mathcal{L}(x,\nu) = f(x) + \nu\, h(x)$; stationarity in $x$ recovers $\nabla f + \nu \nabla h = 0$, and stationarity in $\nu$ recovers the constraint.

Inequalities add one idea. For $\min f(x)$ subject to $g_i(x) \le 0$ and $h_j(x) = 0$, the KKT conditions at an optimum are

The last line is complementary slackness: either a constraint is active ($g_i = 0$) or its multiplier is zero, so inactive constraints exert no force. The sign condition $\lambda_i \ge 0$ encodes that an inequality pushes in one direction only. These are necessary at any optimum satisfying a constraint qualification, and for convex problems also sufficient. In a support vector machine the points with $\lambda_i > 0$ are precisely those on the margin — which is what “support vector” means.

The non-convex elephant

None of the above applies to a deep network. The loss is non-convex in the weights — even a two-layer network with permutation symmetry has factorially many equivalent minima — and yet stochastic gradient descent reliably finds solutions that generalise. What is actually established, as opposed to folklore:

• Saddle points, not local minima, are the obstacle. In high dimensions a random critical point has mixed curvature with overwhelming probability, and perturbed gradient methods provably escape strict saddles in polynomial time.
• Over-parameterisation helps, provably, but only in an idealisation. In the infinite-width neural tangent kernel limit training becomes effectively convex and gradient descent reaches a global minimum — but real networks learn features and the NTK does not, so this explains the idealisation, not the practice.
• Minima are connected, not isolated. Independently trained solutions can be joined by paths of near-constant loss, so the landscape looks more like broad connected valleys than separate basins.
• Generalisation is not explained. The same networks that fit real data also fit randomly permuted labels perfectly, so capacity arguments alone cannot say why the real solutions generalise.

Convexity is a certificate of global optimality that deep learning gives up; what replaces it is empirical.

References

1. Boyd, S., & Vandenberghe, L. Convex Optimization, ch. 2–5 and 9. Cambridge University Press, 2004.
2. Nesterov, Y. Lectures on Convex Optimization, 2nd ed. Springer, 2018.
3. Nocedal, J., & Wright, S. J. Numerical Optimization, 2nd ed., ch. 12. Springer, 2006.
4. Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., & Jordan, M. I. How to Escape Saddle Points Efficiently. ICML 2017.
5. Jacot, A., Gabriel, F., & Hongler, C. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. NeurIPS 2018.
6. Garipov, T., Izmailov, P., Podoprikhin, D., Vetrov, D., & Wilson, A. G. Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs. NeurIPS 2018.
7. Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. Understanding Deep Learning Requires Rethinking Generalization. ICLR 2017.