Improved asynchronous parallel optimization analysis for stochastic incremental methods

By Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien. 2018

78 citations recorded by the source corpus.

As datasets continue to increase in size and multi-core computer architectures are developed, asynchronous parallel optimization algorithms become more and more essential to the field of Machine Learning. Unfortunately, conducting the theoretical analysis asynchronous methods is difficult, notably due to the introduction of delay and inconsistency in inherently sequential algorithms. Handling these issues often requires resorting to simplifying but unrealistic assumptions. Through a novel perspective, we revisit and clarify a subtle but important technical issue present in a large fraction of the recent convergence rate proofs for asynchronous parallel optimization algorithms, and propose a simplification of the recently introduced "perturbed iterate" framework that resolves it. We demonstrate the usefulness of our new framework by analyzing three distinct asynchronous parallel incremental optimization algorithms: Hogwild (asynchronous SGD), KROMAGNON (asynchronous SVRG) and ASAGA, a novel asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. We are able to both remove problematic assumptions and obtain better theoretical results. Notably, we prove that ASAGA and KROMAGNON can obtain a theoretical linear speedup on multi-core systems even without sparsity assumptions. We present results of an implementation on a 40-core architecture illustrating the practical speedups as well as the hardware overhead. Finally, we investigate the overlap constant, an ill-understood but central quantity for the theoretical analysis of asynchronous parallel algorithms. We find that it encompasses much more complexity than suggested in previous work, and often is order-of-magnitude bigger than traditionally thought.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

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 Mechanics

In Optimization & Training

Citations in the corpus

Robust Aggregation for Federated Learning (2019, background): “Recent work includes primal-dual frameworks [62, 80] and variants suited to decentralized [37], and asynchronous [52] settings.”
Communication trade-offs for synchronized distributed SGD with large step size (2019, neutral): “…Keuper and Pfreundt (2015); De and Goldstein (2015); Feyzmahdavian et al. (2015); Lian et al. (2015); Mania et al. (2015); Zhao and Li (2015); Duchi et al. (2015); Chen et al. (2016a); Lian et al. (2017a); Pedregosa et al. (2017); Lian et al. (2017b); Leblond et al. (2018); Alistarh et al. (2018).”
Sparsified SGD with Memory (2018, background): “Asynchronous updates provide an alternative solution to disguise the communication overhead to a certain amount [19].”
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption (2018, methodology): “With this deﬁnition of ∆ it is an easy exercise to show that for iid ξ 1 and ξ 2 in a ﬁnite-sum setting (i.e., ξ i and ξ 2 can only take on a ﬁnite set of possible values) we have (see Proposition 10 in (Leblond et al., 2018)).”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “This technique is based on ideas of the perturbed iterate analysis (Mania et al., 2017; Leblond et al., 2018) in combination with standard estimates (Nesterov, 2004).”
New Convergence Aspects of Stochastic Gradient Algorithms (2018, methodology): “In our analysis we also do not use the bounded gradient assumption as in Leblond et al. (2018). Moreover, (a) we focus on solving the more general problem in (1), while Leblond et al. (2018) considers the specific case of the “finite-sum” problem in (2), and (b) we show that our analysis generalizes”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, background): “[19] Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien.”
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates (2018, background): “For example, there has been much recent interest in asynchronous algorithms, in a model where there is a delay in updating individual coordinates in a shared parameter vector (e.g., the Hogwild! algorithm of [18], or more recently [14, 13]).”
Decoupled Greedy Learning of CNNs (2019, background): “Furthermore, none of these have been combined with CNNs. Distributed optimization based on data parallelism is a popular area of research in machine learning beyond deep learning models and often studied in the convex setting (Leblond et al., 2018).”
The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory (2018, background): “Concurrent work [17, 22] provides significantly more general analyses of iterative processes under asynchrony, covering several important optimization algorithms.”