# Emulating Full Client Participation: A Long-Term Client Selection Strategy
for Federated Learning

Qingming Li, Juzheng Miao, Puning Zhao, Li Zhou, Shouling Ji, Bowen Zhou,
Furui Liu This work was supported by National Key R&D Program of China
(2023ZD0121400, 2023ZD0121401). _(Corresponding author: Furui Liu)_ Qingming
Li, Shouling Ji are with the College of Computer Science and Technology at
Zhejiang University, Hangzhou, Zhejiang, 310027, China. E-mail: {liqm,
<EMAIL_ADDRESS>Miao is with the Department of Computer Science and
Engineering, The Chinese University of Hong Kong, Hong Kong, China. E-mail:
<EMAIL_ADDRESS>Zhao, Li Zhou, Furui Liu are with Zhejiang
Lab, Hangzhou, Zhejiang, 311000, China. E-mail: {pnzhao, zhou.li,
<EMAIL_ADDRESS>Zhou is with the Department of Electronic
Engineering, Tsinghua University, Beijing, 100084, China. E-mail:
<EMAIL_ADDRESS>
###### Abstract

Client selection significantly affects the system convergence efficiency and
is a crucial problem in federated learning. Existing methods often select
clients by evaluating each round individually and overlook the necessity for
long-term optimization, resulting in suboptimal performance and potential
fairness issues. In this study, we propose a novel client selection strategy
designed to emulate the performance achieved with full client participation.
In a single round, we select clients by minimizing the gradient-space
estimation error between the client subset and the full client set. In multi-
round selection, we introduce a novel individual fairness constraint, which
ensures that clients with similar data distributions have similar frequencies
of being selected. This constraint guides the client selection process from a
long-term perspective. We employ Lyapunov optimization and submodular
functions to efficiently identify the optimal subset of clients, and provide a
theoretical analysis of the convergence ability. Experiments demonstrate that
the proposed strategy significantly improves both accuracy and fairness
compared to previous methods while also exhibiting efficiency by incurring
minimal time overhead.

###### Index Terms:

Federated Learning, Client Selection, Individual Fairness, Coreset Selection,
Lyapunov Optimization

##  I Introduction

Federated learning (FL) facilitates collaborative model training without the
necessity of sharing local data [1, 2], and is widely used in various domains
[3, 4, 5]. In FL, model parameters or gradient updates are frequently
exchanged between the central server and participating clients, leading to
substantial communication overhead. To address the challenge posed by the
limited bandwidth, a common approach is to select a subset of clients for
local training, which reduces the communication costs compared with involving
all clients [6, 7]. However, in heterogeneous scenarios, different selection
strategies lead to distinct optimization trajectories, and an improper client
selection strategy can cause the optimization trajectory to deviate seriously
from the optimal one, significantly hindering the model performance.
Therefore, a critical challenge is to develop an effective client selection
strategy that reduces the communication overhead while ensuring model
convergence.

In most cases, the global models generated by full client participation are
considered the gold standard or benchmark. This is because they represent
models trained on the entire dataset available across all clients, offering a
comprehensive reference point for evaluating model performance. Building upon
this understanding, we propose an intuitive strategy where clients are
selected in a manner that ensures the optimization trajectory closely
resembles that achieved with full client participation over the long term. We
refer to this strategy as the long-term client selection strategy. This
strategy yields two key advantages. First, by emulating the optimization
trajectory of full client participation, it aims to achieve comparable
performance. Moreover, it reduces communication overhead by involving only a
subset of clients in the process.

Our Goal. In this work, we investigate the three questions: 1) what principles
should be followed to implement this strategy; 2) how to mathematically
formulate this strategy and provide a fast solution; and 3) is this strategy
more effective than existing methods? To answer the first question, we propose
two crucial principles to be followed.

Principle I: _In each round, the data distribution generated by the selected
subset of clients should closely resemble the data distribution of the full
client participation_. For example, in Fig. 1 (a), clients collaboratively
train an image classification model, where each client has images of only one
kind of animal, and three clusters exist in their data distributions. Due to
limited bandwidth, the server is required only to select three clients in each
round. In this case, as shown in Fig. 1 (b), the ideal strategy is to select
one client from each cluster instead of three clients from the same cluster.
This ensures that the data distribution resulting from the subset of selected
clients serves as a reliable estimation of that from the full set of clients.
However, in real-world applications, the clustering pattern in data
distributions may be unknown or non-existent. Therefore, the key challenge
here is to determine the subset of clients that best approximates the full
client set without imposing extensive assumptions on their data distributions.

Figure 1: An example of the long-term client selection strategy.

However, if only Principle I is followed and client selection is performed by
evaluating each round individually, there is a risk that the same subset of
clients may be consistently selected across multiple rounds, while others may
have minimal opportunities for selection. This phenomenon is indeed observed
in our experimental results. In such cases, the system may accurately predict
outcomes for frequently selected clients but makes inaccurate or biased
predictions for those rarely selected, resulting in degradation of the global
model’s performance and ineffective convergence. Furthermore, these seldom-
selected clients may perceive unfair treatment and lose motivation to
participate, ultimately endangering the sustainability of the federated
system.

To mitigate this problem, we propose Principle II, which guides client
selection across multiple rounds from a long-term perspective. Principle II:
_In multi-round selection, clients with similar data distributions should have
similar frequencies of being selected._ For example, as illustrated in Fig. 1,
clients 1, 2, and 3 should share similar selection frequencies, as should
clients 4 and 5, while the frequencies for clients 1 and 4 may differ. This
principle aligns with the concept of individual fairness (IF) in central
machine learning [8], which posits that similar instances or individuals in a
dataset should yield similar predictions or outcomes. In our work, we refer to
this principle as the individual fairness constraint. Here, the key challenge
is to quantify the similarity between clients in terms of data distribution
and selection frequency, respectively, and further formulate individual
fairness mathematically.

This proposed individual fairness offers two key benefits. First, as
illustrated in Fig. 1 (c), it promotes the diversity of selected clients
across multiple rounds and reduces model prediction bias. Furthermore,
existing fair federated learning approaches often utilize a uniform sampling
constraint [9, 10, 11] to ensure similar selection probabilities for all
clients. However, this uniform approach may compromise selection performance,
as it disregards the heterogeneous data distribution among clients. In
contrast, our proposed fairness constraint specifically targets clients with
similar data distributions. Thus, it allows for varying selection frequencies
among clients with heterogeneous data distributions, such as clients 1 and 4
in Fig. 1. This flexibility enables the individual constraint to accommodate
the data heterogeneity without compromising selection performance in single
rounds.

Limitation of Prior Works. To address the client selection problem, a common
approach is the random selection strategy [1]. Recent works have proposed
various improvements, including contribution-based [12, 1, 13, 14, 15], loss-
based [16, 17, 18], and cluster-based methods [19, 20]. However, these methods
typically evaluate each round individually and fail to select clients from a
long-term perspective, potentially leading to model biases and fairness
issues. Additionally, the clustering pattern in data distributions may be
unknown or non-existent, making the application of cluster-based methods
challenging. Furthermore, fair federated learning has discussed collaborative
fairness [13, 15, 21], group fairness [22, 22] and performance fairness [23,
24], where performance fairness aligns most closely with our objectives.
Existing fair federated learning approaches often utilize a uniform sampling
constraint [9, 10, 11] to ensure similar selection probabilities for all
clients. However, it disregards the heterogeneous data distribution among
clients and requires their selection probabilities to be uniformly similar.
This may hinder the identification of the optimal subset of clients that best
approximates the full set of clients.

In this study, we propose a novel long-term client selection strategy in
federated learning (_LongFed_), designed to emulate the model performance
achieved with full client participation. In a single round, we perform client
selection by minimizing the estimation error between a representative subset
of clients and the full set of clients. In multi-round selection, we propose a
novel individual fairness constraint to promote the diversity of selected
clients without compromising selection performance in single rounds.
Subsequently, we formulate the client selection problem as a time-averaged
optimization function and simplify it using Lyapunov optimization from control
theory. In addition, leveraging the submodular nature of the optimization
function, we propose a fast greedy algorithm to find the optimal subset of
clients in each round. The convergence of the proposed strategy is also
analyzed. We conduct extensive experiments to validate the proposed _LongFed_
strategy. First, the proposed strategy effectively guides the system to
converge along a trajectory similar to that of full client participation.
Second, it outperforms prior works in terms of both accuracy and fairness.
Last, the proposed strategy introduces minimal time overhead compared to the
random selection strategy. Our contributions are as follows.

  * •

We propose a novel long-term client selection strategy designed to guide the
system to converge along a trajectory similar to that of full client
participation. This strategy does not require extensive assumptions on the
data distribution.

  * •

We identify and address an issue that has been rarely discussed in previous
works, i.e., the frequency of selecting clients with similar distributions. We
propose an individual fairness criterion to mathematically formulate this
issue and employ Lyapunov optimization to solve it.

  * •

We provide an extensive theoretical analysis of the convergence ability of the
proposed strategy.

##  II Related Work

Existing literature relevant to our work can be broadly categorized into two
groups: client selection methods and fairness issues in federated learning.

###  II-A Client Selection in Federated Learning

In vanilla federated learning systems [1], the random selection strategy is
commonly employed to choose clients. Recent works have proposed various
improvements, including contribution-based [12, 1, 13, 14, 15], loss-based
[16, 17, 18], and cluster-based methods [19, 20].

The first type focuses on evaluating client contributions, where clients with
higher contributions are assigned higher selection probabilities. One commonly
used metric is the local data size, and clients with larger datasets are
considered to have higher contributions [12, 1]. Another approach involves
employing the Shapley value [25] from game theory, which calculates the
average marginal model improvement of each client over all possible coalitions
[13, 14, 15]. Clients that result in larger model performance improvements are
regarded as making larger contributions and are assigned higher probabilities
of selection. Additionally, some methods evaluate the similarity between the
local model at each client and the aggregated global model at the server.
Clients with higher similarities are considered to bring little improvement to
the global model and are thus assigned lower selection probabilities in
subsequent training epochs [21, 26].

The second type involves selecting clients based on their training losses.
These methods consider that clients with higher training losses may struggle
to effectively fit their local data. As a result, they assign higher selection
probabilities or weights to these clients [16, 17]. FedCor is a representative
work in loss-based approaches that employs Gaussian processes to model the
loss correlations between clients and selects clients with a substantial
reduction in expected global loss [18]. Furthermore, recognizing that clients
may contain similar and redundant information, a diverse strategy is proposed
to choose a subset of clients that can best represent the full client set
[27].

The third approach involves a cluster-based strategy. Recognizing that clients
may have different data distributions or have their own learning tasks, these
clustering-based approaches divide the clients into several clusters. Clients
within the same cluster exhibit similar data distributions, whereas those in
different clusters may display significant variations in their data
distributions. In aggregation, the server randomly selects a client from each
cluster. In this cluster-based paradigm, FedCG leverages a graph neural
network to capture gradient sharing across multiple clusters [19]. Moreover,
IFCA addresses the cluster identification problem by determining the cluster
membership of each client and optimizes each of the cluster models in a
federated learning framework [20].

