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 reasons deep neural networks work well remain unclear, including how they are optimized. This paper analyzes gradient descent and stochastic gradient descent for over-parameterized deep ReLU networks, proving that both can reach global training-loss minima under mild data assumptions.

  • Problem

    How deep neural networks are optimized remains unclear despite their success across applications.

    Source: §1 · p. 1

  • Method

    The proof analyzes gradient descent and stochastic gradient descent from Gaussian random initialization, showing their iterates remain in a small perturbation region around the initial weights.

    Source: §1 · p. 2

  • Results

    Both gradient descent and stochastic gradient descent can achieve global minima of over-parameterized deep ReLU network training loss for a general class of losses under mild training-data assumptions.

    Source: §1 · p. 2, §6 · p. 14

  • Takeaways & Limitations

    The theory offers insight into why stochastic gradient descent can train deep neural networks well in practice and motivates studying optimization dynamics in more sophisticated networks.

    Source: §6 · p. 14

    The authors leave sharpening the polynomial dependence of their results on problem-specific parameters for future work.

    Source: §6 · p. 14

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 shows that, with over-parameterization and random initialization, gradient descent and stochastic gradient descent can reach global training-loss minima for deep ReLU networks under a data-separation assumption.

Related work

  • Unlike Li and Liang (2018) and Du et al. (2018b), which study shallow networks, this work treats deep classification; concurrent studies focus on regression, while this handles nonsmooth ReLU under a different data assumption.Allen-Zhu et al. (2018b) also extends shallow-network results to deep ReLU networks, but focuses on regression with least-squares loss.Source: §1 · pp. 2–3

Main results

  • For binary classification, both GD and SGD achieve global training-loss minima in fully connected ReLU networks with any number of hidden layers, across a broad family of losses.The results extend beyond the shallow-network settings and specific losses considered in the cited prior work.Source: §1 · pp. 2–3

Proof idea

  • Gaussian initialization and gradient-based updates keep iterates in a small perturbation region where local curvature of the empirical loss ensures global convergence.This is the proof's central mechanism for both GD and SGD.Source: §1 · p. 2

GD convergence

  • With Gaussian initialization and sufficiently wide layers, GD achieves zero training error within the stated iteration bound.The width and iteration expressions are garbled in the supplied passages, so their exact values cannot be reported.Source: §1 · pp. 2–3

SGD convergence

  • The paper also proves that SGD achieves zero training error with Gaussian layerwise initialization when the hidden-layer width meets the stated threshold.The supplied passages do not preserve the exact threshold or iteration expression.Source: §1 · p. 3

Data assumptions

  • The analysis assumes data separation, which holds when the data distribution has a constant margin between classes, and presents this as milder than Du et al. (2018b)'s Gram-matrix assumption.The paper also describes its separation assumption as slightly milder than Li and Yuan (2017)'s.Source: §1 · p. 3

2 Related Work

The related work reviews three research lines: recovery guarantees for shallow teacher networks, optimization landscapes of deep linear networks, and generalization bounds for deep neural networks.

One-hidden-layer neural networks with ground truth parameters

Deep linear networks

  • Deep-linear-network studies establish no spurious local minima or only global local minima, depth-related acceleration, and least-squares convergence under specified initialization and regularization (Hardt and Ma, 2016; Kawaguchi, 2016; Arora et al., 2018a,b; Bartlett et al., 2018).Bartlett et al. (2018) showed GD converges to the least-squares solution for residual linear networks with quadratic loss using identity initialization and proper regularization; Arora et al. (2018a) extended these properties to general deep linear networks.Source: §2 · p. 4

Generalization bounds for deep neural networks

3 Problem Setup and Preliminaries

The section defines the ReLU network, empirical-risk training setup, and assumptions on losses, data, and widths, then specifies Gaussian-initialized GD/SGD and introduces network-output and gradient notation.

3.1 Notation

  • The notation section establishes conventions for scalars, vectors, matrices, norms, asymptotic bounds, and ordered matrix products.It includes vector ℓ8 and ℓ0 norms and matrix Frobenius, spectral, and nonzero-entry counts.Source: §3.1 · pp. 4–5

