PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Client Selection for Federated Learning with Volatile Clients

Tiansheng Huang, Weiwei Lin, Li Shen, Keqin Li, Albert Y. Zomaya

arXiv:2011.08756v3cs.LGcs.DC

TL;DR

Volatile client failures make selection consequential: favoring stable clients may increase effective participation, while selection bias may hurt model performance. The paper proposes E3CS, a stochastic selection scheme that balances participation and fairness. In experiments, stable-client selection accelerated early accuracy growth, while the most unfair scheme had the lowest final test accuracy.

  • Problem

    Client selection in volatile FL must balance effective participation, which can support faster convergence, against selection bias that may harm model performance.

    Source: B. Motivations · p. 2

  • Method

    E3CS is an efficient stochastic client-selection algorithm for the volatile FL problem, designed around a practical fairness quota.

    Source: C. Contributions · p. 2, §VII · p. 15

  • Results

    FedCS(A) achieved the fastest early accuracy growth, while FedCS had the lowest final test accuracy and E3CS-0 the second-lowest among evaluated methods.

    Source: C. Real Training on Public Dataset · pp. 13–14

  • Takeaways & Limitations

    E3CS’s fairness quota is designed to tame the tradeoff between training convergence speed and final model accuracy.

    Source: §VII · p. 15

    The study focuses on client selection while fixing the local-update solution; jointly optimizing local updates and selection remains future work.

    Source: §VII · p. 15

Abstract

from arXiv · show

Federated Learning (FL), arising as a privacy-preserving machine learning paradigm, has received notable attention from the public. In each round of synchronous FL training, only a fraction of available clients are chosen to participate, and the selection decision might have a significant effect on the training efficiency, as well as the final model performance. In this paper, we investigate the client selection problem under a volatile context, in which the local training of heterogeneous clients is likely to fail due to various kinds of reasons and in different levels of frequency. {\color{black}Intuitively, too much training failure might potentially reduce the training efficiency, while too much selection on clients with greater stability might introduce bias, thereby resulting in degradation of the training effectiveness. To tackle this tradeoff, we in this paper formulate the client selection problem under joint consideration of effective participation and fairness.} Further, we propose E3CS, a stochastic client selection scheme to solve the problem, and we corroborate its effectiveness by conducting real data-based experiments. According to our experimental results, the proposed selection scheme is able to achieve up to 2x faster convergence to a fixed model accuracy while maintaining the same level of final model accuracy, compared with the state-of-the-art selection schemes.

I. INTRODUCTION

FL keeps training data on clients while coordinating local updates and server aggregation; this paper asks how client selection under volatile participation can balance effective updates and fairness.

A. Background D

B. Motivations

  • Volatile participation creates a tradeoff: selecting stable clients may accelerate convergence, while selection bias may harm model performance.The paper investigates balancing effective participation, measured by returned models per round, with selection fairness.Source: B. Motivations · pp. 1–2

C. Contributions

  • E3CS addresses volatile FL through deadline-based aggregation and a decomposed optimization problem, then relaxes client selection using empirical observations.The paper presents E3CS as an efficient stochastic selection algorithm for the resulting problem.Source: C. Contributions · p. 2

II. RELATED WORKS

  • Prior work explored data exchange and federated augmentation to address non-iid data, while noting that GAN training for augmentation requires client seed samples.Source: A. Statistical Heterogeneity · p. 3

A. Statistical Heterogeneity

  • Statistical heterogeneity makes clients’ local optima differ and has been reported to affect FL convergence; prior work also reported non-iid accuracy losses.Source: A. Statistical Heterogeneity · pp. 2–3

B. System Heterogeneity

The paper extends system heterogeneity to include clients’ differing volatility, then situates client selection amid concerns about participation bias and fairness. It distinguishes its selection fairness objective from agnostic and good-intent fairness objectives.

B. System Heterogeneity

  • System heterogeneity should include client volatility, beyond differences in local training epochs, because volatility can affect overall training performance.The paper describes client volatility as an additional aspect of system heterogeneity.Source: B. System Heterogeneity · p. 3

C. Client Selection

  • The paper adopts stochastic Exp3 rather than deterministic UCB to handle selection fairness without dynamic queues.The cited prior approaches and used dynamic queues.Source: C. Client Selection · p. 4

