A Family of Distributed Momentum Methods Over Directed Graphs With Linear Convergence
Juan Gao, Xinwei Liu, Yu‐Hong Dai, Yakui Huang, Peng Yang
Abstract
We consider the distributed optimization to minimize a sum of smooth and strongly convex local objective functions over directed graphs. Using row- and column-stochastic weights, we propose a family of distributed momentum methods. It is a parametric distributed momentum (PDM) method, for which different values of parameter can lead to different distributed momentum methods. PDM includes the distributed heavy-ball method ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {AB}m$</tex-math></inline-formula> ) and the distributed Nesterov gradient method ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {ABN}$</tex-math></inline-formula> ) as its special cases. When the step sizes and the momentum coefficient do not exceed some upper bounds, we prove that PDM can converge to the optimal solution at a global <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$R$</tex-math></inline-formula> -linear rate. The convergence result of PDM not only covers that of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {AB}m$</tex-math></inline-formula> , but also supplements that of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {ABN}$</tex-math></inline-formula> , which lacks theoretical convergence result. Simulation results on classification problems that arise in machine learning show that PDM with an appropriate negative parameter value can achieve faster acceleration than the existing distributed momentum algorithms.