FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

Konstantinos Pitas 1 Mike Davies 2 Pierre Vandergheynst 1

arXiv:1803.04239v1 [cs.LG] 12 Mar 2018

Abstract
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. We start by proposing a cheap pruning
algorithm for fully connected DNN layers based
on difference of convex functions (DC) optimisation, that requires little or no retraining. We
then provide a theoretical analysis for the growth
in the Generalization Error (GE) of a DNN for
the case of bounded perturbations to the hidden
layers, of which weight pruning is a special case.
Our pruning method is orders of magnitude faster
than competing approaches, while our theoretical
analysis sheds light to previously observed problems in DNN pruning. Experiments on commnon
feedforward neural networks validate our results.

1. Introduction
Recently, deep neural networks have achieved state-of-the
art results in a number of machine learning tasks LeCun
et al. (2015). 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 degra*

Equal contribution 1 LTS2 Laboratory, EPFL, Lausanne,
Switzerland 2 IDCOM Laboratory, University of Edinburgh, Edinburgh, UK. Correspondence to: Pitas Konstantinos <konstantinos.pitas@epfl.ch>.

dation to classification performance. Approaches include
introducing bayesian, sparsity-inducing priors Louizos et al.
(2017) Blundell et al. (2015) Molchanov et al. (2017) and binarization Hou et al. (2016) Courbariaux et al. (2016).Other
methods include the hashing trick used in Chen et al. (2015),
tensorisation Novikov et al. (2015) and efficient matrix factorisations Yang et al. (2015).
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 Kim et al. (2015) Han et al.
(2015a) Han et al. (2015b) although these still require a
lengthy retraining procedure. Closer to our approach recently in Aghasi et al. (2016) the authors propose a convexified layerwise pruning algorithm termed Net-Trim. Building
upon Net-Trim, the authors in Dong et al. (2017) propose
LOBS, an algorithm for layerwise pruning by loss function
approximation.
Pruning a neural network layer introduces a perturbation
to the latent signal representations generated by that layer.
As the pertubated signal passes through layers of non-linear
projections, the perturbation could become arbitrarily large.
DNN robustness to hidden layer perturbations has been investigated for random noise in Raghu et al. (2016). For
the case of pruning in Aghasi et al. (2016) and Dong et al.
(2017) 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 Sokolic
et al. (2017) Bartlett et al. (2017) Neyshabur et al. (2017)
that have used the Lipschitz properties to analyze the Generalization Error (GE) of DNNs, a more useful performance
measure.
1.1. Contributions
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.

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

• We show that the sparsity-inducing objective proposed
in Aghasi et al. (2016) can be cast as a difference of
convex functions problem, that has an efficient solution. For a fully connected layer with input dimension d1 , output dimension d2 and N training samples, Net-Trim and LOBS scale like O(N d31 ) and
O((N + d2 )d21 ), respectively. Our iterative algorithm
k
√
scales like O(K(N + NN
)log( 1 )d1 d2 ), where  is
+ k
the precision of the solution, k is related to the Lipschitz and strong convexity constants, d2  d1 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 Sokolic et al. (2017) to
bound the GE of a DNN for the case of bounded perturbations to the hidden layer weights, of which pruning
is a special case. Our theoretical analysis provides a
principled way of pruning while managing the GE. In
sharp contrast to the analysis of Aghasi et al. (2016)
and Dong et al. (2017) our analysis correctly predicts
the previously observed phenomenon that accuracy degrades exponentially with the remaining depth of the
pruned layer.

m samples drawn from P is denoted by Sm = {si }m
i=1 =
{(xi , yi )}m
i=1 .
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 ∈ RN we assume also that we
have access to the inputs a ∈ Rd1 and the outputs b ∈ Rd2
of the fully connected layer, with a rectifier non-linearity
ρ(x) = max(0, x). The optimisation problem that we want
to solve is then

min
U

1 X
||ρ(U T aj ) − bj ||22 + λΩ(U ),
m

(1)

sj ∈Sm

where λ is the sparsity parameter. The term ||ρ(U T aj ) −
bj ||22 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 ∈ RN , for simplicity, with latent
representations a ∈ Rd and b ∈ Rz

Experiments on common feedforward architectures show
that our method is orders of magnitude faster than competing
pruning methods, while allowing for a controlled increase
in GE.

||ρ(U T a) − b||22 + λΩ(U )
X
=
[ρ(ui T a) − bi ]2 + λΩ(U )

1.2. Notation and Definitions

=

X

=

X

i

We use the following notation in the sequel:matrices ,column vectors, scalars and sets are denoted by boldface uppercase 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 CM -regular kdimensional manifold, where CM is a constant that captures
”intrinsic” properties, is one that has a covering number
N (X ; d, ρ) = ( CρM )k .

2. Our formulation
2.1. DC decomposition
We consider a classification problem, where we observe
a vector x ∈ X ⊆ RN that has a corresponding class
label y ∈ Y. The set X is called the input space, Y =
{1, 2, ..., NY } is called the label space and NY 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

[ρ2 (ui T a) − 2ρ(ui T a)bi + bi 2 ] + λΩ(U )

i

[ρ2 (ui T a) + bi 2 ] + λΩ(U ) +

i

X

[−2bi ρ(ui T a)]

i

X
=
[ρ2 (ui T a) + bi 2 ] + λΩ(U )
i

+

X

X

[−2bi ρ(ui T a)] +

i
bi <0

[−2bi ρ(ui T a)].

i
bi ≥0

(2)
Notice that after the split the first term (bi < 0) is convex
while the second (bi ≥ 0) is concave. We note that bi ≥ 0
by definition of the ReLu and set

g(U ; x) =

X

[ρ2 (ui T a) + bi 2 ],

(3)

i

h(U ; x) =

X

[2bi ρ(ui T a)].

i
bi >0

(4)

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

Algorithm 2 Acc-Prox-SVRG

Then by summing over all the samples we get

f (U ) =

X

g(U ; xj ) + λΩ(U ) −

j

X

h(U ; xj )

j

(5)

= g(U ) + λΩ(U ) − h(U ),
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.
2.2. Optimisation
It is well known that DC programs have efficient optimisation algorithms. We propose to use the DCA algorithm
Tao & An (1997). 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 Tao
& An (1997) state that DCA often converges to the global
minimum, and has been used succefully to optimise a fully
connected DNN layer Fawzi et al. (2015). At iteration k of
DCA, the linearized optimisation problem is given by

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

Initialization: x̃0 ← U k , β, η
for s = 1,...,S do
ũ = ∇g(x̃s )
x1 = y 1 = x̃s
for t = 1,2,...,T do
Choose (A, B) randomly chosen minibatch.
ut = ∇gA,B (y t ) − ∇gA,B (x̃s ) + ũ
xt+1 = proxηh (y t − ηut )
y t+1 = xt+1 + β(xt+1 − xt )
end for
x̃s+1 = xT +1
end for
Return U k+1 ← x̃S+1

the proximal operator for the non-smooth regulariser λΩ(·)
is applied to the result. The hyperparameters for Acc-ProxSVRG 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.

3. Generalization Error
arg min{g(U ) + λΩ(U ) − T r(U T ∇h(U k ))},

(6)

U

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.
Algorithm 1 FeTa (Fast and Efficient Trimming Algorithm)
1: Choose initial point: U 0
2: for k = 1,...,K do
3:
Compute C ← ∇h(U k ).
4:
Solve with Algorithm 2 the convex optimisation prob-

lem:
U k+1 ← arg min{g(U ) + λΩ(U ) − T r(U T C)}
U

3.1. Generalization Error of Pruned Layer
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
∀si ∈ Sm ||f 1 (ai , W 1 ) − f 2 (ai , W 2 )||22 ≤ C1 . Second,
we assume that ∀s ∈ S ∃si ∈ Sm ⇒ ||a − ai ||22 ≤ . Third,
the linear operators in W 1 , W 2 are frames with upper
frame bounds B1 , B2 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 f 2 (a, W 2 ) is bounded by
||f 1 (a, W 1 ) − f 2 (a, W 2 )||22 ≤ C2 where C2 = C1 +
(B1 + B2 ).
the detailed proof can be found in Appendix A.

(7)
5: end for
6: If U k+1 ≈ U k return U k+1 .

In order to solve the linearized problem we propose to use
Accelerated Proximal SVRG (Acc-Prox-SVRG), which was
presented in Nitanda (2014). We detail this method in Algorithm 2b. 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 η. Then

3.2. Generalization Error of Classifier
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

g(x) = max (f (x))i ,
i∈[Ny ]

(8)

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

where (f (x))i is the i−th element of Ny dimensional output of a DNN f : RN → RNy . We assume that f (x) is
composed of L layers

f (x) = fL (fL−1 (...f1 (x, W 1 ), ...W L−1 ), W L ),

(9)

where fl (·, 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. z l = fl (z l−1 , W l ). 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 Sokolic
et al. (2017). These will be useful later for measuring the
generalization error.
Definition 3.1. (Score). For a classifier g(x) a training
sample si = (xi , yi ) has a score

o(si ) = o(xi , g(xi )) = min

j6=g(xi )

√

2(δg(xi ) − δj )T f (xi ),
(10)

where δi ∈ RNy is the Kronecker delta vector with (δi )i =
1, and g(xi ) is the output class for si from classifier g(x)
which can also be g(xi ) 6= yi .
Definition 3.2. (Training Sample Margin). For a classifier
g(x) a training sample si = (xi , yi ) has a classification
margin γ(si ) measured by the l2 norm if
g(x) = g(xi ); ∀x : ||x − xi ||2 < γ(si ).

(11)

The classification margin of a training sample si is the radius of the largest metric ball (induced by the l2 norm) in
X centered at xi that is contained in the decision region
associated with the classification label g(xi ). Note that it
is possible for a classifier to misclassify a training point
g(xi ) 6= yi . We then restate a useful result from Sokolic
et al. (2017).
Corollary 3.1.1. Assume that X is a (subset of) CM regular k-dimensional manifold, where N (X ; d; ρ) ≤
( CρM )k . Assume also that the DNN classifier g(x) achieves a
lower bound to the classification score o(s̃) < o(si ), ∀si ∈
Sm and take l(g(xi ), yi ) to be the 0 − 1 loss. Then for any
δ > 0, with probability at least 1 − δ,
k

GE(g) ≤ A · (γ)− 2 + B,

(12)

q
q
log (2)·Ny ·2k+1 ·(CM )k
2 log 1/δ
where A =
and
B
=
m
m
can be considered constants related to the data manifold
o(s̃)
and the training sample size, and γ = Q ||W
.
i ||2
i

We are now ready to state our main result.

Theorem 3.2. Assume that X is a (subset of) CM -regular
k-dimensional manifold, where N (X ; d; ρ) ≤ ( CρM )k . Assume also that the DNN classifier g1 (x) achieves a lower
bound to the classification score o(s̃) < o(si ), ∀si ∈ Sm
and take l(g(xi ), yi ) to be the 0 − 1 loss. Furthermore
assume that we prune classifier g1 (x) on layer i? using Algorithm 1, to obtain a new classifier g2 (x). Then
for any δ >
Q 0, with probability at least 1 − δ, when
√
i>i? ||W i ||2
(γ − C2 · Q
||W i ||2 ) > 0,
i

GE(g2 ) ≤ A · (γ −

p

Q
i>i? ||W i ||2 − k
C2 · Q
) 2 + B, (13)
i ||W i ||2

q
q
log (2)·Ny ·2k+1 ·(CM )k
2 log 1/δ
where A =
and
B
=
m
m
can be considered constants related to the data manifold
o(s̃)
and the training sample size, and γ = Q ||W
.
i ||2
i

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 CM 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
Bartlett et al. (2017). The bound also depends on the spectral norm of the hidden layers ||W i ||2 . Small spectral norms
k
lead to a larger base in (·)− 2 and thus to tigher bounds.
With respect to pruning
√ our result is quite pessimistic
as
the
pruning
error
C2 is multiplied by the factor
Q
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 Raghu
et al. (2016) Han et al. (2015b) 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) CM -regular
k-dimensional manifold, where N (X ; d; ρ) ≤ ( CρM )k . Assume also that the DNN classifier g1 (x) achieves a lower
bound to the classification score o(s̃) < o(si ), ∀si ∈ Sm
and take l(g(xi ), yi ) to be the 0 − 1 loss. Furthermore
assume that we prune classifier g1 (x) on all layers using Algorithm 1, to obtain a new classifier g2 (x). Then
for any δ > 0, with probability at least 1 − δ, when

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

(γ −

PL

i=0

√

Ci2
Q

QL

j=i+1

||W j ||2

i ||W i ||2

PL √
GE(g2 ) ≤ A · (γ −
q

i=0

) > 0,

Ci2
Q

QL

j=i+1

||W j ||2

i ||W i ||2

k

)− 2 + B,
(14)

q

log (2)·Ny ·2k+1 ·(CM )k
m

2 log 1/δ
m

where A =
and B =
can be considered constants related to the data manifold
o(s̃)
.
and the training sample size, and γ = Q ||W
i ||2
i

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 perturbation to a
hidden layer.

4. Experiments
We make a number of experiments to compare FeTa with
LOBS and NetTrim-ADMM. All experiments were run on
a MacBook Pro with CPU 2.8GHz Intel Core i7 and RAM
16GB 1600 MHz DDR3.
4.1. Time Complexity
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 d1 to be the input dimensions,
d2 to be the output dimensions and N to be the number
of training samples. Assuming that each g(U ; xj ) is LLipschitz smooth and g(U ) is µ-strongly convex, if we
optimise for an  optimal solution and set k = L/µ, FeTa
k
√
scales like O(K(N + NN
)log( 1 )d1 d2 ). We obtain this
+ k
by multiplying the number of outer iterations K with the
number of gradient evaluations required to reach an  good
solution in inner Algorithm 2, and finally multiplying with
the gradient evaluation cost. Conversely LOBS scales like
O((N + d2 )d21 ) while NetTrim-ADMM scales like O(N d31 )
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 toy dataset with d2 = 10 , d1 = {2000 : 100 : 3000}
and N = 1000. The samples a ∈ Rd1 and b ∈ Rd2 are
generated with i.i.d Gaussian entries. We plot in Figure 1
the results, which are in line with the theoretical predictions.
4.2. Classification Accuracy
4.2.1. S PARSE R EGULARISATION
In this section we perform experiments on the proposed
compression scheme with feedforward neural networks.

