An Efficiency-boosting Client Selection Scheme for Federated Learning with Fairness Guarantee

Tiansheng Huang; Weiwei Lin; Wentai Wu; Ligang He; Keqin Li; Albert Y. Zomaya

Source-linked AI summary

An Efficiency-boosting Client Selection Scheme for Federated Learning with Fairness Guarantee

Tiansheng Huang, Weiwei Lin, Wentai Wu, Ligang He, Keqin Li, Albert Y. Zomaya

arXiv:2011.01783v5Nov 3, 2020cs.LGcs.DC

TL;DR

Federated learning must select only some clients under limited bandwidth while balancing training efficiency, model quality, and fairness. This paper formulates fairness-guaranteed selection through Lyapunov optimization, estimates model exchange times with C2MAB, and designs RBCS-F, whose regret is finitely bounded and whose experiments show fairer strategies achieve higher final accuracy at some efficiency cost.

Problem
Limited bandwidth and dynamic client status require selecting only a fraction of volunteers, making client selection a tradeoff among training efficiency, model quality, and fairness.
Method
The paper transforms fairness-constrained client selection into online Lyapunov optimization and uses a C2MAB model to estimate each client's model exchange time for RBCS-F.
Results
RBCS-F has a finite upper bound on time-average regret, while experiments show fairer strategies generally achieve higher final accuracy but sacrifice some training efficiency.
Takeaways & Limitations
Fairness is a critical factor in federated-learning client selection, requiring an explicit tradeoff with training efficiency.
Takeaways & Limitations
The fairness guarantee assumes infinitely many training rounds, and the authors cannot rigorously quantify how the fairness factor affects final accuracy or convergence speed.

Abstract

from arXiv · show

The issue of potential privacy leakage during centralized AI's model training has drawn intensive concern from the public. A Parallel and Distributed Computing (or PDC) scheme, termed Federated Learning (FL), has emerged as a new paradigm to cope with the privacy issue by allowing clients to perform model training locally, without the necessity to upload their personal sensitive data. In FL, the number of clients could be sufficiently large, but the bandwidth available for model distribution and re-upload is quite limited, making it sensible to only involve part of the volunteers to participate in the training process. The client selection policy is critical to an FL process in terms of training efficiency, the final model's quality as well as fairness. In this paper, we will model the fairness guaranteed client selection as a Lyapunov optimization problem and then a C2MAB-based method is proposed for estimation of the model exchange time between each client and the server, based on which we design a fairness guaranteed algorithm termed RBCS-F for problem-solving. The regret of RBCS-F is strictly bounded by a finite constant, justifying its theoretical feasibility. Barring the theoretical results, more empirical data can be derived from our real training experiments on public datasets.

1 INTRODUCTION

The paper studies federated-learning client selection under limited bandwidth, emphasizing efficiency, model quality, and fairness. It combines Lyapunov optimization with C2MAB-based exchange-time estimation to design RBCS-F.

Motivation: Limited bandwidth means only a fraction of volunteer clients can participate in each federated-learning round.Selection affects training time, convergence speed, stability, and final accuracy.
Research gap: Existing selection studies consider communication time or energy but assume pre-known local training time and favor higher-performance devices.The paper identifies these assumptions and selection biases as important limitations of prior work.
Contributions: The paper formulates client selection as minimizing average model exchange time under long-term fairness and rigid system constraints.The formulation also incorporates availability, unknown stochastic training time, and dynamic communication status.
Contributions: Lyapunov optimization transforms the offline problem into an online problem, while dynamic queues quantify the long-term guarantee of client participation.This addresses the time-coupling structure of the original formulation.
Contributions: C2MAB estimates each client’s model exchange time from contextual properties and historical performance for online scheduling.The proposed combination is presented as a trackable approach to long-term constrained online scheduling.

2 RELATED WORKS

Prior FL and edge-intelligence work addresses local computation, communication, and selection efficiency, but the paper focuses on fairness as an additional selection factor. It also introduces multi-arm bandit methods as background for online learning under unknown rewards.

