A Distributed Asynchronous Generalized Momentum Algorithm Without Delay Bounds

Ellie Pond, Yichen Zhao, Matthew Hale · 2025

Read A Distributed Asynchronous Generalized Momentum Algorithm Without Delay Bounds by Ellie Pond, Yichen Zhao, Matthew Hale (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08218.txt.

Introduction

Ellie Pond, Yichen Zhao, and Matthew Hale design a distributed optimization method that needs no delay bounds in a paper from two thousand twenty-five. In distributed computing, workers update at uneven pace, and proofs often assume delays stay capped. Real caps are hard to know.

Their generalized momentum method covers classic schemes like heavy ball and Nesterov's method as special cases. It allows any finite delay. The authors first give settings that guarantee the method settles, then show its speed grows linearly with work done. In tests on a text sorting task with unbounded delays, it beat plain descent by over a third in rounds and also beat both classic rivals.

Catalog record

CREATOREllie Pond, Yichen Zhao, Matthew Hale
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE75 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08218

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Distributed Asynchronous Generalized Momentum Algorithm Without Delay Bounds Ellie Pond, Yichen Zhao, Matthew Hale Abstract Asynchronous optimization algorithms often require delay bounds to prove their convergence, though these bounds can be difficult to obtain in practice. Therefore, we introduce a novel distributed generalized momentum algorithm that provides fast convergence and allows arbitrary finite delays. It subsumes Nesterov’s accelerated gradient algorithm and the heavy ball algorithm, among others. We first develop conditions on the parameters of this algorithm that ensure asymptotic convergence. Then we show its convergence rate is linear in a function of the number of computations and communications that processors perform (in a way that we make precise). Simulations compare this algorithm to gradient descent, heavy ball, and Nesterov’s accelerated gradient algorithm with a text classification problem on the 20 newsgroups dataset. Across a range of scenarios with unbounded delays, the generalized momentum algorithm converges with at least 36 % \% fewer iterations than gradient descent, 28 % \% fewer iterations than the heavy ball algorithm, and 16 % \% fewer iterations that Nesterov’s accelerated gradient algorithm. I Introduction Large-scale convex optimization problems arise in several fields, including robotics [ 1 , 2 , 3 ] , machine learning [ 4 , 5 , 6 ] , and communications [ 7 , 8 , 9 ] . Parallel algorithms are commonly used to solve these problems [ 10 , 11 , 12 , 13 ] . Work in [ 14 ] established three categories for parallelized algorithms: (i) “synchronous”, in which all processors compute and communicate at every iteration, (ii) “partially asynchronous”, in which all processors must compute and communicate at least once within intervals of a specified length, and (iii) “totally asynchronous”, in which there may be arbitrarily long delays between successive computations and communications performed by each processor. Synchronous algorithms are often slowed by the “straggler penalty,” which results from processors idling while waiting for the slowest processor to finish computing and/or communicating [ 15 , 14 ] . Partially asynchronous algorithms can avoid the straggler penalty, but they assume both the existence and knowledge of a bound on all delays, which does not always hold. Totally asynchronous algorithms are more flexible because they permit arbitrarily long delays in communications and computations. However, existing totally asynchronous algorithms have largely used gradient descent (GD) [ 16 ] which can converge slowly. In this work, we therefore develop a totally asynchronous generalized momentum (GM) algorithm. Total asynchrony allows processors to have arbitrarily long delays (i) between successive computations, (ii) between computing a new iterate and communicating it to other processors, and (iii) between when an iterate is sent to another processor and when it is received by that processor. The GM algorithm includes the heavy ball (HB) algorithm [ 17 ] and Nesterov’s accelerated gradient (NAG) algorithm [ 18 ] as special cases. We apply the techniques of [ 14 , Chapter 6] to show that the GM algorithm converges linearly under total asynchrony. This approach shows that an update law converges asymptotically under total asynchrony if it is an \infty- norm contraction. The GM update law is generally not an \infty -norm contraction, but we show that applying it twice is. We therefore present a two-step GM algorithm and prove its convergence. It was shown in [ 14 ] that convergence under total asynchrony requires some form of diagonal dominance of the Hessian of the objective function. We likewise enforce a diagonal dominance condition and our analysis shows how our choice of algorithm interacts with this property to ensure convergence. I-A Summary of Main Contributions To summarize, our contributions are: • A novel totally asynchronous momentum algorithm guaranteed to converge under arbitrarily long delays in computations and communications (Algorithm 1 ). • Bounds on algorithm parameters that ensure convergence is linear in a certain function of the number of computations and communications that processors complete (Theorems 1 - 3 ). • Bounds on the minimum number of computations and communications that must be performed to converge within a given distance of an optimum (Theorem 4 ). • Numerical results that show Algorithm 1 requires at least 36 \% fewer iterations than GD, 28 \% fewer iterations than HB, and 16 \% fewer iterations than NAG on a text classification task (Section VI ). I-B Related Work There is a large body of literature on partially asynchronous optimization algorithms, and a representative sample includes [ 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 ] . As noted above, the convergence of these algorithms requires knowledge of a fixed bound on all delays in all processors’ computations and communications. Such a bound may not be known or even exist (e.g., if delays grow over time), which precludes the use of those algorithms. We focus on total asynchrony because it does not require the existence of such a delay bound to guarantee the convergence of an algorithm. Existing totally asynchronous algorithms include a projected GD algorithm [ 14 ] , the HB algorithm [ 31 ] , and the NAG algorithm [ 32 ] . Algorithm 1 in this paper subsumes all of these algorithms as special cases, and we empirically show that Algorithm 1 converges faster than all of them. Additional work in [ 33 ] presents an asynchronous algorithm based on Newton’s method in which consecutive computations can have arbitrary delays between them. However, processors’ communications are assumed to be received immediately in that work, while we allow arbitrarily long delays between when a message is sent and when it is received. The algorithm in [ 33 ] therefore lacks convergence guarantees under the conditions that we consider and we do not empirically compare to it. A similar statement applies to [ 34 ] . In the centralized setting, it has been widely shown that momentum algorithms converge faster than gradient descent [ 35 , 36 , 37 , 38 , 39 , 40 , 41 ] . We bring this same acceleration to the totally asynchronous setting for the first time, and empirically demonstrate the computational speed-up obtained when using our proposed algorithm compared to existing algorithms that do not impose delay bounds. II Preliminaries and Problem Statements This section defines notation, reviews the generalized momentum algorithm, and states the problems we solve. II-A Notation The real, non-negative real, and natural numbers are denoted by \mathbb{R} , \mathbb{R}_{\geq 0} , and \mathbb{N} respectively. We use \Pi_{\mathcal{X}}:\mathbb{R}^{n}\rightarrow\mathcal{X} to denote the orthogonal projection onto a non-empty, closed, convex set \mathcal{X}\subset\mathbb{R}^{n} , i.e., \Pi_{\mathcal{X}}(y)=\argmin_{x\in\mathcal{X}}\|x-y\|_{2} . For x\in\mathbb{R}^{n} , the \infty -norm is \|x\|_{\infty}=\max_{i\in\{1,\ldots,n\}}|x_{i}| . The Frobenius norm is defined as \|A\|_{F}=\text{trace}(A^{T}A)^{1/2} for a matrix A\in\mathbb{R}^{m\times n} . We use |\cdot| to denote the cardinality of a set. The column operator for a,b\in\mathbb{R}^{n} is \textnormal{col}(a,b)=\begin{bmatrix}a^{T}&b^{T}\end{bmatrix}^{T}\in\mathbb{R}^{2n} . For f:\mathbb{R}^{n}\to\mathbb{R} , we define \nabla_{i}f=\frac{\partial f}{\partial x_{i}} . II-B The Generalized Momentum Algorithm Given an objective function f:\mathbb{R}^{n}\rightarrow\mathbb{R} and a constraint set \mathcal{X}\subset\mathbb{R}^{n} , we consider the optimization problem \operatorname{minimize}_{x\in\mathcal{X}}\,\,f(x) . This problem can be solved by the centralized generalized momentum algorithm [ 42 ] : at timestep l\in\mathbb{N} the decision variable x(l)\in\mathbb{R}^{n} is updated according to x(l+1)=\Pi_{\mathcal{X}}\Big[x(l)-\gamma\nabla f\Big(x(l)+\lambda\big(x(l)-x(l-1)\big)\Big)\\

Read the complete text