DecentLaM: Decentralized Momentum SGD for
Large-Batch Deep Training
Kun Yuan (袁 坤)Center for Machine Learning Research @ Peking University

Nov. 22, 2022

Joint work with

Xinmeng Huang(UPenn)Center of Machine Learning Research

Yiming Chen
(Alibaba)

Bicheng Ying
(Google)Wotao Yin
(Alibaba)<2>

PART 01
Basics and Motivation

Training deep neural network is notoriously difficult

DNN training = non-convexity + massive dataset + huge models
Center of Machine Learning Research<4>Distributed learning•

Training deep neural networks typically requires massive datasets; efficient and scalable
distributed optimization algorithms are in urgent need

• A network of n nodes (devices such as GPUs) collaborate to solve the problem:<latexit sha1_base64="kuvqsFNbjEvULVMnkk4XIG+iKgw=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0mkqMeiF48t2FpoQ9lsJ+3azSbsboQS+gu8eFDEqz/Jm//GbZuDtj4YeLw3w8y8IBFcG9f9dgpr6xubW8Xt0s7u3v5B+fCoreNUMWyxWMSqE1CNgktsGW4EdhKFNAoEPgTj25n/8IRK81jem0mCfkSHkoecUWOlpuyXK27VnYOsEi8nFcjR6Je/eoOYpRFKwwTVuuu5ifEzqgxnAqelXqoxoWxMh9i1VNIItZ/ND52SM6sMSBgrW9KQufp7IqOR1pMosJ0RNSO97M3E/7xuasJrP+MySQ1KtlgUpoKYmMy+JgOukBkxsYQyxe2thI2ooszYbEo2BG/55VXSvqh6l9Vas1ap3+RxFOEETuEcPLiCOtxBA1rAAOEZXuHNeXRenHfnY9FacPKZY/gD5/MH2f+M+w==</latexit>n<latexit sha1_base64="4s4k+h9xgjmrws+lvj2BUmbO47g=">AAACk3icbVHtahQxFM2MX3X8WhVB8E/sImxBlhkVFUqh1Cr+EeritoXNdshkMt3QfIxJxs4S8ga+oG8hPoGZ3RG09ULgcM65yc25Rc2ZsWn6I4qvXL12/cbGzeTW7Tt37w3uPzg0qtGEToniSh8X2FDOJJ1aZjk9rjXFouD0qDh71+lH36g2TMkvdlnTucCnklWMYBuofPAdCSZz10LEJESTyUnp0dcGl7AatVtwB6JKY+Iy76RHphG5YzuZP5GwylkwPIdrMxKFat35gmrqe2pt6G4Q2C6Kwr33uXOoZT5nEBkm4H7O/IdRuw17dmucD4bpOF0VvAyyHgxBXwf54CcqFWkElZZwbMwsS2s7d1hbRjj1CWoMrTE5w6d0FqDEgpq5W6Xm4bPAhDmVDkdauGL/7nBYGLMURXB2XzAXtY78nzZrbPV27pisG0slWT9UNRxaBbsVwJJpSixfBoCJZmFWSBY45GzDopIESXpOlBBYli5sxLs/CU68T0JE2cVALoPDF+Ps9fjl51fD3b0+rA3wBGyCEcjAG7ALPoIDMAUE/IoeR0+jzfhRvB3vxftraxz1PQ/BPxV/+g1ixch4</latexit>

min

x2Rd

1X
f (x) =fi (x),
n i=1
d

where

fi (x) = E⇠i ⇠Di F (x; ⇠i ).

§ Each component fi : R ! R is local and private to node i<latexit sha1_base64="qzaURfASsGooeYPRN6hgZR2ijpo=">AAACJnicbZDLSgMxFIYzXut4q7p0YbAIrsqMioqrohuXtdgLdGrJZDJtaJIZkoxShln6LoJbfQ13Iu58BB/B9ALV1h8CP/85h5zz+TGjSjvOpzU3v7C4tJxbsVfX1jc281vbNRUlEpMqjlgkGz5ShFFBqppqRhqxJIj7jNT93tWgXr8nUtFI3Op+TFocdQQNKUbaRO38XtimFx5Huuv7aSW7C6CnIzgJ2vmCU3SGgrPGHZsCGKvczn97QYQTToTGDCnVdJ1Yt1IkNcWMZLaXKBIj3EMd0jRWIE5UKx0eksEDkwQwjKR5QsNh+nsiRVypPvdN52BDNV0bhP/VmokOz1spFXGiicCjj8KEQXPrgAoMqCRYs74xCEtqdoW4iyTC2rCzbU+QBxxxjkSQepVKlk4AZbZB5E4DmTW1o6J7Wjy+OSmULsewcmAX7IND4IIzUALXoAyqAINH8AxewKv1ZL1Z79bHqHXOGs/sgD+yvn4AJ/KmCw==</latexit><latexit sha1_base64="ZvkstkLZit2MzaUV5cWtHP44tBM=">AAACBnicbVDLSsNAFJ3UV42vqks3wSK4KomKuiy6cdkW+4CmlMn0th06MwkzE6WE7AW3+hvuxK2/4V/4CU7aLLT1wIXDOfdy7z1BxKjSrvtlFVZW19Y3ipv21vbO7l5p/6ClwlgSaJKQhbITYAWMCmhqqhl0IgmYBwzaweQ289sPIBUNxb2eRtDjeCTokBKsjVSn/VLZrbgzOMvEy0kZ5aj1S9/+ICQxB6EJw0p1PTfSvQRLTQmD1PZjBREmEzyCrqECc1C9ZHZo6pwYZeAMQ2lKaGem/p5IMFdqygPTybEeq0UvE//zurEeXvcSKqJYgyDzRcOYOTp0sq+dAZVANJsagomk5laHjLHERJtsbNsX8EhCzrEYJH6jkSZ+tiIIkkaa2iYibzGQZdI6q3iXlfP6Rbl6k4dVREfoGJ0iD12hKrpDNdREBAF6Ri/o1Xqy3qx362PeWrDymUP0B9bnDwCNmUY=</latexit>§ Random variable ⇠i denotes the local data that follows distribution Di<latexit sha1_base64="S7QpqR+KavrSLakXs5+Tz84oS4Y=">AAACCnicbVDLSsNAFJ3UV42vqks3wSK4KomKuiy6cVmLaQtNKJPJpB06MwkzE7WE/IHgVn/Dnbj1J/wLP8FJm4W2HrhwOOde7r0nSCiRyra/jMrS8srqWnXd3Njc2t6p7e51ZJwKhF0U01j0AigxJRy7iiiKe4nAkAUUd4PxdeF377GQJOZ3apJgn8EhJxFBUGnJ9R7JgAxqdbthT2EtEqckdVCiNah9e2GMUoa5QhRK2XfsRPkZFIoginPTSyVOIBrDIe5ryiHD0s+mx+bWkVZCK4qFLq6sqfp7IoNMygkLdCeDaiTnvUL8z+unKrr0M8KTVGGOZouilFoqtorPrZAIjBSdaAKRIPpWC42ggEjpfEzT4/gBxYxBHmZeu51nXrEiCLJ2nps6Imc+kEXSOWk4543T27N686oMqwoOwCE4Bg64AE1wA1rABQgQ8AxewKvxZLwZ78bHrLVilDP74A+Mzx85j5sK</latexit><latexit sha1_base64="vjfsQhfof4ZlRf21LJKMckSYVmM=">AAACCHicbVDLSsNAFJ3UV42vqks3g0VwVRIVdVnUhcta7QOaUCaTaTt0ZhJmJkoJ+QHBrf6GO3HrX/gXfoKTNgutHrhwOOde7r0niBlV2nE+rdLC4tLySnnVXlvf2NyqbO+0VZRITFo4YpHsBkgRRgVpaaoZ6caSIB4w0gnGl7nfuSdS0Ujc6UlMfI6Ggg4oRtpIt1d92q9UnZozBfxL3IJUQYFGv/LlhRFOOBEaM6RUz3Vi7adIaooZyWwvUSRGeIyGpGeoQJwoP52emsEDo4RwEElTQsOp+nMiRVypCQ9MJ0d6pOa9XPzP6yV6cO6nVMSJJgLPFg0SBnUE879hSCXBmk0MQVhScyvEIyQR1iYd2/YEecAR50iEqddsZqmXrwiCtJlltonInQ/kL2kf1dzT2vHNSbV+UYRVBntgHxwCF5yBOrgGDdACGAzBE3gGL9aj9Wq9We+z1pJVzOyCX7A+vgFVr5n9</latexit>§ Each local distribution Di is different; data heterogeneity exists<latexit sha1_base64="vjfsQhfof4ZlRf21LJKMckSYVmM=">AAACCHicbVDLSsNAFJ3UV42vqks3g0VwVRIVdVnUhcta7QOaUCaTaTt0ZhJmJkoJ+QHBrf6GO3HrX/gXfoKTNgutHrhwOOde7r0niBlV2nE+rdLC4tLySnnVXlvf2NyqbO+0VZRITFo4YpHsBkgRRgVpaaoZ6caSIB4w0gnGl7nfuSdS0Ujc6UlMfI6Ggg4oRtpIt1d92q9UnZozBfxL3IJUQYFGv/LlhRFOOBEaM6RUz3Vi7adIaooZyWwvUSRGeIyGpGeoQJwoP52emsEDo4RwEElTQsOp+nMiRVypCQ9MJ0d6pOa9XPzP6yV6cO6nVMSJJgLPFg0SBnUE879hSCXBmk0MQVhScyvEIyQR1iYd2/YEecAR50iEqddsZqmXrwiCtJlltonInQ/kL2kf1dzT2vHNSbV+UYRVBntgHxwCF5yBOrgGDdACGAzBE3gGL9aj9Wq9We+z1pJVzOyCX7A+vgFVr5n9</latexit>

Center of Machine Learning Research<5>

Vanilla parallel stochastic gradient descent (PSGD)<latexit sha1_base64="ir7agV4KnBNsMh4nzIC9tmNnMCk=">AAACvXicbVFraxQxFM2Mrzo+uupH/RBclC3iMGPrA6RYKqhgP9TFbQub7ZBkM7th8xgmGbtLmL/lf/Ff+BPM7Ay4tl4IHM7JvedyLikENzZJfgXhtes3bt7auh3duXvv/nbvwcMTo6uSshHVQpdnBBsmuGIjy61gZ0XJsCSCnZLFx0Y//cFKw7X6blcFm0g8UzznFFtPZb2fs4yfu8Fip4bP9yFSmAgMPw2WLfceLTs14zsQzU2BKXNp/JrKGiJJ9NINjjTFAlItCxv7KQhF6+YXaTuymwRfQpSXmDo0w1Li2qkamUpmju+n9bmCf9fYsEk3bD4LTVof6W2yXj+Jk3XBqyDtQB90dZz1fqOpppVkylKBjRmnSWEnDpeWU8HqCFWGedcFnrGxhwpLZiZunW8Nn3lmCnNd+qcsXLObHQ5LY1aS+J8S27m5rDXk/7RxZfN3E8dVUVmmaGuUVwJaDZtjwSkvGbVi5QGmJfe7QjrHPkbrTxpFSLGLJhCspg4Nh7VDjQUhbljXkY8ovRzIVXDyKk7fxLvf9voHh11YW+AxeAoGIAVvwQH4Ao7BCNDgSXAYfA2Owg8hC0Wo2q9h0PU8Av9UePEHrZPVbg==</latexit>

(k)

(k)

= rF (x(k) ; ⇠i )
n
X
(k)
(k+1)
(k)
x
=x
gi
n i=1
gi

(Local compt.)(Global comm.)<latexit sha1_base64="QLlrUPFVZcwFQRsbcjmX4/rnKdg=">AAACEHicbVDLSsNAFJ34rPFVdekmWIS6KYmKuiy6cVmLfUATy2Q6bYfOI8xM1BLyE4Jb/Q134tY/8C/8BCdtFtp64MLhnHu5954wokRp1/2yFhaXlldWC2v2+sbm1nZxZ7epRCwRbiBBhWyHUGFKOG5ooiluRxJDFlLcCkdXmd+6x1IRwW/1OMIBgwNO+gRBbaSO/0i65C4pj47SbrHkVtwJnHni5aQEctS6xW+/J1DMMNeIQqU6nhvpIIFSE0RxavuxwhFEIzjAHUM5ZFgFyeTk1Dk0Ss/pC2mKa2ei/p5IIFNqzELTyaAeqlkvE//zOrHuXwQJ4VGsMUfTRf2YOlo42f9Oj0iMNB0bApEk5lYHDaGESJuUbNvn+AEJxiDvJX69niZ+tiIMk3qa2iYibzaQedI8rnhnlZOb01L1Mg+rAPbBASgDD5yDKrgGNdAACAjwDF7Aq/VkvVnv1se0dcHKZ/bAH1ifP4rgnVg=</latexit>

(k)
⇠i

•

Each node i samples data•

All nodes synchronize (i.e. globally average) to update model x per iteration<latexit sha1_base64="ZvkstkLZit2MzaUV5cWtHP44tBM=">AAACBnicbVDLSsNAFJ3UV42vqks3wSK4KomKuiy6cdkW+4CmlMn0th06MwkzE6WE7AW3+hvuxK2/4V/4CU7aLLT1wIXDOfdy7z1BxKjSrvtlFVZW19Y3ipv21vbO7l5p/6ClwlgSaJKQhbITYAWMCmhqqhl0IgmYBwzaweQ289sPIBUNxb2eRtDjeCTokBKsjVSn/VLZrbgzOMvEy0kZ5aj1S9/+ICQxB6EJw0p1PTfSvQRLTQmD1PZjBREmEzyCrqECc1C9ZHZo6pwYZeAMQ2lKaGem/p5IMFdqygPTybEeq0UvE//zurEeXvcSKqJYgyDzRcOYOTp0sq+dAZVANJsagomk5laHjLHERJtsbNsX8EhCzrEYJH6jkSZ+tiIIkkaa2iYibzGQZdI6q3iXlfP6Rbl6k4dVREfoGJ0iD12hKrpDNdREBAF6Ri/o1Xqy3qx362PeWrDymUP0B9bnDwCNmUY=</latexit>

