11institutetext: Indian Institute of Technology Bombay, Mumbai, India
22institutetext: Carnegie Mellon University, Pittsburgh, PA, USA

# Multi-Model Federated Learning
with Provable Guarantees

Neelkamal Bhuyan 11 Sharayu Moharir 11 Gauri Joshi 22

###### Abstract

Federated Learning (FL) is a variant of distributed learning where edge
devices collaborate to learn a model without sharing their data with the
central server or each other. We refer to the process of training multiple
independent models simultaneously in a federated setting using a common pool
of clients as multi-model FL. In this work, we propose two variants of the
popular FedAvg algorithm for multi-model FL, with provable convergence
guarantees. We further show that for the same amount of computation, multi-
model FL can have better performance than training each model separately. We
supplement our theoretical results with experiments in strongly convex,
convex, and non-convex settings.

###### Keywords:

Federated Learning Distributed Learning Optimization

##  1 Introduction

Federated Learning (FL) is a form of distributed learning where training is
done by edge devices (also called clients) using their local data without
sharing their data with the central coordinator (also known as server) or
other devices. The only information shared between the clients and the server
is the update to the global model after local client training. This helps in
preserving the privacy of the local client dataset. Additionally, training on
the edge devices does not require datasets to be communicated from the clients
to the server, lowering communication costs. The single model federated
learning problem has been widely studied from various perspectives including
optimizing the frequency of communication between the clients and the server
[26], designing client selection algorithms in the setting where only a subset
of devices train the model in each iteration [14], and measuring the effect of
partial device participation on the convergence rate [19].

Closest to this work, in [3], the possibility of using federated learning to
train multiple models simultaneously using the same set of edge devices has
been explored. We refer to this as multi-model FL. In the setting considered
in [3], each device can only train one model at a time. The algorithmic
challenge is to determine which model each client will train in any given
round. Simulations illustrate that multiple models can indeed be trained
simultaneously without a sharp drop in accuracy by splitting the clients into
subsets in each round and use one subset to train each of the models. One key
limitation of [3] is the lack of analytical performance guarantees for the
proposed algorithms. In this work, we address this limitation of [3] by
proposing algorithms for multi-model FL with provable performance guarantees.

###  1.1 Our Contributions

In this work, we focus on the task of training $M$ models simultaneously using
a shared set of clients. We propose two variants of the Fed-Avg algorithm [22]
for the multi-model setting, with provable convergence guarantees. The first
variant called Multi-FedAvg-Random (MFA-Rand) partitions clients into $M$
groups in each round and matches the $M$ groups to the $M$ models in a
uniformly randomized fashion. Under the second variant called Multi-FedAvg-
Round Robin (MFA-RR), time is divided into frames such that each frame
consists of $M$ rounds. At the beginning of each frame, clients are
partitioned into $M$ groups uniformly at random. Each group then trains the
$M$ models in the $M$ rounds in the frame in a round-robin manner.

The error for a candidate multi-model federated learning algorithm
$\mathcal{P}$, for each model is defined as the distance between each model’s
global weight at round $t$ and its optimizer. Our analytical results show that
when the objective function is strongly convex and smooth, for MFA-Rand, an
upper bound on the error decays as $\mathcal{O}(1/\sqrt{T})$, and for MFA-RR,
the error decays as $\mathcal{O}(1/T)$. The latter result holds when local
stochastic gradient descent at the clients transitions to full gradient
descent over time. This allows MFA-RR to be considerably faster than
FedCluster[6], an algorithm similar to MFA-RR.

Further, we study the performance gain in multi-model FL over single-model
training under MFA-Rand. We show via theoretical analysis that training
multiple models simultaneously can be more efficient than training them
sequentially, i.e., training only one model at a time on the same set of
clients.

Via synthetic simulations we show that MFA-RR typically outperforms MFA-Rand.
Intuitively this is because under MFA-RR, each client trains each model in
every frame, while this is not necessary in the MFA-Rand. Our data-driven
experiments prove that training multiple models simultaneously is advantageous
over training them sequentially.

###  1.2 Related Work

The federated learning framework and the FedAvg algorithm was first introduced
in [22]. Convergence of FedAvg has been studies extensively under convexity
assumption [15, 19, 27] and non-convex setting [15, 20]. When data is
homogeneous across clients and all clients participate in each round, FedAvg
is known as LocalSGD. LocalSGD is easier to analyse because of the
aforementioned assumptions. LocalSGD has been proved to be convergent with
strictly less communication in [24]. LocalSGD has been proved to be convergent
in non-convex setting [8, 28, 25].

FedProx [17] handles data heterogeneity among clients and convergences in the
setting where the data across clients is non-iid. The key difference between
FedAvg and FedProx is that the latter adds an addition proximal term to the
loss function. However, the analysis of FedProx requires the proximal term to
be present and, therefore, does not serve as proof for convergence of FedAvg.

Personalised FL is an area where multiple local models are trained instead of
a global model. The purpose of having multiple models [10] is to have the
local models reflect the specific characteristics of their data. [13, 9, 1]
involved using a combination of global and local models. Although there are
multiple models, the underlying objective is same. This differentiates
personalised FL from our setting, which involves multiple _unrelated_ models.

Clustered Federated Learning proposed in [23] involved performing FedAvg and
bi-partitioning client set in turn until convergence is reached. The idea here
was to first perform vanilla FL. Then, recursively bi-partition the set of
clients into two clusters and perform within the clusters until a more refined
stopping criterion is met. The second step is a post-processing technique. [5]
studies distributed SGD in heterogeneous networks, where distributed SGD is
performed within sub-networks, in a decentralized manner, and model averaging
happens periodically among neighbouring sub-networks.

FedCluster proposed in [6] is very similar to second algorithm we propose in
this work. In [6], convergence has been guaranteed in a non-convex setting.
However, the advantages of a convex loss function or the effect of data sample
size has not been explored in this work. Further, the clusters, here, are
fixed throughout the learning process.

Training multiple models in a federated setting has been explored in [16]
also. However, the setting and the model training methodology are different
from ours [3]. In [16], client distribution among models has been approached
as an optimization problem and a heuristic algorithm has been proposed.
However, neither an optimal algorithm is provided nor any convergence
guarantees.

##  2 Setting

We consider the setting where $M$ models are trained simultaneously in a
federated fashion. The server has global version of each of the $M$ models and
the clients have local datasets (possibly heterogeneous) for every model. The
total number of clients available for training is denoted by $N$. We consider
full device participation with the set of clients divided equally among the
$M$ models in each round. In every round, each client is assigned _exactly one
model_ to train. Each client receives the current global weights of the model
it was assigned and performs $E$ iterations of stochastic gradient descent
locally at a fixed learning rate of $\eta_{t}$ (which can change across rounds
indexed by $t$) using the local dataset. It then sends the local update to its
model, back to the server. The server then takes an average of the received
weight updates and uses it to get the global model for the next round.

Algorithm 1 details the training process of multi-model FL with any client
selection algorithm $\mathcal{P}$. Table 1 lists out the variables used in the
training process and their purpose.

Table 1: Common variables used in algorithms Variable Name | Description
---|---
$n$ | round number
$M$ | Number of Models
$\mathcal{S}_{T}$ | Set of all clients
$N$ | Total number of clients = $|\mathcal{S}_{T}|$
$\mathcal{P}$ | Client selection algorithm
trainModel[$c$] | Model assigned to client $c$
globalModel[$m$] | Global weights of model $m$
localModel[$m,c$] | Weights of $m^{\text{th}}$ model of client $c$
Algorithm 1 Pseudo-code for $M$-model training at server

Input: $\mathcal{S}_{T}$, algorithm $\mathcal{P}$
Initialize: globalModel, localModel

1:globalModel$[m]$ $\leftarrow$ 0 $\forall$ $m\in\\{1,2,..,M\\}$

2:Initialise parameters relevant to algorithm $\mathcal{P}$ in round 0

3:repeat

4: localModel$[m,c]$ $\leftarrow$ 0 $\forall$
$c\in\mathcal{S}_{T},m\in\\{1,2,..,M\\}$

5: Update parameters relevant to algorithm $\mathcal{P}$

6: trainModel $\leftarrow$ call function for $\mathcal{P}$ $\triangleright$
MFA_Rand(t) or MFA_RR(t)

7: for $c\in\mathcal{S}_{T}$ do

8: $m$ $\leftarrow$ trainModel$[c]$

9: localModel$[m,c]$ $\leftarrow$ globalModel$[m]$

10: localUpdate[m,c] $\leftarrow$ update for localModel$[m,c]$ after $E$
iterations of gradient descent

11: end for

12: for $m\in\\{1,2,..,M\\}$ do

13: globalUpdate[m] $\leftarrow$ weighted average of localUpdate[m,c]

14: globalModel$[m]$ $\leftarrow$ globalModel$[m]$ \- globalUpdate[m]

15: end for

16:until $n$ = max iterations

The global loss function of the $m^{\text{th}}$ model is denoted by
$F^{(m)}(\textbf{w})$, the local loss function of the $m^{\text{th}}$ model
for the $k^{\text{th}}$ client is denoted by $F_{k}^{(m)}(\textbf{w})$. For
simplicity, we assume that, for every model, each client has same number of
data samples, $\mathcal{N}$. We therefore have the following global objective
function for $m^{\text{th}}$ model,

$F^{(m)}(\textbf{w})=\frac{1}{N}\sum_{k=1}^{N}F_{k}^{(m)}(\textbf{w}).$ (1)

Additionally,
$\Gamma^{(m)}=\min(F^{(m)})-\frac{1}{N}\sum_{k=1}^{N}\min(F_{k}^{(m)})\geq 0$.
We make some standard assumptions on the local loss function, also used in [7,
19]. These are,

###### Assumption 1

All $F_{k}^{(m)}$ are $\mu$-strongly convex.

###### Assumption 2

All $F_{k}^{(m)}$ are $L$-smooth.

###### Assumption 3

Stochastic gradients are bounded: $\mathbb{E}||\nabla
F_{k}^{(m)}(\textbf{w},\xi)||^{2}\leq(G^{(m)})^{2}$.

###### Assumption 4

For each client k,
$F_{k}^{(m)}(\textbf{{w}})=\frac{1}{\mathcal{N}}\displaystyle\sum_{y=1}^{\mathcal{N}}f_{k,y}^{(m)}(\textbf{w})$,
where $f_{k,y}^{(m)}$ is the loss function of the $y^{th}$ data point of the
$k^{th}$ client’s $m^{th}$ model. Then for each $f_{k,y}^{(m)}$,

$||\nabla
f_{k,y}^{(m)}(\textbf{w})||^{2}\leq\beta_{1}^{(m)}+\beta_{2}^{(m)}||\nabla
F_{k}^{(m)}(\textbf{w})||^{2},$

for some constants $\beta_{1}^{(m)}\geq 0$ and $\beta_{2}^{(m)}\geq 1$.

The last assumption is standard in the stochastic optimization literature [2,
11].

###  2.1 Performance Metric

