Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

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

8 minute read

Published:

TL;DR: A convex function lies below its chords and above its tangents, and those two facts give the guarantee that makes convex problems tractable: any stationary point is a global minimum. Convexity says nothing about speed, that is set by the condition number \(\kappa = L/\mu\), which controls both how elongated the level sets are and how slowly gradient descent crawls along them. Constraints are handled by Lagrange multipliers and, with inequalities, by KKT. Deep learning is non-convex, trains anyway, and the honest position is that we have partial explanations rather than a theory.

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

\[ f\bigl(\theta x + (1-\theta)y\bigr) \le \theta f(x) + (1-\theta)f(y) \quad\text{for all } \theta \in [0,1]. \]

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

\[ f(y) \ge f(x) + \nabla f(x)^\top (y - x) \quad \text{for all } x, y . \]

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

\[ \frac{\kappa - 1}{\kappa + 1}, \qquad\text{so reaching accuracy } \varepsilon \text{ takes } O\!\left(\kappa \log \tfrac{1}{\varepsilon}\right) \text{ iterations.} \]

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 12 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.

Gradient descent on a well-conditioned and an ill-conditioned quadraticLeft: circular level sets for a quadratic with condition number 1; a single straight arrow runs from the starting point directly to the centre. Right: elongated elliptical level sets with axis ratio about 3.16, for the quadratic one half of x squared plus ten y squared, condition number 10. The gradient descent path from the point (10, 3) with the optimal step size two elevenths zig-zags across the valley, visiting (8.18, minus 2.45), (6.69, 2.01) and (5.48, minus 1.64), shrinking by a factor of only nine elevenths per step. κ = 1: one step suffices κ = 10: zig-zag, factor 9/11 per step start start (10, 3) level sets have axis ratio √κ ≈ 3.16 gradient points at the optimum
Notice that the zig-zag is not a badly tuned step size, this is the optimal fixed step. Ill-conditioning is a property of the problem, which is why preconditioning, normalisation layers and adaptive methods all attack κ rather than η.

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

\[ \nabla f + \textstyle\sum_i \lambda_i \nabla g_i + \sum_j \nu_j \nabla h_j = 0,\quad g_i \le 0,\quad h_j = 0,\quad \lambda_i \ge 0,\quad \lambda_i\, g_i = 0 . \]

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.

Key Insight, convexity and conditioning answer different questions: convexity determines whether you find the optimum, conditioning determines how fast. A convex problem with \(\kappa = 10^6\) is hopeless in practice; a non-convex one with benign curvature trains in an afternoon. Almost every practical trick, batch normalisation, careful initialisation, Adam's diagonal preconditioner, residual connections, is aimed at the conditioning term, not the convexity one.
Interview trap, "convex means easy" and "non-convex means stuck". Both are wrong. Convexity gives no rate; an ill-conditioned convex problem can be far harder than a well-behaved non-convex one. Conversely, non-convex does not mean trapped in bad local minima, for large networks the empirical difficulty is saddles, plateaus and conditioning. A third trap: convexity of a composition. \(f(g(x))\) is convex when \(f\) is convex and non-decreasing and \(g\) is convex; drop the monotonicity and it fails, which is why a convex loss on top of a network is still non-convex overall.

Recap

  • Convex function: chords above the graph, tangents below it. Every local minimum is global, so \(\nabla f = 0\) certifies optimality.
  • First order: \(f(y) \ge f(x) + \nabla f(x)^\top(y-x)\). Second order: \(\nabla^2 f \succeq 0\), with \(\mu I \preceq \nabla^2 f \preceq LI\) giving strong convexity and smoothness.
  • Gradient descent contracts by \((\kappa-1)/(\kappa+1)\) per step with the best fixed step, so cost is \(O(\kappa\log(1/\varepsilon))\), or \(O(\sqrt{\kappa}\log(1/\varepsilon))\) with acceleration.
  • KKT: stationarity of the Lagrangian, primal and dual feasibility, \(\lambda_i \ge 0\), and complementary slackness \(\lambda_i g_i = 0\). Necessary in general, sufficient when convex.
  • Deep learning discards the global-optimality guarantee. Saddles rather than local minima dominate, over-parameterisation helps provably only in the NTK idealisation, minima are connected, and generalisation remains unexplained.

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.

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed, most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually, but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first, which is faster, shorter, and free of race conditions.