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.

67 pages, published in JMLR, can be found online at http://jmlr.org/papers/v19/17-650.html. arXiv admin note: substantial text overlap with arXiv:1606.04809

Cited by in corpus (22)

• Robust Aggregation for Federated Learning
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• Linearly Converging Error Compensated SGD
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• New Convergence Aspects of Stochastic Gradient Algorithms
• On the Practicality of Differential Privacy in Federated Learning by Tuning Iteration Times
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes
• The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory
• Parallel and distributed asynchronous adaptive stochastic gradient methods
• Asynchronous Distributed Optimization with Stochastic Delays
• Optimizing the Numbers of Queries and Replies in Federated Learning with Differential Privacy
• Asynchronous Iterations in Optimization: New Sequence Results and Sharper Algorithmic Guarantees
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates
• Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
• Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays
• Fully Asynchronous Stochastic Coordinate Descent: A Tight Lower Bound on the Parallelism Achieving Linear Speedup
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Distributed Networked Real-time Learning
• Distributed Learning and its Application for Time-Series Prediction