The error for a candidate multi-model federated learning algorithm
$\mathcal{P}$’s is the distance between the $m^{\text{th}}$ model’s global
weight at round $t$, denoted by $\overline{\textbf{w}}^{(m)}_{\mathcal{P},t}$
and the minimizer of $F^{(m)}$, denoted by $\textbf{w}^{(m)}_{*}$. Formally,

$\Delta^{(m)}_{\mathcal{P}}(t)=\mathbb{E}||\overline{\textbf{w}}^{(m)}_{\mathcal{P},t}-\textbf{w}^{(m)}_{*}||.$
(2)

##  3 Algorithms

We consider two variants of the Multi-FedAvg algorithm proposed in [3]. For
convenience we assume that $N$ is an integral multiple of $M$.

###  3.1 Multi-FedAvg-Random (MFA-Rand)

The first variant partitions the set of clients $\mathcal{S}_{T}$ into $M$
equal sized subsets
$\\{\mathcal{S}_{1}^{t},\mathcal{S}_{2}^{t},...,\mathcal{S}_{M}^{t}\\}$ in
every round $t$. The subsets are created uniformly at random independent of
all past and future choices. The $M$ subsets are then matched to the $M$
models with the matching chosen uniformly at random.

Algorithm 2 details the sub-process of MFA-Rand invoked when client-model
assignment step (step 6) runs in Algorithm 1. An example involving 3 models
over 6 rounds has been worked out in Table 2.

Table 2: MFA-Rand over 6 rounds for 3 models.  Round | Model 1 | Model 2 | Model 3
---|---|---|---
1 | $\mathcal{S}_{1}^{1}$ | $\mathcal{S}_{2}^{1}$ | $\mathcal{S}_{3}^{1}$
2 | $\mathcal{S}_{1}^{2}$ | $\mathcal{S}_{2}^{2}$ | $\mathcal{S}_{3}^{2}$
3 | $\mathcal{S}_{1}^{3}$ | $\mathcal{S}_{2}^{3}$ | $\mathcal{S}_{3}^{3}$
4 | $\mathcal{S}_{1}^{4}$ | $\mathcal{S}_{2}^{4}$ | $\mathcal{S}_{3}^{4}$
5 | $\mathcal{S}_{1}^{5}$ | $\mathcal{S}_{2}^{5}$ | $\mathcal{S}_{3}^{5}$
6 | $\mathcal{S}_{1}^{6}$ | $\mathcal{S}_{2}^{6}$ | $\mathcal{S}_{3}^{6}$
Algorithm 2 Pseudo-code for MFA-Rand

1:procedure MFA_Rand($t$)

2:
$\\{\mathcal{S}_{1}^{t},\mathcal{S}_{2}^{t},...,\mathcal{S}_{M}^{t}\\}\leftarrow$Partition
$\mathcal{S}_{T}$ randomly into $M$ disjoint subsets

3: for
$\mathcal{S}\in\\{\mathcal{S}_{1}^{t},\mathcal{S}_{2}^{t},...,\mathcal{S}_{M}^{t}\\}$
do

4: if $\mathcal{S}=\mathcal{S}_{j}^{t}$ then

5: trainModel[$c$] $\leftarrow$ $j$ $\forall$ $c\in\mathcal{S}$

6: end if

7: end for

8: return: trainModel

9:end procedure

###  3.2 Multi-FedAvg-Round Robin (MFA-RR)

The second variant partitions the set of clients into $M$ equal sized subsets
once every $M$ rounds. The subsets are created uniformly at random independent
of all past and future choices. We refer to the block of $M$ rounds during
which the partitions remains unchanged as a frame. Within each frame, each of
the $M$ subsets is mapped to each model exactly once in a round-robin manner.
Specifically, let the subsets created at the beginning of frame $l$ be denoted
by $\mathcal{S}_{j}^{l}$ for $1\leq j\leq M$. Then, in the $u^{\text{th}}$
round in frame $l$ for $1\leq u\leq M$, $\mathcal{S}_{j}^{l}$ is matched to
model $((j+u-2)\mod M)+1$.

Algorithm 3 details the sub-process of MFA-RR invoked when client-model
assignment step (step 6) runs in Algorithm 1. An example involving 3 models
over 6 rounds has been worked out in Table 3.

Table 3: MFA-RR over 6 rounds (2 frames) for 3 models. Round | Model 1 | Model 2 | Model 3
---|---|---|---
1 | $\mathcal{S}_{1}^{1}$ | $\mathcal{S}_{2}^{1}$ | $\mathcal{S}_{3}^{1}$
2 | $\mathcal{S}_{3}^{1}$ | $\mathcal{S}_{1}^{1}$ | $\mathcal{S}_{2}^{1}$
3 | $\mathcal{S}_{2}^{1}$ | $\mathcal{S}_{3}^{1}$ | $\mathcal{S}_{1}^{1}$
4 | $\mathcal{S}_{1}^{2}$ | $\mathcal{S}_{2}^{2}$ | $\mathcal{S}_{3}^{2}$
5 | $\mathcal{S}_{3}^{2}$ | $\mathcal{S}_{1}^{2}$ | $\mathcal{S}_{2}^{2}$
6 | $\mathcal{S}_{2}^{2}$ | $\mathcal{S}_{3}^{2}$ | $\mathcal{S}_{1}^{2}$
Algorithm 3 Pseudo-code for MFA-RR

1:procedure MFA_RR($t$)

2: if $t\mod M=1$ then

3: $l=\frac{t-1}{M}+1$

4:
$\\{\mathcal{S}_{1}^{l},\mathcal{S}_{2}^{l},...,\mathcal{S}_{M}^{l}\\}\leftarrow$
Partition $\mathcal{S}_{T}$ randomly into $M$ disjoint subsets

5: end if

6: for
$\mathcal{S}\in\\{\mathcal{S}_{1}^{l},\mathcal{S}_{2}^{l},...,\mathcal{S}_{M}^{l}\\}$
do

7: if $\mathcal{S}=\mathcal{S}_{j}^{l}$ then

8: trainModel[$c$] $\leftarrow$ $((j+t-2)\mod M)+1$ $\forall$
$c\in\mathcal{S}$

9: end if

10: end for

11: return: trainModel

12:end procedure

###### Remark 1

An important difference between the two algorithms is that under MFA-RR, each
client-model pair is used exactly once in each frame consisting of $M$ rounds,
whereas under MFA-Rand, a specific client-model pair is not matched in $M$
consecutive time-slots with probability $\left(1-\frac{1}{M}\right)^{M}$ .

##  4 Convergence of MFA-Rand and MFA-RR

In this section, we present our analytical results for MFA-Rand and MFA-RR.

###### Theorem 4.1

For MFA-Rand, under Assumptions 1, 2, 3, 4 and with
$\eta_{t}=\frac{\beta}{t+\gamma}$, where $\beta>\frac{1}{\mu}$ and
$\gamma>4L\beta-1$, we have

$\Delta_{\text{MFA-Rand}}^{(m)}(t)\leq\frac{\sqrt{\nu}}{\sqrt{t+\gamma}}\text{
}M\geq 1\text{ and }E\geq 1,$

where
$\nu=\max\left\\{\frac{\beta^{2}(B+C)}{\beta\mu-1},\mathbb{E}||\overline{\textbf{w}}^{(m)}_{\text{MFA-
Rand},1}-\textbf{w}^{(m)}_{*}||^{2}(1+\gamma)\right\\},B=6L\Gamma^{(m)}+(1/N^{2})\sum_{k=1}^{N}(\sigma_{k}^{(m)})^{2}+8(E-1)^{2}(G^{(m)})^{2},C=\frac{M-1}{N-1}E^{2}(G^{(m)})^{2}$
and $(\sigma_{k}^{(m)})^{2}=4(\beta_{1}+\beta_{2}(G^{(m)})^{2})$.

The result follows from the convergence of FedAvg with partial device
participation in [19]. Note that $B$ and $C$ influence the lower bound on
number of iterations, $T_{\text{MFA-Rand}}(\epsilon)$, required to reach a
certain accuracy. Increasing the number of models, $M$, increases $C$ which
increases $T_{\text{MFA-Rand}}(\epsilon)$.

###### Theorem 4.2

Consider MFA-Rand, under Assumptions 1, 2, 3, 4 and
$\eta_{t}=\frac{\beta}{1+\left\lfloor\frac{t}{M}\right\rfloor+\gamma}$, where
$\beta>\frac{1}{\mu}$ and $\gamma>\beta L-1$. Further, $\mathcal{N}_{s}(t)$ is
the sample size for SGD iterations at clients in round $t$. If

$\frac{\mathcal{N}-\mathcal{N}_{s}(t)}{\mathcal{N}}\leq\eta_{t}\left(\frac{V}{2E\sqrt{\beta_{1}+\beta_{2}G^{2}}}\right)$

for some $V\geq 0$, $\beta_{1}=\displaystyle\max_{m}\beta_{1}^{(m)}$ and
$\beta_{2}=\displaystyle\max_{m}\beta_{2}^{(m)}$, then,

$\Delta_{\text{MFA-RR}}^{(m)}(t)\leq\frac{\phi}{\frac{t}{M}+\gamma}\text{
}\forall\text{ }M\geq 1\text{ and }E\geq 1,$

where $\phi=\frac{\beta
EG^{(m)}(M-1)}{M}+\max\left\\{\frac{\beta^{2}(Y+Z+V)}{\beta\mu-1},(1+\gamma)\Delta^{(m)}_{\text{MFA-
RR}}(1)\right\\},$
$Y=\frac{LG^{(m)}E^{2}(M-1)}{2M}$ and $Z=LG^{(m)}E(E-1)$.

Here, we require that the SGD iterations at clients have data sample
converging sub-linearly to the full dataset. For convergence, the only
requirement is $\frac{\mathcal{N}-\mathcal{N}_{s}(t)}{\mathcal{N}}$ to be
proportional to the above defined $\eta_{t}$.

We observe that $Y$, $Z$ and $V$ influence the lower bound on number of
iterations, $T_{\text{MFA-RR}}(\epsilon)$, required to reach a certain
accuracy. Increasing the number of models, $M$, increases $Y$ which increases
$T_{\text{MFA-RR}}(\epsilon)$.

A special case of Theorem 4.2 is when we employ full gradient descent instead
of SGD at clients. Naturally, in this case, $V=0$.

###### Corollary 1

For MFA-RR with full gradient descent at the clients, under Assumptions 1, 2,
3, 4 and
$\eta_{t}=\frac{\beta}{1+\left\lfloor\frac{t}{M}\right\rfloor+\gamma}$,

$\Delta_{\text{MFA-
RR}}^{(m)}(t)\leq\frac{\phi^{\prime}}{\frac{t}{M}+\gamma}\text{ }\forall\text{
}M\geq 1\text{ and }E\geq 1,$

where $\phi^{\prime}=\frac{\beta
EG^{(m)}(M-1)}{M}+\max\left\\{\frac{\beta^{2}(Y+Z)}{\beta\mu-1},(1+\gamma)\Delta^{(m)}_{\text{MFA-
RR}}(1)\right\\}$,
$Y=\frac{LG^{(m)}E^{2}(M-1)}{2M}$ and $Z=LG^{(m)}E(E-1)$.

