# convolutional_neural_networks_with_lowrank_regularization__6af206a9.pdf

Published as a conference paper at ICLR 2016

CONVOLUTIONAL NEURAL NETWORKS WITH LOWRANK REGULARIZATION

Cheng Tai1, Tong Xiao2, Yi Zhang3, Xiaogang Wang2, Weinan E1

1The Program in Applied and Computational Mathematics, Princeton University 2Department of Electronic Engineering, The Chinese University of Hong Kong 3Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor {chengt,weinan}@math.princeton.edu; yeezhang@umich.edu {xiaotong,xgwang}@ee.cuhk.edu.hk

Large CNNs have delivered impressive performance in various computer vision applications. But the storage and computation requirements make it problematic for deploying these models on mobile devices. Recently, tensor decompositions have been used for speeding up CNNs. In this paper, we further develop the tensor decomposition technique. We propose a new algorithm for computing the low-rank tensor decomposition for removing the redundancy in the convolution kernels. The algorithm ﬁnds the exact global optimizer of the decomposition and is more effective than iterative methods. Based on the decomposition, we further propose a new method for training low-rank constrained CNNs from scratch. Interestingly, while achieving a signiﬁcant speedup, sometimes the lowrank constrained CNNs delivers signiﬁcantly better performance than their nonconstrained counterparts. On the CIFAR-10 dataset, the proposed low-rank NIN model achieves 91.31% accuracy (without data augmentation), which also improves upon state-of-the-art result. We evaluated the proposed method on CIFAR10 and ILSVRC12 datasets for a variety of modern CNNs, including Alex Net, NIN, VGG and Google Net with success. For example, the forward time of VGG16 is reduced by half while the performance is still comparable. Empirical success suggests that low-rank tensor decompositions can be a very useful tool for speeding up large CNNs.

1 INTRODUCTION

Over the course of three years, CNNs have revolutionized computer vision, setting new performance standards in many important applications, see e.g., Krizhevsky et al. (2012); Farabet et al. (2013); Long et al. (2014). The breakthrough has been made possible by the abundance of training data, the deployment of new computational hardware (most notably, GPUs and CPU clusters) and large models. These models typically require a huge number of parameters (107 109) to achieve stateof-the-art performance, and may take weeks to train even with high-end GPUs. On the other hand, there is a growing interest in deploying CNNs to low-end mobile devices. On such processors, the computational cost of applying the model becomes problematic, let alone training one, especially when real-time operation is needed. Storage of millions of parameters also complicates the deployment. Modern CNNs would ﬁnd many more applications if both the computational cost and the storage requirement could be signiﬁcantly reduced.

There are only a few recent works for speeding up CNNs. Denton et al. (2014) proposed some low-rank approximation and clustering schemes for the convolutional kernels. They achieved 2x speedup for a single convolutional layer with 1% drop in classiﬁcation accuracy. Jaderberg et al. (2014) suggested using different tensor decomposition schemes, reporting a 4.5x speedup with 1% drop in accuracy in a text recognition application. Lebedev et al. (2014) further explored the use of CP decomposition to approximate the convolutional kernels. Vanhoucke et al. (2011) showed that using 8-bit quantization of the parameters can result in signiﬁcant speedup with minimal loss of accuracy. This method can be used in conjunction with low-rank approximations to achieve further speedup.

ar Xiv:1511.06067v3 [cs.LG] 14 Feb 2016

Published as a conference paper at ICLR 2016

As convolution operations constitute the bulk of all computations in CNNs, simplifying the convolution layer would have a direct impact on the overall speedup. The convolution kernels in a typical CNN is a 4D tensor. The key observation is that there might be a signiﬁcant amount of redundancy in the tensor. Ideas based on tensor decomposition seem to be a particularly promising way to remove the redundancy as suggested by some previous works.

In this paper, we further develop the tensor decomposition idea. Our method is based on Jaderberg et al. (2014), but has several signiﬁcant improvements. The contributions are summarized as follows:

