Unmasking the Lottery Ticket Hypothesis: What's Encoded in a Winning Ticket's Mask?
Authors: Mansheej Paul
Feng Chen
Brett W. Larsen
Jonathan Frankle
Surya Ganguli
Gintare Karolina Dziugaite
Venue: ICLR 2023 notable top 25% (2023)
Keywords: linear mode connectivity
iterative magnitude pruning
loss landscape geometry
lottery ticket hypothesis
sparsity

Abstract: As neural networks get larger and costlier, it is important to find sparse networks that require less compute and memory but can be trained to the same accuracy as the full network (i.e. matching). Iterative magnitude pruning (IMP) is a state of the art algorithm that can find such highly sparse matching subnetworks, known as winning tickets. IMP iterates through cycles of training, pruning a fraction of smallest magnitude weights, rewinding unpruned weights back to an early training point, and repeating. Despite its simplicity, the principles underlying when and how IMP finds winning tickets remain elusive. In particular, what useful information does an IMP mask found at the end of training convey to a rewound network near the beginning of training? How does SGD allow the network to extract this information? And why is iterative pruning needed, i.e. why can't we prune to very high sparsities in one shot? We investigate these questions through the lens of the geometry of the error landscape. First, we find that—at higher sparsities—pairs of pruned networks at successive pruning iterations are connected by a linear path with zero error barrier if and only if they are matching. This indicates that masks found at the end of training convey to the rewind point the identity of an axial subspace that intersects a desired linearly connected mode of a matching sublevel set. Second, we show SGD can exploit this information due to a strong form of robustness: it can return to this mode despite strong perturbations early in training. Third, we show how the flatness of the error landscape at the end of training limits the fraction of weights that can be pruned at each iteration of IMP. This analysis yields a new quantitative link between IMP performance and the Hessian eigenspectrum. Finally, we show that the role of retraining in IMP is to find a network with new small weights to prune. Overall, these results make progress toward demystifying the existence of winning tickets by revealing the fundamental role of error landscape geometry in the algorithms used to find them.

Published as a conference paper at ICLR 2023
UNMASKING THE LOTTERY TICKET HYPOTHESIS: WHAT'S ENCODED IN A WINNING TICKET'S S MASK?
Mansheej Paul Feng Chen Brett W. Larsen 1.3- Jonathan Frankle Surya Ganguli Gintare Karolina Dziugaite
Stanford, Meta AI, "Flatiron Institute. "MosaicML,
Harvard, "Google Research, Brain Team, "Mila; McGill
ABSTRACT
As neural networks get larger and costlier, it is important to find sparse networks that require less compute and memory but be trained the same accuracy as the full network (i.e. matching). Iterative magnitude pruning (IMP) is state of the art algorithm that can find such highly sparse matching subnerworks, known as winning tickets. IMP iterates through cycles of training, pruning fraction of smallest magnitude weights, rewinding unpruned weights back to an early train- ing point, and repeating. Despite its simplicity, the principles underlying when and how IMP finds winning tickets remain elusive. In particular, what useful informa- tion does an IMP mask found at the end of training convey to rewound network near the beginning of training? How does SGD allow the network to extract this information? And why is iterative pruning needed, i.e. why can't 't prune to very high sparsities in one shot? We investigate these questions through the lens of the geometry of the error landscape. First, we find that-at at higher sparsities-pairr of pruned networks at successive pruning iterations are connected by a linear path with zero error barrier if and only if they are matching. This indicates that masks found at the end of training convey to the rewind point the identity of an axial subspace that intersects a desired linearly connected mode of a matching sublevel set. Second, we show SGD can exploit this information due to a strong form of robustness: it can return to this mode despite strong perturbations early in training. Third, we show how the flatness of the error landscape at the end of training limits the fraction of weights that can be pruned at each iteration IMP. This analysis yields new quantitative link between IMP performance and the Hessian eigen- spectrum. Finally, we show that the role of retraining in IMP is to find a network with new small weights prune. Overall, these results make progress toward de- mystifying the existence of winning tickets by revealing the fundamental role error landscape geometry in the algorithms used to find them.
INTRODUCTION
Recent advances in deep learning have been driven by massively scaling both the size networks and datasets (Kaplan et al., 2020; Hoffmann et al., 2022). But this scale comes at considerable resource costs. For example, when training or deploying networks on edge devices, memory and computational demands must remain small. This motivates the search for sparse trainable networks (Blalock et al., 2020), pruned datasets (Paul et al., 2021; Sorscher et al., 2022), or both (Paul et al., 2022) that can be used within these resource constraints.
However, finding highly sparse, trainable networks is challenging. A state of the art algorithm for doing so is iterative magnitude pruning (IMP) (Frankle et al., 2020a). IMP starts with dense network usually pretrained for a very short amount of time. The weights of this network are called the rewind point. IMP then repeatedly (1) trains this network to convergence; (2) prunes the trained network by computing a mask that zeros out fraction (typically 20%) of the smallest magnitude weights; (3) rewinds the nonzero weights back to their values at the rewind point, and then starts the next iteration by training the masked network to convergence. Each successive iteration yields a mask with higher sparsity. The final mask applied to the rewind point constitutes highly sparse trainable subnetwork called winning ticket if it trains to the same accuracy as the full network, i.e. matching.
"qqul contribution. Correspondence to: manshee faw.aseeeeetttoooddd.oooo jtt.rttttarorr.ueuuuuaaaagagooo gkdz@googlllgogoo com.

---

Published as a conference paper at ICLR 2023
Figure I: Error landscape of IMP. At iteration L, IMP trains the network from a pruned rewind point (cir- cles), a² DD dimensional axial subspace (col- ored planes), to a level L pruned solution (triangles). The smallest (1-a) fraction weights are then pruned, yielding the level L projection (x s) whose 0 weights form sparsity mask corresponding to a /++1 D di- mensional axial subspace. This mask, when applied to the rewind point, defines the level L++ initializa- tion. Thus IMP moves through sequence of nested axial subspaces of increasing sparsity. We find that when IMP finds sequence of matching pruned so- lutions (triangles), there is no error barrier on the piecewise linear path between them. Thus the key information contained in an IMP mask is the identity of axial subspace that intersects the connected matching sublevel set containing a well-performing overparameterized network.
Nested Subspaces of Increasing Sparsity Q:
<>>
R D
Ia
qaaD
RaD
opt
RDD
Matching Error Sublaval Set
Although IMP produces highly sparse matching networks, it is extremely resource intensive. More- over, the principles underlying when and how IMP finds winning tickets remain quite mysterious. Thus, the goal of this work is to develop a scientific understanding of the mechanisms governing the success or failure of IMP. By doing so, we hope enable the design of improved pruning algorithms.
The operation of IMP raises four foundational puzzles. First, the mask that determines which weights prune is identified based small magnitude weights at the end of training. However, the next iteration, this mask is applied to the rewind point found early in training. Precisely what information from the end of training does the mask convey to the rewind point? Second, how does SGD starting from the masked rewind point extract and use this information? The mask indeed provides actionable information beyond that stored in the network weights at the rewind point- using a random mask or even pruning the smallest magnitude weights at this point leads to higher error after training (Frankle et al., 2021). Third, why are we forced to prune only a small fraction of weights at each iteration? Training and then pruning large fraction of weights in one shot does not perform as well as iteratively pruning a small fraction and then retraining (Frankle & Carbin, 2018). Why does pruning a larger fraction in one iteration destroy the actionable information in the mask? Fourth, why does retraining allow us to prune more weights? A variant of IMP that uses different retraining strategy (learning rate rewinding) also successfully identifies matching subnetworks while another variant (finetuning) fails (Renda et al., 2020). What differentiates a successful retraining strategy from an unsuccessful one?
Understanding IMP through error landscape geometry. In this work, we provide insights into these questions by isolating important aspects of the error landscape geometry that govern IMP performance (Fig. 1). We do so through extensive empirical investigations on a range of benchmark datasets (CIFAR-10, CIFAR-100, and ImageNet) and modern network architectures (ResNet-20, ResNet-18 18, and ResNet-50). Our contributions are as follows:
We find that, at higher sparsities, successive matching sparse solutions at level L and L + (adjacent pairs of triangles in Fig. 1) are linearly mode connected (there is error barrier on the line connecting them in weight space). However, the dense solution and the sparsest matching solution may not be linearly mode connected. The transition from matching to nonmatching sparsity coincides with the failure of this successive level linear mode connectivity. This answers our first question of what information from an IMP solution the end of training is conveyed by the mask to the rewind point: it is the identity of a sparser axial subspace that intersects the linearly connected sublevel set containing the current matching IMP solution. IMP fails to find matching solutions when this information is not present. (Section 3.1)
We show that, at higher sparsities, networks trained from rewind points that yield matching so- lutions exhibit a strong form of robustness. The linearly connected modes these networks train into are not only robust to SGD noise (Frankle et al., 2020a), but also to random perturbations of length equal to the distance between rewind points at successive levels (adjacent circles in second question of how SGD extracts information from the mask: two
Fig. 1). This answers pruned rewind points at successive sparsity levels are likely to navigate back to the same linearly connected mode yielding matching solutions (adjacent triangles Fig. 1). (Section 3.2)
2

---

