# DACFL: Dynamic Average Consensus Based Federated Learning in Decentralized
Topology

Zhikun Chen, Daofeng Li, Jinkang Zhu, , Sihai Zhang,
Zhikun Chen and Daofeng Li are with the Department of Electronic Engineering
and Information Science, School of Information Science and Technology,
University of Science and Technology of China. Address: No. 96 Jinzhai Road,
Hefei, Anhui Province, 230026, P. R. China . E-mail:
<EMAIL_ADDRESS>Jinkang Zhu is with the PCNSS laboratory,
School of Information Science and Technology, University of Science and
Technology of China. Address: No. 96 Jinzhai Road, Hefei, Anhui Province,
230026, P. R. China. E-mail<EMAIL_ADDRESS>Sihai Zhang is with the Key
Laboratory of Wireless-Optical Communications, Chinese Academy of Sciences,
School of Information Science and Technology, University of Science and
Technology of China. Address: No. 96 Jinzhai Road, Hefei, Anhui Province,
230026, P. R. China . *E-mail<EMAIL_ADDRESS>
###### Abstract

Federated learning (FL) is a burgeoning distributed machine learning framework
where a central parameter server (PS) coordinates many local users to train a
globally consistent model. Conventional federated learning inevitably relies
on a centralized topology with a PS. As a result, it will paralyze once the PS
fails. To alleviate such a single point failure, especially on the PS, some
existing work has provided decentralized FL (DFL) implementations like CDSGD
and D-PSGD to facilitate FL in a decentralized topology. However, there are
still some problems with these methods, e.g., significant divergence between
users’ final models in CDSGD and a network-wide model average necessity in
D-PSGD. In order to solve these deficiency, this paper devises a new DFL
implementation coined as DACFL, where each user trains its model using its own
training data and exchanges the intermediate models with its neighbors through
a symmetric and doubly stochastic matrix. The DACFL treats the progress of
each user’s local training as a discrete-time process and employs a first
order dynamic average consensus (FODAC) method to track the average model in
the absence of the PS. In this paper, we also provide a theoretical
convergence analysis of DACFL on the premise of i.i.d data to strengthen its
rationality. The experimental results on MNIST, Fashion-MNIST and CIFAR-10
validate the feasibility of our solution in both time-invariant and time-
varying network topologies, and declare that DACFL outperforms D-PSGD and
CDSGD in most cases.

###### Index Terms:

Decentralized network topology, discrete-time dynamic average consensus,
federated learning.

##  1 Introduction

Numerously increasing smart mobile devices such as phones, tablets, etc. have
provided convenience for human beings and generated plentiful user-related
data like images, sound, text and others. In order to make full use of such
huge amount of data, data mining and machine learning techniques [1, 2, 3]
have been developed. However, these techniques usually work on a central
parameter server (PS). This makes it inevitable to collect large amounts of
users’ data into PS, which may lead to an excessive overhead and expose users’
privacy like food preference, consuming behavior, social ties and so on.
According to the general data protection regulation (GDPR) [4], both industry
and academia should pay more attention to the privacy protection of machine
learning. Hence, taking into consideration the privacy concerns when
exploiting users’ data is now becoming an imperative in the era of artificial
intelligence. To tackle this problem, Google has advocated an alternative
known as federated learning (FL) [5, 6, 7]. Rather than collecting users’ raw
data into a PS, the FL enables each user to train their respective models
using their own data, and only the intermediate models are periodically
synchronized by the PS to obtain a global model.

However, there exist several limitations in conventional FL due to the
centralized network topology (see fig. 1). For example, to iteratively
synchronize users’ local-trained models and send back the aggregated global
model to them, the communication load of the entire system is extremely
unbalanced. Specifically, because all users need to communicate with the PS
concurrently iteratively, the communication traffic jam is very likely to
happen to the PS and the performance will be degraded when the network
bandwidth is low. What’s worse, if there is a single point failure that
happens to the PS by any chance, e.g., being attacked, the entire framework
will be paralyzed.

To eliminate the above bottleneck caused by centralized network topology, a
natural idea is that, is it possible to facilitate FL in a decentralized
topology (see fig. 1) without the support of a PS? Thankfully, some existing
work on wireless sensor network (WSN) and device-to-device (D2D) communication
[8] has confirmed the possibility of communication in a decentralized network
topology. Therefore, we believe that it is not only important but also
applicable to implement FL in a decentralized topology.

Figure 1: Centralized topology vs Decentralized topology.

In this paper, we consider the problem of facilitating federated learning in a
decentralized network topology in the absence of a central parameter server.
To this end, we propose a new decentralized federated learning framework based
on dynamic average consensus, which is coined as DACFL. In DACFL, there is no
central PS and all users are connected through an undirected graph, which is
denoted by a symmetric doubly stochastic matrix (i.e., mixing matrix). Each
user trains its local model utilizing its own training data. The respective
trained model intermediates of different users are treated as different
discrete-time reference input sequences. In order to aggregate different
users’ intermediate models111In a centralized federated learning, there is
central PS to periodically aggregate different users’ model into a global
model and send it back to all users. However, to implement federated learning
in a decentralized network topology where no PS exists, the global aggregation
phase would be a critical problem., for each user, we employ an approximate
estimation method, i.e., a first-order dynamic average consensus (FODAC), to
track the average model estimation. Besides, to alleviate the possible local
over-fitting problem, especially for non-i.i.d data, each user in DACFL takes
its neighborhood weighted average model parameter to reinitialize its local
model after each training round.

Actually, there has been some existing work to date devoting to implementing
federated learning in a fully decentralized network topology (as is described
in 2.2). Apart from them, references [9] and [10] should be the most similar
work to this paper. In [9], the authors propose a new consensus-based
distributed SGD (CDSGD) algorithm for collaborative deep learning over a fixed
network topology that enables data parallelization as well as decentralized
computation. In [10], the authors study a decentralized parallel SGD (D-PSGD)
algorithm on a decentralized computational network. They further prove that
D-PSGD achieves the same convergence rate as the centralized parallel SGD
(C-PSGD) algorithm, but outperforms C-PSGD by avoiding the communication jam.
Although some existing work summarizes CDSGD and D-PSGD into the same method
[11, 12], note that we distinguish between CDSGD and D-PSGD by whether the
algorithm requires a global average or not in this paper (D-PSGD additionally
needs a network-wide model average compared with CDSGD). In what follows, we
describe the deficiency of CDSGD and D-PSGD, and differentiate our solution
from these two methods in detail.

For CDSGD in [9], there are two main limitations. One is that it only
considers a fixed network topology with a uniform interaction matrix
(identical value of each element in the matrix). The other is that it assumes
that the training data is independent and identically distributed (i.i.d) over
all users. These two limitations make it not well suited for federated
learning since mutative network topology and non-i.i.d data are common
occurrences in federated learning. Besides, we empirically verify that when
faced with a sparse topology, there is obvious variance across all users’
final models. This is also inconsistent with the goal of FL to attain a
globally consistent model for all users. While for D-PSGD which additionally
performs a network-wide model average in [10], since there is no PS in
decentralized network topology, a problem that naturally arises is who should
perform this network-wide model average task? And how to ensure the
consistency of each user’s model? Just imagine, if we make each user perform
this network-wide average (although this is achievable by exchanging
information through multi-hop communication), it will inevitably cause
communication congestion in some users (especially those user nodes with
higher degrees on the graph). Besides, the authors in [10] consider only a
fixed ring network topology. Our solution differentiates CDSGD and D-PSGD from
the following aspects. First, rather than taking roughly the neighborhood
weighted average to replace the model aggregation like CDSGD or D-PSGD does,
the DACFL employs an average consensus method, i.e., FODAC, to approximate the
average model for each user. Thanks to the effectiveness of FODAC, each user
is able to track the average model as the training progresses. Thus, no
additional network-wide model average is needed in our DACFL. Second, we
extend more typical network topologies in this work. Apart from time-invariant
(or static) and dense topology, we also consider time-varying (or dynamic) and
sparse topology in this paper. Third, non-i.i.d data assignment in addition to
i.i.d case is also considered in this paper. To alleviate the possible local
over-fitting problem, each user in DACFL takes its neighborhood weighted
average model parameter to reinitialize its local model after each training
round. Fig .2 briefly compares our DACFL with CDSGD and D-PSGD.

Figure 2: Comparison between CDSGD, D-PSGD and DACFL (our solution). We differ
CDSGD and D-PSGD that D-PSGD additionally needs a network-wide model average
before the output. Our solution differentiates CDSGD and D-PSGD by employing
FODAC to approximate the “averaged model” over all users. An iteration of
“1$\to$2$\to$3” for CDSGD and D-PSGD or an iteration of “1$\to$2$\to$3$\to$4”
is called a training round (i.e., a communication round) in this paper. For
more details, please refer to Algorithm 1, 2 and 5.

The contributions of this paper can be summarized as follows:

  * •

This paper devises a new decentralized federated learning implementation
coined as DACFL, which is more adaptable to non-ideal network topology
compared with another two existing methods including CDSGD and D-PSGD w.r.t
the average accuracy and the variance of accuracy. Unlike CDSGD and D-PSGD
taking roughly a neighborhood weighted average to approximate the global
aggregated model, DACFL treats each user’s local training as a discrete-time
process and employs the FODAC to estimate the average model, through which the
users are able to obtain a near-average model in the absence of PS during the
training process.

  * •

We theoretically analyze the convergence of our proposed DACFL approach on the
premise of some relatively ideal assumptions. The numeric result offers a
convergence guarantee of our solution and reveals a positive correlation
between the convergence speed and the learning rate and a negative correlation
to the topology size. Specific experimental results also support our analysis.

  * •

The DACFL is also empirically validated through a wide range of experiments
including experiments on both i.i.d and non-i.i.d data, experiments on both
time-invariant topology and time-varying topology with dense connectivity and
sparse connectivity. Results of these experiments show that our DACFL
outperforms CDSGD and D-PSGD w.r.t Average of Acc and Var of Acc in most
cases.

The remainder of this paper is organized as follows. First, some existing work
about decentralized federated learning implementation and dynamic average
consensus is summarized in section 2 following a brief introduction to
conventional federated learning. Then in section 3, we present the system
model comprising node model and communication model, and mathematically
formulate the decentralized federated learning problem as a combination of
distributed machine learning and dynamic average consensus problem. In section
4, we first provide a heuristic method to construct a symmetric doubly
stochastic matrix and introduce the FODAC algorithm, which is further employed
to design our DACFL approach. In section 5, the convergence of DACFL is
theoretically analyzed on the premise of some relatively ideal assumptions.
Then section 6 presents the experiments and evaluates the performance of DACFL
compared with CDSGD and D-PSGD. Finally, section 7 concludes this paper.

##  2 Related Works

In this section, we first provide a brief introduction to federated learning,
and then summarize some related work about decentralized federated learning
implementations and about dynamic average consensus.

###  2.1 Federated Learning

From the technical perspective, there are two main strategies implementing
federated learning: Horizontal Federated Learning (HFL) and Vertical Federated
Learning[7]. In HFL, participating clients share the same set of features but
target different populations. While in VFL, the client devices share the same
population but target different sets of features. Note that throughout this
paper, we focus only on the HFL. For detail introduction about VFL, please
refer to [13, 14].

The concept of federated learning was first introduced[15], where a
distributed training model is executed by a number of participants, usually
called clients or users, that share local model updates with a central
parameter server whose role is to aggregate these updates to build a global
model. Generally, a federated learning scenario consists of two main phases,
i.e., local update and global aggregation. In the local update phase, clients
compute the gradients to minimize the underlying loss function using their
local data. While in the global aggregation phase, the central parameter
server collects the model updates from different clients, aggregates these
model updates to form a global model and then sends back the aggregated result
to the clients for their next training epoch.

