#  PersA-FL: Personalized Asynchronous Federated Learning

Mohammad Taha Toghania, Soomin Leeb, César A. Uribea This work was partly done
while MTT interning at Yahoo! Research. Part of this material is based upon
work supported by the National Science Foundation under Grants #2211815 and
No. #2213568. Corresponding Author’s Email<EMAIL_ADDRESS>aDepartment of
Electrical and Computer Engineering, Rice University, Houston, TX, USA bYahoo!
Research, Sunnyvale, California, USA

###### Abstract

We study the personalized federated learning problem under asynchronous
updates. In this problem, each client seeks to obtain a personalized model
that simultaneously outperforms local and global models. We consider two
optimization-based frameworks for personalization: (i) Model-Agnostic Meta-
Learning (MAML) and (ii) Moreau Envelope (ME). MAML involves learning a joint
model adapted for each client through fine-tuning, whereas ME requires a bi-
level optimization problem with implicit gradients to enforce personalization
via regularized losses. We focus on improving the scalability of personalized
federated learning by removing the synchronous communication assumption.
Moreover, we extend the studied function class by removing boundedness
assumptions on the gradient norm. Our main technical contribution is a unified
proof for asynchronous federated learning with bounded staleness that we apply
to MAML and ME personalization frameworks. For the smooth and non-convex
functions class, we show the convergence of our method to a first-order
stationary point. We illustrate the performance of our method and its
tolerance to staleness through experiments for classification tasks over
heterogeneous datasets.

###### keywords:

Federated Learning; Personalization; Asynchronous Communication; Heterogeneous
Data; Distributed Optimization; Staleness.

##  1 Introduction

Federated Learning (FL) is designed to facilitate distributed training of
machine learning models across devices by exploiting the data and computation
power available to them [39, 38]. A major benefit of FL is its ability to
allow training models on data distributed across multiple devices without
centralization. This is particularly beneficial in situations with limited
sensitive data [32, 33] where clients are reluctant to share their private
data. At the same time, it is known that training over a larger set of data
points improves the quality of the obtained model [68]. In such scenarios, FL
enjoys the power of collaborative learning without relocating the data from
its original source [32]. Nevertheless, FL poses challenges such as data
heterogeneity (statistical diversity among clients) [34, 17, 11], fairness
[14, 43], privacy [24, 69, 30, 55], unreliable communication [61, 64], and
staleness [70, 3, 44, 53].

The common underlying assumption that determines the superiority of FL to
individual local training is that the data points of all clients are coming
from the same distribution, i.e., homogeneous data across clients.
Consequently, FL can improve the quality of empirical loss minimization when
data available on each device is limited; otherwise, each client may obtain a
proper model without collaboration or communication with others. Therefore,
vanilla FL111We refer to Federated Learning with no personalization as vanilla
FL. results in a common global model with better generalization across clients
[46] compared to individual training. In heterogeneous data setups where
clients hold samples from non-identical data distributions, a common (global)
model may perform poorly on the local data points of each client. For
instance, consider the next word prediction task on a smart keyboard [28],
where each client has a unique writing style or emphasis on the vocabulary
domain. In this example, the corresponding mobile application is supposed to
suggest a set of words that will likely be selected as the next word in the
sentence. This scenario clearly states a case with a heterogeneous data setup
with a limited sample on each client’s device. Thus, if each client trains a
model independently, without collaboration with the other clients, the model
will likely perform poorly on the new data due to sample limitation. Hence,
the question arises about what will occur if the clients hold data samples
from similar (but not identical) distributions.

In FL with heterogeneous data, an ideal scenario is to learn a globally common
model easily adaptable to local data on each client, i.e., model fusion. This
approach is known as _Personalized Federated Learning_ (PFL), which strives to
exploit both the shared and unshared information from the data of all clients.
A solution to the model fusion in PFL is to apply transfer learning [73, 12]
(e.g., fine-tuning) on a jointly trained model under vanilla FL.
Interestingly, the centralized version of this problem has been extensively
studied in Meta-Learning [66] and Multi-Task Learning [50], where the goal is
to obtain a meta (global) model that with (potentially) minimal adaptation
performs well on multiple tasks. Particularly, Model-Agnostic Meta-Learning
(MAML) [21, 56] proposes an optimization-based formulation that aims to find
an initial meta-model with proper performance after applying one or a few
steps of (stochastic) gradient descent. The key property of MAML is its
ability to gauge fine-tuning during the learning process. Multiple studies
have been conducted on the convergence and generalization of MAML [16, 31, 22,
18, 19, 8] for various problems and setups. Fallah et al. [17] suggest the
MAML formulation as a potential solution for PFL, and propose Per-FedAvg
algorithm for collaborative learning with MAML personalized cost function.
Dinh et al. [13] present pFedMe algorithm for PFL via adopting a different
formulation for personalization, namely Moreau Envelopes (ME). The proposed
algorithm is a joint bi-level optimization problem with personalized
parameters which are regularized to be close to the global model. We will
elaborate on these two formulations (MAML & ME) in Section 2. Additionally,
several recent works have approached PFL mainly through optimization-based
[26, 45, 64, 27, 29, 46, 72, 20, 58, 10, 5, 23], or structure-based [9, 65,
60] techniques.

Scalability to large-scale setups with potentially many clients is another
major challenge for FL. The proposed algorithms in this scheme, mostly require
synchronous communications between the server and clients [47, 39, 23, 58, 10,
43, 17, 13]. Such constraints impose considerable delays on the learning
progress, since increasing the concurrency in synchronous updates decreases
the training speed and quality. For example, limited communication bandwidth,
computation power, and communication failures incur large delays in the
training process. In cross-device FL, devices are naturally prone to update
and communicate models under less restrictive rules, whereas clients may apply
updates in an asynchronous fashion, i.e., staleness. Hogwild! [52] is one of
the first efforts to model asynchrony in distributed setup with delayed
updates. Multiple works have studied asynchronous training under different
setups and assumptions [1, 49, 6, 53, 44, 4, 15]. Specifically, some recent
seminal works have studied the convergence of asynchronous SGD-based methods,
and show their convergence under certain assumptions on maximum or average
delay [2, 62, 37, 48].222Mishchenko et al. [48] studies the convergence of
distributed optimization for homogeneous strongly convex and smooth functions
with no assumptions on maximum delay, i.e., unbounded staleness. In
decentralized setups, Hadjicostis et al. [25] propose a consensus algorithm
called running-sum, which is robust to message losses. Furthermore, Olshevsky
et al. [54] present a more general framework with robustness to asynchrony,
message losses, and delays for both consensus and optimization problems [61,
64]. More closely, FL under stale updates has been thoroughly studied in [70,
51, 3, 57, 41, 65]. Particularly, Tziotis et al. [65] studies the existence of
stragglers in PFL via shared representations, i.e., system and data
heterogeneity in structure-based personalization.

In this work, we study the PFL problem under asynchronous communications to
improve training concurrency, performance, and efficiency. We propose the
PersA-FL algorithm, a novel personalized & asynchronous method that jointly
addresses the heterogeneity and staleness in FL. We develop a technique based
on asynchronous updates to resolve the communication bottleneck imposed by
synchronized learning in PFL, where we improve the training scalability and
performance. To the best of our knowledge, this is the first study on the
intersection of staleness and personalization through the lens of
optimization-based techniques. We summarize our contributions as follows:

  * •

Through the integration of two personalization formulations, MAML & ME, we
propose PersA-FL, an algorithm that allows personalized federated learning
under asynchronous communications with the server. Our proposed method
consists of two algorithms from the perspectives of the server and clients. We
present the client algorithm under three different options for the local
updates, each addressing a separate formulation, (A) vanilla AFL, (B) PersA-
FL: MAML, and (C) PersA-FL: ME.

  * •

We present a new convergence analysis of vanilla Asynchronous Federated
Learning (AFL) for smooth non-convex cost functions by removing the
boundedness assumption from the gradient norm. Our analysis assumes bounded
variance of stochasticity and heterogeneity, and bounded maximum delay. Hence,
we improve the existing theory by extending the result to a broader function
class, i.e., unbounded gradient norm.

  * •

We show the convergence rate of PersAFL: MAML based on the maximum delay and
personalization budget under the same assumptions as Fallah et al. [17].333In
addition to the assumptions for AFL, seminal works [17, 22, 56] assume second-
order Lipschitzness, bounded variance, and bounded gradient in the analysis of
MAML cost functions. We highlight the impact of batch size in the biased
stochastic estimation of the full gradients for the MAML cost.

  * •

We prove the convergence of PersAFL: ME with no boundedness assumption on the
gradient norm. We discuss the connection of convergence rate to the gradient
estimation error and level of personalization. Compared to [13], we show an
explicit dependence of convergence rate to the estimation error. Moreover, we
relax the heterogeneity assumption in [13] allowing bounded population
diversity instead of uniformly bounded heterogeneity.

  * •

We present numerical experiments evaluating our proposed algorithm on
heterogeneous MNIST and CIFAR10 with unbalanced distributions across the
clients. We illustrate the advantages of our method in terms of performance
and scalability to varying delays in setups with heterogeneity.

Table 1 illustrates the properties of our proposed method and provides a
comparison between our algorithm and underlying analysis with some related
seminal works. As shown in this table, building upon the results in [17, 13],
we extend the capability of FL to staleness. Table 1 also contains the
convergence results for our proposed algorithm, which we will discuss in more
details in Section 4.

Table 1: Comparison of the characteristics considered in our work with
previous methods for federated learning with guaranteed convergence for smooth
non-convex functions. Parameters $\tau$, $\alpha$, $\nu$, and $b$ respectively
denote the maximum delay, MAML personalization stepsize, ME inexact gradient
estimation error, batch size.

Algorithm | & Reference |  Personalized Cost |  Asynchronous Updates |  Unbounded Gradient |  Convergence Rate
---|---|---|---|---|---
| McMahan et al. [47] | ✗ | ✗ | - | No Analysis
FedAvg | Yu et al. [71] | ✗ | ✗ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$
| Wang et al. [67] | ✗ | ✗ | ✓ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)$
FedAsync | Xie et al. [70] | ✗ | ✓ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$
FedBuff | Nguyen et al. [51] | ✗ | ✓ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$
Per-FedAvg | Fallah et al. [17] |  | ✓
---
✗ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\alpha^{2}}{b}\right)$
pFedMe | Dinh et al. [13] |  | ✓
---
✗ | ✓ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\lambda^{2}\left(\frac{1}{b}+\nu^{2}\right)}{(\lambda{-}L)^{2}}\right)$
| AFL | ✗ | ✓ | ✓ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)$
This Work | PersA-FL: MAML |  | ✓
---
✓ | ✗ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)+\mathcal{O}\left(\frac{\alpha^{2}}{b}\right)$
| PersA-FL: ME |  | ✓
---
✓ | ✓ | $\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)+\mathcal{O}\left(\frac{\lambda^{2}}{(\lambda{-}L)^{2}}\nu^{2}\right)$

The remainder of this paper is organized as follows. In Section 2, we
introduce the PFL setup and discuss the asynchronous communication framework
between the server and clients. In Section 3, we describe our algorithm,
PersA-FL, for PFL under staleness. In Section 4, we state the convergence
result for our proposed algorithm along with the underlying assumptions and
technical lemmas. We present the numerical experiments in Section 5. We
finally end by concluding remarks in Section 6.

##  2 Problem Setup & Background

In this section, we first present the formal problem setup for vanilla FL
[47], as well as the personalization formulations in MAML [17] and ME [13].
Then, we discuss the underlying communication setting under asynchronous
updates.

###  2.1 Federated Learning Problem Setup

We consider a set of $n$ clients and one server, where each client $i\in[n]$
holds a private function $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$, and the goal is
to collaboratively obtain a model $w\in\mathbb{R}^{d}$ that minimizes the
local cost functions on average, as follows:

$\displaystyle\begin{split}\min_{w\in\mathbb{R}^{d}}f(w)&\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(w),\\\
\text{with}\quad f_{i}(w)&\coloneqq\mathbb{E}_{\Xi_{i}\sim
p_{i}}[\ell_{i}(w,\Xi_{i})],\end{split}$ (1)

where $\ell_{i}:\mathbb{R}^{d}\times\mathcal{S}_{i}\to\mathbb{R}$ is a cost
function that determines the prediction error of some model
$w\in\mathbb{R}^{d}$ over a single data point $\xi_{i}\in\mathcal{S}_{i}$ on
client $i$, where $\xi_{i}$ is a realization of $\Xi_{i}\sim p_{i}$, i.e.,
$p_{i}$ is the client $i$’s data distribution over $\mathcal{S}_{i}$, for
$i\in[n]$. In the above definition, $f_{i}(\cdot)$ is the local cost function
of client $i$, and $f(\cdot)$ denotes the global cost function, i.e., average
loss. For instance, in a supervised learning setup with
$\mathcal{Z}_{i}\coloneqq\mathcal{X}_{i}\times\mathcal{Y}_{i}$, we have
$\ell_{i}(w,\xi_{i})$ as the prediction cost of some learning model
parameterized by $w$ for sample $\xi_{i}=(x,y)$, where $x\in\mathcal{X}_{i}$
and $y\in\mathcal{Y}_{i}$. Let $\mathcal{D}_{i}$ be a data batch with samples
independently drawn from the distribution $p_{i}$. Then, the unbiased
stochastic cost associated with data batch $\mathcal{D}_{i}$ can be denoted as
follows:

$\displaystyle\tilde{f}_{i}(w,\mathcal{D}_{i})$
$\displaystyle\coloneqq\frac{1}{|\mathcal{D}_{i}|}\sum\limits_{\xi_{i}\in\mathcal{D}_{i}}\ell_{i}(w,\xi_{i}),$
(2)

where for simplicity, we assume that the size of all batches is larger than
$b$. Then, according to the above definition, we can immediately infer that

$\displaystyle\begin{split}\mathbb{E}_{p_{i}}\left[\tilde{f}_{i}(w,\mathcal{D}_{i})\right]&=f_{i}(w),\\\
\mathbb{E}_{p_{i}}\left[\nabla\tilde{f}_{i}(w,\mathcal{D}_{i})\right]&=\nabla
f_{i}(w),\\\
\mathbb{E}_{p_{i}}\left[\nabla^{2}\tilde{f}_{i}(w,\mathcal{D}_{i})\right]&=\nabla^{2}f_{i}(w).\end{split}$
(3)

Several works have been proposed to solve (1) as a union of local and global
optimization steps. For instance, FedAvg [47] suggests an iterative algorithm
wherein at each round $t\geq 0$, (i) server transmits its current parameter
$w^{t}$ to a subset of the clients, (ii) each selected client updates the
parameter locally, by applying $Q$ sequential rounds of stochastic gradient
descent (SGD) with respect to its local cost function, then (iii) the selected
clients send back their local parameter to the server, and finally, (iv) the
server aggregates the so-called local parameters to obtain a new global
parameter $w^{t+1}$. As a result, clients minimize the average loss in (1)
with less communication cost, i.e., fewer global rounds. Note that the
underlying assumption for methods such as FedAvg is the possibility of
synchronized communications between the selected clients and the server. The
left chart in Figure 1 represents the communication and update schedule for
FedAvg. The performance of FL-based methods depends on the similarity of
distributions $\mathcal{D}_{i}$, thus, cases with heterogeneous datasets slow
down the convergence. Karimireddy et al. [34] and [11] the effect of
heterogeneity in the convergence speed. A solution of (1) is a common model
for all the clients; hence no adaptation or fusion to each client’s data.
Next, we elaborate on the personalization concept and discuss two alternative
problem formulations for (1).

###  2.2 Personalized Federated Learning

In the previous section, we explained how a solution to (1) performs well when
the data is homogeneous, and the goal is to obtain a shared model. On the one
hand, using a single common model, with no adaptation to each client, does not
necessarily lead to a proper performance when dealing with heterogeneous
datasets. On the other hand, when the data distributions of different clients
share some similarities, e.g., bounded variance in their heterogeneity, and
the number of data points on each client is limited, joint training with
fusion improves the performance compared to individual locally trained models
or vanilla FL. Therefore, learning a shared model with little fine-tuning,
e.g., a few steps of SGD with respect to the local cost, may result in a
proper personalized model.

Fallah et al. [17] proposed Per-FedAvg algorithm, which modifies the training
loss function by taking advantage of the fact that fine-tuning will occur
after training. The MAML formulation assumes a limited computational budget
for personalization (fine-tuning) at each client. It then offers to look for
an initial (global) parameter that performs well after it is updated with one
or a few steps of SGD. In other words, [17] define the MAML loss function for
PFL as follows:

$\displaystyle\begin{split}\min_{w\in\mathbb{R}^{d}}F^{(b)}(w)&\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}F^{(b)}_{i}(w),\\\
\text{with}\quad F^{(b)}_{i}(w)&\coloneqq f_{i}(w-\alpha\nabla
f_{i}(w)),\end{split}$ (4)