Figure 1. Time Complexity: We plot the calculation time for FeTa,
NetTrim and LOBS for the toy dataset. We see that the computation time is in line with theoretical predictions. FeTa scales roughly
as O(N d2 d1 ) while NetTrim and LOBS scale like O(N d32 ) and
O(N d22 ). As the size of the input dimensions increases FeTa becomes orders of magnitude faster than the competing approaches.

We compare the original full-precision network (without
compression) with the following compressed networks: (i)
FeTa with Ω(U ) = ||U ||1 (ii) Net-Trim (iii) LOBS (iv)
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:

Input → (1 × 6C5) → M P 2 → (6 × 16C5)
→ M P 2 → 120F C → 84F C → 10SM → Output,
(15)
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

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

brightness distortions to 200000 images. We use a
smaller variant of the AlexNet model:

Input → (3 × 64C5) → M P 2 → (64 × 64C5)
→ M P 2 → 384F C → 192F C → 10SM → Output.
(16)
We first prune only the first fully connected layer (the one
furthest from the output) for clarity. Figure 2 shows the classification accuracy vs compression ratio for FeTa, 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, FeTa has 10% higher accuracy on average
while being the same or marginally worse than LOBS and
NetTrim.
For the task of pruning the first fully connected layer we
also show detailed comparison results for all methods in
Table 1. For the LeNet-5 model, FeTa achieves the same accuracy as Net-Trim while being 25× 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
while being 5× faster, and is significantly better than Thresholding.
Table 1. Test accuracy rates (%) prune only first fully connected
layer.

Table 2. Test accuracy rates (%) prune all fully connected layers.

L E N ET-5
N ET-T RIM
LOBS
T HRESHOLD
F E TA
C IFAR N ET
N ET-T RIM
LOBS
T HRESHOLD
F E TA

O RIGINAL

CR

P RUNED

T IME

99.2%
99.2%
99.2%
99.2%

90%
90%
90%
90%

95%
97%
64%
95%

500 S
97 S
38S

O RIGINAL

CR

P RUNED

T IME

86%
86%
86%
86%

90%
90%
90%

83.4%
64%
71%

3 H 15 MIN
25MIN

marginally worse results while being 13× faster than NetTrim and 2.5× faster than LOBS. For the Cifar experiment
FeTa shows a bigger degradation in performance compared
to LOBS while remaining 8× faster. Thresholding achieves
a notably bad result of 64% accuracy, which makes the
method essentially inapplicable for multilayer pruning.
We note here that the degraded performance of FeTa for
two layer pruning in Cifar is due to a poor solution for the
second dense layer. By combining FeTa for the first dense
layer and Thresholding for the second dense layer one can
achieve 77% accuracy for the same computational cost.
Furthermore as mentioned in Dong et al. (2017) 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.
4.2.2. L OW R ANK R EGULARISATION

L E N ET-5
N ET-T RIM
LOBS
T HRESHOLD
F E TA
C IFAR N ET
N ET-T RIM
LOBS
T HRESHOLD
F E TA

O RIGINAL

CR

P RUNED

T IME

99.2%
99.2%
99.2%
99.2%

95%
95%
95%
95%

95%
97%
83%
95%

455 S
90 S
18S

O RIGINAL

CR

P RUNED

T IME

86%
86%
86%
86%

90%
90%
90%

83.4%
73%
80%

3 H 15 MIN
20MIN

For the CifarNet model we see in Table 1 that 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× faster.
Next we prune both the fully connected layers in the two
architectures to the same sparsity level and show the results
in Table 2. We lower the achieved sparsity for all methods
to 90%. For MNIST The accuracy results are the same as
pruning a single layer, with FeTa achieving the same or

As a proof of concept for the generality of our approach
we apply our method while imposing low-rank regularisation on the learned matrix U . For low rank k we compare two methods (i) FeTa 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 Figure 3.
In the above given U ∈ Rd1 ×d2 the Commpression Ratio
(CR) is defined as CR = (k ∗d1 +k +k ∗d2 )/(d1 ∗d2 ). The
results are in line with the l1 regularisation, with significant
degredation in classification accuracy for Hard Thresholding
above 85% CR.

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

