Title: IMPROVED LEARNING OF ONE-HIDDEN-LAYER CON-VOLUTIONAL NEURAL NETWORKS WITH OVERLAPS Anonymous

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.

1. INTRODUCTION:

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 a j σ `wJ 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 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.

2. PRELIMINARIES:

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 tx i , y i u n i"1 where x i P R d 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: y i " f px i , w ˚, a ˚q, x i " 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 " rP 1 x . . . P k xs P R rˆ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 E x"Z " pf pw, a, xq ´f pw ˚, a ˚, xqq 2 ı ď .

Algorithm 1 Learning One-hidden-Layer Convolutional Network

Input: Input distribution Z. Number of iterations: T 1 , T 2 . Number of samples: T 3 .

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 T 1 iterations with step size η 1 to obtain a pT1q . 2: Stage 2: Run Convotron (Algorithm 3) using a pT1q and ´apT1q for T 2 iterations and step size η 2 to obtain w p`q and w p´q . 3: Stage 3: Choose parameters with lower empirical loss on T 3 samples drawn from Z from `wp`q , a pT q ˘and `wp´q , ´apT q ˘.

3. MAIN RESULT:

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.

3.1. ASSUMPTIONS:

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: E x"Z " xx T ‰ " 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 r 2 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 .

3.2. ALGORITHM:

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 r 2 u `1, for j " 1. . . . , k we define the selection matrix for the non-overlapping part of each patch Note that for any j 1 ‰ j 2 , there is no overlapping between the selected coordinates by P non j1 and P non j2 . Therefore, for a filter w, there is a segment rw r´s`1 , . . . , w s s with length p2s ´rq which acts on the non-overlapping part of each patches. We denote w non " rw r´s`1 , . . . , w s s and our goal in this stage is to learn w non and a ˚jointly.

In this stage, our algorithm proceeds as follows. Given w non , a and a sample px, yq, we define

g pw non , a, x, yq " 2 1 `γ ´f pw non , a, xq ´y¯k ÿ j"1 a i P non j x `1 4 ´}w non } 2 2 ´}a} 2 2 ¯wnon (2) h pw non , a, x, yq " 2 1 `γ ´f pw non , a, xq ´y¯¨w J non P non 1 x . . . w J non P non k x ‚`1 4 ´}a} 2 2 ´}w non } 2 2 ¯a (3)

where f pw non , a, xq " ř k j"1 a j σ `wJ non P non j

x ˘is the prediction function only using w non .

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

1 4 ´}w non } 2 2 ´}a} 2 2 ¯wnon and 1 4 ´}a} 2 2 ´}w non } 2 2 ¯a are is the gradient induced by the regularization 1 4 ´}w non } 2 2 ´}a} 2 2 ¯2

, which is used to balance the magnitude between w non and a and make the algorithm more stable.

With some initialization w p0q non and a p0q , we use the following iterative updates inspired by isotonic regression (Goel et al., 2018) , for t " 0, . . . , T 1 ´1

w pt`1q non Ðw ptq non ´η1 g ´wptq non , a ptq , x ptq , y ptq ¯`η 1 ξ ptq wnon , (4)

a pt`1q Ða ptq ´η1 h ´wptq non , a ptq , x ptq , y ptq ¯`η 1 ξ ptq a (5)

where η 1 ą 0 is the step size parameter, ξ ptq wnon and ξ ptq a are uniformly sampled a unit sphere and at iteration we use a fresh sample `xptq , y ptq ˘. Here we add isotropic noise ξ ptq wnon 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 , a pT1q ˘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 w non " w.

Stage 2: Convotron with fixed Linear Layer In Stage 1 we have learned a good approximation to the second layer (either a pT1q or ´apT1q ). Therefore, the problem reduces to learning a convolutional filter. We run Convotron (Algorithm 3) proposed in Goel et al. (2018) using a pT1q and ´apT1q to obtain corresponding weight vectors w p`q and w p´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 , a pT 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 Return a pT `1q

