PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks

Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu

arXiv:1811.08888v3cs.LGcs.AImath.OCstat.ML

TL;DR

The paper asks whether deep ReLU networks can be reliably optimized despite the difficulty of neural-network training. It analyzes GD and SGD with Gaussian initialization and shows that both can reach global training minima for over-parameterized networks under mild data assumptions, using confinement near initialization and local curvature.

  • Problem

    Training neural networks is theoretically difficult, motivating analysis of optimization in deep networks.

  • Method

    The paper analyzes GD and SGD on over-parameterized deep ReLU classifiers initialized with Gaussian random weights, tracking iterates near initialization.

  • Results

    Both GD and SGD can achieve global minima of training loss for over-parameterized deep ReLU networks with random initialization and mild training-data assumptions.

  • Takeaways & Limitations

    The theory sheds light on why SGD can train deep neural networks effectively in practice and supports studying optimization dynamics in more sophisticated architectures.

  • Takeaways & Limitations

    The authors identify sharpening the polynomial dependence on problem-specific parameters as future work.

Abstract

from arXiv · show

We study the problem of training deep neural networks with Rectified Linear Unit (ReLU) activation function using gradient descent and stochastic gradient descent. In particular, we study the binary classification problem and show that for a broad family of loss functions, with proper random weight initialization, both gradient descent and stochastic gradient descent can find the global minima of the training loss for an over-parameterized deep ReLU network, under mild assumption on the training data. The key idea of our proof is that Gaussian random initialization followed by (stochastic) gradient descent produces a sequence of iterates that stay inside a small perturbation region centering around the initial weights, in which the empirical loss function of deep ReLU networks enjoys nice local curvature properties that ensure the global convergence of (stochastic) gradient descent. Our theoretical results shed light on understanding the optimization for deep learning, and pave the way for studying the optimization dynamics of training modern deep neural networks.

1 Introduction

The paper studies optimization in over-parameterized deep ReLU networks, showing that properly initialized gradient descent and stochastic gradient descent can reach global training minima under mild data assumptions.

  • Motivation: The paper targets the optimization behavior of deep ReLU networks, where training remains theoretically difficult despite their empirical success.Without additional assumptions, even training shallow neural networks can be NP-hard.
  • Main results: For binary classification and any number of hidden layers, over-parameterization and random initialization enable GD and SGD to achieve global minima of training loss.The result applies to a broad class of loss functions rather than only cross-entropy or quadratic loss.
  • Proof idea: Gaussian initialization followed by optimization keeps iterates in a small region around the initial weights, where the empirical loss has favorable local curvature.These local properties support the convergence analysis for both GD and SGD.
  • Main results: GD achieves zero training error with sufficiently wide hidden layers within a quantity polynomial in the problem parameters.The supplied passages identify the width condition and iteration bound only partially through asymptotic notation.
  • Main results: The paper also establishes an analogous SGD convergence result under Gaussian initialization and sufficient hidden-layer width.The result concerns achieving zero training error.
  • Assumptions: The data assumption requires separation only between examples with different labels, and is described as milder and more practical than stronger prior assumptions.It holds for distributions with a constant margin separating classes.

2 Related Work

Related work studies shallow ReLU networks with random initialization, teacher-generated data, and deep linear networks, while this paper extends optimization analysis to deep ReLU classification.

  • One-hidden-layer networks: Prior work analyzed shallow two-layer networks with teacher-generated data, including recovery of ground-truth parameters by gradient descent.One cited result establishes linear-rate recovery for one-hidden-layer ReLU networks.
  • Deep linear networks: Other research studies optimization landscapes of deep linear networks, including the absence of spurious local minima and globality of local minima.These results concern deep linear or residual architectures rather than deep ReLU classification.

3 Problem Setup and Preliminaries

The paper formulates binary classification with fully connected deep ReLU networks, smooth loss functions, separated data, Gaussian initialization, GD, and SGD.

  • Network and objective: The model is an L-hidden-layer fully connected network with entry-wise ReLU activations, layer weight matrices, and a fixed signed output vector.The input dimension is set as m0 = d, and the network is trained through empirical risk minimization.
  • Loss assumptions: The loss is continuous, has nonpositive derivative, approaches zero with its derivative at positive infinity, and satisfies additional derivative and smoothness bounds.The stated loss family includes hinge, cross-entropy, and exponential losses.
  • Data assumptions: Training examples have unit norm, a fixed final input coordinate providing bias, and label-dependent separation of at least φ.Only examples with different labels are required to be separated.
  • Width assumptions: The widths of all hidden layers are assumed to be of the same order, with the largest width at most twice the smallest.The constant 2 is described as nonessential.
  • Optimization algorithms: Both GD and SGD begin from Gaussian-initialized weight matrices and update the layer weights using a step size η.SGD samples minibatches and computes stochastic gradients at each iteration.

4 Main Theory

