When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work

Jiawei Zhang, Yushun Zhang, Mingyi Hong, Ruoyu Sun, Zhi-Quan Luo

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.

Optimization landscapes of wide vs. narrow networks.

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:

  1. Expressivity: Can a narrow network even represent the target function (memorize $n$ samples)?
  2. 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:

  1. 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.
  2. 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.
  3. 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.
The proposed constrained training regime for narrow networks.

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.

  1. 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

Abstract

Modern neural networks are often quite wide, causing large memory and computation costs. It is thus of great interest to train a narrower network. However, training narrow neural nets remains a challenging task. We ask two theoretical questions: Can narrow networks have as strong expressivity as wide ones? If so, does the loss function exhibit a benign optimization landscape? In this work, we provide partially affirmative answers to both questions for 1-hidden-layer networks with fewer than $n$ (sample size) neurons when the activation is smooth. First, we prove that as long as the width $m \geq 2n/d$ (where $d$ is the input dimension), its expressivity is strong, i.e., there exists at least one global minimizer with zero training loss. Second, we identify a nice local region with no local-min or saddle points. Nevertheless, it is not clear whether gradient descent can stay in this nice region. Third, we consider a constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point is a nearly global minimizer. It is expected that projected gradient methods converge to KKT points under mild technical conditions, but we leave the rigorous convergence analysis to future work. Thorough numerical results show that projected gradient methods on this constrained formulation significantly outperform SGD for training narrow neural nets.
BibTeX
@inproceedings{zhang2021when,
  author = {Jiawei Zhang and Yushun Zhang and Mingyi Hong and Ruoyu Sun and Zhi-Quan Luo},
  title = {{When Expressivity Meets Trainability: Fewer than $n$ Neurons Can Work}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=ZBYphQE_hgp},
}
Figure