In the theoretical study of deep learning, there is a persistent "reality gap." To prove that a neural network will converge to a global minimum or achieve low regret, mathematicians often rely on the Neural Tangent Kernel (NTK) regime. This framework assumes that networks are "infinitely wide," allowing them to behave like simple linear models during training.
However, practitioners do not build infinitely wide networks. They build compact, finite-width architectures for mobile phones, embedded systems, and real-time recommendation engines. While theory often suggests we need a number of neurons scaling as $O(n^4)$ or even exponentially with depth to guarantee success, empirical evidence shows that much smaller networks—sometimes even underparameterized ones—perform remarkably well.
A growing body of research is dedicated to narrowing this discrepancy, moving from "lazy" infinite-width proofs toward a more precise understanding of finite-width dynamics.
The Crutch of Infinite Width
The reason researchers like Quanquan Gu and Dongruo Zhou often invoke the NTK regime in papers like Batched Neural Bandits is mathematical tractability. In the infinite-width limit, the features learned by the network don't actually change much; the weights stay close to their initialization. This "lazy training" makes it easy to prove that gradient descent will find a global optimum.
But as Yu Heng Hung and Ping-Chun Hsieh note in their work on Neural Contextual Bandits via Reward-Biased Maximum Likelihood Estimation, this creates a fundamental disconnect. If the theory requires "astronomical" widths to guarantee convergence, it fails to explain why the narrower, bottlenecked architectures used in production actually work.
Reconciling Scaling Laws
The gap is most visible in the "scaling laws" required for convergence proofs. Early breakthroughs by Simon Shaolei Du in Gradient Descent Finds Global Minima of Deep Neural Networks showed that while standard networks might require exponential width, Residual Networks (ResNets) only require width to grow polynomially with depth.
While polynomial scaling is a massive improvement, the resulting parameter counts still dwarf what is computationally feasible. Recent work has focused on bringing these requirements down to earth:
- Data Geometry: Léo Dana and Francis Bach have shown that if data is "weakly interacting" (as is common in high dimensions), shallow ReLU networks can converge with only $O(\log n)$ neurons for $n$ data points.
- Initialization Tricks: In Bounding the Width of Neural Networks via Coupled Initialization, researchers found that pairing neurons with opposite signs at the start can reduce theoretical width requirements from $O(n^4)$ to $O(n^2)$, inching closer to the linear scaling observed in practice.
- Topology: Chao Chen suggests that the number of neurons needed is actually tied to the manifold topology of the data—specifically its Betti numbers—rather than just the raw number of samples.
From Lazy Training to Feature Learning
The most exciting frontier in this research direction is moving beyond the "lazy" regime where weights barely move. In reality, neural networks are powerful because they learn features.
Blake Bordelon and Cengiz Pehlevan argue in Dynamics of Finite Width Kernel and Prediction Fluctuations in Mean Field Neural Networks that this "rich" feature learning actually acts as a stabilizer. Unlike lazy models, which can be sensitive to initialization noise, finite-width networks that adapt their internal representations can reduce prediction variance.
Similarly, Benjamin Bowman and Guido Montufar introduced the concept of "Damped Deviations." They proved that even in underparameterized networks, a "spectral bias" exists: the network naturally prioritizes learning the most important components of a function first, effectively suppressing the errors that come from having "too few" parameters.
Why It Matters for the Future
Closing the overparameterization gap isn't just a mathematical exercise; it has direct implications for how we deploy AI.
In Towards Establishing Guaranteed Error for Learned Database Operations, Sepanta Zeighami points out that database engineers cannot replace traditional indexes with neural networks unless they have hard error guarantees. If our only guarantees require "infinite width," we cannot safely use neural networks in resource-constrained environments like databases or mobile hardware.
By refining these bounds—as seen in the work of Sudeep Salgia and Sattar Vakili on Provably and Practically Efficient Neural Contextual Bandits—the field is moving toward a future where "provably efficient" and "practically useful" are no longer two different things.