However, most of these methods select clients by evaluating each round
individually, thus failing to optimize a series of client subsets from a long-
term perspective. These limitations could cause potential model biases and
fairness issues, ultimately resulting in lower convergence efficiency.
Furthermore, if the clustering pattern among clients is known, the long-term
client selection problem becomes straightforward: simply selecting one client
randomly from each cluster in every communication round [20]. However, in
practical scenarios, the clustering pattern is usually unknown or, in some
cases, does not exist. This limitation renders cluster-based methods
ineffective for solving the long-term client selection problem.

###  II-B Fairness in Federated Learning

There are three types of fairness in federated learning: collaborative
fairness, group fairness, and performance fairness. Collaborative fairness
emphasizes that clients who make larger contributions should be rewarded with
correspondingly larger rewards, and the assessment of client contributions is
a key challenge. Client contribution evaluation methods have been discussed in
Section II-A in the context of contribution-based client selection methods.

Group fairness [28], also known as algorithmic fairness, emphasizes that model
outputs should not unfairly discriminate against vulnerable or
underrepresented groups, such as minorities, women, or the aged [29]. FairFed
[22] serves as one of the representative works of addressing this concern. In
FairFed, both global fairness metrics at the server and local fairness metrics
at each client are defined. These metrics assess disparities in opportunities
among different groups. FairFed then dynamically adjusts aggregation weights
at each round based on the discrepancies between global and local fairness
metrics, which effectively mitigates the biases towards sensitive attributes
[22].

Performance fairness refers that the model should produce similar performance
across all clients, where the uniformity of performance is commonly used as
the metric for evaluation [30, 31]. Various approaches have emerged to achieve
performance fairness. For example, in [24], fairness is defined by assigning
uniform weight to each client and introduced as an additional constraint in
the optimization function. Besides, [23] identifies a trade-off between model
robustness and fairness, and proposes a personalized framework to inherently
achieve both fairness and robustness benefits. Moreover, several works study
the fairness issue by considering that the probability of being selected is
similar for all clients [9, 10, 11].

However, the three types of fairness described above cannot effectively
address the fairness issue outlined in Principle II. While collaborative
fairness and group fairness focus on different aspects compared to our work,
performance fairness aligns most closely with our objectives. In these works
[9, 10, 11], the uniform sampling method ensures a similar probability of
being selected for all clients. However, we argue that it is unsuitable for
achieving the long-term client selection strategy. This is because the uniform
sampling method disregards the heterogeneous data distribution among clients.
Consequently, it may hinder the identification of the optimal subset of
clients that best approximates the data distribution of full client
participation.

##  III The Proposed Optimization Function

In this section, we begin with an introduction to the federated learning
system. Next, we illustrate the client selection in a single round and across
multiple rounds, followed by the proposed long-term optimization function.
Last, we apply Lyapunov optimization to transform and simplify the
optimization function.

###  III-A Preliminary of Federated Learning

In our work, we consider that the federated learning system consists of a
central server and a set of clients denoted as $\mathbb{N}=\\{1,\cdots,N\\}$.
Each client $i\in\mathbb{N}$ has its own local dataset $\mathcal{D}_{i}$ with
a size of $|\mathcal{D}_{i}|$. Due to limited communication bandwidth, in the
$t$-th round, the server typically selects a subset of clients, denoted as
$\mathbb{S}^{t}$ with $|\mathbb{S}^{t}|=K<N$. Clients within the subset
$\mathbb{S}^{t}$ receive the global model $\bm{w}^{t}$ from the server. They
then compute local updates on their respective local datasets, transmitting
the resulting local gradients $\nabla f_{j}(\bm{w}^{t})$ back to the server.
The server aggregates these gradients and updates the model parameters using

$\displaystyle\bm{w}^{t+1}=\bm{w}^{t}-\eta_{t}\sum_{j\in\mathbb{S}^{t}}\theta^{t}_{j}\nabla
f_{j}(\bm{w}^{t}).$ (1)

Here, $\eta_{t}$ represents the predefined learning rate, and $\theta^{t}_{j}$
denotes the weight assigned to client $j\in\mathbb{S}^{t}$ in the $t$-th
round. The training process lasts for $T$ communication rounds until the
global model achieves convergence. Here, the subset $\mathbb{S}^{t}$ and the
weight $\theta^{t}_{j}$ with $j\in\mathbb{S}^{t}$ are the variables to be
determined.

###  III-B The Optimization Function

####  III-B1 Client Selection in a Single Round

In a single round, we identify the subset of clients that best approximates
the data distribution of the full set of clients. Specifically, we evaluate
the estimation error between the aggregated gradient obtained from the client
subset $\mathbb{S}^{t}$ and the aggregated gradient obtained from the full
client set $\mathbb{N}$. A small estimation error indicates that the subset of
selected clients can effectively represent the data distribution of the full
client set. Mathematically, we formulate it as

$\displaystyle\text{D}(\mathbb{S}^{t})=\min_{\theta_{j}^{t}>0}||\sum_{i\in\mathbb{N}}\nabla
f_{i}(\bm{w}^{t})-\sum_{j\in\mathbb{S}^{t}}\theta_{j}^{t}\nabla
f_{j}(\bm{w}^{t})||_{2}^{2}.$ (2)

Here, $\nabla f_{i}(\bm{w}^{t})$ represents the gradient of the $i$-th client,
$\sum_{i\in\mathbb{N}}\nabla f_{i}(\bm{w}^{t})$ is the aggregated gradient on
the full client set $\mathbb{N}$, and
$\sum_{j\in\mathbb{S}^{t}}\theta_{j}^{t}\nabla f_{j}(\bm{w}^{t})$ denotes the
weighted sum of gradients on the client subset $\mathbb{S}^{t}$. Then,
selecting a subset of clients that best approximates the data distribution of
the full client set is equivalent to choosing a subset that minimizes the
estimation error defined in Eq. (2).

Notice that the formation in Eq. (2) is similar to the concept of data coreset
introduced in [32]. The data coreset involves selecting a weighted small
sample of training data to approximate the gradient of the whole training data
set. It is important to highlight that data coreset is commonly employed to
enhance training efficiency in centralized machine learning scenarios [33,
34], while our focus is on optimizing client selection to reduce communication
bandwidth in decentralized and federated scenarios. Moreover, data coreset is
typically utilized for a one-time data selection process, while client
selection in federated learning is a long-term process carried out across
multiple rounds. The long-term optimization nature introduces new challenges,
such as fairness issues and potential model biases introduced in Section I.

In Eq. (2), when clients are not selected in the $t$-th round, the gradients
$\nabla f_{i}(\bm{w}^{t})$ for these clients become unknown, rendering the
optimization of $\text{D}(\mathbb{S}^{t})$ intractable. To address this
challenge, we obtain the upper bound of $\text{D}(\mathbb{S}^{t})$, denoted as
$\text{DUB}(\mathbb{S}^{t})$ in Eq. (3), and minimize this upper bound
instead. The proof of Theorem 1 is provided in the supplementary file.

######  Theorem 1.

Define

$\displaystyle\text{DUB}(\mathbb{S}^{t})\triangleq\sum_{i=1}^{N}\min_{j\in\mathbb{S}^{t}}\|\nabla
f_{i}(\bm{w}^{t})-\nabla f_{j}(\bm{w}^{t})\|_{2}^{2},$ (3)

then $\text{DUB}(\mathbb{S}^{t})$ serves as an upper bound for
$\text{D}(\mathbb{S}^{t})$.

Specifically, following the analysis in [32], we assume a mapping
$\xi^{t}:\mathbb{N}\rightarrow\mathbb{S}^{t}$ that assigns each client
$i\in\mathbb{N}$ to a client $j\in\mathbb{S}^{t}$, i.e., $\xi^{t}(i)=j$,
indicating that client $i$ can be approximately represented by client $j$ in
the $t$-th round. For a client $j\in\mathbb{S}^{t}$, let
$\mathbb{C}^{t}_{j}=\\{i\in\mathbb{N}\,|\,\xi^{t}(i)=j\\}$ be the set of
clients that can be represented by client $j$. The value
$\theta^{t}_{j}=|\mathbb{C}^{t}_{j}|$ is the number of such clients being
represented, and is used as the weight of client $j$ in Eq. (1). Based on the
mapping $\xi^{t}$, we obtain the upper bound of the estimation error in Eq.
(2), as stated in Theorem 1. In the later section, we utilize
$\text{DUB}(\mathbb{S}^{t})$ when minimizing the estimation error
$\text{D}(\mathbb{S}^{t})$ is required.

To manage the computation of $\text{DUB}(\mathbb{S}^{t})$ in Eq. (3), we
introduce the metric $\text{Dist}_{i,j}(t)$ to quantify the distance between
two clients $i$ and $j$ in the $t$-th round. This metric is defined as

$\displaystyle\text{Dist}_{i,j}(t)=||\nabla f_{i}(\bm{w}^{t})-\nabla
f_{j}(\bm{w}^{t})||_{2}^{2}.$ (4)

Note that when clients $i,j\in\mathbb{N}$ are not selected in the $t$-th
round, their gradients $\nabla f_{i}(\bm{w}^{t})$ and $\nabla
f_{j}(\bm{w}^{t})$, and consequently $\text{Dist}_{i,j}(t)$, cannot be
calculated. To address this issue, we propose partial updates for
$\text{Dist}_{i,j}(t)$. Specifically, when $t=0$, all clients are selected,
and we compute $\text{Dist}_{i,j}(t)$ for each pair of clients. Then, for
$t\geq 1$, the server updates $\text{Dist}_{i,j}(t)$ using the gradients only
from the selected $K$ clients. That is expressed as

$\displaystyle\text{Dist}_{i,j}(t)=\begin{cases}&\|\nabla
f_{i}(\bm{w}^{t})-\nabla
f_{j}(\bm{w}^{t})\|_{2}^{2},\;\text{if}\;i,j\in\mathbb{S}^{t},\\\
&\text{Dist}_{i,j}(t-1),\;\text{otherwise}.\end{cases}$ (5)

Although using $\text{Dist}_{i,j}(t-1)$ to approximate $\text{Dist}_{i,j}(t)$
may introduce biases when either client is not selected, experimental results
demonstrate that there are minimal impacts on the model convergence. This can
be attributed to two reasons. First, there are limited variations in gradients
between successive communication rounds. Moreover, the individual fairness
constraint proposed in Section III-B2 ensures that each client has the
opportunity of being selected and the corresponding $\text{Dist}_{i,j}(t)$ can
be updated. In the following, we use $\text{Dist}_{i,j}(t)$ in Eq. (5) to
replace the term $\|\nabla f_{i}(\bm{w}^{t})-\nabla
f_{j}(\bm{w}^{t})\|_{2}^{2}$ in Eq. (3) to make $\text{DUB}(\mathbb{S}^{t})$
solvable.

####  III-B2 Client Selection Across Multiple Rounds

In our work, we propose a novel fairness constraint to guide the client
selection process across multiple rounds. This constraint asserts that clients
with similar data distributions should have similar frequencies of being
selected.

To formulate the fairness constraint, we establish metrics to measure the
similarity between a pair of clients in terms of their data distributions and
the frequencies of being selected, respectively. First, we use
$\text{Dist}_{i,j}(t)$ in Eq. (4) to measure the similarity of the data
distribution and use Eq. (5) to compute its value. Second, let $x_{i,t}$
represent whether the $i$-th client is selected in the $t$-th round, with
$x_{i,t}=1$ if $i\in\mathbb{S}^{t}$ and $x_{i,t}=0$ otherwise. We use