Center of Machine Learning Researchand computes gradient rF (x(k) ; ⇠i(k) )<latexit sha1_base64="rCCY3v0P2hGT6FYuRK2RaWJVE/s=">AAACJXicbZDLSgMxFIYz3h1vVZeCBIvQbsqMigpuREFcarFa6NRyJk1raJIZkoxahtn5LoJbfQ13IrjyFXwE08tCrT8EPv5zDufkD2POtPG8D2dsfGJyanpm1p2bX1hcyi2vXOooUYRWSMQjVQ1BU84krRhmOK3GioIIOb0KO8e9+tUtVZpF8sJ0Y1oX0JasxQgYazVy64GEkAM+Kdxfp4VOMTsI7tmAGqyIG7m8V/L6wqPgDyGPhjpr5L6CZkQSQaUhHLSu+V5s6ikowwinmRskmsZAOtCmNYsSBNX1tP+PDG9ap4lbkbJPGtx3f06kILTuitB2CjA3+m+tZ/5XqyWmtV9PmYwTQyUZLGolHJsI90LBTaYoMbxrAYhi9lZMbkABMTY61w0kvSORECCbaVAuZ2nQWxGGaTnLXBuR/zeQUbjcKvm7pe3znfzh0TCsGbSGNlAB+WgPHaJTdIYqiKAH9ISe0Yvz6Lw6b877oHXMGc6sol9yPr8BB1CkPQ==</latexit><latexit sha1_base64="UFrRpSEctgxpfOWW4xsMtLMRAn8=">AAACCXicbVDLSsNAFJ3UV42vqks3g63gqiQV1GXRjcta7AOaUCaTSTt0ZhJmJmoJ+QLBrf6GO3HrV/gXfoJJm4W2HrhwOOde7r3HixhV2rK+jNLK6tr6RnnT3Nre2d2r7B90VRhLTDo4ZKHse0gRRgXpaKoZ6UeSIO4x0vMm17nfuydS0VDc6WlEXI5GggYUI51LtccaHFaqVt2aAS4TuyBVUKA1rHw7fohjToTGDCk1sK1IuwmSmmJGUtOJFYkQnqARGWRUIE6Um8xuTeFJpvgwCGVWQsOZ+nsiQVypKfeyTo70WC16ufifN4h1cOkmVESxJgLPFwUxgzqE+ePQp5JgzaYZQVjS7FaIx0girLN4TNMR5AGHnCPhJ067nSZOvsLzknaamllE9mIgy6TbqNvn9bPbRrV5VYRVBkfgGJwCG1yAJrgBLdABGIzBM3gBr8aT8Wa8Gx/z1pJRzByCPzA+fwAy1pnZ</latexit><6>

Vanilla parallel stochastic gradient descent (PSGD)•

Global average incurs O(n) comm. overhead; proportional to network size n•

When network size n is large, PSGD suffers severe communication overhead

Center of Machine Learning Research<7>

PSGD cannot achieve linear speedup due to comm. overhead•

PSGD cannot achieve ideal linear speedup in throughput due to comm. overhead•

Larger comm-to-compt ratio leads to worse performance in PSGD

Small comm.-to-compt. ratio•

Large comm.-to-compt. ratio

How can we accelerate PSGD? Decentralized SGD is a promising paradigm.

B. Ying, K. Yuan, H. Hu, Y. Chen and W. Yin, “BlueFog: Make decentralized algorithms practical for optimization and deep learning”, arXiv: 2111. 04287, 2021
Center of Machine Learning Research<8>Decentralized SGD (DSGD)•To break O(n) comm. overhead, we replace global average with partial average(k+ 12 )
(k)
xi
= xi
<latexit sha1_base64="K5uW5GMso9ECnnL+ck/ZO5PjzFw=">AAADJXicbZJbixMxFMcz421bL9vVR1+CRWmRLTO7RQURFgXxQUotdndhU0smTdu0k2SYZNyWkA/gq34IP41vIvjkJxE8vbj3AwMn53eS/+F/JslSYWwU/Q7Ca9dv3Ly1USrfvnP33mZl6/6+0UXOeJfpVOeHCTU8FYp3rbApP8xyTmWS8oNk+mbBDz7z3AitPtp5xnuSjpQYCkYtlPqVv7NPrjZ9SoY5ZS72bsfXfV/gJ/gVXhI4OeHxNiYjKiXFjiiapNS/rZ3BZGwyyrjbjhpNKf1LMhOnsI7/411gmMhEz1ztvWY0xUU2oJbXoaq0KmTCc0xIuVRaDRWfjEJMIftuQoTChLX6MNAxPD3x+KrpJyeCcaPJTiXbNLcCRCn4QUdCjaC3Uo0a0TLw5SReJ1W0jnZ/K6iQgWaF5MqylBpzFEeZ7bnF0yzlvkwKw0F7Skf8CFJFJTc9t9yTx4+hMsBDncOnLF5Wz95wVBozlwl0SmrH5iJbFK9iR4Udvug5obLCcsVWQsMixVbjxdLxQOSc2XQOCWW5gFkxG1MwzcKvUS4TxY+ZhvWqgSOdjndkIZEkruP9echa3q0orM+1PHDwML7o2OVkf6cRP2vsfmhW916v3dxAD9EjVEMxeo720DvURl3EAhZ8Cb4G38Lv4Y/wZ/hr1RoG6zsP0LkI//wD2d0AVA==</latexit>

(k+1)
xi
=

X

(k)

(k)

rF (xi ; ⇠i ) (Local update)(k+ 12 )wij xj(Partial averaging)

j2Ni

•
•
•

DSGD = local SGD update + partial averaging [LS08]<latexit sha1_base64="djb8IL5A/At4KetmqlbXRctl1yE=">AAAB9HicbVDLSgMxFL2pr1pfVZdugkVwVWakqMuiG1dSwT6gHUomzbShmcyYZApl6He4caGIWz/GnX9jpp2Fth4IHM65l3ty/FhwbRznGxXW1jc2t4rbpZ3dvf2D8uFRS0eJoqxJIxGpjk80E1yypuFGsE6sGAl9wdr++Dbz2xOmNI/ko5nGzAvJUPKAU2Ks5PVCYkaUiPR+1uf9csWpOnPgVeLmpAI5Gv3yV28Q0SRk0lBBtO66Tmy8lCjDqWCzUi/RLCZ0TIasa6kkIdNeOg89w2dWGeAgUvZJg+fq742UhFpPQ99OZiH1speJ/3ndxATXXsplnBgm6eJQkAhsIpw1gAdcMWrE1BJCFbdZMR0RRaixPZVsCe7yl1dJ66LqXlZrD7VK/SavowgncArn4MIV1OEOGtAECk/wDK/whiboBb2jj8VoAeU7x/AH6PMHCYSSSQ==</latexit>

Ni is the set of neighbors at node i ; wij scales information from j to i<latexit sha1_base64="Fnwhd7Ta5Tw0dHaaWO+17yDDvLg=">AAAB6HicbVDLTgJBEOzFF+IL9ehlIjHxRHYNUY9ELx4hkUcCGzI79MLA7OxmZtaEEL7AiweN8eonefNvHGAPClbSSaWqO91dQSK4Nq777eQ2Nre2d/K7hb39g8Oj4vFJU8epYthgsYhVO6AaBZfYMNwIbCcKaRQIbAXj+7nfekKleSwfzSRBP6IDyUPOqLFSfdQrltyyuwBZJ15GSpCh1it+dfsxSyOUhgmqdcdzE+NPqTKcCZwVuqnGhLIxHWDHUkkj1P50ceiMXFilT8JY2ZKGLNTfE1MaaT2JAtsZUTPUq95c/M/rpCa89adcJqlByZaLwlQQE5P516TPFTIjJpZQpri9lbAhVZQZm03BhuCtvrxOmldl77pcqVdK1bssjjycwTlcggc3UIUHqEEDGCA8wyu8OSPnxXl3PpatOSebOYU/cD5/ANPvjPc=</latexit><latexit sha1_base64="gQ0QZrHgZBkqf996/QQVBa6B0JU=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0mkqMeiF48t2FpoQ9lsJ+3azSbsboQS+gu8eFDEqz/Jm//GbZuDtj4YeLw3w8y8IBFcG9f9dgpr6xubW8Xt0s7u3v5B+fCoreNUMWyxWMSqE1CNgktsGW4EdhKFNAoEPgTj25n/8IRK81jem0mCfkSHkoecUWOlJu+XK27VnYOsEi8nFcjR6Je/eoOYpRFKwwTVuuu5ifEzqgxnAqelXqoxoWxMh9i1VNIItZ/ND52SM6sMSBgrW9KQufp7IqOR1pMosJ0RNSO97M3E/7xuasJrP+MySQ1KtlgUpoKYmMy+JgOukBkxsYQyxe2thI2ooszYbEo2BG/55VXSvqh6l9Vas1ap3+RxFOEETuEcPLiCOtxBA1rAAOEZXuHNeXRenHfnY9FacPKZY/gD5/MH0muM9g==</latexit><latexit sha1_base64="gQ0QZrHgZBkqf996/QQVBa6B0JU=">AAAB6HicbVBNS8NAEJ3Ur1q/qh69LBbBU0mkqMeiF48t2FpoQ9lsJ+3azSbsboQS+gu8eFDEqz/Jm//GbZuDtj4YeLw3w8y8IBFcG9f9dgpr6xubW8Xt0s7u3v5B+fCoreNUMWyxWMSqE1CNgktsGW4EdhKFNAoEPgTj25n/8IRK81jem0mCfkSHkoecUWOlJu+XK27VnYOsEi8nFcjR6Je/eoOYpRFKwwTVuuu5ifEzqgxnAqelXqoxoWxMh9i1VNIItZ/ND52SM6sMSBgrW9KQufp7IqOR1pMosJ0RNSO97M3E/7xuasJrP+MySQ1KtlgUpoKYmMy+JgOukBkxsYQyxe2thI2ooszYbEo2BG/55VXSvqh6l9Vas1ap3+RxFOEETuEcPLiCOtxBA1rAAOEZXuHNeXRenHfnY9FacPKZY/gD5/MH0muM9g==</latexit><latexit sha1_base64="LBGOUbLEEAkVtcC0YqRQzbLdgbc=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRbBU9mVoh6LXjxWsB/QLiWbZtu02WRJskpZ+h+8eFDEq//Hm//GdLsHbX0w8Hhvhpl5QcyZNq777RTW1jc2t4rbpZ3dvf2D8uFRS8tEEdokkkvVCbCmnAnaNMxw2okVxVHAaTuY3M799iNVmknxYKYx9SM8FCxkBBsrtZ76KRvP+uWKW3UzoFXi5aQCORr98ldvIEkSUWEIx1p3PTc2foqVYYTTWamXaBpjMsFD2rVU4IhqP82unaEzqwxQKJUtYVCm/p5IcaT1NApsZ4TNSC97c/E/r5uY8NpPmYgTQwVZLAoTjoxE89fRgClKDJ9agoli9lZERlhhYmxAJRuCt/zyKmldVL3Lau2+Vqnf5HEU4QRO4Rw8uII63EEDmkBgDM/wCm+OdF6cd+dj0Vpw8plj+APn8wfui49g</latexit>

Incurs O(dmax ) comm. overhead per iteration where dmax = max{|Ni |} is the graph maximum degree<latexit sha1_base64="LtE8Vgg3hnPA1Aosalmoni97PYY=">AAACRHicbZDBbhMxEIa9hdIQWkjhCAeLCIlTtFsQ7aVSBRdOURqRtlI2Ws3OOo1V27uyvS2R6wtPwxUegnfgHbhVvVZ4kxxoy0iWf/3/jMb+8kpwY+P4d7T24OH6o43W4/aTza2nzzrbz49MWWtkIyxFqU9yMExwxUaWW8FOKs1A5oId52efmvz4nGnDS/XFzis2kXCq+JQj2GBlnVdF5lIJXz3dp82d8dRdptjP+GXqs0437sWLovdFshJdsqpBth110qLEWjJlUYAx4ySu7MSBthwF8+20NqwCPINTNg5SgWRm4hbf8PRNcAo6LXU4ytKF+++EA2nMXOahU4KdmbtZY/4vG9d2ujdxXFW1ZQqXi6a1oLakDRNacM3QinkQgJqHt1KcgQa0gVy7nSp2gaWUoAqXDoe+AWZnee6G3t8Ose/dMkUQru9DHhgmd4ndF0c7veRD793h++7BxxXNFnlJXpO3JCG75IB8JgMyIki+ke/kB/kZ/Yr+RFfR9bJ1LVrNvCC3Krr5C1IMsaQ=</latexit><latexit sha1_base64="E+QIbabTheG+ghE+Umq3bpUIrYI=">AAAB8nicbVBNSwMxEJ31s9avqkcvwSLUS9mVoh6LXrxZwX7AdinZNNuGZpMlyYpl6c/w4kERr/4ab/4b03YP2vpg4PHeDDPzwoQzbVz321lZXVvf2CxsFbd3dvf2SweHLS1TRWiTSC5VJ8SaciZo0zDDaSdRFMchp+1wdDP1249UaSbFgxknNIjxQLCIEWys5N9V+r2sG+OnyVmvVHar7gxomXg5KUOORq/01e1LksZUGMKx1r7nJibIsDKMcDopdlNNE0xGeEB9SwWOqQ6y2ckTdGqVPoqksiUMmqm/JzIcaz2OQ9sZYzPUi95U/M/zUxNdBRkTSWqoIPNFUcqRkWj6P+ozRYnhY0swUczeisgQK0yMTaloQ/AWX14mrfOqd1Gt3dfK9es8jgIcwwlUwINLqMMtNKAJBCQ8wyu8OcZ5cd6dj3nripPPHMEfOJ8/w4+Q7g==</latexit>

Center of Machine Learning Researchi<9>DSGD is more communication-efficient than PSGD•

Incurs O(1) comm. overhead on sparse topologies; much less than global average O(n)•Many sparse and effective topologies are proposed recently<latexit sha1_base64="ePWhDDpGjJEQ1JRSBBun38CrrqY=">AAAB63icbVBNSwMxEJ2tX7V+VT16CRahXsquFPVY9OLNCvYD2qVk02wbmmSXJCuUpX/BiwdFvPqHvPlvzLZ70NYHA4/3ZpiZF8ScaeO6305hbX1jc6u4XdrZ3ds/KB8etXWUKEJbJOKR6gZYU84kbRlmOO3GimIRcNoJJreZ33miSrNIPpppTH2BR5KFjGCTSfdV73xQrrg1dw60SrycVCBHc1D+6g8jkggqDeFY657nxsZPsTKMcDor9RNNY0wmeER7lkosqPbT+a0zdGaVIQojZUsaNFd/T6RYaD0Vge0U2Iz1speJ/3m9xITXfspknBgqyWJRmHBkIpQ9joZMUWL41BJMFLO3IjLGChNj4ynZELzll1dJ+6LmXdbqD/VK4yaPowgncApV8OAKGnAHTWgBgTE8wyu8OcJ5cd6dj0VrwclnjuEPnM8f4DqNfA==</latexit>

B. Ying*, K. Yuan*, Y. Chen*, H. Hu, P. Pan, and W. Yin, “Exponential Graph is Provably Efficient for Deep Training”, NeurIPS 2021
Z. Song*, W. Li*, K. Jin*, L. Shi, M. Yan, W. Yin, and K. Yuan “Communication-efficient topologies for decentralized learning with O(1) consensus rate”, NeurIPS 2022
Center of Machine Learning Research< 10 >DSGD is more communication-efficient than PSGD•

