FAST: A Lightweight Mechanism Unleashing Arbitrary Client Participation in Federated Learning

1 Introduction

Federated Learning (FL) stands out as an emerging distributed machine learning framework where a large number of clients (i.e., computing nodes or devices) collaborate together to train a global model under the coordination of a central server [McMahan et al., 2017; Kairouz et al., 2021]. FL establishes itself as a powerful and flexible distributed platform, fostering collaboration among diverse clients characterized by substantial heterogeneity in data and system while preserving the privacy of raw data residing within each client. Hence, previous research endeavors have yielded a spectrum of efficient algorithms capable of achieving optimal convergence rates in theory and delivering great performance in some practical cases, in the presence of varying degrees of data heterogeneity [Kairouz et al., 2021; Zhao et al., 2018; Li et al., 2019; Karimireddy et al., 2020; Yang et al., 2020; Wang et al., 2021].

Nevertheless, realizing these favorable outcomes often hinges on the ideal system condition (i.e., ideal client participation). Specifically, most FL algorithms presume that client participation can be fully known, controlled, predicted or tracked. For example, [McMahan et al., 2017; Acar et al., 2021; Cho et al., 2023] assume partial client participation, where participation follows a known or controllable random process, such as ergodic, mixing, or independent processes. [Yang et al., 2022b; Gu et al., 2021; Yan et al., 2024] suppose that each client participates at least once within certain rounds.

In practice, however, each client's participation is highly dynamic, unknown and unpredictable [Bonawitz et al., 2019; Soltani et al., 2022] since clients frequently exhibit heterogeneous and dynamically shifting attributes, including computational power, communication capacity, and availability [Kairouz et al., 2021; Bonawitz et al., 2019; Yang et al., 2021]. These variations stem from the unique characteristics of each individual client and the dynamics of distributed learning systems. The dynamic, unknown, and unpredictable intricacies of client participation make it challenging and even impossible to ascertain a priori beforehand. Moreover, in some FL systems, such as cross-device FL, tracking client participation is either infeasible or not permitted [Kairouz et al., 2021]. We name these patterns as arbitrary client participation (ACP), reflecting its dependence on various system factors and the absence of explicit client tracking. Clearly, it leaves a substantial gap between algorithmic designs built on the premise of ideal client participation and the real-world applications of FL involving ACP. Also, without any conditions on client participation, a constant error arises for ACP as identified by the lower bound [Cho et al., 2022; Wang et al., 2020; Yang et al., 2022b], implying that no algorithm can achieve stationary point convergence in such case. This observation motivates us to pose the following fundamental question:

Question: Is it possible to design a lightweight mechanism for FL that can accommodate arbitrary client participation with theoretical guarantees?

In this paper, we show an affirmative answer to this question by proposing a new client participation mechanism for FL, denoted as Federated Averaging with SnapshoT (FAST). In contrast to most FL algorithms that necessitate ideal client participation in each communication round, FAST imposes a minimal requirement for client participation by intermittently implementing a snapshot step. This approach significantly diminishes the requirement for individual client participation, enabling ACP for the majority of the training process. We highlight our contributions as follows:

• Through extensive experiments, we reveal that the mismatch between ideal client participation in algorithm design and ACP in practice leads to severe performance degradation, especially in highly heterogeneous data scenarios. These phenomena are universal and extend beyond specific algorithms, as observed across multiple FL algorithms.
• To address this issue, we introduce FAST, a lightweight FL framework that requires only intermittent snapshot steps, enforcing fully random client participation during these steps while accommodating ACP within the system at all other times. This requirement applies to the client cohort rather than individual clients, allowing the participating group to be statistically representative. This is a milder condition compared to existing works (see Table 1), as it eliminates the need to track each client individually.
• Theoretically, we demonstrate that, under mild conditions, FAST can achieve a convergence rate of O(1/√mRK) for non-convex functions and ˜ O(1/R) for strongly-convex functions, where R is the number of communication rounds, K is the number of local steps, and m is the number of participating clients. These rates can match the rates of those under ideal client participation.
• Empirically, we further propose an adaptive strategy adjusting the snapshots' frequency dynamically and show that FAST can seamlessly integrate with other classic FL algorithms. Also, extensive experiments verify its effectiveness.

