Title: PROVABLE GUARANTEES ON LEARNING HIERARCHI-CAL GENERATIVE MODELS WITH DEEP CNNS

Abstract: Learning deep networks is computationally hard in the general case. To show any positive theoretical results, one must make assumptions on the data distribution. Current theoretical works often make assumptions that are very far from describing real data, like sampling from Gaussian distribution or linear separability of the data. We describe an algorithm that learns convolutional neural network, assuming the data is sampled from a deep generative model that generates images level by level, where lower resolution images correspond to latent semantic classes. We analyze the convergence rate of our algorithm assuming the data is indeed generated according to this model (as well as additional assumptions). While we do not pretend to claim that the assumptions are realistic for natural images, we do believe that they capture some true properties of real data. Furthermore, we show that on CIFAR-10, the algorithm we analyze achieves results in the same ballpark with vanilla convolutional neural networks that are trained with SGD.

1. INTRODUCTION:

The success of deep convolutional neural networks (CNN) has sparked many works trying to understand their behavior. As various theoretical studies have shown, learning deep networks is computationally hard in the general case, when no assumptions on the distribution of the data are taken (see for example Livni et al. (2014) ). In practice, learning CNNs is done successfully using simple gradient-based optimization algorithms like SGD. Hence, to provide a theoretical analysis that will explain the practical success of deep learning, one must make assumptions on the distribution of the learned data. Currently, theoretical works in the literature of deep learning make rather strong assumptions, that clearly do not capture the properties of natural data. For example, many works assume that the examples are sampled from a Gaussian distribution, an assumption that is very far from describing distributions on natural images. Other works assume linear separability of the data, which clearly does not hold for any rich enough dataset.

In this work, we assume the data is generated from a deep generative model. According to this model, the examples are generated in a hierarchical manner: each example (image) is generated by first drawing a high-level semantic image, and iteratively refining the image, each time generating a lower-level image based on the higher-level semantics from the previous step. Similar models were suggested in other works as good descriptions of natural images encountered in real world data. While we do not claim that natural images actually come from such distribution, we believe that it captures some key properties of real world data. Importantly, the problem we study is not trivially learned by simple "shallow" learning algorithms.

Our work analyzes the training of a CNN on data from this generative distribution. In a shallow case, where the generative model has only two levels of hierarchy, we analyze the behavior of standard gradient-descent. In the deep case, where our model can have many levels of hierarchy, we analyze a layerwise optimization algorithm, proving its convergence under the assumed generative model (as well as additional, admittedly strong, assumptions). The algorithm we analyze is somewhat different than optimization algorithms that are commonly used in practice, and may seem "tailored" to solve the problem of learning our generative heirarchical model. We show that implementing this algorithm to learn real-world data (CIFAR-10 dataset) achieves performance that are in the same ballpark as a vanilla CNN trained with SGD-based optimizer. This result hints that our model and algorithm indeed capture properties of distributions and algorithms that are common in practice.

2. RELATED WORK:

Any theoretical work that aims to give positive results on learning deep networks must make assumptions on the data distribution and on the learning algorithm. We can roughly divide such works into three categories: (1) works that study practical algorithms (SGD) solving "simple" problems that can be otherwise learned with "shallow" algorithms. (2) works that study problems with less restrictive assumptions, but using algorithms that are not applicable in practice. (3) works that study a generative model similar to ours, but either give no theoretical guarantees, or otherwise analyze an algorithms that are not applicable for learning CNNs on image data.

Trying to study a practically useful algorithm, Daniely (2017) proves that SGD learns a function that approximates the best function in the conjugate kernel space derived from the network architecture. Although this work provides guarantees for a wide range of deep architectures, there is no empirical evidence that the best function in the conjugate kernel space performs at the same ballpark as CNNs. The work of Andoni et al. (2014) shows guarantees on learning low-degree polynomials, which is learnable via SVM or direct feature mapping. Other works study shallow (one-hidden-layer) networks under some significant assumptions. The works of Gori & Tesi (1992) ; Brutzkus et al. (2017) study the convergence of SGD trained on linearly separable data, which could be learned with the Perceptron algorithm, and the works of Brutzkus & Globerson (2017) ; Tian (2017) ; Li & Yuan (2017) ; Zhong et al. (2017) assume that the data is generated from Gaussian distribution, an assumption that clearly does not hold in real-world data. The work of Du et al. (2017) extends the results in Brutzkus & Globerson (2017) , showing recovery of convolutional kernels without assuming Gaussian distribution, but is still limited to the regime of shallow two-layer network.

Another line of work aims to analyze the learning of deep architectures, in cases that exceed the capacity of shallow learning. The works of Livni et al. (2014) ; Zhang et al. (2015; 2016a) show polynomial-time algorithms aimed at learning deep models, but that seem far from performing well in practice. The work of Zhang et al. (2016b) analyses a method of learning a model similar to CNN which can be applied to learn multi-layer networks, but the analysis is limited to shallow two-layer settings, when the formulated problem is convex.

Finally, there have been a few works suggesting distributional assumptions on the data that are similar in spirit to the generative model that we analyze in this paper. Again, these works can be largely categorized into two classes: works that provide algorithms that have theoretical guarantees but are not applicable for learning CNNs, and works that show practical results without theoretical guarantees. The work of Arora et al. (2014) shows a provably efficient algorithm for learning a deep representation, but this algorithm seems far from capturing the behavior of algorithms used in practice. Our approach can be seen as an extension of the work of Mossel (2016) , who studies Hierarchal Generative Models, focusing on algorithms and models that are applicable to biological data. Mossel (2016) suggests that similar models may be used to define image refinement processes, and our work shows that this is indeed the case, while providing both theoretical proofs and empirical evidence to this claim. Finally, the works of Tang et al. (2012); Patel et al. (2016) ; Van den Oord & Schrauwen (2014) study generative models similar to ours, with promising empirical results when implementing EM inspired algorithms, but giving no theoretical foundations whatsoever.

3. DISTRIBUTIONAL ASSUMPTIONS:

In this paper, we are concerned with the problem of learning binary classification of images. Assume we are given a sample S = {(X 1 , y 1 ), . . . , (X n , y n )} from some distribution D on R m×m × Y, where Y = {±1} is our labels. We wish to learn a CNN model that will classify the images correctly. As noted, if we hope to give any guarantees on the success of learning such model, we must make strong assumptions on the distribution D. One naive assumption on D is that it is linearly separable: there exists W * ∈ R m×m such that y W * , X ≥ 1 for (X, y) ∼ D, where we denote A, B = tr(A B). Clearly, such assumption does not hold for any rich enough distribution of natural images (as linear classifiers give poor results on natural image datasets).

To provide a more realistic assumption, we will instead assume the following:

Assumption 1 The images in D are generated from a latent distribution G 0 , such that G 0 is linearly separable.

X (0) ∈C 5×4 0 X (1) ∈C 10×8 1 • • • X∈R 640×512 U { , , , . . . } C 0 = { , , , , , . . . }, C 1 = { , , , . . . } Figure 1: Generative model schematic description

Thus, sampling an image (X, y) ∼ D is equivalent to sampling a latent representation (X (0) , y) ∼ G 0 , and then sampling (X, y) ∼ G X (0) , where G X (0) is a distribution dependent on X (0) . Note that in this case, the distribution D can be very complex, although the images sampled from it have a latent representation that is relatively simple. To give a concrete description of the latent representation, we will assume that G 0 is a distribution over "semantic images": images where each "pixel" represents a semantic class. Formally, we will assume that X (0) ∈ C m0×m0

0:

, where C 0 is some finite set of "semantic classes". Now, we want to describe the generative process of generating the image X from the semantic representation X (0) . This process is done in a hierarchical manner: Given the high-level semantic representation X (0) , where each "pixel" represents a semantic class (for example, background, sky, grass etc.), we generate a lower level image X (1) , where each patch comes from a distribution depending on each "pixel" of the high-level representation, generating a larger semantic image (lower level semantic classes for natural images could be: edges, corners, texture etc.). We can repeat this process iteratively any number of times, each time creating a larger image of lower level semantic classes, thus generating a sequence of increasingly large semantic images X (0) , X (1) , . . . , X (d) . Since D is a distribution over greyscale images, we will assume that the last iteration of this process samples patches over R, i.e X = X (d) ∈ R m×m . This model is described schematically in figure 1 , with a formal description given in section 3.1. In section 3.2 we describe a synthetic example of digit images generated according to this model.

3.1. FORMAL DESCRIPTION:

Here, we will give a detailed description of the generative process described above. To generate an example, we start by sampling the label y ∼ U (Y), where U (Y) is the uniform distribution over the set of labels. Given y, we generate a small image with m 0 × m 0 pixels, where each pixel belongs to a set C 0 . Elements of C 0 corresponds to semantic entities (e.g. "sky", "grass", etc.). The generated image, denoted X (0) ∈ C m0×m0 0 , is sampled according to some simple distribution D y . Next, we generate a new image X (1) ∈ C m0s×m0s 1 as follows. Pixel i in X (0) corresponds to some c ∈ C 0 . For every such c, let D c be the uniform distribution over a finite set of patches S , where we refer to s as a "patch size". We assume the following:

Assumption 2 The sets {S (0) c } c∈C0 are disjoint, and each one is of size k.

So, pixel i in X (0) whose value is c ∈ C 0 generates a patch of size s in X (1) by sampling the patch according to D c . This process continues, yielding images X (2) , . . . , X (d) whose sizes are m 0 s 2 × m 0 s 2 , . . . , m 0 s d × m 0 s d . Each pixel in level i comes from C i , and each patch comes from S (i-1) c for some c ∈ C i-1 . We assume that C d = R, so the final image is over the reals. The observed example is the pair (X (d) , y). We denote the distribution generating the image of level i by G i .

As noted, we assume that G 0 , the distribution that generates the high-level semantic images, is linearly separable. As G 0 is a distribution over semantic images, i.e over C m×m 0 × Y, we need to define what "linear separability" means in this case. To do this, we assign to the i-th class in C 0 the unit vector e i ∈ R |C0| . Then we represent X ∈ C m×m 0 with an equivalent tensor X ∈ R |C0|×m×m , and define linear separability with respect to the tensor representation. Namely, there exists W * such that for (X, y) ∼ G 0 it holds that y X, W * ≥ 1, where X, W * := i,j,k X i,j,k • W * i,j,k . Notice that our semantic classes partition the patches in the image into disjoint sets. There are various ways to partition the patches, some of which might in fact generate the same distribution. For the analysis, we add an assumption that ensures that the semantic classes defined in the model are different enough from each other. We identify each class with a matrix that captures the frequency of its appearance in the image, with respect to the label of the image. For this, we define the "labeled frequency matrix" of class c ∈ C i to be the matrix F c ∈ R m0s i ×m0s i defined as follows: for every c we denote by I c the operator that takes a matrix as its input and replaces every element of the input by the boolean that indicates whether it equals to c. Then, we define:

F c := E (Z,y)∼Gi [yI c (Z)].

Notice that F c is the "mean" image over the distribution for every given semantic class c. For example, semantic classes that tend to appear in the upper-left corner of the image for positive images will have positive values in the upper-left entries of F c . We now assume:

Assumption 3 The vectors {F c } c∈Ci are linearly independent in pairs.

For each c 1 , c 2 ∈ C i we denote the angle between F c1 and F c2 by: ∠(F c1 , F c2 ) := arccos

Fc 1 Fc 2 Fc 1 F Fc 2 F . Denote θ := min i,c1,c2∈Ci ∠(F c1 , F c2

) and λ := min i,c∈Ci F c F . From the linear independence assumption it follows that both θ and λ are strictly positive. The runtime of the algorithms described in the next sections depend on 1/θ and 1/λ.

3.2. SYNTHETIC DIGITS EXAMPLE:

To demonstrate our generative model, we use a small synthetic example to generate images of digits. In this case, we use a three levels model, where semantic classes represent lines, corners etc. In the notations above, we use:

C 0 = { , , , , , , , , } , C 1 = { , , , , , } , C 2 = R

We define D even , D odd to be the uniform distributions over the even/odd digital representations: 2 shows the process output.

D even = U { , , , , }, D odd = U { , , , , } Now,

3.3. LINEAR SEPARABILITY:

While the generative model described above seems complex, one might wonder whether this model, along with all the distributional assumptions given so far, is in fact an overly complicated fashion to describe a rather simple problem. While generally speaking, it is not clear how to measure the "complexity" of the suggested distribution, we can at least address the question of whether this distribution is linearly separable or not.

It is immediate to show that when all the generated patches are orthogonal to each other, this distribution becomes linearly separable. We analyze this case in the next section, and prove some results in this simplistic case. On the other hand, when such assumption is not taken, we argue that the model is typically far from being linearly separable. To show this, we generate examples using this generative distribution, where the generated patches are chosen randomly. Recall that learning a linear separator is a convex problem. Therefore, if the generated data was linearly separable, finding such a separator would be trivial, using the SGD algorithm. Figure 3 shows the accuracy of the linear classifier, compared to the performance of a simple CNN and our algorithm. As is clear from these results, a linear separator achieves very poor results on this data. Furthermore, to show that the generated distribution does not break Assumption 3, we show the values of θ and λ, as measured on the generated data.

The exact details of the experiment are given in appendix D.

4. TWO-LEVEL MODEL:

As a warm-up, we first limit ourselves to observing distributions with only two levels in the hierarchy. Hence, the process of generating examples is simply: G0 (X (0) , y) G1 (X (1) , y). Furthermore, in this section we add an important assumption on the data distribution:

Assumption 4 The set of patches that compose the images generated by G 1 is orthonormal. Recall that we denoted S (0) c ⊂ C s×s 0 the set of patches that are sampled for each pixel of class c. Our assumption means that ∀P 1 ,

P 2 ∈ {S (0) c } c∈C0 we have P 1 , P 2 = 1 P1=P2 .

Notice that this assumption implies the following lemma:

Lemma 1 Given assumptions 1, 2, 4, G 1 is linearly separable with margin √ k W *

, where W * is the linear separator of G 0 (see section 3.1). Consequently, running linear SVM finds a classifier with zero classification loss on this distribution in O(k W * 2 ) iterations.

While usually in classification problems our goal is to minimize the training loss, in this case we would like to find an algorithm that instead recovers the latent representation X (0) given the raw image X (1) . The reasons for this requirement will become clear in the next section. We will prove that training a two layer linear CNN with gradient-descent (GD) on distribution G 1 implicitly recovers the latent representation, even if G 0 is not linearly separable. Note that this is a rather surprising result, as we are only observing (X (1) , y), and have no access to the latent representation X (0) . The following section will give the details of this result: in section 4.1 we describe the details of the GD algorithm, and in section 4.2 we describe the theoretical analysis of this algorithm.

4.1. ALGORITHM: GD ON TWO-LAYER CNN:

Recall that for (X, y) ∼ G 1 , X is an image of size sm 0 × sm 0 , that is composed of s × s patches generated from a high-level semantic image of size m 0 × m 0 . To simplify notation, we consider X to be "reshaped" such that each column is a patch in the original image (the so called "im2col" operation), so

X ∈ R s 2 ×m 2 0 . Given K ∈ R s 2 ×n , W ∈ R m 2 0 ×n , we define a convolutional subnet to be a function N K,W : R s 2 ×m 2 0 → R such that: N K,W (X) = W , K X .

