Year: 2019

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.

heading: 1 INTRODUCTION
text: 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.
†Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, emails: {baykal, lucasl, igilitschenski, rus}@mit.edu ‡Robotics and Big Data Laboratory, University of Haifa, email: dannyf.post@gmail.com *These authors contributed equally to this work
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.

heading: 2 RELATED WORK
text: Our work builds upon the following prior work in coresets and compression approaches.
Coresets 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.
Low-rank Approximations and Weight-sharing Denil et al. (2013) were among the first to empirically demonstrate the existence of significant parameter redundancy in deep neural networks. A predominant class of compression approaches consists of using low-rank matrix decompositions, such as Singular Value Decomposition (SVD) (Denton et al., 2014), to approximate the weight matrices with their low-rank counterparts. Similar works entail the use of low-rank tensor decomposition approaches applicable both during and after training (Jaderberg et al., 2014; Kim et al., 2015; Tai et al., 2015; Ioannou et al., 2015; Alvarez & Salzmann, 2017; Yu et al., 2017). Another class of approaches uses feature hashing and weight sharing (Weinberger et al., 2009; Shi et al., 2009; Chen et al., 2015b;a; Ullrich et al., 2017). Building upon the idea of weight-sharing, quantization (Gong et al., 2014; Wu et al., 2016; Zhou et al., 2017) or regular structure of weight matrices was used to reduce the effective number of parameters (Zhao et al., 2017; Sindhwani et al., 2015; Cheng et al., 2015; Choromanska et al., 2016; 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.
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 & Lempitsky (2016); Dong et al. (2017), e.g., by embedding sparsity as a constraint (Iandola et al., 2016; Aghasi et al., 2017; Lin et al., 2017). Another related approach is that of Han et al. (2015), which considers a combination of weight pruning and weight sharing methods. Nevertheless, prior work in weight pruning lacks rigorous theoretical analysis of the effect that the discarded weights can have on the compressed network. To the best of our knowledge, our work is the first to introduce a practical, sampling-based weight pruning algorithm with provable guarantees.
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, 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.

heading: 3 PROBLEM DEFINITION

heading: 3.1 FULLY-CONNECTED NEURAL NETWORKS
text: A feedforward fully-connected neural network withL ∈ N+ layers and parameters θ defines a mapping fθ : X → Y for a given input x ∈ X ⊆ Rd to an output y ∈ Y ⊆ Rk 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 ∈ R1×η `−1 , and θ = (W 2, . . . ,WL). For notational simplicity, we assume that the bias is embedded in the weight matrix. Then for an input vector x ∈ Rd, let a1 = 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) = zL, and in particular, for classification tasks the prediction is argmaxi∈[k] fθ(x)i = argmaxi∈[k] z L i .

heading: 3.2 NEURAL NETWORK CORESET PROBLEM
text: 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, . . . ,WL). We further denote the input points of a validation data set as P = {xi}ni=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, . . . ,WL.
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 ∈ Rk as the following entry-wise bound: a ∈ (1± ε)b ⇔ ai ∈ (1± ε)bi ∀i ∈ [k], and formalize the definition of an (ε, δ)-coreset as follows.
Definition 1 ((ε, δ)-coreset). Given user-specified ε, δ ∈ (0, 1), a set of parameters θ̂ = (Ŵ 2, . . . , Ŵ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.

heading: 4 METHOD
text: 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.

heading: 4.1 CORENET
text: Our method (Alg. 1) hinges on the insight that a validation set of data points P i.i.d.∼ Dn can be used to approximate the relative importance, i.e., sensitivity, of each weighted edge with respect to the input
data distributionD. 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.∼ Dn; θ = (W 2, . . . ,WL): parameters of the original uncompressed neural network. Output: θ̂ = (Ŵ 2, . . . , Ŵ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 dlog (8 η η∗/δ) log(η η∗)e points from P; 3: a1(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| maxi∈[η`] ∑ x∈S ∆ ` i(x) ) + κ, where κ = √ 2λ∗ ( 1 + √ 2λ∗ log (8 η η ∗/δ) ) ; 9: Ŵ ` ← (~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: ŵ`+i ← SPARSIFY(W+, w ` i , ε`, δ,S, a`−1); ŵ`−i ← SPARSIFY(W−,−w ` i , ε`, δ,S, a`−1); 13: ŵ`i ← ŵ`+i − ŵ `− i ; Ŵ ` i• ← ŵ`i ; . Consolidate the weights into the ith row of Ŵ `; 14: return θ̂ = (Ŵ 2, . . . , ŴL);
Algorithm 2 SPARSIFY(W, w, ε, δ,S, a(·)) Input: W ⊆ [η`−1]: index set; w ∈ R1×η `−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: ŵ: sparse weight vector. 1: for j ∈ W do 2: sj ← maxx∈S wjaj(x)∑
k∈W wkak(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 ← sjS ; 6: m← ⌈ 8S log(η η∗) log(8 η/δ)
ε2
⌉ ; . Compute the number of required samples
7: C ← a multiset of m samples fromW where each j ∈ W is sampled with probability qj ; 8: ŵ ← (0, . . . , 0) ∈ R1×η `−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: ŵj ← ŵj + wjmqj ; . Entries are reweighted by 1 mqj to ensure unbiasedness of our estimator
11: return ŵ;
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 θ̂ = (Ŵ 2, . . . , ŴL) of sparse weight matrices such that the output of each layer and the entire network is approximately preserved, i.e., Ŵ `â`−1(x) ≈W `a`−1(x) and fθ̂(x) ≈ fθ(x), respectively 1.
1â`−1(x) denotes the approximation from previous layers for an input x ∼ D; see Sec. 5 for details.

heading: 4.2 SPARSIFYING WEIGHTS
text: 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 sj 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 sj 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).

heading: 4.3 EXTENSIONS: NEURON PRUNING AND AMPLIFICATION
text: 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) (ŵ`i )1, . . . , (ŵ ` 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 .

heading: 5 ANALYSIS
text: 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.

heading: 5.1 PRELIMINARIES
text: 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 ẑ`(x) and â`(x) denote the respective quantities of layer ` when we replace the weight matrices W 2, . . . ,W ` in layers 2, . . . , ` by Ŵ 2, . . . , Ŵ `, 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 , â`−1(x)〉 ∈ R with respect to a point x, we will simply write z(x) = 〈w, a(x)〉 ∈ R, where w := w`i ∈ R1×η `−1 and a(x) := a`−1(x) ∈ Rη`−1×1. Under this notation, the weight of an incoming edge j is denoted by wj ∈ R.

heading: 5.2 IMPORTANCE SAMPLING BOUNDS FOR POSITIVE WEIGHTS
text: 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] : wj > 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 gj(x), where gj(x) = wj aj(x)∑
k∈W wk ak(x) ∀j ∈ W.
Note that gj(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 gj(x), denoted by Fj (·), satisfies
Fj (M/K) ≤ exp(−1/K), where M = min{x ∈ [0, 1] : Fj (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| = dlog (8 η η∗/δ) log(η η∗)e, 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.∼ Dn.Then, the sensitivity over positive edges j ∈ W directed to a neuron is defined as sj = maxx∈S gj(x).
Our first lemma establishes a core result that relates the weighted sum with respect to the sparse row vector ŵ, ∑ k∈W ŵk âk(x), to the value of the of the weighted sum with respect to the ground-truth
row vector w, ∑ k∈W wk âk(x). We remark that there is randomness with respect to the randomly generated row vector ŵ`i , a randomly drawn input x ∼ D, and the function â(·) = â`−1(·) defined by the randomly generated matrices Ŵ 2, . . . , Ŵ `−1 in the previous layers. Unless otherwise stated, we will henceforth use the shorthand notation P(·) to denote Pŵ`, x, â`−1(·). Moreover, for ease of presentation, we will first condition on the event E1/2 that â(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 ŵ such that
P (∑ k∈W ŵk âk(x) /∈ (1± ε) ∑ k∈W wk âk(x) | E1/2 ) ≤ 3δ 8η
where nnz(ŵ) ≤ ⌈
8S log(η η∗) log(8 η/δ) ε2
⌉ , and S = ∑ j∈W sj .

heading: 5.3 IMPORTANCE SAMPLING BOUNDS
text: 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] : wj > 0} andW− = {j ∈ [η`−1] : wj < 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`−1k (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(s2λ2) ∀|s| ≤ 1λ . 2
2The 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.
For ε ∈ (0, 1) and ` ∈ {2, . . . , L}, we let ε′ = ε2 (L−1) and define ε` = ε′ ∆̂`→ = ε 2 (L−1) ∏L k=` ∆̂ k , where ∆̂` = (
1 |S| maxi∈[η`] ∑ x′∈S ∆ ` i(x ′) ) + κ. To formalize the interlayer dependencies, for each
i ∈ [η`] we let E`i denote the (desirable) event that ẑ`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 ŵ`i = ŵ `+ i − ŵ `− i ∈ R1×η `−1 such that
P ( E`i | E`−1 ) = P ( ẑ`i (x) ∈ (1± 2 (`− 1) ε`+1) z`i (x) | E`−1 ) ≥ 1− δ/η, (1)
where ε` = ε ′
∆̂`→ and nnz(ŵ`i ) ≤
⌈ 8S log(η η∗) log(8 η/δ)
ε`2
⌉ + 1, where S = ∑ j∈W+ sj + ∑ j∈W− sj .
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 Ŵ ` ∈ Rη`×η`−1 such that, for ẑ`(x) = Ŵ `â`(x),
P (Ŵ 2,...,Ŵ `), x (E`) = P (Ŵ 2,...,Ŵ `), x
( ẑ`(x) ∈ (1± 2 (`− 1) ε`+1) z`(x) ) ≥ 1− δ ∑` `′=2 η `′
η .
Theorem 4 (Network Compression). For ε, δ ∈ (0, 1), Algorithm 1 generates a set of parameters θ̂ = (Ŵ 2, . . . , Ŵ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.

heading: 5.4 GENERALIZATION BOUNDS
text: 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θ : Rd → Rk parameterized by θ with respect to a desired margin γ > 0 and distribution D is defined by Lγ(fθ) = P(x,y)∼DX ,Y (fθ(x)y ≤ γ + maxi 6=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 L0(fθ̂) with respect to the points in P ⊆ X , |P| = n, is bounded by
L0(fθ̂) ≤ L̂γ(fθ) + Õ √maxx∈P ‖fθ(x)‖22 L2 ∑L`=2(∆̂`→)2 ∑η`i=1 S`i γ2 n  .

heading: 6 RESULTS
text: 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 CIFAR10 (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.

heading: 7 CONCLUSION
text: 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.

heading: ACKNOWLEDGMENTS
text: This research was supported in part by the National Science Foundation award IIS-1723943. We thank Brandon Araki and Kiran Vodrahalli for valuable discussions and helpful suggestions. We would also like to thank Kasper Green Larsen, Alexander Mathiasen, and Allan Gronlund for pointing out an error in an earlier formulation of Lemma 6.

heading: A PROOFS OF THE ANALYTICAL RESULTS IN SECTION 5
text: This section includes the full proofs of the technical results given in Sec. 5.

heading: A.1 ANALYTICAL RESULTS FOR SECTION 5.2 (IMPORTANCE SAMPLING BOUNDS FOR POSITIVE WEIGHTS)

heading: A.1.1 ORDER STATISTIC SAMPLING
text: 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 = {X1, . . . , Xn} be a set of n = |P| i.i.d. samples each drawn from the distribution D. Let Xn+1 ∼ D be an i.i.d. sample. Then,
P ( K max
X∈P X < Xn+1
) ≤ exp(−n/K)
Proof. Let Xmax = maxX∈P ; then, P(KXmax < Xn+1) = ∫ M
0
P(Xmax < x/K|Xn+1 = x) dP(x)
= ∫ M 0 P (X < x/K)n dP(x) since X1, . . . , Xn are i.i.d.
≤ ∫ M
0
F (x/K)n dP(x) where F (·) is the CDF of X ∼ D
≤ F (M/K)n ∫ M
0
dP(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 ĝj(x) of an edge j after the previous layers have already been compressed be
ĝj(x) = wj âj(x)∑
k∈W wk âk(x) .
Lemma 7 (Empirical Sensitivity Approximation). Let ε ∈ (0, 1/2), δ ∈ (0, 1), ` ∈ {2, . . . , L}, Consider a set S = {x1, . . . , xn} ⊆ P of size |S| ≥ dlog (8 η η∗/δ) log(η η∗)e. Then, conditioned on the event E1/2 occurring, i.e., â(x) ∈ (1± 1/2)a(x),
P x∼D
( ∃j ∈ W : C sj < ĝj(x) | E1/2 ) ≤ δ
8 η ,
where C = 3 log(η η∗) andW ⊆ [η`−1].
Proof. Consider an arbitrary j ∈ W and x′ ∈ S corresponding to gj(x′) with CDF Fj (·) and recall that M = min{x ∈ [0, 1] : Fj (x) = 1} as in Assumption 1. Note that by Assumption 1, we have
F (M/K) ≤ exp(−1/K),
and so the random variables gj(x′) for x′ ∈ S satisfy the CDF condition required by Lemma 6. Now let E be the event that K sj < gj(x) holds. Applying Lemma 6, we obtain
P(E) = P(K sj < gj(x)) = P ( K max
x′∈S gj(x
′) < gj(x) ) ≤ exp(−|S|/K).
Now let Ê denote the event that the inequality Csj < ĝj(x) = wj âj(x)∑ k∈W wk âk(x)
holds and note that the right side of the inequality is defined with respect to ĝj(x) and not gj(x). Observe that since we conditioned on the event E1/2, we have that â(x) ∈ (1± 1/2)a(x).
Now assume that event Ê holds and note that by the implication above, we have
C sj < ĝj(x) = wj âj(x)∑
k∈W wk âk(x) ≤ (1 + 1/2)wj aj(x) (1− 1/2) ∑ k∈W wk ak(x)
≤ 3 · wj aj(x)∑ k∈W wk ak(x) = 3 gj(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 Ê occurs, we obtain the inequality
3K sj ≤ 3 gj(x)⇔ K sj ≤ gj(x), which is precisely the definition of event E . Thus, we have shown the conditional implication ( Ê |
E1/2 ) ⇒ E , which implies that
P(Ê | E1/2) = P(C sj < ĝ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 sj < ĝj(x) | E1/2) ≤ ∑ j∈W P(C sj < ĝ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|.

heading: A.1.2 PROOF OF LEMMA 1
text: 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 ŵ such that
P (∑ k∈W ŵk âk(x) /∈ (1± ε) ∑ k∈W wk âk(x) | E1/2 ) ≤ 3δ 8η
where nnz(ŵ) ≤ ⌈
8S log(η η∗) log(8 η/δ) ε2
⌉ , and S = ∑ j∈W sj .
Proof. Let ε, δ ∈ (0, 1) be arbitrary. Moreover, let C be the coreset with respect to the weight indices W ⊆ [η`−1] used to construct ŵ. Note that as in SPARSIFY, C is a multiset sampled fromW of size m = ⌈ 8S log(η η∗) log(8 η/δ)
ε2
⌉ , where S = ∑ j∈W sj and C is sampled according to the probability
distribution q defined by qj =
sj S
∀j ∈ W.
Let â(·) be an arbitrary realization of the random variable â`−1(·), let x be a realization of x ∼ D, and let ẑ = ∑ k∈W ŵk âk(x)
be the approximate intermediate value corresponding to the sparsified matrix ŵ and let z̃ = ∑ k∈W wk âk(x).
Now define E to be the (favorable) event that ẑ ε-approximates z̃, i.e., ẑ ∈ (1±ε)z̃, We will now show that the complement of this event, Ec, 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 â) and defined as follows:
Z = {x′ ∈ supp(D) : ĝj(x′) ≤ Csj ∀j ∈ W} ,
where C = 3 log(η η∗). Let EZ denote the event that x ∈ Z where x is a realization of x ∼ D.
Conditioned on EZ , event Ec occurs with probability ≤ δ4η : Let x be a realization of x ∼ D such that x ∈ Z and let C = {c1, . . . , cm} be m samples fromW with respect to distribution q as before. Define m random variables Tc1 , . . . , Tcm such that for all j ∈ C
Tj = wj âj(x) mqj = S wj âj(x) msj . (2)
For any j ∈ C, we have for the conditional expectation of Tj :
E [Tj | â(·),x, EZ , E1/2] = ∑ k∈W wk âk(x) mqk · qk
= ∑ k∈W wk âk(x) m
= z̃
m ,
where we use the expectation notation E [·] with the understanding that it denotes the conditional expectation E C | âl−1(·), x [·]. Moreover, we also note that conditioning on the event EZ (i.e., the event that x ∈ Z) does not affect the expectation of Tj . Let T = ∑ j∈C Tj = ẑ denote our approximation and note that by linearity of expectation,
E [T | â(·),x, EZ , E1/2] = ∑ j∈C E [Tj | â(·),x, EZ , E1/2] = z̃
Thus, ẑ = T is an unbiased estimator of z̃ for any realization â(·) and x; thus, we will henceforth refer to E [T | â(·), 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 Tj = 0 for all j ∈ C almost surely, which follows by the fact that Tj ≥ 0 for all j ∈ C by definition ofW and the non-negativity of the ReLU activation. Therefore, in the case that z̃ = 0, it follows that
P(|ẑ − z̃| > εz̃ | â(·),x) = P(ẑ > 0 | â(·),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 Pŵ | â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 :
Csj ≥ ĝj(x) = wj âj(x)∑
k∈W wk âk(x) = wj âj(x) z̃
3Since we conditioned on the event EZ .
⇔ wj âj(x) sj ≤ C z̃. (3)
Utilizing the inequality established above, we bound the conditional variance of each Tj , j ∈ C as follows
Var(Tj | â(·),x, EZ , E1/2) ≤ E [(Tj)2 | â(·),x, EZ , E1/2]
= ∑ k∈W (wk âk(x)) 2 (mqk)2 · qk
= S
m2 ∑ k∈W (wk âk(x)) 2 sk
≤ S m2 (∑ k∈W wk âk(x) ) C z̃
= S C z̃2
m2 ,
where Var(·) is short-hand for VarC | âl−1(·), x (·). Since T is a sum of (conditionally) independent random variables, we obtain
Var(T | â(·),x, EZ , E1/2) = mVar(Tj | â(·),x, EZ , E1/2) (4)
≤ S C z̃ 2
m .
Now, for each j ∈ C let
T̃j = Tj − E [Tj | â(·),x, EZ , E1/2] = Tj − 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 EZ ), we obtain by definition of Tj in (2) and the inequality (3):
Tj = S wj âj(x) msj ≤ S C z̃ m . (5)
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 sj = ∑ j∈W max x′∈S gj(x ′)
≥ 1 |S| ∑ j∈W ∑ x′∈S gj(x ′) = 1 |S| ∑ x′∈S ∑ j∈W gj(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:
|T̃j | = ∣∣∣∣Tj − z̃m ∣∣∣∣ ≤ S C z̃m = M, (6) which follows from the fact that: if Tj ≥ z̃m : Then, by our bound in (5) and the fact that z̃ m ≥ 0, it follows that ∣∣∣T̃j∣∣∣ = Tj − z̃ m ≤ S C z̃ m − z̃ m ≤ S C z̃ m .
if Tj < z̃m : Then, using the fact that Tj ≥ 0 and S ≥ 1, we obtain∣∣∣T̃j∣∣∣ = z̃ m − Tj ≤ z̃ m ≤ S C z̃ m .
Applying Bernstein’s inequality to both T̃ and −T̃ we have by symmetry and the union bound, P(Ec | â(·),x, EZ , E1/2) = P ( |T − z̃| ≥ εz̃ | â(·),x, EZ , E1/2 ) ≤ 2 exp ( − ε 2z̃2
2 Var(T | â(·),x) + 2 ε z̃M3
)
≤ 2 exp ( − ε 2z̃2
2SC z̃2 m + 2S C z̃2 3m
)
= 2 exp ( −3 ε 2m
8S C ) ≤ δ
4η ,
where the second inequality follows by our upper bounds on Var(T | â(·),x) and ∣∣∣T̃j∣∣∣ and the fact
that ε ∈ (0, 1), and the last inequality follows by our choice of m = ⌈
8S log(η η∗) log(8 η/δ) ε2
⌉ . This
establishes that for any realization â(·) of âl−1(·) and a realization x of x satisfying x ∈ Z , the event Ec occurs with probability at most δ4η .
Removing the conditioning on EZ : We have by law of total probability P(E | â(·), E1/2) ≥ ∫ x∈Z P(E | â(·),x, EZ , E1/2) P x∼D (x = x | â(·), E1/2) dx
≥ (
1− δ 4η )∫ x∈Z P x∼D (x = x | â(·), E1/2) dx
= ( 1− δ
4η
) P
x∼D (EZ | â(·), E1/2) ≥ (
1− δ 4η
)( 1− δ
8η ) ≥ 1− 3δ
8η
where the second-to-last inequality follows from the fact that P(Ec | â(·),x, EZ , 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 â`−1(·) to establish P(E | E1/2) = ∫ â(·) P(E | â(·), E1/2)P(â(·) | E1/2) dâ(·)
≥ (
1− 3δ 8η )∫ â(·) P(â(·) | E1/2) dâ(·)
= 1− 3δ 8η .
Consequently,
P(Ec | E1/2) ≤ 1− (
1− 3δ 8η
) = 3δ
8η ,
and this concludes the proof.

heading: A.2 ANALYTICAL RESULTS FOR SECTION 5.3 (IMPORTANCE SAMPLING BOUNDS)
text: 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 Yx′ = E [∆`i(x′)]−∆`i(x′) for each x′ ∈ S and consider the sum Y = ∑ x′∈S Yx′ = ∑ x′∈S ( E [∆`i(x)]−∆`i(x′) ) .
We know that each random variable Yx′ satisfies E [Yx′ ] = 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 { t2
4λ2∗ , t 2λ∗
}) .
Since S = dlog (8 η η∗/δ) log(η η∗)e ≥ 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 Yx, 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 η∗ ≥ η`.

heading: A.2.2 NOTATION FOR THE SUBSEQUENT ANALYSIS
text: Let ŵ`+i and ŵ `− 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 ŵ`+i and ŵ `− i as simply ŵ + and ŵ−, respectively.
Let x ∼ D and define ẑ+(x) = ∑ k∈W+ ŵ+k âk(x) ≥ 0 and ẑ −(x) = ∑ k∈W− (−ŵ−k ) âk(x) ≥ 0
be the approximate intermediate values corresponding to the sparsified matrices ŵ+ and ŵ−; let z̃+(x) = ∑ k∈W+ wk âk(x) ≥ 0 and z̃−(x) = ∑ k∈W− (−wk) âk(x) ≥ 0
be the corresponding intermediate values with respect to the the original row vector w; and finally, let z+(x) = ∑ k∈W+ wk ak(x) ≥ 0 and z−(x) = ∑ k∈W− (−wk) ak(x) ≥ 0
be the true intermediate values corresponding to the positive and negative valued weights.
Note that in this context, we have by definition
ẑ`i (x) = 〈ŵ, â(x)〉 = ẑ+(x)− ẑ−(x), z̃`i (x) = 〈w, â(x)〉 = z̃+(x)− z̃−(x), and z`i (x) = 〈w, a(x)〉 = z+(x)− z−(x),
where we used the fact that ŵ = ŵ+ − ŵ− ∈ R1×η`−1 .

heading: A.2.3 PROOF OF LEMMA 2
text: Lemma 2 (Conditional Neuron Value Approximation). Let ε, δ ∈ (0, 1), ` ∈ {2, . . . , L}, i ∈ [η`], and x ∼ D. CORENET generates a row vector ŵ`i = ŵ `+ i − ŵ `− i ∈ R1×η `−1 such that
P ( E`i | E`−1 ) = P ( ẑ`i (x) ∈ (1± 2 (`− 1) ε`+1) z`i (x) | E`−1 ) ≥ 1− δ/η, (1)
where ε` = ε ′
∆̂`→ and nnz(ŵ`i ) ≤
⌈ 8S log(η η∗) log(8 η/δ)
ε`2
⌉ + 1, where S = ∑ j∈W+ sj + ∑ j∈W− sj .
Proof. Let ε, δ ∈ (0, 1) be arbitrary and let W+ = {j ∈ [η`−1] : wj > 0} and W− = {j ∈ [η`−1] : wj < 0} as in Alg. 1. Let ε` be defined as before, ε` = ε ′
∆̂`→ , where ∆̂`→ = ∏L k=` ∆̂ k and
∆̂` = (
1 |S| maxi∈[η`] ∑ x′∈S ∆ ` i(x ′) ) + κ.
Observe that wj > 0 ∀j ∈ W+ and similarly, for all (−wj) > 0 ∀j ∈ W−. That is, each of index setsW+ andW− 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 ≤ ε 2L−`+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 â(x) ∈ (1 ± ε/2)a(x), where, as before, â and a are shorthand notations for â`−1 ∈ Rη`−1×1 and a`−1 ∈ Rη`−1×1, respectively. This implies that E`−1 ⇒ E1/2 and since m = ⌈ 8S log(η η∗) log(8 η/δ)
ε2
⌉ in Alg. 2 we can invoke Lemma 1 with ε = ε` on each of the SPARSIFY
invocations to conclude that
P ( ẑ+(x) /∈ (1± ε`)z̃+(x) | E`−1 ) ≤ P ( ẑ+(x) /∈ (1± ε`)z̃+(x) | E1/2 ) ≤ 3δ
8η ,
and
P ( ẑ−(x) /∈ (1± ε`)z̃−(x) | E`−1 ) ≤ 3δ
8η .
Therefore, by the union bound, we have
P ( ẑ+(x) /∈ (1± ε`)z̃+(x) or ẑ−(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

heading: 1. ẑ+(x) ∈ (1± ε`)z̃+(x) and ẑ−(x) ∈ (1± ε`)z̃−(x) (7)

heading: 2. ∆`i(x) ≤ ∆̂` (8)
text: Recall that ε′ = ε2 (L−1) , ε` = ε′ ∆̂`→ , and that event E`i denotes the (desirable) event that
ẑ`i (x) (1± 2 (`− 1) ε`+1) z`i (x)
holds, and similarly, E` = ∩i∈[η`] E`i denotes the vector-wise analogue where
ẑ`(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
â`−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
ẑ`i (x) ∈ (1± 2 (`− 1)ε`+1) z`i (x),
which would immediately imply by definition of the ReLU function that
â`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− δ/η
ẑ(x) = ẑ+(x)− ẑ−(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 ε` ≤ 12 (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 ẑ(x) ≤ ( 1 + k ε2` ) z(x) + (k + 1) ε`+1 |z(x)|
≤ (1 + ε`)z(x) + (k + 1)ε`+1z(x) ≤ (1 + ε`+1)z(x) + (k + 1)ε`+1z(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
ẑ(x) ≤ ( 1 + k ε2` ) z(x) + (k + 1) ε`+1 |z(x)|
≤ z(x)− (k + 1)ε`+1z(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 ẑ(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 ẑ(x) ≥ z(x)−2 (`−1)ε`+1|z(x)|. Putting both the upper and lower bound together, we have that with probability at least 1− δη :
ẑ(x) ∈ (1± 2 (`− 1)ε`+1) z(x),
and this completes the proof.

heading: A.2.4 REMARKS ON NEGATIVE ACTIVATIONS
text: 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) = apos(x) − aneg(x), where apos(x) ≥ 0 ∈ Rη `−1 and aneg(x) ≥ 0 ∈ Rη `−1 . Furthermore, we can define the sensitivity over the set of points {apos(x), aneg(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+ wk apos,k(x) ≥ 0 and z−neg(x) = ∑ k∈W− (−wk) aneg,k(x) ≥ 0
be the corresponding positive parts, and z+neg(x) = ∑ k∈W+ wk aneg,k(x) ≥ 0 and z−pos(x) = ∑ k∈W− (−wk) apos,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. ẑ+pos(x), ẑ − neg(x), ẑ + neg(x), and ẑ − pos(x)) to obtain the desired overall failure probability of δ/η.

heading: A.2.5 PROOF OF THEOREM 4
text: 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 Ŵ ` = ( ŵ`1, . . . , ŵ ` η`
)> ∈ Rη`×η`−1 such that P(E` | E`−1) = P ( ẑ`(x) ∈ (1± 2 (`− 1) ε`+1) z`(x) | E`−1 ) ≥ 1− δ η `
η , (9)
where ε` = ε ′
∆̂`→ , ẑ`(x) = Ŵ `â`(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− η
`δ η
ẑ`(x) = Ŵ `â`−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 Ŵ 2, . . . , Ŵ ` for multiple layers.
Lemma 3 (Layer-wise Approximation). Let ε, δ ∈ (0, 1), ` ∈ {2, . . . , L}, and x ∼ D. CORENET generates a sparse weight matrix Ŵ ` ∈ Rη`×η`−1 such that, for ẑ`(x) = Ŵ `â`(x),
P (Ŵ 2,...,Ŵ `), x (E`) = P (Ŵ 2,...,Ŵ `), x
( ẑ`(x) ∈ (1± 2 (`− 1) ε`+1) z`(x) ) ≥ 1− δ ∑` `′=2 η `′
η .
Proof. Invoking Corollary 9, we know that for any layer `′ ∈ {2, . . . , L},
P Ŵ `′ , x, â`′−1(·)
(E` ′ | E` ′−1) ≥ 1− δ η `′
η . (10)
We also have by the law of total probability that
P(E` ′ ) = P(E` ′ | E` ′−1)P(E` ′−1) + P(E` ′ | (E` ′−1)c)P((E` ′−1)c)
≥ P(E` ′ | E` ′−1)P(E` ′−1) (11)
Repeated applications of (10) and (11) in conjunction with the observation that P(E1) = 14 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 Inequality5 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 θ̂ = (Ŵ 2, . . . , Ŵ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− δ.
4Since we do not compress the input layer. 5The 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 θ̂ = (Ŵ 2, . . . , ŴL),
P̂ θ, x
( fθ̂(x) ∈ 2 (L− 1) εL+1fθ(x) ) = P̂ θ, x (ẑL(x) ∈ 2 (L− 1) εL+1zL(x))
= P(EL) ≥ 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`ika `−1 k (x) for all k ∈ W and x ∈ S , for a total computation time that is bounded
above byO ( |S| η`−1 ) since |W| ≤ η`−1 for each i ∈ [η`]. Thus, SPARSIFY takesO ( |S| η`−1 ) time. Summing the computation time over all layers and neurons in each layer, we obtain an asymptotic time complexity ofO ( |S| ∑L `=2 η `−1η` ) ⊆ O (|S| η∗ η). Since |S| ∈ O(log(η η∗/δ)), we conclude that the computational complexity our neural network compression algorithm is
O ( η η∗ log ( η η∗/δ )) . (12)

heading: A.2.6 PROOF OF THEOREM 11
text: 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 dlog (8 η η∗/δ) log(η η∗)e.
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 ,
sj = max x∈S gj(x) ≤ ∑ x∈S gj(x) = ∑ x∈S wj aj(x)∑ k∈W wk ak(x) ,
where the inequality follows from the fact that we can upper bound the max by a summation over x ∈ S since gj(x) ≥ 0, ∀j ∈ W . Thus,
S+ = ∑ j∈W sj ≤ ∑ j∈W ∑ x∈S gj(x)
= ∑ x∈S ∑ j∈W wj aj(x)∑ k∈W wk ak(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− sj ≤ |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, we 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(η η∗/δ) log2(η η∗) η L2
ε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.

heading: A.2.7 GENERALIZED NETWORK COMPRESSION
text: 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.d. input points P ′ of cardinality |P ′| ∈ N+, i.e., P ′
i.i.d.∼ D|P′|, consider the reparameterized version of Alg. 1 with
1. S ⊆ P of size |S| ≥ dlog (16 |P ′| η η∗/δ) log(η η∗)e,
2. ∆̂` = (
1 |S| maxi∈[η`] ∑ x′∈S ∆ ` i(x ′) ) + κ as before, but κ is instead defined as
κ = √ 2λ∗ ( 1 + √ 2λ∗ log (16 |P ′| η η∗/δ) ) , and
3. m ≥ ⌈
8S 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 ′|/δ)L2 ε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.

heading: B ADDITIONAL RESULTS
text: 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.

heading: B.1 DETAILS ON THE COMPRESSION ALGORITHMS
text: 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 (Ŵ 2, . . . , ŴL) to obtain the corresponding parameters θ̂ = (Ŵ 2r , . . . , Ŵ 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 wij of some weight matrix W is sampled with probability
pij = |wij | ‖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
pij = w2ij
‖W‖2F ,
where ‖·‖F is the Frobenius norm of W , and reweighted accordingly.
5. `1+`22 Sampling (Kundu & Drineas, 2014) – The entries (i, j) of each weight matrix W are sampled with distribution
pij = 1
2
( w2ij
‖W‖2F + |wij | ‖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.
7. 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 C1, . . . , 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).

heading: B.2 PRESERVING THE OUTPUT OF A NEURAL NETWORK
text: 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 Ptest ⊆ Rd consisting of d dimensional points, the average relative error of with respect to the fθ̂ generated by each compression algorithm was computed as
errorPtest(fθ̂) = 1 |Ptest| ∑
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.

heading: B.3 PRESERVING THE CLASSIFICATION PERFORMANCE
text: We also evaluated the accuracy of our approximation by computing the loss of prediction accuracy on a test data set, Ptest. In particular, let accPtest(fθ) be the average accuracy of the neural network fθ, i.e,.
accPtest(fθ) = 1 |Ptest| ∑
x∈Ptest
1 ( argmax i∈[ηL] fθ(x) 6= y(x) ) ,
where y(x) denotes the (true) label associated with x. Then the drop in accuracy is computed as
accPtest(fθ)− accPtest(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.

heading: B.4 PRELIMINARY RESULTS WITH RETRAINING
text: We compared the performance of our approach with that of the popular weight thresholding heuristic – henceforth 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.

heading: B.5 DISCUSSION
text: 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.

Review summaries:
Given an additively decomposable function F(X, Q) = sum_over_x_in_X cost(x, Q), one can approximate it using either random sampling of x in X (unbiased, possibly high variance), or using importance sampling and replace the sum_over_x with a sum_over_coreset importance_of_a_point * cost(x, Q) which if properly defined can be both unbiased and have low variance [1]. In this work the authors consider the weighted sum of activations as F and suggest that for each neuron we can subsample the incoming edges. To construct the importance sampling strategy the authors adapt the classic notion of sensitivity from the coreset literature. Then, one has to carefully balance the approximation quality from one layer to the next and essentially union bound the results over all layers and all sampled points. The performed analysis is sound (up to my knowledge).

The authors propose to reduce the size of fully connected neural networks, defined as the total number of nonzeros in the weight matrices, by calculating sensitivity scores for each incoming connection to a neuron, and randomly keeping only some of the incoming connections with probability proportional to their share of the total sensitivity. They provide a specific definition for the sensitivity scores and establish that the sparsified neural network, with constant probability for any sample from the training population, provides an output that is a small multiplicative factor away from the output of the unsparisfied neural network. The cost of the sparsification is essentially the application of the trained neural network to a small number of data points in order to compute the sensitivity scores