# Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

arXiv: https://arxiv.org/abs/2603.26231 · HTML: https://mlsanity.com/paper/2603.26231/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 67 references that are in the map.
- First posted on arXiv 27 Mar 2026.

## Builds on (most cited first, 11 of 11)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Asynchronous Federated Optimization](https://mlsanity.com/paper/1903.03934/) (2019)
- [Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity](https://mlsanity.com/paper/2501.16168/) (2025)
- [DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization](https://mlsanity.com/paper/2202.01268/) (2022)
- [Adaptive Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2211.00188/) (2022)
- [Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays](https://mlsanity.com/paper/2106.12261/) (2021)
- [More Iterations per Second, Same Quality -- Why Asynchronous Algorithms may Drastically Outperform Traditional Ones](https://mlsanity.com/paper/1708.05136/) (2017)
- [MindFlayer SGD: Efficient Parallel SGD in the Presence of Heterogeneous and Random Worker Compute Times](https://mlsanity.com/paper/2410.04285/) (2024)
- [Asynchronous Multi-Server Federated Learning for Geo-Distributed Clients](https://mlsanity.com/paper/2406.01439/) (2024)
- [FuSeFL: Fully Secure and Scalable Federated Learning](https://mlsanity.com/paper/2507.13591/) (2025)

## Abstract (arXiv)

Synchronous federated learning scales poorly due to the straggler effect. Asynchronous algorithms increase the update throughput by processing updates upon arrival, but they introduce two fundamental challenges: gradient staleness, which degrades convergence, and bias toward faster clients under heterogeneous data distributions. Although algorithms such as AsyncSGD and Generalized AsyncSGD mitigate this bias via client-side task queues, most existing analyses neglect the underlying queueing dynamics and lack closed-form characterizations of the update throughput and gradient staleness. To close this gap, we develop a stochastic queueing-network framework for Generalized AsyncSGD that jointly models random computation times at the clients and the central server, as well as random uplink and downlink communication delays. Leveraging product-form network theory, we derive a closed-form expression for the update throughput, alongside closed-form upper bounds for both the communication round complexity and the expected wall-clock time required to reach an ε-stationary point. These results formally characterize the trade-off between gradient staleness and wall-clock convergence speed. We further extend the framework to quantify energy consumption under stochastic timing, revealing an additional trade-off between convergence speed and energy efficiency. Building on these analytical results, we propose gradient-based optimization strategies to jointly optimize routing and concurrency. Experiments on EMNIST demonstrate reductions of 29%--46% in convergence time and 36%--49% in energy consumption compared to AsyncSGD.