# DFedADMM: Dual Constraints Controlled Model Inconsistency
for Decentralized Federated Learning

Qinglun Li 1, Li Shen 2, Guanghao Li 1, Quanjun Yin 1*, Dacheng Tao 3
Corresponding authors.

###### Abstract

To address the communication burden issues associated with federated learning
(FL), decentralized federated learning (DFL) discards the central server and
establishes a decentralized communication network, where each client
communicates only with neighboring clients. However, existing DFL methods
still suffer from two major challenges: local inconsistency and local
heterogeneous overfitting, which have not been fundamentally addressed by
existing DFL methods. To tackle these issues, we propose novel DFL algorithms,
DFedADMM and its enhanced version DFedADMM-SAM, to enhance the performance of
DFL. The DFedADMM algorithm employs primal-dual optimization (ADMM) by
utilizing dual variables to control the model inconsistency raised from the
decentralized heterogeneous data distributions. The DFedADMM-SAM algorithm
further improves on DFedADMM by employing a Sharpness-Aware Minimization (SAM)
optimizer, which uses gradient perturbations to generate locally flat models
and searches for models with uniformly low loss values to mitigate local
heterogeneous overfitting. Theoretically, we derive convergence rates of
$\mathcal{O}\Big{(}\frac{1}{\sqrt{KT}}+\frac{1}{KT(1-\psi)^{2}}\Big{)}$ and
$\mathcal{O}\Big{(}\frac{1}{\sqrt{KT}}+\frac{1}{KT(1-\psi)^{2}}+\frac{1}{T^{3/2}K^{1/2}}\Big{)}$
in the non-convex setting for DFedADMM and DFedADMM-SAM, respectively, where
$1-\psi$ represents the spectral gap of the gossip matrix. Empirically,
extensive experiments on MNIST, CIFAR10 and CIFAR100 datesets demonstrate that
our algorithms exhibit superior performance in terms of both generalization
and convergence speed compared to existing state-of-the-art (SOTA) optimizers
in DFL.

##  1 Introduction

Decentralized Federated Learning (DFL) is a novel distributed learning
framework by adopting the principles of data sharing minimization and
decentralized model aggregation without relying on a centralized server
(Beltrán et al. 2022; Sun, Li, and Wang 2022). Specifically, DFL reduces the
communication burden on servers and eliminates the risk of a single point of
failure that can occur in centralized FL due to the absence of a central
server (Gabrielli, Pica, and Tolomei 2023; Beltrán et al. 2022). Furthermore,
in the decentralized communication approach, each client communicates with its
neighbors, which further minimizes the risk of privacy leakage (Wang et al.
2021; Li et al. 2020).

Nonetheless, we acknowledge that the deterioration of DFL performance is
attributed to local inconsistency and the occurrence of local heterogeneous
overfitting. Particularly in conventional local SGD-based DFL approaches, such
as DFedAvg, the incorporation of persistent biases through local updates
results in eventual divergence towards local solution discrepancies. These
locally overfitted and inconsistent solutions can consequently downgrade the
acquired global model parameters to an average of the locally discordant
solutions. Furthermore, the phenomenon of local heterogeneous overfitting can
induce pronounced client drifts, where the client gravitates toward its
distinct local optimum due to heterogeneous data and local updates. This
phenomenon gradually exerts an impact on global convergence, diminishing both
the pace of convergence and the overall generalization capacity of the model
in DFL.

To address the local inconsistency during the training process and avoid
client drift caused by local over-fitting, we propose the DFedADMM algorithm.
Specifically, the DFedADMM algorithm utilizes alternating updates of primal
and dual variables at each client to search for the saddle points of an
augmented Lagrangian function. The quadratic term of the augmented Lagrangian
function acts as a penalty term, ensuring that clients do not deviate too far
from their initial points during each round of communication optimization.
This strengthens the consistency during the training process. In addition, the
dual variables can capture the biases of each client during the local
optimization process and make corrections after client optimization is
completed. This further enhances local consistency. Furthermore, to address
local over-fitting, we introduce gradient perturbation from sharpness-aware
minimization (SAM) (Foret et al. 2020) to generate local flat models, yielding
the enhanced version of DFedADMM, i.e., DFedADMM-SAM. This has two advantages:
Firstly, gradient perturbation effectively prevents local over-fitting.
Secondly, it has been suggested (Zhong et al. 2022) that generating local flat
models at each client may result in a relatively flat landscape of the
aggregated global model, leading to improved generalization capability.

Theoretically, the convergence speed of the proposed algorithm, DFedADMM and
DFedADMM-SAM, in non-convex and smooth environments has been demonstrated to
be $\mathcal{O}\left(\frac{1}{\sqrt{KT}}+\frac{1}{KT(1-\psi)^{2}}\right)$ and
$\mathcal{O}\Big{(}\frac{1}{\sqrt{KT}}+\frac{1}{KT(1-\psi)^{2}}+\frac{1}{T^{3/2}K^{1/2}}\Big{)}$,
respectively. We also show that better connectivity in the communication
topology leads to tighter upper bounds. Empirically, we conduct extensive
experiments on the MNIST, CIFAR10 and CIFAR100 datasets. The results show that
our methods outperform existing baseline methods such as DPSGD, DFedAvg,
DFedAvgM and DFedSAM in terms of both the generalization performance and
convergence speed. In addition, our method achieves comparable or even better
performance compared to some existing centralized methods such as FedAvg and
FedSAM.

In summary, our main contributions are four-fold:

  * •

We propose the DFedADMM algorithm, which enhances consistency during training
by utilizing the dual variable to control the local inconsistency raised from
the local heterogeneous data distribution.

  * •

We propose the DFedADMM-SAM which further unitizes SAM to alleviate the local
overfitting issue by introducing a gradient perturbation based on DFedADMM and
generating flat planes for better aggregation.

  * •

We derive theoretical analysis for DFedADMM and DFedADMM-SAM, which
demonstrate
$\mathcal{O}\Big{(}\frac{1}{\sqrt{KT}}+\frac{1}{KT(1-\psi)^{2}}\Big{)}$ and
$\mathcal{O}\Big{(}\frac{1}{\sqrt{KT}}+\frac{1}{KT(1-\psi)^{2}}+\frac{1}{T^{3/2}K^{1/2}}\Big{)}$
convergence rate of our algorithms in non-convex and decentralized
environments, respectively. Theory suggests that better connectivity in the
communication topology leads to tighter upper bounds.

  * •

We conduct extensive experimental evaluations, which show that our methods
outperform existing SOTA baseline methods in terms of generalization
performance and convergence speed. Moreover, our method achieves comparable or
even better performance compared to some centralized FL methods.

##  2 Related Work

We briefly review three lines of work that are most related to this paper,
i.e., decentralized federated learning (DFL), ADMM, and sharpness-aware
minimization (SAM).

#### Decentralized Federated Learning (DFL).

DFL is the preferred learning paradigm in situations where edge devices lack
trust in the central server’s ability to protect their privacy (Yang et al.
2019; Lalitha et al. 2018, 2019) adopt a Bayesian-like approach to introduce a
belief system over the model parameter space of the clients within a fully DFL
framework. (Sun, Li, and Wang 2022) apply momentum SGD and quantization
methods for multiple local iterations to reduce communication costs, thus
improving the generality of the model and providing convergence results. (Dai
et al. 2022) develop a decentralized sparse training technique to further
reduce communication and computational costs. (Shi et al. 2023c) introduce
gradient perturbations to generate local flat Models and combine them with
Multiple Gossip Steps to enhance the consistency between local clients. More
related work on DFL can be referred to the survey papers (Gabrielli, Pica, and
Tolomei 2023; Yuan et al. 2023; Beltrán et al. 2022) and their references
therein.

#### ADMM Algorithms.

Alternating Direction Method of Multipliers (ADMM) is a popular primal-dual
algorithm that has achieved significant success in distributed optimization
(Bertsekas 2014; Gabay and Mercier 1976; Boyd et al. 2011). In the field of
centralized FL, FedPD (Zhang et al. 2021) is the first to apply the primal-
dual algorithm to the FL domain. It decomposes the problem into a series of
local subproblems alternately updating the primal and dual variables. Under
the assumption of local accuracy, it achieves a convergence rate of
$\mathcal{O}(1/T)$. In addition, (Acar et al. 2021) propose a similar method
called FedDyn algorithm (Zhang and Hong 2021), which employs dual variables to
enhance both convergence speed and generalization performance. Recently,
several ADMM-based FL methods (Tran Dinh et al. 2021; Wang, Marella, and
Anderson 2022; Gong, Li, and Freris 2022; Sun et al. 2023; Zhou and Li 2023;
Wang et al. 2023) have been proposed and achieved a new SOTA performance for
centralized FL.

#### Sharpness-Aware Minimization (SAM).

SAM (Foret et al. 2020) is a powerful optimizer utilized for training deep
learning models. It leverages the flat geometry of the loss landscape to
enhance the generalization ability of the model. SAM and its variants have
been successfully applied to a wide range of machine learning tasks (Zhong et
al. 2022; Zhao, Zhang, and Hu 2022; Kwon et al. 2021; Du et al. 2021) as
effective optimizers. Recently, (Shi et al. 2023c) applied SAM to the field of
decentralized federated learning (DFL) and achieved state-of-the-art (SOTA)
performance. Similarly, (Sun et al. 2023; Qu et al. 2022) utilized SAM in the
context of centralized federated learning (CFL) and also achieved SOTA
performance. Additionally, (Shi et al. 2023a) utilized SAM in the context of
personalized federated learning (PFL) and achieved SOTA performance.

The most relevant work to ours is the DFedSAM (Shi et al. 2023c). It utilizes
SAM to generate locally flat landscapes, enabling the generation of
potentially flat models during communication with neighboring nodes. This
approach alleviates the issue of local heterogeneous overfitting, while it
controls the local inconsistency via the multiple gossip steps with heavy
communication costs. In this work, we extend the SAM optimizer and ADMM
algorithm to the DFL setting to further solve the local inconsistency issue
with lightweight communication cost.

##  3 Methodology

In this part, we introduce the preliminaries and the proposed FedADMM and
FedADMM-SAM algorithms in detail.

###  3.1 Problem Setup

Let $m$ be the total number of clients. $T$ represents the number of
communication rounds. $(\cdot)_{i,k}^{t}$ indicates variable $(\cdot)$ at the
$k$-th iteration of the $t$-th round in the $i$-th client. $\mathbf{x}$
denotes the model parameters. $\mathbf{g}$ represents the stochastic gradient.
$\hat{\mathbf{g}}$ is the dual variable. The inner product of two vectors is
denoted by $\langle\cdot,\cdot\rangle$, and $\|\cdot\|$ represents the
Euclidean norm of a vector. As shown in Figure 1, in the decentralized network
topology, the communication network between clients is represented by an
undirected connected graph $\mathcal{G}=(\mathcal{N},\mathcal{V},{\bf W})$,
where $\mathcal{N}=\\{1,2,\ldots,m\\}$ denotes the set of clients, and
$\mathcal{V}\subseteq\mathcal{N}\times\mathcal{N}$ represents the set of
communication channels connecting pairs of distinct clients. In the
decentralized setting, there is no central server, and all clients communicate
solely with their neighboring clients via the communication channels specified
by $\mathcal{V}$.

In this work, we focus on the following DFL, formulated as a finite sum of
non-convex stochastic optimization:

$\min_{{\bf x}\in\mathbb{R}^{d}}f({\bf
x}):=\frac{1}{m}\sum_{i=1}^{m}f_{i}({\bf x}),~{}~{}f_{i}({\bf
x})=\mathbb{E}_{\xi\sim\mathcal{D}_{i}}F_{i}({\bf x};\xi),$ (1)

where $\mathcal{D}_{i}$ represents the data distribution in the $i$-th client
in $\mathcal{N}$, which exhibits heterogeneity across clients. Each client’s
local objective function $F_{i}({\bf x};\xi)$ is associated with the training
data samples $\xi$. Additionally, we denote $f^{*}$ as the minimum value of
$f$, where $f(x)\geq f(x^{*})=f^{*}$ for all $x\in\mathbb{R}^{d}$.

(a) Ring

(b) Exponential

(c) Grid

(d) Fully-connected

(e) Random

Figure 1: Five common decentralized communication topologies

###  3.2 DFedADMM Algorithm

In this section, we extend the ADMM algorithm to the DFL setting. To
facilitate the derivation of the DFedADMM algorithm, we first briefly review
the FedPD (Zhang et al. 2021) algorithm, which is a ADMM-based centralized FL
algorithm. For more detailed derivation and additional information, please
refer to paper (Zhang et al. 2021).

#### Prelimary on FedPD.

Firstly, the centralized optimizer of FL is based on the following global
consensus formulation:

$\min\limits_{\mathbf{x}_{0},\mathbf{x}_{i}}\frac{1}{m}\sum\limits_{i=1}^{m}f_{i}(\mathbf{x}_{i}),\quad\text{s.t.}\mathbf{x}_{i}=\mathbf{x}_{0},\forall
i\in[m].$ (2)

The augmented Lagrangian (AL) function of (2) as:

$\displaystyle\mathcal{L}(\mathbf{x}_{0:m},\hat{\mathbf{g}})\triangleq\left.\frac{1}{m}\sum_{i=1}^{m}\mathcal{L}_{i}(\mathbf{x}_{0},\mathbf{x}_{i},\hat{\mathbf{g}}_{i})\right.$
$\displaystyle\mathcal{L}_{i}(\mathbf{x}_{i},\mathbf{x}_{0},\hat{\mathbf{g}}_{i})\triangleq\left.f_{i}(\mathbf{x}_{i})-\langle\hat{\mathbf{g}}_{i},\mathbf{x}_{i}-\mathbf{x}_{0}\rangle+\frac{1}{2\lambda}\left\|\mathbf{x}_{i}-\mathbf{x}_{0}\right\|^{2}.\right.$

