Timezone: »

 
Poster
Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays
Konstantin Mishchenko · Francis Bach · Mathieu Even · Blake Woodworth

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #331
in Poster Session 3 »

The existing analysis of asynchronous stochastic gradient descent (SGD) degrades dramatically when any delay is large, giving the impression that performance depends primarily on the delay. On the contrary, we prove much better guarantees for the same asynchronous SGD algorithm regardless of the delays in the gradients, depending instead just on the number of parallel devices used to implement the algorithm. Our guarantees are strictly better than the existing analyses, and we also argue that asynchronous SGD outperforms synchronous minibatch SGD in the settings we consider. For our analysis, we introduce a novel recursion based on ``virtual iterates'' and delay-adaptive stepsizes, which allow us to derive state-of-the-art guarantees for both convex and non-convex objectives.

Keywords: Optimization · Non-Convex · stochastic · Asynchronous · Convex · Parallel

Author Information

Konstantin Mishchenko (CNRS)
Francis Bach (INRIA - Ecole Normale Superieure)

Francis Bach is a researcher at INRIA, leading since 2011 the SIERRA project-team, which is part of the Computer Science Department at Ecole Normale Supérieure in Paris, France. After completing his Ph.D. in Computer Science at U.C. Berkeley, he spent two years at Ecole des Mines, and joined INRIA and Ecole Normale Supérieure in 2007. He is interested in statistical machine learning, and especially in convex optimization, combinatorial optimization, sparse methods, kernel-based learning, vision and signal processing. He gave numerous courses on optimization in the last few years in summer schools. He has been program co-chair for the International Conference on Machine Learning in 2015.

Mathieu Even (INRIA)
Blake Woodworth (Inria)

More from the Same Authors