Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations
Authors: Yasutoshi Ida
Sekitoshi Kanai
Atsutoshi Kumagai
Tomoharu Iwata
Yasuhiro Fujiwara
Venue: NeurIPS 2024 poster (2024)
Keywords: feature selection
sparse coding
dictionary learning
compressed sensing
iterative hard thresholding
pruning method
Primary area: other

Abstract: We accelerate the iterative hard thresholding (IHT) method, which finds \(k\) important elements from a parameter vector in a linear regression model. Although the plain IHT repeatedly updates the parameter vector during the optimization, computing gradients is the main bottleneck. Our method safely prunes unnecessary gradient computations to reduce the processing time.The main idea is to efficiently construct a candidate set, which contains \(k\) important elements in the parameter vector, for each iteration. Specifically, before computing the gradients, we prune unnecessary elements in the parameter vector for the candidate set by utilizing upper bounds on absolute values of the parameters. Our method guarantees the same optimization results as the plain IHT because our pruning is safe. Experiments show that our method is up to 73 times faster than the plain IHT without degrading accuracy.

Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations
Yasutoshi Idal*
Sekitoshi Kanai!
Atsutoshi Kumagai
Tomoharu Iwata?
Yasuhiro Fujiwara*
NTT Computer and Data Science Laboratories
NTT Communication Science Laboratories
Abstract
We accelerate the iterative hard thresholding (IHT) method, which finds k important elements from a parameter vector in linear regression model. Although the plain IHT repeatedly updates the parameter vector during the optimization, computing gradients is the main bottleneck. Our method safely prunes unnecessary gradient computations to reduce the processing time. The main idea is to efficiently construct a candidate set, which contains &t important elements in the parameter vector, for each iteration. Specifically, before computing the gradients, we prune unnecessary elements in the parameter vector for the candidate set by utilizing upper bounds on absolute values of the parameters. Our method guarantees the same optimization results as the plain IHT because our pruning is safe. Experiments show that our method is up to 73 times faster than the plain IHT without degrading accuracy.
1 Introduction
The optimization problem of finding sparse parameter vectors in linear regression models crucial problem that crosses wide range of fields, including feature selection 220 35), sparse coding (32), dictionary learning [33], and compressed sensing [6]. To obtain the sparse parameter
vector, the parameter vector is often constrained to have i nonzero elements. Among huge number
of algorithms that have been developed for this problem 25 14 27
10 19
11 20 iterative hard
thresholding (IHT) methods [6] are practical methods based gradient descent methods because
they have almost no overhead over the plain gradient descent method 2
A procedure of IHT consists of two main parts in an iteration. First, it updates the parameter vector in accordance with the gradient descent method. Then, the parameter vector is projected onto feasible set being set of sparse parameter vectors. In the projection, IHT uses a hard thresholding operator that selects the k-largest elements in terms of magnitude of the parameter vector, and the other elements are set zero. IHT repeats this procedure until the stopping criterion is satisfied.
When design matrix of the linear regression model is an m-by-n matrix, the length of the parameter vector is n, and gradient computations of IHT require O(m)) or O(n²) time for each iteration. Specifically, IHT suffers from the increase in processing time for large m and n. Taking feature selection
example, IHT slows down for large datasets because m and n correspond to the numbers of samples and features the dataset, respectively. The gradient computations are much more computationally expensive than the projection of the parameter vector because the projection only requires On log k) time it uses a heap. Therefore, the gradient computations are dominant in the overall procedure of IHT, and we need to reduce the cost to raise the efficiency of IHT.
Corresponding author: yasutoshi. ida ieeee.org
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

This paper proposes fast IHT that safely prunes unnecessary gradient computations. Before computing the gradients for each iteration, the proposed method efficiently constructs candidate set whose elements correspond to indices of the k-largest elements in terms of magnitude of the parameter vector. When constructing the candidate set, our method prunes indices that are clearly not included in the candidate set. To identify such indices, we compute upper bounds of absolute values for the elements of the parameter vector. If the upper bound smaller than a threshold, the index is not included in the candidate set. The threshold is automatically determined by leveraging lower bounds absolute values for the elements of the parameter vector. Since the computation cost of the upper and lower bounds is O(n) time, can efficiently construct the candidate set. By updating only the parameters corresponding to the candidate set, we can prune unnecessary gradient computations. Our method guarantees the same optimization results as the plain IHT because it safely prunes unnecessary computations. In addition, our method does not need additional hyperparameter tuning. Experiments demonstrate that method is up 73 times faster than the plain IHT while maintaining accuracy on feature selection tasks.
Related Work
In 4 [3], the authors utilized Youble-overrelaxatie approach to improve the convergence speed of IHT. They use two relaxation steps for the parameter vector, which are similar the momentum of Nesterov's method [28]. In 8 [4], the authors introduced the momentum to IHT inspired by the fast iterative shrinkage thresholding algorithm (FISTA) [] While FISTA uses the momentum with a soft thresholding operator, Cevher S uses it with the hard thresholding operator. This Accelerated IHT
(AccIHT) has substantial theoretical and empirical improvement over the plain IHT 223
While the previous methods have reduced the number of iterations to accelerate IHT as described above, the best of our knowledge, there are papers on reducing the computation cost per iteration of IHT. This paper aims to fill this gap based on the pruming strategy. For convex and some nonconvex regularization, working set algorithms are used reduce the cost of solvers 7 21 26 31] They solve a growing sequence of subproblems that are restricted to a small subset of parameters during optimization. In [12 13
18 17,, the authors reduced the cost by skipping unnecessary norms. However, since these methods are tailored for coordinate descent or the soft thresholding operator, they cannot be used for IHT, which selects l elements from the parameter vector by using the hard thresholding operator.
22
15
16
parameter updates for coordinate descent with
3 Preliminary
Notation. We denote scalars, vectors, and matrices with lower-case, bold lower-case, and bold upper-case letters, e.g., I, x and X, respectively. Given a matrix X, we denote its i-th row by X,- Given vector Ih, denote its i-th element by æ;, and call index. | 12 is the l2 norm. |x lo is ifi E (1...., m | * 0}| and represents the number of nonzero elements æ. 0 E IR" is the mn-dimensional vector whose elements are zeros. I represents the identity matrix. supp(æ)) the function that returns the indices of nonzero elements in æ.
3.1 Problem Setting
Let X E R be an input matrix (design matrix), E RT be set of continuous responses, and IR. be a parameter vector of a linear regression model. To find a sparse parameter vector of the model, we consider the following optimization problem [
min
1
x0l3 subject
|0 S
(1)
DER
In the above problem, the number of nonzero elements in the parameter vector, |0% is constrained b1y x0 for simplicity.
by k E (1,...,,.) n). Here, we will let f(0)
3.2 Iterative Hard Thresholding
IHT is the practical algorithm for Problem I 55 22. It repeatedly performs the following iteration:
z' 0¹ ( 0¹ g++1 =H)(='),
n X v) (I x x)0 +nx y.
(2)
(3)

---

