PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima

Simon S. Du, Jason D. Lee, Yuandong Tian, Barnabas Poczos, Aarti Singh

arXiv:1712.00779v2cs.LGcs.AIcs.CVmath.OCstat.ML

TL;DR

The paper studies whether randomly initialized gradient descent can learn both layers of a one-hidden-layer convolutional ReLU network under Gaussian inputs. It analyzes weight-normalized gradient descent and proves recovery with high or constant probability despite a spurious local minimum, while characterizing two-phase dynamics.

  • Problem

    The paper asks whether randomly initialized gradient descent can learn neural networks with multiple unknown layers, beyond prior results with one unknown layer.

  • Method

    The paper analyzes weight-normalized, randomly initialized gradient descent through attraction basins for the global and spurious minima.

  • Results

    Gradient descent converges to the teacher’s parameters with high probability, while randomly initialized local search can also reach a spurious local minimum.

  • Takeaways & Limitations

    The results show that randomly initialized local search can find a global minimum even when spurious local minima exist, with dynamics exhibiting two convergence phases.

  • Takeaways & Limitations

    The analysis focuses on population loss with Gaussian input, while extending the results to empirical loss and beyond rotationally invariant inputs remains open.

Abstract

from arXiv · show

We consider the problem of learning a one-hidden-layer neural network with non-overlapping convolutional layer and ReLU activation, i.e., $f(\mathbf{Z}, \mathbf{w}, \mathbf{a}) = \sum_j a_jσ(\mathbf{w}^T\mathbf{Z}_j)$, in which both the convolutional weights $\mathbf{w}$ and the output weights $\mathbf{a}$ are parameters to be learned. When the labels are the outputs from a teacher network of the same architecture with fixed weights $(\mathbf{w}^*, \mathbf{a}^*)$, we prove that with Gaussian input $\mathbf{Z}$, there is a spurious local minimizer. Surprisingly, in the presence of the spurious local minimizer, gradient descent with weight normalization from randomly initialized weights can still be proven to recover the true parameters with constant probability, which can be boosted to probability $1$ with multiple restarts. We also show that with constant probability, the same procedure could also converge to the spurious local minimum, showing that the local minimum plays a non-trivial role in the dynamics of gradient descent. Furthermore, a quantitative analysis shows that the gradient descent dynamics has two phases: it starts off slow, but converges much faster after several iterations.

1. Introduction

The paper asks whether randomly initialized gradient descent can learn a one-hidden-layer convolutional ReLU network when both convolutional and output weights are unknown. It proves recovery despite a spurious local minimum and characterizes two-phase convergence dynamics.

  • Problem and setting: The study targets a non-linear convolutional network with two unknown layers, extending prior analyses that fixed the output weights.The network uses a shared filter, non-overlapping patches, and ReLU activation.
  • Main results: Under a specific random initialization, gradient descent converges to the teacher’s parameters with high probability, and additional trials can boost the success rate.The result is stated for the weight-normalized parameterization and the teacher network’s parameters.
  • Main results: The objective also has a spurious local minimum, and the same initialization scheme can direct gradient descent to it from a suitable sign configuration.This provides a counterexample to analyses that rely on every local minimum being global.
  • Main results: Randomly initialized local search can find a global minimum even in the presence of spurious local minima.The paper frames this as a central phenomenon of the optimization dynamics.
  • Dynamics: The dynamics has two phases: prediction error decreases slowly initially, then drops quickly after the alignment signal strengthens.The slow regime lasts around the first 50 iterations in Figure 1b.
  • Technical approach: The analysis characterizes attraction basins for the global and spurious minima to explain how initialization determines the optimization outcome.A specific initialization distribution is designed so the global-minimum basin has probability bounded below by an absolute constant.

2. Related Works

