Title: END-TO-END LEARNING OF A CONVOLUTIONAL NEURAL NETWORK VIA DEEP TENSOR DECOMPOSITION

Abstract: In this paper we study the problem of learning the weights of a deep convolutional neural network. We consider a network where convolutions are carried out over nonoverlapping patches with a single kernel in each layer. We develop an algorithm for simultaneously learning all the kernels from the training data. Our approach dubbed Deep Tensor Decomposition (DeepTD) is based on a rank-1 tensor decomposition. We theoretically investigate DeepTD under a realizable model for the training data where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted convolutional kernels. We show that DeepTD is data-efficient and provably works as soon as the sample size exceeds the total number of convolutional weights in the network. Our numerical experiments demonstrate the effectiveness of DeepTD and verify our theoretical findings.

1. INTRODUCTION:

Deep neural network (DNN) architectures have led to state of the art performance in many domains including image recognition, natural language processing, recommendation systems, and video analysis (He et al. (2016) ; Krizhevsky et al. (2012) ; Van den Oord et al. (2013) ; Collobert & Weston (2008) ). Convolutional neural networks (CNNs) are a class of deep, feed-forward neural networks with a specialized DNN architecture. CNNs are responsible for some of the most significant performance gains of DNN architectures. In particular, CNN architectures have led to striking performance improvements for image/object recognition tasks. Convolutional neural networks, loosely inspired by the visual cortex of animals, construct increasingly higher level features (such as mouth and nose) from lower level features such as pixels. An added advantage of CNNs which makes them extremely attractive for large-scale applications is their remarkable efficiency which can be attributed to: (1) intelligent utilization of parameters via weight-sharing, (2) their convolutional nature which exploits the local spatial structure of images/videos effectively, and (3) highly efficient matrix/vector multiplication involved in CNNs compared to fully-connected neural network architectures.

Despite the wide empirical success of CNNs the reasons for the effectiveness of neural networks and CNNs in particular is still a mystery. Recently there has been a surge of interest in developing more rigorous foundations for neural networks (Soltanolkotabi et al. (2017) ; Zhong et al. (2017b) ; Alon Brutzkus & Globerson (2017) ; Soltanolkotabi (2017) ; Oymak (2018) ; Zhong et al. (2017a) ; Janzamin et al. (2015) ; Li & Yuan (2017) ; Mei et al. (2018) ). Most of this existing literature however focus on learning shallow neural networks typically consisting of zero or one hidden layer. In practical applications, depth seems to play a crucial role in constructing progressively higher-level features from pixels. Indeed, state of the art Resnet models typically have hundreds of layers. Furthermore, recent results suggest that increasing depth may substantially boost the expressive power of neural networks (Raghu et al. (2016) ; Cohen et al. (2016) ).

In this paper, we propose an algorithm for approximately learning an arbitrarily deep CNN model with rigorous guarantees. Our goal is to provide theoretical insights towards better understanding when training deep CNN architectures is computationally tractable and how much data is required for successful training. We focus on a realizable model where the inputs are chosen i.i.d. from a Gaussian distribution and the labels are generated according to planted convolutional kernels. We use both labels and features in the training data to construct a tensor. Our first insight is that, in the limit of infinite data this tensor converges to a population tensor which is approximately rank one and whose factors reveal the direction of the kernels. Our second insight is that even with finite data this empirical tensor is still approximately rank one. We show that the gap between the population and empirical tensors provably decreases with the increase in the size of the training data set and becomes negligible as soon as the size of the training data becomes proportional to the total numbers of the parameters in the planted CNN model. Combining these insights we provide a tensor decomposition algorithm to learn the kernels from training data. We show that our algorithm approximately learns the kernels (up to sign/scale ambiguities) as soon as the size of the training data is proportional to the total number of parameters of the planted CNN model. Our results can be viewed as a first step towards provable end-to-end learning of practical deep CNN models. Extending the connections between neural networks and tensors (Janzamin et al. (2015) ; Cohen et al. (2016) ; Zhong et al. (2017a) ), we show how tensor decomposition can be utilized to approximately learn deep networks despite the presence of nonlinearities and growing depth. While our focus in this work is limited to tensors, we believe that our proposed algorithm may provide valuable insights for initializing local search methods (such as stochastic gradient descent) to enhance the quality and/or speed of CNN training.

2. PROBLEM FORMULATION AND MODELS:

In this section we discuss the CNN model which is the focus of this paper. A fully connected artificial neural network is composed of computational units called neurons. The neurons are decomposed into layers consisting of one input layer, one output layer and a few hidden layers with the output of each layer is fed in (as input) to the next layer. In a CNN model the output of each layer is related to the input of the next layer by a convolution operation. In this paper we focus on a CNN model where the stride length is equal to the length of the kernel. This is sometimes referred to as a non-overlapping convolution operation formally defined below.

Definition 2.1 (Non-overlapping convolution) For two vectors k ∈ R d and h ∈ R p=d p their nonoverlapping convolution, denoted by k * ◻ h yields a vector u ∈ R p= p d whose entries are given by u i = ⟨k ( ) , h[i]⟩ where h[i] ∶= h (i-1)d+1 h (i-1)d+2 . . . h id T .

In this paper it is often convenient to view convolutions as matrix/vector multiplications. This leads us to the definition of the kernel matrix below.

Definition 2.2 (Kernel matrix) Consider a kernel k ∈ R d and any vector h ∈ R p= pd . Corresponding to the non-overlapping convolution k * ◻ h, we associate a kernel matrix

K * ◻ ∈ R p×p defined as K * ◻ ∶= I p ⊗ k T .

Here, A ⊗ B denotes the Kronecker product between the two matrices A and B and I p denotes the p × p identity matrix. We note that based on this definition k * ◻ h = K * ◻ h. Throughout the paper we shall use K interchangeably with K * ◻ to denote this kernel matrix with the dependence on the underlying kernel and its non-overlapping form implied.

With the definition of the non-overlapping convolution and the corresponding kernel matrix in hand we are now ready to define the CNN model which is the focus of this paper. For ease of exposition, the CNN input-output relationship along with the corresponding notation is depicted in Figure 1 .

• Depth and numbering of the layers. We consider a network of depth D where we number the input as layer 0 and the output as layer D and the hidden layers 1 to D -1.

• Layer dimensions and representations. We assume the input of the CNN, denoted by x ∈ R p , consists of p features and the output is a one dimensional label. We also assume the hidden layers (numbered by = 1, 2, . . . , D -1) consists of p units with h( ) ∈ R p and h ( ) ∈ R p denoting the input and output values of the units in the th hidden layer. For consistency of our notation we shall also define h (0) ∶= x ∈ R p and note that the output of the CNN is h (D) ∈ R. Also, p 0 = p and p D = 1.

• Kernel dimensions and representation. For = 1, . . . D we assume the kernel relating the output of layer ( -1) to the input of layer is of dimension d and is denoted by k ( ) ∈ R d .

• Inter-layer relationship. We assume the inputs of layer (denoted by h( ) ∈ R p ) are related to the outputs of layer ( -1) (denoted by h ( -1) ∈ R p -1 ) via a non-overlapping convolution h( ) = k ( ) * ◻ h ( -1) = K ( ) h ( -1) for = 1, . . . , D. In the latter equality we have used the representation of non-overlapping convolution as a matrix/vector product involving the kernel matrix K ( ) ∈ R p ×p -1 associated with the kernel k ( ) ∈ R d per Definition 2.2. We note that the non-overlapping nature of the convolution implies that p = p -1 d .

• Activation functions and intra-layer relationship. We assume the input of each hidden unit is related to its output by applying an activation function φ ∶ R → R. More precisely, h ( ) ∶= φ ( h( ) ) where for a vector u ∈ R p , φ (u) ∈ R p is a vector obtained by applying the activation function φ to each of the entries of u. We allow for using distinct activation functions {φ } D =1 at every layer. Throughout, we also assume all activations are 1-Lipschitz functions (i.e. φ (a)φ (b) ≤ ab ).

• Final output. The input-output relation of our CNN model with an input x ∈ R p is given by

x ↦ f CN N (x) ∶= h (D) ,

(2.1) with hidden unit relations h ( ) = φ ( h( ) ) and h( ) = K ( ) h ( -1) .

3. ALGORITHM: DEEP TENSOR DECOMPOSITION (DEEPTD):

This paper introduces an approach to approximating the convolutional kernels from training data based on tensor decompositions dubbed DeepTD, which consists of a carefully designed tensor decomposition. To connect these two problems, we begin by stating how we intend to construct the tensor from the training data. To this aim given any input data x ∈ R p , we form a D-way tensor X ∈ R ⊗ D =1 d as follows. First, we convert x into a matrix by placing every d 1 consecutive entries of x as a row of a matrix of size p 1 × d 1 . From this matrix we then create a 3-way tensor of size p 2 × d 2 × d 1 by grouping d 2 consecutive entries of each of the d 1 columns and so on. We repeat this procedure D times to arrive at the D-way tensor

X ∈ R ⊗ D =1 d . We define T ∶ R p ↦ R ⊗ D =1 d as the corresponding tensor operation that maps x ∈ R p to X ∈ R ⊗ D =1 d .

