PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Analysis of Federated Learning with Arbitrary Client Participation

Shiqiang Wang, Mingyue Ji

arXiv:2205.13648v4cs.LGcs.DCcs.ITmath.ITmath.OCstat.ML

TL;DR

Partial client participation makes FL convergence under realistic availability patterns an open question, and existing work has often focused on idealized patterns or retained nonzero error for general ones. The paper extends FedAvg with P-round update amplification and a unified analysis of participation effects. It reports convergence results across participation patterns, including regularized participation that can match the SGD lower bound for sufficiently large T.

  • Problem

    Convergence under realistic FL participation patterns remains incompletely understood because prior work often assumes idealized selection or gives general-pattern results with nonzero error.

    Source: §1 · pp. 1–2

  • Method

    The paper generalizes FedAvg to amplify accumulated updates every P rounds and unifies participation effects in a single analysis term.

    Source: §1 · p. 2, §2 · p. 3, §3 · p. 4

  • Results

    Regularized participation with finite P is reported to give the best performance and match the SGD convergence-error lower bound when T is sufficiently large; stochastic bounds also match state-of-the-art FedAvg rates in specified settings.

    Source: §1 · p. 2, §4.2 · p. 6, §7 · p. 10

  • Takeaways & Limitations

    The unified framework provides convergence bounds for non-stochastic and stochastic participation patterns, including ergodic, stationary, strongly mixing, and independent processes.

    Source: §1 · p. 2, §7 · p. 10

    In practice, the wait-for-all method may yield only limited improvement because finite training data restricts noise reduction.

    Source: §5 · p. 8

Abstract

from arXiv · show

Federated learning (FL) faces challenges of intermittent client availability and computation/communication efficiency. As a result, only a small subset of clients can participate in FL at a given time. It is important to understand how partial client participation affects convergence, but most existing works have either considered idealized participation patterns or obtained results with non-zero optimality error for generic patterns. In this paper, we provide a unified convergence analysis for FL with arbitrary client participation. We first introduce a generalized version of federated averaging (FedAvg) that amplifies parameter updates at an interval of multiple FL rounds. Then, we present a novel analysis that captures the effect of client participation in a single term. By analyzing this term, we obtain convergence upper bounds for a wide range of participation patterns, including both non-stochastic and stochastic cases, which match either the lower bound of stochastic gradient descent (SGD) or the state-of-the-art results in specific settings. We also discuss various insights, recommendations, and experimental results.

1 Introduction

Partial participation reflects both the scale and intermittent availability of FL clients, while convergence under realistic participation remains incompletely understood. The paper introduces generalized FedAvg and a unified analysis for a broad range of participation patterns.

1 Introduction

  • FL clients may participate intermittently because recruiting everyone each round is costly and devices can become unavailable.The stated costs include energy use and network congestion; smartphone users may participate only while charging.Source: §1 · p. 1
  • Existing analyses often assume independent probabilistic selection, while general-pattern results may retain constant error or require additional assumptions.The paper frames its questions around which patterns guarantee convergence to zero error and whether their rates can match idealized settings.Source: §1 · pp. 1–3
  • The paper generalizes FedAvg by amplifying parameter updates every P rounds and analyzes participation effects through a single term.This unified framework covers non-stochastic and regularized patterns as well as stochastic patterns, including ergodic, stationary, strongly mixing, and independent cases.Source: §1 · p. 2
  • For stochastic participation, expected convergence rates match state-of-the-art FedAvg rates derived for independent random participation.The paper also reports expected and high-probability convergence bounds for stochastic participation.Source: §1 · p. 2

2 Generalized FedAvg with Amplified Updates

The generalized FedAvg algorithm accumulates global updates over P rounds, then applies an amplification factor to the accumulated updates. The interval P and factor η control this update scheme.

2 Generalized FedAvg with Amplified Updates

  • Clients receive participation weights q_n^t, with zero weight indicating nonparticipation; participating clients perform I local update steps.For analysis, the algorithm has all clients compute local updates, but nonparticipants' computations have no effect on later rounds.Source: §2 · p. 3
  • Global updates accumulate for P rounds, after which the algorithm applies amplification factor η to the accumulated updates.η = 1 leaves updates unchanged, η > 1 amplifies them, and 0 < η < 1 reduces them.Source: §2 · p. 3
  • The authors motivate η > 1 when few clients participate per round: accumulated updates can better estimate the full population and move toward its majority descent direction.The dominant terms of the convergence upper bounds reported in Table 1 do not depend on P.Source: §2 · p. 3

3 Convergence Analysis and Main Result

