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 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.