Algorithm 3 Convotron (Goel et al., 2018) Initialize w 1 :" 0 P R r . for t " 1 to T do Draw px ptq , y ptq q " Z Let g ptq " py ptq ´f pw ptq , a, x ptq qq ´řk i"1 a i P i x ptq Set w pt`1q " w ptq `ηg ptq Return w T `1 the right one. To do this, we simply use T 3 " poly `k, B, 1 ˘fresh samples and output the solution which gives lower squared error.

pw, aq ":

arg min pw,aqPtpw p`q ,a pT q q,pw p´q ,´a pT q qu 1 T 3

EQUATION

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.

3.3. MAIN THEOREM:

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 T 1 , T 2 , T 3 " Ω `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

E x"Z " pf pw, a, xq ´f pw ˚, a ˚, xqq 2 ı ď .

4. PROOFS AND TECHNICAL INSIGHTS:

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.

4.1. ANALYSIS OF STAGE 1:

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 " w J P pxq a " xP pxq , wa J y.

The label also admits this form y " xP pxq , w ˚pa ˚qJ y. A natural way to learn w ˚and a ˚is to consider solving a square loss minimization problem: min pw, a, xq " ´xP pxq , wa J y ´xP pxq , w ˚pa ˚qJ y ¯2 . Now, taking expectation with respect to x, we have

L pw, aq " › › ›wa J ´w˚p a ˚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 L 2 loss is just the standard loss for rank-1 matrix factorization problem.

Recent advances in non-convex optimization shows the following regularized loss function

EQUATION

)

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

EQUATION

)

where `xptq , y ptq ˘is the sample we use in the t-th iteration. In expectation this is the standard gradient descent algorithm for solving equation 8:

E x " g ptq w ı " BL reg `wptq , a ptq Bw ptq , E x " g ptq a ı " BL reg `wptq , a ptq Ba ptq .

With this stochastic gradient oracle at hand, we can implement the noise-injected stochastic gradient descent proposed in Ge et al. (2015) .

w pt`1q " w ptq ´ηg ptq w `ηξ ptq w , a pt`1q " w ptq ´ηg ptq a `ηξ ptq a where ξ ptq w 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

L reg pw non , aq " 1 2 › › ›wnona J ´wn on pa ˚qJ › › › 2 F `1 8 ´}w non } 2 2 ´}a} 2 2 ¯2 .

Under Assumption 3.1, we have 

E x rg

› › › › ď D, › › › › h pw non , a, x, yq ´BL reg pw non , aq Ba › › › › 2 ď D

for some D " O ppoly pB, k, σ 1 qq.

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) " Oppoly pσ 1 qq, }a t } 2 " Oppoly pσ 1 qq. 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 w p0q " O `?σ 1 ˘, a p0q " O `?σ 1 ˘, and

η 1 " O `poly `1 k , 1 B , ˘˘then after T 1 " O `poly `r, k, B, 1 ˘˘we have › › › › › a pT1q › › a pT1q › › 2 ´a} a ˚}2 › › › › › 2 ď . or › › › › › a pT1q › › a pT1q › › 2 `a} a ˚}2 › › › › › 2 ď .

4.2. ANALYSIS OF STAGE 2:

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 k 3 }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 ď Opk 3 }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 P a :" ř 1ďi,jďk a i a j P i P T j . By simple algebra, we can show that the matrix has the following form:

P a pi, jq " $ ' & ' % 1 if i " j ř k´1 i"1 a i a i`1 if |i ´j| " s 0 otherwise.