Prior work established convergence guarantees for restricted neural-network architectures or favorable objective landscapes, but did not explain gradient-based learning when multiple layers are unknown. This paper addresses that gap while providing a polynomial convergence guarantee for vanilla gradient descent.

  • Learning guarantees: Earlier algorithms could learn neural networks in polynomial time under additional assumptions, but were specialized to particular architectures and did not explain practical gradient-based optimization.The cited approaches include tensor, dictionary, matrix, and factorization methods.
  • Gradient descent with Gaussian inputs: For Gaussian inputs, prior analyses showed gradient descent can recover weights in one-layer or otherwise restricted neural-network models.These results include population and empirical projected gradient descent guarantees.
  • Objective landscapes: Many landscape results guarantee global optimization when all local minima are global and non-global critical points have suitable curvature.These conditions support polynomial-time local-search guarantees in several non-neural problems.
  • Contribution: The paper gives a polynomial convergence guarantee for vanilla gradient descent, contrasting with prior statements that lacked rates or established exponential-time lower bounds.The guarantee concerns the paper’s neural-network setting.

3. Preliminaries

The preliminaries define the parameterization, Gaussian non-overlapping-patch setting, and population-loss analysis used to study gradient descent. Rotational invariance yields explicit loss and gradient formulas whose dependence on the output weights affects convergence.

  • Notation: The notation includes iteration parameters w_t and a_t, teacher weights w* and a*, angles between vectors, and the unit sphere S^{p−1}.The Euclidean norm is denoted by ∥·∥_2.
  • Input and loss: Each patch Z_i is modeled with independent Gaussian entries, enabling an explicit formula for the population loss through rotational invariance and Gaussian polar decomposition.The stated Gaussian entries have mean 0 and variance 1.
  • Population formulas: The loss formula depends on the angle φ between the learned filter and teacher filter through g(φ) = (π − φ) cos φ + sin φ.The angle is defined as φ = θ(v, w*).
  • Population formulas: The expected gradients of the filter and output weights also have analytical forms under the Gaussian input model.These formulas are used to analyze the gradient updates.
  • Coupled layers: When output weights are learnable, the filter gradient depends on a^T a*, which helps determine whether optimization approaches the global or local minimum.This dependence is absent when the second layer is fixed.

4. Main Result

The paper proves convergence guarantees for randomly initialized gradient descent despite spurious local minima, while also identifying conditions under which optimization can reach either global or spurious minima.

  • Theorem 4.1: The convergence has two phases: a slow initial regime followed by faster convergence after the signal becomes stronger.The first phase is tied to small initial signal, while the second begins after several iterations when the signal increases.
  • Theorem 4.1: Theorem 4.1 establishes convergence to the global minimum under specified initialization conditions.The required initialization constraints and associated quantitative expressions are partially garbled in the supplied passages.
  • Theorem 4.2: Random initialization with four sign combinations yields a pair that enables gradient descent to find the global minimum in polynomial time.Theorem 4.2 uses random vectors and tests all four sign combinations; its phase-I step size and iteration count are polynomially bounded.
  • Scope and assumptions: The Gaussian input assumption is not necessarily true in practice; the result extends to rotation-invariant distributions, while more general assumptions remain open.The paper specifically identifies structural distributional conditions beyond rotation invariance as a challenging open problem.
  • Theorem 4.3: Under additional conditions on the underlying truth, another sign combination can make gradient descent converge to a spurious local minimum.This contrasts with Theorem 4.1, which requires no assumption on the underlying truth a*.

5. Proof Sketch

