# Federated Learning Under Intermittent Client Availability and Time-Varying
Communication Constraints

Mónica Ribero Dept. of Electrical and Computer Engineering, The University of
Texas at Austin.  Haris Vikalo 11footnotemark: 1 Gustavo De Veciana
11footnotemark: 1

###### Abstract

Federated learning systems facilitate training of global models in settings
where potentially heterogeneous data is distributed across a large number of
clients. Such systems operate in settings with intermittent client
availability and/or time-varying communication constraints. As a result, the
global models trained by federated learning systems may be biased towards
clients with higher availability. We propose F3ast , an unbiased algorithm
that dynamically learns an availability-dependent client selection strategy
which asymptotically minimizes the impact of client-sampling variance on the
global model convergence, enhancing performance of federated learning. The
proposed algorithm is tested in a variety of settings for intermittently
available clients under communication constraints, and its efficacy
demonstrated on synthetic data and realistically federated benchmarking
experiments using CIFAR100 and Shakespeare datasets. We show up to 186% and 8%
accuracy improvements over FedAvg , and 8% and 7% over FedAdam on CIFAR100 and
Shakespeare, respectively.

##  1 Introduction

Federated learning (FL) has emerged as an attractive framework for training
machine learning models in settings where the data is distributed among remote
clients and must remain local due to privacy concerns and/or resource
constraints. In the original Federated Averaging algorithm (FedAvg) [23], as
well as more recent approaches including Scaffold [17], Federated Adaptive
Optimization [27], FedDyn [1] and FedProx [21], a server selects a random
subset of clients and which will participate in updating a global model by
training on local data. The server aggregates the clients’ updates to produce
a new global model, broadcasts it to the clients, and a new round of training
begins; this procedure is repeated until convergence.

One of the biggest gaps between theory and practice of FL is due to biased
sampling of clients caused by their on-and-off availability and communication
constraints [5, 10, 40]. For example, in cross-device settings including
mobile device systems [23], a vast number of client devices [16] with limited
communication and power resources [5] intermittently connects to a central
server to help optimize a global objective. Existing FL algorithms typically
ignore intermittency and assume that the participating client devices are
always available and thus can be tasked with performing a model update at any
time [23, 9, 22, 1]. If not addressed by the system design, time-varying
communication constraints and intermittent client availability (due to battery
and other device-specific limitations) may cause significant degradation of
the learned model performance [10, 28, 9].

To illustrate the potential severity of the problem described above, and
preview the contributions of this paper, consider the following simple
example. Let $c_{1}$ and $c_{2}$ be two clients with distinct data
distributions. A server aims to optimize the function
$F(\mathbf{w})=p_{1}F_{1}(\mathbf{w})+p_{2}F_{2}(\mathbf{w})$ over
$\mathbb{R}^{p}$, where $F_{1}$ and $F_{2}$ denote the loss functions at
clients $c_{1}$ and $c_{2}$, respectively, and for simplicity
$p_{1}=p_{2}=1/2$. We shall consider a model for the clients’ intermittent
availability characterized by the joint distributions given in Table 1, where
$A_{i}$ is a binary random variable indicating whether client $c_{i}$ is
available. In this model, clients’ availabilities in a given round are
independent, with $P(A_{1}=1)=0.375$ while $P(A_{2}=1)=0.8$. Note the client
availabilities are assumed to be independent across rounds. Suppose there is a
communication constraint which restricts the server to sampling at most a
single client each round. The server must thus choose a possibly client state
dependent policy for selecting the clients in each round. Each such policy
would achieve certain long-term client participation rates across the rounds,
denoted $\mathbf{r}=(r_{1},r_{2})$. For example, under the model in Table 1,
the set of achievable long-term participation rates across all possible
policies is given by the region $\mathcal{R}_{1}$ shown in Figure 1. Given the
communication constraints, it is not possible to achieve the full client
participation rates of $\mathbf{r}=(1,1)$ because clients are not always
available and we can only sample one client in each round. However,
$\mathbf{r}^{a}=(0.375,0)$ is achievable by using the state-dependent
deterministic policy which selects $c_{1}$ whenever $c_{1}$ is available and
never selects $c_{2}$. Alternatively, $\mathbf{r}^{b}=(0.375,0.5)$ is also
achievable by selecting $c_{1}$ whenever $c_{1}$ is available, and $c_{2}$
when only $c_{2}$ is available. A naive selection policy that samples from
available clients with probability proportional to $p_{i}=\frac{1}{2}$ in hope
of achieving “ideal” participation rate $(\frac{1}{2},\frac{1}{2})$ [22] would
actually result in client $c_{1}$ participating at a rate of

$r^{c}_{1}=P(A_{1}=1,A_{2}=0)+\frac{P(A_{1}=A_{2}=1)}{2}=0.225.$

Analogously, the long-term participation rate of client $c_{2}$ under the same
naive selection policy is $r^{c}_{2}=0.65$.

As demonstrated in Section 3 (Theorem 3.5), improper choice of the long-term
participation rate $\mathbf{r}$ injects bias and variance into the global
model. Therefore, selecting an “appropriate” rate is of fundamental
importance; yet, as illustrated above, intermittent client availability and
communication constraints present several previously overlooked challenges:
(i) determining the long-term participation rate
$\mathbf{r}^{*}\in\mathcal{R}$ which is best in terms of its impact on the
convergence of federated learning, and (ii) design of a client selection
policy that achieves rate $\mathbf{r}^{*}$. These are particularly demanding
because the (possibly correlated) clients’ availability patterns are unknown
and, therefore, $\mathcal{R}$ is unknown.

Table 1: Client availability model: The availability is independent across time and clients. |  $A_{2}=1$ |  $A_{2}=0$ |  Marginal
---|---|---|---
$A_{1}=1$ |  0.3 |  0.075 |  0.375
$A_{1}=0$ |  0.5 |  0.125 |  0.625
Marginal |  0.8 |  0.2 |
$\mathcal{R}_{1}$Ideal
rate$(\frac{1}{2},\frac{1}{2})$$\mathbf{r}^{a}$$\mathbf{r}^{b}$$\mathbf{r}^{c}$$r_{1}$$r_{2}$
Figure 1: The region of achievable long-term participation rates under the
client availability model in Table 1.

##### The main contribution of this paper: Learning to sample clients with
intermittent client availability.

In this paper we introduce F3ast , a federated learning algorithm that
additionally learns and adapts to the unknown statistics of client
availability and the variability in the FL system capacity (i.e., adapts to
time-varying communication constraints). F3ast  is shown to be
asymptotically optimal (see Theorem 3.3) as its long-term participation rate
converges to the value minimizing a bound on the global model variance over
the space of achievable rates. Remarkably, F3ast accomplishes this with no
prior knowledge of the communication constraints or clients’ availability
models. To our knowledge, this is the first work to formally address client
intermittency and system capacity variability in federated learning, and the
first work to propose a method to learn how to select clients while pursuing a
shared (global) model within the federated learning framework.

##### Extensive experimentation on realistic tasks and data.

F3ast is tested on three benchmark datasets: (i) Synthetic(1,1) [30], a widely
used heterogeneous synthetic dataset for softmax regression [21]; (ii) a
realistically federated version of CIFAR100 [27]; and (iii) Shakespeare [23].
We demonstrate that in learning highly non-linear models F3ast exhibits more
stable convergence and considerably higher accuracy than state-of-art
algorithms. Moreover, F3ast ’s selection and aggregation method is readily
combined with the existing optimization techniques designed to address
system’s constraints, allowing those methods to take advantage of F3ast ’s
policies: experiments confirm that incorporating F3ast reduces bias of
algorithms that do not compensate for client selection uncertainties, and
demonstrate much more stable descent trajectories to the optimum even in
highly time-varying environments.

##  2 Background and Related Work

###  2.1 Federated Learning

Given a set $\mathcal{U}$ with $N$ clients, each having $n_{k}$ data samples,
a federated learning system is concerned with solving

$\min_{\mathbf{w}\in\mathbb{R}^{{}^{p}}}\mathbb{E}_{k\sim\mathcal{P}}[F_{k}(\mathbf{w})],$
(1)

where
$F_{k}(\mathbf{w})=\mathbb{E}_{\xi\sim\mathcal{D}_{k}}[f_{k}(\mathbf{w};\xi)]$
denotes the loss function of client $k$ and $\mathcal{P}$ is the distribution
over users. The generalized FedAvg algorithm, FedOpt [27], interactively
learns the global model by randomly selecting at time $t$ a subset of clients
$S_{t}$ to locally optimize their objective function111E.g., the original
FedAvg algorithm coordinates $E$ epochs over training data. starting from the
initial model $\overline{\mathbf{w}}^{t}$, and communicate their updates
$\mathbf{v}_{k}^{t+1}$ to the server. Then, the server aggregates the received
updates $(\mathbf{v}_{k}^{t+1})_{k\in S_{t}}$ to produce the global update
$\Delta^{t+1}$ and generate a new global model $\overline{\mathbf{w}}^{t+1}$.
For the remainder of the paper we refer to the process of going from
$\overline{\mathbf{w}}^{t}$ to $\overline{\mathbf{w}}^{t+1}$ as a (single)
round of FL. The process is repeated with the aim of finding accurate global
model. Heterogeneity due to generally non-i.i.d. and unbalanced data available
to different clients emerges as one of the main challenges in federated
learning, and thus the choice of a client sampling scheme heavily impacts
convergence of the global model. Several authors have addressed this problem,
proposing different optimizers [27] and client sampling strategies [9, 22],
but all showed convergence (or near convergence) only under the strong
assumption of being able to sample any client at any time. A technique that
deals with heterogeneity by allowing each client to learn a personalized model
was proposed in [32].

Several approaches to addressing communication constraints in FL systems have
recently been proposed in literature, including strategies aiming to reduce
client communication rate via model compression [38, 19, 36, 18, 2, 13]. These
are orthogonal to our work since we focus on settings where the clients are
intermittently available.

##### Client availability.

We assume that, at any time, the set of available clients is random and non-
empty, and that the constraint on the number of clients selected to train and
provide model updates to the server generally varies over time. Note that, in
such scenarios, applying recent stateful optimization techniques such as
Scaffold [17] and FedDyn [1] is challenging due to hardware constraints and
high number of participating devices [40]. Prior work has investigated client
availability under restrictive conditions such as block-cyclic data
characteristics [10, 9], assumed i.i.d. availability across clients that act
as stragglers [21], or produced biased models [42]. However, availability is
much more difficult to model in practice. Although certain patterns such as
day/night are cyclic, there also exist various other non-cyclic client or
cluster-specific patterns that affect some clients more than others, including
access to a power source and the available communication bandwidth.

###  2.2 Client sampling and averaging

Since the number of clients in federated learning systems can be extremely
large [11, 43], only a relatively small subset of them is tasked with training
in each round. Data heterogeneity and communication constraints have inspired
several strategies for selecting clients from the available pool. Some of
those techniques take into account the proportion of data at each client,
which we denote by $p_{k}$ [22]. Alternative strategies apply active learning
ideas to client selection and select those that are more promising according
to some metric, e.g., choose clients with the largest magnitude of the updates
[14, 7, 31, 28, 29] or those with the highest loss [9].

Another line of related prior work has been focused on investigating model
aggregation strategies. In [28], the authors assume that stochastic
optimization updates approximately follow a stationary stochastic process, and
cast the model aggregation as an estimation problem. An alternative
aggregation strategy is to form an unweighted average of the updates [9];
however, this leads to a biased model and large variance. Other approaches
trade communication and memory for stable convergence [17], or replace missing
updates with the previous model [7, 31]. In the centralized setting,
importance sampling has been used to optimally aggregate SGD updates [45],
[29].

Previous works on client sampling in FL systems do not provide formal
convergence guarantees for settings where the clients are intermittently
available. Cho et al. [9], Eichner et al. [10] study effects of cyclically
alternating client availability and propose a sampling strategy empirically
shown to improve over random sampling; however, the resulting models may be
biased and their performance under non-cyclic availability patterns is
unclear.

Alternatively, asynchronous methods address client selection under system
heterogeneity with a fixed selection policy determined by clients training
speed: updates are incorporated individually as they arrive at the server [8]
or, when there are privacy concerns, they are aggregated in buffers [25].

##  3 Methods

