Year: 2018

Abstract:
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.

heading: 1 INTRODUCTION
text: 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 Brutzkus & Globerson (2017) 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 ajσ
` wJPjx ˘
(1)
where w P Rr is a shared convolutional filter, a P Rk is the second linear layer and
Pj “ r 0lomon pj´1qs I lomon r 0 lomon d´pj´1qs`r
s P Rrˆ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 r2 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 Goel et al. (2018) 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 (Ge et al., 2017a). Third, in analyzing our algorithm, we present a robust analysis of Convotron algorithm proposed by Goel et al. (2018), 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 (Goel et al., 2016; Brutzkus & Globerson, 2017). 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 (Tian, 2017; Soltanolkotabi, 2017; Li & Yuan, 2017; Zhong et al., 2017b; Brutzkus & Globerson, 2017; Zhong et al., 2017a; Du et al., 2017). 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. Du et al. (2017) showed if the patches are sufficiently close to each other then stochastic gradient descent can recover the true filter. Goel et al. (2018) 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 (Goel et al., 2016; Zhang et al., 2015; Goel & Klivans, 2017a;b) and tensor decomposition (Sedghi & Anandkumar, 2014; Janzamin et al., 2015). 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 (Ge et al., 2015; Jin et al., 2017) finds a global minimum in polynomial time. Recent work has studied these properties for the landscape of neural networks (Kawaguchi, 2016; Choromanska et al., 2015; Hardt & Ma, 2016; Haeffele & Vidal, 2015; Mei et al., 2016; Freeman & Bruna, 2016; Safran & Shamir, 2016; Zhou & Feng, 2017; Nguyen & Hein, 2017a;b; Ge et al., 2017b; Zhou & Feng, 2017; Safran & Shamir, 2017; Du & Lee, 2018). 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.

heading: 2 PRELIMINARIES
text: We use bold-faced letters for vectors and matrices. We use }¨}2 to denote the Euclidean norm of a finite-dimensional vector. For a matrix A, we use λmax pAq to denote its eigenvalue and λmin pAq its smallest singular value. Let Op¨q and Ω p¨q denote standard Big-O and Big-Omega notations, only hiding absolute constants.
In our setting, we have n data points txi, yiuni“1 where xi P Rd and y P R. We assume the label is generated by a two-layer convolutional neural network with filter size r, stride s and k hidden neurons. Compactly we can write the formula in the following form: yi “ fpxi,w˚,a˚q, xi „ Z where the prediction function f is defined in equation 1. To obtain a proper scaling, we let }w˚}2 }a˚}2 “ σ1. We also define the induced patch matrix as
P pxq “ rP1x . . . Pkxs P Rrˆk
which will play an important role in our algorithm design. Our goal is to properly learn this convolutional neural network, i.e., design a polynomial time algorithm which outputs a pair pw,aq that satisfies Ex„Z ” pfpw,a,xq ´ fpw˚,a˚,xqq2 ı ď .
Algorithm 1 Learning One-hidden-Layer Convolutional Network Input: Input distribution Z . Number of iterations: T1, T2. Number of samples: T3. Step sizes: η1 ą 0, η2 ą 0. Output: Parameters of the one-hidden-layer CNN: w and a.
1: Stage 1: Run Double Convotron (Algorithm 2) for T1 iterations with step size η1 to obtain apT1q. 2: Stage 2: Run Convotron (Algorithm 3) using apT1q and ´apT1q for T2 iterations and step size η2 to obtain wp`q and wp´q. 3: Stage 3: Choose parameters with lower empirical loss on T3 samples drawn from Z from `
wp`q,apT q ˘ and ` wp´q,´apT q ˘ .

heading: 3 MAIN RESULT
text: In this section we describe our main result. We first list our main assumptions, followed by the detailed description of our algorithm. Lastly we state the main theorem which gives the convergence guarantees of our algorithm.