This is equivalent to a convolution operation on an image, followed by a linear weighted sum: multiplying X by K is equivalent to performing a non-overlapping convolution operation with kernels k 1 , . . . , k n on the original image (where k i is the i-th vector of matrix K). Flattening the resulting matrix and multiplying by the weights in W yields the second linear layer.

The top linear layer of the network outputs a prediction for the label y ∈ Y. The network is trained with respect to the loss L S K,W on a given set of examples S, defined as the expected value of some label dependent loss function y : R → R

L S K,W = E (X,y)∼S [ y (N K,W (X))]

For the analysis, we use the loss y (ŷ) = -y ŷ. This loss simplifies the analysis, and seems to capture a similar behavior to other loss types used in practice.

Although in practice we perform a variant of SGD on a sample of the data to train the network, we perform the analysis with respect to the population loss:

L K,W = E (X,y)∼G [ y (N K,W (X))].

We denote K t the weights of the first layer of the network in iteration t, and denote W 0 the initial weights of the second layer. For simplicity of the analysis, we assume that only the first layer of the network is trained, while the weights of the second layer are fixed. Thus, we perform the following update step at each iteration of the gradient descent:

K t = K t-1 -η ∂ ∂K L Kt-1,W0

. We initialize W 0 ∼ N (0, 1) and each n-dimensional column of K 0 is sampled from the uniform distribution on the sphere of radius σ 2 √ n , where σ is a parameter of the algorithm.

4.2. THEORETICAL ANALYSIS:

In this section, we will consider a more general case, where we do not assume that G 0 is linearly separable (Assumption 1). As noted, our main claim in this section is that training the two-layer Conv net implicitly recovers the latent semantic representation of the image. Specifically, we show that gradient-descent finds an embedding of the observed patches into a space such that patches from the same semantic class are close to each other, while patches from different classes are far. Note that this property is indeed enough to recover the latent representation, as running a trivial clustering algorithm on the embedded patches would reconstruct the latent image. Recall that we do not have access to the latent distribution, and thus cannot possibly learn such embedding directly. This surprising property of gradient descent is the key feature that allows our main algorithm (described in the next section) to learn the high-level semantics of the images. Our claim is given in the following theorem:

Theorem 1 Suppose that assumptions 2, 3, 4 hold. Let θ, λ as described in section 3.1. Assume we train a two-layer network of size n > 2π 0.23θ log( |C| δ ) with respect to the population loss on distribution G 1 , with learning rate η, for T > (γ+2σ)k ηλ iterations, for some γ > 0. Assume that the training is as described in section 4.1, where the parameter σ of the initialization is also described there. Then with probability of at least 1 -δ:

1. for each c ∈ C 0 , for every x 1 , x 2 ∈ S (0) c we get K T • x 1 -K T • x 2 < σ 2. for c 1 , c 2 ∈ C 0 , if c 1 = c 2 , for every x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 , we get K T •x 1 -K T •x 2 > γ

We give a similar analysis for the SGD algorithm in appendix B.

5. DEEP MODEL:

Now, assume we are given data from a deep generative distribution as described in section 3 (with d ≥ 2), and our goal is to learn a classifier that predicts the label for each image. A reasonable approach, given the properties of the above distribution, would be to try to infer from the raw image the higher-level semantic representations. If given an example (X, y) we succeed to infer the sequence that generated it, X (0) , X (1) , . . . , X (d) , we could then use SVM on the high-level representation, and learn to infer its label.

Given the results of the previous section, we can recover these semantic representations by training a two-layer Conv net and applying a trivial clustering on the resulting patches. Note that in general we do not assume that all the patches are orthogonal (Assumption 4), as such a property will make the whole model linearly separable. Thus, to apply the results of section 4.2, we would use the clustering algorithm both for standard clustering and also as an "orthogonalization" step, that will map different clusters to orthonormal vectors.

We next describe in details the full algorithm (section 5.1), and show that it finds a network that achieves zero loss in polynomial time (section 5.2).

5.1. ALGORITHM DESCRIPTION:

The algorithm we suggest is built from three building-blocks composed together to construct the full algorithm: (1) clustering algorithm, (2) gradient-based optimization of two-layer Conv net and (3) a simple classification algorithm. In order to expose the latent representation of each layer in the generative model, we perform the following iteratively:

(1) Run a k-means algorithm on patches of size s × s from the input images defined by the previous step (or the original images in the first step), w.r.t. the cosine distance, to get k i cluster centers.

(2) Run a convolution operation with the cluster centroids as kernels, followed by ReLU with a fixed bias and a pooling operation. This will result in mapping the patches in the input images to (approximately) orthogonal vectors in an intermediate space R ki .

(3) Initialize a 1x1 convolution operation, that maps from k i channels into n channels, followed by a linear layer that predicts Y. We train this two-layer subnet using gradient-descent. As an immediate corollary of the analysis in the previous section, this step implicitly learns an embedding of the patches into a space where patches from the same semantic class are close to each other, while patches from different classes are far away. This lays the groundwork for the clustering step of the next iteration. (4) "Throw" the last linear layer, thus leaving a trained block of Conv(s×s)-ReLU-Pool-Conv(1×1) which finds a "good" embedding of the patches of the input image, and repeat the process again, where the output of this block is the input to step 1.

Finally, after we perform this process for d times, we get a network of depth d composed from Conv(s × s)-ReLU-Pool-Conv(1 × 1) blocks. Then, we feed the output of this (already trained) network to an SVM algorithm that learns a linear classifier, training it to infer the label y from the semantic representation that the convolution network outputs. We now describe the building blocks for the algorithm, followed by the definition of the complete algorithm.

Clustering. The first block of the algorithm is the clustering step. We denote KMEANS(S, k) to be the output of the k-means++ algorithm (Arthur & Vassilvitskii (2007) ) running on sample S to find k clusters, w.r.t the cosine similarity. We assume the algorithm returns a mapping φ S : R s → R k , such that if x i , x j ∈ S are in the same cluster then φ S (x i ) = φ S (x j ), and otherwise φ S (x i ) ⊥ φ S (x j ).

For the consistency with common CNN architecture, we can use the centroids of each cluster as kernels for a convolution operation. Combining this with ReLU with a fixed bias and a pooling operation gives an operation that maps each patch to a single vector, where vectors of different patches are approximately orthogonal.

Two-Layer Network Algorithm:

We denote TLGD(S, T, η, n, σ) the GD algorithm, training a twolayer Conv net of width n, on sample S, with learning rate η for T interations. This algorithm returns the weights of the first layer K T . The details of this algorithm are described in section 4.1.

Classification Algorithm Finally, the last building block of the algorithm is a classification stage, that is used on top of the deep convolution architecture learned in the previous steps. As we show, at this stage the examples are linearly separated, so we can use the SVM algorithm to find large margin linear separator. We denote SVM(S) the output of running SVM on sample S.

Complete Algorithm Utilizing the building blocks described previously, our algorithm learns a deep CNN layer after layer. This network is used to infer the label for each image. The algorithm is described formally in algorithm 1. In the description, we use the notation φ * A to denote the operation of applying a map φ : K m0 

)} ⊆ R m 0 s d ×m 0 s d × Y h d ← id for i = d . . . 1 do

set Si ← {(hi(X1), y1), . . . , (hi(XN ), yN )} // construct sample using the current network set Pi ← {patches of size s × s from Si} // generate patches from the current sample set φi ← KMEANS(Pi, ki) // cluster the sampled patches set Ŝi ← {(φi * hi(X1), y1), . . . , (φi * hi(XN ), yN )} // map patches to orthogonal vectors using φi if i > 1 then set Ki-1 ← TLGD( Ŝi, T, η, n, σ) // train a two-layer net to find a "good" embedding for the patches set hi-1 ← K i-1 (φi * hi) // add the current block to the network end if end for set h ← SVM( Ŝ0) return h • h1

