Taming the Wild: A Unified Analysis of Hogwild!-Style Algorithms

Abstract

Stochastic gradient descent (SGD) is a ubiquitous algorithm for a variety of machine learning problems. Researchers and industry have developed several techniques to optimize SGD's runtime performance, including asynchronous execution and reduced precision. Our main result is a martingale-based analysis that enables us to capture the rich noise models that may arise from such techniques. Specifically, we use our new analysis in three ways: (1) we derive convergence rates for the convex case (Hogwild!) with relaxed assumptions on the sparsity of the problem; (2) we analyze asynchronous SGD algorithms for non-convex matrix problems including matrix completion; and (3) we design and analyze an asynchronous SGD algorithm, called Buckwild!, that uses lower-precision arithmetic. We show experimentally that our algorithms run efficiently for a variety of problems on modern hardware.

References in corpus (1)

• Deep Learning with Limited Numerical Precision

Cited by in corpus (34)

• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• An optical neural network using less than 1 photon per multiplication
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis
• Local SGD Converges Fast and Communicates Little
• Communication-Efficient Distributed Deep Learning: A Comprehensive Survey
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• CYCLADES: Conflict-free Asynchronous Machine Learning
• PipeMare: Asynchronous Pipeline Parallel DNN Training
• Communication trade-offs for synchronized distributed SGD with large step size
• Orchestrating the Development Lifecycle of Machine Learning-Based IoT Applications: A Taxonomy and Survey
• New Convergence Aspects of Stochastic Gradient Algorithms
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Keeping CALM: When Distributed Consistency is Easy
• Advances in Asynchronous Parallel and Distributed Optimization
• Revisiting BFloat16 Training
• Distributed Deep Learning with Event-Triggered Communication
• Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent
• Pufferfish: Communication-efficient Models At No Extra Cost
• NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization
• Trends and Advancements in Deep Neural Network Communication
• MixML: A Unified Analysis of Weakly Consistent Parallel Learning
• Where Is the Normative Proof? Assumptions and Contradictions in ML Fairness Research
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes
• Consistent Lock-free Parallel Stochastic Gradient Descent for Fast and Stable Convergence
• Integrating Deep Learning in Domain Sciences at Exascale
• Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates
• Second-Order Convergence of Asynchronous Parallel Stochastic Gradient Descent: When Is the Linear Speedup Achieved?
• Distributed Learning and its Application for Time-Series Prediction
• Scalable Projection-Free Optimization
• Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
• CuttleSys: Data-Driven Resource Management forInteractive Applications on Reconfigurable Multicores
• Quantizing data for distributed learning
• Oscars: Adaptive Semi-Synchronous Parallel Model for Distributed Deep Learning with Global View