Gradient Descent Finds Global Minima of Deep Neural Networks

Simon S. Du; Jason D. Lee; Haochuan Li; Liwei Wang; Xiyu Zhai

Source-linked AI summary

Gradient Descent Finds Global Minima of Deep Neural Networks

Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, Xiyu Zhai

arXiv:1811.03804v4Nov 9, 2018cs.LGcs.AIcs.CVmath.OCstat.ML

TL;DR

Deep neural-network training is nonconvex, yet randomly initialized gradient descent can achieve zero training loss. The paper proves this for over-parameterized deep networks by stabilizing architecture-induced Gram matrices, and extends the result to ResNets and convolutional ResNets.

Problem
The paper asks why randomly initialized gradient descent can reach zero training loss in nonconvex deep networks, even with arbitrary labels.
Method
The proof analyzes architecture-induced Gram matrices, using initialization and perturbation arguments to show their stability during gradient descent.
Results
Polynomial over-parameterization yields zero training loss with linear-rate convergence for deep fully connected networks and ResNets, with a similar result for convolutional ResNets.
Takeaways & Limitations
Gram-matrix stability implies that every gradient-descent step decreases the loss geometrically, establishing convergence to a global minimum in the analyzed settings.
Takeaways & Limitations
The analysis addresses training loss but not test loss, and its ResNet width requirement remains much larger than widths typical of realistic networks.

Abstract

from arXiv · show

Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.

1. Introduction

The paper addresses why randomly initialized gradient descent can fit arbitrary labels and why deeper networks are harder to train. It proves zero-training-loss convergence for fully connected networks, ResNets, and convolutional ResNets under over-parameterization.

Motivation: Over-parameterization is widely believed to enable neural networks to fit all training data, including arbitrary labels.Wide Residual Networks can have 100x more parameters than training examples.
Motivation: Residual connections help randomly initialized first-order methods train networks with an order of magnitude more layers, but their nonlinear theoretical advantages remain unclear.Prior theory established prevention of gradient vanishing for linear residual networks.
Contributions: For fully connected networks, randomly initialized gradient descent converges to zero training loss at a linear rate when width satisfies the stated exponential-in-depth over-parameterization condition.The precise polynomial and data-dependent parameters are deferred to later sections.
Contributions: For ResNets, polynomial width in n and H suffices for randomly initialized gradient descent to converge to zero training loss at a linear rate.The required dependence on depth improves exponentially relative to the fully connected result.
Contributions: The same technique yields zero training loss for convolutional ResNets when width is polynomial in n, the number of patches p, and depth H.The paper organizes this result as its final architectural extension.
Proof strategy: The analysis uses weight stability near initialization and structural properties of deep networks to control the Gram matrix and convergence dynamics.The proof develops techniques for both initialization and gradient-descent dynamics.

2. Related Works

Prior work studies nonconvex landscapes, shallow-network dynamics, and kernel-related behavior, but this paper analyzes deep networks, ResNets, and convolutional networks directly. Its comparisons with concurrent work are conditional on differing activations and data assumptions.

Optimization landscapes: Landscape-based analyses seek function classes where local minima are global and saddles have negative curvature, but such properties can fail even for three-layer linear networks.The paper therefore also considers dynamics of a specific algorithm on a specific architecture.
Convergence analyses: Several prior convergence results assume input distributions or planted labels, whereas this paper studies a different setting for deep over-parameterized networks.The supplied related-work passage contrasts those assumptions with the paper’s setup.
Extensions: Earlier weight-stability arguments covered two-layer networks, while this work extends the approach to deep, residual, and convolutional architectures.The paper also uses smooth activations to improve width dependence on sample size.
Relation to prior theory: The paper’s analysis generalizes infinite-width, finite-time gradient-flow results to finite width and gradient descent, while targeting convergence to a global minimizer.The cited prior work did not establish convergence of gradient flow to a global minimizer.
Concurrent work: Other concurrent studies differ in activation, loss, trained layers, or stochastic-gradient settings, preventing direct comparison in the supplied cases.The paper positions these works as complementary rather than uniformly superior or inferior.
Concurrent work: For ResNets, the paper reports polynomial width dependence that does not depend on desired accuracy ε, unlike the cited concurrent result.The authors caution that the two results are not directly comparable because their measures and data assumptions differ.

3. Preliminaries

The paper formulates quadratic empirical-risk minimization for several neural architectures trained by randomly initialized gradient descent. It assumes analytic, nonpolynomial, Lipschitz, and smooth activations and defines fully connected, residual, and convolutional models.

