Fast Iterative Hard Thresholding Methods with Pruning Gradient Computations

Authors: yasutoshi  ida
sekitoshi  kanai
atsutoshi  kumagai
tomoharu  iwata
yasuhiro  fujiwara
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 10:45:15

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.

Main paper: 
 introduction: 
 The optimization problem of finding sparse parameter vectors in linear regression models is a crucial problem that crosses a wide range of fields, including feature selection [20, 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 k nonzero elements. Among a huge number of algorithms that have been developed for this problem [25, 29, 14, 27, 10, 19, 11, 20] , iterative hard thresholding (IHT) methods [6] are practical methods based on 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 a feasible set being a 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 to zero. IHT repeats this procedure until the stopping criterion is satisfied.When a 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(mn) or O(n 2 ) time for each iteration. Specifically, IHT suffers from the increase in processing time for large m and n. Taking feature selection as an example, IHT slows down for large datasets because m and n correspond to the numbers of samples and features in the dataset, respectively. The gradient computations are much more computationally expensive than the projection of the parameter vector because the projection only requires O(n log k) time if 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. This paper proposes fast IHT that safely prunes unnecessary gradient computations. Before computing the gradients for each iteration, the proposed method efficiently constructs a 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 is smaller than a threshold, the index is not included in the candidate set. The threshold is automatically determined by leveraging lower bounds of absolute values for the elements of the parameter vector. Since the computation cost of the upper and lower bounds is O(n) time, we 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 our method is up to 73 times faster than the plain IHT while maintaining accuracy on feature selection tasks.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 accelerate 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 in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 In [4, 30] , the authors utilized a double-overrelaxation approach to improve the convergence speed of IHT. They use two relaxation steps for the parameter vector, which are similar to the momentum of Nesterov's method [28] . In [8, 24] , the authors introduced the momentum to IHT inspired by the fast iterative shrinkage thresholding algorithm (FISTA) [3] . While FISTA uses the momentum with a soft thresholding operator, Cevher [8] uses it with the hard thresholding operator. This Accelerated IHT (AccIHT) has substantial theoretical and empirical improvement over the plain IHT [23] .While the previous methods have reduced the number of iterations to accelerate IHT as described above, to the best of our knowledge, there are no papers on reducing the computation cost per iteration of IHT. This paper aims to fill this gap based on the pruning strategy. For convex and some nonconvex regularization, working set algorithms are used to 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, 22, 15, 16, 18, 17] , the authors reduced the cost by skipping unnecessary parameter updates for coordinate descent with sparsity-inducing norms. However, since these methods are tailored for coordinate descent or the soft thresholding operator, they cannot be used for IHT, which selects k elements from the parameter vector by using the hard thresholding operator.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 k becomes large (Section 5.1). Nevertheless, our method outperformed all the baselines.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
preliminary: 
 Notation. We denote scalars, vectors, and matrices with lower-case, bold lower-case, and bold upper-case letters, e.g., x, x and X, respectively. Given a matrix X, we denote its i-th row by X i . Given a vector x ∈ R m , we denote its i-th element by x i , and we call i index. || • || 2 is the ℓ 2 norm. ||x|| 0 is |{i ∈ {1, ..., m}|x i ̸ = 0}| and represents the number of nonzero elements in x. 0 ∈ R m is the m-dimensional vector whose elements are zeros. I represents the identity matrix. supp(x) is the function that returns the indices of nonzero elements in x.Let X ∈ R m×n be an input matrix (design matrix), y ∈ R m be a set of continuous responses, and θ ∈ R n be a parameter vector of a linear regression model. To find a sparse parameter vector of the model, we consider the following optimization problem [5] :EQUATIONIn the above problem, the number of nonzero elements in the parameter vector, ||θ|| 0 , is constrained by k ∈ {1, ..., n}. Here, we will let f (θ) = 1 2 ||y -Xθ|| 2 2 for simplicity.IHT is the practical algorithm for Problem (1) [5, 2] . It repeatedly performs the following iteration: EQUATIONEQUATIONθ t+1 ← H k (z t ); t ← t + 1;▷ Selecting the k-largest elements in magnitude of z t 6: until a stopping criterion is met where η > 0 is the step size, θ t is the parameter vector at the t-th iteration. H k (z t ) is the hard thresholding operator that selects the k-largest elements in the magnitude of z t and sets the other elements to zero. The selection requires O(n log k) time if it uses a heap. The pseudocode is described in Algorithm 1. See [5, 14, 6, 8, 4, 20, 23, 2] for theoretical discussions of IHT.From Equation (2) and Algorithm 1, computing gradients ∇f (θ t ) clearly dominates the other cost. In Equation ( 2), we use the second equation or the third one to compute z t . They require O(mn) and O(n2 ) times in every iteration, respectively 2 . Therefore, IHT incurs high computation cost when X ∈ R m×n is large.• 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
proposed algorithm: 
 This section describes our algorithm that reduces the computation cost per iteration in IHT.The bottleneck of IHT is the gradient computation to obtain z t of Equation ( 2): it requires O(mn) or O(n 2 ) time per iteration. Therefore, we reduce the cost by pruning unnecessary elements in z t before computing the gradients. For the pruning, we introduce a candidate set D t such that |D t | = k for the t-th iteration. This set maintains indices of 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 t are included or not in D t+1 . If an index j is not included in D t+1 , we can prune z t j 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, our method utilizes z t j , which is an upper bound of |z t j |. Since the computation of the upper bound does not include the gradient computation, it only requires O(n) time for all the elements in z t . For the checking procedure, after initializing D t appropriately, our method finds a threshold for the pruning by utilizing z t j , which is a lower bound of |z t j |. Then, if z t j is smaller than the threshold for j ̸ ∈ D t , the index j is not included in D t+1 . We describe the details in the next section.This section introduces candidate set D t and its updating method. Since we need upper bound z t j to efficiently update D t as described in Section 4.1, we first define z t j as follows:Definition 1 Let t * be 1 ≤ t * < t in Algorithm 1. Then, z t j at the t-th iteration in Algorithm 1 is computed as follows:EQUATIONwhere G = I -ηX ⊤ X.We note that G and X ⊤ y are precomputed only once before entering the optimization, and t * is automatically decided as described in Section 4.4. z t j has the following property: To efficiently update D t to D t+1 , we utilize the upper bound z t j of Equation (4) for j ̸ ∈ D t . By using z t j , we can identify unnecessary elements in z t that are clearly not included in D t+1 as follows:Lemma 3 (Pruning unnecessary elements) Suppose that z t is computed by using Equation ( 4), and the candidate set D t is initialized as described in Definition 2 at the beginning of the iteration for t > 1. Let z t imin be z t i having the minimum |z t i | in all i ∈ D t , and i min be the index. Then, if|z t imin | ≥ z t j holds for j ̸ ∈ D t , j is not included in D t+1 .From Lemma 3, when we check whether j ̸ ∈ D t is included or not in D t+1 , we do not need to compute the gradient corresponding to z t j if |z t imin | ≥ z t j holds. Although we need to compute the gradients to find z t imin in the initial D t , the cost is relatively small because the cardinality of D t is usually small as|D t | = k ≪ n.Algorithm 2 is the pseudocode of updating the candidate set. It first copies D t to D t+1 (line 3). Lines 4-13 check whether the computation of z t j can be pruned or not by following Lemma 3. If the computation is pruned (line 5), we skip the computation of z t j including the gradient computation (line 6). If the computation is not pruned (line 7), line 8 computes z t j . If |z t imin | < |z t j | holds (line 9), the algorithm updates the candidate set D t+1 to remove i min and include j (line 10). In this case, z t imin must also be updated since D t+1 has been updated (line 11). If |z t imin | < |z t j | does not hold (line 12), we set z t j = 0 because j cannot be included in D t+1 (line 13). For the outputs z t and D t+1 of Algorithm 2, we have the following property: Lemma 4 (Consistency of outputs) For the outputs of Algorithm 2, z t = θ t+1 and D t+1 = supp(θ t+1 ) hold.The above lemma shows that Algorithm 2 returns the same θ t+1 and supp(θ t+1 ) as those of the plain IHT while it prunes unnecessary computations given z t imin , z t , and D t . Specifically, we can use Algorithm 2 instead of lines 4-5 in Algorithm 1.Lemma 5 (Computation cost of updating candidate set) Let u be the number of un-pruned computations at line 7 of Algorithm 2. If G and X ⊤ y are precomputed, Algorithm 2 requires O(un) time and the worst time complexity is O(n 2 ) 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 is high. On the other hand, the worst time complexity of O(n 2 ) time is obtained with a low pruning rate. The asymptotic cost cannot be larger than that of the plain IHT D t+1 ← (D t+1 \ i min ) ∪ j;11:z t imin ← 0; find z t imin in D t+1 ; 12:else 13:z t j ← 0; Algorithm 3 Update of threshold 1: Input: z t imin , z t , D t 2: Output: z t ′ imin , z t ′ , D t ′ 3: D t ′ ← D t 4: for j ̸ ∈ D t do 5: if |z t imin | < z t j then 6: D t ′ ← (D t ′ \ i min ) ∪ j; 7:compute z t j ;8:z t imin ← 0; 9: find z t imin in D t ′ ; 10: z t ′ imin ← z t imin ; 11: z t ′ ← z t ;since the gradient computation of the plain IHT requires O(mn) or O(n 2 ) time. Nonetheless, the pruning rate needs to be increased to achieve higher speeds.In Algorithm 2, |z t imin | plays the role of the threshold for pruning at line 5. Therefore, we can raise the pruning rate for a larger threshold of |z t imin | because |z t imin | ≥ z t j at line 5 is easier to hold for a larger threshold. The next section introduces an efficient way to update |z t imin | to a larger value before entering Algorithm 2.To update threshold |z t imin | to a larger value, we utilize the lower bound z t j such that |z t j | > z t j holds for j ̸ ∈ D t . z t j is defined as follows:Definition 3 Let t * be 1 ≤ t * < t in Algorithm 1. Then, z t j at the t-th iteration in Algorithm 1 is computed as follows:EQUATIONwhereG = I -ηX ⊤ X.The following lemma shows that z t j is the lower bound of |z t j |:Lemma 6 (Lower bound) We have z t j ≤ |z t j | when z t j is computed by Equation ( 5).Lemma 6 is derived from the reverse triangle inequality and the Cauchy-Schwarz inequality. Similarly to the computation cost of the upper bound, Equation ( 5) requires the following cost:Lemma 7 (Computation cost of lower bound) The computation cost of Equation ( 5) for all j ∈ {1, ..., n} at the t-th iteration is O(n) time given G, X ⊤ y and |G j θ t * + η(X ⊤ y) j |.To update |z t imin |, we utilize the following lemma:Lemma 8 (Indices required for candidate set) Suppose that z t is computed by using Equation ( 5), and the candidate set D t is initialized as described in Definition 2 at the beginning of the iteration for t > The computation cost of Algorithm 3 is as follows:Lemma 10 (Computation cost of threshold increase) Let l be the number of indices that are determined to be included in D t ′ at line 5 of Algorithm 3. If G and X ⊤ y are precomputed, Algorithm 3 requires O(ln) time and the worst time complexity of Algorithm 3 is O(n 2 ) time.Similarly to Lemma 5 of Algorithm 2, the worst time complexity is not much more than that of IHT.Algorithm 4 is the pseudocode of our method based on Algorithms 2 and 3. We first precompute G and X ⊤ y for the upper and lower bounds (line 3). The main loop consists of two types of procedures (lines 4-22): the procedure for t = t * (lines 5-11) and the procedure for t ̸ = t * (lines 12-21). For the case of t = t * , the algorithm updates the parameter vector the same as the plain IHT (lines 6-7) and computes the candidate set (line 8). We note that the computation result of line 6 is also used for computing the upper and lower bounds as shown in Definitions 1 and 3. Line 9 sets t * as t and line 10 computes an interval r ≥ 1 that determines which t is the next t * . Specifically, the next t * is determined as t * + r. The computation way of r is described later. r ′ is the variable that monitors the interval. If t = t * does not hold (line 12), it computes z t i for i ∈ D t by using Equation (2) (line 13). Next, line 14 computes the lower bound by using Equation ( 5) on 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 8 and 9 (line 16). Then, we compute the upper bound by using Equation (4) on the basis of Lemma 1 (line 17). Line 18 computes z t by using Algorithm 2 while pruning unnecessary computations on the basis of Lemma 3. This z t can be handled as θ t+1 by following Lemma 4 (line 19). We monitor the interval of the next t * 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 4, we need to compute interval r at line 10 to determine t * because θ t * appears in Equations ( 4) and ( 5) for computing the upper and lower bounds, respectively. Since the upper bound z t j and lower bound z t j are the approximation of z t j , we obtain the following error bound: Lemma 11 Suppose that ϵ j is computed as follows:EQUATION)Then, |z t jz t j | ≤ ϵ j and |z t jz t j | ≤ ϵ j hold.From the above lemma, the magnitude of error bound ϵ j depends on t * because of ||θ tθ t * || 2 in Equation ( 6). If we set r to a large value, the error bound can be large since ||θ tθ t * || 2 tends to be large. In this case, the bounds are loose and it is difficult to hold |z t imin | ≥ z t j in Lemma 3. As a result, the pruning rate will be low. On the other hand, if we set r a 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 r on the basis of the current pruning rate that is defined as follows: r ′ ← r ′ -1;t ← t + 1; 22: until a stopping criterion is met Definition 4 (Pruning rate) Let u t be the number of un-pruned computations at line 7 in Algorithm 2 for the t-th iteration as defined in Lemma 5. Then, we define pruning rate p t at line 10 in Algorithm 4 for the t-th iteration as follows:EQUATION)The unit of p t is percent. We compute r at line 10 in Algorithm 4 on the basis of p t as follows:EQUATION⌈•⌉ 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 r to ⌈r/2⌉ to reduce error bound ϵ j . 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 to be tight. This rule performs well in our experiments.The computation cost of Algorithm 4 is as follows:Theorem 1 (Computation cost) Let u ′ and l ′ be the total numbers of u and l in Lemmas 5 and 10 in Algorithm 4, respectively. Suppose that r is a constant for simplicity, τ is the total number of main loops in Algorithm 4, and τ ′ is the number for which line 12 holds. Then, the computation cost of Algorithm 4 is O(n 2 (m + τ r+1 ) + n(l ′ + u ′ + τ ′ k)) time, and the worst time complexity is O(n 2 (m + τ )) time.The plain IHT of Algorithm 1 requires O(n 2 (m + τ )) time if G and X ⊤ y are precomputed. Therefore, the worst time complexity of our method is the same as the cost of the plain IHT.For the optimization result, we obtain the following theorem: Theorem 2 (Optimization result) Suppose that Algorithm 4 has the same hyperparameters as those of the plain IHT of Algorithm 1. Then, Algorithm 4 yields the same parameter vector and objective value as Algorithm 1.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 3 (Convergence of upper and lower bounds) Suppose that Algorithm 4 converges as θ t = θ t * . Then, we obtain ϵ j = 0 for j ∈ {1, ..., n} where ϵ j is the error bound of the upper and lower bounds defined in Lemma 11.Theorem 3 shows that the upper bound z t j and lower bound z t j become the exact value of z t j when θ t = θ t * holds. Therefore, our method accurately prunes unnecessary computations when the condition is satisfied. 
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 × 5000, 10000 × 7200, 60000 × 19996, 72309 × 20958, and 400000 × 2000, respectively. We evaluated the processing time and accuracy on k = {1, 5, 10, 20, 40, 80, 160, 320, 640, 1280}. We compared our method with the plain IHT (IHT), Regularized IHT (RegIHT) [2] , and Accelerated IHT (AccIHT) [23] . RegIHT is the fastest method among the methods using an adaptive regularization technique [1] . Since RegIHT has the hyperparameter of weight step size c, we tried the setting of c = {k, k/10, k/100} on the basis of the original paper. AccIHT improves the convergence of IHT by utilizing the momentum. We tried µ = {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 η = 1/λ where λ is the largest eigen value of X ⊤ X by following [23] . We stopped these methods when the relative tolerance of the parameter vector dropped below 10 -5 [23, 15] . All the experiments were conducted on a 3.20 GHz Intel CPU with six cores and 64 GB of main memory.Figure 1 (a)-(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 is based on the pruning, it achieved a large speedup factor for smaller k. Even when k 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 determination technique described in Section 4.4. Specifically, practitioners only need to specify k to use our method the same as the plain IHT. On the other hand, the baselines of RegIHT and AccIHT require additional hyperparameter tuning for the weight step size and the momentum step size, respectively. Number of Gradient Computations. Figure 1 (f) compares the number of gradient computations between our method and the plain IHT on the gisette dataset. Our method reduced the number of computations by up to 98.87%. The result shows the effectiveness of our pruning strategy and supports the reduction in processing times of Figure 1 Processing Time with Large Step Size. Since the error bound of upper and lower bounds depends on ||θ tθ t * || 2 in Equation ( 6), a large step size may incur a potential decrease in 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 to 10 times larger than that used in Figure 1 (a) on the gisette dataset. Figure 1 (g) shows the results, exhibit a similar trend to Figure 1 (a). Our method was able to speed up IHT even with the larger step size. This success is due to our automatic determination of t * , 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 AccIHT reduces the number of iterations by using the momentum, our method reduces the cost per iteration on the basis of the pruning strategy. This result shows an advantage of the pruning approach.Theorem 2 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 1 shows 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 in the other settings of k. We note that our method also yielded the same support of nonzero elements in the parameter vector and their coefficients as the plain IHT though the results are omitted. These results support our theoretical result for Theorem 2. In addition, our method also ensures that the parameter vector of each iteration matches perfectly with that of the plain IHT from Lemma 4. This property is not obtained in previous acceleration methods based on the momentum such as AccIHT. 
conclusion: 
 We accelerated iterative hard thresholding (IHT) by safely pruning unnecessary gradient computations. The main idea is to 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 our 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 to extend our method to general convex loss functions with sparsity-inducing norms to enhance more applications. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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.• 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), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper does not release models or datasets.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 
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 are cited in Section 5. However, we were unable to find the license for the dataset we used.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include 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.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset 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. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as 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 in the supplemental material is fine, but if the main contribution 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. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA]Justification: 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. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the 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. 
 
 Appendix: Proof For lines 6-7 in Algorithm 4, line 7 returns the same θ t+1 as line 5 in Algorithm 1 since both procedures are the same. Line 19 in Algorithm 4 also returns the same θ t+1 as line 5 in Algorithm 1 because of Lemma 4. Thus, the sequence of θ t+1 in Algorithm 4 is the same as that of Algorithm 1 if both algorithms have the same hyperparameters. Therefore, Algorithm 4 returns the same parameter vector and objective value as Algorithm 1. □ A.14 Theorem 3Proof If θ t = θ t * holds, ||θ tθ t * || 2 = 0 holds in Equation ( 6). As a result, we obtain ϵ j = 0 in Lemma 11. □If G and X ⊤ y are precomputed, the cost of the gradient computations in IHT is O(n 2 ) time due to the third equation of Equation ( 2). If we use a sparse matrix for the parameter vector, the cost is O(nk) time. However, since the parameter vector changes for each iteration and the sparse matrix must be re-constructed for each iteration, it is rarely used for the parameter vector in practice due to the overhead of the sparse matrix construction 3 . We note that the sparse matrices may be used for the design matrices whose elements do not change for each iteration.This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.NeurIPS Paper ChecklistJustification: The paper follows the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).If I -ηX ⊤ X and X ⊤ y are precomputed, the cost is O(n 2 ) time. If the precomputation is not performed, the cost is O(mn) time because we first compute h = Xθ ty at O(mn) time, then compute X ⊤ h at O(mn) time. See the Appendix for a discussion of IHT with sparse matrices.https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Lasso. html 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: Yes, the authors discuss the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