2 RelatedWork

Ideal Client Participation: full client participation and uniformly random client participation. In FL, client participation can be seen as a proxy for system heterogeneity. Due to the inherent complexity of real-world FL systems, explicitly modeling client participation proves challenging [Bonawitz et al., 2019; Yang et al., 2021]. Most existing FL algorithms often make an assumption about ideal client participation, typically relying on either full client participation [Gorbunov et al., 2021; Haddadpour et al., 2019; Lin et al., 2018; Wang and Joshi, 2019; Wang and Joshi, 2021; Yu et al., 2019] or uniformly random client participation [McMahan et al., 2017; Li et al., 2019; Karimireddy et al., 2020; Yang et al., 2020; Wu et al., 2023; Zhang et al., 2023; Wang et al., 2023; Liu et al., 2021; Jhunjhunwala et al., 2022; Grudzie´n et al., 2023]. This assumption requires that the server force all clients or at least uniformly and randomly sample a subset of clients to participate in each communication round. However, each client in FL is not entirely under the server's control. While the server may sample a client for a specific round, the client is highly likely not to participate due to various system factors such as drop-out, communication congestion, and other unpredictable factors [Kairouz et al., 2021; Yang et al., 2021]. It is worth noting that the server can invest additional resources to enforce uniform client participation, such as sampling more clients and extending the waiting time in each round. Yet, this approach leads to prolonged training times due to significant communication and computation overhead [Zhou et al., 2022]. As shown in [Luo et al., 2022], enforcing uniform client participation in every round by the server results in slow wall-clock time for FL training.

Controllable Client Participation. In addition to uniform client participation, another approach in the field involves modeling client participation as a controllable random process. One line of works utilizes predefined patterns or probabilities as the model of client participation [Chen et al., 2022; Yang et al., 2022b; Fraboni et al., 2021; Ruan et al., 2021; Gu et al., 2021; Avdiukhin and Kasiviswanathan, 2021; Wang and Ji, 2022; Koloskova et al., 2022]. The main idea is to allow asynchronous communication or fixed participation patterns (e.g., given probability) for clients to participate flexibly in training. However, existing works in this area often require extra assumptions, such as bounded delay and extra memory [Yang et al., 2022b; Ruan et al., 2021; Gu et al., 2021; Koloskova et al., 2022] and identical computation rate [Avdiukhin and Kasiviswanathan, 2021]. Moreover, several works explore some unique scenarios of client participation. For instance, [Chen et al., 2022] introduced a novel client subsampling scheme considering the importance of updates, relying solely on the norm of the update. [Malinovsky et al., 2023; Cho et al., 2023] investigated cyclic client participation. [Wang and Ji, 2022] provided a unified analysis for various client participation, including regularized, ergodic, independent, and mixing participation. The implicit assumption in these studies is that client participation is either known, largely controllable or adheres to predefined patterns. It is also noteworthy to mention a related work [Wang and Ji, 2023], wherein the estimated probability of each client's participation was used for a re-weighting process under unknown participation statistics. However, estimating such probabilities can be challenging in practice, such as cross-device FL [Kairouz et al., 2021].

Each of these approaches contributes to the diverse client participation strategies employed in FL. However, these strategies often necessitate adherence to specific patterns, which may not align seamlessly with practical FL scenarios characterized by highly dynamic, unknown and unpredictable nature. In this paper, we introduce a more general and practical pattern - arbitrary client participation (ACP). This implies that we do not impose any assumptions on client participation for the majority of training rounds. Our aim is to offer a flexible and realistic framework that accommodates various client participation scenarios in real-world FL applications.