where $\alpha\geq 0$ is the MAML personalization stepsize. Solving (4) yields
a global (meta) model that can be used to create a personalized model by
applying one step of gradient descent with respect to individual loss
functions. The degree of fine-tuning determines the personalization budget,
which often controls the trade-off between having a local (personalized) or
generic model, i.e., exploiting the shared and local knowledge simultaneously.
In Problem (4), stepsize $\alpha$ determines the personalization budget, where
$\alpha=0$ implies vanilla FL in Problem (1). See [31, 64, 18] for the study
of multi-step MAML. In a nutshell, Per-FedAvg proposes to minimize
$F^{(b)}(w)$ via a similar paradigm as FedAvg. Hence, each client $i$ computes
the personalized gradient of its MAML cost in (4), which can be written as
follows:

$\displaystyle\nabla
F^{(b)}_{i}(w)=\left[I{-}\alpha\nabla^{2}f_{i}(w)\right]\nabla
f_{i}\left(w{-}\alpha\nabla f_{i}(w)\right),$ (5)

where in Per-FedAvg, the authors propose to compute a biased estimation of (5)
using stochastic gradients/Hessian. We will elaborate on the stochastic
approximation in Section 3.

On a separate note, one of the major challenges in Per-FedAvg is the
computation of second-order information such as Hessian for large-scale models
(large $d$). However, as proposed by [17], one can skip the Hessian in the
gradient formulation (FO-MAML) or approximate it with first-order information
(HF-MAML) [16].

As an alternative option to MAML formulation in (4), Dinh et al. [13] suggest
solving the following optimization problem:

$\displaystyle\begin{split}\min_{w\in\mathbb{R}^{d}}F^{(c)}(w)&\coloneqq\frac{1}{n}\sum\limits_{i=1}^{n}F^{(c)}_{i}(w),\\\
\text{with}\quad
F^{(c)}_{i}(w)&\coloneqq\min_{\theta_{i}\in\mathbb{R}^{d}}\left[f_{i}(\theta_{i})+\frac{\lambda}{2}{\left\|\theta_{i}-w\right\|}^{2}\right],\end{split}$
(6)

where each function $F^{(c)}_{i}(w)$ is a local cost of personalized parameter
$\theta_{i}\in\mathbb{R}^{d}$ by using the Moreau Envelope as a regularized
loss function, and parameter $\lambda\geq 0$ determines the degree of
personalization. In this setup, $\lambda=0$ is equivalent to local training
with no collaboration and as $\lambda\to\infty$, the formulation in (6)
converges to vanilla FL in (1) with no personalization which is similar to the
case in (4) with $\alpha=0$. For non-extreme values of $\lambda$, the clients
jointly learn a global model $w$ and personalized parameters $\theta_{i}$,
which are regularized to remain close to $w$. Note that the gradient of
$F^{(c)}_{i}(w)$ can be written as follows (please check out Appendix C to see
the proof):

$\displaystyle\nabla F^{(c)}_{i}(w)$
$\displaystyle=\lambda\left(w-\hat{\theta}_{i}(w)\right),$ (7)
$\displaystyle\text{with}\quad\hat{\theta}_{i}(w)\coloneqq$
$\displaystyle\operatorname*{arg\,min}_{\theta_{i}\in\mathbb{R}^{d}}\left[f_{i}(\theta_{i})+\frac{\lambda}{2}{\left\|\theta_{i}-w\right\|}^{2}\right],$
(8)

where for large $\lambda$, $\hat{\theta}_{i}(w)$ is the exact solution to an
optimization problem. Therefore, solving (6) through a similar approach to
FedAvg or Per-FedAvg, itself requires minimizing Problem (8) which is
potentially intractable. Dinh et al. [13] propose a bi-level optimization
algorithm called pFedMe, to minimize the optimization problem in (6) by
alternating minimization over $\theta_{i}$ and $w$. The main idea behind
pFedMe is to integrating the computation of an inexact solution to (8) inside
an FL-type method. We will explain and use this inexact approximation in the
presentation of our method (Option C) in Section 3.

###  2.3 Asynchronous vs Synchronous Schedule

So far, we have discussed the three different formulations for collaborative
learning that we will consider in our method. As we described the FedAvg
algorithm in Subsection 2.1, at each round $t$, the parameter $w^{t}$, which
is the most recent version of the global parameter in the server, will be sent
to a subset of the clients. Then, the server halts the training process until
all selected clients receive this parameter, perform local updates, and
transmit their updates back to the server. This synchronization procedure
restricts the algorithm flow to the slowest client at each round.
Nevertheless, asynchronous updates and communications can be described in this
described framework.

Let us provide a comparison using the example in Figure 1 which illustrates
the communication and update schedule for synchronous (left) & asynchronous
(right) aggregations for $n=5$ clients in FL with $Q=3$ local updates. As
shown in this Figure, for every update at the server-lever under synchronized
updates (left figure), the server has to wait for all the selected clients.
Nevertheless, these clients build their local updates based on the recent
version of the server’s parameter. On the contrary, in the asynchronous
scenario (right figure), the server updates the global parameter once it
receives a new update from some client. The main challenge for the
asynchronous setup is the staleness between download and upload time from/to
the server. We design PersA-FL based on the second communication scenario.

Figure 1: Communication and update schedule for synchronous and asynchronous
aggregation: The demonstrated setup in this example contains $n=5$ clients
with $Q=3$ local updates.

##  3 Algorithm: AFL & PersA-FL

In this section, by integrating the problem formulations in (1), (4), and (6)
into a united format, we propose Algorithms 1 & 2 to solve these problems
under three different update choices at the client-level. We present our
method through two different perspectives, (i) server and (ii) client.

$\diamond$ Server Algorithm: Let us denote $w^{0}\in\mathbb{R}^{d}$ as the
initial parameter at the server, where the objective is to minimize the cost
function in either (1), (4), or (6). Each client $i\in[n]$ may communicate
with the server when the underlying connection is stable. Clients may request
to download the server’s parameters at any time, and the server will send the
most recent model after receiving the request. All underlying delays for the
communications between the server and clients are modeled as download and
upload delays. We consider variable $t$ as a counter for the updates at the
server level. Algorithm 1 represents the server updates in PersA-FL. The
server performs an iterative algorithm where at each round $t\geq 0$, remains
on hold until receives an update $\Delta_{i_{t}}\in\mathbb{R}^{d}$ from some
client $i_{t}\in[n]$. After receiving the update from client $i_{t}$, the
server updates its parameter according to Step 4 of Algorithm 1, where
$\beta\geq 0$ is the server stepsize.

Algorithm 1 [Personalized] Asynchronous Federated Learning (Server)

1:input: model $w^{0}$, $t=0$, server stepsize $\beta$.

2:repeat

3: if the server receives an update $\Delta_{i_{t}}$ from some client
$i_{t}{\in}[n]$ then

4: $w^{t+1}\leftarrow w^{t}-\beta\Delta_{i_{t}}$

5: $t\leftarrow t+1$

6: end if

7:until not converge

Algorithm 2 [Personalized] Asynchronous Federated Learning (Client $i$)

1:input: number of local steps $Q$, local stepsize $\eta$, MAML stepsize
$\alpha$, Moreau Envelope (ME) regularization parameter $\lambda$, minimum
batch size $b$, estimation error $\nu$.

2:repeat

3: read $w$ from the server $\triangleright$ download phase

4: $w_{i,0}\leftarrow w$

5: for $q=0$ to $Q{-}1$ do $\triangleright$ local updates

6: sample a data batch $\mathcal{D}_{i,q}$ from distribution $p_{i}$
$\triangledown$ 3 options:  7: $\triangleright$ Option A (AFL) 8:
$w_{i,q+1}\leftarrow
w_{i,q}-\eta\nabla\tilde{f}_{i}(w_{i,q},\mathcal{D}_{i,q})$ 9:
$\triangleright$ Option B (PersA-FL: MAML) 10: sample two data batches
$\mathcal{D}_{i,q}^{\prime},\mathcal{D}_{i,q}^{\prime\prime}$ from
distribution $p_{i}$ 11: $w_{i,q+1}\leftarrow
w_{i,q}-\eta\left[I{-}\alpha\nabla^{2}\tilde{f}_{i}(w_{i,q},\mathcal{D}_{i,q}^{\prime\prime})\right]\nabla\tilde{f}_{i}\left(w_{i,q}{-}\alpha\nabla\tilde{f}_{i}(w_{i,q},\mathcal{D}_{i,q}^{\prime}),\mathcal{D}_{i,q}\right)$
12: $\triangleright$ Option C (PersA-FL: ME) 13:
$\tilde{h}_{i}(\theta_{i},w_{i,q},\mathcal{D}_{i,q})\coloneqq\tilde{f}_{i}(\theta_{i},\mathcal{D}_{i,q})+\frac{\lambda}{2}\left\lVert\theta_{i}-w_{i,q}\right\rVert^{2}$
14: minimize $\tilde{h}_{i}(\theta_{i},w_{i,q},\mathcal{D}_{i,q})$ w.r.t.
$\theta_{i}$ up to accuracy level $\nu$ to find $\tilde{\theta}_{i}(w_{i,q})$:
$\left\lVert\nabla\tilde{h}_{i}\left(\tilde{\theta}_{i}(w_{i,q}),w_{i,q},\mathcal{D}_{i,q}\right)\right\rVert\leq\nu$
15: $w_{i,q+1}\leftarrow
w_{i,q}-\eta\lambda(w_{i,q}-\tilde{\theta}_{i}(w_{i,q}))$

16: end for

17: $\Delta_{i}\leftarrow w_{i,0}-w_{i,Q}$

18: client $i$ broadcasts $\Delta_{i}$ to the server$\triangleright$ upload
phase

19:until not interrupted by the server

Now, we are ready to present the client algorithm. Before starting, note that
we drop the time index from the iterates of the client algorithm for clarity
of exposition.

$\diamond$ Client Algorithm: Let us explain the operations of $i$-th client
using the pseudo code in Algorithm 2. Client $i$ repeats an iterative
procedure which is composed of three phases, (i) downloading the most up-to-
date model from the server as in Step 3, (ii) performing $Q$ local updates
starting from the parameters of the downloaded model with respect to the cost
function of the underlying problem, (1), (4), or (6), as in Steps 5-16, and
(iii) uploading the sum of updates on the server as in Step 18. Note that
$\eta\geq 0$ is the local stepsize, a hyperparameter. The main idea for the
local updates is to perform $Q$ sequential SGD steps on the local cost. Below,
we list our stochastic estimation for the full gradients of each loss function
introduced in Section 2:

  * •

Option A: This option intends to minimize (1). Therefore, for each client $i$
at each local round $q$, we sample an independent data batch from $p_{i}$ and
compute an unbiased estimation of the vanilla loss as in (2).

  * •

Option B: By performing this option, we aim to minimize the MAML cost function
in (4). As we saw in Section 2, the full gradient can be computed according to
(5). Following [17], we sample three data batches to compute a biased
estimation of (5) as follows:

$\displaystyle\nabla\tilde{F}^{(b)}_{i}(w,\mathcal{D}_{i}^{\prime\prime},\mathcal{D}_{i}^{\prime},\mathcal{D}_{i})=\left[I{-}\alpha\nabla^{2}\tilde{f}_{i}(w,\mathcal{D}_{i}^{\prime\prime})\right]\nabla\tilde{f}_{i}\left(w{-}\alpha\nabla\tilde{f}_{i}(w,\mathcal{D}_{i}^{\prime}),\mathcal{D}_{i}\right).$
(9)

We will discuss the variance and bias of this estimator in Subsection 4.2

  * •

Option C: Finally, we invoke this option to minimize the ME personalized loss
in (6). As we mentioned earlier, the full gradient of this cost is (7), where
for a fixed $w$, we may obtain $\hat{\theta}_{i}(w)$ by minimizing (8).
Instead, following [13], we define the stochastic approximation
$\tilde{h}_{i}(\theta_{i},w,\mathcal{D}_{i})$ as in Step 14, and minimize this
function with respect to $\theta_{i}$ to obtain an approximate solution
$\tilde{\theta}_{i}(w)$ where the gradient’s norm is less than some threshold
$\nu\geq 0$. Therefore, we approximate (7) with the following estimator:

$\displaystyle\nabla\tilde{F}^{(c)}_{i}(w,\mathcal{D}_{i})=\lambda\left(w-\tilde{\theta}_{i}(w)\right).$
(10)

Let us denote the expectation of $\tilde{h}_{i}(.)$ as $h_{i}(.)$. Then, for
$\lambda>L$, the expected function is $(\lambda{+}L)$-smooth and
$(\lambda{-}L)$-strongly convex due to the properties of Moreau Envelopes
[13]. Then according to the property of [7, 13], for some $\nu\leq 1$ (e.g.,
$10^{{-}5}$), we can find $\tilde{\theta}_{i}(w)$ in
$\mathcal{O}(\frac{\lambda{+}L}{\lambda{-}L}\log(\frac{1}{\nu}))$ iterations.

We will also discuss the properties of (10) in Subsection 4.3.

Next, we present the convergence result of our method for the three
formulations.

##  4 Convergence Results

In this section, we introduce the technical theorems and lemmas to show the
convergence of our method for the three described scenarios. First, we
introduce the common assumptions we will use in our analysis for all the three
choices of Algorithm 2. As mentioned earlier, we require some additional
assumptions to show the convergence of MAML, which we will introduce in
Subsection 4.2. After stating the assumptions, we will present the convergence
results.

Recall that the server updates its model at round $t$ using the updates sent
by client $i_{t}\in[n]$. We denote $\Omega(t)$ as the timestep of the round at
which client $i_{t}$ has received the server’s parameters before applying its
$Q$ local updates. In other words, $(\Omega(t),t)$ denote the download and
upload rounds for client $i_{t}$. Now, we introduce the assumption of maximum
delay.

######  Assumption 1 (Bounded Staleness).

For all server steps $t\geq 0$, the staleness or effective delay between the
model version at the download step $\Omega(t)$ and upload step $t$ is bounded
by some constant $\tau$, i.e.,

$\displaystyle\sup_{t\geq 0}\left|t-\Omega(t)\right|\leq\tau,$ (11)

and the server receives updates uniformly, i.e.,
$i_{t}\sim\mathrm{Uniform}([n])$.

The above assumption is standard in the analysis of asynchronous methods,
specifically in heterogeneous settings [51, 70, 3, 37, 62, 2]. Assumption 1
guarantees that all clients remain active over the course of training.
However, they have transient delays and perform updates with staleness.

Next, we present our only assumption on the function class, i.e., smooth non-
convex.

######  Assumption 2 (Smoothness).

For all clients $i\in[n]$, function $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$ is
bounded below, differentiable, and $L$-smooth, i.e., for all
$w,u\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\nabla f_{i}(w)-\nabla f_{i}(u)\right\rVert\leq
L\lVert w-u\rVert$ (12) $\displaystyle
f_{i}^{\star}\coloneqq\min_{w\in\mathbb{R}^{d}}f_{i}(w)>-\infty.$ (13)

The smoothness assumption is conventional in the analysis of non-convex
functions. We also assume boundedness from below, which is reasonable since
the ultimate goal is to minimize the functions. We also denote
$f^{\star}=\min_{i\in[n]}f_{i}^{\star}$, where according to this definition,
we can immediately see that $f^{\star}\leq\min_{w\in\mathbb{R}^{d}}F^{(b)}(w)$
and $f^{\star}\leq\min_{w\in\mathbb{R}^{d}}F^{(c)}(w)$.

Now, we present our assumptions on bounded stochasticity and heterogeneity.

######  Assumption 3 (Bounded Variance).

For all clients $i\in[n]$, the variance of a stochastic gradient
$\nabla\ell_{i}(w,\xi_{i})$ on a single data point $\xi_{i}\in\mathcal{S}_{i}$
is bounded, i.e., for all $w\in\mathbb{R}^{d}$

$\displaystyle\mathbb{E}_{\xi_{i}\sim
p_{i}}\left\lVert\nabla\ell_{i}(w,\xi_{i})-\nabla
f_{i}(w)\right\rVert^{2}\leq\sigma_{g}^{2}.$ (14)

Assumption 3 is standard in the analysis of SGD-based methods and has been
used in many relevant works [63, 51, 35, 67, 36, 37, 64]. Since we perform
updates using data batches, we also need to show the stochastic variance for
the sampled batches. Recall that for simplicity; we assumed that all batch
sizes are larger than $b\geq 1$, thus, we have:

$\displaystyle\mathbb{E}_{p_{i}}\left\lVert\nabla\tilde{f}_{i}(w,\mathcal{D}_{i})-\nabla
f_{i}(w)\right\rVert^{2}\leq\frac{\sigma_{g}^{2}}{|\mathcal{D}_{i}|}\leq\sigma_{a}^{2}\coloneqq\frac{\sigma_{g}^{2}}{b}$
(15)

Next, we present the bounded heterogeneity assumption.

