PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence Analysis of Two-layer Neural Networks with ReLU Activation

Yuanzhi Li, Yang Yuan

arXiv:1705.09886v2cs.LG

TL;DR

The paper studies how SGD can reliably train neural networks despite limited theoretical guarantees. It analyzes two-layer ReLU networks with identity mappings, proving polynomial-step convergence under Gaussian inputs and standard initialization through a two-phase process, with experiments supporting improved performance over vanilla networks.

  • Problem

    Formal theoretical guarantees explaining how SGD obtains good weights in neural networks remain limited despite their practical success.

  • Method

    The paper analyzes SGD for two-layer ReLU networks augmented with an identity mapping, using a potential function to characterize two convergence phases.

  • Results

    With Gaussian inputs and standard O(1/√d) initialization, SGD converges to the global minimum in polynomially many steps, while experiments report better performance for multilayer identity-mapped networks than vanilla networks.

  • Takeaways & Limitations

    Identity mapping moves initialization into an easier optimization region and supports convergence despite an initially wrong gradient direction.

  • Takeaways & Limitations

    The analysis assumes Gaussian inputs and, with small step size, guarantees sufficient closeness to W* rather than convergence exactly to W*.

Abstract

from arXiv · show

In recent years, stochastic gradient descent (SGD) based techniques has become the standard tools for training neural networks. However, formal theoretical understanding of why SGD can train neural networks in practice is largely missing. In this paper, we make progress on understanding this mystery by providing a convergence analysis for SGD on a rich subset of two-layer feedforward networks with ReLU activations. This subset is characterized by a special structure called "identity mapping". We prove that, if input follows from Gaussian distribution, with standard $O(1/\sqrt{d})$ initialization of the weights, SGD converges to the global minimum in polynomial number of steps. Unlike normal vanilla networks, the "identity mapping" makes our network asymmetric and thus the global minimum is unique. To complement our theory, we are also able to show experimentally that multi-layer networks with this mapping have better performance compared with normal vanilla networks. Our convergence theorem differs from traditional non-convex optimization techniques. We show that SGD converges to optimal in "two phases": In phase I, the gradient points to the wrong direction, however, a potential function $g$ gradually decreases. Then in phase II, SGD enters a nice one point convex region and converges. We also show that the identity mapping is necessary for convergence, as it moves the initial point to a better place for optimization. Experiment verifies our claims.

1 Introduction

The paper addresses the lack of theoretical guarantees for SGD in neural networks by analyzing two-layer ReLU networks with an identity mapping. It proves a two-phase convergence mechanism and reports that identity mappings improve optimization and multilayer performance.

  • Contribution: The paper gives the first convergence analysis of SGD for two-layer feedforward networks with ReLU activations.Prior work could show SGD becoming stuck at saddle points even in simplified settings.
  • Identity mapping: Adding an identity mapping makes the network asymmetric and creates a region near I containing a unique global minimum without saddle points or local minima.The mapping moves standardly initialized weights into this easier optimization region.
  • Experiments: Experiments report that multilayer networks with identity mappings outperform normal vanilla networks, while zero initialization can perform as well as random initialization.The identity mapping itself supplies the asymmetric component in the authors’ explanation.
  • Two-phase convergence: SGD converges in two phases: a potential function g decreases while the gradient may point away from W*, followed by convergence in a one-point convex region.The first phase follows a non-convex path; the second phase approaches the ground truth.
  • Convergence regime: For shallow teacher networks whose weights lie near identity, equally shallow students converge to the global minimum, whereas wrong initialization can cause local-minimum stagnation and underfitting.The paper identifies initialization near identity as the key condition for this result.

2 Preliminaries

The preliminaries define the Gaussian-input two-layer ReLU teacher–student setting, its SGD update, and one-point strong convexity. The analysis uses a potential function to explain how SGD can transition from an initially unfavorable direction into a convergent region.

  • Network and loss: The student and teacher are two-layer networks with column weights W and W∗, trained under ℓ2 loss on Gaussian inputs.The input x is sampled from N(0, I), and the ReLU network and loss are defined through the teacher–student construction.
  • Network and loss: The identity mapping adds e_i to column i of W, making the network asymmetric under column permutations.This structure appears through terms involving e_i + w_i and changes the function when columns are switched.
  • Two-phase analysis: The potential g decreases during Phase I, after which remaining small g places the loss in a one-point strongly convex region for Phase II convergence.The finite-step SGD guarantee additionally assumes bounded iterates, bounded distance from W∗, and a sufficiently small fixed step size.
  • SGD setup: SGD updates W_t using a mini-batch stochastic gradient G_t equal to the population gradient plus zero-mean bounded error.The analysis bounds both spectral and Frobenius norms of the stochastic gradient through G_2 and G_F.
  • Geometric condition: One-point strong convexity requires the negative gradient to have positive alignment with the displacement toward the reference optimum.Unlike ordinary convexity, this condition can hold only relative to one point and still guide successive updates toward W∗.

3 Main Theorem