Comparison of Related Work. We compare some related work about ACP in Table 1. Except for differences in participation and convergence rates, we still need to compare some important points. For FedAmplify [Wang and Ji, 2022], it can achieve the convergence rate of O( 1 √mKR ) only in some ideal cases (see Sec. 5 in [Wang and Ji, 2022]), and the server requires participation frequency for each client. For MIFA [Gu et al., 2021], each client needs to participate in training at least once in the one-time window. For Anarchic Federated Learning (AFL) [Yang et al., 2022b], the server needs to identify and store local models, and each client needs to participate in training at least once in the one-time window. In contrast, FAST framework has no extra assumptions for client participation and can achieve the ideal convergence rate. In addition, regular FAST does not demand to store extra information.

3 The Impact of Client Participation in FL

In this section, our goal is to investigate the impact of client participation on FL performance. We first introduce the fundamental formulation and the standard FedAvg. Subsequently, we examine FedAvg's performance across various client participation scenarios and show the adverse effects of different ACP. This highlights the gap between current algorithm designs and practical FL systems, thus motivating us to develop a new framework to accommodate ACP for FL.

3.1 Federated Learning and Federated Averaging

Problem Formulation. In a FL system with M clients, our goal is to minimize the objective function as:

where x is a d-dimension model parameter, M is the total number of clients, and Fi(x) := 1 |Si | ∑ξ∈Di F(x, ξ), ∀i ∈ [M] is the local loss function associated with local dataset Di that is IID sampled from one underlying distribution Pi. One of the critical features of FL is that each client has a subtly different local data distribution, i.e., Pi ̸= Pj if i ̸= j. This leads to heterogeneous (or Non-IID) data in the FL system, causing model drift and non-trivial performance degradation [Kairouz et al., 2021; Wang et al., 2021].

FedAvg Algorithm. The Federated Average (FedAvg) algorithm [McMahan et al., 2017] stands as the pioneering exemplar FL algorithm, inspiring numerous variants. Most of the FL algorithms follow the typical parameter-server architecture. In each communication round r ∈ [R], the server first selects a subset of clients to participate and broadcasts the current global model xr to each client. Upon receiving the global model, each participating client locally optimizes the loss function for some local steps using the local dataset without communication. For example, FedAvg takes K local steps using the vanilla stochastic gradient descent method. That is, xir,k+1 = xir,k - ηc∇Fi(xir,k , ξ ir,k ), k ∈ {0, · · · , K - 1} starting from xir,0 = xr where ξ ir,k ∼ Di. After local computation, the client sends the model update xir = xir,K to the server. At the server side, the server updates the global model by aggregating all the returned local model, i.e., xr+1 = 1 |Sr | ∑i∈Sr xir where Sr is the set of participated clients in the r-th round. Then, the next training round begins.

Undoubtedly, client participation, denoted as the set Sr, stands as a pivotal factor influencing the performance of FL models. While the majority of works in FL concentrate on mitigating data heterogeneity, the implications of client participation remain largely under-explored. To ensure convergence guarantees in FL algorithms, specific conditions must be imposed on client participation. Essentially, these algorithms necessitate a regulated form of client participation, such as participation through uniformly random sampling or a predetermined probability distribution, as detailed in Sec.2.

However, in real-world FL systems, client participation is inherently dynamic, prone to changes in each round [Bonawitz et al., 2019; Yang et al., 2021]. Even if the server employs an ideal sampling way, like uniformly random sampling, actual client participation remains unknown and largely uncontrollable. We term this as arbitrary client participation, signifying that Sr includes any sampling from the whole client set [M], thereby incorporating a diverse array of participation schemes. This process is determined by various inherent system factors, such as client failures and status changes [Bonawitz et al., 2019; Yang et al., 2021]. Hence, there exists a conflict between existing algorithm designs with ideal client participation and practical FL systems with ACP. This motivates us to explore the impact of ACP on FL algorithms' performance.

