PaperlayerView exact revision on arXiv

Source-linked AI summary

When is a Convolutional Filter Easy To Learn?

Simon S. Du, Jason D. Lee, Yuandong Tian

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

TL;DR

The paper asks when gradient-based methods can learn a ReLU convolutional filter beyond Gaussian inputs. It analyzes recovery with random initialization under patch-correlation and distribution-smoothness conditions, showing polynomial-time recovery and a convergence-rate connection to those conditions. The theory also supports a two-stage learning-rate strategy.

  • Problem

    Prior convergence analyses for ReLU networks rely on Gaussian-specific properties that do not generalize to non-Gaussian input distributions.

    Source: §1 · p. 1

  • Method

    The paper analyzes gradient descent and stochastic gradient descent for a ReLU convolutional filter using only ReLU's definition and structural assumptions on the input distribution.

    Source: §1 · pp. 1–2

  • Results

    With highly correlated patches, randomly initialized gradient descent and stochastic gradient descent recover the filter in polynomial time, with convergence depending on patch closeness and input-distribution smoothness.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The convergence analysis also supports a two-stage learning-rate strategy when the step size can change over time.

    Source: §1 · p. 2

    The guarantees address the analyzed convolutional-filter setting; extending them to deeper and wider architectures remains an open direction.

    Source: §5 · p. 8

Abstract

from arXiv · show

We analyze the convergence of (stochastic) gradient descent algorithm for learning a convolutional filter with Rectified Linear Unit (ReLU) activation function. Our analysis does not rely on any specific form of the input distribution and our proofs only use the definition of ReLU, in contrast with previous works that are restricted to standard Gaussian input. We show that (stochastic) gradient descent with random initialization can learn the convolutional filter in polynomial time and the convergence rate depends on the smoothness of the input distribution and the closeness of patches. To the best of our knowledge, this is the first recovery guarantee of gradient-based algorithms for convolutional filter on non-Gaussian input distributions. Our theory also justifies the two-stage learning rate strategy in deep neural networks. While our focus is theoretical, we also present experiments that illustrate our theoretical findings.

1 INTRODUCTION

The paper studies when gradient descent can recover a ReLU convolutional filter, addressing the gap between practical training success and limited optimization explanations for general input distributions. It gives recovery conditions based on patch correlation and input-distribution smoothness, and relates smoothness to convergence speed.

1 INTRODUCTION

  • The study targets the optimization gap behind successful first-order training of non-convex convolutional networks, especially for non-Gaussian inputs.The model applies a shared filter to input patches, followed by ReLU and average pooling.Source: §1 · p. 1

1.1 RELATED WORKS

  • Prior work includes hardness results for unconstrained inputs, while recovery analyses often assume Gaussian inputs (Tian, 2017); their specialized tools do not generalize to arbitrary distributions.The paper instead uses only the definition of ReLU and weak smoothness assumptions.Source: §1 · p. 1, §1.1 · p. 3

1 INTRODUCTION

  • The analysis asks when gradient descent approaches the unknown teacher filter under a realizable squared-loss setup.Training uses gradient updates with a possibly time-varying step size and a stochastic gradient whose expectation is the population gradient.Source: §1 · p. 2
  • With highly correlated patches, randomly initialized gradient descent and stochastic gradient descent recover the filter in polynomial time; stronger correlations imply faster convergence.The analysis also links smoother input distributions to faster convergence and identifies Gaussian input as yielding the tightest bound; it supports a two-stage learning-rate strategy.Source: §1 · p. 2

1.2 ORGANIZATION

  • The paper analyzes a one-layer one-neuron model, then convolutional-filter learning, followed by empirical illustrations and conclusions.Most detailed proofs are placed in the Appendix.Source: §1.2 · p. 3

1.3 NOTATIONS

  • The setup assumes bounded gradient norms, a condition satisfied when patches, weights, and noise are bounded; gradient descent is not guaranteed to reach a local minimum in polynomial time.The notation section defines Euclidean and eigenvalue conventions and uses standard Big-O and Big-Theta notation.Source: §1.3 · pp. 3–4

2 WARM UP: ANALYZING ONE-LAYER ONE-NEURON MODEL

The one-neuron warm-up establishes convergence under input non-degeneracy and a suitable initialization, then relates iteration complexity to distribution smoothness. Its rate analysis also supports a two-stage learning-rate strategy.

2 WARM UP: ANALYZING ONE-LAYER ONE-NEURON MODEL

  • Gradient descent recovers w∗ when the input satisfies the stated non-degeneracy condition and the initialization has loss below ℓ(0).Degenerate input may be supported on a low-dimensional space; the initialization condition avoids convergence to w = 0, where the gradient is undefined.Source: §2 · p. 4

2.1 CONVERGENCE RATE OF ONE-LAYER ONE-NEURON MODEL

  • Smoother input distributions require fewer iterations: similar γ(φ) and L(φ), with small β, reduce the stated iteration bound.If L(φ) or β is much larger than γ(φ), more iterations are needed.Source: §2.1 · p. 5
  • The rate analysis justifies a two-stage learning rate: use a small rate initially, then a larger rate as the angle to w∗ decreases.The cited strategy is associated with He et al. (2016) and Szegedy et al. (2017).Source: §2.1 · p. 5

3 MAIN RESULTS FOR LEARNING A CONVOLUTIONAL FILTER

The convolutional-filter analysis gives gradient-descent and stochastic-gradient-descent recovery guarantees under conditions involving input smoothness and cross-patch interaction. It identifies close patches and low probability mass near the decision boundary as a sufficient example, and shows that random initialization can yield a good starting point with constant probability.