Using property of Toeplitz matrices, we show the least eigenvalue of P a is lower bounded by 1 ćos ´π k`1 ¯(c.f. Theorem A.2) for all a with norm 1.

4.3. ANALYSIS OF STAGE 3:

Here we show how we can pick the correct hypothesis from the two possible hypothesis. Under our assumptions, the individual loss py piq ´f pw, a, x piq qq 2 is bounded. sThus, a direct application of Hoeffding inequality gives the following guarantee.

Theorem 4.3. Suppose T 3 " Ω `poly `r, k, B, 1 ˘˘and let pw, aq. If either `wp`q , a T1 ˘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 ´ r 1{2 k 5{2 σ1 ¯(without loss of generality, we assume a and

E x"Z " f pw, a, x ´f pw ˚, a ˚, xqq 2 ‰ ď .

a ˚are normalized) with η 1 " O ´poly ´1 k , 1 B , 1 σ1 , ¯¯and |S 1 | " poly `r, k, B, σ 1 , 1 ˘. Now with Theorem 4.2, we know with η " O `poly `1 k , 1 B ˘˘and |S 2 | " O `poly `k, σ 1 , log 1 ˘we have either › › w p`q ´w˚› › 2 ď σ1r 1{2 k 3{2 or › › w p´q ´w˚› › 2 ď σ1r 1{2 k 3{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} 2 2 }w ´w˚} 2 2 `}a ´a˚} 2 2 }w ˚}2 2 ¯}x} 2 2 .

Therefore, we know either `wp`q , a pT1q ˘or `wp´q , ´apT1q ˘achieves prediction error. Now combining Theorem 4.3 and Lemma A.1 we obtain the desired result.

5. EXPERIMENTS:

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 " a pT1q 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 a t an a ˚(in radians). We first test Gaussian input distribution x " N p0, Iq. Figure 1a shows the convergence in Stage 1 of Algorithm 1 with T 1 " 10000 and η 1 " 0.0001. Figure 1b shows the convergence in Stage 2 of Algorithm 1 with T 2 " 10000 and η 2 " 0.0001. We then test uniform input distribution x " Unifr´?3, ? 3s d (this distribution has identity covariance). Figure 1c shows the convergence in Stage 1 of Algorithm 1 with T 1 " 40000 and η 1 " 0.0001. Figure 1d shows the convergence in Stage 2 of Algorithm 1 with T 2 " 100000 and η 2 " 0.00001. Note for both input distributions and all choices of stride size, our algorithm achieves low test error..

6. CONCLUSION AND FUTURE WORK:

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.

A USEFUL LEMMAS/THEOREMS:

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, xqq 2 `pf pw ˚, a, xq ´f pw, a, xqq 2 since pa `bq 2 ď 2 `a2 `b2 ˘for all a, b P R.

The first term can be bounded as follows,

pf pw ˚, a ˚, xq ´f pw ˚, a, xqq 2 " ˜k ÿ i"1 pa i ´ai q σ ´pw ˚qT P i x ¯¸2 ď ˜k ÿ i"1 |a i ´ai || pw ˚qT P i x| ¸2 ď ˜k ÿ i"1 |a i ´ai | }w ˚}2 }x} 2 ¸2 ď k }a ˚´a} 2 2 }w ˚}2 2 }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 R k .

Similarly, the other term can be bounded as follows, pf pw ˚, a, xq ´f pw, a, xqq 2 " ˜k ÿ

i"1 a i ´σ ´pw ˚qT P i x ¯´σ `wT P i x ˘¯¸2 ď ˜k ÿ

i"1

|a i || pw ˚´wq T P i x| ¸2 ď ˜k ÿ i"1 |a i | }w ˚´w} 2 }x} 2 ¸2 ď k }a} 2 2 }w ˚´w} 2 2 }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} 2 2 }w ´w˚} 2 2 `}a ´a˚} 2 2 }w ˚}2 2 ¯.

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 R n , if Z is symmetric then,

E x"Z rσ `aT x ˘`b T x ˘s " 1 `α 2 E x"Z r `aT x ˘`b T x ˘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 R i :" ř n j"1,j‰i |A i,j |. Each eigenvalue of A must lie in at least one of the disks tz : |z ´Ai,i | ď R i u.

The following lemma bounds the eigenvalue of the weighted patch matrices. Theorem A.2. For all a P S k´1 , λ min pP a q ě 1 ´cos ˆπ k `1 ˙and λ max pP a q ď 1 `cos ˆπ k `1 ˙.