A real experiment on a 256-GPUs cluster [CYZ+21]<latexit sha1_base64="op39c8VfbvYKnVp5/0exxa2ZaN0=">AAAD33icfVJNbxMxEN0kQJvlq4UjF4uGqhwa7aYkKbdSLlxalYh+SHFUeb2T1Ko/VrYXqCyfuSGu3Phb/Bu8SQpt0zLSSuP3ZvxmnycrODM2SX7X6o179x8sLTfjh48eP3m6svrsyKhSUzikiit9khEDnEk4tMxyOCk0EJFxOM7O31f88WfQhin5yV4UMBJkItmYUWIDdLpa+4UzmDDpLAktfjiKm/+AkhPtnabUx80mtqrQJYcqFSW3LIiXQrrUO+odtvDVZmO3p3Lg3qN1dIkMmJxsvuNcQ15SuMocEG0Z4YiEAckkUBgjLFg+VxmA2Qe72U3QRqfb7u69RnfFOmp1+tstJMwi4/DUJJfxEnwr7SZVmV+4AuOguAvaoo2tJPmP1qVg+qb39hbFm4LdXv8uQYQzZa0Ss9/FIPO/nseXp/AkpytrSTuZBlpM0nmyFs3jILzpOs4VLQVISzkxZpgmhR25ym0aLoxxaaAg9Dx4PgypJALMyE2n9uhVQHI0Vjp80qIperXDEWHMhchCpSD2zNzkKvA2blja8fbIMVmUFiSdCY1LjqxC1WKinGmgll+EhFDNwqyInhFNqA3re00lU+o8eGN8HGMJX6gSggS78GAQ9rASzjI38P46Sfe9m7GUcLfvAx+cTW/6uJgcddppr731sbO2szv3eDl6Eb2MNqI06kc70YfoIDqMaH2pvlnv1fsN0vjW+N74MSut1+Y9z6Nr0fj5B6OJIPw=</latexit>

Model

Ring-Allreduce

Partial average

ResNet-50 (25.5M)
Bert (300M)

278 ms1469 ms

150 ms
567 msTable. Comparison of per-iter comm. time in terms of runtime with 256 GPUs•

DSGD saves more communications per iteration for larger models[CYZ+21] Y. Chen*, K. Yuan*, Y. Zhang, P. Pan, Y. Xu, and W. Yin, ``Accelerating Gossip SGD with Periodic Global Averaging”, ICML 2021
Center of Machine Learning Research< 11 >DSGD is more communication-efficient than PSGD•DSGD (BlueFog) has better linear speedup than PSGD (Horovod) due to its small comm. overhead

Small comm.-to-compt. ratio

Large comm.-to-compt. ratio

B. Ying, K. Yuan, H. Hu, Y. Chen and W. Yin, “BlueFog: Make decentralized algorithms practical for optimization and deep learning”, arXiv: 2111. 04287, 2021
Center of Machine Learning Research< 12 >DSGD is more communication-efficient than PSGD
Table. Test accuracy and wall-clock training time on ImageNet [YYC+21]<latexit sha1_base64="cN5prPxaMZgTXyEa6JBo7KpMqeA=">AAAGEHiclVTLbhMxFJ0SAjQ8C0s2hgoUFhllJs8lLwlWqBQKSHVUeRw3terHaOwBKss/wYJvYYfYIf6An2ALS+48khISCWFp5HvOffr6epJUcGO73e8bZxpnm+fOX9hsXbx0+crVa1vXXxmdZ5TtUS109iYhhgmu2J7lVrA3acaITAR7nRw/KvSv37LMcK1e2pOUTSSZKX7IKbFAHWw1CE7YjCtnCbj4fXtr0tq8g/Bbc8xT1OmG0YCr1ibglFDmOkMp/R9wUEFBEiaqEB2rU91RespMh2qZkowbrcAIzKpMlCnLMmDmhJFEiAIvGIiUC5J5R+erUm9iiJ7lglWozILuIixzYTk0I5fKxeDlXb/dfz9GT3b2zD2/3mLcHv/DIhq2o+E/bHpxuxef2mBcVVY0QejZCTgRSkPYLJfsPxAsjFF9aMmnxaFruNN58eQx2KHRMOzFIERROIQNYH8EO7A1KtheOKpQPIA9DuNFjbtczeow0XApTNQvwwxqVIUpgw7CYZkxHC/CaMU6KWMZYu/TonyHy6l0iciZL2vs+xUackWrLBgP4lV6EI7W2vbX0HE4LsiqtCVV0YI1DlE4mM8WRjjR1mq5mDDM1HQxjK0az8e1BIthPn0xcfFi5p7wpg6ubXfDbrnQqhDVwnZQr52DrY2PeKppLiE2FcSY/aib2okjGQwfBGzh3DB4f8dkxvZBVEQyM3HlqTy6A8wUHeoMPmVRyf7p4Yg05kQmYCmJPTJ/6wpynW4/t4fjieMqzS1TtEp0mAtkNSr+LGjKM0atOAGB0IxDrYgekYxQaNBylkTrY+iNWTqJm5qiYN9qYcXewa9DEmgh3t31DhfFJInb9X5ZSZ95V2kpEe6Z97W3PWI6Y9LVu3cva2FJC53NZVr8B717cCq3sGGW6ry42NMIMYSGm4z+vrdV4VUMTybsPY+37z+s7/RCcDO4HbSDKBgF94OnwU6wF9DG18aPxs/Gr+aH5qfm5+aXyvTMRu1zI1hazW+/ATtG3uk=</latexit>

nodes
topology
P-SGD
Ring
D-SGD
one-peer exp.
<latexit sha1_base64="cHvi58O5lYiM1j6mKoZUH78yY7M=">AAAB7HicbVBNS8NAEJ3Ur1q/oh69LBbBiyUpoh6LFvRY0bSFNpTNdtMu3WzC7kYoob/BiwdFvPqDvPlv3LY5aOuDgcd7M8zMCxLOlHacb6uwsrq2vlHcLG1t7+zu2fsHTRWnklCPxDyW7QArypmgnmaa03YiKY4CTlvB6Gbqt56oVCwWj3qcUD/CA8FCRrA2klc/e7it9+yyU3FmQMvEzUkZcjR69le3H5M0okITjpXquE6i/QxLzQink1I3VTTBZIQHtGOowBFVfjY7doJOjNJHYSxNCY1m6u+JDEdKjaPAdEZYD9WiNxX/8zqpDq/8jIkk1VSQ+aIw5UjHaPo56jNJieZjQzCRzNyKyBBLTLTJp2RCcBdfXibNasW9qJzfV8u16zyOIhzBMZyCC5dQgztogAcEGDzDK7xZwnqx3q2PeWvBymcO4Q+szx/EoY4C</latexit>

4(4x8 GPUs)
acc.
time

8(8x8 GPUs)
acc.
time

16(16x8 GPUs)
acc.
time

32(32x8 GPUs)
acc.
time

76.32
76.16
76.34

76.47
76.14
76.52

76.46
76.16
76.47

76.25
75.62
76.27

11.6
11.6
11.1

6.3
6.5
5.7

3.7
3.3
2.8

2.2
1.8
1.5

Table. Training loss and wall-clock training time on BERT [CYZ+21]<latexit sha1_base64="RSByxybLLlIgBk0dKlXTTsAg3vY=">AAADunicbVLZbhMxFJ1pWNqUpYVHXiwqUHloNEkpBcRDKWV5gKqEdJEyUWV7bhIrXka2B1RZ/g3EK/wVf4OdDC1pudLIZ+659/guJiVnxmbZ73Shce36jZuLS83lW7fv3F1ZvXdkVKUpHFLFlT4h2ABnEg4tsxxOSg1YEA7HZPIm8sdfQRumZM+elTAQeCTZkFFsg+t0NV3OCYyYdBaHFN9cyilIC5rJUcDnVMWx9k5TGiKWcqtKXXEI8BPYsSpQtMfoHZOYo4/KmPh3jDnfoFzRCeoxAWh9rM0TlOdRQLCiFjjY+PJ+D9UC7db2Vjy3XrSyzix07xK/HQ6XT/t2hFfgN7PWU1/LEmWtEjPlHGRxXnn45ZgAd73Y5cvdt93eqQZTceubfwND96cra1krmxq6Cto1WEtqOwjj+54XilYizIxybEy/nZV24LC2jMZx5pWBEtMJHkE/QIkFmIGblu/Ro+Ap0FDp8EmLpt5/MxwWxpwJEiIFtmNzmYvO/3H9yg6fDxyTZWVB0tlFw4ojq1B8A6hgGqjlZwFgqlmoFdEx1piGxc/fQpSahNmYuU5cYWLBvtnMJXyjSggcRph3u97lsRhCXNf7eZLuezdjKeZu3/s6245BaRCuPr3r1WCODZOtRBlfrHevL3AzN2CpquKDvVDoBOmwyfblvV0FR51W+1lr83NnbWe33uli8iB5mKwn7WQ72Uk+JAfJYUJTnf5If6a/Gq8apMEak1noQlrn3E/mrGH/AHYFLOI=</latexit>

MethodFinal Loss

Wall-clock Time (hrs)

P-SGD
D-SGD

1.75
1.77

59.02
30.4

[YYC+21] B. Ying*, K. Yuan*, Y. Chen*, H. Hu, P. Pan, and W. Yin, “Exponential Graph is Provably Efficient for Deep Training”, NeurIPS 2021
[CYZ+21] Y. Chen*, K. Yuan*, Y. Zhang, P. Pan, Y. Xu, and W. Yin, ``Accelerating Gossip SGD with Periodic Global Averaging”, ICML 2021
Center of Machine Learning Research< 13 >

This talk focuses on decentralized momentum SGD (DmSGD)•

DSGD performs badly in ill-conditioned stochastic optimization; seldom used in real practice<latexit sha1_base64="K5uW5GMso9ECnnL+ck/ZO5PjzFw=">AAADJXicbZJbixMxFMcz421bL9vVR1+CRWmRLTO7RQURFgXxQUotdndhU0smTdu0k2SYZNyWkA/gq34IP41vIvjkJxE8vbj3AwMn53eS/+F/JslSYWwU/Q7Ca9dv3Ly1USrfvnP33mZl6/6+0UXOeJfpVOeHCTU8FYp3rbApP8xyTmWS8oNk+mbBDz7z3AitPtp5xnuSjpQYCkYtlPqVv7NPrjZ9SoY5ZS72bsfXfV/gJ/gVXhI4OeHxNiYjKiXFjiiapNS/rZ3BZGwyyrjbjhpNKf1LMhOnsI7/411gmMhEz1ztvWY0xUU2oJbXoaq0KmTCc0xIuVRaDRWfjEJMIftuQoTChLX6MNAxPD3x+KrpJyeCcaPJTiXbNLcCRCn4QUdCjaC3Uo0a0TLw5SReJ1W0jnZ/K6iQgWaF5MqylBpzFEeZ7bnF0yzlvkwKw0F7Skf8CFJFJTc9t9yTx4+hMsBDncOnLF5Wz95wVBozlwl0SmrH5iJbFK9iR4Udvug5obLCcsVWQsMixVbjxdLxQOSc2XQOCWW5gFkxG1MwzcKvUS4TxY+ZhvWqgSOdjndkIZEkruP9echa3q0orM+1PHDwML7o2OVkf6cRP2vsfmhW916v3dxAD9EjVEMxeo720DvURl3EAhZ8Cb4G38Lv4Y/wZ/hr1RoG6zsP0LkI//wD2d0AVA==</latexit>(k+ 12 )

(k)

(k)

(k)

= xi
rF (xi ; ⇠i ) (Local update)X(k+ 12 )(k+1)
xi=
wij xj(Partial averaging)

xi

j2Ni

Image from“Machine Learning Refined”
Center of Machine Learning Research< 14 >

This talk focuses on decentralized momentum SGD (DmSGD)•

DmSGD can alleviate the “Zig-Zag” and accelerate the convergence; widely used in real applications<latexit sha1_base64="rMg4MLemcvO4jXN8VxvTg0BVg0s=">AAACrXicbVFtaxNBEN4732p8i/rRL4NBSQ2md6WoIEJRED9JBNNWs+kxt9lLN9ndO273tGG5f+cv8Jv/xk1yKbVxYOHheWbm2ZlJCymMjaI/QXjt+o2bt3Zut+7cvXf/QfvhoyOTVyXjQ5bLvDxJ0XApNB9aYSU/KUqOKpX8OJ1/WOrHP3hpRK6/2kXBxwqnWmSCofVU0v6lEnHquvNevFvD83dAU24RGtJTPaAaU4nwsXu+Id/Sc7HBu0Bpq1F6NCuRubh2+/W620UJvAQ6RaUuWq/8LpVu7E2lEjejQgNVaM8YSve5TkQNPxMnZrXvONu2StqdqB+tArZB3IAOaWKQtH/TSc4qxbVlEo0ZxVFhxw5LK5jkdYtWhhfI5jjlIw81Km7GbrXtGp55ZgJZXvqnLazYyxUOlTELlfrM5QjmqrYk/6eNKpu9GTuhi8pyzdZGWSXB5rA8HUxEyZmVCw+QlcL/FdgZ+j1Yf+CWX0J8deRtcLTfj1/1D74cdA7fN+vYIU/IU9IlMXlNDsknMiBDwoIXwSD4FnwP98JhSMPTdWoYNDWPyT8RTv8CXuvNPg==</latexit>

(k+1)

mi

(k)

= mi

(k+ 12 )
(k)
xi
= xi
(k+1)
xi
=

X

(k) (k)+ rF (xi ; ⇠i ) (Momentum update)
(k+1)

mi

(k+ 12 )wij xj(Local variable update)

Reduce to DSGD
when = 0<latexit sha1_base64="2I1yrjKmeu2N0iPAW6pTy+SxsCw=">AAAB8HicbVBNS8NAEJ3Ur1q/qh69LBbBU0lE1ItQ9OKxgv2QNpTNdtIu3WzC7kYoob/CiwdFvPpzvPlv3LY5aOuDgcd7M8zMCxLBtXHdb6ewsrq2vlHcLG1t7+zulfcPmjpOFcMGi0Ws2gHVKLjEhuFGYDtRSKNAYCsY3U791hMqzWP5YMYJ+hEdSB5yRo2VHrsBGkquidsrV9yqOwNZJl5OKpCj3it/dfsxSyOUhgmqdcdzE+NnVBnOBE5K3VRjQtmIDrBjqaQRaj+bHTwhJ1bpkzBWtqQhM/X3REYjrcdRYDsjaoZ60ZuK/3md1IRXfsZlkhqUbL4oTAUxMZl+T/pcITNibAllittbCRtSRZmxGZVsCN7iy8ukeVb1Lqrn9+eV2k0eRxGO4BhOwYNLqMEd1KEBDCJ4hld4c5Tz4rw7H/PWgpPPHMIfOJ8/aayPgg==</latexit>(Partial averaging)

j2NiCenter of Machine Learning Research< 15 >

Large-batch training is a must in large-scale deep learning•

Total batch size increases as the number of nodes (GPUs) grows•

Suppose each node takes 256 samples per iteration:•(8 nodes)256 ⇥ 8 = 2K

(samples)(64 nodes)

256 ⇥ 64 = 16K(samples)(256 nodes)

