Global Convergence in Shallow Neural Networks

This direction is merged into another direction: non-convex optimization landscape (optimization landscape complexity). Its last version stays readable and citable here.

Version 1 of 118 papers19 conceptsfrozen 2026-10-04

In classical optimization theory, non-convexity is often treated as a death knell for global optimality. Because neural networks are inherently non-convex—due to both their architectural structure and non-linear activations—there is a theoretical expectation that gradient descent should get trapped in "spurious" local minima or stall at saddle points.

However, a growing body of research demonstrates that for shallow architectures, the optimization landscape is far more "benign" than previously feared. By analyzing two-layer ReLU networks, linear networks, and autoencoders, researchers have shown that gradient-based methods are mathematically guaranteed to find global optima under surprisingly broad conditions.

The Absence of Spurious Minima

The most direct explanation for why gradient descent works is that, in certain settings, there simply aren't any "bad" places to get stuck. Chenwei Wu, Jason D. Lee, and Jiajun Luo proved this rigorously for a two-layer ReLU network with two hidden units. In No Spurious Local Minima in a Two Hidden Unit ReLU Network, they demonstrate that every local minimum is also a global minimum. Any other critical points are "strict" saddle points—points that have at least one direction of negative curvature, allowing gradient descent to slide past them and continue toward the optimum.

This geometric intuition is complemented by the work of Yuandong Tian. In Symmetry-Breaking Convergence Analysis of Certain Two-layered Neural Networks with ReLU nonlinearity, Tian shows that while symmetric initializations can lead to dead ends, "symmetry-breaking" via standard random initialization is highly effective. For a single-neuron ReLU network, a random start near the origin has at least a 50% chance of landing directly in the convergence basin of the global optimum.

Even without non-linear activations, multi-layer linear networks are non-convex because the loss depends on the product of weight matrices. Despite this, they exhibit remarkable convergence properties.

Holger Rauhut and his colleagues re-imagined the training of these networks as a Riemannian gradient flow. In Learning deep linear neural networks: Riemannian gradient flows and convergence to global minimizers, they prove that this flow converges to a global minimizer from almost any random initialization. This was further bridged to practical, discrete-step optimization by Gabin Maxime Nguegnang and Ulrich Terstiege in Convergence of gradient descent for learning linear neural networks, confirming that the non-convexity inherent in the multi-layer structure does not prevent the discovery of optimal solutions.

The Proportional Regime in Autoencoders

Autoencoders present a unique challenge because they must learn to compress and then reconstruct data. Recent work by Alexander Shevchenko, Hamed Hassani, and Marco Mondelli has characterized the "fundamental limits" of these models.

In their research on Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods, they focus on the proportional regime, where the number of neurons scales linearly with the input dimension. They found that:

  1. Weight-tying is optimal: The common heuristic of making the decoder the transpose of the encoder is actually mathematically optimal.
  2. Linear Convergence: Gradient descent achieves a linear rate of convergence to the global optimum, provided the compression rate is below a specific threshold.

This suggests that the "bottleneck" structure of an autoencoder actually helps regularize the optimization landscape, making it easier for first-order methods to find the best possible representation.

Inductive Bias and Simple Targets

Beyond just finding a global minimum, researchers have looked at which minimum gradient descent finds. Alon Brutzkus and Amir Globerson explored this in Towards Understanding Learning in Neural Networks with Linear Teachers. They found that when training on linearly separable data, SGD forces weights to "cluster." This clustering acts as an inductive bias, compelling a highly expressive network to behave like a simple linear classifier, which ensures both global convergence and good generalization.

Finally, Arnulf Jentzen and Adrian Riekert have provided rigorous proofs for increasingly complex target functions. In A proof of convergence... for piecewise linear target functions, they show that as network width and the number of random initializations increase, the probability of gradient descent failing to find a global minimum drops to zero.

Summary of Intuition

The success of gradient descent in these shallow networks stems from three recurring properties:

  • Landscape Geometry: Spurious local minima are either non-existent or occupy a negligible portion of the space.
  • Symmetry Breaking: Random initialization naturally pushes the optimization path away from unstable saddle points.
  • Scaling Laws: In regimes where the network size is proportional to the data complexity, the non-convexity becomes "benign," allowing for efficient, linear convergence to the global theoretical limits.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_global_convergence_in_shallow_neural_net_d705722b,
  title = {Global Convergence in Shallow Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-convergence-in-shallow-neural-networks/rdr_d705722b5c5147248919e22ef49203d8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_global_convergence_in_shallow_neural_net_d705722b_v1,
  title = {Global Convergence in Shallow Neural Networks},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-convergence-in-shallow-neural-networks/rdr_d705722b5c5147248919e22ef49203d8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}