In this section we show that, algorithm 1 learns in polynomial time (with high probability) a network model that correctly classifies the examples according to their labels.

Recall that we have shown that training a two-layer network implicitly learns an embedding of the patches into a space where patches from the same semantic class are close to each other, while patches from different classes are far. Using this, we show that performing clustering + two-layer network training iteratively, layer by layer, leads to revealing the underlying model, and hence the algorithm's convergence. We claim that algorithm 1 successfully learns a model that correctly classifies the examples sampled from the observed distribution G d . This is stated in the following theorem:

Theorem 2 Suppose that assumptions 1, 2, 3 hold. Fix δ > 0, and let δ = δ 2d . Denote

C := max i<d |C i | the maximal number of semantic classes in any level i. Choose σ = 1 s , n > 2π 0.23θ log( C δ ), T > (C/ √ δ +2σ)k ηλ , k 1 = |C 0 |, . . . , k d-1 = |C d-2 |, k d = k|C d-1 |. Then w.p ≥ 1 -δ, running algorithm 1 with parameters γ, η, T, n, σ, k 1 , . . . , k d on distribution G d returns hypothesis h s.t P (X,y)∼G d (h(X) = y) = 0, and runs in time O d(C 2 k 2 + T ) + k W * 2 .

6. EXPERIMENTS:

A common criticism of theoretical results on deep learning is that they fail to account for the empirical success of deep networks. Indeed, negative results show that learning deep networks is computationally hard, while in practice efficient algorithms like SGD achieve remarkably good performance. Positive results, on the other hand, often make very strong assumptions that clearly do not hold in practice, like assuming the inputs are sampled from Gaussian distribution, or that they are linearly separable. Other positive results make less restrictive assumptions, but analyze algorithms that are very far from algorithms that are used in practice. At first glance, our work may seem to suffer from the same common drawbacks of positive theoretical results: we describe a distribution that is admittedly synthetic, and for deep models we analyze an algorithm that seems "tailored" to Figure 4 : Results of various configurations on the CIFAR-10 dataset learn this distribution. To show that our model and algorithm do capture properties of distributions and algorithms used in practice, we implemented our algorithm to learn a CNN on the CIFAR-10 dataset, comparing it to a vanilla CNN trained with a common SGD-based optimization algorithm.

As our aim is to show that our algorithm achieves comparable result to a vanilla SGD-based optimization, and not to achieve state-of-the-art results on CIFAR-10, we do not use any of the common "tricks" that are widely used when training deep networks (such as data augmentation, dropout, batch normalization, scheduled learning rate, averaging of weights across iterations etc.). We implemented our algorithm by repeating the following steps twice: (1) Sample N patches of size 3x3 uniformly from the dataset. (2) For some , run the K-means algorithm to find cluster centers c 1 . . . c . (3) At this step, we need to associate each cluster with a vector in R , such that the image of this mapping is a set of orthonormal vectors, and then map every patch in every image to the vector corresponding to the cluster it belongs to. We do so by performing Conv3x3 operation with the kernels c 1 . . . c , and then perform ReLU operation with a fixed bias b. This roughly maps each patch to the vector e i , where i is the cluster the patch belongs to. (4) While our analysis corresponds to performing the convolution from the previous step with a stride of 3, to make the architecture closer to the commonly used CNNs (specifically the one suggested in the Tensorflow implementation Google-Brain ( 2016)), we used a stride of 1 followed by a 2x2 max-pooling. ( 5) Randomly initialize a two layered linear network, where the first layer is Conv1x1 with output channels, and the second layer is a fully-connected Affine layer that outputs 10 channels to predict the 10 classes of CIFAR-10. ( 6) Train the two-layers with Adam optimization (Kingma & Ba ( 2014)) on the cross-entropy loss, and remove the top layer. The output of this block is the output of these steps.

Repeating the above steps twice yields a network with two blocks of Conv3x3-ReLU-Pool-Conv1x1. We feed the output of these steps to a final classifier that is trained with Adam on the cross entropy loss for 100k iterations, to output the final classification of this model. We test two choices for this classifier: a linear classifier and a three-layers fully-connected neural network. Note that in both cases, the output of our algorithm is a vanilla CNN. The only difference is in the training algorithm.

To calibrate the various parameters that define the model, we first perform random parameter search, where we use 10k examples from the train set as validation set (and the rest 40k as train set). After we found the optimal parameters for all the setups we compare, we then train the model again with the calibrated parameters on all the train data, and plot the accuracy on the test data every 10k iterations. The parameters found in the parameter search are listed in appendix E.

We compared our algorithm to several alternatives. First, the standard CNN configuration in the Tensorflow implementation with two variants: CNN+(FC+ReLU) 3 is the Tensorflow architecture and CNN+Linear is the Tensorflow architecture where the last three fully connected layers were replaced by a single fully connected layer. The goal of this comparison is to show that the performance of our algorithm is in the same ballpark as that of vanilla CNNs. Second, we use the same two architectures mentioned before, but while using random weights for the CNN and training only the FC layers. Some previous analyses of the success of CNN claimed that the power of the algorithm comes from the random initialization (see Daniely (2017) ), and only the training of the last layer matters. As is clearly seen, random weights are far from the performance of vanilla CNNs. Our last experiment aims at showing the power of the two layer training in our algorithm (step 6). To do so, we compare our algorithm to a variant of it, in which step 6 is replaced by random projections (based on Johnson-Lindenstrauss lemma). We denote this variant by Clustering+JL. As can be seen, this variant gives drastically inferior results, showing that the training step of Conv1x1 is crucial, and finds a "good" embedding for the process that follows, as is suggested by our theoretical analysis. A summary of all the results is given in figure 4 .

A PROOF OF LEMMA 1 AND THEOREM 1:

Denote m = m 0 s the size of the images sampled from G 1 (these images are in R m×m ). As in section 4, we will consider the "reshaped" version of images sampled from G 1 , so we will have X ∈ R s 2 ×m 2 0 . Equivalently, patches of the sampled images, that belong to sets {S (0) c } c∈C , will be vectors in R s 2

. Finally, we denote (Z, y) ∼ G 0 the latent images in the generative process, where Z ∈ C m0×m0 0 . Here we will instead consider these images as vectors in C m 2 0 0 . Similarly, the labeled frequency matrix of class c is F c ∈ R m0×m0 , and we will consider it to be a vector F c ∈ R m 2 0 . In the proof we use the notations F c to denote the negative labeled frequency matrix:

F c := E (Z,y)∼Gi [-yI c (Z)]

We will start by proving Lemma 1:

Proof of Lemma 1: For simplicity, we can assume

C 0 = [C],

for some natural C. Therefore, the linear separator of G 0 is a matrix

W * ∈ R C×m 2 0 . For (Z, y) ∼ G 0 define W * , Z = c∈[C] W * c , I c (Z)

, where I c is the operator that replaces each entry of Z with the boolean 1 if it equals c, or 0 otherwise. Notice that the definition of linear separability in section 3 is equivalent to y W * , Z ≥ 1 for every (Z, y) ∼ G 0 .

Denote P 1 , . . . , P C ∈ R s 2 such that P i = P ∈S (0) i P . From the orthonormality of the patches, for every P ∈ S (0) i

we have P • P j = 1 i=j . Now, denote T : R s 2 ×m 2 0 → R such that:

T (X) = j∈[C] W * j , P j X

For (X, y) ∼ G 1 , denote Z the latent representation of X, then by the definition of the generative distribution it is easy to verify that I j (Z) = P j X, and therefore:

T (X) = j∈[C] W * j , I j (Z)

