Masks, Signs, And Learning Rate Rewinding
Authors: Advait Harshal Gadhikar
Rebekka Burkholz
Venue: ICLR 2024 spotlight (2024)
Keywords: sparsity
pruning
lottery tickets
learning rate rewinding
iterative magnitude pruning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We give provable insights on the benefits of Learning Rate Rewinding over Iterative Magnitude Pruning

Abstract: Learning Rate Rewinding (LRR) has been established as a strong variant of Iterative Magnitude Pruning (IMP) to find lottery tickets in deep overparameterized neural networks. While both iterative pruning schemes couple structure and parameter learning, understanding how LRR excels in both aspects can bring us closer to the design of more flexible deep learning algorithms that can optimize diverse sets of sparse architectures. To this end, we conduct experiments that disentangle the effect of mask learning and parameter optimization and how both benefit from overparameterization. The ability of LRR to flip parameter signs early and stay robust to sign perturbations seems to make it not only more effective in mask identification but also in optimizing  diverse sets of masks, including random ones. In support of this hypothesis, we prove in a simplified single hidden neuron setting that LRR succeeds in more cases than IMP, as it can escape initially problematic sign configurations.

Published as a conference paper at ICLR 2024
MASKS, SIGNS, AND LEARNING RATE REWINDING
Advait Gadhikar & Rebekka Burkholz CISPA Helmholtz Center for Information Security
Saarbrücken, Germany
burkholz 8ci spa.de de
ABSTRACT
Learning Rate Rewinding (LRR) has been established strong variant of Iter- ative Magnitude Pruning (IMP) to find lottery tickets in deep overparameterized neural networks. While both iterative pruning schemes couple structure and pa- rameter learning, understanding how LRR excels in both aspects can bring us closer to the design of more flexible deep learning algorithms that can optimize diverse sets of sparse architectures. To this end, we conduct experiments that dis- entangle the effect of mask learning and parameter optimization and how both benefit from overparameterizatton. The ability of LRR to flip parameter signs early and stay robust to sign perturbations seems to make not only more effec- tive in mask identification but also in optimizing diverse sets of masks, including random ones. In support of this hypothesis, we prove in a simplified single hidden neuron setting that LRR succeeds in more cases than IMP, it escape initially problematic sign configurations.
INTRODUCTION
Overparamettriation has been key to the huge success of deep learning (Bubeck et al. 2023 Neyshabur et al. 2019 Belkin al. 2019). Adding more trainable parameters to models has shown to consistently improve performance of deep neural networks over multiple tasks. While it has been shown that there often exist sparser neural network representations that can achieve competitive per- formance, they are usually not well trainable by standard neural network optimization approaches (Evei al.] 2022). which is a major challenge for learning small scale (sparse) neural networks from scratch to save computational resources.
The Lottery Ticket Hypothesis (LTH) by Frankle Carbin 2019) is based on an empirical existence proof that the optimization of at least some sparse neural network architectures is feasible with the right initialization. According to the LTH, dense, randomly initialized neural networks contain subnetworks that can be trained in isolation with the same training algorithm that is successful for the dense networks. A strong version of this hypothesis |Ramanujan et al. (2020a); Zhou et al. (2019) which has also been proven theoretically (Malach et al. 2020) Pensia et al. 2020 Orseau
et al. 2020 Fischer et al. 2021 Burkholz et al.; Burkollz] 20022; da Cunha et al.) [022] Gadhikar
al. 2023 Ferbach al. 2023). suggests that the identified initial parameters might be strongly
lied to the identified sparse structure. Related experimental studies and theoretical investigations
support this conjecture (Evei al. 2022 Paul et al. 2023).
In line with these findings, contemporary pruning algorithms currently address the dual challenge of structure and parameter learning only jointly. Iterative Magnitude Pruning (IMP) (Frankle & Carbin 2019) and successive methods derived from it, like Weight Rewinding (WR) (Frankle et al.] 2020ah and Learning Rate Rewinding (LRR) (Renda et al.) 2020 Liu al.) (021a) follow an iterative pruning training procedure that removes fraction of parameters in every pruning iteration until a target sparsity is reached. This achieves state-of-the-an neural network sparsification (Paul et al.)
2023). albeit at substantial computational cost.
While this cost can be reduced by starting the pruning procedure from a sparser, randomly pruned network (Gadhikar et al. 2023). the question remains whether the identification of small sparse ral network models necessitates training an overparameterized model first. Multiple works attest that
overparameterizzttoon aids pruning (Zhang al. 2021 Chang al. 2021 Golubeva et al. 2020

---

Published as a conference paper at ICLR 2024
This suggests that overparameterized optimization obtains information that should be valuable for the performance of a sparsified model. Conforming with this reasoning. IMP was found less effec- tive for complex architectures than Weight Rewinding (WR) (Renda et al., 2020), which rewinds parameters to values that have been obtained by training the dense, overparameterized model for a few epochs (instead of rewinding their initial value like IMP). LRR (Renda et al. 2020) com- pletely gets rid of the weight rewinding step and continues to train a pruned model from its current state while repeating the same learning rate schedule in every iteration. Eliminating the parameter rewinding step has enabled LRR to achieve consistent accuracy gains and improve the movement of parameters away from their initial values (Liu et al. 2021a).
Complimentary to Paul et al. (2023); Liu et al. (2021a), we identify a mechanism that provides LRR with (provable) optimization advantages that are facilitated by pruning a trained overparameterizee model. First, we gain provable insights into LRR and IMP for minimal example, i.e., learning single hidden ReL.U neuron. Our exact solutions to the gradient flow dynamics for high-dimensional inputs could be of independent interest. The initial overparameterization of the hidden neuron en- ables learning provably and facilitates the identification of the correct ground truth mask by pruning. LRR benefits from the robustness of the overparameterized neuron to different parameter initializa- tions, as it is capable of switching initially problematic parameter sign configurations that would result in the failure of IMP.
We verify in extensive experiments on standard benchmark data that our theoretical insights capture practically relevant phenomenon and that our intuition regarding parameter sign switches also ap- plies to more complex architectures and tasks. We find that while LRR is able to perform more sign flips, these happen in early training- - pruning iterations, when higher degree of overparameteriza- tion is available to facilitate them. In this regime, LRR is also more robust to sign perturbations.
This observation suggests that LRR could define a more reliable parameter training algorithm than IMP for general masks. However in iterative pruning schemes like IMP and LRR, the mask identi- fication step is closely coupled with parameter optimization. Changing either of these aspects could affect the overall performance considerably. For example, learning only the mask (strong lottery tickets (Ramanujan al.) (020bb) or learning only the parameters with a random mask (Liu al.) 2021b Gadhikar et al. 2023) are unable to achieve the same performance IMP at high sparsities. Yet, we carefully disentangle the optimization of parameters and mask learning aspect to show that LRR achieves more reliable training results for different masks. In addition, it can also identify better mask that can sometimes achieve a higher performance than the IMP mask, even when both optimized even with IMP.
Contributions. Our main contributions are as follows:
To analyze the advantages of LRR for parameter optimization and mask identification, we conduct experiments that disentangle these two aspects and find that the benefits of LRR are two-fold. (a) LRR often finds a better sparse mask during training and (b) LRR is more effective in optimizing parameters of a diverse masks (eg: random mask).
We experimentally verify that, in comparison with IMP, LRR is more flexible in switching parameter signs during early pruning iterations, when the network is still overparameter- ized. It also recovers more reliably from sign perturbations.
For a univariate single hidden neuron network, we derive closed form solutions of its gra- dient flow dynamics and compare them with training and pruning an overparameterized neuron. LRR is provably more likely to converge ground truth target while IMP is more susceptible to failure due to its inability to switch initial problematic weight signs.
1.1 RELATED WORK
Insights into IMP. Paul et al. (2023) attribute the success of IMP to iteratively pruning small fraction of parameters in every step which allows consecutively pruned networks to be linearly mode connected (Frankle et al. 2020a Paul et al. (022). This can be achieved by WR if the dense network is trained for sufficently many epochs. They argue that as long as consecutive networks are sufficiently close, IMP finds sparse networks that belong the same linearly mode connected region of the loss landscape. [Evci et al. (2022) similarly claim that IMP finds an initialization that is close to the pruning solution and within the same basin of attraction. Liu et al. (2021a) similarly show
2

---

Published as a conference paper at ICLR 2024
that initial and final weights correlated for IMP. In experiments study the WR variant of IMP, where the dense network has been trained for sufficiently many epochs to obtain the initial parameters for IMP, but still find that, in comparison, LRR switches more signs and can achieve better performance.
The role of sign switches. While Wang et al. (023) have recently verified the importance of suitable parameter signs for better training of neural networks in general, they have not analyzed their impact on neural network sparsification. Zhou al.] (2019) study the weight distributions for IMP and find that rewinding only parameter signs can be sufficient. Large scale problems, however, rely on learning signs in early epochs and require a good combination with respective parameter magnitudes, as discussed by Frankle et al. (2020b) for IMP. These results are still focused on the IMP learning mechanism and its coupling to the mask learning. In contrast, we show that identifying good signs (and magnitudes) early enables LRR to not only find better mask but to also learn more effectively if the mask identification is independent from the parameter optimization.
Mask optimization. Random sparse masks also qualify as trainable lottery tickets (Su et al. (2020); Ma et al. (202T); Liu et al. (202Ib) which suggests that the mask identification can be separated from parameter optimization upto certain sparsities (Gadhikar et al. 2023). Our experiments isolate the advantages of LRR on both these aspects.
Training dynamics of overparametrized networks. The training dynamics of overparametrized networks have been theoretically investigated in multiple works, which frequently employ bal- anced initialization (Du et al.] 2018) and related conservation law under gradient flow in their analysis. [Arora et al. (2018) 2019) study deep linear networks in this context, while Du et al.] theo- retically characterizes the gradient flow dynamics of two layer ReLU networks. While they require a high degree of overparameterizaaion, [Boursier et al. (2022) obtains more detailed statements on the dynamics with a more flexible paramterization but assume orthogonal data input.
Single hidden neuron setting. These results do not directly transfer to the single hidden neuron case, which has been subject of active research Ychudai & Ohad (2020); Lee al. (2022a); Vardi et al. (222T) Oymak& & Koltanol (2019); (Soltanolkotabi (20 Kalan et al. (2019); Frei et al. (2020); Diakonikolas et al. (2020); TTan & Vershynin (2019); Du et al. Most works assume that the outer weight is fixed, while only the inner weight vector w is learned and mostly study noise free data. We extend similar results to trainable outer weight and characterize the precise training dy- namics of an univariate (masked) neuron in closed form. Lee et al. (2022b) study a similar univariate case but do not consider label noise in their analysis.
Most importantly, similar results have not been deduced and studied under the premise of network pruning. They enable us to derive a mechanism that gives LRR a provable benefit over IMP, which is inherited from overparameterized training.
THEORETICAL INSIGHTS FOR A SINGLE HIDDEN NEURON NETWORK
x10
<0% 0
IMP
X
LRR
x(0)
x
X
X
X
iox = 60x)
M (o) <o
(
(a)
(bb
Figure 1: (a) Target network. For one dimensional input, learning succeeds when the initial val- ues (0),, (0) > 0 are both positive (yellow quadrant), but fails in all other cases (red). (b) For multidimensional input, IMP identifies the correct mask, but cannot learn the target if the model is
reinitialized to w (²) ()) < 0. (c) LRR identifies the correct mask and is able to inherit the correct initial sign w (2) (0) > 0 from the trained overparameterized model if (0) (0) 0.
3

---

Published as a conference paper at ICLR 2024
Intuition behind LRR versus IMP. The advantage of IMP is that it was designed to identify lottery tickets and thus successfully initialize sparse masks (i.e. sparse neural network structures). However, in order to find such an initialization, we show that the information obtained in earlier pruning iterations with the aid of overparameterivation is valuable in learning better models. Notably, we find that each pruning iteration transfers key information about parameter signs to the next iteration. Forgetting this information (due to weight rewinding) means that IMP is challenged to learn the appropriate parameter signs from scratch in each iteration.
To establish provable insights of this form, we face the theoretical challenge to describe the learning dynamics of the parameters in response to different initializations. We therefore focus on an example of minimum complexity that still enables us to isolate a mechanism by which LRR has a higher chance to succeed in solving a learning task. In doing so, we study a single hidden neuron, 2-layer neural network under gradient flow dynamics, as visualized in Fig. (a).
For our purpose, we focus on two main aspects: (i) The trainability of the masked neural network (i.e., a single hidden neuron with d = 1 input), once the sparse mask is identified. (ii) The ability of LRR to leverage the initial overparameterization (i.e., a single hidden neuron with d > inputs) in the model to learn appropriate parameter signs.
Regarding (i), we have to distinguish four different initialization scenarios. Only one scenario (yel- low quadrant in Fig. [ (a)) leads to accurate learning. LRR is able to inherit this setup from the trained overparameterized network and succeed (see Fig. Fig. (c)) in a case when IMP fails (Fig. (b)) because it rewinds its parameters to initial problematic setting. To explain these results in detail, we have to formalize the set-up.
LRR. We focus comparing Iterative Magnitude Pruming (IMP) and Learning Rate Rewinding (LRR). Both cases comprise iterative pruning-training cycles. The i-th pruning cycle identifies a bi- nary mask (1 E {0, 13,,, which is established by pruning a fraction of neural network parameters (G-1) with the smallest magnitude. A training cycle relearns the remaining parameters (00) of the masked neural network fa M)) The only difference between LRR and IMP is induced by how each training cycle is initialized (See Fig. [b). In case of LRR, the parameters of the previous training cycle that were not pruned away are used as initial values of the new training cycle so that g() (0) f (it-)(((enn)))) Thus, training continues (with a learning rate that is reset to its initial value).
IMP. In case of IMP, each pruning iteration starts from the same initial parameters ((0) (0) = ((0) (0) and parameters learnt in the previous iteration are forgotten. While our theoretical analysis focuses on IMP, Frankle et al. (2021); [Su et al.] (2020); : Ma et al. (202T) have shown that IMP does not scale well to larger architectures. Hence, we employ the more successful variant Weight Rewinding
(WR) in our experiments. Here, the parameters are not rewound their initial values but to the
parameters of the dense network which was trained for a few warm-up epochs (()
g(0) (k)
Frankle et al.] (2020a); Renda et al. (2020). Our theory also applies to this case but we will mostly discuss rewinding to the initial values for simplicity. From now on we use IMP to refer to IMP in our theory and WR in our experiments.
Problem set-up. Consider a single hidden neuron network with input x E R.d, given as f(x)= = ao(wx) with the ReLU activation o(x) = max(x, 0} (see Fig. I). Note that one of the weights could assume the role of bias if one of the inputs is constant in all samples, e.g., x; = 1. The task is to learn a scalar target ((x) o(x, ((xx) only dependent on the first coordinate of æ, from which noisy training data points Y = t(X,, + ( are generated (upper case denotes random variables.) For simplicity, we assume that all input components are independently and identically (iid) distributed and follow a normal distribution X; ~ (N while the noise follows an independent normal distribution Ç ~ (0, o²). The precise assumptions on the data distributions our results but clarify our later experimental setting. Based on a training set (æ,, vi for i E [n]] = {1, 21.,,.,n, learning implies minimizing the mean squared error under gradient flow
not crucial for
Σ (f(x.) - 2 dC L= 2n F=1
Oc OC dw; = ow, dt = da dt
(Vi E [1,d),
(1)
which resembles the dynamics induced by minimizing C with gradient descent for sufficiently small learning rates. Note that also higher learning rates and more advanced optimizers like LBFGS converge to the same values that we derive based on gradient flow for this exemplary problem. Stochastic Gradient (SGD) would introduce additional batch noise and exaggerate the issue that we
4

---

Published as a conference paper at ICLR 2024
will discuss for small sample sizes. As gradient flow is sufficient to highlight the mechanism that we are interested in, we focus our analysis on this case.
To simplify our exposition and to establish closed form solutions, assume that the parameters initialized in balanced state such that a(0)² Dim1 (0), which is preserved through training Arora et al. 2018 Du et al. 2018 so that a(t)² Ei= si=l w (t).
2.1 TRAINING DYNAMICS FOR ONE-DIMENSIONAL INPUT (d 1)
Let us start with the case, in which we have identified the correct mask by pruning away the remain- ing inputs and we know the ground truth structure of the problem. Studying this one dimensional case will help identify typical failure conditions in the learning dynamics and how these failure conditions are more likely to occur in IMP than LRR. Knowing the correct mask, our model is re- duced the one-dimensional input case (d = 1) after pruning, so that f(x)) ac((wr) (wr), while the target labels are drawn from ~ <(z) +
Since the ReLU neuron is active only when wx > 0, we have to distinguish all possible initial sign combinations of w and a to analyze the learning dynamics. The following theorem states our main result, which is also visualized in Fig. | (a).
Theorem 2.1. Let a target t(x) σ(x) and network fx) ad(wz) be given such that and w
follow the gradient flow dynamics (7) with random balanced parameter inirialization and suffi- ciently many samples. If a(0) > and w0()) > 0, [(x) can learn the correct target. In all other cases (a(0) 0, w0)) < 0), (a(0) < 0, ((0) > 0) and (a(0) < 0, (( < 0) learning fails.
The proof in Appendix A. derives the closed form solutions of the learning dynamics of f(x) under gradient flow for each combination of initial signs. It establishes that training single neuron f(x) = aΦf (wx) from scratch to learn the noisy target ((x) + can be expected to fail at least with probability 3/4 if we choose a standard balanced parameter initialization scheme where either signs equally likely to occur for a0)), (0).
Why should this imply a disadvantage for IMP over LRR? As we will argue next, overparameter ization in form of additional independent input dimensions E R' can improve substantially the learning success as the set of samples activated by ReLU becomes less dependent on the initial- ization of the first element w1 (0) of w. Thus training overparameterized neuron first, enables LRR and IMP to identify the correct mask. Yet, after reinitialization, IMP is reduced to the failure case described above with probability 3/4, considering the combination of initial signs of a(0) and Wi (0). In contrast, LRR continues training from the learned parameters. It thus inherits potential sign switch from wh (0) < 0 w1 (0) > if (0)) > 0 during training (and pruning) the overparam- eterized model. Thus, the probability that LRR fails due to a bad initial sign after identifying the correct mask is reduced to 1/2, as also explained Fig.
2.2 LEARNING AN OVERPARAMETRIEE NEURON (d > 1)
As we have established the failure cases of the single input case in the previous section, we now focus on how overparameterizztion (to 1) can help avoid one case and thus aid LRR, while IMP is unable to benefit from the same.
Multiple works have derived that convergence of the overparameterized model (d > 1) happens under mild assumptions and with high probability in case of zero noise and Gaussian input data, suggesting that overparameterizztioon critically aids our original learning problem. For instance, YYehudai & Ohad 2020) have shown that convergence to a target vector v is exponentially fast [wr(() " v < wr (0) e|| (exp(>Xt) where the convergence rate > depends on the angle between w and wtt) assuming that (0) a(t) is not trainable.
Insight: For our purpose, it is sufficient that the learning dynamics can change the sign of w (0) < to wi (x0) 0 if d > 2. This would correspond to the first training round of LRR and IMP. Furthermore, training the neuron with multiple inputs enables the pruning step to identify the correct ground truth mask under zero noise, (x0) 0 for k # 1. Yet, while IMP would restart training from wi (0) < 0 and fail to learn parameterization that corresponds to the ground truth, LRR succeeds, as it starts from wi (2o) > 0.
5

---

Published as a conference paper at ICLR 2024
These results assume, however, that a()) = 1 is fixed and not trainable. In the previous section, we have also identified major training failure points if a()) < O. As it turns out, training a single multivariate neuron does not enable recovery from such problematic initialization in general.
Lemma 2.2. Assume that and w follow the gradient flow dynamics induced by Eq. 7 with Gaussian iid input data, zero noise, and that initially < [a]]]=(O)]| S and a(0)² = [0){ Then cannot switch its sign during gradient flow.
This excludes another relevant event that could have given IMP an advantage over LRR. Note that IMP could succeed while LRR fails, if we start from a promising initialization w1 (0) > 0 and
a(0) > 0 but the parameters converge during the first training round to values w1 (0) < 0 and
a(0) < O that would hamper successful training after pruning. This option prevented, however,
by the fact that cannot switch its sign in case of zero noise. We therefore conclude our theoretical analysis with our main insight.
Theorem 2.3. Assume that a and w follow the gradient flow dynamics induced by Eq. with Gaussian iid input data, zero noise, and that initially 0 < |a] [aIlww w0)) S 2 and a(0)² = (0)
If wi (0) < O and a(0) > 0, LRR atlains lower objective than IMP. In all other cases, LRR performs at least well as IMP.
2.3 VERIFYING THEORETICAL INSIGHTS BASED ON SINGLE HIDDEN NEURON NETWORK
Figure (a) empirically validates our theoretical insights for d > 1 and compares LRR and IMP for each combination of initial signs of a(O), ui (0). A single hidden neuron network with input dimension d = 10 and random balanced Gaussian initialization is trained with LBFGS to minimize the objective function| I for a noisy target (o² 2 0.01). Averages and 0.95 confidence intervals over 10 runs for each case are shown. In each run, we prune and train over 3 levels for 1000 epochs each, while removing the same fraction of parameters in each level to achieve a target sparsity of 90% so that only one single input remains. In line with the theory, we find that IMP is only successful in the case a()) > 0 and w1 (0) > O, while LRR succeeds as long as (0)) > 0.
EXPERIMENTS
Our first objective is to analyze whether our theoretical intuition that LRR more flexible in learning advantageous sign configurations transfers to more complex tasks related to standard benchmarks. Different from the simplified one hidden neuron setting, LRR and IMP also identify different masks. Thus, our second objective is to disentangle the impact of the different learning mechanisms and potential sign flips on both, the mask learning and the parameter optimization given a fixed mask.
To this end, we perform experiments CIFARIO, CIFAR 100 (Krizhevsky 2009) and Tiny Ima- geNet (Le & Yang. 2015) with ResNet18 or ResNet50 with IMP and LRR that start from the same initializations. Table [ in the appendix describes the details of the setup. To strengthen the IMP baseline, we in fact study WR and thus rewind the parameters to values that we have obtained after sufficiently high number of training epochs of the dense model, which is in line with successfully obtaining matching networks as found by Paul et al. (2023).
LRR modifications. Different from our theoretical investigations, we have to take more complex factors into account that influence the training process like learning rate schedules and batch nor- malization (BN). We found that the originally proposed training schedule of LRR can suffer from diminishing BN weights that impair training stability on larger scale problems like CIFAR 100 and Tiny ImageNet (see Fig. 4 and Fig. i the appendix). To avoid this issue, we propose rewind BN parameters when the mask is decoupled from parameter optimization. In all our experiments, we introduce warmup after each pruning iteration, which increases the flexibility of LRR to optimize different masks as well as improves baseline performance (see Fig. g in appendix). Fig. 4 (c. d) provides an example where these modifications make LRR competitive with IMP on the IMP mask.
We start our investigations with observations regarding the performance of LRR and IMP in differ- ent learning scenarios before we isolate potential mechanisms that govern these observations like sign flips and network overparameterization. Our experiments establish and confirm that LRR out- performs IMP on all our benchmarks. Does this performance boost result from an improved mask identification stronger parameter optimization?

---

Published as a conference paper at ICLR 2024
10
95
Tost TostLoss
79
50
10-1
INP ned
1.2
INP
LRX w/b BMP raat cowtrd KN
72
50
100
41200
4:500
+..00
2-0
Sparsity (b)
Spansity (c)
Sparsity
(4)
Figure 2: (a) IMP and LRR for single hidden neuron network. (b, Mask randomization for (b) CIFARIO 10 and (c) CIFARIO0. (d) LRR optimizes the IMP mask more effectively on Tiny ImageNet.
LRR identifies a better mask. Even though the mask identification of IMP is coupled to its training procedure, Fig. 3 (a. b) show that the mask that has been identified by LRR also achieves higher performance than the IMP mask on CIFART 10 when its parameters are optimized with IMP. Similar improvements observed CIFAR 100 (Fig- 3 (c, d)) except at high sparsities (> 95%) where the coupling of the mask and parameter optimization is more relevant.
81
81
95.5
Toxt Ase
95.0
79
LKK
LXX
78
94.0
95.0
100.0
Sparsity (x)
Spansity (b)
Sparsity (c)
Spursity
(d)
Figure 3: The sparse mask learnt by LRR superior and the performance IMP improved in combination with the LRR mask on (a, b) CIFARIO and (c, d) CIFAR100.
LRR is more flexible in optimizing different masks. According to Fig. a, b), training LRR with the IMP mask (blue curve) is able improve over IMP for CIFAR1O. 10. While the original LRR is less competitive for learning with the IMP mask on CIFARIO0, 100, LRR with BN parameter rewinding after each pruning iteration outperforms IMP both CIFARIO and CIFARIO0 even high spar- sities. Similar results for Tiny ImageNet are presented in Fig. di.). Yet, are IMP and LRR masks sufficiently diverse? Since IMP and LRR masks are identified based on a similar magnitue based pruning criterion, the other mask and parameter initialization might still carry relevant information for the respective optimization task. order to completely decouple the sparse mask from the pa- rameter optimization and the initialization, we also study the LRR and IMP parameter optimization on a random mask.
95.5
81
95.5
05.0
95.0
94.5
04.5
75
94.0
70
100
90.0
92.5
95.0
100.0
60
50
100
90.0
92.5
95.0
97.5
100.0
Sparsity (n)
Spansity (h)
Spursity (6)
Sparsity
Figure 4: LRR improves parameter optimization within the mask learnt by IMP for (a, b) CIFARIO and (c. d) CIFAR100.
Random Masks. For the same randomly pruned mask with balanced sparsity ratios (Gadhikar et al., 2023) and identical initialization, we compare training from initial values (IMP-rand) or training from the values obtained by the previous training pruning iteration (LRR-rand) (see Fig. b,, c)). Rewinding the BN parameters assists gradual random pruning and improves optimization, thus, LRR-rand (rewind BN) outperforms IMP-rand. This confirms that LRR seems to employ a more flexible parameter optimization approach irrespective of task specifie masks.

---

Published as a conference paper at ICLR 2024
Our theoretical insights align with the observation that LRR learns network parameters reliably than IMP. The main mechanism that strengthens LRR in our toy model is the fact that it inherits parameter signs that identified by training overparameterized model that is sufficiently flexible to correct initially problematic weight signs. To investigate whether similar mechanism supports LRR also in more complex setting, study the sign flip dynamics.
1,0
Donnty
Dessty
0.0
In
16
15
20
6
Level
Praning
LRR
IMP
LRR with IMP mark
LRR sewind BN
LRR with EMI mask rewind BN
Daneg
Devuty
10-
Danelyy
0.5
0.0
flige
Flige
Sign Elige
Figure 5: (top) The pruming iteration at which the parameter signs do not change anymore for LRR (purple) is much earlier than IMP (orange). (bottom) The number of times parameter switches sign over pruning iterations (a) CIFARIO (b) CIFAR100 and (c) Tiny ImageNet.
LRR enables early and stable sign switches. Fig. confirms that LRR corrects initial signs pri- marily in earlier iterations when the mask denser and the model more overparameterized. More- over, the signs also stabilize early and remain largely constant for the subsequent pruning iterations (Fig. 5). Learnt parameters at consecutive sparsity levels in LRR tend to share the same sign in later iterations. but IMP must align initial signs in each pruning iteration, leading to unstable, back and forth flipping of learnt signs across sparsity levels. Overall, LRR changes more signs than IMP at lower sparsities and Tiny ImageNet, where IMP fails to identify stable sign configurations even at high sparsities (see also Fig. 13 in appendix). These results apply settings where the mask and parameter learning coupled. Constraining both IMP and LRR to the same mask, LRR also appears to be more flexible and is able to improve performance by learning larger fraction of parameter signs earlier than IMP (see Fig. BJ)).. For random masks, generally more unstable sign flips occur due to the fact that the mask parameter values are not aligned well. Yet, LRR appears to be more stable and is able to flip more signs overall (Fig. 14 (a, b) in appendix). Even with the improved LRR mask, IMP seems unable to perform effective sign switches (Fig. I4 (c. d) in appendix).
CIFAR1O, 10, yet, the effect is more pronounced in larger networks for CIFAR100
Yet, maybe the LRR optimization can simply tolerate more sign switches? Furthermore, is LRR only able to switch signs early training rounds due to the higher overparameterization the networks? To answer these questions and learn more about the causal connection between sign switches and learning, next we study the effect sign perturbations.
95.5
Tost Ace
35.0
50
94
1BB
78
94.5
JMP
JMP pernns 0.
18R permits DUS
76
34.0
92
78
98
Spursity (A)
S Sparsity
Sparsity (c)
Sparsity (d)
Figure 6: 30% signs in each layer are flipped randomly 20% sparsity for LRR and IMP (dotted) on (a, b) CIFAR10 and (c. d) CIFAR100. Solid lines denote baselines.
LRR recovers from random sign perturbations. In order to characterize the effect of correct parameter signs mask identification, randomly perturb signs different levels of sparsity
8

---

Published as a conference paper at ICLR 2024
for both LRR and IMP. Sign perturbation at a low sparsity has little effect CIFAR10 and both LRR and IMP are able to recover achieving baseline accuracy (Fig. ([a. a b)). For the more complex CIFAR100 dataset, signs have a stronger influence recover to baseline performance. However, LRR is still able to achieve a higher performance than the IMP baseline, but IMP struggles after perturbing initial signs, as the mask does not fit to its initialization O d)).
masks and neither LRR nor IMP can fully
Fig. 7/a.b) shows results for perturbing larger fraction of signs much higher sparsity, i.e., 83%. LRR is able to recover over IMP at later sparsities on CIFARIO. 10. Interestingly. on CIFAR 100, LRR suffers more than IMP from the sign perturbation potentially due to lack of overparameterization at high sparsity. LRR recovers slowly but still achieves baseline performance beyond 95% sparsity. The performance of subsequent masks obtained after perturbing signs reaffirms that parameter signs strongly influence the quality of the mask identification and LRR is capable of rearranging signs in order to find better mask and optimize the corresponding parameters effectively. Yet, LRR requires training time and initial overparameterization to be effective.
The interplay of magnitude and signs. Recent analyses of IMP (Frankle et al. 2020b; Zhou et al, 2019) have found that signs that are learnt at later iterations are more informative and initializing with them improves IMP. In line with this insight, Fig. ( highlights that rewinding only weight amplitude while maintaining the learnt signs improves over IMP. Yet, according Frankle et al. (2020)) the combination with learned weight magnitudes can further strengthen the approach. Our next results imply that the magnitudes might be more relevant for the actual mask learning than the parameter optimization. We find that the learnt signs and the LRR mask contain most of the relevant information. Fig. ()) confirms that if we initialize IMP with the LRR signs and restrict to the LRR mask, we can match the performance of LRR despite rewinding the weight magnitudes in every iteration. These results imply that a major drawback of IMP parameter optimization procedure could be that it forgets crucial sign information during weight rewinding.
95.5
96.0
Test Ase
95.0
95.5
95.0
94.5
78
79-
85
90
96
100
85
90
95
80
85
90 Sparsity
95
100
80
85
90
95
100
Spursity
Sparsity
Sparsit (d)
IMP
TMP
BR mook Aige
Figure 7: 80% signs in each layer are flipped randomly at 83% sparsity for LRR and IMP (dashed) on (a) CIFAR10 and (b) CIFAR100 Rewinding only magnitudes while using the initial weights of IMP with the learnt LRR masks and signs on (c) CIFARIO and (d) CIFAR100.
CONCLUSIONS
Learning Rate Rewinding (LRR), Iterative Magnitude Pruning (IMP) and Weight Rewinding (WR) present cornerstones in our efforts to identify lottery tickets and sparsify neural networks, but the reasons for their successes and limitations are not well understood. To deepen our insights into their inner workings, we have highlighted a mechanism that gives LRR a competitive edge in structure learning and parameter optimization.
In a simplified single hidden neuron model, LRR provably recovers from initially problematic sign configurations by inheriting the signs from trained overparameterized model, which is more robust to different initializations. This main theoretical insight also applies to more complex learning set- tings, as we show in experiments on standard benchmark data. Accordingly, LRR is more flexible in switching signs during early pruning-training iterations by utilizing the still available overparam- cterization. As a consequence, LRR identifies not only highly performant masks. More importantly, it also optimize parameters effectively given diverse sets of masks. In future, we envision that insights into the underlying mechanisms like ours could inspire the development of more efficient sparse training algorithms that optimize sparse networks from scratch.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We gratefully acknowledge funding from the European Research Council (ERC) under the Horizon Europe Framework Programme (HORIZON) for proposal number 101116395 SPARSE-MI.
REFERENCES
Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In International Conference on Machine Learning. pp- PMLR, 2018.
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. convergence analysis of gradient de- scent for deep linear neural networks. In International Conference on Learning Representations, 2019.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical barinnari trade-off. Proceedings of the National Academy of Sciences, 2019.
Etienne Boursier, Loucas Pillaud- Vivien, and Nicolas Flammarion. Gradient flow dynamies of shal- low reLU networks for square loss and orthogonal inputs. In Advances in Neural Information Processing Systems, 2022.
Sébastien Bubeck, Varun Chandrasckaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Ka- mar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712, 2023.
Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. In International Conference Learning Representations.
Rebekka Burkolz. Most activation functions can win the lottery without excessive depth. In Ad- vances in Neural Information Processing Systems, 2022.
Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overparameterization in model compression: From double descent pruning neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6974-6983, 2021.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations, 2022.
Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam R Klivans, and Mahdi Soltanolkotabi. Approximation schemes for relu regression. In Conference on learning theory, pp. 1452 1485. PMLR, 2020.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations.
Simon S Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. Advances neural information processing systems, 31, 2018
Utku Evei, Yani Ioannou, Cem Keskin, and Yann Dauphin. Gradient flow in sparse neural networks and how lottery tickets win. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6577-6586, 2022.
Damien Ferbach, Christos Tsirigotis, Gauthier Gidel, and Joey Bose. A general framework for proving the equivariant strong lottery ticket hypothesis. In International Conference on Learning Representations, 2023.
Jonas Fischer, Advait Gadhikar, and Rebekka Burkholz. Lottery tickets with nonzero biases. arXiv preprint 10 2021.
10

---

Published as a conference paper at ICLR 2024
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2019.
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode con- nectivity and the lottery ticket hypothesis. In International Conference Machine Learning, 2020a.
Jonathan Frankle, David Schwab, and Ari Morcos. The early phase of neural network training. In International Conference on Learning Representations, 2020b.
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. Training batchnorm and only batchnorm: On the expressive power random features in {cnn}s. s. In International Conference on Learning Representations, 2021.
Spencer Frei, Yuan Cao, and Quanquan Gu. Agnostic learning of single neuron with gradient descent. Advances in Neural Information Processing Systems, 33:5417-54225 2020.
Advait Harshal Gadhikar, Sohom Mukherjee, and Rebekka Burkholz. Why random pruning is all we need to start sparse. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 10542-10570, 2023.
Anna Golubeva, Guy Gur-Ari, and Behnam Neyshabur. Are wider nets better given the same number of parameters? In International Conference Learning Representations, 2020.
Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and A Salman Avestimehr. Fitting relus via sgd and quantized sgd. In 2019 IEEE international symposium on information theory (ISIT), pp. 2479. IEEE, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft threshold weight reparameterizatioo for learnable sparsity. In Proceedings of the International Conference Machine Learning, July 2020.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr. Snip: single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations, 2019.
Sangmin Lee, Byeongsu Sim, and Jong Chul Ye. Support vectors and gradient dynamics for implicit bias in relu networks. arXiv preprint arXiv:2202.055100 2022a.
Sangmin Lee, Byeongsu Sim, and Jong Chul Ye. Magnitude and angle dynamics in training single relu neurons. arXiv preprint arXiv:2209. 022009/.3330 13394, 2022b.
Ning Liu, Geng Yuan, Zhengping Che, Xuan Shen, Xiaolong Ma, Qing Jin, Jian Ren, Jian Tang, Sijia Liu, and Yanzhi Wang. Lottery ticket preserves weight correlation: Is it desirable or not? In International Conference on Machine Learning, 2021a.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effeectiveness of random pruning: Return of the most naive baseline for sparse training. International Conference on Learning Representations, 2021b.
Xiaolong Ma. Geng Yuan, Xuan Shen, Tianlong Chen, Xuxi Chen, Xiaohan Chen, Ning Liu, Ming- hai Qin, Sijia Liu, Zhangyang Wang, and Yanzhi Wang. Sanity checks for lottery tickets: Does your winning ticket really win the jackpot? In Advances in Neural Information Processing Sys- tems, 2021.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference Machine Learning, 2020.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over- pweamtrrattiinnnnoonnnn generalization of neural networks. In International Conference on Learn ing Representations, 2019. htR.s:ttt::///

---

Published as a conference paper at ICLR 2024
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Ad- vances in Neural Information Processing Systems, 33, 2020.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In International Conference Machine Learning, pp. 4951-4960. PMLR, 2019.
Mansheej Paul, Brett Larsen, Surya Ganguli, Jonathan Frankle, and Gintare Karolina Dziugaite. Lottery tickets on a data diet: Finding initializations with sparse trainable networks, Advances in Neural Information Processing Systems, 35: 18916-18928,, 2022.
Mansheej Paul, Feng Chen, Brett W. Larsen, Jonathan Frankle, Surya Ganguli, and Gintare Karolina Dziugaite. Unmasking the lottery ticket hypothesis: What's 's encoded in a winning ticket's mask? In The Eleventh International Conference on Learning Representations, 2023. URL https:
net http://wwww..etett//////o/oo//.e XSaW2Am uk2
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Op- timal lottery tickets via subset sum: Logarithmic over-parameterizaaionn is sufficient. In Advances in Neural Information Processing Systems, volume 33, pp. 2599-2610, 2020.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in a randomly weighted neural network? In Conference on Computer Vision and Puttern Recognition, 2020a.
Vivek Ramanujan, Mitchell Wortsman, Aniruddha Kembhavi, Ali Farhadi, and Mohammad Raste- gari. What's hidden in randomly weighted neural network? In Computer Vision and Pattern Recognition, pp. 11893-1199 11902, 2020b.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2020.
K Simonyan and A Zisserman. Very deep convolutional networks for large-scale image recognition. In 3rd International Conference on Learning Representations (ICLR 2015). Computational and Biological Learning Society, 2015.
Mahdi Soltanolkotabi. Learning relus via gradient descent. Advances in neural information pro- cessing systems, 30, 2017.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason D Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. In Advances in Neural Information Processing Systems, 2020.
Yan Shuo Tan and Roman Vershynin. Online stochastic gradient descent with arbitrary initialization solves non-smooth, non-convex phase retrieval. arXiv preprint 1rXiv:1110.12377 2019.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Advances in Neural Information Processing Systems, 2020.
Gal Vardi, Gilad Yehudai, and Ohad Shamir. Learning a single neuron with bias using gradient descent. Advances Neural Information Processing Systems, 34:28690-28700, 2021.
Qingyang Wang, Michael Alan Powell, Eric W Bridgeford, Ali Geisa, and Joshua T Vogelstein. Polarity is all you need to learn and transfer faster. 2023.
Gilad Yehudai and Shamir Ohad. Learning single neuron with gradient methods. In Conference on Learning Theory, pp. 3756-3786. PMLR, 2020.
Shuai Zhang, Meng Wang, Sijia Liu, Yun-Yu Chen, and Jinjun Xiong. Why lottery ticket wins? theoretical perspective of sample complexity on sparse neural networks. Advances in Neural Information Processing Systems, 2021.
Hattie Zhou, Janice Lan, Rosanne Liu, and Jason Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. In Advances in Neural Information Processing Systems, pp. 3597-3607, 2019.
12

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 PROOFS: ONE DIMENSIONAL INPUT
Theorem A.1. Let a target function t(x) = 6(x) and network f(z) = ad(wx) be given such that and w follow the gradient flow dynamics induced by Eq. 47) with random balanced parameter initialization and sufficiently many samples. If a(O) > and w(0) > 0, f(x) can learn the correct target. In all other cases (a(0) > O, w()) 0), (a(0) 0, w (0) 0) and (a(0) < 0, w(O) < 0)
learning fails.
Proof: The derivatives of the parameters (a, w) with respect to the loss are given by
0C
1 - - n
n
dc
n
Σ yy -d(wx;) d(wr)));
(ys ad(wrr)) az, 11 (wz,20);
da
ow
n
which induce the following ODEs under gradient flow:
à = aa + wC2,, de ===- -wa + aC2,
+ (.r,). Note that C₁ and C2 can change over time, as they depend on the potentially changing set I(t) that comprises all samples on which the neuron is switched on: I(t)= (i)w,(t).; > 0}.
where = EiEI ot and C2 = t
To solve this set of ODEs, we have to dinstinguish multiple cases. For all of them, we have a (t) (1). Thus, both parameters can pass through zero only together and potentially switch their sign only in this case. If w:()) does not switch its sign during training. C1 and C2 remain constant, we know that (t)) = sign (0)) (t) and we can focus on solving the dynamic equation for w at least until a potential sign switch. Replacing a(t) sign(a())) (a(O)))w(()))))))))))))))))
in the ODE for w leads to vb - + wC²2 with C2- C2 sign(a(0)) sign (()).. As this ODE is of Bernoulli form, it has a closed form solution. Note that generally C1 2 0. If C1 = O, nothing happens and our function remains constant O. Otherwise, have
(Czw(0) exp(2C2tt
w(()
if if 0,
(4)
VC, -2)((03) C Crw(0)a exp(1).1)
+1
C.- Cy-Ci
sign(w(0))
w(()
if i < 0, and
(5)
exp (2202t) (ci (C1-020 C2/ C1
w()
if C2 = 0. w()) /2C (0)+ +1
(6)
which can be easily verified by differentiation. Note that these equations only hold until w(t) passes through 0. If that happens at to. C₁ and C2 actually change and we have to modify the above equations. Technically, C2(to) 0. Yet, in noisy learning setting with discrete step sizes, it is not impossible that parameters switch their sign. In this case, new dynamics start from the switching point to on a time scale / = 1 to that continues from the previously found parameters w(E 0) w(t to + e). We now develop an intuition of what this means for our learning problem, by differentiating the problem into different cases based on initial parameter signs.
w(tp) = 0, the gradient flow dynamics halt because C2 (to) = 0 and
Correct initial sign. If we start with the correct signs w())= > 0 and a()) > 0 as the target, then our neuron has no problem to learn the right parameters given enough samples. w(() > implies that I = [ilo; > 0} so that C₂- = 1/n Eiez(1;(22) + (ax;)) 1/n Eiez x? + 1/n Exer G.;- According to the law of large numbers, limmn C₂ E(o(X) ( + B(@(X)
12d) > 0 and
lim C = (x)(())) = 1/(2d) almost surely. Also for finite samples, we likely have C2 > 0,
as we will make more precise later. Thus, C2 = sign (gg(ww0))((0)CC = C2 > 0 and w converges
to xxxx C2//Ci 1 without passing through 0. Also a(oo) sign(a(0))ww(oo)) = corresponds to the correct target value.
13

---

Published as a conference paper at ICLR 2024
Case w0) > 0 but a()) < O. Since I is defined as above, our initial constants C1 and C2 identical. Yet, C2 C2 0 changes its sign, which has a considerable impact the learning dynamics. As (() has started with the wrong sign, the gradient dynamics try to rectify it and send w(() 0 in the process, as att) would need to pass through 0 to switch its sign. Thus, learning fails. In case of finite samples, C2 subject to noise. If C2 O, a and still converge to However, C2 > 0 because of substantial noise, w would converge to a positive value w(oo) = / C2//11, while a(xc) = -VC0//C < O, which would not align at all with the target ((x).
Case w0) < O. This case is bound to fail regardless of the sign of a(O), if the noise is not helping with sign switch. The reason is that the neuron is initially switched on only on the negative samples I= (iz; 0}. for which the true labels are zero. In consequence, C2 1/n (x, + 0 almost surely. Thus, the training data provides an incentive for a and w to converge to without passing through 0 in between. Also for finite samples, we have C2= = - (a0)/n Σiez S:I; > O with probability 1/2. In this case, w will
(.2 1/n Ligz SiT; and lim, C2 (E(-((-X)({
converge to a negative value sign( wo) y C2/Cr. Of < O, then both w and a converge to 0 without the opportunity to change the sign with a too large discrete gradient step.
Finite sample considerations. Interestingly, the number of samples and the noise level do not really influence the (failed) learning outcome in case a negative initial weight w(0) < 0. The case w(0)= 0, a0)) < 0 is not able to learn model that can come close to the ground truth target. Thus, only the potential success case w(O) > O and a(0) > 0 depends meaningfully on the data and its signal to noise ratio, our set-up reduces
CC/CC if C2 overparameterized linear regression problem (Note that C2
would imply such high noise that the learning could also not be regarded successful, as a(x)) w(x) = 0.) The sample complexity of learning the parameters the only part that depends on distribution assumptions regarding the input and noise. The effective regression parameter a( a(cc) (c))w(o))))))))))))))))))))))( = C2/C1 = + (Eiez (,2;)((Eeez) 2²) depends in the usual way on the noise, but requires double the number of samples as normal regression problem, as in approximately half of the cases, the neuron is switched off.
with outcome a(co) = w(oo)
A.2 PROOFS: OVERPARAMETHRIIZR) INPUT (d (d>1) 1)
In the following section, we prove main theorem that allows us to conclude that LRR has higher chance to succeed in learning a single univariate neuron than IMP.
Learning overparameterized multivariate neuron f(x) ad(w" x) for E Rd corresponds to more complex set of coupled gradient flow ODEs, if d 1.
-aa aaC, d-ww C C2 w,
with C₁ = _ xxxx C2 = yxxi. SEI
TET
where the dynamic set again defined as the set of samples on which the neuron is activated so that I = {i wif x; >> 0). The main difference to the previous one-dimensional case is that this set is initially not determined by wi (0). Even in case of a problematic initialization w1 (0) < 0, the neuron can learn better model because of 02 O.
We cannot expect to derive the gradient flow dynamics for this problem in closed form, as C, and C2 depend on in complicated nonlinear ways. However, the structure of a solution is apparent, problem corresponds to an overparameterized linear regression problem given I. Lee et al. (2022a) have discussed the solutions to this general problem in case of positive input and fixed, non trainable
the
3/ |||]|| and a = sign(a) / [|3 where 3 = X y is the mean squared error minimizer and X = (.., ssk E
Assuming balancedness a² | our solution must also be of the form
R 7 corresponds to the data matrix on the active samples. Under conditions that enable successful optimization, we obtain 3 z v = (1, OT.T....)T
Yet, there are still several issues that can arise during training as the set I changes with w. Solving the set of ODEs is generally hard problem, even though several variants have been well studied
14

---

Published as a conference paper at ICLR 2024
Yehudai & Ohad (2020); Lee et al. (2022a); Vardi et al. (2021 ?): Oymak & Soltanolkotabi (2019)
Soltanolkotabi (201 7): Kalan et al. (2019); Frei et al. (2020): Diakonikolas et al. (2020): Tan &
Vershynin (20)))))nn((0))):::) Du al. Most works assume that the outer weight is fixed a a
and
only the inner weight vector w is learned Yehudai & Ohad (2020): Lee et al. 2022a Vardi et al. (202T). Only (Boursier et al. 2022) considers trainable but excludes the single hidden neuron case and is restricted to orthogonal inputs. Furthermore, the noise is usually considered to be 0. In the large sample setting, this assumption would be well justified, as the noise contribution to C2 approaches O. However, to guarantee convergence, additional assumptions on the data generating process are still required, as Yehudai & Ohad (2020) have pointed out with a counter example that for a given parameter initialization method (in form of product distribution) there exist a data distribution for which gradient flow (or SGD or GD) does not converge with probability at least 1 - exp(-d/4p Vardi et al. (2021) have furthermore shown that if we also want to learn biases (which would be the case one of our data input components is constant 1). a uniform initial weight distribution could lead to failed learning results with probability close to 1/2.
Recall that three scenarios prevent IMP from succeeding in learning our target ((z)): a) (()) < O, wi (0) O, b) a()) < O, (0) < O, and (c) a(O) > 0 and w1 (0) < O. LRR cannot succeed in case of (a) and (b) as well, because a cannot switch its sign to a(oo)= > 0 during training, as the following lemma states.
Statement (Restated Lemma 2.2 . Assume that and w follow the gradient flow dynamics induced
by Eq. 7 with Gaussian iid input data, zero noise, and that initially 0 < [a]]|[(0)]| S 2 and a(0)² [= Then cannot switch its sign during gradient flow.
Proof. This statement follows immediately from the balancedness property. To switch its sign, a(t) would need to pass through zero. Thus, let us assume there exists a time point to > 0 so that a(tg) 0. Since a(t)² [t) for the complete dynamics, this implies that [|w = O. As
this switches of the neuron, C₁ (to) = C2 = 0 so that a(to) = 0 and (tx) = 0. It follows that at)) = and [t)] 2 = for all 2 to so that no sign switch occurs.
Note that for finite, relatively high learning rates, it could be possible that a neuron switches its sign because it never switches off completely and instead overshoots O with a large enough gradient step- In most cases, this would provide LRR with an advantage. Because a problematic initialization with a(0) < 0 could be mitigated by training so that a(oo) > 0, LRR would benefit but not IMP. The only scenario in favor for IMP would be the case that the initialization is advantageous so that a()) > 0 and w1 (0) > O but becomes problematic during training so that a(oo) < 0. This, however, would require such high noise that also training an univariate neuron from scratch could not result in a good model. It is therefore an irrelevant (and unlikely) case and does not impact our main conclusions, which are restated below for convenience.
Statement (Restated Theorem 2.3). Assume that a and w follow the gradient dynamics induced by Eq. 77) with Gaussian iid input data, zero noise, and that initially 0 < (all)o(0)|| < 2 and a{0)² 2 = ((])]l? If wh (0) < O and a()) > 0, LRR attains a lower objective 7 than IMP. In all other cases, LRR performs at least as well as IMP.
Proof. According to Lemma 2.2, a(0) < 0 implies a(co) S 0 so that neither IMP nor LRR can succeed to learn the correct univariate target neuron after pruning. We can therefore focus our analysis on the case aloo) > O. Note that this implies that at)) = [|)r()] because a does not switch its sign.
Both IMP and LRR rely on the first overparameterized training cycle to result in a successful mask identification, which requires |w1] >> |uy] for any 전 1. Otherwise, both approaches (IMP and LRR) would fail. Hypothetically, it could be possible that [w) (no) >> |wx(()) while w (co) < O, which would not correspond to a successful training round, since w(oo) # (1,0, O...) but would result in a correct mask identification. This case would be interesting, as it would allow IMP to succeed if (0) > 0 while LRR could not, as it would start training univariate neuron from wi (co) < O. However, note that the derivative of w would be nonzero in this case. Thus, there exists no stationary point with the property wi (co) < 0.
In consequence, only cases of successful training offer interesting instances to compare IMP and I LRR. For our argument, it would be sufficient show that learning multivariate neuron is suc-
15