questions: questions: There are some minor questions.
1. Line 42-45 is duplicated with the abstract.
2. Definition 2 is less informative. It generally says nothing about the construction of the candidate set $\mathbb{D}^t$. 
3. The performance seems highly sensitive to the selection of $t^\ast$.
4. 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: limitations: The limitation seems not addressed in the paper. My comments about it are already in the above sections of Weaknesses and Questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: Major:
* It is unclear to me why the pruning strategy is defined the way it is. 
* 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. 
* 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.
* 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.
* Presentation is a bit long-winded at places, e.g. third paragraph

Minor:
* “73 times”: a more precise statement may be more useful; briefly describe the dimensions of the problem etc
* line 60: it is more consistent to use “problem in (1)” instead of “Problem 1”
* Notation: 
    * I find it more natural to use boldface X as the design matrix
    * it is a bit confusing to denote the hard thresholding operator by Pk, hk is more common
    * \mathbb{D}^t and \mathbb{I} are unconventional notations for sets. Use \mathcal{D}^t and \mathcal{I} instead.
questions: 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?
* 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?
* I think X^TX takes O(n^2m) computational cost instead of O(mn)?
* Did you mean to use f(\theta) instead of 1/2||y-X\theta||_2^2 in (1)?
limitations: limitations: I'd suggest the author add one or two sentences in the final Section to discuss the limitations of this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: I do not see any major weakness. 

