PaperlayerView exact revision on arXiv

Source-linked AI summary

Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies

Yae Jee Cho, Jianyu Wang, Gauri Joshi

arXiv:2010.01243v1cs.LGcs.DCstat.ML

TL;DR

Federated learning lacks convergence analysis for biased client selection despite partial participation and heterogeneous data. This paper analyzes selection bias, proposes Power-of-Choice, and reports up to 3× faster convergence with 10% higher test accuracy than random selection.

  • Problem

    Existing partial-participation convergence guarantees are largely limited to unbiased client selection, leaving biased selection’s effect on convergence insufficiently analyzed.

  • Method

    The paper analyzes progress-aware biased client selection and proposes Power-of-Choice to trade off convergence speed against solution bias with low communication and computation overhead.

  • Results

    Power-of-Choice achieves up to 3× faster convergence and 10% higher test performance than random-selection FedAvg.

  • Takeaways & Limitations

    Selecting clients with higher local losses can accelerate convergence, while Power-of-Choice can retain high accuracy with fewer participating clients.

  • Takeaways & Limitations

    Greater selection skew can increase the non-vanishing solution-bias term, and directly selecting highest-loss clients requires costly evaluation across all clients.

Abstract

from arXiv · show

Federated learning is a distributed optimization paradigm that enables a large number of resource-limited client nodes to cooperatively train a model without data sharing. Several works have analyzed the convergence of federated learning by accounting of data heterogeneity, communication and computation limitations, and partial client participation. However, they assume unbiased client participation, where clients are selected at random or in proportion of their data sizes. In this paper, we present the first convergence analysis of federated optimization for biased client selection strategies, and quantify how the selection bias affects convergence speed. We reveal that biasing client selection towards clients with higher local loss achieves faster error convergence. Using this insight, we propose Power-of-Choice, a communication- and computation-efficient client selection framework that can flexibly span the trade-off between convergence speed and solution bias. Our experiments demonstrate that Power-of-Choice strategies converge up to 3 $\times$ faster and give $10$% higher test accuracy than the baseline random selection.

1 Introduction

Federated learning must handle partial participation and heterogeneous client data, but existing convergence guarantees largely assume unbiased client selection. This paper analyzes biased selection and introduces Power-of-Choice to improve convergence while limiting resource costs and solution bias.

  • Partial participation can exacerbate the adverse effects of data heterogeneity in federated learning.
  • Existing convergence generalizations for partial participation are limited mainly to unbiased selection, proportional to each client’s dataset size.
  • Biased selection toward clients with higher local loss can accelerate error convergence and improve communication efficiency in heterogeneous environments.
  • Prior biased-selection approaches in federated learning were supported primarily by empirical demonstrations without rigorous analysis of their effect on convergence speed.
  • Biased data-selection methods from centralized SGD do not directly resolve federated learning’s distributed and heterogeneous setting, making generalization non-trivial and open.
  • Power-of-Choice provides a resource-efficient framework that achieves up to 3× faster convergence and 10% higher test performance than random-selection FedAvg.

2 Problem Formulation

The paper formulates federated optimization over heterogeneous client objectives and describes FedAvg with partial participation. It then defines progress-aware biased selection, which may converge faster than random selection without preserving the unbiased update expectation.

  • The global objective averages client-local empirical risks, while local minimizers can differ substantially from the global minimizer.
  • FedAvg divides training into communication rounds, selects a client fraction, performs τ local SGD iterations, and aggregates the returned models.
  • Under partial participation, the active client set remains fixed across each block of τ local iterations.
  • The server update averages selected clients’ stochastic gradients, while the convergence analysis uses a virtual global-model sequence updated at every iteration.
  • Standard unbiased selection samples clients according to their data fractions, matching full participation in expectation.
  • A biased strategy can select the client with the highest current local loss, sacrificing the unbiased expectation while reaching the global minimum faster in the toy example.

3 Convergence Analysis

