Anarchic Federated Learning

Haibo Yang, Xin Zhang, Prashant Khanduri, Jia Liu

Introduction

Standard Federated Learning (FL) is inherently "server-centric." A central server acts as a coordinator, dictating which workers participate in a given round, how many local updates they must perform, and exactly when they must synchronize.

In the messy reality of edge computing, this rigid structure is highly problematic. Mobile devices and edge nodes face fluctuating battery levels, intermittent connectivity, and varying privacy constraints. Forcing a "one-size-fits-all" schedule inevitably leads to stragglers—slow devices that delay the entire training round—or wasted energy. While asynchronous FL methods exist, most still impose constraints on worker behavior or rely on strong mathematical assumptions to guarantee convergence.

This paper introduces a new paradigm called Anarchic Federated Learning (AFL). AFL asks a fundamental question: Can we let workers be "anarchic"—granting them complete freedom to choose their own timing and computational effort—without breaking the learning process? Despite this lack of central coordination, the authors prove that their proposed algorithms achieve state-of-the-art convergence rates and maintain the highly desirable "linear speedup effect."

The Anarchic Federated Averaging (AFA) Algorithms

To handle the chaotic behavior of anarchic workers, the authors propose the AFL framework and two specific algorithms under the Anarchic Federated Averaging (AFA) umbrella:

  1. AFA-CD (Cross-Device): Designed for massive networks of unreliable devices. It utilizes "two-sided" learning rates—maintaining different rates for the worker and the server—to handle the noise of chaotic participation. Crucially, it does not require the server to store any history of the workers, preserving memory efficiency.
  2. AFA-CS (Cross-Silo): Designed for a smaller, more stable set of workers (such as hospitals or banks). In this setting, the server stores the most recent update from every worker. When a worker is idle, the server reuses its "stale" historical data to perform a form of variance reduction. This stabilizes the global model update even when participation is sporadic.

Both methods handle asynchrony (workers returning at different times) and local step heterogeneity (workers doing different amounts of work) simultaneously, without requiring restrictive assumptions like a "Lipschitz Hessian."

Key Theoretical Insights

  • The Fundamental Error Ball: The authors mathematically prove a "lower bound" demonstrating that under completely general, chaotic worker arrivals, no algorithm can converge to a perfect stationary point. Instead, models converge to an "error ball" around the solution. This is the mathematical "price of anarchy."
  • Historical Data as a Stabilizer: In the cross-silo (AFA-CS) setting, simply reusing the last known update from an inactive worker can eliminate the non-vanishing error term mentioned above, allowing the model to converge to a single point despite the anarchic conditions.
  • Resilience of Linear Speedup: One of the most prized properties in distributed learning is the "linear speedup effect"—doubling the workers or local steps should ideally cut the convergence time in half. Surprisingly, AFL retains this property even when workers act entirely independently.

Empirical Results

The researchers validated their approach using three benchmark datasets commonly used in FL research: MNIST (multinomial logistic regression), CIFAR-10 (CNNs), and Shakespeare (RNN/LSTM for next-character prediction). All datasets were partitioned to be non-i.i.d. to simulate real-world data heterogeneity.

Test accuracy vs. communication rounds for FedAvg, AFA-CD, and AFA-CS across different participation levels ($p$).

In experiments, the "anarchic" AFA algorithms performed competitively with the highly-coordinated FedAvg baseline. As shown in the figure above, as the participation level or number of local steps ($p$) increases, the performance of both AFA-CD and AFA-CS closely tracks the ideal FedAvg trajectory.

Furthermore, AFL enables "loose worker-server coupling," which significantly simplifies real-world implementation. Because the server doesn't need to wait for specific devices, AFL is highly efficient in practice. For a logistic regression task on MNIST, AFL reached 85% accuracy in roughly 1/2.6 of the "wall-clock" time required by FedAvg by completely eliminating straggler bottlenecks.

Limitations and Future Work

While AFL presents a robust step forward for edge ML, the authors note a few limitations:

  • Sampling Bias: If worker participation is truly arbitrary, it might lead to bias or unfairness if certain types of devices (e.g., older phones with poor batteries) rarely participate. Modeling and mitigating this "participation bias" is a critical future direction.
  • Variance Reduction in Deep Learning: While AFA-CS worked well for simpler models, its variance reduction technique was less effective for complex CNNs on CIFAR-10, highlighting a known tricky area in deep learning optimization.
  • Practical Participation Models: The current study uses synthetic "chaotic" models. Testing AFL under real-world traces of device availability would further validate the framework's practical utility.

Summary updated

Abstract

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 achieve these goals, in this work, we propose a new FL paradigm called ``Anarchic Federated Learning'' (AFL). In stark contrast to conventional FL models, each worker in AFL has complete 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, AFL also introduces significant challenges in algorithmic design because the server needs to handle the chaotic worker behaviors. 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, even with general worker information arrival processes, we show that both AFL algorithms achieve the same convergence rate order as the state-of-the-art algorithms for conventional FL. Moreover, they retain the highly desirable {\em linear speedup effect} in the new AFL paradigm. We validate the proposed algorithms with extensive experiments on real-world datasets.
BibTeX
@inproceedings{yang2022anarchic,
  author = {Haibo Yang and Xin Zhang and Prashant Khanduri and Jia Liu},
  title = {{Anarchic Federated Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=ijygjHyhcFp},
}
Figure