Year: 2020

Abstract:
Many designs have recently been proposed to improve the model efficiency of convolutional neural networks (CNNs) at a fixed resource budget, while there is a lack of theoretical analysis to justify them. This paper first formulates CNNs with high-order inputs into statistical models, which have a special ”Tucker-like” formulation. This makes it possible to further conduct the sample complexity analysis to CNNs as well as compressed CNNs via tensor decomposition. Tucker and CP decompositions are commonly adopted to compress CNNs in the literature. The low rank assumption is usually imposed on the output channels, which according to our study, may not be beneficial to obtain a computationally efficient model while a similar accuracy can be maintained. Our finding is further supported by ablation studies on CIFAR10, SVNH and UCF101 datasets.

heading: 1 INTRODUCTION
text: The introduction of AlexNet (Krizhevsky et al., 2012) spurred a line of research in 2D CNNs, which progressively achieve high levels of accuracy in the domain of image recognition (Simonyan & Zisserman, 2015; Szegedy et al., 2015; He et al., 2016; Huang et al., 2017). The current stateof-the-art CNNs leave little room to achieve significant improvement on accuracy in learning stillimages, and attention has hence been diverted towards two directions. The first is to deploy deep CNNs on mobile devices by removing redundancy from the over-parametrized network, and some representative models include MobileNetV1 & V2 (Howard et al., 2017; Sandler et al., 2018).
The second direction is to utilize CNNs to learn from higher-order inputs, for instance, video clips (Tran et al., 2018; Hara et al., 2017) or electronic health records (Cheng et al., 2016; Suo et al., 2017). This area has not yet seen a widely-accepted state-of-the-art network. High-order kernel tensors are usually required to account for the multiway dependence of the input. This notoriously leads to heavy computational burden, as the number of parameters to be trained grows exponentially with the dimension of inputs. Subsequently, model compression becomes the critical juncture to guarantee the successful training and deployment of tensor CNNs.
Tensor methods for compressing CNNs. Denil et al. (2013) showed that there is huge redundancy in network weights such that the entire network can be approximately recovered with a small fraction of parameters. Tensor decomposition recently has been widely used to compress the weights in a CNN network (Lebedev et al., 2015; Kim et al., 2016; Kossaifi et al., 2020b; Hayashi et al., 2019). Specifically, the weights at each layer are first summarized into a tensor, and then tensor decomposition, CP or Tucker decomposition, can be applied to reduce the number of parameters. Different tensor decomposition to convolution layers will lead to a variety of compressed CNN block designs. For instance, the bottleneck block in ResNet (He et al., 2016) corresponds to the convolution kernel with a special Tucker low-rank structure, and the depthwise separable block in MobileNetV1 (Howard et al., 2017) and the inverted residual block in MobileNetV2 (Sandler et al., 2018) correspond to the convolution kernel with special CP forms. All the above are for 2D CNNs, and Kossaifi et al. (2020b) and Su et al. (2018) considered tensor decomposition to factorize convolution kernels for higher-order tensor inputs.
Tensor decomposition can also be applied to fully-connected layers since they may introduce a large number of parameters (Kossaifi et al., 2017; 2020a); see also the discussions in Section 5. Moreover, Kossaifi et al. (2019) summarized all weights of a network into one single high-order tensor, and then directly imposed a low-rank structure to achieve full network compression. While the idea is
highly motivating, the proposed structure of the high-order tensor is heuristic and can be further improved; see the discussions in Section 2.4.
Parameter efficiency of the above proposed architectures was heuristically justified by methods, such as FLOPs counting, naive parameter counting and/or empirical running time. However, there is still lack of a theoretical study to understand the mechanism of how tensor decomposition can compress CNNs. This paper attempts to fill this gap from statistical perspectives.
Sample Complexity Analysis. Du et al. (2018a) first characterized the statistical sample complexity of a CNN; see also Wang et al. (2019) for compact autoregressive nets. Specifically, consider a CNN model, y = FCNN(x,W) + ξ, where y and x are output and input, respectively, W contains all weights and ξ is an additive error. Given the trained and true underlying networks FCNN(x,Ŵ) and FCNN(x,W ∗), the root-mean-square prediction error is defined as
E(Ŵ) = √ Ex|FCNN(x,Ŵ)− FCNN(x,W∗)|2, (1)
where Ŵ and W∗ are trained and true underlying weights, respectively, and Ex is the expectation on x. The sample complexity analysis is to investigate how many samples are needed to guarantee a given tolerance on the prediction error. It can also be used to detect the model redundancy. Consider two nested CNNs, where F1 is more compressed than F2. Given the same true underlying networks, when the prediction errors from trained F1 and F2 are comparable, we then can argue that F2 has redundant weights comparing with F1. As a result, conducting sample complexity analysis to CNNs with higher order inputs will shed light on the compressing mechanism of popular compressed CNNs via tensor decomposition.
The study in Du et al. (2018a) is limited to 1-dimensional convolution with a single kernel, followed by weighted summation, and its theoretical analysis cannot be generalized to CNNs with compressed layers. In comparison, our paper presents a more realistic modeling of CNN by introducing a general N -dimensional convolution with multiple kernels, followed by an average pooling layer and a fully-connected layer. The convolution kernel and fully-connected weights are in tensor forms, and this allows us to explicitly model compressed CNNs via imposing low-rank assumption on weight tensors. Moreover, we used an alternative technical tool, and a sharper upper bound on the sample complexity can be obtained.
Our paper makes three main contributions:
1. We formulate CNNs with high-order inputs into statistical models, and show that they have an explicit “Tucker-like” form.
2. The sample complexity analysis can then be conducted to CNNs as well as compressed CNNs via tensor decomposition, with weak conditions allowing for time-dependent inputs like video data.
3. From theoretical analysis, we draw an interesting finding that forcing low dimensionality on output channels may introduce unnecessary parameter redundancy to a compressed network.

heading: 1.1 COMPARISON WITH OTHER EXISTING WORKS
text: Deep neural networks are usually over-parametrized, yet empirically, they can generalize well. It is an important topic in the literature to theoretically study the generalization ability of deep neural networks, including deep CNNs (Li et al., 2020; Arora et al., 2018). The generalization error, defined as the difference between test and training errors, is commonly used to evaluate such ability, and many techniques have been developed to control its bound; see, for example, the VC dimension (Vapnik, 2013), the Rademacher complexity & covering number (Bartlett & Mendelson, 2002), the norm-based capacity control (Neyshabur et al., 2017; Golowich et al., 2018; Bartlett et al., 2017; Neyshabur et al., 2015) and low-rank compression based methods (Li et al., 2020; Zhou & Feng, 2018; Arora et al., 2018). These works use a model-agnostic framework, and hence relies heavily on explicit regularization such as weight decay, dropout or data augumentation, as well as algorithmbased implicit regularization to remove the redundancy in the network.
We, however, attempt to theoretically explain how much compressibility is achieved in a compressed network architecture. Specifically, we make a comparison between a CNN and its compressed version, and makes theoretically-supported modification to the latter to further increase efficiency.
Subsequently, our analysis requires an explicit formulation for the network architecture, which is provided in Section 2, and the prediction error at (1) is adopted as our evaluation criteria. We notice that Li et al. (2020) also proposes to use the CP Layers to compress the weights in each convolution layer. But their study is still model-agnostic, since the ranks of the underlying CP Layers depend on the trained weights. In details, their proposed approach uses regularization assumptions on the weights and hence, their derived theoretical bound is influenced by training and not suitable to analyze the network design exclusively.
Other existing works, that aim to provide theoretical understanding for the neural networks, include the understanding of parameter recovery with gradient-based algorithms for deep neural networks (Zhong et al., 2017b; Fu et al., 2020; Goel et al., 2018; Zhong et al., 2017a); the development of other provably efficient algorithms (Cao & Gu, 2019; Du & Goel, 2018); and the investigation of convergence in an over-parameterized regime (Allen-Zhu et al., 2019; Li & Liang, 2018; Du et al., 2018b). Our work differs greatly from these works in both target and methodology. We do not consider computational complexity or algorithm convergence. Instead, we focus on the statistical sample complexity to depict the mechanism of compressed block designs for CNNs.

heading: 2 FORMULATING CNNS WITH HIGHER-ORDER INPUTS

heading: 2.1 NOTATION
text: Tensor notations. We follow the notations in Kolda & Bader (2009) to denote vectors by lowercase boldface letters, e.g. a; matrices by capital boldface letters, e.g. A; tensors of order 3 or higher by Euler script boldface letters, e.g. A. For an N th-order tensor A ∈ Rl1×···×lN , denote its elements by A(i1, i2, . . . , iN ) and the n-mode unfolding by A(n), where the columns of A(n) are the n-mode vectors of A, for 1 ≤ n ≤ N . And A(:, · · · , in, · · · , :) denotes the subtensor of A, holding only the nth index fixed. The vectorization operation is denoted by vec(·). The inner product of two tensors A,B ∈ Rl1×···×lN is defined as 〈A,B〉 =∑ i1 · · · ∑ iN A(i1, . . . , iN )B(i1, . . . , iN ), and the Frobenius norm is ‖A‖F = √ 〈A,A〉. The mode-n multiplication ×n of a tensor A ∈ Rl1×···×lN and a matrix B ∈ Rpn×ln is defined as (A×n B)(i1, . . . , jn, . . . , iN ) = ∑ln in=1
A(i1, . . . , in, . . . , iN )B(jn, in), for 1 ≤ n ≤ N , respectively. The mode-n multiplication ×̄N of a tensor A ∈ Rl1×···×lN and a vector b ∈ Rln is defined as (A×̄nb)(i1, . . . , in−1, in+1, . . . , iN ) = ∑ln in=1
A(i1, . . . , in, . . . , iN )b(in), for 1 ≤ n ≤ N . The symbol “⊗” is the Kronecker product and “◦” is the outer product. We extend the definition of Khatri-Rao product to tensors: given tensors A ∈ Rl1×l2×···lN×K and B ∈ Rp1×p2×···pN×K , their Khatri-Rao product is a tensor of size Rl1p1×l2p2×···lNpN×K , denoted by C = A B, where C(:, · · · , k) = A(:, · · · , k)⊗B(:, · · · , k), 1 ≤ k ≤ K. CP decomposition. The Canonical Polyadic (CP) decomposition (Kolda & Bader, 2009) factorizes the tensor A ∈ Rl1×···×lN into a sum of rank-1 tensors, i.e. A = ∑R r=1 αrh (1) r ◦ h(2)r ◦ · · · ◦ h(N)r , where h(j)r is a unit norm vector of size Rlj for all 1 ≤ j ≤ N . The CP rank is the number of rank-1 tensors R.
Tucker decomposition. The Tucker ranks of an N th-order tensor A ∈ Rl1×···×lN are defined as the matrix ranks of the unfoldings of A along all modes. If the Tucker ranks of A are (R1, . . . , RN ), then there exist a core tensor G ∈ RR1×···×RN and matrices H(i) ∈ Rli×Ri , such that A = G×1 H(1) ×2 H(2) · · · ×N H(N), known as Tucker decomposition (Tucker, 1966),

heading: 2.2 BASIC THREE-LAYER CNNS
text: Consider a three-layer CNN with one convolution, one average pooling and one fully-connected layers, and we assume linear activations for simplicity. Specifically, for a general tensor-structured input X ∈ Rd1×d2×···×dN , we first perform its convolution with an N th-order kernel tensor A ∈ Rl1×l2×···×lN to get an intermediate output Xc ∈ Rm1×m2×···×mN , and then use average pooling with pooling sizes (q1, · · · , qN ) to derive another intermediate output Xcp ∈ Rp1×p2×···×pN . Finally, Xcp goes through a fully-connected layer, with weight tensor B ∈ Rp1×p2×···×pN to produce a scalar output; see Figure 1(1).
We consider the convolution layer with the stride size of sc along each dimension. Assume that mj = (dj − lj)/sc + 1 are integers for 1 ≤ j ≤ N , otherwise zero-padding will be needed. Let
U (j) ij = [ 0︸︷︷︸ (ij−1)sc I︸︷︷︸ lj 0︸︷︷︸ dj−(ij−1)sc−lj ]′ ∈ Rdj×lj for 1 ≤ ij ≤ mj , 1 ≤ j ≤ N, (2)
which act as positioning factors to stretch the kernel tensor A into a tensor of the same size as X, while the rest of entries are filled with zeros; see Figure 1(2). As a result, Xc has entries
Xc(i1, i2, . . . , iN ) = 〈X,A×1 U (1)i1 ×2 U (2) i2 ×3 · · · ×N U (N)iN 〉.
For the pooling layer with the stride size of sp along each dimension, we assume the pooling sizes {qj}Nj=1 satisfy the relationship of mj = qj + (pj − 1)sp, so the sliding windows can be overlapped. But for ease of notation, we can simply take qj = mj/pj . The average pooling operation is equivalent to forming p1p2p3 · · · pN consecutive blocks within Xc, each of size Rq1×q2×···×qN , and then take the average per block. The resulting tensor Xcp has entries Xcp(i1, i2, . . . , iN ) = ( ∏ j qj) −1∑ j ∑ijqj kj=(ij−1)qj+1 Xc(k1, k2, . . . , kN ), for 1 ≤ ij ≤ pj and 1 ≤ j ≤ N . If we denote U (j)F,ij = q −1 j ∑ijqj k=(ij−1)qj+1 U (j) k , then equivalently,
Xcp(i1, i2, . . . , iN ) = 〈X,A×1 U (1)F,i1 ×2 U (2) F,i2 ×3 · · · ×N U (N) F,iN 〉.
The fully-connected layer performs a weighted summation over Xcp, with weights given by entries of the tensor B ∈ Rp1×p2×···×pN . Denote U (j)F = (U (j) F,1, · · · ,U (j) F,pj ) for 1 ≤ j ≤ N , and the predicted output has the form of
ŷ = 〈Xcp,B〉 = 〈X, (B⊗A)×1 U (1)F ×2 U (2) F ×3 · · · ×N U (N) F 〉.
Similarly, for a CNN with K kernels, denote {Ak,Bk}Kk=1 to be the set of kernels and fullyconnected weights, where Bk ∈ Rp1×p2×···×pN and Ak ∈ Rl1×l2×···×lN . The model can then be explicitly represented by
yi = ŷi + ξi = 〈Xi,WX〉+ ξi, 1 ≤ i ≤ n, (3) where ξi is the additive error, Xi ∈ Rd1×d2×···×dN , and the composite weight tensor
WX = ( K∑ k=1 Bk ⊗Ak)×1 U (1)F ×2 U (2) F ×3 · · · ×N U (N) F . (4)
The innate weight-sharing compactness of CNN can be equivalently represented as a “Tucker-like” form at (4). The factor matrices {U (j)F ∈ Rdj×ljpj}Nj=1 are fixed and solely determined by CNN operations on the inputs. They have full column ranks given that pj lj ≤ dj always holds. The core tensor is a special Kronecker product that depicts the layer-wise interaction between weights.