D. Agnostic/Fair Federated Learning

  • This paper retains the general weighted-average loss objective and distinguishes selection fairness from good-intent fairness, which seeks more uniform client training losses.Selection fairness is used to minimize average loss, whereas good-intent fairness aims to make training loss more uniform across clients.Source: D. Agnostic/Fair Federated Learning · pp. 4–5

III. A DEADLINE-BASED AGGREGATION MECHANISM

The paper uses a fixed deadline to bound each FL round and aggregate models that arrive in time. Its formulation models client failures and selection constraints, and modifies aggregation to account for unsuccessful participation.

III. A DEADLINE-BASED AGGREGATION MECHANISM

  • A fixed aggregation deadline prevents perpetual waiting; the server stops ongoing training or transmission and drops models arriving after the deadline.Valid returned models are then aggregated using FedAvg or another aggregation scheme.Source: §III · p. 5

A. Basic Assumption and Global Problem

  • Client success is represented by a binary status, while each round selects exactly k of K clients.The selection set is constrained to have cardinality k.Source: A. Basic Assumption and Global Problem · p. 6
  • The global problem jointly optimizes local updates and client selection to minimize average empirical loss, with unsuccessful or unselected clients replaced by the current global model in aggregation.The modified aggregation operation differs from the original FedAvg formulation, which replaces only unselected clients.Source: A. Basic Assumption and Global Problem · p. 6

B. Alternative Optimization

The authors decompose the global optimization into client-selection and local-update blocks, then focus on selection under volatility. They reformulate selection as probability allocation and relax it using effective participation and fairness considerations.

B. Alternative Optimization

  • Alternating minimization separates client selection from local updates; the paper focuses on the selection subproblem while relying on existing solutions for local updates.Prior work addresses standard local-update optimization for system and statistical heterogeneity.Source: B. Alternative Optimization · p. 6

C. Stochastic Optimization of Client Selection Sub-problem

  • Multinomial sampling without replacement converts client selection into probability allocation while selecting exactly k clients and assigning client i selection probability p_i,t.The allocation satisfies the stated probability constraints.Source: C. Stochastic Optimization of Client… · pp. 6–7

D. Problem Relaxation based on Empirical Findings

  • The selection objective includes expected cumulative effective participation, the expected number of successfully returned post-trained models, because failures reduce models available for aggregation.The authors note that a larger number of aggregated models can benefit learning in the volatile setting.Source: D. Problem Relaxation based on… · p. 7
  • Selection fairness reserves at least σ_t selection probability for each client, while larger σ_t makes selection more even and σ_t = k/K yields uniform sampling.The quota trades selection skewness against training efficiency, which can be promoted by favoring clients with higher success rates.Source: D. Problem Relaxation based on… · pp. 7–8
  • Because client success status is unknown before each round, the relaxed selection problem cannot be solved offline and motivates an online adversarial-bandit scheduling solution.Source: D. Problem Relaxation based on… · p. 8

V. SOLUTION AND ALGORITHMS

E3CS adapts Exp3 to select multiple clients while incorporating a minimum selection probability for fairness. Its allocation handles probability overflow by capping weights while preserving weight-based allocation.

A. Preliminary Introduction to Canonical Exp3

  • Canonical Exp3 uses an unbiased reward estimator and exponential weights to favor arms with higher estimated rewards.The estimator satisfies E[ˆx_i,t] = x_i,t.Source: A. Preliminary Introduction to… · p. 8

B. EXP3 with Multiple Play and Fairness Constraint

  • E3CS adapts Exp3’s single-arm selection to multiple clients and incorporates a minimum selection probability for fairness.The canonical Exp3 scheme cannot select multiple arms per round or guarantee a constant minimum probability for each arm.Source: A. Preliminary Introduction to… · p. 8, B. EXP3 with Multiple Play and… · p. 8
  • E3CS modifies the exponential-weights update using learning rate η and the set of clients whose probabilities overflow.The passage points to the regret proof in Appendix B for the reason for this modification.Source: B. EXP3 with Multiple Play and… · p. 8
  • The allocation reserves σ_t probability for each client, then distributes the remaining k−Kσ_t according to client weights.The allocation must sum to k while meeting the expected fairness constraint.Source: B. EXP3 with Multiple Play and… · p. 8
  • A client’s probability can exceed 1 when its exponential weight is too large; E3CS calls this probability overflow.The algorithm caps overly large weights and chooses α_t so every allocated probability remains at most 1.Source: B. EXP3 with Multiple Play and… · pp. 8–9