Algorithm Iterative Hard Thresholding
1: Input: sparsity level k. step size
2: Initializatinn: 0 f 0, 0+1
3: repeat
4: x' 5 0 -V
Performing gradient descent method Selecting the k-largest elements in magnitude of ='
5: 0 f- (x ++1: 1;
6: until stopping criterion is met
where > 0 is the step size, O' is the parameter vector at the t-th iteration. (z²) is the hard thresholding operator that selects the k-largest elements in the magnitude of x and the other elements to zero. The selection requires (n log k) time if it uses heap. The pseudocode is described in Algorithm T
See
14
6
for theoretical discussions of IHT.
From Equation 2 and Algorithm computing gradients ( clearly dominates the other cost. the second equation the third one to compute z'. They require (mn) and Onn2) times in every iteration, respectively Therefore, IHT incurs high computation cost when
In Equation (
X Rm*nn is large.
4 Proposed Algorithm
This section describes our algorithm that reduces the computation cost per iteration in IHT.
4.1
Main Idea
The bottleneck of IHT is the gradient computation to obtain x' of Equation ( it requires (mm) or O(n²) time per iteration. Therefore, we reduce the cost by pruning unnecessary elements in x before computing the gradients. For the pruning, we introduce candidate set 'D' such that [De] for the t-th iteration. This set maintains indices nonzero elements of the parameter vector during optimization. In other words, the candidate set contains indices of the k-largest elements in terms of magnitude of the parameter vector. Before computing Equation (2). we quickly check whether indices of elements in z' included not in Di+1, If an index ; not included in D4+1, we can prune z) and skip the corresponding computation of Equation 2 including the gradient computation.
The point is that our method can efficiently perform the above checking procedure. Specifically, method utilizes zJ. which is an upper bound of |z/|- Since the computation of the upper bound does
not include the gradient computation, it only requires (n) time for all the elements in z For the checking procedure, after initializing DD appropriately. our method finds a threshold for the pruning by utilizing zj,, which is lower bound of 125). Then, if zJ is smaller than the threshold for j & D the index j is not included in D We describe the details in the next section.
4.2 Upper Bound and Candidate Set
This section introduces candidate set DD and its updating method. Since we need upper bound z} to efficiently update D as described in Section 4.1 we first define z as follows:
Definition Let to be S E" < l in Algorithm Then, Σ at the 1-th iteration in Algorithm is computed as follows:
2 = G + +7(X
x GG, 0- 1/
where = -
x X.
We note that G and X y are precomputed only once before entering the optimization, and t is automatically decided as described Section 4.4 z! has the following property:
'If T X X and X y are precomputed, the cost is (ni") time. If the precomputation is not performed, the cost is (mm) time because we first compute h = xx - at (mm) time, then compute X h at (mn) time. See the Appendix for discussion of IHT with sparse matrices.
3

---

Lemma (Upper bound) When ž is computed by Equation we have xj
|zj].
Lemma iss derived from the triangle inequality and the Cauchy- Schwarz inequality. It guarantees that zj is the upper bound of z/). The computation cost of the upper bound is as follows:
Lemma (Computation cost of upper bound) The computation cost of Equation 4 for all j E
(1,..,n) n. at the 1-th iteration is (n) time given G, X y and [G,0' + (X y)j
Lemma 2 shows that the upper bound at the t-th iteration requires only ((n) time G and X y are precomputed and | + r)( (X T y)1 is computed at the (*-th iteration.
Next, we define candidate set D' as follows:
Definition (Candidate set) Let I = (I....,
.... n be a set of all the indices in the parameter vector
O ER".. Suppose that 'D' C I is sel such that (D') = k at the 1-th iteration in IHT where 1. >> 1, and initialized as D' (0") at the beginning of the iteration. Then, we call D' the candidate set.
D' has indices that candidates for supp(0++1) in IHT. Since D' is initialized D supp (0') at the beginning of the iteration in Definition 2 we need to update D' to Dt+11 so that it matches supp( 1). Although can update D' such that D
(x*)((xx(2)) by computing Equa- tions and (3, they include the gradient computation that requires O (mm) or (n²)) time.
To efficiently update D' to Di+1, we utilize the upper bound x of Equation
(4) for j & DD. By using z). can identify unnecessary elements in z' that clearly not included in DD+1 as follows:
Lemma (Pruning unnecessary elements) Suppose that z' is computed by using Equation (4) and the candidate set D' is initialized as described in Defimition 2 at the beginning of the iteration for L 1. Let zim... be z having the minimum | in all E D=, and imin be the index. Then, if
|z Aminn 2 2 holds for j o D'. is not included in Dt+1
From Lemma 3 when we check whether j & DD is included or not in D++1, we do not need to compute the gradient corresponding to 2) if | 2 W² holds. Although we need to compute the gradients to find x iinin in the initial Dt, the cost is relatively small because the cardinality D' is usually small as 'D'== k < n.
Algorithm 2 is the pseudocode of updating the candidate set. It first copies D' to Di+11 (line 3).
Lines 4-13 check whether the computation of 2 can be pruned or not by following Lemma 3 If the computation is pruned (line 5), we skip the computation of 2 including the gradient computation
(line 6). If the computation is not pruned (line 7), line 8 computes z/. If |=!_m. < |z)] holds (line 9), the algorithm updates the candidate set DD to remove imin and include j (line 10). In this case, 2 must also be updated since Dr+1 has been updated (line 11). If 2 | does not hold
(line 12), we set z1 0 because j cannot be included in D (line 13).
For the outputs z² and D4++1 of Algorithm 2 we have the following property:
Lemma 4 (Consistency of outputs) For the outputs of Algorithm 2 z' (0+p( hold.
0 and D4+1
The above lemma shows that Algorithm returns the same 0++1 and (mpp((t+1) as those of the plain IHT while it prunes unnecessary computations given z! min. z', and D Specifically, we can use Algorithm instead of lines 4-5 in Algorithm
The computation cost of Algorithm 2 is as follows:
Lemma (Computation cost of updating candidate set) Let be the number of un-pruned com- putations at line 7 of Algorithm 2 If G and X are precomputed, Algorithm 2 requires ((u)) time and the worst time complexity is O(n²) time.
Lemma 5 shows that the cost of Algorithm 2 is small when the pruning rate is high because u becomes small when the pruning rate high. On the other hand, the worst time complexity of O(n2) time obtained with a low pruning rate. The asymptotic cost cannot be larger than that of the plain IHT

---

Algorithm Update of candidate set
Algorithm 3 Update threshold
Input: = imp W", D
Input: "miy" 2,, D
2: Output: z², DD
2: Output: 2 Bmin 2² D
3: Di+1 f- Dr:
3: De ( DD
for j D do
4: for E D' do
if 2 Emiu
2 x
then
if 1
=2 then -D'
2j 0:
6:
D
(min) U
7: else
7:
compute z). * t
compute z/.
8:
if
b mnin |= then
9:
find z in DC::
10:
D <- (DL- \\ mminn) U
10:
2
f 2mmm
11:
z min
0; find z in Dz+1:
11: z²
guin
f- z²:
12:
else
13:
2] f-
since the gradient computation of the plain IHT requires (mm) or On time. Nonetheless, the pruning rate needs be increased achieve higher speeds.
In Algorithm
2 |=| Festn plays the role of the threshold for pruning at line 5. Therefore, we can raise the pruning rate for larger threshold of | because l 2 x at line 5 is easier to hold for larger threshold. The next section introduces efficient way to update | to larger value before entering Algorithm 2
4.3 Lower Bound and Update of Threshold
To update threshold | to larger value, we utilize the lower bound z such that |2]] for D'. 2² is defined follows:
>
holds
Definition Let to be t < in Algorithm Then, z at the t-th iteration in Algorithm computed as follows:
2 O +n 4)ll 11 0" 12.
where G=I-NX X.
The following lemma shows that 2/ the lower bound [=]]:
Lemma (Lower bound) We have 2 |=3] when 25 is computed by Equation
5
Lemma il derived from the reverse triangle incquality and the Cauchy-Schwarz inequality, Similarly to the computation cost of the upper bound, Equation (5) requires the following cost:
Lemma (Computation cost of lower bound) The computation cost of Equation 5 for all j
{1, n) at the 1-th iteration is O(n) time given G, X y and [G +n((X y)
To update |z] p we utilize the following lemma:
Lemma 8 (Indices required for candidate set) Suppose that z² is computed by using Equation (5) and the candidate set D' is initialized as described in Definition 2 at the beginning of the iteration for t 1. Let 2 be 2t having the minimum [x]] in all E D., and imin be the index. Then, if |2/_...l < 2 holds for & D'. is included in D
The above lemma shows that we can identify indices included in D'+1 without computing the gradients by using the lower bound z². The update procedure of D to D is described in
5

---

Algorithm 3 Since this D is used as the initial candidate set of Algorithm 2 we represent D as DD+1 in Algorithm 3 to avoid confusion. The algorithm copies D' to D' at line 3. Line 5 checks whether | < žj holds or not. If the equation holds, the algorithm updates D' to remove imin and include j (line 6). At this time, we also update z] and x imin to reflect the update D' (lines 7-9). 2!! minn
and z" (lines 10-11) used z and 2 in Algorithm 2
The important point of Algorithm than the initial 1 as follows:
3 is that the absolute value of the output 1x imin
is equal to or larger
Lemma 9 (Threshold increase) In Algorithm
holds.
From the above lemma, we can obtain large | performing Algorithm before entering Algorithm increase the pruning rate.
as the threshold | I in Algorithm by
As a result, we can expect Algorithm to
The computation cost of Algorithm 3 is as follows:
Lemma 10 (Computation cost of threshold increase) Let I be the number of indices that are de-
termined be included in D' at line 5 of Algorithm IfG and X y are precomputed, Algorithm 3
requires (In) time and the worst time complexity of Algorithm 3 is O(n)) time.
Similarly to Lemma of Algorithm?
2
the worst time complexity is not much more than that of IHT.
4.4 Algorithm
4 is the pseudocode of our method based on Algorithms and 3 We first precompute G and X T y for the upper and lower bounds (line 3). The main loop consists of two types of procedures (lines 4-22): the procedure for L = L" (lines 5-11) and the procedure for + t (lines 12-21). For the case of ( = t", the algorithm updates the parameter vector the same the plain IHT (lines 6-7) and computes the candidate set (line 8). We note that the computation result of line
Algorithm
also used for computing the upper and lower bounds as shown in Definitions [and] 3 Line 9 sets t" as L and line 10 computes an interval r 2 1 that determines which is the next t* Specifically, the next t* is determined as t* +r. The computation way of is described later. r' is the variable that monitors the interval. If = t" does not hold (line 12), it computes x for E DD by using Equation (2) (line 13). Next, line 14 computes the lower bound by using Equation (5) the basis of Lemma 6 Then, we find the initial threshold at line 15 and update it by using Algorithm 3 on the basis of Lemmas (line 16). Then, compute the upper bound by using Equation (4) the basis of Lemmal (line 17). Line 18 computes z' by using Algorithm 2 while pruning unnecessary computations on the basis of Lemma 3 This z' can be handled as 0C+ by following Lemma 4 (line 19). We monitor the interval of the next 1* at line 20 through r'. The algorithm repeats the above procedure until a stopping criterion is met (line 22). An example of a stopping criterion is relative tolerance 23
Automatic determination of t via r. In Algorithm we need to compute interval r at line 10 to determine &* because 0* appears in Equations (4) and (5) for computing the upper and lower bounds, respectively. Since the upper bound z" and lower bound 2 are the approximation of z5. we obtain the following error bound:
Lemma 11 Suppose that ej is computed as follows:
Ej 2||G 0" l
(6)
Then, x² - -21 Ej and |z) - 2/1 < e hold.
From the above lemma, the magnitude of error bound e, depends on 1" because of |0 00 ll in
Equation (). If we set r' to large value, the error bound can be large since |0-- 0² tends to be large. In this case, the bounds are loose and it is difficult to hold |z Smin 2 z in Lemma As result, the pruning rate will low. On the other hand, if we set r small value, the algorithm frequently computes lines 5-11 although we can obtain tight bounds. Since line 6 requires O (n²2 time, the reduction of the computation cost will be small. To solve the above problem, we automatically determine on the basis of the current pruning rate that is defined as follows:

---

Algorithm 4 Fast Iterative Hard Thresholding
1: Input: sparsity level k. step size
2: Initialization: 0 <- 0, t 1, t t 1, 1 1 0, t 0
3: computing G and X y:
The precomputation for the upper and lower bounds
4: repeat
b The main loop
5: if = 0 then
The precomputation for the upper and lower bounds b Computing G0 + n y used for z' and z' Updating the parameter
6:
z' GO + +nx y:
7:
o + Hz'z');
8:
D' c supp(0't!):
Updating the candidate set
9:
1* t
10:
compute on the basis of automatic determination and r' <-
+-++1:
12:
else
13:
compute 2 for i D' by Eqn.
14:
compute z' by Equ. 5
> Computing the lower bound on the basis of Lemma
15:
find z',,, in Dr:
16:
update xm 2" and D' by Algorithm
b Based on Lemmas and >> Computing the upper bound the basis of Lemma
compute W' by Eqn. 44:
18:
compute z' and D4+1 by Algorithm 2
D> Based on Lemma
19:
g++1 + z²: r' - L- ++ 1;
Updating the parameter the basis of Lemma
20:
21:
until a stopping criterion is met
Definition (Pruning rate) Let us be the number of un-pruned computations at line 7 in Algorithm Then, define pruning rate ps line 10 in Algorithm
for the t-th iteration as defined in Lemma 5 for the t-th iteration as follows:
Pc
X 100.0.
The unit of Pa is percent. We compute r at line 10 in Algorithm F the basis of pt as follows:
r ++1 if p. 2 50.0 [r/2]
r r=
if Pr 50.0.
[-1 is the ceiling function. If the algorithm could prune half of the computations at the previous iteration, it increases interval r. If not, we update to [r/2] to reduce error bound 6,. Therefore, if the pruning rate is high, we can reduce the number of computations at line 6 by increasing the interval. If not, the interval becomes small and the upper and lower bounds are expected be tight. This rule performs well in our experiments.
4.5 Analysis
The computation cost of Algorithm 4 follows:
Theorem (Computation cost) Let and be the total numbers of u and in Lemmas and 10 in Algorithm 4 respectively. Suppose that r is constant for simplicity, is the total number of main loops in Algorithm and r' is the number for which line 12 holds. Then, the computation cost of Algorithm 4 is O (I (m + -TT) n(l' rl + +'k)) time, and the worst time complexity is O + +)) time.
The plain IHT of Algorithm 1 requires On 7)) time if G and X are precomputed. Therefore, the worst time complexity of our method is the same as the cost of the plain IHT.
For the optimization result, obtain the following thcorem:

---

Theorem (Optimization result) Suppose that 4 the same hyperparameters as those of the plain IHT of Algorithm L value as Algorithm 7
Then, Algorithm yields the same parameter vector and objective
Theorem 2 guarantees accuracy of our method. Our method prunes unnecessary computations without degrading accuracy.
For the upper and lower bounds, the following property holds:
Theorem (Convergence of upper and lower bounds) Suppose that Algorithm converges as O = 0 Then, obtain e 0 for j [I).. where Ej is the ervor bound of the upper and lower bounds defined in Lemma 17
Theorem 3 shows that the upper bound Σ/ and lower bound = become the exact value of 2 when 0' = 0t holds. Therefore, our method accurately prunes unnecessary computations when the condition satisfied.
5 Experiment
We evaluated the processing time and accuracy of our method on feature selection tasks. We performed experiments on five datasets from the LIBSVM [9] and OpenML (34]: gisette, robert, ledgar, real-sim, and epsilon. The sizes of the input matrices are 6000 x 5000, 10000 x 7200, 60000 19996, 72309 20958, and 400000 x 2000, respectively. We evaluated the processing time and accuracy on k (1,5, 5, 10, 20, 40, 80, 160. 320, 640, 1280}. We compared our method with the plain IHT (IHT), Regularized IHT (RegIHT) 22] and Accelerated IHT (AceIHT)
23 RegIHT the
fastest method among the methods using an adaptive regularization technique M. Since ReglHT has the hyperparameter of weight step size c, we tried the setting of (k, 1/10, k/100) on the basis of the original paper. AcclHT improves the convergence of IHT by utilizing the momentum. We tried j (0.025, 0.25, 2.5} for the momentum step size μ where the value of 0.25 is the one recommended in the original paper. We set step sizes of all the methods 7/ = 1/> where À is the largest cigen value of X X by following [23] We stopped these methods when the relative tolerance of the parameter vector dropped below 10
15 All the experiments were conducted on 3.20 GHz Intel CPU with six cores and 64 GB of main memory.
5.1 Processing Time
Figure T (e) compare the processing times on logarithmic scale. Our method was up to 73 times faster than IHT and outperformed all the baselines in all the settings. Because our method based on the pruning, it achieved a large speedup factor for smaller k. Even when & increased, the processing time was significantly shorter than the baselines.
We note that our method does not need hyperparameter tuning due to using the automatic determina- tion technique described in Section 4.4 Specifically, practitioners only need to specify l to method the same as the plain IHT. On the other hand, the baselines of ReglHT and AccIHT require additional hyperparameter tuning for the weight step size and the momentum step size, respectively.
Number of Gradient Computations. Figure (f) compares the number of gradient computations between method and the plain IHT the gisette dataset. Our method reduced the number of computations by up to 88. The result shows the effectiveness of our pruning strategy and supports the reduction in processing times of Figure (a)-
Processing Time with Large Step Size. Since the error bound of upper and lower bounds depends on | 0t 12 in Equation (6). a large step size may incur potential decrease the pruning rate and our method may be slow down. To address this concern, we conducted an experiment to evaluate the processing times with an increased step size. We increased the step size 10 times larger than that used in Figure (a) on the gisette dataset. Figure [ (g) shows the results, exhibit similar trend to Figure (a). Our method was able to speed up IH'T even with the larger step size. This success is due to our automatic determination of 1", which adjusts the pruning rate during optimization, as described in Definition 4 and Equation (8). In contrast, AccIHT failed to converge in some cases due to the momentum, preventing us from evaluating the processing times for those instances. While
8

---

10
IHT
(ccl-1T(0.0255)
107
Regllmmi/100)
Accl11T(0.25)
wellokkk time
AcalHT12255)
clock time
207
ReglliTiK)
(ours))
30
107
20
180
1280
640
(a) gisette
(b) robert
107
105
L00 mal dbok Sme 15
walk time
20*
1PP
107
10
10
10
10
20
80
160
320
640
1280
10
40
80
320
640
(c) ledgar
(d) real-sim
11P
FastiHT(ours)
Log walt obok tne
2.5
2.0-
10
1.5
1.0-
10
10
20
40
80
180
320
640
1280
80
10
40
80
160
3.0
640
1280
(e) epsilon
(f) Number of computations
AociHTio 025)
RegiHTW/00)
AcclHTio 25)
Log wal dooktime
RegiHT//10)
AocIHT(2.5)
RegiHT())
Fasti--T(uur))
107-
10?
10
20
40 80
180
320
640
1280
gisette with large step size
Figure 1: (a)-(e): Comparisons log processing times for each dataset and (f): Comparison of number of gradient computations on gisette. (g): Comparisons of log processing times for gisette with large step size. Some results of AcclHT are omitted since they could not converge.
AcclHT reduces the number of iterations by using the momentum, method reduces the cost per iteration on the basis of the pruning strategy. This result shows an advantage of the pruning approach.
5.2 Accuracy
Theorem guarantees that our method achieves the same results as the plain IHT. To verify the theorem, we compared the objective values between our method and the plain IHT. Table shhows the results for k {1. 20, 160, 1280), and our method achieved the same objective values as the plain IHT. We obtained the same trend results as above also yielded the same support of nonzero elements in the parameter vector and their coefficients the plain IHT though the results are omitted. These results support our theoretical result for Theorem In addition, method also ensures that the parameter vector of each iteration matches perfectly
other settings of We note that our method

