Fight Fire with Fire: Multi-biased Interactions in Hard-Thresholding

Thank you for your thorough review and detailed comments. We sincerely apologize for the poor writing and presentation of our submission, which clearly made it difficult to interpret and evaluate our work. We highly value your feedback and have worked to address the major concerns you raised. Below, we provide responses to each of your comments:

1. On Writing and Presentation

We acknowledge that the quality of writing and presentation in the current version is insufficient. We apologize for any inconvenience this has caused. We have already begun revising the paper to ensure clearer definitions, consistent notation, and improved logical flow. In our next version, we will provide more detailed explanations of all notations, include necessary references, and refine the writing to eliminate grammatical errors and typos. Your specific examples of unclear notations and inconsistencies are extremely helpful, and we will address them systematically in the revised manuscript.

2. On Logical Inconsistencies (Point 3)

Regarding your concern about logical inconsistencies, we believe there is a misunderstanding. Specifically, in Remark 4, we state that "the recursive biased algorithm for the Hard-Threshold can counteract some bias, thus accelerating convergence," which refers to our proposed method. This does not suggest that the general hard-thresholding operation itself eliminates bias, as you implied.

3. On the Number of Experiments (Point 4)

We respectfully disagree with your claim that our experiments are vague or insufficient. As summarized in your review, our submission includes two experiments: black-box adversarial attacks and ridge regression. This demonstrates the applicability of our approach to different tasks. While the numerical example in ridge regression is limited in dimensionality, the black-box adversarial attack experiment explicitly deals with large-scale data, aligning with the introduction's mention of "large-scale machine learning." In addition, we have also conducted experiments on sparse feature selection.

5. On Grammatical Errors and Typos

Thank you for pointing out specific issues such as the misuse of "recursively." We will correct these issues and perform a thorough proofreading of the paper to ensure proper grammar and consistent terminology.

We deeply appreciate your feedback, which has highlighted key areas for improvement in our submission. By addressing these issues, we aim to make our contributions more accessible and convincing in the next version. Thank you again for your insightful comments and suggestions.

Thank you for your insightful review. We sincerely hope that the main concerns raised in the review can be clarified by the following responses.

On the Difference Between $l_0$ Optimization and $l_1$ Optimization

First, we are pleased to discuss the differences between $l_0$ optimization and $l_1$ optimization. Indeed, these two methods have better applications in different fields. It is undeniable that $l_1$ optimization typically achieves better accuracy, which has made it the focus of more widespread research. However, for many scenarios with strict sparsity requirements, $l_0$ optimization remains an important algorithm. Compared to $l_1$ optimization, $l_0$ optimization naturally has lower computational costs, making $l_0$-based algorithms faster in general. Additionally, in scenarios requiring strict sparsity, LASSO often struggles because it is difficult to directly specify the sparsity level. A typical example is sparse adversarial attacks, where the number of noise points must be limited, but LASSO cannot precisely control the sparsity. Similar issues arise in sparse feature selection tasks.
In addition, in our sparse feature selection experiment, we can see that compared to $l_1$ optimization, $l_0$ optimization is similar in accuracy but has smaller sparsity and faster computation time.

On Numerical Experiments

Thank you for your comments. We have included LASSO-SAGA in the experiments for first-order algorithms. Additionally, we have incorporated the adversarial attack experiment and the sparse feature selection experiment into the main text.

On Presentation Style

We have made the necessary adjustments to the presentation style. Thank you for pointing this out.

It is a bit unclear to me why to use $l_0$ regularization together with ridge regression. One argument in the introduction is that $l_0$ regularization avoids hyperparameters, but in the example you re-introduce hyperparameters. How does the algorithm perform in estimation with this constraint?

First, we would like to clarify that $l_0$ optimization is not solely about avoiding hyperparameters but about avoiding the computation of hyperparameters (compared to ISTA algorithms). When combining $l_0$-norm with $l_2$-norm, the model’s robustness to noise can be significantly enhanced. This is because sparse optimization, due to the omission of some features, is often susceptible to noise. In fact, using $l_2$-norm in sparse optimization problems is a common practice, not only in $l_0$ optimization but also in $l_1$ optimization, as seen in approaches like Elastic Net.

What are the asymptotic bounds on the computational complexity of iteration of the algorithm with hard thresholding?