heading: 2.3 SAMPLE COMPLEXITY ANALYSIS
text: We can now derive the non-asymptotic error bound for the CNN model. Let Zi = Xi ×1 U (1)′F ×2 U
(2)′ F ×3 · · · ×N U (N)′ F ∈ Rl1p1×l2p2×···×lNpN . Model (3) is equivalent to
yi = 〈Zi,W〉+ ξi = K∑ k=1 〈Zi,Bk ⊗Ak〉+ ξi, (5)
where W = ∑K k=1 Bk ⊗Ak. The trained weights have the form of Ŵ = ∑K k=1 B̂k ⊗ Âk, where
{B̂k, Âk}1≤k≤K = arg min Bk,Ak,1≤k≤K
1
n n∑ i=1
( yi −
K∑ k=1 〈Zi,Bk ⊗Ak〉
)2 . (6)
Denote xi = vec(Xi) and zi = vec(Zi), and it can be verified that zi = U ′Gx i, where UG = U (1) F ⊗ {U (N) F ⊗ [U (N−1) F ⊗ · · · ⊗ (U (3) F ⊗U (2) F )]} represents the CNN operations on the inputs. Let x̄ = (x1′,x2′, . . . ,xn′)′, and we make the following technical assumptions. Assumption 1. (Time-dependent inputs) x̄ is normally distributed with mean zero and variance Σ = E(x̄x̄′), where cxI ≤ Σ ≤ CxI for some 0 < cx < Cx.
Denote by λmax(A) and λmin(A) the maximum and minimum eigenvalues of a symmetric matrix A, respectively. When {xi} is a stationary time series with spectral density function fX(θ), we can take cx = inf−π≤θ≤π λmin(fX(θ)) and Cx = sup−π≤θ≤π λmax(fX(θ)); see Basu & Michailidis (2015). For independent inputs, Σ = diag{Σ11, . . . ,Σnn} is block diagonal, and it holds that cx = min1≤j≤n λmin(Σjj) and Cx = max1≤j≤n λmax(Σjj), where Σjj = E(xjxj′). Assumption 2. (Sub-Gaussian errors) {ξi} are independent σ2-sub-Gaussian random variables with mean zero, and is independent of {Xj , 1 ≤ j ≤ i} for all 1 ≤ i ≤ n. Assumption 3. (Restricted isometry property) cuI ≤ U ′GUG ≤ CuI for some 0 < cu < Cu.
Denote κU = CxCu and κL = cxcu. Let W ∗ = ∑K k=1 B ∗ k ⊗A ∗ k be the true weight. The model complexity of CNN at (5) is dM = K(P + L+ 1), where P = p1p2 · · · pN and L = l1l2 · · · lN . Theorem 1 (CNN). Suppose that Assumptions 1-3 hold and n & (κU/κL)2dM. Then,
‖Ŵ−W∗‖F ≤ 16σ √ αRSM
αRSC
(√ dM n + √ δ n ) and, E(Ŵ) ≤ √ κU‖Ŵ−W∗‖F
with probability 1− 4 exp{−[cH(0.25κL/κU )2n− 9dM]} − exp{−dM − 8δ}, where δ = Op(1), cH is a positive value, αRSC = κL/2, and αRSM = 3κU/2.
It can be seen that the prediction error E(Ŵ), is Op( √ dM/n), and hence the sample complexity is of order O(dM/ε2), to achieve a prediction error ε. Technical proofs of all theorems and corollary in the paper are deferred to Appendix A.3.
Note that, for simplicity, we assume a simple regression model at (5). The theoretical analysis can indeed be established for classification problems as well. In details, we provide corresponding theorem and corollaries for both binary and multiclass classification problems in Appendix A.4.

heading: 2.4 CNNS WITH MORE LAYERS
text: Consider a 5-layer CNN with “convolution → pooling → convolution → pooling → fully connected” layers, where the settings for the first “convolution→ pooling” layers are the same as those in Section 2.2.
Denote the kernel for the second convolution by Ã ∈ Rl̃1×l̃2×···×l̃N , and the fully-connected weight tensor B is of size Rp̃1×p̃2×···×p̃N . We similarly define matrices Ũ (j)ij and Ũ (j) F,ij , which are both of size Rpj×l̃j with 1 ≤ ij ≤ p̃j and 1 ≤ j ≤ N , and can be used to represent the second convolution and pooling operations, respectively. Note that the output from the first pooling layer, Xcp, is the input to the second convolution layer, and hence the output from the second pooling layer has entries
X̃cp(i1, i2, . . . , iN ) = 〈Xcp, Ã×1 Ũ (1)F,i1 ×2 Ũ (2) F,i2 ×3 · · · ×N Ũ (N) F,iN 〉.
Stack the matrices {U (j)F,ij ∈ R dj×lj}1≤ij≤pj and {Ũ (j) F,ij ∈ R pj×l̃j}1≤ij≤p̃j into 3D tensors U (j) ∈ Rdj×lj×pj and Ũ (j) ∈ Rpj×l̃j×p̃j , respectively. Let U (j)DF = (U (j) ×3 Ũ (j)
)(1) for 1 ≤ j ≤ N and, by some algebra in Appendix A.2, we can show that the predicted output has the form of
ŷ = 〈X̃cp,B〉 = 〈X, (B⊗ Ã⊗A)×1 U (1)DF ×2 U (2) DF ×3 · · · ×N U (N) DF 〉, (7)
where U(j)×3Ũ (j) yields a tensor of size Rdj×lj×l̃j×p̃j , with ∑pj i=1 U (j)(k1, k2, i)Ũ (j)
(i, k3, k4) as its (k1, k2, k3, k4)th entry. The case with multiple kernels will have a form similar to (4). Following the same logic, it can indeed be generalized to an even deeper CNN by adding more “convolutionpooling” layers. Since the composite weight tensor always has a “Tucker-like” form, techniques in proving Theorem 1 can be adopted to conduct the sample complexity analysis for deep CNNs.
Note that, at model (7), the kernels at different convolution layers appear in the form of Ã⊗A, which actually provides a theoretical justification for exploring the layer-wise low-dimensional structure in the literature. On the other hand, we summarize all weights of a network into one single tensor, akin to Kossaifi et al. (2019). But our summarized tensor has an explicit “nested doll” structure, where the weight structure of the previous layer is nested within that of the current layer.
In practice, zero-padding can be used before each convolution layer to preserve the input size. This is compatible with our framework, since we can propagate the padding of zeros to previous layers and all the way back to the input tensor X.

heading: 3 COMPRESSED CNNS
text: For a high-order input, a deep CNN with a larger number of kernels may involve heavy computation, which renders its training difficult for portable devices with limited resources. In real applications, many compressed CNN block designs have been proposed to improve the efficiency, and most of them are based on either matrix factorization or tensor decomposition; see Lebedev et al. (2015); Kim et al. (2016); Astrid & Lee (2017); Kossaifi et al. (2020b).
Tucker decomposition can be used to compress CNNs, which is same as introducing a multilayer CNN block; see Figure 3 in Kim et al. (2016). Specifically, we stack the kernels Ak ∈ Rl1×l2×···×lN with 1 ≤ k ≤ K into a higher order tensor Astack ∈ Rl1×l2×···×lN×K , and assume that Astack has Tucker ranks of (R1, R2, · · · , RN , RN+1). As a result,
Astack = G×1 H(1) ×2 H(2) · · · ×N+1 H(N+1), (8) where G ∈ RR1×···×RN×RN+1 is the core tensor, and H(j) ∈ Rlj×Rj are factor matrices for 1 ≤ j ≤ N + 1. From Section 2, to train such a compressed CNN block with linear activations is equivalent to search for the least-square estimators at (6) with Astack being constrained to have the form of (8). Denote the estimators by {B̂ TU k , Â TU
k }1≤k≤K . The trained weights then have a form of ŴTU = ∑K k=1 B̂ TU k ⊗Â TU k , and the model complexity is d TU M = ∏N+1 j=1 Rj+ ∑N i=1 liRi+RN+1P .
CP decomposition is more popular in compressing CNNs; see Kossaifi et al. (2020b); Lebedev et al. (2015); Astrid & Lee (2017). Let {B̂ CP k , Â CP
k }1≤k≤K be the least-square estimators at (6) with Astack having a CP decomposition with a rank of R. Then, the trained weights are ŴCP =∑K k=1 B̂ CP k ⊗ Â CP k , and the model complexity is d CP M = R N+1 +R( ∑N i=1 li + P ).
Theorem 2 (Compressed CNN). Let (Ŵ, dM) be (ŴTU, dTUM ) for Tucker decomposition, or (ŴCP, d CP M ) for CP decomposition. Suppose that Assumptions 1-3 hold and n & (κU/κL)
2cNdM. Then,
‖Ŵ−W∗‖F ≤ 16σ √ αRSM
αRSC
(√ cNdM n + √ δ n ) and, E(Ŵ) ≤ √ κU‖Ŵ−W∗‖F
with probability 1−4 exp{−[cH(0.25κL/κU )2n−3cNdM]}−exp{−dM−8δ}, where δ = Op(1), cN = 2 N+1 log(N + 2), cH is a positive value and αRSC, αRSM are defined in Theorem 1.
Theorem 2 shows that, as expected, the sample complexity is proportional to the model complexity. Compared to Theorem 1, we see that the sample complexity of the compressed CNN depends on∑N i=1 li instead of ∏N i=1 li. When the input dimension N is large, compressed CNN can indeed reduce a large number of parameters.
However, we notice that the sample complexity of a compressed CNN depends on the rank RN+1 or R, rather than the number of kernels K. This differs from the naive parameter counting, and we hence provide the rationale behind this counter-intuitive observation in the corollary below.
Corollary 1. (a) If A has a Tucker decomposition with the ranks of (R1, R2, · · · , RN+1), the CNN is equivalent to one with RN+1 kernels, and each kernel Ar, where 1 ≤ r ≤ RN+1, has a Tucker decomposition with ranks of (R1, R2, · · · , RN ). Moreover, (b) if the stacked kernel tensor A has a CP decomposition with rank R, the corresponding CNN can be reparameterized into one with R kernels, and each kernel Ar, where 1 ≤ r ≤ R, has a CP decomposition form with rank R.
Define the K/R ratio to be the value of K/RN+1 for Tucker decomposition or K/R for CP decomposition, and in practice, it always holds that K ≥ R. Corollary 1 essentially states that when K/R > 1, there exists model redundancy in the CNN model with linear activations. In other words, we can obtain a more compressed network by setting K = R such that it has the same sample complexity as the previous one. The K/R ratio appears in various block designs; see Figure 2. And we can use this finding to evaluate their model efficiency.
(T1) Standard bottleneck block. The basic building block in ResNet (He et al., 2016) can be exactly replicated by a Tucker decomposition on Astack ∈ Rl1×l2×C×K , with ranks of (l1, l2, R,R), where C is the number of input channels (Kossaifi et al., 2020b). As shown by the ablation studies in Session 4, when K R, this design may not be the most parameter efficient. (T2) Funnel block. As a straightforward revision on a standard bottleneck block, the funnel block maintains an output channel size of K = R. This is hence an efficient block design. Also, when R = C, we obtain a normalized funnel block, with the same number of input and output channels.
(C1) Depthwise separable block. This block is the basic module in MobileNetV1 (Howard et al., 2017) with a pair of depthwise and pointwise separable convolution layers. It is equivalent to assuming a CP decomposition on Astack ∈ Rl1×l2×C×K with the rank of C (Kossaifi et al., 2020b). The 1 × 1 pointwise convolution expands the numbers of channels from C to K. When K C, this design is parameter inefficient from a computation viewpoint.
(C2) Inverted residual block. Sandler et al. (2018) later proposed this design in MobileNetV2. It includes expansive layers between the input and output layers, with the channel size of x ·C(x ≥ 1), where x represents the expansion factor. As discussed by Kossaifi et al. (2020b), it can heuristically correspond to a CP decomposition on Astack, with CP rank equals to x ·C. Since, the rank of output channel dimension can be at most x · C, as long as K ≤ x · C holds, it is theoretically efficient and provides leeway for exploring thicker layers within blocks.
With nonlinear activations, the model redundancy may bring some benefit. Such benefit is often not guaranteed. And when K R, it will, without a doubt, greatly hinder computational efficiency. We will show, in our ablation studies in the next section, that under realistic settings with nonlinear activations, our finding on the K/R ratio still applies. Specifically, networks with K/R = 1 maintains comparable performance as networks with K/R > 1, while using much less parameters.