3.2 The Impact of Client Participation in FL

Arbitrary Client Participation Simulation. We delve into FedAvg's performance across four client participations characterized by distinct distributions: uniform, Beta, Gamma, and Weibull. Uniform client participation entails the random client selection from the entire client set, which is an idealized scenario in current FL algorithms. The Beta distribution is commonly employed to model events constrained within an interval. The Gamma distribution finds application in characterizing the frequency of a sequence of events associated with time or distance. The Weibull distribution is widely utilized in reliability or survival analysis [Lai et al., 2006]. In FL, the server often receives returns from clients within a given time window. Hence, it is reasonable to use uniform distribution as a baseline for ideal client participation. The latter three distributions are utilized to approximate different real-world scenarios, serving as representatives of ACP.

It is important to emphasize that our primary goal is not to precisely model client participation in FL but to explore the impact of different potential client participation scenarios. Also, we aim to highlight the adverse effects resulting from the mismatch between the ideal client participation used in the current algorithm design and ACP observed in practical FL.

Experiment Settings. We perform extensive experiments on Fashion-MNIST [Xiao et al., 2017] and CIFAR-10 [Krizhevsky et al., 2009], considering various Non-IID degrees and utilizing the four distributions to simulate different client participation. As shown in Table 2, we scrutinize the model performance using FedAvg. For each case, we record the last five results and report the mean and standard deviation of test accuracy. Here, we only show key findings and delegate the detailed settings and results for other datasets and algorithms to Sec. 5 and Appendix.

Observations. We have three key observations. First, FedAvg's performance is significantly influenced by client participation. As shown in Table 2, the model accuracy varies across different client participation cases, with uniform participation yielding the best performance among these four cases. This performance difference is substantial, ranging from 3% to 18%. These results align with practical FL simulations, where uncontrolled client participation induced by system heterogeneity leads to non-trivial model performance degradation [Yang et al., 2021]. Second, this performance degradation strongly correlates with the degree of Non-IID data. In our setting, we adopt the common approach of generating Non-IID data using the Dirichlet distribution [Acar et al., 2021], with the parameter α controlling the Non-IID degree. A smaller α corresponds to a higher Non-IID degree. For datasets with a higher degree of Non-IID data (smaller α), the model accuracy gap between uniform and other cases becomes more pronounced. For instance, on the Fashion-MNIST dataset, the model behaves similarly for different client participation cases with less Non-IID data (i.e., α = 1). However, as the Non-IID degree gets higher, such as α = 0.05, the accuracy gap between uniform and other participation could be as large as 18%. Third, the performance degradation for ACP (in the latter three cases) is universal, which extends beyond FedAvg, as evidenced by consistent observations across other FL algorithms such as FedProx and SCAFFOLD.

It is essential to note that occasional enforcement of uniform client participation in FL is feasible. For instance, the server can sample a larger number of clients and allocate sufficient time for each communication round, allowing ample clients to complete local computations. However, this strategy inevitably demands more resources and significantly extends the training time due to longer waiting time. Thus, it becomes unrealistic to enforce uniform client participation in every round. In addition, without imposing any constraints on client participation, FedAvg is theoretically incapable of asymptotically converging to a stationary point [Yang et al., 2022b; Yang et al., 2022a] and experiences non-trivial performance degradation in practice, as shown above. This realization motivates us to develop a lightweight client participation mechanism, aiming to achieve performance similar to that of uniform participation while imposing fewer constraints on FL systems.

4 Federated Average with Snapshot (FAST)

We first introduce a lightweight client participation mechanism - Federated Average with SnapshoT (FAST). Then, we

Algorithm 1 Federated Average with Snapshot (FAST)