A new algorithm for computing the low-rank tensor decomposition. Low-rank tensor decompositions are non-convex problems and difﬁcult to compute in general, Jaderberg et al. (2014) use iterative schemes to get an approximate local solution. But we ﬁnd that the particular form of low-rank decomposition in (Jaderberg et al., 2014) has an exact closed form solution which is the global optimum. Hence we obtain the best data-independent approximation. Furthermore, computing the exact solution is much more effective than iterative schemes. As the tensor decomposition is the most important step in approximating CNNs, being able to obtain an exact solution efﬁciently thus provides great advantages.

A new method for training low-rank constrained CNNs from scratch. Most previous works only focus on improving testing time computation cost. This is achieved by approximating and ﬁne-tuning a pre-trained network. Based on the low-rank tensor decomposition, we ﬁnd that the convolutional kernels can be parameterized in a way that naturally enforces the lowrank constraint. Networks parameterized in this low-rank constrained manner have more layers than their non-constrained counterparts. While it is widely observed that deeper networks are harder to train, we are able to train very deep low-rank constrained CNNs with more than 30 layers with the help of a recent training technique called batch normalization Ioffe & Szegedy (2015).

Evaluation on large networks. Previous experiments in Jaderberg et al. (2014) and Denton et al. (2014) give some promises of the effectiveness of low-rank approximations. But these methods have not been tested extensively for large models and generic datasets. Moreover, as iterative methods are used to ﬁnd the approximation, bad local minima may hurt performance. In this paper, we test the proposed method for various state-of-the-art CNN models, including NIN (Lin et al., 2013), Alex Net (Krizhevsky et al., 2012), VGG (Simonyan & Zisserman, 2014) and Google Net (Szegedy et al., 2014). The datasets used include CIFAR10 and ILSVRC12. We achieved signiﬁcant speedups for these models with comparable or even better performance. Success on a variety of CNN models give strong evidence that low-rank tensor decomposition can be a very useful tool for simplifying and improving deep CNNs.

Our numerical experiments show that signiﬁcant speedup can be achieved with minimal loss of performance, which is consistent with previously reported results. Surprisingly, while all previous efforts report a slight decrease or no change in performance, we found a signiﬁcant increase of classiﬁcation accuracy in some cases. In particular, on the CIFAR-10 dataset, we achieve 91.31% classiﬁcation accuracy (without data augmentation) with the low-rank NIN model, which improves upon not only the original NIN but also upon state-of-the-art results on this dataset. We are not aware of signiﬁcant improvements with low-rank approximations being reported in the previous literature.

The rest of the paper is organized as follows. We discuss some related work in section 2. We then introduce our decomposition scheme in section 3. Results with typical networks including Alex Net, NIN, VGG and Google Net on CIFAR10 and ILSVRC12 datasets are reported in section 4. We conclude with the summary and discussion in Section 5.

2 RELATED WORK

Using low-rank ﬁlters to accelerate convolution has a long history. Classic examples include high dimensional DCT and wavelet systems constructed from 1D wavelets using tensor products. In the context of dictionary learning, learning separable 1D ﬁlters was suggested by Rigamonti et al. (2013).

Published as a conference paper at ICLR 2016

More speciﬁc to CNNs, there are two works that are most related to ours: Jaderberg et al. (2014); Lebedev et al. (2014). For Jaderberg et al. (2014), in addition to the improvements summarized in the previous section, there is another difference in the approximation stage. In Jaderberg et al. (2014), the network is approximated layer by layer. After one layer is approximated by the lowrank ﬁlters, the parameters of that layer are ﬁxed, and the layers above are ﬁne-tuned based on a reconstruction error criterion. Our scheme ﬁne-tunes the entire network simultaneously using a discriminative criterion. While Jaderberg et al. (2014) reported that discriminative ﬁne-tuning was inefﬁcient for their scheme, we found that it works very well in our case.

In Lebedev et al. (2014), CP decomposition of the kernel tensors is proposed. Lebedev et al. (2014) used non-linear least squares to compute the CP decomposition. It is also based on the tensor decomposition idea, but our decomposition is based on a different scheme and has some numerical advantages. For the CP decomposition, ﬁnding the best low-rank approximation is an ill-posed problem, and the best rank-K approximation may not exist in the general case, regardless the choice of norm (de Silva & Lim, 2008). But for the proposed scheme, the decomposition always exists, and we have an exact closed form solution for the decomposition. In principle, both the CP decomposition scheme and the proposed scheme can be used to train CNNs from scratch. In the CP decomposition, one convolutional layer is replaced with four convolutional layers. Although the effective depth of the network remains the same, it makes optimization much harder as the gradients of the inserted layers are prone to explosion. Because of this, application of this scheme to larger and deeper models is still problematic due to numerical issues.