The analysis characterizes federated averaging under biased client selection using local-global objective gap and selection-skew metrics. It shows that greater selection skew accelerates convergence but may introduce solution bias, with the trade-off quantified by the convergence bound.

  • Assumptions: The analysis applies to federated averaging with partial participation under L-smoothness, strong convexity, unbiased bounded-variance gradients, and bounded expected gradient norms.These are stated as Assumptions 3.1–3.4.
  • Metrics: The local-global objective gap Γ measures heterogeneity between local and global objectives and is independent of the client selection strategy.When Γ = 0, the local and global optimal values are consistent and selection introduces no solution bias.
  • Metrics: Selection skew ρ and its conservative variant eρ quantify how client selection changes the local-global objective gap across training states.The metrics account for the selection-governing model, evaluation point, and randomness in the selected client set.
  • Trade-off: Biased selection trades faster convergence for possible solution bias, whereas unbiased selection has ρ = eρ = 1 and zero bias term.The bias term can nevertheless be negligible when eρ/ρ − 1 is close to zero.
  • Main result: Theorem 3.1 gives a convergence bound for any client selection strategy under a decaying learning rate η_t = 1/[µ(t+γ)].The bound separates a vanishing error term from a non-vanishing bias term.
  • Main result: A larger ρ yields faster convergence at rate O(1/(Tρ)), while the bound remains conservative because selection skew varies during training.The practical convergence improvement can be larger than, and at least equal to, ρ.

4 Proposed POWER-OF-CHOICE Client Selection Strategy

POWER-OF-CHOICE samples a candidate pool, estimates candidates’ local losses, and selects the highest-loss clients, while variants reduce computation or communication. The candidate-set size controls a trade-off between faster convergence and greater solution bias.

  • Trade-off: A larger selection skew ρ yields faster convergence but can increase the non-vanishing error term and solution bias.The analysis uses a conservative constant ρ, while practical skew may change during training.
  • Core strategy: POWER-OF-CHOICE selects clients with the largest local losses from a sampled candidate set.The server samples d clients, obtains their local losses, and selects m clients with the highest values.
  • Experiments: In quadratic experiments with K = 30, πpow-d converges faster than πrand, while increasing d raises convergence speed and solution bias.The figure reports nearly negligible solution bias for small d.
  • Efficient variants: πcpow-d reduces local computation by estimating each candidate’s local loss from a mini-batch rather than the entire local dataset.The supplied passage introduces the mini-batch estimate as the computation-efficient variant.
  • Efficient variants: πrpow-d reduces both computation and communication by using each client’s latest accumulated averaged loss as a proxy for local loss.For clients not yet selected, the latest proxy value is initialized to ∞.
  • Trade-off: The candidate-set size d controls the trade-off between convergence speed and solution bias, with d = m recovering random sampling without replacement in proportion to p_k.As d increases, selection skew ρ increases, producing faster error convergence at the risk of a higher error floor.

5 Experimental Results

Experiments across quadratic optimization, synthetic logistic regression, and heterogeneous FMNIST show that Power-of-Choice strategies accelerate convergence and improve test accuracy over random selection, while exposing a trade-off between speed, bias, and resource use.

  • Quadratic and Synthetic Simulation Results: Power-of-Choice spans a trade-off between convergence speed and solution bias by varying d.Larger d increases convergence speed but can raise the error floor; for d = 15 and K = 100, πpow-d has higher ρ with approximately the same eρ/ρ as πrand.
  • Quadratic and Synthetic Simulation Results: 3× faster convergence occurs for πpow-d with d = 10m, while d = 2m achieves 2× faster convergence than πrand to global loss ≈0.5.These results use logistic regression on Synthetic(1,1).
  • Experiments with Heterogeneously Distributed FMNIST: Approximately 10% higher test accuracy than πrand is achieved by πpow-d on FMNIST across both small and large α.For higher α, larger d performs better; for smaller α, d = 6 performs better than larger d because excessive solution bias is adversarial under greater heterogeneity.
  • Performance of the Communication- and Computation-Efficient variants: For α = 0.3, πcpow-d and πrpow-d perform as well as πpow-d and provide a 10% accuracy improvement over πrand.For α = 2, πcpow-d and πrpow-d yield approximately 6% and 5% higher accuracy than πrand, respectively, but lower accuracy than πpow-d.
  • Performance of the Communication- and Computation-Efficient variants: With C = 0.03, Power-of-Choice variants reduce communication rounds and can lower computation time relative to πrand with C = 0.1 while maintaining higher test accuracy.In Table 1, R60 is 0.52, 0.47, and 0.57 times the baseline for πpow-d, πcpow-d, and πrpow-d, respectively; πcpow-d and πrpow-d also have smaller tcomp.