$\displaystyle p_{i}=\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}(x_{i,t}).$ (6)

to evaluate the frequency of a client $i$ being selected throughout the total
$T$ rounds. Note that $\\{x_{i,t}\\}$ forms a stochastic process, and the
expectation operation $\mathbb{E}$ is applied in Eq. (6). Given two clients
$i,j\in\mathbb{N}$, we use $|p_{i}-p_{j}|$ to quantify the difference between
their frequencies of being selected.

Building on $\text{Dist}_{i,j}(t)$ and $p_{i}$, we employ the
$\epsilon\text{-}\delta$-IF framework utilized in [35, 36] to quantify the
fairness constraint. We evaluate a client selection strategy at the end of the
$T$-th communication round. Specifically, given $\epsilon,\delta\geq 0$, a
client selection strategy is of individual fairness if for every pair of
clients $i,j\in\mathbb{N}$ with $\text{Dist}_{i,j}(T)\leq\epsilon$, the
difference in their frequencies of being selected, namely, $p_{i}$ and
$p_{j}$, should not exceed $\delta$. The mathematical formulation of
$\epsilon\text{-}\delta$-IF is provided in Definition 1, and the impact of
parameter selection for $\epsilon$ and $\delta$ is discussed in Section V-C.

######  Definition 1.

($\epsilon\text{-}\delta$-IF). Consider $\epsilon,\delta\geq 0$, a client
selection strategy is said to be of individual fairness if

$\displaystyle\forall\,i,j\in\mathbb{N},\,\,\text{Dist}_{i,j}(T)\leq\epsilon\,\,\Rightarrow\,\,|p_{i}-p_{j}|\leq\delta.$
(7)

Note that $\epsilon\text{-}\delta$-IF requires examining Eq. (7) for all pairs
of clients, leading to significant computational overhead and rendering
subsequent optimization challenging. To address this issue, we propose to
determine a reference client $i^{\star}$ for each client $i$, which exhibits
the largest difference in the frequency of being selected among clients whose
gradient distances are less than $\epsilon$. That is,

$\displaystyle
i^{\star}=\text{argmax}_{\text{Dist}_{i,j}(T)\leq\epsilon}\,|p_{i}-p_{j}|,\;\forall\;j\in\mathbb{N}.$
(8)

Then, given a client $i$ and its reference client $i^{\star}$, a client
selection strategy is certified as $\epsilon\text{-}\delta$-IF if

$\displaystyle|p_{i}-p_{i^{\star}}|\leq\delta,\quad\forall\;i\in\mathbb{N}.$
(9)

By introducing the reference client in Eq. (8), the evaluation of
$\epsilon\text{-}\delta$-IF is simplified from examining Eq. (7) for pairs of
clients $i,j\in\mathbb{N}$ to evaluating Eq. (9) for individual clients
$i\in\mathbb{N}$. This reduction in the number of variables facilitates
further optimization.

####  III-B3 The Optimization Function

Building on the estimation error in Eq. (2) and the individual fairness
constraint in Eq. (9), we formulate the client selection strategy as an
optimization problem. The objective is to select a series of subsets
$\\{\mathbb{S}^{1},\cdots,\mathbb{S}^{T}\\}$ with $|\mathbb{S}^{t}|=K$ that
minimize the expected estimation error over all $T$ rounds while adhering to
the individual fairness constraint. That is,

(P1)
$\displaystyle\min_{\\{\mathbb{S}^{1},\cdots,\mathbb{S}^{T}\\}}\;\lim_{T\to+\infty}\frac{1}{T}\,\sum_{t=1}^{T}\mathbb{E}\left[\text{DUB}(\mathbb{S}^{t})\right],$
(10) $\displaystyle\qquad\textrm{s.t.}\quad\quad\text{Eq.
\eqref{equ:client_star_IF}}.$

However, directly solving the optimization function in Eq. (10) is infeasible.
The optimization objective and constraints, particularly $p_{i}$ in Eq. (9),
are presented in a time-averaged form. That is, these values are determined by
averaging over all $T$ rounds, which can only be accomplished at the end of
training. In contrast, federated learning requires clients to be selected
online in each round. This misalignment poses a practical implementation
challenge. In our work, the solution to address this misalignment is proposed
in Section III-C.

###  III-C Problem Transformation Under Lyapunov Optimization

To solve P1 in Eq. (10), we leverage Lyapunov optimization, a technique from
control theory used to analyze the stability of dynamic systems [37, 9]. The
main idea behind Lyapunov optimization is to break down the long-term time-
averaged constraints in the optimization problem into constraints that can be
adhered to in each communication round. This allows us to optimize the
objective function directly in each round without violating the constraints
specific to that round. Furthermore, by ensuring that these constraints are
adhered to in each round, we can automatically achieve compliance with the
long-term time-averaged constraints at the end of the $T$ round. By leveraging
Lyapunov optimization, the problem stated as P1 in Eq. (10) is ultimately
converted into the problem P3 in Eq. (23), which can be efficiently solved
online in each communication round. Details of problem transformation are
described below.

Before employing Lyapunov optimization, we remove the absolute value sign from
the constraint in Eq. (9) and rephrase it as two equivalent constraints,

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}(x_{i,t}-x_{i^{\star},t})-\delta\leq
0,\;\forall\,i\in\mathbb{N},$ (11)
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}(-x_{i,t}+x_{i^{\star},t})-\delta\leq
0,\;\forall\,i\in\mathbb{N}.$ (12)

Lyapunov optimization typically involves three steps [37]. First, a virtual
queue is defined for each time-averaged constraint. This step converts the
time-averaged constraints into stability constraints for virtual queues.
Second, a Lyapunov function is defined based on virtual queues, and the
Lyapunov drift is introduced. This step breaks down the time-averaged
constraints into requirements for Lyapunov drift in each communication round.
Finally, the Lyapunov drift is integrated into the optimization objective,
allowing us to minimize both the Lyapunov drift and the optimization objective
simultaneously. In the following, we illustrate how to transform problem P1
using these three steps.

First, we define two virtual queues, namely $Z_{i}(t)$ for the constraint in
Eq. (11) and $Q_{i}(t)$ for the constraint in Eq. (12), for all clients
$i\in\mathbb{N}$. Specifically, these queues are initialized as $Z_{i}(0)=0$
and $Q_{i}(0)=0$, and updated according to the following rule

$\displaystyle
Z_{i}(t+1)=\max\left\\{Z_{i}(t)+x_{i,t}-x_{i^{\star},t}-\delta,0\right\\},$
(13) $\displaystyle
Q_{i}(t+1)=\max\left\\{Q_{i}(t)-x_{i,t}+x_{i^{\star},t}-\delta,0\right\\}.$

By the introduction of $Z_{i}(t)$ and $Q_{i}(t)$, we have Theorem 2, which
converts the long-term constraints on $x_{i,t}$ in Eq. (11) and (12) into the
stability constraints for $Z_{i}(t)$ and $Q_{i}(t)$. The proof of Theorem 2 is
provided in the supplementary file.

######  Theorem 2.

The constraints in Eq. (11) and (12) hold if $Z_{i}(t)$ and $Q_{i}(t)$ remain
stable, that is,

$\displaystyle\lim_{T\to+\infty}\frac{\mathbb{E}[Z_{i}(T)]}{T}=0,\;\text{and}\;\lim_{T\to+\infty}\frac{\mathbb{E}[Q_{i}(T)]}{T}=0.$
(14)

To make $Z_{i}(t)$ and $Q_{i}(t)$ remain stable, an intuitive approach is to
bound the increase of these queues in each round so that they could not grow
to infinity. Based on this intuition, in our work, we define a global queue
$\Theta(t)$, which stores the state of $Z_{i}(t)$ and $Q_{i}(t)$ for all
clients. That is,

$\displaystyle\Theta(t)\triangleq\left[Z_{1}(t),\cdots,Z_{n}(t),Q_{1}(t),\cdots,Q_{n}(t)\right].$
(15)

Second, following Lyapunov optimization, we define the Lyapunov function [37]
as

$\displaystyle
L\left(\Theta(t)\right)\triangleq\frac{1}{2}\sum_{i=1}^{N}\left[Z_{i}^{2}(t)+Q_{i}^{2}(t)\right],$
(16)

which represents the sum of the squares of all elements in $\Theta(t)$. Then,
the increase of $\Theta(t)$ from the communication round $t$ to $(t+1)$ is
formulated as

$\displaystyle\Delta\left(\Theta(t)\right)\triangleq\mathbb{E}\left[L\left(\Theta(t+1)\right)-L\left(\Theta(t)\right)|\Theta(t)\right],$
(17)

which is called _Lyapunov drift_ [37]. If the drift
$\Delta\left(\Theta(t)\right)$ remains sufficiently small in each round, the
constraints in Eq. (11) and Eq. (12) will be satisfied after $T$ rounds. That
is, introducing $\Delta\left(\Theta(t)\right)$ allows us to break down the
time-averaged constraints in Eq. (11) and Eq. (12) into the specific
requirements for $\Delta\left(\Theta(t)\right)$ in each communication round.

At last, to ensure that $\Delta\left(\Theta(t)\right)$ remains sufficiently
small, a straightforward method to combine the optimization objection with the
drift $\Delta\left(\Theta(t)\right)$, and minimize both simultaneously.
Mathematically, in our work, the optimization problem in Eq. (10) is
transformed into

$\displaystyle\text{(P2)}\;\min_{\mathbb{S}^{t}}\quad(1-V)\cdot\Delta\left(\Theta(t)\right)+V\cdot\text{DUB}(\mathbb{S}^{t})$
(18)

with $|\mathbb{S}^{t}|=K$ as a constraint, where $V$ is a predefined trade-off
factor. Note that the expectation notation $\mathbb{E}$ is dropped since we
are only concerned with a single communication round.

However, solving P2 in Eq. (18) still presents two challenges. First,
determining $i^{\star}$ requires the information about $p_{i}$, which is not
available until the end of training. To address the issue, we calculate the
frequency of a client $i$ being selected up to the $t$-th round, denoted as
$p_{i}(t)=\frac{1}{t}\sum_{k=1}^{t}x_{i,t}$. Then, we determine the reference
client in the $t$-th round by

$\displaystyle
i^{\star}_{t}=\text{argmax}_{\text{Dist}_{i,j}(t)\leq\epsilon}|p_{i}(t)-p_{j}(t)|,\;\forall\,j\in\mathbb{N}.$
(19)

In our experiment, we replace the reference client $i^{\star}$ in Eq. (8) with
$i^{\star}_{t}$ in Eq. (19), thus it can be determined using information
available up to the $t$-th round.

Additionally, because the computation of $\Delta\left(\Theta(t)\right)$
requires information about $L\left(\Theta(t+1)\right)$, which is not available
in the current round $t$. To overcome this issue, we derive an upper bound for
$\Delta\left(\Theta(t)\right)$ using Theorem 3 and minimize the upper bound
instead. The proof is provided in the supplementary file.

######  Theorem 3.

Define