In this section we present and analyze a novel framework for selecting and
aggregating intermittently available clients in federated learning systems
that operate under time-varying communication constraints. In such settings,
the contribution each client makes to the federated averaging process depends
on how often the client is selected to provide an update – i.e., on the long-
term client participation rate. We start by characterizing the set
$\mathcal{R}$ of achievable long-term client participation rates subject to
communication and client availability constraints. Then, we introduce F3ast,
an algorithm that dynamically learns clients’ long-term participation rate and
improves the convergence of federated learning by reducing the model bias and
minimizing variance introduced by sampling intermittently available clients.
The omitted proofs can be found in the appendix.

###  3.1 Preliminaries

##### Communication constraints and intermittent client availability.

Consider a FL system in which a random subset of clients $\mathbf{A}_{t}$ is
available/responsive at time $t$; here
$(\mathbf{A}_{1},\mathbf{A}_{2},\dots)=(\mathbf{A}_{t})_{t}$ form a discrete-
time stochastic process with a finite state space
$\mathcal{A}=2^{\mathcal{U}}$, i.e., the collection of all possible subsets of
the set of users $\mathcal{U}$. Communication constraints restrict the
possible subsets of clients that can be chosen to participate during a
training round; we let $\mathbf{C}_{t}$ denote the (random) collection of the
available clients sets that meet communication constraints at time $t$ and
denote its state space by $\mathcal{C}$; given $\mathbf{A}_{t}=A$, a
realization $\mathbf{C}_{t}=C$ corresponds to a collection of subsets of $A$,
i.e., $C\subseteq 2^{A}$. For convenience, in the remainder of the paper we
refer to $\mathbf{C}_{t}$ as the system configuration.

To illustrate the use of the introduced notation, consider the communication-
constrained setting where the number of clients allowed to participate in
training round $t$ is no more than (possibly random) $K_{t}$. Given a
realization of the set of clients available at time $t$, $\mathbf{A}_{t}=A$,
and the aforementioned communications constraint $K_{t}=k\in\mathbb{N}$, the
collection of feasible client sample sets $S$ that the server may choose to
include in the training round is

$C=\\{S\subset A:|S|\leq k\\}.$

If the communication constraints are not time-varying, i.e., if $K_{t}=k$
almost surely for all $t$, we are back in the traditional FedAvg cross-device
setting.

######  Assumption 1.

The sequence of random collections of feasible client sampling sets
$(\mathbf{C}_{t})_{t}$ forms a discrete-time irreducible Markov chain with a
finite state space $\mathcal{C}\subseteq 2^{\mathcal{U}}$ and a stationary
distribution $\pi=(\pi(C),C\in\mathcal{C})$.

1 significantly relaxes assumptions typically made when analyzing convergence
of state-of-the-art FL algorithms, e.g., the much stronger assumptions of all
users having unlimited availability [23, 26, 24, 21, 1, 17] or a deterministic
block-cyclic availability [10]. 1 captures various realistic settings
including that of home devices available with a given probability - not
necessarily uniform across clients - throughout the day. Our experimental
results showcase that in several realistic settings which meet 1, our method
provides significant performance improvements while other techniques fail to
adapt to unknown availability models.

##### Static configuration-dependent client sampling policies.

Communication constraints and intermittent client availability restrict the
space of admissible long-term client participation rates. Indeed, it is
unrealistic to expect being able to sample an arbitrary collection of $k$
clients at time $t$ with pre-specified probabilities
$\mathcal{P}=(p_{i}:i=1\ldots N)$ since some of those $k$ clients may be
unavailable, and/or time horizon is not long enough to achieve certain rate
(see examples in Section 1). To characterize achievable long-term
participation rates we introduce the following concepts.

Recall that for a given configuration of communication constraints and client
availabilities there exists an associated collection of feasible client sample
sets $C$ that a sampling policy can choose from. We define a static
configuration-dependent client sampling policy as follows.

######  Definition 3.1.

For each $C$, let $f_{C,S}\geq 0$ denote the probability of selecting the
subset of clients $S\in C$, where $\sum_{\mathcal{S}\in C}f_{C,S}=1$. If we
denote $\bm{f}_{C}=(f_{C,S},S\in C)$, then
$\bm{f}:=(\bm{f}_{C},C\in\mathcal{C})$ specifies a static configuration-
dependent sampling policy selecting clients over different
communication/availability configurations.

Let ${\cal F}$ denote the set of possible static configuration-dependent
client sampling policies. Under the above model, the long-term client
participation rate can be expressed as

$\mathbf{r}^{\bm{f}}=\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f_{{}_{C,S}}\mathds{1}_{S},$ (2)

where $\mathds{1}_{S}$ is an $N$-dimensional binary indicator vector whose
$i^{th}$ entry is $1$ if the $i^{th}$ client is in $S$, and is $0$ otherwise.
One can interpret the $i^{th}$ component of vector $\mathbf{r}^{\bm{f}}$ as
the fraction of time the $i^{th}$ client is selected by the server.

Finally, we define the long-term client participation rate region as the set
of all possible long-term participation rate vectors $\mathbf{r}^{\bm{f}}$,
i.e., $\mathcal{R}:=\\{\mathbf{r}^{\bm{f}}|\bm{f}\in{\cal F}\\}$.

######  Lemma 3.2.

The long-term client participation rate region
$\mathcal{R}=\\{\mathbf{r}^{\bm{f}}|\bm{f}\in{\cal F}\\}$ is a subset of the
simplex in the $N$-dimensional Euclidean space, and a closed convex set.

###### Proof.

The lemma follows from the fact that $\mathcal{R}$ is a linear image of all
possible $\bm{f}$, a closed bounded convex set. ∎

###  3.2 F3ast : Minimizing the sampling variance

Here we formally introduce an algorithm that learns a client selection policy
which ensures that the resulting long-term client participation rate converges
to a value minimizing

$H(\mathbf{r}):=\begin{cases}\vspace{-0.05in}\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}&\text{client
availability is }\\\ &\text{positively correlated,}\\\
\sum_{k=1}^{N}\frac{p^{2}_{k}}{r_{k}}&\text{ otherwise}.\\\ \end{cases}$ (3)

It is readily shown that $H(\mathbf{r})$ bounds the variance induced in the
global model by the selection policy with rate $\mathbf{r}$. For the ease of
exposition we postpone that discussion to Section 3.2.2 in favor of first
presenting our proposed algorithm.

F3ast (Federated Averaging Aided by an Adaptive Sampling Technique), is
presented as Algorithm 1. Formally, F3ast aims to find a configuration-
dependent client sampling strategy $\bm{f_{\text{{F3ast} }}}$ such that its
long-term client participation rate $\mathbf{r}_{\text{{F3ast} }}$
approximates the optimal achievable strategy
$\mathbf{r}^{*}\in\text{argmin}_{\mathbf{r}\in\mathcal{R}}H(\mathbf{r})$. To
accomplish this, F3ast first initializes $\mathbf{r}(0)$ arbitrarily (line 2).
At each round $t$, with $\mathbf{C}_{t}=C_{t}$, selecting set $S\in C_{t}$
implies a contribution to the participation rate of $1$ for every client $k\in
S$. Whether or not selecting set $S$ brings $r(t)$ closer to $\mathbf{r}^{*}$
can be computed by estimating the marginal utility of $S$ using the gradient
of $H(\mathbf{r})$. Thus, we select $S_{t}$ (line 5) as

$S_{t}\in\arg\max_{S\in C_{t}}-\nabla H(\mathbf{r}(t))\cdot\mathds{1}_{S}.$
(4)

In general, (4) is a combinatorial optimization problem; in the federated
learning systems with a time-varying bound on the number of clients $K_{t}$
that can be selected ($K_{t}\geq 0$), (4) reduces to the discrete optimization
problem of greedily selecting $K_{t}$ available clients with the largest
entries of $-\nabla H(\mathbf{r}(t))$. Optimality of the greedy approach
follows because the objective is an additive set function.

Figure 2: Test per-sample accuracy (averaged over three runs) for different
client sampling and aggregation schemes under HomeDevice availability model.
We observe that F3ast consistently outperforms FedAvg and PoC . Further, F3ast
stabilizes while FedAvg and PoC are unable to adapt to the time-varying
environment.

Next, the rate is updated to reflect the selection made in the latest
iteration of the sampling scheme. This is done by forming an exponentially
smoothed average of the past sampling rates (line 6),

$\mathbf{r}(t+1)=(1-\beta)\mathbf{r}(t)+\beta\mathds{1}_{S},$ (5)

where $\beta>0$ is a fixed small parameter. After having selected clients
$S_{t}$, the server broadcasts the current model and the selected clients
perform local updates. Finally, the server uses $\mathbf{r}(t)$ to produce an
unbiased global model $\overline{\mathbf{w}}^{t+1}$ with estimator
$\Delta^{t+1}$ (lines 9-10).

0: Server parameters: learning rate schedule $\\{\eta_{t}\\}_{t=1}^{T}$, the
number of global rounds $T$, the number of clients per round $K_{t}$, the
number of client local updates $E$

0: Global model $\overline{\mathbf{w}}_{T}$

1: initialize $\overline{\mathbf{w}}_{0}\in\mathbb{R}^{p}$ arbitrarily,
initialize $\mathbf{r}(0)$ arbitrarily

2: for $t=1\to T$ do

3: $C_{t}\quad\leftarrow$ feasible client sets at time $t$

4: $S_{t}\in\text{argmin}_{S\in C_{t}}\nabla H(\mathbf{r}_{t})\mathds{1}_{S}$

5: $\mathbf{r}(t)=(1-\beta)\mathbf{r}(t-1)+\beta\mathds{1}_{S}$

6: for Clients $k\in S_{t}$, in parallel do

7:
$\mathbf{v}_{k}^{t+1}\leftarrow\textsc{ClientOpt}(\overline{\mathbf{w}}^{t},E\text{
steps},\eta_{t})$

8: end for

9: $\Delta^{t+1}\leftarrow\sum_{k\in
S_{t}}\frac{p_{k}}{r_{k}(t)}\mathbf{v}_{k}^{t+1}$

10:
$\overline{\mathbf{w}}^{t+1}\leftarrow\textsc{ServerOpt}(\overline{\mathbf{w}}^{t},\Delta^{t+1})$

11: end for

Algorithm 1 F3ast : Federated Averaging Aided by an Adaptive Sampling
Technique

##### Beyond FedAvg .

F3ast modifies two crucial steps in FedAvg : client sampling and model
updates aggregation. This makes it suitable to work in combination with other
FL algorithms like Scaffold [17], AFL [24], FedProx [21], FedDyn [1], and more
generally FedOpt [27]. These methods’ theoretical guarantees are provided
under the “all clients are available” assumption, implying that they assume an
unrealistic fixed sampling policy which introduces bias to the model. Our
proof extends to those settings by modifying accordingly sampling and
aggregation to the asymptotically learned $\mathbf{r}$ as long as the
$\ell_{2}$-norms of clients’ model updates are uniformly bounded – an
assumption already made by the above methods.

####  3.2.1 Asymptotic optimality

Below we show that as $\beta\downarrow 0$, the selection policy rate converges
to the value that optimizes $H(\mathbf{r})$ and, therefore, reduces the model
variance. To this end, consider the discrete time Markov process
$S^{\beta}(t)=(\mathbf{r}^{\beta}(t),\mathbf{C}_{t})$ indexed by the value of
$\beta$ defined in Eq. (5), with $\beta\downarrow 0$ along sequence
$\mathcal{B}=\\{\beta_{j}\\}_{j\in\mathbb{N}}$. $S^{\beta}(0)$ and the
probability law of $\mathbf{C}_{t}$ describing the availability model are
fixed for all $\beta\in\mathcal{B}$. The speed of convergence is discussed in
the appendix.

######  Theorem 3.3.

Let $\mathbf{r}^{\beta}(t)$ be the rate determined by Algorithm 1. Let
$V\subset\mathbb{R}_{+}^{N}$ be a bounded set, $\epsilon>0$, and let
$\mathbf{r}^{*}$ denote the minimizer of the variance function $H(\mathbf{r})$
over $\mathcal{R}$. Then for $T>0$, depending on $\epsilon$ and $V$,

$\lim_{\beta\downarrow 0}\quad\sup_{\mathbf{r}^{\beta}(0)\in
V,t>T/\beta}P[\|\mathbf{r}^{\beta}(t)-\mathbf{r}^{*}\|>\epsilon]=0.$

####  3.2.2 Bounding the global model variance

We start by analyzing a fixed arbitrary stochastic policy
$\bm{f}^{\mathbf{r}}$ achieving rate $\mathbf{r}$ and use the result to
demonstrate that $H($$\mathbf{r}$$)$ reflects the model variance induced by
$\bm{f}^{\mathbf{r}}$ (for more details, please see appendix). Let us
introduce several assumptions regarding clients’ loss functions
$F_{k}(\mathbf{w})=\mathbb{E}_{\xi\sim\mathcal{D}_{k}}\left[f_{k}(\mathbf{w};\xi)\right]$,
$1\leq k\leq N$; these assumptions are commonly encountered in the federated
learning literature [22, 9].