256 ⇥ 256 = 64K(samples)<latexit sha1_base64="x8PK4g76ySy2BsbGjH4G4XW0cBM=">AAAB+nicbVBNS8NAEJ3Ur1q/Uj16WSyCp5KUWnsRil4ELxXsB7ShbLabdulmE3Y3Sqn9KV48KOLVX+LNf+O2zUFbHww83pthZp4fc6a043xbmbX1jc2t7HZuZ3dv/8DOHzZVlEhCGyTikWz7WFHOBG1opjltx5Li0Oe05Y+uZ37rgUrFInGvxzH1QjwQLGAEayP17HzpvIK6moVUoSq6RKXbnl1wis4caJW4KSlAinrP/ur2I5KEVGjCsVId14m1N8FSM8LpNNdNFI0xGeEB7RgqsNnlTeanT9GpUfooiKQpodFc/T0xwaFS49A3nSHWQ7XszcT/vE6ig6o3YSJONBVksShIONIRmuWA+kxSovnYEEwkM7ciMsQSE23SypkQ3OWXV0mzVHQrxfJduVC7SuPIwjGcwBm4cAE1uIE6NIDAIzzDK7xZT9aL9W59LFozVjpzBH9gff4ABoyR6w==</latexit><latexit sha1_base64="ZeWYBpY6mcqN84eV1VXe8DcGhGw=">AAAB/HicbVDLSsNAFJ3UV62vaJduBovgqiSlRjdC0Y3gpoJ9QBvKZDpph04ezNwIIdRfceNCEbd+iDv/xmmbhbYeuHA4517uvceLBVdgWd9GYW19Y3OruF3a2d3bPzAPj9oqSiRlLRqJSHY9opjgIWsBB8G6sWQk8ATreJObmd95ZFLxKHyANGZuQEYh9zkloKWBWa6dO7gPPGAKO3V8hW3nbmBWrKo1B14ldk4qKEdzYH71hxFNAhYCFUSpnm3F4GZEAqeCTUv9RLGY0AkZsZ6mIdHb3Gx+/BSfamWI/UjqCgHP1d8TGQmUSgNPdwYExmrZm4n/eb0E/Es342GcAAvpYpGfCAwRniWBh1wyCiLVhFDJ9a2YjokkFHReJR2CvfzyKmnXqrZTrd/XK43rPI4iOkYn6AzZ6AI10C1qohaiKEXP6BW9GU/Gi/FufCxaC0Y+U0Z/YHz+APYjkmY=</latexit><latexit sha1_base64="WSdbjcE0iseOMctsIcnT5pNhlf8=">AAAB/XicbZDLSsNAFIZP6q3WW7zs3AwWwVVJSq1uhKIbwU0F2wptKJPppB06mYSZiVBL8VXcuFDEre/hzrdx0mahrT8MfPznHM6Z3485U9pxvq3c0vLK6lp+vbCxubW9Y+/uNVWUSEIbJOKRvPexopwJ2tBMc3ofS4pDn9OWP7xK660HKhWLxJ0exdQLcV+wgBGsjdW1D8qnVdTRLKQKpXiBqpWbrl10Ss5UaBHcDIqQqd61vzq9iCQhFZpwrFTbdWLtjbHUjHA6KXQSRWNMhrhP2wYFNuu88fT6CTo2Tg8FkTRPaDR1f0+McajUKPRNZ4j1QM3XUvO/WjvRwbk3ZiJONBVktihIONIRSqNAPSYp0XxkABPJzK2IDLDERJvACiYEd/7Li9Asl9xqqXJbKdYuszjycAhHcAIunEENrqEODSDwCM/wCm/Wk/VivVsfs9aclc3swx9Znz9yKZKm</latexit>

Large-batch training is a must for large-scale deep training with massive number of GPUs

Center of Machine Learning Research< 16 >

DmSGD performs well in small-batch scenario•

Experimental setting: CIFAR-10; ResNet-20•

Baseline: parallel (centralized) momentum SGD (PmSGD)•

Small-batch: 2K total batch-size per iteration

DmSGD and PmSGD have almost the same performance with small-batch
Center of Machine Learning Research< 17 >

However, DmSGD performs badly in large-batch scenario•

Experimental setting: CIFAR-10; ResNet-20•

Large-batch: 8K total batch-size per iteration

DmSGD drops 1% performance compared to PmSGD with large-batch
Center of Machine Learning Research< 18 >

Two critical questions:• Why does DmSGD have severe performance degradation with large batch size?

• Can we overcome such degradation?

Center of Machine Learning Research< 19 >

PART 02
Reason behind Performance Degradation

DmSGD limiting bias•

The limiting bias of DSGD/DmSGD (s.c. cost) typically suffers from two sources<latexit sha1_base64="dqY5ZTivGtzWDGOv36Go5jBItnI=">AAACY3icbVFBaxQxGM2M2tat2rH1JkJwESriMlOK9VIoFcFjBbctbHaHJJtpw2aSIfmm7DbNn/TmrRf/h9ntHLT1g8DjvfeRvBfWKOkgz38l6aPHT9bWN572Np89f7GVvdw+daa1XAy5UcaeM+qEkloMQYIS540VtGZKnLHZl6V+diWsk0b/gEUjxjW90LKSnEKkyuyaKFmXfkbAYCJ1BYuASWUp90XwOhDXRlUeFmGiMakpXDLmvwZyMy/lxO/O3gf8Ec8nxAG15Gayhw+ji5m5d2AGmEnqAv7QUVJzo12M1All1s8H+WrwQ1B0oI+6OSmzn2RqeFsLDVxR50ZF3sDYUwuSKxF6pHWioXxGL8QoQk1r4cZ+1VHA7yIzxZWx8WjAK/bvDU9r5xY1i85lTHdfW5L/00YtVJ/HMVzTgtD87qKqVTgWuiwcT6UVHNQiAsqtjG/F/JLGhiF+Sy+WUNyP/BCc7g2KT4P97/v9o+Oujg30Gr1Fu6hAB+gIfUMnaIg4uk3Wkq0kS36nm+l2+urOmibdzg76Z9I3fwCtTLgu</latexit>

lim

n
X
1

k!1 n

i=1

(k)

Ekxi

x? k2 = sto. bias + inconsist. bias

§ Stochastic bias is caused by the gradient noise§ Inconsistency bias is caused by data heterogeneity (i.e., different distribution Di )<latexit sha1_base64="UBCoSKccsYAsMigUfrgabNRLyug=">AAAB9HicbVDLSgMxFL2pr1pfVZdugkVwVWakqMuiLlxWsA9oh5JJM21oJjMmmUIZ+h1uXCji1o9x59+YaWehrQcCh3Pu5Z4cPxZcG8f5RoW19Y3NreJ2aWd3b/+gfHjU0lGiKGvSSESq4xPNBJesabgRrBMrRkJfsLY/vs389oQpzSP5aKYx80IylDzglBgreb2QmBElIr2b9Xm/XHGqzhx4lbg5qUCORr/81RtENAmZNFQQrbuuExsvJcpwKtis1Es0iwkdkyHrWipJyLSXzkPP8JlVBjiIlH3S4Ln6eyMlodbT0LeTWUi97GXif143McG1l3IZJ4ZJujgUJAKbCGcN4AFXjBoxtYRQxW1WTEdEEWpsTyVbgrv85VXSuqi6l9XaQ61Sv8nrKMIJnMI5uHAFdbiHBjSBwhM8wyu8oQl6Qe/oYzFaQPnOMfwB+vwB+i+SPw==</latexit>n<latexit sha1_base64="4s4k+h9xgjmrws+lvj2BUmbO47g=">AAACk3icbVHtahQxFM2MX3X8WhVB8E/sImxBlhkVFUqh1Cr+EeritoXNdshkMt3QfIxJxs4S8ga+oG8hPoGZ3RG09ULgcM65yc25Rc2ZsWn6I4qvXL12/cbGzeTW7Tt37w3uPzg0qtGEToniSh8X2FDOJJ1aZjk9rjXFouD0qDh71+lH36g2TMkvdlnTucCnklWMYBuofPAdCSZz10LEJESTyUnp0dcGl7AatVtwB6JKY+Iy76RHphG5YzuZP5GwylkwPIdrMxKFat35gmrqe2pt6G4Q2C6Kwr33uXOoZT5nEBkm4H7O/IdRuw17dmucD4bpOF0VvAyyHgxBXwf54CcqFWkElZZwbMwsS2s7d1hbRjj1CWoMrTE5w6d0FqDEgpq5W6Xm4bPAhDmVDkdauGL/7nBYGLMURXB2XzAXtY78nzZrbPV27pisG0slWT9UNRxaBbsVwJJpSixfBoCJZmFWSBY45GzDopIESXpOlBBYli5sxLs/CU68T0JE2cVALoPDF+Ps9fjl51fD3b0+rA3wBGyCEcjAG7ALPoIDMAUE/IoeR0+jzfhRvB3vxftraxz1PQ/BPxV/+g1ixch4</latexit>

min

x2Rd

Center of Machine Learning Research

1X
f (x) =fi (x),
n i=1

where

fi (x) = E⇠i ⇠Di F (x; ⇠i ).
< 21 >

DmSGD limiting bias: an illustration•

Take DSGD as an example, its limiting bias (s.c. cost) is derived as [YAYS20]
n

1X
(k)
lim
Ekxi
k!1 n
i=1
<latexit sha1_base64="ZxLkwWnJfT4Zto9/MEs+aMW7pL4=">AAAC5nicdVLdahQxGM2Mf3X96VYvvQkuwi7SZWcp6k2hVATvrOC2hc3OkGQzs2GTzJBkSpc0D+CNF4p46zN558MIZnZH0NZ+EObwnZyT5HxDKsGNHY1+RvGNm7du39m627l3/8HD7e7Oo2NT1pqyCS1FqU8JNkxwxSaWW8FOK82wJIKdkOXrhj85Y9rwUn2wq4rNJC4UzznFNrSy7i8kuMzcEtkSIq5yu/Io15i6xDvlkakDyfcTnyoksV0Q4t54dHGe8dT1lwMPd+F5iozFGl2kY7gP4Tt0yIs+RLWaM02CE3MbQ1RgKXE6RoYXzbfxh8/hdWSyi/Si9D5zSEtobDlEkHBs1pprzSFptP2NeBBwq+eKlsqEOP+4NLccwKzbGw1H64JXQdKCHmjrKOv+QPOS1pIpSwU2ZpqMKjtzWFtOBfMdVBtWYbrEBZsGqLBkZubWY/LwWejMYV7qsJSF6+7fCoelMStJws4ma3OZa5r/46a1zV/NHFdVbZmim4PyWsAw02bmcM41o1asAsBU83BXSBc45GbDn9EJISSXn3wVHI+HyYvh3vu93sFhG8cWeAKegj5IwEtwAN6CIzABNKLRx+hz9CVexJ/ir/G3zdY4ajWPwT8Vf/8NTnnrIQ==</latexit>n•

Quantity

2<latexit sha1_base64="7hPbLxmhkW66hlOsHJ+dAcUnUkw=">AAAB73icbVBNSwMxEJ2tX7V+VT16CRbBU9ktRT0WvXisYD+gXUs2zbahSXZNskJZ+ie8eFDEq3/Hm//GdLsHbX0w8Hhvhpl5QcyZNq777RTW1jc2t4rbpZ3dvf2D8uFRW0eJIrRFIh6pboA15UzSlmGG026sKBYBp51gcjP3O09UaRbJezONqS/wSLKQEWys1O1rNhL4oTYoV9yqmwGtEi8nFcjRHJS/+sOIJIJKQzjWuue5sfFTrAwjnM5K/UTTGJMJHtGepRILqv00u3eGzqwyRGGkbEmDMvX3RIqF1lMR2E6BzVgve3PxP6+XmPDKT5mME0MlWSwKE45MhObPoyFTlBg+tQQTxeytiIyxwsTYiEo2BG/55VXSrlW9i2r9rl5pXOdxFOEETuEcPLiEBtxCE1pAgMMzvMKb8+i8OO/Ox6K14OQzx/AHzucPyLKP0A==</latexit>

denotes gradient noise;<latexit sha1_base64="WVqy9sOIUkqGNq2ZesdFOhKy+iE=">AAACN3icbVDLSgMxFM3UV62vqks3wSJU0DIjRUUQim5cVugLOrVkMpk2NJMZkoxQpvMv/oY/4Fa3rtwVt/6BmbagrR4InHvuvdyT44SMSmWa70ZmaXlldS27ntvY3Nreye/uNWQQCUzqOGCBaDlIEkY5qSuqGGmFgiDfYaTpDG7TfvORCEkDXlPDkHR81OPUoxgpLXXzV7boB/Aa2qMmPIW2JxCOrSTmie0j1XelLn7YQ80eQZtyWDRPrONuvmCWzAngX2LNSAHMUO3mx7Yb4MgnXGGGpGxbZqg6MRKKYkaSnB1JEiI8QD3S1pQjn8hOPPljAo+04kIvEPpxBSfq740Y+VIOfUdPpn7lYi8V/+u1I+VddmLKw0gRjqeHvIhBFcA0MOhSQbBiQ00QFlR7hbiPdE5Kx5qbO+PK1Fuig7EWY/hLGmcl67xUvi8XKjeziLLgAByCIrDABaiAO1AFdYDBE3gBr+DNeDY+jLHxOR3NGLOdfTAH4+sbgCSroQ==</latexit>

•

2 2

|

n

⌘
b
+
⇢
(1 ⇢)2}| {z }

2 2