The analysis isolates partial participation in the P-round divergence term, then uses learning-rate corollaries to derive bounds for different participation patterns. The theorem is stated under smoothness, gradient, and parameter constraints.

3 Convergence Analysis and Main Result

  • The alternative divergence bound separates per-round divergence terms from ˜δ2(P), which measures divergence of gradients averaged over P rounds.When participation weights are properly chosen, their averages across P rounds become more alike as P grows, and ˜δ2(P) becomes small.Source: §3 · p. 4
  • Theorem 3.1 assumes Assumptions 1, 2, and 3’, with γ ≤ 1/(12LIP), γη ≤ 1/(2LIP), and P ≤ T/2.The supplied theorem passage does not include the bound itself.Source: §3 · p. 4
  • Two learning-rate corollaries provide building blocks for the unified analysis, with the choice depending on whether and how fast P grows with T.After deriving ˜δ2(P), the authors substitute it into a corollary to obtain the participation-pattern results in Table 1.Source: §3 · pp. 4–5

4 Interpreting and Applying the Unified Framework

The section decomposes client-gradient divergence and interprets the participation term that governs convergence. It then relates that term to participation patterns, including regularized and stochastic cases.

4.1 Discussion on ˜β2 and ˜ν2: Decomposition of Divergence

  • The original divergence d² decomposes into β̃² and ν̃² components; increasing P reduces the ν̃-related term but not the β̃-related term.The paper attributes this difference to the smaller learning rate at larger P and to averaging over participating rather than all clients.Source: §4.1 · p. 5

4.2 Discussion on ˜δ2(P): Effect of Partial Participation

  • When averaged participation weights are equal across clients in every P-round window, δ̃²(P)=0 and the paper gives a regularized-participation convergence corollary.The corollary uses learning rates from Corollary 3.2.Source: §4.2 · p. 6
  • The participation term δ̃²(P) can be expressed through the variance of client participation weights averaged over P rounds, and the suggested P grows with participation variance and client count.The variance interpretation is presented as a way to analyze participation patterns when requiring δ̃²(P)=0 is too stringent.Source: §4.2 · pp. 6–7
  • For ergodic participation, the participation term can be chosen to approach zero as P grows.The proposition identifies this as a result for ergodic participation.Source: §4.2 · p. 6
  • For stationary participation with strong-mixing coefficient α(P)=O(P^-5), the paper gives expected and high-probability control of the participation term as P grows.The high-probability statement is given with probability 1−c.Source: §4.2 · p. 7
  • With participation independent across rounds, the high-probability bound has a tighter logarithmic c term than the strongly mixing bound, while clients in the same round may remain dependent.The stated independence assumption is across time, not across clients within a round.Source: §4.2 · p. 7
  • Under either strongly mixing or independent stochastic participation, Corollary 4.8 gives an expected convergence-error bound with a participation-dependent choice of P and learning rates.The result uses P choices and learning rates specified in Corollary 4.8.Source: §4.2 · p. 7

5 Discussions and Insights

The discussion connects participation patterns to convergence rates, practical speedup, and the trade-offs of waiting for all clients. Under stated conditions, the analysis reaches centralized-SGD lower-bound or state-of-the-art rates.

Interpretation of “Linear Speedup”

  • With equal-weight participation by S clients per round, the analysis gives linear speedup in S; arbitrary participation has speedup factor 1/ρ².The bound also gives speedup in S_min when at least S_min clients participate with equal weight each round.Source: §5 · p. 8

Matching Lower Bound or State-of-the-Art Results

  • For regularized participation, the rate matches centralized SGD’s convergence-error lower bound and is asymptotically optimal; stochastic participation matches state-of-the-art FedAvg rates for independent, unbiased sampling.The stochastic result does not require every client to participate within P rounds.Source: §5 · pp. 8–9

Special Case of Waiting for All Clients

  • The wait-for-all configuration averages M independent gradient samples per client, reducing noise to σ²/M and yielding rate O(σ/√(MNT)).For sufficiently large M under regularized participation, its rate can potentially match Algorithm 1’s rate and the SGD lower bound.Source: §5 · p. 8
  • In practice, wait-for-all may improve performance only modestly: finite data limits noise reduction, and SGD noise can help avoid saddle points and local minima.Experiments found amplified Algorithm 1 outperformed wait-for-all methods.Source: §5 · pp. 8–9

Achieving Regularized Participation in Practice

  • Regularized participation can be approximated by scheduling connected clients for similar averaged weights over P rounds; amplification may help when that cohort is more representative than a single-round subset.The experiments report good performance even when P is shorter than the full participation cycle.Source: §5 · p. 9

6 Experiments

