Improved asynchronous parallel optimization analysis for stochastic incremental methods
From MaRDI portal
Publication:4614129
Abstract: 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.
Recommendations
- Perturbed iterate analysis for asynchronous stochastic optimization
- Asynchronous stochastic coordinate descent: parallelism and convergence properties
- On the convergence analysis of asynchronous SGD for solving consistent linear systems
- On the convergence of asynchronous parallel iteration with unbounded delays
- Parallel and distributed asynchronous adaptive stochastic gradient methods
Cites work
- A Parallel Mixture of SVMs for Very Large Scale Problems
- An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
- Distributed optimization with arbitrary local solvers
- Erratum to: ``Minimizing finite sums with the stochastic average gradient
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Perturbed iterate analysis for asynchronous stochastic optimization
- Semi-stochastic coordinate descent
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Cited in
(10)- Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup
- ARock: an algorithmic framework for asynchronous parallel coordinate updates
- Perturbed iterate analysis for asynchronous stochastic optimization
- Improved asynchronous parallel optimization analysis for stochastic incremental methods
- Distributed Learning with Sparse Communications by Identification
- scientific article; zbMATH DE number 7307474 (Why is no real title available?)
- The error-feedback framework: SGD with delayed gradients
- Parallel and distributed asynchronous adaptive stochastic gradient methods
- 1-D CNNs with lock-free asynchronous adaptive stochastic gradient descent algorithm for classification of astronomical spectra
- A tight convergence analysis for stochastic gradient descent with delayed updates
This page was built for publication: Improved asynchronous parallel optimization analysis for stochastic incremental methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4614129)
