Skip to Main content Skip to Navigation
Journal articles

Improved asynchronous parallel optimization analysis for stochastic incremental methods

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.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-01950558
Contributor : Rémi Leblond <>
Submitted on : Monday, December 10, 2018 - 10:53:09 PM
Last modification on : Thursday, July 1, 2021 - 5:58:09 PM
Long-term archiving on: : Monday, March 11, 2019 - 5:35:07 PM

File

1801.03749-2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01950558, version 1

Collections

Citation

Rémi Leblond, Fabian Pedregosa, Simon Lacoste-Julien. Improved asynchronous parallel optimization analysis for stochastic incremental methods. Journal of Machine Learning Research, Microtome Publishing, In press. ⟨hal-01950558⟩

Share

Metrics

Record views

109

Files downloads

79