Mask in the Mirror: Implicit Sparsification
Authors: Tom Jacobs
Rebekka Burkholz
Venue: ICLR 2025 Poster (2025)
Keywords: Continuous sparsification
Implicit bias
Mirror flow
Time-dependent Bregman potential
Regularization
Rich regime
Primary area: optimization

Abstract: Continuous sparsification strategies are among the most effective methods for reducing the inference costs and memory demands of large-scale neural networks. A key factor in their success is the implicit $L_1$ regularization induced by jointly learning both mask and weight variables, which has been shown experimentally to outperform explicit $L_1$ regularization. We provide a theoretical explanation for this observation by analyzing the learning dynamics, revealing that early continuous sparsification is governed by an implicit $L_2$ regularization that gradually transitions to an $L_1$ penalty over time. Leveraging this insight, we propose a method to dynamically control the strength of this implicit bias. Through an extension of the mirror flow framework, we establish convergence and optimality guarantees in the context of underdetermined linear regression. Our theoretical findings may be of independent interest, as we demonstrate how to enter the rich regime and show that the implicit bias can be controlled via a time-dependent Bregman potential. To validate these insights, we introduce PILoT, a continuous sparsification approach with novel initialization and dynamic regularization, which consistently outperforms baselines in standard experiments.

Published as a conference paper at ICLR 2025
MASK IN THE MIRROR: IMPLICIT SPARSIFICATION
Tom Jacobs
Rebekka Burkholz
CISPA Helmholtz Center for Information Security tom. jtt.jaaccssssssp.
CISPA Helmholtz Center for Information Security cuzkholz@cisse de
ABSTRACT
Continuous sparsification strategies are among the most effective methods for re- ducing the inference costs and memory demands of large-scale neural networks. A key factor in their success is the implicit L1 regularization induced by jointly learning both mask and weight variables, which has been shown experimentally to outperform explicit L1 regularization. We provide theoretical explanation for this observation by analyzing the learning dynamics, revealing that early continu- ous sparsification is governed by an implicit L2 regularization that gradually tran- sitions to an L1 penalty over time, Leveraging this insight, we propose a method dynamically control the strength of this implicit bias. Through extension of the mirror flow framework, we establish convergence and optimality guarantees in the context of underdetermined linear regression. Our theoretical findings may be of independent interest, as we demonstrate how to enter the rich regime and show that the implicit bias can be controlled via a time-dependent Bregman po- tential. To validate these insights, we introduce PILoT, a continuous sparsification approach with novel initialization and dynamic regularization, which consistently outperforms baselines in standard experiments.
INTRODUCTION
Deep learning continues impress across disciplines ranging from language and vision (Ramesh) et al. 2022) to drug design (Stephenson et al., 2019 Jumper et al.) (02I) and even fast matrix multiplication (Fawzi et al.) 2022). These accomplishments come at immense costs, as they rely on increasingly large neural network models. Moreover, training such massive models with first-order methods like variants of Stochastic Gradient Descent (SGD) is a considerable challenge and often requires large-scale compute infrastructure (Kaack et al. (022). Even higher costs are incurred at inference time, if the trained models are frequently evaluated (Wu et al. 2022 Luccioni et al. 2023)
Sparsifying such neural network models is thus pressing objective. It not only holds the promise to save computational resources, it can also improve generalization (Frankle & Carbin 2019 Paul
et al. 2023). interpretability (Chen al. 2022; Hossain et al.) (024), denoising (Jin et al. [022]
Wang et al. 22023), and verifiability (Narodytska et al.) 2020 Albarghouthi] 2021). However, at its core is hard large-scale nested optimization problem combining multiple objectives. In ad- dition to minimizing a typical neural network loss minweR- f(w) (and its generalization error), we wish rely on the smallest possible number of weights, effectively minimizing the Lo norm min || This is an NP-hard problem that is also practically hard to solve due to its mixed discrete and continuous nature. This becomes more apparent when we reformulate it like the best performing sparsification methods.
Among such approaches that achieve high sparsity while maintaining high generalization perfor- mance are continuous sparsification methods and iterative pruning strategies. These methods ex- plicitly identify for each weight parameter w of a neural network a binary mask m E {0, 1) that signifies whether a parameter is pruned. Thus, parameter is set to zero (m 0) or not (m 1), effectively parameterizing the network with parameters x = m O w, where O is the pointwise mut- liplication (Hadamard product). The introduction of the additional mask parameters sparsity objective into a discrete L1 penalty of m as w| @ milL, = E, m, subject to m, E {0, 1), where @ denotes elementwise multiplication and we assume that * 0 if m = 1. The L1 objective is already more amenable to continuous optimization than the original Ln objective (Louizos et al. 2018). Nevertheless, the big challenge arises from the fact that is binary.
turns the

---

Published as a conference paper at ICLR 2025
Continuous sparsification addresses this issue by relaxing the optimization problem to continuous or even differentiable variables m, often with m E [0, 1] by learning a parameterization m = g(s) with g: I + [0. 1]. e.g., like sigmoid. This way, the problem becomes solvable with standard first-order optimization methods. Yet, moving from the continuous space back to the discrete space is error-prone. Regularizing and projecting m towards binary values (0, 1] is generally problematic, requires careful tuning, and often entails robustness issues.
However, this projection step is not necessarily required in a parameterization m O w. where m can freely attain values in IR. Ziyin & Wang (2023) show that a loss with this parameterization m O w combined with weight decay a (1 mm i w (i.)) is equivalent to LASSO and thus an explicit L1- regularization (Ziyin (023). Yet, their proposed method spred significantly outperforms LASSO, which suggests that the posed equivalence of optimized objectives cannot explain this success.
As we show, an important, but overlooked, distinguishing factor is the fact that continuous sparsifi- cation with m @ w parameterization is driven by an implicit rather than an explicit regularization. This implies that in a sufficiently overparameterized setting, the following hierarchical optimization problem is solved:
min || ==)=:
The main idea follows the same philosophy as the lottery ticket hypothesis (Frankle & Carbin 2019). From range of models which all attain optimal training loss, it prefers the sparsest model. In other words, we aim to find a subnetwork with similar accuracy having two competing objectives, we enforce cooperation between the two objectives by subjugating the sparsification. While this formulation can have advantages, if we can attain zero training loss (f()) = 0), it might still be equivalent to an explicit regularization.
dense network. Instead of
The real potential of continuous sparsification and its induced implicit bias (in particular in non- convex settings) becomes apparent when we study the corresponding learning dynamics. Our the- oretical analysis of (stochastic) gradient flow applied to m @ w reveals that the dynamics differ fundamentally from the ones of LASSO, where redundant features are sparsified exponentially fast. Instead, we show by extending the mirror flow framework that a dynamic explicit weight decay can move the implicit bias from L2 to Lı during training. In consequence, the sparsification becomes ef- fective only relatively late during training, allowing the overparameterized model to first attain high generalization performance. The dynamics resemble thus successful strategy that is applied across continuous and iterative pruning methods, which all acknowledge and realize the premise that train- ing overparameterized models before they are sparsified usually leads to significant performance benefits (Frankle & Carbin| 2018 Paul et al. 2023) Gadhikar & Burkhhlz, 2024).
Our analysis extends the implicit bias framework, which covers different parameterizations (Pesme cet al. 202 Gunasekar et al., 2020: Woodworth et al. 2020; Li et al. 2022) and the well-known fact that standard gradient flow has an implicit Le bias (Nemirovski & Yudin 1983 Beck & Teboulle, 2003). Another common use of the framework has been to study when training dynamics enter the so-called rich regime, which is responsible for improved feature learning. In this context, we study two main innovations. a) As we show, the explicit regularization (i.e. weight decay on m and w) guides the strength of the implicit bias. The fact that this makes the implicit bias tuneable makes it practically relevant for sparsification, as we have to be able to reach target sparsity. b) By proposing a dynamic regularization (rather than common static one), we obtain control over the transition speed from L2 to L1 regularization, which is crucial for performance gains in the high sparsity regime and enables us to enter the rich regime. From a conceptual point of view, we unite explicit and implicit bias within a time-dependent Bregman potential, which is potentially of independent theoretical interest.
While our general derivations provide insights into various continuous sparsification approaches, including STR (Kusupati et al., 2020), spred ZZyin & Wang (2023), or (Savarese et al.) 202T), J. we also utilize them to propose
improved algorithm, PILoT (Parametric Implicit Lottery Ticket). PILoT combines the m @ w parameterization with a dynamic regularization and an initialization that enables sign flips. Such sign flips are key effective sparse training (Gadhikar & Burkholz 2024). but are not feasible with the spred initialization. The dynamic regularization and thus implicit bias leads us to outperform state-of of-e-of-theeart baselines in particular in the high- aig-sppasitty regime, demonstrate in extensive experiments.
In summary, we make the following contributions:
2

---

