HOGWILD swMATH ID: 28396 Software Authors: Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright Description: HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent. 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. Homepage: https://arxiv.org/abs/1106.5730 Keywords: Optimization; arXiv_math.OC; Machine Learning; arXiv_cs.LG; Stochastic Gradient Descent; SGD Related Software: Saga; ARock; AdaGrad; ImageNet; Adam; RCV1; CIFAR; LIBSVM; AlexNet; L-BFGS; PDCO; TensorFlow; TernGrad; DSCOVR; glmnet; ADADELTA; DiSCO; PyTorch; SHOGUN; L-BFGS-B Cited in: 63 Publications Standard Articles 1 Publication describing the Software Year HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent Feng Niu, Benjamin Recht, Christopher Re, Stephen J. Wright 2011 all top 5 Cited by 184 Authors 6 Takáč, Martin 4 Xu, Yangyang 4 Yin, Wotao 3 Jordan, Michael Irwin 3 Richtárik, Peter 3 Wright, Stephen J. 2 Curtis, Frank E. 2 Jaggi, Martin 2 Liu, Ji 2 Ma, Chenxin 2 Mahoney, Michael W. 2 Nocedal, Jorge 2 Peng, Zhimin 2 Ré, Christopher M. 2 Yan, Ming 1 Agarwal, Deepak 1 Aksenov, Vitaly 1 Alistarh, Dan 1 An, Aijun 1 Bach, Francis R. 1 Belgioioso, Giuseppe 1 Bittorf, Victor 1 Boffi, Nicholas M. 1 Bottou, Léon 1 Byrd, Richard H. 1 Cannelli, Loris 1 Cao, Ming 1 Cen, Shicong 1 Cenedese, Carlo 1 Chang, Tsung-Hui 1 Chen, Bao Xin 1 Chen, Jie 1 Chen, Ke 1 Chen, Mengqiang 1 Chen, Weizhu 1 Chen, Yuxin 1 Cheong, LoongFah 1 Chi, Yuejie 1 Chin, Gillian M. 1 Chow, Yinlam 1 Cohen, William W. 1 Cron, Andrew 1 Demmel, James Weldon 1 Devarakonda, Aditya 1 Diggavi, Suhas N. 1 Ding, Hu 1 Dingle, Nicholas J. 1 Draper, David 1 Dutta, Haimonti 1 Dvurechensky, Pavel E. 1 Erway, Jennifer B. 1 Facchinei, Francisco 1 Faghri, Fartash 1 Feng, Weiming 1 Forte, Simone 1 Fountoulakis, Kimon 1 Gao, Bin 1 Gasnikov, Alexander V. 1 Grammatico, Sergio 1 Granitzer, Michael 1 Griffin, Joshua D. 1 Guo, Binbin 1 Gürbüzbalaban, Mert 1 Hannah, Robert 1 Hendrikx, Hadrien 1 Hong, Mingyi 1 Hu, Yonggang 1 Huang, Ziyun 1 Iutzeler, Franck 1 Jain, Prateek 1 Kakade, Sham M. 1 Kallus, Nathan 1 Karakus, Can 1 Karimireddy, Sai Praneeth 1 Kidambi, Rahul 1 Koppel, Alec 1 Kuang, Di 1 Kungurtsev, Vyacheslav 1 Lacoste-Julien, Simon 1 Lao, Ni 1 Leblond, Rémi 1 Lee, Choon Meng 1 Lee, Dongha 1 Li, Boyue 1 Li, Huan 1 Li, Qin 1 Lin, Qihang 1 Lin, Zhouchen 1 Liu, Haoyang 1 Liu, Jianguo 1 Liu, Junfeng 1 Liu, Xin 1 Liu, Yangwei 1 Luo, Zhi-Quan 1 Ma, Shiqian 1 Ma, Shuming 1 Mackey, Lester 1 Malick, Jérôme 1 Mallmann-Trenn, Frederik 1 Mania, Horia ...and 84 more Authors all top 5 Cited in 29 Serials 15 Journal of Machine Learning Research (JMLR) 7 SIAM Journal on Optimization 4 Mathematical Programming. Series A. Series B 4 SIAM Journal on Scientific Computing 3 Information Sciences 3 Machine Learning 2 Neural Computation 2 Optimization Methods & Software 1 Inverse Problems 1 BIT 1 Mathematics of Operations Research 1 Operations Research 1 SIAM Journal on Matrix Analysis and Applications 1 Journal of Scientific Computing 1 International Journal of Computational Geometry & Applications 1 Numerical Algorithms 1 Computational Mathematics and Mathematical Physics 1 European Journal of Operational Research 1 SIAM Review 1 Distributed Computing 1 Computational Optimization and Applications 1 International Journal of Computer Vision 1 European Journal of Control 1 Journal of Applied Statistics 1 Brazilian Journal of Probability and Statistics 1 SIAM Journal on Imaging Sciences 1 Algorithms 1 Journal of Computational and Graphical Statistics 1 Journal of the Operations Research Society of China all top 5 Cited in 13 Fields 38 Computer science (68-XX) 35 Operations research, mathematical programming (90-XX) 23 Numerical analysis (65-XX) 8 Calculus of variations and optimal control; optimization (49-XX) 8 Statistics (62-XX) 7 Linear and multilinear algebra; matrix theory (15-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Combinatorics (05-XX) 2 Probability theory and stochastic processes (60-XX) 2 Biology and other natural sciences (92-XX) 1 Ordinary differential equations (34-XX) 1 Operator theory (47-XX) 1 Systems theory; control (93-XX) Citations by Year