Deep learning features a profound foundational paradox. On one hand, engineers routinely deploy compact, finite-width neural networks that learn rich representations and converge reliably. On the other hand, mathematical proofs guaranteeing this success often require networks to be astronomically wide—sometimes infinitely wide, or scaling as a high-degree polynomial of the dataset size or time horizon.
This discrepancy is known as the theoretical-practical width gap. To understand why deep learning works in the real world, we must understand why mathematical theory relies on extreme overparameterization, where these bounds break down, and how researchers are working to bridge the divide.
The Mathematical Crutch of Infinite Width
To appreciate why the width gap exists, we have to look at the mathematical difficulty of analyzing a standard neural network. A deep network is a highly non-linear, non-convex system. As gradient descent updates the weights, the internal features of the network shift in a chaotic, moving-target dynamic that is notoriously difficult to track.
To make the mathematics tractable, theorists frequently rely on two idealized frameworks that assume infinite network width:
- The Neural Tangent Kernel (NTK) Regime: When a network's layers approach infinite width, the network's outputs can be approximated by a linear system. In this regime, the weights change infinitesimally during training, meaning the network behaves like a fixed kernel method.
- The Mean-Field Regime: Instead of tracking individual weights, this framework models the weights as a continuous probability distribution, turning a chaotic discrete optimization problem into a smooth, convex flow.
By assuming infinite or extreme width, researchers can prove global convergence guarantees (Gradient Descent Finds Global Minima of Deep Neural Networks; Width Provably Matters in Optimization for Deep Linear Neural Networks) and establish near-optimal regret bounds for online decision-making algorithms like contextual bandits (Neural Contextual Bandits with UCB-based Exploration; Neural Thompson Sampling).
Where the Bounds Break Down
While infinite-width assumptions make proofs possible, the resulting bounds are often practically unfeasible. In many cases, the mathematical requirements for network width scale so aggressively that they describe architectures orders of magnitude larger than anything used in production.
Absurd Polynomial Scaling
In standard deep ReLU networks, theoretical bounds for guaranteed convergence and low generalization error often require a network width that scales polynomially with a very high degree relative to the target error or sample size (Generalization Error Bounds of Gradient Descent for Learning Over-Parameterized Deep ReLU Networks). For optimization methods like Natural Gradient Descent, proofs often require the number of neurons to scale polynomially with the number of training samples (Fast Convergence of Natural Gradient Descent for Over-Parameterized Neural Networks), creating a massive discrepancy with practical architectures.
The "Over-Overparameterization" of Min-Max Games
The gap becomes even more severe when moving beyond simple minimization tasks. In neural min-max games—such as those used in Generative Adversarial Networks (GANs) and adversarial training—Deep Patel demonstrates that guaranteeing global convergence requires a cubic width scaling ($\Omega(n^3)$) relative to the sample size. This pessimistic theoretical requirement contrasts sharply with the empirical success of much narrower networks in adversarial settings.
Sequential and Active Learning Bottlenecks
In Recurrent Neural Networks (RNNs), theoretical convergence proofs often necessitate hidden layer widths that scale polynomially with the sequence length (Learning and Generalization in RNNs). Similarly, in neural active learning (Improved Algorithms for Neural Active Learning) and robust contextual bandits (Robust Neural Contextual Bandit against Adversarial Corruptions), uncertainty estimation formulas rely heavily on the overparameterized NTK regime, limiting the applicability of these theories to the compact, resource-constrained architectures used in real-world deployments.
What the Theory Misses: Feature Learning
Why do compact networks perform so well when theory says they shouldn't? The core reason is that infinite-width models exhibit "lazy training." Because the network is infinitely wide, it can fit any dataset without its internal representations changing.
However, practical networks are powerful precisely because they do change their representations. They perform feature learning.
Blake Bordelon et al. demonstrate that this "rich" feature learning acts as a stabilizer, reducing the prediction variance that plagues simpler, lazy models when sample sizes are comparable to network width. While mean-field analyses of architectures like Elman-type RNNs (Global optimality of Elman-type RNNs in the mean-field regime) attempt to capture this feature-learning behavior, they still struggle to quantify the exact, finite number of neurons required to avoid local minima in practice.
Bridging the Gap
To make deep learning theory useful for practical engineering, researchers are actively developing new frameworks that relax or bypass the infinite-width assumption entirely.
[Underparameterized] ---------> [Mildly Parameterized] ---------> [Infinitely Wide (NTK)]
Spectral Bias Saddle Point Escape Lazy Training
Learns dominant components Few extra neurons alter Mathematically tractable
via Damped Deviations the loss landscape but practically loose
Mild Overparameterization
Instead of demanding infinite width, Gilad Yehudai proves that adding just a small number of additional neurons—"mild" overparameterization—fundamentally alters the optimization landscape. While it destroys local convexity around global minima, it simultaneously turns troublesome non-global minima into escapable saddle points, allowing gradient descent to succeed without requiring massive model capacity.
Underparameterized Dynamics and Spectral Bias
Flipping the problem entirely, some researchers study what happens when networks are intentionally small. Benjamin Bowman et al. introduce the concept of "Damped Deviations," proving that underparameterized networks still exhibit a structured "spectral bias." They naturally learn the most important components of a target function first because mathematical errors in the network's evolution are suppressed in those specific directions, explaining why small networks converge effectively without overparameterization.
Realistic Architectural Constraints
Other domains are successfully establishing bounds for constant-width networks:
- Convolutional Networks: Kenta Oono et al. show that deep, constant-width ResNets can achieve minimax optimal error rates without requiring channel widths to grow with the sample size.
- Contextual Bandits: The authors of Provably and Practically Efficient Neural Contextual Bandits introduce smooth activation functions to move beyond infinite-width NTK assumptions, providing sublinear regret guarantees for finite-sized networks.
By moving away from the mathematical convenience of infinity and focusing on the geometric properties of finite architectures, the machine learning community is steadily closing the gap between what can be proven on paper and what works in production.