Given a set of training data consisting of n input/output pairs (x i , y i ) ∈ R p × R we construct a tensor T n by tensorizing the input vectors as discussed above and calculating a weighted combination of these tensorized inputs. More precisely,

T n ∶= 1 n n i=1

(y iy avg ) X i where y avg = 1 n n i=1 y i and X i = T (x i ).

(3.1)

We then perform a rank-1 tensor decomposition on this tensor to approximate the convolutional kernels. Specifically we solve

k(1) , . . . , k(D) = arg max v ∈R d ⟨T n , D ⊗ =1 v ⟩ subject to v 1 2 = . . . = v D 2 = 1. (3.2)

In the above ⊗ D =1 v denotes the tensor resulting from the outer product of v 1 , v 2 , . . . , v D . This tensor rank decomposition is also known as CANDECOMP/PARAFAC (CP) decomposition Bro (1997) and can be solved efficiently using Alternating Least Squares and a variety of other algorithms Anandkumar et al. (2014a) ; Ge et al. (2015) ; Anandkumar et al. (2014b). 1 At this point it is completely unclear why the tensor T n or its rank-1 decomposition can yield anything useful. The main intuition is that as the data set grows (n → ∞) the empirical tensor T n converges close to a population tensor T whose rank-1 decomposition reveals useful information about the kernels. Specifically, we will show that

lim n→∞ T n = T ∶= E x∼N (0,Ip) [f CNN (x)T (x)] ≈ α D ⊗ =1 k ( ) , (3.3)

with α a scalar whose value shall be discussed later on. Here, x is a Gaussian random vector with i.i.d. N (0, 1) entries and represents a typical input with f CNN (x) the corresponding output and T (x) the tensorized input. We will also utilize a concentration argument to show that when the training 1 We would like to note that while finding the best rank-1 TD (3.2) is NP-hard, our theoretical guarantees continue to hold when using an approximately optimal solution to (3.2). In fact, we can show that unfolding the tensor along the ith kernel into a di × ∏ j≠i dj matrix and using the top left singular vector yields a good approximation to k (i) . However, in our numerical simulations we instead utilize popular software packages to solve (3.2). data set originates from an i.i.d. distribution, for a sufficiently large training data n, T n yields a good approximation of the population tensor T .

Another perhaps perplexing aspect of the construction of T n in (3.1) is the subtraction by y avg in the weights. The reason this may be a source of confusion is that based on the intuition above

E[T ] = E 1 n n i=1 y i X i = E 1 n -1 n i=1 (y i -y avg ) X i = n n -1 E[T n ] ≈ α D ⊗ =1 k ( ) ,

so that the subtraction by the average seems completely redundant. The main purpose of this subtraction is to ensure the weights y iy avg are centered (have mean zero). This centering allows for a much better concentration of the empirical tensor around its population counter part and is crucial to the success of our approach. We would like to point out that such a centering procedure is reminiscent of batch-normalization heuristics deployed when training deep neural networks.

Finally, we note that based on (3.3), the rank-1 tensor decomposition step can recover the convolutional kernels {k ( ) } D =1 up to sign and scaling ambiguities. Unfortunately, depending on the activation function, it may be impossible to overcome these ambiguities. For instance, if the activations are homogeneous (i.e. φ (ax) = aφ (x)), then scaling up one layer and scaling down the other layer by the same amount does not change the overall function f CNN (⋅). Similarly, if the activations are odd functions, negating two of the layers at the same time preserves the overall function. In Appendix C, we discuss some heuristics and theoretical guarantees for overcoming these sign/scale ambiguities.

4. MAIN RESULTS:

In this section we introduce our theoretical results for DeepTD. We will discuss these results in three sections. In Section 4.1 we show that the empirical tensor concentrates around its population counterpart. Then in Section 4.2 we show that the population tensor is well-approximated by a rank-1 tensor whose factors reveal the convolutional kernels. Finally, in Section 4.3 we combine these results to show DeepTD can approximately learn the convolutional kernels up to sign/scale ambiguities.

4.1. CONCENTRATION OF THE EMPIRICAL TENSOR:

Our first result shows that the empirical tensor concentrations around the population tensor. We measure the quality of this concentration via the tensor spectral norm defined below. Definition 4.1 Let RO be the set of rank-one tensors ⊗ D =1 v satisfying v i 2 ≤ 1 for all 1 ≤ i ≤ D. The spectral norm of a tensor X ∈ R ⊗ D =1 d is given by the supremum T = sup V ∈RO ⟨V , T ⟩. Theorem 4.2 Consider a CNN model x ↦ f CN N (x) of the form (2.1) consisting of D ≥ 2 layers with convolutional kernels k (1) , k (2) , . . . , k (D) of lengths d 1 , d 2 , . . . , d D . Let x ∈ R p be a Gaussian random vector distributed as N (0, I p ) with the corresponding labels y = f CN N (x) generated by the CNN model and X ∶= T (x) the corresponding tensorized input. Suppose the data set consists of n training samples where the feature vectors x i ∈ R p are distributed i.i.d. N (0, I p ) with the corresponding labels y i = f CN N (x i ) generated by the same CNN model and X i ∶= T (x i ) the corresponding tensorized input. Suppose n ≥ (∑ D =1 d ) log D. Then the empirical tensor T n and population tensor T defined based on this dataset obey

EQUATION

with probability at least 1 -5e -min t 2 ,t √ n,n , where c > 0 is an absolute constant.

The theorem above shows that the empirical tensor approximates the population tensor with high probability. This theorem also shows that the quality of this approximation is proportional to

∏ D =1 k ( ) 2

. This is natural as

∏ D =1 k ( ) 2

is an upper-bound on the Lipschitz constant of the network and shows how much the CNN output fluctuates with changes in the input. The more fluctuations, the less concentrated the empirical tensor is, translating into a worse approximation guarantee. Furthermore, the quality of this approximation grows with the square root of the parameters in the model (∑ D =1 d ) and is inversely proportional to the square root of the number of samples (n) which are typical scalings in statistical learning. We would also like to note that as we will see in the forthcoming sections, in many cases T is roughly on the order of

∏ D =1 k ( ) 2 so that (4.1) guarantees that T n -T T ≤ c ′ ∑ D =1 d log D n

. Therefore, the relative error in the approximation is less than as soon as the number of observations exceeds the number of parameters in the model by a logarithmic factor in depth i.e. n ≳ (∑ D =1 d ) log D 2 . 4.2 RANK ONE APPROXIMATION OF THE POPULATION TENSOR Our second result shows that the population tensor can be approximated by a rank one tensor. To explain the structure of this rank one tensor and quantify the quality of this approximation we require a few definitions. The first quantity roughly captures the average amount by which the nonlinear activations amplify or attenuate the size of an input feature at the output. Definition 4.3 (CNN gain) Let x ∼ N (0, I p ) and define the hidden unit/output values of the CNN based on this random input per equations (2.1). We define the CNN gain as

α CNN = ∏ D =1 E[φ ′ ( h( ) 1 )].

In words, this is the product of expectations of the activations evaluated at the first entry of each layer. For non differentiable activations, φ ′ should be interpreted as the average of the left and right derivatives. For instance, when φ (z) =ReLU(z) then φ ′ (0) = 1 2.

This quantity is the product of the average slopes of the activations evaluated along a path connecting the first input feature to the first hidden units across the layers all the way to the output. We note that this quantity is the same when calculated along any path connecting an input feature to the output passing through the hidden units. Therefore, this quantity can be thought of as the average gain (amplification or attenuation) of a given input feature due to the nonlinear activations in the network. To gain some intuition consider a ReLU network which is mostly inactive. Then the network is dead and α CNN ≈ 0. On the other extreme if all ReLU units are active the network operates in the linear regime and α CNN = 1. We would like to point out that α CNN can in many cases be bounded from below by a constant. For instance, as proven in Appendix B, for ReLU activations as long as the kernels obey

1 T k ( ) ≥ 4 k ( ) 2 , (4.2) then α CNN ≥ 1 4.

Another example is the softplus activation φ (x) = log (1 + e x ) for which we prove α CNN ≥ 0.3 under similar assumptions (Also in Appendix B). We note that an assumption similar to (4.2) is needed for the network to be active. This is because if the kernel sums are negative one can show that with high probability, all the ReLUs after the first layer will be inactive and the network will be dead. With this definition in hand, we are now ready to describe the form of the rank one tensor that approximates the population tensor. 

L CNN ∈ R ⊗ D =1 d as L CNN = α CNN ⊗ D =1 k ( ) .

That is, the product of the kernels {k ( ) } D =1 scaled by the CNN gain α CNN . To quantify how well the rank one CNN tensor approximates the population tensor we need two definitions. The first definition concerns the activation functions. Definition 4.5 (Activation smoothness) We assume the activations are differentiable everywhere and S-smooth (i.e. φ ′ (x)φ ′ (y) ≤ S xy for all x, y ∈ R) for some S ≥ 0.

