Data-Independent Neural Pruning via Coresets
Authors: Ben Mussay
Margarita Osadchy
Vladimir Braverman
Samson Zhou
Dan Feldman
Venue:  (2020)
Keywords: coresets
neural pruning
network compression

Abstract: Previous work showed empirically that large neural networks can be significantly reduced in size while preserving their accuracy. Model compression became a central research topic, as it is crucial for deployment of neural networks on devices with limited computational and memory resources. The majority of the compression methods are based on heuristics and offer no worst-case guarantees on the trade-off between the compression rate and the approximation error for an arbitrarily new sample.

We propose the first efficient, data-independent neural pruning algorithm with a provable trade-off between its compression rate and the approximation error for any future test sample. Our method is based on the coreset framework, which finds a small weighted subset of points that provably approximates the original inputs. Specifically, we approximate the output of a layer of neurons by a coreset of neurons in the previous layer and discard the rest. We apply this framework in a layer-by-layer fashion from the top to the bottom. Unlike previous works, our coreset is data independent, meaning that it provably guarantees the accuracy of the function for any input $x\in \mathbb{R}^d$, including an adversarial one. We demonstrate the effectiveness of our method on popular network architectures. In particular, our coresets yield 90% compression of the LeNet-300-100 architecture on MNIST while improving the accuracy.

Published as a conference paper at ICLR 2020
DATA-INDEPENDENT NEURAL PRUNING VIA CORESETS
Ben Mussay
Margarita Osadchy
Computer Science Department University of Haifa
Computer Science Department
University of Haifa
Haifa, Israel bengordoncshal fa@gma com
Haifa, Israel
rita@cs
Vladimir Braverman
Samson Zhou
Computer Science Department
Computer Science Department
Johns Hopkins University
Carnegie Mellon University
Baltimore, MD., USA vovašcs. juu.
Pittsburgh, IN., USA samsonzhouee gma com
Dan Feldman
Computer Science Department University of Haifa Haifa, Israel dannyf f. post 8gma com
ABSTRACT
Previous work showed empirically that large neural networks can be significantly reduced in size while preserving their accuracy. Model compression became central research topic, as it is crucial for deployment of neural networks on de- vices with limited computational and memory resources. The majority of the compression methods are based on heuristics and offer no worst-case guarantees on the trade-off between the compression rate and the approximation error for an arbitrarily new sample.
We propose the first efficient, data- inta-indeeendent neural pruning algorithm with provable trade-off hetween its compression rate and the approximation error for any future test sample. Our method is based the coreset framework, which finds a small weighted subset of points that provably approximates the original inputs. Specifically, we approximate the output of a layer of neurons by a coreset of neurons in the previous layer and discard the rest. We apply this framework in a layerr fashion from the top the bottom. Unlike previous works, our coreset is data independent, meaning that it provably guarantees the accuracy of the function for any input x E RR,, including an adversarial one. We demonstrate the effectiveness of our method on popular network architectures. In particular, our coresets yield 90% compression of the LcNet-300-11 architecture on MNIST while improving classification accuracy.
INTRODUCTION
Neural networks today are the most popular and effective instrument of machine learning with nu- merous applications in different domains. Since Krizhevsky et al. (2012) used model with 60M parameters to win the ImageNet competition 2012, network architectures have been growing wider and deeper. The vast overparametrizatioon of neural networks offers better convergence (Allen- Zhu et al., 2019) and better generalization (Neyshabur et al., 2018). The downside of the over- parametrization is its high memory and computational costs, which prevent the use of these networks in small devices, e.g., smartphones. Fortunately, it was observed that trained network could re- duced to smaller sizes without much accuracy loss. Following this observation, many approaches to

---

Published as a conference paper at ICLR 2020
compress existing models have been proposed (see Gale et al. (2019) for recent review network sparsification, and Mozer Smolensky (1989); Srivastava et al. (2014); Yu et al. (2018); He et al. (2017) for neural pruning).
Although a variety model compression heuristics have been successfully applicd to different neu- ral network models, such Jacob et al. (2018); Han al. (2015); Alvarez & Salzmann (2017), these approaches generally lack strong provable guarantees on the trade-off between the compression rate and the approximation error. The absence of worst-case performance analysis can poten- tially be a glaring problem depending on the application. Moreover, data-dependent methods for model compression (e.g., Mozer & Smolensky (1989); Srivastava al. (2014); Hu al. (2016); Yu et al. (2018); Baykal et al. (2018)) rely on the statistics presented in data set. Hence, these methods are vulnerable to adversarial attacks (Szegedy et al., 2014), which design inputs that do not follow these statistics.
Ideally, a network compression framework should 1) provide provable guarantees on the trade- off between the compression rate and the approximation error, 2) be data independent, 3) provide high compression rate, and 4) be computationally efficient. To address these goals, we propose an efficient framework with provable guarantees for neural pruning, which is based on the existing theory of coresets such as (Braverman et al., 2016). Coresets decrease massive inputs to smaller instances while maintaining good provable approximation of the original set with respect a given function. Our main idea is to treat neurons a neural network as inputs in a coreset framework. Specifically, reduce the number of neurons in layer i by constructing coreset of neurons in this layer that provably approximates the output of neurons in layer + 1 and discarding the rest. The coreset algorithm provides with the choice of neurons in layer and with the new weights connecting these neurons to layer i+1. The coreset algorithm is applied layer-wise from the bottom the top of the network.
The size of the coreset, and consequently the number of remaining neurons in layer i, is provably related the approximation error of the output for every neuron in layer 1. Thus, we can theoretically derive the trade-off between the compression rate and the approximation error of any layer in the neural network. The coreset approximation of neurons provably holds for any input; thus our compression is data-independent.
Similar to our approach, Baykal et al. (2018) used coresets for model compression. However, their coresets are data-dependent; therefore, they cannot guarantee robustness over inputs. Moreover, they construct coresets of weights, while our approach constructs coresets of ncurons. Neural pruning reduces the size of the weight tensors, while keeping the network dense. Hence the implementation of the pruned network requires no additional effort. Implementing networks with sparse weights (which is the result of weight pruning) is harder and in many cases does not result in actual compu- tational savings.
Our empirical results LeNet- for MNIST (LeCun et al., 1998) and VGG-16 (Simonyan & Zisserman, 2014) for CIFAR-10 (Krizhevsky, 2009) demonstrate that our framework based on coresets of neurons outperforms sampling- ficing the accuracy. Finally, our construction is very fast; it took about 56 sec. to compress each dense layer in the VGG-16 network using the platform specified in the experimental section.
coresets by improving compression without sacri-
We propose an efficient, data-independent neural pruning algorithm with provable trade-off between the compression rate and the output approximation error. This is the first framework to perform neural pruning via coresets. We provide theoretical compression rates for some of the most popular neural activation functions summarized in Table 2.
Our Contributions:
RELATED WORK
2.1 CORESETS
Our compression algorithm based on a data summarization approach known as coresets. Over the past decade. coreset constructions have been recognized for high achievements in data reduction in a variety of applications, including memaass, SVD, regression, low-rank approximation, PageRank, convex hull, and SVM; details in Phillips (2016). Many of the non-deterministic coreset based
2