######  Assumption 4 (Bounded Population Diversity).

For all $w\in\mathbb{R}^{d}$, the gradients of local functions $f_{i}(w)$ and
the global function $f(w)$ satisfy the following property:

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\lVert\nabla f_{i}(w)-\nabla
f(w)\rVert^{2}\leq\gamma_{g}^{2}.$ (16)

The above assumption measures the population diversity (heterogeneity) between
the gradients. In heterogeneous settings, this bound indicates the similarity
between different distributions. Fallah et al. [17] show connections between
heterogeneity and the Wasserstein distance between the distributions under
certain assumptions.

The above assumptions are sufficient to prove the convergence of our method
(Algorithms 1 & 2) under Option A and Option C. Therefore, we present the
convergence analyses starting from our results on AFL.

###  4.1 Asynchronous Federated Learning (Option A)

We now demonstrate the convergence rate of our method for the cost function in
(1).

######  Theorem 1 (AFL).

Let Assumptions 1-4 hold, $\beta=1$, and $\eta=\frac{1}{Q\sqrt{LT}}$. Then,
the following property holds for the joint iterates of Algorithms 1 & 2 under
Option A on Problem (1): for any timestep $T\geq 160L(Q{+}7)(\tau{+}1)^{3}$ at
the server

$\displaystyle\frac{1}{T}\sum_{t=0}^{T-1}\,\mathbb{E}\left\lVert\nabla
f\left(w^{t}\right)\right\rVert^{2}$
$\displaystyle\leq\frac{4\sqrt{L}\left(f(w^{0})-f^{\star}\right)}{\sqrt{T}}+\frac{8\sqrt{L}\left(\frac{\sigma_{g}^{2}}{b}+\gamma_{g}^{2}\right)}{\sqrt{T}}$
$\displaystyle+\frac{80L(1{+}Q)(\tau^{2}{+}1)\left(\frac{\sigma_{g}^{2}}{b}+\gamma_{g}^{2}\right)}{T}.$

The proof of Theorem 1 is provided in Appendix A. This theorem suggests a
convergence rate of
$\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{Q\tau^{2}}{T}\right)$
for asynchronous federated learning AFL. Our analysis removes the unnecessary
boundedness assumption on the gradient norm.

######  Remark 1.

Selecting $\beta=1$ in Theorem 1, results in a sub-optimal first-order
stationary rate for smooth non-convex cost functions. However, this is an
arbitrary choice for the value of $\beta$ and can be relaxed to any
$\beta=\mathcal{O}(1)$ similar to [51].

Next, we present the convergence of PersA-FL: MAML along with some technical
lemmas borrowed from [17].

###  4.2 Personalized Asynchronous Federated Learning: Model-Agnostic Meta-
Learning Setup (Option B)

As we discussed in Section 3, we require the second-order derivatives of the
local functions to compute the gradients of the personalized costs in (4).
Accordingly, we consider similar assumptions for the second-order derivatives
as Assumptions 2-4.

######  Assumption 5 (Second-Order Properties).

For all clients $i\in[n]$, the following properties hold for the Hessian of
each $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$, the variance of a stochastic Hessian
$\nabla^{2}\ell_{i}(w,\xi_{i})$ on a single data point
$\xi_{i}\in\mathcal{S}_{i}$, and the global Hessian $\nabla^{2}f(w)$: for all
$w,u\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\nabla^{2}f_{i}(w)-\nabla^{2}f_{i}(u)\right\rVert\leq\rho\lVert
w-u\rVert,$ (17) $\displaystyle\mathbb{E}_{\xi_{i}\sim p_{i}}$
$\displaystyle\left\lVert\nabla^{2}\ell_{i}(w,\xi_{i})-\nabla^{2}f_{i}(w)\right\rVert^{2}\leq\sigma_{h}^{2},$
(18) $\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}$
$\displaystyle\left\lVert\nabla^{2}f_{i}(w)-\nabla^{2}f(w)\right\rVert^{2}\leq\gamma_{h}^{2}.$
(19)

Assumption 5 is conventional in the analysis of methods with access to second-
order information [16, 17, 59, 64]. Finally, we adopt another assumption from
[22, 17, 19] on the gradient norm to simplify the analysis for the MAML cost.

######  Assumption 6 (Bounded-Gradient).

There exists a constant $G$ such that for all clients $i\in[n]$, and any
parameter $w\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\nabla f_{i}(w)\right\rVert\leq G.$ (20)

To the best of our knowledge, seminal works on MAML loss mainly consider this
assumption to simplify the properties of the personalized function. Note that
we consider Assumptions 5-6 only in the analysis of PersA-FL (Algorithms 1 &
2) under Option B. Under Assumptions 2 and 6, the properties in (19) and (16)
can be simply derived with $\gamma_{h}=2L$ and $\gamma_{g}=2G$ [17].

Before stating the convergence of PersA-FL: MAML, let us state some technical
lemmas on the personalized MAML cost function.

######  Lemma 1 ([17], Lemma 4.2 - Smoothness: MAML).

Let Assumptions 2 and 6 hold. Then, $F^{(b)}_{i}$ in (4) is $L_{b}$-smooth,
i.e., for all clients $i\in[n]$, and any parameters $w,u\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\nabla F^{(b)}_{i}(w)-\nabla
F^{(b)}_{i}(u)\right\rVert\leq L_{b}\lVert w-u\rVert,$ (21)

where $L_{b}\coloneqq L(1{+}\alpha L)^{2}+\alpha\rho G$.

Lemma 1 indicates that the personalized cost in (4) is also smooth. The
smoothness parameter $L_{b}$ depends on the personalization hyperparameter
$\alpha$. Increasing the value of $\alpha$ results in higher smoothness
constant $L_{b}$. The smoothness property of MAML cost under multi-step
personalization (instead of one) is shown in [64][Lemma 3].

######  Lemma 2 ([17], Lemma 4.3 - Bounded Variance: MAML).

Let Assumptions 2, 3, 5, and 6 hold, and data batches
$\mathcal{D},\mathcal{D}^{\prime},\mathcal{D}^{\prime\prime}$ be randomly
sampled according to data distribution $p_{i}$. Then, the following properties
hold for the stochastic personalized gradient
$\nabla\tilde{F}^{(b)}_{i}(w,\mathcal{D}^{\prime\prime},\mathcal{D}^{\prime},\mathcal{D})$:

$\displaystyle\left\lVert\mathbb{E}_{p_{i}}\left[\nabla\tilde{F}^{(b)}_{i}(w,\mathcal{D}^{\prime\prime},\mathcal{D}^{\prime},\mathcal{D})-\nabla
F^{(b)}_{i}(w)\right]\right\rVert$
$\displaystyle\leq\mu_{b}\coloneqq\frac{\alpha L(1{+}\alpha
L)\sigma_{g}}{\sqrt{b}},$ (22)
$\displaystyle\mathbb{E}_{p_{i}}\left\lVert\nabla\tilde{F}^{(b)}_{i}(w,\mathcal{D}^{\prime\prime},\mathcal{D}^{\prime},\mathcal{D})-\nabla
F^{(b)}_{i}(w)\right\rVert^{2}$ $\displaystyle\leq\sigma_{b}^{2},$ (23)

for all $w\in\mathbb{R}^{d}$, where $\sigma_{b}^{2}\coloneqq 3(1{+}\alpha
L)^{2}\sigma_{g}^{2}\left[\frac{1}{b}{+}\frac{\alpha^{2}L^{2}}{b}\right]+3\alpha^{2}G^{2}\frac{\sigma_{h}^{2}}{b}+\frac{3\alpha^{2}\sigma_{g}^{2}\sigma_{h}^{2}}{b}\left[\frac{1}{b}{+}\frac{\alpha^{2}L^{2}}{b}\right]$.

Lemma 2 highlights two important results. First, the stochastic gradient in
(9) is a biased estimation of the full gradient 5. The biasness is controlled
by two factors, personalization stepsize $\alpha$, and batch size $b$.444It
should be noted that the batch size in the upper bound of (22) refers to the
size of $|\mathcal{D}^{\prime}|$. Recall that we use this batch to approximate
the inner gradient in 10. Therefore, we obtain an unbiased estimation under no
personalization, i.e., $\alpha=0$. However, as we select a larger $\alpha$, we
require more samples to reduce the error imposed by biased gradient
estimations. Second, similar to Assumption 3 on the vanilla cost; we have a
tight variance based on $\alpha$ and $b$.

######  Lemma 3 ([17], Lemma 4.4 - Bounded Population Diversity: MAML).

For all $w\in\mathbb{R}^{d}$, the gradients of local personalized functions
$F^{(b)}_{i}(w)$ and the global function $F^{(b)}(w)$ satisfy the following
property:

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\nabla
F^{(b)}_{i}(w)-\nabla F^{(b)}(w)\right\rVert^{2}\leq\gamma_{b}^{2}\coloneqq
12(1+\alpha
L)^{2}\left[1+\alpha^{2}L^{2}\right]\gamma_{g}^{2}+12\alpha^{2}G^{2}\gamma_{h}^{2}.$
(24)

The above lemma determines the heterogeneity of the personalized gradients
$\nabla F_{i}^{(b)}(w)$ based on the heterogeneity of gradient and Hessian.
One can see the connection of this bound with
$\mathcal{O}(\gamma_{g}^{2})+\alpha^{2}\mathcal{O}(\gamma_{h}^{2})$, whereby
setting $\alpha=0$, we recover the same heterogeneity in terms of
$\mathcal{O}(\cdot)$ notion.

######  Lemma 4 (Bounded-Gradient: MAML).

For all clients $i\in[n]$, and any parameter $w\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\nabla F^{(b)}_{i}(w)\right\rVert\leq
G_{b}\coloneqq(1{+}\alpha L)G.$ (25)

This lemma indicates that the bound on the norm of personalized gradients
potentially increases under a larger personalization budget $\alpha$.

Building upon the results in Lemmas 2-(25), we are now ready to present the
convergence result for PersA-FL: MAML.

######  Theorem 2 (PersA-FL: MAML).

Let Assumptions 1-6 hold, $\alpha\geq 0$, $\beta=1$, and
$\eta=\frac{1}{Q\sqrt{L_{b}T}}$. Then, the following property holds for the
joint iterates of Algorithms 1 & 2 under Option B on Problem (4): for any
timestep $T\geq 64L_{b}$ at the server

$\displaystyle\frac{1}{T}\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}$
$\displaystyle\leq\frac{4\sqrt{L_{b}}\left(F^{(b)}(w^{0})-f^{\star}\right)}{\sqrt{T}}+\frac{8\sqrt{L_{b}}\left(\sigma_{b}^{2}+\gamma_{b}^{2}\right)}{\sqrt{T}}$
$\displaystyle+\frac{20\,QL_{b}\left(G_{b}^{2}{+}\sigma_{b}^{2}\right)\left(\tau^{2}{+}1\right)}{T}+\frac{4\,Q\alpha^{2}L^{2}(1{+}\alpha
L)^{2}\sigma_{g}^{2}}{b}.$

The proof of this theorem can be found in Appendix B. Theorem 2 shows a
convergence rate of
$\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)+\mathcal{O}\left(\frac{\alpha^{2}\sigma_{g}^{2}}{b}\right)$
for PersA-FL algorithm under MAML setup. Now, let us compare this rate with
the convergence rate of AFL and Per-FedAvg, as in Table 1. The last term in
the above rate, i.e.,
$\mathcal{O}\left(\frac{\alpha^{2}\sigma_{g}^{2}}{b}\right)$ accounts for
personalization with biased gradient estimation. Moreover, compared to Per-
FedAvg, the second term of this rate is different, which accounts for the
maximum delay in asynchronous updates. For instance, under a fixed
personalization budget $\alpha\geq 0$, our method requires
$T=\mathcal{O}(\varepsilon^{-2})$ and $b=\mathcal{O}(\varepsilon^{-1})$ to
reach an $\varepsilon$-approximate first-order stationary solution. The last
expression can also be controlled through a combined stepsize $\alpha$ and
batch size $b$. It is consistent with intuition, meaning more samples are
needed to obtain a higher degree of personalization.

Next, we will present the analysis of PersA-FL: ME.

###  4.3 Personalized Asynchronous Federated Learning: Moreau Envelope Setup
(Option C)

In this subsection, we show three technical lemmas on the bounded variance of
stochasticity and heterogeneity as well as smoothness for ME formulation (6)
and then present the convergence rate of PersA-FL for this personalization
framework. The proof of all results in this subsection is provided in Appendix
C.

First, we present the smoothness property of ME loss.

######  Lemma 5 (Smoothness: ME).

Let Assumption 2 holds and $\lambda\geq\kappa L$ for some $\kappa>1$. Then,
$F^{(c)}_{i}$ in (6) is $L_{c}$-smooth, where
$L_{c}=\frac{\lambda}{\kappa{-}1}$.

According to Lemma 5, we limit our exploration to $\lambda>L$ which satisfies
the smoothness constraint for the ME formulation. In fact, according to
Appendix C, one can also see that originally, each $F^{(c)}_{i}(\cdot)$ is
$\frac{\lambda L}{\lambda{-}L}$-smooth which is also smaller than
$L_{c}=\frac{\lambda}{\kappa{-}1}$. As we mentioned in Section 2, when
$\lambda\to\infty$, ME framework converts to vanilla FL. The smoothness
property in Lemma 5 is tight because, $L_{c}\to L$ if $\lambda\to\infty$.

######  Corollary 1 ([13], Proposition 1).

If $\lambda\geq 2L$, then Lemma 5 implies that $F^{(c)}_{i}$ in (6) is
$\lambda$-smooth.

######  Lemma 6 (Bounded Variance: ME).

Let Assumptions 2 and 3 hold, $\lambda\geq\kappa L$ (for some $\kappa>1$), and
the data batch $\mathcal{D}$ be randomly sampled according to data
distribution $p_{i}$. Then, the following properties hold for the stochastic
personalized gradient $\nabla\tilde{F}^{(c)}_{i}(w,\mathcal{D})$: for all
$w\in\mathbb{R}^{d}$,

$\displaystyle\left\lVert\mathbb{E}_{p_{i}}\left[\nabla\tilde{F}^{(c)}_{i}(w,\mathcal{D})-\nabla
F^{(c)}_{i}(w)\right]\right\rVert$
$\displaystyle\leq\mu_{c}\coloneqq\frac{\lambda}{\lambda{-}L}\nu,$ (26)
$\displaystyle\mathbb{E}_{p_{i}}\left\lVert\nabla\tilde{F}^{(c)}_{i}(w,\mathcal{D})-\nabla
F^{(c)}_{i}(w)\right\rVert^{2}$
$\displaystyle\leq\sigma_{c}^{2}\coloneqq\frac{2\lambda^{2}}{\left(\lambda{-}L\right)^{2}}\left[\frac{\sigma_{g}^{2}}{b}+\nu^{2}\right].$
(27)

This lemma is analogous to Lemma 2 in Subsection 4.2. In Lemma 6, we show an
upper bound on the variance and bias of the stochastic gradient compared to
the full gradient. Note that when $\lambda\to\infty$, we know that
$\hat{\theta}_{i}(w)\to w$. Therefore, by fixing $\tilde{\theta}_{i}(w)=w$, it
is guaranteed that $\nu=0$, thus our gradient estimation becomes unbiased and
the variance similar to (15).

######  Lemma 7 (Bounded Population Diversity: ME).

Let personalization hyperparameter $\lambda\geq 7L$. Then, for all
$w\in\mathbb{R}^{d}$, the gradients of local personalized functions
$F^{(c)}_{i}(w)$ and the global ME function $F^{(c)}(w)$ satisfy the following
property:

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\nabla
F^{(c)}_{i}(w)-\nabla
F^{(c)}(w)\right\rVert^{2}\leq\gamma_{c}^{2}\coloneqq\frac{16\lambda^{2}}{\lambda^{2}{-}48L^{2}}\gamma_{g}^{2}.$
(28)

Lemma 7 provides a bound on population diversity of ME as a factor of
$\gamma_{g}^{2}$. Similar to what we explained so far, for $\lambda\to\infty$,
the heterogeneity bound turns into $\gamma_{g}^{2}$.

######  Remark 2.

In the analysis for Theorem 3, we consider bounded population diversity as in
Assumption 4, average bounded diversity. [13][Assumption 3] and [68][6.1.1
Assumptions and Preliminaries, (vii)] consider a slightly stronger version of
this assumption, namely uniformly “bounded heterogeneity” which is defined as
follows:

$\displaystyle\max_{i\in[n]}\sup_{w\in\mathbb{R}^{d}}\lVert\nabla
f_{i}(w)-\nabla f(w)\rVert^{2}\leq\gamma_{g}^{2}.$ (29)

Under the modified assumption in (29), we can improve
$\gamma_{c}^{2}\coloneqq\frac{16\lambda^{2}}{\lambda^{2}{-}8L^{2}}\gamma_{g}^{2}$.

