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

1 Introduction

• Unknown availability patterns and communication constraints make it difficult to identify the best achievable participation rate and a policy that realizes it.The motivating example assumes independent availability with P(A1 = 1) = 0.375 and P(A2 = 1) = 0.8, while the server can sample at most one client per round.Source: §1 · pp. 1–2
• F3AST adapts to unknown client-availability statistics and time-varying system capacity, with its long-term participation rate converging to one that minimizes a bound on global-model variance.The paper describes this behavior as asymptotically optimal.Source: §1 · p. 2
• F3AST is reported to achieve higher accuracy than state-of-the-art algorithms and more stable convergence on realistic tasks, including CIFAR100 and Shakespeare.The experiments also report reduced bias and more stable descent trajectories when F3AST is incorporated into algorithms that do not compensate for client-selection uncertainty.Source: §1 · p. 3

2.1 Federated Learning

• Federated learning repeatedly selects clients to train locally and aggregates their updates into a global model, but convergence is affected by heterogeneous, often non-i.i.d. client data.Prior convergence analyses typically assume any client can be sampled at any time.Source: §2.1 · p. 3
• Communication-reduction methods such as model compression are orthogonal to this work, which focuses on intermittently available clients.The text also notes hardware and device-count challenges for stateful methods such as SCAFFOLD and FEDDYN.Source: §2.1 · p. 3
• Availability may vary over time and the selection capacity may change, while practical patterns can be non-cyclic and client- or cluster-specific.Examples include access to power and available communication bandwidth.Source: §2.1 · pp. 3–4

2.2 Client sampling and averaging

• Client-selection strategies use data proportions or active-learning criteria such as update magnitude or client loss to choose among available clients.Aggregation alternatives include unweighted averaging, prior-update replacement, and methods trading communication or memory for stable convergence.Source: §2.2 · p. 4
• Prior intermittent-availability sampling work studies cyclic patterns and may produce biased models, with performance under non-cyclic availability unclear and no formal convergence guarantees reported.Asynchronous approaches instead use fixed policies based on client training speed and incorporate updates as they arrive or in privacy-preserving buffers.Source: §2.2 · p. 4

3.2 F3AST: Minimizing the sampling variance

• F3AST adapts client selection and aggregation to intermittent availability and time-varying communication constraints, learning a feasible participation rate that minimizes H(r).H(r) bounds the variance induced by the selection policy; F3AST’s global update is unbiased.Source: §3 · p. 4, §3.2 · pp. 6–7

3.1 Preliminaries

• The feasible long-term participation rates form a closed convex subset of the N-dimensional simplex, under a finite-state irreducible Markov model of feasible client sets.A rate component represents the fraction of time its client is selected; the feasible sets reflect both availability and communication constraints.Source: §3.1 · pp. 5–6

3.2 F3AST: Minimizing the sampling variance

• F3AST selects feasible clients using the gradient of H(r), updates its estimated participation rates by exponential smoothing, and uses those rates in an unbiased global-model update.When the round’s client limit is Kt, selection reduces to greedily choosing Kt available clients with the largest entries of −∇H(r).Source: §3.2 · pp. 6–7

3.2.1 Asymptotic optimality

• As β decreases, F3AST’s participation rate approaches a minimizer of H(r) over the feasible rate region R.The theorem states this result for a bounded set V and ϵ > 0, with T depending on ϵ and V.Source: §3.2.1 · p. 7

3.2.2 Bounding the global model variance

• Under Assumptions 1–4, Lemma 3.4 defines client-sampling variance for an achievable long-term participation rate, and Theorem 3.5 applies SGD with its attaining policy to the model after T steps.The assumptions specify smooth, strongly convex client losses, bounded gradient variance, and uniformly bounded expected stochastic-gradient norms.Source: §3.2.2 · p. 8
• The variance objective can be minimized over R even when full participation is infeasible or the rate region and its configuration-dependent policy are unknown; F3AST learns an asymptotically optimal policy.The paper also states that its unbiased-update and variance analysis applies to arbitrary feasible selection policies, extending beyond two specific sampling schemes.Source: §3.2.2 · p. 9

4.1 Datasets and models

