Improving the Transient Times for Distributed Stochastic Gradient Methods

DOI10.1109/TAC.2022.3201141MaRDI QIDQ6080216zbMATH OpenFDO

Authors Kun Huang, Shi Pu

Publication date 2 October 2023

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.04851

zbMATH Keywords

convex optimizationdistributed optimizationstochastic gradient methods

Mathematics Subject Classification ID

Systems theory; control (93-XX)

Abstract: 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=mathcalOleft(fracn1-lambd{a}_{2}ight)$, where $1-lambd{a}_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.

Recommendations

• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• A Continuous-Time Analysis of Distributed Stochastic Gradient
• Fast Distributed Gradient Methods
• Distributed stochastic gradient tracking methods
• Distributed asynchronous deterministic and stochastic gradient optimization algorithms
• Accelerated Distributed Nesterov Gradient Descent
• Random gradient extrapolation for distributed and stochastic optimization
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization
• Distributed stochastic optimization with large delays

Cited in

(1)

• An accelerated distributed stochastic gradient method with momentum

This page was built for publication: Improving the Transient Times for Distributed Stochastic Gradient Methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080216)