Formally, suppose there are a subset of clients $C\subseteq N$ selected by the
PS at training epoch $t\leq T$. Each client $c\in C$ keeps a local training
dataset $D_{c}=\left\\{X_{c},Y_{c}\right\\}$, where
$X_{c}\in\mathbb{R}^{\left|D_{c}\right|\times d}$ represents the feature space
of client $c$’s training data and
$Y_{c}\in\mathbb{R}^{\left|D_{c}\right|\times m}$ is the associated label
space of $D_{c}$. Let $\ell\left(\omega;x_{i},y_{i}\right)$ denote the loss
function of data sample $x_{i}$, where $\omega$ denotes the parameters of
neural networks, then the local loss function of client $c$ over training
dataset $D_{c}$ can be expressed as

$f_{c}\left(\omega\right)=\frac{1}{\left|D_{c}\right|}\sum_{i\in
D_{c}}\ell\left(\omega;x_{i},y_{i}\right)$ (1)

While for the global loss function over all clients $C$ and the whole training
dataset, it can be given as

$f\left(\omega\right)=\sum_{c=1}^{\left|C\right|}\frac{\left|D_{c}\right|}{\left|D\right|}f_{c}\left(\omega\right)$
(2)

where $D=\bigcup_{c}D_{c}$ represents for the whole training dataset over
clients subset $C$ and
$\left|D\right|=\sum_{c=1}^{\left|C\right|}\left|D_{c}\right|$ denotes the
total number of the data samples.

To solve the above distributed optimization problem, existing work has offered
several suggestions. A necessarily incomplete list of these solutions includes
FedAvg [15], FedProx [16], FedPAQ [17], Turbo-Aggregate [18], FedMA [19],
Semi-FL [20] and Hier-FL [21]. However, all these approaches rely on a
centralized network topology where a central parameter server is necessary to
execute the global aggregation phase in federated learning 222Note that in
this section, we only aim at clarifying some definitions and preliminaries of
federated learning. For a more comprehensive study of federated learning,
please refer to [7, 22, 23]..

###  2.2 Decentralized Federated Learning Implementation

Actually, apart from references [9] and [10] which have been introduced in
section 1, there has also been some existing work to date devoting to deep
learning with decentralized computation without the aid of a PS. In [24], the
authors present a distributed learning algorithm to address the fully
decentralized federated learning problem. In this framework, users take a
Bayesian-like approach to iterate and aggregate the beliefs of their one-hop
neighbors and collaboratively estimate the global optimal parameter. In [25],
the authors propose a server-less, peer-to-peer approach for federated
learning termed BrainTorrent, particularly targeted towards medical
applications. In this approach, all clients are assumed pair-wise connected
and update their models by checking the local model version with the latest
model version over the network. In [26], the authors propose a decentralized
federated learning design, Combo, based on the gossip protocol. They also
present a model segmentation level synchronization mechanism in order to
maximize the utilization of bandwidth capacities between users. However, their
design also requires a fully connected network topology and a prerequisite of
randomly distributed data among the workers. While in [27], the authors
further extend the Combo into a bandwidth aware solution BACombo by greedily
choosing the bandwidth-sufficient worker to reduce the transmission delay. In
[28], the authors design an experimental study to compare federated learning
with gossip learning, and find that gossip learning is comparable to federated
learning in their result. In [29], the authors propose a decentralized
federated learning framework based on blockchain termed BFLC. The framework
uses blockchain for the global model storage and the local model update
exchange without a central server. In [30], the authors introduce a fully
decentralized federated learning framework, termed IPLS, that is partially
based on the interplanetary file system (IPFS). By using IPLS and connecting
into the corresponding private IPFS network, any party can initiate the
training process of a model or join an ongoing training process that has
already been started by another party. In [31], the authors propose the
decentralized federated learning via mutual knowledge transfer (Def-KT)
algorithm where local clients fuse models by transferring their knowledge to
each other.

Input: Maximum epoch $m$; learning rate $\alpha$; number of agents $N$;

Output: The trained models of $N$ users:
$x_{m+1}^{1},x_{m+1}^{2},\cdots,x_{m+1}^{N}$;

1 Initialize: $x_{0}^{j},\left(j=1,2,\cdots,N\right)$;

2 Distribute the training dataset to $N$ agents;

3 for  _each agent_ do

4 for  _$k=0:m$_ do

5 Randomly shuffle the corresponding data subset $\mathcal{D}_{j}$;

6 $\omega_{k+1}^{j}=\sum_{l\in Nb_{(j)}}\pi_{jl}x_{k}^{l}$;

/* $Nb_{(j)}$ indicates the neighborhood of agent $j$;
$\Pi=\left[\pi_{jl}\right]\in\mathbb{R}^{N\times N}$ indicates the connection
weights between agents; */

7 $x_{k+1}^{j}=\omega_{k+1}^{j}-\alpha g_{j}(x_{k}^{j})$;

/* $g_{j}(x_{k}^{j})$ is stochastic gradient of loss at $x_{k}^{j}$; */

8

9 end for

10

11 end for

Algorithm 1 CDSGD (baseline 1) [9]

Input: initial point $x_{0,i}=x_{0}$, step length $\gamma$, weight matrix $W$,
and number of iterations $K$;

1 for  _$k=0,1,2,\cdots,K-1$_ do

2 Sample $\xi_{k,i}$ from local data on $i$-th node;

3 Compute a local stochastic gradient based on $\xi_{k,i}$ and current
optimization variable $x_{k,i}$: $\nabla F_{i}\left(x_{k,i};\xi_{k,i}\right)$;

4 Compute the neighborhood weighted average by fetching optimization variables
from neighbors: $x_{k+\frac{1}{2},i}=\sum_{j=1}^{n}W_{ij}x_{k,j}$;

5 Update the local optimization variable: $x_{k+1,i}\leftarrow
x_{k+\frac{1}{2},i}-\gamma\nabla F_{i}\left(x_{k,i};\xi_{k,i}\right)$;

6

7 end for

Output: $\frac{1}{n}\sum_{i=1}^{n}x_{K,i}$; /* the D-PSGD additional needs a
network-wide average comparing to CDSGD; */

8

Algorithm 2 D-PSGD on the $i$th node (baseline 2) [10]

###  2.3 Dynamic Average Consensus

The dynamic average consensus problem, in opposition to the more studied
static consensus [32], is referred to the problem in which a set of autonomous
agents aims to track the average of individually measured time-varying signals
by local communication with neighbors. It has already been widely used in
various fields such as formation control [33], sensor fusion [34, 35, 36],
distributed estimation [37] and distributed tracking [38].

Some existing work has studied the dynamic average consensus problem regarding
the continuous-time reference inputs [34, 39, 35, 40]. In [34], the authors
use standard frequency-domain techniques and show that their algorithm is able
to track the average of ramp reference inputs with zero steady-state error. In
the context of input-to-state stability, the authors of [39] show that
proportional dynamic average consensus algorithm can track with bounded
steady-state error the average of bounded reference inputs with bounded
derivatives. Besides, a proportional-integral dynamic average consensus
algorithm is also designed to track the average of constant reference inputs
with sufficiently small steady-state error. In [35], the authors propose a
dynamic consensus algorithm and apply it to design consensus filters. Their
algorithm can track with some bounded steady-state error the average of a
common reference input with a bounded derivative. In [40], the authors study a
problem similar to that in [36] but further assume that agents know the
nonlinear model which generates the time-varying reference function.

While for the dynamic average consensus problem regarding the discrete-time
reference inputs, the authors of [41] have proposed a class of discrete-time
dynamic average consensus algorithms and analyzed their convergence
properties. Their algorithms are able to track a class of time-varying
reference inputs including polynomials, logarithmic-type functions, periodic
functions and other functions whose $n$-th-order differences are bounded, for
$n\geq 1$, with zero or sufficiently small steady-state error.

For our decentralized federated learning implementation in this paper, we
employ the first-order dynamic average consensus (FODAC) algorithm [41] (see
Algorithm 4) for each user to track the average model in the absence of
central PS.

##  3 System Model and Problem Formulation

For federated learning in a centralized topology, the most critical stage is
that the central PS aggregates the model updates from different users and
sends back the global model to them iteratively. However, when it comes to a
decentralized topology where there is no PS, one of the most difficult problem
arises, i.e., how can we execute the global aggregation phase in a fully
decentralized way in the absence of a central parameter server?

In this section, we first formulate a user as a node in an undirected weighted
graph in 3.1. Then, how the users communicate is formulated as a communication
model based on a symmetric and doubly stochastic symmetric matrix (also
referred to as a mixing matrix) in 3.2. Finally, we formally constitute the
decentralized federated learning implementation as a minimization optimization
problem in 3.3.

###  3.1 Node Model

A node model refers to a user containing its own local dataset and training
its local model using the local training data.

Assume that there are $N$ nodes in a decentralized network topology, where
each node is labeled by $i\in V=\\{1,2,\cdots,N\\}$. We denote the local
dataset on the $i$-th node ${D}_{i}$, then the whole dataset formed by all
local dataset is ${D}={D}_{1}\cup\cdots\cup{D}_{N}$, where
${D}_{i}\cap{D}_{j}=\emptyset$ if $i\neq j$.

The machine learning model of node $i$ at round $t\left(1\leq t\leq T\right)$
is represented by $\omega_{i}^{t}$. Generally, all nodes’ machine learning
models are required to be structured identical (i.e., the depth of the neural
network, each layer’s type and width, etc.) and to be initialized by the same
parameters, i.e.,
$\omega_{1}^{0}=\omega_{2}^{0}=\cdots=\omega_{N}^{0}=\omega^{0}$. Here the
$\omega^{0}$ denotes model initialization, which usually follows Glorot-
initialization [42] or He-initialization [43] in Pytorch. For the local update
phase, each node trains its own $\omega_{i}^{t}$ using its local training
dataset. Hence, the intermediate model parameters generated by each node $i$
during the local update phase can be regarded as a discrete-time reference
signal
$\boldsymbol{\omega}_{i}=\\{\omega_{i}^{0},\omega_{i}^{1},\cdots,\omega_{i}^{T}\\}$.
We also define $\bar{\omega}^{t}=\frac{1}{N}\sum_{i=1}^{N}\omega_{i}^{t}$ the
average model over $N$ nodes at round $t$. However, to implement federated
learning, a global aggregation phase is still needed in addition to local
update. So, we are now faced with the problem of how to make nodes
periodically synchronize the average model in the absence of a central PS?

###  3.2 Communication Model

A communication model in this section refers to two rules that govern the
information exchange between all nodes. One is a connectivity rule ensuring
that the information of each node influences the information of any other
nodes. The other is a rule on connection weights that a node uses when combing
its information with the information received from its neighbors.

We represent a decentralized network topology formed by $N$ nodes at round $t$
as an undirected graph
$\mathcal{G}\left(t\right)\coloneqq\left(V,E\left(t\right)\right)$, where the
$E(t)\subset V\times V$ is an edge set. Besides, node $i$ and $j$ are called
neighbor nodes to each other if and only if $(i,j)\in E(t)$, which further
means that node $i$ and node $j$ can directly communicate with each other at
round $t$. For the connectivity rule, the $\mathcal{G}(t)$ is required to be a
connected graph [44], such that the information of node $i$ can influence the
information of any other nodes directly or indirectly. While for the
connection weights, we further define a mixing matrix
$\mathbf{W}(t)=\left[\mathbf{w}_{ij}(t)\right]\in\mathbb{R}^{N\times N}$ to
denote the connection weights between nodes in $\mathcal{G}(t)$, where

