PaperlayerView exact revision on arXiv

Source-linked AI summary

A Lightweight Method for Tackling Unknown Participation Statistics in Federated Averaging

Shiqiang Wang, Mingyue Ji

arXiv:2306.03401v3cs.LGcs.DCcs.ITmath.ITmath.OCstat.ML

TL;DR

Unknown, heterogeneous client participation can make it difficult to minimize the original federated learning objective, while existing variance-reduction approaches can require substantial additional memory. This paper introduces FedAU, which adapts FedAvg aggregation weights using participation histories. Its analysis establishes convergence to an optimal solution and linear speedup under stated conditions, and experiments report gains across participation patterns.

  • Problem

    The paper asks how to provably minimize the original FL objective when client participation statistics are unknown, uncontrollable, and heterogeneous, without the additional memory required by variance-reduction approaches.

    Source: §1 · pp. 1–2

  • Method

    FedAU adaptively weights client updates using estimates of optimal aggregation weights based on each client’s participation history.

    Source: §1 · p. 2

  • Results

    FedAU’s analysis shows convergence to an optimal solution of the original objective and linear speedup for sufficiently many FL rounds, while experiments report advantages across participation patterns.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The paper presents adaptive aggregation weighting as a lightweight approach to unknown participation statistics, with experiments including time-dependent Markovian and cyclic patterns.

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

    The convergence analysis requires time-independent client participation, although experiments report performance gains for time-dependent Markovian and cyclic patterns.

    Source: §4 · p. 6

Abstract

from arXiv · show

In federated learning (FL), clients usually have diverse participation statistics that are unknown a priori, which can significantly harm the performance of FL if not handled properly. Existing works aiming at addressing this problem are usually based on global variance reduction, which requires a substantial amount of additional memory in a multiplicative factor equal to the total number of clients. An important open problem is to find a lightweight method for FL in the presence of clients with unknown participation rates. In this paper, we address this problem by adapting the aggregation weights in federated averaging (FedAvg) based on the participation history of each client. We first show that, with heterogeneous participation statistics, FedAvg with non-optimal aggregation weights can diverge from the optimal solution of the original FL objective, indicating the need of finding optimal aggregation weights. However, it is difficult to compute the optimal weights when the participation statistics are unknown. To address this problem, we present a new algorithm called FedAU, which improves FedAvg by adaptively weighting the client updates based on online estimates of the optimal weights without knowing the statistics of client participation. We provide a theoretical convergence analysis of FedAU using a novel methodology to connect the estimation error and convergence. Our theoretical results reveal important and interesting insights, while showing that FedAU converges to an optimal solution of the original objective and has desirable properties such as linear speedup. Our experimental results also verify the advantage of FedAU over baseline methods with various participation patterns.

1 INTRODUCTION

Federated learning clients can have heterogeneous participation rates that are unknown and difficult to control, potentially biasing training away from the original objective. The paper motivates adaptive aggregation weights and introduces FedAU to estimate them from client participation histories.

1 INTRODUCTION

  • Heterogeneous participation may bias FL toward certain local objectives and away from the optimum of the original objective.Because participation can correlate with data heterogeneity, frequently participating clients may be favored over less frequent participants.Source: §1 · p. 2
  • Prior variance-reduction methods store recent updates for all clients, requiring additional memory on the order of Nd.The paper asks whether the original objective can be provably minimized without this memory burden when participation is unknown, uncontrollable, and heterogeneous.Source: §1 · p. 2
  • FedAvg with non-optimal aggregation weights minimizes a different objective from the original FL objective.This motivates finding appropriate aggregation weights.Source: §1 · p. 2
  • FedAU estimates optimal aggregation weights from each client’s participation history without knowing participation statistics a priori.It is presented as a lightweight procedure within the overall FL process.Source: §1 · p. 2
  • The analysis shows FedAU converges to an optimal solution of the original objective and achieves linear speedup when the number of FL rounds is large enough.The convergence analysis bounds a weight-error term using a bias-variance decomposition.Source: §1 · p. 2
  • The paper reports experiments across independent, Markovian, and cyclic client participation patterns.The related-work discussion distinguishes this focus from variance-reduction approaches that store client updates and notes that adaptive gradients and local updates are orthogonal approaches.Source: §1 · pp. 2–3