We note that if $f$ has a $k^*$-sparse unconstrained minimizer, which could happen in sparse reconstruction, or with overparameterized deep networks (see for instance [1] Assumption (2)]), then we would have $\|\nabla f(x^*)\| = 0$, and hence that part of the system error would vanish.*

[1] Alexandra Peste, Eugenia Iofinova, Adrian Vladu, and Dan Alistarh. Ac/dc: Alternating compressed/decompressed training of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.

Thank you for your insightful review. We sincerely hope that the main concerns raised in your review can be clarified by the following responses.

The one main contribution of this paper is to propose several first-order and zeroth-order hard-thresholding algorithms such as SARAH-HT, BSVRG-HT, and BSAGA-HT. There are much first-order and zeroth-order stochastic hard-thresholding algorithms. Therefore, the novelty of this paper is very limited.

While we acknowledge that there are existing studies on first-order hard-thresholding algorithms, we would like to highlight the following points regarding the novelty of our work:

1. Limited Research on Zeroth-Order Hard-Thresholding: To the best of our knowledge, only two prior works (William, 2023 and Yuan, 2024) have studied zeroth-order hard-thresholding algorithms.
   • Our proposed algorithm framework, BVR-SZHT, generalizes existing zeroth-order hard-thresholding methods, including VR-SZHT (2024) as a special case when $\theta=1$. This unified framework allows us to better analyze the role of gradient bias and demonstrate how appropriate parameter choices (e.g., $\theta>1$) lead to faster convergence.
2. Gradient Bias Analysis: Our work is the first to investigate the impact of gradient bias in both first-order and zeroth-order settings. This includes analyzing how memory and recursive biases interact with the hard-thresholding operator and using this understanding to design algorithms that improve convergence and efficiency.

1. What’s the advantage of the proposed first-order and zeroth-order stochastic hard-thresholding algorithms against related algorithms in terms of convergence rates and complexities?

-First-Order Algorithms:
Our BSVRG-HT algorithm encompasses SVRG-HT [1] as a special case. Specifically, SVRG-HT can be viewed as a particular instance of BSVRG-HT when $\theta$. This relationship is directly reflected in Theorem 1, where the advantages of BSVRG-HT in terms of improved convergence rates are clearly demonstrated.
-Zeroth-Order Algorithms:
Similarly, our BVR-SZHT algorithm generalizes VR-SZHT. By introducing adjustable parameters, BVR-SZHT effectively mitigates gradient instability issues inherent in VR-SZHT, resulting in faster convergence.
To support these claims, we have added a remark in the manuscript with detailed comparisons of convergence rates and complexities.

2. The experimental results are not convincing. The authors should compare the proposed algorithms with more recently proposed algorithms.

Thank you for your suggestion. We would like to clarify the following regarding the experimental comparisons: Zeroth-Order Algorithms: For zeroth-order hard-thresholding, we compared our proposed BVR-SZHT with the two most recent state-of-the-art algorithms: 1.VR-SZHT (2024): Included as a special case within our framework (when $\theta=1$). 2.SZOHT (2023): Another prominent recent work in this domain. Our experiments (e.g., few-point adversarial attack on CIFAR-10) consistently demonstrate that BVR-SZHT outperforms both VR-SZHT and SZOHT in terms of convergence speed and computational efficiency. This validates the effectiveness of our approach. First-Order Algorithms: For first-order hard-thresholding, we compared SARAH-HT and BSVRG-HT with: 1.SVRG-HT: A recently proposed variant of the SVRG algorithm combined with hard-thresholding. 2.SAGA-LASSO: A widely recognized first-order method integrating SAGA with LASSO regularization. We recognize that the experimental section may not have provided sufficient details about the algorithms we compared. To address this, we have added necessary descriptions of all baseline algorithms to the revised paper, ensuring clarity and transparency. If there are any specific algorithms you believe must be included for comparison, we kindly ask for your suggestions. We are more than willing to conduct additional experiments to incorporate these comparisons.

> 3. Both the English language and equations in this paper need to be improved. For example, Line 225: ‘In Hard-Thresholding algorirthm, The commonly used Zeroth-Order estimation is’.

Thank you for pointing this out. We have carefully revised the manuscript. Overall language has been improved to ensure readability and flow.
We sincerely hope these changes address your concerns and demonstrate the significance of our contributions. [1]Li, Xingguo, et al. "Nonconvex sparse learning via stochastic optimization with progressive variance reduction." arXiv preprint arXiv:1605.02711 (2016).

