PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards moderate overparameterization: global convergence guarantees for training shallow neural networks

Samet Oymak, Mahdi Soltanolkotabi

arXiv:1902.04674v1cs.LGcs.ITmath.OCstat.ML

TL;DR

The paper asks how much and what kind of overparameterization is needed for first-order methods to globally fit arbitrary labels despite nonconvexity. It studies randomly initialized gradient methods for shallow networks and shows global convergence under moderate parameter scaling, while leaving generalization and worst-case data as boundaries of the results.

  • Problem

    The required overparameterization for gradient descent to reach global optima and perfectly interpolate labels remains unclear, especially beyond very wide theoretical regimes.

  • Method

    The paper analyzes randomly initialized gradient descent and stochastic gradient descent for one-hidden-layer networks with smooth activations, and develops analogous ReLU results.

  • Results

    The results establish global convergence and zero training error when the square of the model's parameter count exceeds the dataset size by a fixed numerical constant, with geometric convergence and related ReLU guarantees.

  • Takeaways & Limitations

    The theory narrows the gap between existing very-wide-network guarantees and the more moderate overparameterization observed in numerical experiments.

  • Takeaways & Limitations

    The work does not directly address generalization, and its randomly generated datasets may not represent worst-case datasets requiring substantially more overparameterization.

Abstract

from arXiv · show

Many modern neural network architectures are trained in an overparameterized regime where the parameters of the model exceed the size of the training dataset. Sufficiently overparameterized neural network architectures in principle have the capacity to fit any set of labels including random noise. However, given the highly nonconvex nature of the training landscape it is not clear what level and kind of overparameterization is required for first order methods to converge to a global optima that perfectly interpolate any labels. A number of recent theoretical works have shown that for very wide neural networks where the number of hidden units is polynomially large in the size of the training data gradient descent starting from a random initialization does indeed converge to a global optima. However, in practice much more moderate levels of overparameterization seems to be sufficient and in many cases overparameterized models seem to perfectly interpolate the training data as soon as the number of parameters exceed the size of the training data by a constant factor. Thus there is a huge gap between the existing theoretical literature and practical experiments. In this paper we take a step towards closing this gap. Focusing on shallow neural nets and smooth activations, we show that (stochastic) gradient descent when initialized at random converges at a geometric rate to a nearby global optima as soon as the square-root of the number of network parameters exceeds the size of the training data. Our results also benefit from a fast convergence rate and continue to hold for non-differentiable activations such as Rectified Linear Units (ReLUs).

1 Introduction

The paper studies when moderately overparameterized shallow neural networks can be trained to global optima, addressing a gap between practical behavior and existing theory. It formulates a one-hidden-layer model and establishes notation for its analysis.

  • Motivation: Overparameterized networks can fit arbitrary labels, but the required parameterization for gradient descent to reach global optima remains unclear.The challenge arises from the nonconvex training landscape and potentially many global minima.
  • Motivation: Existing convergence results largely require specialized settings or neural networks whose hidden widths are polynomially large in the dataset size.The paper contrasts these results with the more modest overparameterization used in practice.
  • Contributions: The paper develops convergence results for differentiable activations and analogous results for ReLU activations, using random-matrix and Hadamard-matrix spectral tools.Its stated goal is to narrow the gap between theoretical guarantees and practical overparameterized training.
  • Model: The paper analyzes one-hidden-layer networks with d inputs, k hidden units, and a single output, using weights W and v with activation function φ.The model maps x ∈ R^d to a scalar through the hidden layer and output weights.
  • Notation: The notation includes singular values, Khatri-Rao products, Hadamard powers, and vectorization of the hidden-layer weight matrix.For ReLU, the paper uses a generalized derivative φ′(z) = I{z≥0}.

2 Main results