Lastly, different from both, we consider more and much larger models, which is more challenging. Thus our results provide strong evidence that low-rank approximations can be applicable to a variety of state-of-the-art models.

In line with the method in Jaderberg et al. (2014), the proposed tensor decomposition scheme is based on a conceptually simple idea: replace the 4D convolutional kernel with two consecutive kernels with a lower rank. In the following, we introduce the details of the decomposition and the algorithms of using the decomposition to approximate a pre-trained network and to train a new one.

3.1 APPROXIMATION OF A PRE-TRAINED CNN

Formally, a convolutional kernel in a CNN is a 4D tensor W RN d d C, where N, C are the numbers of the output and input feature maps respectively and d is the spatial kernel size. We also view W as an 3D ﬁlter array and use notation Wn Rd d C to represent the n-th ﬁlter. Let Z RX Y C be the input feature map. The output feature map F = (F1, , FN) is deﬁned as

y =1 Zc(x , y )Wc n(x x , y y ),

where the superscript is the index of the channels.

The goal is to ﬁnd an approximation W of W that facilitates more efﬁcient computation while maintaining the classiﬁcation accuracy of the CNN. We propose the following scheme:

k=1 Hk n(Vc k)T , (1)

where K is a hyper-parameter controlling the rank, H RN 1 d K is the horizontal ﬁlter, V RK d 1 C is the vertical ﬁlter (we have slightly abused the notations to make them concise, Hk n and Vc k are both vectors in Rd). Both H and V are learnable parameters.

With this form, the convolution becomes:

k=1 Hk n(Vc k)T Zc =

c=1 Vc k Zc !

Published as a conference paper at ICLR 2016

Figure 1: (a) Filters in the ﬁrst layer in Alex Net. (b) Low-rank approximation using the proposed schemes with K = 8, corresponding to 3.67 speedup for this layer. Note the low-rank approximation captures most of the information, including the directionality of the original ﬁlters. (c) Low-rank ﬁlters trained from scratch with K = 8.

The intuition behind this approximation scheme is to exploit the redundancy that exist both in the spatial dimensions and across channels. Note the convolutions in the above equation are all one dimensional in space.

We can estimate the reduction in computation with this scheme. Direct convolution by deﬁnition requires O(d2NCXY ) operations. In the above scheme, the computational cost associated with the vertical ﬁlters is O(d KCXY ) and with horizontal ﬁlters O(d NKXY ), giving a total computational cost of O(d K(N + C)XY ). Acceleration can be achieved if we choose K < d NC

N+C . In principle, if C N, which is typical in the ﬁrst layer of a CNN, the acceleration is about d times.

We learn the approximating parameters H and V by a two-step strategy. In the ﬁrst step, we approximate the convolution kernel W in each layer by minimizing W W F (index of the layers are omitted for notation simplicity). Note that this step can be done in parallel as there is no inter-layer dependence. Then we ﬁne-tune the whole CNN based on the discriminative criterion of restoring classiﬁcation accuracy.

3.2 ALGORITHM

Based on the approximation criterion introduced in the previous section, the objective function to be minimized is:

(P1) E1(H, V) := X

k=1 Hk n(Vc k)T 2 F . (3)

This minimization problem has a closed form solution. This is summarized in the following theorem and the proof can be found in the appendix. The theorem gives us an efﬁcient algorithm for computing the exact decomposition. Theorem 1. Deﬁne the following bijection that maps a tensor to a matrix T : RC d d N 7 RCd d N, tensor element (i1, i2, i3, i4) maps to (j1, j2), where

j1 = (i1 1)d + i2, j2 = (i4 1)d + i3.

Deﬁne W := T [W]. Let W = UDQT be the Singular Value Decomposition (SVD) of W. Let

ˆVc k(j) = U(c 1)d+j,k p

Dk,k ˆHk n(j) = Q(n 1)d+j,k p

then ( ˆH, ˆV) is a solution to (P1).