$\left\\{{\begin{array}[]{*{20}{c}}{0<\mathbf{w}_{ij}(t)<1,\text{if }(i,j)\in
E(t)}\\\ {\mathbf{w}_{ij}(t)=0,\text{if }(i,j)\notin
E(t)}\end{array}.}\right.$ (3)

For the sake of convergence, the $\mathbf{W}(t)$ is required to be a doubly
stochastic symmetric matrix, i.e., it satisfies
$\mathbf{W}(t)\mathbf{1}=\mathbf{1}$ and
$\mathbf{1}^{\mathrm{T}}\mathbf{W}(t)=\mathbf{1}^{\mathrm{T}}$. Here
$\mathbf{1}\in\mathbb{R}^{N}$ is the column vector whose entries are all ones,
$\mathrm{T}$ indicates the matrix transpose operator. The doubly stochastic
property ensures a weighted average where the weight sum is 1 when a node
combines other nodes’ information.

###  3.3 Problem Formulation

On the basis of node model and communication model, a remaining problem is how
to effectively execute global aggregation phase without the help of a central
PS? In other words, how to enable each node to synchronize the average model
in the absence of the PS? In what follows, we show that implementing global
aggregation phase in a decentralized topology can be converted into a dynamic
average consensus problem and hence a dynamic consensus algorithm can be
employed to effectively solve it.

Specifically, by treating the local update phase as a discrete-time process
and taking the
$\boldsymbol{\omega}_{i}=\\{\omega_{i}^{0},\omega_{i}^{1},\cdots,\omega_{i}^{T}\\}$
as the discrete-time reference input on node $i$, to synchronize the average
model is to track the average of all nodes’ reference inputs, which can be
also referred to as a dynamic average consensus problem, whose objective can
be formulated as:

$\min_{\boldsymbol{x}^{t}}\left\|\boldsymbol{x}^{t}-\bar{\omega}^{t-1}\mathbf{1}\right\|_{2}^{2}$
(4)

Here $x_{i}^{t}$ denotes the estimation of node $i$ at round $t$,
$\bar{\omega}^{t}$ denotes the average model at round $t$, and
$\boldsymbol{x}^{t}$ is a vector denoting all the estimations on $N$ nodes at
round $t$
$\boldsymbol{x}^{t}=\left[x_{1}^{t};x_{2}^{t};\cdots;x_{N}^{t}\right]$. In
this paper, we advocate the first-order dynamic average consensus (FODAC)
algorithm [41] (see Algorithm 4) to solve problem (4) during the decentralized
federated learning process.

In addition to the consensus problem (4), another objective for federated
learning is to minimize the global loss function shown by (2). So, we can
summarize the objective of the decentralized federated learning as follows:

$\left\\{\begin{array}[]{l}\min\limits_{\omega}f(\omega)\coloneqq\sum_{i=1}^{N}\frac{\left|D_{i}\right|}{\left|D\right|}f_{i}(\omega)\\\
\min\limits_{\boldsymbol{x}^{t}}\left\|\boldsymbol{x}^{t}-\bar{\omega}^{t-1}\mathbf{1}\right\|_{2}^{2}\end{array}\right.$
(5)

Moreover, if each node holds the same number of training samples, (5) can be
rewritten as:

$\left\\{\begin{array}[]{l}\min\limits_{\omega}f(\omega)\coloneqq\frac{1}{N}\sum_{i=1}^{N}f_{i}(\omega)\\\
\min\limits_{\boldsymbol{x}^{t}}\left\|\boldsymbol{x}^{t}-\bar{\omega}^{t-1}\mathbf{1}\right\|_{2}^{2}\end{array}\right.$
(6)

In section 4, we design a DACFL algorithm to solve this problem.

##  4 Algorithm Design

To facilitate our proposed solution, we need to first construct a symmetric
doubly stochastic matrix. Therefore, we first demonstrate how we construct the
symmetric doubly stochastic matrix. Then, a brief introduction to the first-
order dynamic average consensus algorithm is given. And last, we propose the
DACFL training algorithm for our decentralized FL implementation.

###  4.1 Construct a Symmetric Doubly Stochastic Matrix

A symmetric doubly stochastic matrix is defined as a square matrix
$\mathbf{W}$ which meets $\mathbf{W}\mathbf{1}=\mathbf{1}$,
$\mathbf{1}^{\mathrm{T}}\mathbf{W}=\mathbf{1}^{\mathrm{T}}$,
$\forall\mathbf{w}_{ij}\in\mathbf{W}\geq 0$ [32, 45]. Intuitively, a very
simple matrix that meets these conditions can be
$\mathbf{W}\coloneqq\left[\frac{1}{n}\right]^{n\times n}$. To generate a more
random matrix $\mathbf{W}$, we take the following heuristic method to
construct the mixing matrix used in this paper: (i) generate a doubly
stochastic matrix $\mathbf{A}$; (ii) transpose the matrix $\mathbf{A}$ and get
$\mathbf{A}^{\mathrm{T}}$; (iii) symmetrization:
$\mathbf{W}=\frac{1}{2}\left(\mathbf{A}+\mathbf{A}^{\mathrm{T}}\right)$. The
heuristic construction method is shown in Algorithm 3333For the specific
“sparse matrix” in section 6, it is generated by the Sinkhorn-Knopp algorithm
[46]..

Input: Dimension: $n$;

Output: Matrix: $\mathbf{W}$;

1 $\mathbf{A}(1,1)=\rm{\textbf{rand}}$;

2 for  _$i=2:n-1$_ do

3 $d=1-\rm{\textbf{sum}}\left(\mathbf{A}\left(1,1:i-1\right)\right)$;

4 $\mathbf{A}(1,i)=d\times\rm{\textbf{rand}}$;

5

6 end for

7

8for  _$i=2:n-1$_ do

9 $d=1-\rm{\textbf{sum}}\left(\mathbf{A}\left(1:i-1,1\right)\right)$;

10 $\mathbf{A}(i,1)=d\times\rm{\textbf{rand}}$;

11

12 end for

13for  _$i=2:n-1$_ do

14 for  _$j=2:n-1$_ do

15 $d_{1}=1-\rm{\textbf{sum}}\left(\mathbf{A}(i,1:j-1)\right)$;

16 $d_{2}=1-\rm{\textbf{sum}}\left(\mathbf{A}(1:i-1,j)\right)$;

17 $d=\rm{\textbf{min}(d_{1},d_{2})}$;

18 $\mathbf{A}(i,j)=d\times\rm{\textbf{rand}}$;

19

20 end for

21

22 end for

23for  _$i=1:n-1$_ do

24 $\mathbf{A}(n,i)=1-\rm{\textbf{sum}}(\mathbf{A}(1:n-1,i))$;

25

26 end for

27for  _$i=1:n$_ do

28 $\mathbf{A}(i,n)=1-\rm{\textbf{sum}}(\mathbf{A}(i,1:n-1))$;

29

30 end for

31if  _$\mathbf{A}(n,n) <0$_ then

32 Repeat line 1-22;

33

34 end if

35$\mathbf{W}=\frac{1}{2}\left(\mathbf{A}+\mathbf{A}^{\mathrm{T}}\right)$;

/* rand: a function that randomly generates a float number in $(0,1)$; */

/* sum: a sum function; */

/* min: a minimum function;: */

Algorithm 3 A heuristic method to construct a symmetric doubly stochastic
matrix

###  4.2 First-Order Dynamic Average Consensus

As is demonstrated in section 3.3, by treating the intermediate models
generated during the local update phase as the discrete-time reference inputs,
to synchronize the average model can be also referred to as a dynamic average
consensus problem (4). To solve this problem, [41] has proposed a first-order
dynamic average consensus algorithm (FODAC) and has proved that the FODAC
tracks the average state with either a zero steady-state error or an upper-
bounded steady-state error (cf. [41]). Algorithm 4 briefly shows the
pseudocode of FODAC.

Input: Reference inputs of $N$ nodes: $r_{i}(t),(i=1,2,\cdots,N)$;

Output: Consensus states of $N$ nodes: $x_{i}(T),(i=1,2,\cdots,N)$;

1 Initialize: mixing matrix
$\mathbf{W}=\left[\mathbf{w}_{ij}\right]\in\mathbb{R}^{N\times N}$;
initialized consensus state: $x_{i}(0)=r_{i}(0)$; number of iterations: $T$;

2 for  _$t=0,1,2,\cdots,T$_ do

3 $x_{i}(t+1)=x_{i}(t)+\sum_{j\neq
i}\mathbf{w}_{ij}\left(x_{j}(t)-x_{i}(t)\right)+\Delta r_{i}(t)$;

/* $\Delta r_{i}(t)$ indicates the first-order difference of $r_{i}(t)$:
$\Delta r_{i}(t)=r_{i}(t)-r_{i}(t-1)$; */

4

5 end for

Algorithm 4 First-order dynamic average consensus [41]

###  4.3 DACFL Algorithm

As is formulated in (5) (or (6)), the objective of the decentralized federated
learning implementation is to simultaneously minimize a global loss function
$f(\omega)$ and solve a dynamic average consensus problem. For the former sub-
problem, a distributed stochastic gradient descent can be used here-in, while
for the latter sub-problem, we employ the FODAC to solve it. By combining the
distributed gradient descent and the FODAC method, we devise an algorithm
called Dynamic Average Consensus based Federated Learning (DACFL).

Three main steps constitute our DACFL algorithm: (i) each node trains its own
model using its local data; (ii) each node computes a neighborhood weighted
average model $\omega_{i}^{t^{\prime}}$ by exchanging its intermediate model
with its neighbors; (iii) each node performs the FODAC to track the average
model $\bar{\omega}^{t}$. More specifically, step (i) can be also referred to
as the local update phase in federated learning. In step (ii), we further use
the neighborhood weighted average model $\omega_{i}^{t^{\prime}}$ to
reinitialize the user’s local model (line 6, Algorithm 5), which also
differentiates CDSGD and D-PSGD. As is empirically demonstrated in our
experimental results, such re-initialization is more robust to sparse topology
and non-i.i.d data since it to some extent avoids the local overfitting
problem. In step (iii), we employ the FODAC to estimate the average model of
all nodes in a fully decentralized manner, which helps handle the model fusion
in global aggregation phase without a central PS. The complete DACFL training
algorithm is shown in Algorithm 5.

Input: mixing matrix:
$\mathbf{W}(t)=\left[\mathbf{w}_{ij}(t)\right]\in\mathbb{R}^{N\times N}$;
initialized models of $N$ nodes:
$\omega_{1}^{0}=\omega_{2}^{0}=\cdots=\omega_{N}^{0}$; initialized consensus
states of $N$ nodes: $x_{1}^{0}=x_{2}^{0}=\cdots=x_{N}^{0}$; number of
communication rounds $T$; number of nodes $N$; learning rate $\lambda$;

Output: consensus states of $N$ nodes: $x_{1}^{T},x_{2}^{T},\cdots,x_{N}^{T}$;

1 Initialize:
$\boldsymbol{x}^{0}\coloneqq\left[x_{1}^{0},x_{2}^{0},\cdots,x_{N}^{0}\right];\boldsymbol{\omega}^{0}\coloneqq\left[\omega_{1}^{0},\omega_{2}^{0},\cdots,\omega_{N}^{0}\right]$;
$\boldsymbol{x}^{0}=\boldsymbol{\omega}^{0}$;

2 for  _each node $i\in 1,2,\cdots,N$ parallel_ do

3 for  _$t=0,1,2,\cdots,T-1$_ do

4 Compute the neighborhood weighted average model:
$\omega_{i}^{t^{\prime}}=\sum_{j=1}^{N}\mathbf{w}_{ij}(t)\omega_{j}^{t}$;

5 Randomly sample a batch training data $\zeta_{i}^{t}$ from local data on
$i$-th node;

6 Use neighborhood weighted average model to reinitialize and update the local
model: $\omega_{i}^{t+1}\leftarrow\omega_{i}^{t^{\prime}}-\lambda\nabla
f_{i}\left(\omega_{i}^{t^{\prime}};\zeta_{i}^{t}\right)$;

/* $f_{i}(\cdot)$ indicates the loss function on node $i$; $\nabla$ indicates
the gradient operator; */

Perform the average consensus by FODAC:
$\Delta\omega_{i}^{t}=\omega_{i}^{t}-\omega_{i}^{t-1}$; /*
$\omega_{i}^{-1}=\omega_{i}^{0}$ */

7
$x_{i}^{t+1}=\sum_{j=1}^{N}\mathbf{w}_{ij}(t)x_{j}^{t}+\Delta\omega_{i}^{t}$;

8

9 end for

10

11 end for

Algorithm 5 DACFL (our solution)

##  5 Convergence Analysis

Without loss of generality, each user is assumed to hold the same number of
training samples in this paper such that we can denote the loss function
$f(x)$ as

$f(\omega)\coloneqq\frac{1}{N}\sum_{i=1}^{N}f_{i}(\omega)$ (7)

To complete the analysis, we make the following assumptions on the loss
functions.

######  Assumption 1.

(L-Smooth) Each loss function $f_{i}(\omega)$ is L-smooth such that

$f_{i}(v)\leq f_{i}(w)+(v-w)^{\mathrm{T}}\nabla
f_{i}(w)+\frac{L}{2}\|v-w\|_{2}^{2}$ (8)

In a conventional centralized learning way, the gradient $\nabla f(\omega)$ is
computed based on the whole dataset. However, in a decentralized federated
learning, each user holds a local data shard for its own training and gradient
computation $\nabla f_{i}(\omega)$. To declare the user-wise gradients $\nabla
f_{i}(\omega)$, we have Assumption 2 and 3 on the premise of i.i.d data.

######  Assumption 2.

(Bounded Gradients) For each user $i$ and a randomly sampled batch data
$\zeta_{i}$, there exists $G>0$ such that

$\mathbb{E}_{\zeta_{i}\sim\mathcal{D}_{i}}\left\|\nabla
f_{i}\left(\omega;\zeta_{i}\right)\right\|^{2}\leq G^{2}$ (9)

######  Assumption 3.

(Uniform Gradient First-order Difference) At any round $t$, define

$\displaystyle\Delta\mathcal{g}_{i}^{t}=\nabla
f_{i}(\omega^{t^{\prime}};\zeta_{i})-\nabla
f_{i}(\omega^{t-1^{\prime}};\zeta_{i})=\mathcal{g}_{i}^{t}-\mathcal{g}_{i}^{t-1}$

as the first-order difference of gradient, this paper assumes an i.i.d data
distribution over all users for the convergence analysis, such that

$\mathbb{E}\left[\Delta\mathcal{g}_{i}^{t}\right]=\mathbb{E}\left[\Delta\mathcal{g}_{j}^{t}\right]=\Delta\mathcal{g}^{t},\forall
i,j,\,1\leq i,j\leq N$ (10)

Note that the mixing matrix $\mathbf{W}(t)$ of the communication network
topology $\mathcal{G}(t)$ plays a pivotal role enabling our algorithm, which
follows the assumptions.

######  Assumption 4.

(Symmetric Doubly Stochastic Matrix) At any round $t$, the mixing matrix
$\mathbf{W}(t)$ is symmetric and doubly stochastic, such that

$\mathbf{W}(t)\mathbf{1}=\mathbf{1},\mathbf{1}^{\mathrm{T}}\mathbf{W}(t)=\mathbf{1}^{\mathrm{T}},\mathbf{W}(t)=\mathbf{W}(t)^{\mathrm{T}}$
(11)

Additionally, we make Assumption 5 to ensure the average model parameter can
be well tracked.

######  Assumption 5.

(Bounded First-order Differences of Model Parameter) At any round $t$, there
exists a constant $\theta>0$ ensures an upper bound of each user’s model
parameters such that

$\left\|\omega_{i}^{t}-\omega_{i}^{t-1}\right\|^{2}\leq\theta^{2}$ (12)

Actually, the above statement can be guaranteed by choosing a sufficiently
small learning step size $\lambda$ and a proper activation function.

Following the Assumption 5, we can easily draw a relatively bounded first-
order difference similar to Eq.(1) in [41] such that

$\displaystyle\Delta\omega_{\rm{max}}^{t}-\Delta\omega_{\rm{min}}^{t}\leq\kappa$
(13)

where $\kappa$ is the upper bound related to $\theta$ and

$\displaystyle\Delta\omega_{i}^{t}:=\omega_{i}^{t}-\omega_{i}^{t-1}$
$\displaystyle\Delta\omega_{\rm{max}}^{t}:=\max_{i=1,2,\dots,N}\Delta\omega_{i}^{t}$
$\displaystyle\Delta\omega_{\rm{min}}^{t}:=\min_{i=1,2,\dots,N}\Delta\omega_{i}^{t}$

The above (13) ensures the FODAC to track the average of the time-varying
reference inputs, w.r.t., model parameters $\omega_{i}^{t}$, with a
sufficiently small steady-state error. For detail proof of the conclusion,
please refer to [41]. Note, to track the average of matrix-form reference
inputs can be reformulated as tracking the average of scalar-form reference
inputs by considering the matrix as a set of element-wise scalars.

Following the above assumptions, we present the convergence rate of our
proposed algorithm. In our result, we follow the convention in literature [10]
to use the average expected squared gradient norm to characterize the
convergence rate.

######  Theorem 1.

Following the aforementioned assumptions, we have the average expected squared
gradient norm following

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}$ $\displaystyle\leq\frac{2}{\lambda
T}\mathbb{E}\left(f(\bar{\omega}^{0})-f(\bar{\omega}^{T})\right)+G^{2}+\frac{\theta^{2}}{\lambda^{2}}+\frac{L\theta^{2}}{\lambda}$
(14) $\displaystyle\leq\underbrace{\frac{2}{\lambda
T}\left(f(\bar{\omega}^{0})-f^{*}\right)}_{:\rm{C}_{0}}+\underbrace{G^{2}+\frac{\theta^{2}}{\lambda^{2}}+\frac{L\theta^{2}}{\lambda}}_{:\rm{C}_{1}}$

where $f^{*}$ denotes the minimum loss value of $f(x)$.

Note that in (14), the average squared gradient norm is bounded by
$\rm{C}_{0}+\rm{C}_{1}$, where the $\rm{C}_{0}$ gradually tends to $0$ when
training iteration $T$ increases. In other words, the average squared gradient
norm is bounded by a learning rate related term $\rm{C}_{1}$ when
$T\to+\infty$. Until now, we have declared the convergence taking the average
model parameter $\bar{\omega}^{t}$ as the input of loss function $f$.
Moreover, the final output of DACFL algorithm
$\boldsymbol{x}^{T}=[x_{1}^{T},x_{2}^{T},\dots,x_{N}^{T}]^{1\times N}$ can
track the $\bar{\omega}^{T}$ with a small steady-state error under the above
assumptions. (Please refer to [41] for the convergence guarantee of FODAC.)
This further offers a convergence guarantee for our DACFL solution.

The detailed proof of Theorem 1 is deferred to the appendix of this paper.

##  6 Experiments and Performance Evaluation

In this section, we first declare the experimental setup and then evaluate the
performance of DACFL on different datasets with vary topologies and data
allocations. Note that, the curves of following experimental result are
smoothed by Savitzky-Golay filter [47].

###  6.1 Experimental Setup

####  6.1.1 Dataset

Three publicly accessible datasets including MNIST [48], Fashion-MNIST
(FMNIST) [49] and CIFAR-10 [50] widely used in image classification field are
used for our performance validation in this paper. (i) MNIST: a dataset
includes 70,000 images of hand-written digits, totally 10 classes, with a
training set consisting 60,000 examples and a test set consisting 10,000
examples, respectively. (ii) Fashion-MNIST: a new dataset comprises
28$\times$28 grayscale images of 70,000 fashion products from 10 categories.
The training set has 60,000 images and the test set has 10,000 images. (iii)
CIFAR-10: a dataset consists totally 60,000 color images with three RGB
channels which can be classified into 10 classes. The training set has 50,000
examples and the test set has 10,000 examples.

####  6.1.2 Dataset Allocation

We design two ways for data allocation in our experiments, i.e., i.i.d and
non-i.i.d allocations. (i) i.i.d: each user is assigned the same number of
training samples with a uniformly random distribution over 10 classes. (ii)
non-i.i.d: the training set is sorted by labels first and then divided into
multiple shards with the same number of training samples. Finally, each user
samples only 2 shards of data without replacement. Note that in this setup,
the non-i.i.d allocation only considers the class imbalance of data [22].

####  6.1.3 Communication Network Topology

As is demonstrated in section 3, we can represent the communication network
topology with the mixing matrix. In our experiments, we design the topology
from different perspectives. (i) time-varying and time-invariant: for the
time-invariant topology, we initialize the mixing matrix before training and
keep it unchanged during the training process; while for the time-varying
topology, we reconstruct the mixing matrix every 10 training rounds. (ii)
sparse and dense connectivity: for the sparse ($\psi$=0.5) topology, half
entries of the mixing matrix are 0; while for the dense ($\psi$=1.0) topology,
all entries in the mixing matrix are non-zeros. 444Note here we call a matrix
with ‘sparse’ just for simplicity, which is not strictly equivalent to a
“sparse matrix”. The “sparse matrix” here is generated by Sinkhorn-Knopp
algorithm [46]. All the above considered mixing matrices are symmetric and
doubly stochastic.

####  6.1.4 Neural Network Structure

For the training models used to perform the image classification tasks, we use
the same convolutional neural network (CNN) for MNIST and Fashion-MNIST which
contains two 5$\times$5 convolutional layers (each layer is followed with a
batch normalization and 2$\times$2 max pooling), a fully connected layer with
ReLu activation and a final softmax output layer. For CIFAR-10 dataset, we use
a CNN consisting two convolutional layers (each layer is followed with batch
normalization, ReLu activation and 2$\times$2 max pooling), two fully
connected layers with ReLu activation and a final softmax output layer. Both
CNN models are mended from [15]. Unless otherwise specified, some important
hyper-parameters in our experiments are set as TABLE I.

####  6.1.5 Baselines and Performance Metric

In this work, we compare our DACFL with a conventional centralized federated
learning method, i.e., FedAvg and another two decentralized federated learning
implementations called CDSGD [9] and D-PSGD [10]. For the FedAvg
implementation in this paper, a centralized topology with the same number of
users to the decentralized topology is considered, where all users are ensured
to participate in each training round. For CDSGD and D-PSGD, the mixing matrix
and other hyper-parameters are consistent with DACFL. Additionally, we assume
that there still exists a “god node” for D-PSGD to perform the network-wide
model average, hence generating a global model used for the performance test.
To make the result more clear, we design two metrics including Average of Acc
and Var of Acc to indicate the performances of different methods.
Specifically, we respectively test each user’s trained model (or estimated
model in DACFL) and get the test accuracy of all users. Then the Average of
Acc is computed through averaging all users’ test accuracy and Var of Acc is
the variance over all users’ test accuracy. Generally, a superior
decentralized federated learning method is expected to obtain a higher Average
of Acc and a smaller Var of Acc. Note that for FedAvg and D-PSGD where the
final output is the only global model, the Average of Acc is actually same
with the test accuracy and the Var of Acc is 0.

TABLE I: Experimental parameters setting Parameter | Numerical value
---|---
Number of nodes: | 10
Training rounds: | 100
Local batch size: | 20
Local epoch: | 1
Decaying for learning rate: | 0.995
Loss function: | Cross Entropy
Learning rate: | MNIST/FMNIST: 0.001, CIFAR: 0.005

###  6.2 Why Choose FODAC? A Numerically Empirical Perspective

In order to clarify how FODAC benefits our solution, some specific numerical
experiments are designed in this section. More specifically, we separately
apply FODAC, CDSGD and D-PSGD to track the average of two types of discrete-
time inputs under three different mixing matrices.

Inputs I: A class of discrete-time inputs with relatively large variance
between each user,

$R_{i}(t)=\sin(t)+\left(\frac{1}{t}\right)^{i}+t+i$

Inputs II: A class of discrete-time inputs with relatively small variance
between each user,

$R_{i}(t)=\sin(t)+\left(\frac{1}{t}\right)^{i}+t$

where $R_{i}(t)$ denotes the input of $i$-th user at time $t$, with
$i\in\left\\{1,2,\cdots,10\right\\}$,$t\in\left\\{1,2,\cdots,20\right\\}$.

For the mixing matrices, (i) sparse: a 10$\times$10 mixing matrix with
$\psi$=0.5, i.e., half entries are 0; (ii) dense: a 10$\times$10 mixing matrix
with $\psi$=1.0, i.e., all entries are non-zeros; (iii) uniform: a
10$\times$10 mixing matrix with all entries being 0.1. Note all kinds of
matrices considered here are symmetric doubly stochastic. For CDSGD, we take
roughly the neighborhood weighted average as the estimated value (see line 6
in Algorithm 1); for D-PSGD, the estimated value used here is the result of
executing an additional network-wide average on the estimation by CDSGD. While
for FODAC, we take the consensus state (see line 3 in Algorithm 4) as the
estimated result. Then, the absolute error can be computed by

$\mathrm{abs(err)}=\left|\bar{R}_{i}(t)-\hat{R}_{i}(t)\right|$

where the $\hat{R}_{i}(t)$ denotes the estimated value and $\bar{R}_{i}(t)$
denotes the average of inputs with
$\bar{R}_{i}(t)=\frac{1}{10}\sum_{i=1}^{10}R_{i}(t)$. The results are shown in
Fig. 3.

As can be seen in fig. 3(a), the FODAC is superior to CDSGD when users’
reference inputs are with large variance under both sparse and dense mixing
matrices. It can be concluded that if employing CDSGD to approximate the
average of inputs, an estimating error and a large deviation between users are
not negligible. While the CDSGD becomes feasible only when the inputs turn to
be with small variance or when the mixing matrix is uniform. Nonetheless, the
FODAC still slightly outperforms CDSGD from the perspective of convergence
speed when users’ inputs are with small variance under both sparse and dense
mixing matrices, which are shown in Fig. 3(b). Note that D-PSGD outperforms
the other two methods because it additionally executes a network-wide average
which enables it to accurately compute the average value of the inputs.
However, such a network-wide average is unacceptable when it comes to a fully
decentralized topology where no PS helps to do this.

From this empirical result, we conclude that the FODAC method is more
adaptable than CDSGD and D-PSGD on approximating the average in a fully
decentralized topology. Actually, this also motivates us to employ FODAC to
decentralized federated learning since (i) the common non-i.i.d data usually
leads to a large variance between users’ local models; (ii) a non-ideal
communication topology (a not uniform mixing matrix) often arises in
practical; (iii) there is no central PS to perform a network-wide model
average.

(a) Large variance inputs (Inputs I)

(b) Small variance inputs (Inputs II)

Figure 3: The result of approximating the average by different algorithms

###  6.3 Performance on i.i.d Data

Fig. 4 and 5 respectively shows the performances of different algorithms with
i.i.d data allocation under time-invariant and time-varying topologies. The
hyper-parameters in this experiment follow Table I.

(a) Average of Acc on MNIST

(b) Average of Acc on FMNIST

(c) Average of Acc on CIFAR-10

(d) Var of Acc on MNIST

(e) Var of Acc on FMNIST

(f) Var of Acc on CIFAR-10

Figure 4: Performance comparison with i.i.d data and time-invariant topology
(a communication round also corresponds to a training round in our
experiments).

(a) Average of Acc on MNIST

(b) Average of Acc on FMNIST

(c) Average of Acc on CIFAR-10

(d) Var of Acc on MNIST

(e) Var of Acc on FMNIST

(f) Var of Acc on CIFAR-10

Figure 5: Performance comparison with i.i.d data and time-varying topology

####  6.3.1 Time-invariant Topology

Fig. 4 shows the result with i.i.d data and time-invariant topology. From the
following three perspectives, we can draw different conclusions.

First, the proposed DACFL outperforms D-PSGD and CDSGD in terms of Average of
Acc, albeit slightly inferior to the conventional FedAvg. Specifically, from
fig. 4(a), 4(b) and 4(c), the DACFL finally harvests $97\%$, $86\%$, $70\%$
accuracy under a dense topology and $96\%$, $85\%$, $67\%$ accuracy under a
sparse topology, respectively on MNIST, FMNIST and CIFAR-10 datasets. This is
superior to the result of CDSGD with $93\%$, $64\%$, $18\%$ accuracy under a
dense topology and $68\%$, $51\%$, $20\%$ accuracy under a sparse topology,
and the result of D-PSGD with $97\%$, $83\%$, $55\%$ accuracy under a dense
topology and $95\%$, $75\%$, $45\%$ accuracy under a sparse topology. Since
D-PSGD additionally performs a network-wide model average over all users, it
holds a better Average of Acc than CDSGD. Contrarily, there exists different
levels of deviation between user’s intermediate training models, which may
severely rely on the unevenness of the decentralized communication network
topology. By means of FODAC, each user in DACFL is able to well approximate
the “near average” model. This is exactly why DACFL outperforms CDSGD and
D-PSGD in this experiment.

Second, the DACFL is less sensitive to the sparsity of communication topology.
That is, the DACFL has minimal degradation in the Average of Acc when a sparse
topology arises. Specifically, the DACFL has $1\%$, $1\%$, $3\%$ of accuracy
reduction on three datasets. While the D-PSGD has reduction of $2\%$, $8\%$,
$10\%$ on three datasets and the CDSGD has reduction of $25\%$, $13\%$ on
MNIST and FMNIST.555Since CDSGD dose not converge on CIFAR-10 after 100
rounds, it is not counted here. This result indicates that both CDSGD and
D-PSGD ask for tighter topology requirements than DACFL for convergence
guarantees.

Third, each user has closer performance in DACFL than that in CDSGD. From fig.
4(d), 4(e) and 4(f), it can be seen that, the variance of accuracy of DACFL is
smaller and more stable when comparing to CDSGD, and gradually tends to around
$0$ as the training progresses, especially on MNIST. This result also supports
that the average model can be well tracked by DACFL through the FODAC
consensus method.

In summary, the DACFL approach outperforms D-PSGD and CDSGD on i.i.d data
under time-invariant topology.

####  6.3.2 Time-varying Topology

In this section, we investigate how the time-varying topology affects the
performance of DACFL and compare it with CDSGD and D-PSGD. Fig. 5 presents the
result on i.i.d data under time-varying topology.

From the perspective of Average of Acc, the DACFL still outperforms D-PSGD and
CDSGD. Take the result on FMNIST dataset as an example (fig. 5(b)), the DACFL
finally reaches $87\%$ accuracy, which is better than the $84\%$ accuracy of
D-PSGD and $68\%$ of CDSGD. Intuitively, the FedAvg with a centralized
topology performs better than other decentralized implementations as it has a
central parameter server to do the global aggregation phase. This would not be
affected by the varying decentralized topology considered in this section.

Besides, a time-varying topology has greater randomness than a time-invariant
topology. Due to the randomness, the accuracy degradation caused by the
topology sparsity becomes smaller for all decentralized implementations
considered in this section. Specially, for D-PSGD on FMNIST (fig. 5(b)) and
CIFAR-10 (fig. 5(c)), the average accuracy under a sparse topology is even
greater than that under a dense topology. This might because that the
randomness introduced by time-varying topology reduces the possibility of
early over-fitting that may be caused by a sparse topology.

Finally, for the Var of Acc shown by Fig. 5(d), 5(e) and 5(f), result similar
to that of a static topology arises. As is shown in the figures, the DACFL
holds smaller and more stable variance of accuracy than CDSGD on both dense
and sparse topology over all the datasets. This confirms the effectiveness of
our approach again.

In summary, the DACFL still has higher feasibility in the case of time-varying
topology.

###  6.4 Performance on non-i.i.d Data

The section 6.3 has shown the result of DACFL on i.i.d data and declared its
practicality under both time-invariant and time-varying topology. In this
section, we test the performance of DACFL on non-i.i.d data and show the
result in Fig. 6 and Fig. 7. The hyper-parameters in this experiment follow
Table I.

####  6.4.1 Time-invariant Topology

Fig. 6 presents the experimental result on non-i.i.d data under time-invariant
topology.

First, for the Average of Acc, both FedAvg and three decentralized federated
learning implementations have different levels of accuracy degradation on
three datasets. This is because the non-i.i.d property would lead to users’
local model divergence and early over-fitting. Since D-PSGD additionally
performs a net-work wide model average, it has higher accuracy than DACFL and
CDSGD in MNIST and FMNIST.666Since all three DFL approaches do not converge in
CIFAR-10, the result on CIFAR-10 is not counted here. However, we should note
that a network-wide model average usually becomes impractical when users are
very scattered in a very large decentralized topology since an acceptable
overhead would be caused by such a network-wide communication. Therefore, in
case that there is no network-wide model average, our DACFL outperforms CDSGD.
Take the result under dense topology as an example, DACFL gets average
accuracy of $86\%$, $70\%$, while CDSGD only reaches $58\%$, $40\%$ on MNIST
and FMNIST, respectively.

Second, the numerical result of Var of Acc in fig. 6(d), 6(e) and 6(f) also
shows the superiority of DACFL compared to CDSGD. Actually, the accuracy
variance is larger than that of i.i.d data due to the non-i.i.d property.
However, we can still see that the accuracy variance of DACFL gradually
decreases and stabilizes as the training progresses.

In summary, the DACFL is also feasible on non-i.i.d data (MNIST and FMNIST)
under time-invariant topology.

(a) Average of Acc on MNIST

(b) Average of Acc on FMNIST

(c) Average of Acc on CIFAR-10

(d) Var of Acc on MNIST

(e) Var of Acc on FMNIST

(f) Var of Acc on CIFAR-10

Figure 6: Performance comparison with non-i.i.d data and time-invariant
topology

(a) Average of Acc on MNIST

(b) Average of Acc on FMNIST

(c) Average of Acc on CIFAR-10

(d) Var of Acc on MNIST

(e) Var of Acc on FMNIST

(f) Var of Acc on CIFAR-10

Figure 7: Performance comparison with non-i.i.d data and time-varying topology

####  6.4.2 Time-varying Topology

Fig. 7 presents the experimental result on non-i.i.d data under time-varying
topology.

It can be seen from fig. 7(a), 7(b) and 7(c) that the overall average accuracy
degradation due to non-i.i.d data still exists when compared with the result
on i.i.d data. Because the randomness introduced by time-variant topology may
alleviate the local model over-fitting caused by non-i.i.d data, our DACFL has
a better performance than that of a time-invariant topology shown in Fig. 6,
especially on FMNIST and CIFAR-10. For the Var of Acc, similar result to Fig.
6 happens, i.e., the variance of DACFL gradually decreases and tends to zero,
which confirms the viability of DACFL on tracking an “average model”.

To sum up, the DACFL is also viable on non-i.i.d data (MNIST and FMNIST) under
time-varying topology.

###  6.5 Convergence Speed vs Learning Rate and Topology Size

To figure out how the learning rate and network topology size affect our
solution, we also log the average test accuracy and average training loss on
i.i.d MNIST with different learning rates and topology sizes. Fig. 8 shows the
numerical result. Note that there are no decaying on learning rate and all
topologies are dense in this part of experiments. Except for the learning rate
and topology size, other hyper-parameters in this experiment follow Table I.

####  6.5.1 Performance vs Learning Rate $\lambda$

Fig. 8(a), 8(b) and 8(c) show the result of average test accuracy, average
training loss and variance over test accuracy with different learning rates,
respectively. From Fig.8(a) and 8(b), we can see that a larger $\lambda$ could
bring the benefit to faster convergence within the range $0.001\leq\lambda\leq
0.01$. This is because a larger learning rate makes the loss function
decreases with a larger step size, which leads to a faster convergence.
However, this situation changes when $0.05\leq\lambda\leq 0.1$, i.e, when
$\lambda$ increases from $0.05$ to $0.1$, the convergence speed and
convergence result become even worse. Smaller average test accuracy and larger
average training loss with greater surge precisely reflect this phenomenon. It
is because that an excessive learning rate $\lambda$ would lead to a larger
upper bound of first-order difference of model parameter $\theta$ and thus
cause a larger relatively upper bound of first-order difference $\kappa$ in
(13). Consequently, a larger relatively bound would lead to a larger steady-
stater error when using FODAC to track the average of users’ models [41].
Hence, an excessive learning rate would be unfriendly to our DACFL solution.
From fig.8(c), it can be seen that a greater learning rate leads to a greater
variance of accuracy. So, $\lambda=0.01$ should be the best choice in this
experiment, which gets a higher average test accuracy and lower variance while
ensuring fast convergence.

####  6.5.2 Performance vs Topology Size $N$

Fig. 8(d), 8(e) and 8(f) present the numerical result on different topology
sizes. It is shown in fig. 8(d) and 8(e) that, as the size of topology $N$
grows, the convergence speed slows down. Also, the larger topology size it is,
the lower final test accuracy it gets. This is because that a larger size of
topology would lead to a larger deviation among all users, which further cause
a slower rate of our FODAC tracking for average model. Regarding the variance
of accuracy, a larger topology usually results in a larger variance in the
early training of our algorithm as is shown in fig. 8(f). However, the
accuracy variance on different topology gradually tend to $0$ after a certain
number of iterations. This also declares the effectiveness of our solution by
employing FODAC to track the average model.

In a summary, a proper learning rate can accelerate the convergence of our
DACFL training. Also, although DACFL is robust to different topology sizes, a
smaller size is preferred to attain a better performance within a limit number
of training rounds.

(a) Average of Acc

(b) Average of Loss

(c) Var of Acc

(d) Average of Acc

(e) Average of Loss

(f) Var of Acc

Figure 8: Performance with different learning rate and topology size

##  7 Conclusions

Over-reliance on the central PS makes the federated learning possibly paralyze
when the server breaks down. To alleviate this single point failure in
conventional FL, existing researches have offered different DFL
implementations including CDSGD and D-PSGD. However, there exists significant
variance between users’ final models in CDSGD while D-PSGD necessitates a
network-wide model average. In this paper, we devise a new DFL method coined
as DACFL to solve the deficiency in CDSGD and D-PSGD. The DACFL treats the
respective local training processes as discrete-time series and employ FODAC
to track the average model over all users. To confirm the feasibility of
DACFL, we also deliver a theoretical analysis on the premise of some
assumptions, which offers a convergence guarantee of our solution. Besides, we
design specific experiments on MNIST, Fashion-MNIST and CIFAR-10 under i.i.d
and non-i.i.d allocations, and compare the DACFL with D-PSGD and CDSGD. The
results verify the effectiveness of DACFL under different network topologies,
and declare that DACFL outperforms D-PSGD and CDSGD in most cases.

There are several issues need further investigation. First, DACFL solves the
problems of CDSGD and D-PSGD at the expense of more communication overhead
because each user exchanges both estimation states and local models during the
training progress. Therefore, a more communication-efficient method for DACFL
is deserved. Second, since this work only considers DACFL with synchronized
settings, an asynchronized decentralized federated learning deserves
investigation for practical application. Third, because DACFL works
effectively only when mixing matrix is symmetric and doubly stochastic, users
dropping out or joining in during the training process will change the nature
of mixing matrix and thus yields negative effects on this method. Thus,
designing an offline and join aware DACFL would be worthy of future research.

##  Appendix A Proof of Theorem

###  A.1 Preliminaries

In this section, we give an upper bound on the expected average squared
gradient norms, which serves as a metric to measure the convergence rate for
the non-convex objectives.

Before the detailed proof, here are some notations avoiding ambiguity. We
denote the mixing matrix
$\mathbf{W}=\left[\mathbf{w}_{ij}(t)\right]\in\mathbb{R}^{N\times N}$ a fully
decentralized communication network topology with $N$ users, where
$x_{i}^{t},\omega_{i}^{t}$ represents for the estimation and local model of
$i$-th user at round $t$, respectively. We further have
${\bar{\omega}^{t}}=\frac{1}{N}\sum_{i=1}^{N}{\omega_{i}^{t}}$ defined as the
average model of all users at round $t$. Besides, we denote
$\omega_{i}^{t^{\prime}}=\sum_{j=1}^{t}\mathbf{w}_{ij}(t)\omega_{j}^{t}$ the
neighborhood weighted average model, and use $\mathcal{g}_{i}^{t}=\nabla
f_{i}\left(\omega_{i}^{t^{\prime}},\zeta_{i}^{t}\right)$ to denote the
stochastic gradient of user $i$ at round $t$, where the
$\zeta_{i}^{t}\subseteq\mathcal{D}_{i}$ is the uniformly sampled mini-batch
from the $i$-th user’s data shards at round $t$. With $\rm{T}$ denoting the
transpose of a matrix, we also define the following notations

${\boldsymbol{x}^{t}}={\left[{x_{1}^{t},x_{2}^{t},\cdots,x_{N}^{t}}\right]^{\rm{T}}},$
${\boldsymbol{\omega}^{t}}={\left[{\omega_{1}^{t},\omega_{2}^{t},\cdots,\omega_{N}^{t}}\right]^{\rm{T}}},$

to denote the sets of estimations and intermediate models at round $t$,
respectively. In the following proof, we consider a time-invariant topology
where $\boldsymbol{\rm{W}}(t)=\boldsymbol{\rm{W}}$, such that
$\mathbf{w}_{ij}(t)=\mathbf{w}_{ij},t=0,1,\dots,T-1$.

###  A.2 Proof of Theorem 1

###### Proof:

According to the updating rules in Algorithm 5 (line 4 to line 6), we have

$\displaystyle\omega_{i}^{t^{\prime}}$
$\displaystyle=\sum_{j=1}^{N}\mathbf{w}_{ij}(t)\omega_{j}^{t}$ (15)
$\displaystyle\omega_{i}^{t+1}$
$\displaystyle=\omega_{i}^{t^{\prime}}-\lambda\mathcal{g}_{i}^{t}$ (16)

where $\mathbf{w}_{ij}(t)\in\mathbf{W}(t)$ denotes the $(i,j)$-th entry of the
mixing matrix, thus

$\begin{split}\mathbb{E}\left[\left\|{\bar{\omega}^{t+1}-\bar{\omega}^{t}}\right\|^{2}\right]&=\mathbb{E}\left[{\frac{1}{N^{2}}}\left\|{\sum_{i=1}^{N}\left(\omega_{i}^{t+1}-\omega_{i}^{t}\right)}\right\|^{2}\right]\\\
&\leq\mathbb{E}\left[\frac{1}{N}\sum_{i=1}^{N}\left\|\omega_{i}^{t+1}-\omega_{i}^{t}\right\|^{2}\right]\\\
&\leq\theta^{2}\end{split}$ (17)

where the (17) follows from Assumption 5.

Take the following recursive equations as examples,

$\displaystyle\omega_{i}^{t+1}-\omega_{i}^{t}$
$\displaystyle=\sum_{j=1}^{N}\mathbf{w}_{ij}\omega_{j}^{t}-\lambda\mathcal{g}_{i}^{t}-\left(\sum_{j=1}^{N}\mathbf{w}_{ij}\omega_{j}^{t-1}-\lambda\mathcal{g}_{i}^{t-1}\right)$
$\displaystyle=\sum_{j=1}^{N}{\mathbf{w}_{ij}\left(\omega_{j}^{t}-\omega_{j}^{t-1}\right)-\lambda\left(\mathcal{g}_{i}^{t}-\mathcal{g}_{i}^{t-1}\right)}$
$\displaystyle\omega_{j}^{t}-\omega_{j}^{t-1}=\sum_{i=1}^{N}\mathbf{w}_{ij}\left(\omega_{i}^{t-1}-\omega_{i}^{t-2}\right)-\lambda\left(\mathcal{g}_{j}^{t-1}-\mathcal{g}_{j}^{t-2}\right)$
$\displaystyle\omega_{i}^{t-1}-\omega_{i}^{t-2}=\sum_{j=1}^{N}\mathbf{w}_{ij}\left(\omega_{j}^{t-2}-\omega_{j}^{t-3}\right)-\lambda\left(\mathcal{g}_{i}^{t-2}-\mathcal{g}_{i}^{t-3}\right)$
$\displaystyle\omega_{j}^{t-2}-\omega_{j}^{t-3}=\sum_{i=1}^{N}\mathbf{w}_{ij}\left(\omega_{i}^{t-3}-\omega_{i}^{t-4}\right)-\lambda\left(\mathcal{g}_{j}^{t-3}-\mathcal{g}_{j}^{t-4}\right)$
$\displaystyle\vdots$
$\displaystyle\omega_{i}^{1}-\omega_{i}^{0}=\sum_{j=1}^{N}\mathbf{w}_{ij}\left(\omega_{j}^{0}-\omega_{j}^{-1}\right)-\lambda\left(\mathcal{g}_{i}^{0}-\mathcal{g}_{i}^{-1}\right)$

Then we have

$\displaystyle\omega_{i}^{t+1}-\omega_{i}^{t}$
$\displaystyle=\underbrace{\sum_{j=1}^{N}\mathbf{w}_{ij}\sum_{i=1}^{N}\mathbf{w}_{ij}\dots\sum_{j=1}^{N}\mathbf{w}_{ij}}_{\Sigma_{i}\,\text{or}\,\Sigma_{j}\,\text{total
$t$ times}}\left(\omega_{j}^{0}-\omega_{j}^{-1}\right)$
$\displaystyle-\underbrace{\sum_{i=1}^{N}\mathbf{w}_{ij}\sum_{j=1}^{N}\mathbf{w}_{ij}\dots\sum_{j=1}^{N}\mathbf{w}_{ij}}_{\Sigma_{i}\,\text{or}\,\Sigma_{j}\,\text{total
$t$-1 times}}\lambda\left(\mathcal{g}_{i}^{0}-\mathcal{g}_{i}^{-1}\right)$
$\displaystyle\vdots$
$\displaystyle-\sum_{j=1}^{N}\mathbf{w}_{ij}\lambda\left(\mathcal{g}_{j}^{t-1}-\mathcal{g}_{j}^{t-2}\right)-\lambda\left(\mathcal{g}_{i}^{t}-\mathcal{g}_{i}^{t-1}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}-\underbrace{\sum_{i=1}^{N}\mathbf{w}_{ij}\sum_{j=1}^{N}\mathbf{w}_{ij}\dots\sum_{j=1}^{N}\mathbf{w}_{ij}}_{\Sigma_{i}\,\text{or}\,\Sigma_{j}\,\text{total
$t$-1 times}}\lambda\left(\mathcal{g}_{i}^{0}-\mathcal{g}_{i}^{-1}\right)$
$\displaystyle-\underbrace{\sum_{j=1}^{N}\mathbf{w}_{ij}\sum_{i=1}^{N}\mathbf{w}_{ij}\dots\sum_{j=1}^{N}\mathbf{w}_{ij}}_{\Sigma_{i}\,\text{or}\,\Sigma_{j}\,\text{total
$t$-2 times}}\lambda\left(\mathcal{g}_{i}^{1}-\mathcal{g}_{i}^{0}\right)$
$\displaystyle\vdots$
$\displaystyle-\sum_{j=1}^{N}\mathbf{w}_{ij}\lambda\left(\mathcal{g}_{j}^{t-1}-\mathcal{g}_{j}^{t-2}\right)-\lambda\left(\mathcal{g}_{i}^{t}-\mathcal{g}_{i}^{t-1}\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}-\lambda\left(\Delta\mathcal{g}_{i}^{t}+\Delta\mathcal{g}_{j}^{t-1}+\dots+\Delta\mathcal{g}_{i}^{0}\right)$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}-\lambda\sum_{t=0}^{t}\Delta\mathcal{g}^{t}$

where $(a)$ follows from the initialization
$\boldsymbol{\omega}^{0}=\boldsymbol{\omega}^{-1}$, $(b)$ follows from the
Assumption 4, and $(c)$ follows from Assumption 3.

Substituting the above equation into (17), we have

$\displaystyle\mathbb{E}\left[\left\|\bar{\omega}^{t+1}-\bar{\omega}^{t}\right\|^{2}\right]$
$\displaystyle=\frac{\lambda^{2}}{N^{2}}\left\|\sum_{i=1}^{N}\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$
(18)
$\displaystyle\leq\frac{\lambda^{2}}{N}\sum_{i=1}^{N}\underbrace{\left\|\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}}_{:\rm{T}_{0}}$
$\displaystyle\leq\mathbb{E}\left[\frac{1}{N}\sum_{i=1}^{N}\left\|\omega_{i}^{t+1}-\omega_{i}^{t}\right\|^{2}\right]$
$\displaystyle\leq\theta^{2}$

