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

arXiv: https://arxiv.org/abs/1506.06438 · HTML: https://mlsanity.com/paper/1506.06438/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2015.

## Built on by (most cited first, 30 of 31)

- [Pufferfish: Communication-efficient Models At No Extra Cost](https://mlsanity.com/paper/2103.03936/) (2021)
- [DataLens: Scalable Privacy Preserving Training via Gradient Compression and Aggregation](https://mlsanity.com/paper/2103.11109/) (2021)
- [An optical neural network using less than 1 photon per multiplication](https://mlsanity.com/paper/2104.13467/) (2021)
- [Critical Parameters for Scalable Distributed Learning with Large Batches and Asynchronous Updates](https://mlsanity.com/paper/2103.02351/) (2021)
- [Distributed Learning Systems with First-order Methods](https://mlsanity.com/paper/2104.05245/) (2021)
- [A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates](https://mlsanity.com/paper/2206.10189/) (2022)
- [Stochastic Approximation Beyond Gradient for Signal Processing and Machine Learning](https://mlsanity.com/paper/2302.11147/) (2023)
- [Spectrum Breathing: Protecting Over-the-Air Federated Learning Against Interference](https://mlsanity.com/paper/2305.05933/) (2023)
- [Convergence and Privacy of Decentralized Nonconvex Optimization with Gradient Clipping and Communication Compression](https://mlsanity.com/paper/2305.09896/) (2023)
- [Transformers Go for the LOLs: Generating (Humourous) Titles from Scientific Abstracts End-to-End](https://mlsanity.com/paper/2212.10522/) (2022)
- [Elastic Consistency: A General Consistency Model for Distributed Stochastic Gradient Descent](https://mlsanity.com/paper/2001.05918/) (2020)
- [Low-Precision Streaming PCA](https://mlsanity.com/paper/2510.22440/) (2025)
- [Considerations on the Theory of Training Models with Differential Privacy](https://mlsanity.com/paper/2303.04676/) (2023)
- [Distributed Extra-gradient with Optimal Complexity and Communication Guarantees](https://mlsanity.com/paper/2308.09187/) (2023)
- [Proactive DP: A Multple Target Optimization Framework for DP-SGD](https://mlsanity.com/paper/2102.09030/) (2021)
- [AET-SGD: Asynchronous Event-triggered Stochastic Gradient Descent](https://mlsanity.com/paper/2112.13935/) (2021)
- [Scaling the Wild: Decentralizing Hogwild!-style Shared-memory SGD](https://mlsanity.com/paper/2203.06638/) (2022)
- [Scaling up Stochastic Gradient Descent for Non-convex Optimisation](https://mlsanity.com/paper/2210.02882/) (2022)
- [Quantization-Based Optimization: Alternative Stochastic Approximation of Global Optimization](https://mlsanity.com/paper/2211.03972/) (2022)
- [Dual-Delayed Asynchronous SGD for Arbitrarily Heterogeneous Data](https://mlsanity.com/paper/2405.16966/) (2024)
- [Acoustic Model Optimization over Multiple Data Sources: Merging and Valuation](https://mlsanity.com/paper/2410.15620/) (2024)
- [DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication](https://mlsanity.com/paper/2512.13583/) (2025)
- [Tight Analysis of Decentralized SGD: A Markov Chain Perspective](https://mlsanity.com/paper/2601.07021/) (2026)
- [NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization](https://mlsanity.com/paper/2104.13818/) (2021)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Distributed Learning and its Application for Time-Series Prediction](https://mlsanity.com/paper/2106.03211/) (2021)
- [Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization](https://mlsanity.com/paper/2109.15292/) (2021)
- [Stochastic Gradient Langevin Dynamics Based on Quantization with Increasing Resolution](https://mlsanity.com/paper/2305.18864/) (2023)
- [The Landscape of Modern Machine Learning: A Review of Machine, Distributed and Federated Learning](https://mlsanity.com/paper/2312.03120/) (2023)
- [Asynchronous Heavy-Tailed Optimization](https://mlsanity.com/paper/2602.18002/) (2026)

## Abstract (arXiv)

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.