2 FEDAVG WITH PLUGGABLE AGGREGATION WEIGHTS

The section presents FedAvg with pluggable aggregation weights and shows why fixed weights can target the wrong objective under heterogeneous participation. The result motivates adapting the weights to participation statistics.

2 FEDAVG WITH PLUGGABLE AGGREGATION WEIGHTS

  • The generic algorithm runs T rounds with I local SGD steps per participating client and uses local and global step sizes γ and η.It includes a separate oracle for computing aggregation weights.Source: §2 · p. 3
  • Each client computes its weight locally without coordination, using an aggregated participation-history metric rather than storing the full record.FedAU uses the average participation interval, computed online, and excludes current-round participation when computing the current weight.Source: §2 · p. 3

Objective Inconsistency with Improper Aggregation Weights

  • With Bernoulli participation and time-constant weights, FedAvg generally minimizes an objective weighted by client participation probabilities rather than the original objective.With standard FedAvg weights of 1, this implicit weighting favors clients that participate more frequently; when probabilities are unknown, the objective being minimized is also unknown.Source: §2 · p. 4

3 FEDAU: ESTIMATION OF OPTIMAL AGGREGATION WEIGHTS

FedAU estimates client-specific aggregation weights online from participation histories, using cutoff participation intervals to make those estimates more stable. The cutoff K trades estimation bias against variance, while the averaging procedure requires only a few scalar state variables per client.

3 FEDAU: ESTIMATION OF OPTIMAL AGGREGATION WEIGHTS

  • FedAU aims to weight updates inversely to client participation frequency, counteracting participation bias in the original objective.The target is a long-term average weight close to 1/p_n for each client.Source: §3 · p. 4
  • Because future participation is unknown, each round estimates client weights from participation history observed before that round.With few observations, a long interval can distort the average and destabilize training.Source: §3 · p. 4
  • A cutoff K bounds interval lengths; smaller K reduces variance but increases bias in the estimated aggregation weight.The paper reports that an appropriate finite K improves performance in most cases.Source: §3 · p. 5
  • FedAU averages observed cutoff intervals online using three scalar state variables per client, avoiding storage of all past intervals.The state variables are the interval count, the current interval length, and the previous weight.Source: §3 · p. 5
  • Weight computation uses each client's participation states, not its training data or model, and the server only sums participating clients' updates.The paper says secure aggregation and differentially private FedAvg methods can be applied directly or similarly.Source: §3 · p. 5
  • If each client participates only once, convergence to the original objective is impossible without sharing additional information.This boundary follows a lower bound cited by the authors.Source: §3 · p. 6

4 CONVERGENCE ANALYSIS

The analysis connects aggregation-weight estimation error to convergence of the original objective, under stated smoothness, gradient, and participation assumptions. It establishes convergence with unknown participation probabilities and linear speedup when the number of rounds is large enough, while the proof does not cover time-dependent participation.

4 CONVERGENCE ANALYSIS

  • The proof assumes client participation is independent across rounds; this is a theoretical limitation, while experiments report gains for Markovian and cyclic patterns.The authors say the proof step would not hold if participation depended on the past.Source: §4 · p. 6
  • Theorem 2 bounds convergence error to the original objective for arbitrary given weights under Assumptions 1–5.The stated assumptions include smooth local objectives, bounded gradient conditions, and participation conditions.Source: §4 · p. 7
  • The convergence bound includes a separate weight-error term, which the analysis further bounds to establish FedAU's convergence result.The weight-error analysis uses a bias-variance decomposition of cutoff participation intervals.Source: §4 · p. 7
  • With Algorithm 2 weights, FedAU's error approaches zero as rounds increase despite unknown participation statistics, with linear speedup when rounds remain large enough.The unknown-probability contribution has order O(log^2 T/T).Source: §4 · p. 7

5 EXPERIMENTS

Across four image-classification tasks and several participation patterns, FedAU generally achieved the highest accuracy among the baselines, with a CIFAR-10 test-accuracy exception. Its finite cutoff interval also mattered: an intermediate K performed better when clients participated very infrequently.

Experimental setup

  • Experiments covered four image-classification datasets, 250 clients, non-IID data, and Bernoulli, Markovian, or cyclic participation patterns.The main experiments lower-bounded each client’s stationary participation probability at 0.02; baselines included ordinary averaging and methods using additional memory or known participation statistics.Source: §5 · pp. 8–9