• 1: Initialize: model parameter x0, learning rate ηc, local update steps K, communication rounds R, snapshot step interval I (or probability q).
• 2: for r = 0, . . . ,R-1 do
• 3:
• If r%I == 0 (with q = 1/I): ▶ Snapshot
• 4: Server enforces uniformly random clients Sr = S u r (|S u r | = m) to participate.
• 5: Otherwise: ▶ Arbitrary
• 6: Server allows arbitrarily random clients Sr = S a r (|S a r | = n) to participate.
• 7: Each client i ∈ Sr computes in parallel:
• 8: xir,k+1 = xir,k - ηc∇Fi(xir,k , ξ ir,k ), k ∈ [K]
• 9: Send xir = xir,k+1 to the server
• 10: Server aggregation: xr+1 = 1 |Sr | ∑ i∈Sr xir
• 11: end for
• 12: Note: Lines 7-10 can be replaced by any other FL algorithms.

provide the convergence analysis for non-convex and stronglyconvex cases. Lastly, to eliminate the need for predefining the snapshot frequency, we empirically propose a strategy to dynamically adjust the snapshot frequency for FAST.

4.1 AlgorithmDescription

As shown in Algo. 1, we introduce a lightweight client participation mechanism for FL. In each communication round r ∈ [R], we design two client participation options. If r%I == 0, the server takes a snapshot step that requires to enforce a round of uniform client participation denoted as client set Su r with cardinality m for that round, where I is a hyper-parameter to control the snapshot frequency. Otherwise, the server does not put any constraints and can accommodate any system heterogeneity by allowing ACP denoted as set Sa r with cardinality n. On the client side, each participating client takes K Stochastic Gradient Descent (SGD) steps and sends the returns back to the server, mirroring the procedure in FedAvg. Subsequently, after local computations, the server aggregates all the returns and updates the global model. Additionally, from a probabilistic perspective, in each round, there exist a probability q of enforcing snapshots and a complementary probability of 1 - q to permit ACP. Here q = 1/I can be regarded as the snapshot probability or frequency.

In general, the uniqueness of FAST is utilizing a snapshot step every I rounds by enforcing a round of uniform client participation. The trade-offs of the snapshot are discussed as follows: 1) Resources. Although uniform client participation is an ideal situation in FL, it can still be achieved in practice by using some strategies. For instance, the server can initially sample 1.3 × m clients and extend the waiting period [Bonawitz et al., 2019]. This approach would make uniformly random client participation hold statistically, and mirrors practical FL simulations, such as 11.6% dropout rate and an optimal waiting time [Yang et al., 2021]. Hence, enforcing uniform client participation is practical in reality. Unfortunately, this approach to achieve uniform participation consumes more resources, such as time and computation. However, in FAST, snapshots just occupy a small portion of entire training rounds, so FAST can save resources compared to completely uniform participation in other FL algorithms. 2) Benefits. By the snapshot, our FAST can simultaneously enjoy the optimal convergence rates as those with uniform client participation shown in Sec. 4.2 and achieve improved performance when compared with ACP shown in Sec. 5.

4.2 Convergence Analysis

We first state several standard assumptions commonly used in our work and other works about optimization and FL [Kairouz et al., 2021; Wang et al., 2021].

Assumption 1 (L-Lipschitz Continuous Gradient) For any x and y, there exists a constant L > 0 such that ∥∇F(x) -∇F(y)∥ ≤ L∥x - y∥ and ∥∇Fi(x) - ∇Fi(y)∥ ≤ L∥x - y∥.

Assumption 2 (Unbiased Stochastic Gradients with Bounded Variance) The stochastic gradient calculated by the client or server is unbiased with bounded variance: E[∇Fi(x, ξ)] = ∇Fi(x) and E[∥∇Fi(x, ξ)- ∇Fi(x)∥2 ] ≤ σ2 , where ξ is a data sample.

Assumption 3 (Bounded Gradient Dissimilarity) For any i ∈ [M], ∥∇Fi(x) -∇F(x)∥2 ≤ σ2G.