$\displaystyle
m_{i,t}=x_{i,t}-x_{i^{\star}_{t},t}-\delta,\;\text{and}\;n_{i,t}=-x_{i,t}+x_{i^{\star}_{t},t}-\delta,$
(20)

then $\Delta\left(\Theta(t)\right)$ is bounded by

$\displaystyle\Delta\left(\Theta(t)\right)\leq
B+\sum_{i=1}^{N}\left[Z_{i}(t)m_{i,t}+Q_{i}(t)n_{i,t}\right],$ (21)

where $B$ is a constant.

Based on Theorem 3, the problem P2 in Eq. (18) is transformed into

$\displaystyle\min_{\mathbb{S}^{t}}\;(1-V)\sum_{i=1}^{N}\left[Z_{i}(t)m_{i,t}+Q_{i}(t)n_{i,t}\right]+V\cdot\text{DUB}(\mathbb{S}^{t}).$
(22)

Substituting $\text{DUB}(\mathbb{S}^{t})$ by Eq. (3) and moving the sum sign
outside of the minimum sign, the problem in Eq. (22) is equivalent to

$\displaystyle\min_{\mathbb{S}^{t}}\;G(\mathbb{S}^{t})=\sum_{i=1}^{N}\min_{j\in\mathbb{S}^{t}}\Big{\\{}(1-V)\big{[}Z_{i}(t)m_{i,t}+Q_{i}(t)n_{i,t}\big{]}$
(23) $\displaystyle\text{(P3)}\qquad\qquad\qquad\qquad+V\cdot\big{\|}\nabla
f_{i}(\bm{w}^{t})-\nabla f_{j}(\bm{w}^{t})\big{\|}\Big{\\}},$

where $Z_{i}(t)$ and $Q_{i}(t)$ are defined in Eq. (13), $m_{i,t}$ and
$n_{i,t}$ are defined in Eq. (20), and $V$ is a hyperparameter that balances
the optimization function and the fairness constraint. With an appropriate
$V$, the solution in Eq. (23) can infinitely approximate the optimal solution
in Eq. (18) [38]. In the following, we select clients by minimizing
$G(\mathbb{S}^{t})$ in Eq. (23) in each round.

##  IV The Proposed _LongFed_

###  IV-A The Client Selection Strategy

The optimization problem in Eq. (23) is NP-hard as it involves calculating the
value of $G(\mathbb{S}^{t})$ for $\frac{N!}{K!(N-K)!}$ subsets, where $!$
denotes the factorial function [39]. To address this issue, we exploit the
submodular nature of $G(\mathbb{S}^{t})$.

Specifically, a set function $g:2^{\mathbb{N}}\rightarrow\mathbb{R}$ is
submodular if for every $A\subseteq B\subseteq\mathbb{N}$ and
$i\in\mathbb{N}\backslash B$ it holds that
$g(A\cup\\{i\\})-g(A)>g(B\cup\\{i\\})-g(B)$. One typical example of a
submodular function is the facility location function [40]. Suppose we aim to
select locations from a set of positions $\mathbb{N}=\\{1,\ldots,N\\}$ to open
facilities and to serve a collection of $K$ users. If a facility is located at
position $j$, the service it provides to user $i$ is quantified by $M_{i,j}$.
Each user is assumed to select the facility with the highest service, and the
total service provided to all users is modeled by the set function

$\displaystyle f(\mathbb{S})=\sum_{i=1}^{m}\max_{j\in\mathbb{S}}M_{i,j},$ (24)

where $f(\emptyset)=0$. If $M_{i,j}\geq 0$ for all $i,j$, then $f(\mathbb{S})$
is a monotone submodular function. By introducing an auxiliary element $e$,
the set function $G(\mathbb{S}^{t})$ in Eq. (23) is transformed into

$\displaystyle\overline{G}(\mathbb{S}^{t})=G(\\{e\\})-G(\mathbb{S}^{t}\cup\\{e\\}),$
(25)

which is a facility location function and has a submodular nature.
$\overline{G}(\mathbb{S}^{t})$ measures the decrease in the value of
$G(\mathbb{S}^{t})$ associated with the set $\mathbb{S}^{t}$ compared to that
associated with just the auxiliary element $e$. Without loss of generality, we
set the auxiliary element as $e=1$. Consequently, minimizing
$G(\mathbb{S}^{t})$ in Eq. (23) is equivalent to maximizing
$\overline{G}(\mathbb{S}^{t})$ in Eq. (25).

Algorithm 1 The Proposed Client Selection Strategy

1:Input: $Z_{i}(t)$, $Q_{i}(t)$

2:Output: the selected subset $\mathbb{S}^{t}$

3:Initialize $\mathbb{S}_{0}^{t}=\emptyset$, $\mathbb{P}_{0}=\mathbb{N}$, and
$e=1$.

4:for $k\in[0,K-1]$ do

5: Determine the reference client $i^{\star}_{t}$ for $i\in\mathbb{P}_{k}$

6: Compute $m_{i,t}$ and $n_{i,t}$ for $i\in\mathbb{P}_{k}$

7: Calculate $G(\mathbb{S}_{k}^{t}\cup\\{i\\}),\forall\,i\in\mathbb{P}_{k}$

8: Identify the client
$i_{\text{max}}=\text{argmax}_{i}\overline{G}(\mathbb{S}_{k}^{t}\cup\\{i\\})$

9: $\mathbb{S}_{k+1}^{t}\leftarrow\mathbb{S}_{k}^{t}\cup
i_{\text{max}},\;\mathbb{P}_{k+1}\leftarrow\mathbb{P}_{k}\backslash
i_{\text{max}}$

10:end for

Prior studies show that the greedy algorithm is an effective solution for
finding the maximum value of a submodular function [41, 39]. Following this
greedy algorithm, we propose a strategy to select clients in the $t$-th round,
as outlined in Algorithm 1. The proposed strategy starts with an empty set
$\mathbb{S}_{0}^{t}=\emptyset$, and initializes a candidate set as
$\mathbb{P}_{0}=\mathbb{N}$ (Line 3). In an iteration $k\in[0,K-1]$, we first
determine the reference client $i^{\star}_{t}$ for client
$i\in\mathbb{P}_{k}$, and compute $m_{i,t}$ and $n_{i,t}$ with $x_{i,t}=1$ if
$i\in\mathbb{S}^{t}_{k}$, and similarly for $x_{i^{\star}_{t},t}$ (Line 5-6).
Next, we calculate $\overline{G}(\mathbb{S}_{k}^{t}\cup\\{i\\})$ for all
clients $i\in\mathbb{P}_{k}$, and identify the client $i_{\text{max}}$ with
the maximum value (Line 7-8). Subsequently, the client $i_{\text{max}}$ is
removed from $\mathbb{P}_{k}$ and added to the subset $\mathbb{S}_{k}^{t}$
(Line 9). This iteration continues until $K$ clients are selected. The
complexity of the algorithm is $O(KN)$.

Based on the client selection strategy in Algorithm 1, we further present the
proposed federated training algorithm, as outlined in Algorithm 2. First, the
server initializes the queues $Z_{i}(0)$ and $Q_{i}(0)$, along with the model
parameter $\bm{w}^{0}$ (Line 3). Subsequently, the server selects the subset
of clients $\mathbb{S}^{t}$ (Line 5-9). If the communication round $t=0$, all
clients are selected; otherwise, the server selects $K$ clients according to
Algorithm 1. The server then sends the model parameter $\bm{w}^{t}$ to the
selected clients, and these clients perform local training and send the
gradients back to the server (Line 10-11). The server updates $Z_{i}(t)$ and
$Q_{i}(t)$ according to Eq. (13), and aggregates these results to obtain the
model parameter $\bm{w}^{t+1}$ according to Eq. (1). The iteration is repeated
until completing the $T$ rounds.

Algorithm 2 The Federated Training Algorithm

1:Input: $\epsilon$, $\delta$, $V$ and $T$

2:Output: The trained model $\bm{w}^{T}$

3:Initialize $\bm{w}^{0}$, $Z_{i}(0)=Q_{i}(0)=0$,

4:for $t\in[0,T]$ do

5: if $t=0$ then

6: Select all clients with $\mathbb{S}^{t}=\mathbb{N}$

7: else

8: Select K clients $\mathbb{S}^{t}$ according to Algorithm 1

9: end if

10: The server sends $\bm{w}^{t}$ to the selected clients in $\mathbb{S}^{t}$

11: Clients train local models in parallel and send the gradients $\nabla
f_{i}(\bm{w}^{t})$ to the server

12: The server update $Z_{i}(t+1)$, $Q_{i}(t+1)$

13: The server aggregate the results and obtain $\bm{w}^{t+1}$

14:end for

###  IV-B Convergence Analysis

We provide a theoretical analysis to demonstrate the convergence ability of
the proposed client selection strategy. The analysis uses FedAvg as the
aggregation method, and it can be extended to other federated optimization
methods as well. To implement the theoretical analysis, we establish six
assumptions regarding the local models and data distribution heterogeneity
among clients.

First, based on the effective greedy selection strategy in Algorithm 1, we
assume that the estimation error between the client subset and the full client
set (Eq. (2)) is small and can be quantified by a variable $\rho$, as stated
in Assumption 1. This assumption has also been studied in the context of data
coreset selection [32] and client selection methods [27]. Note that $\rho$ is
used as a measure to characterize the quality of the estimation, and the
analysis holds for any $\rho<\infty$.

Assumption 1. At each communication round $t$, we assume that the gradient
aggregated from the selected subset of clients can provide a good
approximation of the gradient aggregated from the full set, i.e.,

$\displaystyle\left\|\sum_{i\in\mathbb{N}}\nabla
f_{i}(\bm{w}^{t})-\sum_{j\in\mathbb{S}^{t}}\theta_{j}^{t}\nabla
f_{j}(\bm{w}^{t})\right\|\leq\rho.$ (26)

Next, we outline the assumptions regarding local models $f_{1},\cdots,f_{N}$
and their gradients $\nabla f_{1}(\bm{w}^{t}),\cdots,\nabla
f_{N}(\bm{w}^{t})$, as stated in Assumption 2-5. These assumptions are
standard and widely used in the federated optimization literature [42, 43, 18,
27].

Assumption 2. $f_{1},\cdots,f_{N}$ are all $L$-smooth. Formally, for all
$\bm{v}$ and $\bm{w}$, we have

$\displaystyle f_{k}(\bm{v})\leq f_{k}(\bm{w})+(\bm{v}-\bm{w})^{T}\nabla
f_{k}(\bm{w})+\frac{L}{2}\|\bm{v}-\bm{w}\|_{2}^{2}.$ (27)

Assumption 3. $f_{1},\cdots,f_{N}$ are all $\mu$-strongly convex. Formally,
for all $\bm{v}$ and $\bm{w}$, it holds

$\displaystyle f_{k}(\bm{v})\geq f_{k}(\bm{w})+(\bm{v}-\bm{w})^{T}\nabla
f_{k}(\bm{w})+\frac{\mu}{2}\|\bm{v}-\bm{w}\|_{2}^{2}.$ (28)

Assumption 4. The variance of gradients for $f_{i}$ is bounded for
$i\in\mathbb{N}$. Formally, letting $\alpha_{i}^{t}$ be a data sample randomly
chosen from the local dataset of the client $i$, we have