Proof. Since s ě t r 2 u `1, only adjacent patches overlap, and it is easy to verify that the matrix P a has the following structure:

P a pi, jq " $ ' & ' % 1 if i " j ř k´1 i"1 a i a i`1 if |i ´j| " s 0 otherwise.

Using the Gershgorin Circle Theorem, stated below, we can bound the eigenvalues, λ min pP a q ě 1 ´ˇˇřk´1 i"1 a i a i`1 ˇˇand λ max pP a q ď 1 `ˇˇřk´1

i"1 a i a i`1 ˇˇ.

To bound the eigenvalues, we will bound ˇˇř k´1 i"1 a i a i`1 ˇˇby maximizing it over all a such that }a} 2 " 1. We have max

!ˇˇˇř k´1 i"1 a i a i`1 ˇˇ) " max ! ř k´1 i"1 a i a i`1

) since the maximum can be achieved by setting all a i to be non-negative. This can alternatively be viewed as max }a} 2 "1 a T Ma " λ 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. Boeóttcher & Grudsky (2005) ). The maximum eigenvalue is thus cos ´π k`1 ¯. This gives us the result. Because the input distribution is symmetric and the covariance is identity, by Lemma A.2, we have The proof for h pw non , a, x, yq is similar.

B OMITTED PROOFS:

EQUATION

To obtain a bound of the gradient, note that 

EQUATION

P i P T j ´w˚´wptq ¯(13) ě 1 `α 2 ¨λmin pP a q › › ›w ptq ´w˚› › › 2 2 ´}w ˚}2 › › › › › ÿ 1ďiďk pa i ´ai q P i › › › › › 2 › › › › › ÿ 1ďjďk a j P j › › › › › 2 › › ›w ptq ´w˚› › › 2 ‚ (14) ě 1 `α 2 ˆλmin pP a q › › ›w ptq ´w˚› › › 2 2 ´k }w ˚} }a ˚´a} 2 }a} 2 › › ›w ptq ´w˚› › › 2 ě 1 `α 2 ˆλmin pP a q › › ›w ptq ´w˚› › › 2 2 ´k }w ˚}2 › › ›w ptq ´w˚› › › 2 (11)

follows from using Lemma A.2, (13) follows from defining P a :" ř 1ďi,jďk a i a j P i P T j , (12) follows from setting the covariance matrix to be identity and ( 14) follows from observing that P a is symmetric, thus @x, x T P a x ě λ min pP a q }x} 2 2 as well as lower bounding the second term in terms of the norms of the corresponding parts. for β " 1`α 2 λ min pP a q, γ " 2λ max pP a q kB, δ " 1`α 2 k }w ˚}2 and χ " 2λ max pP a q kB }w ˚}2 2 .

From Theorem A.2, we have that λ min pP a q " 1 ´cos ´π k`1 ¯" Ω `1{k 2 ˘(by Taylor expansion) implying β " ω `1{k 2 ˘and γ " O pkBq, χ " O ´kB }w ˚}2 2 ¯.

We set η " β min ´1 γ , 1 χ ¯. First we show that E St´1 r › › w ptq ´w˚› › 2 2 s ď 1 for all iterations t. We prove this inductively. For t " 1, since w 1 " 0, this is satisfied. Let us assume it holds for iteration t, then we have that, 

E

:

Note that we can assume that the outer layers have norm 1 by using the normalized weight vectors since the activations are scale invariant.

Figures and Tables:

Figure 1: Evaluation of Algorithm 1. Gaussian input (G): 1a and 1b. Uniform input (U): 1c and 1d. 4.4 PUTTING THINGS TOGETHER: PROOF OF THEOREM 3.1 Now we put our analyses for Stage 1-3 together and prove Theorem 3.1. By Theorem 4.1, we know we have a pT1q such that › › a T1 ´a˚› › ď O

