New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions
Xinzhe Yuan, William de Vazelhes, Bin Gu, Huan Xiong · 2026
Read New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions by Xinzhe Yuan, William de Vazelhes, Bin Gu, Huan Xiong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18035.txt.
Introduction
Xinzhe Yuan and three colleagues offer a new view on variance reduction in zero-order hard-cutoff for sparse fitting. The SZOHT algorithm alone tackles l0 thinness limits with zero-order slopes, but caps the number of random directions because gradient drift clashes with the cutoff stretch. Their wider spread-cut algorithm drops that cap, with a matching settling study under standard terms. Theory shows it improves convergence rates and widens use over SZOHT, shown on ridge fitting and black-box hostile attacks.
Catalog record
| CREATOR | Xinzhe Yuan, William de Vazelhes, Bin Gu, Huan Xiong |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 107647 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18035
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions Xinzhe Yuan, William de Vazelhes, Bin Gu, Huan Xiong Abstract Hard-thresholding is an important type of algorithm in machine learning that is used to solve ℓ 0 \ell_{0} constrained optimization problems. However, the true gradient of the objective function can be difficult to access in certain scenarios, which normally can be approximated by zeroth-order (ZO) methods. The SZOHT algorithm is the only algorithm tackling ℓ 0 \ell_{0} sparsity constraints with ZO gradients so far. Unfortunately, SZOHT has a notable limitation on the number of random directions due to the inherent conflict between the deviation of ZO gradients and the expansivity of the hard-thresholding operator. This paper approaches this problem by considering the role of variance and provides a new insight into variance reduction: mitigating the unique conflicts between ZO gradients and hard-thresholding. Under this perspective, we propose a generalized variance reduced ZO hard-thresholding algorithm as well as the generalized convergence analysis under standard assumptions. The theoretical results demonstrate the new algorithm eliminates the restrictions on the number of random directions, leading to improved convergence rates and broader applicability compared with SZOHT. Finally, we illustrate the utility of our method on a ridge regression problem as well as black-box adversarial attacks. 1 Introduction \ell_{0} constrained optimization is a fundamental method in large-scale machine learning, particularly in high-dimensional problems. This approach is widely favored for achieving sparse learning. It offers numerous advantages, notably enhancing efficiency by reducing memory usage, computational demands, and environmental impact. Additionally, this constraint plays a crucial role in combatting overfitting and facilitating precise statistical estimation ( 23 ; 28 ; 3 ; 35 ) . In this study, we focus on the following problem: \min_{\theta\in\mathbb{R}^{d}}\mathcal{F}(\theta)=\frac{1}{n}\sum^{n}_{i=1}f_{i}(\theta),\quad s.t.\ \mathcal{k}\theta\mathcal{k}_{0}\leq k, (1) Here, \mathcal{F}(\theta) is the (regularized) empirical risk. \left\|\theta\right\|_{0} represents the number of non-zero directions. d is the dimension of \theta . Unfortunately, due to the \ell_{0} constraint, ( 1 ) becomes an NP-hard problem, rendering traditional methods unsuitable for its analysis. Therefore, we consider using the hard-threshold iterative algorithm ( 28 ; 17 ; 26 ; 34 ) , which is a widely used technique for obtaining approximate solutions to NP-hard’s \ell_{0} constrained optimization problems. Specifically, this technique alternates between the gradient step and the application of the hard threshold operator \mathcal{H}_{k}(\theta) . Operator \mathcal{H}_{k}(\theta) retains the top k elements of \theta while setting all other directions to zero. The advantage of hard-thresholding over its convex relaxations is that it can achieve similar precision without the need for computationally intensive adjustments, such as tuning \ell_{1} penalties or constraints. Hard-thresholding was first used for its full gradient form ( 17 ) . Nguyen ( 26 ) developed a stochastic gradient descent SGD version of hard thresholding known as StoIHT. Nevertheless, StoIHT’s convergence condition is overly stringent for practical applications ( 20 ) . To address this issue, ( 37 ) , ( 31 ) and ( 20 ) implemented variance reduction techniques to improve the performance of StoIHT in real-world problem-solving. However, this type of StoIHT is still not suitable for many problems. For example, in certain graphical modeling tasks ( 2 ) , obtaining the gradient is computationally hard. Even worse, in some settings, the gradient is inaccessible by nature, for instance in bandit problems ( 30 ) , black-box adversarial attacks ( 32 ; 5 ; 6 ) , or reinforcement learning ( 29 ; 22 ; 7 ) . To address these challenges, zeroth-order (ZO) optimization methods have been developed ( 24 ) . These methods commonly replace the inaccessible gradient with its finite difference approximation which can be calculated by simply using the function evaluations. Subsequently, ZO methods have been adapted to handle convex constraint sets, rendering them suitable for solving the \ell_{1} convex relaxation of the problem ( 1 ) ( 21 ; 1 ) . However, it’s essential to highlight that in the context of sparse optimization, \ell_{1} regularization or constraints can introduce substantial estimation bias and result in inferior statistical properties when compared to \ell_{0} regularization and constraints ( 12 ; 36 ) . To tackle this issue, a recent development introduced the stochastic zeroth-order hard-thresholding algorithm (SZOHT) ( 8 ) , specifically designed for \ell_{0} sparsity constraints and gradient-free optimization. Unfortunately, as the only available algorithm in zeroth-order hard-thresholding so far, SZOHT has notable limitations due to the inherent conflict between the deviation of ZO estimators and the expansivity of the hard-thresholding. This limitation makes the algorithm difficult to use in practice, and a natural question is proposed: Could we have a simple ZO hard-thresholding algorithm whose convergence does not rely on the number of q (the number of random directions used to estimate the gradient, further defined in Section 2 )? In this paper, we provide a positive response to this question. Our approach centers on the role of variance in addressing this problem. We firmly believe that variance reduction can offer a dual benefit. It not only holds the potential to accelerate convergence speed but, more importantly, it can effectively mitigate the unique conflicts associated with zero-order hard-thresholding. From this perspective, SZOHT is characterized by its limitation in restricting the sampling of zero-order gradients, essentially representing an incomplete approach to variance reduction. This incompleteness leads to strict conditions for SZOHT. In contrast, we have developed better algorithms by using historical gradients to reduce variance thoroughly. We then provide the convergence and complexity analysis for the generalized variance reduce algorithm under the standard assumptions of sparse learning, which are restricted strong smoothness (RSS), and restricted strong convexity (RSC) ( 26 ; 31 ) to retain generality. These algorithms eliminate the restrictions on zero-order gradient steps, leading to improved convergence rates and broader applicability. Crucial to our analysis is to provide how variance reduction mitigates contradictions on the parameters q and k . Finally, we demonstrate the effectiveness of our method by applying it to both ridge regression problems and black-box adversarial attacks. Our results highlight that our method can achieve competitive performance when compared to state-of-the-art methods for zeroth-order algorithms designed to enforce sparsity. Figure 1: Motivation of our algorithm. The majority of our work can be summarized in three parts: 1. New Perspective on Resolving Conflicts Between Zeroth-Order Methods and Hard-Thresholding. Our paper acknowledges the necessity of mitigating this contradiction, emphasizing the demand for a more flexible and resilient approach. By employing the perspective of variance to analyze this issue, our paper presents a more practical and effective solution. 2. Variance Reduction: Another key innovation presented in the paper is the introduction of variance reduction. This concept provides a unique solution to \ell_{0} -constrained zeroth-order optimization. By employing data-driven techniques to reduce variance, the paper not only enhances the algorithm’s convergence but also expands its utility across a wider range of scenarios. 3. General Analysis: The introduction of a general analysis framework is another contribution to the paper. This framework systematically evaluates the performance and behavior of varying variance reduced algorithms under \ell_{0} -constraint and ZO gradient. 2 Preliminaries Throughout this paper, we use \mathcal{k}\theta\mathcal{k} to denote the Euclidean norm for a vector, \mathcal{k}\theta\mathcal{k}_{\infty} to denote the maximum absolute component of that vector, and \mathcal{k}\theta\mathcal{k}_{0} to