The proof analyzes stationary points, preserves geometric invariants, and tracks the angle between the learned and true filters to explain convergence and its two-phase rate.

  • 5.1. Qualitative Analysis of Convergence: The analysis characterizes attraction basins for the disjoint global and local minima to study convergence in the presence of local minima.The proof treats the basin associated with each minimum as the central object governing gradient-descent behavior.
  • 5.1. Qualitative Analysis of Convergence: Stationary-point analysis shows that convergence with nonorthogonal output weights leads to either a global optimum or a local minimum.This conclusion follows from the stated stationary-point lemma when a⊤a* ≠ 0 and the learned filter has finite norm.
  • 5.1. Qualitative Analysis of Convergence: A positive inner product between a_t and a* decreases the angle between v and w*, whereas a negative inner product increases it.The projection structure in the gradient update makes the sign of this inner product decisive for the filter-direction dynamics.
  • 5.1. Qualitative Analysis of Convergence: Maintaining positive second-layer signal and an angle below π/2 yields invariants that support convergence to the global minimum.The proof tracks positivity of (a_t)⊤a* and related second-layer quantities by induction.
  • 5.2. Quantitative Analysis of Two Phase Phenomenon: The quantity sin^2 φ_t shrinks geometrically, providing the quantitative control used to analyze the first-layer direction.Here φ_t is the angle between v_t and v*; the weight-normalized dynamics depend on this angular quantity.
  • 5.2. Quantitative Analysis of Two Phase Phenomenon: Initially, cos φ_t and λ_t are small, so prediction error decreases slowly; after cos φ_t becomes Ω(1), convergence enters a faster phase.The transition occurs after a number of iterations depending on the step size, initial angle, and initial signal.
  • 5.2. Quantitative Analysis of Two Phase Phenomenon: In phase II, the convergence rate is much faster, followed by contraction of the output-weight error toward O(ε∥a*∥2).The supplied passages state that later lemmas establish this output-weight accuracy after additional iterations.

6. Experiments

The experiments illustrate two-phase convergence and examine how initialization conditions affect convergence to global versus spurious local minima. The observed dynamics are initially slow and later substantially faster.

  • Probability of Converging to the Global Minimum: 5000 random initializations are run for each tested setting to estimate the probability of converging to the global minimum.The experiments set p = 6 and vary k and (1⊤a∗)^2/2.
  • Probability of Converging to the Global Minimum: When (1⊤a∗)^2/2 is sufficiently small, randomly initialized gradient descent converges to the spurious local minimum with constant probability.Table 1 empirically verifies the importance of this assumption.
  • Multi-phase Phenomenon: After ∼200 iterations, the monitored quantities converge at much faster linear rates than during the initial slow period.The quantities include the angle between v and w∗, ∥a − a∗∥, 1⊤a − 1⊤a∗, and prediction error.
  • Probability of Converging to the Global Minimum: For fixed k, increasing (1⊤a∗)^2/2 increases the probability of converging to the global minimum.
  • Probability of Converging to the Global Minimum: For fixed (1⊤a∗)^2/2, increasing k decreases the probability of converging to the global minimum.The quantitative relationship between success probability and the second-layer dimension remains an open problem.

7. Conclusion and Future Works

The paper establishes a polynomial convergence guarantee for randomly initialized gradient descent in a one-hidden-layer convolutional network, while identifying input and architectural settings that remain open for extension.

  • Conclusion: The paper proves the first polynomial convergence guarantee for randomly initialized gradient descent learning a one-hidden-layer convolutional neural network.
  • Conclusion: Randomly initialized local search can converge either to a global minimum or to a spurious local minimum.The paper gives a quantitative characterization of gradient descent dynamics and reports experiments verifying the theoretical findings.
  • Future Works: The analysis focuses on population loss with Gaussian input rather than the empirical loss used in practice.Concentration results are identified as useful for generalizing the analysis to the empirical version.
  • Future Works: Extending the analysis beyond rotationally invariant input distributions is presented as a more challenging question.
  • Future Works: Generalizing the result to deeper and wider architectures, including multiple kernels, remains an open direction.The paper also identifies one-hidden-layer fully connected networks as a target for generalization.

A. Proofs of Section 3

The appendix derives expected gradients and supporting Gaussian identities used in the proofs for the population loss and gradient dynamics.

  • Proofs of Section 3: The proof first expands the loss function directly and computes expectations of the relevant gradient expressions separately.
  • Proofs of Section 3: The derivation computes the matrix terms A(w) and B(w,w∗), then combines them with the normalized relation w = v/∥v∥2 to obtain the stated result.
  • Proofs of Section 3: The expected gradient of a is obtained by taking expectations and substituting the formulas for A(w) and B(w,w∗).The resulting formula is checked against a prior formula when a = a∗ = 1.
  • Proofs of Section 3: Lemma A.1 supplies identities for Gaussian vectors w and w∗ with angle φ, including moments used in the gradient calculations.
  • Proofs of Section 3: The Gaussian identities are proved using orthonormal bases, independence, half-Gaussian moments, and a polar representation in the plane spanned by w and w∗.

