Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the convergence distributed linear SA under Markovian sampling. Both asymptotic and non-asymptotic convergence rate results are provided. This paper consider the setting in which the agents interact over a time-varying directed graph, which extend previous studies. Overall the results in this paper is solid and has some technical contributions.
main_review: Overall I think the results in this paper is solid and should be some interesting to the community. I have the following comments about the paper.

(1) Only convergence rate is characterized in the main theorems. It would be better to see the sample complexity result (total number of samples that required to achieve $\epsilon$-accuracy level) so that the readers can compare the contributions in this paper with the state-of-art.

(2) Although it is a theoretical paper, empirical verification is also suggested even with toy example.

(3) As claimed by the author, the dependence on some conditional numbers is not clear. However those conditional numbers could affects the convergence rate significantly. A detailed discussion about those numbers would makes the paper more convincing. 

-------- after rebuttal ---------
In the discussion, since the area chair and reviewer AANE raised some concerns about assumptions and the author did not address these concerns convincingly, I change my score to weakly reject.
limitations_and_societal_impact: This paper does not have potential negative societal impact
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This submission considers finite-time error analysis for distributed linear stochastic approximation (SA) algorithms under the assumption that the interconnection matrix is stochastic. In addition, leveraging the idea from “push-sum” based approaches, a novel Push-SA algorithm and the corresponding finite-time error bound are devised for directed interaction graphs.
main_review: Strength:
This paper relaxes the commonly adopted assumption that the interconnection matrix is doubly stochastic to a more general one. The assumptions and results obtained in the work are well explained relative to existing works. 

Weakness:
The motivating context concerns the application of SA approximation in reinforcement learning (RL).  It is suggested to briefly discuss how SA is applied in RL, for example, TD learning.

Some typos to be fixed:
Line 36, “arguably” —> “inarguably”;
Line 37, “differing” —> “different”

-------- after rebuttal --------- 
Thanks for the reply! After reading other reviews and the committee discussion, I decide to change the score to weakly reject, which is in agreement with other reviewers, who raise detailed and constructive concerns.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies a distributed linear stochastic approximation algorithm. The interconnection structure among the agents is described by a time varying directed graph. Under the setting of Markovian samples, the main contribution is to characterize the finite time error bound on the mean squared error. The analysis is applied to study a push-sum version of distributed linear stochastic approximation. 
main_review: As mentioned, the main contribution is a new analysis on the distributed linear stochastic approximation algorithm given in (1), encompassing constant stepsize and time varying step size, Markovian samples. To achieve this, the study introduces a technique known as the absolute probability sequence to track the evolution of error in light of the time varying directed graph which results in a row-stochastic interconnection matrix. This technique can be interesting as it leads to a simple recursion of the iterates in (4), simplifying the subsequent analysis.

However, there are a number of drawbacks which outweigh the benefits of the current paper, as discussed below:

- Though the paper title reads "distributed linear stochastic approximation", the algorithm in (1) only considers a restricted setting with an identical driving matrix $A(x)$ across agents (and different $b^i(x)$ across agents). This setting may be suitable for the distributed policy evaluation problem where a number of prior works have appeared, but it does not include many interesting cases for distributed linear stochastic approximation including classical ones such as linear regression. In this regard, the paper may better position itself as a paper for distributed policy evaluation insteado of the more general linear stochastic approximation. 

- The main theorems (Theorem 2 & 3) require Assumption 6 which is not well justified. Particularly, this assumption requires the absolute probability seqeunce to admit a limit vector. The Remark 3 which follows the assumption fails to provide a convincing case for this assumption to hold. Therein, two examples are given: the case $W_t$ is doubly stochastic is rather trivial as it defies one of the main relaxation considered in this paper; the case when the number of neighbors of agents are unchanged over time (also, is it the number of out-neighbors? or in-neighbors?) appears to be too artificial. The paper shall include a more concrete construction on how the assumption holds. 

- In addition, it is not clear what are the benefits of employing the absolute probability sequence technique in analyzing the convergence of distributed algorithms, e.g., when compared to the classical approach in [52] for the push-SA algorithm. As for the convergence to a weighted average of the equilibrium point when a row-stochastic mixing matrix is employed, some relevant work can be found in the static graph setting, e.g.,

-- J. Chen, A. Sayed, "Distributed Pareto Optimization via Diffusion Strategies", IEEE Transactions on Signal Processing, 2013. 