Published as a conference paper at ICLR 2025
We gain novel insights into continuous sparsification by highlighting its implicit bias to- wards sparsity induced by doubling the number of trainable parameters. In particular, we explain the effectiveness of spred Ziyin & Wang 2023), which is based m w.
To the best of our knowledge, we are the first to introduce the implicit bias with an explicit regularization resulting in a mirror flow with a time-dependent Bregman potential.
We provide convergence results for (quasi)-convex loss functions (Thcorem 2.2) and opti- mality for underdetermined linear regression (Theorem 2.3 with time-dependent Bregman potential.
Improving results by (Alvarez et al. 2004 Li al. 2022), replace convexity with the Polyak-tojasiewiizz inequality, quasi-convexity and a growth condition on the Bregman potential (see Theorem A.3).
Using our extensions of the mirror flow framework, we propose new continuous sparsifi- cation method, PILoTT, which controls the implicit regularization dynamically moving from L2 to L1. Its initialization enables sign flips in contrast to spred.
In experiments for diagonal linear networks and vision benchmarks (including ImageNet), PILoT consistently outperforms baseline sparsification methods such as STR and spred, which demonstrates the utility of our theoretical insights.
1.1 RELATED WORK
Neural network sparsification. A multitude of neural network sparsification methods have been
proposed with different objectives (Liu & Wang, 2023). A popular objective is, for instance, to save
computational and memory costs primarily inference, also during training, which is linked to
the time of pruning, i.c., initially (Frankle et al. 2021 Lee et al.
2019; Tanaka et al.] (2200 Wang
let al.
2020
Pham al. 2023 Patil & Dovrolis 2021 Tanaka et al. [020:] Liu et al. [021] | Gadhikar
eet al.
2023 Fischer & Burkholz [001). early during training (Evci et al. 2020 Dettmers & Zettle-
moyer
2019), during training like continuous sparsification (Sreenivasan et al. [022 Kusupati al.
2020
Savarese et al., 2021 Peste et al. |202 or within multiple pruning- trriiinn-rriinng iterations (Han
al.
2015 Frankle & Carbin 2018] You et al., 2020, Renda al. 2020 Gadhikar Burkholzz
2024..
Other distinguishing factors are which type of sparsity the methods seek, if they focus on sav-
ing computational resources and memory in specific resource-conse constriend environments or, which
methodological approach they follow.
Unstructured sparsity. In this work, we focus on unstructured sparsity, i.e., the fraction of pruned weights, and thus seek to remove as many weight entries as possible, which can achieve generally the highest sparsity ratios while maintaining high generalization performance. Structured sparsity, which usually obtains higher computational gains on modern GPUs (Kuzmin al. 2019 Wen et al., 2016 Lasby et al., 2023). could also be realized in the continuous sparsification setting, for instance, by learning neuron-, group, even layer-wist masks. Yet, this would not enjoy the same theoretical benefits as we derive here by showing that the unstructured continuous m @ w parameterization induces mirror flow, whereas for example the neuron-wise mask does not (see Section D)
Iterative pruning. Iterative pruning is often motivated by the Lottery Ticket Hypothesis (LTH)
FFanklle & Carbin 2018), which conjectures the existence of sparse subnetworks of larger dense source networks that can achieve the same accuracy as the dense network when trained (Frankle)
al. 2021
Liu et al. 2024 Malach et al. 20000 Orseau et al. 2020 Pensia al. 2020 Burkholz
et al. 2022). In addition to the sparse structure, iterative pruning tries to identify trainable parameter initialization, indirectly also implementing an approximate In-regularizzatio. In repeated prune- train iterations, trained weights are thresholded according to an importance score like magnitude. Afterward, the remaining parameters are free to adapt to data in new training run and not be regularized by a sparsity penalty (like L1). Our proposal PILOT can be combined with such iterative schemes. The experiments show that it boosts performance of sfate-of-the-art schemes like Weight Rewinding (WR) (Frankle et al. 2019), and Learning Rate Rewinding (LRR) (Maene et al. 2021).
2022 Fischer & Burkholz, 2021 Burkholz, 2022a by da Cunha et al.) [0222] Ferbach et al.)
Continuous sparsification. Continuous sparsification characterizes collection of methods that can compete with iterative pruning techniques, while often requiring fewer training epochs (Sreenivasan et al. 2022 Kusupati et al. 2020). In one of the first proposals by (Savarese et al., 2021), the mask
3

---

Published as a conference paper at ICLR 2025
is relaxed to continuous variable. In general, continuous sparsification can be combined with
probabilistic approach where m is interpreted as a probability (Louizos et al.
2018:
Zhou et al,
2021abb). Other parameterizations of m that are not restricted to the range [0. (e.g.
Powerpropa-
gation) can also be utilized to regularize towards higher sparsity (Schwarz.ed et al. 2021)
). Yet, they are
usually combined with projection to map to binary mask. The spred algorithm (Ziyin & Wang
2023) removes any projections and shows that m O w with weight decay solve a LASSO objective. To explain its performance gain over LASSO, we extend the mirror flow framework and find an explanation in the training dynamics. Our extension, PILoT,, dynamically adjusts the weight decay and induces a transition from an implicit Lg to L1 regularization. This enables it outperform the sfate-of-the-art method STR Kusupati et al.) 2020) in the high-sparsity regime. For a survey of other methods see (Kuznedelev et 2003))
Implicit bias, The implicit bias of (S)GD is well-studied phenomenon CChizt & Bach 2020 Li
et al. 2022
Woodworth et al.] 2020, Gunasekar et al.
2020:
2017 Chou et al.) 2024] Vaškevičius
et al.
2019 Li et al. 2023] Zhao et al. 2022; Li et al.
2021 and can in certain cases be described
by a mirror flow or mirror descent (in the discrete case with finite learning rate) (Li et al. 2022).
Originally, mirror descent was proposed to generalize gradient descent and other first-order methods
in convex optimization (Alvarez et al. 2004 |Rockaelllrr & Fenchel| 1970, Boyd & Vandenberghe
2009
Nemirovski & Yudin| 1983, Beck & Teboulle, 2003). Moreover, has been used to study
the implicit regularization of SGD in diagonal linear networks (Pesme et al.] 2021 Even et al.
2023
More recently it also has been applied analyze the implicit bias of attention (Sheen al.
2024. While (Li et al. 2022) has shown that different parameterizations have a corresponding mirror flow, we find that m O w with our proposed explicit regularization, PILoT, gives rise to a corresponding time-dependent mirror flow. Its time dependence gives us means to control the implicit bias, while still achieving convergence. Time-dependent mirror descent has so far only been studied in the discrete case as general possibility (Radhakrishnan et al.) (022]) The time dependence also naturally arises in SDE modelling, yet, without control of the implicit bias (Pesme) et al. [021]; Even et al., 2023). Here, we not only highlight practical use case for time-dependent Bregman potentials, we also derive a way to control and exploit it.
Optimization and convergence proofs. Loss landscapes and the convergence of first-order methods is a large field of study (Karimi et al., 2016 Fehrman et al. 2019) in its own right. We draw on literature that shows convergence by using the Polyak-Lojasiewerr
inequality (Wojtowytsch) 2021 Dereich & Kassing 2024). which is a more realistic assumption in the deep learning context than, for example convexity, because it can hold locally true for non-convex loss functions that are common in machine learning.
CONTROLLING THE IMPLICIT BIAS WITH EXPLICIT REGULARIZATION
Structure of theoretical exposition. Our first goal is to advance the mirror flow framework from (Li al., (002) to incorporate time-dependent regularization. This is a key innovation that forms the foundation of our proposed PILoT algorithm (Algorithm D]. The dynamical description also covers constant regularization, as implemented in the spred algorithm. We begin by integrating time-dependent regularization in the mirror flow framework in the case of the parameterization m O w combined with time-varying weight decay. This corresponds to a time-dependent Breg- man potential, enabling more dynamic and powerful form of implicit regularization. The implicit regularization becomes controllable and moves from an L2 to an L2 regularization. Building on this, Theorem 2.1 rigorously characterizes this process within this extended framework, offering new insights into the sparsification process. Then Theorem estaabilsss convergence to a solution of the original optimization problem. Sparsity is still attained according to Theorem 2.I] which can also be observed in the gradient flow in Eq. (6) of PILOT. For diagonal linear networks, which is an analytically tractable setting, we also prove optimality, as stated by Theorem 2.3 This highlights a mechanism how our method PILoT improves over spred, since spred cannot reach optimality.
Optimization problem. Consider the following time-dependent optimization problem for loss function f RR" + R:
min f(m @ w) + (11ml12, + 11w01122))
(2)
m.wER"
4

---