3.2 Problem Setup

  • The model uses L hidden ReLU layers on binary-labeled examples, with a fixed output-weight vector containing equal numbers of +1 and -1 entries, and minimizes empirical risk.The network weights are the trainable parameters; its input dimension is set to d.Source: §3.2 · p. 5
  • The loss is continuous, nonincreasing, vanishes at positive infinity with derivative tending to zero, has a bounded-derivative condition, and is λ-smooth.The derivative condition covers hinge, cross-entropy, and exponential losses; a specified limiting case reduces to the PL condition.Source: §3.2 · p. 5
  • Inputs have unit norm and shared last coordinate μ; differently labeled inputs are separated by at least φ, and the largest layer width is at most twice the smallest.The label-dependent separation is weaker than requiring every pair of distinct points to be separated; the width factor 2 can be replaced by any constant at least 1.Source: §3.2 · pp. 5–6

3.3 Optimization Algorithms

  • Gaussian initialization independently draws each layer-weight column from N(0, 2/m_l I), after which GD uses the full empirical-risk gradient and SGD uses sampled minibatch gradients.Both updates use step size η; each SGD minibatch has batch size B.Source: §3.3 · p. 6

3.4 Preliminaries

  • The preliminaries introduce notation for layer outputs, the network output, and the partial gradient of training loss with respect to layer weights.The notation section also defines vector and matrix norms, asymptotic bounds, and ordered matrix products.Source: §3.1 · p. 4, §3.4 · pp. 6–7

4 Main Theory

With Gaussian initialization, over-parameterization lets gradient descent and stochastic gradient descent reach arbitrarily small training loss; the theorems give high-probability guarantees under stated assumptions.

4.1 Gradient Descent

  • With Gaussian initialization and Assumptions 3.1–3.6, gradient descent reaches empirical loss at most ϵ with high probability using the theorem’s prescribed width and iterations.The stated step size is η = O(n^-3 L^-9 m^-1).Source: §4.1 · pp. 7–8
  • Gradient descent’s required width and iteration count are polynomial in n, separation parameter φ, and depth L, with ϵ-dependence ranging from Õ(ϵ^-1) to Õ(1).The authors state that depth dependence is polynomial, unlike the e^Ω(L) dependence proved by Du et al. (2018a).Source: §4.1 · p. 8
  • If ℓ(0) > 0, the width condition in Corollary 4.3 lets gradient descent reach zero training error under Theorem 4.1’s assumptions.Corollary 4.6 gives the corresponding zero-training-error guarantee for stochastic gradient descent under Theorem 4.5’s assumptions.Source: §4.1 · p. 8, §4.2 · p. 9

4.2 Stochastic Gradient Descent

  • The stochastic-gradient guarantee adds Assumption 4.4, which bounds the loss derivative from above as well as below by functions of the loss with the same order p.When α0 is finite, the passage notes that the loss is ρ0-Lipschitz.Source: §4.2 · p. 8
  • With Gaussian initialization and Assumptions 3.1–3.6 plus 4.4, stochastic gradient descent reaches empirical loss at most ϵ with high probability using the theorem’s prescribed width and iterations.The stated step size is η = O(n^-3 L^-9 m^-1).Source: §4.2 · pp. 8–9
  • Compared with gradient descent, stochastic gradient descent requires n^2 to n^4 times more width and iterations to achieve zero training error, though both requirements are polynomial in n, φ, and L.The comparison is reported in Remark 4.7.Source: §4.2 · p. 9

5 Proof of the Main Theory

The proof establishes high-probability properties of Gaussian initialization, then uses local behavior near those initial weights to prove convergence of gradient descent and stochastic gradient descent. It also shows that sufficiently wide layers keep the iterates within the region where that local analysis applies until the loss target is reached.

5 Proof of the Main Theory

  • For both methods, bounds on kη keep iterates within radius τ, and sufficiently wide layers let the loss target be reached before that bound is exceeded.The proofs combine conditional convergence inside the region with bounds on how long iterates stay there, then choose layer width to make convergence occur in time.Source: §5 · p. 9, §5.1 · p. 12, §5.2 · p. 13
  • Theorem 5.1 supplies high-probability properties of Gaussian-initialized weights under the stated assumptions and sufficient width, forming the basis for the subsequent analysis.The theorem’s parameters characterize ReLU activation patterns, and the proof relates their values to the perturbation level and layer width.Source: §5 · pp. 9–10
  • Within the perturbation region, Theorem 5.3’s gradient lower and upper bounds establish local curvature and quantify weight changes that help prevent the iterates from escaping.The theorem analyzes weight matrices within radius τ of Gaussian initialization and bounds changes in network activations and gradients.Source: §5 · pp. 10–11