The paper proves that over-parameterized deep ReLU networks trained from Gaussian initialization can reach arbitrarily small training loss for binary classification using both GD and SGD, under data and loss assumptions.

  • Main result: Over-parameterization and Gaussian initialization enable GD and SGD to converge to the global minimum of the empirical training loss.The result applies to L-hidden-layer fully connected ReLU networks for any L ≥ 1.
  • Gradient Descent: GD reaches training loss at most ϵ with high probability under polynomial-width and iteration conditions.The theorem uses step size η = O(n^-3L^-9m^-1).
  • Gradient Descent: The required GD width and iteration counts are polynomial in the sample size n, separation parameter φ, and depth L.The depth dependence is reported as polynomial and is better than the dependence in Du et al. (2018a).
  • Gradient Descent: If ℓ(0) > 0, GD can find a point with zero training error when each hidden layer is sufficiently wide.The required width is specified by Corollary 4.3.
  • Stochastic Gradient Descent: SGD achieves the same type of high-probability training-loss guarantee under an additional derivative condition on the loss.The derivative assumption controls the SGD optimization trajectory.
  • Stochastic Gradient Descent: Compared with GD, SGD requires width and iterations larger by a factor ranging from O(n^2) to O(n^4) to achieve zero training error.The comparison is stated for the zero-training-error guarantees.

5 Proof of the Main Theory

The proof combines Gaussian initialization bounds, local perturbation analysis, convergence inside a controlled region, and width conditions that keep iterates in that region until optimization succeeds.

  • Initialization: The proof first establishes high-probability structural properties of Gaussian-initialized random matrices.These properties provide the basic network structure used in later steps.
  • Local geometry: Within a small perturbation region around initialization, the network has favorable local curvature and controlled activation changes.The perturbation analysis bounds output, activation-pattern, and gradient changes.
  • Convergence: Assuming iterates remain inside the perturbation region, the authors derive convergence conditions for GD and SGD.The conditions constrain the product of iteration count k and step size η.
  • Stability: For kη ≤ T, the iterates remain within radius τ of the Gaussian initialization.This stability result justifies applying the local curvature theorem throughout optimization.
  • Width choice: The proof chooses sufficiently large hidden-layer widths so convergence occurs before the iterates can leave the perturbation region.This closes the bootstrap between the convergence and stability arguments.
  • Stochastic Gradient Descent: SGD uses analogous arguments, with a loss-derivative assumption needed to control its stochastic trajectory.The resulting SGD guarantee is stated for finding a point with training loss at most ϵ.

6 Conclusions and Future Work

The paper concludes that GD and SGD can globally optimize over-parameterized deep ReLU networks under mild data assumptions, while leaving sharper parameter dependence for future work.

  • Conclusions: Both GD and SGD can achieve global minima for over-parameterized deep ReLU networks with random initialization and a general class of loss functions.The conclusion emphasizes only mild assumptions on the training data.
  • Conclusions: The theory is presented as evidence relevant to understanding why SGD trains deep neural networks effectively in practice.The authors also connect it to future study of optimization dynamics in more sophisticated networks.
  • Future Work: The authors identify sharpening the polynomial dependence on problem-specific parameters as future work.This is the stated scope boundary for the current theoretical rates.

A Proof of Theorem 5.1

The appendix proves the Gaussian-initialization properties used by the main theory, including norm preservation, separation control, activation-pattern bounds, and gradient regularity.

  • Random initialization: Gaussian random weights preserve layerwise output norms up to high-probability bounds.The argument conditions on the preceding layer and applies concentration inequalities before induction across layers.
  • Propagation through depth: ReLU truncation and Gaussian concentration control how sample norms and pairwise separations evolve through depth.The appendix uses Gaussian calculations, Bernstein bounds, union bounds, and induction.
  • Separation bound: The appendix derives the depth-dependent separation bound by applying the one-layer estimate repeatedly across layers.The resulting bound is stated after union bounding and induction.
  • Activation patterns: The activation-pattern lemma bounds the number of near-zero preactivations using the parameter β.The bound holds simultaneously over layers and training examples under a width condition.
  • Gradient regularity: Theorem 5.1 combines these concentration results with covering-number arguments to establish gradient Lipschitz properties.These properties support the local perturbation and convergence analysis.

B Proof of Theorem 5.3

The proof establishes perturbation and activation-pattern bounds for Gaussian-initialized deep ReLU networks, then derives stability of hidden representations and related matrix products.

  • Matrix-product bounds: Auxiliary lemmas decompose products of weight and activation matrices into cases and bound each resulting term.The argument combines these casewise bounds to obtain an overall product estimate.
  • Perturbation stability: Perturbing each weight matrix by at most τ controls the differences between corresponding hidden-layer outputs.The bound scales with L and the cumulative perturbation across layers.
  • Activation patterns: The proof bounds the number of ReLU sign changes caused by weight and representation perturbations.These bounds control differences between the associated diagonal activation matrices.
  • Consequences: Corollary B.4 applies the activation-change estimate to bound the size of the perturbed final-layer sign-change set.The result follows directly from Lemma B.3.