heading: 3.1 ASSUMPTIONS
text: Our first assumption is on the input distribution Z . We assume the input distribution is symmetric, bounded and has identity covariance. The symmetry assumption is used in Goel et al. (2018) and many learning theory papers Baum (1990). The identity covariance assumption is true if the data whitened. Further, in many architectures, the input of certain layers is assumed having these properties because of the use of batch normalization (Ioffe & Szegedy, 2015) or other techniques. Lastly, the boundedness is a standard regularity assumption to exclude pathological input distributions. We remark that this assumption considerably weaker than the standard Gaussian input distribution assumption used in Tian (2017); Zhong et al. (2017a); Du et al. (2017), which has the rotational invariant property.
Assumption 3.1 (Input Distribution Assumptions). We assume the input distribution satisfies the following conditions.
• Symmetry: P pxq “ P p´xq .
• Identity covariance: Ex„Z “ xxT ‰ “ I.
• Boundedness: @x „ Z, }x}2 ď B almost surely for some B ą 0.
Our second assumption is on the patch structure. In this paper we assume the stride is larger than half of the filter size. This is indeed true for a wide range of convolutional neural network used in computer vision. For example some architecture has convolutional filter of size 3 and stride 2 and some use non-overlapping architectures (He et al., 2016).
Assumption 3.2 (Large Stride). s ě t r2 u` 1.
Next we assume the activation function is piecewise linear. Commonly used activation functions like rectified linear unit (ReLU), Leaky ReLU and linear activation all belong to this class.
Assumption 3.3 (Piece-wise Linear Activation).
σpxq “ " x if x ě 0 αx if x ă 0 .

heading: 3.2 ALGORITHM
text: Now we are ready to describe our algorithm (see Algorithm 1). The algorithm has three stages, first we learn the outer layer weights upto sign, second we use these fixed outer weights to recover the filter weight and last we choose the best weight combination thus recovered.
Stage 1: Learning the Non-overlapping Part of the Convolutional Filter and Linear Weights Our first observation is even if there may be overlapping patches, as long as there exists some nonoverlapping part, we can learn this part and the second layer jointly. To be specific, with filter size being r and stride being s, if s ě t r2 u ` 1, for j “ 1. . . . , k we define the selection matrix for the non-overlapping part of each patch
Pnonj “ r 0lomon pj´1qs`r I lomon 2s´r 0 lomon d´pj`1qs s P Rp2s´rqˆd.
Note that for any j1 ‰ j2, there is no overlapping between the selected coordinates by Pnonj1 and Pnonj2 . Therefore, for a filter w, there is a segment rwr´s`1, . . . , wss with length p2s´rq which acts on the non-overlapping part of each patches. We denote wnon “ rwr´s`1, . . . , wss and our goal in this stage is to learn w˚non and a ˚ jointly.
In this stage, our algorithm proceeds as follows. Given wnon, a and a sample px, yq, we define
g pwnon,a,x, yq “ 2
1` γ
´ f̂pwnon,a,xq ´ y ¯
k ÿ j“1 aiP non j x` 1 4 ´ }wnon}22 ´ }a} 2 2 ¯ wnon (2)
h pwnon,a,x, yq “ 2
1` γ
´ f̂pwnon,a,xq ´ y ¯
¨
˝
wJnonP non 1 x
. . . wJnonP non k x
˛
‚` 1 4 ´ }a}22 ´ }wnon} 2 2 ¯ a (3)
where f̂ pwnon,a,xq “ řk j“1 ajσ ` wJnonP non j x ˘ is the prediction function only using wnon.
As will be apparent in Section 4, g and h are unbiased estimates of the gradient for the loss function of learning a linear CNN. The term 14 ´ }wnon}22 ´ }a} 2 2 ¯ wnon and 14 ´ }a}22 ´ }wnon} 2 2 ¯ a are
is the gradient induced by the regularization 14 ´ }wnon}22 ´ }a} 2 2
¯2
, which is used to balance the magnitude between wnon and a and make the algorithm more stable.
With some initialization wp0qnon and ap0q, we use the following iterative updates inspired by isotonic regression (Goel et al., 2018), for t “ 0, . . . , T1 ´ 1
wpt`1qnon Ðwptqnon ´ η1g ´ wptqnon,a ptq,xptq, yptq ¯ ` η1ξptqwnon , (4)
apt`1q Ðaptq ´ η1h ´ wptqnon,a ptq,xptq, yptq ¯ ` η1ξptqa (5)
where η1 ą 0 is the step size parameter, ξptqwnon and ξ ptq a are uniformly sampled a unit sphere and at iteration we use a fresh sample ` xptq, yptq ˘ . Here we add isotropic noise ξptqwnon and ξ ptq a because the objective function for learning a linear CNN is non-convex and there may exist saddle points. Adding noise can help escape from these saddle points. We refer readers to Ge et al. (2015) for more technical details regarding this. As will be apparent in Section 4, after sufficient iterations, we obtain a pair ` wpT1q,apT1q ˘
such that either it is close to the truth pw˚non,a˚q or close to the negative of the truth p´w˚non,´a˚q. Remark 3.1 (Non-overlapping Patches). If there is no overlap between patches, we can skip Stage 2 because after Stage 1 we have already learned a and wnon “ w.
Stage 2: Convotron with fixed Linear Layer In Stage 1 we have learned a good approximation to the second layer (either apT1q or´apT1q). Therefore, the problem reduces to learning a convolutional filter. We run Convotron (Algorithm 3) proposed in Goel et al. (2018) using apT1q and ´apT1q to obtain corresponding weight vectors wp`q and wp´q. We show that the Convotron analysis can be extended to handle approximately known outer layer weight vectors.
Stage 3: Validation In stage 2 we have obtained two possible solutions ` wp`q,apT q ˘
and `
wp´q,´apT q ˘
. We know at least one of them is close to the ground truth. Closeness in ground truth implies small squared loss (c.f. Lemma A.1). In the last stage we use a validation set to choose
Algorithm 2 Double Convotron
Initialize wp0qnon P R2s´r and ap0q P Rk randomly for t “ 1 to T do
Draw pxptq, yptqq „ Z Compute g ` wnon,a,x ptq, yptq ˘ and h ` wnon,a,x ptq, yptq ˘
according to equation 2 and equation 3.
Set wpt`1qnon “ wptqnon ´ η1g ´ w ptq non,aptq,xptq, yptq ¯ ` η1ξptqwnon Set apt`1q “ aptq ´ η1h ´ w ptq non,aptq,xptq, yptq ¯
` η1ξptqa Return apT`1q
Algorithm 3 Convotron (Goel et al., 2018) Initialize w1 :“ 0 P Rr. for t “ 1 to T do
Draw pxptq, yptqq „ Z Let gptq “ pyptq ´ fpwptq,a,xptqqq ´
řk i“1 aiPix
ptq ¯
Set wpt`1q “ wptq ` ηgptq Return wT`1
the right one. To do this, we simply use T3 “ poly ` k,B, 1 ˘
fresh samples and output the solution which gives lower squared error.
pw,aq “ arg min pw,aqPtpwp`q,apT qq,pwp´q,´apT qqu
1
T3
T3 ÿ
i“1
´ ypiq ´ f ´ w,a,xpiq ¯¯2 . (6)
Since we draw many samples, the empirical estimates will be close to the true loss using standard concentration bounds and choosing the minimum will give us the correct solution.

heading: 3.3 MAIN THEOREM
text: The following theorem shows that Algorithm 1 is guaranteed to learn the target convolutinoal neural network in polynomial time. To our knowledge, this is the first polynomial time proper learning algorithm for convolutional neural network with overlapping patches. Theorem 3.1 (Theorem 1.1 (Formal)). Under Assumptions 3.1-3.3, if we set T1, T2, T3 “ Ω ` poly ` k,B, 1 ˘˘ and η1, η2 “ O ` poly ` 1 k , 1 B , ˘˘
then with high probability, Algorithm 1 returns a pair pw,aq which satisfies
Ex„Z ” pfpw,a,xq ´ fpw˚,a˚,xqq2 ı ď .

heading: 4 PROOFS AND TECHNICAL INSIGHTS
text: In this section we list our key ideas used for designing the Algorithm 1 and proving its correctness. We discuss the analysis stage-wise for ease of understnading.

heading: 4.1 ANALYSIS OF STAGE 1
text: Learning a non-overlapping CNN with linear activation. We first consider the problem of learning a convolutional neural network with linear activation function and non-overlapping patches. For this setting, we can write the prediction function in a compact form:
f pw,a,xq “ wJP pxqa “ xP pxq ,waJy. The label also admits this form y “ xP pxq ,w˚ pa˚qJy. A natural way to learn w˚ and a˚ is to consider solving a square loss minimization problem:
min ` pw,a,xq “ ´ xP pxq ,waJy ´ xP pxq ,w˚ pa˚qJy ¯2 .
Now, taking expectation with respect to x, we have
L pw,aq “ › › › waJ ´w˚ pa˚qJ › › ›
2 F (7)
where the last step we used our assumptions that patches are non-overlapping and the covariance of x is the identity. From equation 7, it is now apparent that the population L2 loss is just the standard loss for rank-1 matrix factorization problem.
Recent advances in non-convex optimization shows the following regularized loss function
Lreg pw,aq “ 1
2
›
› › waJ ´w˚ pa˚qJ
›
›
›
2 F ` 1 8 ´ }w}22 ´ }a} 2 2 ¯2 . (8)
satisfies all local minima are global and all saddles points and local maxima has a negative curvature Ge et al. (2017a) and thus allows simple local search algorithm to find a global minimum. Though the objective function in equation 8 is a population risk, we can obtain its stochastic gradient by our samples if we use fresh sample at each iteration. We define
gptqw “ ´ f ´ wptq,aptq,xptq ¯ ´ yptq ¯ P ` xt ˘ aptq ` 1 2
ˆ
›
› › wptq
›
›
›
2 2 ´ › ›at › › 2 2
˙
wptq (9)
gptqa “ ´ f ´ wptq,aptq,xptq ¯ ´ yptq ¯ P ` xt ˘J wptq ` 1 2
ˆ
› ›at › ›
2 2 ´ › › › wptq › › ›
2
2
˙
aptq (10)
where ` xptq, yptq ˘
is the sample we use in the t-th iteration. In expectation this is the standard gradient descent algorithm for solving equation 8:
Ex ” gptqw ı “ BLreg
` wptq,aptq ˘ Bwptq , Ex ” gptqa ı “ BLreg ` wptq,aptq ˘ Baptq .
With this stochastic gradient oracle at hand, we can implement the noise-injected stochastic gradient descent proposed in Ge et al. (2015).
wpt`1q “ wptq ´ ηgptqw ` ηξptqw , apt`1q “ wptq ´ ηgptqa ` ηξptqa
where ξptqw and ξ ptq a are sampled from a unit sphere. Theorem 6 in Ge et al. (2015) implies after polynomial iterations, this iterative procedure returns an -optimal solution of the objective function equation 8 with high probability.
Learning non-overlapping part of a CNN with piece-wise linear activation function Now we consider piece-wise linear activation function. Our main observation is that we can still obtain a stochastic gradient oracle for the linear convolutional neural network using equation 2 and equation 3. Formally, we have the following theorem. Lemma 4.1 (Properties of Stochastic Gradient for Linear CNN). Define
Lreg pwnon,aq “ 1
2
›
› › wnona J ´w˚non pa˚q J › › ›
2 F ` 1 8 ´ }wnon}22 ´ }a} 2 2 ¯2 .
Under Assumption 3.1, we have
Ex rg pwnon,a,x, yqs “ BLreg pwnon,aq
Bwnon ,Ex rh pwnon,a,x, yqs “ BLreg pwnon,aq Ba
where g pwnon,a,x, yq and h pwnon,a,x, yq are defined in equation 2 and equation 3, respectively. Further, if }wnon}2 “ Oppoly pσ1qq, }a}2 “ Oppoly pσ1qq, then the differences are also bounded
›
›
›
›
g pwnon,a,x, yq ´ BLreg pwnon,aq
Bwnon
›
›
›
›
ď D, › › ›
›
h pwnon,a,x, yq ´ BLreg pwnon,aq
Ba
›
›
›
›
2
ď D
for some D “ O ppoly pB, k, σ1qq.
Here the expectation of g and h are equal to the gradient of the objective function for linear CNN because we assume the input distribution is symmetric and the activation function is piece-wise linear. This observation has been stated in Goel et al. (2018) and based on this property, Goel et al.
(2018) proposed Convotron algorithm (Algorithm 3), which we use in our stage 2. Lemma 4.1 is a natural extension of Lemma 2 of Goel et al. (2018) that we show even for one-hidden-layer CNN, we can still obtain an unbiased estimate of the gradient descent for linear CNN.
Now with Lemma 4.1 at hand, we can use the theory from non-convex matrix factorization. Ge et al. (2017a) has shown if η1 “ O ` poly ` 1 k , 1 B , ˘˘ then for all iterates, with high probability, ›
› › w ptq non
›
›
› 2 “ Oppoly pσ1qq, }at}2 “ Oppoly pσ1qq. Therefore, we can apply the algorithmic result in
Ge et al. (2015) and obtain the following convergence theorem. Theorem 4.1 (Convergence of Stage 1). If wp0q “ O `? σ1 ˘ , ap0q “ O `? σ1 ˘
, and η1 “ O ` poly `
1 k , 1 B ,
˘˘ then after T1 “ O ` poly ` r, k,B, 1 ˘˘
we have ›
›
›
›
›
apT1q › ›apT1q › ›
2
´ a ˚
}a˚}2
›
›
›
›
›
2
ď . or
›
›
›
›
›
apT1q › ›apT1q › ›
2
` a ˚
}a˚}2
›
›
›
›
›
2
ď .