The main theorem analyzes SGD for the identity-mapped two-layer ReLU network under Gaussian inputs, bounded initialization, and controlled stochastic-gradient error. It proves a two-phase process: the potential first contracts, then SGD converges within a one-point strongly convex region, subject to the stated assumptions and step-size conditions.

  • Phase II: The Phase II guarantee uses η = (1+α) log T/T when T satisfies the theorem’s dimension-, noise-, and confidence-dependent lower bound.The displayed condition involves d, G_F, α, and log T.
  • Assumptions and scope: The result matches standard O(1/√d) initialization in its spectral-norm scaling, but assumes Gaussian inputs and constant spectral norm for W∗.The authors note that Gaussianity can be generalized to rotation-invariant distributions, while the stated practice-oriented initialization discussion also permits large Frobenius norm.
  • Phase I: In Phase I, the potential g decreases geometrically until it is at most 197γ^2, taking at most 1/(16η) steps.After this stage, the theorem states that the iterate remains spectrally bounded and g remains at most 0.1.

4 Overview of the Proofs

The proof explains why SGD requires two phases: the gradient can initially point incorrectly, while a potential function decreases until the loss enters a one-point-convex region. Taylor expansions and geometric bounds then establish convergence despite non-negligible angular errors.

  • Motivation: For two-layer ReLU networks, the gradient may point in the wrong direction, preventing direct application of one-point strong convexity.This motivates analyzing SGD dynamics rather than assuming the loss is one-point strongly convex from initialization.
  • Potential function: The potential function g measures a potentially arbitrary gradient component; when g is sufficiently small, the loss becomes one-point strongly convex.The proof therefore uses g to control when the remaining gradient terms guarantee progress toward W∗.
  • Two-phase convergence: SGD is analyzed in two phases: g decreases during Phase I, then W converges toward W∗ during Phase II while g remains small.Phase I may not reduce the distance to the optimum, but it moves the iterate into the region needed for Phase II.
  • Taylor expansion: The Phase II approximation cannot assume θ_i,j∗≈π/2, because constant spectral norm can keep these angles far from π/2 even near W∗.The formal proof instead uses Taylor expansion and controls higher-order terms.
  • Taylor expansion: A joint Taylor expansion makes the approximation error bounded by showing the relevant difference of cubic inner-product terms tends to zero.This supports lower bounds on the inner product between the negative gradient and W∗−W.
  • Taylor expansion: Combining the Taylor terms shows that L(W) is one-point convex when g is small, completing the bridge from Phase I to convergence in Phase II.Geometric lemmas provide tight bounds for recurring terms in this argument.

5 Experiments

Experiments test identity mappings across deep and shallow networks, supporting both improved performance and the predicted two-phase SGD dynamics.

  • 5.1 Importance of identity mapping: 3.03% lower test error than the vanilla network was achieved by adding a single skip identity mapping to 56-layer CIFAR-10 networks.The single-skip model was also 2.04% from ResNet under otherwise identical settings.
  • 5.2 Global minimum convergence: The global-convergence experiment used Gaussian data and small initial spectral norms for both student and teacher weights.The setup compared ResLink, Vanilla, and a three-block student network against teachers sharing their respective structures.
  • 5.2 Global minimum convergence: ResLink reached zero training and test error in all five trials, while the comparable vanilla network did not converge to W∗.The distance ∥W − W∗∥2 converged to zero only for ResLink.
  • 5.3 Verify the dynamics: After about 15 iterations, the dynamics shifted from a negative to positive inner product as the potential g decreased, while distance to the optimum remained unchanged.This behavior matches the described Phase I dynamics.
  • 5.3 Verify the dynamics: In Phase II, the potential remained small, the inner product stayed positive, and the distance to W∗ slowly decreased.These trajectories match the paper’s Phase II theorem.
  • 5.4 Initialization and expressivity: On MNIST, zero and random initialization produced 1.28% and 1.27% test error, respectively, for the five-block identity-mapping network.Removing the identity mapping made zero initialization ineffective.
  • 5.5 Spectral norm of W∗: For all 45 MNIST class pairs, increasing ∥W∥2 to 0.6 reduced average training error from 34% to 14%.For classes 0 and 1, training error fell from 7% at W = 0 to 1% at ∥W∥2 = 0.6.

6 Discussions

The analysis may extend beyond Gaussian inputs and motivates further work on deeper networks and other non-convex problems.

  • 6 Discussions: The Gaussian-input assumption can be relaxed to nearby covariance distributions, rotation-invariant distributions, and more general distributions with explicitly computable expectations.For N(0, Σ), the stated condition is that ∥Σ − I∥2 is bounded by a small constant.
  • 6 Discussions: Extending the analysis to multiple layers is identified as an open problem, while the two-phase framework may apply to other non-convex problems.The paper presents this as a direction for future work rather than an established result.

A Flowchart of the proofs

The paper organizes its intricate proof into a top-down presentation, supported by a flowchart for navigating the theorem and lemma dependencies.

  • A Flowchart of the proofs: A proof flowchart is included to help readers navigate the long and complicated arguments.The paper also marks intuitive lemmas so time-constrained readers can skip their proofs initially.
  • A Flowchart of the proofs: The main theorems are presented first, followed by the necessary lemmas and then their proofs in later sections.Theorems 3.1, 3.2, and 3.3 appear before lemmas in Sections B–D and proofs in Sections G–I.

