Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity
Authors: William de Vazelhes
Hualin Zhang
Huimin Wu
Xiaotong Yuan
Bin Gu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sparse learning
Hard-thresholding
Zeroth-order
Stochastic optimization

Abstract: $\ell_0$ constrained optimization is prevalent in machine learning, particularly for high-dimensional problems, because it is a fundamental approach to achieve sparse learning. Hard-thresholding gradient descent is a dominant technique to solve this problem. However, first-order gradients of the objective function may be either unavailable or expensive to calculate in a lot of real-world problems, where zeroth-order (ZO) gradients could be a good surrogate. Unfortunately, whether ZO gradients can work with the hard-thresholding operator is still an unsolved problem.
To solve this puzzle, in this paper, we focus on the $\ell_0$ constrained black-box stochastic optimization problems, and propose a new stochastic zeroth-order gradient hard-thresholding (SZOHT) algorithm with  a general ZO gradient estimator powered by a novel random support sampling. We provide the convergence analysis of SZOHT under standard assumptions.   Importantly, we   reveal a conflict between  the deviation of  ZO estimators and  the expansivity of the hard-thresholding operator,  and provide a theoretical   minimal value of the number of random directions in ZO gradients. In addition,  we find that the query complexity of SZOHT is independent or weakly dependent on the dimensionality under different settings.  Finally, we illustrate the utility of our method on a portfolio optimization problem as well as black-box adversarial attacks.