Edge intelligence: Edge intelligence combines AI with distributed edge devices, including DNN partitioning and low-latency inference.The related work situates federated learning within broader edge-intelligence research.
Federated learning: Federated learning trains models locally rather than transmitting data to the cloud, but communication overhead remains a bottleneck.Federated distillation and edge aggregation are discussed as ways to reduce communication distance or exchanged information.
Client selection: Prior client-selection studies mainly optimize communication or bandwidth allocation to shorten communication time.The paper distinguishes its fairness-oriented perspective from this communication-centered line of work.
Multi-arm bandits: Classical multi-arm bandits model actions with unknown reward distributions and require balancing exploration against exploitation.Upper Confidence Bound and Thompson Sampling are cited as representative solutions.

3 PRELIMINARY INTRODUCTION ON FL

The paper describes synchronous edge-coordinated federated learning in which an edge server aggregates local models and selects participating clients each round. Training proceeds through reporting, selection, distribution and local training, upload, and aggregation.

System model: The system uses an edge aggregator, mobile clients, private local data, and synchronous iterative training.Clients train locally on behalf of the model owner while the edge performs aggregation.
Training workflow: Fig. 1 is referenced as a visual presentation of the federated-learning training process.The supplied caption identifies it as an illustration of FL.
Training workflow: Each iteration begins with clients reporting willingness to participate and client-side information for subsequent selection.The scheduler uses these reports before choosing participants.
Training workflow: The scheduler selects a portion of volunteers, distributes the global model, and waits for selected clients to complete local training.Selection is based on the information supplied by participating clients.
Training workflow: After local training, clients return updated models; the server aggregates them into the next global model.The round then returns to the reporting stage for another iteration.

4 PROBLEM FORMULATION

The problem formulation targets long-term model-exchange efficiency while enforcing fairness, availability, and selection constraints. Because availability and exchange times are revealed dynamically, the offline problem motivates an online Lyapunov and bandit-based treatment.

4.1.1 Model Exchange Time: The model exchange time spans distribution, local training, and upload until all selected models are gathered.Client-specific exchange times are unknown to the scheduler until the round ends.
4.1.2 Long-Term Fairness Constraint: The paper questions greedy selection of the fastest clients because slower clients may receive little selection opportunity and contribute less local data.The text connects this selection bias with possible degradation in global-model generalization.
4.1.2 Long-Term Fairness Constraint: The long-term fairness constraint requires every client’s average chosen rate to remain at least β.x_t,n indicates whether client n is selected in round t, and short-term violations are tolerated.
4.1.3 Availability of Clients: Client availability is dynamic because volunteers may join or leave at any time, so I_t,n records willingness to participate.Availability information is obtained from client reports before scheduling.
4.1.4 Selection Fraction: When fewer than m clients are available, the scheme selects all active clients rather than forcing the maximum selection count.The selection fraction is constrained using a minimum involving availability and m.
4.2 An Offline Long-Term Optimization Problem: The optimization minimizes long-term model exchange time subject to a soft fairness constraint and two hard system constraints.S_t denotes the selected clients in each round.
4.2 An Offline Long-Term Optimization Problem: An offline optimum is impractical because availability is revealed only at round start, fairness couples decisions across time, and exchange time is observed after training.These information and timing constraints prevent the scheduler from accessing all required quantities before selection.

4.3 Problem Transformation under Lyapunov Framework

The paper converts long-term fairness constraints into virtual-queue stability conditions, then uses Lyapunov drift-plus-cost optimization to obtain an online scheduling problem. The resulting formulation balances model exchange time against fairness while accounting for stochastic client availability and unknown exchange times.

