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 justify our theoretical findings. Deep convolutional neural networks (CNN) have achieved the state-of-the-art performance in many applications such as computer vision BID16 , natural language processing BID3 and reinforcement learning applied in classic games like Go BID31 . Despite the highly non-convex nature of the objective function, simple first-order algorithms like stochastic gradient descent and its variants often train such networks successfully. On the other hand, the success of convolutional neural network remains elusive from an optimization perspective.When the input distribution is not constrained, existing results are mostly negative, such as hardness of learning a 3-node neural network BID0 or a non-overlap convolutional filter BID1 . Recently, BID30 showed learning a simple one-layer fully connected neural network is hard for some specific input distributions.These negative results suggest that, in order to explain the empirical success of SGD for learning neural networks, stronger assumptions on the input distribution are needed. Recently, a line of research BID36 BID1 BID18 BID33 BID39 assumed the input distribution be standard Gaussian N (0, I) and showed (stochastic) gradient descent is able to recover neural networks with ReLU activation in polynomial time.One major issue of these analysis is that they rely on specialized analytic properties of the Gaussian distribution (c.f. Section 1.1) and thus cannot be generalized to the non-Gaussian case, in which real-world distributions fall into. For general input distributions, new techniques are needed.In this paper we consider a simple architecture: a convolution layer, followed by a ReLU activation function, and then average pooling. Formally, we let x ∈ R d be an input sample, e.g., an image, we generate k patches from x, each with size p: Z ∈ R p×k where the i-th column is the i-th patch generated by some known function Z i = Z i (x). For a filter with size 2 and stride 1, Z i (x) is the i-th and (i + 1)-th pixels. Since for convolutional filters, we only need to focus on the patches instead of the input, in the following definitions and theorems, we will refer Z as input and let Z as the distribution of Z: (σ(x ) = max(x, 0) is the ReLU activation function) ( a) (b) (c) Figure 1 : (a) Architecture of the network we are considering. Given input X, we extract its patches {Z i } and send them to a shared weight vector w. The outputs are then sent to ReLU and then summed to yield the final label (and its estimation). (b)-(c ) Two conditions we proposed for convergence. We want the data to be (b ) highly correlated and ( c) concentrated more on the direction aligned with the ground truth vector w * . DISPLAYFORM0 See Figure 1 (a) for a graphical illustration. Such architectures have been used as the first layer of many works in computer vision BID19 BID23 . We address the realizable case, where training data are generated from (1) with some unknown teacher parameter w * under input distribution Z. Consider the 2 loss (w, Z) = 1 2 (f (w, Z) − f (w * , Z)) 2 . We learn by (stochastic) gradient descent, i.e., DISPLAYFORM1 where η t is the step size which may change over time and g(w t ) is a random function where its expectation equals to the population gradient E [g(w)] = E Z∼Z [∇ (w, Z)] . The goal of our analysis is to understand the conditions where w → w * , if w is optimized under (stochastic) gradient descent.In this setup, our main contributions are as follows:• Learnability of Filters: We show if the input patches are highly correlated (Section 3), i.e., θ (Z i , Z j ) ≤ ρ for some small ρ > 0, then gradient descent and stochastic gradient descent with random initialization recovers the filter in polynomial time. 1 Furthermore, strong correlations imply faster convergence. To the best of our knowledge, this is the first recovery guarantee of randomly initialized gradient-based algorithms for learning filters (even for the simplest one-layer one-neuron network) on non-Gaussian input distribution, answering an open problem in BID36 .• Distribution-Aware Convergence Rate. We formally establish the connection between the smoothness of the input distribution and the convergence rate for filter weights recovery where the smoothness in our paper is defined as the ratio between the largest and the least eigenvalues of the second moment of the activation region (Section 2). We show that a smoother input distribution leads to faster convergence, and Gaussian distribution is a special case that leads to the tightest bound. This theoretical finding also justifies the twostage learning rate strategy proposed by BID12 BID35 if the step size is allowed to change over time. In this paper we provide the first recovery guarantee of (stochastic) gradient descent algorithm with random initialization for learning a convolution filter when the input distribution is not Gaussian. Our analyses only used the definition of ReLU and some mild structural assumptions on the input distribution. Here we list some future directions.One possibility is to extend our result to deeper and wider architectures. Even for two-layer fullyconnected network, the convergence of (stochastic) gradient descent with random initialization is not known. Existing results either requires sufficiently good initialization BID39 relies on special architecture BID18 . However, we believe the insights from this paper is helpful to understand the behaviors of gradient-based algorithms in these settings.Another direction is to consider the agnostic setting, where the label is not equal to the output of a neural network. This will lead to different dynamics of (stochastic) gradient descent and we may need to analyze the robustness of the optimization procedures. This problem is also related to the expressiveness of the neural network BID25 where if the underlying function is not equal bot is close to a neural network. We believe our analysis can be extend to this setting.
We prove randomly initialized (stochastic) gradient descent learns a convolutional filter in polynomial time. Studies the problem of learning a single convolutional filter using SGD and shows that under certain conditions, SGD learns a single convolutional filter. This paper extends the Gaussian distribution assumption to a more general angular smoothness assumption, which covers a wider family of input distributions