The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information
Authors: Diyuan Wu
Ionut-Vlad Modoranu
Mher Safaryan
Denis Kuznedelev
Dan Alistarh
Venue: NeurIPS 2024 poster (2024)
Keywords: Optimal Brain Surgeon
Sparse Recovery
Pruning
Second-Order Optimization
Primary area: optimization
TL;DR: We consider iterative version of OBS framework of finding sparse solutions providing practical evidence and theoretical justifications for convergence.

Abstract: The rising footprint of machine learning has led to a focus on imposing model sparsity as a means of reducing computational and memory costs. For deep neural networks (DNNs), the state-of-the-art accuracy-vs-sparsity is achieved by heuristics inspired by the classical Optimal Brain Surgeon (OBS) framework [LeCun et al., 1989, Hassibi and Stork, 1992, Hassibi et al., 1993], which leverages loss curvature information to make better pruning decisions. Yet, these results still lack a solid theoretical understanding, and it is unclear whether they can be improved by leveraging connections to the wealth of work on sparse recovery algorithms. In this paper, we draw new connections between these two areas and present new sparse recovery algorithms inspired by the OBS framework that come with theoretical guarantees under reasonable assumptions and have strong practical performance. Specifically, our work starts from the observation that we can leverage curvature information in OBS-like fashion upon the projection step of classic iterative sparse recovery algorithms such as IHT. We show for the first time that this leads both to improved convergence bounds in well-behaved settings and to stronger practical convergence. Furthermore, we present extensions of this approach to training accurate sparse DNNs, and validate it experimentally at scale.

The Iterative Optimal Brain Surgeon: Faster Sparse Recovery by Leveraging Second-Order Information
Diyuan Wu
Tonut- Modoranu'
Mher Safaryan'
Denis Kuznedeley
Dan Alistarh
Institute of Science and Technology Austria (ISTA) YYandex Research
3Skoltech
Abstract
The rising footprint machine learning has led focus on imposing model sparsity as a means of reducing computational and memory costs. For deep neural networks (DNNs), the sante-of-the-aad accuracy-vs- vs-sparsity achieved by heuristics inspired by the classical Optimal Brain Surgeon (OBS) framework (LeCun et al.) 1989 Hassibi and Stork| 1992, Hassibi et al. 1993), which leverages loss curvature information to make better pruning decisions. Yet, these results still lack solid theoretical understanding. and it is unclear whether they can be improved by leveraging connections to the wealth of work on sparse recovery algorithms. In this paper, we draw new connections between these two areas and present new sparse recovery algorithms inspired by the OBS framework that comes with theoretical guarantees under reasonable assumptions and have strong practical performance. Specifically, our work starts from the observation that can leverage curvature information in OBS-like fashion upon the projection step classic iterative sparse recovery algorithms such IHT. We show for the first time that this leads both to improved convergence bounds under standard assumptions. Furthermore, we present extensions of this approach to the practical task of obtaining accurate sparse DNNs, and validate it experimentally at scale for Transformer-based models on vision and language tasks.
Introduction
The increased focus efficiency in machine learning has led to significant interest in sparsity a means of reducing both the computational and memory costs of training and executing accurate models, with literally hundreds of methods being proposed recently [Hoefler et al. 2021] The key trade-off in this context is between the degree of sparsity imposed and the accuracy of the dense (uncompressed) model.
Currently, the best performing post-training methods for DNNs are inspired by the Optimal Brain Damage (OBD) framework of LeCun et al. 1989]. generalized via the Optimal Brain Surgeon (OBS) approach of Hassibi and Stork 1992), J. Hassibi et al. 1993 In brief, OBD/OBS poses accurate pruning constrained optimization problem, and approximates the optimal solution by leveraging recond-order information about the loss function to make better pruning decisions. Recently, there has been significant work on versions of OBS that can scale to deep neural networks (DNNs), leading
to surprisingly good results at scale Frantar and Alistarh 2022 2023) Yet, no theoretical guarantees are known for OBS-type algorithms.
'The two frameworks primarily differ in the second-order approximation. Since OBS a strict generalization of OBD, in the following we use OBS to denote the pruning framework.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

By contrast, the area of sparse recovery provides rich set of theoretically-uustiie iterative algorithms for reconstructing or upproximating
nigh-dimensional but sparse signal from limited set of observations, such as Iterative Hard Thresholding (IHT) [Blumensath and Davies 2009) or Matching Pursuit (MP)-type [Tropp and Gilbert, 2007] algorithms. Yet, to our knowledge, these algorithms do not usually employ curvature information in their structure, and do not extend to DNNs.
It is still an open question whether one can connect these lines of work, for instance by leveraging second-order information to improve the convergence of sparse recovery algorithms,, or by extending these algorithms the more complex task of sparsifying multi-layer DNNs. This the question we approach in this paper.
Contributions. In this paper, we propose a family of algorithms that generalize the post-training OBS framework to the iterative setting, popular in the context of sparse recovery. This new approach, which we call the Iterative Optimal Brain Surgeon (I-OBS), provides convergence guarantees that can improve upon classic algorithms such as IHT by leveraging second-order information on the sparse projection step. As a consequence, we provide the first theoretical guarantees for popular practical pruning heuristics such as OBC Frantar and Alistarh (2022) or WoodFisher (Singh and Alistarh 2020). Second, on the practical side, we show that the improved guarantees can lead to Taster practical convergence.
In more detail, our contributions are as follows:
We propose a new family of sparse recovery algorithms called Iterative Optimal Brain Surgeon (I-OBS), which generalize upon the classic IHT--ased algorithms by leveraging approximate second-ordes information in the sparse projection step.
We prove that this family of algorithms provides faster analytical convergence rates than previously-knon known methods. under standard first- and second-order smoothness and strong convexity assumptions. We also show that prior practical pruning algorithms such as
WoodFisher (Singh and Alistarh, 2020) and OBC (Frantar and Alistarh 2022 are special cases of our framework, providing them with theoretical guarantees.
We provide practical variants of these algorithms, which relax the theoretical constraints but can be easily implemented and can scale to large problem instances arising in the compression of vision and language models. We validate our results both on synthetic datasets, showing that our approach leads to faster convergence relative to IHT, and therefore validating our theoretical findings. Finally, we present empirical evidence that our approach can scale to large models and lead improved results. by implementing it to accurately sparsify models with more than 1 billion parameters.
2 Related Work
Model compression. In recent years, the literature has witnessed significant surge in research focusing on model compression. Among various techniques, network pruning or sparsification stands out as a powerful approach, effectively reducing the model's parameter count by eliminating the
least influential weights and fine-tuning the remaining ones [Singh and Alistarh| 2020 Lin et al.,
2020 Hoefler et al.) [021] Frantar and Alistarh ].23]. Following a similar concept to pruning, quantization techniques suggest reducing the precision of each parameter by allocating fewer bits.
rather than completely removing weights from the network (Yao et al. 2022 Dettmers et al. 2022
Frantar et al. 2023 Kim et al. 2023). Additionally, methods that leverage low-rank factorization are gaining popularity due to their inherent tensor structure (Hu et al.] 2022 Lialin et al., 2024 Xu et al.)
2023 Nikdan et al. 2024]. J. Notably, these compression methods are versatile, applicable during both the optimization and post-training phases. Another noteworthy technique is knowledge distillation Hinton et al. 2014, Mishra and Marr 2018 Polino et al., 2018), where the compressed model is compact "student" model trained by a larger "teacher" model. The teacher model can either be already trained to high accuracy or trained simultaneously with the student model [Guo et al. 2020
Harutyunyan et al.] 2023].
Sparse recovery. The model compression problem we study in this paper is closely related to the field of sparse recovery, which aims to optimize certain objective function based on sparsity constraints, see e.g. [Zhao] 20188) for a detailed introduction. One of the most common sparse optimization algorithms is the iterative hard thresholding algorithm (IHT) first proposed by Blumensath and Davies
2

---

