More Side Information, Better Pruning: Shared-Label Classification as a Case Study
Authors: Omer Leibovitch
Nir Ailon
Venue:  (2021)
Keywords: Pruning
Compression
CNN
LSTM
Image classification

Abstract: Pruning of neural networks, also known as compression or sparsification, is the task of converting a given network, which may be too expensive to use (in prediction) on low resource platforms, with another 'lean' network which performs almost as well as the original one, while using considerably fewer resources.  By turning the compression ratio knob, the practitioner can trade off the information gain versus the necessary computational resources, where information gain is a measure of reduction of uncertainty in the prediction.

In certain cases, however, the practitioner may readily possess some information on the prediction from other sources.  The main question we study here is, whether it is possible to take advantage of the additional side information, in order to further reduce the computational resources, in tandem with the pruning process?

Motivated by a real-world application, we distill the following elegantly stated problem.  We are given a multi-class prediction problem, combined with a (possibly pre-trained) network architecture for solving it on a given instance distribution, and also a method for pruning the network to allow trading off prediction speed with accuracy.  We assume the network and the pruning methods are state-of-the-art, and it is not our goal here to improve them.  However, instead of being asked to predict a single drawn instance $x$, we are being asked to predict the label of an $n$-tuple of instances $(x_1,\dots x_n)$, with the additional side information of all tuple instances share the same label.  The shared label distribution is identical to the distribution on which the network was trained.

One trivial way to do this is by obtaining individual raw predictions for each of the $n$ instances (separately), using our given network, pruned for a desired accuracy, then taking the average to obtain a single more accurate prediction. This is simple to implement but intuitively sub-optimal, because the $n$ independent instantiations of the network do not share any information, and would probably waste resources on overlapping computation.

We propose various methods for performing this task, and compare them using extensive experiments on public benchmark data sets for image classification. Our comparison is based on measures of relative information (RI) and $n$-accuracy, which we define. Interestingly, we empirically find that I) sharing information between the $n$ independently computed hidden representations of $x_1,..,x_n$, using an LSTM based gadget, performs best, among all methods we experiment with, ii) for all methods studied, we exhibit a sweet spot phenomenon, which sheds light on the compression-information trade-off and may assist a practitioner to choose the desired compression ratio.

Under review as a conference paper at ICLR 2021
MORE SIDE INFORMATION, BETTER PRUNING: SHARED-LABEL CLASSIFICATION AS A CASE STUDY
Anonymous authors
Paper under double-blind review
ABSTRACT
Pruning of neural networks, also known as compression or sparsification, is the task of converting a given network, which may be too expensive to use (in prediction) on low resource platforms, with another 'lean' network which performs almost well as the original one, while using considerably fewer resources. By turning the compression ratio knob, the practitioner the necessary computational resources, where information gain is a measure of reduction of uncertainty in the prediction.
trade off the information gain versus
In certain cases, however, the practitioner may readily possess some information on the prediction from other sources. The main question we study here is, whether it is possible to take advantage of the additional side information, in order to further reduce the computational resources, in tandem with the pruning process?
Motivated by real-world application, we distill the following elegantly stated problem. We are given a multi-class prediction problem, combined with a (possibly pre-trained) network architecture for solving it on a given instance distribution, and also method for pruning the network to allow trading off prediction speed with accuracy. We assume the network and the pruning methods are state-of-the of-thhe-rr, and it not our goal here improve them. However, instead of being asked to predict a single drawn instance x, we are being asked to predict the label of an n-tuple of instances (Z1.... ). with the additional side information of all tuple instances share the same label. The shared label distribution is identical to the distribution on which the network was trained.
One trivial way to do this is by obtaining individual raw predictions for each of the n instances (separately), using our given network, pruned for desired accuracy, then taking the average to obtain single more accurate prediction. This is simple to implement but intuitively sub-optimal, because the independent instantiations of the network do not share any information, and would probably waste resources on overlapping computation.
We propose various methods for performing this task, and compare them using extensive experiments on public benchmark data sets for image classification. Our comparison is based on measures of relative information (RI) and ra-accuracy, which we define. Interestingly, we empirically find that i) sharing information between the n independently computed hidden representations of x1, Zn, using an LSTM based gadget, performs best, among all methods we experiment with, ii) for all methods studied, we exhibit sweet spot phenomenon, which sheds light on the compression-inforaatii trade-off and may assist practitioner to choose the desired compression ratio.
INTRODUCTION
Pruning Neural networks, the task of compressing a network by removing parameters, has been an important subject both for practical deployment and theoretical research. Some pruning algorithms have focused on manipulating pre-trained models, (Mozer & Smolensky 1989 LeCun et al.. 1990;
Reed 1993; Han al. 2015)) while recent work have identified that there exist sparse subnetwork (also called winning tickets) in randomly-initialin
neural networks that, when trained in isolation,
can match and often even surpass the test accuracy of the original network (Frankle & Carbin 2019

---

Under review as a conference paper at ICLR 2021
Frankle et al. 2020). There is vast literature network pruning, and we refer the reader to Blalock et al. (2020); : Sze et al. (2017); Reed (1993) for an excellent survey. In this work, we adopt the pruning methods of Tanaka et al. (2020); Lee et al. (2019); Wang et al. (020); Han et al. (2015) which have been influential in our experiments.
More crucially, most literature on pruning has been focused designing machine that converts a fixed deep learning solution to a prediction problem, to a more efficient version thereof. The pruning machine has a compression knob which trades off the level of pruning with accuracy of the prediction. The more resources we are willing to expend in prediction (measured here using floating peating--oonttiooo operations (FLOPs)), the more information we can obtain, where information here is measured as prediction accuracy, or as reduction of uncertainty (defined below).
We now ask what happens when we want to prune a network, but also possess information on the prediction coming from another source. Intuitively, given some form of additional side information, we should be able to prune our network with a higher compression ratio to reach the same level of accuracy for the prediction task, compared with scenario with no additional side information. But how can we take the side information into account when pruning?
1.1 MOTIVATION
This question was motivated by actual real-life scenario. We describe the scenario in detail, although the actual problem we thoroughly study in what follows is much simpler.
Imagine database retrieval system with static space of objects X. Given a query object q. the goal is to return an object x from X' that maximizes a ground-truth retrieval value function f, (z). We have access to a function (x) expressed as a deep network, which approximates Sy. and was trained using samples thereof. The function f,, is very expensive to compute. (Note that keep q fixed here, as part of the definition of (-). although in an actual setting both q and x would be input to a bivariate retrieval function f.) Computing (ar) for all x E X' is infeasible. One way to circumvent this is by computing a less accurate, but efficient function (+()) defined by the network resulting in a pruning of the network defining Fq. Then compute f.(-) on all x E X' to obtain a shortlist of candidates X', and then compute f1( on x X" only. This idea can also be bootstrapped,
2 2(4) 2(5) and increasingly shorter shortlist. using rougher, more aggresively pruned estimates fqr However, an important point is ignored in this approach: The space X' is structured, and we expect there to be prior connections between its elements. This is the side information. Such connections can be encoded, for example, as a similarity graph over X' where it is expected that fy (211 ) is close to fg (222 whenever there is edge between 21, 22. There is much work on deep networks over graphs (Zhou et al. 2018 8 Kipt& & Welling, 2017 Wu et al. 2020). But how can the extra information, encoded graph, be used in conjunction with the pruning process?
Let us simplify the information retrieval scenario. First, assume that we are in a classification and not in a regression scenario, so that f, (x) can take finite set of discrete values, and fx( returns a vector of logits, one coordinate per class. Second, assume the side information of X' into cliques, or clusters XI...Yy where on each clique the value of f.(.) is fixed, and written as i 1..k. Now the problem becomes that of estimating the (x(X)) 's using n random samples Fa1....4 E X2 = 1..k:
X' is a partitioning
Fixing the cluster X; one obvious thing to do in order to estimate (X,) is to take an average of the logit vectors (f where f, is some fixed (possibly pruned) network, and use the argmaz coordinate as prediction. Assuming each pruned network f, outputs prediction vector with a certain level of uncertainty, the averaged vector should have lower uncertainty, and this can be quantified using simple probabilistic arguments. This will henceforth be called the baseline method. Intuitively the baseline method, though easy to do using out-of-the-boo pruning libraries, cannot possibly be optimal given the side information of same label across X, Indeed, the baseline method feeds all the examples Zi independently through separate instantiations of fg. and nothing
Continuing the retrieval story. the practitioner would now find the X; that maximizes for and then further focus the search in that cluster.
2

---

Under review as a conference paper at ICLR 2021
prevents the different instantiations to learn overlapping pieces of information. Hence it makes sense to somehow interconnect these networks as a neeta-network, and possibly do the pruning on the meta-network. In this work, experiment with several methods for performing this task, and compare our results with the baseline.
1.2 THE SHARED- LABEL. PREDICTION PROBLEM
We depart from the original motivating information retrieval scenario, and henceforth consider a simpler, toy problem which we call the shared-label prediction problem. We given underlying space of instances X' and an unknown ground truth labelling function ʃ X' + y/ for some discrete set set of labels. The goal is to train a classifier that, given a random n-tuple of instances 21... E X sharing the same unknown label (so that f(z1) = = f(rm) ) = y). outputs a prediction of This is the shared prediction problem.
Our work is empirical, and the goal is to develop general methods for the shared prediction problem, given a base network, designed for the standard shon-shared) prediction problem, and base pruning method, we ask: How do we reuse and rewire these readily available tools to effectively solve the hhared-label prediction problem on tuples of n-instances?
OUR CONTRIBUTION
Below in Section 2.1 we present four methods. Each method uses a baseline CNN model, together with a pruning method with a compression ratio knob p. and creates a meta-network that parameterized by the information size n and by p. designed to solve the shared classification problem. To measure our success, we will both use a measure of accuracy as well as a measure of relative information which we define below. We will compute these measures extensively over grid of possible pairs (n, p). for each method. Visualization the results highlights an interesting invariant that is worth studying.
Intuitively, the measure of relative information tells us how efficiently each method uses its computa- tional resource, without wasting time computing the same pieces of information over and over on the n-tuple of instances. Therefore, it allows us to obtain quantitative comparison between the methods. To define the measure, we first recall some information theory.
Given a random variable Y over a discrete space, the Shannon entropy. or uncertainty of Y is H[Y] - - Pr[Y y] log Pr(Y y). where the sum ranges over possible values of Y. In our case, we will use HY) to measure the uncertainty in the label of a randomly drawn instance, which also the uncertainty the label of randomly drawn n-tuple the shared label setting.
Given random variable Y (an estimate of Y), the information gain measures the difference between the entropy of Y and the expectation with respect to Y of (Y|))). More precisely, IG(Y; H(Y) Eg | E, Pr[Y = log Pr((Y =>18]] Note that information gain is symmetrical, that is IG(ÝYY) IG(Y; V). Therefore it is also called mutual information and denoted I(Y; Y)) In our setting, Y will be an estimator of Y obtained using the output of the network on an n-tuple of instances in the shared label setting, and / I(Y; Y) will measure the expected amount of information we learn about Y using the network output that tuple. For given network, we will be computing IG(Y; Y) empirically in what follows, by taking Y to be the prediction obtained by selecting the argmax coordinate (logit) of the output of a network.
Given method for the shared-label scenario, we define the relative information (RI) to be
IG(Ý;Y) n/p
RI(Y, n,
In words, this is measure of information that the network learns, per computational cost. The denominator n/ p is a reasonable measure computational cost for the methods we study, because for these methods, the amount of computational effort expend for shared label instance 21...
3

---

Under review as a conference paper at ICLR 2021
is proportional to n, and inverse proportional to the compression ratio p. We believe it is also reasonable measure of computational cost for other natural methods.
For all methods we study, fixing the information size a sweet spot phenomenon, or a "compression threshold" in the sense that RI, as a function of p. has global maximum p² If the compression ratio is smaller than p², than compressed regime, where we can still save computational resources without relatively deteriorating the results, or the information, than p², than we are at the over-compressed regime, where we can gain a lot more information, by using a relatively mere amount of computational resources. We believe that better understanding of this phenomenon can shed light on the interaction between different compression ratios, information sizes, and the information gains achieved by the methods (which is equívalent to test performances, as our experiments show). We show that the above is a robust phenomenon that occurs in a variety of settings.
experiments suggest that there exists
the under-
large extent. On the other side, if the compression ratio p bigger
2.1 OUR METHODS
1. Baseline method (Section 4.1 Use a fixed model, with fixed pruning method. For prediction, run the pruned model on the n instances F1-...n, and use the average of the corresponding logit vectors for the shared prediction.
2. Balanced method (Section 4.2) The same the baseline method, except that the training set is organized such that each batch of images consists of k random n-tuples, such that instances of each n-tuple share the same unknown label y. The model is trained using the balanced loss, which is a convex combination of a loss defined for n-tuples, and the standard loss the individual instances.
3. Graph method (Section 4.
Inspired by work on Graph neural networks (GNNs), propose an architecture consisting of n duplicates of a base CNN, with information passage between neurons of the different copies of the CNN. The training set is organized in the same way as in the balanced method.
4. Unified CNN-LSTM method (Section 4.4) We propose a model that combines a truncated version of a base CNN, giving a latent representation of the inputs, and then connecting the n representations to each other, sequentially, using LSTM (Long Short-Term Memory) gadgets. Intuitively, this architecture encoded inside the LSTM, to assist in predicting 2; for i = 2,...n. n. The training set is organized in the same way as in the balanced method.
information learned from instances 21...
In Section 5.]
we validate the above sweet spot phenomenon under a variety of benchmark datasets, architectures, compression ratios and information lengths. We report the results of the baseline method for its simplicity (the same results hold for all other shared-label prediction methods well).
In Section 5.2 we compare the differences between the baseline methods and the balanced method both qualitatively and quantitatively.
we compare all the proposed methods for shared-label prediction across different benchmark data sets for image classification and different evaluation metrics. The proposed unified CNN-LSTM method achieves significantly better performance compared to the other methods.
In Section 5.3
3 RELATED WORK
There is variety of approaches to compressing neural networks, such as neural network pruning
LeCun et al.) 1990 [Se et al.) 2017 Reed 1993] Han et al., 2015] Blalock et al. 2020 Frankle & Carbin, 2019 Frankle al. 2020), training of dynamic sparse networks (Bellec et al. 2018 Mocanu et al. 2018) dimensionality reduction of network parameters
(oozer & Smolensky
1989;
(Jaderberg al.] 2014 Novikov al. 2015), , and many more. Nonetheless, these results do not
mention how the new compressed, efficient network, benefit from additional side information.
Moreover, there is much work on the "double-descemt phenomenon (Belkin al. 2019 Advani & Saxe 2017: Geiger et al.] 2019). In a work by Nakkiran et al.) (2020), it is shown that a variety of modern deep learning tasks exhibit "double-descent", and that it occurs not just as function
4

