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

Christopher De Sa, Ce Zhang, Kunle Olukotun, Christopher Ré

The Problem with "Wild" Optimization

In the quest to train machine learning models faster, practitioners often abandon the "clean" world of sequential, high-precision mathematics. Instead, they turn to high-performance "hacks" like asynchrony (where multiple CPU cores update a shared model simultaneously without locks, leading to "stale" data) and low precision (using 8-bit or 16-bit integers instead of 32-bit floats to save memory and leverage faster hardware instructions).

While algorithms like HOGWILD! work brilliantly in practice, they are notoriously difficult to analyze theoretically. Standard convergence proofs assume a single, consistent state of the model. In the "wild," different cores see different versions of the model simultaneously. Previous theoretical work was highly fragmented, requiring a brand-new proof for every specific type of hardware noise or problem type. This paper introduces a unified theoretical framework to prove that these asynchronous, low-precision algorithms are mathematically sound.

A Unified Framework: Rate Supermartingales

The core innovation of this paper is a martingale-based analysis using a rate supermartingale.

Conceptually, a supermartingale acts as a mathematical function that measures "unhappiness" with the current state of the algorithm. In a standard sequential world, the expected unhappiness should decrease at every step. The authors demonstrate that you can "tame" the noise introduced by asynchrony and quantization by folding it directly into this unhappiness measure.

Key insights from this approach include:

  • Asynchrony as Noise: Hardware-level "messiness" (like race conditions and stale reads) can be modeled as just another form of statistical variance. As long as the "delay" (how many updates a core is behind) is bounded on average, the algorithm will still converge.
  • Relaxing Sparsity: Previous proofs for HOGWILD! required gradient updates to be extremely sparse (only changing a few variables at a time). This new analysis relaxes those assumptions, proving HOGWILD! is far more robust than previously thought.
  • Managing Non-Convexity: While most Stochastic Gradient Descent (SGD) theory focuses on "convex" (bowl-shaped) problems, this paper extends the analysis to non-convex problems like matrix completion. It proves that asynchrony doesn't trap the algorithm in local minima or saddle points any more than sequential SGD would.

BUCKWILD!: Speed Without Sacrifice

Building on their unified noise model, the authors introduce BUCKWILD!, a new algorithm variant that combines the lock-free asynchrony of HOGWILD! with low-precision (fixed-point) arithmetic.

Moving to 8-bit or 16-bit integers isn't just about saving memory; it unlocks the power of SIMD (Single Instruction, Multiple Data). Modern CPUs can process many small integers in a single clock cycle, which drives massive performance gains.

Performance scaling of BUCKWILD! for logistic regression across different thread counts and precision levels.

In empirical tests on datasets like RCV1 (a large-scale text classification dataset), BUCKWILD! achieved up to a 2.3x speedup over the already-fast HOGWILD! by utilizing 8-bit integers.

Crucially, this speedup does not come at the cost of model quality. The authors validated their theoretical results across several standard benchmarks (Reuters, Forest, RCV1, and Music).

Training loss comparison across datasets, demonstrating that 8-bit and 16-bit integer precision achieves nearly identical accuracy to 32-bit floats.

As shown in the results, the training loss for 8-bit and 16-bit integer versions was nearly identical to the 32-bit floating-point version (e.g., 0.1879 vs 0.1888 on RCV1). The probability of the algorithm failing to converge only increases by a negligible factor due to hardware delays, provided the step size is chosen correctly.

Limitations and Future Work

While this unified analysis is a significant step forward, it does have boundaries:

  • Atomic Write Assumption: The proofs rely on the assumption that writes to the central store are atomic (no "torn writes"). While true for single entries on most modern CPUs, this complicates the analysis for more complex data structures.
  • Specific Non-Convexity: The non-convex analysis is specifically tailored to matrix completion (Alecton). A truly universal theory for all non-convex landscapes, such as those found in deep neural networks, remains an open challenge.
  • Hardware Specifics: The speedup from low precision is highly dependent on the CPU's SIMD capabilities. On hardware lacking 4-bit or 1-bit SIMD support, attempting to use even lower-precision modes actually resulted in slower runtimes than 8-bit execution.

Summary updated

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 useour 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.
BibTeX
@inproceedings{sa2015taming,
  author = {Christopher De Sa and Ce Zhang and Kunle Olukotun and Christopher Ré},
  title = {{Taming the Wild: A Unified Analysis of Hogwild-Style Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=SJEGN_bO-S},
}
Figure