heading: 4 EXPERIMENTS
text: This section first verifies the theoretical results with synthetic datasets, and then conducts ablation studies on the bottleneck blocks in ResNet (He et al., 2016) with different K/R ratios.

heading: 4.1 NUMERICAL ANALYSIS FOR THEORETICAL RESULTS
text: We choose four settings to verify the sample complexity in Theorem 1; see Table 1. The parameter tensors {Ak,Bk}Kk=1 are generated to have standard normal entries. We consider two types of
inputs: the independent inputs are generated with entries being standard normal random variables, and the time-dependent inputs {xi} are generated from a stationary VAR(1) process. The random additive noises are generated from the standard normal distribution. The number of training samples n varies such that √ dM/n is equally spaced in the interval [0.15, 0.60], with all other parameters fixed. For each n, we generate 200 training sets to calculate the averaged estimation error in Frobenius norm. It can be seen that the estimation error increases linearly with the square root of dM/n, which is consistent with our finding in Theorem 1.
For Theorem 2, we also adopt four different settings; see Table 1. Here, we consider 4D input tensors. The stacked kernel Astack is generated by (8), where the core tensor has standard normal entries and the factor matrices are generated to have orthonormal columns. The number of training
samples n is similarly chosen such that √ dTUM /n is equally spaced. A linear trend between the estimation error and the square root of dTUM /n can be observed, which verifies Theorem 2.
For details of implementation, we employed the gradient descent method for the optimization with a learning rate of 0.01 and a momentum of 0.9. The procedure is deemed to have reached convergence if the target function drops by less than 10−8.

heading: 4.2 ABLATION STUDIES ON COMPUTATIONALLY-EFFICIENT BLOCK DESIGNS
text: Following the notation in Section 3, we denote by K, the number of output channels of a bottleneck block, and by R, the Tucker rank of Astack along the output channels dimension. Since K ≥ R, we let t = K/R be the expansive ratio of the block. As t increases, the number of parameters within the block increases. Here, ablation studies are conducted to show that the increase in t does not necessarily lead to the increase in test accuracy. We analyze two image recognition datasets, CIFAR10 (Krizhevsky et al., 2009) and Street View House Numbers (SVHN) (BNetzer et al., 2011), and an action recognition dataset, UCF101 (Soomro et al., 2012). Standard data pre-processing and augmentation techniques are adopted to all three datasets (He et al., 2016; Hara et al., 2017).
Network architecture. Two network architectures are considered in our study; as shown in Figure 4. For image recognition datasets, we adopt a 41-layer Residual Network: it consists of a 3 × 3 convolution layer, a max pooling layer, followed by 3 groups of A + x × B residual blocks with different R, and ends with an average pooling and fully-connected layer. Block B represents the bottleneck structure that we are interested in. The standard bottleneck block corresponds to t = 4. When t = 1, it corresponds to the normalized funnel block in Section 3 (T2). For sake of
comparison, we also take t = 8 or 16. When t > 1, Block A is the standard downsampling block that contains convolution with the stride size of 2. It is inefficient according to our study. So when t = 1, we propose minor revisions to simultaneously increase the channels while performing the stride-2 3× 3 convolution. For UCF101 dataset, we use 3D ResNet-18 as the basic framework and insert 4 stacks of Block B with R = 256 before the average pooling and fully-connected layer.
Results. The results in Table 2 provide empirical support for our theoretical finding. Though the number of parameters in the network increases with larger t, the overall test accuracy remains roughly comparable. For CIFAR-10, it may appear that the test accuracy for t = 16 is slightly better than t = 1 but it uses 5 times as many parameters.
Implementation details. All experiments are conducted in PyTorch and on Tesla V100-DGXS. Following the practice in He et al. (2016), we adopt batch normalization(BN) (Ioffe & Szegedy, 2015) right after each convolution and before the ReLU activation. For network (1), we initialize the weights as in He et al. (2015). We use stochastic gradient descent with weight decay 10−4, momentum 0.9 and mini-batch size 128. The learning rate starts from 0.1 and is divided by 10 for every 100 epochs. We stop training after 300 epochs, since the training accuracy hardly changes. The training accuracy is approximately 93% for CIFAR-10 and 96% for SVHN. We set seeds 1-5 and report the worst case scenario of the test accuracy in Table 2. For network (2), we follow Hara et al. (2018) and use the Kinetics pretrained 3D ResNet-18. The weights are fixed for the first few layers, and backward propagation is only applied to the added Block B layers and the fully-connected layer. We use stochastic gradient descent with weight decay 10−5, momentum 0.9 and mini-batch size 64 with 16 frames per clip. The learning rate starts from 0.001 and divided by 10 for every 30 epochs. Training is stopped after 80 epochs and top-1 clip accuracy is around 79% for UCF101.

heading: 5 CONCLUSION AND DISCUSSION
text: Our paper proposes a unified theoretical framework that can adopt sample complexity analysis as a tool to study the effective number of parameter in a tensor decomposed CNN block. The main practical takeaways are: (i) For a large kernel tensor A (Peng et al., 2017), it is always effective to impose low-rank structure on its input dimensions, such as height, width or time-length, etc; and (ii) It is essential to maintain K/R = 1 for a CNN block in order to increase accuracy in a more parameter efficient way. In this regard, one can either choose a small R with deeper networks or a larger R with shallower networks. In fact, when K/R = 1, the block corresponds exactly to the “straightened” bottleneck in Zagoruyko & Komodakis (2016), who showed in their empirical study that by increasing R in shallow networks, the test accuracy can indeed improve quite significantly.
Since the low-dimensional structure at convolution layers is our focus, tensor decomposition has been applied to the kernel weights Astack only in Section 3. Kossaifi et al. (2017) applied tensor decomposition to fully-connected layers since they may contain a large number of parameters as well. Along the line, we can stack the fully-connected weights Bk ∈ Rp1×p2×···×pN with 1 ≤ k ≤ K into a higher order tensor Bstack ∈ Rp1×p2×···×pN×K , and further consider a Tensor Contraction Layer (TCL) or Tensor Regression Layer (TRL) as in (Kossaifi et al., 2020a). Similar theoretical analysis can be obtained, and we leave it for future research.

heading: A APPENDIX
text: This appendix contains five sections. In the first section, we provide details for our mathematical formulation for a high-order 3-layer CNN. In the next section, we discuss the formulation of a 5- layer CNN as an illustrating example of how to add more layers to our framework. A complete version of Theorems 1&2 together with the technical proofs for Theorems 1&2 and Corollary 1 are provided in the third section. In the fourth section, we extend our settings to classification and subsequently establish theorem and corollaries for binary and multiclass classification problem. More implementation details and results for additional experiments are presented in the last section.

heading: A.1 CNN FORMULATION
text: For a tensor input X ∈ Rd1×···×dN , it first convolutes with an N -dimensional kernel tensor A ∈ Rl1×···×lN with stride sizes equal to sc, and then performs an average pooling with pooling sizes equal to (q1, · · · , qN ). It ends with a fully-connected layer with the weight tensor B and produces a scalar output. We assume that mj = (dj − lj)/sc + 1 are integers for 1 ≤ j ≤ N , otherwise zero-padding will be needed. For ease of notation, we take the pooling sizes {qj}Nj=1 to satisfy the relationship mj = pjqj .
To duplicate the operation of the convolution layer using a simple mathematical expression, we first need to define a set of matrices {U (j)ij ∈ R dj×lj}, where
U (j) ij = [ 0︸︷︷︸ (ij−1)sc I︸︷︷︸ lj 0︸︷︷︸ dj−(ij−1)sc−lj ]′ ∈ Rdj×lj for 1 ≤ ij ≤ mj , 1 ≤ j ≤ N. (9)
U (j) ij
acts as a positioning factor to transform the kernel tensor A into a tensor of same size as the input X, with the rest of the entries equal to zero.
We are ready to construct our main formulation for a 3-layer tensor CNN. To begin with, we first illustrate the process using a vector input x ∈ Rd, with a kernel vector a ∈ Rl; see Fig 5. Using the ith positioning matrix U (1)i , we can propagate the small kernel vector a, into a vector U (1) i a of size Rd, by filling the rest of the entries with zeros. The intermediate output vector has entries given by xc(i) = 〈x,U (1)i a〉, for 1 ≤ i ≤ m. The average pooling operation is equivalent to forming p consecutive vectors within xc, each of size Rq , and then take the average. This results in a vector xcp of size Rp, with ith entry equal to xcp(i) = q−1 ∑iq k=(i−1)q+1 xc(i) = 〈x, q−1 ∑iq k=(i−1)q+1 U (1) k a〉. The fully-connected layer performs a weighted summation over the p vectors, with weights given by entries of the vector b ∈ Rp. This gives us the predicted output ŷ = 〈b,xcp〉 = 〈x,wX〉, where
wX = p∑ i=1 bi 1 q iq∑ k=(i−1)q+1 U (1) k a = U (1) F (b⊗ a) = (b⊗ a)×1 U (1) F ,
and U (1)F = q −1( ∑q k=1 U (1) k , · · · , ∑m k=m−q+1 U (1) k ), and ”×1” represents the mode-1 product.
For matrix input X with matrix kernel A, however, we need 2 sets of positioning matrices, {U (1)i1 } m1 i1=1 and {U (2)i2 } m2 i2=1 , one for the height dimension and the other for width. Then, the intermediate output from convolution has entries given by Xc(i1, i2) = 〈X,U (1)i1 AU (2)′ i2 〉, for 1 ≤ i1 ≤ p1, 1 ≤ i2 ≤ p2. For the average pooling, we form p1p2 consecutive matrices from Xc, each of size Rq1×q2 and take the average. This results in Xcp ∈ Rp1×p2 , with Xcp(i1, i2) = 〈X, (q−11 ∑i1q1 k1=(i1−1)q1+1 U (1) k1 )A(q−12 ∑i2q2 k2=(i2−1)q2+1 U (2) k2
)′〉. The output Xcp goes through fully-connected layer with weight matrix B and gives the predicted output ŷ = 〈X,WX〉, where
WX = p2∑ i2=1 p1∑ i1=1 bi1bi2 1 q1q2 ( i1q1∑ k1=(i1−1)q1+1 U (1) k1 )A( i2q2∑ k2=(i2−1)q2+1 U (2)′ k2 ) = (B⊗A)×1U (1)F ×2U (2) F ,
with U (j)F = q −1 j ( ∑qj k=1 U (j) k , · · · , ∑mj k=mj−qj+1 U (j) k ) for j = 1 or 2. And ”×1”, ”×2” represent the mode-1 and mode-2 product.
From here, together with the case of high-order tensor input discussed in Session 2.2, we can then derive the form of predicted outcome as ŷ = 〈X,WsingleX 〉, where
W single X = (B⊗A)×1 U (1) F ×2 U (2) F × · · · ×U (N) F ,
with U (j)F = q −1 j ( ∑qj k=1 U (j) k , · · · , ∑mj k=mj−qj+1 U (j) k ), and ”×j” represents the mode-j product for 1 ≤ j ≤ N . With K kernels, we denote the set of kernels and the corresponding fully-connected weight tensors as {Ak,Bk}Kk=1. Since the convolution and pooling operations are identical across kernels, we can use a summation over kernels to derive the weight tensor for multiple kernels, which is
WX = ( K∑ k=1 Bk ⊗Ak)×1 U (1)F ×2 U (2) F × · · · ×U (N) F ,
and we arrive at the formulation for 3-layer tensor CNN.