Published as a conference paper at ICLR 2025
where Ot 2 0 can change during training. In contrast, Ziyin & Wang 2023 set ay constant and show that Eq. is equivalent to the LASSO objective. Why does spred tend to outperform LASSO then?
Seeking answers in the training dynamics. The gradient flow associated with minimizing the con- tinwously differentiable loss function f is: dæ, (xx))dt 20 Zimi- Using this gradient flow framework, (Li et al. 2022) show that a reparameterization or overparameterization of the param- eters leads mirror flow. A mirror flow informally minimizes a potential in the background, for example, the Lı or L2-norm. In contrast, explicit regularization forces a direct trade-off. The no need for trade-off becomes clear in the convergence and optimality theorem.
+ R be a differentiable function. It is Mirror flow. Concretely, to define a mirror flow, let R R described by
dV - (xx)
= Finit
(Li et al. 2022) provide sufficient conditions for paramerization g: M R to induce mirror flow, where M is smooth sub-manifold in IR for D 2 n. The parameterization m 3 w falls into this category. The corresponding potential R is either close to the L1 or L2 norm depending on the initialization of my and wo. If we could steer it towards L1, we could therefore induce an implicit regularization towards sparsity. yet, not without issues.
Two caveats and their solution. a) The potential 0). This also holds for other reparameterizations (Li et al.) 2022). In consequence, we would not promote actual sparsity for zo * O. b) To induce In regularization and enter the rich regime, the initialization of both mg and w/ would need be exponentially small (Woodworth al. 2020).
R attains its global minimum at the initial 2g (and
The explicit dynamic regularization of PILoT in Eq. (2) solves both of these problems, as we show next. The corresponding mirror function A is stated in Theorem A. and the corresponding conver- gence and optimality theorems in Theorem A.2 and A.4
Dynamic regularization. Next we present the main result, the dynamical description with time- dependent regularization. The exact dynamics are described by the time-dependent mirror flow and derived in Theorem 2.1
Theorem 2.1 Let wo for all i [n], the dipendependent Bregman potential is given by
Re, (I)
1 a
Σe
ztarcsinh
Ii
V x
-1,log
Ug,i
at,
20,
with azi 20, (-2 crdds) and uo,i mo.stwo.s and vo,i
ma --o.1-Wo..
The gradient
//2
/2
flow of x4 = my O Wp induced by Eq. (2) then satisfies
dV Ra, (xx) V (xt))dt
To = mg O Wp-
Proof. The proof is given in the appendix. The main steps are: a) Deriving the evolution of the gradient flow (Lemma B.I). b) Showing that it satisfies the time-dependent mirror flow (Lemma
B.2). Note that step a) also derives Eq. (6)
Observe that the potential in Eq. (3) now depends de- This changes the global minimum
Ra, (z) = = x exp (-2 agds
O my
C wp-
Thus, we gain control over the positional implicit bias, solving our problem with the nonzero global minimum. Next, we characterize the asymptotic behavior, which control in practice with on, which determines also The asymptotics follows from Theorem 2 in (Woodworth et al. 2020
For + 0 and - JC, we receive
-
(x( log
|||||
Interestingly, the term æ;log log(L) in front of the other term dominates. Figure 1 illustrates the asymptotics for the one dimen- sional case. We observe that our previously identified mirror flow caveats be resolved: a)
Mp.. does not play a role in the asymptotics. The reason that
5

---

Published as a conference paper at ICLR 2025
Increasing moves the minimum the origin, leading to L1 regularization. This implies initial- izing at zero with an exponentially small scaling (i.e. a + 0) is not necessary. b) Moreover, the regularization a has exponential and time-dependent effect dynamics towards an L regularization at the desired speed. In conclusion, our extension and novel analysis have revealed how explicit regularization solves the problems of the standard mirror flow framework.
az- It thus enables steering the
Remark 2.1 At the end of LASSO training, the regularization can be turned off to enable the search for better solution. However, this risks losing the benefits of the regularization, for example, if the basin of attraction contains non-sparse critical points. In contrast, for the mow reparaneterization, the dependent Bregman potential steers (but does not force) the bias towards sparsity.
Convergence and optimality. It remains to be shown that convergence and optimality results transfer from the mirror flow framework to the time-dependent mirror flow framework. For quasi-convex loss functions, we prove convergence a critical point. For convex quasi-convex functions that sat- isfy the PL-inequality, we derive convergence to a minimizer.
20
2
10
Theorem 2.2 Assume f quasi-convex. f is locally Lips- chitz and [
R²) is non-empty. Assume 04 for all 2 0 and that So a,ds oo for t [0, oc) U {oc). Then as t + DC, converges to some critical point x". Fur- thermore, if is either convex or both quasi-convex and satis- fies the PL-inequality in Eq. (9). Then It convergences to an interpolator x² that a minimizer of f. Furthermore, in the PL-inequalit case, the loss converges linearly such that there a constant C > 0 such that
4
2
R
0
3
X
Figure 1: Evolution the time- dependent Bregman potential. Jo a,ds is the exponent of az.
f(x)) - [(x)) < Bexp( (-)
(4)
where B (f(x)) - f (x*)) exp (C'|=* [| So a,ds) with C depending on the smoothness of the loss function and Ase min, (mo.: - wh,) exp (-2 S00 a,ds).
The main steps of the proof are to show that a) the iterates are bounded and converge to a critical point (Lemma ;) b) the loss converges (Theorem B.I.. A noteworthy tool is a time- dependent Bregman divergence, which we use bound the iterates. Furthermore, we utilize that at 2 O converges to zero, resulting eventually in non-increasing evolution of the loss.
Proof.
Potential drawbacks. Theorem 2.2 guarantees convergence in the case of implicit regulariza- tion. Explicit L1 regularization or spred, on the other hand, cannot achieve the same result due to constant regularization, which we will also highlight in experiments. Regardless, note that the constant B in Eq. 44) could be large. Furthermore, to reach the implicit L L--regularization,
a, = (m) w exp
2 l (ads)) needs to be exponentially small similarly as in Theorem 2 in Woodworth al., 2020). These two potential drawbacks also reveal where the method will work, namely, in overparameterized settings where the solution x" should have less active parameters. Then B potentially relatively small.
Remark 2.2 / one-sided inversely Lipschitz. a speed-up is possible. The quantity that needs to be bounded for convergence is fx)(z) Zz. In this case, we get
-V((z)) < -Vf(x)) 1 112, S
1|x x1
where C is the bound on the smoothness of the loss function f. This implies that when the interpo- lator x² ss 0 is small, the right-hand side is negative, leading a speed-up. This condition is also known as coercive.
Optimality. The main assumption in Theorem 2.2 is a2 + O, which ensures convergence to a
minimizer of the original problem, while retaining sparsity depending o a In the case of diagonal linear networks, we can even prove optimality with respect to the final Bregman potential R.

---

Published as a conference paper at ICLR 2025
Theorem 2.3 In case of uunder-determined regression consider the loss function f(z) f( x
Y).
Assume f satisfies the conditions with at least one of the convergence criteria of Theorem 2.2 I, converges to x² such that
Then
=
argmin z==Y Ra (a))-
(5)
Proof. We show that the KKT conditions of Problem (5 are satisfied (Theorem B.2
Take away. We have shown that our extended mirror flow framework can attain convergence and optimality in an analytically tractable scenario. Furthermore, from practical side, it also gives us new tools to derive more promising continuous sparsification techniques with implicit regularization. In the following section, we propose a way to dynamically control the transition from implicit L2 regularization to L1 during training with the help of the derived time-dependent Bregman potential.
THE ALGORITHM: PILOT
Like spred, our algorithm PILoT (Algorithm I utilizes the parameterization @ but pro- poses a novel initialization and dynamic regularization schedule to control the transition from im- plicit L2 to Ln regularization. To attain the desired results in the original parameterization æ, first derive its gradient flow.
Gradient flow. Essentially, the gradient flow follows from the analysis in Section 2 According to Theorem 2.2 we guarantee convergence by ensuring ar + O. Concretely, the gradient flow for Tt my wy induced by Eq. (2) is given by:
dx, --va x7 t
(f(2)) + 20,
Ft.
dt,
Zinit:
(6)
V2i
+
(-2 2- a,ds) my and wp have to be initialized such that mp wp Tinit- Note that all operations are point-wise. The derivation is based on the time-dependent mirror flow in Section
where 0g (m] wx) exp
Remark 3.1 The gradient flow in Eq. 16) allows us to make a direct comparison to the continuous sparsification method STR (Kusupati al. 2020). Instead of the soft thresholding operator, have Vuž + oz. The main difference is that STR does not change the magnitude of the gradient update outside of the (learnable) threshold, while both PILoT and spred actively change the magnitude depending on the magnitude of the weight. This active sparsification explains why spred and also PILoT can perform better in the high-sparsity regime.
Spred. The gradient flow in Eq. (6) explains why spred performs better than LASSO and highlights where spred can further be improved. Note that the balanced initialization of spred is defined such that m w 0 and the regularization is constant
a. Plugging this into Eq. (6) gives
dx; = x
о (Vf(z,) + 20sign (z+)) dt,
Zo = Pinit.
Compare this with the gradient flow of LASSO with regularization strength 20:
dr. ( (xx) + 2asign (z+)) dt,
T0 Tinit-
We observe that the main difference to the gradient flow of LASSO is the factor / v This implies the considerable trawback that spred gradient flows cannot sign flip. Therefore, cannot reach the optimal solution specific minimizers potentially. Another way to see this is studying the evolution
_r 20 exp (4sigg (ar) fo V (x 2at) satisfying Eq. 77. In practice, the absence of sign flips might be remedied by using a large learning rate and noise. The evolution also explains why it decays redundant parameters exponentially faster instead of linearly. other words, the gradient update is proportional to the magnitude of the parameter. Therefore, the evolution of spred (Eq. (7) can converge faster and come closer to than LASSO.
it perform better than LASSO,
PILOT. Our main goal is to remedy the caveats of the spred by inducing the more general gradient flow in Eq. (6) The first improvement is to enable sign flips by changing the initialization to m

---

Published as a conference paper at ICLR 2025
w = > O. where 3 denotes the scaling constant. After discretizing Eq. 6 the effective learning rate at initialization 2n = 0 is 77 1718), where 1 > O is the learning rate. Therefore, we use = in the experiments that the learning rate 7) is not altered.
Our second and main improvement is induced by the time dependence of ag a controls the strength of both the implicit and explicit regularization via at. If a, >> It. then the regularization term in Eq. 6 resembles an L2 instead of an L norm. Therefore decreasing a, moves the implicit regularization from L2 to Li. Accordingly, we sparsify only mildly in early training epochs in contrast to spred. We have shown this formally in Section 2 Furthermore, convergence is covered by Theorem 2.2 when ag + Even when PILoT attains similar sparsity as spred the end of the training dynamics, it can usually still achieve a higher accuracy due to its improved training dynamics.
Details on PIL.T. The described design choices define Algorithm [ Our update of the regulariza- tion strength 0g depends on three quantities: a) the sparsity threshold K for the weights (a hyper- parameter), b) the training accuracy, and c) 5 > 1, the multiplicative factor to gradually increase or decrease the regularization strength. The regularization strength (and thus sparsity) grows the sparsity threshold has not been reached yet and the training accuracy has increased in the previous gradient update step. As the strength is adaptive, the algorithm less sensitive to the initial strength ag. Note that the setting 5 and B 0 corresponds to spred. Therefore, PILoT is strict gen- eralization of spred. In contrast to spred, however, after half of the training epochs, we decay the regularization strength regardless of whether the sparsity threshold K is reached. This guarantees convergence of the corresponding gradient flow, in accordance with Theorem 2.2
Algorithm PILoT
Require: epochs T, schedule Cinit, initialization Tinit, scaling constant / Initialize mo; wo such that mg C wo Tinit, my w = B, 6 2 and, K
0g + Qinit
+ Set f(m, w, an) := f(m O w) + ao (11mll,, + 1|w])2,)
conrent.training..
for k in 1... . do
(m,, wx) = OptimizerStep
if TTaaninngacce
wwwrent.trainingg.. and Ii c wxlle, 2 K and k S then
ag + 1
else
OK - 0 end if Currentt.rriiingg.cce + Training.ace
end for return Model fXT) with 2T = mT ② WT
EXPERIMENTS
We demonstrate the effectiveness of PILoT in extensive experiments covering three different sce- narios. Firstly, we confirm our theoretical results on the gradient flow in Theorem 2.3 Secondly, we compare PILoT with other state-of- -o--th--rttt-tt- continuous sparsification methods such as STR (Kusupati) jet al., 2020) and spred (Ziyin Wang 2023) one-shot setting. In this context, we also isolate the individual contribution of our initialization. Finally, we combine PILoT with iterative pruning methods such as WR (Frankle & Carbin 2019) and LRR (Maene et al. 2021).
Memory requirements. As most other continuous sparsification approaches, note that PILoT dou- bles the number of parameters during training. Yet, according to Ziyin & Wang (023).. the training time of ResNet50 with m C parameterization the memory cost is negligible if the batch size is larger than 50. At inference, we would return to the original representation x and therefore benefit from the improved sparsification.
ImageNet increases roughly by 5% only and
8

---