Published as a conference paper at ICLR 2023
We develop approximate theory, based on Larsen et al. (2022), that determines how aggres- sively one can prune a trained solution (triangle in Fig. 1) in any level in terms of the length of the pruning projection (distance to associated x in Fig. 1) and the Hessian eigenspeetrum at the solution. This theory sheds light on why flatter error landscapes allows more aggressive pruning. Our theory quantitatively matches random pruning while show that magnitude pruning can slightly outperform it. (Section 3.3)
We explain the superior performance of magnitude pruning by showing that this method identi- fies flatter directions in the error landscape compared to random pruning, thereby allowing more aggressive pruning per iteration. Together, these results provide new quantitative connections be- tween error landscape geometry and feasible IMP hyperparameters. They also answer our third question why we need iterative pruning: one-shot pruning to high sparsities is prohibited by the sharpness of the error landscape. (Section 3.3)
We show that fundamental role of retraining is to reequilibriate the weights of the network, i.e. find networks with new small weights amenable to further pruning. Successful retraining strategies such as weight and learning rate (LR) rewinding (Renda al., 2020) both do this while finetuning (FT), an unsuccessful retraining strategy, does not. This answers our fourth question regarding why retraining allows further magnitude pruning. (Section 3.4)
Overall, our results provide new geometric insights into IMP, including when this method breaks down and why. We hope this understanding will lead to new pruning strategies that match the per- formance of IMP but with fewer resources. Indeed, simple adaptive rule for choosing the pruning ratio at each level leads to nontrivial improvements (Appendix F). Furthermore, understanding the role of weight reequilibriation in retraining may inspire methods achieve this property faster.
Related work. A number of studies have focused on finding matching subnetworks at initializa- tion (c.g., Lee et al., 2019; Wang et al., 2020; Tanaka et al., 2020). Despite substantial progress, these methods do not find matching solutions at scale (Su et al., 2020; Frankle al., 2021); the trained dense network seems to be an important ingredient for IMP (e.g.. Zhou et al., 2019; Frankle et al., 2020a; Ramanujan al., 2020; Sreenivasan et al., 2022). Another essential part of IMP is to iteratively prune a small fraction of the weights with periods of retraining between them. For both training without rewinding (Han al., 2015), and lottery tickets with rewinding (Frankle al., 2020a), one-shot magnitude pruning cannot find matching subnetworks of the same sparsity as itera- tive pruning. Alternative methods that do also feature iterations of pruning and retraining (Renda et al., 2020; Savarese et al., 2020). Additionally Zhou et al. (2019) and Frankle et al. (2020b) in- vestigate what information weights to prune and how to reinitialize weights for retraining. We explore the importance of these ingredients in IMP through the lens of the error landscape geometry.
necessary for finding winning tickets with many ablations of which
The closest related works to our results are Frankle et al. (2020a) and Evci et al. (2022). Both works consider linear mode connectivity between two networks of the same sparsity. Frankle et al. (2020a) compare two networks trained from the same rewind point at the same pruning level but with different SGD noise. Evci et al. (2022) find pruning solution and mask using Gradual Magnitude Pruning (GMP; Zhu & Gupta (2017)) instead of IMP and apply the mask to the rewind point to obtain a lottery ticket solution. They then observe that these two sparse solutions are linearly mode connected, and close in function space. In contrast, our work studies linear mode connectivity between pairs of IMP solutions at different levels of sparsity. This allows us to understand the mechanism by which an IMP iteration can find a sparser matching subnetwork from the previous matching IMP solution. Finally, in concurrent work, Na et al. (2022) show that networks trained with SAM (Foret et al., 2021) are more amenable to pruning. This provides further evidence connecting loss landscape flatness and pruning. See Appendix A for extended related work.
PROBLEM SETUP, NOTATION, AND DEFINITIONS
Let w E RRO be the weights of network and let E(w) be its test error on a classification task. Definition 2.1 (Linear Connectivity). Two weights w, w' are s-lincarly connected if E [0. 1]. E(7 + (1-7)- w') S 7. E(w)= (1 - 7) E(w") +
(2.1)
We define the error barrier between and w' as the smallest for which this is true. We say two weights are linearly mode connected if the error barrier between them is small (i.e., less than the standard deviation across training runs).
3

---

Published as a conference paper at ICLR 2023
Sparse subnetworks. Given dense network with weights w, a sparse subnetwork has weights m O w, where m E {0, 10 is a binary mask and @ is the element-wiss wise product. The sparsity of a mask m is the fraction of zeros, (1 (1-n)< E 1]. Such mask also defines -DDddimessonall axial subspace spanned by coordinate axis vectors associated with weights not zeroed out by the mask.
Notation for training. For iteration f, weights w, and number of steps t', let A, t') be the output of training the weights w for t' steps starting with the algorithm state (e.g. learning rate schedule) at time L. In this notation, if wo denotes the randomly initialized weights, then ordinary training for T steps produces the final weights Wr - Ao(o.. T).
Iterative magnitude pruning (IMP). IMP with Weight Rewinding (IMP-WR) is described in Al- gorithm (Frankle et al., 2020a). Each pruning iteration is called a pruning level, and m(4) is the mask obtained after L levels of pruning. 7 denotes the rewind step, w, the rewind point, and 1 aa denotes a fixed pruning ratio, i.e. fraction of weights removed. The algorithm is depicted schemat- ically in Fig. 1. The axial subspace associated with mask m m(") is colored subspace, the pruned rewind point m ( w, is the circle in this subspace, the level T. solution w(4) obtained from training is the triangle also in this subspace, and the level L projection obtained as m (L+11) @ w(() is the cross in the next, lower dimensional axial subspace. Note w(2) = =Ar Am (L) @ W,, W,,T-57 -T).
We also study two variants of IMP with different retraining strategies in Section 3.4: IMP with LR rewinding (IMP-IRR) and IMP with finetuning (IMP-FT) (Renda et al., 2020). In IMP-LRR, the level L solution, and not the rewind point, is used as the initialization for level L retraining and the entire LR schedule is repeated: w(?) Am(m())) ( T)). IMP-FT is similar to IMP-LRR but instead of repeating the entire LR schedule, we continue training at the final low LR for the same number of steps: w(1)) = Ar m (4) @ w(L-1), 1)T-))))).a See Appendix A for a discussion.
Algorithm I: Iterative Magnitude Pruning- Weight Rewinding (IMP-WR) (Frankle et al., 2020a)
1: Initialize dense network Wo R and pruning mask m
1d
2: Train We for 7 steps to w.-
Phase I: Pre-Training
3: for L E {O...., Lmxx 1) do
> Phase 2: Mask Search
4: Train the pruned network m m(2) @ w- to obtain level L solution w())
5: Prune a fraction a of smallest magnitude nonzero weights after training:
Let m [[] if weight is pruned, otherwise let m (L+1)) m (1)
[]]
6: Train the final network m ( Wy. Mcasure its accuracy.
> Phase 3: Sparse Training
Definition 2.2. A sparse network m @ w is e-matching (in error) if it achieves accuracy within of that of a trained dense network wrr E(m @ ww I E((r) + E.
Since we always set as the standard deviation of the error of independently trained dense networks, we drop the e from our notation and simply use matching.
Definition 2.3. (sparse or dense) network W, stable (at iteration r) if, with high probabil- ity, training pair of networks from initialization w- using the same algorithm but with different randonness (e.g., different minibatch order, data augmentation, random seed, etc.) produces final weights that are linearly mode connected. The first iteration T at which network is stable is called the onset linear mode connectivity (LMC).
Frankle et al. (2020a) provide evidence that sparse subnetworks are matching if and only they are stable. Finally, playing central role in our work is the concept of an LCS-set.
Definition 2.4. An s-linearly connected sublevel set (LCS-set) of a network w is the set of all weights w' that achieve the same error as up to E, i.e. E(w') S E(w) E, and are linearly mode connected to w, i.e. there are no error barriers on the line connecting w and w' in weight space.
Note that an LCS-set is star convex; not all pairs of points in the set are linearly mode connected. As with matching, we drop E from the notation for LCS-set.
RESULTS
3.1 PRUNING MASKS IDENTIFY AXIAL SUBSPACES THAT INTERSECT MATCHING LCS-SETS.
First, we elucidate what useful information the mask found at the end of training at level provides to the rewind point level I. 1. We find that when an iteration of TMP from level L. to T. + finds
4

---

Published as a conference paper at ICLR 2023
imagittet Randtee CIARR-10 Reatet
Test Ertor (R6
50
9.0
Level
9.8
9.4
9.0
7.5
1012
8.6
Test Enrr 1%)
100
24.0
80
23.5
Level
23.0
99101112
4 8
Level (Higher Sparsity -+)
Level (Higher Sparsity ++)
Level (Higher Sparsity -)
Early Step
Matching
6-Matching
Figure 2: Error Connectivity IMP. Left: The error along a piecewise linear path connecting each
level L solution w-(+) the 1+11 solution w-[++11 for different rewind steps. Purple curves: rewind step O, orange curves: early rewind steps (250 for CIFAR-10 and 1250 for ImageNet), and green curves: rewind steps that produce matching subnetworks (2000 for CIFAR-10 and 5000 for Ima- shows that networks the piecewise linear path between matching IMP solutions are also matching. Right column: The maximal error barrier be- tween all pairs of solutions different levels (from the matching rewind step). The dark blue regions indicate solutions a matching linearly connected mode. See Fig. 16 for CIFAR- CETAR-100/Re/// 100/ResNet- results and Fig. 11 for results Iterative Gradient Pruning, different pruning strategy.
geNet). Middle: Zoomedd in plot green
Level
15 Reshet
9.4 gd
8.6
8.2
Level
Level
Level
Level
24.0
!
23.5 d
23.0
Imagehic
Level Soin.
Level L Projected
Level Soin.
Axial Subspace
Projection
e-Matching Thresh.
Figure 3: Two-dimensional slices of the error landscape spanned by 3 points each level L: (1) the solution (()) (grey triangle), (2) its level L projection m (l+1) @ ((.) (orange x) onto the axial subspace mL+1) (purple dashed line), and (3) the level I, + 1 solution w(++1) (orange triangle) found by retraining with the new mask m (L+1), The axial subspace mL++1) is obtained by 20% magnitude pruning on w(2), The dotted black contour outlines the LCS-set of w(4), Column shows low sparsity level where the projection remains within the LCS-set; column 3 shows
higher sparsity level where the projection is outside, but w[++)) returns to the LCS-set. Column shows a higher sparsity level, at which IMP fails to find matching solution: both the projection and retrained solution lie outside the LCS-set. See Fig. 17 and 18 for additional results.
a matching subnetwork, the axial subspace m (L+1) obtained by pruning the level L solution, w(D), intersects the LCS-set of this solution. By the definition of set- all the points in this intersection matching solutions in the sparser m (4++1) subspace and are linearly connected to w-(.), We also find that the network wI++)) found by SGD is in fact one of these solutions. Conversely, when IMP from level L to L + 1 does not find a matching subnetwork, the solution (L+11) does not lie in the LCS-set of w(L), suggesting that the axial subspace m (L+1) does not intersect this set. Thus, we hypothesize that round of IMP finds matching subnetwork if and only if the sparse axial subspace found by pruning intersects the LCS-set of the current matching solution.
Figs. 2 and 3 present evidence for this hypothesis. The left and center columns of Fig. show that in a ResNet-50 (ResNet-20) trained on ImageNet (CIFAR-10) 10), for rewind steps at initialization (blue curve) or early in training (orange curve), successive IMP solutions (1.) and w(+++) are neither matching linearly mode connected. However, at later rewind point (green curve) successive
5

---