• The evaluation uses Syn-hetic(1,1) for softmax regression, a 1M-parameter recurrent network for Shakespeare next-character prediction, and ResNet-18 with group normalization for CIFAR100.Shakespeare has 725 clients; CIFAR100 uses a realistic heterogeneous partition.Source: §4.1 · p. 9
• Five availability models cover always-available clients, homogeneous scarce availability, home-device availability, time-varying smartphone availability, and availability inversely related to client dataset size.The comparisons fix the communication constraint at M = 10 clients per round before varying M.Source: §4.1 · p. 10
• FedAvg and FedAdam use normalized client probabilities, and experiments also compare availability-aware versions that incorporate F3AST sampling and aggregation.Power-of-Choice is another baseline; stateful SCAFFOLD and FedDyn are excluded as inapplicable to cross-device settings.Source: §4.1 · pp. 10–11

4.2 Numerical results.

• On CIFAR100, F3AST achieves almost a 200% improvement in average accuracy over the last 100 rounds and exhibits more stable behavior.The experiments use the Home-devices availability model for this comparison.Source: §4.2 · p. 11
• F3AST stabilizes after the first 100 iterations on Shakespeare and Synthetic, while FedAvg and POC show high variability under time-varying client availability.The reported convergence plots average three runs in the appendix.Source: §4.2 · p. 11
• F3AST improves final accuracy over FedAvg on CIFAR100 and Shakespeare across all availability models, and over FedAdam in every model except Uneven, where accuracy is unchanged.The Uneven setting nevertheless has lower loss for F3AST than FedAdam.Source: Table 2 · p. 10, §4.2 · pp. 11–12

• F3AST is designed for federated systems with communication constraints and intermittently available clients.Source: §5 · p. 12
• The authors report accuracy superior to state-of-the-art federated methods and resilience in challenging system settings.Source: §5 · p. 12
• Future work includes studying clients grouped into clusters or classes and a wider range of communication constraints.Source: §5 · p. 12

Communication Constraints and Intermittent Client Availability”

• The appendix is organized into notation and definitions, extensions and problem variations, proofs, and experimental details.Source: Communication Constraints and… · p. 16

A Notation and Definitions

• The notation defines the client set U, sampled-client count K_t, availability process A_t, feasible client sets C_t, selected set S_t, and stationary distribution π.Source: A Notation and Definitions · p. 16
• The expected global update v_{t+1} is formed under desired distribution P, and z_{t+1} is the desired global model at the end of round t.Source: A Notation and Definitions · p. 16
• The appendix includes a frequently used symbols table and an update relation connecting w_{t+1}, w_t, and Δ_{t+1}.Source: Table 4 · p. 16, A Notation and Definitions · p. 17
• The generalized FedAvg procedure initializes local models from the current global model and defines client-local updates across rounds and iterations.Source: A Notation and Definitions · p. 16

B F3AST Extensions and Problem Variations.

• After a burn-in, the learned sampling rate stabilizes, and the asymptotic convergence rate O(1/TE) is unaffected by a nonconstant early rate.The convergence argument uses mixing properties of the availability and communication process.Source: B F3AST Extensions and Problem… · p. 17
• Client weights p_k can be interpreted as data shares across client clusters, making their tracking an estimate of time-varying class sizes.The appendix notes that efficient protocols can make this feasible.Source: B F3AST Extensions and Problem… · p. 17
• The sampling model can represent constraints such as selecting as many available clients as possible up to M or imposing minimum sampling requirements on user groups.Source: B F3AST Extensions and Problem… · p. 17
• The framework's fairness objective represents clients proportionally to dataset size; adapting it to other fairness metrics is left for future research.Source: B F3AST Extensions and Problem… · p. 17

C Proofs

• A fixed-policy procedure takes a target long-term rate and a configuration-dependent policy, selects feasible client sets, and outputs the final global model.Source: C Proofs · p. 18

C.1 Proof of Theorem 3.5

• The proof of Theorem 3.5 uses an unbiased global update and derives the variance incurred by the sampling policy and aggregation step, including importance-sampling terms.Source: §C.1 · p. 18
• The convergence proof bounds distance to the optimum using the full-participation convergence term plus an additional client-sampling variance term, then bounds expected final objective error.Source: §C.1 · p. 19

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