So, we can bound $\rm{T}_{0}$ following (18),

$\displaystyle T0\leq\frac{\theta^{2}}{\lambda^{2}}$ (19)

Given the L-smooth assumption, the following inequality holds

$\displaystyle\mathbb{E}\left[{f({{\bar{\omega}}^{t+1}})}\right]\leq$
$\displaystyle\mathbb{E}\left[{f({{\bar{\omega}}^{t}})}\right]+\mathbb{E}\underbrace{\left[{\left\langle{\nabla
f({{\bar{\omega}}^{t}}),{{\bar{\omega}}^{t+1}}-{{\bar{\omega}}^{t}}}\right\rangle}\right]}_{:\rm{T}_{1}}$
(20)
$\displaystyle+\frac{L}{2}\mathbb{E}\left[{{{\left\|{{{\bar{\omega}}^{t+1}}-{{\bar{\omega}}^{t}}}\right\|}^{2}}}\right]$

Now, let’s look at $\rm{T}_{1}$,

$\displaystyle\rm{T}_{1}$ $\displaystyle=\langle\nabla
f(\bar{\omega}^{t}),\frac{1}{N}\sum_{i=1}^{N}\left(\omega_{i}^{t+1}-\omega_{i}^{t}\right)\rangle$
(21) $\displaystyle=\langle\nabla
f(\bar{\omega}^{t}),\frac{1}{N}\sum_{i=1}^{N}\left(-\lambda\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\rangle$
$\displaystyle=-\lambda\langle\nabla
f(\bar{\omega}^{t}),\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\rangle$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}-\frac{\lambda}{2}\left[\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}+\left\|\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\right\|^{2}\right]$
$\displaystyle+\frac{\lambda}{2}\left[\left\|\nabla
f(\bar{\omega}^{t})-\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\right\|^{2}\right]$