Experiments on FashionMNIST and CIFAR-10 compare amplified FedAvg with standard FedAvg and wait-for-all variants under periodic client availability. Amplified Algorithm 1 performs best in the method comparison, while the best tested interval depends on the setting.

Experimental Setup

  • The experiments train CNNs on FashionMNIST and CIFAR-10 across 250 clients with non-IID data and availability cycling among groups every 100 rounds.Each client has one majority class label and 5% of data from other labels; the study uses an initial training phase before comparing methods.Source: §6 · p. 9

Comparing Different Methods

  • With periodically connected clients at P = 500, Algorithm 1 with amplification achieves the best performance; wait-minibatch and wait-full perform worse, while standard FedAvg gives the lowest performance.Source: Figure 1 · p. 9, §6 · pp. 9–10

Different Values of P

  • For P values tested with η = 10, P = 100 and P = 300 perform similarly to P = 500 and slightly better on CIFAR-10, while P = 700 and P = 900 perform worse.The authors suggest that larger accumulated updates may make amplification changes too large; a smaller learning rate may improve results for large P.Source: §6 · p. 10, Figure 2 · p. 10

7 Conclusion

The paper develops convergence analysis for generalized FedAvg under arbitrary client participation and reports rates matching SGD’s lower bound or state-of-the-art FedAvg results in specified settings. It distinguishes this multi-client, non-convex focus from related work on block-cyclic SGD, centralized sampling, and two-sided learning rates.

7 Conclusion

  • For regularized participation, finite P gives the best performance and matches the SGD convergence-error lower bound for sufficiently large T; stochastic participation has guarantees for ergodic processes and can match state-of-the-art FedAvg rates.Experiments also confirm amplification is useful.Source: §7 · p. 10

A Additional Related Works

  • Unlike block-cyclic SGD work [6] [7], this paper targets one model without block structure and non-convex objectives common in neural-network problems.The cited block-cyclic work analyzes convex objectives with multiple models trained on client groups of known identity.Source: A Additional Related Works · p. 15
  • Centralized minibatch-sampling studies cover IID sampling [11] and random reshuffling [25], whereas this paper addresses client-specific objective diversity and a broader unified framework.The passage notes that federated learning is more complex because it incorporates diversity across clients’ local objectives.Source: A Additional Related Works · p. 15
  • Two-sided learning-rate FedAvg [18] [36] is the P = 1 case; this work extends it to P ≥ 1 and experimentally verifies amplification under more challenging participation patterns.Look-ahead methods [31, 42] consider two agents, unlike this paper’s multiple arbitrarily participating clients with non-IID data.Source: A Additional Related Works · p. 15
  • A theoretical account of local SGD’s practical advantage over minibatch SGD across broad problem classes, especially non-convex ones, remains an open direction [33] [41].Source: A Additional Related Works · p. 15

B.1 Why Does Amplification Help?

The motivating example explains how periodic amplification can speed progress under cyclic client availability, while the following discussion relates participation patterns to practical FL settings.

B.1 Why Does Amplification Help?

  • With cyclic availability, changing clients can pull the model toward different local optima, leaving a gap after 15 rounds with either large or small γ.The no-amplification trajectories can cycle around the global optimum, especially for large γ.Source: §B.1 · pp. 15–16
  • Amplifying updates accumulated over P = 3 rounds makes the model move faster toward the global optimum in this example.The explanation is that the combined update directions across clients are more likely to point toward the global optimum or its neighborhood.Source: §B.1 · p. 16

B.2 Relating Different Participation Patterns to Practical FL Scenarios

  • P need not exactly match the participation cycle; the paper reports good performance when P is shorter than the full cycle.The empirical result is cited as support for this point.Source: §B.1 · p. 16, §B.2 · p. 17
  • Regularized participation models periodic shifts, while ergodic, strongly mixing, and independent patterns correspond to different long-term participation behaviors in cross-device or cross-silo FL.Strongly mixing includes Markov-chain availability; independent participation can represent clients skipping rounds for higher-priority tasks.Source: §B.2 · pp. 16–17

C Proofs

The proof appendices collect recurring inequalities and notation, then use lemma derivations as technical ingredients for the main convergence analysis.

C.1 Preliminaries

  • Jensen’s and Peter–Paul (Young’s) inequalities are listed as tools used throughout the proofs.The appendix says these inequalities will be used without further explanation.Source: §C.1 · p. 17
  • The proofs use E·|Q [·] as shorthand for conditional expectation and adopt notation from the algorithm and assumptions..Source: §C.1 · p. 17