R 2s´r and a p0q P R k randomly for t " 1 to T do Draw px ptq , y ptq q " Z Compute g `wnon , a, x ptq , y ptq ˘and h `wnon , a, x ptq , y ptq ˘according to equation 2 and equa-

Table content: <table><tr><td>Algorithm 2 Double Convotron</td><td/></tr><tr><td>Initialize w non P tion 3. p0q Set w pt`1q non " w non ´η1 g ptq</td><td>´wptq</td></tr></table>

pw non , a, x, yqs " BL reg pw non , aq Bw non , E x rh pw non , a, x, yqs " BL reg pw non , aq Ba where g pw non , a, x, yq and h pw non , a, x, yq are defined in equation 2 and equation 3, respectively. Further, if }w non } 2 " Oppoly pσ 1 qq, }a} 2 " Oppoly pσ 1 qq, then the differences are also bounded

Table content: <table><tr><td>› › › › g pw non , a, x, yq</td><td>´BL reg pw non , aq Bw non</td></tr></table>

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 ofGoel 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.

Table content: <table><tr><td>Now with Lemma 4.1 at hand, we can use the theory from non-convex matrix factorization. Ge</td></tr><tr><td>et al. (2017a) has shown if η 1 " O `poly `1 k , 1 B , ˘˘then for all iterates, with high probability, › › ›w › ptq › non › 2</td></tr></table>

Thus E x rg pw non , a, x, yqs " BL reg pw, aq Bw .

Table content: <table><tr><td/><td/><td/><td/><td/><td colspan="2">2 w non .</td></tr><tr><td>Similarly, we have</td><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td>«</td><td>k</td><td/><td>ff</td></tr><tr><td/><td colspan="2">E x</td><td>y</td><td>ÿ</td><td>a j P non j</td><td>x</td><td>" a J a ˚w˚.</td></tr><tr><td/><td/><td/><td/><td colspan="2">j"1</td></tr><tr><td>Also recall</td><td/><td/><td/><td/><td/></tr><tr><td>BL reg pw, aq Bw</td><td>" }a}</td><td colspan="3">2 2 w non</td><td colspan="2">´aJ a ˚w˚`1 4</td><td>´}w non } 2 2 ´}a} 2 2 ¯wnon .</td></tr></table>

We follow the Convotron analysis and include the changes. Define S t " tpx 1 , y 1 q , . . . , px t , y t qu.|S t´1 s " 2ηE xt,yt r ´w˚´wptq ¯T g ptq |S t´1 s´η 2 E xt,yt r||g ptq || 2 |S t´1 s. xt r ˆai σ ´pw ˚qT P i x t ¯´a i σ ˆ´w ptq ¯T P i x t

