The NeurIPS 2021 paper, "When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work," challenges the conventional wisdom that neural networks must be massive to be trainable. The authors provide a theoretical and algorithmic framework showing that narrow networks—specifically those with fewer neurons than training samples—can achieve zero training loss and high performance if initialized and constrained correctly.
The Challenge of Narrow Networks
In modern deep learning, practitioners often rely on "over-parameterization." We make networks incredibly wide because theory suggests that wider networks have "benign" optimization landscapes—meaning gradient descent is less likely to get stuck in bad local minima. However, these wide networks are computationally expensive and memory-intensive, making them poor fits for embedded systems or "green computing."
The challenge is that when you shrink a network (making it "narrow"), the optimization landscape becomes "non-benign." It fills up with saddle points and poor local minima.
As illustrated above, wide networks feature a large "nice" region where the Jacobian matrix is full-rank ($JJ^T \succ 0$), allowing the optimization path ($w^0 \to w^*$) to easily find a solution. In contrast, narrow networks have a much smaller healthy region, and standard unconstrained training often escapes it, leading to optimization failures.
The authors tackle two core questions to solve this:
- Expressivity: Can a narrow network even represent the target function (memorize $n$ samples)?
- Trainability: If a solution exists, can a local search algorithm actually find it?
Methods: Fixing the Landscape
The authors focus on 1-hidden-layer networks with smooth activation functions (like Sigmoid or Tanh). Their approach relies on four key pillars:
- Mirrored LeCun’s Initialization: Standard initialization leads to a non-zero starting output. The authors propose initializing neurons in pairs with opposite signs so the initial output of the network is exactly zero. This "zero-output" starting point is mathematically crucial for applying the Inverse Function Theorem.
- The $2n/d$ Width Bound: They prove that if the width $m \ge 2n/d$ (where $n$ is sample size and $d$ is input dimension), a zero-loss global minimizer exists with probability 1. This is a much tighter bound than the typical $m \ge n$ requirement found in older literature.
- Constrained Optimization (PGD): Instead of unconstrained SGD, they propose a constrained formulation. They restrict the hidden weights to stay within a "nice" local region around the initialization where the Jacobian is full-rank.
By using Projected Gradient Descent (PGD), they ensure the iterates stay in this healthy region, effectively performing "landscape surgery" to prevent the optimizer from wandering into bad local minima.
- Pairwise Structure: They reformulate the network output to maintain a mirrored structure during training, which helps ensure that every KKT point (stationary point of the constrained problem) is a nearly global minimizer.
Key Insights and Results
- The Power of Movement: A major insight is that while a fixed narrow network might lack the "rank" to fit data, allowing the hidden weights to move even a small amount ($w \in B_\epsilon(w^0)$) provides enough "effective expressivity" to fit any label.
- The Jacobian is Key: Trainability is intrinsically tied to the Jacobian matrix being full-rank. In narrow nets, the Jacobian often becomes singular (rank-deficient). The proposed constraints specifically keep the Jacobian "healthy" throughout training.
- Theoretical Efficiency: Proving that $2n/d$ neurons are sufficient for zero training loss significantly lowers the theoretical floor for network width compared to previous $n$-neuron requirements.
- Superiority over SGD: In experiments on narrow ResNet-18 architectures (shrinking channels from 512 down to 64), the proposed training regime significantly outperformed standard SGD. On R-ImageNet, the authors' method maintained high test accuracy even as the network became extremely narrow, whereas regular training regimes collapsed.
Limitations and Future Work
While groundbreaking, the paper leaves room for future exploration:
- Architecture Depth: The primary theoretical results are for 1-hidden-layer networks. A rigorous extension to multi-layer architectures is left for future work.
- Activation Functions: The theory requires smooth, analytic activations. It does not currently cover ReLU, which is non-smooth at zero, though many modern smooth approximations (like GeLU or Swish) would likely fit the framework.
- Convergence Rate: While they prove that the points the algorithm reaches are good (KKT points), they do not provide a formal proof of the speed of convergence for PGD in this specific setting.
Summary updated