When is a Convolutional Filter Easy To Learn?

By Simon Shaolei Du, Jason D. Lee, Yuandong Tian. 2017

131 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “As discussed in Section 1, a popular approach is to show that the objective landscape admits the properties of no poor local minima and strict saddle, which, by Ge et al. (2015); Lee et al. (2016); Panageas and Piliouras (2017), ensure convergence to global minimum.”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “A series of papers made strong assumptions on input distribution as well as realizability of labels, and showed global convergence of (stochastic) gradient descent for some shallow neural networks (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Du et al., 2017a,b; Li & Yuan, 2017).”
Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “Based on these assumptions, one can obtain global convergence of gradient descent for some shallow neural networks [Tian, 2017, Soltanolkotabi, 2017, Brutzkus and Globerson, 2017, Du et al., 2018a, Li and Yuan, 2017, Du et al., 2017b].”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “One-hidden-layer neural networks with ground truth parameters Recently a series of work (Tian, 2017; Brutzkus and Globerson, 2017; Li and Yuan, 2017; Du et al., 2017a,b; Zhang et al., 2018) study a speciﬁc class of shallow two-layer (one-hidden-layer) neural networks, whose training data are…”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, background): “Other works have studied generalization of neural networks in a model recovery setting, where assumptions are made on the underlying model and the input distribution (Brutzkus & Globerson, 2017; Zhong et al., 2017; Li & Yuan, 2017; Du et al., 2017; Tian, 2017).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, background): “However, extending to more general distributional assumption, e.g., structural conditions used in [Du et al., 2017b] remains a challenging open problem.”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, methodology): “A line of research focused on analyzing gradient descent dynamics for (convolutional) neural networks with one or two unknown layers [Tian, 2017, Brutzkus and Globerson, 2017, Du et al., 2017a,b, Zhong et al., 2017, Li and Yuan, 2017, Ma et al., 2017, Brutzkus et al., 2017].”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, methodology): “Following Du et al. [2018b], Wu et al. [2019], we make the following assumption on the data.”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, methodology): “Focusing on gradient-based algorithms, a line of research (Tian, 2017; Brutzkus and Globerson, 2017; Zhong et al., 2017a;b; Li and Yuan, 2017; Du et al., 2017b;c) analyzed the behavior of (stochastic) gradient descent with a structural assumption on the input distribution.”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “Assumption 4.1 is widely made in most existing work on over-parameterized neural networks (Li and Liang, 2018; Allen-Zhu et al., 2018b; Du et al., 2017b, 2018b).”
The loss surface and expressivity of deep convolutional neural networks (2017, background): “…2016; Haeffele & Vidal, 2015; Gautier et al., 2016; Brutzkus & Globerson, 2017; Soltanolkotabi, 2017; Soudry & Hoffer, 2017; Goel & Klivans, 2017; Du et al., 2017; Zhong et al., 2017; Tian, 2017; Li & Yuan, 2017) in order to identify conditions under which one can guarantee that local search…”
Learning One-hidden-layer ReLU Networks via Gradient Descent (2018, methodology): “Du et al. (2017b) further studied the problem of learning the one-hidden-layer ReLU based convolutional neural network in the no-overlap patch setting.”
Optimization Landscape and Expressivity of Deep CNNs (2017, background): “ical results have been recently developed (Andoni et al., 2014; Sedghi & Anandkumar, 2015; Janzamin et al., 2016; Haeffele & Vidal, 2017; Gautier et al., 2016; Brutzkus & Globerson, 2017; Soltanolkotabi, 2017; Zhong et al., 2017; Tian, 2017; Du et al., 2018) in order to identify conditions under whi”
Gradient descent optimizes over-parameterized deep ReLU networks (2019, background): “One-hidden-layer neural networks with ground truth parameters Recently a series of work (Tian 2017; Brutzkus and Globerson 2017; Li and Yuan 2017; Du et al. 2017; Zhang et al. 2018) studied a specific class of shallow two-layer (one-hidden-layer) neural networks,whose training data are generated by ”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “…the objective function is smooth and satisﬁes (1) all local minima are global and (2) for every saddle point, there exists a negative curvature, then the noise-injected (stochastic) gradient descent [Jin et al., 2017, Ge et al., 2015, Du et al., 2017a] can ﬁnd a global minimum in polynomial time.”
An Improved Analysis of Training Over-parameterized Deep Neural Networks (2019, background): “To better understand the training of neural networks, there is a line of research (Tian, 2017; Brutzkus and Globerson, 2017; Du et al., 2017; Li and Yuan, 2017; Zhong et al., 2017; Du and Lee, 2018; Zhang et al., 2018) studying two-layer (i.”
A Provably Correct Algorithm for Deep Learning that Actually Works (2018, background): “The work of [6] extends the results in [3], showing recovery of convolutional kernels without assuming Gaussian distribution, but is still limited to the regime of shallow two-layer network.”