When is a Convolutional Filter Easy To Learn?

Abstract

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.

arXiv commentPublished as a conference paper at ICLR 2018

Cited by in corpus (31)

• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks
• Understanding the Loss Surface of Neural Networks for Binary Classification
• Width Provably Matters in Optimization for Deep Linear Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• A Provably Correct Algorithm for Deep Learning that Actually Works
• Agnostic Learning of a Single Neuron with Gradient Descent
• Directional Pruning of Deep Neural Networks
• The Multilinear Structure of ReLU Networks
• How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
• On the Global Convergence of Training Deep Linear ResNets
• End-to-end Learning of a Convolutional Neural Network via Deep Tensor Decomposition
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlaps
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• Guaranteed Recovery of One-Hidden-Layer Neural Networks via Cross Entropy
• Theory III: Dynamics and Generalization in Deep Networks
• On the Learnability of Deep Random Networks
• Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent
• The Global Optimization Geometry of Shallow Linear Neural Networks
• Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• Structured Directional Pruning via Perturbation Orthogonal Projection
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Recursive Sketches for Modular Deep Learning
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• ReLU Regression with Massart Noise