Nearly Minimal Over-Parametrization of Shallow Neural Networks

Armin Eftekhari, ChaeHwan Song, Volkan Cevher

TL;DR

This paper shows that shallow neural networks can perfectly fit training data with linear over-parametrization, a significant improvement over the quadratic requirement in prior theory. This is achieved using a variant of gradient descent that avoids the "lazy regime," potentially leading to better generalization.

What Problem Does This Paper Address?

Training neural networks, especially deep ones, is notoriously challenging due to nonconvex optimization landscapes with local minima and saddle points. While over-parametrization (having more parameters than training data points) is empirically known to help networks fit data well, theoretical guarantees often require a substantial amount of over-parametrization. For shallow networks, existing theory typically demands quadratic over-parametrization (number of parameters $p$ scales with $m^2$, where $m$ is the number of samples) to guarantee zero training error. This paper aims to bridge this gap by showing that much less over-parametrization is needed, specifically linear over-parametrization ($p \propto m$), and that this can be achieved without falling into the "lazy training" regime, which can hurt generalization.

Methods

The authors develop a unified framework for analyzing over-parametrization in learning problems, which they then apply to shallow neural networks. The core idea is to analyze the behavior of gradient descent (and its stochastic variant) on a composite function $h = f \circ \Phi$, where $f$ is a loss function and $\Phi$ is the network's forward pass.

Key techniques include:

  • Polyak-Lojasiewicz (PL) condition: A relaxation of strong convexity that guarantees convergence to a global minimum for certain functions.
  • Near-isometry of the Jacobian: Analyzing the properties of the Jacobian of the network's mapping ($\Phi$) to ensure that the optimization landscape remains well-behaved near the initialization.
  • Gradient Flow Analysis: Studying the continuous-time limit of gradient descent to understand convergence properties.
  • Weighted Gradient Descent: A specific algorithm for shallow networks that leverages the structure of the problem to achieve efficient training.
  • Stochastic Gradient Descent (SGD): Extending the analysis to the more practical setting of SGD.

A crucial aspect is demonstrating that their approach avoids the "lazy regime," where the network's behavior is dominated by its initial random weights, leading to poor generalization.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees and uses synthetic data assumptions (e.g., full row rank data matrix $Z$).

Key Insights and Ideas

  • Linear Over-parametrization is Sufficient: The most significant finding is that for shallow networks, linear over-parametrization ($p \propto m$) is enough to guarantee perfect fitting of training data, a substantial improvement over prior quadratic requirements.
  • Avoiding the "Lazy Regime": The proposed gradient descent variants are shown to avoid the "lazy training" phenomenon, which is a known pitfall of some over-parametrization theories and can lead to poor generalization. This is achieved by ensuring the optimization trajectory stays within a controlled neighborhood of the initialization.
  • Unified Framework: The paper introduces a general framework for analyzing over-parametrization that is applicable beyond shallow networks, suggesting broader implications for understanding deep learning.
  • Weighted GD for Shallow Networks: A specific algorithm for shallow networks is proposed and analyzed, which effectively trains an auxiliary network and then transfers weights, offering a practical path to achieving the theoretical results.

Key Results

  • Theorem 6 (Gradient Descent): Guarantees that gradient descent converges to a global minimizer with zero training error for shallow networks, provided linear over-parametrization and certain conditions on the activation function and data are met.
  • Theorem 7 (Stochastic Gradient Descent): Extends the result to SGD, showing almost sure convergence to a global minimizer with zero training error, also under linear over-parametrization.
  • Theorem 8 (Weighted GD for Shallow Networks): Demonstrates that a specific weighted gradient descent algorithm achieves global optimality for shallow networks with linear over-parametrization, with only an exponentially small probability of failure. This result is shown to hold for a wide range of data distributions.

Limitations and Future Work

  • Shallow Networks Focus: While the framework is general, the main theoretical results are specifically for shallow networks. Extending these to deeper networks is an open question.
  • Generalization: The paper primarily focuses on achieving zero training error. While avoiding the lazy regime is a step towards better generalization, a formal theoretical guarantee on generalization performance is not provided.
  • Activation Function Assumptions: The analysis relies on specific assumptions about the activation function (e.g., twice-differentiable, bounded derivatives, decaying Hermite coefficients), which might exclude some common activations like ReLU directly (though smoothed approximations are discussed).
  • Data Assumptions: The theoretical results often rely on assumptions about the data matrix (e.g., full row rank).

Future work suggested by the authors includes:

  • Extending the theory to deeper networks.
  • Investigating the generalization error of networks trained with their methods.
  • Exploring whether linear over-parametrization is sufficient for deeper architectures.

Summary updated

Abstract

A recent line of work has shown that an overparametrized neural network can perfectly fit the training data, an otherwise often intractable nonconvex optimization problem. For (fully-connected) shallow networks, in the best case scenario, the existing theory requires quadratic over-parametrization as a function of the number of training samples. This paper establishes that linear overparametrization is sufficient to fit the training data, using a simple variant of the (stochastic) gradient descent. Crucially, unlike several related works, the training considered in this paper is not limited to the lazy regime in the sense cautioned against in [1, 2]. Beyond shallow networks, the framework developed in this work for over-parametrization is applicable to a variety of learning problems.
BibTeX
@misc{eftekhari2019nearly,
  author = {Armin Eftekhari and ChaeHwan Song and Volkan Cevher},
  title = {{Nearly Minimal Over-Parametrization of Shallow Neural Networks}},
  year = {2019},
  eprint = {1910.03948},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1910.03948},
}
Figure