We extend our sincere gratitude for dedicating your valuable time to reviewing our paper and for expressing your appreciation and support for our work. In the following, we will provide a comprehensive response to your review comments.

The experiments are somewhat weak.

Thank you for your valuable suggestion, which provides us with great insights. We have supplemented our experiments with sparse feature selection tasks on the CIFAR-10, MNIST datasets, and a colon cancer dataset. These experiments highlight the performance of our proposed methods under practical settings. Additionally, we are conducting further experiments, and if time permits, we will provide additional results before the rebuttal period ends.

As for the theoretical analysis, the discussion of when these assumptions might fail is limited and there is no analysis of what happens when conditions are violated.

We appreciate your insightful observation regarding the assumptions. It is important to clarify that the RSC (Restricted Strong Convexity) and RSS (Restricted Strong Smoothness) conditions are specifically designed for high-dimensional and non-convex problems. These conditions do not require global convexity or smoothness but instead impose curvature requirements along specific sparse directions ($\|x-y\|_0 < s$).

Thus, concerns about points (a) and (c) are alleviated by the very nature of these assumptions, which are widely used in the field of sparse optimization[1,2]. Indeed, most work in this domain relies on these conditions.

Regarding point (b), the impact of noise on hard-thresholding algorithms is an intriguing topic, but it is challenging to analyze it purely from the perspective of bias cancellation. This presents a valuable avenue for future work, which we intend to explore.

What is the computational overhead of tracking and managing different types of biases compared to simpler approaches?

The computational cost of our framework is inherently low due to its structural simplicity. Specifically, BSAGA-HT and BSVRG-HT algorithm only modifies a single parameter compared to unbiased methods such as SAGA-HT and SVRG-HT. This allows our approach to achieve faster convergence without introducing additional computational overhead during iterations.

Preliminary experimental results further support this claim, demonstrating that our method achieves convergence in fewer iterations compared to traditional unbiased methods. For example, in our experiments on the CIFAR-10 dataset, our method achieves convergence in X fewer iterations compared to SVRG, while maintaining comparable computational cost per iteration.

Our experiments on the MNIST, CIFAR-10, and colon cancer datasets consistently demonstrate that our methods (e.g., BVRSZHTn-HT and SARAH-HT) outperform traditional methods like SAGA-LASSO in terms of feature selection efficiency and computational cost. Below are key highlights from the results:

1. MNIST Dataset:

   • Accuracy: SARAH-HT achieves 96.16%, and BVRSZHTn-HT achieves 95.93%, comparable to SAGA-LASSO at 97.29%.
   • Number of Selected Features: SARAH-HT and BVRSZHTn-HT select 235 features, significantly fewer than the 644 features selected by SAGA-LASSO.
   • Selection Time: SARAH-HT completes selection in 63.99 seconds, while SAGA-LASSO takes over 1131 seconds.

2. CIFAR-10 Dataset:

   • Accuracy: SARAH-HT achieves 51.26%, and BVRSZHT12-HT achieves 51.09%, comparable to SAGA-LASSO at 51.02%.
   • Number of Selected Features: SARAH-HT and BVRSZHTn-HT select 1843 features, far fewer than the 3053 features selected by SAGA-LASSO.
   • Selection Time: SARAH-HT completes selection in 153.08 seconds, while SAGA-LASSO takes over 5148 seconds.

3. Colon Cancer Dataset:

   • Accuracy: SARAH-HT achieves 89.38%, and BVRSZHTn-HT achieves 88.50%, while SAGA-LASSO achieves 92.03%.
   • Number of Selected Features: SARAH-HT and BVRSZHTn-HT select 2863 features, fewer than the 3470 features selected by SAGA-LASSO.
   • Selection Time: SARAH-HT completes selection in 65.66 seconds, while SAGA-LASSO takes over 645 seconds.

These results illustrate that our framework achieves faster convergence and reduced computational overhead while maintaining competitive accuracy. The structural simplicity of our algorithms is a key factor in achieving these results. We have incorporated these findings into the manuscript to further clarify the computational advantages of our approach. [1]Nam Nguyen, Deanna Needell, and Tina Woolf. Linear convergence of stochastic iterative greedy algorithms with sparse constraints. IEEE Transactions on Information Theory, 63(11): 6869–6895, 2017 [2] Jie Shen and Ping Li. A tight bound of hard thresholding. The Journal of Machine Learning Research, 18(1):7650–7691, 2017.