---

Table 1: Objective values of the plain IHT and our method for {1, 20, 160, 1280).
dataset
method
k =
k = 20
k = 160
k == 1280
gisette
IHT
56.01 x 10
31.99
10-2
14.01 10
80.73 10
ours
56.01 x 10-2
31.99 x 10-2
14.01 x 10-2
80.73 x 10-3
robert IHT
99.03 x 10-1
91.23 x 10-1
73.56
10-1
66.24 10
ours
99.03 x 10-1
91.23 x 10-1
73.56 x 10-1
66.24 x 10
ledgar
IHT
12.76 x 102
82.48 10'
50.70 10
35.35 10
ours
12.76 x 10²
82.48 X 10'
50.70 x 10'
35.35 x 10'
real-sim
IHT
86.47 x 10-2
63.84 10-2 2
40.32
10-2
23.16 10
ours
86.47 x 10-2
63.84 X 10-2 2
40.32 x 10-2
23.16 X 10
epsilon
IHT
93.50 x 10-2
67.24
10-2
44.93
10-2
43.03 10-2
ours
93.50 x 10-2
67.24 x 10-2
44.93 x 10-2
43.03 x 10
with that of the plain IHT from Lemma 4 This property is not obtained in previous acceleration methods based on the momentum such AccIHT.
Conclusion
We accelerated iterative hard thresholding (IHT) by safely pruning unnecessary gradient computations. The main idea is efficiently maintain the candidate set, which contains indices of nonzero elements in the parameter vector, during optimization. Before computing the gradients for each iteration, we prune unnecessary elements for the candidate set by utilizing the upper bound. To raise the pruning rate, we update the threshold to determine whether an element is included or not in the candidate set by using the lower bound. Our method guarantees the same optimization results as the plain IHT because pruning is safe. In addition, it does not need additional hyperparameter tuning. Experiments show that our method is up to 73 times faster than IHT without degrading accuracy. As future work, we plan extend our method to general convex loss functions with sparsity-inducins norms to enhance more applications.
References
[1] K. Axiotis and M. Sviridenko. Sparse Convex Optimization via Adaptively Regularized Hard Thresholding. Journal of Machine Learning Research (JMLR), 22(122):1-47, 2021.
[2] K. Axiotis and M. Sviridenko. Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions without Sacrificing Runtime. In Proceedings of International Conference on Machine Learning (ICML), pages 1175-1197, 2022.
[3] A. Beck and M. Teboulle. A Fast Iterative Shrinkage-Thesholdiig Thresholding Algorithm for Linear Inverse Problems. SIAM Journal on Imaging Sciences, 2(1):183-203: 2009.
[4] Blumensath. Accelerated Iterative Hard Thresholding. Signal Process., 92(3):752-756, 2012.
[5] Blumensath and Davies. Iterative Thresholding for Sparse Approximations. Journal of Fourier Analysis and Applications, 14:629 -654, 2008
[6] T. Blumensath and M. Davies. Iterative Hard Thresholding for Compressed Sensing. Applied and Computational Harmonic Analysis, 2763):26,-274, 2009.
[7] A. Boishunon, R. Flamary, and Rakotomamonjy. Active Set Strategy High-dimensional Non-Convex Sparse Optimization Problems. In Proceedings of International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1517-1521. IEEE, 2014.
[8] V. Cevher. Accelerated Hard Thresholding Methods for Sparse Approximation. In Wavelets and Sparsity XIV, volume 8 8388, 2011.
10

---

[9] C. Chang and C. Lin. LIBSVM: A Library for Support Vector Machines. ACM TIST, 2(3): 27:1-27:27, 2011.
[10] W. Dai and O. Milenkovic. Subspace Pursuit for Compressive Sensing Signal Reconstruction. IEEE Trans. Inf. Theory, 55(5):2200-2249, 2009.
[11] S. Foucart. Hard Thresholding Pursuit: An Algorithm for Compressive Sensing. SIAM J. Numer. Anal., 49(6))2543-2566) 2011.
[12] Y. Fujiwara, Y. Ida, J. Arai, M. Nishimura, and S. Iwamura. Fast Algorithm for the Lasso based LI- LI-Graph Construction. Proc. VLDB Endow. 10(3):22-2400, 2016.
[13] Y. Fujiwara, Y. Ida, H. Shiokawa, and S. Iwamura. Fast Lasso Algorithm via Selective Co- ordinate Descent. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 1561-1567, 2016.
[14] R. Garg and R. Khandekar. Gradient Descent with Sparsification: An Iterative Algorithm for Sparse Recovery with Restricted Isometry Property. In Proceedings of International Conference on Machine Learning (ICML), pages 337-344, 2009.
[15] Y. Ida, Y. Fujiwara, and H. Kashima. Fast Sparse Group Lasso. In Advances in Neural Information Processing Systems (NeurIPS), pages 1702-1710, 2019.
[16] Y. Ida, S. Kanai, Y. Fujiwara, T. Iwata, K. Takeuchi, and H. Kashima. Fast Deterministic CUR Matrix Decomposition with Accuracy Assurance. In Proceedings of International Conference on Machine Learning (ICML). pages 4594 4603, 2020.
[17] Y. Ida, S. Kanai, K. Adachi, A. Kumagai, and Y. Fujiwara. Fast Regularized Discrete Optimal Transport with Group- Sparse Regularizers. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pages 7980-7987, 2023.
[18] Y. Ida, S. Kanai, and A. Kumagai. Fast Block Coordinate Descent for Non-Convex Group Regularizations. In Proceedings of International Conference Artificial Intelligence and Statistics (AISTATS), pages 248 14493,, 2023.
[19] P. Jain, A. Tewari, and I. S. Dhillon. Orthogonal Matching Pursuit with Replacement. In Advances Neural Information Processing Systems (NeurIPS), pages 1215-1223, 2011.
[20] Jain, A. Tewari, and P. Kar. On Iterative Hard Thresholding Methods for High-dimensional M- Estimation. In Advances in Neural Information Processing Systems (NeurlPS), pages 685-693, 2014.
[21] T. Johnson and C. Guestrin. Blitz: A Principled Meta-Algorithm for Scaling Sparse Opti- mization. In Proceedings of International Conference on Machine Learning (ICML), pages 1171-1179, 2015.
[22] T. B. Johnson and C. Guestrin. StingyCD: Safely Avoiding Wasteful Updates in Coordinate Descent. In Proceedings of International Conference on Machine Learning (ICML), pages 7762,1760, 2017.
[23] R. Khanna and A. Kyrillidis. IHT Dies Hard: Provable Accelerated Iterative Hard Thresholding. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pages 188-198, 2018
[24] A. Kyrillidis and V. Cevher. Recipes on Hard Thresholding Methods. In IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, pages 353-356, 2011.
[25] Mallat and Z. Zhang. Matching Pursuits with Time- Time-Frequency Dictionaries. IEEE Transac- tions on Signal Processing, 41(12):3397-3455, 1993.
[26] M. Massias, J. Salmon, and A. Gramfort. Celer: Fast Solver for the Lasso with Dual Extrapolation. In Proceedings of International Conference on Machine Learning (ICML), pages 3321-3330, 2018
11

---