###### Remark 2

MFA-RR, when viewed from perspective of one of the $M$ models, is very similar
to FedCluster. However, there are some key differences between the analytical
results.

First, FedCluster assumes that SGD at client has fixed bounded variance for
any sample size (along with Assumption 3). This is different from Assumption 4
of ours. When Assumption 4 is coupled with Assumption 3, we get sample size
dependent bound on the variance. A smaller variance is naturally expected for
a larger data sample. Therefore, our assumption is less restrictive.

Second, the effect of increasing sample size (or full sample) has not been
studied in [6]. We also see the effect of strong convexity on the speed of
convergence. The convergence result from [6] is as follows,

$\frac{1}{T}\sum_{j=0}^{T-1}\mathbb{E}||\nabla
F(\overline{\textbf{w}}_{jM})||^{2}\leq\mathcal{O}\left(\frac{1}{\sqrt{T}}\right).$

If we apply the strong convexity assumption to this result and use that
$\mu||x-x_{*}||\leq||\nabla F(x)||$, we get

$\frac{\mu^{2}}{T}\sum_{j=0}^{T-1}\mathbb{E}||\overline{\textbf{w}}_{jM}-\textbf{w}_{*}||^{2}\leq\mathcal{O}\left(\frac{1}{\sqrt{T}}\right).$

Applying Cauchy-Schwartz inequality on LHS we get,

$\left(\frac{1}{T}\sum_{j=0}^{T-1}\mathbb{E}||\overline{\textbf{w}}_{jM}-\textbf{w}_{*}||\right)^{2}\leq\frac{1}{T}\sum_{j=0}^{T-1}\mathbb{E}||\overline{\textbf{w}}_{jM}-\textbf{w}_{*}||^{2}.$

Finally, we have

$\frac{1}{T}\sum_{j=0}^{T-1}\mathbb{E}||\overline{\textbf{w}}_{jM}-\textbf{w}_{*}||\leq\mathcal{O}\left(\frac{1}{T^{1/4}}\right),$

for any sampling strategy. With an increasing sample size (or full sample
size), we can obtain $\mathcal{O}(1/T)$ convergence. This is a significant
improvement over the convergence result of FedCluster.

##  5 Advantage of Multi-Model FL over single model FL

We quantify the advantage of Multi-Model FL over single model FL by defining
the gain of a candidate multi-model Federated Learning algorithm $\mathcal{P}$
over FedAvg [22], which trains only one model at a time.
Let $T_{1}(\epsilon)$ be the number of rounds needed by one of the $M$ models
using FedAvg to reach an accuracy level (distance of model’s current weight
from its optimizer) of $\epsilon$. We assume that all $M$ models are of
similar complexity. This means we expect that each model reaches the required
accuracy in roughly the same number of rounds. Therefore, cumulative number of
rounds needed to ensure all $M$ models reach an accuracy level of $\epsilon$
using FedAvg is $MT_{1}(\epsilon)$. Further, let the number of rounds needed
to reach an accuracy level of $\epsilon$ for all $M$ models under
$\mathcal{P}$ be denoted by $T_{\mathcal{P}}(M,\epsilon)$. We define the gain
of algorithm $\mathcal{P}$ for a given $\epsilon$ as

$g_{\mathcal{P}}(M,\epsilon)=\frac{MT_{1}(\epsilon)}{T_{\mathcal{P}}(M,\epsilon)}.$
(3)

Note that FedAvg and $\mathcal{P}$ use the same number of clients in each
round, thus the comparison is fair. Further, we use the bounds in Theorem 4.1
and Theorem 4.2 as proxies for calculating $T_{\mathcal{P}}(M,\epsilon)$ for
MFA-Rand and MFA-RR respectively.

###### Theorem 5.1

When $\epsilon<\displaystyle\min_{m}\Delta_{\text{MFA-Rand}}^{(m)}(1)$ and
$M\leq\frac{N}{2}$, the following holds for the gain of $M$-model MFA-Rand
over running FedAvg $M$ times

$\displaystyle g_{\text{MFA-Rand}}(M,\epsilon)$ $\displaystyle>1\text{
}\forall\text{ }M>1$ $\displaystyle\frac{d}{dM}g_{\text{MFA-
Rand}}(M,\epsilon)$ $\displaystyle>0\text{ }\forall\text{ }M\geq 1$

for all $E\geq 2$ and for $E=1$ when
$N>1+\displaystyle\max_{m}\left\\{\frac{6L\Gamma^{(m)}}{(G^{(m)})^{2}}\right\\}$.

We get that gain increases with $M$ upto $M=N/2$, after which we have the
$M=N$ case. At $M=N$, each model is trained by only one client, which is too
low, especially when $N$ is large.

For the case of $E=1$, Theorem 5.1 puts a lower bound on $N$. However, the
$E=1$ case is rarely used in practice. One of the main advantages of FL is the
lower communication cost due to local training. This benefit is not utilised
when $E=1$.

##  6 Simulations in strongly convex setting

###  6.1 Simulation Framework

We take inspiration from the framework presented in [19] where a quadratic
loss function, which is strongly convex, is minimized in a federated setting.
We employ MFA-Rand and MFA-RR algorithms and compare their performance in this
strongly convex setting. In addition to that, we also measure the gain of MFA-
Rand and MFA-RR over sequentially running FedAvg in this strongly convex
setting.
The global loss function is

$F(w)=\frac{1}{2N}\left(\textbf{w}^{T}\textbf{A}\textbf{w}-2\textbf{b}^{T}\textbf{w}\right)+\frac{\mu}{2}||\textbf{w}||^{2},$
(4)

where $N>1$, $\textbf{A}\in\mathcal{\textbf{R}}^{(Np+1)\times(Np+1)}$,
$\textbf{w}\in\mathcal{\textbf{R}}^{(Np+1)}$ and $\mu>0$. We have,

$\textbf{A}=\sum_{k=1}^{N}\textbf{A}_{k}$ (5)
$\textbf{b}=\sum_{k=1}^{N}\textbf{b}_{k}.$ (6)

Here the $k^{th}$ pair $(\textbf{A}_{k},\textbf{b}_{k})$ represents the
$k^{th}$ client. Following is the definition of $\textbf{A}_{k}$

$\textbf{A}_{k}=\begin{cases}\textbf{B}_{k}+\textbf{E}_{1,1}&k=1\\\
\textbf{B}_{k}&1<k<N\\\ \textbf{B}_{k}+\textbf{E}_{Np+1,Np+1}&k=N,\end{cases}$
(7)

where $\textbf{E}_{i,j}$ is a matrix where $(i,j)$ element is 1 and rest all
are 0. $\textbf{B}_{k}$ is defined as follows

$\left(\begin{array}[]{ccc}\textbf{0}_{(k-1)p\times(k-1)p}&&\\\
&\left(\begin{array}[]{ccccc}1&-1&&&\\\ -1&2&-1&&\\\ &-1&\ddots&\ddots&\\\
&&\ddots&2&-1\\\ &&&-1&1\end{array}\right)&\\\
&&\textbf{0}_{(N-k)p\times(N-k)p}\end{array}\right)$

and $\textbf{b}_{k}$ is defined as follows

$\textbf{b}_{k}=\begin{cases}\textbf{e}_{k}&k=1\\\ \textbf{0 }&1<k\leq
N.\end{cases}$ (8)

We finally define local loss function of the $k^{\text{th}}$ client as

$F_{k}(\textbf{w})=\frac{1}{2}\left(\textbf{w}^{T}\textbf{A}_{k}\textbf{w}-2\textbf{b}_{k}^{T}\textbf{w}\right)+\frac{\mu}{2}||\textbf{w}||^{2},$
(9)

which satisfies our problem statement $F=\frac{1}{N}\sum_{k=1}^{N}F_{k}$.

###### Remark 3

We simulate the minimization of a single global loss function while talking
about multi-model learning. The reason behind this is that we are doing these
simulations from the perspective of one of the $M$ models. Therefore,
$M$-model MFA-Rand boils down to sampling $N/M$ clients independently every
round while $M$-model MFA-RR remains the same (going over subsets
$\\{\mathcal{S}_{1}^{l},\mathcal{S}_{2}^{l},..,\mathcal{S}_{M}^{l}\\}$ in
frame $l$). Furthermore, the gain simulations here assume that all $M$ models
are of the same complexity.

###  6.2 Comparison of MFA-Rand and MFA-RR

We consider the scenario where $N=24$, $p=4$ and $\mu=2\times 10^{-4}$. We
take $E=5$, meaning 5 local SGD iterations at clients. We track the log
distance of the current global loss from the global loss minimum, that is

$gap(t)=\log_{10}(F(w)-F(w_{*}))$ (10)

for 1000 rounds. We consider both constant $(\eta_{t}=0.1)$ and decaying
learning rate $\left(\eta_{t}=\frac{30}{100+t}\right)$for $M=2$ and $M=12$.

(a) Averaged over 20 sample runs

(b) 20 sample runs each

Figure 1: $M=2$, constant learning rate

(a) Averaged over 20 sample runs

(b) 20 sample runs each

Figure 2: $M=2$, decaying learning rate

As one can observe in Fig. 1(a) and Fig. 2(a), we have similar mean
performance for MFA-Rand and MFA-RR. However, Fig. 1(b) and Fig. 2(b) reveal
that the randomness involved in MFA-Rand is considerably higher than that in
MFA-RR, showing the latter to be more reliable.

(a) Averaged over 20 sample runs

(b) 20 sample runs each

Figure 3: $M=12$, constant learning rate

(a) Averaged over 20 sample runs

(b) 20 sample runs each

Figure 4: $M=12$, decaying learning rate

It is evident from Fig. 3(a) and Fig. 4(a) that MFA-RR, on an average,
performs better than MFA-Rand when $M$ is high. Again, Fig.3(b) and Fig. 4(b)
show that MFA-Rand has considerably higher variance than MFA-RR.

###### Remark 4

In this set of simulations, each client performs full gradient descent. While
the analytical upper bounds on errors suggest an order-wise difference in the
performance of MFA-RR and MFA-Rand, we do not observe that significant a
difference between the performance of the two algorithms. This is likely
because our analysis of MFA-RR exploits the fact that each client performs
full gradient descent, while the analysis of MFA-Rand adapted from [19] does
not.

###  6.3 Gain vs $M$

We test with $N=24$ clients for $M\leq 12$ for $E=1,5$ and $10$. Gain vs $M$
plots in Fig. 5 show that gain increases with $M$ for both MFA-Rand and MFA-
RR.

(a) MFA-Rand

(b) MFA-RR

Figure 5: Gain vs $M$ in strongly convex setting

##  7 Data Driven Experiments on Gain

We use Synthetic(1,1) [17, 18] and CelebA [4][21] datasets for these
experiments. The learning task in Synthetic(1,1) is multi-class logistic
regression classification of feature vectors. Synthetic(1,1)-A involves 60
dimensional feature vectors classified into 5 classes while Synthetic(1,1)-B
involves 30 dimensional feature vectors classified into 10 classes. CelebA
dataset involves binary classification of face images based on a certain
facial attribute, (for example, blond hair, smiling, etc) using convolutional
neural networks (CNNs). The dataset has many options for the facial attribute.