Maybe the presentation can be improved in some parts. Here are some suggestions:

Line 51: m-dimensionAL vector
Line 63:  ... if it uses a heap ...
Line 137: The ASYMPTOTIC cost ... [in some situations the actual cost should be higher] 
Lines 239 and 241: Avoid starting a sentence with references.
Table 1: The information content is really low.
questions: 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?

2. 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: limitations: The scope of the problem addressed by the paper is clearly stated. Within this scope, I do not see limitations.

Comments: comment: We sincerely appreciate the reviewer's response. If the reviewer has any further questions or suggestions, please feel free to reach out to us.
Thank you for the responses.
We sincerely appreciate the reviewer's interest in our method. We are also deeply grateful for your assistance in improving the score. We will incorporate the valuable discussion above into our paper.
The authors' responses sufficiently address my questions. In response, I would like to raise my score. Overall, it is an interesting work from the computation aspect of the sparse regression problem.
We are pleased to receive such a positive response and sincerely thank the reviewer for raising the score. If the reviewer has any further questions or suggestions, please do not hesitate to contact us.
Thank you for answering my questions. As you have noticed, I like your paper. To make a clear statement, I will increase my score to accept.
We thank the reviewer for verifying the rating. We greatly appreciate the positive feedback and will continue to work on improving the paper.
Thank you for pointing that out. I meant to say borderline accept, i.e. I've increased my rating by 2 points: one point to account for my own misunderstanding, and another to reflect the changes proposed by the authors. Overall I wanted to change my rating to indicate that this paper is worthy of publication.
We would like to express our sincere gratitude for the response. We are currently revising the paper based on the feedback, and we believe that these changes have significantly improved its quality. If the reviewer has any further questions or suggestions, please do not hesitate to reach out to us.

(Furthermore, the term "weak accept" in the reply is generally associated with a rating of 6 in this conference. We would greatly appreciate it if you could kindly verify whether the rating is accurate.)
I thank the authors for their detailed response, in particular, for articulating the reason for choosing "pruning" over "thresholding", for explaining the gap in the literature that this work fills, and for agreeing to improve the structure and presentation of the paper. I decided to increase my rating to a weak accept.