heading: A.2 FIVE-LAYER CNN FORMULATION
text: Consider a 5-layer CNN with ”convolution→pooling→convolution→pooling→fully connected” layers and a 3D tensor input X ∈ Rd1×d2×d3 . Here, we denote the intermediate output from the first convolution by Xc ∈ Rm1×m2×m3 , from the second convolution by X̃c ∈ Rm̃1×m̃2×m̃3 , and the output from the first pooling by Xcp ∈ Rp1×p2×p3 and from the second pooling by X̃cp ∈ Rp̃1×p̃2×p̃3 . We can first see that the predicted output from the 5-layer CNN is the same as directly feeding Xcp to the second convolution layer, followed by an average pooling layer and a fully-connected layer.
Denote the first convolution kernel tensor by A ∈ Rl1×l2×l3 , the second convolution kernel tensor by A ∈ Rl̃1×l̃2×l̃3 , and the fully-connected weight tensor by B ∈ Rp̃1×p̃2×p̃3 . Define the set of matrices {U (j)ij ∈ R
dj×lj}, for 1 ≤ ij ≤ mj , 1 ≤ j ≤ N as in (2). And similarly, define {Ũ (j)ij ∈ R
pj×l̃j}, with Ũ
(j) ij = [ 0︸︷︷︸ (ij−1)s̃c I︸︷︷︸ l̃j 0︸︷︷︸ pj−(ij−1)s̃c−l̃j ]′, (10)
where s̃c is the stride size for the second convolution. Let Ũ (j) F = (Ũ (j) F,1, · · · , Ũ (j) F,pj ) = (q̃−1j ∑q̃j k=1 Ũ (j) k , · · · , q̃ −1 j ∑m̃j k=m̃j−q̃j+1 Ũ (j) k ). We further stack the matrices {U (j) F,ij ∈
Rdj×lj}1≤ij≤pj and {Ũ (j) F,ij ∈ R pj×l̃j}1≤ij≤p̃j into 3D tensors U (j) ∈ Rdj×lj×pj and Ũ
(j) ∈
Rpj×l̃j×p̃j .
We have that the predicted output
ŷ = 〈B⊗ Ã,Xcp ×1 Ũ (1)′F ×2 Ũ (2)′ F ×3 Ũ (3)′ F 〉
= 〈 B⊗ Ã,
p1∑ i1=1 p2∑ i2=1 p3∑ i3=1 〈A,X×1 U (1)′F,i1 ×2 U (2)′ F,i2 ×3 U (3)′ F,i3〉ũi1 ◦ ũi2 ◦ ũi3
〉
= 〈 B⊗ Ã⊗A,
p1∑ i1=1 p2∑ i2=1 p3∑ i3=1 X×1 (ũi1 ⊗U (1)′ F,i1)×2 (ũi2 ⊗U (2)′ F,i2)×3 (ũi3 ⊗U (3)′ F,i3)
〉
= 〈 B⊗ Ã⊗A,X×1 (U(1) ×3 Ũ (1) )′(1) ×2 (U (2) ×3 Ũ (2) )′(1) ×3 (U (3) ×3 Ũ (3) )′(1) 〉 = 〈 X, (B⊗ Ã⊗A)×1 (U(1) ×3 Ũ (1) )(1) ×2 (U(2) ×3 Ũ (2) )(1) ×3 (U(3) ×3 Ũ (3) )(1)
〉 = 〈 X, (B⊗ Ã⊗A)×1 U (1)DF ×2 U (2) DF ×3 U (3) DF
〉 where ũij = vec(Ũ (1) (ij , :, :)) ∈ Rl̃j p̃j and U (j)DF = (U (j) ×3 Ũ (j)
)(1), for 1 ≤ ij ≤ pj and 1 ≤ j ≤ 3.

heading: A.3 THEORETICAL RESULTS AND TECHNICAL PROOFS
text: Let Zi = Xi×1 U (1)′F ×2 U (2)′ F ×3 · · · ×N U (N)′ F ∈ Rl1p1×l2p2×···×lNpN . The trained weights have the form of Ŵ = ∑K k=1 B̂k ⊗ Âk, where
{B̂k, Âk}1≤k≤K = arg min Bk,Ak,1≤k≤K
1
n n∑ i=1
( yi −
K∑ k=1 〈Zi,Bk ⊗Ak〉
)2 .
Given a test sample (X, y), where y = 〈X,WX〉+ ξ, and (X, ξ) satisfies Assumptions 1 and 2. The mean-square training and test error are defined as
errtrain(Ŵ) = √√√√ 1 n n∑ i=1 ( yi − 〈Xi,ŴX〉 )2 and err(Ŵ) = √ E (X,y) ( y − 〈X,ŴX〉 )2 .
Denote κU = CxCu and κL = cxcu. Let W ∗ = ∑K k=1 B ∗ k ⊗ A ∗ k be the true weights, and
‖W‖2n := n−1 ∑n i=1(〈Z
i,W〉)2 be the empirical norm with respect to W. The model complexity of CNN at equation (1) or (2) is dM = K(P + L+ 1). Theorem 1 (Complete Version). Suppose that Assumptions 1-3 hold and n & (κU/κL)2dM. Then, for some δ > 0,
(a) ‖Ŵ−W∗‖F ≤ 16σ √ αRSM
αRSC
(√ dM n + √ δ n )
(b) ‖Ŵ−W∗‖n ≤ 16σαRSM αRSC (√ dM n + √ δ n )
(c) err2(Ŵ) ≤ (
16σαRSM αRSC )2( dM n + δ n ) + σ2,
with probability 1−4 exp{−[cH(0.25κL/κU )2n−9dM]}−exp{−dM−8δ}, where cH is a positive value, αRSC = κL/2, and αRSM = 3κU/2.
It can be seen that the estimation error, ‖Ŵ −W∗‖F, is Op( √ dM/n), and hence the sample complexity is of order O(dM/ε2), to achieve a training error ε. The empirical norm is equivalent to the training error minus the sample standard deviation of noise. And we can see that the training error errtrain(Ŵ) = Op( √ dM/n) + σ̂ and test error err(Ŵ) = Op( √ dM/n) + σ, where σ̂ and σ represent the sample and population standard deviation of noise, respectively.
Now we proceed to provide a complete version of the sample complexity of compressed CNNs. Let dTUM = ∏N+1 j=1 Rj + ∑N i=1 liRi +RN+1P and d CP M = R N+1 +R( ∑N i=1 li + P ).
Theorem 2 (Complete Version). Let (Ŵ, dM) be (ŴTU, dTUM ) for Tucker decomposition, or (ŴCP, d CP M ) for CP decomposition. Suppose that Assumptions 1-3 hold and n & (κU/κL)
2cNdM. Then, for some δ > 0,
(a)‖Ŵ−W∗‖F ≤ 16σ √ αRSM
αRSC
(√ cNdM n + √ δ n ) ,
(b)‖Ŵ−W∗‖n ≤ 16σαRSM αRSC (√ cNdM n + √ δ n ) ,
(c)err2(Ŵ) ≤ (
16σαRSM αRSC )2( cNdM n + δ n ) + σ2,
with probability 1 − 4 exp{−[cH(0.25κL/κU )2n − 3cNdM]} − exp{−dM − 8δ}, where cN = 2N+1 log(N + 2), cH is a positive value and αRSC, αRSM are defined in Theorem 1.
Because CP decomposition can be considered as a special case of Tucker decomposition where Rj = R, for 1 ≤ j ≤ N + 1. We only provide the proof for Tucker CNN.

heading: A.3.1 PROOF OF THEOREM 1
text: Denote the sets ŜK = { ∑K k=1 Bk ⊗ Ak : Ak ∈ Rl1×l2×···×lN and Bk ∈ Rp1×p2×···×pN } and SK = {W ∈ ŜK : ‖W‖F = 1}. Let ∆̂ = Ŵ−W∗, and then
1
n n∑ i=1 (yi − 〈Zi,Ŵ〉)2 ≤ 1 n n∑ i=1 (yi − 〈Zi,W∗〉)2,
which implies that
‖∆̂‖2n ≤ 2
n n∑ i=1 ξi〈Zi, ∆̂〉 ≤ 2‖∆̂‖F sup ∆∈S2K 1 n n∑ i=1 ξi〈Zi,∆〉, (11)
where ‖∆‖2n := n−1 ∑n i=1(〈Z i,∆〉)2 is the empirical norm with respect to ∆, and ∆̂ ∈ Ŝ2K .
Consider a ε-net S̄2K , with the cardinality of N (2K, ε), for the set S2K . For any ∆ ∈ S2K , there exists a ∆̄j ∈ S̄2K such that ‖∆ − ∆̄j‖F ≤ ε. Note that ∆ − ∆̄j ∈ Ŝ4K and, from Lemma 1(a), we can further find ∆1,∆2 ∈ Ŝ2K such that 〈∆1,∆2〉 = 0 and ∆ − ∆̄j = ∆1 + ∆2. It then holds that ‖∆1‖F + ‖∆2‖F ≤ √ 2‖∆− ∆̄j‖F ≤ √ 2ε since ‖∆− ∆̄j‖2F = ‖∆1‖2F + ‖∆2‖2F. As a result,
1
n n∑ i=1 ξi〈Zi,∆〉 = 1 n n∑ i=1 ξi〈Zi, ∆̄j〉+ 1 n n∑ i=1 ξi〈Zi,∆1〉+ 1 n n∑ i=1 ξi〈Zi,∆2〉
≤ max 1≤j≤N (2K,ε)
1
n n∑ i=1 ξi〈Zi, ∆̄j〉+ √ 2ε sup ∆∈S2K 1 n n∑ i=1 ξi〈Zi,∆〉,
which leads to
sup ∆∈S2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≤ (1− √ 2ε)−1 max 1≤j≤N (2K,ε) 1 n n∑ i=1 ξi〈Zi, ∆̄j〉. (12)
Note that, from Lemma 1(b), logN (2K, ε) ≤ 2dM log(9/ε), where dM = K(P + L + 1). Let ε = (2 √ 2)−1, and then 8− 2 log(9/ε) > 1. As a result, by (12) and Lemma 3,
P [ sup
∆∈S2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≥ 8σ √ αRSM (√ dM n + √ δ n ) , sup ∆∈S2K ‖∆‖2n ≤ αRSM ]
≤ P [ max
1≤j≤N (2K,ε)
1
n n∑ i=1 ξi〈Zi, ∆̄j〉 ≥ 4σ √ αRSM (√ dM n + √ δ n ) , sup ∆∈S2K ‖∆‖2n ≤ αRSM ]
≤ N (2K,ε)∑ j=1 P
( 1
n n∑ i=1 ξi〈Zi, ∆̄j〉 ≥ 4σ √ αRSM (√ dM n + √ δ n ) , ∥∥∆̄j∥∥2n ≤ αRSM ) ≤ exp{−dM − 8δ}.
(13)
Note that
P [ sup
∆∈S2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≥ 8σ √ αRSM (√ dM n + √ δ n )]
≤ P [ sup
∆∈S2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≥ 8σ √ αRSM (√ dM n + √ δ n ) , sup ∆∈S2K ‖∆‖2n ≤ αRSM ]
+ P (
sup ∆∈S2K
‖∆‖2n ≥ αRSM ) .
From (13) and Lemma 2, we then have that, with probability 1 − 4 exp{−[cH(0.25κL/κU )2n − 9dM]} − exp{−dM − 8δ},
sup ∆∈S2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≤ 8σ √ αRSM (√ dM n + √ δ n ) and ‖∆‖2n ≥ αRSC ‖∆‖ 2 F ,
which, together with (11), leads to
‖∆̂‖F ≤ 16σ √ αRSM
αRSC
(√ dM n + √ δ n ) and ‖∆̂‖n ≤ 16σ αRSM αRSC (√ dM n + √ δ n ) .
Finally we prove (c). Given a test sample (X, y), and let Z = X×1U (1)′F ×2U (2)′ F ×3 · · ·×NU (N)′ F . It holds that E(y − 〈X,WX〉)2 = E(y − 〈Z,W〉)2 = E(〈Z,∆〉)2 + σ2,
and E(〈Z,∆〉)2 = ∆′E(z̄z̄′)∆ = ∆′UGE(x̄x̄′)U ′G∆ ≤ κU‖∆‖22.
As a result, from (a) of this theorem, we have err2(Ŵ) ≤ (
16σαRSM αRSC )2( dM n + δ n ) + σ2.
This accomplishes the proof.

