# Distributed Online Optimization with Stochastic Agent Availability

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 28 references that are in the map.
- First posted on arXiv 25 Nov 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Distributed optimization over time-varying directed graphs](https://mlsanity.com/paper/1303.2289/) (2013)
- [Fast Federated Learning in the Presence of Arbitrary Device Unavailability](https://mlsanity.com/paper/2106.04159/) (2021)
- [Convergence of Update Aware Device Scheduling for Federated Learning at the Wireless Edge](https://mlsanity.com/paper/2001.10402/) (2020)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Semi-Cyclic Stochastic Gradient Descent](https://mlsanity.com/paper/1904.10120/) (2019)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Online Distributed Optimization on Dynamic Networks](https://mlsanity.com/paper/1412.7215/) (2014)
- [Distributed Online Linear Regression](https://mlsanity.com/paper/1902.04774/) (2019)
- [Distributed Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/1912.09705/) (2019)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)

## Built on by (most cited first, 3 of 3)

- [Decentralized Parameter-Free Online Learning](https://mlsanity.com/paper/2510.15644/) (2025)
- [Distributed Multi-Agent Bandits Over ErdHos-R'enyi Random Networks](https://mlsanity.com/paper/2510.22811/) (2025)
- [Decentralized Parameter-Free Online Learning with Compressed Gossip](https://mlsanity.com/paper/2605.27831/) (2026)

## Abstract (arXiv)

Motivated by practical federated learning settings where clients may not be always available, we investigate a variant of distributed online optimization where agents are active with a known probability p at each time step, and communication between neighboring agents can only take place if they are both active. We introduce a distributed variant of the FTRL algorithm and analyze its network regret, defined through the average of the instantaneous regret of the active agents. Our analysis shows that, for any connected communication graph G over N agents, the expected network regret of our FTRL variant after T steps is at most of order (kappa/p2)minbig√N,N1/4/√pbig√T, where kappa is the condition number of the Laplacian of G. We then show that similar regret bounds also hold with high probability. Moreover, we show that our notion of regret (average-case over the agents) is essentially equivalent to the standard notion of regret (worst-case over agents), implying that our bounds are not significantly improvable when p=1. Our theoretical results are supported by experiments on synthetic datasets.