B Compute Approximation Matrix

This section approximates the gradient-related matrix terms with Taylor expansions and bounds the resulting approximation error for later convergence arguments.

  • B Compute Approximation Matrix: Taylor series approximate angular and sine terms appearing in the exact gradient expression.The approximations replace angle-related quantities with inner products and quadratic corrections.
  • B Compute Approximation Matrix: The approximation matrix P is decomposed columnwise as P = P1 + P2 + P3.Although P depends on W, the notation suppresses that dependence.
  • B Compute Approximation Matrix: The approximation loss is shown to be negligible for one-point convexity and spectral-norm analysis.This establishes why P can substitute for the exact gradient-related expression in the convergence proof.
  • B Compute Approximation Matrix: When ∥W∥2 and ∥W∗∥2 are at most γ ≤ 1/100, the approximation satisfies a Frobenius-norm inner-product bound below 0.085∥W∗ − W∥2_F.This is the bound stated in Lemma B.2.
  • B Compute Approximation Matrix: Under the same spectral-norm condition, ∥P + ∇L(W)∥2 is bounded by 3.5γ2.This is the spectral-norm control stated in Lemma B.3.

C Phase I: The Decreasing Potential Function

Phase I analyzes SGD while the potential g and weight norms remain controlled, establishing the conditions needed to enter Phase II.

  • C Phase I: The Decreasing Potential Function: The analysis first addresses potentially large initial g and weight norms by tracking their SGD dynamics.When g ≤ 0.1 and the relevant norms are bounded, the loss is one-point convex; Phase I analysis establishes these conditions.
  • C Phase I: The Decreasing Potential Function: The negative gradient is approximated by a structured matrix with error at most 61γ2 when the weight norms are at most γ ≤ 1/100.The approximation also yields the gradient-norm bound ∥∇L(W)∥2 ≤ 6dγ.
  • C Phase I: The Decreasing Potential Function: Geometric bounds control interactions among the perturbed basis vectors ei + wi and ei + w∗i under γ ≤ 1/100.These estimates support the gradient approximation and the subsequent potential-function dynamics.

G.3 Proof for Lemma B.3

The proof bounds the spectral-norm error between the exact gradient and its approximation by decomposing angular and sine approximation errors.

  • G.3 Proof for Lemma B.3: The gradient-approximation error ∆ is decomposed into ∆1 for angular terms and ∆2 for sine terms.The two components are bounded separately before being combined.
  • G.3 Proof for Lemma B.3: The sine component satisfies ∥∆2∥2 ≤ 6γ3 under the same norm condition.The proof reduces the estimate to bounding a diagonal matrix and uses the factor (1+γ)/(1−γ).
  • G.3 Proof for Lemma B.3: Combining the two components gives a spectral-norm approximation loss of less than 61γ2 for −∇L(W).Additional lower-order terms are removed when constructing Q(W) from P(W).
  • G.3 Proof for Lemma B.3: The resulting approximation is used to relate changes in g to the gradient paired with I + W, with Figure 11 providing the projection intuition.This connects the matrix approximation to the potential-function update analyzed in Phase I.

H.5 Proof for Lemma C.5

Lemma C.5 shows that a combined potential-and-error quantity contracts during Phase I, and that g continues decreasing until it is sufficiently small.

  • H.5 Proof for Lemma C.5: If the relevant inequality holds, |g_t| + ∥s_t∥2 decreases by at least the factor 1 − 0.5ηd.This contraction continues while the quantity remains above the stated threshold.
  • H.5 Proof for Lemma C.5: The auxiliary quantity satisfies ∥s_t∥2 ≤ 4.5γ once the combined quantity has contracted sufficiently.This bound is then substituted into the update for |g_t|.
  • H.5 Proof for Lemma C.5: Even after |g_t| + ∥s_t∥2 falls below 4.5γ, |g_t| keeps shrinking until it is below 197γ2.The same contraction factor is used for this final part of Phase I.
  • H.5 Proof for Lemma C.5: With γ = 1/400 and γ0 = 1/8000, reaching the Phase-I threshold requires at most 1/(16η) steps.The estimate follows from geometric decay of |g_t| under the contraction factor.
  • H.5 Proof for Lemma C.5: The proof maintains the weight-norm bound by recursively controlling the evolution of H = W − W∗ and its symmetric and antisymmetric parts.This ensures ∥W_t∥2 remains bounded by γ throughout the Phase-I process.

J Proofs for Section 2

The argument states that g either decreases geometrically or remains controlled by a bounded increase, yielding the Phase-I-to-Phase-II transition.

  • J Proofs for Section 2: When the relevant decrease condition holds, F decreases by a factor of 1 − ηδ at every step.Otherwise, the proof bounds its possible increase before resuming the decay analysis.
  • J Proofs for Section 2: The resulting case analysis bounds the time or decrease behavior needed for the potential to reach the Phase-II regime.The displayed derivation supplies the intermediate inequalities for this conclusion.
Loading 1705.09886v2…