Intuitively, this means that weights a distance away from w,, are in the same attraction basin as w,- If RGD is robust to perturbations of the same norm as v||2, then (4411) @w, will train to solution that is linearly mode connected to (L) Additionally if ((4 is matching and m (L+1) intersects the LCS- of w (L),, then w(++1) is in the LCS-set of (L) and so it will be matching. We empirically test this notion of SGD robustness starting from the pruned rewind point (4) @ w, for all levels L and perturb by either the actual IMP perturbation v or a random perturbation of norm || 1/22- Fig. confirms that whenever IMP can find matching network, SGD is indeed robust not only to IMP- induced perturbations but also random perturbations. In Appendix D. we show implications of this result: masks found by IMP-LRR can also be used for retraining from the rewind point. In summary, we find that IMP can use the mask m (L+1) at an early rewind point to navigate back to an LCS- set of the previous solution (1. when the rewind point enjoys the property of SGD robustness to Published as a conference paper at ICLR 2023
matching solutions are linearly mode connected. Fig. 3 visualizes two dimensional slices of the error landscape containing the level L solution, its pruning projection, and the level L ++ solution. We find that at early pruning levels, the projected network, m (L++)) @ w(4), remains in the -eC of w(L), Thus the m(++) axial subspace intersects this set. As L increases, the projections leave the LCS-set of w w(L), which also shrinks in size. However, the axial subspace m still intersects the LCS-set of w(t) since w(++1) lies in this set. Conversely, at the sparsity level when matching breaks down, the axial subspace no longer intersects the LCS-set.
In summary, when IMP succeeds, i.e. w(L) and w(++1) are both matching, the mask m m(++1) defines an axial subspace that intersects the LCS-set of w(4), When IMP fails, this intersection also fails. Thus, the key information provided by the mask m (L+1) is good axial subspace that could potentially guide SGD matching solutions in the LCS-set of w(7) but at higher sparsity.
Note that at rewind steps where IMP is successful, Level O and Level 1 may not be linearly mode connected (Fig. 3 bottom left) because the dense network is not yet stable (Frankle et al., 2020a). However, we sill find matching solutions as the network with 80% weights remaining is still very overparameterized and many good optima exist. See Appendix G for detailed discussion.
Another interesting observation: the dark blue regions in Fig. 2 (right) indicate that all pairs of matching IMP solutions at intermediate levels are linearly mode connected with each other. How- ever, in ImageNet, there are error barriers between the earliest and last matching level (yellow block position (1, 10)). Though each successive pair of matching IMP solutions are linearly connected, all matching IMP solutions need not lie in a convex linearly connected mode. The connected set containing the piecewise linear path between successive IMP solutions can in fact be quite non- convex; see Fig. 16 for an extreme example on results on Iterative Gradient pruning, another iterative pruning method.
Also see Appendix H for
3.2 RETRAINING FINDS MATCHING SUBNETWORKS IF SGD IS ROBUST TO PERTURBATIONS.
So far we have seen that IMP succeeds in finding a matching subnetwork if w(1)) is matching and the mask m (L+1) provides an axial subspace that intersects the I.CS of w( thus guaranteeing the existence of sparse matching solutions. But how is SGD able to extract this information from the mask at the rewind point. In particular, assuming m (I++) intersects the LCS-set of w('.) why would m (L+1) @ W, train to a ((++)) that lies within the LCS-set of (L) and not some other optimum in the m (I+1) axial subspace?
We will show that IMP retraining likely does so because of the robustness of SGD training to pertur- bations at late enough rewind steps. We treat v (mL++) @ @w.) - (m (-+)-(m(2 O ow) perturbation to the level L pruned rewind point (L) @ W.- At this rewind point, we hypothesize that the net- work (L) C w, stable not only up to SGD noise (Frankle et al., 2020a), but also that the linearly connected mode SGD trains to is robust to perturbations of magnitude less than or equal to || We define robustness of SGD to perturbations as follows:
Definition 3.1. A (sparse) network w, is robust at T to random perturbations of size c, if with high probability Ar T -)) is linearly connected to A, A,(w, +v, -)). f)r v drawn uniformly from the sphere of radius e around 0, (0).
sufficiently large perturbations. See Appendix I for further experiments robustness of SGD.

---

Published as a conference paper at ICLR 2023
RaD a
CIFAR-10 ResNet-20
ImageNet ResNet-50
Rociral
P
27
9.5
26
Projection
9.0
25
8.5
24
23
7.5
22
2
4
10
4
6
Lovel (Highar Sparsity
Level (Higher Sparsity
IR R
Mandhing
<:Matching
-
IMP Projection
Random Perturbation
Figure 4: Robustness of SGD. Left: At rewind step T that yields a winning ticket wr. for each level L, we add random perturbation to the level L pruned rewind point m(4) @ w, with the same ly norm as the lz distance R between m(*) @ w, and level L + pruned IMP projection m(++1) ④ Wy- We then train all networks (black curves) Right: The error barrier between the level L solution w(4) and the level L + 1 IMP solution w (blue) and the enror barrier between the level L solution w(2) and the trained random perturbation (orange). These curves show that for levels that yield matching solutions, the robustness of SGD explains why, after projecting the rewind step, m (L+1) O W, can train to the LCS-set of w(4), See Fig 19 for CIFAR-100/ReSt 18 results.
3.3 THE HESSIAN FIGENSPECTRUM GOVERNS MAXIMAL PRUNING RATIOS PER ITERATIOON
Our third question concerns why iterative pruning is necessary and why we can't simply prune to high sparsities in one-shot without sacrificing accuracy? To address this, consider the level I. IMP solution w(L) and its associated projection ml w(4) (i.e. triangles and their associated x's in Fig. 1). Let denote the distance between m(++1) @ w(L) and w(L) by R. Also we know from Sec. 3.1 that when IMP achieves matching. the axial subspace m (L+1) intersects the LCS- set of w() because retraining within m (L+1) yields matching ((++1) that is linearly connected to w(1). Now suppose we have used a constant pruning ratio (fraction of weights removed) of
1 1- a < 1 up to level I. so that w(L) has a² D nonzero weights. Suppose further that at level L explore different pruning ratios f- This means we remove fraction f of the a D nonzero weights in ((1)) to obtain networks in an axial subspace ml++1) that have (1 f)a² D nonzero weights. Thus we would like to understand conditions under which an axial subspace of dimension == (1 - fa D centered at point m (L+1) @ (L) of distance R from w intersects the -.CS-set of this solution. This leads us to exploit the phase transition observed in Larsen et al. (2022):
Phase transitions in the intersection probability of random subspaces with error sublevel sets. While it is difficult characterize when an axial subspace of low dimension intersects given error sublevel set, recent work has analyzed both empirically (Li et al., 2018) 8) and theoretically (Larsen et al., 2022) when a random affine subspace of dimension d centered a point P intersects a loss sublevel set located a distance R from P. In particular Larsen et al. (2022) showed that the intersection probability (over the choice of random affine subspaces) undergoes sharp phase transition from 0 to I as the dimensionality d increases. We call the dimensionality d' at which this phase transition occurs the intersection threshold (it was called the threshold training dimension by Larsen et al. (2022)). This threshold increases the further the point P is from the sublevel set (it is harder to hit a sublevel set when one starts further away) and decreases the larger the sublevel set is (it is easier to hit larger sublevel sets). Larsen et al. (2022) found general formulas for the intersection threshold d', and derived an explicit formula when the error landscape could be approximated as a quadratic well, yielding:
Lemma 3.1. Consider a quadratic error landscape over ambient dimension D with minimum error O and Hessian eigenvalues "a.....,AAA! An E-sublevel set M is then an ellipsoid with principal radii T = /2 A random affine subspace of dimension of d centered at a point P distance R from the minimum intersects M with high (low) probability if d d² (d < d') where the intersection threshold d' is given by the approximate upper bound d' = DA_ r +r?).
Intuitively, the further one is from the minimum (larger R), the higher the intersection threshold is (harder to hit). Also the larger the sublevel set is (through more large radii r; corresponding Hessian eigenspectra with more small Aç. i.c. flat directions) the lower the intersection threshold d' (i.e. the easier is to intersect). See Appendix C for more discussion.
The intersection thresholds of random subspaces predicts maximal pruning ratios. We now apply Lemma 3.1 predict maximal pruning ratios for random affine subspaces, which we use as
7

---

Published as a conference paper at ICLR 2023
CIFAR-10 ResNet-20
ImageNet ResNet-50
1.0
Jevel
level
level H
1.00
level
level 6
level 1.0
Prunigg Ratto
Pruning Batlo
3,75
20
3.50
0.0
0.00
10
40
30
10
20
100
8
R
R
Matching Magnitude X Non Matching Magnitude
Matching Random X Non- Matthhn Random
Theary
Figure 5: The Hessian eigenspectrum determines the limits of IMP. For each level L, we use the intersection threshold of random subspaces with LCS-sets (see Lemma 3.1 and main text) to derive a maximal theoretical pruning ratio at level L (black eurves) that still allows matching. This predicted maximal ratio decreases with the distance R of the projection. The resultant limiting black curve shrinks to the origin as the Hessian eigenspectrum gets sharper at higher levels L. We illustrate this by plotting the theoretically predicted maximal pruning ratio curves from earlier levels in light gray. We compare the maximum pruning ratio with both random and magnitude pruning. The theoretical maximum pruming ratio (black curves) predicts well when random pruning will match at small pruning ratios (green circles below black curves) and when random pruning will fail to match at large pruning ratios (red x 's above black curves). Interestingly, IMP slightly outperforms random pruning, with some matching IMP solutions (blue circles) occuring above the black curves, though eventually they fail to match at even larger pruning ratios (orange x's).
an approximation for pruning to a random axial subspace. In particular, we consider w:(1) to be the minimum of an error landscape over ambient dimension D = D. D. We approximate this error landscape through a quadratic approximation, using the Lanczos algorithm (Yao et al., 2020) to estimate the entire Hessian cigenspectrum density at w((), We then prune w-(4) with pruning ratio (either random pruning or magnitude pruning) obtaining an affine axial subspace of dimension w(L)) that is distance R from w(2). We model this axial subspace as a random affine subspace. Then inserting these expressions into the intersection phase transition condition d > d' D Σ; r /RR + r²)) turns a lower bound on the subspace dimension d () in order to intersect the sublevel set into an upper bound on the pruning ratio f in order to intersect. Thus, according to this random subspace intersection phase transition, the intersection of the axial subspace m!4-1) with the LCS-set of w(4) is predicted to occur only if the pruning ratio f is less than a threshold set by both the distance R and the radii rg. In
d = (1 f) centered at point P m (L+1) @
particular, smaller distances R moved in the projection allow larger pruning ratios f. as do Hessian eigenspectra with more flat directions, i.c. with more large radii Ti.
Fig. 5 shows the results of comparing the prediction of Lemma 3.1 to both random and magnitude pruning at a variety of pruning ratios f and levels L. Our theory predicts well when random pruning shifts from matching at small pruning ratios f' below the predicted maximum to non- non-matching at large pruning ratios above the maximum. Furthermore, as one progresses to higher sparsity levels L, the maximal allowed pruning ratio (black phase boundaries) shift lower. This happens because the error landscape is getting sharper at higher sparsity levels, thereby limiting the maximal allowed pruning ratio more stringently.
IMP preferentially prunes flatter landscape directions. Surprisingly, we also note in Fig. 5 that IMP can sometimes find matching subnetworks pruning ratios higher than the maximal allowed by our theory given the assumptions-as few blue circles to the upper right of the black curves. This suggests that the success of IMP is not due to smaller projection distance R alone. Strikingly, the small magnitude weights pruned by IMP are preferentially correlated with flatter error directions in the LCS-set. Fig. provides strong evidence for this hypothesis. IMP implicitly pruning flatter direction of the error landscape allows for higher pruning ratios. We note that pruning weights along flat directions dates back the 1980's, e.g. optimal brain damage (LeCun et al., 1989).
3.4 THE IMPORTANCE OF ITERATIVE PRUNING AND RETRAINING
Here we study our fourth question: the role of retraining, Renda et al. (2020) find that both IMP-WR and IMP-LRR find matching subnetworks while standard finetuning (with fixed small learning rates) does not. What does either weight or LR rewinding achieve that typical finetuning does not? Fig. 7 demonstrates that both 1MP-WR and IMP-LRR reequilibriate the weight distribution after pruning, i.e. retrained network once again contains substantial fraction of small magnitude weights that
8

---

Published as a conference paper at ICLR 2023
Level
Level
Level
Level
Level 10
30
28 4
26
Imagole
22
Smallest Weights
Prune Random Weights
M-Matching Thresh.
Figure 6: Magnitude pruning directions correlate with flat directions. The level L solution w (f.) at the center. The orange (purple) arrow indicates weight space motion when we prune the 20% smallest (random) weights. We visualize slice of the error landscape along the plane spanned by these two directions and the black dashed contour shows the boundary of the LCS-set of w-(4), Note: (1) the smallest magnitude weight direction is flatter than the random one; and (2) the basin in this slice becomes sharper at higher levels of sparsity. See Fig. 20 and 21 for CIFAR- 10 and CIFAR-100) 100.
ImageNel ResNet50
Level
Level 4
Level 7
Level 11
0.3
0.3
0.3
0.3
0.2
0.2
0.2
0.2
CDF
0.1
0.1
0.1
0.1
0.0
0.0
0.0
0.5
0.0
0.5
0.0
0.5
0.0
0.5
Norma lized Weights
Normalized Weights
Normalized Weights
Normalized Weights
Weight Rewinding
After Projection Learning Rewinding
Finctuning
Figure 7: The effect of Weight Rewinding, Learning Rate Rewinding and Finetuning on the distribu-
tion of weights at each level. The dark blue curve shows the cumulative distribution function (CDF) of the absolute value of the normalized weights immediately after projection; the initial flat seg- ment is due to the 20% of the weights pruned from the previous level. The three other curves show the CDF of the weights after three different training procedures: IMP-WE IMP-LRR, and IMP- FT. We observe that IMP-WR and IMP-LRR produce similar CDFs but IMP-FT results in fewer small weights. These observations indicate that a key role of iteration in IMP is to reequilibriate the weights. See Fig. for discussion and Fig. 22 for CIFAR-10 10 results.
are amenable to pruning. Finetuming, on the other hand, fails to reequilibriate the weights and further pruning creates large projections, thus making it difficult to find an axial subspace that intersects with the LCS-set containing the current solution. As a result, finetuning fails to find matching networks up to the same levels of sparsity as weight or learning rate rewinding. Further discussion in Fig. 9.
4 DISCUSSION
In this work, we investigate the different steps that make up an iteration of IMP and construct a scientific understanding of the role played by each of these steps in finding winning lottery tickets. We uncover that the IMP mask conveys to the rewind point the location of linearly connected mode containing matching sparse solutions. We show that the ability to train into this mode from the rewind point and find these matching solutions follows from the robustness of SGD at the rewind step. We also forge new link between the Hessian eigenspectrum and IMP, showing sharper minima limit maximal pruning ratios. Remarkably, we discover that IMP implicitly finds flatter directions to prune. Finally, we show that the role of retraining is find new mmanl-ma weights to prune.
Our results suggest that a key design principle for future pruning strategies might involve direct exploration of lower-dimensional axial subspaces that intersect the LCS-set of the current network. Indeed, motivated by our new scientific understanding we show in Appendix F (Fig. 10) that it is possible to achieve the same performance as IMP but with fewer levels of pruning by dynamically choosing the per-level pruning ratio so as to stay within the LCS-sC after projection. In CIFAR- 100 example, we are able to prune to the same sparsity in 7 levels instead of the 11 required when using the fixed ratio of 20%. Though the strategy of pruning more for low sparsity levels is not new, our findings provide new geometric principles for efficiently and effectively choosing this pruning ratio hyperparameter at every sparsity level. Additionally, by uncovering that the key role of retraining is to reequilibriate the weights, our results provide new direction for algorithmic approaches to achieve this property using less compute than full retraining. Finally, work opens up new theoretical questions, such as why small magnitude weights correlate with flatter directions on the error landscape.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
The experiments for this paper were partially funded by Google Cloud research credits and partially performed at Meta AI. The authors would like to thank Daniel M. Roy, Ari Morcos, and Utku Evci for feedback on drafts.
REFERENCES
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? In I. Dhillon, D. Papailiopoulos, and V. Sze (eds.), Proceedings of Machine Learning and Systems, volume 2, pp. 129- URL https: /ptpp//eoooeegsssseeeee....ss mlays. wttppppppe////////e/.////// L2cdaalBfo6655888223636633322222
146, 2020.
Utku Evei, Yani loannou, Cem Keskin, and Yann Dauphin. Gradient flow in sparse neural networks and how lottery tickets win. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pp. 6577-6586, 2022. URL https: www.jsaaaii..o.. index. wwnde.pppp/eeeee AAAT/ atticle/view/26611
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware mini- mization for efficiently improving generalization. In ICLR Sporlight, 2021. URL https: //waxiiv.rgg/aaaaaiee..//o /2100.01..0000 01412.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations, volume 119 of Proceedings of Machine Learning Research. PMLR, 13-18 Jul 2018. URL https: htttps:/pproceeding mlr. www..pressvvil wwlllvlliiuli html.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In Proc. Int. Conf. Machine Learning (ICML), 2020a. URL https: ppppppeeoennggseee ml www.mmerr....ll... Farrk////rakke0aaaammmm html.
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. The early phase of neural network training. In International Conference on Learning Representations, 2020b. URL https:
/ //openreview..o..//o..e.ee.e.eve http://ooommmmdi/oeeeeee
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works initialization: Why are missing the mark? In International Conference on Learning Representations, 2021. URL https: http///peeeeeeeeeeeeeeeeeee net. http://wwwwweeeetuueeeeeeee
/
VyQo- MLK.
Ychoram Gordon. On milman's 's incquality and random subspaces which escape through mesh in R". In Geometric aspects of functional analysis, pp. 84-106. Springer, 1988.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connec- tions for efficient neural network. In Advances in Neural Information Processing Systems, volume 28, 2015. URL https://procedde neurips. wc/paaper/211///illee. aeCeb3eed3 aeCeb3eee3922beef422222 paw.aaeeeee.ateeeeeeeeeeeeee
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hen- nigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models. arXiv preprint arXiv: 15556, 2022. URL https:: /tts:///aaavv... wwwg/osaaa.o..ooooo. alss/ 2203 15556.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020. URL hattpa://arxet otgg/b/////....... 08361.
10

