Distributed Stochastic Optimization with Large Delays

Zhengyuan Zhou (), Panayotis Mertikopoulos (), Nicholas Bambos (), Peter Glynn () and Yinyu Ye ()
Additional contact information
Zhengyuan Zhou: Stern School of Business, New York University, New York, New York 10012
Panayotis Mertikopoulos: Univ. Grenoble Alpes, CNRS, Inria, LIG, 38000 Grenoble, France
Nicholas Bambos: Department of Management Science and Engineering, Stanford University, Stanford, California 94305
Peter Glynn: Department of Management Science and Engineering, Stanford University, Stanford, California 94305
Yinyu Ye: Department of Management Science and Engineering, Stanford University, Stanford, California 94305

Mathematics of Operations Research, 2022, vol. 47, issue 3, 2082-2111

Abstract: The recent surge of breakthroughs in machine learning and artificial intelligence has sparked renewed interest in large-scale stochastic optimization problems that are universally considered hard. One of the most widely used methods for solving such problems is distributed asynchronous stochastic gradient descent (DASGD), a family of algorithms that result from parallelizing stochastic gradient descent on distributed computing architectures (possibly) asychronously. However, a key obstacle in the efficient implementation of DASGD is the issue of delays : when a computing node contributes a gradient update, the global model parameter may have already been updated by other nodes several times over, thereby rendering this gradient information stale. These delays can quickly add up if the computational throughput of a node is saturated, so the convergence of DASGD may be compromised in the presence of large delays. Our first contribution is that, by carefully tuning the algorithm’s step size, convergence to the critical set is still achieved in mean square, even if the delays grow unbounded at a polynomial rate. We also establish finer results in a broad class of structured optimization problems (called variationally coherent), where we show that DASGD converges to a global optimum with a probability of one under the same delay assumptions. Together, these results contribute to the broad landscape of large-scale nonconvex stochastic optimization by offering state-of-the-art theoretical guarantees and providing insights for algorithm design.

Keywords: Primary: 90C15; 90C26; secondary: 90C25; 90C05; distributed optimization; delays; stochastic gradient descent; stochastic approximation (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1200 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:2082-2111

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().