The main idea of the FedPD algorithm is to solve the optimization problem of
the local AL $\mathcal{L}_{i}$ function using ADMM. The updates for the primal
and dual variables of each client in FedPD are as follows:

$\displaystyle\\!\\!\mathbf{x}_{i}^{t+1}\\!=\\!\arg\min_{\mathbf{x}}f_{i}(\mathbf{x})-$
$\displaystyle\left\langle\hat{\mathbf{g}}_{i}^{t},\mathbf{x}-\mathbf{x}_{0}^{t}\right\rangle+\frac{1}{2\lambda}\left\|\mathbf{x}-\mathbf{x}_{0}^{t}\right\|^{2}\\!\\!$
(3) $\displaystyle\hat{\mathbf{g}}_{i}^{t+1}=\hat{\mathbf{g}}_{i}^{t}-$
$\displaystyle\frac{1}{\lambda}(\mathbf{x}_{i}^{t+1}-\mathbf{x}_{0}^{t})$ (4)

In the case where all clients are fully participating, the updates for the
server in the FedPD algorithm are as follows:

$\displaystyle\mathbf{x}_{0}^{t+1}=\dfrac{1}{m}\sum_{i=1}^{m}(\mathbf{x}_{i}^{t+1}-\lambda\hat{\mathbf{g}}_{i}^{t+1})$
(5)

Equation (5) indicates that the server is responsible for communication,
receiving the model parameters from participating client devices, and
performing the aggregation. This can lead to a communication burden, and if
the server crashes, the entire system’s updates will be interrupted. Below, we
try to reallocate communication to each client in a peer-to-peer manner by
discarding the central sever to address these issues.

#### Derive the DFedADMM.

To mitigate the risks of single point of failure and communication burden
associated with centralization, we make three modifications to the above
update scheme to accommodate a decentralized topology :

  * •

Change in solving method for each client: For each client, the precise
solution of Equation (3) is computationally expensive. To better align with
practical scenarios, we can modify Equation (3) to perform $K$ rounds of local
stochastic gradient descent, as described in line 13 of Algorithm 1. The
specific update formula for $\mathbf{x}_{i,k}^{t}$ is as follows:

$\mathbf{x}_{i,k+1}^{t}=\mathbf{x}_{i,k}^{t}-\eta_{l}\left(\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1}+\frac{1}{\lambda}\left(\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\right)\right)$
(6)

where $\mathbf{g}_{i,k}^{t}$ is the random gradient,
$\hat{\mathbf{g}}_{i}^{t-1}$ is the dual variable, $\lambda$ is the penalty
parameter, and $\mathbf{x}_{i}^{t}$ is the model parameter of the $i$-th
client after communication with neighbors in the $t$-th round. After
performing $K$ local updates, we obtain the following equation:

$\mathbf{x}_{i,K}^{t}-\mathbf{x}_{i}^{t}=-\lambda\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}+\gamma\lambda\hat{\mathbf{g}}_{i}^{t-1}$
(7)

where
$\sum_{k=0}^{K-1}\gamma_{k}=\sum_{k=0}^{K-1}{\eta_{l}}/{\lambda}\bigl{(}1-{\eta_{l}}/{\lambda}\bigr{)}^{K-1-k}=\gamma=1-(1-{\eta_{l}}/{\lambda})^{K}$.
Due to the space limitation, proof details of above equation is placed in the
Appendix.

  * •

Change in initial values for each client: Without the coordination and
communication from a central server to transmit initial model values, the
initial values for each client’s updates, denoted as $\mathbf{x}_{0}^{t}$,
need to be modified to be specific to each client, denoted as
$\mathbf{x}_{i}^{t}$. The parameter $\mathbf{x}_{i}^{t}$ will be stored
locally on client $i$.

  * •

Change in communication scheme: In the absence of server aggregation, the
previous server communication followed by aggregation is replaced with
individual peer-to-peer communication via the communication topology matrix
$\bf W$. After communication with their respective neighbors, each client
performs a local aggregation operation. The specific communication expression
is as follows:

$\mathbf{x}_{i}^{t+1}=\sum_{l\in\mathcal{N}\left(i\right)}w_{il}\mathbf{z}^{t}_{i}$
(8)

where $\mathbf{x}_{i}^{t+1}$ represents the updated model parameter of the
$i$-th client after communication with its neighbors,
$\mathcal{N}\left(i\right)$ represents the set of neighbors of the $i$-th
client, $w_{il}$ represents the weight or communication coefficient between
the $i$-th client and its neighbor $l$, and the update method for
$\mathbf{z}^{t}_{i}$ can be found in line 17 of Algorithm 1.

The complete algorithm is summarized in Algorithm 1.

Algorithm 1 DFedADMM and DFedADMM-SAM

0: model parameters $\mathbf{x}_{i}^{0}$, total communication rounds $T$,
local gradient controller $\hat{\mathbf{g}}_{i}^{-1}=0$, penalized weight
$\lambda$.

0: model average parameters $\bar{\mathbf{x}}^{t}$.

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

2: for client $i$ in parallel do

3: set $\mathbf{x}_{i,0}^{t}=\mathbf{x}_{i}^{t}$

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

5: sample minibatch $\varepsilon_{i,k}^{t}$ and compute unbiased stochastic
gradient: $\mathbf{g}_{i,k}^{t}=\nabla
f_{i}(\mathbf{x}_{i,k}^{t};\varepsilon_{i,k}^{t})$

6: if DFedADMM then

7: update gradient descent step:
$\mathbf{x}_{i,k+1}^{t}\leftarrow\mathbf{x}_{i,k}^{t}-\eta_{l}\bigl{(}\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1}+\frac{1}{\lambda}(\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t})\bigr{)}$

8: end if

9: if DFedADMM-SAM then

10: compute unbiased stochastic gradient: $\mathbf{g}_{i,k,1}^{t}=\nabla
f_{i}(\mathbf{x}_{i,k}^{t};\varepsilon_{i,k}^{t})$

11: update extra step:
$\breve{\mathbf{x}}_{i,k}^{t}=\mathbf{x}_{i,k}^{t}+\rho\frac{\mathbf{g}_{i,k,1}^{t}}{\|\mathbf{g}_{i,k,1}\|}$

12: compute unbiased stochastic gradient: $\mathbf{g}_{i,k}^{t}=\nabla
f_{i}(\breve{\mathbf{x}}_{i,k}^{t};\varepsilon_{i,k}^{t})$

13: update gradient descent step:
$\mathbf{x}_{i,k+1}^{t}\leftarrow\mathbf{x}_{i,k}^{t}-\eta_{l}\bigl{(}\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1}+\frac{1}{\lambda}(\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t})\bigr{)}$

14: end if

15: end for

16:
$\hat{\mathbf{g}}_{i}^{t}=\hat{\mathbf{g}}_{i}^{t-1}-\frac{1}{\lambda}(\mathbf{x}_{i,K}^{t}-\mathbf{x}_{i}^{t})$

17:
$\mathbf{z}_{i}^{t}=\mathbf{x}_{i,K}^{t}-\lambda\hat{\mathbf{g}}_{i}^{t-1}$

18: Receive neighbors’ models $\mathbf{z}_{l}^{t}$ with adjacency matrix ${\bf
W}$

19:
$\mathbf{x}_{i}^{t+1}=\sum_{l\in\mathcal{N}\left(i\right)}w_{il}\mathbf{z}^{t}_{i}$

20: end for

21: end for

###  3.3 DFedADMM-SAM Algorithm

Based on the SAM optimizer, we propose the DFedADMM-SAM algorithm, which
builds upon the DFedADMM to further alleviate the issue of local overfitting.
DFedADMM-SAM algorithm can be described as follows. Each client maintains a
local model $\mathbf{x}$ in its local memory and repeats the following steps
(taking client $i$ as an example):

  * •

Client $i$ samples a minibatch $\varepsilon_{i,k}^{t}$ from the data
distribution $\mathcal{D}_{i}$ and computes the unbiased stochastic gradient:
$\mathbf{g}_{i,k,1}^{t}=\nabla
f_{i}(\mathbf{x}_{i,k}^{t};\varepsilon_{i,k}^{t})$.

  * •

Client $i$ performs a gradient ascent step at $\mathbf{x}_{i,k}^{t}$:
$\breve{\mathbf{x}}_{i,k}^{t}=\mathbf{x}_{i,k}^{t}+\rho\frac{\mathbf{g}_{i,k,1}^{t}}{\|\mathbf{g}_{i,k,1}\|}$,
where $\rho$ is the step size.

  * •

Client $i$ uses minibatch $\varepsilon_{i,k}^{t}$ at
$\breve{\mathbf{x}}_{i,k}^{t}$ to compute the unbiased gradient
$\mathbf{g}_{i,k}^{t}$.

The updates for $\hat{\mathbf{g}}_{i}^{t}$, $\mathbf{z}_{i}^{t}$, and
$\mathbf{x}_{i}^{t+1}$ in the subsequent steps are the same as DFedADMM
algorithm. The complete algorithm scheme can be found in Algorithm 1.

##  4 Convergence Analysis

In this section, we present the theoretical analysis for FedADMM and FedADMM-
SAM algorithms. Due to space constraints, detailed proofs are placed in the
Appendix. Below, we provide some standard definitions and assumptions.

###### Definition 1

(Gossip/Mixing matrix). [Definition 1, (Sun, Li, and Wang 2022)] The gossip
matrix ${\bf W}=[w_{i,j}]\in[0,1]^{m\times m}$ is assumed to have the
following properties: (i) (Graph) If $i\neq j$ and $(i,j)\notin{\cal V}$, then
$w_{i,j}=0$, otherwise, $w_{i,j}>0$; (ii) (Symmetry) ${\bf W}={\bf W}^{\top}$;
(iii) (Null space property) $\mathrm{null}\\{{\bf I}-{\bf
W}\\}=\mathrm{span}\\{\bf 1\\}$; (iv) (Spectral property) ${\bf I}\succeq{\bf
W}\succ-{\bf I}$. Under these properties, the eigenvalues of $\bf{\bf W}$
satisfy $1=|\psi_{1}({\bf W)})|>|\psi_{2}({\bf
W)})|\geq\dots\geq|\psi_{m}({\bf W)})|$. Furthermore, we define
$\psi:=\max\\{|\psi_{2}({\bf W)}|,|\psi_{m}({\bf W)})|\\}$ and
$1-\psi\in(0,1]$ as the spectral gap of $\bf W$.

###### Assumption 1

(L-Smoothness) The non-convex function $f_{i}$ satisfies the smoothness
property for all $i\in[m]$, i.e., $\|\nabla f_{i}(\mathbf{x})-\nabla
f_{i}(\mathbf{y})\|\leq L\|\mathbf{x}-\mathbf{y}\|$, for all
$\mathbf{x},\mathbf{y}\in\mathbb{R}^{d}$.

###### Assumption 2

(Bounded Stochastic Gradient) The stochastic gradient
$\mathbf{g}_{i,k}^{t}=\nabla
f_{i}(\mathbf{x}_{i,k}^{t},\varepsilon_{i,k}^{t})$ with the randomly sampled
data $\varepsilon_{i,k}^{t}$ on the local client $i$ is unbiased and with
bounded variance, i.e., $\mathbb{E}[\mathbf{g}_{i,k}^{t}]=\nabla
f_{i}(\mathbf{x}_{i,k}^{t})$ and $\mathbb{E}\|\mathbf{g}_{i,k}^{t}-\nabla
f_{i}(\mathbf{x}_{i,k}^{t})\|^{2}\leq\sigma_{l}^{2}$, for all
$\mathbf{x}_{i,k}^{t}\in\mathbb{R}^{d}$.

###### Assumption 3

(Bounded Heterogeneity) The dissimilarity of the dataset among the local
clients is bounded by the local and global gradients, i.e.,
$\mathbb{E}\|\nabla f_{i}(\mathbf{x})-\nabla
f(\mathbf{x})\|^{2}\leq\sigma_{g}^{2}$, for all $\mathbf{x}\in\mathbb{R}^{d}$.
This paper also assumes global variance is bounded, i.e.,
$\frac{1}{m}\sum_{i=1}^{m}\|\nabla f_{i}({\bf x})-\nabla f({\bf
x})\|^{2}\leq\sigma_{g}^{2}$.

###### Assumption 4

(Bounded gradient) we have $\|\nabla f_{i}(\mathbf{x})\|\leq B.$ for any
$i\in\\{1,2,\cdots,m\\}$.

Note that the above-mentioned assumptions are mild and commonly used in
characterizing the convergence rate of DFL (Sun, Li, and Wang 2022; Shi et al.
2023b).

Compared with decentralized parallel SGD methods such as D-PSGD (Lian et al.
2017), the technical difficulty stems from the realization that
$\mathbf{x}_{i}^{t,K}-\mathbf{x}_{i}^{t}$ cannot be regarded as an unbiased
estimate of the gradient $\nabla f_{i}(\mathbf{x}_{i}^{t})$ following numerous
local iterations (Sun, Li, and Wang 2022; Shi et al. 2023c). Moreover, in our
algorithm (Algorithm 1, line 13), the introduction of dual variables adds
additional challenges to the analysis of
$\mathbf{x}_{i}^{t,K}-\mathbf{x}_{i}^{t}$. To overcome this problem, we define
two auxiliary sequences:
$\overline{\mathbf{x}^{t}}=\frac{1}{m}\sum_{i\in[m]}\mathbf{x}_{i}^{t}$ and
$\mathbf{w}^{t}=\overline{\mathbf{x}^{t}}+\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})$.
By doing so, we construct a mapping from $\mathbf{x}^{t}$ to $\mathbf{w}^{t}$,
and the entire update process is simplified to an SGD-type method with
gradients $\mathbf{g}$. The detailed proof can be found in the Appendix.

###### Theorem 1