5.1 Proof of Theorem 4.1

  • Within the prescribed perturbation region, gradient descent reaches a point with empirical loss at most ϵ under the stated initialization, assumptions, and step-size conditions.Lemma 5.4 establishes convergence assuming the iterates remain in the region; the proof of Theorem 4.1 then ensures the target is reached before the iterates exceed its radius.Source: §5.1 · p. 12

5.2 Proof of Theorem 4.5

  • Under Gaussian initialization, Assumptions 3.1–3.6 and 4.4, perturbation level τ = O(n^-9L^-17φ^3), step size η = O(Bn^-4L^-9m^-1φ), and α0 < 8, SGD finds W^(K) with empirical loss L_S(W^(K)) ≤ ϵ.Source: §5.2 · p. 13

6 Conclusions and Future Work

The paper proves that gradient descent and stochastic gradient descent can reach global minima for over-parameterized deep ReLU networks under mild data assumptions. Future work will sharpen the polynomial dependence of the results on problem-specific parameters.

6 Conclusions and Future Work

  • Gradient descent and stochastic gradient descent can achieve global minima for over-parameterized deep ReLU networks with random initialization, a general class of loss functions, and mild training-data assumptions.The theory sheds light on why stochastic gradient descent trains deep neural networks well in practice and paves the way for studying optimization in more sophisticated networks.Source: §6 · p. 14
  • The theory helps explain why stochastic gradient descent trains deep neural networks well in practice and enables future study of optimization in more sophisticated networks.Source: §6 · p. 14
  • Future work will sharpen the polynomial dependence of the results on problem-specific parameters.Source: §6 · p. 14

A Proof of Theorem 5.1

The proof of Theorem 5.1 develops concentration-based bounds on network behavior under Gaussian initialization, including hidden-layer outputs, inner products and separation, and uniform node counts. These high-probability bounds are established under width conditions and address relationships among samples and network outputs.

Layer output norms

  • With ml ≥ C² log(nL/δ), Gaussian initialization preserves each layer’s input norms up to a controlled error, simultaneously over samples and layers with probability at least 1 − δ.The proof extends the single-layer bound across layers by induction.Source: A Proof of Theorem 5.1 · p. 15

Pairwise sample distances

  • If φ ≤ κL^-1 and m ≥ CL^4φ^-4 log(4n²L/δ), normalized sample-pair distances retain a lower bound proportional to [1 − log(2)/(2L)]^l φ^l with probability at least 1 − δ.The stated width and probability conditions come from Lemma A.4; its proof applies union bounds and induction across layers.Source: A Proof of Theorem 5.1 · pp. 17, 19

Output bounds

  • For every training sample i = 1,...,n, the network output satisfies |f_W(x_i)| ≤ C, where C is an absolute constant.The proof uses equal numbers of +1 and −1 entries in v.Source: A Proof of Theorem 5.1 · p. 19

Activation patterns

  • If ml ≥ C max{[β^-1 log(nL/δ)]^(2/3), L² log(nL/δ)}, then |S_l,i(β)| ≤ 2ml^(3/2)β for every layer and sample with probability at least 1 − δ.This is the activation-pattern bound in Lemma A.7.Source: A Proof of Theorem 5.1 · p. 20

Gradient continuity

  • For Theorem 5.1 parts (v)–(vii), the proof combines concentration bounds with covering-number arguments to establish gradient Lipschitz continuity results.Lemma A.8 gives a high-probability bound for all samples and layer pairs when m ≥ C log(nL²/δ).Source: A Proof of Theorem 5.1 · p. 20

Lemmas A.9–A.10

  • The auxiliary sparse-vector and sparse bilinear-form lemmas obtain uniform high-probability bounds when s ≥ C log(nL/δ) and s ≥ C log(nL^2/δ), respectively.Both lemmas state probability at least 1 − δ; C is an absolute constant.Source: A Proof of Theorem 5.1 · pp. 22–23

Lemma A.11

  • For jointly standard Gaussian Z1 and Z2, the proof establishes E[σ(Z1)σ(Z2)] ≥ 1/2 E[Z1Z2].This correlation inequality is used in the induction for the normalized hidden-output bound.Source: A Proof of Theorem 5.1 · p. 24

Theorem 5.1(viii)

  • For layer l and the indicated sample indices i and i′, the cited quantity x_l,iᵀx_l,i′ is bounded below by μ²[1 − (2L)⁻¹ log(2)]ˡ.Source: A Proof of Theorem 5.1 · p. 24