---

Published as a conference paper at ICLR 2024
cessful with nonzero probability and argue that LRR succeeds while IMP fails in some of these cases. Yet, we can derive a much stronger statement by using and adapting Theorem 6,4 by Yehudai and Shamir (Yehudai & Ohad, 2020) and prove that learning is generally successful for reasonable initializations.
Learning single neuron. We define z(t) a(t)wr(t) Note that z has therefore norm || = |wll and its direction coincides with the one of w, as z/||z|| = w/|lw|]. In case of successful training, we expect z(t) + for t - oc, where v a general target vec- tor. In our case, we assume v = (1, ...).. Our main goal is to bound the time derivative 8/6t][=(t)- - w11 2 (z(t), x(t) v) < -X|2((t) - = for a X
Grönwall's inequality would then imply that [t= v/| < =|((0) - -v(0]] exp(-Xts and hence xt) + a exponentially fast.
u||
In contrast to Yehudai & Ohad 2020 the derivative (t) and + aw consists of two parts that we have to control separately.
It is easy to see based on Eq.
7 that the time derivative of w (t) fulfills:
(awi x 1--07 0) =
a²
Σ
(2i, 2 - w)²
(8)
n iEl,0T2,20
a
(Di, 2 - v) (x,; z)
(9)
n
iET," 2,50
a²
a²llz
01|2-
1
|0:1| cos (c((xi 2- =)))²
(10)
iEL, xx.00
a n iET, 2,50 < w113 A1 ->al|=1l| -1/p---ll u11 2 doll= = u11
(z,, 2)²
a²
Σ
(12, -v)
(11)
n2
(12)
where we dropped the term because it is negative. (Note that all involved factors are positive because -v-'; x; 2 0.) Furthermore, we have \ 1/n 1/n Ei ||= cos (yp(z), = - -))²
O with high probability with respect to the data distribution according to Lemma B1 by Yehudai and Shamir (Yehudai & Ohad 2020). Similarly, the proof of Thm. 5.3 by (Yehudai & Ohad 2020) argues why a² the constant Ag
is bounded from below, which allows us to integrate its lower bound into
The second term of 2 is not considered by (Yehudai & Ohad 2020 as they assume that a is not trainable. We get:
(aw, = v) =ů (w. = v) < O.
(13)
The last inequality can be deduced by distinguishing two cases. If (w, = - v) > O. then à < 0. If
(w. = Dv) < 0, then â O. This follows from the fact that v)
1 à -|
Σ iET," 2200
(u, (20
(14)
n iET
and that (w. z 4) |w: ||
(w, v)
|
Wi. On average with respect to the data, we thus
receive Eq. (13). Note that the normal case is that (w, z - v) > 0, as this holds initially with high
probability and it remains intact during training.
Combining Eq. 12 and Eq.
13) completes our argument, since
8|| 0|(((t)
- 01|2
2 (#(1), - v) S -Al=2(()= - w/12
(15)
5t.
for a A > 0. Grönwall's inequality leads to ||0(1) - w112 < [I=(0) - v(0)]l exl[lexxp(XX and hence 2t) e exponentially fast.
LRR outperforms IMP. If training the overparameterized neuron is successful with (()) > 0 and (xx) 1 0. After pruning, LRR has to train an
a(oo) 0 as discussed previously, then w/ (1)
16

---

Published as a conference paper at ICLR 2024
univariate neuron with the initial condition w ()) w (xo) 0, which converges to the correct
ground truth model. However, if wi (0) < O, IMP has to start training from wi (2) which leads wrong model estimate, discussed in Section 2.1
(0) Wi (0) < 0,
A.3 EXPERIMENTAL DETAILS
Dataset
CIFARIO
CIFARI00
Tiny ImageNet
ImageNet
Model
ResNet18
ResNet50
ResNet50
ResNet50
Epochs
150
150
150
90
LR
0.1
0.1
0.1
0.1
Scheduler
cosine-warmin
step-wamuup
nee-warmup
step-warmup
Batch Size
256
256
256
256
Warmup Epochs
50
10
50
Optimizer
SGD
SGD
SGD
SGD
Weight Decay
le-4
Te-3
1e-3
1e-4
Momentum
0,9
0.9
0,9
0.9
Init
Kaiming Normal Kaiming Normal
Kaiming Normal
Kaiming Normal
Table I: Experimental Setup
Image Classification Tasks. Table details our experimental setup. In each pruning iteration, we keep 80% of the currently remaining parameters of highest magnitude (Frankle & Carbin 2019)
Warmup Epochs. Each training run of a dense network starts with warmup epochs with a linearly increasing learning rate from upto 0.1. Weights rewound to their values after warmup in case of IMP (i.e. similar to WR). We ensure that each run of IMP and LRR has an identical rewind point (after warmup epochs).
The learning rate schedules we found to achieve the best performance in our experiments as con- firmed in Figure g and
Test Ace
75
70
80
100
60
8D
100
Spursity
Spunsity (b)
IMP [MP
IMP
.....
LRR with IMP nonk In)
LBR with IMP makk (step-rommp))
Figure 8: Comparing LR schedules on CIFAR100.
(i) ssine-warmup: Learning rate increased linearly to 0.1 for the first 10 epochs, followed by cosine Ir schedule for the remaining 140 epochs.
(ii) step-warmup: Learning rate is increased linearly to 0.1 for the first 10 epochs, followed by step Ir schedule for the remaining 140 epochs with learning multiplied by factor of 0.1 at epochs 60 and 120.
constant learning of 0.01 during the warmup phase. The learning rate is reduced by a factor of 10 every 30 epochs after the warmup phase, starting from 0.1.
(iii) ImageNet: For ImageNet,
In case of random pruning we randomly remove parameters each layer in order to maintain balanced layerwise sparsity ratio (Gadhikar et al. 2023) i.e. every layer has equal number of
17

---

Published as a conference paper at ICLR 2024
96.0
95.00
95.5
Test Ace
94.75
95.0
94.50
94.25
(cosine Ir)
94.5
(cosine Ir)
IMP (cosine-wand warmup Ir)
LRR (cosine- warmup Ir)
70
80
90
100
50
100
Sparsity
Sparsity
(a)
(b)
Figure 9: Comparing LR schedules CIFARIO.
nonzero parameters. Each run is repeated thrice and we report the mean and 95% confidence interval of these runs. All experiments are performed on a Nvidia A100 GPU. Our code built on the work of (Kusupati al. 2020).
A.4 ADDITIONAL RESULTS
We plot the layer wise distributions of the learnable scaling parameter y for our experiments. The distributions are similar on CIFARIO (Figure[TO) with most values being positive in every layer for IMP. LRR and LRR with IMP mask. Hence, rewinding BN parameters also finds similar distributions.
BN parameter distributions:
However, the rewinding BN improves performance of LRR with IMP mask CIFAR100 (See Fig. 44) This can be attributed to the reducing the number of neurons (channels) where 7 = (eg: Layer 22, 23 in CIFARI00 Fig. [T]. We find that this is necessary deeper layers aid signal propagation and hence we propose rewinding BN parameters to aid LRR when the mask is decoupled from the optimization.
CIFARI0 ResNetl
188 30
130 MMi
25
05
0.5
0.5
D09
140 mb 3d7
210
23
LIKE
18 Mrauk
LEK wIsMM rank warlE
20
10k
250
18
Figure 10: Layer wise distributions of BN parameter (7) on CIFAR10 ResNet18 at Sparsity 96%.
Interplay magnitude and signs on CIFAR100. On CIFAR100 too, the signs and mask learnt by LRR contain majority of the information required while training. When using the mask and signs
18

---

Published as a conference paper at ICLR 2024
BN CIFAR100 ReNARI Spuraty:
1.3
180 wisiMi endimet
622
500
02
1oo cob 280 120 cas eap eo
IMP
1.48
180 wili evck mvd
wi
Vola
KIUUNI
55
600
613
03
880
Figure 11: Layer wise distributions BN parameter (7) on CIFARI00 ResNet50 at Sparsity 96%.
learnt by LRR and only rewinding weight magnitudes, match the performance of LRR (see Fig.
80
78
90
85
100
Sparsity
Figure 12: (a) For CIFARI00 we compare rewinding only magnitudes to using the initial weights of IMP with the learnt LRR masks and signs.
Overall sign flips for LRR vs IMP. As verified experimentally, LRR enables more sign flips early in training. This can also be confirmed by measuring the total number of sign flips from initial signs to learnt signs at each sparsity level for both LRR and IMP. We plot the difference between the number of sign flips enabled by LRR and IMP at each pruning iteration in Figure Early sparsities show large positive difference between the number of signs flipped by LRR and IMP, showing the ability of LRR to enable more sign flips.
LRR enables early sign switches for parameter optimization. Figure 14 a, b) shows for ran- domized mask, -.Rd enables larger fraction of signs to switch earlier in training than IMP- rand in spite of unstable sign flips due randomized mask which does not align with parameter values. On the other hand, the ability to switch signs still lacks in IMP in spite training with an improved LRR mask shown in Figure 14 c, d) highlighting that the weight rewinding step leads to loss of sign information.
LRR enables early sign switches ImageNet. We report results ImageNet in Figure 15 (a) for a ResNet50. We find that our insights translate to the large scale setting as well. To support our hypothesis of the importance of learnt signs, show that using the initial weight magnitudes of
19

---

Published as a conference paper at ICLR 2024
10
sign switchss
10
10
Spanityy
(a)
Thny ImageNet
CIFARIO
CIFARI00
Figure 13: (a) Difference between number of sign slips between initial weights and weights at each sparsity level enabled by LRR and IMP. Positive differences indicate that LRR enables more sign flips than IMP.
INth-oadd
Deciit
I0 Prasin
0
30
20
33
23
30
Prosiig Land
Prasss Lovd
(6)
(b)
M0
0.2
Stan Plpe
Saa Pipe
Figure 14: (top) The pruning iteration at which the parameter signs do not change anymore and (bottom) the number of times parameter switches sign over pruning iterations, with random mask for (a) CIFARIO and (b) CIFARION 100 and with an LRR mask for (c) CIFARIO and (d) CIFARI00.
Density
Test
74
40
60
80
100
0.0
2.5
5.0
7.5
10.0
Spansity (a)
Pruning Level
(b)
LRR
init L.R
I.RRR
Figure 15: (a) Comparison of LRR IMP for ResNet50 ImageNet. (b) Histograms of the pruning iteration at which the parameter signs do not change anymore for ImageNet.
IMP with the mask learnt by LRR and the weight signs learnt by LRR, we are still able to match the performance of LRR (blue curve). Figure 15 (b) confirms that LRR enables early sign switches by the third prune-train iteration while IMP struggles to perform sign switches.
Impact of pruning criteria. In order to highlight that different pruning criteria can benefit from initial overparameteriizaton with continued training in comparison with weight rewinding, we port results for pruning iteratively with Synflow (Tanaka et al. 2020) and SNIP (Lee et al. 2019). Although, these criteria have been proposed for pruning at initialization, following the same prune-train procedure as LRR and IMP. Although LRR and IMP are used in the context of magnitude pruning, use the same terms followed by the pruning criterion to differen-
them iteratively
20

---

Published as a conference paper at ICLR 2024
tiate between training with learning rate rewinding (LRR (synflow/snip)) and training with weight rewinding (IMP (synflow/snip). For eg: IMP (synflow) indicates that each prune- train iteration prunes weights based the Synflow criterion and rewinds the nonzero weights back to their initial values.
Figure supports hypothesis that for different pruning criteria, like Synflow and SNIP, contin- ued training benefits from initial overparameterization by enabling better sign switchyoes. The blue curve confirms that as long as the mask and sign learnt by LRR (synflow/snip) is used, we match the performance of LRR (synflowsnipp) denoted by the purple curve for any weight magnitude ((IMP init LRR mask LRR sign (snip/synflow)).
96
96
95
Text
93
93
40
60
80
100
Spursity
Sparsity
(a)
IMP (synflow)
IMP (smip)
(synflow)
LRR (snip)
IMP init + LRR mask LRR sign (synflow)
IMP init LRR mask LRR xign (snip)
Figure 16: Effect of pruning criteria (a) Synflow and (b) SNIP with iterative pruning. LRR (syn- flow/snip) denotes iterative pruning with learning rate rewinding after every pruning step and IMP (synflow/snip) denotes iterative pruning with weight rewinding after every pruning step with the respective pruning criterion for ResNet18 CIFARIO. Dotted lines indicate baseline results of IMP and LRR using magnitude as the pruning criteria.
CIFARIO on VGG16. We also report results for a VGG16 model with Batch Normalization (Si- monyan & Zisserman 2015) CIFARIO. Figure 17 shows that LRR improves over IMP and that its signs and mask contain sufficient information to match the performance of LRR (see blue curve). Figure I7 further confirms that LRR enables early sign switches compared IMP, sup- porting our hypothesis that LRR gains performance due to its ability to effectively switch signs in early iterations.
94
93
Text Ace
Duusity
0.2
92
91
40
60
80
100
10
20
Spunsity (a)
Pruming Level
(b)
IMP
LRR
IMP init + LRR mask
LRR sign
Figure 17: (a) Comparison of LRR versus IMP for a VGG16 model on CIFARIO. (b) Histogram of the pruning iteration at which the parameter signs do not change anymore.
Impact of overparameterization on single hidden neuron network. We show that increasing overparameterization in the input dimension d for the single hidden neuron network defined in Sec- tion 2 aids LRR. We follow the same experimental setup as Section 2.3 In the when d 1, LRR and IMP are equally likely to succeed for the case where a(0) 0, (0) > 0 (see Figure 18 a)). If we increase d 1, we find that LRR is able leverage the overparameterized model
21

---

Published as a conference paper at ICLR 2024
in the early pruning iterations to flip initial bad signs and succeed more often than IMP (see Figure 18 b), (c), (d)) as long as a(0) >
d=
d=
d= 10
10
Tost Loss
10
a.40
02-0
42-0
a<
ac
4.3-
440
91.00
41.50
M: <00
3-0
05,00
Mry
<.0
00.00
19.00
4150
9120 1: 10:40
<0
(8)
(b)
(e)
Figure 18: Effect of increasing input overparameetrrizatinn (measured by the input dimension (d) for the single hidden neuron network. Without overparaaectrrizttion (a) d = and with overparameter- ization (b) (c) d 5 (d) d
10.
22


Reviews:
[{"review_id": "uvpFUEnQVC", "reviewer": "Reviewer_6o5w", "summary": "This study compares two key techniques in deep neural networks: Learning Rate Rewinding (LRR) and Iterative Magnitude Pruning (IMP). A clear and detailed analysis of both methods highlights the benefits of LRR, particularly its early parameter sign switching and better optimization of various network structures.\nThrough practical testing on different models and datasets, the authors present LRR's advantages, emphasizing it as a more versatile method for neural network optimization. This research serves as practical groundwork for further exploration of improvements to sparse training algorithms.\nInterestingly, the authors examine the impact of sign perturbations. The experimental evidence in the paper shows that at lower sparsity levels, the impact of sign perturbations is small, but it has a significant effect on performance in the complex CIFAR100 dataset. This evidence further aligns with the authors' point - LRR is not only better at identifying masks but also optimizes various mask scenarios.", "questions": "See above weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper presents two new advantages of Learning Rate Rewinding (LRR) and validates their existence, offering fresh insights not covered in previous LRR research. This work is an essential foundation for understanding and improving network pruning algorithms, particularly the LRR method. One notable contribution is the discovery of parameter sign switching, a key characteristic of LRR. This not only reveals a unique facet of LRR but also offers new perspectives for understanding and designing more effective algorithms.\nThe article presents enough experiments as evidence. Firstly, it uses a single hidden neuron model for learning tasks, showing that LRR has more success cases than IMP because LRR can avoid problematic initial sign configurations.\nThe paper further validates LRR's advantage over IMP through a series of representative tasks and networks. Experimental results show that LRR performs well in standard benchmark tests such as CIFAR10, CIFAR100, and Tiny ImageNet, regardless of its combination with ResNet18 or ResNet50. These results strongly support the superiority of LRR over IMP in deep neural network training.", "weaknesses": "This paper impressively combines clear presentation with strong experimental results, and I have yet to identify any significant shortcomings. But I have some questions about hyperparameters :\n1. Considering that hyperparameter tuning is generally a problem-specific task, do you believe this sensitivity might hinder the practical application of LRR? Could you provide some advice or guidelines for hyperparameter selection or tuning when using LRR and discuss how the learning rate schedule influences the performance of this algorithm?\n2. Your paper also indicates that LRR can benefit from the overparametrization of neural networks. Can you elaborate on how this overparametrization impacts the functionality of LRR? Is it possible to have too much overparametrization, which could negatively impact the performance of LRR?", "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": "", "extra_scores": {}}, {"review_id": "FclSJ0qybO", "reviewer": "Reviewer_z4v8", "summary": "This paper delves into the effectiveness of learning rate rewinding (LRR) both from a theoretical and practical perspective, with a specific focus on the concept of weight sign flipping. In the context of a single-layer neural network, the authors offer theoretical evidence that LRR can reliably rectify initially problematic weight sign patterns by inheriting the sign information from a well-trained overparameterized model. When applied to more complex neural networks, empirical findings validate that the observed changes in weight sign configurations align with the theoretical insights. Furthermore, the authors dissect the impact of LRR into two distinct components: sparse network optimization and the performance of the generated mask. Through rigorous experiments, they provide empirical support for LRR's exceptional performance in both of these aspects.", "questions": "- Is there any further results on ImageNet or any large-scale datasets?\n- In Figure 3, is the presented LRR results with or without BN rewinding?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper offers a clear rationale for the effectiveness of LRR by examining it through the perspective of weight sign flipping, which is a pioneering work in exploring sign flipping within the context of sparse neural networks. The authors provide theoretical evidence demonstrating that LRR gains an advantage from flexible mask sign configurations, in contrast to IMP, a finding substantiated by empirical experiments at a toy-level. This research has the potential to serve as a source of inspiration for the advancement of more efficient sparse training algorithms that can leverage the power of mask sign configurations.\n- The paper presents carefully designed ablation studies investigating two distinctive roles of LRR in (i) sparse neural network optimization and (ii) discovering a good sparse mask.  \n- The paper is effectively structured and exhibits clear and concise writing\n- The paper covers a fair amount of relevant previous studies.", "weaknesses": "- While the authors argue LRR finds a better mask than WR in Figure 3, I wonder if a longer training epochs within each IMP cycle would help WR to find a superior mask. In other words, are both WR and LRR fully converged? If that’s the case, does the mask configuration stay constant after convergence? Further, if the optimal mask can be attained only at the end of the training epochs, it could pose challenges in efforts to reduce the computational cost associated with IMP (both WR & LRR).\n- Concerning the flexible LRR mask analysis (see Figure 4), there appear to be some questionable findings. For instance, the \"LRR with IMP mask (blue)\" does not appear to show significant improvement over WR (orange) except for the case of Cifar-10 with a moderate level of sparsity. Moreover, it is unclear regarding the implication of \"LRR w/ BN rewind (yellow)\" in Figure 4 in the context of \"flexible LRR training.\"\n- In Figures 3 and 6, there are only two sets of experimental results available for analysis, Cifar-10 and Cifar-100. The authors argue that Cifar-100 results may not fully meet expectations due to its higher complexity. However, it remains an open question whether the same trend would hold for different network architectures, such as VGG networks.", "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": "", "extra_scores": {}}, {"review_id": "sozSUf8Fmz", "reviewer": "Reviewer_yLRG", "summary": "The paper explores LRR and IMP, the key methods for identifying lottery tickets in large neural networks, with the goal to understand the differences between mask learning and parameter optimization. The paper provides valuable theoretical results for one hidden neuron networks predicting the LRR's superior performance due to its ability to overcome initial parameter sign challenges. Experiments with ResNets on CIFAR10, CIFAR100 and Tiny ImageNet demonstrate LRR's superior performance due to its ability to adjust the parameter signs early in training.", "questions": "* The conclusions for CIFAR10 and CIFAR100 often diverge (Fig. 4: LRR with IMP mask vs IMP, Fig. 7), however the explanation for this divergence is not well understood. Although the authors list potential reasons, there is no experiment to support or reject the hypothesis. Evaluation on more datasets and more architectures should help to provide a stronger evidence for the claims and the relevance of the obtained theoretical findings.\n* What is the meaning of the light blue line in Fig. 11?\n* How does Fig. 12 support the claim made in the figure caption \"LRR enables considerably more sign flips than IMP and thus improving mask identifcation and parameter optimization\"?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper addresses and important, timely and high-impact problem, which could help to drastically improve the efficiency and decrease the cost of sparse training. \n* Decoupling structure learning and parameter learning is interesting and the steps taken in the paper are meaningful.\n* The theoretical results on one hidden neuron networks are interesting, strong, and well described. \n* The experimental results support the claims of the paper, although the performance differences between LRR and IMP are small.", "weaknesses": "* Although the main ideas explored in the paper and the theoretical insights are strong, the empirical evaluation is limited to ResNet architectures. The empirical results are mainly reported for CIFAR10 and CIFAR100. Extending the findings to more architectures and other domains would be helpful to understand the significance of the findings. Additionally, to reviewer's understanding, several figures do not fully support the claims made in the text (see questions below).\n* Magnitude pruning is explored as the only strategy to train sparse networks. Can the findings regarding the superiority of LRR be generalized and extended to other pruning strategies? \n* An exploration of the impact of the learning rate would also help to better understand the practical value of the proposed analysis.\n\nMinor: A missing reference [?] on p.3. \"LRR is improves parameter optimization\" on p.7.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)