Results

  • FedAU achieved the highest accuracy against almost all baselines, except that FedVarp led on CIFAR-10 test accuracy.The comparison includes baselines requiring extra memory or known participation statistics.Source: Table 1 · p. 8, §5 · p. 9
  • FedAU avoids stale local updates by starting participating clients from the latest global model, unlike FedVarp and MIFA, which retain historical updates.The paper links potentially outdated updates from infrequent clients to slow convergence.Source: §5 · p. 9
  • FedAU uses each client’s observed participation history to estimate aggregation weights, and the paper reports better empirical performance than using 1/pn even when pn is known.The paper attributes this to the empirical participation path capturing actual client behavior.Source: §5 · p. 9
  • With small minimum participation probabilities, K = 50 performed best, while K ≥500 significantly deteriorated performance.The paper identifies a finite, intermediate cutoff interval for weight estimation as important when some clients participate very infrequently.Source: §5 · p. 9

6 CONCLUSION

The conclusion presents FedAU as a lightweight response to unknown client participation, using participation histories to adapt aggregation weights and a bias-variance-based analysis. The appendix notes that the objective can also represent weighted client risks and clarifies conditions used in the convergence analysis.

6 CONCLUSION

  • FedAU adapts aggregation weights using each client’s participation history, and its analysis bounds weight-estimation error to establish convergence and linear speedup for sufficiently many rounds.The paper reports experimental advantages across several participation patterns and identifies broader participation processes and other FL algorithms as future work.Source: §6 · p. 9

A.1 EXTENDING OBJECTIVE (1) TO WEIGHTED AVERAGE

  • The objective extends to weighted averages of client empirical risks, allowing different client importance through coefficients qn.The main paper omits these coefficients for simplicity.Source: §A.1 · p. 14

A.2 ASSUMPTION ON BOUNDED GLOBAL GRADIENT

  • The convergence result holds under either a bounded-global-gradient condition or a nearly-optimal-weights condition; the gradient bound is needed when weight-estimation error is large.The paper contrasts its global-gradient bound with the stronger bounded-stochastic-gradient assumption used in cited adaptive-gradient works.Source: §A.2 · p. 14

A.3 COMPARISON WITH EXISTING CONVERGENCE BOUNDS FOR FEDAVG

The appendix compares FedAvg convergence results across participation settings and details the proof framework. Its comparison treats heterogeneous, unknown client probabilities as more general than fixed-size uniform sampling, while the proof uses an equivalent algorithm formulation and a weighted-loss descent analysis.

A.3 COMPARISON WITH EXISTING CONVERGENCE BOUNDS FOR FEDAVG

  • For equiprobable sampling, the paper says its bound matches Karimireddy et al. (2020), improves over Yang et al. (2021), and has linear speedup in participating clients.These comparisons are for the special case of known, homogeneous participation probabilities.Source: §A.3 · p. 15
  • Unlike fixed-size uniform-sampling analyses, this work allows heterogeneous, unknown participation probabilities and a number of participating clients that varies over time.The bound uses Q to capture participation statistics because a fixed S does not apply to this general setting.Source: §A.3 · pp. 14–15

B.1 PRELIMINARIES

  • The preliminary proof toolkit invokes Jensen’s inequality and the generalized Young’s inequality.The appendix also identifies the latter as the Peter-Paul inequality.Source: §B.1 · p. 16

B.2 EQUIVALENT FORMULATION OF ALGORITHM 1

  • The appendix treats all clients as computing local updates for analysis, since nonparticipants’ zero indicator makes those updates irrelevant to the server output.The paper states this formulation is logically equivalent to the practical algorithm and produces the same output sequence.Source: §B.2 · p. 16

B.3 GENERAL DESCENT LEMMA

  • The proof framework defines a generally weighted loss to derive a descent lemma, enabling convergence analysis for objectives that differ when aggregation weights are improperly chosen.The appendix’s proof steps invoke smoothness, gradient-variance, and gradient-divergence bounds.Source: §B.3 · pp. 17–18

B.4 FORMAL VERSION AND PROOF OF THEOREM 1

The formal appendix theorem defines an alternative objective and gives conditions under which the algorithm’s convergence bound can be made arbitrarily small as the number of rounds grows. The proof reparameterizes step size and aggregation weights while preserving their product.