Since T is a linear function such that T 2 F = k W * 2 F , and using standard results on the SVM algorithm, the conclusion of the lemma follows.

In the rest of this section, we will prove Theorem 2. We use the notations w

(t) i , k (t)

i to denote the i-th columns of W t , K t respectively.

For some class c ∈ C 0 and for some patch x ∈ S (0) c , denote f x a function that takes a matrix X and returns a vector f x (X) such that the i'th element of f x (X) is the 1 if the i'th column of X, denoted x i , equals to x and 0 otherwise. That is,

f x (X) :=    1 x1=x . . . 1 xm=x   

Notice that from the orthonormality of the observed columns of X it follows that: f x (X) = X x .

We begin with proving the following technical lemma.

Lemma 2 For each c ∈ C 0 and for each x ∈ S (0) c we have:

E (X,y)∼G1 [-yf x (X)] = 1 k F c

Proof Denote D Z the distribution of (X (1) , y) ∼ G 1 conditioned on X (0) = Z (the distribution of the images generated from the latent image Z). Observe that

E (X,y)∼G1 [-yf x (X)] = 1 2 y=±1 -yE Z∼Dy [E X∼D Z [f x (X)]]

Recall that for each c ∈ C 0 , we have

|S (0) c | = k. Therefore, for each j ∈ [m 2 0 ] we have: 1 2 y=±1 -yE z∼Dy [E X∼D Z [f x (X) j ]] = 1 2 y=±1 -yE Z∼Dy E X∼D Z 1 xj =x = 1 2 y=±1 -yE Z∼Dy [P X∼D Z (x j = x )] = 1 2 y=±1 -yE Z∼Dy 1 k 1 zj =c = 1 k • 1 2 y=±1 -yE Z∼Dy [I c (Z) j ] = 1 k [F c ] j

The next lemma reveals a surprising connection between the gradient and the vectors F c .

Lemma 3 for every c ∈ C 0 and for every x ∈ S (0) c :

x ∂ ∂k i L K,W = 1 k w i • F c

Proof For a fixed X and W , denote ŷ(K) = N K,W (X). Note that:

EQUATION

c we have:

x • ∂ ∂k i ŷ = (x ) Xw i = w i • f x (X)

Combining the above with the definition of the loss function, y (ŷ) = -y ŷ, and with Lemma 2 we

x ∂ ∂k i L Kt,W0 = E (X,y)∼G1 x ∂ ∂k i y (ŷ) = E (X,y)∼G1 -y x ∂ ∂k i ŷ = E (X,y)∼G1 -y w (0) i • f x (X) = w (0) i • E (X,y)∼G1 [-yf x (X)] = 1 k w (0) i • F c

As an immediate corollary we obtain that a gradient step does not change the projection of the kernel on two vectors that correspond to the same class (both are in the same S (0) c ).

Corollary 1 For every t ≥ 0, i ∈ [n], for every semantic class c ∈ C and for every

x 1 , x 2 ∈ S (0) c it holds that: |k (t+1) i • x 1 -k (t+1) i • x 2 | = |k (t) i • x 1 -k (t) i • x 2 |.

Proof From Lemma 3 we can conclude that for a given c ∈ C, for every x 1 , x 2 ∈ S (0) c we get:

x 1 ∂ ∂k i L Kt,W0 = x 2 ∂ ∂k i L Kt,W0

From the gradient descent update rule:

k (t+1) i = k (t) i -η ∂ ∂k i L Kt,W0

And therefore:

|k (t+1) i • x 1 -k (t+1) i • x 2 | = |(k (i) t -η ∂ ∂k i L Kt,W0 ) • x 1 -(k (t) i -η ∂ ∂k i L Kt,W0 ) • x 2 | = |k (t) i • x 1 -k (t) i • x 2 -(η ∂ ∂k i L Kt,W0 x 1 -η ∂ ∂k i L Kt,W0 x 2 )| = |k (t) i • x 1 -k (t) i • x 2 |

Next we turn to show that a gradient step improves the separation of vectors coming from different semantic classes.

Lemma 4 Fix c 1 , c 2 ∈ C 0 . Recall that we denote ∠(F c1 , F c2 ) to be the angle between the vectors F c1 , F c2 . Then, with probability ∠(F c1 , F c2 )/π on the initialization of w (0) i we get:

sign(w (0) i • F c1 ) = sign(w (0) i • F c2 )

Proof Observe the projection of w (0) i on the plane spanned by F c1 , F c2 . Then, the result is immediate from the symmetry of the initialization of w (0) i .

Lemma 5 Fix c 1 = c 2 ∈ C 0 . Then, with probability of at least 0.23

∠(Fc 1 ,Fc 2 ) π

we get for every

x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 : |k (T ) i • x 1 -k (T ) i • x 2 | > 1 k ηT F c1 + F c2 2 -2σ

Proof Notice that since w (0) i ∼ N (0, 1), we get that w

(0) i • F cj ∼ N (0, F cj 2 ) for j ∈ {1, 2}.

Therefore, the probability that w (0) i •F cj deviates by at most 1 2 -std from the mean is erf( 1 2 √

2 ). Thus, we get that:

P (|w (0) i • F cj | ≤ F cj ) = erf( 1 2 √ 2 )

And using the union bound:

P (|w (0) i • F c1 | ≤ F c1 ∨ |w (0) i • F c2 | ≤ F c2 ) ≤ 2erf( 1 2 √ 2 ) < 0.77

Thus, using Lemma 4, we get that the following holds with probability of at least 0.23

∠(Fc 1 ,Fc 2 ) π : • |w (0) i • F c1 | > F c1 • |w (0) i • F c2 | > F c2 • sign(w (0) i • F c1 ) = sign(w (0) i • F c2 ) Assume w.l.o.g that w (0) i • F c1 < 0 < w (0) i • F c2 , then using Lemma 3 we get: k (T ) i x 1 = k (0) i x 1 -η T t=1 ∂ ∂k (i) x 1 L Kt,W0 = k (0) i -η T t=1 1 k w (0) i • F c1 = k (0) i - 1 k ηT w (0) i • F c1 > 1 k ηT F c1 2 -σ

In a similar fashion we can get:

k (T ) i x 2 < - 1 k ηT F c2 2 + σ

And thus the conclusion follows:

k (T ) i x 1 -k (T ) i x 2 > 1 k ηT F c1 + F c2 2 -2σ

Finally, we are ready to prove the main theorem.

Proof of Theorem 1. We show two things:

1. Fix c ∈ C 0 . By the initialization, we get that for every

EQUATION

c and for every i ∈ [n]:

|x 1 • k (0) i -x 2 • k (0) i | < σ √ n

Using Corollary 1, we get that:

|x 1 • k (T ) i -x 2 • k (T ) i | < σ √ n

And thus:

K T x 1 -K T x 2 < σ 2. Let c 1 = c 2 ∈ C 0 . Assume T > (γ+2σ)k ηλ . For i ∈ [n],

from Lemma 5 we get that with probability of at least 0.23

∠(Fc 1 ,Fc 2 ) π > 0.23 θ π for every x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 : |k (T ) i x 1 -k (T ) i x 2 | > 1 k ηT F c1 + F c2 2 -2σ > 1 k ηT λ -2σ > γ

For a given c 1 = c 2 ∈ C 0 , denote the event:

A c1,c2 = {∀i ∈ [n] : |k (T ) i • x 1 -k (T ) i • x 2 | < γ, x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 } Then,

from what we have showed, it holds that:

P (A c1,c2 ) < (1 -0.23 θ π ) n ≤ exp(-0.23n θ π )

Using the union bound, we get that: 