+
1
{z

sto. bias

2 2inconsist. bias

1X
2
Quantity b =krfi (x? )k2 denotes data heterogeneity; b2 = 0 when fi (x) = fj (x) = f (x)n i=1<latexit sha1_base64="O1sjhXj/2MkwPVky1/rM4VvvGw8=">AAACIHicbVBNS8NAEN34WetX1KOXxSLopSSlWC+FohePFWwtNG2YbDe6uNmE3Y1Y0vwUL/4VLx4U0Zv+Gre1B60+GHi8N8PMvCDhTGnH+bDm5hcWl5YLK8XVtfWNTXtru63iVBLaIjGPZScARTkTtKWZ5rSTSApRwOllcHM69i9vqVQsFhd6mNBeBFeChYyANpJv14J+BdexF0ogmZtnIvdUGvkZq7t5X2Bv5AkIOODQZwd3fU9pkIfeqF/x7ZJTdibAf4k7JSU0RdO3371BTNKICk04KNV1nUT3MpCaEU7zopcqmgC5gSvaNVRARFUvmzyY432jDHAYS1NC44n6cyKDSKlhFJjOCPS1mvXG4n9eN9XhcS9jIkk1FeR7UZhyrGM8TgsPmKRE86EhQCQzt2JyDSYrbTItmhDc2Zf/knal7B6Vq+fVUuNkGkcB7aI9dIBcVEMNdIaaqIUIukeP6Bm9WA/Wk/VqvX23zlnTmR30C9bnF8G5osA=</latexit>•x? k2 = O⇣

Quantity ⇢ = kW<latexit sha1_base64="bv1p2AGWXhexdrj4S0Kswp/IxhM=">AAAB9XicbVBNTwIxEJ3FL8Qv1KOXRmLiiewSoh6JXjxiImDCLqRbutDQdjdtV0M2/A8vHjTGq//Fm//GAntQ8CWTvLw3k5l5YcKZNq777RTW1jc2t4rbpZ3dvf2D8uFRW8epIrRFYh6rhxBrypmkLcMMpw+JoliEnHbC8c3M7zxSpVks780koYHAQ8kiRrCxUs/XbChwr4Z8EyO3X664VXcOtEq8nFQgR7Nf/vIHMUkFlYZwrHXXcxMTZFgZRjidlvxU0wSTMR7SrqUSC6qDbH71FJ1ZZYCiWNmSBs3V3xMZFlpPRGg7BTYjvezNxP+8bmqiqyBjMkkNlWSxKEo5si/OIkADpigxfGIJJorZWxEZYYWJsUGVbAje8surpF2rehfV+l290rjO4yjCCZzCOXhwCQ24hSa0gICCZ3iFN+fJeXHenY9Fa8HJZ47hD5zPH0pMkbs=</latexit>

2<latexit sha1_base64="7bahaDxP5dykYSFX/diIl3xlF/s=">AAAB7nicbVDLSgNBEOyNrxhfUY9eBoPgKeyGoF6EoBePEcwDkjXMTmaTIbOzy0yvEEI+wosHRbz6Pd78GyfJHjSxoKGo6qa7K0ikMOi6305ubX1jcyu/XdjZ3ds/KB4eNU2casYbLJaxbgfUcCkUb6BAyduJ5jQKJG8Fo9uZ33ri2ohYPeA44X5EB0qEglG0Uit4rJBr4vaKJbfszkFWiZeREmSo94pf3X7M0ogrZJIa0/HcBP0J1SiY5NNCNzU8oWxEB7xjqaIRN/5kfu6UnFmlT8JY21JI5urviQmNjBlHge2MKA7NsjcT//M6KYZX/kSoJEWu2GJRmEqCMZn9TvpCc4ZybAllWthbCRtSTRnahAo2BG/55VXSrJS9i3L1vlqq3WRx5OEETuEcPLiEGtxBHRrAYATP8ApvTuK8OO/Ox6I152Qzx/AHzucPi8qOaA==</latexit><latexit sha1_base64="5I1AydUjk+3ujUD5nA5D+iOv6jk=">AAAB/3icbZDLSgMxFIbP1Futt1HBjZtgEeqmzEhRN0LRjcsK9gLtMGTSTBubyQxJRiy1C1/FjQtF3Poa7nwb03YWWj0Q8vH/55CTP0g4U9pxvqzcwuLS8kp+tbC2vrG5ZW/vNFScSkLrJOaxbAVYUc4ErWumOW0lkuIo4LQZDC4nfvOOSsVicaOHCfUi3BMsZARrI/n2Xuiz0v0ROkehf5uBuXy76JSdaaG/4GZQhKxqvv3Z6cYkjajQhGOl2q6TaG+EpWaE03GhkyqaYDLAPdo2KHBElTea7j9Gh0bpojCW5giNpurPiRGOlBpGgemMsO6reW8i/ue1Ux2eeSMmklRTQWYPhSlHOkaTMFCXSUo0HxrARDKzKyJ9LDHRJrKCCcGd//JfaByX3ZNy5bpSrF5kceRhHw6gBC6cQhWuoAZ1IPAAT/ACr9aj9Wy9We+z1pyVzezCr7I+vgE0xpOo</latexit>! 0 as batch-size grows large

1 T
11 k 2 (0, 1) characterizes the network topology connectivityn[YAYS20] K. Yuan, S. Alghunaim, B. Ying and A. Sayed, “On the influence of bias-correction on distributed stochastic optimization”, IEEE TSP, 2020
Center of Machine Learning Research< 22 >

Inconsistency bias dominates large-batch setting

Proposition. Inconsistency bias dominates convergence of large-batch DmSGD.
<latexit sha1_base64="DbKVsWmoGmVhxteQzWFmuS1NbHo=">AAACXHicbZBNaxsxEIblbT6dj7ot5JKLiAnkkmU3hCbH0Aba3hxaJwHbmFntrC2ij0WaDTWLf15/RC899tJre6/W8aFJOiB4ed+RZvRkpZKekuR7K3qxsrq2vrHZ3tre2X3ZefX62tvKCewLq6y7zcCjkgb7JEnhbekQdKbwJrt73+Q39+i8tOYLzUocaZgYWUgBFKxxZzw0VpocDfEh4VfKirrnbGm9bPJ4zj8ZYY0Pi6ARM55J8Dy3Whog9DxE4fFJiJDbgisI+jgDElPOL/XnD5fxuNNN4mRR/LlIl6LLltUbd34OcysqHTYSCrwfpElJoxocSaFw3h5WHksQdzDBQZAGNPpRvQAx54fByXlhXTjhRwv33xs1aO9nOgudGmjqn2aN+b9sUFFxPqqlKauGw8OgolKcLG+o8lw6FKRmQYBwgZ3gYgoOBAX27Udjct/sNg9g0qcYnovrkzh9G59enXQv3i0RbbB9dsCOWMrO2AX7yHqszwT7xn6x3+xP60e0Em1FOw+tUWt55w17VNHeX9nOuKA=</latexit>

Small-batch settingsto. bias
Center of Machine Learning Researchinconst. bias
< 23 >

Inconsistency bias dominates large-batch setting

Proposition. Inconsistency bias dominates convergence of large-batch DmSGD.
<latexit sha1_base64="DbKVsWmoGmVhxteQzWFmuS1NbHo=">AAACXHicbZBNaxsxEIblbT6dj7ot5JKLiAnkkmU3hCbH0Aba3hxaJwHbmFntrC2ij0WaDTWLf15/RC899tJre6/W8aFJOiB4ed+RZvRkpZKekuR7K3qxsrq2vrHZ3tre2X3ZefX62tvKCewLq6y7zcCjkgb7JEnhbekQdKbwJrt73+Q39+i8tOYLzUocaZgYWUgBFKxxZzw0VpocDfEh4VfKirrnbGm9bPJ4zj8ZYY0Pi6ARM55J8Dy3Whog9DxE4fFJiJDbgisI+jgDElPOL/XnD5fxuNNN4mRR/LlIl6LLltUbd34OcysqHTYSCrwfpElJoxocSaFw3h5WHksQdzDBQZAGNPpRvQAx54fByXlhXTjhRwv33xs1aO9nOgudGmjqn2aN+b9sUFFxPqqlKauGw8OgolKcLG+o8lw6FKRmQYBwgZ3gYgoOBAX27Udjct/sNg9g0qcYnovrkzh9G59enXQv3i0RbbB9dsCOWMrO2AX7yHqszwT7xn6x3+xP60e0Em1FOw+tUWt55w17VNHeX9nOuKA=</latexit>

Midium-batch settingsto. bias
Center of Machine Learning Researchinconst. bias
< 24 >

Inconsistency bias dominates large-batch setting

Proposition. Inconsistency bias dominates convergence of large-batch DmSGD.
<latexit sha1_base64="DbKVsWmoGmVhxteQzWFmuS1NbHo=">AAACXHicbZBNaxsxEIblbT6dj7ot5JKLiAnkkmU3hCbH0Aba3hxaJwHbmFntrC2ij0WaDTWLf15/RC899tJre6/W8aFJOiB4ed+RZvRkpZKekuR7K3qxsrq2vrHZ3tre2X3ZefX62tvKCewLq6y7zcCjkgb7JEnhbekQdKbwJrt73+Q39+i8tOYLzUocaZgYWUgBFKxxZzw0VpocDfEh4VfKirrnbGm9bPJ4zj8ZYY0Pi6ARM55J8Dy3Whog9DxE4fFJiJDbgisI+jgDElPOL/XnD5fxuNNN4mRR/LlIl6LLltUbd34OcysqHTYSCrwfpElJoxocSaFw3h5WHksQdzDBQZAGNPpRvQAx54fByXlhXTjhRwv33xs1aO9nOgudGmjqn2aN+b9sUFFxPqqlKauGw8OgolKcLG+o8lw6FKRmQYBwgZ3gYgoOBAX27Udjct/sNg9g0qcYnovrkzh9G59enXQv3i0RbbB9dsCOWMrO2AX7yHqszwT7xn6x3+xP60e0Em1FOw+tUWt55w17VNHeX9nOuKA=</latexit>

Large-batch settingsto. bias
Center of Machine Learning Researchinconst. bias
< 25 >

DmSGD incurs severe inconsistency bias•

Therefore, it is enough to examine the inconsistency bias in large-batch setting•

We rewrite full-batch DmSGD as<latexit sha1_base64="2ImeFdlhzZBeCHGthYfHIZ23tIw=">AAACoXicbVFdb9MwFHXC11Y+VuBxErqiAnWqqJJpAl6Qpo0HeGAqiG6T6hLduE7n1nai2AEqK/+L38Eb/wa3zaaxciVLx+d+HN/jtJDC2Cj6E4S3bt+5e29ru3X/wcNHO+3HT05NXpWMD1ku8/I8RcOl0HxohZX8vCg5qlTys3R+vMyffeelEbn+ahcFHyucapEJhtZTSfuXSsQ315334r0aXr4DmnKL0JCe6gHVmEqErPvzktwDSlvNrUezEpmLa7dfrydclcEroFNU6mrcSuNa66WkqVTiZlRooArtBUPpTupE1PAjcWJW+4mzTamk3Yn60SpgE8QN6JAmBkn7N53krFJcWybRmFEcFXbssLSCSV63aGV4gWyOUz7yUKPiZuxWDtfwwjMTyPLSH21hxV7vcKiMWajUVy5XMDdzS/J/uVFls7djJ3RRWa7ZWiirJNgclt8FE1FyZuXCA2Sl8G8FdoHeB+s/teVNiG+uvAlO9/vx6/7B54PO4VFjxxbZJc9Jl8TkDTkkH8iADAkLngXvg0/BSdgJP4aD8Mu6NAyanqfknwhHfwEsk8iU</latexit>

(k+1)

mi

(k)

= mi

(k+ 12 )
(k)
xi
= xi
(k+1)
xi
=

X

(k)

+ rfi(xi )(Momentum update)mi(Local variable update)<latexit sha1_base64="CzRuuz3qOwikXCfcqltShnKr0vY=">AAACFXicbVBNSwMxEM3Wr7p+VT16CRbBU9kVUY9FLx5bsB/QLiWbZtvQZLMks0pZ+gu8Kv4ab+LVs79G03YPtvXBwOO9GWbmhYngBjzv2ymsrW9sbhW33Z3dvf2D0uFR06hUU9agSijdDolhgsesARwEayeaERkK1gpHd1O/9ci04Sp+gHHCAkkGMY84JWClOu+Vyl7FmwGvEj8nZZSj1iv9dPuKppLFQAUxpuN7CQQZ0cCpYBO3mxqWEDoiA9axNCaSmSCbHTrBZ1bp40hpWzHgmfp3IiPSmLEMbackMDTL3lT8z+ukEN0EGY+TFFhM54uiVGBQePo17nPNKIixJYRqbm/FdEg0oWCzcRfWhEqNgIRm4ZVMpgK4Vk8T1ybmL+ezSpoXFf+qclm/LFdv8+yK6ASdonPko2tURfeohhqIIoae0Qt6dd6cd+fD+Zy3Fpx85hgtwPn6BVSbn9Q=</latexit>(k+1)(k+ 12 )wij xj(Partial averaging)

j2NiCenter of Machine Learning Research< 26 >

DmSGD incurs severe inconsistency bias•

Therefore, it is enough to examine the inconsistency bias in large-batch setting•

We rewrite full-batch DmSGD as<latexit sha1_base64="qEMoBe1SVNstTWCeTYMHXirO2Yw=">AAADH3ichVJbaxNBFJ5db228NNVHXw4GS0ptyEq9vAilBvRJKpq2kInL7GSSTjIzG+eiCcP+E1/8K774oIj41n/jbLKIaQUPDHyc6/edOdlUcGPb7bMovnT5ytVra+u16zdu3tqob94+MrnTlHVpLnJ9khHDBFesa7kV7GSqGZGZYMfZ5HkZP/7AtOG5emvnU9aXZKT4kFNigyvdjB7NUv7ONyc7yXYBW88AOzVgOtOEMo+Nk6kfY64AS2JPKRH+VZHyAj6mno8LwAd81IRZOi47hPpdwCMiJQGsSCYIDNNx8090e5G+XaQeawmdNy86oYHKlZMZ04BxbX0Lv3dkADurJDJmSTXJ44VinwnHior4cuz/mFYsdoPKYoWHzCVT1sniAQY8zDURAnjZp6f6LVgSKg3LLJ/5ZkcG3qG23mi32guDiyCpQANVdpjWf+FBTl05iwpiTC9pT23fE205FayoYWfYlNAJGbFegIpIZvp+obaA+8EzgEAuPGVh4f27whNpzFxmIbMUb87HSue/Yj1nh0/7nqups0zR5aChE2BzKI8FBlwzasU8AEI1D1yBnpLwLTacVC0sITkv+SI4ethKHrf2Xu819g+qdayhu+geaqIEPUH76CU6RF1Eo0/Rl+hb9D3+HH+Nf8Q/l6lxVNXcQSsWn/0GeIP7oA==</latexit>

(k+1)
xi
=

X

(k)
wij xj

j2Ni

|

+
|

Center of Machine Learning Research

⇣

⇣

(k)
rfj (xj )

{z

DSGD
(k)
xi

X

(k 1)
wij xjj2Ni{zmomentum⌘⌘}, 8i 2 [n].

(DmSGD)}< 27 >

DmSGD incurs severe inconsistency bias

<latexit sha1_base64="qEMoBe1SVNstTWCeTYMHXirO2Yw=">AAADH3ichVJbaxNBFJ5db228NNVHXw4GS0ptyEq9vAilBvRJKpq2kInL7GSSTjIzG+eiCcP+E1/8K774oIj41n/jbLKIaQUPDHyc6/edOdlUcGPb7bMovnT5ytVra+u16zdu3tqob94+MrnTlHVpLnJ9khHDBFesa7kV7GSqGZGZYMfZ5HkZP/7AtOG5emvnU9aXZKT4kFNigyvdjB7NUv7ONyc7yXYBW88AOzVgOtOEMo+Nk6kfY64AS2JPKRH+VZHyAj6mno8LwAd81IRZOi47hPpdwCMiJQGsSCYIDNNx8090e5G+XaQeawmdNy86oYHKlZMZ04BxbX0Lv3dkADurJDJmSTXJ44VinwnHior4cuz/mFYsdoPKYoWHzCVT1sniAQY8zDURAnjZp6f6LVgSKg3LLJ/5ZkcG3qG23mi32guDiyCpQANVdpjWf+FBTl05iwpiTC9pT23fE205FayoYWfYlNAJGbFegIpIZvp+obaA+8EzgEAuPGVh4f27whNpzFxmIbMUb87HSue/Yj1nh0/7nqups0zR5aChE2BzKI8FBlwzasU8AEI1D1yBnpLwLTacVC0sITkv+SI4ethKHrf2Xu819g+qdayhu+geaqIEPUH76CU6RF1Eo0/Rl+hb9D3+HH+Nf8Q/l6lxVNXcQSsWn/0GeIP7oA==</latexit>

(k+1)
xi
=

X

(k)
wij xj

j2Ni

|

+
|

⇣

⇣

(k)
rfj (xj )

{z

DSGD
(k)
xi

X

(k 1)
wij xj

j2Ni

{z

(k)

⌘

}

, 8i 2 [n].

(DmSGD)}

momentum<latexit sha1_base64="OYuL7pZJjhQdNmohOHZ6YRxUG78=">AAACJnicbVDLSgMxFM3UV62vUZduglXQhWWmiLoRim5cSQX7gE4dMmlq02YyY5LRlmG+xo2/4sZFRcSdn2Km7UJbDwQO55xL7j1eyKhUlvVlZObmFxaXssu5ldW19Q1zc6sqg0hgUsEBC0TdQ5IwyklFUcVIPRQE+R4jNa93mfq1RyIkDfitGoSk6aN7TtsUI6Ul1zzf67v0Lj7oHSbQ4eQBOjLy3bjrUA4dH6kORiy+TlyawCc3pt0E9t1umj+yD5M918xbBWsEOEvsCcmDCcquOXRaAY58whVmSMqGbYWqGSOhKGYkyTmRJCHCPXRPGppy5BPZjEdnJnBfKy3YDoR+XMGR+nsiRr6UA9/TyXRzOe2l4n9eI1Lts2ZMeRgpwvH4o3bEoApg2hlsUUGwYgNNEBZU7wpxBwmElW42p0uwp0+eJdViwT4pHN8U86WLSR1ZsAN2wQGwwSkogStQBhWAwTN4BUPwbrwYb8aH8TmOZozJzDb4A+P7B3slpSk=</latexit>

⌘

P

(k 1)

•

Momentum will not vanish as xi•

Compared to DSGD, momentum will incur additional inconsistency bias

Center of Machine Learning Research

6=

j2Ni wij xj

as k ! 1<latexit sha1_base64="XPVLJ0TT/R5Iw7TBNXSPkF287WA=">AAAB83icbVBNS8NAEJ3Ur1q/qh69LBbBU0lE1GPRi8cK9gOaUDbbTbt0swm7EyGU/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTKUw6LrfTmltfWNzq7xd2dnd2z+oHh61TZJpxlsskYnuhtRwKRRvoUDJu6nmNA4l74Tju5nfeeLaiEQ9Yp7yIKZDJSLBKFrJHxMfE+ILFWHer9bcujsHWSVeQWpQoNmvfvmDhGUxV8gkNabnuSkGE6pRMMmnFT8zPKVsTIe8Z6miMTfBZH7zlJxZZUCiRNtSSObq74kJjY3J49B2xhRHZtmbif95vQyjm2AiVJohV2yxKMoksX/OAiADoTlDmVtCmRb2VsJGVFOGNqaKDcFbfnmVtC/q3lX98uGy1rgt4ijDCZzCOXhwDQ24hya0gEEKz/AKb07mvDjvzseiteQUM8fwB87nD5oxkWs=</latexit>< 28 >

DmSGD incurs severe inconsistency bias

<latexit sha1_base64="oYzIHqbGqQjLGxB2P1H3VzQgw4M=">AAADfnicbVLbbtNAEHUSLiXcUnjkZaABOaVx4whBhVSpaivBG0W9St0kWq/H9irrXcu7po1c/wVfxhvfwgvrJEKQMpKl47nszJw5QSa4NoPBz0azdefuvftrD9oPHz1+8rSz/uxMqyJneMqUUPlFQDUKLvHUcCPwIsuRpoHA82B6UMfPv2GuuZInZpbhKKWx5BFn1FjXZL3xnUjFZYjSADF4bYKoPMpVpjSvE7wKThKEqBCiH1DDEjhMjz8dgnvsHXjAlDY9SKgGUycpIdQVlzFwyZTUdniUbAYBp/pjmwQYc1lSwWO5WbWJ4OmknBKjgHAZmVkFJMopK/2qlBXRhY3yXb8aSyA31xM+Lt1pr4I+XI+JNjQnN+Mh7MIXss9jd1lKYpqm1PqD8bAqXb9vexraGw9rmCfKItvFFvS22gRl+GeYqwRzhG4wf9L1t2VvZQAiaSAoRBPuLvv36gG6YHlTBhf7h9TQ1dXRXCFKkCpEvQVUhtCdD9UFvihKVWqpL1LLJUb2LNz+ee1JZ2PgDeYGt4G/BBvO0o4mnR8kVKyo32KCan3pDzIzKmluOBNo6S40ZpRNaYyXFkqaoh6Vc/lU8Np6Qnu+3H5WBnPv3xUlTbWepYHNTKlJ9Gqsdv4vdlmYaGdUcpkVNR2LRlZKYI9eaxFCniMzYmYBZbkVHAOWUHtKYxVbk+CvrnwbnA09/7337utwY29/Scea88J55biO73xw9pzPzpFz6rDGr+bL5mbzbctpvWn1W9uL1GZjWfPc+cdaO78BLPIY8w==</latexit>

Proposition. The full-batch DmSGD (S.C. cost) has the following inconsistency bias:n

1 X (k)
lim
kxi
k!1 n
i=1

? 2

x k =O

⇣

2 2

(1

b
)2 (1

⇢)2

⌘

,

Pn
where b2 = (1/n) i=1 krfi (x? )k2 denotes the data inconsistency between
nodes, and is the momentum coefficient.

•

Recall that full-batch DSGD has limiting bias as O( 2 b2 /(1•The momentum in DmSGD amplifies inconsistency bias as⇢)2 )<latexit sha1_base64="PLx25rGPhrEqjtIjFJJXulHLkaE=">AAACCHicbVDLTgIxFO3gC/E16tKFjcQEFuIMIeqS6MadmMgjYQbSKQUa2s6k7ZiQCUs3/oobFxrj1k9w599YYBaKnuQmp+fcm957gohRpR3ny8osLa+srmXXcxubW9s79u5eQ4WxxKSOQxbKVoAUYVSQuqaakVYkCeIBI81gdDX1m/dEKhqKOz2OiM/RQNA+xUgbqWsf3hRg4g0Q56hThkGnPDlNCu6JJ4dh0TyKXTvvlJwZ4F/ipiQPUtS69qfXC3HMidCYIaXarhNpP0FSU8zIJOfFikQIj9CAtA0ViBPlJ7NDJvDYKD3YD6UpoeFM/TmRIK7UmAemkyM9VIveVPzPa8e6f+EnVESxJgLPP+rHDOoQTlOBPSoJ1mxsCMKSml0hHiKJsDbZ5UwI7uLJf0mjXHLPSpXbSr56mcaRBQfgCBSAC85BFVyDGqgDDB7AE3gBr9aj9Wy9We/z1oyVzuyDX7A+vgFlMJeu</latexit>

Center of Machine Learning Research<latexit sha1_base64="4rvx14CDHpwGHb9DzzjKXw5+Qso=">AAAB9HicbVBNS8NAEJ3Ur1q/qh69BItQQUoiRT0WvXisYD+gCWWznbRLN5u4uymU0t/hxYMiXv0x3vw3btsctPXBwOO9GWbmBQlnSjvOt5VbW9/Y3MpvF3Z29/YPiodHTRWnkmKDxjyW7YAo5ExgQzPNsZ1IJFHAsRUM72Z+a4RSsVg86nGCfkT6goWMEm0k3wtQE4+JsnPhnneLJafizGGvEjcjJchQ7xa/vF5M0wiFppwo1XGdRPsTIjWjHKcFL1WYEDokfewYKkiEyp/Mj57aZ0bp2WEsTQltz9XfExMSKTWOAtMZET1Qy95M/M/rpDq88SdMJKlGQReLwpTbOrZnCdg9JpFqPjaEUMnMrTYdEEmoNjkVTAju8surpHlZca8q1YdqqXabxZGHEziFMrhwDTW4hzo0gMITPMMrvFkj68V6tz4WrTkrmzmGP7A+fwApBJEO</latexit>

2 (0, 1)

< 29 >

DmSGD incurs severe inconsistency bias: verification•

Full-batch linear regression•

DmSGD is faster but suffers moreinconsistency bias (as expected)

Center of Machine Learning Research< 30 >

A brief summary• Inconsistency bias dominates large-batch setting• Momentum amplifies inconsistency bias in DmSGD especially whenn

1 X (k)
lim
kxi
k!1 n
i=1
<latexit sha1_base64="oCfEhA8HRIvZyF4VTE1W4vh5eKw=">AAACdHicbVFNbxMxEPUuXyV8NIUDBzgYokrJodFuVAGXSlW5cKNIpK0UZ1dex5tYsb0re7Zq5PoX8O+48TO4cMab7gFaRrL09N48zfhNUUthIUl+RvG9+w8ePtp53Hvy9Nnz3f7eizNbNYbxKatkZS4KarkUmk9BgOQXteFUFZKfF+tPrX5+yY0Vlf4Gm5rPFV1qUQpGIVB5/zuRQuVuTaDCROgSNh6T0lDmUu+0J7YJqjhKfaYxub7KReaG65HHB/gqIxaoIdfZBB/hL+RELIedlSypUjTwRTbxzpHtms7whR+mB6TgQEdBaLFZVS3ErXuU9wfJONkWvgvSDgxQV6d5/wdZVKxRXAOT1NpZmtQwd9SAYJL7Hmksrylb0yWfBaip4nbuttt4vB+YBS4rE54GvGX/djiqrN2oInQqCit7W2vJ/2mzBsqPcyd03QDX7GZQ2UgcEm4vgBfCcAZyEwBlRoRdMVvRkBuEO/VCCOntL98FZ5Nx+n58+PVwcHzSxbGDXqN3aIhS9AEdo8/oFE0RQ7+iVxGO3ka/4zfxIN6/aY2jzvMS/VPx+A/m57yu</latexit>? 2

x k =O

⇣

2 2

(1

b
)2 (1

⇢)2

<latexit sha1_base64="AYBaXPIKdSckFE8+KBHbsyIVsQk=">AAACH3icbVBNS8NAEN3Urxq/qh69LBbBU0mkqMeiF48V7AckoWy2m3bpJht2J0oJ/RleFX+NN/HaX6PbNgfb+mDg8WaGmffCVHANjjO1ShubW9s75V17b//g8KhyfNLWMlOUtagUUnVDopngCWsBB8G6qWIkDgXrhKP7Wb/zzJTmMnmCccqCmAwSHnFKwEieHzIg2AeJ3V6l6tScOfA6cQtSRQWavcqP35c0i1kCVBCtPddJIciJAk4Fm9h+pllK6IgMmGdoQmKmg3z+8gRfGKWPI6lMJYDn6t+NnMRaj+PQTMYEhnq1NxP/63kZRLdBzpM0A5bQxaEoE9hYnPnHfa4YBTE2hFDFza+YDokiFExK9tKZUMoRkFAvWcnjTABX8mVim8Tc1XzWSfuq5l7X6o/1auOuyK6MztA5ukQuukEN9ICaqIUokugVvaF368P6tL6s78VoySp2TtESrOkvWaWjdw==</latexit>!1⌘• This explains why DmSGD gets poor performance in large-batch setting
Center of Machine Learning Research< 31 >

PART 03
DecentLaM: Remove Momentum-Incurred Bias

DmSGD incurs severe inconsistency bias

<latexit sha1_base64="qEMoBe1SVNstTWCeTYMHXirO2Yw=">AAADH3ichVJbaxNBFJ5db228NNVHXw4GS0ptyEq9vAilBvRJKpq2kInL7GSSTjIzG+eiCcP+E1/8K774oIj41n/jbLKIaQUPDHyc6/edOdlUcGPb7bMovnT5ytVra+u16zdu3tqob94+MrnTlHVpLnJ9khHDBFesa7kV7GSqGZGZYMfZ5HkZP/7AtOG5emvnU9aXZKT4kFNigyvdjB7NUv7ONyc7yXYBW88AOzVgOtOEMo+Nk6kfY64AS2JPKRH+VZHyAj6mno8LwAd81IRZOi47hPpdwCMiJQGsSCYIDNNx8090e5G+XaQeawmdNy86oYHKlZMZ04BxbX0Lv3dkADurJDJmSTXJ44VinwnHior4cuz/mFYsdoPKYoWHzCVT1sniAQY8zDURAnjZp6f6LVgSKg3LLJ/5ZkcG3qG23mi32guDiyCpQANVdpjWf+FBTl05iwpiTC9pT23fE205FayoYWfYlNAJGbFegIpIZvp+obaA+8EzgEAuPGVh4f27whNpzFxmIbMUb87HSue/Yj1nh0/7nqups0zR5aChE2BzKI8FBlwzasU8AEI1D1yBnpLwLTacVC0sITkv+SI4ethKHrf2Xu819g+qdayhu+geaqIEPUH76CU6RF1Eo0/Rl+hb9D3+HH+Nf8Q/l6lxVNXcQSsWn/0GeIP7oA==</latexit>

(k+1)
xi
=

X

(k)
wij xj

j2Ni

|

+
|

⇣

⇣

(k)
rfj (xj )

{z

DSGD
(k)
xi

X

(k 1)
wij xj

j2Ni

{z

(k)

⌘

}

, 8i 2 [n].

(DmSGD)}

momentum<latexit sha1_base64="OYuL7pZJjhQdNmohOHZ6YRxUG78=">AAACJnicbVDLSgMxFM3UV62vUZduglXQhWWmiLoRim5cSQX7gE4dMmlq02YyY5LRlmG+xo2/4sZFRcSdn2Km7UJbDwQO55xL7j1eyKhUlvVlZObmFxaXssu5ldW19Q1zc6sqg0hgUsEBC0TdQ5IwyklFUcVIPRQE+R4jNa93mfq1RyIkDfitGoSk6aN7TtsUI6Ul1zzf67v0Lj7oHSbQ4eQBOjLy3bjrUA4dH6kORiy+TlyawCc3pt0E9t1umj+yD5M918xbBWsEOEvsCcmDCcquOXRaAY58whVmSMqGbYWqGSOhKGYkyTmRJCHCPXRPGppy5BPZjEdnJnBfKy3YDoR+XMGR+nsiRr6UA9/TyXRzOe2l4n9eI1Lts2ZMeRgpwvH4o3bEoApg2hlsUUGwYgNNEBZU7wpxBwmElW42p0uwp0+eJdViwT4pHN8U86WLSR1ZsAN2wQGwwSkogStQBhWAwTN4BUPwbrwYb8aH8TmOZozJzDb4A+P7B3slpSk=</latexit>

⌘

P

(k 1)

•

Momentum will not vanish as xi•

Compared to DSGD, momentum will incur additional inconsistency bias

Center of Machine Learning Research

6=

j2Ni wij xj

as k ! 1<latexit sha1_base64="XPVLJ0TT/R5Iw7TBNXSPkF287WA=">AAAB83icbVBNS8NAEJ3Ur1q/qh69LBbBU0lE1GPRi8cK9gOaUDbbTbt0swm7EyGU/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTKUw6LrfTmltfWNzq7xd2dnd2z+oHh61TZJpxlsskYnuhtRwKRRvoUDJu6nmNA4l74Tju5nfeeLaiEQ9Yp7yIKZDJSLBKFrJHxMfE+ILFWHer9bcujsHWSVeQWpQoNmvfvmDhGUxV8gkNabnuSkGE6pRMMmnFT8zPKVsTIe8Z6miMTfBZH7zlJxZZUCiRNtSSObq74kJjY3J49B2xhRHZtmbif95vQyjm2AiVJohV2yxKMoksX/OAiADoTlDmVtCmRb2VsJGVFOGNqaKDcFbfnmVtC/q3lX98uGy1rgt4ijDCZzCOXhwDQ24hya0gEEKz/AKb07mvDjvzseiteQUM8fwB87nD5oxkWs=</latexit>< 33 >

Remove momentum-incurred bias•

We modify the momentum term a little bit<latexit sha1_base64="8rHwoFpgmXbsvgAYkLG3iAOSIWM=">AAADAXicbVLLbhMxFPUMrza8UliwYGNRUSUqjTKoAjZIVYkEC0BFkLZSHEa246RObM/gBySyhg2/woYFCLHlL9jxN3gmI0RajmTp6D7Pvb4kF9zYbvd3FJ87f+HipbX1xuUrV69db27cODSZ05T1aSYyfUywYYIr1rfcCnaca4YlEeyIzJ6U/qP3TBueqTd2kbOhxBPFx5xiG0zpRnRrnvK3vjXbTtoF3HoMkVMjponGlHlknEz9FHEFkcT2hGLhXxYpL+CH1PNpAdE+n7TgPJ2WFUL+DkQTLCWGSGEiMByn09Zfb7sKbxepR1rC3uunvVDgncMjWAJJks19q8coU/Y5ftEukMqUk4RpiFBjfWsZur0qkDCLaxUeVdvwRDhW1ENVkmq+EwYsViTITIZeThb3EETjTGMhIC+HHahhJ21udjvdCvAsSWqyCWocpM1faJRRV5akAhszSLq5HXqsLaeCFQ3kDMsxneEJGwSqsGRm6CvNBbwbLCMYNISnLKys/2Z4LI1ZSBIiy48wp32l8X++gbPjR0PPVe4sU3TZaOwEtBkszwGOuGbUikUgmGoetEJ6gsNybTiaRlhCcnrks+Twfid50Nl9tbu5t1+vYw3cBndACyTgIdgDz8AB6AMafYw+R1+jb/Gn+Ev8Pf6xDI2jOucmWEH88w8Eiu8n</latexit>

(k+1)
xi
=

X

(k)
wij xj

j2Ni

|

+
|

⇣

⇣

(k)
rfj (xj )

{z

DSGD
(k)
xi

(k 1)
xi

{z

momentum⌘⌘(DecentLaM)}, 8i 2 [n].
}<latexit sha1_base64="w1iexLJgTKHWgBlMmkjFT/e1xDE=">AAACBnicbVDLSgMxFL1TX7W+Rl2KECxCXbTMSFGXRTcuK9gHtOOQSTNtaOZBkhHL0JUbf8WNC0Xc+g3u/BvTdhbaeiBwcs69JOd4MWdSWda3kVtaXlldy68XNja3tnfM3b2mjBJBaINEPBJtD0vKWUgbiilO27GgOPA4bXnDq4nfuqdCsii8VaOYOgHuh8xnBCstuebhg8vu0tLwZIzKKONlW9+6KkKWaxatijUFWiR2RoqQoe6aX91eRJKAhopwLGXHtmLlpFgoRjgdF7qJpDEmQ9ynHU1DHFDppNMYY3SslR7yI6FPqNBU/b2R4kDKUeDpyQCrgZz3JuJ/XidR/oWTsjBOFA3J7CE/4UhHnHSCekxQovhIE0wE039FZIAFJko3V9Al2PORF0nztGKfVao31WLtMqsjDwdwBCWw4RxqcA11aACBR3iGV3gznowX4934mI3mjGxnH/7A+PwBEhSW9A==</latexit>

§

(k)
xi

(k 1)
xi
! 0 as k ! 1<latexit sha1_base64="XPVLJ0TT/R5Iw7TBNXSPkF287WA=">AAAB83icbVBNS8NAEJ3Ur1q/qh69LBbBU0lE1GPRi8cK9gOaUDbbTbt0swm7EyGU/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTKUw6LrfTmltfWNzq7xd2dnd2z+oHh61TZJpxlsskYnuhtRwKRRvoUDJu6nmNA4l74Tju5nfeeLaiEQ9Yp7yIKZDJSLBKFrJHxMfE+ILFWHer9bcujsHWSVeQWpQoNmvfvmDhGUxV8gkNabnuSkGE6pRMMmnFT8zPKVsTIe8Z6miMTfBZH7zlJxZZUCiRNtSSObq74kJjY3J49B2xhRHZtmbif95vQyjm2AiVJohV2yxKMoksX/OAiADoTlDmVtCmRb2VsJGVFOGNqaKDcFbfnmVtC/q3lX98uGy1rgt4ijDCZzCOXhwDQ24hya0gEEKz/AKb07mvDjvzseiteQUM8fwB87nD5oxkWs=</latexit>§ Momentum-incurred bias will vanish as k ! 1<latexit sha1_base64="XPVLJ0TT/R5Iw7TBNXSPkF287WA=">AAAB83icbVBNS8NAEJ3Ur1q/qh69LBbBU0lE1GPRi8cK9gOaUDbbTbt0swm7EyGU/g0vHhTx6p/x5r9x2+agrQ8GHu/NMDMvTKUw6LrfTmltfWNzq7xd2dnd2z+oHh61TZJpxlsskYnuhtRwKRRvoUDJu6nmNA4l74Tju5nfeeLaiEQ9Yp7yIKZDJSLBKFrJHxMfE+ILFWHer9bcujsHWSVeQWpQoNmvfvmDhGUxV8gkNabnuSkGE6pRMMmnFT8zPKVsTIe8Z6miMTfBZH7zlJxZZUCiRNtSSObq74kJjY3J49B2xhRHZtmbif95vQyjm2AiVJohV2yxKMoksX/OAiADoTlDmVtCmRb2VsJGVFOGNqaKDcFbfnmVtC/q3lX98uGy1rgt4ijDCZzCOXhwDQ24hya0gEEKz/AKb07mvDjvzseiteQUM8fwB87nD5oxkWs=</latexit>

Center of Machine Learning Research< 34 >

Remove momentum-incurred bias

<latexit sha1_base64="qDbsJqbn5Q9ngqkKzSMEJt2cXAg=">AAAC2HicbVJdixMxFM2MX9v6VfXRl4tFaIUOnSIqwsKyK+KDYkW7u9i0JZNmpqGZZEgy2pId8EERX/1pvvkr/AtmuhV01wuBwzkn3NxzkxSCG9vv/wzCCxcvXb6y02hevXb9xs3WrduHRpWashFVQunjhBgmuGQjy61gx4VmJE8EO0qWB7V+9IFpw5V8Z9cFm+QkkzzllFhPzVq/sFRczpm0gC1b2SR1Q60KZXitRxU8L4XoJcTSBTxj1PteklfQeRsdRECVsV1YEANEApdUSeMfzCRdQ8Jr1kCqhFAfzdNmo4ETlnHpiOCZfFDVhOD5zC2xVYC5TO26AmxKT/HduJpKwCerGZ+6zrJbQQ9WU2ws0fhkOoBdeI33edbBqSbU4YzkOfF0Mh1UrhP3sF6orse1p1s3YnL+p++s1e5H/U3BeRBvQRttazhr/cBzRcvcT04FMWYc9ws7cURbTgWrmrg0rCB0STI29lCSnJmJ2yymgvuemfsQtD8+4Q379w1HcmPWeeKdObELc1aryf9p49KmTyaOy6Ks8z5tlJYCfJb1lmHONaNWrD0gVPtdUqAL4tOy/i80fQjx2ZHPg8NBFD+KHr4ZtPf2t3HsoLvoHuqgGD1Ge+gFGqIRosEocMHn4Ev4PvwUfg2/nVrDYHvnDvqnwu+/ATo54LY=</latexit>

Proposition. Full-batch DecentLaM (S.C. cost) has an inconsistency bias asfollows:⇣ 2 b⌘2 ⌘
n 1 X
⇣
2 2
(k)
X
(k)kxi ? 2x? k2 = O blim2
limk!1 nkxi
x k =O
(1
⇢)
2
i=1
k!1
(1 ⇢)
i=1
<latexit sha1_base64="oEhqYiAkghqhOWp3kpxAJJr8lgI=">AAACW3icbVFNa9swGJbdbs2ybs02dtpFNAySQ4MdSttLobSX3dZB0xai2LxW5EREko0klwbVf3Kn9bC/MiYnOWxtXxA8PB+80qOsFNzYKHoMwq3tV693Wm/ab3ffvd/rfPh4bYpKUzaihSj0bQaGCa7YyHIr2G2pGchMsJtscdHoN3dMG16oK7ss2UTCTPGcU7CeSjuaCC5TtyC2wISr3C5rTHIN1MW1UzUxlVf5aVwnCpOH+5Qnrrfo1/gA3yfEWNDkIRniU/ydnPNZb50kM5ASPJ0lw9r14gOi50Xf48bTb6edbjSIVoOfg3gDumgzl2nnJ5kWtJJMWSrAmHEclXbiQFtOBavbpDKsBLqAGRt7qEAyM3Grbmr81TNTnBfaH2Xxiv034UAas5SZd0qwc/NUa8iXtHFl85OJ46qsLFN0vSivBPZFNkXjKdeMWrH0AKjm/q6YzsH3Y/13NCXET5/8HFwPB/HR4PDHYffsfFNHC31B+6iHYnSMztA3dIlGiKJf6E+wE7SC3+FW2A5319Yw2GQ+of8m/PwXI9ezoA==</latexit>n

2 2<latexit sha1_base64="JUmKCDNcuZZ7VEenZ6JKeQu4T0M=">AAACIXicbZDLSgMxFIYzXmu9VV26CRahXVhmStEui27cWcFeoNOWM2mmDSYzQ5IRytBXceOruHGhSHfiy5hpu9DWHwIf/zmHk/N7EWdK2/aXtba+sbm1ndnJ7u7tHxzmjo6bKowloQ0S8lC2PVCUs4A2NNOctiNJQXictrzHm7TeeqJSsTB40OOIdgUMA+YzAtpY/Vz1zvXYsIBdXwJJ3CEIAb0y9nrlSVJwLlyPaij2yinKUWhogtOBIu7n8nbJngmvgrOAPFqo3s9N3UFIYkEDTTgo1XHsSHcTkJoRTidZN1Y0AvIIQ9oxGICgqpvMLpzgc+MMsB9K8wKNZ+7viQSEUmPhmU4BeqSWa6n5X60Ta7/aTVgQxZoGZL7IjznWIU7jwgMmKdF8bACIZOavmIzAZKVNqFkTgrN88io0yyXnslS5r+Rr14s4MugUnaECctAVqqFbVEcNRNAzekXv6MN6sd6sT2s6b12zFjMn6I+s7x8pvaEE</latexit>

b
)2 (1

•

Recall that full-batch DmSGD has limiting bias as O•

DecentLaM removes the momentum-incurred bias•

With smaller inconsist. bias, DecentLaM is expected to outperform DmSGD in large-batch scenario

Center of Machine Learning Research

(1

⇢)2

< 35 >

Remove momentum-incurred bias: verification•

Full-batch linear regression•

DecentLaM is as fast as DmSGD,
and as accurate as DSGD

Center of Machine Learning Research< 36 >

However, DmSGD performs badly in large-batch scenario•

Experimental setting: CIFAR-10; ResNet-20•

Large-batch: 8K total batch-size per iteration

DmSGD drops 1% performance compared to PmSGD with large-batch
Center of Machine Learning Research< 37 >

Go back to large-batch Cifar-10 experiment•

Experimental setting: CIFAR-10; ResNet-20•

Large-batch: 8K total batch-size per iteration

DecentLaM is much better than DmSGD, and is even better than PmSGD
Center of Machine Learning Research< 38 >

Formal convergence in the non-convex scenario<latexit sha1_base64="ZAhLL3eLFT+8h/c077lWRg4qTuU=">AAADPnicbVJLb9QwEE7Cq5RXC0cuIxqk7qGrzVIeAiG1PCQOHIrUB1KzXU2cya5Vx45sp+oqzS/jwm/gxpELBxDiyhE7XSRoGcnS53l84/nGWSW4sYPB5zC6cPHS5SsLVxevXb9x89bS8u1do2rNaIcpofT7DA0JLmnHcivofaUJy0zQXnb40sf3jkgbruS2nVU0KnEiecEZWucaL4fbqVRc5iQtpJaObVY0m8bUZeXj/RZWN/tJD14jm0JcjPnqcS8GbiB+G6+ZUik7feZThj3YnhJMNObcUzlOQz6vlhl3z8sBZQ5TNJCp2nXL4Qg1R8moK3/Qg3iv462U4ZYfEeRUcMktdYW5qjMxWzNWMcdhOeuq1nvwCi3ClCxpNSFJ3M48ybzHU4jTQiNrkraRbeqGGjf8edIeSEhPUomZQDgdCdbgz93d0pODIaSCoMnag2HsWz3swRZqLH0nx5qRxRgYSqksZARWKWBCGY8gTuLx0sqgP+gMzoNkDlaCuW2Nlz6luWJ16bRjAo3ZTwaVHTWo3ayC2sW0NlQhO8QJ7Tso3UvMqOnW38L92gtcKO2O077z/l3RYGnMrMxcZol2as7GvPN/sf3aFk9GDZdVbUmy00ZFLfyQ/i9BzjUxK2YOINNubwzcfpziTiWz6ERIzo58HuwO+8mj/vq74crGi7kcC8Hd4F6wGiTB42AjeBNsBTsBCz+EX8Jv4ffoY/Q1+hH9PE2NwnnNneAfi379BgSuAmw=</latexit>

Assumption. (A.1) Each fi (x) is L-smooth; (A.2) The gradient noise is unbiased and has bounded variance; (A.3) W is positive
definite and doublyPnstochastic; (A.4) Data heterogeneity is bounded: n1 i=1 krfi (x) rf (x)k2 
b2 (A.5) Parameter cannot be too close to 1

<latexit sha1_base64="y9MpkMr8LEOtg6SP1zi4u0hTILE=">AAAEw3icdVPJbtswEFVit03cLWmPvRDNArmpDcvodgkQpA3QQ4ukgLMAoW2QNCURJimBpNoEDH+yt/xNKVlZmjgEBAxm3puZN5rBOWfa9HqXC4uN5qPHT5aWW0+fPX/xcmX11ZHOCkXoIcl4pk4w0pQzSQ8NM5ye5IoigTk9xtOvZfz4N1WaZXJgznM6FCiRLGYEGe8ary5eQpkxOaHSAGjomcGxHaQ0U1R0HThmJgUoz1WWK4YMBSST2iCP5RQpyWQCVOlehwkSAq2DUFMKTEpBjnKq2u/BN0p86h/oJ/jDOC/5vpuEAmRAa3kZYpowaRFniXznIEeYcju5onRKdEcS55GbAMYKERs5O3BQF2Jsp9s9N7KDTuRgqnNEqO30uh+FcFAgk2Js9xy8uGbJmsW2IzeSAEqEOQLxmIUQI2XPfKpw2nZteDHqAwChr7m9CfbhLktCAAs/IYVVWaTO2PG9G+TsTDkYODe2UIlKYdKF1Vwc2JpDrRlQs0SgUd+3FtbZ2hWhAoEZatS/gXmQSrOrOtpkvgpmSM+vcp0AWOxKejjjt71dp2Cy/J1+x7qzPKXWtp9MJguBqfIT2ACQ7IdzFYeDrciPa+sGMPO7a2DtvZHp0bfylc08rLLtRT0EBjBF5r6qdrlQVE6u1mm8stbr9qoH7htRbawF9TsYr/yFk4wUwm8f4Ujr06iXm6FFyjDCqWvBQlO/Z1OU0FNvSiSoHtrqBh3Y8J4JiDPlP38flfc2wyKh9bnAHlmup74bK53zYqeFib8MLZN5Yai/hapQXHBgMlAeNJgwRYnh595ARDHfKyAp8kMz/uxbfgjRXcn3jaN+N/rU/fCrv7azW49jKXgTvA3CIAo+BzvB9+AgOAxIY6cRN7JG3txrTpuqaWbQxYWa8zr47zXdPz6XkH8=</latexit>

Theorem. With appropriate constant learning rate
LaM will converge at(see the paper), Decent-T 1
n
1 X 1XEk
rfi (x̄(k) )k2
T
n i=1
k=0
⇣ 1
⌘
2
2 2
2 2
b
=O
+
+
+
T
n(1
) 1 ⇢
(1 ⇢)2| {z }|{z}| {z }
convg. rate

Center of Machine Learning Researchsto. bias

removed momentumincurred bias

inconsist.bias< 39 >

DecentLaM suffers smallest inconsistency bias

<latexit sha1_base64="FnYIfqYYImTf8jjeael+6nPJGCk=">AAAHyHicvVXbTttAEDW0JCS9QfvYl1UJKKjF2BbQ9o1LpKCIqwIElA3R2tkEi/WuZa+BaOWXfl1/oX/Qz+g6cdw4kBIqtSNFmZ3ZmTlzxh6bLrF9rmk/pqafPZ/JZGdz+RcvX71+Mzf/9sxngWfhU4sR5p2byMfEpviU25zgc9fDyDEJrpnXO5G/doM932b0hHdd3HBQh9pt20JcmprzM9+hiTs2FRzJkLB+1cjnctDClGPPpp3okPgDgrxQeJYVSnMOcuZ6AcE93QkItyWawKFCDwUJRQiWAOT4jpttUeUeox3SXbEYvcF3w64DRhPreIEQQMduDcqVnGq5VC/vGlojfW8JHKhb6h8STSJLoHAITbtThG0PWQJ2kOOgSwPsXxqhKOorkhCOluUhurRcAPDGd5GFhaauO04I4W+E1VK5lMb4cG6xvmqEo/k3Bvn/Szdrj3YzUVZzDEf9yUwEOA0gtvVhbK30eb2oXOhfU6P/p4MXZvjI6PWEqq3aTgxyu3LyMRn+U5+pJ+F7bJQxukUJr0rY7T6DbcY4ZRyLeg3RDsBcRUT9BAxN0hoOFxw3tIEnKTH0tByXYwb2jqoVQ29Mlq8gYG+bCZMEOBSHxTT9y2FYGK6XVEuFDbZKCUcbbA/tg+Jh4PkyeKRYKshkpOV3Hfk3XNaMiv7F2zfaypj0w12Nl2jxmYxz5sS7D2LaSnZxPjnK1d2cW9BUrSfgvqLHyoISy1Fz7idsMStwJFMWQb5f1zWXNwTy5CaX+fIw8LEk+xp1cF2qFDnYb4heZyFYlJYWaDNP/igHPetwhECOHzUtbzqIX/mjvsj4kK8e8PaXhrCpG3BMrX6hdkAAZyD6foGW7WGLk65UkOXZEiuwrpB8H+QHy8+nypiMXUtu/IgafZSI+8qZoeob6tqxsbC5HZM0q7xXPihFRVc+K5vKrnKknCpWZjVzmrnMNLOVrJu9zXb7V6en4ph3Skqy334BKd8ZbA==</latexit>

Strongly-convex
DmSGD[GH20]

N.A.

DmSGD[SDGD20]

O

DmSGD

O

DA-DmSGD[YJY19]
AWC-DmSGD[BJT+20]
QG-DmSGD[LPSJ21]
DecentLaM (Ours)

O

5/2

M2
(1
)6
2 2
b
(1
)2

Non-convex
O
O

2

M2
(1
)2
2
M2
(1
)4

N.A
2 2

N.A.

O (1 b )2

2

2

M2
(1
)2

N.A
O( 2 b2 )

O

M2
(1
)4
2 2

O( b )O( 2 b2 )Note: quantity M is typically far larger than bCenter of Machine Learning Research< 40 >

Experiments in deep training (image classification)

ImageNet-1K dataset
1.3M training images
50K test images
1K classes
DNN model: ResNet-50 (25.5M parameters)
GPU: Up to 64 Tesla V100 GPUs

• Batch-size: we will test batch-sizes 2K, 16K, and 32K• Baseline: PmSGD, PmSGD + LARS (layer-wise learning rate), DmSGD

Center of Machine Learning Research< 41 >

Experiments with batch-size 2K (test accuracy)•

Sto. bias dominates in 2K batch-size•

DecentLaM performs similarly to DmSGD(as expected)

Center of Machine Learning Research< 42 >

Experiments with batch-size 32K (test accuracy)•

Inconst. bias dominates in 32K batch-size•

DecentLaM outperforms DmSGD
significantly (as expected)•

DecentLaM even outperforms PmSGD
with LARS

Center of Machine Learning Research< 44 >

Comparison with more baselines<latexit sha1_base64="U6YLFjmI5o2lSA449yyHGsmUQiY=">AAAF8XicdVRbb9MwFA6shbXcBjzyYthFXNQql162NwZI8LDBxhhDWsrkuO5q1YmD7WwaUX4Ib4hXfhH8GTiJ02bdwFJyfG7fZ5+ckyDmTGnb/nXl6kKtfu36YqN54+at23eW7t77qEQiCd0nggv5KcCKchbRfc00p59iSXEYcHoQTF7m/oMTKhUT0Qd9FtNBiI8jNmIEazAd3V347Qf0mEWpxpCSHeqHg2aj4Z+oCYuR3Xa6LMp1E0NopKnMwDC1qBBzXhgaq8g3fhYdF4YKOOFYZinJl4lt+FrEMuG01MKEaybFaepm6dMsDakei2GG1pDxwDWTMEo7gJGlL7AmY7THvtIMId83CGvInSBYa2i9kGbv9Cbw9ozL99GUjQ0r7p1w7/UriOr32p5rpL1upNvPZTeX59KLhGdbm+/3TJTTM1EbXaP3ukbvebPTvao4DCZwOKXu5bLT3uhX0ZutcwleDreS+sWnTgOe0Cwn3chWSjrX0HWdGcDmwcvzCO5GecBeiegY3aso97g43Ral2zbuTnn7rleGV/fZfT2H783j90qA9V51pZXP7kqVA+CdEtSeLyLYZzk0b6ctvI0ev0ukevKvMnS8ogz/K88le/8/8a4L9imxHwitRThrEZ9Gw1kXN6eGWecXWjUZqz7BcT5b6QcRtxx0gjkbFsOGMCGJxOQMnY5phLTELIJZQe+pekt1q2ujU6bHaMhGIyoBDwVFpyvodNUumDgOKDeT2mIwyDSCPEkViK7dwsV0TU8Lw3y0tGy37WKhyxun3Cxb5do5WvrjDwVJQiAnHCt16NixHqRYwggCXtNPFI0xmQDzIWwjHFI1SItSZmgVLEM0EhIeOHxhPZ+R4lCpszCAyBDrsbroy43/8h0merQ+SFkUJ5pGxBCNEo60QPkfDQomKdH8DDaYSAZnRWSModDwRVRzjiYQYgK1UXNXSad/n6wJFXMu1ufy5qML/dru7LrLz1+UtVu0HliPrMeWY/Wt59Yba8fat0hts3Zci2tf6qr+rf69/sOEXr1S5ty35lb951+0waTV</latexit>

methodPmSGDPmSGD+LARS
DmSGD
DA-DmSGD
AWC-DmSGD
SlowMoQG-DmSGD
D2 -DmSGD
DecentLaM (Ours)

Center of Machine Learning Research

2k

Batch Size
8k
16k

32k

76.32
76.16
76.27
76.35
76.29
76.30
76.23
75.44
76.43

76.08
75.95
76.01
76.19
75.96
75.47
75.96
75.30
76.19

75.27
75.63
74.97
75.51
75.37
75.33
75.86
75.44
76.22

76.27
76.65
76.23
76.62
76.31
75.53
76.60
76.16
76.73

Outperforms all otherbaselines significantly
for large-batch settings< 45 >

Experiments in deep training (Object detection)

PASCAL/COCO dataset<latexit sha1_base64="iRhmu2YfaQRWWAOgY+jk6PIoW5w=">AAAFM3icbVRLb9QwEE67C5TwauEIB0O7CAltlGzZbrm17Ao49EVLH1KzqhzH27XWjqPYaVVFOfFruIL4MYgb4spvgHGSPrZbS5HHM998tr8ZJ4g5U9p1f05N1+q3bt+ZuWvfu//g4aPZucd7SqYJobtEcpkcBFhRziK6q5nm9CBOKBYBp/vBqGvi+yc0UUxGn/VZTPsCH0dswAjW4Dqaqz3zA3rMokxjSMkP9fO+7Z+oEYuR63htFtlVnNBI0yQ/XyqBOb9ckdxuIL/EsOjYviRNOU7yjJgBcC3jJOXURjB6WMPBNXqJfJFyzeAyqYiyFqDzbGt1p7u6hvY2u/nNgO5mdzNHvl9QrcuQcsBtNzcKwvfN7e7GxqQD4LYvWFicobEldj70INh567gwLbvOIkyLS06rnNrA7PuoAr5eW93eMehlCBRJywbWdjrnScDeu6T0Ssp2GfXK6Y1htBu91WZvYvP2OQSmDjgNHTWSruF1BM4FX2A9DAYZpCzmC1c9kN0Z9wDR0jVPx/HAU0gQSK2lKFTwaRRe1KlcmWqWRlVkY1/Uv2yOJnQHNEfDJzg2nZR1pYhxwkyjITlAeCATKiAH1jREguqhDBU6ZXqIQjYY0ARiSJi6KQQpl/VGOAqRqS4KywZRTlVGE6gKmVBgQFqibapZhC+iWMEhzyEqpkSzE8rPHDg3xwHlZZs3Q6pNSEZNgeOrd2qZhq8UgedwNDvvOm4x0KThVca8VY2to9l/fihJai5OOFbq0HNj3c9wAt0LfLafKhpjMsLH9BDMCAuq+lnxjHPUAE+IQDj4QJzCezUjw0KpMxEA0tRUXY8Z502xw1QPlvsZi+JU04iUGw1SbvQz/wQoSAJy8DMwMEkYnBWRIU4wATGVPbZNIOUItFFjV8mK55nI09wGxbzr+kwaey3Hg07/1JpfeVdpN2M9tV5YryzP6lgr1kdry9q1SO1L7WvtW+17/Uf9V/13/U8JnZ6qcp5YY6P+9z9E+Zm9</latexit>

DatasetModel
DmSGD
DecentLaM

Center of Machine Learning Research

PASCAL VOC
R-Net F-RCNN

COCO
R-Net F-RCNN

79.1
79.3

36.1
36.6

80.5
80.7

36.4
37.1

< 46 >

PART 04
BlueFog: An open-source and high-performance python libraryhttps://github.com/Bluefog-Lib/bluefog

BlueFog• An open-source library to support decentralized communication in optimization and deep learning• High-performance• Easy-to-use

Center of Machine Learning Research< 48 >

High-performance• BlueFog has larger throughput than Horovod (the SOTA DL system implementing PSGD) [YYH+21]• All our research progresses are involved in BlueFog[YYH+21] B. Ying, K. Yuan, H. Hu, Y. Chen, and W. Yin, ``BlueFog: Make Decentralized Algorithms Practical for Optimization and machine learning”,
arXiv:2111.04287 [GitHub site: github.com/Bluefog-Lib/bluefog]
Center of Machine Learning Research< 49 >

Easy-to-use• Writing codes for decentralized methods is as easy as writing equations

Decentralized least-square algorithms<latexit sha1_base64="7Al5dgSsezZ5Rd7v5b5bWC9Sxys=">AAAFu3icbdTNb9MwFABwd1thlI1tcORiMYE6AVULCLhMGnDhhEa1L6kpkeM6rVvHyWKnXWb5D+XA/0L6IfTah6VEL+/nZ1svkqNMSWPb7d+1re2d+oOHu48aj/f2nxwcHj29MmmRc3HJU5XmNxEzQkktLq20StxkuWBJpMR1NPk29+upyI1M9YUtM9FP2FDLWHJmq1R4OCtD+cs1Jyeevjqld/8+3tJgyJKE0S9V6qJZvdcwCuUJDYLGKve6s6wPTJGEbhxITYOE2RFnyv3wofR0Fjo59rQMx8s1wsPjdqu9GBQHnVVwTFbjPDzaeRMMUl4kQluumDG9TjuzfcdyK7kSvhEURmSMT9hQ9KpQs0SYvlt0yNOXVWZA4zSvHm3pIgsrHEuMKZOomjk/t9m0efJ/1its/LnvpM4KKzRfbhQXitqUzttNBzIX3KqyChjPZXVWykcsZ9xWP2VtlyhNJ5ZFxjcagRYznlbd1wMXTJl3btHNKHbMe7/BEeAIMwfMMQ8ADzALwAJzDDjGPAQ8xDwCPMIsAUvMY8BjzBPAE8wKsMKcAE4wa8Aacwo4xZwBzjDfAr7FnAPOMRvABrMFbDEXgAvMU8BTzDPAM8x3gO8wl4BLzPeA7+e87t2uX3Hkun5+v3Q2bxMcXL1rdT623v/8cHz2dXXT7JLn5AVpkg75RM7Id3JOLgknf2rbtb3afv20zuvjulpO3aqtap6RtVEv/gKF2xak</latexit>

(k)

(k)

(k)

= xi
ATi (Ai xi
X
(k+1)
(k)
xi
=
wij yj
yi

bi )

j2Ni

Center of Machine Learning Research< 50 >

Easy-to-use
Abundant documents

Center of Machine Learning Research< 51 >

Easy-to-use
Detailed tutorials

Center of Machine Learning Research< 52 >

Final summary•

DmSGD suffers significant performance degradation in large-batch settings•

Root reason: inappropriate momentum amplifies inconsistency bias•

We propose DecentLaM to completely remove the momentum-incurred bias•

Theoretical and numerical results justify the superiority of DecentLaM to DmSGD

Center of Machine Learning Research< 53 >

Thank you!
Kun Yuan homepage: https://kunyuan827.github.io/
BlueFog homepage: https://github.com/Bluefog-Lib/bluefog