ASAGA: Asynchronous Parallel SAGA

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

107 citations recorded by the source corpus.

We describe ASAGA, an asynchronous parallel version of the incremental gradient algorithm SAGA that enjoys fast linear convergence rates. 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 thereby prove that ASAGA 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 speedup as well as the hardware overhead.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, 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 Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, background): “…optimize (1) in its general form, only Svrg had had an asynchronous parallel version proposed.3 No such adaptation had been attempted for Saga until Leblond et al. (2017), even though one could argue that it is a more natural candidate as, contrarily to Svrg, it is not epoch-based and thus has no…”
Revisiting Distributed Synchronous SGD (2016, background): “Understanding the theoretical impact of staleness is difﬁcult work and the topic of many recent papers, e.g. Recht et al. (2011); Duchi et al. (2013); Leblond et al. (2016); Reddi et al. (2015); k to parameter servers. end Algorithm 2: Async-SGD Parameter Server j Input: γ 0 , γ 1 , . . . learning…”
Distributed Learning over Unreliable Networks (2018, background): “Recent works indicate that many distributed learning is delay-tolerant under an asynchronous setting (Zhou et al., 2018; Lian et al., 2015; Sra et al., 2015; Leblond et al., 2016).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, background): “In fact, two recent works [60, 48] highlight subtle but important issue with labelling of iterates in the presence of asynchrony, rendering most of the existing analyses of asynchronous optimization algorithms incorrect.”
Sparsified SGD with Memory (2018, positive): “Inspired by the perturbed iterate framework in [22] and [18] we first define a virtual sequence {x̃t}t≥0 in the following way: x̃0 = x0 , x̃t+1 = x̃t − ηt∇fit(xt) , (11) where the sequences {xt}t≥0, {ηt}t≥0 and {it}t≥0 are the same as in (8).”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “Other approaches for low-communication training focus on sparsification of gradients, either by thresholding small entries or by random sampling [6, 22, 23, 24, 25, 26, 27, 28].”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “In fact, two recent works [110, 92] highlight subtle but important issue with labeling of iterates in the presence of asynchrony, rendering most of the existing analyses of asynchronous optimization algorithms incorrect.”
AdaBatch: Efficient Gradient Aggregation Rules for Sequential and Parallel Stochastic Gradient Methods (2017, background): “It does not require storing extra information and can be adapted to other algorithms such as SVRG or SAGA.”
Asynchronous Coordinate Descent under More Realistic Assumptions (2017, background): “Recently [12] proposes (in the SGD setting) an innovative “read after” sequence relabeling technique to create the independence.”
99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it (2019, background): “[18] Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien.”
Scaling Up Quasi-newton Algorithms: Communication Efficient Distributed SR1 (2019, methodology): “Currently, due to its fast learning properties, low per-iteration cost, and ease of implementation, the stochastic gradient (SG) method [9, 45], and its adaptive [22, 31, 60], variance-reduced [21, 28, 39, 48] and distributed [20, 32, 43, 44, 56, 62] variants are the preferred optimization methods f”
Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization (2017, methodology): “Following Leblond et al. (2017), we will also replace the dense gradient estimate ui by the sparse estimate vi := ∇fi(x) − αi + Diα, where Di is the diagonal matrix defined block-wise as [Di]B,B = dB1{B ∈ Ti}I |B|.”
A Delay-tolerant Proximal-Gradient Algorithm for Distributed Learning (2018, background): “(Recht et al., 2011), Distributed SDCA (Takáč et al., 2015), Distributed SVRG (Lee et al., 2015; Zhao & Li, 2016), ASAGA (Leblond et al., 2017), ProxASAGA (Pedregosa et al., 2017)).”
ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates (2015, background): “Alternatively, the paper [36] increments k right after an agent finishes reading x̂.”
Decoupled Greedy Learning of CNNs (2019, background): “2 simulates potential delays in such a setup by the use of a probability mass function (pmf) p ( j ) over workers analogous to typical asynchronous settings such as (Leblond et al., 2017).”
Asynchronous Distributed Learning with Sparse Communications and Identification (2018, methodology): “In large-scale machine learning, stochastic optimization algorithms are very popular, see e.g. the parallel stochastic algorithms of [13, 29].”