heading: 4.2 ANALYSIS OF STAGE 2
text: After Stage 1, we have approximately recovered the outer layer weights. We use these as fixed weights and run Convotron to obtain the filter weights. The analysis of Convotron inherently handles average pooling as the outer layer. Here we extend the analysis of Convotron to handle any fixed outer layer weights and also handle noise in these outer layer weights. Formally, we obtain the following theorem:
Theorem 4.2. (Learning the Convolutional Filter) Suppose }a´ a˚}2 ď for ď 1
k3}w˚}2 and
without loss of generality1 let }a}2 “ }a˚}2 “ 1. For suitably chosen η “ O ` poly ` 1 k , 1 B ˘˘
, Convotron (modified) returns w such that with a constant probability, }w ´w˚}2 ď Opk3 }w˚} q in polypk, }w˚} , B, logp1{ qq iterations.
Note that we present the theorem and proof for covariance being identity and no noise in the label but it can be easily extended to handle non-identity convariance with good condition number and bounded (in expectation) probabilistic concept noise.
Our analysis closely follows that from Goel et al. (2018). However, in contrast to the known second layer setting considered in Goel et al. (2018), we only know an approximation to the second layer and a robust analysis is needed. Another difficulty arises from the fact that the convergence rate depends on the least eigenvalue of Pa :“ ř
1ďi,jďk aiajPiP T j . By simple algebra, we can show
that the matrix has the following form:
Papi, jq “
$
’ &
’ %
1 if i “ j řk´1 i“1 aiai`1 if |i´ j| “ s 0 otherwise.
Using property of Toeplitz matrices, we show the least eigenvalue of Pa is lower bounded by 1 ´ cos ´
π k`1
¯
(c.f. Theorem A.2) for all a with norm 1.

heading: 4.3 ANALYSIS OF STAGE 3
text: Here we show how we can pick the correct hypothesis from the two possible hypothesis. Under our assumptions, the individual loss pypiq ´ fpw,a,xpiqqq2 is bounded. sThus, a direct application of Hoeffding inequality gives the following guarantee.
Theorem 4.3. Suppose T3 “ Ω ` poly ` r, k,B, 1 ˘˘ and let pw,aq. If either ` wp`q,aT1 ˘
or `
wp´q,´aT1 ˘ has population risk smaller than 2 , then let pw,aq be the output according to equation 6, then with high probability
Ex„Z “ fpw,a,x´ fpw˚,a˚,xqq2 ‰ ď . 1Note that we can assume that the outer layers have norm 1 by using the normalized weight vectors since
the activations are scale invariant.

heading: 4.4 PUTTING THINGS TOGETHER: PROOF OF THEOREM 3.1
text: Now we put our analyses for Stage 1-3 together and prove Theorem 3.1. By Theorem 4.1, we know we have apT1q such that › ›aT1 ´ a˚ › › ď O ´
r1{2k5{2σ1
¯
(without loss of generality, we assume a and
a˚ are normalized) with η1 “ O ´ poly ´ 1 k , 1 B , 1 σ1 , ¯¯ and |S1| “ poly ` r, k,B, σ1, 1 ˘ .
Now with Theorem 4.2, we know with η “ O ` poly ` 1 k , 1 B ˘˘ and |S2| “ O ` poly ` k, σ1, log 1 ˘˘ we have either › ›wp`q ´w˚ › ›
2 ď σ1r1{2k3{2 or
› ›wp´q ´w˚ › ›
2 ď σ1r1{2k3{2 . Lastly, the following
lemma bounds the loss of each instance in terms of the closeness of parameters.
Lemma 4.2. For any a and w, we have
´ f pw˚,a˚,xq ´ f ´ wptq,a,x ¯¯2 ď 2k ´
}a}22 }w ´w ˚}22 ` }a´ a ˚}22 }w ˚}22
¯
}x}22 .
Therefore, we know either ` wp`q,apT1q ˘ or ` wp´q,´apT1q ˘
achieves prediction error. Now combining Theorem 4.3 and Lemma A.1 we obtain the desired result.

heading: 5 EXPERIMENTS
text: In this section we use simulations to verify the effectiveness of our proposed method. We fix input dimension d “ 160 and filter size r “ 16 for all experiments and vary the stride size s “ 9, 12, 16. For all experiments, we generate w˚ and a˚ from a standard Gaussian distribution and use 10, 000 samples to calculate the test error. Note in Stage 2 of Algorithm we need to test a “ apT1q and ´apT1q. Here we only report the one with better performance in the Stage 2 because in Stage 3 we can decide which one is better. To measure the performance of Stage 1, we use the angle between at an a˚ (in radians). We first test Gaussian input distribution x „ Np0, Iq. Figure 1a shows the convergence in Stage 1 of Algorithm 1 with T1 “ 10000 and η1 “ 0.0001. Figure 1b shows the convergence in Stage 2 of Algorithm 1 with T2 “ 10000 and η2 “ 0.0001. We then test uniform input distribution x „ Unifr´ ? 3, ?
3sd (this distribution has identity covariance). Figure 1c shows the convergence in Stage 1 of Algorithm 1 with T1 “ 40000 and η1 “ 0.0001. Figure 1d shows the convergence in Stage 2 of Algorithm 1 with T2 “ 100000 and η2 “ 0.00001. Note for both input distributions and all choices of stride size, our algorithm achieves low test error..

heading: 6 CONCLUSION AND FUTURE WORK
text: 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 (Ge et al., 2017b) may be useful.

heading: A USEFUL LEMMAS/THEOREMS
text: In this section we present a few lemmas/theorems that are useful for our analysis.
Proof of Lemma 4.2. Observe that, ´
f pw˚,a˚,xq ´ f ´ wptq,a,x ¯¯2
ď 2 ´ pf pw˚,a˚,xq ´ f pw˚,a,xqq2 ` pf pw˚,a,xq ´ f pw,a,xqq2 ¯
since pa` bq2 ď 2 ` a2 ` b2 ˘ for all a, b P R. The first term can be bounded as follows,
pf pw˚,a˚,xq ´ f pw˚,a,xqq2 “ ˜ k ÿ
i“1 pa˚i ´ aiqσ
´ pw˚qT Pix ¯
¸2
ď ˜ k ÿ
i“1 |a˚i ´ ai|| pw˚q T Pix|
¸2
ď ˜ k ÿ
i“1 |a˚i ´ ai| }w˚}2 }x}2
¸2
ď k }a˚ ´ a}22 }w ˚}22 }x} 2 2 .
Here the first inequality follows from observing that σ paq ď |a| and the last follows from }v}1 ď? k }v}2 for all v P Rk.
Similarly, the other term can be bounded as follows,
pf pw˚,a,xq ´ f pw,a,xqq2 “ ˜ k ÿ
i“1 ai
´ σ ´ pw˚qT Pix ¯ ´ σ ` wTPix ˘ ¯
¸2
ď ˜ k ÿ
i“1 |ai|| pw˚ ´wqT Pix|
¸2
ď ˜ k ÿ
i“1 |ai| }w˚ ´w}2 }x}2
¸2
ď k }a}22 }w ˚ ´w}22 }x} 2 2 .
Here we use the Lipschitz property of σ to get the first inequality. The lemma follows from combining the above two.
The following lemma extends this to the overall loss. Lemma A.1. For any a and w,
Er ´ f pw˚,a˚,xq ´ f ´ wptq,a,x ¯¯2 s ď 2kB ´
}a}22 }w ´w ˚}22 ` }a´ a ˚}22 }w ˚}22
¯
.
The following lemma from Goel et al. (2018) is key to our analysis. Lemma A.2 (Lemma 1 of Goel et al. (2018)). For all a,b P Rn, if Z is symmetric then,
Ex„Z rσ ` aTx ˘ ` bTx ˘ s “ 1` α 2 Ex„Z r ` aTx ˘ ` bTx ˘ s.
The following well-known theorem is useful for bounding eigenvalues of matrices. Theorem A.1 (Gershgorin Circle Theorem Weisstein (2003)). For a nˆ n matrix A, define Ri :“ řn j“1,j‰i |Ai,j |. Each eigenvalue of A must lie in at least one of the disks tz : |z ´Ai,i| ď Riu.
The following lemma bounds the eigenvalue of the weighted patch matrices. Theorem A.2. For all a P Sk´1,
λmin pPaq ě 1´ cos ˆ π
k ` 1
˙ and λmax pPaq ď 1` cos ˆ π
k ` 1
˙
.
Proof. Since s ě t r2 u` 1, only adjacent patches overlap, and it is easy to verify that the matrix P a has the following structure:
Pa pi, jq “
$
’ &
’ %
1 if i “ j řk´1 i“1 aiai`1 if |i´ j| “ s 0 otherwise.
Using the Gershgorin Circle Theorem, stated below, we can bound the eigenvalues, λmin pPaq ě 1´ ˇ ˇ
ˇ řk´1 i“1 aiai`1
ˇ
ˇ ˇ and λmax pPaq ď 1`
ˇ
ˇ
ˇ řk´1 i“1 aiai`1
ˇ
ˇ ˇ .
To bound the eigenvalues, we will bound ˇ ˇ
ˇ řk´1 i“1 aiai`1
ˇ
ˇ ˇ by maximizing it over all a such that }a}2 “
1. We have max ! ˇ ˇ
ˇ řk´1 i“1 aiai`1
ˇ
ˇ
ˇ
) “ max ! řk´1 i“1 aiai`1 ) since the maximum can be achieved by
setting all ai to be non-negative. This can alternatively be viewed as max}a}2“1 a TMa “ λmax pMq where M is a tridiagonal symmetric Toeplitz matrix as follows:
M pi, jq “ " 1{2 if |i´ j| “ 1 0 otherwise.
It is well known that the eigenvalues of this matrix are of the form cos ´
iπ k`1
¯
for i “ 1, . . . , k (c.f.
Boeóttcher & Grudsky (2005)). The maximum eigenvalue is thus cos ´
π k`1
¯
. This gives us the result.

heading: B OMITTED PROOFS
text: B.1 PROOF OF LEMMA 4.1
First by definition, we have
Ex rg pwnon,a,x, yqs “Ex
«
2
1` γ
´ f̂ pwnon,a,xq ´ y ¯
k ÿ j“1 ajP non j x` 1 4 ´ }wnon}22 ´ }a} 2 2 ¯ wnon
ff
.
Because the input distribution is symmetric and the covariance is identity, by Lemma A.2, we have
Ex
«
2 1` γ f̂ pwnon,a,xq k ÿ
j“1 ajP
non j x
ff
“Ex
«
2
1` γ
k ÿ j“1 ajσ ` wJnonP non j x ˘ k ÿ j“1 ajP non j x
ff
“Ex
«
k ÿ j“1 ajw J nonP non j x k ÿ j“1 ajP non j x
ff
“}a}22 wnon.
Similarly, we have
Ex
«
y k ÿ
j“1 ajP
non j x
ff
“ aJa˚w˚.
Also recall BLreg pw,aq
Bw “ }a} 2 2 wnon ´ a Ja˚w˚ ` 1 4 ´ }wnon}22 ´ }a} 2 2 ¯ wnon.
Thus
Ex rg pwnon,a,x, yqs “ BLreg pw,aq
Bw .
The proof for h pwnon,a,x, yq is similar. To obtain a bound of the gradient, note that
›
›
›
›
›
k ÿ j“1 ajσ ` wJnonP non j x ˘ k ÿ j“1 ajP non j x
›
›
›
›
›
ď k ÿ
j“1 |aj |
ˇ ˇwJnonP non j x ˇ ˇ
›
›
›
›
›
k ÿ j“1 ajP non j x
›
›
›
›
›
ďmax j |aj |
k ÿ j“1 }wnon}2 › ›Pnonj x › › 2 ¨ }a}2 }x}2
ďk }a}22 }x} 2 2 }w}2 “poly pk, σ1, Bq .
Similar argument applies to y řk j“1 ajP non j x.
B.2 PROOF OF THEOREM 4.2
We follow the Convotron analysis and include the changes. Define St “ tpx1, y1q , . . . , pxt, ytqu. The modified gradient update is as follows,
gptq “ ´ yt ´ f ´ wptq,a,xt ¯¯
˜
k ÿ i“1 aiPixt
¸
The dynamics of Convotron can then be expressed as follows:
Ext,ytr › › › wptq ´w˚ › › ›
2 2 ´ › › › wpt`1q ´w˚ › › › 2 2 |St´1s “ 2ηExt,ytr ´ w˚ ´wptq ¯T gptq|St´1s´η2Ext,ytr||gptq||2|St´1s.
We have,
Ext,yt „ ´ w˚ ´wptq ¯T gptq|St´1 
“ Ext,yt
«
´ w˚ ´wptq ¯T ´ yt ´ f ´ wptq,a,xt ¯¯
˜
k ÿ i“1 aiPixt
¸ˇ
ˇ
ˇ
ˇ
ˇ
St´1
ff
“ Ext
«
´ w˚ ´wptq ¯T ´ f pw˚,a˚,xtq ´ f ´ wptq,a,xt ¯¯
˜
k ÿ i“1 aiPixt
¸ ˇ
ˇ
ˇ
ˇ
ˇ
St´1
ff
“ ÿ
1ďi,jďk Extr
ˆ
a˚i σ ´ pw˚qT Pixt ¯ ´ aiσ ˆ ´ wptq ¯T Pixt ˙˙ˆ aj pw˚qT ´ aj ´ wptq ¯T ˙ Pjxt|St´1s
“ 1` α 2 ÿ
1ďi,jďk Ext
„ˆˆ
a˚i pw˚q T ´ ai
´ wptq ¯T
˙
Pixt
˙ˆ
aj pw˚qT ´ aj ´ wptq ¯T
˙ Pjxt|St´1 
(11)
“ 1` α 2 ÿ
1ďi,jďk
ˆ
a˚i pw˚q T ´ ai
´ wptq ¯T
˙
PiExtrxtxTt sPTj ´ ajw ˚ ´ ajwptq ¯
(12)
“ 1` α 2 ÿ
1ďi,jďk
ˆ
a˚i pw˚q T ´ ai pw˚qT ` ai pw˚qT ´ ai
´ wptq ¯T
˙
PiP T j
´
ajw ˚ ´ ajwptq
¯
“ 1` α 2
˜
´ pw˚qT ´ pw˚qT ¯ Pa pw˚ ´w˚q ` ÿ
1ďi,jďk pa˚i ´ aiq aj pw˚q T PiP T j
´ w˚ ´wptq ¯
¸
(13)
ě 1` α 2
¨
˝λmin pPaq › › › wptq ´w˚ › › ›
2 2 ´ }w˚}2
›
›
›
›
›
ÿ
1ďiďk pa˚i ´ aiqPi
›
›
›
›
›
2
›
›
›
›
›
ÿ
1ďjďk ajPj
›
›
›
›
›
2
›
› › wptq ´w˚
›
›
›
2
˛
‚
(14)
ě 1` α 2
ˆ
λmin pPaq › › › wptq ´w˚ › › ›
2 2 ´ k }w˚} }a˚ ´ a}2 }a}2 › › › wptq ´w˚ › › › 2
˙
ě 1` α 2
ˆ
λmin pPaq › › › wptq ´w˚ › › ›
2 2 ´ k }w˚}2 › › › wptq ´w˚ › › › 2
˙
(11) follows from using Lemma A.2, (13) follows from defining Pa :“ ř 1ďi,jďk aiajPiP T j , (12) follows from setting the covariance matrix to be identity and (14) follows from observing that Pa is symmetric, thus @x,xTPax ě λmin pPaq }x}22 as well as lower bounding the second term in terms of the norms of the corresponding parts.
Now we bound the variance of gptq.
Ext,ytr||gptq||2|St´1s
“ Ext,yt
»
–
´ yt ´ f ´ wptq,a,xt
¯¯2 ˇ ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
k ÿ i“1 aiPixt
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
St´1
fi
fl
ď λmax pPaqExt „ ´ f pw˚,a˚,xtq ´ f ´ wptq,a,xt ¯¯2 ||xt||2 ˇ ˇ ˇ
ˇ
St´1