B.4 FORMAL VERSION AND PROOF OF THEOREM 1

  • Under the theorem’s stated conditions, the convergence bound for the alternative objective tends to zero as rounds grow, allowing an arbitrarily small target bound.The theorem specifies conditions on step size and positive aggregation weights.Source: §B.4 · pp. 23–24
  • The proof changes step size and aggregation weights while preserving their product, leaving the algorithm’s output unchanged.It chooses transformed weights proportional to the original weights and client count.Source: §B.4 · p. 23
  • The appendix connects the theorem’s objective to the general descent lemma by substituting transformed step-size and weight parameters.It identifies the theorem’s objective with the function used in the descent-lemma argument.Source: §B.4 · p. 23

B.5 PROOF OF THEOREM 2

The proof applies a descent lemma for the original objective, then uses the theorem’s step-size conditions to bound its terms and derive a round-averaged result.

B.5 PROOF OF THEOREM 2

  • The proof starts from a descent lemma stated for the original objective.The lemma is invoked under the conditions of Lemma B.3.3.Source: §B.5 · p. 24
  • The theorem’s step-size conditions are used to bound terms in the descent inequality before rearranging it.The proof applies these bounds after substituting into the lemma.Source: §B.5 · p. 24
  • The final result comes from summing the resulting bound over T rounds, dividing by T, and absorbing constants into O(·).The proof chooses ΨG according to the applicable case.Source: §B.5 · p. 25

B.6 PROOF OF THEOREM 3

The proof bounds FedAU’s aggregation-weight estimation error using the statistics of a K-cutoff geometric participation interval. It handles initialization separately before averaging the bounds over rounds and clients.

B.6 PROOF OF THEOREM 3

  • The participation interval S_n follows a K-cutoff geometric distribution, with its mean and variance used in the weight-error analysis.The cutoff caps the interval at K; as K tends to infinity, the distribution becomes geometric.Source: §B.6 · p. 25
  • Before a client’s first participation, the estimator uses its initial value for at most K rounds; later bounds use samples of S_n.The proof considers at least one sample once estimation has begun and uses the interval cutoff to lower-bound the number of samples.Source: §B.6 · pp. 27–28
  • The proof sums the per-round weight-error bounds, divides by T, and averages the result across clients.The derivation distinguishes initial rounds from rounds at or beyond K.Source: §B.6 · p. 28

B.7 PROOF OF COROLLARY 4

This merged block covers the proof of Corollary 4 and the experimental setup details for datasets, models, hyperparameters, computation, and simulated participation patterns.

B.7 PROOF OF COROLLARY 4

  • Choosing K = ⌈log_c T⌉ makes the relevant term in Theorem 3’s bound decrease with T.The proof uses the minimum client participation probability p in bounding the term.Source: §B.7 · pp. 28–29

C.2 DATASETS

  • The experiments use SVHN, CIFAR-10, CIFAR-100, and CINIC-10, each comprising 32 × 32 color images.The datasets contain 10, 10, 100, and 10 object or digit classes, respectively.Source: §C.2 · p. 30

C.3 MODELS

  • All models use two convolutional layers; SVHN uses two fully connected layers, while the other datasets use three.CIFAR-100 and CINIC-10 also use dropout before each fully connected layer.Source: §C.3 · p. 30

C.4 HYPERPARAMETERS

  • Learning rates are selected by a separate grid search for local and global step sizes, with CIFAR-100 alone using scheduled local-rate decay.The search selects the local rate first with the global rate fixed at 1, then tunes the global rate; CIFAR-100 halves its local rate every 1,000 rounds starting at round 10,000.Source: §C.4 · p. 30

C.5 COMPUTATION RESOURCES

  • Experiments use five random seeds per dataset and algorithm, with round counts of 2,000 for SVHN, 10,000 for CIFAR-10 and CINIC-10, and 20,000 for CIFAR-100.A 10,000-round experiment took about four hours on an RTX 3070 GPU.Source: §C.5 · p. 31

C.6.1 GENERATING PARTICIPATION PATTERNS

  • Participation heterogeneity is simulated by deriving client probabilities from class distributions, with a target mean probability of 0.1 and a minimum of 0.02.The study compares Bernoulli, Markovian, and cyclic patterns while maintaining the same stationary client probabilities; cyclic participation uses 100-round cycles with random initial offsets.Source: §C.6.1 · pp. 31–32

