Reproduce “HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright

This paper introduces Hogwild!, a lock-free method for parallelizing Stochastic Gradient Descent (SGD) on shared-memory multicore systems. The approach demonstrates that for sparse optimization problems, concurrent, unsynchronized updates can achieve order-of-magnitude speedups and near-linear scalability compared to locking-based methods, without compromising convergence rates.

Key insights

  • Strict memory consistency through locking is not always necessary for efficient parallel numerical optimization, particularly for sparse problems.
  • Leveraging data sparsity allows for lock-free asynchronous updates, as the probability of conflicting writes to the same memory location is low.
  • The algorithm achieves robust 1/k convergence rates for Stochastic Gradient Descent with constant stepsizes and exponential back-off, even with concurrent, unsynchronized updates.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.