Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Feng Niu, Benjamin Recht, Christopher Ré and Stephen J. Wright Computer Sciences Department, University of Wisconsin-Madison 1210 W Dayton St, Madison, WI 53706
Abstract
Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine learning tasks. Several researchers have recently proposed schemes to parallelize SGD, but all require performance-destroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking. We present an update scheme called Hogwild! which allows processors access to shared memory with the possibility of overwriting each other’s work. We show that when the associated optimization problem is sparse, meaning most gradient updates only modify small parts of the decision variable, then Hogwild! achieves a nearly optimal rate of convergence. We demonstrate experimentally that Hogwild! outperforms alternative schemes that use locking by an order of magnitude.
中文速览
随机梯度下降（SGD）在机器学习中表现出色，但其天然的串行结构让并行化变得棘手——现有的并行方案都要靠内存加锁来防止多处理器互相覆盖数据，而加锁本身会严重拖慢速度。本文提出了一种名为 Hogwild! 的无锁并行 SGD 方案：让多个处理器直接共享内存、随意读写，完全不加任何同步锁，哪怕彼此覆盖对方的更新也无所谓。理论分析表明，当优化问题具有稀疏性（即每次梯度更新只涉及决策变量的极小一部分）时，处理器间互相覆盖的概率极低，引入的误差几乎可以忽略，算法仍能达到近乎最优的收敛速度，并随处理器数量实现近线性加速。实验结果进一步验证，Hogwild! 在稀疏分类、协同过滤、图切割等多项机器学习任务上比带锁的并行方案快出一个数量级，为多核单机上的大规模数据分析提供了一条简单高效的新路径。
原文 arXiv:1106.5730;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1106.5730v2