$\displaystyle\mathbb{E}\left[\|\nabla
f_{i}(\bm{w}_{i}^{t},\alpha_{i}^{t})-\nabla f_{i}(\bm{w}_{i}^{t})\|\right]\leq
B_{2}.$ (29)

Assumption 5. The expected squared norm of gradients is uniformly bounded,
that is,

$\displaystyle\mathbb{E}\left[\|\nabla
f_{i}(\bm{w}_{i}^{t},\xi_{i}^{t})\|\right]\leq B_{3}.$ (30)

Furthermore, we introduce the term $\Gamma$ in Assumption 6 to quantify the
data heterogeneity among clients. If the data distribution among clients is
independently and identically distributed, then $\Gamma$ approaches zero as
the number of clients grows. Conversely, if the data distribution is
heterogeneous, the magnitude of $\Gamma$ reflects the degree of heterogeneity.

Assumption 6. Let $f^{\star}$ and $f_{i}^{\star}$ be the minimum values of $f$
and $f_{i}$, respectively. We consider the degree of data heterogeneity to be
bounded, that is,

$\displaystyle\Gamma=\|f^{\star}-\sum_{i=1}^{N}\theta_{i}f_{i}^{\star}\|\leq
B_{4}.$ (31)

Based on these assumptions, the proposed client selection strategy is
demonstrated to converge to the global optimal parameter $\bm{w}^{\star}$ at a
rate of $\mathcal{O}(1/t)$ for heterogeneous data settings, as stated in
Theorem 4. The proof is provided in the supplementary file. The convergence
rate $\mathcal{O}(1/t)$ is the same as existing client selection methods [27,
18, 43].

######  Theorem 4.

Under Assumptions 1-6, we have

$\displaystyle\mathbb{E}\|\bm{w}^{\star}-\bm{w}^{t}\|_{2}^{2}\leq\mathcal{O}(1/t)+\mathcal{O}(\rho).$
(32)

The term $\rho$ encodes the estimation error in Eq. (2). When more clients are
selected in a communication round, the subset of selected clients can better
approximate the data distribution of the full client set, then the term $\rho$
is smaller. Particularly, $\rho$ becomes zero when all clients are selected in
each round, i.e., $K=N$. We also analyze the impact of varying $K$ empirically
and propose an adaptive client selection method [44]. However, to reduce
communication overhead, the number of selected clients is usually less than
the total number of available clients, i.e., $K<N$. In this case, $\rho$
remains a non-vanishing term. In experiments, we observe that the proposed
client selection strategy guides the system to converge along a trajectory
similar to that of full client participation, but there exists a non-
diminishing solution bias dependent on $\rho$. This observation is consistent
with our theoretical analysis.

##  V Experiment

###  V-A Experimental Settings

We consider the cross-device federated learning scenario where a large number
of clients exist, each with limited computational power. In our experiments,
we fix the number of clients at $N=100$ and employ FedAvg [1] as the
aggregation method. The proposed client selection strategy is evaluated on two
datasets, FMNIST [45] and CIFAR-10 [46]. Following the approach in [18], we
opt for basic and small-scale models to accommodate the clients’ restricted
computational resources. Specifically, for the FMNIST dataset, we utilize a
multilayer perception (MLP) with two hidden layers as the global model. For
CIFAR-10, our global model adopts a convolutional neural network (CNN)
architecture consisting of three convolutional layers, with the outputs of
these layers fed into an MLP layer. Further details on training and
hyperparameter settings can be found in the supplementary file.

We explore four data partitioning methods, including an independently and
identically distributed (IID) approach and three heterogeneous approaches. In
the IID approach, we randomly partition the dataset into $N$ parts, with each
client assigned one part. We select $K=5$ clients in each round. Three
heterogeneous data partitioning approaches are as follows.

(i) 1 Shard Per Client (1SPC). Following the setting in [1], we divide the
dataset into $N$ shards, ensuring that data within a shard shares the same
label. We randomly assign a shard to each client so that a client has data
with only one label. This is the most heterogeneous case. In this case, we
select $K=10$ clients in each round.

(ii) 2 Shards Per Client (2SPC). Similar to the 1SPC setting, the dataset is
partitioned into $2N$ shards, where data within each shard shares the same
label. Clients are randomly assigned two shards, where most clients have data
with two labels (two shards with different labels), while a few clients have
data with only one label (two shards with the same label). In this case, we
set $K=5$ in each round.

(iii) Dirichlet Distribution (Dir). We partition the dataset based on a
Dirichlet distribution parameterized by a concentration variable $\alpha$,
where a smaller value of $\alpha$ indicates higher heterogeneity. In our work,
we set $\alpha=0.8$. Under this setting, clients have data with all labels,
but the data size of each label varies among clients. We determine the data
size of each label for each client following the analysis in [47, 18]. In this
case, we choose $K=5$ clients in each round.

Figure 2: Test accuracy on FMNIST and CIFAR-10 under the IID scenario.

Note that the 1SPC and 2SPC scenarios address label shift heterogeneity, while
the Dir scenario accounts for heterogeneity in both labels and dataset size.
Furthermore, apart from the assumption of a fixed number of clients ($K$) to
be selected, we also explore the impact of varying $K$ and propose an adaptive
method to determine its value. Details of the adaptive method can be found in
[44].

Figure 3: Test accuracy on FMNIST and CIFAR-10 under three heterogeneous data partitioning settings. TABLE I: Time overhead analysis on FMNIST in the 1SPC scenario. Method | Random | AFL | Powerd | DFairFed
---|---|---|---|---
Time (ms) For Client Selection Only | 0.038 | 0.153 | 0.016 | 0.529
Time (ms) For Completing a Communication Round | 2019 | 2044 | 2033 | 2472

We conduct the experiments five times using different randomized initial
conditions and present the average results. In our experiments, we set
$\delta=0.1$ , $\epsilon=0.3$, and $V=0.9$ for FMNIST, and $\delta=0.05$,
$\epsilon=0.05$, $V=0.7$ for CIFAR-10. We compare the proposed _LongFed_ with
three baseline methods: (1) the random selection strategy (Random) [1]; (2)
active client selection strategy (AFL), where clients with higher training
losses have higher probabilities of being selected [16]; (3) power-of-choice
strategy (Powerd), where clients are selected based on the power of $d$
choices load balancing strategy [17]. These methods are commonly used as
baselines in [18, 27]. Additionally, we compare our method with the full
client participation method (Full) with $K=100$.

###  V-B Experimental Results

####  V-B1 Convergence Analysis

The experimental results under the IID scenario are presented in Fig. 2, and
the results under three heterogeneous data partitioning methods are presented
in Fig. 3. In Fig. 2 and Fig. 3, the $x$ axis represents the communication
round, and the $y$ axis displays the test accuracy of the global model. For a
clearer comparison, we apply the moving average rule [48] with a sliding
window size of 10 to smooth the results.

Fig. 2 reveals that in the IID scenario, these methods achieve similar
performance. For three heterogeneous scenarios on the FMNIST dataset, as shown
in Fig. 3 (a), (b), and (c), respectively, the proposed method achieves
performance that is the most similar to that with full client participation.
Moreover, it exhibits faster convergence speed and superior test accuracy
compared to prior works. Notably, there is an approximate $20\%$ improvement
in the 1SPC scenario and an $8\%$ improvement in the 2SPC and Dir scenarios.
Similar trends are also observed for the CIFAR-10 dataset.

Figure 4: Visualization of the selected clients on the FMNIST dataset under
the 1SPC scenario. (a) is the t-SNE plot of client embeddings, where clients
are organized into 10 clusters. (b)-(f) display the results of the selected
clients using different client selection strategies, with the chosen clients
marked by black stars. Figure 5: Visualization of the selected clients on the
FMNIST dataset under the 2SPC scenario. (a) shows the t-SNE plot of client
embeddings, where the clustering pattern is not evident. In (b)-(f), circles
are drawn around the selected clients, indicating that clients covered by a
circle can be represented by the corresponding selected client.

####  V-B2 Time Overhead Analysis

We evaluate the time overhead of the proposed client selection strategy, and
the results are presented in Table I. The time overhead analysis is conducted
on the FMNIST dataset under the 1SPC scenario, with similar observations
across other scenarios. In Table I, the first row focuses on the time solely
for client selection within a communication round, while the second row
denotes the overall time required for a complete communication round,
including client selection, local updates, and global aggregation.

First, examining the time solely for client selection, our proposed method
exhibits only a marginal increase (less than 0.4ms) compared to existing
methods. This increment is acceptable in most real applications. In addition,
the time required for client selection (about 0.5ms) is almost negligible
compared to the total time required to complete a communication round (about
2000ms). This highlights that the majority of time is allocated to local
updates within clients. Second, examining the time required to complete a
round, our proposed strategy imposes only a modest additional computational
time (about 400 ms) compared to existing approaches. This is primarily because
evaluating the distance $\text{Dist}_{i,j}(t)$ in Eq. (5) is time-consuming,
especially when the dimension of $\nabla f_{i}(\bm{w}^{t})$ is high. The time
overhead can be reduced by employing a more efficient method for calculating
distances in high-dimensional gradient space. Nevertheless, the marginal
increase in time for the proposed strategy is justified when considering its
superior performance in client selection.

####  V-B3 Visualization of Client Selection Strategy

We provide visualizations of the selected clients to offer an interpretable
analysis of our proposed strategy. As shown in Fig. 4, in the 1SPC scenario on
the FMNIST dataset, baseline methods typically select two or more clients from
the same cluster. In contrast, the proposed _LongFed_ , as shown in 4 (e),
selects one client from each cluster, which effectively approximates the data
distribution of the full client set. Additionally, as shown in Fig. 4 (f), it
chooses a diverse subset of clients in the multi-round selection, adhering to
Principle II.

The results in the 2SPC scenario are illustrated in Fig. 5, where the
clustering pattern is not evident. For baseline methods, the circles around
selected clients often overlap and cover only a minority of clients. However,
in our proposed method, as shown in Fig. 5 (e), these circles cover the
majority of clients. This suggests that the selected clients provide a better
approximation of the full client set compared to the baseline approaches.
Moreover, as shown in Fig. 5 (f), the strategy selects a diverse subset of
clients across multiple rounds, satisfying Principle II. Visualization results
of other scenarios are provided in the supplementary file.

###  V-C Individual Fairness Analysis

We analyze the proposed individual fairness in terms of the trade-off factor
$V$, the similarity measure $\epsilon$, and the probability difference measure
$\delta$. The results are illustrated using the 2SPC scenario on the CIFAR-10
dataset, and similar trends are observed for other scenarios. The random
selection strategy is chosen as the baseline because it selects clients
randomly and without bias. The impact of these parameters is assessed through
two metrics: test accuracy and the standard deviation of the selection
probability $p_{i}$ between clients with similar data distributions, denoted
as $\sigma(t)$. To calculate $\sigma(t)$, we define $c_{i}(t)$ as the
accumulated number of selections for client $i$ during previous $t$
communication rounds. That is, $c_{i}(t)=\sum_{k=1}^{t}x_{i,k}$. For each
client $i$, we identify clients whose similarity with it is less than
$\epsilon$, denoted as
$\mathbb{I}_{i}(t)=\\{j\in\mathbb{N}\mid\text{Dist}_{i,j}(t)<\epsilon\\}$. We
then compute the average selection count among clients in $\mathbb{I}_{i}(t)$
by