heading: A.3.2 PROOF OF THEOREM 2
text: Denote the sets ŜTU(R1, · · · , RN+1) = { ∑K k=1 Bk ⊗ Ak : the stacked kernel Astack ∈ Rl1×l2×···×lN×K has the ranks of (R1, ..., RN , RN+1) and Bk ∈ Rp1×p2×···×pN }, ŜTU2K = {W1 + W2 : W1,W2 ∈ ŜTU(R1, · · · , RN+1)}, and STU2K = {W ∈ ŜTU2K : ‖W‖F = 1}. Note that ŴTU,W ∗ ∈ ŜTU(R1, · · · , RN+1), and ∆̂ = ŴTU −W∗ ∈ ŜTU2K .
We first consider a ε-net for STU2K . For each 1 ≤ k ≤ K, Let bk = (bk1, . . . , bkP )′ = vec(Bk), and we can rearrange Bk ⊗ Ak into the form of Ak ◦ bk, which is a tensor of size Rl1×l2×···×lN×P , where P = p1p2 · · · pN . Denote B = (bkj) ∈ RP×K , and it holds that
K∑ k=1 Ak ◦ bk = A×N+1 B = G×1 H(1) ×2 H(2) · · · ×N+1 B̃,
which is a tensor with the size of Rl1×l2×···×lN×P and the ranks of (R1, ..., RN , RN+1) where B̃ = BH(N+1) ∈ RP×RN+1 . Essentially, in this step, we rewrite the model into one with Rk+1 kernels instead. Specifically, we now have W = ∑RN+1 r=1 Ãr ⊗ B̃r, where Ãr = Gr ×1 H(1) ×2 H(2) · · · ×N H(N) with Gr = G(:, :, · · · , r) and the r-th column of B̃ is the vectorization of B̃r for 1 ≤ r ≤ RN+1.
As a result, ŜTU2K consists of tensors with the ranks of (2R1, ..., 2RN , 2RN+1) at most.
Denote STucker(r1, · · · , rN , rN+1) = {T ∈ Rl1×···×lN×lN+1 : ‖T‖F = 1, T has the Tucker ranks of (r1, · · · , rN , rN+1)}, where lN+1 = P = p1p2 · · · pN . Then the ε-covering number for STU2K satisfies
|STU2K | ≤ |STucker(2R1, · · · , 2RN , 2RN+1)|.
For each T ∈ STucker(r1, · · · , rN , rN+1), we have
T = G×1 U (1) ×2 · · · ×N+1 U (N+1),
where G ∈ Rr1×···×rN×rN+1 with ‖G‖F = 1, and U (i) ∈ Rli×ri with 1 ≤ i ≤ N + 1 are orthonormal matrices. We now construct an ε-net for STucker(r1, · · · , rN , rN+1) by covering the sets of G and all U (i)s, and the proof hinges on the covering number of low-multilinear-rank tensors in Wang et al. (2019). Treating G as ∏N+1 j=1 rj-dimensional vector with ‖G‖F = 1, we can find an
ε/(N + 2)-net for it, denoted by Ḡ, with the cardinality of |Ḡ| ≤ (3(N + 2)/ε) ∏N+1 j=1 rj .
Next, let On,r = {U ∈ Rn×r : U>U = Ir}. To cover On,r, it is beneficial to use the ‖ · ‖1,2 norm, defined as
‖X‖1,2 = max i ‖Xi‖2,
where Xi denotes the ith column of X . Let Qn,r = {X ∈ Rn×r : ‖X‖1,2 ≤ 1}. One can easily check that On,r ⊂ Qn,r, and then an ε/(N + 2)-net Ōn,r for On,r has the cardinality of |Ōn,r| ≤ (3(N + 2)/ε)nr. Denote S̄Tucker(r1, · · · , rN , rN+1) = {G ×1 U (1) ×2 · · · ×N+1 U (N+1) : G ∈ Ḡ, U (i) ∈ Ōli,ri , 1 ≤ i ≤ N + 1}. By a similar argument presented in Lemma A.1 of Wang et al. (2019), we can show that S̄Tucker(r1, · · · , rN , rN+1) is a ε-net for the set STucker(r1, · · · , rN , rN+1) with the cardinality of(
3N + 6
ε
)∏N+1 j=1 rj+ ∑N+1 j=1 ljrj
.
where lN+1 = P . Thus, the ε-covering number of STU2K is
NTU(ε) = |STucker(2R1, · · · , 2RN , 2RN+1)| ≤ ( 3N + 6
ε
)2N+1 ∏N+1j=1 Rj+2∑Ni=1 liRi+2RN+1P .
Let ε = 1/2. It then holds that log(3(N + 2)/ε) < 3 log(N + 2) and logNTU(ε) ≤ 2N+1dTUM log[(3N + 6)/ε], where d TU M = ∏N+1 j=1 Rj + ∑N i=1 liRi +RN+1P . By a method similar to the proof of Lemma 2, we can show that
P { sup
∆∈STU2K ‖∆‖2n ≥ αRSM
} ≤ 2 exp { −cHn ( κL
4κU
)2 + 3cNd TU M } , (14)
and
P { inf
∆∈STU2K ‖∆‖2n ≤ αRSC
} ≤ 2 exp { −cHn ( κL
4κU
)2 + 3cNd TU M } . (15)
where cN = 2N+1 log(N + 2). Moreover, similar to equation 13, by applying Lemma 3, we can show that
P [ sup
∆∈STU2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≥ 8σ √ αRSM (√ cNdTUM n + √ δ n ) , sup ∆∈STU2K ‖∆‖2n ≤ αRSM ]
≤ P [ max
1≤j≤NTU(ε)
1
n n∑ i=1 ξi〈Zi, ∆̄j〉 ≥ 4σ √ αRSM (√ cNdTUM n + √ δ n ) , sup ∆∈STU2K ‖∆‖2n ≤ αRSM ]
≤ NTU(ε)∑ j=1 P
( 1
n n∑ i=1 ξi〈Zi, ∆̄j〉 ≥ 4σ √ αRSM (√ cNdTUM n + √ δ n ) , ∥∥∆̄j∥∥2n ≤ αRSM ) ≤ exp{−dTUM − 8δ},
(16)
where ε = (2 √
2)−1 and 2N+4 log(N + 2) − 2N+1 log(3(N + 1)/ε) > 1. By a method similar to the proof of Theorem 1, we can show that, with probability 1 − 4 exp{−[cH(0.25κL/κU )2n − 3cN log(N + 2)d TU M ]} − exp{−dTUM − 8δ},
sup ∆∈STU2K
1
n n∑ i=1 ξi〈Zi,∆〉 ≤ 8σ √ αRSM (√ cNdTUM n + √ δ n ) and ‖∆‖2n ≥ αRSC ‖∆‖ 2 F ,
which, together with equation 11, leads to
‖∆̂‖F ≤ 16σ √ αRSM
αRSC
(√ cNdTUM n + √ δ n ) ,
‖∆̂‖n ≤ 16σ αRSM αRSC (√ cNdTUM n + √ δ n ) ,
err2(ŴTU) ≤ (
16σαRSM αRSC
)2( cNd
TU M n + δ n
) + σ2.
We accomplished the proof.

heading: A.3.3 PROOFS OF COROLLARY 1
text: When the kernel tensor A has a Tucker decomposition form of A = G×1H(1)×2H(2)×3 · · ·×N+1 H(N+1), and the multilinear rank is (R1, R2, · · · , RN+1). Let H = G×1H(1)×2H(2)×3 · · ·×N H(N), which is a tensor of size Rl1×···×lN×RN+1 . The mode-(N + 1) unfolding of H is a matrix with RN+1 row vectors, each of size RL, and we denote them by g1, · · · , gRN+1 . Fold grs back into tensors, i.e. gr = vec(H̃r), where H̃r ∈ Rl1×···×lN and 1 ≤ r ≤ RN+1. Moreover, let H(N+1) = (h
(N+1) 1 , · · · ,h (N+1) K ) ′, where h(N+1)k is a vector of size RRN+1 and we denote its rth
entry as h(N+1)k,r , for 1 ≤ r ≤ RN+1. It can be verified that, for each 1 ≤ k ≤ K,
Ak = G×1 H(1) ×2 H(2) · · · ×N H(N)×̄N+1h(N+1)k = H×̄N+1h (N+1) k ,
and hence,
K∑ k=1 Bk ⊗Ak = RN+1∑ r=1 K∑ k=1 Bk ⊗ ( H̃r · h(N+1)k,r ) = RN+1∑ r=1 ( K∑ k=1 h (N+1) k,r Bk ) ⊗ H̃r.
By letting B̃r = ∑K k=1 h (N+1) k,r Bk and Ãr = H̃r for 1 ≤ r ≤ RN+1, we can reformulate the model into
yi = 〈 RN+1∑ r=1 B̃r ⊗ Ãr,Zi〉+ ξi,
and the proof of (a) is then accomplished.
Suppose that the kernel tensor A has a CP decomposition form of A = ∑R r=1 αrh (1) r ◦ h(2)r ◦ · · · ◦ h(N+1)r , where h(j)r ∈ Rlj and ‖h(j)r ‖ = 1 for all 1 ≤ j ≤ N . Moreover, h(N+1)r = (h
(N+1) r,1 , ..., h (N+1) r,K ) ′ ∈ RK and ‖h(N+1)r ‖ = 1. Note that
Ak = R∑ r=1 αrh (N+1) r,k h (1) r ◦ h(2)r ◦ · · · ◦ h(N)r ,
for all 1 ≤ k ≤ K, and hence K∑ k=1 Bk ⊗Ak = R∑ r=1 K∑ k=1 Bk ⊗ ( αrh (N+1) r,k h (1) r ◦ h(2)r ◦ · · · ◦ h(N)r ) =
R∑ r=1 ( h (N+1) r,k Bk ) ⊗ ( αrh (1) r ◦ h(2)r ◦ · · · ◦ h(N)r ) .
By letting B̃r = h (N+1) r,k Bk and Ãr = αrh (1) r ◦ h(2)r ◦ · · · ◦ h(N)r for all 1 ≤ r ≤ R, we can reparameterize the model into
yi = 〈 R∑ r=1 B̃r ⊗ Ãr,Zi〉+ ξi,
and the proof of (b) is then accomplished.