6 Concluding Remarks

The paper establishes convergence guarantees for biased client selection under partial participation and proposes POWER-OF-CHOICE based on this analysis. Experiments report faster convergence and higher test accuracy than random selection, including when using fewer clients.

  • 6 Concluding Remarks: Biasing selection toward clients with higher local losses can speed convergence at rate O(1/Tρ), where ρ measures selection skew.The selection skew is specifically toward clients with higher local losses.
  • 6 Concluding Remarks: POWER-OF-CHOICE is an adaptive client selection strategy motivated by the convergence benefit of biased selection.The paper presents it as a practical strategy derived from the convergence analysis.
  • 6 Concluding Remarks: 3× faster convergence and 10% higher test accuracy are reported for POWER-OF-CHOICE than for federated averaging with random selection.These are extensive-experiment results against the baseline random-selection method.
  • 6 Concluding Remarks: 2× faster convergence with high test performance is reported even when POWER-OF-CHOICE uses fewer clients than random selection.The comparison concerns client count as well as convergence and test performance.

A Additional Theorem

The appendix gives a fixed-learning-rate convergence theorem for federated averaging with partial device participation and arbitrary client selection. As iterations grow, the vanishing term disappears while the remaining term determines the fixed-rate bias.

  • A Additional Theorem: Under Assumptions 3.1–3.4, Theorem A.1 bounds the error after T iterations for any client selection strategy π.The theorem assumes a fixed learning rate η ≤ min{1/(2µB), 1/(4L)}, with B = 1 + 3ρ/8.
  • A Additional Theorem: As T →∞, the first term in the theorem’s bound vanishes and the second term becomes the fixed-learning-rate bias term.This describes the asymptotic roles of the two terms in the error bound.
  • A Additional Theorem: For small η, the fixed-learning-rate bias term is upper bounded by 8LΓ.The supplied passage states this upper bound without displaying the complete surrounding expression.
  • A Additional Theorem: The fixed-learning-rate bias term is identical to the decaying-learning-rate case.The proof is presented in Appendix D.

B Preliminaries for Proof of Theorem 3.1 and Theorem A.1

This section introduces expectations over client-selection randomness and develops lemmas controlling client-model discrepancies and distance to the global optimum. The proof uses synchronization and learning-rate conditions to bound these quantities.

  • B Preliminaries: The analysis distinguishes expectation over the sampling source S(t) from expectation over all random sources.The notation is ES(t) for selection sampling and E for total expectation.
  • B Preliminaries: Lemma B.2 concerns the expected average discrepancy between the global model and selected clients’ models.The supplied passages identify the lemma’s subject but do not provide its complete bound.
  • B Preliminaries: Terms with identical client indices vanish because k and k′ belong to the same selected set S(t).The argument removes k = k′ terms when passing from the pairwise sum in (14) to (15).
  • B Preliminaries: For arbitrary t, the discrepancy between client and global models is bounded over at most τ updates, using non-increasing learning rates and η_t0 ≤ 2η_t.Selected clients are updated with the global model every τ iterations.
  • B Preliminaries: Lemma B.3 gives an upper bound on E[||w(t)−w*||²] for any selection strategy π.The expectation includes randomness from the selection strategy.

C Proof of Theorem 3.1

