PaperlayerView exact revision on arXiv

Source-linked AI summary

Anarchic Federated Learning

Haibo Yang, Xin Zhang, Prashant Khanduri, Jia Liu

arXiv:2108.09875v4cs.LGcs.DC

TL;DR

Conventional FL’s server-controlled participation can constrain workers in heterogeneous edge settings, while AFL leaves participation timing and local-step counts to workers. The paper proposes AFA-CD and AFA-CS for cross-device and cross-silo AFL, reporting linear speedup under stated participation conditions.

  • Problem

    It was unclear whether AFL algorithms could converge under worker-controlled, asynchronous participation, and under what conditions and rates.

    Source: §1 · pp. 1–2

  • Method

    The paper proposes AFA-CD and AFA-CS, two-sided-learning-rate federated averaging algorithms for cross-device and cross-silo AFL.

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

  • Results

    AFA-CD retains linear speedup in m and K, while AFA-CS’s speedup depends on total workers M rather than the m collected per round.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The proposed AFL framework permits flexible worker participation while retaining convergence guarantees under the analyzed participation conditions.

    Source: §1 · p. 2, §4.1 · p. 6, §6 · p. 8

    The stronger cross-device convergence result considers uniformly distributed worker arrivals; the section also identifies bounded delays as a condition for convergence to a stationary point.

    Source: §4.1 · p. 6

Abstract

from arXiv · show

Present-day federated learning (FL) systems deployed over edge networks consists of a large number of workers with high degrees of heterogeneity in data and/or computing capabilities, which call for flexible worker participation in terms of timing, effort, data heterogeneity, etc. To satisfy the need for flexible worker participation, we consider a new FL paradigm called "Anarchic Federated Learning" (AFL) in this paper. In stark contrast to conventional FL models, each worker in AFL has the freedom to choose i) when to participate in FL, and ii) the number of local steps to perform in each round based on its current situation (e.g., battery level, communication channels, privacy concerns). However, such chaotic worker behaviors in AFL impose many new open questions in algorithm design. In particular, it remains unclear whether one could develop convergent AFL training algorithms, and if yes, under what conditions and how fast the achievable convergence speed is. Toward this end, we propose two Anarchic Federated Averaging (AFA) algorithms with two-sided learning rates for both cross-device and cross-silo settings, which are named AFA-CD and AFA-CS, respectively. Somewhat surprisingly, we show that, under mild anarchic assumptions, both AFL algorithms achieve the best known convergence rate as the state-of-the-art algorithms for conventional FL. Moreover, they retain the highly desirable {\em linear speedup effect} with respect of both the number of workers and local steps in the new AFL paradigm. We validate the proposed algorithms with extensive experiments on real-world datasets.

1. Introduction

Conventional FL’s server-directed participation can be restrictive in heterogeneous edge networks, motivating AFL, where workers independently choose when to participate and how many local steps to perform. The paper introduces AFA-CD and AFA-CS and analyzes their convergence and speedup under conditions on worker participation.

1. Introduction

  • Server-centric FL assumes workers are available for complete rounds and follow shared timing and local-step schedules, which can be restrictive on edge networks.Unavailable devices, stragglers, wasted computation, and synchronous networking overhead motivate flexible participation.Source: §1 · pp. 1–2
  • AFL lets each worker choose participation timing and local-step count, while asynchronous, heterogeneous worker behavior makes server-side algorithm design challenging.Workers may base local steps on battery, communication, or privacy conditions.Source: §1 · p. 2
  • AFA-CD matches the fundamental lower bound with an O(1/(mKT)) convergence rate and linear speedup in collected workers m and local steps K under bounded maximum delay.Here, T is the number of global rounds; the rate applies to the cross-device setting.Source: §1 · p. 2
  • AFA-CS achieves linear speedup with a factor depending on all M workers rather than the m workers collected per round.The passage gives the rate as O(1/(MKT)); M > m.Source: §1 · p. 2
  • The paper also validates AFA on computer-vision and NLP tasks and explores asynchrony, local steps, and integration with FedProx and SCAFFOLD.The introduction reports extensive experiments but does not give their specific outcomes here.Source: §1 · p. 2

2. Related Work

Prior flexible-participation FL methods typically accommodate selected forms of heterogeneity, while retaining restrictions such as synchronous communication, identical local steps, or constrained worker availability. The paper positions AFL as combining worker-controlled local computation with asynchronous communication and reports AFA convergence without some assumptions used in related work.

1) Server-Centric FL Algorithms

  • FedAvg follow-ups address model drift from heterogeneous data and multiple local steps, but remain server-centric and synchronous.Examples include FedProx, SCAFFOLD, FedNova, FedDyn, and MIME.Source: §2 · p. 3