Now, we present our convergence result of PersA-FL: ME under Assumption 1-4

######  Theorem 3 (PersA-FL: ME).

Let Assumptions 1-4 hold, $\lambda\geq 7L$, $\beta=1$, and
$\eta=\frac{1}{Q\sqrt{L_{c}T}}$. Then, the following property holds for the
joint iterates of Algorithms 1 & 2 under Option C on Problem (6): for any
timestep $T\geq 288L_{c}(Q{+}7)(\tau{+}1)^{2}$ at the server

$\displaystyle\frac{1}{T}\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
F^{(c)}(w^{t})\right\rVert^{2}$
$\displaystyle\leq\frac{4\sqrt{L_{c}}\left(F^{(c)}(w^{t})-f^{\star}\right)}{\sqrt{T}}+\frac{8\sqrt{L_{c}}\left(\sigma_{c}^{2}+\gamma_{c}^{2}\right)}{\sqrt{T}}$
$\displaystyle+\frac{144L_{c}(1{+}Q)(\tau^{2}{+}1)\left(\sigma_{c}^{2}+\gamma_{g}^{2}\right)}{T}+\frac{4Q\lambda^{2}\nu^{2}}{(\lambda{-}L)^{2}}.$

This theorem proposes a convergence rate of
$\mathcal{O}\left(\frac{1}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{\tau^{2}}{T}\right)+\mathcal{O}\left(\frac{\lambda^{2}\nu^{2}}{(\lambda{-}L)^{2}}\right)$
for PersA-FL under ME formulation. Again, under the exact same reasoning as
Lemma 6, we know that $\nu=0$ when $\lambda\to\infty$, thus the convergence
rate simply reduces to vanilla AFL with no personalization. Let us compare
this convergence rate with the rate of pFedMe [13] in Table 1. By comparing
the last terms in both rates,
$\mathcal{O}\left(\frac{\lambda^{2}\nu^{2}}{(\lambda{-}L)^{2}}\right)$ and
$\mathcal{O}\left(\frac{\lambda^{2}\left(\frac{1}{b}+\nu^{2}\right)}{(\lambda{-}L)^{2}}\right)$,
one can see that the additional term $\frac{1}{b}$ in the convergence rate of
pFedMe, implies that even under $\lambda\to\infty$, the last term does not
vanish unless with large data batches, i.e., $b=\mathcal{O}(\varepsilon)$.
Therefore, from the personalization perspective, our analysis provides a
tighter bound compared to pFedMe.

##  5 Numerical Experiments

In this section, we discuss the concurrency, speed-up, and accuracy of our
proposed method in heterogeneous settings under delayed communications.

Let us first start by explaining our simulation setup for communications with
delays. We consider a set of $n=50$ different clients, where each client holds
a set of random delays at the upload and download stage. We set the random
delays to be generated such that the upload delay is $4$ to $6$ times higher
than the download delay on average. We assume that the time for local updates
is negligible compared to the time for communication and aggregation. Then, we
plot the number of active users (not idle) over the training process under
asynchronous communications. The orange chart in Figure 2(a) describes the
ratio of active users, which on average is roughly $80\%$ over time.
Therefore, we consider the same ratio for client sampling in the synchronous
updates for methods such as FedAvg and plot the activity of users in the same
figure with green color. As shown in Figure 2(a), the degree of concurrency
for asynchronous methods is dramatically higher than their synchronous
counterparts.

We also generate heterogeneous data from MNIST [42] and CIFAR-10 [40] datasets
on the clients, i.e., each client holds a distinguished and unbalanced
distribution of images from different classes. For instance, client $i\in[n]$
may mostly have samples from odd numbers in MNIST, while client $j\in[n]$
mainly holds digits zero to four. Over the underlying communication setup and
heterogeneous data setting, we compare the speed and accuracy of FedAvg, Per-
FedAvg, pFedMe, AFL, PersA-FL: MAML, PersA-FL: ME, where the first three
methods are synchronous and the rest are asynchronous. For MNIST and CIFAR-10,
we consider 2-layer and 4-layer convolutional networks [40] with pooling and
dropout as well as cross-entropy loss. For all algorithms, we consider $Q=10$
local updates, and select the best $\lambda\in\\{15,20,25,30\\}$ for ME and
$\alpha\in\\{0.001,0.002,0.005,0.01,0.02\\}$ for MAML. Moreover, we pick
$\beta\in\\{0.7,0.8,0.9,1.0,1.1,1.2\\}$ and fix $\eta=0.03$. For both
experiments, we consider the exact same communication setup and repeat each
experiment $3$ times and plot the test accuracy curve over time until one of
the algorithms stops. Figure 2 (b)&(c) compares the performance and speed of
these algorithms.

It is worth mentioning that in the implementation of algorithms with MAML, we
approximated the Hessian-vector products via the following first-order
formulation: for some small $\delta>0$,

$\displaystyle\nabla^{2}f_{i}(w)u\approx\frac{\nabla f_{i}(w+\delta u)-\nabla
f_{i}(w-\delta u)}{\delta}.$ (30)

Moreover, in the bi-level optimization problem for the ME formulation, we
applied a constant $K=10$ steps of SGD to obtain $\tilde{\theta}_{i}(w)$.

(a) Concurrency (b) MNIST (c) CIFAR-10

Figure 2: The impact of heterogeneity and communication delays on concurrency,
convergence speed, and performance of multiple FL-based algorithms. The
underlying setup of this experiment consists of $n=50$ clients, $Q=10$ local
updates, and each client has a random upload and download delay at each round.
(a) A comparison between the ratio of active users for synchronous and
asynchronous updates over the course of training. (b) Comparison between the
test accuracy of FedAvg, Per-FedAvg, pFedMe, AFL, PersA-FL: MAML, and PersA-
FL: ME on MNIST data with heterogeneous distribution. (c) Test accuracy of the
mentioned methods on CIFAR-10 data with synthetic heterogeneity within a
limited fixed time.

##  6 Conclusion

This work studied the personalized federated learning problem for the
heterogeneous data setting under asynchronous communications with the server.
We considered the Model-Agnostic Meta-Learning (MAML) and Moreau Envelope (ME)
formulations to account for personalization. We proposed the PersA-FL
algorithm to solve this problem under stale updates. We showed the convergence
rate of our method for smooth non-convex functions vanilla asynchronous
federated learning, and personalized federated learning under the two
personalization formulations, i.e., MAML and ME. Particularly, for vanilla
asynchronous federated learning and personalized federated learning under
Moreau Envelope costs, we presented a proof technique that does not require a
boundedness assumption on the gradient norm. We finally show numerical results
that illustrate the benefits of our proposed method in terms of accuracy and
scalability. The studies of generalization and communication efficiency will
be left to future research. Moreover, the extensions of our method to the
buffered aggregation and decentralized setups remain for future studies.

## References

  * Agarwal and Duchi [2012] Alekh Agarwal and John C Duchi.  Distributed delayed stochastic optimization.  In _2012 IEEE 51st IEEE Conference on Decision and Control (CDC)_ , pages 5451–5452. IEEE, 2012.
  * Arjevani et al. [2020] Yossi Arjevani, Ohad Shamir, and Nathan Srebro.  A tight convergence analysis for stochastic gradient descent with delayed updates.  In _Algorithmic Learning Theory_ , pages 111–132. PMLR, 2020.
  * Assran et al. [2020] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat.  Advances in asynchronous parallel and distributed optimization.  _Proceedings of the IEEE_ , 108(11):2013–2031, 2020.
  * Aviv et al. [2021] Rotem Zamir Aviv, Ido Hakimi, Assaf Schuster, and Kfir Y Levy.  Learning under delayed feedback: Implicitly adapting to gradient delays.  _arXiv preprint arXiv:2106.12261_ , 2021.
  * Bergou et al. [2022] El Houcine Bergou, Konstantin Burlachenko, Aritra Dutta, and Peter Richtárik.  Personalized federated learning with communication compression.  _arXiv preprint arXiv:2209.05148_ , 2022.
  * Bertsekas [2021] Dimitri Bertsekas.  Distributed asynchronous policy iteration for sequential zero-sum games and minimax control.  _arXiv preprint arXiv:2107.10406_ , 2021.
  * Bubeck et al. [2015] Sébastien Bubeck et al.  Convex optimization: Algorithms and complexity.  _Foundations and Trends® in Machine Learning_ , 8(3-4):231–357, 2015.
  * Charles and Konečnỳ [2021] Zachary Charles and Jakub Konečnỳ.  Convergence and accuracy trade-offs in federated learning and meta-learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2575–2583. PMLR, 2021.
  * Collins et al. [2021] Liam Collins, Hamed Hassani, Aryan Mokhtari, and Sanjay Shakkottai.  Exploiting shared representations for personalized federated learning.  _arXiv preprint arXiv:2102.07078_ , 2021.
  * Deng et al. [2020] Yuyang Deng, Mohammad Mahdi Kamani, and Mehrdad Mahdavi.  Adaptive personalized federated learning.  _arXiv preprint arXiv:2003.13461_ , 2020.
  * Dennis and Smith [2020] Don Kurian Dennis and Virginia Smith.  Heterogeneity for the win: Communication-efficient federated clustering, 2020.
  * Dimitriadis et al. [2020] Dimitrios Dimitriadis, Kenichi Kumatani, Robert Gmyr, Yashesh Gaur, and Sefik Emre Eskimez.  Federated transfer learning with dynamic gradient aggregation.  _arXiv preprint arXiv:2008.02452_ , 2020.
  * Dinh et al. [2020] Canh T Dinh, Nguyen H Tran, and Tuan Dung Nguyen.  Personalized federated learning with moreau envelopes.  _arXiv preprint arXiv:2006.08848_ , 2020.
  * Divi et al. [2021] Siddharth Divi, Yi-Shan Lin, Habiba Farrukh, and Z Berkay Celik.  New metrics to evaluate the performance and fairness of personalized federated learning.  _arXiv preprint arXiv:2107.13173_ , 2021.
  * Eichner et al. [2019] Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar.  Semi-cyclic stochastic gradient descent.  In _International Conference on Machine Learning_ , pages 1764–1773. PMLR, 2019.
  * Fallah et al. [2020a] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.  On the convergence theory of gradient-based model-agnostic meta-learning algorithms.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1082–1092. PMLR, 2020a.
  * Fallah et al. [2020b] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.  Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach.  _Advances in Neural Information Processing Systems_ , 33, 2020b.
  * Fallah et al. [2021a] Alireza Fallah, Kristian Georgiev, Aryan Mokhtari, and Asuman Ozdaglar.  On the convergence theory of debiased model-agnostic meta-reinforcement learning.  _Advances in Neural Information Processing Systems_ , 34, 2021a.
  * Fallah et al. [2021b] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar.  Generalization of model-agnostic meta-learning algorithms: Recurring and unseen tasks.  _Advances in Neural Information Processing Systems_ , 34, 2021b.
  * Farnia et al. [2022] Farzan Farnia, Amirhossein Reisizadeh, Ramtin Pedarsani, and Ali Jadbabaie.  An optimal transport approach to personalized federated learning.  _arXiv preprint arXiv:2206.02468_ , 2022.
  * Finn et al. [2017] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _International Conference on Machine Learning_ , pages 1126–1135. PMLR, 2017.
  * Finn et al. [2019] Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine.  Online meta-learning.  In _International Conference on Machine Learning_ , pages 1920–1930. PMLR, 2019.
  * Gasanov et al. [2021] Elnur Gasanov, Ahmed Khaled, Samuel Horváth, and Peter Richtárik.  Flix: A simple and communication-efficient alternative to local methods in federated learning.  _arXiv preprint arXiv:2111.11556_ , 2021.
  * Girgis et al. [2021] Antonious Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh.  Shuffled model of differential privacy in federated learning.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2521–2529. PMLR, 2021.
  * Hadjicostis et al. [2015] Christoforos N Hadjicostis, Nitin H Vaidya, and Alejandro D Domínguez-García.  Robust distributed average consensus via exchange of running sums.  _IEEE Transactions on Automatic Control_ , 61(6):1492–1507, 2015.
  * Hanzely et al. [2020] Filip Hanzely, Slavomír Hanzely, Samuel Horváth, and Peter Richtárik.  Lower bounds and optimal algorithms for personalized federated learning.  _Advances in Neural Information Processing Systems_ , 33:2304–2315, 2020.
  * Hanzely et al. [2021] Filip Hanzely, Boxin Zhao, and Mladen Kolar.  Personalized federated learning: A unified framework and universal optimization techniques.  _arXiv preprint arXiv:2102.09743_ , 2021.
  * Hard et al. [2018] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage.  Federated learning for mobile keyboard prediction.  _arXiv preprint arXiv:1811.03604_ , 2018.
  * Huang et al. [2021] Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang, Jiangchuan Liu, Jian Pei, and Yong Zhang.  Personalized cross-silo federated learning on non-iid data.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 7865–7873, 2021.
  * Huang et al. [2015] Zhenqi Huang, Sayan Mitra, and Nitin Vaidya.  Differentially private distributed optimization.  In _Proceedings of the 2015 International Conference on Distributed Computing and Networking_ , pages 1–10, 2015.
  * Ji et al. [2020] Kaiyi Ji, Junjie Yang, and Yingbin Liang.  Multi-step model-agnostic meta-learning: Convergence and improved algorithms.  _arXiv preprint arXiv:2002.07836_ , 2020.
  * Kairouz et al. [2019] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Kairouz et al. [2021] Peter Kairouz, Ziyu Liu, and Thomas Steinke.  The distributed discrete gaussian mechanism for federated learning with secure aggregation.  In _International Conference on Machine Learning_ , pages 5201–5212. PMLR, 2021.
  * Karimireddy et al. [2020] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh.  Scaffold: Stochastic controlled averaging for federated learning.  In _International Conference on Machine Learning_ , pages 5132–5143. PMLR, 2020.
  * Khaled et al. [2020] Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik.  Tighter theory for local sgd on identical and heterogeneous data.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4519–4529. PMLR, 2020.
  * Koloskova et al. [2019] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi.  Decentralized deep learning with arbitrary communication compression.  _arXiv preprint arXiv:1907.09356_ , 2019.
  * Koloskova et al. [2022] Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi.  Sharper convergence guarantees for asynchronous sgd for distributed and federated learning.  _arXiv preprint arXiv:2206.08307_ , 2022.
  * Konečnỳ et al. [2015] J. Konečnỳ, B. McMahan, and D. Ramage.  Federated optimization: Distributed optimization beyond the datacenter.  _arXiv preprint arXiv:1511.03575_ , 2015.
  * Konečnỳ et al. [2016] Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016.
  * Krizhevsky and Hinton [2010] Alex Krizhevsky and Geoff Hinton.  Convolutional deep belief networks on cifar-10.  _Unpublished manuscript_ , 40(7):1–9, 2010.
  * Kulkarni et al. [2020] Viraj Kulkarni, Milind Kulkarni, and Aniruddha Pant.  Survey of personalization techniques for federated learning.  In _2020 Fourth World Conference on Smart Trends in Systems, Security and Sustainability (WorldS4)_ , pages 794–797. IEEE, 2020.
  * LeCun [1998] Yann LeCun.  The mnist database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_ , 1998.
  * Li et al. [2021] Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith.  Ditto: Fair and robust federated learning through personalization.  In _International Conference on Machine Learning_ , pages 6357–6368. PMLR, 2021.
  * Li et al. [2019] Yanan Li, Shusen Yang, Xuebin Ren, and Cong Zhao.  Asynchronous federated learning with differential privacy for edge intelligence.  _arXiv preprint arXiv:1912.07902_ , 2019.
  * Lyu et al. [2022] Boxiang Lyu, Filip Hanzely, and Mladen Kolar.  Personalized federated learning with multiple known clusters.  _arXiv preprint arXiv:2204.13619_ , 2022.
  * Mansour et al. [2020] Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh.  Three approaches for personalization with applications to federated learning.  _arXiv preprint arXiv:2002.10619_ , 2020.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial intelligence and statistics_ , pages 1273–1282. PMLR, 2017.
  * Mishchenko et al. [2022] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth.  Asynchronous sgd beats minibatch sgd under arbitrary delays.  _arXiv preprint arXiv:2206.07638_ , 2022.
  * Mitliagkas et al. [2016] Ioannis Mitliagkas, Ce Zhang, Stefan Hadjis, and Christopher Ré.  Asynchrony begets momentum, with an application to deep learning.  In _2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 997–1004. IEEE, 2016.
  * Mortaheb et al. [2022] Matin Mortaheb, Cemil Vahapoglu, and Sennur Ulukus.  Fedgradnorm: Personalized federated gradient-normalized multi-task learning.  _arXiv preprint arXiv:2203.13663_ , 2022.
  * Nguyen et al. [2022] John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba.  Federated learning with buffered asynchronous aggregation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3581–3607. PMLR, 2022.
  * Niu et al. [2011] Feng Niu, Benjamin Recht, Christopher Ré, and Stephen J Wright.  Hogwild!: A lock-free approach to parallelizing stochastic gradient descent.  _arXiv preprint arXiv:1106.5730_ , 2011.
  * Niwa et al. [2021] Kenta Niwa, Guoqiang Zhang, W Bastiaan Kleijn, Noboru Harada, Hiroshi Sawada, and Akinori Fujino.  Asynchronous decentralized optimization with implicit stochastic variance reduction.  In _International Conference on Machine Learning_ , pages 8195–8204. PMLR, 2021.
  * Olshevsky et al. [2018] Alex Olshevsky, Ioannis Ch Paschalidis, and Artin Spiridonoff.  Fully asynchronous push-sum with growing intercommunication intervals.  In _2018 Annual American Control Conference (ACC)_ , pages 591–596. IEEE, 2018.
  * Prasad et al. [2022] Karthik Prasad, Sayan Ghosh, Graham Cormode, Ilya Mironov, Ashkan Yousefpour, and Pierre Stock.  Reconciling security and communication efficiency in federated learning.  _arXiv preprint arXiv:2207.12779_ , 2022.
  * Rajeswaran et al. [2019] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine.  Meta-learning with implicit gradients.  _Advances in neural information processing systems_ , 32, 2019.
  * Reisizadeh et al. [2022] Amirhossein Reisizadeh, Isidoros Tziotis, Hamed Hassani, Aryan Mokhtari, and Ramtin Pedarsani.  Straggler-resilient federated learning: Leveraging the interplay between statistical accuracy and system heterogeneity.  _IEEE Journal on Selected Areas in Information Theory_ , 2022.
  * Sadiev et al. [2022] Abdurakhmon Sadiev, Ekaterina Borodich, Aleksandr Beznosikov, Darina Dvinskikh, Saveliy Chezhegov, Rachael Tappenden, Martin Takáč, and Alexander Gasnikov.  Decentralized personalized federated learning: Lower bounds and optimal algorithm for all personalization modes.  _EURO Journal on Computational Optimization_ , page 100041, 2022.
  * Safaryan et al. [2021] Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik.  Fednl: Making newton-type methods applicable to federated learning.  _arXiv preprint arXiv:2106.02969_ , 2021.
  * Shamsian et al. [2021] Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik.  Personalized federated learning using hypernetworks.  In _International Conference on Machine Learning_ , pages 9489–9502. PMLR, 2021.
  * Spiridonoff et al. [2020] Artin Spiridonoff, Alex Olshevsky, and Ioannis Ch Paschalidis.  Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-independent performance for strongly convex functions.  _Journal of machine learning research_ , 21(58), 2020.
  * Stich et al. [2021] Sebastian Stich, Amirkeivan Mohtashami, and Martin Jaggi.  Critical parameters for scalable distributed learning with large batches and asynchronous updates.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4042–4050. PMLR, 2021.
  * Stich [2019] Sebastian Urban Stich.  Local sgd converges fast and communicates little.  In _ICLR 2019-International Conference on Learning Representations_ , number CONF, 2019.
  * Toghani et al. [2023] Mohammad Taha Toghani, Soomin Lee, and César A. Uribe.  Pars-push: Personalized, asynchronous and robust decentralized optimization.  _IEEE Control Systems Letters_ , 7:361–366, 2023.  10.1109/LCSYS.2022.3189317.
  * Tziotis et al. [2022] Isidoros Tziotis, Zebang Shen, Ramtin Pedarsani, Hamed Hassani, and Aryan Mokhtari.  Straggler-resilient personalized federated learning.  _arXiv preprint arXiv:2206.02078_ , 2022.
  * Vanschoren [2018] Joaquin Vanschoren.  Meta-learning: A survey.  _arXiv preprint arXiv:1810.03548_ , 2018.
  * Wang et al. [2020] Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor.  Tackling the objective inconsistency problem in heterogeneous federated optimization.  _Advances in neural information processing systems_ , 33:7611–7623, 2020.
  * Wang et al. [2021] Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al.  A field guide to federated optimization.  _arXiv preprint arXiv:2107.06917_ , 2021.
  * Wei et al. [2020] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor.  Federated learning with differential privacy: Algorithms and performance analysis.  _IEEE Transactions on Information Forensics and Security_ , 15:3454–3469, 2020.
  * Xie et al. [2019] Cong Xie, Sanmi Koyejo, and Indranil Gupta.  Asynchronous federated optimization.  _arXiv preprint arXiv:1903.03934_ , 2019.
  * Yu et al. [2019] Hao Yu, Sen Yang, and Shenghuo Zhu.  Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 5693–5700, 2019.
  * Zhang et al. [2020] Michael Zhang, Karan Sapra, Sanja Fidler, Serena Yeung, and Jose M Alvarez.  Personalized federated learning with first order model optimization.  _arXiv preprint arXiv:2012.08565_ , 2020.
  * Zhuang et al. [2020] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He.  A comprehensive survey on transfer learning.  _Proceedings of the IEEE_ , 109(1):43–76, 2020\.

