Improving the Transient Times for Distributed Stochastic Gradient Methods
This work addresses the challenge of slow initial convergence in distributed stochastic gradient methods for multi-agent systems, representing an incremental improvement in algorithm design.
The paper tackles the problem of distributed optimization with stochastic gradients by proposing the EDAS algorithm, which achieves the same asymptotic convergence rate as centralized SGD for strongly convex and smooth functions and characterizes a transient time of O(n/(1-λ₂)), claimed to be the shortest known.
We consider the distributed optimization problem where $n$ agents each possessing a local cost function, collaboratively minimize the average of the $n$ cost functions over a connected network. Assuming stochastic gradient information is available, we study a distributed stochastic gradient algorithm, called exact diffusion with adaptive stepsizes (EDAS) adapted from the Exact Diffusion method and NIDS and perform a non-asymptotic convergence analysis. We not only show that EDAS asymptotically achieves the same network independent convergence rate as centralized stochastic gradient descent (SGD) for minimizing strongly convex and smooth objective functions, but also characterize the transient time needed for the algorithm to approach the asymptotic convergence rate, which behaves as $K_T=\mathcal{O}\left(\frac{n}{1-λ_2}\right)$, where $1-λ_2$ stands for the spectral gap of the mixing matrix. To the best of our knowledge, EDAS achieves the shortest transient time when the average of the $n$ cost functions is strongly convex and each cost function is smooth. Numerical simulations further corroborate and strengthen the obtained theoretical results.