---

Published as a conference paper at ICLR 2020
methods rely on the sensitivity framework, in which elements of the input are sampled according to their sensitivity (Langberg & Schulman, 2010; Braverman et al., 2016; Tolochinsky & Feldman, 2018), which is used as measure of their importance. The sampled elements usually reweighted afterwards.
2.2 MODEL COMPRESSION
State-of-the-art neural networks are often overparameterized, which causes a significant redundancy of weights. To reduce both computation time and memory requirements of trained networks, many approaches aim removing this redundancy by model compression.
Weight pruning was considered as far back as 1990 (LeCun et al., 1990), but has recently seen more study (Lebedev & Lempitsky, 2016; Dong al., 2017). One of the most popular approaches is pruning via sparsity. Sparsity can be enforced by L1 regularization to push weights towards zero during training (Hu et al., 2016). However, it was observed (Han et al., 2015) that after fine-tuning of the pruned network, L2 regularized network outperformed L1. as there is no benefit to pushing values towards zero compared to pruning unimportant (small weight) connections.
Weight Pruning:
The approach in Denton et al. (2014) exploits the linearity of the neural network by finding a low- rank approximation of the weights and keeping the accuracy within 1 1% of the uncompressed model. Jacob et al. (2018) performs quantization of the neural network's weights and suggests a new training procedure to preserve the model accuracy after the quantization.
These methods showed high compression rates, c.g., the compression rate of AlexNet can reach 35x with the combination of pruning, quantization, and Huffman coding (Han et al., 2016). Nevertheless, strong provable worst-case analysis is noticeably absent for most weight pruning methods.
Weight pruning leads to an irregular network structure, which needs a special treatment to deal with sparse representations, making it hard to achieve actual computational sav- ings. On the other hand, neural pruning (Hu et al., 2016) and filter pruning in CNNs (e.g, Zhuang al. (2018); Li al. (2017); Liu al. (2017) simply reduce the size of the tensors.
Neural pruning:
The method in Hu et al. (2016) first identifies weak neurons by analyzing their activiations on large validation dataset. Then those weak neurons are pruned and the network is retrained. The processes are repeated several times. Zhuang et al. (2018) introduces channel pruning based on the contribution to the discriminative power. These methods are data-dependent; thus they cannot provide guarantees of approximation error for any future input.
Li al. (2017) measures the importance of channels by calculating the sum of absolute values of weights. Other channel pruning methods either impose channel-wise sparsity in training, followed by pruning channels with small scaling factors, and fine-tuning (e.g. Liu et al. (2017)) or perform channel pruning by minimizing the reconstruction error of feature maps between the pruned and pre-trained model (e.g., He et al. (2017).) These methods lack provable guarantees on the trade-offs between their accuracy and compression.
Coreset-Basse Based Model Compression Similar to our work, the approach in Baykal et al. (2018) uses corests for model compression. However, they construct coresets of weights, while we con- struct coresets of neurons. Their approach computes the importance of each weight, which is termed sensitivity, using subset from the validation set. The coreset is chosen for the specific distribution (of data) so consequently, the compressed model is data detiddeeeeddnt.. In our construction, the input of the neural network assumed to be an arbitrary vector IRd and the sensitivity of neuron is computed for every input in RRd This means that we create a data-independent coreset; its size is in- dependent of the properties of the specific data at hand, and the compression provably approximates any future test sample.
Dubey et al. (2018) builds upon k-means coresets by adding a sparsity constraint. The weighting of the filters in the coreset is obtained based on their activation magnitudes over the training set. The compression pipeline also includes a pre-processing step that follows a simple heuristic that eliminates filters based on the mean of their activation norms over the training set. This construction obviously data-dependent and uses corsets as an alternative mechanism for low-rank approxi- mation of filters.
3

---

Published as a conference paper at ICLR 2020
d(p x)
P1d
wi50lrf
w2y0(pf 2)
Pra
01g o(gf x)
Input Layer R
Hidden Layer E R?
Output Layer R?
d(p
Σ
21
(e(1.447)
22
Σ
u2
JE(1,37)
Pra
G1 = ol x) Layer
Input Layer
Output Layer
Figure 1: Illustration of our neuron coreset construction on a toy example: (a) a full network, (b) the compressed network. Both neurons in the second layer (b) choose the same coreset comprising neurons {1, 3, 7} from layer 1, but with different weights. The compressed network has pruned neurons (2,5, 5, 6} from layer
METHOD
We propose an algorithm for compressing layer and we apply to all layers from the bottom to the top of the network. We first give intuitive description of the algorithm. We then formalize it and provide a theoretical analysis of the proposed construction.
3.1 DATA-INDEPENDENT CORESET FOR NEURAL PRUNING
Let at <(p x:) be the jth neuron in layer i, in which Py denotes its weights, and denotes an arbitrary input in Rd (see Figure 1, top). We first consider a single neuron in layer i + 1. The linear part of this neuron is E w(p))oppzz)) We would like to approximate by Σier o(p z) where J" C {1,..., [P]} is a small subset, and we want this approximation to be bounded by multiplicative factor that holds for any x E Rdd Unfortunately, our result in Theorem 6 shows that this idealized goal is impossible. However, we show in Theorem and Corollary that we can construct small coreset C, such that | - 2 < for any input e Rd.
Algorithm summarizes the coreset construction for single neuron with an activation function Φ. (our results for common neural activation functions are summarized in Table 2). Algorithm 2 and Corollary show the construction of a single coreset with possibly different weights for all neurons in layer + 1 (see Figure 1, bottom).
3.2 PRELIMINARIES
Definition (weighted set), Let P. Rdd be a finite set, and w be a function that maps every p E P weight w(p) > O. The pair (P, w) is called weighted set.
4

