New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions
Authors: Xinzhe Yuan
William de Vazelhes
Bin Gu
Huan Xiong
Venue: ICLR 2024 poster (2024)
Keywords: zeroth-order gradient
hard-thresholding
variance reduction
Primary area: optimization

Abstract: Hard-thresholding is an important type of algorithm in machine learning that is used to solve $\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. SZOHT algorithm is the only algorithm tackling $\ell_0$ sparsity constraints with zeroth-order 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 portfolio optimization problem as well as black-box adversarial attacks.

Published as a conference paper at ICLR 2024
NEW INSIGHT OF VARIANCE REDUCE IN ZERO-ORDER HARD-THRESHOLDINGE MITIGATING GRADIENT ER- ROR AND EXPANSIVITY CONTRADICTIONS
Xinzhe Yuan', William Vazelhes", Bin Gu Huan Xiong1.2+
IASM, Harbin Institute of Technology
MMohamed bin Zayed University of Artificial Intelligence "Scoool of Artificial Intelligence, Jilin University
hit mit.edu.c. edu.cn
[william. vazelhes, bin.gu @mbzuai ac. huan. xicng ceathhemaall
ABSTRACT
torethhhreholding is an important type of algorithm in machine learning that is used to solve tu constrained optimization problems. However, the true gradient of the objective function can be difficult to access in certain scenarios, which normally be approximated by zeroth-order (ZO) methods. The SZOHT algorithm is the only algorithm tackling fg sparsity constraints with 70 gradients so far. Unfortu- nately, SZOHT has a notable limitation on the number of random directions due the inherent conflict between the deviation of ZO gradients and the expansivity of the hard hard-thresholding operator. This paper approaches this problem by considering the role of variance and provides a new insight into variance reduction: mitigat- ing the unique conflicts between ZO gradients and hard-thresholding. Under this perspective, we propose generalized variance reduced ZO hard-thresholding algo- rithm as well as the generalized convergence analysis under standard assumptions.
The thcoretical results demonstrate the new algorithm climinates the restrictions on the number of random directions, leading to improved convergence rates and broader applicability compared with SZOHTT. Finally, illustrate the utility of our method on a ridge regression problem as well as black-box adversarial attacks.
INTRODUCTION
to constrained optimization 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 crucial role in combatting overfitting and facilitating precise statistical estimation (Negahban et al. 2012; Raskutti et al. 2011
Bühlmann and Van De Geer 2011 Yuan and Li 2021). In this study, focus the following problem:
min F(0) = f((0), s.t. 1001o s k, 6ER
(I)
Here, F(O) is the (regularized) empirical risk. ||0|, represents the number of non-zero directions. d is the dimension of f. Unfortunately, due to the lo constraint, rendering traditional methods unsuitable for its analysis.
[ becomes an NP-hard problem,
Therefore, we consider using the Bard-threshee iterative algorithm (Raskutti et al., 2011 Jain et al. 2014, Nguyen al., 2017b, Yuan et al.] 2017). which widely used technique for obtaining approximate solutions to NP-hard's ln constrained optimization problems. Specifically, this technique alternates between the gradient step and the application of the hard threshold operator H2 (0). Operator
"Corresponding authors.

---

Published as a conference paper at ICLR 2024
(f) retains the top & elements of 8 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 & penalties constraints. Hard-thresholding was first used for its full gradient form(Jain et al., 2014). Nguyen (Nguyen et al. 2017b) developed stochastic gradient descent SGD version of hard thresholding known StolHT. Nevertheless, StoIHT's convergence condition is overly stringent for practical applications et al., 2016)). To
address this issue, (Zhou al. 2018), (Shen and Li 2017) and (Li 2016) implemented variance reduction techniques to improve the performance of StolHT in real-world mooblem-solvinge
However, this type of stolHT is still not suitable for many problems. For example, in certain graphical modeling tasks (Blumensath and Davies 2009), obtaining the gradient is computationally hard. Even worse, in some settings, the gradient is inaccessible by nature, for instance in bandit problems [Shamir 2017), black-box adversarial attacks(Tu et al. 22199; Chen et al.] 2017]] (2019). or reinforcement learning (Salimans et al. 2017 Mania et al. 2018]] Choromanski et al. 2020). To address these challenges, zeroth-order (ZO) optimization methods have been developed(Nesterov and Spokoiny 2017). 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 l convex relaxation of the problem (Lu et al. 2018: Balasubramanian and Ghadimi 2018). However, it's essential to highlight that in the context of sparse optimization, E regularization or constraints can introduce substantial estimation bias and result in inferior statistical properties when compared to Eo regularization and constraints(Fan and Li 2001; Zhang 2010).
To tackle this issue, a recent development introduced the Stochastic Zeroth- Hard-Thresholding algorithm (SZOHT){de Vazelhes et al. (022), specifically designed for lg 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 70 estimators and the expansivity of the aard-threshodding. This limitation makes the algorithm difficult to use in practice, and natural question is proposed: Could we have simple 70 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
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 offer dual benefit. 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 striet 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) (Nguyen al.) [0176] Shen and Li 2017) 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 the-ttrr methods for zeroth-order algorithms designed to enforce sparsity.
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 per- spective 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 En consttriad zeroth-ordee optimization. By employing data-driven techniques to reduce variance, the paper not only
2

---

