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. Neural networks today are the most popular and effective instrument of machine learning with numerous applications in different domains. Since Krizhevsky et al. (2012) used a model with 60M parameters to win the ImageNet competition in 2012, network architectures have been growing wider and deeper. The vast overparametrization of neural networks offers better convergence (AllenZhu et al., 2019) and better generalization (Neyshabur et al., 2018) . The downside of the overparametrization 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 a trained network could be reduced to smaller sizes without much accuracy loss. Following this observation, many approaches to compress existing models have been proposed (see Gale et al. (2019) for a recent review on network sparsification, and Mozer & Smolensky (1989) ; Srivastava et al. (2014) ; Yu et al. (2018) ; He et al. (2017) for neural pruning). Although a variety of model compression heuristics have been successfully applied to different neural network models, such as Jacob et al. (2018) ; Han et 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 potentially be a glaring problem depending on the application. Moreover, data-dependent methods for model compression (e.g., Mozer & Smolensky (1989) ; Srivastava et al. (2014) ; Hu et al. (2016) ; Yu et al. (2018) ; Baykal et al. (2018) ) rely on the statistics presented in a 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 tradeoff 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 a good provable approximation of the original set with respect to a given function. Our main idea is to treat neurons of a neural network as inputs in a coreset framework. Specifically, we reduce the number of neurons in layer i by constructing a coreset of neurons in this layer that provably approximates the output of neurons in layer i + 1 and discarding the rest. The coreset algorithm provides us with the choice of neurons in layer i and with the new weights connecting these neurons to layer i + 1. The coreset algorithm is applied layer-wise from the bottom to the top of the network. The size of the coreset, and consequently the number of remaining neurons in layer i, is provably related to the approximation error of the output for every neuron in layer i + 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 neurons. 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 computational savings. Our empirical results on LeNet-300-100 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-based coresets by improving compression without sacrificing 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. Our Contributions: We propose an efficient, data-independent neural pruning algorithm with a 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 1. 2 RELATED WORK 2.1 CORESETS Our compression algorithm is 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 k-means, SVD, regression, low-rank approximation, PageRank, convex hull, and SVM; see details in Phillips (2016) . Many of the non-deterministic coreset based 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 a measure of their importance. The sampled elements are usually reweighted afterwards. We proposed the first neural pruning algorithm with provable trade-offs between the compression rate and the approximation error for any future test sample. We base our 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. In this paper we focused on pruning neurons. In future work, we plan to extend the proposed framework to pruning filers in CNNs, to composition of layers, and to other architectures. Putting all together. By applying Theorem 1 with X = B β (0), we obtain that, with probability at least 1 − δ, ∀x ∈ B β (0) : Assume that the last equality indeed holds. Hence, ∀x ∈ B β (0) : A.3 PROOF OF COROLLARY 8 We assume that φ is a non-decreasing function. Otherwise, we apply the proof below for the nondecreasing function φ * = −φ and corresponding weight w * (p) = −w(p) for every p ∈ P . The correctness follows since w(p)φ(p T x) = w * (p)φ * (p T x) for every p ∈ P . Indeed, put x ∈ B β (0), and φ non-decreasing. Hence, Equation 6 is obtained by separating each sum into points with positive and negative weights and applying Cauchy-Schwarz inequality. Next, we bound points with positive and negative weights separately using Theorem 7.
We propose an efficient, provable and data independent method for network compression via neural pruning using coresets of neurons -- a novel construction proposed in this paper.
{"src": "scitldr-AIC_train", "paper_id": "H1gmHaEKwB"}