Zeroth-Order Hard-Thresholding Gradient Error vs. Expansivity
William de Vazelhes', Hualin Zhang", Huimin Wu², Xiao-Tong Yuan?, Bin Gu
*Mohamed bin Zayed University of Artificial Intelligence
Nanjing University of Information Science & Technology
Hydevazelhes,zhanngee zhanghualin98, xttetttttxnnnnnn (tg.aa1190...ggaaaaaaggr jsgubin)(gmail.commm.o...mmm com, vuhuimin@nuist. edu. cn
Abstract
tn constrained optimization is prevalent in machine learning, particularly for high- dimensional problems, because it is fundamental approach to achieve sparse learning. tard-lhresholding gradient descent is a dominant technique to solve this problem. However, first-order gradients of the objective function may be either unavailable or expensive to calculate in a lot of real-world problems, where zeroth-order (7O) gradients could be good surrogate. Unfortunately, whether 70 gradients can work with the hard-thresholding operator is still an unsolved prob- lem. To solve this puzzle, in this paper, focus the to constrained black-box stochastic optimization problems, and propose new stochastic zeroth-order gradi- ent hard-thresholding (SZOHT) algorithm with general ZO gradient estimator powered by a novel random support sampling. We provide the convergence analysis of SZOHT under standard assumptions. Importantly, the deviation of ZO estimators and the expansivity of the hard shre-thheeholding opera- tor, and provide theoretical minimal value of the number of random directions in ZO gradients. In addition, we find that the query complexity of SZOHT is independent or weakly dependent on the dimensionality under different settings. Finally, we illustrate the utility of our method on portfolio optimization problem as well as black-box adversarial attacks.
reveal conflict between
Introduction
to constrained optimization prevalent in machine learning, particularly for high-dimensional problems, because it is fundamental approach to achieve sparse learning. In addition to improving the memory, computational and environmental footprint of the models, these sparse constraints We formulate the
help reduce overfitting and obtain consistent statistical estimation [6 33 29 problem as follows:
min [f(x) = Bef {)}. wERd
s.t.
||0||0 < A
where f(:,E) RR : R is a differentiable function and & is noise term, for instance related to an underlying finite sum structure in f.of the form: Eę/(xr, { = - (x) thrd-thhesholding gradient algorithm 17
is a dominant technique to solve this problem. It generally consists in alternating between a gradient step, and hard-thresholding operation which only keeps k-largest components (in absolute value) of the current iterate. The advantage of hard threshhhrsh over its convex relaxations ((39 41) is that can often attain similar precision, but more computationally efficient, since it can directly ensure desired sparsity level instead of tuning e penalty or constraint. The only expensive computation hard-three hard-thresholding is the hard-thresholding step itself, which requires finding the top & elements of the current iterate. Hard-thresholle thw.shhldihhingggg developed in full gradient form [7]], but has been later on extended to the stochastic setting by
31 45
originally
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table I: Complexity of sparsity-enforcing algorithms. We give the query complexity for precision E, up the system error (see section 4.. For first-order algorithms (FO), we give in terms of number of first order oracle calls (HIFO), that is, calls to V [z E), and for ZO algorithms, in terms of calls of ((. Here R denotes the condition number L. with L is the smoothness (or RSS) constant and is the strong-convexity (or RSC)
constant.
Type
Name
Assumptions
#IZO##IFO
#HT ops.
FO/Lo
StolHT [1
RSS, RSC
(oxl))()))
(ogg())))
ZO/
RSPGF [4
smooth
0 (
701/
2
convex, smooth
O ((7)
s-sparse gradient, weakly sparse hessian, smooth; RSCais
ZOI4
ZORO
O(s log(d) log(t))
ZO16
SZOHT
RSS, RSC
O + 2)m² log(
Ok log(
ZOH
SZOHT
smooth, RSC
O(ky² log(2))
O(x² log(
The definition of Restricted Strong Convexity from 7 is different from ours and that of 31] hence
the bis subscript. We refer to the modified version of ZSCG (Algorithm 3 in (2)).
RSPGF and ZORO minimize f(x) + A||z||] only f needs to be smooth.
Nguyen et al. [3I,, which developed a stochastic gradient descent (SGD) version of hard thresholding (StolHT), and further more with Zhou et al. 47), Shen and Li 36 and Li et al. 20)). which used variance reduction technique to improve upon StolHT.
However, the first-order gradients used in the above methods may be either unavailable expensive to calculate in a lot of real-world problems. For example, in certain graphical modeling tasks (42), obtaining the gradient of the objective function is computationally hard. Even worse, in some settings, the gradient is inaccessible by nature, for instance bandit problems [35]. black-box adversarial attacks 44 9 10), or reinforcement learning [34 27 [T] To tackle those problems, ZO optimization methods have been developed [30]. Those methods usually replace the inaccessible gradient by its finite difference approximation which can be computed only from function evaluations, following the idea that for a differentiable function f R > RR we have: f'(x) = lim,-so f(x+h)-f(=) Later on, ZO methods have been adapted to deal with a convex constraints set, and can therefore be used to solve the e, convex relaxation of problem [T.. To that end, Ghadimi et al. [14,, and Cai et al. 7 introduce proximal ZO algorithms, Liu et al. (24 introduce a ZO projected gradient algorithm and Balasubramanian and Ghadimi (2) introduce 70 conditional gradient [19] algorithm. We provide review of those results in Table As can be seen from the table, their query complexity is high (linear in d), except (7] that has a complexity of O(s log (d) log( )). but assumes that gradients are sparse. In addition. those methods must introduce a hyperparameter À (the strength of the l penalty) or R (the radius of the & ball), which need to be tuned to find which value ensures the right sparsity level. Therefore, it would be interesting to use the hard-thresholding techniques described in the previous paragraph, instead of those convex relaxations.
Unfortunately, ZO hard-thresholding gradient algorithms have not been exploited formally. Even more, whether Z0 gradients can work with the hard-thresholding operator still an unknown problem. Although there was one related algorithm proposed recently by Balasubramanian and Ghadimi (2), they did not target Eo constrained optimization problem and importantly have strong assumptions in their convergence analysis. Indeed, they assume that the gradients, as well as the solution of the unconstrained problem, are s-sparse: || (=))lo S s and | S s* Rd 8, where xx arg min,, fxx). In addition, it was recently shown by Cai et al. 77] that they must in fact assume that the support of the gradient is fixed for all x E X, for their convergence result to hold, which is hard limitation, since that amounts to say that the function f depends on s fixed variables.
To fill this gap, in this paper, we focus on the to constrained black-box stochastic optimization problems, and propose novel stochastic zeroth-order gradient hard-thresholding (SZOHT) algorithm. Specifically, we propose a dimension friendly 70 gradient estimator powered by a novel random support sampling technique, and then embed it into the standard hard-thresholding operator.

---

2 7 We then provide the convergence and complexity analysis of S2OHT under the standard assumptions of sparse learning. which are restricted strong smoothness (RSS), and restricted strong convexity (RSC) 33 36 to retain generality, therefore providing a positive answer to the question of whether 70 gradients can work with the trrethhresholding operator. Crucial to our analysis is to provide carefully tuned requirements on the parameters (the number of random directions used to estimate the gradient, further defined in Section (.1c and k. Finally, we illustrate the utility of our method on a portfolio optimization problem as well as black-box adversarial attacks, by showing that our method can achieve competitive performance in comparison to state the art methods for sparsity-efforcing zeroth-ordes algorithm deseribed in Table I such as [1 77.
Importantly, we also show that in the smooth case, the query complexity of SZOHT independent of the dimensionality, which is significantly different to the dimensionality dependent results for most existing 7O algorithms. Indeed, it is known from Jamieson et al. [8] that the worst case query complexity of 70 optimization over the class Fu,z of v-strongly convex and T-smooth functions defined over a convex set X' is linear in d. Our work is thus in line with other works achieving dimension-insensittve query complexity in zeroth-order optimization such as [S] 37
6
22 [8), but contrary to those, instead of making further assumptions (i.e. restricting the class F2, to smaller class), we bypass the impossibility result by replacing the convex feasible set X' by non-conver set (the to ball), which is how we can avoid making stringent assumptions on the class of functions f.
Contributions. We summarize the main contributions of our paper follows:
1. We propose new algorithm SZOHT that is, up to our knowledge, the first zeroth-order sparsity constrained algorithm that is dimension independent under the smoothness assumption, without assuming any gradient sparsity.
2. We reveal an interesting conflict between the error from zeroth-order estimates and the hard- thresholding operator, which results in minimal value for the number of random directions q that is necessary to ensure at each iteration.
3. We also provide the convergence analysis of our algorithm in the more general RSS setting, providing, up to our knowledge, the first zeroth-order algorithm that can work with the usual assumptions of RSS/RSC from the hard hard-thresholding literature.
Preliminaries
Throughout this paper, denote by ||ж||| the Euclidean norm for vector Rd, by || the maximum absolute component of that vector, and by |o the Eu norm (which is not a proper norm). For simplicity, denote fe(
E). We call uF (resp. V=f(=)) the vector which sets all coordinates & F of u (resp. V f=(x)) to O. We also denote by x" the solution of problem (T) defined in the introduction, for some target sparsity 1-" which could be smaller than k. To derive our result, we will need the following assumptions on f.
Assumption 1 ((v,,) -RSC. [7 28 26 45 20 36 31). f is said to be vs restricted strongly convex with sparsity parameters if it is differentiable, and there exist a generic constant V, such that for all (xx y) E Rd with | yllo= S s:
f(y) 2 f(x) + (Vf()). -- x)
Vz -1 y1l
yl2
Assumption 2 ((I,, RSSS 36 31). For almost any &. Se is said to be T.g restricted smooth with sparsity level if it is differentiable, and there exist a generic constant T., such that for all (x. y) E Rd with | - yllo= S s:
[VVe(()) - -Ve(vll S -.1x-yy yll
Assumption 3 2fN- 166, Assumption 2.3 (Finite Gradient Noise)). f is said to have o-finite gradient noise for almost any &, fe is differentiable and the gradient noise a = =off defined below is finite:
Be Ve )1
Remark 1. Even though the original version of (T6 uses the Eo norm, we use the Eox norm here, in order to give more insighiful results in terms of lo and d, as is done classically in to optimization, similarly to [47]. We also note that in [66,, x² denotes an unconstrained minimum when our case it denotes the constrained minimum for some sparsity k".
3

---

For Corollary 2 we will also need the more usual smoothness assumption: Assumption 4 (L-smooth), For almost any &. fe is said to be L smooth, if it is differentialle, and for all (z. y) E :²:
& L||= -yll
3 Algorithm
3.1 Random support Zeroth-Order estimate
In this section, we describe our zeroth-order gradient estimator. It basically composed of random support sampling step, followed by a random direction with uniform smoothing on the sphere supported by this support. We also use the technique of averaging our estimator over g dimensions, as described in [25]. More formally, our gradient estimator is described below:
Vfe(x) = qu
(felæ + j.u,) -fe(z))
(2)
where each random direction u, is a unit vector sampled uniformly from the set S = {u e R : ||u/|o I $2, |/|| = 1). We can obtain such vectors u by sampling first a random support S (i.e. set of coordinates) of size $2 from [d]. (denoted as S ~ U ((()) in Algorithm 1) and then by sampling a random unit vector u supported on that support S, that is, uniformly sampled from the set Sg := {u E R U(d-s = 0, |||/|| 1}. (denoted as u U(S)) in algorithm 1). The original uniform smoothing technique on the sphere is described in more detail in [12]. However, in our case, the sphere along which we sample is restricted
random support of size $2. Our general estimator, through the setting of the variable 82, can take several forms, which are similar to pre-existing gradient estimators from the literature described below:
sf d. fe (x) is the usual vanilla estimator with uniform smoothing on the sphere [12 If S 82 S d, our estimator is similar to the Random Block-Coordinate gradient estimator from Lian et al. [21]. except that the blocks are not fixed at initialization but chosen randomly, and that we use uniform smoothing with forward difference on the given block instead of a coordinate-wist estimation with central difference. This random support technique allows to give a convergence analysis under the classical assumptions of the theeshhhresolding literature (see 3cmark(3), and to deal with huge scale optimization, when sampling uniformly from unit d-sphere is costly 7 6 in the distributed setting for instance, each worker would just need to sample sp-spe random vector, and only the centralized server would materialize the full gradient approximation containing up to q82 non-zero entries.
Error Bounds of the Zeroth-Order Estimator. We now derive error bounds on the gradient estimator, that will be useful in the convergence rate proof, except that we consider only the restriction to some support F' (that is, we consider a subset of components of the gradient/cstimato)) Indeed, proofs in the fard-thresholding literature (see for instance (45). are usually written only on that support. That is the key idea which explains how the dimensionality dependence is reduced when doing SZOHT compared to vanilla ZO optimization. We give more insight on the shape of the original distribution of gradient estimators, and the distribution of their projection onto a hyperplane F in Figure in Appendix E We can observe that even if the original gradient estimator poor, in the projected space, the estimation error is reduced, which we quantify in the proposition below.
Proposition 1. (Proof in Appendix C.3 Let us consider any support F C [d] of size s ({F) s). For the Zo gradient estimator (2). with q random directions, and random supports of size $2, and assuming that each fg (Iez, RRS, we have, with V Frfg (x) denoting the hard thresholding of the gradient V fe((z) (x: on F (that is, we set all coordinates not in F to 0):
(a) [EVFfe(z) Vefe(=) < Emp
(b) V =t
E Vr f2(2)]1 Eats/1?
(c) E V=fe(=)] { 2(EF
2 [|V==f(())) + 2

---

2d
(s-1))(s> 11
with
Eμ = sd
EF
+ + +2,
((82 + 2)
d d-1
(3)
2d
[5{2 -1) d
2d12 352
(s- - () - 1)
Epe
and
Eabs
d - +1) +
12 sd
((52 + 22
-d-1
q
3.2 SZOHT Algorithm
We now present our full algorithm to optimize problem 1 which we name SZOHT (Stochastic Zeroth-Order Hard Thresholding). Each iteration of our algorithm composed two steps: (i) the gradient estimation step, and (ii) the hard thresholding step, where the gradient estimation step is the one described in the section above, and the hard trrrthhheshoddnn is described in more detail in the following paragraph. We give the full formal description of our algorithm in Algorithm
In the hard thresholding step, we only keep the & largest (in magnitude) components of the current iterate xf. This ensures that all our iterates (including the last one) are k-sparse. This hard-thresholding operator has been studied for instance in [36.. and possesses several interesting properties. Firstly, can be seen projection the to ball. Second, importantly, it is not non-expansive, contrary to other operators like the soft-thresholding operator [36). That expansivity plays an important role in the analysis of our algorithm, we will see later.
Compared to previous works, our algorithm can be seen as a variant of Stochastic Hard Thresholding (StolHT from (31) where we replaced the true gradient of fe by the estimator (a)). is also very close to Algorithm 5 from Balasubramanian and Ghadimi (2) (Truncated-2SGiD), with just different zeroth-order gradient estimator: we use a uniform smoothing. random-block estimator, instead of their gaussian smoothing, full support vanilla estimator. This allows to deal with very large dimensionalities, the order of millions, similarly to Cai al. [6]. Furthermore, as described in the Introduction, contrary to Balasubramanian and Ghadimi (), we provide the analysis of our algorithm without any gradient sparsity assumption.
The key challenge arising in our analysis is described in Figure | the bard-thresholding operator being expansive [36], each approximate gradient step must approach the solution enough to stay close to it even after tard-lhresholding. Therefore, it is priori unclear whether the zeroth-order estimate can be accurate enough to guarantee the convergence of SZOHT. Hopefully, as we will see in the next section, we can indeed ensure convergence, as long as we carefully choose the value of q.
(x)
10((())
Quality of ff((x)
(x)
measures the quality of ff(x)
(x
(x)
Non expansive
|| (x- ( f/ (x((T)
7
X
since y >1
< 51|x nd fs(x)) - x||
thresholding
Figure 1: Conflict between the hard-thresholding operator and the zeroth-order estimate.
Convergence analysis
In this section, we provide the convergence analysis of SZOHT, using the assumptions from section 2 and discuss an interesting property of the combination of the zeroth-order gradient estimate and the hard-thresholdin operator, providing positive answer the question from the previous section.
Theorem 1. (Proof in Appendix D.7) Assume that that each fe is (Ly, 8' == max( (n))()2))))+-))) RRSS, and that f is (v., RRSC and o-FGN, with 2k + k < d, with d-k" 2 k p²k" /(1 p²)², with 2 defined as below. Suppose that we run SZOHT with random supports of size $2. q random directions, V. a learning rate of 1l (de++1)13,, and k coordinates kept at each iterations. Then, we have
geometric convergence rate, of the following form, with (1)) denoting the t-iterate of SZOHT:
(1) (t) x²1| S (7p) (0) -x"1+ 6111+ + (1-7 a +
7a
7b
4
1- 7p)
5

---

Algorithm 1: Stochastic Zeroth-Order Hard- Torr-TTheeholdnng (SZOHT)
Initialization: Learning rate 7, maximum number of iterations T, size of the random directions
support 82, number of random directions q, number of coordinates to keep at each iteration k = k()), initial point (0)) with || [x(00) llo k- (typically x0 -),
Output::"
for f I'.. do
Sample & (for instance sample a train sample i)
for i 1, ..., q do
Sample random support S ~~ (4((((())) (((())))
Sample random direction us from the unit sphere supported on S: u, ~ U (5
Compute (f((("=1;;,, P
d (fe(x pai) - f<())) u,;
end
Compute ( E (ie
Compute a' x _ fe
Compute x' ot as the truncation a' with top is entries preserved;
end
a a= a=n ( 2 EFo (d- V8) b= (VEu
with
+ m7 2E
Lig'
V² 0² = ( + 1)L2 and - 1+ (k*/k: + v k2t kk)
-V+It
k- 1k) 12
(4)
and &F, and Su are defined in
Remark 2 (System error). The format of our result similar to the ones in (45) and [3]], in that contains a linear convergence term, and a system error which depends on the expected norm of the gradient x" (through the variable σ). We note that if f has a ks -parse unconstrained minimizer. which could happen in sparse reconstruction, or with overparameterized deep networks (see for instance (32] Assumption (2)]), then we would have [
O, and hence that part of the system error would vanish. In addition to that usual system error, we also have here another system error, which depends on the smoothing radius p. due to the error from the Z0 estimate.
Remark 3 (Generality). we take $2 S 8, the first assumption Theorem) becomes the requirement that fe is (Lg, R)-RSS Therefore, SZOHT as well as the theorem above provides. up to our knowledge, the first algorithm that can work in the usual setting of hard- sonddhheesooddng algorithms (that is. (L.. s)-
RSS and (U,,8) RRCC 31 36)), as well as its convergence rule.
Interplay between hard-thresholding and zeroth-order error Importantly, contrary to previous works in ZO optimization, g must be chosen carefully here, due to our specific setting combining ZO and whnnhhhreeholdig.. Indeed, as described in 36), the hhrd-thrrsholding operator is not non- expansive (contrary to projection onto the & ball) it drive the iterates away from the solution. Therefore, enough descent must be made by the (approximate) gradient step to get close enough to the solution, and is therefore crucial limit errors in gradient estimation. This problem arises with any kind of gradient errors: for instance with SGD errors [31] 47 it is generally dealt with either by ensuring some conditions the function f (T forming bigger batches of samples 47), and/or considering a larger number of components lo kept in hard-thresholding (to make the hard- thresholding less expansive). In our work, similarly to Zhou al. [47) we deal with this problem by relaxing & and sampling more directions u. (which is the ZO equivalent to taking bigger batch-size in SGD). However, there an additional effect that happens in our case, specific to ZO estimation: as described in Proposition] I] the quality of our estimator also depends on k. Therefore, it may be hard to make the algorithm converge only by considering larger higher l means less expansivity (which helps convergence), but worse gradient estimate (which harms convergence). We further illustrate this conflict between the non-expansiveness of thrshhhhesh (quantified by the parameter 7 (36), and the error from the zeroth-order estimate, in Figure Therefore, it is even more crucial to tune precisely our remaining degree of freedom at hand which More precisely, minimal value of q is always necessary to ensure convergence in our setting, contrary to most ZO setting (in which

---

taking even q = 1 can work, as long as other constants like 17 are well chosen, see for instance 23 Corollary 31). The remark below gives some necessary conditions on q to illustrate that fact. Remark (Some necessary condition on 9, proof in [.2). Let k. E No and assume, that l is such that l > p²k* /11-2 (which ensures that p. < 1), and that S d-k' These conditions imply the following necessary (but not sufficient) condition on q:
2
if $2 > q
[8xx 1 1+ 2 2 9k² (+2+2Xd-1)
2h 2 2 (82
82 =
Remark is just a warning that usual rules from ZO do not apply to SZOHT, but it does not say how to choose q to ensure convergence: for that we would need some sufficient conditions on q for Theorem apply. We give such conditions in the next section.
4.1 Weak/non dependence on dimensionality of the query complexity.
In this section, we provide Corollaries [ and following from Theorem I which give an example of q that is sufficient to converge (that is, to obtain "/p < 1 in Theorem and that achieves weak dimensionality dependence in the case of RSS, and complete dimension independence in the case of smoothness.
Corollary 1 (RSS fE. proof in Appendix D.3. Assume that that almost all fe are (Lgr s' max R)S-, and that I is (Va, RRSSC and a-FGN, with s = 2k + k* < d, with d-k" 2 k (86k* 4 - 12k²)k" (with k k= 1.). Suppose that we run SZOHT with random support of size 82, learning rate of 1313, with k coordinates kept at each iterations by the ward-thresholding and
with q 2 2s + 6 Then, we have a geometric convergence rate, of the following form, with (t) denoting the t-iterate of SZOHT:
as"
E|xx(t) x=1| S (1p) (|x x²11+ ( 7a
7
o+
1-
1-
with a, b and 7 are defined in ④ and p = /1 2_ Therefore, the query complexity (QC) to
13nz
ensure that E (+)) x²1| E
ya [-
o 1-10) is (n² _ log(
We now turn to the case where the functions fe are smooth. The key result in that case is that we can have query complexity independent of the dimension d, which is, up to knowledge, the first result of such kind for sparse zeroth-order optimization without assuming any gradient sparsity.
Corollary 2 (Smooth Je. proof in Appendix D.4). Assume that, in addition to the conditions from Corollary I above, almost all f are L-smooth, with d-k" k (86n* 12x² )k* (with v, 2
&.
and take q + and 82 d (that is, no random support sampling). Then, we have a geometric convergence rate, of the following form, with (t)) denoting the t-iterate of SZOHT:
El x=1 5 (Tp)' ||x
x=11+
7/a
σ
7
(-
7p)
Therefore, the QC to ensure that El (1) x= S
+
1-70)
aa
σ
(1
(1-1p) i O log(?)).
Additionally, our convergence rate highlights an interesting connection between the geometry of f (defined by the condition number к L /v.), and the number of random directions that we need to take at each iteration: if the problem is ill-conditioned, that is k is high, then we need a bigger k. This result is standard in the Lp litterature (see for instance 45).. But specifically, in our ZO case, also impacts the query complexity: since the projected gradient is harder to approximate when the dimension io of the projection larger, 9 needs to grow too, resulting in higher query complexity. We believe this is an interesting result for the sparse zeroth-order optimization community: it reveals that the query complexity may in fact depend on some notion intrinsic dimension the problem, related to both the sparsity of the iterates k; and the geometry of the function ʃ for given 82 (through the restricted condition number k), rather than the dimension of the original space d as in previous works like [14].
7

---

Experiments
5.1 Sensitivity analysis
We first conduct sensitivity parameter analysis on toy example, to highlight the importance of the choice of y, as discussed in Section 4 We fix a target sparsity k- 5, choose k 74k*, and consider a sparse quadric function f R - I, with: f(z) aa @ (æ: b)l2 (0 denotes the s-RSC and smooth,
elementwise product). with a; 1 if
s and 0 otherwise (to ensure
with v, = L = 1), and b, = 100d for all i e [d - -0k* and 0 for all d 70k* S ss d (we make such choice in order to have V (x=) "I small enough). We choose 77 as in Theorem ! " (1Ex-1)
with e defined in Proposition D in terms of and d (we take 82 d), / le 4, and present results in Figure 2 for six values of q. We can observe on Figure 2(b) that the smaller the q. the less f(x) can descend. Interestingly, we can also see on Figure (( that for = and 20, ||x(0) x=1l diverges: can indeed compute that py for those q. which explains the divergence, from Theorem
5.2 Baselines
We compare our SZOHT algorithms with state of the zeroth-order algorithms that can deal with sparsity constraints, that appear in Table
1. ZSCG 2 is a Frank- ZO algorithm, for which we consider an & ball constraint.
2. RSPGF
is a proximal ZO algorithm, for which we consider an & penalty.
3. ZORO is proximal 70 algorithm, that makes of sparsity of gradients assumptions, using a sparse reconstruction algorithm at each iteration to reconstruct the gradient from a few measurements. Similarly, as for ZSCG, consider ε penalty.
In all the applications below, we will tune the sparsity of SZOHT, the penalty of RSPGF and ZORO, and the radius of the constraint of ZSCG, such that all algorithms attain a similar converged objective value, for fair comparison.
5.3 Applications
We compare the algorithms above two tasks: sparse asset risk management task from g and an adversarial attack task 9 with sparsity constraint.
Sparse asset risk management We consider the portfolio management task and dataset from {) similarly to 77. We have a given portfolio of assets, with each asset giving an expected return m,, and with a global covariance matrix of the return of assets denoted as C. The cost function we minimize is the portfolio risk: -5
CC ). where æ is a vector where each component æ; denotes
how much is invested in each asset, and we require to minimize it under constraint of minimal
return r: And m.a. We enforce that constraint using the Lagrangian form below. Finally, we add
Σ
sparsity constraint, restrict the investments only k assets. Therefore, we obtain the cost function below:
x² T Cx
min Dim max Di 24
0 o)) s.t. | S k
min HER4
2 + A
Dd 1 23
2
We use three datasets: port3, port4 and port5 from the OR-library [3) of respective dimensions
d 89; 98; 225. We keep r and À the same for the 4 algorithms: r 0.1, X 10 (for port3 and port4); and r = le - 3, = 3
3 for port5. For SZOHT, we set A: = 10, 82 10, q = 10, and (n, n) = (0.015, 0.015) for port4, and (j,, 17) 10. 1) for port5 (μ and are both obtained by grid search over the interval [10-3 10%). For other algorithms, we got the optimal hyper-parameters through grid search. We present results in Figure 3

---

Few pixels adversarial attacks We consider the problem of adversarial attacks with sparse constraint. Our goal minimize ming f(x + 6) such that | - where f the Carlini-Wagner Wagner cost function 9 that is computed from the outputs of pre-trained model on the corresponding dataset. We consider three different datasets for the attacks: MNIST, CIFAR, and Imagenet, of dimension respectively d 784; 3072; 268203. All algorithms are initialized with 5 = 0. We set the hyperparameters of SZOHT as follows: MNIST: & 20, 82 100, q = 100, μl = 0.3, rj = 1; 1000, μ le 3. l 0.01; ImageNet: k 100000, s2 1000, q = 100, μr = 0.01, 77 = 0.015. We present our results Figure All experiments are conducted in the workstation with four NVIDIA RTX A6000 GPUs, and take about one day to run.
CIFAR: k = 60, 82 = 100,
5.4 Results and Discussion
We observe from Figures and that the performance of SZOHT is comparable better than the other algorithms. This can be explained by the fact that SZOHT has a linear convergence, but the query complexity of ZSCG and RSPGF is in (1//T) We can also notice that RSPGF is faster than ZSCG, which is natural since proximal algorithms are faster than Frank- Wolfe algorithms (indeed, in case of possible strong-convexity, vanilla Frank- -olfe algorithms maintain (1/TT) rate [3), when proximal algorithms get linear rate [4 Theorem 10.29]). Finally, it appears that the convergence of ZORO is sometimes slower, particularly the early stage of training, which may come from the fact that ZORO assumes sparse gradients, which is not necessarily verified in real-world use cases like the ones we consider; in those cases where the gradient is sparse, it is possible that the sparse gradient reconstruction step of ZORO does not work well. This motivates even further the need to consider algorithms able to work without those assumptions, such as SZOHT.
Nedoo
f(z)
(a) port3
(b) port4
(c) portS
Figure 3: f(x) vs. # queries (asset management)
11000
(b) |a
(a) MNIST
(b) CIFAR
(c) Imagenet
Figure Sensitivity analysis
Figure 4: f(x) vs. # queries (adversarial attack)
6 Conclusion
In this paper, we proposed a new algorithm, SZOHT, for sparse zeroth-order optimization. We gave its convergence analysis and showed that it is dimension independent in the smooth case, and weak in the RSS case. We further verified experimentally the efficiency of SZOHT in several settings. Moreover, throughout the paper, we showed how the condition number of f as well as the gradient error have an important impact on the convergence of SZOHT. As such, it would be interesting to study whether we can improve the query complexity by regularizing f. by using an adaptive learning rate acceleration methods, or by using recent variance reduction techniques. Finally, it would also interesting to extend this work a broader family of sparse structures, such as low-rank approximations graph sparsity. We leave this for future work.

---

Acknowledgments and Disclosure of Funding
Xiao-Tong Yuan is funded in part by the National Key Research and Development Program of China under Grant No. 2018AAA0100400. and in part by the Natural Science Foundation of China (NSFC) under Grant No.U21B2049, No.61876090 and No.61936005.
References
[1] George Arfken and Hans Weber. Mathematical methods for physicists. American Association of Physics Teachers, 1999.
[2] Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates. In Advances in Neural Information Processing Systems, volume 31, 2018.
[3] John E Beasley. Or-library: distributing test problems by electronic mail. Journal of the operational research society, 1069--00777 1990.
[4] Amir Beck. First-order methods in optimization. SIAM, 2017.
[5] Peter Bühlmann and Sara Van De Geer. Statistics for high sigh-dimenssonal data: methods, theory and applications. Springer Science & Business Media, 2011.
[6] HanQin Cai, Yuchen Lou, Daniel McKenzie, and Wotao Yin. A zeroth-order block coordinate descent algorithm for huge-scale black-box optimization. In International Conference Machine Learning, pages 1193-1203. PMLR, 2021.
[7] HanQin Cai, Daniel McKenzie, Wotao Yin, and Zhenliang Zhang. Zeroth-order regularized optimization (zoro): Approximately sparse gradients and adaptive sampling. SIAM Journal on Optimization, 32(2):687-714, 2022.
[8] T-J Chang, Nigel Meade, John E Beasley, and Yazid M Sharaiha. Heuristics for cardinality constrained portfolio optimisation. Computers & Operations Research, 27(13):1271-330) 2000.
[9] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization 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.
[10] Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm: Zeroth-order adaptive momentum method for black-bor optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
[11] Krzysztof Choromanski, Aldo Pacchiano, Jack Parker-Holdes 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.
[12] Xiang Gao, Bo Jiang, and Shuzhong Zhang. On the coammatiionadaatiive variants of the admm: an iteration complexity perspective. Journal of Scientific Computing, 76(1):327-363, 2018.
[13] Dan Garber and Elad Hazan. Faster rates for the frank-wolfe method over strongly-convex sets.
In International Conference on Machine Learning, pages 541-549. PMLR, 2015.
[14] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155 (1):267-305, 2016.
[15] Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, and Qiuyi Zhang Gradientless descent: High-dimensional zeroth-order optimization. International Conference on Learning Representattons, 2019.
10

---

[16] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. Proceedings of the 36th International Conference Machine Learning, volume 97, pages 5200-5209. PMLR, 2019.
[17] Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m-estimation. In Advances in Neural Information Processing Systems, volume 27, 2014.
[18] Kevin G Jamieson, Robert Nowak, and Ben Recht. Query complexity of Serivative-free optimization. In Advances in Neural Information Processing Systems, volume 25, 2012.
[19] Evgeny S Levitin and Boris T Polyak. Constrained minimization methods. USSR Computational mathematics and mathematical physics, 6(5): 1966.
[20] Xingguo Li, Raman Arora, Han Liu, Jarvis Haupt, and Tuo Zhao. Nonconvex sparse learning via stochastic optimization with progressive variance reduction. arXiv preprint 17Xi::660.00271,, 2016.
[21] Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, and Ji Liu. A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth- order to first- order. Advances in Neural Information Processing Systems, 29, 2016.
[22] Hongcheng Liu and Yu Yang. A dimensioon-nssensitve algorithm for stochastic zeroth-order optimization. arXiv preprini arXiv:2 1283, 2021.
[23] Sijia Liu, Jie Chen, Pun-Yu Chen, and Alfred Hero. Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2018.
[24] Sijia Liu, Bhavya Kailkhura, Pun-Yu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth-order stochastic variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 31, 2018.
[25] Sijia Liu, Pin-Yu Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred O Hero III, and Pramod K Varshney. A primer on zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):43-54, 2020.
[26] Po-Ling Loh and Martin Wainwright. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. Advances Neural Information Processing Systems, 26, 2013.
[27] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies competitive for reinforcement learning. In Advances Neural Information Processing Systems, volume 31, 2018.
[28] Sahand Negahban, Bin Yu, Martin J Wainwright, and Pradeep Ravikumar. A unified framework for figh-diimnsional analysis of m-estimators with decomposable regularizers. Advances in neural information processing systems, 22, 2009.
[29] Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical science, 27(4)553--557, 2012.
[30] Yurii Nesterov and Vladimir Spokoiny, Random gradient-frre minimization of convex functions. Foundations of Computational Mathematics, 17(2)5277556, 2017.
[31] 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.
[32] Alexandra Peste, Eugenia lofinova, Adrian Vladu, and Dan Alistarh. Ac/de: Alternating compressed/decoppessed training of deep neural networks. Advances in Neural Information Processing Systems, 34, 2021.

---

[33] Garvesh Raskutti, Martin Wainwright, and Bin Yu. Minimax rates of estimation for high- dimensional linear regression over E bpballs. IEEE transactions on information theory, 57(10): 6976-6994 2011.
[34] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and llya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv: 70000000006... 2017.
[35] Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1703-1113, 2017.
[36] Jie Shen and Ping Li. A tight bound of hard thresholding. The Journal of Machine Learning Research, 18(1):7550-7611, 2017.
[37] Artem Sokolov, Julian Hitschler, Mayumi Ohta, and Stefan Riezler. Sparse stochastic zeroth-order optimization with an application to bandit structured prediction. arXiv preprint a806: 04458, 2018.
[38] Stanislav Sykora. Surface integrals over n-dimensional spheres. Stan's 's Library, (Volume I), May 2005. doi: 10.3247/sl m
[39] Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288, 1996.
[40] Chun-Chen Tu, Paishun Ting, Pun-Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-basee zeroth order optimization method for attacking black-box neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 742-749, 2019.
[41] Sara A Van de Geer. High-dimensional generalized linear models and the lasso. The Annals of Statistics, 36(2):614-645 2008.
[42] Martin J Wainwright, Michael Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1(1-2):1-305, 2008.
[43] Christian Walck et al. Hand-book on statistical distributions for experimentalists. University of Stockholm, 10:96-01, 2007.
[44] Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-orde optimization in high dimensions. In International Conference on Artificial Intelligence and Statistics, pages 1356-1365. PMLR, 2018.
[45] Xiao-Tong Yuan, Ping Li, and Tong Zhang. Gradient hard thresholding pursuit. Journal of Machine Learning Research, 18(1):602766069 2017.
[46] Xiaotong Yuan and Ping Li. Stability and risk bounds of iterative hard thresholding. In International Conference on Artificial Intelligence and Statistics, pages 1702-1710. PMLR, 2021.
[47] Pan Zhou, Xiaotong Yuan, and Jiashi Feng. Efficient stochastic gradient hard thresholding. In Advances in Neural Information Processing Systems, volume 31, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In the conclusion we mention
some possible ways to improve upon our work
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
12

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Our code will be included the supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they
chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes] The code will be submitted in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "iSxtQI4Cm0-", "reviewer": "Reviewer_baZg", "summary": "This work considers the problem of stochastic optimization in the presence of an L0 ball constraint (i.e. at most k components of the minimizer can be nonzero). This is essentially stochastic optimization in a setting where a sparse solution is sought. In particular, the authors consider this problem in a zeroth-order (ZO) optimization situation where (stochastic) gradients are not available, useful for black-box adversarial attacks and reinforcement learning (for example).\n\nSpecifically, the paper proposes to use iterative hard thresholding, a standard method for L0-constrained problems, but with stochastic gradients estimated via gradient smoothing (a form of randomized finite differencing). The gradient smoothing is specifically designed to apply sparse perturbations to the current iterate, unlike standard smoothing. \n\nThey prove a linear convergence rate for their algorithm to a neighborhood of a minimizer under some restricted versions of strong convexity and L-smoothness. The neighborhood of convergence depends on both the variance of the stochastic gradients, and the smoothing parameter used in the gradient estimator. Under full L-smoothness of the objective, they prove a fully dimension-independent convergence rate, which improves on existing sparse ZO optimization based on L1 regularization. A key restriction of this technique is that the convergence theory requires the number of gradient smoothing estimates to be sufficiently large (to ensure the estimated stochastic gradient is sufficiently close to the true stochastic gradient). \n\nThe authors provide numerical experiments for sparse portfolio optimization and adversarial example generation, showing that their proposed method outperforms existing sparse ZO optimization methods.", "questions": "1. In the gradient estimator eq (2), is it correct that each u_i has a different support set? In that case, the gradient estimator could have up to q*s_2 nonzero entries. Is this a concern from a computational effort point of view?\n\n2. Throughout Section 4, what is k*? Is this just an upper bound on ||x_0||_0 (in which case if x_0=0 then any k* is acceptable), or something else? \n\n3. The conditions of Theorem 1, in particular $s \\leq d$ implies that we must have $k\\leq d/2$. Does this cause any conflict with the other assumption $k \\geq k^* \\rho^2 / (1-\\rho^2)^2$? Any restrictions on the problem constant $k$ should be explicitly given (even though $k\\leq d/2$ is not a problematic requirement).\n\n4. It is mentioned in line 219 that Lemma 1 gives conditions for which $\\rho \\gamma < 1$. However, the lemma's statement does not appear to include this. What specifically does $q \\geq q_{\\min}$ imply? In particular, does it imply either/both of $k \\geq k^* \\rho^2 / (1-\\rho^2)^2$ or $\\rho\\gamma<1$?\n\n5. Figure 2b seems to show that there is essentially no reduction of $\\|x-x^*\\|$ for any value of $q$. Does this mean your choice of problem makes the non-decaying ($\\sigma$ and $\\mu$) terms in Theorem 1 too large to show useful results in this regard?", "limitations": "The main limitations are related to problem assumptions and requirements on $q$ and $k$. These are reasonably well described, noting my feedback above. There is no concern about negative societal impact from this work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To my knowledge, this is the first attempt to combine hard thresholding with ZO gradient estimators (although it has already been applied to stochastic gradients). The resulting algorithm is simple and appears to perform well in practice. I note that in practice both the learning rate and the smoothing parameter have to be tuned, which is expensive, but a reasonable cost in this setting. The convergence theory is interesting and the implications for the gradient smoothing accuracy will likely affect any future L0-constrained ZO algorithm development. \n\nOverall I find this an interesting work. The quality of prose is sufficiently high in most places. \n\nMy main concern is the discussion around the choice of $q$ (particularly Lemma 1) in Section 4. My understanding of Lemma 1 is that first a suitable $q \\geq q_{\\min}$ is chosen, and that then defines a valid range of $k$. This seems to be the wrong way around - usually we would have a $k$ specified by the problem, and then choose how to construct the ZO gradient estimators with a corresponding restriction on $q$ (depending on $k$). It also appears that the authors require, if the chosen $k$ is too small (although exactly what this means is unclear as per my concern around Lemma 1) that a larger $k$ is chosen. That is, the actual L0 constraint must be changed. This is quite unusual, in that an optimization algorithm requires the solution of a *different* problem than originally specified. \n\nMinor comments:\n- What is footnote 4 in Table 1 (for SZOHT in the second-last row)?\n- The variable $q$ is mentioned several times in the introduction, but not defined until later.\n- I find Figure 1 extremely unclear and don't think it contributes to the text (lines 174-178). I recommend it be removed.\n- Line 298, \"proximal algorithms are faster than Frank-Wolfe algorithms\". I have not seen this conclusion before (as a non-expert in these methods) - do you have a citation for this?\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZYfQfUxFl_b", "reviewer": "Reviewer_skyg", "summary": "This paper considers the $\\ell_0$ constrained stochastic optimization problem with zeroth-order oracles only. They proposed a stochastic zeroth-order hard-thresholding algorithm, making use of a novel random support sampling. They provide the convergence guarantees of SZOHT under standard assumptions, and the query complexity of SZOHT has weak/no dependence under different settings.", "questions": "See \"Strengths and Weaknesses\"", "limitations": "See \"Strengths and Weaknesses\"", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper proposed a new algorithm SZOHT and show that the oracle complexity is dimension independent under some condition without additional gradient sparsity assumption. The ideas and the proposed algorithm are easy to follow. The paper is well organized. The experiments show improvements over previous work. In general, the paper is good.\n\nI have a few comments/questions:\n\nMajor Comments:\n1. $k$ and $k^*$: I have two questions about $k^*$ and $k$. Based on my understanding, $k^*$ is the actual target sparsity, while $k$ is just a parameter in the algorithm, and each iterate of algorithm maintains $k$-sparsity instead of $k^*$-sparsity. That means each iterate of the algorithm does NOT maintain primal feasibility, is that correct? If that is the case, is there any polishing steps you can do to refine the solution so that it has exact $k^*$ nonzeros? The second question about this is in the algorithm, it says $k=\\mathcal{O}(\\kappa^4k^*)$, and also in Remark 4, the authors mention that $q$ should be taken so that $k\\leq d$. But even with $q=\\infty$, $\\epsilon_F=2$, there are still chances that $k=\\mathcal{O}(\\kappa^4k^*)$ will be always greater than $d$, which means the algorithm has limitation on actual target sparsity $k^*$?\n2. $\\mu$: In the convergence analysis, there is only a linear term in $\\mu$ while neither other constants or nor other terms depend on $\\mu$. This is a bit counter-intuitive, because that means $\\mu$ can be taken arbitrarily small to reduce the error term? Is there any theory to provide guidelines on how to choose $\\mu$? What did you choose for $\\mu$ in the numerical experiments?\n3. Condition number $\\kappa$ and $s_2$: in theory, the convergence guarantee and oracle complexity bound depend heavily upon the condition number $\\kappa$, which is unknown or hard to compute based on its definition. The convergence guarantee may not hold if the learning rate $\\eta$ and/or $q$ are chosen arbitrarily. In practice, one may need to tune heavily on these hyperparams, which the authors did for their experiments. I am wondering if there is any way you can estimate these parameters or any way to avoid large grid of hyperparam tuning? Also there any theory to provide guidelines on how to choose $s_2$? Because $s_2$ might also affect the condition number?\n\nMinor Comments\n1. In line 75/94, $q$ is not introduced yet, so it is better to give some descriptions on $q$.\n2. In Proposition 1 Theorem 1, Corollary 1 and Corollary 2, the constants are hard to locate. Probably it’s better to have equation number and refer to these equations later on to remind people what these constants are in the theory.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "GaExOJqdUZ0", "reviewer": "Reviewer_bBM4", "summary": "This paper describes a zeroth-order version of the hard-thresholding algorithm. Interestingly, the convergence rate (up to system errors) is dimension-independent in the case of smooth functions and full support sampling for the random directions. The paper also provides convergence results in the more general case of restricted smoothness and restricted support for the sampling of random directions. It also discusses an interesting trade-off that arises between the error of the zeroth-order estimate, and the expansivity of the hard-thresholding operator, that results into a minimal value for the number of random directions q. Finally, the authors demonstrate the utility of their method with encouraging  experimental results on synthetic datasets such as a quadratic function, and real-life datasets such as asset management and black-box adversarial attacks.", "questions": "I believe one aspect that may deserve further discussion is about the system error in Theorem 1, that depends on the norm of the gradient at optimum ||nabla f(x*)||. If this term is large, the upper bound for the convergence rate might become large too. However, this term seems to appear also in other works on hard-thresholding like [2], so I guess it is not really an issue of the work itself, more of an issue intrinsic to the hard-thresholding method and l0 constraint. But I think it might be interesting to elaborate on how large this term can get in practice, and also in which settings it can be small (for instance, it may be interesting to add references on compressed sensing, in which the original parameter vector is assumed sparse, or to related assumptions like assumption (2) in [3], in which it is stated that \"the existence of very sparse minimizers is a known property in over-parametrized DNNs\").", "limitations": "Since this algorithm describes a general method for optimization, I don't believe there is any direct negative societal impact.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality:\nThe main difference compared to previous work is in tackling both zeroth-order and l0 optimization, which has not been done before (except by the work of [1], but they make stronger assumptions (sparsity of gradients)). The proof for the dimension independence/insensitiveness of zeroth-order hard-thresholding, a consequence of the bounds on the error of the ZO gradient, is novel, and uses interesting results about the surface integration on a sphere, as well as involved combinatorics computations to generalize them to the random support technique. I think it is an interesting contribution to the litterature on ZO optimization. The discussion about the minimal value for q is also very interesting and novel. \n\n## Quality:\nThe authors provide detailed self-contained proofs for the main claims in the appendix. They also provide some code to run SZOHT on the toy experiments, as well as an asset management problem and an adversarial attack problem.\n\n## Clarity:\nThe main results and theorems are discussed in details. Figure 1 convey very well the main message regarding the conflict between expansivity and gradient error.\nI believe there are a few typos/missing notations, that could easily be addressed:\n- In table 1, note 4 does not appear\n- In table 1, I think FO was not defined (though I guess it means \"First-order\")\n- In section 5.1 sensitivity analysis, I think it should be an elementwise product a  * (x - b), not a dot product (otherwise the squared norm would be just a squared number)\n \n## Significance :\nAs zeroth-order optimization is known to suffer from the curse of dimensionality, as described in the introduction of the paper, dimension-insensitive results like the one from this paper are very interesting. In addition, that paper manages to achieve such results with only mild assumptions (namely, RSC and RSS, and without any gradient sparsity assumption). The experiments are extensive, and ran on real-life datasets like adversarial attacks which shows the method also works well in large scale practical machine learning problems.\n\n\n# References\n[1]   \"Zeroth-order (non)-convex stochastic optimization via conditional gradient and gradient updates\"\n  Balasubramanian, Krishnakumar and Ghadimi, Saeed\n  Proceedings of the 32nd International Conference on Neural Information Processing Systems 2018\n\n\n[2] \"Linear convergence of stochastic iterative greedy algorithms with sparse constraints\",\n  Nguyen, Nam and Needell, Deanna and Woolf, Tina\n  IEEE Transactions on Information Theory, 2017,\n\n[3] Ac/dc: Alternating compressed/decompressed training of deep neural networks},\n  Peste, Alexandra and Iofinova, Eugenia and Vladu, Adrian and Alistarh, Dan},\n  Advances in Neural Information Processing Systems\n  2021", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept