Distributed Zeroth-Order Optimization: Convergence Rates That Match Centralized Counterpart
Authors: Deming Yuan
Lei Wang
Alexandre Proutiere
Guodong Shi
Venue: ICLR 2022 Submitted (2022)
Keywords: Zeroth-order optimization
distributed optimization

Abstract: Zeroth-order optimization has become  increasingly important  in complex optimization and machine learning  when  cost functions are impossible to be described   in closed analytical forms. The key idea of zeroth-order optimization lies in the ability for a learner to build gradient estimates by queries  sent to the cost function, and then traditional  gradient descent algorithms can be executed with gradients replaced by the estimates. For optimization of large-scale  multi-agent systems with decentralized data and costs, zeroth-order optimization can continue to be utilized to develop scalable and distributed zeroth-order algorithms. It is important to understand the trend in performance transitioning from centralized to distributed zeroth-order algorithms in terms of convergence rates, especially for multi-agent systems  with time-varying communication networks. In this paper, we  establish a series of convergence rates for distributed zeroth-order subgradient algorithms under both one-point and two-point zeroth-order oracles. Apart from the additional node-to-node communication cost in distributed algorithms, the established rates in convergence are shown to match their centralized counterpart. We also propose a multi-stage distributed zeroth-order algorithm that better utilizes the learning rates, reduces the computational complexity,   and attains even faster convergence rates for compact decision set.

Under review as a conference paper at ICLR 2022
DISTRIBUTED ZEROTH-ORDER OPTIMIZATION: CON- VERGENCE RATES THAT MATCH CENTRALIZED COUNTERPART
Anonymous authors Paper under double-blind review
ABSTRACT
Zeroth-order optimization has become increasingly important in complex opti- mization and machine learning when cost functions are impossible to be described in closed analytical forms. The key idea of zeroth-order optimization lies in the ability for a learner to build gradient estimates by queries sent the cost func- tion, and then traditional gradient descent algorithms can be executed replacing gradients by the estimates. For optimization over large-scale multi-agent sys- tems with decentralized data and costs, zeroth-order optimization can continue to be utilized to develop scalable and distributed algorithms. In this paper, we aim at understanding the trend in performance transitioning from centralized distributed -rothh-order algorithms in terms of convergence rates, and focus on multi- ageet systems with time- varying communication networks. We establish a series of convergence rates for distributed zeroth-order subgradient algorithms un- der both one-point and two-point zeroth-order oracles. Apart from the additional node-to-node communication cost due to the distributed nature of algorithms,, the established rates in convergence are shown to match their centralized counterpart. We also propose multi-stage distributed zeroth-order algorithm that better uti- lizes the learning rates, reduces the computational complexity, and attains even faster convergence rates for compact decision set.
INTRODUCTION
Various machine learning tasks ultimately boil down to solving optimization problems of different forms, where the cost functions are formed jointly by the data accumulated in experiences and the model used in representing the learning framework. Gradient descent algorithms have been playing foundational role in practically solving such optimization problems. However, for learning tasks with nigh-dimensiioal data and involved learning representations, access to the gradient the cost function may turn out not possible: the cost function supporting the learning may have a closed analytical form; or it is simply too computationally costly to be properly differentiated. Zeroth-orde optimization provides systemic way of facilitating gradient descent without direct access to gradient information, where oracles query the cost function values and generate gradient estimates. Zeroth-order methods have shown number of successful applications, e.g., searching for adversarial attacks in deep learning Chen et al. (2019) : Liu et al. (2019) and policy search in reinforcement learning Vemula al. (2019).
The literature has also explored the potential in extending the standard (centralized) zeroth-order optimization to distributed settings over multi-agent systems, where the data and cost functions are scattered across a network of decentralized agents. With the help of a communication network, the agents may collaboratively solve the network-level optimization task by iteratively exchanging decisions obtained from local zeroth-order descent. The rates of convergence of centralized zeroth- order optimization algorithms We are interested in systematically investigating these convergence rates scale for the corresponding distributed algorithms, and focus the case of time-varying communication networks.
well understood for several sub-classes of convex functions.

---

Under review as a conference paper at ICLR 2022
1.1 PROBLEM DEFINITION
Consider a network of agents (nodes) V = following distributed optimization problem
[1....,NN. The agents aim to collectively solve the
minimize
f(x) Σ fi(x)
(1)
subject to
X X.
Here E IRd is the decision variable, X C Rd is convex decision space, and fi IR IR is private convex objective function associated with agent i.
The communication network connecting the nodes is described by time-varying graph S(() (V, Et)). where E(t) the of activated links time Let ( be weight matrix time for the graph S(t): for each link (i,j) E E()), weight (t)ss > 0 is assigned, and [A(t)ks
for (i.j) (t). We impose the following assumption on the communication network E(t) and the
weight matrix (t).
Assumption (i) There exists a positive integer B such that the union graph
B() is strongly connected for all ks 2 0; (ii) A(t) is doubly stochastic, i.e, I = 1 and [)=(A(t)]] (iii) [A(t)] a 2 for all i, and [A(t))s 2 if E E(t), where & $>0 0.
1.2 FUNCTION CLASSES
Let Fer denote the set of all convex functions on Rd. We define the following three classes of convex functions in Tevx-
The Lipschitz continuous class (ipp contains the functions in Fox that admit finite Lipschitz constant Ly over X, i.c.,
Fipp ( (0) = {g E Fexx Vx, x' E X, 1g(xx - g(x')l = L x'II
The smooth class (s X) contains the functions that admit s - Lipscciit continuous gradient over X, i.e.,
T smo
(s sm
= {gg E Fex Vx, E X, Vg(x) Vg(x')l S sy|ix x' |/
The strongly convex class Fsc(1 X) contains the functions that are /1y-Strongly convex, i.c..
Fx = to E Fox Vx, E gx 2 g(x) (Vo(x')) x²)
14 2 xx 21
1.3 CONTRIBUTIONS AND RELATED WORK
Contributions. We first present MAZOPA, multi-agent zeroth-order projection averaging algo- rithm. In MAZOPA, the agents iteratively carry out local zeroth-order descents for their private costs generate intermediate decisions, send these intermediate decisions to their neighbors over the graph (()), and then update their decisions by projecting the average neighboring intermediate decisions onto X. For distributed zeroth-order oracles based on one-point or two-point estimates, series of convergence rate results are established for the three basic function classes. Remarkably, the convergence rates for distributed algorithms are found to be matching their centralized coun- terpart, and sometimes even tighter rates are obtained, as summarized in Table 1. These results show that by paying the price of node-to-node communication, distributed zeroth-order optimiza- tion provides equal performance guarantees those of centralized approaches. Next, generalize the MAZOPA to a multi-stage setting, where the local zeroth-order descents take place for multiple steps before the projected averaging in sequence of epochs. Such multi-stage MAZOPA is shown to be able to reduce the computational complexity. while providing improved convergences rates compared to MAZOPA when the decision set is compact.
2

---

Under review as a conference paper at ICLR 2022
Table 1: Convergence rates established for MAZOPA
700
Lipschitz Class [Centralized Counternart
Strnngyy Convex Class [Centralized Countemart
Thp 0( pirz) ( pfrz)
Flaxman et al. 2005
Tip ( Tae (
Agarwal ct al. 2010
One One-poinn
Sip O Fmmm:
Fiip O Pmno ( 0
[o
Agarwal et al. 2010
v
Two-point
Tip: o(y () [o(y
Shumir 2017
Jíp nTae: 0( (
Agarwal
2010
ip n Fmmm: 0V4
Sip Fimo Tae
0
[0
Agarwal al. 2010
Related Work. Recently, many types of centralized zeroth-order optimization algorithms have been studied, and their convergence rates (and the way they depend on the dimension) have been estab- lished in different settings. For unconstrained convex optimization, Nesterov & Spokoiny (2017) develops several types of two-point gradient estimators and achieves convergence rates that scale with dimension as (df). For constrained stochastic optimization. Duchi et al. (2015) establishes that the convergence rates are sharp up to factors at most logarithmic in the dimension. Zeroth-order optimization has natural connection to bandit online optimization, where the latter focuses dy- namic environment where the objective functions are varying over time (see, e.g., Flaxman et al. (2005;; Agarwal et al. (2010); Shamir (2013) 2017 Bubeck al. (2017); Lattimore (2020); Hazan Levy (2014)) In particular, the seminal work Flaxman et al. (2005) constructs a one-point gradi- ent estimator (or one-point bandit feedback model) and achieves an Od average regret. For two-point gradient estimator, (Shamir (2017) establishes the tightness of the dimension-deppndent
factor U(Vd) in the framework of zeroth-order stochastic mirror descent.
It is worth zooming into the literature distributed zeroth-order/bandi online optimization. Due to the absence of a central coordinator, the algorithms developed should always rely on local com- putations and communications (e.g.. Yuan & Ho (2015): Yi al. (2020); Jakovetic al. (2018):
Hajinezhad et al. (2019); Wang et al. (2019); Pang & Hu (2019) ; Hajinezhad & Zav Lavlanos (2018)
Wan al. (2020), ) This makes the convergence analysis
the distributed seroth-order/bandf on-
line optimization algorithms more challenging. In Yuan & Ho (015), the authors develop class of distributed zeroth-order optimization algorithms that require two functional evaluations at each iteration, and establishes asymptotic convergence of the algorithm. Non-asymptotie convergence is established in Jakovetic et al. (0088;; Hajinehhad et al. (2019); Wang et al.) (2019); Pang & Hu 2019); Hajinezhad & Zavlanos (2088), but the dimension-depenee dependence factors either (dd) or far from optimal. The work Yi et al. (2020) considers distributed online optimization with long-term constraints and establishes bounds regret as well constraint violations. To avoid Euclidean projection onto the constraint set. Wann et al. (2020) develops a distributed bandit online optimiza- tion algorithm based conditional gradient descent and one-point bandit feedback, and achieves regret scaling of ((T9/11/I
2
THE MAZOPA ALGORITHM AND ITS CONVERGENCE RATES
In this section, we present the MAZOPA algorithm and establish the convergence rates for the three function classes.
2.1 DISTRIBUTED ZEROTH-ORDER ORACLES
Let be a random vector in Rd drawn from some probability distribution. Then
fx 5) := E, [x + 8n)]
(2)
is smoothed function for f.. Here 8 > 0 is parameter setting the level of the smoothing. We introduce the following definition on distributed zeroth-order oracles (DistZ0O).
Definition (DistZOO) A vector (x; IRd is called distributed zeroth-order oracle at node i if the following conditions hold:
(i) E [gx((x;)) = f((xx; 8) for all Rdd;
(ii) If ft E Fip (Ly), then f. E &Fi((L)) as well, and there holds (f((x;) 6) f((x)) $ paL, with pa being some positive constant;
3

---

Under review as a conference paper at ICLR 2022
(iii) fs Fsyo(sy), then (x) - f((x) S 2o with pa being some positive constant.
number of DistZO0 satisfying Definition I can be obtained using existing gradient estimators, see, e.g.. Liu et al. (0020) In the paper, we provide two representative gradient estimators that are commonly adopted in the literature. Let u, be a random vector independently generated from a unit sphere Bj in Rd Then Flaxman et al. )2005)
OP x 5) = fi(x 8,u,),d/6
a one-point DistZ0O satisfying Definition 1. Moreover,
28 (Ji(x + óu) - fi(x 5u)) two-point DistZO0 satisfying Definition 1 (c.g.. Shamir 2017
gi
(x:
(4)
2.2 THE MAZOPA ALGORITIM
We present the following Multi-Agent Zeroth-Order Projection Averaging (MAZOPA) algorithm, which consists of two steps, local zeroth-order optimization step and distributed averaging step.
MAZOPA, whose pseudo-code is presented in Algorithm [ is a variation of the multi-agent sub- gradient averaging algorithm proposed in Nedic al. (2008) y; Nedic & Ozdaglar (2009); Nedic al.
2010), where the local optimization step is executed by uub-gradient descent.
Algorithm MAZOPA: &; (T) MAZOPA (x,
n/, 6,
Require: step size nh. DistZOO g. (x: 6,) with exploration parameter & for all i e V
Ensure: x; (1) E X, Vi E V
1: for tor== to T do
2: Node queries the DistZOO at point (t) and receives gi (xx(());)))
3: Node computes
(t( = (t) g (x;;
4: Node updates its state by using the information received from its instant neighbors
xt + 1) projx
Σ [A()))vs())
5: end for Output: (T( + Σt= (1)
2.3 MAIN RESULTS
Let &, (7') be the output of Algorithm at agent i. We denote the optimal solution of problem by x* arg minxex (x). Defining X = fx + x X, u B,}, we present the following results on the convergence rate of the MAZOPA algorithm.
Theorem Let Assumption / hold. Let DistZOO take the form of (-) Further assume that (x, + (,),())) S
aor all We have the following convergence results for every V
and all 1
(i) Consider Si E it holds that E [x (T)) fxx) 0 (744))
all i V. Setting ti = 27574 and 5 = 2144 t =1, 1,...,y
1
(ii) Consider fs E Fiip (L,, ()) 0 Fsmo (8), Setting N = 07 and 5₃ = 0/6.
1
1
1...., T, it holds that (x, - f(x')= = -
Theorem Let Assumption 7 hold. Let DistZOO take the form of TTP (.). Set T Jar and
8, = 1 t= =t==1..... ,,...,T.. T.. Consider fo E X0), V. Then, for every i E V and all T' 2 1, we
Vi
have [[f(x, f(x*) =0 0(V 4).
4

---

Under review as a conference paper at ICLR 2022
With strong convexity, the convergence rates established above be further strengthened.
Theorem Let Assumption ! hold. Let DistZOO take the form of g: (-)- Further assume that (t) + 6,u,(t)) C for all V. We have the following convergence results for every i E V and all 1. 1.
(i) Consider fi Flip (L,, 29) n X0) all i E V. Setting d²
Mst and de gi/3
1..,,,,,3 T, it holds that [[
f(xx)((xxx)))))))) (T173)
(ii) Consider fi E Fiip (, x nJ smo (5) (p, (²). Setting T aye and ó, g274.
t == 1....., T,
it holds that {( - f(x') 0 d²
Theorem Let Assumption 7 hold. Let DistZOO take the form of g. TTT(()))))))))))p (.) Set 1
1et and 8g t
t= ..... T. Consider Frip (Ter, (z ),), V. Then, for every E V and all T 2 1, we have E [[(({((T) - f(x*)= = 0( dlu((T)
T
MULTISTAGE MAZOPA: ADAPTIVE LOCAL DESCENT
We impose the following compactness as- We now propose a multi-stage variant of Algorithm I sumption on the constraint set X.
Assumption There exists 0 < Rx such that [|x|| Rx for all x X.
3.1 THE ALGORITIM
The basic idea is to divide the optimization process into sequence of epochs, each of which has an exponentially decreasing step size and an exponentially increasing iteration number. The updates in the inner loop of each stage are just made according to Algorithm [ with fixed step size. In each stage only the average point maintained and used as the starting point of the next stage. This idea of setting up multi-stage optimization algorithms was originally explored in Hazan & Kale (2011).
Take positive integers m 2 1 and 2 2. Let k [ogga ( 1) where |<| represents the largest inter with value no greater than I. We divide the T time steps into A epochs by
Epoch 1:
I,...,
Epoch 2: 7()) + 1...., T(2);
Epoch A -1)--1) 1) + +....., T(t)).
m. For the jth epoch, all agents will run the MAZOPA algorithm, and denote output of the j-th epoch at agent by x(²) (T(i)). The pseudo-code of the resulting multi-stage MAZOPA is presented in Algorithm 2
Here ((1) m, (2) ar,, amm..., T(**) k
Compared to the MAZOPA algorithm, the multi-stage MAZOPA has the following advantages:
(i) Multistage MAZOPA only requires each node projects its estimates onto the ball Bx rather than the constraint set X in each epoch. In particular, multistage MAZOPA algorithm significantly reduces the number of Euclidean projections onto the constraint set X from T to Ab. This makes the algorithm more computationally efficient.
(ii) Multistage MAZOPA better utilizes the step size rules, in the sense that at earlier epochs the algorithm, larger step sizes are adopted to facilitate convergence, while smaller step sizes are adopted to achieve better accuracy at later epochs.
3.2 OPTIMAL CONVERGENCE RATES
We now modify the definitions of Figs Fumo and Fec by replacing X with B BR with slight abuse of notation. As it turns out, the multistage MAZOPA enjoys refined convergence rates.
5

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Multistage MAZOPA
Require: exploration parameter 8(2), step size 111), T(1) m, total number of iterations T, integer a 2 2, and scalar
Ensure: x; (1) E for all E V, and set = ........."
1: while j = l..... 1
do
2: Call Algorithm to obtain
(T()) MAZOPA (x( (1), (Rx,
3: Compute x (1+1) (1) projx
(T())) (T(i()
4: Update v/ (8+1) = 1 and 06+1) = ((80)
5: Update T(++) aT())
6: Update j -+1
7: end while
Output: (T) projx (x: (19) ( (T(A)))
Theorem Let Assumptions and hold. Ler DistZOO take the form of g. (-). Set b, T(1) = 1)(2) 3 and ((1) Consider Ji E Fip( Bn,) ( B B,.). iE V.
have E max (T) x |3] (-41))
The idea of the analysis leading to Theorem 5 can also be extended to one-point oracles. If DistZO0 takes the form of g. (-). one needs impose the following assumption on the objective functions, that is, (x; + 6t),(t)) I C for all i E V. For fi E Fipp BRy) ) n Fsc (M Bn, set- ting = b3. the final estimates enjoy a convergence rate of E max (T) - x* [|
O & vvss) For fa E Fiip (Ly, BR n (sy, BR.) (f BR,) setting a = b², there holds
E maxiev (T]x:(T) x [[ 0 d
NUMERICAL EXAMPLES
In this section, we evaluate the performance of the proposed algorithms on distributed ridge re- gression problem.
System setup. The optimization problem has the following form:
NV f(x) Σ (aTx - -b,2 + p||x|1))
minimize
(5)
subject to |x||| - i=1
where x E Rd is the optimization variable, the data pair (a;, b.) E IRd R. is only known to node with a; and by being generated uniformly from the unit normal distribution.
Network setup. We implement the proposed algorithms over randomly generated network that consists of N nodes, which is shown Fig. In the simulations, we d = 10, 1 3/4, = 1/2, and Ry = 3/4. We evaluate the performance of the algorithms via the average of 10 implementations. The weight matrix associated with the graph is generated according to maximum-degree weights:
(j,1) E &
I+dmax I+dmax
[t())
(j.1) & &
where dmax maxxev (d:} } the maximum degree of St (d: denotes the degree of node i).
Results. The performance of algorithms MAZOPA and multistage MAZOPA is illustrated via plot- ting the maximum function errors, max,v f(, and max (T)( as a function of the number of iterations 7 in Fig. 2. As benchmark, the convergence performance of the gradient

---

Under review as a conference paper at ICLR 2022
Fig. A random network of 50 nodes.
algorithm is displayed in Fig. as well. From the numerical results it is clear that the maximum function errors are vanishing for all zerroth-order algorithms. In fact, the convergence performance of two-point MAZOPA is even comparable to the gradient method. Moreover, the multistage vari- ants in general exhibit better convergence performance, and this is more obvious for the case of two-point MAZOPA. These numerical results are in compliance with the theoretical findings in the paper.
gradent
bwo-pcint
one-point MAZOPA
MS lac- point MAZOPA
10'
Maximum Function
10
150
250
llerationn number
Fig. 2. Convergence performance the algorithms.
Reproduction of the results. The code used for producing this numerical example is provided in the suplementary material.
CONCLUSIONS
We have established series of convergence rates for distributed zeroth-order subgradient algorithms that match their centralized counterpart for Lipschitz, smooth, and strongly convex function classes. These results provided the theoretical benchmarks for zeroth-order approaches over complex dy- namic networks. We also proposed multi-stage variant of the algorithm that better utilizes the learning rates and attains the connection between the convergence rates and the underlying communication complexity for distributed zeroth-order algorithms.
improved convergence rates. In future work, it is worth exploring

---

Under review as a conference paper at ICLR 2022
REFERENCES
Alckh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In COLT, pp. 28 40. Citeseer, 2010.
Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex opti- mization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 72-85, 2017.
Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lin, Mingyi Hong, and David Cox. Zo- adamm: Zrder adaptive momentum method for black-box optimization. arXiv preprint 1oX.::/910.06513. 2019.
John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions Information Theory, 61(5):2788-288 2015.
Abraham D) Flaxman, Adam Tauman Kalai, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium Discrete algorithms, pp. 385-394. Society for Industrial and Applied Mathematics, 2005.
Davood Hajinezhad and Michael M Zavlanos. Gradient-free multi-agent nonconvex nonsmooth optimization. 2018 IEEE Conference on Decision and Control (CDC), pp. 4939 4944. IEEE, 2018.
Davood Hajinezhad, Mingyi Hong, and Alfredo Garcia. Zone: Zeroth order nonconvex multi-agent optimization over networks. IEEE Transactions on Automatic Control, 2019.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithm for stochastic strongly-conver optimization. In Proceedings of the 24th Anmual Conference on Learn- ing Theory, pp. 421-436 JMLR Workshop and Conference Proceedings, 2011.
Elad Hazan and Kfir Levy. Bandit convex optimization: Towards tight bounds. In Advances in Neural Information Processing Systems, pp. 784-792, 2014.
Dusan Jakovetie, Dragana Bajovic, Anit Kumar Sahu, and Soummya Kar. Convergence rates for distributed stochastic optimization over random networks. In 2018 IEEE Conference Decision and Control (CDC), pp. 4238-4245. IEEE, 2018.
Tor Lattimore. Improved regret for zeroth-order adversarial bandit convex optimisation. Mathemat- ical Statistics and Learning, 2(3):311-333 2020.
Sijia Liu, Pin-Yo Yu Chen, Xiangyi Chen, and Mingyi Hong. signsgd via zeroth-order oracle. In International Conference Learning Representations, 2019.
Sijia Liu, Pin- Yu Chen, Bhavya Kailkhura, Gaoyuan Zhang, Alfred Hero III, and Pramod K Varshney. A primer zeroth-order optimization in signal processing and machine learning: Principals, recent advances, and applications. IEEE Signal Processing Magazine, 37(5):33544 2020.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions Automatic Control, 54(1):48, 2009.
Angelia Nedic, Alex Olshevsky, Asuman Ozdaglar, and John N Tsitsiklis. Distributed subgradient methods and quantization effects. In 2008 47th IEEE Conference on Decision and Control, pp-
4177-4184. IEEE, 2008.
Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922-938, 2010.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
8

---

Under review as a conference paper at ICLR 2022
Yipeng Pang and Guoqiang Hu. Randomized gradient-free distributed optimization methods for multi-agent system with unknown cost function. IEEE Transactions on Automatic Control, 2019.
Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on Learning Theory, pp. 3-24. PMLR, 2013.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Anirudh Vemula, Wen Sun, and Bagnell. Contrasting exploration in parameter and action space: A zeroth-order optimization perspective. In The 22nd International Conference on Artificial In- telligence and Statistics, pp. 2926-299 2935.. PMLR, 2019.
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Projection-free distributed online convex optimization with of (T) communication complexity. In International Conference Machine Learning, pp- 9818-9828. PMLR, 2020.
Yinghui Wang, Wenxiao Zhao, Yiguang Hong, and Mohsen Zamani. Distributed subgradient-free free stochastic optimization algorithm for nonsmooth convex functions over time- varying networks. SIAM Journal on Control and Optimization, 57(4):2821-2842) 2019.
Xinlci Yi, Xiuxian Li, Tao Yang, Lihua Xie, Tianyou Chai, and Karl H Johansson. Distributed bandit online convex optimization with time-varying coupled incquality constraints. IEEE Transactions Automatic Control, 2020.
Deming Yuan and Daniel WC Ho. Randomized gradient-free method for multiagent optimization over time-varying networks. IEEE Transactions on Neural Networks and Learning Systems, 26 (6):1342-1347, 2015.

---

Under review as a conference paper at ICLR 2022
A
KEY LEMMAS
We first establish the basic convergence result for Algorithm | that is based on DistZOO g: (x; 6z), which plays crucial role in subsequent analyses. We will sometimes use i to denote a node in 1/ just to highlight the focus given node (but i" indeed may take any value in V and therefore is a generic node).
Lemma Let Assumption hrold. Let (x;;;; 6.) be a DistZOO that satisfies Definition 7 () and (ūi). Then, for any i E V and all T 2 1, there holds
Σ [B[((x.(t)] f((x))
[xx f((xx
T
[[If((x;, (x): (0))))
[A)
+ LsLS
2m
T
1
(x)
B
T
2
1=1
1=1
T-1 Σ
+ P224,
Bl (1;;
where Pı = 2N maxiev (1v + 2Na
iiml ||xx (1)I.. p2 = 2N
30
+ 4).
1-8
I-8
and (t) = ΣM" [Ixx(t) x=1 with Xavg (1) =
1/2 Σ N x (1). a (1 IN
2
and
1/B
4NT
Before presenting the proof of Lemma [| we provide the following two supporting lemmas. The first lemma characterizes the convergence property of the transition matrix induced by weight matrix (1) (see Nedic et al. (2008)).
Lemma Define the transition matrix as A(t 8 A(t)A(t 1)... A(E + 1)A(() for all
t t2 2 1, and write :t: A(t). A(t: : E) satisfies
1
(1: E)
S a
N
where a (1-
and 3 -(1 (1-
1/B
INT
AN
The second lemma establishes the accumulated disagreement for every node in the network.
Lemma 3 (Disagreement) Let Assumption 1 hold. For every node i E V, we have
aB
(1) x;(l < X (1) x;(1)]l
||xx(10]
1 B
T-1
3a
+ 1 - 3
Σ 7t Σ
(1)
where (tvg(t) = -5Ex((t
Proof. To simplify the presentation, we denote
N
v1(()= (((()),,))))
j=1
s;(t) = projx (Vv(t)) v.(t).
10

---

Under review as a conference paper at ICLR 2022
Step 3 in Algorithm I can be rewritten as
([t++)=v.(+ x, + 1] = v.( + st)).
Our analysis relies on the estimate of [|s which can be bounded as follows:
N (0){ > (A)) (x))
[|s((O]| S proix (v:(t))
Σ (0)),))) ==1
where the inequality is based on Step 3 in Algorithm | and (t)) is double stochastic (cf. As- sumption []. Using the non-expansiveness of the Euclidean projection (-) and the fact that (t=l(((t)) E X. we have
N [()| S Σ (A()) (x,(),,))
(6)
1=1
We now derive the general expressions for Xavg (t + 1) and (t + 1), respectively. For Xavg (t + 1),
we have
Xuvg (t 1) Xuvg (t) (x,;)))) + N (t).
Applying the preceding inequality recursively, we get
N
Xavg (t + 1) X1vg(1)
Σ neg (x,
>
s()..
(7)
Similarly, for x, + 1), we have
N (1]++1= = Σ ((: (1)
N (l: (x(106) +
t-1 N
Σ
Σ
A 10),ss()) + s.())
t=1 j=1
(8)
Combining and gives
N
1 [xx( +
1
||Xavg (++ 1) (t + 1)Il <
A(t: 1)1s
[A 0l.
me | (x, (1):
N
N
1
N
|A(I:++])] N
[|s,(e]] |s:(1)] +
Σ
[(s(
N
(9)
Combining the results in 6 9 and Lemma 2 leads to
N +3 Σ gl me Σ
[[Xavg(t (t 1) xt (t+++))l 1)11 S aB
Σ
[xxx
(x);
+ 4mp Σ
(x,
where we used the following relation, based on
6
[t)l+) + N Σ (+)ll < Σ (t)) < N N
N
N (t)s, (x)) $ 4m Σ
ll (x)( (1):
This implies that
Xxavg( (t) xx(())l S XXavg(1) (1) - (1)] +a a Σ
X (1)1l
Σ
(10)
T-1 1
N
T-1
+ 3a
Σ
Σ
m Σ
+
mc Σ
g (x, (t);
t=1 E=1

---

Under review as a conference paper at ICLR 2022
This, in combination with (T)), leads to the final bound.
[Proof of Lemma]
7 Denote
A(t) Σ (1)
E
(11)
We follow the standard analysis by deriving the general evolution of At)),
N A(t + 1)
N Σ EAAOOOO0
2
Σ
projx
[[ve())
x||
(12)
where the inequality follows from the non non-expansiveness of the Euclidean projection and the con- vexity of norm square funetion. Expanding the term further gives
N
A(t + 1) = A() + Σ (x): 2Tp
(0): x)
(13)
Taking the expectation both sides and using the following property of DistZOO (ef. Definition Ti)):
E (x,
(t)
further obtain
N Σ
- + vi
21p
(x(((xx((); fx(x;
1=1
(14)
which implies
T N
T [[A(O) - BIA(E + 1)
T
N
E ((); (x; <
E
g
x ((); 6,)11
2m
(15)
We turn our attention the left-hand side of 15). By adding and subtracting the term f((x; (t); 56) and using the Lipschitz continuity f, (ef. Definition Ii)), follows that
(1xx())))) Σ
f(xx L
xt,(t) x;-
which, together with [T]. yields
T
T
[[A(O] -
- [A(t +1]
- i(x; 0z)
21
(16)
Σ 1h Σ
L
[t,
(f)]
t=1
The desired result follows by relating the left-hand side to the original function f. using the dis- agreement estimate in Lemma 3 and setting x x*.
B PROOFS OF THEOREMS 1 AND 2
We first provide the the following lemma that characterizes the properties of the DistZOOs in 3
and (4) Its proof can be derived by resorting Flaxman et al. (2005): Shamir (201)). which omit here to save space.
Lemma 4 Suppose that Je E ( all i V. We have the following.
12

---

Under review as a conference paper at ICLR 2022
(i) For g there hold Pa 1 and
Cd
E [l (x)
where C = maxiev (1) + 5,,; with x;( E X and (t( uniformly drawn from 11 We have pa = 1 when fi E (s))
(ii) For TP (.), there hold pa and
E 1 (x:(t): 80ll - 3
where is some universal constant. In addition, Pa when fi ss)o
Now are ready to prove Theorems and
ii) First, using the property of the DistZOO R. (-) (cf. Definition | Qii)). it follows that
N
- Σ -l) (t)x s SNLy
(17)
Σ [x(xx) - fx(x;)0)) NL,0,
i=1
We now focus on the case of fa E 2t)) Combining with inequality (17 the results in
Lemmas I and gives
1 (LA
[[[((x((t)) - f(x')) S SPLL + 2NL,
8c Σ
+
27
1=1
(18)
1 + N
T1 82
+ N2NL,
Σ
1/p
8,
where we used the fact that 7/. is function of T and Jensen's inequality, i.e.
E [ (t); - [B[1] (4) (():)))113)) 1/2
Cd S
Substituting the explicit expressions of l) = का:7 and 8, マो. into (8) and dividing both sides by T. we find that
T (1) - = T1/4
Σ T
(19)
where we used the following inequality thet ΣT= 10 O(T)+a), Va + 11 The desired result follows by using the convexity of function f, i.e., T Σ f'xx,- (1)) 2 (T).
When fa E Fip (T,, 22) smo ( it follows from the property of the DistZOO g.op (.) (cf.
Definition ( that
N
Σ (x( (t)) - ((xx)(()))) - Nsy87
(20)
1 8
Σ - - 2
We then combine the preceding inequality and the results in Lemmas and I to get
(E[J(x- - s(x))) S spLL
No4
E (1)
2m
(21)
T +
T N
NC 82
Σ
Σ
2
82
[=1
13

---

Under review as a conference paper at ICLR 2022
In contrast with the bound in (18). the second term the right-hand side of (21) now becomes Nsy Σ o2, which gives much more space when choosing d;; show that the choices of
1s yield the optimal convergence rate 7m/3). 77 272/3 and 6e 5//5
(ii) When La E (ip(L,,,2) )*), we have the following result for Algorithm 1 running with DistZOO (.):
[xx((x f(x)) S SILL 2N
E 8e [[A
24
(22)
(2ad + paveda L
where we have used the bounds in (17). Lemma fii and Lemma 1 Then we can deduce from the terms 1 and IIT that the optimal choice of 77 is VT Hence, substituting the explicit expressions
1/2 for nh = var and 6t = vi into (2 dividing both sides with T, and using the convexity of function F, the desired bound can be concluded.
When f. [ip(L, n (s X.). it can be shown that the term (2 Σi= 6,) on the right-hand side of (2 is replaced by (Ns; Σ o2), because of (20). As we discussed in the case of f: [ xx) the convergence rate is determined by the terms involving 1 and n.T. Hence, nu the convergence rate is the same as that of the case when f; in only Lipschitz continuous. The proof is complete.
C PROOFS OF THEOREM 3 AND
First, we claim that for the DistZOOs g. and (-), the strongly convexity of Si implies the strongly convexity of its smoothed variant fi and its proof is straightforward. We now establish the basic convergence results for Algorithm running with g.p (-) and (.). It follows from (13 that
N
E [A(t+ + 1)] = B [A()]] + Mh
E (t)(;);)))
2m
(
x)]
S [A(( Ti Σ (x)
2m, Σ (L(f(((()): - -xxx))
(23)
where in the equality we used the relation E g (x.(; fx; (t) ) (cf. Definition 1 ii) and
in the inequality we used the strongly convexity of function ʃ. Summing the inequalities in 23 over = 1 to and regrouping the terms, we obtain
N
(f)()((()))))) fa(x)) -
l (x, (t::6)11
[E[)(t)] - - [[ - 1,)
2
m
1=1
N
(1 1-m -s B[A(1)]
Σ 7
E ((
Th
1 E [A(T + 1))-
B [[A(0]
7t-1 - ns 17t
2mp
(24)
By substituting the expression for nt pgy into
24h and dropping the negative term, it follows
T
N
T
N
Σ
[[f((x((t::)))
f(x)) - Σ n > B (x. (f): 6.1
(25)
2
[=1
14

---

Under review as a conference paper at ICLR 2022
Then, following the same lines as that of the proof of Lemma | and 8. (?),
we have that, for DistZ00s (.)
[[[((x)))) f(x²)) - Σ B[1f(x)
f(xx;60)
E
- (xxx)))))
N B
T-1
N B
+ +p +
+ p2l, 7
(x
61]]
(26)
(i We now derive the convergence rate results for Algorithm
|
running with DistZOOs BPP(.)
When fi Fip((L,, n (1, we combine the results in
17 26 and Lemma i) to get
T Σ [x][(x - f(x)) s p1 + 2
T
Σ o
N
e
Σ NI,
T
T
8
By substituting 7/+ - jyt and 6, = γ. into the preceding inequality and using the convexity of F, it yields the following optimal bound
T
(t)x f(x')) (
d2
T1/3
When / E Fip(Ly; (0) n F am (8 x²) n Fec )²), it follows from an argument similar to that of 21 that
[(((x((1)]] - f(x*)) S PILL Ns; Σ 8 + 1
N
d
Tle + L
m
8z
1 yields the optimal convergence rate, that is, can be proven that the choice of 6, = पा7
(ii) The proof for Algorithm|| | running with DistZOO g. (.) can be obtained in similar way by exploiting the properties of the DistZO0 (-).
D PROOF OF THEOREM 5
We provide the basic convergence result for each stage k; and we start by deriving a similar bound as that of Lemma as follows:
(T())
[B[ (k) (1)) - [(x))) Σ B[][(x))
f(x); +
Σ
(8) (1)) f(x! (k) (1); 8()))
(T)))
E [A(k).(() (t) - E |A (k) (t + 1)]
+ +P1 Ls
(K)
+
1
T
(A)
E
g (x (1) (t); 1(
(x)(
2
1=1
T(k)
+ 12
Σ
17 (8)
E
[|||: Lg
(x: (k) (t);
1=1
(27)
where (t)
1x
(1)
(t)
x* 1|2 and p (k)
satisfies the following bound, according to
compactness of the set
X,
Pi
(l)) = -2N max [1x00] (1) - x. NVV
(1)Il 2Na8
(k))
Σ |x (2) (1)II
N
S 4N
1 - 1- g/2) Rx.
2aB
1- 3
(28)
15

---

Under review as a conference paper at ICLR 2022
The left-hand side of (27) can be further bounded by using the strongly convexity of F, that is,
( (V](x)),
(T(K)) (T((t) -x*)
Nus
(k) (T((k) x=12
T(K)
2
Applying the first-order optimality condition to the preceding inequality, i.e., (VF(x*), x-xx)),x-xx) 20 for any E X, yields
2:0 T(R) Σ (F6x
Nus (1+1) (1) -x1-
z
(29)
where the second inequality follows from the ee-eeaanniveeess of the Euclidean projection pr and the last equality from Step in Algorithm 2 Combining the inequalities (27) 28
and 29 we have for any 8 E V.
X ( (1)
Nuf E (1) 1x1
+ (NN + 2003 x-) Rxx T(k)
2
(R)
T(())
T [[[( ;(x);
B [[] (00(xx((())))) (1) f(x (1); (1))))
+
T())
T(k)
N
((k)
N
(b)
Σ
E Ex
( (x.
(t):
p2L1 T(K)
(1)
E
El
g (x) (2) (t); ((0) |I]
k
(30)
From 30 we find that the convergence depends on the properties of the DistZOOs, and we first
derive the dimension-dependdnnce error bounds for DistZóO gi (-) and the bounds for g! T.P()) nat-
urally follows from the derivations.
g. For DistZOO SPP(.), (-), when fi E Fin BRy) n Fec BR,), it follows from Lemma i)) that
17
30 and
E
max {1Ix (++ 1) (1) - -x11 s E
iEV
max iEV
{||x (*) (1) xx [1]]
(TT()))
(31)
4 L g(k) + (2 2 1 - 3
a
Lif
L Cd (K)
(h)
N
Rx T(k)
+ 2p2
21 g1k) + c
(000)22
On the other hand, we have
(Kk) = a² 8- (T()
(k)
ah- ")
5(h) 1
8 (()
(32)
This, together with incquality 31 gives
E max iEV
{||x (k+1) (1) - x 113 < E
max EEV
[[x({((1) - -x11p] (
1
(4_18()) -4(2 2+ 1 Ms
ag
L Rx T()
(min {a, b, 6. 1)))
k- x
us
(33)
Ls
Ca
1
c2 171))
+ 2p2
+
8a)
(8(1)2
4 min fainfb,.53 (b,0) and 8(1) into the preceding relation,
By substituting (1) 1, () arrive at
3ps
max
V { [|xx! (1((+(+()()))) (x)=])]]]]]
$
max
4 4in 6, +t {|x] (1) x*1²]]
+
Ri (min {b, az k-1
(34)
16

---

Under review as a conference paper at ICLR 2022
where have used the fact that min {a, b, g. } min {b, B. J. due to > 8² (because of @
> 1) and > 1, and
R1 4 Ls 800) + +a (2+
aB B us
Ls
+ +p2 Ls ca
Ms 8()) + 1 ca na
Rx T())
Hy
1
Ms (8(1)22
We next show by induction that
4 max { RR, R3g
E
max REV
{1|x (1) (1) - x* |2}
(35)
ha-2
where h = min {b, f }.. For = 1, we can use the following bound to deduce that inequality
35
holds, max;v {||x (1) x1] S 4R3 I 4h max ( (R1, R&g). We then assume that inequality
35
holds for l and show it holds for k + 1 as well,
3
R 4 m R2
max VVV
{|x} (++1) (1)
(1) - - |1}
4h
max EVV
{1xx
x'11]] (1)-xx113)
+
h4-1
3 max R1, R3}
max[R], R&c) S
h--1
h4-1
which leads the conclusion in (35). is easy to verify that the total number of stages in Algorithm
2 is k = loga ( + +1]. , and the final estimates returned by Algorithm aare (T:))), i E V. Hence,
applying k 1 to (35. we have
4 4 ( R&. hk:41-2
4h max R1, R&
4h2 max R2, R
E max (T) x* |p}
1008((
T + lngg
(36)
where we used the inequality that A4 > log, (I +1) - 1. We are left to find the minimum of logn( (a) = 1og (b. 22) } (a), which is achieved when = f2 This yields the following final conver-
gence rate, that is, E max (T] x 12]
4b max n. ned 0
(T+1)
(T+1)))3
de
where the
equality follows from Ri 0 (d.)
When fa E Fiip (Ly, BRR) 5 (8,, BRx) ) n JF BRx). ). the dimensiin--dependdncc bound can be obtained in similar fashion.
For DistZOO TP (-), when fi E Fip(Ls, )xx) n Foc Bxx), it follows from 0 30 and Lemma ii)) that
EE max {|Ix (A (++)) - xx 1||]]] <
{1xx (+) (1) - [1 (y
max iEV
iEV
(37)
+ 4 1 + 4 2 -- 3
aB
L1 Rx T())
1
+ 13
(od + 2p vovd ()))
N
My
By setting b = a and then substituting (() = 1, (1
4a and 8(1) = into the preceding 3ns
=
inequality it follows that
E max (1|x (k+1) (1) (1x xx1]]] < E
max iEV
(1|x (K) (1) - x11]]]
-x-1==))
3
+
R₂ ak
(38)
sEV
4a
where R₂ 4 my an argument similar to that of part (i), we obtain
g(1) (2+ 29 Ls Rx pbo
13 (od + 2p vcvd) () Then, following
My
4a² max R2, R 0 (T) -x 121 <
d
E max NEV
T+1
T+1)
Similarly, when S E (L,, BRx) n Fss BRx) n FFccluy Rx we have
max E
LEV { (T) - x [12)] v
4a² max (iax R2 0
d
T 1
T+1
where Rt/- = (0 + 4 2 23 Le Rxx रoos + xs
(dd + 2p2 Vepve 17 The proof is 12
complete.
17


Reviews:
[{"review_id": "wSwQe5M0gU1", "reviewer": "Reviewer_5m6d", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength: \nIt seems that this paper provided new convergence results for the decentralized setting.\n\nWeakness: \n1. However, the related works are not well-compared or missing. So it's hard for me to judge the results of this paper. For instance, in Table 1, \n- the results for the Lipschitz class clearly also hold for Lipschitz and smooth class; \n- the non-accelerated result for the smooth class is $O(\\frac{d}{T})$ (see, e.g., [1, 2] via directional derivative), and also accelerated result $O(\\frac{d^2}{T^2})$ is obtained in [2] via two-point gradient estimators. Both results are much better than the one in the current submission, but the authors did not list and compare with them.\n- for the strongly convex class, the convergence rate is linear (e.g., [2] provides the accelerated rates $\\Big(1-\\frac{\\sqrt{\\mu_f/s_f}}{d}\\Big)^T$ ), while the authors listed the much weaker sublinear results in Table 1.\n-ps: I do not think the constrained/unconstrained domain will affect the comparison with results of [2], since the current submission directly uses the non-expansiveness of the Euclidean projection **proj**($\\cdot$) in their proofs (see Page 11-12)).\n\n\n2. The authors consider the decentralized setting, however, their convergence results (see Table 1 and Theorems 1-4)  do not depend on any parameters (e.g., spectral gap) regarding the decentralized network topology. so it's also hard for me to believe the correctness of their results.\n\n\n\n[1] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. *SIAM Journal on optimization*, 19(4):1574–1609, 2009.\n\n[2] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. *Foundations of Computational Mathematics*, 17(2):527–566, 2017.", "summary_of_the_paper": "This paper studied zeroth-order methods via one-point and two-point gradient estimators for decentralized optimization.", "summary_of_the_review": "The comparison of results is not appropriate and accurate. Also, their results look strange (e.g., do not depend on the parameter of network topology). So I recommend a reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jsCjQvKUdr9", "reviewer": "Reviewer_fRi4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "0. This paper is well organized and clearly written. The results seem to be reasonable.\n1. The proposed algorithms look like simple extensions from the first-order to the zeroth-order. The authors should highlight the novel contributions of this paper. Are there any particular challenges in analyzing the zeroth-order algorithms, compared to analyzing the first-order ones?\n2. The communication graph should play an important role in the established convergence rates, but the main theorems fail to clarify this issue. Detailed discussions would be helpful.\n3. In the first paragraph, the authors motivate with applications like adversarial attacks in deep learning and policy search in reinforcement learning. However, the numerical experiments end up with a simple least squares problem. More extensive numerical experiments are necessary.\n", "summary_of_the_paper": "In this paper, the authors develop a distributed zeroth-order algorithm over a time-varying communication graph, as well as its multi-stage variant with time-varying step size. Convergence rates are established and compared with those of the centralized algorithms.", "summary_of_the_review": "Overall, this paper has disadvantages in novelty, depth of analysis, and numerical experiments.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H251C_YV7e", "reviewer": "Reviewer_JpXi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "This paper is well written and the theoretical results are solid. I have a few concerns as follows,\n\n- The novelty of this paper: the idea of both the MOZAPA and multi-stage MOZAPA algorithms are not novel. They all have their first-order counterparts and have been presented years ago. Although the authors do give credits to these previous work, the novelty of the two algorithms should be doubted as the only change in the algorithms is to replace the first order oracle with a zeroth-order one.\n\n- Some assumptions may need some explanation. In theorem 1 and 3, the authors present their results based on the assumption that $|f_i(x_i(t) + \\delta_t u_i(t))| \\leq C$, for all $i \\in \\mathcal{V}$. I understand this assumption is needed for one-point oracle, but we do need some explanation and comparison between the assumptions for OP oracle and TP oracle.\n\n- The comparison table on Page 3 presents some sub-optimal results for the centralized counterpart. For example, for a two-point oracle with strong convexity, the optimal rate should be $\\mathcal{\\tilde{O}}(d/T)$, if one refers to some previous work like Duchi et al. (2015). The sub-optimal rate should not be presented.\n\n- The numerical experiments are trivial and need improvement. The experiment is a toy example, with these theoretical findings, we do not expect very comprehensive numerical results, but at least run 100 MC simulations, instead of 10. We also need a comparison with the centralized zeroth-order algorithm.", "summary_of_the_paper": "This paper proposes a zeroth-order optimization algorithm for distributed, multi-agent systems with time-varying communication networks. The authors show that their presented multi-agent zeroth-order projection averaging algorithm (and its improved multi-stage version) has a convergence rate that matches the centralized counterpart algorithms under different assumptions. A small numerical experiment is also conducted to illustrate their theoretical findings.", "summary_of_the_review": "This paper presents some rigorous theoretical findings for the distributed zeroth-order SGD. However, my main concern is the novelty of this paper. There are some modifications needed on the assumtion and numerical experiments as well. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is about a topic that has been extensively studied for more than a decade, hence a very precise discussion of prior work as well as the new insights is absolutely necessary. Unfortunately both are lacking at this stage, thus the paper cannot be accepted.
Decision: Reject