2) FL with Flexible Worker Participation

  • Earlier flexible-participation approaches are grouped into methods varying local steps synchronously, asynchronous methods with identical local steps, and methods allowing unavailability but retaining a common clock.The cited examples include AsyncCommSGD and buffered asynchronous aggregation; the passage notes differing assumptions and convergence guarantees.Source: §2 · p. 3

3) Key Differences of AFL from Related Works

  • AFL combines different local-step counts and asynchronous communication, with participation and local optimization determined by workers rather than server sampling.The paper describes AFL as subsuming the related settings discussed in this section as special cases.Source: §2 · p. 3
  • The paper reports that AFA achieves the same convergence rate without strong assumptions such as the Lipschitz Hessian condition used by Gu et al. (2021).The related-work discussion contrasts this with prior methods’ assumptions.Source: §2 · p. 3

3. Anarchic Federated Learning

AFL is a federated-learning architecture in which workers participate and compute independently, while a concurrent server collects and aggregates their updates. The section establishes a convergence lower bound for general worker arrivals and explains that stronger convergence requires additional assumptions on participation.

3. Anarchic Federated Learning

  • Cross-device FL has many workers and limited capacity to retain their information across rounds, whereas cross-silo FL has fewer workers and can store each worker’s latest information.The objective averages the local losses associated with workers’ data distributions, which may differ across workers.Source: §3 · p. 3
  • AFL workers pull the current model when they choose to participate, perform local updates, and return results with timestamps; server collection and aggregation proceed concurrently.The server aggregates after a condition such as collecting m updates, while worker processes remain independent of that schedule.Source: §3 · pp. 3–4
  • The analysis assumes Lipschitz-continuous gradients, unbiased local stochastic gradients, and bounded local and global gradient variances.The global variance bound is used to quantify data heterogeneity across workers.Source: §3 · p. 4
  • With general independent worker-arrival processes, the paper establishes a convergence-error lower bound using a worst-case participation process.The bound applies to loss functions satisfying the section’s stated assumptions; the authors attribute unavoidable error to objective drift from worker participation.Source: §3 · p. 4
  • The lower bound applies under general worker arrivals, and the paper identifies uniformly distributed arrivals and bounded delays as additional conditions for stationary-point convergence.The authors distinguish participation-driven objective deviations from optimization error under ideal participation.Source: §3 · pp. 4–5

4. The Anarchic Federated Averaging (AFA) Algorithms for AFL

The paper extends FedAvg to anarchic federated learning through AFA-CD for cross-device settings and AFA-CS for cross-silo settings. Their convergence guarantees depend on worker-arrival conditions, bounded delay, and learning-rate choices; AFA-CS also reuses stored worker updates.

4.1. The AFA-CD Algorithm for Cross-Device AFL

  • AFA-CD uses SGD on both sides, collects m delayed worker updates per round, and lets each participating worker choose its number of local steps.Workers return rescaled sums of stochastic gradients; the server aggregates the collected updates.Source: §4.1 · p. 5
  • With bounded maximum delay and sufficiently small learning rates, AFA-CD converges to a neighborhood around a stationary point under general worker-arrival processes.With a constant local-step count and appropriate rates, its convergence has linear speedup in m and K; the non-vanishing error term matches the lower bound when workers set ηL = 1/√T.Source: §4.1 · p. 6
  • Under uniformly distributed worker arrivals, AFA-CD achieves linear speedup to a stationary point at O(1/(√m√K√T)) for sufficiently large T.The stated rate no longer depends on delay after sufficiently many rounds.Source: §4.1 · p. 6

4.2. The AFA-CS Algorithm for Cross-Silo AFL

  • AFA-CS stores each worker’s latest update and aggregates the stored updates whenever m new updates arrive.The worker code is the same as AFA-CD; the cross-silo server can retain historical feedback because the setting has relatively few workers.Source: §4.2 · p. 7
  • AFA-CS eliminates the non-vanishing O(σ^2_G) error term under general worker arrivals and bounded delay by reusing historical updates, with a linear speedup in M even when only m workers participate per round.The passage says this rate is tight against a lower bound.Source: §4.2 · pp. 7–8

5. Numerical results

Across logistic regression on MNIST, CNN on CIFAR-10, and RNN on Shakespeare, AFA-CD and AFA-CS with general worker arrivals achieve test accuracy comparable to or nearly the same as FedAvg. The experiments also report robustness to asynchrony and heterogeneity factors.

