Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
main_review: This paper is well written and the theoretical results are solid. I have a few concerns as follows,

- 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.

- 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.

- 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.

- 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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studied zeroth-order methods via one-point and two-point gradient estimators for decentralized optimization.
main_review: Strength: 
It seems that this paper provided new convergence results for the decentralized setting.

Weakness: 
1. 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, 
- the results for the Lipschitz class clearly also hold for Lipschitz and smooth class; 
- 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.
- 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.
-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)).


2. 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.



[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.

[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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: 0. This paper is well organized and clearly written. The results seem to be reasonable.
1. 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?
2. 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.
3. 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.

summary_of_the_review: Overall, this paper has disadvantages in novelty, depth of analysis, and numerical experiments.
review_title: null

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