##  Appendix A Asynchronous Federated Learning

###### Proof of Theorem 1.

First, we present a set of useful inequalities we will use in the proof. For
any set of $m$ vectors $\\{w_{i}\\}_{i{=}1}^{m}$ such that
$w_{i}\in\mathbb{R}^{d}$, and a constant $\alpha>0$, the following properties
hold: for all $i,j\in[m]$:

$\displaystyle\lVert w_{i}+w_{j}\rVert^{2}$
$\displaystyle\leq(1{+}\alpha)\lVert w_{i}\rVert^{2}+(1{+}\alpha^{-1})\lVert
w_{j}\rVert^{2},$ (31a) $\displaystyle\lVert w_{i}+w_{j}\rVert$
$\displaystyle\leq\lVert w_{i}\rVert+\lVert w_{j}\rVert,$ (31b) $\displaystyle
2\langle w_{i},w_{j}\rangle$ $\displaystyle\leq\alpha\lVert
w_{i}\rVert^{2}+\alpha^{-1}\lVert w_{j}\rVert^{2},$ (31c)
$\displaystyle\left\lVert\sum\limits_{i=1}^{m}w_{i}\right\rVert^{2}$
$\displaystyle\leq m\left(\sum\limits_{i=1}^{m}\lVert w_{i}\rVert^{2}\right).$
(31d)

Now, let us rewrite the update rule of the joint iterates in Algorithms 1 & 2
Option A at time $t$ as follows:

  * •

Client update:

$\displaystyle w_{i,0}^{t}$ $\displaystyle=w^{t},$ (32) $\displaystyle
w_{i,q{+}1}^{t}$
$\displaystyle=w_{i,q}^{t}-\eta\nabla\tilde{f}_{i}(w_{i,q}^{t},\mathcal{D}_{i,q}^{t}),$
(33)

  * •

Server update:

$\displaystyle
w^{t{+}1}=w^{t}-\beta\Delta_{i_{t}}=w^{t}-\eta\beta\sum\limits_{q=0}^{Q{-}1}\nabla\tilde{f}_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)},\mathcal{D}_{i,q}^{\Omega(t)}\right).$
(34)

For simplicity, we denote
$\tilde{\nabla}f_{i}\left(w\right)=\nabla\tilde{f}_{i}\left(w,\mathcal{D}_{i}\right)$.
Therefore, at round $t$, the server updates its parameter by receiving
$\Delta_{i_{t}}$ from some client $i_{t}\in[n]$, as follows:

$\displaystyle
w^{t{+}1}=w^{t}-\eta\beta\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right).$
(35)

Moreover, Due to Assumption 2, we can infer that $f$ is $L$-smooth, thus

$\displaystyle
f\left(w^{t{+}1}\right)\overset{\eqref{eq:smoothness}}{\leq}f(w^{t})-\eta\beta\underbrace{\left\langle\nabla
f(w^{t}),\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right)\right\rangle}_{=:S_{a_{1}}}+\frac{L\eta^{2}\beta^{2}}{2}\underbrace{\left\lVert\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right)\right\rVert^{2}}_{=:S_{a_{2}}}$
(36)

First, we provide a lower bound on term $S_{a_{1}}$ in (36). Prior to show the
bound, let us denote
$\tilde{g}_{i}^{t}=\sum\limits_{q{=}0}^{Q{-}1}\tilde{\nabla}f_{i}\left(w_{i,q}^{\Omega(t)}\right)$,
$\tilde{g}^{t}=\frac{1}{n}\sum\limits_{i{=}1}^{n}\tilde{g}_{i}^{t}$,
$g_{i}^{t}=\sum\limits_{q{=}0}^{Q{-}1}\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)$, and
$g^{t}=\frac{1}{n}\sum\limits_{i{=}1}^{n}g_{i}^{t}$. Therefore,

$\displaystyle\mathbb{E}\left[S_{a_{1}}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}_{i_{t}}\left\langle\nabla
f(w^{t}),\tilde{g}_{i_{t}}^{t}\right\rangle\right]$ (37)
$\displaystyle=\mathbb{E}\left[\left\langle\nabla
f(w^{t}),\frac{1}{n}\sum\limits_{i=1}^{n}\tilde{g}_{i}^{t}\right\rangle\right]$
(38) $\displaystyle=\mathbb{E}\left\langle\nabla
f(w^{t}),\frac{1}{n}\sum\limits_{i=1}^{n}\mathbb{E}_{p_{i}}\left[\tilde{g}_{i}^{t}\right]\right\rangle=\mathbb{E}\left\langle\nabla
f(w^{t}),\frac{1}{n}\sum\limits_{i=1}^{n}g_{i}^{t}\right\rangle$ (39)
$\displaystyle=Q\,\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}+\mathbb{E}\left\langle\nabla f(w^{t}),g^{t}-Q\nabla
f(w^{t})\right\rangle$ (40) $\displaystyle{\geq}Q\,\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}-\frac{1}{2}\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}-\frac{1}{2}\mathbb{E}\left\lVert g^{t}-Q\nabla
f(w^{t})\right\rVert^{2}$ (41)
$\displaystyle=\frac{2Q{-}1}{2}\,\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}-\frac{1}{2}\mathbb{E}\left\lVert g^{t}-Q\nabla
f(w^{t})\right\rVert^{2}.$ (42)

Moreover, the following holds for $S_{a_{2}}$ in (36):

$\displaystyle\mathbb{E}_{i_{t}}\left[S_{a_{2}}\right]=\mathbb{E}_{i_{t}}\left\lVert\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}f_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right)\right\rVert^{2}=\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\tilde{g}_{i}^{t}\right\rVert^{2}.$
(43)

Now, according to (36), (42), and (43), we have:

$\displaystyle\mathbb{E}f\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}f(w^{t})-\frac{\eta\beta(2Q{-}1)}{2}\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$ (44)
$\displaystyle+\frac{\eta\beta}{2}\mathbb{E}\underbrace{\left\lVert
g^{t}-Q\nabla
f(w^{t})\right\rVert^{2}}_{=:S_{a_{3}}}+\frac{L\eta^{2}\beta^{2}}{2n}\mathbb{E}\underbrace{\left[\sum\limits_{i=1}^{n}\left\lVert\tilde{g}_{i}^{t}\right\rVert^{2}\right]}_{=:S_{a_{4}}},$
(45)

where we bound $S_{a_{3}}$ and $S_{a_{4}}$ as follows:

$\displaystyle
S_{a_{3}}=\left\lVert\frac{1}{n}\sum\limits_{i=1}^{n}\left(g_{i}^{t}-Q\nabla
f_{i}(w^{t})\right)\right\rVert^{2}$
$\displaystyle{\leq}\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert
g_{i}^{t}-Q\nabla f_{i}(w^{t})\right\rVert^{2}$ (46)
$\displaystyle=\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\sum\limits_{q{=}0}^{Q{-}1}\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-Q\nabla f_{i}(w^{t})\right\rVert^{2}$
(47)
$\displaystyle=\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\sum\limits_{q{=}0}^{Q{-}1}\left[\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
f_{i}(w^{t})\right]\right\rVert^{2}$ (48)
$\displaystyle{\leq}\frac{Q}{n}\sum\limits_{i=1}^{n}\sum\limits_{q=0}^{Q{-}1}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla f_{i}(w^{t})\right\rVert^{2},$
(49)

$\displaystyle S_{a_{4}}$
$\displaystyle=\,\,\,\,\,\sum\limits_{i=1}^{n}\Big{\lVert}\sum\limits_{q{=}0}^{Q{-}1}\tilde{\nabla}$
$\displaystyle f_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}$ (50)
$\displaystyle{\leq}\,\,\,\,Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}$
$\displaystyle\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}$
(51)
$\displaystyle=\,\,\,\,\,\,\,\,Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}$
$\displaystyle\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)+\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla f_{i}\left(w^{t}\right)$
$\displaystyle+\nabla f_{i}\left(w^{t}\right)-\nabla
f\left(w^{t}\right)+\nabla f\left(w^{t}\right)\Big{\rVert}^{2}$ (52)
$\displaystyle{\leq}4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}$
$\displaystyle\Bigg{[}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}+\Big{\lVert}\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
f_{i}\left(w^{t}\right)\Big{\rVert}^{2}$ $\displaystyle+\Big{\lVert}\nabla
f_{i}\left(w^{t}\right)-\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}+\Big{\lVert}\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}\Bigg{]}\Rightarrow$ (53)

$\displaystyle\mathbb{E}[S_{a_{4}}]$
$\displaystyle{\leq}4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}_{p_{i}}\Bigg{[}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}\Bigg{]}$ (54)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
f_{i}\left(w^{t}\right)\Big{\rVert}^{2}$ (55)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{t}\right)-\nabla f\left(w^{t}\right)\Big{\rVert}^{2}$ (56)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}$ (57)
$\displaystyle{\leq}4nQ^{2}\left[\sigma_{a}^{2}+\gamma_{g}^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{t}\right)\Big{\rVert}^{2}\right]$ (58)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla f_{i}(w^{t})\right\rVert^{2}.$
(59)

Therefore, due to (44)-(49) and (58)-(59), we have

$\displaystyle\mathbb{E}f\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}f(w^{t})-\left[\frac{\eta\beta(2Q{-}1)}{2}-2\eta^{2}L\beta^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$ (60) $\displaystyle+\left[\frac{\eta\beta
Q}{2n}+\frac{2\eta^{2}\beta^{2}QL}{n}\right]\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
f_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla f_{i}(w^{t})\right\rVert^{2}$
(61)
$\displaystyle+2\eta^{2}L\beta^{2}Q^{2}\sigma_{a}^{2}+2\eta^{2}L\beta^{2}Q^{2}\gamma_{g}^{2}$
(62)
$\displaystyle{\leq}\mathbb{E}f(w^{t})-\left[\frac{\eta\beta(2Q{-}1)}{2}-2\eta^{2}L\beta^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$ (63) $\displaystyle+\frac{\eta\beta
QL^{2}\left(1{+}4\eta\beta
L\right)}{2n}\mathbb{E}\underbrace{\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\left\lVert
w_{i,q}^{\Omega(t)}-w^{t}\right\rVert^{2}}_{=:S_{a_{5}}}$ (64)
$\displaystyle+2\eta^{2}L\beta^{2}Q^{2}\sigma_{a}^{2}+2\eta^{2}L\beta^{2}Q^{2}\gamma_{g}^{2}.$
(65)

Thus, it is sufficient to bound the following expression in $S_{a_{5}}$:

$\displaystyle\Big{\lVert}w^{t}$ $\displaystyle-
w_{i,q}^{\Omega(t)}\Big{\rVert}^{2}$ (66)
$\displaystyle=\left\lVert\sum\limits_{s{=}\Omega(t)}^{t{-}1}\left(w^{s{+}1}-w^{s}\right)+w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$
(67)
$\displaystyle{\leq}\left(1{+}\frac{1}{\beta^{2}}\right)\left\lVert\sum\limits_{s{=}\Omega(t)}^{t{-}1}\left(w^{s{+}1}-w^{s}\right)\right\rVert^{2}+\left(1{+}\beta^{2}\right)\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$ (68)
$\displaystyle{\leq}\left(t{-}\Omega(t)\right)\left(1{+}\frac{1}{\beta^{2}}\right)\left[\sum\limits_{s{=}\Omega(t)}^{t{-}1}\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}\right]+\left(1{+}\beta^{2}\right)\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$ (69)
$\displaystyle{\leq}\tau\left(1{+}\frac{1}{\beta^{2}}\right)\underbrace{\left[\sum\limits_{s{=}t{-}\tau}^{t{-}1}\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}\right]}_{=:S_{a_{7}}}+\left(1{+}\beta^{2}\right)\underbrace{\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}}_{=:S_{a_{6}}}.$ (70)

Now, we show a bound on the evolution of local updates at an arbitrary round
$s\geq 0$, i.e., the distance between $w_{i,q}^{s}$ and $w^{s}$:

$\displaystyle\mathbb{E}\left\lVert w_{i,q}^{s}-w^{s}\right\rVert^{2}$
$\displaystyle=\mathbb{E}\left\lVert
w_{i,q{-}1}^{s}-\eta\tilde{\nabla}f_{i}\left(w_{i,q{-}1}^{s}\right)-w^{s}\right\rVert^{2}$
(71) $\displaystyle=\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}-\eta\nabla
f\left(w^{s}\right)$
$\displaystyle\quad-\eta\tilde{\nabla}f_{i}\left(w_{i,q{-}1}^{s}\right)+\eta\nabla
f_{i}\left(w_{i,q{-}1}^{s}\right)$ $\displaystyle\quad-\eta\nabla
f_{i}\left(w_{i,q{-}1}^{s}\right)+\eta\nabla f_{i}\left(w^{s}\right)$
$\displaystyle\quad-\eta\nabla f_{i}\left(w^{s}\right)+\eta\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}$ (72)
$\displaystyle{\leq}\left(1{+}\frac{1}{2Q}\right)\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}$
(73) $\displaystyle+\hskip
10.00002pt4(1{+}2Q)\eta^{2}\mathbb{E}\Bigg{[}\Big{\lVert}\tilde{\nabla}f_{i}\left(w_{i,q{-}1}^{s}\right)-\nabla
f_{i}\left(w_{i,q{-}1}^{s}\right)\Big{\rVert}^{2}$ $\displaystyle\hskip
71.00017pt+\Big{\lVert}\nabla f_{i}\left(w_{i,q{-}1}^{s}\right)-\nabla
f_{i}\left(w^{s}\right)\Big{\rVert}^{2}$ $\displaystyle\hskip
71.00017pt+\Big{\lVert}\nabla f_{i}\left(w^{s}\right)-\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}$ $\displaystyle\hskip
71.00017pt+\Big{\lVert}\nabla f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]}$
(74)
$\displaystyle{\leq}\left(1{+}\frac{1}{2Q}\right)\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}$
(75) $\displaystyle+\hskip
10.00002pt4(1{+}2Q)\eta^{2}\Bigg{[}\sigma_{a}^{2}+L^{2}\,\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}$
$\displaystyle\hskip 71.00017pt+\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{s}\right)-\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]}.$ (76)

Note that we can select stepsize $\eta\leq\frac{1}{4L(Q{+}1)}$ such that

$\displaystyle\eta^{2}\leq\frac{1}{16L^{2}(Q{+}1)^{2}}\leq\frac{1}{8L^{2}Q(2Q{+}1)}\Rightarrow
4(1{+}2Q)\eta^{2}L^{2}\leq\frac{1}{2Q},$ (77)

therefore, due to (71)-(77), we have:

$\displaystyle\underbrace{\mathbb{E}\left\lVert
w_{i,q}^{s}-w^{s}\right\rVert^{2}}_{:=P_{i,q}^{s}}\leq\underbrace{\left(1{+}\frac{1}{Q}\right)\mathbb{E}\Big{\lVert}w_{i,q{-}1}^{s}-w^{s}\Big{\rVert}^{2}}_{:=P_{i,q{-}1}^{s}}$
(78)
$\displaystyle\qquad\quad+\underbrace{4(1{+}2Q)\eta^{2}\Bigg{[}\sigma_{a}^{2}+\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{s}\right)-\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]}}_{:=R_{i}^{s}}\Rightarrow$ (79)
$\displaystyle P_{i,q}^{s}$
$\displaystyle\leq\left(1{+}\frac{1}{Q}\right)P_{i,q{-}1}^{s}+R_{i}^{s}$ (80)
$\displaystyle=R_{i}^{s}\sum\limits_{k=0}^{q{-}1}\left(1{+}\frac{1}{Q}\right)^{k}\leq
R_{i}^{s}\sum\limits_{k=0}^{Q{-}1}\left(1{+}\frac{1}{Q}\right)^{k}$ (81)
$\displaystyle=R_{i}^{s}\frac{\left(1{+}\frac{1}{Q}\right)^{Q}-1}{\left(1{+}\frac{1}{Q}\right)-1}=R_{i}^{s}Q\left[\left(1{+}\frac{1}{Q}\right)^{Q}-1\right]\leq
R_{i}^{s}Q(e-1)\leq 2R_{i}^{s}Q\Rightarrow$ (82) $\displaystyle\mathbb{E}$
$\displaystyle\left\lVert w_{i,q}^{s}-w^{s}\right\rVert^{2}\leq
8Q(1{+}2Q)\eta^{2}\Bigg{[}\sigma_{a}^{2}+\mathbb{E}\Big{\lVert}\nabla
f_{i}\left(w^{s}\right)-\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{s}\right)\Big{\rVert}^{2}\Bigg{]},$ (83)

for all $q\in[Q]$ and $s\geq 0$. We now will use (71)-(83) to provide a bound
on the expression in $S_{a_{7}}$. Again, note that according to Algorithms 1 &
2, we have:

$\displaystyle w^{s{+}1}$
$\displaystyle=w^{s}-\beta\left(w_{i_{s},0}^{\Omega(s)}-w_{i_{s},Q}^{\Omega(s)}\right)\Rightarrow$
(84) $\displaystyle\mathbb{E}\left\lVert w^{s{+}1}-w^{s}\right\rVert^{2}$
$\displaystyle\leq\beta^{2}\,\mathbb{E}\left\lVert
w_{i_{s},Q}^{\Omega(s)}-w^{\Omega(s)}\right\rVert^{2}$ (85)
$\displaystyle=\beta^{2}\,\mathbb{E}\left[\mathbb{E}_{i_{s}}\left\lVert
w_{i_{s},Q}^{\Omega(s)}-w^{\Omega(s)}\right\rVert^{2}\right]$ (86)
$\displaystyle=\frac{\beta^{2}}{n}\sum\limits_{j{=}1}^{n}\mathbb{E}\left\lVert
w_{j,Q}^{\Omega(s)}-w^{\Omega(s)}\right\rVert^{2}$ (87) $\displaystyle\leq
8Q(1{+}2Q)\eta^{2}\beta^{2}\Bigg{[}\sigma_{a}^{2}+\gamma_{g}^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(s)}\right)\Big{\rVert}^{2}\Bigg{]}.$ (88)

Let $\phi=8\eta^{2}Q^{2}(1{+}2Q)(1{+}\beta^{2})$, then according to (66)-(88)

$\displaystyle\frac{1}{n\phi}\mathbb{E}[S_{a_{5}}]$
$\displaystyle\leq\tau\left[\sum\limits_{s{=}t{-}\tau}^{t{-}1}\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}\right]+\frac{1}{nQ}\sum_{i=1}^{n}\sum_{q=0}^{Q{-}1}\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}.$ (89)
$\displaystyle\leq\tau^{2}\sigma_{a}^{2}+\tau^{2}\gamma_{g}^{2}+\tau\sum_{s=t{-}\tau}^{t{-}1}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(s)}\right)\Big{\rVert}^{2}$ (90)
$\displaystyle+\sigma_{a}^{2}+\gamma_{g}^{2}+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(t)}\right)\Big{\rVert}^{2}$ (91)
$\displaystyle\leq(\tau^{2}{+}1)\left[\sigma_{a}^{2}+\gamma_{g}^{2}\right]+\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(t)}\right)\Big{\rVert}^{2}+\tau\sum_{s=t{-}\tau}^{t{-}1}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(s)}\right)\Big{\rVert}^{2}$ (92)
$\displaystyle\leq(\tau^{2}{+}1)\left[\sigma_{a}^{2}+\gamma_{g}^{2}\right]+\tau\sum_{s=t{-}\tau}^{t}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(s)}\right)\Big{\rVert}^{2}.$ (93)

Thus, by combining (60)-(93), we have the following inequality:

$\displaystyle\mathbb{E}f\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}f(w^{t})-\eta\beta\left[\frac{2Q{-}1}{2}-2\eta\beta
LQ^{2}\right]\mathbb{E}\left\lVert\nabla f(w^{t})\right\rVert^{2}$ (94)
$\displaystyle+4\eta^{3}\beta L^{2}Q^{3}(1{+}2Q)(1{+}\beta^{2})(1{+}4\eta\beta
L)\,\tau\left[\sum\limits_{s{=}t{-}\tau}^{t}\mathbb{E}\left\lVert\nabla
f\left(w^{\Omega(s)}\right)\right\rVert^{2}\right]$ (95)
$\displaystyle+4\eta^{3}\beta
L^{2}Q^{3}(1{+}2Q)(\tau^{2}{+}1)(1{+}\beta^{2})(1{+}4\eta\beta
L)\left(\sigma_{a}^{2}+\gamma_{g}^{2}\right)$ (96)
$\displaystyle+2\eta^{2}\beta^{2}LQ^{2}\left(\sigma_{a}^{2}+\gamma_{g}^{2}\right),$
(97)

where by rearranging, we obtain the following inequality:

$\displaystyle\left(1-4\eta\beta LQ\right)\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}$ (98)
$\displaystyle\qquad-8\eta^{2}L^{2}Q^{2}(1{+}2Q)(1{+}\beta^{2})(1{+}4\eta\beta
L)\,\tau\left[\sum\limits_{s{=}t{-}\tau}^{t}\mathbb{E}\left\lVert\nabla
f\left(w^{\Omega(s)}\right)\right\rVert^{2}\right]$ (99)
$\displaystyle\leq\frac{2\left[\mathbb{E}f(w^{t})-\mathbb{E}f\left(w^{t{+}1}\right)\right]}{\eta\beta
Q}$ (100)
$\displaystyle\qquad+8\eta^{2}L^{2}Q^{2}(1{+}2Q)(\tau^{2}{+}1)(1{+}\beta^{2})(1{+}4\eta\beta
L)\left(\sigma_{a}^{2}+\gamma_{g}^{2}\right)$ (101)
$\displaystyle\qquad+4\eta\beta LQ\left(\sigma_{a}^{2}+\gamma_{g}^{2}\right).$
(102)

Now, note that for any $s\geq 0$,555For $s<\tau$, the right-hand side of the
inequality consists of fewer terms.

$\displaystyle\mathbb{E}\Big{\lVert}\nabla
f\left(w^{\Omega(s)}\right)\Big{\rVert}^{2}\leq\sum_{u=s-\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
f\left(w^{u}\right)\Big{\rVert}^{2},$ (103)

Therefore, we add up the inequality in (98)-(102), for $t=0,1,\dots T{-}1$,
and obtain

$\displaystyle\big{[}1-4\eta\beta LQ-8\eta^{2}L^{2}$ $\displaystyle
Q^{2}(1{+}2Q)\tau(\tau{+}1)^{2}(1{+}\beta^{2})(1{+}4\eta\beta
L)\big{]}\frac{\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
f(w^{t})\right\rVert^{2}}{T}$ (104)
$\displaystyle\leq\frac{2\left[f(w^{0})-\mathbb{E}f(w^{T})\right]}{\eta\beta
QT}$ $\displaystyle+4\eta\beta LQ\left(\sigma_{a}^{2}+\gamma_{g}^{2}\right)$
(105)
$\displaystyle+8\eta^{2}L^{2}Q^{2}(1{+}2Q)(\tau^{2}{+}1)(1{+}\beta^{2})(1{+}4\eta\beta
L)\left(\sigma_{a}^{2}+\gamma_{g}^{2}\right).$ (106)

Thus, by setting $\beta=1$ and $\eta=\frac{1}{Q\sqrt{LT}}$, we can simply see
that

$\displaystyle 1-4\eta\beta LQ-8\eta^{2}L^{2}$ $\displaystyle
Q^{2}(1{+}2Q)\tau(\tau{+}1)^{2}(1{+}\beta^{2})(1{+}4\eta\beta
L)\geq\frac{1}{2},$ (107) $\displaystyle\eta\leq\frac{1}{4L(Q{+}1)},$ (108)

for $T\geq 160L(Q{+}7)(\tau{+}1)^{3}$. Therefore, we can conclude the final
result in Theorem 1 under this choice of $\eta$ and $\beta$. ∎

##  Appendix B Personalized Asynchronous Federated Learning: MAML

###### Proof of Theorem 2.

To simplify (9), we denote
$\tilde{\nabla}F^{(b)}_{i}\left(w\right)=\nabla\tilde{F}^{(b)}_{i}\left(w,\mathcal{D}_{i}^{\prime\prime},\mathcal{D}_{i}^{\prime},\mathcal{D}_{i}\right)$.
Then similar to (35), at round $t$, the update rule for Option B can be
written as follows:

$\displaystyle
w^{t{+}1}=w^{t}-\eta\beta\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}F^{(b)}_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right).$
(109)

According to Lemma 1,

$\displaystyle
F^{(b)}\left(w^{t{+}1}\right)\overset{\eqref{eq:smoothness}}{\leq}F^{(b)}(w^{t})$
$\displaystyle-\eta\beta\underbrace{\left\langle\nabla
F^{(b)}(w^{t}),\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}F^{(b)}_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right)\right\rangle}_{=:S_{b_{1}}}$
$\displaystyle+\frac{L_{b}\eta^{2}\beta^{2}}{2}\underbrace{\left\lVert\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}F^{(b)}_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right)\right\rVert^{2}}_{=:S_{b_{2}}}$
(110)

Similar to the inequalities in (37)-(42), we first show a lower bound on term
$S_{b_{1}}$ in (B). We also denote
$\tilde{g}_{i}^{t}=\sum\limits_{q{=}0}^{Q{-}1}\tilde{\nabla}F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)$,
$\tilde{g}^{t}=\frac{1}{n}\sum\limits_{i{=}1}^{n}\tilde{g}_{i}^{t}$,
$g_{i}^{t}=\sum\limits_{q{=}0}^{Q{-}1}\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)$, and
$g^{t}=\frac{1}{n}\sum\limits_{i{=}1}^{n}g_{i}^{t}$ for simplicity. Note that
$\tilde{g}_{i}^{t}$ and $g_{i}^{t}$ are the stochastic and deterministic
gradients of the personalized cost functions $F^{(b)}_{i}$ at stale
parameters. According to these definitions, we have

$\displaystyle\left\lVert\mathbb{E}\left[\tilde{g}^{t}-g^{t}\right]\right\rVert$
$\displaystyle{\leq}\frac{1}{n}\sum_{i=1}^{n}\left\lVert\mathbb{E}\left[\tilde{g}_{i}^{t}-g_{i}^{t}\right]\right\rVert$
(111)
$\displaystyle{\leq}\frac{1}{n}\sum_{i=1}^{n}\sum_{q=0}^{Q{-}1}\left\lVert\mathbb{E}\left[\tilde{\nabla}F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)\right]\right\rVert$ (112)
$\displaystyle{\leq}\frac{1}{n}\sum_{i=1}^{n}\sum_{q=0}^{Q{-}1}\mu_{b}=Q\mu_{b},$
(113)

where as we discussed in (22), $\mu_{b}$ measures the unbiasedness in the
estimation of the personalized stochastic gradient.

$\displaystyle\mathbb{E}\left[S_{b_{1}}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}_{i_{t}}\left\langle\nabla
F^{(b)}(w^{t}),\tilde{g}_{i_{t}}^{t}\right\rangle\right]$ (114)
$\displaystyle=\mathbb{E}\left[\left\langle\nabla
F^{(b)}(w^{t}),\frac{1}{n}\sum\limits_{i=1}^{n}\tilde{g}_{i}^{t}\right\rangle\right]=\mathbb{E}\left[\left\langle\nabla
F^{(b)}(w^{t}),\tilde{g}^{t}\right\rangle\right]$ (115)
$\displaystyle=Q\,\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}+\mathbb{E}\left\langle\nabla
F^{(b)}(w^{t}),\mathbb{E}\left[\tilde{g}^{t}-g^{t}\right]\right\rangle$ (116)
$\displaystyle+\mathbb{E}\left\langle\nabla F^{(b)}(w^{t}),g^{t}-Q\nabla
F^{(b)}(w^{t})\right\rangle$ (117)
$\displaystyle{\geq}Q\,\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}-\frac{1}{4}\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}-\left\lVert\mathbb{E}\left[g^{t}-\tilde{g}^{t}\right]\right\rVert^{2}$
(118) $\displaystyle-\frac{1}{4}\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}-\mathbb{E}\left\lVert g^{t}-Q\nabla
F^{(b)}(w^{t})\right\rVert^{2}$ (119)
$\displaystyle{\geq}\frac{2Q{-}1}{2}\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}-\mathbb{E}\left\lVert g^{t}-Q\nabla
F^{(b)}(w^{t})\right\rVert^{2}-Q^{2}\mu_{b}^{2},$ (120)

and

$\displaystyle\mathbb{E}_{i_{t}}\left[S_{b_{2}}\right]=\mathbb{E}_{i_{t}}\left\lVert\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}F^{(b)}_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right)\right\rVert^{2}=\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\tilde{g}_{i}^{t}\right\rVert^{2}.$
(121)

Therefore, according to (B), (120), and (121),