5. Numerical results

  • AFA-CD and AFA-CS with general worker arrivals achieve test accuracy comparable to or nearly the same as FedAvg.The experiments cover logistic regression on manually partitioned non-i.i.d. MNIST, CNN on CIFAR-10, and RNN on Shakespeare.Source: §5 · p. 8, Figure 1 · p. 8
  • AFA algorithms are reported to be robust against asynchrony and heterogeneity factors, including when paired with FedProx and SCAFFOLD as worker-side optimizers.For LR on MNIST, asynchrony and dynamic local steps produce zigzagging curves, while final accuracy differences are negligible; the zigzagging is more pronounced at higher non-i.i.d. levels.Source: §5 · p. 8

6. Conclusions

The conclusion presents AFL as a lower-coordination alternative to tightly coupled conventional FL, with flexible worker participation. It reports AFA-CD and AFA-CS and says they retain linear speedup.

6. Conclusions

  • AFL allows flexible worker participation with lower server-worker coordination complexity than tightly coupled conventional FL.The conclusion also reports that the framework works numerically with FedProx and SCAFFOLD as worker-side optimizers.Source: §6 · p. 8
  • The paper proposes AFA-CD and AFA-CS, two Anarchic Federated Averaging algorithms with two-sided learning rates for cross-device and cross-silo settings.The conclusion says both retain the linear speedup effect in AFL.Source: §6 · p. 8

A. Proofs of Lemma 1 and Lemma 2

The appendix begins the proofs with two lemmas concerning local-update estimates and a fixed set of selected workers.

A. Proofs of Lemma 1 and Lemma 2

B. Proof of the performance of the AFA-CD algorithm

This section establishes a lower bound for AFL under general worker information arrivals, then proves it using a two-worker worst-case construction.

B. Proof of the performance of the AFA-CD algorithm

  • The analysis treats general arrivals with only independence of worker participation, while uniform arrivals are sampled independently without replacement.The uniform-arrival case is introduced as a separate analysis setting.Source: B. Proof of the performance of the… · p. 12

B.1. Lower Bound for General Worker Information Arrival Processes

  • Theorem 1 gives a convergence-error lower bound for AFL under general worker information arrival processes and any heterogeneity level σG.It asserts that suitable loss functions and a participation process force the bound for any convergent algorithm.Source: §B.1 · p. 12
  • The proof uses two workers with quadratic losses and a participation process in which only the first worker trains.The resulting algorithm optimizes that worker’s loss rather than the global objective.Source: §B.1 · p. 12
  • For this construction, any convergent algorithm returns an expected output of −G, yielding global gradient error Ω(σG^2).The workers’ squared gradient deviations from the global gradient are bounded by σG^2.Source: §B.1 · p. 12

B.2. General Worker Information Arrival Processes

This section analyzes AFA-CD with general worker information arrivals. Under bounded delay and suitable learning-rate conditions, it establishes convergence bounds and a linear-speedup corollary for a fixed local-step count.

B.2. General Worker Information Arrival Processes

  • Under Assumptions 1–3, AFA-CD with general worker information arrival processes has an output sequence satisfying the theorem’s stated conclusion when its resultant maximum delay under AFL is finite (τ < ∞) and learning rates meet stated conditions.Source: §B.2 · p. 12
  • The proof bounds the update using smoothness, bounded global variance, maximum delay, and the maximum local-step count K.It also invokes a bound on local parameter changes based on prior work.Source: §B.2 · pp. 13–15
  • For a constant local-step count K, Corollary 1 gives a linear-speedup convergence rate to an error ball with ηL set proportional to 1/√(mK).Here m is the number of participating workers in the corollary’s rate statement.Source: §B.2 · p. 16

B.3. Uniformly Distributed Worker Information Arrivals

This section analyzes AFA-CD when worker information arrivals are uniformly sampled without replacement. Under the stated delay and learning-rate conditions, it establishes convergence and a linear-speedup corollary to a stationary point.

B.3. Uniformly Distributed Worker Information Arrivals

  • Under the same delay condition as Theorem 2 and the stated learning-rate conditions, AFA-CD with uniform arrivals satisfies the theorem’s convergence bound.The case treats each round’s participating workers as a uniformly random sample without replacement.Source: §B.3 · p. 17
  • The proof uses the uniform independent arrival assumption alongside the delay bound to control the update terms.The one-step update is written as xt+1 − xt = −ηηL Gt; with zero delay, the stated update reduces to synchronous FL with partial worker participation.Source: §B.3 · pp. 17–18
  • For a constant local-step count K, Corollary 2 gives a linear-speedup convergence rate to a stationary point with ηL set proportional to 1/√(mK).The uniform-arrival case is presented as a widely used FL assumption for understanding performance in large-scale AFL systems.Source: §B.3 · pp. 17, 22

C. Proof of the performance results of the AFA-CS algorithm

AFA-CS is analyzed under assumptions for general worker-information arrivals, with a bounded-delay condition for its stated convergence result. The discussion connects its server-side variance reduction to reduced convergence error and notes a remaining error source under arbitrary sampling with non-i.i.d. data.