2009 for compressed sensing problem, which applies a topk operator to each gradient update, which
keeps the i elements with the largest magnitude and setting the rest zero. While IHT is simple
and effective, there is also a long line of work [Blumensath, 2012 Bahmani et al. 2013 Chen and
Gu 2017 Meng and Zhao 2020, /Zhou et al., 2021] that studies the sparse variants Newton's
methods for these sparse optimization problems, aiming to get acceleration benefits. In particular,
Blumensath [012]] proposed a general definition of accelerated IHT for sparse linear regression
problems, and showed an accelerated convergence rate in this type of method. Bahmmani et al.) [2013)
proposed general framework called GraSP, and they proposed to use a restricted Newton step as an approximation of the sparse constrained optimization problem. Chen and Gu [2017] proposed Fast Newton Hard Thresholding Pursuit, which uses an iterative algorithm to estimate the inverse Hessian matrix for a stochastic objective function. They also obtain composite rate of convergence. [Mngg and Thao 2020] consider applying hard thresholding to Newton's 's method for sparse linear regression Iterative Hard Thresholding (NSIHT), and prove
problems, where they call Newton-Step-Banl a global convergence for this specific problem. (Zhou et al.
[202T) proposed a general framework called Newton Hard Thresholding Pursuit (NHTP) for general sparse optimization problems showing implicit global and local quadratic convergence rates. In contrast to our approach, at each step NHTP selects the spare support based on the first-order gradient information, switches restricted gradient update whenever the restricted Newton update fails to provide sufficiently good descent direction, and additionally incorporates line search procedure to achieve global convergence.
Further comparison. Our work follows the salience-basee based weight pruning approach, which evaluates the impact of removing weights the model's loss or output. Among these, methods based on second-order information are most relevant, particularly those following the Hassibi et al. 19933
framework. Dong et al. 2017] use second-order approximation of the loss function, assuming zero gradient, and introduce a layerwise strategy to approximate the Hessian. (Singh and Alistarh [222)] scale this idea with the empirical Fisher approximation of the Hessian, improving performance and considering non-zero gradients. However, WoodTayllr methods by Siighh and Alistarh (2020) focus on pruning one weight at a time, whereas our work extends this to multiple weights.
Other methods addressing multiple weight pruming include Combinatorial Brain Surgeon (CBS) Yu et al. 2022), which formulates mask selection as an integer programming problem and proposes two heuristics to approximate its solution. FFantar and Alistarh| [2022] tackle layerwise pruning with quadratic problem and introduces greedy heuristic for effcient layerwise problem-solving. Similarly, (Bebaki et al. [2023) formulate layerwise pruning as a folz-regularized quadratic problem
and propose an IHT-likee iterative algorithm with a line search strategy. AAgaasi et al. [2017] minimize
the norm of weight matrices while ensuring similar activations in the pruned layer. While prior
iterative algorithms like CHITA (Benbaki et al., 20023] focus on specific problems, our methods apply to general loss functions beyond quadratic problems and offer convergence guarantees. Practically, within our iterative framework, using a cost-effective projection step (e.g., TopK or SparseGPT Frantar and Alistarh 2023]) yields competitive results compared to more complex one-shot solvers.
3 Derivation and convergence of I-OBS
3.1. Notation. Denote [d] = 21, ... d). For given vector 0 E Rdd let supp(0) = (i E [d]: 0[v] o 0} be the support of 0, and |101|o = (0)) | be the cardinality of its support, where denotes the cardinality of set. Let fei, e,. eaf be the standard basis vectors in Rd. For a given index set Q S [d]. we define eq = Eyeq Eq. and (f)q = Σyeq f/gcey the restriction of f to Q. We denote 0 @ 0' to be the Hadamard product of vectors 0 and 6'. Finally, denote T3 the "Top-k" operator choosing the top & coordinates of the input by their magnitude and zeroing out the rest.
Next, we introduce notation for manipulating matrices by removing specific rows and columns. Given an index set Q S [d], we define the square matrix Eq E ddddd with diagonal entries (Eq)a. = 1 for i Q. and all other entries set to zero. Consequently, for matrix H E d the result of the left multiplication EgH E ddd yields matrix where only the rows with indices in Q are retained, and all other rows are set to zero. Similarly, the right multiplication HEQ e idddd keeps the columns with indices in Q untouched, and sets all other columns to zero
Analogously, for a given index set Q = {qi,... ... 9 S [d], define the rectangular matrix IQ E RiQ[xd xd as Iq T < ... T TT Hence, for matrix H E Raxd, the resulting matrix
3

---

IaH E RIQIxd is composed of the rows with indices in Q. Similarly, HIQ E R is composed of columns with indices in Q. Finally, given real symmetric matrix H Rdxd, we denote the eigenvalues of H as X (H) .... S (H)), dropping H in the notation when clear from context.
3.2. Problem setup and assumptions. We consider general optimization problem with sparsity constraints:
min f()) subject to |10||o S k. BER
where f: Rd - R is given smooth objective function of parameters 0 E Idd and k is the sparsity threshold. Finding or approximating the solution of is known to be NP-hard even for quadratics [Naaarajan 1995, Foster et al. 2015).
We make use of the following assumptions regarding the convexity and smoothness of the objective function, which are similar to those in c.g. (Peste et al. [021]:
Assumption (The existence of sparse solution). The function f() admits minimizer 0 with sparsity k- S d.
Assumption 2 (J--Strong convexity). The function f: IRd + R is differentiable and j--strongly convex for some constant μ > 0, ie., for any 0, 0' Rd it holds
(()) > 1(0' + (V)())) 0 - 0¹) ~ 0'1
Assumption ((ki k -e-Restieceedd first-order smoothness). The function f: Rd + R is twice differentiable and k-restricted L-smooth for some constant L 0, i..., for any Rd such that ||0|oo= < & it holds that:
v T 1(0) S L| for all e with sparsity ||v||o S d k.
As our approach relies on curvature information, it is common to assume Hessian smoothness, similar to the gradient smoothness Assumption 3 in first-order optimization.
Assumption 4 ((2k + k" ----sttricteed second-order smoothness). The function f: Rd + IR is twice differentiable and (2k: + k²) reestricted M-smooth for some constant M > 0, i.e., for any 0, 0' E Rd such that |0 + |10'|o I 2k + k- it holds
V f(0) v² S M|0 1l112.
(4)
where the norm for matrix A is defined as ||A||2 max| ||Ar||2 Amaxx (A A).
When the function is twice differentiable, note that the strong convexity 2 is equivalent to |V² 2. f for all 0 E Rd. Also, the (k:, d - k. -)-Restrected first-order smoothness in Assumption is weaker than L-smoothness given the function is twice differentiable, since L- B
smoothness require T (0)e < Lllulle for all v. Similarly, the (2k + k*, M)-Restricted second-order smoothness assumption is weaker than the usual p-second-order smoothness which requires (()) (0')ll) S MI10 - 0'112, 0' E Rd
3.3. IHT Proximal Point Method. Proximal Point Methods (PPMs) the backbone of many optimization procedures for solving problem (T. In each step, given the current parameters 0,, PPM defines the next iterate via
0c+1 = arg mig f(0) + 1 10 0,112. 2n
(5)
BER*
for some learning rate 17 > O. The intuition behind adding a quadratic penalty term is to ensure that the next update 0.41 is not far away from the current 0, Clearly, can consider PPM with sparsity
constraint as in (T. However, solving (5) with or without sparsity constraint is no easier than the initial problem of minimizing (().
To make this practical, we adopt a model-based viewpoint, where in each iteration we choose a (possibly stochastic) model o, that approximates the objective function f(0) in expectation, namely E (0)) R [()). For example, we might choose our model (0) = + (V)))+(V(() ( -00,) 0.)
to be the linear part of the objective; together with the sparsity constraints, we arrive at
0,41
arg min Φe (0) + 1 0.1
(6)
e: @llkkk
With this linear viewpoint, the problem 6 can be solved closed form and we get the well-known Iterative Hard Thresholding (IHT) method [Blumensath and Davies 2009).

---

Lemma 1. The closed-form solution to (6) with linear model 6:(() f(()) + (V.()))) 0²) is
Oz+1 - ()V(()))))(..).
The derivation of k-IHT is standard, and provide the proof of Lemmal in Appendix B.2 for completeness. Note that, choosing the stochastic linear model (0 = f(O.) (g(0.). 0 0,) with stochastic gradients g(O)), the update (6) reduces to stochastic IHT PPeste et al., 2021 Besides, dropping the sparsity constraints recovers the standard stochastic gradient descent (SGD).
Leveraging Second-order Information. Our intuition is that we can go beyond the standard Euclidean norm in ( used in the regularizer, penalizing the distance from the current iterate, by incorporating local curvature information via the Hessian matrix H, = V ((e,) instead of the implicit scaled identity matrix II, which treats all coordinates equally and ignores correlations. Specifically, we can write:
3.4. I-OBS:
7/.
0 = arg min (e( + 2 1/100 0
0:110||o<k
Thus, in each iteration, we minimize the second-order approximation of f(0) at 0g over the sparse non-convex domain. In turn, this leads us the proposed Iterative OBS (I-OBS) method. Dropping the constant term f(0,) of o, (0), I-OBS can be equivalently defined by
0++
arg min (V.())), 8 0₂) + 2 a 0ellit.
(8)
0:110
We now introduce our idealized algorithm, which we call the Iterative Optimal Brain Surgeon (I-OBS), corresponding to Algorithm I with Option 2. The main intuition behind the algorithm is that the computation of 0.+1 in Eqn. ( can be split into two phases: finding the optimal mask and then solving the problem with given mask. We present the pseudocode below:
Algorithm 1 Iterative Optimal Brain Surgeon (I-OBS)
1: Input: initial value 01 E Rd, sparsity threshold E [d]
2: for each step & 21, ... T do
3: Compute the gradient 9r = (O,( and the Hessian H, (g,(),),
4: Compute dense Newton's 's update 0 = 0g H,
5: Select the support/mask Q++1 of size k or d k indices S441 prune for the next iterate
6: Option (practical): Q++1 = supp Th (0,)
7: Option (theoretical): with H. == 1 (IsH,
Is. set Q++1 [d] \ Se+1 where
S = arg min s: (0T) H (0t),,
8: D Optimize the parameters over the selected support/mask Q++1
9: Option (practical): 0,+1 = (0t )q = (o,
10: Option (theoretical): 0.+1 I H. H S S.+1
0
end for
At each step of the algorithm, we first compute Newton's update 0, A, H. 9t. which might be dense in general. Next, we proceed to select the support Q++1, or equivalently, the set indices Se+1 for pruning. Unfortunately, the selection of the theoretically optimal support set Q++1 outlined in Option 2 intractable due to sparsity constraints. To address this limitation, we introduce the practical Option 1, which prioritizes parameters with the largest magnitudes.
Once the mask Q. 1 is determined, we optimize the remaining parameters to minimize loss. For Option 1, further optimization is undertaken, and the subsequent iterate 0,41 comprises just the top elements with the largest absolute value of Newton's 's update 8;- On the other hand, the theoretical Option 2 adjusts the unpruned part of of to precisely solve the sub-problem the lemma below.
as demonstrated in
Lemma 2. If H, is positive definite, then each step of Algorithm ( (Option 2) solves Eqn.
5

---

The iterative procedure Algorithm with Option 2. is fairly complex to implement in practice for large models. However, has a number of interesting theoretical properties and inspires practical extensions, which we describe in the next section. For the procedure Algorithm call it Topl-IIOBS, which we will discuss in more detail in section g
I with Option 1, we
Although it appears quite theoretical, the I-OBS algorithm is closely related to popular neural network pruning algorithms such as WoodFisher, WoodTaylor (Singh and Alistarh 2020] and OBC [Frantar and Alistarh 2022]. In particular, both WoodFissherWooodlaaylo and OBC are special cases of the I-OBS algorithm.
Connection to WoodFisher/Vood (Singh and Alistarh 2020] To recover the WoodFisher, we set V (f6) = 0 and k 1, obtaining [Singh and Alistarh 2020 equation (10) and (11))-
More specifically, in this case we have 8 0, and S {2} singleton. Hence, the matrix
H can be computed as H
(Ho ).. Thus, the criterion of choosing the optimal index to prune
e.e,
60 (Mo which recovers [Singh and Alistarh 2020 equation (11)). Also,
becomes i = arg min
the update of the remaining coordinates are computed as 01 - 0g = H e.c. 0g
HH, 'ee.
( la
(M hs
which recovers (Singh and Alistarh 2020, equation (10)). This implies that WoodFisher can be considered as running I-OBS for one step under the assumption that (f())) = O. and pruning one coordinate. Without the zero gradient assumption, we obtain the WoodTaylor method (Singh and Alistarh| 2020, Eqn. (23)). The computation is almost the same as the one for recovering WoodFisher, so we omit the details here.
Connection to OBC FFrantar and Alistarh, 2022] To recover the OBC, consider the objective function (())= = |X0 X0ol.. where X E I Rxxa and 0, 0n0 E Rd. From a practical point of view, consider X as the input of linear layer, and 0 as a row-vector of the weight matrix. Note that a special property of this problem is that the objective function is quadratic, which implies that the [gorrthmm[Joovertt
in one step. Indeed, since the objective is quadratic, for any and fg. we have f() + (0o), 0 0o) + + 10 Bo However, the difficulty is that we need to find the optimal mask, which might be infeasible in practice. The OBC method Frantar and Alistarh 2022 Algorithm 1] applies a greedy strategy. wherein it sets k = d d-1 1 in the first step. Applying the IOBS algorithm I and brute-forcing over all the masks, we find the optimal coordinate to prune. Since, in this case, we only prune one entry at a time, brute-forcing over all the masks takes ((d) steps, which feasible. Then, one applies this procedure for d h times prune the rest of the weights. Thus, the OBC method can be viewed as running I-OBS for d - k rounds, and for each round one lets the sparsity be d - 1, i.e., only pruning one entry at time.
3.5. Local convergence of I-OBS. In this section, we present the local convergence of the I-OBS method described Section 3 under the regularity Assumptions D As described in Algorithm [ it contains a gradient step preconditioned by the Hessian matrix. Thus, our I-OBS method can be viewed as a sparse variant of Newton's method. Below, we demonstrate that, perhaps surprisingly, the imposed sparsity constraint does not degrade the asymptotic local quadratic convergence rate of Newton's 's method.
Theorem 1.
Let Assumptions 7 2 3 BanddPhold. Then, for any fixed ks with k < k: S d, the I-OBS algorithm has the following local quadrafic convergence rate:
||0+1 - 1- S (1 1
/ d-
M
11,, - 11.
(9)
d-
2p
The quadratic convergence rate in the form |0z41 - 1- cl 0" 11 implies O(og log !)
iteration complexity for achieving an e-error with initialization ||0 0" ll2 S 1 This complexity matches the classical Newton's 's method up to constants. Due to space constraints, we defer the complete proof to Appendix B.4 Here, we provide a brief overview of the proof idea.
2c:
Proof sketch. We split the error 0c+1 - 6" into two parts: the standard error 0g - H. VV
0" corresponding to the Newton's method and an additional error H stemming from the sparsity. The key technical challenge of the proof is to bound the second error by the first one, which then can be bounded by the squared error 10 01 using standard tools.
-H

---

Notice that the matrix ' of the second error term is projection matrix (see Lemma 7 This observation allows bounding the error by 10, H, V (0t))l... which however, may not converge to zero as 0 is missing. To get tighter upper bound, we utilize the structure of H and the definition of gt++1 to show
0F | st
112 [10011 1l2
(10)
for any set S S [d] with | | d - ki where 07 = 02 H, V ((,)). Then, we choose the
set S to minimize the norm in the right, namely S [d] supp A With this choice of the set S we invoke Lemma and get
1g = (TT( 122 S V
d-k*
d-k 100 - 0 12-
(11)
Combining 10 and 11 together with the bound ||0²-
0- lll
110e 2y
M
0- 112 of the standard
Newton's ' method concludes the proof of our main claim in Eqn.
Discussion and Implications. Although it offers strong convergence guarantees, the vanilla version of I-OBS is hard to implement in practice. The difficulties are two-fold. First, in computing H.
we need to compute H, 1 which is the inverse of a |||] x |S] matrix, requiring ([S)))) complexity in general. Also, if [|| ed for some c E (0, 1), ie. we prune a c-fraction of weight, then the complexity of this step will be (dd). Second, to obtain the optimal set St+1, we need to solve a combinatorial problem arg ming: [ OH This problem is NP-hard [Chen et al. 2014
Natarajan 1995), and brute-forcing over all possible sets has the complexity of O(d)). If ed, then the complexity will be ((e") which is too expensive in practical applications. Thus, we propose a practical variants I-OBS which corresponds to Algorithm (Option I), namely Topk-I-OBS. We also provide local convergence guarantee for Topk-I-OBS. Besides, we also proposed another version called stochastic I-OBS in Appendix 3
3.6. A Practical Variant: Topk-OBS. As mentioned above, one natural implementation of the I-OBS
method in practice is replace the multiplication by the matrix I I- H, ' with directly applying the Top-k operator to the preconditioned gradient step. This leads to the following Topk-I-OBS update corresponding Algorithm with Option 1:
0 = (O: (V)())
(12)
For the Topk-I-OBS method, we can still show local convergence similar to Theorem 1
Lemma 3. Let Assumptions 7 and hold. Then I-OBS method defined in 12) has the following
convergence rate:
10:+1 0.112
1
k-
M 2μ
0
(13)
The proof is deferred to Appendix B.5 We remark that similar algorithms are studied for sparse linear regression problems with a linear global rate, while our Topk-I-OBS method applies to a wider class of problems, and obtains a quadratic local rate.
4
Experiments
4.1 Synthetic Experiments for Sparse Linear Regression
To validate our theoretical analysis, we first consider the sparse linear regression problem with two different priors. First, we consider sparse linear regression problem with Gaussian prior. In particular, we first sample signal 0, e Rd of dimension d = 128 from standard Gaussian prior, and then we set it to be sparse by uniformly random keeping k. = 16 entries, and set the rest to zero. Then, we generate n 256 sensing vectors X [21 22, xx E d i.i.d. from a standard Gaussian distribution with variance n and the label is generated via linear measurement = (f., (0.,2:). We aim to recover the signal by minimizing the empirical mean square loss L(0) / x0113. and set the sparsity for each step to k = 64. It is easy to see that in this case, the Hessian of the loss function is H. C(O) X X. and this matrix is with high probability positive definite.
7

---

9
g
9
3
3
(a) Learning curve with standard Gaussian prior.
(b) Recovery of the MNIST prior.
Figure 1: Comparison of k-IHT and Topk- Soons--oooTayllorr for sparse linear regression with standard
Gaussian and MNIST priors.
We compare k-IHT (Peste et al. the learning rate A We run each algorithm for 750 steps, and run 20 independent experiments then take the average over all the experiments. The synthetic experiments can be done on a personal laptop. The results are shown Figure Ta We see that the topk- WoodTaylor method compared k-IHT due the of second-order information
2021 and Topk-I-OBS
122 numerically, For k-IHT, we apply
indeed has better convergence in Newton's step. In particular, the left plot of Figure Ta characterizes the training loss, and the right plot characterizes the distance the optimal solution.
In the second setting, we let the signal be uniformly sampled from the MNIST dataset. particular, randomly sample image of MNIST training dataset and use this image the signal O.. In this case, the dimension d of the signal is 784, and we denote the sparsity of the signal as k., Next we generate = 2d 1568 sensing vectors X i.i.d from standard Gaussian distribution with variance and the label generated via a linear measurement y/ = (f., στ). Similarly, we minimize the MSE loss, and the sparsity set for each step is & 2k.. We also compare k-IHT and Topk-I-OBS numerically. We run each algorithm for 4000 steps and run 20 independent experiments. For the k-IHT, similarly, apply the maximum possible learning rate.
We show the recovered signals in Figure (The learning curve almost identical to the Gaussian case and therefore omitted.) When plotting the recovered image, only plot the value between [0, 255]. We can see from the learning curve that the Topk-I-OBS has better convergence rate, which results in better recovery quality compared to k-IHT for fixed number of steps.
4.2 Applying I-OBS to Model Pruning
In this section we describe our implementations for selecting the of weights to prune using second order information applied to practical models.
Algorithm 2 Iterative Optimal Brain Surgeon (I-OBS) for practical model pruning
1: Input: Sparsity threshold ke [d] for each layer é {1, 2........ L}
2: for each round E (1.2...., do
3: Sample data batch X,
4: D- Pruning and optimization step:
5: H - Xx
6: for each layer l 2, L. do
Solve the constrained optimization problem
minp:
-W
8.l. || = kg
using a quadratic sparsity solver such as OBC or SparseGPT.
8:
W + W
9: W t- W! not (Xe, (Xe, W for each & e L}}
end for
11: end for

---

Detailed algorithm. The algorithms we implement for pruning are described in Algorithm 2 We consider pruning an L-layer feedforward neural network f(X; W w.... Wr.) or. W W .... 01 W X, but similar pruning strategy would apply neural networks with different structure. More specifically, we consider pretrained model, and we aim to find a sparse model using the I-OBS algorithm. We apply a layer-wise pruning strategy as in OBC [Frantar and Alistarh 2022]. In particular, for each round t, we sample new data batch X,, and solve the quadratic sparse optimization problem
or
min I - W s.t. 1o k
where = W o ... o W X is the input of the f-th layer. We use the SparseGPT method [Frantar and Alistarh [022] as an approximate solver for this problem. The connection between one-shot pruners such as OBC or SparseGPT and I-OBS was discussed in Section 3
Example 1: Pruning Vision Transformers (ViTs). We now apply this approach to pruning DNNs from the ViT family (Dosovitskiy et al., 2021] For this, we instantiate the above pruning framework solver in the context of I-OBS, to prune the DeiT-Tiny (5M parameters), DeiT-Small (22M parameters) and DeiT-Base (86M parameters) models one shot to 50% uniform sparsity, starting from an accurate pretrained model, using 1000 ImageNet calibration samples. We present our results in Table where the single-iteration result is given by the one-shot algorithm, which in this instance is SparSeGPT.
for the case of the SparseGPT solver
Table Pruning results for ViTs (DeiT) using SParseGPT. We report Top-1 accuracy results on the ImageNet validation set.
Model
# iterations
D
1
10
25
50
75
100
DeiT-Tiny 72.08
62.98
63.61
64.01
64.11
64.13
64.05
DeiT-Small
79.81
76.07
76.28
76.36
76.50
76.57
76.57
DeiT-Base
81.91
80.29
80.30
80.37
80.42
80.46
80.43
The results show that I-OBS can bring consistent improvements across all three model sizes, with the largest improvements coming at the smallest model size (5M), where the performance drop relative to the dense model is most pronounced. We also observe that improvements quickly saturate the larger model sizes and with respect to increasing the number of I-OBS iterations, suggesting that the sparse solution already close to the local optimum in the case of highly-overparametrized models.
Example 2: Pruning Large Language Models (LLMs). Finally, we extend the previous approach LLMs, again comparing against SPT as a baseline. Specifically, we estimate the Hessian matrix at each layer by using 128 calibration samples from the WikiText2 dataset for 12T-125M and from Red Pajama dataset for 1.5,, respectively. We report the accuracy terms of perplexity (lower is better) on the WikiText2 and C4 datasets. In this scenario, we start from a dense model and prune it to 50% uniform sparsity, using I-OBS for iterations. (We observed that using larger number of iterations leads to "overfitting." by which we mean good PPI. on WikiTexx22 but worsening on C4.) The results are given in Table
Table 2: Pruning results for Phi-1.5M using SparseGPT. We report perplexity (the lower, the better).
Model
samples
WikiText2 SparseGPT
C4
Dense
I-OBS(3)
Dense
SparseGPT
I-OBS(3)
OPT-125M
128
27.65
33.85
25.20
24.61
32.27
31.41
Phi-1.5
128
21.82
25.28
23.94
20.90
21.13
20.26
In both cases, we observe that I-OBS leads to significant improvements in terms of perplexity, specifically of approximately one PPL point on C4, relative to SparseGPT. This effect confirms the fact that I-OBS significantly better at minimizing the per-layer compression loss relative to single iteration of SPTrseGPT.

---

We also applied our methods on Llama-2(7B) and (aama-((BB) models, and the results are discussed in Appendix A.2
Limitations and Future works
In this section, we discuss the limitation of this work, and address few directions for future work.
From the theoretical perspective, our main limitation is the mild gap between the analytical sumptions and the practical setting we considered in the pruning experiments. We mention that our assumptions standard in the literature (see e.g. (Peste al. 202T Analytical Assumptions)) to guarantee the convergence of gradient- based methods, it does not hold in general for practical problem such model pruning. Thus, one interesting direction for future work
relax those assumptions. In addition, in Theorem and Lemma 3 we only provide local convergence rate, which mean that we require the initial distance from the global optimum to be small enough. While such local convergence results are typical for Newton type algorithms (see e.g. [Nesterov] 2018 Theorem 1.2.5)), there are few modifications of the vanilla Newton's methods which gives global convergence rate such as adding cubic regularization term [Nesterov] [2018] Section 4.1] or adding a proper adaptive quadratic regularization term [Mishchenko] 2023). The challenge is how to incorporate the sparsity constrain to make each step sparse, and we leave this direction for future works. For the experiments, it would be interesting to apply the pruning method to larger models, which we plan to do future work.
Acknowledgements
The authors thank the anonymous NeurlPS reviewers for their useful comments and feedback, the IT department from the Institute of Science and Technology Austria for the hardware support, and Weights and Biases for the infrastructure to track all our experiments. Mher Safaryan has received funding from the European Union's 's Horizon 2020 research and innovation program under the Maria Sklodowska-Curie grant agreement No 101034413.
References
Alireza Aghasi, Afshin Abdi, Nam Nguyen, and Justin Romberg. Net-Trim: Convex Pruning of Deep Neural Networks with Performance Guarantee. Advances in Neural Information Processing Systems, 30, 2017.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-276. 1998.
Sohail Bahmani, Bhiksha Raj, and Petros T Boufounos. Greedy sparsity-constrained optimization. The Journal of Machine Learning Research, 14(1):807-841, 2013.
Riade Benbaki, Wenyu Chen, Xiang Meng, Hussein Hazimeh, Natalia Ponomareva, Zhe Zhao, and Rahul Mazumder. Fast chita: Neural network pruning with combinatorial optimization. In International Conference on Machine Learning, pages 2031-2049. PMLR, 2023.
Thomas Blumensath. Accelerated iterative hard thresholding. Signal Processing, 92(3):752-756. 2012.
Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Applied and Computational Harmonic Analysis, 27(3):265-274, 2009.
Jinghui Chen and Quanquan Gu. Fast newton hard thresholding pursuit for sparsity constrained nonconvex optimization. In Proceedings of the 23rd ACM SIGKDD international conference knowledge discovery and data mining, pages 757-766, 2017.
Xiaojun Chen, Dongdong Ge, Zizhuo Wang, and Yinyu Ye, Complexity of unconstrained L2 Lp minimization. Mathematical Programming, 143(1):37--383 2014.
Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. LLM.int8): 8-bit Matrix Multiplication for Transformers at Scale. Advances in Neural Information Processing Systems (NeurIPS), 2022.
10

---

Xin Dong, Shangyu Chen, and Sinno Pan. Learning to prune deep neural networks via layer-wise optimal brain surgeon. Advances in neural information processing systems, 30, 2017.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition scale, 2021.
D. Foster, H. Karloff, and J. Thaler. Variable selection is hard. Conference on Learning Theory, pages 696-709, 2015.
Elias Frantar and Dan Alistarh. Optimal brain compression: A framework for accurate post-training quantization and pruning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho. editors, , Advances in Neural Information Processing Systems, 2022. URL /
hettfoorumidd-ksoeeae VGCO1000
Elias Frantar and Dan Alistarh. SparseGPT: Massive Language Models Can be Accurately Pruned in One-Shot, International Conference on Machine Learning (ICML), 2023.
Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. OPTQ: Accurate Quantization
for Generative Pre-trained Transformers. International Conference on Learning Representations (ICLR), 2023.
Qiushan Guo, Xinjiang Wang, Yichao Wu, Zhipeng Yu, Ding Liang, Xiaolin Hu, and Ping Luo. Online knowledge distillation via collaborative learning. Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition, page 1 11020 1029, 2020.
Hrayr Harutyunyan, Ankit Singh Rawat, Aditya Krishna Menon, Seungyeon Kim, and Sanjiv Kumar. Supervision Complexity and its Role in Knowledge Distillation. International Conference on Learning Representations (ICLR), 2023.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neural information processing systems, 5, 1992.
Babak Hassibi, David Stork, and Gregory Wolff. Optimal brain surgeon: Extensions and performance comparisons. Advances in neural information processing systems, 6, 1993.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the Knowledge in a Neural Network. Deep Learning Workshop at NIPS, 2014.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. The Journal of Machine Learning Research, 22(1):10882-11 11005, 2021.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhi -hu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-Rank Adaptation of Large Language Models. International Conference Learning Representations (ICLR), 2022.
Sehoon Kim, Coleman Hooper, Amir Gholami, Zhen Dong, Xiuyu Li, Sheng Shen, Michael W. Mahoney, and Kurt Keutzer. SqueezeLLM: Sinse-and-Sparg Quantization. arXiv preprint 2.2.02.306..7622, 2023.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. In D. Touret- zky, editor, Advances in Neural Information Processing Systems, volume 2. Morgan- Kaufmann, 1989. URL http::://procceediiiiaeee hwwp:iiiiiinnnnnnnnnneueee nowr.ps.cc/ppa.rrrr wttp:pcpe..lllee//////e//e wwf.fseessserrr//re 1989/ ftle//6882bbatt//002000011226775
.dff
Vladislav Lialin, Sherin Muckatira, Namrata Shivagunde, and Anna Rumshisky. ReLoRA: High-Ran Rank Training Through Low-Rank Updates. International Conference on Learning Representations (ICLR), 2024.
Tao Lin, Sebastian U. Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic Model Pruning with Feedback. International Conference on Learning Representations (ICLR), 2020.
11

---

Nan Meng and Yun-Bin Zhao. Newton-step-base hard thresholding algorithms for sparse signal recovery. IEEE Transactions on Signal Processing. 68:6594 6606, 2020.
Konstantin Mishchenko. Regularized Newton method with global O(1/k²) convergence. SIAM
Journal on Optimization, 33(3):1440-14400 2023. doi: 10. 10.1137/22M1488752
Asit Mishra and Debbie Marr. Apprentice: Using Knowledge Distillation Techniques To Improve Low-Precision Network Accuracy. International Conference on Learning Representations (ICLR), 2018.
B. K. Natarajan. Sparse approximate solutions linear systems. SIAM Journal on Computing, 24(2): 227-234, 1995.
Yurii Nesterov. Lectures on convex optimization, volume 137. Springer, 2018.
Mahdi Nikdan, Soroush Tabesh, and Dan Alistarh. RoSA: Accurate Parameter-Efficien Fine- Tine-Tuning via Robust Adaptation. arXiv preprint arXiv:2401.0460 2024.
Alexandra Peste, Eugenia lofinova, Adrian Vladu, and Dan Alistarh. AC/DC: Alternating com-
pressed/decompresseed training of deep neural networks. Advances in Neural Information Process- ing Systems, 34:8557-8570 2021.
Antonio Polino, Razvan Pascanu, and Dan Alistarh. Model compression via distillation and quantiza- tion. International Conference Learning Representations (ICLR), 2018
Sidak Pal Singh and Dan Alistarh. WoodFisher: Efficient second-order approximation for neural network compression. Advances in Neural Information Processing Systems, 33:18098 10088-8818,,, 2020.
Joel A. Tropp and Anna C. Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53((1))4655 4666, 2007.
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie- Yan Liu, and Wei Chen.
Provable adaptivity in Adam. arXiv preprint arXiv:2208.09900 2022.
Mingxue Xu, Yao Lei Xu, and Danilo P. Mandic. TensorGPT: Efficient Compression of the Embed- ding Layer LLMs based on the Tensor-Train Decomposition. arXiv preprint arXiv:2307.00526 2023.
Zhewei Yao, Reza Yazdani Aminabadi, Minjia Zhang, Xiaoxia Wu, Conglong Li, and Yuxiong He. ZeroQuant: Efficient and Affordable Post- tra--Trainng Quantization for Large-Scale Transformers. Advances in Neural Information Processing Systems (NeurIPS), 2022.
Xin Yu, Thiago Serra, Srikumar Ramalingam, and Shandian Zhe. The combinatorial brain surgeon: pruning weights that cancel one another in neural networks. In International Conference on Machine Learning, pages 25668-25683 PMLR, 2022.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: theoretical justification for adaptivity. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. URL https wewpee/eoooonndda/neiaaaa
Yun-Bin Zhao. Sparse optimization theory and methods. CRC Press, 2018.
Shenglong Zhou, Naihua Xiu, and Hou-Duo Qi. Global and quadratic convergence of newton hard-thresholding pursuit. The Journal of Machine Learning Research, 22(1):599-643, 2021.
12

---

Contents
Introduction
Related Work
Derivation and convergence of I-OBS
4
Experiments
4.1
Synthetic Experiments for Sparse Linear Regression
4.2
Applying I-OBS to Model Pruning
5
I Limitations and Future works
10
Experimental Details
13
A.I I-OBS for Model Pruning
13
Extra experiments
14
B
Deferred Proofs
15
Stochastic 1OBSS
15
B 2
Proof of Lemmal
16
B3 Proof of Lemma
17
4
Proof of Theorem
19
B 5
Proof of Lemma
20
B.6 Proof of Lemma
Technical Lemmas
22
A
Experimental Details
In this section we provide details about the hyper- parameters that we used for both experiments described in Section 4
A.1 I-OBS for Model Pruning
Pruning ViTs. We use ViTs from the timm package that are pretrained on ImageNet using RGB images of size 224 224. We both learning rate and hessian dampening 0.01, sparsity 50% and prune the query, key, values, projection and fully connected layers for 100 iterations using batch size 128.
Pruning LLMs. We use the pretrained OPT-125m model from Meta in bftoat16 format with sequence length 2048 and prune it to 50% uniform sparsity using 3 iterations of I-OBS on batches of size 128 (calibration samples) from the WikiText2 using both learning rate and hessian dampening set to 0.01.
We use the pretrained Phi-1.5 model from Microsoft also b9loat format with sequence length 2048 and prune it to 50% uniform sparsity using 3 iterations of I-OBS batches of size 128 (calibration samples) from the Red Pajama dataset using learning rate le and hessian dampening set to 0.01.
13

---

A.2 Extra experiments
I-OBS for LLMs To study the scalability of I-OBS pruning to LLM (Large Language Models)
we consider iterative pruning followed by finetuning for Llama-2 (7B) and Llama-3 (8B) models. Specifically, apply SparseGPT [Frantar and Alistarh 2023) pruner with Hessians estimated using 8M tokens (2k sequences of length 4096 for Llama-2 and IK sequences of length 8192 for Llama-3) and use the same calibration set for finetuning P After each pruning step tune the model for 1 epoch without applying any sparsity mask, i.e. all parameters may become non-zero before some of them are projected back on next pruning iteration. We adopt Adam optimizer with learning rate of 10-s, batch size of 16 for Llama-2 and 8 for Llama-3. The dynamics of evaluation metrics for both model is shown Figures and We also evaluate the pruned model on MMLU tasks, and the results are shown in the following Table 3 and
64
Perplexity on Wildtext-2
8.4-
Perplexity C4
6.3
6.1
6.1
8.0
0.0-
5.9
7.8
2
Iteration
Iteration
Figure I-OBS dynamics for Llama-2 7B (star corresponds to best validation score). (Left) Wikitext- 2 Perplexity vs iteration. (Right) C4 Perplexity vs iteration.
Perplexit explexiiy on Wikitext-?
Perplexity C4
3.-
9.2
3.0
5.-
15
Iteration
Iteration
Figure I-OBS dynamics for Llama-3 8B (star corresponds to best validation score). (Left) Wikitext- 2 Perplexity vs iteration. (Right) C4 Perplexity vs iteration.
One observe that the quality of sparse solution significantly improves after first finetuning iteration. Then there is small improvement during the next few iterations, followed by gradual performance deterioration afterward. We speculate that this behavior is due to the overfitting the calibration set.
Comparing with CBS In Ta the attached file in global rebuttal, we provide results for I-OBS applied to MobileNetV1 model used in STR, which is the same model studied in Table 4 of (Yu ct al. 2022). We skip the depth-wise convolutions having shape (C, 1, K, K) when we apply our pruning algorithm, as is standard. Starting with 60% sparsity, our I-OBS pruner outperforms CBS method on MobileNetVI by a large margin: 2% for 60% sparsity, 5% for 70% sparsity and 12% for 80% sparsity. For low sparsities (30% to 50%), the two methods comparable, since the accuracy difference is less than 0.5%.
?Calibration data is sampled from Red Pajama dataset.
14

---

Table 3: Performance of I-OBS on Llama-2-7b
Iterations
MMLU(5-shot)
(dense)
0.4584
0.3878
0.3950
0.3932
0.3943
0.3946
0.3929
0.3919
0.3893
0.3903
0.3863
Table 4: Performance of I-OBS on Llama-3-8B
Iterations
MMLU(5-shot)
0 (dense) 0.6525
0.5476
0,5577
0,5582
0,5605
0.5553 6
0,5521
0.5444
8
0.5449
0.5403
10
0.5375
Table Comparison of I-OBS and CBS different sparsity levels
sparsity
I-OBS
CBS
30%
71.6
71.88
40%
71.3
71.45
50%
70.6
70.21
60%
68.4
66.37
70%
60.7
55.11
80%
27.9
16.38
0% (dense)
71.95%
B Deferred Proofs
B.1
Stochastic I-OBS
To enhance the computational efficiency of the I-OBS approach to large scale problems, introduce certain relaxations to approximate the full-batch gradient f(e)) and the Hessian H,-
Suppose have access stochastic gradients g()) that is unbiased estimator of the full-batch
gradient, namely [[](()) = (0). Inspired by the Fisher approximation [Amari] [998 we
over-approximate the Hessian using the outer products of stochastie gradients follows:
f() ~ AI + (O),, with G(0)
a(1)g16) [9(0)]l
(14)
where À > O and for two matrices A, B the inequality A < B means that B - A is positive semi- definite. Compared to the Fisher approximation we scaled the second term inside the expectation by divided with the norm [[g(0)]|2 avoid scaling issues. Since the stochastic matrix composed of outer
15

---

product inside the expectation is positive semi-definite, the condition 14) holds automatically under L-smoothness assumption with L.
For example, we use full-batch gradient g(0) = V f()), then the matrix [[) is of rank In this case should be the largest eigenvalue Amax (H,) of the Hessian. However, when batch size of g(0) is smaller, then the expectation of stochastic rank-1 matrices G(0) would potentially be of full-rank, allowing us choose smaller value for A.
An alternative motivation behind condition (14) is given by empirical observations on the corre- lation between loss smoothness and gradient norm [Zhang al. 2020 Wang al. [0022]. Since Amax G = Ilg( [2) and | f())
I E (
condition (14) can be viewed as matrix version
of (Lo, L1) )- -smothhesss condition by Zhang et al. 2020
V f(0)1l2 Lo L1 L
(15)
allowing the smoothness to grow with the gradient norm.
Applying the condition (14). we can over-approximate the quadratic objective of 7 by (l)))
0.) (s(0.).0-0.)
211g(0=)1lz + 2100 lell The stochastic quadratic problem of the latter objective can be solved analytically we specify the sparsity constraint.
Lemma 4. With fixed sparsity constraint Ig0 the stochastic quadratic problem
arg min (9(0.), 0 0.) + (g((e)), 0 - 0,) 01.6-0
+ 110 0,11
2]g((,))
has the following solution for the update
oct1 = EQ (0. x+ 04
where the mask Q is the complement of S.
In general, the closed form solution for the mask Q not tractable. For this reason, we propose the following stochastic version of I-OBS:
0G+1 = Ta (0, X+ 3
with Q' = 0
B.2 Proof of Lemma
Lemma 1. The closed-form solution to (6) with linear model (e( f(0.) + (Vf(e)) 0₂) is
0 To( f(.)).
Proof of Lemmal 7
Plugging the linear model (0) f(0.) + (V,(),), - 0,) into the problem (6) and dropping the constant term (0.) in the arg min, we get the following problem:
1
arg min 0: @1
(V 0,) + 2n
11112
(16)
We break this problem into two sub- aub-leoblems: first solve the problem with fixed sparsity mask. then optimize over the mask. Formally, for given mask Q C [d] with cardinality |Q] = k, we solve
0
arg min (VS(0.). 0 0.) 0:1e==0
1 110 0.113
(17)
2n
where S [d] is the complement of the mask, i.e., the coordinates that we want drop. Afterwards, we find the optimal mast Q*+1 by solving
1 1000 0ell2
Q-1
arg min
(V)(0), 01) + 2n Q: =
(18)
Then, the solution to 16 would be 0,41 02
16

---

Let us start solving the first sub- cetb-problemii in [7 As the problem is convex (convex quadratic objective with linear constraints), we can solve it with the method of Lagrange multipliers. With a modified primal variable
0₂ E Id and dual variable À E R (s the Lagrangian takes the form
1 21j 1111
L A) - (VS(0),)) +
(Is + 0.)).
Applying Karush
(KKT) conditions to our problem yiclds
0 VoI(o", v.((,) + 6" + I
Vxl(ō", X*) = I5 + 02)- Solving the first equation for 8 variable, we get 0= nn( / (0.) + 1*) Plugging this into the second equation gives
0= I=(- + +1 + 0.) = Is v)(() - X
Noticing that I is the identity matrix R|S|||S| and Is = Es, we conclude
x 1 Is(0, -
7
8" = ((.)) Es(0: 1 (V)()),
which implies that the solution to first sup-problem (17) be given
0 6" + 0
0 V, f (0.) - Es(O, f),)(
= (I (8; - f(E)) = Eq(0: VV f(e)).
To solve the second sub problem 18) we plug in the obtained solution 0 and simplify the objective function as follows:
V (V,())) 02 0e)
110
0e113
1
(110))
0, + +/ (112----1-107700055-1777771111
2n
2m)
1
- (e) - f
[I
2m)
1
Es
7V 2 |()())))
2n
Recall that we need to minimize the obtained expression with respect to the mask Q, or equivalently its complement S. As the second term, - f does not depend on the mask, we can ignore it. To minimize the first term, [6, - (O,))) we need to choose the projection set S corresponding to the coordinates of the vector 0, 1/ (O+) with minimal absolute values. In other words, the mask Q should be chosen to be the coordinates corresponding to the largest magnitudes of the vector, namely Q++1 supp (Ty (f: f(.)).
Thus, combining the solutions of these two problems we conclude that 0,+1 = (O.
B.3 Proof of Lemma
Lemma 2. H, is positive definite, then each step of Algorithm [ (Option 2) solves Eqn.
Proof of Lemma 2 To solve the optimization problem in First, we fix subset Q S [d] with size k and complement S [d] Q, then we find the optimal set Q
we break this problem into two parts.
(or equivalently S). The first step is solve the following quadratic optimization problem:
++1 = arg min (V)(0)), 0z) + 2
(0 0., H. 0,)),
(19)
0:10==
17

---

Next, we aim to find the optimal set to prune, which is given by
Stt min (V](()),
1+1 O²) + 100 1+1 0r. H. 1+1 - 01)).
(20)
S: |S|=d-k
Once we solve both the problems
19 and 20 set 01t1 =i++1
To solve [1)]. notice that the optimization problem is convex with S linear equality constraints. Therefore we can solve it via KKT conditions. With change of variable å = 0 0r E IR, we define the Lagrangian with multipliers À E 1215| as follows:
L(ō, A) = (V.())), 6) + (6, H,0) + (02 + 5,,1
2
Then the KKT conditions become
0 = VsL(0", ( + H2O + +I VxL(6", ) Is(8 + 0z).
Note that the matrix H. invertible since it is positive definite. From the first equation we obtain that 8" H, (V (0.) Then, plugging this into the second equation, we get (IsHH I ) (s( H ((.)).. Note that IsH, Ig basically the matrix H removing the rows and columns outside S.
Next, we claim that the matrix IsH, 'In is also positive definite. Indeed, by the interlacing property in Lemma 9 we have:
1 (H, S (H, S A (IsH,
which implies that all eigenvalues of Ig 'IJ are positive, hence it is also invertibility. Therefore, we get
X (IsH, (s H. ((.))) =: Ar.s
(21)
8" #H- - H.H 1 =: 6,,5.
(22)
Finally, we have the following update rule for I-OBS:
0 = 0₂ + 8 = (I- HI, H - (H, (.()))
(23)
where H. I (IsH, [ -1 Ig that is, we let:
- E Raxd, Next, we should pick the optimal S St+1 via 20)
VV(0)),0 0+ 01) + 1 10 Oz, (O 0z))
St-1 arg min
2
Plugging the expression not depend on S, we have
23 of 0 into the above definition of st+1, and ignoring terms that do
1
st+1
arg min (V.(e,), 05 - 0,) +
(05 0,, H, 0.))
8: =d
2
arg min (V)(0,), 02-)) + 22 8: =Sk=
1
(05
10+1 H,O (140 - (0,, H,OSm1
(H,05 1+1 H. f((.)) + 1 100 H,O
arg arg dSk
arg argmin min =S]=d=
(HH, H (0. H. (v) 0. (v)))(
arg min (0, H. v. ( (0: H. vf())))
(24)
=d
Finally, setting 0,41 0551 finishes the proof.
18

---

B.4 Proof of Theorem
1
We first recall Theorem below:
Theorem 1, Let Assumptions 7 2 and 4 hold.
hold. Then, for any fixed with k- S k S d, the I-OBS
algorithm has the following local quadratic convergence rate:
|0:+1 - 0 (1
L d- 10 0
(9)
Proof of Theorem
1 From the update rule, is easy to see that:
O2t1 0" 0. H 0" H (O.-H,'V((0))
s**1
For simplicity, we define Q" supp(("), Q' (.)) and recall that by definition, we have
gt+1=
arg min
(0)- - H H (0. ((
SC14,
arg min (0. - (1s - S|
Then we have
10+11
st* (0. (0 (e-H.'VS(00)) 1l2. la S 11.c V.(0) - 0-112 + || H
Next we want control
H HH (0-
((0))) (V-HH) ll2 term above. For simplicity, we define
8t = 8 - f(0.).
H H
SM 11
g+
2
= (8+) H H, H 1112
(0+)T (H)))))))
1/2 H, (H, s " 11/2 (HH(HH, (H&5*)))1200 1120
(HI H (H: )122 (0+) "1:""'0 g+
Amax
Amax
H H g11
H
(o+) H 11 a+
H ot+1 H (0+) H 0 0+
Amax
H,
H H.ll (0+) H 0+
where we used the fact that matrices AB and BA have the same nonzero eigenvalues counting multiplicity, and for any symmetric and positive semi-definite matrix A it holds ||]|| = Amax (A).
The norm H, H sh H ||2 can be bounded by splitting it into two matrix operations by invoking Lemma 7 and strong convexity Assumption 2
H.
H.
<
H. H
H
112
S
Furthermore, based on 24 we have (0+) H gt s (0+) for any set Š of the same
cardinality s1+1, Noticing that I Eg S. we get
(0 0 = (Eg0+)
) (EsO+)
(Egot)
H /2 H 1/2 H H 1/2 H/2 1/2 (EgOt)
Amax
H, 1/2 H 1/2
E 1.g0
H, (Eg0*)
Amax
H (Eg0
H (EsO+)
- L Eg
| L |
19

---

where we used the fact that H,' is projection matrix (Lemma and restricted first-order smoothness condition (Assumption Then, choosing S arg [ || 11 and using
Lemma 8 we have that:
[g(O - (H
= 1T H V((O) (0. ((
d bt
S
100 H V -1
d k
Hence, combining these bounds we arrive
H 3 (0: - H H,,)) ll S
Ld- k p d d 10 H ((0))) - 0" 1|2.
And the rest follows from the standard proof of Newton's methods, see e.g. Nesterov 2018 pg. 38-39]. We redo the proof here for completeness:
[// v21( + T((. -0)) - 80) dr
10: (() - 12 - 02 0 -H,²
H S'" (v2 v25 + 7(0 0*))) (0. 0*) dr
< H 112 1'" (v2)(0))- - v2 100 + 7(, 02))) dr 1 0/11
00 !. dr 11, 11
M
10: 12.
2p
Finally, combining this with the previous bounds we get
|10.4.
12 x 110, H, (.(()
8* ||2 + H H.a (0, H, ' f(.)) ll2
L d k
1n
1+
110 H, V 82112
11 d k
Ld - k+
M
1
1 1-1
1 d d- k
2p
which concludes the proof of Theorem T
B.5 Proof of Lemma 3
Lemma 3. Let Assumptions 1 and 4 hold. Then I-OBS method defined in
12 has the following
convergence rate:
10++1 0,112 S
1
M 2z
00
0 1
(13)
Proof of Lemma 3 Similar to the proof of Theorem 1 Notice that by definition
we define Q' = =uupp((t)) Q- = -uup(("))
Bct1 = Ti( - H. (V((e))
Equ (0, - (v(())...
(25)
Then we have that
10++1
8-112
|E (0+41 8*) |E (Ta: - H, 1 ((())) - 8-)
< E (Th H,'' - Equiuq (0, H (((()))
+ [E (0, - H. - -8')
(26)
20

---

We further upper bound the second term by dropping the projection matrix EQuHiQ For the first term, 25 implies
EQ (x H; vf())) = T. (Eor-too (0: - H. VV(()))
Hence, the first term can be upper bounded by Lemma 8
EQr+iug- (Tx (V((,) Equ+iUo (0, - - (T.'v((()))) ((::))
[Th (EQultU- (8: - H (v.())) EQuiee (0: H (
k*
s [E (0g H (V(()) 8*
k k*
S 110, H. (0,) 1
k
Using the obtained bounds, (26) implies
10++1 - 0- <
(1+
100 H - 00112-
The rest follows from standard analysis of Newton's methods showing that
M
||0 - H, f(,)) 00 -
00 112.
2μ
B.6
Proof of Lemma
Lemma 4, With fixed sparsity construint Is0 = 0, the stochastic quadratic problem
arg min (g(0.), 0.) + (g(())) 0
B,)1
+ 2 110 0,11
(l(g(0:) la
has the following solution for the update
0++1 = Eq (0i- 10
where the mask Q is the complement of S.
Due to the convexity of the quadratic objective and linearity of constraints, we solve the problem with KKT conditions. The Lagrangian with multipliers & E TR|S| will be
Proof of Lemma 4
I(O,E) = ( 0.) (g(0,) 0,1
2 2 0.113 E I
A
(27)
2l(g(0:)
Taking the gradient with respect each variable and & separately, have
= VoL(O, = g((.) + ((.))
1l9(6.) + +AI) (0 0²) + I5e
VeC(O,E) = Is0
Multiplying the first equation by Is, we solve for E:
= Is ((().) + ((,))))(0,) 119(0:)1l2
+ AI) (0 0z)
21

---

Then we plug it back in the first equation
((0.))(00))
AI (0 - 0.) I ((0,)) + (9l0))9(0)) =1) (0 0::)
= g0()))++
11g(01)]l2 + 21
lg((0))l2
-(-EEs) Es) g((,) + g((,)) [((0))((0)T
+ x1) (0 - 0,)
(19(6:)
Ee (o(O)) (1+ ((o)) (0- - 0z)
+ X(O 0.)
(28)
(0:(2))l2
From this and the fact that supp(0) C Q (since IsO implies that:
8: EQ 8t) -n,og((())
(29)
for some scalar value n. remains to derive the expression for 7,, which can be done by plugging the obtained expression for 0 - 0, = -n)Eggg (0x) into (88 and solving for the parameter 1).
0 = Eo g(Ob) (1+ g(0,) 02)
+ A(0 0.)
(1,(2,)l1
g(0)) (0 0z)
(0g(
XE 0.)
(0.g0.)
9(0)) E0)(
Eog(O:)
n)E2g(01)
(1)()))l 2
Eng(8 (0.)
Egg(0:)
(0.)0)))l
A [Bor(())) (lo))
The update rule (29 with the obtained expression of completes the proof.
C Technical Lemmas
Lemma 5. Given p-strongly convex and L-smooth function f, with the unique global minimizer 6*, we have the following properties:
1. f satisfy u-PL inequality, namely for any A:
[V)01 Z 2p( -
2. f is 'almost' are quadratic function, for any 0:
~/ - 0 - f(0) f(00))--((0))) f(00) < 2 110 0-
Lemma 6. Given a twice differentiable function f .Rdd TR, assume I satisfy assumplions 2 then we have the following properties:
1. = 42 exists and is positive definite for any 0.
2. Given S E [d] with |S] k for any d, given any a 0, then H IsH- positive definite, with:
- S s .... Au ( 5p
Proof. The first argument is directly from the strong convexity assumption.
For the second argument, the upper bound directly follows from the strong convexity assumption and Lemma 9 Indeed, we have:
> (H)) < A ")= (H)
22

---

Next, we show that A ( 2 L under assumption
Denote o1...., Uu the eigenvectors
corresponding to \1 (H)...., Aa(H), and let 1|0l122 = 1, vi E [d] w.l.ogg. Given any vector u E TR such that ||u||2 we have that:
H = (IS H (Ig u) Σ
X (H)
((Isu) u
==1
Note that Σラ ((1) u) T u,)² = ||ul12 1, and the function g(x) xa is convex for > Thus we have:
u H Σ
(H)
((T
i=1
{:(H) u) T
==1 ( H ()) x))
where the first inequality is due to Jensen's inequality, and the last inequality follows from assumption The lower bound also implies that H is positive definite.
Lemma 7. For any set S, we have |H, HH < 1.
Proof. Using the definition of H.S. we can see that the matrix P P= HH projection matrix (i.e., p2 P) with eigenvalues 0 1. Hence, ||Px|| S ||^||| for any vector Rd.
Lemma 8 (Property of top-k operator). (Peste et al. 2021 Lemma 1] Let be vectors with sparsity parameters ki and h. respectively such that by Ry. Then, for any le E [kv, ku] we have:
hin k k k
||T (u) u1
| m1...
Proof of Lemma 8 We reprove the lemma here for completeness. The case ky trivially holds, so let assume that ku. Notice that the ratio
[T u
k
representing the average of squared coordinates is monotonically decreasing as we increase Hence,
Th (u) ky
ul12
|KT., (u) ul13
(30)
ki ko
remains notice that, Th. (u) the closest -y-sparse vector to u with respect norm, namely [[Zk, (u) - w/12 < ||e u/12. Plugging this inequality in (30) we conclude the lemma.
Lemma 9 (Interlacing property). (Horn and Johnson
2012
Theorem 4.3.28 restated] Consider a < (H). Given S C [d], have the
symmetric matrix H E gaxd, with eigenvalues (H
following properties eigenvalue of matrix II
(HH) S (A(SHHI)))) (H) Vi 1,... |S|
23

---

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: Claims made in the abstract and introduction are reflecting the contributions we report in the theoretical results in Section 3 and the experimental results in Section 4
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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 as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please Section for the discussion.
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 a separate "Limitations" section 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 on 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]

---

Justification:
The assumptions are provided in Assumptions 1 and are referred both in the theorems and the proofs once they are needed.
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 or referenced in the statement of any theorems.
The proof's 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: [Yes]
Justification: Please Section and Appendix A for the experimental details.
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?
25

---

Answer: [Yes]
Justification: Please check the supplementary material for the code
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips.com wttpcccpppbccccceec guwde//ddeeeeee Cooeeoooddesssseeeeeee http:p/l//laaddeeeeeeeeeeaaassss
ssioiilicy 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We provide all the experiments details in section and Appendix A including all the training and pruning hyperparameters, the models, and the exact algorithm use.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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: [Yes]
Justification: Error bars are reported for Figure
Ta
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are 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 (e.g., Normally distributed errors).
26

---

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 figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain 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 to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
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 (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:///aaaappppcoooooooccccaaaa
Answer: [Yes]
Justification: We confirm that the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a 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: This paper contributes to the advancement of the field of Machine Learning. While it does not directly engage with applications and potential impacts of machine learning. we acknowledge that there might be potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Guidelines:
The answer NA means that there is 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.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no 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 to 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. Licenses for existing assets
Question: 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?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.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 package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
28

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset 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. Crowdsoureing 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:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS Code of Ethics, 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 equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 NeurIPS 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.
29


Reviews:
[{"review_id": "9PxtGoUEKn", "reviewer": "Reviewer_JoZw", "summary": "Having clarified my concerns in their rebuttal, I have updated my score for acceptance.\n----\nThis paper presents a variant of the classic Optimal Brain Surgeon (OBS) method to iteratively prune multiple weights of a neural network at once, with each step consisting of obtaining a pruning mask for the fraction of weights to be removed and then updating the remaining weights. The update step is framed as a sparse recovery problem to be solved using second-order methods based on the Hessian of the loss function. Two approaches are proposed for the selection of weights to prune as well as for the update of the remaining weights, with one having stronger guarantees and the other being more manageable in practice.", "questions": "1) Can you please address the overlap with CBS?\n\n2) Can you please frame your contribution over a broader range of recent work on network pruning, besides the four papers that you cited?\n\n3) Can you please discuss the connection with sparse recovery in more detail, and also the relevance of this connection if having a quadratic objective function as in I-OBS leads to an optimization problem that can solved in closed-form?\n\n4) Can you please benchmark your approach with at least magnitude pruning and CBS?\n\n5) If possible, can you please provide results with higher amounts of sparsity?", "limitations": "The authors did a reasonable work discussing limitations and what should be done in future work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "In my opinion, the core contribution here is the idea of iteratively changing the pruning mask and updating the remaining weights, which implies that the decision about which weights to prune is revisited at every step. This is a subtle departure from how this is typically done with post-training pruning (i.e., prune once, update once; or prune a smaller amount, update, and then repeat by pruning more).\n\nMoreover, I appreciate that the authors discuss the two steps by providing methods that either have better guarantees (Option 1) or that are more tractable in practice (Option 2).\n\nThe connection with sparse recovery is also very interesting, although I wished it was made more explicit. After one paragraph in Section 2, this connection is leveraged for their algorithm but the authors do not provide greater insight on the algorithms used in sparse recovering.", "weaknesses": "The authors imply that their work is the first generalization of OBS for simultaneously pruning multiple weights. However, this was already explored before in an ICML 2022 paper as the Combinatorial Brain Surgeon (CBS) [1]. In that paper, the method is also broken down in two steps, the first step selecting which weights to prune (CBS-S), which is equivalent to selecting the support mask in I-OBS, and the second step determining how to update the remaining weights (CBS-U), which is equivalent to optimizing the parameters in I-OBS. Because of the intractability of the problem, CBS-S is also approached in a greedy way, similar to Top$k$ in I-OBS. The main difference would be that CBS-S uses a semi-greedy heuristic to vary the selection of weights, whereas I-OBS updates the weights after fixing a mask and consequently affects which weights would be chosen by the greedy selection in the next iteration.\n\n[1] https://arxiv.org/abs/2203.04466\n\nMore generally, the authors only cite fours papers about network pruning in the last decade in their literature review, one of those being a survey and another two being from a same group. For the rest of the paper, they just refer back to these two papers from the same group as the state-of-the-art and do not benchmark with anything else. There has been several papers focused on OBS in the last decade, both before and following [1]. Moreover, there are other pruning methodologies with theoretical guarantees, such as those based on coresets.\n\nThe connection with sparse recovery is quite interesting, but it generalizes the algorithm much more than it would be need for OBS. Because the objective function is quadratic, my understanding is that the weights has a closed-form solution (see discussion in the WoodFisher paper, in [1] regarding CBS-U, and also in lines 211-212 of I-OBS).\n\nFinally, the authors only present results for sparsity 50%, which is not a lot of pruning in practice. For that amount of pruning, magnitude pruning (preserving the half of the weights with largest absolute value) is competitive with more refined techniques, such as WoodFisher and CBS. Because the weight selection done by the authors with Top$k$ is basically magnitude pruning, the results do not provide evidence of the strength of the technique. The technique may be strong, but that needs to be shown in more detail.\n\nOther minor comments about the writing:\n\n6-7: \"lack a solid theoretical understanding\": this is a bold statement, perhaps a bit unfair, and I don't think that the theory provided in the paper addresses exactly that (you just prove convergence rates for an update based on an optimization algorithm)\n\nEquations 7 and 8: What is $H_t$ used as a subindex?\n\n201: \"critierion\" -> criterion\n\n201: \"[,] which recovers\"\n\n210: $X$ not in bold as in previous uses\n\n215: \"in the first step one\": remove one?\n\n216 and 217: it is not \"bruteforcing\" if what you are doing takes linear time; bruteforcing is solving an entire problem by exhaustion\n\n222: \"As observed Algorithm 1\": please rewrite\n\n251, 278, 304-305, 311, 346: these references should have been in parantheses rather than having the authors names mentioned in the sentence without proper wording for it\n\n256: \"call[ed]\"\n\n269: \"the[o]retical\"\n\n282: remove comma before \"due\"\n\n285: remove \"to\"\n\nAlgorithm 2, line 1: remove first \"for each layer\" and remove comma\n\n339: \"guarentee\" -> guarantee\n\n340: \"mode[l] pruning\"?\n\n341: \"those assumption\": either use \"this\" or use \"assumptions\"\n\n342: \"is\" -> to be", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed reviews, as well as the insightful comments and questions. We address your comments and questions below \n\n**Q1**. CBS assumes the model gradient is zero for post-training pruning, while I-OBS does not, making I-OBS more general. We retain the gradient term because models may not be fully trained and subsequent I-OBS iterations can increase gradient norms for sparsity. Additionally, I-OBS is an iterative algorithm, in contrast to CBS's one-shot approach, allowing CBS-S to be used as a projection step in our iterative process by taking the gradient term into consideration.\n \nThe objectives for selecting the masks are also different. Specifically, in the IQP formulation of CBS-S procedure for mask selection, the remaining weights and their further updates are ignored. This means that the updates of the unpruned weights are not considered during the mask selection procedure. Consequently, solving each subproblem (CBS-S and CBS-U) to optimality does not guarantee optimal solution to CBS.\n \nIn the theoretical I-OBS algorithm, masks and weight updates are solved jointly, as stated in Lemma 2. Optimization in equation (8) handles both new weights and masks. Although the practical I-OBS algorithm first selects a mask and then updates weights (similar to CBS-U), it optimally finds the mask by solving an Integer Programming (IP) problem, unlike CBS-S's IQP. This makes I-OBS mask selection optimal but computationally challenging, so the practical version uses a top-k mask for efficiency, maintaining the same local convergence rate in strongly convex cases.\n\n**Q2.** We will discuss more literature review over broader range of model pruning:\nOur work follows the salience-based weight pruning approach, which evaluates the impact of removing weights on the model's loss or output. Among these, methods based on second-order information are most relevant, particularly those following the [OBS] framework. [L-OBS] uses a second-order approximation of the loss function, assuming a zero gradient, and introduces a layerwise strategy to approximate the Hessian. [WoodFisher] scales this idea with the empirical Fisher approximation of the Hessian, improving performance and considering non-zero gradients. However, WoodTaylor methods in [WoodFisher] focus on pruning one weight at a time, whereas our work extends this to multiple weights. \n\nOther methods addressing multiple weight pruning include [CBS], which formulates mask selection as an integer programming problem and proposes two heuristics to approximate its solution. [OBC] tackles layerwise pruning with a quadratic problem and introduces a greedy heuristic for efficient layerwise problem-solving. Similarly, [CHITA] formulates layerwise pruning as an $L0L2$-regularized quadratic problem and proposes an IHT-like iterative algorithm with a line search strategy. [Net-trim] minimizes the $L1$​ norm of weight matrices while ensuring similar activations in the pruned layer. While prior iterative algorithms like [CHITA] focus on specific problems, our methods apply to general loss functions beyond quadratic problems and offer convergence guarantees. Practically, within our iterative framework, using a cost-effective projection step (e.g., TopK or SparseGPT) yields competitive results compared to more complex one-shot solvers.\n\n**Q3.** We consider sparse optimization problems, aiming to find the sparse solution $\\theta_*$ for an objective function $f(\\theta)$ with a $k^*$-sparse global optimum $\\theta_*$. This includes the classic sparse recovery problem: recovering a $k$-sparse signal $\\theta_*$ from a noisy observation $A \\theta_* + \\epsilon$ with a sensing matrix $A$.\nI-OBS is a sparse optimization algorithm for sparse recovery. Besides finding $\\theta_*$, it ensures each iteration's weights are $k$-sparse (with $k \\ge k^*$), guaranteeing a $k$-sparse solution even if $\\theta_*$ is not found. Such type of algorithms are known as proper learners in sparse recovery. Both theoretical and practical versions of I-OBS are sparse optimization algorithms resembling sparse Newton's methods. Similar first-order algorithms are studied in [AC/DC], but I-OBS leverages second-order information to potentially speed up convergence (both I-OBS versions achieve super-exponential local convergence rates).\n\nFor quadratic objectives, consider two settings: strongly convex (Hessian is positive definite) and convex (Hessian is positive semi-definite but not positive definite).\nStrongly convex: The theoretical I-OBS solves the problem in one step as the second-order approximation equals the function itself. The challenge is efficiently computing the optimal mask. The practical I-OBS doesn't converge in one step but shows super-exponential local convergence.\nConvex: I-OBS cannot be directly applied due to the non-invertible Hessian, similar to issues in Newton's method for convex optimization. Adding a small L2 regularization can address invertibility but complicates obtaining a convergence rate, as the global optimum is no longer sparse. This is left for future work.\n\n**Q4 and Q5.**  Thank you for the suggestion.  In Table 3 of the attached file in global rebuttal, we provide results for I-OBS applied to MobileNetV1 model used in STR, which is the same model studied in Table 4 of the CBS paper. We skip the depth-wise convolutions having shape $(C, 1, K, K)$ when we apply our pruning algorithm, as is standard. Starting with 60\\% sparsity, our I-OBS pruner outperforms CBS method on MobileNetV1 by a large margin: 2\\% for 60\\% sparsity, 5\\% for 70\\% sparsity and 12\\% for 80\\% sparsity. For low sparsities (30\\% to 50\\%), the two methods are comparable, since the accuracy difference is less than 0.5\\%.", "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": "4iKin2RGDQ", "reviewer": "Reviewer_Dt8W", "summary": "The paper presents a new family of algorithms called Iterative Optimal Brain Surgeon (I-OBS), extending the post-training Optimal Brain Surgeon (OBS) framework to an iterative setting commonly used in sparse recovery. I-OBS algorithms utilize second-order information during the sparse projection step, enhancing convergence guarantees compared to classic algorithms like Iterative Hard Thresholding (IHT).\n\nContributions of the paper:\n\n* Introduction of I-OBS, which improves classic IHT-based algorithms by incorporating approximate second-order information in the sparse projection step.\n\n* Provision of faster analytical convergence rates for I-OBS under standard first- and second-order smoothness and strong convexity assumptions. It also offers theoretical guarantees for existing practical pruning algorithms such as WoodFisher and OBC.\n\n* Development of practical versions of the I-OBS algorithms that relax theoretical constraints, making them easy to implement and scalable for large problem instances, such as compressing vision and language models.", "questions": "* How does the algorithm using second-order information compare with one using first-order information?\n\n* Can you provide experiments comparing training time in the pruning process among the proposed method and existing works?\n\n* How does the proposed algorithm apply to the Convolution network?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper introduces an algorithm with theoretical guarantees that its predecessors do not provide.\n\n* It also offers a practical computational algorithm that approximates the theoretical one.\n\n* The paper shows the benefit of the proposed algorithm in training sparse linear regression.\n\n* The paper shows empirically that the proposed algorithm is applicable to prune large models in experiments and obtain promising results.", "weaknesses": "* The paper does not analyze the differences between the practical version of the algorithm and the theoretical one.\n\n* Since the algorithm uses second-order information, it may have time complexity issues.\n\n* The paper only compares the proposed method with SparseGPT. Hence, other existing methods for pruning can be also added.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable questions and comments, we address the questions and comments below:\n\n**W1. The difference between the practical and theoretical version of the algorithm**\nWe compare the practical and theoretical version of Algorithm 1 below:\n(1) The way of choosing the mask is different: For the theoretical version of the algorithm, we choose the mask in an optimal way, which is equivalent to solving the integer programming problem in Line 7 of Algorithm 1; for the practical version, we simply use the top-k mask to replace the optimal mask\n(2) The complexity of the two versions is different. For the theoretical one, solving the integer programming problem in Line 7 of Algorithm 1 is NP-hard; while for the practical version, computing a top-k mask only has $O(d)$ complexity\n(3) The local convergence rate of the two algorithms is the same: in both case we obtain a local convergence in the form of $||\\theta\\_{t+1} - \\theta^*||\\_2 \\leq C||\\theta\\_t - \\theta^*||\\_2^2$ implies a $\\mathcal{O}(\\log \\log(1/\\epsilon))$ iteration complexity for achieving an $\\epsilon$-error with initialization $||\\theta\\_0 - \\theta^*||\\_2 \\leq \\frac{1}{2C}$.\n\n**W2. The complexity issue by using second-order information**\nWhile second-order information is historically hard to apply at the scale of deep networks, notice that there have recently been several efficient variants that work in linear time and space (in the model dimension) and can therefore be scaled. Specifically, we apply the recent scalable M-FAC method [M-FAC] to approximate the inverse of the Hessian.\n\n**W3. Comparing I-OBS with other existing methods**\n\n We provide extra experiments that compare our methods with [CBS].  In Table 3 of the attached file in global rebuttal, we provide results for I-OBS applied to MobileNetV1 model used in STR. Our experiment results implies that: starting with 60\\% sparsity, our I-OBS pruner outperforms CBS method on MobileNetV1 by a large margin: 2\\% for 60\\% sparsity, 5\\% for 70\\% sparsity and 12\\% for 80\\% sparsity. For low sparsities (30\\% to 50\\%), the two methods are comparable, since the accuracy difference is less than 0.5\\%\n\n\n**Q1. How does the algorithm using second-order information compare with one using first-order information?**\n\nIn I-OBS, we solve a sparse optimization problem at each step with the objective function being the second-order approximation of the loss function, in particular, we have $\\theta\\_{t+1} = \\arg \\min_{\\theta: ||\\theta||\\_0 \\le k} \\; \\phi\\_t(\\theta) + \\tfrac{1}{2}||\\theta-\\theta\\_t||^2_{H_t}$. The Hessian of the objective funcion appears in the $\\tfrac{1}{2}||\\theta-\\theta\\_t||^2\\_{H\\_t}$ term. While in the first-order method such as k-IHt studied in [AC/DC], the algorithm solves a sparse optimization problem at each step with the objective function being the first-order approximation of the loss function, in particular $\\theta\\_{t+1} = \\arg \\min\\_{\\theta: ||\\theta||\\_0\\le k} \\; \\phi\\_t(\\theta) + \\tfrac{1}{2\\eta}||\\theta-\\theta\\_t||^2$, the Hessian is replaced by a quadratic term. \n\nRegarding the convergence rate, typical first-order methods such as k-IHt studied in [AC/DC] have achieved $\\epsilon$-error in $O(\\log \\frac{1}{\\epsilon})$ iterations for any initialization. The I-OBS proposed in this paper, achieved $\\epsilon$-error in $O(\\log\\log \\frac{1}{\\epsilon})$ iterations with initialization $||\\theta\\_0 - \\theta^*||\\_2 \\leq \\frac{1}{2 C}$. In short, I-OBS have a faster local convergence rate but we are unable to provide a global convergence rate. The difference resembles the one between gradient descent and Newton's methods. \n\n**Q2 Comparing training time in the pruning process among the proposed method and existing works**\n\nThank you for the suggestion. However, it is a bit difficult to directly compare the pruning time since it depends on the implementation of the algorithms and the device. We need to adapt the implementation of methods in other existing works on our device, which is a bit time-consuming. We report the pruning time of our methods below:\n\nFor the experiments on ViTs (Table 1 in the paper), it took about 4 hours for running 100 iterations and the hardware we used was Nvidia A100 GPU with 80GB memory. For LLMs experiments, as suggested by reviewer T9TW,  we ran I-OBS on Llama-2 (7B) and Llama-3 (8B) models, and it takes around 1.5 hours per iteration (15h for 10 iterations). Unfortunately, we haven't recorded the time of running the experiments on OPT-125M and Phi-1.5 models (Table 2 in the paper). \n\n**Q3 Whether the proposed algorithm applies to CNNs**\n\nThe proposed methods indeed apply to CNNs. In Algorithm 2, we use OBC as the quadratic sparse solver for the problem defined in line 7 of Algorithm 2, and OBC applies to convolution layers. In fact, the experiments we are doing to baseline our methods with CBS are on MobileNet_v1, and we find I-OBS improves the performance of CBS on pruning MobileNet_v1. \n\n\n**References**\n\n[M-FAC] Frantar, Elias, Eldar Kurtic, and Dan Alistarh. \"M-fac: Efficient matrix-free approximations of second-order information.\" Neurips 2021.\n\n[AC\\DC] Peste, Alexandra, et al. \"Ac/dc: Alternating compressed/decompressed training of deep neural networks.\"  Neurips 2021\n\n[CBS] Yu, X., Serra, T., Ramalingam, S., & Zhe, S.. “The combinatorial brain surgeon: pruning weights that cancel one another in neural networks.”  ICML 2022", "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": "rEkmtXh9Hl", "reviewer": "Reviewer_T9TW", "summary": "This work combines second-order curvature information with sparse recovery algorithms to demonstrate, both theoretically and empirically, that the curvature information leads to improved convergence rates and generalization performance in post-training iterative pruning and sparse recovery", "questions": "## Questions\n* In terms of wall clock time, what was the duration required for the pruning results in Tables 1 and 2 and what hardware configuration was used? \n* How do the compressed LLMs compare on downstream tasks such as LLM-KICK or GLUE? \n* Can I-OBS be extended to fine-grained sparsity types such as N:M sparsity?\n* Are the results in Table 2 obtained with 32- or 16-bit weights? How does a quantized dense model with half the precision as used in Table 2 compare? \n\n## Suggestions\n* Use vector graphic formats for Figure 1. \n* Potential typos to address:\n\t* L281 & Figure 1 Caption: Refers to topk-WoodFisher, I believe this should be **topk-I-OBS**? Perhaps a prior naming convention? \n\t* Table 2 caption: Phi-1.5M -> Phi-1.5B\n\t* L332: pwer-layer -> per-layer\n\t* L340: mode -> model", "limitations": "In general the limitations listed are appropriate. However, I encourage the authors to add some discussion about the practical requirements for their algorithm in terms of time and compute.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "* This work offers a rigorous analysis of the proposed method, I-OBS, complete with detailed derivations and proofs. \n* The authors ground their contributions within the context of the existing literature but clearly identify how it differs from prior works by leveraging second order information. \n* Despite the intractability of the theoretical approach, the authors offer a practical formulation that yields improved performance across a diverse range of data domains. \n* The paper is rather dense; however, the authors provide all the necessary notation required to follow their derivations. \n* This is a well motivated line of inquiry as post-training compression is increasingly important in the era of LLMs. Further, despite requiring additional iterations compared to one-shot pruning methods, I-OBS converges in a small number of iterations (<100 for DeiT and <3 for LLMs).", "weaknesses": "* Grounding this work in some practical considerations would improve the overall impact of the paper and may help the reader assess whether this technique is suitable for a desired use case. For instance, adding some overall runtime characteristics for the empirical results would establish an order-of-magnitude estimate of the overall computational requirements. \n* In a similar vein, conducting experiments with fine-grained sparsity such as 2:4 would be a nice extension to produce sparse neural networks that can actually be accelerated in practice. As it currently stands, the unstructured networks learned by I-OBS do not offer much in the way of an immediate practical application. \n* For the LLM experiments, perplexity has been shown to be a somewhat misleading metric when evaluating compressed LLMs [1]. Ideally, the LLM experiments should be evaluated on downstream tasks such as GLUE or better yet the LLM-KICK benchmark [1]. \n* Several post-training compression schemes have been proposed recently. Comparisons with methods such as [2-6] would improve my confidence in the significance of this work. \n* Several small typos, see suggestions below. \n\n[1] A. Jaiswal, Z. Gan, X. Du, B. Zhang, Z. Wang, and Y. Yang, “Compressing LLMs: The Truth is Rarely Pure and Never Simple.” arXiv, Oct. 02, 2023. doi: 10.48550/arXiv.2310.01382.\n\n[2] T. Dettmers et al., “SpQR: A Sparse-Quantized Representation for Near-Lossless LLM Weight Compression.” arXiv, Jun. 05, 2023. [Online]. Available: http://arxiv.org/abs/2306.03078\n\n[3] M. Sun, Z. Liu, A. Bair, and J. Z. Kolter, “A Simple and Effective Pruning Approach for Large Language Models.” arXiv, Jun. 20, 2023. doi: 10.48550/arXiv.2306.11695.\n\n[4] Y. Zhang, H. Bai, H. Lin, J. Zhao, L. Hou, and C. V. Cannistraci, “Plug-and-Play: An Efficient Post-training Pruning Method for Large Language Models,” presented at the The Twelfth International Conference on Learning Representations, Oct. 2023. [Online]. Available: https://openreview.net/forum?id=Tr0lPx9woF\n\n[5] Y. Zhang et al., “Dynamic Sparse No Training: Training-Free Fine-tuning for Sparse LLMs.” arXiv, Oct. 17, 2023. doi: 10.48550/arXiv.2310.08915.\n\n[6] Y. Ma et al., “AffineQuant: Affine Transformation Quantization for Large Language Models.” arXiv, Mar. 19, 2024. doi: 10.48550/arXiv.2403.12544.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you  for the detailed review, as well as your valuable questions and comments. We address your questions and concerns below\n\n**Q1 and W1 Regarding the training time of the pruning results**\n\nFor the experiments on ViTs (Table 1 in the paper), it took about 4 hours to run 100 iterations and the hardware we used was Nvidia A100 GPU with 80GB memory. For LLMs experiments,  we ran I-OBS on Llama-2 (7B) and Llama-3 (8B) models, and it takes around 1.5 hours per iteration (15h for 10 iterations). Unfortunately, we haven't recorded the time of running the experiments on OPT-125M and Phi-1.5 (Table 2 in the paper). \n\n**Q2 and W3 Evaluating the performance on LLM-KICK or GLUE**\n\nTo address your concern and study the scalability of I-OBS, we ran I-OBS on Llama-2 (7B) and Llama-3 (8B) models. Specifically, we apply SparseGPT (50% sparsity) and finetune on the same calibration set used for Hessian estimates. We evaluate the performance on 5-shot MMLU, one of the tasks from LLM-KICK benchmark–we did this due to time constraints but will expand to the full benchmark for the next revision. \n\nExperimental results are provided in Table 1 and Table 2 of the PDF file we attached in the global rebuttal.\n\nOne can observe that the quality of sparse solution significantly improves after first finetuning iteration, thus validating our approach. Moreover, there is small improvement during the next few iterations, followed by gradual performance deterioration afterward, which we explain due to overfitting on the calibration set. Specifically, I-OBS improves accuracy on MMLU by >1 point, a 20% reduction in error relative to the original dense model. \n\n**W4 Comparison to other  works in pruning**\n\nThank you for the suggestion. As also suggested by reviewer JoZw, we provide a more detailed literature review. Please refer the answer to **Q2 of reviewer JoZw**. We apologize that we can not copy the whole response here due to the character limit. \n\nAlso, as suggested by reviewer JoZw, we conducted experiments on  MobileNetV1 to compare to the CBS methods.  The results are shown in  Table 3 of the attached file in global rebuttal. Our experiments imply that, starting with 60\\% sparsity, our I-OBS pruner outperforms CBS method on MobileNetV1 by a large margin: 2\\% for 60\\% sparsity, 5\\% for 70\\% sparsity and 12\\% for 80\\% sparsity. For low sparsities (30\\% to 50\\%), the two methods are comparable, since the accuracy difference is less than 0.5\\%\n\n**Q3 and W1  Extend to fine-grained sparsity type**\n\nThe practical implementation of I-OBS indeed extends to N:M sparsity. In particular, we apply OBC or SparseGPT as sparsity solvers for the layerwise pruning problem, and  OBC or SparseGPT applies to N:M sparsity. However, for the theoretical results, we are unable to extend the analysis to the masks selected based on N:M sparsity, we will leave this to future work.\n\n\n\n**Q4 Are the results in Table 2 obtained with 32- or 16-bit weights? How does a quantized dense model with half the precision as used in Table 2 compare?**\n\nThe results in Table 2 are obtained with bfloat16 (half precision) weights, which is standard. Generally, we found the weight precision to be orthogonal to our results, as sparsification can be applied independently of the baseline weight representation, and always yields similar speedups (the maximum speedup due to 2:4 sparsity is 2x for INT8 and FP16). \nMore broadly, we believe our iterative approach should be generalizable to compression via quantization as well: specifically, we could modify the projection step to perform quantization rather than sparsification. \n\n**Suggestions**\n\nThank you for the suggestions. We will change the figure format and correct the typos in the revision\n\n**References**\n[CBS] Yu, X., Serra, T., Ramalingam, S., & Zhe, S.. “The combinatorial brain surgeon: pruning weights that cancel one another in neural networks.”  ICML 2022", "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": "eae0UVLNHv", "reviewer": "Reviewer_3y7g", "summary": "This paper proposes a theoretically convergent iterative Optimal Brain Surgeon (OBS) algorithm, which generalizes the classic Iterative Hard Thresholding (IHT)-based algorithms by incorporating approximate second-order information in the sparse projection step. The author also provides practical variants of these algorithms for solving sparse linear regression and model pruning. The experiments show that the proposed algorithm leads to faster convergence than traditional algorithms and improves accuracy.", "questions": "Detailed comments are as follows:\n1. The author elaborates on the theoretically convergent I-OBS method and provides specific calculations for both practical and theoretical schemes. What is the gap between the two schemes? Can it be verified through experiments or illustrated with examples? What is the specific operator T in the practical scheme?\n2. In lines 158 and 169, the specific form of the model \\( \\phi_t(\\theta) \\) differs.\n3. In the model pruning experiment, the author provides the specific algorithm Alg. 2 for the practical use of I-OBS. By constructing a constrained optimization problem for the learnable parameters \\( W \\) of each layer to fine-tune the model, the author has verified the method's feasibility through experiments. Is it theoretically feasible?", "limitations": "The author objectively analyzed the limitations of this article.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The proposed algorithm is simple yet effective.", "weaknesses": "Theoretical analysis does not hold in general for practical problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable questions and positive comments. We address your questions below:\n\n**Q1, Regarding the gap between the practical and theoretical schemes:**\n\nWe note that for the theoretical scheme we have $|| \\theta\\_{t+1} - \\theta^* ||\\_2 \\leq \\left(1+ \\sqrt{\\frac{L}{\\mu}\\frac{d-k^*}{d-k}} \\right) \\frac{M}{2 \\mu} || \\theta\\_t - \\theta^*||\\_2^2.$ (Theorem 1) and for the practical scheme we have $ || \\theta\\_{t+1} - \\theta\\_* ||\\_2 \\leq \\left( 1+ \\sqrt{\\frac{k^*}{k}} \\right) \\frac{M}{2 \\mu} || \\theta\\_t - \\theta^* ||\\_2^2$ ( Lemma 3). In both cases, the upper is in the form of $|| \\theta_{t+1} - \\theta_* ||_2 \\leq C|| \\theta_t - \\theta^* ||_2^2 $, where $C$ is a constant. Thus, both scheme gives a super-exponential local convergence rate, namely both algorithms achieve $\\epsilon$-error with initialization $||\\theta_0 - \\theta^*||_2 \\leq \\frac{1}{2 C}$ in $O( \\log \\log \\frac{1}{\\epsilon})$ steps. Thus,  there is no gap in terms of convergence rate. There is indeed a difference in the convergence radius $ \\frac{1}{2 C}$ since the constant $C$ is different, but we remark that this difference is minor in practice.   \n\n**Q2, In lines 158 and 169, the specific form of the model ( $\\phi_t (\\theta)$ ) differs**\n\nWe thank the reviewer for the detailed review, however, there are no $ \\phi_t(\\theta)$ in line 169. Do you mean the $ \\phi_t(\\theta)$ in line 164? \nIn line 164, we replace the gradient  $\\nabla f(\\theta_t) $ term with the stochastic gradient term$g_t(\\theta_t) $, so that if one solves the proximal problem induced by the $ \\phi_t(\\theta)$ in line 164, one will get the update of stochastic gradient descent rather than gradient descent.\nPlease let us know if there are any further questions regarding this point.\n\n**Q3, Regarding the theoretical analysis of the practical implementation of I-OBS**\n\nWhile we believe it would be interesting to obtain a theoretical guarantee for the practical implementation of I-OBS, we find it is difficult to make it end-to-end rigorous, as the underlying constrained optimization problem is NP-hard. In particular, to efficiently solve the constraint optimization problem in line 7 of Algorithm 2, we applied existing heuristic quadratic sparsity solvers, such as OBC or SparseGPT. (In preliminary experiments, we have also investigated applying algorithms with approximation guarantees, such as Natarajan’s algorithm [Natarajan95], but found that these are much less scalable and do not provide better solutions.) These solvers use greedy heuristics to efficiently compute the masks, since obtaining the theoretical optimal masks shown in line 7 of Algorithm 1 is practically infeasible. Despite this approximation, we note that our approach obtains high practical performance. \n \n[Natarajan95] Natarajan, Balas Kausik. \"Sparse approximate solutions to linear systems.\" SIAM journal on computing 24.2 (1995): 227-234.", "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:
We would like to thank the reviewers for their detailed feedback. We briefly summarize our responses here for clarity: 

1. One general question was regarding the positioning of our work relative to prior work on pruning. 
In this context, our work tries to provide the first rigorous analysis of approaches inspired by the Optimal Brain Surgeon paper of [1], achieving quadratic convergence rates in the case of an idealized algorithm for choosing masks. Surprisingly, we are also able to provide similar rates for a practical algorithm based on greedy TopK mask selection (Lemma 3). 
In addition, our work directly connects to recent work on pruning: as discussed in Section 3.4, methods such as WoodFisher/WoodTaylor [2] and OBC [3] are special cases of our iterative framework. Generally, our iterative approach can be seen as complementary to methods investigating better one-shot Hessian approximations, such as CBS [4], as they can be directly plugged into our algorithm’s projection/selection steps.   
To fully address this point, we have provided detailed comparisons with additional recent work suggested by the reviewers, such as CBS and CHITA[5] , in the individual responses, and will definitely expand this discussion and the citations in the next revision of our work. 

2. Another general question regarded expanding the experimental comparisons. To address this, we provide additional experiments on Llama2-7B and Llama3-8B models, again providing significant improvements relative to the baselines (specifically, SparseGPT[6]). Moreover, we show that this improvement also holds on the MMLU LLM task, a subset of the suggested LLM-KICK benchmark. (We plan to further expand this comparison in the next revision.)  

3. We provide the extra experiment results in the attached PDF file of this global rebuttal.

4. Beyond these two common points, we have provided answers to each individual reviewer's concerns. 

We hope that our responses address the reviewers’ questions, and would be happy to continue the discussion during the rest of the rebuttal period. 

[1] LeCun, Yann, John Denker, and Sara Solla. "Optimal brain damage." Advances in neural information processing systems 2 (1989).

[2] Singh, Sidak Pal, and Dan Alistarh. "Woodfisher: Efficient second-order approximation for neural network compression." Neurips 2020

[3] Frantar, Elias, and Dan Alistarh. "Optimal brain compression: A framework for accurate post-training quantization and pruning." Neurips 2022

[4] Yu, X., Serra, T., Ramalingam, S., & Zhe, S.. “The combinatorial brain surgeon: pruning weights that cancel one another in neural networks.”  ICML 2022

[5] Benbaki, Riade, et al. "Fast as chita: Neural network pruning with combinatorial optimization." ICML 2023

[6] Frantar, Elias, and Dan Alistarh. "Sparsegpt: Massive language models can be accurately pruned in one-shot."ICML 2023

Meta-review: This paper proposes iterative approaches for pruning machine learning models, motivated by the iterative hard thresholding algorithm and the compressed sensing literature in conjunction with the Optimal Brain Surgeon framework. By employing second order information, the authors generalize previous approaches. Theoretical guarantees are derived for their pruning approach under suitable assumptions, and the numerical experiments support the authors' claims. 

There is a consensus among reviewers that this work would be a good addition to the conference, and I agree.
Decision: Accept (poster)