---

Published as a conference paper at ICLR 2023
Brett W. Larsen, Stanislav Fort, Nic Becker, and Surya Ganguli. How many degrees of freedom do we need to train deep networks: a loss landscape perspective. In Internationall Confer- ence Learning Representations, 2022. URL https: httpps/:/ppeereeee...... wttprr/wwwwwweeeeorrreeeeeeeeeee net/forumffiet ChMLTGRR cU.
Matthew Leavitt. Blazingly fast computer vision training with the mosaic resnet and composer, 2022. URL https:/ www. www.imss....... wwt.bcoo///oc//o...o.c.oo.o.oo.o mooog//mosiiiooooooooooo resnet.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neurul informa- lion processing systems, 2, 1989. URL
neurips ps. cc/paper/ .dff.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. SNIP: SINGLE-SHOT NETWORK
PRUNING BASED ON CONNECTION SENSITIVITY. In International Conference on Learn- ing Representations, 2019. URL https: http///pppeeeeeeeeeeeeeeeeeeeeee net/ forum ? BididdddBBjaAAA
Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. International Conference on Learning Representations, 2018. URL,
https: reperreviee net forum? d=ryup8-WCV,
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. International Confer- ence on Learning Reprexentations, 2018.
Clara Na. Sanket Vaibhav Mehta, and Emma Strubell. Train flat, then compress: Sharpness-aware minimization learns more compressible models, 2022. URL https://arxiis org/ abs/ 2205. 12694.
Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34:20596-20607, 2021. URL https: httpss:/ppooceddingg http:///pcoceee..eeeeee
cttpscccpppppeee cc/paper/
Mansheej Paul, Brett W Larsen, Surya Ganguli, Jonathan Frankle, and Gintare Karolina Dziugaite. Lottery tickets on data diet: Finding initializations with sparse trainable networks. arXiv preprint arXiv:2206.01278, 2022. URL https: http://wxvvvv.ro. org/ abs/ 2206. 01278.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in a randomly weighted neural network? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 18993-19902, 2020.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference Learning Representations, 2020. URL https: //oppnreview.neeeeeeeee
ferss/forummiee stt.orummmdiiigsooooo111 JONKV.....
Pedro Savarese, Hugo Silva, and Michael Maire.
Winning the lottery with contin- uous sparsification. Advances in Neural Information Processing Systems, 33:1 11390. 2020. URL
Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. arXiv preprint 2rX.v:2206.14444 2022.
URL wwwtthtts//// /ttt://axxxxe /aaxiiiiii org/ aas//b//// /20 14486.
Kartik Sreenivasan, Jy-yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang, Kang- wook Lee, and Dimitris Papalliopollos. Rare gems: Finding lottery tickets initialization. arXiv preprint arXiv:2202. 2022. URL
.ogg abs 2202. 12002.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruming methods: Random tickets can win the
jackpot. Advances in Neural Information Processing Systems, 33:20390-20401, 2020.
URL https:://prooeedngss.ut wwwp:eiww.n..nnninnnoooe.......e
httee///ps..ccpppp////////////// aaaape//0200/1eee. .dd.
11

---

Published as a conference paper at ICLR 2023
Hidenori Tanaka, Daniel Kunin, Daniel L Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in Neural Information Processing Systems, 33:6377-6388 2020. URL https: h/pooceei/..ccoccgg..... neurips ec/
paper/2020/ e 05 oag.eeeee00.ctttooeeoeeeeaeaeeee pddf.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by
preserving gradient flow. International Conference on Learning Representations, 2020. URL
https://openrewe
net/ forum?id-SkgsACCT
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of hessian. 2020 IEEE international conference on big data (Big data), pp. 581-590. IEEE, 2020.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tick- ets: Zeros, signs, and the supermask. Advances in neural information processing sys- tems, 32, 2019. URL https://proceeddin neurips.................. httpaaaass..ccppppe/////////a//e 1113d7a76 o htt.:caaee...aaaooooooooeeeaaaa-
pdf.
Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint 171001770 2017. URL https:/ /ttps:///xxvv..///////
abs/17100 01878.
12

---

