A gradient estimator via L1-randomization for online zero-order optimization with two point feedback
Authors: Arya Akhavan
Evgenii E Chzhen
Massimiliano Pontil
Alexandre Tsybakov
Venue: NeurIPS 2022 Accept (2022)
Keywords: zero-order optimization
online learning

Abstract: This work studies online zero-order optimization of convex and Lipschitz functions. We present  a novel gradient estimator based on two function evaluations and randomization on the $\ell_1$-sphere. Considering different geometries of feasible sets and Lipschitz assumptions we analyse online dual averaging algorithm with our estimator in place of the usual gradient. We consider two types of  assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem. In the case of canceling noise that was previously studied in the literature, our guarantees are either comparable or better than state-of-the-art bounds obtained by~\citet{duchi2015} and \citet{Shamir17} for non-adaptive algorithms. Our analysis is based on deriving a new weighted Poincaré type inequality for the uniform measure on the $\ell_1$-sphere with explicit constants, which may be of independent interest.

A gradient estimator via L1-randomization for online zero-order optimization with two point feedback
Arya Akhavan Istituto Italiano di Tecnologia CREST, ENSAE, IP Paris
Evgenii Chzhen Université Paris-Saclay, CNRS Laboratoire de mathématiques O'Osyy evgenii. wwwhehhcnss.....mmoo fr
Massimiliano Pontil
Alexandre B. Tsybakov CREST, ENSAE, Paris
Istituto Italiano di Tecnologia University College London massimi liano. pont ias.simiii......tiiieiii.....
fr
Abstract
This work studies online zero-order optimization of convex and Lipschitz functions. We present a novel gradient estimator based on two function evaluations and randomization on the sppeee.. Considering different geometries of fcasible sets and Lipschitz assumptions we analyse online dual averaging algorithm with our estimator in place of the usual gradient. We consider types of assumptions on the noise of the zero-order oracle: canceling noise and adversarial noise. We provide anytime and completely data-driven algorithm, which is adaptive all parameters of the problem. In the case of canceling noise that was previously studied in the literature, our guarantees of fi-the-art art bounds obtained by Duchi et al. [14] and Shamir [33] for non-adan -daative algorithms. Our analysis is based on deriving new weighted Poincaré type inequality for the uniform measure on the & fi-sphere with explicit constants, which may be of independent interest.
either comparable better than state-
Introduction
In this work we study the problem of convex online zero-order optimization with two-point feedback, in which adversary fixes sequence f1. f2....: : Rd - of convex functions and the goal of the learner is to minimize the cumulative regret with respect to the best action in prescribed convex set C Rd. This problem has received significant attention in the context of continuous bandits and online optimization [see e.g., 1, 3, 12, 13, 16, 18, 21, 25, 29, 33, and references therein].
We consider the following protocol: each round ... the algorithm chooses a a. E IRd (that can be queried outside of +) and the adversary reveals
...
fix)) + E
and
f((a²) +
where E R are the noise variables (random or not) specified. Based on the above information and the previous rounds, the learner outputs a, E θ and suffers loss fe(z)). The goal of the learner is to minimize the cumulative regret
T
T
(..))
min Σ f((x) 2E6
1=1
At the core our approach a novel zero-order gradient estimator based on two function evaluations outlined in Algorithm A key novelty of our estimator is that it employs randomization step
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Algorithm 1: Zero-Order E--Randomized Online Dual Averaging
Input: Convex function V(.), step size 7n > 0, and parameters hG, for = 1, ..... Initialization: Generate independently vectors S1 S2,... uniformly distributed on 0B and set
21 for l....: do
2t = arg max {m (Ze, a²
((=)}
y/ = fi(æt + (t) + & and ye = fi(æ; hoo)) + E/¹ d
// Query // li l-graddeet estimate // Update 2n
9. 2h. (v/ v/")) sig
Zt+1 2t 9:
update the step-size 1)++1
end
the 1 sphere. This is in contrast to most of the prior work [see e.g.. 3-3-5, 14, 16, 17, 22, 28, 32] that was employing l2 or fee type randomizations to define x. We use the proposed estimator within an online dual averaging procedure to tackle the zero-order online convex optimization problem, matching or improving the state-of-the-ar results. Duchi al. [14] and Shamir [33] have studied instances of the above problem under the assumption that & = C which we will further refer to as canceling noise assumption. Specifically, [14] considered the stochastic optimization framework where ft = f. for every t, and obtained bounds on the optimization error rather than on cumulative regret, while [33] analyzed the case & = " = O. The results in [14, 33] are obtained for the objective and 2, although, with extra
functions that are Lipschitz with respect to the nnorrmm for derivations possible to extend the above mentioned results beyond such cases. The proposed method allows to improve upon these results in several aspects.
Contributions. The contributions of the present paper can be summarized as follows. We present a new randomized zero-order gradient estimator and study its statistical properties, both under canceling noise and under adversarial noise (see Lemma and Lemma 4); 2) the canceling noise case (g: = 4 in Theorem 1 we show that dual averaging based on our gradient estimator either improves or matches the state-of-the- thetheeearr art bounds [14, 33]. We derive the results for Lipschitz functions with respect to all -norms, E [1, oo]. In particular, when g 1 and θ is the probability simplex, bound is better by / Vlog(d d) factor than that of [14, 33]; 3) We propose completely data-driven and anytime version of the algorithm, which is adaptive to all parameters of the problem. We show that it achieves analogous performance as the non-adaptive algorithm in the case of canceling noise and only slightly worse performance under adversarial noise. To the best of our knowledge, no adaptive algorithms were developed for zero-order online problems in our setting far; 4) As key element of our analysis, we derive in Lemma 3 a weighted Poincaré type inequality [following the terminology of 10] with explicit constants for the uniform measure on f E1-speer. This result may be of independent interest.
Notation. Throughout the paper we use the following notation. We denote by I1-1lp the f--norm in Rd. For any æ E Rd we denote by x + sign(x) the component-wist wise sign function (defined at 0 as 1). We let ( the standard inner product in Rdd For p E [1, oo] we introduce the open l- bp-ball and lp -ppher respectively as
B f EERE |1=1, <1 and AB - f |=11--1/
For two a, b E R, we denote by A b (resp. V b) the minimum (resp. the maximum) between and We denote by I (0, xo) + R, the gamma function. In what follows, log always stands for the natural logarithm and is Euler's number.
2 The algorithm
Let è be closed convex subset of Rd and let V : - R be a convex function. The procedure that propose in this paper is summarized in Algorithm 1.
Intuition behind the gradient estimate. The form of gradient estimator 9, in Algorithm is explained by Stokes' theorem (see Theorem 5 in the appendix and the discussion that follows).

---

Stokes' theorem provides connection between the gradient of function f (first order information) and f itself (zero order information). Under some regularity conditions, establishes that
J. f((x) dx = f(z))(())
where 0D is the boundary of D, n is the outward normal vector to 0D, and (5()) denotes the surface measure. Introducing U and ς distributed uniformly on D and 0D respectively,
rewrite the above identity as
[[V]( Vold-1(0D) Elf(5 (n(()) VDla(D)
where Volg-1(0D) is the surface area of and Vola(D) is its volume. In what follows we consider the special case Br. For this choice of D we have n(x) v sign(æ) with Volz-1(0D)/ VD) 2/2 leading to our gradient estimate for the two-point feedback setup.
Computational aspects. Let us highlight two appealing practical features of the é fi-randomized gradient estimator g, in Algorithm 1. First, can easily evaluate any fp-norm of 9r- Indeed, it holds that llg.llp (d (d++1///2hy (o24)l8/4 3/ i.c. computing || ll only requires ((1) elementary operations. Second, this gradient estimator is very economic in terms of the required memory: in order to store 9, we only need bits and float. None of these properties is inherent the popular alternatives based on the randomization over the f2-sphere [see e.g., 5, 16, 22] or on Gaussian randomization [see e.g., 19, 23, 24].
To compute 9, one needs to generate S, distributed uniformly 8 The most straightforward way to it consists in first generating a dddimeensionl vector of i.i.d. centered scaled Laplace random variables and then normalizing this vector by its f--orm. The result is guaranteed to follow the uniform distribution on J [see c.g., 30, Lemma 1]. Furthermore, to sample from the centered scaled Laplace distribution
simply use inverse transform sampling. Indeed, if U is distributed uniformly on (0, 1), then 1og(2U)1((L 1/2) log(2 2U 2 1/2) follows centered scaled Laplace distribution.
3 Assumptions
We say that the convex function (-) is 1-strongly convex with respect to the fo-norm on θ
V(x') 2 V(x) (z== + (w, x' - x) + ++11====0 x 1|
2
for all x, x' E θ and all w E (v)),, where (x: ) is the subdifferential of V at point æ.
Throughout the paper, we assume that p.q E [o]. d 2 3, and set p", q" E [o] such that and
+ p"
=1 with the usual convention 1/oc = O. We will use the following
assumptions.
Assumption 1. The following conditions hold:
1. The set θ C Rd is compact and convex.
2. There exists V O > R, which is lower semi-continuos, 1 1-strongly convex on O w.r. the en-norm and such that
sup V(x) - inf V(x) < R²
for some constant R >>>
3. Each function fc RRd + convex on Rd for all 2 1.
4. For all x' E Rd, and all t 2 we have (f((x) f((=') S L| x' x'l1 for some constant
L >>>
Assumption is rather standard in the study of dual averaging type algorithms and have been previously considered in the context of zero-order problems [14, 33]. assume that θ is compact as we are interested in the worst-case regret, which ensures that R < +oc. We discuss extensions of our results to the case of unbounded θ in Section 8. Note that the constant dimension independent. Below provide two classical examples of V [see e.g., 31, Section 2).
not necessarily

---

Example 1. Let θ be any comvex subset of Rd and E (1,2). Then, V(x) 1-strongly convex θ w.r.f. the f--norm.
2(p-1) ||=|| is
1
Example 2. Lef θ = {ir E R ||=||| = 1, x: 2 03. Then', V(x) Σj= Ri log(rz) is 1- strongly convex on w.r.t. the fn-or and R² log(d).
Assumptions on the noise. We consider two different assumptions on the noises E St' The first noise assumption common in the stochastic optimization context [see e.g., 14, 19, 23, 24, 33].
Assumption (Canceling noise). For all = -,2..... holds that E = EL almost surely.
Formally, Assumption 2 permits noisy evaluations function values. However, due to the fact that we are allowed to query ft two points, taking difference of y/ and y/" in the estimator of the gradient effectively erases the noise. It results in a smaller variance of our gradient estimator, Importantly, Assumption 2 covers the case of no noise, that is, the classical online optimization setting defined, e.g., in [31].
Second, we consider an adversarial noise assumption, which is essentially equivalent to the assump- tions used [3, 4].
Assumption 3 (Adversarial noise). For all = 1.2...., holds that: (i) E((()) S o² and { - o2: (ii) (E))21 and (Ef) are independent of (Sz)121
Assumption 3 allows for stochastic & and E" that are not necessarily zero-mean or independent over the trajectory. Furthermore, it permits bounded non-stochastic adversarial noises. Part (ii) of Assumption 3 is always satisfied. Indeed, 4/ and g are coming from the environment and are unknown the learner while č 's are artificially generated by the learner. We mention part (ii) only for formal mathematical rigor.
Note that, since the choice of function V belongs to the learner and θ is given, it is always reasonable to assume that parameter R is known. At the same time, parameters and may be either known or unknown. We will study both cases in the next sections.
Upper bounds on the regret
In this section, we present the main convergence results for Algorithm I when L, a, are known to the learner. The case when they are unknown is analyzed in Section 5, where we develop fully adaptive versions of Algorithm
To state our results a unified way, we introduce the following sequence that depends on the dimension and on the norm index g 1:
qdt (elo(d))
if q E (og))(()),
(d) A d+1
if q 2 log(d).
The value (d) will explicitly influence the choice of the step size > 0 and of the discretization parameter h > 0.
The first result of this section establishes the convergence guarantees under the canceling noise assumption. This case was previously considered by Duchi al. [14] and Shamir [33].
Theorem 1. Let Assumptions and be satisfied. Then, Algorithm I with the parameters
AR L
d
7R
11 =
and any h.
T
100b,(d) (d)
where A = (V6 + V12)
-1 satisfies, for any x E θ
E
Σ (J.( - S((zr)
11.9. RLY Ta 1
'We use the convention that 0 log(0) = 0.

---

Note that, as in other related works [14, 20, 23, 24, 33], under the canceling noise (or no noise) assumption the discretization parameter that, under the canceling noise assumption, the variance of the gradient estimate 9; is bounded by constant independent of It no longer the case under the adversarial noise assumption exhibited in the next theorem.
can be chosen arbitrary small. This is due to the fact
Theorem 2. Let Assumptions and be satisfied. Then Algoritium 1 with the parameters
R
[bb(d) /2R
<2Rr Lbg(d)
Td +
and h =
T ldd
VTL
where A = 661+ 2)). satisfies. for any a E θ
E
Σ
(fe(z)) f(((z)
$ 11.9 RL Ta कां
V Vidl+!-3
if log(d),
+ 2.4 V...VRIE VRLOT
elog(d)d*
if 2 log(d).
Comparison state-of-the-art bounds. We provide two examples p, q, and compare results for our method to those of [14, 33] where only the canceling noise Assumption 2 and q {1,2] were considered.
Corollary 1.
Let p = q = and Bd.. Then under Assumption 2, Algorithm with V O
defined in Example I, satisfies
E
Σ (f((z)) f(()))
< 11.9 LVTT
In the setup of Corollary 1, Duchi et al. [14] obtain OLLv d' log(d) rate and Shamir [33] ex- hibits OLLv d')), which is the optimal rate. Both results do not specify the leading absolute constants.
Corollary 2. Let p = q =1 and @ for E Rd a 222 0. || 1}. Then under Assumption Algorithm / with V θ - R defined in Example 2, satisfies
E
- - 11.9- ddd log(d)
In the setup of Corollary 2, Shamir [33] proves the rate O(Lv d7 log(d)) for the method with lz- randomization. On the other hand, Duchi et al. [14] derived a lower bound O dT' log(d)). Thus, our algorithm further reduces the gap between the upper and the lower bounds.
Finally, note that in the case = 1, = 2 with of Theorem is of the order O ((vTlog(d)) This case was handled by an algorithm with 41- randomization slightly different from ours in [18] leading the suboptimal rate Olv dT log(d)).
e + R defined in Example 2 the bound
5 Adaptive algorithms
Theorems and 2 used the step size and the discretization parameter h that depend on the potentially unknown quantities L, a, and the optimization horizon canceling noise Assumption 2, adaptation to unknown L comes with nearly no price. On the other hand, under the adversarial noise Assumption 3, our adaptive rate has slightly worse dependence on L and a in the dominant term. The proof is based on combining the adaptive scheme for online dual averaging [see Section 7.13 in 26, for an overview] with our bias and variance evaluations, cf. Section 6 below.
this section, we show that, under the
5

---

Theorem 3. Let Assumptions and be satisfied. Then, Algorithm I with the parameters
7R
1/ V2.75 Σx=1 1
and any h4 S 200b, (d)vt
satisfies for any +
T (f((x))
< 110.6 RLV Td gez
The above result gives, up an absolute constant, the same convergence rate as that of the non- adaptive Theorem 1. In other words, the price for adaptive algorithm does not depend on the parameters of the problem. Finally, we derive an adaptive algorithm under Assumption 3. Theorem 4. Let Assumptions and be satisfied. Then, Algorithm I with the parameters
R
and any h4 (6.65V6
R
t t-
T/
by(d)
V 1275 Ei 1
satisfies for any x E
E
Σ (J((z)) - (((o))
< 110.6. RLV T wnz
Vadl+++
if E [1, log(d))
5.9 vR(O+L)TH.
e eelo(d)dd
if 2 log(d)
Note that the bound of Theorem 4 has a less advantageous dependency on a and L compared to Theorem 2, where we had VoL instead of a + L. We remark that if known but L is unknown, one recover the V dependency by selecting fú, depending σ.. We do not state this result that can be derived in a similar way and favor here only the fully adaptive version.
Elements of proofs
In this section, we outline major ingredients for the proofs of Theorems 1 1-4, The full proofs can be found in Appendix C. Here, we only focus on novel elements without reproducing the general scheme of online dual averaging analysis [sec e.g., 26, 31]. Namely, highlight two key facts, which are the smoothing lemma (Lemma 1) and the weighted Poincaré type inequality for the uniform measure on @Bf (Lemma 3) used to control the variance.
6.1 Bias and smoothing lemma
First, as in the prior work that was using smoothing ideas [see e.g., 16, 22, 33], we show that our gradient estimate is an unbiased estimator of a surrogate version of fo and establish its approximation properties.
Lemma 1 (Smoothing lemma). Fix h > 0 and E [L, [o). Let f. Rd + R be an L-Lipschitz function w.r.t. the fy-norm. Let U be distributed uniformly on Bi and Ç be distributed uniformly on } Let (x) Elf(x + for E R... Then fn is differentiable and
E
d
(f(x
h() f(x -h)) sign(() (f,(2))
2h
Furthermore, we have for all d 2 3 and all E Rd
(z) f(x)] < by (d)
(I)
Finally, O Rd is convex, convex @+hB then fr is convex in and (z)) 2 f(x) for E O.
We adopt the convention that and 1/0 1 in the definition of n..

---

Proof. There are three claims to prove. For the first one, we notice that Ç has the same distribution as -c. hence,
E
(J(a 1() f(æ hc)) sign(() E
f(x h J + sign(())
2h
and the first claim follows from Theorem in the Appendix (a version of Stokes', or divergence, theorem) applied to g()) f(æ + h-) with observation that Vg(+) AV f( + h.) where V is the gradient defined almost everywhere and whose existence is ensured by the Rademacher theorem.
We now prove the approximation property (1). Assuming d 2 3 grants that log(d) 2 1. Since f is L-Lipschitz w.r.t. the by -norm we get that, for any æ E Rd.
(xx [(=) - Lh E
(2)
If q E [1, log(d) then (1) follows from Lemma 2. If 2 log(d) then using again Lemma 2 we find
log (og(d) elog(d)
E| = E| U (l)g
I
d+1
+
which together with (2) yields the desired bound.
Finally, if f is convex in θ + hB4 then for all a, x' E θ and a E [0, 1] we have
(ox + (1 a)x²)=====))))) = f (a(x + hU) + (1 - aa + +(U) S (x) + ()=
Thus f, is indeed convex O. Furthermore, again by convexity of f. we deduce that for any E θ
f (x) = Elf(x + hU)] 2 E [f(x) + (w, hU)] = f(x) where w E @f(x).
The proof of Lemma relies on the control of the fg-norm of random vector U established in the next result.
Lemma 2. Let (o) and let U be distributed uniformly Bi. Then E E||u I
gd
d+I
Proof. Let Wi...., Wa, Wd+1 be i..dd random variables having the Laplace distribution with mean and scale parameter Set W (W1...., Wa). Then, following [6. Theorem 1] we have
W
W [Wa1l
where d denotes equality in distribution. Furthermore, [30, Lemma 1] states that the random variables (W, (..Wa+rl)
and are independent. Hence, for any q E oo), it holds that
[ + [Wa+1l
W| 11 + +|Watil
El|W
(a) S
1
r= +1) (0)
gdt
E| U 11, (W Wa+1)llı
d E W
d -
d+1
d+17
where (a) follows from Jensen's 's inequality and (b) uses the fact that [1/( S a for g 2 0
6.2 Variance and weighted Poincaré type inequality
We additionally need to control the squared -n- of each gradient estimator 9:- This is where we get the main improvement of our procedure compared to previously proposed methods. To derive the result, we first establish the following lemma of independent interest, which allows us to control the variance of Lipschitz functions on ØB The proof of this lemma is given in the Appendix.
Lemma 3. Let d 2 3. Assume that G Rd + R is continuously differentiable function, and Ç is distributed uniformly on ÖBC Then
Var(G(()) 2)
4
E
|VGOO)
(1+va(cIa))
Furthermore, G Rd + R an L-Lipschitz,uunie w.r.t. the e tn-norm then
412
2d
Var(G(()) < d(d - 2)
1
7

---

Remark 1. Since d' /d((ddd 2)) - 3 for all d 2 3. the last inequality of Lemma 3 implies that
Var(G(()) & 12(1 + (L/)(
Vd2
(3)
We deduce the following bound the squared lp- -norm of gr- Lemma 4. Let p E [1, oo) and p* p-T- Assume that fa. is L-Lipschitz w.F. the f--norm. Then, for all d 2 3.
under canceling noise Assumption 2,
E 9e l
& 12(1 L2) 502
d
002
under adversarial noise Assumption 3.
112
Proof. Using the definition of 9, get
df
[[f + hC1) f(( - ((.,) +
<M> sign( [x,]
2h2
-
E[(fe(xx + hSg) fe(xx h(,))
< a2.]
4h2
Let G(C) & f((1, + hς)
fz, hC). First, observe that E x; = and under both
Assumption and Assumption 3(i) holds that E(G(C, (E) (2' 2t Using these remarks
and the fact that under adversarial noise Assumption 3, E[(() 2 [t I 4o², we find:
-= 4h2
0
under cancelling noise Assumption 2
E E 12 [x)] S
VVr(GG(s,) æx)
under adversarial noise Assumption 3
Furthermore, since ft is L-Lipschitz, w.r.t. the normm, the map + G(C) is (2Lhd 1)- Lipschitz w.rt. the fn-norm. Applying (3) to bound Var(G((,)) æx), yields the desired result.
Note that under adversarial noise Assumption the bound squared f---norm of 9, gets additional term d2-202h-2 In contrast to the case of canceling noise Assumption 2, this does not allow us take arbitrary small hence inducing the bias-variance trade-off.
7 Numerical illustration
In this section, we provide numerical comparison of our algorithm with the method based on fz-randomization from Shamir [33] (see Appendix for the definition). We consider the no noise model and Se f. Vi, with the function f Rd IR defined as
f(x) = o 2ll₂ + x 0.1 cll
where c = (cI,...,ca) TT) Rd such that cj = exp(i) exp(i) for j I,...,d. We choose
θ = for Rd ||m||| x 2 0} and V(x) = Σ Ii log(a;))
As stated in Example 2, V is 1-strongly convex on θ w.r.t the -nomm and R < Vlg(d) dd) Moreover, is a Lipschitz function w.r.t. the formr. We deploy the adaptive paramcterization that appears in Theorem 3. In Figure we present the optimization error of the algorithms, which is defined as
Σ
x;
min f(x)
The results are reported over 30 trials. We plot all the 30 runs alongside the average performance. One can observe that the fy-randomizttion method behaves significantly better than the zandomizinnn algorithm. The theoretical bound for method in this setup has vlog d gain in the rate.

---

Constraint type: simplex; dimension:
Constraint type: aimplex;
184
fyrrnddmizzaion
prrandomization Esrandomizationn
farddcmmization
05-
Optimization
Optimicationn
0.6
3.3-
094
3.0
150000
170000
133000
175000
Number iterations
Number iterations
Figure 1: Opt. error vs. number of iterations for 42-randomization (as in [33]) and our method.
Discussion and comparison to prior work
We introduced and analyzed novel estimator for the gradient based on randomization the -ispheee. We established guarantees for the online dual averaging algorithm with the gradient replaced by the proposed estimator. We provided an anytime and completely data-driven algorithm, which is adaptive to all parameters of the problem. Our analysis based on deriving a weighted Poincaré type inequality for the uniform measure on the fi-sheere that may be of independent interest. Under the canceling noise assumption and E {1, our setting is analogous to [14, 33]. For the case q = p 2 and canceling noise, we show that the performance of our method is the same as in [33, Corollary 2] up to absolute constants that were not made explicit in [33]. For the case of p = 1 and canceling noise, we improved the bound [33, Corollary 3] by a /log(d) (d) factor. For the case 9 2, p 2 1, comparing with the lower bound in [14, Proposition 11, shows that the result of Theorem is minimax optimal. For the case Theorem 1 optimal up a log(d) factor.
1, [14, Proposition 2] shows that our result
Under the adversarial noise assumption, Theorem 2 provides the rate O(T3/4), that is, we get an additional / factor compared to the canceling noise case. It remains unclear whether it is optimal under adversarial noise this question deserves further investigation. Note that, under sub-Gan Gaussian i.i.d. noise assumption and p 2, one can achieve the rate O(d" /T) with relatively big a > [2, 8, 13, 21]. particular, with an ellipsoid type method [21] obtains the rate O(d4.5.Tloglh ?)) for the cumulative regret.
Finally, let us discuss the compactness of θ. is straightforward to extend the results of Theorems 1, 1,2
to any closed convex ④ considering the regret against fixed action æ E O. Indeed, using [26, Corollary 7.9], one only needs to replace R appearing in both Theorems 1, by upper bound on VV(x) infa'ee V(æ'). The adaptive case is more complicated. One way to tackle this case is to use [27, Theorem 1] requiring control of E mmx [|g 1lp- This term can be controlled under the canceling noise Assumption 2 using the Lipschitzness of fi s. that Theorem 3 extends to unbounded @. However, without the canceling noise assumption, following the approach outlined
- The adversarial noise Assumption 3 is not above, needs to control E max hr sufficient to reasonably control this term, so that extending Theorem 4 unbounded θ is not possible without further assumptions.
Acknowledgments and disclosure of funding
The work of E. Chzhen was supported by ANR PIA funding: ANR-20-IDEES- 0002 The work of M. Pontil is partially supported by European Union's 's Horizon 2020 research and innovation programme under ELISE grant agreement No 951847. The research of A. Akhavan and A. B. Tsybakov is supported by a grant of the French National Research Agency (ANR), "Investissements d' Avenir" (LabEx Ecodec/ANR-11 1--------1--B--047777
References
[1] Agarwal, A., Dekel, O., and Xiao, L. (2010). Optimal algorithms for online convex optimization with multi-point bandit feedback. Proc. 23rd International Conference on Learning Theory, pages 28-40.

---

[2] Agarwal, A., Foster, D. P., Hsu, D. J., Kakade, S. M., and Rakhlin, A. (2011). Stochastic convex optimization with bandit feedback. In Advances in Neural Information Processing Systems, volume 25, pages 1035-1043.
[3] Akhavan, A., Pontil, M., and Tsybakov, A. (2020). Exploiting higher order smoothness in derivative-free optimization and continuous bandits. In Advances in Neural Information Processing Systems, volume 33.
[4] Akhavan, A., Pontil, M., and Tsybakov, A. B. (2021). Distributed zero-order optimization under adversarial noise. In Advances in Neural Information Processing Systems, volume 34.
[5] Bach, F. and Perchet, V. (2016). Highly-smooth zero-th order online optimization. In Proc. 29th Annual Conference on Learning Theory, pages 1-27.
[6] Barthe, F., Guédon, O., Mendelson, S., and Naor, A. (2005). A probabilistic approach to the geometry of the Lpn-ball. The Annals of Probability, 33(2):480- - 513.
[7] Barthe, F. and Wolff, P. (2009). Remarks non-interacting conservative spin systems: the of gamma distributions. Stochastic processes and their applications, 119(8):2711-22
[8] Belloni, A., Liang, T., Narayanan, H., and Rakhlin, A. (2015). Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proc. 28th Annual Conference on Learning Theory, pages 240-265.
[9] Bobkov, S. and Ledoux, M. (1997). Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution. Probability Theory and Related Fields, 107(3):383- 400.
[10] Bobkov, G. and Ledoux, M. (2009). Weighted Poincaré-type inequalities for Cauchy and other convex measures. The Annals of Probability, 37(2):403 - 427.
[11] Boucheron, S., Lugosi, G., and Massart, (2013). Concentration inequalities: nonasymptotic theory of independence. Oxford university press.
[12] Bubeck, S. and Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122
[13] Bubeck, S., Lee, Y. T., and Eldan, R. (2017). Kernel-based methods for bandit convex op- timization. In Proc. 49th Annual ACM SIGACT Symposium Theory of Computing, pages 72-85.
[14] Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. (2015). Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):278--280)
[15] Evans, L. C. and Gariepy, R. F. (2018). Measure theory and fine properties of functions. Routledge.
[16] Flaxman, A. D., Kalai, A. T., and McMahan, H. B. (2005). Online convex optimization in the bandit setting: gradient descent without gradient. In Proc. 16th Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pages 3944
[17] Gasnikov, A., Krymova, E., Lagunovskaya, A., Usmanova, I,, and Fedorenko, F. (2017). Stochastic online optimization. Single-point and multi-point non-linear anmee bandits. Convex and strongly convex case. Automation and Remote Control, 78(2):224-234.
[18] Gasnikov, A., Lagunovskaya, A., Usmanova, I., and Fedorenko, F. (2016). Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex. Automation and Remote Control, 77(1) 1):2018-2033
[19] Ghadimi, S. and Lan, G. (2013). Stochastic first- and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368.
10

---

[20] Hu, X., Prashanth, L. A., György, A., and Szepesvári, C. (2016). Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proc. 10th International Conference on Artificial Intelligence and Statistics, pages 819-828.
[21] Lattimore, T. and Gyorgy, A. (2021). Improved regret for zeroth-order stochastic convex bandits. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134, pages 2938-2964. PMLR.
[22] Nemirovsky, A. and Yudin, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley & Sons.
[23] Nesterov, (2011), Random gradient-free minimization convex functions. Technical Report 201 1001, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain.
[24] Nesterov, Y. and Spokoiny, V. (2017). Random gradient-fre free minimization of convex functions. Found. Comput. Math., 17:527-560 566.
[25] Novitskii, V. and Gasnikov, A. (2021). Improved exploiting higher order smoothness in derivative-free optimization and continuous bandit. arXiv preprin! arXiv:2101.03821.
[26] Orabona, F. (2019). A modern introduction to online learning. ArXiv, abs/1912.13213.
[27] Orabona, F. and Pál, D. (2016). Scale-free online learning. Theoretical Computer Science, 716.
[28] Polyak, T. B. and Tsybakov, A. B. (1990). Optimal order of accuracy of search algorithms in stochastic optimization. Problems of Information Transmission, 26(2):45-53.
[29] Saha, A. and Tewari, A. (2011). Improved regret guarantees for online smooth convex optimiza- tion with bandit feedback. Proc. 14th International Conference on Artificial Intelligence and Statistics, pages 636-642.
[30] Schechtman, and Zinn, J. (1990). On the volume of the intersection of two L balls. Proc. Amer. Math. Soc., 110(1):1172224
[31] Shalev-Shwartz, S. (2012). Online learning and online convex optimization, volume Now Publishers, Inc.
[32] Shamir, O. (2013). On the complexity of bandit and derivative- frree stochastic convex optimiza- tion. In Proc. 30th Annual Conference on Learning Theory, pages 1-22.
[33] Shamir, O. (2017). An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 180)):7003-1733.
[34] Zorich, V. A. (2016). Mathematical analysis II. Springer.
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]
(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]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..

---

(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [Ye]] at https:
/gi thub. com/ evgchz/ Akhavan wwwkhaaa_hhhhhnn_aae Chwhen_Pontiiini Tsyyakov222
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasnng new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'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, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links 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]
12


Reviews:
[{"review_id": "wUWMG_QyZx", "reviewer": "Reviewer_Kfmr", "summary": "This paper studies online optimization problem with zero-order and two-point noisy feedback. The proposed algorithm is based on a randomized gradient estimator with the perturbation for the queried points drawn from an ell-1 sphere, followed by performing online mirror descent update. The authors show an improvement of polylog factors in the regret bound in certain cases compared to previous work, and the assumption can handle Lipschitzness with respect to arbitrary norms. An adaptive version where the parameter choice can be made independent of unknown noise variance, Lipschitz constant is also analyzed and the resulting regret is comparable to the nonadaptive version for the cancelling noise while degrade in the case of adversarial noisy feedback. Numerical experiments are also presented comparing with ell-2 randomization. ", "questions": "- I think there's also the complexity of drawing samples from Gaussian vs. Laplace that need to be taken into consideration perhaps, given that one has smooth/strongly convex potential and the other doesn't.\n- I'm not totally synced with this part of the literature, but in the case when q \\neq {1,2} and under the cancelling noise assumption, are there no known algorithmic rates for this setup (I sense there should be)?\n\n\n===== post author response =====\n\nI thank the authors for addressing my comments and would like to keep my score unchanged.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I believe the result is of interest to the community and the writing is also very clear and well-structured. Most of the technical work is spent on analyzing statistical properties of the newly proposed gradient estimator, which is the main contribution of the paper. It is, perhaps, not a surprising result from an optimization algorithm point of view, but this slight improvement in the regret guarantee and generalization of various degree is a nice addition to the literature.", "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": "Xx28xHIIG0A", "reviewer": "Reviewer_Evju", "summary": "In this paper, the authors propose a gradient estimator (together with an analysis of online mirror descent with it) in the online optimization case where the algorithm gets to query--maybe with noise--the function at two distinct points. As in previous work, they build this estimator based on the gradients of the functions \"smoothed by randomness\". Their key contribution, however, is to smooth the function using noise distributed in the $\\ell_1$-ball. In order to analyze the performance of this estimators they show how far the smoothed function may be from the actual function, and show a inequality (in the style of Poincaré's inequality) to bound the variance of their estimator. Finally, they show regret bounds both in cases with \"simple\" and \"adversarial\" noise, showing that it either matches or improves on previous work.", "questions": "- Why do you need to have $\\Theta$ bounded?\n- Algorithm 1 seems to be a dual averaging (or \"lazy\" mirror descent) algorithm. But in this type of algorithms usually we see the same step-size being applied to all the gradients at each step (that is, we would have $z_t = - \\eta_t \\sum_{s < t } g_s $ instead of $z_t = - \\sum_{s < t } \\eta_s g_s$ like what you do). I was curious if you've considered using the latter, which usually behaves better (more specifically, behaves better with the $\\max_x V(x) - \\min_y V(y)$ term) when you have adaptive step-sizes.", "limitations": "My guess is that the main technical impediment of this work is the dependency on a bounded set. The authors were also somewhat upfront about the $O(T^{3/4})$ and has a discussion whether this should be the right upper-bound or not, which is great.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n- The result is elegant and flexible, yielding already improved regret bounds and allowing for the analysis of regret bounds with quite loose assumptions on the noise;\n- The Poincaré-style inequality can be a tool of independent interest for the community (as the authors mention);\n- The regret analysis are clean enough for all the constants to be clearly written in the bound, which apparently was not the case with previous bounds;\n- The presentation of the technical part is good (focusing on the key technical innovations) and seems sound to me.\n### Weaknesses\n- I know that part of this is due to space limitations, but I felt the previous/related work was poorly discussed. I am not very acquainted with the latest developments on zeroth-order (online?) optimization. Just based on the paper itself I could not get a satisfying picture to properly place the paper's contribution in the literature. I had to read the introductions/related work sections of [13] and [31] to get a better picture, which is not ideal. It makes me unsure as well, for example, if really no other work has studied adaptive optimization algorithms for zeroth-order optimization.\n- I was (and still am) puzzled that the authors need $\\Theta$ to be bounded, and they do not discuss why they need this in the paper. This is a clear weakness and, just from the main body of the paper, does not seem to be due the gradient estimator they use.\n- (Minor) The use of references is also not good, and is related to the lack of a good discussion of related work. A list of 10 papers without any context does not help readers that are not aware of the latest work in the topic and can annoy the authors of the papers you cite.\n\n\n### Summary \nI think the paper is very solid and clearly deserves to be accepted. I'm not extremely familiar with the landscape in 0th-order optimization, but this feels to be potentially very impactful. Depending on the rebuttal phase and the discussion with authors and other reviewers I might increase my score.\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": "MZorJoa_zCv", "reviewer": "Reviewer_ewZu", "summary": "This paper propose a new method to estimate the gradient via a zeroth-order oracle, which is especially effective in the L1 geometry. With this new estimator, this paper studies the the online zeroth-oder convex optimization under both canceling noise and adversarial noise, and also study the adaptive version of the algorithm under this setting.", "questions": "This work reminds me the paper \"SIGNSGD VIA ZEROTH-ORDER ORACLE\" https://openreview.net/pdf?id=BJe-DsC5Fm, which also use a sign opeartion for the sampled direction. But, of course, their convergence result is clearly worse than the one proposed by this work, because sign operation is not suitable for L2 gradient estimator.", "limitations": "It seems to me that there is no clear limitation in this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The main contribution of this paper is to propose a new zeroth oracle gradient estimation method in the L1 geometry, which enjoys a few good properties like (1) it is theoretically better than the commonly used L2 gradient estimator expecially in the mirror descent on a simplex, which is a classical problem with L1 geometry. (2) It is computationally friendly since it only need to store a binary valued vector. From my viewpoint, this paper is very novel, and it is an easy accept for me.", "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": {}}]

Author rebuttal:

Decision: Accept