Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The algorithm is straightforward to parallelize via Hogwild because updates are sparse and collisions are very unlikely on large-scale data.
“Moreover, the algorithm is straightforward to parallelize via methods such as Hogwild [26], as the updates are sparse (only a small number of embeddings are modified in an update) and collisions are very unlikely on large-scale data.”
From Poincaré Embeddings for Learning Hierarchical Representations (2017) · cites this paper as [26]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
The citation lists haven’t been fetched yet
References 27 · Cited by 1,211
Research works printed but not linked: 21
- [3][3] D. P. Bertsekas. Nonlinear Programming . Athena Scientific, Belmont, MA, 2nd edition, 1999. -
- [5][5] L. Bottou and O. Bousquet. The tradeoffs of large scale learning. In Advances in Neural Information Processing Systems , 2008. -
- [6][6] Y. Boykov and V. Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence , 26(9):11241137, 2004. -
- [7][7] G. C˘ alinescu, H. Karloff, and Y. Rabani. An improved approximation algorithm for multiway cut. In Proceedings of the thirtieth annual ACM Symposium on Theory of Computing , pages 48-52, 1998. -
- [8][8] E. Cand` es and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics , 9(6):717-772, 2009. -
- [9][9] J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Communications of the ACM , 51(1):107-113, 2008. -
- [12][12] J. Duchi, A. Agarwal, and M. J. Wainwright. Distributed dual averaging in networks. In Advances in Neural Information Processing Systems , 2010. -
- [13][13] S. H. Fuller and L. I. Millett, editors. The Future of Computing Performance: Game Over or Next Level . Committee on Sustaining Growth in Computing Performance. The National Academies Press, Washington, D.C., 2011. -
- [14][14] T. Joachims. Training linear svms in linear time. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD) , 2006. -
- [16][16] J. Langford, A. J. Smola, and M. Zinkevich. Slow learners are fast. In Advances in Neural Information Processing Systems , 2009. -
- [17][17] J. Lee, , B. Recht, N. Srebro, R. R. Salakhutdinov, and J. A. Tropp. Practical large-scale optimization for max-norm regularization. In Advances in Neural Information Processing Systems , 2010. -
- [19][19] D. Lewis, Y. Yang, T. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research , 5:361-397, 2004. -
- [21][21] S. Melnik, A. Gubarev, J. J. Long, G. Romer, S. Shivakumar, M. Tolton, and T. Vassilakis. Dremel: Interactive analysis of web-scale datasets. In Proceedings of VLDB , 2010. -
- [22][22] A. Nedic and D. P. Bertsekas. Convergence rate of incremental subgradient algorithms. In S. Uryasev and P. M. Pardalos, editors, Stochastic Optimization: Algorithms and Applications , pages 263-304. Kluwer Academic Publishers, 2000. -
- [23][23] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization , 19(4):1574-1609, 2009. -
- [24][24] B. Recht, M. Fazel, and P. Parrilo. Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization. SIAM Review , 52(3):471-501, 2010. -
- [25][25] B. Recht and C. R´ e. Parallel stochastic gradient algorithms for large-scale matrix completion. Submitted for publication. Preprint available at http://pages.cs.wisc.edu/ ~ brecht/publications.html , 2011. -
- [26][26] S. Shalev-Shwartz and N. Srebro. SVM Optimization: Inverse dependence on training set size. In Proceedings of the 25th Internation Conference on Machine Learning , 2008. -
- [27][27] N. Srebro, J. Rennie, and T. Jaakkola. Maximum margin matrix factorization. In Advances in Neural Information Processing Systems , 2004. -
- [28][28] P. Tseng. An incremental gradient(-projection) method with momentum term and adaptive stepsize rule. SIAM Joural on Optimization , 8(2):506-531, 1998. -
- [30][30] M. Zinkevich, M. Weimer, A. Smola, and L. Li. Parallelized stochastic gradient descent. Advances in Neural Information Processing Systems , 2010.
- Authors
- Niu, F., Recht, B., Re, C., & Wright, S. J.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2011
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1106.5730
- OpenAlex
- W2951781666
- Cited by
- 1,211
- References
- 27
- Citations by year
- 2026: 1 · 2025: 5 · 2024: 9 · 2023: 25 · 2022: 25 · 2021: 111 · 2020: 136 · 2019: 187 · 2018: 136 · 2017: 170 · 2016: 159 · 2015: 106 · 2014: 74 · 2013: 49 · 2012: 15
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
- Keywords
- stochastic gradient descent, lock-free algorithms, parallel optimization, shared memory, sparse optimization, convergence rate, distributed learning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