C.1 Proof of Lemma 5.4

The proof analyzes one gradient-descent update using smoothness and lower bounds on the gradient, then accumulates decrease over iterations to obtain a target-loss condition.

  • Setup: The iterates are assumed to remain within a radius-τ perturbation region around Gaussian-initialized weights.This invariant is used together with the assumptions of Theorem 5.3.
  • One-step analysis: Smoothness provides an upper bound on the loss change after each gradient-descent update.The proof applies λ-smoothness to the update increment.
  • One-step analysis: The analysis uses the gradient of the last hidden-layer weight matrix to ensure loss decrease.The resulting inequality is substituted into the one-step descent bound.
  • Iteration count: The proof treats p = 1/2 separately from p ≠ 1/2 when summing the per-iteration loss decrease.The resulting telescoping bounds determine the required product Kη.
  • Iteration count: The initial network output and smoothness imply an initial training loss of order O(1).This determines the cumulative decrease required to reach target accuracy ε.

D Proof of Lemma 5.5

The proof of Lemma 5.5 uses induction to show that gradient-descent iterates remain within the prescribed perturbation region around initialization.

  • Inductive control: The induction assumes the iterate bound for all earlier steps and applies the preceding descent inequality.The argument combines the loss-decrease relation with auxiliary perturbation bounds.
  • Inductive control: The accumulated update remains small enough that each layer stays within distance τ of its initialization.The proof concludes this invariant for the current iteration and completes the induction.

D.1 Proof of Lemma 5.6

The stochastic-gradient proof bounds conditional loss changes and their expectations under minibatch sampling, then telescopes these bounds to obtain convergence requirements.

  • Setup: The stochastic-gradient iterates are assumed to remain in a small perturbation region with controlled activation changes.The assumptions constrain τ, the activation-change sparsity s, and the maximum iteration number.
  • One-step stochastic analysis: The proof derives the one-step stochastic loss change by conditioning on the current iterate and taking expectation over minibatch randomness.It combines smoothness, gradient bounds, and auxiliary lemmas.
  • Parameter choices: The step size is constrained by η ≤ c0mφB^4C3n^4L^9M^2 = O(Bn^-4L^-9M^-1φ).This condition is used to control the stochastic update within the perturbation regime.
  • Convergence: Telescoping the expected loss inequalities yields iteration requirements that differ between p ≠ 1/2 and p = 1/2.The proof then specifies step-size and iteration choices sufficient to reach loss at most ε.
  • Convergence: For p ≠ 1/2, the proof requires k = rΩ(n^12-4pB^-2φ^-2) to obtain the needed cumulative decrease.The stated requirement is part of the parameter selection for stochastic-gradient convergence.

D.2 Proof of Lemma 5.7

The proof controls the stochastic-gradient iterates and the quantity L_S(W^(k)) under suitable initialization, step size, and perturbation-radius conditions. It establishes high-probability bounds that hold uniformly over iterations.

  • Case analysis: The proof treats p ≠ 1/2 and p = 1/2 separately because their bounds use different forms.The p ≠ 1/2 case uses powers involving 1−2p, while p = 1/2 uses logarithmic bounds.
  • Control of the loss-related quantity: With probability at least 1−δ, L_S(W^(k)) remains rÕ(1) for a fixed iteration k.The argument selects η = O(φm^-1n^(2p−7)L^-8B^2) to control the relevant increment.
  • Control of the loss-related quantity: With probability at least 1−Kδ, L_S(W^(k)) = rÕ(1) holds simultaneously for all k ≤ K.The uniform statement follows by applying a union bound over the iterations.
  • Iterate stability: For kη ≤ T, induction keeps W^(k) inside the perturbation region centered at W^(0) with radius τ.The stated horizon is T = rÕ(τL^-2M^-1/2n^-1), with η = O(φm^-1n^(2p−7)L^-8B^2).

E.3 Proof of Lemma D.1

Lemma D.1 is proved by adapting the argument for Lemma C.2 from full gradients to stochastic gradients. The supporting bounds use Theorem 5.3 and separate cases according to p.

  • Proof strategy: The proof replaces the full-gradient bound in Lemma C.2 with a bound on the stochastic gradient G^(k).The proof technique is otherwise described as essentially identical to Lemma C.2.
  • Proof strategy: The stochastic-gradient bound is obtained using part (viii) of Theorem 5.3.The cited theorem supplies the bound substituted into the Lemma C.2-style argument.
  • High-probability control: Azuma’s inequality yields bounds holding with probability at least 1−δ for the corresponding stochastic-gradient evolution.The displayed bounds include terms involving k, log(1/δ), n, L, M, η, and B.
Loading 1811.08888v3…