Problem transformation: The offline fairness-constrained selection problem is transformed into an online problem using Lyapunov optimization.The transformation addresses time coupling in the long-term constraint.
Virtual-queue fairness: Virtual queues track each client’s guaranteed participation deficit, and mean-rate stability of all queues guarantees the long-term fairness constraint.The queue backlog grows when actual selection fails to match the expected guaranteed selection rate.
Lyapunov framework: The quadratic Lyapunov function measures virtual-queue backlogs, while Lyapunov drift bounds their expected increase over each federated round.The queue state contains the backlogs of all client-specific virtual queues.
Online scheduling: The per-round scheduling problem minimizes the drift-plus-cost upper bound after conditioning on observable queue states, client availability, and selection randomness.The formulation still requires model exchange-time estimates because actual client times are unknown before scheduling.
Drift-plus-cost optimization: A drift-plus-cost objective combines queue stabilization with minimization of model exchange time.The penalty factor V controls the tradeoff between the objective and fairness satisfaction.

4.4 Estimation of Model Exchange Time with C2MAB

The paper models client exchange time with a linear contextual bandit, using observable client and communication features with unknown stationary coefficients. Historical observations support ridge-regression estimates and UCB confidence bounds, producing exchange-time estimates for scheduling.

C2MAB formulation: C2MAB represents clients as arms and client subsets as super arms, with contextual losses and a collective objective minimized through repeated selection.UCB uses historical losses to narrow confidence bounds toward expected values.
Parameter estimation: Ridge regression uses historical client contexts and observed exchange times to estimate each client’s unknown static coefficient vector.The scheduler treats client-specific coefficients as stationary and learns them from prior plays.
Contextual features: Model exchange time is estimated from computation capacity, prior-round participation status, model size, and allocated bandwidth.The contextual vector includes [1/µt,n, st,n, M/Bt,n]⊤.
Confidence estimation: The UCB estimate adds an exploration term to the predicted exchange time, with αt serving as the exploration parameter.The confidence bound is intended to keep the real expected exchange time close to its optimistic estimate with high probability.
Optimization reformulation: The estimated-time formulation converts the scheduling problem into a solvable integer linear program, for which the paper designs a divide-and-conquer solution.The transformed problem is used as the basis for efficient scheduling decisions.

5 ALGORITHMS AND ANALYSIS

RBCS-F combines estimated exchange times with virtual-queue backlogs to select available clients under fairness constraints. The analysis gives a finite regret upper bound and proves fairness-queue stability, while noting that finite training horizons can delay fairness convergence for large V.

Selection solver: The divide-and-conquer solver filters available clients by estimated exchange time, selects candidates with the largest virtual-queue backlogs, and compares subproblem objectives.The procedure selects k = min{m, Σn It,n} clients and has computation complexity O(N^2).
RBCS-F procedure: RBCS-F observes contexts and client availability, estimates exchange times from historical data, solves the selection subproblem, and updates queues and estimators after each round.The algorithm distributes the model to selected clients, observes their exchange times, and updates the associated parameters.
Regret analysis: The time-average regret of RBCS-F is defined against an optimal policy and is strictly upper bounded with probability at least (1 − δ)^2.The bound applies for any control parameter V under finite positive norm bounds on contexts and coefficients.
Fairness guarantee: For any V, RBCS-F’s fairness virtual queues are mean-rate stable, guaranteeing time-average fairness.This result is stated as Theorem 4.
Impact of V: Larger V can improve long-term exchange time while slowing queue convergence, so finite training may provide weaker fairness before convergence.The asymptotic fairness guarantee assumes infinitely many training rounds.

6 EXPERIMENTS

Experiments evaluate RBCS-F through simulations and real training on fashion-MNIST and CIFAR-10, examining fairness, training time, accuracy, and round efficiency under varied settings. Results show that fairness and efficiency trade off, while fairer selection generally improves final accuracy.