######  Assumption 2.

[Smoothness and strong convexity] $F_{1},...,F_{N}$ are $L-$smooth and
$\mu-$strongly convex functions, meaning that for all $v$ and $w$,
$F_{k}(\mathbf{v})\leq F_{k}(\mathbf{w})+\nabla
F_{k}(\mathbf{w})^{T}(\mathbf{v}-\mathbf{w})+\frac{L}{2}\|\mathbf{v}-\mathbf{w}\|_{2}^{2}$
and $F_{k}(\mathbf{v})\geq F_{k}(\mathbf{w})+\nabla
F_{k}(\mathbf{w})^{T}(\mathbf{v}-\mathbf{w})+\frac{\mu}{2}\|\mathbf{v}-\mathbf{w}\|_{2}^{2}$,
respectively.

######  Assumption 3.

[Bounded variance] Let $\xi$ be a data point that client $k$ samples from
distribution $\mathcal{D}_{k}$. Then
$\mathbb{E}_{\xi\sim\mathcal{D}_{k}}[\|\nabla f_{k}(\mathbf{w},\xi)-\nabla
F_{k}(\mathbf{w})\|_{2}^{2}]\leq\sigma_{k}^{2}$, $k=1,...,N$

######  Assumption 4.

[Bounded stochastic gradients] The expected norm of the stochastic gradients
of $f_{k}$ is uniformly bounded, i.e.,
$\mathbb{E}_{\xi\sim\mathcal{D}_{k}}[\|\nabla
f_{k}(\mathbf{w},\xi)\|_{2}^{2}]\leq G^{2}$, $k=1,...,N$.

Assumption 2 holds in a number of scenarios of interest, including
$\ell_{2}$-regularized linear and logistic regression, and classification with
softmax function. Assumptions 3 and 4 are common in state-of-the-art
distributed learning literature [44, 33, 34, 37]. Note that while we rely on
the above assumptions when analyzing the performance, experimental results
demonstrate that our sampling techniques work very well in more general
settings involving highly non-linear models such as convolutional and
recurrent neural networks trained on realistic datasets.

The following lemma introduces and analyzes
$\sigma^{2}_{t}(\bm{f}^{\mathbf{r}})$, the client sampling variance under
sampling policy $\bm{f}^{\mathbf{r}}$.

######  Lemma 3.4.

Suppose Assumptions 1-4 hold. Let $\mathbf{r}\in\mathcal{R}$ be an achievable
long-term client participation rate under the system configuration determined
by distribution $\pi$, and $\bm{f}^{\mathbf{r}}$ denote a static
configuration-dependent selection policy achieving $\mathbf{r}$. Define the
client sampling variance
$\sigma^{2}_{t}(\bm{f}^{\mathbf{r}}):=\frac{1}{\eta_{t}^{2}}\mathbb{E}_{S_{t}}\left[\|\Delta^{t}-\overline{\mathbf{v}}^{t}\|^{2}\right]$
where $\overline{\mathbf{v}}^{t}=\sum_{k=1}^{N}p_{k}\mathbf{v}^{k}_{t}$ is the
update at time $t$ with full client participation. Then

$\sigma_{t}^{2}(\bm{f}^{\mathbf{r}})\leq
4E^{2}G^{2}(\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}-1).$ (6)

Furthermore, if client availabilities are uncorrelated or negatively
correlated, then there exists a policy $\bm{f}^{r}$ such that

$\sigma_{t}^{2}(\bm{f}^{\mathbf{r}})\leq
4E^{2}G^{2}\left(\sum_{k=1}^{N}\frac{p_{k}^{2}}{r_{k}}+\sum_{k=1}^{N}p_{k}^{2}\right).$
(7)

######  Theorem 3.5.

Instate the settings of Lemma 3.4. Let $\mathbf{w}^{*}$ denote the solution to
the optimization problem (1), and $L,\mu=O(1)$. Define
$\gamma=\max\\{8\frac{L}{\mu},E\\}$, and assume learning rate
$\eta_{t}=\frac{2}{\mu(\gamma+t)}$. Then by setting ClientOpt to SGD and
ServerOpt$(\overline{\mathbf{w}}^{t},\Delta^{t+1})=\overline{\mathbf{w}}^{t}+\Delta^{t+1}$,
the model $\overline{\mathbf{w}}^{T}$ produced with policy
$\bm{f}^{\mathbf{r}}$ after $T$ steps satisfies

$\displaystyle\mathbb{E}[F(\overline{\mathbf{w}}^{T})]$
$\displaystyle-F^{*}=O\left(\frac{1}{TE+\gamma}\left(\|\mathbf{w}_{1}-\mathbf{w}^{*}\|^{2}\right.\right.$
$\displaystyle+\sum^{N}_{k=1}p_{k}^{2}\sigma_{k}^{2}+\left.\left.6\Gamma+8(E-1)^{2}G^{2}+\sigma_{T}^{2}(\bm{f}^{\mathbf{r}})\right)\right),$
(8)

where $\Gamma=F^{*}-\sum_{k=1}^{N}p_{k}F_{k}^{*}$ denotes the local-global
objective gap222Local-global objective gap quantifies data heterogeneity: for
i.i.d. data, $\Gamma\to 0$ as the number of samples grows, while a large
$\Gamma$ indicates a high degree of heterogeneity [22, 9]., $F^{*}$ and
$F_{k}^{*}$ are the minimum values of $F$ and $F_{k}$, respectively, and
$\sigma_{T}(\mathbf{r})$ (Lemma 3.4) captures the variance induced by client
sampling.

######  Remark 3.6.

Proof of Theorem 3.5 follows the line of argument similar to that in the
analysis of FL algorithms convergence [33, 22, 27]. The first term in the
parenthesis in eq. (3.5) captures the effect of initialization, while the
second term reflects the variance of stochastic gradients. The remaining terms
are tied to the inherent challenges of data heterogeneity in FL.

In summary, our presented technical contributions include: (i) developing an
arbitrary selection policy with feasible long-term client participation rate
$\mathbf{r}$ (meanwhile, the result of Li et al. [22] applies only to two
specific - potentially unfeasible in real settings - sampling schemes); (ii)
showing the global update is unbiased under this selection policy and
aggregation step; and (iii) computing the incurred variance captured by the
last term $\sigma_{T}^{2}(\mathbf{r})$ and bounded in Lemma 3.4.

##### From static to dynamic policies.

Aiming to circumvent the requirement for having access to (generally
unavailable) system configuration information that applies to static selection
policies, we proceed by combining expressions (6) and (7) (ignoring constant
terms) to define

$H(\mathbf{r}):=\begin{cases}\vspace{-0.05in}\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}&\text{client
availability is }\\\ &\text{positively correlated,}\\\
\sum_{k=1}^{N}\frac{p^{2}_{k}}{r_{k}}&\text{ otherwise.}\\\ \end{cases}$

Clearly, minimizing $H(\mathbf{r})$ over $\mathbf{r}$ reduces the upper bound
on the model variance stated in Lemma 3.4. It follows from Equation 2 that
$r_{k}\leq 1$, and thus it can readily be shown that $r_{k}=1$ for all $k$
minimizes $H(\mathbf{r})$ over $[0,1]^{N}$. However, it is possible that for a
given configuration of the system this long-term client participation rate is
not achievable, i.e., $\bm{1}\notin\mathcal{R}$ (the set of feasible
$\mathbf{r}$’s defined in Lemma 3.2). Recalling the example in Section 1,
minimization of $H(\mathbf{r})$ over $\mathcal{R}$ is also difficult because
it requires knowledge of the achievable long-term client participation rate
region $\mathcal{R}$, determined by the distribution $\pi$ defined in
Assumption 1. Finally, even if $\mathcal{R}$ is known, the resulting policy
$\bm{f}^{\mathbf{r}}$ will likely be client and set dependent, thus rendering
the problem challenging due to an exponential number of variables and unknown
parameters. These are precisely the obstacles that F3ast overcomes by learning
a selection policy which is asymptotically optimal in terms of minimizing
$H(\mathbf{r})$, and guaranteeing convergence to a long-term participation
rate minimizing $H(\mathbf{r})$ over $\mathcal{R}$.

Table 2: Test sample accuracy of all methods, and relative improvements of F3ast over FedAvg and F3ast \+ Adam over FedAdam , for different availability models (columns) on CIFAR100 (1000 rounds) and Shakespeare (500 rounds). |  | Availability models
---|---|---
|  | Always | Scarce | HomeDevice | Uneven | SmartPhones
CIFAR100 | FedAvg | 0.141 | 0.096 | 0.111 | 0.072 | 0.142
F3ast | 0.198 (+40%) | 0.201 (+109%) | 0.208 (+87%) | 0.206 (+186%) | 0.201 (+42%)
7 |  |  |  |  |  |
| FedAdam | 0.262 | 0.288 | 0.302 | 0.282 | 0.298
|  F3ast \+ Adam |  0.271 (+3%) |  0.308 (+7%) |  0.324 (+7%) |  0.281 (0%) |  0.320 (+7%)
7 |  |  |  |  |  |
| PoC | 0.101 | 0.115 | 0.139 | 0.111 | 0.069
Shakespeare | FedAvg | 0.54 | 0.549 | 0.522 | 0.540 | 0.538
F3ast |  0.569 (+5%) |  0.555 (+1%) |  0.568 (+9%) | 0.556 (+3%) | 0.570 (+6%)
7 |  |  |  |  |  |
| FedAdam | 0.536 | 0.541 | 0.520 | 0.557 | 0.520
|  F3ast \+ Adam | 0.549 (+2%) | 0.551 (+2%) | 0.566 (+9%) |  0.557 (0%) | 0.551 (+6%)
7 |  |  |  |  |  |
| PoC | 0.554 | 0.555 | 0.496 | 0.555 | 0.535
Table 3: Sample loss of all methods, and relative improvements of F3ast over FedAvg and F3ast \+ Adam over FedAdam , for different availability models (columns) on CIFAR100 (1000 rounds) and Shakespeare (500 rounds). |  | Availability model
---|---|---
|  | Always | Scarce | HomeDevice | Uneven | SmartPhones
CIFAR100 | FedAvg | 4.42 | 4.77 | 4.74 | 5.29 | 4.28
F3ast | 4.20 (-5%) | 4.18 (-12%) | 4.14 (-13%) | 4.17 (-21%) | 4.15 (-3%)
7 |  |  |  |  |  |
| FedAdam | 3.74 | 3.65 | 3.50 | 3.67 | 3.55
|  F3ast \+ Adam |  3.69 (-1%) |  3.61 (-1%) |  3.45 (-1%) |  3.66 (-0.5%) |  3.46 (-2%)
7 |  |  |  |  |  |
| PoC | 4.90 | 4.84 | 4.63 | 4.86 | 5.42
Shakespeare | FedAvg | 1.24 | 1.15 | 1.36 | 1.17 | 1.22
F3ast |  1.10 (-11%) |  1.13 (-1%) |  1.10 (-19%) | 1.13 (-3%) |  1.10 (-10%)
7 |  |  |  |  |  |
| FedAdam | 1.27 | 1.23 | 1.40 | 1.12 | 1.36
|  F3ast \+ Adam | 1.18 (-8%) | 1.19 (-3%) | 1.11 (-21%) |  1.11  (-1%) | 1.18 (-13%)
7 |  |  |  |  |  |
| PoC | 1.13 | 1.13 | 1.74 | 1.13 | 1.24

##  4 Experiments

###  4.1 Datasets and models

We test our model on three well-known federated datasets. First, a synthetic
heterogenous dataset Synthetic(1,1) for softmax regression, introduced in [30]
and widely used in the FL community [9, 21, 22]. Second, a recurrent neural
network with 1M parameters for the next character prediction task on the
Shakespeare dataset [23], a language modelling dataset with 725 clients, each
one a different speaking role in each play from the collective works of
William Shakespeare. Third, CIFAR100 with the partition introduced in [27],
utilizing Latent Dirichlet Allocation in order to generate a realistic
heterogenous distribution. We train ResNet-18, replacing batch with group
normalization, a modification that has shown improvements in federated
settings [15]. Our code is available on
Github333https://github.com/mriberodiaz/f3ast

##### Availability models.

