SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization
Authors: Taisuke Yasuda
Kyriakos Axiotis
Gang Fu
Mohammadhossein Bateni
Vahab Mirrokni
Venue: NeurIPS 2024 poster (2024)
Keywords: pruning
sparsification
sparse optimization
neural network
Primary area: optimization_for_deep_networks
TL;DR: Combining differentiable pruning and combinatorial optimization for block-sparse pruning of DNNs

Abstract: Neural network pruning is a key technique towards engineering large yet scalable, interpretable, and generalizable models. Prior work on the subject has developed largely along two orthogonal directions: (1) differentiable pruning for efficiently and accurately scoring the importance of parameters, and (2) combinatorial optimization for efficiently searching over the space of sparse models. We unite the two approaches, both theoretically and empirically, to produce a coherent framework for structured neural network pruning in which differentiable pruning guides combinatorial optimization algorithms to select the most important sparse set of parameters. Theoretically, we show how many existing differentiable pruning techniques can be understood as nonconvex regularization for group sparse optimization, and prove that for a wide class of nonconvex regularizers, the global optimum is unique, group-sparse, and provably yields an approximate solution to a sparse convex optimization problem. The resulting algorithm that we propose, SequentialAttention++, advances the state of the art in large-scale neural network block-wise pruning tasks on the ImageNet and Criteo datasets.

SequentialAttention++ for Block Sparsification: Differentiable Pruning Meets Combinatorial Optimization
Taisuke Yasuda"!
Kyriakos Axiotis Google Research axiotis@google.co com
Voleon Group
yasuda. www.aaataisiuiieeeee taisukee1gmail..com
Gang Ful Google Research
MohammadHossein Bateni
Vahab Mirrokni Google Research mi mirrokni@google.o
Google Research
zhomasfu@google.ccom
bateni@google.coo com
Abstract
Neural network pruning is key technique towards engineering large yet scalable, interpretable, and generalizable models. Prior work on the subject has developed largely along two orthogonal directions: (1) differentiable pruning for efficiently and accurately scoring the importance of parameters, and (2) combinatorial op- timization for efficiently searching over the space of sparse models. We unite the two approaches, both theoretically and empirically, to produce a coherent framework for structured neural network pruning in which differentiable pruning guides combinatorial optimization algorithms to select the most important sparse set of parameters. Theoretically, ing techniques can be understood as nonconvex regularization for group sparse optimization, and prove that for wide class of nonconvex regularizers, the global optimum is unique, group-sparse, and provably yields an approximate solution to sparse convex optimization problem. The resulting algorithm that we propose, SequentialAAtentiion-+ advances the state of the art in large-scale neural network block-wise pruning tasks on the ImageNet and Criteo datasets.
show how many existing differentiable prun-
Introduction
Pruning methods for neural networks [LeCun et al., 1989] replace dense weight matrices by sparse approximations, which offer improved generalization and inference efficiency in terms of storage, energy consumption, and other computational resources. In various common formulations, the problem of computing the best sparse approximation to dense weight matrix is intractable as generalizes the sparse linear regression problem, which is known to be NP-hard even approximate [Natarajan, 1995, Foster et al., 2015, Gupte and Vaikuntanathan, 2021, Price et al., 2022]. Despite this fact, wide variety of techniques have proven to be quite successful in practice. This includes magnitude pruning, 4 regularization, greedy coordinate descent, sampling, among others.
While earlier works have focused on unstructured (i.e., entrywise) sparsity, which has been active and fruitful area, researchers have rapidly recognized the importance of structured sparsity, which enforces that the sparse approximation respects certain patterns, such as block structure. These structural constraints often lead to further efficiency gains due to improved hardware utilization
Work done while at Google Research.
Cooresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