heading: A.3.4 LEMMAS USED IN THE PROOFS OF THEOREMS
text: Lemma 1. (Partition and covering number of restricted spaces) Consider ŜK = { ∑K k=1 Bk⊗Ak : Ak ∈ Rl1×l2×···×lN and Bk ∈ Rp1×p2×···×pN } and SK = {W ∈ ŜK : ‖W‖F = 1}.
(a) For any ∆ ∈ Ŝ2K , there exist W1,W2 ∈ ŜK such that ∆ = W1 +W2 and 〈W1,W2〉 = 0.
(b) The ε-covering number of the set SK is
N (K, ε) ≤ (9/ε)K(L+P+1),
where L = l1l2 · · · lN and P = p1p2 · · · pN .
Proof. For eachK, we first define a map TK : ŜK → RP×L. For any W = ∑K k=1 Bk⊗Ak ∈ ŜK ,
we define that TK(W) = ∑K k=1 vec (Bk) vec(Ak) ′ ∈ RP×L, which has the rank of at most K.
For any ∆ ∈ Ŝ2K , the rank of matrix TK(∆) is at most 2K. As shown in Figure 6, we can split the singular value decomposition (SVD) of TK(∆) into two parts, and it can be verified that TK(∆) = U1Λ1V1 ′ + U2Λ2V2 ′ and 〈U1Λ1V1′,U2Λ2V2′〉 = 0. Denote Ui = (u(i)1 ,u (i) 2 , . . . ,u (i) K ) and ViΛ ′ i = (v (i) 1 ,v (i) 2 , . . . ,v (i) K ) for i = 1 and 2. We then fold u (i) j s and v (i) j s into tensors, i.e. u (i) k = vec(B (i) k ) and v (i) k = vec(A (i) k ) with 1 ≤ k ≤ K. Let W1 = ∑K k=1 B (1) k ⊗ A (1) k and
W2 = ∑K k=1 B (2) k ⊗ A (2) k . It then can be verified that W1,W2 ∈ ŜK , ∆ = W1 + W2 and 〈W1,W2〉 = 0. Thus, we accomplish the proof of (a). Denote by Smatrix ⊂ RP×L the set of matrices with unit Frobenius norm and rank at most K. Note that T (SK) ⊂ Smatrix, while the ε-covering number for Smatrix is
|Smatrix| ≤ (9/ε)K(L+P+1);
see Candes & Plan (2011). This accomplishes the proof of (b).
Lemma 2. (Restricted strong convexity and smoothness) Suppose that n & (κU/κL)2dM. It holds that, with probability at least 1− 4 exp{−[cH(0.25κL/κU )2n− 9dM]},
αRSC ‖∆‖2F ≤ 1
n n∑ i=1 (〈Zi,∆〉)2 ≤ αRSM ‖∆‖2F ,
for all ∆ ∈ Ŝ2K , where Ŝ2K is defined in Lemma 1, cH is a positive constant from the HansonWright inequality, αRSC = κL/2 and αRSM = 3κU/2.
Proof. It is sufficient to show that sup∆∈S2K ‖∆‖ 2 n ≤ αRSM and inf∆∈S2K ‖∆‖ 2 n ≥ αRSC hold with a high probability, where ‖∆‖2n := n−1 ∑n i=1(〈Z
i,∆〉)2 is the empirical norm, and S2K is defined in Lemma 1. Without confusion, in this proof, we will also use the notation of ∆ for its vectorized version, vec(∆). Note that
‖∆‖2n = 1
n n∑ i=1 (〈Zi,∆〉)2 = 1 n n∑ i=1 zi′∆∆′zi = 1 n n∑ i=1 xi′UG∆∆ ′U ′Gx i
= 1 n x̄′ [ In ⊗ (UG∆∆′U ′G) ] x̄ = w̄′Qw̄,
(17)
where Q = n−1Σ 1 2 [In ⊗ (UG∆∆′U ′G)]Σ 1 2 , w̄ ∈ RnD is a random vector with i.i.d. standard normal entries, zi = U ′Gx i, xi = vec(Xi), x̄ = (x1′,x2′, . . . ,xn′)′, and Σ = E(x̄x̄′) ∈ RnD×nD.
Denote wG = UG∆ ∈ RD and Sn−1 = {v ∈ Rn : ‖v‖2 = 1}. Let λmax(Σii) be the maximum eigenvalue of Σii = E(vec (Xi) vec (Xi) ′ ) for 1 ≤ i ≤ n, and it holds that λmax(Σii) ≤ Cx for all 1 ≤ i ≤ n. For matrix Q, we have
tr(Q) = 1 n tr ( Σ 1 2 [In ⊗wG][In ⊗w′G]Σ 1 2 ) = 1 n tr ([In ⊗w′G]Σ[In ⊗wG]) = 1 n n∑ i=1 (w′GΣiiwG)
≤ 1 n n∑ i=1
( sup
wG∈SPL−1 w′GΣiiwG w′GwG
)( sup
∆∈SPL−1 ∆′U ′GUG∆ ) ≤ 1 n n∑ i=1 λmax(Σij)Cu ≤ κU ,
(18)
and similarly, we can show that tr(Q) ≥ κL, where κL = cxcu, κU = CxCu and κL ≤ κU . Thus,
κL ≤ E ‖∆‖2n = tr(Q) ≤ κU . (19)
Moreover, denote Q1 = n− 1 2 Σ 1 2 [In ⊗wG] and note that Q = Q1Q′1. To bound the operator norm of Q, we have
‖Q‖op ≤ ‖Q1‖ 2 op = sup u∈Sn−1 u′Q′1Q1u =
1 n sup u∈Sn−1 u′[In ⊗w′G]Σ[In ⊗wG]u
≤ 1 n
( sup
u∈Sn−1 u′[In ⊗w′G]Σ[In ⊗wG]u u′[In ⊗w′G][In ⊗wG]u
)( sup
u∈Sn−1 u′[In ⊗w′GwG]u ) ≤ Cx
n ‖wG‖22 ≤ Cx n ‖UG‖2op ‖∆‖ 2 2 ≤ κU n .
(20)
Finally we can use (18) and (20) to bound the Frobenius norm of Q. By some algebra, for any square matrices A,B ∈ Rn×n, ‖AB‖2F ≤ ‖A‖ 2 op ‖B‖ 2 F holds. Hence,
‖Q‖2F = ‖Q1Q ′ 1‖ 2 F ≤ ‖Q1‖ 2 op ‖Q1‖ 2 F = ‖Q1‖ 2 op tr(Q) ≤ κ2U n .
This, together with (17), (20) and the Hanson-Wright inequality (Vershynin, 2018, Chapter 6), leads to
P {∣∣∣‖∆‖2n − E ‖∆‖2n∣∣∣ ≥ t} ≤ 2 exp { −cH min ( t
‖Q‖ op ,
t2
‖Q‖2F )} ≤ 2 exp { −cHnmin ( t/κU , (t/κU ) 2 )} ,
(21)
where cH is a positive constant.
On the other hand,
‖∆‖2n − E ‖∆‖ 2 n =
1
n n∑ i=1 ∆′zizi′∆− E(∆′zizi′∆) = ∆′Γ̂∆,
where Γ̂ = n−1 ∑n i=1[z
izi′ − E(zizi′)] is a symmetric matrix. Consider a ε-net S̄2K , with the cardinality of N (2K, ε), for the set S2K . For any ∆ ∈ S2K , there exists a ∆̄j ∈ S̄2K such that ‖∆−∆̄j‖F ≤ ε. Note that ∆−∆̄j ∈ Ŝ4K and, from Lemma 1, we can further find ∆1,∆2 ∈ Ŝ2K such that 〈∆1,∆2〉 = 0 and ∆ − ∆̄j = ∆1 + ∆2, and it then holds that ‖∆1‖F + ‖∆2‖F ≤√
2‖∆ − ∆̄j‖F ≤ √
2ε. Moreover, for a general real symmetric matrix A ∈ Rd×d, u ∈ Rd and v ∈ Rd, sup‖u‖2=‖v‖2=1 u ′Av = sup‖u‖2=1 u ′Au. As a result,
∆′Γ̂∆ = ∆̄′jΓ̂∆̄j + (∆1 + ∆2) ′Γ̂(∆1 + ∆2 + 2∆̄j)
≤ max 1≤j≤N (2K,ε) ∆̄′jΓ̂∆̄j + 5ε sup ∆∈S2K ∆′Γ̂∆,
where (‖∆1‖F + ‖∆2‖F)2 + 2(‖∆1‖F + ‖∆2‖F)‖∆̄j‖F ≤ 2(ε + √
2)ε ≤ 5ε as ε ≤ 1, and this leads to
sup ∆∈S2K ∆′Γ̂∆ ≤ (1− 5ε)−1 max 1≤j≤N (2K,ε) ∆̄′jΓ̂∆̄j . (22)
Note that, from Lemma 1(b), logN (2K, ε) ≤ 2dM log(9/ε), where dM = K(L + P + 1). Let ε = 1/10, and then 2 log(9/ε) < 9. Combining (21) and (22) and letting t = κL/2, we have
P {
sup ∆∈S2K
‖∆‖2n − E ‖∆‖ 2 n ≥ κL 2
} ≤ 2 exp { −cHn ( κL
4κU
)2 + 9dM } ,
which, together with (19) and the fact that κL ≤ κU , implies that P {
sup ∆∈S2K
‖∆‖2n ≥ αRSM } ≤ 2 exp { −cHn ( κL
4κU
)2 + 9dM } , (23)
where αRSM = 1.5κU ≥ κU + κL/2. By a method similar to (22), we can also show that
sup ∆∈S2K
E ‖∆‖2n − ‖∆‖ 2 n ≤ (1− 5ε) −1 max 1≤j≤N (2K,ε) E ∥∥∆̄j∥∥2n − ∥∥∆̄j∥∥2n ,
which, together with (21), leads to P {
sup ∆∈S2K
E ‖∆‖2n − ‖∆‖ 2 n ≥ κL 2
} ≤ 2 exp { −cHn ( κL
4κU
)2 + 9dM } ,
where t = κL/2 and ε = 1/10. As a result, P {
inf ∆∈S2K
‖∆‖2n ≤ αRSC } ≤ 2 exp { −cHn ( κL
4κU
)2 + 9dM } ,
where αRSC = κL − κL/2. This, together with (23), accomplishes the proof.
Lemma 3. (Concentration bound for martingale) Let {ξi, 1 ≤ i ≤ n} be independent σ2-subGaussian random variables with mean zero, and {zi, 1 ≤ i ≤ n} is another sequence of random variables. Suppose that ξi is independent of {zi, zi−1, . . . , z1} for all 1 ≤ i ≤ n. It then holds that, for any real numbers α, β > 0,
P
[{ 1
n n∑ i=1 ξizi ≥ α
} ∩ { 1
n n∑ i=1 (zi)2 ≤ β
}] ≤ exp ( − nα 2
2σ2β
) .
Proof. We can prove the lemma by a method similar to Lemma 4.2 in Simchowitz et al. (2018).