[27] D. Needell and J. Tropp. CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples. Applied and Computational Harmonic Analysis, 26(3):301-3211 2009.
[28] Y. Nesterov. A Method for Solving the Convex Programming Problem with Convergence Rate O(1/k²), Proceedings of the USSR Academy of Sciences, 269:543-547, 1983.
[29] Y. C. Pati, R. Rezaiffar, and P. S. Krishnaprasad. Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decompositio.. Proceedings of 27th Asilomar Conference Signals, Systems and Computers, pages 40 44, 1993.
[30] K. Qiu and Dogandžić. Double Overrelaxation Thresholding Methods for Sparse Signal Reconstruction. In Annual Conference on Information Sciences and Systems, pages 1-6, 2010.
[31] A. Rakotomamonjy, R. Flamary, J. Salmon, and G. Gasso. Convergent Working Set Algorithm for Lasso with Non-Convex Sparse Regularizers. Proceedings of International Conference on Artificial Intelligence and Statistics (AISTA7S), pages 5196-5211 2022.
[32] C. J. Rozell, D. H. Johnson, R. G. Baraniuk, and B. A. Olshausen. Sparse Coding via Thresh- olding and Local Competition in Neural Circuits. Neural Comput., 20(10):2526 2563, 2008.
[33] Sulam, B. Ophir, M. Zibulevsky, and M. Elad. Trainlets: Dictionary Learning in High
Dimensions, IEEE Trans. Signal Process., (0(12):3180-31193 2016.
[34] Vanschoren, N. van Rijn, B. Bischl, and L. Torgo OpenML: Networked Science in Machine Learning. SIGKDD Explorations, 15(2):99-60, 2013.
[35] X. Yuan, P. Li, and T. Zhang. Gradient Hard Thresholding Pursuit for Sparsity- Constt--Conttrainedd Optimization. Proceedings of International Conference on Machine Learning (ICML), pages 127-135, 2014.
12

---

Appendix
A Proofs
A.1 Lemma
Proof From Equation
we obtain the following equation:
z'
x' + x""
nX- x) +x 1 yI X)O + nx y -I- X)0 -1x1
G0" + +xx y G( )²))
By using the triangle inequality and the Sauchy-Schwarz inequality, we have the following inequality from the above equation:
x < G, + + 4)11 + |G -0)0
$ GG, + n(( y)11 + |G 8"
which completes the proof.
A.2 Lemmal 2
Proof Computing 1 -0012 in Equation { requires ((n) time. Therefore, the cost of Equation (4) at the t-th iteration is (n) time if G. X y and G (n( y)5 are precomputed.
A.3 Lemma 3
Proof If 1f holds for j Dt, we obtain | 2 [2]]_from z 2 |2/]1
I. In this case, since 1 is the minimum for all DD' |zy] cannot be larger than [z]] all D.. Therefore, cannot be included in D
A.4 Lemma 4
if 2t テ holds for j $ D', j cannot be included in Di++1 by Lemma (line 5), In addition, Pimin does not decrease compared to the previous |2|,.... wwen it is updated at line 11. Therefore, 12fm.. Σ always holds even after | is updated. As result, since lz)] cannot be included in the k-largest elements in the magnitude z", cannot be included in supp(er+1). If [ < 2 holds (line 7), Algorithm 2 exactly computes z) (line 8) and checks whether |z4] included or not in the k-largest elements in the magnitude of (lines 9-13). Therefore, this part exactly computes g++1 = Hx(z') ) j. Since j cannot be included in supp(0*+3) for the case of |=!_.. 2 z and the other case exactly computes 0++1 Hx(2²²), zt matches 0 In addition, since De+1 supp(2²) holds from line 10, D1+1 matches supp(0
Proof In Algorithm
A.5 Lemma
Proof For un-pruned j at line in Algorithm 2 computing z² (line 8) requires (n) time if G and X are precomputed. When |2( < 12 holds (line 9), we need to find 2 in Di+1 in addition to the above computation. The cost is O(k) time because of (D'| k. Because the number of un un-pruned computations u, the total cost of Algorithm O(u(n + k)) time. At this time, since k 4 n, the final cost is ((u)) time.
If Algorithm 2 cannot prune any computation for j & Dt. the number of un-pruned computations equals k. Since k <. n,, the worst time complexity is O(n") time.
13

---

A.6 Lemma
Proof Similarly to the proof of Lemma 7 we obtain the following inequality by using Equation 2 the reverse triungle inequality and the Sauchy-Schward inequality:
2 2 |G,0* + ( 5)sl -G 00
2 2G,,0 + + 4)11
|G,|l2|0* 0² 12.
which completes the proof.
A.7 Lemma
Proof Similarty the proof of Lemma computing 100 0² 12 in Equation requires O(n)
time. Therefore, the cost of Equation at the t-th iteration ((n) time if G, X y and [G,0
((x y) are precomputed.
A.8 Lemma
Proof When Limmi 23 holds, | |2]1 holds because we have 2) < 12]]- Since |z]]
larger than b Pmin which is the minimum |z] for E D', j is included Dt+11
A.9
Lemma 9
Proof When Isf 2) holds at line 5 in Algorithm the corresponding [z]] is larger than | since we have 2] < |25]- In addition, z!_... is set to zero at line 8. Thus, the absolute value of the new Ayg found at line 9 is equal to or larger than the old one. If If is not updated in Algorithm
equal to the initial | Therefore, |z! 2 12) holds.
A.10 Lemma 10
Proof Similarly the proof of Lemma computing z} (line 7) requires ((r)) time in Algorithm if G and X are precomputed. In addition, we need to find 2 in DD at O(k) time (line 9).
Therefore, the total cost of Algorithm is O(I(n + time. At this time, since k & n, the final cost (In) time.
all j & D' are determined be included in Dt line its number is l - k. Since < n, the worst time complexity is O(n²) time.
A.11 Lemma
Proof From Equations 4 and 5
= -0" = Then, for the upper bound,
1z! z11 S |z] z Ej holds. Similarly to the upper bound, also obtain the inequality in the lemma for the lower bound.
A.12 Theorem 1
Proof For line 3 in Algorithm 4 computing and X require On?'m) and O(nm) times, respectively. Next, lines 6 and 7 require O(n²) and O(n log k) times, respectively. Since lines 6-11 are performed T T/(r (r +1) times, the cost of this part is O(n ( (r+1)))))))))) time. For lines 13-21, the costs of O(nk) (line 13), O(n) (line 14), O(k) (line 15), ((In) (line 16), O(n) (line 17), and O(un) (line 18) are required. Since this part is performed r' times, the cost represented as O(n(I' + + + 7'k)) time by using l' and u/. Therefore, the total cost of Algorithm O(n' (n22mm++++ +I +n((' + +T(k) time.
The case of = and k yields the worst time complexity. In this case, the cost of lines 13-21 is O(r'n2) time. addition, the cost of lines 6-1 can be represented as O((T r')n²) time. As a result, the cost is O T)) time.
14

---

A.13 Theorem 2
Proof For lines 6-7 in Algorithm line returns the same 8 as line Algorithm D since both procedures are the same. Line 19 in Algorithu also returns the same 0 as line in Algorithm because of Lemmma Thus, the sequence of ft in Algorithm the same as that of Algorithm 1 both algorithms have the same hyperparameters. Therefore, Algorithm rrturns the same parameter vector and objective value as Algorithm
A.14
Theorem 3
Proof 1f0' 0t holds, 110' - -0" -0holds in Equation 6 Lemma
As a result, we obtain = in
77
B Computation Cost of IHT with Sparse Matrices
If G and X are precomputed, the cost of the gradient computations in IHT is (n²)) time due to the third equation of Equation 2 we use sparse matrix the parameter vector, the cost (nk) time. However, since the parameter vector changes for each iteration and the sparse matrix must be re-constructed for each itcration, it rarely used for the parameter vector in practice due to the overhead of the sparse matrix construction We note that the sparse matrices may be used for the design matrices whose elements do not change for each iteration.
C Broader Impacts
This paper presents work whose goal is advance the field of machine learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
htt./////a.aacaae/oi//oooo/a//aa Iode Lasso.
html
15

