Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: ## Summary

I do apologize for delaying the review process. I do spend lots of time and carefully read the paper. All comments listed below intend to help authors improve the quality of the manuscript. They are based on my understanding which might contain misunderstanding points if any. I hope comments are helpful and even the critiques are not discouraging your endeavor in the following.

First of all, the manuscript proposed an on-line push-sum algorithm to handle the decentralized SGD with the single-sided constrain. A rigorous regret analysis is provided for the proposed algorithms. The detailed comments are listed in the following.


## 1Major Comments:

- The motivation of the manuscript is really strange. The authors mentioned that they considered social network scenarios many times. However, the explanations and discussions are falling in the edge server setting.
- They proposed the online push-sum algorithm which is generalized from Tsianos (2012). I still cannot understand why the online push-sum algorithm is a federated learning algorithm. From my perspective, it is only a generalization of the push-sum algorithm in the online setting with single-sided trust constrain. Could you please show me the special feature of your setting?
- They provided a regret analysis of the proposed algorithm. However, the authors never showed that the contributions of the proof skill.
- In the simulation study, could you please show the network structure you proposed?

## 2 Minor Comments
- Page 2, Notation. You should introduce $n$ first, before the confusion matrix.
- Page 2, related work: the citation of Stich (2018) and Wang and Joshi (2018) is not corrected.
- Page 5, you should explain the “strongly connected” in Assumption 1 detailedly.

review_title: Decentralized algorithm, but less consider the federated learning setting

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This work focuses on single-sided decentralized federated learning. The authors propose a push
sum-based algorithm to relax the symmetric matrix assumption, which leads to a flexible
decentralized training on a directed network graph. The authors analyze the regret bound, as well as
run some numerical experiments to demonstrate the correctness of the proposed algorithm.
***Strengths***:
Overall the paper is well written.
1. The proposed method bridges a gap between existing decentralized federated learning algorithms
and real single-sided social networks. Another example I can recall is that sharing in the data market
is single-sided. The motivation is sound. ​As far as I know, this is the first paper in the FL community
talks about this setting.
2. The authors design a novel algorithm. Its theoretical results of the convergence rate ​connect
"online learning" and "asymmetric graphs", which is novel in federated learning.
3. The experimental design is excellent (including many settings). The code is very readable and
well-documented. I believe this helps the popularity of this proposed algorithm.
***Weakness***:
I can understand that this work focuses on the algorithm rather than provides a privacy guarantee.
So it would be great if the authors provide some intuitions or discussions about how to address
privacy concerns.
I prefer to demonstrate the proposed algorithm on more challenging datasets, but since this work
emphasizes the convergence analysis, it should be OK for me.
The authors only mention an important work in the related works section: “Notably, Zhao et al.
(2019) shares a similar problem definition and theoretical result as our paper. However, single-sided
communication is not allowed in their setting, restricting their results”. I suggest the authors discuss
more about it and distinguish the contributions in theory analysis.
Related works:
“Stochastic gradient push for distributed deep learning” (ICML 2019) should be discussed.
In section 4.4, more privacy-related works should be mentioned.
Overall Rating
Since the theory in this work is sound and the experimental design and code implementation are
also excellent, I incline to strongly support the acceptance of this work.
review_title: This work focuses on single-sided decentralized federated learning. The authors propose a push sum-based algorithm to relax the symmetric matrix assumption, which leads to a flexible decentralized training on a directed network graph. The authors analyze the regret bound, as well as run some numerical experiments to demonstrate the correctness of the proposed algorithm.

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################

Summary:
 
The paper proposed Online Push-Sum (OPS) method, which aims at solving decentralized federated optimization problems under a social network scenario where the centralized authority does not exist in a federated learning (FL) system. A social network application scenario is assumed by OPS where the graph is of single-sided trust. The author further extends the proposed OPS method to the online setting and provide regret analysis. The experimental study indicates that OPS is effective and converges faster than other decentralized online methods.

##########################################################################

Reasons for score: 
 
Overall, I think the current manuscript is marginally below the acceptance threshold of ICLR conference. Studying the effectiveness of the central server free federated learning algorithm is a promising direction. The proposed algorithm is interesting and is with theoretical guarantees. However, the major concern is that the problem setting may not be novel enough. Moreover, the experimental justification of this paper can be improved.
 
##########################################################################

Pros: 
 
1. The paper is well written. The research direction on studying central server free federated learning algorithms is promising.
 
2. The formulation and theoretical analysis of the proposed OPS method looks promising.
 
3. Experimental results under simulated federated learning under the social networking environment are provided to show the effectiveness of OPS.
 
##########################################################################

Cons: 
 
1. The major concern on the proposed OPS method is its novelty. A series of central server-free federated learning algorithms have already been developed e.g. [1] and it seems the main contribution of OPS is to study one specific setting e.g. decentralized FL under the single-sided trust social network graph. Thus, the authors are expected to show either that OPS outperforms the previously proposed methods or its capability to handle a completely new area. 
2. OPS seems to follow the Push-Sum algorithm [2], but is also extended to the online setting. But it is not quite clear why the online setting is important in the decentralized FL scenario. 
3. The experimental justification of the proposed method is limited to linear models. However, most of the modern machine learning tasks are running over more complex models e.g. neural networks. The authors are highly encouraged to extend the scale of the experiments. 

[1] https://arxiv.org/abs/1905.09435
[2] https://ieeexplore.ieee.org/document/6426375

 
#########################################################################

Minor Comments: 
1. Missing references: [1-2]. 

[1] https://arxiv.org/abs/1912.04977
[2] https://arxiv.org/abs/1908.07873
review_title: Interesting paper, but may not be novel

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Paper Summary:** This paper proposes a decentralized federated learning algorithm called Online Push-Sum (OPS) for peer-to-peer learning in the context of social networks with the property of single-sided trust . 

**Questions for the authors**
1. Sec 1, it is mentioned that “Only models rather than local gradients are exchanged among clients in our algorithm.” My understanding is in most of the federated learning algorithms, either model parameters or difference of model parameters are exchanged (also noise can be added on top of them to guarantee differential privacy). So, it would be great if the authors further explain why this is a feature of their algorithm worth highlighting.  
2. Maybe I have missed it, but in Sec 4.1, why do we need an extra parameter (i.e., $w_{t+1}^{i}$) for normalization? Why can't we just use the summation of the weights (i.e. $W_{ki}$) to do the normalization ? Can you explain further?
3. Sec 4.3, one assumption of the proposed algorithm is that the graph is strongly connected. I am afraid this may not be the case in practical applications. Fully decentralized algorithms for learning should be robust to the limited availability of the clients/nodes (with clients temporarily unavailable, dropping out or joining during the execution) and limited reliability of the network (with possible message drops). Interested to see the authors’ thoughts on this. 

**Novelty**
The paper to me seems an incremental extension of the previous work (Zhao et al., 2019), and I think the novelty is a little thin.

**Areas to Improve**
I think it would be good to compare the proposed method with other existing Federated Learning methods such as (Dinh et al. NeurIPS, 2020) as well. 

**Minor Concerns**
Page 2. Notation section. “denoting the sets of in neighbors of and out neighbors” -> "denoting the sets of out neighbors of and in neighbors" ?

**References**
1. Personalized Federated Learning with Moreau Envelopes (Dinh et al. NeurIPS, 2020)
2. Peer-to-peer federated learning on graphs (Lalitha et al. 2019). This is a relevant paper which is missing.
review_title: The studied problem of decentralized federated learning in the context of social network seems to be interesting, but I think the novelty is low.

Meta-review: The paper studies federated learning in what they call ```'single-sided trust' scenario, i.e. there is no dedicated server and the trust relationship is asymmetric.

This paper was a trickier case to decide on, and more borderline, in our opinion, than the reviewers' scores suggest, primarily, because the reviewers' recommendations are based on more subjective notions of novelty and importance/appropriateness of the studied setting, rather than identifying specific flaws in theoretical analysis or experiments. Ultimately, it boils down to three reviewers being (rather) negative about the paper, and the only (very) positive reviewer not stepping in to champion it. The negative reviewers believed that the novelty is not substantial enough to meet the high ICLR acceptance bar  (see details in reviews by R1 and R2 re similarity to ) and also have questioned the general motivation  (R1) and/or the online learning setting (R3).  While this assessment may be too harsh (esp. R1) - I think that the paper has merit - I share their feeling that in its current form it does not have a strong enough contribution. 



Decision: Reject