Title: DATA-DEPENDENT CORESETS FOR COMPRESSING NEURAL NETWORKS WITH APPLICATIONS TO GENER-ALIZATION BOUNDS

Abstract: We present an efficient coresets-based neural network compression algorithm that sparsifies the parameters of a trained fully-connected neural network in a manner that provably approximates the network's output. Our approach is based on an importance sampling scheme that judiciously defines a sampling distribution over the neural network parameters, and as a result, retains parameters of high importance while discarding redundant ones. We leverage a novel, empirical notion of sensitivity and extend traditional coreset constructions to the application of compressing parameters. Our theoretical analysis establishes guarantees on the size and accuracy of the resulting compressed network and gives rise to generalization bounds that may provide new insights into the generalization properties of neural networks. We demonstrate the practical effectiveness of our algorithm on a variety of neural network configurations and real-world data sets.

1. INTRODUCTION:

Within the past decade, large-scale neural networks have demonstrated unprecedented empirical success in high-impact applications such as object classification, speech recognition, computer vision, and natural language processing. However, with the ever-increasing size of state-of-the-art neural networks, the resulting storage requirements and performance of these models are becoming increasingly prohibitive in terms of both time and space. Recently proposed architectures for neural networks, such as those in Krizhevsky et al. (2012); Long et al. (2015) ; Badrinarayanan et al. (2015) , contain millions of parameters, rendering them prohibitive to deploy on platforms that are resource-constrained, e.g., embedded devices, mobile phones, or small scale robotic platforms.

In this work, we consider the problem of sparsifying the parameters of a trained fully-connected neural network in a principled way so that the output of the compressed neural network is approximately preserved. We introduce a neural network compression approach based on identifying and removing weighted edges with low relative importance via coresets, small weighted subsets of the original set that approximate the pertinent cost function. Our compression algorithm hinges on extensions of the traditional sensitivity-based coresets framework (Langberg & Schulman, 2010; Braverman et al., 2016) , and to the best of our knowledge, is the first to apply coresets to parameter downsizing. In this regard, our work aims to simultaneously introduce a practical algorithm for compressing neural network parameters with provable guarantees and close the research gap in prior coresets work, which has predominantly focused on compressing input data points.

In particular, this paper contributes the following:

1. A coreset approach to compressing problem-specific parameters based on a novel, empirical notion of sensitivity that extends state-of-the-art coreset constructions. 2. An efficient neural network compression algorithm, CoreNet, based on our extended coreset approach that sparsifies the parameters via importance sampling of weighted edges. 3. Extensions of the CoreNet method, CoreNet+ and CoreNet++, that improve upon the edge sampling approach by additionally performing neuron pruning and amplification.

4. Analytical results establishing guarantees on the approximation accuracy, size, and generalization of the compressed neural network.

5. Evaluations on real-world data sets that demonstrate the practical effectiveness of our algorithm in compressing neural network parameters and validate our theoretical results.

2. RELATED WORK:

Our work builds upon the following prior work in coresets and compression approaches. Wen et al., 2016) . Despite their practical effectiveness in compressing neural networks, these works generally lack performance guarantees on the quality of their approximations and/or the size of the resulting compressed network.

Coresets

Weight Pruning Similar to our proposed method, weight pruning (LeCun et al., 1990) hinges on the idea that only a few dominant weights within a layer are required to approximately preserve the output. Approaches of this flavor have been investigated by Lebedev 1984) and proved generalization bounds based on succinct reparameterizations of the original neural network. Building upon the work of Arora et al. (2018) , we extend our theoretical compression results to establish novel generalization bounds for fully-connected neural networks. Unlike the method of Arora et al. (2018) , which exhibits guarantees of the compressed network's performance only on the set of training points, our method's guarantees hold (probabilistically) for any random point drawn from the distribution. In addition, we establish that our method can ε-approximate the neural network output neuron-wise, which is stronger than the norm-based guarantee of Arora et al. (2018) .

In contrast to prior work, this paper addresses the problem of compressing a fully-connected neural network while provably preserving the network's output. Unlike previous theoretically-grounded compression approaches -which provide guarantees in terms of the normed difference -, our method provides the stronger entry-wise approximation guarantee, even for points outside of the available data set. As our empirical results show, ensuring that the output of the compressed network entry-wise approximates that of the original network is critical to retaining high classification accuracy. Overall, our compression approach remedies the shortcomings of prior approaches in that it (i) exhibits favorable theoretical properties, (ii) is computationally efficient, e.g., does not require retraining of the neural network, (iii) is easy to implement, and (iv) can be used in conjunction with other compression approaches -such as quantization or Huffman coding -to obtain further improved compression rates.

3. PROBLEM DEFINITION:



3.1. FULLY-CONNECTED NEURAL NETWORKS:

A feedforward fully-connected neural network with L ∈ N + layers and parameters θ defines a mapping

f θ : X → Y for a given input x ∈ X ⊆ R d to an output y ∈ Y ⊆ R k as follows. Let η ∈ N + denote the number of neurons in layer ∈ [L]

, where [L] = {1, . . . , L} denotes the index set, and where

η 1 = d and η L = k. Further, let η = L =2 η and η * = max ∈{2,...,L} η . For layers ∈ {2, . . . , L}, let W ∈ R η ×η -1

be the weight matrix for layer with entries denoted by w ij , rows denoted by

w i ∈ R 1×η -1

, and θ = (W 2 , . . . , W L ). For notational simplicity, we assume that the bias is embedded in the weight matrix. Then for an input vector

x ∈ R d , let a 1 = x and z = W a -1 ∈ R η , ∀ ∈ {2, . . . , L}, where a -1 = φ(z -1 ) ∈ R η -1

denotes the activation. We consider the activation function to be the Rectified Linear Unit (ReLU) function, i.e., φ(•) = max{• , 0} (entry-wise, if the input is a vector). The output of the network for an input x is f θ (x) = z L , and in particular, for classification tasks the prediction is

argmax i∈[k] f θ (x) i = argmax i∈[k] z L i .

3.2. NEURAL NETWORK CORESET PROBLEM:

Consider the setting where a neural network f θ (•) has been trained on a training set of independent and identically distributed (i.i.d.) samples from a joint distribution on X × Y, yielding parameters θ = (W 2 , . . . , W L ). We further denote the input points of a validation data set as P = {x i } n i=1 ⊆ X and the marginal distribution over the input space X as D. We define the size of the parameter tuple θ, nnz(θ), to be the sum of the number of non-zero entries in the weight matrices W 2 , . . . , W L .

For any given ε, δ ∈ (0, 1), our overarching goal is to generate a reparameterization θ, yielding the neural network f θ (•), using a randomized algorithm, such that nnz( θ) nnz(θ), and the neural network output f θ (x), x ∼ D can be approximated up to 1 ± ε multiplicative error with probability greater than 1 -δ. We define the 1 ± ε multiplicative error between two k-dimensional vectors a, b ∈ R k as the following entry-wise bound:

a ∈ (1 ± ε)b ⇔ a i ∈ (1 ± ε)b i ∀i ∈ [k],

and formalize the definition of an (ε, δ)-coreset as follows.

Definition 1 ((ε, δ)-coreset). Given user-specified ε, δ ∈ (0, 1), a set of parameters θ = ( Ŵ 2 , . . . , Ŵ L ) is an (ε, δ)-coreset for the network parameterized by θ if for x ∼ D, it holds that

P θ,x (f θ (x) ∈ (1 ± ε)f θ (x)) ≥ 1 -δ,

where P θ,x denotes a probability measure with respect to a random data point x and the output θ generated by a randomized compression scheme.

4. METHOD:

In this section, we introduce our neural network compression algorithm as depicted in Alg. 1. Our method is based on an important sampling-scheme that extends traditional sensitivity-based coreset constructions to the application of compressing parameters.

4.1. CORENET:

Our method (Alg. 1) hinges on the insight that a validation set of data points P i.i.d.

∼ D n can be used to approximate the relative importance, i.e., sensitivity, of each weighted edge with respect to the input data distribution D. For this purpose, we first pick a subsample of the data points S ⊆ P of appropriate size (see Sec. 5 for details) and cache each neuron's activation and compute a neuron-specific constant to be used to determine the required edge sampling complexity (Lines 2-6).

Algorithm 1 CORENET:

Input: ε, δ ∈ (0, 1): error and failure probability, respectively; P ⊆ X : a set of n points from the input space X such that P i.i.d. ∼ D n ; θ = (W 2 , . . . , W L ): parameters of the original uncompressed neural network.

Output: θ = ( Ŵ 2 , . . . , Ŵ L ): sparsified parameter set such that f θ (•) ∈ (1 ± ε)f θ (•) (see Sec. 5 for details). 1: ε ← ε 2 (L-1) ; η * ← max ∈{2,...,L-1} η ; η ← L =2 η ; λ * ← log(η η * )/2; 2: S ← Uniform sample (without replacement) of log (8 η η * /δ) log(η η * ) points from P; 3: a 1 (x) ← x ∀x ∈ S; 4: for x ∈ S do 5:

for ∈ {2, . . . , L} do

6: a (x) ← φ(W a -1 (x)); ∆ i (x) ← k∈[η -1 ] |w ik a -1 k (x)| k∈[η -1 ] w ik a -1 k (x)