Next, we offer FAST's convergence under non-convexity.

Theorem 1 (Convergence of FAST for Non-convex Functions). Under assumptions 1, 2 and 3, supposing that the probability q ≥ (2LKηc-1)G2+2K2 σ2G G1+(2LKηc-1)G2-2LKηcG3+2K2 σ2G and the learning rate ηc ≤ min { 1 8LK , nq+m(1-q) 5mnLK }, then the sequence {xr} generated by FAST satisfies:

where ζ := F(x0) -F(x∗ ), x∗ is the optimal solution, and G1-3 are defined in Appendix.

With a proper learning rate, FAST achieves convergence rate:

Corollary 1 With ηc = O ( √mn √RK(nq+m(1-q)) ), the convergence rate of FAST is

The convergence error of FAST comprises three components: 1) optimization error depending on the initial point x0, 2) staerror arising from heterogeneous data and local updates in FL.

tistical error associated with stochastic gradient noise σ, and 3) Notably, the third error exhibits a quadratic relationship with the learning rate. Hence, the first two terms dominate when using a sufficiently small learning rate. With an appropriate learning rate, the convergence rate is O(√ nq+m(1-q) nmKR ) for a suitably large round R ≥ (mnK)3 [nq+m(1-q)]3 . In a special case (m = n), the convergence rate becomes:

Corollary 2 With m = n, FAST achieves convergence rate:

Remark 1 In non-convex functions, this sublinear convergence rate shows the speedup in terms of clients' number m and the local steps K, which matches the optimal convergence rate in FL with uniform client participation in every round [Karimireddy et al., 2020; Yang et al., 2020].

Remark 2 It is worth noting that there exists a requirement of the snapshot probability/frequency q (or I). Specifically, it depends on data heterogeneity in the FL system: q ≥ (2LKηc-1)G2+2K2 σ2G G1+(2LKηc-1)G2-2LKηcG3+2K2 σ2G =

1 1+(G1-2LKηcG3)/(2K2 σ2G+2LKηcG2-G2) . For every heterogeneous data in FL, we can choose a proper q such that it can converge at such an optimal rate. We list two special cases to show FAST's generalization. 1) σG → 0. If data is IID among clients, then q ≥ 0, meaning that we can always avoid using the snapshot step and set q = 0. This situation corresponds to traditional distributed learning where each client has access to a shared dataset or IID datasets. In such cases, the choice of which subset of clients participates is inconsequential, as the training data used remains statistically identical. 2) σG →∞. If data is extremely highly Non-IID, the lower bound of q will approach 1, requiring a high frequency of snapshots. In extreme cases, it might require uniform client participation in every round to guarantee convergence.

If we assume a strongly convex condition on the function, we can achieve a faster convergence rate.

Assumption 4 (Strong Convexity) For any x and y, Fi is µ-convex with a constant µ > 0, if Fi(y) ≥ Fi(x) + ∇Fi(x)T (y - x) + µ2 ∥y - x∥2 , ∀i ∈ [M].

Theorem 2 (Convergence of FAST for Strongly Convex Functions). Under assumptions 1,2,3 and 4, supposing that the learning rate 0 < ηc ≤ min { 1 20mLK , 1 20nLK } and the probability q ≥ 1 - ( µKηc-16L2K2 η2 c 4σ2G ), the sequence {xr} generated by FAST satisfies:

where κ = ∥x0 - x∗ ∥2 and x∗ is the optimal solution.

Corollary 3 For Theorem 2, supposing µ > 0, m = n, ηc ≤ 1 20mLK and R ≥ 20mL, we can obtain

where ˜ O(·) subsumes all log-terms and constants. Accordingly, FAST achieves a convergence rate of ˜ O(1/R).

