We propose a new algorithm to learn a one-hidden-layer convolutional neural network where both the convolutional weights and the outputs weights are parameters to be learned. Our algorithm works for a general class of (potentially overlapping) patches, including commonly used structures for computer vision tasks. Our algorithm draws ideas from (1) isotonic regression for learning neural networks and (2) landscape analysis of non-convex matrix factorization problems. We believe these findings may inspire further development in designing provable algorithms for learning neural networks and other complex models. While our focus is theoretical, we also present experiments that illustrate our theoretical findings. Giving provably efficient algorithms for learning neural networks is a core challenge in machine learning theory. The case of convolutional architectures has recently attracted much interest due to their many practical applications. Recently BID2 showed that distributionfree learning of one simple non-overlapping convolutional filter is NP-hard. A natural open question is whether we can design provably efficient algorithms to learn convolutional neural networks under mild assumptions.We consider a convolutional neural network of the form f px, w, aq " k ÿ j"1 a j σ`w J P j x˘(1)where w P R r is a shared convolutional filter, a P R k is the second linear layer and P j " r 0 lo omo on pj´1qs I lo omo on r 0 lo omo on d´pj´1qs`r s P R rˆd selects the ppj´1qs`1q-th to ppj´1qs`rq-th coordinates of x with stride s and σ p¨q is the activation function. Note here that both w and a are unknown vectors to be learned and there may be overlapping patches because the stride size s may be smaller than the filter size r.Our Contributions We give the first efficient algorithm that can provably learn a convolutional neural network with two unknown layers with commonly used overlapping patches. Our main result is the following theorem. Theorem 1.1 (Main Theorem (Informal)). Suppose s ě t r 2 u`1 and the marginal distribution is symmetric and isotropic. Then the convolutional neural network defined in equation 1 with piecewise linear activation functions is learnable in polynomial time.We refer readers to Theorem 3.1 for the precise statement.Technical Insights Our algorithm is a novel combination of the algorithm for isotonic regression and the landscape analysis of non-convex problems. First, inspired by recent work on isotonic regression, we extend the idea in BID13 to reduce learning a CNN with piecewise linear activation to learning a convolutional neural network with linear activation (c.f. Section 4). Second, we show learning a linear convolutional filter can be reduced to a non-convex matrix factorization problem which admits a provably efficient algorithm based on non-convex geometry BID8 . Third, in analyzing our algorithm, we present a robust analysis of Convotron algorithm proposed by BID13 , in which we draw connections to the spectral properties of Toeplitz matrices. We believe these ideas may inspire further development in designing provable learning algorithms for neural networks and other complex models.Related Work From the point of view of learning theory, it is well known that training is computational infeasible in the worst case BID12 BID2 . Thus distributional assumptions are needed for efficient learning. A line of research has focused on analyzing the dynamics of gradient descent conditioned on the input distribution being standard Gaussian BID29 BID28 BID21 BID32 BID2 BID31 BID5 . Specifically for convolutional nets, existing analyses heavily relied on the analytical formulas which can only be derived if the input is Gaussian and patches are non-overlapping.Recent work has tried to relax the Gaussian input assumption and the non-overlapping structure for learning convolutional filters. BID5 showed if the patches are sufficiently close to each other then stochastic gradient descent can recover the true filter. BID13 proposed a modified iterative algorithm inspired from isotonic regression that gives the first recovery guarantees for learning a filter for commonly used overlapping patches under much weaker assumptions on the distribution. However, these two analyses only work for learning one unknown convoutional filter.Moving away from gradient descent, various works have shown positive results for learning general simple fully connected neural networks in polynomial time and sample complexity under certain assumptions using techniques such as kernel methods BID12 BID30 BID10 BID0 and tensor decomposition BID27 BID18 . The main drawbacks include the shift to improper learning for kernel methods and the knowledge of the probability density function for tensor methods. In contrast to this, our algorithm is proper and does not assume that the input distribution is known.Learning a neural network is often formulated as a non-convex problem. If the objective function satisfies (1) all saddle points and local maxima are strict (i.e., there exists a direction with negative curvature), and (2) all local minima are global (no spurious local minmum), then noise-injected (stochastic) gradient descent BID7 BID19 ) finds a global minimum in polynomial time. Recent work has studied these properties for the landscape of neural networks BID20 BID3 BID15 BID14 BID22 BID6 BID25 Zhou & Feng, 2017; BID23 BID0 BID9 Zhou & Feng, 2017; BID26 BID4 . A crucial step in our algorithm is reducing the convolutional neural network learning problem to matrix factorization and using the geometric properties of matrix factorization. In this paper, we propose the first efficient algorithm for learning a one-hidden-layer convolutional neural network with possibly overlapping patches. Our algorithm draws ideas from isotonic regression, landscape analysis of non-convex problem and spectral analysis of Toeplitz matrices. These findings can inspire further development in this field. Our next step is extend our ideas to design provable algorithms that can learn complicated models consisting of multiple filters. To solve this problem, we believe the recent progress on landscape design BID9 may be useful.
We propose an algorithm for provably recovering parameters (convolutional and output weights) of a convolutional network with overlapping patches. This paper studies the theoretical learning of one-hidden-layer convolutional neural nets, resulting in a learning algorithm and provable guarantees using the algorithm. This paper gives a new algorithm for learning a two layer neural network which involves a single convolutional filter and a weight vector for different locations.