Table content: <table><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>2 }x} 2 2 }w} 2</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>"poly pk, σ 1 , Bq .</td></tr><tr><td colspan="11">Similar argument applies to y</td><td colspan="4">ř k j"1 a j P non j</td><td>x.</td></tr><tr><td colspan="13">B.2 PROOF OF THEOREM 4.2</td><td/></tr><tr><td colspan="15">The modified gradient update is as follows,</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>Ţhe</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="6">g ptq " ´yt</td><td>´f ´wptq , a, x t</td><td>¯¯˜k ÿ</td><td>a i P i x t</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>i"1</td></tr><tr><td/><td colspan="14">dynamics of Convotron can then be expressed as follows:</td></tr><tr><td colspan="6">E xt,yt r › › ›w ptq ´w˚› › › 2 2</td><td colspan="9">´› › ›w pt`1q ´w˚› › ›</td><td>2 2</td></tr><tr><td colspan="4">We have,</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td>"</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td></td></tr><tr><td colspan="3">E xt,yt</td><td colspan="10">´w˚´wptq ¯T g ptq |S t´1</td><td/></tr><tr><td/><td/><td/><td/><td>«</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>¸ˇˇˇˇS</td><td>ff</td></tr><tr><td colspan="4">" E xt,yt</td><td colspan="4">´w˚´wptq</td><td colspan="4">¯T ´yt</td><td colspan="3">´f ´wptq , a, x t</td><td>¯¯˜k ÿ</td><td>a i P i x t</td><td>t´1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>i"1</td></tr><tr><td/><td/><td colspan="2">«</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>¸ˇˇˇˇS</td><td>ff</td></tr><tr><td colspan="3">" E xt</td><td colspan="4">´w˚´wptq</td><td colspan="8">¯T ´f pw ˚, a ˚, x t q</td><td>´f ´wptq , a, x t</td><td>¯¯˜k ÿ</td><td>a i P i x t</td><td>t´1</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>i"1</td></tr><tr><td>"</td><td/><td colspan="2">ÿ</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>˙˙ˆa j pw</td><td>˚qT ´aj</td><td>´wptq</td><td>¯T ˙Pj x t |S t´1 s</td></tr><tr><td/><td colspan="4">1ďi,jďk</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>"</td><td>1</td><td colspan="2">`α 2</td><td>1ďi,jďk ÿ</td><td colspan="2">E xt</td><td colspan="3">"ˆˆa</td><td colspan="3">i pw</td><td colspan="2">˚qT ´ai</td><td>´wptq</td><td>¯T ˙Pi x t ˙ˆa j pw</td><td>˚qT ´aj</td><td>´wptq</td><td>¯T ˙Pj x t |S t´1</td><td></td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>(11)</td></tr><tr><td>"</td><td>1</td><td colspan="2">`α 2</td><td>1ďi,jďk ÿ</td><td colspan="4">ˆai pw</td><td colspan="5">˚qT ´ai</td><td>´wptq</td><td>¯T ˙Pi E xt rx t x T t sP T j ´aj w ˚´a j w ptq ¯(12)</td></tr><tr><td>"</td><td>1</td><td colspan="2">`α 2</td><td>1ďi,jďk ÿ</td><td colspan="4">ˆai pw</td><td colspan="6">˚qT ´ai pw</td><td>˚qT `ai pw</td><td>˚qT ´ai</td><td>´wptq</td><td>¯T ˙Pi P T j ´aj w ˚´a j w ptq</td><td>"</td></tr><tr><td/><td/><td/><td/><td>˜´pw</td><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td>1</td><td colspan="2">`α 2</td><td colspan="6">˚qT ´pw</td><td/><td/><td/><td/></tr></table>

Now we bound the variance of g ptq .E xt,yt r||g ptq || 2 |S t´1 s " E xt,ytCombining the above equations and taking expectation over S t´1 , we get

Table content: <table><tr><td/><td>» -´yt</td><td colspan="3">´f ´wptq , a, x t</td><td colspan="3">¯¯2 ˇˇˇˇˇˇˇˇk ÿ</td><td>a i P i x t</td><td>ˇˇˇˇˇˇˇˇ2 ˇˇˇˇˇS</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td>i"1</td></tr><tr><td/><td/><td/><td>2 2</td><td colspan="3">› › ›w ptq ´w˚› › › 2 2</td><td>`}a ´a˚} 2 2 }w</td><td>˚}2 2 ˙Ext</td><td>" }x t } 4 2</td><td>ı</td><td>(16)</td></tr><tr><td colspan="3">ď 2kBλ max pP a q</td><td colspan="3">ˆ› › ›w ptq ´w˚› › › 2 2</td><td colspan="2">` 2 }w</td><td>˚}2 2 ˙(17)</td></tr><tr><td colspan="4">(15) follows from observing that ˇˇˇˇř</td><td/><td/><td/><td>2 2 for all x and (16) follows from</td></tr><tr><td>Lemma 4.2.</td><td/><td/><td/><td/><td/><td/></tr><tr><td>E St r › › ›w pt`1q ´w˚› › › 2 2</td><td colspan="7">s ď `1 ´2ηβ `η2 γ ˘ESt´1 r › › ›w ptq ´w˚› › › 2 2</td><td>› s `2ηα E St´1 r › ›w ptq ´w˚› › › 2</td><td>s `η2 χ 2</td></tr><tr><td/><td colspan="7">ď `1 ´2ηβ `η2 γ ˘ESt´1 r › › ›w ptq ´w˚› › › 2 2</td><td>s `2ηδ</td><td>b E St´1 r › › w ptq ´w˚› › 2 2 s `η2 χ 2</td></tr></table>