The multi-model FL framework for training multiple unrelated models
simultaneously was first introduced in our previous work [3]. We use the same
framework for these experiments. We first find the gain vs $M$ trend for
Synthetic(1,1)-A, Synthetic(1,1)-B and CelebA. Then, we simulate a real-world
scenarios where each of the $M$ models is a different learning task.

###  7.1 Gain vs $M$

Here, instead of giving $M$ different tasks as the $M$ models, we have all $M$
models as the same underlying task. The framework, however, treats the $M$
models as independent of each other. This ensures that the $M$ models are of
equal complexity.

We plot gain vs $M$ for two kinds of scenarios. First, when all clients are
being used in a round. Theorem 5.1 assumes this scenario. We call it full
device participation as all clients are being used. Second, when only a
sample, of the set of entire clients, is selected to be used in the round (and
then distributed among the models). We call this partial device participation
as a client has a non-zero probability of being idle during a round.

####  7.1.1 Full device participation:

For Synthetic(1,1)-A, we have $N=100$ clients and $T_{1}=70$. During single
model FedAvg, we get 51% training accuracy and 51% test accuracy at the end of
70 rounds.

Synthetic(1,1)-B, we have $N=100$ clients and $T_{1}=70$. During single model
FedAvg, we get 42.7% training accuracy and 42.8% test accuracy at the end of
70 rounds.

For CelebA, we have 96 clients and $T_{1}=75$. We get 79% training accuracy
and 68% test accuracy at the end of 75 rounds of single model FedAvg.

(a) Synthetic(1,1)-A

(b) Synthetic(1,1)-B

(c) CelebA

Figure 6: Gain vs $M$ for full device participation

For full device participation, we observe from Fig. 6 that gain increases with
$M$ for both Synthetic(1,1) and CelebA datasets with the trend being sub-
linear in nature.

####  7.1.2 Partial device participation:

For Synthetic(1,1)-A, we have $N=200$ clients (out of which 32 are sampled
every round) and $T_{1}=200$. During single model FedAvg, we get 61.1%
training accuracy and 61.3% test accuracy at the end of 200 rounds.

For Synthetic(1,1)-B, we have $N=200$ clients (out of which 32 are sampled
every round) and $T_{1}=200$. During single model FedAvg, we get 58.4%
training accuracy and 57.7% test accuracy at the end of 200 rounds.

For CelebA, we have 96 clients (out of which 24 are sampled every round) and
$T_{1}=75$. We get 78% training accuracy and 71.5% test accuracy at the end of
75 rounds of single model FedAvg.

(a) Synthetic(1,1)-A

(b) Synthetic(1,1)-B

(c) CelebA

Figure 7: Gain vs $M$ for partial device participation

When there is partial device participation, for both datasets, we observe in
Fig. 7 that gain increases with $M$ for the most part while decreasing at some
instances. Although, there are some dips, gain is always found to be more than
1.

###### Remark 5

It is important to note that the learning task in CelebA dataset invloves
CNNs, rendering it a non-convex nature. This, however, does not severely
impact the gain, as we still observe it to always increase with $M$ for full
device participation.

###### Remark 6

Although, Theorem 5.1 assumes full device participation, we see the benefit of
multi-model FL in partial device participation scenario. For all three
datasets, gain is always found to be significantly greater than 1.

###  7.2 Real-world Scenarios

We perform two types of real world examples, one involving models that are
similar in some aspect and the other involving completely different models. In
these experiments, $T_{1}$ denotes the number of rounds for which single model
FedAvg was been run for each model. Further, $T_{M}$ denotes the number of
rounds of multi-model FL, after which each model an accuracy that is at least
what was achieved with $T_{1}$ rounds of single model FedAvg.

####  7.2.1 Similar models:

First one tests Theorem 5.1 where each of the $M(=9)$ models is a binary image
classification based on a unique facial attribute, using CelebA dataset. Table
4 shows the results of our experiment.

Based on the the values of $T_{1}$ and $T_{M}$ from Table 4, we have the
following for training and testing cases.

  * •

Gain in training = $9\times 50/117=\textbf{3.846}$

  * •

Gain in testing = $9\times 50/126=\textbf{3.571}$

Table 4: MFA-RR training 9 different CNN models Facial attribute | Train Accuracy | Test Accuracy
---|---|---
for classification | $T_{1}=50$ | $T_{M}=117$ | $T_{1}=50$ | $T_{M}=126$
Eyeglasses | 74.7 | 84.6 | 69.1 | 71.9
Baldness | 74.0 | 74.5 | 66.8 | 69.4
Goatee | 74.3 | 83.5 | 64.7 | 68.7
Wearing Necklace | 73.3 | 80.3 | 66.2 | 72.6
Smiling | 72.0 | 78.7 | 76.0 | 79.7
Moustache | 74.1 | 82.1 | 65.4 | 72.1
Male | 77.1 | 85.0 | 58.7 | 63.5
Wearing Lipstick | 75.4 | 83.8 | 65.9 | 72.7
Double Chin | 75.3 | 83.9 | 63.9 | 69.3

####  7.2.2 Completely different models:

In the second one, we do a mixed model experiment where one model is logistic
regression (Synthetic(1,1) with 60 dimensional vectors into 5 classes) and the
other model is CNN (binary classification of face images based on presence of
eyeglasses).
Based on $T_{1}$ and $T_{M}$ from Table 5, we get the following values of gain
for training and testing cases,

  * •

Gain in training = $2\times 100/100=\textbf{2.0}$

  * •

Gain in testing = $2\times 100/142=\textbf{1.41}$

Table 5: MFA-RR training logistic regression and convolutional NN simultaneously Model | Train Accuracy | Test Accuracy
---|---|---
Type | $T_{1}=100$ | $T_{M}=100$ | $T_{1}=100$ | $T_{M}=142$
Logistic Regression | 51.9 | 52.4 | 52.8 | 55.6
Convolutional NN | 86.7 | 87.2 | 75.8 | 77.5

##  8 Conclusions

In this work, we focus on the problem of using Federated Learning to train
multiple independent models simultaneously using a shared pool of clients. We
propose two variants of the widely studied FedAvg algorithm, in the multi-
model setting, called MFA-Rand and MFA-RR, and show their convergence. In case
of MFA-RR, we show that an increasing data sample size (for client side SGD
iterations), helps improve the speed of convergence greatly
$\left(\mathcal{O}\left(\frac{1}{T}\right)\text{ instead of
}\mathcal{O}\left(\frac{1}{T^{1/4}}\right)\right)$.

Further, we propose a performance metric to access the advantage of multi-
model FL over single model FL. We characterize conditions under which running
MFA-Rand for $M$ models simultaneously is advantageous over running single
model FedAvg for each model sequentially. We perform experiments in strongly
convex and convex settings to corroborate our analytical results. By running
experiments in a non-convex setting, we see the benefits of multi-model FL in
deep learning. We also run experiments that are out of the scope of the
proposed setting. These were the partial device participation experiments and
the real world scenarios. Here also we see an advantage in training multiple
models simultaneously.

Further extensions to this work include theoretical analysis of partial device
participation scenarios, and convergence guarantees, if any, for unbiased
client selection algorithms [3] in multi-model FL.

## References

  * [1] Agarwal, A., Langford, J., Wei, C.Y.: Federated residual learning. arXiv preprint arXiv:2003.12880 (2020)
  * [2] Bertsekas, D.P., Tsitsiklis, J.N.: Neuro-dynamic programming. Athena Scientific (1996)
  * [3] Bhuyan, N., Moharir, S.: Multi-model federated learning. In: 2022 14th International Conference on COMmunication Systems & NETworkS (COMSNETS). pp. 779–783. IEEE (2022)
  * [4] Caldas, S., Duddu, S.M.K., Wu, P., Li, T., Konečnỳ, J., McMahan, H.B., Smith, V., Talwalkar, A.: Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01097 (2018)
  * [5] Castiglia, T., Das, A., Patterson, S.: Multi-level local sgd for heterogeneous hierarchical networks. arXiv preprint arXiv:2007.13819 (2020)
  * [6] Chen, C., Chen, Z., Zhou, Y., Kailkhura, B.: Fedcluster: Boosting the convergence of federated learning via cluster-cycling. In: 2020 IEEE International Conference on Big Data (Big Data). pp. 5017–5026 (2020). https://doi.org/10.1109/BigData50022.2020.9377960
  * [7] Cho, Y.J., Wang, J., Joshi, G.: Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint arXiv:2010.01243 (2020)
  * [8] Coppola, G.F.: Iterative parameter mixing for distributed large-margin training of structured predictors for natural language processing. PhD Thesis (2015)
  * [9] Deng, Y., Kamani, M.M., Mahdavi, M.: Adaptive personalized federated learning. arXiv preprint arXiv:2003.13461 (2020)
  * [10] Eichner, H., Koren, T., McMahan, B., Srebro, N., Talwar, K.: Semi-cyclic stochastic gradient descent. In: International Conference on Machine Learning. pp. 1764–1773. PMLR (2019)
  * [11] Friedlander, M.P., Schmidt, M.: Hybrid deterministic-stochastic methods for data fitting. SIAM Journal on Scientific Computing 34(3), A1380–A1405 (2012)
  * [12] Gurbuzbalaban, M., Ozdaglar, A., Parrilo, P.A.: Convergence rate of incremental gradient and incremental newton methods. SIAM Journal on Optimization 29(4), 2542–2565 (2019)
  * [13] Hanzely, F., Richtárik, P.: Federated learning of a mixture of global and local models. arXiv preprint arXiv:2002.05516 (2020)
  * [14] Kairouz, P., McMahan, H.B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A.N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., et al.: Advances and open problems in federated learning. Foundations and Trends® in Machine Learning 14(1–2), 1–210 (2021)
  * [15] Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., Stich, S.: A unified theory of decentralized sgd with changing topology and local updates. In: International Conference on Machine Learning. pp. 5381–5393. PMLR (2020)
  * [16] Li, C., Li, C., Zhao, Y., Zhang, B., Li, C.: An efficient multi-model training algorithm for federated learning. In: 2021 IEEE Global Communications Conference (GLOBECOM). pp. 1–6 (2021). https://doi.org/10.1109/GLOBECOM46510.2021.9685230
  * [17] Li, T., Sahu, A.K., Zaheer, M., Sanjabi, M., Talwalkar, A., Smith, V.: Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems 2, 429–450 (2020)
  * [18] Li, T., Sanjabi, M., Beirami, A., Smith, V.: Fair resource allocation in federated learning. arXiv preprint arXiv:1905.10497 (2019)
  * [19] Li, X., Huang, K., Yang, W., Wang, S., Zhang, Z.: On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.02189 (2019)
  * [20] Li, X., Yang, W., Wang, S., Zhang, Z.: Communication efficient decentralized training with multiple local updates. arXiv preprint arXiv:1910.09126 5 (2019)
  * [21] Liu, Z., Luo, P., Wang, X., Tang, X.: Deep learning face attributes in the wild. In: Proceedings of the IEEE international conference on computer vision. pp. 3730–3738 (2015)
  * [22] McMahan, B., Moore, E., Ramage, D., Hampson, S., y Arcas, B.A.: Communication-efficient learning of deep networks from decentralized data. In: Artificial intelligence and statistics. pp. 1273–1282. PMLR (2017)
  * [23] Sattler, F., Müller, K.R., Samek, W.: Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints. IEEE transactions on neural networks and learning systems 32(8), 3710–3722 (2020)
  * [24] Stich, S.U.: Local sgd converges fast and communicates little. arXiv preprint arXiv:1805.09767 (2018)
  * [25] Wang, J., Joshi, G.: Cooperative sgd: A unified framework for the design and analysis of communication-efficient sgd algorithms. arXiv preprint arXiv:1808.07576 (2018)
  * [26] Wang, J., Joshi, G.: Adaptive communication strategies to achieve the best error-runtime trade-off in local-update sgd. In: Talwalkar, A., Smith, V., Zaharia, M. (eds.) Proceedings of Machine Learning and Systems. vol. 1, pp. 212–229 (2019), https://proceedings.mlsys.org/paper/2019/file/c8ffe9a587b126f152ed3d89a146b445-Paper.pdf
  * [27] Woodworth, B.E., Patel, K.K., Srebro, N.: Minibatch vs local sgd for heterogeneous distributed learning. Advances in Neural Information Processing Systems 33, 6281–6292 (2020)
  * [28] Zhou, F., Cong, G.: On the convergence properties of a $k$-step averaging stochastic gradient descent algorithm for nonconvex optimization. arXiv preprint arXiv:1708.01012 (2017)