where $(d)$ follows from the fundamental equation
$\langle\mathbf{A},\mathbf{B}\rangle=\frac{1}{2}\left[\left\|\mathbf{A}\right\|^{2}+\left\|\mathbf{B}\right\|^{2}-\left\|\mathbf{A}-\mathbf{B}\right\|^{2}\right]$
for any vector $\mathbf{A},\mathbf{B}$.

Substituting (18) and (21) into (20), we have

$\displaystyle\mathbb{E}\left[f(\bar{\omega}^{t+1})\right]$
$\displaystyle\leq\mathbb{E}\left[f(\bar{\omega}^{t})\right]-\frac{\lambda}{2}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}$ (22)
$\displaystyle-\frac{\lambda}{2}\left\|\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\right\|^{2}$
$\displaystyle+\frac{\lambda}{2}\underbrace{\left[\left\|\nabla
f(\bar{\omega}^{t})-\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\right\|^{2}\right]}_{:\rm{T}_{2}}$
$\displaystyle+\frac{L\lambda^{2}}{2N^{2}}\left\|\sum_{i=1}^{N}\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$

Now let’s bound the $\rm{T}_{2}$,

$\displaystyle\rm{T}_{2}$
$\displaystyle=\left\|\frac{1}{N}\sum_{i=1}^{N}\nabla
f_{i}(\bar{\omega}^{t})-\frac{1}{N}\sum_{i=1}^{N}\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$
(23) $\displaystyle=\frac{1}{N^{2}}\left\|\sum_{i=1}^{N}\left(\nabla
f_{i}(\bar{\omega}^{t})-\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\frac{1}{N}\sum_{i=1}^{N}\left\|\nabla
f_{i}(\bar{\omega}^{t})-\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}\frac{1}{N}\sum_{i=1}^{N}\left(\left\|\nabla
f_{i}(\bar{\omega}^{t})\right\|^{2}+\left\|\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{\leq}}\frac{1}{N}\sum_{i=1}^{N}\left(G^{2}+\frac{\theta^{2}}{\lambda^{2}}\right)$
$\displaystyle=G^{2}+\frac{\theta^{2}}{\lambda^{2}}$