$\displaystyle\mathbb{E}F^{(b)}\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}F^{(b)}(w^{t})-\frac{\eta\beta(2Q{-}1)}{2}\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}+\eta\beta Q^{2}\mu_{b}^{2}$ (122)
$\displaystyle+\eta\beta\,\mathbb{E}\underbrace{\left\lVert g^{t}-Q\nabla
F^{(b)}(w^{t})\right\rVert^{2}}_{=:S_{b_{3}}}+\frac{L_{b}\eta^{2}\beta^{2}}{2n}\mathbb{E}\underbrace{\sum\limits_{i=1}^{n}\left\lVert\tilde{g}_{i}^{t}\right\rVert^{2}}_{=:S_{b_{4}}},$
(123)

where similar to (46)-(49), we can bound $S_{b_{3}}$ as follows:

$\displaystyle
S_{b_{3}}\leq\frac{Q}{n}\sum\limits_{i=1}^{n}\sum\limits_{q=0}^{Q{-}1}\left\lVert\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}(w^{t})\right\rVert^{2}.$ (124)

Moreover, we can show an upper bound on $S_{b_{4}}$ akin to (125)-(128):

$\displaystyle S_{b_{4}}$
$\displaystyle=\,\,\sum\limits_{i=1}^{n}\Big{\lVert}\sum\limits_{q{=}0}^{Q{-}1}\tilde{\nabla}$
$\displaystyle F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}$
(125) $\displaystyle{\leq}Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}$
$\displaystyle\Big{\lVert}\tilde{\nabla}F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}$
(126) $\displaystyle=\,\,\,Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}$
$\displaystyle\Big{\lVert}\tilde{\nabla}F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)+\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w^{t}\right)$ $\displaystyle+\nabla
F^{(b)}_{i}\left(w^{t}\right)-\nabla F^{(b)}\left(w^{t}\right)+\nabla
F^{(b)}\left(w^{t}\right)\Big{\rVert}^{2}$ (127)
$\displaystyle{\leq}4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}$
$\displaystyle\Bigg{[}\Big{\lVert}\tilde{\nabla}F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}$
$\displaystyle+\Big{\lVert}\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w^{t}\right)\Big{\rVert}^{2}$
$\displaystyle+\Big{\lVert}\nabla F^{(b)}_{i}\left(w^{t}\right)-\nabla
F^{(b)}\left(w^{t}\right)\Big{\rVert}^{2}$ $\displaystyle+\Big{\lVert}\nabla
F^{(b)}\left(w^{t}\right)\Big{\rVert}^{2}\Bigg{]}\Rightarrow$ (128)

$\displaystyle\mathbb{E}[S_{b_{4}}]$
$\displaystyle{\leq}4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}_{p_{i}}\Bigg{[}\Big{\lVert}\tilde{\nabla}F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)\Big{\rVert}^{2}\Bigg{]}$ (129)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\Big{\lVert}\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w^{t}\right)\Big{\rVert}^{2}$ (130)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\Big{\lVert}\nabla
F^{(b)}_{i}\left(w^{t}\right)-\nabla
F^{(b)}\left(w^{t}\right)\Big{\rVert}^{2}$ (131)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\Big{\lVert}\nabla
F^{(b)}\left(w^{t}\right)\Big{\rVert}^{2}$ (132)
$\displaystyle{\leq}4nQ^{2}\left[\sigma_{b}^{2}+\gamma_{b}^{2}+\mathbb{E}\Big{\lVert}\nabla
F^{(b)}\left(w^{t}\right)\Big{\rVert}^{2}\right]$ (133)
$\displaystyle+4Q\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}(w^{t})\right\rVert^{2}.$ (134)

Therefore, due to (122)-(124) and (133)-(134), we have

$\displaystyle\mathbb{E}F^{(b)}\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}F^{(b)}(w^{t})-\left[\frac{\eta\beta(2Q{-}1)}{2}-2\eta^{2}L_{b}\beta^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}$ (135) $\displaystyle+\left[\frac{\eta\beta
Q}{n}+\frac{2\eta^{2}\beta^{2}QL_{b}}{n}\right]\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\nabla
F^{(b)}_{i}\left(w_{i,q}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}(w^{t})\right\rVert^{2}$ (136) $\displaystyle+\eta\beta
Q^{2}\mu_{b}^{2}+2\eta^{2}L_{b}\beta^{2}Q^{2}\sigma_{b}^{2}+2\eta^{2}L_{b}\beta^{2}Q^{2}\gamma_{b}^{2}$
(137)
$\displaystyle{\leq}\mathbb{E}F^{(b)}(w^{t})-\left[\frac{\eta\beta(2Q{-}1)}{2}-2\eta^{2}L_{b}\beta^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}$ (138) $\displaystyle+\frac{\eta\beta
QL_{b}^{2}\left(1{+}2\eta\beta
L_{b}\right)}{n}\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\underbrace{\left\lVert
w_{i,q}^{\Omega(t)}-w^{t}\right\rVert^{2}}_{=:S_{b_{5}}}$ (139)
$\displaystyle+\eta\beta
Q^{2}\mu_{b}^{2}+2\eta^{2}L_{b}\beta^{2}Q^{2}\left(\sigma_{b}^{2}+\gamma_{b}^{2}\right).$
(140)

Now, we provide an upper bound on $S_{b_{5}}$ in (138) as follows:

$\displaystyle S_{b_{5}}=\left\lVert
w^{t}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$ $\displaystyle=\left\lVert
w^{t}-w^{\Omega(t)}+w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$ (141)
$\displaystyle{\leq}2\underbrace{\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}}_{S_{b_{6}}}+2\underbrace{\left\lVert
w^{t}-w^{\Omega(t)}\right\rVert^{2}}_{S_{b_{7}}},$ (142)

where the first term determines the evolution of local updates and the second
term considers the effect of asynchronous updates. Therefore, using Lemma 4,
we have

$\displaystyle\mathbb{E}[S_{b_{6}}]$ $\displaystyle=\mathbb{E}\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$ (143)
$\displaystyle=\mathbb{E}\left\lVert
w_{i,0}^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}$ (144)
$\displaystyle{=}\eta^{2}\mathbb{E}\left\lVert\sum_{r{=}0}^{q{-}1}\tilde{\nabla}F^{(b)}_{i}\left(w_{i,r}^{\Omega(t)}\right)\right\rVert^{2}$
(145)
$\displaystyle{\leq}\eta^{2}q\sum_{r{=}0}^{q{-}1}\mathbb{E}\left\lVert\tilde{\nabla}F^{(b)}_{i}\left(w_{i,r}^{\Omega(t)}\right)\right\rVert^{2}$
(146)
$\displaystyle{\leq}2\eta^{2}q\sum_{r{=}0}^{q{-}1}\left[\mathbb{E}\left\lVert\tilde{\nabla}F^{(b)}_{i}\left(w_{i,r}^{\Omega(t)}\right)-\nabla
F^{(b)}_{i}\left(w_{i,r}^{\Omega(t)}\right)\right\rVert^{2}+\mathbb{E}\left\lVert\nabla
F^{(b)}_{i}\left(w_{i,r}^{\Omega(t)}\right)\right\rVert^{2}\right]$ (147)
$\displaystyle{\leq}2\eta^{2}q\sum_{r{=}0}^{q{-}1}\left(G_{b}^{2}+\sigma_{b}^{2}\right)=2\eta^{2}q^{2}\left(G_{b}^{2}+\sigma_{b}^{2}\right),$
(148)

$\displaystyle\mathbb{E}[S_{b_{7}}]$ $\displaystyle=\mathbb{E}\left\lVert
w^{t}-w^{\Omega(t)}\right\rVert^{2}$ (149)
$\displaystyle=\mathbb{E}\left\lVert\sum_{s{=}\Omega(t)}^{t{-}1}\left(w^{s{+}1}-w^{s}\right)\right\rVert^{2}$
(150)
$\displaystyle{=}\eta^{2}\beta^{2}\mathbb{E}\left\lVert\sum_{s{=}\Omega(t)}^{t{-}1}\sum_{q{=}0}^{Q{-}1}\tilde{\nabla}F^{(b)}_{i_{s}}\left(w_{{i_{s}},q}^{\Omega(s)}\right)\right\rVert^{2}$
(151)
$\displaystyle{\leq}\eta^{2}\beta^{2}Q\,(t{-}\Omega(t))\sum_{s{=}\Omega(t)}^{t{-}1}\sum_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert\tilde{\nabla}F^{(b)}_{i_{s}}\left(w_{{i_{s}},q}^{\Omega(s)}\right)\right\rVert^{2}$
(152)
$\displaystyle{\leq}2\eta^{2}\beta^{2}Q\,\tau\sum_{s{=}t{-}\tau}^{t{-}1}\sum_{q{=}0}^{Q{-}1}\Bigg{[}\mathbb{E}\left\lVert\tilde{\nabla}F^{(b)}_{i_{s}}\left(w_{{i_{s}},q}^{\Omega(s)}\right)-\nabla
F^{(b)}_{i_{s}}\left(w_{{i_{s}},q}^{\Omega(s)}\right)\right\rVert^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\quad\,\,\,+\mathbb{E}\left\lVert\nabla
F^{(b)}_{i_{s}}\left(w_{{i_{s}},q}^{\Omega(s)}\right)\right\rVert^{2}\Bigg{]}$
(153)
$\displaystyle{\leq}2\eta^{2}\beta^{2}Q\tau^{2}\sum_{q{=}0}^{Q{-}1}\left(G_{b}^{2}+\sigma_{b}^{2}\right)=2\eta^{2}\beta^{2}Q^{2}\tau^{2}\left(G_{b}^{2}+\sigma_{b}^{2}\right).$
(154)

So, according to (135)-(154),

$\displaystyle\mathbb{E}F^{(b)}\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}F^{(b)}(w^{t})-\frac{\eta\beta}{2}\left(2Q{-}1-4\eta\beta
L_{b}Q^{2}\right)\mathbb{E}\left\lVert\nabla F^{(b)}(w^{t})\right\rVert^{2}$
(155) $\displaystyle+4\eta^{3}\beta Q^{4}L_{b}^{2}\left(1{+}2\eta\beta
L_{b}Q\right)\left(G_{b}^{2}{+}\sigma_{b}^{2}\right)\left(\beta^{2}\tau^{2}{+}1\right)$
(156) $\displaystyle+\eta\beta
Q^{2}\mu_{b}^{2}+2\eta^{2}\beta^{2}L_{b}Q^{2}\sigma_{b}^{2}+2\eta^{2}\beta^{2}L_{b}Q^{2}\gamma_{b}^{2},$
(157)

where by adding the terms in (155)-(157), for $t=0,1,\dots T{-}1$, and
rearranging them, we obtain the following inequality:

$\displaystyle\frac{1-4\eta\beta
L_{b}Q}{T}\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
F^{(b)}(w^{t})\right\rVert^{2}$
$\displaystyle\leq\frac{2\left(F^{(b)}(w^{0})-\mathbb{E}F^{(b)}(w^{T})\right)}{\eta\beta
QT}$ (158) $\displaystyle+8\eta^{2}Q^{3}L_{b}^{2}\left(1{+}2\eta\beta
L_{b}Q\right)\left(G_{b}^{2}{+}\sigma_{b}^{2}\right)\left(\beta^{2}\tau^{2}{+}1\right)$
(159) $\displaystyle+4\eta\beta
L_{b}Q\left(\sigma_{b}^{2}+\gamma_{b}^{2}\right)$ (160)
$\displaystyle+2Q\mu_{b}^{2}.$ (161)

Finally, we can conclude the proof by fixing $\beta=1$ and
$\eta\coloneqq\frac{1}{Q\sqrt{L_{b}T}}$ for $T\geq 64L_{b}$, hence
$\eta\leq\frac{1}{8\beta L_{b}Q}$. ∎

##  Appendix C Personalized Asynchronous Federated Learning: ME

We start by showing (10), where according to the definitions in (6) and (8),
we have

$\displaystyle\hat{\theta}_{i}(w)$
$\displaystyle=\operatorname*{arg\,min}_{\theta_{i}\in\mathbb{R}^{d}}\left[f_{i}(\theta_{i})+\frac{\lambda}{2}{\left\|\theta_{i}-w\right\|}^{2}\right]\Rightarrow\nabla
f_{i}\left(\hat{\theta}_{i}(w)\right)+\lambda\left[\hat{\theta}_{i}(w)-w\right]=0,$
(162) $\displaystyle F^{(c)}_{i}(w)$
$\displaystyle=f_{i}\left(\hat{\theta}_{i}(w)\right)+\frac{\lambda}{2}\left\lVert\hat{\theta}_{i}(w)-w\right\rVert^{2},$
(163)

therefore,

$\displaystyle\nabla F^{(c)}_{i}(w)$
$\displaystyle{=}\frac{\partial\,\hat{\theta}_{i}(w)}{\partial w}\left[\nabla
f_{i}\left(\hat{\theta}_{i}(w)\right)\right]+\lambda\left[\frac{\partial\,\hat{\theta}_{i}(w)}{\partial
w}-I\right]\left[\hat{\theta}_{i}(w)-w\right]$ (164)
$\displaystyle{=}\lambda\frac{\partial\,\hat{\theta}_{i}(w)}{\partial
w}\left[w-\hat{\theta}_{i}(w)\right]+\lambda\left[\frac{\partial\,\hat{\theta}_{i}(w)}{\partial
w}-I\right]\left[\hat{\theta}_{i}(w)-w\right]$ (165)
$\displaystyle=\lambda\left[w-\hat{\theta}_{i}(w)\right].$ (166)

Before, presenting the proof of Theorem 3, we proceed by providing the proof
of Lemmas 5, 6, and 7.

###### Proof of Lemma 5.

Let $w,v$ be two arbitrary vectors in $\mathbb{R}^{d}$. Then, we have:

$\displaystyle\nabla F_{i}^{(c)}(w)-\nabla F_{i}^{(c)}(y)$
$\displaystyle{=}\lambda\left[w-\hat{\theta}_{i}(w)\right]-\lambda\left[v-\hat{\theta}_{i}(v)\right]$
(167) $\displaystyle{=}\nabla f_{i}\left(\hat{\theta}_{i}(w)\right)-\nabla
f_{i}\left(\hat{\theta}_{i}(v)\right)\Rightarrow$ (168)
$\displaystyle\left\lVert\nabla F_{i}^{(c)}(w)-\nabla
F_{i}^{(c)}(y)\right\rVert$ $\displaystyle=\left\lVert\nabla
f_{i}\left(\hat{\theta}_{i}(w)\right)-\nabla
f_{i}\left(\hat{\theta}_{i}(v)\right)\right\rVert$ (169)
$\displaystyle{\leq}L\left\lVert\hat{\theta}_{i}(w)-\hat{\theta}_{i}(v)\right\rVert$
(170) $\displaystyle{=}L\left\lVert w-\frac{1}{\lambda}\nabla
f_{i}\left(\hat{\theta}_{i}(w)\right)-v+\frac{1}{\lambda}\nabla
f_{i}\left(\hat{\theta}_{i}(v)\right)\right\rVert$ (171) $\displaystyle\leq
L\left\lVert w-v\right\rVert+\frac{L}{\lambda}\left\lVert\nabla
f_{i}\left(\hat{\theta}_{i}(w)\right)-\nabla
f_{i}\left(\hat{\theta}_{i}(v)\right)\right\rVert$ (172)
$\displaystyle=L\left\lVert w-v\right\rVert+\frac{L}{\lambda}\left\lVert\nabla
F_{i}^{(c)}(w)-\nabla F_{i}^{(c)}(y)\right\rVert\Rightarrow$ (173)
$\displaystyle\left\lVert\nabla F_{i}^{(c)}(w)-\nabla
F_{i}^{(c)}(y)\right\rVert$ $\displaystyle\leq\frac{\lambda
L}{\lambda-L}\left\lVert w-v\right\rVert,$ (174)

which means $F^{(c)}_{i}$ is $\frac{\lambda L}{\lambda-L}$-smooth. Note that
for $\lambda\geq\kappa L$, for some $\kappa>1$,

$\displaystyle\frac{\lambda L}{\lambda-L}\leq
L_{c}\coloneqq\frac{\lambda}{\kappa-1}$ (175)

This concludes the statement of Lemma 5. ∎

###### Proof of Lemma 6.

According to Step 14 of Algorithm 2, let us introduce full and stochastic
auxiliary cost functions $h_{i}(\cdot)$ and $\tilde{h}_{i}(\cdot)$ as follows:

$\displaystyle h_{i}(\theta_{i},w)$
$\displaystyle=f_{i}(\theta_{i})+\frac{\lambda}{2}\left\lVert\theta_{i}-w\right\rVert^{2},$
(176) $\displaystyle\tilde{h}_{i}(\theta_{i},w,\mathcal{D})$
$\displaystyle=\tilde{f}_{i}(\theta_{i},\mathcal{D})+\frac{\lambda}{2}\left\lVert\theta_{i}-w\right\rVert^{2},$
(177)

