<p>In this paper, we introduce an accelerated distributed stochastic gradient method with momentum for solving the distributed optimization problem, where a group of <i>n</i> agents collaboratively minimize the average of the local objective functions over a connected network. The method, termed “Distributed Stochastic Momentum Tracking (DSMT)”, is a single-loop algorithm that utilizes the momentum tracking technique as well as the Loopless Chebyshev Acceleration (LCA) method. We show that DSMT can asymptotically achieve comparable convergence rates as centralized stochastic gradient descent (SGD) method under a general variance condition regarding the stochastic gradients. Moreover, the number of iterations (transient times) required for DSMT to achieve such rates behaves as <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {O}(n^{5/3}/(1-\lambda ))$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>5</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">/</mo> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mi>λ</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for minimizing general smooth objective functions, and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {O}(\sqrt{n/(1-\lambda )})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msqrt> <mrow> <mi>n</mi> <mo stretchy="false">/</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>-</mo> <mi>λ</mi> <mo stretchy="false">)</mo> </mrow> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> under the Polyak-Łojasiewicz (PL) condition. Here, the term <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$1-\lambda $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>-</mo> <mi>λ</mi> </mrow> </math></EquationSource> </InlineEquation> denotes the spectral gap of the mixing matrix related to the underlying network topology. Notably, the obtained results do not rely on multiple inter-node communications or stochastic gradient accumulation per iteration, and the transient times are the shortest under the setting to the best of our knowledge.</p>

An accelerated distributed stochastic gradient method with momentum

期刊论文
发表日期：

2025年3月26日

查看全文

Kun Huang,
Shi Pu,
Angelia Nedić

摘要

In this paper, we introduce an accelerated distributed stochastic gradient method with momentum for solving the distributed optimization problem, where a group of n agents collaboratively minimize the average of the local objective functions over a connected network. The method, termed “Distributed Stochastic Momentum Tracking (DSMT)”, is a single-loop algorithm that utilizes the momentum tracking technique as well as the Loopless Chebyshev Acceleration (LCA) method. We show that DSMT can asymptotically achieve comparable convergence rates as centralized stochastic gradient descent (SGD) method under a general variance condition regarding the stochastic gradients. Moreover, the number of iterations (transient times) required for DSMT to achieve such rates behaves as $\mathcal {O}(n^{5/3}/(1-\lambda ))$ $O (n^{5 / 3} / (1 - λ))$ for minimizing general smooth objective functions, and $\mathcal {O}(\sqrt{n/(1-\lambda )})$ $O (\sqrt{n / (1 - λ)})$ under the Polyak-Łojasiewicz (PL) condition. Here, the term $1-\lambda $ $1 - λ$ denotes the spectral gap of the mixing matrix related to the underlying network topology. Notably, the obtained results do not rely on multiple inter-node communications or stochastic gradient accumulation per iteration, and the transient times are the shortest under the setting to the best of our knowledge.