We perform tests on five realistic availability models described below. To our
knowledge, there exist no public databases with real availability patterns;
Smartphone’s model [5] is inspired by realistic data. All models are motivated
by practical federated learning systems:

  1. 1.

Always: Baseline model, clients are always available.

  2. 2.

Scarce: Independent and homogeneous availability across clients and time with
probability $q=0.2$.

  3. 3.

Home-devices: Independent availability across clients and time with
probability $q_{k}=T_{k}/B$, where $T_{k}\sim\mbox{\rm lognormal}$ and
$B=\max_{k}T_{k}$.

  4. 4.

Smartphones: Sine-modulated Home-devices model, $q_{k,t}=f_{t}q_{k}$, where
$q_{k}$ is defined in the Home-devices model and $f_{t}$ denotes a sinusoidal
time-dependent availability (see [5]).

  5. 5.

Uneven: Each client’s availability is inversely proportional to its dataset
size, $q_{k}\propto 1/p_{k}$.

We split each client’s dataset into training and validation sets. We assume
the distribution $\mathcal{P}$ over users is determined by the fraction of
data they possess. In the following, we first fix the communication constraint
to select $M=10$ clients in each round and compare different methods across
availability models. We then proceed by exploring the effect of varying $M$.
Further details on the data sets, model architectures, availability modeling,
and hyperparameters can be found in Appendix D.3. We implement our models
using the Tensorflow-Federated API [39].

##### Baselines.

First, we compare our algorithm with two availability-agnostic methods: (i)
FedAvg , a standard baseline, and (ii) FedAdam , which achieves state-of
the-art performance in the considered benchmark tasks [27]. Both methods
sample available clients with normalized probabilities $p_{k}$, but FedAvg
uses SGD as the server optimizer while FedAdam uses Adam. For a fair
comparison, we implement both methods and compare with their availability-
aware versions wherein we incorporate our proposed sampling and aggregation
step.

Second, we test against a state-of-the-art algorithm, Power-of-Choice (PoC )
[9], a method that, although agnostic to the availability model, can work in
conjuction with client unavailability. In PoC , the server at time $t$ samples
$d$ clients from the available set $C_{t}$ without replacement, choosing
client $k$ with probability $p_{k}$. The $d$ clients receive the current model
$\mathbf{w}_{t}$ and inform the server about their current loss
$F_{k}(\overline{\mathbf{w}}^{t})$. The server then selects for training the
top $M$ clients with the highest loss.

We do not compare our method with stateful techniques (Scaffold, FedDyn) since
they are not applicable in the cross-device federated settings [16].

To evaluate performance of the algorithms, we compute the loss and accuracy
using per-test-sample averages (the average is taken over individual data
points). Per-user average results can be found in the appendix.

###  4.2 Numerical results.

We first show the convergence of F3ast on the three datasets with Home-devices
availability model, a setting that fits Assumption 1 and is realistic in FL
(note that the synthetic dataset satisfies all assumptions from Section 3).
Corroborating expectations of the impact of the de-biasing step introduced by
F3ast , Figure 2 shows that F3ast achieves higher accuracy than FedAvg and
PoC on all datasets (the corresponding loss plot can be found in Appendix D).
Moreover, after the first 100 iterations, F3ast stabilizes on Shakespeare and
Synthetic datasets, and follows a more stable learning trajectory,
illustrating its variance reduction advantage, unlike the two baselines that
have high variability due to time-varying client availability. The sharp drop
in Shakespeare is caused by sampling a client misaligned due to the
heterogenous nature of the data; this has been reported in [6]. We show an
average over three runs in Appendix D. We observe a similar behaviour on
CIFAR100: F3ast achieves almost a 200% improvement in the average accuracy
over the last 100 rounds, and has a much more stable behaviour. The stagnation
of FedAvg and PoC at higher loss models confirms that naive averaging
introduces bias to the model, hindering convergence.

Table 2 shows the final accuracy of algorithms under diverse availability
models defined in Section 4.1 (1000 rounds on CIFAR100 and 500 rounds on
Shakespeare 444Higher accuracy values on CIFAR100 could be obtained by running
experiments for 10,000+ rounds). F3ast effectively improves the accuracy of
FedAvg over both datasets and for all availability models. It also improves
FedAdam for all but the Uneven model where the accuracy remains the same
although the loss value is lower (Table 3). F3ast is particularly successful
in difficult settings, e.g. Scarce and Uneven, where a small number of clients
is available for training and where the client availability is inversely
proportional to the amount of data clients hold – there, F3ast is able to
maintain performance similar to the setting where all clients are available.
Meanwhile, the performance of both FedAvg and PoC deteriorates. FedAdam is
able to maintain performance in the Uneven model where momentum may help with
biased updates, but deteriorates in all other settings.

##  5 Conclusion

We presented F3ast , an algorithm for learning in federated systems that
operate under communication constraints and service intermittently available
clients. We demonstrated that the algorithm achieves accuracy superior to
state-of-the-art federated learning techniques, and exhibits resilience in
challenging system settings. Future work includes studies of the setting where
the clients are grouped in clusters/classes, and exploring a wider range of
communication constraints.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under grant no. 2148224 and is supported in part by funds from OUSD R&E, NIST,
and industry partners as specified in the Resilient & Intelligent NextG
Systems (RINGS) program.

## References

  * Acar et al. [2021] Acar, D. A. E., Zhao, Y., Matas, R., Mattina, M., Whatmough, P., and Saligrama, V.  Federated learning based on dynamic regularization.  In _International Conference on Learning Representations_ , 2021.
  * Alistarh et al. [2017] Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M.  QSGD: Communication-efficient SGD via gradient quantization and encoding.  In _Advances in Neural Information Processing Systems_ , pp. 1709–1720, 2017.
  * Alouf et al. [2002] Alouf, S., Altman, E., and Nain, P.  Optimal online estimation of the size of a dynamic multicast group.  In _Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies_ , volume 2, pp. 1109–1118 vol.2, 2002\.  doi: 10.1109/INFCOM.2002.1019359.
  * Billingsley [2013] Billingsley, P.  _Convergence of probability measures_.  John Wiley & Sons, 2013.
  * Bonawitz et al. [2019] Bonawitz, K., Eichner, H., Grieskamp, W., Huba, D., Ingerman, A., Ivanov, V., Kiddon, C., Konečnỳ, J., Mazzocchi, S., McMahan, H. B., et al.  Towards federated learning at scale: System design.  _arXiv preprint arXiv:1902.01046_ , 2019.
  * Charles et al. [2021] Charles, Z., Garrett, Z., Huo, Z., Shmulyian, S., and Smith, V.  On large-cohort training for federated learning.  _arXiv preprint arXiv:2106.07820_ , 2021.
  * Chen et al. [2018] Chen, T., Giannakis, G., Sun, T., and Yin, W.  LAG: Lazily aggregated gradient for communication-efficient distributed learning.  In _Advances in Neural Information Processing Systems_ , pp. 5050–5060, 2018.
  * Chen et al. [2020] Chen, Y., Ning, Y., Slawski, M., and Rangwala, H.  Asynchronous online federated learning for edge devices with non-iid data.  In _2020 IEEE International Conference on Big Data (Big Data)_ , pp. 15–24. IEEE, 2020.
  * Cho et al. [2020] Cho, Y. J., Wang, J., and Joshi, G.  Client selection in federated learning: Convergence analysis and power-of-choice selection strategies.  _arXiv preprint arXiv:2010.01243_ , 2020.
  * Eichner et al. [2019] Eichner, H., Koren, T., McMahan, B., Srebro, N., and Talwar, K.  Semi-cyclic stochastic gradient descent.  In _International Conference on Machine Learning_ , pp. 1764–1773. PMLR, 2019.
  * Hard et al. [2018] Hard, A., Rao, K., Mathews, R., Ramaswamy, S., Beaufays, F., Augenstein, S., Eichner, H., Kiddon, C., and Ramage, D.  Federated learning for mobile keyboard prediction.  _arXiv preprint arXiv:1811.03604_ , 2018.
  * He et al. [2016] He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Horvath et al. [2019] Horvath, S., Ho, C.-Y., Horvath, L., Sahu, A. N., Canini, M., and Richtarik, P.  Natural compression for distributed deep learning.  _arXiv preprint arXiv:1905.10988_ , 2019.
  * Hsieh et al. [2017] Hsieh, K., Harlap, A., Vijaykumar, N., Konomis, D., Ganger, G. R., Gibbons, P. B., and Mutlu, O.  Gaia: Geo-distributed machine learning approaching $\\{$LAN$\\}$ speeds.  In _14th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 17)_, pp. 629–647, 2017.
  * Hsieh et al. [2020] Hsieh, K., Phanishayee, A., Mutlu, O., and Gibbons, P.  The non-iid data quagmire of decentralized machine learning.  In _International Conference on Machine Learning_ , pp. 4387–4398. PMLR, 2020.
  * Kairouz et al. [2019] 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.  _arXiv preprint arXiv:1912.04977_ , 2019.
  * Karimireddy et al. [2020] Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T.  Scaffold: Stochastic controlled averaging for federated learning.  In _International Conference on Machine Learning_ , pp. 5132–5143. PMLR, 2020.
  * Konečnỳ & Richtárik [2018] Konečnỳ, J. and Richtárik, P.  Randomized distributed mean estimation: Accuracy vs. communication.  _Frontiers in Applied Mathematics and Statistics_ , 4:62, 2018.
  * Konečnỳ et al. [2016] Konečnỳ, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ , 2016.
  * Levin & Peres [2017] Levin, D. A. and Peres, Y.  _Markov chains and mixing times_ , volume 107.  American Mathematical Soc., 2017.
  * Li et al. [2018] Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V.  Federated optimization in heterogeneous networks.  _arXiv preprint arXiv:1812.06127_ , 2018.
  * Li et al. [2019] Li, X., Huang, K., Yang, W., Wang, S., and Zhang, Z.  On the convergence of fedavg on non-iid data.  _arXiv preprint arXiv:1907.02189_ , 2019.
  * McMahan et al. [2017] McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In _Proceedings of the 20th International Conference on Artificial Intelligence and Statistics_ , volume 54 of _Proceedings of Machine Learning Research_ , pp. 1273–1282. PMLR, 2017.
  * Mohri et al. [2019] Mohri, M., Sivek, G., and Suresh, A. T.  Agnostic federated learning.  In _International Conference on Machine Learning_ , pp. 4615–4625. PMLR, 2019.
  * Nguyen et al. [2021] Nguyen, J., Malik, K., Zhan, H., Yousefpour, A., Rabbat, M., Malek, M., and Huba, D.  Federated learning with buffered asynchronous aggregation.  _arXiv preprint arXiv:2106.06639_ , 2021.
  * Rabi et al. [2012] Rabi, M., Moustakides, G. V., and Baras, J. S.  Adaptive sampling for linear state estimation.  _SIAM Journal on Control and Optimization_ , 50(2):672–702, 2012.
  * Reddi et al. [2020] Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečnỳ, J., Kumar, S., and McMahan, H. B.  Adaptive federated optimization.  _arXiv preprint arXiv:2003.00295_ , 2020.
  * Ribero & Vikalo [2020] Ribero, M. and Vikalo, H.  Communication-efficient federated learning via optimal client sampling.  _arXiv preprint arXiv:2007.15197_ , 2020.
  * Rizk et al. [2020] Rizk, E., Vlaski, S., and Sayed, A. H.  Federated learning under importance sampling.  _arXiv preprint arXiv:2012.07383_ , 2020.
  * Shamir et al. [2014] Shamir, O., Srebro, N., and Zhang, T.  Communication-efficient distributed optimization using an approximate newton-type method.  In _International conference on machine learning_ , pp. 1000–1008. PMLR, 2014.
  * Singh et al. [2019] Singh, N., Data, D., George, J., and Diggavi, S.  SPARQ-SGD: Event-triggered and compressed communication in decentralized stochastic optimization.  _arXiv preprint arXiv:1910.14280_ , 2019.
  * Smith et al. [2017] Smith, V., Chiang, C.-K., Sanjabi, M., and Talwalkar, A. S.  Federated multi-task learning.  In _Advances in Neural Information Processing Systems_ , pp. 4424–4434, 2017.
  * Stich [2018] Stich, S. U.  Local SGD converges fast and communicates little.  _arXiv preprint arXiv:1805.09767_ , 2018.
  * Stich et al. [2018] Stich, S. U., Cordonnier, J.-B., and Jaggi, M.  Sparsified SGD with memory.  _arXiv preprint arXiv:1809.07599_ , 2018.
  * Stolyar [2005] Stolyar, A. L.  On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation.  _Operations research_ , 53(1):12–25, 2005.
  * Suresh et al. [2017] Suresh, A. T., Yu, F. X., Kumar, S., and McMahan, H. B.  Distributed mean estimation with limited communication.  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , pp. 3329–3337. JMLR. org, 2017.
  * Taheri et al. [2020] Taheri, H., Mokhtari, A., Hassani, H., and Pedarsani, R.  Quantized decentralized stochastic learning over directed graphs.  In _International Conference on Machine Learning_ , pp. 9324–9333. PMLR, 2020.
  * Tang et al. [2019] Tang, H., Lian, X., Zhang, T., and Liu, J.  Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression.  _arXiv preprint arXiv:1905.05957_ , 2019.
  * The TFF Authors [2019] The TFF Authors.  ”tensorflow federated,”, 2019.  URL https://www.tensorflow.org/federated.
  * Wang et al. [2021] Wang, J., Charles, Z., Xu, Z., Joshi, G., McMahan, H. B., Al-Shedivat, M., Andrew, G., Avestimehr, S., Daly, K., Data, D., et al.  A field guide to federated optimization.  _arXiv preprint arXiv:2107.06917_ , 2021.
  * Wu & He [2018] Wu, Y. and He, K.  Group normalization.  In _Proceedings of the European conference on computer vision (ECCV)_ , pp. 3–19, 2018.
  * Xia et al. [2020] Xia, W., Quek, T. Q. S., Guo, K., Wen, W., Yang, H. H., and Zhu, H.  Multi-armed bandit-based client scheduling for federated learning.  _IEEE Transactions on Wireless Communications_ , 19(11):7108–7123, 2020.  doi: 10.1109/TWC.2020.3008091.
  * Yang et al. [2018] Yang, T., Andrew, G., Eichner, H., Sun, H., Li, W., Kong, N., Ramage, D., and Beaufays, F.  Applied federated learning: Improving google keyboard query suggestions.  _arXiv preprint arXiv:1812.02903_ , 2018.
  * Zhang et al. [2013] Zhang, Y., Duchi, J. C., and Wainwright, M. J.  Communication-efficient algorithms for statistical optimization.  _The Journal of Machine Learning Research_ , 14(1):3321–3363, 2013.
  * Zhao & Zhang [2015] Zhao, P. and Zhang, T.  Stochastic optimization with importance sampling for regularized loss minimization.  In _international conference on machine learning_ , pp. 1–9. PMLR, 2015.

