Recent DNN pruning algorithms have succeeded in reducing the number of parameters in fully connected layers often with little or no drop in classification accuracy. However most of the existing pruning schemes either have to be applied during training or require a costly retraining procedure after pruning to regain classification accuracy. In this paper we propose a cheap pruning algorithm based on difference of convex (DC) optimisation. We also provide theoretical analysis for the growth in the Generalisation Error (GE) of the new pruned network. Our method can be used with any convex regulariser and allows for a controlled degradation in classification accuracy while being orders of magnitude faster than competing approaches. Experiments on common feedforward neural networks show that for sparsity levels above 90% our method achieves 10% higher classification accuracy compared to Hard Thresholding. Recently, deep neural networks have achieved state-of-the art results in a number of machine learning tasks BID12 . Training such networks is computationally intensive and often requires dedicated and expensive hardware. Furthermore, the resulting networks often require a considerable amount of memory to be stored. Using a Pascal Titan X GPU the popular AlexNet and VGG-16 models require 13 hours and 7 days, respectively, to train, while requiring 200MB and 600MB, respectively, to store. The large memory requirements limit the use of DNNs in embedded systems and portable devices such as smartphones, which are now ubiquitous. A number of approaches have been proposed to reduce the DNN size during training time, often with little or no degradation to classification performance. Approaches include introducing bayesian, sparsity-inducing priors BID13 BID2 BID14 and binarization BID10 BID5 .Other methods include the hashing trick used in BID4 , tensorisation BID17 and efficient matrix factorisations BID11 .However, trained DNN models are used by researchers and developers that do not have dedicated hardware to train them, often as general feature extractors for transfer learning. In such settings it is important to introduce a cheap compression method, i.e., one that can be implemented as a postprocessing step with little or no retraining. Some first work in this direction has been BID11 BID8 BID9 although these still require a lengthy retraining procedure. Closer to our approach recently in BID0 the authors propose a convexified layerwise pruning algorithm termed Net-Trim. Building upon Net-Trim, the authors in BID6 propose LOBS, an algorithm for layerwise pruning by loss function approximation. Pruning a neural network layer introduces a pertubation to the latent signal representations generated by that layer. As the pertubated signal passes through layers of non-linear projections, the pertubation could become arbitrary large. In BID0 and BID6 the authors conduct a theoretical analysis using the Lipschitz properties of DNNs showing the stability of the latent representations, over the training set, after pruning. The methods employed have connections to recent work BID19 BID1 BID15 Lipschitz properties to analyze the Generalization Error (GE) of DNNs, a more useful performance measure. In this work we introduce a cheap pruning algorithm for dense layers of DNNs. We also conduct a theoretical analysis of how pruning affects the Generalization Error of the trained classifier.• We show that the sparsity-inducing objective proposed in BID0 DISPLAYFORM0 , where is the precision of the solution, k is related to the Lipschitz and strong convexity constants, d 2 d 1 and K is the outer iteration number. Emprirically, our algorithm is orders of magnitude faster than competing approaches. We also extend our formulation to allow retraining a layer with any convex regulariser.• We build upon the work of BID19 to bound the GE of a DNN after pruning. Our theoretical analysis holds for any bounded pertubation to one or multiple hidden DNN layers and provides a principled way of pruning while managing the GE.Experiments on common feedforward architectures show that our method is orders of magnitude faster than competing pruning methods, while allowing for a controlled degradation in GE. We use the following notation in the sequel:matrices ,column vectors, scalars and sets are denoted by boldface upper-case letters (X), boldface lower-case letters (x), italic letters (x) and calligraphic upper-case letters (X ), respectively. The covering number of X with d-metric balls of radius ρ is denoted by N (X ; d, ρ). A C M -regular k-dimensional manifold, where C M is a constant that captures "intrinsic" properties, is one that has a covering number N (X ; d, ρ) = ( DISPLAYFORM0 We consider a classification problem, where we observe a vector x ∈ X ⊆ R N that has a corresponding class label y ∈ Y. The set X is called the input space, Y = {1, 2, ..., N Y } is called the label space and N Y denotes the number of classes. The samples space is denoted by S = X × Y and an element of S is denoted by s = (x, y). We assume that samples from S are drawn according to a probability distribution P defined on S. A training set of m samples drawn from P is denoted by DISPLAYFORM1 We start from the Net-Trim formulation and show that it can be cast as a difference of convex functions problem. For each training signal x ∈ R N we assume also that we have access to the inputs a ∈ R d1 and the outputs b ∈ R d2 of the fully connected layer, with a rectifier non-linearity ρ(x) = max(0, x). The optimisation problem that we want to solve is then DISPLAYFORM2 where λ is the sparsity parameter. The term ||ρ(U T a j ) − b j || 2 2 ensures that the nonlinear projection remains the same for training signals. The term λΩ(U ) is the convex regulariser which imposes the desired structure on the weight matrix U .The objective in Equation 1 is non-convex. We show that the optimisation of this objective can be cast as a difference of convex functions (DC) problem. We assume just one training sample x ∈ R N , for simplicity, with latent representations DISPLAYFORM3 Notice that after the split the first term (b i < 0) is convex while the second (b i ≥ 0) is concave. We note that b i ≥ 0 by definition of the ReLu and set DISPLAYFORM4 DISPLAYFORM5 Then by summing over all the samples we get DISPLAYFORM6 which is difference of convex functions. The rectifier nonlinearity is non-smooth, but we can alleviate that by assuming a smooth approximation. A common choice for this task is ρ(x) = 1 β log(1 + exp(βx)), with β a positive constant. It is well known that DC programs have efficient optimisation algorithms. We propose to use the DCA algorithm BID20 . DCA is an iterative algorithm that consists in solving, at each iteration, the convex optimisation problem obtained by linearizing h(·) (the non-convex part of f = g − h) around the current solution. Although DCA is only guaranteed to reach local minima the authors of BID20 state that DCA often converges to the global minimum, and has been used succefully to optimise a fully connected DNN layer BID7 . At iteration k of DCA, the linearized optimisation problem is given by arg min DISPLAYFORM0 where U k is the solution estimate at iteration k. The detailed procedure is then given in algorithms 1 and 2. We assume that the regulariser is convex but possibly non-smooth in which case the optimisation can be performed using proximal methods. Compute C ← ∇h(U k ). Solve with Algorithm 2 the convex optimisation problem: DISPLAYFORM0 5: end for DISPLAYFORM1 Choose (A, B) randomly chosen minibatch. x 1 = y 1 =x s for t = 1,2,...,T do 6:Choose (A, B) randomly chosen minibatch. u t = ∇g A,B (y t ) − ∇g A,B (x s ) +ũ 8:x t+1 = prox ηh (y t − ηu t ) 9: DISPLAYFORM0 end for 11:x s+1 = x T +1 12: end for 13: Return U k+1 ←x S+1In order to solve the linearized problem we first propose to use Proximal Stochastic Gradient Descent (Prox-SG), which we detail in algorithm 2a. At each iteration a minibatch A and B is drawn. The gradient for the smooth part is calculated and the algorithm takes a step in that direction with step size ρ t . At each iteration ρ is updated as ρ t ← min(ρ, ρ t0 t ) where t 0 is a hyperparameter. Then the proximal operator for the non-smooth regulariser λΩ(·) is applied to the result. We find that for the outer iterations K the values 5 to 15 are usually sufficient, while for the inner iterations T = 150 is usually sufficient. Although Prox-SG is very efficient, it sometimes doesn't converge to a good solution. We therefore propose to use Accelerated Proximal SVRG (Acc-Prox-SVRG), which was presented in BID16 . We detail this method in Algorithm 2b. For most experiments we see a significant improvement over Prox-SG. The hyperparameters for Acc-Prox-SVRG are the acceleration parameter β and the gradient step η. We have found that in our experiments, using β = 0.95 and η ∈ {0.001, 0.0001} gives the best results. We name our algorithm FeTa, Fast and Efficient Trimming Algorithm. Having optimized our pruned layer for the training set we want to see if it is stable for the test set. We denote f 1 (·, W 1 ) the original representation and f 2 (·, W 2 ) the pruned representation. We assume that after training DISPLAYFORM0 Second, we assume that ∀s ∈ S ∃s i ∈ S m ⇒ ||a − a i || 2 2 ≤ . Third, the linear operators in W 1 , W 2 are frames with upper frame bounds B 1 , B 2 respectively. Theorem 3.1. For any testing point s ∈ S, the distance between the original representation f 1 (a, W 1 ) and the pruned representation DISPLAYFORM1 the detailed proof can be found in Appendix A. In this section we use tools from the robustness framework Xu & Mannor (2012) to bound the generalization error of the new architecture induced by our pruning. We consider DNN classifiers defined as DISPLAYFORM0 where DISPLAYFORM1 where f l (·, W l ) represents the l−th layer with parameters W l , l = 1, ..., L. The output of the l−th layer is denoted z l , i.e. DISPLAYFORM2 The input layer corresponds to z 0 = x and the output of the last layer is denoted by z = f (x). We then need the following two definitions of the classification margin and the score that we take from BID19 . These will be useful later for measuring the generalization error. Definition 3.1. (Score). For a classifier g(x) a training sample DISPLAYFORM3 where δ i ∈ R Ny is the Kronecker delta vector with (δ i ) i = 1, and g(x i ) is the output class for s i from classifier g(x) which can also be g( DISPLAYFORM4 The classification margin of a training sample s i is the radius of the largest metric ball (induced by the l 2 norm) in X centered at x i that is contained in the decision region associated with the classification label g(x i ). Note that it is possible for a classifier to misclassify a training point g(x i ) = y i . We then restate a useful result from BID19 . Corollary 3.1.1. Assume that X is a (subset of) C M -regular k-dimensional manifold, where DISPLAYFORM5 Assume also that the DNN classifier g(x) achieves a lower bound to the classification score o(s) < o(s i ), ∀s i ∈ S m and take l(g(x i ), y i ) to be the 0 − 1 loss. Then for any δ > 0, with probability at least 1 − δ, DISPLAYFORM6 DISPLAYFORM7 and B = 2 log 1/δ m can be considered constants related to the data manifold and the training sample size, and γ = o(s) DISPLAYFORM8 We are now ready to state our main result. Theorem 3.2. Assume that X is a (subset of) C M -regular k-dimensional manifold, where DISPLAYFORM9 Assume also that the DNN classifier g 1 (x) achieves a lower bound to the classification score o(s) < o(s i ), ∀s i ∈ S m and take l(g(x i ), y i ) to be the 0 − 1 loss. Furthermore assume that we prune classifier g 1 (x) on layer i using Algorithm 1, to obtain a new classifier g 2 (x). Then for any δ > 0, with probability at least 1 − δ, DISPLAYFORM10 where DISPLAYFORM11 and B = 2 log 1/δ m can be considered constants related to the data manifold and the training sample size, and γ = o(s) DISPLAYFORM12 The detailed proof can be found in Appendix B. The bound depends on two constants related to intrinsic properties of the data manifold, the regularity constant C M and the intrinsic data dimensionality k. In particular the bound depends exponentially on the intrinsic data dimensionality k. Thus more complex datasets are expected to lead to less robust DNNs. This has been recently observed empirically in BID1 . The bound also depends on the spectral norm of the hidden layers ||W i || 2 . Small spectral norms lead to a larger base in (·) With respect to pruning our result is quite pessimistic as the pruning error √ C 2 is multiplied by the factor i>i ||W i || 2 . Thus in our analysis the GE grows exponentially with respect to the remaining layer depth of the pertubated layer. This is in line with previous work BID18 BID9 that demonstrates that layers closer to the input are much less robust compared to layers close to the output. Our algorithm is applied to the fully connected layers of a DNN, which are much closer to the output compared to convolutional layers. We can extend the above bound to include pruning of multiple layers. Theorem 3.3. Assume that X is a (subset of) C M -regular k-dimensional manifold, where DISPLAYFORM13 k . Assume also that the DNN classifier g 1 (x) achieves a lower bound to the classification score o(s) < o(s i ), ∀s i ∈ S m and take l(g(x i ), y i ) to be the 0 − 1 loss. Furthermore assume that we prune classifier g 1 (x) on all layers using Algorithm 1, to obtain a new classifier g 2 (x). Then for any δ > 0, with probability at least 1−δ, DISPLAYFORM14 where DISPLAYFORM15 and B = 2 log 1/δ m can be considered constants related to the data manifold and the training sample size, and γ = o(s) DISPLAYFORM16 The detailed proof can be found in Appendix C. The bound predicts that when pruning multiple layers the GE will be much greater than the sum of the GEs for each individual pruning. We note also the generality of our result; even though we have assumed a specific form of pruning, the GE bound holds for any type of bounded pertubation to a hidden layer. We make a number of experiments to compare FeTa with LOBS and NetTrim-ADMM. We test two versions of the algorithm, FeTa 1 optimised with Prox-SGD and FeTa 2 optimized with Acc-Prox-SVRG. All experiments were run on a MacBook Pro with CPU 2.8GHz Intel Core i7 and RAM 16GB 1600 MHz DDR3. First we compare the execution time of FeTa with that of LOBS and NetTrim-ADMM. We set Ω(U ) = ||U || 1 and aim for 95% sparsity. We set d 1 to be the input dimensions, d 2 to be the output dimensions and N to be the number of training samples. Assuming that each g(U ; x j ) is L-Lipschitz smooth and g(U ) is µ-strongly convex, if we optimise for an optimal solution and set DISPLAYFORM0 We obtain this by multiplying the number of outer iterations K with the number of gradient evaluations required to reach an good solution in inner Algorithm 2a and inner Algorithm 2b, and finally multiplying with the gradient evaluation cost. Conversely LOBS scales like O((N + d 2 )d 2 1 ) while NetTrim-ADMM scales like O(N d 3 1 ) due to the required Cholesky factorisation. This gives a computational advantage to our algorithm in settings where the input dimension is large. We validate this by constructing a synthetic experiment with d 2 = 10 , d 1 = {2000 : 100 : 3000} and N = 1000. The samples a ∈ R d1 and b ∈ R d2 are generated with i.i.d Gaussian entries. We plot in FIG2 the results, which are in line with the theoretical predictions. In this section we perform experiments on the proposed compression scheme with feedforward neural networks. We compare the original full-precision network (without compression) with the following compressed networks: (i) FeTa 1 with Ω(U ) = ||U || 1 (ii) FeTa 2 with Ω(U ) = ||U || 1 (iii) Net-Trim (vi) LOBS (v) Hard Thresholding. We refer to the respective papers for Net-Trim and LOBS. Hard Thresholding is defined as F (x) = x I(|x| > t), where I is the elementwise indicator function, is the Hadamard product and t is a positive constant. Experiments were performed on two commonly used datasets:1. MNIST: This contains 28 × 28 gray images from ten digit classes. We use 55000 images for training, another 5000 for validation, and the remaining 10000 for testing. We use the LeNet-5 model: DISPLAYFORM1 where C5 is a 5 × 5 ReLU convolution layer, M P 2 is a 2 × 2 max-pooling layer, F C is a fully connected layer and SM is a linear softmax layer. 2. CIFAR-10:This contains 60000 32 × 32 color images for ten object classes. We use 50000 images for training and the remaining 10000 for testing. The training data is augmented by random cropping to 24 × 24 pixels, random flips from left to right, contrast and brightness distortions to 200000 images. We use a smaller variant of the AlexNet model: DISPLAYFORM2 We first prune only the first fully connected layer (the one furthest from the output) for clarity. FIG3 shows the classification accuracy vs compression ratio for FeTa 1 , FeTa 2 , NetTrim, LOBS and Hard Thresholding. We see that Hard Thresholding works adequately up to 85% sparsity. From this level of sparsity and above the performance of Hard Thresholding degrades rapidly and FeTa has 10% higher accuracy on average. We also see a notable improvement of 3% − 5% for FeTa 2 over FeTa 1 . Finally NetTrim and LOBS also give good results for a wide range of sparsity values, with LOBS giving the best results overall. For the task of pruning the first fully connected layer we also show detailed comparison results for all methods in TAB1 . For the LeNet-5 model, FeTa achieves the same accuracy as Net-Trim while being significantly faster. This is expected as the two algorithms optimise a similar objective, while FeTa exploits the structure of the objective to achieve lower complexity in optimisation. Furthermore FeTa achieves marginally lower classification accuracy compared to LOBS, and is significantly better than Thresholding. Overall FeTa enjoys competitive accuracy results while being able to prune the dense layer 5× to 25× faster compared to other approaches. For the CifarNet model Net-Trim is not feasible on the machine used for the experiments as it requires over 16GB of RAM. Compared to LOBS FeTa again achieves marginally lower accuracy but is 8× to 14× faster. Note that as mentioned in BID6 and Wolfe et al. (2017) retraining can recover classification accuracy that was lost during pruning. Starting from a good pruning which doesn't allow for much degradation significantly reduces retraining time. Next we prune both the fully connected layers in the two architectures to the same sparsity level and plot the results in TAB2 . We lower the achieved sparsity for all methods to 90%. The accuracy results are mostly the same as when pruning a single layer, with FeTa achieving the same or marginally worse results while enjoying significant computation speedups for MNIST. At the same time there is a larger degradation for the CIFAR experiment. One significant difference is that Thresholding achieves a notably bad result of 64% accuracy, which makes the method essentially inapplicable for multilayer pruning. As a proof of concept for the generality of our approach we apply our method while imposing lowrank regularisation on the learned matrix U . For low rank k we compare two methods (i) FeTa 1 with Ω(U ) = ||U || and optimised with Acc-Prox-SVRG and (ii) Hard Thresholding of singular values using the truncated SVD defined as U = N ΣV , Σ = diag({σ i } 1≤i≤k ). We plot the results in FIG4 . In the above given U ∈ R d1×d2 the Commpression Ratio (CR) is defined as CR = (k DISPLAYFORM0 The results are in line with the l 1 regularisation, with significant degredation in classification accuracy for Hard Thresholding above 85% CR. According to our theoretical analysis the GE drops exponentially as the pruning moves away from the output layer. To corroborate this we train a LeNet-5 to high accuracy, then we pick a single layer and gradually increase its sparsity using Hard Thresholding. We find that the layers closer to the input are exponentially less robust to pruning, in line with our theoretical analysis. We plot the results in FIG5 .a. For some layers there is a sudden increase in accuracy around 90% sparsity which could be due to the small size of the DNN. We point out that in empirical results BID18 BID9 for much larger networks the degradation is entirely smooth. Next we test our multilayer pruning bound. We prune to the same sparsity levels all layers in the sets i ≥ 0 , i ≥ 1 , i ≥ 2 , i ≥ 3. We plot the results in FIG5 .b. It is evident that the accuracy loss for layer groups is not simply the addition of the accuracy losses of the individual layers, but shows an exponential drop in accordance with our theoretical result. We now aim to see how well our bound captures this exponential behaviour. We take two networks g a pruned at layer 3 and g b pruned at layers 2 and 3 and make a number of simplifying assumptions. First we assume that in Theorem 3. DISPLAYFORM0 . This is logical as B includes only log terms. Assuming that the bounds are tight we now aim to calculate DISPLAYFORM1 We know that the value of this ratio for 90% sparsity is GE(g a )/GE(g b ) ≈ 0.1/0.4 = 1/4 and we have managed to avoid the cumbersome A parameter. Next we make the assumption that k ≈ 40, this is common for the MNIST dataset and results from a simple dimensionality analysis using PCA. We also deviate slightly from our theory by using the average layerwise errors DISPLAYFORM2 which is very close to the empirical value. In this paper we have presented an efficient pruning algorithm for fully connected layers of DNNs, based on difference of convex functions optimisation. Our algorithm is orders of magnitude faster than competing approaches while allowing for a controlled degradation in the Generalization Error. We provided a theoretical analysis of the degradation in GE resulting from our pruning algorithm. This analysis validates the previously observed phenomenon that network layers closer to the input are exponentially less robust to pruning compared to layers close to the output. Our theoretical analysis is of value by itself as it holds for any kind of bounded pertubation to one or multiple hidden DNN layers. Experiments on common feedforward architectures validate our results. Proof. See BID3 for details, the derivation is not entirely trivial due to the nonsmoothness of the rectifier non-linearity. Proof. We see that: DISPLAYFORM0 1+exp(βx) ≤ 1. Therefore the smooth approximation to the rectifier non-linarity is Lipschitz smooth with Lipschitz constant k = 1. Then DISPLAYFORM1 We drop the W i from the layer notation for clarity. Using the triangle inequality DISPLAYFORM2 where we used Lemma 6.1 and Lemma 6.2 in line 5.B. PROOF OF THEOREM 3.2. We will proceed as follows. We first introduce some prior results which hold for the general class of robust classifiers. We will then give specific prior generalization error results for the case of classifiers operating on datapoints from C m -regular manifolds. Afterwards we will provide prior results for the specific case of DNN clasifiers. Finally we will prove our novel generalization error bound and provide a link with prior bounds. We first formalize robustness for generic classifiers g(x). In the following we assume a loss function l(g(x), y) that is positive and bounded DISPLAYFORM3 , such that ∀s i ∈ S m , ∀s ∈ S, DISPLAYFORM4 Now letl(·) and l emp (·) denote the expected error and the training error, i.e, DISPLAYFORM5 we can then state the following theorem from Xu & Mannor (2012): Theorem 6.3. If S m consists of m i.i.d. samples, and g(x) is (K, (S m ))-robust, then for any δ > 0, with probability at least 1 − δ, DISPLAYFORM6 The above generic bound can be specified for the case of C m -regular manifolds as in BID19 . We recall the definition of the sample margin γ(s i ) as well as the following theorem:Theorem 6.4. If there exists γ such that DISPLAYFORM7 By direct substitution of the above result and the definiton of a C m -regular manifold into Theorem 6.3 we get: Corollary 6.4.1. Assume that X is a (subset of) C M regular k−dimensional manifold, where DISPLAYFORM8 k . Assume also that classifier g(x) achieves a classification margin γ and take l(g(x), y) to be the 0 − 1 loss. Then for any δ > 0, with probability at least 1 − δ, DISPLAYFORM9 Note that in the above we have used the fact that l(g(x), y) ≤ 1 and therefore M = 1. The above holds for a wide range of algorithms that includes as an example SVMs. We are now ready to specify the above bound for the case of DNNs, adapted from BID19 , Theorem 6.5. Assume that a DNN classifier g(x), as defined in equation 8, and letx be the training sample with the smallest score o(s) > 0. Then the classification margin is bounded as DISPLAYFORM10 We now prove our main result. We will denote byx = arg min si∈Sm min j =g(xi) v T g(xi)j f (x i ) the training sample with the smallest score. For this training sample we will denote j = arg min j =g(x) v T g(x)j f (x) the second best guess of the classifier g(·). Throughout the proof, we will use the notation DISPLAYFORM11 First we assume the score o 1 (x, g 1 (x)) of the pointx for the original classifier g 1 (x). Then, for the second classifier g 2 (x), we take a point x that lies on the decision boundary between g 2 (x) and j such that o 2 (x , g 2 (x)) = 0. We assume for simplicity that, after pruning, the classification decisions do not change such that g 1 (x) = g 2 (x). We then make the following calculations DISPLAYFORM12 where we used Theorem 3.1 in line 5, since x is not a training sample. From the above we can therefore write o 1 (x, g 1 (x)) − √ C 2 i>i ||W i || 2 DISPLAYFORM13 By following the derivation of the margin from the original paper BID19 and taking into account the definition of the margin we know that DISPLAYFORM14 Therefore we can finally write DISPLAYFORM15 The theorem follows from direct application of Corollary 3.1.1. Note that if γ − √ C2 i>i ||W i||2 i ||W i||2 < 0 the derived bound becomes vacuous, as by definition 0 ≤ γ 2 (x).C. PROOF OF THEOREM 3.3. We start as in theorem 3.2 by assuming the score o 1 (x, g 1 (x)) of the pointx for the original classifier g 1 (x). Then, for the second classifier g 2 (x), we take a point x that lies on the decision boundary between g 2 (x) and j such that o 2 (x , g 2 (x)) = 0. We assume as before that the classification decisions do not change such that g 1 (x) = g 2 (x). We write DISPLAYFORM16 We can then write DISPLAYFORM17 Then as before DISPLAYFORM18 The theorem follows from direct application of Corollary 3.1.1.
A fast pruning algorithm for fully connected DNN layers with theoretical analysis of degradation in Generalisation Error. Presents a cheap pruning algorithm for dense layers of DNNs. Proposes a solution to the problem of pruning DNNs by posing the Net-trim objective function as a Difference of convex(DC) function.