heading: A.4 CLASSIFICATION PROBLEMS
text: Starting from Section 2.2, we know that, for each input tensor X, the intermediate scalar output after convolution and pooling has the following form
output = 〈X, K∑ k=1 (Bk ⊗Ak)×1 U (1)F ×2 U (2) F ×3 · · · ×N U (N) F 〉 = 〈Z,W〉,
where W = ∑K k=1 Bk⊗Ak and Z = X×1U (1)′ F ×2U (2)′ F ×3 · · · ×N U (N)′ F , Ak ∈ Rl1×l2×···×lN is the kth kernel and Bk ∈ Rp1×p2×···×pN is the corresponding kth fully-connected weight tensor. Consider a binary classification problem. We have the binary label output y ∈ {0, 1} with
p(y|Z) = (
1
1 + exp(〈Z,W〉)
)1−y ( exp(〈Z,W〉)
1 + exp(〈Z,W〉)
)y = exp {y〈Z,W〉 − log [1 + exp(〈Z,W〉)]} .
Suppose we have samples {Zi, yi}ni=1, we use the negative log-likelihood function as our loss function. It is given, up to a scaling of n−1 by
Ln(W) = − 1
n n∑ i=1 yi〈Zi,W〉+ 1 n n∑ i=1 φ(〈Zi,W〉), (24)
where φ(z) = log(1 + ez) and its gradient and Hessian matrix is
∇Ln(W) = ∂Ln(W) ∂ vec(W) = − 1 n n∑ i=1 yi vec(Zi) + 1 n n∑ i=1 φ′(〈Zi,W〉) vec(Zi) and, (25)
Hn(W) = ∂2Ln(W) ∂2 vec(W) = 1 n n∑ i=1 φ′′(〈Zi,W〉) vec(Zi) vec(Zi)′, (26)
with φ′(z) = 1/(1 + e−z) ∈ (0, 1) and φ′′(z) = ez/(1 + ez)2 = 1/(e−z + 2 + ez) ∈ (0, 0.25) [because e−z + ez ≥ 2]. Since Hn(W) is a positive semi-definite matrix, our loss function in (24) is convex.
Suppose Ŵ is the minimizer to the loss function
Ŵ ∈ arg min W∈ŜK∩B(R) Ln(W),
where ŜK = { ∑K k=1 Bk ⊗Ak : Ak ∈ Rl1×l2×···×lN and Bk ∈ Rp1×p2×···×pN }, and B(R) is a Frobenius ball of some fixed radius R centered at the underlying true parameter.
Similar to Fan et al. (2019), we need to make two additional assumptions to guarantee the locally strong convexity condition. Assumption 4 (Classification). Apart from Assumptions 2-3, we additionally assume that
(C1) {vec(Xi)}ni=1 are i.i.d gaussian vectors with mean zero and variance Σ, where Σ ≤ CxI . (C2) the Hessian matrix at the underlying true parameter W∗ is positive definite and there exists some κ0 > κU > 0, such that H(W ∗) = E(Hn(W∗)) ≥ κ0 · I , where κU = CxCu; (C3) ‖W∗‖F ≥ α √ dM for some constant α, where dM = K(P + L+ 1).
Notice that we can relax (C1) into Assumption 1, but it will require more techincal details. Also, {vec(Xi)}ni=1 can be sub-gaussian random vectors instead of gaussian random vectors. Denote dM = K(P + L+ 1). Theorem 3 (Classification: CNN). Suppose that Assumptions 2&3 and Assumption 4 hold and n & dM. Then, for some δ > 0,
‖Ŵ−W∗‖F ≤ 2 √ κU κ1 (√ dM n + √ δ n ) ,
with probability 1− 4 exp {−0.25cn+ 9dM} − 2 exp {−cγdM − cδ}, where δ = Op(1), c and cγ are some positive constants.
Denote dTUM = ∏N+1 j=1 Rj + ∑N i=1 liRi +RN+1P and d CP M = R N+1 +R( ∑N i=1 li + P ).
Corollary 2 (Classification: Compressed CNN). Let (Ŵ, dM) be (ŴTU, dTUM ) for Tucker decomposition, or (ŴCP, dCPM ) for CP decomposition. Suppose that Assumptions in Theorem 3 hold and n & cNdM. Then, for some δ > 0,
‖Ŵ−W∗‖F ≤ 2 √ κU κ1 (√ 3cNdM n + √ δ n ) ,
with probability 1− 4 exp {−0.25cn+ 3cNdM} − 2 exp {−cγdM − cδ}, where δ = Op(1), c and cγ are some positive constants, and cN is defined as in Theorem 2.
We consider a binary classification problem as a simple illustration. In fact, the analysis framework can be easily extended to a multiclass classification problem. Here, we consider a M -class classification problem.
Because we need our intermediate output after convolution and pooling to be a vector of length M , instead of a scalar, we need to introduce one additional dimension to the fully-connected weight tensor. Hence, we introduce another subscript m to represent the class label. And the set of fullyconnected weights is represented as {Bk,m}1≤k≤K,1≤m≤M where each Bk,m is of size p1 × p2 × · · · × pN . Then, for each input tensor X, our intermediate output is a vector of size M , where the mth entry is represented by outputm = 〈Z,Wm〉, where Wm = ∑K k=1(Bk,m ⊗Ak) is an N -th order tensor of size l1p1 × l2p2 × · · · × lNpN .
For aM -class classification problem, we have the vector label output y ∈ (0, 1)M . Essentially, each entry of y comes from a different binary classification problem, with M problems in total. We can model it as
p(ym|Z) = (
1
1 + exp(〈Z,Wm〉) )1−ym ( exp(〈Z,Wm〉) 1 + exp(〈Z,Wm〉) )ym = exp {ym〈Z,Wm〉 − log [1 + exp(〈Z,Wm〉)]}
If we stack {Wm}Mm=1 into a tensor Wstack, which is an N + 1-order tensor of size l1p1 × l2p2 × · · · × lNpN ×M . And we further introduce some natural basis vectors {em ∈ RM}Mm=1. It can be shown that
〈Zi,Wm〉 = 〈Zi ◦ em︸ ︷︷ ︸ Zim ,Wstack〉,
where ◦ is the outer product.
We can then recast this model into one with nM samples {Zim, yim : 1 ≤ k ≤ K, 1 ≤ m ≤ M}. The corresponding loss function is
Ln(Wstack) = − 1
nM M∑ m=1 n∑ i=1 yi〈Zim,Wstack〉+ 1 nM M∑ m=1 n∑ i=1 φ(〈Zim,Wstack〉).
We can now use the techniques in Theorem 3 to show the following corollaries for multiclass classification problem.
Denote dMCM = K(MP + L+ 1).
Corollary 3 (Multiclass Classification: CNN). Under similar assumptions as in Theorem 3, suppose that n & dMCM . Then, for some δ > 0,
‖Ŵstack −W∗stack‖F ≤ 2 √ κU κ1 (√ dMCM n + √ δ n ) ,
with probability 1− 4 exp { −0.25cn+ 9dMCM } − 2 exp { −cγdMCM − cδ } , where δ = Op(1), c and cγ are some positive constants. Denote dMC−TUM = ∏N+1 j=1 Rj + ∑N i=1 liRi + RN+1PM and d MC−CP M = R N+1 + R( ∑N i=1 li + PM).
Corollary 4 (Multiclass Classification: Compressed CNN). Let (Ŵstack, dMCM ) be (Ŵstack,TU, d MC−TU M ) for Tucker decomposition, or (Ŵstack,CP, d MC−CP M ) for CP decomposition. Suppose that Assumptions in Theorem 3 hold and n & cNdmultiM . Then, for some δ > 0,
‖Ŵstack −W∗stack‖F ≤ 2 √ κU κ1
(√ 3cNdMCM
n +
√ δ
n
) ,
with probability 1 − 4 exp { −0.25cn+ 3cNdMCM } − 2 exp { −cγdMCM − cδ } , where δ = Op(1), c and cγ are some positive constants, and cN is defined as in Theorem 2. Proof of Theorem 3. Denote the sets ŜK = { ∑K k=1 Bk ⊗ Ak : Ak ∈ Rl1×l2×···×lN and Bk ∈ Rp1×p2×···×pN } and SK = {W ∈ ŜK : ‖W‖F = 1}. We further denote ∆ = vec(W −W∗), where W∗ is the underlying true parameter and W,W∗ ∈ ŜK , and define the first-order Taylor error
En(∆) = Ln(W)− Ln(W∗)− 〈∇Ln(W∗),∆〉 .
Suppose Ŵ is the minimizer for the loss function, i.e.,
Ŵ = arg min W∈ŜK
Ln(W).
Denote ∆̂ = vec(Ŵ−W∗). We then have
Ln(Ŵ)− Ln(W∗) ≤ 0, which can be rearranged into En(∆̂) ≤ − 〈 ∇Ln(W∗), ∆̂ 〉 .
Then, for some W̃ between Ŵ and W∗,
1 2 ∆̂′Hn(W̃)∆̂ ≤ ∣∣∣〈∇Ln(W∗), ∆̂〉∣∣∣ , which leads to
‖∆̂‖2F sup ∆∈S2K ∆′Hn(W̃)∆ ≤ 2‖∆̂‖F sup ∆∈S2K |〈∇Ln(W∗),∆〉| . (27)
From Lemma 4 and Lemma 5, when n & dM, we obtain that, for some δ > 0,
‖Ŵ−W∗‖F ≤ 2 √ κU κ1 (√ dM n + √ δ n ) ,
with probability 1− 4 exp {−0.25cn+ 9dM} − 2 exp {−cγdM − cδ}.
Now we proof several lemmas to be used in Theorem 3. For simplicity of notation, denote xi = vec(Xi) and zi = vec(Zi). It holds that zi = UGxi, for 1 ≤ i ≤ n. Lemma 4 (Deviation bound). Under Assumption 4(C3), suppose that n & dM, then, for some δ > 0,
P { sup
∆∈S2K |〈∇Ln(W∗),∆〉| ≥ 0.5
√ κU (√ dM n + √ δ n )} ≤ 2 exp {−cγdM} ,
where δ = Op(1), dM = K(P + L+ 1), κU = CxCu and cγ is some positive constant.
Proof. Let ηi = 〈Zi,W∗〉, and from (25),
〈∇Ln(W∗),∆〉 = 1
n n∑ i=1 [φ′(ηi)− yi]〈zi,∆〉,
and we can observe that E{[φ′(ηi)− yi]〈zi,∆〉} = E{E[φ′(ηi)− y|z]〈zi,∆〉} = 0 = E[φ′(ηi)− yi]E[〈zi,∆〉]. It implies (i) E〈∇Ln(W∗),∆〉 = 0, (ii) the independence between φ′(ηi) − yi and 〈zi,∆〉. And from Lemma 6, the independence leads to ‖[φ′(ηi)−yi]〈zi,∆〉‖ψ1 ≤ ‖φ′(ηi)−yi‖ψ2‖〈zi,∆〉‖ψ2 . Denote κU = CxCu. For any fixed ∆ such that ‖∆‖2 = 1,
‖〈zi,∆〉‖ψ2 = ‖〈wi,Σ1/2UG∆〉‖ψ2 ≤ √ κU .
This, together with ‖φ′(ηi)− yi‖ψ2 ≤ 0.25 in Lemma 7, gives us ‖[φ′(ηi)− yi]〈zi,∆〉‖ψ1 ≤ 0.25 √ κU .
Then, we can use the Beinstein-type inequality, namely Corollary 5.17 in (Vershynin, 2010) to derive that, for any fixed ∆ with unit l2-norm,
P {|〈∇Ln(W∗),∆〉| ≥ t} = P
{ 1
n ∣∣∣∣∣ n∑ i=1 [φ′(ηi)− yi]〈zi,∆〉 ∣∣∣∣∣ ≥ t }
≤ 2 exp { −cnmin ( 4t √ κU , 16t2 κU )} .
(28)
Consider a ε-net S̄2K , with the cardinality of N (2K, ε), for the set S2K . For any ∆ ∈ S2K , there exists a ∆̄j ∈ S̄2K such that ‖∆ − ∆̄j‖F ≤ ε. Note that ∆ − ∆̄j ∈ Ŝ4K and, from Lemma 1(a), we can further find ∆1,∆2 ∈ Ŝ2K such that 〈∆1,∆2〉 = 0 and ∆ − ∆̄j = ∆1 + ∆2. It then holds that ‖∆1‖F + ‖∆2‖F ≤ √ 2‖∆− ∆̄j‖F ≤ √ 2ε since ‖∆− ∆̄j‖2F = ‖∆1‖2F + ‖∆2‖2F. As a result, |〈∇Ln(W∗),∆〉| =
∣∣〈∇Ln(W∗), ∆̄j〉∣∣+ |〈∇Ln(W∗),∆1〉|+ |〈∇Ln(W∗),∆2〉| ≤ max
1≤j≤N (2K,ε) ∣∣〈∇Ln(W∗), ∆̄j〉∣∣+√2ε sup ∆∈S2K |〈∇Ln(W∗),∆〉| ,
which leads to sup
∆∈S2K |〈∇Ln(W∗),∆〉| ≤ (1−
√ 2ε)−1 max
1≤j≤N (2K,ε) ∣∣〈∇Ln(W∗), ∆̄j〉∣∣ . Note that, from Lemma 1(b), logN (2K, ε) ≤ 2dM log(9/ε), where dM = K(P + L + 1). Let ε = (2 √ 2)−1 and then 2 log(9/ε) < 7. With (28), we can show that
P {
sup ∆∈S2K
|〈∇Ln(W∗),∆〉| ≥ 2t } ≤ 2 exp { −cnmin ( 4t √ κU , 16t2 κU ) + 7dM } .
Take t = 0.25 √ κU ( √ dM/n + √ δ/n) where δ = Op(1), and there exists some γ such that√
dM/n ≤ γ holds. We can finally show that
P { sup
∆∈S2K |〈∇Ln(W∗),∆〉| ≥ 0.5
√ κU (√ dM n + √ δ n )} ≤ 2 exp {−cγdM − cδ} ,
where cγ is some positive constant related to γ.
Lemma 5 (LRSC). Suppose that n & dM, under Assumptions 4, there exists some constant R > 0, such that for any W ∈ Ŝ2K satisfying ‖W−W∗‖F ≤ R,
inf ∆∈S2K ∆′Hn(W)∆ ≥ κ̃1 2
holds with probability 1− 4 exp {−0.25cn+ 9dM} , where κ̃1 = κ1 − κU . And κ1 is defined in Lemma 8.
Proof. We divide this proof into two parts.
1. RSC of Ln(W) at W = W∗. We first show that, for all ∆ ∈ S2K , the following holds with probability at least 1 − 2 exp { −0.25c(κL/κU )2n+ 9dM } ,
∆′Hn(W ∗)∆ ≥ κ̃,
where κ̃ = κ0 − κL > 0. Let ηi = 〈Zi,W∗〉 and denote z̃i = √ φ′′(ηi)zi and we can see that
Hn(W ∗) =
1
n n∑ i=1 z̃iz̃i′ and, H(W∗) = EHn(W∗).
Denote xi = vec(Xi). Here, for simplicity, we assume {xi}ni=1 to be independent gaussian vectors with mean zero and covariance matrix Σ, where cxI ≤ Σ ≤ CxI for some 0 < cx < Cx. We will also use the notation of ∆ for its vectorized version, vec(∆), and we consider ∆ with unit l2-norm.
Since ‖〈∆, z̃i〉‖ψ2 = ‖〈∆, √ φ′′(ηi)U ′GΣ 1/2wi〉‖ψ2 ≤ 0.25 √ κU , where wi is a standard gaussian vector and κU = CxCu, we can show that
‖〈∆, z̃i〉2 − E [ 〈∆, z̃〉2 ] ‖ψ1 ≤ 2‖〈∆, z̃i〉2‖ψ1 ≤ 4‖〈∆, z̃i〉‖2ψ2 ≤ κU ,
where the first inequality comes from Remark 5.18 in (Vershynin, 2010) and second inequality comes from Lemma 5.14 in (Vershynin, 2010).
And hence, by the Beinstein-type inequality in Corollary 5.17 in (Vershynin, 2010), for any fixed ∆ such that ‖∆‖2 = 1, we have
P {|∆′(Hn(W∗)−H(W∗))∆| ≥ t} = P
{ 1
n ∣∣∣∣∣ n∑ i=1 { 〈∆, z̃i〉2 − E [ 〈∆, z̃〉2 ]}∣∣∣∣∣ ≥ t }
≤ 2 exp { −cnmin ( t
κU , t2 κ2U
)} .
With similar covering number argument as presented in Lemma 2 in our paper, we can show that, P {
sup ∆∈S2K
|∆′(Hn(W∗)−H(W∗))∆| ≥ 2t } ≤ 2 exp { −cnmin ( t
κU , t2 κ2U
) + 9dM } ,
where dM = K(P + L+ 1).
Llet t = 0.5κU . By Assumption 4(C1), we can obtain that, when n & dM, P {
inf ∆∈S2K
∆′Hn(W ∗)∆ ≤ κ̃ } ≤ 2 exp {−0.25cn+ 9dM} ,
where κ̃ = κ0 − κU > 0. 2. LRSC of Ln(W) around W∗.
Define the event A = {|〈W∗,Zi〉| > τ sup∆∈S2K |〈∆, z i〉|} and construct the functions
hn(W) = 1
n n∑ i=1 φ′′(〈Zi,W〉)IAzizi′ and, h(W) = Ehn(W),
where τ is some positive constant to be selected according to Lemma 8. Since the difference between hn(·) and Hn(·) is the indicator function, it holds that Hn(·) ≥ hn(·). We will finish the proof of LRSC in two steps. Firstly, we show that, with high probability, hn(W
∗) is positive definite on the restricted set S2K . Secondly, we bound the difference between ∆′hn(W)∆ and ∆′hn(W
∗)∆, and hence show that hn(W) is locally positive definite around W∗. This naturally leads to the LRSC of Ln(W) around W∗. From Lemma 8, we can select τ , such that h(W∗) ≥ κ1I . Following similar arguments as in the first part, we can show that for all ∆ ∈ S2K , the following holds with probability at least 1− 2 exp {−0.25cn+ 9dM},
∆′hn(W ∗)∆ ≥ κ̃1, (29)
where κ̃1 = κ1 − κU > 0.
In the meanwhile, for any W ∈ ŜK such that ‖W−W∗‖F ≤ R, where R can be specified later to satisfy some conditions,
|hn(W)− hn(W∗)| = ∣∣∣∣∣ 1n n∑ i=1 φ′′(〈Zi,W〉)IAzizi′ − 1 n n∑ i=1 φ′′(〈Zi,W∗〉)IAzizi′ ∣∣∣∣∣
≤ 1 n n∑ i=1 ∣∣∣φ′′(〈Zi,W〉)− φ′′(〈Zi,W∗〉)∣∣∣ IAzizi′ = 1
n n∑ i=1 ∣∣∣φ′′′(〈Zi,W̄〉)〈Zi,W−W∗〉∣∣∣ IAzizi′, where W̄ lies between W and W∗, and φ′′′(z) = ez(1 − ez)/(1 + ez)3. Given the event A holds, choose R < τ , we can lower bound the term,
|〈Zi,W̄〉| ≥ |〈Zi,W∗〉| − sup ∆∈Ŝ2K ,‖∆‖F≤R |〈Zi,∆〉| ≤ (τ −R) sup ∆∈S2K |〈Zi,∆〉|.
Notice that, for all z ∈ R, the third order derivative of the function φ(z) is upper bounded as |φ′′′(z)| ≤ 1/|z|. This relationship helps us further bound the term,∣∣∣φ′′′(〈Zi,W̄〉)〈Zi,W−W∗〉∣∣∣ ≤ |〈Zi,W−W∗〉|
|〈Zi,W̄〉| ≤
sup∆∈Ŝ2K ,‖∆‖F≤R |〈Z i,∆〉| (τ −R) sup∆∈S2K |〈Z i,∆〉|
≤ R sup∆∈S2K |〈Z i,∆〉| (τ −R) sup∆∈S2K |〈Z i,∆〉| = R τ −R .
Hence, we can show that P {
sup ∆∈S2K
|∆′[hn(W)− hn(W∗)]∆| ≥ t } ≤ P { R
τ −R sup
∆∈S2K
1
n n∑ i=1 ∆′zizi′∆ ≥ t
} .
By setting t = αRSMR/(τ − R), where αRSM = 3κU/2, we can use the equation (16) in Lemma 2 to obtain, as long as n & dM,
P {
sup ∆∈S2K
|∆′[hn(W)− hn(W∗)]∆| ≥ αRSMR
τ −R
} ≤ 2 exp {−cHn+ 9dM} .
By rearranging terms, this is equivalent to
P  inf∆∈S2K ∆ ′hn(W)∆ ≤ sup ∆∈S2K ∆′hn(W ∗)∆− αRSMR τ −R︸ ︷︷ ︸
denoted as the eventB1  ≤ 2 exp {−cHn+ 9dM} . If we define the event B2 = {inf∆∈S2K ∆′hn(W
∗)∆ ≤ κ̃1} and denote its complementary event by Bc2, and from (29), we know that P(B2) ≤ 2 exp {−0.25cn+ 9dM}. It can be seen that
P ({
inf ∆∈S2K
∆′hn(W)∆ ≤ κ̃1 − αRSMR
τ −R
} ∩Bc2 ) ≤ P(B1 ∩Bc2) ≤ P(B1)
So, if we choose R to be sufficiently small, such that αRSMR/(τ −R) ≤ κ̃1/2, it holds that, P {
inf ∆∈S2K ∆′hn(W)∆ ≤ κ̃1 2
} ≤ P ({ inf
∆∈S2K ∆′hn(W)∆ ≤ κ̃1 −
αRSMR τ −R
} ∩Bc2 ) + P(B2).
This, together with Hn(·) ≥ hn(·), leads us to conclude that, when n & dM, there exists some R > 0, such that for any W ∈ Ŝ2K satisfying ‖W−W∗‖F ≤ R,
inf ∆∈S2K ∆′Hn(W)∆ ≥ κ̃1 2 ,
holds with probability
1− 2 exp {−0.25cHn+ 9dM} − 2 exp {−0.25cn+ 9dM} .
We accomplished our proof of the LRSC of Ln(W) around W∗.
Lemma 6. For two sub-gaussian random variables, X and Y , when E(XY ) = EXEY , i.e. X is independent to Y , it holds that ‖XY ‖ψ1 ≤ ‖X‖ψ2‖Y ‖ψ2 . Lemma 7.
‖φ′(ηi)− yi‖ψ2 ≤ 0.25.
Proof. Firstly, we observe that E ( exp{λ [ φ′(ηi)− yi ] }|zi ) = exp{λφ′(ηi)} exp{−φ(ηi)}+ {λ [ φ′(ηi)− 1 ] } exp{ηi − φ(ηi)}
= exp{λφ′(ηi)− φ(ηi)}[1 + exp{ηi − λ}] = exp{φ(ηi − λ)− φ(ηi) + λφ′(ηi)} = exp{0.5λ2φ′′(η∗)} ≤ exp{0.125λ2}.
It then holds that E ( exp{λ [ φ′(ηi)− yi ] } ) = E{E ( exp{λ [ φ′(ηi)− yi ] }|zi ) } ≤ exp{0.125λ2}, and this implies that ‖φ′(ηi)− yi‖ψ2 ≤ 0.25.
Lemma 8. Under Assumption 4, there exists a universal constant τ > 0 such that h(W∗) ≥ κ1I , where κ1 is a positive constant.
Proof. We first show that for any p0 ∈ (0, 1), there exists a constant τ such that
P(|〈W∗,Zi〉| > τ sup ∆∈S2K |〈∆, zi〉|) ≥ p0.
We would separately show that
P(|〈W∗,Zi〉| > c1 √ dM︸ ︷︷ ︸
denoted by eventD1
) ≥ p0 + 1 2 and, P( sup ∆∈S2K |〈∆, zi〉| ≤ c2 √ dM︸ ︷︷ ︸
denoted by eventD2
) ≥ p0 + 1 2 ,
for some positive constants c1 and c2. Using the relationship P(D1 ∩ D2) = P (D1) + P (D2) − P (Dc1 ∪Dc2) ≥ P (D1) + P (D2)− 1, it follows naturally that
P(|〈W∗,Zi〉| > τ sup ∆∈S2K |〈∆, zi〉|) ≥ p0 + 1 2 + p0 + 1 2 − 1 = p0, (30)
where τ = c1/c2.
Since xi is a gaussian vector with mean zero and covariance Σ, zi = U ′Gx i is a zero-mean gaussian vector with covariance given by U ′GΣUG, and 〈W ∗,Zi〉 = 〈vec(W∗), zi〉 also follows a normal distribution with mean zero and variance (also its sub-Gaussian norm) upper bounded by κU‖W∗‖2F, where κU = CxCu.
Since from Assumption 4(C2), ‖W∗‖2F ≥ α √ dM, we can take c1 to be sufficiently small such that
P(D1) = P ( |〈W∗,Zi〉| κU‖W∗‖F > c1 κUα ) ≥ P(|x| > c1 κUα ) ≥ p0 + 1 2 ,
where x is a gaussian variable with variance upper bounded by 1.
Then, we can also observe that, for any fixed ∆ ∈ S2K , 〈∆, zi〉 is a gaussian variable with zero mean and variance upper bounded by κU . We can use the concentration inequality for gaussian random variable to establish that
P ( |〈∆, zi〉| ≥ t ) ≤ 2 exp(− t 2
κU ),
for all t ∈ R. We can further use the union bound to show that P (
sup ∆∈S2K
|〈∆, zi〉| ≥ t ) ≤ 2 exp(− t 2
κU + 7dM).
Let t = c2 √ dM for some positive constant c2 > √ 7κU . We can choose c2 large enough such that
P (
sup ∆∈S2K
|〈∆, zi〉| ≥ c2 √ dM ) ≤ 1− p0
2 .
The probability at (30) is hence shown.
Now, we will take a look at the matrix h(W∗) and show that it is positive definite. Same as in Lemma 5, we denote the event A = {|〈W∗,Zi〉| > τ sup∆∈S2K |〈∆, z
i〉|}, and its complement by Ac, then
∆′h(W∗)∆ = 1
n E { n∑ i=1 φ′′(〈Zi,W〉)IA∆′zizi′∆ }
= 1
n E { n∑ i=1 φ′′(〈Zi,W〉)∆′zizi′∆ } − 1 n E { n∑ i=1 φ′′(〈Zi,W〉)IAc∆′zizi′∆ }
= ∆′H(W∗)∆− 1 n E { n∑ i=1 φ′′(〈Zi,W〉)IAc∆′zizi′∆ }
(i) ≥ κ0 − 1
n √√√√E{ n∑ i=1 [φ′′(〈Zi,W〉)]2〈∆, zi〉4 }√√√√E{ n∑ i=1 IAc }
(ii) ≥ κ0 − √ 3κU 4 (1− p0),
where (i) follows from Assumption 4(C1), And since 〈∆, zi〉 is a gaussian variable with mean zero and variance bounded by κU , its fourth moment is bounded by 3κU . Also, by φ′′(z) ∈ (0, 0.25) for all z ∈ R, (ii) can be shown. Here, we can take p0 to be small enough such that 0.25 √ 3κU (1−p0) ≤ 0.5κ0 holds. It follows that
∆′h(W∗)∆ ≥ κ1,
with κ1 = 0.5κ0. We hence accomplished the proof of the lemma.

