Deep Ensembling with No Overhead for either Training or Testing: The All-Round Blessings of Dynamic Sparsity
Authors: Shiwei Liu
Tianlong Chen
Zahra Atashgahi
Xiaohan Chen
Ghada Sokar
Elena Mocanu
Mykola Pechenizkiy
Zhangyang Wang
Decebal Constantin Mocanu
Venue: ICLR 2022 Poster (2022)
Keywords: efficient ensemble
FreeTickets
dynamic sparse training
deep ensemble
dynamic sparsity

Abstract: The success of deep ensembles on improving predictive performance, uncertainty estimation, and out-of-distribution robustness has been extensively studied in the machine learning literature. Albeit the promising results, naively training multiple deep neural networks and combining their predictions at inference leads to prohibitive computational costs and memory requirements. Recently proposed efficient ensemble approaches reach the performance of the traditional deep ensembles with significantly lower costs. However, the training resources required by these approaches are still at least the same as training a single dense model. In this work, we draw a unique connection between sparse neural network training and deep ensembles, yielding a novel efficient ensemble learning framework called $FreeTickets$. Instead of training multiple dense networks and averaging them, we directly train sparse subnetworks from scratch and extract diverse yet accurate subnetworks during this efficient, sparse-to-sparse training. Our framework, $FreeTickets$, is defined as the ensemble of these relatively cheap sparse subnetworks. Despite being an ensemble method, $FreeTickets$ has even fewer parameters and training FLOPs than a single dense model. This seemingly counter-intuitive outcome is due to the ultra training/inference efficiency of dynamic sparse training. $FreeTickets$ surpasses the dense baseline in all the following criteria: prediction accuracy, uncertainty estimation, out-of-distribution (OoD) robustness, as well as efficiency for both training and inference. Impressively, $FreeTickets$ outperforms the naive deep ensemble with ResNet50 on ImageNet using around only $1/5$ of the training FLOPs required by the latter. We have released our source code at https://github.com/VITA-Group/FreeTickets.

Published as a conference paper at ICLR 2022
DEEP ENSEMBLING WITH No OVERHEAD FOR EITHER TRAINING OR TESTING: THE ALL-ROUND BLESSINGS OF DYNAMIC SPARSITY
Shiwei Liu', Tianlong Chen', Zahra Atashgahi', Xiaohan Chen', Ghada Sokar!, Elena Mocanu', Mykola Pechenizkiy'. Zhangyang Wang", Decebal Constantin Mocanu Eindhoven University of Technology. "University of Texas at Austin, UUniversity of Twente,
wt.liu3,g.aa.. sokar, m. www.ennikkiyyeeeeee..... htt............ccceeeeeie//.ee.e ftianlong chen, xiaohan, chen, aat.aaaccchhhat..aaaaaaaneaaaaar az.atashgahi, .oc.anu d. hec.....ccccnceetteettttee.
ABSTRACT
The success of deep ensembles improving predictive performance, uncertainty estimation, and out-of-distribution robustness has been extensively studied in the machine learning literature. Albeit the promising results, naively training multi- ple deep neural networks and combining their predictions at inference leads to prohibitive computational costs and memory requirements. Recently proposed efficient ensemble approaches reach the performance of the traditional deep en- sembles with significantly lower costs. However, the training resources required by these approaches are still at least the same as training a single dense model. In this work, we draw unique connection between sparse neural network train- ing and deep ensembles, yielding a novel efficient ensemble learning framework called FreeTickets Instead of training multiple dense networks and averaging them, we directly train sparse subnetworks from scratch and extract diverse yet accurate subnetworks during this efficient, sparse-to-spane training. Our frame- work, PFreeTickels is defined as the ensemble of these relatively cheap sparse subnetworks. Despite being an ensemble method, FreeT ickets has even fewer parameters and training FLOPs than single dense model. This seemingly counter- intuitive outcome is due to the ultra training/inference efficiency of dynamic sparse training. FreeTicker surpasses the dense baseline in all the following criteria: prediction accuracy, uncertainty estimation, out-of- -itro--distribution (OoD) robustness, well as efficiency for both training and inference. Impressively, FreeTTickel outperforms the naive deep ensemble with ResNet50 on ImageNet using around only 1/5 of the training FLOPs required by the latter. We have released our source code at https:tpss... : http//gtttu//b/ com /ttp://TTo-oroopp/eeeeiiccc
INTRODUCTION
Ensembles (Hansen Salamon 1990:
Levin et al. 1990) of neural networks have received large
success in terms of the predictive accuracy (Perrone & Cooper 1992 Breiman 1996]
Dietterich
2000 Xie et al. 20133, uncertainty estimation (Fort al. [019 Lakshminarayanan
2017 Wen
et al. 2020 Havasi et al. 2021), and out-of ditoo---dstrbuttionn robustness (Ovadia et al.) 2019 9a Gustafsson
2020 Given the fact that there are a wide variety of local minima solutions located in the high dimensional optimization landscape of deep neural networks and various randomness (e.g., random initialization, random mini-batch shuffling) occurring during training, neural networks trained with different random seeds usually converge to different low-loss basins with similar error rates (Fort ctt al., 2019; Ge et al.) 2015) Kawaguchi] 2016) Wen et al.) 2019). Deep ensembles, combining the predictions of these low-loo networks. achieve large performance improvements over a single network (Huang et al.) 2017 Garipov et al. 2018: Evci et al. 2020b).
al.
Despite the promising performance improvement, the traditional deep ensemble naively trains multiple deep neural networks independently and ensembles them, whose training and inference cost increases linearly with the number of the ensemble members. Recent works efficient ensembles are able

---

Published as a conference paper at ICLR 2022
FreeTTicket Engemble
Free ticket 1
Free ticket
Free ticket M
Exploration
Refine 1
Refine
Refine M
Training Time
Figure 1: Illustration of FrreeTickets with EDST Ensemble as an example. EDST Ensemble, consisting of exploration phase and M sequential refinement phases, produces M diverse subnetworks with very low cost (hence called "free tickets"). By combining all these free tickets, EDST Ensemble matches the performance of the dense ensemble with only half of FI FI.OPs required to train a single dense model.
to reach the performance of dense ensembles with negligible overhead compared to a single dense model (Wen et al.) 2020: Wenzel et al. 2020 Havasi et al., (021). However, the training resources required by these approaches are still at least the same as training a single dense model. Since the
size of advanced deep neural networks is inevitably exploding (Touvron et al. 2020 Dosovitskiy al. 202T Brown et al., 20200 Touvron et al.) (02T), the associated enormous training costs are
potentially beyond the reach of most rescarchers and startups, leading to financial and environmental
concerns (Garcfa-Martin et al. 2019 Schwartz et al. 2019; Strubell et al. 2019).
On the other hand, researchers have recently explored the possibility of directly training sparse neural networks from scratch (Mocanu et al.) 2016; Liu et al. 2020a Evei et al.) 2019). while trying to maintain comparable performance. Training sparse network from scratch typically results in worse
performance than the traditional network pruning (Kalchbrenner et al. 2018: Evei et al., 2019), with the exception of Dynamic Sparse Training (DST) (Mocanu et al. 2018 Evei al. 2020a]] Liu et al. 20)1c Instead of inheriting weights from dense networks, DST starts from a randomly mandomly-initializee sparse network and optimizes the model weights together with the sparse connectivity during training. However, the current only way for DST to match the performance of its dense counterpart on the popular benchmark, e.g., ResNet-50 on ImageNet, is to extend the training time (Evci al. 2020a). which might require thousands of training epochs for extremely sparse models (Liu et al. (021c)..
In this paper, we attempt to address the anoove-mentioned two challenges jointly by drawing unique connection between sparse training and deep ensembles. Specifically, we ask the following question:
Instead of allocating all resources to find a strong winning ticket, can we find many weak tickets with very low costs (free tickets), such that the combination of these free tickets can significantly outperform the single dense network, even the dense ensemble?
Note that it is not trivial to obtain free tickets. To guarantee superior ensemble performance, three key desiderata that the free tickets are expected to satisfy (1) high diversity: according to the ensemble theory (LeCun et al. 2015 Hansen & Salamon 1990 Ovadia al., 2019b), higher diversity among ensemble members leads to higher predictive performance; (2) high accessibility: free tickets should be cheap to obtain that the overall training cost does not compromise too much; and (3) high expressibility: the performance each free ticket should be comparable with the dense model.
Leveraging the insight from Liu et al. (202bb) that full network contains plenitude of perfor- mative subnetworks that are very different in the topological space, we introduce the concept of FreeTickklss, an efficient ensemble framework that utilizes sparse training techniques to create cheap yet accurate subnetworks for ensemble. Furthermore, we instantiate FreeTickklss by proposing two efficient ensemble methods Dynamic Sparse Training Ensemble (DST Ensemble) and Efficient Dynamic Sparse Training Ensemble (EDST Ensemble). Both methods yield diverse subnetworks that consummately satisfy the above-mentioned criteria. We summarize our contributions below:
Our first method, DST Ensemble, independently trains multiple subnetworks from scratch with dynamic sparsity. By averaging the predictions of these subnerworks, DST Ensemble improves the predictive accuracy, OoD robustness, uncertainty estimation, and efficiency over the traditional dense ensemble.
Our second, liight method EDST Ensemble) yields many free tickets in single run, which is more efficient to train and test than a single dense model, while approaching the performance of the traditional dense ensemble.
2

---

Published as a conference paper at ICLR 2022
We analyze the diversity of the individual subnetworks generated by our methods and confirm the effectiveness of our methods on inducing model diversity.
Our results suggest that besides the training/inference efficiency, sparse neural networks also enjoy other favorable properties which are absent in dense networks (robustness, out-of- distribution generalization, etc), opening the path for new research directions.
2 RELATED WORKS
Efficient Ensembles. One major limitation of ensembles is the expensive computational and memory costs for both training and testing. To address this problem, various approaches have been proposed. TreeNet (Lee et al.) 2015) shares weights in earlier layers and splits the following model into several branches, improving accuracy over the dense ensemble. Monte Carlo Dropout (Gal & Ghahramani 2016) can be used to approximate model uncertainty in deep learning without sacrificing either computational complexity or test accuracy. BatchEnsemble (Wen et al., 2020) was proposed to improve parameter efficiency by decomposing the ensemble members into the product of shared
matrix and a rank-one matrix personalized for each member. MIMO (Havasi et al. (202T) uses a multi-input multi-output configuration concurrently discover subnetworks that co-habit the dense network without explicit separation. Snapshot (Huang et al., (017)) and FGE (Garipov et al. 2018)
Furlanellll discover diverse models by using cyclical learning rate schedules, Furlanello et al. (2018) applied knowledge distillation (Hinton et al. 2015) to train several generations of dense students. The ensemble of the dense students outperforms the teacher model significantly. Other related works include but are not limited to hyper-batch ensembles (Wenzel et al. (2020) and Late Phase (Oswald ctt al. 202T). However, the training resources required by these methods are still at least the same as training single dense model. In contrast to the existing efficient ensemble methods, our methods (EDST Ensemble) can match the performance of naive ensemble with only a fraction of the resources required by training single dense network.
Dynamic Sparse Training. Dynamic Sparse Training (DST) is a class of methods that enables training sparse neural networks from scratch by optimizing the sparse connectivity and the weight values simultaneously during training. DST stems from Sparse Evolutionary Training (SET) (Mocanu et al.) 2018), sparse training algorithm that outperforms training static sparse model from scratch (Mocauu et al.) 2016 Evci et al. 2019). Weight reallocation was further proposed in Mostafa & Wang (2019); Dettmers & Zettlemoyer (2019); Liu al.) (202Tb) reallocate new weights across layers for better layer-wise sparsity. Further, Dettmers & Zettlemoyer (2019); Evci et al. (2020a) leverage the gradient information the backward pass guide the optimization of sparse connectivity and demonstrate substantial performance improvement. Some recent works (Jayakumar al., 2020 Raihan & Aamodt 2020 Liu al. 2021c) demonstrate that a large range of exploration in the parameter space is important for dynamic sparse training. |Pice & Tanner (2021) improved the performance DST by adding additional non non-trainable parameters. DST has also demonstrated its strength in feature detection (Atashgahi et al., (02T). D, lifelong learning (Sokar et al.) (021).
federated learning (Zhu & Jin 2019 Bibikar et al. 2022 Huang et al. 2022), and adversarial training (Özdenizei & Legenstein 2021. Sparse MoE (Shazeer et al.
et al. 2021
sparsely activates one of the few expert networks to increase the model capacity - but with a constant computational cost. It usually requires specialized modules, such as gating and selector networks to perform the sparsification.
3 FREETICKETS
3.1 PRELIMINARIES
Dynamic Sparse Training. Let's consider i.i.d. classification setting with data ((x,, y1) (:)),-1 where & usually denotes input samples and y the corresponding labels. For a network f(x; 0) parameterized by 0 E Rd, we train f(x; 0) to solve the following optimization problem: argmin, ΣN= [(f ().r;;))),))) U))
Dynamic sparse training (DST) starts with a randomly- initialized sparse neural network f(x; 0.). parameterized by fraction of parameters 0.. The sparsity level of the model pre-defined as S ||0_1ee where || llo is the norm. The goal of DST is yield a sparse network with the target sparsity S after training, while maintaining the overall computational and memory overheads close to training static sparse model (fixed sparse connectivity).
3

---

Published as a conference paper at ICLR 2022
During training, DST continuously minimizes the loss Ex= [xf(x;; 0.). while periodically exploring the parameter space for better sparse connectivity with non con-differentiable heuristics. A common exploration heuristics is prune-and-grow that is. pruning fraction p of the unimportant weights from o, followed by regrowing the same number of new weights. By repeating this prune-and-grov eycle, DST keeps searching for better sparse connectivities while sticking to fixed parameter budget. See Appendix A for the general pseudocode and a brief literature review of DST.
3.2 FREETICKETS ENSEMBLE
We propose the concept of FreeTickets here. FreeTickels refers to efficient ensemble methods that utilize DST to generate subnetworks for the ensemble. free ticket is a converged subnetwork created by sparse training methods. These free tickets {0], ... 0 J. .. within one training run (EDST Ensemble) or multiple training runs (DST Ensemble), are further used to construct the FreeTicket Ensemble. Assuming that the probability of the 1tth output neuron in the classifier of the jth free ticket is given by p(az)) Then the corresponding output probability in the ensemble given by taking the average across all the M subnetworks, i.e., M Σ Ey=1p(a))
observed and collected either
Compared with the existing efficient ensemble techniques (Huang et al., 2017 Wen al. 2020), FreeTicket induces diversity inspired by the observations that there exist many performant sub- networks with very different sparse topologies located in the full network (Liu et al. 2020b). The efficiency of FreeT so that the memory and floating -oonnt operations (FLOPs) required by FreeTickets can be even fewer than training a single dense network. To realize the concept of FreeT ickels, we introduce two DST-based ensemble methods, DST Ensemble and EDST Ensemble, as described below.
comes from the fact that each subnetwork is sparse from the beginning.
3.2.1 DST ENSEMBLE
Dynamic Sparse Training Ensemble (DST Ensemble) is presented in Algorithm 2 Appendix B It takes advantage of the training efficiency from DST and independently trains M sparse networks with DST from scratch. By averaging the predictions of each sparse neural network, DST Ensemble can improve the predictive accuracy and uncertainty estimation significantly. Except for the common diversity producers, i.e., random initializations and random stochastic gradient descent (SGD) noise, each DST run converges to different sparse connectivities, promoting even higher diversity over the naive dense Ensemble.
We choose the advanced DST method the Rigged Lottery (RigL) (Evei al. 2020a) for DST Ensemble. RigL contains three main steps: sparse initialization, model weight optimization, and parameter exploration.
Sparse Initialization. Each subnetwork is randomly initialized with the Erdös-Rén Rényi-Kernee (ERK) (Mocanu et al., 2018 Evei al. 2020a) distribution at sparsity of S. The sparsity level of layer / is scaled with 1 . Ixn' x where n' refers to the number of neurons/channels of layer 1; wt and le' are the width and the height of the convolutional kernel in layer 1. ERK allocates higher sparsities to the layers with more parameters.
+w
Model Weight Optimization. After initialization. the activated weights are optimized by the standard optimizer SGD with momentum (Sutskever et al. 2013 Polyak 1964) and the non-activated weights are forced zero.
Parameter Exploration. After every AT iterations of training, we perform parameter exploration once adjust the sparse connectivity, More concretely, we first prune a fraction p of weights from 0, with the smallest magnitude:
0. = Topk(p 1-9)
where Top k) returns the weight tensor retaining the top k-proportion of elements from Immediately after pruning, we grow the same number new weights back which have the highest gradient magnitude:
0, 0', TopK( p)
where Bige; are the gradients of the zero weights. We follow the suggestions in Liu et al. (002cc) and choose = 0.5 and a large update interval AT = 1000 for CIFAR- 10/100 and AT 4000 for ImageNet to encourage almost full exploration of all network parameters.
4

---

Published as a conference paper at ICLR 2022
3.2.2 EDST ENSEMBLE
While efficient, the number of training runs (complete training phases) required by DST Ensemble increases linearly with the number of subnetworks, leading to an increased device count and resource requirements. To further reduce the training resourees and the number of training runs, propose Efficient Dynamic Sparse Training Ensemble (EDST Ensemble) to yield many diverse subnetworks in one training run. The overall training procedure of EDST Ensemble is summarized in Algorithm
The challenge of producing many free tickets serially in one training run is how to escape the current local basin during the typical DST training. Here, we force the model to escape the current basin by significantly changing a large fraction of the sparse connectivity, like adding significant perturbations to the model topology. 'he training procedure of EDST Ensemble is end-to-end training run consisting of one exploration phase followed by M consecutive refinement phases. The M refinement phases are performed sequentially one after another within one training run.
Exploration phase. We first train sparse network with DST using a large learning rate of 0.1 for time of fex. The goal of this phase is to explore a large range of the parameter space for potentially good sparse connectivity. Training with a large learning rate allows DST to validly search a larger range of the parameter space, as the newly activated weights receive large updates and become more competitive at the next pruning iteration.
Refinement phase. After the exploration phase, we equally split the rest of training time by M to collect M free tickets. At each refinement phase, the current subnetwork is refined from the converged subnetwork in the previous phase (the first subnetwork is refined from the exploration phase) and then trained with learning rates 0.01 followed by 0.001 for time of tre. Once the current subnetwork is converged, we use a large global exploration rate = 0.8 0.8 and a larger learning rate of 0.01 to force the converged subnetwork to escape the current basin. We repeat this process several times until the target number of free tickets is reached. The number of subnetworks M that we obtain at the end of training is given by M frotal-fer. faee See Appendices I and J for the effect of the global exploration rate q and the effect of different regrowth criteria on E Ensemble, respectively.
tre
Different from DST Ensemble, the diversity of EDST Ensemble comes from the different sparse subnetworks the model converges to during each refinement phase. The number of training FLOPs required by EDST Ensemble is significantly smaller than training an individual dense network, as DST is efficient and the exploration phase is only performed once for all ensemble learners.
EXPERIMENTAL RESULTS
In this section, we demonstrate the improved predictive accuracy, robustness, uncertainty esti- mation, and efficiency achieved by FreeTickets. We mainly follow the experimental setting of MIMO (Havasi et al. 202T), shown below.
Baselines.
We compare our methods against the dense ensemble, and various state-of-the-ar ef- ficient ensemble methods in the literature, including MIMO (Havasi et al. 2021), Monte Carlo Dropout (Gal & Ghahramani] 20166). BatchEnsemble (Wen et al. 2020), TreeNet (Lee et al. 2015).
Snapshop (Huang al.) 2017), and FGE (Garipov et al. 2018).
Moreover, to highlight the fact that the free tickets are non-trivial to obtain, we further implement three sparse network ensemble methods: Static Sparse Ensemble (naively ensemble M static sparse networks), Lottery Ticket Rewinding Ensemble (LTR Ensemble;(Framd
et al. 2020)) (ensemble M winning tickets"] trained with the same mask but different random seeds), and pruning and fine-tuning (PF Ensembles; Han et al. (2015)) While Static Sparse Ensemble can be diverse and efficient, it does not satisfy the high expressibility property (Evci et al.) 2019). LTR Ensemble suffers from low diversity and prohibitive costs. PF Ensemble requires at least the same training FLOPs as the dense ensemble. See Appendix for their implementation and hyperparameter details.
Architecture and Dataset. We evaluate our methods mainly with Wide ResNet28-10 10 Zagoruyko & Komodakis 2016) on CIFAR-10/100 and ResNet-50 (He et al. 2016) on ImageNet.
"To be distinct with the standard exploration rate in DST, we define q as the global exploration rate. We rewind the tickets the weights 5% epoch used in Frankle al. 2020 Chen al. 2021b
Chen
5

---