3 MAIN RESULTS FOR LEARNING A CONVOLUTIONAL FILTER

  • Cross-patch interactions affect convergence because patches can occupy different activation regions, and the analysis assumes their cross-covariance grows smoothly with angle.The authors relate small Lcross to patches being very similar.Source: §3 · p. 6
  • When γ(φ0) > 6Lcross, the convolutional-filter result gives linear convergence; the SGD theorem also provides an iteration guarantee for recovery.The stated gradient-descent theorem additionally assumes ∥w0 − w∗∥2 < ∥w∗∥2.Source: §3 · pp. 6–7

3.1 WHAT DISTRIBUTION IS EASY FOR SGD TO LEARN A CONVOLUTIONAL FILTER?

  • Close patches and low probability mass near the decision boundary provide an example satisfying the condition for the convolutional-filter theorem.The passage identifies these as the two conditions in its example.Source: §3.1 · p. 7

3.2 THE POWER OF RANDOM INITIALIZATION

  • Uniform random initialization yields a good initialization with constant probability, and random restarts can raise success probability arbitrarily close to 1.For the convolutional-filter case, the stated initialization condition is stronger than for the one-neuron model.Source: §3.2 · pp. 7–8

4 EXPERIMENTS

The simulations examine how input smoothness, patch similarity, and initialization relate to SGD convergence. On MNIST, learned filters can have near-zero loss without exactly matching the teacher filter.

4 EXPERIMENTS

  • As σ increases, the input distribution becomes smoother and closer to rotation-invariant, and Figure 3a verifies the predicted convergence behavior.The experiment fixes initialization and step size; the passage says L(φ)/γ(φ) and β become smaller as σ grows.Source: §4 · p. 8
  • Smaller variance between patches produces faster convergence, matching Theorem 3.1.The experiment varies the angles of unit-norm patches around a reference patch.Source: §4 · p. 8
  • On MNIST, better initializations yield faster SGD convergence, while learned filters show patterns similar to the true filters.For these experiments, the authors report relative loss because SGD often reaches near-zero loss without exact filter recovery; they suggest the data lie approximately on a low-dimensional manifold.Source: §4 · p. 8

5 CONCLUSIONS AND FUTURE WORKS

The paper presents a random-initialization recovery guarantee for convolutional filters with non-Gaussian inputs. It identifies deeper or wider architectures and agnostic labels as directions for further work.

5 CONCLUSIONS AND FUTURE WORKS

  • The paper provides a random-initialization recovery guarantee for gradient descent on convolutional filters with non-Gaussian inputs.The analysis uses the definition of ReLU and mild structural assumptions on the input distribution.Source: §5 · p. 8
  • Extending the result to deeper and wider architectures remains an open direction; even two-layer fully connected networks lack a known random-initialization convergence result in the discussed setting.The cited existing results require sufficiently good initialization or a special architecture.Source: §5 · pp. 8, 10
  • The authors identify agnostic learning, where labels need not equal a neural network's output, as another direction for studying different SGD dynamics and robustness.They also connect this setting to neural-network expressiveness.Source: §5 · p. 10

A.1 PROOFS OF THE THEOREM IN SECTION 2

The appendix proofs use distributional assumptions to rule out nonoptimal critical points in the one-neuron analysis. They also establish a special parameter value for rotationally invariant inputs.

A.1 PROOFS OF THE THEOREM IN SECTION 2

  • Under the stated input-distribution assumptions, a critical point other than w* leads to a contradiction, so the proof concludes w = w*.The argument treats angles distinct from π and the antiparallel case separately.Source: §A.1 · p. 13
  • The proof of Theorem 2.2 uses the observation that iterates within the specified distance of w* satisfy an angle bound, then applies the gradient-descent dynamics.The passage defines θ(w_t, w*) = θ_t and states θ_t ≤ φ_t.Source: §A.1 · p. 13
  • For any unit-norm rotationally invariant input distribution, β equals 1.The appendix states this as Theorem A.1.Source: §A.1 · p. 14

A.2 PROOFS OF THEOREMS IN SECTION 3

The appendix develops the convolutional-filter convergence proofs by controlling the iterates near w* and then deriving rates. It also bounds conditions tied to patch closeness and random initialization.

A.2 PROOFS OF THEOREMS IN SECTION 3

  • Theorem 3.1's proof expands the gradient and bounds its interaction with w − w* using the defined regions and Lcross.The displayed proof outline then combines the bounds with gradient-descent dynamics and the step-size choice.Source: §A.2 · pp. 14–16
  • Theorem 3.2's proof first keeps the iterates in a neighborhood of w* with high probability, then derives the convergence rate under step-size and horizon conditions.The cited conditions include a step-size inequality and a probability guarantee for all iterates through T.Source: §A.2 · p. 16
  • The SGD proof uses a supermartingale argument and Azuma-Hoeffding to bound deviations while controlling whether iterates leave the region.The proof also uses a union bound and Markov's inequality when bounding failure probability.Source: §A.2 · pp. 17–18
  • The appendix derives bounds involving patch closeness and Lcross, and separately optimizes a lower bound on random-initialization failure probability.The closeness argument uses unit-norm patches and the law of cosines; the initialization argument chooses rinit = cos(φ*) ||w*||2 to maximize the bound.Source: §A.2 · p. 19

B ADDITIONAL EXPERIMENTAL RESULTS

The experiments examine loss along linear interpolations between the learned filter and the ground-truth filter, finding very low loss across interpolation ratios.

B ADDITIONAL EXPERIMENTAL RESULTS

Loading 1709.06129v2…