; 7: for ∈ {2, . . . , L} do

8: ∆ ← 1 |S| max i∈[η ] x∈S ∆ i (x) + κ, where κ = √ 2λ * 1 + √ 2λ * log (8 η η * /δ) ; 9: Ŵ ← ( 0, . . . , 0) ∈ R η ×η -1 ; ∆ → ← L k= ∆k ; ε ← ε ∆ → ; 10: for all i ∈ [η ] do 11: W+ ← {j ∈ [η -1 ] : w ij > 0}; W-← {j ∈ [η -1 ] : w ij < 0}; 12: ŵ + i ← SPARSIFY(W+, w i , ε , δ, S, a -1 ); ŵ - i ← SPARSIFY(W-, -w i , ε , δ, S, a -1 ); 13: ŵ i ← ŵ + i -ŵ - i ; Ŵ i• ← ŵ i ;

Consolidate the weights into the i th row of Ŵ ; 14: return θ = ( Ŵ 2 , . . . , Ŵ L ); Algorithm 2 SPARSIFY(W, w, ε, δ, S, a(•))

Input: W ⊆ [η -1 ]: index set; w ∈ R 1×η -1

: row vector corresponding to the weights incoming to node i ∈ [η ] in layer ∈ {2, . . . , L}; ε, δ ∈ (0, 1): error and failure probability, respectively; S ⊆ P: subsample of the original point set; a(•): cached activations of previous layer for all x ∈ S. Output: ŵ: sparse weight vector.

1: for j ∈ W do 2: sj ← maxx∈S

w j a j (x) k∈W w k a k (x) ;

Compute the sensitivity of each edge 3: S ← j∈W sj; 4: for j ∈ W do Generate the importance sampling distribution over the incoming edges 5: qj ← s j S ; 6: m ← 8 S log(η η * ) log(8 η/δ) ε 2

;:

Compute the number of required samples 7: C ← a multiset of m samples from W where each j ∈ W is sampled with probability qj;

8: ŵ ← (0, . . . , 0) ∈ R 1×η -1

; Initialize the compressed weight vector 9: for j ∈ C do Update the entries of the sparsified weight matrix according to the samples C 10: ŵj ← ŵj + w j m q j ; Entries are reweighted by1 m q j to ensure unbiasedness of our estimator 11: return ŵ; Subsequently, we apply our core sampling scheme to sparsify the set of incoming weighted edges to each neuron in all layers (Lines 7-13). For technical reasons (see Sec. 5), we perform the sparsification on the positive and negative weighted edges separately and then consolidate the results (Lines 11-13). By repeating this procedure for all neurons in every layer, we obtain a set θ = ( Ŵ 2 , . . . , Ŵ L ) of sparse weight matrices such that the output of each layer and the entire network is approximately preserved, i.e., Ŵ â -1 (x) ≈ W a -1 (x) and f θ (x) ≈ f θ (x), respectively 1 .

4.2. SPARSIFYING WEIGHTS:

The crux of our compression scheme lies in Alg. 2 (invoked twice on Line 12, Alg. 1) and in particular, in the importance sampling scheme used to select a small subset of edges of high importance. The cached activations are used to compute the sensitivity, i.e., relative importance, of each considered incoming edge j ∈ W to neuron i ∈ [η ], ∈ {2, . . . , L} (Alg. 2, Lines 1-2). The relative importance of each edge j is computed as the maximum (over x ∈ S) ratio of the edge's contribution to the sum of contributions of all edges. In other words, the sensitivity s j of an edge j captures the highest (relative) impact j had on the output of neuron i ∈ [η ] in layer across all x ∈ S.

The sensitivities are then used to compute an importance sampling distribution over the incoming weighted edges (Lines 4-5). The intuition behind the importance sampling distribution is that if s j is high, then edge j is more likely to have a high impact on the output of neuron i, therefore we should keep edge j with a higher probability. m edges are then sampled with replacement (Lines 6-7) and the sampled weights are then reweighed to ensure unbiasedness of our estimator (Lines 9-10).

4.3. EXTENSIONS: NEURON PRUNING AND AMPLIFICATION:

In this subsection we outline two improvements to our algorithm that that do not violate any of our theoretical properties and may improve compression rates in practical settings.

Neuron pruning (CoreNet+) Similar to removing redundant edges, we can use the empirical activations to gauge the importance of each neuron. In particular, if the maximum activation (over all evaluations x ∈ S) of a neuron is equal to 0, then the neuron -along with all of the incoming and outgoing edges -can be pruned without significantly affecting the output with reasonable probability. This intuition can be made rigorous under the assumptions outlined in Sec. 5. Amplification (CoreNet++) Coresets that provide stronger approximation guarantees can be constructed via amplification -the procedure of constructing multiple approximations (coresets) ( ŵ i ) 1 , . . . , ( ŵ i ) τ over τ trials, and picking the best one. To evaluate the quality of each approximation, a different subset T ⊆ P \ S can be used to infer performance. In practice, amplification would entail constructing multiple approximations by executing Line 12 of Alg. 1 and picking the one that achieves the lowest relative error on T .

5. ANALYSIS:

In this section, we establish the theoretical guarantees of our neural network compression algorithm (Alg. 1). The full proofs of all the claims presented in this section can be found in the Appendix.

5.1. PRELIMINARIES:

Let x ∼ D be a randomly drawn input point. We explicitly refer to the pre-activation and activation values at layer ∈ {2, . . . , } with respect to the input x ∈ supp(D) as z (x) and a (x), respectively. The values of z (x) and a (x) at each layer will depend on whether or not we compressed the previous layers ∈ {2, . . . , }. To formalize this interdependency, we let ẑ (x) and â (x) denote the respective quantities of layer when we replace the weight matrices W 2 , . . . , W in layers 2, . . . , by Ŵ 2 , . . . , Ŵ , respectively.

For the remainder of this section (Sec. 5) we let ∈ {2, . . . , L} be an arbitrary layer and let i ∈ [η ] be an arbitrary neuron in layer . For purposes of clarity and readability, we will omit the the variable denoting the layer ∈ {2, . . . , L}, the neuron i ∈ [η ], and the incoming edge index j ∈ [η -1 ], whenever they are clear from the context. For example, when referring to the intermediate value of a neuron i ∈ [η ] in layer ∈ {2, . . . , L}, z i (x) = w i , â -1 (x) ∈ R with respect to a point x, we will simply write z(x) = w, a(x) ∈ R, where w := w i ∈ R 1×η -1 and a(x) := a -1 (x) ∈ R η -1 ×1 . Under this notation, the weight of an incoming edge j is denoted by w j ∈ R.

5.2. IMPORTANCE SAMPLING BOUNDS FOR POSITIVE WEIGHTS:

In this subsection, we establish approximation guarantees under the assumption that the weights are positive. Moreover, we will also assume that the input, i.e., the activation from the previous layer, is non-negative (entry-wise). The subsequent subsection will then relax these assumptions to conclude that a neuron's value can be approximated well even when the weights and activations are not all positive and non-negative, respectively. Let W = {j ∈ [η -1 ] : w j > 0} ⊆ [η -1 ] be the set of indices of incoming edges with strictly positive weights. To sample the incoming edges to a neuron, we quantify the relative importance of each edge as follows. Definition 2 (Relative Importance). The importance of an incoming edge j ∈ W with respect to an input x ∈ supp(D) is given by the function g j (x), where g j (x) = wj aj (x)

k∈W w k a k (x) ∀j ∈ W.

Note that g j (x) is a function of the random variable x ∼ D. We now present our first assumption that pertains to the Cumulative Distribution Function (CDF) of the relative importance random variable. Assumption 1. For all j ∈ W, the CDF of the random variable g j (x), denoted by F j (•), satisfies

F j ( M /K) ≤ exp(-1/K), where M = min{x ∈ [0, 1] : F j (x) = 1}, and K ∈ [2, log(η η * )] is a universal constant. 2

Assumption 1 is a technical assumption on the ratio of the weighted activations that will enable us to rule out pathological problem instances where the relative importance of each edge cannot be well-approximated using a small number of data points S ⊆ P. Henceforth, we consider a uniformly drawn (without replacement) subsample S ⊆ P as in Line 2 of Alg. 1, where |S| = log (8 η η * /δ) log(η η * ) , and define the sensitivity of an edge as follows.

Definition 3 (Empirical Sensitivity). Let S ⊆ P be a subset of distinct points from P i.i.d. ∼ D n .Then, the sensitivity over positive edges j ∈ W directed to a neuron is defined as s j = max x∈S g j (x).

Our first lemma establishes a core result that relates the weighted sum with respect to the sparse row vector ŵ, k∈W ŵk âk (x), to the value of the of the weighted sum with respect to the ground-truth row vector w, k∈W w k âk (x). We remark that there is randomness with respect to the randomly generated row vector ŵ i , a randomly drawn input x ∼ D, and the function â(•) = â -1 (•) defined by the randomly generated matrices Ŵ 2 , . . . , Ŵ -1 in the previous layers. Unless otherwise stated, we will henceforth use the shorthand notation P(•) to denote P ŵ , x, â -1 (•). Moreover, for ease of presentation, we will first condition on the event E1 /2 that â(x) ∈ (1 ± 1 /2)a(x) holds. This conditioning will simplify the preliminary analysis and will be removed in our subsequent results. Lemma 1 (Positive-Weights Sparsification). Let ε, δ ∈ (0, 1), and x ∼ D. SPARSIFY(W, w, ε, δ, S, a(•)) generates a row vector ŵ such that