The paper analyzes shallow, overparameterized neural networks trained by gradient-based methods and identifies conditions under which they reach global optima while remaining near random initialization. Its results cover smooth and ReLU activations, with guarantees extending to stochastic gradient descent.

  • Setup: The setup fixes the output weights and trains input-to-hidden weights with quadratic loss from a random initialization.The network has one hidden layer, k hidden units, d-dimensional inputs, and a scalar output.
  • Methods: Gradient descent and stochastic gradient descent are studied for smooth activations, while analogous guarantees are also established for ReLU activations.The paper organizes the results into smooth-activation GD, ReLU GD, and SGD analyses.
  • Overparameterization: kd ≳ n^2 is the typical smooth-activation requirement, meaning the square of the model parameter count exceeds the training-set size up to fixed numerical constants.This scaling is stated for generic data in the n ≳ d regime and is weaker than requiring an extremely large number of hidden units polynomial in n.
  • Gradient descent guarantees: When n ≲ d, perfect fitting requires only k ≳ n hidden units, and the convergence rate is a fixed numerical constant independent of the dimensions.In this regime, the relevant conditioning quantity scales as √(d/n).
  • Gradient descent guarantees: Under this scaling, gradient descent converges geometrically to a global optimum with zero training error and perfectly interpolates arbitrary labels.The iterates remain within a neighborhood of radius on the order of √n around initialization, and the path length is also on the order of √n.
  • Stochastic gradient descent: SGD also converges to a global optimum near initialization, with its iterates staying in a local neighborhood with high probability.For generic data with n ≥ d, the iteration complexity is comparable to full gradient descent after accounting for the computational cost of n SGD iterations.

3 The need for overparameterization beyond width

The section contrasts fitting only the output layer with training input-to-hidden weights, then characterizes when random features yield perfect interpolation. For generic data, the main result requires roughly kd ≳ n^2 parameters and achieves zero training error under stated eigenvalue conditions.

  • Random-feature baseline: Fixing random input-to-hidden weights reduces training to a least-squares problem over output weights.The random-feature matrix is Φ = φ(XW^T), and the least-squares solution is globally optimal when the features have sufficient rank.
  • Random-feature baseline: Full row rank of Φ suffices for random-feature regression to perfectly interpolate the training data.The relevant condition is that the output feature matrix provides enough independent features for the labels.
  • Eigenvalue conditions: For generic or random data, σmin(X * X) often scales like a constant, so the neural-network eigenvalue can also remain constant.The paper defines the output feature covariance eigenvalue as the minimum eigenvalue of the corresponding covariance matrix.
  • Eigenvalue conditions: When the relevant eigenvalue condition holds, a width k ≳ n random-feature network achieves perfect interpolation with high probability.This result concerns fitting the last layer while keeping the input-to-hidden weights random.

4 Numerical experiments

Numerical experiments test whether shallow networks fit randomly generated data as hidden width and input dimension vary. The observed transition closely follows the parameter-count boundary n = kd, while the authors caution that worst-case datasets may require more overparameterization.

  • Experimental setup: The experiments vary hidden nodes k and input dimension d while fixing dataset size n, using random spherical inputs and random Gaussian labels.The study examines whether first-order methods can fit randomly generated data as parameter counts increase.
  • Experimental setup: The experiments use fixed learning rates, up to 15,000 iterations, and ten independent realizations per (k,d) pair.Success is based on a relative error or loss threshold of 2.5 × 10^-3.
  • Phase transitions: For n = 100 and n = 200, success transitions from failure to success as k and d increase.The transition is more visible at higher dimensions, which the paper relates to concentration of measure.
  • Phase transitions: The success region is tightly surrounded by the curve n = kd, indicating that slight overparameterization can suffice for fitting random data.The larger-dataset experiment matches the curve even more closely.
  • Scope: Worst-case datasets may exhibit different phase transitions, especially when identical inputs receive different outputs.The authors therefore limit the empirical conclusion to randomly generated datasets.

5 Prior art