where ($e$) follows by the inequality
$\left\|\sum_{i=1}^{N}\mathbf{z}_{i}\right\|^{2}\leq
N\sum_{i=1}^{N}\left\|\mathbf{z}_{i}\right\|^{2}$, ($f$) follows from the
inequality
$\left\|\mathbf{A}+\mathbf{B}\right\|^{2}\leq\left\|\mathbf{A}\right\|^{2}+\left\|\mathbf{B}\right\|^{2}$
for any vector $\mathbf{A},\mathbf{B}$, and ($g$) follows from Assumption 2
and (19).

Substituting (23) into (22), we have

$\displaystyle\mathbb{E}\left[f(\bar{\omega}^{t+1})\right]$
$\displaystyle\leq\mathbb{E}\left[f(\bar{\omega}^{t})\right]-\frac{\lambda}{2}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}$ (24)
$\displaystyle-\underbrace{\frac{\lambda}{2}\left\|\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right)\right\|^{2}}_{:\rm{T}_{3}}$
$\displaystyle+\frac{\lambda}{2}\left(G^{2}+\frac{\theta^{2}}{\lambda^{2}}\right)$
$\displaystyle+\frac{L\lambda^{2}}{2N^{2}}\left\|\sum_{i=1}^{N}\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}\mathbb{E}\left[f(\bar{\omega}^{t})\right]-\frac{\lambda}{2}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}+\frac{\lambda}{2}\left(G^{2}+\frac{\theta^{2}}{\lambda^{2}}\right)$
$\displaystyle+\frac{L\lambda^{2}}{2N^{2}}\left\|\sum_{i=1}^{N}\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\mathbb{E}\left[f(\bar{\omega}^{t})\right]-\frac{\lambda}{2}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}+\frac{\lambda}{2}\left(G^{2}+\frac{\theta^{2}}{\lambda^{2}}\right)$
$\displaystyle+\frac{L\lambda^{2}}{2N}\sum_{i=1}^{N}\left\|\sum_{t=0}^{t}\Delta\mathcal{g}^{t}\right\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(j)}}{{\leq}}\mathbb{E}\left[f(\bar{\omega}^{t})\right]-\frac{\lambda}{2}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}+\frac{\lambda}{2}\left(G^{2}+\frac{\theta^{2}}{\lambda^{2}}\right)$
$\displaystyle+\frac{L\theta^{2}}{2}$
$\displaystyle=\mathbb{E}\left[f(\bar{\omega}^{t})\right]-\frac{\lambda}{2}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}+\frac{\lambda}{2}\left(G^{2}+\frac{\theta^{2}}{\lambda^{2}}+\frac{L\theta^{2}}{\lambda}\right)$