Because of this Theorem, we call the ﬁlters (H, V) low-rank constrained ﬁlters. Note that the solution to (P1) is not unique. Indeed, if (H, V) is a solution, then (αH, 1/αV) is also a solution for

Published as a conference paper at ICLR 2016

Figure 2: The proposed parametrization for low-rank regularization. Left: The original convolutional layer. Right: low-rank constraint convolutional layer with rank-K.

any α = 0, but these solutions are equivalent in our application. An illustration of the closed-form approximation is shown in Figure 1.

A different criterion which uses the data distribution is proposed in Denton et al. (2014). But minimization for this criterion is NP-hard. The proof is also included in the appendix.

The algorithm provided by the above theorem is extremely fast. In our experiments, it completes in less than 1 second for most modern CNNs (Alex Net, VGG, Goog Le Net), as they have small convolutional kernels. Iterative algorithms (Denton et al. (2014); Jaderberg et al. (2014) take much longer, especially with the data-dependent criterion. In addition, iterative algorithms often lead to bad local minimum, which leads to inferior performance even after ﬁne-tuning. The proposed algorithm solves this issue, as it directly provides the global minimum, which is the best dataindependent approximation. Numerical demonstrations are given in section 4.

3.3 TRAINING LOW-RANK CONSTRAINED CNN FROM SCRATCH

Using the above scheme to train a new CNN from scratch is conceptually straightforward. Simply parametrize the convolutional to be of the form in (1), and the rest is not very different from training a non-constrained CNN. Here H and V are the trainable parameters. As each convolutional layer is parametrized as the composition of two convolutional layers, the resulting CNN has more layers than the original one. Although the effective depth of the new CNN is not increased, the additional layers make numerical optimization much more challenging due to exploding and vanishing gradients, especially for large networks. To handle this problem, we use a recent technique called Batch Normalization (BN) (Ioffe & Szegedy, 2015). BN transform normalizes the activations of the internal hidden units, hence it can be an effective way to deal with the exploding or vanishing gradients. It is reported in Ioffe & Szegedy (2015) that deeper networks can be trained with BN successfully, and larger learning rates can be used. Empirically, we ﬁnd BN effective in learning the low-rank constrained networks. An illustration of transformation of a original convolutional layer into a low-rank constraint one is in Figure 2. More details can be found in the numerical experiments section.

4 EXPERIMENTS

In this section, we evaluate the proposed scheme on the CIFAR-10 and the ILSVRC12 datasets with several CNN models.

4.1 CIFAR-10

CIFAR-10 dataset is small by today s standard, but it is a good testbed for new ideas. We deploy two models as baseline models; one is a customized CNN and the other is the NIN model. We compare their performance with their corresponding low-rank constrained versions. All models on this dataset are learned from scratch.

Published as a conference paper at ICLR 2016

Table 1: Network structure for CIFAR-10

Layer name CNN Low-rank CNN conv1 5 5 192 K1 = 12 conv2 5 5 128 K2 = 64 conv3 5 5 256 K3 = 128 fc1 2304 512 fc2 512 10

Layer name NIN Low-rank NIN conv1 5 5 192 K1 = 10 conv2,3 1 1 160, 1 1 96 conv4 5 5 192 K2 = 51 conv5,6 1 1 192, 1 1 192 conv7 3 3 192 conv8,9 1 1 192, 1 1 10

Table 2: CIFAR-10 performance

METHOD WITHOUT AUG. WITH AUG. SPEEDUP CNN (ours) 15.12% 12.62% 1 Low-rank CNN (ours) 14.50% 13.10% 2.9 CNN + Dropout (ours) 13.90% 12.29% 0.96 Low-rank CNN + Dropout (ours) 13.81% 11.41% 2.8 NIN (ours) 10.12% 8.19% 1 Low-rank NIN (ours) 8.69% 6.98% 1.5 CNN + Maxout (Goodfellow et al., 2013) 11.68% 9.38% - NIN (Lin et al., 2013) 10.41% 8.81% - CNN (Srivastava et al., 2014) 12.61% - - NIN + APL units (Agostinelli et al., 2014) 9.59% 7.51% -

The conﬁgurations of the baseline models and their low-rank counterparts are outlined in Table 1. We substitute every single convolutional layer in the baseline models with two convolutional layers with parameter K introduced in the previous section. All other speciﬁcations of the network pairs are the same. Rectiﬁed Linear Unit (Re LU) is applied to every layer except for the last one. Our implementation of the NIN model is slightly different from the one introduced in Lin et al. (2013). We did not replace the 3 3 convolutional layer because this layer only constitutes a small fraction of the total execution time. Hence the efﬁciency gain of factorizing this layer is small.

The networks are trained with back propagation to optimize the multinomial logistic regression objective. The batch size is 100. The learning learning rate is initially set to 0.01 and decreases by a factor of 10 every time the validation error stops decreasing. Some models have dropout units with probability 0.25 inserted after every Re LU. For exact speciﬁcations of the parameters, the reader may check https://github.com/chengtaipu/lowrankcnn. We evaluated the performance of the models both with and without data augmentation. With data augmentation, the images are ﬂipped horizontally with probability 0.5 and translated in both directions by at most 1 pixel. Otherwise, we only subtract the mean of the images and normalize each channel. The results are listed in Table 2.

The performance of the low-rank constrained versions of both networks are better than the baseline networks, with and without data augmentation. Notably, the low-rank NIN model outperforms the baseline NIN model by more than 1%. And as far as we know, this is also better than previously published results.

We then study how the empirical performance and speedup change as we vary the rank K. We choose the CNN+Dropout as baseline model with data augmentation described above. The results are listed in Table 3.

The number of parameters in the network can be reduced by a large factor, especially for the second and third layers. Up to 7 speedup for a speciﬁc layer and 2-3 speedup for the whole network can be achieved. In practice, it is difﬁcult for the speedup to match the theoretical gains based on the number of operations, which is roughly proportional to the reduction of parameters. The actual gain also depends on the software and hardware optimization strategies of convolutions. Our results in Table 3 are based on Nvidia Titan GPUs and Torch 7 with cudnn backend.

Interestingly, even with signiﬁcant reductions in the number of parameters, the performance does not decrease much. Most of the networks listed in Table 3 even outperform the baseline model.

Published as a conference paper at ICLR 2016

Table 3: Speedup and performance change. Performance change is relative to the baseline CNN+Dropout model with accuracy 87.71%.

LAYER K1 K2 K3 ACCURACY CHANGE SPEEDUP (LAYER) SPEEDUP (NET) REDUCTIONS (WEIGHTS)

First 4 64 256 +0.69% 1.20 2.91 3.5 8 64 256 +0.85% 1.13 2.87 1.8 12 64 256 +0.94% 1.05 2.85 1.2

12 8 256 -0.02% 7.13 3.21 47.5 12 16 256 +0.50% 6.76 3.21 23.8 12 32 256 +0.89% 6.13 3.13 12.0 12 64 256 +0.94% 3.72 2.86 6.0 12 128 256 +1.32% 2.38 2.58 3.0 12 256 256 +1.40% 1.25 1.92 1.5

12 64 8 -2.25% 6.98 3.11 52.5 12 64 16 +0.21% 6.89 3.11 26.4 12 64 32 +0.19% 5.82 3.10 13.3 12 64 64 +0.19% 3.74 2.96 6.7 12 64 128 +0.94% 2.38 2.86 3.3 12 64 256 +1.75% 1.31 2.30 1.7

Applying the low-rank constraints for all convolutional layers, the total number of parameters in the convolutional layers can be reduced by a large factor without degrading much performance. For example, with K1 = 12, K2 = 16 and K3 = 32, the parameters in the convolutional kernels are reduced by 91% and the relative performance is +0.25%.

Nevertheless, the parameters in the fully connected layers still occupy a large fraction. This limits the overall compression ability of the low-rank constraint. There are some very recent works focusing on reducing the parameters in the fully connected layers (Novikov et al., 2015), combining these techniques with the proposed scheme will be explored in future research.

4.2 ILSVRC12

ILSVRC12 (Russakovsky et al., 2015) is a well-known large-scale benchmark dataset for image classiﬁcation. We adopt three famous CNN models, Alex Net (Krizhevsky et al., 2012) (Caffe Net (Jia et al., 2014) as an variant), VGG-16 (Simonyan & Zisserman, 2014), and Goog Le Net (Szegedy et al., 2014) (BN-Inception (Ioffe & Szegedy, 2015) as an variant) as our baselines. The Caffe Net and VGG-16 are directly downloaded from Caffe s model zoo and then ﬁne-tuned on the training set until convergence, while the BN-Inception model is trained from scratch by ourselves.

The introduced low-rank decomposition is applied to each convolutional layer that has kernel size greater than 1 1. Input images are ﬁrst warped to 256 256 and then cropped to 227 227 or 224 224 for different models. We use the single center crop during the testing stage, and evaluate the performance by the top-5 accuracy on the validation set. Detailed training parameters are available at https://github.com/chengtaipu/lowrankcnn.

As before, the hyper-parameter K controls the trade-off between the speedup factor and the classiﬁcation performance of the low-rank models. Therefore, we ﬁrst study its effect for each layer, and then use the information to conﬁgure the whole low-rank model for better overall performance. We decompose a speciﬁc layer with a different K each time, while keeping the parameters of all the other layers ﬁxed. The performance after ﬁne-tuning with respect to the theoretical layer speedup is demonstrated in Figure 3. In general, we choose for each layer the value of K that most accelerates the forward computation while does not hurt the performance signiﬁcantly (< 1%). A more automatic way for choosing K is based on Eigengap, such that the ﬁrst K eigenvectors account for 95% of the variations. This is similar to choosing the number of principal components in PCA. The detailed low-rank model structures are listed in Table 4.

The proposed closed form solution provides the optimal data-independent initialization to the lowrank model. As indicated in Figure 4, there is a performance gap between the low-rank models and

Published as a conference paper at ICLR 2016

2 4 8 16 Theoretical layer forward speedup

Val. top-5 accuracy gain

conv1 conv2 conv3 conv4 conv5

Figure 3: The performance w.r.t. the theoretical layer speedup. Only the conv1-conv5 layers of the Alex Net are shown.

0 5 10 15 20 25 The training epoch

Val. top-5 accuracy gain

Alex Net approx VGG-16 approx Goog Le Net approx Alex Net from scratch

Figure 4: The performance w.r.t. the ﬁne-tuning epoch when using the proposed closed form solution as initialization.

Table 4: Low-rank models for ILSVRC12. For VGG-16, each convolution module contains two or three sub-convolutional layers. For Goog Le Net, each inception module contains one 3 3 and two consecutive 3 3 convolutional layers. Their corresponding Ks are shown in a cell for brevity.

(a) Alex Net

Layer K conv1 8 conv2 40 conv3 60 conv4 100 conv5 200

Layer K conv1 5, 24 conv2 48, 48 conv3 64, 128, 160 conv4 192, 192, 256 conv5 320, 320, 320

(c) Goog Le Net

Layer K Layer K conv1 8 inception(4b) 64, 64, 80 conv2 48 inception(4c) 64, 64, 64 inception(3a) 32, 32, 48 inception(4d) 64, 96, 96 inception(3b) 32, 32, 48 inception(4e) 64, 128, 160 inception(3c) 80, 32, 48 inception(5a) 128, 96, 128 inception(4a) 32, 64, 80 inception(5b) 128, 96, 128

their baselines at the beginning, but the performance is restored after ﬁne-tuning. It is claimed in Denton et al. (2014) that data-dependent criterion leads to better performance, we found that this is true upon approximation, but after ﬁne-tuning, the difference between the two criteria is negligible (< 0.1%).

At last, we compare the low-rank models with their baselines from the perspective of classiﬁcation performance, as well as the time and space consumption. The results are summarized in Table 5. We can see that all the low-rank models achieve comparable performances. Those initialized with closed form weights approximation (cf. approximation rows in Table 5) are slightly inferior to their baselines. While the low-rank Alex Net trained from scratch with BN could achieve even better performance. This observation again reveals that the low-rank CNN structure could have better discriminative power and generalization ability. On the other hand, both the running time and the number of parameters are consistently reduced. Note that the large gaps between the theoretical and the actual speedup are mainly due to the CNN implementations, and the current BN operations signiﬁcantly slow down the forward computation. This suggests room for accelerating the low-rank models by designing speciﬁc numerical algorithms.

5 DISCUSSION

In this paper, we explored using tensor decomposition techniques to speedup convolutional neural networks. We have introduced a new algorithm for computing the low-rank tensor decomposition and a new method for training low-rank constrained CNNs from scratch. The proposed method is evaluated on a variety of modern CNNs, including Alex Net, NIN, VGG, Google Net with success. This gives a strong evidence that low-rank tensor decomposition can be a generic tool for speeding up large CNNs.

Published as a conference paper at ICLR 2016

Table 5: Comparisons between the low-rank models and their baselines. The theoretical speedup and weights reduction are computed concerning only the convolutional layers to be decomposed. While the actual speedup is based on the forward computation time of the whole net.

METHOD TOP-5 VAL. ACCURACY THEORETICAL SPEEDUP ACTUAL SPEEDUP WEIGHTS REDUCTION

Alex Net (original) 80.03% 1 1 1 Low-rank (cf. approximation) 79.66% 5.27 1.82 5.00 Low-rank (from scratch with BN) 80.56% 5.24 1.09 4.94 VGG-16 (original) 90.60% 1 1 1 Low-rank (cf. approximation) 90.31% 3.10 2.05 2.75 Goog Le Net (original) 92.21% 1 1 1 Low-rank (cf. approximation) 91.79% 2.89 1.20 2.84

On the the other hand, the interesting fact that the low-rank constrained CNNs sometimes outperform their non-constrained counterparts points to two things. One is the local minima issue. Although the expressive power of low-rank constrained CNNs is strictly smaller than that of the non-constrained one, we have observed in some cases that the former have smaller training error. This seems to suggest the low-rank form helps the CNNs begin with a better initialization and settles at a better local minimum. The other issue is over-ﬁtting. This is shown by the observation that in many cases the constrained model has higher training error but generalizes better. Overall, this suggests room for improvement in both the numerical algorithms and the regularizations of the CNN models.

ACKNOWLEDGMENTS

This work is supported in part by the 973 project 2015CB856000 of the Chinese Ministry of Science and Technology and the DOE grant DE-SC0009248.

Agostinelli, Forest, Hoffman, Matthew, Sadowski, Peter, and Baldi, Pierre. Learning activation functions to improve deep neural networks. ar Xiv preprint ar Xiv:1412.6830, 2014.

de Silva, Vin and Lim, Lek-Heng. Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem. SIAM Journal on Matrix Analysis and Applications, 30(3):1084 1127, September 2008.

Denton, Emily L, Zaremba, Wojciech, Bruna, Joan, Le Cun, Yann, and Fergus, Rob. Exploiting linear structure within convolutional networks for efﬁcient evaluation. In NIPS, 2014.

Farabet, Clement, Couprie, Camille, Najman, Laurent, and Le Cun, Yann. Learning hierarchical features for scene labeling. TPAMI, 35(8):1915 1929, 2013.

Gillis, Nicolas and Glineur, Franc ois. Low-rank matrix approximation with weights or missing data is np-hard. SIAM Journal on Matrix Analysis and Applications, 32(4):1149 1165, 2011.

Goodfellow, Ian J, Warde-Farley, David, Mirza, Mehdi, Courville, Aaron, and Bengio, Yoshua. Maxout networks. ar Xiv preprint ar Xiv:1302.4389, 2013.

Ioffe, Sergey and Szegedy, Christian. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ar Xiv preprint ar Xiv:1502.03167, 2015.

Jaderberg, Max, Vedaldi, Andrea, and Zisserman, Andrew. Speeding up convolutional neural networks with low rank expansions. ar Xiv preprint ar Xiv:1405.3866, 2014.

Jia, Yangqing, Shelhamer, Evan, Donahue, Jeff, Karayev, Sergey, Long, Jonathan, Girshick, Ross, Guadarrama, Sergio, and Darrell, Trevor. Caffe: Convolutional architecture for fast feature embedding. ar Xiv preprint ar Xiv:1408.5093, 2014.

Published as a conference paper at ICLR 2016

Krizhevsky, Alex, Sutskever, Ilya, and Hinton, Geoffrey E. Imagenet classiﬁcation with deep convolutional neural networks. In NIPS, 2012.

Lebedev, Vadim, Ganin, Yaroslav, Rakhuba, Maksim, Oseledets, Ivan, and Lempitsky, Victor. Speeding-up convolutional neural networks using ﬁne-tuned cp-decomposition. ar Xiv preprint ar Xiv:1412.6553, 2014.

Lin, M., Chen, Q., and Yan, S. Network In Network. Ar Xiv e-prints, December 2013.

Long, Jonathan, Shelhamer, Evan, and Darrell, Trevor. Fully convolutional networks for semantic segmentation. ar Xiv preprint ar Xiv:1411.4038, 2014.

Novikov, A., Podoprikhin, D., Osokin, A., and Vetrov, D. Tensorizing Neural Networks. Ar Xiv e-prints, September 2015.

Rigamonti, Roberto, Sironi, Amos, Lepetit, Vincent, and Fua, Pascal. Learning separable ﬁlters. In CVPR, 2013.

Russakovsky, Olga, Deng, Jia, Su, Hao, Krause, Jonathan, Satheesh, Sanjeev, Ma, Sean, Huang, Zhiheng, Karpathy, Andrej, Khosla, Aditya, Bernstein, Michael, Berg, Alexander C., and Fei-Fei, Li. Image Net Large Scale Visual Recognition Challenge. IJCV, pp. 1 42, April 2015.

Simonyan, Karen and Zisserman, Andrew. Very deep convolutional networks for large-scale image recognition. ar Xiv preprint ar Xiv:1409.1556, 2014.

Srivastava, Nitish, Hinton, Geoffrey, Krizhevsky, Alex, Sutskever, Ilya, and Salakhutdinov, Ruslan. Dropout: A simple way to prevent neural networks from overﬁtting. In ICML, 2014.

Szegedy, Christian, Liu, Wei, Jia, Yangqing, Sermanet, Pierre, Reed, Scott, Anguelov, Dragomir, Erhan, Dumitru, Vanhoucke, Vincent, and Rabinovich, Andrew. Going deeper with convolutions. ar Xiv preprint ar Xiv:1409.4842, 2014.

Vanhoucke, Vincent, Senior, Andrew, and Mao, Mark Z. Improving the speed of neural networks on cpus. In Deep Learning and Unsupervised Feature Learning, NIPS Workshop, 2011.

PROOF OF THEOREM 1

Proof. Consider the following minimization problem: (P2) E2( W) := W W 2 F subject to Rank( W) K. (5)

Let (H , V ) be a solution to (P1), then we can construct a solution to (P2) as follows:

V1 k V2 k... VC k

Hk 1, Hk 2, , Hk N .

Because of the separability of the Frobenius norm, E1(H , V ) = E2( W).

Moreover, as Rank( W) K, hence W is feasible for (P2). We have

E2(W ) E1(H , V ) = E2( W), (6) where W is any solution to (P2).

On the other hand, let W be a solution to (P2), then we construct a solution ( ˆH, ˆV) to (P1) as (4). Hence E1(H , V ) E1( ˆH, ˆV). Together with (6), E1( ˆH, ˆV) = E2(W ) = E1(H , V ). (7) We have proved ( ˆH, ˆV) is a solution to (P1).

Published as a conference paper at ICLR 2016

HARDNESS OF THE DATA-DEPENDENT APPROXIMATION

Using the data-dependent criterion, the minimization problem is:

c=1 Wc n Zc i

k=1 Hk n(Vc k)T Zc i 2 F . (8)

For ﬁxed stride s, deﬁne the linear map Pm : RX Y 7 Rd d, Pm(z) samples the m-th d d patch from z RX Y followed by ﬂipping the patch horizontally and vertically. Then X

c Wc n Zc n 2 F = X

m,c Wc n, Pm Zc i 2.

Pm Z1 i Pm Z2 i ... Pm Zc i

(1, 1, , 1) | {z } N

Similar as in Criterion 1, the approximation problem is equivalent to the following minimization program: E( W) := X

i,m (W W) Zim 2 F

subject to Rank( W) K, (9)

where is the Hadamard product.

This is a weighted low-rank approximation problem:

ij Gij(Wij Wij)2

subject to Rank( W) K, (10)

where G = P

im Zim Zim.

Although it appears very similar to the problem in Criterion 1, which has a closed form solution, this is much more difﬁcult to solve except for a few special cases. (E.g., when the weight matrix is identity or has rank one.) In fact, it can be proved that this problem is NP-hard (Gillis & Glineur, 2011).