PaperlayerView exact revision on arXiv

Source-linked AI summary

An Improved Analysis of Training Over-parameterized Deep Neural Networks

Difan Zou, Quanquan Gu

arXiv:1906.04688v1cs.LGmath.OCstat.ML

TL;DR

Existing analyses established global convergence for sufficiently wide neural networks but often required very stringent width conditions. This paper sharpens the analysis of GD and SGD using improved gradient and trajectory-length bounds, obtaining milder width requirements and faster convergence, including for two-layer ReLU networks.

  • Problem

    Global-convergence analyses for gradient-based training of over-parameterized deep networks required stringent width conditions, often high-degree polynomials in n.

  • Method

    The paper analyzes GD and SGD with Gaussian random initialization using a tighter gradient lower bound and a sharper characterization of trajectory length.

  • Results

    The analysis proves faster global convergence under milder width conditions for deep networks and improves the corresponding two-layer ReLU results.

  • Takeaways & Limitations

    The proof techniques may also apply to cross-entropy loss, convolutional networks, and ResNet architectures.

  • Takeaways & Limitations

    The stated theory assumes unit-ℓ2-norm training inputs and an additional positive-coordinate condition on each input.

Abstract

from arXiv · show

A recent line of research has shown that gradient-based algorithms with random initialization can converge to the global minima of the training loss for over-parameterized (i.e., sufficiently wide) deep neural networks. However, the condition on the width of the neural network to ensure the global convergence is very stringent, which is often a high-degree polynomial in the training sample size $n$ (e.g., $O(n^{24})$). In this paper, we provide an improved analysis of the global convergence of (stochastic) gradient descent for training deep neural networks, which only requires a milder over-parameterization condition than previous work in terms of the training sample size and other problem-dependent parameters. The main technical contributions of our analysis include (a) a tighter gradient lower bound that leads to a faster convergence of the algorithm, and (b) a sharper characterization of the trajectory length of the algorithm. By specializing our result to two-layer (i.e., one-hidden-layer) neural networks, it also provides a milder over-parameterization condition than the best-known result in prior work.

1 Introduction

The paper targets stringent width requirements for global convergence in over-parameterized deep networks and develops sharper analyses for GD and SGD. Its results improve width and iteration bounds, including for two-layer ReLU networks.

  • Motivation: Prior deep-network convergence theory required unrealistic width conditions, including eΩ(kn^24L^12φ^-8) for GD and SGD.Here n is the training sample size, L the number of hidden layers, k the output dimension, and φ the minimum data separation distance.
  • Main contributions: The paper improves global convergence guarantees for GD and SGD under milder neural-network width conditions than prior work.The analysis uses Gaussian random initialization on each layer.
  • Main contributions: A tighter gradient lower bound yields faster convergence rates, while a sharper trajectory-length characterization supports the improved analysis.These are the paper’s two stated proof techniques.
  • GD results: Compared with Allen-Zhu et al. (2018b), the GD width condition improves by eΩ(n^16φ^-4) and iteration complexity by eO(n^4φ^-1).The comparison concerns deep neural-network training under the paper’s stated setting.
  • SGD results: For SGD, the corresponding improvements over Allen-Zhu et al. (2018b) are eΩ(n^7B^5) for width and eO(n^2) for iteration complexity.B denotes the minibatch size.

2 Problem setup and algorithms

The paper formulates training for fully connected deep ReLU networks using empirical loss, and studies both full-batch and minibatch gradient descent with shared Gaussian random initialization.

  • Network architecture: The model is an L-hidden-layer fully connected network mapping x ∈ R^d to y ∈ R^k through weight matrices and a vector-valued function f_W.The hidden layers use width m, while V is the output-layer weight matrix.
  • Activation: The network uses entry-wise ReLU activation σ(x) = max{0, x}, with σ′(x) denoting its derivative.The notation also identifies the weight vector associated with each node and layer.
  • Training objective: The training set contains n input-output pairs, and the empirical objective evaluates a loss between each target y_i and prediction ŷ_i = f_W(x_i).The paper specializes this objective to square loss for exposition.
  • Loss scope: The paper notes that its square-loss analysis can be extended to other losses, including cross-entropy loss.This extension is stated as straightforward rather than developed in the setup section.
  • Algorithms: Gradient descent updates weights using the full gradient, whereas stochastic gradient descent uses a minibatch B(t) of size B at each iteration.Both algorithms are presented in Algorithm 1 and share the same initialization.

3 Main theory