• Each selection indicator has mean r_i and variance r_i(1−r_i), providing the moments used in the sampling-variance calculation.The indicator is 1 when client i is selected and 0 otherwise.Source: §C.2 · p. 21
• For an attainable rate r, the lemma considers a static configuration-dependent policy f_r and the corresponding client-selection vector.The lemma is stated under Assumptions 1–4.Source: §C.2 · p. 22
• For uncorrelated or negatively correlated client availabilities, the lemma states that a policy exists with the specified variance property.The supplied statement does not include the displayed bound itself.Source: §C.2 · pp. 21–22
• The proof uses nonpositive off-diagonal selection covariances to bound the aggregate variance, with the diagonal terms given by Bernoulli variances.The covariance inequality is stated for uncorrelated or negatively correlated availabilities.Source: §C.2 · pp. 21, 23

C.3 Proof of Theorem 3.3

• The proof uses fluid sample paths whose limiting trajectories approach r*, the minimizer of H(r).The theorem statement bounds the time needed to approach the minimizer as a function of ε and V.Source: §C.3 · p. 23

D Experiments details

• Experiments use β = O(1/T) = 0.001; one training round takes 8 GPU seconds on CIFAR100, 67 on Shakespeare, and 0.57 on Synthetic(1,1).The reported runs used AMD Vega 20 (ROCm) cards.Source: D Experiments details · p. 24

D.1 Datasets

• The synthetic dataset is split evenly across 100 clients, while Shakespeare clients have at most 128 sentences each.Shakespeare is used for next-character prediction.Source: §D.1 · p. 24

D.2 Federated Datasets Details

• Table 5 summarizes the number of clients and total samples for the federated datasets.The supplied passages do not include the table's cell values.Source: §D.2 · p. 24, Table 5 · p. 25

D.3 Models

• The Shakespeare model embeds characters in eight dimensions, then applies two LSTMs and a dense layer; ResNet-18 uses group instead of batch normalization.The Shakespeare architecture is presented in Table 6.Source: §D.3 · p. 24, Table 6 · p. 25

D.4 Availability models

• The Home-devices and Smartphones availability models use lognormal client speeds, while the third model samples a sine-wave availability function at 24 times.The lognormal parameters are (0, 0.5) for Home-devices and (0, 0.25) for Smartphones.Source: §D.4 · p. 25

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

• F3AST achieves smaller loss and more stable convergence across datasets, and its accuracy varies less across three independent runs.The passages identify Figures 3 and 4 as the accuracy and loss comparisons, respectively.Source: §D.5 · p. 25, Figure 3 · p. 25, Figure 4 · p. 26

D.6 Varying the communication constraint.

• F3AST achieves equal or higher accuracy than competitors across communication levels, and its gap widens as more clients are selected.The authors attribute this to its greedy marginal-utility selection and balanced sampling rate; the other policies may over-select available users.Source: Figure 5 · p. 26, §D.6 · p. 26

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

• F3AST consistently improves both unweighted and weighted accuracy across availability models and datasets.Figure 6 presents accuracy and relative gains over FedAvg and FedAdam.Source: Figure 6 · p. 27
• User-averaged metrics average local test results across users, whereas sample metrics average over test samples.The authors note that uniform performance across users is desired even when some users have few datapoints.Source: §D.7 · p. 27
• For CIFAR100, user and sample accuracy coincide because the data is split evenly across clients, so the user-accuracy results are omitted.Source: §D.7 · p. 27

D.8 Varying heterogeneity in the synthetic dataset.

• F3AST is more accurate than FedAvg for every tested synthetic-data heterogeneity parameter α under the Smartphones setting.Table 9 reports test accuracy for the synthetic(α, α) dataset in that setting; no cell values are supplied here.Source: §D.8 · p. 27, Table 9 · p. 28
• The reported data heterogeneity comes from unequal data amounts and heterogeneous client distributions.Source: §D.8 · p. 27
• F3AST addresses this heterogeneity by selecting clients whose participation is far from the desired rate.Source: §D.8 · p. 27