Published as a conference paper at ICLR 2025
Diagonal Linear Network. We have proven optimality for the analytically tractable setting of diagonal linear networks. Now we illustrate the benefit of our initialization and dynamic explicit regularization. Furthermore, we highlight the impact of good dynamic schedule of the regular- ization strength 04- We use d 40 amount of data points with feature dimension n = 100 and sample 2j ((O,T,)) for j [d]. The ground truth x² is set such that ||>0|| م. 5. Further- more, the network parameters and the trajectories are averaged over initializations. 0.95 confidence regions are indicated by shades. The mean squared enror is used as loss function. We report the distance to the ground truth ||æ; - x" z"Il,, over training time in Figure 2 Two different initializations, i.c., the one of spred and of PILoT, and different regularization schedules are considered. The schedules are de- scribed in Appendix C.I Results for the best ones are shown in the figure and confirm our the- oretical insights. The inability sign flip prevents spred from reaching the ground truth for all considered schedules. Furthermore, with a dynamic regularization, our PILoT initialization out- performs both spred and LASSO, reaching the ground truth. The best-performing schedule for the PILoT initialization is geometrically decaying schedule, also implemented in Algorithm [ In contrast, for the other two methods, a constant regularization works best. This experi- mentally confirms Theorem 2.3 and Remark 2.2 Note that LASSO with gradient descent per- forms as expected. Decaying schedules perform worse than constant ones supporting Remark 2.1
initialized with 26 NO,,, (/)) The step-size is yj 10-4
One-shot sparsification. Firstly, we compare our method PILoT with STR, spred, and LASSO on CIFARIO and CIFAR100 training ResNet-20 or ResNet-18, 18, respectively. Furthermore, in the case of CIFARIO, we also implement the novel initial- 1) without dynamic regu- larization to isolate its benefits. We consider two learning rates {0.1, 0.2) and the weight decay range (le-5,-. - 5, le 2} for CIFARIO and range {le le - 3) for CIFARIO0 and always show the best result. The same range for the regularization strength is explored for LASSO. The other hyper- parameters are reported in the appendix. Secondly, we train ResNet-50 on ImageNet with the setup of STR (Kusupati et al. 2020) and compare directly with their results. Furthermore, we implement both PILoT and spred in this setting.
10
10"
10"
ization (mg w
mw spred init
10"
PILoT inil
x LL1
10 20
250
500
750
1000
Time
Figure 2: A simulation of gradient flow diagonal linear network is given for the dif- ferent regularizations.
Figure presents results for CIFARIO and CIFARI00, PILoT outperforms all other methods and particularly effective in the high-sparsity regime. Our PILoT initialization leads to improvements over spred and STR for medium levels of sparsity. This supports our theoretical insight into the role of initializations and how they influence the implicit bias. In addition, STR is outperformed by spred the high-sparsity regime, confirming the findings of (Ziyin & Wang 2023
90
75
spred
Test Accuracy
70
PILST
80
65
STR
PlLoT init
60
0.80
0.85
0.90
0.95
1.00
0.900
0.925
0.950
0.975
1.000
Spansity (%)
Spunsity (%)
Figure 3: One-shot sparsification. Acc. versus sparsity for CIFARIO (left) and CIFARI00 (right).
In Table 1 we compare PILoT to both STR and spred on ImageNet (Deng et al., 2009). See Ap-
pendix C.2 Table 3 for details on experimental configurations. Our method competes with or out-
Starting from pretrained model with 77% validation accuracy

---

Published as a conference paper at ICLR 2025
Table 1: ResNet-50 ImageNet sparsity (%)
versus accuracy (%) results.
Method
Top-1 Ace Sparsity
ResNet-50
77.01
0
Method ResNet-50
Top-1 Ace Sparsity
STR
70.4
95.03
77.01
spred
69.47
94.50
STR
76.19
79.55
PILoT
72.67
94.00
STR
76.12
81.27
PILoT
71.30
95.00
spre
75.5
80.00
PILoT
71.05
95.60
spred
72.64
79.03
PILoT
70.49
96.00
PILoT
75.62
80.00
STR
67.22
96.53
STR
74.73
87.7
spred
66.12
97.19
STR
74.01
90.55
PILoT
68.49
97.19
spred
71.84
89.26
STR
61.46
98.05
PILOT
74.73
88.00
spred
62.71
98.20
PILoT
74.04
91.00
PILoT
66.49
97.75
PILoT
64.06
98.20
71
Test Accuncy (%)
LRR-PILOT
70
70
WR-PILaT
LRR
WR
69
69
0.2
0.4
0.6
0.8
0.80
0.85
0.90
0.95
Sparsity (%)
Sparsity (%)
Figure 4: Learning Rate Rewinding (LRR) and Weight Rewinding (WR) with PILoT on ImageNet ResNet- 18. The left plot is the complete plot and the right plot is zoomed-in version.
performs all baselines medium and high sparsity levels. In addition, improves over spred at 80% sparsity, even when spred is initialized with 77% pretrained ResNet-50. This highlights the effectiveness of PILoT and confirms the insights from the developed theory.
Iterative Pruning. To demonstrate the versatility of PILoT, also combine it with the state-of- the-art iterative pruning methods Learning Rate Rewinding (LRR) (Maene et al. (021)) and Weight Rewinding (WR) (Frankle al. 2019) ImageNet using ResNet-18. For simplicity,
3 = and no regularization, We see in Figure 4 that the parameterization m @ w futher boosts the performance of iterative methods. Remarkably, WR becomes competitive with LRR. Additional periments on CIFARIO and CIFAR 100 with regularization are in Appendix C.3 further helps reach higher accuracy at high sparsities.
The regularization
DISCUSSION
We have shed light on the inner workings of continuous sparsification. Its basic relaxed formulation utilizes the parameterization m @ w, which induces an implicit bias towards sparsity. In contrast an explicit Li-reuularization
enjoys all the benefits of an implicit regularization that caters first to the loss and not sparsity penalty. Exploiting this insight for neural network sparsification, we have proposed PILoT, which relies on controllable regularization that acts like an implicit regularization in the original neural network parameter space and, remarkably, corresponds to time-dependent Bregman potential. As we have shown, the time-dependent control enables associated mirror flow to enter the so-called rich regime, and thus effectively change the implicit regularization from Lg to L1. This property central to showing convergence our approach for (quasi)-convex loss functions and optimality for underdetermined linear regression. Experiments standard vision benchmarks further corroborate the utility of our theoretical insights, as our proposal PILoT achieves significant improvements state-of-the-ar baselines.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
The authors gratefully acknowledge the Gauss Centre for Supercomputing e. for funding this project by providing computing time the GCS Supercomputer JUWELS at Jülich Supercom- puting Centre (ISC). We also gratefully acknowledge funding from the European Research Coun- cil (ERC) under the Horizon Europe Framework Programme (HORIZON) for proposal number 101116395 SPARSE-ML.
REFERENCES
Aws Albarghouthi. Introduction to neural network verification, 2021.
Felipe Alvarez, Jérôme Bolte, and Olivier Brahic. Hessian riemannian gradient flows in convex pro- gramming. SIAM Journal on Control and Optimization, 43(2)477-501, January 2004. ISSN 1095-7138.
doi: 10. 10.113775006331120244130
URL http: woci.ooroe 10. 11377
07363012902440
Amir Beck and Mare Tehoulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003. ISSN 0167-6377. doi:
URL https: htttpp::/www..ci.e. www.wciincddi.eettttt....
Stephen P. Boyd and Lieven Vandenberghe. Convex optimization. 2009. URL https:///wbb
Rebekka Burkholz. Convolutional and residual networks provably contain lottery tickets. In Inter- national Conference on Machine Learning, 2022a.
Rebekka Burkholz. Most activation functions can win the lottery without excessive depth. In Ad- vances in Neural Information Processing Systems, 2022b.
Rebekka Burkholz, Nilanjana Laha, Rajarshi Mukherjee, and Alkis Gotovos. On the existence of universal lottery tickets. In International Conference on Learning Representations, 2022.
Tianlong Chen, Zhenyu Zhang, Jun Wu, Randy Huang, Sijia Liu, Shiyu Chang, and Zhangyang Wang. Can you win everything with lottery ticket? Transactions on Machine Learn-
ing Research, 2022. ISSN 2835-8856. URL htttps:/openreviiee net forum?? ?
J16MJ9XF zWj
Lénaïc Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. Jacob Abernethy and Shivani Agarwal (cds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning mmlr.
Research, pp. 1338. PMLR, 09-12 Jul 2020. URL press/v125/cht
html
Hung-Hsu Chou, Johannes Maly, and Dominik Stöger. How to induce regularization in linear mod- cls: A guide to reparametrizing gradient flow, 2024.
Arthur da Cunha, Emanuele Natale, and Laurent Viennot. Proving the lottery ticket hypothesis for convolutional neural networks. In International Conference on Learning Representations, 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hier- archical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pp. 248-255, 2009. doi: 10. 10910///.P2222 200.558800..00
Steffen Dereich and Sebastian Kassing. Convergence of stochastic gradient descent schemes for lojasiewicz-llndscapes. 2024.
Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. 2019.
Simon S. Du, Chi Jin, Jason D. Lee, Michael Jordan, Barnabas Poczos, and Aarti Singh. Gradient descent take exponential time to escape saddle points, 2017.
11

---

Published as a conference paper at ICLR 2025
Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pp. 2943-2952
PMLR, 2020.
Mathieu Even, Scott Pesme, Suriya Gunasekar, and Nicolas Flammarion. (s)gd over diagonal linear networks: Implicit regularisation, large stepsizes and edge of stability. ArXiv, abs/2302.0893 08982, 2023. URLhtttss: /tctps://api... htt.:tpsrsaapp...eanticcccccciie www.nticscoooo.............. wwwphoolrrrrrrr.eooooooooooooeee wwt. wwwpoo/rggsD::/2/.0 268042033
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera- Moham- madamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszez, David Silver, Demis Hassabis, and Pushmeet Kohli. Discovering faster matrix multi- plication algorithms with reinforcement learning. Nature, 61077930):47-53, 2022.
Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen. Convergence rates for the stochastic gra- dient descent method for non-convex objective functions, 2019.
Damien Ferbach, Christos Tsirigotis, Gauthier Gidel, and Bose Avishek. A general framework for proving the equivariant strong lottery ticket hypothesis, 2022.
Jonas Fischer and Rebekka Burkholz. Plant 'n' seek: Can you find the winning ticket?, 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv: Learning, 2018.
http:/ppp...mmmttcccccccchooooee org/
Cor3pss1D:53388625
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 M. Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. CoRR, abs/1912.05671, 2019. URL http://
arxiv.org/
05671
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Pruning neural net- works at initialization: Why are we missing the mark? In International Conference on Learning Representations, 2021.
Advait Gadhikar and Rebekka Burkholz. Masks, signs, and learning rate rewinding. In Twelfth International Conference on Learning Representations, 2024. httpttttppp//peeeeeeeeeeeeeeeeee
Advait Harshal Gadhikar, Sohom Mukherjee, and Rebekka Burkholz. Why random pruning is all need to start sparse. In International Conference on Machine Learning, 2023.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization in matrix factorization, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry, 2020.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Intekhab Hossain, Jonas Fischer, Rebekka Burkholz, and John Quackenbush. Not all tickets are equal and we know Guiding pruning with domain-specific knowledge, 2024.
Tian Jin, Michael Carbin, Daniel M. Roy, Jonathan Frankle, and Gintare Karolina Dziugaite. Pruning's effect generalization through the lens of training and regularization. In Al- ice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neu- ral Information Processing Systems, 2022. UR.httss: /ttpss//ppppevieeeee net forummrmmmmmm ? DrcLKV9sK0p
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvumakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with AlphaFold. Nature, 596(7873)5583-555))) 2021.
12

