Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
Authors: Nikita Kornilov
Ohad Shamir
Aleksandr Lobanov
Darina Dvinskikh
Alexander Gasnikov
Innokentiy Andreevich Shibaev
Eduard Gorbunov
Samuel Horváth
Venue: NeurIPS 2023 poster (2023)
Keywords: stochastic optimization
gradient-free optimization
zero-order oracle
gradient clipping
infinite variance
TL;DR: We propose a gradient-free method built upon an accelerated gradient method (Sadiev et al., 2023) with batching technique which is optimal with respect to iteration complexity and the maximal noise level with infinite variance.

Abstract: In this paper, we consider non-smooth stochastic convex optimization with two function evaluations per round under infinite noise variance. In the classical setting when noise has finite variance, an optimal algorithm, built upon the batched accelerated gradient method, was proposed in (Gasnikov et. al., 2022). This optimality is defined in terms of iteration and oracle complexity, as well as the maximal admissible level of adversarial noise. However, the assumption of finite variance is burdensome and it might not hold in many practical scenarios. To address this, we demonstrate how to adapt a refined clipped version of the accelerated gradient (Stochastic Similar Triangles) method from (Sadiev et al., 2023) for a two-point zero-order oracle. This adaptation entails extending the batching technique to accommodate infinite variance — a non-trivial task that stands as a distinct contribution of this paper.

Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variance
Nikita Kornilov
Ohad Shamir Weizmann Institute of Science ohad. Chamir@weizmane ac il
Aleksandr Lobanov MIPT, ISP RAS
MIPT, SkolTech kornilov. www.nnnstechhhccocmccmmm kormilov..m@@aysseccc.co edu
lobanov.c waaaavv.vemipt.rrr
Darina Dvinskikh HSE University, ISP RAS
Alexander Gasnikov
Innokentiy Shibaev MIPT.
MIPT,
ISP RAS, SkolTech
ITTP RAS
dmdvinskikhhhse.cr ru
gasnikov@yandex.rg
hamokantiy.ahbaaaee@hsstttc.
Eduard Gorbunov
Samuel Horváth MBZUAI
MBZUAI
eduard. gonaroobgrbbu ac .e
samuel. samuel.horvatael www..hoottttmbbuui....o ac ae
Abstract
this paper, we consider non-smooth stochastic convex optimization with two function evaluations per round under infinite noise variance. In the classical setting when noise has finite variance, an optimal algorithm, built upon the batched accelerated gradient method, terms of iteration and oracle complexity, as well as the maximal admissible level of adversarial noise. However, the assumption of finite variance is burdensome and it might not hold in many practical scenarios. To address this, we demonstrate how adapt a refined clipped version of the accelerated gradient (Stochastic Similar Triangles) method from [35] for a two-point zero-order oracle. This adaptation entails extending the batching technique accommodate infinite variance a non-trivial task that stands as a distinct contribution of this paper.
proposed in [17]. This optimality is defined in
Introduction
In this paper, we consider stochastic non-smooth convex optimization problem
min rERa { f(x) Re-D (f(,,)))
(1)
where {Ix is MapSS-Lipschitz continuous in x w.r.t the Euclidean norm, and the expectation Eg-D [)] is with respect random variable with unknown distribution D. The optimization is performed only by accessing two function evaluations per round rather than sub-gradients, i.e., for any pair of points v; Rdd oracle returns [ar {) and f(y, E) with the same Ç. The primary motivation for this gradient-free oracle arises from different applications where calculating gradients computationally infeasible even impossible. For instance, in medicine, biology, and physics, the objective function can only be computed through numerical simulation or as the result of real experiment, i.c., automatic differentiation cannot be employed calculate function derivatives. Usually, black-box function we are optimizing is affected by stochastic or computational noise. This noise can arise naturally from modeling randomness within a simulation or by computer discretization.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In classical setting, this noise has light tails. However, usually in black-box optimization, we know nothing about the function, only its values at the requested points are availableccomputable, so light tails assumption may be violated. In this case, gradient-free algorithms may diverge. We aim to develop an algorithm that is robust even to heavy-tailed noise, i.e., noise with infinite variance. In theory, one can consider heavy-tailed noise to simulate situations where noticeable outliers may occur (even the nature of these outliers is non-stochastic). Therefore we relax classical finite variance assumption and consider less burdensome assumption of finite a-th moment, where E (1.
In machine learning, interest in gradient-free methods is mainly driven by the bandit optimization problem [14, 2, 51, where a learner engages in a game with an adversary: the learner selects point æ, and the adversary chooses a point Ç. The learner's 's goal is to minimize the average regret based solely on observations of function values (losses) fz, E). As feedback, at each round, the learner receives losses at two points. This corresponds to a zero-order oracle in stochastic convex optimization with two function evaluations per round. The vast majority of researches assume aub-Gaasssinn distribution of rewards. However, in some practical cases (e.g., in finance [333) reward distribution has heavy-tails or can be adversarial. For the heavy-tailed bandit optimization, we refer to [9].
Two-point gradient-free optimization for non-smooth (strongly) convex objective is a well-researched area. Numerous algorithms have been proposed which are optimal with respect to two criteria: oracle and iteration complexity. For a detailed overview, see the recent survey [15] and the references therein. Optimal algorithms. in terms of oracle call complexity, are presented in [10, 36, 3]. The distinction between the number of successive iterations (which cannot be executed in parallel) and the number of oracle calls was initiated with the lower bound obtained in [6]. It culminated with the optimal results from [17], which provides an algorithm which optimal in both criteria. Specifically, the algorithm produces â, an c-solution of (1), such that we can guarantee [[](a]] min f(x) after =ERd
d successive iterations, de oracle calls (number of f(x {) calculations).
The convergence guarantee for this optimal algorithm from [17] was established in the classical setting of light-tailed noise, i.e., when noise has finite variance: Egg (M) < co. However, in many modern learning problems the variance might not be finite, leading the aforementioned algorithms to potentially diverge. Indeed, heavy-tailed noise is prevalent in contemporary applications of statistics and deep learning. For example, heavy-tailed behavior can be observed in training attention models [41] and convolutional neural networks [37, 20J. Consequently, our goal is to develop an optimal algorithm whose convergence is not hampered by this restrictive assumption. To the best of our knowledge, no existing literature on gradient-free optimization allows for (x) to be infinite. Furthermore, convergence results for all these gradient-free free methods were provided in expectation, that is, without (non-trivial) high-pno gigh-prbbability bounds. Although the authors of [17] mentioned (without proof) that their results can be formulated in high probability using [19], this aspect notably affects the oracle calls complexity bound and complicates the analysis.
common technique to relax finite variance assumption is gradient clipping [31]. Starting from the work of [26] (see also [8, 19]), there has been increased interest in algorithms employing gradient clipping to achieve high-probability convergence guarantees for stochastic optimization problems with heavy-tailed noise. Particularly, in just the last two years there have been proposed
an optimal algorithm with a general proximal setup for non-smooth stochastic convex optimization problems with infinite variance [39] that converges in expectation (also referenced in [27]).
an optimal adaptive algorithm with general proximal setup for non-smooth online stochastic convex optimization problems with infinite variance [42] that converges with high probability,
optimal algorithms using the Euclidean proximal setup for both smooth and non-smooth stochastic convex optimization problems and variational inequalities with infinite variance [35, 30, 29] that converge with high probability,
an optimal variance-adaptive algorithm with the Euclidean proximal setup for non-smooth stochastic (strongly) convex optimization problems with infinite variance [24] that converges with high probability.
None of these papers discuss a gradient-free oracle. Moreover, they do not incorporate acceleration (given the mon-smooth nature of the problems) with the exception of [35]. Acceleration is a crucial
2

---

component to achieving optimal bounds on the number of successive iterations. However, the approach in [35] presumes smoothness and does not utilize batching. To apply the convergence results from [35] to our problem, we need to adjust our problem formulation to be smooth. This achieved by using the Smoothing technique [27, 36, 17J. the work [22] authors proposed an algorithm based on Smoothing technique and non-accelerated Stochastic Mirror Descent with clipping. However, this work also does not support acceleration, minimization on the whole space and batching. Adapting the technique from [35] to incorporate batching necessitates a substantial generalization. We regard this aspect of our work as being of primary interest.
Heavy-tailed noise can also be handled without explicit gradient clipping, e.g., by using Stochastic Mirror Descent algorithm with a particular class of uniformly convex mirror maps [39]. However, the convergence guarantee for this algorithm is given in expectation. Moreover, applying batching and acceleration is non-trivial task. Without this, we are not able to get the optimal method in terms of the number of iterations and not only in terms of oracle complexity. There are also some studies on the alternatives to gradient clipping [21] but the results for these alternatives are given in expectation and are weaker than the state-of-the-ar results for the methods with clipping. This is another reason why we have chosen gradient clipping to handle the heavy-tailed noise.
1.1 Contributions
We generalize the optimal result from [17] to accommodate weaker assumption that allows the noise to exhibit heavy tails. Instead of the classical assumption of finite variance, we require the boundedness of the a-moment: there exists a E (1, 2] such that Eg [M2){) < c0. Notably, when < 2, this assumption is less restrictive than the assumption of finite variance and thus it has garnered considerable interest recently, see [41, 35, 29] and the references therein. Under this assumption we prove that for convex f. an e-solution can be found with high probability after
dis-!
successive iterations,
(vd/E)
oracle calls,
and for ju-strongly convex f, the e-solution can found with high probability after
~ dd (NE) successive iterations,
(d/(p)) म. oracle calls.
In both instances, the number of oracle calls is optimal in terms of e-dependency within the non-smooth setting [27, 39]. For first-order optimization under heavy-tailed noise, the optimal e-dependency remains consistent, as shown in [35, Table 1].
In what follows, we highlight the following several important aspects of our results
High--trbabillty guarantees. We provide upper- upper-bounds on the number of iterations/oracle calls needed to find a point é such that (() mingeR" f(x) S e with probability at least 1 1 B. The derived bounds have poly-logarithmic dependence on 1/8. To the best of our knowledge, there are no analogous high-probabillty results, even for noise with bounded variance.
Generality of the setup. Our results are derived under the assumption that gradient-free oracle returns values of stochastic realizations f(x, x) subject to (potentially adversarial) bounded noise. We further provide upper bounds for the magnitude of this noise, contingent upon the target accuracy and confidence level |.. Notably, our assumptions about the objective and noise confined to a compact subset of gd. This approach, which differs from standard ones in derivative- free optimization, allows us encompass wide range of problems. This approach differs from standard ones in derivative-fres optimization
Batching without bounded variance, To establish the aforementioned upper bounds, we obtain the following: given XI...., Xn as independent random vectors in Rdd where E[X.] Rd and E; - xil < のºh for some a 2 and a E (1, 2]. then
a
E
X;
2
Ba-1
(2)
2
3

---

When = 2, this result aligns with the conventional case of bounded variance (accounting for numerical factor 2). Unlike existing findings, such as [40, Lemma where a 2. the relation (2) does not exhibit a dependency the dimension d. Moreover, (2) offers theoretical basis to highlight the benefits of hini-batchinn, applicable to methods highlighted in this paper as well as first-order methods presented in [35, 29].
Dependency on As far as we are aware, an open question remains: is the bound (vdje
optimal regarding its dependence on d? For smooth stochastic convex optimization problems using a (d+ 1)-possss stochastic zeroth-order oracle, the answer is negative. The optimal bound is proportional to de -.. Consequently, for a E (1,2), our results are intriguing because the dependence on d in our bound differs from known results in the classical case where a = 2.
1.2 Paper organization
The paper is organized as follows. In Section 2, we give some preliminaries, such as smoothing technique and gradient estimation, that are workhorse of our algorithms. Section the main section presenting two novel gradient-free algorithms along with their convergence results in high probability. These algorithms solve non-smooth stochastic optimization under heavy-tailed noise, and they will be reffered to as ZO-clipped-SST and respectively). In Section we extend our results to gradient-free oracle corrupted by additive deterministic adversarial noise. In Section 5, we describe the main ideas behind the proof and emphasize key lemmas. In Section 6, we provide numerical experiments on the synthetic task that demonstrate the robustness of the proposed algorithms towards heavy-tailed noise.
and R-ZO-clipped-SSS -SSM (see Algorithms 1
2 Preliminaries
Assumptions on a subset. Although we consider an unconstrained optimization problem, our analysis does not require any assumptions to hold on the entire space. For our purposes, it is sufficient to introduce all assumptions only on some convex set Q E IRd since we prove that the considered methods do not leave some ball around the solution or some level-set of the objective function with high probability. This allows us to consider fairly large classes of problems.
Assumption (Strong convexity) There exist a convex set Q Rdd and p 2 such that function fæ, E) is u-strongly convex on Q for any fixed &, i.e.
f(A21 (1 -)x2)) s Af(x1) + + (1-))))111))))) jur(1 A)[[z1 x2
for all 01,02 E QQA E [0.
This assumption implies that f(r is μ-strongly convex as well.
For small constant r 0, let us define an expansion of set Q namely Q, Q Bg. where stands for Minkowski addition. Using this expansion we make the following assumption.
Assumption (Lipschitz continuity and boundedness of a-moment) There exist a comvex set is -iipschit continuous w.E.t. the Euclidean Q C Rd and 7 > such that function fxx,g) {) norm on Qy. i.e., f.e. for all 21, 32 E QT
1f( f(z2, 3) Mc(E)l x2ll2-
Moreover, there exist a E [1 and M2 > 0 such that [E{[M((E))) < Mg.
If 2, we say that noise heavy-tailed. When a the above assumption recovers the standard uniformly bounded variance assumption.
Lemma Assumption implies that fxx is Mæ-Lipschitz on Q.
Randomized smoothing. The main scheme that allows us to develop methods for non-smooth convex problems is randomized smoothing [13, 17, 27, 28, 38) of non-
gradient-
smooth function f(x, E). The smooth approximation to non-smooth function f(z, E) is defined as

---

(+(x) del En,gf((x ru, E)]:
where u U(B)) is a random vector uniformly distributed on the Fuclidean unit ball By del (ar Rd | < 1). In this approximation, dition to stochastic variable ç.
type of randomization appears in ad-
The next lemma gives estimates for the quality of this approximation. In contrast to f(z). function (x) is smooth and has several useful properties.
Lemma [17, Theorem 2.1.] Let there exist subset Q C IRd and т > 0 such that Assumptions 1 and 2 hold Q,. Then,
1. Function (x) is convex, Lipschitz with constant M2 on Q, and satisfies
sup (f-(x) - [(x)] S M2.. zeQ
2. Function f+(x) is differentiable on Q with the following gradient
d - Te)e
(x(()) - Eg
where (S$) is random vector uniformly distributed unit Eucledian sphere S def
fx e Rd || 1}.
3. Function fx( is L-smooth with L = V.Ma/r on Q.
Our algorithms will aim at minimizing the smooth approximation f- (x)). Given Lemma 2, the output of the algorithm will also be good approximate minimizer of f(z) when is sufficiently small.
Gradient estimation. Our algorithms will based on randomized gradient estimate, which will then be used in first order algorithm. Following [36], the gradient can be estimated by the following vector:
o(x,E,e) = 2r
(f(x + re, f(x te, e),
where т > 0 and ~~ U. We also use batching technique in order to allow parallel calculation of gradient estimation and acceleration. Let B be a batch size, we sample {c and { independently, then
B
(x.
(2) (e)) = 2BT - re, Ei) - f(x - re,, E.)ee
(5)
The next lemma states that (x, (E, {e}} from (5) is an unbiased estimate of the gradient of fr (x) (3). Moreover, under heavy-tailed noise (Assumption with bounded a-moment g (zz (E)(e)) has also bounded a-moment.
Lemma 3 Under Assumptions I and 2, it holds
Re.lg((o,E.el = BEE) la (xx (E). (e}) = (x))
and
VdM2
Eg,ell9(Z,E,ee) - -, 5 def
2
a
E (19 (x, (5).
E(s) 19 (E), [e))
(6)
11-1
5

---

Main Results
In this section, present two zrde- algorithms. which will refer to Z0-clipped- SSTM and R-ZO-Clipped-SSTM to solve problem (1) under heavy-tailed noise assumption. To deal with heavy-tailed noise, we clipping technique which clips heavy tails. Let À > 0 be clipping constant and E Rd, then clipping operator clip is defined as
T911z min (19112,)) A), 0,
7 0,
clip (g. A)
g =
We apply clipping operator for batched gradient estimate 90 (<). {e)) from (5) and then feed it into first-order Clipped Stochastic Similar Triangles Method (clipped-SS) -STMM) from [18]. We will refer zero-order versions of clipped-SSTI as ZO-clipped-SSTT and R-20-ClippedSSSTM for the convex case and strongly convex case respectively.
3.1
Convex case
Let us suppose that Assumption is satisfied with = O.
Algorithm Z0-dlipped-SSTM (z", K, (A=
Input: starting point z.,, number of iterations batch size B, stepsize > smoothing parameter
7, clipping levels {
K
k=
Set I. VdMa/T, Ag ag = 0, y0 20 r
2: for k ...... K 1
3: Set 0 = k+2/2aL,
ARt1 Au -.k-1
4: akt1 Auy +0R41*"
A+11
5: Sample ( D and [c _ S independently.
6:
Compute gradient estimation (xttt (ck) }. {e*)) as defined in (5). Compute clipped ğR+1 clip (g (z {5*), fer fe* })) as defined in (7).
7:
8:
g 2² 04 19141.
k+1 Aay 10u112 1+1
9:
y
Ae11
10: end for
Output: gx
Theorem (Convergence of ZO-clipped-SSTT SSTM) Let Assumptions 1 and hold with p 0 and Q Rdd. Let || x2 < R², where x. is starting point and x" is an optimal solution to (1). Then for the output y K of Z0-clipeed-SSTTM run with batchsize B, = In 4K/3 2
O(max A2, VdM,K (a-1), A (-=") |LRB _==")) }). s/4M, and d +((//tau1))), we can
guarantee f()*) f(x²) I with probability at least 1 - 3 ffrr any B E (0, 1)) after
M2 VaR
VdM2R
-
K ==Ō max
(8)
E
successive iterations and K B oracle calls. Moreover, with probability at least - 3 the iterates of K+1
TO-cliped--SSTM remain in the ball B2R(x"), i.e., { {y*
Jk=0
Jk {=*]
Jk=0 C B²x(**).
Here and below notation δ means an upper bound on the growth rate hiding logarithms. The first term in bound (8) is optimal for the deterministic case for non-smooth problem (see [6]) and the second term in bound (8) is optimal in e for E (1, 2] and zero-point oracle (see [27]).
We notice that increasing the batch size B to reduce the number of successive iterations makes sense only as long as the first term of (8) lower than the second one, i.e. there exists optimal value of batchsize
VdMyR
B

---

3.2 Strongly-convex case
Now we suppose that Assumption satisfied with μ 0. For this case we employ ZO-clipped- SSTM with restarts technique. We will call this algorithm as R-ZO-clipped-SSTMG (see Algorithm 2). At each round R-20-clipped-SSTM call ZO-clipped-SSt SSTM with starting point f', which the output from the previous round, and for K, iterations.
Algorithm 2 R-ZO clipped-SSTT
Input: starting point x², number of restarts N, number of steps {K,) batchsizes {B:) stepsizes {at smoothing parameters {Te hre) clipping levels {>x k=0 .... {A Tk=0
Ki- NNNKK KN
1: 0 _²
2: for 1, ..... do
3: 4' Z0- XO-clipee--SSTM (H*11,K K1, B1, (AR)
4: end for
Output: &.
Let Assumptions 1, 2 hold with > 0 and 1² 22= < R², where x is starting point and x" is the optimal solution to (1). Let also N [log2((?²) /2=)] be the number of restarts. Let at each stage t = 1,..,,N of R-ZO- 5//MM, Lt M2 7,, K.
Theorem (Convergence of 1--ZO-lipped-SSS
Q = -... Let ||
clipped-SSTM, SSTM, Z0- ZO-clipped-SSS -SSM is with batchsize Bú, Te a11
((max
(v L s/er, (a (aRi-1/es) (2.-1/e) /B,)). a, ((max[1, /L.Re)) and X (1/ait)) where Ri-1 2 R, p 1/4, In 3/K 1, 3 (0, 1]. Then to guarantee f(NN) f(x*) S E with probability at least - 3, R- SSTM requires
M3va
dd3
2[a
δ max
MIE
HiE
oracle calls. Moreover, with probability at least 1 the iterates of R-ZOOclipped-SSSTT SSTM stage t t= 1= stay in the ball (2²".
The obtained complexity bound (see the proof in Appendix C.2) is the first optimal (up to logarithms) high-probabiility complexity bound under Assumption for the smooth strongly convex problems. Indeed, the first term cannot be improved in view of the deterministic lower bound [27], and the second term is optimal [41].
4 Setting with Adversarial Noise
Often, box access of f(x, {) are affected by some deterministic noise 5(x). Thus, now we suppose that a zero-order oracle instead of objective values (x. {) returns its noisy approximation
fs
{) def f(z, {) + 8(z).
(10)
This noise 5(x:) can be interpreted, e.g., as computer discretization when calculating [æx E). For our analysis, we need this noise to uniformly bounded. Recently, noisy <black-box> optimization with bounded noise has been actively studied [1 25). The authors of [11] consider deterministic adversarial noise, while in [25] stochastic adversarial noise was explored.
Assumption (Boundedness of noise) There exists a constant Q.
> 0 such that (8(x) < A for all
This is standard assumption often used in the literature (e.g., [17]). Moreover, some applications [4] the bigger the noise the cheaper the zero-order oracle. Thus, it is important to understand the maximum allowable level of adversarial noise at which the convergence of the gradient-free algorithm is unaffected.

---

4.1 Non-smooth sefting
In noisy setup, gradient estimate from (4) replaced by
d
g(r,5,0)
(fa(x + re, fa(x [e.
(11)
2r
Then (6) from Lemma 3 will have an extra factor driven by noise (see Lemma 2.3 from [22])
[Ioo" (e)) - lo (x (9), [e)ille]
2 Ba-1
v VdM₂
dA
S
24
To guarantee the same convergence the algorithm in Theorem (see (8)) for the adversarial deterministic noise case, the variance term must dominate the noise term, i.e. dAr-1 S vdM2. Note that if the term with noise dominates the term with variance, it does not mean that the gradient-free algorithm will not converge. contrast, algorithm will still converge, only slower (oracle complexity will be e-2 times higher). Thus, if we were considering the zero-order oracle concept with adversarial stochastic noise, would be enough to express the noise level A, and substitute the value of the smoothing parameter to obtain the maximum allowable noise level. However, since we are considering the concept of adversarial noise in a deterministic setting, following previous work [11, 1] say that adversarial noise accumulates not only in the variance, but also in the bias:
Bg.e (19(2, - (z)) & Vābl|rller-1
for all Rd
This bias can be controlled by the noise level A, i.e., in order to achieve the s-accuracy algorithm considered this paper, the noise condition must be satisfied:
AS RVd
(12)
As we can see, we have more restrictive condition on the noise level in the bias (12) than in the variance (A S <Ma/va). Thus, the maximum allowable level of adversarial deterministic noise, which guarantees the same convergence of ZO-clipped-SB SSTM, as in Theorem (see (8)) is as follows
RM2
where r = 5/2M, the smoothing parameter from Lemma 2.
Remark (jestrongly convex case) Let us assume that [(x) is also p-stroogly convex (see Assump-
tion 1). Then, following the works [11, 22], we can conclude that the R-ZO-clippe-SSSTH has the same oracle and iteration complexity as in Theorem 2 at the following maximum allowable level of adversarial noise: A S n² /222 VdM2.
4.2 Smooth setting
Now we examine the maximum allowable level of noise at which we can solve optimization problem (I) with e-precision under the following additional assumption
Assumption (Smoothness) The function f is L-smooth, i.e., it is differentiable on Q for all y, with L > 0:
[Vf(() - ff(x))22 < Llly x/12.
If Assumption holds, then Lemma be rewritten as
Lr²
sup #EQ
Thus, present the convergence results of the gradient-free algorithm in the smooth setting. Specifically, if the Assumptions 2-4 are satisfied, then 20-clipped-SSS Saneedd-STIi SSTM converges to E-accuracy after ō (VLRPe-1 iterations with probability least It easy to see that the iteration complexity improves in the smooth setting (since the Lipschitz gradient constant L already exists,

---

i.e., no smoothing is needed), but oracle complexity remained unchanged (since we are still using the gradient approximation via (2 randomization (11) instead of the true gradient (=)),,), consistent with
the already optimal estimate on oracle calls: Ō ((VM22 (MM (
And to obtain the maximum
allowable level of adversarial noise A in the smooth setting, which guarantees such convergence, it is sufficient to substitute the smoothing parameter T VEEL in the inequality (12):
g3/2
AS
RVLL.
Thus, we can conclude that smooth setting improves iteration complexity and the maximum allowable noise level for the gradient-free algorithm, but the oracle complexity remains unchanged.
Remark (u-sttongly convex case) Suppose that fz) is also p-strrongy convex (see Assumption 1). Then we can conclude that R-ZO +-20-clipped-SS) SSTM has the orucle and iteration complexity just mentioned above at the following maximum allowable level of adversarial noise: A S. /
Remark 3 (Upper bounds optimality) The upper bounds on maximum allowable level of adversar- ial noise obtained in this section in both non-smooth and smooth settings are optimal in terms of dependencies on E and according to the works [32, 34).
Remark 4 (Better oracle complexity) In the aforementioned approach in the case when (x, E) has
Lipschitz grudient in x (for all {) one can improve oracle complexity from Ō ((ViM)Re))
to Ō (d (M₂RE 1) This can be done by using component wise finite-difference stochastic gradient approximation [15]. Iteration complexity remains Ō (VLLP--1). (omais@((VLPP-))) for u-strongly convex case: from Ö (() x to Ô (M( ()=
The same can be done
5 Details of the proof
The proof is built upon a combination of two techniques. The first one is the Smoothing technique from [17] that is used to develop gradient-free method for convex non-smooth problems based on full-gradient methods. The second technique is the Accelerated Clipping technique that has been recently developed for smooth problems with the noise having infinite variance and first-order oracle [35]. The authors of [35] propose Hipped--STTY method that we develop in our paper. We modify clipped-SST SSTM by introducing batching into it. Note that due to the infinite variance, such modification is interesting in itself. Then we run batched clipped- SSTM with gradient estimations of function f obtained via Smoothing technique and two-point zeroth-order oracle. To do this, need to estimate the variance of the clipped version of the batched gradient estimation.
In more detail, we replace the initial problem of minimizing f by minimizing its smoothed approx- imation fy, see Lemma 2 In order to use estimated gradient of f, defined in (4) or (5), we make sure that it has bounded a-th moment. For these purposes we proof Lemma 3. First part shows boundness of unbatched estimated gradient g defined in (4). It follows from measure concentration phenomenon for the Euclidean sphere for Ma. -ipschitt function f(x + er). According to this phenomenon probability of the functions deviation from its math expectation becomes exponentially small and a-th moment of this deviation becomes bounded. Furthermore, the second part of Lemma 3 shows that batching helps to bound a-th moment of batched gradient g defined in (5) even more. Also batching allows parallel caleulations reducing number of necessary iteration with the same number of oracle calls. All this is possible thanks to the result, interesting in itself, presented in the following Lemma.
Lemma 4 Let XI...., XB be d-dimensional martingale E| X1] = for < i BB satisfying for 1 $ a $
difference sequence (i.e.
E|| X,-1, X1 < 0
Then we have
B
2 Ba-1
X
<
2

---

The proposed Next, we use the Clipped-SSTM for function for with heavy-tailed gradient estimates. This algorithm was initially proposed for smooth functions in the work [35]. The scheme for proving convergence with high probability is also taken from it, the only difference is additional randomization caused by smoothing scheme.
6 Numerical experiments
We tested ZO-clipped-SSTM on the following problem
min || - bll2 + (S,
=ER-
where { is a random vector with independent components sampled from the symmetrie Levy a-stable distribution with a 3/2, A Rmxdd b IRm (we used d = 16 and 500). For this problem, Assumption holds with
and Assumption holds with a = 1/2 and M2(5) = || + [
We compared ZO-clipped-SSTI proposed in this paper, with ZO- SGD and ZO-SSTM. For these algorithms, we gridsearched batchsize B 5, 50, 100, 500 and stepsize y y: - 3, le 4, le 5, le The best convergence
20-clipes-15TM
20-55 M
20 950
10t
50-00)
achieved with the following parameters:
10a
Z0-clipped-SSTM: 7 = le 3,
== = 1 0.01,
ZO-SSTM: 7 = le 5, B = 500,
sampaAs
ZO-SGD: 7 le 4, B 100,
w = 0.9, where w is a heavy-ball momentum parameter.
Figure 1: Convergence of ZO So--ciiped-SSTTE ZO-SGD and ZO-clipped-SSTT SSTM in terms of gap function w.r.t. the number of consumed samples.
The code is written Pythone and is publicly available at attps://githh Figure presents the comparison of convergences averaged over 15 launches with different noise. In contrast to ZO-clipped-SSS SSTM, the last two methods are unclipped and therefore failed to converge under haivy-tailed noise.
wttc/oocmm//aaeeee http://lpppppStccssttt.sss SttpssoccchssiMMMtcheeeeeee cMethods /20 cl wlipped-SSST. SSTM.
7 Conclusion and future directions
In this paper, we propose a first gradient- free algorithm ZO-clipped-SSTW and solve problem (I) under heavy-taile noise assumption. By using the restart techmique we extend this algorithm for strongly convex objective, we refer to this algorithm algorithms are optimal with respect to oracle complexity (in terms of the dependence on e), iteration complexity and the maximal level of noise (possibly adversarial). The algorithms can be adapted to composite and distributed minimization problems, saddle- point problems, and variational inequalities. Despite the fact that the algorithms utilize the two-point feedback, they can be modified to the one-point feedback. We leave it for future work.
1-ZO-clipped-SS
Moreover, we provide theoretical basis demonstrate benefits of batching technique in case of heavy-tailed stochastic noise and apply it to methods from this paper. Thanks to this basis, it is possible to use batching other methods with heavy-tiled noise, e.g. first-order methods presented in [35, 29].
Acknowledgment
The work of Alexander Gasnikov, Aleksandr Lobanov, and Darina Dvinskikh was supported by grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D733311P0000000
and the agreement with the Ivannikov Institute for System Programming of dated November 2, 2021 No. 70-2021-00142.
10

---

References
[1] BA Alashkar, Alexander Vladimirovich Gasnikov, Darina Mikhailovna Dvinskikh, and Alek- sandr Vladimirovich Lobanov. Gradient-free federated learning methods with 1_1 and 1_2- randomization for non-smooth convex stochastic optimization problems. Zhurnal Vychislitel noi Matematiki Matematicheskoi Fiziki, 63(9): 458--1512, 2023.
[2] Peter Bartlett, Varsha Dani, Thomas Hayes, Sham Kakade, Alexander Rakhlin, and Ambuj Tewari. High-probability regret bounds for bandit online linear optimization. In Proceedings of the st Annual Conference on Learning Theory- Theory-COLT COLT 2008, pages 335-342. Omnipress, 2008.
[3] Anastasia Sergeevna Bayandina, Alexander Gasnikov, and Anastasia Lagunovskaya. Gradient-free free two-point methods for solving stochastic nonsmooth convex optimization prob- lems with small non-random noises. Automation and Remote Control, 79:1399- 1408, 2018.
[4] Lev Bogolubsky, Pavel Dvurechenskii, Alexander Gasnikov, Gleb Gusev, Yurii Nesterov, Andrei M Raigorodskii, Aleksey Tikhonov, and Maksim Zhukovskii. Learning supervised pagerank with gradient-based and gradient-free optimization methods. Advances in neural information processing systems, 29, 2016.
[5] Sébastien Bubeck and Nicoló Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
[6] Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in neural information processing systems, 32, 2019.
[7] Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter Bartlett, and Michael Jordan. Optimal mean estimation without a variance. In Conference on Learning Theory, pages 356-357. PMLR, 2022.
[8] Damek Davis, Dmitriy Drusvyatskiy, Lin Xiao, and Junyu Zhang. From low probability to high confidence in stochastic convex optimization. Journal of Machine Learning Research, 22(49):1-38, 2021.
[9] Yuriy Dorn, Kornilov Nikita, Nikolay Kutuzov, Alexander Nazin, Eduard Gorbunov, and Alexander Gasnikov. Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits. arXiv preprint arXiv:2305. 06743, 2023.
[10] John C Duchi, Michael I Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of function evaluations. IEEE Transactions on Information Theory, (5):777888228 2015.
[11] Darina Dvinskikh, Vladislav Tominin, Iaroslav Tominin, and Alexander Gasnikov. Noisy zeroth-order optimization for non-smooth saddle point problems. In Mathematical Optimization Theory and Operations Research: 21 International Conference, MOTOR 2022, Petrozavodsk, Russia, July 2-6, 2022, Proceedings, pages 18-33. Springer, 2022.
[12] Pavel Dvurechenskii, Darina Dvinskikh, Alexander Gasnikov, Cesar Uribe, and Angelia Nedich. Decentralize and randomize: Faster algorithm for wasserstein barycenters. Advances in Neural Information Processing Systems, 31, 2018.
[13] Yu Emnolee. Stochastic programming methods, 1976.
[14] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprint cx/0408007, 2004.
[15] Alexander Gasnikov, Darina Dvinskikh, Pavel Dvurechensky, Eduard Gorbunov, Aleksander Beznosikov, and Alexander Lobanov. Randomized gradient-free methods in convex optimization. arXiv preprint arXiv:2211.13566 2022.

---

[16] Alexander Gasnikov and Yurii Nesterov. Universal fast gradient method for stochastic composit optimization problems. arXiv preprint arXi:: 2016.
[17] Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii, Farshed Abdukhakimov, Dmitry Kam- zolov, Aleksandr Beznosikov, Martin Takac, Pavel Dvurechensky, and Bin Gu. The power of first-order smooth optimization for black-box non-smooth problems. In International Confer- ence Machine Learning, pages 7241-7265. PMLR, 2022.
[18] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping, Advances in Neural Information Processing Systems, 53:15042-55053,, 2020.
[19] Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexan- der Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv:2106.0599 05958,, 2021.
[20] Mert Gurbuzbalaban and Yuanhan Hu, Fractional noment-presservng initialization schemes for training deep neural networks. In International Conference on Artificial Intelligence and Statistics, pages 2233-2241. PMLR, 2021.
[21] Dusan Jakovetic, Dragana Bajovic, Anit Kumar Sahu, Soummya Kar, Nemanja Milosevich, and Dusan Stamenkovic. Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise. SIAM Journal on Optimization, 33(2):394-423, 2023.
[22] Nikita Kornilov, Alexander Gasnikov, Pavel Dvurechensky, and Darina Dvinskikh. Gradient- free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact.
Computational Management Science, 20(1):37, 2023.
[23] Michel Ledoux. The concentration of measure phenomenon. ed. by peter landweber et al. vol.
89. Mathematical Surveys and Monographs. Providence, Rhode Island: American Mathematical Society, page 181, 2005.
[24] Zijian Liu and Zhengyuan Zhou, Stochastic nonsmooth convex optimization with heavy-tailed noises. arXiv preprini arXiv:2303. / /2277, 2023.
[25] Aleksandr Lobanov. Stochastic adversarial noise in the" black box" optimization problem. arXiv preprint , 2023.
[26] Aleksandr Viktorovich Nazin, AS Nemirovsky, Aleksandr Borisovich Tsybakov, and AB Judit- sky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 80(9): 1007-167771 2019.
[27] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. M.: Nauka, 1983.
[28] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17:527-566, 2017.
[29] Ta Duy Nguyen, Alina Ene, and Huy L Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv preprint arXiv:2304.011119 2023.
[30] Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Le Nguyen. High probability convergence of clipped-sgd under taavy- noise. arXiv preprint arXiv:2302.05437. 2023.
[31] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference machine learning, pages 1310-1318, 2013.
[32] Dmitry Pasechnyuk. Aleksandr Lobanov, and Alexander Gasnikov. Upper bounds on maximum admissible noise in zeroth-order optimisation. arXiv preprint arXiv:2306.16371, 2023.
[33] Svetlozar Todorov Rachev. Handbook of heavy tailed distributions in finance: Handbooks in finance, Book 1. Elsevier, 2003.
12

---

[34] Andrej Risteski and Yuanzhi Li. Algorithms and matching lower bounds for approximately- convex optimization. Advances in Neural Information Processing Systems, 29, 2016.
[35] Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. Highh-robabiiliy bounds for stochastic optimization and variational inequalities: the case of unbounded variance. arXiv preprint arXivv 00999, 2023.
[36] Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 18(1):1003-1713, 2017.
[37] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning. pages 5827-5837. PMLR, 2019.
[38] James C Spall. Introduction to stochastic search and optimization: estimation, simulation, and control. John Wiley & Sons, 2005.
[39] Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. Conference on Learning Theory, pages 65-102. PMLR, 2022.
[40] Hongjian Wang, Mert Gurbuzbalaban, Lingjiong Zhu, Umut Simsekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. Advances in Neural Information Processing Systems, 34:1 18866-18877, 2021.
[41] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33, 2020.
[42] Jiujia Zhang and Ashok Cutkosky. Parameter-free regret in high probability with heavy tails. Advances Neural Information Processing Systems, 35:8000-8012 2022.
13

---

A Batching with unbounded variance
To prove batching Lemma 4 generalize Lemma 4.2 from [7] not only for i..d. random variables with zero mean but for martingale difference sequence.
Lemma Let g(z) = sign [=) = V 111" for < a 52 Then any 2 0
maxg(1 h)) g(x) 2 22- aaa==_ =22 -22-ng(0 =2h-ng(h).
Proof. Consider ((x) = g(x + h) g(z)). We see that is differentiable everywhere except 0
and x h. As long as + 0, -h, we have
(x) = 0ax + h) - gz) = (a 1)(x= + h|a |x1
Since, we have a > 1, I
is local maxima for ((x). Furthermore, note that ('(x) 2 0 for E (-00- - (1) \ {- and (z)x)
for (- o0) \ {0). Therefore, = is global maxima.
Lemma Let 21..... JB
be one-dimensional martingale difference sequence, i.e.
E æ1 = 0 for 1 < i < B, satisfying for S a 2
21 11-1..... r1l S d".
We have:
n0
E
B
Bo-1
Proof. Everywhere below we will use the following notations.
Es(1 def Er E []:
E E def
-1.-..
For = 1 proof follows from triangle inequality for .1. When a > 1, we start by defining
S:
So = 0,
f(x) = 1
Then we can calculate desired expectation as
B
B
[[)(S))]
E
S(S.) - f(S
=
E (1((S.)
8,
Σ
(x)dr
1=1
9
/
E
x
(' (S
f'(x) - ((())-(((S))))) ('(
(13)
8
While {2:} is martingale difference sequence then ( = Ees E Bedl (x = 0.
From (13) and Lemma 5 (g(z) = (() we obtain
|z
B
[[[(S)))
Σ
si (S +
f(() 1)s 212-0
E
1'(1/2)d1
S
1x.1/2
B
Σ
E
2f' (s)ds
22-
E [f
2 a
Ezi
[E
[[x)]]/2)]] < 2B
(14)
Now we are ready to prove batching lemma for random variables with infinite variance.
14

---

Lemma
Let
. XB be d-dimensional martingale
difference sequence, i.e.
X X1] for <is B. satisfying for 2
E x -I..........
Xil - d
We have
2
E
Ba-1
Proof.
Let 9 (0, and yi conditional expectation we get
def
X g- Firstly, prove that Elyg] B[[[X:11)] Indeed, using
Blyy/ 9]
EE [ 91)%1 = Ex, [ [(xx, 9l)]]]
Ex. Esix; ((Ix] 91)2)//22)
Jensen ing S
(E ()) /0/2
Ex
(11x a/2 = |||| 11]] Next, considering X, g (O [X]] and, thus, Eg X gl
Ex.
(15)
|X||| Il, we bound desired expectation
as
B
B
Ex
X;
Ex
Egg
2
X
(16)
1=1
Jensen's 's ing
Ex.9
Σ
x
g
Ex.
Σ
(17)
Finally, we apply Lemma 6 for yi sequence with bounded a-th moment from (15) and get
Ex
X
<
Ex
E
Σ
V
20 B.
i=1
B
Smoothing scheme
Lemma 8 Assumption 2 implies that f(x) is M2 Lipschitz on Q.
Proof. For all 11, Q
If(z1) f(22)
Eelf(zn f(22, E)]l Egllf(z1, f(22, [M(a)())] - #2ll2 S M2 - 22|12-
(18)
(19)
The following lemma gives some facts about the measure concentration on the Euclidean unit sphere for next proof.
Lemma Let f(x be My Lipschitz continuous function w.r.t ||. Ife is random and uniformly (1,2), then
distributed the Euclidean sphere and
6M3
Ex - (e)l(
<
b
v2
Proof. standard result the measure concentration on the Euclidean unit sphere implies that Vt
Pr (If(e) E[f(e))] > t) < 2exp( 5'dtt (M2)) =
(20)
15

---

(see the proof of Proposition 2.10 and Corollary 2.6 in [23]). Therefore,
Ee (J(e)- (ols(e)))
Pr - > 1) dt
Pr (1((0) B[f(e)]] v/ dt
-b'd.t%///M3 /M3 dt - bM3
2 exp
(21)
t=
Finally, below we prove Lemma which states that batched gradient estimation from (5) has bounded a-th moment.
Proof of Lemma 3.
1. We will prove equality immediately for gd. Firstly, notice that distribution of is symmetric and by definition (5) we get
B
Eg,olg (.) =
d
Σ
Es e. [f(x + tei - f(x - re,, Es)ei]
2BT
1=1
d
Eee [1E, [f + Te,, e.)
BT
i=1
d
Ee, +
(22)
BT
Using v(((x) [Rel + re)e] from Lemma we obtain necessary result.
2. By definition (4) of estimated gradient g bound a-th moment
d (f(x + (e,E) - f(x - (),
E Eg,e
d
2T E ||le|| + f(x =).
(23)
Considering ||e||2
1 we can omit Next we add =0(E) in (23) for all )(g) and get
Bx.e [I + Te, f(x te, 1]
= E5,e 11f(= re, - 6) - (f(r - rC, {) - 1
Using Jensen's inequality for la we bound
e [l( +e, 8) (f(z - (e,
< 2d Eg,o [z + rc, 8 5|0ी [0]]+2-11pp 2 llf rc, 8
We note that distribution of symmetric and add two terms together
2a-' [lf(x rc, 5|0] 2 Ilf(r Tc, - 5
< 2 [I + re, { - 510)
Let 8(E) = Ea re, }) then because of Cauchy-Sehwartz inequality and conditional expectation properties we obtain
2 [1 r), 510] E EN [f[( + re, -
< 2
[ Ea [I[ + re, E. + Te, (e]
16

---

Next, we use Lemma 9 for f(x + re, with fixed & and Lipschitz constant M2(E)r
2 2-1/272
Be
[I[ [1 Te,
Bel Te,
S Te
(T22-1/2) (=d
a/2
2-112
2
2 (M s 2"
M27
d
d
Finally, we get desired bound of estimated gradient
vd
E F,,eello(r,,.e))13 =
21/4 M2
(24)
Now we apply Jensen inequality to
Bg.elllg(r,&..) &, e)
e)]12] < 2a-1 (Re,alll(2,,,,e)ll + Re.ello(r,, 6, (2)
(25)
And get necessary result.
For batched gradient gD we use Batching Lemma and estimation (25).
C Missing Proofs for ZO-clipped-SSTM and R-ZO-Clipped-SSTM
In this section, we provide the complete formulation of the main results for Hiipped-SSTI and R-clipped-SSTT -STM and the missing proofs.
Minimization on the subset Q In order to work with subsets of Q C Rd we must assume one more condition on (x).
Assumption& We assume that there exist some convex set Q C TRdd constants t, L > 0 such that for all x. Q
( I 2L (((x)))))
(26)
where f: inf fx(x) > -0.
When Q R2 (26) follows from Lemma 2 as well. But in general case this is not true. work [35] in Section "Useful facts" authors show that, in the worst case, to have (26) set Q one needs to assume smoothness on a slightly larger set.
Thus, in the full version of the theorems in which we can require much smaller Q, we will also require satisfying all three Assumptions 1, 2, 5.
C.1 Convex Functions
We start with the following lemma, which a special case of Lemma 6 from [19]. This result can be seen the "optimization" part of the analysis of -SSpe the proof follows the same steps as the analysis deterministic Similar Triangles Method [16], [12] and separates stochasticity from the deterministic part of the method.
Pay attention that in full version of Theorem 1 we require Assumptions 2 to hold only on Q BaR(ø*) ), however we need to require one more smoothness Assumption 5 as well.
17

---

Theorem (Full version of Theorem 1) Let Assumptions 1,2, 5 with 0 hold on Q Baa(**)
where |200 x²1
and
4K
1800
1)K
4K
2 max
48600 In
(27)
B LR
R
As 30a 1 In 4K
(28)
L Mavd
(29)
for some K and (0, 1] such that in the iterates with probability at least B satisfy
2 Then, after K iterations of ZO- ZO-lipped-SSTTT
B
GaLR
f-x)- S 2M2T
and {a 12 ok 1 K Tkmo S B2n(x"). (30)
K(K +3)
In particular, when parameter a equals the maximum from (27), then the iterates produced by ZO- clipped-SSTM after K iterations with probability at least 1 B satisfy
LR 2 K
K oRin
m-1
1)
f(y*) f(x)) 2M2T +0
max
3
3
(31)
K2
(BK)
meaning that to achieve f(y f(x*) S e with probability least clipped-SSTM requires
B with 6
-0-
IMs
(1
MR VRVdR2 M3
ddR 1 2BB
oR
o
K K=o
In
In
iterations. (32)
B
B3
In case when second term in max in (31) is greater total number of oracle calls is
oR
R
K. T-
In
Proof. The proof is based the proof of Theorem F.2 from [35]. We apply first-order algorithm clipped-SSTI for Mavid -mooth function fr with unbiased gradient estimation n that has a-th moment bounded with 2n" Additional randomization caused by smoothing doesn't affect the proof of the original Theorem.
According to it after K iterations we have that with probability at least 1 B
.a..R2
f - K(K +3)
and [ {z {u S B2R(x*).
Considering approximation properties of fr from Lemma 2
fly*) - ffxx)) $ 2M + 6a LR
K(K +3)
Finally, if
4K
18000 K + 1)K In
8-1 4K
a max 48600 In?
3
= LR
18

---

then with probability at least 1 - B
6aLR
f(y*) - f(x") < 2M2 +
K(K + +3)
291600LR In2
4K
10800oR((K 1)K In
2M2r max
K(K +3)
K(K + +3)B"
LR In² K B
oRh
2M2r + O
K2
(BK)
=
where L Mava by Lemma 2.
To get f1y fx*) S with probability at least B it sufficient choose 7
4W1 and K
such that both terms the maximum above are ((e). This leads to
M3 22
M3RdR
VR
d
1
RR
RR
K-O
In
In
2²
B
B
that concludes the proof.
C.2 Strongly Convex Functions
In the strongly convex case, consider the restarted version of Z0-clipedd SSTM (R-ZO-clippee SSTM). The main result is summarized below.
Pay attention that in full version of Theorem 2 we require Assumptions 1, 2 to hold only on Q Bsn(=*). however we need to require one more smoothness Assumption as well.
Theorem (Full version of Theorem 2) Let Assumptions I, 2, 5 with μ hold for Ban(x*), where 2 ||=00 x²1 and R-ZD-dlipped-SSTM runs Z0-dlipped-SSTM times. Let
VdM₂
Ek M2
L
Tk =
(33)
L.R
2160
L L.R
N
10800a R
R
a-1
4N
5400g
K,
max 1
In
In
Et
VeBB
B₁
B,3
(34)
RRR_
N = log2 uR
4K,N
Rr
In
2 1,
(35)
21121/2
28
B
4K,N
1800a Kr + K)
In a-1 4K,N
04 = max
48600 In
(36)
8
B. a-1
LiRe
R
X
(37)
30a +1 In 1K,N
for = L...., T. Then to guarantee f(i²) f(x²) S E with probability 2 1 - ,3 R-Clipped-SSTM requires
M3Va Vd E/p
RR²
Mad's S
nR²
2
Zio
max
In
In
In
In
E
uE
UEE
E
(38)
oracle calls. Moreover, with probability 2 the ball B2R--1 (2R)),(x"),
B the iterates of R-RRipppedd-STT stage stay in
19

---

Proof. The proof itself repeats of the proof Theorem F.3 from [35]. In this theorem authors prove convergence of restarted clipped-SSTM. In our case it is sufficient to change clipped-SSTM ZO-
clipped-SSTM and put results of Theorem 3 in order to guarantee g-solution after Σ K₁ successive
iterations.
It remains calculate the overall number of oracle calls during all runs of clipped-SSTIN We have
N
B
=
o
Σ
N
max
M3 M3VOR,
o7
In
V M3
MRVaRG-NN
E3B
B
1
σ
R
Et
In
BB
N
R
Et
M3 vd R2 1122
V MMWaN
N
I
o
max
In
ln
1R
1RR
N
M2 va R2
MRVaN
N
2
2%
max
24
In
2//2
a.
In
a
PR3
PR
3
pR
max
M3V V 122
2N/2 In
2N/2 V
MB Va
PRR
n-1
In
N
22
2 1
WRB
E
uR
B
pR
M3vd E/
M3Va
PRR
N
1-8
aN
O
max
In
In
In
2 2)
22(1-13
VETB
uR
B
uR
M3Vd E/
VM3Vd
PR?
0
2
022
2[a
HRR
O
max
In
In
In
ln
VEPB
E
UEE
uE
E
which concludes the proof.
20


Reviews:
[{"review_id": "fHOMNspV2i", "reviewer": "Reviewer_6zia", "summary": "This paper provides high probability bounds for the convergence of gradient-free methods on convex and strongly-convex functions when the noise in the gradient oracle has infinite variance. An oracle provides $f(x,\\xi)$, a noisy evaluation of the function $f$ at point $x\\in \\mathbb{R}^d$ by the oracle, where $\\xi$ is the noise variable. For the same noise $\\xi$, the function is $M_2(\\xi)$-Lipschitz, where $M_2(\\xi)$ quantifies the noise level.\n\nIf the noise variance is finite, ($\\mathbb{E}[M_2(\\xi)^2] < \\infty$), [1] provides optimal iteration and oracle complexity for convergence of in expectation. The primary technique used in [1] is a batched accelerated gradient method which uses smoothing. For a fixed constant $\\tau>0$ which defines the smoothing level, smoothing computes an approximate gradient of $f$ at point $x\\in \\mathbb{R}^d$ as, \n\n$$\ng^B(x) = \\frac{d}{2B \\tau }\\sum_{i=1}^B (f(x + \\tau e_i, \\xi_i) - f(x - \\tau e_i, \\xi_i))e_i\n$$\nHere, $e_i$ are sampled uniformly from the unit sphere, $\\xi_i$ are the noise variables of the oracle and $B$ is the batch size. On expectation, the smoothed gradient is the gradient of $ \\mathbb{E}_{e,\\xi}[f(x + \\tau e, \\xi)] $. For small value of $\\tau$, this approximation is close to $f$. Further, even if the function $f$ is non-smooth but Lipschitz, smoothing makes  $\\frac{\\sqrt{d}M_2}{\\tau}$ smooth.\n\n\n\nThis paper extends this technique to the infinite noise variance setting, $\\mathbb{E}[M_2(\\xi)^\\alpha] < M_2^\\alpha$ for some $\\alpha \\in (1,2]$ by applying clipping. Specifically, the technique of clipped Stochastic Similar Triangles used for handling heavy tailed noise in smooth optimization is extended to the non-smooth case by the above smoothing procedure.\n\nFor convex Lipschitz functions, the iteration complexity and oracle complexity is $\\frac{\\sqrt{d}^{1/4}}{\\epsilon}$ and $\\left(\\frac{\\sqrt{d}}{\\epsilon}\\right)^\\frac{\\alpha}{\\alpha-1}$. For $\\mu$-strongly convex and lipshcitz functions, the corresponding bounds are $\\frac{d^{1/4}}{(\\mu\\epsilon)^{-1/2}}$ and $\\left(\\frac{d}{\\mu\\epsilon}\\right)^{\\frac{\\alpha}{\\alpha-1}}$. These rates are shown to be optimal in $\\epsilon$.\n\n\nFurther, when if the oracle provides a corrupted value of $f$ with an additive corruption of $\\lvert\\delta(x)\\rvert \\leq \\Delta$, the authors derive the maximum possible values of $\\Delta$ such that the convergence rates for both smooth and non-smooth settings are unaffected by the corruption.\n\n\n**References**\n1. Gasnikov et al. The power of first-order smooth optimization for black-box non-smooth problems. ICML 2022.\n2. Sadiev et al. High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. ICML 2023.", "questions": "- Are there any lower bounds for oracle and iteration complexity in the adversarial corruption case in terms of $\\Delta$?\n- Are there methods other than clipping to handle unbounded variance in stochastic optimization?", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "- **Interesting Problem Setting**:  Heavy-tailed noise is a significant problem which violates the commonly used bounded variance assumption in stochastic optimization.  The authors extend the solution of clipping to handle it for derivative-free methods.\n- **Convergence Rates** : These are the first convergence rates for derivate-free optimization under heavy-tailed noise. Further, the rates are high probability bounds instead of in expectation. Additionally, for both cases, convex and strongly convex,  the obtained rates are optimal in terms of error $\\epsilon$.\n- **Thorough literature review** : The authors thoroughly review existing results in derivative-free methods and clipping.", "weaknesses": "- **Presentation** : The paper seems to be missing an introduction and experiment section. Although the paper is theoretical, the proposed algorithm, clipped-SSTM with two-point feedback, is new and should have been tested on at least synthetic problems.\n\n- **Lack of a motivating example** : The authors do not provide a motivating example which justifies the heavy-tailed noise in gradient-free settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed summary of our main contributions. Below, we address questions and concerns raised by the reviewer.\n\n> **Missing introduction and numerical experiments.**\n\nWe agree that the introductory part can be improved and will extend it in the final version of our work. We will add more motivational examples about the significance of the problem we are solving, in particular, motivational examples that justifies the use of gradient-free methods as well as the need to consider heavy-tailed noise. Moreover, we understand your concern about the presentation of our work, but we promise that the final version will be much more comprehensive and precise.\n\nThe numerical experiments are provided in the general response to all reviewers.\n\n> **Motivating examples.**\n\nThank you for the suggestion. See our general response where we provide motivating examples. We will definitely add them to the final version.\n\n>**On the lower bounds.**\n\nThe lower bound for the iteration complexity can be found in [1]. The lower bound for oracle complexity is presented in [1] and [2]. These lower bounds were obtained in a noiseless setup ($\\Delta = 0$). The lower bound for $\\Delta$ (maximal absolute value of noise) is given in [3]. The additional presence of noise cannot improve iteration and oracle complexity, it can only make it worse. The upper bounds of our method meet (up to the numerical and logarithmic factors) all of these three lower bounds (for iteration complexity and $\\Delta$, this holds in the regime when $\\varepsilon^{-2} \\lesssim d$, this is the large-dimension regime, when the subgradient method is better than the center of gravity type methods [1]). Thus, our algorithm is optimal in terms of all of these three criteria.\n\n[1] Arkadii S. Nemirovsky and David B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983. \n \n[2]  S. Bubeck, Q. Jiang, Y. T. Lee, Y. Li, A. Sidford, et al. Complexity of\nhighly parallel non-smooth convex optimization. Advances in neural information processing systems, 2019.\n\n[3]   A. Risteski and Y. Li. Algorithms and matching lower bounds for approximately-convex optimization. Advances in Neural Information Processing Systems, 29:4745–4753, 2016. \n\n\n>**Alternatives to clipping.**\n\nHeavy-tailed noise can also be handled without explicit gradient clipping. For example, one can use Stochastic Mirror Descent algorithm with a particular class of uniformly convex mirror maps [1]. This algorithm does not require any explicit gradient clipping or normalization. However, the convergence guarantee was given in expectation. Moreover, it is not clear how to apply batching and acceleration for this method. Without this, we would not be able to get the optimal method in terms of the number of iterations and not only in terms of oracle complexity. There are also some studies on the alternatives to gradient clipping [2] but the results for these alternatives are given in-expectation and are weaker than the state-of-the-art results for the methods with clipping. This is another reason why we choose gradient clipping to handle the heavy-tailed noise.\n\n[1] Vural, Nuri Mert, et al. \"Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance.\" Conference on Learning Theory. PMLR, 2022.\n\n[2] Jakovetić, Dus̆an, et al. \"Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noise.\" SIAM Journal on Optimization 33.2 (2023): 394-423."}, {"review_id": "1Sgv43j3WR", "reviewer": "Reviewer_nSeP", "summary": "This paper presented derivative-free methods for the optimization of stochastic convex functions with a potentially infinite variance noise. Here the level of noise is defined in terms of the boundedness of modulus of a Hölder-type continuous condition. The main technique is to adopt a gradient clipping to the two-point estimation of the gradient of the randomized smoothed function. For some of their results, they also claim the attained bounds are rate optimal. The presentation and organization is of very clear and relatively easy to follow.", "questions": "See above.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall the contribution is well-motivated, and fits into the flurry of recent development of methods for problem with infinite noise variance. The paper is well written, and the proofs are intuitive and relatively easy to follow.\n", "weaknesses": "I only have some minor comments and questions:\n\n* L113: it might be better to use {\\xi_i}_i and {e_i}_i as the input of the function g^B.\n* L119: where is the \\sigma_B used in the statement of Lemma 3?\n* the second line of Section 2: you might need to assume g \\neq 0.\n* L126: where is the distribution D_k defined?\n* L139: could you elaborate on why the first term is optimal using the lower bound from [4]? Do you need some assumption on batch-size B here to illustrate rate optimality?\n* L152: it might be better to emphasize that w.p. 1-\\beta, *for any* 1 \\leq t \\leq N, ..., if the boundedness of iteration holds uniformly.\n* Question (out of curiosity): is the bound in L190 optimal? Or, is there any lower bound for such a so-called maximum allowable noise level?\n* L224: proof -> prove.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a positive evaluation of our work. Below, we address questions and concerns raised by the reviewer.\n\n\n\n>**L113: it might be better to use {\\xi_i}_i and {e_i}_i as the input of the function g^B.**\n\n\nThank you for the suggestion, we agree with it. We did not want to complicate formulas with $g^B$ and thus used this notation in the paper. We can use bold symbols with superscript $B$ so that there was no confusion: $\\mathbf{e}^B = \\lbrace e_i\\rbrace_i$ and $\\boldsymbol{\\xi}^B =\\lbrace\\xi_i\\rbrace_i$. Then we were able to use $\\mathbf{e}^B$ and as $\\boldsymbol{\\xi}^B$ the input of the function $g^B(x, \\mathbf{e}^B, \\boldsymbol{\\xi}^B)$. We will change this in the final version of our paper.\n\n\n>**L119: where is the \\sigma_B used in the statement of Lemma 3?**\n\n\nThank you for the question. We do not need to introduce $\\sigma_B$ since its value is explicitly written in the third formula in Lemma 3. We will remove $\\sigma_B$ in the final version.\n\n>**the second line of Section 2: you might need to assume g \\neq 0.**\n\n\nThank you, we will add this and also add that $\\text{clip}(0,\\lambda) = 0$.\n\n\n>**L126: where is the distribution D_k defined?**\n\n\nThank you, this is a typo. It must be $D$. This is a distribution of random variable $\\xi$. We do not know $D$ but we can sample from it (see Eq. (1) in line 14).\n\n\n>**L139: could you elaborate on why the first term is optimal using the lower bound from [4]? Do you need some assumption on batch-size B here to illustrate rate optimality?**\nThis optimality is in terms of $\\varepsilon$. The first term is independent of batch size B. In **[4]** (citation is from our work), it was proven that this corresponds to the lower bound in one of the regimes in a noiseless setup. The additional presence of noise cannot improve iteration and oracle complexity, it can only make it worse (due to its possible adversarial nature). The number of iterations of our method that allows the presence of (possibly non-stochastic) noise corresponds to the lower bound for a noiseless setup, that is, the number of iterations is optimal. Also, we refer to [1] where the authors propose an optimal algorithm in terms of oracle and iteration complexity but in classical settings of noise with bounded variance. The iteration complexity of the method from [1] coincides with the iteration complexity of our method. Thus, our algorithm can be also seen as a robust version of the algorithm from [1] that makes it possible to work with heavy-tailed noise.\n**[4]** Sébastien Bubeck, Qijia Jiang, Yin-Tat Lee, Yuanzhi Li, and Aaron Sidford. Complexity of highly parallel non-smooth convex optimization. Advances in neural information processing systems, 32, 2019. \n\n[1] Gasnikov, A., Novitskii, A., Novitskii, V., Abdukhakimov, F., Kamzolov, D., Beznosikov, A., ... & Gu, B. (2022, June). The power of first-order smooth optimization for black-box non-smooth problems. In International Conference on Machine Learning (pp. 7241-7265). PMLR.\n\n\n>**L152: it might be better to emphasize that w.p. 1-\\beta, for any 1 \\leq t \\leq N, ..., if the boundedness of iteration holds uniformly.**\n\n\nThank you, we will do it.\n\n\n>**Question (out of curiosity): is the bound in L190 optimal? Or, is there any lower bound for such a so-called maximum allowable noise level?**\n\nThe lower bound for $\\Delta$ (maximal absolute value of noise) is given in [1]. Our bound exactly corresponds to that lower bound in the regime when $\\varepsilon^{-2} \\lesssim d $. That is the large-dimension regime, when the subgradient method is better than the center of gravity type methods [2]. \n\n[1]   A. Risteski and Y. Li. Algorithms and matching lower bounds for approximately-convex optimization. Advances in Neural Information Processing Systems, 29:4745–4753, 2016. \n\n[2] A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983. \n\n>**L224: proof -> prove.**\n\n\nThank you, we will fix this typo."}, {"review_id": "3yBXd04F74", "reviewer": "Reviewer_FKLk", "summary": "This paper proposed and analyzed a zeroth-order method for non-smooth stochastic optimization under heavy-tailed noise and adversarial noise, by combining ball-averaging-based smoothing technique (to tackle non-smoothness) and gradient clipping technique (to tackle heavy-tailed/adversarial noise). This generalizes previous results where $L_\\infty$ or $L_2$ boundness of noise is assumed. There are also several technical improvements over previous results, including proving a high-probability bound instead of a bound in expectation.", "questions": "I have no additional questions other than the ones discussed in `Weaknesses`.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The topic is important. Gradient free method for stochastic optimization is a popular field of research, and it certainly helps to handle the heavy-tailed/adversarial noisy setting which is common in practice. \n2. I have briefly gone through the proof and have no doubt on its correctness. \n3. Though not proved in the paper, the theoretical bound seems close to being tight.", "weaknesses": "1. The presentation is concise, but maybe at the cost of some necessary clarity. In Eqn. (2) it's not specified what distribution should $\\bf e$ follow (should be the uniform distribution in the unit _ball_), which leaves the entire equation undefined. It becomes even more confusing that later in (3) $\\bf e$ is used with a different meaning, denoting a random vector uniformly distributed on the unit _sphere_!\n2. It may also improve clarity to discuss the order of the theoretical bounds and compare them with previous results. In particular, it would be helpful to discuss whether the dependence of $\\alpha$ is optimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a positive evaluation of our work. Below, we address questions and concerns raised by the reviewer.\n\n>**The presentation is concise, but maybe at the cost of some necessary clarity. In Eqn. (2) it's not specified what distribution should $e$ follow (should be the uniform distribution in the unit ball), which leaves the entire equation undefined. It becomes even more confusing that later in (3) $e$ is used with a different meaning, denoting a random vector uniformly distributed on the unit sphere!**\n\nWe thank the reviewer for spotting this mismatch in our notation. Eqn. (2) is the only place where vector $e$ should be uniformly distributed on the unit **ball**. Everywhere else $e$ is a random vector uniformly distributed on the unit **sphere**. To avoid this confusion, we propose the following change that we will apply in the final version: in Eqn. (2) we will use vector $u$ to denote a random vector uniformly distributed on the unit ball. Then, everywhere in the paper, vector $e$ will denote a random vector uniformly distributed on the unit sphere.\n\n>**It may also improve clarity to discuss the order of the theoretical bounds and compare them with previous results. In particular, it would be helpful to discuss whether the dependence of $\\alpha$ is optimal.**\n\nOur work is the first work on gradient-free optimization with heavy-tailed noise.  Optimality of oracle complexity in terms of the dependence on $d$ is an open problem in non-smooth settings (if $\\alpha$=2, i.e., when noise has bounded variance, it is optimal). However, it is not optimal for **smooth** stochastic convex optimization problems with $(d+1)$-points stochastic zero-order oracle. \nIteration complexity and maximal level of noise are optimal (coincides with lower bounds in one of the regimes, see [1, 2]). We will add these remarks to the final version of the paper.\n\n[1]  Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1), 1-122.\n\n[2]   A. Risteski and Y. Li. Algorithms and matching lower bounds for approximately-convex optimization. Advances in Neural Information Processing Systems, 29:4745–4753, 2016.\n"}, {"review_id": "YG3CCcws6S", "reviewer": "Reviewer_M3Ug", "summary": "In this papers, the authors build upon the work that has been done in [28] and adjust the proposed algorithms there for zero-order oracles rather than the gradient oracles. The goal is to optimize non-smooth stochastic convex optimization problems with infinite variance. ", "questions": "- In which cases we should utilize the proposed accelaerated zeroth-order method for non-smooth stochastic convex optimization problems with infinite variance?\n\n- It is not very clear to me why the paper considers the case when \\delta = 0 on page 6. Could you please elaborate more on that?\n\n- Could you please list some instances where non-smooth stochastic convex optimization problems show up and why we should be interested in them?", "limitations": "The advantages and the disadvantages of the proposed method is not discussed in detail except for the advantage of enabling weaker assumptions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper does a good job when it comes to introducing the notions they have used with clarity. The organization of the paper helps the reader to understand the concepts. The quality of the write up and the technical contributions look solid. ", "weaknesses": "- Minor typo in the abstract: ajust --> adjust.\n\n- \"We emphasis (--> emphasize) that this generalization requires an extension of the batching technique to (--> for) infinite variance.\" The emphasis should be emphasize in this sentence and I believe for is more suitable than to.\n\n- The motivation about why we should be interested in such problems is only explained in citation numbers ([30, 6]) with no mention of what these motivating examples actually are. You have 9 pages of space without the references and you are not utilizing all of it. I suggest using the remaining space to attract more attention to your paper by mentioning concrete examples. This would help with the visibility of your paper as well.\n\n- \"• can be generalized for saddle-point problems (based on [28]) and one-point feedback [13]. We leave it for future work.\" This should not been mentioned in the contributions since this paper has not actually made this contributions yet. You can add a conclusion and/or future work paragraph or section in the end mention it there.\n\n- Similarly, related work could have a section of its own.\n\n- My main concern about this paper is that, even though adjusting the method from [28] for two-point zero-order oracle is nontrivial, it feels a bit too incremental for a venue like NeurIPS. Also, the trade-off between using weaker or stronger assumptions can be discussed further in order to convince the reader on the advantages and the disadvantages of the zeroth-order methods and where to use which.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for a detailed review of our work. Below, we address questions and concerns raised by the reviewer.\n\n>**Minor typo in the abstract: ajust --> adjust.**\n\n>**\"We emphasis (--> emphasize) that this generalization requires an extension of the batching technique to (--> for) infinite variance.\" The emphasis should be emphasize in this sentence and I believe for is more suitable than to.**\n\nThank you, we will fix these typos.\n\n> **Motivating examples.**\n\nThank you for the suggestion. See our general response where we provide motivating examples. We will definitely add them to the final version.\n\n\n>**\"• can be generalized for saddle-point problems (based on [28]) and one-point feedback [13]. We leave it for future work.\" This should not been mentioned in the contributions since this paper has not actually made this contributions yet. You can add a conclusion and/or future work paragraph or section in the end mention it there.**\n\nYou are right, thank you for the comment. We will move this part to the conclusion section.\n\n>**Similarly, related work could have a section of its own.**\n\nWe agree with the reviewer and promise to fix the final version of the paper accordingly. \n\n\n>**My main concern about this paper is that, even though adjusting the method from [28] for two-point zero-order oracle is nontrivial, it feels a bit too incremental for a venue like NeurIPS. Also, the trade-off between using weaker or stronger assumptions can be discussed further in order to convince the reader on the advantages and the disadvantages of the zeroth-order methods and where to use which.**\n\n\nThank you for this suggestion. We should definitely more thoroughly explain the need for zero-order methods in the introduction. Zero-order methods should be used when one has black-box access to an objective function, e.g., the objective function is computed by a black-box simulation package or it is the result of a real experiment. Thus, automatic differentiation is impossible. This is often the case of various problems encountered in medicine, biologics, physics, and etc. The disadvantage of zero-order methods is the dependence of iteration and oracle complexity on the problem dimension $d$. The main advantage of zero-order methods is the possibility to solve an optimization problem when it is impossible to apply first-order methods (as we cannot calculate derivatives). However, all existing zero-order methods are not robust to heavy-tailed noise, which is why we propose a zero-order algorithm that is able to cope with this issue.\n\nOur main result indeed relies on the techniques from Sadiev et al. (2023), but we would like to highlight that the adjustment of clipped-SSTM to the derivative-free setup is non-trivial. To do it we needed to generalize the smoothing technique to the case of bounded $\\alpha$-th moment, e.g., see Lemma 11. Next, to achieve optimal oracle and iteration complexities, we also needed to generalize the classical result about batching from bounded variance to bounded $\\alpha$-th moment case. This results in Lemma 9 that is interesting on its own. To the best of our knowledge, the previous result of this type is Lemma 7 from [1] that has an extra factor of $d^{1-\\frac{\\alpha}{2}}$, where $d$ is the dimension of the problem. For huge-scale problems, this factor can be large even for $\\alpha \\approx 3/2$. In contrast, our Lemma 9 is dimension-independent.\n\n[1] Wang et al. Convergence rates of stochastic gradient descent under infinite noise variance. NeurIPS 2021.\n\n>**In which cases we should utilize the proposed accelaerated zeroth-order method for non-smooth stochastic convex optimization problems with infinite variance?**\n\n\nWe refer to our general comment to the reviewers (see the section with motivating examples).\n\n>**It is not very clear to me why the paper considers the case when \\delta = 0 on page 6. Could you please elaborate more on that?**\n\n\nWe thank the reviewer for spotting this typo. We will fix it in the final version. We focus mostly on the case of $\\Delta = 0$ to make the proofs simpler and more readable. The proofs for the case of $\\Delta > 0$ follow similar steps and require just accurate calculations. In particular, the additive noise creates extra non-stochastic bias terms in the sums like (12). Since the noise $\\delta(x)$ is bounded, these bias terms can be upper-bounded by induction using the same technique as in the proof for the case $\\Delta = 0$ (the idea is described in lines 232-244). We will add these details to the final version.\n\n>**Could you please list some instances where non-smooth stochastic convex optimization problems show up and why we should be interested in them?**\n\n\nStochastic non-smooth convex optimization problems arise in machine learning (population risk minimization) and statistical application (e.g., likelihood maximization).  We can list SVM or ReLU activation functions in deep learning problems. See also our general response for motivating examples."}, {"review_id": "vyQ6xZP42m", "reviewer": "Reviewer_zmkR", "summary": "This paper proposes a novel gradient-free (zeroth-order) clipped version of stochastic similar triangles method for solving non-smooth stochastic convex optimization problem under a much weaker infinite variance assumption. The derived iteration and oracle complexity bounds are optimal in both convex and strongly convex case.", "questions": "Line 118: Should the upper bound of the second inequality be a notation $\\sigma_B^{\\alpha}$?", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The problem addressed in this paper is well-motivated, the write-up is easy to follow, and the novelty and contribution are easy to identify.", "weaknesses": "1. While the paper is a valuable theoretical contribution, the addition of experimental results would enhance the overall work by demonstrating the feasibility and effectiveness of this method in practical applications.\n\n2. The absence of a Conclusion section or any definitive end to the work makes it feel like a work in progress.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**While the paper is a valuable theoretical contribution, the addition of experimental results would enhance the overall work by demonstrating the feasibility and effectiveness of this method in practical applications.**\n\nThank you for the suggestion. Please, see our general response to all reviewers where we provided the results of numerical experiments and also describe them.\n\n>**The absence of a Conclusion section or any definitive end to the work makes it feel like a work in progress.**\n\nThank you for the suggestion. We will add a conclusion section that will summarize our work, briefly list our contributions and reveal possible directions for further research.\n\n\n>**Line 118: Should the upper bound of the second inequality be a notation $\\sigma_B^\\alpha$**\n\n\nThank you for the question. We do not need to introduce $\\sigma_B$ since its value is explicitly written in the third formula in Lemma 3. We will remove $\\sigma_B$ in the final version.\n"}]

Author rebuttal:
We thank the reviewers for their valuable feedback and time. In particular, we appreciate that the reviewers acknowledged the following strengths of our work: a well-motivated problem, an algorithm with tight and valid theoretical bounds, an important contribution, and a good write-up and organization.

The reviewers also have several questions and concerns that we address in our responses to each reviewer.

In this general comment, we respond to the common reviewers’ comments and concerns.

## Motivation examples

In machine learning, the interest in gradient-free methods is mainly driven by the bandit optimization problem [1,2]. The vast majority of authors assume sub-Gaussian distribution of rewards. However, in some practical cases (e.g., in finance [3]) rewards distribution has heavy tails or can be adversarial. For the heavy-tailed bandit optimization, we refer to [4].
Moreover, in many applications of medicine, biologics, physics, etc., the objective function is only computable through numerical simulation or the result of a real experiment, i.e., automatic differentiation cannot be employed to calculate function derivatives.  Usually, a black-box function we are optimizing is affected by stochastic or computational noise. This noise can arise naturally from modeling randomness within a simulation or by computer discretization. The classical setting assumes this noise to have light tails. However, usually, in black-box optimization, we know nothing about the function, only its values at requested points are available/computable, so any assumptions about noise may not be fulfilled. And if so, gradient-free algorithms may diverge. We aim to construct an algorithm that is robust even to heavy-tailed noise that does not have finite variance. In theory, one can consider heavy-tailed noise to model a situation when noticeable outliers may occur in practice (even if the nature of these outliers is non-stochastic). That is why we relax classical assumptions about finite variance and consider less burdensome assumptions of finite $\alpha$-th moment. 

## Numerical experiments

Following the reviewers’ requests, we conducted numerical experiments with the proposed method. We consider the following convex non-smooth problem: $\min_{x\in \mathbb{R}^{16}}f(x)$, where $f(x) = \frac{1}{500}\|\| Ax - b \|\|_1$ for some matrix $A \in \mathbb{R}^{500 \times 16}$ and vector $b \in \mathbb{R}^{500}$. The stochastic noise is introduced as follows: $f(x,\xi) = f(x) + \langle \xi, x \rangle$, where $\xi$ is a random vector having independent components sampled from the symmetric Levy $\alpha$-stable distribution with $\alpha = 3/2$. This problem satisfies Assumption 1 with $\mu = 0$ and Assumption 2 with $\alpha = 3/2$ and $M_2(\xi) = \|\|A\|\|_1 + \|\| \xi \|\|_2$. We notice that $\mathbb{E}[M_2(\xi)^\alpha]$ is bounded while $\mathbb{E}[M_2(\xi)^2] = +\infty$ due to the choice of $\xi$.

The existing SOTA zeroth-order methods do not use clipping. They are also obtained from the first-order methods using the smoothing technique and two-point feedback oracle. We call the methods obtained this way from SGD and SSTM as ZO-SGD and ZO-SSTM, respectively, and compare them with our method (ZO-clipped-SSTM). The results of the experiments are provided in the PDF attached to the response. As expected, the methods with clipping fail to converge due to the heavy tails in the distribution of the noise, while ZO-clipped-SSTM converges even in such a setup. This numerical experiment illustrates the necessity of clipping (or other non-linear transformations) in zeroth-order methods for handling heavy-tailed noise.

If the reviewers have further questions/concerns/comments, we will be happy to participate in the discussion.

---
References:

[1]  Flaxman, A. D., Kalai, A. T., & McMahan, H. B. (2004). Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007.

[2]  Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1), 1-122.

[3]  S.T Rachev: Handbook of Heavy Tailed Distributions in Finance: Handbooks in Finance, Book 1. Elsevier, North Holland (2003)

[4] Dorn, Y., Nikita, K., Kutuzov, N., Nazin, A., Gorbunov, E., & Gasnikov, A. (2023). Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits. arXiv preprint arXiv:2305.06743.

Meta-review: Overview: This paper presented derivative-free methods for the optimization of stochastic convex functions with a potentially infinite variance noise. Here the level of noise is defined in terms of the boundedness of modulus of a Hölder-type continuous condition. The main technique is to adopt a gradient clipping to the two-point estimation of the gradient of the randomized smoothed function. For some of their results, they also claim the attained bounds are rate optimal. The presentation and organization is of very clear and relatively easy to follow.

Pros:

- Instead of listing, the positive points are mostly within all the reviews included in the reviewing process. Interesting Problem Setting, theory of 
Convergence Rates,  Thorough literature review 

Cons: 

- Only disadvantage the lack of a motivating example, that was handled during the discussion.

Overall: Based on the initial reviews + discussion with the authors, the paper has only positive comments, and all the comments raised by the reviewers were adequately tackled by the authors.

The only requirement for the authors is to include (if possible and if space allows) any additional discussion that is useful during the rebuttal phase, in order to improve the paper. Please do not include material that is not presented during the rebuttal and material that cannot be checked, unless another round of review is required.
Decision: Accept (poster)