Published as a conference paper at ICLR 2022
Metrics. To measure the predictive accuracy, robustness, and efficiency, follow the Uncertainty Baseling and report the overall training FLOPs required to obtain all the subnetworks including forward passes and backward passes. See Appendix D for more details on the metrices used.
Table I: Wide 10//1/2R00// we mark the best results of one-pass efficient ensemble in bold and the
best results of multi-pass efficient ensemble in blue. Results with are obtained from Havasi ct al. (021).
Training FLOPS ())
Training
Methods
Acc (1)
NLL (1)
ECE (1)
cAce
cNLL
<BCE (1)
runs ())
Single Dense Model"
96.0
0.159
0.023
76.1
1,050
0.153
3.6c17
Monte Carlo Dropout"
95.9
0.160
0.024
68.8
1.270
0.166
1.00x
MIMO (M 3)'
96.4
0.123
0.010
76.6
0.927
0.112
1,00x
EDST Ensemble 3) 0.89 (Our))
96.3
0.127
0.012
77.9
0.814
EDST Ensemble (M 7) = 0.3) (Ours)
96.1
0.122
0.008
77.2
0,803
0.081
0,57
TreeNet (M =
95.9
0.158
0.018
75.6
0.969
0.137
1.52K
Buschnnsemlle (M = 4)"
96.2
0.143
0.021
77.5
1,020
0.129
1.10x
LTR Ensemble (M = 3) 0.8)
96.2
0.133
0.015
76.7
0.950
0.118
1.75x
Static Spanse Enseemble
(8 0.8)
96.0
0.133
0.014
76.2
0.920
PF Ensemble (M 3) (S = 0.8)
96.4
0.129
0.011
78.2
0.801
0.082
3.75%
DST Ensemble (M (5- 0.8) (Ours)
96.3
0.122
0.010
78.8
0.766
0.075
1.01x
Dense Ensemble (M 4)*
96.6
0.114
0.010
77.9
0.810
0.087
4.00x
Table Wide ResNe128-1OCIIFARI 10/CIFARIO:: we mark the best results of one-past efficient ensemble in bold and the best results multi-pass efficient ensemble in blue. Results with are obtained from Havasi et al. (2021).
Training FLOPSs (L)
Truining
Methods
Acc (1)
NLL (1)
ECE (1)
cAce (*)
cNI.I. (1)
cRCP.
runs (L)
Single Dense Model
79.8
0.875
0.086
51.4
2,700
0.239
3.6e17
Monte Carlo Drapout"
79.6
0.830
0.050
42.6
2,900
0.202
1.00x
MIMO (M 3)
82.0
0.690
0.022
53.7
2.284
0.129
1.00x
EDST Ensemble 33 0.8) (Ours)
82.2
0.137
0.61x
EDST Ensemble (M (8 = (Ous)
82.6
0.653
0.036
52.7
2.410
0.170
0.57
TreeNet (M
80.8
0.777
0.047
53.5
2.295
0.176
1.52x
BatchEnsemble (M 1y"
81.5
0.740
0.056
54.1
2,490
0.191
1.10%
LTR Ensemble (M 3) 0.8)
82.2
0.703
0.045
53.2
2.345
0.180
1.75
Static Spusse Ensemble
(8 0.8)
82.4
0.167
1.0xx
Pf Ensemble (M 3) (8- 0.8)
83.2
0.639
0.020
54.2
2.182
0.115
3.75x
DST Ensemble (M (S 0.5) (Oun)
83,3
0.623
0.018
55,0
2,109
0.104
101x
Dense Ensemble (M d)"
82.7
0.666
0.021
54.1
2,270
0.138
4.00x
Table ResNet50/lmageNet:: we mark best results one-pass efficient ensemble in bold and the best results of multi- mulli-pass efficient ensemble in blue. Results with are obtained from Havasi et al. (2021).
Methoos
NLL
ECE(()
<NIL.
<BCE
sAce
.NLL
4ECE())
FLOPss
TTriiiing (1)
Single Denue Model'
76.1
0.943
0.039
40.5
3.200
0.305
0.7
5.09
0.43
4.8c18
MIMO 20 - 0.6
71.5
6.877
6.07
43.3
51300
0.196
1.4
7.76
0.45
190s
EDST Ensemble//4 (M 22/15 (.8) (Ouss)
76.9
0.744
0.060
41.3
3.014
8.055
3.7
4.00
0.37
0.48%
EDST Fremmbl: (M 1::8
(.8) (Dun))
77.7
4.74
6.35
085x
BondEniemble
DST Fraemble (M 21(8- 0.8) (Dard)
28.3
0.914
0.060
43.7
1910
6,687
4.09
0.38
1.13x
Drmo Ennemble (M 57"
77.5
0.577
0.011
42.1
2.900
0.051
400%
Results.
The metrics on CIFAR-10/100 and ImageNet reported in Table Table 2 and Table 3 respectively. For a fair comparison, we mainly set M of our methods the same as the one used in MIMO. See Appendix L for the comparison between Snapshot, FGE, and our methods.
With multiple training runs, DST Ensemble consistently outperforms other efficient ensemble meth- ods, even the dense ensemble on accuracy, robustness, and uncertainty estimation, while using only 1/4 of the training FLOPs compared to the latter. When the number of training runs is limited to 1, EDST Ensemble consistently outperforms the single dense model by large margin, especially in terms of accuracy. with only 61 % training FLOPs. Moreover, we observe that the performance of EDST Ensemble can further be improved by increasing the sparsity level. For instance, with a high sparsity level S = 0.9, EDST Ensemble can collect 7 subnetworks, more than twice as many as O.S. Combining the prediction of these sparser subnetworks boosts the performance of EDST Ensemble towards the dense ensembles with only 57% training FLOPs, beyond the reach of any efficient ensemble methods. More impressively, DST Ensemble achieves the best performance on uncertainty estimation and OoD robustness among various ensemble methods.
As we expected, Static Sparse Ensemble and LTR Ensemble consistently have inferior ensemble performance compared with DST Ensemble. While PF Ensemble achieves comparable performance
hes

---

Published as a conference paper at ICLR 2022
with DST Ensemble, its costly procedure requires more than triple the FLOPs of DST Ensemble. We argue that LTR is not suitable for FreeTickets since (1) it starts from a dense network, with the costly iterative train- train-prune- prune- cetueertrrin process. Hence it is more expensive than training dense network, in contrary to our pursuit of efficient training (our method sticks to training sparse networks end-to-end); (2) The series of sparse subnetworks yielded by iterative pruning is not diverse enough, since the latter sparse masks are always pruned from and thus nested in earlier masks (Evci et al. 2020b), Evci al. (2020b) show that the different runs of winning tickets discovered by LTR are always located in the same basin as the pruning solution. Consequently, the ensemble of LTR would suffer from poor diversity, leading to poor ensemble performance. We observe a very similar pattern in Section 5.1 as well. The diversity and performance of LTR Ensemble are lower than DST-based ensembles, highlighting the importance dynamic sparsity sparse network ensembles.
FREE TICKETS ANALYSIS
5.1 DIVERSITY ANALYSIS
According to the ensembling theory (LeCun et al. 2015 Hansen & Salamon 1990; Ovadia et al.,
2019b), more diversity among ensemble learners leads to better predictive accuracy and robustness. We follow the methods used in Fort et al.] (2019) and analyze the diversity of the subnetworks collected by our methods in function space.
Concretely, we measure the pairwise diversity of the subnetworks collected by our methods on the test data. The diversity is measured by Da E [d (Pi (2/=11 IN); (2 (NN))] where d(:,.) is a metric between predictive distributions and (zt, y) are the test set. We use two metrics (1) Prediction Disagreement, and (2) Kullback Leibler divergence.
Prediction Disagreement. Prediction Disagreement defined as the fraction of test data the predic- tion of models disagree on: dais(P,, (P1, P2) N E (arg maxg. Pi (0)) # arg maxg. P2(0:)).
Kullback-Leibler (KL) Divergence. KL Divergence (Kullback & Leibler 1951 is metric that is widely used to describe the diversity of two ensemble learners (Fort et al. 2019 Havasi et al. 2021 defined as: (PL P2) Ep, [log Pi (y) - log (z))].
Table 4: Prediction disagreement and KL divergence among various sparse ensembles (M 3, S = 0.8).
Wide ResNe28.1UCIIARRU
Wide
das (t)
dic,( (f)
Acc (f)
das. (1)
dkI.
(t)
LIT Enseabbie
0.026
0.056
96.200
0.111
0.185
82.100
Static Ensemble
0.031
0.079
96.000
0.156
01401
82.400
EDST Fasemble (Qurs)
0.031
0.073
0.237
Ensemble
0.035
0.108
96.400
0.148
0.345
83.200
DST Ensemble (Ours)
0.085
0.095
96.300
0.166
0.411
83.500
Dense Ensemble
0.032
0.086
98.600
0.145
0.338
82.700
We report the diversity among various sparse network ensembles in Table 4 We see that DST Ensemble achieves the highest prediction disagreement among various sparse ensembles, especially on CIFAR-100 where its diversity even surpasses the deep ensemble. Even though EDST Ensemble produces all subnetworks with one single run, its diversity approaches other multiple-run methods. The diversity comparison with non-sparse ensemble methods is reported in Figure Right. Again, the subnetworks learned by DST Ensemble are more diverse than the non-sparse methods and the diversity of EDST Ensemble very close to the diversity of the dense ensemble, higher than the other efficient ensemble methods e.g.. TreeNet and BatchEnsemble.
Wide ResNet28-11 10 on CIFRR-10
10
das (t)
dxL (1)
KL Divergence
20
1ST Crsemble
TreeNet
0.010
0.010
30
BatchEnsemble
0.014
0.020
30
Ensemble
0.026
0.057
20
EDST Ensemble (Ours)
0.031
0,073
MIMO
0.032
0.086
30
DST Ensemble (Ours)
0.035
0.095
Dense Ensemble
0.032
0.086
Figure 2: Left: KL divergence across intermediate feature maps of various sparse ensemble methods. Each line the averaged KL divergence among M = 3 subnetworks. Right: Diversity comparison between sparse ensemble methods and non-sparse ensemble methods with Wide ResNer28-11 10 on CIFAR-10 (M = 3, 5 = 0.8).
7

---

Published as a conference paper at ICLR 2022
To better understand the source of disagreement, apply KL divergence across intermediate feature maps learned by different subnetworks in Figure Left. Each line is the averaged KL divergence among M = 3 subnetworks. It is interesting to observe that the KL divergence is quite high at early layers for the DST Ensemble and the Static Ensemble, which implies that the source their high diversity might locate in the early layers. We further provide disagreement breakdown for the first len classes in CIFAR-100 between different subnetworks in Appendix G The overall breakdown of disagreement very similar the diversity measurement results, i.e., DST Ensemble Static Ensemble > EDST Ensemble >> LTR Ensemble. We share heatmaps of prediction disagreement of DST/EDST ensemble Appendix
5.2 TRAINING TRAJECTORY
In this section, networks discovered by our methods in function space. We save the checkpoints along the training trajectory of each subnetwork and take the softmax output on the test data of each checkpoint to represent the subnetwork's 's prediction. t-SNE maps the prediction to the 2D space. From Figure we can observe that subnetworks of DST Ensemble converge to completely different local optima, and the local optima converged by EDST Ensemble are relatively closer to each other. Interestingly, even the last two subnetworks of EDST Ensemble (blue and green lines) start from similar regions, they end up in two different optima.
t-SNE (Van der Maaten & Hinton 2008)
visualize the diversity of sparse
389
50
Dinessen
Dinersion
Dimumeen
Dimesson
Dimension 1
(emersion
Dimendin
(6) DST on CIEAR- 10
(b) EDST on CIFAR 10
(c) DST on CIFAR 100
(d) EDST on CIFAR 100
Figure 3: t-SNE projection of training trajectories of ensemble learners discovered by DST Ensemble and EDST Ensemble with Wide ResNe128-10 on CIFAR-10/100. The sparsity level is S = 0.8.
5.3 ABLATION STUDY OF PARAMETER EXPLORATION
We conduct an ablation study to analyze the effect of parameter exploration promoting the model diversity. For comparison, we train the same number of subnetworks without any parameter exploration. Shown in Table without parameter exploration, the diversity and the ensemble accuracy consistently decreases, highlighting the effectiveness of parameter exploration on inducing diversity.
Table 5: Ablation study of DST-based Ensemble with and without parameter exploration (M 3, S 0.8).
CIFARIO
CIFARI00
dus
dga (t)
dg (t)
dgL (?)
Acc (?)
Fasemble Parameter Explotation)
96.000
0.081
0.148
81.500
EDST Ensemble
0.031
0.073
96.300
0.128
0.237
82.200
DST Ensemble (wlo Parameter Exploration)
0.079
96,000
DST Ensemble
0.035
0.095
96.300
0.166
0.411
83.300
5.4 EFFECT OF SPARSITY
We further study the effect of subnetworks sparsity on the ensemble performance and diversity, shown in Figure 4 While the individual networks learned by DST Ensemble and EDST Ensemble achieve similar test accuracy, the higher diversity of DST Ensemble boosts its ensemble performance over the EDST Ensemble significantly, highlighting the importance of diversity for ensemble. What's more, it is clear to see that the pattern of the ensemble accuracy is highly correlated with the accuracy of the individual subnetwork. This observation confirms our hypothesis in the introduction, that is, high expressibility is also crucial desideratum for free tickets to guarantee superior ensemble performance. We further support our hypothesis with the Pearson correlation (Pearson 1895) and the Spearman correlation (Powers & Xie. 2008) between the accuracy of individual networks and their ensemble accuracy in Appendix|H
8

---

Published as a conference paper at ICLR 2022
$5.0
65.0
lali but daatt
05.4
652
Scaedi Herger
SCMMO Ohaegenes
Sparkly
Sparaity
Starsiy
Spassiy
(b)
DS) CIFAR-100
(d)
Figure 4: Performance divergence of the subnetworks ensemble of subnetworks as spansity varies. The KI. divergence is scaled to the test accuracy for better visualization.
5.5 EFFECT OF ENSEMBLE SIZE
In this section, we analyze the effect of the ensemble size (the number of ensemble learners) methods. For EDST Ensemble, we fix the total training time and vary the total number of ensemble learners M. The larger ensemble size M leads shorter training time of each ensemble learner. For DST Ensemble, we simply train a different number of individual sparse models from scratch and report the ensemble performance.
The results are shown in Figure 5 "Individ- ual Subnetworks" refers the averaged accu- racy of single subnetworks learned by DST and EDST. The prediction accuracy of DST Ensem- ble keeps increasing the ensemble size in- creases, demonstrating the benefits of ensemble. As expected, the predictive accuracy of individ- ual EDST subnetworks decreases as the ensem- ble size M increases likely due to the insufficient training time of each subnetwork. Nevertheless, the ensemble performance of EDST still quite robust to the ensemble size. Specifically, despite the poor individual performance with M = 7, the ensemble prediction is still higher than sin- gle dense model. This behavior confirms our hypothesis mentioned before, i.e., multiple free tickets work better than one high-quality winning ticket or even dense network.
95.75
06.77 75
EDST Ensemble
Indlv Suznebecrics
796.25
Z 26:22
96.000
96.00
90.75
93.75
95.50
03.30
DST Ensemble
92.23
Indiodual Subnewwads
95.00
3
95.00
DST Ensemble
EDST Ensemble
Figure 5: Performance the subnetworks and the en- semble of subnetworks as the ensemble size M varies (Wide ResNet28-10 CIFAR-10).
5.6 EXPERIMENTS WITH OOD AND ADVERSARIAL ROBUSTNESS
We further test the performance of Free'Tiickets on out-of didtistrinttion (OoD) detection and adver- sarial robustness, reporting the results in Appendices K and L methods also bring benefits to OoD performance and adversarial robustness.
respectively. Our proposed ensemble
6 CONCLUSION AND FUTURE WORKS
We introduce FreeTickets, an efficient way boost the performance of sparse training over the dense network, even the dense ensemble. FreeTickets is built as a combination of the diverse subnetworks extracted during dynamic sparse training and achieves a co-win in terms of accuracy, robustness, uncertainty estimation, as well as training/inference efficiency. We demonstrate for the first time that DST methods may not match the performance of dense training when standalone, but surpass the generalization of dense solutions (including the dense ensemble) an ensemble, while still being more efficient to train than a single dense network.
The aforementioned compelling efficiency has not been fully explored, due to the limited support of the commonly used hardware. Fortunately, some prior works have successfully demonstrated the promising speedup of sparse networks real mobile processors (Elsen et al. 2020), GPUs (Gale et al., 2020), and CPUs (Liu et al., 2020a). In future work, we are interested to explore sparse ensembles hardware platforms for real speedups in practice.

---

Published as a conference paper at ICLR 2022
7 REPRODUCIBILITY
The training configurations and hyperparameterss used in this paper shared in Appendix The metrics used to enable comparisons among different methods are given in Appendix D released our source code at httt:s///sstaaaa.cccc////ttttttt
We have
ACKNOWLEDGEMENT
We would like to thank Bram Grooten for giving feedback on the camera-ready version; the profes- sional and conscientious reviewers of ICLR for providing valuable comments. Z. Wang is in part supported by the NSF Al Institute for Foundations of Machine Learning (IFML).
REFERENCES
Zahra Atashgahi, Ghada Sokar, Tim van der Lee, Elena Mocanu, Decebal Constantin Mocanu, Raymond Veldhuis, and Mykola Pechenizkiy. Quick and robust feature selection: the strength of energy-efficient sparse training for autoencoders. Machine Learning, pp. 1-38, 2021.
Maximilian Augustin, Alexander Meinke, and Matthias Hein. Adversarial robustness on in-and out- distribution improves explainability. In European Conference on Computer Vision, pp. 228 245. Springer, 2020.
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:://ppeneete
net Forummid=daa (oorum?dd=BJ_NNOL
Sameer Bibikar, Haris Vikalo, Zhangyang Wang, and Xiaohan Chen. Federated dynamic sparse training: Computing less, communicating less, yet learning better. Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI), 2022.
Leo Breiman. Bagging predictors. Machine learning, (62)):23-140, 1996.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben- jamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot leamers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL httpt:://///mm httt:s::/proceeeingss neurips cc 2t//ppppe//222////1/144//5/00000 ottp://ccccc.aoooo........a.1..1
Paperr pdf
Tianlong Chen, Yu Cheng, Zhe Gan, Lu Yuan, Lei Zhang, and Zhangyang Wang. Chasing sparsity in vision transformers: An end-to-end exploration. Advances in Neural Information Processing Systems, 34, 2021a.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and superviee pre-training in computer vision models. In Proceedings of the IEEE/CVF Conference on Computer Vision and 2021b.
Pattern Recognition, pp.
Tim Dettmers and Luke Zettlemoyer Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv: 107.::1977.044400 2019.
Anastasia Dietrich, Frithjof Gressmann, Douglas Orr, Ivan Chelombiev, Daniel Justus, and Carlo Luschi. Towards structured dynamic sparse pre-training of bert, 2021.
Thomas G. Dietterich. Ensemble methods in machine learning. In Multiple Classifier Systems, 2000.
10

---

Published as a conference paper at ICLR 2022
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL httpps://pperrevieee
Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets. In Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pp. 14629-14638, 2020.
Paul Erdós and Alfréd Rényi. On random graphs i. Publicationes Mathematicae (Debrecen), 6: 290-297, 1959.
Utku Evei, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint arXiv: /906. 10732,
Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2955 PMLR, 2020a.
Utku Evci, Yani Ioannou, Cem Keskin, and Yann Dauphin. Gradient flow in sparse neural networks and how lottery tickets win. arXiv preprint arXiv:2010.03533, 2020b.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Advances in Neural Information Processing Systems., 2021.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape perspec- tive. arXiv preprint arXiv:1912.02755. 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning. pp. 3259-3269. PMLR, 2020.
Tommaso Furlanello, Zachary Lipton, Michael Tschannen, Laurent Itti, and Anima Anandkumar. Born again neural networks. In International Conference on Machine Learning, pp. 1607-1616. PMLR, 2018.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty deep learning. In international conference on machine learning, pp. 1050-1059. PMLR, 2016.
Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv: 190740957.. 2019.
Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen. Sparse gpu kernels for deep learning. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14. IEEE, 2020.
Eva Gareía-Martín, Crefeda Faviola Rodrigues, Graham Riley, and Håkan Grahn. Estimation of energy consumption machine learning. Journal of Parallel and Distributed Computing, 134: 75-88,22 2019.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry Vetrov, and Andrew Gordon Wilson. Loss surfaces. mode connectivity, and fast ensembling of dnns. In Proceedings of the 32nd International Conference on Neural Information Processing Systems. pp.
2018.
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points oolienooooeeeeeeee stochastic gradient for tensor decomposition. Conference on learning theory, pp. 797-842. PMLR, 2015.
Fredrik K Gustafsson, Martin Danelljan, and Thomas B Schon. Evaluating scalable bayesian deep learning methods for robust computer vision. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 318-319, 2020.
11

---

Published as a conference paper at ICLR 2022
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, pp. 1135-1143, 2015.
Lars Kai Hansen and Peter Salamon. Neural network ensembles. IEEE transactions pattern analysis and machine intelligence, 12(100993-1101, 1990.
Marton Havasi, Rodolphe Jenatton, Stanislav Fort, Jeremiah Zhe Liu, Jasper Snoek, Balaji Lak- shminarayanan, Andrew Mingho Dai, and Dustin Tran. Training independent subnetworks for robust prediction. In International Conference on Learning Representations, 2021. URL
https: ptttps://cpenreviee net htt.pp/nweeeeeeeeeeeooorrrreddde
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In Proceedings of the IEFE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf. Why relu networks yield high- confidence predictions far away from the training data and how to mitigate the problem. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pp. 41-50, 2019.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness common corruptions and perturbations. arXiv preprint
2019.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. arXiv preprint arXiv:/907.077 174, 2019.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint 1rX3v:150.002533 2015.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241):1-122 2021.
Gao Huang, Yixuan Li, Gcoff Pleiss, Zhuang Liu, John E Hopcroft, and Kilian Q Weinberger. Snapshot ensembles: Train get for free. arXiv preprint
2017.
Tiansheng Huang, Shiwei Liu, Li Shen, Fengxiang He, Weiwei Lin, and Dacheng Tao. On heteroge- neously distributed data, sparsity matters, 2022. URL bttps::/ppeneeiie..nttt.t wew.:/wwwwee..to...eeeeeeeeeee
Ed-ATOX-S23QGs
Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Advances Neural Information Processing Systems, 33, 2020.
Nal Kalchbrenner, Erich Elsen, Karen Simonyan, Seb Noury, Norman Casagrande, Edward Lockhart, Florian Stimberg, Aaron Oord, Sander Dieleman, and Koray Kavukcuoglu. Efficient neural audio synthesis. In International Conference on Machine Learning, pp. 2410-2419. PMLR, 2018
Kenji Kawaguchi. Deep learning without poor local minima. D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, vol- ume 29. Curran Associates, Inc., 2016. URL pattps://procest Paper.pd. 727711445400 wweeeeaaaaaaaaaeee.
neurig.neuriss.. cc/
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: arXiv: 12446696,, 2014.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathemati- cal statistics, 22(1):79-55) 1951.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2022
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity, In International Conference on Learning Representations, 2019. URL
httts://cpenrevaie nnt/ Forumrri----V-V22AcAAA.
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.
Stefan Lee, Senthil Purushwalkam, Michael Cogswell, David Crandall, and Dhruv Batra. Why m heads are better than one: Training a diverse ensemble of deep networks. arXiv preprint arXiv:1511.0631 2015.
Esther Levin, Naftali Tishby, and Sara Solla. A statistical approach to learning and generalization in layered neural networks. Proceedings of the IEEE, 78(10):1568-1555 1990.
Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with one million artificial neurons on commodity hardware. Neural Computing and Applications, 2020a.
Shiwei Liu, Tim Van der Lee, Anil Yaman, Zahra Atashgahi, Davide Ferraro, Ghada Sokar, Mykola Pechenizkiy, and Decebal Constantin Mocanu. Topological insights into sparse neural networks. In ECMLPKDD, 2020b.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse training via boosting pruning plasticity with neuroregeneration. Advances in Neural Information Processing Systems, 34, 2021a.
Shiwei Liu, Decebal Constantin Mocanu, Yulong Pei, and Mykola Pechenizkiy. Selfish sparse rnn training. In Proceedings of the 39th International Conference Machine Learning, pp. 6893-6904. PMLR, 2021b.
Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do we actually need dense wve-pparameterization?? in-time over-parameterizzaion in sparse training. In Proceedings of the 39th International Conference on Machine Learning, pp. 6989-7000. PMLR, 2021c
Alexander Meinke and Matthias Hein. Towards neural networks that provably know when they don't know. arXiv preprint arXiv: /909. 12180, 2019.
Decebal Constantin Mocanu, Elena Mocanu, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta, A topological insight into restricted boltzmann machines. Machine Learning, 104(2-3): 243-270, 2016.
Decebal Constantin Mocanu, Flena 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()):2383, 2018.
Decebal Constantin Mocanu, Elena Mocanu, Tiago Pinto, Selima Curci, Phuong H Nguyen, Madeleine Gibescu, Damien Ernst, and Zita A Vale. Sparse training theory for scalable and efficient agents. International Conference on Autonomous Agents and Multiagent Systems (AA- MAS), arXiv:2103.0160 2021.
Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference on Machine Learning, 2019.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated prob- abilities using bayesian binning. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
13

---

Published as a conference paper at ICLR 2022
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URL http: stanford...o..oo edu/
housenumbers/nii hoops//sssmppp11ooooooooeeeeerr
Johannes Von Oswald, Seijin Kobayashi, Joao Sacramento, Alexander Meulemans, Christian Hen- ning, and Benjamin F Grewe. Neural networks with late-phase weights. In International Confer- ence on Learning Representations, 2021. URL https:://ppenreeeeee http:/ewwweee.ttteeeeeeeeeo COqJUx5dxPb
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, D. Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evalu- ating predictive uncertainty under dataset shift.
Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019a. URL httptpppppppppccccassss.s... neuripss......s.ssp.pp........ss cc/
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua V Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint arXiv: 1906.02300, 2019b.
Ozan Özdenizei and Robert Legenstein. Training adversarially robust sparse networks via bayesian connectivity sampling. In International Conference on Machine Learming, pp. 8314-8324. PMLR, 2021.
K Pearson. Notes on regression and inheritance in the case of two parents proceedings of the royal society of london, 58, 240-242, 1895.
Michael P Perrone and Leon N Cooper. When networks disagree: Ensemble methods for hybrid neural networks. Technical report, BROWN UNIV PROVIDENCE RI INST FOR BRAIN AND NEURAL SYSTEMS, 1992.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- fional mathematics and mathematical physics, 4(5):1-17, 1964.
Daniel Powers and Yu Xie. Statistical methods for categorical data analysis. Emerald Group Publishing. 2008
Ilan Price and Jared Tanner. Dense for the price of sparse: Improved performance of sparsely initialized networks via a subspace offset. arXiv preprint arXivv2102.00655, 2021.
Joaquin Muinonero-Candell Carl Edward Rasmussen, Fabian Sinz, Olivier Bousquet, and Bern- hard Schölkopf. Evaluating predictive uncertainty challenge. In Machine Learning Challenges Workshop, pp. 1-27. Springer, 2005.
arXiv preprint Md Aamir Raihan and Tor M Aamodt. Sparse weight activation training. arXiv:2001.01969, 2020.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Roy Schwartz, Jesse Dodge, Noah A Smith, and Oren Etzioni. Green ai. arXiv preprint arXiv:1907.10597, 2019.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint 1rXiv:1701.066. 06538, 2017.
Ghada Sokar, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Spacenet: Make free space for continual learning. Neurocomputing, 439:1-11, 2021.
Thilo Strauss, Markus Hanselmann, Andrej Junginger, and Holger Ulmer. Ensemble methods defense to adversarial perturbations against deep neural networks. arXiv preprint ww..:v:000.033... 2017.
14

---

Published as a conference paper at ICLR 2022
Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in nlp. arXiv preprint
2019.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147. PMLR, 2013.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 2013.
Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems 33 pre-proceedings, 2020.
Kale-ab Tessera, Sara Hooker, and Benjamin Rosman. Keep the gradients flowing: Using gradient flow study sparse network optimization. arXiv preprint arXiv:2102.01670, 2021.
Hugo Touvron, Andrea Vedaldi, Matthijs Douze, and Hervé Jégou. Fixing the train-test resolution discrepancy: Fixefficientnet. arXiv preprint arXiv:2003.082.3 2020.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference Machine Learning, pp. 10347-10357. PMLR, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using I-sne. Journal of machine learning research, 9(11), 2008.
Chaoqi Wang, Guodong Zhang, and Roger Grosse Picking winning tickets before training by preserving gradient flow. International Conference on Learning Representations, 2020. URL
https::/ [ttp:p///.eeeeeeeeeeee.sss/sssss
net forum?id-SkssscccE.
Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba. Interplay between optimization and generalization of stochastic gradient descent with covariance noise. arXiv preprint 1902.08.4 2019.
Yeming Wen, Dustin Tran, and Jimmy Ba. Batchensemble: an alternative approach efficient ensemble and lifelong learning. In International Conference on Learning Representations, 2020.
URL /tttttsss//ppeeeeeeeeee
net / forum? id=SkkffyyyDDrr
Florian Wenzel, Jasper Snoek, Dustin Tran, and Rodolphe Jenatton. Hyperparameter ensembles for robustness and uncertainty quantification. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 6514-6527 Curran Associates, Inc., 2020. URL http:httt//sttt http:s://ppcceeeinggg http:/eeeddiinn....ineeeeeee cc/ http:://..2...aaaa..aaaaaaaaaaa2
pdd
Jingjing Xie, Bing Xu, and Chuang Zhang. Horizontal and vertical ensemble with deep representation for classification. CoRR, abs/1306.2759, 2013.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. 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. ISBN 1-901725-59-6, doi: 10.5244/C. 30.87. URL http::ttp:///t http::::/oox..0.....c//.///2///2
doi org/10. 0244//....244442
Hangyu Zhu and Yaochu Jin. Multi-objective evouuutto federated learning. IEEE transactions on neural networks and learning systems, 31(4): 2019.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. Xrxiv preprint 171.0.1710.0187,, 2017.
15

---

Published as a conference paper at ICLR 2022
A DYNAMIC SPARSE TRAINING
In this Appendix, describe the full details of dynamic sparse training. See the survey of Mocanu et al. (021) and (Hoefler et al. 2021 for more details.
A.1 ALGORITHM
Dynamic Sparse Training (DST) (Mocanu al. 2018 Liu et al. 2020a) is class of methods that enable the end-to-end training of sparse neural networks. DST starts from a sparse network and simultaneously optimizes the sparse connectivity and model weights during training. Without loss of generality, we provide the general pseudocode of DST that can cover most of the existing DST methods Algorithm
While there is an upsurge in increasingly efficient ways for sparse training (Bellec et al. 2018 Mostafa Wang 2019 Dettmers & Zettlemoyer 2019 Evei et al., [2000a] Liu al. 2021b Jayakumar et 2020 Liu et al. 2021c] Dietrich et al. | Chen et al. (021a). most of DST methods contain three
key components: sparse initialization, model weight optimization, and parameter exploration. We
explain them below.
Algorithm 1 Dynamic Sparse Training
Require: Network fe. dataset (#,, 91 W Layer-wise sparsity ratio: S, Update Interval AT, Explo-
ration Rate p
1: # Sparse Initialization
2: f(;;0, t fx; 0:
3: for each training step t do
4: # Model Weight Optimization
5: f(x; 0.) + (Gr 0x))
6: if (t mod AT) = then
7:
# Parameter Exploration
Pruning p percentage of parameters using Eq, Growing p percentage of parameters using Eq. 10: Update exploration rate p
8:
9:
end if
12: end for
A.1.1 SPARSE INITIALIZATION
Layer-wise Sparsity Ratio. Layer-wise sparsity ratio plays an important role for sparse training. Mocanu al. (2018) first introduced Erdös-Rényi (ER) (Erdös & Rényi 1959) from graph theory to the field of neural networks, achieving better performance than the uniform sparsity ratio. [Eeci al.) (2020a) further extended ER to CNN and brings significant gains sparse CNN training with the Erdös-Reds Benids-Rénni-Kernee (ERK) ratio. Specifically, the sparsity level of layer / is scaled with
1 n 4n'' -.t-1xxx xxx Xxx X where ne' refers to the number of neurons/channels of layer 1; wt and h are the width and the height of layer 1. Works with weight redistribution (Mostafa & Wang 2019 Dettmers & Zettlemoyer 2019 Liu et al., (2021b) start with the uniform layer-wise ratio and dynamically change the layer-wise ratio according heuristic criteria, ending up with non-uniform layer-wise ratios.
Weight Initialization. Weight initialization also affects the performance of sparse training. Unlike the dense network, sparse networks contain a partial of weights be zero, breaking the appealing properties of dense initialization such as dynamical isometry (Lee et al. 2020), gradient flow (Evci
al.
20206
Tessera al. 202T), etc.
A.1.2 MODEL. WRIGHT OPTIMIZATION
After initializing the sparse model, need to optimize the model weights minimize the loss function. In general, dynamic sparse training is compatible with the most widely used optimizers, e.g., minibatch stochastic gradient descent (SGD) (Robbins & Monro 195T), minibatch stochastic
16

---

Published as a conference paper at ICLR 2022
gradient descent with momentum (Sutskever et al. 2014).
2013 Polyak 1964). and Adam Kingma & Ba
However, need pay extra attention to average- based optimizers, such Averaged Stochastic Gradient Descent (ASGD), which is widely used in the language modeling tasks with RNNs and LSTMs. Liu et al. 2021b) points out that ASGD seriously destroys the sparse connectivity opti- mization since the average operation brings the newly-grown weights immediately to zero, leading over-pruning situation. Moreover, TTssera et al. (2021) shows that optimizers that use an exponentially weighted moving average (EWMA) are sensitive to high gradient flow.
A.1.3 PARAMETER EXPLORATION
Dynamic sparse training outperforms static sparse training mainly due to the parameter explo- ration (Liu et al. 2021c). One simple yet effective heuristic used here is prune-and-grow. Removing p percentage of the existing weights and regrowing the same number of new weights allows DST to gradual optimize the sparse connectivity in heuristic way.
Although there exists various pruning criteria in pruning literature, the most common way for DST the simple magnitude pruning. We also tried other criteria for pruning initialization e.g., SNIP (Lee et al., 2019). GraSP (Wang et al., 2020), SynFlow (Tanaka et al. 2020). All of them fall short of the accuracy achieved by magnitude pruning.
Weight Prune:
The most common ways to grow new weights are random- based growth (proposed in SET (Mocanu et al.) 2018) and gradient-based growth (proposed in RigL (Evei et al., 2020a) and SNFS (Dettmers & Zettlemoyer 2019)). Random- -baned growth ensures purely sparse forward pass and backward pass, while very likely needs more steps to find the important connections, especially for the very extreme sparsities. Gradient-based growth detects the weights that reduce the current loss the fastest, whereas it involves the dense gradient calculation and is likely to cause a collapse of the explored parameter space (Liu et al. 2021b Dietrich et al. (02I).
Weight Grow:
is worth noting that the choice of when-to-explore is also importance for DST. The number of training iterations between two parameter explorations is controlled by the update interval AT. Since the newly-grow weights are initialized to zero, large AT is necessary to guarantee that the new weights receive enough weight updates to survive at the next pruning iteration (Liu et al. 2021c).
17

---

Published as a conference paper at ICLR 2022
B PSEUDOCODE OF DST ENSEMBLE AND EDST ENSEMBLE
Algorithm 2 DST Ensemble
Require: network fe. dataset {., Vi N ensemble size M, sparsity distribution S, update interval AT, DST exploration rate p, training time of each free ticket T.
1: for j 1 to M do
2: # Sparse Initialization
f(x; 0% < f(:00';3
4: for = 1 to 7" do
5:
# Model Weight Optimization
6:
[(e; 0%) - (G;
7:
if (t mod AT) = 0 then
8:
DST Parameter Exploration
9:
DST parameter exploration using Eq. 1& & 2 with p
Update exploration rate
11: end if
12: end for
13: Save the converged sparse subnetwork f(z; 02)
14: end for
Algorithm 3 EDST Ensemble
Require: network fe. dataset {a,, yi N
i=1 ensemble size M, sparsity distribution: S, update interval AT, DST exploration rate global exploration rate g, training time of the exploration phase lea: training time of each refinement phase Lre/
1: # Sparse Initialization
2: f(;; 0.) + f( 0:
3: # One Exploration Phase
4: for = to fez do
5: f(x;;
(G:(f(#;;)) 0.))
6: if (t mod AT) = 0 then
7: DST parameter exploration using Eq. & with p
8: end if
9: end for
10: # M Sequential Refinement Phases
for j = M do
12: for = to tre / do
13:
f(x; 03) + SGD(f(x; (t mod AT) = 0 then
14:
15:
DST parameter exploration using Eq. [ with p 16: end if
17:
end for
18: Save f(x; 02) and escape by parameter exploration using Eq.
& with
end for
18

---

Published as a conference paper at ICLR 2022
C IMPLEMENTATION AND HYPERPARAMETERS
In this Appendix, we provide the hyperparameters used in Section 4
We mentioned in the main content of paper that these free tickets (subnetworks) are non-trivial to obtain due to the three key desiderata. To confirm this, we implement and test two paarity--based efficient ensemble methods, Static Sparse Ensemble and Lottery Ticket Hypothesis (LTR) Ensemble.
Static Sparse Ensemble Static Sparse Ensemble refers to directly training M sparse subnetworks from scratch and ensemble them for test. Even though it naturally satisfies the low training cost and high diversity, its insufficient accuracy leads to worse performance than the proposed DST/EDST Ensemble.
gradual magnitude pruning (GMP) ZZhu & Gupta 2017] Gale et al.] 2019) for LTR, which is a well studied and more efficient pruning method than iterative magnitude pruning (IMP). Concretely, we first use gradual magnitude pruning to prune the dense network to the target sparsity. After that, we retrain and rewind the subnetworks to the 5 5% epoch for M times. The converged subnetworks are further used for ensemble. Note that even GMP is much more efficient than IMP, the overall training FLOPs required by this method is much higher than directly training a single dense model. We expect that using IMP for Ensemble can be more accurate, but also leads to prohibitive training costs, in contrary to our pursuit of efficient ensemble.
LTR Ensemble Following Evei et al. 2020b),
PF Ensemble For the pruning baseline, we choose the strong techniques - global magnitude pruning. We first prune three independently pre-trained dense networks (each is trained for 250 epochs) to the target sparsity, and then fine-tune them for another 250 epochs with different random seeds. We believe this setting can provide enough diversity as all the training procedures independent, with different random seeds.
Hyperparameters of DST Ensemble For a fair comparison, we follow the training configuration of MIMO. For Wide ResNer28-10 10 on CIFAR, we train the sparse model for 250 epochs with learning rate of 0.1 decayed by 10. We use a batch size of 128, weight decay of 5e-4. To achieve good tradc-off between ensemble accuracy and sparsity, the hyperparameters of DST, we choose a large update interval AT = 1000 between two sparse connectivity updates and a constant DST exploration rate p p= 0.5.
set sparsity S 0.8. Regarding
For ResNet-50 on ImageNet, to the best of our knowledge, all the state-of- of-the--rtttt DST approaches can not match the performance of the dense ResNet-50 on ImageNet within standard training time. To guarantee sufficient predictive accuracy for the individual ensemble learners, we follow the training setups used in Liu al. (2021c) and train each sparse ResNet-50 for 200 epochs with batch size of 64. The learning rate is linearly increased to 0.1 with a warm-up in the first 5 epochs and decreased by a factor of 10 at epochs 60, 120, and 180. Even with a longer training time, it takes much fewer FLOPs to train sparse networks using DST compared to the dense network. We choose AT = 4000 and a cosine annealing schedule for the exploration rate with an initial value p = 0.5.
Hyperparameters of EDST Ensemble For Wide ResNer28- 10 on CIFAR, we train the 80% sparse model for 450 epochs and 90% sparse model for 850 epochs with tex = 150, tre = 100, so that we can get M- = 3 subnetworks with sparsity of 0.8 and M = 7 subnetworks with sparsity of 0.9 for ensemble. The numbers of training FLOPs of this two settings are similar due to the different sparsity levels. The DST exploration rate is chosen p- 0.5 which achieves the best performance as shown in (Evci et al. [2200a] Liu et al. 2021ch. To encourage a large diversity between ensemble learners, we use large global exploration rate g = 0.8 force the subnetowrk escape the current basin. We have also tested a larger exploration rate, i.e., g = 0.9. The results are similar with q = 0.8.
For ResNet-50 on ImageNet, we set tex 30 and tre 70 so that we can obtain M = 2 subnetworks with 170 epochs and M = 4 subnetworks with 310 epochs, respectively. We set p = 0.5 and q = 0.8. The rest of hyperparameters are the same as DST Ensemble. Due the limited resources, we only test the 80% sparsity for ResNet-50. We believe that the ensemble performance can further improve with lower sparsity.
19

---

Published as a conference paper at ICLR 2022
D EXPERIMENTAL METRICS
To measure the predictive accuracy and robustness, we follow the Uncertainty Baseline and focus on test accuracy (Acc), negative log-likelihood (NLL), and expected calibration error (ECE) on the i..d. test set, corrupted test sets (i.e., CIFAR-IO-C and ImageNet-C) (Hendrycks & Dietterich 2019) which contain 19 natural corruptions such as added blur, compression artifacts, frost effects, etc, as well as on the natural adversarial samples (i.e., ImageNet-A) (Hendrycks et al.) (2019). We adopt (cAce, cNLL,, cECE} and (aAce, aNI.L, a to denote the corresponding metrics on corrupted test sets and natural adversarial samples, respectively.
Negative log- log-likelihood (NLL) a proper scoring rule and popular metric for evaluating predictive uncertainty (Quinonero-Canded Candela et al. 2005).
Expected Calibration Error (ECE) (Naeini al. 2015), widely adopted metric to approximate the difference in expectation between confidence and accuracy of machine learning models (i.e., miscalibration). Specifically, partitions predictions into M equally-spaced bins, and then calculates weighted average of the accuracy/confidence discrepancy in each of these bins. Larger ECE values represent a worse match between confidence and accuracy.
To compare the computational efficiency, report the training FLOPs required to obtain the targeted number of subnetworks for all methods and normalize them with the FLOPs required by a dense model. Following Rigl (Evei al. (2200a), the FLOPs are calculated with the total number of multiplications and additions layer by layer. Briefly speaking, with ERK distribution, the training FLOPS of sparse Wide ResNer28-10 10 at sparsity S 0.8 and S 0.9 are 33.7% and 16.7% of the dense model, respectively. For sparse ResNet-50 at S = 0.8, the required training FLOPS is 42% of the dense model. We omit the additional computational cost for the extra inputs and the extra outputs of MIMO, as is negligible compared with the whole training FLOPs. Moreover, we suppose the hardware can fully utilize large batch size so that Batchen incurs almost no additional computational overhead and memory cost.
E COMPARISON WITH SNAPSHOT AND FGE
In this Appendix, we compare our methods with the ensemble methods that use cyclical learn- ing rate schedules to discover diverse dense networks, i.e., Snapshot (Huang et al., 2017) and FGE (Garipov et al. 2018). For relatively fair comparison, we compare our methods with their "IB' versions (Garipov et al. 2018) which have similar training FLOPs with our methods. However, their test FLOPs would be much larger their ensemble members dense networks. As shown in Table 6 while achieving relatively similar performance, Snapshot and FGE require significantly more test FLOPs than the DST-based ensemble methods.
Table Comparison between DST-based ensemble methods with Snapshot (Huang et al. 2017 and FGE Caripov et al. 2018). The experiments are conducted with Wide ResNet28-10 on CIFAR- 10/
Methods
Sparsity
# Taiining FLOPS (U)
FLOPs (1)
# Text
CIFAR-10(())
Acc
Aoc CIPAR-100
Snapshot (M 12)
U
D.8Ux
12.00x
96.227
82.10
PGE (M 5)
0.80x
5.00%
96.35
82.30
(Oun)
EUST Ensemble (M 3) (Oun)
0.8
0.61x
1.01x x
96.30
82.20
DST Ensemble (M 3) (Our))
0.8
1.01x
1.01x
96.30
83.30
'More details can be found in the official repository of Rigl. https: httpg/ggtthh.oooo gogg
20

---

Published as a conference paper at ICLR 2022
F PREDICTION DISAGREEMENT ON CIFAR-10/100
We compare the prediction disagreement among the naive dense ensemble, DST Ensemble with sparsity S 0.8, EDST Ensemble with sparsity S 0.8 and S 0.9. The comparison results on CIFAR-10 and CIFAR-I00 are shown in Figure 6 and Figure 7 respectively. We find that the subnetworks discovered by DST Ensemble are even more diverse than the ones discovered by the traditional dense ensemble, confirming our hypothesis that dynamic sparsity can provide extra diversity addition random initializations. While the average functional diversity of the subnetworks discovered by EDST Ensemble is a bit lower compared with DST Ensemble, the diversity still notable. Moreover, as expected, a higher sparsity S 0.9, the prediction diversity EDST Ensemble slowly rises the ensemble size M increases, and ends up with similar diversity the Dense Ensemble.
0213
RPM
0.035
4.005
4.00
2200
A.65
0.065
6445
6005
3.00
(a) Dense Ensemble
(b) DST Ensemble (S=0.8)
(c) EDST Ensemble (S=0.8)
(d) EDST Ensemble (S=0.9)
Figure 6: Prediction disagreement between ensemble learners with Wide ResNet28-100 10 on CIFAR-10, Each subfigure shows the fraction of labels on which the predictions from different ensemble learners disagrec.
034
6:0
0.00
6.10
606
6.0
6.4
6/8
6/0
(a) Dense Ensemble
(b) DST Ensemble (S=0.8) (c) EDST Ensemble (S=0.8) (d) EDST Ensemble (S=0.9)
Figure 7: Prediction disagreement between ensemble learners with Wide ResNet28-10 CIFAR-100. Each subfigure shows the fraction of labels on which different ensemble learners disagree.
21

---

Published as a conference paper at ICLR 2022
G DISAGREEMENT BREAKDOWN BETWEEN VARIOUS SPARSE NETWORK ENSEMBLES ON CIFAR-100
In this Appendix, try provide detailed illustration about various classes that the disagreement between various sparse network ensembles. We choose the first 10 classes CIFAR- 100 and measure the disagreement between the subnetworks learned by the same method on these classes. The results are shared in Table 7 The overall breakdown of disagreement is very similar to the diversity measurement results, i.e., DST Ensemble > Static Ensemble EDST Ensemble LTR Ensemble. The prediction on classes like Fish, Baby, and Bear have higher diversity than Apple and Beetle.
Table 7: Disagreement Breakdown of various sparse network ensembles, including LTR Ensemble, Static Ensemble, EDST Ensemble, and DST Ensemble, on CIFAR-I00
Class
Apple
Aquarium
Fish
Baby
Bear
Beaver
Bed
Bec
Beetle
Bicycle
LTR Ensemble 0.027
0.063
0.140
0.170
0.157
0.070
0.127
0.110
0.027
0.030
EDST Ensemble
0.043
0.067
0.153
0.187
0.137
0.090
0.107
0.080
0.027
0.067
Static Ensemble
0.077
0.090
0.220
0.180
0.227
0.157
0.120
0.097
0.047
0.073
DST Ensemble
0.057
0.080
0.227
0.277
0.230
0.137
0.160
0.133
0.053
0.093
H CORRELATION MEASUREMENT BETWEEN THE ACCURACY OF SUBNETWORKS AND THEIR ENSEMBLE ACCURACY
In the main paper, we hypothesize that high expressibility is crucial desideratum for FreeTickets to guarantee superior ensemble performance. Here, we apply two widely used correlation measurements, Pearson correlation (Pearson 1895) and Spearman correlation (Powers & Xie 2008), to support our hypothesis. We use these two methods to measure the correlation between the mean accuracy of individual networks and the accuracy of their ensemble (higher values refer to higher correlation). The results are shared in Table & We find that the individual accuracy and the ensemble accuracy are very highly correlated on CIFAR- 1-0. Their correlation is relatively low on CIFAR-10 likely due to the almost saturated accuracy of the individual subnetwork (96%). Given such high accuracy, even the usually clear and strong correlation between the sparsity and test accuracy becomes relatively vague on CIFAR-10 Figure fa a and Figure 4b.
Table Correlation between mean accuracy of individual networks and accuracy of their ensemble.
Methods
Wide ResNae28-10CCIFAR100
Wide ResNer28-10/CIFAR 100
Pearson Correlation
Spearman Correlation
Pearson Correlation
Spearman Correlation
EDST Ensemble
0.459
0.257
0.979
DST Ensemble
0.332
0.319
0.972
0.812
22

---

Published as a conference paper at ICLR 2022
1 EFFECT OF THE GLOBAL EXPLORATION RATE ON EDST ENSEMBLE
Intuitively, a larger global exploration rate g leads to larger sparse connectivity diversity whereas large g would prune the important connections, hurting the ensemble accuracy. We perform sensitivity study with EDST Ensemble in Table [ whose results are in line with our conjecture. A large global exploration rate q = 0.8 promote higher diversity but degrades the ensemble accuracy bit compared with 0.5. q = 0.5 seems to achieve the best ensemble performance.
Table 9: Effect of Exploration Rate g on EDST Ensemble. "Acc" refers to the ensemble accuracy.
Wide ResNe128 1CCIFARIO
Wide ResNei28 10CIFARIO0
Different choices of
(1)
dKL
Acc
dais (?)
dKL
Acc (t)
0.1
0.028
0.070
96.2
0.109
0.217
82.14
q 0.5
0.031
96.3
0.125
9 0.8
0.033
0.073
96.3
0.127
0.237
82.20
J EFFECT OF REGROWTH METHODS ON EDST ENSEMBLE
Random regrowth naturally considers a larger range of parameters to explore compared the gradient regrowth as used in the main paper. We added below a small set of experiments to study different growth criteria (random gradients) the EDST Ensemble. As shown in Table 10 it seems that random growth may provide more diversity and better performance for more complex datasets (i.e., CIFAR-100, but more studies necessary understand the phenomenon better.
Table 10: Effect of regrowth methods EDST Ensemble. We compare gradient regrowth and random regrowth. "Individual Acc" refers the averaged test accuracy of subnetworks discovered by different ensemble methods "Ace" refers to the ensemble accuracy.
Wilk RoNNee88 10CIFAR
Methods
Individual Ace
6a.
(t)
Ato(t)
Individaal
des (1)
dgc,,(1)
(co(1)
Random growth
85 64
0.031
0.72
96.2
81.01
0.129
0.231
K2.4
Gradieni gonnc
95.
0.01
0073
96.3
81.09
0.126
0.235
81.2
23

---

Published as a conference paper at ICLR 2022
K EXPERIMENTS WITH OOD RESULTS
In this section, we report the performance of OoD detection for single sparse networks and ensemble models. Specifically, we use datasets that
seen during training time for OoD evaluation.
Following the classic routines (Augustin et al., 2020 Meinke & Hein 2019). SVHN (Netzer et al.
2011h. CIFAR- (Krizhevsky & Hinton ) and CIFAR-I0 with random Gaussian noise (Hein et al. 2019) are adopted for models trained on CIFAR-10 (Krizhevsky & Hinton 2009); SVHN, CIFAR-10, and CIFAR-100 with random Gaussian noise are used for models trained on CIFAR-100. The ROC-AUC performance (Augustin et al. 2020 Meinke & Hein 2019) are reported over the respective out of distribution datasets, as shown Table [T and Table 12 As we expected, our proposed ensemble methods provide gains to the OoD performance. DST Ensemble and EDST Ensemble can even surpass the dense models by a clear margin in most cases.
Table 11: The ROC-AUC OoD performance Wide ResNet-28-11 trained on CIFAR-10.
OOD dataset for CIFAR- 10 trained models
Methods
SVHN
CIFAR-100
Gaussian Noise
Static Spurse Ensemble (M
0.8)
0.8896
0.8939
0.9559
Static Spurse Ensemble (M
0.8)
0.9229
0,9082
0.9910
DST Ensemble (M () 0.8)
0.9082
0.8957
0.9964
DST Ensemble (M 3) ($ 0.8)
0.9533
0.9114
0.9969
EDST Ensemble (M [) 0.8)
0.9461
0.8895
0.9607
EDST Ensemble (M (S 0.8)
0.9487
0,9045
0,9928
EDST Ensemble (M 1) 0.9)
0.9439
0,8955
0,9817
EDST Ensemble (M 7) (S 0.9)
0.9658
0.9115
0,9956
Single Dense Models
0.9655
0.8847
0.9803
Table 12: The ROC-AUC OoD performance for Wide ResNet-28-11 trained on CIFAR- 100.
OOD dataset for CIFAR- 100 trained models
Methods
SVHN
CIFAR-10
Gaussian Noise
Static Sparse Ensemble (M (S 0.8)
0.7667
0,8004
0.7858
Static Sparse Ensemble (M = 3) 0.8)
0.8165
0,8141
0,9560
DST Ensemble (M
0.8)
0.8284
0.8019
0,8131
DST Ensemble (M
0.8207
0.8221
0,8865
EDST Ensemble (M () 0.8)
0.7481
0.7941
0,8736
EDST Ensemble (M 3) (S 0.8)
0.8585
0.8137
0,9046
EDST Ensemble (M () 0.9)
0.7990
0.7937
0,8097
EDST Ensemble (M (S 0.9)
0.8092
0.8148
0.9436
Single Dense Models
0.7584
0,8045
0.7374
24

---

Published as a conference paper at ICLR 2022
L EXPERIMENTS WITH ADVERSARIAL ROBUSTNESS
Table 13 presents the adversarial robustness performance of Wide ResNet-28-10 trained on CIFARO- 10 and CIFAR-IO0, where the Fast Gradient Sign Method (FGSM) (Szegedy al., 2013) with step & size 255 is adopted. Following similar routine as in Strauss et al. (017)) we craft adversarial examples for each single model and report the (min, mean, max) robust accuracy over generated attacks from different models. The results demonstrate that our proposed ensemble methods improve robustness accuracy as well, especially in terms of average robust accuracy. More surprisingly, the ensemble of static sparse models can even outperform DST-based Ensembles in this setting. Further analysis on this task serves as interesting future work.
Table 13: The robust accuracy (%) for Wide ResNett-28 trained on CIFAR- and CIFAR- 100.
Robust Accuracy (%) (min/mean/max)
Methods
CIFAR-10
CIFAR-100
Static Sparse Ensemble (M 1) 0.8)
33.68/38 40/41.29 .22
11.89/15.21/17.01
Static Sparse Ensemble (M = 3) (S 0.8)
39.28/39.466 46/39.77
16.44/16.8 1/11..1
DST Ensemble (M (S = 0.8)
37.30/38.49/1 12
1.966/15.59/15 ,00
EDST Ensemble (M 3) (S 0.8)
19.66/40.35/41.000
13.00/13. 1000/3..1/13.55 19/13.56
EDST Ensemble (M (S 0.9)
35.68/37. 74/38.67
14.45/14.33/15.56
Single Dense Models
44,20
11.82
25


Reviews:
[{"review_id": "WEniRlr5E9-", "reviewer": "Reviewer_HPxD", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n- Well written paper, with good background, clear motivation.\n- This paper's contributions, while completely empirical, present a very good and I'd say relatively complete experimental analysis that will no doubt be useful for researchers and engineers in understanding how DST can benefit sparse neural network training in generalization and/or efficiency.\n- Results for EDST are compelling when generalization/theoretical training compute is considered (as it should be), results that I believe are novel and important - showing that dynamic sparse training can match dense generalization with less (theoretical compute).\n\n\nWeaknesses:\n- DST ensemble is not novel, as it is just an ensemble of DST-trained models which has been analyzed (although with a different focus) in other work.\n- EDST is marginally more novel, but clearly related to other existing methods of training deep neural networks.\n- Some of the analysis of the diversity of sparse solutions is not novel, e.g. Lottery Ticket rewinding not resulting in diverse solutions/producing poor ensembles relative to static sparse ensembles is one of the main contributions of the paper \"Gradient flow in sparse neural networks\", Evci et al., 2020. This paper is cited by the authors elsewhere but not in reference to these results. The authors expand on these results however, and I believe it would strengthen the author's results on the diversity of solutions if they cited this work in the appropriate places and compared their findings (which I believe corroborate that paper's).\n- Some parts of the method are not clearly described (i) through (iv) below:\n(i) 3.1, end of page 3: \"A free ticket is one of the sparse neural networks (subnetworks) generated *during* the dynamic sparse training procedure\". These free tickets \\theta_s^1, \\theta_s^2, \\ldots, \\theta_s^M)...\" this is *very* misleading as \"during\" the DST training there are multiple subnetworks generated over time with each mask update, and this text makes it sounds like the ensemble is of those - but I realized by the next page this is not the case. This needs rewording to make it clear subnetworks are the result of multiple DST training runs.\n(ii) example Algorithm 1 does not describe how the refinement model weights (\\theta_s^j) are initialized explicitly, and this isn't clearly defined in the text. I can only reasonably assume they are initialized from \\theta_s in the exploration phase.\n(iii) Another aspect of this method that's not clear: \"...at the end of each refinement phase\" in section 3.3, does this mean the refinement phase is run multiple times? Or is this referring to each of the subnetwork's refinements? Figure 1 also confuses me on this point as it seems to show multiple refine/exploration steps, and Algorithm 1 only seems to show one Refinement phase (of t_{ex} < ?? steps). Given the lack of clarity, I've assumed there is only one exploration & M refinement phases (consisting of M subnetwork training runs) but I would appreciate this being made clear in the text/Algo 1/Fig 1.\n(iv) several of the variables used in Algo 1 are undefined or misused, including s^i \\in (s^1, \\ldots, s^L) which seems to be the sparse masks, and t_{ex}, and t_{re} which are used as time counters/indices in the algorithm, but are the total amount of time in the text.\n- The paper's usage of \"forward passes\" is problematic - it's defined as a \"complete training phase\" in 3.3, i.e.  a whole training run, which goes against the common usage of the term and is very misleading for the careless reader in the results - change this term to \"training runs\"\n- Although the motivation is efficiency, there are no real timings *or* explanation on how these theoretical FLOPS gains might be realized. There are compelling papers that the author could refer to showing how to accelerate unstructure sparsity however on CPU and GPU (see \"Fast sparse convnets\", Gale et al. 2020), and I would encourage the authors to refer to these to allay such concerns.\n- Figure 1 is much too small, and yet there is a lot of wasted space in how it's presented on the page. I'm also pretty sure that ICLR doesn't allow text to wrap around figures like this - but I could be wrong. Regardless, it would be very easy to fix this figure so that it was more compact, a proper floating figure, and more legible at the same time.", "summary_of_the_paper": "The authors propose to improve the generalization of dynamic sparse neural network training methods, such as RiGL, by learning an ensemble of these models. The authors propose two methods of doing so, the Dynamic Sparse Training (DST) Ensemble, and the Efficient Dynamic Sparse Training (EDST) Ensemble. A DST ensemble is a straightforward ensemble of M DST trained models, which like all ensembles incurs high overhead in training and inference cost (training/using M models). An EDST ensemble on the other hand uses approximately the same training compute as a single model. It does so by splitting the training into two phases (of the total amount of steps as a single standard DST training run). The first phase is standard DST training (called the Exploration Phase), where training uses a large learning rate. The second phase (called the Refinement Phase) trains M models initialized from the weights of the model in the first phase, but with much smaller learning rates decayed over training. Hyperparameters determine the amount of exploration v.s. refinement training steps.\n\nThe authors evaluate the trained ensembles for Image Classification with Wide ResNet28-10 on CIFAR-10/100 and ResNet-50 on ImageNet,  and compare these to baselines including: an ensemble of sparse trained models (with a static mask), an ensemble of Lottery Ticket Rewound models, an alternative method with similar motivation (MIMO), a single dense model, BatchEnsemble and TreeNet. The DST and EDST Ensembles show similar or marginally higher generalization than baselines, but specifically in the EDST case, with much fewer (theoretical) training FLOPS. The authors also compare the diversity of the ensemble members in a few of these baselines, showing that DST has much higher diversity than EDST (as might be expected), but also interestingly that DST appears to have higher diversity than a dense ensemble. The authors perform an ablation study on their results, attempting to discern the affects of parameter exploration (i.e. dynamic mask updates in DST methods), affect of sparsity and affect of ensemble size on the results. The authors also claim to show better out-of-distribution performance and robustness, although these results are in the appendix and only referred to in the main text.", "summary_of_the_review": "I believe this paper, albeit short on technical novelty, does provide a sufficiently novel and important empirical evaluation and details analysis of Dynamic Sparse Training (DST) ensembling methods, and could be accepted - assuming the authors can address the issues I have detailed in my review. In particular this paper has demonstrated, I believe for the first time, that DST methods such as RiGL may not match dense training when standalone, but can surpass the generalization of a dense solution as an ensemble - while still being (theoretically) more efficient to train than the dense model. This result will drive further research into DST methods, as well as encourage researchers to explore the practicality of DST training for making DNN research more computationally accessible.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UN-q2pyoa6", "reviewer": "Reviewer_wRp3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper pointed out an interesting and potentially useful way of training sparse DNNs bypassing the difficulty of optimizing sparse DNNs, i.e. by choosing to ensemble weakly optimized multiple sparse subnets, instead of post-training compression or lengthy DST to reach a single subnet.  \n\nMajor concerns:\n\n- Inference flops.  From the presentation of the results, I do not understand how emsembling $M$ sparse subnets would be efficient at inference time.  Of course at a certain high level of sparsity, the flop count is going to be lower than the dense baseline, but how can it beat a single subnet at the same sparsity, such as one trained with RigL, in flop count?  Even though the training flop count for a single subnet by DST is much higher, the $M\\times$ lower inference flop count would still be desirable in deployment.  If I understand correctly, a fair comparison (in the sense of equal inference flop count) should be between an ensemble of $M$ sparse subnets at sparsity $s$, and a single sparse subnet trained by DST at sparsity $1-M(1-s)$. However, the baselines for comparison are other ensembles instead of single nets.  Given the under-trained individual subnets (e.g. in Fig. 5b), single subnet even at the same sparsity might outperform a sparse ensemble.  \n- Dense ensemble baselines.  How does the sparse ensemble compare to an ensemble of thin, dense individual subnets at the same flop count?  \n- The paper presented hypotheses on the generalization performance of the sparse ensemble trained as such, which are interesting scientific questions, but did not provide convincing results or discussions to validate or disprove the hypotheses.  For example, it is not clear if *diversity*, i.e. disagreement between the subnets, is responsible for the generalization.  Counter-evidence exist, e.g. it has been shown that ensembling nets that are intentionally trained to agree with each other through knowledge distillation improves instead of hurts generalization (arXiv:1805.04770).  From a practical perspective, DST or EDST are by nature handicapped in producing diverse subnets, because the enclosing dense net architecture is still the same--in order to obtain diversity, wouldn't one ensemble individual nets of completely different architecture rather than sparse subnets of the same enclosing dense net?  Further, the ablation study on parameter exploration only reported diversity metrics, but how do they differ in generalization performance?  In Fig. 3, does ensembling a red, a green and a blue checkpoint give higher accuracy than ensembling say three red checkpoints?  \n\nMinor concerns:\n\n- Writing.  Language needs substantial polishing for publication standard.  Too colloquial at places, e.g. \"a tough nut to crack\", and redundant and ungrammatical at others, e.g. \"Currently, the current only way ...\", \"the training costs are far fewer ...\", \"exploring heavily a large fraction ...\", etc.  \n- Some figure/table fonts are too small to be legible.  \n- Sparsely gated mixture of experts.  How does the sparse subnet ensemble compare with sparsely gated MoEs at the same training and inference flop counts?  \n", "summary_of_the_paper": "The authors proposed a method to train an ensemble of sparse DNNs by means of DST such as RigL which, within the same training flop budget, is reported to generalize better than the enclosing dense net or other efficient ensembles; it is also reported to have higher inference-time efficiency.  Further analysis was performed to understand the effectiveness of the sparse ensemble.  \n", "summary_of_the_review": "Though the paper presented interesting ideas, it unfortunately falls short of a systematic study to make a practically useful methodology, or of a compelling hypothesis test that shed light on underlying scientific questions.  \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "S7QCfx20y7r", "reviewer": "Reviewer_4rju", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths\n- The outline of the training setups across different versions of DST and the proposed method was extremely clear and direct. It helps the reader understand the distinction between them easily.\n- Conceptually and practically, the improvements offered by training an ensemble of sparse networks to augment the failures of a single dense/sparse model is extremely useful. A stronger emphasis on analyzing the structural and representational diversity among the FreeTickets and drawing comparisons to prior literature on cascaded weak classifiers would help deepen the impact of the work.\n\nWeaknesses\n- The term \"cheap\" pertaining to one of the key properties required of FreeTickets is left undefined until Pg. 4, Section 3.1. While the comparison to dense networks and their ensembles is fair from the perspective of performance, could the authors clarify if methods like static LTR ensemble and others are similarly \"cheap\" to  DST and EDST? Ultimately, tying a quantifiable comparison of total FLOPs to calculate ensembles to emphasize the notion cheap would be preferable. \n- Could the authors clarify what $n^{(L)}$ refers to in Pg. 4, L. 2?\n- Could the authors discuss the different decision factors that influence the choice of $t_{ex}$? While M controls the amount of time each sub-network is fine-tuned, to what degree does $t_{ex}$ need to be explored so that a sufficient embedding space is learned?\n- Pg. 6, Paragraph on Baselines, the last sentence mentions that the LTR ensemble has low diversity and prohibitive costs. A quantifiable measure or citation would help qualify this statement.\n- Could the authors clarify if the training FLOPs include the total number of forward passes and the FLOPs for each pass or they quantify the FLOPs required for a single pass only? \n- The difference in ECE values between the best and remaining methods across different models and datasets is unstable. Could the authors comment on the significance of these values and their changes? These become critical as we observe a large variation in the best value across multiple methods and metrics, considering Tables 1, 2 and 3.\n- A breakdown of the various labels/samples that cause the disagreement between various FreeTickets would be instructional and add a visual cue to the diversity metric. Additionally, applying KL divergence across intermediate feature embeddings could trace the source of variations and how they have an effect on various metrics.\n- Fig. 3 and Section 5.2 do not comprehensively cover the tSNE projections of other models tested in Tables 1,2 and 3. Without a clear frame of reference and common scale factors it is difficult to compare across the various projections presented. I encourage the authors to try providing a projections for multiple baseline and remove any possible stochasticity in projections to ensure the comparisons are suitable.\n- Section 5.4: Based on Fig. 4 there is a claim that the pattern of ensemble accuracy is highly correlated with the accuracy of the individual sub-network. I encourage the authors to support this with a quantifiable measure. Additionally, visually they do  not seem to have the same pattern of evolution, wrt. sub-network accuracy or deviation in performance of sub-networks. Could the authors clarify the statement in the manuscript?\n- Section 5.5: The manuscript uses the term \"Individual Tickets\" which does not match the nomenclature used in Fig. 5.\n- Section 5.6: The adversarial robustness results for CIFAR-10 show that the dense model is more robust than the sparse models. Could the authors clarify their statements in Section 5.6?\n\nAfter Rebuttal\n\nI thank the authors for their detailed response to each of the comments posted and a well done revision of their manuscript.\nBased on their responses, I have updated my recommendation to an acceptance.\n\nFor the comment on t-SNE plots, on of the key issues when comparing across vastly differing feature spaces is that the 2D projection scales unequally. In providing such projections for alternative ensembling approaches, we can visually discuss the diversity of solutions (mirroring the discussion based on quantifiable metrics).\n", "summary_of_the_paper": "This work focuses on generating ensembles of sparse networks, called FreeTickets, that requires significantly lesser training FLOPs and parameters compared to single or ensemble dense networks while maintaining high prediction accuracy.  FreeTickets are expected to be diverse, highly expressive and easy to obtain. Apart from the methodology to generate these FreeTickets and ensure they match the desired properties, a key claim in this work is that FreeTickets demonstrate improved prediction accuracy, robustness and uncertainty estimation while being much more efficient, in terms of the computational resources required for training. ", "summary_of_the_review": "The proposed methodology is supported strongly by the main set of results. However, there are some missing explanations and justifications required for statements in the analysis performed that need to be clarified. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "7SjN6quCyq", "reviewer": "Reviewer_hJ1v", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Overall, I find the paper quite timely and exciting. It studies a new dimension where sparse neural networks can be used and has many strengths:\n- First large study on the ensemble of sparse neural networks. \n- Strong experimental evaluation and results which include Imagenet-r50 ensembles. Especially experiments in ResNet-50 shows significant gains over dense ensembles.\n- Useful for the community and has descent potential to inspire further research. \n\nHowever, the writing and the overall structure of the paper feels a bit rushed: there are many typos and some important baselines/papers are missing. Given the experimental nature of this work, I think it is important to further polish the paper both in terms of writing and experiments. I share my thoughts below:\n\n**1.Major Concerns/Limitations**\n\na) I think one important ensemble method is missing from the comparison. FGE [2] is possibly the most similar ensemble method to the proposed method. FGE uses cyclic learning rates to find different basins, similar to high q's used in EDST. Comparing these approaches is important I think for completeness. Specifically authors can compare (1) learning rate restart (2) DST training (3) Both LR restart and DST training for EDST.\n\nb) I think this paper has great potential to inspire future research on the topic, therefore I recommend adding pruning baseline to the results. Pruning costs more during training, but might provide better results. It would be nice to see whether that is the case.\n\nc) [3] studies ensembling of sparse NNs and the diversity of various sparse solutions (LT, static, DST). I think a discussion in Section 5.1 comparing results of both papers would be appropriate. Authors can also motivate why LTs are not good for ensembling using their results. \n\nd) Authors say that EDST requires one forward pass, but this is not clear to me; since each model would have a different connectivity and weights and thus would require different (but more efficient than normal) forward pass. The only difference between EDST and DST seems like the training. Do they have different inference procedure? If so, this needs to be clarified; otherwise I think EDST belongs to the same group as DST.\n\ne) Robustness metrics needs to be discussed in the text. I recommend authors to highlight the superior robustness of their approach. It looks like sparse neural networks provide better robustness. \n\nf) An analysis for the p/q used in sparse training would be nice. How does the diversity of the solutions are effected by q? \n\ng) An ablation on importance of grow criteria would be nice (random vs gradients; how much it matter?) An extension of this is to look at the parallel ensemble (i.e. growing different set of connections after removing q=80% of the existing weights); doing this with random would make sense and would tell whether it is better to follow a line, or branch from the same point. \n\nh) There are some things in Figure 4 and 5 that are not clear. In Figure 4, how many networks are ensembled? Given that smaller networks cost less training and inference FLOPs, it feels natural to use more of them for ensembling. Similarly these curves can be all presented on a single plot where x-axis is the inference/training flops and y axis is the ensemble accuracy. \n\n**Minor**\n- I am not sure it makes sense to introduce FreeTickets name as the individual methods are introduced later under different synonyms (DST and EDST). \n- I found the motivation in the intro a bit off. This paper proposes an efficient ensemble method, however the intro talks about different sparse training methods and their tradeoffs. I think authors can introduce these methods later in the text, while focus on the main problem this paper addresses (making ensemble more efficient?).\n- Line 6 and Line 19/20 does the same thing in Algorithm:1, right? It would be nice to use same notation. L20 is currently confusing.\n- Escaping current local minima -> escaping current `basin`.\n- Equation (2): I think a `union` operator would be more appropriate, \"+\" is confusing when you combine indices.\n- Baselines for the ensemble methods are mentioned in related work briefly. A longer description is needed. It would be nice to explain generic ensemble framework while doing this using the notation introduced (in Preliminaries). \n- In different instances authors mention \"with can produce in one shot many diverse yet accurate subnetworks\", however this is only valid for one of the methods proposed (EDST). I recommend rephrasing them accordingly.\n- \" Currently, the current only way for DST to match the performance of its dense counterpart on the popular benchmark, e.g., ResNet-50 on ImageNet, is to perform In-Time Over-Parameterization (Evci et al., 2020a; Liu et al., 2021b), \" -> do you mean rigl? [1] also achieves this I believe.\n- Another related work: Packnet [4]. \n\n**Writing**\nI think the writing of the paper can be improved significantly. Some of them (stopped at page3):\n- \"FreeTickets is defined as the ensemble of these sparse subnetworks\" -> \"Our method, FreeTickets\", uses the ensemble of these sparse networks. Overall, I think abstract can be improved. How about starting with the explanation of your method and then having something like: \"Since these diverse subnetworks are found through relatively cheap ways we call our method FreeTickets.\"\n- Recent works -> Recent work\n- over-extended training time -> longer training time\n- ensemble of models, - >ensemble method\n- FreeTickets is observed to demonstrate a -> FreeTickets improves over dense baseline in following criteria:\n- FreeTickets easily outperforms -> FreeTickets outperforms\n- \"researchers have investigated efforts to train sparse\" ->  researchers studied the training of sparse...\n- \"promising on training efficiency\" -> promising in terms of training.\n- \"g in general is a tough nut to crack\" -> remove i.e \"promising in terms of training efficiency, training a sparse network from scr\"\n- \"Currently, the current only way for\"\n- \"We introduce and conduct the concept\" -> not sure conducting the concept refers to\n- \"ds with can p\" -> \"which can\"\n- \"Our lightest method\" -> our light-weight method\n- \"PRELIMINARY AND SETUPS\" -> Preliminaries\n\n[1] https://arxiv.org/abs/2102.07655\n[2] https://arxiv.org/pdf/1802.10026.pdf\n[3] https://arxiv.org/abs/2010.03533\n[4] https://arxiv.org/abs/1711.05769\n\n## After Rebuttal\nI read your response and went over the changes made in the main text. I appreciate extra results added during the rebuttal:\n\nIt's nice to see sparse connectivity updates complements the learning rate restarts.\nDST ensemble matches pruning ensemble and reduces training costs, which is important to highlight.\nI believe this paper includes some important and through experimental work on ensemble of sparse networks. I increased my score to 6 (not 8 because it still needs some through polishing; which should be done before the camera-ready if accepted). Below I share some minor comments/suggestions.\n\n- Numbers when comparing random growth with gradient based growth looks suspiciously close. If random works as well as the gradient, it worth demonstrating this clearly, running ResNet-50 experiments might give better signals.\n- Algorithm in appendix use p (not q) for exploration.\n", "summary_of_the_paper": "To my knowledge this paper provides the first extensive study on the ensemble of sparsely connected neural networks. Ensembles often improve performance, however they are costly. Sparse neural networks, on the other hand, can reduce the cost of each weak learner significantly. In addition to reducing cost at inference, authors also focus on reducing the cost of training, therefore they use end-to-end sparse training methods (dynamic sparse training). Results show that sparse neural networks can provide comparable (or better) ensemble performance while reducing the training and inference cost significantly. This work also provides some interesting insights into the ensemble of sparse neural networks.", "summary_of_the_review": "The work address an important problem \"Making Ensemble training and inference More Efficient\" using dynamic sparse training algorithms. Results demonstrate that sparse ensembles (1) reduce training and inference cost and (2) increase the robustness (and sometimes accuracy) over the dense models. Given that sparse models provide same accuracy using less parameters, (1) seems not surprising, however (2) is quite interesting and possibly novel. Authors introduce two algorithms for finding sparse networks however both algorithms seem to do the same thing at inference (contrary to how they are explained); this part and some other points need further clarification. Overall, I believe this work has great potential, however current version lacks few important baselines and written poorly. Therefore my initial rating is weak accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: #### Summary

The goal of this work is to reduce the costs of inference in ensembled models by ensembling sparse models. The paper also aims to reduce the costs of training these ensembles as well. The proposed techniques (DST and EDST) each these goals, respectively. 

#### Discussion

As noted by the reviewers, the paper is interesting and timely. The authors provided significant clarifications in the response that satisfied the reviewers' concerns. There is still significant room to revise the remaining points and polish the text of the paper for the camera-ready (I highly recommend proofreading from an individual who is not an author on the paper; there are still typos in the revised edits)

#### Recommendation.
 
I recommend Accept, due to the strengths above and the reasonably scoped remaining work to do going into the camera-ready.
Decision: Accept (Poster)