Prior work established convergence for specialized or extremely wide overparameterized networks, while this paper targets dependence on total parameter count and shallow architectures. The section also distinguishes finite-size convergence analysis from generalization and asymptotic mean-field work.

  • Existing convergence theory: Earlier convergence results often require quadratic activations or widths polynomially large in the dataset size.The paper contrasts these specialized or very wide settings with more moderate practical overparameterization.
  • Comparison with prior theory: For smooth activations, the paper requires kd ≳ n^2, compared with k ≳ n^4 in one prior result.The authors describe this as sharper in hidden-unit requirements by a factor on the order of n^2d^0.5.
  • Scope: The paper studies one-hidden-layer networks, whereas some cited prior results apply to deep architectures.The authors state that their results and proof strategy may extend to deeper networks as future work.
  • Related perspectives: Mean-field work characterizes parameter distributions asymptotically, while this paper addresses finite-size networks.These are presented as distinct analytical perspectives on overparameterized optimization.
  • Scope: Generalization remains outside this paper’s direct scope, despite possible links between its optimization analysis and generalization questions.The relationship between optimization and generalization is identified as future research.

6 Proofs

The proofs establish global-convergence results by controlling the Jacobian spectrum near random initialization, then applying these controls to smooth and ReLU activations.

  • Jacobian structure: The network Jacobian with respect to input-to-hidden weights is assembled from one-hidden-unit Jacobians involving activation derivatives and the data matrix.The proof also expresses its Gram matrix through a Hadamard product involving activation derivatives and XXT.
  • Initialization and covariance: The neural network covariance matrix is defined from Gaussian random weights and is linked to the expected Jacobian Gram matrix at initialization.This covariance determines the minimum neural network eigenvalue used in the convergence theorems.
  • Smooth and ReLU cases: For smooth activations, bounded first and second derivatives support the meta-theorem, while ReLU receives a separate theorem under the corresponding nonsmooth setting.The main theorems follow by lower bounding the neural network eigenvalue through a reduction to quadratic activations.
  • Optimization setup: Gradient descent starts from i.i.d. Gaussian weights and updates only the input-to-hidden weights using a prescribed step size.The same meta-theorem framework is stated for smooth activations and separately for ReLU activations.
  • Spectral control: The Jacobian analysis bounds its spectral norm and initialization minimum eigenvalue, providing the conditioning controls needed for convergence.The initialization result holds for random Gaussian weights with probability at least 1 − 1/n.
  • Jacobian perturbation: Smooth activations yield a Lipschitz Jacobian, whereas ReLU perturbation is controlled by bounding changes in activation patterns around initialization.The ReLU argument reduces Jacobian changes to sign flips and controls how many signs can change within a neighborhood.

A.1 Proof for the spectral norm of the Jacobian (Proof of Lemma 6.6)

This proof bounds the Jacobian’s spectral norm by rewriting its Gram matrix as a Hadamard product and applying positive-semidefinite matrix inequalities.

  • Gram-matrix representation: The Jacobian Gram matrix is written as a Hadamard product of an activation-derivative factor and XXT.This representation isolates the data geometry from the activation and output-weight terms.
  • PSD inequality: Schur’s theorem for positive-semidefinite matrices supplies the key eigenvalue inequality for the Hadamard-product bound.The proof invokes the theorem after identifying the relevant factors in the Jacobian Gram matrix.
  • Concentration: The proof applies matrix Chernoff to independent single-hidden-unit Jacobian Gram matrices, with an upper bound determined by the activation derivative bound and output weights.This concentration step relates the random Jacobian spectrum to its expectation.

B Reduction to quadratic activations (Proof of Lemma 6.4)

The proof reduces the neural-network covariance for a general activation to the covariance associated with a quadratic activation, using Gaussian identities.

  • Gaussian identities: The proof begins from identities for Gaussian expectations involving the activation derivative and the data vectors.Unit-norm inputs simplify the resulting covariance expressions.
  • Reduction: The resulting covariance and eigenvalue bounds complete the reduction to quadratic activations.The argument concludes the lemma after identifying the transformed covariance expression.