Under the Assumptions 1-4, when the local learning rate $\eta_{l}$ satisfies
$\eta_{l}\leq\min\\{\frac{1}{96KL},2\lambda\\}$, and the local interval $K$
satisfies $K\geq\lambda/\eta_{l}$, let
$\kappa=\frac{1}{2}-1152L^{2}\eta_{l}^{2}K^{2}$ be a positive constant
selected with the proper values of $\eta_{l}$ and $\rho$, then the auxiliary
sequence $\mathbf{w}^{t}$, generated by executing Algorithm 1 of DFedADMM-SAM,
satisfies:

$\begin{split}&\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{t}\|\nabla
f(\mathbf{w}^{t})\|^{2}\\\ &\leq\frac{f(\mathbf{w}^{0})-f^{*}}{\lambda\kappa
T}+\frac{96L^{2}\eta_{l}^{2}K^{2}}{\kappa}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})\\\
&+\frac{3\lambda^{2}L^{2}(1+384L^{2}\eta_{l}^{2}K^{2})}{\kappa}(\sigma_{l}^{2}+B^{2})+\frac{L\lambda}{2\kappa}\left(\sigma_{l}^{2}+B^{2}\right)\\\
&+\frac{96\eta_{l}^{2}K^{2}L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)}{\kappa(1-\psi)^{2}}\\\
&+\frac{6\lambda^{2}L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\left(\sigma_{l}^{2}+B^{2}\right)}{\kappa(1-\psi)^{2}}+\frac{6\rho^{2}\lambda
L^{2}}{\kappa}(\sigma_{l}^{2}+B^{2})\\\ \end{split}$

where $f$ is a non-convex objective function $f^{*}$ is the optimal of $f$, T
is the number of communication rounds. More specifically, by setting $\rho=0$,
we obtain the convergence theorem for Algorithm 1 of DFedADMM.

More detailed proof can be found in the Appendix. With Theorem 1, we can state
the following convergence rates for DFedADMM and DFedADMM-SAM algorithms:

###### Corollary 1

Let the local adaptive learning rate satisfy
$\eta_{l}=\mathcal{O}(\frac{1}{LK\sqrt{T}})$ , the penalty parameter satisfy
$\lambda=\mathcal{O}(\frac{1}{L\sqrt{KT}})$, and the perturbation parameter
$\rho=\mathcal{O}(\frac{1}{\sqrt{T}})$. Then, the convergence rate for
DFedADMM-SAM satisfies:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{t}\|\nabla
f(\mathbf{w}^{t})\|^{2}=\mathcal{O}\Big{(}\frac{(f({\bf
w}^{0})-f^{*})+K^{-1/2}(B^{2}+\sigma_{l}^{2})}{\sqrt{T}}$
$\displaystyle+\frac{\left(B^{2}+\sigma_{l}^{2}+\sigma_{g}^{2}\right)}{T(1-\psi)^{2}}+\frac{L(B^{2}+\sigma_{l}^{2})}{T^{3/2}K^{1/2}}+\frac{(B^{2}+\sigma_{l}^{2})}{TK(1-\psi)^{2}}\Big{)}.$

More specifically, by setting $\rho=0$, we obtain the convergence rate for
DFedADMM:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{t}\|\nabla
f(\mathbf{w}^{t})\|^{2}=\mathcal{O}\Big{(}\frac{(f({\bf
w}^{0})-f^{*})+K^{-1/2}(B^{2}+\sigma_{l}^{2})}{\sqrt{T}}$
$\displaystyle+\frac{\left(B^{2}+\sigma_{l}^{2}+\sigma_{g}^{2}\right)}{T(1-\psi)^{2}}+\frac{(B^{2}+\sigma_{l}^{2})}{TK(1-\psi)^{2}}\Big{)}.$

###### Remark 1

From Corollary 1, we observe that the convergence speed of the DFedADMM and
DFedADMM-SAM algorithms improves with an increase in the number of local
iterations, K. This finding is consistent with the results obtained by (Sun,
Li, and Wang 2022). When K is large enough, For DFedADMM, the term
$\mathcal{O}\left(\frac{1}{\sqrt{T}}+\frac{B^{2}+\sigma_{l}^{2}+\sigma_{g}^{2}}{T(1-\psi)^{2}}\right)$
will dominate the convergence bound. Similarly, for DFedADMM-SAM, the term
$\mathcal{O}\Big{(}\frac{1}{\sqrt{T}}+\frac{B^{2}+\sigma_{l}^{2}+\sigma_{g}^{2}}{T(1-\psi)^{2}}+\frac{1}{T^{3/2}}\Big{)}$
will dominate the convergence bound. To achieve an error of $\epsilon>0$, Both
require $\mathcal{O}\left(\frac{1}{\epsilon^{2}}\right)$ communication rounds,
which is the same as SGD and DSGD. When $\psi$ is smaller, the convergence
bounds of both algorithms will be tighter. This means that when the
communication topology is better connected, tighter convergence bounds can be
achieved.

In summary, both the DFedADMM algorithm and the DFedADMM-SAM algorithm achieve
a convergence rate of $1/\sqrt{T}$. The difference between them lies in the
additional term $\frac{L(B^{2}+\sigma_{l}^{2})}{T^{3/2}K^{1/2}}$, which arises
from the additional SGD step for smoothness using the SAM local optimizer.
This term can be considered negligible compared to the other terms.

##  5 Experiments

In this section, we evaluate the efficacy of our algorithms compared to six
baselines from CFL and DFL settings. In addition, we conduct several
experiments to verify the impact of the communication network topology.

###  5.1 Experiment Setup

#### Dataset and Data Partition.

The effectiveness of the proposed DFedADMM and DFedADMM-SAM methods is
evaluated on the MNIST, CIFAR-10, and CIFAR-100 datasets (Krizhevsky, Hinton
et al. 2009) in both IID and non-IID settings. To simulate non-IID data
distribution among federated clients, the Dirichlet Partition (Hsu, Qi, and
Brown 2019) approach is utilized. This approach partitions the local data of
each client by sampling label ratios from the Dirichlet distribution
Dir($\alpha$), where parameters $\alpha=0.3$ and $\alpha=0.6$ are used for
this purpose.

#### Baselines.

The baselines used for comparison include several state-of-the-art (SOTA)
methods in both the CFL and DFL settings. In the centralized setting, the
baselines consist of FedAvg (McMahan et al. 2017) and FedSAM (Qu et al. 2022).
For the decentralized setting, the baselines include D-PSGD (Lian et al.
2017), DFedAvg, DFedAvgM (Sun, Li, and Wang 2022), and DFedSAM (Shi et al.
2023c). These baselines are selected to provide comprehensive comparisons
across different settings and methodologies.

#### Implementation Details.

The total number of clients is set to 100, with 10% of the clients
participating in the communication. For decentralized methods, all clients
perform the local iteration step, while for centralized methods, only the
participating clients perform the local update. The local learning rate is
initialized to 0.1 with a decay rate of 0.998 per communication round for all
experiments. For SAM-based algorithms, such as DFedSAM and DFedADMM-SAM, we
set the gradient perturbation weight $\rho=0.1$. For the CIFAR-100 dataset, we
adopt ResNet-18 (Simonyan and Zisserman 2014) as the backbone architecture for
each client. Please refer to the Appendix for the specific backbone
architectures used for MNIST and CIFAR-10. The number of communication rounds
is set to 500 for all experiments comparing baselines on CIFAR-10/100, and 300
rounds for MNIST. For investigating the topology-aware performance, we employ
a data partitioning scheme on the MNIST dataset using Dirichlet $\alpha=0.3$.
Additionally, all ablation studies are conducted on the CIFAR-10 dataset with
300 communication rounds.

#### Communication Configurations.

To ensure a fair comparison between decentralized and centralized approaches,
we have implemented a dynamic and time-varying connection topology for the
decentralized methods. This guarantees that the number of connections in each
round does not exceed that of the central server. By controlling the number of
client-to-client communications, we can match the communication volume of the
centralized methods. It is worth noting that, based on previous research, the
communication complexity is measured in terms of the frequency of local
communications. For detailed experimental information, please refer to
Appendix due to space constraints.

###  5.2 Performance Evaluation

#### Comparative performance analysis with baseline methods.

We assess the performance of DFedADMM and DFedADMM-SAM with $\rho=0.1$ on
MNIST and CIFAR-10/100 datasets. We compare these methods with all baselines
from CFL and DFL in both experimental settings. From the results in Figure 5
(found in the Appendix) and Table 1, it is evident that our proposed
algorithm, DFedADMM-SAM, achieves superior accuracy and convergence speed on
the test sets compared to all baseline methods on the CIFAR-10/100 datasets.
It achieves state-of-the-art (SOTA) performance. Even in the MNIST IID
setting, our algorithm performs comparably to the CFL method. In terms of
convergence speed, our proposed algorithm achieves convergence in fewer
communication rounds. Specifically, the speed of the DFedAvgM method is
comparable to our proposed algorithm in the early stages, but its accuracy is
lower than our algorithm in the middle and later stages. Specifically, it
reaches convergence in approximately $2/5$ of the specified communication
rounds, and during this period, our algorithm demonstrates a noticeable
performance gap compared to other baseline methods. This demonstrates the fast
convergence speed of our algorithm (For further detailed discussion on the
convergence speed, please refer to the Appendix), which also verifies that the
introduced dual variable can control the model inconsistency well for DFL.

#### Impact of non-IID levels.

Our algorithm demonstrates certain robustness to heterogeneous data. In Table
1, we can observe that our algorithm exhibits robustness to different data
partition scenarios, including IID, Dirichlet 0.6, and Dirichlet 0.3. The
presence of heterogeneous data makes training the global/consensus model more
challenging. However, our algorithm achieves the highest accuracy across all
data partition scenarios. Moreover, as the data heterogeneity increases (with
$\alpha$ decreasing from 1 to 0.3, where 1 represents the IID scenario), our
algorithm maintains minimal accuracy loss compared to baseline methods. For
example, On the CIFAR-10 dataset, the difference in accuracy obtained by our
algorithm between IID and Dirichlet 0.3 is 1.92%, outperforming FedAvg
(3.05%), FedSAM (2.99%), DFedSAM (2.41%), and DFedAvgM (3.04%). This result
highlights the effectiveness of our algorithm in mitigating the impact of
heterogeneous data on the global/consensus model through the introduction of
dual constraints control.

Algorithm | MNIST  | CIFAR-10  | CIFAR-100
---|---|---|---
Dir 0.3 | Dirt 0.6 | IID  | Dir 0.3 | Dir 0.6 | IID  | Dirt 0.3 | Dir 0.6 | IID
FedAvg | 97.33 | 98.10 | 98.29  | 78.64 | 79.71 | 81.69  | 55.11 | 56.01 | 57.40
FedSAM | 98.32 | 98.36 |  98.52 | 80.56 | 81.55 | 83.55  | 56.52 | 57.39 | 57.79
D-PSGD | 97.26 | 97.49 | 97.67  | 73.02 | 74.68 | 78.06  | 56.17 | 56.61 | 57.39
DFedAvg | 97.78 | 97.74 | 98.07  | 77.56 | 78.59 | 79.42  | 59.11 | 59.46 | 60.22
DFedAvgM | 98.16 | 98.21 | 98.25  | 79.91 | 80.77 | 82.95  | 54.72 | 55.93 | 56.24
DFedSAM | 98.34 | 98.21 | 98.31  | 80.10 | 80.82 | 82.44  | 59.19 | 60.03 | 60.84
DFedADMM | 98.07 | 98.07 | 98.09  | 80.50 | 80.29 | 80.05  | 58.83 | 58.89 | 60.80
DFedADMM-SAM | 98.44 | 98.47 |  98.44 | 82.00 | 82.36 |  83.92 | 59.37 | 60.44 | 61.68
Table 1: Top 1 test accuracy (%) on two datasets in both IID and non-IID
settings.

###  5.3 Topology-aware Performance

Algorithm | Ring | Grid | Exp | Full
---|---|---|---|---
D-PSGD | 93.31 | 94.17 | 93.48 | 95.02
DFedAvg | 95.86 | 97.49 | 97.57 | 98.00
DFedAvgM | 95.62 | 97.76 | 98.07 | 98.17
DFedSAM | 96.86 | 97.98 | 98.01 | 98.13
DFedADMM | 96.41 | 97.94 | 97.99 | 98.26
DFedADMM-SAM | 97.08 | 98.27 | 98.29 | 98.50

Table 2: Top 1 test accuracy (%) in various network topologies compared with
decentralized algorithms on MNIST.

In this section, we examine the effects of different DFL communication
topologies on various DFL methods using the MNIST dataset. Unlike in Section
5.2, the communication topology in this section is deterministic rather than
random. Each client in the network only communicates with its predetermined
neighbors, and the specific communication pattern is determined by the
corresponding topology as illustrated in Figure 1. In DFL, the degree of
sparse connectivity $\psi$ follows the order: Ring $>$ Grid $>$ Exponential
(Exp) $>$ Full-connected (Full) (Shi et al. 2023c; Zhu et al. 2022).

From Figure 4 and Table 2, it can be observed that as the sparse connectivity
$\psi$ decreases, the accuracy of our proposed algorithm on the test set
increases. This is attributed to the fact that a well-designed communication
topology allows clients to obtain better optimization starting points through
communication, resulting in improved results. Furthermore, our algorithm
consistently achieves higher test set accuracy compared to other DFL baselines
across different communication topologies. This result showcases the
effectiveness of our introduced dual constraints control in mitigating model
inconsistency.

Figure 2: Topology-aware performance of DFL methods.

###  5.4  Ablation Study

We conduct experiments to evaluate the impact of each component and hyper-
parameter in DFedADMM-SAM, where $\rho$ was set to 0.1, except for the study
of $\rho$ itself. All experiments are conducted with the ”Random” topology,
where each client communicates with only 10 randomly selected neighbors among
100 total clients in each round. The performance analysis on different
topologies has been addressed in the Topology-aware Performance section.

Figure 3:  Sensitivity of hyper-parameters: local iteration K, penalty
parameter $\lambda$, number of participated clients m, perturbation radius
$\rho$, respectively.