Published as a conference paper at ICLR 2023
A EXTENDED RELATED WORK
Rewind point. Frankle et al. (2020a) observed that, for larger datasets and architectures, IMP fails to find matching subnetworks random initialization. However, matching subnetworks can instead be found after briefly training the dense network and using these new pre-trained weights as the rewind point. The authors further observed that the rewind step at which matching subnetworks emerge strongly correlates with the onset of linear mode connectivity in the pruned network. They hypothesize that IMP is able to find matching initializations once SGD has "stabilized" in the sparse network's is subspace. Follow up work by Paul et al. (2022) characterized the role of data in this pre-training stage, and analyzed what information is encoded into this rewind point by the dense network training. The rewind step alone, however, cannot explain IMP's success because random masks applied to this point do not produce matching lottery ticket initializations (Frankle et al., 2020a). Therefore, in addition to the information encoded in the rewind point, there must be some critical information encoded in the mask itself.
Masks constructed at the end of training. Significant attention has focused on trying to find matching subnetworks early in training or at initialization without information after convergence (e.g., Lee al., 2019; Wang et al., 2020; Tanaka et al., 2020). Despite lot of progress, these early pruning methods fall short of finding matching initializations (Su et al., 2020; Frankle et al., 2021). I). As far as we know, key component of the success of IMP remains the use of information from the end of training to construct the mask (e.g., Zhou et al., 2019; Frankle et al., 2020a; Ramanujan et al., 2020; Savarese et al.. 2020; Sreenivasan et al., 2022).
Our work identifies the mechanism by which IMP finds matching solutions: the algorithm maintains the information from the dense network about the loss landscape by encoding this information into the mask. Evci et al. (2022) report similar findings but for a different setting. In their work, they construct sparse masks from a pruned solution (sparse network trained to convergence), where the latter is obtained through gradual magnitude pruning (GMP) throughout training (Zhu & Gupta, 2017) as opposed to IMP. They find that the resulting sparse subnetwork lies in the same basin (i.e.. no error barrier pruned solution does not match the accuracy obtained by the dense solution, which is one of the key properties of sparse subnetworks studied in our work. These results hint at the larger picture explored in this paper about the full sequence of matching networks of increasing sparsity found by IMP being piecewise linearly connected in the error landscape.
connecting linear path) the original pruned solution. Note that the GMP
Iterative pruning with retraining. An essential part of IMP is that the weights are pruned itera- tively with periods of retraining between them. For standard training without rewinding, Han et al. (2015) show that one-shot magnitude pruning cannot find subnetworks of the same sparsity as it- erative magnitude pruning; Frankle & Carbin (2018) show the same for the lottery ticket setting in which weights are rewound to their values from early in training after pruning. Alternative meth- ods that attain matching performance at the sparsity levels as IMP also feature iterative pruning and retraining (Renda et al., 2020; Savarese et al., 2020). In this work, we take the first step towards understanding why the iterative piece of IMP is critical for finding high sparsity and yet matching subnetworks.
Finetuning and learning rate rewinding. In the IMP-WR framework proposed by Frankle et al. (2020a) after each pruning step the network is rewound that point on the network is retrained with the new sparsity pattern. One can alternatively consider methods that train from the final model after pruning rather than this rewind point. We refer IMP- FT as training the pruned final model with the same final learning rate. Renda et al. (2020) show that this finetuning underperforms IMP-WR in final test accuracy. To alleviate this, Renda et al. (2020) propose a middle ground between IMP-WR and IMP-FT called learning rate rewinding (IMP-LRR). In IMP-LRR, the final pruned model is trained for the same amount time as the original training run and with the original learning rate schedule, but starting at the weights at convergence instead of rewinding to w,. As shown in Renda et al. (2020), this produces networks that perform equivalently to IMP-WR.
early rewind point w,, and from
Pruning flat directions. The basic idea of pruning the weights that are aligned with "flat" direc- tions in the optimization landscape dates back to late 1980's, and was explicitly described in the
13

---

Published as a conference paper at ICLR 2023
work introducing optimal brain damage (LeCun et al., 1989). The motivation is based second order Taylor expansion of the optimization objective g(w, S). In more detail, for an axis-aligned perturbation captured by mask m,
g(m @ S) g(w,S) = ((1 m) w) dg(w.S) + ((1 m) w) T m) ④ w), (A.1)
dw
where H d', ddw This requires computing all Hessian entries (i,j) for which (m),, (m), = O. Finding masks that minimize the change in the optimization objective g(w, S) requires computing the full spectrum of the Hessian and identifying the smallest eigenvalue direc- tions. This is prohibitively expensive in modern deep neural networks. Last but not least, ideally we want to look at the empirical error error landscapes instead, which are not differentiable.
B EXPERIMENTAL DETAILS
CIFAR-10 ResNet-20. We train with SGD and batchsize of 128 for 62400 steps. We use Ir 0.1, momentum = 0.9, weight decay = 0.0001. The learning rate is decayed by a factor or 10 at 31200 and 46800 steps. We run 12 rounds of pruning and prune 20% of the smallest magnitude weights at each round. After each round of pruning, the weights are rewinded to O, 250, or 2000 steps and then retrained with the sparsity mask corresponding that level. For each rewind step we plot the mean and standard deviation of the final test accuracies across 4 replicates with independent random seeds.
CIFAR-100 ResNet-18. We train with SGD and batchsize of 128 for 78125 steps. We use Ir 0.1. momentum = 0.9, weight decay = 0.0005. The learning rate is decayed by factor or 5 at 23438, 46875, and 62500 steps. We run 15 rounds of pruning and prune 20% of the smallest magnitude weights each round. After each round of pruning, the weights steps and then retrained with the sparsity mask corresponding to that level. For each rewind step we plot the mean and standard deviation of the final test accuracies across replicates with independent random seeds.
rewinded to 0, 400, or 3200
ImageNet ResNet-50. We train with decoupled SGD (Loshchilov & Hutter, 2018 8) and a batchsize
of 2048 for 15970 steps. We use Ir = 2.048, momentum = 0.875, weight decay = 0.0005. We use cosine decay for learning rate scheduler with warm-up of 5000 steps. We use additional algorithms to speed up the training as described by Leavitt (2022). We run 12 rounds of pruning and prune 20% of the smallest magnitude weights at each round. Additionally, After each round of pruning, the weights are rewinded to O, 1250, or 5000 steps and then retrained with the sparsity mask corresponding that level. For each rewind step we plot the mean and standard deviation of the final test accuracies across 4 replicates with independent random seeds.
Pruning. Following Frankle & Carbin (2018), in all our pruning experiments, the prunable pa- rameters are weights of the convolutional layers and the fully-connected layers. For experiments involving interpolation, we interpolate all parameters (both prunable and nonprumable parameters) within the convex hull of the models. When extrapolating outside the convex hall, we only ex- trapolate the prunable parameters and the non-prunable parameters are projected onto the closest boundary of the convex hull.
Error Connectivity of IMP Solutions. (Fig. 2) In Fig. 2, we consider the error along linear paths between pairs of solutions found by IMP. The solution level obtained after the Lth iteration of Algorithm 1 for a given rewind step. Given two IMP solutions, w(L)) and w(),, we calculate the error along the linear interpolation of the solutions: E((1- (B) + (k)))), where 3 E [0, 1]. Typically, we evaluate beta at (0.1,0.2, ..., 0.9). We plot the test error along this path between IMP solutions (4) and w wL++1) For all results we show the mean and standard deviation of 4 independent runs.
For the heatmap, between each pair of solutions given by row and column j. we calculate max; E((1 - (() + Bw(i)). This is also the mean of 4 runs. The darkest limit of the color- bar is set to the e-matching threshold.
14

---

Published as a conference paper at ICLR 2023
Error landscape of an IMP step. (Fig. 3) we evaluate the test error on the two-dimensional plane spanned by points at each level L: the level I. solution w(L), its level projection m (L++1) @ w(2) and the level + solution w(L+1). We construct 51 x 51 grid and evaluate the error on the the grid. The contour is plotted for the matching error at each level for every dataset. For better visualization, we use different scales for the vertical and horizontal direction each level. We fix the the positions of the level L projection m m(<+1) @ w() and the level L+1 solution w(++1) on each plot and scale the orthogonal direction by times. We show the error landscape for all the levels in Fig. 17 19.
To investigate the enror landscape of an IMP step,
Robustness at rewind point. (Fig. 4) In this experiment, we compare the error barriers between two IMP solutions and an IMP solution and the trained solution after random perturbation. For each level, the blue lines are the error barrier between the IMP solution at Level L and the IMP solution at Level L+1. These are just the midpoints between the successive level interpolations in Fig. 2. To obtain the orange points, we first calculate the distance of the projection when the magnitude pruning mask obtained by pruning the Level L IMP solution is applied to the rewind step. In the conceptual figure accompanying Fig. 4, this is represented by p. We then apply a random perturbation to the rewind step in the full D'D dimensions of the Level L solution and train to convergence. The orange points are the test error halfway along the line connecting this solution and the original Level I. IMP solution. All results show the mean and standard deviation of 4 independent runs.
Threshold training dimension. (Fig. 5) We first estimate an appropriate (L) for linearly con- nected training loss sublevel set for level L. We perform random pruning at level 4 and record the train loss and test error. We repeat the procedure and linearly fit loss versus error to get the train
loss Lmacching corresponding to the test eπrоr Edense for the dense network. We then determine (LL) by subtracting the train loss level L solution from Lmatching. At each level, we use the PyHessian package (Yao et al., 2020) to estimate the Hessian eigenspectrum density of the train loss (average across 4 runs 512 Lanezos iterations for CIFAR- and runs of 128 Lanezos iterations for Ima- geNet; we randomly sample 25000 examples from ImageNet to evaluate the train loss for each run). In Fig. 5, the theory lines are generated from Lemma 3.1 with the estimated Hessian eigenspec- trum. To verify the theory, we perform series of pruning experiments each level L. We scan the pruning ratio from 0.1 to 0.9 with a step of 0.1 for both magnitude pruning and random pruning and check if the L ++] solution is matching. The projection distance from pruning is calculated as R [|w[[++1= - w())
Small weights are correlated with flat directions. (Fig. 6) We find that magnitude pruning outperforms the theoretical prediction. To investigate the reason, we study the properties of the LCS-set. In Fig. 6 and 20), we visualize the error landscape in the subspace spanned by a random projection and the magnitude projection (both for a 20% pruning ratio). We construct a 51 x 51 grid and evaluate the еигоr the the grid. The contour is plotted for the matching error at each level for every dataset. We use the same scale for both directions and for each level. Generally, the random pruning projection is not orthogonal to the the magnitude pruning projection and we have performed Gram-Schmidt procedure to figure out an orthogonal basis.
The importance of iterative pruning and retraining. (Fig. 7) In Fig. 7, we plot the CDF of weights at level I. projection (L) (L-11) We perform three different training procedures level L: retraining from the rewind point (weight rewinding), Fine'Tuning and Learning rate Rewinding and we plot the CDFs of the solution obtained from these three training procedures. When we plot the CDF, we normalize the absolute values of the weights by their means. For Learning Rate Rewinding, we rewind the original learning rate schedule and run the training for the same amount of time the original run. For Fine Tuning, smaller than the peak learning rate of the original run. We also turning off the weight decay for Fine Tuning.
learning rate of 0.02, which is 100 times
15

---

Published as a conference paper at ICLR 2023
C THRESHOLD DIMENSION
For completeness, we summarize the result presented in (Larsen et al., 2022). Let E RDx be random Gaussian matrix with columns normalized to 1, w, E RD. be weight configuration, and S be the set in I2 (typically a sublevel set of the loss function). Then we are consider the quantity:
P. P.=P(sn { {w, + (p)an(A)} * o/-
(C.1)
Lee the probability that the Gaussian affine subsapce defined by A, w. intersects the set S. We are then interested understanding the minimal dimension for which an intersection occurs with high probability or the threshold training dimension.
Definition C.1 (Threshold training dimension).
The threshold training dimension d' (S, t, 8) is the 6 for some small ō > 0.
minimal value of d such that P.
Their main result bounds the threshold dimension of an affine subspace, such that this subspace intersects a target set M with high probability. The proof uses Gordon's Escape Theorem (Gordon, 1988), and depends on the Gaussian width of the projected set M.
Definition C.2 (Gaussian Width). The Gaussian width of a subset M C. CR" is given by:
-yx-)), 1 sup (g.x- y), g ~ N(0,IDxD).
r(M)
2 x.EM
The local angular dimension is then the Gaussian width of M projected onto the unit sphere around the subspace offset:
Definition C.3 (Local angular dimension). The local angular dimension of a general set M R about a point w is defined as
dhoead (M, w) =
(M)).
(C.2)
where proj (M) denotes projection of set M onto a unit sphere centered at w:
proj = {(x - w)/l x w/12: E M).
The threshold training dimension is finally obtained by taking D minus the local angular dimension.
d' D dhocal (M, w).
(C.3)
Intuitively, this relation means that the closer one gets to the set, the larger it's projection on the surrounding unit sphere will be, and hence the lower the dimension of the subspace that will be required to hit the subspace with high probability.
For neural network loss landscapes, this local angular dimension is challenging compute. How- ever, an analytic bound for the threshold training dimension can be derived in the case of a quadratic loss function L(w) fw" w Hw where Rdd and H E RDxD is symmetric, positive definite Hessian matrix with cigenvalues {AI....,Ap) This loss function can be used as a second-order approximation of the loss landscape surrounding minima. The lower bound on the local angular dimension of S(z) about w is given by:
AD).
2 R2 +
diocal (5, R) = w N
Σ
(C.4)
where r, X2
D IMP-LRR SUBNETWORKS CAN BE RETRAINED FROM AN EARLY REWIND POINT
IMP with learning rate rewinding (IMP-LRR) has been shown to exceed the performance standard fine tuning, and match the performance of IMP-WR (Renda al., 2020).
16