P k∈W ŵk âk (x) / ∈ (1 ± ε) k∈W w k âk (x) | E1 /2 ≤ 3δ 8η

where nnz( ŵ) ≤ 8 S log(η η * ) log(8 η/δ) ε2 

, and S = j∈W s j .

5.3. IMPORTANCE SAMPLING BOUNDS:

We now relax the requirement that the weights are strictly positive and instead consider the following index sets that partition the weighted edges:

W + = {j ∈ [η -1 ] : w j > 0} and W -= {j ∈ [η -1 ] : w j < 0}.

We still assume that the incoming activations from the previous layers are positive (this assumption can be relaxed as discussed in Appendix A.2.4). We define ∆ i (x) for a point x ∼ D

and neuron i ∈ [η ] as ∆ i (x) = k∈[η -1 ] |w ik a -1 k (x)| | k∈[η -1 ] w ik a -1 k (x)| .

The following assumption serves a similar purpose as does Assumption 1 in that it enables us to approximate the random variable ∆ i (x) via an empirical estimate over a small-sized sample of data points S ⊆ P. Assumption 2 (Subexponentiality of ∆ i (x)). For any layer ∈ {2, . . . , L} and neuron i ∈ [η ], the centered random variable

∆ = ∆ i (x) -E x∼D [∆ i (x)] is subexponential (Vershynin, 2016) with parameter λ ≤ log(η η * )/2, i.e., E [exp (s∆)] ≤ exp(s 2 λ 2 ) ∀|s| ≤ 1 λ . 2

For ε ∈ (0, 1) and ∈ {2, . . . , L}, we let ε = ε 2 (L-1) and define ε = ε

∆ → = ε 2 (L-1) L k= ∆k , where ∆ = 1 |S| max i∈[η ] x ∈S ∆ i (x ) + κ.

To formalize the interlayer dependencies, for each i ∈ [η ] we let E i denote the (desirable) event that ẑ i (x) ∈ (1 ± 2 ( -1) ε +1 ) z i (x) holds, and let E = ∩ i∈[η ] E i be the intersection over the events corresponding to each neuron in layer .

Lemma 2 (Conditional Neuron Value Approximation). Let ε, δ ∈ (0, 1), ∈ {2, . . . , L}, i ∈ [η ], and x ∼ D. CORENET generates a row vector

EQUATION

where

ε = ε ∆ → and nnz( ŵ i ) ≤ 8 S log(η η * ) log(8 η/δ) ε 2

+ 1, where S = j∈W+ s j + j∈W-s j .

The following core result establishes unconditional layer-wise approximation guarantees and culminates in our main compression theorem.

Lemma 3 (Layer-wise Approximation). Let ε, δ ∈ (0, 1), ∈ {2, . . . , L}, and x ∼ D. CORENET generates a sparse weight matrix Ŵ ∈ R η ×η -1 such that, for ẑ (x) = Ŵ â (x),

P ( Ŵ 2 ,..., Ŵ ), x (E ) = P ( Ŵ 2 ,..., Ŵ ), x ẑ (x) ∈ (1 ± 2 ( -1) ε +1 ) z (x) ≥ 1 - δ =2 η η .

Theorem 4 (Network Compression). For ε, δ ∈ (0, 1), Algorithm 1 generates a set of parameters

θ = ( Ŵ 2 , . . . , Ŵ L ) of size nnz( θ) ≤ L =2 η i=1 32 (L -1) 2 ( ∆ → ) 2 S i log(η η * ) log(8 η/δ) ε 2 + 1 in O η η * log η η * /δ time such that P θ, x∼D f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 -δ.

We note that we can obtain a guarantee for a set of n randomly drawn points by invoking Theorem 4 with δ = δ/n and union-bounding over the failure probabilities, while only increasing the sampling complexity logarithmically, as formalized in Corollary 12, Appendix A.2.

5.4. GENERALIZATION BOUNDS:

As a corollary to our main results, we obtain novel generalization bounds for neural networks in terms of empirical sensitivity. Following the terminology of Arora et al. (2018) , the expected margin loss of a classifier f θ : R d → R k parameterized by θ with respect to a desired margin γ > 0 and distribution D is defined by

L γ (f θ ) = P (x,y)∼D X ,Y (f θ (x) y ≤ γ + max i =y f θ (x) i ).

We let Lγ denote the empirical estimate of the margin loss. The following corollary follows directly from the argument presented in Arora et al. ( 2018) and Theorem 4.

Corollary 5 (Generalization Bounds). For any δ ∈ (0, 1) and margin γ > 0, Alg. 1 generates weights θ such that with probability at least 1 -δ, the expected error L 0 (f θ ) with respect to the points in P ⊆ X , |P| = n, is bounded by

L 0 (f θ ) ≤ Lγ (f θ ) + O   max x∈P f θ (x) 2 2 L 2 L =2 ( ∆ → ) 2 η i=1 S i γ 2 n   .

6. RESULTS:

In this section, we evaluate the practical effectiveness of our compression algorithm on popular benchmark data sets (MNIST (LeCun et al., 1998), FashionMNIST (Xiao et al., 2017) , and CIFAR-10 (Krizhevsky & Hinton, 2009)) and varying fully-connected trained neural network configurations: 2 to 5 hidden layers, 100 to 1000 hidden units, either fixed hidden sizes or decreasing hidden size denoted by pyramid in the figures. We further compare the effectiveness of our sampling scheme in reducing the number of non-zero parameters of a network, i.e., in sparsifying the weight matrices, to that of uniform sampling, Singular Value Decomposition (SVD), and current state-of-the-art sampling schemes for matrix sparsification (Drineas & Zouzias, 2011; Achlioptas et al., 2013; Kundu & Drineas, 2014) , which are based on matrix norms -1 and 2 (Frobenius). The details of the experimental setup and results of additional evaluations may be found in Appendix B.

Experiment Setup We compare against three variations of our compression algorithm: (i) sole edge sampling (CoreNet), (ii) edge sampling with neuron pruning (CoreNet+), and (iii) edge sampling with neuron pruning and amplification (CoreNet++). For comparison, we evaluated the average relative error in output ( 1 -norm) and average drop in classification accuracy relative to the accuracy of the uncompressed network. Both metrics were evaluated on a previously unseen test set.

Results Results for varying architectures and datasets are depicted in Figures 1 and 2 for the average drop in classification accuracy and relative error ( 1 -norm), respectively. As apparent from Figure 1 , we are able to compress networks to about 15% of their original size without significant loss of accuracy for networks trained on MNIST and FashionMNIST, and to about 50% of their original size for CIFAR. Discussion The simulation results presented in this section validate our theoretical results established in Sec. 5. In particular, our empirical results indicate that we are able to outperform networks compressed via competing methods in matrix sparsification across all considered experiments and trials.

The results presented in this section further suggest that empirical sensitivity can effectively capture the relative importance of neural network parameters, leading to a more informed importance sampling scheme. Moreover, the relative performance of our algorithm tends to increase as we consider deeper architectures. These findings suggest that our algorithm may also be effective in compressing modern convolutional architectures, which tend to be very deep.

7. CONCLUSION:

We presented a coresets-based neural network compression algorithm for compressing the parameters of a trained fully-connected neural network in a manner that approximately preserves the network's output. Our method and analysis extend traditional coreset constructions to the application of compressing parameters, which may be of independent interest. Our work distinguishes itself from prior approaches in that it establishes theoretical guarantees on the approximation accuracy and size of the generated compressed network. As a corollary to our analysis, we obtain generalization bounds for neural networks, which may provide novel insights on the generalization properties of neural networks. We empirically demonstrated the practical effectiveness of our compression algorithm on a variety of neural network configurations and real-world data sets. In future work, we plan to extend our algorithm and analysis to compress Convolutional Neural Networks (CNNs) and other network architectures. We conjecture that our compression algorithm can be used to reduce storage requirements of neural network models and enable fast inference in practical settings. We now establish a couple of technical results that will quantify the accuracy of our approximations of edge importance (i.e., sensitivity). Lemma 6. Let K > 0 be a universal constant and let D be a distribution with CDF F (•) satisfying

F ( M /K) ≤ exp(-1/K), where M = min{x ∈ [0, 1] : F (x) = 1}. Let P = {X 1 , . . . , X n } be a set of n = |P| i.i.d.

samples each drawn from the distribution D. Let X n+1 ∼ D be an i.i.d. sample. Then,

P K max X∈P X < X n+1 ≤ exp(-n/K)

Proof. Let X max = max X∈P ; then,

P(K X max < X n+1 ) = M 0 P(X max < x /K|X n+1 = x) d P(x) = M 0 P (X < x /K) n d P(x) since X 1 , . . . , X n are i.i.d. ≤ M 0 F ( x /K) n d P(x) where F (•) is the CDF of X ∼ D ≤ F ( M /K) n M 0 d P(x) by monotonicity of F = F ( M /K) n ≤ exp(-n/K) CDF Assumption,

and this completes the proof.

We now proceed to establish that the notion of empirical sensitivity is a good approximation for the relative importance. For this purpose, let the relative importance ĝj (x) of an edge j after the previous layers have already been compressed be