(a)

(b)

Figure 2. Accuracy vs Sparsity: (a)We plot the classification accuracy of the pruned LeNet-5 architecture for different sparsity levels.
Until the 80% sparsity level roughly all methods are equal. For sparsity levels greater than 80% FeTa clearly outperforms Hard
Thresholding while remaining competitive with LOBS. (b)We plot the classification accuracy of the pruned CifarNet architecture for
different sparsity levels. The results are consistent with the LeNet-5 experiment.

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

(a) LeNet-5

(b) CifarNet

Figure 3. Accuracy vs CR: (a)We plot the classification accuracy
of the low-rank compressed LeNet-5 architecture for different CR
levels. Until the 85% CR level roughly all methods are equal.
For CR levels greater than 85% FeTa clearly outperforms Hard
Thresholding. (b)We plot the classification accuracy of the pruned
CifarNet architecture for different CR levels. The results are consistent with the LeNet-5 experiment.

4.3. Generalization Error
According to our theoretical analysis the GE drops exponentially with remaining layer depth. 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 Figure 4.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 Raghu et al. (2016) Han et al. (2015b)
for much larger networks the degradation is entirely smooth.

We now aim to see how well our bound captures this exponential behaviour. We take two networks ga pruned
at layer 3 and an unpruned network gb and make a number of simplifying assumptions. First we assume that
in
Theorem
3.3 B = 0 such that GE(g? ) ≤ A · (γ −
√
P
Q
L
i=0

Ci2
Q

L
j=i+1

||W j ||2 − k
2

) . This is logical as B includes
only log terms. Assuming that the bounds are tight we now
aim to calculate
i

||W i ||2

GE(ga )
=
GE(gb )
=

γ−

PL

i=0 (

!− k2
p a Qi
Ci2 / j=0 ||W j ||2 )
γ

o(s̃)
PL p a QN
o(s̃) − i=0 ( Ci2 j=i+1 ||W j ||2 )

! k2

(17)
We can use the above to make predictions for the
GE of the pruned network by noting that GE(ga ) =

 k2
PL p a QN
GE(gb ) o(s̃)/(o(s̃) − i=0 ( Ci2
j=i+1 ||W j ||2 ))
as we know that GE(gb ) ≈ 0.01 for the unpruned network
and we have managed to avoid the cumbersome A

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

(a) Single Layer

(b) Multiple Layers

Figure 4. Layer Robustness: We plot the theoretical prediction for the GE (dashed lines) and the empirical value of the GE (solid lines)
for single layer pruning (a) and multilayer (b) pruning. Our theoretical predictions are tight for layers with small remaining depth but are
loose for layers with big remaining depth. We first focus on pruning for 80% sparsity. Layer i = 0 is as predicted exponentially less robust
compared to layers i = {1, 2, 3}. We then focus on pruning layer i = 0 and layers i ≥ 0 for 80% sparsity. We see that even though the
GE errors for i > 0 are negligible the GE error for i ≥ 0 is exponentially greater than the sum of the GEs when pruning i = 0 and i > 0.
Interestingly in the empirical GE estimate there exists an artifact around 90% sparsity which is partially captured by our prediction.

parameter. Next we make the assumption that k ≈ 20.
Dimensionality values 20 − 40 are common for the
MNIST dataset and result from a simple dimensionality
analysis using PCA. We also deviate slightly from
p our
a]
theory by using the minimum layerwise error mini [ Ci2
for each sparsity level, as well as the average scores
Es∼S [o(x, g(x))]. We plot the theoretical predictions
for single layer pruning in Figure 4.a and the theoretical
predictions for multilayer pruning in Figure 4.b. We see
that, while loose, the theoretical predictions correctly
capture qualitatively the behaviour of the GE. Specifically,
layers, as predicted, are exponentially less robust with
remaining layer depth. Also , as predicted, when pruning
multiple layers the resulting GE is exponentially greater
than the sum of the individual GEs.

5. Conclusion
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 increase in the GE. We provided
a theoretical analysis of the increase in GE resulting from
bounded perturbations to the hidden layer weights, of which
pruning is a special case. This analysis correctly predicts
the previously observed phenomenon that network layers
closer to the input are exponentially less robust to pruning
compared to layers close to the output. Experiments on

common feedforward architectures validated our results.

References
Aghasi, Alireza, Nguyen, Nam, and Romberg, Justin. Nettrim: A layer-wise convex pruning of deep neural networks. arXiv preprint arXiv:1611.05162, 2016.
Bartlett, Peter, Foster, Dylan J, and Telgarsky, Matus.
Spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1706.08498, 2017.
Blundell, Charles, Cornebise, Julien, Kavukcuoglu, Koray,
and Wierstra, Daan. Weight uncertainty in neural networks. arXiv preprint arXiv:1505.05424, 2015.
Chen, Wenlin, Wilson, James, Tyree, Stephen, Weinberger,
Kilian, and Chen, Yixin. Compressing neural networks
with the hashing trick. In International Conference on
Machine Learning, pp. 2285–2294, 2015.
Courbariaux, Matthieu, Hubara, Itay, Soudry, Daniel, ElYaniv, Ran, and Bengio, Yoshua. Binarized neural networks: Training deep neural networks with weights
and activations constrained to+ 1 or-1. arXiv preprint
arXiv:1602.02830, 2016.
Dong, Xin, Chen, Shangyu, and Pan, Sinno Jialin. Learning
to prune deep neural networks via layer-wise optimal
brain surgeon. arXiv preprint arXiv:1705.07565, 2017.

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

Fawzi, Alhussein, Davies, Mike, and Frossard, Pascal.
Dictionary learning for fast classification based on softthresholding. International Journal of Computer Vision,
114(2-3):306–321, 2015.

Tao, Pham Dinh and An, Le Thi Hoai. Convex analysis
approach to dc programming: Theory, algorithms and
applications. Acta Mathematica Vietnamica, 22(1):289–
355, 1997.

Han, Song, Mao, Huizi, and Dally, William J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv
preprint arXiv:1510.00149, 2015a.

Wolfe, Nikolas, Sharma, Aditya, Drude, Lukas, and Raj,
Bhiksha. The incredible shrinking neural network: New
perspectives on learning representations through the lens
of pruning. arXiv preprint arXiv:1701.04465, 2017.

Han, Song, Pool, Jeff, Tran, John, and Dally, William.
Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems, pp. 1135–1143, 2015b.

Xu, Huan and Mannor, Shie. Robustness and generalization.
Machine learning, 86(3):391–423, 2012.

Hou, Lu, Yao, Quanming, and Kwok, James T. Lossaware binarization of deep networks. arXiv preprint
arXiv:1611.01600, 2016.
Kim, Yong-Deok, Park, Eunhyeok, Yoo, Sungjoo, Choi, Taelim, Yang, Lu, and Shin, Dongjun. Compression of deep
convolutional neural networks for fast and low power
mobile applications. arXiv preprint arXiv:1511.06530,
2015.
LeCun, Yann, Bengio, Yoshua, and Hinton, Geoffrey. Deep
learning. Nature, 521(7553):436–444, 2015.
Louizos, Christos, Ullrich, Karen, and Welling, Max.
Bayesian compression for deep learning. arXiv preprint
arXiv:1705.08665, 2017.
Molchanov, Dmitry, Ashukha, Arsenii, and Vetrov, Dmitry.
Variational dropout sparsifies deep neural networks. arXiv
preprint arXiv:1701.05369, 2017.
Neyshabur, Behnam, Bhojanapalli, Srinadh, McAllester,
David, and Srebro, Nathan. A pac-bayesian approach to
spectrally-normalized margin bounds for neural networks.
arXiv preprint arXiv:1707.09564, 2017.
Nitanda, Atsushi. Stochastic proximal gradient descent
with acceleration techniques. In Advances in Neural
Information Processing Systems, pp. 1574–1582, 2014.
Novikov, Alexander, Podoprikhin, Dmitrii, Osokin, Anton,
and Vetrov, Dmitry P. Tensorizing neural networks. In
Advances in Neural Information Processing Systems, pp.
442–450, 2015.
Raghu, Maithra, Poole, Ben, Kleinberg, Jon, Ganguli, Surya,
and Sohl-Dickstein, Jascha. On the expressive power of
deep neural networks. arXiv preprint arXiv:1606.05336,
2016.
Sokolic, Jure, Giryes, Raja, Sapiro, Guillermo, and Rodrigues, Miguel RD. Robust large margin deep neural
networks. IEEE Transactions on Signal Processing, 2017.

Yang, Zichao, Moczulski, Marcin, Denil, Misha, de Freitas,
Nando, Smola, Alex, Song, Le, and Wang, Ziyu. Deep
fried convnets. In Proceedings of the IEEE International
Conference on Computer Vision, pp. 1476–1483, 2015.

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

A. Proof of theorem 3.1.
We denote by f 1 (·, W 1 ) the original representation and by f 2 (·, W 2 ) the pruned representation. We assume that, after
training, ∀s ∈ Sm ||f 1 (a, W 1 ) − f 2 (a, W 2 )||22 ≤ C1 . Second, we assume that ∀s ∈ S ∃si ∈ Sm ⇒ ||a − ai ||22 ≤ .
Third the linear operators in W 1 , W 2 are frames with upper frame bounds B1 , B2 respectively. The following two lemmas
will be useful:
Lemma .1. The operator f 1 (·, W 1 ) is Lipschitz continuous with upper Lipschitz constant B1 .
Proof. See ? for details, the derivation is not entirely trivial due to the non-smoothness of the rectifier non-linearity.
Lemma .2. The operator f 2 (·, W 2 ) is Lipschitz continuous with upper Lipschitz constant B2 .
Proof. We see that:

d
dx ρ(x)

=

d 1
dx β log(1 + exp(βx))

=

exp(βx)
1+exp(βx)

≤ 1. Therefore the smooth approximation to the rectifier

non-linarity is Lipschitz smooth with Lipschitz constant k = 1. Then ||f 2 (x, W 2 ) − f 2 (y, W 2 )||22 ≤ k||W 2 x − W 2 y||22 ≤
||W 2 (x − y)||22 ≤ B2 ||x − y||22 .
We drop the W i from the layer notation for clarity. Using the triangle inequality
||f 1 (a) − f 2 (a)||22 = ||f 1 (a) + f 1 (ai ) − f 1 (ai ) − f 2 (a)||22
≤ ||f 1 (a) − f 1 (ai )||22 + ||f 1 (ai ) − f 2 (a)||22
= ||f 1 (a) − f 1 (ai )||22 + ||f 1 (ai ) + f 2 (ai ) − f 2 (ai ) − f 2 (a)||22
≤ ||f 1 (a) − f 1 (ai )||22 + ||f 1 (ai ) − f 2 (ai )||22 + ||f 2 (ai ) − f 2 (a)||22
≤ B1 ||ai −

a||22

+ C + B2 ||ai −

(18)

a||22

= C1 + (B1 + B2 )||ai − a||22
≤ C1 + (B1 + B2 ),
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 Cm -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 0 ≤ l(g(x), y) ≤ M .
Definition .1. An algorithm g(x) is (K, (Sm )) robust if S can be partitioned into K disjoint sets, denoted by {Tt }K
t=1 ,
such that ∀si ∈ Sm , ∀s ∈ S,
si , s ∈ Tt , ⇒ |l(g(xi ), yi ) − l(g(x), y)| ≤ (Sm ).

(19)

Now let ˆl(·) and lemp (·) denote the expected error and the training error, i.e,
ˆl(g) , Es∼S l(g(x), y);

lemp (g) ,

1 X
l(q(xi ), yi )
m
si ∈Sm

we can then state the following theorem from Xu & Mannor (2012):

(20)

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

Theorem .3. If Sm consists of m i.i.d. samples, and g(x) is (K, (Sm ))-robust, then for any δ > 0, with probability at
least 1 − δ,

r
GE(g) = |ˆl(g) − lemp (g)| ≤ (Sm ) + M

2Kln2 + 2ln(1/δ)
.
m

(21)

The above generic bound can be specified for the case of Cm -regular manifolds as in Sokolic et al. (2017). We recall the
definition of the sample margin γ(si ) as well as the following theorem:
Theorem .4. If there exists γ such that

γ(si ) > γ > 0 ∀si ∈ Sm ,

(22)

then the classifier g(x) is (NY · N (X ; d, γ/2), 0)-robust.
By direct substitution of the above result and the definiton of a Cm -regular manifold into Theorem 6.3 we get:
Corollary .4.1. Assume that X is a (subset of) CM regular k−dimensional manifold, where N (X ; d, ρ) ≤ ( CρM )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 − δ,

s
GE(g) ≤

log(2) · NY · 2k+1 · (CM )k
+
γkm

r

2log(1/δ)
.
m

(23)

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 Sokolic et al. (2017),
Theorem .5. Assume that a DNN classifier g(x), as defined in equation 8, and let x̃ be the training sample with the smallest
score o(s̃) > 0. Then the classification margin is bounded as

o(s̃)
= γ.
i ||W i ||2

γ(si ) ≥ Q

(24)

We now prove our main result. We will denote by x̃ = arg minsi ∈Sm minj6=g(xi ) v Tg(xi )j f (xi ) the training sample with
the smallest score. For this training sample we will denote j ? = arg minj6=g(x̃) v Tg(x̃)j f (x̃) the second best guess of the
√
classifier g(·). Throughout the proof, we will use the notation v ij = 2(δ i − δ j ).
First we assume the score o1 (x̃, g1 (x̃)) of the point x̃ for the original classifier g1 (x). Then, for the second classifier g2 (x),
we take a point x? that lies on the decision boundary between g2 (x̃) and j ? such that o2 (x? , g2 (x̃)) = 0. We assume
for simplicity that, after pruning, the classification decisions do not change such that g1 (x̃) = g2 (x̃). We then make the

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

following calculations

o1 (x̃, g1 (x̃)) = o1 (x̃, g1 (x̃)) − o2 (x? , g2 (x̃)) = v Tg1 (x̃)j ? f 1 (x̃) − v Tg2 (x̃)j ? f 2 (x? )
= v Tg2 (x̃)j ? (f 1 (x̃) − f 2 (x? ))
≤ ||v Tg2 (x̃)j ? ||2 ||f 1 (x̃) − f 2 (x? )||2 = ||fL1 (x̃) − fL2 (x? )||2
Y
≤
||W i ||2 ||fi1? (x̃) − fi2? (x? )||2
i>i?

≤

Y

||W i ||2 {||fi1? (x̃) − fi1? (x? )||2 + ||fi1? (x? ) − fi2? (x? )||2 }

(25)

i>i?

≤

Y

≤

Y

p
||W i ||2 {||fi1? (x̃) − fi1? (x? )||2 + C2 }

i>i?

||W i ||2 ||x̃ − x? ||2 +

||W i ||2

p

C2

i>i?

i

≤

Y

Y

||W i ||2 γ2 (si ) +

Y

||W i ||2

p

C2 ,

i>i?

i

where we used Theorem 3.1 in line 5, since x? is not a training sample. From the above we can therefore write

√

Q
C2 i>i? ||W i ||2
≤ γ2 (x̃).
i ||W i ||2

o1 (x̃, g1 (x̃)) −
Q

(26)

By following the derivation of the margin from the original paper Sokolic et al. (2017) and taking into account the definition
of the margin we know that

o1 (x̃, g1 (x̃))
γ= Q
≤ γ1 (x̃).
i ||W i ||2

(27)

Therefore we can finally write

√
γ−

Q
C2 i>i? ||W i ||2
Q
≤ γ2 (x̃).
i ||W i ||2

(28)

√

The theorem follows from direct application of Corollary 3.1.1. Note that if γ −
becomes vacuous, as by definition 0 ≤ γ2 (x̃).

Q
C2 i>i? ||W i ||2
Q
i ||W i ||2

< 0 the derived bound

C. Proof of theorem 3.3.
We start as in theorem 3.2 by assuming the score o1 (x̃, g1 (x̃)) of the point x̃ for the original classifier g1 (x). Then,
for the second classifier g2 (x), we take a point x? that lies on the decision boundary between g2 (x̃) and j ? such that

FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees

o2 (x? , g2 (x̃)) = 0. We assume as before that the classification decisions do not change such that g1 (x̃) = g2 (x̃). We write

o1 (x̃, g1 (x̃)) = o1 (x̃, g1 (x̃)) − o2 (x? , g2 (x̃)) = v Tg1 (x̃)j ? f 1 (x̃) − v Tg2 (x̃)j ? f 2 (x? )
= v Tg2 (x̃)j ? (f 1 (x̃) − f 2 (x? ))
≤ ||v Tg2 (x̃)j ? ||2 ||f 1 (x̃) − f 2 (x? )||2 = ||fL1 (x̃) − fL2 (x? )||2
≤ ||fL1 (x̃) − fL1 (x? )||2 + ||fL1 (x? ) − fL2 (x? )||2
p
≤ ||fL1 (x̃) − fL1 (x? )||2 + CL2
p
1
2
≤ ||W L ||2 ||fL−1
(x̃) − fL−1
(x? )||2 + CL2
1
1
1
2
≤ ||W L ||2 {||fL−1
(x̃) − fL−1
(x? )||2 + ||fL−1
(x? ) − fL−1
(x? )||2 } +
p
p
1
1
≤ ||W L ||2 {||fL−1
(x̃) − fL−1
(x? )||2 + CL−1,2 } + CL2
p
p
1
1
≤ ||W L ||2 ||fL−1
(x̃) − fL−1
(x? )||2 + ||W L ||2 CL−1,2 + CL2

p

CL2

(29)

≤ ...
≤

Y

||W i ||2 ||x̃ − x? ||2 +

i

≤

L p
X
i=0

Y

||W i ||2 γ2 (si ) +

i

L p
X

L
Y

Ci2

||W j ||2

j=i+1
L
Y

Ci2

||W j ||2 .

j=i+1

i=0

We can then write
o1 (x̃, g1 (x̃)) −

PL √
i=0

Q

i

Ci2

QL

j=i+1

||W j ||2

||W i ||2

≤ γ2 (x̃).

(30)

Then as before
PL √
γ−

i=0

Ci2
Q

QL

j=i+1

i ||W i ||2

The theorem follows from direct application of Corollary 3.1.1.

||W j ||2

≤ γ2 (x̃).

(31)