$\displaystyle\overline{c}_{i}(t)=\frac{1}{|\mathbb{I}_{i}(t)|}\sum_{j\in\mathbb{I}_{i}(t)}c_{j}(t),$
(33)

and the standard deviation in their selection counts by

$\displaystyle\sigma(t)=\sqrt{\frac{1}{N}\sum_{i=1}^{N}\left[c_{i}(t)-\overline{c}_{i}(t)\right]^{2}}.$
(34)

A smaller $\sigma(t)$ indicates that the client selection strategy aligns more
closely with the individual fairness constraint.

Trade-Off Factor $V$. We vary the value of $V$ from $0.0$, $0.4$, $0.6$, and
$1.0$, and present the results in Fig. 6. First, we observe that the proposed
method with these four values converges faster than the random strategy and
achieves better performance. Among them, $V=0.6$ yields the best test
accuracy. This suggests that the individual fairness constraint improves the
overall performance. Second, the random strategy achieves the lowest standard
deviation $\sigma(t)$. The proposed method exhibits significantly larger
$\sigma(t)$ when $V=1.0$. This is because when $V=1.0$, our proposed method
prioritizes minimizing the estimation error in Eq. (2) and neglects the
fairness constraint. Furthermore, the standard deviation $\sigma(t)$ decreases
significantly when $V\leq 0.6$. It indicates that the constraint in Eq. (7)
indeed enhances the system fairness.

Similarity Measure $\epsilon$. We vary the value of $\epsilon$ across $0.05$,
$0.1$, $0.2$, and $0.3$, and observe the corresponding test accuracy and
standard deviation, as presented in Fig. 7. First, the results on test
accuracy indicate that the proposed method outperforms the random strategy
consistently across these $\epsilon$ values. On the other hand, a larger
$\epsilon$ in the proposed method corresponds to a smaller standard deviation.
Specifically, the results are comparable to the random selection strategy when
$\epsilon>0.05$, and even surpass it when $\epsilon=0.3$. This is attributed
to the fact that a larger $\epsilon$ enforces more clients to follow the
fairness constraint, thus the standard deviation obtained through the proposed
strategy gets closer to the random selection strategy.

Figure 6: Impact of the trade-off factor $V$. Figure 7: Impact of the
similarity measure $\epsilon$.

Probability Difference Measure $\delta$. We vary the value of $\delta$ across
$0.01$, $0.1$, $0.15$, and $0.2$, and observe the corresponding test accuracy
and standard deviation, as presented in Fig. 8. The results indicate that the
proposed method consistently performs better than the random selection
strategy across these $\delta$ values in terms of test accuracy. Moreover, a
smaller $\delta$ in the proposed method corresponds to a smaller standard
deviation. This is because a smaller $\delta$ narrows the range of probability
difference between clients with similar distributions, resulting in a smaller
standard deviation.

##  VI Conclusion

In our work, we introduce a novel long-term client selection approach for
federated learning, aiming to emulate the optimization trajectory achieved by
full client participation. We establish two guiding principles to steer the
client selection process effectively. We formulate the client selection
problem as a long-term optimization task, where the objective is to minimize
the estimation error in gradient space between the selected subset of clients
and the full client set. Besides, we impose the individual fairness constraint
to ensure similar selection frequencies among clients with similar data
distributions. Leveraging Lyapunov optimization techniques from control
theory, we transform this problem and propose a greedy algorithm to find
solutions efficiently. Experimental results demonstrate that our proposed
strategy closely approximates the performance achieved under full client
participation, with significant improvements over previous methods in terms of
both accuracy and fairness. Additionally, our method exhibits efficiency by
incurring minimal time overhead, which is often negligible when compared to
local training duration.

Figure 8: Impact of the probability difference measure $\delta$.

## References

  * [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in _Artificial intelligence and statistics_. PMLR, 2017, pp. 1273–1282.
  * [2] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, and et al., “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021.
  * [3] J. Wicaksana, Z. Yan, D. Zhang, X. Huang, H. Wu, X. Yang, and K. Cheng, “Fedmix: Mixed supervised federated learning for medical image segmentation,” _IEEE Transactions on Medical Imaging_ , 2022.
  * [4] Y. Tan, G. Long, J. Ma, L. Liu, T. Zhou, and J. Jiang, “Federated learning from pre-trained models: A contrastive learning approach,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 19 332–19 344, 2022.
  * [5] Y. Yin, Y. Li, H. Gao, T. Liang, and Q. Pan, “Fgc: Gcn-based federated learning approach for trust industrial service recommendation,” _IEEE Transactions on Industrial Informatics_ , vol. 19, no. 3, pp. 3240–3250, 2022.
  * [6] T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” in _ICC 2019-2019 IEEE international conference on communications (ICC)_. IEEE, 2019, pp. 1–7.
  * [7] L. Fu, H. Zhang, G. Gao, M. Zhang, and X. Liu, “Client selection in federated learning: Principles, challenges, and opportunities,” _IEEE Internet of Things Journal_ , 2023.
  * [8] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel, “Fairness through awareness,” in _Proceedings of the 3rd innovations in theoretical computer science conference_ , 2012, pp. 214–226.
  * [9] T. Huang, W. Lin, W. Wu, L. He, K. Li, and A. Y. Zomaya, “An efficiency-boosting client selection scheme for federated learning with fairness guarantee,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 7, pp. 1552–1564, 2020.
  * [10] H. Zhu, Y. Zhou, H. Qian, Y. Shi, X. Chen, and Y. Yang, “Online client selection for asynchronous federated learning with fairness consideration,” _IEEE Transactions on Wireless Communications_ , vol. 22, no. 4, pp. 2493–2506, 2022.
  * [11] Y. Shi, H. Yu, and C. Leung, “Towards fairness-aware federated learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2023.
  * [12] S. K. Shyn, D. Kim, and K. Kim, “Fedccea: A practical approach of client contribution evaluation for federated learning,” _arXiv preprint arXiv:2106.02310_ , 2021.
  * [13] Z. Liu, Y. Chen, H. Yu, Y. Liu, and L. Cui, “Gtg-shapley: Efficient and accurate participant contribution evaluation in federated learning,” _ACM Transactions on Intelligent Systems and Technology (TIST)_ , vol. 13, no. 4, pp. 1–21, 2022.
  * [14] G. Wang, C. X. Dang, and Z. Zhou, “Measure contribution of participants in federated learning,” in _2019 IEEE international conference on big data (Big Data)_. IEEE, 2019, pp. 2597–2604.
  * [15] Q. Sun, X. Li, J. Zhang, L. Xiong, W. Liu, J. Liu, Z. Qin, and K. Ren, “Shapleyfl: Robust federated learning based on shapley value,” in _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2023, pp. 2096–2108.
  * [16] J. Goetz, K. Malik, D. Bui, S. Moon, H. Liu, and A. Kumar, “Active federated learning,” _arXiv preprint arXiv:1909.12641_ , 2019.
  * [17] Y. J. Cho, J. Wang, and G. Joshi, “Towards understanding biased client selection in federated learning,” in _International Conference on Artificial Intelligence and Statistics_. PMLR, 2022, pp. 10 351–10 375.
  * [18] M. Tang, X. Ning, Y. Wang, J. Sun, Y. Wang, H. Li, and Y. Chen, “Fedcor: Correlation-based active client selection strategy for heterogeneous federated learning,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 10 102–10 111.
  * [19] D. Caldarola, M. Mancini, F. Galasso, M. Ciccone, E. Rodolà, and B. Caputo, “Cluster-driven graph federated learning over multiple domains,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021, pp. 2749–2758.
  * [20] A. Ghosh, J. Chung, D. Yin, and K. Ramchandran, “An efficient framework for clustered federated learning,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 19 586–19 597, 2020.
  * [21] M. Jiang, H. R. Roth, W. Li, D. Yang, C. Zhao, V. Nath, D. Xu, Q. Dou, and Z. Xu, “Fair federated medical image segmentation via client contribution estimation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 16 302–16 311.
  * [22] Y. H. Ezzeldin, S. Yan, C. He, E. Ferrara, and A. S. Avestimehr, “Fairfed: Enabling group fairness in federated learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 37, no. 6, 2023, pp. 7494–7502.
  * [23] T. Li, S. Hu, A. Beirami, and V. Smith, “Ditto: Fair and robust federated learning through personalization,” in _International Conference on Machine Learning (ICML)_. PMLR, 2021, pp. 6357–6368.
  * [24] W. Du, D. Xu, X. Wu, and H. Tong, “Fairness-aware agnostic federated learning,” in _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_. SIAM, 2021, pp. 181–189.
  * [25] L. S. Shapley, “A value for $n$-person games,” _Contributions to the Theory of Games_ , pp. 307–317, 1953.
  * [26] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, “Scaffold: Stochastic controlled averaging for federated learning,” in _International conference on machine learning_. PMLR, 2020, pp. 5132–5143.
  * [27] R. Balakrishnan, T. Li, T. Zhou, N. Himayat, V. Smith, and J. Bilmes, “Diverse client selection for federated learning via submodular maximization,” in _International Conference on Learning Representations_ , 2022.
  * [28] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” _ACM computing surveys_ , vol. 54, no. 6, pp. 1–35, 2021.
  * [29] H. Chen, T. Zhu, T. Zhang, W. Zhou, and P. S. Yu, “Privacy and fairness in federated learning: on the perspective of tradeoff,” _ACM Computing Surveys_ , vol. 56, no. 2, pp. 1–37, 2023.
  * [30] T. Li, M. Sanjabi, A. Beirami, and V. Smith, “Fair resource allocation in federated learning,” _arXiv preprint arXiv:1905.10497_ , 2019.
  * [31] M. Mohri, G. Sivek, and A. T. Suresh, “Agnostic federated learning,” in _International Conference on Machine Learning (ICML)_. PMLR, 2019, pp. 4615–4625.
  * [32] B. Mirzasoleiman, J. Bilmes, and J. Leskovec, “Coresets for data-efficient training of machine learning models,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 6950–6960.
  * [33] L. Huang, K. Sudhir, and N. Vishnoi, “Coresets for time series clustering,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 22 849–22 862, 2021.
  * [34] K. Killamsetty, D. Sivasubramanian, G. Ramakrishnan, and R. Iyer, “Glister: Generalization based data subset selection for efficient and robust learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 9, 2021, pp. 8110–8118.
  * [35] P. G. John, D. Vijaykeerthy, and D. Saha, “Verifying individual fairness in machine learning models,” in _Conference on Uncertainty in Artificial Intelligence_. PMLR, 2020, pp. 749–758.
  * [36] E. Benussi, A. Patane’, M. Wicker, L. Laurenti, and M. Kwiatkowska, “Individual fairness guarantees for neural networks,” in _Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence_ , 7 2022, pp. 651–658.
  * [37] M. Diehl, R. Amrit, and J. B. Rawlings, “A lyapunov function for economic optimizing model predictive control,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 3, pp. 703–707, 2010.
  * [38] M. Neely, _Stochastic network optimization with application to communication and queueing systems_. Springer Nature, 2022.
  * [39] A. Krause and D. Golovin, “Submodular function maximization.” _Tractability_ , vol. 3, no. 71-104, p. 3, 2014.
  * [40] G. Cornuejols, M. Fisher, and G. L. Nemhauser, “On the uncapacitated location problem,” in _Annals of Discrete Mathematics_. Elsevier, 1977, vol. 1, pp. 163–177.
  * [41] L. A. Wolsey, “An analysis of the greedy algorithm for the submodular set covering problem,” _Combinatorica_ , vol. 2, no. 4, pp. 385–393, 1982.
  * [42] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the convergence of fedavg on non-iid data,” in _International Conference on Learning Representations (ICLR)_ , 2020.
  * [43] Y. J. Cho, J. Wang, and G. Joshi, “Client selection in federated learning: Convergence analysis and power-of-choice selection strategies,” _arXiv preprint arXiv:2010.01243_ , 2020.
  * [44] Q. Li, X. Li, L. Zhou, and X. Yan, “Adafl: Adaptive client selection and dynamic contribution evaluation for efficient federated learning,” in _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2024, pp. 6645–6649.
  * [45] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” _arXiv preprint arXiv:1708.07747_ , 2017.
  * [46] A. Krizhevsky, G. Hinton, and et al., “Learning multiple layers of features from tiny images,” 2009.
  * [47] T. H. Hsu, H. Qi, and M. Brown, “Measuring the effects of non-identical data distribution for federated visual classification,” _arXiv preprint arXiv:1909.06335_ , 2019.
  * [48] C. Chiarella, X. He, and C. Hommes, “A dynamic analysis of moving average rules,” _Journal of Economic Dynamics and Control_ , vol. 30, no. 9-10, pp. 1729–1753, 2006.

##  VII Additional Details of The Proposed Optimization Function

###  VII-A Proof of Theorem 1

###### Proof.

Following the analysis in [32], based on the mapping
$\xi^{t}:\mathbb{N}\rightarrow\mathbb{S}^{t}$ that assigns each client
$i\in\mathbb{N}$ to a client $j\in\mathbb{S}^{t}$, we have

$\displaystyle\sum_{i\in\mathbb{N}}\nabla f_{i}(\bm{w}^{t})$
$\displaystyle\quad=\sum_{i\in\mathbb{N}}\left[\nabla f_{i}(\bm{w}^{t})-\nabla
f_{\xi^{t}(i)}(\bm{w}^{t})+\nabla f_{\xi^{t}(i)}(\bm{w}^{t})\right]$ (35)
$\displaystyle\quad=\sum_{i\in\mathbb{N}}\left[\nabla f_{i}(\bm{w}^{t})-\nabla
f_{\xi^{t}(i)}(\bm{w}^{t})\right]+\sum_{j\in\mathbb{S}^{t}}\theta_{j}^{t}\nabla
f_{j}(\bm{w}^{t}).$

Subtracting and taking the norm of the both sides, we have

$\displaystyle\big{\|}\sum_{i\in\mathbb{N}}\nabla
f_{i}(\bm{w}^{t})-\sum_{j\in\mathbb{S}^{t}}\theta_{j}^{t}\nabla
f_{j}(\bm{w}^{t})\big{\|}\leq\sum_{i\in\mathbb{N}}\big{\|}\nabla
f_{i}(\bm{w}^{t})-\nabla f_{\xi^{t}(i)}(\bm{w}^{t})\big{\|}.$ (36)

The upper bound is minimized when $\xi^{t}$ assigns each client
$i\in\mathbb{N}$ to the client in the subset $\mathbb{S}^{t}$ that has the
highest similarity in the gradient space. That is,

$\displaystyle\xi^{t}(i)\in\text{argmin}_{j\in\mathbb{S}^{t}}\big{\|}\nabla
f_{i}(\bm{w}^{t})-\nabla f_{j}(\bm{w}^{t})\big{\|},$ (37)

Therefore, we have

$\displaystyle\min_{\theta_{j}^{t}}\big{\|}\sum_{i\in\mathbb{N}}\nabla
f_{i}(\bm{w}^{t})-\sum_{j\in\mathbb{S}^{t}}\theta_{j}^{t}\nabla
f_{j}(\bm{w}^{t})\big{\|}\leq\sum_{i\in\mathbb{N}}\min_{j\in\mathbb{S}^{t}}\big{\|}\nabla
f_{i}(\bm{w}^{t})-\nabla f_{j}(\bm{w}^{t})\big{\|},$ (38)

which completes the proof. ∎

###  VII-B Proof of Theorem 2

###### Proof.

We first present the theoretical analysis for $Z_{i}(t)$. Based on Eq. (13),
we have

$\displaystyle Z_{i}(t+1)\geq Z_{i}(t)+x_{i,t}-x_{i\star,t}-\delta,$ (39)

which is equivalent to

$\displaystyle x_{i,t}-x_{i\star,t}-\delta\leq Z_{i}(t+1)-Z_{i}(t).$ (40)

Accumulating this inequality by $t$ for $t\in[1,T]$, we have

$\displaystyle\sum_{t=1}^{T}\left(x_{i,t}-x_{i\star,t}-\delta\right)\leq
Z_{i}(T)-Z_{i}(0)=Z_{i}(T).$ (41)

Taking the expectation operation $\mathbb{E}$ on both sides, we have

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left(x_{i,t}-x_{i\star,t}\right)-\delta\leq\frac{\mathbb{E}[Z_{i}(T)]}{T}.$
(42)

It is equivalent to

$\displaystyle\lim_{T\to+\infty}\frac{\mathbb{E}[Z_{i}(T)]}{T}=0\;\Rightarrow\;\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}(x_{i,t}-x_{i^{\star},t})-\delta\leq
0,\;\forall\,i\in\mathbb{N}.$ (43)