The proof expands the squared distance after a federated update into several terms and bounds them using smoothness, convexity, gradient unbiasedness, variance, and selection-related quantities. These bounds are combined recursively under learning-rate constraints.

  • C Proof of Theorem 3.1: The update expansion decomposes the squared distance into terms A1 through A4 involving local gradients, the aggregate stochastic gradient, and their discrepancies.The decomposition begins from ||w(t+1)−w*||² and defines labeled terms in the proof.
  • C Proof of Theorem 3.1: A5 is reformulated and bounded through A6 and A7 using learning-rate restrictions, convexity, smoothness, and definitions of selection skew and heterogeneity.The proof applies η_t < 1/(4L) and uses ρ, eρ, and Γ as defined quantities.
  • C Proof of Theorem 3.1: The proof combines the term bounds into a recursion and applies a decaying learning rate η_t = β/(t+γ) by induction.The induction uses β > 1/(µB) and γ > 0.
  • C Proof of Theorem 3.1: The proof uses smoothness, convexity, AM-GM, Cauchy–Schwarz, gradient unbiasedness, and stochastic-gradient variance bounds to control A1–A4.The passage explicitly identifies the inequalities and assumptions used for these bounds.

E Extension: Generalization to different averaging schemes

The convergence analysis extends from simple averaging to time-invariant weighted schemes whose selected-client weights sum to one, including uniform sampling without replacement. The resulting analysis remains consistent with Theorem 3.1 and separates vanishing error from non-vanishing selection bias.

  • The generalized averaging scheme uses time-invariant weights q_k satisfying that their sum over selected clients equals one each round.
  • Uniform random sampling without replacement is included by setting q_k = p_kK/m for selected clients.
  • The update rule replaces simple averaging with a weighted aggregate gradient using the selected clients’ coefficients q_k.
  • The convergence analysis for weighted averaging is consistent with Theorem 3.1 through corresponding generalized lemmas.
  • The bound distinguishes a vanishing error term from a non-vanishing bias under the generalized selection scheme.

F Experiment Details

The experiments combine quadratic-model, synthetic logistic-regression, and heterogeneous FMNIST evaluations with implementation variants of Power-of-Choice. They measure client-selection profiles and use controlled sampling, local optimization, and simulated selection distributions.

  • Quadratic Model Optimization: The quadratic model uses strongly convex local objectives, power-law-distributed client data sizes, and a weighted global objective.
  • Theoretical selection-skew quantities are estimated by grid-searching model pairs and simulating 10000 client-sampling iterations for each strategy and model.
  • Logistic Regression on Synthetic Dataset: Synthetic logistic-regression experiments use 30 highly heterogeneous devices, mini-batches of 50, τ = 30, η = 0.05, and scheduled learning-rate decay.
  • DNN on FMNIST Dataset: FMNIST experiments train a two-hidden-layer multilayer perceptron with Dirichlet-partitioned client data, where smaller α indicates greater heterogeneity.
  • Power-of-Choice Variants: The rpow-d implementation selects m clients from d sampled candidates using accumulated averaged losses, reducing both local computation and communication.

G.2 Communication and Computation Efficiency with larger data heterogeneity

Under larger data heterogeneity, Power-of-Choice variants improve test accuracy and reduce communication rounds relative to random selection, including when clients have intermittent availability. The comparison reports R60, computation time, and test accuracy across strategies.

  • Table 2 compares R60, per-round computation time, and test accuracy for sampling strategies at α = 2.
  • With C = 0.03, πpow-d, πcpow-d, and πrpow-d achieve at least approximately 10% higher test accuracy than πrand with C = 0.1.
  • R60 is 0.61, 0.66, and 0.73 times the random-selection baseline for πpow-d, πcpow-d, and πrpow-d, respectively.
  • For intermittent availability, πpow-d achieves approximately 10% higher test accuracy than πrand for both α = 2 and α = 3.
  • At C = 0.1, πpow-d improves test accuracy by approximately 15% for α = 2 and 5% for α = 0.3 relative to πrand.
Loading 2010.01243v1…