Timezone: »
Poster
Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go?
Zhengyuan Zhou · Panayotis Mertikopoulos · Nicholas Bambos · Peter Glynn · Yinyu Ye · Li-Jia Li · Li Fei-Fei
One of the most widely used optimization methods for large-scale machine learning problems is distributed asynchronous stochastic gradient descent (DASGD). However, a key issue that arises here is that of delayed gradients: when a “worker” node asynchronously contributes a gradient update to the “master”, the global model parameter may have changed, rendering this information stale. In massively parallel computing grids, these delays can quickly add up if the computational throughput of a node is saturated, so the convergence of DASGD is uncertain under these conditions. Nevertheless, by using a judiciously chosen quasilinear step-size sequence, we show that it is possible to amortize these delays and achieve global convergence with probability 1, even when the delays grow at a polynomial rate. In this way, our results help reaffirm the successful application of DASGD to large-scale optimization problems.
Author Information
Zhengyuan Zhou (Stanford University)
Panayotis Mertikopoulos (CNRS)
Nicholas Bambos (Stanford University)
Peter Glynn (Stanford University)
Yinyu Ye
Li-Jia Li (Google)
Li Fei-Fei (Stanford University)
Related Events (a corresponding poster, oral, or spotlight)
-
2018 Oral: Distributed Asynchronous Optimization with Unbounded Delays: How Slow Can You Go? »
Thu. Jul 12th 09:50 -- 10:00 AM Room A9
More from the Same Authors
-
2023 Poster: Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism »
Yu-Guan Hsieh · Franck Iutzeler · Jérôme Malick · Panayotis Mertikopoulos -
2022 Poster: Nested Bandits »
Matthieu Martin · Panayotis Mertikopoulos · Thibaud J Rahier · Houssam Zenati -
2022 Poster: UnderGrad: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees »
Kimon Antonakopoulos · Dong Quan Vu · Volkan Cevher · Kfir Levy · Panayotis Mertikopoulos -
2022 Oral: UnderGrad: A Universal Black-Box Optimization Method with Almost Dimension-Free Convergence Rate Guarantees »
Kimon Antonakopoulos · Dong Quan Vu · Volkan Cevher · Kfir Levy · Panayotis Mertikopoulos -
2022 Spotlight: Nested Bandits »
Matthieu Martin · Panayotis Mertikopoulos · Thibaud J Rahier · Houssam Zenati -
2022 Poster: A Study of Face Obfuscation in ImageNet »
Kaiyu Yang · Jacqueline Yau · Li Fei-Fei · Jia Deng · Olga Russakovsky -
2022 Spotlight: A Study of Face Obfuscation in ImageNet »
Kaiyu Yang · Jacqueline Yau · Li Fei-Fei · Jia Deng · Olga Russakovsky -
2022 Poster: AdaGrad Avoids Saddle Points »
Kimon Antonakopoulos · Panayotis Mertikopoulos · Georgios Piliouras · Xiao Wang -
2022 Spotlight: AdaGrad Avoids Saddle Points »
Kimon Antonakopoulos · Panayotis Mertikopoulos · Georgios Piliouras · Xiao Wang -
2021 Poster: Online Learning for Load Balancing of Unknown Monotone Resource Allocation Games »
Ilai Bistritz · Nicholas Bambos -
2021 Spotlight: Online Learning for Load Balancing of Unknown Monotone Resource Allocation Games »
Ilai Bistritz · Nicholas Bambos -
2021 Poster: The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets »
Ya-Ping Hsieh · Panayotis Mertikopoulos · Volkan Cevher -
2021 Poster: Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach »
Nadav Hallak · Panayotis Mertikopoulos · Volkan Cevher -
2021 Spotlight: Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach »
Nadav Hallak · Panayotis Mertikopoulos · Volkan Cevher -
2021 Oral: The Limits of Min-Max Optimization Algorithms: Convergence to Spurious Non-Critical Sets »
Ya-Ping Hsieh · Panayotis Mertikopoulos · Volkan Cevher -
2021 Poster: SECANT: Self-Expert Cloning for Zero-Shot Generalization of Visual Policies »
Jim Fan · Guanzhi Wang · De-An Huang · Zhiding Yu · Li Fei-Fei · Yuke Zhu · Anima Anandkumar -
2021 Spotlight: SECANT: Self-Expert Cloning for Zero-Shot Generalization of Visual Policies »
Jim Fan · Guanzhi Wang · De-An Huang · Zhiding Yu · Li Fei-Fei · Yuke Zhu · Anima Anandkumar -
2021 Poster: Zeroth-Order Non-Convex Learning via Hierarchical Dual Averaging »
Amélie Héliou · Matthieu Martin · Panayotis Mertikopoulos · Thibaud J Rahier -
2021 Spotlight: Zeroth-Order Non-Convex Learning via Hierarchical Dual Averaging »
Amélie Héliou · Matthieu Martin · Panayotis Mertikopoulos · Thibaud J Rahier -
2020 Poster: Gradient-free Online Learning in Continuous Games with Delayed Rewards »
Amélie Héliou · Panayotis Mertikopoulos · Zhengyuan Zhou -
2020 Poster: My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits »
Ilai Bistritz · Tavor Z Baharav · Amir Leshem · Nicholas Bambos -
2020 Poster: A new regret analysis for Adam-type algorithms »
Ahmet Alacaoglu · Yura Malitsky · Panayotis Mertikopoulos · Volkan Cevher -
2020 Poster: Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games »
Tianyi Lin · Zhengyuan Zhou · Panayotis Mertikopoulos · Michael Jordan -
2020 Poster: Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits »
Nian Si · Fan Zhang · Zhengyuan Zhou · Jose Blanchet -
2019 Poster: Cautious Regret Minimization: Online Optimization with Long-Term Budget Constraints »
Nikolaos Liakopoulos · Apostolos Destounis · Georgios Paschos · Thrasyvoulos Spyropoulos · Panayotis Mertikopoulos -
2019 Oral: Cautious Regret Minimization: Online Optimization with Long-Term Budget Constraints »
Nikolaos Liakopoulos · Apostolos Destounis · Georgios Paschos · Thrasyvoulos Spyropoulos · Panayotis Mertikopoulos -
2019 Poster: Probability Functional Descent: A Unifying Perspective on GANs, Variational Inference, and Reinforcement Learning »
Casey Chu · Jose Blanchet · Peter Glynn -
2019 Oral: Probability Functional Descent: A Unifying Perspective on GANs, Variational Inference, and Reinforcement Learning »
Casey Chu · Jose Blanchet · Peter Glynn -
2018 Poster: MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels »
Lu Jiang · Zhengyuan Zhou · Thomas Leung · Li-Jia Li · Li Fei-Fei -
2018 Oral: MentorNet: Learning Data-Driven Curriculum for Very Deep Neural Networks on Corrupted Labels »
Lu Jiang · Zhengyuan Zhou · Thomas Leung · Li-Jia Li · Li Fei-Fei