#### Number of participated clients $m$.

In Figure 3 (c), we compare the performance across different numbers of client
participation ($m=\\{50,100,150\\}$) while keeping the hyper-parameters
consistent. The experimental results demonstrate the robustness of our
algorithm with respect to the number of clients $m$. We observe that the
convergence speed and generalization performance of the algorithm show no
significant difference despite varying values of $m$. This is a crucial factor
to consider when deploying the algorithm in practical scenarios, as in real-
world federated learning settings, $m$ is often very large.

#### Local iteration steps $K$.

The previous work (Sun, Li, and Wang 2022; Shi et al. 2023c) with theoretical
guarantees has already indicated that larger values of $K$ can accelerate
convergence. In order to explore the acceleration effect of larger local
iteration steps $K$, we kept other hyper-parameters fixed and varied $K$
within the set $\\{1,2,5,10\\}$. The results indicate that a larger value of
$K=10$ exhibits faster convergence compared to $\\{1,2,5\\}$. This aligns with
the results obtained in the convergence analysis section, which demonstrates
that larger values of $K$ can tighten the upper bound.

#### Perturbation radius $\rho$.

The perturbation radius $\rho$ also influences the performance as the
accumulated perturbation increases with each communication round $T$.
Generally, the choice of $\rho$ should not be too large, as it may obscure the
true direction of gradients, leading to slow convergence or even divergence
(Andriushchenko and Flammarion 2022; Zhu et al. 2023). To determine an
appropriate value for DFedADMM-SAM, we conduct experiments using different
perturbation radius from the set $\\{0.01,0.05,0.1,0.2,0.25,0.3\\}$, as
depicted in Figure 3 (d). The results indicate that an appropriate value of
$\rho$ can enhance the model’s generalization ability, and within the given
set, $\rho=0.1$ is the optimal value. Furthermore, it is observed that as
$\rho$ increases, the convergence speed gradually decreases, which aligns with
our previous analysis.

#### Penalty parameter $\lambda$.

The penalty parameter $\lambda$ has an impact on the performance as the
communication round $T$ increases. It represents a trade-off between the local
optima and the consistency of the aggregated model. If $\lambda$ is too small,
the client model parameters may get trapped near the aggregated model
parameters, making it difficult to optimize. On the other hand, if $\lambda$
is too large, clients may move towards local optima, exacerbating local
inconsistency. To select an appropriate value for the penalty parameter in our
algorithms, we conduct several experiments using different values from the set
$\\{0.05,0.1,0.2,0.5\\}$, as shown in Figure 3 (b). We observe that we achieve
better performance with $\lambda=0.2$ compared to other values in the set.

##  6 Conclusions And Future Work

In this paper, we address two challenges in Decentralized Federated Learning
(DFL): local inconsistency and local heterogeneous overfitting. We propose two
DFL frameworks: DFedADMM and DFedADMM-SAM, to achieve better model consistency
among clients. DFedADMM addresses model inconsistency caused by heterogeneous
data by introducing a dual constraint, and DFedADMM-SAM is an enhanced version
of DFedADMM that incorporates gradient perturbation based on the Sharpness-
Aware Minimization (SAM) optimizer to generate locally flat models. This helps
alleviate local heterogeneous overfitting by seeking models with uniformly low
loss values. For theoretical findings, We explore the convergence rate in DFL
by investigating the impacts of gradient perturbation in SAM, the local epoch
K, the penalty parameter in ADMM, the network topology, and data homogeneity.
Our theoretical findings provide a unified understanding of these factors on
the convergence rate in DFL. Furthermore, empirical results further validate
the effectiveness of our proposed approaches. Moving forward, future work will
focus on understanding the generalization of ADMM in the context of DFL.

## References

  * Acar et al. (2021) Acar, D. A. E.; Zhao, Y.; Navarro, R. M.; Mattina, M.; Whatmough, P. N.; and Saligrama, V. 2021.  Federated learning based on dynamic regularization.  _arXiv preprint arXiv:2111.04263_.
  * Andriushchenko and Flammarion (2022) Andriushchenko, M.; and Flammarion, N. 2022.  Towards understanding sharpness-aware minimization.  In _International Conference on Machine Learning_ , 639–668. PMLR.
  * Beltrán et al. (2022) Beltrán, E. T. M.; Pérez, M. Q.; Sánchez, P. M. S.; Bernal, S. L.; Bovet, G.; Pérez, M. G.; Pérez, G. M.; and Celdrán, A. H. 2022.  Decentralized federated learning: Fundamentals, state-of-the-art, frameworks, trends, and challenges.  _arXiv preprint arXiv:2211.08413_.
  * Bertsekas (2014) Bertsekas, D. P. 2014.  _Constrained optimization and Lagrange multiplier methods_.  Academic press.
  * Boyd et al. (2011) Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J.; et al. 2011.  Distributed optimization and statistical learning via the alternating direction method of multipliers.  _Foundations and Trends® in Machine learning_ , 3(1): 1–122.
  * Dai et al. (2022) Dai, R.; Shen, L.; He, F.; Tian, X.; and Tao, D. 2022.  DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training.  In _International Conference on Machine Learning_ , 4587–4604. PMLR.
  * Du et al. (2021) Du, J.; Yan, H.; Feng, J.; Zhou, J. T.; Zhen, L.; Goh, R. S. M.; and Tan, V. 2021\.  Efficient Sharpness-aware Minimization for Improved Training of Neural Networks.  In _International Conference on Learning Representations_.
  * Foret et al. (2020) Foret, P.; Kleiner, A.; Mobahi, H.; and Neyshabur, B. 2020.  Sharpness-aware Minimization for Efficiently Improving Generalization.  In _International Conference on Learning Representations_.
  * Gabay and Mercier (1976) Gabay, D.; and Mercier, B. 1976.  A dual algorithm for the solution of nonlinear variational problems via finite element approximation.  _Computers & mathematics with applications_, 2(1): 17–40.
  * Gabrielli, Pica, and Tolomei (2023) Gabrielli, E.; Pica, G.; and Tolomei, G. 2023.  A Survey on Decentralized Federated Learning.  _arXiv preprint arXiv:2308.04604_.
  * Gong, Li, and Freris (2022) Gong, Y.; Li, Y.; and Freris, N. M. 2022.  FedADMM: A robust federated deep learning framework with adaptivity to system heterogeneity.  In _2022 IEEE 38th International Conference on Data Engineering (ICDE)_ , 2575–2587. IEEE.
  * Hsu, Qi, and Brown (2019) Hsu, T.-M. H.; Qi, H.; and Brown, M. 2019.  Measuring the effects of non-identical data distribution for federated visual classification.  _arXiv preprint arXiv:1909.06335_.
  * Krizhevsky, Hinton et al. (2009) Krizhevsky, A.; Hinton, G.; et al. 2009.  Learning multiple layers of features from tiny images.
  * Kwon et al. (2021) Kwon, J.; Kim, J.; Park, H.; and Choi, I. K. 2021.  Asam: Adaptive sharpness-aware minimization for scale-invariant learning of deep neural networks.  In _International Conference on Machine Learning_ , 5905–5914. PMLR.
  * Lalitha et al. (2019) Lalitha, A.; Kilinc, O. C.; Javidi, T.; and Koushanfar, F. 2019.  Peer-to-peer federated learning on graphs.  _arXiv preprint arXiv:1901.11173_.
  * Lalitha et al. (2018) Lalitha, A.; Shekhar, S.; Javidi, T.; and Koushanfar, F. 2018.  Fully decentralized federated learning.  In _Third workshop on Bayesian Deep Learning (NeurIPS)_.
  * Li et al. (2020) Li, T.; Sahu, A. K.; Talwalkar, A.; and Smith, V. 2020.  Federated learning: Challenges, methods, and future directions.  _IEEE signal processing magazine_ , 37(3): 50–60.
  * Lian et al. (2017) 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_ , 5330–5340.
  * McMahan et al. (2017) McMahan, B.; Moore, E.; Ramage, D.; Hampson, S.; and y Arcas, B. A. 2017.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , 1273–1282. PMLR.
  * Nedic and Ozdaglar (2009) Nedic, A.; and Ozdaglar, A. 2009.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1): 48–61.
  * Qu et al. (2022) Qu, Z.; Li, X.; Duan, R.; Liu, Y.; Tang, B.; and Lu, Z. 2022.  Generalized Federated Learning via Sharpness Aware Minimization.  In _International Conference on Machine Learning, ICML_ , 18250–18280.
  * Shi et al. (2023a) Shi, Y.; Liu, Y.; Sun, Y.; Lin, Z.; Shen, L.; Wang, X.; and Tao, D. 2023a.  Towards More Suitable Personalization in Federated Learning via Decentralized Partial Model Training.  _arXiv preprint arXiv:2305.15157_.
  * Shi et al. (2023b) Shi, Y.; Liu, Y.; Wei, K.; Shen, L.; Wang, X.; and Tao, D. 2023b.  Make landscape flatter in differentially private federated learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 24552–24562.
  * Shi et al. (2023c) Shi, Y.; Shen, L.; Wei, K.; Sun, Y.; Yuan, B.; Wang, X.; and Tao, D. 2023c.  Improving the model consistency of decentralized federated learning.  _arXiv preprint arXiv:2302.04083_.
  * Simonyan and Zisserman (2014) Simonyan, K.; and Zisserman, A. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_.
  * Sun, Li, and Wang (2022) Sun, T.; Li, D.; and Wang, B. 2022.  Decentralized Federated Averaging.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.
  * Sun et al. (2023) Sun, Y.; Shen, L.; Huang, T.; Ding, L.; and Tao, D. 2023.  Fedspeed: Larger local interval, less communication round, and higher generalization accuracy.  _arXiv preprint arXiv:2302.10429_.
  * Tran Dinh et al. (2021) Tran Dinh, Q.; Pham, N. H.; Phan, D.; and Nguyen, L. 2021.  FedDR–randomized Douglas-Rachford splitting algorithms for nonconvex federated composite optimization.  _Advances in Neural Information Processing Systems_ , 34: 30326–30338.
  * Wang, Marella, and Anderson (2022) Wang, H.; Marella, S.; and Anderson, J. 2022.  Fedadmm: A federated primal-dual algorithm allowing partial participation.  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 287–294. IEEE.
  * Wang et al. (2021) Wang, J.; Charles, Z.; Xu, Z.; Joshi, G.; McMahan, H. B.; Al-Shedivat, M.; Andrew, G.; Avestimehr, S.; Daly, K.; Data, D.; et al. 2021.  A field guide to federated optimization.  _arXiv preprint arXiv:2107.06917_.
  * Wang et al. (2023) Wang, S.; Xu, Y.; Wang, Z.; Chang, T.-H.; Quek, T. Q.; and Sun, D. 2023.  Beyond ADMM: A Unified Client-Variance-Reduced Adaptive Federated Learning Framework.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, 10175–10183.
  * Yang et al. (2019) Yang, Q.; Liu, Y.; Cheng, Y.; Kang, Y.; Chen, T.; and Yu, H. 2019.  Federated Learning. Morgan & Claypool Publishers.
  * Yuan et al. (2023) Yuan, L.; Sun, L.; Yu, P. S.; and Wang, Z. 2023.  Decentralized Federated Learning: A Survey and Perspective.  _arXiv preprint arXiv:2306.01603_.
  * Zhang and Hong (2021) Zhang, X.; and Hong, M. 2021.  On the Connection Between Fed-Dyn and FedPD.  _FedDyn_FedPD. pdf_.
  * Zhang et al. (2021) Zhang, X.; Hong, M.; Dhople, S.; Yin, W.; and Liu, Y. 2021.  FedPD: A federated learning framework with adaptivity to non-iid data.  _IEEE Transactions on Signal Processing_ , 69: 6055–6070.
  * Zhao, Zhang, and Hu (2022) Zhao, Y.; Zhang, H.; and Hu, X. 2022.  Penalizing gradient norm for efficiently improving generalization in deep learning.  In _International Conference on Machine Learning_ , 26982–26992. PMLR.
  * Zhong et al. (2022) Zhong, Q.; Ding, L.; Shen, L.; Mi, P.; Liu, J.; Du, B.; and Tao, D. 2022.  Improving sharpness-aware minimization with fisher mask for better generalization on language models.  _arXiv preprint arXiv:2210.05497_.
  * Zhou and Li (2023) Zhou, S.; and Li, G. Y. 2023.  Federated learning via inexact ADMM.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.
  * Zhu et al. (2023) Zhu, T.; He, F.; Chen, K.; Song, M.; and Tao, D. 2023.  Decentralized SGD and Average-direction SAM are Asymptotically Equivalent.  arXiv:2306.02913.
  * Zhu et al. (2022) Zhu, T.; He, F.; Zhang, L.; Niu, Z.; Song, M.; and Tao, D. 2022.  Topology-aware generalization of decentralized sgd.  In _International Conference on Machine Learning_ , 27479–27503. PMLR.

Appendix for “ DFedADMM: Dual Constraints Controlled Model Inconsistency
for Decentralized Federated Learning ”

##  Appendix A  More Details on Algorithm Implementation

###  A.1 Datasets and backbones.

MNIST is a relatively simple dataset for handwritten digit recognition.
CIFAR-10 and CIFAR-100 (Krizhevsky, Hinton et al. 2009) are labeled subsets of
the larger 80 million images dataset. These three datasets share the same set
of 60,000 input images. CIFAR-100 provides a more detailed labeling with 100
unique labels, while CIFAR-10 has 10 unique labels. The ResNet as the backbone
is used for CIFAR-100, where the batch-norm layers are replaced by group-norm
layers due to a detrimental effect of batch-norm. The backbone architecture
used for MNIST is as follows: Cascading three fully connected layers, the
architecture includes 200 neurons in the initial layer, followed by an
additional 200 neurons in the subsequent layer, and concludes with 10 output
neurons in the final layer.This architecture can be found in the work of (Sun,
Li, and Wang 2022). The backbone architecture used for CIFAR-10 is as follows:
The architecture of the network consists of two convolutional layers, one max
pooling layer, and three fully connected layers. The first convolutional layer
takes a 3-channel input and generates a 64-channel output using a kernel size
of 5. Similarly, the second convolutional layer has 64 input channels, 64
output channels, and a kernel size of 5. Following each convolutional layer,
spatial dimensions are reduced through max pooling with a kernel size of 2 and
a stride of 2. The subsequent fully connected layers comprise 384 neurons in
the first layer, 192 neurons in the second layer, and a final layer with an
output size that matches the number of classes in the classification task.