ĝj (x) = w j âj (x) k∈W w k âk (x) . Lemma 7 (Empirical Sensitivity Approximation). Let ε ∈ (0, 1/2), δ ∈ (0, 1), ∈ {2, . . . , L}, Consider a set S = {x 1 , . . . , x n } ⊆ P of size |S| ≥ log (8 η η * /δ) log(η η * ) . Then, conditioned on the event E1 /2 occurring, i.e., â(x) ∈ (1 ± 1 /2)a(x), P x∼D ∃j ∈ W : C s j < ĝj (x) | E1 /2 ≤ δ 8 η , where C = 3 log(η η * ) and W ⊆ [η -1 ].

Proof. Consider an arbitrary j ∈ W and x ∈ S corresponding to g j (x ) with CDF F j (•) and recall that M = min{x ∈ [0, 1] : F j (x) = 1} as in Assumption 1. Note that by Assumption 1, we have

F ( M /K) ≤ exp(-1/K),

and so the random variables g j (x ) for x ∈ S satisfy the CDF condition required by Lemma 6. Now let E be the event that K s j < g j (x) holds. Applying Lemma 6, we obtain

P(E) = P(K s j < g j (x)) = P K max x ∈S g j (x ) < g j (x) ≤ exp(-|S|/K).

Now let Ê denote the event that the inequality Cs j < ĝj (x) = wj âj (x) k∈W w k âk (x) holds and note that the right side of the inequality is defined with respect to ĝj (x) and not g j (x). Observe that since we conditioned on the event E1 /2 , we have that â(x) ∈ (1 ± 1 /2)a(x). Now assume that event Ê holds and note that by the implication above, we have

C s j < ĝj (x) = w j âj (x) k∈W w k âk (x) ≤ (1 + 1 /2)w j a j (x) (1 -1 /2) k∈W w k a k (x) ≤ 3 • w j a j (x) k∈W w k a k (x) = 3 g j (x).

where the second inequality follows from the fact that 1+1/2 /1-1/2 ≤ 3. Moreover, since we know that C ≥ 3K, we conclude that if event Ê occurs, we obtain the inequality

3 K s j ≤ 3 g j (x) ⇔ K s j ≤ g j (x),

which is precisely the definition of event E. Thus, we have shown the conditional implication Ê | E1 /2 ⇒ E, which implies that

P( Ê | E1 /2 ) = P(C s j < ĝj (x) | E1 /2 ) ≤ P(E) ≤ exp(-|S|/K).

Since our choice of j ∈ W was arbitrary, the bound applies for any j ∈ W. Thus, we have by the union bound

P(∃j ∈ W : C s j < ĝj (x) | E1 /2 ) ≤ j∈W P(C s j < ĝj (x) | E1 /2 ) ≤ |W| exp(-|S|/K) = |W| η * δ 8η ≤ δ 8η .

In practice, the set S referenced above is chosen to be a subset of the original data points, i.e., S ⊆ P (see Alg. 1, Line 2). Thus, we henceforth assume that the size of the input points |P| is large enough (or the specified parameter δ ∈ (0, 1) is sufficiently large) so that |P| ≥ |S|.

A.1.2 PROOF OF LEMMA 1:

We now state the proof of Lemma 1. In this subsection, we establish approximation guarantees under the assumption that the weights are strictly positive. The next subsection will then relax this assumption to conclude that a neuron's value can be approximated well even when the weights are not all positive.

Lemma 1 (Positive-Weights Sparsification). Let ε, δ ∈ (0, 1), and x ∼ D. SPARSIFY(W, w, ε, δ, S, a(•)) generates a row vector ŵ such that

P k∈W ŵk âk (x) / ∈ (1 ± ε) k∈W w k âk (x) | E1 /2 ≤ 3δ 8η

where nnz( ŵ) ≤ 8 S log(η η * ) log(8 η/δ) ε 2

, and S = j∈W s j .

Proof. Let ε, δ ∈ (0, 1) be arbitrary. Moreover, let C be the coreset with respect to the weight indices W ⊆ [η -1 ] used to construct ŵ. Note that as in SPARSIFY, C is a multiset sampled from W of size m = 8 S log(η η * ) log(8 η/δ) ε 2

, where S = j∈W s j and C is sampled according to the probability distribution q defined by q j = s j S ∀j ∈ W.

Let â(•) be an arbitrary realization of the random variable â -1 (•), let x be a realization of x ∼ D, and let ẑ = k∈W ŵk âk (x)

be the approximate intermediate value corresponding to the sparsified matrix ŵ and let

z = k∈W w k âk (x).

Now define E to be the (favorable) event that ẑ ε-approximates z, i.e., ẑ ∈ (1 ± ε)z, We will now show that the complement of this event, E c , occurs with sufficiently small probability. Let Z ⊆ supp(D) be the set of well-behaved points (defined implicitly with respect to neuron i ∈ [η ] and realization â) and defined as follows:

Z = {x ∈ supp(D) : ĝj (x ) ≤ Cs j ∀j ∈ W} ,

where C = 3 log(η η * ). Let E Z denote the event that x ∈ Z where x is a realization of x ∼ D.

Conditioned on E Z , event E c occurs with probability ≤ δ 4η : Let x be a realization of x ∼ D such that x ∈ Z and let C = {c 1 , . . . , c m } be m samples from W with respect to distribution q as before. Define m random variables T c1 , . . . , T cm such that for all j ∈ C

EQUATION

For any j ∈ C, we have for the conditional expectation of T j :

E [T j | â(•), x, E Z , E1 /2 ] = k∈W w k âk (x) m q k • q k = k∈W w k âk (x) m = z m ,

where we use the expectation notation E [•] with the understanding that it denotes the conditional expectation

E C | âl-1 (•), x [•]

. Moreover, we also note that conditioning on the event E Z (i.e., the event that x ∈ Z) does not affect the expectation of T j . Let T = j∈C T j = ẑ denote our approximation and note that by linearity of expectation,

E [T | â(•), x, E Z , E1 /2 ] = j∈C E [T j | â(•), x, E Z , E1 /2 ] = z

Thus, ẑ = T is an unbiased estimator of z for any realization â(•) and x; thus, we will henceforth refer to E [T | â(•), x] as simply z for brevity.

For the remainder of the proof we will assume that z > 0, since otherwise, z = 0 if and only if T j = 0 for all j ∈ C almost surely, which follows by the fact that T j ≥ 0 for all j ∈ C by definition of W and the non-negativity of the ReLU activation. Therefore, in the case that z = 0, it follows that

P(|ẑ -z| > εz | â(•), x) = P(ẑ > 0 | â(•), x) = P(0 > 0) = 0,

which trivially yields the statement of the lemma, where in the above expression, P(•) is short-hand for the conditional probability P ŵ | âl-1 (•), x (•).

We now proceed with the case where z > 0 and leverage the fact that x ∈ Z3 to establish that for all j ∈ W:

EQUATION

Utilizing the inequality established above, we bound the conditional variance of each T j , j ∈ C as follows

Var(T j | â(•), x, E Z , E1 /2 ) ≤ E [(T j ) 2 | â(•), x, E Z , E1 /2 ] = k∈W (w k âk (x)) 2 (m q k ) 2 • q k = S m 2 k∈W (w k âk (x)) 2 s k ≤ S m 2 k∈W w k âk (x) C z = S C z2 m 2 ,

where Var(•) is short-hand for Var C | âl-1 (•), x (•). Since T is a sum of (conditionally) independent random variables, we obtain

Var(T | â(•), x, E Z , E1 /2 ) = m Var(T j | â(•), x, E Z , E1 /2 ) (4) ≤ S C z2 m .

Now, for each j ∈ C let

T j = T j -E [T j | â(•), x, E Z , E1 /2 ] = T j -z,

and let T = j∈C T j . Note that by the fact that we conditioned on the realization x of x such that x ∈ Z (event E Z ), we obtain by definition of T j in (2) and the inequality (3):

EQUATION

We also have that S ≥ 1 by definition. More specifically, using the fact that the maximum over a set is greater than the average and rearranging sums, we obtain

S = j∈W s j = j∈W max x ∈S g j (x ) ≥ 1 |S| j∈W x ∈S g j (x ) = 1 |S| x ∈S j∈W g j (x ) = 1 |S| x ∈S 1 = 1.

Thus, the inequality established in (5) with the fact that S ≥ 1 we obtain an upper bound on the absolute value of the centered random variables:

EQUATION

which follows from the fact that: if T j ≥ z m : Then, by our bound in (5) and the fact that z m ≥ 0, it follows that

T j = T j - z m ≤ S C z m - z m ≤ S C z m .

if T j < z m : Then, using the fact that T j ≥ 0 and S ≥ 1, we obtain

T j = z m -T j ≤ z m ≤ S C z m .

Applying Bernstein's inequality to both T and -T we have by symmetry and the union bound,

P(E c | â(•), x, E Z , E1 /2 ) = P |T -z| ≥ εz | â(•), x, E Z , E1 /2 ≤ 2 exp - ε 2 z2 2 Var(T | â(•), x) + 2 ε zM 3 ≤ 2 exp - ε 2 z2 2SC z2 m + 2S C z2 3m = 2 exp - 3 ε 2 m 8S C ≤ δ 4η ,