---

Published as a conference paper at ICLR 2025
Lynn H Kaack, Priya L Donti, Emma Strubell, George Kamiya, Felix Creutzig, and David Rolnick. Aligning artificial intelligence with climate change mitigation. Nature Climate Change, 12(6): 518-527, 2022.
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the polyak-tojasiewicz condition. In Paolo Frasconi, Niels Landwehr, Giuseppe Manco, and Jilles Vreeken (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 19 Cham, 2016. Springer International Publishing. ISBN 978-3-319- 46128-1.
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 on Machine Learning, July 2020.
Andrey Kuzmin, Markus Nagel, Saurabh Pitre, Sandeep Pendyam, Tijmen Blankevoort, and Max Welling. Taxonomy and evaluation of structured compression of convolutional neural networks, 2019.
Denis Kuznedelev, Eldar Kurtic, Eugenia Iofinova, Elias Frantar, Alexandra Peste, and Dan Alistarh. Accurate neural network pruning requires rethinking sparse optimization, 2023.
Mike Lasby, Anna Golubeva, Utku Evci, Mihai Nica, and Yani loannou. Dynamic sparse training with structured sparsity. arXiv preprint arXi::2305.02299 2023.
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.
Jiangyuan Li, Thanh V. Nguyen, Chinmay Hegde, and Raymond K. W. Wong. Implicit sparse regularization: The impact of depth and early stopping, 2021. URL htttp:://arxiv.rrt
abss/108..0 05574
Jiangyuan Li, Thanh V. Nguyen, Chinmay Hegde, and Raymond K. W. Wong. Implicit regulariza- tion for group sparsity, 2023. /RtLts::://xxxiivcooo httgg/abs/233111 2e0p//231.11400 12540
Zhiyuan Li, Tianhao Wang. Jason D. Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent. ArXiv, abs/2207.04036 2022. URL : https: www.nt ott.arriiiccccc........ooooroeoa
Bohan Liu, Zijie Zhang, Peixiong He, Zhensen Wang, Yang Xiao, Ruimeng Ye, Yang Zhou, Wei- Shinn Ku, and Bo Hui. A survey of lottery ticket hypothesis, 2024.
Shiwei Liu and Zhangyang Wang. Ten lessons we have learned in the new "sparseland"; A short handbook for sparse neural network researchers, 2023.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness random pruning: Return the most naive baseline for sparse training. In International Conference on Learning Representations, 2021.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through 4n regularization, 2018.
Alexandra Sasha Luccioni, Yacine Jernite, and Emma Strubell. Power hungry processing: Watts driving the cost of ai deployment? arXiv preprint arXiv:2311.1686. 2023.
Jaron Maene, Mingxiao Li, and FranciFe Moens. Towards understanding iterative magnitude pruning: Why lottery tickets win, 2021.
Eran Malach, Gilad Yehudai, Shai Shalev-Schwart,, and Ohad Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference Machine Learning, 2020.
Nina Narodytska, Hongee Zhang, Aarti Gupta, and Toby Walsh. In search for sat-friendly binarized neural network architecture. In International Conference on Learning Representations, 2020. DRLhttps. httptttss//pppneeviiie wtt.ee/rweeeeeeeeeooo/oooooooaae
13

---

Published as a conference paper at ICLR 2025
A.S. Nemirovski and D.B. Yudin. Problem Complexity and Method Efficiency in Optimization. A Wiley-Interscienee publication. Wiley, 1983. ISBN 9780471103455. URL bttps://books.
Laurent Orseau, Marcus Hutter, and Omar Rivasplata. Logarithmic pruning is all you need. Ad- vances in Neural Information Processing Systems, 33, 2020.
Shreyas Malakarjun Patil and Constantine Dovrolis. Phew: Constructing sparse networks that learn fast and generalize well without training data. In International Conference Machine Learning, pp. 1432-8442. PMLR, 2021.
Mansheej Paul, Feng Chen, Brett W. Larsen, Jonathan Frankle, Surya Ganguli, and Gintare Karolina Dziugaite. Unmasking the lottery ticket hypothesis: What's encoded in winning ticket's mask? In The Eleventh International Conference on Learning Representations, 2023. URL https:
//openzeview.co net. www.//rtt//ouee.e wwtpddddxxSsmmmeeemm
Ankit Pensia, Shashank Rajput, Alliot Nagle, Harit Vishwakarma, and Dimitris Papailiopoulos. Op- timal lottery tickets via subset sum: Logarithmic over-paramntteriaatonnn is sufficient. In Advances in Neural Information Processing Systems, volume 33, pp. 2599-2610, 2020.
Scott Pesme, Loucas Pillaud-Vivien, and Nicolas Flammarion. Implicit bias of sgd for diagonal linear networks: a provable benefit of stochasticity, 2021.
Alexandra Peste, Eugenia lofinova, Adrian Vladu, and Dan Alistarh. Acide: Alternatnng com- pressed/decompressedd training of deep neural networks, 2021.
Hoang Pham, Shiwei Liu, Lichuan Xiang, Dung D Le, Hongkai Wen, Long Tran-Thanh, et al. Towards data-agnostic pruning at initialization: What makes a good sparse mask? In Thirty- seventh Conference on Neural Information Processing Systems, 2023.
Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Linear convergence of gen- eralized mirror descent with time-dependent mirrors, 2021.
Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text- conditional image generation with clip latents. arXiv preprint arXiv:2204.066 06125, 2022.
Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in neural network pruning. In International Conference on Learning Representations, 2020.
Tyrrel R Rockafellar and Werner Fenchel. Convex Analysis.
1970. URL https://apk
semant ccscholase ar. wawr.org/Cee /orrg/uruuuuaaai TD: 1981 (0397)9
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsification, 2021.
Jonathan Schwarz, Siddhant M. Jayakumar, Razvan Pascanu, Peter E. Latham, and Yee Whye Tch. Powerpropagation: A sparsity inducing weight reparameterisattion, 2021.
Heejune Sheen, Siyu Chen, Tianhao Wang. and Harrison H. Zhou. Implicit regularization of gradient flow on one-layer softmax attention, 2024.
Kartik Sreenivasan, Jy-yong Sohn, Liu Yang, Matthew Grinde, Alliot Nagle, Hongyi Wang, Eric Xing, Kangwook Lee, and Dimitris Papailiopoulos. Rare gems: Finding lottery tickets at initial- ization. Advances in Neural Information Processing Systems, 35:14529-145555 2022.
Natalie Stephenson, Emily Shane, Jessica Chase, Jason Rowland, David Ries, Nicola Justice, Jie Zhang, Leong Chan, and Renzhi Cao. Survey of machine learning techniques in drug discovery. Current drug metabolism, 20(3):185-199 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.
Tomas Vaškevičius. Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery, 2019. URL hRL.httss:/ petttps://ariiv wttp://wwwwww////.////oo 05122
14

---

Published as a conference paper at ICLR 2025
Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations, 2020.
Kun Wang. Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang, and Yang Wang. Searching lottery tickets in graph neural networks: A dual perspective. In The Eleventh Interna- lional Conference Learning Representations, 2023. URL https: pttaps://cpeee //open repenrevieen ew net/
Eorum?id-Dvs a
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Advances in Neural Information Processing Systems, volume 29, 2016.
Stephan Wojtowytsch. Stochastic gradient descent with noise of machine learning type. part Discrete time analysis, 2021.
Blake Woodworth, Suriya Gunasekar, Jason D. Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models, 2020.
Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga, Jinshi Huang, Charles Bai, al. Sustainable ai: Environmental impli- cations, challenges and opportunities. Proceedings of Machine Learming and 4ystems,,:795-881 2022.
Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks, In International Conference on Learning Representationss 2020.
Peng Zhao, Yun Yang, and Qiao Chu He. High-dimensional linear regression via implicit regular- ization. Biometrika, 109(4)1033--146, February 2022. ISSN 1464-3510. doi: 10.1093/biomet/
asac010. http::ppp/bx......g//00....0.00. wtt.:.....r/.....1///ii......ee. 1tt.://///omee/aaaa.....
Xiao Zhou, Weizhong Zhang. Zonghao Chen, Shizhe Diao, and Tong Zhang. Efficient neural net-
work training via forward and backward propagation sparsification. Advances in Neural Informa- tion Processing Systems, 34:15216-15229 2021a.
Xiao Zhou, Weizhong Zhang. Hang Xu, and Tong Zhang. Effective sparsification of neural networks with global sparsity constraint. In Proceedings of the IEFE/CVE Conference on Computer Vision and Pattern Recognition, pp. 3599-3608, 2021b.
Liu Ziyin. Symmetry induces structure and constraint of learning. 2023. URL https:: semant semanticschoaar wwwp:lapurrg/ooouuuuupppa 263310669
Liu Ziyin and Zihao Wang. spred: Solving 4 penalty with sgd, 2023. URL https:
org/ org/abs/ abs/ 2210. 01212
A MIRROR FLOW FRAMEWORK
In this section we present some known results from the mirror flow framework for completeness. We derive the Bregman potential associated with m @ w in Theorem A.I Next, we will also show the convergence of the loss and provide optimality guarantees in Theorem A.2 In addition, we extend
Theorem A.2 with Theorem A.3 Finally, we give the optimality result for diagonal linear networks in Theorem
Theorem A. Let the initialization of m and wo satisfy mo,; > |wo.il for all E [n]. Then the corresponding mirror function is:
R(x) z,arcsinh
I₁ 200,
V 12 + 4u8 2,l0g
Uooi
(8)
Vo,4
where Vo,
m0,140000 and Vo,4 /2
mo.1 -00. /2
Furthermore, R is Bregman function.
15

---

characterizes the behavior in the limit for this case. For the Published as a conference paper at ICLR 2025
Proof. The result follows directly from applying Theorem 4.16 in (Li al. 2022
Theorem A.I limplies the following: a) The global minima of R is at the initialization 2o = mg @ w-g-
b) The Lipschitz coeficient of R depends on the initalization. The Lipschitz coeficient LR of (8) is
Ln= = min, 2uo.;"o.,' determining the smoothness of the potential. Following these two observations we make the following remark about Theorem A.1
Remark A.1 Note that when the initialization is zero, i.e., wio 0, va with a 2 then ( the hyperbolic entropy. The hyperbolic entropy is
I arcciin (=) Va +
Theorem of (Woodworth al. 2020
hyperbolic entropy in case a + 0 and
D0,
R(x) ~ log 1
This means an L1 bias is induced when is small. Nevertheless, we need an exponentially small compared to x to get there as shown in Woodworth et al. [2020]. which can lead to numerical prob- lems. Furthermore, mi = wi a saddle point which can slow down training (exponentially) Du et al. 2017). Additionally, the asymptotic result only holds for initializing at zero. Note Ln this case.
Remark A. shows the potential of using the implicit bias to induce sparsity. To actualize this, we need to solve the two challenges posed in the remark. Both are remedied in Section 2
In addition this promising formulation of implicitly minimizing an L norm with the use of the mirror framework, we can get convergence results. These results make it clear why implicit regularization preferable over explicit regularization. The convergence result from (Li et al. 2022 is stated for setting. Furthermore, the theorem is extended for a specific class of Bregman functions.
Theorem A.2 (Theorem 4. 4.14 (Li et al. 2022 Assume that f is quasi-conver, V f is locally Lips- chitz and (f E ]²] is non-empty. Then as t + co, It converges to some critical point x², Moreover, f is convex Dt converges to minimizer of f.
In Theorem A.2 it is shown that with implicit regularization an optimal solution to the original optimization problem can be reached. In contrast, explicit regularization makes this not possible, by definition. Because the optimization problem has fundamentally changed. Showing the benefit of implicit over explicit.
For the extension, the convexity constraint is replaced by the Soyyak-Eojasiewicz (PL) inequality in the theorem. The PL-inequality is a more realistic constraint in a machine learning context as loss functions not locally convex but can satisfy the PL inequality locally (Wojtowytsch) 2021 Dereich & Kassing, 2024). The PL-inequality for a continuously differentiable function f
[)) (f(x)) ((f()))((="))
Vx R
for some > and global minima x" of f. This allows us to state the modified theorem.
Theorem A.3 Consider the same setting as Theorem A.2
Assume R satisfies for all x R".
(V²R(x)) 2 2 2||2|| P
Yz
ER.
(10)
Furthermore, assume I satisfies the Pl-inequality Furthermore, the loss converges linearly with rate x..
Then In converges minimizer of f.
Proof.
The evolution of f(x,)
f(x*) is described by df(xz)
-Vf(zz) (V²R(z)) df(z))dt. From 10 and (9) the evolution is bounded by
df(xz) S - -o)((())) f(xx)) dt.
16

