🤖 machine learning

New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

This paper proposes a generalized variance-reduced zeroth-order hard-thresholding algorithm that resolves the inherent conflict between gradient deviation and operator expansivity in the existing SZOHT method, thereby eliminating restrictions on random directions and achieving improved convergence rates and broader applicability for $\ell_0$ constrained optimization.

Original authors: Xinzhe Yuan (Harbin Institute of Technology), William de Vazelhes (Mohamed bin Zayed University of Artificial Intelligence), Bin Gu (Mohamed bin Zayed University of Artificial Intelligence, Jilin Univ

Published 2026-05-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinzhe Yuan (Harbin Institute of Technology), William de Vazelhes (Mohamed bin Zayed University of Artificial Intelligence), Bin Gu (Mohamed bin Zayed University of Artificial Intelligence, Jilin University), Huan Xiong (Harbin Institute of Technology, Mohamed bin Zayed University of Artificial Intelligence)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the Needle in a Haystack Without Touching It

Imagine you are trying to find the perfect combination of ingredients for a secret recipe (the "optimal solution"). However, you have two major rules:

The "Zero-Order" Rule: You cannot taste the ingredients to see how they change the flavor (you can't calculate a "gradient"). You can only mix them, bake a cake, and see if it tastes good or bad. You have to guess the direction to improve based on trial and error.
The "Hard-Thresholding" Rule: You are only allowed to use exactly 5 ingredients out of a pantry of 1,000. If you use a 6th, you must immediately throw one out to stay at 5.

This paper tackles a specific problem: When you try to improve your recipe using only taste tests (Zero-Order) while strictly limiting your ingredients (Hard-Thresholding), the math gets messy. The previous best method (called SZOHT) was like a tightrope walker who could only cross the wire if the wind was perfectly calm and the wire was a specific length. If the wind blew too hard (too much "noise" or "variance" in your taste tests) or the wire was too long, the walker would fall.

The Problem: The "Expansivity" Trap

The authors explain that the "Hard-Thresholding" rule (keeping only the top 5 ingredients) is tricky. Unlike a gentle filter that smooths things out, this rule is "expansive." Imagine trying to squeeze a large, bouncy ball through a small hole. If you push it too hard, it might bounce back out or get stuck in a weird shape.

In the old method (SZOHT), to stop the algorithm from bouncing out of control, the researchers had to force the "taste testers" (the random directions used to guess the gradient) to be extremely precise. They had to use a huge number of taste tests just to make sure the noise didn't ruin the math. This made the method slow and impractical for many real-world problems.

The Solution: The "Memory" Trick (Variance Reduction)

The authors' big insight is that the problem isn't just about the "noise" of the taste tests; it's about the variance (how much the guesses jump around).

They propose a new approach called pM-SZHT and VR-SZHT. Think of this as giving the chef a memory.

The Old Way: Every time you bake a cake, you forget what happened last time. You start from scratch, taste a few random spots, and guess the direction. Because you have no memory, your guesses jump all over the place (high variance). To fix this, you have to taste thousands of spots to get a reliable average.
The New Way: The chef remembers the last few cakes. When tasting the new cake, they compare it to the memory of the old ones. "This one is a bit sweeter than the last one, but the last one was too salty." By looking at the difference between the new guess and the old memory, the wild jumps cancel out. The "noise" is reduced.

Because the chef is using memory to smooth out the guesses, they don't need to taste thousands of spots to get a reliable direction. They can get away with fewer taste tests, and the algorithm doesn't need those strict, impossible conditions to work.

The Results: Faster and More Flexible

The paper proves mathematically that by using this "memory" (variance reduction):

The "Wind" Doesn't Matter as Much: The algorithm no longer needs the number of random taste tests to be huge to stay stable. It can handle more "windy" conditions (noisier data).
Faster Convergence: The recipe gets to the perfect flavor much faster because the chef isn't wasting time re-tasting things they already know.
Broader Use: The method works on problems where the old method would have failed completely.

Real-World Tests

The authors tested their new "Chef with a Memory" on two specific tasks:

Ridge Regression: A standard math problem for predicting numbers (like predicting house prices based on features). They showed their method found a better solution faster than the old method.
Black-Box Adversarial Attacks: This is like trying to trick a security camera (a neural network) into misidentifying a picture of a "plane" as a "truck" by adding tiny, invisible pixels. The camera is a "black box" (you can't see its internal math). The authors showed their method could find the perfect set of pixels to fool the camera more effectively than the previous best method, even when they could only "poke" the camera and see the result, not see the code.

Summary

The paper says: "We found that the reason the old method was so fragile was that it didn't use memory to calm down the noise. By adding a 'variance reduction' memory system, we can make the algorithm stable without needing strict, unrealistic rules. This makes it faster and usable for more difficult problems."

Technical Summary: New Insight of Variance Reduce in Zero-Order Hard-Thresholding

Problem Statement
The paper addresses the challenge of solving $\ell_0$ -constrained optimization problems, which are fundamental for achieving sparse learning in high-dimensional machine learning tasks. The specific problem is formulated as minimizing a regularized empirical risk $F(\theta) = \frac{1}{n}\sum_{i=1}^n f_i(\theta)$ subject to $\|\theta\|_0 \leq k$ . While hard-thresholding iterative algorithms are effective for $\ell_0$ constraints, they traditionally require access to true gradients. In many modern scenarios—such as bandit problems, black-box adversarial attacks, and reinforcement learning—gradients are inaccessible, necessitating the use of zeroth-order (ZO) optimization methods that rely on function evaluations.

The existing state-of-the-art algorithm for this setting, Stochastic Zeroth-Order Hard-Thresholding (SZOHT), suffers from a critical limitation. The authors identify an inherent conflict between the deviation (error) of ZO gradient estimators and the expansivity (non-non-expansiveness) of the hard-thresholding operator. To ensure convergence, SZOHT imposes stringent conditions on the number of random directions ( $q$ ) used for gradient estimation and the sparsity level ( $k$ ). These conditions are often too restrictive for practical applications, limiting the algorithm's utility.

Methodology
The paper proposes a new perspective on resolving the conflict between ZO gradients and hard-thresholding by focusing on variance reduction. The authors argue that the conflict is fundamentally between the hard-thresholding operator and the variance of the gradient estimation, rather than the estimation error itself.

To address this, the paper introduces a generalized framework called pM-SZHT (p-Memorization Stochastic Zeroth-Order Hard-Thresholding). This framework utilizes historical gradients to reduce variance, similar to first-order variance reduction techniques like SAGA and SVRG, but adapted for the ZO setting. The core components include:

Generalized Iterative Expression: The algorithm follows the update rule $\theta^{(r+1)} = H_k(\theta^{(r)} - \eta \hat{g}^{(r)}(\theta^{(r)}))$ , where $\hat{g}^{(r)}$ is a generalized gradient estimate incorporating variance reduction.
p-Memorization: The framework employs a memory mechanism where a random subset of gradient estimates is updated in each iteration, allowing the algorithm to leverage historical information to stabilize the ZO estimates.
Specific Algorithms: Within this framework, the authors instantiate specific algorithms, including VR-SZHT (a ZO adaptation of SVRG) and SARAH-SZHT (a ZO adaptation of SARAH).

Theoretical Analysis
The paper provides a comprehensive convergence analysis under standard sparse learning assumptions: Restricted Strong Convexity (RSC) and Restricted Strong Smoothness (RSS).

Conflict Mitigation: The analysis demonstrates that by using variance reduction, the algorithm can eliminate the strict dependency on the number of random directions ( $q$ ) required for convergence. In SZOHT, $q$ must be large enough to satisfy specific bounds relative to $k$ ; in the proposed methods, convergence is guaranteed for any $q > 0$ (provided other parameters like the learning rate are chosen correctly).
Convergence Rates: Theoretical results show that the proposed algorithms achieve improved convergence rates compared to SZOHT. Specifically, the query complexity for VR-SZHT is derived as $O([n + \frac{\kappa^3}{\kappa^2+1}] \log(1/\epsilon))$ , which represents a significant improvement over the $O((k + d/s^2)\kappa^2 \log(1/\epsilon))$ complexity of SZOHT, particularly when the condition number $\kappa$ is large.
Independence from $q$ : A key theoretical finding is that variance reduction decouples the convergence condition from the number of random directions, allowing for more flexible parameter selection.

Experimental Results
The authors validate their methods on two primary tasks:

Ridge Regression: Using synthetic data, the proposed variance-reduced algorithms (VR-SZHT, SAGA-SZHT, SARAH-SZHT) consistently outperform the vanilla SZOHT and the full-gradient ZOHT (FGZOHT). They achieve lower function values with fewer hard-thresholding operations (NHT) and competitive zeroth-order oracle calls (IZO).
Black-Box Adversarial Attacks: The methods are applied to generate sparse universal adversarial perturbations on the CIFAR-10 dataset against a black-box classifier. The results indicate that variance-reduced methods, particularly SARAH-SZHT and SAGA-SZHT, achieve higher attack success rates and lower loss values compared to SZOHT. For instance, SARAH-SZHT successfully attacked 7 out of 10 images in the "airplane" class, outperforming SZOHT.

Significance and Claims
The paper claims to provide a "new insight" into variance reduction, framing it not just as a speed-up mechanism but as a necessary tool to mitigate the unique contradictions between ZO estimators and hard-thresholding operators. The significance of the work lies in:

Relaxing Constraints: It removes the prohibitive restrictions on the number of random directions ( $q$ ) found in SZOHT, making ZO hard-thresholding viable for a broader range of real-world problems.
General Framework: It establishes a general analysis framework (pM-SZHT) that encompasses various variance-reduced ZO methods, offering a unified theoretical understanding.
Practical Utility: The experimental results on adversarial attacks and regression demonstrate that these methods can achieve competitive or superior performance compared to state-of-the-art ZO algorithms while maintaining sparsity constraints.

The authors conclude that their approach effectively enhances existing algorithms for sparse zero-order optimization, offering a more flexible and resilient solution for scenarios where gradients are inaccessible.