Published as a conference paper at ICLR 2024
Variance Reduction
-x
a(#)
Data
Bf(0)
-/((0)
Vfi(x)
the quality of0/100
It thresholding
Mitigate
Not Non-Expansev of Hard-Thrre hard-Thresholding
Quality of ZO Estimation
y >
(f((
Contradictons
Figure I: Motivation of our algorithm.
enhances the algorithm's convergence but also expands its utility across wider range of scenarios.
3. General Analysis: The introduction a general analysis framework another contribution to the paper. This framework systematically evaluates the performance and behavior of varying variance reduced algorithms under concosttaii and ZO gradient.
2 PRELIMINARIES
Throughout this paper, use ||0]| to denote the Euclidean norm for vector, ||0|| to denote the maximum absolute component of that vector, and ||0]lo to denote the to norm (which is not a proper norm). The following two assumptions widely adopted (Li et al. 2016 Nguyen al. 201 and are needed in this paper.
Assumption 1 (Restricted strong convexity (RSC) (Li et al.,
2016 Nguyen et al., 2017b)). A
differentiable function F is restricted Ps -strongly convex sparsity there exists generic constant Pg > 0 such that for any 0, 0' E Rd with ||0 - 0'1oo S 8, we have:
F(O) ((0) (VF(O') 8)
Ps 2
1
111
2016 Nguyen al. 2017b)). For any i [n), differentiable function f; is restricted ot -strongly smooth at sparsity level if there exists a generic constant pt > O such that for any 8, E Rdd with || 8' llo 8, we have
Assumption 2 (Restricted strong smoothness (RSS) ( ei al.
[V V (O)( S P3 p 0 0'|]-
We assume that the objective function F(0)) satisfies the RSC condition and that each component
function fe(0)) " 1=1 satisfies the RSS condition. We also define the restricted condition number as fg = pt//pp /p. . This assumption ensures that the objective function behaves like strongly convex and smooth function over sparse domain, even when it is non-convex.
2.1 70 ESTIMATE
Then, give zeroth-order gradient estimator below adopted by (de Vazelhes al., 2022):
v5(0) qu E(ro mu.) f(0))
where each random direction u; is unit vector sampled uniformly from the set {u E Rd: |u]lo < 82, ||u||| = =1, q is the number random unit vectors, and μ > is a constant called the smoothing radius (typically taken small possible, but no too small to avoid numerical errors). To obtain these vectors, we can first sample a random set of coordinates of size 82 from [d]. Following, sample random vector supported on S. in other words, uniformly sampled from the set {u E I u = 0. |u|| = 1}. Especially, if 82 = d, the general estimator is the usual vanilla estimator with uniform smoothing the sphere (Gao et al. 2018). Additionally, for convenience,

---

Published as a conference paper at ICLR 2024
define I' (f) as the support of 0" Let ((r) be sparse vector with ||0|7)|6 I k and support I(r) supp(O(r)) Define, with Hzx(-) (-) the hard-thresholding operator of sparsity 2k:
== supp(H2x (FF(")) (LF((H)((FFF(")
supp(t").
and let I = I(r) + I(++1)
+ I. Ep = P₂ 2 sd, EI 0(x2+2)
+ +3) + 2, Ex = (0-1)(e--1) d-1
2d ((22
((22-1) 1)
2dpt 882
[a-1]] +1) + p 2 sd.
Eabs
2.2 REVISIT OF SZOHT
Based on this assumption and ZO estimation, de Vazelhes proposed the SZOHT algorithm (de Vazel
hes al. 2022). The iteration relationship of this algorithm is:
g(r+1) Hu((((r) - ()((F((())
where H.)-) is the theshhlnesso operator and F((rr) is 70 gradient estimate defined by 3 7 represents learning rate. SZOHT can address some ZO co-constrained problems under specific conditions. However, it's important to note that the bard-thresholding operator, unlike the projection onto the & ball, lacks eonnexaansivessss. Consequently, has the potential to divert the algorithm's iteration away from the desired solution. To deal with this challenge, SZOHT imposes stringent limitations on both (hard- thandddheesh coefficients) and q. That is,
1
Ps
2
ke (4Ex p)
d-k- k'
(45I + 1)p² ?
2
Ps
and
if $2 > 1: g 2
16d(sz 1)k"* x² (d=+))
18k² - 1 + 2 9r²
1) +
d-1
2x
2
2-2
k
if 1:
S
g
Evidently, these conditions are exceedingly stringent and may not be suitable for numerous real- world problems. Therefore, we urgently need an algorithm with fewer constraints.
3 GENERAL ANALYSIS WITH VARIANCE
In this section, we will analyze the random 70 hard-thresholding algorithm from the perspective of variance and provide a positive response to the above questions. These algorithms can be described using the following general iterative expression:
g(r+1) H4() ng (0()))
where (0(+)) is the generalized gradient estimate (applicable all ZO hard-thresholding algo-
2 rithms). Let V
Then, we have:
Theorem 1. Assume that each ft is (D,,5') RSS and that F is (p_ -SC. For any stochastic zo threholdigo algorithm capable of expressing its iterative relationships as described in (4) we can establish the following:
B||g(r-1)
1¹1 < (1 + p= DEE ((()) -0-1 + n7 (r) (B(r)) 2na [F(B(r)) -F(O))
+ 2 Emp2
P
(5)
Remark 1. Differing from the approach in (Yuan et al. 2017 Nguyen et al.) 2017b de Vazel The et al. 2022), where the convergence inequality is segregated into linear convergence terms
4

---

Published as a conference paper at ICLR 2024
(represented as (1 + p p-s - )aEl(((r) 0 (5) and ervor terms (represented as a "'eey" 2nja -
in (5), we have introduced the gradient squared term of ( 113 to elucidate the role of variance better. We can transform 5 into the form of (Yuan et al 2017 Nguyen et al. [017bb de Vazelhes et al.) (202)) by establishing an upper bound for the gradient squared term,
which is often feasible for specific algorithms.
Conflict analysis through variance, It is worth noting that among these three components, only the gradient squared term ( encompasses both the sard-thresholding parameter (included by a) and the ZO gradient parameter (included by (((C)) [[2). In essence, this means that the conflict between expansivity and zeroth-order error can be fully encapsulated through the
gradient squared term. More importantly, when our attention is directed towards the gradient squared term, we discover that in cases where the gradient estimation is unbiased, we obtain ([(gg()) (0tr))11
Varllg(*) (0(*))] gradient estimation. This indicates that the conflict between the expansionary of hard- soundtthreshoddng and 7.0 error is actually between hard-thresholding and the variance of gradient estimation. In SZOHT, have (((r)) ()((()). Then, the gradient squared term becomes 17² a (F((() In this scenario, to guarantee algorithm convergence, it becomes essential to ensure that the gradient squared term remains within reasonable upper bound. Due the fact that a is already required to satisfy certain conditions (which are generated by linear convergence terms and eτтor terms), therefore, the sampling method for ZO gradients must restricted, which leads to a reduction in the variance. However, due to the technique of sampling used to reduce the variance, the limitation on the number y of random directions is introduced into SZOHT.
FF(((r))|| which means that E| ( only related to the variance of
Improvement plan. A natural idea is to use a more comprehensive variance reduction approach instead of only using sampling technique to reduce [E] [g (0(r))) which could effectively alleviate the conflict between ZO estimation and hard thresholding, ultimately enabling the design of algo- rithms with fewer constraints, broader applicability, and enhanced convergence speed. Based on this perspective, we have developed generalized variance reduction 70 hard-thresholding algorithm that leverages historical gradients. We will provide a detailed explanation of this algorithm in the next section.
4 PM-SZHT ALGORITHM FRAMEWORK
This section mainly presents the PM-SZHT algorithm framework along with its convergence anal- ysis. This framework encompasses the majority of unbiased stochastic variance-reduction ZO thrd-thresholding methods, providing a generalized Subsequuus,, we introduce the VR-SZHT algorithm, a special case under this framework. Additionally, we extend our discussion by introducing SARAH-ZHT (please note that the gradient estimate in this algorithm is biased) and providing its convergence analysis in the appendix.
4.1 PM-SZHT
We now present our generalized algorithm to solve the target problem [Ip which we name pM-SZHT (p Memorization Stochastic Zeroth-Order Threshhiresh...ng)... Each iteration of our algorithm is composed of two steps: (i) the gradient estimation step, and (ii) the hard thresholding step, where the gradient estimation step includes the variance reduce estimation and zeroth-order estimation. We give the full formal description of our algorithm in Algorithm (I..
In the gradient estimation step, we are utilizing the p-Memorization framework, which was originally proposed by Hofmann (Hofmann et al. (015)) to analyze the sequential stochastic gradient algorithm for convex and smooth optimization problems. It's worth noting that our gradient estimation can be seen as its zeroth-order variant (the zeroth-order estimation is shown in Section 2.2). Here, we select in each iteration a random index set J S [m] of memory locations to update according to:
(0), J azة
Vj Vj In]: at
otherwise
5

---

conference paper at ICLR 2024
Published as a conference
such that any j has the same probabidi of p/n being updated where p is the number of directions dirrectonne
updated each time (see (Hofmann et al. 20151/ The value of p set J. Vj. Eyej P(J) h. Its
probable probability is determined by some specific algorithm. For example, if P(J) = 1/ (p) if | = p. and
P[J]- = 0 otherwise. we obtain the p-SAGA -ZH algorithm. If (0) = 1 P,
". and P[[1: [[[1=]]]= = P.
we obtain a variant of the VR-SZHT algorithm from Section 4.2 Those are the Z0 hard-thresholding
versions of the Aigortthnns mentioned in Hofmann et al. (2015): Gu et al. (2020).
mentioned
in the hard thresholding step we only keep the k largest (in magnitude) components of the current iterate ((r). This ensures that all our iterates (including the last one) are k-sparse. This hard- thresholding operator has been studied for instance in (Shen and Li. 2017), and possesses several interesting properties Firstly, it can be seen as a projectie on the Eo ball. Second, aesortaann it not non eeeeepaeenannn contrary to other operators like the tott-hhres operain (Shen and L.i. 2017
rediuced zeroth-order Hard-Thrrshooldnng with Memoorizaaaae
Algorithm 1 Stochastic variance reduced (pM-SZHT)
Input: Learning rate 7) maximum number of iterations T, initial point (()), number of random directions and number of coordinates to keep at each iteration k.
Output: g(r).
1: for 1---e T do
2: Undaa ((0
3: Randoni
Randomly sample i, {1, ...,...,, .,., ,
4: g ( = /i. (0(r-1)) - ai (11
+ L. EE (1-1)
5:
g(r) H4 (0(r-1) ng (r (r (((r-1)))
6: end for
Convergence Analysis: We provide the cfnvergoo analysis of -M-SZAi using the aesumpessin from Section 2 and iemoonstate the correctness of the conclusion made in Section by assessingg whether
whether the algorithm Aegorithm converges dedeppendee of q.
Theorem 2. Suppose F(0) satisfies the RSC condition and that the funcionl [f,(0))=,sattii satisfy the RSS condition with 2k + k". For Algerithaar IJ suppoese that we run SZOHT with random supports of size $2, q random directions, a have:
I learming rate of n. and i coordinate aertiattes kept at each inch a We
here Ln = a n'e,p" 2 + 6asabs 222 + +66/2a Ar. L, = v [ ( 1
- 1
- - -10 - 2 + Lrr
(6)
- - -0"112 17 (4
+ 487 - - 2na + - )
2) + Zz= +=I- (d k) fir fi (0+ 113)) 7- (20 p
Remark 2. (System error). This format of result is similar to the ones in (Yuan et al. 2017
Nguyen et al. 2017b de Vazethes et al. 2022). the right of (23) contains linear convergence term
mimimmit er F(O"), }}. and system error 2h, Lyp We note that if F has a k. -sparse coonsttriii minimizer, which could happen in sparse (oomstruuctii or with Ponaaameeeeetn deep networks, then we would have F )l = 0 and ft, (f=((00)) )12 = O, and hence that part of the system vanish. In addition, we also have another system error Ly, which depends on the addiit
error woulld
smoothing radius μ. due to the error
p from the ZO estimate and the iterative method of à.
From this theorem, we we know that if the algorithm converges, 1) needs to lie in some theeal a
needs
s come specific interval. interval.
Conolarr 1. If
Corollary
A
ri app + )
S n) S max max /f + 2(48Erap: p + pp 48
converges. Here
Hfereff 1/ =
48Erap 4 1 +0
A = 4a² 4 - 4 4(485rapt + 1 p=)(1 - 2 2
+
'Originally, Memoriizationn directions in zeroth order
--Mooriization is called Memoooiizziinn We change it to p avoid conflicting with random
05
6

---

Published as a conference paper at ICLR 2024
Remark 3. (Independence of q) When k k", for any q > 0 the necessary condition A for 77) holds. We emphasize here that variance reduction can only make q unable to determine whether to converge, but q still affect the convergence speed. In other words, variance reduction can mitigate the conflict, but cannol resolve it.
4.2 VR-SZHT
To offer specific analysis, we introduce the VR-SZHT algorithm, which the adaptation of the original SVRG method and Zhang (2013) to our 70 hard-thresholding setting. In addition to the previously mentioned convergence analysis, we will also provide a complexity analysis to demonstrate the advantages of this algorithm, which extend beyond existing algorithm.
Algorithm 2 Stochastic variance reduced zeroth-order Hard- Bard-Thresholding (VR-SZHT)
Input: Learning 1), maximum number of iterations T, initial point 09, SVRG update frequency m. number of random directions g, and number of coordinates to keep at each iteration k.
Output: 0"
1: for r I.....T
T do
2:
(10) 01 00-1
3:
A 1 E.E (((00))
4: for 0.1....,m do
5:
Randomly sample i, E (1,2..... n): Compute ZO estimate Vf, (0(r)) (f(r)) ) Vi, (0(0);
6:
Øir+1) ((r) n ( ft, (0()) fr. (0(0) + β)); 8: gir+1) H4 (0irt)))
7:
9: end for
8" ((++1), random t' [m 1];
11:
end for
Theorem 3. Suppose F(0) satisfies the RSC condition and that the functions (f(0)); satisfy the
RSS condition with 2k + k. When 1) 2(48czapz p 4/ we have:
ap
8 ( < <<''s/_70 /B - -F(0")] + L L.
(8)
Here (1 + 17 ps 2 )a,
8Th
8-1 (2n) 48 ps a, o 200 18n1 at Ezer( (m
Po
B-1
4/ P. 3 and L' = 8-1 (72)) 2 Eaba/1 2 + up
2g / F ((0)) 1l (( 8" ||2 + 61)² 8m al a4 +
(d (d- k)) f., f.. (0
This theorem is similar to Theorem 2. And it is worth noting that y is also independent in VR-SZHT, and can be found the appendix due space limitations.
Corollary 2. The 70 query complexity of the algorithm is O (In+ thresholding query complexity is (log())).
log (t)) And the hard- K #
When comparing VR-SZHT with SZOHT, where the 7O query complexity of SZOHT is
O ((kk + _ log evident that the theehhhressolding query complexity of VR-SZHT significantly reduced. Further- more, as & becomes large, the ZO complexity is also reduced.
log (t)) and the hard-thresholding query complexity is O (x² logo() it becomes
EXPERIMENTS
We now compare the performance of VR-SZHT, SAGA-SZHT, and SARAH-SZHT (an adaptation of the SARAH variance reduction method (Nguyen et al. 2017a) to our ZO hard-three sanddthresholding setting, for which provide the convergence analysis in Appendix with that of the following algorithms,
7

---

Published as a conference paper at ICLR 2024
in terms of IZO (iterative zeroth-order oracle, i.c. number of calls to fi) and NHT (number of hardthhresholding operations):
. SZOHT dde Vazelhes al. 2022): ) vanilla stochastic ZO hard-thresholding algorithm.
FGZOHT: the full gradient version of SZOHT.
Ridge Regression We first consider the following " regression problem, where malfunctions fi are defined as follows: f((0) = (x: 0 y1)22 + 2110 where À some regularization parameter. We generate each randomly from a unit norm ball in R., and a true random model 0* from a normal distribution (0, Iaxa). Each ys is defined as yi x 0r. We set the constants of the problem as such: = 10, d = 5, À = 0.5. Before training, we preprocess each column by subtracting its mean and dividing it by its empirical standard deviation. We run each algorithm with k = 3. 200, 1 10_1, = d = 5. and for the variance reduced algorithms, we choose = 10. For all algorithms, the learning rate rj found through grid-search in (0.005, 0.01, 0.05, 0.1, choose the learning rates giving the lowest function value (averaged over several runs) at the end of training. We stop each algorithm once its number of IZO reaches 80,000. All curves are averaged over 3 runs, and plot their mean and standard deviation in Figure 2 As we can observe, SZOHT converges to higher function values than other algorithms: this illustrates the advantage of the variance reduction techniques, which can allow attain smaller function values than plain SZOHT, but at a cheaper cost than FGZOHT.
H10
08
voco wine
NHT
Figure 2: #IZO and #NHT on the ridge regression task.
IZ0
NHT
Figure 3: #1ZO and #NHT on the few pixels adv. attacks (CIFAR-10), for the original class 'airplane".
Few Pixels Universal Adversarial Attacks Finally, we consider a few-pixel universal adversarial attacks problem. Let some classifier be trained on dataset of images. We assume that it can only be accessed as a black box, i.c. only returns the log probabilities of each estimated class, given an input image. This is a typical real-life scenario, where for instance the model can only be accessed through a provider's API. We seek to find a single perturbation 0 E TRd.. to apply to several images at once, (we denote those images by 2;, {L, ...... r2). and their true label as y:) make the predicted class for those images different than their true class. Further discussion on universal perturbations can be found in (Dezfooli et al. 2017). In addition, we seek adversarial perturbation that is sparse, to preserve as much as possible the original image. As is usual in black- box adversarial attacks, we maximize the following Carlini- Wagner loss (Carlini and Wagner 2017; Chen al., 2017). which encourages the prediction from the model to be different from the true class:
Carlini-Wagner
(0) = max Fy (clip(x; + 0)) max (clipp( + 0)), 0}. jæy.
where z; is the original i-th image (rescaled to have values in [00.5, 0.5)). of true class yt. clip denotes the clipping operation into [-0.5, 0.5), 0 is the universal perturbation that seek optimize, and
8

---

Published as a conference paper at ICLR 2024
Table Comparison of universal adversarial attacks on 10 images from the CIFAR-10 test-set, from the 'airplane' class. For each algorithm, the leftmost image is the sparse adversarial perturbation applied to each image the row. ("auto' stands for "automobile", and 'plane' for 'airplane")
Image ID
3
27
44
90
97
98
111
116
125
153
Original
FGZOHT
plane
plane
plane
ship
deer
plane
plane
plane
ship
truck
SZOHT
plane
plane
plane
plane
deer
plane
bird
bird
ship
fruck
VR-SZHT
plane
plane
auto
plane
ship
plane
plane
plane
ship
truck
SAGA-SZHT
plane
frog
plane
plane
deer
plane
plane
plane
ship
ship
SARAH-SZHT
plane
plane
auto
ship
ship
plane
bird
plane
frog
truck
each function Fs outputs the log- ogg-robbbblliyy of image being of class k as predicted by the model,
for ls E {1..., K), with the number of classes (similarly to (Chen al., 2017: Liu al. 2018 Huang et al. 2019)). Similarly to Liu et al. (2018) (Appendix A.11), we evaluate the algorithm on dataset of 10 images from the test-set the CIFAR-10 drtzsee(KKizheevsky dimensionality 32 x 32 x 3 3, 072, from the same class 'airplane', which we display in Table We take as model a fixed neural network, already trained on the train-set of CIFAR- 100 obtained from the supplementary material of (de Vazelhes al. 2022). We set 60, 0.001,
al. 2009). of
10,
82 = = 3, 072, and the number inner iterations of the variance reduced algorithms to m = 10. We check each iteration the number of IZO, and stop training if it exceeds 600. Finally, for each algorithm, we grid-search the learning rate 7) in {0.001, 0.005, 0.01, 0.05). The best learning rates (giving the curve which obtained the smallest minimum function value), respectively: FGZOHT: 0.05. SZOHT: 0.005, VR-SZHT: 0.01, SAGA-SZHT: 0.05, SARAH-SZHT: 0.05. Our experiments conducted
workstation of 128 CPU cores. The training curves are presented in Figure 3 SAGA-SZA SZHT obtains the lowest function value at the end of the training, followed by SARAH-SZHT. In terms of attack success rate, SARAH-SZA attacked 7/10 images. We provide further results, on 3 more classes ('ship", 'bird", and 'dog') in the appendix, which demonstrate even further the advantage of variance reduction methods in our setting.
presents the highest success rate, has successfully
CONCLUSION
In this paper, introduce a novel approach to address sparse zero-order optimization problems and leverage it to enhance existing algorithms. We perform a comprehensive convergence analysis of the generalized variance reduction algorithm, showcasing how variance reduction effectively mitigate the limitations inherent in existing algorithms. To substantiate our claims, we validate our algorithm through experiments involving ridge regression and adversarial attacks.

---

Published as a conference paper at ICLR 2024
REFERENCES
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic optimiza- tion via conditional gradient and gradient updates, Advances in Neural Information Processing Systems, 31, 2018.
Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing, Applied and computational harmonic analysis, 27(3):265-22 274, 2009.
Peter Bühlmann and Sara Van De Geer. Statisties for high-dimensional data: methods, theory and applications. Springer Science & Business Media, 2011.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pages 39-57. Ieee, 2017.
Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and ChoJui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 15-26, 2017.
Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm: Zeroth-orde adaptive momentum method for black-box optimization, Advances in neural information processing systems, 32, 2019.
Krzysztof Choromanski, Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, Deepali Jain, Yuxiang Yang, Atil Iscen, Jasmine Hsu, and Vikas Sindhwani. Provably robust blackbox optimization for reinforcement learning. In Conference on Robot Learning, pages 683-696. PMLR, 2020.
William de Vazelhes, Hualin Zhang, Huimin Wu, Xiaotong Yuan, and Bin Gu. Zeroth-order hard- thresholding: Gradient error vs. expansivity. Advances Neural Information Processing Systems, 35:22589-2248 2022.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
SM Moosavi Dezfooli, F Alhussein, F Omar, F Pascal, and S Stefano. Analysis of universal adversarial perturbations. arXiv preprint 10V::1705009554, 2017.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL hatt:: ics. uci. edu/ml
Jannqig Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 1344456):334-116)) 2001.
X. Gao, B. Jiang, and S. Zhang. On the information-adaptive variants of the admm: An iteration complexity perspective. Journal of Scientific Computing, 76(1):327-363, 2018.
Bin Gu, Wenhan Xian, Zhouyuan Huo, Cheng Deng, and Heng Huang. unified q-memorization framework for asynchronous stochastic optimization. The Journal of Machine Learning Research, 21(1):7761-7813, 2020.
Hofmann, A. Lucchi, S. Lacoste-Julien, and B. Mewilliams, Variance reduced stochastic gradient descent with neighbors. Mathematics, 2015.
Feihu Huang, Bin Gu, Zhouyuan Huo, Songcan Chen, and Heng Huang. Faster gradient-free proximal stochastic methods for nonconvex nonsmooth optimization. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1503-1510, 2019.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m m-estimation. Advances in neural information processing systems, 27, 2014.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
10

---

Published as a conference paper at ICLR 2024
Xingguo Li, Raman Arora, Han Liu, Jarvis Haupt, and Tuo Zhao. Nonconvex sparse learning via stochastic optimization with progressive variance reduction. arXiv preprint arXiv: 111...005.221.. 2016.
Sijia Liu, Bhavya Kailkhura, Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018.
Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu. unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. 2012.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions.
Foundations of Computational Mathematics, 17:527-566, 2017.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. International conference on machine learning, pages 2613-2621. PMLR, 2017a.
Nam Nguyen, Deanna Needell, and Tina Woolf. Linear convergence of stochastic iterative greedy algorithms with sparse constraints. IEEE Transactions on Information Theory, 63(1 1):6869-6895, 2017b.
Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011.
Garvesh Raskutti, Martin Wainwright, and Bin Yu. Minimax rates estimation for high-dimensional linear regression over fg-balls. IEEE transactions on information theory, 57(10)66976 6994, 2011.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.038%: 2017.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1033-7133, 2017.
Jie Shen and Ping Li. A tight bound of hard thresholding. The Journal of Machine Learning Research, (8(1) 2017.
ChunChen Tu, Paishun Ting, PinYu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, ChoJui Hsieh, and ShinMing Cheng. Autozoom: Autoencoder-basse zeroth order optimization method for attacking black-box neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, number 01, pages 742-749, 2019.
Joaquin Vanschoren, Jan N Van Rijn, Bernd Bischl, and Luis Torgo. Openml: networked science in machine learning. ACM SIGKDD Explorations Newsletter, 15(2): 60, 2014.
Xiaotong Yuan and Ping Li. Stability and risk bounds of iterative hard thresholding. International Conference Artificial Intelligence and Statistics, pages 1702-1710. PMLR, 2021.
Xiao'Tong Yuan, Ping Li, and Tong Zhang. Gradient hard thresholding pursuit. J. Mach. Learn. Res., 18(I):6027-6069, 2017.
CunHui Zhang. Nearly unbiased variable selection under minimax concave penalty. 2010.
Pan Zhou, Xiaotong Yuan, and Jiashi Feng. Efficient stochastic gradient hard thresholding. Advances in Neural Information Processing Systems, 31, 2018
11


Reviews:
[{"review_id": "4OtEYoYV7w", "reviewer": "Reviewer_5xEJ", "summary": "This paper  provides a new insight into variance reduction: mitigating the unique conflicts between ZO gradients and hard-thresholding. Under this perspective, this paper proposes 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.", "questions": "Since the Problem (1) is NP-complete, what  is $\\theta^*$ in the convergence analysis? If $\\theta^*$ is the optimal point of Problem (1), why can the proposed algorithm can achieve a  linear convergence rate which means it is a polynomial time algorithm that can solve a NP-complete problem?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "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.", "weaknesses": "Typo:\nIt should be $\\| \\nabla f_i(\\theta) - \\nabla f_i(\\theta') \\| \\leq \\rho_s^+ \\|\\theta - \\theta'\\|$ in the Assumption 2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "W5rBPtbw0B", "reviewer": "Reviewer_TcW5", "summary": "The paper presents a new algorithm for solving sparse learning problems in machine learning. By incorporating variance reduction techniques, the algorithm improves convergence rates and expands its applicability. It offers a solution to conflicts between zeroth-order gradients and hard-thresholding and provides a general analysis framework. Overall, the paper contributes an efficient and effective approach for sparse learning.", "questions": "1. Could the authors elaborate more on what's the conflict between the expansionary of hard-theresholding and ZO error about? And how it affects the performance of zeroth-order hard-thresholding algorithms?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. This paper introduces an interesting perspective, i.e., variance reduction, to improve existing zeroth-order hard-thresholding algorithms.\n2. This paper has provided sound theoretical analysis for the newly proposed algorithm.", "weaknesses": "1. There are many symbol error as well as misleading notations in the paper, which requires further correction. E.g., the $k^*$ should be s in Assumption 1; no introduction of $\\mu$ in eq. 3; no explanation for $H_{2k}$ in page 3 when it appears at the first time; what's the meaning of J in page 5? how to get the i in page 5? and so on. This will make it hard for readers to understand the paper.\n2. More details and discussion for experiment section, e.g., the explanation on IZO and NHT in Fig.2,3, how to tell VR-SZHT is better in Table 1?\n3. More experiments may do a better job in supporting the advantages of the VR-SZHT algorithm. Currently, VR-SZHT seems to be even worse than baselines in some cases, e.g., Fig. 3.\n\nPS: it's really hard for reviewers to point out which equation when there is no equation number!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "RHAon1mRxN", "reviewer": "Reviewer_iAcw", "summary": "The paper provides a new analysis of SZOHT and provides a new perspective on conflict of zeroth-order methods and hard thresholding, then introduces variance reduction to improve convergence.", "questions": "Out of curiosity, when applying variance reduction to SZOHT, are there any major technical difficulties in the analysis or major new techniques used in the work?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The generalized algorithm framework and analysis are comprehensive, demonstrating the role of variance in convergence guarantee.\n2. The introduction of variance reduction into SZOHT is new and query complexity is reduced.", "weaknesses": "1. I don't see major weaknesses of the work, maybe more experiments on larger scale problems would further validate the practical benefits of variance reduction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "ahYsxhYG4L", "reviewer": "Reviewer_wexC", "summary": "This paper first proposes a general convergence analysis on stochastic zeroth-order hard-thresholding algorithms with variance. Based on the theoretical analysis, this paper further proposes a generalized variance reduced zeroth-order hard-thresholding algorithm. Theoretical results demonstrate the new algorithm has improved convergence rates and broader applicability compared with existing methods by eliminating the restrictions on the number of random directions. Experiments on both ridge regression and black-box adversarial attack demonstrate the effectiveness of proposed method.", "questions": "- My first concern is on the usefulness of zeroth-order oracles. From experiments in this paper, it seems that we have easy access to gradient information in all these applications. Therefore, why do we need to emphasize zeroth-order algorithms? The authors may consider some other applications where gradient information is hard to obtain. \n- Another concern is on the setting of L0 regularization. While there exist many other approaches on obtaining sparse solutions (e.g., LASSO), the authors may need to justify the necessity of using L0 regularization here.  \n- I am a bit confused on the key contribution of this work. The authors introduced two algorithms, pM-SZHT and VR-SZHT. What is the key difference of these two algorithms? Moreover, pM-SZHT is not compared in experiments, but SARAH/SAGA-SZHT is compared. This is also very confusing and may need some explanations. \n- It seems that SAGA-SZHT is missing in both the main text and appendix. Given its good performance in Table 1, I am a bit confused on why it is not properly introduced. Are there some errors? \n- Regarding experimental results, I am a bit confused by Figure 3. It seems that SZOHT converges faster than all other methods, but gradually becomes worse with more iterations. Some explanations may be needed here on why we need so many iterations after convergence. \n- Also, the evaluation of few-pixels universal adversarial attacks may seem a bit restricted with only 10 images from the same class. It would be better if the authors can use more images from different classes to further justify the effectiveness of proposed method.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The idea of combining variance reduction with zeroth-order hard-thresholding methods should be novel", "weaknesses": "- The proposed method is not clearly introduced and has many confusing points. \n- Experiments is not very supportive for the proposed method, details can be found in Questions part", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "WrMrSzMdcv", "reviewer": "Reviewer_CZzv", "summary": "The paper introduces a new algorithm for solving $\\ell_0$ constrained optimization problems using zeroth-order (ZO) gradients, specifically targeting the limitations of the SZOHT algorithm, which is currently the only algorithm addressing this problem. The main limitation of SZOHT is the conflict between ZO gradients and the expansivity of the hard-thresholding operator, which restricts the number of random directions. The proposed algorithm takes a novel perspective by considering the role of variance and introduces a generalized variance-reduced ZO hard-thresholding algorithm. The paper provides theoretical analysis and demonstrates that the new algorithm overcomes the limitations of SZOHT, resulting in improved convergence rates and broader applicability. The utility of the proposed method is illustrated through experiments on a ridge regression problem and black-box adversarial attacks.", "questions": "Please refer to the weakness section for detailed feedback. Overall, I appreciate the paper for its natural motivation and principled solutions. However, there are several issues with the presentation that need to be addressed. During the rebuttal phase, I encourage the authors to resolve the mentioned concerns or correct any misunderstandings I may have. I suggest that the authors respond to my questions in multiple phases if they need much time to solve all the issues, allowing for further clarification if needed. For instance, it would be helpful to begin with the related works section and provide the algorithm for SAGA-SZHT as a priority. One suggestion is for the authors to incorporate the appendix into the current PDF version of the paper. This would enhance convenience for reviewers, allowing them to access all relevant information in a single document.\n\nBased on the current version of the paper, I have given it a borderline score. However, I will reconsider my evaluation based on the authors' responses during the rebuttal phase. I would like to defend my positive attitude towards the paper if my concerns and issues are effectively addressed.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The paper presents a well-motivated and principled approach to resolving conflicts between zeroth-order methods and hard thresholding. The authors offer a fresh perspective on the problem, providing innovative insights and potential solutions.\n2. The paper introduces a comprehensive analysis framework that evaluates the performance and behavior of variance-reduced algorithms under the $\\ell_0$-constraint and zeroth-order gradient settings.\n3. The paper includes rigorous theoretical analysis, establishing a solid foundation for the proposed algorithm. The theoretical justifications and proofs contribute to the robustness of the research and build confidence in its practical applicability. Additionally, the paper demonstrates the versatility of the proposed method through applications in ridge regression and black-box adversarial attacks, highlighting its real-world relevance and effectiveness.", "weaknesses": "1. The paper lacks a proper related work section, which makes it challenging for readers to quickly grasp the background and understand the previous works. It is crucial to include a comprehensive discussion on related works, especially regarding the variance-reduced ZO hard-thresholding algorithm and the variance reduction aspect.\n2. The paper suffers from a lack of necessary references, such as papers on SAGA, SARAH, and SVRG methods. When these methods are initially mentioned, it is essential to provide corresponding references. Additionally, there are errors in the appendix due to bibtex errors, which should be carefully reviewed and corrected.\n3. The presentation of baselines and experimental settings in the main text is not well-organized. It is recommended to reorganize this information to improve clarity, especially for readers who are unfamiliar with the baselines and adversarial attacks. Providing a cross-reference to the appendix can also help readers gain a better understanding.\n4. The introduction of SAGA-SZHT is missing from the paper, and it cannot be found. It is necessary to either locate the missing information or add it during the rebuttal phase.\n5. The authors propose three variants of VR-SZHT by utilizing SVRG, SARAH, and SAGA. It would be beneficial to summarize the advantages of each method in terms of memory storage and convergence rate, similar to what is found in the variance-reduction literature. Providing tables or summaries can help readers compare and understand the individual strengths of these methods.\n6. It is well-known that variance-reduction methods can improve the convergence rate of SGD from sublinear to linear under strongly convex and smoothness conditions. It would be interesting to clarify whether VR-SZHT exhibits a similar improvement compared to SZOHT. If there are notable differences, the authors should provide explanations or insights into the reasons behind these variations.\n7. I am curious to know if there are any additional technical challenges when integrating VR methods into SZOHT and proving the convergence rate, compared to applying VR methods to traditional finite-sum tasks. The response to this question will not impact my final evaluation of the paper's novelty. However, it will help me gain a better understanding of the paper's correctness and soundness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "tABrhNwUsA", "reviewer": "Reviewer_7pPP", "summary": "This paper studies efficient zeroth order (ZO) algorithms for solving $\\ell_0$-constrained optimization problems. While existing approach alternate between gradient descent and hard thresholding, it only works well in restricted settings. This paper makes the novel observation that large variance  of gradient estimation would result in conflict between ZO gradient and expansity of hard-thresholding operators. To resolve this issue, the authors prodive a variance reduced ZO hard-thresholding algorithm, and theoretically demonstrate that the variance-reduced algorithm is guaranteed to converge under standard assumptions and eliminates the requirement of the random direction sampled. Finally, the authors demonstrate the superiority of their algorithm by solving portfolio and adversatial attacks.", "questions": "The paper [1] considers a stochastic optimization setting while the current paper studies finite-sum optimization. Can there be a way to reduce the variance for [1]'s setting?\n\n[1] de Vazelhes, W., Zhang, H., Wu, H., Yuan, X., & Gu, B. (2022). Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity. Advances in Neural Information Processing Systems, 35, 22589-22601.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Both the algorithm and the analysis presented in this paper seem novel. Notably, the role of variance discovered by this paper is found by establish a new descent inequality (Theorem 1), and based on this discovery a variance reduced algorithm is introduced.\n\n2) The paper is in general well-written and not hard to read. The authors introduce necessary background of ZO in the introduction section and also discuss previous works, making it easier to understand the contribution of this paper.\n\n3) Besides sound theoretical results, extensive experiments are also conducted to verifty the efficiency of the proposed algorithm.", "weaknesses": "1) Some quantities seem to be used before being defined: $k*$ and $\\kappa$ in Sec. 2.2, $\\hat{g}_I^{(r)}$ in Theorem 1.\n\n2) In the experiments, I think the authors can add more comparison on computational cost and also comparisons with first-order methods or other methods as well, to highlight the benefits of using zeroth order optimization. I'm not an expert in zeroth order optimization, so I think adding such comparisons could make your results more convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (poster)