When Expressivity Meets Trainability: Fewer than n Neurons Can Work

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

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.

Introduction

Modern deep learning relies heavily on over-parameterization. Massive networks are typically preferred because they are easier to optimize; their loss landscapes are smoother, facilitating the discovery of global minima via gradient descent. However, these wide networks impose significant computational and memory burdens, making them impractical for edge devices or environmentally conscious "green computing."

When training narrow networks—where the number of neurons $m$ is less than the number of samples $n$—practitioners face two primary hurdles:

  1. Expressivity: Whether a narrow network can theoretically represent the training data with zero loss.
  2. Trainability: Whether the optimization landscape allows standard methods like Stochastic Gradient Descent (SGD) to find these solutions without getting trapped in sub-optimal local minima or saddle points.

This research bridges this gap, demonstrating that narrow networks can be both expressive and trainable under specific conditions.

Methodology

The authors propose a novel training regime designed to exploit the local geometry of the loss landscape. This regime consists of three pillars:

  1. Mirrored LeCun’s Initialization: Standard initialization typically results in a non-zero starting output. To ensure the network begins at a neutral state, the authors initialize hidden weights in pairs $(w_j, -w_j)$ and outer weights as $(v_j, -v_j)$. This "mirrored" structure ensures the initial output is exactly zero for any input.
Mirrored initialization architecture ensuring zero initial output.
  1. The $2n/d$ Threshold: Mathematical proof shows that if the network width $m$ is at least $2n/d$ (where $n$ is sample size and $d$ is input dimension), a zero-loss solution is guaranteed to exist in the vicinity of the initialization point.
  2. Constrained Optimization via PGD: To prevent the optimizer from wandering into "bad" regions of the landscape, the authors employ Projected Gradient Descent (PGD). By defining a "nice" local region around the initialization and constraining weights within it, they prove that every Karush–Kuhn–Tucker (KKT) point is a nearly global minimizer.

Theoretical Insights: Landscape Surgery

A key insight of this work is that while narrow networks may have poor global landscapes, they possess "nice" local neighborhoods. In wide networks, the region where the Jacobian product $JJ^T$ is positive definite (the "nice" region) is large enough that standard gradient descent naturally finds a global minimizer. In narrow networks, this region is smaller, and unconstrained optimization often exits it, leading to poor convergence.

Comparison of optimization landscapes and training regimes for wide vs. narrow networks.

By starting at zero output via mirrored initialization, the network is effectively surrounded by all possible directions in the output space. This allows the application of the Inverse Function Theorem to prove that small weight perturbations can match any target label, provided the optimization is properly constrained.

Empirical Evaluation

The proposed theory and PGD algorithm were validated across diverse benchmarks including synthetic regression, MNIST, CIFAR-10/100, and Restricted ImageNet (R-ImageNet).

Key Results

  • Optimization Superiority: On synthetic data, the PGD regime consistently reached near-zero loss, whereas standard GD/SGD stalled at high-loss stationary points as width decreased.
  • ResNet Performance: In a narrow ResNet-18 (final block width reduced from 512 to 64) on R-ImageNet, the proposed regime maintained test accuracy (~86%) comparable to the full-width model, significantly outperforming standard SGD.
  • Memorization Success: The method achieved >99% training accuracy on CIFAR-10 with random labels using narrow networks, demonstrating that these models can memorize complex datasets when properly trained.

Conclusion and Future Work

This work demonstrates that the "ultra-wide" requirement for neural network trainability can be relaxed. However, several avenues for future research remain, including extending the proof to non-smooth activations like ReLU, providing a full "end-to-end" proof for multi-layer architectures, and formally addressing convergence rates and the generalization gap inherent in this constrained regime.

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