B. Proofs of Qualitative Convergence Results

The proofs analyze normalized gradient dynamics through angle and output-weight inner-product recurrences, establishing monotonic alignment and the Phase I convergence behavior.

  • Qualitative Convergence: When a⊤a∗ > 0, the gradient update decreases the angle between v and w∗.The gradient is aligned with w∗ after projection onto the complement space of v.
  • Qualitative Convergence: The output-weight inner product a⊤a∗ is uniformly lower bounded, and the proof also derives an iteration bound for making it Θ.
  • Qualitative Convergence: The analysis studies the dynamics of sin^2 φt and bounds the output-weight inner product throughout the iterations.
  • Phase I: The Phase I proof uses joint induction to establish convergence of φt together with a uniform upper bound on ∥vt∥2.The gradient of v is orthogonal to v, yielding a simple norm dynamic used in the induction.
  • Phase I: A uniform upper bound on ∥v∥2 and φt ≤ π/2 provide a lower bound on λt used in the convergence argument.

C.3. Analysis of Phase II

The section analyzes Phase II convergence using normalized teacher weights, lower bounds on alignment-related quantities, and auxiliary lemmas that control the loss and output weights.

  • Phase II convergence: The analysis combines lower bounds on λ_t and cos φ_t with Theorem 5.5 to establish convergence after an iteration-dependent bound.The cited passages state that cos φ_t is monotonically increasing and remains Ω(1), while λ_t also has an Ω(·) lower bound.
  • Phase II convergence: Auxiliary Lemmas C.4–C.6 are used to complete the convergence argument and obtain the desired result after appropriately rescaling ϵ.The proof invokes Lemmas C.4, C.5, and C.6 before applying the rescaling.
  • Assumptions: Phase II assumes, without loss of generality, that the teacher convolutional weight has unit norm.This uses the positive homogeneity property of the model.
  • Auxiliary lemmas: The output-weight dynamics preserve the relevant ordering and imply that 1^⊤a*−1^⊤a_t is at most 2ϵ∥a*∥2.The proof assumes 1^⊤a*>0; the opposite case is stated to be analogous.
  • Auxiliary lemmas: The proof separately analyzes the inner product and squared gradient norm, obtaining a bound of Cϵ∥a*∥2 after rescaling ϵ.These steps provide the remaining control needed for the stated result.
  • Auxiliary lemmas: Lemma C.6 bounds the population loss by Cϵ∥a*∥2 when the angular quantity π−g(φ) and normalized output-weight error are at most ϵ.The bound follows by substituting these assumptions into Theorem 3.1.
  • Supporting theorem: Theorem 4.2 relies on sphere and ball symmetry, a direct application of Hardt and Price’s Lemma 2.5, and an initialization-based argument involving a0.The proof also uses Hölder’s inequality in an intermediate bound.

E. Proofs of Converging to Spurious Local Minimum

The proof of convergence to the spurious local minimum tracks a trajectory toward −w* while maintaining a negative output-weight inner product and increasing angular quantity.

  • Proof strategy: The proof targets convergence toward −w*, assuming without loss of generality that ∥w*∥2=1.This distinguishes the argument from the proof of Theorem 4.1.
  • Invariants: A key invariant is a^⊤a*<0, which the proof maintains alongside the trajectory’s angular behavior.The negative inner product is explicitly identified as necessary for this theorem.
  • Invariants: The initialization condition and induction establish the needed norm relation and imply that φ_t is increasing.The proof uses the induction hypothesis to propagate this behavior across iterations.
  • Dynamics: The dynamics of (a_t)^⊤a* are bounded using induction hypotheses on both the output-weight inner product and φ_t.These inequalities preserve the trajectory conditions used by the proof.
  • Limit: When gradient descent converges, Lemma 5.1 implies θ(v,w*)=π and determines the limiting output weights.The supplied passage states this conclusion at the end of the proof.
Loading 1712.00779v2…