##  Appendix 0.A Appendix

###  0.A.1 Method of Analysis

We analyze the multi-model algorithms from the perspective of one of the $M$
models. Proving convergence for one of the models is enough as Assumptions 1,
2, 3 and 4 hold for all the $M$ models. To that end, below is MFA-Rand and
MFA-RR from the perspective of one of the $M$ models.

In addition to that, we are dropping the time index (or frame index) of the
set of subsets during analysis of MFA-Rand (or MFA-RR). This is because we are
analysing MFA-Rand over one round and MFA-RR over one frame, during which the
set of subsets remain fixed.

####  0.A.1.1 MFA-Rand:

From the perspective of one of the models, it is equivalent to sampling
$\frac{N}{M}$ clients out of $N$ clients, every round. We can, therefore,
refer to the analysis of single-model FedAvg with partial device participation
in [19].

####  0.A.1.2 MFA-RR:

A model goes over each of the $M$ client-subsets (created at the start of
$t=(l-1)M+1$) exactly once during $t=(l-1)M+1$ to $t=(l-1)M+M$. This means
that a model goes over each one of
$\\{\mathcal{S}_{1},\mathcal{S}_{2},..\mathcal{S}_{M}\\}$ exactly once during
that frame.

###  0.A.2 Convergence of MFA-Rand

In [19], the convergence of FedAvg for partial device participation is stated
as,

$\mathbb{E}||\overline{\textbf{w}}_{t}-\textbf{w}_{*}||^{2}\leq\frac{\nu}{t+\gamma}$
(11)

where,

$\nu=\max\left\\{\frac{\beta^{2}(B+C)}{\beta\mu-1},\mathbb{E}||\overline{\textbf{w}}_{1}-\textbf{w}_{*}||^{2}(1+\gamma)\right\\},$
(12)

where,

$B=6L\Gamma+\frac{1}{N^{2}}\sum_{k=1}^{N}\sigma_{k}^{2}+8(E-1)^{2}G^{2}.$ (13)

where $\sigma_{k}^{2}$ is the upper bound on the variance of $\nabla
F_{k}(x,\xi)$ for any size of $\xi$. We can the get its value by setting
$|\xi|=0$ in Lemma 1.
Here, $K$ is the number of clients selected per round. Since, we have
$K=\frac{N}{M}$, we put that in the expression of $C$ in [19] giving us

$C=\frac{N-K}{(N-1)K}E^{2}G^{2}=\frac{M-1}{N-1}E^{2}G^{2}.$ (14)

One important thing to note is that $\eta_{t}$ is constant during the $E$
iterations in round $t$. However, [19] has a decreasing step size even during
the $E$ iterations. This is the reason why one will find a factor of 4 absent
in inequality 14 when compared to its counterpart in [19].
Using Cauchy-Schwartz theorem, we have,

$\left(\mathbb{E}||\overline{\textbf{w}}_{t}-\textbf{w}_{*}||\right)^{2}\leq\mathbb{E}||\overline{\textbf{w}}_{t}-\textbf{w}_{*}||^{2}.$
(15)

We therefore have,

$\mathbb{E}||\overline{\textbf{w}}_{t}-\textbf{w}_{*}||\leq\frac{\sqrt{\nu}}{\sqrt{t+\gamma}}.$
(16)

###  0.A.3 Convergence of MFA-RR

We start with introducing some new notation only for the purposes of the
proof. We first drop the $m$ subscript that indicated model number $m$ as we
need to prove convergence for only one of the $M$ models. Below are the
notations used frequently in the proof. Some of them are adopted from [12].

  1. 1.

$l$: frame number

  2. 2.

$i$: $i^{\text{th}}$ round in current frame $(1\leq i\leq M)$

  3. 3.

Local iteration: stochastic gradient descent iteration at local device

  4. 4.

Global iteration: stochastic centralized gradient descent iteration (virtual)

  5. 5.

$\mathcal{S}_{i}$: $i^{\text{th}}$ subset of clients to be used in the
$i^{\text{th}}$ round of a frame (this may differ across frames but we analyse
MFA-RR over a single frame and hence, do not index it by frame number)

  6. 6.

$\overline{\textbf{w}}_{i}^{l}$: global weight
$\overline{\textbf{w}}_{\text{MFA-RR},t}$ (subscript $m$ dropped) at
$t=(l-1)M+i$

  7. 7.

$\textbf{u}_{p}$: global weight vector (virtual) of $p^{\text{th}}$
centralized full GD iteration from $\overline{\textbf{w}}_{1}^{l}$

  8. 8.

$\textbf{u}_{k,p}$: local weight vector of $p^{\text{th}}$ local SGD iteration
of $k^{\text{th}}$ client. Since a client is used by a model exactly once in a
frame, there is no need to index this variable by the round number.

  9. 9.

$\alpha_{l}$: learning rate for all $M$ rounds in $l^{\text{th}}$ frame.

The local update rule is

$\textbf{u}_{k,p+1}=\textbf{u}_{k,p}-\alpha_{l}\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})\text{ , }\forall\text{
}k\in\mathcal{S}_{i}\text{ and }p=1,2,..,E$ (17)

where $\textbf{u}_{k,1}=\overline{\textbf{w}}_{i}^{l}$. Therefore, the update
at the $k^{th}$ client is

$\textbf{u}_{k,E+1}-\overline{\textbf{w}}_{i}^{l}=\alpha_{l}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})$ (18)

The global update rule involves summing weight updates from clients in
$\mathcal{S}_{i}$ and multiplying a factor of $\frac{1}{N}$ to it.

$\overline{\textbf{w}}_{i+1}^{l}=\overline{\textbf{w}}_{i}^{l}-\frac{1}{N}\sum_{k\in\mathcal{S}_{i}}\left(\alpha_{l}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})\right)$ (19)

Over one frame, the above expression evaluates to

$\overline{\textbf{w}}_{1}^{l+1}=\overline{\textbf{w}}_{M+1}^{l}=\overline{\textbf{w}}_{1}^{l}-\frac{\alpha_{l}}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\bigg{(}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})\bigg{)}.$ (20)

Now we will compare this with $E$ global iterations of centralized GD,

$\displaystyle\overline{\textbf{w}}_{1}^{l+1}$
$\displaystyle=\overline{\textbf{w}}_{1}^{l}-\alpha_{l}\sum_{p=1}^{E}\nabla
F(\textbf{u}_{p})$
$\displaystyle-\alpha_{l}\left(\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p})-\sum_{p=1}^{E}\nabla F(\textbf{u}_{p})\right)$
$\displaystyle-\frac{\alpha_{l}}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\left(\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})-\nabla F_{k}(\textbf{u}_{k,p})\right)$ (21)

where $\textbf{u}_{1}=\overline{\textbf{w}}_{1}^{l}$ and,

$\textbf{u}_{p+1}=\textbf{u}_{p}-\alpha_{l}\nabla F(\textbf{u}_{p})\text{ ,
}p=1,2,..,E.$ (22)

So,

$\textbf{u}_{E+1}=\overline{\textbf{w}}_{1}^{l}-\alpha_{l}\sum_{p=1}^{E}\nabla
F(\textbf{u}_{p})$ (23)

We define error $\textbf{e}^{l}$ as,

$\displaystyle\textbf{e}^{l}$ $\displaystyle=\sum_{p=1}^{E}\nabla
F(\textbf{u}_{p})-\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\bigg{(}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p})\bigg{)}$ (24)
$\displaystyle=\sum_{p=1}^{E}\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\nabla
F_{k}(\textbf{u}_{p})-\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p})$ (25)
$\displaystyle=\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}(\nabla
F_{k}(\textbf{u}_{p})-\nabla F_{k}(\textbf{u}_{k,p}).$ (26)

And we define $\textbf{d}^{l}$ as

$d^{l}=\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\left(\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})-\nabla F_{k}(\textbf{u}_{k,p})\right).$ (27)

Therefore,

$\overline{\textbf{w}}_{1}^{l+1}=\textbf{u}_{E+1}+\alpha_{l}\textbf{e}^{l}-\alpha_{l}\textbf{d}^{l}$
(28)

We now track the expected distance between $\overline{\textbf{w}}_{1}^{l}$ and
$\textbf{w}_{*}$. Subtracting $\textbf{w}_{*}$ on both sides of the above
equation and taking expectation of norm, we get

$\mathbb{E}||\overline{\textbf{w}}_{1}^{l+1}-\textbf{w}_{*}||\leq\mathbb{E}||\textbf{u}_{E+1}-\textbf{w}_{*}||+\alpha_{l}\mathbb{E}||\textbf{e}^{l}||+\alpha_{l}\mathbb{E}||\textbf{d}^{l}||.$
(29)

We state lemmas 1, 2, 3 and 4 and use them to prove Theorem 4.2. Proofs of
lemmas can be found after proof of Theorem 4.2.

###### Lemma 1

Under assumptions 3 and 4, for each client $k$ and sample $\xi_{k,p}$, we have

$var(\nabla F_{k}(u_{k,p}))\leq
4\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}}\right)^{2}(\beta_{1}+\beta_{2}G^{2}).$

###### Lemma 2

Under assumptions 1 and 2, for $E$ iterations of centralized GD with learning
rate $\alpha_{l}\leq\frac{1}{L}$, we get