where the second inequality follows by our upper bounds on Var(T | â(•), x) and T j and the fact that ε ∈ (0, 1), and the last inequality follows by our choice of m = 8 S log(η η * ) log(8 η/δ)

ε 2

. This establishes that for any realization â(•) of âl-1 (•) and a realization x of x satisfying x ∈ Z, the event E c occurs with probability at most δ 4η . Removing the conditioning on E Z : We have by law of total probability

P(E | â(•), E1 /2 ) ≥ x∈Z P(E | â(•), x, E Z , E1 /2 ) P x∼D (x = x | â(•), E1 /2 ) dx ≥ 1 - δ 4η x∈Z P x∼D (x = x | â(•), E1 /2 ) dx = 1 - δ 4η P x∼D (E Z | â(•), E1 /2 ) ≥ 1 - δ 4η 1 - δ 8η ≥ 1 - 3δ 8η

where the second-to-last inequality follows from the fact that P(E c | â(•), x, E Z , E1 /2 ) ≤ δ 4η as was established above and the last inequality follows by Lemma 7.

Putting it all together Finally, we marginalize out the random variable â -1 (•) to establish

P(E | E1 /2 ) = â(•) P(E | â(•), E1 /2 ) P(â(•) | E1 /2 ) dâ(•) ≥ 1 - 3δ 8η â(•) P(â(•) | E1 /2 ) dâ(•) = 1 - 3δ 8η .

Consequently,

P(E c | E1 /2 ) ≤ 1 -1 - 3δ 8η = 3δ 8η ,

and this concludes the proof.

A.2 ANALYTICAL RESULTS FOR SECTION 5.3 (IMPORTANCE SAMPLING BOUNDS):

We begin by establishing an auxiliary result that we will need for the subsequent lemmas.

A.2.1 EMPIRICAL ∆ i APPROXIMATION Lemma 8 (Empirical ∆ i Approximation). Let δ ∈ (0, 1), λ * = log(η η * )/2, and define

∆ = 1 |S| max i∈[η ] x ∈S ∆ i (x ) + κ,

where κ = √ 2λ * 1 + √ 2λ * log (8 η η * /δ) and S ⊆ P is as in Alg. 1. Then,

P x∼D max i∈[η ] ∆ i (x) ≤ ∆ ≥ 1 - δ 4η .

Proof. Define the random variables

Y x = E [∆ i (x )] -∆ i (x )

for each x ∈ S and consider the sum

Y = x ∈S Y x = x ∈S E [∆ i (x)] -∆ i (x ) .

We know that each random variable Y x satisfies E [Y x ] = 0 and by Assumption 2, is subexponential with parameter λ ≤ λ * . Thus, Y is a sum of |S| independent, zero-mean λ * -subexponential random variables, which implies that E [Y] = 0 and that we can readily apply Bernstein's inequality for subexponential random variables (Vershynin, 2016) to obtain for t ≥ 0

P 1 |S| Y ≥ t ≤ exp -|S| min t 2 4 λ 2 * , t 2 λ * .

Since S = log (8 η η * /δ) log(η η * ) ≥ log (8 η η * /δ) 2λ * , we have for t = √ 2λ * ,

P E [∆ i (x)] - 1 |S| x ∈S ∆ i (x ) ≥ t = P 1 |S| Y ≥ t ≤ exp -|S| t 2 4λ 2 * ≤ exp (-log (8 η η * /δ)) = δ 8 η η * .

Moreover, for a single Y x , we have by the equivalent definition of a subexponential random variable (Vershynin, 2016 ) that for u ≥ 0

P(∆ i (x) -E [∆ i (x)] ≥ u) ≤ exp -min - u 2 4 λ 2 * , u 2 λ * .

Thus, for u = 2λ * log (8 η η * /δ) we obtain

P(∆ i (x) -E [∆ i (x)] ≥ u) ≤ exp (-log (8 η η * /δ)) = δ 8 η η * .

Therefore, by the union bound, we have with probability at least 1 -δ 4η η * :

∆ i (x) ≤ E [∆ i (x)] + u ≤ 1 |S| x ∈S ∆ i (x ) + t + u = 1 |S| x ∈S ∆ i (x ) + 2λ * + 2λ * log (8 η η * /δ) = 1 |S| x ∈S ∆ i (x ) + κ ≤ ∆ ,

where the last inequality follows by definition of ∆ .

Thus, by the union bound, we have

P x∼D max i∈[η ] ∆ i (x) > ∆ = P ∃i ∈ [η ] : ∆ i (x) > ∆ ≤ i∈[η ] P ∆ i (x) > ∆ ≤ η δ 4η η * ≤ δ 4 η ,

where the last line follows by definition of η * ≥ η .

A.2.2 NOTATION FOR THE SUBSEQUENT ANALYSIS:

Let ŵ + i and ŵ - i denote the sparsified row vectors generated when SPARSIFY is invoked with first two arguments corresponding to (W + , w i ) and (W -, -w i ), respectively (Alg. 1, Line 12). We will at times omit including the variables for the neuron i and layer in the proofs for clarity of exposition, and for example, refer to ŵ + i and ŵ - i as simply ŵ+ and ŵ-, respectively. Let x ∼ D and define Note that in this context, we have by definition

EQUATION

z i (x) = w, a(x) = z + (x) -z -(x),

where we used the fact that ŵ = ŵ+ -ŵ-∈ R 1×η -1 .

A.2.3 PROOF OF LEMMA 2:

Lemma 2 (Conditional Neuron Value Approximation). Let ε, δ ∈ (0, 1), ∈ {2, . . . , L}, i ∈ [η ], and x ∼ D. CORENET generates a row vector

EQUATION

where ε = ε ∆ → and nnz( ŵ i ) ≤ 8 S log(η η * ) log(8 η/δ) ε 2

+ 1, where S = j∈W+ s j + j∈W-s j .

Proof. Let ε, δ ∈ (0, 1) be arbitrary and let W + = {j ∈ [η -1 ] : w j > 0} and W -= {j ∈ [η -1 ] : w j < 0} as in Alg. 1. Let ε be defined as before, ε = ε ∆ → , where ∆ → = L k= ∆k and

∆ = 1 |S| max i∈[η ] x ∈S ∆ i (x ) + κ.

Observe that w j > 0 ∀j ∈ W + and similarly, for all (-w j ) > 0 ∀j ∈ W -. That is, each of index sets W + and W -corresponds to strictly positive entries in the arguments w i and -w i , respectively passed into SPARSIFY. Observe that since we conditioned on the event E -1 , we have

2 ( -2) ε ≤ 2 ( -2) ε 2 (L -1) L k= ∆k ≤ ε L k= ∆k ≤ ε 2 L-+1 Since ∆k ≥ 2 ∀k ∈ { , . . . , L} ≤ ε 2 ,

where the inequality ∆k ≥ 2 follows from the fact that

∆k = 1 |S| max i∈[η ] x ∈S ∆ i (x ) + κ ≥ 1 + κ Since ∆ i (x ) ≥ 1 ∀x ∈ supp(D) by definition ≥ 2.

we obtain that â(x) ∈ (1 ± ε /2)a(x), where, as before, â and a are shorthand notations for â -1 ∈ R η -1 ×1 and a -1 ∈ R η -1 ×1 , respectively. This implies that E -1 ⇒ E1 /2 and since

m = 8 S log(η η * ) log(8 η/δ) ε 2

in Alg. 2 we can invoke Lemma 1 with ε = ε on each of the SPARSIFY invocations to conclude that

EQUATION

P ẑ-(x) / ∈ (1 ± ε )z -(x) | E -1 ≤ 3δ 8η .

Therefore, by the union bound, we have

P ẑ+ (x) / ∈ (1 ± ε )z + (x) or ẑ-(x) / ∈ (1 ± ε )z -(x) | E -1 ≤ 3δ 8η + 3δ 8η = 3δ 4η .

Moreover, by Lemma 8, we have with probability at most δ 4η that

∆ i (x) > ∆ .

Thus, by the union bound over the failure events, we have that with probability at least 1 -( 3δ /4η + δ /4η) = 1 -δ /η that both of the following events occur

EQUATION

Recall that ε = ε 2 (L-1) , ε = ε ∆ → , and that event E i denotes the (desirable) event that

ẑ i (x) (1 ± 2 ( -1) ε +1 ) z i (x)

holds, and similarly, E = ∩ i∈[η ] E i denotes the vector-wise analogue where

ẑ (x) (1 ± 2 ( -1) ε +1 ) z (x).

Let k = 2 ( -1) and note that by conditioning on the event E -1 , i.e., we have by definition

â -1 (x) ∈ (1 ± 2 ( -2)ε )a -1 (x) = (1 ± k ε )a -1 (x),

which follows by definition of the ReLU function. Recall that our overarching goal is to establish that

ẑ i (x) ∈ (1 ± 2 ( -1)ε +1 ) z i (x),

which would immediately imply by definition of the ReLU function that

â i (x) ∈ (1 ± 2 ( -1)ε +1 ) a i (x).

Having clarified the conditioning and our objective, we will once again drop the index i from the expressions moving forward.

Proceeding from above, we have with probability at least 1 -δ /η

ẑ(x) = ẑ+ (x) -ẑ-(x) ≤ (1 + ε ) z+ (x) -(1 -ε ) z-(x)