---

Under review as a conference paper at ICLR 2021
of model size. Therefore, it is interesting question ask whether this also occurs in the case of relative information, and our experimental results validate that this is not the case.
The concept of graph neural network (GNN) first proposed by Scarselli et al. 2009). who extended existing neural networks for processing the data represented graph domains graph papers. The first motivation of GNNs roots in convolutional neural networks (CNNs) (Lecun al. 1998). Recent works on GNNs (Zhou et al. 2018 Kipf & Welling, 2017] Wu et al. 2020) inspired us to extend this idea as one of our methods for the task of shared-label prediction.
Lastly, RNNs are interesting for our purposes because they equip neural networks with memory, and the introduction of gating units such LSTM and GRU (Hochreiter & Schmidhuber, 1997 Cho et al. 2014) has greatly helped in making the learning of these networks manageable. The LSTM based architecture has yielded the most promising results throughout our experiments.
OUR METHODS
In order to describe our four methods in details, we will need to present some standard terminology from the network pruning literature.
Layer-collapse Pruning neural networks is usually done in two steps: The first step scores the parameters of a network according to some metric and the second step eliminates parameters based on their scores. This process can be applied both globally (on the network
whole) and locally (separately on each layer). Recent work (Wang et al. 2020; Lee et al. 2020) You et al. (020) has identified key failure mode, layer-collapse, for the global version. Layer-collapse
when an
algorithm prunes all parameters in a layer, rendering the network disconnected (and untrainable).
Compression ratio (p) Logarithm to the base 10 of the number of parameters in the original network divided by the number of parameters remaining after pruning. In our experiments we use (not necessarily integer) powers of 10 for the compression ratios. For example, compression 2.5 means that the number of parameters in the original network divided by the number of parameters remaining after pruning equals to 102.5
Max compression (Pmaz)- The maximal possible compression ratio for a network that doesn't 't lead to layer-collapse.
We further define an accuracy based evaluation metric for shared-label prediction method, n- accuracy, which highly correlates with information gain, as our experiments show. We denote to be the number of classes in the data set and without loss of generality let the labels be {1,.... f). Moreover, Yi is vector of size & that contains raw, unnormalized scores for each class, predicted by given model.
n-accuracy- the percentage of correctly classified n-tuples. Formally, n-accuracy of a shared-label prediction method is defined to be
T
1
ΣΣx 2=1
X,
T
where X; an indicator for the event that the i'th n-tuppl was classified correctly. In our experiments we take T = e. 100. Namely, we test on 100 random n-tuples from each class and report the average accuracy.
4.1 BASELINE METHOD
In the bascline method, each model is simply trained in a standard fashion for image classification, with a randomly shuffled training set with batch size B and the Cross Entropy Loss defined as:
Cross entropy Loss(ū, class) = ----loo log( exp(ū]class))
[[ccaas) + log( Σ exp (rp(ū[))
Σj exp(ū"))
Finally, the losses are averaged over observations for each batch:
B Cross entropy Loss( class;)
Standard Loss
B
1=1
5

---

Under review as a conference paper at ICLR 2021
where di contains raw, unnormalized scores for each class, predicted by the model for the ith data point in the batch and class; is its corresponding label. For this method, evaluation is done by simply taking an average of the predicted logit vectors Vi...nn. and then taking the argmar the shared label prediction. In this way, we can take advantage of the probability scores in each logit vector.
4.2 BALANCED METHOD
Recall that our task is to classify n different data points that share the same class with their corre- sponding label. Thus, the motivation will be to optimize directly for that purpose. The training set is organized such that each batch of images of size consists n-tuples, such that each n-tuple share the same unknown label (B = k n). For a batch of size B, the average batch prediction is defined to be:
B ΣE
1
Average Batch Prediction(bal.c) =
9k ==1
Furthermore, let batch; be the subset of the current batch that only contains data points corresponding to label (batch, is of size k). Denote y' = Average Batch Prediction(batedt (batch,). Then, the Average Same Label Loss defined to be:
1 Σ j=
Average Same Label Loss(batch)
Cross entropy Loss Loss(j';)
Intuitively, the loss function encourages the model to do well on each n-tuple rather than doing well on each specific data point. As a result, using this loss as is in our experiments, does not lead to a model that generalizes well. Therefore, the Average Same Label Loss, as the first is often used for standard multi-class classification, and the latter may help perform better at the shared-label prediction task. With that in mind, the idea is to X. The balanced loss is defined to be:
offer natural rrf between the Standard Loss and
balance between these two losses using a
Balanced Loss(batch) (1 - A) Average Same Label Loss(batch)
Standard Loss(batch)
Intuitively, the loss function encourages the model to do well on both the n-tuple as whole, and on each specific image (controlled by the hyper-parameter A). When 1, this is equivalent to the I For this method, evaluation is done in
baseline method. Throughout our experiments, we use À 2- the same way as in the baseline method.
4.3
GRAPH METHOD
In the graph method, propose a duplicated convolutional neural network architecture with information passage between the different copies of the CNN. This is inspired by recent work on
Graphical Neural Networks (GNNs) (Zhou al. 2018 Kipf & Welling 2017 Wu et al. 2020). We investigate two kinds of architecture, see Appendix B for further information.
4.4
UNIFIED CNN-LSTM METHOD
4.4.1
ARCHITECTURE
We propose a unified CNN-LSTM architecture, which effectively learns both the embedding of the data points into low-dimensional vectors and the dependency between the embedding of different data points in the same sequence. An illustration of this architecture is shown in Appendix A. The CNN part extracts semantic representations from images, whereas the shared-label dependency between data points in the same sequence in this www-dimessional space is modeled with the long short-term memory (L.TTM) recurrent neurons, which maintain the information of label context in their internal memory states (for more information on LSTM, see Appendix A.2). The LSTM part computes the probability of a shared-label prediction sequentially as an ordered prediction path, where the posteriori probability of the single true label can be computed again at each time step, based on the image embedding at the current time step and the output of the recurrent neuron from the previous time step. The proposed CNN-LSTM model is unified framework combining the advantages of both learning an effective image embedding using a deep CNN, while also taking into account the label sharing.

---

Under review as a conference paper at ICLR 2021
4.4.2 TRAINING
Training with the unified CNN-LSTM method done by using the cross entropy loss on the soft-max normalization of the average of the outputs of the linear layer following the LSTM (see Figure IO). and employing back-pre proppaaaaan through time algorithm. Although is possible to train the model in end-to-end way, our experiments show that it is much more preferable to train the CNN part separately, using the bulanced method (Section 4.2), and truncate the final classification layer to achieve the desired embedding. Although it is possible to fine-tune the convolutional neural network afterward, we keep unchanged in our implementation for simplicity (we noticed that it doesn't make any considerable differences). Both parts of the model are also pruned separately.
When using this method, an important decision is to determine the order of the sequence (as the LSTM part is not symmetric). For further information the different order techniques that we have experimented with and their motivation, please refer to Appendix A.3
5
EXPERIMENTS
In this section we report the results of our experiments based on the ideas presented in Sections 1.2 Full experimental details are in Appendix
and 2
5.1
COMPARISON USING THE BASELINE METHOD
In this section, use the baseline method and Conv model the CIFAR-10 data set (see Appendix Cf more information). We study how variation in the floating-poin operations (FI.Oss) due to altering values of n E {1, 2, 3, 4, 5, 10, 15, 40, 60} and p effect on different evaluation measures. The results are presented in Figures [-7 Similar results for different combinations of models and data sets are presented in Appendix
Figure 4: Information gain and FLOPs comparison. is observed that diflerent compression ratios are optimal terms FLOP%) for different desired information
Figure 1: r--accuracy and FLOPs comparison. It observed that ferent compression ratios opti mal (in terms of FL.OPs) for differ- ent desired n-acouracy.
Figure Log errer FLOPs Figure Relative information comgarison, where the ervee is and n comparison. For each value simply n-accuracy/ / 100 the binary logarithm used.
ohserve specific between the compression ratios. gain.
Figure 5: n-accuracy and information guin comparison for the first 3 compression mtios. We observe that there exists very high corre- lation between two measures our exper- imental setup.
Figure 6: r rccuuuuyy and information gain comparison the last compression ratios. We observe that there exists a very high corre- imental setup.
Figure 7: Relative informatio and compres- sions comparison for different values n. spot in temns of the
We observe pression ratio, for each different value of n.
the measures exper-
5.2 BASELINE AND BALANCED METHODS COMPARISON
In this section, we compare the performances of the baseline method and the balanced method, and report the n-accuracy various data sets, models, and values of n and p. In all cases, it is
7

---

Under review as a conference paper at ICLR 2021
observed that the balanced method (with À x= outperforms the baseline method in the shared-label prediction task for sufficiently large values of n. Nevertheless, is interesting to observe that the baseline method still almost always outperforms the balanced method in the normal classification task (equivalent to shared-label prediction with n = 1). The results are summarized in Table [ Appendix (F) For further discussion the comparison between the two methods, please Appendix
5.3 SHARED-LABEL. PREDICTION METHODS COMPARISON
In this section, we compare the performances of all the shared-label prediction baseline methods discussed above, and report the n-accuracy on various data sets, models, and values of n and In all cases, it is observed that the unified CNN-LSTM with balanced trained CNN highly outperforms all the other methods for every value of E (2, 5, 7, 15, 40). even though it has less remaining parameters, and uses fewer FLOPs. The results for the Conv model and Tiny-Imagent data set in measures of n-aaccuracy and relative information are presented in Figure g and Figure Seeuueerrese respectively. similar figure for the MNIST data set is presented in Appendix E.2 Further results for the higher n-accuracy methods, with different combinations of models and data sets presented in Table 2 in Appendix
90
Brannt
80-
OUS centure dieiree
takeed OS
Relative information
50
20
20
Figure 8: nn-accuracy on Tiny ImageNet various sharod-
Figure Relative information on Tiny ImageNet with various shared-Jabel prediction methods.
label prediction methods.
CONCLUSION AND DISCUSSION
We introduce real-world motivated problem and investigate how to take advantage of additional side information in order to reduce computational efforts. We study simple scenario which we coined as the shared-label prediction problem, and suggest various methods, based on different architectures in deep learning, to perform it. We conduct extensive experiments to improve our understanding of i) the and advantages or disadvantage of each method, and the differences between them, ii) the vast connection between measures of accuracy, information, compression ratio, and FLOPs our settings, and how they interact with each other, and (iii) introduce relative information generalized measure of information that the network learns, per computational cost, which, to the best of our knowledge, has not been previously proposed. We further suggest that it enjoys a sweet spot phenomenon, that leads regime, where in certain scenarios increasing decreasing the compression ratio knob can deteriorate the relative information. Therefore, we also believe our characterization of the sweet spot provides a useful way of thinking for practitioners.
Throughout our research, we have used common pruning algorithms as black box. Is it an interesting future research question ask whether is possible design pruning algorithm (or somehow incorporate an existing one as part of the prediction method) that is better suited for the task of shared-label prediction, namely, one that takes advantage of the side information scenario, in order to gain higher performances.
REFERENCES
Madhu Advani and Andrew Saxe. High-dimensional dynamics of generalization error in neural networks. 10 2017.
8

---

Under review as a conference paper at ICLR 2021
M. Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnine practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, 116:15849 15854, 2019.
Guillaume Bellec, David Kappel, Wolfgang Maass, and Robert Legenstein. Deep rewiring: Training very sparse deep networks. In International Conference on Learning Representations, 2018. URL
https://openreviiet net/ htt.//orrmmmdddddd Fid=BJ__iB__ wNO1C-
net.
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? arXiv, 2020.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1735 1734, Doha, Qatar, October 2014. Association for Computational Linguisties. doi: 10.3115/v1/D144 1179
URL https: /ww. www. aclweb
org/ httaaaaattooooii/aaaa
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
Jonathan Frankle, G Karolina Dziugaite, DM Roy, and M Carbin. Stabilizing the lottery ticket hypothesis. arXiv, 2020.
M. Geiger, S. Spigler, Stéphane d' Ascoli, Levent Sagun, M. Baity-Jesi, G. Biroli, and M. Wyart. The jamming transition as paradigm to understand the loss landscape of deep neural networks. Physical review. E, 100 1-1:012115, 2019.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. pp. 1135-1143, 2015.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 7, 12 2015.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9:1735-80, 12 1997. doi: 10. 1662nec/n... 1997.9.8. 1735.
Max Jaderberg, A. Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. ArXiv, abs/ hts/1405.3866 2014.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11):2278-23) 2324, 1998.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In D. S. Touretzky (ed.), Advances in Neural Information Processing Systems 2, pp. 598-605 Morgan-Kaufina 1990.
URL httthhttpppppeee.e wwps. wttpppcpcpppee///00--- http://ppprr/2500p.immmmml brain damage . pdff
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, Stephen Gould, and Philip H. S. Torr A signal propagation perspective for pruning neural networks at initialization. In International Conference on Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2021
Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H. Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1), 6 2018. ISSN 2041-1723. doi:
Michael Mozer and Paul Smolensky. Skeletonization: technique for trimming the fat from network via relevance assessment. In D. S. Touretzky (ed.), Advances in Neural Information Processing Systems 1, pp. 107-115. Norgan-Kaufmann 1989.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever, Deep double descent: Where bigger models and more data hurt. In International Conference on Learning Representations, 2020. URL httLttttt///pnnntte
net/ forum www.:eeeooo..ddllli.eaeee... Pid-Blg5sAttwr
Alexander Novikov, Dmitrii Podoprikhin, Anton Osokin, and Dmitry P Vetrov. Tensorizing neural networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems 28, pp. 442-450 Curran Associates, Inc., 2015.
URL
pdf
David Page.
How to train your resnet. 2018.
URL https://myrtle..r
how Now-to--e -oo-train--o your- 1aaa----aaahhhrrrreeee
Razvan Pascanu, Tomas Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. 30th International Conference on Machine Learning, ICML 2013, 11 2012.
R. Reed. Pruning algorithms-a survey. IEEE Transactions on Neural Networks, 4(5):740-74) 747440-77,,11 1993.
Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner. and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1),61-80, 2009.
V. Sze, Y. Chen, T. Yang, and J. S. Emer. Efficient processing of deep neural networks: A tutorial and survey. Proceedings of the IEEE, (15(12):2295-2329 2017.
Hidenori Tanaka, Daniel Kunin, Daniel L. K. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv, 2020.
ImageNn. Available at httt::://inny-imagnee....
com
Chaoqi Wang, Guodong Zhang, and Roger Grosse
Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, C. Zhang, and Philip S. Yu. A comprehen- sive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks. In International Conference Learning Representations, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Edwin R. Hancock Richard C. Wilson and William A. P. Smith (eds.). Proceedings of the British Machine Vision Conference (BMVC), pp. 87.1-87.12. BMVA Press, September 2016.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. arXiv, 12 2018.
A UNIFIED CNN-LSTM
A.1 ARCHITECTURE ILUSTRATION
The architecture of the proposed unified CNN-LSTM model for shared-label prediction is presented in Figure 10, The convolutional neural network is employed the image representation, and the recurrent layer captures the information of the previously predicted labels. The outputs of the LSTM are fed through linear classifier to compute the output label probability.
10

---

Under review as a conference paper at ICLR 2021
Linear Layer
Unaot Lawe
Highls spara Cona
Predicted Labe Frobabl by
Higure 10: The unitied CNN-LSTM architecture
A.2 LONG SHORT TERM MEMORY NETWORKS (LSTM)
As mentioned earlier, since the objective is to characterize the high-order label dependency in the same sequence (data points embedding the same sequence share the same label), we employ long short term memory (LSTM) neurons (Hochreiter & Schmidhuber 1997) as our recurrent neurons. This approach has been demonstrated to powerful model of long-term dependency. RNN is class of neural network that maintains internal hidden states to model the dynamic temporal behavior of sequences with arbitrary lengths through directed eyclic connections between its units. It can be considered hidden Markov model extension that employs nonlinear transition function and is capable of modeling long term temporal dependencies. LSTM extends RNN by adding three gates to RNN neuron: forget gate f to control whether to forget the current state; input gate to indicate if it should read the input; an output gate o to control whether to output the state. These gates enable LSTM to learn long-term dependency in sequence, and make it is easier optimize, because these gates help the input signal to effectively propagate through the recurrent hidden states r()) without affecting the output. LSTM also effectively deals with the gradient vanishing/exploding issues that commonly appear during RNN training (Pascanu et al. 2012).
A.3 SEQUENCE ORDER OF THE LSTM
In the experiments of this paper, we tested both random ordering and confidence based ordering the sequence order during training (and inference) determined according the confidence of the corresponding data points by the CNN model. Data points that have higher confidence in the prediction by the CNN model (trained separately with the balanced method) appear earlier than the less confident ones. This corresponds to the intuition that easier data points should be predicted first to help predict more difficult data points (one data points is classified with higher confidence than the other data point if the largest entry in its logit vector is higher than the largest entry in the other data point logit vector). In particular, the first data point in the sequence will not have prediction from earlier time to rely and would like this prediction to be as easy as possible. Otherwise, face a problem if the first predicted label wrong, it is possible that the whole sequence will not be correctly predicted. In our experiments, confidence based ordering usually gained better performances than random ordering, especially for lower values of n. We further attempted to randomly permute the lahel orders in each mini-batch, repeat multiple times, and then taking the average prediction, but this does not have notable effects on the performance and it makes the training harder to converge.
may
B THE GRAPH METHOD
In the graph method, we investigate the following two architectures:
1. Each of the data points in the n-tuple goes through copy of the CNN, and their corresponding embeddings are fed through another classifier. The whole architecture is trained end-to-end using the cross entropy loss.

---

Under review as a conference paper at ICLR 2021
2. Each of the data points in the n-tuple goes through copy of the CNN, but now, information passes between different copies of each neuron. This is similar to the architecture used in GNN's (Graphical Neural Networks).
C EXPERIMENTAL DETAILS
C.I MODELS
We use the following architectures as the model/CNN for each method throughout our experiments.
FC. Standard fully-connected network designed follows for imput r::
I f Flatten[z]] (Flattens a tensor of dimensions C' H X W to vector of size W)
ReL.U(Lnnear(C: H W. 100))
J < ReL.U(Linear(( 100, [00)[z]) (repeat 4 times)
ReLU(LLneerr100, [=))
Conv. Standard CNN. We consider simple 5-layer CNN which based on the "backbone" architecture from Page 2018), designed follows for input x::
f- Conv2d(in channels, out channels 32, kernel size=(3.3), 3), stride=(1, 1). (L, (in channels 1 for MNIST, in channels = for CIFARIO, CIFARI00, Tiny ImageNet)
r ReL.U[z]
Conv2d(in channels 32, out channels = 32, kernel size= 3). stride=(1, 1), (1dding-(111)
x f Flatten(R=LL((:))
<- Linear(in features [xx))
ResNet18. (He et 2015)
WideResNet20. Zagoruyko & Komodakis, 2016)
C.2 OTHER EXPERIMENTAL SETUP
Optimization. We used the Adam optimizer (Kingma Ba 2014), learning rate was set at constant to 10-4 and all other parameters were set to their default Py lorch values.
Data sets. We conducted our experiments on several public benchmark data sets for image classifica- tion:
MNIST (LeCun & Cortes
2010
CIFAR-10 (rrizhevsky
2009
CIFAR-100 (Krizhessky 2009)
Tiny-ImageNer (Tige-lmageNet)
Pruning algorithms. All pruning algorithms considered here use the following two steps: (i) scoring parameters, and (ii) masking parameters globally across the network with the lowest scores. description of how we compute scores used each of the pruning algorithms:
Random: We sampled independently from a standard Gaussian.
Magnitude: We computed the absolute value of the parameters. (Han et al. 2015
SNIP: As done in (Lee
2019
GraSP: As done in (Wang et al. 2020
SynFlow: As done in Tanaka et al. 2020
We report the results using the SynFlow pruning algorithm it achieved the best results for all methods tested. We run the pruning algorithm for 100 iterations before the training phase (our comparisons hold for other pruners well).
12

---

Under review as a conference paper at ICLR 2021
D EXTENDED DISCUSSION ON THE BALANCED METHOD
further observed from our research that it is possible to improve the results of the balanced method. Higher n-aceuracy measures were achieved using the following procedure:
Train model with the baseline method until no further improvement is gained.
Freeze all the layers in the model, except the last few layers.
Retrain the mode with the balanced method until no further improvement gained.
The method achieves even higher n-aceuracy than the baseline method in the shared-labe prediction task for sufficiently large values of n which in turn is better than the baseline method, as reported in Table in Appendix [F]
The intuition behind this method is similar to standard transfer learning: Training the model initially with the baseline method yields a model with better representation of both the lower-level features and the higher-level features of the data. Then, tuning it at the end by retraining the final layers only with balanced training yields a model with more adequate high-level features for shared-label prediction task in one hand, and a better understanding of how use these features to make better decision, based on various data points containing the same label.
Consider the following example when classifying MNIST digits: A standard model in the highly- parametrized regime would learn to detect basic features such as small curved lines the shallow part of the neural network, and at deeper stage of the network it may learn detect features such as circles. When we are at the low-parametrized regime, we have to make a compromise, deteriorating the quality of the high-level features. Using this method may benefit the model by helping it to learn better "low quality" high-level features that may not be "good enough" for normal classification, yet sufficient for the shared-label prediction task.
complex
E ADDITIONAL PLOTS
E.
PLOTS FROM SECTION 5.1
Figures 11 20 describe the results of the comparison done part of the experiments in Section 5.1
The results presented in Figures II were generated using Ride-ResNet20 model on the Tiny- ImageNet data set (n E (1, 2, 5, 7, 10, 15, 40 and the results presented in Figures 16 were generated using ResNet18 model on the CIFAR-100 data set (n 21,2,3. 4, 5, 7, 10, 15, 40, 60)).
100
50
20
107
FLOPs
3071
10a
10
10
FLOPs
Figure Il: n-accuracy and FLOPs comparison. It observed that different compression ratios are optimal (in FLOPs) for different desired n-accuracy.
Figure 12: Log error and FLOPs comparison, where the error simply n--ccuracyy /100 and the binary logarithun used.
E.2 PLOTS FROM SECTION
Figures 22 describe the results of the comparison done part of the experiments in Section 5.3 The results presented figure were generated using a Conv model on the MNIST data set (n (1, 4, 5, 7, 10, 15, 40, 60)).
13

---

Under review as a conference paper at ICLR 2021
75
70-
45
Figure Relative information comparison. each value of n. observe specific order between the compression ratios.
Figure 14: Information gain FLOPs comparison. It ob- served that different compression ratios optimal (in terms FLOPs) for different desired information gain.
90
80
70
60
50
4.5
5.0
5.5
6.0
6.5
7.0
75
Information gain
Figure 15: n n-accuracy and information guin comparison. We observe that there exists very high correlation between the measures our experimental setup.
100
70
COMFTEEIE- 21
10a
10P
FLOPs
107
10"
101h
FLOPs
Figure 16: i accuracy and ELOPs comparison. is observed that different compression are optimal FT.OPs) for different desired n--ecurray.
Figure 17: Log and Fl 11.0Ps comparison, where the emorr simply n-accuracy/ 1000 and the binary logarithm used.
F TABLES
14

---

Under review as a conference paper at ICLR 2021
60
5.
45
40
35
30
Compocaio- 20
10
10'
10"
107
10th
FLOPS
Figure 18: Relative information and comparison. each value n. we observe specific order hetween the compression ratios.
Figure 19: Information guin and FLOPs comparison. It ab served that different compression ratios are optimal (in terms FLOPs) for different desired information gain.
90
80
naccuncy
50
3.0
3.5
5.0 Information gain
6.0
6.5
Figure n-accuracy information gain comparison. ubserve that there exists very bigh correlation between the two experimental setup.
175
Grish
90
150
OW pendaan
Relative Information
125
araenig
naccuuccy
80
70
60
foance anoring
10'
10
Figure r-accuracy MNIST shared-label pre-
Figure information label prediction methods.
diction methods.
15

---

Under review as a conference paper at ICLR 2021
Method
Data
Total ponmettes Compression Remaining
Medel
I
25
40
60
Baseline
71.72
MNIST
119,400
378
PC
Balanced
30.29
78.28
$6.53
89.44
93.33
260,384
147
Cony
Balanced
50.69
94.44
96.78
100
100
Baseline
39.20
260,384
Cony
Balanced
35.15
78.79
85.31
90.06
94.17
Baseline
50.54
91.75
90.40
91.35
91.67
Balanced
35.16
92.25
96.80
99.38
100
Baseline
28.92
45.25
44.00
41.38
40.00
CIFAR-10
11,172002
ResNet-18
Balonced
21.10
50.75
Baseline
18.28
77,00
75.30
75.00)
83.00
CIEAR-10 100
3,286.880
10,395
Cony
Bascline
21.10
59.75
61.50
61.00
62.00
CIFAR-100
1,092,960
2.0
10,930
WideResNat-20
Table n-accuracy on different data sets with various architectures and compressions. In all cases, the balanced method highly outperforms the balanced method (for sufficiently large values of n)).
Mathod
Total parameters Compesssion Remaining pormecter
[+40]
Balanced
260,,544
Conv
Unified CNN-LSTM
69.43
74.61
85.31
with baseline
171,710
Com
trained CNN
MIISTT
432,094
3/75, 3.75
78
LSTM
80.25
92.24 94.10
95.15
97.14
UNN-LSTM
with balanced
171,710
78
LSTM
maiined CNN
432,064
11,172,033
1118
ResNet 18
Unified CNN-LSTM
11,172,002 +
4.0
58.10
73.05
77.96
$1.39
89.60
with beseline
176,730
354 559
ResNet-18-
Unified CNN-L.STM
11,122.032-
4.5, 2.5
354
ReaNer-18
62.06
81.15
65.42
94.24
98.40
with balanced
176.730
913
LSTM
Balancal
1.092,960
10,930
WideReeNes220
Uniteed CNN-LSIM
1,092,900
48.05
51.45
WideResNas-10
traieed CNN
CIFAR-I0I
1,405,880 860
2.5, 2.0
6586
LSTM
39.86 60.95 70.64
90
88.50
Unifled CNN-L1TMM with
1,092,900
WideResNNs-211
84.16
92.00
trained CNN
1,405 R60
Balanced
26,224,150
262.245
Unitied CNN-LSTM
26,224.480-
2.0
16.52
28.45
36.07
49.17
59.50
with baseline
101,.000
26,225
10,1100
Com +
traised ImageNet
26,6266.20
3.0,
66.405
LSTM
09.83
83.50
Unified CNN-LSTM with balanced trained CNN
26.224.480-
3.0,
26.225
18,180
Com +
25.0 45.70 54.00
73.33
86.50
401,5000
66,405
LSTM
26,626.250
Table n-accuracy on different data sets with various architectures and compressions. In all cases, the unified CNN-LSTM with balanced trained CNN highly outperforms the other methods for every value of n, even though has less remaining parameters and uses less FLOPs.
16


Reviews:
[{"review_id": "ZPQ6RRic1Nj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "More Side Information, Better Pruning: Shared-Label Classification as a Case Study\n\nSummary:\nThe goal of this paper is to use side information about a task to prune models more effectively i.e., with minimal loss in performance as compared to original model.\nThe particular type of side information they focus on is prior knowledge about a collection of instances sharing a class label. The motivation is an Information Retrieval Scenario, wherein it is expensive to identify relevant examples for a query, therefore, an approximate, cheaper model is used to identify good candidates that have a high likelihood of being relevant. The original model is then computed only on the identified subset. The paper then switches to using a related, toy problem where the goal is to predict an unknown, shared label for a given tuple of n items.\nThe paper describes 4 methods to exploit the additional information: (i) a baseline method that trains in a standard fashion and computes the label of each example in an n-tuple independently. (ii) Balanced method: Sum of standard classification loss and cross entropy computed with respect to average labels per batch\n(iii) Graph method based on GNNs (iv) CNN+LSTM architecture, where n-tuples with shared labels are treated as a sequence passed to an LSTM.\nFinally, the paper proposes a relative information metric that measures the tradeoff of information gain vs the computation cost. Empirical results are presented comparing the various methods, showing the relationship between relative information, compression ratios and n. \n\nStrengths:\n1. Authors propose a novel quantitative metric (relative information gain) in measuring the loss of performance in pruned models vs computational cost. This gives practioners a tool to clearly think about tradeoffs in cost vs model certainty.\n2. Paper provides rigorous experimental results. Each proposed method is compared under various compression ratios. Relative information is shown to be correlated with both compression ratio and n (number of examples in a tuple with shared label). For a given compression ratio, relative information is shown to improve with increasing n until a \"sweet spot\" is reached, beyond which relative information starts degrading.\nRelationship between accuracy at various compression ratios and FLOPs is also reported clearly.\n\nWeaknesses:\n1. The paper is missing a clear description of real-world applications. \na. The original motivation is a very interesting problem, wherein only an approximate function can be computed generating a subset that *possibly* share the same label. However, the actual task the rest of the paper focuses on is materially different wherein n examples are known to share the same label. Can the authors describe a real-world scenario where one is guaranteed to receive n examples at a time belonging to a single class. \nb. If these n examples come from an approximate classifier as in the original motivating scenario, how do the methods described in this paper handle \"within-tuple\" uncertainty, i.e. uncertainty that all the examples indeed belonging to the same class. If we had reasonable certainty in all examples having the same label, then why do we need another more complex/expensive classifier to be applied subsequently?\n2. The methods are not clearly described.\na. For the balanced method, a portion of the loss per batch is cross-entropy between average label of an n-tuple and the true label of the n-tuple, averaged across k n-tuples in the batch. This is not clearly described at all and required many readings. Notation is unclear: both $k$ and $l$ are used to describe the number of n-tuples in a batch. k is also used to describe the number of data points belonging to a single label i. In that case, different labels $i$ have different sizes $k_i$. After k is introduced, it is not used at all.\nb. Graph method is described in 1 sentence. Some information about the architecture is in the appendix which are not very helpful either. Paper needs to be self-contained.  What is the input graph passed to the GNN? Assuming, all examples with the same label are represented as fully connected subgraphs, does the complete dataset comprise of several disconnected components. Is the performance impacted by number of subgraphs/labels?\nc. In the LSTM based method, an n-tuple is treated as a sequence, so that LSTMs can used to capture the fact that the examples in an n-tuple are related. This is unusual usage, since LSTMs would only be able to model local neighborhood in practice. Paper claims that ordering examples by certainty gives improved performance, and supports this claim with empirical results. It is unclear, how well the models cope with errors in confidence or uncalibrated models. The current set of experiments do not address this key factor that would occur in any practical setting.\n\nConclusion:\nMy recommendation is to reject the paper at this time, because the problem statement is not well-formed. Specifically, how the methods handle uncertainty of labels within a tuple. This is especially confusing given that LSTM-based solution is found to be the best empirically. However, how would an LSTM perform if intermediate examples are in fact mislabeled. Additionally, the explanation of the methods is unclear. \n\nI would encourage the authors to make their future work stronger by grounding the work in a real problem. The IR example cited at the beginning is a good one. If this problem is solved as is, this work can be very impactful. The simplifying assumptions made at the moment weaken the problem statement. Therefore, even though the experimental results are thorough, their application to any practical scenario is not obvious.", "extra_scores": {}, "extra_text": {}}, {"review_id": "NncE8reODbu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "Summary\n\nThis paper introduces the problem of shared-label prediction -- the problem of classifying the (common) label of a set of points conditioned on the knowledge that they all share the same label --  and suggests various methods that take advantage of side information to solve it.\n\nRationale for Score\n\nI think that the idea of using side information for pruning is promising overall. However, given the lack of clarity in the exposition -- e.g., in motivating and defining the problem (and its connections to pruning) and conveying & contextualizing the paper's contributions --, I am unable to fully understand and appreciate the significance of this work.\n\nStrengths\n\n- The shared-label prediction problem introduced seems interesting and made me initially wonder whether it could be applied to, e.g., accelerating pooled-testing methods for Covid-19 (with neural nets) where a small partitioned group of samples may share the label (negative) with high probability\n- Using side information for pruning is a nice idea that may be appreciated by the pruning community\n- There are some empirical evaluations of the proposed approaches\n\n\nWeaknesses\n\n- The abstract is very long, takes up almost the entire first page, and reads more like an introduction than a proper abstract. Despite its length, the proposed method or novel idea of the paper is not revealed, but rather only merely hinted at as “we propose various methods for performing this task.”\n- The problem that this paper attempts to solve is not very well motivated by a concrete real-world application as the abstract suggests. As someone that is not very familiar with the problem tackled by the paper, I am left trying to think of a scenario where we *know for a fact* a priori that the group of points we are feeding as input to the neural network share the same label, but yet do not know the label itself.\n- The problem definition (and consequently, my sense of the paper’s contribution) is very confusing. There are numerous “problems of interest” introduced in the paper right off the bat and it is very difficult to discern the particular problem that serves as the main focus of the paper. In particular, the paper starts off in Sec. 1.1 with a very generic problem of trying to maximize the ground-truth “retrieval function given a static space of objects.” This is then relaxed to using approximations of the ground-truth retrieval function in terms of a neural network, which is then reformulated as the problem of using a pruned network to construct a shortlist of candidates for which the original network is used. Then, the authors claim that elements of this shortlist have similarity that we can exploit (for reasons that are not clear to me); unfortunately, immediately after the problem is then recast again as one of classification where the input space is partitioned into k clusters, each consisting of points of the same label, and the objective is to classify the label of each cluster using n random samples using the information that all points in the cluster share a label. This is then somewhat more rigorously defined as the “shared prediction problem” in Sec. 1.2 and set as the target problem that this paper tackles.\n\n Overall, I found this exposition quite confusing and not very well-introduced or motivated by a real-world application (as the authors had hinted at in the abstract). Since the problem in question is quite general, I am also not sure why the pivot of the paper is to emphasize pruning in the introduction, rather than as a potential application of the proposed approach in, e.g., the experiments section. Since the shared prediction problem is more concrete relative to the more general problem that the authors start off with in Sec. 1.1, I would recommend simply defining the shared prediction problem (the most concrete of them all) first, rather than starting with the most abstract problem.\n- The definitions for the variables used are ambiguous and defined way later after being used. For example, the compression ratio \\rho, which is used as early as Sec. 2, is not formally defined until Sec. 4. This might have been fine if the definition of the compression ratio was consistent with that of existing work -- e.g., (# of parameters in the original network) / (# of parameters remaining in pruned network) -- however, it turns out that, as defined much later on in Sec. 4, it is defined as “logarithm to the base 10 of the number of parameters in the original network divided by the number of parameters remaining after pruning.” This definition is quite confusing and misplaced under the section “Our Methods.” For clarity, I would recommend defining the variable earlier on when it is used in Sec. 2 (to define the problem), and using actual math to define the compression ratio, among other pertinent variables.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LadIPHLEnFO", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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 study how to improve the prediction and pruning performance with additional information generated by labels in the shared-label classification problem. As a starting point, the authors consider a simple scenario where side information can be extracted from the same labeled batch. To train the neural network, the authors use a balanced loss consisting of a weighted sum of general cross-entropy and cross-entropy of average batch prediction. The authors also suggest a new CNN-LSTM architecture to improve predictive performance to exploit the side information. The experiments section shows the proposed method performs well and achieves a high compression rate. \n\nThe data model used in this study is different from the common classification problem. This paper assumes that n-data points give side information with the shared-label batch, referred to as \"n-tuple.\" In general, classification problems have labels independent of other data points. \n\n[Strength]\n \nThe authors study a general relationship between pruning and additional side information for the shared label problem. The authors define \"relative information\" to measure the appropriate compression rate for various prediction performance and pruning levels. Using the relative information, we can dramatically reduce the number of parameters while maintaining prediction performance. Besides, the proposed CNN-LSTM architecture improves the prediction performance with the shared-label training scheme.\n\n[Weakness]\n\nThis paper considers a very different data model which never been studied before. The shared-label model should be motivated very well. I'm not convinced why we have to study this model.\n\nThe explanation of which benefits the network from the side information is ambiguous.  There is no theoretical and empirical explanation of how the side information and balanced loss can discriminate ineffective parameters. It requires providing more clear evidence, such as the statistics of network parameters before and after the pruning algorithm.\n\nThe existence of optimal compression rate \\rho^* should be discussed more rigorously if possible with a theoretical proof based on relative information.  \n\nIn the experiment section, only the 5 Conv net was investigated to check the effectiveness of pruning. It would be more convincing if the authors can add results for the proposed CNN-LSTM network.\n\n[Minor Issue]\n\nIt is challenging to read Fig1-9 because of their interpretation. I suggest the authors use other colors with a bigger font size.\n\nIt would be better to use tables rather than graphs to present many experimental results. Graphs are too small to understand ", "extra_scores": {}, "extra_text": {}}, {"review_id": "DlwPIx1EjQU", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "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 paper proposes to use a set of input examples, x1 to xn, having a common label y, and use them together for better classification. And use these shared label examples as additional information during model pruning.\n\nI have multiple challenges to understand this research paper:\n\n1. Clarity of Writing:\nThe paper is very tough to read and understand. The authors jump through multiple levels of motivations, starting with information retrieval and then to approximation of database queries. But then the rest of the paper talks about loss averaging and results are shown using a CNN model on CIFAR10, and TinyImagenet. Either the whole motivation on IR aspects can be removed or relevant experiments and approach be proposed. At multiple places, I am either lost or confused on what is the problem that the paper is trying to solve. Example, after reading 2 pages of the paper, the authors state, \"We depart from the original motivating information retrieval scenario, and henceforth consider a simpler, toy problem which we call the shared-label prediction problem.\"\n\n2. Misleading Title and Takeaway in the paper:\nThe paper title, abstract, and motivation says to use \"More Side Information\". While shared-labels is not side information or additional information. If you have 10 instances to classify, instead of classifying them independently, the paper is trying to classify them together. So, there is no side information used in the approach. Also, this is not a \"structure\" present in X.\n\n3. Incorrect or Insufficient assumptions:\nThe paper makes a lot of strong assumptions, which are not practical:\na. What if multiple instance, x1 to xn of the same class label is not available ? In few shot learning or one shot learning scenario. \nb. \"We assume the network and the pruning methods are state-of-the-art, and it is not our goal here to improve them\" -  I do not understand the need for introduction model pruning for shared label classification. If the goal is not to improve pruning methods, then why do network pruning, at all?\nc. \"For all methods we study, fixing the information size n, our experiments suggest that there exists a sweet spot phenomenon, or a \"compression threshold\" in the sense that RI, as a function of ρ, has a global maximum ρ∗\" - There is no proven approach that such a threshold should exist for any dataset/model combination. I do not agree to this assumption.\n\n4. Lack of Novelty:\nMost of the approaches explained in Section 4 are just averaging the loss of the tuple of samples. When we average the samples, it is automatically considered that the tuple of samples are drawn from i.i.d. And in the proposed CNN-LSTM approach, the tuple of samples are \"sequentially\" classified. That raises more questions than answers - why sequence, and in what sequence? While the paper does not discuss any of these important questions.\n\n5. Appendix has more information than the paper itself:\nMost of the detailed and important information about the paper, including primary details about the approach, the model architecture, and many experimental results are in the appendix. At many instances, the paper reads like an index to the appendix. Example, section 4.3, \"We investigate two kinds of architecture, see Appendix B for further information\". Throughout the paper we do not have information the architectures. Even the proposed approach in 4.4, \"An illustration of this architecture is shown in Appendix A.1\"\n\n6. Lack of experiments:\nThe proposed approach of CNN-LSTM is comapred with baseline methods : loss averaging, graph based averaging of loss. And the paper claims that the CNN-LSTM approach is better than the baseline methods. This is insufficient. The paper fails to compare with other relevant techniques in literature and place the paper empirically among the others papers in the literature. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "65btFXEAd7", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 discusses empirically a workflow about how to compress network architectures with side information. The side information defined in this study is provied by the training data instances that share the same class labels, aka the problem of shared label prediction. \n\nThe contribution of this work can be concluded as\n1. This work defines a set of benchmarks measuring efficiency of shared label prediction, including relative information and information gain. These two metrics are used to measure how much information can be learned by the compressed neural networks over the data instances sharing the same label, given the compression ratio and the name of training instances \n2. This work empirically unveil the sweet spot phenomena, which indicates how relative information varies in an montonical way with respect to different compression ratios. \n3. This work proposes to make full use of the training instances sharing the same class label via a combination of CNN and LSTM. CNN is used to extract features and LSTM is used to encode the correlation between different instances sharing the label. Experimental study confirms the merit of the proposed workflow. \n\nOverall, this paper is well explicated, starting with clearly written background on basic concepts and prior work, stating clear the algorithmic design and conducting correspondingly the experimental study to confirm the benefits of the algorithm.  \n\nThere are several downsides:\n\n1) no theoretical discussion about the sweet spot phenomena is given. The turing point shown in this observation is very interesting. If we can provide an estimate about when the turining point appear (given a compression ratio and a base neural network architecure), that would be very useful for guding practical network compression tasks. \n\n2) Can we still observe the sweet sopt thing for the proposed CNN + RNN workflow ? It looks like Figure 8 and 9 both assume the compression ration is fixed. \n\n3) For the RNN architecture, why does the confidence ordering based RNN perform better than random ordering? \n\n4) When n =1,  it is not surprising to find the balance method has a worse performance than the baseline method. When n = 1, The average batch prediction includes a blurred prediction result by taking the average of k training instances (when n = 1, each n-tuple contains only 1 instance). Thus the average same label loss should be noisy.  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of classifying a set of points given the knowledge that all points should have the same class. There seems to be a consensus among the reviews that under the assumptions made, the authors provide thorough experiments convincing that their method is useful. However, the paper has two weaknesses that are too strong to ignore. First, the clarity of exposition seems to be lacking, specifically a clear motivation for this new setup as well as its connection to the abstract problem being solved. Second, the assumptions made seem to be too strong, and the solution seems to rely on these strong assumptions too much. 

Decision: Reject