The proof is similar for $Q_{i}(t)$, and is omitted here. ∎

###  VII-C Proof of Theorem 3

###### Proof.

Based on Lemma 1, we accumulate the inequality for $Z_{i}(t)$ in Eq. (47) by
all clients and have

$\displaystyle\frac{1}{2}\sum_{i=1}^{N}Z_{i}^{2}(t+1)\leq\frac{1}{2}\sum_{i=1}^{N}\left[Z_{i}(t)+m_{i}(t)\right]^{2}=\frac{1}{2}\sum_{i=1}^{N}Z_{i}^{2}(t)+\frac{1}{2}\sum_{i=1}^{N}m_{i}^{2}(t)+\sum_{i=1}^{N}Z_{i}(t)m_{i}(t).$
(44)

Similarly, for $Q_{i}(t)$, we have

$\displaystyle\frac{1}{2}\sum_{i=1}^{N}Q_{i}^{2}(t+1)\leq\frac{1}{2}\sum_{i=1}^{N}\left[Q_{i}(t)+n_{i}(t)\right]^{2}=\frac{1}{2}\sum_{i=1}^{N}Q_{i}^{2}(t)+\frac{1}{2}\sum_{i=1}^{N}n_{i}^{2}(t)+\sum_{i=1}^{N}Q_{i}(t)n_{i}(t).$
(45)

Then, for the Lyapunov drift $\Delta\left(\Theta(t)\right)$, we have

$\displaystyle\Delta\left(\Theta(t)\right)$
$\displaystyle=L\left(\Theta(t+1)\right)-L\left(\Theta(t)\right)$ (46)
$\displaystyle=\frac{1}{2}\sum_{i=1}^{N}\left[Z_{i}^{2}(t+1)+Q_{i}^{2}(t+1)\right]-\frac{1}{2}\sum_{i=1}^{N}\left[Z_{i}^{2}(t)+Q_{i}^{2}(t)\right]$
$\displaystyle=\frac{1}{2}\sum_{i=1}^{N}Z_{i}^{2}(t+1)-\frac{1}{2}\sum_{i=1}^{N}Z_{i}^{2}(t)+\frac{1}{2}\sum_{i=1}^{N}Q_{i}^{2}(t+1)-\frac{1}{2}\sum_{i=1}^{N}Q_{i}^{2}(t)$
$\displaystyle\leq\frac{1}{2}\sum_{i=1}^{N}m_{i}^{2}(t)+\sum_{i=1}^{N}Z_{i}(t)m_{i}(t)+\frac{1}{2}\sum_{i=1}^{N}n_{i}^{2}(t)+\sum_{i=1}^{N}Q_{i}(t)n_{i}(t)$
$\displaystyle=\sum_{i=1}^{N}\left[Z_{i}(t)m_{i}(t)+Q_{i}(t)n_{i}(t)\right]+\frac{1}{2}\sum_{i=1}^{N}\left[m_{i}^{2}(t)+n_{i}^{2}(t)\right],$
$\displaystyle\leq\sum_{i=1}^{N}\left[Z_{i}(t)m_{i}(t)+Q_{i}(t)n_{i}(t)\right]+B,$

where $B$ is a positive value that acts as the upper bound for
$\frac{1}{2}\sum_{i=1}^{N}\left[m_{i}^{2}(t)+n_{i}^{2}(t)\right]$. ∎

######  Lemma 1.

Based on Eq. (13), we have

$\displaystyle
Z_{i}^{2}(t+1)\leq\left[Z_{i}(t)+m_{i}(t)\right]^{2},\quad\text{and}\quad
Q_{i}^{2}(t+1)\leq\left[Q_{i}(t)+n_{i}(t)\right]^{2}.$ (47)

###### Proof.

First, if $Z_{i}(t)+m_{i}(t)\leq 0$, then $Z_{i}(t+1)=Z_{i}(t)+m_{i}(t)$, and
we have

$\displaystyle Z_{i}^{2}(t+1)=\left[Z_{i}(t)+m_{i}(t)\right]^{2}.$ (48)

Next, if $Z_{i}(t)+m_{i}(t)<0$, then $Z_{i}(t+1)=0>Z_{i}(t)+m_{i}(t)$, and we
have

$\displaystyle Z_{i}^{2}(t+1)<\left[Z_{i}(t)+m_{i}(t)\right]^{2}$ (49)

Combining the two cases, we have

$\displaystyle Z_{i}^{2}(t+1)\leq\left[Z_{i}(t)+m_{i}(t)\right]^{2}$ (50)

The analysis is similar for $Q_{i}(t)$, and is omitted here. ∎

##  VIII Additional Details of The Convergence Analysis

###  VIII-A Proof of Theorem 4

###### Proof.

Our theoretical analysis is based on the FedAvg [1] method, and it can also be
extended to other federated optimization methods. To align with the approach
in [42], we unify the epochs of local training in clients and communication
rounds for parameter transmission between the server and clients into a single
dimension, indexed by $t=sE+k$. Here, $s$ denotes the index of the current
communication round, $E$ is the number of local epochs in a communication
round, and $k\in[1,E-1]$. If $t$ is divisible by $E$ (indicated as $t\mid E$),
it signifies the communication step where the server aggregates the model
parameters from the selected clients. Otherwise, it represents a local
training step for clients.

To show the convergence, we introduce an auxiliary variable $\bm{v}_{i}^{t}$
to signify the immediate result of a single stochastic gradient descent (SGD)
step in local updates. That is,