---

Published as a conference paper at ICLR 2020
Algorithm 1: CORESET(P. (P, u; m, 9.
Input:
A weighted set (P, w))
an integer (sample size) m 2 1,
an (activation) function R + [0. oo), an upper bound 0.
Output:
A weighted set (C, u); Theorem 7 and Corollary 8.
for every p P do
((3 Ipll) pr(p) = Egep w (33 1g
u(p) :=
C+
for m iterations do
Sample point q from P such that p chosen with probability pr(p).
C {g}
u(q) = =[g) + w(g) pr(4)
return (C, u)
coreset this paper is applied on a query space which consists of an input weighted set, an objective function, and class of models (queries) as follows.
Definition 2 (Query space). Let P' (P, w) be weighted set called the input set. Let X Rd be a set, and f P x X + [0, oo) be loss function. The tuple (P, w, X) f) is called query space.
Given a set of points P and a set of queries X, a coreset of is a weighted set of points that provides good approximation to P for any query X. We state the definition of coresets with multiplicative guarantees below, though we shall also reference coresets with additive guarantees.
Definition (e-coreset, multiplicative guarantec). Let (P, w, X. be query space, and E (0,1) be an error parameter. An e-coreset of (P, w. X, f) f) is weighted set (Q, u) such that for every E X
Σ (p))s(p,)) - Σ (1())(1)))) PEP
Se w(p)s(p,
QEQ
PEP
The size of our coresets depends on two parameters: the complexity of the activation function which defined below, and the sum of supremum that is defined later. We now recall the well-known definition of VC dimension (Vapnik & Chervonenkis, 2015) using the variant from (Feldman & Langberg, 2011).
Definition 4 (VC-dimension (Feldman & Langherg. 2011)), Let (P, w. X. be a query space. For every E Rdd. and 2 O we define rangep,(2,7)
E P f(p,2) <T} and ranges( P, X) C (ange C P,x X,r 0}. For ranges of subsets of Rd, the VC-dimension of (Rd ranges) is the size |C| of the largest subset C S Rd such that
[CC range rango E ranges)
|= 2
The VC-dimension of the query space (P,X, is the VC-dimension of (P,
The VC-dimension of all the query spaces that correspond to the activation functions Table is Od), as most of the other common activation functions (Anthony & Bartlett, 2009).
The following theorem bounds size of the coreset for given query space and explains how to construct it. Unlike previous papers such as (Feldman & Langberg, 2011), consider additive error and not multiplicative error.
Theorem (Braverman et al. (2016)). Let be the VC-dimension of a query space (P,w, X, f). x). Lef I. Eper s(p), and e, Suppose P - [0, oo) such that s(p) 2 w(p) sup (p.
5

---

Published as a conference paper at ICLR 2020
1). Lete 2 1 be sufficiently large constant that be determined from the proof, and let C' be a sample (multi-st)) of m 8²
ct dlogt + log )
i.idd points from P. where for every p E P and q E C we have pr(p s(p)/t. Then, with probability at least 8,
w(q)
Vx E X:
Σ
wwp)s((p,))
Σ
(1) Se.
mpr(q)
PEP
SEC
Algorithm 2: CORESET PER LAYER W1 WR, my v,
Input:
Weighted sets (P. w1). (.1).... ... (P, wk),
integer (sample size) 2
an (activation) function
R + [0, 0o),
upper bound 0.
Output:
A weighted set (C, u); see Theorem 7.
for every P do
pr(p)= = max ws (p) (3 [pll)
Eger max W/ (1) Ial)
u(p) 0
C
0
for m iterations do
Sample point q from P such that P is chosen with probability pr(p).
C := C {q}
w;(4)
Vi E [k] : (.(9) == u4(9) + m pr(g)
return (C, "1. uk))
3.3 MAIN THEORETICAL RESULTS
Most the coresets provide (1 + e)-multipiccative factor approximation for every query that is applied the input set. The bound on the coreset size independent at least sub-linear in the original number n of points, for any given input set. Unfortunately, the following theorem proves that it impossible to compute small coresets for many common activation functions such ReLU. This holds even if there are constraints on both the length of the input set and the test set of samples.
Theorem (No coreset for multiplicative error). Let : R + [0, oo) such that s(b) > 0 if and only b > O. Let o, 3 >> 0, e E (0, 1) and n 2 1 be an integer. Then there is set P C (0) of points such that if a weighted set (C, u) satisfies C and
Vr E BB(0):
Σ 2(pTT))
Σ [(())((Tx)) DEC
SE Σ Ed(TTa)
PEP
then C P.
The proof of Theorem 6 is provided in Appendix A.I.
The following theorem motivates the usage of additive e-error instead multiplicative (1 + error. Fortunately, in this case there is bound on the coreset's 's size for appropriate sampling distributions.
Theorem 7. Let a > O and (P, w, (0), be a query space of VC-dimension such that P C (0), the weights w are non-negative, 2:) = @(p x)) and & : IR - 10, 20) is a non-
decreasing function. Let E, 5 E (0, 1) and
m > et
(logg + log 11

---

Published as a conference paper at ICLR 2020
where
t= Ew(p) w(p)
PEP
and is sufficiently large constant that can be determined from the proof.
Let (C, u) be the output of a call to CORESET w, m, o. 3); see Algorithm 1. Then, [C] I m and, with probability al least 5,
Σ
w(p)o(p'a) Σ u(p)((p's)) Se. PEC
PEP
The proof is provided in Appendix A.2.
As weights of neural network can take positive and negative values, and the activation functions & R + IR may return negative values, we generalize result to include negative weights and any monotonic (non-decreasing or non-increasing) bounded activation function in the following corollary.
Corollary 8. Let (P, w. f) be general query spaces, of VC-dimension O(d) such that f(p, - ó0p" x)) for some monotonic function + and P C (0).). Let
sp)) sup (w(p)((p")) =ex
for every E P. Let 2 1 be a sufficiently large constant that can be determined from the proof, t Epep s(D), and
2 ct -
ddlogt log (1)
m
Let (C, u) be the output of a call to CORESET m, 1b, B); see Algorithm 1. Then, [C| S and, with probability at least 1
Yx E By(
Σ
w(p)o(p"x) Σ
"up))(p=<>) SE.
pEP
DEC
The proof of Corollary is provided in Appendix A.3.
3.4 FROM CORESET PER NEURON TO CORESET PER LAYER
Applying Algorithm to each neuron in a layer + could result in the situation that a neuron in layer is selected to the coreset of some neurons in layer i + but not others. In this situation, cannot be removed. To perform neuron pruning, every neuron in layer + 1 should select the same neurons for its coreset, maybe with different weights. Thus, we wish compute a single coreset for multiple weighted sets that are different only by their weight function. Each such a set represents neuron level i + 1, which includes neurons. Algorithm 2 and Corollary show how to compute single coreset for multiple weighted sets. Figure provides an illustration of the layer pruning on a toy example.
Corollary (Coreset per Layer). Let (P, w1, (0), wK. B)), be k query spaces, each of VC-dimension (d) such that f(p, x) = o0p" x) for some non-decreasing & : R + [0, oo) and C (0). Let
s(p)
max sup w (p)))(p'')) *E(R] #
for every P E Let be a sufficiently large constant that can be determined from the proof, t Sp)))(p)
dl (logg log (1)
m Let (C, U1 Un) be the output of a call to CORESET W1," ... Wk. m, ④. B); see Algorithm 2. Then, |C| < and, with probability least -,
Vi E [k], E (0) Σ
w.(p)((pT Σ u.(p)((p_ SE.
PEP
PEC

---

Published as a conference paper at ICLR 2020
Network
Error %
Parameters
Compression
Ratio
LeNNet3300-100
2.16
267K
LeNeet330-110
2.03
26K
90%
Pruned
VGG-16
8.95
1.4M
VGG-16 Pruned
8.16
350K
75%
Table I: Empirical evaluations of our coresets on existing architectures for MNIST and CIFAR-10.
Note the improvement of accuracy in both cases!
The proof follows directly from the observation in Theorem 5 that s(p) 2 w(p) suPsex (p.
EXPERIMENTS
We first test our neural pruning with coresets on two popular models: LeNet-300-10M on MNIST (LeCun et al., 1998), and VGG-16 (Simonyan & Zisserman, 2014) CIFAR- 10 (Krizhevsky, 2009). We then compare the compression rate of our coreset (Neuron Coreset)
to the compression methods based on the following sampling schemes:
Baselines:
uniform sampling, percentile (which deterministically retains the inputs with the highest norms), and Singular Value Decomposition (SVD);
Schemes for matrix sparsification: based LI and L2 norms and their combination (Drineas & Zouzias, 2011; Achlioptas et al., 2013; Kundu & Drineas, 2014);
Sensitivity sampling: CoreNet and CoreNet+ (Baykal et al., 2018).
In all experiments we used ReLU networks and we computed the average error of the tested al- gorithms after performing each test ten times. For every layer, after applying neural pruning the remaining weights were fine-tuned until convergence. The experiments were implemented in PyTorch (Paszke et al., 2017)
Linux Machine using Intel Xcon, 32-core CPU with 3.2 GHz, 256 GB of RAM and Nvidia TitanX and Quadro M4000 GPUs The source code of method can be found at: https: /ttp:/ggtttt//// com Beee//eaeMuuaa/aeeeeee Sewaal--runnin-vi---ooreee
aaaissssyyyaaa-aaaaaa aat//aaaaaaaaaeeaaa peata-Independett-
4.1 COMPRESSING LENET AND VGG
LeNet-300-100 network comprises two fully connected hidden layers with 300 and 100 neurons correspondingly, trained MNIST data set. Our coresets were able to prune roughly 90% of the parameters and our compression did not have any associated accuracy cost - in fact, slightly improved the classification accuracy.
VGG-16 (Simonyan & Zisserman, 2014) includes blocks comprising convolutional and pooling layers, followed by 3 dense layers the first two with 4096 neurons and the last with 1000 neurons. The model was trained and tested on CIFAR-I0. We applied our algorithm for neural pruning to the dense layers, which have the largest number parameters. Our experiment showed slight improve- ment in accuracy of classification while the number of parameters decreased by roughly 75%. We summarize findings in Table 1.
4.2 CORESETS RELU
We analyzed the empirical trade-off between the approximation enror and the size of the coreset, constructed by Algorithm and Corollary 8, comparison to uniform sampling, which also imple- ments Algorithm I, but sets the probability of point to 1/n (n is the size of the full set), and to percentile, which deterministically retains the inputs with the highest norms (note that in percentile the points not weighted). We three tests, varying the distribution of weights. In the first and second tests (Figure (a) and (b)) the weights were drawn from the Gaussian and Uniform distri- butions respectively. The total number of neurons
1000. We selected subsets of neurons
8

---

Published as a conference paper at ICLR 2020
Coreset Unioorm Perrentie like
Coresot Uniform
0.8
1.0
Perrzer li+e
8.8
Addive Error
Ncotive
68
Acditve
C4
02
200
-00
50C
502
1000
200
400
500
902
1000
100
100
200
300
Coreset Size
Coreset Size
Coresel Size
(a)
(b)
(c)
Figure 2: Approximation error of single neuron on MNIST dataset across different coreset sizes. The weights of the points in (a) drawn from the Gaussian distribution, in (b) from the Uniform distribution and in (c) we used the trained weights from LeNer-300-100. Our coreset, computed by Algorithm and Corollary 8, outperforms other reduction methods.
of increasing sizes from to 1000 with a step 50. the third test (Figure 2, (c)) we used the trained weights from the first layer of Lenet-300- 100000000000000 including 300 neurons. We varied the core- set size from 50 to 300 with a step 50. To evaluate the approximation error, we used images from MNIST test set queries. Each point in the plot was computed by 1) running the full network and the compressed network (with corresponding compression level) on each image x in the test set, 2) computing additive approximation error
Epep w(p)o(p"z) 2) Epec u(p) 2)) 3) averaging the resulting error over the test set. In all three tests, our coresets outperformed the tested methods across all coreset sizes.
17.5
Uniform
CoreNet
Average Additive Error
15.0
SVD
CoreNet
L1
Our Mathod
1.25
Average Additve
L
CoreNel
7.5
0.75
5.0
Our Merhhd
0.50
2.5
0.25
0.0
10
15
15 20
25
Percantage of Non-zero Parameters Ratained
Percenlage Non-zero Parametors Relained
(a)
(b)
Figure 3: Average accuracy various algorithms on LeNet-200-105 on MNIST dataset across different sparsity rates. Plot (a) shows the results of all tested methods. Plot (b) focuses the three top methods. Our method, which constructs neural coresets by applying the Algorithm 2 and Corollary in a layer-by-layer fashion, outperforms other bresset-based algorithms.
4.3 COMPARISON WITH OTHER METHODS.
We compare the average approximation еrror vs. compression rates of our neural pruning coreset with several other well-known algorithms (listed above). We run these tests LeNet-200-109 chitecture, trained and tested on MNIST, and we measure the corresponding average approximation error as defined (Baykal et al., 2018):
Σ [10g(z) de (x)
error
Ptest sEPiest
where (g(x) and (1) the outputs of the approximated and the original networks respectively.

---

Published as a conference paper at ICLR 2020
The results summarized in Figure 3. As expected, all algorithms perform better with lower compression, but our algorithm outperforms the other methods, especially for high compression rates.
4.4 ABLATION ANALYSIS
The proposed compression framework includes for every layer, a selection of neurons using Al- gorithm 2, followed by fine-tuning. We performed the following ablation analysis evaluate the contribution of different parts of our framework on LeNet-300-1 trained on MNIST. First, we removed the fine-tuning, to test the improvement due to Algorithm over the uniform sampling. Figure 4, (a) shows the classification accuracy without fine-tuning as function of the compression rate. Figure 4, (b) shows that fine- one-tuning improves both methods, but the advantage of the coreset is still apparent across almost all compression rates and it increases at the higher compression rates. Note that the model selected by the coreset can be fine-tuned to 98% classification accuracy for any compression rate, while the model chosen uniformly cannot maintain the same accuracy for high compression rates.
These results demonstrate that coreset algorithm provides better selection of neurons compared to uniform sampling. Moreover, requires significantly less fine-tuning: fine-tuning until conver- gence of the uniform sampling took close to 2 epochs, while fine-tuning of method required about half of that time.
Refore Fino-Tuning
After Finn- Finn-Tuning
80
97.5
87.0
Accurazy (%)
96.5
60
88.5
60
Corcsat
94.5
Coresel
Uniform (u=w)
94.0
Unifarm (u-w)
50
60
70
80
40
50
Compression essions Rale (%)
Compression Rate (%)
(a)
(b)
Figure 4: Average accuracy over 5 runs of the proposed framework and the uniform baseline LeNet-300-100 on MNIST dataset across different compression rates. Plot (a) shows the results before fine-tuning, plot (b)-after fine-tuning. The fine-tuning done until convergence. Fine- tuning of the uniform sampling almost doubles in time compared to the fine-tuning of the coreset.
5 CONCLUSION
We proposed the first neural pruning algorithm with provable trade-offs between the compression rate and the approximation enror for any future test sample. We base compression algorithm on the coreset framework and construct coresets for most common activation functions. Our tests on ReLU networks show high compression rates with no accuracy loss, and our theory guarantees the worst case accuracy vs. compression trade-off for any future test sample, even an adversarial one. this paper we focused on pruning neurons. future work, we plan to extend the proposed framework to pruning filers in CNNs, to composition of layers, and to other architectures.
ACKNOWLEDGMENTS
We thank Rafi Dalla- Torre, Matan Weksler and Benjamin Lastmann from Samsung Research Israel for the fruitful debates and their technical support.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Dimitris Achlioptas, Zohar Karnin, and Edo Liberty. Matrix entry-wise sampling: Simple is best, 2013.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In ICML, pp. 242-252, 2019.
Jose M. Alvarez and Mathieu Salzmann. Compression-awee aware training of deep networks. In Advances in Neural Information Processing Systems 30, pp. 856-867, 2017.
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundaaiooss cambridge university press, 2009.
Cenk Baykal, Lucas Liebenwein, Igor Gilitschenski, Dan Feldman, and Daniela Rus. Data- dependent coresets for compressing neural networks with applications to generalization bounds. CoRR, abs/ 800008804. 2018.
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/1612.008833 2016. URL http://://axxi wrw. wtt.//ggg//bb//o/////../eeeeea/t 00889.
Emily L Denton, Wojeiech Zaremba, Joan Bruna. Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in neural informa- fion processing systems, pp. 1269-1277, 2014.
Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. In Advances in Neural Information Processing Systems, pp. 4857-4867, 2017.
Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via matrix- valued bernstein inequality. Information Processing Letters, 111(8):385-388 2011.
Abhimanyu Dubey, Moitreya Chatterjee, and Narendra Ahuja. Coreset-based neural network com- pression. ECCV, pp. 469-486, 2018
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In STOC, pp. 569-578, 2011.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. CoRR, abs/1902.09574, 2019.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems 28, pp. 1135- 1143, 2015.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. In ICLR, 2016.
Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural net- works. In ICCV 2017, Venice, Italy, October 22-29, 2017, pp. 1398-1406, 2017.
Hengyuan Hu, Rui Peng, Yu-Wing Tai, and Chi- Chi-Keung Tang. Network trimming: A data-driven neuron pruning approach towards efficient deep architectures. CoRR, abs/1607.032561 2016.
Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew G. Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-arithmeticoonly inference. In CVPR, pp. 2704-2713, 2018
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009. URL https: //www cs. toronto. weteiee.dduukiiiieee
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
11

---

Published as a conference paper at ICLR 2020
Abhisek Kundu and Petros Drineas. A note on randomized element- wise matrix sparsification. CoRR, abs/1404.0320, 2014.
Michael Langberg and Leonard Schulman. Universal epsilon-approximmtors for integrals. In SODA, pp- 518-69877 2010.
Vadim Lebedev and Victor Lempitsky. Fast convnets using group-wise brain damage. In CVPR, pp- 2554-2564, 2016.
Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pp. 598-605, 1990.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2778-2324, 1998.
Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. Pruning filters for effi- cient convnets. In ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learn- ing efficient convolutional networks through network slimming. In ICCV 2017, Venice, Italy, October 22-29, 2017, pp. 2755-2763, 2017.
Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from a network via relevance assessment. In Advances in neural information processing systems, pp. 107-115, 1989.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of over-parametrization in generalization of neural networks. CoRR, abs/1805.12076 2018
Adam Paszke, Sam Gross, Soumith Chintala, and Gregory Chanan, Pytorch: Tensors and dynamic neural networks in python with strong gpu acceleration. PyTorch: Tensors and dynamic neural networks Python with strong GPU acceleration, 6, 2017.
Jeff M Phillips. Coresets and sketches. arXiv preprint arXiv:1601.0066 2016.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recogni- tion. CORR, abs/1409, 1556, 2014.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15()):1929-1958 2014.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. ICLR, 2014.
Elad Tolochinsky and Dan Feldman. Coresets for monotonic functions with applications to deep learning. CoRR, abs/1 /0//1070277 2018.
Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad Morariu, Xintong Han, Mingfei Gao, Ching- Yung Lin, and Larry S. Davis. NISP: pruning networks using neuron importance score propagation. In CVPR 2018, pp. 9194 9203, 2018.
Zhuangwei Zhuang, Mingkui Tan, Bohan Zhuang, Jing Liu, Yong Guo, Qingyao Wu, Junzhou Huang, and Jinhui Zhu. Discrinination-awaar channel pruning for deep neural networks. In Advances in Neural Information Processing Systems 31, pp. 875-886, 2018.
12

---

Published as a conference paper at ICLR 2020
Figure 5: (left) Any point on a circle can be separated from the other points via line. (right) The same holds for circle which the intersection of a d-dimensional sphere and a hyperplane; see Theorem 6.
A APPENDIX
A.1 PROOF OF THEOREM 6
Consider the points (0) whose norm is and last coordinate is a/2. This is a (d 1)- dimensional sphere S that is centered at (0..... ... 0, a/2). For every point on this sphere there is hyperplane that passes through the origin and separates p from the rest of the points in S. Formally, there is an arbitrarily short vector Tp (which orthogonal to this hyperplane) such that xf > 0, but 2
T q < 0 for every S {p}: see Fig. 5. By the definition of Φ, we also have (x T p) > 0,
but (5 q) 0 for every q S (p).
Let P be arbitrary set of points in S, and C P. Hence exists point P PA C. By the previous paragraph,
Σ SEP
o(1 Σ
Eu(1)((xfg)
= -1(0 - -0 =
SEC
Σ
25 Σ (xn
PEP
Therefore C' does not satisfy equation in Theorem 6.
A.2 PROOF OF THEOREM 7
We want apply Algorithm 1, and this end need to prove bound that is independent of on the supremum s, the total supremum f, and the VC-dimension of the query space.
Bound on f(p, x). Put p E P and æ E B3( Hence,
f(p, 2(p x) s ((())|
(2)
(3)
s ((aB))
(4)
where equation holds by the Cauchy-Schwarz inequality and since & non-decreasing, equation holds since (O), and equation 4 holds since p (0).
Bound on the total sup t. Using our bound on fp,,
Σ s(p) = Σ (<pp)((1p))) < ((a.3) Σ w(p),
PEP
PEP
PEP
where the last inequality is by equation 4.
Bound on the VC-dimension the query space (P, w. (,()) f) is O(d) as proved e.g. in An-
thony & Bartlett (2009).
13

---

Published as a conference paper at ICLR 2020
Putting all together. By applying Theorem with X BB((), obtain that, with probability at least 1 6,
Ye E BB(0)=
Σ w())((p,x) Σ (ug)s((,.))
Se.
PEP
SEC
Assume that the last equality indeed holds. Hence,
Vx E BB(0):
Σ (p))(pp'x)
Σ u(1))(a"x)) Se.
PEP
DEC
A.3 PROOF OF COROLLARY
We assume that é is non-decreasing function. Otherwise, apply the proof below for the non- decreasing function o* = -Ø and corresponding weight w" (p) -w(p) for every E P. The correctness follows since w(p)o(p" 2) w" (p) (p" x) for every p P P.
Indeed, put (0()), and e non-decreasing. Hence.
Σ w(p)((p'a) Σ u(p))(pTx)
(5)
PEP
PEC
Σ
x(p)
Σ
u(p)((Tx)) +
Σ
w(p)
Σ
u(p)((T=') x)
PEP
DEC
PEP
PEC
(mpp)((p x)20
"(p)((p' a]20
(w(p)d(p x)<00
x)<0
"(p)o(p " <)<0
Σ PEP
w(p)olpTx)
Σ PEC
u(p)dlpTx)
Σ PEP w(p)d(p x)<0
lu(p)0(p x))
Σ
Iu(p)((y x)]
PEC
w(p)d(pp =)))) 2)20
u(p)o(p' #)20
u(p)o(p <)<0 (7)
Equation 6 is obtained by separating each sum into points with positive and negative weights and applying Cauchy-Sehwarz inequality. Next, we bound points with positive and negative weights separately using Theorem
A.4 CORESET FOR DIFFERENT ACTIVATION FUNCTIONS
Activation Function
Definition
ReLU
max(x, 0)
I+e-r
0 for
binary
1 for 2 In e²)
soft-clipping
1 log
142a
Gaussian
Table 2: Examples of activation functions & for which we can construct coreset of size O (0)) that approximates [r| Epep o(pTz) x) with e-additive error.
14


Reviews:
[{"review_id": "rJlj2ZzVcH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a data-independent way for pruning neutrons in deep neural networks with a provable trade-off between its compression rate and the approximation error. The output of a layer of neurons is approximated by a corset of neurons in its preceding layer. \n\nThe pruning of neurons based on the coresets is shown to be effective when compared with other methods. The authors have validated it on two convolutional network architectures.  \n\nThe paper starts from defining the coresets and introducing the VC dimension, and extends the theorem to more generalized cases. \n\nThe coreset seems to require the activation function to be non-negative, which will possibly limit the scope of application of the proposed theory. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SygftbOCKr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposed a model compressing method based on coreset framework. The goal of the paper is to reduce the number of neurons. The basic idea is sampling the neurons on each layer with probability equal to the neuron's max share among all the outputs to the next layer, and updating the weights associated with the remained neurons. Another main contribution is the authors provided theoretical analysis to guarantee the accuracy vs compression trade-off for all possible inputs.\nPros:\n\nThe proposed method is easy to understand and seems to make sense.\nThe theoretical analysis seems strong.\nThe experiment results on two datasets show the proposed method achieved high compression rate and improvement of accuracy.\n\n\nCons:\n\nDespite the theoretical guarantee, it is not as clear on the value of the proposed method in real world. I would be better to test on more datasets and networks to verify the effectiveness of the proposed compressing method, as it claimed to be data-independent.\n\n\nAlthough the method achieved very good experiment results, its contribution to the high accuracy is unclear, since the networks were fine-tuned after the compression. So how do we exactly evaluate the accuracy vs compression trade-off when there is no such trade-off shown in the experiments?\n\n\nQuestions and suggestions:\n\n\nIn the Fig 2, it seems that the performances of the proposed method and the percentile-based method should be close to each other, and the uniform sampling method should be worse than them. However the results are opposite. If it was not incorrect labeling in the figure, it would be good to add some analyses about this result.\n\nTo solve the second point in \"Cons\", is it possible to show the accuracy of the compressed model without fine-tune? Or still fine-tune the model but simply set u(q) = w(q) in the line 8 algorithm 1?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgB97XXqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "------ after reading authors' response ------\nThanks for the complete response and revision. The new Fig 4 is very nice, and this helps address my concerns. I'm more favorable of the paper now, changing from \"Weak Accept\" to \"Accept\".\n\nNote a small typo in the displayed equation just above Fig 4: the sum is over $P_{test}$ but it's written $P_{t}est$ (and also using \\text makes it look nicer, $P_{\\text{test}}$)\n\n------- original review -----\nThe paper proposes a neuron pruning technique that can compress an existing pre-trained neural net (though the experiments actually do additional unspecified \"fine-tuning\" training). It is motivated by the need to compress neural nets so they work on embedded devices (smart phones, etc.), and it is in contrast to most other techniques that prune at training, or prune after-training but prune weights not nodes. They argue convincingly that pruning weights is awkward, as one has to work with sparse matrices which are only actually effective for extreme sparsity levels. They also claim another big benefit is that theirs is the first with with (1) provable guarantees, and (2) is data-independent.\n\nI have a some criticism of the paper, but before I get lost in the details, let me say that I like the overall paper. I think it's a clever idea, it's a useful topic, the authors show very good understanding of the coreset literature, and it has some nice theory.  The paper is also well-written and easy to understand, and the appendix is short enough that I actually read it.\n\nHowever, I have at least two major comments:\n\n\n(1) The theorems are nice, but with the exception of Thm 6 (which I like), they are simple applications of existing results. My main issue is that you have not provided an end-to-end bound. There are two things lacking:\n\n(1a) Lack of dealing with several layers, e.g., composing your approximation error. With an additive error instead of a relative error, does composition cause a major problem? Seems like this could be an easy theorem.\n\n(1b) Lack of a clear final statement bounding the overall error. This is somewhat trivial (if you have a single pruned layer), but it makes the assumptions more clear. In particular, you assume the input x has norm bounded by beta. In this sense, you have not provided a \"data-independent\" guarantee.  Since you do not have a relative error bound, the norm of x is important.  Yet this also exposes something that really confuses me: for the ReLU activation, with non-negative inputs, this is positive homogeneous, i.e., phi( beta ||p|| ) = beta phi( ||p|| ). If you look at step 2 in Algo 2, you see that the choice of beta does not affect the probabilities (if phi is ReLU or anything else with this property). Thus we can choose beta arbitrarily... and thus you have a fixed additive bound, for an arbitrarily large input, which seems impossible!\n\n(2) Experiments were very promising, but I'm not convinced about the baselines.\n\n(2a) The fine-tuning after pruning wasn't described so I don't know how much effect it had. It makes sense to do this, but it means that it is less clear if your results were due to your theorem.  Please show results with and without the fine-tuning, and describe the fine-tuning (how many epochs of training?)\n\n(2b) You do some abstract experiments with random weights, to test your theorem, which is a nice somewhat direct test of your results (I assume here you are not fine-tuning, as it doesn't make sense, right?). Also in the abstract setup, you could test this as a function of depth, since I'm worried that your error guarantees get worse as a function of depth. The experimental setup was vague: what are the inputs x (from a ball, or sphere? uniform?), was this averaged over many runs? What was this network (you change size when you go to the LeNet-300-100), especially, what was the 100% number of samples (1000?)?.\n\n(2c) For table 3, taking the LeNet for example, you have 90% compression and improved error. This is nice, but to really convince me, in addition to adding the results without the fine-tuning, I'd like to see what you get with uniform pruning (say, with 85% compression) with and without fine-tuning. I don't have a good \"baseline\" expectation here, so while your improved error with 90% compression seems like a fantastic result, I suspect that one might get similar results (with say 85% compression) with trivial subsampling.\n\n\nSome minor comments: \n\n-- abstract, \"guarantees the accuracy of the function\" and \"... on MNIST while improving the accuracy.\"  These are 2 very different meaning of \"accuracy\", so please be more precise, e.g., a per-layer approximation error vs classification error on testing data.\n\n-- First paragraph of intro, saying networks are limited to HPC environments is hyperbole. These networks might need to be trained in an HPC environment, but most can be deployed on laptops (not an HPC environment). A bigger issue is deploying them on a smartphone.  Adding some quantitative numbers would strengthen your case (e.g., size of typical neural nets, and size of RAM in a smartphone).  Note that training requires much more memory due to memory explosion in backpropagation, but this does not effect runtime/deployment.\n\n-- middle of page 2, \"is very fast, ...\" the comma should be a semicolon to make it grammatically correct.  Page 3, near bottom, \"corests\" is a typo.\n\n-- personally I dislike things like Table 1, as they feel too much like boasting. You've chosen the columns carefully so it doesn't feel that meaningful, and you've already stated these things in the text. But it's not my paper.\n\n-- def 4 is very hard to parse. Are these subsets or strict subsets?\n\n-- Notation B_alpha could be explained; I'm used to seeing B_alpha(0), and you can always just write \\forall x with ||x||<= alpha to make it super clear.\n\n-- Your theorems require phi to be non-decreasing, but intuitively you can clearly handle non-increasing, since the set of inputs x \\in B_beta is invariant to sign changes. More generally, you could assume the existence of some 1D function psi(t) such that phi( t ) <= psi( |t| ). I don't know if there are many more common activation functions, but this could give a wider class.  The change to the proofs is trivial, since you just replace psi( |t| ) for phi( alpha beta).\n\n-- If Corollary 9 \"follows directly from Theorem 5\", why didn't Thm 7 and Corollary 8 also follow directly? You mean, it follows, but using the same simple bounding tricks from the appendix as used for Thm 7 and Corollary 8, right?\n\n-- Fig 3 shows very nice results\n\n-- A.1 Proof of Thm 6, you could use \\subsetneq (with amssymb package) to be more clear that it is a strict subset, since I find \\subset vague since different authors have different conventions.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The rebuttal period influenced R1 to raise their rating of the paper.
The most negative reviewer did not respond to the author response.
This work proposes an interesting approach that will be of interest to the community.
The AC recommends acceptance.
Decision: Accept (Poster)