## Supplementary Material for “Federated Learning Under Time-Varying
Communication Constraints and Intermittent Client Availability”

This document is organized as follows. Section A introduces notation and
states useful definitions. Section B presents discussion of F3ast extensions
and problem variations. Section C provides proofs of theorems and lemmas that,
for the sake of brevity, have been omitted from the main document. Finally,
details of the experiments are given in Section D.

##  Appendix A Notation and Definitions

For clarity, frequently used symbols are summarized in Table 1 below.

Symbol | Definition
---|---
$\mathcal{U}$ | Set of all users
$N=|\mathcal{U}|$ | Total number of clients
$K_{t}$ | Number of clients sampled at round $t$
$T$ | Total number of rounds
$m_{t}$ | Number of available clients at time $t$
$(\mathbf{A}_{t})_{t}$ | availability stochastic process
$(\mathbf{C}_{t})_{t}$ | feasible client sets stochastic process
$S_{t}$ | Set of clients participating at round $t$
$\pi(\cdot)$ | Stationary distribution of availability and communication constraint process.
$\mathbf{r}$ | Client sampling rate
$\bm{f}^{\mathbf{r}}$ | Configuration-dependent client sampling policy
$\Delta^{t+1}$ | Pseudo-gradient for server optimizer: aggregates updates of participating clients at round $t$
$\overline{\mathbf{w}}^{t}$ | Global model at beginning of round $t$
$\mathbf{w}_{k}^{t+1}$ | Local model at the end of round $t$ at client $k$
$\mathbf{v}_{k}^{t+1}$ | Local update at the end of round $t$ at client $k$
$\overline{\mathbf{v}}^{t+1}=\mathbb{E}_{k\sim\mathcal{P}}\left[\mathbf{v}^{k}_{t+1}\right]=\sum_{k=1}^{N}p_{k}\mathbf{v}^{k}_{t+1}$ | Expected global update at the end of round $t$ under desired distripution $\mathcal{P}$
$\overline{\mathbf{z}}^{t+1}=\overline{\mathbf{w}}^{t}+\overline{\mathbf{v}}^{t+1}$ | Desired global model at the end of round $t$
Table 4: Frequently used symbols.

The generalized FedAvg assumes the server sends to clients in $S_{t}$ at time
$t$ an initial model $\overline{\mathbf{w}}^{t}$. For $t=0,...,T$; the clients
locally initialize
$\mathbf{w}_{k}^{(t,0)}\leftarrow\overline{\mathbf{w}}^{t-1}$ and take $E$
steps of SGD producing the sequence $(\mathbf{w}_{k}^{(t,i)})_{i=0}^{E}$.
Formally, let $\xi^{(t,i)}_{k}$ be the mini-batch for client $k$ at time $i$
in round $t$; for each client $k$, we can then define the local model
$\mathbf{w}^{(t,i)}_{k}$ and local update $\mathbf{v}_{k}^{t}$ as

$\mathbf{w}^{(t+1,i)}_{k}=\begin{cases}\overline{\mathbf{w}}^{t}&i=0\\\
\mathbf{w}^{(t+1,i-1)}_{k}-\eta_{t+1,i}\nabla
F_{k}(\mathbf{w}^{(t+1,i-1)}_{k},\xi^{(t+1,i)}_{k}),&i=1,...,E,\end{cases}\hskip
28.45274pt\mathbf{v}^{t+1}_{k}=\mathbf{w}_{k}^{(t+1,E)}-\overline{\mathbf{w}}^{t}.$

Here $\mathbf{w}_{k}^{(t,i)}$ tracks local models of client $k$ at round $t$
and iteration $i$, and $\mathbf{v}_{k}^{t}$ is the local update of client $k$
at the end of round $t$. Following distributed optimization standard
techniques [33, 22], we define the sequences

$\overline{\mathbf{v}}^{t+1}=\sum_{k=1}^{N}p_{k}\mathbf{v}^{t+1}_{k},\hskip
14.22636pt\Delta^{t+1}=\sum_{i\in
S_{t}}\frac{p_{i}}{r_{i}}\mathbf{v}_{k}^{t+1},\hskip
14.22636pt\overline{\mathbf{w}}^{t+1}=\overline{\mathbf{w}}^{t}+\Delta^{t+1},\hskip
14.22636pt\overline{\mathbf{z}}^{t+1}=\overline{\mathbf{w}}^{t}+\overline{\mathbf{v}}^{t+1}.$
(9)

##  Appendix B F3ast Extensions and Problem Variations.

##### Rapid mixing time.

Convergence rate of $\mathbf{r}(t)\to\mathbf{r}^{*}$ depends on the properties
of the Markov chain specified by the availability process. Concretely, we have
the following known theorem (see, e.g., [20] for a proof and details).

######  Theorem B.1.

[Convergence Theorem] Let $P$ be the transition matrix of a system
configuration satisfying 1 with stationary distribution $\pi$. Then there
exists a constant $\alpha\in(0,1)$ and $C>0$ such that

$\max_{C\in\mathcal{C}}\|P^{t}(C,\cdot)-\pi\|_{TV}\leq C\alpha^{t}.$

The above result shows that in practice one needs
$t_{0}\geq\frac{\log\epsilon}{\log\alpha}$ iterations to achieve a stationary
rate $\mathbf{r}$ up to an error $\epsilon$ to the stationary distribution.
Further, even if the rate is not constant during the early iterations, this
result demonstrates that after a burn-in the rate will stabilize and the
asymptotic convergence rate of $O(1/TE)$ will not be affected.

##### Working with clusters of clients.

Note that in some settings the number of clients is rather large and thus
tracking $p_{k}$ could be difficult. In such scenarios, it may be meaningful
to interpret $p_{k}$, $k=1,...,N$, as a partition of data over clusters of
clients, and the objective function in (1) as a weighted average over the
clusters. Tracking $p_{k}$ can then be cast as the estimation of time-varying
class sizes, which is feasible through efficient protocols [3].

##### More general sampling constraints.

Our model is quite general in that it can capture different client sampling
requirements, e.g., forcing the selection of as many clients as available up
to $M$ or other minimal sampling requirements on groups of users.

##### Societal impact.

Our work is motivated by model fairness in the sense that clients are
represented in the global model proportionally to their dataset size. Notice
that our framework adapts to different fairness metrics by replacing
distribution $\mathcal{P}$. This is out of the scope of our paper, and we
leave it for future research.

##### Fixed-policy F3ast .

For the sake of completeness, we here formalize as Algorithm 2 the procedure
that can determine the fixed policy analyzed in Section 3.2.

0: Server parameters: learning rate schedule
$\\{\eta_{(t,i)}\\}_{{}_{(t,i)}}$, the number of global rounds $T$, targeted
long-term rate $\mathbf{r}\in\mathcal{R}$ and static configuration dependent
sampling policy $\bm{f}^{\mathbf{r}}$ that achieves $\mathbf{r}$

0: Global model $\overline{\mathbf{w}}^{T}$

1: initialize $\overline{\mathbf{w}}^{0}$

2: for $t=1\to T$ do

3: $C_{t}\quad\leftarrow$ available collection of possible client subsets at
time $t$

4: Use policy $\bm{f^{r}}$ to select $S_{t}\in C_{t}$

5: for Clients $k\in S_{t}$, in parallel do

6:
$\mathbf{v}_{k}^{t+1}\leftarrow\textsc{ClientOpt}\left(\overline{\mathbf{w}}^{t},E\text{
steps},\\{\eta_{(t,i)}\\}_{{}_{(t,i)}}\right)$

7: end for

8: $\Delta^{t+1}=\sum_{k\in S_{t}}\frac{p_{k}}{r_{k}}\mathbf{v}^{t+1}_{k}$

9:
$\overline{\mathbf{w}}^{t+1}\leftarrow\textsc{ServerOpt}(\overline{\mathbf{w}}^{t},\Delta^{t+1})$

10: end for

Algorithm 2 Fixed-policy F3ast .

##  Appendix C Proofs

This section provides proofs of the lemmas and theorems omitted from the main
document.

###  C.1 Proof of Theorem 3.5

Proof of Theorem 3.5 follows standard optimization proofs [33, 22, 27]. Our
technical contribution comes from using a sampling policy with arbitrary
sampling rate $\mathbf{r}$, showing global update $\Delta^{t+1}$ is unbiased
(Lemma C.1), and computing the incurred variance of such sampling policy and
aggregation step (Lemma 3.4). This last step is of particular interest and
challenging due to the unknown system configuration, and the importance
sampling multiplicative terms.

######  Lemma C.1 (Unbiased update).

Suppose Assumption 1 holds. Let $\mathbf{r}\in\mathcal{R}$ be an achievable
sampling rate, and $\bm{f}^{r}$ be a state-dependent static policy achieving
rate $\mathbf{r}$. Fix $\overline{\mathbf{w}}^{t}\in\mathbb{R}^{p}$. Let
$(\mathbf{v}_{k}^{t+1})_{k=1}^{N}$ denote updates of clients starting from
model $\overline{\mathbf{w}}^{t}$. Let
$\overline{\mathbf{v}}^{t+1}=\sum_{k=1}^{N}p_{k}\mathbf{v}_{k}^{t+1}$, let $S$
be the client set selected by policy $\bm{f}^{r}$ at time $t$ and
$\Delta^{t+1}=\sum_{k\in S}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t+1}$. Then
$\mathbb{E}_{S}[\Delta^{t+1}]=\overline{\mathbf{v}}^{t+1}$.

###### Proof.

Recall that at any given time $t$ we pick $S\in C_{t}$ for some
$C_{t}\in\mathcal{C}$ according to $f^{r}_{C_{t}S}$. Using the definition of
$\pi$ and $\bm{f}^{r}$,

$\displaystyle\mathbb{E}_{S}\left[\Delta^{t+1}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\sum_{k\in
S}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t+1}\big{|}C\right]\right]=\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f^{r}_{CS}\sum_{k\in S}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t+1}$ (10)
$\displaystyle=\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f^{r}_{CS}\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t+1}\cdot\mathds{1}_{\\{k\in
S\\}},$ (11)

where the last step replaces the sum over $S$ by the sum over all clients but
adding the indicator function over $S$. Reorganizing,