where $(h)$ follows because $\rm{T}_{3}\geq 0$, $(i)$ and $(j)$ follow from
the inequality $\left\|\sum_{i=1}^{N}\mathbf{z}_{i}\right\|^{2}\leq
N\sum_{i=1}^{N}\left\|\mathbf{z}_{i}\right\|^{2}$ aforementioned and (18),
respectively.

Rearrange the (24), we have

$\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}\leq\frac{2}{\lambda}\mathbb{E}\left[f(\bar{\omega}^{t})-f(\bar{\omega}^{t+1})\right]+G^{2}+\frac{\theta^{2}}{\lambda^{2}}+\frac{L\theta^{2}}{\lambda}$
(25)

For (25), we sum it over $t\in\\{0,1,2,\cdots,T-1\\}$ first and then divide
both sides by $\mathit{T}$,

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\left\|\nabla
f(\bar{\omega}^{t})\right\|^{2}$ $\displaystyle\leq\frac{2}{\lambda
T}\mathbb{E}\left(f(\bar{\omega}^{0})-f(\bar{\omega}^{T})\right)+G^{2}+\frac{\theta^{2}}{\lambda^{2}}+\frac{L\theta^{2}}{\lambda}$
(26) $\displaystyle\leq\frac{2}{\lambda
T}\left(f(\bar{\omega}^{0})-f^{*}\right)+G^{2}+\frac{\theta^{2}}{\lambda^{2}}+\frac{L\theta^{2}}{\lambda}$

where the $f^{*}$ is the optimum of loss function $f$, and this completes the
proof. ∎

## Acknowledgment

This work was partially supported by Key Program of Natural Science Foundation
of China under Grant(61631018), Huawei Technology Innovative Research.