---

Published as a conference paper at ICLR 2023
Both IMP-LRR and IMP-WR can be used to find matching subnetworks. However, IMP-WR has special property: it can be retrained from an iteration early in training.
Let T denote training step from which IMP-WR works (i.e., the onset of lincar mode connectivity). Here we further show that a mask m that gives a matching subnetwork with learning rate rewinding will also give matching subnetwork @ W,, iee. the subnetwork can be rewound back to t and retrained to the same error.
The results presented in Fig. 8 show that IMP-LRR-obtainee subnetworks not only matching with learning rate rewinding, but can also be retrained from the same rewinding iteration as IMP- WR subnetworks, and obtain the rewind point. In other words, IMP-LRR subnetworks perturb the network at the rewind point within the stability limit (see Section 3.2 for more details).
error. This is due to the stability up to perturbations the
CIFAR-10 ResNet-20
ImageNet ResNet-50
Test Error (%)
10
23
8
22
2
4
6
8
10
12
0
4
6
8
10 12
Level (Higher Sparsity -+)
Level (Higher Sparsity -)
E-Matching Thresh.
LR Rewind
- LR-Rewind Retrain
Figure 8: At each sparsity level (x-axis) train the same sparse subnetwork obtained via IMP-LR under two conditions: we train the network with learning rate rewinding after pruning (standard IMP-LR, blue line), or we train the network by first rewinding it to a stable rewind point (like in standard IMP-WR, orange line). We evaluate the error of the resulting trained network (y-axis). The overlap between the two curves suggests that IMP-I. mask can be retrained from stable rewind point and match the performance of standard retraining with learning rate rewinding. In other words, IMP-LR produces masks that can be retrained from a point early training.
E LEARNING RATE REWINDING VS. FINE TUNING
We refer FINE TUNING training the pruned final model with the same final learning rate. Renda et al. (2020) show that fine tuning underperforms IMP-WR in final test accuracy. To alleviate this, Renda al. (2020) propose middle ground between IMP-WR and FINE TUNING called IMP with LEARNING RATE REWINDING (IMP-LRR). In IMP-LRE the final pruned model is trained for the same amount of time the original training run and with the original learning rate schedule, but starting at the weights at convergence instead of rewinding to w.- As shown in (Renda et al., 2020), this produces networks that perform equivalently IMP-WR.
Fig. 9 compares fine tuning and IMP-LRR on CIFAR-10 and ImageNet. We show that IMP-LRR achieves a lower test error than fine tuning across sparsities, which can be explained by weight reequilibriation IMP-LRR maintains larger fraction of small weights compared to fine tuning.
F A SIMPLE ADAPTIVE PRUNING HEURISTIC FOR OPTIMIZING IMP
One of the limitations of IMP is its computational intensiveness. Pruning standard networks on standard benchmarks to the maximum sparsity achievable by IMP often involves retraining the net- work more than 10 times. For example, with standard hyperparameters and a 20% pruning ratio at each level, ResNet-18 trained on CIFAR- 100 requires 11 levels of pruning to achieve sparsity of 9% weights remaining. Note, specifically select this example because, among experimen- tal settings, a ResNet-18 trianed on CIFAR- 100 was able to train to the lowest fraction of weights remaining and required the most number of levels; speedup in this setting would be the most effective.
Part of the cost of IMP is due to the fact that 20% is not the optimal pruming ratio at every level at low sparsity levels the network can be pruned more aggressively and at high sparsity levels, the pruning ratio must be small to overshoot. 20% is often chosen balance between the high
17

---

Published as a conference paper at ICLR 2023
CIFAR-10 ResNet-20
ImageNet ResNet-50
Test Error (%)
11
20 %ile Weight
0.7
Test Error (%)
24
20 %ile Weight
0.7
10
0.5
23
0.5
0.3
22
0.3
12
6
12
10
8 Level (More Sparse
Level (More Sparse
Level (More Sparse -+)
Level (More Sparse
-)
E-Matching
IMP-LeamingRateeeewiddng --- IMP-FineTuning
Figure 9: Learning rate rewinding yields trainable matching networks and provides small weights to prune further, unlike finetuning. The left plots in each dataset panel show the test error achieved by learning rate rewinding (LRR) and fine tuning at each level. The right plots in each dataset panel show the magnitude of the 20th percentile weight (normalized by the mean weight that level so that we can compare across levels and strategies) at each level for both LRR and finetuning. With LRR, the 20th percentile weight is much smaller compared to finetuning, indicating LRR creates new small weights to further prune in a way that fine tuning cannot. In the retrain step, we finetune, the distribution of weights doesn't change much from the pruned model and there no small weights to prune (see also Fig. 7 and 22). This results in a large projection distance and thus we cannot find an intersection between the axial subspace and the LCS-set. On the other hand, with learning rate rewinding, the network weights achieve a new equilibrium and there will be additional new small weights to prune (see also Fig. 7 and 22). This explains why LRR is able to achieve higher accuracies.
CIFAR- 100 ResNet-18
23.0
Pruning Ratio
Fixed 40%
Test Error (%)
22.5
Fixed 30%
Fixed 20%
Dynamic
22.0
21.5
21.0
11
26
41
64
100
% Weights Remaining
Figure 10: Adaptive Pruming Heuristic: A simple heuristic (described in Appendix F) for adapting the pruning ratio each level (orange crosses) can yield 33% improvement in training compute compared to IMP with a fixed pruning ratio of 20% at each level (blue circles).
pruning ratios possible at low sparsity levels and the low pruning ratios necessary high sparsity levels since it is not evident priori what the appropriate pruning ratio at any given level is.
Insights from our investigation of the error landscape at each IMP step (Fig. 3) suggests a natural heuristic for determining the optimal pruning ratio; choose a pruning ratio that keeps the pruned solution within the LCS-set of the unpruned solution. This guarantees that we will find an axial subspace that intersects with the desired LCS-set and at low sparsity levels, this effectively allows us to prune larger fractions of the weights. However at higher sparsities, this heuristic may result in multiple iterations of pruming small fraction of the weights as even small perturbations take us out of the LCS-set. Additionally, we don't have access to the test error at training time and so cannot directly determine when have pruned out of the LCS-set. To overcome these challenges, design our heuristic as follows:
1. Estimate an appropriate e for a linearly connected training loss sublevel set. We estimate this using the standard deviation of the training loss across batches over the last epoch of training the dense network. We will refer to this as the train LeS-set. Our threshold for leaving the train LCS-set is thus the training loss of the dense network + the estimated e.
18

---

Published as a conference paper at ICLR 2023
2. At the Level L solution, sweep pruning ratios of 10%, 20%, ... to find the maximum pruning ratio p such that level L solution after pruning remains within the train LCS-set, i... the training loss along the linear path between the Level L solution before and after pruning is less than the threshold estimated in step 1.
3. We will use the p found in step 2 as the new pruning ratio of IMP in this level (if p > 0.2, or otherwise we will use 20% as the pruning ratio), i.e. we prune max 0.2) of the smallest magnitude weights and start the retraining step of IMP.
As demonstrated in Fig. 10, this heuristic of choosing dynamic pruning ratio indeed reduces the compute by approximately 33%-we only need retrain 7 instead of 11 times without losing any accuracy, and at each level, the cost of determining the pruning ratio involves just few forward passes through (possibly a random subsample of) the training set.
This heuristic is especially effective when pruning ratio of 20% is much smaller than the optimal pruning ratio. However, in datasets suchs as ImageNet, the improvement is moderate because the optimal pruning ratio at early levels is already close to 20%.
Note: we do not claim that this an optimal algorithm, our goal in this work is to achieve deeper scientific understanding of IMP, this heuristic is just one of the many ways we can use these insights to improve the algorithm. We leave the task of fully exploring and characterizing these avenues to future work.
G PRUNING A DENSE NETWORK
In our experiments investigating linear mode connectivity of trained IMP solutions at different levels (Fig. 2 and 16), we find that the Level 0 (dense) solution is separated from the solutions at higher levels by small but non zero error barrier. In fact, for rewind steps at which we can find matching sparse networks of high sparsity, there always exists a piecewise linear path that interpolates between solutions at successive levels with 0 error barrier. Only for CIFAR-10 10, does this extend to the level solution.
An interesting question that challenges our hypotheses is, why are we not connected to the dense network? The answer lies in Fig. 4hehe dense network is not robust to perturbations at the rewind- ing step used in our experiments. When we perturb the dense network at the rewind point by distance equal to the norm of the projection induced by the level mask and train in the full dense space, the resulting solution is not linearly mode connected to original level O solution. In fact, at this rewind step, the dense network isn't even linearly mode connected (robust to SGD noise); Frankle et al. (2020a) find that IMP can find matching solutions after the onset of LMC in the sparse axial subspace which typically occurs before the onset of LMC in the dense space. As observed in Figure 16, as the rewind step increases, the error barrier between level 0 and level I gets smaller.
This result further underscores the importance of robustness to perturbation at the rewind step that observe in Fig. 4. At level 0, even though have an 80% sparsity axial-subspace that intersects the LCS-set of the level 0 solution, since the network is not robust to perturbation at the rewind step, we train to a level 1 solution in a different basin with a small error barrier to the level solution.
However, this begs the question, why at level I do we not need to train into the same LCS-set as the level 0 solution? At level 1, we are still in a massively perrpparameterized regime with 80% of the weights remaining. We can thus find a solution in this space that is as good as the solution level O. Indeed if the weights are rewound having a random network with 80% sparsity, we get the same error Fig. 15. This is not true at high sparsities-if at later level, we are unable to find an intersection with the I.CS-set of a matching network, then it is difficult to find different matching solution in that sparse space sparse training without explicit knowledge of the end-point is still a difficult task.
initialization, which essentially equivalent to
What is surprising is that, the actual error barriers between a level 0 and level I IMP solution (blue point in Fig. 4 at level 0) is actually much smaller than the error barrier between the original level 0 network and randomly perturbed network (orange point in Fig. 4 at level 0). Thus the IMP mask projection creates a perturbation that is more stable than a random perturbation. Investigating why this is true is left to future work.
19

---

Published as a conference paper at ICLR 2023
H ERROR LANDSCAPE GEOMETRY OF ITERATIVE GRADIENT PRUNING
In this section, we show that our key observation, all matching networks are in the same LCS Set, holds for Iterative Gradient Pruning (IGP). IGP is a common iterative pruning strategy similar to IMP, except, at each pruming step, instead of pruning weights with the smallest magnitude, we prune weights with the lowest absolute value of (weight X gradient) (Blalock et al., 2020). Fig 11 shows the results of using IGP instead of IMP in the same setting as in Fig. 2. IGP does not perform as well IMP-it ceases produce matching subnetworks at earlier levels of pruning. However, pairs of solutions at successive levels do not have an error barrier between them and all matching solutions are in the same LCS when IGP rewound to step 2000. This suggests that finding pruned solutions in the LCS set of the dense solution might be general feature of iterative pruning algorithms that start with trained dense network and consrtuct nested subnetworks each iteration.
CIFAR-10 ResNet-20
Test Error (%)
90
10 ResNet-220
Test Error (%)
10.0
10.6
Test Eror (%)
9.5
10.2
50
9.0
9.8
8.5
9.4
30
8.0
10
9.0
10
7.5
12
8.6
10 Level (Higher Sparsity +)
2
6
10
0
1012
Level (Higher Sparsity +)
Level (Higher Sparsity +)
Rewind Init
Early Rewind Step
Matching Rewind Step
e-Matching Thresh.
Same plots as Fig. 2 but for Iterative Gradient Pruning (IGP) on CIFAR-10 ResNet-20. 20% of the weights are pruned at each step. Though IGP stops being matching at lower levels compared to IMP, the matching networks all lie the same LCS set.
Figure 11:
To further investigate the reason why the performance of IGP is inferior IMP, calculated the Hessian along the directions given by three different pruning algorihm--Megnitude Pruming, Ran- dom Pruming and Gradient Pruming. (Fig. 12) We found that both Magnitude Pruming and Gradient Pruning found flatter directions than Random Pruning. In fact, Gradient Pruning found directions of similar sharpness (Hessian along the given direction) Magnitude Pruning. However, because Magnitude Pruning aims to prune the smallest magnitude weights, the fractional distance (defined in Eq. I.I) of the projection is smaller than the one given by Gradient Pruning. According our theory (Sec. 3.3), IGP would break down before IMP.
CIFAR-10 ResNet-20
Fractional Distance
0.5
Sharpness
10-2
0.4
0.3
10-3
0.0
0
2
4 6
8
10
0
4
8
10
Level (Higher Sparsity +
Level (Higher Sparsity )
Magnitude Pruning
Pruning
Gradient Pruning
Figure 12: Gradient Pruning direction is of similar sharpness Magnitude Pruning direction but its fractional distance is larger than Magnitude Pruning. We looked at three different pruning algo- rithms each level of an IMP experiment. We compute the Hessian along the pruning direction on the training dataset (left) and the fractional distance as defined in Eq. (right), Although Gradient Pruning can find similar flat direction, its fractional distance is larger, resulting the poor perfor- mance of IGP compared with IMP, which is expected from our theory in Sec. 3.3. All results were averaged over four replicates.
20

---

Published as a conference paper at ICLR 2023
1 ADDITIONAL EXPERIMENTS ON THE ROBUSTNESS OF SGD
CIFAR-10 ResNet-20
Run Replicate
Replicate
10.0
10.0
9.5
9.5
9.0
Test Error
9.0
8.5
8.5
8.0
7.5
4
10
2
10
Level (Higher Sparsity
Level (Higher Sparsity ->
c-Motching
IMP Projection
Random Perturbation
Figure 13: Sensitivity of SGD Robustness to Number of Runs. For CIFAR-10 ResNet-20 we re- peat the experiment Fig. 4 but with more runs test its sensitivity. All experiments are conducted for 4 replicates that use independent seeds. Left: identical to the middle plot in Fig. 4, reproduced for comparison. One random perturbation was performed per replicate, means and standard devi- ations are calculated across the 4 replicates. Right: We use 4 independent random perturbations per replicate. The mean and standard deviation of the orange line calculated across a total of 16 runs (4 runs each for 4 replicates). The results are extremely similar suggesting that exploring one random perturbation per replicate is reasonable given computational constraints.
Level
Level 1
Level
0.11
0.11
Midpoint Ernor
0.32
Midroit Enror
0.10
0.11
Miggont
0.10
0.10
0.09
0.88
0.08
0.00
0.6 Fractional Distance
Fractional Distance
Fractional Distance
IMP Projection
Random Perturbation
e-Matching
Figure 14: SGD Robustness to Perturbations of Varying Lengths. On CIFAR-10 ResNet-20,, for the first 3 levels of IMP (in the titles), we look at the robustness of SGD to random perturbations of various lengths compared IMP mask projections to subsequent levels. Fractional distance on the x-axis is measured as the ratio of norms of the perturbation//rojectiio and the weights at the the error at the midpoint the line in weight space
rewind point. Midpoint error is measured connecting the trained network from the rewind point and the trained perturbed/proojeteed network. Surprisingly, at high sparsities, SGD is robust to large random perturbations.
In this section, further explore the robustness properties of SGD. Recall that in Section 3.2, found that, when the rewind point is projected onto the new axial subspace, SGD finds the desired LCS set of the previous IMP solution with high probability because even a random perturbation of the same magnitude will train to the LCS set with high probability. Thus, the ability of SGD to extract the location of the LCS set from the mask follows from the general robustness of SGD late in training.
In Fig. 13 we verify that our results are still valid we perform more random perturbations and in Fig. 14 we look at the effects of the random perturbation distance at a given sparsity level on the robustness of SGD.
Experiment 1, Fig. 13: In this experiment CIFAR-10 ResNet-20, we add more random per- turbations to our experiments to verify that our results hold in general and are not an artifact of insufficient sampling. Fig. 13 left is identical to Fig. 4 middle column, reproduce it here for comparison. Fig. 13 right is the new experiment with more perturbations. Both figures use 4 inde- pendently trained replicates to calculate the mean and standard deviation of both the IMP projection
21

---

Published as a conference paper at ICLR 2023
and the random curves. In the left plot, for each replicate only sample random projection. On the right plot, for each replicate we sample 4 independent random projections. For the orange curve, we then average over all the random projections for each replicate for total of 16 runs. The blue curves are still the 4 replicates for IMP; there is no additional degree of freedom to sample over. The experimental setup is otherwise the same as described in Fig. 4 and section 3.2. The results very similar suggesting that the robustness of SGD is indeed a true phenomenon and not an artifact of insufficient sampling.
We now look at the dependence of the robustness of SGD to random and IMP perturbations on different lengths at early IMP levels for CIFAR- 10 and ResNet-20. In Fig. 14, the 3 columns correspond to experiments performed at the first 3 sparsity levels: level 0 = 100% weights remaining, level 1 80% weights remaining, and level 2 = 64% weights remaining, Since IMP creates a sequence of nested subspaces, we can examine any level L the projection of the rewind point onto the axial subspaces of levels L + 1, L + 2, and so on. The blue curves in the figure correspond these IMP projections. Specifically, at level L, denoted in the title, consider
Experiment 2, Fig. 14:
the projection distance of (4) O w onto the axial subspaces of m ml(+1)) m m4(+2) The x-axis corresponds to these distances fraction of the norms of the weights given by
m (L) W m((+)) Wr ll2
(I.1)
(m(2) @ wrll2
for k = 1,2,3, .... The y-axis is the test error at the midpoint interpolation between the correspond- ing IMP solutions w(() and w-(--R) for k 2, Not this is different from Fig. 4 as instead of looking at the midpoint between solutions at subsequent levels, we are looking at the midpoints between the solution at the current level and all following levels. The black línes correspond the matching threshold: if a point is below that line, it means that the two corresponding end points are in the same seS- The blue curves show how the mask projection distance at the rewind point affects whether two networks at different levels train into the same LCS-set. As expected, they do until we reach the last few levels. The mean and standard deviation is calculated across independent replicates.
The orange curves show the relationship between the length of random perturbations at the rewind point in the m(..) space and whether the networks before and after the perturbations train to the same LCS-set. Specifically, at each level L, denoted by the title, we apply a random perturbation v of length e to m (L) @ W.. The length e is chosen to have the correct fractional length in the x-axis and the direction chosen uniformly from all directions in the L-dimensional axial subspace given by (f.) This perturbed network is then trained in the m(.) subspace for T steps to get Φ A,(m, (m(() @ W. + v,T r). The y-axis plots the test error at the midpoint between this trained network w and the IMP solution at (4),, For points along the orange curve that are below the black line, the network obtained from applying a random perturbation of the given length to the level L rewind point will train into the LCS-set of the level L IMP solution. The mean and standard deviation is calculated across 4 independent replicates.
For the higher levels, we find that the LCS set the network trains into is robust to large perturbations at the rewind point. In fact, the network is robust to random perturbations that are larger than the IMP mask projections of all successive matching levels. This provides further evidence for the role of SGD robustness in enabling the pruned network to train back into the LCS set of the previous IMP solution. Note that an IMP mask projection of given length may not find a matching solution because the subspace corresponding to the mask may not intersect with the desired LCS-set. However, a random perturbation of the same length might train into the desired LCS-set as training is happening in the finter--imensionall space that we know contains this set. Also the results from Level have large error barrier between the networks before and after random perturbation for the same reason as described in Appendix G.
J FULL RESULTS
Here we present the full set of experiments performed for the results in the main text as well as extensions to additional datasets.
22

---

Published as a conference paper at ICLR 2023
CIFAR-10 ResNet-20
CIFAR-100 ResNet-18
ImageNet ResNet-50
28
Test Error (%)
11
25
26
10
24
9
24
22
8
22
12
Level (Higher Sparsity - Level (Higher Sparsity )
Level (Higher Sparsity -)
Rewind init
Early Rewind Slep
Matching Rewind Step
Matching Accuracy
Figure 15: Error and Rewind Steps for IMP. Purple curves show rewind step 0. Orange curves show early rewind steps (250 for CIFAR-10, 400 for CIFAR-100, 1250 for ImageNet) and the green curves show rewind steps that produce sparse matching subnetworks (step 2000 for CIFAR-10, 3200 for CIFAR- 100 and 5000 for ImageNet).
CIFAR-10 ResNet-20
10.6
10.0
Test Error (%)
70
9.5
10.2
Test Error (%6
50
9.0
Level
8.5
9.4
8.0
10
9.0
7.5
12
8.6
2
10
12
1012
ImageNet ResNet-50 CIFAR- 100 Res
100
24
Test Error (%)
Test Test Emro (%)
24
23
60
22
10
23
12
20
21
14
0
2
8
10
12
14
2
4
6
8
10
12
14
0
4 6
801214
100
25.0
Test Error (%)
24.0
Test Emor (%)
24.5
23.5
Level
60
23.0
24.0
22.5
23.5
10
22.0
20
12
23.0
0
2
8
10
12 )
2
4
6
10
12
2 4 8 1012
Level (Higher Sparsity
Level (Higher Sparsity -)
Level (Higher Sparsity -)
Rewind to Init
Early Rewind Step
Matching Rewind Step
e-Matching Thresh.
Figure 16: 50.Net-50.
The same plots as Fig. 2 on CIFAR-I0 ResNet-20, CIFAR-100 ResNet-18. and ImageNet
23

---

Published as a conference paper at ICLR 2023
CIFAR-10 ResNet-20
Level
Level 2
9.8
9.4
Test Erro (%6
9.0
8.6
8.2
7.8
Level 4
Level 5
Level 6
Level 7
9.4
Test Error (%)
8.6
8.2
7.8
Level
Level 9
Level 10
Level 11
Test Error (%6
A
A Level Level Projected
Matching Thresh.
Axial Subspace
Projection
Figure 17: All the projection levels for CIFAR-10. The two-dimensional slice of the loss landscape determined by each level L by points: the solution found level L (grey triangle), the projection of this solution (orange circle) onto the axial subspace determined by the smallest weights (blue dotted line), and the solution found at level + by retraining with the mask (pink cross). Note that by definition, the L + solution must also lie on the axial subspace. The light dotted black line outlines the E sub-level set.
24

---

Published as a conference paper at ICLR 2023
CIFAR-100 ResNet-18
Level 0
Level 1
Level 2
Level
Level 4
Test Error
23
22
21
Level 5
Level 6
Level 7
Level
Level 9
24
Test Error (%)
23
22
10
Level 11
Level
Level
14
24
Test Error (%)
23
21
A Level L Soln. Level L Projected
Level L+1 Soln.
Matching Thresh. Axial Subspace
Projection
Figure 18: All the projection levels for CIFAR- 100. The wwo-dimensional slice of the loss landscape determined by each level by 3 points: the solution found level L. (grey triangle), the projection of this solution (orange circle) onto the axial subspace determined by the smallest weights (blue dotted line), and the solution found level L by retraining with the mask (pink cross). Note that by definition, the L + solution must also lie on the axial subspace. The light dotted black line outlines the sub-level set.
CIFAR-100 ResNet-18
30
E-Matching
28
IMP Projection
Test Error (%))
Random Perturbation
26
22
10 Level (Higher Sparsity -)
Figure 19: Stability to perturbations at the rewind point for CIFAR-100.
25

---

Published as a conference paper at ICLR 2023
CIFAR-10 ResNet-20
Level 0
Level 1
Level 2
Level
10.0
9.5
Test Error (96)
9.0
8.5
8.0
7.5
Level 4
Level 5
Level 6
Level
10.0
9.5
Test Error (96)
9.0
8.5
8.0
7.5
Level 8
Level 9
Level 10
Level 11
10.0
9.5
Test Error (%6
9.0
8.5
8.0
7.5
Prune 20% Smallest Weights
Prune 20% Random Weights
E-Matching Thresh
Figure 20: The same plots as Fig. but for CIFAR- 10 dataset. Projection of the error landscape
in the subspace spanned by random projection and small magnitude weight projection. Flat error directions correlate with small magnitude directions. The size the LCS-set decreases with in- creasing sparsity levels.
26

---

Published as a conference paper at ICLR 2023
CIFAR-100 ResNet-18
Level 0
Level 1
Level
Level 3
Level
24.0
23.5
Test Errr (%))
23.0
22.5
Level 5
Level 6
Level
Level 8
Level
24.0
23.5
Test Emor (%)
23.0
22.5
22.0
Level 10
Level
Level
Level 13
Level
24.0
23.5
Test Erro (%)
23.0
22.5
22.0
Prune 20% Smallest Weights
Prune 20% Random Weights
e-Matching Thresh
Figure 21: The same plots Fig. 6 but for CIFAR-100 dataset. Projection of the error landscape in the subspace spanned by random projection and small magnitude weight projection. Flat error directions correlate with small magnitude directions. The size of the LCS-set decreases with in- creasing sparsity levels.
CIFAR10 ResNet20
Level
Leve 4
Level 7
Level
0.3
0.2
0.2
0.2
CDF
0.1
0.1
0.1
0.1
0.0
8.00
0.25
0.50
0.75
0.0
0.00
0.25
0.50
0.75
0.0
0.00
0.25
0.50
0.75
0.0
0.00
0.25
0.50
0.75
ImageNet ResNet50
Level
Level
Level 7
Level 11
0.3
0.3
0.3
CDF
0.1
0.1
0.0
0.0
0.0
0.0
0.0
0.5
0.0
Normalized Weights
Normalized Weights
Normalized Weights
Normalized Weights
Weight Rewinding
After Projection
Learning Rate Rewinding
Finetuning
Figure 22: The same plots Fig. CIFAR-10 ResNet-20 and ImageNet ResNet-50. The zoomed out version shown in Fig. 23
27

---

Published as a conference paper at ICLR 2023
CIFAR10 ResNet20
1.00
Level 1
Level 4
Level
1.00
Level 9
0.75
0.75
0.75
0.75
0.50
0.50
0.25
0.25
0.25
0.25
0.00
0.00
0.00
0.00
ImageNet ResNet50
Level 1
Level 4
Level
Level 11
1.00
1.00
1.00
1.00
0.75
0.75
0.75
0.75
CDF
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.00
0.00
0.00
0.00
Normalized Weights
Normalized Weights
Normalized Weights
Normalized Weights
Weight Rewinding
At Projection
Learning Rate Rewinding
Finetuning
Figure 23: The same plots as Fig. 22 but showing the zoomed out version.
28


Reviews:
[{"review_id": "osJrGLPPcK4", "reviewer": "Reviewer_y14k", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper investigates iterative magnitude pruning (IMP) from the perspective of loss landscapes to answer questions such as why is it necessary to rewind the search iteratively rather than perform the pruning in one-shot fashion. The authors show that the IMP mask encodes the location of linearly connected modes (i.e. modes with low error barrier) containing matching sparse solutions. Further, the authors show that rewinding is necessary to “equalize” the weights to identify the next set of low-magnitude weights to prune. Finally, a link to the Hessian eigenvalue spectrum is established. The insights can lead to improved (faster) versions of IMP, one such version is proposed by the authors in the appendices.", "summary_of_the_review": "To conclude, I would be very sad if this paper is rejected, since it is definitely one of the best ones that I have recently reviewed or read. I think this work is potentially very impactful, and I believe that the loss landscape perspective provides an excellent lense to deeper our understanding of neural networks training and behavior.", "strength_and_weaknesses": "Strengths:\n* The paper studies IMP from the loss landscape perspective, the results are insightful and open up many future research directions.\n* The obtained insights have a very practical application (e.g. improving IMP).\n* The paper is very well written, the experiments are realistic.\n\nWeaknesses:\n* The paper does not link the observations to the attraction basins in the loss landscape, which to me feels like an important omission.\n* The appendices for the paper are extensive, and include such sections as related work, which seem better suited in the main body of the paper. In general, I think this paper would be more suited for a journal rather than a conference publication. However, I acknowledge that the ML community strongly favors top-tier conferences, and understand authors’ decision to compress their work into 9 pages. I commend the impressive effort, but honestly believe that the narrative would have benefited from a less stringent page limit.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Pbcf-Eij5Iq", "reviewer": "Reviewer_d22d", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper shed some light on the underlying principles that allow IMP to find winning tickets. In particular, the authors focus on four fundamental questions regarding the information provided by the mask, the need of an iterative procedure for pruning, and the differences between retraining, learning rate rewinding and finetuning.", "summary_of_the_review": "I think that this is a solid paper and it provides a significant contribution to explain the underlying principles of the lottery ticket hypothesis.", "strength_and_weaknesses": "I think that this paper is very interesting because it tries to answer to some fundamental questions related to the lottery ticket hypothesis, providing a significant contribution to the research in this field. The analysis presented in this paper is based on solid theoretical assumptions and validated by extensive empirical experiments. ", "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": "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": "HulRoXtUapf", "reviewer": "Reviewer_HZpf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides the interpretation of IMP method in terms of the loss geometry, to better understand why and how IMP finds winning tickets. It provides various interesting empirical results. The main finding is that whether we find a matching network or not is related with whether the subnetworks at successive rounds are linearly connected in the loss landscape. \n", "summary_of_the_review": "This is an interesting empirical work. Although we do not have sufficient theoretical explanation, it is good to share with the research community, given a proper comparison with existing iterative pruning methods. ", "strength_and_weaknesses": "* Strengths\n    * It provides extensive empirical results\n    * The interpretation provided in this paper makes sense.\n\n* Weaknesses\n    * It is mostly empirical, and is not providing theoretical insight.\n    * It compares with random pruning, but I'm curious the result for other pruning algorithms applied in an iterative manner. \n    * Although the result is interesting, we still don't know why simple \"magnitude-based\" pruning can find such flatter directions in the error landscape. \n \n", "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": "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": "2DFcrKfFmM", "reviewer": "Reviewer_vB9o", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates why iterative magnitude pruning (IMP) is successful.  The authors hypothesize that the masks discovered during iterations of IMP encode subspaces that intersect the linearly connected loss sublevel sets associated with the previous iterate.  They present multiple experiments to support this hypothesis.", "summary_of_the_review": "I would be inclined to accept this paper after revisions are made to properly address the literature in the main body of the paper and to make proper comparisons to the present work.\n\n\n", "strength_and_weaknesses": "**Strengths:** \n\nThe paper investigates the relevant problem of identifying the conditions for the success of IMP.  The hypothesis is appealing and is consistent with their data.  The figures are clear and readable.\n\n**Weaknesses:**\n\nThis paper lacks an adequate discussion of related work in the main body.  While they have a related work section in the Appendix, it is standard to have this section in the main body.  It is important for readers of the work to have these comparisons made clear.  Also note that reviewers for ICLR are not required to read the supplementary material for better or for worse, which makes it even more important for this section be included in the main body.\n\nThe paper makes many key claims (e.g. the six bullet points spanning the end of page 3 and the start of page 4).  While there are data to support each of these claims, these are big proclamations and some could be a separate paper on their own.  For example when investigating robustness of SGD you would need to take many perturbations and then train to really see if all the solutions are linearly connected due to the high dimensionality of the space.  I think the paper could potentially be improved if it slightly reduced its scope and focused the experiments on its most important claims.\n", "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": "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": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%