###  A.2 More details about baselines.

FedAvg is a classical FL method that utilizes weighted averaging to train a
global model in parallel with a central server. FedSAM applies the Sharpness-
Aware Minimization (SAM) method as the local optimizer to enhance the model’s
generalization performance. In the decentralized setting, D-PSGD is a well-
known decentralized parallel SGD method that aims to reach a consensus model.
It should be noted that in this work, we focus on decentralized FL, which
involves multiple local iterates during training, as opposed to decentralized
learning/training that focuses on one-step local training. For instance,
D-PSGD (Lian et al. 2017) is a decentralized training algorithm that uses one-
step SGD to train local models in each communication round. DFedAvg is a
decentralized version of FedAvg, where clients perform local training and
share updated models through communication rounds. DFedAvgM extends on DFedAvg
by incorporating SGD with momentum, where each client performs multiple local
training steps before each communication round. Furthermore, DFedSAM enhances
the generalization ability of the aggregated model by applying gradient
perturbation techniques to generate locally flattened models.

###  A.3 Hyperparameters.

In our experiments, we set the total number of clients to 100 for both
centralized and decentralized settings. In the decentralized setting, each
client is connected to at most 10 neighbors. For the centralized setting, the
sample ratio of clients is set to 0.1. The local learning rate is initialized
to 0.1 and decayed by a factor of 0.998 after each communication round in all
experiments. For centralized methods, the global learning rate is set to 1.0.
The batch size is fixed at 128 for all experiments. We run 500 global
communication rounds for CIFAR-10/100 and 300 global communication rounds for
MNIST. We use the SGD optimizer with a weighted decay parameter of 0.0005 for
all baselines except for DFedADMM and DFedADMM-SAM. In algorithms based on the
SAM optimizer, such as FedSAM, DFedSAM, and DFedADMM-SAM, the hyper-parameter
for gradient perturbation, denoted as $\rho$, is set to 0.1. In addition, in
our algorithm, the penalty parameter $\lambda$ is set to 0.1 for all
experiments. Following the approach in (Sun, Li, and Wang 2022), we use a
momentum of 0.9 for the local optimization in DFedAvgM. For the number of
local iterations $K$, the training epoch in D-PSGD is set to 1, while for all
other methods, it is set to 5.

###  A.4 Communication configurations.

In the decentralized methods, such as mentioned in (Dai et al. 2022), the
communication volume is generally higher compared to centralized methods. This
is because each client in the network topology needs to transmit their local
information to their neighbors. However, in the centralized setting, only a
subset of clients is sampled to upload their parameter updates to a central
server. To ensure a fair comparison, we adopt a dynamic and time-varying
connection topology for the decentralized methods in Section 5.2.
Specifically, we restrict each client to communicate with a maximum of 10
randomly selected neighbors, without replacement, from all the clients.
Moreover, only 10 clients, who are neighbors to each other, are allowed to
perform one gossip step to exchange their local information in the
decentralized methods.

##  Appendix B More experiments results

###  B.1 Convergence speed

We demonstrate the needed communication rounds for each method to reach a
target accuracy as follows. Results for MNIST are in Table 3, while results
for CIFAR-10 in Table 4 and CIFAR1-100 in Table 5.

Methods | Dir 0.3 | Dir 0.6 | IID
---|---|---|---
Acc@97 | Acc@98 |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| Acc@98 |<EMAIL_ADDRESS>|<EMAIL_ADDRESS>| Acc@98 |<EMAIL_ADDRESS>
FedAvg | 60 | >300 | >300 | 76 | 194 | >300 | 46 | 108 | 135
FedSAM | 41 | 135 | 201 | 55 | 121 | 177 | 33 | 68 | 98
D-PSGD | 223 | >300 | >300 | >300 | >300 | >300 | 227 | >300 | >300
DFedAvg | 87 | >300 | >300 | 107 | >300 | >300 | 64 | 229 | >300
DFedAvgM | 19 | 104 | >300 | 26 | 67 | 258 | 19 | 53 | 283
DFedSAM | 51 | 140 | 218 | 67 | 163 | 294 | 53 | 105 | 200
DFedADMM | 19 | 115 | >300 | 22 | 45 | >300 | 18 | 53 | >300
DFedADMM-SAM | 16 | 32 | 40 | 21 | 30 | 41 | 16 | 25 | 32

Table 3: Averaged needed communication rounds for each method to a target
accuracy on MNIST dataset.

Methods | Dir 0.3 | Dir 0.6 | IID
---|---|---|---
Acc@73 | Acc@75 | Acc@80 | Acc@75 | Acc@79 | Acc@81 | Acc@78 | Acc@80 | Acc@82
FedAvg | 113 | 154 | >500 | 121 | 392 | >500 | 143 | 243 | >500
FedSAM | 120 | 141 | 392 | 111 | 211 | 399 | 128 | 195 | 329
D-PSGD | 500 | >500 | >500 | >500 | >500 | >500 | 499 | >500 | >500
DFedAvg | 124 | 177 | >500 | 138 | >500 | >500 | 190 | >500 | >500
DFedAvgM | 61 | 91 | >500 | 61 | 217 | >500 | 58 | 101 | 237
DFedSAM | 145 | 182 | 473 | 146 | 281 | >500 | >237 | >237 | >237
DFedADMM | 45 | 62 | 330 | 52 | 183 | >500 | 60 | 236 | >500
DFedADMM-SAM | 63 | 72 | 167 | 53 | 95 | 165 | 50 | 67 | 125

Table 4: Averaged needed communication rounds for each method to a target
accuracy on CIFAR-10 dataset.

Methods | Dir 0.3 | Dir 0.6 | IID
---|---|---|---
Acc@50 | Acc@55 | Acc@58 | Acc@52 | Acc@55 | Acc@58 | Acc@55 | Acc@58 | Acc@60
FedAvg | 98 | 381 | >500 | 105 | 257 | >500 | 126 | >500 | >500
FedSAM | 136 | 311 | >500 | 147 | 261 | >500 | >500 | >500 | >500
D-PSGD | 232 | 402 | >500 | 261 | 386 | >500 | 320 | >500 | >500
DFedAvg | 57 | 111 | 268 | 61 | 95 | 212 | 66 | 135 | 391
DFedAvgM | 59 | >500 | >500 | 47 | 111 | >500 | 65 | >500 | >500
DFedSAM | 91 | 153 | 287 | 92 | 135 | 233 | 86 | 141 | 318
DFedADMM | 42 | 67 | 123 | 33 | 42 | 72 | 28 | 40 | 54
DFedADMM-SAM | 44 | 67 | 108 | 40 | 54 | 76 | 31 | 45 | 70

Table 5: Averaged needed communication rounds for each method to a target
accuracy on CIFAR-100 dataset.

From Tables 3, 4, and 5, it can be observed that our proposed algorithms,
DFedADMM and DFedADMM-SAM, achieve the minimum communication cost for a given
target accuracy. Compared to other baseline methods, our algorithms are able
to reach 90% of the final convergence accuracy in fewer communication rounds.
This result demonstrates the fast convergence speed of our algorithms.

###  B.2 Different topology

Figure 4:  Accuracy of different DFL algorithms with different decentralized
topologies on the test dataset.

This Figure 4 complements Table 2, showing that as the connectivity of the
communication topology improves, the proposed algorithm achieves higher
accuracy on the test set. This observation aligns with the conclusion of
Corollary 1 in Section 4.

###  B.3 Performance Evaluation

(a) MNIST

(b) CIFAR-10

(c) CIFAR-100

Figure 5:  Test accuracy of all baselines on (a) MNIST, (b) CIFAR-10, and (c)
CIFAR-100 in both IID and non-IID settings.

Similar to Table 1, Figure 5 presents the performance of each method on
different datasets and with different data partitioning schemes.

##  Appendix C Proofs for Analysis

In this part we will demonstrate the proofs of all formula mentioned in this
paper. Each formula is presented in the form of a lemma.

###### Lemma 1

[Lemma 4, (Lian et al. 2017)] For any $t\in\mathbb{Z}^{+}$, the mixing matrix
${\bf W}\in\ \mathbb{R}^{m}$ satisfies $\|{\bf W}^{t}-{\bf
P}\|_{\emph{op}}\leq\psi^{t},$ where $\psi:=\max\\{|\psi_{2}(\bf
W)|,|\psi_{m}(\bf W)|\\}$ and for a matrix ${\bf A}$, we denote its spectral
norm as $\|{\bf A}\|_{\emph{op}}$. Furthermore, ${\bf
1}:=[1,1,\ldots,1]^{\top}\in\mathbb{R}^{m}$ and

${\bf P}:=\frac{\mathbf{1}\mathbf{1}^{\top}}{m}\in\mathbb{R}^{m\times m}.$

In [Proposition 1, (Nedic and Ozdaglar 2009)], the author also proved that
$\|{\bf W}^{t}-{\bf P}\|_{\textrm{op}}\leq C\psi^{t}$ for some $C>0$ that
depends on the matrix.

###### Lemma 2

For $\forall\ \mathbf{x}_{i,k}^{t}\in\mathbb{R}^{d}$ and
$i\in\mathcal{S}^{t}$, we denote
$\delta_{i,k}^{t}=\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i,k-1}^{t}$ with setting
$\delta_{i,0}^{t}=0$, and
$\Delta_{i,K}^{t}=\sum_{k=0}^{K}\delta_{i,k}^{t}=\mathbf{x}_{i,K}^{t}-\mathbf{x}_{i,0}^{t}$,
under the update rule in Algorithm Algorithm 1, we have:

$\Delta_{i,K}^{t}=-\lambda\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}+\gamma\lambda\hat{\mathbf{g}}_{i}^{t-1}$
(9)

where
$\sum_{k=0}^{K-1}\gamma_{k}=\sum_{k=0}^{K-1}\frac{\eta_{l}}{\lambda}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}=\gamma=1-(1-\frac{\eta_{l}}{\lambda})^{K}$.

###### Proof 1

According to the update rule of Line.11 in Algorithm 1, we have:

$\displaystyle\delta_{k}$
$\displaystyle=\Delta_{i,k}^{t}-\Delta_{i,k-1}^{t}=\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i,k-1}^{t}$
$\displaystyle=-\eta_{l}\bigl{(}\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1}+\frac{1}{\lambda}(\mathbf{x}_{i,k-1}^{t}-\mathbf{x}_{i,0}^{t})\bigr{)}=-\eta_{l}(\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1}+\frac{1}{\lambda}\Delta_{i,k-1}^{t}).$

Then We can formulate the iterative relationship of $\Delta_{i,k}^{t}$ as:

$\displaystyle\Delta_{i,k}^{t}=\Delta_{i,k-1}^{t}-\eta_{l}(\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1}+\frac{1}{\lambda}\Delta_{i,k-1}^{t})=(1-\frac{\eta_{l}}{\lambda})\Delta_{i,k-1}^{t}-\eta_{l}(\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1}).$

Taking the iteration on $k$ and we have:

$\displaystyle\mathbf{x}_{i,K}^{t}-\mathbf{x}_{i,0}^{t}=\Delta_{i,K}^{t}$
$\displaystyle=(1-\frac{\eta_{l}}{\lambda})^{K}\Delta_{i,0}^{t}-\eta_{l}\sum_{k=0}^{K-1}(1-\frac{\eta_{l}}{\lambda})^{K-1-k}(\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle\overset{(a)}{=}-\eta_{l}\sum_{k=0}^{K-1}(1-\frac{\eta_{l}}{\lambda})^{K-1-k}(\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=-\lambda\sum_{k=0}^{K-1}\frac{\eta_{l}}{\lambda}(1-\frac{\eta_{l}}{\lambda})^{K-1-k}(\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=-\lambda\sum_{k=0}^{K-1}\frac{\eta_{l}}{\lambda}(1-\frac{\eta_{l}}{\lambda})^{K-1-k}\mathbf{g}_{i,k}^{t}+\bigl{(}1-(1-\frac{\eta_{l}}{\lambda})^{K}\bigr{)}\lambda\hat{\mathbf{g}}_{i}^{t-1}$
$\displaystyle=-\lambda\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}+\gamma\lambda\hat{\mathbf{g}}_{i}^{t-1}.$

(a) applies $\Delta_{i,0}^{t}=\delta_{i,0}^{t}=0$.

###### Lemma 3

Under the update rule in Algorithm Algorithm 1, we have:

$\hat{\mathbf{g}}_{i}^{t}=(1-\gamma)\hat{\mathbf{g}}_{i}^{t-1}+\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}.$
(10)

where
$\sum_{k=0}^{K-1}\gamma_{k}=\sum_{k=0}^{K-1}\frac{\eta_{l}}{\lambda}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}=\gamma=1-(1-\frac{\eta_{l}}{\lambda})^{K}$.

###### Proof 2

According to the update rule of Line.13 in Algorithm 1, we have:

$\displaystyle\hat{\mathbf{g}}_{i}^{t}$
$\displaystyle=\hat{\mathbf{g}}_{i}^{t-1}-\frac{1}{\lambda}(\mathbf{x}_{i,K}^{t}-\mathbf{x}_{i,0}^{t})$
$\displaystyle\overset{(a)}{=}\hat{\mathbf{g}}_{i}^{t-1}+\frac{\eta_{l}}{\lambda}\sum_{k=0}^{K-1}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}(\mathbf{g}_{i,k}^{t}-\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=\hat{\mathbf{g}}_{i}^{t-1}+\frac{\eta_{l}}{\lambda}\sum_{k=0}^{K-1}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}\mathbf{g}_{i,k}^{t}-\frac{\eta_{l}}{\lambda}\Bigl{(}\sum_{k=0}^{K-1}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}\Bigr{)}\hat{\mathbf{g}}_{i}^{t-1}$
$\displaystyle=\hat{\mathbf{g}}_{i}^{t-1}+\frac{\eta_{l}}{\lambda}\sum_{k=0}^{K-1}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}\mathbf{g}_{i,k}^{t}-\frac{\eta_{l}}{\lambda}\frac{1-(1-\frac{\eta_{l}}{\lambda})^{K}}{\frac{\eta_{l}}{\lambda}}\hat{\mathbf{g}}_{i}^{t-1}$
$\displaystyle=(1-\frac{\eta_{l}}{\lambda})^{K}\hat{\mathbf{g}}_{i}^{t-1}+\frac{\eta_{l}}{\lambda}\sum_{k=0}^{K-1}\bigl{(}1-\frac{\eta_{l}}{\lambda}\bigr{)}^{K-1-k}\mathbf{g}_{i,k}^{t}$
$\displaystyle=(1-\gamma)\hat{\mathbf{g}}_{i}^{t-1}+\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}$

(a) applies the Lemma 2.

###### Lemma 4

(Bounded global update) The global update
$\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t}$ holds the upper bound of:

$\displaystyle\mathbb{E}_{t}\|\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t}\|^{2}\leq\sigma_{l}^{2}+B^{2}$

###### Proof 3

According to the lemma 3,we have:

$\displaystyle\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t}=(1-\gamma)\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-1}+\gamma\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}.$

Take the L2-norm and we have:

$\displaystyle\|\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t}\|^{2}$
$\displaystyle=\|(1-\gamma)\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-1}+\gamma\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}\|^{2}$
$\displaystyle\leq(1-\gamma)\|\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\|\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}\|^{2}.$
$\displaystyle\leq(1-\gamma)\|\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\left(\sigma_{l}^{2}+B^{2}\right)$

Thus we have the following recursion,

$\displaystyle\mathbb{E}_{t}\|\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-1}\|^{2}\leq(1-\gamma)\mathbb{E}_{t}\|\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\left(\sigma_{l}^{2}+B^{2}\right)\leq\left(\sigma_{l}^{2}+B^{2}\right)$

Where we use the fact $0<\gamma<1$

###### Lemma 5

(Bounded local update) The local update $\hat{\mathbf{g}}_{i}^{t}$ holds the
upper bound of:

$\displaystyle\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t}\|^{2}\leq(\sigma_{l}^{2}+B^{2})$

###### Proof 4

According to the lemma3, we have:

$\displaystyle\hat{\mathbf{g}}_{i}^{t}=(1-\gamma)\hat{\mathbf{g}}_{i}^{t-1}+\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}.$

Take the L2-norm and we have:

$\displaystyle\|\hat{\mathbf{g}}_{i}^{t}\|^{2}$
$\displaystyle=\|(1-\gamma)\hat{\mathbf{g}}_{i}^{t-1}+\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}\|^{2}$
$\displaystyle\overset{(a)}{\leq}(1-\gamma)\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\|\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}\|^{2}$
$\displaystyle\overset{(b)}{\leq}(1-\gamma)\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\|\mathbf{g}_{i,k}^{t}\|^{2}$

(a) and (b) hold by applying the Jensen inequality. Thus we have the following
recursion:

$\displaystyle\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t}\|^{2}$
$\displaystyle\leq(1-\gamma)\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbb{E}_{t}\|\mathbf{g}_{i,k}^{t}\|^{2}$
$\displaystyle\leq(1-\gamma)\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+\gamma\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\leq\sigma_{l}^{2}+B^{2}$

###### Lemma 6

(Bounded global update) Given the stepsize $0<\eta_{l}<\frac{1}{6LK}$, we have
following bound:

$\frac{1}{m}\sum_{i\in{m}}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}\leq
16\eta_{l}^{2}K^{2}C_{0}$ (11)

where
$C_{0}=\left(3\sigma_{g}^{2}+\sigma_{l}^{2}\right)+3\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(\sigma_{l}^{2}+B^{2})$

###### Proof 5

We denote
$\mathbf{c}^{t}=\frac{1}{m}\sum_{i\in{m}}\sum_{k=0}^{K-1}(\gamma_{k}/\gamma)\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}$
term as the local offset after $k$ iterations updates, we firstly consider the
$\mathbf{c}_{k}^{t}=\frac{1}{m}\sum_{i\in{m}}\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}$
and it can be bounded as:

$\displaystyle\mathbf{c}_{k}^{t}$
$\displaystyle=\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}=\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i,k-1}^{t}+\mathbf{x}_{i,k-1}^{t}-\mathbf{x}_{i,0}^{t}\|^{2}$
$\displaystyle=\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|-\eta_{l}(\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1})+(1-\frac{\eta_{l}}{\lambda})(\mathbf{x}_{i,k-1}^{t}-\mathbf{x}_{i,0}^{t})\|^{2}$
$\displaystyle\leq(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i,k-1}^{t}-\mathbf{x}_{i,0}^{t}\|^{2}+(1+\frac{1}{a})\frac{\eta_{l}^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1}\|^{2}$
$\displaystyle=(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\mathbf{c}_{k-1}^{t}+(1+\frac{1}{a})\frac{\eta_{l}^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{g}_{i,k-1}^{t}-\hat{\mathbf{g}}_{i}^{t-1}\|^{2}$
$\displaystyle=(1+\frac{1}{a})\frac{\eta_{l}^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f_{i}(\mathbf{x}_{i,k-1}^{t})-\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+(1+\frac{1}{a})\eta_{l}^{2}\sigma_{l}^{2}+(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\mathbf{c}_{k-1}^{t}$
$\displaystyle\leq(1+\frac{1}{a})\frac{2\eta_{l}^{2}}{m}\sum_{i\in[m]}\left(\mathbb{E}_{t}\|\nabla
f_{i}(\mathbf{x}_{i,k-1}^{t})\|^{2}+\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}\right)+(1+\frac{1}{a})\eta_{l}^{2}\sigma_{l}^{2}+(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\mathbf{c}_{k-1}^{t}$
$\displaystyle\leq(1+\frac{1}{a})\frac{2\eta_{l}^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f_{i}(\mathbf{x}_{i,k-1}^{t})\|^{2}+(1+\frac{1}{a})\frac{2\eta_{l}^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}+(1+\frac{1}{a})\eta_{l}^{2}\sigma_{l}^{2}$
$\displaystyle\quad+(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\mathbf{c}_{k-1}^{t}$
$\displaystyle\leq(1+\frac{1}{a})\frac{2\eta_{l}^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f_{i}(\mathbf{x}_{i,k-1}^{t})-\nabla f_{i}(\mathbf{x}_{i}^{t})+\nabla
f_{i}(\mathbf{x}_{i}^{t})-\nabla f(\mathbf{x}_{i}^{t})+\nabla
f(\mathbf{x}_{i}^{t})\|^{2}$
$\displaystyle\quad+(1+\frac{1}{a})2\eta_{l}^{2}\left(\sigma_{l}^{2}+B^{2}\right)+(1+\frac{1}{a})\eta_{l}^{2}\sigma_{l}^{2}+(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\mathbf{c}_{k-1}^{t}$
$\displaystyle\leq(1+\frac{1}{a})\frac{6\eta_{l}^{2}L^{2}}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i,k-1}^{t}-\mathbf{x}_{i}^{t}\|^{2}+(1+\frac{1}{a})\eta_{l}^{2}(6\sigma_{g}^{2}+\sigma_{l}^{2})+(1+\frac{1}{a})6\eta_{l}^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}$
$\displaystyle\quad+(1+\frac{1}{a})2\eta_{l}^{2}\left(\sigma_{l}^{2}+B^{2}\right)+(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}\mathbf{c}_{k-1}^{t}$
$\displaystyle\leq\left[(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}+(1+\frac{1}{a})6\eta_{l}^{2}L^{2}\right]\mathbf{c}_{k-1}^{t}+(1+\frac{1}{a})\eta_{l}^{2}(6\sigma_{g}^{2}+\sigma_{l}^{2})$
$\displaystyle\quad+(1+\frac{1}{a})6\eta_{l}^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(1+\frac{1}{a})2\eta_{l}^{2}\left(\sigma_{l}^{2}+B^{2}\right)$

we have:

$\displaystyle\begin{aligned}
\mathbf{c}_{k}^{t}&\leq\left[(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}+(1+\frac{1}{a})6\eta_{l}^{2}L^{2}\right]\mathbf{c}_{k-1}^{t}+(1+\frac{1}{a})\eta_{l}^{2}(6\sigma_{g}^{2}+\sigma_{l}^{2})\\\
&\quad+(1+\frac{1}{a})6\eta_{l}^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(1+\frac{1}{a})2\eta_{l}^{2}\left(\sigma_{l}^{2}+B^{2}\right)\\\
\end{aligned}$ (12)

Set $a=2K-1,\eta_{l}\leq 2\lambda$ and $0<\eta_{l}<\frac{1}{6LK}$, we get:

$\displaystyle(1+a)(1-\frac{\eta_{l}}{\lambda})^{2}+(1+\frac{1}{a})6\eta_{l}^{2}L^{2}<1+\frac{1}{K-1}$

then we have:

$\displaystyle\mathbf{c}_{k}^{t}$ $\displaystyle\leq
4K\eta_{l}^{2}\sum_{j=0}^{K-1}\left(1+\frac{1}{K-1}\right)^{j}\Bigl{(}\left(3\sigma_{g}^{2}+\sigma_{l}^{2}\right)+3\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(\sigma_{l}^{2}+B^{2})\Bigr{)}$
$\displaystyle=4K\eta_{l}^{2}\left(K-1\right)\left[\left(1+\frac{1}{K-1}\right)^{K}-1\right]\Bigl{(}\left(3\sigma_{g}^{2}+\sigma_{l}^{2}\right)+3\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(\sigma_{l}^{2}+B^{2})\Bigr{)}$
$\displaystyle\overset{(a)}{\leq}16K^{2}\eta_{l}^{2}\Bigl{(}\left(3\sigma_{g}^{2}+\sigma_{l}^{2}\right)+3\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(\sigma_{l}^{2}+B^{2})\Bigr{)}$ (13)

Where (a) uses the inequality $\left(1+\frac{1}{K-1}\right)^{K}<5$ holds for
any $K\geq 1$.

Since the expression of
$\mathbf{c}^{t}=\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{c}_{k}^{t}$,
the upper bound of $\mathbf{c}^{t}$ is the same as the upper bound of
$\mathbf{c}_{k}^{t}$:

$\displaystyle\mathbf{c}^{t}$ $\displaystyle\leq
16K^{2}\eta_{l}^{2}\Bigl{(}\left(3\sigma_{g}^{2}+\sigma_{l}^{2}\right)+3\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(\sigma_{l}^{2}+B^{2})\Bigr{)}$

we complete the proof.

###### Lemma 7

(Bounded local update) Given the stepsize $0<\eta_{l}<\frac{1}{6LK}$, we have
following bound:

$\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}\leq
16\eta_{l}^{2}K^{2}C_{0}$ (14)

where
$C_{0}=\Bigl{(}\left(3\sigma_{g}^{2}+\sigma_{l}^{2}\right)+3\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+(\sigma_{l}^{2}+B^{2})\Bigr{)}$

###### Proof 6

We use equation 5 and
$\mathbf{c}^{t}=\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{c}_{k}^{t}$
complete the proof.

###### Lemma 8

Let $\\{\mathbf{x}^{t}(i)\\}_{t\geq 0}$ be generated by DFedADMM for all
$i\in\\{1,2,...,m\\}$ and any learning rate $\frac{1}{6KL}>\eta_{l}>0$, we
have following bound:

$\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}_{t}[\|\mathbf{x}_{i}^{t}-\overline{\mathbf{x}^{t}}\|^{2}]\leq\frac{2C_{2}}{(1-\psi)^{2}},$

Where
$C_{2}=16\eta_{l}^{2}K^{2}\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)+\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$.

###### Proof 7

Following [Lemma 4, (Sun, Li, and Wang 2022)], we denote ${\bf
Z}^{t}:=\begin{bmatrix}{\bf z}_{1}^{t},{\mathbf{z}}_{2}^{t},\ldots,{\bf
z}_{m}^{t}\end{bmatrix}^{\top}\in\mathbb{R}^{m\times d}$. With these notation,
we have

$\displaystyle{\bf X}^{t+1}={\bf W}{\bf Z}^{t}={\bf W}{\bf
X}^{t}-{\bf\zeta}^{t},$ (15)

where ${\bf\zeta}^{t}:={\bf W}{\bf X}^{t}-{\bf W}{\bf Z}^{t}$. The iteration
equation (15) can be rewritten as the following expression

$\displaystyle{\bf X}^{t}={\bf W}^{t}{\bf X}^{0}-\sum_{j=0}^{t-1}{\bf
W}^{t-1-j}{\bf\zeta}^{j}.$ (16)

Obviously, it follows

${\bf W}{\bf P}={\bf P}{\bf W}={\bf P}.$ (17)

According to Lemma 1, it holds

$\|{\bf W}^{t}-{\bf P}\|\leq\psi^{t}.$

Multiplying both sides of equation (16) with ${\bf P}$ and using equation
(17), we then get

$\displaystyle{\bf P}{\bf X}^{t}={\bf P}{\bf X}^{0}-\sum_{j=0}^{t-1}{\bf
P}{\bf\zeta}^{j}=-\sum_{j=0}^{t-1}{\bf P}{\bf\zeta}^{j},$ (18)

where we used initialization ${\bf X}^{0}=\textbf{0}$. Then, we are led to

$\displaystyle\|{\bf X}^{t}-{\bf P}{\bf X}^{t}\|=\|\sum_{j=0}^{t-1}({\bf
P}-{\bf W}^{t-1-j}){\bf\zeta}^{j}\|$ (19)
$\displaystyle\leq\sum_{j=0}^{t-1}\|{\bf P}-{\bf
W}^{t-1-j}\|_{\textrm{op}}\|{\bf\zeta}^{j}\|\leq\sum_{j=0}^{t-1}\psi^{t-1-j}\|{\bf\zeta}^{j}\|.$

With Cauchy inequality,

$\displaystyle\mathbb{E}\|{\bf X}^{t}-{\bf P}{\bf
X}^{t}\|^{2}\leq\mathbb{E}(\sum_{j=0}^{t-1}\psi^{\frac{t-1-j}{2}}\cdot\psi^{\frac{t-1-j}{2}}\|{\bf\zeta}^{j}\|)^{2}$
$\displaystyle\leq(\sum_{j=0}^{t-1}\psi^{t-1-j})(\sum_{j=0}^{t-1}\psi^{t-1-j}\mathbb{E}\|{\bf\zeta}^{j}\|^{2})$

Direct calculation gives us

$\mathbb{E}\|{\bf\zeta}^{j}\|^{2}\leq\|{\bf W}\|^{2}\cdot\mathbb{E}\|{\bf
X}^{j}-{\bf Z}^{j}\|^{2}\leq\mathbb{E}\|{\bf X}^{j}-{\bf Z}^{j}\|^{2}.$

Next,we will bound $\mathbb{E}\|{\bf X}^{t}-{\bf Z}^{t}\|^{2}$.

$\displaystyle\mathbb{E}\|{\bf X}^{t}-{\bf Z}^{t}\|^{2}$
$\displaystyle=\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i}^{t}-\mathbf{z}_{i}^{t}\|^{2}$
$\displaystyle\overset{(a)}{=}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i}^{t}-\mathbf{x}_{i,K}^{t}+\lambda\hat{\mathbf{g}}_{i}^{t-1}\|^{2}$
$\displaystyle\leq
2\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i}^{t}-\mathbf{x}_{i,K}^{t}\|^{2}+2\lambda^{2}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}$
$\displaystyle\leq
2m\mathbf{c}_{t}^{K}+2\lambda^{2}m\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\hat{\mathbf{g}}_{i}^{t-1}\|^{2}$
$\displaystyle\overset{(b)}{\leq}32m\eta_{l}^{2}K^{2}\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)+2\lambda^{2}m\left(\sigma_{l}^{2}+B^{2}\right)$

