Deep learning works incredibly well in practice, but proving why it works mathematically is a tale of two worlds. If you restrict a neural network to a single hidden layer (a two-layer network), the mathematical landscape becomes surprisingly well-behaved. Under the right conditions of overparameterization, we can prove that gradient descent finds global minima, features are learned optimally, and models generalize cleanly even when memorizing noise.
However, as soon as we stack a third, fourth, or hundredth layer, this theoretical paradise collapses. The transition from shallow to deep models introduces a massive gap in convergence theory. In deep networks, layers interact dynamically, gradients flow through complex compositions of non-linearities, and the optimization landscape becomes highly non-convex and riddled with hierarchical dependencies.
The Shallow Paradise: What We Can Provably Guarantee
To understand why deep networks are hard to analyze, we must first look at what makes shallow networks tractable. For overparameterized two-layer networks, the optimization landscape can often be linearized or analyzed via local convexity and kernel regimes.
For instance, Du et al. demonstrated that for sufficiently wide two-layer ReLU networks, randomly initialized gradient descent converges to zero training loss at a linear rate. This global convergence holds despite the non-convex nature of the objective function. Similarly, Arora et al. provided a fine-grained analysis explaining how these shallow architectures optimize quickly and generalize well without merely memorizing random noise.
This mathematical tractability extends to many foundational properties of machine learning:
- Benign Overfitting: We can prove that non-linear, two-layer networks can perfectly interpolate noisy training data while maintaining optimal generalization capabilities (Frei et al.).
- Implicit Regularization: The stochastic noise in optimization isn't just random interference; Wang et al. proved that for shallow models, this noise structurally aligns with local curvature to help the trajectory escape sharp minima.
- Architectural Variations: Global convergence guarantees can be proven for specialized shallow architectures, such as one-hidden-layer convolutional networks (Lee et al.) and two-layer Kolmogorov-Arnold Networks (Tan et al.).
In almost all of these cases, the mathematical strategy relies on a core simplification: tracking how a single layer of representations moves relative to a fixed or simple output layer.
The Multi-Layer Obstacle: Compounded Non-Convexity
Why can't we just apply these shallow proofs layer-by-layer to deep networks? The core issue is compounded non-convexity and dynamic layer interaction.
In a two-layer network, the input features are transformed once, and the output layer simply takes a linear combination of them. In a deep network, the gradients of the first layer depend multiplicatively on the weights of all subsequent layers. If the weights in Layer 2 change, the entire optimization landscape for Layer 1 shifts. This coupling creates a cascading feedback loop that leads to vanishing or exploding gradients and highly unpredictable representation trajectories. As Zhou et al. noted, convergence theories developed for shallow models completely fail to account for these complex dependencies and gradient stability issues.
To make proofs tractable in deeper networks, theorists are often forced to introduce artificial constraints that do not reflect practical training. For example, Chen et al. established global convergence guarantees for multi-layer networks, but only by requiring that a subset of layers (such as the second-to-last layer) be trained while the other layers remain fixed. Proving convergence when all layers are optimized simultaneously remains an open challenge. Similarly, Eshtehardian et al. highlighted that the joint optimization of all layers in specialized architectures remains a significant theoretical hurdle.
A Ubiquitous Gap Across Paradigms
This theoretical bottleneck isn't isolated to standard feed-forward networks; it spans almost every modern architecture and optimization paradigm:
- Generative Models: Wipf proved that the act of marginalization selectively smooths the loss landscape and eliminates bad local minima in Variational Autoencoders (VAEs), but the proof is restricted to shallow, single-layer decoders. For GANs, Balaji et al. showed that while overparameterization guarantees convergence to global saddle points in shallow generators, extending this to deep multi-layer networks is blocked by the non-linear complexity of hierarchical mappings.
- Graph and Routing Networks: In Graph Neural Networks (GNNs), Liu demonstrated that formalizing optimization dynamics for multi-layer architectures is required to account for the compounding effects of depth on convergence. For Mixture-of-Experts, Chowdhury et al. proved patch-level routing efficiency only by limiting the underlying model to a shallow, two-layer CNN.
- Alternative Learning Rules: Biologically plausible alternatives to backpropagation, such as Feedback Alignment, enjoy rigorous convergence proofs only in two-layer settings; extending them to deep networks remains an open problem due to the lack of weight transport across multiple layers (Robertson et al.).
Pathways to Deep Proofs
How are researchers pushing past the two-layer boundary? Two primary strategies have emerged: mean-field feature tracking and asymptotic depth analysis.
Instead of tracking individual weights, the mean-field framework tracks the continuous distribution of features across layers. Fang et al. used this approach to prove global convergence for deep Residual Networks (ResNets). Crucially, the authors noted that skip connections are vital to the math: without them, standard feed-forward networks suffer from feature degeneracy in deep layers, causing the proof (and the optimization) to fail.
Another angle is analyzing the asymptotic limits of depth. Súkeník et al. proved that "Neural Collapse"—a highly structured state where a network's internal representations become perfectly symmetrical—is the mathematically optimal outcome for deep ResNets and Transformers, showing that this organization tightens as depth approaches infinity. However, they also emphasized that the specific convergence bounds for models with a moderate number of layers remain loosely defined.
Ultimately, bridging the convergence theory gap requires moving away from the "lazy" kernel regimes that made shallow networks easy to analyze, and developing new mathematical tools capable of tracking the rich, coupled geometric transformations that occur across deep neural hierarchies.