[Anwar et al., 2017, Pool and Yu, 2021, Liu et al., 2022]. Our work thus focuses on developing new and improved techniques for structured sparsification of weight matrices, and in particular on block sparsification [Ma et al., 2023], which allow for balance between performance gains from hardware utilization and reduced computation due to sparsity [Gale et al., 2023].
1.1 Importance scoring and combinatorial optimization
We argue that existing approaches to neural network pruning have developed along two orthogonal directions: algorithms for importance scoring and algorithms for combinatorial optimization. We roughly think of importance scoring algorithms as those that aim to select small number of important entries (or blocks) of weight matrices, while we think of combinatorial optimization algorithms as wrapper methods that use the importance scoring algorithms as oracles iteratively construct the desired (block) sparse weight matrix.
Among importance scoring algorithms, early popular choices have included magnitude pruning [Thimm and Fiesler, 1995, Han et al., 2015], where the magnitude each trainable parameter serves as proxy for its importance, as well as methods based on gradients [Karnin, 1990, Sanh et al., 2020], Hessians [LeCun et al., 1989 Hassibi et al., 1993, Singh and Alistarh, 2020, Frantar and Alistarh, 2023], and other statisties of the weights. Other works have incorporated & regularization [Wen et al., 2016, Yang et al., 2019] to encourage sparsity. More recently, a class of techniques broadly termed differentiable pruning inspired by techniques for differentiable neural architecture search [Liu et al.. 2019] have increased in popularity, where importance scores and/or soft masks are trained together with the network weights in differentiable manner [Xiao al., 2019, Voita al., 2019, Kang and Han, 2020, Ramakrishnan et al., 2020, Savarese et al., 2020, Zhang et al., 2022]. Variations of this idea use the network weights themselves represent the "importance scores", and simply use a transformation of the original network weights [Schwarz et al., 2021, Vanderschueren and Vleeschouwer, 2023, Cho et al., 2023].
As for the combinatorial optimization aspects of pruning, the use of iterative or greedy procedures has long been explored and is known improve sparsification quality over "one-shot" uses of importance scoring algorithms [LeCun et al., 1989, Hassibi et al., 1993, Ström, 1997, Frankle and Carbin, 2019]. The work of Halabi et al. [2022] gives theoretical justification of this observation via connections to weakly submodular optimization. Combinatorial optimization algorithms beyond greedy approaches, especially local search methods that improve sparsity patterns via local swaps such as iterative hard thresholding (IHT), have long been known in the submodular optimization literature, and have recently been shown to be extremely effective when combined with magnitude pruning [[Eci et al., 2020, Peste et al., 2021, Kuznedeley et al., 2023b, Benbaki et al., 2023]. The work of Peste et al. [2021] also provides strong theoretical guarantees for their approach, ACDC. Similar ideas have also been termed as "neuroregenneration" in work of Liu et al. [2021].
Given these two highly fruitful approaches to the problem of pruming neural networks, it is natural to ask how recent advances in importance scoring algorithms and combinatorial optimization algorithms can work in concert. We investigate this question from both theoretical and empirical perspectives.
1.2 Theoretical results
We first present a theoretical investigation of differentiable pruning techniques for block sparsification when the objective function L IR R is strictly convex and differentiable. This already captures several interesting problems where block sparsification of weight matrices is desired, such as multinomial logistic regression and multiple response linear regression. We take the n variables of our objective function to be partitioned into disjoint groups (Ti where T, S [n]] and possibly have varying size. For instance, in the context of block sparsification, L could correspond to the multinomial logistic regression objective function with K classes and d features, and the Kd variables could be partitioned into blocks Ti. T2...., ,T. Furthermore, we will also consider an & regularization term on the parameters B, that is, we study variants of the problem minBER" L(33) + |||B1||2 Note that explicit & regularization is a standard component of machine learning architectures, and also appears implicitly whenever a loss function is optimized with gradient descent SShalev-Shwart. 2012], 2], with the regularization parameter being controlled by learning rate parameters and early stopping [Suggala et al., 2018].

---

Our contributions are twofold: (1) we show that a wide variety of differentiable pruming techniques can all be understood as an implementation of nonconvex regularization that generalizes the group LASSO, and (2) we show that a wide class of nonconvex regularizers give unique 1-sparse global minimum that coincides with the unique 1-sparse global minimum of a corresponding group LASSO problem. These two results together establish that many differentiable pruning techniques work simply by identifying the same 1-sparse solution as the group LASSO. In turn, it is known that the 1-sparse solution found by the group LASSO is the variable block with the largest squared gradient [Axiotis and Yasuda, 2023]. which is equivalent to the Orthogonal Matching Pursuit [Pati et al., 1993, Shalev-Shwarz et al., 2010, Liberty and Sviridenko, 2017, Elenberg et al., 2018] when applied sequentially (see Appendix B). Thus together, these results make progress towards understanding the inner workings of modern differentiable pruning methods.
1.2.1 Differentiable pruning nonconvex regularization
For our first contribution, we observe that if we minimize the loss L with each of the variable groups B|T for i E [t] replaced by "masked" version q( 31T. and with regularization on w and B. then this problem equivalent to another optimization problem that simply optimizes L with different, and often mausstt-induccigg regularizer. A basic version of this observation already appears in works of Hoff [2017], Axiotis and Yasuda [2023], where it shown that if the masks q are just the identity, then we recover the usual group LASSO problem, that is,
> (I|w 1 + +11111 min C(B) + A Σ |/|T, T. 2
min WER' ,ERR
[((w,))7.H11)++ +
SER"
where (w.,3 r. Vi denotes the concatenation of the "masked" groups w,Glm for i E [t]. We generalize this observation and show that this framework also applies to other ideas popular in the differentiable pruning literature, such as applying & regularization on the masks w to induce sparsity [Yang et al., 2019] or applying softmax-type masks such as (w;) [Yasuda et al., 2023]. We note that prior to our work, there little theoretical understanding on the value of applying such techniques in the context of differentiable pruning.
We also apply similar ideas to differentiable pruning techniques that use the network weights themselves as importance scores [Schwarz et al., 2021, Cho et al., 2023]. Here, the basic observation is that if one optimizes a loss function L with variables /3 replaced by the (signed) entrywise square @ B, then this results in "rich get richer" dynamic where large weights evolve to be larger while smaller weights are driven to zero, resulting in sparse solutions. This idea also has connections to exponentiated gradient descent which also results in sparse solutions [Vaskevicius et al., 2019, Amid and Warmuth, 2020a.b]. However, prior work only handles entrywise sparsity and does not address the question of structured pruning. We show that these ideas can also be understood in the framework of sparsity- innduiig regularizers, even in the group setting. Here, we show that "masking" each of the variable groups Bir, by its l norm [|3) ll2 gives a natural group generalization of this technique, and that this gives an optimization problem that is again equivalent to the group LASSO.
1.2.2 Unique sparse global minima
Our second set of contributions We now consider the following regularized problem, where g IR,, + IR, is a strictly increasing and subadditive function with (0)= = 0, and À 0 is a regularization parameter:
analyze the solutions of wide class of nonconvex regularizers.
E (a(11/1lll)))
min L(B) + X -----1 BER
(1)
For instance, some popular choices of q include the absolute value q(x) |z/, p-th powers g(z) |x]] for < 1, or logarithmic regularizers such as q(x) log(1 + xr). In general, the class of such g (strictly) contains the set of all concave functions g that vanish the origin. Note that the form of (1) slightly differs from the usual form of nonconvex regularizers, as it applies q on the sum E/= x(11/3/7 r. (l2) rather than taking the regularizer to just be Σi= ((111)7; This does not substantially change the nature of the optimization problem as it is the Lagrangian dual for the same constraint. The main result of this section is Theorem 1.1, which relates the group q-regularized
3

---

DNN weight matrix
Partitonn weights into blocks
Scale blocks by softmax mask
Aui
Auz
Aua
Asz-
Aps
Ax1
Axs
Au
exp(1.g)
exp(le>)
Figure 1: Differentiable pruning of weight blocks
objective (I) to the following corresponding group LASSO objective:
min ((B) BER"
Σ 1B1T,112
Theorem 1.1 (Unique sparse global minima). Let q 14 - R. be stricily increasing, subadditive (i.e., q(a + b) S q(a) + q(b) for a, E IR+),, and satisfy q(0) 0. If (2) has unique minimizer 3 with group sparsity at most then 3" also the unique minimizer for (1).
We make several remarks about Theorem 1.1. First, we justify why the assumption of the theorem is vacuous: that is, we explain why the group LASSO objective (2) has sparse solutions. In recent work of Axiotis and Yasuda [2023] the following are shown if L is strongly convex and differentiable:
If A 2 r for max V (L()) m. 2|, then (2) has unique global minimizer
0.
If X < 7 is sufficiently close to т, then (1) has unique 1-sparse global minimizer.
Thus, when À is large enough, Theorem 1.1 establishes that (1) has unique sparse global minimum.
Furthermore, Axiotis and Yasuda [2023] also show that the above global minimizer of the group LASSO problem (2) with group sparsity 1 is supported
group T; that maximizes || C()) |r. l12. that is, selects the group of variables that locally provides the largest improvement in the objective function cost. Repeatedly alternating between selecting such a feature and re-optimizing over the support is an algorithm known as the group orthogonal matching pursuit (group OMP), and has provable guarantees for group sparse convex optimization when L satisfies the restricted strong convexity and restricted smoothness properties [Axiotis and Yasuda, 2023]. It is also shown that a related local search algorithm known group orthogonal matching pursuit with replacement (group OMPR) also applies in this context, which has improved guarantees.
Finally, we emphasize that it is generally difficult to establish structural results for nonconvex optimization problems, even for simple convex problems with nonconvex regularizers. Thus, we believe that our results may be of independent interest in the literature of nonconvex optimization.
1.3 Empirical results: AaateentillAtenntione
We now apply theoretical insights of combining differentiable pruning and combinatorial op- timization to develop a novel algorithm for block neural network pruning, which we call Sequen- tialArtention++.. SequentialAAttention Attention, a feature selection technique based on differentiable pruning developed in work of Yasuda al. [2023], and ACDC, which is a highly effective stochastic adaptation of the classic iterative hard thresholding (IHT) algorithm [Peste et al., 2021] 1] from the combinatorial optimization literature.
is primarily a fusion of two prior techniques: Sequential
Sequential Attention [Yasuda et al., 2023] is algorithm for feature selection neural networks, that introduces a softmax mask that is trained together with the neural network weights. Each of the n input features is scaled by differentiable mask A, exp(Tx)) Σ5= exp( (sp(TT)) for vector T of logits. Note that our theoretical results differentiable pruning, and in particular Lemma 2.1, suggests that this roughly corresponds to performing a log-sum regularization on the corresponding weights for these features. We first extend this the block sparsification setting by instead scaling each block of weights to prune by a similar softmax mask (see Figure 1). Note that in this new setting, Lemma 2.1 shows that this corresponds
group log-sum regularization
each of the blocks.
We then use this differentiable pruning technique as part of a local search procedure inspired by ACDC [Peste al., 2021]. In the originally proposed ACDC algorithm, the neural network is trained

---

in multiple phases, where the phases alternate between a "dense" training phase and a "sparse" training phase. During the dense phases, the weights are trained the standard way, whereas the sparse phases, only sparse set of weights corresponding to the top & weights at the beginning of the phase (i.e., chosen by magnitude pruning) are used. The idea here that if suboptimal sparse support is selected during the sparse phase, then this support can be modified during the dense phase. We note that one of the weaknesses of this algorithm is the use of the weight magnitudes as proxy for the importance of the weights, whereas improved parameter importance estimation is possible by introducing differentiable pruning techniques. Thus in our SequentialAttentioons algorithm, we modify the ACDC algorithm by training softmax mask together with the neural network weights during the dense phase as in Figure I, and then using the softmax mask to select a sparse support during the sparse phases. Our theoretical results establish provable guarantees for slightly modified version of this algorithm, by showing that log-sum regularization can be integrated with a similar local search algorithm that alternates between dropping small weights from the support, selecting weights via regularization, and optimizing on the new support (see Theorem B.3 and Appendix B).
Theory
In Section 2, we present our theoretical results on differentiable pruning and local search algorithms for DNN sparsification. Missing proofs can be found in Appendix A.
2.1 Differentiable pruning as nonconvex regularization
In this section, we show how a wide variety of differentiable pruning techniques studied in the literature can be viewed as nonconvex regularizers. described earlier in Section 1.2.2, we later show that nonconvex regularization can in fact be connected to provable guarantees for sparse convex optimization by implementing the orthogonal matching pursuit algorithm and its variants. Thus, together, we give the first steps towards full theoretical analysis of many popular differentiable pruning techniques in the literature.
2.1.1 Unnormalized softmax
The softmax is popular differentiable by exponentiating each entry and normalizing the result. The softmax forms the backbone of many modern MI techniques ranging from multinomial logistic regression differentiable architecture search [Liu et al., 2019] to attention mechanisms and transformers [Vaswani et al., 2017], and thus a theoretical understanding of the softmax is critical mission for modern machine learning theory.
technique, where vector is transformed
We take step towards this by considering unnormalized softmax, which corresponds to a simple entrywise exponentiation. The unnormalized softmax is a popular alternative to the usual softmax as still captures its allows for more efficient implementations. We show that, in fact, unnormalized softmax can be viewed as a type of log-sum regularization, which is a popular relaxation of the |l-Ilo norm that has been often considered in the machine learning and signal processing literatures [Rao and Kreutz- DellzzDe 1999, Wipf and Nagarajan, 2009, Qiao et al., 2020, Tugnait, 2022, Zhou et al., 2023].
properties [Amid and Warmuth, 2020a,b], while its simplicity
Lemma 2.1 (Unnormalized softmax as log-sum regularization).
min WER' WER',BER" L(Hesp(w.)8mm.H. + 1(1 +18112) = min L(u) + X Σ al ((1l)) BER
where ((a) = f(W)- W.
and W is the Lambert W function, iee, the inverse of 2.1.2 f rr-geuuarizedd masks
Next, we consider the idea of applying a sparsity-inducing regularization mask (see, e.g., the work of Yang et al. [2019]). We show that by regularizing the mask instead of the parameters themselves, the resulting optimization leads to "more nonconvex" regularizer.
5

---

Lemma 2.2 (41-regularized masks as regularization).
min [((w,Alr:))) + (11 +1 = min L(u) + 2 2//3 x WER",BER
| 2/3
uER
2=1
2.1.3 Powerpropagation
Finally, we study differentiable pruning techniques that use the network weights themselves as importance scores. The most straightforward implementation of this idea is to square each of the weights, as explored works such as powerpropagation for neural networks [Schwarz et al., 2021J, but more complex versions have also been considered [Cho et al., 2023]. We show how these techniques can generalized to handle the group setting, and show how they can also be interpreted implementation of group pparsity-inducing regularization.
Lemma 2.3 (Group powerpropagation as Group LASSO).
min 111181l..11211.1 H wER' "ER"
A|B = min C(u) +
> 2m
10/lu/ |1/
HE
2.2 Unique sparse global minima
We will prove the following theorem in this section, which establishes natural conditions for which nonconvex regularization of a convex function produces a unique group-sparse global minimum. As discussed in Section 1.2.2, this theorem is the main crucial result for proving that local search algorithms give provable guarantees for sparse convex optimization.
Theorem 1.1 (Unique sparse global minima). Let q R+ - R. be strictly increasing, subadditive (i.e., q(a + b) S q(a) + (b) for a, E IR+,, and satisfy (()) = 0. If (2) has unique minimizer 3 with group sparsity at most then 33 also the unique minimizer for (1).
We have the following lemma that shows that if q is strictly increasing and subadditive, then the group g-regularization always larger than group LASSO regularization. Thus, the group LASSO objective is always lower bound on the g-regularized objective.
Lemma 2.4. Let q R + R4 be strictly increasing and subadditive. Then,
Σ Blm $
Σ ((118))
Proof. Since q is invertible, applying the subadditivity condition 9(E/=1l1)) l12) and then applying q on both sides of the inequality yields the result.
Furthermore, note that for solutions 3 that have group sparsity at most 1, the group q-regularization has the same value the group LASSO regularization. That is, the lower bound value can be achieved when the group sparsity is at most
Lemma 2.5. Let q R4 - R4 be strictly increasing and satisfy q(0) 0. Then, for any B RR" with group sparsity 1,
Σ (11 (1 l2)
1 112 =
Proof. If (3 has group sparsity most 1, say supported on T, for some j E [t]. then we have
Σ ((1l))mllaa = -4-1(1(113)1 (12)) = 1|3 1l2-
Together, Lemmas 2.4 and 2.5 imply that if the group LASSO objective has unique sparse minimum, then this a lower bound on the optimal value that can be achieved by the qrregularized objective. This proves Theorem I.I. The formal argument can be found in Appendix A.

---

3 The SequentialAAteetiion-+ algorithm
Weight magnitude is a simple and reliable importance score used to prune candidates (in our case. blocks) in sparse optimization problem. In many cases, however, the magnitudes do not correlate very well with the true importances of the candidates. This has been observed e.g. in Axiotis and Sviridenko [2021, 2022], who showed that the magnitude pruning criterion used in the IHT algorithm is provably suboptimal even for simple sparse regression tasks, and proposed an adaptive weight decay deal with this issue. One reason for the suboptimality of magnitude pruning is that the weights are not encouraged to be sparse during model training, leading to redundancy. Methods such as Powerpropagation [Schwarz al., 2021] and Sequential Attention [Yasuda et al., 2023] have been proposed to address this issue by explicitly encoding a non-convexity that encourages weights to be concentrated on sparse subset (this can be viewed as weight re- re-parameterization or concave regularization, as shown in Section 2).
To test the hypothesis that softmax attention weights higher-quality importance scores, consider one-shot block pruning based on the softmax attention scores used in Sequential Attention (see Figure I on how to apply it to blocks), and compare it with block magnitude (Frobenius norm) pruning. The results in Figure 2a suggest that softmax attention scores are generally more reliable block importance scores, especially for larger block sizes. This leads us to adopt the softmax parameterization in our algorithm.
As observed c.g. in Peste et al. [2021], one-shot pruning approaches significantly suboptimal compared to iterative pruning approaches such as ACDC. We use a similar alternating compressed and decompressed phases approach as ACDC, but we apply it the softmax attention weights instead of the block magnitudes. This establishes SequentialAttentione
as a combination between Sequential Attention and ACDC. The basic algorithm be seen in Algorithm 2.
Algorithm Feed- forward layer with the basic version of AequeentialAttentionn to select top k parameters from a kernel W.
Algorithm 2 Attention mask. We omit SPARSIFI- CATION phases for simplicity.
function Mask(A : attention weights, training step)
function FF(X E Raxxn_ input batch, t
-anttrainable state: mask E {0, 1]
training step)
Trainable params:
Kernel W E Raxm Logits L E R=xm
if L is in a DENSE phase then mask topx (A)
A / TL W W @ A Mask(A, A,
return 1,xm
else if' is in SPARSE phase then return mask
return XW end function
end if end function
3.1 The SPARSIFICATION phase
One drawback of sparse/dense (compressonn/dcoopresso phases is that the dense-to-sparss transition is abrupt. Since the lowest-magnitude weights are instantly pruned, this neglects correlations between these pruned parameters. If we were to re-train the model after pruning one parameter at a time, the picture could be drastically different, since low-magnitude weights could grow (this could happen e.g. due to parameter redundancy). In fact, this effect was highlighted by Kuznedelev et al. [2023a], who devised backward selection method based on correlations captured by the Hessian.
Inspired by this approach, we incorporate a backward selection phase between the DENSE and SPARSE phases, which call the SPARSIFICATION phase. In this phase, we gradually prune the least important features based on the attention weights. This gradual process allows the model to re-adjust the attention weights after some parameters pruned. The importance of this phase is validated by ablation experiments in Appendix D.I. We use an exponential pruning schedule, to prune more aggressively in the beginning of the phase, and more carefully at the end (as approach the desired number of candidates k). A comparison of the sparsity schedules of ACDC and SequentialAttentionn - for t e [0,
can be found in Figure 2b. We use the sparsity schedule sparsity(t)
7

---

VALIDATION ACCURACY
BLOCK SIZE:
BLOCK SIZE: x
70%
80%
90%
95%
70%
80%
90%
95%
0.12
-0.11
+0.10
+0.19
+0.13
00.21
-133
0.5
BLOCK SIZE: 32 x 32
BLOCK SIZE: 64 x 64
0.5
68%
78%
88%
92%
58%
66%
74%
79%
+0.32
+0.58
+0.71 +3.17
+2.54
+2.81 +2.85 +5.54
(a) Quantifying the effectiveness of magnitude softmax attention as block importance scores (ResNet50 on ImageNet). For different block sizes and sparsities, we show the difference hetween the validation accuracy (in percentage points) of model pruned one- shot based on the softmax attention scores minus pruned based on the block magnitudes (Frobenius norms). We train dense models for the first half of training. prune once, and then continue
0.0
(b) Sparsity schedules of ACDC and Sequen- tialAttention++. ACDC uses an instant dense- to-sparse transition, while Sequential to train the remaining blocks for the second half of training. The tion++ uses exponential sparsity schedule. experimental sctup is as in Section 4,
Figure 2: (a) Softmax attention vs magnitude pruning, and (b) the SPARSIFICATION phase.
where s is the target sparsity. This interpolates between sparsity 0 and 8, and constitutes a single SPARSIFICATION phase. We choose the constant 4 (for an ablation analysis, see Appendix D.2).
4 Experiments
We evaluate our algorithms on sparsification tasks where dense DNN is approximated by block- sparse counterparts, various block sizes B and sparsities p. where a sparsity p indicates that the DNN layer will only have a p fraction of nonzero entries, and block size of B indicates that the nonzero entries are arranged B x blocks. Note that for a fixed sparsity, larger block sizes generally translate to improved efficiency due to improved hardware utilization, but also degrades quality. Block size corresponds to unstructured pruning. Our experiments are performed on the ImageNet and Criteo datasets. More details on the setup can be found in Section C.I.
4.1 Baseline algorithms
We compare our SequentialAAtteniinnt algorithm to three other representative prior algorithms for DNN pruning. The first is basic magnitude pruming, which is a popular and effective algorithm where the weights are sparsified by keeping the weights with the largest magnitude after training [Frankle and Carbin, 2019]. We it in the block setting by keeping the largest blocks in Frobenius norm. The second algorithm a block generalization Powerpropagation [Schwarz et al., 2021], which combines magnitude pruning with differentiable pruning technique where sparsity is encouraged by squaring the weights. While the original Powerpropagation algorithm did not handle the block sparsification setting, we show that multiplying each block by the Frobenius norm leads a provable generalization (see Lemma 2.3). Finally, we consider ACDC [Peste et al., 2021], which is an adaptation of iterative hard thresholding (IHT) [Blumensath and Davies, 2009] the setting of neural network sparsification, and has produced the state-of-the-arr pruning results for ImageNet [Kuznedelev al., 2023b]. For all algorithms and datasets, we include fine-tuning phase at the end of training, using the pruned model, and evaluate the final pruned model on the test set.
4.2 Results
Our results on ImageNet are summarized in Table 1. The sparsities range over 58-95% and the block sizes over 8, 16, 32, 64. We compare ACDC and ScquentialAttentionr+ Our ACDC implementation closely follows the implementation in Peste et al. [2021]'. We use the phase schedule suggested by Kuznedelev et al. [2023b] (10% dense, 7 equal SPARSE- phases where the last dense phase is extended by 5%, 15% sparse). For Sequenttia/Attenntinn+t, we additionally replace each sparse-dense
We checked our ACDC implementation by verifying that the accuracy of 90% unstructured global pruning matches that of the ACDC paper (75.01 75.03).

---

Table 1: Block sparsification of ResNet50 ImageNet. Our dense baseline validation aceuracy 76.90. The dashes are results where the algorithms diverged because of extreme sparsity. The sparsities where chosen 70%, 80%, 90%, 95%. As seen in the table, for larger block sizes the real sparsity is lower because we are only sparsifying layers with at least 100 blocks.
VALIDATION ACCURACY
SPARSITY:
70%
80%
90%
90%
70%6
80%
9006
96%
ACDC
74.11
72.47
67.74
74.08
72.56
68.61
61.42
APTENTIOON (OURS)
74.14
72:90
69.92
BLOCK SIZE:
32
BLOCKK SIZE: 66%
64 64
68%
78%
88%
92%
58%
74%
ACDC
7-1.0
72.39
68. 96
63.03
73.18
74
71.95
67.36
SEQUENTIALLTTEENTION+ (OURS)
74.82
73.
70.82
65.41
75.53
74.52
72.76
70.30
10000
50000
Figure 3: Training accuracy vs step on ImageNet: Comparison between ACDC and Sequential Atten- tion++. The setting is 90% sparsity and 32 x 32-size blocks.
phase, described in Section 3.1, 1 and replace the last of the 7 phases (including its extension) by SPARSIFICATION phase. We use a batch size of 2048 and a maximum learning rate of 0.8.
phase by
We observe that SequentialAAtentioon+ generally outperforms ACDC on the block sparsification task, across all different block sizes and sparsities that tested. It should be mentioned that this comes the cost introducing additional trainable parameters to the model (one parameter per block). This overhead could be concerning in applications if block size is too small (e.g.. 1), in which the model's parameters are being doubled. However, the overhead is negligible for larger (e.g.. 2 8) block sizes.
Our results on the Critco dataset are presented in Table The sparsities range over p E (90%, 95%, 97%, 98%, }9%} and block sizes B E. {5, 10, 20}. In this experiment, used schedule of 10 sparse-dense phases, in addition to 20% initial dense phase and final 20% sparse phase. Note that for this experiment, unselected blocks are not pruned but multiplied with an all-zero mask. We observe that SequentialAt- tention++ is the best performing algorithm. In fact, notice that the gap widens with large block sizes and high sparsity, suggesting that SequentialAttentionn is highly accurate block sparsification algorithm for large block sizes and extreme sparsities.
used masking instead of pruning for ACDC, meaning that
5 Conclusion
In this work, we unified, generalized, and improved prior approaches to neural network pruning via framework which combines differentiable pruning with combinatorial optimization algorithms, in particular local search techniques. Theoretically, we gave a unified analysis of a wide class of existing techniques via a connection to nonconvex regularization, and proved novel properties about sparse convex optimization with nonconvex regularization. In particular, under which nonconvex regularization yields a unique group-spare global minimum that is supported on the group that maximizes the & norm of the gradient, thus yielding provable guarantees for group sparse convex optimization. Empirically, we proposed a novel algorithm, SequentialAttention++ which outperforms prior methods standard benchmark datasets for neural network sparsification.
established natural conditions
We conclude with a few open directions which we believe to interesting for future work. The first is on characterizing the nature of critical points and local minima of eercoovvx-reeulariize convex problems. This would be more practically useful variation on our result, which only establishes provable guarantees for the global minimizer. For our second question, ask whether

---

one can theoretically establish that nonconvex regularization yields better optimization guarantees than the LASSO. In our work, we have only shown that the quality of solutions found by nonconvex regularization can match the LASSO for wide variety of nonconvex regularizers, but we do not theoretically establish that this formulation is better. would be interesting show, e.g., that nonconvex regularizers allow for faster convergence to the sparse global minimizer.
References
Ehsan Amid and Manfred K. Warmuth. Reparameterizing mirror descent as gradient de- scent. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020a. URL. https: httpt::ttt//ceeeeeeeeee http://oooeeednsn..eeecee nwwrinenripp... wtt.:eerrss.ccpppeee/////e. wttpcc/apppe//////aaaaaaeaee /aah///sh2////////////// Abstract httl..
Ehsan Amid and Manfred K. Warmuth. Winnowing with gradient descent. In Jacob Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria], volume 125 of Proceedings of Machine Learning Research, pages 163-182. PMLR, 2020b. URL http:htt:ppeee http://proceedings mlr wtl.r.pss//eeee wtppp//eess////// ami d20a. html.
Sajid Anwar, Kyuyeon Hwang, and Wonyong Sung. Structured pruning of deep convolutional neural networks. ACM J. Emerg. Technol. Comput. Syst., 13(3):32:13221136 2017. doi: 105/340/30 URL https: //doi. org/10, 10. 1145/3005348.
Kyriakos Axiotis and Maxim Sviridenko. Sparse convex optimization via adaptively regularized hard thresholding. Journal of Machine Learning Research, 22(122):1 2021.
Kyriakos Axiotis and Maxim Sviridenko. Iterative hard thresholding with adaptive regularization: Sparser solutions without sacrificing runtime. In International Conference on Machine Learning, pages 1175-1197. PMLR, 2022.
Kyriakos Axiotis and Taisuke Yasuda. Performance of é regularization for sparse convex op- timization. CoRR, abs/2307 00000 2023. doi: 10.4550/ARXXV.3300.074555 URL https: 400..8850/aaaa w3w..
Riade Benbaki, Wenyu Chen, Xiang Meng, Hussein Hazimeh, Natalia Ponomareva, Zhe Zhao, and Rahul Mazumder. Fast CHITA: neural network pruming with combinatorial optimization. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 2031-2049. PMLR, 2023. URL BtLhttps:/ / http://eoocceeeeeeeeeeeeeee .ml...mmm......... wwwpinnssmm.....rre.eeee www.:eeevv2//eeebaaaaee html.
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Applied and computational harmonic analysis, 27(3):265-22) 274,, 2009.
Minsik Cho, Saurabh Adya, and Devang Naik. PDP: farameter-free differrentiable pruning is all you need. CoRR, abs/2305. 11 2023. doi: 10.48550ARXIV.230.. 12033 URL https: //doi.orrgreeeee 48550/ 2305 11203.
Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. leee, 2009.
Eustache Diemert, Julien Meynet, Pierre Galland, and Damien Lefortier. Attribution modeling increases efficiency of bidding in display advertising. In Proceedings of the ADKDD '1,, pages 1-6. 2017.
Ethan R Flenberg, Rajiv Khanna, Alexandros G Dimakis, and Sahand Negahban. Restricted strong convexity implies weak submodularity, The Annals of Statistics.
2018.
10

---

httpeeee555444441133333333333333 Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2943-2952, PMLR, 2020. www.http:/pproceeeeee #119/evci20s html.
mlr.press.
Dean P. Foster, Howard J. Karloff, and Justin Thaler. Variable selection hard. Peter Grünwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, volume 40 of JMLR Workshop and Conference Proceedings, pages 696-709. JMLR.org, 2015. URL http://prooceeiiggs mlr mlr press/v40/ Foster15 html.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019. URL attps://openrevice www.:/wwwteeeoooooie.... rJ1-b3RcF7.
Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models can be accurately pruned in one-shot. In International Conference on Machine Learning, pages 10323-10337, PMLR, 2023,
Trevor Gale, Deepak Narayanan, Cliff Young, and Matei Zaharia. Megablocks: Efficient sparse training with mixture-of-experts. Proceedings of Machine Learning and Systems, 5, 2023.
Aparna Gupte and Vinod Vaikuntanathan. The fine-grained hardness of sparse linear regression. CoRR, abs/2106.03131, 2021.
03131
Marwa El Halabi, Suraj Srinivas, and Simon Lacoste-Julien Data-efficient structured pruning via submodular optimization. In NewrIPS, 2022. URL pppppp http:/ppperllsss__/leallllaapeep f_flee//////l
mips: cc/
Abstract CenierrracCCoffeee erence. html.
Song Han, Jeff Pool, John Tran, and William J. Dally, Learning both weights and connections for efficient neural network. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1135-1143, 2015. URL https: / http///proceeen...///e//// neurips cc/paper/ www.eee-bbsttat.......ea.aaaa..e html.
2015/hash hatss/hhaaaaeeeeee (a0000eas9000ce44424444444888889
Babak Hassibi, David G. Stork, and Gregory J. Wolff. Optimal brain surgeon and general net- work pruning. Proceedings of International Conference on Neural Networks (ICNN'88) San Francisco, CA. USA, March 28- April 1, 1993, pages 293-299. IEEE, 1993. doi: N0.11099CNN.199329888 URL https://ddot htt//ii.oggg/i// 10. 1119/10101MM 1993, 298572.
Peter D) Hoff. Lasso, fractional norm and structured sparse estimation using Hadamard product parametrization. Computational Statistics & Data Analysis, 15:186-118, 2017.
Minsoo Kang and Bohyung Han. Operation-aware soft channel pruning using differentiable masks. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5122-5131. PMLR, 2020. URL htttp://proceedingg mlr, pwwps/eevvvveeeeeeee beass/vv19/kent 11/1/k9//g2...... html. htmll.
Ehud D. Karnin. A simple procedure for pruning back-propagation trained neural networks. IEEE Trans. Neural Networks, 1(2):239-22) 242,, 1990. doi: 10.1109/72.8033 URL https://doi. org/ 10. 11109/72.80266
Denis Kuznedelev, Eldar Kurtic, Elias Frantar, and Dan Alistarh. Cap: Correlation-aware pruning for accurae sparse vision models. In Thirty Conference on Neural Information Processing Systems, 2023a.
Denis Kuznedelev, Eldar Kurtic, Eugenia lofinova, Elias Frantar, Alexandra Peste, and Dan Alis- tarh. Accurate neural network pruning requires rethinking sparse optimization. arXiv preprint arXiv:2308.022 02060, 2023b.

---

Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In David S. Touretzky, editor, Advances Neural Information Processing Systems [NIPS Conference, Denver, Colorado. USA, November 27-30, 1989]. pages 598-605. Morgan Kaufmann, 1989. URL. htt.: http://papprss nips. (ttpaper/20--opttiiie brain---b-------- aara-mmmmaaaaaaadaaa.......
Edo Liberty and Maxim Sviridenko. Greedy minimization of weakly supermodular set functions. In Klaus Jansen, José D. Rolim, David Williamson, and Santosh S. Vempala, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDON 2017, August 16-18, 2017, Berkeley, CA, USA, volume 81 of LiPIcs, pages 19:1-19:11 11. Schloss Dagstuhl- Leibniz-Zenntrum für Informatik, 2017. doi: (04420/LLPPcs.APPRRR APPROX- RANDOM.2017. PXPPOO-RRANDEE 2017. .99.
19. URL https:///oi.c. org/ 40300/413IIIcc
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, OvenReview.net, 2019. URL
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Zahra Atashgahi, Lu Yin, Huanyu Kou, Li Shen, Mykola Pechenizkiy, Zhangyang Wang, and Decebal Constantin Mocanu. Sparse train- ing via boosting pruning plasticity with neuroregeneration.
In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edi- tors, Advances in Neural Information Processing Systems 34: Anmual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 9908-9922, 2021. URL https: / http///proeeen...e//ee/e/ee newesnnerpppp.. wctppppee//2////aa/e/eaaaa 322766aa1224465f0777333abbabbbbb 36015 Abstract html.
Zhi Gang Liu, Paul N. Whatmough, Yuhao Zhu, and Matthew Mattina. S2TA: exploiting structured sparsity for energy-efficient mobile CNN acceleration. In IEEE International Symposium on Brigh-Perfomante Computer Architecture, HPCA 2022, Seoul, South Korea, April 2-6, 2022, pages 573-586. IEEE, 2022. doi: 10. 10.100///CA5339662200000 202...00222299999 URL https:/ /toi///oo...o/ org/ 10. 1w111/99/HAH96666.. 2022.00049.
Haoyu Ma, Chengming Zhang, Lizhi Xiang, Xiaolong Ma, Geng Yuan, Wenkai Zhang, Shiwei Liu, Tianlong Chen, Dingwen Tao, Yanzhi Wang, Zhangyang Wang, and Xiaohui Xie. HRBP: Hardware- friendly regrouping towards block-based pruning for sparse CNN training. In Conference on Parsimony and Learning (Proceedings Truck), 2023. URL https://openreviee saapeerrrviee..et/oormm net/forum? id=VP1XrdzOBp.
B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM J. Comput., 24(2):227-334, 1995. ISSN 0097-5397. doi: 10. 10.1137/50097533992440000 URL https://doi. org/10.11/ 1137/ $0097539792240406.
Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sun- daraman, Jongsoo Park, Xiaodong Wang, Udit Gupta, Carole-Jean Wu, Alisson G. Azzolini, Dmytro Dzhulgakov, Andrey Mallevich, Ila Cherniavskii, Yinghai Lu, Raghuraman Krish- namoorthi, Ansha Yu, Volodymyr Kondratenko, Stephanic Pereira, Xianjie Chen, Wenlin Chen, Vijay Rao, Bill Jia, Liang Xiong, and Misha Smelyanskiy. Deep learning recommendation model for personalization and recommendation systems. CoRR, abs//996.0000) 2019. URL attp://arxits: wwrgg/bb//1990 00011
Yagyensh Chandra Pati, Ramin Rezaifar, and Perinkulam Sambamurthy Krishnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pages 40-44 44. IEEE, 1993.
Alexandra Peste, Eugenia Iofinova, Adrian Vladu, and Dan Alistarh. AC/DC: alternating compressel/decooppessse training of deep neural networks. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edi- tors, Advunces in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 8557-8570, 2021. URL https: https::/ http:///ppooece..///ee///ce/seee hwwpooceedingg.neuiiisssses neurips. wttppssccpppppe///peeeeeppee /02hhhhhh// 1800068778115fFf00011111aaa33333 -tt.ta/77777770---atatt..cc..
Abstract html.
12

---

Jeff Pool and Chong Yu. Channel permutations for N: M sparsity. In Marc' Aurelio Ran- zato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 13316-13327, 2021. URL https: / http///precee.....c..cce www.sneurippccom www..pp.ccppppper//eeee.e. wwtpc/pppp///////////// Abstract
6688044c3693488277788222222 (1035522222222111144888184 -tw.teasssaabataaaatt..a. html.
Eric Price, Sandeep Silwal, and Samson Zhou. Hardness and algorithms for robust and sparse optimization. In International Conference on Machine Learming, pages 17926-17944. PMLR, 2022.
Chen Qiao, Yan Shi, Yu-Xian Diao, Vince D. Calhoun, and Yu-Ping Wang. Log-sum enhanced sparse deep neural network. Neurocomputing, 407:206- 2020. doi: 118. URL https://doi org/10. 1016/ neucom. 2020. 118.
Ramchalam Kinattinkara Ramakrishnan, Eyyüb Sari, and Vahid Partovi Nia. Differentiable mask for pruming convolutional and recurrent networks. In 17th Conference on Computer and Robot Vision, CRV 2020, Ottawa, ON, Canada, May 13-15, 2020, pages 222 222-229. IEEE, 2020. doi: 10.1 (009/CCC50064202200
URL https:// org/10.110 wttrg/0..119///EI
2020. 00037..
Bhaskar D. Rao and Kenneth Kreutz-Delgado. An affine scaling methodology for best basis selection. IEEE Trans. Signal Process., 47(1):187-200, 1999. doi: 10.1109/78.38251. URI. https: //doi. org/ 10. 10t..111997..73220008
Victor Sanh, Thomas Wolf, and Alexander M. Rush. Movement pruning: Adaptive sparsity by fine-tuning. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: An- nual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December /hash/
http://prceeeiiinnneieee..... 6-12, 2020, virtual, 2020. URL Aww.raat.tttaaaeeeeeeeeeaee (aaalaaaaa76eee4455533eeae
Pedro Savarese, Hugo Silva, and Michael Maire. Winning the lottery with continuous sparsi- fication. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12. 2020, virtual, 2020. URL https: //pooeedg///c wtw.oeeeeiinnn.nuriips..... nwwrineriip.ccm cc/ wtt.cc/cppppac... pwtpp//ppp///pa//pppppppppp /hash// Aww.ttaaaaaaa--aaaaabaaaaaaaaaa.
Abstract .tmll.
Jonathan Schwarz, Siddhant M. Jayakumar, Razvan Pascanu, Peter E. Latham, and Yee Whye Teh. Powerpropagation: A sparsity inducing weight reparameterisation. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 28889-28903, 2021. URL f1o70@eefaef16662f0066e6eee
http://peoeeen.neeeeeeee weg.gsneuripp.coo wwtpcccpppp/////////e// Abstract html.
Shai Shalev-Shwartz Online learning and online convex optimization. Found. Trends Mach. Learn. (2):077-19, 2012. doi: 10.1561/2200000013 URL https://ddoo org/ 10. /2200/200000
Shai Shalev- Shwarzz, Nathan Srebro, and Tong Zhang. Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM J. Optim., 2066)22807-282,, 2010. ISSN 1052-6234.
doi: 10/11377797759574 URL https://doi. org/oo..//.....o 119.0.1111100000555777777
Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URI. https: :tteap:s//pccccddiing www..is.....ppppeeee.e. dLff1ee88B2225513350111111333333 haw.:222bbb-Abttact..hhta. Abstract.
/0220/hhhh//
Nikko Ström Sparse connection and pruning in large dynamic artificial neural networks. In George Kokkinakis, Nikos Fakotakis, and Evangelos Dermatas, editors, Fifth European Conference
13

---

on Speech Communication and Technology, EUROSPEECH 1997, Rhodes, Greece, September 22-25, 1997, pages 2807-2810. ISCA, 1997. doi: 10.21457/EUROSPEECC..999 21437/Eurospa /arr////roopp.ch.. 1997-708,
URL
21437
Arun Sai Suggala, Adarsh Prasad, and Pradeep Ravikumar. Connecting optimization and regular- ization paths. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchii and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pages 10631-10641, 2018. URL htttttss:/pprroeeeeeee cc/paper 2018 h/w.s///aaaaaeaaeeeaaeaaaeeeaaaa 444.44/5000007776544477467777663 Abstract. html.
neurips.
Georg Thimm and Emile Fiesler. Evaluating pruning methods. In Proceedings of the International Symposium on Artificial neural networks, pages 20-25, 1995.
Jitendra K. Tugnait. Sparse-group group log-sum penalized graphical model learning for time series. In IEEE International Conference Acoustics, Speech and Signal Processing, ICASSP 2022, Virtual and Singapore, 23-27 May 2022, pages 5822- 5826. IEEE, 2022. doi: 10. 1091ICS44444 2022.9747446. URL https: //woi. http///ii.og/////// org/10. 1109 1A00///CCASSP99222 2022. .747446.
Antoine Vanderschueren and Christophe De Vleeschouwer. Are straight-through gradients and soft- thresholding all you need for sparse training? In IEEE/CVE Winter Conference on Applications of Computer Vision. WACV 2023, Walkoloa, HI, USA, January 2-7, 2023, pages 3797-3806. IEEE, 2023. doi: 10.1 N0.100//ACV5666882222222 0023.00330
200.:66008..2200000888 URL https: / /doii org/ 10. 1109 1109//ACV56688
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' A'cch-BBus Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December URL https: //poceeddgs... Abstrrctttbstrrrrtcc html.
8-14, 2019, Vancouver, BC, Canada, pages 2968-2979, 2019.
neurips.. cw/papee/pppaeeeeecceeceeeeeee 1tt/22219999hhh/ httpa////oceeeeeeeeeeaae222666e0
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, V. N. Vishwanathan, and Ro- man Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Confer- ence on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998-6008 2017. URL https: http://pppoceee.../////// www.ggs.neris.... cetrrpps.cc/pee http//appr////1/1 /0/0//////////// 3ffee243547dee91fff wttp://eeeeebboooocoooeooooococe 44845aaa- Abstract html.
Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Anna Korhonen, David R. Traum, and Lluís Mårquez, editors, Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, 2019, Volume 1: Long Pupers, pages 5797-5808. Association for Computational Linguistics, 2019. doi: 10.18653/ V1/P19-1580. URL https://doiii org/ 10. 100653/v1/19--1111
Wei Wen, Chumpeng Wu, Yandan Wang. Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 2082-2082, 2016. URL httttppss/prrrcediiigg 9016/hash/44 /tt///////22aabb00beeeeefffeeefe -ataaaa0000455000-aatttttttt htmll.
couurps..c/papes..
David Wipf and Srikantan Nagarajan. Solving sparse linear inverse problems: Analysis of reweighted 11 and 12 methods. In SPARS'09-Signal Processing with Adaptive Sparse Structured Representa- tions, 2009.
Xia Xiao, Zigeng Wang, and Sanguthevar Rajasekaran. Autoprune: Automatic network prun- ing by regularizing auxiliary parameters. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-BBue, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information
14

---

Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, puges 13681-13691, 2019. URL https://proceeddngn wtw.eeeeinnnn..urip.......... neurips. cc/ wtt.cc/cppppp..... httpppppppppeppaeeeeeeee 4ef
Abstracc.. Abstract.html.
Chen Yang, Zhenghong Yang, Abdul Mateen Khattak, Liu Yang. Wenxin Zhang, Wanlin Gao, and Minjuan Wang. Structured pruning of convolutional neural networks via LI regularization. IEEE Access, 7: 7:106385-106394 2019. doi: 10. 109/ACCESS 2019..99209 URL https:
1009 /At.O///AACCS.... 2019. 2933032.
Taisuke Yasuda, Mohammad Hossein Bateni, Lin Chen, Matthew Fahrbach, Gang Fu, and Vahab Mirronni. Sequential attention for feature selection. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, OpenReview.net, 2023.
URL https: http://pppereeeeeee/eee/ee wwt.rreeeeeeeeeeeeeeeeeeeeeeeeee wwt.:ee///eeeee mtt.:pdffiidTTTLLGGxeee
Yuxin Zhang, Mingbao Lin, Mengzhao Chen, Fei Chao, and Rongrong Ji. Optg: Optimizing gradient-driven criteria in network sparsity. arXiv preprint arXiv:2201. 12826, 2022.
Xin Zhou, Xiao-Wos Liu, Gong Zhang, Luliang Jia, Xu Wang, and Zhiyuan Zhao. An iterative threshold algorithm of log-sum regularization for sparse problem. IEEE Trans. Circuits Syst. Video Technol. 33(9):4728-4777 4740, 2023. doi: 10. 10.1099/CCST222333224444 URL https: //doi.org//iitii. 1109/ 2023. 3247944.
A Missing proofs from Section
Proof of Lemmaa 2.1. Note first that for fixed > 0, the function + w² + aa//expx exp(2w) is minimized at w satisfying 2w 2n exp(-2w) = 0, that is, w W22a2)/2 Then, for each group i [t), we can set ulz. 3xp(w:))B(r;
: + 18 113 w
w²
exp(2w:)
where (2 /22 Summing over the groups E [4] gives the desired result.
Proof of Lemma 2.2. Note first that for a fixed > 0, the function w + w + a² /2/ww w satisfying 2a²w-& 33- 0, that is, w = 2/33 Then, for each group i [t]. we can set u/7; w.BlT; so
? is minimized
| l12 3 w? 2 w
wi + ||3 2.113 |wa/
2
where w = 2/3 | 12 2/3 Summing over the groups i E [t] gives the desired result.
Proof of Lemma 2.3. Set u/n: |r: 1 T;- Then,
| || [1 |1, ll2 11,))r; so summing over the groups gives the claimed result.
A.1 Unique sparse global minima
Proof of Theorem I.1. Suppose that the optimal group LASSO solution 3 of objective (2) has group sparsity most Then for any other solution 3" we have that
L(3') + Ag
Σ
2 C(B') + A Σ 1|,'|zz.112 1z.112
by Lemma 2.4
> C(B)) Σ
1T: ll2
by optimality
1=1
15

---

C(8) >q
Σ (11s)))) In 1r:l1a)
by Lemma 2.5.
Thus, 3 must the unique minimizer of (1).
B OMPR via nonconvex regularization
We show that our results from Section 2.2 together with recent work Axiotis and Yasuda [2023] give provable guarantees for local search algorithm based orthogonal matching pursuit with replacement using nonconvex regularization.
We first introduce some definitions needed to state our result.
Definition B.1. Let T3 S [m] for i [4] form partition of [v]. Then, define
| group == if [t] B/x * 0}/.
Definition B.2 (Restricted strong convexity and smoothness). Let C R - R be differentiable. Let T; S [n] for i E [t] form partition of [n]. Then, / is ur-retiiitted strongly convex at group sparsity s if for any 3 E R" and
E IR" with A group I 8,
C(3 + A) ((3) - (VL(3), A) 2
2
and -e-retrricted smooth at group sparsity 8 for any B R and
E R with
| |group S 8,
L
C(B A) [(B) (V (B) A
A
2
We will now obtain provable guarantees for Algorithm 3 in Theorem B.3.
Algorithm 3 OMPR via nonconvex regularization
Initialize S arbitrarily such that [S] = k
for i = 1,..., R do
Let
e arg min L(B) x. X. BER
E9(11
igS
for sufficiently large
Let & S the group maximizing Bi. and j E be the group minimizing ||
5 < (i (i}
end for
Theorem B.3 (OMPR via nonconvex regularization). Let Rr + R. be strictly increasing. subadditive, and at the origin. After R iterations of Algorithm with W 2 ko
13
+ 1)) for
L2 log
((3 L(3))
R k.
Pk+k
then / has group sparsity ||@000 group S k' and satisfies
L(3 L(3")
where Paak is lower bound on the restricted strong convexity constant of I at group sparsity k + ke and L2 is an upper bound on the restricted smoothness constant of group sparsity (see Defiitionn B.2).
Proof. By Theorem 1.1, the optimization problem in Algorithm 3 with q replaced by the absolute value function has unique minimizer with group sparsity at most 1, then / unique global minimizer with group sparsity at most 1, and coincides with this Group LASSO solution. Lemma 3.2 of Axiotis and Yasuda [2023] then establishes that this solution is supported on the group that maximizes the & norm of the gradient, which in turn implies Theorem B.3 via guarantees for the group orthogonal matching pursuit with replacement algorithm (Corollary A.10 of Axiotis and Yasuda (2023]).
D
16

---

Table 2: Block sparsification Criteo. The validation losses average of three Our dense
baseline validation loss is 0.4489.
VALIDATION Loss
SPARSITY: 90%
B1,CKK SIZE: 10
BLOCK
MAGNITUDE
0.4523
0.4093
0.4923
POWPRRPROOAATTION
0.4521
0.4572
0.4920
ACDC
(1.4517
(1.4580
0.4829
SEQUEENTILLATEENION+ (OURS)
0.4515
0.4535
0.4596
SPARSITY: 95%
BLOCK SIZE: 5
BLOCK SIZE: 10
BLOCK SIZE; 20
MAGNITUDE
01.4586
0..8892
0.4998
PROPPRRTONO
0.4547
0.4768
0.4946
ACDC
(L.5447
0.4754
0.4961
ATTENTION++ (OURS)
0.4540
0.4595
0.4715
SPARSITY: 97%
BLOCK SIZE: 5
BLOCK SIZE: 10
BLOCK SIZE: 20
MAGNITUDE
0.4656
0.5004
0.5079
PROPAGATON
(1.4587
0.5061
0.5093
ACDC
0.4606
0.4936
0.5056
SEQUENTIALATEENIINN+ (OURS)
0.4570
0.4708
0.4865
SPARSITY: 98%
BLOCK
BLOCK SIZE: 10
MAGNITUDE
0.5145
0.5447
POWERPROPACATION
0.4622
0.5158
0.5379
ACDC
0.4692
0.4929
0.5184
SEQUENTIALATTEETION++ (OURS)
0.4601
0.4904
0.5162
SPARSITY: 99%
BLOCK SIZE: 5
BLOCK SIZE: 10
BLOCK SIZE: 20
MAGNITUDE
0.4881
0.5376
0.5482
POPPRPRONNN
0.5017
0.5295
0.5425
ACDC
0.5050
0.5153
0.5427
(OURS)
0.4803
0.5068
0.5258
Additional details on experiments
C.1 Experimental setup
ImageNet [Deng et al., 2009]. ImageNet is the most widely used vision dataset and is considered as the facto benchmark in the neural network pruning literature, culminating in the state of the art results in Kuznedelev et al. [2023b]. We use ResNet50 and standard training setup (90 epochs, SGD with cosine learning rate and momentum, weight decay). We reshape the 4-dimensional (H x W x Cin X Cou) kernel tensors used in convolutional layers to 2D matrices of shape HWC, Cin Couts which define the 2D block candidates for pruning. We prune all layers uniformly, except for layers with 100 blocks, which do not prune at all, to avoid degeneracy at high sparsities.
Criteo [Diemert et al., 2017]. Criteo is standard public dataset for the clickthrough rate (CTR) prediction task, which consists of 33M training examples with 13 numerical and 26 categorical features. The model we sparsify is standard fully connected DNN with three 400-width layers and an additional embedding layer to transform each input feature into an embedding vector of size 10 (for total embedding width of 390). We note that simple MIP is often fairly competitive model for this task [Naumov et al., 2019]. We prune the first dense layer after the embedding layer. We use Adam optimizer with learning rate that decays exponentially from 2 10-2 to 3 10-4 We train to minimize the cross-entropy loss for 25 epochs with a batch size of 32768.
C.2 Block sparsification results Criteo
We give block sparsification results the Criteo dataset in Table 2.
17

---

Block size: 8x8
Block 16x16
0.74
0.74
0.72
0.70
0.71
0.68
0.70
0.66
0.89
0.64
ACDC
ACDC Sequaniasktteeiion++
0.08
Seqummiikktteemio+++
0.750 0.775
0.025
Spersity
Sparsity
Block size: 32x32
Block size: 64x64
0.74
0.75
0.72
0.73
00070
0.72
0.68
0.71
0.66
0.69
Socuentaakttention+*
ACDC
0.68
SecuentalAttenioon+
ACDC
0.70
0.75
0.80 Sparsity
0.85
0.30
Sparsity
Figure 4: Block sparsification on Imagenet.
C.3 Additional tricks
In addition to the basic algorithm described in Section 3, our implementation of ScquentialAtten tion++ incorporates several other ingredients for improved empirical performance. First, confirm the observation of Peste et al. [2021] ]] that resetting the optimizer between each phase of SequentialAt- tention++ is crucial for good performance. We note that this is also suggested by theoretical results (Theorem B.3), which suggests that each of the dense and sparse phases should be thought of separate optimization problem that is solved independently. Similarly to Kuznedelev et al. [2023b], we also observe that weight decay significantly boosts performance, even when applied to the attention logits.
Second, we observe that pruning each layer of the network separately performs better than a global pruning algorithm which attempts to prune all layers at once. We suggest that this may be the due to "bottlenecking" behavior, where a global pruning algorithm may choose to almost completely climinate layer which may destroy the connectivity of the neural network. While this is not the case when pruning individual parameters, pruning large blocks can easily eliminate a layer. We use uniform sparsity across layers, but choose not to sparsify layers containing less than 100 blocks. This because layers have greatly varying sizes, and want to avoid a sharp quality drop from overpruning smaller layers, which was observed in experiments. Finally, clip attention weights to the range [n density, n n/density] to avoid them becoming too small or too large.
C.4 Additional results
We provide additional plots for our experiments in Figures 4 and 5. In Figure 4, we plot tradeoffs between the validation accuracy and weight matrix sparsity for SequentialAAtteniion- and ACDC Peste et al. [2021]. In Figure 5, we plot tradeoffs between the validation loss and AUC against weight matrix sparsity for SequentialAttention=+ and our three baseline algorithms of Magnitude Pruning, Powerpropagation Schwarz et al. [2021], and ACDC Peste et al. [2021].
18

---

Block size:
Block size:
Magnitude Fruning
Magnitude Fruning
0.455
ACDC
Power Propagation
4
ACDC
0.49
18 Teldation (022
0.453
0.48
0.452
0.47
0.451
0.46
0.450
0.5
0.6
0.7
0.8
0.9
1.0
0.5
0.6
0.7
0.8
0.9
1.0
Sparsity
Spansity
Block size: 10
Block
0.54
Magnitude Pruning
Magnitude Fruning
Power Propagation
Power Propagation
0.52
ACDC
ACDC
Socuenta/Attmtooon+
Socuenbalttention++
validadion 1652
Valicstion
0.46
0.46
0.5
0.6
0.7
0.8
0.9
1.0
1.0
Sparsity
Sparsity
size:
Block
0.81
0.808
0.806
0.78
0.77
0.76
0.75
Magnitude Pruning
Magnitude Pruning
Power Propagation
ACDC
Sequentallttentoree
Secuenialkttentoon**
0.6
Sparsity
Spansity
Black
0.800
0.80
0.775
0.750
0.725
3 0.70
0.65
Magnitude Pruning
Magnitude Pruning
Power Propagation
Power Propagation
0.650
0.60
SequentialAttetionn-
SequentisAAteeninnn-4
0.625
1.0
Sparsity
Sparsity
Figure 5: Block sparsification on Critco. There are no Powerpropagation results for block size 1 because the algorithm diverged.
D Ablations
D.1 Importance of the SPARSIFICATION phase.
We perform experiments to study the effect of the SPARSIFICATION phase, as described in Section 3.1,
to the final accuracy. To that end, remove the SPARSIFICATION phase and only apply alternating
19

---

Table 3: Removing the SPARSIFICATION phase from AeguentialAttentionns The results show validation accuracy for training block-spars, ResNet50 on ImageNet. We use the same sparsities as in Table 1.
VALIDATION ACCURACY
SPARSITY:
70%
80%
90%
95%
70%
80%
903
96%
VALIDATION ACCURACY
0.61922
0-61405
0.69678
0,68152
0.88658
0.70079
0.72845
DIFF FROM BASELINE
0.0235
0.04006
0.00624
0.01108
0.01262
0.00733
+0.00089
BLOCK
BloCK
SPARSITY:
68%
78%%
88%
92%
68%
741%
79%
VALIDATION ACCURACY
0.72333
0.72006
0.73346
0.7432
0.741994
0.74099
0.74268
0.75104
RASELINE
0.00196
+-0.00059
0.00300
0.00647
0.00421
Table 4: Modifyyng the exponent constant in the schedule of the SPARSIFICATION phase. Block-sparse training of ResNet50 on ImageNet for 90% sparsity.
VALIDATION ACCURACY
BLOCK SIZE
x
16 x 16
32 x 32
64 x 64
C
2
0.69403
0.69613
0.70614
0.72264
C
0.6956
0.6992
0.70817
0.72756
8
0.69202
0.70036
0.70976
0.72614
DENSE and SPARSE phases, each of equal duration. The final phase before the last fine-tuning is now DENSE phase.
The results Table 3 show that, on average over different block sizes and densities, removing the SPARSIFICATION phase decreases validation accuracy by 0.009, or 0.9 percentage points. We conclude that the SPARSIFICATION phase an important feature of SequentialAAtentiion-
D.2 Choice of the SPARSIFICATION exponent.
In this section, we try different values of the constant used in the exponent of the schedule of the SPARSIFICATION operation. We remind that during a SPARSIFICATION phase, the sparsity varies as sparsity (t) = T-c-o for t E [o, 1], where is the target sparsity. The constant c determines how non-linearly the sparsity interpolates from 0 to s.
--e-d
20

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We support our main claims with theorems and empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss some limitations in Section 5 and suggest these as research directions for future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
Our theoretical results are supported by full proofs, which can be found in the main text and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yss]
Justification:
We plan to release the code used in experiments if accepted.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer: [Yes]
Justification: We plan to release the code used in experiments accepted. The datasets used in experiments are popular and publicly available datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
Bagilic/guddee/odSSuubiii ion for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//nips.coom htlpsscccppblicc//ee http:/gddeeeeeeeee /ete:///ooeebmiii ssi ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We plan release the code used in experiments if accepted, which will contain this information.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification:
[TODO]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by eπror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
23

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We plan to release the code used in experiments if accepted, which will contain this information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that NeurlPS Code of Ethics https: http///eerrpppeeeeee httpp//wwts.pppuupepppeeppcpceet cttpppiiic/thiiccsueeeeeeeee
didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: (TODO)
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
25

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "soOXL7Ic4W", "reviewer": "Reviewer_5Nz3", "summary": "This work studies the task of neural network pruning. The authors unify the two main directions of the literature: differential pruning and combinatorial optimizations. Specifically, they point out that most differentiable pruning techniques can be considered as non-convex regularization group sparse optimization problems. Based on this theoretical analysis, they propose SequentialAttention++. The empirical evaluation shows their method reaching state-of-the-art results.", "questions": "Do you have more reasons behind the combination of Sequential Attention and ACDC? Also, can you explain why in most of the experiment results, larger block size seems to perform better? Wouldn't a smaller block size mean more flexibility in pruning?", "limitations": "Yes, the authors discuss the limitation of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The theoretical insight to unify differential pruning with combinatorial optimizations seems to be a strong theoretical contribution. The empirical evaluation also shows strong performance of the proposed method.", "weaknesses": "The writing is slightly hard to follow. Specifically, the exact motivation of SequentialAttention++ seems a bit unclear. Is it just a combination of Sequential Attention and ACDC because they are currently state-of-the-art methods? Or is there a stronger reason and theoretical support behind this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work!\n\n> Is it just a combination of Sequential Attention and ACDC because they are currently state-of-the-art methods? Or is there a stronger reason and theoretical support behind this?\n\nBased on our experiments, as well as the work of Yasuda et al. 2023, the softmax attention parameterization provides a reliable way to rank network components by importance. In particular, for structured (block) sparsity, we find that the softmax attention scores are significantly more reliable than magnitude scores (Figure 2a), especially for larger block sizes. On the other hand, given some proxies for the importance of the candidate components, a very successful approach is to use an iterative method to search over the set of candidates, as opposed to a one-shot pruning approach. For example, orthogonal matching pursuit (OMP) performs forward selection with gradient magnitude scores, IHT/ACDC perform local search with parameter magnitude scores, GMP performs backward selection with parameter magnitude scores, etc. Out of these, ACDC is a state-of-the-art algorithm for neural network pruning, and so we focused on combining it with the softmax attention parameterization as a method that is likely to produce superior results.\n\n> Also, can you explain why in most of the experiment results, larger block size seems to perform better? Wouldn't a smaller block size mean more flexibility in pruning?\n\nIf the reviewer is referring to Table 1 (Imagenet results), note that different block sizes are evaluated with different sparsity rates, so it is not true that higher block size leads to better quality. The reason we had to use different sparsity rates is because the layers of ResNet-50 have a wide variety of sizes, and we refrain from sparsifying smaller layers (less than 100 blocks) because it leads to drastic quality degradation. So even though the sparsity rate for layers we sparsify is the same, fewer layers are sparsified as the block size increases. In our results in Table 2 (Criteo dataset) where we only sparsified one layer, increasing the block size leads to worse quality, as expected.", "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": "Nm2nAElYqS", "reviewer": "Reviewer_rDbF", "summary": "This paper analyzes sparse training with group sparsity and proposes a general theoretical framework to analyze both hard thresholding (discrete) and scoring (continuous) pruning methods. The proposed theoretical framework of block sparsification encompasses multiple existing sparsification methods via non convex regularizers and shows the existence of a unique global minimizer for such problems by establishing an equivalence to the group LASSO problem. Based on the theoretical insights, the proposed algorithm Sequntial Attention++ iteratively prunes parameters combining the approach of AC/DC with block sparsification and score based pruning.", "questions": "See above.", "limitations": "The paper sheds light on the connection between sparsification methods via nonconvex regularizers to the group LASSO problem, thus establishing a theoretical framework to analyze continuous sparsification methods, which is also empirically validated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides a general theoretical framework to analyze score based sparsification methods and shows the existence of a unique minimizer.\n2. The authors build on existing work to propose a new pruning algorithm Sequential Attention++ combining hard thresholding and score based pruning.", "weaknesses": "1. The authors discuss that the magnitude is not necessarily the best importance scoring metric for sparsification. However, experimentally it has been observed to be the best performing criteria across multiple datasets for hard thresholding methods with unstructured pruning (see [1]). I would like to know if the authors observe a different trend for (i) structured pruning and (ii) score based sparsification instead of hard thresholding i.e. does magnitude based scoring perform worse in case of differentiable pruning. \n2. In the proposed algorithm, the authors use a softmax based scoring method. Does using an unnormalized softmax lead to similar results?\n3. If I understand correctly, the proposed results also hold for scoring methods which use the network weights as a score like in STR  [2] or like powerpropagation. However, does the additional overparametrization in case of using a separate scoring parameter improve the overall performance of the network?\n4. For ImageNet it would be nice to see comparisons with structured DST [2] as it achieves a state of the art performance for structured sparsity.\n5. Have the authors tried the same algorithm without an AC/DC approach, by simply training with a scoring method and pruning after every few epochs. Is the dense phase necessary?\n\n[1] Hoefler, Torsten, et al. \"Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks.\" Journal of Machine Learning Research (2021).\n\n[2] Kusupati, Aditya, et al. \"Soft threshold weight reparameterization for learnable sparsity.\" International Conference on Machine Learning (2020).\n\n[3] Lasby, Mike, et al. \"Dynamic Sparse Training with Structured Sparsity.\" The Twelfth International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the very detailed review!\n\n> The authors discuss that the magnitude is not necessarily the best importance scoring metric for sparsification. However, experimentally it has been observed to be the best performing criteria across multiple datasets for hard thresholding methods with unstructured pruning (see [1]). I would like to know if the authors observe a different trend for (i) structured pruning and (ii) score based sparsification instead of hard thresholding i.e. does magnitude based scoring perform worse in case of differentiable pruning.\n\nThe answer to both (i) and (ii) is yes. For structured (block) pruning, we observe a consistent and strong improvement by using the softmax attention parameterization instead of magnitude scores. In Figure 2a, we compared the quality of one-shot block sparsification when using magnitude scores vs the softmax attention parameterization, and found that the latter gives higher-quality results, especially for larger block sizes (In addition, our results in Tables 1, 2 include baselines like ACDC and one-shot magnitude pruning, which use magnitude scores). For unstructured pruning, it is important to note that the softmax attention reparameterization introduces a large number of additional parameters, reducing its practicality over other methods. Nonetheless, we ran some experiments to answer this question, and found that one-shot softmax attention-based pruning outperforms magnitude pruning even for the setting of unstructured sparsity (accuracy 74.96 vs 74.51 for 80% sparsity and 73.19 vs 72.75 for 90% sparsity). (Technical note for unstructured sparsity: we observed that the quality of the sequential attention reparameterization degrades as the number of candidates becomes too high (as is the case in unstructured sparsity). We mitigated this by decreasing the softmax temperature to 0.25 from the default of 1.0, to obtain the above results).\nMore generally, there are also other works that document improvements over magnitude pruning, dating back to the first works on neural network pruning. We have given a discussion of this history along with many references in our introduction.\n\n> In the proposed algorithm, the authors use a softmax based scoring method. Does using an unnormalized softmax lead to similar results?\n\nBased on our experiments, using unnormalized softmax leads to similar but slightly degraded results. For 32x32 block sizes, we have the following results:\n\n```\nSparsity | unnormalized | normalized\n68% 74.69 74.82\n78% 73.21 73.78\n88% 69.45 70.82\n92% (diverged) 65.41\n```\n\nSo experimentally it seems that the normalization provides a small quality gain and some stability improvement. It is possible that these results could be improved by tuning the learning rate and weight decay of the logits used in the exponential function (which together serve as a sort of normalization).\n\n\n> If I understand correctly, the proposed results also hold for scoring methods which use the network weights as a score like in STR [2] or like powerpropagation. However, does the additional overparametrization in case of using a separate scoring parameter improve the overall performance of the network?\n\nGreat question. As we remark in Section 2.1.3, applying the Hadamard overparameterization actually increases the concavity (i.e. decreases q) of the equivalent l_q regularizer, which leads to inducing a harder sparsity constraint. As an example, a combination of the Hadamard overparameterization with l1 regularization has been considered in Yang et al. 2019. Quantifying the precise tradeoffs between overparameterization and the choice of non-linear weight activations is an interesting question. As for an experimental comparison, our results on the Criteo dataset in Table 2 include a comparison with Powerpropagation, where we observe a consistent improvement by using SequentialAttention++.\n\n> For ImageNet it would be nice to see comparisons with structured DST [2] as it achieves a state of the art performance for structured sparsity.\n\nWe adapted the structured sparsity approach of [2] for block sparsification, however we were not able to produce conclusive results. Fundamentally the STR method requires careful tuning of the weight decay rate and sigmoid initialization in order to properly control the sparsity rate. In order to get a fair comparison, we would have to match the block sparsities in each layer, which is a considerably hard hyperparameter tuning problem. The default hyperparameter values proposed in [2] for 90% sparsity do not seem to transfer to the block sparsity setting.\n\n> Have the authors tried the same algorithm without an AC/DC approach, by simply training with a scoring method and pruning after every few epochs. Is the dense phase necessary?\n\nOne challenge with this approach is that, because of weight decay, the scores of the pruned candidate blocks will keep decreasing during the sparse phases. As such, this scheme will be equivalent to one-shot pruning (since the pruned candidate blocks will be too small and will never be selected again after the first pruning). We believe the introduction of the dense phase is important for re-introducing these pruned blocks as active candidates. Something close to this would be to significantly decrease the size of the dense phase. We tried reducing the duration of each dense phase to only around 11 training steps, and let the sparse phases occupy the rest of the training. However, the results are not promising: accuracy 67.28 vs 72.15 for 32x32 blocks and 88% sparsity, likely because of high variance during the short dense phase.", "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": "6jnyc34VNk", "reviewer": "Reviewer_2z8b", "summary": "This paper focuses on bringing a theoretical understanding to differentiable pruning for neural networks and reveals connections to group lasso.", "questions": "I think this paper provides some useful connections between optimization theory and pruning. I haven’t checked the math carefully, but things seem reasonable overall. It is interesting that the differential pruning techniques can be explained using group lasso. The empirical results are nice to have, but I view the theoretical connections made in the paper to be the main contribution.\n\n1) Does the training curve in Figure 3 represent the entirety of the training? It looks like for the orange curve, the peak around step=48000 is higher than the accuracy at the end of the training. \n\n2) Also, what happens if the models are trained longer? Will the blue curve continue to do better than the orange curve?", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Please see the “Questions” section.", "weaknesses": "Please see the “Questions” section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review!\n\n> Does the training curve in Figure 3 represent the entirety of the training? It looks like for the orange curve, the peak around step=48000 is higher than the accuracy at the end of the training.\n\nThe peak around step=48000 is due to the use of a dense phase during this training step, and is therefore not a fair comparison to the training accuracy of the final sparse model.\n\n> Also, what happens if the models are trained longer? Will the blue curve continue to do better than the orange curve?\n\nWe evaluated this by continuing to train both models in that figure with a fixed final learning rate of 1e-3 for another 90 epochs (for a total of 180 epochs). The gap between the two curves does not narrow at all (also the final accuracy of the orange curve (65.83) doesn't reach the accuracy that the blue line had before these extra 90 epochs (67.42)), leading us to conclude that the quality difference between the two algorithms is likely because of the different sets of blocks chosen, rather than a delayed convergence.", "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:

Meta-review: This work addresses structured neural network pruning by unifying differential pruning and combinatorial optimizations. A nonconvex regularization for group sparse optimization is shown to underpin many differentiable pruning methods, and its global optimum is analyzed.  A practical algorithm SequentialAttention++ is then proposed, whose effectiveness is demonstrated on block-wise pruning tasks on the ImageNet and Criteo.

This paper is well written.  It provides new insights on optimization and neural network pruning, and the empirical algorithm is effective.  I am personally a bit concerned that most theoretical results assume the group sparsity is at most 1.  However, overall, the merits of the paper make it a solid contribution to the conference.
Decision: Accept (poster)