heading: A.5 ADDITIONAL EXPERIMENTS

heading: A.5.1 MORE EXPERIMENTS FOR THEORETICAL RESULTS
text: We first provide some additional implementation details for Section 4.1 in the paper. We consider two types of inputs for verification of the sample complexity in Theorem 1. For the time-dependent inputs, we generate a sequence of vectors {xi} with size Rd from a stationary VAR(1) process, where d = 245 or 192. The VAR(1) process has a transition matrix with spectral norm less than
1 to ensure stationarity, and a white noise sequence which follows multivariate standard normal distribution. The first 50 simulated data points in the sequence are discarded to alleviate the influence of initialization, and the length of the resulting sequence is equal to the training sample size plus the testing sample size, i.e. n+ 200. We then reshape {xi} into a sequence of tensors of shape (7, 5, 7) or (8, 8, 3), which are the time-dependent inputs for experiments under S1/S2 or S3/S4.
Next, we conduct extra experiments for efficient number of kernels for a CP block design. This study uses 32× 32 inputs with 16 channels, and we set stride to 1 and pooling sizes to (5, 5). We generate the orthonormal factor matrices {H(j), 1 ≤ j ≤ 4}, where H(1) is of size R8×R, H(2) is of size R8×R, H(3) is of size R16×R and H(4) is of size RK×R where R = 8 and K ∈ {8, 16, 24, 32}. If we denote the orthonormal column vectors of H(j) by h(j)r where 1 ≤ r ≤ R and 1 ≤ j ≤ 4, the stacked kernel tensor A can then be generated as A = ∑R r=1 h (1) r ◦ h(2)r ◦ h(3)r ◦ h(4)r . And it can be seen that A has a CP rank of R = 8. We split the stacked kernel tensor A along the kernel dimension to obtain {Ak, 1 ≤ k ≤ K} and generate the corresponding fully-connected weight tensors {Bk, 1 ≤ k ≤ K} with standard normal entries. The parameter tensor W is hence obtained, and we further normalize it to have unit Frobenius norm to ensure the comparability of estimation errors between different Ks. The block structure in Figure 7(1) is employed to train the network, and it is equivalent to the bottleneck structure with a CP decomposition on A; see Kossaifi et al. (2020b). We can see that as K increases, there is more redundancy in the network parameters. Fifty training sets are generated for each training size, and we stop training when the target function drops by less than 10−5. From Figure 7(2), the estimation error increases asK is larger, and the difference is more pronounced when training size is small.

heading: A.5.2 ABLATION STUDIES ON MORE BLOCK DESIGNS
text: In this section, we present the results from the studies of K/R ratios on two popular networks structures, namely, ResNeXt (Xie et al., 2017) and Shufflenet v2 (Ma et al., 2018). To start with, we will show the bottleneck block structure and its respective K/R ratio in ResNeXt and Shufflenet.
In Figure 8, we represent the bottleneck block structure of ResNeXt consisting of 3 layers: a 1 × 1 convolution layer, a 3 × 3 group convolution layer followed by another 1 × 1 convolution layer. During group convolution phase, there are g parallel paths, each has a bottleneck size of r, which
is also the rank of the output channel in each individual path; see also Figure 1 in Xie et al. (2017). Since the output from each path is aggregated via summation, the rank of the output channel of the entire bottleneck block is equal to R = r · g. Subsequently, we can define the expansion ratio of this block to be t = K/R.
In Figure 9, we represent the bottleneck block structure of Shufflenet. It consists of 3 layers: a 1× 1 convolution layer, a 3× 3 depthwise convolution layer followed by another 1× 1 convolution layer. So, the only difference between this block structure and that in ResNet (He et al., 2016) is that the full 3×3 convolution is replaced by the depthwise separable convolution. It follows that the expansion ratio is t = K/R.
We conducted the experiments on the SVNH dataset and take t = 1, 2, 4, since t = 2 or t = 4 in particular, is commonly used in practice. We followed the design of ResNeXt-50 (see Table 1 in Xie et al. (2017)) and Shufflenet v2-50 (see Appendix Table 2 in Ma et al. (2018)), only be removing the three convolution block in ”conv5” to avoid overfitting. And we set R = 24, 58, 116, 232 as the bottleneck rank for ”conv1”-”conv4”, respectively. And K = t · R is taken according to different values of t. The implementations are similar to before. Following the practice in He et al. (2016), we adopt batch normalization(BN) (Ioffe & Szegedy, 2015) right after each convolution and before the ReLU activation. For ResNeXt, the cardinality of the group convolution is set to be 32, and we initialize the weights as in He et al. (2015). We use stochastic gradient descent with weight decay 10−4, momentum 0.9 and mini-batch size 128. The learning rate starts from 0.1 and is divided by 10 for every 100 epochs. We stop training after 350 epochs, since the training accuracy hardly changes. The training accuracy is approximately 96%. We set seeds 1-5 and report the worst case scenario of the test accuracy in Table 3.
We can see that, when t = 1, the test accuracy is comparable to when t = 2 or 4, and the number of parameters are reduced by a lot. In fact, the ratio of number of parameters at a single bottleneck block for t = 1, 2 and 4 is roughly 1 : 2 : 4, for both networks. This implies that the number of parameters will increase dramatically when we have a deeper CNN, for instance, ResNeXt-101. Hence, it is always recommended to keep t = 1 to achieve more parameter efficiency without sacrificing the test accuracy.

Review summaries:
This paper formulated higher-order CNNs into a Tucker form and provides sample complexity analysis to higher-order CNNs and compressed designs of CNNs via tensor analysis. It uses then theoretically analyzes the efficiency of four block designs from ResNet, MobileNetV1, and MobileNetV2. The paper also conducts numerical experiments to verify its theoretical results and provide some empirical studies to show that increasing the expansive ratio of a bottleneck

This paper provides theoretical analysis of the estimating power of CNN (3 and 5 layers). By formulating the problem using tensors, the authors showed that the estimating error of the learned CNN weights with respect to the true weights is of the order $\sqrt{d/n}$ where $d$ measures model complexity and $n$ is the training sample size. In addition, the authors considered low rank approximation to the convolution tensor through CP and Tucker decompositions, and they derived convergence result for the CNN weights in this case. The authors then applied these results to analyze different block designs through numerical experiments and ablation studies.