Rethinking Compressed Convolution Neural Network from a Statistical Perspective
Authors: Feiqing Huang
Yuefeng Si
Guodong Li
Venue:  (2021)
Keywords: Compressed Convolutional Neural Network
Tensor Decomposition
Sample Complexity Analysis

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.

Under review as a conference paper at ICLR 2021
RETHINKING COMPRESSED CONVOLUTIONAL NEU- RAL NETWORKS FROM A STATISTICAL PERSPECTIVE
Anonymous authors Paper under double-blind review
ABSTRACT
Many designs have recently been proposed to improve the model efficiency of convolutional neural networks (CNNs) at fixed resource budget, while there is 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 litera- the output channels, which
ture. The low rank assumption is usually imposed according to our study, may not beneficial to obtain computationally effi- cient model while similar accuracy can be maintained. Our finding is further supported by ablation studies on CIFAR1O, SVNH and UCF101 datasets.
INTRODUCTION
The introduction of AlexNet (Krizhevsky al., 2012) spurred line of research in 2D CNNs, which progressively achieve high levels of accuracy in the domain of image recognition (Simonyan & Zisserman 2015; Szegedy al., 2015 He et al. 2016 Huang et al., 2017). The current state- of-the-art CNNs leave little room to achieve significant improvement on accuracy in learning still- images, and attention has hence been diverted towards two directions. The first is deploy deep CNNs on mobile devices by removing redundancy from the over parametrized network, and some representative models include MobileNetV1 V2 (Howard al., 2017, Sandler 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 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, 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 be approximately recovered with small fraction of parameters. Tensor decomposition recently has been widely used to compress the weights in CNN network (Lebedev al. 2015 Kim et al.) 2016;; Kossaifi et al. 20200b] Hayashi et al., 2019). Specifically, the weights at each layer are first summarized into tensor, and then tensor decomposition, CP 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., (016) corresponds to the convolution kernel with a special Tucker low-rank structure, and the depthwise separable block in MobileNetVI (Howard et al. 2017) and the inverted residual block in MobileNetV2 (Sandler 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 oigher-order tensor inputs.
Tensor decomposition can also be applied to fully-connected layers since they may introduce large number of parameters (Kossaifi al. 2017 2020a); also the discussions in Section 5. Moreover, Kossaifi et al.] (2019) summarized all weights a network into one single high-order tensor, and then directly imposed low-rank structure to achieve full network compression. While the idea is

---

Under review as a conference paper at ICLR 2021
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 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 a. W) + S. where y and are output and input, respectively, W contains all weights and & is an additive error. Given the trained and true underlying networks FONN(Z, W) and (aN W²), the root-mean-square prediction error is defined as
E(W) V Em FCNN (x: W) FENN W²
where W and W are trained and true underlying weights, respectively, and Eg is the expectation on at. The sample complexity analysis is investigate how many samples are needed to guarantee given tolerance on the prediction error. It can also be used to detect the model redundancy. Consider two nested CNNs, where F is more compressed than F2. Given the same true underlying networks, when the prediction errors from trained F1 and F3 are comparable, we then can argue that F3 has redundant weights comparing with F1. As a result, conducting sample complexity analysis 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 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 gen- eral N-dimensional convolution with multiple kernels, followed by an average pooling layer and a fully-comnected 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 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.
1.1 COMPARISON WITH OTHER EXISTING WORKS
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 Li 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 [aanik] 2013). the Rademacher complexity & covering number (Bartlett & Mendelson] 2002). the norm-based capacity control (Neyshabur et al. 2017 Golowich et al. [018]] Bartlett et al.] 2017 Neyshabur al. 2015) and low-rank compression based methods (Li et al. 2020; Zhou & Feng, 2018 Arora et al. 2018). These works use a aagnosicc framework, and hence relies heavily on explicit regularization such as weight decay, dropout data augumentation, well algorithm- based implicit regularization to remove the redundancy in the network.
We, however, attempt to theoretically explain how much compressibility is achieved in compressed network architecture. Specifically. we make a comparison between a CNN and its compressed version, and makes prcoretically-supportt modification to the latter to further increase efficiency.
2

---