C. Proof of the performance results of the AFA-CS algorithm

  • With bounded maximum delay, the AFA-CS analysis gives a convergence result for general worker-information arrivals.The proof groups worker gradient returns into delayed and non-delayed updates.Source: C. Proof of the performance results of… · pp. 22, 26
  • Under Assumptions 1–3, AFA-CS satisfies a convergence bound for general worker-information arrival processes.The bound uses constants αL and αG; the supplied passages do not provide their complete definitions or the full rate expression.Source: C. Proof of the performance results of… · p. 22

D. Discussion

  • With arbitrary independent sampling and non-i.i.d. data, the surrogate objective can deviate from the global objective by a non-vanishing amount, motivating further study of participation modeling and potential bias.The discussion distinguishes this source of error from objective inconsistency caused by different local-step counts.Source: D. Discussion · p. 27
  • AFA-CS stores a gradient estimate for each worker and updates the global model using all workers’ stored estimates, although each round receives only m updates.The discussion characterizes this server-side variance reduction as a way to diminish convergence error and accelerate convergence with a linear speedup factor M; it says this approach is orthogonal to worker-side variance reduction.Source: D. Discussion · p. 27

E. Experiments

  • The appendix section provides detailed experimental settings and additional results that did not fit in the main paper.Source: E. Experiments · p. 27

E.1. Model and Datasets

The experiments use three models across image and text benchmarks, with controlled non-i.i.d. partitions and several simulated forms of worker heterogeneity. The authors frame the evaluation as a comparison with FedAvg and report communication rounds rather than wall-clock time.

E.1. Model and Datasets

  • Experiments cover logistic regression on MNIST, a CNN on CIFAR-10, and an RNN on Shakespeare.The datasets are described as benchmarks used in prior federated-learning studies.Source: §E.1 · p. 27
  • For MNIST and CIFAR-10, workers receive data from randomly chosen classes; p=2 gives two classes per worker, while p=10 is nearly i.i.d.The setup distributes data across 10 or 100 workers with equal training and test sample counts per worker.Source: §E.1 · p. 28
  • The Shakespeare task predicts the next character from 80-character sequences using a two-layer LSTM with 100 hidden units.The model embeds characters into an 8-dimensional space and predicts among 80 character classes.Source: §E.1 · p. 28
  • The authors aim to show performance comparable to FedAvg and measure communication rounds rather than wall-clock time.For LR/MNIST with p=1, the stated rounds-to-85%-accuracy ratio is 61/46, while the wall-clock-time ratio is 1/2.6 for AFL/FedAvg.Source: §E.1 · p. 28
  • The evaluation simulates asynchronous updates, constant or dynamic local steps, uniform or biased worker arrivals, and varying image-data heterogeneity.For asynchronous updates, workers choose among the five most recent global models; dynamic local steps are sampled uniformly from [1, 2 × c].Source: §E.1 · p. 28

E.2. Further experimental results

Across the examined tasks, asynchrony and dynamic local steps produce accuracy comparable to synchronous constant-step training, while greater data heterogeneity can lower accuracy and slow convergence. FedProx retains performance in AFL, but SCAFFOLD and biased worker sampling show task- or setting-dependent limitations.

E.2. Further experimental results

  • Asynchrony and dynamic local steps show no obvious top-1 accuracy differences from synchronous constant steps across three tasks, while increasing non-i.i.d. levels lowers accuracy.The comparison uses uniformly random worker sampling; smaller p denotes greater non-i.i.d. level.Source: §E.2 · p. 29, Table 2 · p. 29
  • Asynchrony and dynamic steps yield zigzagging accuracy curves, especially at higher non-i.i.d. levels, and greater non-i.i.d. levels take more rounds to converge.For less non-i.i.d. settings (p = 10 and p = 5), curves are almost identical; the LSTM curves oscillate under asynchrony and dynamic steps.Source: §E.2 · p. 29, Figure 2 · p. 30, Figure 3 · p. 31
  • FedProx performs as well as FedAvg and shows no performance degradation in AFL, whereas SCAFFOLD performs poorly on CNN for CIFAR-10, especially at higher non-i.i.d. levels.The authors suggest stale control variates during partial worker participation as one possible reason for SCAFFOLD's CIFAR-10 results.Source: §E.2 · pp. 29, 31, Table 3 · p. 30
  • Biased worker sampling degrades performance for highly non-i.i.d. data (p = 1), but not significantly for p = 2, 5, or 10; AFA-CS works on MNIST but not CIFAR-10 in this setting.The authors conjecture that variance reduction does not always work well in practice.Source: §E.2 · p. 32, Figure 5 · p. 32, Figure 6 · p. 33

Related papers

Loading 2108.09875v4…