The reason smoothness of the activations play a role in the quality of the rank one approximation is that smoother activations translate into smoother variations in the entries of the population tensor. Therefore, the population tensor can be better approximated by a low-rank tensor. The second definition captures how diffused the kernels are.

Definition 4.6 (Kernel diffuseness parameter) Given kernels {k ( ) } D =1 with dimensions {d } D =1 , the kernel diffuseness parameter µ is defined as µ = sup 1≤ ≤D √ d k ( ) ∞ k ( ) 2 .

The less diffused (or more spiky) the kernels are, the more the population tensor fluctuates and thus the quality of the approximation to a rank one tensor decreases. With these definitions in place, we are now ready to state our theorem on approximating a population tensor with a rank one tensor.

Theorem 4.7 Consider the setup of Theorem 4.2. Also, assume the activations are S-smooth per Definition 4.5 and the convolutional kernels are µ-diffused per Definition 4.6. Then, the population tensor T ∶= E[yX] can be approximated by the rank-1 tensor

L CNN ∶= α CNN ⊗ D =1 k ( ) as follows T -L CNN ≤ T -L CNN F ≤ √ 8πµS ⋅ D i=1 k (i) 2 ⋅ sup i=1 k (i) 2 D min d .

The theorem above states that the quality of the rank one approximation deteriorates with increase in the smoothness of the activations and the diffuseness of the convolutional kernels. As mentioned earlier increase in these parameters leads to more fluctuations in the population tensor making it less likely that it can be well approximated by a rank one tensor. We also note that

L CNN = α CNN ∏ D =1 k ( ) 2

and therefore the relative error in this approximation is bounded by

T -L CNN L CNN ≤ √ 8π µS α CNN sup i=1 k (i) 2 D min d .

We would like to note that for many activations the smoothness is bounded by a constant. For instance, for the softplus activation (φ(x) = log(1 + e x )) and one can show that S ≤ 1. As stated earlier, under appropriate assumptions on the kernels and activations, the CNN gain α CNN is also bounded from below by a constant. Assume the convolutional kernels have unit norm and are sufficiently diffused so that the diffuseness parameter is bounded by a constant. We can then conclude that

T -L CNN L CNN ≤ c α CNN D min d .

This implies that as soon as the length of the convolutional patches scale with the square of depth of the network by a constant factor the rank one approximation is sufficiently good. Our back-of-the-envelope calculations suggest that the correct scaling is linear in D versus the quadratic result we have established here. Improving our result to achieve the correct scaling is an interesting future research direction. Finally, we would like to note that while we have assumed differentiable and smooth activations we expect our results to apply to popular non-differentiable activations such as ReLU activations.

4.3. LEARNING THE CONVOLUTIONAL KERNELS:

We demonstrated in the previous two sections that the empirical tensor concentrates around its population counter part and that the population tensor is well-approximated by a rank one tensor. We combine these two results along with a perturbation argument to provide guarantees for DeepTD.

Theorem 4.8 (Main theorem) Consider the setups of Theorems 4.2 and 4.7. Assume activations are S-smooth per Definition 4.5 and the convolutional kernels are µ-diffused per Definition 4.6. The DeepTD estimates of the convolutional kernels given by (3.2) using the empirical tensor T n obeys

∏ D =1 ⟨k ( ) , k( ) ⟩ ∏ D =1 k ( ) 2 ≥ 1 - 2 α CNN ⎛ ⎜ ⎝ c ∑ D =1 d log D + t √ n + √ 8πµS ⋅ sup i=1 k (i) 2 D min d ⎞ ⎟ ⎠

, with probability at least 1 -5e -min t 2 ,t √ n,n , where c > 0 is an absolute constant.

The above theorem is our main result on learning a non-overlapping CNN with a single kernel at each layer. It demonstrates that estimates k( ) obtained by DeepTD have significant inner product with the ground truth kernels k ( ) with high probability, using only few samples. Indeed, similar to the discussion after Theorem 4.7 assuming the activations are sufficiently smooth and the convolutional kernels are unit norm and sufficiently diffused, the theorem above can be simplified as follows

∏ D =1 ⟨k ( ) , k( ) ⟩ ∏ D =1 k ( ) 2 ≥ 1 -c ⎛ ⎜ ⎝ ∑ D =1 d log D √ n + D min d ⎞ ⎟ ⎠

.

Thus the kernel estimates obtained via DeepTD are well aligned with the true kernels as soon as the number of samples scales with the total number of parameters in the model and the length of the convolutional kernels (i.e. the size of the batches) scales quadratically with the depth of the network.

5. NUMERICAL EXPERIMENTS:

Our goal in this section is to numerically corroborate the theoretical predictions of Section 4. To this aim we use a CNN model of the form (2.1) with D layers and ReLU activations and set the kernel lengths to be all equal to each other i.e. d 4 = . . . = d 1 = d. We use the identity activation for the last layer (i.e. φ D (z) = z) with the exception of the last experiment where we use a ReLU activation (i.e. φ D (z) = max(0, z)). We conducted our experiments in Python using the Tensorly library for the tensor decomposition in DeepTD (Kossaifi et al. (2016) ). Each curve in every figure is obtained by averaging 100 independent realizations of the same CNN learning procedure. Similar to our theory, we use Gaussian data points x and ground truth labels y = f CNN (x).

We conduct two sets of experiments: The first set focuses on larger values of depth D and the second set focuses on larger values of width d. In all experiments kernels are generated with random Gaussian entries and are normalized to have unit Euclidean norm. For the ReLU activation if one of the kernels have all negative entries, the output is trivially zero and learning is not feasible. To 

) = ⟨ k( ) , k ( ) ⟩

) between the DeepTD estimate and the ground truth kernels for different layers and over-sampling ratios N . address this, we consider operational networks where at least 50% of the training labels are nonzero.

Here, the number 50% is arbitrarily chosen and we verified that similar results hold for other values. Finally, to study the effect of finite samples, we let the sample size grow proportional to the total degrees of freedom ∑ In Figure 2 , we consider two networks with d = 2, D = 12 and d = 3, D = 8 configurations. We plot the absolute correlation between the ground truth and the estimates as a function of layer depth. For each hidden layer 1 ≤ ≤ D, our correlation measure (y-axis) is corr( k( ) , k ( ) ) = ⟨ k( ) , k ( ) ⟩ . This number is between 0 and 1 as the kernels and their estimates both have unit norm. We observe that for both d = 2 and d = 3, DeepTD consistently achieves correlation values above 75% for N = 20. While our theory requires d to scale quadratically with depth i.e. d ≳ D 2 , we find that even small d values work well in our experiments. The effect of sample size becomes evident by comparing N = 20 and N = 50 for the input and output layers ( = 1, = D). In this case N = 50 achieves perfect correlation. Interestingly, correlation values are smallest in the middle layers. In fact this even holds when N is large suggesting that the rank one approximation of the population tensor provides worst estimates for the middle layers.

In Figure 3 , we use a ReLU activation in the final layer and assess the impact of the centering procedure of the DeepTD algorithm which is a major theme throughout the paper. We define the NaiveTD algorithm which solves (3.2) without centering in the empirical tensor i.e.

k(1) , . . . , k(D) = arg max v ∈R d ⟨ 1 n n i=1 y i X i , D ⊗ =1 v ⟩ subject to v 1 2 = . . . = v D 2 = 1. (5.1)

Since the activation of the final layer is ReLU, the output has a clear positive bias in expectation which will help demonstrating the importance of centering. We find that for smaller oversampling factors of N = 10 or N = 20, DeepTD has a visibly better performance compared with NaiveTD. The correlation difference is persistent among different layers (we plotted only Layers 1 and 2) and appears to grow with increase in the kernel size d.

Finally, in Figure 4 , we assess the impact of activation nonlinearity by comparing the ReLU and identity activations in the final layer. We plot the first and final layer correlations for this setup. While the correlation performances of the first layer are essentially identical, the ReLU activation (dashed lines) achieves significantly lower correlation at the final layer. This is not surprising as the final layer passes through an additional nonlinearity. 

6. RELATED WORK:

Our work is closely related to the recent line of papers on neural networks as well as tensor decompositions. We briefly discuss this related literature.

Neural 

7. CONCLUSION:

In this paper we studied a multilayer CNN model with depth D. We assumed a non-overlapping structure where each layer has a single convolutional kernel and has stride length equal to the dimension of its kernel. We establish a connection between approximating the CNN kernels and higher order tensor decompositions. Based on this, we proposed an algorithm for simultaneously learning all kernels called the Deep Tensor Decomposition (DeepTD). This algorithm builds a D-way tensor based on the training data and applies a rank one tensor factorization algorithm to this tensor to simultaneously estimate all of the convolutional kernels. Assuming the input data is distributed i.i.d. according to a Gaussian model with corresponding output generated by a planted set of convolutional kernels, we prove DeepTD can approximately learn all kernels with a near minimal amount of training data. A variety of numerical experiments complement our theoretical findings.

A PROOFS:

In this section we will prove our main results. Throughout, for a random variable X, we use zm(X) to denote X -E[X]. Simply stated, zm(X) is the centered version of X. For a random vector/matrix/tensor X, zm(X) denotes the vector/matrix/tensor obtained by applying the zm() operation to each entry. For a tensor T we use T F to denote the square root of the sum of squares of the entries of the tensor. Stated differently, this is the Euclidean norm of a vector obtained by rearranging the entries of the tensor. Throughout we use c, c1, c2, and C to denote fixed numerical constants whose values may change from line to line. We begin with some useful definitions and lemmas.

A.1 USEFUL CONCENTRATION LEMMAS AND DEFINITIONS:

In this section we gather some useful definitions and well-known lemmas that will be used frequently throughout our concentration arguments.

Definition A.1 (Orlicz norms) For a scalar random variable Orlicz-a norm is defined as

X ψa = sup k≥1 k -1 a (E[ X k ]) 1 k

Orlicz-a norm of a vector x ∈ R p is defined as x ψa = sup v∈B p v T x ψa where B p is the unit 2 ball. The sub-exponential norm is the function ⋅ ψ 1 and the sub-gaussian norm the function ⋅ ψ 2 .

We now state a few well-known results that we will use throughout the proofs. This results are standard and are stated for the sake of completeness. The first lemma states that the product of sub-gaussian random variables are sub-exponential.

Lemma A.2 Let X, Y be subgaussian random variables. Then XY

ψ 1 ≤ X ψ 2 Y ψ 2 .

The next lemma connects Orlicz norms of sum of random variables to the sum of the Orlicz norm of each random variable.

Lemma A.3 Suppose X, Y are random variables with bounded ⋅ ψa norm. Then X + Y ψa ≤ 2 max{ X ψa , Y ψa }. In particular X -E X] ψa ≤ 2 X ψa .

The lemma below can be easily obtained by combining the previous two lemmas.

Lemma A.4 Let X, Y be subgaussian random variables. Then zm(XY )

ψ 1 ≤ 2 X ψ 2 Y ψ 2 .

Finally, we need a few standard chaining definitions.

Definition A.5 (Admissible sequence Talagrand (2014)) Given a set T an admissible sequence is an increasing sequence {An} ∞ n=0 of partitions of T such that An ≤ Nn where N0 = 1 and Nn = 2 2 n for all n ≥ 1.

For the following discussion ∆ d (An(t)), will be the diameter of the set S ∈ An that contains t, with respect to the d metric.

Definition A.6 (γa functional Talagrand (2014)) Given a > 0, and a metric space (T, d) we define γa(T, d) = inf sup t∈T n≥0

2 n a ∆ d (An(t)),

where the infimum is taken over all admissible sequences.

The following lemma upper bounds γα functional with covering numbers of T . The reader is referred to Section 1.2 of Talagrand (2006) , Equation (2.3) of Dirksen (2013) , and Lemma D.17 of Oymak (2018) . 

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 n n i=1 zm(zm(f (xi))Xi) ≤ c1L √ n ⎛ ⎜ ⎝ D =1 d log D + t ⎞ ⎟ ⎠ ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ e -min t 2 ,t √ n ,

holds with c1 > 0 a fixed numerical constant.

Lemma A.9 Consider the setup of Lemma A.8. Then

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 n n i=1 zm(f (xi)) 1 n n i=1 Xi ≥ c2t1L n ⎛ ⎜ ⎝ D =1 d log D + t2 ⎞ ⎟ ⎠ ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ 2 e -t 2 1 + e -t 2 2 ,

holds with c2 > 0 a fixed numerical constant.

Combining Lemma A.8 with f = fCNN(), L = ∏ D =1 k ( ) 2

, and c1 = c 2 together with Lemma A.9 with t1 = √ n, t2 = t, and c2 = c 2 concludes the proof of Theorem 4.2. All that remains is to prove Lemmas A.8 and A.9 which are the subject of the next two sections.

A.2.1 PROOF OF LEMMA A.8:

It is more convenient to carryout the steps of the proof on ∑ By construction E[g(T ) -g(H)] = 0. We next claim that Yi is a sub-exponential vector. Consider a tensor T with unit length T F = 1 i.e. the sum of squares of entries are equal to one. We have ⟨Yi, T ⟩ = zm(f (xi)) ⟨Xi, T ⟩. f (Xi) is a Lipschitz function of a Gaussian random vector. Thus, by the concentration of Lipschitz functions of Gaussians we have

P( zm(f (Xi)) ≥ t) ≤ 2 exp(- t 2 2L 2 ). (A.3)

This immediately implies that zm(f (Xi)) ψ 2 ≤ cL for a fixed numerical constant c. Also note that ⟨Xi, T ⟩ ∼ N (0, 1) hence ⟨Xi, T ⟩ ψ 2 ≤ c. These two identities combined with Lemma A.4 implies a bound on the sub-exponential norm zm(⟨Yi, T ⟩) ψ 1 ≤ cL. Next, we observe that g(T ) -g(H) is sum of n i.i.d. sub-exponentials each obeying ⟨zm(Yi), T -H⟩ ψ 1 ≤ cL T -H F . Applying a standard sub-exponential Bernstein inequality, we conclude that

P( g(T ) -g(H) ≥ t) ≤ 2exp -c ⋅ min t L T -H F , t 2 nL 2 T -H 2 F , (A.4)

holds with γ a fixed numerical constant. This tail bound implies that g is a mixed tail process that is studied by Talagrand and others (Talagrand (2014) ; Dirksen (2013) ). In particular, supremum of such processes are characterized in terms of a linear combination of Talagrand's γ1 and γ2 functionals (see Definition A.6 as well as Talagrand (2014; 2006) for an exposition). We pick the following distance metrics on tensors induced by the Frobenius norm: d1(T , H) = L H -T F c and d2(T , H) = H -T F L n c. We can thus rewrite (A.4) in the form

P g(T ) -g(H) ≥ t ≤ 2 exp -min t d1(T , H) , t 2 d 2 2 (T , H)

,

which implies P g(T ) -g(H) ≥ √ td2(T , H) + td1(T , H) ≤ 2 exp(-t).

Observe that the radius of RO with respect to ⋅ F norm is 1 hence radius with respect to d1, d2 metrics are L c, L n c respectively. Applying Theorem 3.5 of Dirksen ( 2013), we obtain

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ sup T ∈RO g(T ) ≥ C γ2(RO, d2) + γ1(RO, d1) + L un c + uL c ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ e -u .

Observe that we can use the change of variable t = L ⋅ max √ un, u to obtain

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ sup T ∈RO g(T ) ≥ C (γ2(RO, d2) + γ1(RO, d1) + t) ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ exp -min t 2 L 2 n , t L , (A.5)

with some updated constant C > 0. To conclude, we need to bound the γ2 and γ1 terms. To achieve this we will upper bound the γα functional in terms of Dudley's entropy integral which is stated in Lemma A. 

({v } D =1 ) -({u } D =1 ) F ≤ D =1 (v1, . . . , v , u +1 , . . . , u D ) -(v1, . . . , v -1 , u , . . . , u D ) F (A.6) = D =1 v 2 . . . v -1 2 v -u 2 u +1 2 . . . u D 2 ≤ Dδ. (A.7)

Denoting Frobenius norm covering number of RO by N (ε), this implies that, for 0 

< ε ≤ 1, N (ε) ≤ (1 + 2D ε) ∑ D =1 d . Clearly, N (ε) = 1 for ε ≥ 1 by picking the cover {0}. Consequently, γ1(RO, ⋅ F ) ≤ 1 0 log N (ε)dε ≤ c D =1 d log D, γ2(RO, ⋅ F ) ≤ 1 0 log N (ε)dε ≤ c D =1 d log D.

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ sup T ∈RO g(T ) ≥ C ⎛ ⎜ ⎝ L n D =1 d log D + t ⎞ ⎟ ⎠ ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ e -min t 2 L 2 n , t L .

Substituting t → L √ nt and recalling (A.2), concludes the proof.

1 √ n n i=1 Xi ≤ c ′′ ⎛ ⎜ ⎝ D =1 d log D + t2 ⎞ ⎟ ⎠ ⇒ 1 n n i=1 Xi ≤ c ′′ ∑ D =1 d log D + t2 √ n , (A.11)

holds with probability 1 -2e -t 2 2 . Combining (A.10) and (A.11) via the union bound together with (A.9) concludes the proof.

A.3 RANK ONE APPROXIMATION OF THE POPULATION TENSOR (PROOF OF THEOREM 4.7):

We begin the proof of this theorem by a few definitions regarding non-overlapping CNN models that simplify our exposition. For these definitions it is convenient to view non-overlapping CNNs as a tree with the root of the tree corresponding to the output of the CNN and the leaves corresponding to input features. In this visualization Dth layer of the tree corresponds to the th layer. Figure 5 depicts such a tree visualization along with the definitions discussed below. Definition A.10 (Path vector) A vector i ∈ R D+1 is a path vector if its zeroth coordinate satisfies 1 ≤ i0 ≤ p and for all D -1 ≥ j ≥ 0, ij+1 obeys ij+1 = ⌈ij dj⌉. This implies 1 ≤ ij ≤ pj and i D = 1. We note that in the tree visualization a path vector corresponds to a path connecting a leaf (input feature) to the root of the tree (output). We use I to denote the set of all path vectors and note that I = p. We also define i(i) ∈ I be the vector whose zeroth entry is i0 = i. Stated differently i(i) is the path connecting the input feature i to the output. Given a path i and a p dimensional vector v, we define v i ∶= v i 0 . A sample path vector is depicted in bold in Figure 5 which corresponds to i = (d1, 1, 1, 1).