Where (a) we use algorithm1 line 17, (b) apply lemma7 and 5.

Thus, we get:

$\displaystyle\mathbb{E}\|{\bf X}^{t}-{\bf Z}^{t}\|^{2}$ $\displaystyle\leq
2m\left(16\eta_{l}^{2}K^{2}\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)+\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)\right)$

In the end ,we get:

$\displaystyle\mathbb{E}\|{\bf X}^{t}-{\bf P}{\bf
X}^{t}\|^{2}\leq\frac{2mC_{2}}{(1-\psi)^{2}}.$

Where
$C_{2}=16\eta_{l}^{2}K^{2}\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)+\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$.

The fact that ${\bf X}^{t}-{\bf P}{\bf X}^{t}=\left(\begin{array}[]{c}{\bf
x}_{1}^{t}-\overline{{\bf x}^{t}}\\\ {\bf x}_{1}^{t}-\overline{{\bf x}^{t}}\\\
\vdots\\\ {\bf x}_{m}^{t}-\overline{{\bf x}^{t}}\\\ \end{array}\right)$ then
proves the result.

###### Lemma 9

Considering the
$\overline{\mathbf{x}^{t}}=\frac{1}{m}\sum_{i\in[m]}\mathbf{x}_{i}^{t}$ is the
mean averaged parameters among the last iteration of local clients at time
$t$, the auxiliary sequence
$\bigl{\\{}\mathbf{w}^{t}=\overline{\mathbf{x}^{t}}+\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})\bigr{\\}}_{t>0}$
satisfies the update rule as:

$\mathbf{w}^{t+1}=\mathbf{w}^{t}-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}.$
(20)

###### Proof 8

Firstly, according to the lemma 2 and ${\bf P}{\bf X}^{t+1}={\bf P}{\bf W}{\bf
Z}^{t}={\bf P}{\bf Z}^{t}$, that is also $\overline{{\bf
x}^{t+1}}=\overline{{\bf z}^{t}},$ so we have:

$\displaystyle\overline{\mathbf{x}^{t+1}}-\overline{\mathbf{x}^{t}}$
$\displaystyle=\overline{{\bf z}^{t}}-\overline{\mathbf{x}^{t}}$
$\displaystyle=\frac{1}{m}\sum_{i\in[m]}(\mathbf{z}_{i}^{t}-\mathbf{x}_{i}^{t})$
$\displaystyle=\frac{1}{m}\sum_{i\in[m]}(\mathbf{x}_{i,K}^{t}-\mathbf{x}_{i,0}^{t}-\lambda\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=\frac{1}{m}\sum_{i\in[m]}(-\lambda\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}+\lambda\gamma\hat{\mathbf{g}}_{i}^{t}-\lambda\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\left(\gamma\mathbf{g}_{i,k}^{t}+(1-\gamma)\hat{\mathbf{g}}_{i}^{t-1}\right).$

Then we expand the the auxiliary sequence $\mathbf{z}^{t}$ as:

$\displaystyle\mathbf{w}^{t+1}-\mathbf{w}^{t}$
$\displaystyle=(\overline{\mathbf{x}^{t+1}}-\overline{\mathbf{x}^{t}})+\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t+1}}-\overline{\mathbf{x}^{t}})-\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})$
$\displaystyle=\frac{1}{\gamma}(\overline{\mathbf{x}^{t+1}}-\overline{\mathbf{x}^{t}})-\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\left(\Bigl{(}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}\Bigr{)}+\frac{1-\gamma}{\gamma}\hat{\mathbf{g}}_{i}^{t-1}\right)-\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}-\frac{1-\gamma}{\gamma}\frac{1}{m}\sum_{i\in[m]}\lambda\hat{\mathbf{g}}_{i}^{t-1}-\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}-\frac{1-\gamma}{\gamma}\frac{1}{m}\sum_{i\in[m]}(\overline{\mathbf{z}^{t-1}}-\overline{\mathbf{x}^{t-1}}+\lambda\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}-\frac{1-\gamma}{\gamma}\frac{1}{m}\sum_{i\in[m]}(\mathbf{z}_{i}^{t-1}-\mathbf{x}_{i}^{t-1}+\lambda\hat{\mathbf{g}}_{i}^{t-1})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}-\frac{1-\gamma}{\gamma}\frac{1}{m}\sum_{i\in[m]}(\mathbf{x}_{i,K}^{t-1}-\mathbf{x}_{i,0}^{t-1}+\lambda\hat{\mathbf{g}}_{i}^{t-1}-\lambda\hat{\mathbf{g}}_{i}^{t-2})$
$\displaystyle=-\lambda\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t}.$

###### Lemma 10

Considering the
$\overline{\mathbf{x}^{t}}=\frac{1}{m}\sum_{i\in[m]}\mathbf{x}_{i}^{t}$ is the
mean averaged parameters among the last iteration of local clients at time
$t$, the auxiliary sequence
$\bigl{\\{}\mathbf{w}^{t}=\overline{\mathbf{x}^{t}}+\frac{1-\gamma}{\gamma}(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}})\bigr{\\}}_{t>0}$
satisfies the following inequation:

$\displaystyle\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{w}^{t}-\overline{\mathbf{x}^{t}}\|^{2}\leq
2\lambda^{2}\left(\gamma-1\right)^{2}\left(1+\frac{(\gamma-1)^{2}}{\gamma^{2}}\right)\left(\sigma_{l}^{2}+B^{2}\right)$

###### Proof 9

According to the defination of $\mathbf{w}^{t}$ ,we have:

$\displaystyle\overline{\mathbf{x}^{t}}-\mathbf{w}^{t}$
$\displaystyle=\frac{\gamma-1}{\gamma}\left(\overline{\mathbf{x}^{t}}-\overline{\mathbf{x}^{t-1}}\right)$
$\displaystyle=\frac{\gamma-1}{\gamma}\left(\overline{\mathbf{z}^{t-1}}-\overline{\mathbf{x}^{t-1}}\right)$
$\displaystyle=\frac{\gamma-1}{\gamma}\frac{1}{m}\sum_{i\in[m]}\left(\mathbf{z}_{i}^{t-1}-\mathbf{x}_{i}^{t-1}\right)$
$\displaystyle=\frac{\gamma-1}{\gamma}\frac{1}{m}\sum_{i\in[m]}\left(\mathbf{x}_{i,K}^{t-1}-\lambda\hat{\mathbf{g}}_{i}^{t-2}-\mathbf{x}_{i,0}^{t-1}\right)$
$\displaystyle=\frac{\gamma-1}{\gamma}\frac{1}{m}\sum_{i\in[m]}\left(-\lambda\gamma\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t-1}+\gamma\lambda\hat{\mathbf{g}}_{i}^{t-2}-\lambda\hat{\mathbf{g}}_{i}^{t-2}\right)$
$\displaystyle=-\lambda(\gamma-1)\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{g}_{i,k}^{t-1}-\lambda\frac{(\gamma-1)^{2}}{\gamma}\frac{1}{m}\sum_{i\in[m]}\hat{\mathbf{g}}_{i}^{t-2}$

so we have:

$\displaystyle\frac{1}{m}\sum_{i\in[m]}\|\overline{\mathbf{x}^{t}}-\mathbf{w}^{t}\|^{2}$
$\displaystyle\overset{(a)}{\leq}2\lambda^{2}(\gamma-1)^{2}(\sigma_{l}^{2}+B^{2})+2\lambda^{2}\frac{(\gamma-1)^{4}}{\gamma^{2}}(\sigma_{l}^{2}+B^{2})$
$\displaystyle\leq
2\lambda^{2}(\gamma-1)^{2}\left(1+\frac{(\gamma-1)^{2}}{\gamma^{2}}\right)(\sigma_{l}^{2}+B^{2})$

where (a) holds according to Lemma4.

###  C.1 Proof of convergence results for DFedADMM.

For the general non-convex case, according to the Assumptions and the
smoothness of $f$, we take the conditional expectation at round $t+1$ and
expand the $f(\mathbf{w}^{t+1})$ as:

$\displaystyle\mathbb{E}_{t}f({\bf w}^{t+1})\leq\mathbb{E}_{t}f({\bf
w}^{t})+\underbrace{\mathbb{E}_{t}\langle\nabla f({\bf w}^{t+1}),{\bf
w}^{t+1}-{\bf
w}^{t}\rangle}_{\bf{R2}}+\underbrace{\frac{L}{2}\mathbb{E}_{t}\|{\bf
w}^{t+1}-{\bf w}^{t}\|^{2}}_{\bf{R1}}$ (21)

#### Bounded R1

According to the equation(20) ,we have

$\displaystyle\mathbb{E}_{t}\|{\bf w}^{t+1}-{\bf
w}^{t}\|^{2}\leq\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$

Therefore

$\displaystyle\frac{L}{2}\mathbb{E}_{t}\|{\bf w}^{t+1}-{\bf
w}^{t}\|^{2}\leq\frac{L}{2}\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$ (22)

#### Bounded R2

Note that $\mathbf{R2}$ can be bounded as:

$\displaystyle\mathbf{R2}$ $\displaystyle=\mathbb{E}_{t}\langle\nabla f({\bf
w}^{t}),{\bf w}^{t+1}-{\bf w}^{t}\rangle$
$\displaystyle\overset{(\ref{w^t})}{=}\lambda\mathbb{E}_{t}\langle\nabla
f({\bf
w}^{t}),-\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})\rangle$
$\displaystyle=\lambda\mathbb{E}_{t}\langle\nabla f({\bf
w}^{t}),-\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})+\nabla
f({\bf w}^{t})-\nabla f({\bf w}^{t})\rangle$
$\displaystyle=\underbrace{\lambda\mathbb{E}_{t}\langle\nabla f({\bf
w}^{t}),-\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})+\frac{1}{m}\sum_{i\in[m]}\nabla
f_{i}({\bf w}^{t})\rangle}_{\mathbf{R2.1}}-\lambda\mathbb{E}_{t}\|\nabla
f({\bf w}^{t})\|^{2}$

Now we will bound $\mathbf{R2.1}$:

$\displaystyle\mathbf{R2.1}$ $\displaystyle=\lambda\mathbb{E}_{t}\langle\nabla
f({\bf
w}^{t}),-\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\left(\nabla
f_{i}(\breve{\mathbf{x}}_{i,k}^{t})-\nabla f_{i}({\bf w}^{t})\right)\rangle$
$\displaystyle=-\lambda\mathbb{E}_{t}\langle\nabla f({\bf
w}^{t}),\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\left(\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})-\nabla
f_{i}({\bf w}^{t})\right)\rangle$
$\displaystyle\overset{(a)}{\leq}\lambda\left(\frac{1}{2}\mathbb{E}_{t}\|\nabla
f({\bf
w}^{t})\|^{2}+\frac{1}{2}\mathbb{E}_{t}\|\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\left(\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})-\nabla
f_{i}({\bf w}^{t})\right)\|^{2}\right)$
$\displaystyle\leq\lambda\left(\frac{1}{2}\mathbb{E}_{t}\|\nabla f({\bf
w}^{t})\|^{2}+\frac{1}{2}\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbb{E}_{t}\|\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})-\nabla
f_{i}({\bf w}^{t})\|^{2}\right)$
$\displaystyle\leq\lambda\frac{1}{2m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbb{E}_{t}\|\mathbf{\nabla}f_{i}(\breve{\mathbf{x}}_{i,k}^{t})-\nabla
f_{i}(\mathbf{x}_{i}^{t})+\nabla f_{i}(\mathbf{x}_{i}^{t})-\nabla
f_{i}(\overline{\mathbf{x}^{t}})+\nabla
f_{i}(\overline{\mathbf{x}^{t}})-\nabla f_{i}({\bf w}^{t})\|^{2}$
$\displaystyle\quad+\frac{1}{2}\lambda\mathbb{E}\|\nabla f({\bf w}^{t})\|^{2}$
$\displaystyle\leq 3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbb{E}_{t}\|\breve{\mathbf{x}}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}+3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i}^{t}-\overline{\mathbf{x}^{t}}\|^{2}+3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{w}^{t}-\overline{\mathbf{x}^{t}}\|^{2}$
$\displaystyle\quad+\frac{1}{2}\lambda\mathbb{E}\|\nabla f({\bf w}^{t})\|^{2}$
$\displaystyle\leq 6\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\sum_{k=0}^{K-1}\frac{\gamma_{k}}{\gamma}\mathbb{E}_{t}\|\mathbf{x}_{i,k}^{t}-\mathbf{x}_{i}^{t}\|^{2}+3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i}^{t}-\overline{\mathbf{x}^{t}}\|^{2}+3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{w}^{t}-\overline{\mathbf{x}^{t}}\|^{2}$
$\displaystyle\quad+\frac{1}{2}\lambda\mathbb{E}\|\nabla f({\bf
w}^{t})\|^{2}+6\rho^{2}\lambda L^{2}(\sigma_{l}^{2}+B^{2})$ $\displaystyle\leq
6\lambda L^{2}\mathbf{c}^{t}+3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{x}_{i}^{t}-\overline{\mathbf{x}^{t}}\|^{2}+3\lambda
L^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\mathbf{w}^{t}-\overline{\mathbf{x}^{t}}\|^{2}+\frac{1}{2}\lambda\mathbb{E}\|\nabla
f({\bf w}^{t})\|^{2}+6\rho^{2}\lambda L^{2}(\sigma_{l}^{2}+B^{2})$

(a) applies
$-\langle\mathbf{x},\mathbf{y}\rangle\leq\frac{1}{2}\bigl{(}\|\mathbf{x}\|^{2}+\|\mathbf{y}\|^{2}\bigr{)}$.According
to Lemma8,6 and 10, $\mathbf{R2.1}$ can be simplified to the following
expression:

$\displaystyle\mathbf{R2.1}$ $\displaystyle\leq 96\lambda
L^{2}\eta_{l}^{2}K^{2}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})+288\lambda
L^{2}\eta_{l}^{2}K^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+6\lambda L^{2}\frac{C_{2}}{(1-\psi)^{2}}$
$\displaystyle\quad+6\lambda^{3}L^{2}(\gamma-1)^{2}\left(1+(\frac{\gamma-1}{\gamma})^{2}\right)(\sigma_{l}^{2}+B^{2})+\frac{1}{2}\lambda\mathbb{E}\|\nabla
f({\bf w}^{t})\|^{2}+6\rho^{2}\lambda L^{2}(\sigma_{l}^{2}+B^{2})$

We have now completed the upper bound estimation for $\mathbf{R2.1}$. Then
$\mathbf{R2}$ can be simplified to the following expression:

$\displaystyle\mathbf{R2}$ $\displaystyle\leq 96\lambda
L^{2}\eta_{l}^{2}K^{2}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})+288\lambda
L^{2}\eta_{l}^{2}K^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}+6\lambda L^{2}\frac{C_{2}}{(1-\psi)^{2}}$
$\displaystyle\quad+6\lambda^{3}L^{2}(\gamma-1)^{2}\left(1+(\frac{\gamma-1}{\gamma})^{2}\right)(\sigma_{l}^{2}+B^{2})-\frac{1}{2}\lambda\mathbb{E}\|\nabla
f({\bf w}^{t})\|^{2}+6\rho^{2}\lambda L^{2}(\sigma_{l}^{2}+B^{2})$

#### Bounded Global Gradient

As we have bounded the term $\mathbf{R1}$ and $\mathbf{R2}$, according to the
smoothness inequality, we combine the inequalities above and get the
inequality:

$\displaystyle\mathbb{E}_{t}f({\bf w}^{t+1})$
$\displaystyle\leq\mathbb{E}_{t}f({\bf w}^{t})+\mathbf{R1}+\mathbf{R2}$
$\displaystyle\leq\mathbb{E}_{t}f({\bf w}^{t})+96\lambda
L^{2}\eta_{l}^{2}K^{2}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})+288\lambda
L^{2}\eta_{l}^{2}K^{2}\frac{1}{m}\sum_{i\in[m]}\mathbb{E}_{t}\|\nabla
f(\mathbf{x}_{i}^{t})\|^{2}$
$\displaystyle\quad+6\lambda^{3}L^{2}(\gamma-1)^{2}\left(1+(\frac{\gamma-1}{\gamma})^{2}\right)(\sigma_{l}^{2}+B^{2})-\frac{1}{2}\lambda\mathbb{E}\|\nabla
f({\bf w}^{t})\|^{2}+\frac{L}{2}\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\quad+6\lambda L^{2}\frac{C_{2}}{(1-\psi)^{2}}+6\rho^{2}\lambda
L^{2}(\sigma_{l}^{2}+B^{2})$

Furthermore, with Lemma 8, we can get

$\begin{split}\frac{1}{m}\sum_{i=1}^{m}\mathbb{E}_{t}\left\|\nabla
f(\mathbf{x}_{i}^{t})\right\|^{2}&\leq
2L^{2}\frac{\sum_{i=1}^{m}\left\|\mathbf{x}_{i}^{t}-\overline{\mathbf{x}^{t}}\right\|^{2}}{m}+2\mathbb{E}_{t}\left\|\nabla
f(\overline{\mathbf{x}^{t}})-\nabla f({\bf w}^{t})+\nabla f({\bf
w}^{t})\right\|^{2}\\\
&{\leq}4L^{2}\frac{C_{2}}{(1-\psi)^{2}}+4L^{2}\mathbb{E}_{t}\|\overline{\mathbf{x}^{t}}-\mathbf{w}^{t}\|^{2}+4\mathbb{E}_{t}\left\|\nabla
f({\bf w}^{t})\right\|^{2}\\\
&\overset{(a)}{\leq}4L^{2}\frac{C_{2}}{(1-\psi)^{2}}+8L^{2}\lambda^{2}(\gamma-1)^{2}\left(1+\frac{(\gamma-1)^{2}}{\gamma^{2}}\right)(\sigma_{l}^{2}+B^{2})\\\
&\quad+4\mathbb{E}_{t}\left\|\nabla f({\bf w}^{t})\right\|^{2}\\\ \end{split}$
(23)

(a) applies lemma10.

Therefore, we have:

$\displaystyle\mathbb{E}_{t}f({\bf w}^{t+1})\leq\mathbb{E}_{t}f({\bf
w}^{t})+\mathbf{R1}+\mathbf{R2}$ $\displaystyle\leq\mathbb{E}_{t}f({\bf
w}^{t})-(\frac{1}{2}-1152L^{2}\eta_{l}^{2}K^{2})\lambda\mathbb{E}\|\nabla
f({\bf w}^{t})\|^{2}+96\lambda
L^{2}\eta_{l}^{2}K^{2}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})$
$\displaystyle\quad+6\lambda^{3}L^{2}(1+384L^{2}\eta_{l}^{2}K^{2})(\gamma-1)^{2}\left(1+(\frac{\gamma-1}{\gamma})^{2}\right)(\sigma_{l}^{2}+B^{2})+\frac{L}{2}\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\quad+6\lambda
L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\frac{C_{2}}{(1-\psi)^{2}}+6\rho^{2}\lambda
L^{2}(\sigma_{l}^{2}+B^{2})$
$\displaystyle\overset{(a)}{\leq}\mathbb{E}_{t}f({\bf
w}^{t})-(\frac{1}{2}-1152L^{2}\eta_{l}^{2}K^{2})\lambda\mathbb{E}\|\nabla
f({\bf w}^{t})\|^{2}+96\lambda
L^{2}\eta_{l}^{2}K^{2}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})$
$\displaystyle\quad+3\lambda^{3}L^{2}(1+384L^{2}\eta_{l}^{2}K^{2})(\sigma_{l}^{2}+B^{2})+\frac{L}{2}\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\quad+6\lambda
L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\frac{C_{2}}{(1-\psi)^{2}}+6\rho^{2}\lambda
L^{2}(\sigma_{l}^{2}+B^{2})$

Where (a) uses following condition to bound $\gamma$:

Firstly we should note that $\gamma=1-(1-\frac{\eta_{l}}{\lambda})^{K}<1$ when
$\eta_{l}\leq 2\lambda$. Thus we have $1/\gamma>1$. When $K$ satisfies that
$K\geq\frac{\lambda}{\eta_{l}}$, $(1-\frac{\eta_{l}}{\lambda})^{K}\leq
e^{-\frac{\eta_{l}}{\lambda}K}\leq e^{-1}$, and then $\gamma>1-e^{-1}$ and
$1/\gamma<\frac{e}{e-1}<2$.

We denote the constant
$\lambda\kappa=\lambda(\frac{1}{2}-1152L^{2}\eta_{l}^{2}K^{2})$ and $\kappa$
could be considered as a constant. We can select
$\eta_{l}<\frac{\sqrt{1-2c_{1}}}{48\sqrt{2}LK}$. Then we can bound the
$\kappa=\frac{1}{2}-1152L^{2}\eta_{l}^{2}K^{2}>c_{1}>0$, and the term
$\frac{1}{\kappa}<\frac{1}{c_{1}}$ which is a constant upper bound. Specially,
we can let $c_{1}=\frac{1}{4}$ ,then $\eta_{l}<\frac{1}{96LK}$ and
$\frac{1}{\kappa}<4$.

We can obtain the following expression by rearranging the terms:

$\displaystyle\lambda\kappa\mathbb{E}_{t}\|\nabla f({\bf w}^{t})\|^{2}$
$\displaystyle\leq\left(\mathbb{E}_{t}f({\bf w}^{t})-\mathbb{E}_{t}f({\bf
w}^{t+1})\right)+96\lambda
L^{2}\eta_{l}^{2}K^{2}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})$
$\displaystyle\quad+3\lambda^{3}L^{2}(1+384L^{2}\eta_{l}^{2}K^{2})(\sigma_{l}^{2}+B^{2})+\frac{L}{2}\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\quad+6\lambda
L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\frac{C_{2}}{(1-\psi)^{2}}+6\rho^{2}\lambda
L^{2}(\sigma_{l}^{2}+B^{2})$

Take the full expectation and telescope sum on the inequality above and
applying the fact that $f^{*}\leq f(\mathbf{x})$ for
$\mathbf{x}\in\mathbb{R}^{d}$, we have:

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{t}\|\nabla
f(\mathbf{w}^{t})\|^{2}$
$\displaystyle\leq\frac{f(\mathbf{w}^{0})-f^{*}}{\lambda\kappa
T}+\frac{96L^{2}\eta_{l}^{2}K^{2}}{\kappa}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})$
$\displaystyle\quad+\frac{3\lambda^{2}L^{2}(1+384L^{2}\eta_{l}^{2}K^{2})}{\kappa}(\sigma_{l}^{2}+B^{2})+\frac{L\lambda}{2\kappa}\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\quad+\frac{6L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)}{\kappa}\frac{C_{2}}{(1-\psi)^{2}}+\frac{6\rho^{2}\lambda
L^{2}}{\kappa}(\sigma_{l}^{2}+B^{2})$

Where
$C_{2}=16\eta_{l}^{2}K^{2}\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)+\lambda^{2}\left(\sigma_{l}^{2}+B^{2}\right)$.

Here we summarize the conditions and some constrains in the above conclusion.
Firstly we should note that $\gamma=1-(1-\frac{\eta_{l}}{\lambda})^{K}<1$ when
$\eta_{l}\leq 2\lambda$. Thus we have $1/\gamma>1$. When $K$ satisfies that
$K\geq\frac{\lambda}{\eta_{l}}$, $(1-\frac{\eta_{l}}{\lambda})^{K}\leq
e^{-\frac{\eta_{l}}{\lambda}K}\leq e^{-1}$, and then $\gamma>1-e^{-1}$ and
$1/\gamma<\frac{e}{e-1}<2$. To let
$\kappa=\frac{1}{2}-1152L^{2}\eta_{l}^{2}K>\frac{1}{4}>0$ hold, $\eta_{l}$
satisfy that $0<\eta_{l}<\frac{1}{96KL}$.

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{t}\|\nabla
f(\mathbf{w}^{t})\|^{2}$
$\displaystyle\leq\frac{f(\mathbf{w}^{0})-f^{*}}{\lambda\kappa
T}+\frac{96L^{2}\eta_{l}^{2}K^{2}}{\kappa}(3\sigma_{g}^{2}+2\sigma_{l}^{2}+B^{2})$
$\displaystyle\quad+\frac{3\lambda^{2}L^{2}(1+384L^{2}\eta_{l}^{2}K^{2})}{\kappa}(\sigma_{l}^{2}+B^{2})+\frac{L\lambda}{2\kappa}\left(\sigma_{l}^{2}+B^{2}\right)$
$\displaystyle\quad+\frac{96\eta_{l}^{2}K^{2}L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\left(3\sigma_{g}^{2}+2\sigma_{l}^{2}+4B^{2}\right)}{\kappa(1-\psi)^{2}}$
$\displaystyle\quad+\frac{6\lambda^{2}L^{2}\left(1+192L^{2}\eta_{l}^{2}K^{2}\right)\left(\sigma_{l}^{2}+B^{2}\right)}{\kappa(1-\psi)^{2}}+\frac{6\rho^{2}\lambda
L^{2}}{\kappa}(\sigma_{l}^{2}+B^{2}).$