Remark 3 In strongly-convex functions, FAST can achieve a faster convergence rate of ˜ O(1/R) compared to the nonconvex case. It is worth mentioning that this rate can match those achieved in FL with ideal client participation [Li et al., 2019]. In conjunction with Corollary 1, it is clear that, under appropriate hyper-parameter settings, FAST can achieve the same convergence rate under ACP as these FL algorithms with ideal client participation.

4.3 Adaptive FAST

As shown in Algo. 1, FAST introduces an extra hyperparameter, q (or I), representing the snapshot probability (or frequency). Obviously, the effective performance of our FAST is evidently contingent on the selection of an appropriate q, as indicated by the ablation study on q in Sec. 5. In practice, obtaining prior knowledge to consistently set the optimal q poses a challenge. To address this issue, we propose an adaptive strategy to dynamically update q as shown in Algo. 2.

Algorithm 2 Adaptive q in FAST

• 1: Initialize: q0 = 0, ∆= 0, λ(default = 1).
• 2: for round r = 0, 1, ...,R-1 do
• 3: Obtain accr from the FL system
• 4: ∆←∆-accr
• 5: qr+1 ←min(1,max(0, qr +λ∆))
• 6: ∆← accr
• 7: end for

In more detail, we initiate with q = 0 to refrain from enforcing client participation at the beginning of training procedure. Meanwhile, q is adjusted in each round based on the training accuracy difference ∆ between the current and previous rounds. When ∆ > 0, indicating a decrease in training accuracy compared to the last round, we increase q by

λ∆. This adjustment aims to increase the probability of uniform client participation, improving performance. Conversely, when ∆ < 0, signifying an increase in training accuracy in the current round, we decrease q by λ∆. This reduction aims to diminish the probability of uniform client participation, ensuring a more substantial contribution from arbitrary participation in the training process. Line 5 ensures that the frequency q stays within the range of [0,1]. For the selection of λ, we conduct a series of experiments to assess the performance under different λ. Our results show that the adaptive FAST is less sensitive to the choice of λ, and choosing a default λ = 1 works well under different settings provided in Sec. 5 and Appendix.

5 Experiments

We provide our experiment settings and main results in Sec. 5.1, while leaving other details to Appendix.

Datasets and Models. We employ Fashion-MNIST [Xiao et al., 2017] and CIFAR-10 datasets [Krizhevsky et al., 2009] for image classification tasks, and we utilize the Shakespeare dataset [Caldas et al., 2018] for the next character prediction task. For image classification tasks, we train convolutional neural network (CNN) models in our FL system, but the models are different for these two datasets, aiming to adapt to the characteristics of different tasks. For character prediction tasks, we train the Char-LSTM model. Comprehensive details regarding datasets and models can be found in Appendix.

FL System. Our FL system comprises 100 clients in total for Fashion-MNIST and CIFAR-10 and 139 clients for Shakespeare. In each round, only 10% clients are chosen to participate in training. 1) Data Heterogeneity. The experiments on Fashion-MNIST and CIFAR-10 adhere to balanced and Non-IID datasets, implying that each client possesses an equal number of data, yet label distributions differ across clients. To establish this setup, we leverage the FedLab [Zeng et al., 2023] for data partitioning and employ Dirichlet Distribution to generate label-based distributions for each client. By adjusting the concentration parameter α, we can control the Non-IID degree of data. Generally, a smaller α corresponds to higher data heterogeneity. Shakespeare dataset is naturally Non-IID, so we directly distribute each user's data to each client. 2) Client Participation. We employ four distributions (i.e., uniform, Beta, Gamma and Weibull) to simulate various participation. The uniform distribution serves as ideal client participation, and the other three distributions act as proxies for ACP. 3) Algorithms. We implement three baselines: FedAvg, FedProx, and SCAFFOLD. Here, we primarily present FedAvg's results, deferring other results to Appendix. When q = 0, FAST becomes the classic FedAvg under various ACP. When q = 1, it is the FedAvg under ideal client participation.