C. Algorithm

E3CS initializes client weights, allocates selection probabilities, samples clients without replacement, and updates the model and weights after local training and aggregation.

C. Algorithm

  • E3CS samples k clients without replacement from the probability allocation returned by ProbAlloc.The algorithm initializes all client weights to 1 in the first round.Source: C. Algorithm · p. 9
  • Selected clients train on the global model, and successful returns are aggregated while missing or unsuccessful returns are replaced by the global model.The server waits until the deadline before aggregation.Source: C. Algorithm · pp. 9–10
  • After aggregation, E3CS updates its client expectations and calls ProbAlloc to return selection probabilities and the overflowed-client set.The weight update follows the same estimator and exponential-weights approach described earlier.Source: C. Algorithm · pp. 9–10

D. Theoretical Regret Guarantee

The regret analysis compares E3CS’s expected cumulative effective participation with an optimal allocation. The stated boundary cases connect the fairness quota to regret and canonical single-play Exp3.

D. Theoretical Regret Guarantee

  • The regret of E3CS is defined as the performance gap between its expected cumulative effective participation and the optimal solution’s.The optimal allocation reserves σ_t probability for each client and allocates the residual k−Kσ_t optimally.Source: D. Theoretical Regret Guarantee · p. 10
  • Theorem 1 states an upper bound on E3CS regret.The supplied passage introduces the bound but does not include its expression.Source: D. Theoretical Regret Guarantee · p. 10
  • When σ_t = k/K, regret is zero; when σ_t = 0, the regret bound is k times the canonical single-play Exp3 bound.At σ_t = k/K, both solutions reduce to even random selection among clients.Source: D. Theoretical Regret Guarantee · p. 10

VI. EXPERIMENTS

The experiments evaluate the proposed client-selection solution using numerical simulation and real training on two public datasets.

VI. EXPERIMENTS

  • Experiments use numerical simulation and real training on EMNIST-Letter and CIFAR-10.The passage identifies these as iconic public datasets.Source: §VI · p. 10

A. Setup

The experiments model volatile, heterogeneous clients and compare selection schemes under different fairness settings. The simulations show how selection fairness and effective participation vary across schemes and quotas.

A. Setup

  • Simulations select 20 of 100 clients, with success-rate classes 0.1, 0.3, 0.6, and 0.9, independently assigned training epochs, and iid or non-iid data settings.Source: A. Setup · pp. 10–11
  • Baselines were FedCS, Random, and pow-d; E3CS-0 disables the fairness constraint, while E3CS-inc sets its quota to zero through the first quarter of training.E3CS-inc raises the quota to k/K after T/4.Source: A. Setup · p. 11

B. Numerical Simulation

  • Across 2,500 rounds, E3CS-0 misselected sub-optimal classes only dozens of times and spread probability across the 25 highest-success Class 4 clients.FedCS instead repeatedly selected the same 20 of 25 Class 4 clients.Source: B. Numerical Simulation · pp. 11–12, Figure 3 · p. 12
  • Selection fairness ranks Random > E3CS-0.8 > pow-d > E3CS-0.5 > E3CS-0 > FedCS; schemes favoring Class 4 can maximize CEP while reducing fairness.Source: B. Numerical Simulation · p. 12
  • A larger constant fairness quota is associated with a lower converged success ratio across E3CS schemes, while E3CS variants other than E3CS-inc share similar convergence trends.Fig. 4 plots communication rounds against success ratio and cumulative effective participation for different schemes.Source: B. Numerical Simulation · p. 12, Figure 4 · p. 12
  • E3CS-inc’s success ratio drops at round 625 (T/4) and eventually converges to Random’s as T grows; pow-d maintains low CEP and success ratio.The passage attributes pow-d’s pattern to its tendency to select clients more likely to fail.Source: B. Numerical Simulation · p. 13