Thus for T " O ´1 ηβ log `1 ˘¯, we have, Now using Markov's inequality, we know that the above holds for some constant probability.B.3 PROOF OF THEOREM 4.3For i " T 2 `1, . . . , T 3 , define z piq " `ypiq ´f `w, a, x piq ˘˘2 . Using our assumptions, we know z piq ď O ppoly pr, k, Bqq almost surely. Now applying Hoeffding inequality we obtain our desired result.

Table content: <table><tr><td>us,</td><td/><td/><td/><td/></tr><tr><td colspan="2">E St r › › ›w pt`1q ´w˚› › ›</td><td>2 2</td><td colspan="3">s ď `1 ´2ηβ `η2 γ ˘ESt´1 r › › ›w ptq ´w˚› › ›</td><td>2 2</td><td>s `2ηδ `η2 χ 2</td></tr><tr><td/><td/><td/><td colspan="3">ď p1 ´ηβq E St´1 r › › ›w ptq ´w˚› › › 2 2</td><td>s `2ηδ `ηβ 2</td></tr><tr><td/><td/><td/><td colspan="3">ď p1 ´ηβq t }w 1</td><td>´w˚} 2 2 ``2ηδ `ηβ 2 ˘t´1 ÿ</td><td>p1 ´ηβq i</td></tr><tr><td/><td/><td/><td/><td/><td>i"0</td></tr><tr><td/><td/><td/><td colspan="2">ď p1 ´ηβq</td><td>t `2δ β</td><td>` 2</td></tr><tr><td/><td colspan="5">E St r › › ›w pt`1q ´w˚› › › 2 2</td><td>s ď O</td><td>ˆδ β</td><td>˙" O `k3 }w ˚}2</td><td>˘.</td></tr><tr><td>St r › › ›w pt`1q ´w˚› › › 2 2</td><td colspan="5">s ď `1 ´2ηβ `η2 γ ˘ESt´1 r › › ›w ptq ´w˚› › › 2 2</td><td>s `2ηδ</td><td>b E St´1 r › › w ptq ´w˚› › 2 2 s `η2 χ 2</td></tr><tr><td/><td colspan="5">ď 1 ´2ηβ `η2 γ `2ηδ `η2 χ 2</td></tr><tr><td/><td colspan="5">ď 1 ´2ηβ `ηβ `2ηδ `ηβ</td></tr><tr><td/><td colspan="5">ď 1 ´η pβ ´pδ `βq q ď 1</td></tr><tr><td colspan="4">The last inequality follows from ď</td><td colspan="2">1 k 3 }w ˚}2</td><td>ď β δ`β . Thus we have that for each iteration,</td></tr><tr><td colspan="6">E St´1 r › › w ptq ´w˚› › 2 2 s ď 1. Substituting this in the recurrence and solving the recurrence gives</td></tr></table>

Peer review (iclr2019):
 I believe the authors need to give more intuition on the importance of such a study, and how it can lead to improvement in real life application. The work seems interesting but is limited and as the authors mentioned it might be a good start for further investigation. However, what I really wanted to see was a simple comparison on a dataset like MNIST with conventional CNN being trained via SGD, for example. Also, there are some small typos you may need to fix, e.g "will be play" -> "will be playing".