Note. For simplicity and clarity, we declare the following notations across all tables in this paper: a) Ada.(λ) means adaptive FAST with a fixed λ. (def.) means the default λ = 1. b) Ratio = Rounds with ACP Total rounds , representing the percentage of ACP. (1 - Ratio) represents the percentage of the snapshot enforcement. c) For A±B, A is the average of the last 5 test accuracy, and B is the standard deviation.

5.1 Experiment Results

In this subsection, we provide four key findings to validate our algorithm and support theoretical analysis.

1. FL Algorithms' Degraded Performance under ACP. In Sec. 4, we show the non-trivial performance degradation of FedAvg under ACP. Notably, this performance degradation is a universal phenomenon extending beyond FedAvg. This is evident in the FedProx results that reveal a discernible gap between ideal client participation (uniform distribution) and ACP (other three distributions), with this gap significantly impacted by the level of data heterogeneity. In Appendix, we present more similar findings for other FL algorithms.

1. Improved Performance of FAST under ACP. In Table 3, we present a comparison between FedAvg and FAST across various client participation and Non-IID scenarios, leading to three key findings: 1) FAST improves performance by increasing the snapshot frequency q across all tasks. We conducted experiments with different fixed values of q and observed that when q = 0.5, FAST nearly matches the test accuracy of FedAvg under ideal client participation. In other words, we can enforce uniform client participation in only half of the rounds, enabling ACP in the remaining rounds. 2) Adaptive FAST proves effective, showcasing an increased test accuracy with the least snapshots. For instance, in FashionMNIST with α = 0.05 and default λ = 1, FAST requires only 1 - 91.8% = 8.2% snapshot enforcement while elevating accuracy from 66.65% to 71.48% in the Gamma distribution. If we take a more aggressive λ = 7, the accuracy can be improved to 79.95%. 3) Adaptive FAST achieves a great balance between test accuracy and snapshot frequency. Across all cases in Table 3, the default adaptive strategy (Ada.(def.), with λ = 1) consistently requires less than 10% snapshots while delivering notable improvements.

3. Compatible FAST Framework to Integrate with Other FL Algorithms. We highlight that the client participation mechanism in FAST constitutes a general and compatible framework which can seamlessly integrate with other FL algorithms. To show this, we adopt two additional FL algorithms, FedProx and SCAFFOLD, utilizing the FAST client participation mechanism, referred to as FAST+.

Detailed experimental results are provided in Appendix. In general, we observe that, under ACP, the performance of FAST+ significantly surpasses that of FedProx and SCAFFOLD. These results hold for both fixed q and adaptive q. In specific cases, adaptive FAST+ achieves higher test accuracy than FAST+ with a fixed q when their individual proportions of ACP are approximately equal. In other words, adaptive FAST+ can attain higher test accuracy with a higher percentage of ACP (bigger Ratio or smaller q). These observations align with the results in Table 3 for FedAvg, demonstrating that the client participation mechanism in FAST is general and compatible with other FL algorithms.

4. Ablation Study for Hyper-parameters. We conducted extensive ablation experiments on FL and hyper-parameters of FAST, including α, distributions for modeling client participation, adaptive hyper-parameter λ, etc. Here, we specifically investigate the impact of λ as a key hyper-parameter in adaptive FAST. All other results are offered in Appendix.

In Appendix, we present the test accuracy for FashionMNIST with λ varying from 1 to 9. Overall, FAST's performance exhibits less sensitivity to the choices of different λ under distinct distributions. As increasing λ, the snapshot frequency rises, resulting in a decreased ratio. This indicates that the q increases with the increase of λ. However, we observe that the model performance remains stable. Notably, with our default choice of λ = 1, FAST attains good test accuracy with only a small percentage of snapshots. Across these three distributions, when λ = 1, we require less than 5% of snapshot enforcement, validating the effectiveness of adaptive FAST.

Acknowledgments

This work has been partially supported by the GWBC Award at RIT.