A Proof of Theorem 5.1

  • Taking an infimum in the preceding inequality gives a lower bound a1 on the squared distance between h(w1) and h(w2).This follows after establishing that ⟨zi, z1⟩ ≥ 0 for all i ∈ I1.Source: A Proof of Theorem 5.1 · pp. 27–28
  • With m ≥ Cn^2φ^-1 log(4n), every a ∈ R^n has at least mLφ/2 nodes on layer L satisfying the lemma’s condition, with probability at least 1 - exp(-C1mLφ/n).The lemma uses absolute constants C and C1.Source: A Proof of Theorem 5.1 · pp. 28–29
  • A C1/(4n)-net, Bernstein’s inequality, and a union bound yield the probability bound used in the uniform node-count argument.The net covers the positive part of the unit infinity-norm sphere.Source: A Proof of Theorem 5.1 · p. 28

B Proof of Theorem 5.3 · C Proof of Technical Lemmas in Section 5

These sections establish technical bounds for Gaussian-initialized networks under weight perturbations, covering matrix products, hidden outputs, activation patterns, exceptional nodes, and partial and stochastic gradients. Together, they complete the proof of Theorem 5.3 and its supporting lemmas.

B Proof of Theorem 5.3

  • Lemma B.1 bounds the expanded matrix-product terms by (C2 + e^2)L, using estimates from Theorem 5.1 for the unperturbed and perturbed terms.The proof separates the unperturbed product from terms involving gate or weight perturbations.Source: B Proof of Theorem 5.3 · pp. 30–31
  • For weights within the stated perturbation region, Lemma B.3 bounds the difference between hidden outputs by CL times the sum of layerwise weight differences.The bound applies at every layer and training example, when both weight collections are within distance τ of the Gaussian-initialized weights.Source: B Proof of Theorem 5.3 · p. 33
  • Lemma B.3 bounds activation-pattern changes between perturbed and initialized weights by C1/2 L^4/3 τ^2/3 ml.The proof bounds sign changes between the corresponding layer inputs to control the number of differing diagonal-gate entries.Source: B Proof of Theorem 5.3 · pp. 33–34
  • Corollary B.4 defines S_L as output-layer units whose activation differs for at least one training example and asserts a bound on its size under Lemma B.3’s assumptions.The supplied passage does not show the bound’s formula.Source: B Proof of Theorem 5.3 · p. 35
  • At most C3 n L^(4/3) τ^(2/3) m_L nodes in the layer have an activation-sign change for at least one training example.The bound follows from Lemma B.3.Source: B Proof of Theorem 5.3 · p. 36
  • After excluding those nodes, at least C2 m_L φ/(2n) nodes remain satisfying the stated gradient-coordinate condition, completing the proof.The proof uses the initial count of at least C2 m_L φ/n qualifying nodes and the bound on sign-changing nodes.Source: B Proof of Theorem 5.3 · pp. 36–37
  • Lemma B.6 states that when ||W̃_l − W_l||_2 ≤ τ, an absolute constant bounds the partial gradient and stochastic partial gradient norms.The supplied passage states the condition and existence of bounds, but does not provide their formulas.Source: B Proof of Theorem 5.3 · p. 37

C.1 Proof of Lemma 5.4

Assuming Gaussian initialization and that every iterate stays within radius τ of the initial weights, the proof bounds the loss change and derives iteration requirements, treating p=1/2 separately from p≠1/2.

C.1 Proof of Lemma 5.4

  • The lemma assumes Gaussian initialization, iterates within a radius-τ perturbation region through K steps, and the conditions of Theorem 5.3 to bound the update quantity Δ^(k).The excerpt does not preserve the explicit upper and lower bound formulas.Source: §C.1 · p. 38
  • The proof uses loss smoothness and bounds on the update, then uses only the last hidden-layer weight gradient to ensure loss decrease.It invokes Lemma C.2 and Lemma B.5, together with Assumption 3.2, in deriving the decrease bound.Source: §C.1 · pp. 38–40
  • The proof telescopes the decrease bounds separately for p≠1/2 and p=1/2 to obtain the corresponding loss bounds over K gradient-descent steps.For p≠1/2 it applies Lemma C.1; the excerpt presents a separate argument for p=1/2.Source: §C.1 · pp. 40–41
  • To reach target training loss ε after K steps, the proof derives a requirement on Kη and retains α₀ to handle the cases α₀=∞ and finite α₀.When α₀=∞, the proof removes a term that becomes zero; when α₀ is finite, it treats that term as O(1).Source: §C.1 · p. 41

