Orateur
Description
We consider decentralized optimization over a network of $n$ workers, aiming to minimize
$$
f(x) = \frac{1}{n} \sum_{i=1}^n f_i(x),
$$
where each $f_i$ is $\mu$-strongly convex and $L$-smooth. Most known convergence bounds rely on inner-outer loop structures that alternate synchronized gossip steps with (possibly randomized) local gradient updates, implicitly restricting the algorithm class to those with coordinated behavior.
Recent work, such as DADAO (Nabli & Oyallon, ICML 2023), challenges this structure by introducing a fully stochastic scheme in which both communication and computation occur according to independent Poisson clocks. This eliminates the need for synchronization or gradient tracking and achieves communication-optimal convergence at a rate of
$$
\mathcal{O} \left( n \cdot \frac{L}{\mu} \log \left( \frac{1}{\varepsilon} \right) \right),
$$though this is not optimal in terms of total complexity.
This raises an open question: Can we achieve the optimal convergence rate in decentralized settings by fully randomizing both communication and computation? The best known rate for such randomized, asynchronous (yet centralized) methods is
$$
\mathcal{O} \left( \left( \sqrt{\frac{nL}{\mu}} + n \right) \log\left( \frac{1}{\varepsilon} \right) \right),
$$ which outperforms known deterministic approaches in various regimes. However, current lower bounds are derived under structural assumptions that exclude such randomized schemes. This suggests a potential trade-off between achieving optimal communication complexity and optimal computation complexity.
This talk aims to expose this theoretical gap, revisit the assumptions underlying existing lower bounds, and discuss recent developments in randomized decentralized algorithms.