6.1 Experiments: The simulation uses 40 heterogeneous clients divided equally into four classes, with model exchange time modeled linearly.Client bandwidth and computation capacity are varied to represent different communication and computational abilities.
6.1 Experiments: RBCS-F is compared with random selection and an adapted FedCS baseline under a common client-selection setting.FedCS(3) uses a 3-second deadline, producing approximately eight selected clients, matching the other strategies.
6.1.2 Numerical performance evaluation: Different penalty factors V produce queue curves that eventually flatten, supporting mean-rate queue stability and long-term fairness.Higher V is associated with slower convergence and a higher convergence value, implying a short-term fairness sacrifice before convergence.
6.1.2 Numerical performance evaluation: After 500 decision rounds, high V and FedCS(3) produce more uneven client pull distributions, whereas random selection and low-penalty RBCS-F are more even.The more even selection of clients explains why fairer strategies can require more training time than strategies favoring the fastest clients.
6.2.2 Impact of fairness: Higher fairness concentration γ2 improves final accuracy on both fashion-MNIST and CIFAR-10, while lower non-iid concentration γ1 increases curve jitter and delays convergence.The experiments do not explicitly show that γ1 changes the influence of fairness on accuracy.
6.2.4 Accuracy vs. training time: FedCS(3) has the highest early time efficiency at low accuracy, while RBCS-F maintains an acceptable gap from FedCS(3) and improves substantially over random.A higher penalty does not necessarily improve time efficiency: RBCS-F(20) outperforms RBCS-F(50) throughout the reported training process.

7 CONCLUSION AND FUTURE PROSPECT

The paper studies the tradeoff between fairness and training efficiency in federated-learning client selection. Experiments indicate that fairer strategies can improve final accuracy while sacrificing some efficiency, but the relationship remains unquantified.

Fairness plays a critical role in the federated-learning training process.
Fairer client-selection strategies can achieve higher final accuracy while sacrificing some training efficiency.
The relationship between fairness, final accuracy, and convergence speed lacks a rigorous quantification.
The paper identifies theoretical analysis of fairness in federated learning as an open direction for future work.

APPENDIX A PROOF OF THEOREM 2

The proof derives the theorem through a sequence of algebraic transformations involving squared binary variables, prior inequalities, and an expected objective term.

The proof begins by taking the square of equation (6).
Because x_t,n is binary, its square is bounded by 1.
The derivation combines equations (8), (9), and (26) to obtain the next bound.
Substituting V E[f(S_t, τ_t)|Θ(t)] into equation (27) yields the form of equation (11).

APPENDIX B PROOF OF LEMMA 1

The appendix establishes Lemma 1 using a sub-Gaussian confidence result, the model’s boundedness assumptions, and comparisons between the proposed policy and benchmark policies.

Lemma 2 assumes conditionally R-sub-Gaussian noise and bounded parameter and context norms.
The confidence result states that the estimator satisfies a bound with probability at least 1−δ across rounds.
Finite bounds on training time and contexts justify applying Lemma 2 to the system model.
The proof applies the estimation rule and analyzes the second term in a minimum expression.

APPENDIX C PROOF OF THEOREM 3

The appendix bounds the regret by decomposing it into terms and applying policy comparisons, queue stability, confidence bounds, and matrix inequalities. The resulting bound holds with high probability.

The proof defines the time-average regret and compares the proposed policy with a policy that knows the real model exchange time.
The queue-stability argument uses the fact that the optimal policy’s expected input rate is below its service rate.
The optimal policy cannot outperform the fully informed comparison policy in the stated objective.
The regret terms are bounded using confidence quantities, bounded exchange times, and estimates of the reward gap.
The final regret upper bound holds with probability (1−δ)^2.

APPENDIX D PROOF OF THEOREM 4

The proof of Theorem 4 establishes RBCS-F’s optimality within the considered comparison and derives mean-rate stability of the queues, supporting the long-term fairness guarantee.

Theorem 4 proof: Lemma 4 supplies the auxiliary result used to derive the theorem’s proof inequalities.The proof invokes Lemma 4 before applying expectation, summation, and limiting arguments.
Theorem 4 proof: RBCS-F minimizes the right-hand side of inequality (11), so no other policy matches its objective under the stated proof comparison.The argument applies the minimization property to any ω-only policy and any observed stochastic events.
Theorem 4 proof: The proof uses expectation, telescoping over t, division by T, and the law of large numbers to obtain the asymptotic conclusion.It also uses nonnegativity of E[Z_T,n] in the final step.
Theorem 4 proof: Mean-rate stability of all queues holds regardless of V, and combined with Theorem 1 it ensures no violation of the long-term average fairness constraint.The queue-stability result is the proof’s direct fairness implication.