Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors study the decentralized asynchronous optimization problem on a time-varying network with n nodes where the main purpose is to minimize the sum of  L-smooth and \mu-strongly convex functions distributed on the nodes. The authors decouple the computation and communication steps in the asynchronous optimization problem by modeling this problem as a union of two independent Poisson Point Processes and consider primal gradients in their proposed method. They show convergence results for this problem under the proper assumptions. They also present numerical results corroborating their findings in the convergence results.

strength_and_weaknesses: Strengths:
-The authors can achieve communication rounds and convergence complexity results by decoupling optimization (computation) from communication via two independent Poisson processes.
-The authors provide a clear statement of contributions and comparisons to the literature.
-A novel analysis of asynchronous communications via is provided in Section 3.

Weaknesses:
-The optimization results in Subsection 3.3 do not contain information on bounds for hyperparameters in the proposed dynamic in Subsection 3.2.
-The stochastic result (Corollary 3.2.1) shows a non-vanishing error in the rate. It is conventional to tweak the hyperparameters (e.g., a decreasing learning rate) to make this term vanish over time. It is unclear why this term is a constant and if it can be improved. The current format undermines stochastic optimization results.
-Numerical comparisons are limited to the ADOM+ algorithm. I recommend further comparisons with other algorithms, such as Gradient Tracking.

clarity,_quality,_novelty_and_reproducibility: -Throughout the manuscript, underlying assumptions are clearly stated.
-I recommend moving Algorithm 2 from the appendix to the main manuscript.
-The clarity of convergence results requires some improvements. The main technical contribution of this paper lies in the gossip analysis. However, the optimization results are not presented and elaborated sufficiently. I recommend expanding the discussion in Subsection 3.3.

summary_of_the_review: A new study on decentralized asynchronous optimization on time-varying graphs is made in this paper. By modeling the problem via Poisson processes, the authors present communication and computation complexity for their proposed algorithm. Some improvements in Subsection 3.3 are required to clarify the findings for stochastic optimization.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a decentralized asynchronous stochastic first-order algorithm DADAO to minimize the sum of strongly convex functions over time-varying decentralized networks. This paper develops the theoretical performance guarantee of a related ODE system and tests the empirical performance by numerical simulations. 
strength_and_weaknesses: Strength: 

1. The proposed algorithm achieves new performance guarantees in both communication edges and gradients.

Weaknesses:

1. Theorems 3.2 and Corollary 3.2.1 provide guarantees for the ODE system Eq.(3) and Eq.(8), respectively. However, because ODE considers a continuous-time regime, it is not obvious whether these results still hold in practical discrete-time implementations. The discrete-time performance guarantee has been shown in prior works (i.e., Theorem 4 of [1]). It would be beneficial if the performance guarantees of discrete-time GD and SGD algorithms can be provided, which is provided in prior work. 

2. Theorem 3.2 considers the case where $\chi_1^* \chi_2^* \leq 0.5$. This assumption seems to be a bit restrictive because the constants $\chi_1^*$ and $\chi_2^*$ depend on the network itself. It looks that ADOM+ in [1] does not need such a restrictive assumption to ensure convergence. It would be helpful if an additional explanation can be provided to justify why such an assumption is required. It would also be beneficial to discuss whether similar assumptions are required to the mentioned benchmark algorithms. 

3. Theorem 3.2 shows the existence of the parameters $\alpha,\gamma$ but does not specify how these parameters should be chosen in real networks. It would be helpful to specify the choice of these parameters. Also, does  $\gamma$ refer to the same quantity in Table 1? 

4. Corollary 3.2.1 introduces an additional bias term $\frac{C_1}{\sqrt{\mu L}}$ to characterize the SGD system (8) in a continuous-time regime. It is claimed that "$L$ allows to adjust the trace-off bias-variance of the descent". This seems to be a bit confusing because $L$ represents the fixed Lipschitz constant. If one considers a larger $L$ to reduce this term, the decay rate of the term $C_0 e^{-ct\sqrt{\mu/L}}$ would deteriorate as well. It would be helpful if the authors could elaborate more on this. 

5. When comparing DADAO with ADOM+, it is claimed that ADOM+ has potentially substantially higher expected communication than DADAO. It would be beneficial if the paper can specify the referred scenarios. 

6. Various benchmark algorithms are tested in the numerical part. However, it seems that MSDA also has comparable performance with the proposed DADAO algorithm in most of the scenarios. Could the authors provide additional numerical experiments to demonstrate the efficiency of DADAO? It would be helpful if numerical experiments in some special cases such as star or complete networks can suggest DADAO's superior performance.