C. Real Training on Public Dataset

Real-data experiments examine convergence and final accuracy across selection schemes, while the conclusion frames client selection as a tradeoff between effective participation and fairness. The paper proposes E3CS with a fairness quota to manage that tradeoff.

C. Real Training on Public Dataset

  • High cumulative effective participation (CEP) accompanies faster initial accuracy growth, especially in non-iid settings and on the harder CIFAR-10 task.FedCS(A) grows accuracy fastest initially; the gap between FedCS(A) and pow-d(A) expands under non-iid training.Source: C. Real Training on Public Dataset · pp. 13–14
  • CEP’s convergence-speed advantage diminishes later: fairer Random(A) gradually catches up with and eventually dominates FedCS(A).A similar pattern is reported for FedProx-based training.Source: C. Real Training on Public Dataset · p. 14
  • At convergence, FedCS has the lowest final test accuracy, while E3CS-0 has the second-lowest among the evaluated methods.The paper characterizes both schemes as relatively unfair.Source: C. Real Training on Public Dataset · p. 14
  • E3CS-inc sets σt = 0 during the first T/4 rounds, disregarding fairness and focusing on increasing CEP, because CEP supports faster initial convergence while fairness matters more near convergence.Source: C. Real Training on Public Dataset · p. 14
  • E3CS-inc achieves promising first-stage convergence speed without an undesirable drop in final test accuracy.The experiments cover EMNIST-Letter and CIFAR-10.Source: C. Real Training on Public Dataset · p. 15
  • The experiments vary selection cardinality k across 10, 20, and 30; this analysis is moved to Appendix C.Source: C. Real Training on Public Dataset · p. 15

VII. CONCLUSION AND FUTURE PROSPECT

  • The conclusion identifies a tradeoff between cumulative effective participation and fairness, which corresponds to a tradeoff between convergence speed and final model accuracy.E3CS is presented as a stochastic selection algorithm with a practical fairness-quota setting to manage it.Source: §VII · p. 15
  • The optimization fixes the local-update subproblem while optimizing selection; joint optimization of the coupled components is left for future work.Source: §VII · p. 15

APPENDIX A BASELINE DESCRIPTION

The appendix describes three client-selection baselines and lists preliminary facts used in the proof. Its proof outline names upper- and lower-bound steps for E.

APPENDIX A BASELINE DESCRIPTION

  • FedCS schedules faster clients for more successful returns before a deadline; here it is assumed to select clients with the highest success rates using full information.The baseline is adapted to the volatile setting described in the passage.Source: Appendix A · p. 16
  • Random selects a fraction of clients uniformly, while pow-d samples a candidate set and selects k clients with the highest reported local loss.The pow-d comparison assumes clients can report losses successfully but may drop out during training.Source: Appendix A · p. 16

A. Preliminary Facts

  • The proof preliminaries identify the weight update, exponential Taylor-series facts, probability allocation, and unbiased estimator used in subsequent reasoning.Source: A. Preliminary Facts · p. 16
  • The listed inequality fact is weighted AM-GM for nonnegative values and weights summing to one.Source: A. Preliminary Facts · p. 16
  • The proof outline names upper- and lower-bound sections for E and indicates that it takes expectations and combines earlier facts.Source: B. Upper Bound of E · p. 17

D. Combining the bounds

The passage records intermediate steps combining equations, facts, and a definition to derive a result.

T ] and E[CEPE3CS

The proof concludes before the appendix reports experiments varying selection cardinality. Those experiments find that cardinality affects convergence and final accuracy, and report E3CS’s speed advantage with no or minor final-accuracy loss.

T ] and E[CEPE3CS

APPENDIX C ADDITIONAL EXPERIMENTS UNDER VARYING SELECTION CARDINALITY

  • The number of selections per round may significantly affect convergence speed and final convergence accuracy.Source: Appendix C · pp. 18–19
  • E3CS solutions show accelerated convergence with no or only minor final-accuracy loss in experiments varying k.The compared selection cardinalities are k = 10, 20, and 30.Source: Appendix C · pp. 18–19, Figure 7 · p. 19
Loading 2011.08756v3…