Central Server Free Federated Learning over Single-sided Trust Social Networks
Authors: Chaoyang He
Conghui Tan
Hanlin Tang
Shuang Qiu
Ji Liu
Venue:  (2021)

Abstract: Federated learning has become increasingly important for modern machine learning, especially for data privacy-sensitive scenarios. Existing federated learning mostly adopts the central server-based architecture or centralized architecture. However, in many social network scenarios, centralized federated learning is not applicable (e.g., a central agent or server connecting all users may not exist, or the communication cost to the central server is not affordable). In this paper, we consider a generic setting: 1) the central server may not exist, and 2) the social network is unidirectional or of single-sided trust (i.e., user A trusts user B but user B may not trust user A). We propose a central server free federated learning algorithm, named Online Push-Sum (OPS) method, to handle this challenging but generic scenario. A rigorous regret analysis is also provided, which shows interesting results on how users can benefit from communication with trusted users in the federated learning scenario. This work builds upon the fundamental algorithm framework and theoretical guarantees for federated learning in the generic social network scenario.

Under review as a conference paper at ICLR 2021
CENTRAL SERVER FREE FEDERATED LEARNING OVER SINGLE-SIDED TRUST SOCIAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning has become increasingly important for modern machine learn- ing, especially for data privacy-sensitive scenarios. Existing federated learning mostly adopts the central server-based architecture or centralized architecture. However, in many social network scenarios, centralized federated learning is not applicable (e.g., central agent server connecting all users may not exist, the communication cost to the central server is not affordable). In this paper, we consider generic setting: 1) the central server may not exist, and 2) the social network is unidirectional or of single-sided trust (i.e., user A trusts user B but user B may not trust user A). We propose central server free federated learning al- gorithm, named Online Push-Sum (OPS) method, to handle this challenging but generic scenario. A rigorous regret analysis is also provided, which shows inter- esting results on how users can benefit from communication with trusted users in the federated learning scenario. This work builds upon the fundamental algorithm framework and theoretical guarantees for federated learning in the generic social network scenario.
INTRODUCTION
Federated learning has been well recognized a framework able to protect data privacy Konečný eet al.] (2016); Smmth et al. (2017a): Yang et al. (2019). State-of-the-as federated learning adopts the centralized network architecture where a centralized node collects the gradients sent from child agents to update the global model. Despite its simplicity, the centralized method suffers from com- munication and computational bottlenecks in the central node, especially for federated learning, where a large number of clients are usually involved. Moreover, to prevent reverse engineering of the user's identity, a certain amount of noise must be added to the gradient to protect user privacy, which partially sacrifices the efficiency and the accuracy (hhokr and Shmatikov (0115).
To further protect the data privacy and avoid the communication bottleneck, the decentralized ar- chitecture has been recently proposed Vanhaesebrouck et al. (2017); Bellet al. (2018). where the centralized node has been removed, and each node only communicates with its neighbors (with mutual trust) by exchanging their local models. Exchanging local models is usually favored to the data privacy protection over sending private gradients because the local model is the aggregation or mixture of quite a large amount of data while the local gradient directly reflects only one batch of private data samples. Although advantages of decentralized architecture have been well recognized over the state-of-the-art method (its centralized counterpart), it usually can only be run on the network with mutual trusts. That is, two nodes (or users) can exchange their local models only if they trust each other reciprocally (e.g., node A may trust node B. but if node B does not trust node A, they cannot communicate). Given social network, one can only use the edges with mutual trust to run decentralized federated learning algorithms. Two immediate drawbacks will be: (1) If all mutual trust edges do not form connected network, the federated learning does not apply; (2) Removing all single-sided edges from the communication network could significantly reduce the efficiency of communication. These drawbacks lead to the question: How do we effectively utilize the single-sided trust edges under decentralized federated learning framework?
In this paper, we consider the social network scenario, where the centralized network is unavailable (c.g., there does not exist central node that can build up the connection with all users, or the centralized communication cost is not affordable). We make minimal assumption on the social

---