Under review as a conference paper at ICLR 2021
Subsequently, analysis requires explicit formulation for the network architecture, which is provided in Section 2, and the prediction error at (T) is adopted as our evaluation criteria. We notice Lh et al. (2020) also proposes 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 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 (hoog et al. 2017b; Fu et al. 2020, Goel et al., [0188] Zhong et al.) (2017a); the development of other provably efficient algorithms (Cao & Gul 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 both target and methodology. We not consider computational complexity algorithm convergence. Instead, we focus the statistical sample complexity to depict the mechanism of compressed block designs for CNNs.
2
FORMULATING CNNS WITH HIGHER-ORDER INPUTS
2.1 NOTATION
Tensor notations. We follow the notations in Kolda Bader (2009) denote vectors by low- ercase boldface letters, e.g. a; matrices by capital boldface letters, e.g. A; tensors of order or higher by Euler script boldface letters, e.g. A. For an -od-order tensor A E I de- note its elements by A(i .2.....in and the n-mode unfolding by A where the columns of A()) are the n-mode vectors of A, for S n S N. And A(: .in.... ... ,:) denotes the subtensor of A, holding only the nh index fixed. The vectorization operation is denoted by vee(-). The inner product of two tensors A, B E IRl1x.-xxxx is defined as (A, B) = E., ......... -iix A(ii..... B())B(i............... iN), and the Frobenius norm is |AAl| = v A), The mode-n multiplication Xn of a tensor A E R/1xx and matrix B E R is defined as N, respec- tively. The mode-n multiplication XN tensor A E RR, xixxxxxxx and a vector b E R is defined = I - The symbol "ø" the Kronecker product and "o" is the outer product. We extend the definition produce of Khatri-Rao product to tensors: given tensors A E R4 xlxx-xxxxx x and B E Rp xpxxxxxx-pppp xK their Khatri-Rao product is a tensor of size R4 lupp denoted by e A B, where
(A xn Bi .iah....--mmm Jn. iN) Σ!n -i.=1 A(i1,..... ..a in....,,ny iN B(jn, in). for 1 S
as (1,..)) ....,,,-11 - fu.1....,,
.n...., in )b(in)) ) for 1 S n I N.
e(: ... .)) = A(:,.. ,k) 2 B(: k), S k K.
2009 factorizes the tensor A E R4 xlxxx into a sum of rank-1 tensors, i.e. A = >y=1 hr, h o ... (N)
CP decomposition. The Canonical Polyadic (CP) decomposition (Kolda & Bader
where h,( is a unit norm vector of size R4 for all 1 S S N. The CP rank the number of rank-1 tensors R.
Tucker decomposition. The Tucker ranks of an -rdder tensor A R'1x xlxxxxlyy are defined as the matrix ranks of the unfoldings of A along all modes. If the Tucker ranks of A are (R,,.., "R,...,,x)) then there exist a core tensor G E R xx and matrices (4) E R4 such that A = X1 (I) X2 H22)... XN H HNN), known as Tucker decomposition (Tucker 1966).
(1)
A
Conv
Pool
Fally-Conneeted
(2)
B
X, E R
X
X p4,d
A X2 0
X2 U (
Xy U
Figure I: (1) 3-layer CNN for 3D input X with one kernel tensor A, average pooling, and fully- connected weights B. (2) U) act as positioning factors. The white spaces indicate zero entries.
3

---

Under review as a conference paper at ICLR 2021
2.2 BASIC THREE-LAYER CNNS
Consider a three-layer CNN with one convolution, one average pooling and one fully-connected layers, and assume linear activations for simplicity. Specifically, for general tensor-structuredd input X E Rd xdxxx"Xxxx we first perform its convolution with an N kernel tensor A IR'1 xlxxx-xxxx to get an intermediate output X E M xm2x and then use average pool- ing with pooling sizes (g1.--. 9N) to derive another intermediate output Kep E R Xp2 XPpN Finally, Xcp goes through a fully-connected layer, with weight tensor B E TR XP2XX"XXX to pro- duce a scalar output; see Fi.
We consider the convolution layer with the stride size of se along each dimension. Assume that my = (d] 1/) + are integers for S j S N, otherwise zero-padding will be needed. Let
( 0
0
I'E VE g4 x for 1 S in S mj. 1 i N,
(2)
(1,-1)8c d, d,-(6,-1)s.-
which act as positioning factors to stretch the kernel tensor A into tensor of the same size as X, while the rest of entries are filled with zeros; see Figure 22). As a result, XC has entries
(e i2,
........,....... ix)
(XC A X1 U X2 U.! X3 ... X )
For the pooling layer with the stride size of Sp along each dimension, we assume the pool- ing sizes {qj ) satisfy the relationship of my = 9, + (pj 1)sp. so the sliding windows can be overlapped. But for case of notation, we can simply take 93 = my/Pj. The average pooling operation is equivalent to forming P1P2P3 ... PN consecutive blocks within X,, each of size R xxy, and then take the average per block. The resulting tensor Xep has entries
Kep (1,, (2,...,in)) iN) (1 E3 1y9:
-(t -)) (k, A.,,.., lN). for S ig S Pj and
1 1s J.JSNII we denote U//, qj Σ
5,
UlO), then equivalently,
ki D0++1
(11 .2,...,, iN) = (X, A x1 USA X2 Fite X3 ... XN Uf/s).
The fully-connected layer performs a weighted summation over Kop, with weights given by entries of the tensor B I2t XxxX Denote UY" - -bA,)) for S j s N, and the predicted output has the form of
ÿ (Xep. B) (X, ( A) u U X3. XN M
(1)
Similarly, for a CNN with K kernels, denote (As, B k connected weights, where Ba xPixxixx-XXP and A Rh xxxxxxxxxxx The model can then be explicitly represented by
to be the set of kernels and fully-
y D' + = (x, Wx) + 1sisn,
(3)
where ç the additive error,
X' E Rdixd2x xdN and the composite weight tensor
K By A x1 U8 X2 f X3 ... X (N)
Wx
(4)
1=1
The innate weight-sharing compactness of CNN can be equivalently represented as a "Tucker-like" form at (4). The factor matrices (ū E Rd N are fixed and solely determined by CNN operations on the inputs. They have full column ranks given that p,lE S d, always holds. The core tensor is a special Kronecker product that depicts the layer-wise interaction between weights.
lz=1
2.3 SAMPLE COMPLEXITY ANALYSIS
We can now derive the non-asymptotic error bound for the CNN model. Let 2 Xt x Uf! X2 (2)) Xg... XN UNY Rli xlapı xlyNN Model (3) is equivalent
K
y = (z3, W) + Σ
2 B 8 A +5"
(5)
A=
4

---

Under review as a conference paper at ICLR 2021
where W = Σx= Bx @ Ag. The trained weights have the form of W Ex= BB @ Ak, where
{Bk ARhiskk arg min
min As ni
BB Ar)
(6)
Denote x² = veo(X() and z' vec(Z"), and it can be verified that 2' Uga', where UG UP @ (Uu @ ( 8... @ (U @ +f }} represents the CNN operations on the inputs. Let = (x , "...,,"y,, and we make the following technical assumptions.
Assumption 1. (fime-dependent inputs) ā is normally distributed with mean zero and variance Σ B (i'), where C₂ S Σ S C,I for some O < Co < Ca.
Denote by (A) and Amia( (A) the maximum and minimum eigenvalues of a symmetric matrix A, respectively. When {x*) a stationary time series with spectral density function (0), we can take C. inf = Amin (f (0)) and C₂ = sup x SSS= (fx (fx( see Basu & Michailidis Exn is block diagonal, and it holds that
2015). For independent inputs, E = Gy min Amin 553) and C₂ = maxisisn Amax (Ez}), where Σj = R(xx==")
Assumption 2. (Sub-Gaussian errors) {5t) are independent ---sub-Gausiin random variables with mean zero, and is independent of (X), 1 S j i} for all 1 1 S
Assumption 3. (Restricted isometry property) cal S KUGUG S Cul some 0 < Cu < C..
Denote Ky = Cr and KL CaCu. Let W = Σk B @ A be the true weight. The model complexity of CNN at (5) Theorem (CNN), Suppose that Assumptions 1-3 hold and n Z (NU/ [()) d Then,
is dm K(P + L 1), where P = piP2 ... PN and L= 1112...4. ....
160 /RRMM
(Vam
dd
6 +V
JW - W- <
+
and, 8(W) S /NE M - W
a'sc
with probability 1- expp exx((-(ccc (0.25kL/ ) 9d expl-dw dd 863, where Op(1),
Cn is positive value, oRsc = k1,/2, and OnSM 3KU
It can be seen that the prediction error & E(W), is Op(Vdm/nn) and hence the sample complexity is of order Oddm/=²), to achieve prediction error Technical proofs of all theorems and corollary in the paper are deferred to Appendix AA.3
Note that, for simplicity, 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..
assume simple regression model at The theoretical analysis
2.4 CNNs WITH MORE LAYERS
Consider a 5-layer CNN with "convolution - pooling - convolution - pooling - fully con- nected" 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 Ā [ xlxxxxx-xxxx and the fully-connected weight tensor B is of size RPP xxxxx..xxxx. x..xxxxxxx xpv_ We similarly define matrices (() and Fay"" which are both of
size xI, with < in S pJ and 1 < < N, and can be used to represent the second convolution and pooling operations, respectively. Note that the output from the first pooling layer, Xep. is the input to the second convolution layer, and hence the output from the second pooling layer has entries
( (ip ii,.i....... iy..... = (Xop Ā X1 Fd
( X2 Fit2 X3 ... XN 0
Stack the matrices (66) E Ed xl, hishs and {0 E x Jisiysh, into 3D tensors ( Fij
Rdd xlyx;; and ()) E RR xi, xi, respectively. Let D (1 X3 U (n for 1 S < N and,
by some algebra Appendix A.2
we can show that the predicted output has the form of
1 ( B) (X, (B A 80 A) ( x2 U Xg... XN U (N),
5

---

Under review as a conference paper at ICLR 2021
where (( x3U yields a tensor of size R4, x7, with Σ U k2 .) (i. Kz, ka) as its (k1, f2, ,3, k4 )4 entry. The case with multiple kernels will have a form similar to Following the same logie, it can indeed be generalized to an even deeper CNN by adding more "convolution- pooling" layers. Since the composite weight tensor always has a "Tucker-like" form, techniques in proving Theorem
( ())
D 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 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 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.
3 COMPRESSED CNNS
For a high-order input, a deep CNN with 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 al. (2015):
Kim et al. (2016); Astrid & Lee (0017): Kossaifi et al. (2020b).
Tucker decomposition
be used to compress CNNs, which same introducing multilayer CNN block; see Figure 3 in Kim et al. (2016). Specifically, we stack the kernels Ag E TR. xl2x-xxxx with 1 S k S K into higher order tensor Astack E [R xxxxxxxxxxxxx and assume that Astack has Tucker ranks of (R1, R2. ... RN, RN+1). As a result,
(8) Rx+1 is the core tensor, and HU) R are factor matrices for 1 < j I 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 have the
Astack 9 x (2) X2 (2) XN+1 (N++),
where E R.
TU TU
form of (8) Denote the estimators by {B, A hIASSK. The trained weights then have form of
W TU = Σk BB
A
TU
and the model complexity is dM = -I Ry+ 4R,+ RN+1P.
k=1
CP decomposition is more popular in compressing CNNs; see Kossaiñ et al. (0200b; Lebedev CP -CP.
al.
2015); Astrid & Lee (2117). Let {Br A hISAsK be the least-square estimators (6)
with Astack having CP decomposition with a rank of R. Then, the trained weights are Wer CP
CC
B
2 A and the model complexity is det RNN+1 + + 4
Theorem 2 (Compressed CNN). Let (W,dM) be (WTu, d for Tucker decomposition, or
(Wer, d for CP decomposition. Suppose that Assumptions 1-3 hold and n Z (KU CNdM. Then,
160 /ORSM
CNdM n
5 + V
IW - 1W-WWI IP S
and, E(W) S V /RU W - -'
@RSC
with probability 1- cx (O..(O..5...) / cN 2 log(NN + 2), Cи is positive value and arsc, ØRSM defined in Theorem 1
3cnd expl 86}, where ö Op()),
Theorem 2 shows that, as expected, the sample complexity is proportional to the model complexity. Compared to Theorem [ we see that the sample complexity of the compressed CNN depends on EN14 instead of IT 1, When the input dimension N is large, compressed CNN can indeed reduce large number of parameters.
However, notice that the sample complexity of compressed CNN depends 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.

---

Under review as a conference paper at ICLR 2021
Corollary 1. (a) If A has Tucker decomposition with the ranks of (R1, R2,.... -N++1), the CNN equivalent to one with RN+1 kemels, and each kernel A,, where T RN+1, has a Tucker decomposition with ranks of (R1, R2," ...................... R.x) 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 S R, has CP decomposition form with rank R.
Define the K/ ratio to be the value of K/RN+1 for Tucker decomposition K/R for CP de- composition, and in practice, it always holds that K Z R. Corollary 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; Figure And we can use this finding to evaluate their model efficiency.
(T1) Standard bottleneck block. The basic building block in ResNet (He al. 2016 can be exactly replicated by a Tucker decomposition on Astack E IR's xl2xC* with ranks of (1, 12, R. R). where C' the number 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 straightforward revision maintains an output channel size of K = R. This is hence an efficient block design. Also, when R = C, we obtain normalized funnel block, with the same number of imput and output channels.
standard bottleneck block, the funnel block
(C1) Depthwise separable block. This block is the basic module in MobileNetV1 (Howard et al.,
2017) with pair of depthwise and pointwise separable convolution layers. It is equivalent as- suming CP decomposition on Astack E IR x with the rank of C' (Kossaifi et al. 2020b). The x 1 pointwise convolution expands the numbers of channels from C' K. When K > this design is parameter inefficient from computation viewpoint.
(C2) Inverted residual block. (andler et al. 2018) later proposed this design in MobileNetV2. includes expansive layers between the input and output layers, with the channel size of x- (t-C(1 1), where x represents the expansion factor. As discussed by Kossaifi et al. (2020b), can heuristically correspond to CP decomposition 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.
A with CP rank equals to C. Since, the rank of output
With nonlinear activations, the model redundancy may bring some benefit. Such benefit is often not guaranteed. And when K" >> R, it will, without doubt, greatly hinder computational efficiency. We will show, in our ablation studies in the next section, that under realistic settings with nonlin- ear activations, our finding on the K/R ratio still applies. Specifically, networks with K/ K/R maintains comparable performance as networks with K/ R > 1, while using much less parameters.
4 EXPERIMENTS
This section first verifies the theoretical results with synthetic datasets, and then conducts ablation studies on the bottleneck blocks ResNet (He et al. (0166) with different K/ //F R ratios.
4.1 NUMERICAL ANALYSIS FOR THEORETICAL RESULTS
We choose four settings to verify the sample complexity in Theorem 1 see Table 1 The parame- ter tensors {Ak, B& Ik=1 are generated to have standard normal entries. We consider two types of
(TI) Standard bottleneck block
(T2) Funnel block
(CI) Depthwise separable block (C2) Inverted residual block
Tucker inefficient
Tucker efficient
ineflicient
efficient
Figure 2:
We use thickness of each layer to indicate its relative number of channels. The last layer indicates the output of the block. The dashed layer represents the "bottleneck" the block.
7

---

Under review as a conference paper at ICLR 2021
Table 1: Different settings for verifying Theorem 1 (left), and Theorem 2 (right).
Input sizes
Kernel sizes
Pooling sizes
Kemells
Inpett sizes
Komel sizes
Pooling sizes
Tacker ranks
Kemels
Seting (S1)
(7.5.
2.2)
(3,2,3) 3)
(10, 1.38.3)
(5.5.3)
(3.3.3)
(2.2.2. 1)
Setting? 2 (S2)
(7, 7)
(,,2,2)
(3,2,
(10, 10, 8,
(5,5,3)
(3,3,3)
(2,2,
Setting (83)
(8, 8,
(3,3,))
(3,3. 1)
(12, 6,,
0,7,3)
(,3,2)
(2,3,2,0
Settig (54)
(8, 8,,8,3)
(3,3,3)
(3,3. 1)
(12, 6,,
(7.7.)
(3.3,2)
(2.3,2.1)
(1) CNN dm0
e1 CMN Timedapeeteett dots
Turler CMN L10
Figure 3: (1)-(2) are the experiment results for Theorem 1 with independent and dependent inputs, respectively. (3) is the experiment results for Tucker CNN in Theorem 2.
inputs: the independent inputs are generated with entries being standard normal random variables, and the time-dependent inputs (x*) are generated from a stationary VAR(I) process. The random additive noises are generated from the standard normal distribution. The number of training samples varies such that v /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 Frobe- nius norm. It can be seen that the estimation error increases linearly with the square root of dm/nn, which is consistent with our finding in Theorem] !
For Theorem 2, also adopt four different settings; see Table Here, consider 4D input tensors. The stacked kernel Astack is generated by (). 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 V
/axt /n is equally spaced. A linear trend between the
estimation error and the square root of dTV /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
4.2 ABLATION STUDIES ON COMPUTATIONALLY
BLOCK DESIGNS
Following the notation in Section 3, we denote by K, the number of output channels of bottleneck block, and by R, the Tucker rank of Astack along the output channels dimension. Since K > R. we let t= K/ be the expansive ratio of the block. As / increases, the number of parameters within the block increases. Here, ablation studies are conducted show that the increase in does not necessarily lead to the increase in test accuracy. We analyze two image recognition datasets, CIFAR- 10 (Krizhevsky al., 2009) and Street View House Numbers (SVHN) (BNetzer al. 2011 and an action recognition dataset, UCF101 (Soomro et al. 2012 Standard data pre- pre-proccesing and augmentation techniques are adopted to all three datasets (He al., 2016 Hara 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: consists of a x convolution layer, max pooling layer, followed by 3 groups of A + x 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 = 1, it corresponds to the normalized funnel block in Section 3 (T2). For sake of
Table 2: Test accuracy(%) on CIFAR-10, SVHN and UCF101. For UCF101, we only count the number of parameters and FLOPs for the added blocks.
CIFAR-10
SVHN
#FLOPs
#Params
UCF101
#Added FLOP:
#Added Params
1
93.53
96.30
0.17GMac
5.56M
79.31
0.125GMac
6.7MM
0.26GMac
8.55M
0.145MMac
9.16M
8 93.59
96.32
0.43GMae
14.15M
79.25
0.175GMac
11.11M
94,03
96.31
0.87GMac
29.28M
79.52
0.235GMac
15.00M
8

---

Under review as a conference paper at ICLR 2021
Block 1
Block
Block
(1)
Win cinchaamss
1X LORY
BloditA 2 8) 6 61
Block(4
3 corr 5- 2
X come
226
Blodu.
auscage pusling 6
6,8 - 128
1 1
Blcckt 5 6,8 m 256
pooling
Figure 4: (1) 41-layer Residual Network for CIFAR-IO&SVNE (2) 30-layer 3D Residual Network for UCF101. Here, t = K/ / represents the expansion ratio, and takes values of 1,4,8.16.
comparison, we also take / = 8 or 16. When & > 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 I = 1, we propose minor revisions to simultaneously increase the channels while performing the stride-2 3 x 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 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 slightly better than 1 but it uses 5 times as many parameters.
Implementation details. All experiments are conducted in PyTorch and on Tesla VI00-DGXS. Following the practice in He et al. (2016), we adopt batch normalization(BN) (loffe & Szegedy) 2013) 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), follow Hara al.. (2018) and use the Kinetics pretrained 3D 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 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 I clip accuracy is around 79% for UCF101.
5 CONCLUSION AND DISCUSSION
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 large kernel tensor A (Peng al. 2017). 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 CNN block in order increase accuracy in a more parameter efficient way. In this regard, one can either choose small R with deeper networks or larger R with shallower networks. In fact, when K K/R "straightened"" bottleneck in Zagoruyko & Komodakis (2016), who showed in their empirical study that by increasing in shallow networks, the test accuracy can indeed improve quite significantly.
the block corresponds exactly to the
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. (0117) applied tensor decomposition to fully-connected layers since they may contain large number of parameters as well. Along the line, we can stack the fully-connected weights BB E RPI x xpx with 1 < k < K into higher order tensor B stack R XPs x.. Xpy & and further consider 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.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of the 36th International Conference on Machine Learning. volume 97, pp. 242-2422222222 252, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 354-263, 2018.
Marcella Astrid and Seung-lk Lee, Cp-decomposition with tensor power method for convolutional neural networks compression. In 2017 IEEE International Conference on Big Data and Smart Computing (BigComp), pp. 115-118. IEEE, 2017.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally- margin bounds for neural networks. In Advances in Newral Information Processing Systems, pp. 0240)-649, 2017.
Sumanta Basu and George Michailidis. Regularized estimation in sparse high-dimensional time series models. The Annals of Statistics, 43(4):1535-1567, 2015.
Yuval BNetzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Read- ing digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011,
Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57 (4):2342-2359, 2011.
Yuan Cao and Quanquan Gu. Tight sample complexity of learning one-hidden-layer convolutional neural networks. In Advances Neural Information Processing Systems, pp. 10611-1062,, 2019.
Yu Cheng, Fei Wang, Ping Zhang, and Jianying Hu. Risk prediction with electronic health records: A deep learning approach. In Proceedings of the 2016 SIAM International Conference on Data Mining, pp. 432-440. SIAM, 2016.
Misha Denil, Babak Shakibi, Laurent Dinh, Marc' Aurelio Ranzato, and Nando De Freitas. Pre- dicting parameters in deep learning. In Advances in Neural Information Processing Systems, pp. 2148-2156, 2013.
Simon S Du and Surbhi Goel. Improved learning of one-hidden-layer convolutional neural networks with overlaps. arXiv preprint arXiv:/805.007 1805007798, 2018.
Simon S Du, Yining Wang. Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples needed to estimate convolutional neural network? In Advances in Neural Information Processing Systems, pp. 373-383, 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv.1810.02044, 2018b.
Jianqing Fan, Wenyan Gong, and Ziwei 7hu. Generalized high-dimensional trace regression via nuclear norm regularization. Journal of econometrics, 21 212()): 2019.
Haoyu Fu, Yuejie Chi, and Yingbin Liang. Guaranteed recovery of ane-hidden-layee neural networks via cross entropy. IEEE Transactions on Signal Processing, 2020.
Surbhi Goel, Adam Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. arXiv preprint arXiv:1802.022. 02540....222...... 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- Size-independent sample complexity of neural networks. In Conference On Learning Theory, pp. 297-299. PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2021
Kensho Hara, Hirokatsu Kataoka, and Yutaka Satoh. Learning spatio-temporee features with 3d residual networks for action recognition. In Proceedings of the IEEE International Conference Computer Vision Workshops, pp. 3154-3160, 2017.
Kensho Hara, Hirokatsu Kataoka, and Yutaka Satoh. Can spatiotemporal 3d cnns retrace the history of 2d cnns and imagenet? In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 6546-6555, 2018.
Kohei Hayashi, Taiki Yamaguchi, Yohei Sugawara, and Shin-ichi Maeda. Exploring unexplored tensor network decompositions for convolutional neural networks. In Advances in Neural Infor- mation Processing Systems, pp. 5552-5562, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on Computer Vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Andrew Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 1704.0461,, 2017.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 4700 4708, 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference Inter- national Conference on Machine Learning, pp. 448 456, 2015.
Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Com- pression of deep convolutional neural networks for fast and low power mobile applications. In International Conference Learning Representations, 2016.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM Review, 51(3): 455-500, 2009.
Jean Kossaifi, Aran Khanna, Zachary Lipton, Tommaso Furlanello, and Anima Anandkumar. Ten- contraction layers for parsimonious deep nets. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition Workshops, pp. 26-32, 2017.
Jean Kossaifi, Adrian Bulat, Georgios Tzimiropoulos, and Maja Pantic. T-net: Parametrizing fully convolutional nets with a single high-order tensor. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7822-7831, 2019.
Jean Kossaifi, Zachary C Lipton, Arinbjom Kolbeinsson, Aran Khanna, Tommaso Furlanello, and Anima Anandkumar. Tensor regression networks. Journal of Machine Learning Research, 21 (123):1-21, 2020a. 202,a
Jean Kossaifi, Antoine Toisoul, Adrian Bulat, Yannis Panagakis, Timothy M Hospedales, and Maja Pantic. Factorized higher-order cnns with an application to spatio-temporal emotion estimation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6060- 6069, 2020b.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Tech Report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
11

---

Under review as a conference paper at ICLR 2021
Vadim Lebedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oseledets, and Victor Lempitsky. Speeding up convolutional neural networks using fine-tuned cp-decomposition. In International
Conference Learning Representations, 2015.
Jingling Li, Yanchao Sun, Jiahao Su, Taiji Suzuki, and Furong Huang. Understanding generalization in deep learning via tensor methods. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 504-515, 2020.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. Shufflenet v2: Practical guidelines for efficient architecture design. In Proceedings of the European conference computer vision (ECCV), 116-131, 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learming Theory, pp. 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally-normalzzed margin bounds for neural networks. arXiv preprint arXiv:100.005664 2017.
Chao Peng, Xiangyu Zhang, Gang Yu, Guiming Luo, and Jian Sun. Large kernel matters-improve semantic segmentation by global convolutional network. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 3353-4361, 2017.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang -hing Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp.
2018.
Max Simchowitz, Horia Mania, Stephen Tu, Michael Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. Proceedings of Machine Learning Research vol, 75:1-35, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah. Ucf101: dataset of 101 human actions classes from videos in the wild. arXiv preprint arXiv: 221. 2012.
Jiahao Su, Jingling Li, Bobby Bhattacharjee, and Furong Huang. Tensorial neural networks: Generalization of neural networks and application to model compression. arXiv preprint arXiv: 10352, 2018
Qiuling Suo, Fenglong Ma, Ye Yuan, Mengdi Huai, Weida Zhong, Aidong Zhang, and Jing Gao. Personalized disease prediction using a can-based similarity learning method. In 2017 IEEE International Conference Bioinformatics and Biomedicine (BIBM), pp. 811-816. IEEE, 2017.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 1-9, 2015.
Du Tran, Heng Wang. Lorenzo Torresani, Jamie Ray, Yann LeCun, and Manohar Paluri. A closer look at spatiotemporal convolutions for action recognition. Proceedings of the IEEE conference Computer Vision and Pattern Recognition, pp. 6450-6459, 2018
Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3): 279-311, 1966.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
12

---

Under review as a conference paper at ICLR 2021
R. Vershynin. High-dimensional probability: an introduction with applications in data science. Cambridge University Press, Cambridge, 2018.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
Di Wang. Feiqing Huang, Jingyu Zhao, Guodong Li, and Guangjian Tian. Compact autoregressive network. arXiv preprint arXiv: /909.0383,, 2019.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1492-1500, 2017.
Sergey Zagoruyko and Nikos Komodakis. arXIv:1605.07116.2211
Wide residual networks.
arXiv preprint
Kai Zhong, Zhao Song, and Inderjit S Dhillon. Learning non-overiapping convolutional neural networks with multiple kernels. arXiv preprint arXiv:1711.03440) 2017a.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit Dhillon. Recovery guarantees for one-hidden-layer neural networks. In Proceedings of the 34th International Conference Machine Learning, pp. 4140-4149, 2017b.
Pan Zhou and Jiashi Feng. Understanding generalization and optimization performance of deep cnns. arXiv preprint arXiv:1805.10767 2018.
13

---

Under review as a conference paper at ICLR 2021
A APPENDIX
This appendix contains five sections. In the first section, we provide details for our mathematical formulation for high-order 3-layer CNN. In the next section, 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 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.
A.1 CNN FORMULATION
For a tensor input X E xxxxx it first convolutes with an N-dimensional kernel tensor A E R4 x-xxyy with stride sizes equal to 8es and then performs an average pooling with pooling sizes equal to (qi,".. .qN). It ends with a fully-connected layer with the weight tensor B and produces scalar output. We assume that mj (dj /s) + 1 are integers for I j N, otherwise zero-padding will be needed. For ease of notation, take the pooling sizes {q; f==1 to satisfy the relationship my = Pj
To duplicate the operation of the convolution layer using simple mathematical expression, first need to define a set of matrices {U!b] E [24x x1y)) where
U = -
I'R xly for 1 Si S my, 1SjSN.
(9)
(1,-1)8c d, (1- 11)--1))
fy 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 3-layer tensor CNN. To begin with, we first illustrate the process using a vector input æ E Rd, with kernel vector a E R see Fig 5 Using the 7th positioning matrix U we can propagate the small kernel vector a, into vector U. of size Rd. by filling the rest of the entries with zeros. The intermediate output vector has entries given by 2x(1) = (x. U. a), for S i S m. The average pooling operation is equivalent to forming p con- secutive vectors within Z.. each of size R2, and then take the average. This results in a vector Tep of size IR, with ith entry equal to (i)(1) = q " ( (i) = (x,4-- Ei- (i- 1) U a)- The fully-connected layer performs weighted summation over the vectors, with weights given by entries of the vector b IRP, This gives the predicted output ğ = (b, xep) = (x, wx), where
ig E
Wx = Σ
UHe a= (b)))
1=1
(=
and U = -- U@)
Ex-m-gt1 U("),, and "x1" " represents the mode-1 product.
For matrix input X with matrix kernel A, however, we need 2 sets of positioning matrices, one for the height dimension and the other for width. Then, the (X, U(!)) AU!?"), for 1 < i I Pi. 1 E is S P2. For the average pooling, we form P1P2 consecutive matrices from X,, each of size Re and take the average. This results in Xap E RPiXP2, with Xip iz) = Uk (r)))) The output Xep goes through fully-connected layer with weight matrix and gives the predicted output ğ = (X, Wx), where
is (U!")) M= and (2(2))m m2 -
intermediate output from convolution has entries given by i2()
(X, - UK) A((z -kz=(t2 1)
P1 by
iigi
i292 Σ
Wx
biz
Σ
A
T(2y) k2
(B3A) x U U X
R1
9192
4=1 =1
k
k1=
199+11
k2= (12
192+11
with فهن
of
U .....
Ek=m
(1)) for j 1 or 2. And "x," ", "x,"""""" represent
the mode-1 1 and mode-2 product.
14

---

Under review as a conference paper at ICLR 2021
Convolution
Avemge pooling
Fully-connected layer
x
0
0100
9-1 2 U
Litem- b,a
lmd
(mm--p-1
Figure Formulating the process with an input vector a. Note that we combine the convo- lution, pooling and fully connected layers into the composite weight vector wx, where wx
E U.! a+... " 2i=m-g41 U a. The @ represents the convolution operation.
From here, together with the case high-orde tensor input discussed in Session 2.2 we can then derive the form of predicted outcome as = (X, Wrsingle where
Weingle
(B
2 A) X1 U
X2 U x
U
with U-41 = 9 for S.S N.
E U E
Ul and "x, represents the mode-j product +1
With K kernels, we denote the set of kernels and the corresponding fully- colle-conneeted weight tensors as (As; H Since the convolution and pooling operations are identical across kernels, we can use summation over kernels to derive the weight tensor for multiple kernels, which is
B AR) x1 U X2 U ... (N)
Wx
and we arrive at the formulation for 3-layer tensor CNN.
A.2 FIVE-LAYER CNN FORMULATION
Consider a 5-layer CNN with layers and 3D tensor input X E Xddixd Here, denote the intermediate output from the first convolution by X. Rm Xmax from the second convolution by X. R xm, x and the output from the first pooling by Xep 12t1 X and from the second pooling by XCp E Rd: x$2xÿs, We can first see that the predicted output from the 5-layer CNN the same as directly feeding Xep to the second convolution layer, followed by average pooling layer and fully-connected layer.
connected"
Denote the first convolution kernel tensor by A E xlaxs, the second convolution kernel tensor by A R fxxlxfs, and the fully-connected weight tensor by B R Define the set of matrices (U4) E [d }. for 1 < ig s mj, 1 < j < N as in And similarly, define (ū xls with
5
R.
(10)
(33 1)88 p--(6-11)8--
where Sa is the stride size for the second convolution. Let أهب (0))
T0) =
5
(ē Ee ū q
Lk-my-a+ (
my
We further stack the matrices (U!
Rd, Rd,xly ( D5sisps and (56) RR Jisss, into 3D tensors 40 IRd, xl,x,, and i (
RP, x
15

---

Under review as a conference paper at ICLR 2021
We have that the predicted output
(B
A,
X1
X2
f X3 )
P
P2
P8
B
A 1 U X2 U X3 F o uis o uis
B B
Σ
x 11 (ū &U X2 (ū, @ &U x3 (ū,, @ uUf
B8A A 8 A,X 1 (1 X3 u (n) X2 (u u 2 Yn) X3 (u 3 x3 u Th (11)
(B 8 A 4) (2 u (1)
)() X2 (2
X3 u (2)
x3 u )m))) (1) x3 (u
x (B 2 A A) X Ubt U07 5
)a)- where U. voc(U()) (1) (1,, RLb and Ubf (2 X3 u ) for 1 S ig S Pj and
15j 33
A.3 THEORETICAL RESULTS AND TECHNICAL PROOFS
Let 2 xX' x1 U/ X2 Uf the form of W Σ Be 2 Ar, where
@ x.. NN UfN e ghii Xlapsx The trained weights have
K
B Ashissk =
arg min A.ASK
1 Σ
Σ
B 8 Ax
k=1
Given a test sample (X, y). where = (XC Wx) + E. and (XC, {) satisfies Assumptions 1 and 2. The mean-square training and test error are defined
y (X0) wx)) and eer( = E (v- (XC wx))
efftrain W
1=1
Denote KU = Cn and Kr = CrCa. Let W = Σ B A be the true weights, and || 2 n - ((3), W) be the empirical norm with respect W. The model complexity of CNN at equation (1) or (2) is dm= = K(P + L + +).
Theorem (Complete Version). Suppose that Assumptions 1-3 hold and n Z (NU ( ) Then, for some 8 > 0,
160 /ARSM ORSC
dM
(a) J W |F <
n
n
1600RSM
d
(b) J
Wl
+
OBSC
n
160ARSM
d. 8
(c) err (W)
<
+
C'RSC
n1
with probability 1- exp [CH (.ccH00.2mmm (0.25%1//50 )/b5)) n -expf -dm - 86}. where cn is a positive
value, omsc /2, and ORSM 3kU/2 /2.
It can be seen that the estimation eπror, W W' is Op( (d(dd//)), and hence the sample complexity is of order (ddm/=²), to achieve training error E. The empirical norm is equivalent the training error minus the sample standard deviation of noise. And we can see that the training error eraar (W)= = O (d(ddm//) + â and test error err (W) = Op(ydm// + a,, where & and o represent the sample and population standard deviation of noise, respectively.
16

---

Under review as a conference paper at ICLR 2021
Now proceed to provide complete version of the sample complexity of compressed CNNs. Let dM I N+1 R2 Σ N
R4 + Ry+1P P and d RNN+1 + + P).
Theorem 2 (Complete Version). Let (W, dm) be (Wro, d for Tucker decomposition, or (Wer, d for CP decomposition. Suppose that Assumptions 1-3 hold and n. Z Pxdd Then, for some 8 > 0,
160 /RRSA
CNdM n
5
(a)l W S
V
O'SC
72
(6) - 1' 160ARSM
cNdM
1
8
+
n
CRSSC
11600SsM
CNdM n
8
(c)er² (W)
1
+ + +0?
CRSC
with probability 1 4 (opp--(ca00.55.... / - dedd expl- dm - 86), where ON = 2 2 log(N + 2), cи is a positive value and aRSC, aRSM defined in Theorem 1.
Because CP decomposition can be considered as special case of Tucker decomposition where Rg R, for 1 S j S N + 1. We only provide the proof for Tucker CNN.
A.3.1 PROOF OF THFOREM 1
Denote the sets SK = EE k= B 2 A AA E RRxxlxxxxxxx and BB E R and
SK- = (W E Sx: || = 1). Let A W W and then
Σ
w - (23 w/
2 v Σ (0t -
(
(2',
2=1
1=1
which implies that
<
2
sup Σ 5' A) |F
(11)
AES,K 1=1
i=1
where | || := n- ((Z3, } 2 is the empirical norm with respect to A, and â S2K.
Consider a e-net S2K, with the cardinality of N2(2, E), for the set S2K. For any A S2K, there
exists a A E Sax such that A A S e. Note that A E SA4 and, from Lemma [a,
we can further find A,, A2 E S2x such that (A1, A2) 0 and A A A + A.. It then
holds that A + A2l1E I / A 22 since A a result,
=
A
| A As
D 1=1
A + Σ tl (Z'. A2)
+
n 5 A,) + 20 sup
Sax n ES(3,A) A)
< max 15j5N(2K,z)
n
which leads to
sup
Σ
gz $1 V2 (2K,) n
max
1 E A
(12)
AES2K 1=1
17

---

Under review as a conference paper at ICLR 2021
Note that, from Lemma [b) log (2), < 2dM log(9/s), where dm K(P + L ++ 1). Let
(2v2) and then - 2 (9gg(9/E) 1. As result, by 12 and Lemma
n
(Van
sup
(z)
2 S0 VRRM
+V
+
sup AES2X
| ll I aRSM
AES2K
n
dM
SP
max
A,) 2 40 VovaMsM
+
sup AES2K
A l S
ORSM
(2)5)(2
1=1
(22,,e
jdm
P
(Z),, ا,) 40VARSM
(V
| S ORSM
n2
n
1=1
S expp dM - -87.
(13)
Note that
n 52(33, A 2 S0 VRRMM
Var
du
sup
V
+
AES2K
i=1
(Vih dM
S TP
sup
2 S0
sup AES2K
| S CnsM
AES2R
n i=1
n
n
P
sup
2
ORSM
AES2x
From
13 and Lemma
we then have that, with probability
4 expl - (c.10.225k /
(d expl -dd
1
(Van
du
sup AES2K
So v
CRRM
V
and
2 aRsC
A 1
11
i=1
which, together with
leads
A
F
160 /ORSM
dd
and
| S 160 ORSM
Vanu
V
du
ORSC
n
aRsc
n
n
Finally we prove (c). Given a test sample (X, v), and let 2 = xx, U (1) holds that
X2 U (2)
X3 X N.
Ely (X, Wx Wx))² B(y - (z, w))² = EE(2,
and
E( A)) A AE(EEEE = A'UGE(ET' S 1
As result, from (a) of this theorem, have
160ARRM )
(dM i
enz2 err) -
+02
ORRCC
n n1
This accomplishes the proof.
A.3.2 PROOF OF THEOREM 2
Denote the sets STU,R,,...,R Rx41) (EK B & A the stacked kernel Astack E xxxxxxxx has the ranks of (RI, RN, RN+1) and Bg R xxxxpxx--Xxx] STU
( + W2 : W1, W2 E STU (RI, RN+1)}. and STU = (w E STV ||Wl|e = 1).
Note that Wru, W E (TT, RN+1), and A Wre W S2
18

---

Under review as a conference paper at ICLR 2021
We first consider E-net for S2k For each 1 2 k: - K, Let by (bx1.-.. PEPY vec(BB)), and we can rearrange B, @ Ag into the form of Ag o by- which is tensor of size TR xlxxxxxxxxx where = P1P2 PP.. Denote = (buj) E I nx K and holds that
PN.
A bb A AXN+1 9 X1 H X2 H XN+I B,
which tensor with the size of R xlxxxxxxxxxPPP and the ranks of (Ri,... RN, RN+1) where B = BH (N+1) g*x Essentially, in this step, we rewrite the model into one with Rk+1 kernels instead. Specifically, we now have W = Rx+1 A, @ Br, where A, Sr X1 H X2 H (2) XN H(N) with 9 ". ,r) and the r-th column of B is the vectorization of B, for S RN+1-
STU consists of tensors with the ranks of (2R .... 2Rx 2R at most. As result, 22
Denote (T1, -N, TN+1) = {J R4x xly x
||]|| = 1, has the Tucker ranks P1P2 ......p PN. Then the E-covering number for STV
of (ri,'.. ""N.""",,NN" (N+1)) where IN+1 satisfies
ITU
T (2R1,
For each T E STucker (r1, N, TN+1), we have
J = 9 X1 (1) X2 .. XN+1 UN+11,
and U E R4xx with S S N + orthonormal matrices. We now construct an E-net for STucker sets of 9 and all (t)s,, and the proof hinges on the covering number of low-multilnnear-ran tensors in Wang et al. 2019). Treating 9 as I r, didiinnnionaal vector with |||| 1, we can find an e/(N -ett for it, denoted by G, with the cardinality of [G| (3(N ()) I rs
where X- with |||F
TN: (N+1) by covering the
Next, let On, = (U E Raxx :U = I,). To cover On,r. is beneficial to use the || ||1 norm, defined as
11,2 max [epax||X;]1 ||
where X; denotes the 7thh column of X. Let Qn, {X Raxr ||||1,, S 1}. One can easily check that Ou, C Qn.r. and then e/(N + 2)-net On, for O has the cardinality of 10nrl I (3(N + 2)/E)"r. Denote STucker (T1, ,TN, (N+1) {S U(1) x.... X UN+++ 9 E G. ( E Ö S S N + 1}. By similar argument presented in Lemma A.l of Wang et al. (211)). we can show that "Tucker(11, ,N, TN+1) 1) is E-net for the set STucker (F1, ... TN, TN41) with the cardinality of
3N + 11 + brs
where |N+1 = P. Thus, the e-covering number of STU
2 11 R,+2EN 2R
3.V +
(T) = =ISTucker (2R1, ... 2RN, 2RN+1)1
Let E 1/2. It then holds that log(3(N + 2)/e) < 3 3log(N N + 2) and log./TU( < 2~+1dTu log[(3.V + 6)/ee, where d'u show that
-1 R5 MN I. + RN+1P. I.. By method similar
N+1
to the proof of Lemma
sup AESTU
||| 2
OnSM
< 2exp
-CHN
KL 4ku
+ 3eNd {
(14)
and
P
inf AESTI
||| 2 < URSC
< <eexp
-CHN
KL
+ 3CNd TU
(15)
4Ku
19

---

Under review as a conference paper at ICLR 2021
where ON show that
2 log(N + 2). Moreover, similar to equation 13
by applying Lemma
we can
sup AESIK
2 80 VRRMM
(
cNNda M
+
sup A AES2
| ll S ORSM
Y
n
i=1
cend M
SP
max ISISATO (c) n
2 10 4ovans
sup EES
A ll S
CRSM
N (e)
$
Σ P Σ (z (A,) 40 VRRMM
+
| 1l - RRSM
j=1
$ exp( d 867
(16)
where 8 = (2v2) and 2 log(N + 2) - 2N (N + 1)/8) > 1. By a method similar
to the proof of Theorem 1, show that, with probability exp [ca(0..5k_/rrz) ) 3CN log(N + 1) exp( - 86}.
n EZ A S 80 VaRSM
cxdM M
sup TI
+
and
| z ansc ||
AEST 2K
i=1
n
72
which, together with equation 11 leads to
16 VanSM aRSC
CNdil
!
+
V
n
cxddi
18
A In S
160
CRSM
+
aRSC
n
160TRRMM
2
8
er?² (WTu)
+
+ 0².
ORSC
n
n1
We accomplished the proof.
A.3.3 PROOFS OF COROLLARY
When the kernel tensor A has a Tucker decomposition form A 9x, X2 X3 .Xx1 HN++1), and the multilinear rank (R,, R2.... RN+1). Let HC = x1 (1)) x2 (2) X3...XX (N),, which is a tensor of size Tlx xgxxxxxxxx xRx+. The mode-(N + 1) unfolding of H a matrix with RN+1 row vectors, each of size RRL, and we denote them by 91. 'INN+1- Fold g,s back into tensors, i.e. gr = vec(IC,). where H., E x and 1 I r < RN+1- Moreover, let (N++) is vector of size R Rx++ and we denote its nhh (N+1) for 1 r < RN+1. It can be verified that, for each 1 < K: S K, entry as k,r
(N+)) (h +1) h
(N+1) lly, where h
K
A = 9 1 (1)) X2 ( ... XN H (N) x (N+1)
JC N 1/
(N+1)
and hence,
By+1 K
Ry+1
K
Σ B A Σ
Σ
B₁ s H. h
((N41))
Σ
(N+1)BBg
& H,
By letting B, k== Mrr model into
(N+1) B3 and A,
FC, for 1 S s RN+1, can reformulate the
R +1
Σ
B, 8 A,, 2²) +
and the proof of (a) is then accomplished.
20

---

Under review as a conference paper at ICLR 2021
Suppose that the kernel tensor A has a CP decomposition form of A E o, (2) hr (N+1) where h R and ||,, ( 1 for all S j S N. Moreover, h, (N+1)
(h (1) ... T,K
(N+1) (N+ I2 and | ( I. Note that
R
A
Σ
a r.
(N+1) (1) o h o (M)
for all 1 S k S K, and hence
R K
B
A Σ
Bx &
h(()) h h!NT)
k=1
R
hy
(N+1)
B₁ 8 (ar o (22) ..... lo. n,,r))
By letting B, h h reparameterize the model into
(N+1)
BB and A, ar (2)
hr
(2)
....o h (N) for all S S R, we
R
B, 2 A,,
and the proof of (b) is then accomplished.
A.3.4 LEMMAS USED IN THE PROOFS OF THEOREMS
Lemma 1. (Partition and covering number of restricted spaces) Consider Sx {E B A
A E xxxlxx-xxx and Bx E R XpxX--XXX } and SK {W E Sx || = 1
(a) For any A S2K, there exist W1, W2 E SK such that A = W + W2 and (11, W₂) = 0.
(b) The e-covering number of the set Sx
N(K,=) s (9/E) ((/=))(
where L 1112..--1x Ly and P P1P2 .. PN.
Proof. For each K, we first define map Tr Sx PXL, For any W = >K Br Ar E Sx. we define that (W) = ΣK vee (Bt)) voc(AA)) PxL, which has the rank of at most K.
For any A E S2K. the rank of matrix Tx ) is at most 2K. As shown in Figure 6 we can split the singular value decomposition (SVD) of T A) into two parts, and it can be verified that Tk (A)
V + U2A Vz2 and (U' U,A, V2') = 0. Denote U; = (u u2 ..... K and
V.A, (v) (0)
UK for = and 2. We then fold (6) and vy s into tensors, i.e.
(9) veo(B and UR
(8) vec(AA (0) with S S K. Let W, Σk B()) @ (!)) and
u
W DK B(2 8 ( It then be verified that W1, W2 Sk. A W1 + W2 and (W1, Wz) = 0. Thus, we accomplish the proof of (a).
Denote by Smatrix Pxt. the set of matrices with unit Frobenius norm and rank most K. Note that T(Sx) C Smatrix, while the e-covering number for Smatrix is
Smatrix| S (9/2) (L)+)((++
see Candes & Plan 2011). This accomplishes the proof of (b).
21

---

Under review as a conference paper at ICLR 2021
U, U2
A2
V
V' 2
U R
Figure 6: Splitting matrix T(A) based on its singular value decomposition.
Lemma 2. (Restricted strong convexity and smoothness) Suppose that n Z (KU (RU/RL))dM It holds that, with probability least 4xpp ((pp(-(c ) 9dm]],
ØBsC | S
(13 A)}
CRSM I F
for all A E S2K, where S2k is defined Lemma
CH positive constant from the Hanson-
Wright inequality, aRsc = KL/2 and ORSM 3Ky /2.
Proof. It is sufficient show that sup S |||| 1 S ORSM and inf AeS2
- Z anse hold
with a high probability. where A 1l == n Ei= ((z,, A))² is the empirical norm, and S2K is
defined in Lemma [ Without confusion, in this proof, we will also use the notation of A for its vectorized version, vec(A). Note that
n
A 2
(Z) A))²
Σ
"UGAA'U
n
n1
n
(17)
x In (UG U3)
w Qw,
where Q = n Σ In & (UG Σi, 1 E RaD a random vector with i.i.d. standard
normal entries, x' U' x² = vec (X') ) = (x" ",""" ..... z" and Σ = E(@æ') e DDDD
Denote WG = UG E D and nn (v E R :|0112 = 1}. Let Amax Eis) be the maximum eigenvalue of Σ;; E(vec (X') vee (2")) for 1 < i is n, and holds that Amax (Ex) S C2 for all 1 < i < n. For matrix Q, we have
1 tr(Q)= tr Σ In wall In
w/d [
w/a
1 tr ([I, @ w/ & wel)
(w/ D(we)
n
w' w'DDww
sup WOE
w/uuG
sup AESPE-1
A'UGUGA S
Amax Eig) S KU
(18)
and similarly, we can show that tr(Q) 2 Kr, where Ky, = C,Cus = C2C,, and KG S ky. Thus,
R1 E E 12 tr(()= KU-
(19)
Moreover, denote Q1 = - I,, x wc] and note that Q = Q Q' To bound the operator norm of Q, we have
sup n' u'Q - sup u' In w'g E[I, @ wa/u
11
uEga-1
n wega-1
1 sup
w'In w/ E & wely
sup u' u'[n, X w/ (
(20)
71 wE8
w I' & w/ll In & walu
Cz
ww 1 <
C₂
UG op
| ? < Ri
n
22

---

Under review as a conference paper at ICLR 2021
Finally
(8 and 20
to bound the Frobenius norm of Q. By some algebra, for any
square matrices A, B
R
[ABB]
A up
[B holds. Hence,
Q = 1Q:Q <
Q Q 1Q tr(Q) -
KU 2018
This, together with to
20 and the Hanson- Waanson-Wright inequality (Vershynin
Chapter 6), leads
t²
P
E
2
S 2 exp
-H min QQ op
11Q1
(21)
2 2xp {
(-Hn min (t/nu, (t/me)²)
where on a positive constant. On the other hand,
R 71 Σ A'='="A E(A' ATA
E(z'z 2)] is a symmetric matrix. Consider a E-net S2k, with the cardinality of E), for the set S2x. For any A S2k. there exists a A, S2K such that
where f = n 1 Li=1 12
S Note that A - A, SaK and, from Lemma we can further find A A2 E S2x a - ||
such that (A,, A2) O and A A A + 22, and it then holds that || A ||F + || S
A A ||r S V2e. Moreover, for a general real symmetric matrix A E R 1dxd E R and
Rd, sup =/|2=||0|/== u' Au suP///|2=1 u' Au. As result,
ATA AJiA (A A A + A2 +A,))
A TA + 58 sup AESOK
A'TA,
max
(2K,)
where (| |F + 2211))² + 2(1 leads to
A 1 |F S 2( + /2)e S 5s as < 1, and this
A A A < - 55) max
TJA
(22)
A
(2K,)
Note that, from Lemma Tb), (2K, < 2d log(9/e) where dM = K(L + P 1).. Let E 1/10, and then (ogg(9/ ) 9. Combining (1)) and (2 and letting
(9/)
2, we have
2
+ Sadm )
sup AES
|
E
12
KL 2
2exp
CH
which, together with 19) and the fact that KI. S NU, implies that
< 2exp {
2 + gdn
P
sup AESaK
| 1 2 ORSM
-cHm
KL 4Ru
(23)
where QRSM = 1.5KU 2 KU + k2/2.
By method similar
122
also show that
sup AES
E
(1 58)
A (2K,)
E
1
|
which, together with 21 leads to
2
)
sup
E A 2
|
12
K1. 2
< 2 2exp
-CHT
Ki 4Ku
+ 9d J
ES2x
where f = K2/2 2 and
1/10. As a result,
P
I inf
A 1 <
onsc
< 2 2exp
CHT
KL 4Ku
+ 9dm
AES.X
where onsC Ki R2/2. This, together with
23
accomplishes the proof.
23

---

Under review as a conference paper at ICLR 2021
Lemma 3. (Concentration bound for martingale) Let {5' 1 S i n. be independent o?-sub- Gaussian random variables with mean zero, and { 1 S i < n) is another sequence of random variables. Suppose that E is independent of {z', 2¹ ...., for all S n. It then holds that, for any real numbers o, 3 > O,
na² 2028
P
Σ
C2
S exp
T
Proof. We can prove the lemma by a method similar to Lemma 4.2 in Simchowitz et al. (2018).
A.4 CLASSIFICATION PROBLEMS
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
K
output (XC,
BE
2
An)
X1 U
X2 X3... XN
(N)) NN U
(Z, W),
k=1
where W -- Σド is the kth kernel and Bg E X Xp2 XpN is the corresponding kth fully-connected weight tensor.
k- B @ Ag and z = x Uf X2 U2 x3. X U Ar R xlax.xxxx
Consider binary classification problem. have the binary label output y E {0, 13 with
2()12)) (1 (T+ ex, W))
1
exp W)) 1 expl (2,)))))) W)) ) exp (u(Z, W) - log [1 + exp( W))]
Suppose we have samples (Z', y " tion. It is given, up to scaling of by
we use the negative log- ligelikkiihodd function our loss func- 1
(n( = - ΣE
1 - Σ (1 w)), (2) W) + v
n
(24)
where (=) log(1 e*) and its gradient and Hessian matrix is
(W)
V.,(W)- O vec(W)
(z0 + Σ ('('z,, W3) vec(23) and,
(25)
82 Ln (W) Hn(W)= 82 ())
"
Σ 0² d" W)) vec vec (2)))
(26)
1 with = 1/(1 +e =) E (0. and (²(2) E" =
E (0, 25
[because E +e² 2 2]. Since H, (W) a positive semi-definite matrix, our loss function in 24
is convex.
Suppose W the minimizer to the loss function
W E min C, (W)),
WESRNB(R)
(E BB A₁ Frobenius ball of some fixed radius R centered at the underlying true parameter.
where SK
AA E x11 and Bg E IR XPP and (B) is
Similar to Fan al. (2019), we need to make additional assumptions to guarantee the locally strong convexity condition.
Assumption (Classification). Apart from Assumptions 2-3, we additionally assume that
(CI) (vec(X')) ) are i.i.d gaussian vectors with mean zero and variance E, where < C.l. (C2) the Hessian matrix at the underlying true parameter ' is positive definite and there exists some Kg > KU O, such that H(W") E(H, Z Ro I. where KU C.Cui
(C3) ||" || avddM for some constant a, where dm K(P L+
24

---

Under review as a conference paper at ICLR 2021
Notice that relax (CI) into Assumption 1 but it will require more techineal details. Also, {vec(X() (==)) can be sub-gaussian random vectors instead of gaussian random vectors.
Denote dm= <(P+L++ 1).
Theorem 3 (Classification: CNN). Suppose that Assumptions 2 and Assumption hold and n 2 dm- Then, for some > 0,
2/Ku
dM +
W W0I1 -
R1
with probability 4 exp -0225c + 9dme 2exp -cddM co., where ó Op(1), c and c are some positive constants.
Denote dM 11
N+1 R2 DEE1R + RN+IP and d RN + 1 P).
Corollary (Classification: Compressed CNN). Let (W, dm) be (WTU, dM for Tucker decom- position, or WCp, d for decompoxition. Suppose that Assumptions in Theorem hold and 2 exdM. Then, for some ô > O,
2yRU
3CNdM T2
6
W W
K1
with probability 4 exp { (-0.25cn + 3cndM) - 2ex (-c,dyy du cτ}, where = Op(1), e and Cry are some positive constants, and eN defined as Theorem
We consider binary classification problem as simple illustration. In fact, the analysis frame- work can be easily extended multiclass classification problem. Here, we consider a M-class classification problem.
Because we need our intermediate output after convolution and pooling be vector of length M, instead of 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 fully- connected weights is represented as [B K.nggKKSmmm where each B is of size p1 x p2 x ...X PN- PN.
Then, for each input tensor X, our intermediate output is vector of size M, where the mth entry is represented by
output,, = (2, W...
where W EK (B A₁) is an N-th order tensor of size I1P1 X 12P2 X INPN-
For M-class classification problem, have the vector label output y (0, Essentially, each entry of comes from a different binary classification problem, with M problems in total. We can model it as
cxp(( (expl (2s, Wm))
plym (2) =
1 exp( (Zs, W Wm))
I exp((p( (ep(((2) ((Z, Wm))
= exp {ym (Z, W. log [1 exp((Z, Wm)))}
If we stack (W m m==1 into tensor W Sstack. which is N + 1-order tensor of size 4pp1 lap2 x X INPN x M. And we further introduce some natural basis vectors (em E R M M
1.
/m=1- It can be
shown that
(2 Wm)
(Z em, W Wstack),
where o is the outer product.
We can then recast this model into one with n.M samples (% vin 1 < K, S m S M). The corresponding loss function is
M Σ m=
M Σ
Cn Cn(Wstace = nM
yd (Z) W Wetack) + nM
((Z) W Wstack))
i=1
m= im
25

---

Under review as a conference paper at ICLR 2021
We the techniques in Theorem 3 to show the following corollaries for multiclass clas- sification problem.
Denote MM K +
Corollary 3 (Multiclass Classification: CNN). Under similar assumptions as in Theorem 3 suppose that ni 2 dMC. Then, for some å > O,
2/RU 11
dMC
stack W
stack || S
M
stack
with probability 1 exp { -0.25cn MdM exp Cyy are some positive constants.
-c, chic -66). where Op(1), cand
Denote d MC-TU PM).
II II Rg +E 4R, + PN41PM and d -NN+ + RI 4
N+1
(Multiclass Classification: Compressed CNN). Let (Wstack. dxx)) be (W TU,,, M (MC-TUU for Tucker decomposition, or (Wstack,cm) d'M dbvc-CP) for CP decom- position. Suppose that Assumptions in Theorem hold and n 2 exd Then, for some
Corollary
ACC 2/KU (V
W stack
-Wo Witaccell I
Ki
n
MC and ey are some positive constants, and eN is defined in Theorem 2
with probability - exp { 0.22ccn + 3ex
MC)
exx { --c,d
where = O,(1), c c5}.
Proof of Theorem 3 Denote the sets SK + B& @ A₁ : Ax 14x1/xx.xxx and BB RP XpaX-"XPN and SK = {W E SK |W][F = 1}. We further denote A = vec(W- - W*), where W is the underlying true parameter and W w Sk. and define the first-order Taylor error
(A) = LW) k. (VC, A)
Suppose W the minimizer for the loss function, i.c..
W
arg min C, (W).
WE
Denote Â vec(W- W W*) We then have
C. (WV) s 0, which can be rearranged into (A)
-VV,,(W'),)) A).
Then, for some W between W and W"
1 ('H,(WW)' s (VC, |
2
which leads to
A 2 sup
A'H, (W) < 2
sup AESIK
(VL, (W"), A)
(27)
AES2K
From Lemma and Lemma when n 2 dm we obtain that, for some d 0,
2/FE Ki
(Van) dd +
JW W v
n
with probability 1 - (
-0.25cn + [dmG - 2exp { {-eydM- - -d).
26

---

Under review as a conference paper at ICLR 2021
Now proof several lemmas to be used in Theorem 3 For simplicity of notation, denote x² vee( and z' rec(2 It holds that x' = Ugx' for S i n.
Lemma 4 (Deviation bound). Under Assumption + (3), suppose that n Z dM. then, for some 5 > 0,
((VL, A O.5 (Van + +/=² s sexp ( AES2K
P
sup
where 8 = Op(1), dm ( + L + 1), NO = C2Ou and cy some positive constant.
Proof. Let = (23, W"), and from 25
1 n
(VC, A)
M 10 (0'(11)) // A)
n1
and we can observe that ((lo((n') - = 0= 1id'(n))) -0=
- [2] A}]. 0. (ii) the independence between d'(n²) y' and (z', A). And
It implies (i) E(V (WW",, A from 6 the independence leads |||o' y'' A I 1ld (17') y eel (z A) 1l
Denote Ky = C. For any fixed A such that A 12
1,
11 A)| 11 E /
A > 11 S VKU.
This, together with [ld'()))) y' 2l S 0.25 in Lemma gives
(n') - y'(("', A)loe S 0.25
Then, we can use the Beinstein type inequality, namely Corollary 5.17 in (Vershynin 2010 that, for any fixed A with unit 1o-norm,
derive
P (WK) A
2 t = IP
Σ 16' (n')
A)
2
(28)
4t
16t
S 2cx
min
VRU
KU
Consider s-net S2K, with the cardinality of N((K,e) for the set S2K. For any A S2K, there
exists a A E S2K such that | A S e. Note that A we can further find A,, A2 E S2x such that (A1, A2) 0 and
E S4 and, from Lemma aa,
A
A, A + A It then
holds that | + A2l1E /2114 A A ||E 222 since A
A As
a result,
KVL, A = (VL, A (VC, A (VC, A2)
<
max
(VC, + V2= sup DES2X
(VL) A)
12)s)(2
which leads to
(W") A) 228)
(VL. إ,رر
sup AESaK
MAX 12iEN(2K.e)
Note that, from Lemma bb), log Moog(((K, (2K,E) < 2d log(9/s), where dM = K(P + I. + 1). Let
8 (2v2)-1 and then 2 (og(9/e) < 7. With (28) we can show that
4t
16t2
P sup AES2X
(W"), A 2t
exp -enmin min
+ Tdm J.
VKU
KU
Take = 0.25 dm/n + 0/n) where ā Op(1), and there exists some y such that
v /dm/n < holds. We can finally show that
dm V
n + 66) [/)) 2exp (-cddm--a-- - co}.
sup AES2K
(VC, A) 2 0.5
where by is some positive constant related to 7.
27

---

Under review as a conference paper at ICLR 2021
Lemma (LRSC). Suppose that 2 dm, under Assumptions 4 such that for any W S2K satisfying I WWWWll ||e S R,
there exists constant R 0,
K1
inf AES2K
H, (W)
holds with probability
1- 4exp 1-0.2220m + md
where K1 K1 KU. And K1 is defined in Lemma 8
Proof. We divide this proof into two parts.
RSC of (W)) at W W We first show that, for all A E S2K, the following holds with probability at least exp (-0.25c(KL/ n + }
A'H, 2
where ñ Ko KL 0.
Let 17² (Z', W and denote " (1²))) 2
and we can see that
HW = Σ 2 and, H(W") =H,"
Denote x = (C) Here, for simplicity, we assume {x²) Jim to be independent gaussian vectors with mean zero and covariance matrix E, where I < Σ < C. I for some 0 < Cr Cz. We will also use the notation of A for its vectorized version, veo A), ), and we consider A with unit Io-norm.
(21/2"))ll - 0.25 ky. where wi is standard gaussian Since II 1s = || AA, v (T")" "
vector and Kü = C2 C.. we can show that
a 2) EE (A, ") ls, S |, 11 S 4| E S KU,
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 incquality in Corollary 5.17 in (Vershynin 2010 for any fixed A such that A 2 1, we have
n (AA 2112 E [(A
(H)) -HWH)H(W)))) 2 = =P
マ} 21
n
1=1
S
exp
en min
Ky
With similar covering number argument as presented in Lemma 2 in our paper, we can show that,
L 12
PP sup A (H.()WW) H(W))) 2 21 AES2K
2 2exp -ennmii min
9dm )
KU
kit
where dm- = K(P+L+1)
Llet t 0.5ky. By Assumption ACI., we can obtain that, when 2 dm
inf A AESax
AWH, < $ 2exp { -0.25cn + 9dm1,
where R = Ku- > 0.
LRSC of (W) around W
Define the event (l(W", 23)1 > T sup supAesaa KA 2 and construct the functions
h h,))) = Σ d"((z', 2 and, h(W) = Eh,, (W),
28

---

Under review as a conference paper at ICLR 2021
where is some positive constant to be selected according to Lemma
8 Since the difference between
h ()) and (.)() is the indicator function, it holds that (-) 2 h.(.))
We will finish the proof of LRSC in two steps. Firstly, we show that, with high probability, he (W") is positive definite on the restricted set S2x- Secondly, we bound the difference between A h (W) A and Ahh,, (W*) A, and hence show that h (W) is locally positive definite around W This naturally leads to the LRSC of C, (W) around W
From Lemma 8 we select т, such that h(W") 2 K. Following similar arguments in the first part, we can show that for all A E S2x, the following holds with probability at least 1 2 exp { (-0. 0.25en + 9d.}.
(W") K1,
(29)
where R₁ K1 RC > O.
In the meanwhile, for any W E Sx such that I/W - W/ S R. where R can be specified later to satisfy some conditions,
n
hh (W) - ten (WV)
0" (2', W))
o" (2 W ) 1Az'' ""
=
71
(' W)) ~0" w>>) 2n
n1
1
-- 8²' (='( (3' - w w T1
where W lies between W and W", and (²) = e (1 - e²)/(1+ + E7)3 Given the event A holds,
choose R < T. we can lower bound the term,
[2 w/l 2 ( w
| A) S (T R) sup ((3,
sup AES.K.IAPSSA AIRER
A AES2K
Notice that, for all E E. the third order derivative of the function (22) upper bounded as (x)) I 1/12/. This relationship helps us further bound the term,
2 W-
W
sup A DEPAESEA ck ||ll (Z3 A)
(23) w w
2 W)I
(T R) SupA
1 A
RsupAESIX K
A
R
$
(T R)suPAESA 1 A)l - R
Hence, we can show that
R
1 -
P sup AES2X
(A' hr, (W]")] 2 1)
<P
sup A "1 i=1
T
R
By setting = RR/MR\(TT It), where ORSM
3kt /2, we can use the equation (16) in Lemma
to obtain, as long as n Z dy-
aRSM R
P sup
(W), h. (W"))AI >
< 2exp (-cHn + 9dm)
EESIK
By rearranging terms, this is equivalent to
ORSM R
P
inf AES2K
A
< sup A hn (W*)A AES2K
< 2exp (-cHn + 9d
R
demoted as the event B,
If we define the event Bg (inf A hn (W") A < k } and denote its complementary event
by B5, and from (29.. we know that IP( (B2) < 2exp 0.25cn + 9d J. It can be seen that
TP (f
CRSM R
inf A'h, < AASS
0 B5
S (B n B5) S P(B.)
29

---

Under review as a conference paper at ICLR 2021
So, if we choose R. to be sufficiently small, such that CRSM R/(rr R) S R1/2, it holds that,
P inf A (W)A = K1 AESIx
(L
aRSM
S
inf A' (W) S K1 AESEK
B5 + P(B2).
T-
This, together with Hn 2 (.). leads to conclude that, when n 2 dm, there exists some
R > O, such that for any W S2k satisfying W W ||B S R.
1 2
inf A AES2K
H' (W)
holds with probability
1 - exp (-0.25c + [dme - 2 exp { --0.25cn + 9d.l
We accomplished our proof of the LRSC of L, (W) around W
Lemma 6. For two sub-gaussian random variables, X and Y, when E(XY) = EXEY, iee. X is independent to Y, holds that
|XY|e S [|
Lemma 7.
11'()1") - -yy llv2 0.25..
Proof. Firstly, we observe that
E (expf) (0'(1") y²1))=²)
(xph 11} exp((r'--onn)) o(n'))
- -cpp)
- -()
then holds that E (exp(A (0'(n') - E[B ( )11) exp(0.1252)
and this implies that ( - vl 0.25.
Lemma 8. Under Assumption there exists universal constant 0 such that h(W") 2 K1 where Ky is a positive constant.
Proof. We first show that for any po E (0, 1), there exists a constant such that
P((W",, 2z)
sup (A, (A, 2 po-
A EE5K
We would separately show that
Po + 2
Po P0+1
P((W", (,,22)112 2>);"")>cvvl >
and, PP sup |( $ 2
ACSaK
2
denoted by event Dj
denoted
for some positive constants C₁ and C2. Using the relationship P(D1 n D2) = P(D:) + + P(D2)
D 2 +(D:)+ P(D2) - 1, it follows naturally that
+
Pu +
P([(W", 23)
sup
(A. (A,')))
1 Po:
(30)
A AESIK
where r = c1/02.
Since x' is gaussian vector with mean zero and covariance E, 2' = of is zero-mean gaussian vector with covariance given EUG, and (W",2') (vec(W"), ),"" x²) also follows normal
distribution with mean zero and variance (also its Sab-Gausiinn norm) upper bounded by ky k [|
where Ky C.Cu-
30

---

Under review as a conference paper at ICLR 2021
Since from Assumption C2), | 2 avdn, take e₁ be sufficiently small such that \W K KU W"
+1
P(D:) P
P([2
Kea
2
where a is gaussian variable with variance upper bounded by 1.
Then, also observe that, for any fixed A S2K, (A,z') is gaussian variable with zero mean and variance upper bounded by kt. We can use the concentration inequality for gaussian random variable establish that
t²
(I x')1 2 t) & 2 exxp(-
KU
for all t E R. We can further use the union bound to show that
12
P
sup AES
(A, 21) 2 2 2 expp(
+ 7dm).
Let t = d2 for some positive constant C2 TRu. We can choose large enough such that
KA x 2 02V dm 1
Po
sup
AES2X
2
The probability at (30g hence shown.
Now, we will take look the matrix h(W") and show that it is positive definite. Same in we denote the event A {|("", 2²)| SSpAASSIN |(A, [}. and its complement by
Lemma 5
A then
A'h(W")
E
((23,
E
(1Z), A)
E
("(1", W
n
A'H(W")
E
(((
n
Kg
(0' W))
z4y4
E
Σ
IA
IV
V3KKU
K0
po):
4
where (i) follows from Assumption C1), And since (A, x²) ) is a gaussian variable with mean zero and variance bounded by kv. fourth moment is bounded by 3xg. Also, by (²(2) (0, 0.25) for
all E IR. (ii) can be shown.
Here, we can take Po to small enough such that / (1 - Po) S 0.5rg holds. follows that
A d'h(W") A > K1;
with K1 = 0.5rg. We hence accomplished the proof the lemma.
A.5 ADDITIONAL. EXPERIMENTS
A.5.1 MORE EXPERIMENTS FOR THEORETICAL RESULTS
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 dime-dependent inputs, we generate a sequence of vectors (x') with size Rd from a stationary VAR(1) process, where d = 245 192. The VAR(1) process has transition matrix with spectral norm less than
31

---

Under review as a conference paper at ICLR 2021
11 Network design
(2) Efficient number of kernels (R-8)
K=8
K=24
"Ilm - Mill
K-16
K-32
1000
2000
3000
1000
Figure 7: Additional experiments for efficient number of kemelss
I to ensure stationarity, and 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.c. n + 200. We then reshape {x'} } into a sequence of tensors of shape (7, 5, 7) or (8, 8, 3), which the time-dependent inputs for experiments under S1/S2 S3/S4.
Next, we conduct extra experiments for efficient number of kernels for a CP block design. This study uses 32 x 32 imputs with 16 channels, and we set stride to I and pooling sizes to (5, 5). We generate the orthonormal factor matrices {H 1 S I 4), where ( is of size R R. H2) is of size RSXR (3) is of size 116xR and H is of size R RKx where R. 8 and K {8, 16, 24, 32).
If we denote the orthonormal column vectors of (6) by 12,)) where 1 S S and 1 < s 4, the stacked kernel tensor A can then be generated as A Σn= (1) h h.. hr And it can be seen that has a CP rank of R = 8. We split the stacked kernel tensor A along the kernel dimension to obtain {AA,1 1 < k < K} and generate the corresponding fully-connected weight tensors B & k S K} with standard normal entries. The parameter tensor W is hence obtained, and we further normalize it to have unit Frobenius errors between different Ks. The block structure in Figure 1) is employed to train the network, and it is equivalent to the bottleneck structure with CP decomposition on A; see Kossaifi et al. (020b).. 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-S. From Figure 2), the estimation error increases as K is larger, and the difference more pronounced when training size is small.
to ensure the comparability of estimation
A.5.2 ABLATION STUDIES ON MORE BLOCK DESIGNS
In this section, present the results from the studies of K/R ratios 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 ResNeXt and Shufflenet.
In Figure g we represent the bottleneck block structure of ResNeXt consisting of 3 layers: 1 x convolution layer,
group convolution layer followed by another 1 x I convolution layer. During group convolution phase, there are parallel paths, each has bottleneck size of r, which
(1)
(2)
CODV
K
XX conV
Lotal paths; and r-g
cOnY
CORY
cony
greup
X cony
1 X DOnY
X 1 cony
K
1 conv
K
Figure 8: Equivalent ResNext building blocks. Both (1) and (2) represent a block of ResNeXt with
cardinality g, with R r g. Here, the expansion ratio K/ R, and takes values of 1,2 and
32

---

Under review as a conference paper at ICLR 2021
Channel Split
Bottleneck
K
1 x 1 Conv
1 X conv
3 x 3 DWConv
x DWconv
Conv
R
1 1 1 conv
K
Concat
Channel Shuffle
Figure 9: A basic block of Shufflenet v2, with its bottleneck structure depict explicitly. Here, the expansion ratio = K/R, and takes values of 1,2 and 4.
Table 3: Test accuracy(%) (%) of ResNeXt and Shufflenet on SVNH.
ResNeXt
#FLOPs
#Params
Shufflenet
#FLOPs
#Params
96.20
0.05GMac
1.45M
95.93
0.05GMac
1.33M
96.25
0.07GMae
2.13M
96.08
0.08GMac
1.67M
96.20
0.14GMac
4.44M
96.03
0.16GMac
3.84M
is also the rank of the output channel in each individual path; see also Figure 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 be t K/R.
In Figure we represent the bottleneck block structure of Shufflenet. It consists of 3 layers: a I 1x convolution layer, 3 depthwise convolution layer followed by another x convolution layer. So, the only difference between this block structure and that in ResNet (He et al. 2016) is that the full x convolution is replaced by the depthwise separable convolution. It follows that the expansion ratio is = K/R.
We conducted the experiments on the SVNH dataset and take 2, 4, since 2 or t 4 in particular, is commonly used in practice. We followed the design of ResNeXt-50 (see Table 1 in Xie
al. ( and Shufflenet v2-50 (see Appendix Table 2 in Ma 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 "conv conv""" respectively. And K = f R is taken according to different values of t. The implementations are similar to before. Following the practice in He et al. (016)) we adopt batch normalization(BN) (Toffe & 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
We can see that, when t = 1, the test accuracy comparable to when of parameters are reduced by a lot. In fact, the ratio of number of parameters at a single bottleneck block for of parameters will increase dramatically when we have deeper CNN, for instance, ResNeXtt1011. Hence, it is always recommended to keep = 1 to achieve more parameter efficiency without sacrificing the test accuracy.
or 4, and the number
1, 2 and is roughly 1 : 4, for both networks. This implies that the number
33


Reviews:
[{"review_id": "XHAcUBUZ7lg", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe writing is generally clear. The use of tensors give a very compact representation of an CNN, however tensor notations and indices can quickly become complicated in higher dimensions. The convergence results are a nice contribution to the growing literature on neural networks' theoretical analysis. In particular, the analysis of various tensor decompositions help guide the design of blocks in CNNs. \n\nAlthough the results are interesting, I feel that important aspects of CNNs were not analyzed nor discussed in this paper. Here are some of my comments and questions.\n  \nOne of the main uses of CNNs is to perform classification where there is a softmax layer after the fully connected layer. Hence model (2) does not reflect what is done in practice and $\\boldsymbol{y}$ should be a vector of probabilities. In fact I think the authors did classification on CIFAR-10 and SVHN in the numerical experiments (although it is not mentioned) using residual networks and not the model in (2). Also, why do you add sub-Gaussian errors to CNN outputs as in (2)?\n\nIn the experiments, the authors used ReLU instead of linear activation, and there is batch normalization between convolution layers. In addition, there are residual connections in the ResNet (block) architecture. All these factors that affect convergence rates were not considered in the theoretical analysis. Although I understand that these issues were omitted to simplify the proofs, I feel that there should be consistency between the theory and implementation parts. Hence Table 2 and Figure 3 do not necessarily provide empirical evidence to the theoretical results derived, as these networks have different architectures than the ones considered in Section 2. Consequently, the results hold true for a special type of CNN and it is not clear to me whether these results will still hold for CNNs used in practice (with non-linear activation, batch norm, max pooling etc.), or when the true weight tensor does not have the same tensor product structure as the learned weight tensor.\n\nEquation (5) seems to assume that you can optimize the weights for the full connected layer and the convolution kernel perfectly. However in the numerical experiments and in practice, stochastic gradient descent with momentum is used for training and this will contribute an error term to the right hand side of Theorem 1.\n\nIn Theorem 1, can you give more explanation as to the meaning of model complexity $d_{\\mathcal{M}}$? Is this the effective number of parameters? Also what are $P$ and $L$ here? In addition, is $d_{\\mathcal{M}}$ always larger than $\\delta$? As there is no restriction on $\\delta$, it is possible that $\\delta$ is much larger than $d_{\\mathcal{M}}$. The same comment also applies to Theorem 2.\n\nSome other comments:\n1.  In (2), state that $1\\leq i\\leq n$\n2.  In the paragraph after Assumption 1, what do you mean by $\\lambda_{\\mathrm{min}}(f_X(\\theta))$ as $f_X(\\theta)$ is not a matrix.\n3.  On Page 5 the 2nd line after the first display, mode-$3$ multiplication between two tensors does not seem to be introduced in the notations\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KDaHrdGBxiK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper formulates CNNs with high-order inputs into an explicit Tucker model, and provides sample complexity analysis to CNNs as well as compressed CNNs via tensor decomposition. Experiments support their theoretical results. Sample complexity analysis of CNNs and compressed CNNs is an interesting topic. This paper is well written and is easy to follow.\n\nCons: \n\n1. Technical novelty is limited. It has been well understood that CNNs can be formulated as a tensor model, see Lebedev et al. (2015); Hayashi et al. (2019);  Kossaifi et al. (2019). By assuming a realization model, the sample complexity analysis of CNNs and compressed CNNs was transferred to the sample complexity analysis of tensor regression model and low-rank tensor regression model. The latter analysis is not new given a rich literature on this topic, see e.g., Bahadori et al. (2014); Yu and Liu (2016); Kossaifi et al. (2020). \n\nLebedev, V., et al. \"Speeding-up convolutional neural networks using fine-tuned CP-decomposition.\" 3rd International Conference on Learning Representations, ICLR 2015-Conference Track Proceedings. 2015.\n\nHayashi, Kohei, et al. \"Exploring Unexplored Tensor Network Decompositions for Convolutional Neural Networks.\" Advances in Neural Information Processing Systems. 2019.\n\nKossaifi, Jean, et al. \"T-net: Parametrizing fully convolutional nets with a single high-order tensor.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.\n\nBahadori, Mohammad Taha, Qi Rose Yu, and Yan Liu. \"Fast multivariate spatio-temporal analysis via low rank tensor learning.\" Advances in neural information processing systems. 2014.\n\nYu, Rose, and Yan Liu. \"Learning from multiway data: Simple and efficient tensor regression.\" International Conference on Machine Learning. 2016.\n\nKossaifi, Jean, et al. \"Tensor regression networks.\" Journal of Machine Learning Research 21.123 (2020): 1-21.\n\n\n2. The sample complexity analysis is for the global minimizer from a non-convex optimization, see (5).  It would be more interesting to study the sample complexity analysis for the estimator from some polynomial algorithm.  \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FSbC6WekRpZ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThis 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\n\nPros:\n1.This work provides a theoretical analysis for higher-order CNNs via analyzing its Tucker formulation using tensor methods.\n2.The proposed theoretical analysis can be applied to compressed designs of CNNs.\n3.This work also provides numerical experiments to verify its theoretical claims.\n\nCons:\n1.This work lacks comparisons with many important and relevant works (e.g. [1-5]), which also formulate CNNs or higher-order CNNs using various tensor decomposition forms. Many of the works also provide theoretical analysis (e.g. generalization bound in [5]) for the proposed formulations. It would be nice for the authors to show how their formulation is different from the existing ones and what is novel about the proposed formulation. Since [3] and [4] both have formulations of higher-order CNNs/CNNs using Tucker decomposition, it seems to me that the current formulation proposed in this work lacks novelty.\n\n2.The current presentation of this work could be much more improved via a) providing more intuitions for its theoretical analysis, b) putting more connections between the theoretical analysis and empirical experiments, and c) adopting better notations (e.g. definitions of tensor operations rather than using elementwise notations) to make the theoretical analysis cleaner and clearer.\n\n3.The finding discovered in this work via its theoretical analysis lacks sufficient experimental supports: the finding is only shown using one particular architecture design and the room for potential improvements is very limited. For example, in Table 2, the test accuracy of even the smallest model is already very close to the state-of-the-art results on these datasets, which leaves very limited room for potential improvements of test accuracies by simply increasing the expansion ratio. \n\n4.As mentioned above, because a) the proposed formulation of higher-order CNNs lack proper comparisons with existing works and has limited novelty and b) the finding from theoretical analysis lack sufficient experimental supports, the contribution of this paper is limited and it would be nice for the authors to provide more justifications for its novelty and better designs of experiments to convey the message.\n\n[1] Kossaifi, Jean, et al. \"Tensor contraction layers for parsimonious deep nets.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops. 2017.\n\n[2] Kossaifi, Jean, et al. \"T-net: Parametrizing fully convolutional nets with a single high-order tensor.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.\n\n[3] Su, Jiahao, et al. \"Tensorial neural networks: Generalization of neural networks and application to model compression.\" arXiv preprint arXiv:1805.10352 (2018).\n\n[4] Kossaifi, Jean, et al. \"Tensor regression networks.\" Journal of Machine Learning Research 21.123 (2020): 1-21.\n\n[5] Li, Jingling, et al. \"Understanding Generalization in Deep Learning via Tensor Methods.\" arXiv preprint arXiv:2001.05070 (2020).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a theoretical analysis of CNN compression using tensor methods. None of the three reviewers have strong opinion; there scores are 5, 6, and 5.

The attempt to understand the mechanism of how tensor decomposition compresses CNNs is meaningful and interesting. However, the main contribution of this work is not sufficiently distinct compared to the existing approaches and the analysis and proof is conduected only for simplified models as mentioned by reviewers. The practical benefit of this paper is not clear and the experimental validation is weak because only a small number of model architectures were tested on a few small datasets.

This is a borderline paper. However, this paper needs to extend its contribution by performing more comprehensive analysis for general CNNs. 
Decision: Reject