where due to (176), we have

$\displaystyle\nabla\tilde{h}_{i}(\tilde{\theta}_{i}(w),w,\mathcal{D})$
$\displaystyle=\nabla\tilde{f}_{i}(\tilde{\theta}_{i}(w),\mathcal{D})+\lambda\left[\tilde{\theta}_{i}(w)-w\right],$
(178)

hence, we can show (26) as follows:

$\displaystyle\Big{\lVert}\mathbb{E}_{p_{i}}\Big{[}\nabla\tilde{F}^{(c)}_{i}$
$\displaystyle(w,\mathcal{D})-\nabla F^{(c)}_{i}(w)\Big{]}\Big{\rVert}$ (179)
$\displaystyle{=}\left\lVert\mathbb{E}_{p_{i}}\big{[}\lambda\hat{\theta}_{i}(w)-\lambda\tilde{\theta}_{i}(w)\big{]}\right\rVert$
(180) $\displaystyle{=}\Big{\lVert}\mathbb{E}_{p_{i}}\big{[}\nabla
f_{i}(\hat{\theta}_{i}(w))-\nabla\tilde{f}_{i}(\tilde{\theta}_{i}(w),\mathcal{D})+\nabla\tilde{h}_{i}(\tilde{\theta}_{i}(w),w,\mathcal{D})\big{]}\Big{\rVert}$
(181) $\displaystyle=\Big{\lVert}\mathbb{E}_{p_{i}}\big{[}\nabla
f_{i}(\hat{\theta}_{i}(w))-\nabla
f_{i}(\tilde{\theta}_{i}(w))\big{]}+\mathbb{E}_{p_{i}}\big{[}\nabla\tilde{h}_{i}(\tilde{\theta}_{i}(w),w,\mathcal{D})\big{]}\Big{\rVert}$
(182) $\displaystyle\leq\Big{\lVert}\mathbb{E}_{p_{i}}\big{[}\nabla
f_{i}(\hat{\theta}_{i}(w))-\nabla
f_{i}(\tilde{\theta}_{i}(w))\big{]}\Big{\rVert}+\nu$ (183)
$\displaystyle{\leq}L\Big{\lVert}\mathbb{E}_{p_{i}}\big{[}\hat{\theta}_{i}(w)-\tilde{\theta}_{i}(w)\big{]}\Big{\rVert}+\nu$
(184)
$\displaystyle{=}\frac{L}{\lambda}\left\lVert\mathbb{E}_{p_{i}}\left[\nabla\tilde{F}^{(c)}_{i}(w,\mathcal{D})-\nabla
F^{(c)}_{i}(w)\right]\right\rVert+\nu\Rightarrow$ (185)
$\displaystyle\Big{\lVert}\mathbb{E}_{p_{i}}\Big{[}\nabla\tilde{F}^{(c)}_{i}$
$\displaystyle(w,\mathcal{D})-\nabla
F^{(c)}_{i}(w)\Big{]}\Big{\rVert}\leq\frac{\lambda}{\lambda-L}\nu.$ (186)

You can find the proof of (27) in [13][Appendix A.2]. ∎

###### Proof of Lemma 7.

First, note that we have

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla$ $\displaystyle F^{(c)}(w)\Big{\rVert}^{2}$ (187)
$\displaystyle{=}\frac{1}{n}\sum\limits_{i=1}^{n}\left\lVert\lambda(w-\hat{\theta}_{i}(w))-\frac{1}{n}\sum_{j=1}^{n}\lambda(w-\hat{\theta}_{i}(w))\right\rVert^{2}$
(188)
$\displaystyle{=}\frac{1}{n^{3}}\sum\limits_{i=1}^{n}\left\lVert\sum\limits_{j=1}^{n}\left[\nabla
f_{i}(\hat{\theta}_{i}(w))-\nabla
f_{j}(\hat{\theta}_{j}(w))\right]\right\rVert^{2}$ (189)
$\displaystyle{\leq}\frac{1}{n^{2}}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\left\lVert\nabla
f_{i}(\hat{\theta}_{i}(w))-\nabla f_{j}(\hat{\theta}_{j}(w))\right\rVert^{2}.$
(190)

So, we simplify the upper bound as follows:

$\displaystyle\Big{\lVert}\nabla f_{i}(\hat{\theta}_{i}(w))-\nabla$
$\displaystyle f_{j}(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (191)
$\displaystyle=\Big{\lVert}\nabla f_{i}(\hat{\theta}_{i}(w))-\nabla
f_{i}(\hat{\theta}_{j}(w))+\nabla f_{i}(\hat{\theta}_{j}(w))-\nabla
f(\hat{\theta}_{j}(w))$ $\displaystyle\quad+\nabla
f(\hat{\theta}_{j}(w))-\nabla f(\hat{\theta}_{i}(w))+\nabla
f(\hat{\theta}_{i}(w))-\nabla f_{j}(\hat{\theta}_{i}(w))$
$\displaystyle\quad+\nabla f_{j}(\hat{\theta}_{i}(w))-\nabla
f_{j}(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (192)
$\displaystyle{\leq}\frac{4}{3}\Big{\lVert}\nabla
f_{i}(\hat{\theta}_{i}(w))-\nabla f_{i}(\hat{\theta}_{j}(w))+\nabla
f(\hat{\theta}_{j}(w))-\nabla f(\hat{\theta}_{i}(w))$
$\displaystyle\qquad\quad+\nabla f_{j}(\hat{\theta}_{i}(w))-\nabla
f_{j}(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (193)
$\displaystyle+4\Big{\lVert}\nabla f(\hat{\theta}_{i}(w))-\nabla
f_{j}(\hat{\theta}_{i}(w))+\nabla f_{i}(\hat{\theta}_{j}(w))-\nabla
f(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (194)
$\displaystyle{\leq}4\Big{\lVert}\nabla f_{i}(\hat{\theta}_{i}(w))-\nabla
f_{i}(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (195)
$\displaystyle+4\Big{\lVert}\nabla f(\hat{\theta}_{j}(w))-\nabla
f(\hat{\theta}_{i}(w))\Big{\rVert}^{2}$ (196)
$\displaystyle+4\Big{\lVert}\nabla f_{j}(\hat{\theta}_{i}(w))-\nabla
f_{j}(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (197)
$\displaystyle+8\Big{\lVert}\nabla f_{i}(\hat{\theta}_{j}(w))-\nabla
f(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (198)
$\displaystyle+8\Big{\lVert}\nabla f(\hat{\theta}_{i}(w))-\nabla
f_{j}(\hat{\theta}_{i}(w))\Big{\rVert}^{2}$ (199)

Note that we can bound (198) and (199) according to Lemma 16:

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\Big{\lVert}\nabla
f_{i}(\hat{\theta}_{j}(w))-\nabla f(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$
$\displaystyle\overset{\eqref{eq:bounded-heterogeneity}}{\leq}\gamma_{g}^{2},$
(200)

and also given the fact that function $f(\cdot)$ as well as each function
$f_{i}(\cdot)$ are $L$-smooth, we can bound (195), (196), and (197) as
follows:

$\displaystyle\Big{\lVert}\nabla f_{i}(\hat{\theta}_{i}(w))$
$\displaystyle-\nabla f_{i}(\hat{\theta}_{j}(w))\Big{\rVert}^{2}$ (201)
$\displaystyle\leq
L^{2}\Big{\lVert}\hat{\theta}_{i}(w)-\hat{\theta}_{j}(w)\Big{\rVert}^{2}$
(202)
$\displaystyle=\frac{L^{2}}{\lambda^{2}}\Big{\lVert}\lambda\left[\hat{\theta}_{i}(w)-w\right]-\lambda\left[\hat{\theta}_{j}(w)-w\right]\Big{\rVert}^{2}$
(203) $\displaystyle{=}\frac{L^{2}}{\lambda^{2}}\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla F^{(c)}_{j}(w)\Big{\rVert}^{2}$ (204)
$\displaystyle{=}\frac{L^{2}}{\lambda^{2}}\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla F^{(c)}(w)+\nabla F^{(c)}(w)-\nabla
F^{(c)}_{j}(w)\Big{\rVert}^{2}$ (205)
$\displaystyle{\leq}\frac{2L^{2}}{\lambda^{2}}\left[\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla F^{(c)}(w)\Big{\rVert}^{2}+\Big{\lVert}\nabla
F^{(c)}(w)-\nabla F^{(c)}_{j}(w)\Big{\rVert}^{2}\right].$ (206)

Therefore, according to (207)-(206), we have

$\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla F^{(c)}(w)\Big{\rVert}^{2}$ $\displaystyle\leq
16\gamma_{g}^{2}+\frac{48L^{2}}{n\lambda^{2}}\sum\limits_{i=1}^{n}\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla$ $\displaystyle F^{(c)}(w)\Big{\rVert}^{2}\Rightarrow$
(207) $\displaystyle\frac{1}{n}\sum\limits_{i=1}^{n}\Big{\lVert}\nabla
F^{(c)}_{i}(w)-\nabla F^{(c)}(w)\Big{\rVert}^{2}$
$\displaystyle\leq\frac{16\lambda^{2}\gamma_{g}^{2}}{\lambda^{2}-48L^{2}},$
(208)

which concludes the proof. ∎

Now, we are ready to state the proof of Theorem 3.

###### Proof of Theorem 3.

We write
$\tilde{\nabla}F^{(c)}_{i}\left(w\right)=\nabla\tilde{F}^{(c)}_{i}\left(w,\mathcal{D}_{i}\right)$
to simplify (10). Then, the update rule for Algorithms 1 & 2 under Option C
can be written as follows:

$\displaystyle
w^{t{+}1}=w^{t}-\eta\beta\sum\limits_{q=0}^{Q{-}1}\tilde{\nabla}F^{(c)}_{i_{t}}\left(w_{i_{t},q}^{\Omega(t)}\right),$
(209)

where similar to (B)-(140), we can show that:

$\displaystyle\mathbb{E}F^{(c)}\left(w^{t{+}1}\right)$
$\displaystyle\leq\mathbb{E}F^{(c)}(w^{t})-\left[\frac{\eta\beta(2Q{-}1)}{2}-2\eta^{2}L_{c}\beta^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
F^{(c)}(w^{t})\right\rVert^{2}$ (210) $\displaystyle+\frac{\eta\beta
QL_{c}^{2}\left(1{+}2\eta\beta
L_{c}\right)}{n}\underbrace{\sum\limits_{i=1}^{n}\sum\limits_{q{=}0}^{Q{-}1}\mathbb{E}\left\lVert
w_{i,q}^{\Omega(t)}-w^{t}\right\rVert^{2}}_{=:S_{c_{1}}}$ (211)
$\displaystyle+\eta\beta
Q^{2}\mu_{c}^{2}+2\eta^{2}L_{c}\beta^{2}Q^{2}\left(\sigma_{c}^{2}+\gamma_{c}^{2}\right),$
(212)

with $L_{c},\mu_{c},\sigma_{c},\gamma_{c}$ as defined in Lemmas 5, 6, and 7.
Thus, to show the convergence rate of our method for the cost function in (6),
it would only be sufficient to provide an upper bound on $S_{c_{1}}$. First,
note that similar to (66)-(70), we have

$\displaystyle\left\lVert w_{i,q}^{\Omega(t)}-w^{t}\right\rVert^{2}$
$\displaystyle\leq\tau\left(1{+}\frac{1}{\beta^{2}}\right)\left[\sum\limits_{s{=}t{-}\tau}^{t{-}1}\underbrace{\left\lVert
w^{s{+}1}-w^{s}\right\rVert^{2}}_{=:S_{c_{3}}}\right]+\left(1{+}\beta^{2}\right)\underbrace{\left\lVert
w^{\Omega(t)}-w_{i,q}^{\Omega(t)}\right\rVert^{2}}_{=:S_{c_{2}}}.$ (213)

Now, if we introduce stepsize $\eta$ such that
$\eta\leq\frac{1}{4L_{c}(Q{+}1)}$, similar to (71)-(76) and (84)-(88), the
following two inequalities holds for $S_{c_{2}}$ and $S_{c_{3}}$:

$\displaystyle\mathbb{E}[$ $\displaystyle S_{c_{2}}]=\mathbb{E}\left\lVert
w_{i,q}^{\Omega(t)}-w^{\Omega(t)}\right\rVert^{2}$ (214) $\displaystyle\leq
8Q(1{+}2Q)\eta^{2}\Bigg{[}\sigma_{c}^{2}+\mathbb{E}\Big{\lVert}\nabla
F^{(c)}_{i}\left(w^{\Omega(t)}\right)-\nabla
F^{(c)}\left(w^{\Omega(t)}\right)\Big{\rVert}^{2}+\mathbb{E}\Big{\lVert}\nabla
F^{(c)}\left(w^{\Omega(t)}\right)\Big{\rVert}^{2}\Bigg{]},$
$\displaystyle\mathbb{E}\left[S_{c_{3}}\right]$
$\displaystyle=\mathbb{E}\left\lVert w^{s{+}1}-w^{s}\right\rVert^{2}\leq
8Q(1{+}2Q)\eta^{2}\beta^{2}\Bigg{[}\sigma_{c}^{2}+\gamma_{c}^{2}+\mathbb{E}\Big{\lVert}\nabla
F^{(c)}\left(w^{\Omega(s)}\right)\Big{\rVert}^{2}\Bigg{]},$ (215)

where by denoting $\phi=8\eta^{2}Q^{2}(1{+}2Q)(1{+}\beta^{2})$, we have

$\displaystyle\frac{1}{n\phi}\mathbb{E}[S_{c_{1}}]$
$\displaystyle\leq(\tau^{2}{+}1)\left[\sigma_{c}^{2}+\gamma_{c}^{2}\right]+\tau\sum_{s=t{-}\tau}^{t}\sum_{u=s{-}\tau}^{s}\mathbb{E}\Big{\lVert}\nabla
F^{(c)}\left(w^{u}\right)\Big{\rVert}^{2}.$ (216)

Then, according to (210)-(216), we obtain

$\displaystyle\mathbb{E}F^{(c)}$
$\displaystyle(w^{t{+}1})\leq\mathbb{E}F^{(c)}(w^{t})-\left[\frac{\eta\beta(2Q{-}1)}{2}-2\eta^{2}L_{c}\beta^{2}Q^{2}\right]\mathbb{E}\left\lVert\nabla
F^{(c)}(w^{t})\right\rVert^{2}$ (217) $\displaystyle+8\eta^{3}\beta
Q^{3}L_{c}^{2}(1{+}2Q)(1{+}\beta^{2})\left(1{+}2\eta\beta
L_{c}\right)\tau\left[\sum\limits_{s{=}t{-}\tau}^{t}\sum\limits_{u{=}s{-}\tau}^{s}\mathbb{E}\left\lVert\nabla
F^{(c)}(w^{u})\right\rVert^{2}\right]$ (218) $\displaystyle+8\eta^{3}\beta
Q^{3}L_{c}^{2}(1{+}2Q)(\tau^{2}{+}1)(1{+}\beta^{2})\left(1{+}2\eta\beta
L_{c}\right)\left(\sigma_{c}^{2}+\gamma_{c}^{2}\right)$ (219)
$\displaystyle+2\eta^{2}L_{c}\beta^{2}Q^{2}\left(\sigma_{c}^{2}+\gamma_{c}^{2}\right)$
(220) $\displaystyle+\eta\beta Q^{2}\mu_{c}^{2},$ (221)

where by averaging the terms in (217)-(221), for $t=0,1,\dots T{-}1$, and
rearranging them (similar to (104)-(106), we can conclude the following
inequality:

$\displaystyle\frac{1-4\eta\beta
QL_{c}-16\eta^{2}Q^{2}L_{c}^{2}(1{+}2Q)\tau(\tau{+}1)^{2}(1{+}\beta^{2})\left(1{+}2\eta\beta
L_{c}\right)}{T}\sum\limits_{t=0}^{T{-}1}\mathbb{E}\left\lVert\nabla
F^{(c)}(w^{t})\right\rVert^{2}$
$\displaystyle\leq\frac{2\left(F^{(c)}(w^{0})-\mathbb{E}F^{(c)}(w^{T})\right)}{\eta\beta
QT}+2Q\mu_{c}^{2}$ (222)
$\displaystyle+16\eta^{2}Q^{2}L_{c}^{2}(1{+}2Q)(\tau^{2}{+}1)(1{+}\beta^{2})\left(1{+}2\eta\beta
L_{c}\right)\left(\sigma_{c}^{2}+\gamma_{c}^{2}\right)$ (223)
$\displaystyle+4\eta\beta QL_{c}\left(\sigma_{c}^{2}+\gamma_{c}^{2}\right)$
(224)

Finally, by fixing $\eta=\frac{1}{Q\sqrt{L_{c}T}}$, for $T\geq
288L_{c}(Q{+}7)(\tau{+}1)^{2}$, we obtain the sublinear convergence rate in
Theorem 3. ∎