(15)
ď 2kλmax pPaq ˆ }a}22 › › › wptq ´w˚ › › › 2
2 ` }a´ a˚}22 }w
˚}22 ˙ Ext ” }xt}42 ı
(16)
ď 2kBλmax pPaq ˆ › › › wptq ´w˚ › › › 2
2 ` 2 }w˚}22
˙
(17)
(15) follows from observing that ˇ ˇ
ˇ
ˇ
ˇ
ˇ řk i“1 aiPix
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
2
ď λmax pPaq }x}22 for all x and (16) follows from Lemma 4.2.
Combining the above equations and taking expectation over St´1, we get
EStr › › › wpt`1q ´w˚ › › ›
2 2 s ď ` 1´ 2ηβ ` η2γ ˘ ESt´1r › › › wptq ´w˚ › › › 2 2 s ` 2ηα ESt´1r › › › wptq ´w˚ › › › 2 s ` η2χ 2
ď ` 1´ 2ηβ ` η2γ ˘ ESt´1r › › › wptq ´w˚ › › ›
2 2 s ` 2ηδ
b
ESt´1r › ›wptq ´w˚ › ›
2 2 s ` η2χ 2
for β “ 1`α2 λmin pP aq, γ “ 2λmax pPaq kB, δ “ 1`α2 k }w ˚}2 and χ “ 2λmax pPaq kB }w˚} 2 2.
From Theorem A.2, we have that λmin pPaq “ 1 ´ cos ´ π k`1 ¯ “ Ω ` 1{k2 ˘ (by Taylor expansion)
implying β “ ω ` 1{k2 ˘ and γ “ O pkBq, χ “ O ´ kB }w˚}22 ¯ .
We set η “ βmin ´
1 γ , 1 χ
¯
. First we show that ESt´1r › ›wptq ´w˚ › ›
2 2 s ď 1 for all iterations t. We
prove this inductively. For t “ 1, since w1 “ 0, this is satisfied. Let us assume it holds for iteration t, then we have that,
EStr › › › wpt`1q ´w˚ › › ›
2 2 s ď ` 1´ 2ηβ ` η2γ ˘ ESt´1r › › › wptq ´w˚ › › › 2 2 s ` 2ηδ
b
ESt´1r › ›wptq ´w˚ › ›
2 2 s ` η2χ 2
ď 1´ 2ηβ ` η2γ ` 2ηδ ` η2χ 2
ď 1´ 2ηβ ` ηβ ` 2ηδ ` ηβ ď 1´ η pβ ´ pδ ` βq q ď 1
The last inequality follows from ď 1k3}w˚}2 ď β δ`β . Thus we have that for each iteration, ESt´1r › ›wptq ´w˚ › › 2 2 s ď 1. Substituting this in the recurrence and solving the recurrence gives
us,
EStr › › › wpt`1q ´w˚ › › ›
2 2 s ď ` 1´ 2ηβ ` η2γ ˘ ESt´1r › › › wptq ´w˚ › › › 2 2 s ` 2ηδ ` η2χ 2
ď p1´ ηβqESt´1r › › › wptq ´w˚ › › ›
2 2 s ` 2ηδ ` ηβ 2
ď p1´ ηβqt }w1 ´w˚}22 ` ` 2ηδ ` ηβ 2 ˘
t´1 ÿ i“0 p1´ ηβqi
ď p1´ ηβqt ` 2δ β ` 2
Thus for T “ O ´
1 ηβ log
`
1
˘
¯
, we have,
EStr › › › wpt`1q ´w˚ › › ›
2 2 s ď O
ˆ
δ
β
˙
“ O ` k3 }w˚}2 ˘ .
Now using Markov’s inequality, we know that the above holds for some constant probability.
B.3 PROOF OF THEOREM 4.3
For i “ T2 ` 1, . . . , T3, define zpiq “ ` ypiq ´ f ` w,a,xpiq ˘˘2
. Using our assumptions, we know zpiq ď O ppoly pr, k,Bqq almost surely. Now applying Hoeffding inequality we obtain our desired result.

Review summaries:
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. The algorithm works on any symmetric input data. The techniques in this paper combines two previous approaches: 1. the algorithm Convotron for learning a single convolutional filter (while the second layer has fixed weight) on any symmetric input distributions; 2. non-convex optimization for low rank matrix factorization.