By Event (7) above

≤ (1 + ε )(1 + k ε ) z + (x) -(1 -ε )(1 -k ε ) z -(x) Conditioning on event E -1 = 1 + ε (k + 1) + kε 2 z + (x) + -1 + (k + 1)ε -kε 2 z -(x) = 1 + k ε 2 z(x) + (k + 1) ε z + (x) + z -(x) = 1 + k ε 2 z(x) + (k + 1) ε L k= ∆k z + (x) + z -(x) ≤ 1 + k ε 2 z(x) + (k + 1) ε ∆ i (x) L k= +1 ∆k z + (x) + z -(x) By Event (8) above = 1 + k ε 2 z(x) + (k + 1) ε L k= +1 ∆k |z(x)| By ∆ i (x) = z + (x) + z -(x) |z(x)| = 1 + k ε 2 z(x) + (k + 1) ε +1 |z(x)|.

To upper bound the last expression above, we begin by observing that kε 2 ≤ ε , which follows from the fact that ε ≤ 1 2 (L-1) ≤ 1 k by definition. Moreover, we also note that ε ≤ ε +1 by definition of ∆ ≥ 1.

Now, we consider two cases.:

Case of z(x) ≥ 0: In this case, we have

ẑ(x) ≤ 1 + k ε 2 z(x) + (k + 1) ε +1 |z(x)| ≤ (1 + ε )z(x) + (k + 1)ε +1 z(x) ≤ (1 + ε +1 )z(x) + (k + 1)ε +1 z(x) = (1 + (k + 2) ε +1 ) z(x) = (1 + 2 ( -1)ε +1 ) z(x),

where the last line follows by definition of k = 2 ( -2), which implies that k + 2 = 2( -1). Thus, this establishes the desired upper bound in the case that z(x) ≥ 0.

Case of z(x) < 0: Since z(x) is negative, we have that 1 + k ε 2 z(x) ≤ z(x) and |z(x)| = -z(x) and thus

ẑ(x) ≤ 1 + k ε 2 z(x) + (k + 1) ε +1 |z(x)| ≤ z(x) -(k + 1)ε +1 z(x) ≤ (1 -(k + 1)ε +1 ) z(x) ≤ (1 -(k + 2)ε +1 ) z(x) = (1 -2 ( -1)ε +1 ) z(x),

and this establishes the upper bound for the case of z(x) being negative.

Putting the results of the case by case analysis together, we have the upper bound of ẑ(x) ≤ z(x) + 2 ( -1)ε +1 |z(x)|. The proof for establishing the lower bound for z(x) is analogous to that given above, and yields ẑ(x) ≥ z(x)-2 ( -1)ε +1 |z(x)|. Putting both the upper and lower bound together, we have that with probability at least 1 -δ η :

ẑ(x) ∈ (1 ± 2 ( -1)ε +1 ) z(x),

and this completes the proof.

A.2.4 REMARKS ON NEGATIVE ACTIVATIONS:

We note that up to now we assumed that the input a(x), i.e., the activations from the previous layer, are strictly nonnegative. For layers ∈ {3, . . . , L}, this is indeed true due to the nonnegativity of the ReLU activation function. For layer 2, the input is a(x) = x, which can be decomposed into a(x) = a pos (x) -a neg (x), where a pos (x

) ≥ 0 ∈ R η -1 and a neg (x) ≥ 0 ∈ R η -1

. Furthermore, we can define the sensitivity over the set of points {a pos (x), a neg (x) | x ∈ S} (instead of {a(x) | x ∈ S}), and thus maintain the required nonnegativity of the sensitivities. Then, in the terminology of Lemma 2, we let

z + pos (x) = k∈W+ w k a pos,k (x) ≥ 0 and z - neg (x) = k∈W- (-w k ) a neg,k (x) ≥ 0

be the corresponding positive parts, and

z + neg (x) = k∈W+ w k a neg,k (x) ≥ 0 and z - pos (x) = k∈W- (-w k ) a pos,k (x) ≥ 0

be the corresponding negative parts of the preactivation of the considered layer, such that

z + (x) = z + pos (x) + z - neg (x) and z -(x) = z + neg (x) + z - pos (x).

We also let

∆ i (x) = z + (x) + z -(x) |z(x)|

be as before, with z + (x) and z -(x) defined as above. Equipped with above definitions, we can rederive Lemma 2 analogously in the more general setting, i.e., with potentially negative activations.

We also note that we require a slightly larger sample size now since we have to take a union bound over the failure probabilities of all four approximations (i.e. ẑ+ pos (x), ẑneg (x), ẑ+ neg (x), and ẑpos (x)) to obtain the desired overall failure probability of δ /η.

A.2.5 PROOF OF THEOREM 4:

The following corollary immediately follows from Lemma 2 and establishes a layer-wise approximation guarantee. Corollary 9 (Conditional Layer-wise Approximation). Let ε, δ ∈ (0, 1), ∈ {2, . . . , L}, and x ∼ D. CORENET generates a sparse weight matrix Ŵ = ŵ 1 , . . . , ŵ η ∈ R η ×η -1 such that

EQUATION

where ε = ε ∆ → , ẑ (x) = Ŵ â (x), and z (x) = W a (x).

Proof. Since (1) established by Lemma 2 holds for any neuron i ∈ [η ] in layer and since

(E ) c = ∪ i∈[η ] (E i ) c

, it follows by the union bound over the failure events (E i ) c for all i ∈ [η ] that with

probability at least 1 -η δ η ẑ (x) = Ŵ â -1 (x) ∈ (1 ± 2 ( -1) ε +1 ) W a -1 (x) = (1 ± 2 ( -1) ε +1 ) z (x).

The following lemma removes the conditioning on E -1 and explicitly considers the (compounding) error incurred by generating coresets Ŵ 2 , . . . , Ŵ for multiple layers.

Lemma 3 (Layer-wise Approximation). Let ε, δ ∈ (0, 1), ∈ {2, . . . , L}, and x ∼ D. CORENET generates a sparse weight matrix Ŵ ∈ R η ×η -1 such that, for ẑ (x) = Ŵ â (x),

P ( Ŵ 2 ,..., Ŵ ), x (E ) = P ( Ŵ 2 ,..., Ŵ ), x ẑ (x) ∈ (1 ± 2 ( -1) ε +1 ) z (x) ≥ 1 - δ =2 η η .

Proof. Invoking Corollary 9, we know that for any layer ∈ {2, . . . , L},

EQUATION

)

We also have by the law of total probability that

EQUATION

Repeated applications of ( 10) and ( 11) in conjunction with the observation that P(E 1 ) = 1 4 yield

P(E ) ≥ P(E | E -1 ) P(E -1 )

. . . Repeated applications of ( 11)

≥ =2 P(E | E -1 ) ≥ =2 1 - δ η η By (10) ≥ 1 - δ η =2 η

By the Weierstrass Product Inequality, where the last inequality follows by the Weierstrass Product Inequality 5 and this establishes the lemma.

Appropriately invoking Lemma 3, we can now establish the approximation guarantee for the entire neural network. This is stated in Theorem 4 and the proof can be found below.

Theorem 4 (Network Compression). For ε, δ ∈ (0, 1), Algorithm 1 generates a set of parameters

θ = ( Ŵ 2 , . . . , Ŵ L ) of size nnz( θ) ≤ L =2 η i=1 32 (L -1) 2 ( ∆ → ) 2 S i log(η η * ) log(8 η/δ) ε 2 + 1 in O η η * log η η * /δ time such that P θ, x∼D f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 -δ.

4 Since we do not compress the input layer. 5 The Weierstrass Product Inequality (Doerr, 2018) states that for p1, . . . , pn ∈ [0, 1],

n i=1 (1 -pi) ≥ 1 - n i=1 pi.

Proof. Invoking Lemma 3 with = L, we have that for θ = ( Ŵ 2 , . . . , Ŵ L ),

P θ, x f θ (x) ∈ 2 (L -1) ε L+1 f θ (x) = P θ, x (ẑ L (x) ∈ 2 (L -1) ε L+1 z L (x)) = P(E L ) ≥ 1 - δ L =2 η η = 1 -δ,

where the last equality follows by definition of η = L =2 η . Note that by definition,

ε L+1 = ε 2 (L -1) L k=L+1 ∆k = ε 2 (L -1)

,

where the last equality follows by the fact that the empty product

L k=L+1

∆k is equal to 1.

Thus, we have

2 (L -1)ε L+1 = ε,

and so we conclude

P θ, x f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 -δ,

which, along with the sampling complexity of Alg. 2 (Line 6), establishes the approximation guarantee provided by the theorem.

For the computational time complexity, we observe that the most time consuming operation per iteration of the loop on Lines 7-13 is the weight sparsification procedure. The asymptotic time complexity of each SPARSIFY invocation for each neuron i ∈ [η ] in layers ∈ {2, . . . , L} (Alg. 1, Line 12) is dominated by the relative importance computation for incoming edges (Alg. 2, Lines 1-2). This can be done by evaluating w ik a -1 k (x) for all k ∈ W and x ∈ S, for a total computation time that is bounded above by O |S| η -1 since |W| ≤ η -1 for each i ∈ [η ]. Thus, SPARSIFY takes O |S| η -1 time. Summing the computation time over all layers and neurons in each layer, we obtain an asymptotic time complexity of O |S| L =2 η -1 η ⊆ O (|S| η * η). Since |S| ∈ O(log(η η * /δ)), we conclude that the computational complexity our neural network compression algorithm is