C.2 Lemmas

  • The lemma proofs use stochastic-gradient variance decomposition and combine recursion, smoothness, and inequality steps to derive bounds.The cited proof fragments invoke Jensen’s inequality and L-smoothness among the steps.Source: §C.2 · p. 22

C.3 Proof of Theorem 3.1

The proof of Theorem 3.1 combines intermediate bounds and telescopes them across rounds to obtain the stated convergence result.

C.3 Proof of Theorem 3.1

  • The argument uses unbiased stochastic gradients and the law of total expectation when taking expectations over the iterates..Source: §C.3 · pp. 24, 26
  • The proof combines Lemmas C.1 and C.2 to bound terms in the descent argument..Source: §C.3 · p. 26
  • Under the stated step-size conditions, the proof telescopes the descent bound and includes stochastic-gradient, divergence, and participation terms.The passage gives γ ≤ 1/(12LIP) and γη ≤ 1/(2LIP) as conditions used in rearranging the bound.Source: §C.3 · pp. 27–28

C.4 Proof of Corollaries 3.2 and 3.3

The corollary proofs verify the step-size conditions of Theorem 3.1 and obtain their results by substituting the corollary-specific learning rates.

C.4 Proof of Corollaries 3.2 and 3.3

  • The proof checks γ ≤ 1/(12LIP) and γη ≤ 1/(2LIP) so that Theorem 3.1 applies..Source: §C.4 · p. 28
  • For one corollary, the proof establishes γη ≤ 1/(2LIP) before invoking Theorem 3.1..Source: §C.4 · p. 28
  • The corollary result is obtained by substituting its γ and η values into Theorem 3.1 and using ρ² ≤ 1..Source: §C.4 · p. 28

D Additional Details and Results of Experiments

The appendix details the experimental setup and reports that, with always-available clients, independent and regularized participation perform similarly, with a slight advantage for regularized participation. It also describes periodic-availability settings and additional training choices.

D.1 Additional Details of the Setup

  • The experiments use non-IID client data and periodic availability motivated by geographically dispersed user groups or edge servers active at different times.In the periodic setup, groups of clients with different majority labels take turns being available in 100-round intervals, with a 500-round full cycle and 10 selected clients per round.Source: §D.1 · p. 29
  • For always-available clients, 10 of 250 clients participate per round, either through independent uniform selection or regularized sequential selection after a random permutation.With regularized participation, all clients participate once in every N rounds.Source: §D.1 · p. 29
  • Initial learning rates were selected by searching on always-available clients, and subsequent rates for periodic availability were searched over a grid of multiples of the initial rate.The initial-rate choice was based on training loss after 2,000 FashionMNIST rounds and 4,000 CIFAR-10 rounds; the table lists the optimal rates from the subsequent grid search.Source: §D.1 · p. 29, Table D.1 · p. 30
  • Experiments fix local updates at I = 5 and minibatch size at 16, and do not study their effects in detail.The authors note that changing these settings can affect all methods, while their relative differences may remain similar.Source: §D.1 · pp. 29–30

D.2.1 Always Available Clients

  • With always-available clients, independent and regularized participation perform similarly, while regularized participation has a marginal performance improvement and slightly better convergence rate.The comparison is shown in Figure D.1; the convergence-rate observation is stated to agree with the theory.Source: §D.2.1 · p. 31, Figure D.1 · p. 31

D.2.2 Periodically Available Clients

For periodically available clients, larger learning rates are generally unstable, while reducing the rate improves performance. At the smallest tested rates, amplification improves performance, and a moderate range of amplification factors performs similarly.

D.2.2 Periodically Available Clients

  • For periodically available clients, large γ generally produces unstable training with high fluctuation, high loss, and low accuracy, while reducing γ improves performance.The discussion links the instability at large γ to the convergence conditions suggested by the theory when P is large.Source: §D.2.2 · p. 31, Figure D.2 · p. 31
  • Figure D.2 compares Algorithm 1 across different learning rates with periodically available clients; FashionMNIST at γ = 0.1 is omitted because NaN values occurred when training rounds were large.Source: Figure D.2 · p. 31
  • FashionMNIST results for γ = 0.1 are omitted because NaN values occurred when the number of training rounds was large.Source: Figure D.2 · p. 31
  • With γ fixed at 10^-5 for FashionMNIST and 5 × 10^-6 for CIFAR-10, η = 5, 10, and 15 perform similarly, while η = 2 performs worse and η = 20 has greater fluctuation and lower performance.The authors suggest that a coarse, experience-based choice of η can be sufficient without fine-grained tuning.Source: §D.2.2 · p. 32, Figure D.3 · p. 32

Related papers

Loading 2205.13648v4…