Asymptotic convexity of wide and shallow neural networks

Vivek Borkar, Parthe PanditarXiv 2025 · DOI · arXiv

Abstract

The reliable convergence of massive, non-convex neural networks to high-quality solutions remains a central mystery in deep learning. This paper provides a theoretical foundation for this phenomenon by demonstrating that the optimization landscape of shallow neural networks becomes asymptotically convex as their width increases. By leveraging the Shapley-Folkman Lemma and the theory of Minkowski sums, the authors show that the aggregation of many non-convex neuron landscapes "smooths out" into a well-behaved convex problem. This "convexification effect" explains why wide networks are particularly amenable to simple gradient-based optimization.

Introduction

In classical optimization, non-convexity is typically viewed as a significant hurdle, as gradient descent can easily become trapped in sub-optimal local minima. Neural networks are inherently non-convex, yet empirical evidence consistently shows that "wide" networks—those with a large number of neurons in a hidden layer—find global or near-global minima with remarkable ease. This paper seeks to bridge the gap between this empirical success and the lack of theoretical guarantees by proving that width acts as a fundamental regularizer for the optimization landscape itself.

Theoretical Framework and Methods

The authors employ a rigorous mathematical approach rooted in real analysis and set theory to analyze the geometry of the loss surface. The methodology follows several key steps:

  1. Network Modeling: A shallow network is defined as a weighted sum of component "sub-networks" or neurons. The output is governed by a specific kernel weighting scheme that determines how individual neuron contributions are aggregated.
  2. Minkowski Sums of Epigraphs: The core of the proof relies on the Shapley-Folkman Lemma. The authors consider the "epigraphs" of the loss functions—the sets of points lying above the loss curves. They demonstrate that the Minkowski sum (the set-based addition) of many non-convex epigraphs becomes increasingly convex as the number of sets in the sum grows.
  3. Convex Minorants: The research shows that the input-output map of a wide network approximates the convex minorant, which is the largest convex function that remains below the original non-convex function.
  4. Asymptotic Analysis: By taking the limit as the network width ($N$) approaches infinity, the authors prove that the global minima of the wide network align with the global minima of this convexified landscape.

The Convexification Effect

The most striking insight of this work is that non-convexity is essentially a "small-scale" problem. When a model aggregates many non-convex components (neurons), their individual "bumps" and "dips" average out. The Minkowski sum of their epigraphs converges to the convex hull of the original sets.

This formalizes the intuition that adding neurons does more than just increase representational capacity; it fundamentally alters the geometry of the loss surface, making it flatter and more "convex-like." Consequently, in a sufficiently wide network, the distinction between local and global minima vanishes, justifying the use of simple algorithms like Stochastic Gradient Descent (SGD) in high-dimensional spaces.

Key Results

The paper presents several critical findings regarding the behavior of wide networks:

  • Theorem 4.5: This centerpiece theorem states that the parameters minimizing the wide network's loss function converge to the global minimum of the convex minorant of the underlying map as the width and kernel parameters approach their limits.
  • Convergence of SGD: In the context of the Least Mean Square (LMS) criterion, the authors demonstrate that "asymptotic" SGD (where $N \to \infty$) converges in probability to the set of global minima. This provides a theoretical justification for why SGD is so effective even when individual neurons exhibit complex, sign-indefinite behaviors.
  • Rate of Convergence: Drawing on existing literature regarding Minkowski sums, the authors note that the convergence to the convex hull occurs at a rate of $O(1/n)$. This suggests how quickly the benefits of width begin to manifest in finite architectures.

Discussion and Limitations

While this work provides a powerful explanation for the success of wide networks, it has specific boundaries:

  • Architectural Scope: The proofs are primarily developed for shallow (one hidden layer) networks. While the principles of Minkowski sums may eventually be extended to deep networks, the current mathematical machinery is most directly applicable to the wide-and-shallow case.
  • Asymptotic vs. Finite Width: The results are asymptotic ($N \to \infty$). While this explains the general trend, it does not yet provide a specific "threshold width" required to achieve a certain level of convexity for a given problem.
  • Kernel Dependency: The results are sensitive to the choice of the weighting kernel for the final layer. Future research is needed to explore how different architectural components, such as attention mechanisms or varied activation functions, influence the convexification process.

In conclusion, this paper offers a significant step forward in understanding the "unreasonable effectiveness" of wide neural networks, showing that the very act of scaling a network can transform a difficult optimization problem into a manageable one.

Summary updated

BibTeX
@misc{borkar2025asymptotic,
  author = {Vivek Borkar and Parthe Pandit},
  title = {{Asymptotic convexity of wide and shallow neural networks}},
  year = {2025},
  eprint = {2507.01044},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.01044},
}
Figure