$\displaystyle\mathbb{E}_{S}\left[\Delta^{t+1}\right]$
$\displaystyle=\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t+1}\left(\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f^{r}_{CS}\mathds{1}_{\\{k\in S\\}}\right).$ (12)

Here the term in parenthesis is, by definition,

$r_{k}=\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t+1}r_{k}=\sum_{k=1}^{N}p_{j}\mathbf{v}_{t+1}^{j}=\overline{\mathbf{v}}^{t+1}.$

∎

We proceed by introducing a key lemma derived in [22], characterizing
convergence for the full client participation case, and then utilize it to
prove Theorem 3.5.

Notice that the learning rate depends on round $t$, $t=0,...,T$ and epoch $i$
$i=1,...,E$.

######  Lemma C.2.

$\mathbb{E}[\|\overline{\mathbf{w}}^{t+1}-\mathbf{w}^{*}\|^{2}]\leq(1-\eta_{(t,E)}^{2}\mu)\mathbb{E}[\|\overline{\mathbf{w}}^{t}-\mathbf{w}^{*}\|^{2}]+\eta_{(t,E)}^{2}\text{Var}_{1},$
(13)

where

$\text{Var}_{1}=\sum^{N}_{k=1}p_{k}^{2}\sigma_{k}^{2}+6L\Gamma+8(E-1)^{2}G^{2}.$

###### Proof.

This result follows from the first part of Theorem 1 in [22], showing the
convergence of FedAvg with full client participation (i.e., no client
sampling). ∎

######  Theorem (Theorem 3.5).

Instate the settings of Lemma 3.4. Let $\mathbf{w}^{*}$ denote the solution to
the optimization problem (1), and $L,\mu=O(1)$. Define
$\gamma=\max\\{8\frac{L}{\mu},E\\}$, and assume learning rate
$\eta_{(t,i)}=\frac{2}{\mu(\gamma+(tE+i))}$. Then by setting ClientOpt to SGD
and
ServerOpt$(\overline{\mathbf{w}}^{t},\Delta^{t+1})=\overline{\mathbf{w}}^{t}+\Delta^{t+1}$,
the model $\overline{\mathbf{w}}^{T}$ produced by Algorithm 1 with policy
$\bm{f}^{\mathbf{r}}$ satisfies

$\mathbb{E}[F(\overline{\mathbf{w}}^{T})]-F^{*}=O\left(\frac{1}{TE+\gamma}\left(\|\overline{\mathbf{w}}^{1}-\mathbf{w}^{*}\|^{2}+\sum^{N}_{k=1}p_{k}^{2}\sigma_{k}^{2}+6\Gamma+8(E-1)^{2}G^{2}+\sigma_{T}^{2}(\bm{f}^{\mathbf{r}})\right)\right),$
(14)

where $\Gamma=F^{*}-\sum_{k=1}^{N}p_{k}F_{k}^{*}$ denotes the local-global
objective gap555Local-global objective gap quantifies data heterogeneity: for
i.i.d. data, $\Gamma\to 0$ as the number of samples grows, while a large
$\Gamma$ indicates a high degree of heterogeneity [22, 9]., $F^{*}$ and
$F_{k}^{*}$ are the minimum values of $F$ and $F_{k}$, respectively, and
$\sigma^{2}_{T}(\bm{f}^{\mathbf{r}})$ (Lemma 3.4) captures the variance
induced by client sampling.

##### A brief outline of the upcoming proof.

We start by expanding $\|\overline{\mathbf{w}}^{t+1}-\mathbf{w}^{*}\|^{2}$, a
term that measures the distance to the optimum, and bound it by the term
characterizing convergence of the full participation scheme [21] plus an
additional variance term emerging due to client sampling (computed in Lemma
C.5). We then invoke a standard inductive argument to express
$\|\overline{\mathbf{w}}^{t+1}-\mathbf{w}^{*}\|^{2}$ in terms of
$\|\overline{\mathbf{w}}^{1}-\mathbf{w}^{*}\|^{2}$ and, noting smoothness,
finally bound $\mathbb{E}[F(\mathbf{w}_{T})]-F^{*}$.

###### Proof.

$\|\overline{\mathbf{w}}^{t+1}-\mathbf{w}^{*}\|^{2}=\|\overline{\mathbf{w}}^{t+1}-\overline{\mathbf{z}}^{t+1}+\overline{\mathbf{z}}^{t+1}-\mathbf{w}^{*}\|^{2}=\underbrace{\|\overline{\mathbf{w}}^{t+1}-\overline{\mathbf{z}}^{t+1}\|^{2}}_{A_{1}}+\underbrace{\|\overline{\mathbf{z}}^{t+1}-\mathbf{w}^{*}\|^{2}}_{A_{2}}+\underbrace{2\langle\overline{\mathbf{w}}^{t+1}-\overline{\mathbf{z}}^{t+1},\overline{\mathbf{z}}^{t+1}-\mathbf{w}^{*}\rangle}_{A_{3}}.$
(15)

Based on Lemma C.1, we know $\Delta^{t+1}$ is unbiased, thus
$\mathbb{E}\left[\Delta^{t+1}\right]=\overline{\mathbf{v}}^{t+1}$.

We use this fact to prove that $A_{3}=0$ as follows:

$\mathbb{E}\left[\langle\overline{\mathbf{w}}^{t+1}-\overline{\mathbf{z}}^{t+1},\overline{\mathbf{z}}^{t+1}-\mathbf{w}^{*}\rangle\right]=\mathbb{E}\left[\langle\overline{\mathbf{w}}^{t}+\Delta^{t+1}-\overline{\mathbf{w}}^{t}-\overline{\mathbf{v}}^{t+1},\overline{\mathbf{z}}^{t+1}-\mathbf{w}^{*}\rangle\right]=\mathbb{E}\left[\langle\Delta^{t+1}-\overline{\mathbf{v}}^{t+1},\overline{\mathbf{z}}^{t+1}-\mathbf{w}^{*}\rangle\right]=0.$

Now, $A_{1}$ can be bounded using Lemma 3.4, since
$\|\overline{\mathbf{w}}^{t+1}-\overline{\mathbf{z}}^{t+1}\|^{2}=\|(\overline{\mathbf{w}}^{t}+\Delta^{t+1})-(\overline{\mathbf{w}}^{t}+\overline{\mathbf{v}}^{t+1})\|^{2}=\|\Delta^{t+1}-\overline{\mathbf{v}}^{t+1}\|^{2}$.

Define

$\text{Var}_{1}=\sum^{N}_{k=1}p_{k}^{2}\sigma_{k}^{2}+6\Gamma+8(E-1)^{2}G^{2},\quad\text{Var}_{2}:=\sigma^{2}_{t}(\bm{f}^{\mathbf{r}})=\frac{1}{\eta_{(t,E)}^{2}}\mathbb{E}\left[||\Delta^{t+1}-\overline{\mathbf{v}}^{t+1}\|^{2}\right].$

Then by replacing Lemmas C.2 and C.5 in Equation 15 we have that

$\mathbb{E}\|\overline{\mathbf{w}}^{t+1}-\mathbf{w}^{*}\|^{2}\leq(1-\eta_{(t,E)}\mu)\mathbb{E}\|\overline{\mathbf{w}}^{t}-\mathbf{w}^{*}\|^{2}+\eta_{(t,E)}^{2}(\text{Var}_{1}+\text{Var}_{2}).$

Thanks to Lemma C.1, we find a similar expression to the one in [22], but with
different constants coming from different client sampling variance in Lemma
3.4. The rest of the proof then follows standard techniques, e.g., see [22].
We repeat those steps for the sake of completeness.

Let $\beta>\frac{1}{\mu}$, $\gamma>0$, and define
$\eta_{(t,i)}=\frac{\beta}{(t-1)E+i+\gamma}$ such that
$\eta_{(1,1)}<\min\\{\frac{1}{\mu},\frac{1}{4L}\\}$, and $\eta_{(t,1)}\leq
2\eta_{(t,E)}$.

As a standard technique, we show by induction in $t$ that
$\mathbb{E}\|\overline{\mathbf{w}}^{t}-\mathbf{w}^{*}\|^{2}\leq\frac{v}{\gamma+tE}$,
where

$v=\max\\{\frac{\beta^{2}(\text{Var}_{1}+\text{Var}_{2})}{\beta\mu-1},(\gamma+1)\|\overline{\mathbf{w}}^{1}-\mathbf{w}^{*}\|^{2}\\}.$

This holds for $t=1$ trivially, from the definition of $v$. Now assume the
claim holds for $t$; starting from the above equation, we have that

$\displaystyle\mathbb{E}\|\overline{\mathbf{w}}^{t+1}-\mathbf{w}^{*}\|^{2}$
$\displaystyle\leq(1-\eta_{(t,E)}\mu)\mathbb{E}\|\overline{\mathbf{w}}^{t}-\mathbf{w}^{*}\|^{2}+\eta_{(t,E)}^{2}(\text{Var}_{1}+\text{Var}_{2})$
$\displaystyle\leq\left(1-\frac{\beta\mu}{tE+\gamma}\right)\frac{v}{tE+\gamma}+\frac{\beta^{2}(\text{Var}_{1}+\text{Var}_{2})}{(tE+\gamma)^{2}}$
(16)
$\displaystyle=\frac{tE+\gamma-E}{(tE+\gamma)^{2}}v+\left[\frac{\beta^{2}(\text{Var}_{1}+\text{Var}_{2})}{(tE+\gamma)^{2}}-\frac{\beta\mu-E}{(tE+\gamma)^{2}}v\right]$
(17) $\displaystyle\leq\frac{v}{tE+\gamma+E}=\frac{v}{(t+1)E+\gamma}.$ (18)

where Equation 16 follows by induction step and definition of $\eta_{(t,E)}$,
Equation 17 from adding and substracting $\frac{Ev}{(tE+\gamma)^{2}}$, and the
last step by noticing that

$\frac{tE+\gamma-E}{(tE+\gamma)^{2}}=\frac{(tE+\gamma-E)(tE+\gamma+E)}{(tE+\gamma)^{2}(tE+\gamma+E)}\leq\frac{1}{tE+\gamma+E}.$

Finally, by smoothness of $F$,

$\mathbb{E}[F(\overline{\mathbf{w}}^{t})]-F^{*}\leq\frac{L}{2}\mathbb{E}\|\overline{\mathbf{w}}^{t}-\mathbf{w}^{*}\|^{2}\leq\frac{v}{\gamma+tE}.$
(19)

Setting $\beta=\frac{2}{\mu}$, $\kappa=\frac{L}{\mu}$ and
$\gamma=\max\\{8\kappa,E\\}-1$, and using Lemma C.5 to compute
$\text{Var}_{2}$, we obtain the desired result. ∎

###  C.2 Proof of Lemma 3.4: Bounded client sampling variance

For clarity of the proof of Lemma 3.4, we first introduce the following lemma
on the inner product of local models.

######  Lemma C.3.

At round $t$ for any pair of clients $i$ and $j$,

$\mathbb{E}\left[\langle\mathbf{v}_{i}^{t},\mathbf{v}_{j}^{t}\rangle\right]\leq
4E^{2}G^{2}\eta_{(t,E)}^{2},$ (20)

where the expectation is taken over the samples in local SGD steps.

###### Proof.

Recall that $\mathbf{v}_{i}^{t}$ represents the user $i$’s update after
training locally for $E$ epochs starting with model
$\overline{\mathbf{w}}^{t-1}$. Then,

$\|\mathbf{v}_{i}^{t}\|^{2}=\|\mathbf{w}_{i}^{t,E}-\mathbf{w}_{i}^{t,0}\|^{2}=\|\sum_{\ell=0}^{E-1}\eta_{(t,\ell)}\nabla
f_{k}(\mathbf{w}_{i}^{t,\ell},\xi_{\ell})\|^{2}\leq
E\sum_{\ell=0}^{E-1}\eta^{2}_{t,0}\|\nabla
f_{k}(\mathbf{w}_{i}^{t,\ell})\|^{2}\leq 4\eta_{(t,E)}^{2}E^{2}G^{2},$

where we used the Jensen inequality and the fact that $\eta_{(t,\ell)}$ is
decreasing (i.e., $\eta_{(t,0)}\leq 2\eta_{(t,\ell)}$ for $\ell\leq E$). Now,
since
$\langle\mathbf{v}_{i}^{t},\mathbf{v}_{j}^{t}\rangle\leq\max_{k}\|\mathbf{v}_{k}^{t}\|^{2}$,
the result follows.

∎

