Tightening the Width Bounds for Global Convergence

This direction is merged into another direction: theoretical-practical width gap. Its last version stays readable and citable here.

Version 1 of 129 papers34 conceptsfrozen 2026-10-04

Deep learning theory has long grappled with a paradox: neural networks are non-convex and theoretically difficult to optimize, yet in practice, simple gradient descent consistently finds global minima. Early theoretical attempts to explain this relied on the "infinite-width" regime, such as the Neural Tangent Kernel (NTK), which required models to be astronomically large—often needing a number of neurons proportional to a high-degree polynomial of the dataset size ($n^6$ or more).

A growing body of research is now dismantling these "infinite-width" requirements. By refining our understanding of optimization landscapes and data-architecture alignment, researchers have shown that global convergence is achievable with much more "moderate" over-parameterization, often scaling linearly or quadratically with the number of samples.

The Shift Toward Moderate Over-parameterization

The core mission of this research direction is to bridge the gap between theoretical "infinite" models and the finite, practical architectures used in the real world. The primary breakthrough has been the reduction of the required hidden layer width ($m$) relative to the number of training samples ($n$).

While early proofs suggested $m$ must be massive to ensure a "benign" optimization landscape, Jason D. Lee and Simon S. Du demonstrated in On the Power of Over-parametrization in Neural Networks with Quadratic Activation that for certain shallow networks, a width proportional to $\sqrt{n}$ is sufficient. This suggests that the degree of over-parameterization needed to overcome non-convexity is significantly smaller than previously theorized.

Finding the Critical Thresholds

Different architectural choices and data properties further tighten these bounds:

Why It Works: Data-Architecture Alignment

The intuition behind these tighter bounds often lies in how the architecture interacts with the data distribution. When data points are "weakly interacting" (low correlation), the requirements drop precipitously. Francis Bach and colleagues found that in high-dimensional settings with distinct features, a shallow network needs only $\log(n)$ neurons to reach zero training loss (Convergence of Shallow ReLU Networks on Weakly Interacting Data).

Furthermore, structural modifications like Weight Normalization help by decomposing the learning process into "length" and "direction." As shown by Yonatan Dukler and Quanquan Gu, this decomposition significantly reduces the necessary over-parameterization compared to standard un-normalized networks (Optimization Theory for ReLU Neural Networks Trained with Normalization Layers).

Implications for Practical Training

These theoretical refinements provide a "green light" for practical deep learning. They explain why frameworks like FedAvg (Local SGD) can converge linearly to zero loss on large-scale models (FedAvg Converges to Zero Training Loss Linearly for Overparameterized Multi-Layer Neural Networks) and why Nesterov acceleration effectively speeds up non-convex problems like matrix factorization with minimal width (Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks). By moving away from the "infinite-width" crutch, this research direction provides a mathematical foundation that finally aligns with the actual scale of modern AI.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tightening_the_width_bounds_for_global_c_79c3e15f,
  title = {Tightening the Width Bounds for Global Convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-the-width-bounds-for-global-convergence/rdr_79c3e15f5a164aec84132413f5cee0a2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tightening_the_width_bounds_for_global_c_79c3e15f_v1,
  title = {Tightening the Width Bounds for Global Convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-the-width-bounds-for-global-convergence/rdr_79c3e15f5a164aec84132413f5cee0a2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}