$\left|\left|\textbf{u}_{E+1}-w_{*}\right|\right|\leq(1-\alpha_{l}\mu)^{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||.$

###### Lemma 3

Under assumptions 2 and 3 we get the following bound on
$\mathbb{E}||\textbf{e}^{l}||$ for all $E\geq 1$ and $M\geq 1$

$\mathbb{E}||\textbf{e}^{l}||\leq\alpha_{l}LG\bigg{(}\frac{E^{2}(M-1)}{2M}+E(E-1)\bigg{)}.$

###### Lemma 4

Under assumptions 3 and 4, we get the following bound on
$\mathbb{E}||\textbf{d}^{l}||$ for all $E\geq 1$ and $M\geq 1$

$\mathbb{E}||\textbf{d}^{l}||\leq
2E\left(\frac{\mathcal{N}-\mathcal{N}_{s}(l)}{\mathcal{N}}\right)\sqrt{\beta_{1}+\beta_{2}G^{2}}$

where $\mathcal{N}_{s}(l)$ is the common sample size for local SGD iterations
at all clients in frame $l$.

####  0.A.3.1 Proof of Theorem 2:

Combining lemmas 1, 2, 3 and 4, we have

$\displaystyle\mathbb{E}||\overline{\textbf{w}}_{1}^{l+1}-\textbf{w}_{*}||\leq$
$\displaystyle(1-\alpha_{l}\mu)^{E}\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||$
$\displaystyle+\alpha_{l}^{2}LG\left(\frac{E^{2}(M-1)}{2M}+E(E-1)\right)$
$\displaystyle+\alpha_{l}2E\left(\frac{\mathcal{N}-\mathcal{N}_{s}(l)}{\mathcal{N}}\right)\sqrt{\beta_{1}+\beta_{2}G^{2}}.$
(30)

Now if we have the following sample size evolution

$\frac{\mathcal{N}-\mathcal{N}_{s}(l)}{\mathcal{N}}\leq\alpha_{l}\left(\frac{V}{2E\sqrt{\beta_{1}+\beta_{2}G^{2}}}\right)$
(31)

for some $V\geq 0$, we get $\mathbb{E}||\textbf{d}^{l}||\leq\alpha_{l}V$.
Further $(1-\alpha_{l}\mu)^{E}\leq 1-\alpha_{l}\mu$ as $E\geq 1$. We therefore
have

$\mathbb{E}||\overline{\textbf{w}}_{1}^{l+1}-\textbf{w}_{*}||\leq(1-\alpha_{l}\mu)\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||+\alpha_{l}^{2}(Y+Z+V)$
(32)

where $Y=\frac{LGE^{2}(M-1)}{2M}$ and $Z=LGE(E-1)$.
We now take $\alpha_{l}=\frac{\beta}{l+\gamma}$ and show through induction
that
$\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||\leq\frac{\nu}{l+\gamma}$
for some $\nu>0$ and some $\gamma\geq 0$.
For $l=1$ we want,

$\frac{\nu}{1+\gamma}\geq\mathbb{E}||\overline{\textbf{w}}_{1}^{1}-\textbf{w}_{*}||$
(33)

or,

$\nu\geq(1+\gamma)\mathbb{E}||\overline{\textbf{w}}_{1}^{1}-\textbf{w}_{*}||.$
(34)

Next we show that
$\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||\leq\frac{\nu}{l+\gamma}$
implies
$\mathbb{E}||\overline{\textbf{w}}_{1}^{l+1}-\textbf{w}_{*}||\leq\frac{\nu}{l+1+\gamma}$
for a certain $\nu$

$\displaystyle\mathbb{E}||\overline{\textbf{w}}_{1}^{l+1}-\textbf{w}_{*}||$
$\displaystyle\leq\bigg{(}1-\frac{\beta\mu}{l+\gamma}\bigg{)}\frac{\nu}{l+\gamma}+\frac{\beta^{2}(Y+Z+V)}{(l+\gamma)^{2}}$
(35)
$\displaystyle=\frac{(l+\gamma-\beta\mu)\nu+\beta^{2}(Y+Z+V)}{(l+\gamma)^{2}}$
(36)
$\displaystyle=\frac{(l+\gamma-1+1-\beta\mu)\nu+\beta^{2}(Y+Z+V)}{(l+\gamma)^{2}}$
(37)
$\displaystyle=\frac{l+\gamma-1}{(l+\gamma)^{2}}\nu-\bigg{(}\frac{(\beta\mu-1)\nu-\beta^{2}(Y+Z+V)}{(l+\gamma)^{2}}\bigg{)}$
(38)
$\displaystyle\leq\frac{\nu}{l+\gamma+1}-\bigg{(}\frac{(\beta\mu-1)\nu-\beta^{2}(Y+Z+V)}{(l+\gamma)^{2}}\bigg{)}$
(39) $\displaystyle\leq\frac{\nu}{l+\gamma+1}.$ (40)

Inequality 39 holds as $\frac{x-1}{x^{2}}\leq\frac{1}{x+1}$ for $x>-1$ and
$l+\gamma>-1$ obviously. Inequality 40 holds when

$(\beta\mu-1)\nu\geq\beta^{2}(Y+Z+V)$ (41)

or,

$\nu\geq\frac{\beta^{2}(Y+Z+V)}{\beta\mu-1}$ (42)

with $\beta\geq\frac{1}{\mu}$. We therefore have,

$\nu=\max\bigg{\\{}\frac{\beta^{2}(Y+Z+V)}{\beta\mu-1},(1+\gamma)\mathbb{E}||\overline{\textbf{w}}_{1}^{1}-\textbf{w}_{*}||\bigg{\\}}.$
(43)

Further, we need $\alpha_{l}\leq\frac{1}{L}$ $\forall$ $l\geq 0$. This is
satisfied if $\alpha_{1}\leq\frac{1}{L}$,

$\frac{\beta}{1+\gamma}\leq\frac{1}{L}$ (44)

or,

$\gamma\geq\beta L-1.$ (45)

Note that $\beta L-1\geq 0$ as $\beta\geq\frac{1}{\mu}$.
Putting everything together, we get the following for
$\alpha_{l}=\frac{\beta}{l+\gamma}$ with $\beta\geq\frac{1}{\mu}$ and
$\gamma\geq\beta L-1$,

$\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||\leq\frac{\nu}{l+\gamma}\text{
}\forall\text{ }l\geq 1.$ (46)

Therefore for any $\overline{\textbf{w}}_{i}^{l}$,

$\displaystyle\mathbb{E}||\overline{\textbf{w}}_{i}^{l}-\textbf{w}_{*}||$
$\displaystyle=\mathbb{E}||(\overline{\textbf{w}}_{i}^{l}-\overline{\textbf{w}}_{1}^{l})+\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||$
(47)
$\displaystyle\leq\mathbb{E}||\overline{\textbf{w}}_{i}^{l}-\overline{\textbf{w}}_{1}^{l}||+\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||$
(48) $\displaystyle\leq\frac{\alpha_{l}(i-1)EG}{M}+\frac{\nu}{l+\gamma}$ (49)
$\displaystyle=\frac{\beta EG((i-1)/M)+\nu}{l+\gamma}$ (50)
$\displaystyle\leq\frac{\beta EG((M-1)/M)+\nu}{l+\gamma}.$ (51)

Therefore,

$\mathbb{E}||\overline{\textbf{w}}_{i}^{l}-\textbf{w}_{*}||\leq\frac{\beta
EG((M-1)/M)+\nu}{l+\gamma}.$ (52)

We can write $l$ as $1+\left\lfloor\frac{t}{M}\right\rfloor$ and
$\overline{\textbf{w}}_{i}^{l}$ is $\overline{\textbf{w}}_{\text{MFA-
RR},t}^{(m)}$. Since, $\frac{t}{M}-1$ is less than
$\left\lfloor\frac{t}{M}\right\rfloor$, we can replace the latter with the
former to give Theorem 4.2. The denominator will still be always non-negative
as $\gamma\geq\beta L-1\geq 0$.
The results hold for any set of disjoint client subsets as we do not use any
specification information regarding distribution of clients into
$\\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{M}\\}$. This means that
the results hold even if
$\\{\mathcal{S}_{1},\mathcal{S}_{2},...,\mathcal{S}_{M}\\}$ is different for
every frame.

####  0.A.3.2 Proof of Lemma 1:

For any sample $\xi_{k,p}$ of data points in any client $k$, we have

$\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})=\frac{1}{|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}\nabla
f_{k,h}(\textbf{u}_{k,p}).$ (53)

We therefore have

$\displaystyle\textbf{v}_{k,p}$ $\displaystyle=\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})-\nabla F_{k}(\textbf{u}_{k,p})$ (54)
$\displaystyle=\frac{1}{|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}\nabla
f_{k,h}(\textbf{u}_{k,p})-\frac{1}{\mathcal{N}}\sum_{y=1}^{\mathcal{N}}\nabla
f_{k,y}(\textbf{u}_{k,p})$ (55)
$\displaystyle=\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}\nabla
f_{k,h}(\textbf{u}_{k,p})-\frac{1}{\mathcal{N}}\sum_{y\not\in\xi_{k,p}}\nabla
f_{k,y}(\textbf{u}_{k,p}).$ (56)

Using assumption 4, we get

$\displaystyle||\textbf{v}_{k,p}||^{2}$
$\displaystyle=\left|\left|\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}\nabla
f_{k,h}(\textbf{u}_{k,p})-\frac{1}{\mathcal{N}}\sum_{y\not\in\xi_{k,p}}\nabla
f_{k,y}(\textbf{u}_{k,p})\right|\right|^{2}$ (57)
$\displaystyle\leq\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}||\nabla
f_{k,h}(\textbf{u}_{k,p})||+\frac{1}{\mathcal{N}}\sum_{y\not\in\xi_{k,p}}||\nabla
f_{k,y}(\textbf{u}_{k,p})||\right)^{2}$ (58)
$\displaystyle\leq\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}1^{2}+\frac{1}{\mathcal{N}}\sum_{y\not\in\xi_{k,p}}1^{2}\right)\times$
$\displaystyle\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}|\xi_{k,p}|}\sum_{h\in\xi_{k,p}}||\nabla
f_{k,h}(\textbf{u}_{k,p})||^{2}+\frac{1}{\mathcal{N}}\sum_{y\not\in\xi_{k,p}}||\nabla
f_{k,y}(\textbf{u}_{k,p})||^{2}\right)$ (59) $\displaystyle\leq
4\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}}\right)^{2}(\beta_{1}+\beta_{2}||\nabla
F_{k}(\textbf{u}_{k,p})||^{2}).$ (60)

Using Assumption 3,

$\displaystyle var(\nabla F_{k}(u_{k,p}))$
$\displaystyle=\mathbb{E}||\textbf{v}_{k,p}||^{2}$ (61) $\displaystyle\leq
4\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}}\right)^{2}(\beta_{1}+\beta_{2}\mathbb{E}||\nabla
F_{k}(\textbf{u}_{k,p})||^{2})$ (62) $\displaystyle\leq
4\left(\frac{\mathcal{N}-|\xi_{k,p}|}{\mathcal{N}}\right)^{2}(\beta_{1}+\beta_{2}G^{2}).$
(63)

####  0.A.3.3 Proof of Lemma 2:

We have the following update rule for $\textbf{u}_{p}$,