3.1. Notations: The notation defines Gaussian initialization, matrix and vector norms, inner products, smallest eigenvalues, and asymptotic O(·) and Ω(·) notation.The smallest eigenvalue notation is used later for Gram-matrix analysis.
3.2. Activation Function: The activation function σ is required to be Lipschitz and smooth; softplus is the guiding example and has both constants equal to 1.These conditions are used to show training-process stability.
3.2. Activation Function: The activation must also be analytic and nonpolynomial to guarantee positive definiteness of certain Gram matrices.Softplus satisfies this assumption.
3.3. Problem Setup: The optimization problem uses quadratic empirical risk, with labels, parameters θ, and neural-network prediction function f defining the training objective.The paper studies empirical risk minimization and trains all layers by gradient descent.
3.3. Problem Setup: The paper defines multilayer fully connected networks recursively using weight matrices, an output vector, and activation σ.Intermediate layers are assumed square for simplicity, though rectangular matrices are described as a straightforward generalization.
3.3. Problem Setup: The ResNet recursion uses a small residual scaling factor, which helps keep required per-layer width polynomial in depth H.The analyzed architecture places skip connections at every layer rather than every two layers.
3.3. Problem Setup: The convolutional ResNet divides feature maps into p patches before applying layer transformations, with patch size controlled by q.The analysis treats q as a constant because practical patch sizes are often small.

4. Technique Overview

The analysis tracks prediction errors through Gram-matrix dynamics and proves convergence by showing the relevant Gram matrix remains close to a fixed positive-definite matrix. It separately controls initialization and training perturbations, with ResNet connections stabilizing perturbation propagation.

Prediction dynamics: The prediction-error dynamics converge at a rate determined by the least eigenvalue of a fixed Gram matrix and the step size.The fixed matrix depends on the training inputs, architecture, and activation, but not on the network parameters.
Prediction dynamics: If the fixed Gram matrix is strictly positive definite, power-method analysis yields linear convergence of gradient descent.Strict positive definiteness is established when the training data are not degenerate.
Stability analysis: The proof establishes Gram-matrix stability in two stages: concentration near the fixed matrix at initialization and proximity to initialization throughout training.The second stage requires controlling changes in all layer weights and the activation output.
Stability analysis: Initialization analysis tracks recursively propagated perturbations through nonlinear layers using induction and Malliavin-calculus techniques.The recursive structure makes perturbation control substantially more involved for deep networks than for two-layer networks.
ResNet advantage: ResNet connections make perturbation propagation more stable and avoid the exponential-explosion problem appearing in the fully-connected analysis.The paper attributes the improved layer dependence to the residual architecture’s perturbation-propagation structure.
Training stability: During training, the analysis replaces individual weight-vector control with bounds on averaged Frobenius-norm changes across layers.This supplies the control needed to keep the Gram matrix close to its initialization value in multilayer networks.

5. Warm Up: Convergence Result of GD for Deep Fully-connected Neural Networks

The warm-up result analyzes gradient descent for deep fully connected networks through a recursively defined Gram matrix. With sufficiently large width, appropriate step size, and nondegenerate data, gradient descent reaches zero loss at a linear rate, although the width and step-size requirements depend exponentially on depth.

Convergence theorem: Sufficient width and an appropriately chosen constant positive step size make gradient descent converge to the global minimum at a linear rate.The theorem gives this result with probability at least 1 −δ over random initialization.
Gram matrix: A recursively defined Gram matrix K(H) governs the convergence rate and the required over-parameterization through its least eigenvalue.For nondegenerate training data, the paper shows λmin(K(H)) is strictly positive.
Convergence theorem: Zero training loss is achieved under the theorem’s large-width assumptions for normalized inputs and bounded labels.The stated assumptions include ∥x_i∥2 = 1 and |y_i| = O(1).
Width dependence: The width requirement depends polynomially on n and 1/λmin but exponentially on the number of layers H.The exponential depth dependence is attributed to instability in the fully connected architecture’s perturbation propagation.
Step-size dependence: The deep fully connected analysis also requires a step size that is exponentially small in the number of layers.The paper links this requirement to the same depth-dependent instability that enlarges the width requirement.

6. Convergence Result of GD for ResNet

The ResNet analysis defines a recursive Gram matrix whose least eigenvalue controls gradient-descent convergence. Skip connections stabilize this matrix and remove inverse-exponential depth dependence under polynomial over-parameterization.

The recursive Gram matrix K(H) is defined for ResNet, and its least eigenvalue determines the convergence rate.The analysis compares this matrix with the fully connected case and tracks its depth dependence.
The ResNet Gram matrix depends on coefficients introduced by the skip-connection block.This dependence distinguishes its recursive definition from that of a fully connected network.
The least eigenvalue λmin does not depend inversely exponentially on depth when the input training data is non-degenerate.This property supports a polynomial dependence on the number of layers.
Polynomially wide ResNets achieve zero training loss at a linear rate with randomly initialized gradient descent.Under the theorem’s assumptions, the result holds with probability at least 1 −δ over random initialization.
The required width and convergence rate are polynomial in the number of data points and layers.The over-parameterization requirement depends on the smallest eigenvalue of the Gram matrix.
Skip connections stabilize the architecture during initialization and training, explaining the absence of an exponential depth factor.The width requirement also includes terms controlling Gram-matrix stability, output normalization, and initialization perturbation.

7. Convergence Result of GD for Convolutional ResNet

The paper extends its Gram-matrix convergence analysis from ResNet to convolutional ResNet. With width polynomial in the data size, depth, and number of patches, randomly initialized gradient descent achieves zero training loss.

The convolutional ResNet analysis defines a recursive Gram matrix indexed by training examples and convolutional patches.Its entries include patch indices and layer-dependent quantities.
The convolutional ResNet result has the same qualitative convergence structure as the ResNet result.The analysis is described as similar, with the extra dependence on the number of patches appearing in width and step-size requirements.
The convolutional ResNet theorem assumes unit Frobenius-norm inputs, bounded labels, and a specified number of hidden nodes per layer.The result holds with probability at least 1 −δ over random initialization.
Polynomial width in the number of data points, patches, and layers is sufficient for zero training loss.The required step size is only polynomially small, with an additional polynomial dependence on the number of patches.

8. Conclusion

The paper shows gradient descent can reach zero training loss in deep over-parameterized networks, while identifying limitations concerning generalization, width, stochastic optimization, and convergence-rate analysis.

Conclusion: Gradient descent on deep over-parameterized networks achieves zero training loss because over-parameterization stabilizes the Gram matrix and yields geometric loss decrease.The analysis uses random initialization and perturbation analysis to maintain Gram-matrix stability throughout training.
Limitations: The paper does not address test loss, leaving generalization behavior as an important direction for future work.The authors specifically suggest algorithm-dependent analyses for understanding generalization.
Limitations: ResNet analysis requires layer width polynomial in the parameters but still very large relative to realistic networks.The authors identify covering commonly used networks as an open problem.
Limitations: The current analysis treats gradient descent rather than stochastic gradient descent, although the authors believe an extension could retain linear convergence.This is presented as a scope boundary rather than an established result.
Limitations: Using contributions from all Gram matrices might improve convergence rates, but would substantially complicate initialization and perturbation analyses.The paper leaves this refinement as a possible improvement.

A. Proof Sketch

The proof sketch tracks prediction dynamics through the Gram matrix and controls perturbations caused by gradient updates. A positive least eigenvalue dominates higher-order terms, producing linear loss convergence.

Induction: The proof assumes an induction hypothesis describing empirical-loss convergence and uses it to establish the next training step.The induction condition is the central invariant in the proof sketch.
Loss dynamics: If the first-order decrease exceeds the quadratic update term, the loss decreases.The proof compares the inner-product decrease with the squared prediction-change term.
Loss dynamics: The loss update separates into a first-order term that drives decrease and a second-order perturbation term that remains small.The first term is proportional to η, while the perturbation term is proportional to η^2.
Gram matrix: A lower bound on the Gram matrix's least eigenvalue converts the first-order prediction update into a contraction of the residual.The argument relies on controlling G(H)(k) throughout training.
Stability: Sufficiently large width keeps each weight matrix close to initialization, limiting Gram-matrix perturbations during training.The required width depends on how perturbations amplify through the architecture.
Architecture dependence: For fully connected networks, perturbation amplification is exponential in depth, whereas ResNet and convolutional ResNet amplification is polynomial in depth.The required width is proportional to the corresponding amplification factor.

B. Proofs for Section 5

The Section 5 proofs establish initialization control, weight stability, Gram-matrix stability, and bounded update terms for multilayer fully connected networks. These ingredients support the claimed linear convergence.