Definition A.11 (Kernel and activation path gains) Consider a CNN model of the form (2.1) with input x and inputs of hidden units given by { h( ) } D =1 . To any path vector i connecting an input feature to the output we associate two path gains: a kernel path gain denoted by k i and activation path gain denoted by φ ′ i (x) defined as

k i = D =1 k ( ) mod(i -1 ,d ) and φ ′ i (x) = D =1 φ ′ ( h( ) i )

, where mod(a, b) denotes the remainder of dividing integer a by b. In words the kernel path gain is multiplication of the kernel weights along the path and the activation path gain is the multiplication of the derivatives of the activations evaluated at the hidden units along the path. For the path depicted in Figure 5 in bold the kernel path gain is equal

k i = k (1) d 1 k (2) 1 k (3) 1

and the activation path gain is equal to φ

′ i (x) = φ ′ 1 ( h(1) 1 )φ ′ 2 ( h(2) 1 )φ ′ 3 ( h(3) 1 ).

Definition A.12 (CNN offsprings) Consider a CNN model of the form (2.1) with input x and inputs of hidden units given by { h( ) } D =1 . We will associate a set set (i) ⊂ {1, . . . , p} to the ith hidden unit of layer defined as set (i) = {(i -1)r + 1, (i -1)r + 2, . . . , ir } where r = p p . By construction, this corresponds to the set of entries of the input data x that h( ) i (x) is dependent on. In the tree analogy set (i) are the leaves of the tree connected to hidden unit i in the th layer i.e. the set of offsprings of this hidden node. We depict set2(p2) which are the offsprings of the last hidden node in layer two in Figure 5 .

We now will rewrite the population tensor in a form such that it is easier to see why it can be well approximated by a rank one tensor. Note that since the tensorization operation is linear the population tensor is equal to

T = E[fCNN(x)X] = E[fCNN(x)T (x)] = T (E[fCNN(x)x]) .

(A.12) Define the vector g CNN to be the population gradient vector i.e. g CNN = E[∇fCNN(x)] and note that Stein's lemma combined with (A.12) implies that 

T = T (E[fCNN(x)x]) = T (E[∇fCNN(x)]) = T g CNN . (A.13) Also note that ∂fCNN(x) ∂xi = k i(i) φ ′ i(i) (x).

Thus we have:

g CNN i = E ∂fCNN(x) ∂xi = k i(i) E[φ ′ i(i) (x)]. (A.14) x = h (0) ∈ R p ∶= R p0 h (1) ∈ R p1 k (1) ∈ R d1 k (1) k (1) k (1) h (2) ∈ R p2 k (2) ∈ R d2 k (2) y = f CNN (x) = h (D) = h (3 k (3) ∈ R d3 set 2 (p 2 )

k i = k (1) d1 k (2) 1 k (3)

1 and the activation path gain is equal to φ

′ i (x) = φ ′ 1 ( h(1) 1 )φ ′ 2 ( h(2) 1 )φ ′ 3 ( h(3) 1 )

. The set set 2 (p 2 ) (offsprings of the last hidden node in layer two) is outlined.

Define a vector k ∈ R p such that ki = k i(i) . Since k i(i) consists of the product of the kernel values across the path i(i) it is easy to see that the tensor K ∶= T (k) is equal to

K = D ⊗ =1 k ( ) .

(A.15)

Similarly define the vector v ∈ R p such that vi = E[φ ′ i(i) (x)] and define the corresponding tensor V = T (v). Therefore, (A.14) can be rewritten in the vector form g CNN = k ⊙ v where a ⊙ b denotes entry-wise (Hadamard) product between two vectors/matrices/tensors a and b of the same size. Thus using (A.13) the population tensor can alternatively be written as

T = T g CNN = K ⊙ V = D ⊗ =1 k ( ) ⊙ V .

Therefore, the population tensor T is the outer product of the convolutional kernels whose entries are masked with another tensor V . If the entries of the tensor V were all the same the population tensor would be exactly rank one with the factors revealing the convolutional kernel. One natural choice for approximating the population tensor with a rank one matrix is to replace the masking tensor V with a scalar. That is, use the approximation

T ≈ c ⊗ D =1 k ( ) . Recall that LCNN ∶= αCNN ⊗ D =1 k (

) is exactly such an approximation with c set to αCNN given by

αCNN = D =1 E x∼N (0,I) [φ ′ ( h( ) i )].

To characterize the quality of this approximation note that

EQUATION

= D =1 k ( ) 2 v -αCNN ∞ .

Here, (a) follows from the fact for a tensor, its spectral norm is smaller than its Frobenius norm, (b) from the definitions of T and LCNN, (c) from the fact that K = T (k) and V = T (v), (d) from the fact that a ⊙ v 2 ≤ a 2 b ∞ , and (e) from the fact that the Euclidean norm of the kronecker product of of vectors is equal to the product of the Euclidean norm of the indivisual vectors. As a result of the latter inequality to prove Theorem 4.7 it suffices to show that

v -αCNN ∞ ≤ √ 8πµS ⋅ sup i=1 k (i) 2 ⋅ D min d . (A.16)

In the next lemma we prove a stronger statement. Lemma A.13 Assume the activations are S-smooth. Also consider a vector v ∈ R p with entries vi =

E x∼N (0,I) [φ ′ i(i) (x)] and αCNN = ∏ D =1 E x∼N (0,I) [φ ′ ( h( ) i )] we have vi -αCNN ≤ κi ∶= √ 8πS D =1 k ( ) mod(i -1 ,d ) -1 i=1 k (i) 2 .

Here, i is the vector path that starts at input feature i.

Before proving this lemma let us explain how (A.16) follows from this lemma. To show this we use the kernel diffuseness assumption introduced in Definition 4.6. This definition implies that k ( )

mod(i -1 ,d ) ≤ k ( ) ∞ ≤ µ d k ( ) 2 . Thus we have κi ∶= √ 8πS D =1 k ( ) mod(i -1 ,d ) -1 i=1 k (i) 2 , ≤ √ 8πµS D =1 1 √ d k ( ) 2 -1 i=1 k (i) 2 , = √ 8πµS D =1 1 √ d i=1 k (i) 2 , ≤ √ 8πµDS ⋅ sup ∏ i=1 k (i) 2 √ d , ≤ √ 8πµS ⋅ sup i=1 k (i) 2 ⋅ D min d .

This completes the proof of Theorem 4.7. All that remains is to prove Lemma A.13 which is the subject of the next section.

A.3.1 PROOF OF LEMMA A.13:

To bound the difference between vi and αCNN consider the path i = i(i) and define the variables {ai} D i=0 as

ai = E x∼N (0,I) [ i =1 φ ′ ( h( ) i )] D =i+1 E x∼N (0,I) [φ ′ ( h( ) i )]

. Note that a D = vi and a0 = αCNN. To bound the difference vi -αCNN = a D -a0 we use a telescopic sum

a D -a0 ≤ D-1 =0 a +1 -a .

(A.17)

We thus focus on bounding each of the summands a -

a -1 . Setting γ = ∏ D i= E x∼N (0,I) [φ ′ i ( h(i) i i )],

this can be written as

a -a -1 = E x∼N (0,I) [(φ ′ ( h( ) i ) -E[φ ′ ( h( ) i )]) -1 i=1 φ ′ ( h( ) i )]γ +1 .

Using γ ≤ 1 (which follows from the assumption that the activations are 1-Lipschitz), it suffices to bound

E x∼N (0,I) [(φ ′ ( h( ) i ) -E[φ ′ ( h( ) i )])θ -1 ] where θ = i=1 φ ′ i ( h(i) i i ). (A.18)

To this aim we state two useful lemmas whose proofs are deferred to Sections A.3.1.1 and A.3.1.2.

Lemma A.14 Let X, Y, Z be random variables where X is independent of Z. Let f be an L-Lipschitz function.

Then

EQUATION

) is a deterministic function of the entries of x indexed by set (i). In other words, there exists a function f such that h(

) i (x) = f (x set (i) ).

With these lemmas in-hand we return to bounding (A.18). To this aim we decompose h( ) i as follows

h( ) i = d i=1 k ( ) i h ( -1) d (i -1)+i = k ( ) mod(i -1 ,d ) h ( -1) i -1 + r,

where the r term is the contribution of the entries of h ( -1) other than i -1 . By the non-overlapping assumption, r is independent of θ -1 as well as h

( -1)

i -1 (see Lemma A.15). In particular, h

( -1)

i -1 and θ -1 is a function of x set -1 (i -1 ) whereas r is a function of the entries over the complement set (i ) -set -1 (i -1 ). With these observations, applying Lemma A.14 with f

= φ ′ , X = r, Y = k ( ) mod(i -1 ,d ) h ( -1)