---

Published as a conference paper at ICLR 2025
Applying Gronwall's Lemma concludes the proof. D
Note that Theorem A.3 holds in the same (general) setting as Theorem A.2 PL-inequality together with quasi-convexity does not imply convexity. Theorem A.3 holds for our setting. In this case, it follows from a direct computation that
Also, note that the
(V R(x)) diag
/22
4u V0,1
4u
0.n
This implies that a = min; V0, in Theorem A.3 which again highlights the importance of the initialization.
Finally, the case of under-determined linear regression, we can derive optimality conditions in the form of KKT conditions of Rt Consider a data set (zj, M)) with E R" and E IR. Let Z (Z1,-... zd) and Y (y1,..-Wa), For the regression to be called underdetermined d.
Theorem A.4 (Theorem 4. (Li el al. 2022)) In case of under-determmnedd regression consider the loss function f(x) =fZz Y). Assume f satisfies the conditions of Theorem A.2 Then Zt converges to x² such that
x² argmin 72= R(z)
Note that Theorem 4.17 of (Li et al. 2022) only uses guasi-convexity of the loss. Theorem A.4 guarantees that the optimization problem solved while implicitly minimizing the potential R. Thus choosing the sparsest model out of the models that predict the data perfectly. This highlights another benefit of implicit regularization over explicit regularization.
In this section, we have shown the viability of using the implicit bias framework to induce an implicit regularization. Furthermore, we have given two known benefits using the implicit bias framework over explicit regularization. The benefits are convergence to the optimal solution of the original problem and optimality the case of underdetermined regression. To add to this, we have extended the convergence theorem using the PL-inequality in i Moreover, of the initialization of mg and Wp with the influence on the smoothness of the Bregman potential and convergence of the loss. The initialization insight in the main text is used improve upon spred Ziyin 2023) as their initialization has scaling 2ugth = 0, it follows already from the mirror flow framework that 2uoto 1 is better initialization. Furthermore, we also do initialize zero though, and scaling needs to be exponentially small to get a good approximation of the L1 norm potentially making hard escape the saddle point. Therefore, the explicit regularization analyzed in Section is necessary to exploit the implicit bias framework.
again highlight the importance
B PROOF MAIN RESULT
We show the main result here. The proof consists of four parts
Ra, satisfies mirror flow (Lemmas B.I and B.2
Boundedness of the iterates and convergence to critical point (Lemma
B.3
Convergence of the loss (Theorem B.I
Optimality in case of underdetermiind linear regression (Theorem B.2
Consider the following gradient flow
dm,; V (my ( wr) O we dt
(11)
dw, = - Vf (m, @ w,) O m, wa
For the flow II] to be well-posed V f needs to be locally Lipschitz continuous. This a sufficient condition given that a is "nice", which will be made more rigorous later. The evolution of æ, my @ Wa is derived in LemmalB. [.
Lemma B.1 The evolution of my O W/ with 77 is described by
x, = u ② exp (22 /' V (x,) ds - a,ds of o exp
Vs (1.)) do 1f( agds)
17

---

Published as a conference paper at ICLR 2025
where uo
+ /2
and 0o
v2
Proof. This follows from deriving the flow of my and wa and then combining the two. The evolution of both are given by
m4
m0 cosh (- S0 V (Irs) ds
+ wo sinh
Jo V (ars) (ars)) ds
exp
(-2 So a,dss
wo O cosh
So f (Io) ds + mo
o sinh
So V (zx) ds
exp
(-2 a,ds
For of notation set L, f v (v:a) ds and
A, So a,ds. Combining gives
= my @ wi
o cosh (-Le) @ sinh (-L,) exp expppppppppe (-4Ac) + wy mo @ cosh (-Lx)² + cosh (-L,)² exp (-4A,)
-m² + w
(mg + w)) sinh (-2hx) exp(-4A.)
+ wr 2 mi @ (cosh -T.)) exp (-4At;)
un exp 2L, 44,
un exp (2L, 4A,)
where the second equality follows from hyperbolic identities. m
follows from Lemma B.1 and the local Lipschitz condition on Vf and So a, < for all i 2 O, that the flow is well-posed. We now define the (coprecced)-hyperbolli entropy function. The corrected hyperbolic entropy given by
(x) = E r,arcsinh
Vaz 2t + a²
too 1,,og
co,
where the last term is the correction. The correction stems from not initializing at zero
Lemma B.2 Let wwal I moi for all i E [n]], then Ro, (xx) with oe = 2uo O unexp (-2 a,ds)
satisfies
dV Rui (x:) = v f(x:)dt
To = ma O wD-
(12)
Proof. This follows from Lemma B.I
xxexp (15 agds) = ugexp
- nsexp 2 V((rs)ds) +
-2
V ((xx)dds)
J
S Vf(zz)ds.
arcsinh(
log 2o
a1
This equivalence follows from setting exp - 2 V f )ds and solving the resulting
quadratic equation. Notice that the left hand side in [12 is V Ra, (x²).
Lemma B.3 Let ff be a quasi-convex function and a, 2 0 for all t 2 0. Furthermore, assume the integral So a,ds < cc. Then the iterates are bounded and converge to critical point.
Consider the time-dependent Bregman divergence
Da, (x" ,x)) Ray (x*) Ru, (IxE) V R (x* x2.) The divergence is bounded by:
Das (x" (x)) S Raco (a*) - Ras (xx) V R2 (x" xxa) =: Wt,
this follows from the fact that the map - R, is decreasing. We make the following two observa- tions:
d
x la| +
do,
- Ra(x) = 2 vo² 2
and
< 0
Vt 2 0.
(13)
da
dt
18

---

Published as a conference paper at ICLR 2025
This allows to bound the evolution
d W. = (-Ro, (It) Ve (x* - -11)
d
dt
dt
d Ro, (xx)
dl at - d di (Voltt)) (x* x()
= da
(I)( (x:)
00
where the observations in 13 are used in the first inequality.
From Theorem 4.16 in (Li al. 2022 follows that for all a 0, Rg is Bregman potential. Implying that for all a > 0 the level set for 7 E IR,
for R" Da(=",z) s^}
bounded. Combining this with the fact that the evolution is bounded, implies the iterates are bounded.
In the next part, it is shown that Fe converges to a critical point. We first show that the loss becomes eventually non-increasing. There is I such that for all T the loss f is non-increasing.
df((s) =
V (xx)) I diag
(V o2
V=2+ +
Vf(z)) + 2a, ff(x)) dt
Vat + of Vf(x,) + 20, +2,,C
< (x,)) diag
where it is used that the iterates are bounded and V is locally Lipschitz. As l + we have that ag + and a, + 0x > 0 by assumption. Hence there exists a such that for all 2 T we have
df(x)) < 0.
Note if this is not the case then there T such that V((T)) implying convergence (to critical point).
Now let v accumulation point of the bounded flow xy. We this show convergence to a critical point. We have that for all x E R",
T++ (TV
1 (Ray( Rar+, (IT+:)) O,
vf(zx) lim
== lim 1000
where the first equality follows from that the loss is non-increasing and the second one from the time-dependent mirror flow description. Finally, because x, converges to accumulation point also have lim,- Ro, (xx) = Ra_ (x) by continuity, giving the last equality.
We use that the accumulation point is critical point and set Ino in W, such that W2 - 0. This implies Da, (Foo: xx2) + by the upperbound. follows from the fact that the iterates are bounded that Ru, is p-strongly convex this bounded convex set where the iterates stay. This gives
|| - xelle. L. < H Da, (Ioo, xz) + +,
2
showing converges to critical point. 0
Lemma B.3 gives a condition such that the iterates are bounded and converge to a critical point. remains be shown that the loss converges. This is done in Theorem B.1
Theorem B.1 Consider the same setting as Lemma B.3 if is convex or satisfies the Pl-inequality we have convergence an interpolator such that minimizer of f. Furthermore, in the PL-inequality case, the loss converges linearly.
Proof. Assume is convex, notice first that there T such that for all t 2 T the loss non- increasing. Combining this with bound on the deneneepnd Bregman potential gives conver- gence of the loss. The time-dependent Bregman divergence is again defined by
Da, (x" xx) Ra, (x²) Ra, (2ra) Va RT, (x" xx. 0.
19

---

Published as a conference paper at ICLR 2025
The divergence is bounded by:
Da. (x"",aaaa) We.
The evolution of the bound is
d
d
W.
(-Ro, (Ie) RoR (x" -x+))
dt
dt
d da Ro (De) ai- d
(VoRsa) (x* xz)
< VaJ(z)) (x"-xx)
s - (xt):
where again the observations in (13 are used in the first inequality. Therefore the loss converges:
1 fT
1 T++
f(xT+e) - f(x²) -
f(x.) f(x" )ds
Wr
Wr+t
< 1
WT t
where the first inequality follows from convexity of the loss and the third inequality from the fact that W, 2 Da, (x* , xx) O. So the loss converges. We already know from Lemma B.3 that the iterates converge, concluding the convex case.
In case when satisfies the PI-inequality, we proceed in the way as Theorem A.3 The evolution of f is given by
(f(x)) ((x))) diag (V x² af V vs(x)) + 20, ((xx) Txa de ddiag S (-A f(x")) a,C||=" (|z) dt
where C is constant depending on the smoothness of f and Ace 2 min, uo exp (-2 a,ds). Then it follows from Gronwall's Lemma that
f(x,) - f(x²{((==))))))))))) s (f(20) f(x*)) exp (-Acstt+ J'' a.C(ll""le,ds)
follows from the fact that J/¹ a,ds < co for all 2 0 that the loss convergence. Convergence of the iterates now follows in a similar way as the convex case. D
We now show optimality in the case of underdetermined linear regression Consider a data set (2y, Bj ) with 2j E R and yj E IR. Let Z = (21.... 2d) and Y (y1....ya) For the re- gression to be called underdetermined n d.
Theorem B.2 In case of under- regression consider the loss function f(x) f(Zx- Y). Assume f satisfies the conditions with at least one of the convergence criteria of Theorem B. Then converges to x" such that
Tr -argmin Z==y Ra.. (x:
(14)
Proof. Convergence follows from Theorem B. It remains to be shown that the optimality condi- tions of (14) are satisfied. The gradient flow of Rs, satisfies
RR, (2+) = ZT L/ Vi(x.)ds span
This quantity is well defined for all t 0 because v is locally Lipschitz (because has to be locally Lipschitz). Therefore taking the - 2o yields the KKT conditions the optimization problem in (14)
20

---

Published as a conference paper at ICLR 2025
B.1 DISCUSSION OF THE PROOF
Most of the proof follows the same arguments as in (Alvarez et al. 2004 Li et al. 2022 Pesme al. (021). The notable differences are showing that the loss becomes decreasing over time and the observations made in 13
C DETAILS EXPERIMENTS
In this section, we provide the details of the experiments. In addition, there are additional figures given.
Compute
The codebase for the experiments is written in PyTorch and torchvision and their rel- evant primitives for model construction and data-related operations. The experiments in the paper trained NVIDIA A6000. In addition, the diagonal linear network is trained on CPU 13th Gen INTEL(R) Core(TM) 19- 13900H.
C.I DIAGONAL LINEAR NETWORK
For each setting, different regularization schemes are tried. In total, 7 options are tried. of the schedules are constant i.c. the regularization stays the same during training. The remaining 3 are decaying schedules. These schedules we name harmonic, quadratic, and geometric. The schedules are described by the following recurrent relations:
1
hg
and
1
where we have set p = 0.95. These schedules lead to a total strength of regularization applied. We denote A == 1 ds the total strength of the regularization. So in practice, the weighted sum of the regularization strength.
In Figure 5 we present the trajectories of all the schedules for the considered settings. We observe that regularization performs the best with the decaying schedules predicted by the theory. The other methods need constant regularization to perform well as already mentioned in Remark Note that, PILoT also can perform well with constant regularization (see Figure 5
2.1
10
10
1l
10
X
X
10
10"
500
1000
500
1000
500
1000
Time
Constant A 0.1
Constant 10
Harmonic A 14.4
Geometeric A
20
Constant
Constant = 100
Quadratic
Figure 5: All runs for the diagonal linear network. From left to right m @ uo with PILoT initalization, m O w with spred initialization, and x with L1 regularization
C.2 ONE-SHOT
In this section we give the additional details for the one-shot experiments. In Table 2 the hyperpa- rameters for the CIFAR 10 and 100 experiments given. To determine which configuration is best
21

---

Published as a conference paper at ICLR 2025
for which sparsity level compute the validation accuracy at multiple levels and choose the level just before the accuracy drops 1% or in the high-sparsity regime 2%. Moreover, we use s 200 for STR.
For the ImageNet experiment we use the setup of (Kusupati et al. 2020). For PILoT and spred we in addition use Le regularization to compensate for the weight decay i.e. we add a term (m O w)² with strength 0.00003051 7 which is based the weight decay strength in (Kusupati et al. 2020) for the baseline. Furthermore, weight decay is turned off for the other parameters. In Table we present the configurations that correspond the values in Table ! Note for all PILoT
configs = 1.01 is used.
Table One-shot experiment
Parameter
Setting
Comments
Optimizer
SGD
Momentum
0.9
Batch size
256
Activation function
ReLu
Weight decay? 2
10-4
Base learning rate
(0.1,0.2)
Epochs
150
Warmup period
0
Initialization
Kaiming normal
Scaling
1
Only for
1.01
K
8000
CIFAR 10
Learning rate schedule
cosine warmup
CIFAR 100
Learning rate schedule
step warmup
Table 3: ResNet-50 on ImageNet configurations for each sparsity (%).
Method asnit
K
sparsity
spred
2e 5
94.50
Method
Osnit
K
sparsity
PILoT
2e 5 60000
94.00
spred"
2e
80.00
PILoT
3e
60000
95.00
spred
3e 6
79.03
PILoT
3e 5 60000
95.60
PILoT
7e
60000
80.00
PILoT
3e 5 60000
96.00
spred
5e
89.26
spred
3e 5
97.19
PILoT
le 5 60000
88.00
PILoT
4e 40000
97.19
PILoT
1.4e 5 60000
91.00
spred
5e 5
98.20
PILoT
5e 5 20000
97.75
PILoT 7e 20000
98.20
Label smoothing Altough PILoT is competitive in the 80% 90% sparsity range it is not SOTA. Nevertheless. if we turn of label smoothing in the experiment PILoT outperforms STR in this range as well. The only change for STR is turning of labelsmoothing. For PlLoT we use two different configurations. We use L2 regularization i.e. ||m @ will,, regularization set to 5 10-5 instead of the value from STR experiment. We use
600000 and 1.01. Furthermore, the strength of the PILoT regularization is initialized at 10-5 2 10 10-5) and weight decay is used on the rest of the parameters. The results are given in Table C.2
2 "Applied to the other parameters Starting from pretrained model with 77% validation accuracy
22

---

Published as a conference paper at ICLR 2025
Table Extra experiment ResNet-50 on ImageNet sparsity (%) smoothing.
versus accuracy (%) without label
Method
Top-1 Ace Sparsity
ResNet-50
75.80
0
STR
73.03
79.03
PILoT
74.72
79.03
STR
71.6
89.26
PILoT
73.21
91.41
C.3 ITTERATIVE PRUNING
Table55th details of the ImageNet the experiment are given. Note the base learning rate 0.1 is for the baseline and 0.2 is used for our parameterization combined with scaling 1. In addition, the Le regularization denotes the reparameterization of the original weight decay, Thus for PILoT, this case, that instead. Moreover, all runs have been done for 3 different seeds. Furthermore, provide additional experiments on CIFAR 10 and 100 with ResNet-20 and ResNet- 18 respectively The details given in Table
in Figure 6
Table 5: WR and LRR experiment ImageNet
Parameter
Setting
Comments
Optimizer
SGD
Momentum
0.9
Batch size
512
Activation function
ReLu
Weight decay
{0, (,10044
Learning rate schedule
step warmup
Base learning rate
(0.1,0.2
Cycles
25
Pruning rate
0.8
Epochs per cycle
90
Warmup period Initialization
10
Kaiming normal
Le regularization
5 10
Only for m 0 w
PILOT regularization
{0}
Only for m
Scaling
1
Only for m O w
1
Only for
Only for m
④ w
76
76
Test Accuracy
LRR+PILOT
91
91
LKR
%
0.5
1.0
00.s
0.9
1.0
00.0
1.0
0.90
0.95
1.00
Sparsity
Figure 6: Learning Rate Rewinding (LRR) and Weight Rewinding (WR) with PILoT shows im- provement over the baseline itterative pruning methods for CIFAR 10 and 100.
D REMARK NEURONWISE PRUNING
In the main text. we have used mirror flow describe the implicit bias of parameterwise pruning. In this section, we show that neuronwise pruning can not be analyzed the same way. We first define neuronwise pruning. Next, paraphrase the necessary condition such that the implicit bias can be
23

---

Published as a conference paper at ICLR 2025
Table 6: WR and LRR experiment on CIFAR 10 and 100
Parameter
Setting
Comments
Optimizer
SGID
Momentum
0.9
Batch size
256
Activation function
ReLu
Weight decay
10-4
Learning rate schedule
step warmup
Base learning rate
(0.1,0.2)
Cycles
25
Pruning rate
0.8
Epochs per cycle
150
Warmup period Initialization
50
Kaiming normal
Le regularization
Only for m O w
PILOT regularization
(10-1)
Only for
Scaling
Only for m @ w
1
Only for m w
K
Only for m O w
described by a mirror flow from (Li et al. 2022). Finally, we show neuronwise pruning violates this condition pointing out limitation of the framework.
Consider the parameterization for a function with neurons, 9 RP x R" x... x R"v,
gmm, Wi,..., up) = (m1 "nn. Wpp
where my E R is the mask and E R are the neurons.
We state the necessary condition for parameterization induce mirror flow.
Theorem D.1 (Theorem 4.10 (Li et al. 2022)) The Lie bracket span of (Vig)= is in the kernel of Jacobian dg.
Now, we use this theorem to show that neuronwise pruning does not induce a mirror flow.
Lemma D.1 Neuronwise pruning violates Theorem D.1
Proof. We show that for 1 the condition is already violated. This implies that in the general case, the condition is also violated as the neurons themselves are commuting with each other as they parameterized separate.
To see this we can explicitly check the commuting condition for the following parameterization g: R x R
R R
g(m, w) mw
Then the gradients (Jacobians) and Hessian's are given by:
Wi
I
I
mIma
Lim
Vgz
and
Hg:
for i = 1,
mI m=
T
Computing H V
0
1
Hg. Vg, = Wj
11
24

---

Published as a conference paper at ICLR 2025
compute the Lie brackets which span subspace of the Lie Algebra (Ig) The subspace spanned by
===1
I==1
span
Wj
Mt
for i,j E [n]
C (L))
Iizn/
Clearly, this span in K (er(Og) as can be shown by a direct computation:
4==1
11==1
(0g)
wy
W
(T==1mm1 - 1--1==11000 11-1, Mi= - T==1mmo))
jinn/
For the span to be in the kernel need either that all w; 0 for all [n]] or 0. In both cases this implies that g(m, w) E {0}. This implies that a mirror flow is only well-defined the parameterization is zero. Hence, couron-wise continuous sparsification does induce mirror
flow. D
25


Reviews:
[{"review_id": "nXxUV3349j", "reviewer": "Reviewer_cfhK", "summary": "\"Spred\" is a recent algorithm that implicitly achieves sparse solutions through reparameterization. To understand why \"Spred\" outperforms LASSO, the authors analyzed its training dynamics using the mirror flow framework. They demonstrated that when the regularization term in \"Spred\" is time-dependent, it can smoothly transition between implicit L2 and L1 regularization. Building on this insight, they introduced PILoT, an approach that dynamically adjusts the regularization strength. Finally, the authors validated the effectiveness of PILoT through experiments on CIFAR-10/100 and ImageNet datasets.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "The theoretical analysis of the reparametrization with time-varying weight decay is solid and novel. It is valuable to first develop a deep theoretical understanding, which then serves as a basis for algorithmic improvements.", "weaknesses": "**Major:**\n- **Inaccurate and unclear writing**: The presentation in the paper could benefit from a substantial revision to improve clarity, particularly in the latter half of Section 1 and Sections 2, 3, and 5. Additionally, some inaccuracies need to be addressed. For example, the abstract states that \"A key factor in their (continuous sparsification) success is the implicit L1 regularization induced by jointly learning both mask and weight variables.\" However, the discussion from Lines 54-65 suggests that this implicit L1 regularization is exclusive to the \"Spred\" algorithm, which utilizes reparameterization. The paper is currently difficult to follow, which is my primary concern.\n- **Computation and memory costs of reparameterization**: The reparameterization approach proposed in the algorithm effectively doubles the number of parameters, resulting in increased computational and memory demands. However, this is not discussed in the paper.\n\n**Minor:**\n- **Figure 4's legend is confusing**: It would be clearer to rename \"mw LRR\" to \"LRR with reparameterization\" and \"x LRR\" to \"LRR.\"\n- **Unclear variables in Algorithm 1**: The variables \"u_0\" and \"v_0\" introduced in Algorithm 1 are not referred to in subsequent sections, leading to confusion about their purpose.", "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": "bYuFrFiMiG", "reviewer": "Reviewer_L22t", "summary": "This paper studies the mirror flow of the time-dependent $L_2$-regularized optimization problem which is parametrized by masked weights $x=m\\odot w$. The authors derive the corresponding Bregman potential for the mirror flow and prove a convergence result for quasi-convex loss functions. Inspired by the forms of the derived Bregman potential and the gradient flow, the authors propose PILoT, which takes (i) a strategy to control the strength of $L_2$-regularization dynamically and (ii) a initialization for $m$ and $w$ that enables sign flipping. Evaluations show that PILoT outperforms baselines on CIFAR 10 and CIFAR 100.", "questions": "1. I found table 1 confusing. Why do all methods have duplicates in the table?\n2. At line 227, why does $R$ attain its global minimum at $x_0$ when $R$ is $L_1$ norm?\n3. At line 218, is there any formal result stating that explicit regularization would lead to a trade-off? I can see that implicit bias of the reparametrized optimization is helping achieve both sparsification and low loss, but does that imply an explicit regularization forces a trade-off?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "* The theoretical result seems sound though I didn't check the proofs. \n* The Bregman potential offers insight on $L_1$ regularization effect. \n* The gradient flow also offers insights on why spred outperforms Lasso from the perspective of convergence rate. \n* I appreciate that the authors also develop an algorithm inspired by the theory.", "weaknesses": "The writing is poor. Some notations are never explained, e.g., $m^2$ (though I can see that's the square of $L_2$ norm, but it is not the standard notation). The experiments are also a bit hard to read. Please see questions.", "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": "YDvaDQtb7s", "reviewer": "Reviewer_jfBc", "summary": "In this paper, the authors focus on the problem of finding sparse neural networks. They propose a new method called PILoT based on theoretical analysis on simple diagonal linear networks. They use the insights gained from theoretical analysis to improve previous method called spred to introduce dynamic regularization strength and initialization scheme. Experiments are provided to show the improvement of the proposed method.", "questions": "-\tIn line 228, I was wondering why ‘’the potential $R$ attains its global minimum at the initialization $x_0$... In consequence, we would not promote actual sparsity’’. I’m confused about this. As many paper that authors cited, when initialization scale goes to 0, the final implicit regularization is $\\ell_1$ norm that promotes the sparsity.\n-\tIn Theorem 2.2, what is $\\alpha_\\infty$? Is it regularization $\\alpha_t$ at time $t\\to\\infty$? If not, what does it mean? If so, it seems to me that $\\alpha_t\\to 0$ given the assumptions. This would make $\\alpha_\\infty=0$, which makes the statement very weird. Moreover, if $\\alpha_\\infty\\neq 0$, then why $x_t$ would converge to a minimizer of $f$ given the existence of a regularization term.\n-\tIn line 347, I wonder if authors could explain more on why eq (6) explains spred performs better than LASSO. I believe there are many classical algorithms that can solve LASSO better than just using gradient descent/gradient flow, and they may not have such problems.\n-\tIn line 374, I wonder why $\\beta=1$ is motivated by the discretization of the gradient flow. It is not clear to me what are the connections here.\n-\tIn the proposed algorithm PILoT (Algorithm 1), I wonder why $\\alpha_k$ should be increased when the sparsity $\\|m_k \\odot w_k \\|_1\\ge K$. Since decreasing $\\alpha_k$ would promotes better sparsity, I feel $\\alpha_k$ should be decreased in this case?\n-\tIn experiments, what are the schedules of $\\alpha_k$ that are used?\n\n\nTypo:\n\n-\tBelow eq (6), missing ( in expression of $a_t$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "-\tStudying the sparsification of neural networks is an interesting research problem.\n-\tThe proposed method that applies the idea of implicit/explicit regularization to pruning seems to be new.\n-\tThe performance of the proposed method shown in experiments suggests that there is some improvement over the previous works.", "weaknesses": "-\tMany places are not very clear to me as a reader.\n-\tSee questions section below.", "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": "6NaIgRYFjQ", "reviewer": "Reviewer_UaBp", "summary": "This paper studies the implicit sparse regularization of continuous specification. By studying the implicit bias of a specific mirror flow with a time-dependent Bregman potential, the authors propose a novel continuous sparsification method  \"parametric implicit lottery ticket\" (PILoT). The convergence and optimality is shown theoretically, and the effectiveness in real-world examples is demonstrated numerically.", "questions": "The literature below is related but missed\n\n* Vaskevicius et al, Implicit regularization for optimal sparse recovery, NeurIPS 2019.\n* Li et al, Implicit Sparse Regularization: The Impact of Depth and Early Stopping, NeurIPS 2021.\n* Zhao et al, High-Dimensional Linear Regression via Implicit Regularization, Biometrika 2022.\n* Li et al, Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent, NeurIPS 2022.\n* Li et al, Implicit Regularization for Group Sparsity, ICLR 2023.\n\nMinor comments:\n* .(dot) is missed for the leading bold text in Section 1.1\n* Line 213, \"(Ziyin & Wang, 2023)...\" is not a sentence.\n* Line 404, \"return...\" goes to the next line", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written and easy to follow. I didn't go through the proofs, but the illustrations make sense, and the technical contribution is solid.", "weaknesses": "One point that might limit the significance of the conclusion is that the implicit regularization appears after the model fits the data perfectly (Theorem 2.3), which might not hold in reality.", "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 (Poster)