Minor Issues: There are some typos and some quantities are undefined. 

1.  In the abstract, the $O(n \sqrt{\frac{L}{\mu}} \log \epsilon)$ gradient complexity is confusing. Should it be  $O(n \sqrt{\frac{L}{\mu}} \log \frac{ 1}{ \epsilon} )$ where $\epsilon$ is the precision? 

2. In Table 1, $\gamma$ is undefined so that a fair comparison between $\sqrt{\chi_1\chi_2} n $ and $\chi_1 |\mathcal{E}|$ is not obvious. 

3. When defining $\chi_2(t)$ in page 4, the quantity $\Lambda^+(t)$ is undefined. 

References: 
[1] Kovalev, D., Shulgin, E., Richtárik, P., Rogozin, A., and Gasnikov, A. (2021). ADOM: Accelerated decentralized optimization method for time-varying networks. 
clarity,_quality,_novelty_and_reproducibility: The problem setting is clear but the writing is not very good because of typos and missing definitions. The work seems to be novel. 




summary_of_the_review: This paper proposes an algorithm to solve decentralized strongly convex optimization and establishes some new complexity results. The results are developed for continuing-time frameworks, but the guarantees for implementable practical frameworks are absent. The theoretical claims are also only applicable to a restrictive class of problems. The overall contribution seems to be limited.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work proposed a decentralized asynchronous stochastic first order algorithm to minimize a sum of L-smooth and µ-strongly convex functions distributed over a time-varying connectivity network of size n. The authors model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, to decouple the computation and communication steps. The proposed method is differ from the majority of works since it does not use a multi-consensus inner loop nor other ad-hoc mechanisms such as Error Feedback, Gradient Tracking, or a Proximal operator.

strength_and_weaknesses: strength: the proposed approach is differ from the majority of works since it model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, to decouple the computation and communication steps. 

weakness: 
- the experiment setting with decentralized linear and logistic regression tasks is too simple to validate the effectiveness of the approach. 
- many importance factors of convergence rate are not clear, such as communication latency and linear speedup 
clarity,_quality,_novelty_and_reproducibility: writing is not very clear to follow
summary_of_the_review: The authors model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, which differ from the majority of works. The experiment is too simple for verification. The convergence analysis is lacking some important factors.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studied asynchronous decentralized SGD for strongly convex problems. The authors provide theoretical analysis for the convergence rate and conduct experiments to verify its performance. But the writing is not very clear. It is not easy to follow.
strength_and_weaknesses: Strength:
1. Theoretical convergence rate is established.
2. Studying the convergence from the continuous perspective.


Weaknesses:
1. The convergence rate in the abstract is wrong. 
2. Why is it necessary to study the convergence rate from a continuous perspective? Is there any benefit? For strongly convex problems, the traditional analysis can also establish the linear convergence rate. Moreover, in the appendix, I didn't find the authors use continuous tools to investigate convergence. Why do you introduce Eq.(3) and that in Section 3.3?
3. What's the meaning of $\chi_1$ and $\chi_2$? How do they relate to the spectral gap?
4. How does the communication latency affect the convergence rate?
5. How does the spectral gap affect the convergence rate?
6. Can the convergence rate achieve the linear speedup with respect to the number of devices?
7. The experiment is too simple. More complicated models and datasets should be used to evaluate the performance. 
8. Asynchronous decentralized SGD has been studied before. But the authors missed some important literature, e.g., http://proceedings.mlr.press/v80/lian18a.html 
clarity,_quality,_novelty_and_reproducibility: Clarity: Poor
Quality: Poor
Novelty: Neutral
Reproducibility: N/A
summary_of_the_review: This paper studied asynchronous decentralized SGD for strongly convex problems. The authors provide theoretical analysis for the convergence rate and conduct experiments to verify its performance. But the writing is not very clear. It is not easy to follow.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work considers a decentralized optimization problem, and develops an asynchronous accelerated gossip algorithm to solve it. The strengths are in providing theoretical guarantees and the innovation of using Poisson processes to model the asynchronous time-stamps at which algorithmic updates are executed. The algorithmic approach is fairly similar to prior works, meaning the main contrast is in employing  the Poisson counters for modeling the asynchronous updates. The consensus opinion of the reviewers is that this is insufficiently innovative to meet the bar of novelty required for acceptance. I tend to agree that this problem is so well-studied, additional efforts must provide a substantial departure so as to not retread past works. That this is the case is evidenced by the diversity of references called out by the reviewers, which have minimal overlap with one another. Unfortunately, this paper does not qualify as a substantial depature.
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Reject