EQUATION

A.2.6 PROOF OF THEOREM 11

In order to ensure that the established sampling bounds are non-vacuous in terms of the sensitivity, i.e., not linear in the number of incoming edges, we show that the sum of sensitivities per neuron S is small. The following lemma establishes that the sum of sensitivities can be bounded instance-independent by a term that is logarithmic in roughly the total number of edges (η • η * ).

Lemma 10 (Sensitivity Bound). For any ∈ {2, . . . , L} and i ∈ [η ], the sum of sensitivities S = S + + S -is bounded by S ≤ 2 |S| = 2 log (8 η η * /δ) log(η η * ) .

Proof. Consider S + for an arbitrary ∈ {2, . . . , L} and i ∈ [η ]. For all j ∈ W we have the following bound on the sensitivity of a single j ∈ W,

s j = max x∈S g j (x) ≤ x∈S g j (x) = x∈S w j a j (x) k∈W w k a k (x)

, where the inequality follows from the fact that we can upper bound the max by a summation over x ∈ S since g j (x) ≥ 0, ∀j ∈ W. Thus,

S + = j∈W s j ≤ j∈W x∈S g j (x) = x∈S j∈W w j a j (x) k∈W w k a k (x) = |S|,

where we used the fact that the sum of sensitivities is finite to swap the order of summation.

Using the same argument as above, we obtain S -= j∈W-s j ≤ |S|, which establishes the lemma.

Note that the sampling complexities established above have a linear dependence on the sum of sensitivities,

L =2 η i=1

S i , which is instance-dependent, i.e., depends on the sampled S ⊆ P and the actual weights of the trained neural network. By applying Lemma 10, obtain a bound on the size of the compressed network that is independent of the sensitivity.

Theorem 11 (Sensitivity-Independent Network Compression). For any given ε, δ ∈ (0, 1) our sampling scheme (Alg. 1) generates a set of parameters θ of size

nnz( θ) ∈ O log(η/δ) log(η η * /δ) log 2 (η η * ) η L 2 ε 2 L =2 ( ∆ → ) 2 , in O η η * log η η * /δ time, such that P θ, x∼D f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 -δ.

Proof. Combining Lemma 10 and Theorem 4 establishes the theorem.

A.2.7 GENERALIZED NETWORK COMPRESSION:

Theorem 4 gives us an approximation guarantee with respect to one randomly drawn point x ∼ D. The following corollary extends this approximation guarantee to any set of n randomly drawn points using a union bound argument, which enables approximation guarantees for, e.g., a test data set composed of n i.i.d. points drawn from the distribution. We note that the sampling complexity only increases by roughly a logarithmic term in n.

Corollary 12 (Generalized Network Compression). For any ε, δ ∈ (0, 1) and a set of i.i. 

EQUATION

3. m ≥ 8 S log(η η * ) log(16|P | η/δ) ε 2

in the sample complexity in SPARSIFYWEIGHTS.

Then, Alg. 1 generates a set of neural network parameters θ of size at most

nnz( θ) ≤ L =2 η i=1 32 (L -1) 2 ( ∆ → ) 2 S i log(η η * ) log(16 |P | η/δ) ε 2 + 1 ∈ O   log(η η * ) log(η |P |/δ) L 2 ε 2 L =2 ( ∆ → ) 2 η i=1 S i   , in O η η * log η η * |P |/δ time such that P θ, x ∀x ∈ P : f θ (x) ∈ (1 ± ε)f θ (x) ≥ 1 - δ 2 .

Proof. The reparameterization enables us to invoke Theorem 4 with δ = δ /2 |P |; applying the union bound over all |P | i.i.d. samples in P establishes the corollary.

B ADDITIONAL RESULTS:

In this section, we give more details on the evaluation of our compression algorithm on popular benchmark data sets and varying fully-connected neural network configurations. In the experiments, we compare the effectiveness of our sampling scheme in reducing the number of non-zero parameters of a network to that of uniform sampling and the singular value decomposition (SVD). All algorithms were implemented in Python using the PyTorch library (Paszke et al., 2017) and simulations were conducted on a computer with a 2.60 GHz Intel i9-7980XE processor (18 cores total) and 128 GB RAM.

For training and evaluating the algorithms considered in this section, we used the following off-theshelf data sets:

• MNIST (LeCun et al., 1998) -70, 000 images of handwritten digits between 0 and 9 in the form of 28 × 28 pixels per image. • CIFAR-10 (Krizhevsky & Hinton, 2009) -60, 000 32 × 32 color images, a subset of the larger CIFAR-100 dataset, each depicting an object from one of 10 classes, e.g., airplanes.

• FashionMNIST (Xiao et al., 2017) -A recently proposed drop-in replacement for the MNIST data set that, like MNIST, contains 60, 000, 28 × 28 grayscale images, each associated with a label from 10 different categories.

We considered a diverse set of network configurations for each of the data sets. We varied the number of hidden layers between 2 and 5 and used either a constant width across all hidden layers between 200 and 1000 or a linearly decreasing width (denoted by "Pyramid" in the figures). Training was performed for 30 epochs on the normalized data sets using an Adam optimizer with a learning rate of 0.001 and a batch size of 300. The test accuracies were roughly 98% (MNIST), 45% (CIFAR10), and 96% (FashionMNIST), depending on the network architecture. To account for the randomness in the training procedure, for each data set and neural network configuration, we averaged our results across 4 trained neural networks.

B.1 DETAILS ON THE COMPRESSION ALGORITHMS:

We evaluated and compared the performance of the following algorithms on the aforementioned data sets.

1. Uniform (Edge) Sampling -A uniform distribution is used, rather than our sensitivity-based importance sampling distribution, to sample the incoming edges to each neuron in the network. Note that like our sampling scheme, uniform sampling edges generates an unbiased estimator of the neuron value. However, unlike our approach which explicitly seeks to minimize estimator variance using the bounds provided by empirical sensitivity, uniform sampling is prone to exhibiting large estimator variance.

2. Singular Value Decomposition (SVD) -The (truncated) SVD decomposition is used to generate a low-rank (rank-r) approximation for each of the weight matrices ( Ŵ 2 , . . . , Ŵ L ) to obtain the corresponding parameters θ = ( Ŵ 2 r , . . . , Ŵ L r ) for various values of r ∈ N + . Unlike the compared sampling-based methods, SVD does not sparsify the weight matrices. Thus, to achieve fair comparisons of compression rates, we compute the size of the rank-r matrices constituting θ as,

nnz( θ) = L =2 r i=1 nnz(u i ) + nnz(v i ) ,

where W = U Σ (V ) for each ∈ {2, . . . , L}, with σ 1 ≥ σ 2 . . . ≥ σ η -1 and u i and v i denote the ith columns of U and V respectively.

3. 1 Sampling (Achlioptas et al., 2013) -An entry-wise sampling distribution based on the ratio between the absolute value of a single entry and the (entry-wise) 1 -norm of the weight matrix is computed, and the weight matrix is subsequently sparsified by sampling accordingly.

In particular, entry w ij of some weight matrix W is sampled with probability

p ij = |w ij | W 1 ,

and reweighted to ensure the unbiasedness of the resulting estimator.

4. 2 Sampling (Drineas & Zouzias, 2011) -The entries (i, j) of each weight matrix W are sampled with distribution

p ij = w 2 ij W 2 F

, where • F is the Frobenius norm of W , and reweighted accordingly.

5. 1+ 2 2

Sampling (Kundu & Drineas, 2014) -The entries (i, j) of each weight matrix W are sampled with distribution

p ij = 1 2 w 2 ij W 2 F + |w ij | W 1 ,

where • F is the Frobenius norm of W , and reweighted accordingly. We note that Kundu & Drineas (2014) constitutes the current state-of-the-art in data-oblivious matrix sparsification algorithms.

6. CoreNet (Edge Sampling) -Our core algorithm for edge sampling shown in Alg. 2, but without the neuron pruning procedure. 

B.2 PRESERVING THE OUTPUT OF A NEURAL NETWORK:

We evaluated the accuracy of our approximation by comparing the output of the compressed network with that of the original one and compute the 1 -norm of the relative error vector. We computed the error metric for both the uniform sampling scheme as well as our compression algorithm (Alg. 1). Our results were averaged over 50 trials, where for each trial, the relative approximation error was averaged over the entire test set. In particular, for a test set P test ⊆ R d consisting of d dimensional points, the average relative error of with respect to the f θ generated by each compression algorithm was computed as

error Ptest (f θ ) = 1 |P test | x∈Ptest f θ (x) -f θ (x) 1 .

Figures 3, 4 , and 5 depict the average performance of the compared algorithms for various network architectures trained on MNIST, CIFAR-10, and FashionMNIST, respectively. Our algorithm is able to compress networks trained on MNIST and FashionMNIST to about 10% of their original size without significant loss of accuracy. On CIFAR-10, a compression rate of 50% yields classification results comparable to that of uncompressed networks. The shaded region corresponding to each curve represents the values within one standard deviation of the mean.

B.3 PRESERVING THE CLASSIFICATION PERFORMANCE:

We also evaluated the accuracy of our approximation by computing the loss of prediction accuracy on a test data set, P test . In particular, let acc Ptest (f θ ) be the average accuracy of the neural network f θ , i.e,.

acc Ptest (f θ ) = 1 |P test | x∈Ptest 1 argmax i∈[η L ] f θ (x) = y(x) ,

where y(x) denotes the (true) label associated with x. Then the drop in accuracy is computed as

acc Ptest (f θ ) -acc Ptest (f θ ).

Figures 6, 7, and 8 depict the average performance of the compared algorithms for various network architectures trained on MNIST, CIFAR-10, and FashionMNIST respectively. The shaded region corresponding to each curve represents the values within one standard deviation of the mean.

B.4 PRELIMINARY RESULTS WITH RETRAINING:

We compared the performance of our approach with that of the popular weight thresholding heuristichenceforth denoted by WT -of Han et al. (2015) when retraining was allowed after the compression, i.e., pruning, procedure. Our comparisons with retraining for the networks and data sets mentioned in Sec. 6 are as follows. For MNIST, WT required 5.8% of the number of parameters to obtain the classification accuracy of the original model (i.e., 0% drop in accuracy), whereas for the same percentage (5.8%) of the parameters retained, CoreNet++ incurred a classification accuracy drop of 1%. For CIFAR, the approach of Han et al. (2015) matched the original models accuracy using 3% of the parameters, whereas CoreNet++ reported an accuracy drop of 9.5% for 3% of the parameters retained. Finally, for FashionMNIST, the corresponding numbers were 4.1% of the parameters to achieve 0% loss for WT, and a loss of 4.7% in accuracy for CoreNet++ with the same percentage of parameters retained.

B.5 DISCUSSION:

As indicated in Sec. 6, the simulation results presented here validate our theoretical results and suggest that empirical sensitivity can lead to effective, more informed sampling compared to other methods. Moreover, we are able to outperform networks that are compressed via state-of-the-art matrix sparsification algorithms. We also note that there is a notable difference in the performance of our algorithm between different datasets. In particular, the difference in performance of our algorithm compared to the other method for networks trained on FashionMNIST and MNIST is much more significant than for networks trained on CIFAR. We conjecture that this is partially due to considering only fully-connected networks as these network perform fairly poorly on CIFAR (around 45% classification accuracy) and thus edges have more uniformly distributed sensitivity as the information content in the network is limited. We envision that extending our guarantees to convolutional neural networks may enable us to further reason about the performance on data sets such as CIFAR. 

:

â -1 (x) denotes the approximation from previous layers for an input x ∼ D; see Sec. 5 for details.

The upper bound of log(ηη * ) for K and λ can be considered somewhat arbitrary in the sense that, more generally, we only require that K, λ ∈ O(polylog(ηη * |P|). Defining the upper bound in this way simplifies the presentation of the core ideas without having to deal with the constants involved in the asymptotic notation.

Since we conditioned on the event EZ .

Figures and Tables:

Figure 1: Evaluation of drop in classification accuracy after compression against the MNIST, CIFAR, and FashionMNIST datasets with varying number of hidden layers (L) and number of neurons per hidden layer (η * ). Shaded region corresponds to values within one standard deviation of the mean.

k ) âk (x) ≥ 0 be the approximate intermediate values corresponding to the sparsified matrices ŵ+ and ŵ-; let z+ (x) = k∈W+ w k âk (x) ≥ 0 and z-(x) = k∈W-(-w k ) âk (x) ≥ 0 be the corresponding intermediate values with respect to the the original row vector w; and finally, let z + (x) = k∈W+ w k a k (x) ≥ 0 and z -(x) = k∈W-(-w k ) a k (x) ≥ 0 be the true intermediate values corresponding to the positive and negative valued weights.

CoreNet+ (CoreNet & Neuron Pruning) -Our algorithm shown in Alg. 1 that includes the neuron pruning step. 8. CoreNet++ (CoreNet+ & Amplification) -In addition to the features of Corenet+, multiple coresets C 1 , . . . , C τ are constructed over τ ∈ N + trials, and the best one is picked by evaluating the empirical error on a subset T ⊆ P \ S (see Sec. 4 for details).

Figure3: Evaluations against the MNIST dataset with varying number of hidden layers (L) and number of neurons per hidden layer (η * ). Shaded region corresponds to values within one standard deviation of the mean. The figures show that our algorithm's relative performance increases as the number of layers (and hence the number of redundant parameters) increases.

Coreset constructions were originally introduced in the context of computational geometry (Agarwal et al., 2005) and subsequently generalized for applications to other problems via an importance sampling-based, sensitivity framework (Langberg & Schulman, 2010; Braverman et al., 2016). Coresets have been used successfully to accelerate various machine learning algorithms such as k-means clustering (Feldman & Langberg, 2011; Braverman et al., 2016), graphical model training (Molina et al., 2018), and logistic regression (Huggins et al., 2016) (see the surveys of Bachem et al. (2017) and Munteanu & Schwiegelshohn (2018) for a complete list). In contrast to prior work, we generate coresets for reducing the number of parameters -rather than data points -via a novel construction scheme based on an efficiently-computable notion of sensitivity.

Table content: <table/>

Generalization The generalization properties of neural networks have been extensively investigated in various contexts (Dziugaite & Roy, 2017; Neyshabur et al., 2017a; Bartlett et al., 2017). However, as was pointed out by Neyshabur et al. (2017b), current approaches to obtaining non-vacuous generalization bounds do not fully or accurately capture the empirical success of state-of-the-art neural network architectures. Recently, Arora et al. (2018) and Zhou et al. (2018) highlighted the close connection between compressibility and generalization of neural networks. Arora et al. (2018) presented a compression method based on the Johnson-Lindenstrauss (JL) Lemma (Johnson & Lindenstrauss,

Table content: <table/>

Emily Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. CoRR, abs/1404.0736, 2014. URL http://arxiv.org/abs/1404.0736. 2 PROOFS OF THE ANALYTICAL RESULTS IN SECTION 5This section includes the full proofs of the technical results given in Sec. 5.

Table content: <table><tr><td colspan="3">Benjamin Doerr. Probabilistic tools for the analysis of randomized optimization heuristics. arXiv A.1 ANALYTICAL RESULTS FOR SECTION 5.2 (IMPORTANCE SAMPLING BOUNDS FOR preprint arXiv:1801.06733, 2018. 23 POSITIVE WEIGHTS)</td></tr><tr><td colspan="3">Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise</td></tr><tr><td colspan="3">optimal brain surgeon. In Advances in Neural Information Processing Systems, pp. 4860-4874, A.1.1 ORDER STATISTIC SAMPLING</td></tr><tr><td>2017. 2</td><td/></tr><tr><td colspan="3">Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via a matrix-</td></tr><tr><td colspan="3">valued bernstein inequality. Information Processing Letters, 111(8):385-389, 2011. 8, 28</td></tr><tr><td colspan="3">Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for</td></tr><tr><td colspan="3">deep (stochastic) neural networks with many more parameters than training data. arXiv preprint</td></tr><tr><td>arXiv:1703.11008, 2017. 2</td><td/></tr><tr><td colspan="3">Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In</td></tr><tr><td colspan="3">Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 569-578. ACM,</td></tr><tr><td>2011. 2</td><td/></tr><tr><td colspan="3">Contemporary mathematics, 26(189-206):1, 1984. 2</td></tr><tr><td colspan="3">Yong-Deok Kim, Eunhyeok Park, Sungjoo Yoo, Taelim Choi, Lu Yang, and Dongjun Shin. Com-</td></tr><tr><td colspan="3">pression of deep convolutional neural networks for fast and low power mobile applications. arXiv</td></tr><tr><td>preprint arXiv:1511.06530, 2015. 2</td><td/></tr><tr><td colspan="3">Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.</td></tr><tr><td>7, 27</td><td/></tr><tr><td colspan="3">Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep</td></tr><tr><td>convolutional neural networks.</td><td colspan="2">In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q.</td></tr><tr><td colspan="3">Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097-</td></tr><tr><td colspan="2">1105. Curran Associates, Inc., 2012.</td><td>URL http://papers.nips.cc/paper/</td></tr><tr><td colspan="3">4824-imagenet-classification-with-deep-convolutional-neural-networks.</td></tr><tr><td>pdf. 1</td><td/></tr></table>

Peer review (iclr2019):
 In this work the authors improve upon the work of Arora et al. mainly with respect to one aspect, i.e., They provide eps-approximation of a fully connected neural network output neuron-wise. The idea of compression is very natural and has been explored by various previous works (key refs are cited). Intuitively, the number of effective parameters is significantly less than the number of parameters in the neural network. The authors introduce the notion of the coreset that is suitable for compressing the weight parameters in definition 1. Their main result is stated as Theorem 4. Finally, the authors experiment on standard benchmarks, perform a careful experimental analysis (i.e., they ensure fairness of comparison between methods such as SVD and the rest). It would be interesting to see the histogram/distribution of the weights per layer and at an aggregate level for the datasets used. Also, in the light of the recent results of Arora et al. that show that the signal out of a layer is correlated with the top singular values, how would coresets developed in the numerical linear algebraic community (e.g., Near-optimal Coresets For Least-Squares Regression by Boutsidis et al.) perform, even as an experimental heuristic compared to the proposed method?