---

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: Our abstract and introduction include the following contributions: (i) we accel- erate iterative hard thresholding (IHT) method by pruning unnecessary computations, (ii) our method guarantees the same optimization results as the plain IHT, and (iii) Experiments show that our method is up to 73 times faster than the plain IHT without degrading accuracy.
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 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 not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The processing time of our method increases when & becomes large (Sec-
tion 5.1p. Nevertheless, our method outperformed all the baselines.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
16

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We have stated assumptions in all the lemmas and theorems, e.g., precomputa- tion. All the proofs described in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have described datasets, hyperparameters, and hardware used in the experiment (Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a 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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way 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 (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
17

---

5. Open access to data and code
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?
Question:
Answer: [No]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/ sublic/guides: htegll//guuiess/ooeebbbiissssss
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips cc/
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, 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 (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have described datasets, hyperparameters, and hardware used in the experiment (Section 5)
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not reported because the basclines are too computationally expensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run 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).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It 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 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 reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have described datasets, hyperparameters, and hardware used in the experiment (Section
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics Ethics/https: http://///eaaessscccppc/c//cccca
Answer: [Yes]
Justification:
The paper follows the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there 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: [Yes]
Justification:
The section of broader impacts is provided in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
19

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess 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 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 an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used 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 to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not release models or datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but 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: [No]
Justification: The datasets used in this paper cited in Section 5 However, we were unable to find the license for the datasct we used.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a 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.
20

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information 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: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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:
The paper does not involve crowdsourcing nor research with human subjects.
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 in the main paper.
According to 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 institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
22


Reviews:
[{"review_id": "8Vf0R5JPIr", "reviewer": "Reviewer_Hc1f", "summary": "The authors accelerate the iterative hard thresholding (IHT) method, whose purpose is to find the k most important elements from a linear regression model. Specifically, they safely prune unnecessary elements with upper bounds on the element values. The experiment shows significant speedup for the proposed method.", "questions": "Is it possible to include more experiments from the other use cases mentioned in the paper such as sparse coding, dictionary learning, or compressed sensing, preferably of a larger scale?", "limitations": "Yes, the authors discuss the limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method comes with theoretical guarantees and exhibit significant empirical speedup.", "weaknesses": "The importance of the work seems to be not clearly conveyed. The evaluation is also limited. While providing significant speedup, for the scale of the problem considered, the wall time of the baselines still seems to be within a tolerable range.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We extend our sincere gratitude to the reviewer for working on our paper. We address the weaknesses and questions raised by the reviewer below.\n\n> The importance of the work seems to be not clearly conveyed.\n\nA1. As mentioned in lines 13—15, IHT is widely used in various fields, such as feature selection, sparse coding, dictionary learning, and compressed sensing. The original paper of IHT [6] has thereby been cited more than 2800 times. However, if design matrix $X$ is large, IHT suffers from high computation costs of gradient computations as described in 25—32. For instance, in our experiment of feature selection task, IHT requires over 24 hours for the total processing time, including hyperparameter search on the ledger and epsilon datasets, as shown in Figure 1 (c) and (e). Furthermore, in our answer of A3 below, we conducted an additional experiment on the image compressive sensing recovery task, and the baselines could not complete the task within 4 days. Our method completes all experiments, including additional experiments, within 24 hours, and we believe it can contribute to reduce the processing times required for many tasks using IHT.  \n\nFrom a technical point of view, although accelerating IHT is the critical issue as described above, the number of approaches to accelerate IHT has been limited due to the non-convexity caused by $\\ell_0$ cardinality constraints in Problem (1). As mentioned in lines 245-246, the previous approaches have reduced the number of iterations to accelerate IHT. In contrast, our approach reduces the computation cost per iteration by pruning unnecessary computations. Therefore, our method will provide a new direction for the acceleration of IHT. As illustrated in Figure 1, our approach significantly enhances the speedup factor compared to baselines using the previous approaches. We would like to incorporate this explanation into the beginning of our paper.\n\n> The evaluation is also limited. While providing significant speedup, for the scale of the problem considered, the wall time of the baselines still seems to be within a tolerable range.\n\nA2. We thank the reviewer for highlighting that issue. Regarding the comparison of processing times in Figure 1, the processing time for each $k$ and hyperparameter falls within a tolerable range. However, in our experiments, the total processing time for each baseline on the ledger and epsilon datasets exceeded 24 hours. While the acceptable range of processing time is subjective, many practitioners would likely find more than a day impractical. In contrast, our method took less than 24 hours, even for the ledger and epsilon datasets. We would like highlight that we conducted an additional experiment on the image compressive sensing recovery task, and the baselines could not complete the task within 4 days as we will explain in our answer of A3 below.\n\n> Is it possible to include more experiments from the other use cases mentioned in the paper such as sparse coding, dictionary learning, or compressed sensing, preferably of a larger scale?\n\nA3. We are grateful for the constructive feedback. We conducted an additional experiment on the image compressive sensing recovery task by following [a]. Although our experimental setting was almost the same as in Section 5 of [a], we used a large image with 2728$\\times$2728 resolution. Consequently, the number of image blocks was 348,843. We investigated $k = [1, 8, 16, 24, 32]$ and evaluated the total processing times, including hyperparameter search. Our method completed the experiment in approximately 10 hours. Unfortunately, all other methods could not complete the experiment within the author's response period (4 days). The strong baselines of AccIHT and RegIHT also could not finish the experiment because they require additional hyperparameters for the weight step size and the momentum step size, respectively. We would like to highlight that our method does not require any additional hyperparameters, in contrast to AccIHT and RegIHT.\n\n[a] J. Zhang, C. Zhao, D. Zhao, and W. Gao, “Image compressive sensing recovery using adaptively learned sparsifying basis via L0 minimization”. Signal Process. 103: 114-126, 2014.", "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": "asVHERmcLM", "reviewer": "Reviewer_Lxri", "summary": "The paper proposes to pruning the computation of marginal gradients in the IHT algorithm to accelerate the updating steps. For that, the upper bound $\\overline{z}_j^{t}$ of the component $z_j^t$ in the gradient step is proposed in Definition 1 and  unnecessary elements in $\\mathbf{z}^t$ that must be thresholded to zero can be identified.", "questions": "There are some minor questions.\n1. Line 42-45 is duplicated with the abstract.\n2. Definition 2 is less informative. It generally says nothing about the construction of the candidate set $\\mathbb{D}^t$. \n3. The performance seems highly sensitive to the selection of $t^\\ast$.\n4. The proposed method seems only suitable when the learning rate $\\eta$ is small and the parameters update gradually. When a larger learning rate is used or the momentum is introduced as in the related work (Section 4), the pruning may no longer take effect.", "limitations": "The limitation seems not addressed in the paper. My comments about it are already in the above sections of Weaknesses and Questions.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The proposed fast IHT is save in the sense that it can achieve the same output as original IHT.\n- Pruning the unnecessary marginal gradient computation significantly saves computation costs when the sparsity $k$ is small. The idea is simple yet effective. \n- Good empirical performance.", "weaknesses": "- The proposed upper/lower bounds seem to be very restricted to the structure of the sparse linear regression task. And the proposed method does not work when general convex loss functions are considered.\n- For the sparse linear regression task, there are already efficient algorithms. For example, the cordinate descent algorithm uses in `glmnet`, which only needs to compute one dimension of marginal gradient in per iteration. The comparation beyond the IHT-type algorithm is ignored in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s constructive comments on our paper. To begin, we address the questions raised by the reviewer below.\n\n> 1. Line 42-45 is duplicated with the abstract.\n\nWe thank the reviewer for this comment. We will revise those sentences accordingly.\n\n> 2. Definition 2 is less informative. It generally says nothing about the construction of the candidate set $\\mathbb{D}^{t}$. \n\nWe are grateful to the reviewer for this comment. We will revise the manuscript to write it as a paragraph rather than a definition.\n\n> 3. The performance seems highly sensitive to the selection of $t^*$.\n\nWe greatly appreciate the reviewer for highlighting this critical point. The problem of sensitivity of $t^*$ is solved by the automatic determination of $t^*$ as described in lines 194-215. Specifically, the proposed method automatically adjusts $t^*$ during optimization to enhance performance, thereby eliminating the need to select $t^*$. According to Lemma 11, the error bounds of the upper and lower bounds may increase depending on the value of $t^*$, potentially reducing the pruning rate described in Definition 4 and consequently affecting performance. However, our method monitors the pruning rate and automatically adjusts $t^*$ to prevent a decrease in the pruning rate. Specifically, if the pruning rate decreases during optimization, the interval until the next $t^*$ is reduced following Equation (8). From Lemma 11, we know that the error bound of the upper and lower bounds tends to decrease when the interval until the next $t^*$ is small. Thus, this automatic adjustment of $t^*$ helps maintain the pruning rate.\n\n> 4. The proposed method seems only suitable when the learning rate is small and the parameters update gradually. When a larger learning rate is used or the momentum is introduced as in the related work (Section 4), the pruning may no longer take effect.\n\nAlthough the pruning rate might decrease due to the introduction of a large learning rate or momentum, the proposed method can adjust the pruning rate by automatically determining $t^*$ during optimization, as mentioned in our previous response.\n\nTo demonstrate this, we conducted an additional experiment with a learning rate on the gisette dataset. The results are shown in PDF file in the global response. In the experiment, we increased the learning rate to 10 times that used in the experiment of Figure 1 (a) in our paper. The results exhibit a similar trend to Figure 1(a). Our method could accelerate IHT even with a large learning rate. We would like to highlight that all the objective values of AccIHT, which utilizes the momentum, diverged with the setting of $k=1280$, and we could not evaluate the processing times. This suggests that the method with momentum tends to fail when a large learning rate is used in our setting. In contrast, the methods without momentum, including our proposed method, converged in all settings. We would like to incorporate this finding into our paper.\n\nFinally, we would like to mention that even if the pruning rate of the proposed method is low, its worst time complexity remains the same as the original IHT (lines 218-224).\n\n> To Weaknesses:\n\n> The proposed upper/lower bounds seem to be very restricted to the structure of the sparse linear regression task. And the proposed method does not work when general convex loss functions are considered.\n\nAs the reviewer pointed out, the proposed method is specialized for sparse linear regression with $\\ell_0$ cardinality constraints. We agree that extending our method to general convex loss functions is important, and we plan to address this in future work. We would like to mention that the sparse linear regression with $\\ell_0$ cardinality constraints is widely used in various fields, such as feature selection, sparse coding, dictionary learning, and compressed sensing, as described in lines 13--15. Although we performed a feature selection task in our experiment, we conducted an additional experiment on an image compressive sensing recovery task in response to Reviewer Hc1f. Our method completed the experiment in approximately 10 hours, while all other methods could not complete it within the author response period (4 days). We think that our method can contribute to reduce the times required for many tasks using IHT.\n\n> For the sparse linear regression task, there are already efficient algorithms. For example, the cordinate descent algorithm uses in glmnet, which only needs to compute one dimension of marginal gradient in per iteration. The comparation beyond the IHT-type algorithm is ignored in the paper.\n\nWhile it is true that there are many algorithms for accelerating sparse linear regression, the non-convexity due to $\\ell_0$ cardinality constraints in Problem (1) of our paper limits the number of available acceleration methods, which is a crucial motivation for proposing our method. For instance, the coordinate descent method of glmnet, mentioned by the reviewer, is specialized for convex optimization with $\\ell_1$ regularization, such as lasso and elastic net, and therefore cannot be used for the non-convex optimization with $\\ell_0$ cardinality constraints in Problem (1). Similarly, screening [a] and working set algorithm [b] also accelerate sparse linear regression tasks but rely on the computation of a duality gap based on convex optimization and are not applicable to Problem (1). Although lines 245-252 of our paper contain a similar explanation, we believe that incorporating the above discussion will enhance the paper's readability, and we would like to reflect this in the revised manuscript.\n\n[a] O. Fercoq, A. Gramfort, J. Salmon, \"Mind the duality gap: safer rules for the Lasso\", ICML, 2015.\n\n[b] M. Massias, J. Salmon, and A. Gramfort, \"Celer: a Fast Solver for the Lasso with Dual Extrapolation\", ICML, 2018.\n\n> To Limitations:\n\nWe intend to incorporate the above discussion into our paper. We sincerely appreciate the reviewer’s helpful comments.", "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": "tNaNwbrg69", "reviewer": "Reviewer_abvp", "summary": "This paper studies iterative hard thresholding (IHT) as a canonical method for sparse linear regression. With precomputed X^TX and X^Ty, the computational cost of the algorithm is dominated by the gradient updates. To reduce the computational cost, this work proposed a pruning procedure at each step of IHT to only compute certain elements of the gradient vector.", "questions": "* I find the terminology \"pruning\" a bit confusing. My understanding is that it refers to setting a particular entry  $z_j^t$ to zero depending on whether or not $\\bar{z}_{j}^t $ is less than     a certain threshold. Is this correct? If yes, then maybe \"thresholding\" is a better terminology?\n* By \"pruning is safe\", do you mean that the pruning step does not compromise the accuracy of IHT at all? Can you prove this more explicitly?\n* I think X^TX takes O(n^2m) computational cost instead of O(mn)?\n* Did you mean to use f(\\theta) instead of 1/2||y-X\\theta||_2^2 in (1)?", "limitations": "I'd suggest the author add one or two sentences in the final Section to discuss the limitations of this work.", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "Reducing the computational cost of IHT is an interesting and important problem.\nNumerical results indicate a significant reduction in running time by employing the pruning procedure proposed in the paper, without compromising the estimation accuracy.", "weaknesses": "Major:\n* It is unclear to me why the pruning strategy is defined the way it is. \n* Consider adding more literature review: it is not clear how big of a gap exists in the literature that this work is trying to bridge. Section 4 Related Work feels out of place. Could consider moving this to the beginning of the paper. \n* A general suggestion: consider adding more explanation on the rationale behind each technical definition/ result and why it is defined/ stated in that particular way. For instance, it may be helpful to mention that Lemma 1 is derived from the triangle inequality + Holders inequality.\n* I think some definitions are stated in the form of lemmas which they should not be, e.g. Lemmas 3 and 8. In general, I think some lemmas are unnecessary or can be combined.\n* Presentation is a bit long-winded at places, e.g. third paragraph\n\nMinor:\n* “73 times”: a more precise statement may be more useful; briefly describe the dimensions of the problem etc\n* line 60: it is more consistent to use “problem in (1)” instead of “Problem 1”\n* Notation: \n    * I find it more natural to use boldface X as the design matrix\n    * it is a bit confusing to denote the hard thresholding operator by Pk, hk is more common\n    * \\mathbb{D}^t and \\mathbb{I} are unconventional notations for sets. Use \\mathcal{D}^t and \\mathcal{I} instead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thoughtful review of our paper. Below are our answers to the questions and weaknesses raised by the reviewer.\n\n> I find the terminology \"pruning\" a bit confusing. My understanding is that it refers to setting a particular entry $z_{j}^{t}$ to zero depending on whether or not $\\bar{z}^{t}_{j}$ is less than a certain threshold. Is this correct? If yes, then maybe \"thresholding\" is a better terminology?\n\nA1. Yes, that is correct. We chose the term \"pruning\" instead of \"thresholding\" to distinguish our procedure from the thresholding procedure of the hard thresholding operator $P_{k}$​. The thresholding of $P_{k}$ sets unnecessary $z_{j}^{t}$ to zero **after** computing the gradient and updating all the parameters. In contrast, our method's pruning sets unnecessary  $z_{j}^{t}$ to zero **before** computing the gradient and updating the parameters.\n\n> By \"pruning is safe\", do you mean that the pruning step does not compromise the accuracy of IHT at all? Can you prove this more explicitly?\n\nA2. Yes, our pruning method is theoretically guaranteed to maintain the same accuracy as the original IHT. This is demonstrated in Theorem 2, with detailed proof provided in the appendix. Below, we outline the proof:\n\n1. The original IHT selects the top-$k$ parameters in absolute values. In contrast, our method uses a candidate set $\\mathbb{D}^{t}$ with cardinality $k$, as described in Definition 2, and updates $\\mathbb{D}^{t}$ to include the top-$k$ parameters during optimization.\n\n2. At the beginning of each iteration, our method initializes $\\mathbb{D}^{t}$ to include the indices of the current top-$k$ parameters (line 103). For the parameters corresponding to $\\mathbb{D}^{t}$, we compute their gradients to obtain the exact $z_{i}^{t}$ for $i$ in $\\mathbb{D}^{t}$  (line 13 in Algorithm 4). We then set $z_{i_{\\rm min}}^{t}$ as the minimum $z_{i}^{t}$​ in $\\mathbb{D}^{t}$, as shown in Lemma 3.\n\n3. Next, we consider the upper bound of $z_{j}^{t}$​ for parameters not included in $\\mathbb{D}^{t}$. This upper bound  $\\bar{z}^{t}\\_{j}$  is given by Definition 1 and Lemma 1. If  $\\bar{z}^{t}\\_{j} \\leq z\\_{i\\_{\\rm min}}^{t}$ holds,​ $z_{j}^{t}\\leq z\\_{i\\_{\\rm min}}^{t}$ also holds.​ Therefore, the $j$-th parameter must not be included in $\\mathbb{D}^{t}$. In this case, the $j$-th parameter​ can be safely pruned without computing the gradient (Lemma 3). For parameters that do not satisfy the condition, our method exactly computes $z_{j}^{t}$​ as shown in line 8 of Algorithm 2. Consequently,  $\\mathbb{D}^{t}$ is exactly the same as the top-$k$ parameters of the original IHT (Lemma 4).\n\nAs described above, since our method prunes parameters that must be zero, pruning the corresponding gradient computations does not affect the final top-$k$ parameters. Additionally, our method not only achieves the same final accuracy as the original IHT but also ensures that the parameters during optimization match perfectly with those of the original IHT. We would like to highlight that this property is not found in previous methods such as AccIHT[19].\n\n> I think X^TX takes O(n^2m) computational cost instead of O(mn)?\n\nA3. In the part of $X^T(X\\theta^{t}-y)$ in Equation (2), we first compute $h=X\\theta^{t}-y$ at $\\mathcal{O}(mn)$ time, then compute $X^T h$ at $\\mathcal{O}(mn)$ time. Consequently, Equation (2) requires $\\mathcal{O}(mn)$ time. We would like to incorporate this explanation into our paper.\n\n> Did you mean to use f(\\theta) instead of 1/2||y-X\\theta||_2^2 in (1)?\n\nA4. Yes, for the sake of simplicity, we use the expression as stated in line 58.\n\n> I'd suggest the author add one or two sentences in the final Section to discuss the limitations of this work.\n\nWe thank the reviewer for this comment. The limitation of our method is that the speedup factor decreases for large $k$ as described in line 270-272. However, as demonstrated in Theorem 1, the worst time complexity of our method is the same as that of the original IHT. We will incorporate this explanation into the paper.\n\n> To weaknesses:\n\n> It is unclear to me why the pruning strategy is defined the way it is.\n\nKindly refer to our response in A2, which details the pruning strategy of our method and explains why this pruning strategy is safe. The point is that our method prunes unnecessary parameters before computing gradients by using upper bounds, which have small time complexity.\n\n> Consider adding more literature review: it is not clear how big of a gap exists in the literature that this work is trying to bridge. Section 4 Related Work feels out of place. Could consider moving this to the beginning of the paper.\n\nWe would like to move Section 4 to the beginning of the paper. As explained in lines 245-246, while previous acceleration methods for IHT have reduced the number of iterations, there has not yet been a method to accelerate IHT by reducing the computation cost per iteration. This paper aims to fill this gap based on the pruning strategy.\n\n> A general suggestion: consider adding more explanation on the rationale behind each technical definition/ result and why it is defined/ stated in that particular way. For instance, it may be helpful to mention that Lemma 1 is derived from the triangle inequality + Holders inequality.\n\nWe plan to explain the sketch of the proof and the reason for defining it before and after theorems and definitions, respectively.\n\n> I think some definitions are stated in the form of lemmas which they should not be, e.g. Lemmas 3 and 8. In general, I think some lemmas are unnecessary or can be combined.\n\nWe will revise the manuscript to write Lemmas 3 and 8 as normal paragraphs or definitions.\n\n> Presentation is a bit long-winded at places, e.g. third paragraph\n\nWe intend to shorten redundant expressions, such as those found in the third paragraph.\n\n> To minor comments:\n\nWe plan to revise the paper by incorporating these helpful suggestions, including the notations.", "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": "ur5CdXjmLj", "reviewer": "Reviewer_FTQw", "summary": "Iterative hard thresholding (IHT) is used to select the k most important features in an ordinary least squares (OLS) linear regression model, that is, the model parameter vector is constrained to have only k non-zero entries. It seems that most practical IHT methods to solve the constrained problem are based on gradient descent. The running time of iterative methods until convergence depends on (a) the computational cost of each iteration, and (b) the number of iterations. If we understand it correctly, previous work has focussed on reducing the number of iterations by using some form of regularization (improving the smoothness of the problem) or by exploiting information from previous iterations, such as, momentum. The paper under review seems first to propose a method for reducing the computation cost of the iterations by avoiding the computation of unnecessary entries in the gradient. This is achieved by maintaining upper and lower bounds for each entry of the full OLS parameter vector at each iteration. The bounds can be used to prune computations of unnecessary entries in the gradient. The method is guaranteed to give the same results as plain IHT.", "questions": "1. Would it be possible to combine your technique with techniques that aim to reduce the number of iterations? For instance, the techniques described in references 4 and 26, or 8 and 20?\n\n2. Why did you not include the methods from references 4, 26, 8, and 20 in your experiments? Are they superseded by references 2 and 19?", "limitations": "The scope of the problem addressed by the paper is clearly stated. Within this scope, I do not see limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem is well stated and relevant. The proposed idea to reduce the cost per iteration is, as far as I can tell, novel. Its realization is technically non-trivial, but well described. I have not checked the proofs in the appendix, but intuitively the results make sense.  In general, the paper is well written. Actually, I enjoyed reading it.", "weaknesses": "I do not see any major weakness. \n\nMaybe the presentation can be improved in some parts. Here are some suggestions:\n\nLine 51: m-dimensionAL vector\nLine 63:  ... if it uses a heap ...\nLine 137: The ASYMPTOTIC cost ... [in some situations the actual cost should be higher] \nLines 239 and 241: Avoid starting a sentence with references.\nTable 1: The information content is really low.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s positive feedback on our paper. As mentioned in the reviewer's comment, previous methods for accelerating IHT have focused on reducing the number of iterations. In contrast, our approach accelerates IHT by reducing the computation cost per iteration. Accelerating IHT is challenging due to its non-convexity, resulting from $\\ell_0$ cardinality constraints in Problem (1), and there are relatively few acceleration methods for IHT compared to those for $\\ell_1$ regularization, such as lasso. Therefore, we hope that the proposed method will offer a new direction for speeding up IHT.\n\nWe also thank the reviewer for the valuable suggestions on improving the presentation. We will revise the paper accordingly.\n\nBelow are our responses to the questions:\n\n> Would it be possible to combine your technique with techniques that aim to reduce the number of iterations? For instance, the techniques described in references 4 and 26, or 8 and 20?\n\nYes, it is relatively straightforward to combine these methods with our proposed method. This is because these methods utilize a linear combination of parameters to reduce the number of iterations. For example, the acceleration methods in [8] and [20] can be integrated with our method as follows:\n\n1. Compute the linear combination of parameters at the $t$-th iteration $\\phi^{t}$, by following Equation (21) in [8] or Equation (19) in [20].\n\n2. Set $\\theta^{t}=\\phi ^{t}$. Then, we can compute the upper and lower bounds using Equations (4) and (5) in our paper, respectively.\n\n3. Perform Algorithm 4 in our paper based on these upper and lower bounds.\n\nWe are currently working on combining these acceleration methods with our approach and appreciate the valuable feedback.\n\n> Why did you not include the methods from references 4, 26, 8, and 20 in your experiments? Are they superseded by references 2 and 19?\n\nWe sincerely thank the reviewer for the insightful comment. References [4, 26] utilize acceleration techniques known as double over-relaxation. However, the theoretical guarantees for these methods are limited. Specifically, the method in [26] lacks theoretical guarantee, and the method in [4] is guaranteed to converge only when the acceleration technique is applied under conditions where the objective function decreases. In contrast, [8, 20] provide convergence proofs when using Nesterov’s acceleration [24] and squared loss. Additionally, [19] examines the properties of the momentum step in Nesterov’s acceleration. Since the algorithms in [8, 20, 19] are almost the same, we consider [8, 20] to be superseded by [19] in our paper.\n\nUnlike the above methods, [2] adds squared $\\ell_2$ regularization to Problem (1), and is completely different from the above papers. Therefore, we have added it to the baseline in our experiment.\n\nWe would like to incorporate the above explanation into the related work section.", "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 working on our paper. We have received many constructive comments, which we intend to incorporate to improve the quality of our work. We believe we have addressed most of the comments and would be grateful if the reviewers could respond to our response.

In this global response, we have attached a PDF file containing additional experimental results. Some reviewers suggested that our method might be slow with a large learning rate due to a potential decrease in the pruning rate. To address this concern, we conducted an additional experiment to evaluate the processing times with an increased learning rate.

In the experiment, we increased the learning rate to 10 times that used in Figure 1(a) of our paper. The results, detailed in the attached PDF, exhibit a similar trend to Figure 1(a). Our method was able to speed up IHT even with the larger learning rate. This success is due to our automatic determination of $t^{*}$, which adjusts the pruning rate during optimization, as described in lines 194—215. In contrast, AccIHT failed to converge in some cases, preventing us from evaluating the processing times for those instances. We would like to incorporate these findings into our paper.

Meta-review: The paper proposes to pruning the computation of marginal gradients in the IHT algorithm to accelerate the updating steps. Experiemental results showed great speedup. Some reviewers raised scores after authors addressed review comments.
Decision: Accept (poster)