Distributed Zero-Order Optimization under Adversarial Noise
Authors: Arya Akhavan
Massimiliano Pontil
Alexandre B Tsybakov
Venue: NeurIPS 2021 Poster (2021)
Keywords: Zero-order optimization
statistical learning theory
online learning

Abstract: We study the problem of distributed zero-order optimization for a class of strongly convex functions. They are formed by the average of local objectives, associated to different nodes in a prescribed network. We propose a distributed zero-order projected gradient descent algorithm to solve the problem. Exchange of information within the network is permitted only between neighbouring nodes. An important feature of our procedure is that it can query only function values, subject to a general noise model, that does not require zero mean or independent errors.  We derive upper bounds for the average cumulative regret and optimization error of the algorithm  which highlight the role played by a network connectivity parameter, the number of variables, the noise level, the strong convexity parameter, and smoothness properties of the local objectives. The bounds indicate some key improvements of our method over the state-of-the-art, both in the distributed and standard zero-order optimization settings.

Distributed Zero-Order Optimization under Adversarial Noise
Arya Akhavan CSML, Istituto Italiano di Tecnologia and
Massimiliano Pontil CSML, Istituto Italiano di Tecnologia and
CREST, ENSAE, IP Paris
University College London
aria. arriaaahhhaaafooonniiitt...
massimiliano. pont
Alexandre B. Tsybakov CREST, ENSAE, IP Paris
alexandre. hwwaaandde.tsyyaako/eeeesss
Abstract
We study the problem of distributed zero-order optimization for class strongly convex functions. They are formed by the average of local objectives, associated to different nodes a prescribed network. We propose a distributed zero-order projected gradient descent algorithm to solve the problem. Exchange of information within the network is permitted only between neighbouring nodes. An important feature of our procedure is that it can query only function values, subject to general noise model, that does not require zero mean or independent errors. We derive upper bounds for the average cumulative regret and optimization error of the algorithm which highlight the role played by a network connectivity parameter, the number of variables, the noise level, the strong convexity parameter, and smoothness properties of the local objectives. The bounds indicate some key improvements of our method over the state-of-the-arr, both in the distributed and standard zero-order optimization settings. We also comment on lower bounds and observe that the dependency over certain function parameters in the bound is nearly optimal.
Introduction
We study the problem of distributed optimization where each node (or agent) has objective function fi Rd + and exchange information is limited between neighhouring agents within prescribed network of connections. The goal is minimize the average of these objectives closed bounded
convex set θ C Rd.
min f(x) #
where f(x)
fz(z). +=1
(1)
Distributed optimization has been widely studied in the literature, we refer to Tsitsiklis et al. [1886]
Nedic and Ozdaglar [2009]. Nedic al. (2010), [Boyd et al. [20IT) Duchi et al. [2012], Jakovetić et al.)
2014]] Lobel et al. 2011]. Kia et al. 22055] Shi et al. 2014]. Jakovetic 2019 Scaman et al. [2019]
Pu et al. 2021 1 and references therein. This problem has broad applications such as multi-agent
target seeking Liu et al. (2017), distributed learning Kraska et al. (013)) and wireless networks Park al. 2020), among others.
We address problem ( from the perspective of zero-order distributed optimization. That is we assume that only function values can be queried by the algorithm, subject measurement noise.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

During the optimization procedure, each agent maintains a local copy of the variables which are sequentially updated based on local and neighboring functions' queries. We wish to devise such optimization procedures which are efficient in bounding the average optimization ervor and cumulative regret in terms of the functions' properties and network topology.
Contributions Our principal contribution is a distributed zero-order optimization algorithm, intro- duced in Section 2 which we show to achieve tight rates of convergence under certain assumptions on the objective functions, outlined in Section 3 Specifically, we consider that the local objectives fi are 3-Hölder and the average objective f is a-strongly convex. The algorithm relies on a novel zero-order gradient estimator, presented in Section 4 Although conceptually very simple, this estimator, when employed within our algorithm, allows us to obtain an O(d²) computational gain as well as improved error rates than previous state-of-the tet-hhe-rtt art cero-order optimization procedures Akhavan et al. (2020).
Bach and Perchet (2016), in the special case of standard (undistributed) setting. Another key advantage of our approach is due to the general noise model presented in Section 5 under which
function values are queried. The noise variables do not need to be zero mean or independently
sampled, and thus they include "adversarial" noise. In Section 6 we derive the rates of convergence for the cumulative regret and the optimization error of the proposed algorithm, and in Section 7 we consider the special case of 2-smooth functions. The rates highlight the dependency with respect to the number of variables d, the number of function queries T, the spectral gap of the network matrix 1 p. and the parameters n, and B. The bounds enjoy better dependency on 1 - p than previous bounds on zero-order distributed optimization Qu and Li (2018), Yu et al. [2019). Tang et al. [2019]. We also compare bounds to related lower bounds in Akhavan et al. [2020] for undistributed setting, observing that our rates are optimal either with respect to 7 and o or with respect to T and d.
Previous Work We briefly comment on previous related work and defer to Section foor a more in depth discussion and comparison. For both deterministic and stochastic scenarios of problem (I).
large body of literature is devoted to first-order gradient based methods with a consensus scheme (see the papers cited above and references therein). On the other hand, the study of zero-order methods
was started only recently Qu and Li [2018), Sahu et al. [2018b a Hajinezhad et al. [2019].
). Yu et al.
(2019). Tang et al. [019]. The works Qu and Li [2018), Yu et al. [2019). Tang al. [2019] dealing with zero-order distributed methods in noise-Iree settings while the noisy setting is developed in Hajinezhad et al. [019], (ahu et al. [018b Namely, HHjinezhad al. [0199] considers 2-point zero-order methods with stochastic queries for non-convex optimization but assume that the noise is the same for both queries, which makes the problem analogous to noise-free scenario in terms of optimization rates. Papers|Sall et al. [2018b a study zero-order distributed optimization for strongly convex and f-smooth functions Sü with 3 E 3). They derive bounds on the optimization error, though without providing closed form expressions.
Notation Throughout we denote by (..-) and ||. be the standard inner product and Euclidean norm on Rd, respectively, and by || ||- the spectral norm of a matrix. The notation I is used for the n n-dimensional identity matrix and for the vector IR with all entries equal to 1. We denote by ej
the j-th canonical basis vector in Rd. For any set A, the number of elements in A is denoted by |A]. For x E I. the value [x] is the maximal integer less than x. For every closed convex set ② Rd and IRd we denote by (x:) argmin(ll= z||| E Q) the Euclidean projection of x onto e. We denote by diam ()) the Euclidean diameter of e. Finally we let U1-1,11 be the uniform distribution on 11.
2
The Problem
Let ni be the number of agents and let g = (V, be an undirected graph, where V (1,....,)) n} is the set of nodes and E C V x V is the set of edges. The adjacency matrix of G is the symmetric matrix (A defined as A,j = 1, ji E E and zero otherwise. We consider the following sequential learning framework, where each agent gets values of function fi corrupted by noise and shares information with other agents. At step t, agent acts as follows:
makes queries and gets noisy values of fu,
provides local output u² (t) based on these queries and on the past information,
broadcasts w² (1) to neighboring agents,
2

---

Algorithm Distributed Zero-Order Gradient
Input Communication matrix (Wi)),,=n step sizes (T/ > 0)1=1 76-1
Initialization Choose initial vectors x (1) z²(1) E R
For t == ,o
For i .......2
1.
Build an estimate gt) of the gradient (t)( using noisy evaluations of fi
2. Update -1+++))- Ek=1 WroProje (z (1) - (t))
End
End
Output Approximate minimizer (TT)) 1 n Ei=l x' (To) of the average objective n Ei= fo
updates its local variable using information from other agents as follows:
[t++1)==
EWaju
j=1
where W (W (Wa)) is a given matrix called the consensus matrix.
Below the following condition the consensus matrix.
Assumption A. Matrix W is symmetric, doubly stochastic, and p = ||W - n 11 |. <.
Matrix W accounts for the connectivity properties of the network. Wij the agents and are not connected (do not exchange information). Often W is defined as doubly stochastic matrix function of the adjacency matrix of the graph. One popular example is as follows:
if i j.
mAx (d()),()))
Wij
Σ ki
A max (()))
if = j,
1==1 Al is the degree of node and y > 0 is a constant. Then, clearly, W = (Way) is a symmetric and doubly stochastic matrix, and Wi, = 0 if agents and are not connected. Moreover, we have p < 1 e/n² for constant e >> 0 (see Qu and Li 2018). Olshevsky (2014). Values of spectral gaps p for some other W reflecting different network topologies can be found in Duchi et al.) (2012). Typically, & < 1 an, where a, = 22(n or a₂ = Q2n 2). Parameter can be viewed as measure of difference between the distributed problem and standard optimization problem. If the graph of communication a complete graph natural choice is W = n 1, and then 0. For more examples of consensus matrices W, see Olshevsky and Tsitsiklis 2009 Duchi et al. 2012 and references therein.
where d(i) -E
The local outputs u' can be defined in different ways. Our approach is outlined in Algorithm At Step 1, an estimate of the gradient the local objective fa (=((( is constructed. This involves randomized procedure that we describe and justify in Section 4 The local output u is defined as an update of the projected gradient algorithm with such an estimated gradient. At Step 2 of the algorithm, each agent computes the next point by local consensus gradient descent step, which uses local and neighbor information. Step 2 of the algorithm is known as gossip method, see e.g.. Boyd al. (2066)) which was initially introduced connection between the nodes changing by time. We also refer to [Sayin et al. [2017) for similar algorithms in the context of distributed stochastic first-order gradient methods.
approach for the networks with the imposed
3 Assumptions on Local Objectives
In this section, we give some definitions and introduce our assumptions on the local objective functions fi. Definition 1. Denote by Fa(L) the set of all functions Rd R that are E differentiable and satisfy. for all x, Rd the Hölder-type condition
[ times
f(z) - Σ
1 1mTh f(x)(2 x²)m < L||2 - = m!
(2)
05imlse
3

---

Algorithm 2 Gradient Estimator with 2d Queries
Input Function F: Rd R and point E Rd
Requires Kernel K [ 1J + IR, parameter h > 0
Initialization Generate random from uniform distribution on [-1,1] For j =.....,d
1. Obtain noisy values y/ F( + hre,) Ey and v/ F(x hree) ) +,
2. Compute 9, (v) (r))
End
Output g = == E Rd estimator of (z)))
where L > 0, the sum is over the multi-index m (mi...., ma) E No, we used the notation m! = my!- mal |m| = my + .... + m. and we defined, for every v (V),..., 148 E Rd,
a f(x)
D f=x("=)"" 8m1111 ... Ima
1
Elements of the class (L) are referred to as 3-Hölder functions.
Definition 2. Function Rd R is called 2-smooth if is differentiable on Rd and there exists >>0 O such that, for every (x, x') E Rd x RR,, it holds that
[V](() V(('')l S Ll|x x'|l-
Definition 3. Let a > O. Function f: Rd called a-strongly convex if f is differentiable on Rd and
f(x') 2 (Vf(('), x²) Assumption B. Functions fi..... fn: (i) belong to the class FL( for some $ 2 2, and (ii) are 2 2moohh..
x' Vx, x' Rd.
In Section 6 we will analyse the convergence properties of Algorithm 1 when the objective function in [is is d--troogly convex. We stress that we do not need the functions - to be well a-strongly convex. enough to make such an assumption on the compound function f. while the local functions f. only need to satisfy the smoothness conditions stated in Assumption B above.
4 Gradient Estimator
In this section, we detail our choice of gradient estimators g' (1) used at Step of Algorithm We consider Algorithm 2 For any function F : Rd + and any point æ, the vector g returned by Algorithm is estimate of F(x) based noisy observations of F randomized points. The estimator is computed for every node at each step f, thus giving the vectors
g (t) in Algorithm 1 The gradient estimator crucially requires kernel function K [-1, 1] - R that allows to take advantage of possible higher order smoothness properties of f. Specifically, in what follows we assume that
f [u((uddu= 11, / (())du j j 0,2,3, ..., and Ki
[ du oc, (3)
for given 3 > 2 and - [3]. In Polyak and Tsybakov 1990 such kernels can be constructed weighted sums of Legendre polynomials, in which case Kg
2v233 with B > 1; see also
Appendix A.3 in Bach and Perchet (2016) for derivation.
The gradient estimator in Algorithm differs from the standard 2d-point Kiefer- Wolfowitz type estimator that it uses multiplication by random variable (r)) with a well-chosen kernel K. On the other hand, it is also different from the previous kernel- based estimators in zero-order optimization literature Polyak and Tsybakov [1990, [Bach and Perchet (2016), Akhavan et al. 2020 that needs 2d function queries per step, whereas those estimators require only one or two queries; see, in particular, Algorithm 1 in Akhavan et al. [2020) for a comparison. At first sight, this seems big drawback of the estimator proposed here, however we will show below that thanks to this estimator

---

we achieve both more efficient optimization procedure and better rate of convergences for the optimization error.
When the estimator in Algorithm 2 is used at the i-th outer step of Algorithm 1 it should be intended random variable that depends the randomization used during the current estimation the given node, as well as on the randomness of the past iterations, inducing the o-algebra F; (see Section for the definition). Bounds for the bias of this estimator conditional on the past and for its second moment play an important role below, in our analysis of the convergence rates. These bounds are presented in the next two lemmas, whose proofs are presented in Appendix We state them in the simpler setting of Algorithm with no reference to the filtration (Fi)ieN-
Lemma 1. Let f IRd + R be a function in FL( 2 and let the random variables Ei..... Ed and E, be independent of and satisfy E[K,,] cc. ElE]]] < oc, for =........ L...., .. d. Let the
kernel satisfy conditions 3 If the gradient estimator g of f given by Algorithm 2 then, for all E Rd.
[|||]] V f(())l S L
is straightforward see that the bound Lemma holds when the estimators are build recursively during the execution of Algorithm and the expectation is taken conditionally on F,. This will be used the proofs.
Lemma 2. Les f: IRd + be 2-smooth and let max [V(())] I G.K K (2 < co. Let ........
the random variables EI...., Ea and ,,,..,, E4 be independent of and E[G]] S o², E[({)* o² for j 1....,d. d. If g is defined by Algorithm 2 where is random variable with values in θ independent of and depending on fi....,E, and Ei....,
Eu in an arbitrary way, then
3dn
o²
3 h2
Elg =
+
+ n
2
4
4
5 Noise Model
Algorithm 2 is called to compute estimators of gradients of the local functions fi, 1,... n, at each iteration Algorithm|] T Thus, we assume that agent at iteration generates uniform random variable (t) ~ U[-1,, and gets 2d noisy observations, defined, for I.....d
(6, = ((x'(1) + herr(()e,) (t) (l, = ((x(()) +
where the parameters h4 will be specified later.
In what follows, we denote by Fe the o-algebra generated by the random variables (t),,, for i = ,.....n.. n. In order meet the conditions of Lemmas 1 and 2 for each (i,t), we impose the following assumption on the collection of random variables (r,(t),,,,tt
Assumption C. For all integers and i {1.....m.)
n the following properties hold.
(i) The random variables re(t) U[ are independent of (..(().... (t). (t)...... (t) and the o-algebra F..
(i) E[(S,, (1) < a², (1() < o² for = l..... d, and some 2 0.
Assumption C is very mild. Indeed, its part (i) occurs as a matter of course since it is unnatural assume dependence between the random environment noise and artificial random variables rt( generated by the agents. We state (i) only for the purpose of formal rigor. Remarkably, we do not assume the noises (t) and (t) to have zero mean. What is more, these variables can be deterministic and no independence between them for different i. is required. so we consider an adversarial environment. Having such relaxed assumption on the noise possible because of multiplication by the zero-mean variable K (r) in Algorithm 2 This and the fact that all components of the vectors are treated separately allows the proofs go through without the zero-mean assumption and under arbitrary dependence between the noises.
5

---

6 Main Results
In this section, we provide upper bounds on the performance of the proposed algorithms. Recall that To is the number of outer iterations in Algorithm I Let T be the total number of times that we observed noisy values of each f:. At each iteration of Algorithm to keep the total budget equal to T we need to make To T/ (2d2) steps of Algorithm (assuming that T/ (2d) an integer). We compare our results to lower bounds for any algorithm with the total budget of I' queries.
2 we make 2d queries. Thus,
For given 2, we choose the tuning parameters n/e and h he in Algorithms and 2
2 and
h4 t 20
at
Inspection of the proofs in Appendix minimizing the bounds. As one can expect, there are two contributions to the bounds, one representing the usual stochastic optimization error, while the second one accounts for the distributed character of the problem. This second contribution to the bounds is driven by the following quantity that we call the mean discrepancy: (t) n Σ
[ shows that these values of The and he lead to the best rates
It plays an important role in our argument and may be of interest by itself, cf. Tang et al. [019 The next lemma gives a control of the mean discrepancy.
(t) =(t) J.
Lemma 3. Let Assumptions A B and C hold. Let θ be a convex compact subset of RR_ Assume that diam ( S I. and max [V[())] G. If the updates xf (t), s(t) are defined by Algorithm 4 in
which the gradient estimators for i-th agent are defined by Algorithm with F = fú. 1, and parameters then
At) S A
(
P
2
(5)
p-
a
where A is a constant independent of I, d, or, n, p. The explicil value A can
can be found in the proof.
Proof Sketch. Let V(t) E (()) and 2t()) Proje (=' (t))((((((t))) (x' (t)
Neg (t)) The first step is show that, due to the definition of the algorithm and Assumptions A on
matrix W, we have
v(t+1) p²
(1)( =(t) ()( 5(1) + +1) =(1
(6)
where g(t) and E(() denote the averages of (1)'s and 2² (()'s over the agents i. From (6. by using conditionally on F., taking expectations and
the fact that [[= < 7) (I)]l, applying Lemma I
then applying Lemma we deduce the recursion
p²
28-1
1) + + A
1-p a²
where A > is constant. The initialization of Algorithm that A (t) is bounded by a discrete convolution that can be carefully evaluated leading to (5)
1 is chosen so that A(1) 0. It follows
Using Lemma 3 we obtain the following theorem. Theorem 4. Let be a-strongly convex function and let the assumptions of Lemma be satisfied. Then for any x E the cumulative regret satisfies
d TØ (B, + B2p²) + Σ E(((E(()) f(x)] < a(l-p)
B3
(log (To) + 1),
where the positive constants B, are independent To, d, a, n, The explicit values of these constants can be found in the proof. Furthermore, if is the minimizer of I over O the optimization error of the averaged estimator i (TT)) To Ib x(t) satisfies
To - Elf()(Th)) - f(x')( v a(1 - p)
d
B3
log (Tg) + +1).
(B, + BBp²) + a(1 p)
(7)
Tg

---

Proof sketch. Note first that, due to the definition of Algorithm and to the properties of matrix W we have #(++1) = =(t)
n)) zt). This resembles the usual recursion the gradient algorithm with an additional term =(() = n Σ Zi=1 21()), where |='(1)] Σ me (nllg"(() (4)ll- Using this bound and a-strong convexity of f. analyzing the recursion in the standard way and taking conditional
expectations we obtain that, for any x E θ
f(ā(t) - f(x) S 1 E[aa- a441 [F
+
2T/
Σ
n
E
1g (+)l |F
21
|E(O(()55) VS(3() (T()
xl
((()), +(() x> |F]
(8)
T
Biasl
Bias2
where = [+((1) ==12. Here, the term Bias2 is entirely induced by the distributed nature of the problem. Using the properties of Euclidean projection and some algebra, it can be bounded as
Bias2 - 2(1 p)m
3tt
E(llg((t))
+
1-P Σ (x =(t)|| 2nTTEe
(9)
On the other hand, Bias accumulates two contributions, the first due the gradient approximation [ and the second due to the distributed nature of the problem:
(ef. Lemma
L
Biasl s RgT.Vanf ||+(()
x=ll
=(t)l [T(()) x=l
((NaL)
dhg
2(3-1)
000
Lta(l - p)
20 (1) x1|
41ae(1 - -p0mm5) -
LK3 (10)
Next, we combine inequalities 8) 10p. take expectations of both sides of the resulting inequality, and use Lemmas 2 and to bound the second moments E| gg(())))))))))()) [2] and the mean discrepancy. The final result obtained by summing up from t 1 to t Ty and recalling that 7/2 2 h4 क.
Due to a-strong convexity of f. Theorem 4 immediately implies bound on the estimation error ([[)
x= [2.]. The bound is of the order of the right-hand side of (7) divided by Furthermore, we get the following result about local estimators, which follows from a slight modification of Lemma
3 and Theorem[4
Corollary 5. Let Assumptions A A and C hold. Let θ be convex compact subset of Rd. Assume
that diam(()) < IC and max [x)]] I G. If the updates x² (t) are defined by Algorithm
7 in which the gradient estimators for i-th agent are defined by Algorithm 2 with F fu. i
1. I,...,n, n, and parameters tp a(t+1) he t then the local average estimator & (To) To(To+1) Ets, (x) satisfies
{
d
To 1
np² (1 (1 D)To
)
[[]) xx -1]) C Cmin
i 1, I....,n.
a²
where C > O is positive conslant independent of To, d, n.
We now state a corollary of Theorem 4 for an algorithm with total budget queries. Assume that To T/(2d) is an integer. As our algorithm makes 2d queries per step the estimator ((T((2d) uses the total budget 7 queries. Combining Theorem 4 with the trivial bound (()(G(T((dd) GKC we get the following result.
Corollary 6. Let T 2 2d and let the assumptions of Theorem be satisfied. Then we have
min {1, 12-1/8
T 2
( -
a(1 p)
where C > O is a positive constant independent of "T,,d,aa n.
We now state several important implications of our results.

---

Remark 1. Previous bounds on zero-order distributed optimization Ou and Li [2018). Yu et al. [2019, Tang et al. [2019] contain a dependency of (1- in the "connectivity" parameter p. While Theorem Saneemmmoooer covers more difficult noisy setting, our bound displays a better dependency of (1 ()- Since most common values of p are of the order n (or n n this represents substantial gain.
Remark 2. The case n = 1, O corresponds to usual (undistributed) zero-order stochastic
optimization. Then 6 bound of order min (1, - T - )) This improves upon
the bound min (1, TT= obtained under the same assumptions in Akhavan al. 22220]. Still
our bound does not match the minimax lower bound established in Akhavan et al. 12000 and equal to
min
d d LT
(T=-)t) a
(11)
VT
For a x the lower bound [1] scales as min (1, TT) It has the same behavior in the a interesting regime of a not too small (a 2 TT1122+188 and T 2 d. Note, however, that the lower bound (11) is obtained for the setting with i.i.d. noise, while our upper bound is valid under adversarial noise. Therefore, it may seem rather surprising that the ratio is only d! 1/8
With the same budget of queries T, the 2d-point method Algorithmm 2 is computatioonally simpler than the methods with one two queries per step Polyak and Tsybakov (1990), Bach and Perchei (2016), AAkhavan et al. (2020) previously suggested for the same setting. For example, the method in Bach and Perchei (2016], Akhavan et al. [2020] prescribes, at each step 1...,, T, to generate a random variable uniformly distributed on the unit sphere in Rd. This requires of order d calls of one-diment one-dimensional random variable generator. Overall, in T steps, the number of calls is of order df. For our method with the same budget T, we make of order To = T/((d) steps and at each step we need to call the generator only once in order to get U[- Thus, with the same budget of queries, Algorithm needs ~ 1/d2 less calls of random variable generator than the gradient estimator in Bach and Perchet (2016). Akhavan al. (2020).
Remark 3.
In Appendix E we present a numerical comparison between the algorithm proposed in this paper and that in Akhavan et al. 2220)) The results confirm our theoretical findings. The algorithm of this paper converges faster and the advantage is more pronounced as d increases.
7 Improved Bounds for B = 2
In this section we provide improved upper bounds for the case 3 2 in Corollary 6 where we relax the dependency over d, from d3/2 to d.
Following the literature on undistributed zero-order optimization, we use standard 2-point method with elements of the analysis developed in Flaxman et al. [2005), Agarwal et al. [2010]. Duchi et al. 20133) Shamir [2013 2017), Akhavan et al. 22200] among others. Specifically, we define
d (v.(0)
(1(1) 2h, where (1( = (O)
(12)
=1)== (A-0)))---))
with the random variables (t),, 1 < < n, t T, that are i...d. uniformly distributed on the unit Euclidean sphere in Rd. We make the following assumption on the noise analogous to Assumption C Assumption D. For all integers and all {L....,n) n) the following properties hold.
(i) The random variables (i(t) are independent of (,(t), E((t) and from the a-algebra Ft,
(ii) E[({)(t))?] < o², E((E((t))) < o² for some 2 0.
Theorem 7. Let f be an a-strongly convex function. Let Assumptions A
B and D hold with 2. Let O be convex compact subset of Rd. and assume that diam K. Assume that
'The recent work Novitskii and Gasnikov [022] obtains the same improvement using the gradient estimator of Akhhaaan et al. [020]. However, as we explain in Remark 3 that estimator is less appealing from the computational point of view.
8

---

max,ce [Vf((=)] & for 1 sii n. Let the updates z xt()), be defined by Algorithm
in
which the gradient estimator for i-th agent is defined by 12 and 1): = at h4 =
3d
Then for the estimator ((T) T-(2/ 2 [7/2]+1 +1
x(t) we have
B d d²
E[J(T(T)) - [(x))] - 1 --p VaT
aT)
where B > O is a constant independent of T, d, a. n,
The main idea of the proof is to use surrogate functions f1()), for 1 1 i I n, defined, for every E RR as (z) = [f + h&C), where the expectation with respect to the random vector uniformly distributed on the unit ball B3 = {u E Rd ||u]| < 11. A result, which can be traced back to Nemirovsky and Yudin [188) implies the fact that (t) an unbiased estimator of the gradient of the surrogate function fe at x (t). Thus, we can consider Algorithm as a gradient descent for the surrogate function. Then replacing fi and by the surrogate functions with the cost of the order h2. we can recover the initial problem. This method does not work for B > 2 since the error of
approximation by surrogate function becomes of bigger order than the optimal rate T -- The results that we implement as tools for this section are given in Appendix D
Combining Theorem 7 with the obvious bound ([)(T(T) f(x*)] S GK we obtain
B'
min (I,
d
E[f(i(T)) - f(x"))))))))))))))) < 1 p
(13)
VaT
where 13 > 0 is a constant independent of T, d, a, n. p. By comparing this upper bound with the
minimax lower bound III for / = 2. one note that 13 is optimal with respect to the parameters T and d when a x 1.
8 Discussion
We expand our discussion on previous related work, comparing our results to the sfate-of-the-art distributed and undistributed zero-order optimization settings, and highlight few key open problems.
Comparison to Zero-Order Distributed Settings Distributed opimization with noisy functions' queries was considered in detail in Sahu et al. [2018b a). where the setting differs from ours in some key aspects: the updates are obtained not as in Step 2 of Algorithm I but rather via decentralized techniques, matrix W is random, the noise is zero-mean random rather than adversarial, and 2-point gradient estimator is used. Papers Sahu al. 2018b provide, for 2 and / 3, bounds on 3/2 2/3 respectively, as functions of 1/2 and [1-p)= T
E[[[> (T) x²) [[2] of the order at least
9/2
(1-p)²
n. p and T. Their bounds contain uncontrolled terms of the form [[])==((a)) x= [2) for some large enough kn = (11, o: d) leaving unclear the resulting rate. Paper Hajinezhad et al. [2019) considers 2-point methods with stochastic queries but assume that the noise is the same for both queries and
deal with non-convex optimization. Noisy-free free zero-order distributed optimization is studied by Qu and Li [2018] Yu et al. [2019] Tang et al. [2019] From these, Tang et al. [2019] is the closest to our work as it builds on the updates as at Step 2 of Algorithm (though without projections). The bounds obtained therein are of the order (1 p) considered as functions p. although they hold for the larger class of gradient dominant functions. As noted in Remark thhe bound of Theorem 4 scales only as (1 - p) and this bound holds true, in particular, for noisy-free free setting, which is its special case corresponding to O. Since most common values of 1 are of the order n (or n 11) this represents a substantial gain. Moreover, Theorem 4 covers a difficult noise setting as we deal with adversarial noise. It is also worthwhile to note that the first-order distributed optimization exhibits much better dependency on since bounds that scale as - (1-p)-14 -1/2 can be achieved, see (Duchi et al. (2155] [Scaman et al.) 2019). Some of the references mentioned above considered unconstrained optimization while our results deal with constrained optimization. Note that the only difference in the proofs of the upper bounds for constrained and unconstrained cases is in the presence of an additional term proportional to the second moment of the gradient at the update (see Lemma 2.4 in Akhavan et al. (020) for a similar argument). Since this additional term is bounded independently of p the overall dependency on p remains the same.

---

Computational and Statistical Advantage of the Proposed Gradient Estimator As we high- lighted in Section the gradient estimator in Algorithm requires 2d function queries. At first sight this seems problematic when the dimension d is high, they need at least T = 2d queries. However, the lower bounds in Shamir 2013], Akhavan et al. (2020) reported in (1 above indicate that no
estimator can achieve nontrivial convergence rate for zero-order optimization when T S d==i, Thus, having the total budget of 'T' > queries is a necessary condition for success of any zero-order stochastic optimization method. Algorithms with
two queries per step can, of course, be realized for T S but in this case they do not enjoy any nontrivial error behavior. Moreover, by Remark 3] with the same total budget of queries T. the gradient estimator from Algorithm 2 is computationally more efficien than the estimators in Polyak and Tsybakov 1990 Bach and Perchet 2016), Akhavan al. [2020). Indeed, with the same budget of queries, it needs 1/d less calls of random variable generator than it would be for the gradient estimator in [Bach and Perchet (2016), Akhavan et al. 2020). At the same time, as detailed in Remark 2 the proposed gradient estimator
yields better rates on the optimization error. We conclude that the proposed zero-order optimization procedure provides both a computational and statistical improvement over the state-of-the of-the--rtttttttt methods
in Ankhhaaan et al. [2020].
Limitations and Future Work main problem, which remains open, is to study whether the dependency of (1 - p) in the upper bounds in Corollary and Theorem is minimax optimal. Moreover, in the standard (undistributed) setting it remains open problem to design order optimization procedure that meets the minimax lower bound [II with respect to all problem parameters (T, d, 3 and a). Further directions of research include the analysis of disturbed zero-order algorithms for larger classes of functions, such as a-gradient dominant ones, as well as extension of results to stochastic updates asynchronous activation schemes.
Funding Disclosure
A. Akhavan and M. Pontil were partially supported by SAP SE. The research of A.B. Tsybakov is supported by a grant of the French National Research Agency (ANR), "Investissements d' Avenir" (LabEx
References
A. Agarwal, O. Dekel, and L. Xiao. Optimal algorithms for online convex optimization with multi- point bandit feedback. In Proc. 23rd International Conference on Learning Theory, pages 28-40, 2010.
A. Akhavan, M. Pontil, and A.B. Tsybakov. Exploiting higher order smoothness in derivative-free optimization and continuous bandits. In Advances in Neural Information Processing Systems 33, 2020.
F. Bach and V. Perchet. Highly-smooth zero-th order online optimization. In Proc. 29th Annual Conference on Learning Theory, pages 1-27, 2016.
A. Belloni, T. Liang, H. Narayanan, and A. Rakhlin. Escaping the local minima via simulated annealing: Optimization of approximately convex functions. In Proc. 28th Annual Conference on Learning Theory, pages 240-265, 2015.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6))2508-22 25300 2006.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3:1-122, 2011.
"One may object that computation bottleneck in zero-orde crde- optimization in function evaluation; however such costs are external to the optimization procedure, for example they may be performed by black-bor box software running on external machines or devices. Thus such costs should not be taken into account in evaluating the procedure itself. In this
computational speedup is important for high dimensional settings.
10

---

L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, New York, 1996.
J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3): 592-606, 2012.
C. Duchi, M. I. Jordan, M. Wainwright, and A. Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (1(5):778-28806 2015.
A. D. Flaxman, A. T. Kalai, and H. B. McMahan. Online convex optimization the bandit setting: gradient descent without gradient. In Proc. 16th Annual ACM-SIAM Symposium Discrete algorithms (SODA), pages 385 -85-,94, 2005.
D. Hajinezhad, M. Hong, and A. Garcia. Zeroth order nonconvex multi-agent optimization networks. IEEE Transactions on Automatic Control, 64(10):3995 -4000 2019.
D. Jakovetić. A unification and generalization of exact distributed first-order methods. IEEE Transactions on Signal and Information Processing over Nenworks, 5(1):31-46, 2019.
D. Jakovetić, J. Xavier, and J. M. F. Moura. Fast distributed gradient methods. IEEE Transactions Automatic Control, 131-1113111114 146, 2014.
131-1
S. Kia, J. Cortés, and S. Martínez. Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication. Autom,, 55:254-264, 2015.
T. Kraska, A. Talwalkar, J. C. Duchi, R. Griffith, M. Franklin, and M. I. Jordan. MLbase: A distributed machine-learning system. In CIDR, 2013.
L. Liu, C. Luo, and F. Shen. Multi-agent formation control with target tracking and navigation. In 2017 IEEE International Conference on Information and Automation (ICIA), pages 98-103, 2017. doi: 10.1109/ICInfA.22 20177.078889
I. Lobel, A. Ozdaglar, and D. Feijer. Distributed multi-agent optimization with state-dependent communication. Mathematical Programming, 129:255-221 284, 201
A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agen optimization. IEEE Transactions on Automatic Control, 54(1):48-66 2009.
A. Nedic, A. Ozdaglar, and P. Parrilo. Constrained consensus and optimization in multi-agent networks. Automatic Control, IEEE Transactions on, 55:922-938, 2010.
A. S. Nemirovsky and D. B Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley & Sons, 1983.
V. Novitskii and A. Gasnikov. Improved exploiting higher order smoothness in derivative-free optimization and continuous bandit. arXiv preprint arXiv:2 00320012,..1.. 2021.
A. Olshevsky. Linear time average consensus on fixed graphs and implications for decentralized optimization and multi-agent control. arXiv: Optimization and Control, 2014.
A. Olshevsky and J. Tsitsiklis. Convergence speed in distributed consensus and control. SIAM Journal on Control and Optimization, 48(1):33-55, 2009.
J. Park, S. Samarakoon, A. Elgabli, J. Kim, M. Bennis, S.-L. Kim, and M. Debbah. Communication- efficient and distributed learning over wireless networks: Principles and applications, 08 2020.
T. B. Polyak and A. B. Tsybakov. Optimal order of accuracy of search algorithms in stochastic optimization. Problems of Information Transmission, 26(2):45-53, 1990.
S. Pu, Shi, Xu, and A. Nedié. Push-pull gradient methods for distributed optimization in networks. IEEE Transactions Automatic Control, 66(1):1-16, 2021.
11

---

G. Qu and N. Li. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Nenwork System, 5(5):1245-1260, 2018.
A. Sahu, D. Jakovetic, D. Bajovic, and S. Kar. Communication-fffcienn distributed strongly convex stochastic optimization: Non-asymptotic rates. arXiv:/809.02930 2018a.
A. Sahu, D. Jakovetic, D. Bajovic, and S. Kar. Distributed zeroth order optimization random networks: A woffer- stochastic approximation approach. pages 4951 -9158,958 12 2018b.
M. O. Sayin, N. D. Vanli, S. S. Kozat, and T. Başar. Stochastic subgradient algorithms for strongly convex optimization over distributed networks. IEEE Transactions on Network Science and Engineering, 4(4):248-260, 2017.
K. Scaman, F. Bach, S. Bubeck. Y. T. Lee, and L. Massoulié. Optimal convergence rates for convex distributed optimization networks. Journal of Machine Learning Research, 20:1-31, 2019.
O. Shamir. On the complexity bandit and derivative-free stochastic convex optimization. In Proc. 30th Annual Conference Learning Theory, pages 1-22, 2013.
O. Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(1):1703-1713, 2017.
W. Shi, G. Wu, and W. Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization, 25(2):44--966, 2014.
Y. Tang, J. Zhang, and N. Li. Distributed zero-order algorithms for nonconvex multi-agent optimiza- tion. arXiv preprint arXiv: 1908. / 1444v3, 2019.
J. Tsitsiklis, D. Bertsekas, and M. Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE Transactions on Automatic Control, 3109)803--11, 1986.
Z. Yu, D. W. C. Ho, and D. Yuan. Distributed randomized gradient-free free mirror descent algorithm for constrained optimization. arXiv preprint arXiv:/903.044 941557 2019.
12


Reviews:
[{"review_id": "x5Q45vHozL", "reviewer": "Reviewer_LtqT", "summary": "This paper considers the problem of distributed zeroth-order optimization for a class of strongly convex functions. The authors propose a distributed zeroth-order optimization algorithm that only requires only functional evaluations of the objective functions, subject to a general noise model. The error bounds of the algorithm have also been established and improve upon the previous works. Lower bounds have also been discussed and they are nearly optimal. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very well written and easily readable. But the presentation of the paper could be improved:\n\n1. As is well known that zeroth-order optimization is closely related to bandit optimization in online learning, so it would be better if the authors could provide some discussions about the connections between these two directions;\n\n2. The simulation results are lacking. It is preferred to present some experiments on real-world applications, and comparisons with more related algorithms are welcome;\n\n3. Is the dependence of the bounds on the dimension optimal? \n\n4. More discussions about Definition 1 should be given. Why consider this type of function?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "tI4tAAuk2pa", "reviewer": "Reviewer_RUCN", "summary": "This paper studies a distributed optimization problem where the nodes conform to a given adjacency graph. The prevailing formulation of this problem in the literature is based on first order (gradient based) algorithms. This paper however, following [11, 27, 28, 29, 35, 37] considers a zeroth order optimization problem where only direct observations from the function value are accessible (instead of gradient). The average objective function is assumed to be strongly convex and the local objectives are assumed to be Hölder continuous. A distributed optimization algorithm based on a novel gradient estimator is presented. It is shown that the proposed algorithm is favorable over the existing ones in both convergence rate and computational complexity.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The work is a combination of well-known techniques. Graph structured distributed optimization is a well-studied problem under the first order setting. This paper uses a kernel based gradient estimation for smooth functions to translate the zeroth order information to the first order ones (Algorithm 2). This gradient estimation step which seems the main contribution is also similar to the existing methods.\n\nQuality: The results are technically sound.\n\nClarity: The paper is very well written and well organized.\n\nSignificance: The results seem to improve over the existing ones both in computational complexity and convergence rate. Although, to better understand the scope and novelty of the results, I have a couple of questions detailed below.\n\n1. The gradient estimation method seems completely independent of the particular \"graph structured distributed\" optimization problem. Is it true that if the same gradient estimation is used for a standard centralized problem that also results in an improvement? If not, could you please specify why it results in an improvement in the \"graph structured distributed\" optimization?\n\nIn particular, it seems that the novelty is in the gradient estimation. Otherwise, when the zeroth order information is translated to the first order information, the rest follows the standard optimization techniques. I would like to better understand the scope of this better estimation of the gradient. Are algorithm 2 and Lemmas 1,2 novel fundamental results on the way to estimate gradient of a smooth function? In that case, I think this should be clarified in the paper. The improvement in the gradient estimation should also be quantified and reported in the paper.\n\n\n2. The difference between Algorithm 1 in [2] and Algorithm 2 in this paper seems very subtle. It seems that the only difference is that while, in this paper, the canonical basis vectors are used for the change in the input of the function, in [2] an arbitrary vector on the sphere is used. This subtle difference appears to result in a considerable gain in the gradient estimation:\n\ni) an $O(\\sqrt{d})$ improvement in the bound on bias; Lemma 1 vs Lemma 2.3 of [2]\n\nii) an $O(d)$  improvement in the bound on variance; Lemma 2 vs Lemma 2.4 of [2]\n\n- Could authors provide some intuition on the reason for these improvements given the algorithms are essentially the same?\n\n- These improvements are reflected in the convergence rate. Is it fair to say these improvements are the only reason for the improved convergence rates?\n \n\n\nA minor comment: there seems to be an error in lines 458, 465 where Lemma 2 is placed before the proof of Lemma 1. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the work are discussed in Section 8. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "gyAhdS94KVh", "reviewer": "Reviewer_N8uL", "summary": "This paper considers distributed optimization with zero-order information and under rather general setting of noise in the evaluation of function values. The authors propose a zero-order projected gradient descent algorithm, in which a novel zero-order gradient estimation scheme is used. An important contribution of this paper is to provide explicit upper bounds for the average cumulative regret and optimization error of the proposed algorithm. The obtained bound is clearly presented and show the advantage of the proposed algorithm over existing ones. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: the proposed kernel-based $2d$-point gradient estimator seems new. It is key to achieving improved evaluation upper bound and handling non-zero-mean noise.\n\nQuality: this paper is of high quality. All the technical results are supported with proof and comments. Insights and limitations of the obtained results are also discussed. It would be better if the authors could provide some insight on why the proposed algorithm attains an upper bound that is proportional to $(1-\\rho)$ rather than $(1-\\rho)^2$.\n\nClarity: the paper is written with high quality. The motivation, technical results, and limitations are clearly presented. It is a pleasure to read this paper. It would be nice if the authors could include some numerical results in the main body of the paper.\n\nSignificance: the obtained bound is new and significantly improves existing bounds even for standard (centralized) zero-order optimization.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no foreseeable negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "_ytW7PDGcrw", "reviewer": "Reviewer_pQgq", "summary": "This paper studies zero-order optimization for strongly convex functions. The authors propose a novel 2d point zero-order gradient estimator, combing with distributed projected gradient descent, they provide upper bounds that are robust to adversary noises and have better dependence on (1 - \\rho). In addition, they provide an improved analysis for 2-Holder functions using 2 point gradient estimator in that the dimension dependence is improved from d^1.5 to d. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. The paper proposes a novel 2d point zero-order gradient estimator, which is computationally more efficient by a factor (1/d^2) in terms of total calls of random variable generators during algorithm execution,  especially beneficial in high-dimension regimes. \n\n2. The paper shows optimization upper bound that has network dependence (1 - \\rho), improving from the previous (1 - \\rho)^2, where \\rho is the spectral gap of the mixing matrix. Although I’d appreciate it if the authors could provide a brief analysis into this dependence matter, I only find explicit dependence of (1 - \\rho)^2 in reference [27], while the authors also mention this dependence in references [35][37]. Also, I notice that those mentioned references are considering unconstrained optimization while this paper uses convex compact constraint, could the authors discuss a little bit on this when comparing the network dependence?\n\n3. The numerical experiment is pretty artificial, can we find some real but may simple machine learning tasks to demonstrate the effectiveness of the proposed algorithms? \n\n4. I skipped the proof for section 7, for the parts I have read,  \n    4.1. In line 181, I am trying to understand why these values of \\eta_t, and h_t lead to the best rates.\n    4.2. In the proof of Lemma 2, we may half the constants since r has density 1/2. \n    4.3. In appendix B, the statements for Lemma 1 and Lemma 2 seems to be reversed.\n    4.4. In line 521, there are some obvious typos. \n    4.5. In line 524, I am trying to understand when deriving B_1 why the dependence on 1/(1 - \\rho) is dropped, the overall dependence on (1-\\rho) in the lemma is not affected though.\n    4.6. In equations below line 537, the last term misses T_0. \n\n5. The paper title contains “adversarial noise”, however, it seems to me the noise model is a general unbiased one with bounded second moment, there is no adversary such as designed attack or arbitrary value manipulations, so I feel this adjective in title may not be that relevant. \n\n6. The paper is in general well written and of high quality, the contribution is very solid.\n\nComments after rebuttal:\nI thank all the replies from authors and other reviewers, and I keep my current assessment.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are all in agreement that this work ought to be accepted, and the largely-minor concerns were all resolved following the author feedback.  There were no major points of discussion that need highlighting in this meta-review, but I encourage the authors to carefully incorporate the reviewer feedback in the final version.  As one specific point, I do agree that the word "adversarial" could potentially cause confusion, especially in the title.  Although the word has many meanings, it could serve as a disadvantage if the title gives potential readers the wrong impression.  I leave it up to the authors whether to change the title, but ask that they consider the possibility carefully.
Decision: Accept (Poster)