Under unit-norm, separated training data, the paper proves global convergence for GD and SGD with milder width requirements and faster iteration complexity than prior analyses, with further improvements for two-layer networks.

  • Assumptions: The theory assumes unit-norm inputs whose pairwise distances are at least φ, an assumption described as mild for the regression setting.The unit-norm condition can be relaxed to inputs whose norms are bounded above and below by constants.
  • Gradient descent: With probability at least 1 − O(n^-1), GD reaches ε training loss under a specified width condition for L-hidden-layer ReLU networks.The guarantee is stated in Theorem 3.3 and uses the same two data assumptions.
  • Gradient descent: Compared with Allen-Zhu et al. (2018b), the GD iteration complexity improves by O(n^4/φ), while the over-parameterization condition improves by eΩ(n^16/φ^4).The paper also contrasts its polynomial dependence on L with the exponential dependence in Du et al. (2018a).
  • Two-layer GD: For two-layer ReLU networks, the paper removes dependence on L and reports milder width and iteration requirements than prior two-layer results.The comparison includes Du et al. (2018b) and Oymak and Soltanolkotabi (2019).
  • Assumptions: Under these assumptions, the smallest Gram-matrix eigenvalue satisfies λ0 ≥ Cφn^-2, and λ0 > 0 is equivalent to the separation assumption.The Gram matrix is defined on the training data.
  • Stochastic gradient descent: With probability at least 1 − O(n^-1), SGD reaches ε expected training loss under the stated width condition for L-hidden-layer networks.Theorem 3.8 extends the global-convergence result from GD to SGD.
  • Stochastic gradient descent: Relative to Allen-Zhu et al. (2018b), the SGD width condition improves by eΩ(n^7B^5), and iteration complexity improves by O(n^2).The comparison is stated in Remark 3.9.
  • Two-layer SGD: For two-layer networks, SGD receives a further improvement in over-parameterization because the loss has nicer local properties near initialization.The specialized result is stated in Theorem 3.10.

4 Proof sketch of the main theory

The proof establishes global convergence by combining local training-loss regularity, an improved gradient lower bound, and tighter control of the optimization trajectory. It then verifies that GD iterates remain in the perturbation region long enough to achieve the target accuracy.

  • Perturbation region: The perturbation region is defined around initialization with preset radius τ for each weight matrix.
  • Gradient lower bound: The gradient lower bound uses disjoint regions associated with all training examples, making the utilized region roughly n times larger than prior analyses.This yields an O(n) improvement in the gradient lower bound.
  • GD convergence and trajectory: The sharper trajectory characterization improves over a prior bound of C′kn^6L^2(W(0))/(mφ^2), contrasting with the tighter order Ckn^2L(W(0))/(mφ).
  • The proof roadmap has three steps: establish curvature within a perturbation region, prove convergence there, and keep all iterates inside it.
  • Training-loss properties: The initial training loss does not depend on the number of hidden nodes per layer m under the stated initialization conditions.
  • Training-loss properties: Local semi-smoothness makes the non-smooth ReLU term small when τ ≪1, so the training loss behaves approximately like a smooth function in the region.
  • GD convergence and trajectory: Gradient descent decreases the training loss at a linear rate, while the trajectory bound is checked against τ to ensure all iterates stay inside the required region.

5 Conclusions and future work

The paper improves global-convergence results for gradient descent and stochastic gradient descent on overparameterized ReLU networks. The authors suggest extending the proof technique to other losses and architectures, while identifying sharper over-parameterization, convergence, and generalization analyses as future directions.

  • The paper improves state-of-the-art global-convergence results for gradient descent and stochastic gradient descent on overparameterized ReLU networks.
  • Future work: The proof technique may extend to cross-entropy loss, convolutional neural networks, and ResNet.
  • Future work: Future work includes further improving the over-parameterization condition and convergence rate.
  • Future work: Another direction is applying the technique to generalization analysis of overparameterized networks trained by gradient-based algorithms.

A.1 Proof of Proposition 3.6

The proposition characterizes the smallest eigenvalue of the Gram matrix according to whether the training data contain duplicates. Distinct data yield a positive eigenvalue, whereas duplicates force the eigenvalue to zero.

  • Without duplicate training data, the proposition proves that λmin(H) > 0.
  • If two training examples are identical, corresponding rows of H are identical, implying λmin(H) = 0.
  • The proof combines the positive-eigenvalue result for nonparallel inputs with the duplicate-row argument to complete the proposition.

A.2 Proof of Theorem 3.8

The SGD proof follows the GD analysis but adds gradient upper bounds and tighter control of stochastic iterates. Its larger trajectory length and smaller step size make the SGD over-parameterization requirement worse than GD’s.

  • The SGD proof uses initialization and perturbation-region characterization, convergence-rate analysis, and verification that all iterates remain in the region.
  • Initialization and trajectory: Gradient upper bounds control the distance between SGD iterates and their initialization.
  • Convergence rate: SGD converges to the global minimum at a linear rate when iterates stay inside the perturbation region and the step size satisfies the stated conditions.
  • Trajectory verification: Compared with GD, SGD has a much larger trajectory length and requires a much smaller step size, worsening its over-parameterization condition.
  • Trajectory verification: The proof verifies the required width by substituting the selected m into the trajectory bound, then obtains the iteration count needed for ε expected training loss.

A.3 Proof of Theorem 3.10

The proof establishes stochastic-gradient control and uses it with semi-smoothness, step-size choices, and high-probability bounds to derive an iteration guarantee for achieving ε expected training loss.

  • Auxiliary bounds: Lemma A.5 provides a two-layer ReLU semi-smoothness bound whose τ dependence improves over the bound obtained through Frobenius-norm conversion.The passage states that this sharper τ dependence is crucial for a better SGD convergence guarantee.
  • Stochastic-gradient control: The proof bounds the mini-batch stochastic gradient and its conditional expectation using one-step SGD inequalities and auxiliary lemmas.These bounds are established uniformly over iterations with high probability.
  • Convergence guarantee: The proof derives the number of iterations required to achieve ε expected training loss and then concludes the theorem.The iteration count follows from the preceding convergence inequalities.

B.1 Proof of Lemma 4.1

This proof develops upper and lower gradient-norm bounds by combining hidden-layer norm control, initialization estimates, and perturbation-region analyses, then uses them to control SGD trajectories and loss.

  • Initialization and network bounds: The proof first establishes bounded hidden-layer outputs and initialization properties under a width condition involving L, n, k, and φ.Lemma B.1 gives 1/2 ≤ ∥x_l,i∥2 ≤ 2 when m ≥ O(L log(nL)), while Lemma B.2 assumes m ≥ eO(n^2k^2φ−1).
  • Gradient and output control: The proof also bounds the gradient from above and controls network outputs and loss using Gaussian output weights, union bounds, and the assumption ∥y_i∥2 = O(1).The output bound is established uniformly over training examples with probability at least 1 − O(n−1).
  • Gradient bounds: A lower bound for ∥∇_W L_L(f_W)∥F is obtained by analyzing the gradient form and controlling changes inside the perturbation region.The argument combines Lemmas B.1 and B.3 and uses τ ≤ O(L−4/3).
  • SGD trajectory: For SGD, conditional expectation and variance bounds lead to a supermartingale argument that controls the loss and the trajectory over iterations.The proof applies one-sided Azuma’s inequality together with step-size and radius choices.
  • Semi-smoothness: The semi-smoothness proof decomposes activation changes into two terms and bounds the number of changing activation coordinates by O(mτ 2/3).The decomposition yields a bound involving ∥f_W − c_W∥2,∞ and the operator norm of V.

C.1 Proof of Lemma B.2

The proof establishes the initialization gradient lower bound by combining Gaussian concentration, separated normalized hidden representations, and an ε-net argument over coefficient vectors.

  • Geometric setup: The proof considers vectors with bounded norms and pairwise separated normalized directions, then constructs orthonormal coordinate systems for them.The assumptions include 1/2 ≤ min_i ∥z_i∥2 and max_i ∥z_i∥2 ≤ 2, with separation at least eφ.
  • Fixed-vector analysis: For fixed coefficient vectors, Gaussian random variables and disjoint events associated with the separated directions yield lower-bound estimates for the relevant random quantity.The construction defines the coefficients, events, and their moments before applying concentration.
  • Concentration: Bernstein’s inequality converts the moment bounds into a high-probability inequality for the fixed vector collection.The proof then prepares to extend this result beyond one collection.
  • Uniformization: An ε-net over all vector collections in (R^d)^n and a union bound extend the inequality to arbitrary choices of the vectors.The resulting statement holds for all choices of {u_i} simultaneously.

D Proof of Auxiliary Lemmas in Appendix C

The auxiliary lemmas analyze Gaussian regions associated with separated vectors, proving that these regions are disjoint and that their conditioning supports the required lower-bound calculations.

  • Gaussian-region construction: The proof decomposes a Gaussian vector into coordinates aligned with each normalized z_i and defines regions W_i using these coordinates.The parameter γ controls the regional construction and subsequent probability estimates.
  • Disjointness: The regions W_i and W_j are shown to be disjoint because the defining constraints for W_j conflict with the separation condition imposed by W_i.The argument uses |⟨z̄_i, z̄_j⟩| ≤ 1 and the threshold conditions involving γ.
  • Probability bounds: The probability of each region is bounded using Gaussian-coordinate calculations and a union bound over the vector indices.The auxiliary estimates control simultaneous inner products with the other normalized vectors.
  • Conditional separation: Conditioning on W_i separates the sign cases of the aligned coordinate and enables a lower-bound calculation for ∥h(w_1) − h(w_2)∥2.The proof completes the auxiliary estimate after applying the decomposition and norm bound for z_i.
Loading 1906.04688v1…