i -1 , Z = θ -1 and using the fact that θ -1 ≤ 1 which holds due to 1-Lipschitzness of σ 's, we conclude that

E x∼N (0,I) [(φ ′ ( h( ) i ) -E[φ ′ ( h( ) i )])θ -1 ] ≤ 2S E zm(Y ) .

Here, S is the smoothness of σ and Lipschitz constant of φ ′ . To conclude, we need to assess the E zm(Y ) term. Now note that starting from x, each entry of h ( -1) is obtained by applying a sequence of inner products with {k (i)

} -1 i=1 and activations σ (⋅), which implies h

( -1) i -1 is a ∏ -1 i=1 k (i) 2 -Lipschitz function of set -1 (i -1 ). This implies Y is a Lipschitz function of a Gaussian vector with Lipschitz constant L Y = k ( ) mod(i -1 ,d ) ∏ -1 i=1 k (i)

2 . Hence, zm(Y ) obeys the tail bound

P( zm(Y ) ≥ t) ≤ 2 exp(- t 2 2L 2 Y ).

Using a standard integration by parts argument the latter implies that

E zm(Y ) ≤ √ 2πL Y . Thus, a -a -1 ≤ k ( ) mod(i -1 ,d ) -1 i=1 k (i)

2 . concluding the upper-bound on each summand of (A.17). Combining such upper bounds (A.17) implies

a D -a0 ≤ √ 8πS D =1 k ( ) mod(i -1 ,d ) -1 i=1 k (i)

2 ∶= κ i . This concludes the proof of Lemma A.13. A.3.1.1 Proof of Lemma A.14 Using the independence of X, Z, we can write Lemma A.15 Informally, this lemma is obvious via the tree visualization. To formally prove this lemma we use an induction argument. For h(1) the result is trivial because h(1) i = ⟨k (1) , x(i)⟩ which is a weighted sum of entries corresponding to set1(i). Suppose the claim holds for all layers less than or equal to -1 and h( -1)

E[f (X + Y )Z] = E[f (X + E[Y ])Z] + E[(f (X + Y ) -f (X + E[Y ]))Z] = E[f (X + E[Y ])] E[Z] + E[(f (X + Y ) -f (X + E[Y ]))Z] = E[f (X + Y )] E[Z] + E[f (X + E[Y ]) -f (X + Y )] E[Z] + E[(f (X + Y ) -f (X + E[Y ]))Z]. This implies E[f (X +Y )Z]-E[f (X +Y )] E[Z] = E[f (X +E[Y ])-f (X +Y )] E[Z]+E[(f (X +Y )-f (X +E[Y ]))Z]. Now, using Lipschitzness of f , we deterministically have that f (X + E[Y ]) -f (X + Y ) ≤ L Y -E[Y ] = L zm(Y ) . Similarly, (f (X + Y ) -f (X + E[Y ]))Z ≤ L zm(Y )Z . Taking absolute values we arrive at E[f (X + E[Y ]) -f (X + Y )] E[Z] + E[(f (X + Y ) -f (X + E[Y ]))Z] ≤ L E[ zm(Y ) ( Z + E[Z] )]. This immediately implies (A.19). If Z ≤ 1 almost surely, we have E[ zm(Y )Z ] ≤ E[ zm(Y ) ] and E[Z] ≤ 1 which yields the 2L E[ zm(Y ) ] upper bound. A.3.1.2 Proof of

i = f -1 (x set -1 (i) ).

For layer , we can use the fact that set

(i) = ⋃ d j=1 set -1 ((i -1)d + j) to conclude that h( ) i = d j=1 k ( ) j σ -1 ( h( -1) (i-1)d +j ) = d j=1 k ( ) j σ -1 (f -1 (x set -1 ((i-1)d +j) )) ∶= f (x set (i)

). The latter is clearly a deterministic function of x set (i) . Also it is independent of entry i because it simply chunks the vector x set (i) into d sub-vectors and returns a sum of weighted functions of these sub-vectors. Here, the weights are the entries of k ( ) and the functions are given by σ -1 (f -1 (⋅)) (also note that the activation output is simply h

( ) i = σ (f (x set (i) ))).

A.4 PROOFS FOR LEARNING THE CONVOLUTIONAL KERNELS (PROOF OF THEOREM 4.8)

The first part of the theorem follows trivially by combining Theorems 4.2 and 4.7. To translate a bound on the tensor spectral norm of Tn -LCNN to a bound on learning the kernels, requires a perturbation argument for tensor decompositions. This is the subject of the next lemma. Then we have

D i=1 u * i vi ≥ 1 -2δ γ.

The proof of Theorem 4.8 is complete by applying Lemma A.16 above with v = k ( ) , u = k( ) , γ = αCNN and E = Tn -LCNN. All that remains is to prove Lemma A.16 which is the subject of the next section.

A.4.1 PROOF OF LEMMA A.16:

To prove this lemma first note that for any two rank one tensors we have

⟨ D ⊗ =1 u , D ⊗ =1 v ⟩ = D i=1 ⟨ui, vi⟩ .

Using this equality together with the fact that the vectors {u } D =1 are a maximizer for (A.21) we conclude that

⟨L + E, D ⊗ =1 v ⟩ ≤ ⟨L + E, D ⊗ =1 u ⟩ , ≤ ⟨L, D ⊗ =1 u ⟩ + ⟨E, D ⊗ =1 u ⟩ , ≤ γ D i=1 ⟨ui, vi⟩ + δ. (A.22)

Furthermore, note that 

⟨L + E, D ⊗ =1 v ⟩ = γ + ⟨E, D ⊗ =1 v ⟩ ≥ γ -δ. (A.

= D =1 E φ ′ h( ) i = D =1 E 1 h( ) i ≥0 = D =1 P h( ) i ≥ 0 Thus using t = E h( ) i we arrive at P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ h( ) i < 0 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ e - E h( ) i 2 2 ∏ r=1 kr 2 2 . (B.3)

Since the entries of h ( ) and h( ) are i.i.d. we use H ( ) and H( ) to denote the corresponding distributions. We note that E h(

) i = E ⟨k ( ) , h ( ) [i ]⟩ = 1 T k ( ) E[H ( ) ] = 1 T k ( ) E φ H( ) ≥ 1 T k ( ) φ E[ H( ) ] = 1 T k ( ) ⋅ E[ H( ) ].

where in the last inequality we used the fact that 1 T k ( ) ≥ 0 and applied Jenson's inequality for a convex φ. Applying this inequality recursively we arrive at

E h( ) i ≥ r=1 1 T k (r) E[φ(g)] = 1 √ 2π r=1 1 T k (r) . (B.4)

Using the latter in (B.3) we arrive at

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ h( ) i < 0 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤e -1 4π ∏ r=1 1 T k (r) 2 k (r) 2 2 ⇒ P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ h( ) i ≥ 0 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≥ 1 -e -1 4π ∏ r=1 1 T k (r) 2 k (r) 2 2 .

Thus using the diffusion assumption (B.2) in the latter inequality we arrive at

αCNN ≥ D =1 1 -e -1 4π ν 2

Thus using the fact that for 0 ≤ x1, x2, ..., xn ≤ 1 we have

n i=1 (1 -xi) ≥ 1 - n i=1 xi, we conclude that αCNN ≥1 - D =1 e -1 4π ν 2 ≥1 - D 0 e -1 4π ν 2x dx ≥1 - ∞ 0 e -1 4π ν 2x dx =1 - E1( 1 4π ) log ν 2 =1 - E1( 1 4π ) log 16 ≥ 1 4 .

In the above E1

(x) = ∫ ∞ 1 e -tx

t dt and we used the fact that E1 1 4π ≤ 1.016 and ν ≥ 4. Thus, αCNN ≥ 1 4 . Softplus: For the softplus activation we have

αCNN = D =1 E φ ′ h( ) i = D =1 E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 1 + e - h( ) i ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = D =1 E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ ⎛ ⎝ 1 - 1 1 + e h( ) i ⎞ ⎠ ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ = D =1 ⎛ ⎝ 1 -E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 1 + e h( ) i ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ⎞ ⎠ .

Thus using the fact that for 0 ≤ x1, x2, ..., xn ≤ 1 we have

n i=1 (1 -xi) ≥ 1 - n i=1 xi, we conclude that αCNN ≥1 - D =1 E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 1 + e h( ) i ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ≥1 - D =1 E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 h( ) i <E[ h( ) i ] 2 + 1 h( ) i ≥E[ h( ) i ] 2 1 + e h( ) i ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ≥1 - D =1 E 1 h( ) i <E[ h( ) i ] 2 - D =1 E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 h( ) i ≥E[ h( ) i ] 2 1 + e h( ) i ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ =1 - D =1 P h( ) i < E[ h( ) i ] 2 - D =1 E ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 h( ) i ≥E[ h( ) i ] 2 1 + e h( ) i ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ≥1 - D =1 P h( ) i < E[ h( ) i ] 2 - D =1 1 1 + e E h( ) i 2 . (B.5)

We bound the expected value of the hidden unites similar to the argument for ReLU activations. The only difference is that in the identity (B.4) we need to use the softplus activation in lieu of the ReLU activation for φ.

Therefore, (B.4) changes to

E h( ) i ≥ r=1 1 T k (r) E[φ(g)] = 0.806059 r=1 1 T k (r) . (B.6)

Similar to the ReLU argument, we note that h( ) i is a Lipschitz function of a Gaussian random vector (g) with Lipschitz constant equal to ∏ r=1 k (r) 2 . Using Lipschitz concentration of Gaussians we thus have

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ h( ) i -E h( ) i < -t ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ e - t 2 2 ∏ r=1 k (r) 2 . (B.7) Thus using t = E h( ) i

2 we arrive at

P ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ h( ) i < E[ h( ) i ] 2 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ ≤ e - E h( ) i 2 8 ∏ r=1 kr 2 2 . (B.8)

Thus using the diffusion assumption (B.2) with ν ≥ 4 we have 

D-1 =1 P h( ) i < E[ h( ) i ] 2 ≤ D-1 =1 e -0.1ν 2 ≤ D-1 0 e -0.1ν 2x dx ≤ +∞ 0 e -0.1ν 2x dx = E1(0.1) log ν 2 Also using (B.6) and assuming k ( ) 2 ≥ 1 we have D-1 =1 1 1 + e E h( ) i 2 ≤ D-1 =1 1 1 + e 0.4030295 ∏ r=1 1 T k (r) ≤ D-1 =1 e -0.4030295 ∏ r=1 1 T k (r) ≤ D-1 =1 e -0.4030295⋅ν ⋅∏ r=1 k (r) 2 ≤ D-1 =1 e -0.4030295⋅ν ≤ D-1 0 e -0.

C CENTERED ERM AND RESOLVING SIGN & SCALING AMBIGUITIES:

We note that DeepTD operates by accurately approximating the rank one tensor ⊗ D =1 k ( ) from data. Therefore, DeepTD can only recover the convolutional kernels up to Sign/Scale Ambiguities (SSA). In general, it may not be possible to recover the ground truth kernels from the training data. For instance, when activations are ReLU, the norms of the kernels cannot be estimated from data as multiplying a kernel and dividing another by the same positive scalar leads to the same training data. However, we can try to learn a good approximation fCNN() of the network fCNN() to minimize the risk E[(fCNN(x) -fCNN(x)) 2 ].

To this aim, we introduce Centered Empirical Risk Minimization (CERM) which is a slight modification of Empirical Risk Minimization (ERM). Let us first describe how finding a good fCNN() can be formulated with CERM. Given n i.i.d. data points {(xi, yi)} n i=1 ∼ (x, y), and a function class F, CERM applies ERM after centering the residuals. Given f ∈ F, define the average residual function ravg

(f ) = 1 n ∑ n i=1 yi -f (xi). We define the Centered Empirical Risk Minimizer as f = min f ∈F 1 n n i=1 (yi -f (xi) -ravg(f )) 2 , = min f ∈F 1 n n i=1 (yi -f (xi) -E[(yi -f (xi))]) 2 - 1 n 2 n i=1 yi -f (xi) -E[(yi -f (xi))] 2 . (C.1)

The remarkable benefit of CERM over ERM is the fact that, the learning rate doesn't suffer from the label or function bias. This is in similar nature to the DeepTD algorithm that applies label centering. In the proofs (in particular Section C.2, Theorem C.2) we provide a generalization bound on the CERM solution (C.1) in terms of the Lipschitz covering number of the function space. While (C.1) can be used to learn all kernels, it does not provide an efficient algorithm. Instead, we will use CERM to resolve SSA after estimating the kernels via DeepTD. Interestingly, this approach only requires a few (O(D)) extra training samples. Inspired from CERM, in Section C.1, we propose a greedy algorithm to address SSA. We will apply CERM to the following function class with bounded kernels, The above theorem states that CERM finds the sign/scale ambiguity that accurate estimates the labels on new data as long as the number of samples which are used in CERM exceeds the depth of the network by constant/log factors. In the next section we present a greedy heuristic for finding the CERM estimate.

F k,B ∶= f ∶ R p ↦ R f

C.1 GREEDY ALGORITHM FOR RESOLVING SIGN AND SCALE AMBIGUITIES:

In order to resolve SSA, inspired from CERM, we propose Algorithm 1 which operates over the function class, (C.4) It first determines the signs β by locally optimizing the kernels and then finds a global scaling γ > 0. In the first phase, the algorithm attempts to maximize the correlation between the centered labels yc,i = yi -n -1 ∑ n i=1 yi and the fCNN() predictions given by ŷc,i = ŷin -1 ∑ n i=1 ŷi. It goes over all kernels one by one and it flips a kernel ( k( ) → -k( ) ) if flipping increases the correlation. This process goes on as long as there is an improvement. Afterwards, we use a simple linear regression to get the best scaling γ by minimizing the centered empirical loss ∑ n i=1 (yc,i -γ ŷc,i)

F k ∶= γf ∶ R p ↦ R f

2 . While our approach is applicable to arbitrary activations, it is tailored towards homogeneous activations (φ(cx) = cφ(x)). The reason is that for homogeneous activations, function classes (C.2) and (C.4) coincide and a single global scaling γ is sufficient. Note that ReLU and the identity activation (i.e. no activation) are both homegeneous, in fact they are elements of a larger homogeneous activation family named Leaky ReLU. Leaky ReLU is parametrized by some scalar 0 ≤ β ≤ 1 and defined as follows LReLU (x) =

x if x ≥ 0, βx if x < 0.

C.2 GENERALIZATION BOUNDS FOR CERM:

In this section we prove a generalization bound for Centered Empirical Risk Minimization (CERM) (C.1). The following theorem shows that using a finite sample size n, CERM is guaranteed to choose a function close to population's minimizer. For the sake of this section f L∞ will be the Lipschitz constant of a function.

Theorem C.2 Let F be a class of functions f ∶ R p → R. Suppose sup f ∈F f L∞ ≤ R. Let {(xi, yi)} n i=1 ∼ (x, y) be i.i.d. data points where x ∼ N (0, Ip) and y is so that y -E[y] is K subgaussian. Suppose F has ⋅ L∞ , δ-covering bound obeying log N δ ≤ s log C δ for some constants s ≥ 1, C ≥ R. Given ε ≤ K = K + R, Algorithm 1 Greedily algorithm for resolving sign/scale ambiguities for Leaky ReLU activations.

1: procedure MAXCORR 2: Inputs: Data (y i , x i ) n i=1 , estimates { k( ) } D =1 .

3:

ρ max ← Corr({ k( ) } D =1 , 0) , FLIP←TRUE. } K2 s log C δ ), then for all cover elements T1 + T2 ≤ 2ε. holds with probability at least 1 -exp(-O(n)). To conclude the proof, we need to move from the cover F δ to F. Pick f ∈ F and its δ neighbor f δ ∈ F δ . Utilizing the deterministic relation zm(X) ≤ X + E[X] and using the fact that f δ is in a δ neighborhood of f , we arrive at the following bounds zm(f (x) -f δ (x)) ≤ δ( x 2 + E[ x 2 ]).

(C.8) zm(f (x) + f δ (x) -2y) ≤ 2R( x 2 + E[ x 2 ]) + 2K zm(y) .

(C.9) Next observe that, with probability at least 1 -4n exp (-p) 

:



Figures and Tables:

Figure 1: Depiction of the input-output relationship of a non-overlapping Convolutional Neural Network (CNN) model along with the various notations and symbols.

Definition 4.4 (Rank one CNN tensor) We define the rank one CNN tensor

d = 3, D = 8.

Figure 2: Correlations (corr( k( ) , k ( )

Figure 3: DeepTD estimate vs NaiveTD estimate when final activation is ReLU. Bias of NaiveTD results in significantly worse performance.

=1 d . In particular, we set an oversampling factor N = n ∑ D =1 d and carry out the experiments for N ∈ {10, 20, 50, 100}. While our theory requires N ≳ log D, in our experiments, we typically observe that improvement is marginal after N = 50.

Figure 4: Performance of DeepTD when the final activation is ReLU in lieu of the identity activation.

Lemma A.7 (Dudley's entropy integral) Let N (ε) be the ε covering number of the set T with respect to the d metric. Then γα(T, d) ≤ Cα ∞ 0 log 1 α N (ε)dε, where Cα > 0 depends only on α > 0. D =1 d log D and D ≥ 2. Then

zm(f (xi))Xi). The lemma trivally follows by a scaling by a factor 1 n. We first write the tensor spectral norm as a supremum Yi = zm(f (xi))Xi. Define the random process g(T ) = ∑ n i=1 ⟨zm(Yi), T ⟩. We claim that g(T ) has a mixture of subgaussian and subexponential increments (see Definition A.1 for subgaussian and subexponential random variables). Pick two tensors T , H ∈ R ⊗ D =1 d . Increments of g satisfy the linear relation g(T ) -g(H) = n i=1 ⟨zm(Yi), T -H⟩ .

7. First, let us find the ε covering number of RO. Pick 0 < δ ≤ 1 coverings C of the unit 2 balls B d . These covers have size at most (1 + 2 δ) d . Consider the set of rank 1 tensors C = C1 ⊗ . . . ⊗ C D with size (1 + 2 δ) ∑ D =1 d . For any ⊗ D =1 v ∈ RO, we can pick ⊗ D =1 u ∈ C satisfying vu 2 ≤ δ for all 1 ≤ ≤ D. This implies

d1, d2 metrics are ⋅ F norm scaled by a constant. Hence, their γα functions are scaled versions of (A.8) given by γ1(RO, d1) ≤ cL D =1 d log D, γ2(RO, d2) ≤ cL n D =1 d log D. Now, observe that if n ≥ ∑ D =1 d log D, we have γ1(RO, d1) ≤ cL n ∑ D =1 d log D. Substituting these in (A.5) and using n ≥ ∑ D =1 d log D we find

Figure 5: Tree visualization of a non-overlapping CNN model. The path in bold corresponds to the path vector i = (d 1 , 1, 1, 1) from Definition A.10. For this path the kernel path gain is equal k i = k

Lemma A.16 Let L = γ ⊗ D =1 v be a rank one tensor with {vi} D i=1 vectors of unit norm. Also assume E is a perturbation tensor obeying E ≤ δ. Set u1, u2, . . . , u D = arg max ū1 , ū2 ,..., ūD ⟨L, D ⊗ =1 ū ⟩ subject to ū1 2 = ū2 2 = . . . = ūD 2 = 1. (A.21)

Plugging the latter two inequalities in (B.5), allows to conclude that for ν ≥ 10

is a CNN function of the form (2.1) with kernels {β k( is the function class of all CNN functions with kernels the same as those obtained by DeepTD up to sign/scale ambiguities {β } D =1 where the maximum scale ambiguity is B. Theorem C.1 Let fCNN() be defined via (2.1) with convolutional kernels {k ( ) } D =1 obeying k ( ) 2 ≤ B 1 D for some B > 0 and consider the function class F k,B above with the same choice of B. Assume we have n i.i.d. samples (xi, yi) ∼ (x, y) where x ∼ N (0, Ip) and y = fCNN(x). Suppose for some ε ≤ B, n ≥ cB 2 D log CDBp max 1 , 1 2 , holds for fixed numerical constants c, C > 0. Then the solution f to the CERM problem (C.1) obeys E f (x) -fCNN(x) sample x ∈ N (0, Ip) with probability at least 1 -e -γn -4n exp(-p) with γ > 0 an absolute constant.

is a CNN of the form (2.1) with kernels {β k( ) } D =1 with β ∈ {1, -1}, γ ≥ 0 .

Corr({ k(1) , . . . , -k( ) , . . . , k(D) }, Corr({ k( ) } D =1 , 1). 13: return kernels { k( ) } D =1 , scaling γ.Algorithm 2 Return the correlation between centered labels.1: procedure CORR({ k( ) } D =1 , opt) 2: ŷi ← f CNN ({ k( ) } D =1 ; x i ).

i ← y i -1 n ∑ n i=1 y i and ŷc,i ← ŷi -,i ŷc,i . 5: return ρ if opt = 0, ρ (∑ n i=1 ŷ2 c,i ) if opt = 1. suppose n ≥ O(max{ε -1 , ε -2 } K2 s log C ′ p K ε ) for some C ′ > 0. Then the CERM output (C.1) obeys E[ f (x) -y -E[( f (x) -y)] f (x) -y -E[(f (x) -y)]) 2 ] + ε. (C.5)with probability 1 -exp(-O(n)) -4n exp(-p).Proof Consider the centered empirical loss that can alternatively be written in the form f (xi))) 2 ∶= T1 + T2 (C.6) To prove the theorem, we will simply bound the supremum sup f ∈F E(f ) ≤ sup f ∈F T1 + T2 . Pick a δ covering F δ of F with size s log C δ where δ will be determined later in this proof. We first bound E(f ) for all f ∈ F δ . Given a fixed f , observe that zm(zm(yif (xi)) 2 ) ψ 1 ≤ O( K) 2 = O(K + R) 2 which follows from zm(yif (xi)) ψ 2 ≤ O( K) = O(K + R). Applying subexponential concentration, since T1 is sum of i.i.d. subexponentials, we have P( T1 ≥ ε) ≤ exp(-O(n min{ε 2 K2 , ε K})). (C.7) Next, since zm(yif (xi)) ψ 2 ≤ O( K), we can conclude that 1 n ∑ n i=1 zm(yif (xi)) ψ 2 ≤ O( K) √ n ⇒ T2 ψ 1 ≤ O( K) 2 n.Using (C.7) for T1 and the subexponential tail bound for T2 holds when ε ≤ K, and assuming the number of samples n obeys n ≥ O(max{ε -1 , ε -2

networks: Learning neural networks is a nontrivial task involving non-linearities and nonconvexities. Consequently, existing theory works consider different algorithms, network structures and assumptions. A series of recent work focus on learning zero or one-hidden layer fully connected neural networks with random inputs and planted models(Goel et al. Cohen et al.  (2016)  relate convolutional neural networks and tensor decompositions to provide insights on the expressivity of CNNs.Mondelli & Montanari (2018) connects the hardness of learning shallow networks to tensor decompositions. Closer to this paper,Janzamin et al. (2015) andZhong et al.  (2017b)  apply tensor decomposition on one-hidden layer, fully connected networks to approximately learn the latent weight matrices.

Table content: <table/>

Consider a CNN model per Section 2 with fCNN() the corresponding CNN function per (2.1). We have the following lower bound on the nonlinearity parameter αCNN = ∏

Table content: <table><tr><td/><td/><td/><td/><td/><td>23)</td></tr><tr><td colspan="2">Combining (A.22) and (A.23) we conclude that</td><td/><td/><td/></tr><tr><td>D</td><td/><td/><td/><td/></tr><tr><td>γ</td><td colspan="4">⟨ui, vi⟩ + δ ≥ γ -δ,</td></tr><tr><td colspan="2">i=1</td><td/><td/><td/></tr><tr><td>concluding the proof.</td><td/><td/><td/><td/></tr><tr><td colspan="2">B LOWER BOUNDS ON CNN GAIN</td><td/><td/><td/></tr><tr><td colspan="6">Lemma B.1 D =1 E[φ ′</td><td>(</td><td>h( ) 1 )] from Definition 4.3.</td></tr><tr><td colspan="6">• ReLU model: φ(x) = max(0, x) with the added assumption that the kernels have mean larger than</td></tr><tr><td colspan="3">zero and are modestly diffused. Specifically, assume</td><td/><td/></tr><tr><td/><td/><td>(1 T kr) 2 kr</td><td colspan="2">≥ 4.</td><td>(B.1)</td></tr><tr><td>Then</td><td/><td>αCNN ≥</td><td>1 4</td><td>.</td></tr><tr><td>• softplus model: φ(x) = log (1 + e x</td><td colspan="5">) with the added assumption that the kernels have mean larger</td></tr><tr><td colspan="6">than zero, are modestly diffused and have a sufficiently large Euclidean norm. Specifically, assume</td></tr><tr><td colspan="2">(1 T kr) 2 kr</td><td colspan="2">≥ 10 and</td><td>k</td><td>2 ≥ 1.</td><td>(B.2)</td></tr><tr><td>Then</td><td/><td/><td/><td/></tr><tr><td/><td/><td colspan="3">αCNN ≥ 0.3.</td></tr><tr><td>Proof ReLU: In this case note that</td><td/><td/><td/><td/></tr><tr><td colspan="2">αCNN</td><td/><td/><td/></tr></table>

, all xi, yi obey xi 2 ≤ O(

Table content: <table/>

Peer review (iclr2019):
 This paper provides theoretical guarantees for learning deep convolutional neural networks using rank-one tensor decomposition. In particular, a tensor is first constructed from the given data. Then the authors show that the error between this tensor and its corresponding population counterpart can be bounded. They also show that the population tensor can be approximated by a rank-one tensor whose components are convolutional kernels. Finally, by doing decomposition of this tensor, the kernels can be recovered up to some error. The paper is in general easy to read even if there are a lot of technical notations in it. The analyses also look rigorous. The tensor formulation provides some theoretical insights for deep neural networks since most existing tensor approaches for neural networks can only handle one-layer neural networks. However, I have several concerns about this paper. 1. The assumptions are very strong and mostly unrealistic. For example, 1) the input needs to follow Gaussian distribution; 2) the stride is equal to the kernel size; 3) the input and activations are one-dimensional. 4) the data comes from a planted model. 2. Another caveat of the analyses is that it assumes the constructed tensor can be approximated by a rank-one tensor. However, according to Theorem 4.7, this error highly depends on the ground truth kernels as well as the activation function. This error does not converge to zero asymptotically and is not proved to be a sufficiently small number. In other words, this error may be a significant number that invalidates the proposed tensor decomposition approach for learning deep networks. Recovery guarantees for deep convolutional neural networks are challenging. This paper provides a tensor approach with rigorous analyses. However, the assumptions are too strong and the error bound does not converge to zero asymptotically .