C.6.2 ILLUSTRATION OF DATA AND PARTICIPATION HETEROGENEITY

The block illustrates how simulated class composition relates to participation probabilities, then reports FedAU’s performance and client-wise behavior under varied participation conditions. It also examines computed weights and the choice of cutoff interval K.

C.6.2 ILLUSTRATION OF DATA AND PARTICIPATION HETEROGENEITY

  • In the illustrated simulation, client participation probabilities are computed from class distributions, and clients with more data in the class emphasized by q receive higher probabilities.FedAU itself does not know the generated participation probabilities.Source: §C.6.2 · pp. 32–33

D.1 RESULTS WITH DIFFERENT PARTICIPATION HETEROGENEITY

  • FedAU performs best among methods under the same setting across all tested degrees of CIFAR-10 participation heterogeneity.The reported differences between methods grow as heterogeneity increases, corresponding to smaller α_p.Source: §D.1 · p. 34, Table D.1.1 · p. 34

D.2 LOSS AND ACCURACY PLOTS

  • Across most rounds and datasets, FedAU performs best in the reported Bernoulli-participation plots, with slightly lower CIFAR-10 test accuracy than FedVarp and MIFA.On CIFAR-10, FedAU still has the highest training accuracy; FedVarp and MIFA require substantially more memory than FedAU.Source: §D.2 · p. 34, Figure D.2.1 · p. 34, Figure D.2.2 · p. 35

D.3 CLIENT-WISE DISTRIBUTIONS OF LOSS AND ACCURACY

  • FedAU has a smaller client-wise spread in loss and accuracy than the average-participating and average-all baselines with the same memory use.The authors interpret this as reduced bias among clients, especially with K = 50.Source: §D.3 · p. 36, Table D.3.1 · p. 36, Figure D.3.1 · p. 36

D.4 AGGREGATION WEIGHTS

  • With Bernoulli participation, FedAU’s computed weights can differ substantially from 1/p_n, especially for clients with low participation probabilities.Under cyclic participation, FedAU’s weights are more similar to those from the known-statistics baseline.Source: §D.4 · p. 36, Figure D.4.1 · p. 37, Figure D.4.2 · p. 37

D.5 CHOICE OF DIFFERENT K

  • Lowering the minimum participation probability produces more clients with very small probabilities, and the appendix compares FedAU across these bounds and different K values.For K = 10^5 with p_n ≥ 0.0, the loss is NaN.Source: §D.5 · p. 37, Figure D.5.1 · p. 38, Figure D.5.2 · p. 38

D.6 LOW PARTICIPATION RATES

With no minimum participation-probability cap, the experiments vary clients’ mean participation probability on CIFAR-10. FedAU with K = 50 performs best across a wide range of participation rates while keeping learning rates unchanged.

Further Discussion

  • FedAU with K = 50 gives the best performance across a wide range of participation rates, using unchanged learning rates.The cutoff interval limits large aggregation weights while giving frequently participating clients lower weights.Source: Table D.6.1 · p. 39, §D.6 · p. 40

LOW PARTICIPATION RATES

  • The CIFAR-10 experiments compare accuracy across mean participation probabilities with no minimum cap on client probabilities.The table reports training and test accuracy over 10,000 rounds; the probability distributions are shown as empirical CDFs with a logarithmic x-axis.Source: Table D.6.1 · p. 39, §D.6 · p. 39, Figure D.6.1 · p. 39

Key Observations

  • Most algorithms’ performance decreases as mean participation probability falls; FedVarp’s small increase from 0.01 to 0.001 is attributed to experimental randomness.The reported results are from CIFAR-10 experiments over 10,000 rounds.Source: §D.6 · p. 39, Table D.6.1 · p. 39
  • At low participation rates, FedVarp and MIFA can suffer from outdated saved updates, while inverse-probability weights can become very large and destabilize training.The authors note that 10% accuracy is random-guess performance on 10-class CIFAR-10.Source: §D.6 · p. 39
  • Average participating and average all baselines are more stable at low participation rates because their aggregation weights vary less.The authors say smaller learning rates might improve some baseline results, but tuning them to unknown participation rates is impractical and can slow convergence.Source: §D.6 · pp. 39–40

Related papers

Loading 2306.03401v3…