Initialization: The fully connected network proof begins by deriving the multilayer gradient and analyzing the Gram matrix at initialization.The initial least-eigenvalue bound is obtained using assumptions about the population Gram matrix and concentration inequalities.
Initialization: With high probability, layer features are approximately normalized under Lipschitz activation and sufficient-width assumptions.The bounds are established uniformly over layers and training examples.
Perturbation control: Weight perturbations are propagated layer by layer to control their effect on network inputs and the Gram matrix.The proof uses induction and smoothness or Lipschitz properties of the activation.
Loss decrease: The perturbation and quadratic update terms are bounded under a sufficiently small learning rate.These bounds are then combined with the Gram-matrix lower bound in the loss recurrence.

C. Proofs for Section 6

The Section 6 proofs extend the stability argument to ResNets and convolutional ResNets. They control normalized features, initialization spectra, perturbation propagation, and update terms under architecture-dependent width and step-size conditions.

ResNet proof: The ResNet proof analyzes the residual architecture's gradient and Gram matrix before controlling training dynamics by induction.The loss-convergence induction is paired with bounds on deviation from initialization.
ResNet initialization: With high probability, ResNet layer features are approximately normalized under the stated activation and initialization conditions.The normalization result is uniform over layers and training points.
ResNet initialization: The ResNet initialization analysis lower bounds the least eigenvalue of the Gram matrix.This spectral bound supplies the central conditioning quantity for the convergence argument.
ResNet stability: Induction bounds how weight perturbations propagate through ResNet layers and alter the Gram matrix.The proof separately controls perturbation and quadratic terms using sufficiently small learning rates.
Convolutional ResNet: The convolutional ResNet proof repeats this strategy while accounting for the number of patches p in feature and perturbation bounds.Its assumptions and step-size constraints include architecture-dependent polynomial factors in p.

E.1. A General Framework for Analyzing Random Initialization in First (H −1) Layers

This section develops a framework for analyzing Gram matrices at random initialization across fully connected, ResNet, and convolutional architectures. It defines population Gram matrices and quantifies the over-parameterization required for empirical Gram matrices to remain close to them.

The framework targets population Gram matrices and bounds the width m needed for random initialization to approximate them.The bound depends on the sample count n and properties of the activation function.
Network setup: The unified architecture uses deterministic mappings D^(h): fully connected networks set them to zero, while ResNet and convolutional ResNet set them to identity.The activation notation ρ incorporates scaling, and the fully connected and ResNet cases use one-dimensional layer outputs.
Network setup: The network is defined recursively across layers, with indices for data points, layers, channels, or weight vectors.Weights are independently generated, and weights at each layer follow a layer-specific distribution P^(h).
Gram-matrix recursion: Population Gram matrices are defined recursively, with the next-layer matrix depending on both the previous Gram matrix and a bias term.The final-layer Gram matrix has a qualitatively different definition involving σ′ rather than σ.
Architecture-dependent bounds: Convolutional ResNet has the same parameter scaling as ResNet, but its Gram matrix is np × np and therefore requires larger width.The architecture-specific constants differ between fully connected networks and ResNet.
Concentration analysis: Concentration inequalities are applied inductively across layers to control initialization errors and their propagation.The proof combines conditional expectations, Bernstein and Hoeffding bounds, and layer-by-layer induction.

F.1. Full Rankness of K(h) for the Fully-connected Neural Network

This section establishes full rankness of the fully connected network’s Gram matrices under non-parallel inputs and suitable activation assumptions. It further shows that the minimum eigenvalue remains bounded with a depth-independent activation- and data-dependent factor.

Positive definiteness: Non-parallel input vectors are sufficient for K^(H) to be strictly positive definite.The result is stated for the final-layer Gram matrix under the paper’s activation assumptions.
Layerwise induction: The full-rankness proof propagates positive definiteness through earlier layers and uses the final-layer kernel result to conclude for K^(H).For ResNet, the identity mapping D^(h) is used in the corresponding eigenvalue argument.
Kernel argument: For analytic, non-polynomial activations and non-parallel data, the induced kernel Gram matrix satisfies λmin(G(Z)) > 0.The proof establishes linear independence of the feature maps induced by the kernel.
Depth dependence: λmin(K^(H)) is lower-bounded by c_Hκ, where κ depends only on the activation and input data, not on depth.The paper explicitly states that this quantity does not depend inverse exponentially on H.