A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order

By Xiangru Lian, Huan Zhang, Cho-Jui Hsieh, Yijun Huang, Ji Liu. 2016

124 citations recorded by the source corpus.

Asynchronous parallel optimization received substantial successes and extensive attention recently. One of core theoretical questions is how much speedup (or benefit) the asynchronous parallelization can bring us. This paper provides a comprehensive and generic analysis to study the speedup property for a broad range of asynchronous parallel stochastic algorithms from the zeroth order to the first order methods. Our result recovers or improves existing analysis on special cases, provides more insights for understanding the asynchronous parallel behaviors, and suggests a novel asynchronous parallel zeroth order method for the first time. Our experiments provide novel applications including model blending problems using the proposed asynchronous parallel zeroth order method.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Optimization & Training, Statistical Learning Theory, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Optimization & Training

In Statistical Learning Theory

In Mathematical Optimization

Citations in the corpus

Asynchronous Decentralized Parallel Stochastic Gradient Descent (2017, methodology): “The Asynchronous Parallel Stochastic Gradient Descent ( A-PSGD ) [Agarwal and Duchi, 2011, Feyzmah-davian et al., 2016, Paine et al., 2013, Recht et al., 2011] breaks the synchronization in S-PSGD.”
ZOO: Zeroth Order Optimization Based Black-box Attacks to Deep Neural Networks without Training Substitute Models (2017, methodology): “imization algorithms like gradient descent or coordinate descent can be applied using the estimated gradients. The convergence of these zeroth order methods has been proved in optimization literature [11, 25, 32], and under mild assumptions (smoothness and Lipschitzian gradient) they can converge to”
A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning: Principals, Recent Advances, and Applications (2020, methodology): “ZO-SCD [34] NC, UnCons Two-point CooGE*”
Asynchronous Byzantine Machine Learning (2018, background): “M L ] 9 J u l 2018 cation delays (Lian et al., 2016; Liu et al., 2015; Ho et al., 2013; Li et al., 2014a).”
A Linear Speedup Analysis of Distributed Deep Learning with Sparse and Quantized Communication (2018, methodology): “This metric is conventionally used in the analysis for non-convex optimization [17, 32, 31].”
More Iterations per Second, Same Quality - Why Asynchronous Algorithms may Drastically Outperform Traditional Ones (2017, unknown): “In [19], the authors review a number of asynchronous algorithm analyses and collect conditions necessary for linear speedup on a ﬁxed problem.”
HogWild++: A New Mechanism for Decentralized Asynchronous Stochastic Gradient Descent (2016, background): “[11] proposed a comprehensive convergence analysis for asynchronous algorithms.”