P (∃c 1 = c 2 ∈ C 0 s.t A c1,c2 ) < exp(-0.23n θ π )|C 0 | 2 Choosing n > 2π 0.23θ log( |C| δ ) we get P (∃c 1 = c 2 ∈ C 0 s.t A c1,c2 ) < δ. Now, if for every c 1 = c 2 ∈ C 0 the event A c1,c2 doesn't hold, then clearly for every x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 we would get K T • x 1 -K T • x 2 > γ,

B ANALYSIS OF SGD:

We show a theorem equivalent to Theorem 1, when using the SGD algorithm on samples from distribution G 1 , instead of updating on the population gradient with the GD algorithm. For this analysis, we fix m 0 = 3 and take the columns of W to be initialized on the unit sphere.

Theorem 3 Assume that assumptions 2, 3, 4 hold. Assume we train a two-layer network of size n > 2π 0.12θ log( |C| δ ) with SGD with batch size of 1 on samples from distribution G 1 , for T > max{ (γ+4σ) 

4 k 4 (0.4λ) 4 , 8n 2 m 4 0 σ 4 log 2 ( 2|C0|kn δ

)} iterations, with learning rate η = T -3/4 , for some γ > 0. Then with probability of at least 1 -2δ:

1. for each c ∈ C 0 , for every x 1 , x 2 ∈ S (0) c we get K T • x 1 -K T • x 2 < 2σ 2. for c 1 , c 2 ∈ C 0 , if c 1 = c 2 , for every x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 , we get K T •x 1 -K T •x 2 > γ

Assume we are given a sample (X 1 , y 1 ), . . . , (X T , y T ) sampled i.i.d from distribution G 1 , and we run SGD with batch size of 1 (with respect to the same problem analyzed in the previous section). Denote by ŷt the prediction of the network on iteration t. Denote g (t)

i the gradient with respect to the kernel k i on iteration t.

Similar to Lemma 3, we get for every c ∈ C 0 and x ∈ S (0) c :

x g (t) i = x ∂ ∂k i yt (ŷ t ) = -y t x ∂ ∂k i w (0) i • f x (X)

Using Lemma 3 along with the fact that (X t , y t ) ∼ i.i.d G 1 we get that:

E (Xt,yt)∼G1 x g (t) i = 1 k w (0) i • F c

Since we assume w (i) 0

≤ 1, we get that:

|ηx g (t) i | ≤ η w (0) i f x (X t ) ≤ ηm 0

Therefore, fixing α > 0, and using Hoeffding's bound we get:

P r(| T t=1 ηx g (t) i - ηT k w (0) i • F c | ≥ α) ≤ 2 exp(-2α 2 /(T η 2 m 2 0 ))

And taking η = T -3/4 we get:

P r(| T t=1 ηx g (t) i - ηT k w (0) i • F c | ≥ α) ≤ 2 exp(-2 √ T α 2 /m 2 0 )

Denote by A the event where:

∃i ∈ [n], ∃x ∈ ∪ c∈C0 S (0) c : | T t=1 ηx g (t) i - T k w (0) i • F c | ≥ α Taking T ≥ m 4 0 2α 4 log 2 ( 2|C0|kn δ

) and using union bound over all kernels k i , i ∈ [n] and patches in ∪ c∈C0 S (0) c we get: P r(A) ≤ δ

Using the above, we get the following:

Corollary 2 With probability at least 1 -δ, we get:

|k (T ) i • x 1 -k (T ) i • x 2 | ≤ σ √ n + 2α

Proof With probability at least 1 -δ, for every c ∈ C 0 and for every x 1 , x 2 ∈ S (0) c we get:

|k (T ) i • x 1 -k (T ) i • x 2 | = |k (0) i • x 1 -k (0) i • x 2 -η T t=1 x • g (t) i + η T t=1 x • g (t) i | ≤ |k (0) i • x 1 -k (0) i • x 2 | + | T t=1 ηx 1 g (t) i - T k w (0) i • F c | + | T t=1 ηx 2 g (t) i - T k w (0) i • F c | ≤ σ √ n + 2α

We repeat the proof of Lemma 5, now assuming the updates are of SGD.

Lemma 6 Assume event A does not occur. Fix c 1 = c 2 ∈ C 0 . Then, with probability of at least 0.23

∠(Fc 1 ,Fc 2 ) π

we get for every

EQUATION

i , F cj / F cj + 1). The vector w (0) i is distributed uniformly on the sphere, and from spherical symmetry we can see that the distribution of v is independent of the value of F cj / F cj . Therefore, we can see that the distribution of v is simply the distribution of the first coordinate of w (4, 4) . Therefore, we get:

(0) i , normalized to [0, 1]. Since w (0) 0 is of dimension m 2 0 , we get that v ∼ Beta((m 2 0 -1)/2, (m 2 0 -1)/2)) = Beta

P (0.4 ≤ v ≤ 0.6) < 0.44

And from this we get:

P (|w (0) i • F cj | ≤ 0.2 F cj ) < 0.

44 And using the union bound:

P (|w (0) i • F c1 | ≤ 0.2 F c1 ∨ |w (0) i • F c2 | ≤ 0.2 F c2 ) < 0.88

Thus, using Lemma 4, we get that the following holds with probability of at least 0.12

∠(Fc 1 ,Fc 2 ) π : • |w (0) i • F c1 | > 0.2 F c1 • |w (0) i • F c2 | > 0.2 F c2 • sign(w (0) i • F c1 ) = sign(w (0) i • F c2 ) Assume w.l.o.g that w (0) i • F c1 < 0 < w (0) i • F c2 ,

then using what we have shown:

k (T ) i x 1 = k (0) i x 1 - T t=1 ηx 1 g (t) i = k (0) i x 1 - T t=1 ηx 1 g (t) i + ηT k w (0) i • F c1 - ηT k w (0) i • F c1 ≥ k (0) i x 1 - ηT k w (0) i • F c1 -| 1 T T t=1 x 1 g (t) i - ηT k w (0) i • F c1 | > 0.2T 1/4 k F c1 -σ -α

In a similar fashion we can get:

k (T ) i x 2 < - 0.2T 1/4 k F c2 + σ + α

And thus the conclusion follows:

k (T ) i x 1 -k (T ) i x 2 > 0.2T 1/4 k ( F c1 + F c2 ) -2σ -2α

We can now repeat the main theorem for the SGD case:

Proof of Theorem 3. Assume event A does not occur, and fix α = σ 2 √ n . We show two things:

1. Using Corollary 2, we get that:

|x 1 • k (T ) i -x 2 • k (T ) i | < 2σ √ n

And thus:

K T x 1 -K T x 2 < 2σ 2. Let c 1 = c 2 ∈ C 0 . Assume T > (γ+4σ) 4 k 4 (0.4λ) 4 . For i ∈ [n],

from Lemma 6 we get that with probability of at least 0.12

∠(Fc 1 ,Fc 2 ) π > 0.12 θ π for every x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 : |k (T ) i x 1 -k (T ) i x 2 | > 0.2T 1/4 k ( F c1 + F c2 ) -2σ -2α > 0.4T 1/4 k λ -4σ > γ

For a given c 1 = c 2 ∈ C 0 , denote the event:

A c1,c2 = {∀i ∈ [n] : |k (T ) i • x 1 -k (T ) i • x 2 | < γ, x 1 ∈ S (0) c1 , x 2 ∈ S (0)

c2 } Then, from what we have showed, it holds that:

P (A c1,c2 ) < (1 -0.12 θ π ) n ≤ exp(-0.12n θ π )

Using the union bound, we get that:

P (∃c 1 = c 2 ∈ C 0 s.t A c1,c2 ) < exp(-0.12n θ π )|C 0 | 2

Choosing n > 2π 0.12θ log( |C| δ ) we get P (∃c 1 = c 2 ∈ C 0 s.t A c1,c2 ) < δ. Now, if for every c 1 = c 2 ∈ C 0 the event A c1,c2 doesn't hold, then clearly for every