Next, we define the random vector $X^{\mathbf{r}}\in\\{0,1\\}^{N}$ that
indicates which clients are selected, and specify its moments.

######  Lemma C.4.

Let $X^{\mathbf{r}}\in\\{0,1\\}^{N}$ be such that its $i^{th}$ component takes
on value $X^{\mathbf{r}}_{i}=1$ if client $i$ is selected at time $t$, and 0
otherwise. Let $\Sigma$ denote the covariance matrix of $X^{\mathbf{r}}$. Then
$\mathbb{E}\left[X\right]=\mathbf{r}$ and $\text{Var}(X_{i})=r_{i}(1-r_{i})$.

###### Proof.

This follows trivially from the observation that $X_{i}$ is a Bernoulli random
variable with parameter $r_{i}$. ∎

######  Lemma C.5.

Let $\mathbf{r}\in\mathcal{R}^{+}$ be an achievable sampling rate,
$\bm{f}^{\mathbf{r}}$ denote a static configuration-dependent sampling policy
achieving $\mathbf{r}$, and $X^{\mathbf{r}}$ the corresponding selection
random vector with covariance $\mathbf{\Sigma}$. Then for $t=1,...,T$,

$\sigma_{t}^{2}(\bm{f}^{\mathbf{r}}):=\frac{1}{\eta_{(t,E)}^{2}}\mathbb{E}\left[\|\Delta^{t}-\overline{\mathbf{v}}^{t}\|^{2}\right]=\frac{1}{\eta_{(t,E)}^{2}}\mathbf{Tr}(\mathbf{Y}_{t}\mathbf{Y}_{t}^{T}\mathbf{\Sigma}),$
(21)

where vector $\frac{p_{k}}{r_{k}}\mathbf{v}^{t}_{k}$ is the $k^{th}$ row of
matrix $\mathbf{Y}_{t}\in\mathbb{R}^{N\times p}$.

###### Proof.

Below $\|\cdot\|$ denotes the $\ell_{2}-$norm. Using the variance formula and
that $\mathbb{E}\left[\Delta^{t}\right]=\overline{\mathbf{v}}^{t}$ by Lemma
C.1,

$\mathbb{E}_{S}\left[\|\Delta^{t}-\overline{\mathbf{v}}^{t}\|^{2}\right]=\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]-\|\overline{\mathbf{v}}\|^{2}.$
(22)

Let us focus on the first term:

$\displaystyle\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]$
$\displaystyle=\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in C}f_{CS}\|\sum_{k\in
S}\frac{p_{k}}{r_{k}}\mathbf{v}_{k}^{t}\|^{2}=\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f_{CS}\sum_{i,j\in
S}\frac{p_{i}p_{j}}{r_{i}r_{j}}\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle$
$\displaystyle=\sum_{i,j=1}^{N}\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f_{CS}\frac{p_{i}p_{j}}{r_{i}r_{j}}\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle\mathds{1}_{i\in
S}\mathds{1}_{j\in S}=\sum_{i,j=1}^{N}\sum_{C\in\mathcal{C}}\pi(C)\sum_{S\in
C}f_{CS}\frac{p_{i}p_{j}}{r_{i}r_{j}}\langle\mathbf{v}_{i},\mathbf{v}_{j}\rangle
X_{i}X_{j}.$

From the defition of $\mathbf{Y}_{t}$ and by reorganizing,

$\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]=\mathbb{E}\left[X^{T}\mathbf{Y}_{t}\mathbf{Y}_{t}^{T}X\right].$

Introducing $\mathbf{B}=\mathbf{Y}_{t}\mathbf{Y}_{t}^{T}$,

$\displaystyle\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{i,j}b_{ij}X_{i}X_{j}\right]=\sum_{i,j}b_{ij}\mathbb{E}\left[X_{i}X_{j}\right]$
$\displaystyle=\sum_{i,j}b_{ij}(\mathbf{\Sigma}_{ij}+r_{i}r_{j})$ (23)
$\displaystyle=\sum_{i}[\mathbf{B\Sigma}]_{ii}+\mathbf{r}^{T}\mathbf{B}\mathbf{r}$
$\displaystyle=\mathbf{Tr}(\mathbf{Y_{t}Y_{t}^{T}\Sigma})+\|\overline{\mathbf{v}}^{t}\|^{2},$
(24)

where Eq. 23 follows by the covariance formula and Eq. 24 follows due to
cancellation in denominator of $\mathbf{B}=\mathbf{Y}_{t}\mathbf{Y}_{t}^{T}$.
After combining this with Equation 22, the term
$\|\overline{\mathbf{v}}^{t}\|^{2}$ cancels and we obtain the desired result.
∎

######  Lemma (Lemma 3.4).

Suppose Assumptions 1-4 hold. Let $\mathbf{r}\in\mathcal{R}$ be an achievable
sampling rate under the system configuration determined by distribution $\pi$,
and $\bm{f}^{\mathbf{r}}$ denote a static configuration-dependent sampling
policy achieving $\mathbf{r}$.

Define the client sampling variance
$\sigma^{2}_{t}(\bm{f}^{\mathbf{r}}):=\frac{1}{\eta_{t}^{2}}\mathbb{E}_{S_{t}}\left[\|\Delta^{t}-\overline{\mathbf{v}}^{t}\|^{2}\right]$
where $\overline{\mathbf{v}}^{t}=\sum_{k=1}^{N}p_{k}\mathbf{v}^{k}_{t}$ is the
update at time $t$ with full client participation. Then

$\sigma_{t}^{2}(\bm{f}^{\mathbf{r}})\leq
4E^{2}G^{2}(\sum_{k=1}^{N}\frac{p_{k}}{r_{k}}-1).$ (25)

Furthermore, if client availabilities are uncorrelated or negatively
correlated, then there exists a policy $\bm{f}^{r}$ such that

$\sigma_{t}^{2}(\bm{f}^{\mathbf{r}})\leq
4E^{2}G^{2}\left(\sum_{k=1}^{N}\frac{p_{k}^{2}}{r_{k}}+\sum_{k=1}^{N}p_{k}^{2}\right).$
(26)

###### Proof.

For the first part, taking expectation over the independent local SGD sampling
and over the random set of clients $S$,

$\displaystyle\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\|\sum_{k\in
S}\frac{p_{k}}{r_{k}}\mathbf{v}^{t}_{k}]\|^{2}\right]=\mathbb{E}\left[\sum_{i,j\in
S}\frac{p_{i}p_{j}}{r_{i}r_{j}}\langle\mathbf{v}_{i}^{t},\mathbf{v}_{j}^{t}\rangle\right]=\sum_{i,j=1}^{N}\frac{p_{i}pj}{r_{i}r_{j}}\mathbb{E}\left[\langle\mathbf{v}_{i}^{t},\mathbf{v}_{j}^{t}\rangle\right]P(i,j\in
S)$ $\displaystyle\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\left(\sum_{i=1}^{N}\frac{p_{i}^{2}}{r_{i}^{2}}P(i\in
S)+\sum_{i=1}^{N}\sum_{j=1,j\neq i}^{N}\frac{p_{i}p_{j}}{r_{i}r_{j}}P(i,j\in
S)\right).$

Given that $P(i,j\in S)\leq P(i\in S)$ and $P(i\in S)=r_{i}$,

$\displaystyle\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]$ $\displaystyle\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\left(\sum_{i=1}^{N}\frac{p_{i}^{2}}{r_{i}}+\sum_{i=1}^{N}\sum_{j=1,j\neq
i}^{N}\frac{p_{i}p_{j}}{r_{i}r_{j}}P(j\in S)\right)$ $\displaystyle\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\left(\sum_{i=1}^{N}\frac{p_{i}^{2}}{r_{i}}+\sum_{i=1}^{N}\frac{p_{i}}{r_{i}}\sum_{j=1,j\neq
i}^{N}p_{j}\right)$ $\displaystyle\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\left(\sum_{i=1}^{N}\frac{p_{i}^{2}}{r_{i}}+\sum_{i=1}^{N}\frac{p_{i}}{r_{i}}(1-p_{i})\right)$
$\displaystyle\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\sum_{i=1}^{N}\frac{p_{i}}{r_{i}}.$

Therefore,

$\mathbb{E}\left[\|\Delta^{t}-\overline{\mathbf{v}}^{t}\|^{2}\right]=\mathbb{E}\left[\|\Delta^{t}\|^{2}\right]-\|\overline{\mathbf{v}}^{t}\|^{2}\\\
\leq 4E^{2}G^{2}\eta_{(t,E)}^{2}(\sum_{i=1}^{N}\frac{p_{i}}{r_{i}}-1),$

and the result follows.

For the second part of the lemma, consider a policy $\bm{f}$ with rate
$\mathbf{r}$ that at time $t$ selects $S$ as

$S_{t}\in\arg\max_{S\in C_{t}}-\nabla H(\mathbf{r})\cdot\mathds{1}_{S}.$

Let $u_{k}$ denote the $k$-th largest utility value, where the individual
utilities are defined by vector $-\nabla H(\mathbf{r})$. W.l.o.g. assume
$u_{i}<u_{j}$ if $i<j$, and let $A_{k}$ be the (random) number of users $i$
with the utility less than $u_{k}$. Let $K$ be a bound on the set size $S$.
Let $i,j$ be two users, $i<j$; then $u_{i}<u_{j}$. Now, since $i,j$ are
uncorrelated or negatively correlated, $P(i,j\text{ are available})\leq
P(j\text{ is available})P(i\text{ is available})$. Therefore,

$P(j\in S|i\in S)=P(j\text{ is available})P(A_{k}-1<K)\leq P(j\text{ is
available})P(A_{k}<K)=P(j\in S).$

Note that from the definition of conditional probability, it follows that the
sampling is also uncorrelated since

$P(i,j\in S)=P(i\in S)P(j\in S|i\in S)=P(i\in S)P(j\in
S)=\mathbb{E}\left[X_{i}\right]\mathbb{E}\left[X_{j}\right]=r_{i}r_{j}.$

Therefore, we have that
$\Sigma_{ij}=\mathbb{E}\left[X_{i}X_{j}\right]-\mathbb{E}\left[X_{i}\right]\mathbb{E}\left[X_{j}\right]=P(i,j\in
S)-r_{i}r_{j}\leq 0$. From Eq. 23, we have that

$\mathbf{Tr}(\mathbf{YY^{T}\Sigma})=\sum_{i,j}\frac{p_{i}p_{j}}{r_{i}r_{j}}\langle\mathbf{v}_{i}^{t},\mathbf{v}_{j}^{t}\rangle\mathbf{\Sigma}_{ij};$

since $\mathbf{\Sigma}_{ij}\leq 0$ for $i\neq j$,

$\displaystyle\mathbf{Tr}(\mathbf{YY^{T}\Sigma})$
$\displaystyle=\sum_{i,j}\frac{p_{i}p_{j}}{r_{i}r_{j}}\langle\mathbf{v}_{i}^{t},\mathbf{v}_{j}^{t}\rangle\mathbf{\Sigma}_{ij}\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\sum_{i}\frac{p_{i}^{2}}{r^{2}_{i}}\Sigma_{ii}+\sum_{i\neq
j}\frac{p_{i}p_{j}}{r_{i}r_{j}}\Sigma_{ij}$ $\displaystyle\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\sum_{i}\frac{p_{i}^{2}}{r^{2}_{i}}(r_{i}(1-r_{i}))\leq
4E^{2}G^{2}\eta_{(t,E)}^{2}\left(\sum_{i}\frac{p_{i}^{2}}{r_{i}}+\sum_{i}p_{i}^{2}\right),$

where the first inequality follows from Lemma C.3 and breaking the sum on
diagonal and non diagonal terms. The second inequality follows by dropping
negative terms and replacing the variance value $\Sigma_{ii}=r_{i}(1-r_{i})$
for $X_{i}$ (Lemma C.4), while the last one follows simply by expanding the
previous term.

∎

###  C.3 Proof of Theorem 3.3

######  Theorem (Theorem 3.3).

Let $\mathbf{r}^{\beta}(t)$ be defined by Algorithm 1, following equations (4)
and (5). Let $V\subset\mathbb{R}_{+}^{N}$ be a bounded set, $\epsilon>0$, and
let $\mathbf{r}^{*}$ denote the minimizer of the variance function
$H(\mathbf{r})=\sum_{k=1}^{n}\frac{p_{k}^{2}}{r_{k}}$ over $\mathcal{R}$. Then
for $T>0$, depending on $\epsilon$ and $V$,

$\lim_{\beta\downarrow 0}\quad\sup_{\mathbf{r}^{\beta}(0)\in
V,t>T/\beta}P[\|r^{\beta}(t)-r^{*}\|>\epsilon]=0.$

