Anarchic Federated Learning

Haibo Yang, Xin Zhang, Prashant Khanduri, Jia Liu

Abstract

Standard Federated Learning (FL) frameworks are typically "server-centric," requiring a central coordinator to manage worker participation and synchronize local updates. This rigid structure is often incompatible with the unpredictable nature of edge devices, such as smartphones and IoT sensors, which face varying battery levels and network stability. We introduce Anarchic Federated Learning (AFL), a framework that grants edge devices total autonomy over their participation timing and local workload. We propose two algorithms—AFA-CD for cross-device settings and AFA-CS for cross-silo settings—and demonstrate that they achieve state-of-the-art convergence rates while maintaining the "linear speedup" effect.

Introduction

In conventional FL, the central server acts as a dictator, selecting workers and mandating specific update schedules. This leads to bottlenecks caused by "stragglers" and inefficient energy use. AFL flips this script by allowing "loose-coupled" workers to pull the global model, perform an arbitrary number of local steps, and push updates whenever they are ready. This paper investigates whether such a chaotic system can maintain the mathematical guarantees of convergence required for robust machine learning.

Methodology

The AFL framework is operationalized through two distinct algorithms tailored to different scales of deployment:

  1. AFA-CD (Cross-Device): Designed for massive scales involving millions of devices. To manage the inherent noise and delays of anarchic participation without tracking individual workers, the server employs "two-sided learning rates," using different scales for worker updates and server-side aggregation.
  2. AFA-CS (Cross-Silo): Optimized for smaller groups (e.g., financial or medical institutions). The server maintains a memory of the most recent update from every worker. By reusing historical data from idle workers, it performs variance reduction to stabilize training and eliminate non-vanishing error terms.

Theoretical Analysis

A central contribution of this work is the rigorous theoretical analysis of anarchic systems. The authors establish a fundamental lower bound for convergence error, proving that a certain level of error is inevitable when worker behavior is unpredictable and data is heterogeneous.

Key theoretical insights include:

  • The Anarchy Paradox: Despite the lack of coordination, AFL retains the linear speedup effect, where the time to reach a solution is roughly halved by doubling the number of workers or local steps, provided the maximum delay remains bounded.
  • The Heterogeneity Floor: In worst-case scenarios, a non-vanishing error term proportional to data heterogeneity ($\sigma_G^2$) persists. However, the memory-based approach in AFA-CS effectively mitigates this, translating anarchy into a manageable asynchronous update problem.

Experimental Evaluation

The proposed algorithms were evaluated on MNIST (Logistic Regression), CIFAR-10 (CNN), and the Shakespeare dataset (LSTM). These benchmarks were modified to simulate high data heterogeneity.

Test accuracy vs. communication rounds for varying participation levels (p).

As shown in the experimental results, the anarchic algorithms (AFA-CD and AFA-CS) perform competitively against the synchronized FedAvg baseline. While AFA-CD exhibits more noise at lower participation levels, both algorithms converge toward the baseline performance as the number of updates increases, validating the theoretical claims of robustness.

Conclusion and Future Work

Anarchic Federated Learning proves that central coordination is not a prerequisite for efficient convergence in FL. While AFA-CS offers superior stability through memory, it faces scaling challenges in cross-device scenarios. Future research will explore advanced server-side variance reduction and strategies to mitigate "biased" participation, ensuring that autonomous worker behavior does not compromise model fairness.

Summary updated

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