Distributed Online Optimization with Stochastic Agent Availability
This addresses the problem of federated learning with intermittent client connectivity for practitioners, representing an incremental improvement by adapting existing methods to stochastic availability.
The paper tackles distributed online optimization with stochastic agent availability, introducing a variant of the FTRL algorithm that achieves an expected network regret of order (κ/p^2)min{√N, N^{1/4}/√p}√T, where κ is the condition number, N is the number of agents, p is the availability probability, and T is the time steps, with results validated on synthetic datasets.
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 $(κ/p^2)\min\big\{\sqrt{N},N^{1/4}/\sqrt{p}\big\}\sqrt{T}$, where $κ$ 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.