###### Proof.

Our proof follows the stochastic approximation analysis in [35] that
establishes an attraction property for Fluid Sample Paths (FSPs), which are
limiting trajectories of the generalized versions of the processes considered
in our manuscript. The idea behind the proof is that as $t$ grows, we can
study the limiting trajectories (i.e., FSPs) $x=(x(t),t\geq 0)$ of the process
$r(t/\beta)$. Since $-H(\mathbf{r})$ is a convex function, it follows from
Theorem 4 in [35] that for an arbitrary initial state $x(0)$,
$x(t)\to\mathbf{r}^{*}$ as $t\to\infty$. More concretely, from Theorem 3 in
[35] it follows that as $\beta\downarrow 0$, a limit of sequence
$\\{\mathbf{r}^{\beta}\\}$ considered in Section 3 of our paper is a process
with sample paths being FSPs $x$ with probability 1.

Assume $V\subset[0,a]^{N}$ such that $a>\bar{\mu}$, where
$\bar{\mu}=\max_{C\in\mathcal{C},S\in S}\frac{1}{|S|}$. Let $\epsilon>0$ and
$\delta>0$. By the above result on FSPs (i.e., by Theorem 4 in [35]), we can
find $T$ large enough such that $\|x(t)-\mathbf{r}^{*}\|\leq\epsilon$
uniformly for $t$ in the interval $[T,T+\delta]$. Combining this result with
the continuous mapping theorem [4], we obtain

$\lim_{\beta\to 0}\sup_{r^{\beta}\in
V}P(\sup_{t\in[T,T+\delta]}\|x(t)-\mathbf{r}^{*}\|>\epsilon)=0.$

Also, notice that for all $t$,
$r^{\beta}_{i}(t)\leq\max\\{\bar{\mu},\mathbf{r}^{\beta}_{i}(0)\\}$ element-
wise, where $\bar{\mu}=\max_{C\in\mathcal{C},S\in S}\frac{1}{|S|}$ by
construction. Then for any $\tau\geq 0$ we can re-start the process, implying

$\lim_{\beta\to 0}\sup_{r^{\beta}\in V}\sup_{\tau\geq
0}P(\sup_{t\in[\tau+T,\tau+T+\delta]}\|x(t)-\mathbf{r}^{*}\|>\epsilon)=0$

and thus establishing the desired result. ∎

##  Appendix D Experiments details

##### Hyperparameter tuning.

We set the learning rate on Shakespeare and CIFAR100 according to the optimal
values found in [27]. For the synthetic dataset we use the learning rate tuned
in [21], $\eta=0.01$. For Shakespeare we use mini-batches of size 4, and mini-
batches of size 20 for the remaining datasets. Following literature, in all
the experiments we use $\beta=O(1/T)=0.001$.

##### Machines.

We ran our experiments on AMD Vega 20 (ROCm) cards. One rounds of training in
Fig. 1 require 8 GPU seconds for CIFAR100, 67 GPU seconds for Shakespeare, and
0.57 GPU seconds for Synthetic(1,1).

###  D.1 Datasets

##### Synthetic dataset.

We generate this data by taking $10^{4}$ samples
$X_{i}\in\mathbb{R}^{100}\sim\mathcal{N}(0,I_{100})$. Moreover, we generate
$\beta\sim\mathcal{N}(0,I_{100})$ and, finally, set labels
$y_{i}=round(X_{i}^{T}\beta)$. The samples are split evenly among $100$
clients.

##### Skakespeare.

Each client’s dataset is restricted to have at most 128 sentences, and is
split into training and validation sets. Following the previous work with this
dataset [27], we use a build vocabulary with 86 characters contained in the
text, and 4 characters representing padding, out-of-vocabulary, beginning, and
end of line tokens. We use padding and truncation to enforce 20 word
sentences, and represent them with index sequences corresponding to the
vocabulary words, out of vocabulary words, beginning and end of sentences.

###  D.2 Federated Datasets Details

Number of clients and total number of samples is summarized in Table 5.

Table 5: Datasets Dataset | Users | Samples
---|---|---
Synthetic | 100 | 60 K
CIFAR100 | 500 | 50 K
Shakespeare | 715 | 16 K

###  D.3 Models

We train a recursive neural network for the next character prediction that
first embeds characters into an 8-dimensional space, followed by 2 LSTMs and
finally a dense layer. The architecture is presented in Table 6.

ResNet-18 architecture can be found in [12], where we replace batch
normalization by group normalization [41] as in [27].

Table 6:  Shakespeare next character prediction model architecture Layer | Output |  | # Trainable
---
parameters
Activation
Input | 80 |  |
Embedding | (80,8) | 720 |
LSTM | (80,256) | 271360 |
LSTM | (80,256) | 525312 |
Dense | (80,90) | 23130 | Softmax
Total |  | 4,050,748 |

###  D.4 Availability models

For the Home-devices model $t_{k}\sim lognormal(0,0.5)$, while for the
Smartphones $t_{k}\sim lognormal(0,0.25)$. The sine wave is defined by
$f(t)=0.4\sin(t)+0.5$ and we sample at times $t=\frac{2\pi j}{24}$ for
$j=1,...,24$.

###  D.5 Loss and accuracy values under independent availability model.

Figure 4 shows that F3ast exhibits a much more stable convergence for all data
sets and achieves a smaller loss value. Figure 3 also proves F3ast is more
resilient: it maintains similar performance across 3 independent runs.

Figure 3: Test per-sample accuracy of different algorithms over all data sets
(averaged over three runs). In all cases F3ast converges to a model with
higher accuracy. Furthermore, F3ast stabilizes while FedAvg and PoC are not
able to adapt to the time-varying environment. F3ast also provides the
smallest variance across independent runs.

###  D.6 Varying the communication constraint.

Figure 5 shows the test accuracy during training for the three algorithms
(F3ast , FedAvg and PoC ). We observe that F3ast achieves equal or higher
performance than competing methods across all communication levels. Note that
PoC stagnates at a similar accuracy in all cases; we believe this is due to
the inherent bias in the algorithm due to top-k loss based sampling, as
reported by the authors. It is possible that certain groups of clients are
never selected by this policy. It is interesting to note that the gap between
F3ast and two baselines widens as the number of selected clients increases.
Indeed, as the number of users grow, a configuration-dependent policy becomes
much harder to facilitate since the number of possible selections grows
exponentially with $K$. Nevertheless, the greedy nature of F3ast allows it to
keep selecting the set of users that maximizes marginal utility and achieves a
balanced sampling rate under the availability model. The other two policies,
however, do not track previous selections of users and thus may end up over-
selecting available users rather than exploring the full pool of devices.

Figure 4: Test per-sample loss of different algorithms over all data sets. In
all cases F3ast converges to a model with smaller objective value.
Furthermore, F3ast stabilizes while FedAvg and PoC are not able to adapt to
the time-varying environment. Figure 5: Impact of varying communication level
$K$ in the Synthetic(1,1) dataset experiments. As the number of sampled
clients increases, the gap between F3ast and competing methods widens.

###  D.7 Additional user/sample results and accuracy visualization.

Figure 6 presents average user and sample loss over CIFAR100 and Shakespeare
for all availability models. User average first computes the local test metric
and then averages over users, while sample metrics computes the metric
averaged over all test samples. Typically in deep learning test sample
accuracy reflects better performance. However, in federated learning uniform
performance across users is desired even if some users have very few
datapoints. Below we show that claims in Section 4 are also valid for user-
averaged metrics. Notice that sample accuracy and user accuracy coincide in
CIFAR100 given that data is split in a balanced way among clients so we omit
these results.

(a) Test accuracy

(b) Train loss

Figure 6: Accuracy and relative gain of F3ast over FedAvg and FedAdam for different availability models (rows) and datasets (columns). F3ast consistently improves both the unweighted and weighted accuracy. Table 7: User accuracy of all methods, and relative improvements of F3ast over FedAvg and F3ast \+ Adam over FedAdam , for different availability models (columns) on Shakespeare (500 rounds). Availability model | Always | Scarce | HomeDevice | Uneven | SmartPhones
---|---|---|---|---|---
Routine |  |  |  |  |
FedAvg | 0.529 | 0.534 | 0.512 | 0.525 | 0.526
F3ast |  0.556 (+5%) |  0.542 (+1%) |  0.556 (+8%) | 0.543 (+3%) |  0.556 (+5%)
FedAdam | 0.524 | 0.529 | 0.509 | 0.544 | 0.510
F3ast +Adam | 0.541 (+3%) | 0.541 (+2%) | 0.552 (+8%) |  0.544 (0%) | 0.540 (+5%)
PoC | 0.541 | 0.543 | 0.486 | 0.543 | 0.524
Table 8: User loss of all methods, and relative improvements of F3ast over FedAvg and F3ast \+ Adam over FedAdam , for different availability models (columns) on Shakespeare (500 rounds). Availability model | Always | Scarce | HomeDevice | Uneven | SmartPhones
---|---|---|---|---|---
Routine |  |  |  |  |
FedAvg | 1.02 | 0.95 | 1.12 | 0.97 | 1.00
F3ast |  0.90 (-11%) |  0.93 (-1%) |  0.91 (-18%) | 0.93 (-3%) |  0.90 (-9%)
FedAdam | 1.05 | 1.02 | 1.16 | 0.93 | 1.12
F3ast +Adam | 0.97 (-8%) | 0.98 (-3%) |  0.91 (-20%) |  0.92 (-1%) | 0.97 (-13%)
PoC | 0.93 | 0.93 | 1.43 | 0.93 | 1.02

###  D.8 Varying heterogeneity in the synthetic dataset.

Table 9: Test accuracy on the synthetic($\alpha,\alpha$) dataset under the Smartphones availability model.  | $\alpha=0$ | $\alpha=0.5$ | $\alpha=1$
---|---|---|---
FedAvg | 0.72 | 0.72 | 0.68
F3ast | 0.83 | 0.75 | 0.76

In our paper we consider heterogeneity of both data and clients’ availability.
Data heterogeneity arises from unbalanced amounts of data generated from
heterogeneous distributions. F3ast aims to address data heterogeneity by
selecting clients whose participation is far from the desired rate. Table 9
shows that for all values of the synthetic data heterogeneity parameter
$\alpha$ (Smartphones setting), F3ast is more accurate than FedAvg .


Base.zero(::Type{ConfigEnumerator{N}}) where {N} =
ConfigEnumerator{N}(BitVector[])

Base.one(::Type{ConfigEnumerator{N}}) where {N} =
ConfigEnumerator{N}([falses(N)])

# the algebra sampling one of the configurations

struct ConfigSampler{N}

data::BitVector

end

function Base.:+(x::ConfigSampler{N}, y::ConfigSampler{N}) where {N} # biased
sampling: return `x`

return x # randomly pick one

end

function Base.:*(x::ConfigSampler{L}, y::ConfigSampler{L}) where {L}

ConfigSampler{L}(x.data .| y.data)

end

Base.zero(::Type{ConfigSampler{N}}) where {N} = ConfigSampler{N}(trues(N))

Base.one(::Type{ConfigSampler{N}}) where {N} = ConfigSampler{N}(falses(N))

# enumerate all configurations if `all` is true; compute one otherwise.

# a configuration is stored in the data type of `StaticBitVector`; it uses
integers to represent bit strings.

# `ConfigTropical` is defined in `TropicalNumbers`. It has two fields:
tropical number `n` and optimal configuration `config`.

# `CountingTropical{T,<:ConfigEnumerator}` stores configurations instead of
simple counting.

function mis_config(code; all=false)

# map a vertex label to an integer

vertex_index = Dict([s=>i for (i, s) in enumerate(uniquelabels(code))])

N = length(vertex_index) # number of vertices

xs = map(getixsv(code)) do ix

T = all ? CountingTropical{Float64, ConfigEnumerator{N}} :
CountingTropical{Float64, ConfigSampler{N}}

if length(ix) == 2

return [one(T) one(T); one(T) zero(T)]

else

s = falses(N)

s[vertex_index[ix[1]]] = true # one hot vector

if all

[one(T), T(1.0, ConfigEnumerator{N}([s]))]

else

[one(T), T(1.0, ConfigSampler{N}(s))]

end

end

end

return code(xs...)

end

println("one of the optimal configurations is $(mis_config(optimized_code;
all=false)[].c.data)")

# direct enumeration of configurations can be very slow; please check the
bounding version in our Github repo.

println("all optimal configurations are $(mis_config(optimized_code;
all=true)[].c)")