$\textbf{u}_{p+1}=\textbf{u}_{p}-\alpha_{l}\nabla F(\textbf{u}_{p})\text{ ,
}p=1,2,..,E.$ (64)

We therefore have,

$||\textbf{u}_{p+1}-\textbf{w}_{*}||=||\textbf{u}_{p}-\alpha_{l}\nabla
F(\textbf{u}_{p})-\textbf{w}_{*}||\text{ , }p=1,2,..,E.$ (65)

Now,

$\nabla F(\textbf{x}_{B})-\nabla
F(\textbf{x}_{A})=\int_{\textbf{x}_{A}}^{\textbf{x}_{B}}\nabla^{2}F(\textbf{x})\textbf{dx}$
(66)

where dx is an infinitesimal vector. The above expression is an extension of
line integral of gradient,

$g(\textbf{x}_{B})-g(\textbf{x}_{A})=\int_{\textbf{x}_{A}}^{\textbf{x}_{B}}\nabla
g(\textbf{x})^{T}\textbf{dx}.$ (67)

Since $\nabla^{2}F=[\nabla g_{1}\nabla g_{2}...\nabla g_{n}]^{T}$ where
$\nabla F=[g_{1}g_{2}...g_{n}]^{T}$, applying equation 67 on each $g_{i}$
gives equation 66. Note that the integral is independent of the path taken
from $\textbf{x}_{A}$ to $\textbf{x}_{B}$, so any dx works as long as
$\int_{\textbf{x}_{A}}^{\textbf{x}_{B}}\textbf{dx}=\textbf{x}_{B}-\textbf{x}_{A}$
Now, putting $\textbf{x}_{A}=\textbf{w}_{*}$, $\textbf{x}_{B}=\textbf{u}_{p}$,
$\textbf{x}=\textbf{w}_{*}+\tau(\textbf{u}_{p}-\textbf{w}_{*})$, we have

$\nabla
F(\textbf{u}_{p})-\textbf{0}=\bigg{(}\int_{0}^{1}\nabla^{2}F(\textbf{w}_{*}+\tau(\textbf{u}_{p}-\textbf{w}_{*}))d\tau\bigg{)}(\textbf{u}_{p}-\textbf{w}_{*})$
(68)

as $\textbf{dx}=d\tau(\textbf{u}_{p}-\textbf{w}_{*})$. Lets define $A_{p}$ as,

$A_{p}=\int_{0}^{1}\nabla^{2}F(\textbf{w}_{*}+\tau(\textbf{u}_{p}-\textbf{w}_{*}))d\tau.$
(69)

We therefore have,

$\nabla F(\textbf{u}_{p})=A_{p}(\textbf{u}_{p}-\textbf{w}_{*}).$ (70)

Therefore,

$\textbf{u}_{p}-\alpha_{l}\nabla
F(\textbf{u}_{p})-\textbf{w}_{*}=(I-\alpha_{l}A_{p})(\textbf{u}_{p}-\textbf{w}_{*}).$
(71)

Taking norm on both sides,

$\displaystyle||\textbf{u}_{p}-\alpha_{l}\nabla
F(\textbf{u}_{p})-\textbf{w}_{*}||$
$\displaystyle=||(I-\alpha_{l}A_{p})(\textbf{u}_{p}-\textbf{w}_{*})||$ (72)
$\displaystyle\leq||I-\alpha_{l}A_{p}||.||\textbf{u}_{p}-\textbf{w}_{*}||$
(73)
$\displaystyle=\sigma_{max}(I-\alpha_{l}A_{p})||\textbf{u}_{p}-\textbf{w}_{*}||$
(74)
$\displaystyle=\left(\max_{j}|\lambda_{j}(I-\alpha_{l}A_{p})|\right)||\textbf{u}_{p}-\textbf{w}_{*}||,$
(75)

where $\sigma_{max}$ is the spectral norm of a matrix. The last equality is
true because $A_{p}$ is a real symmetric matrix, making $I-\alpha_{l}A_{p}$
real symmetric. Here, $\lambda_{j}(\cdot)$ denotes $j^{\text{th}}$ eigenvalue
of the matrix.
Since $\mu I\preceq\nabla^{2}F\preceq LI$ and semi-definiteness holds under
addition, the following is true

$\int_{0}^{1}\mu
Id\tau\preceq\int_{0}^{1}\nabla^{2}F(\textbf{w}_{*}+\tau(\textbf{u}_{p}-\textbf{w}_{*}))d\tau\preceq\int_{0}^{1}LId\tau$
(76)

implying,

$\mu I\preceq A_{p}\preceq LI$ (77)

and,

$(1-\alpha_{l}L)I\preceq I-\alpha_{l}A_{p}\preceq(1-\alpha_{l}\mu)I.$ (78)

We would like $I-\alpha_{l}A_{p}$ to be always positive semi-definite [12] and
therefore impose $\alpha_{l}\leq\frac{1}{L}$.
Now, $I-\alpha_{l}A_{p}-(1-\alpha_{l}\mu)I$ has eigenvalues
$\left\\{\lambda_{j}(I-\alpha_{l}A_{p})-(1-\alpha_{l}\mu)\right\\}$. Since,
$I-\alpha_{l}A_{p}-(1-\alpha_{l}\mu)I\preceq 0$, all its eigen values are less
than or equal to 0 giving us

$0\leq\lambda_{j}(I-\alpha_{l}A_{p})\leq(1-\alpha_{l}\mu)\text{ }\forall\text{
}j.$ (79)

Therefore,

$\displaystyle||\textbf{u}_{p}-\alpha_{l}\nabla
F(\textbf{u}_{p})-\textbf{w}_{*}||$
$\displaystyle\leq\left(\max_{j}|\lambda_{j}(I-\alpha_{l}A_{p})|\right)||\textbf{u}_{p}-\textbf{w}_{*}||$
(80) $\displaystyle\leq(1-\alpha_{l}\mu)||\textbf{u}_{p}-\textbf{w}_{*}||.$
(81)

Putting everything together,

$||\textbf{u}_{p+1}-\textbf{w}_{*}||\leq(1-\alpha_{l}\mu)||\textbf{u}_{p}-\textbf{w}_{*}||\text{
, }p=1,2,..,E$ (82)

which gives us

$\displaystyle||\textbf{u}_{E+1}-\textbf{w}_{*}||$
$\displaystyle\leq(1-\alpha_{l}\mu)^{E}||\textbf{u}_{1}-\textbf{w}_{*}||$ (83)
$\displaystyle=(1-\alpha_{l}\mu)^{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||.$
(84)

Therefore,

$\mathbb{E}||\textbf{u}_{E+1}-\textbf{w}_{*}||\leq(1-\alpha_{l}\mu)^{E}\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\textbf{w}_{*}||.$
(85)

####  0.A.3.4 Proof of Lemma 3:

We have norm of $\textbf{e}^{l}$ as

$\displaystyle\mathbb{E}||\textbf{e}^{l}||$
$\displaystyle=\bigg{|}\bigg{|}\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in
S_{i}}\sum_{p=1}^{E}(\nabla F_{k}(\textbf{u}_{p})-\nabla
F_{k}(\textbf{u}_{k,p}))\bigg{|}\bigg{|}$ (86)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in
S_{i}}\sum_{p=1}^{E}\mathbb{E}||\nabla F_{k}(\textbf{u}_{p})-\nabla
F_{k}(\textbf{u}_{k,p})||.$ (87)

From assumption 2, $F_{k}$ is $L$-smooth, giving us

$||\nabla F_{k}(\textbf{u}_{p})-\nabla F_{k}(\textbf{u}_{k,p})||\leq
L||\textbf{u}_{p}-\textbf{u}_{k,p}||$ (88)

We now find an upper bound on $||\textbf{u}_{p}-\textbf{u}_{k,p}||$,

$\displaystyle||\textbf{u}_{p}-\textbf{u}_{k,p}||$
$\displaystyle=\bigg{|}\bigg{|}\sum_{j=1}^{p-1}(\textbf{u}_{j+1}-\textbf{u}_{j})+\textbf{u}_{1}-\textbf{u}_{k,1}+\sum_{j=1}^{p-1}(\textbf{u}_{k,j}-\textbf{u}_{k,j+1})\bigg{|}\bigg{|}$
(89)
$\displaystyle\leq\sum_{j=1}^{p-1}||\textbf{u}_{j+1}-\textbf{u}_{j}||+||\textbf{u}_{1}-\textbf{u}_{k,1}||+\sum_{j=1}^{p-1}||\textbf{u}_{k,j}-\textbf{u}_{k,j+1}||$
(90) $\displaystyle\leq\sum_{j=1}^{p-1}||\alpha_{l}\nabla
F(\textbf{u}_{j})||+||\textbf{u}_{1}-\textbf{u}_{k,1}||+\sum_{j=1}^{p-1}||\alpha_{l}\nabla
F_{k}(\textbf{u}_{k,j},\xi_{k,j})||.$ (91)

Therefore,

$\displaystyle\mathbb{E}||\textbf{u}_{p}-\textbf{u}_{k,p}||\leq$
$\displaystyle\alpha_{l}\sum_{j=1}^{p-1}\left(\mathbb{E}||\nabla
F(\textbf{u}_{j})||+\mathbb{E}||\nabla
F_{k}(\textbf{u}_{k,j},\xi_{k,j})||\right)+\mathbb{E}||\textbf{u}_{1}-\textbf{u}_{k,1}||$
(92) $\displaystyle\leq$
$\displaystyle\alpha_{l}\sum_{j=1}^{p-1}\left(||\nabla
F(\textbf{u}_{j})||+\sqrt{\mathbb{E}||\nabla
F_{k}(\textbf{u}_{k,j},\xi_{k,j})||^{2}}\right)$
$\displaystyle+\mathbb{E}||\textbf{u}_{1}-\textbf{u}_{k,1}||$ (93)
$\displaystyle\leq$ $\displaystyle\alpha_{l}\sum_{j=1}^{p-1}(||\nabla
F(\textbf{u}_{j})||+G)+\mathbb{E}||\textbf{u}_{1}-\textbf{u}_{k,1}||$ (94)
$\displaystyle\leq$ $\displaystyle
2(p-1)\alpha_{l}G+\mathbb{E}||\textbf{u}_{1}-\textbf{u}_{k,1}||$ (95)
$\displaystyle=$ $\displaystyle
2(p-1)\alpha_{l}G+\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||.$
(96)

Inequality 95 holds as $||\nabla F(\textbf{x})||=||(1/N)\sum_{k=1}^{N}\nabla
F_{k}(\textbf{x})||\leq$
$(1/N)\sum_{k=1}^{N}||\nabla
F_{k}(\textbf{x})||=(1/N)\sum_{k=1}^{N}||\mathbb{E}\nabla
F_{k}(\textbf{x},\xi)||\leq$
$(1/N)\sum_{k=1}^{N}\mathbb{E}||\nabla F_{k}(\textbf{x},\xi)||\leq G$
Inserting inequality 88 and 96 in inequality 87,

$\displaystyle\mathbb{E}||\textbf{e}^{l}||$
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in
S_{i}}\sum_{p=1}^{E}L(2(p-1)\alpha_{l}G+\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||)$
(97) $\displaystyle=\frac{L}{N}\sum_{i=1}^{M}\sum_{k\in
S_{i}}2\frac{E(E-1)}{2}\alpha_{l}G+E\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||$
(98)
$\displaystyle=\frac{L}{N}\sum_{i=1}^{M}\frac{N}{M}(E(E-1)\alpha_{l}G+E\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||)$
(99)
$\displaystyle=\bigg{(}\frac{LE}{M}\sum_{i=1}^{M}\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||\bigg{)}+\alpha_{l}LGE(E-1).$
(100)

We will now get an upper bound on
$\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||$,

$\displaystyle\mathbb{E}||\overline{\textbf{w}}_{1}^{l}-\overline{\textbf{w}}_{i}^{l}||$
$\displaystyle=\mathbb{E}\bigg{|}\bigg{|}\sum_{j=1}^{i-1}(\overline{\textbf{w}}_{j}^{l}-\overline{\textbf{w}}_{j+1}^{l})\bigg{|}\bigg{|}$
(101)
$\displaystyle\leq\sum_{j=1}^{i-1}\mathbb{E}||\overline{\textbf{w}}_{j}^{l}-\overline{\textbf{w}}_{j+1}^{l}||$
(102)
$\displaystyle=\sum_{j=1}^{i-1}\mathbb{E}\bigg{|}\bigg{|}\frac{1}{N}\sum_{k\in
S_{i}}\bigg{(}\alpha_{l}\sum_{p=1}^{E}\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})\bigg{)}\bigg{|}\bigg{|}$ (103)
$\displaystyle\leq\frac{\alpha_{l}}{N}\sum_{j=1}^{i-1}\sum_{k\in
S_{i}}\sum_{p=1}^{E}\mathbb{E}||\nabla F_{k}(\textbf{u}_{k,p},\xi_{k,p})||$
(104) $\displaystyle\leq\frac{\alpha_{l}}{N}\sum_{j=1}^{i-1}\sum_{k\in
S_{i}}\sum_{p=1}^{E}\sqrt{\mathbb{E}||\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})||^{2}}$ (105)
$\displaystyle\leq\frac{\alpha_{l}}{N}\sum_{j=1}^{i-1}\sum_{k\in
S_{i}}\sum_{p=1}^{E}G$ (106)
$\displaystyle=\alpha_{l}\times\frac{1}{N}\times(i-1)\times\frac{N}{M}\times
EG$ (107) $\displaystyle=\frac{\alpha_{l}(i-1)EG}{M}.$ (108)

Inserting inequality 108 in inequality 100,

$\displaystyle\mathbb{E}||\textbf{e}^{l}||$
$\displaystyle\leq\frac{LE}{M}\sum_{i=1}^{M}\frac{\alpha_{l}(i-1)EG}{M}+\alpha_{l}LGE(E-1)$
(109)
$\displaystyle=\frac{\alpha_{l}LE^{2}G}{M^{2}}\times\frac{M(M-1)}{2}+\alpha_{l}LGE(E-1)$
(110) $\displaystyle=\alpha_{l}LG\left(\frac{E^{2}(M-1)}{2M}+E(E-1)\right).$
(111)

We finally have following upper bound on norm of error $\textbf{e}^{l}$,

$\mathbb{E}||\textbf{e}^{l}||\leq\alpha_{l}LG\left(\frac{E^{2}(M-1)}{2M}+E(E-1)\right).$
(112)

####  0.A.3.5 Proof of Lemma 4:

We have the following for $\mathbb{E}||d^{l}||$.

$\displaystyle\mathbb{E}||d^{l}||$
$\displaystyle=\mathbb{E}\left|\left|\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\left(\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})-\nabla
F_{k}(\textbf{u}_{k,p})\right)\right|\right|$ (113)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\mathbb{E}||\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})-\nabla F_{k}(\textbf{u}_{k,p})||$ (114)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\sqrt{\mathbb{E}||\nabla
F_{k}(\textbf{u}_{k,p},\xi_{k,p})-\nabla F_{k}(\textbf{u}_{k,p})||^{2}}$ (115)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\sqrt{var(\nabla
F_{k}(\textbf{u}_{k,p}))}$ (116)
$\displaystyle\leq\frac{1}{N}\sum_{i=1}^{M}\sum_{k\in\mathcal{S}_{i}}\sum_{p=1}^{E}\frac{2(\mathcal{N}-|\xi_{k,p}|)}{\mathcal{N}}\sqrt{\beta_{1}+\beta_{2}G^{2}}$
(117)
$\displaystyle=2E\left(\frac{\mathcal{N}-\mathcal{N}_{s}(l)}{\mathcal{N}}\right)\sqrt{\beta_{1}+\beta_{2}G^{2}},$
(118)

where, $\mathcal{N}_{s}(l)$ is the common sample size for local SGD iterations
at all clients in frame $l$.

###  0.A.4 Advantage of MFA-Rand over running FedAvg $M$ times

We defined gain of MFA-Rand over FedAvg as

$g_{\text{MFA-Rand}}(M,\epsilon)=\frac{MT_{1}(\epsilon)}{T_{\text{MFA-
Rand}}(M,\epsilon)}.$ (119)

Here, we make use of the assumption that all $M$ models are of similar
complexity. Therefore, when MFA-Rand is used, all models will reach
$\epsilon$-accuracy in roughly the same number of rounds. $T_{\text{MFA-
Rand}}(M,\epsilon)$ will be same as the number rounds each model took to reach
accuracy of $\epsilon$. We use Theorem 4.1 to calculate $T_{\text{MFA-
Rand}}(M,\epsilon)$ and drop the $m$ superscript during analysis as number
rounds each model takes to reach accuracy of $\epsilon$ is same. At the end,
however, we add the $m$ superscript for completeness of proof.
We will show that $g_{\text{MFA-Rand}}(1,\epsilon)=1$ and
$\frac{d}{dM}g_{\text{MFA-Rand}}(1,\epsilon)\geq 0$ $\forall$ $M\geq 1$

####  0.A.4.1 Proof of Theorem 3:

In the proof use $T_{1}$ for $T_{1}(\epsilon)$, $T_{M}$ for $T_{\text{MFA-
Rand}}(M,\epsilon)$ and $g$ for $g_{\text{MFA-Rand}}(M,\epsilon)$.

$\displaystyle\frac{d}{dM}g$
$\displaystyle=\frac{d}{dM}\left(\frac{MT_{1}}{T_{M}}\right)$ (120)
$\displaystyle=\frac{T_{1}T_{M}-MT_{1}\frac{dT_{M}}{dM}}{T_{M}^{2}}$ (121)
$\displaystyle=\frac{T_{1}\left(T_{M}-M\frac{dT_{M}}{dM}\right)}{T_{M}^{2}}.$
(122)

So for $\frac{d}{dM}g>0$, we need,

$\frac{T_{M}}{M}>\frac{dT_{M}}{dM}.$ (123)

We have following convergence result for MFA-Rand (we use $\Delta_{t}$ as a
shorthand for $\Delta^{(m)}_{\text{MFA-Rand}}(t)$),

$\Delta_{T_{M}}\leq\frac{\sqrt{\nu}}{\sqrt{T_{M}+\gamma}},$ (124)

where,
$\nu=\max\left\\{\frac{\beta^{2}(B+C)}{\beta\mu-1},\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||^{2}(1+\gamma)\right\\}$. Note that we drop the $m$
superscript and use convergence of only one model as rest of the models will
behave similarly and reach $\epsilon$ accuracy in the same time.

$\Delta_{T_{M}}\leq\frac{1}{\sqrt{T_{M}+\gamma}}\sqrt{\frac{\beta^{2}(B+C)}{\beta\mu-1}+\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||^{2}(1+\gamma)}$ (125)

For $\Delta_{T_{M}}\leq\epsilon$, satisfying the following equation is
sufficient

$\sqrt{\frac{\frac{\beta^{2}(B+C)}{\beta\mu-1}+\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||^{2}(1+\gamma)}{T_{M}+\gamma}}=\epsilon.$ (126)

Implies,

$T_{M}=\frac{\frac{\beta^{2}(B+C)}{\beta\mu-1}+\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||^{2}(1+\gamma)-\epsilon^{2}\gamma}{\epsilon^{2}}.$
(127)

Putting $T_{M}$ in inequality 123, we get

$\frac{\frac{\beta^{2}(B+C)}{\beta\mu-1}+\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||^{2}(1+\gamma)-\epsilon^{2}\gamma}{M\epsilon^{2}}>\frac{\beta^{2}}{(\beta\mu-1)\epsilon^{2}}\frac{dC}{dM}.$
(128)

Satisfying the following inequality is sufficient if
$\epsilon^{2}<(\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||)^{2}<\mathbb{E}||\overline{\textbf{w}}_{\text{MFA-
Rand},1}-\textbf{w}_{*}||^{2}$,

$\frac{B+C}{M}>\frac{dC}{dM}.$ (129)

Putting $C=\frac{M-1}{N-1}E^{2}G^{2}$ in the above inequality, the required
condition is

$B>\frac{E^{2}G^{2}}{N-1}.$ (130)

Now putting expression of $B$ in the above equation, the following inequality
needs to satisfied for increasing gain,

$6L\Gamma+(1/N^{2})\sum_{k=1}^{N}\sigma_{k}^{2}+8(E-1)^{2}G^{2}>\frac{E^{2}G^{2}}{N-1}.$
(131)

Now, if $N\geq 2$ (which is required for $M>1$ as a client can train only one
model at once),

${N-1}>\frac{E^{2}}{8(E-1)^{2}}\text{ }\forall\text{ }E\geq 2,$ (132)

as the right hand side of the above inequality has maximum value of
$\frac{1}{2}$. Therefore,

$8(E-1)^{2}G^{2}>\frac{E^{2}G^{2}}{N-1}\text{ }\forall\text{ }E\geq 2.$ (133)

Therefore, we have

$6L\Gamma+(1/N^{2})\sum_{k=1}^{N}\sigma_{k}^{2}+8(E-1)^{2}G^{2}>\frac{E^{2}G^{2}}{N-1}\text{
}\forall\text{ }E\geq 2,$ (134)

proving that $\frac{d}{dM}g>0$ $\forall$ $E\geq 2$.
For inequality 131 to hold for $E=1$, the following is sufficient

$6L\Gamma>\frac{E^{2}G^{2}}{N-1},$ (135)

or

$N>1+\frac{G^{2}}{6L\Gamma}.$ (136)

Since, $T_{M}=T_{1}$ when $M=1$, we get that $g=\frac{1\times T_{1}}{T_{1}}=1$
when $M=1$. For $M>1$, under the conditions of $\frac{d}{dM}g>0$, we have
$g>1$ and increasing $\forall$ $M>1$.
Inequality 136 needs to be satisfied for all models. Therefore, we need the
following as the condition for increasing gain for $E=1$,

$N>1+\max_{m}\left\\{\frac{6L\Gamma^{(m)}}{(G^{(m)})^{2}}\right\\}.$ (137)