D Proof of Lemma 5.5

The proof establishes Lemma 5.5 by induction, using bounds for earlier iterates and Lemma B.6 to conclude that the iterate at step k stays within distance τ of its initialization.

D Proof of Lemma 5.5

D.1 Proof of Lemma 5.6

The proof of Lemma 5.6 bounds the SGD loss change and telescopes the resulting decrease, using small-perturbation assumptions on the iterates and auxiliary bounds.

D.1 Proof of Lemma 5.6

  • The iterate bounds are assumed to hold through the maximum iteration K, with τ and s log(M)/m at most κL^-3 for a sufficiently small absolute κ.The weights are generated by Gaussian random initialization, and the stated bounds apply to every layer and iteration.Source: §D.1 · p. 42
  • Under Assumption 3.3, the proof upper-bounds the loss difference between consecutive iterates, takes expectation conditional on W(k), and combines bounds using Lemmas D.1 and D.2.Source: §D.1 · pp. 43–44
  • The proof chooses η = O(φM^-1n^(2p-5)) and an iteration count of order Ω(n^(12-4p)B^-2φ^-2) to make the training loss at most ε.The passages give separate cases for p ≠ 1/2 and p = 1/2 in the preceding bounds.Source: §D.1 · pp. 45–46

D.2 Proof of Lemma 5.7 … E.2 Proof of Lemma C.2

The proofs establish high-probability control of the SGD loss within a perturbation region and derive auxiliary inequalities used in the analysis. They handle distinct values of p and bound terms in the proof of Lemma C.2.

D.2 Proof of Lemma 5.7

  • For p ≠ 1/2, choosing η=O(φm^-1n^(2p-7)L^-8B^2) upper-bounds the second term on the right-hand side of (D.15); p=1/2 is treated separately.Source: §D.2 · p. 46
  • With probability at least 1-Kδ, the stochastic-iterate loss L_S(W^(k)) is rOp(1) for every k≤K.The proof first establishes the bound for a particular iterate and then applies a union bound.Source: §D.2 · p. 47
  • For iterates satisfying kη≤T, induction keeps W^(k) in the radius-τ perturbation region around W^(0).The proof gives T=rOp(τL^-2M^-1/2n^-1) and also states T=O(τL^-2M^-1/2) for the finite-α0 case.Source: §D.2 · p. 47

E.1 Proof of Lemma C.1

  • For p∈[0,1/2)∪(1/2,1], concavity of f(x)=x^(1-2p)/(1-2p) yields the displayed bound relating a−b to b^-2p.The proof applies the tangent-line inequality for a concave function.Source: §E.1 · p. 48

E.2 Proof of Lemma C.2

  • The Lemma C.2 proof derives a lower bound for Δ^(k) by decomposing it into terms and bounding the components.The derivation invokes Theorem 5.3 and a vector-norm bound; the supplied passages do not expose the final bound's full expression.Source: §E.2 · pp. 48–50

E.3 Proof of Lemma D.1 · E.4 Proof of Lemma D.2 · E.5 Proof of Lemma D.3

These appendices prove Lemmas D.1–D.3 using a proof technique inherited from Lemma C.2, expectation calculations, and separate cases for p = 1/2 and p ≠ 1/2.

E.3 Proof of Lemma D.1

  • Lemma D.1 follows the technique of Lemma C.2, replacing the gradient bound with a stochastic-gradient bound; details are omitted.The proof cites condition (viii) in Theorem 5.3.Source: §E.3 · p. 50

E.4 Proof of Lemma D.2

  • The Lemma D.2 proof reduces its claim to expectation calculations for random variables u1,...,un.Source: §E.4 · p. 50

E.5 Proof of Lemma D.3

  • For p ≠ 1/2, the proof bounds the loss change using (D.4), Lemma D.1, and absolute constants C1 and C2.It then divides by the squared loss and applies Lemma C.1.Source: §E.5 · p. 51
  • By Azuma’s inequality, the stated bound holds with probability at least 1 − δ.Source: §E.5 · p. 51
  • For p = 1/2, the proof derives a loss-change upper bound similar to the other case and uses log(x) ≤ x − 1 to bound the log-loss change.Source: §E.5 · p. 51
  • For p = 1/2, Azuma’s inequality likewise yields a bound holding with probability at least 1 − δ.The supplied passage fragments do not preserve the bound’s full expression.Source: §E.5 · p. 51

Related papers

Loading 1811.08888v3…