$\displaystyle\bm{v}_{i}^{t+1}=\bm{w}_{i}^{t}-\eta_{t}\nabla
f_{i}(\bm{w}_{i}^{t},\beta_{i}^{t}),\quad\text{and}\quad\bm{w}_{i}^{t}=\begin{cases}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\bm{v}_{i}^{t},\;&\text{if}\;t\mid
E,\\\ \bm{v}_{i}^{t},\;&\text{otherwise}.\end{cases}$ (51)

Based on $\bm{v}_{i}^{t}$ and $\bm{w}_{i}^{t}$, we define two virtual
sequences $\bar{\bm{v}}^{t}$ and $\bar{\bm{w}}^{t}$,

$\displaystyle\bar{\bm{v}}^{t}=\sum_{i}\theta_{i}^{t}\bm{v}_{i}^{t},\quad\text{and}\quad\bar{\bm{w}}^{t}=\sum_{i}\theta_{i}^{t}\bm{w}_{i}^{t}.$
(52)

and define

$\displaystyle\bar{\bm{g}}^{t}=\sum_{i=1}^{N}\theta_{i}^{t}\nabla
f_{i}(\bm{w}_{i}^{t})\quad\text{and}\quad\bm{g}^{t}=\sum_{i=1}^{N}\theta_{i}^{t}\nabla
f_{i}(\bm{w}_{i}^{t},\alpha_{i}^{t}).$ (53)

Therefore, we have

$\displaystyle\bar{\bm{v}}^{t+1}=\bar{\bm{w}}^{t}-\eta_{t}\bm{g}^{t}\quad\text{and}\quad\mathbb{E}(\bm{g}^{t})=\bar{\bm{g}}^{t}$
(54)

Note that

$\displaystyle\|\bar{\bm{w}}^{t+1}-\bm{w}^{\star}\|^{2}$
$\displaystyle=\|\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1}+\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\|^{2}$
(55)
$\displaystyle=\underbrace{\|\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1}\|^{2}}_{A_{1}}+\underbrace{\|\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\|^{2}}_{A_{2}}+\underbrace{2\cdot\langle\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1},\;\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\rangle}_{A_{3}}.$

That is, we can bound $\|\bar{\bm{w}}^{t+1}-\bm{w}^{\star}\|$ by obtaining the
upper bounds of the three terms, i.e., $A_{1}$, $A_{2}$, and $A_{3}$,
respectively.

Upper bound of Term $A_{1}$. Consider the last time of aggregation occurs at
the step $t_{0}=t+1-E$, and let
$\Delta\bm{v}^{\tau}_{i}=\bm{v}^{\tau+1}_{i}-\bm{v}^{\tau}_{i}$ be the updates
on $\bm{v}^{\tau}_{i}$ at the $\tau$-th step, then we have

$\displaystyle\bar{\bm{v}}^{t+1}=\bar{\bm{w}}^{t_{0}}+\frac{1}{N}\sum_{i=1}^{N}\sum_{\tau=t_{0}}^{t}\Delta\bm{v}^{\tau}_{i}.$
(56)

The term $A_{1}$ is equivalent to

$\displaystyle\|\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1}\|^{2}$
$\displaystyle=\left\|\left(\bar{\bm{w}}^{t_{0}}+\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\sum_{\tau=t_{0}}^{t}\Delta\bm{v}^{\tau}_{i}\right)-\left(\bar{\bm{w}}^{t_{0}}+\frac{1}{N}\sum_{i=1}^{N}\sum_{\tau=t_{0}}^{t}\Delta\bm{v}^{\tau}_{i}\right)\right\|$
(57)
$\displaystyle=\left\|\sum_{\tau=t_{0}}^{t}\left(\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\Delta\bm{v}^{\tau}_{i}-\frac{1}{N}\sum_{i=1}^{N}\Delta\bm{v}^{\tau}_{i}\right)\right\|$
$\displaystyle\leq\sum_{\tau=t_{0}}^{t}\left\|\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\Delta\bm{v}^{\tau}_{i}-\frac{1}{N}\sum_{i=1}^{N}\Delta\bm{v}^{\tau}_{i}\right\|.$

Note that for every local step $\tau\in(t_{0},t]$, we use the same
$\mathbb{S}^{t}$ to approximate the full gradients. Based on Assumption 6, we
have

$\displaystyle\left\|\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\nabla
f_{i}(\bm{v}^{\tau}_{i})-\frac{1}{N}\sum_{i=1}^{N}\nabla
f_{i}(\bm{v}^{\tau}_{i})\right\|$
$\displaystyle\leq\left\|\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\nabla
f_{i}(\bm{v}^{\tau}_{i})-\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\nabla
f_{i}(\bm{v}^{t_{0}}_{i})\right\|$ (58)
$\displaystyle\qquad+\left\|\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\nabla
f_{i}(\bm{v}^{\tau}_{i})-\frac{1}{N}\sum_{i=1}^{N}\nabla
f_{i}(\bm{v}^{\tau}_{i})\right\|$ (59)
$\displaystyle\qquad+\left\|\frac{1}{N}\sum_{i=1}^{N}\nabla
f_{i}(\bm{v}^{t_{0}}_{i})-\frac{1}{N}\sum_{i=1}^{N}\nabla
f_{i}(\bm{v}^{\tau}_{i})\right\|$ (60) $\displaystyle\leq
2LB_{3}\sum_{v=t_{0}}^{\tau}\eta_{v}+\rho$ (61)

where the first and third terms on the right-hand side are bounded by
Assumption 1 and Assumption 3, respectively. Therefore, the term $A_{1}$ is
bounded by

$\displaystyle\|\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1}\|^{2}$
$\displaystyle\leq\sum_{\tau=t_{0}}^{t}\left\|\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\Delta\bm{v}^{\tau}_{i}-\frac{1}{N}\sum_{i=1}^{N}\Delta\bm{v}^{\tau}_{i}\right\|$
(62)
$\displaystyle=\sum_{\tau=t_{0}}^{t}\eta_{\tau}\left\|\frac{1}{N}\sum_{i\in\mathbb{S}^{t}}\theta_{i}^{t}\nabla
f_{i}(\bm{v}^{\tau}_{i})-\frac{1}{N}\sum_{i=1}^{N}\nabla
f_{i}(\bm{v}^{\tau}_{i})\right\|$ $\displaystyle\leq
2LB_{3}\sum_{\tau=t_{0}}^{t}\sum_{v=t_{0}}^{\tau}\eta_{\tau}\eta_{v}+E\rho\eta_{\tau}$
$\displaystyle\leq LB_{3}E(E-1)\eta_{t_{0}}^{2}+E\rho\eta_{t_{0}}$

Upper bound of $A_{2}$. Under the Assumptions 1 and 2, based on the Lemma 1 in
[42], we have

$\displaystyle\mathbb{E}\|\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\|^{2}\leq(1-\eta_{t}\mu)\mathbb{E}\|\bar{\bm{w}}^{t}-\bm{w}^{\star}\|^{2}+\eta_{t}^{2}C_{1},$
(63)

where $C_{1}$ is a constant.

Upper bound of $A_{3}$.  Following the proof in [27], we have
$\mathbb{E}\left[\|\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\|\right]$ can be bounded
by a constant $C_{2}$, which is determined by the value of ${B_{3}}/{\mu}$.

Based on the above analysis, we have

$\displaystyle\mathbb{E}\|\bar{\bm{w}}^{t+1}-\bm{w}^{\star}\|^{2}$
$\displaystyle\leq\mathbb{E}\|\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1}\|^{2}+\mathbb{E}\|\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\|^{2}+2\cdot\mathbb{E}\left[\langle\bar{\bm{w}}^{t+1}-\bar{\bm{v}}^{t+1},\;\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\rangle\right]$
(64)
$\displaystyle\leq\left[LB_{3}E(E-1)\eta_{t_{0}}^{2}+E\rho\eta_{t_{0}}\right]^{2}+\left[(1-\eta_{t}\mu)\mathbb{E}\|\bar{\bm{w}}^{t}-\bm{w}^{\star}\|^{2}+\eta_{t}^{2}C_{1}\right]$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+2\left[LB_{3}E(E-1)\eta_{t_{0}}^{2}+E\rho\eta_{t_{0}}\right]\cdot\mathbb{E}\|\bar{\bm{v}}^{t+1}-\bm{w}^{\star}\|^{2}$
$\displaystyle\leq(1-\eta_{t}\mu)\mathbb{E}\|\bar{\bm{w}}^{t}-\bm{w}^{\star}\|^{2}+\left[LB_{3}E(E-1)C_{2}+\left(LB_{3}E(E-1)\eta_{t_{0}}+E\rho\right)^{2}\right]\eta_{t_{0}}^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+EC_{2}\rho\eta_{t_{0}}+C_{1}\eta_{t}^{2}$
$\displaystyle\leq(1-\eta_{t}\mu)\mathbb{E}\|\bar{\bm{w}}^{t}-\bm{w}^{\star}\|^{2}+\mathcal{O}(\rho)+\mathcal{O}(\eta_{t}^{2})+\mathcal{O}(\eta_{t_{0}}^{4}).$

By letting

$\displaystyle\eta_{t}=\frac{\beta}{t+\gamma},\quad\text{and}\quad\eta_{t_{0}}=\frac{\beta}{t+1-E+\gamma}$
(65)

with $\beta>{1}/{\mu}$ and $\gamma>0$ to achieve a diminishing learning rate,
we complete the proof.

∎

##  IX Additional Details of Experiment

###  IX-A Experimental Settings

Following [18], for the FMNIST dataset, we employ a multilayer perceptron with
two hidden layers as the global model, where the number of units in the two
hidden layers is 64 and 30, respectively. Additionally, we set the number of
local epochs to 3, the local batch size to 64, and the learning rate to
$0.005$. For the CIFAR-10 dataset, the architecture of the global model is a
convolutional neural network (CNN) with three convolutional layers having 32,
64, and 64 kernels, respectively. All kernels are designed with the size
$3\times 3$. Besides, the outputs of the convolutional layers are fed into an
MLP layer with 64 units. We set the number of local epochs to 5, the local
batch size to 128, and the learning rate to 0.05.

###  IX-B Visualization of Client Selection Strategy

The visualization results in Fig. 9 for the FMNIST dataset under the Dir
scenario are similar to the 2SPC scenario. Specifically, in Fig. 9 (b)-(d),
the circles around selected clients for baseline methods often overlap and
cover only a minority of clients. Moreover, as depicted in Fig. 9 (e), the
clients selected by our proposed method effectively cover the majority of
remaining clients. Additionally, as shown in Fig. 9 (f), the strategy selects
different clients in different rounds, adhering to the fairness constraint.

For further insights, we provide visualizations for the CIFAR-10 dataset in
the 1SPC, 2SPC, and Dir scenarios in Fig. 10, Fig. 11, and Fig. 12,
respectively. The conclusions drawn from the CIFAR-10 dataset align with those
from the FMNIST dataset.

Figure 9: Visualization of selected clients on FMNIST in the Dir scenario.
Figure 10: Visualization of selected clients on CIFAR-10 in the 1SPC scenario.
Figure 11: Visualization of selected clients on CIFAR-10 in the 2SPC scenario.
Figure 12: Visualization of selected clients on CIFAR-10 in the Dir scenario.