x 1 ∈ S (0) c1 , x 2 ∈ S (0) c2 we would get K T • x 1 -K T • x 2 > γ,

and this is what we wanted to show.

Since event A happens with probability at most δ, the conclusion follows.

C PROOF OF THEOREM 2:

Our algorithm uses the k-means++ algorithm, which is a variant of Lloyd's algorithm where the initial cluster centers are chosen with probability proportional to their distance to the closest cluster that was already chosen. The algorithm first chooses a cluster center c 1 uniformly on all examples. Any new cluster is chosen in the following way: assume we already chose cluster centers c 1 , . . . , c n , denote D(x) := min j∈ [n] xc j , the minimal distance from example x ∈ S to the closest cluster center. Then, the algorithm chooses an example x ∈ S with probability D(x) 2

x ∈S D(x ) 2 . After the cluster centers are chosen, we run the standard Lloyd's algorithm for k-means.

The following lemma shows that k-means++ finds an optimal solution with high probability on highly-clustered data:

Lemma 7 Fix δ > 0. Let S be a finite set that is "highly-clustered": S is partitioned such that S = ∪ j∈[C] B j , where the partition satisfies:

1. For every x, y ∈ B j it holds that xy < 1.

2. For every x ∈ B i , y ∈ B j such that i = j it holds that xy > C/ √ δ.

3. All B j -s are sets of fixed size:

∀ i,j |B i | = |B j |.

Assume we run the k-means++ algorithm on set S to find C clusters. Then with probability at least 1 -δ, the algorithm returns an "optimal clustering": the centers returned by the algorithm x1 , . . . , xC satisfy that for every j ∈ [C] there exist i ∈ [C] with xi ∈ B j .

Proof We will prove by induction that at the i-th step of choosing the centers, with probability at least 1 -i C δ, the chosen centers x1 , . . . , xi satisfy that there are no i

1 = i 2 ∈ [i] such that xi1 , xi2 ∈ B j :

• for i = 1 this is immediate.

• assume we chose x1 , . . . , xi that satisfy the above condition, and w.l.o.g we can assume that for j ≤ i we have xj ∈ B j . Then, for every x ∈ B j with j ≤ i we have D(x) < 1, and for every x ∈ B j with j > i we have D(x) > C/ √ δ. Therefore, the probability of choosing x ∈ B j with j ≤ i in the next step is at most:

i i + (C -i)C 2 /δ ≤ C -1 C 2 /δ ≤ δ C

Now, using the union bound we get the required.

Taking i = C proves the initialized center are already optimal. Clearly, any step of Lloyd's algorithm will maintain this property. In fact, the algorithm will converge after one step, returning x1 , . . . , xC with xj = 1 C x∈Bj x.

Before we complete the proof of the theorem, we remind a few notations that were used in the algorithm's description. We use φ i to denote the clustering of patches learned in the i-th iteration of the algorithm, and K i the weights of the kernels learned BEFORE the i-th step (thus, the patches mapped by K i are the input to the clustering algorithm that outputs φ i ). Note that we do not learn a mapping in the last step, as from Lemma 1 as the distribution G 1 is linearly separable, so we could simply use SVM on the output of the network at that stage. Finally, we use the notations φ * A to indicate that we operate φ on every patch of the tensor A. When we use operations on distributions, for example h • G or φ * G, we refer to the new distribution generated by applying these operation to every examples sampled from G. The essence of the proof is the following lemma:

Lemma 8 Let G := G d be the distribution over pairs (X, y), where X is the observed image over the reals, and recall that for i < d, the distribution G i is over pairs (X (i) , y) where X (i) is in a space of latent semantic images over C i . For every i ∈ [d], with probability at least 1 -2(d -i)δ , there exists an orthonormal patch mapping ϕ i :

C s×s i → R ki such that φ i * (h i • G) = ϕ i * G i ,

where φ i and h i are as defined in algorithm 1.

The lemma tells us that the neural network at step i of the algorithm reveals (in some sense) the latent semantic structure.

We will again use a "reshaped" notation: in every level i (the i-th step of the induction), we treat patches P ∈ C s×s i as vectors P ∈ C s 2 i . For a sub-image in the next level, denoted Z ∈ C s 2 ×s 2 i+1 , we will denote Z j ∈ C s 2 i+1 to be the j-th patch of size s × s in the sub-image (generated by the class at the j-th coordinate of higher level patch P ∈ C s 2 i ). We will prove by induction the following claim:

Lemma 9 Assume that for some i < d the condition of the lemma holds for i + 1, namely that there exists an orthonormal patch mapping ϕ i+1 :

C s×s i+1 → R ki+1 such that φ i+1 * (h i+1 • G) = ϕ i+1 * G i+1 .

Then, with probability at least 1 -2δ this condition holds for i.

Proof Let ϕ i+1 be the mapping satisfying the condition of the claim for i + 1. Notice that the data that is fed to the two-layer training step comes from the distribution ϕ i+1 * G i+1 , and satisfies the conditions for the analysis of Theorem 1.

First, we will show that the set of patches S i , the set of all patches in the distribution h i • G is "highly-clustered" with probability at least 1 -δ .

For every c ∈ C i , denote B c = {K i ϕ i+1 (P ) : P ∈ S (i) c }. Recall that from our assumption,

h i • G = K i (ϕ i+1 * G i+1 ). Therefore, we have that S i = ∪ c∈Ci B c . Now, from Theorem 1, since we have T > k(C/ √ δ +2σ) ηλ

and σ = 1 s , with probability at least 1 -δ , conditions 1 and 2 in the "highly-clustered" definition hold. Since we assume that S (i) c are of the same size, condition 3 follows.

From the above, using Lemma 7, with probability at least 1 -2δ the set S i is "highly-clustered" and k-means++ returns an optimal clustering. We will now limit ourselves to the event that both of these hold. Now, define the map ϕ i : C s×s i → R k in the following way: first, for every patch P ∈ C s 2 i we take an arbitrary manifestation of the patch P in the next level, denoted Z ∈ C s 2 ×s 2 i+1 . In other words, Z could be any s 2 × s 2 sub-image in the next level that could be generated from the patch P . Now, take ϕ i (P ) := φ i (K i • (ϕ i+1 * Z)). Then, the following holds:

1. ϕ i (P ) does not depend on the choice of Z: if Z, Z are two different manifestations of P , then, from the definition of the generative model, for every j ∈ [s] it holds that Z j , Z j ∈ S Pj . Thus from what we have shown:

EQUATION

Therefore:

K i • ϕ i+1 * Z -K i • ϕ i+1 * Z 2 = s 2 j=1 K i • ϕ i+1 (Z j ) -K i • ϕ i+1 (Z j ) 2 < 1

and since we get an optimal clustering, we have:

φ i (K i • (ϕ i+1 * Z)) = φ i (K i • (ϕ i+1 * Z ))

2. for every two patches P = P we get ϕ κ (P ) ⊥ ϕ κ (P ): let Z, Z be the manifestations of p, p respectively. Since P = P there exists j ∈ [s 2 ] such that P j = P j . From the generative model it follows that Z j ∈ S (i) Pj and Z j ∈ S (i) P j

, and therefore from the behavior of the algorithm:

K i • ϕ i+1 (Z j ) -K i • ϕ i+1 (Z j ) > C/ √ δ > k i / √ δ . Therefore, we get that K i • ϕ i+1 * Z -K i • ϕ i+1 * Z > k i / √

δ, and thus from the clustering optimality we get ϕ i (P ) ⊥ ϕ i (P ). Now, recall that in the algorithm definition: h i = K i • (φ i+1 * h i+1 ). Using the assumption for i + 1, we get:

h i • G = K i (ϕ i+1 * G i+1 )