Under review as a conference paper at ICLR 2021
Server
(b) Decentralized with mutual trust (c) Decentralized with singe-sided
(a) Centralized
trust
Figure 1: Different types of architectures.
network: The data may come in a streaming fashion on each user node as the federated learning algorithm runs; the trust between users may be single-sided, where user A trusts user B, but user B may not trust user ("trust" means "would like to send information to").
For the setting mentioned above, develop decentralized learning algorithm called online push- sum (OPS) which possesses the following features:
Only models rather than local gradients are exchanged among clients our algorithm. This scheme can reduce the risk of exposing clients' data privacy Aono et al. (2017).
Our algorithm removes some constraints imposed by typical decentralized methods, which makes it more flexible in allowing arbitrary network topology. Each node only needs to know its out neighbors instead of the global topology.
We provide the rigorous regret analysis for the proposed algorithm and specifically dis- tinguish two components the online loss function: the adversary component and the stochastic component, which can model clients' private data and internal connections be- tween clients, respectively.
Notation
We adopt the following notation in this paper:
For random variable < subject to distribution D.", we use En,r and Dn,T to denote the set of random variables and distributions, respectively:
(5( (8) E T 114tJJsse JISISHASESTT DR,T= (D( ISSSHIISITT"
Notation En,7 ~ Dr.T implies E ~ D for any E [n] and / E [T].
For a decentralized network with n nodes, we use W E R= to present the confusion
matrix, where Wij 2 0 is the weight that node sends node (i,j E [n]). Nu (j
[n] Wij 0} and A\" {k E [n] WA 0} are also used for denoting the sets of in neighbors of and out neighbors of node i respectively.
Norm denotes the lg norm || by default.
RELATED WORK
The concept of federated learning was first proposed in McMahan et al. (2016), which advocates novel learning setting that learns a shared model by aggregating locally-computed gradient updates without centralizing distributed data on devices. Early examples research into federated learning also include Konečný et al. 2015 2016), and widespread blog article posted by Google McMa- han and Ramage (2017). To address both statistical and system challenges, /Smith et al.) (2017b) and Caldas et al. (2018) propose a multi-task learning framework for federated learning and its related optimization algorithm, which extends early works SDCA Shalev-Shwartz and Zhang (2013); Yang (2013); Yang al. (2013) and COCOA Jaggi et al. 2014); Ma et al. (2015); Smith et al. (2016) to the federated learning setting. Among these optimization methods, Federated Averaging (FedAvg), proposed by McMahan et al. (2016), beats conventional synchronized mini-batee SGD regarding communication rounds well converges non-IID and unbalanced data. Recent rigorous the- oretical analysis Stich (018);; Wang and Joshi (2018);
: Yu et al. (2018); Lin et al. (2018) shows that FedAvg special case of averaging periodic SGD (also called "local SGD") which allows nodes
2

---

Under review as a conference paper at ICLR 2021
to perform local updates and infrequent synchronization between them to communicate less while converging quickly. However, they cannot be applied to the single-sided trust network (asymmetric topology matrix).
Decentralized learning is a typical parallel strategy where each worker is only required to commu- nicate with its neighbors, which means the communication bottleneck (in the parameter server) is removed. It has already been proved that decentralized learning can outperform the traditional cen- tralized learning when the worker number is comparably large under a poor network condition Lian ct al. (201)). There are two main types of decentralized learning algorithms: fixed network topology He al. (2018), and time-varying Nedić and Olshevsky (2015); Lian al.] (2018) during training. Wu et al. (2017;; Shen et al. (2018) shows that the decentralized SGD would converge with a com- parable convergence rate the centralized algorithm with less communication to make large-scale model training feasible. Li et al. (2018) provides systematic analysis of the decentralized learning
pipeline.
Online learning has been studied for decades. It is well known that the lower bounds of online optimization methods are O(vT) and Oflog T) for convex and strongly convex loss functions re- spectively Hazzan al.] (20T6); (Shalev-Shwarz al. (2012). recent years, due to the increasing volume of data, distributed online learning, especially decentralized methods, has attracted much attention. Examples of these works include Kamp et al. (2014); Shahrampour and Jadbabaic (2017); Lee al. (216)) Notably, Zhao et al. (2019) shares similar problem definition and theoretical result as our paper. However, single-sided communication is not allowed in their setting, restricting their results.
3 PROBLEM SETTING
In this paper, we consider federated learning with n clients (a.ka., nodes). Each client can be either an edge server or some other kind of computing device such as smart phone, which has local private data and the local machine learning model x; stored on it. We assume the topological structure of the network of these n nodes can be represented by a directed graph G (nodes [n]. edges E) with vertex set [n]] = 21,2.... ... n and edge set E C [n] [m). If there exist an edge (u, v) F,, it means node u and node v have network connection and u can directly send messages to v.
Let x," denote the local model on the i-th node at iteration t. In each iteration, node i receives a new sample and computes prediction for this new sample according to the current model xx") (e.g., it may recommend some items to the user in the online recommendation system). After that, a loss function, (+) associated with that new sample is received by node i. The typical goal of online learning is to minimize the regret, which is defined as the difference between the summation of the losses incurred by the nodes" prediction and the corresponding loss of the global optimal model x":
T
Rr ΣΣ (Jex(x()) ((xxx(()-ii((()))
where x" = arg min, ΣT En fre(x) is the optimal solution.
However, here we consider more general online setting: the loss function of the i-th node at iteration t is (:. which is additionally parametrized by random variable Êi.e- This &,, is drawn from the distribution D,,,, and is mutually independent in terms of i and t, and we call this part as the stochastic component of loss function fi,((: E.,)) The stochastic component can be utilized to characterize the internal randomness of nodes' data, and the potential connection among different nodes. For example, music preference may be impacted by popular trends on the Internet, which can formulated by our model by letting Di, D; for all [ni] with some time-varying distribution D, On the other hand, function fi,((5)) is the adversarial component of the loss, which may include, for example, user's 's profile, location, etc. Therefore, the objective regret naturally becomes the expectation of all the past losses:
ΣΣ
(full()) :.! -0x((x))(())))
R
E
(1)
En,T T DaoT
1=
with x -arg ming E= RE, D E1=1 EL Ful(x; E!")
3

---

Under review as a conference paper at ICLR 2021
One benefit of the above formulation is that it partially resolves the non-L.LD. issue in federated learning. A fundamental assumption in many traditional distributed machine learning methods is that the data samples stored on all nodes are I.I.D,, which fails to hold for federated learning since the data on each user's device is highly correlated to that user's preferences and habits. However, our formulation does not require the L.I.D. assumption to hold for the adversarial component all. Even though the random samples for the stochastic component still need to be independent, they are allowed be drawn from different distributions.
Finally, one should note that online optimization also includes stochastic optimization (i.e., data samples are drawn from fixed distribution) and offline optimization (i.e., data are already collected before optimization begins) as its typical cases Shalev-Shward et al.] (2012). Hence, our setting covers a wide range of applications.
ONLINE PUSH-SUM ALGORITHM
In this section, we define the construction of the confusion matrix and introduce the proposed algo- rithm.
4.1 CONSTRUCTION OF CONFUSION MATRIX
One important parameter of the algorithm is the confusion matrix W. W is a matrix depending on the network topology G. which means Wij 0 if there is directed edge (i.j) in G. If the value of Way is large, the node will have a stronger impact on node j. However, W still allows flexibility where users specify their weights associated with existing edges, meaning that even if there is a physical connection between two nodes, the nodes can decide against using the channel.
For example, even if (i.j) E. user still can set Wij- 0 if user i thinks node j is not trustworthy and therefore chooses to exclude the channel from to j.
Of course, there are still some constraints over W. W must be a row stochastic matrix (i.c., each entry in W is non-negative, and the summation of cach row is 1). This assumption is different from the one in classical decentralized distributed optimization, which typically assumes W is symmetric and doubly stochastic (e.g.. Duchi et al. (011)) (i.e., the summations of both rows and columns are all 1). Such a requirement quite restrictive, because not all networks admit a doubly stochastic matrix (Gharesifard and Cortés (2010), and relinquishing double stochasticity can introduce bias in optimization Raam et al. (2010); Tsianos and Rabbat (2012). As a comparison, our assumption that W is row stochastic will avoid such concerns since any non non-negative matrix with at least one positive entry on each row (which is already implied by the connectivity of the graph) can be casily normalized into row stochastic. The relaxation of this assumption is crucial for federated learning. considering that the federated learning system usually involves complex network topology due to its large number of clients. Moreover, since each node only needs to make sure the summation of its out-weights is 1, there is no need for it to be aware of the global network topology, which significantly benefits the implementation of the federated learning system. Meanwhile, requiring W to be symmetric rules out the possibility of using asymmetric network topology and adopting sing-sided trust, while our method does not have such restriction.
4.2 ALGORITHM DESCRIPTION
The proposed online push-sum algorithm is presented in Algorithm The algorithm design mainly follows the pattern of push-sum algorithm Tsianos et al. (0012), but here we further generalize into the online setting.
The algorithm mainly consists of three steps:
1. Local update: each client i applies the current local model xx to obtain the loss function, based on which an intermediate local model (4) is computed;
2. Push: the weighted variable Way 2 is sent to j for all its out neighbors j;
()) 3. Sum: all the received W W 243 is summed and normalized to obtain the new model X
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Online Push-Sum (OPS) Algorithm
Require: Learning rate ?, number of iterations
6:
Send
(Wisz Wyse!") to all j e
T. and the confusion matrix W.
1: Initialize X zu 0, wh
(d)
(1)
1 for all
7: Update
E [n]
2: for O, ...,, T - do
3:
// For all users (say the i-th node E
2i41
Σ
WhiZ
14
(1)
[n))
KENT
W111 Σ
WhEW (R)
4: Apply local model x and suffer loss
(x (1), =())
KE
5: Locally computes the intermedia vari-
2++1
able
(4)
W1+1
8: end for
(6) (1) VV (x)
9: return XT
to node i
should be noted an auxiliary variables 2 and 2(4) are used in the algorithm. Actually, they are used in the algorithm to clarify the description but may be easily removed in the practical im- plementation. Besides, another variable w/(h) is also introduced, which is the normalizing factor of (a) w plays important role in the push-sum algorithm, since W is not doubly stochastic in Zz+1-
our setting, and is possible that the total weight receives does not equal to 1. The introduction
of the normalizing factor w helps the algorithm avoid issues brought by that W is not doubly stochastic. Furthermore, when W becomes doubly stochastic, it can be easily verified that w,
and x(" = 2 for any i and f, then Algorithm reduces to the distributed online gradient method proposed by Zhao et al. (2019).
In the algorithm, the local data, which is encoded in the gradient (x, (8) &t) Shokri and Shmatikov
(2015), only utilized updating local model. What neighboring nodes exchanges are only limited to the local models.
4.3 REGRET ANALYSIS
In this subsection, we provide regret bound analysis of OPS algorithm. Due the limitation of space, the detail proof is deferred to the appendix. For convenience, first denote
(x,(x) = D.. ft,(x; Et,)
To carry out the analysis, the following assumptions are required:
Assumption 1. We make the following assumptions throughout this paper: (I) The topological graph G strongly connected; W is row stochastic; (2) For any [n]] and E [T], the loss function fx,(x;; E1,)) is convex in x; (3) The problem domain is bounded such that for any two vectors and y we always have ||x y/12 < R; (4) The norm of the expected gradient V F..(.) is bounded, iee. there exist constant G > 0 such that || (x)]( S G2 for any i, and x; (5) The
gradient variance is also bounded by o², namely.
E Di,
Here constant G' provides upper bound for the adversarial component. On the other hand, measures the magnitude stochasticity brought by the stochastic component. When a = 0, the problem setting simply reduces back to normal distributed online learning. The strong connectivity assumption is necessary to ensure that the information can be exchanged between any two nodes. As for the convexity and the domain boundedness assumptions, they are quite common in online learning literature, such as Hazan et al. (016)).
Equipped with these assumptions,
are ready present the convergence result:
5

---

Under review as a conference paper at ICLR 2021
Theorem 2. If we set
VRR
(2)
o OvI+nC, GVnUIT
the regret of OPS can be bounded by:
Rr S O (OGRVVT+ + oR (1+ VnCz) vnt),
(3)
where C1 and C2 are two constants defined the appendix.
and O, where the problem setting just reduces normal online optimiza- tion, the implied regret bound (GGRyT) exactly matches the lower bound of online optimization Hazan et al. (016)) Moreover, our result also matches the convergence rate of centralized online learning where y O for fully connected networks. Hence, we can conclude that the OPS algorithm has optimal dependence on T'
Note that when
This bound has linear dependence on the number nodes ni, but it is easy to understand. First, we have defined the regret to be the summation of the losses on all the nodes. Increasing makes the regret naturally larger. Second, our federated learning setting is different from the typical distributed learning in that LLD. assumption does not hold here. Each node contains distinct local data that may be drawn from totally different distributions. Therefore, adding more nodes not helpful for decreasing the regret of existing clients.
Moreover, we also prove that the difference of the model x on each worker could be bounded using the following theorem:
Theorem 3. If we set "y as (2) the difference of the model X, on each worker admits a faster convergence rate than regret:
n
Z+11/ || so (nGR+ + nRo
Σ
X241
Hence, the models on all clients' devices will finally converge to the same one with rate (1/TT).
4.4 PRIVACY PROTECTION
Our proposed algorithm has several advantages concerning privacy protection.
First, as we have mentioned, OPS runs in a decentralized way and exchanges models instead of gradients training samples, which is already proven effective for reducing the risk of privacy leakage Bellet et al. (2117). Second, OPS runs in decentralized and asymmetric fashion. These properties create difficulties for many attacking methods such as Nast et al. (2018). In order infer the data of other clients, the attacker needs to know the reactions of other nodes after the attack is injected, which impossible when the connections are single-sided. Even though the attack will spread among the whole network and finally return to the attacker, it is still hard for the attacker to distinguish whether the information he receives from its neighbors already affected by the attack or not, since he is unaware of the global topology.
EXPERIMENTS
We compare the performance of our proposed Online Push-Sum (OPS) method with that of Decen- tralized Online Gradient method (DOL) and Centralized Online Gradient method (COL), and then evaluate the effectiveness of OPS in different network size and network topology density settings.
5.1 IMPLEMENTATION AND SETTINGS
We consider online logistic regression with squared & norm regularization:
fa, (x: Es,t = log (1 + exp (- (.,)) + ||x|

---

Under review as a conference paper at ICLR 2021
0.52
SUSY
SUSY
Room Occupancy
Boom Occupancy
D3L-tym -0gmmm OPS
Pegret (Rverrage Lox5)
50-4ymm
D0L-aym
Diverage Lexi
001 symm
150 (50-05ymi
DOL-3gmm OPS
USL Lagam
075
GPS
Regres (Average
0.50
OXL
COL
COL
COL
0.40
0.40
0.52
Regret
500
1020
1500
2320
500
1020
1500
2000
520
1250
1500
2000
520
1050
2200
2002
Iteration
Peration
Reration
Reration
(a) stochastic= 100%
(b) stochastic=50%
(c) stochastic=100% (d) stochastic=50%
(7 = 128, #Neighb.=32) (n- = 128, #Neighb.=32)
(n = 20, #Neighb.=10)
(n = 20, #Neighb.=10)
Figure 2: Comparison among OPS, DOL (Decentralized Online Learning) and COL (Centralized Online Learning)
where regularization coefficient À is set to 10 4, Ei. is the stochastic component of the function ft, introduced in Section [ which is encoded in the random data sample (Ai, Vi,)) We evaluate the learning performance by measuring the average loss
T ΣΣ 1= t=1
Ju Ex.),
nT
instead of using the dynamic regret ① directly, since the optimal reference point x* the same for all the methods. The learning rate 7 in A tuned to be optimal for each dataset separately. The experiment implementation based on Python 3.7.0, Py PyTorch 1.2.0, NetworkX 2.3, and scikit- learn 0.20.3. The source code along with other information concerning the experiment such as the setting of the pppee-prrsmeters is provided in the supplementary materials.
Dataset Experiments were run on two real-world public datasets: SUSY and Room-Occupanc B SUSY and Room-Occupange are both large-scale binary classification datasets, containing 5,000,000 and 20,566 samples, respectively. Each dataset is split into two subsets: the stochas- tic data and the adversarial data. The stochastic data is generated by allocating fraction of samples (e.g., 50% of the whole dataset) to nodes randomly and uniformly. The adversarial data is gener- ated by conducting on the remaining dataset to produce n clusters and then allocating every cluster to a node. As we analyzed previously, only the scattered stochastic data can boost the model per- formance by intra-node communication. For each node, this pre-acquired data is transformed into streaming data to simulate online learning.
5.2 COMPARISON WITH DOL AND COL
To compare OPS with DOL and COL, network size with 128 nodes and 20 nodes are selected for SUSY and Room-Occupancy, respectively. For COL, its confusion matrix W is fully-connected (doubly stochastic matrix). For DOL and OPS, they are run with the same network topology and the same row stochastic matrix (asymmetric confusion matrix) to maintain a fair comparison. Such asymmetric confusion is constructed by setting each node's 's number of neighbors as random value which is smaller than fixed upper bound and also ensures the strong connectivity of the whole network (this upper-bound neighbor number set to 32 for the SUSY dataset, while is set for the Room-Occupali doubly stochastic confusion matrix, DOL is run in two settings for comparison. In the first set- ting, in order to meet the assumption of the symmetry and doubly stochasticity, all unidirectional connections are removed the confusion matrix so that the row stochastic confusion matrix degen- erates into doubly stochastic matrix. This setting is labeled as DOL-Symm in Figure In another setting, DOL is forced to run on the asymmetric network where each node naively aggregates its received models without considering whether its sending weights are equal to its receiving weights. DOL-Asymm is used to label this setting in Figure 2
dataset). Since DOL typically requires the network to be the symmetric and
As illustrated in Figure 2 in both two datasets. OPS outperforms DOL-Symm in the row stochastic confusion matrix. This demonstrates that incorporating unidirectional communication can help to boost the model performance. In other words, OPS gains better performance in the single-sided sided
htm² 4
SUSY
https://archiver http:///cw.....oeococc///o/////a

---

Under review as a conference paper at ICLR 2021
SUSY
SUSY
0.500
SUSY
SUSY
2560
01-250)
0.495
Regret (Averoge
30.50
0FS
0PS
5m-512)
102-0
segret (overoge
0..44
OPS (n-512)
0-460
0.54
CP
0.49
0.53
0.480
scgret
0.53
0.48
0.475
0.52
0.410
500
1000
1500
2000
500
1000
1500
2000
500
1000
1500
2020
500
1500
2000
Reration
Reeation
Iteration
Iteraiio
(a) stochastic=100%s
(b) stochastic=50%
(c) stochastic=10099
(d) stochastic=50%
Figure 3: Evaluation different network sizes and densities
trust network under the setting of federated learning- OPS also works better than DOL-Asymm. Although DOL-Asymm utilizes additional unidirectional connections, in some cases its performance even worse than DOL-Symm (c.g.. Figure 2aj. This phenomenon is most likely attributed to its simple aggregation pattern, which causes decreased performance in DOL-Asymm when removing the doubly stochastic matrix assumption. These two observations confirm the effectiveness of OPS in row stochastic confusion matrix, which is consistent with our theoretical analysis.
Comparing Segurreeeande Figure 2d we also observe that when increasing the ratio of the stochastic component, the average loss (regret) becomes smaller. It is reasonable that OPS achieves slightly worse performance than COL, because OPS works sparsely connected network where informa- tion exchanging is much less than COL. We use the COL as the bascline in all experiments.
Only the number of iterations instead of the actual running time is considered in the experiment. is redundant to present the actual running time. Because the centralized method requires more time for each iteration due to the network congestion in the central node, OPS usually outperforms COL in terms of running time.
5.3 EVALUATION ON DIFFERENT NETWORK SIZES
Figure 3a and 3b summarizes the evaluation of OPS in different network sizes (in the SUSY dataset, 128, 256, 512, 1024 are set). The upper-bound neighbor number is aligned to the same value among different network sizes to isolate its impact. As we can see, in every dataset, the average loss (regret) curve in different network sizes is close on small scale. These observations demonstrate OPS is robust to the network size. Furthermore, the average loss (regret) is smaller in larger network size (i.e., the curve of the n 1024 network size is lower than others), which also demonstrates that more stochastic samples provided by more nodes can naturally accelerate the convergence. Due to limitation of space, the results on the other dataset is deferred the appendix.
5.4 EVALUATION ON NETWORK DENSITY
We also evaluate the performance of OPS in different network densities. We fix the network size to 512 for SUSY dataset. Network density is defined as the ratio of the upper-bound random neighbor number per node to the size of the network (e.g., if the ratio is 0.5 in SUSY, it means 256 is set as the upper-bound neighbor number for each node). We can see from Figure 3c and 3d that as the network density increased, the average loss (regret) decreased. This observation also proves that our proposed OPS algorithm can work well different network densities, and can gain more benefits from denser row stochastic matrix. This benefit can also be understood intuitively: in federated learning network, user's model performance will improve if it communicates with more users. The results of Room Occupancy are also deferred to the appendix.
CONCLUSIONS
Decentralized federated learning with single-sided trust is promising framework for solving wide range of problems. In this paper, the online push-sum algorithm developed for this setting, which is able to handle complex network topology and is proven to have an optimal convergence rate. The regret-based based online problem formulation also extends its applications. We tested the proposed OPS algorithm in various experiments, which have empirically justified its efficiency.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Aono, Y., Hayashi, T., Wang, L., Moriai, S., et al. (2017). Privacy-rreservngg deep learning via additively homomorphic eneryption. IEEE Transactions on Information Forensics and Security, 13(5):1333-1345.
Assran, M., Loizou, N., Ballas, N., and Rabbat, M. (2018). Stochastic gradient push for distributed deep learning. arXiv preprint arXiv:/811.10722
Assran, M. and Rabbat, M. (2018). TrXiv:1803.0899)
Asynchronous subgradient-push.
arXiv preprint
Bellet, A., Guerraoui, R., Taziki, M., and Tommasi, M. (2017). Personalized and private peer-to-peer machine learning, arXiv preprint arXiv:1705. 17050043.
Bellet, A., Guerraoui, R., Taziki, M., and Tommasi, M. (2018). Personalized and private peer-to- peer machine learning. In International Conference on Artificial Intelligence and Statistics, pages 473-481.
Caldas, S., Smith, V., and Talwalkar, (2018). Federated Kernelized Multi-Task Learning. The Conference Systems and Machine Leurning, page 3.
Duchi, C., Agarwal, A., and Wainwright, (2011). Dual averaging for distributed opti-
mization: Convergence analysis and network scaling. IEEE Transactions Automatic control, 57(3):592-606.
Gharesifard, B. and Cortés, (2010). When does digraph admit doubly stochastic adjacency matrix? In Proceedings of the 2010 American Control Conference, pages 2440-2445. IEFF.
Hazan, E. al. (2016). Introduction online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325.
He, L., Bian, A., and Jaggi, M. (2018). Cola: Decentralized linear learning. In Advances in Neural Information Processing Systems, pages 4541-4551.
Jaggi, M., Smith, V., Takác, M., Terhorst, J., Krishnan, S., Hofmann, T., and Jordan, M. I. (2014). Communication-eficien distributed dual coordinate ascent. In Advances in neural information processing systems, pages 3068-3076.
Kamp, M., Boley, M., Keren, D., Schuster, A., and Sharfman, I. (2014). Communication-effiienn distributed online prediction by dynamic model synchronization. Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 623-639) Springer.
Konečny, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint 16X.v:1610.05442.
Konečný, J., McMahan, B., and Ramage, D. (2015). Federated Optimizaation Optimiza- tion Beyond the Datacenter. arXiv:1511.0357 [cs, math]. arXiv: 1511.03575.
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Fed- erated Learning: Strategies for Improving Communication Efficiency. arXiv:1610.05492 [cs]. arXiv: 1610.05492.
Lee, S., Nedić, A., and Raginsky, M. (2016). Coordinate dual averaging for decentralized online optimization with nonseparable global objectives. IEEE Transactions on Control of Network Systems, 541):34444
Li, Y., Yu, M., Li, S., Avestimehr, S., Kim, N. S., and Schwing, A. (2018). Pipe-sgd: A decentralized pipelined sgd framework for distributed deep net training. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianche Bianchi, N., and Garnett, R., editors, Advances in Neural Information Processing Systems 3/, pages 8056-8067. Curran Associates, Inc.

---

Under review as a conference paper at ICLR 2021
Lian, X., Zhang. C., Zhang, H.,, Hsieh, C.-J., Zhang, W., and Liu, J. (2017). Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pages 5330-5340.
Lian, X., Zhang, W., Zhang, C., and Liu, J. (2018). Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning.
Lin, T., Stich, S. U., and Jaggi, M. (2018). Don't Use Large Mini-Batches, Use Local SGD. 1808 07217 [cs, stat]. arXiv: 1808.07217.
Ma, C., Smith, V., Jaggi, M., Jordan, M. I., Richtárik, P., and Takáć, M. (2015). Adding vs. Averag- ing in Distributed Primal-Dual Optimization. arXiv: 1XXiv:/502.03500 [cs]. arXiv: 1502.03508.
McMahan, and Ramage, D. (2017). Google AI Blog: Federated Learning: Collaborative Machine Learning without Centralized Training Data.
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and Arcas, B. A. (2016). Communication- Efficient Learning of Deep Networks from Decentralized Data. arXiv:1602.055: [cs]. arXiv: 1602.05629.
Nasr, M., Shokri, R., and Houmansadr, A. (2018). Comprehensive privacy analysis of deep learning: Stand-alone and federated learning under passive and active white-box inference attacks. arXiv preprint arXiv:1812.00912
Nedić, A. and Olshevsky, A. (2014). Distributed optimization over time-varying directed graphs. IEEE Transactions Automatic Control, 60(3):601-615)
Nedić, A. and Olshevsky, A. (2015). Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601-615.
Nedić, A. and Olshevsky, A. (2016). Stochastic gradient-push for strongly convex functions on varying directed graphs. IEEE Transactions on Automatic Control, (11))333936339)
Ram, S., Nedić, A., and Veeravalli, V. (2010). Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications, 147(3):516~ 545.
Shahrampour, S. and Jadbabaie, A. (2017). Distributed online optimization in dynamic environments using mirror descent. IEEF Transactions on Automatic Control, 63(3):714-725.
Shalev-Shwartz, et al. (2012). Online learning and online convex optimization. Foundations and Trends in Machine Learning. 4(2):107-194.
Shalev-Shwartz, S. and Zhang, T. (2013). Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(Feb):567-599
Shen, Z., Mokhtari, A., Zhou, T., Zhao, P., and Qian, H. (2018). Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication. In Dy, J. and Krause, A., editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4624 4633, Stockholmsmässan, Stockholm Sweden. PMLR.
Shokri, R. and Shmatikov, V. (2015). Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1310-1321. ACM.
Smith, V., Chiang, C.-K., Sanjabi, M., and Talwalkar, A. S. (2017a). Federated multi-task learning. In Advances in Neural Information Processing Systems, pages 4424-4434.
Smith, V., Chiang, C.-K., Sanjabi, M., and Talwalkar, S. (2017b). Federated multi-task learning- In Advances in Neural Information Processing Systems, pages 4424 4434.
Smith, V., Forte, S., Ma, C., Takac, M., Jordan, M. I., and Jaggi. M. (2016). CoCoA: A Gen- eral Framework for Communication Efficient Distributed Optimization. arXiv:J611.02118 [cs]. arXiv: 1611 1,02199.
10

---

Under review as a conference paper at ICLR 2021
Stich, S. U. (2018). Local SGD Converges Fast and Communicates Little.
Tsianos, K. I., Lawlor, S., and Rabbat, M. G. (2012). Push-sum distributed dual averaging for convex optimization. In 2012 IEEE s1 IEEE Conference on Decision and Control (CDC), pages 5453- 5458. IEEE.
Tsianos, K. I. and Rabbat, M. G. (2012). Distributed dual averaging for convex optimization under communication delays. In 2012 American Control Conference (ACC), pages 1067-1072. IEEE.
Vanhaesebrouck, P., Bellet, A., and Tommasi, M. (2017). Decentralized collaborative learning of personalized models over networks. In International Conference on Artificial Intelligence and Statistics (AISTATS).
Wang, and Joshi, G. (2018). Cooperative SGD: unified Framework for the Design and Analysis of Coommunication-Efiiiiie SGD Algorithms.
Wu, T., Yuan, K., Ling, Q., Yin, W., and H. Sayed, A. (2017). Decentralized consensus optimization with asynchrony and delays. IEEE Transactions on Signal and Information Processing over Networks, PP:1-1.
Yang, Q. Liu, Y., Chen, T., and Tong, Y. (2019). Federated machine learning: Concept and applica- tions. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):12.
Yang. T. (2013). Trading computation for communication: Distributed stochastic dual coordinate ascent. In Advances in Neural Information Processing Systems, pages 629-637.
Yang, T., Zhu, S., Jin, R., and Lin, Y. (2013). Analysis of distributed stochastic dual coordinate ascent, arXiv preprint arXiv: 1312.
Yu, H., Yang, S., and Zhu, S. (2018). Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning. 1rXiv:1807.060 06629 [cs, mathJ. arXiv: 1807.06629.
Zhao, Y., Yu, C.. Zhao, P., and Liu, (2019). Decentralized online learning: Take benefits from others' data without sharing your own to track global trend. arXiv preprint arXiv: 1901..9011005
A PROOFS
Notations:
Below we use the following notation in our proof
(X,, = [VF.. (x,") (xx")... ...., V.n, [x("))]
X; == X; X2 x (n)
(1) (2)
G, V (x, ..... (x.
Here we first present the proof Theorem 2 then we will present some key lemmas along with the proof of Theorem 3
The following theorem is the key to prove Theorem
Theorem 4. For the online push-sum algorithm with step size y > 0, it holds that
nR²
Rr S G o nC22)
(4)
27
where
8C'g + 1, C₂
20g
C = 8min (1 4)
8mii (1 9)
and C, q and 8min some constants defined in later lemmas.
11

---

Under review as a conference paper at ICLR 2021
Proof. Since the loss function f.,(+) is assumed to be convex, which leads to
fie
x1 :.() -nF((x))
(1)
E,
x -5(
(1)
faa (x": (x:55(")
1
x
x xx)
E,
(1)
(1)
Zz
+ E
V Si,
(x) (( Tz x*)
(0) (00
1=1
1=
1=12
For T2x, we have
E2
V Sig
Xt :st _ -x*)
(0.e(0 (())
1
(8), (8)
E,
V fi, X 1t
-z xx'
7
1=1
2
72
E,
V
fite
xx
(1)
:5t
+ I 1x
Z, x
2
fúr
xx -
(1) (1)
27
11
n
i=1
| |>>
n R.
Vi.t
x :5t
+ |ū x=1 - a x2
27
1=1
2200
11
E,
7²2² +
+ 12 x"
x=1
|| xx()²)
27
Notice that for COL, we have I = 0 because x, z. So for DOL, in order to bound I,s, we need to bound the difference
x z, (using Lemma 8)
Vfa (x( (x():].)) xxx0 xx5- Zi)
E,
n
V.L.e ) -Z.)
E,
<E,
VF.. (x(²) [2())|]
+
1
x
(6)
-,
α
12

---

Under review as a conference paper at ICLR 2021
Summing up the inequality above from t = 1 to T, we get
T
(5)
E2
.x1
E2
Pii
(1)
,x,
(3)
Zt
a
(6)
)|(
1
(
2 1')
E,
[
x
a
1
aE VF (
p +
Es
| - 2, 21113/
a
C²2
T
E. V. ( + ad min (1 q)²
Σ
E, |Gell
E=
C22 q2
Sa
E,
VF (
E (VV)) tno2)
a min q)²
1=1
Choosing
2yC9 0min(1-9)
have
T
CnyCTgG2
+ 2nnCgo²T
(x. :.!0)
(0) 2z s
E
xx,
8miu (1 9)
8mia - 9)
1=1
1=1
So have
Σ E. 2
fex 2 -9)E(0) -nF(x')
8nyCTTQQ2
2700021
Σ
02 +
7²02
+B, 12e - x=1 - Ee 1,+11 xx11²)
+ 2117
Ōmin (1 4))
Omin (1 - -4)
n
<CTTy
8Cq
+1) + TTTT
1 11
Juin (1 - 9) )
2nCq
+
71
T
Eg 1Ize
x*112 - Be | x² 112)
6m -q) 9)
27 t=1
8C4
8min (1 9)) )
2nC4
RRR
<CTTay
+1)
+ T²TTy
1+
+
61 - 9)
2
nR²
+Cnn@TT+((++CC3) 2T
27
VoR Notice that Theorem can be easily verified by setting 7 (o
Next, we will present two lemmas for our proof of Lemma 8 The proofs of following two lemmas
can be found in existing literature Nedić and Olshevsky (2014] 2016); Assran and Rabbat (0188;; Assran al. (2018).
Lemma 5. Under the Assumption 7 there exists a constant 8min > 0 such that for any t, the following holds
1
TT ....Woly 2 8mia 2
Vi
(5)
n
where Wt is row stochastic matrix.
13

---

Under review as a conference paper at ICLR 2021
Lemma 6. Under the Assumption
1 for any there always exists stochastic vector (b(t) and two 1 such that for any satisfying $ I t, the following inequality
constants = 4 and q = 1 n "
holds
| W W W -b)(() S Cq" Vi. V
where W is row stochastic matrix, and (b()) is vector with (t)(t) being its i-th entry.
Lemma 7. Given non-negative sequences {ar]s=1 and (be that satisfying
a: bbs
(6)
with 10, we have
D2 =
1t
1
Σ
13
(1
p)
8=1
Proof. From the definition, have
by
S
b
b
1=1
s=1
t=
==
k
D&
br
b,br
62
b2
2
62
1=1
p)
Based on the above three lemmas, we can obtain the following lemma. Lemma 8. Under the Assumption the updating rule of Algorithm equality
? leads to the following in-
n
C2202
ΣΣ
2441 1|, S 82 (1 q)2
Σ G.
x
min
where y is the step size, and C 4, 8min 2 n nn .9 the stochastic gradient at time s (e.g., the i-th column is the stochastic gradient vector on node at time 8).
n are constants. G is the matrix for
Proof. The updating rule of OPS can be formulated as
Z = (Z. GG) W
W++1 T We
X Z, (ddl(wia(w+++))
14

---

Under review as a conference paper at ICLR 2021
where W is row stochastic matrix. X, [ X X2 (n)] is matrix whose each column is
(1) (2)
X; (5) G3 the matrix of gradient, whose each column is the stochastic gradient at z, on node
Z. [2, 1- " is the matrix whose each column is 2, (1)
(I)
Assuming Xo = O and Wp = 1, then we have
Z++1 (Z:- W- --
G. W
(8)
2(1 = Zz -B:
18.t
(9)
W1+1 W Wo:
(10)
where X, = X,1 is the average of all variables on the nodes, and gr G,1 is the averaged gradient. We have W1 = since W is a row stochastic matrix.
For w1+1, according Lemma 6
decompose it as follows
W1+1 = -W++T Wo |W - +btt)11aa + (tt)1 wo = (W xtt{ + nz((), (11)
since wg 1.
On the other hand, according to Lemma
we also have
++ = / 1T e, = Ew 2 ndminn
(12)
3=1
where is vector with only the i-th entry being 1 and O for others. We need further bound the following term
X
Ze+1
-
(1)
Ze+1
Wei1
G Wi e;
G.1
W e
n
nG. W
G.11
W
e;
(2)
mw
where the second equality is by
8
and 10
We turn to bound the following term
GG Wi-s+le
e;
G1 Wi+
nw
(nG, W s+1 e G,11 T6,11T
n 20i
where the first inequality is accordng to 12 Therefore, combining the results above, we can have
(nG, W G, W le)
2x41
4
$2 min
Σ
(nG. W G.11 - W(+1)
4 2
where the second inequality is due to E Ae; |
15

---

Under review as a conference paper at ICLR 2021
It remains bound the following term
nGG, w -G,11 T w
(nG, W
+ (xp(()]]
2
(nG, (GG,WW-+H 1b)( G [W++1 1 T])
2
(OG.[WetRe 10(1 T11 +
Σ
[W - G (
2
|. ||al [|all| (t) (t))
Sn²
Σ G
-
G. | 10(() 111
#=0
8=0
|G, [0Cg"=t|||G,,lle Σ
Zn²
Σ
++1
==
2
c2n Ed-.1
where the third inequality is due to |11 T |P = and the fourth inequality is by Lemma 6 and the fact that || S n max,, |4,l if E Raxx
Therefore, if we combining all the above inequalities together, we can obtain
Σ
2 I
4r20a9²
Σ
x
Z(+1
min
Using Lemma
we have
2
Σ
9
G G.llP
(1 9)2
Σ
G 1
which leads
T
42209²
T
Σ
x X++1
Z,41
82 min (1 9)
G
t=0 t=1
t=0
which completes the proof.
Actually, Theorem is corollary of Lemma by setting y as the appropriate value.
B EXTRA EXPERIMENT RESULTS
B. EVALUATION ON Room Occupancy DATASET
Due to the limitation of space, we only present the experiment results on SUSY dataset Section
5.3 and 5.4 Related presents on Room Occupancy is shown in Figure and Figure
In Figure we vary the number of clients in the network, from 6 to 20. In Figure 5 the network density varied. All the results are consistent with the ones on SUSY.
16

---

Under review as a conference paper at ICLR 2021
Room Occupancy
Room Occupancy
3.5
2.5
OPS (n 6]
OPS (n 6)
OPS (n 10)
OPS (n 10)
Regret (Average
(n 20)
Regret (Average
2.5
1.5
2.0-
1.0
0.5
2000
2000
Iteration
Iteration
(a) stochastic=100%
(b) stochastic=50%
#Neighbors=2
#Neighbors=2
Figure 4: Evaluation on the Network Sizes
Room Occupancy
Room Occupancy
Regret (Average Loss]
1.2
OPS (0.2)
OPS (0.2)
OPS (0.5)
1.4
(0.5)
1.0
(0.8)
Regret (Average
1.2
(0.8)
COL
COL
1.0
0.8
0.4
0.2
500
1000
1500
2000
500
1000
1500
2000
Iteration
Iteration
(a) stochastic=100%
(b) stochastic=50%
Figure 5: Evaluation on the Network Density
B.2 COMPARISON WITH LOCAL ONLINE GRADIENT DESCENT
To justify the necessity of communication, we also compare OPS with the local online gradient descent (local OGD), where every node trains local model without communicating with others. We run experiments in different ratios of the adversary and stochastic components based on settings Figure 2. As can see in Figure in reducing regret. Moreover, as the ratio of the stochastic components increased, the regret of OPS decreases further. This also empirically proves that the stochastic component can benefit from the communication while the adversarial component does not.
empirically prove that communication does have benefits
SUSY
SUSY
0.60
00.
0.64
20wrsm
0.58
0.62
COL
Regret (Average
Regret (Average
0.60
0.54
0.52
0.56
0.50
0.54
0.48
0.52
500
1000
1500
2000
500
1000
1500
2000
Iteration
Iteration
stochastic=1009
stochastic=50%%
128, #Neighhors=32)
(n 128, #Neighhors=32)
Figure 6: Comparison between OPS and Local OGD.
17


Reviews:
[{"review_id": "txJeSrhiMo3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**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 . \n\n**Questions for the authors**\n1. 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.  \n2. 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?\n3. 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. \n\n**Novelty**\nThe paper to me seems an incremental extension of the previous work (Zhao et al., 2019), and I think the novelty is a little thin.\n\n**Areas to Improve**\nI 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. \n\n**Minor Concerns**\nPage 2. Notation section. “denoting the sets of in neighbors of and out neighbors” -> \"denoting the sets of out neighbors of and in neighbors\" ?\n\n**References**\n1. Personalized Federated Learning with Moreau Envelopes (Dinh et al. NeurIPS, 2020)\n2. Peer-to-peer federated learning on graphs (Lalitha et al. 2019). This is a relevant paper which is missing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "FOztKqcRefG", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\n\nI 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.\n\nFirst 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.\n\n\n## 1Major Comments:\n\n- 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.\n- 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?\n- They provided a regret analysis of the proposed algorithm. However, the authors never showed that the contributions of the proof skill.\n- In the simulation study, could you please show the network structure you proposed?\n\n## 2 Minor Comments\n- Page 2, Notation. You should introduce $n$ first, before the confusion matrix.\n- Page 2, related work: the citation of Stich (2018) and Wang and Joshi (2018) is not corrected.\n- Page 5, you should explain the “strongly connected” in Assumption 1 detailedly.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0P760t2vx84", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work focuses on single-sided decentralized federated learning. The authors propose a push\nsum-based algorithm to relax the symmetric matrix assumption, which leads to a flexible\ndecentralized training on a directed network graph. The authors analyze the regret bound, as well as\nrun some numerical experiments to demonstrate the correctness of the proposed algorithm.\n***Strengths***:\nOverall the paper is well written.\n1. The proposed method bridges a gap between existing decentralized federated learning algorithms\nand real single-sided social networks. Another example I can recall is that sharing in the data market\nis single-sided. The motivation is sound. ​As far as I know, this is the first paper in the FL community\ntalks about this setting.\n2. The authors design a novel algorithm. Its theoretical results of the convergence rate ​connect\n\"online learning\" and \"asymmetric graphs\", which is novel in federated learning.\n3. The experimental design is excellent (including many settings). The code is very readable and\nwell-documented. I believe this helps the popularity of this proposed algorithm.\n***Weakness***:\nI can understand that this work focuses on the algorithm rather than provides a privacy guarantee.\nSo it would be great if the authors provide some intuitions or discussions about how to address\nprivacy concerns.\nI prefer to demonstrate the proposed algorithm on more challenging datasets, but since this work\nemphasizes the convergence analysis, it should be OK for me.\nThe authors only mention an important work in the related works section: “Notably, Zhao et al.\n(2019) shares a similar problem definition and theoretical result as our paper. However, single-sided\ncommunication is not allowed in their setting, restricting their results”. I suggest the authors discuss\nmore about it and distinguish the contributions in theory analysis.\nRelated works:\n“Stochastic gradient push for distributed deep learning” (ICML 2019) should be discussed.\nIn section 4.4, more privacy-related works should be mentioned.\nOverall Rating\nSince the theory in this work is sound and the experimental design and code implementation are\nalso excellent, I incline to strongly support the acceptance of this work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-m4sn6UcL0j", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n \nThe 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.\n\n##########################################################################\n\nReasons for score: \n \nOverall, 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.\n \n##########################################################################\n\nPros: \n \n1. The paper is well written. The research direction on studying central server free federated learning algorithms is promising.\n \n2. The formulation and theoretical analysis of the proposed OPS method looks promising.\n \n3. Experimental results under simulated federated learning under the social networking environment are provided to show the effectiveness of OPS.\n \n##########################################################################\n\nCons: \n \n1. 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. \n2. 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. \n3. 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. \n\n[1] https://arxiv.org/abs/1905.09435\n[2] https://ieeexplore.ieee.org/document/6426375\n\n \n#########################################################################\n\nMinor Comments: \n1. Missing references: [1-2]. \n\n[1] https://arxiv.org/abs/1912.04977\n[2] https://arxiv.org/abs/1908.07873", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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