C.1 Proof for Lipschitzness of the Jacobian with smooth activations (Proof of Lemma 6.8)

The smooth and ReLU perturbation proofs control how the Jacobian changes away from random initialization, using derivative bounds for smooth activations and activation-pattern stability for ReLU.

  • Smooth activations: The smooth proof expresses the Jacobian difference through the difference of activation derivatives multiplied by the data matrix.A mean-value argument then controls this difference using the bounded second derivative.
  • Smooth activations: The resulting smooth Jacobian bound is Lipschitz in the Frobenius distance between weight matrices.The bound scales with the second-derivative bound, the maximum output-weight magnitude, and the data-matrix norm.
  • ReLU activations: For ReLU, controlling the Jacobian reduces to controlling changes in the derivative activation pattern within a neighborhood of initialization.Because the ReLU derivative is a step function, the proof counts sign flips between WXT and W0XT.
  • ReLU activations: The ReLU argument shows that many sign changes would require a large displacement from initialization, contradicting the assumed neighborhood radius.This converts bounds on small Gaussian coordinates into a perturbation bound for the Jacobian.
  • ReLU activations: Gaussian concentration and a union bound extend the sign-control argument simultaneously across all input data points.The resulting event establishes the required perturbation control around the random initialization.

D Proof of Corollary 6.11

The corollary follows by rewriting (6.13), applying Jacobian Lipschitzness, and using the triangle inequality to establish (6.7). Theorem 6.10 therefore applies with its conclusions intact.

  • Jacobian Lipschitzness and the triangle inequality establish condition (6.7) under the corollary’s assumptions.
  • Once (6.7) holds, all assumptions of Theorem 6.10 continue to hold.
  • The conclusions of Theorem 6.10 consequently remain valid for the corollary.

E Proof of Corollary 2.2

The proof applies Theorem 2.1 after calculating activation, data-matrix, and Jacobian constants. These calculations provide the conditions needed for the theorem’s result.

  • The proof reduces the result to Theorem 2.1 by calculating the constants appearing in that theorem.
  • For the activation, the constants satisfy B = M = 1 and µφ ≈0.207.
  • The required width condition is kd ≥˜c(1 + δ)κ(X)n for a fixed numerical constant ˜c.
  • The data-dependent quantity κ(X) is controlled using concentration results for random matrices with independent and identically distributed rows.
  • The maximum Euclidean norm of a neural-network Jacobian row is bounded by B ∥v∥ℓ2.

G.1 Completing the proof of Theorem 6.13

The proof establishes convergence by controlling Jacobian perturbations and keeping successive iterates within a radius-R neighborhood of initialization. It then derives the residual contraction rate.

  • The iterative argument first shows that successive iterates remain inside the region ∥θ −θ0∥≤R.
  • The update analysis combines Lemmas G.3 and G.4 to control both residual changes and the iterates’ distance from initialization.
  • The convergence rate is geometric, with the residual norm bounded by (1 −ηα2)∥rτ∥ℓ2.
  • The covariance analysis uses Hermite expansions and higher-order Khatri-Rao products to lower-bound neural-network and output-feature covariance eigenvalues.

I Proofs for datasets with δ-separation (Proof of Theorem 2.5)

For δ-separated datasets, the proof establishes covariance control for Gaussian indicator mappings and ReLU Jacobians, then applies the meta-theorem. The resulting width requirement is polynomial in n and depends on δ.

  • Theorem I.1 bounds the covariance of the indicator vector I(Xw) for unit-norm, δ-separated inputs.
  • The proof uses Gaussian orthogonal decomposition and independence to establish the indicator covariance bound.
  • The event analysis yields P(∣f(g)∣≥∥a∥ℓ∞/2) ≥δ/24n.
  • Corollary I.2 transfers the separation-based covariance control to the ReLU Jacobian.
  • λ(X) ≥ δ 100n2, and substituting this value gives k ≥O((1 + ν)2n9∥X∥6/δ4) with the associated learning rate.
Loading 1902.04674v1…