and from the definition of ϕ i and what we have shown we get:

φ i * (h i • G) = ϕ i * G i

Proof [of Lemma 8] We prove by induction:

• Note that an immediate property of the k-means++ algorithm is that it doesn't choose the same example twice. Therefore, if we run k-means++ on sample S to find |S| clusters, we get a single cluster center for each element of S. From the definition of our model, there are |C d-1 |k patches in the observed image, and since we run k-means++ to find k d = |C d-1 |k clusters, we get a cluster center for each patch. Hence, k-means++ returns an orthogonal patch mapping φ d , and since h d = id we get the required. • Assume the claim holds for i + 1, then with probability at least 1 -2(d -i -1)δ the condition holds for i + 1. In such event, from Lemma 9 with probability at least 1 -2δ , it holds for i. Therefore, with probability (1 -2(d -i -1)δ )(1 -2δ ) ≥ 1 -2(d -i)δ it holds for i.

Proof [ of Theorem 2] From Lemma 8, after performing d iterations of the algorithm, we observe that with probability at least 1 -2dδ = 1 -δ distribution ϕ 1 * G 1 , where ϕ 1 is an orthonormal patch mapping. Therefore, using Lemma 1, it is linearly separable with margin k W * 2 . Therefore, the SVM algorithm finds an optimal separator in O(k W * 2 ). To count the overall amount of iterations, notice that the when running k-means++ on sample S to find C clusters, the initialization step at most |S|C iterations and the algorithm itself converges after one iteration, so in our case its runtime is bounded by C 2 k 2 . The runtime of the T LGD algorithm is T . We perform d iterations of clustering and the T LGD algorithm, and finally run the SVM algorithm that converges in O(k W * 2 ). So the runtime of the whole algorithm is O d(C 2 k 2 + T ) + k W * 2 .

D SYNTHETIC DATA EXPERIMENT:

To confirm that our model is typically not linearly separable, we generated synthetic examples using our model in the following way:

• We chose Y = {±1}.

• We fixed C 0 = {0, 1, 2, 3}, and chose 4 vectors for each class, uniformly over C 3×3 0 . Notice that overall there are 8 vectors labeled with ±1, and they are linearly independent with high probability (we also validated that they are indeed independent). This process defines the distribution G 0 , and it is therefore indeed linearly separable.

• We fix C 1 = {0, 1, 2, 3}, and for each c ∈ C 0 we choose the set S . This defines the distribution G 1 .

• Finally, we choose C 2 = R 3 , and for each c ∈ C 1 we choose S . This defines the distribution G 2 , which is the observed distribution.

We run this model with different values of k (30, 40, 50). We then measure the values of θ and λ, to show that Assumption 3 holds for this distribution.

We generate a sample of 50, 000 examples from this distribution, taking 40, 000 as train examples, and 10, 000 as test. We train a linear classifier on this distribution, and display its performance on the test data. For comparison, we also train a CNN with non-overlapping convolutions (convolutions of 3x3 and stride 3) with the ReLU activation. We use an architecture of two layers of convolution, and a final readout layer, and train with respect to the logistic loss. This training is done with the Adam optimizer in a standard end-to-end fashion. We also train the same architecture with our algorithm, where we the training is done layer-by-layer. E PARAMETERS FOR CIFAR-10 EXPERIMENTS figure 5 below lists the parameters that were learned in the random parameter search for the different configurations of the algorithm, as described in 4. The table lists the parameters used in each layer:

1 , 2 are the number of clusters for the first and second layer, and 1 , 2 are the output channels of the Conv1x1 operation for each layer. These parameters could be used to reproduce the results of our experiments. 

:



Figures and Tables:

1

Figure 2: Left: Image generation process example. Right: Synthetic examples generated.

A, replacing patches of size m 0 by vectors in K m1 1 . Formally: φ * A := [φ(A :,i•m0...(i+1)•m0 )] i Algorithm 1 Deep Layerwise Clustering input: numbers η, T, n, σ, k1, . . . , k d sample S = {(X1, y1), . . . (XN , yN

and this is what we wanted to show.

by drawing k vectors from a normal distribution over C 3×3 2

Figure 5: Parameters used in our experiment .



Table content: <table><tr><td>pixel</td><td>, we sample over:</td><td>,</td><td>,</td><td>,</td><td>.</td></tr><tr><td>Similarly,</td><td/><td/><td/><td/><td/></tr></table>

Notice that though this example is extremely simplistic, it can generate 4 9 examples per digit in the first level, and 4 90 examples for each digit in the final layer, amounting to 9 • 4 90 ≈ 1.38 • 10 55 different examples.Figure

Table content: <table><tr><td/><td/><td/><td/><td/><td>4</td></tr><tr><td>elements. For example, for the pixel</td><td>, we sample over:</td><td>,</td><td>,</td><td>,</td><td>.</td></tr></table>

Peer review (iclr2019):
 The paper claims to propose a computationally efficient algorithm for training deep CNNs by making assumptions about the distribution of data. The authors argue that (i) they don*t make very simplistic assumptions about the data generating distribution as some other papers do, and (ii) their algorithm resembles the actual methods that are used for training deep models and shows some surprising properties of SGD. Throughout the paper, the authors make a number of assumptions which seem arbitrary at times; not much justifications are provided. The authors claim that their assumptions are not as simplistic as assuming e.g., the inputs are sampled from Gaussian distribution. Unfortunately this is highly unclear: while the "assumptions" themselves are complex, the combination of those assumptions may make the problem solution trivial. While proving a lower bound to address this issue may be hard, at least the authors should try to illuminate more why the solution is not trivial (e.g., why a linear classifier doesn*t work, etc.) Despite the claims, I find the proposed algorithm very far from the usual SGD-based training methods; this is not a problem per se but I don*t think that the result illuminates on the effectiveness of SGD (as the authors suggest). The proposed algorithm is a greedy layer-wise method that in each level does a clustering and also trains a "linear" CNN with SGD. So the hardness of end-to-end training of a deep network does not show up. Furthermore, it is not clear for training a linear CNN the SGD is even needed. I suggest that the authors name each of the assumptions and clearly say which ones are assumed for which result. Here are some of the assumptions that the authors talk about. 1_ The data is generated by the following recursive procedure: First a small "high-level image" is generated from a distribution, G_0. The "pixels" of this high-level image are supposed to encode semantic classes, e.g., sky or ground. In the next step, each of these high-level pixels are turned into a small (lower-level) image. Therefore, we will have a more refined image after the second step. (each semantic class (e.g., sky) has a corresponding distribution that generates the smaller lower-level image (e.g., uniform over 4 possible types of skies)). This procedure continues recursively until we have the final image. 2_ G_0 is "linearly separable". 3_ Semantic classes defined in the model are different enough from each other 4_ {F_c} corresponding to semantic classes are linearly independent 5_ Patch Orthonormality (apparently not assumed everywhere) it appears that if one assumes all of 1-5, then the problem becomes trivial (linearly separable). The authors then say that we don*t want to make assumption 5 for this reason; still, the problem solution may be trivial (authors should at least intuitively justify why it isn*t ) Here are some more uses of the word "assumption". 6_ "For simplicity of analysis, we assume only the first layer of the network is trained". 7_ "We assume the algorithm [KMEANS++] returns a mapping [...] such that [...]" The experiments do not seem conclusive. Only a few experiments have been done. I think the acquired results for CIFAR-10 are below the usual ones using CNNs, and the effects of various hyper-parameters may have interfered. -- After reading the authors* response, I still think the way that the contributions are depicted (e.g., a justifying the effectiveness of SGD) are inaccurate/unsupported. Furthermore, although the authors* suggest that they have tested a linear classifier and observed that the data is not linearly separable, more explanations/intuitions are needed about the assumptions that are made throughout the paper.