## References

  * [1] X. Wu, X. Zhu, G.-Q. Wu, and W. Ding, “Data mining with big data,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 26, no. 1, pp. 97–107, 2013\.
  * [2] D. Michie, D. J. Spiegelhalter, C. Taylor _et al._ , “Machine learning,” _Neural and Statistical Classification_ , vol. 13, 1994.
  * [3] F. Pedregosa, G. Varoquaux _et al._ , “Scikit-learn: Machine learning in python,” _Journal of machine learning research_ , vol. 12, no. Oct, pp. 2825–2830, 2011.
  * [4] P. Voigt and A. Von dem Bussche, “The eu general data protection regulation (gdpr),” _A Practical Guide, 1st Ed., Cham: Springer International Publishing_ , 2017.
  * [5] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” _arXiv preprint arXiv:1610.05492_ , 2016.
  * [6] “Ieee draft guide for architectural framework and application of federated machine learning,” _IEEE P3652.1/D6, April 2020_ , pp. 1–70, 2020.
  * [7] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 10, no. 2, pp. 1–19, 2019.
  * [8] S. Hakola, T. Chen, J. Lehtomaki, and T. Koskela, “Device-to-device (d2d) communication in cellular network-performance analysis of optimum and practical communication mode selection,” in _2010 IEEE wireless communication and networking conference_. IEEE, 2010, pp. 1–6.
  * [9] Z. Jiang, A. Balu, C. Hegde, and S. Sarkar, “Collaborative deep learning in fixed topology networks,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 5904–5914.
  * [10] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 5330–5340.
  * [11] J. Wang and G. Joshi, “Cooperative sgd: A unified framework for the design and analysis of communication-efficient sgd algorithms,” in _ICML Workshop on Coding Theory for Machine Learning_ , 2019.
  * [12] F. Haddadpour and M. Mahdavi, “On the convergence of local descent methods in federated learning,” _arXiv preprint arXiv:1910.14425_ , 2019.
  * [13] S. Hardy, W. Henecka, H. Ivey-Law, R. Nock, G. Patrini, G. Smith, and B. Thorne, “Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption,” _arXiv preprint arXiv:1711.10677_ , 2017.
  * [14] R. Nock, S. Hardy, W. Henecka, H. Ivey-Law, G. Patrini, G. Smith, and B. Thorne, “Entity resolution and federated learning get a federated resolution,” _arXiv preprint arXiv:1803.04035_ , 2018.
  * [15] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial Intelligence and Statistics_ , 2017, pp. 1273–1282.
  * [16] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith, “Federated optimization in heterogeneous networks,” in _Proceedings of Machine Learning and Systems_ , I. Dhillon, D. Papailiopoulos, and V. Sze, Eds., vol. 2, 2020, pp. 429–450. [Online]. Available: https://proceedings.mlsys.org/paper/2020/file/38af86134b65d0f10fe33d30dd76442e-Paper.pdf
  * [17] A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani, “Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2020, pp. 2021–2031.
  * [18] J. So, B. Güler, and A. S. Avestimehr, “Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning,” _IEEE Journal on Selected Areas in Information Theory_ , vol. 2, no. 1, pp. 479–489, 2021.
  * [19] H. Wang, M. Yurochkin, Y. Sun, D. Papailiopoulos, and Y. Khazaeni, “Federated learning with matched averaging,” in _International Conference on Learning Representations_ , 2020.
  * [20] Z. Chen, D. Li, M. Zhao, S. Zhang, and J. Zhu, “Semi-federated learning,” in _2020 IEEE Wireless Communications and Networking Conference (WCNC)_. IEEE, 2020, pp. 1–6.
  * [21] L. Liu, J. Zhang, S. Song, and K. B. Letaief, “Client-edge-cloud hierarchical federated learning,” in _ICC 2020-2020 IEEE International Conference on Communications (ICC)_. IEEE, 2020, pp. 1–6.
  * [22] O. A. Wahab, A. Mourad, H. Otrok, and T. Taleb, “Federated machine learning: Survey, multi-level classification, desirable criteria and future directions in communication and networking systems,” _IEEE Communications Surveys & Tutorials_, vol. 23, no. 2, pp. 1342–1397, 2021.
  * [23] C. Zhang, Y. Xie, H. Bai, B. Yu, W. Li, and Y. Gao, “A survey on federated learning,” _Knowledge-Based Systems_ , vol. 216, p. 106775, 2021.
  * [24] A. Lalitha, S. Shekhar, T. Javidi, and F. Koushanfar, “Fully decentralized federated learning,” in _Third workshop on Bayesian Deep Learning (NeurIPS)_ , 2018.
  * [25] A. G. Roy, S. Siddiqui, S. Pölsterl, N. Navab, and C. Wachinger, “Braintorrent: A peer-to-peer environment for decentralized federated learning,” _arXiv preprint arXiv:1905.06731_ , 2019.
  * [26] C. Hu, J. Jiang, and Z. Wang, “Decentralized federated learning: A segmented gossip approach,” _arXiv preprint arXiv:1908.07782_ , 2019.
  * [27] J. Jiang, L. Hu, C. Hu, J. Liu, and Z. Wang, “Bacombo—bandwidth-aware decentralized federated learning,” _Electronics_ , vol. 9, no. 3, p. 440, 2020.
  * [28] I. Hegedűs, G. Danner, and M. Jelasity, “Gossip learning as a decentralized alternative to federated learning,” in _IFIP International Conference on Distributed Applications and Interoperable Systems_. Springer, 2019, pp. 74–90.
  * [29] Y. Li, C. Chen, N. Liu, H. Huang, Z. Zheng, and Q. Yan, “A blockchain-based decentralized federated learning framework with committee consensus,” _IEEE Network_ , vol. 35, no. 1, pp. 234–241, 2020.
  * [30] C. Pappas, D. Chatzopoulos, S. Lalis, and M. Vavalis, “Ipls: A framework for decentralized federated learning,” _arXiv preprint arXiv:2101.01901_ , 2021\.
  * [31] C. Li, G. Li, and P. K. Varshney, “Decentralized federated learning via mutual knowledge transfer,” _IEEE Internet of Things Journal_ , 2021.
  * [32] J. N. Tsitsiklis, “Problems in decentralized decision making and computation.” Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, Tech. Rep., 1984.
  * [33] P. Yang, R. A. Freeman, and K. M. Lynch, “Multi-agent coordination by decentralized estimation and control,” _IEEE Transactions on Automatic Control_ , vol. 53, no. 11, pp. 2480–2496, 2008.
  * [34] D. P. Spanos, R. Olfati-Saber, and R. M. Murray, “Dynamic consensus on mobile networks,” in _IFAC world congress_. Citeseer, 2005, pp. 1–6.
  * [35] R. Olfati-Saber and J. S. Shamma, “Consensus filters for sensor networks and distributed sensor fusion,” in _Proceedings of the 44th IEEE Conference on Decision and Control_. IEEE, 2005, pp. 6698–6703.
  * [36] R. Olfati-Saber, “Distributed kalman filter with embedded consensus filters,” in _Proceedings of the 44th IEEE Conference on Decision and Control_. IEEE, 2005, pp. 8179–8184.
  * [37] S. Martinez, “Distributed representation of spatial fields through an adaptive interpolation scheme,” in _2007 American control conference_. IEEE, 2007, pp. 2750–2755.
  * [38] P. Yang, R. A. Freeman, and K. M. Lynch, “Distributed cooperative active sensing using consensus filters,” in _Proceedings 2007 IEEE International Conference on Robotics and Automation_. IEEE, 2007, pp. 405–410.
  * [39] R. A. Freeman, P. Yang, and K. M. Lynch, “Stability and convergence properties of dynamic average consensus estimators,” in _Proceedings of the 45th IEEE Conference on Decision and Control_. IEEE, 2006, pp. 338–343.
  * [40] W. Ren, “Consensus seeking in multi-vehicle systems with a time-varying reference state,” in _2007 American Control Conference_. IEEE, 2007, pp. 717–722.
  * [41] M. Zhu and S. Martínez, “Discrete-time dynamic average consensus,” _Automatica_ , vol. 46, no. 2, pp. 322–329, 2010.
  * [42] X. Glorot and Y. Bengio, “Understanding the difficulty of training deep feedforward neural networks,” in _Proceedings of the thirteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 2010, pp. 249–256.
  * [43] K. He, X. Zhang, S. Ren, and J. Sun, “Delving deep into rectifiers: Surpassing human-level performance on imagenet classification,” in _Proceedings of the IEEE international conference on computer vision_ , 2015, pp. 1026–1034.
  * [44] N. M. M. De Abreu, “Old and new results on algebraic connectivity of graphs,” _Linear algebra and its applications_ , vol. 423, no. 1, pp. 53–73, 2007\.
  * [45] A. I.-A. Chen, “Fast distributed first-order methods,” Ph.D. dissertation, Massachusetts Institute of Technology, 2012.
  * [46] P. A. Knight, “The sinkhorn–knopp algorithm: convergence and applications,” _SIAM Journal on Matrix Analysis and Applications_ , vol. 30, no. 1, pp. 261–275, 2008.
  * [47] R. W. Schafer, “What is a savitzky-golay filter?[lecture notes],” _IEEE Signal processing magazine_ , vol. 28, no. 4, pp. 111–117, 2011.
  * [48] L. Deng, “The mnist database of handwritten digit images for machine learning research [best of the web],” _IEEE Signal Processing Magazine_ , vol. 29, no. 6, pp. 141–142, 2012.
  * [49] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [50] A. Krizhevsky, G. Hinton _et al._ , “Learning multiple layers of features from tiny images,” Citeseer, Tech. Rep., 2009.

|  Zhikun Chen received the B.S. degree in Electronic Information Science and
Technology from the Shandong University (SDU), Shandong, China, in 2018. He is
currently pursuing his Ph.D. degree in the College of Information Science and
Technology, University of Science and Technology of China (USTC), Hefei,
China. His research interests are mainly in artificial intelligence, federated
learning and wireless big data.
---|---
|  Daofeng Li received the B.S. degree in Electronic Engineering and
Information Science from the University of Science and Technology of China
(USTC), Hefei, China, in 2018. He is currently pursuing the M.E. degree in the
College of Information Science and Technology, University of Science and
Technology of China (USTC), Hefei, China. His research interests are mainly in
artificial intelligence and wireless communication.
---|---
|  Jinkang Zhu (M’92-LM’18) received his B.S. degree in Electrical Engineering
from Sichuan University, China, in 1966. He joined University of Science and
Technology of China (USTC) in 1966, and has been a professor of USTC since
1992. He has been committed to research on wireless mobile communications and
networks, signal processing for communications and the future wireless
technologies.
---|---
|  Sihai Zhang (M’09-SM’18) received the Ph.D. degree from the Department of
Computer Science and Technology, University of Science and Technology of China
(USTC), Hefei, China, in 2006. He has been with the PCNSS Laboratory,
Department of Electronic Engineering and Information Science, USTC, since
2009. His research interests include wireless networks, big data analysis and
intelligent algorithms. He is currently an associate professor of Electronic
Engineering with the Department of Electronic Engineering and Information
Science, USTC. He has authored or co-authored over 60 technical papers, such
as the IEEE TETC, the IEEE TVT, MONET, and WPC. He initiated the research
field of wireless big data in 2014. He has participated in projects, including
the National Science Foundation of China for Machine Type Communications, Key
Program of the National Natural Science Foundation of China for Wireless Big
Data. He has served over 15 international conferences as a member of
organizing committee, TPC member or a reviewer, such as publication chair for
WCSP 2014. In 2016, he has co-chaired special sessions on Wireless Big Data in
WCSP 2016, Machine Type Communications in WPMC2016 and guest editor of special
issue on Wireless Big Data for JCIN.
---|---