- The presentation of the main theorems lacks useful information that a finite-time error analysis should encompass. For instance, it is mentioned that "$C_2$ depends on $L, \gamma_{min}, \gamma_{max}, A_{max}, b_{max}$ ..." which does not describe how small/large the bound is - in fact, without a more detailed description, the bound in (7) is not useful since $C_2$ can be large; the result for push-SA is summarized in Theorem 5 *only* for the case of time varying step size, and it is mentioned that "our current analysis approach cannot be directly applied for this case" which lacks further expatiation; in theorem 3, how does that the convergence rate of $\eta_t$ affects the finite time error bound in the constant step size case? 

---
**Post Rebuttal**

The reviewer appreciates the detailed response from the authors. Unfortunately, the response has not addressed my previous concerns and therefore my previous evaluation stands. In particular, the promised "simulation based" study will not be very convincing since cases which violate Assumption 6 may still include a lot of cases. Instead, it would be better to construct an **analytical** example to illustrate the necessity of Assumption 6. In summary, my main concern is that Assumption 6 and its corresponding analysis due to the "absolute probability sequence" is one of the main innovations claimed in the paper, yet its applications are so far only limited to the previously known cases. 

Moreover, while it is acceptable that $C_2$ can be a large constant, it is also important to point out **how** does $C_2$ depends on the system parameter $L, \gamma_{min}, \gamma_{max}, A_{max}, b_{max}$. The current presentation has so far eluded from discussing about that. 
limitations_and_societal_impact: There isn't any potential negative societal impact. The limitation/suggestions for improvement have been discussed in the main review above.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: An interesting submission dealing with distributed stochastic approximation driven by Markovian noise, in which the communication topologies considered among agents are captured by a stochastic matrix (in contrast to the doubly stochastic matrix studied in the related literature). Both asymptotic and finite-time error bounds are established and it was shown that the algorithm converges to some unspecified convex combination of the equilibrium points of local tasks. This paper finally proposes a push-type distributed stochastic approximation algorithm and provides its finite-time bounds for the performance by leveraging the analysis for the consensus-type algorithm with stochastic matrices. All analysis and error bounds are directly applicable to distributed TD algorithms.
main_review: Originality: This paper studies distributed Markovian stochastic approximation algorithms with stochastic interconnection matrices, which has not yet been covered in the related literature. The results are a bit different than what is known for related algorithms having doubly stochastic interconnection matrices. Further, a push-type algorithm is proposed for decentralized implementation. 

Quality. The results are technically sound and theoretically supported. The algorithm proposed is also new.

Clarity. The paper is well written and easy to follow. The results are nicely organized and the contributions relative to existing works are clear too.

Significance. The results are important and complement the existing distributed Markovian stochastic approximation results which have only focused on doubly stochastic interconnections among agents. The tools developed for analysis may also be useful for further use. 
limitations_and_societal_impact: Numerical simulations may be provided comparing the proposed algorithm and existing ones as well as validating the proved finite-time error bounds for both constant/time-varying stepsizes.
review_title: null

Meta-review: The paper has received some discussion among the reviewers, with a weak consensus centering around rejection. A key concern is the presence of Assumption 6 in the paper. This issue has received substantial discussion with a lengthy reply from the authors. Nevertheless, I believe the authors have not successfully rebutted the concerns raised. 

To summarize the main contribution of the paper: existing analysis of distributed stochastic approximation are based on doubly stochastic matrices. The authors propose an analysis which can handle more cases, based on so-called absolute probability sequences, which is where Assumption 6 comes into play. However, the main concern is that the applicability of these new results is quite narrow. 

The authors list two cases where their results are applicable: (i) when all the matrices appearing in the algorithm share the same left-eigenvector (ii) when the matrices in question change until time T, at which point they remain constant. However, generalizing existing results from doubly stochastic matrices to cover case (i) is quite easy. The authors implicitly point out the key element of this in their response, which is that in this case we can write down a quadratic Lyapunov function using the quantities pi as coefficients -- there is no need for an absolute probability sequence. 

This leaves only case (ii). But if this is the main case where the results of this paper apply, the applicability already is quite narrow. Additionally, while in this case the authors remove scaling with the time T, they add a scaling with pi_{min} because the errors are scaled by pi_{min} in the bounds. There are bounds in the literature for this quantity which are exponentially small in the number of states; for example, see the proof of Theorem 4 in Touri and Nedic,  ''On the existence of a quadratic comparison function...", Proc. CDC 2011. So even in this case, it is not at all clear the results are better than the naive approach of simply applying existing bounds after time T; rather, there are tradeoffs.  Thus I believe this paper does not make the cut for NeurIPS. 

My suggestion to the authors for future submissions is to center the paper around their second main result, Theorem 5, provided it has good applications in distributed ML (this would need to be convincingly argued). 
Decision: Reject