Accelerating Decentralized Deep Training withSparse and Effective Topologies
Kun YuanCenter for Machine Learning Research @ Peking University

Nov. 23, 2022

Joint work with

Bicheng Ying (Google)

Yiming Chen (Alibaba)

Hanbin Hu (Google)

Wotao Yin (Alibaba)

Zhuoqing Song (Fudan U)

Kexin Jin (Princeton U)

Weijian Li (Alibaba)

Ming Yan (CUHK-SZ)

Center of Machine Learning Research<2>Preface
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? We must reduce communication overhead.
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>Methodologies to save communication• Each node sends a full model (or gradient) to the server; proportional to dimension d[Communication compression]• Each node interacts with the server at every iteration; proportional to iteration numbers[Lazy communication]• Global average incurs O(n) comm. overhead; proportional to network size n[Decentralized communication]

Center of Machine Learning Research<9>Communication compression• A basic (but not state-of-the-art) algorithm is QSGD [Alistarh et. al., 2017]

(k)

(k)

(k)

= rF (xi ; ⇠i )
n
X
(k+1)
(k)
(k)
xi
= xi
C(gj )
n j=1
gi•

C(g1 )

C(g2 )

C(g3 )C(g4 )

C(·) is a compressor. It can quantize or sparsify the full gradient
8 bit

Quantization
1 bit
Center of Machine Learning Research< 10 >

Communication compression• A basic (but not state-of-the-art) algorithm is QSGD [Alistarh et. al., 2017]

(k)

(k)

(k)

= rF (xi ; ⇠i )
n
X
(k+1)
(k)
(k)
xi
= xi
C(gj )
n j=1
gi

C(g1 )

C(g2 )

C(g3 )C(g4 )• C(·) is a compressor. It can quantize or sparsify the full gradient
8 bit

Sparsification
8 bit
Center of Machine Learning Research< 11 >

Lazy communication (Federated Average)(k+ 12 )
(k)
xi
= xi
(k+1)
xi
=

(

(k)

(k)

rF (xi ; ⇠i )(k+ 12 )xi
Pn(k+ 12 )1
j=1 xjn

if mod(k, ⌧ ) 6= 0
if mod(k, ⌧ ) = 0(Local update)(Lazy comm. )• Nodes communicate once every ⌧ iterations [Konecny et .al. 2015, 2016]• Or nodes communicate when necessary, i.e., [Chen et. al. 2018; Liu et.al., 2019]• In ProxSkip [Mishchenko et. al., 2022], lazy strategy is proved to save communication
Center of Machine Learning Research< 12 >

This talk will study distributed learning with decentralized communication< 13 >

Contents•

Decentralized SGD and topology effects•

Exponential graphs are provably efficient•

EquiTopo graphs are new state-of-the-art•

BlueFog libraries: introduction and demosPART 01
Decentralized SGD and Topology Effects

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< 16 >DSGD is more communication-efficient than PSGD•

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

Center of Machine Learning Research< 17 >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< 18 >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< 19 >

However, DSGD has slower convergence• The efficient comm. comes with a cost: slower convergence<latexit sha1_base64="nrllaBxiQkBnlfaLbWB8AQj2EyY=">AAACQnicbZDLSgMxFIYzXmu9tboSN8EiCEKZUVE3QtGNywr2Am0dMpm0TZtJhiSjLcPg07jVl/AlfAV34taFmbYL2/pD4Oc753Byfi9kVGnb/rAWFpeWV1Yza9n1jc2t7Vx+p6pEJDGpYMGErHtIEUY5qWiqGamHkqDAY6Tm9W/Seu2RSEUFv9fDkLQC1OG0TTHSBrm5vYFLH47hFWyqKIDxkxvTXgIHbi9xcwW7aI8E540zMQUwUdnNW/mmL3AUEK4xQ0o1HDvUrRhJTTEjSbYZKRIi3Ecd0jCWo4CoVjy6IYGHhviwLaR5XMMR/TsRo0CpYeCZzgDprpqtpfC/WiPS7ctWTHkYacLxeFE7YlALmAYCfSoJ1mxoDMKSmr9C3EUSYW1im9riCdHXyFPJNPV8yjvTzFfpEUk2a0J0ZiObN9WTonNePL07K5SuJ3FmwD44AEfAARegBG5BGVQABs/gBbyCN+vd+rS+rO9x64I1mdkFU7J+fgF+Nq/3</latexit>•+
Partial average xi =X

wij xj is less effective to aggregate information than global average• The average effectiveness can be evaluated by graph spectral gap:
<latexit sha1_base64="yR4hZA7oFXDauA7ttmrh/4nAUeM=">AAACjnicbVDLThsxFHUG2tL0QYAlG4uoEpXaaIZWtKpARWXDCtGIEKQ4jWyPh1jxY2R7WkXGP9OvYdvu+Bs8SSQa6JEsHZ9zr+69h5SCW5emt41kZfXJ02drz5svXr56vd7a2LywujKU9agW2lwSbJngivUcd4JdloZhSQTrk8lx7fd/MmO5VuduWrKhxFeKF5xiF6VR6wCZsYaHEF334XuICoOpz4JXAUnsxrmNn3v24xxdj/Yg4grupu+yt6NWO+2kM8DHJFuQNljgbLTR+IJyTSvJlKMCWzvI0tINPTaOU8FCE1WWlZhO8BUbRKqwZHboZ2cG+CYqOSy0iU85OFP/7fBYWjuVJFbWK9uHXi3+zxtUrvg89FyVlWOKzgcVlYBOwzozmHPDqBPTSDA1PO4K6RjHqFxMdmkK0XriMLFLl/jc1guHZhMp9otqKbHKPep2g59lS4jvhrBs0tPg5y7Fwp+G6Me0s4fZPiYXe51sv/Ph+8f20bdF7mtgG+yAXZCBT+AInIAz0AMU/AY34A/4m7SS/eQw+TovTRqLni2whOTkDrrnybI=</latexit>

1 T
11 k2 2 (0, 1) where W = [wij ] 2 Rn⇥nn<latexit sha1_base64="5t2FwX+ylDcebDnKZMKpdQKG6kA=">AAACFXicbVDLSgNBEJyNrxhfUY9eBhPBg4RdEfUiBL14jGIekF3D7KSTjM7OLjOzhrDsT3jxV7x4UMSr4M2/cfI4aGJBQ1HVTXeXH3GmtG1/W5m5+YXFpexybmV1bX0jv7lVU2EsKVRpyEPZ8IkCzgRUNdMcGpEEEvgc6v79xdCvP4BULBQ3ehCBF5CuYB1GiTZSK3/Q74EEXKyfNfuthN2lnssEdgOie76fXKe3iXA1C0BhkRZb+YJdskfAs8SZkAKaoNLKf7ntkMYBCE05Uarp2JH2EiI1oxzSnBsriAi9J11oGiqIWeQlo69SvGeUNu6E0pTQeKT+nkhIoNQg8E3n8Fw17Q3F/7xmrDunXsJEFGsQdLyoE3OsQzyMCLeZBKr5wBBCJTO3YtojklBtgsyZEJzpl2dJ7bDkHJeOrg4L5fNJHFm0g3bRPnLQCSqjS1RBVUTRI3pGr+jNerJerHfrY9yasSYz2+gPrM8fiMefEQ==</latexit>⇢ = kW

Center of Machine Learning Research

Fully-connected matrix< 20 >

However, DSGD has slower convergence• The efficient comm. comes with a cost: slower convergence<latexit sha1_base64="nrllaBxiQkBnlfaLbWB8AQj2EyY=">AAACQnicbZDLSgMxFIYzXmu9tboSN8EiCEKZUVE3QtGNywr2Am0dMpm0TZtJhiSjLcPg07jVl/AlfAV34taFmbYL2/pD4Oc753Byfi9kVGnb/rAWFpeWV1Yza9n1jc2t7Vx+p6pEJDGpYMGErHtIEUY5qWiqGamHkqDAY6Tm9W/Seu2RSEUFv9fDkLQC1OG0TTHSBrm5vYFLH47hFWyqKIDxkxvTXgIHbi9xcwW7aI8E540zMQUwUdnNW/mmL3AUEK4xQ0o1HDvUrRhJTTEjSbYZKRIi3Ecd0jCWo4CoVjy6IYGHhviwLaR5XMMR/TsRo0CpYeCZzgDprpqtpfC/WiPS7ctWTHkYacLxeFE7YlALmAYCfSoJ1mxoDMKSmr9C3EUSYW1im9riCdHXyFPJNPV8yjvTzFfpEUk2a0J0ZiObN9WTonNePL07K5SuJ3FmwD44AEfAARegBG5BGVQABs/gBbyCN+vd+rS+rO9x64I1mdkFU7J+fgF+Nq/3</latexit>•+
Partial average xi =X

wij xj is less effective to aggregate information than global average• The average effectiveness can be evaluated by graph spectral gap:
<latexit sha1_base64="yR4hZA7oFXDauA7ttmrh/4nAUeM=">AAACjnicbVDLThsxFHUG2tL0QYAlG4uoEpXaaIZWtKpARWXDCtGIEKQ4jWyPh1jxY2R7WkXGP9OvYdvu+Bs8SSQa6JEsHZ9zr+69h5SCW5emt41kZfXJ02drz5svXr56vd7a2LywujKU9agW2lwSbJngivUcd4JdloZhSQTrk8lx7fd/MmO5VuduWrKhxFeKF5xiF6VR6wCZsYaHEF334XuICoOpz4JXAUnsxrmNn3v24xxdj/Yg4grupu+yt6NWO+2kM8DHJFuQNljgbLTR+IJyTSvJlKMCWzvI0tINPTaOU8FCE1WWlZhO8BUbRKqwZHboZ2cG+CYqOSy0iU85OFP/7fBYWjuVJFbWK9uHXi3+zxtUrvg89FyVlWOKzgcVlYBOwzozmHPDqBPTSDA1PO4K6RjHqFxMdmkK0XriMLFLl/jc1guHZhMp9otqKbHKPep2g59lS4jvhrBs0tPg5y7Fwp+G6Me0s4fZPiYXe51sv/Ph+8f20bdF7mtgG+yAXZCBT+AInIAz0AMU/AY34A/4m7SS/eQw+TovTRqLni2whOTkDrrnybI=</latexit>

1 T
11 k2 2 (0, 1) where W = [wij ] 2 Rn⇥nn<latexit sha1_base64="5t2FwX+ylDcebDnKZMKpdQKG6kA=">AAACFXicbVDLSgNBEJyNrxhfUY9eBhPBg4RdEfUiBL14jGIekF3D7KSTjM7OLjOzhrDsT3jxV7x4UMSr4M2/cfI4aGJBQ1HVTXeXH3GmtG1/W5m5+YXFpexybmV1bX0jv7lVU2EsKVRpyEPZ8IkCzgRUNdMcGpEEEvgc6v79xdCvP4BULBQ3ehCBF5CuYB1GiTZSK3/Q74EEXKyfNfuthN2lnssEdgOie76fXKe3iXA1C0BhkRZb+YJdskfAs8SZkAKaoNLKf7ntkMYBCE05Uarp2JH2EiI1oxzSnBsriAi9J11oGiqIWeQlo69SvGeUNu6E0pTQeKT+nkhIoNQg8E3n8Fw17Q3F/7xmrDunXsJEFGsQdLyoE3OsQzyMCLeZBKr5wBBCJTO3YtojklBtgsyZEJzpl2dJ7bDkHJeOrg4L5fNJHFm0g3bRPnLQCSqjS1RBVUTRI3pGr+jNerJerHfrY9yasSYz2+gPrM8fiMefEQ==</latexit>⇢ = kW§ Well-connected topology has ⇢ ! 0 , e.g. fully-connected topology<latexit sha1_base64="eYtf7bylL9BvKhE9SS4TpGw+QwQ=">AAACWnicbVBNTxsxEHWWFkhSKB+99WI1QuIU7UIFiBOil56iEDWAmo2isdchVvyxsr2gyNp/wZX+r0r8mHqTHEjoSCM9vTejefNILrh1cfy3Fm18+Li5tV1vND/t7H7e2z+4tbowlPWpFtrcE7BMcMX6jjvB7nPDQBLB7sj0R6XfPTJjuVa/3CxnQwkPio85BReo36mZaJw6jePRXitux/PC70GyBC20rO5ov3aZZpoWkilHBVg7SOLcDT0Yx6lgZSMtLMuBTuGBDQJUIJkd+rnlEh8FJsNjbUIrh+fs2w0P0tqZJGFSgpvYda0i/6cNCje+GHqu8sIxRReHxoXA4cfqf5xxw6gTswCAGh68YjoBA9SFlFauEK2nDohd+cRntjJcNhqpYk9USwkq82mvV/q0MkOI75Xlqkg7pV+oFITvlEEPaSfr2b4Htyft5Kx9evO9dXW9zH0bfUXf0DFK0Dm6Qj9RF/URRQo9oxf0p/YaRVE9ai5Go9py5xCtVPTlHxKwtyM=</latexit><latexit sha1_base64="WUXWyP17hf5M87nb/60D/53RUEM=">AAACa3icbVBdaxNBFJ2sVWv8Su1TWx8GQ6E+GHartCIUin3xqdZg2kI2hjuzs82Q+VhmZpUwDP01fdXf44/wPzib5MG0XrhwOOde7rmHVIJbl6a/W8m9tfsPHq4/aj9+8vTZ887Gi3Ora0PZgGqhzSUBywRXbOC4E+yyMgwkEeyCTE8a/eI7M5Zr9dXNKjaScKV4ySm4SI07W7mZaHyEP+9lb/LSAPVZ8Orbfng97nTTXjovfBdkS9BFyzobb7Q+5IWmtWTKUQHWDrO0ciMPxnEqWGjntWUV0ClcsWGECiSzIz//IeDdyBS41Ca2cnjO/rvhQVo7kyROSnATe1tryP9pw9qV70eeq6p2TNHFobIW2GncBIILbhh1YhYBUMOjV0wnEJNwMbaVK0TrqQNiVz7xhW0Mh3Y7V+wH1VKCKnze7wefN2YI8f0QVkV6GvxCpSD8aYh6TDu7ne1dcL7fyw56b7+86x5/XOa+jnbQK7SHMnSIjtEndIYGiKJrdIN+ol+tP8lmsp28XIwmreXOJlqpZPcvggK8zQ==</latexit>§ Sparsely-connected topology has ⇢ ! 1 , e.g. ring has ⇢ = O(1<latexit sha1_base64="P1FqJ4ccUyWhvlyTsrpFHIMDEpg=">AAACWnicbVDLahtBEBytk1iPPCQnt1yGiEBOYjcOtslJOJecjCOiB9EK0TM7sgbNY5mZjRHD/oWvzn8F8jGZlXSIpDQ0FFXddHWRXHDr4vh3LTp58vTZab3RbD1/8fJVu3M2srowlA2pFtpMCFgmuGJDx51gk9wwkESwMVl9qfTxT2Ys1+q7W+dsJuFO8QWn4AL1IzVLjVOncTJvd+NevCl8DJId6KJd3c47tc9ppmkhmXJUgLXTJM7dzINxnApWNtPCshzoCu7YNEAFktmZ31gu8fvAZHihTWjl8Ib9d8ODtHYtSZiU4Jb2UKvI/2nTwi2uZp6rvHBM0e2hRSFw+LH6H2fcMOrEOgCghgevmC7BAHUhpb0rROuVA2L3PvGZrQyXzWaq2D3VUoLKfDoYlD6tzBDiB2W5L9Kb0m9VCsLflEEPaSeH2R6D0cdectE7//ap27/e5V5Hb9E79AEl6BL10Vd0i4aIIoUe0CP6VfsTRVEjam1Ho9pu5zXaq+jNXxSdtyQ=</latexit>§ ⇢ or 1<latexit sha1_base64="s/9D7PJLWJrL2wt5SShr0gI+bZ0=">AAACL3icbVDLSsNAFJ3UV42vVpduBovgxpKoqMuiG5cV7APaUCaTSTt0MhNmJkIJ+Qm3+hN+jbgRt/6FkzYL03rgwuGce7n3Hj9mVGnH+bQqa+sbm1vVbXtnd2//oFY/7CqRSEw6WDAh+z5ShFFOOppqRvqxJCjyGen50/vc7z0TqajgT3oWEy9CY05DipE2Ut+F53AoJ2JUazhNZw64StyCNECB9qhu1YeBwElEuMYMKTVwnVh7KZKaYkYye5goEiM8RWMyMJSjiCgvnR+cwVOjBDAU0hTXcK7+nUhRpNQs8k1nhPRELXu5+J83SHR466WUx4kmHC8WhQmDWsD8exhQSbBmM0MQltTcCvEESYS1yai0xRdiqpGvsrLqB5SPy1qg8icy2zYhusuRrZLuRdO9bl4+XjVad0WcVXAMTsAZcMENaIEH0AYdgAEDL+AVvFnv1of1ZX0vWitWMXMESrB+fgEe16hO</latexit><latexit sha1_base64="1kGfeHdsV//FMcy0N6xzv+AIF80=">AAACK3icbVDLSsNAFJ3xWeOr1aWbYBFclURFXRbduKxgH9CGMjOZNEMnM2FmIpSQX3CrP+HXuFLc+h8mbRam9cCFwzn3cu89OOZMG8f5hGvrG5tb27Uda3dv/+Cw3jjqaZkoQrtEcqkGGGnKmaBdwwyng1hRFGFO+3h6X/j9Z6o0k+LJzGLqRWgiWMAIMoU0UqEc15tOy5nDXiVuSZqgRGfcgI2RL0kSUWEIR1oPXSc2XoqUYYTTzBolmsaITNGEDnMqUES1l86PzeyzXPHtQKq8hLHn6t+JFEVazyKcd0bIhHrZK8T/vGFiglsvZSJODBVksShIuG2kXXxu+0xRYvgsJ4golt9qkxApREyeT2ULlnJqENZZVcU+E5Oq5uviicyy8hDd5chWSe+i5V63Lh+vmu27Ms4aOAGn4By44Aa0wQPogC4gIAQv4BW8wXf4Ab/g96J1DZYzx6AC+PMLb5WniA==</latexit>

1)n2⇢ essentially gauges the graph connectivity

Center of Machine Learning Research< 21 >DSGD convergence rate
• Convergence comparison (non-convex and data-homogeneous scenario) [KLB+20]:
⇣
⌘
1 X
(k) 2
p
Ekrf (x̄ )k = O
TnT
T<latexit sha1_base64="5joZSddPznBRQ2+7vbhQ7Dk4CTg=">AAADq3icrVJdb9MwFE0WPtbytcEjLxYVqBVqaToEaNKkaQzB0yhdu1XUbWU7bhs1tjvbgVaefxu/gx/AK/wFnCYPdEPihStFObrnXvv43IsXSax0s/nd3wpu3Lx1e7tUvnP33v0HO7sPz5RIJaE9IhIh+xgpmsSc9nSsE9pfSIoYTug5nr/N+PMvVKpY8K5eLeiQoSmPJzFB2qXGu34fMiyWpl0/fX9s98EzAC9SFAE4kYiY0JquhSplYzM/CO2oCxnSM4zNOwsvIUc4QWBShRhJs7QjU53XbA1ejlrgAHyER/G0WpwDVTxlyLr/hdSGd60FGV0DEJZLpVzB8f9W8C8JzwFMeUQldjQ1RZWciZFpvdizeX2OnYYcgGpYz0pqIxNmeTt2HQzQpZYIAuGMnlEU2fXbxjuVZqO5DnAdhAWoeEW03Sz2YSRIyijXJEFKDcLmQg8NkjomCbVlmCq6QGSOpnTgIEeMqqFZ74AFT10mAhMh3cc1WGf/7DCIKbVi2FVmDqqrXJb8GzdI9eTN0MR8kWrKSX7RJE2AFiBbKBDFkhKdrBxARMZOKyAz5MzUbu02bsFCzDXCauMlJlKZYFsuQ06/EsEY4pGBnY4bVTHqjrWbJDmxJmcJSsyJm0PZuR1e9fY6OGs1wleNvU8vK4dHhe/b3mPviVf1Qu+1d+h98NpezyP+N/+H/9P/FdSD0+BzAPPSLb/oeeRtREB/A7mtMiU=</latexit>

P-SGD :

k=1

⇣
⌘
1 X
⇢2/3 2/3
Ekrf (x̄(k) )k2 = O p+ 2/3
TT (1 ⇢)1/3
nT
k=1
|
{z
}
T

D-SGD :

extra overhead

where<latexit sha1_base64="C7boI7RLqXzetU6VYX1040vnwrU=">AAACWHicbVBNSyNBEK2Mu35k1++jl2HDgqcwo6LiSfSyJ9FgNJCJUt3TiU36Y+ju2SU08ye87v6x9dfYk+Rg1IKCx3tV1KtHCsGtS5L/jWjpy9flldW15rfv6xubW9s7d1aXhrIu1UKbHkHLBFes67gTrFcYhpIIdk/Gl7V+/5sZy7W6dZOCDSSOFB9yii5QvczykcSHg8etVtJOphV/BOkctGBe14/bjbMs17SUTDkq0Np+mhRu4NE4TgWrmllpWYF0jCPWD1ChZHbgp4ar+Gdg8nioTWjl4in7dsOjtHYiSZiU6J7se60mP9P6pRueDjxXRemYorNDw1LETsf193HODaNOTAJAanjwGtMnNEhdyGjhCtF67JDYhU98bmvDVbOZKfaHailR5T7rdCqf1WYI8Z2qWhTpVeVnKkXhr6qgh7TT99l+BHcH7fS4fXhz1Dq/mOe+CnvwA/YhhRM4h19wDV2gIOAZ/sK/xksE0Uq0NhuNGvOdXVioaOcVGvy2uA==</latexit>2is the gradient noise, and T is the number of iterations<latexit sha1_base64="kDAtQi2ND3CW20xDLd0/PEvP9uA=">AAACUXicbVBNTxRBEK0ZQXERBT16mbgh8bSZAaLGE9ELJwIbFkh2NqS6pxY62x+T7h7NpjO/wKv+Mk/8FG/27O7BBSup5OW9qtSrx2opnM/z+yR9srH59NnW8972i52Xr3b3Xl8601hOI26ksdcMHUmhaeSFl3RdW0LFJF2x2ddOv/pG1gmjL/y8ponCWy2mgqOP1PnFzW4/H+SLyh6DYgX6sKqzm73kc1kZ3ijSnkt0blzktZ8EtF5wSW2vbBzVyGd4S+MINSpyk7Bw2mb7kamyqbGxtc8W7L8bAZVzc8XipEJ/5x5qHfk/bdz46adJELpuPGm+PDRtZOZN1r2dVcIS93IeAXIroteM36FF7mM4a1eYMTOPzK19EirXGW57vVLTd26UQl2FcjhsQ9mZYSwM23Zd5KdtWKocZThtox7TLh5m+xhcHgyKD4PD86P+8ZdV7lvwFt7BeyjgIxzDCZzBCDgQ/ICf8Cv5nfxJIU2Xo2my2nkDa5Vu/wUPfLTI</latexit>• D-SGD can asymptotically converge as fast as P-SGD when T ! 1 ; the first term dominates; reachlinear speedup asymptotically<latexit sha1_base64="P3AmB7xN4emTfMqSy4VHay0dgoE=">AAACXHicbVDLahtBEBxt/FDkR+wEcslliAj4JHZtE5ucRHLJyTjCsg1aYXpmZ+1B81hmeh3EsL+Ra/JbueRbMivpENlpaCiquunqYpWSHtP0dyd5sbG5td192dvZ3dt/dXD4+trb2nEx5lZZd8vACyWNGKNEJW4rJ0AzJW7Y7Eur3zwK56U1VzivxFTDvZGl5ICRyq9ojpbm0pQ4vzvop4N0UfQ5yFagT1Z1eXfY+ZQXltdaGOQKvJ9kaYXTAA4lV6Lp5bUXFfAZ3ItJhAa08NOwMN3QD5EpaGldbIN0wf67EUB7P9csTmrAB/9Ua8n/aZMay/NpkKaqURi+PFTWisZH2wRoIZ3gqOYRAHcyeqX8ARxwjDmtXWHWzhCYX/skFL413PR6uRHfudUaTBHy0agJeWuGsTBqmnWRXzRhqXJQ4aKJekw7e5rtc3B9PMg+Dk6+nfaHn1e5d8k78p4ckYyckSH5Si7JmHBSkR/kJ/nV+ZNsJDvJ3nI06ax23pC1St7+BVkCuDw=</latexit>• But D-SGD requires more iteration to reach that stage due to the overhead caused by partial average

Center of Machine Learning Research< 22 >

Transient iterations• Definition [POP21]: number of iterations before D-SGD achieves linear speedup• D-SGD for non-convex and data-homogeneous
scenario has O(n3 (1 ⇢) 2 ) transient iterations

D-SGD over ring (logistic regression)<latexit sha1_base64="4FGwyAAZQIkAn9UlEi7EVmkWWyw=">AAAB/HicbVDLTgIxFO34RHyNsnTTSExgAZlBoi6JbtyJiTwSGEinFGjotJO2YzKZ4K+4caExbv0Qd/6NBWah4ElucnLOvbn3Hj9kVGnH+bbW1jc2t7YzO9ndvf2DQ/vouKlEJDFpYMGEbPtIEUY5aWiqGWmHkqDAZ6TlT25mfuuRSEUFf9BxSLwAjTgdUoy0kfp27q7Ae+cFt9SVY1HsJaXKtNi3807ZmQOuEjcleZCi3re/ugOBo4BwjRlSquM6ofYSJDXFjEyz3UiREOEJGpGOoRwFRHnJ/PgpPDPKAA6FNMU1nKu/JxIUKBUHvukMkB6rZW8m/ud1Ij288hLKw0gTjheLhhGDWsBZEnBAJcGaxYYgLKm5FeIxkghrk1fWhOAuv7xKmpWye1Gu3lfztes0jgw4AaegAFxwCWrgFtRBA2AQg2fwCt6sJ+vFerc+Fq1rVjqTA39gff4ACa6TGg==</latexit><latexit sha1_base64="/uzIgb/ubHdb5m9u32qF5NpFdVE=">AAAC6XicbVFdixMxFM2MX2v96uqjL8EidMGtnXZREYRFX3yQdS3t7kLTlkwmnYbmYzbJuJSQH+GT4qu/yh8jmGkH2e56IeTknHu5N+emBWfGdru/o/jGzVu37+zcbdy7/+Dho+bu4xOjSk3oiCiu9FmKDeVM0pFlltOzQlMsUk5P0+WHSj/9SrVhSg7tqqATgXPJ5oxgG6hZ8zuaa0wc0gs1db2XfQ+RYbnAm4d3w5ptJ/tVzt7UJRUPEaewLl3n+3Cfa+vk0Ht0XuIMok9K5prlC4u1Vhdwww7hO/RZ0By3LzU+gHLa9+5fj57fmzVb3U53HfA6SGrQAnUcz3ajtyhTpBRUWsKxMeOkW9iJw9oywqlvoNLQApMlzuk4QIkFNRO3dtDD54HJ4FzpcKSFa/ZyhcPCmJVIQ6bAdmGuahX5P21c2vmbiWOyKC2VZNNoXnJoFazWATOmKbF8FQAmmoVZIVng4IwNS9vqkiq1tDg1Wz9xmakG9o0GkvSCKCGwzBwaDMI+qmHS1A283xbJkXcblWDujnzQg9vJVW+vg5NeJ3nV6X85aB2+r33fAU/BM9AGCXgNDsFHcAxGgIA/USt6Ee3Hy/hb/CP+uUmNo7rmCdiK+Ndf0e3rvQ==</latexit>⇢

2/3 2/3

T 2/3 (1⇢)1/3

⇢4 n 3 ⇢4 n 3=) O(
T = ⌦( 2 ) 2 )
(1 ⇢)
(1 ⇢)
<latexit sha1_base64="45/3kgvHn70xEEJ/gp6XKuI9/bA=">AAACCXicbVC7TsMwFHXKq5RXgJHFokJqB6qkVMBYwcJGkehDatLKcZ3WquNEtoNURV1Z+BUWBhBi5Q/Y+BucNgO0HOlKx+fcK997vIhRqSzr28itrK6tb+Q3C1vbO7t75v5BS4axwKSJQxaKjockYZSTpqKKkU4kCAo8Rtre+Dr12w9ESBryezWJiBugIac+xUhpqW/C25LjC4QTR4zCXg3y3tk0Kdmn6bPcq07LfbNoVawZ4DKxM1IEGRp988sZhDgOCFeYISm7thUpN0FCUczItODEkkQIj9GQdDXlKCDSTWaXTOGJVgbQD4UuruBM/T2RoEDKSeDpzgCpkVz0UvE/rxsr/9JNKI9iRTief+THDKoQprHAARUEKzbRBGFB9a4Qj5AORunwCjoEe/HkZdKqVuzzSu2uVqxfZXHkwRE4BiVggwtQBzegAZoAg0fwDF7Bm/FkvBjvxse8NWdkM4fgD4zPHyRBmLY=</latexit>

pnT• Sparse topology ⇢ ! 1 incurs longer tran. Iters.
<latexit sha1_base64="P1FqJ4ccUyWhvlyTsrpFHIMDEpg=">AAACWnicbVDLahtBEBytk1iPPCQnt1yGiEBOYjcOtslJOJecjCOiB9EK0TM7sgbNY5mZjRHD/oWvzn8F8jGZlXSIpDQ0FFXddHWRXHDr4vh3LTp58vTZab3RbD1/8fJVu3M2srowlA2pFtpMCFgmuGJDx51gk9wwkESwMVl9qfTxT2Ys1+q7W+dsJuFO8QWn4AL1IzVLjVOncTJvd+NevCl8DJId6KJd3c47tc9ppmkhmXJUgLXTJM7dzINxnApWNtPCshzoCu7YNEAFktmZ31gu8fvAZHihTWjl8Ib9d8ODtHYtSZiU4Jb2UKvI/2nTwi2uZp6rvHBM0e2hRSFw+LH6H2fcMOrEOgCghgevmC7BAHUhpb0rROuVA2L3PvGZrQyXzWaq2D3VUoLKfDoYlD6tzBDiB2W5L9Kb0m9VCsLflEEPaSeH2R6D0cdectE7//ap27/e5V5Hb9E79AEl6BL10Vd0i4aIIoUe0CP6VfsTRVEjam1Ho9pu5zXaq+jNXxSdtyQ=</latexit>

Center of Machine Learning Research< 23 >

Trade-off between comm. cost and trans. iters.

•

Recall per-iter comm. O(dmax ) and trans. iters. ⌦(n3 (1<latexit sha1_base64="J35v2FnQp3fJtnauKsrW1KPz95Y=">AAACa3icbVDLahsxFJUnfaTuI06y6mMhagLOImYmKUnpKqSbrtLU1EnA45grjWwL6zFImhYjRL+m2/R7+hH9h2psL+qkFy4czrmXe+4hpeDWpenvRrLx4OGjx5tPmk+fPX+x1dreubS6MpT1qRbaXBOwTHDF+o47wa5Lw0ASwa7I7GOtX31jxnKtvrp5yYYSJoqPOQUXqVHrZf5Zsgl01M0R7mQHuZnq/Rt/cBj2R6122k0Xhe+DbAXaaFUXo+3Gh7zQtJJMOSrA2kGWlm7owThOBQvNvLKsBDqDCRtEqEAyO/SLHwLei0yBx9rEVg4v2H83PEhr55LESQluau9qNfk/bVC58fuh56qsHFN0eWhcCew0rgPBBTeMOjGPAKjh0SumUzBAXYxt7QrReuaA2LVPfGFrw6HZzBX7TrWUoAqf93rB57UZQnwvhHWRnge/VCkIfx6iHtPO7mZ7H1wedrPj7tGXd+3Ts1Xum+g1eos6KEMn6BR9Qheojyj6gX6iW/Sr8SfZTV4lb5ajSWO1s4vWKtn7C5l0vFQ=</latexit><latexit sha1_base64="E+QIbabTheG+ghE+Umq3bpUIrYI=">AAAB8nicbVBNSwMxEJ31s9avqkcvwSLUS9mVoh6LXrxZwX7AdinZNNuGZpMlyYpl6c/w4kERr/4ab/4b03YP2vpg4PHeDDPzwoQzbVz321lZXVvf2CxsFbd3dvf2SweHLS1TRWiTSC5VJ8SaciZo0zDDaSdRFMchp+1wdDP1249UaSbFgxknNIjxQLCIEWys5N9V+r2sG+OnyVmvVHar7gxomXg5KUOORq/01e1LksZUGMKx1r7nJibIsDKMcDopdlNNE0xGeEB9SwWOqQ6y2ckTdGqVPoqksiUMmqm/JzIcaz2OQ9sZYzPUi95U/M/zUxNdBRkTSWqoIPNFUcqRkWj6P+ozRYnhY0swUczeisgQK0yMTaloQ/AWX14mrfOqd1Gt3dfK9es8jgIcwwlUwINLqMMtNKAJBCQ8wyu8OcZ5cd6dj3nripPPHMEfOJ8/w4+Q7g==</latexit>⇢) 2 )• Trade-off between per-iteration communication and transient iteration complexity<latexit sha1_base64="zIredhPhYXfbA0OjrGSprrLvQik=">AAADl3icdVLbbhMxEHWyXMpyaQovVLxYJCBeWGWDBLxRAUJ9bAVpK8VR5PVOEiu+rGxv1WjlF/6ST+AjkPAmUci2ZSRL4zkzc2aOnRWCW9fv/2q1ozt3793fexA/fPT4yX7n4OmZ1aVhMGRaaHORUQuCKxg67gRcFAaozAScZ4svNX5+CcZyrX64ZQFjSWeKTzmjLoQmB62fJIMZV5WjocSPxvG/eymo8ZVhzMfE6cKUAmIiS+F44C2lqlJfCV95vGuvMXFw5bJp9b2gxgIOlWGK2dLvQF9BNRBCMJE8XzNscgowb7kDg5mWMvG7DD3C5sAWkppFr8m9tR5xXIJtwBiTS1tQBtVAypp0y+UMVTbBNV1S8xUCrrhbjXx7owbpf8apl8q0c1qu9wKVb1Xd3oLm8aTT7Sf9leGbTrpxumhjJ5POH5JrVkpQjglq7SjtF25cURNepm5ISgthzwWdwSi4ioYFxtXqs3j8KkRyPNUmHOXwKrpbUVFp7VJmIVNSN7fXsTp4GzYq3fTjuOKqKB0otiaaliI8M65/Hs65AebEMjiUGR5mxWxODWVB9SZLpvUiaGN9M5rlXM18XOuVXlfnpnM2SNL3ybvTQffo80a5PfQCvURvUIo+oCN0jE7QELHW7/Z++3n7MDqMPkXfouN1aru1qXmGGhad/gWEZRTa</latexit>

Sparse topology

Dense topology

per-iter comm.

X⇥

trans. iter. complexity⇥

Center of Machine Learning ResearchX< 24 >

What topology to use?
• Shall we use these common topologies to organize all nodes?

Ring

Center of Machine Learning Research

Grid

Torus

Erdos-Renyi Random< 25 >

What topology to use?
• Communication cost v.s. transient iteration complexity in DSGD
<latexit sha1_base64="ERUA6ofpDvMzp7ScCp+xXUgT2nQ=">AAAG8HicnVTNThsxEF4oSUn6B+2xF6sEBIessqGUHim0oj20SWn4kdgQeb1OsFjbK9uLiFa+tq/QW9Vr36hv0GMfoXb+RJIFCiNFmZ35xt/MeDxBHBGpKpXfM7P35nL5+/OF4oOHjx4/WVh8eiB5IhDeRzzi4iiAEkeE4X1FVISPYoEhDSJ8GJztWP/hORaScNZQ3Rg3Keww0iYIKmNqLc799QPcISxV0ITo42axUPARZgoLwjr2Y+ROIih0KhDSxlzwFY9FEuGeTpNIEZNMQlnq6RTp1Ff4QgXttMFjk0OnqzVYAUNjHYsyMQwu2OGUuuCyryEgky74YNzmb5WQEEiTDxSEr2kAgO8Dn5JwSL1nsgTZsgJKtVVvrZRhZSebk/a++OcyhginFXeD0j5dcdnQfFFQFKyMTrDxtz/LnFB9W94VpqpbJu0rEoU4rWlDuJFNOMU4Imxwkci7tOl2TCW/LSCyE1DVpfIeZOGugPHpFcTgcitHjOvTjPbKA64Up71bt/exTWIozLhjYFk+QoWyWGzbahR3YFZ9n9w37nWZXeXPKN1mlPq9x5gGUYK1GRfzHsC7i5jra6sfixrk6pv30qqatqzp0hA4hhsWZZoF+uCTHryk/xO9PkCPl5JVSI3hch1jcUMpV1B6w5RuAt65kiF6YkTMSsIsHC2t4ujTrLjWwlLFrfQETCveQFlyBlJvLfzxQ44SapYiiqCUx14lVs3Uzh8y5xX9RGLTxjPYwcdGZZBi2Ux7eWuwbCwhaHNhfkyBnvVyRAqplF0aGCSF6lRO+qwxy3ecqPbrZkpYnCjMUJ+onURAcWD3PAiJwEhFXaNAJIgdR3QKzfO0i7U4RhNwfmZ6I21rvMlGTCsHVdd75b78XF3a2h40ad557rxwVh3P2XS2nPdO3dl3UO4wp3Nfc9/yIv89/yP/sw+dnRnEPHPGJP/rH08U3Nk=</latexit>

Topology

Per-iter. Comm.

Trans. Iters. (iid scenario)

Ring
2D-Grid
2D-Torus
1
2 -RandGraph

O(1)
O(1)
O(1)
O(n)

O(n7 )
Õ(n5 )O(n5 )O(n3 )The smaller both comm. cost and tran. Iters. are, the better• These topologies either have expensive communication cost or longer transient stage• Is there any topology that enables both cheap communication and fast convergence?

Center of Machine Learning Research< 26 >

PART 02
Exponential graphs are provably efficientStatic exponential graph: topology and per-iteration comm.

<latexit sha1_base64="dFdn9F+PH6ykkTsUV0iqcvEpFRM=">AAACf3icbVDLahsxFJWnr9R9Oe0yG1FTmoJjZqYlSbsK6aarkJo6CVi2kTQaR1iPQdKkGKGvyNdkm3xF/6Ya24s66YULh3Pu5Z57SCW4dWn6p5U8evzk6bOt5+0XL1+9ftPZfntmdW0oG1IttLkg2DLBFRs67gS7qAzDkgh2TubfG/38ihnLtfrlFhUbSzxTvOQUu0hNO3v5JO3lk6yHaKGd7cF84pEohdYGCT2b5rtqL/uEzJIJ00437afLgg9BtgZdsK7T6XbrGyo0rSVTjgps7ShLKzf22DhOBQttVFtWYTrHMzaKUGHJ7Ngv/wrwQ2QKWGoTWzm4ZP/d8Fhau5AkTkrsLu19rSH/p41qVx6OPVdV7Ziiq0NlLaDTsAkJFtww6sQiAkwNj14hvcQGUxej3LhCtJ47TOzGJ76wjeHQbiPFflMtJVaFR4NB8KgxQ4gfhLAp0pPgVyrFwp+EqMe0s/vZPgRneT/b73/++aV7dLzOfQvsgPdgF2TgAByBH+AUDAEF1+AG3IK7pJV8TPpJuhpNWuudd2Cjkq9/Ac1fw6s=</latexit>• Each node links to neighbors that are 20 , 21 , · · · , 2blog2 (n 1)c away [ALB+19]• In the figure, node 1 connects to node 2, 3 and 5.

• Each node has dlog2 (n)e neighbors; per-iter comm. cost is O(log2 (n))<latexit sha1_base64="6aLKGog4xmFAMw9yApXyMs+i5A8=">AAACaXicbVDLbhNBEBwvr2AeseEAgssICylcrN2ACOIUwYVTFCycRPJaVk/v2Bl5HquZ2SBrNF/DFT6Ib+AnmLV9wAkttVSq6lZXF6ulcD7Pf3eyW7fv3L23d7/74OGjx/u9/pMzZxqLfIxGGnvBwHEpNB974SW/qC0HxSQ/Z8vPrX5+xa0TRn/zq5pPFSy0mAsEn6hZ71kpkQtJS2kWs8MD/YaWtiVmvUE+zNdFb4JiCwZkW6ezfudjWRlsFNceJTg3KfLaTwNYL1Dy2C0bx2vAJSz4JEENirtpWH8Q6evEVHRubGrt6Zr9dyOAcm6lWJpU4C/dda0l/6dNGj//MA1C143nGjeH5o2k3tA2DloJy9HLVQKAViSvFC/BAvoU2s4VZszSA3M7n4TKtYZjt1tq/h2NUqCrUI5GMZStGcbCKMZdEU9i2KgIMpzEpKe0i+vZ3gRnh8Pi/fDt13eD40/b3PfIS/KKHJCCHJFj8oWckjFBEskP8pP86vzJ+tnz7MVmNOtsd56SncoGfwHC4ryA</latexit><latexit sha1_base64="N2qhgHQtRaxJAv8uvflWVmEnqIQ=">AAACCXicbVDLSsNAFJ3UV62vqks3wSK0m5KUoi6LbtxZwT6gCWUynbRDJzNh5kYooV/g3q3+gjtx61f4B36G0zYL23rgwuGcezmXE8ScaXCcbyu3sbm1vZPfLeztHxweFY9P2lomitAWkVyqboA15UzQFjDgtBsriqOA004wvp35nSeqNJPiESYx9SM8FCxkBIORvPuyx+WwXyuLSqVfLDlVZw57nbgZKaEMzX7xxxtIkkRUAOFY657rxOCnWAEjnE4LXqJpjMkYD2nPUIEjqv10/vPUvjDKwA6lMiPAnqt/L1IcaT2JArMZYRjpVW8m/uf1Egiv/ZSJOAEqyCIoTLgN0p4VYA+YogT4xBBMFDO/2mSEFSZgaiosxQRSjgEHemqqcVeLWCftWtW9rNYf6qXGTVZSHp2hc1RGLrpCDXSHmqiFCIrRC3pFb9az9W59WJ+L1ZyV3ZyiJVhfvxCMmdk=</latexit>• Empirically successful in deep training but less theoretically understoodCenter of Machine Learning Research< 28 >

Static exponential graph: weight matrix• The weight matrix associated with exponential graph is defined as<latexit sha1_base64="B72FSU6YDcb7IOiPkdVRY4UUFkw=">AAADBXicbVJNbxMxEN0sXyV8BThysUhACZBoN0LApVIFF45FIm2lOERe72zixB+L7W0aWcu1/BluiCu/g7/BmQPedFWRljk9vZnxm3njJOfM2Cj61QivXL12/cbOzeat23fu3mvdf3BgVKEpjKjiSh8lxABnEkaWWQ5HuQYiEg6HyfJdlT88Bm2Ykh/tOoeJIDPJMkaJ9dS09RsnMGPSEc5m8lmJOUmAuxVb9I31JbQPJ3nZXH1yWAtU4aljixLtombdSL24KZs404S6uHSYU2AcYa5m02FX9hDWG+I5ikv0FGGRqBPHMtSpK7Agdq6FEyotu4s+eyF7vQ5iBhGJmLQwA42URh22u+iUCOMm/lyQFEXnbyk7B71iBgYlPjY5oeD6QyH8SCDT8/EqXO84bbWjQbQJdBnENWgHdexPW39wqmghQFrKiTHjOMrtxBHt/eHgHy8MeN0lmcHYQ0kEmInb3KZETzyTosyvkClp0Yb9t8MRYcxaJL6ycsJczFXk/3LjwmZvJo7JvLAg6ZlQVnBkFaoOjVKmgVq+9oBQzfysiM6Jv5L136G5JZMotbQkMVuruNRUE1d2xRfNuQwOhoP41eDlh2F7721t3E7wKHgcdIM4eB3sBe+D/WAU0MZR40vjtPE1PA2/hd/DH2elYaPueRhsRfjzLxFL9Xs=</latexit>

exp
wij
=

⇢

1
dlog2 (n)e+1

0

if log2 (mod(ji, n)) is an integer or i = jotherwise.

• An illustrating example:

Center of Machine Learning Research< 29 >

Static exponential graph: connectivity• Is the static exponential graph well connected?

1
T
Theorem. Let ⌧ = dlog2 (n)e, and ⇢ = kWn 11 k2 be the spectral gap. It
holds that
8
2
>
⇢
=
1
, when n is even
<
⌧ +1
2
>
:⇢ < 1, when n is odd⌧ +1<latexit sha1_base64="BKCmI0ifmDX8nOnOJO9v2jLS4uY=">AAADoHicdVLbbtNAEHUSLiXcWnhCvIyStCptieIIARIgVfBSJCRaKWkqumm0Xo/tVde71u66NHL9B/wg38ErD6zbKDQNjGV5fOZ25hJkghvb6/2s1Ru3bt+5u3Kvef/Bw0ePV9eeHBqVa4ZDpoTSRwE1KLjEoeVW4FGmkaaBwFFw+qmyj85QG67kwE4zHKc0ljzijFoHTdZqP4hUXIYoLRCL5zaIikGCSmPaLeELWugQS3P4AEQw5MJ9VDzpb8oXQHQFdHaAytB56URVXhcjeAkk0pQVflnIkqTUJqFxP3+1kwG5mPQ7ECDYBMFkyKymAmKadeGzhUSJ0DgTtU0SYMxlQQWP5VbZhHVXw59X6JeFvz1nVEKTCIwsKRbCMCybM3YLkVVf2365A3PZIO+qB4CkgTovvicooSM7wA3gGbpeyFWi9/9JtAGzBMvxKqxYoAznnIjmcWK718CtcrLa7nV7lwLLij9T2t5M9ierv0moWJ669TFBjTn2e5kdF1RbzgS6irnBjLJTGuOxUyVN0YyLy7MpYd0hIURKu9et/xK9HlHQ1JhpGjjPanXmpq0C/2U7zm30dlxwmeUWJbsqFOUCrILqBiHk2m1cTJ1CmeaOK7CEumlad6nNhTKBUqeWBmahlSI0FeNqXP7N4Swrh/2u/7r76qDf3v04G9yK99xreZue773xdr09b98beqz2q/6s3qq3G63GXuNr4+DKtV6bxTz1FqTx7Q8EPCCH</latexit>• This theorem implies that exponential graph has ⇢(W ) = O(1<latexit sha1_base64="A+dXDVcQ/0+ahE0M+b653uJgHp4=">AAACL3icbVDLSgMxFM3UV62vUZe6CLZCu7DOFFE3QtGNOyvYB7TDkEnTNjSTDElGKEM3fo3b+jPiRtz6Dy5MHwvbeuDC4Zx7ufeeIGJUacf5sFIrq2vrG+nNzNb2zu6evX9QUyKWmFSxYEI2AqQIo5xUNdWMNCJJUBgwUg/6d2O//kykooI/6UFEvBB1Oe1QjLSRfPs415I9ka8X4A18yLtn7nmLia5fyvNCIefbWafoTACXiTsjWTBDxbd/Wm2B45BwjRlSquk6kfYSJDXFjAwzrViRCOE+6pKmoRyFRHnJ5IshPDVKG3aENMU1nKh/JxIUKjUIA9MZIt1Ti95Y/M9rxrpz7SWUR7EmHE8XdWIGtYDjSGCbSoI1GxiCsKTmVoh7SCKsTXCZuTWBEH2NAjX3StJW44uHJi53MZxlUisV3cvixWMpW76dBZcGR+AE5IELrkAZ3IMKqAIMXsArGIE3a2S9W5/W17Q1Zc1mDsEcrO9fpvmm9Q==</latexit>

1/ log2 (n))• Highly non-trivial proofs; requires smart utilization of Fourier transformCenter of Machine Learning Research< 30 >

Static exponential graph: illustration of the spectral gap• Our theoretical bound is very tight• Spectral gap increases slowly when n grows

Center of Machine Learning Research< 31 >

Static exponential graph: transient iterations in DSGD
• Recall DSGD has transient iteration complexity O(n3 /(1<latexit sha1_base64="8tO7i9AB5RnVCrunfXiePl6m6T8=">AAACJnicbVDLSgMxFM3UV62v0S7dBIvQLqwztajLoht3VrAP6ItMJtOGZpIhyQhl6Le4rT/jTsSdH+LC9LGwrQcCh3Pu5Z4cL2JUacf5slIbm1vbO+ndzN7+weGRfXxSVyKWmNSwYEI2PaQIo5zUNNWMNCNJUOgx0vCG91O/8UKkooI/61FEOiHqcxpQjLSRenY2eRzneffqMu9etOVAFLqlQs/OOUVnBrhO3AXJgQWqPfun7Qsch4RrzJBSLdeJdCdBUlPMyDjTjhWJEB6iPmkZylFIVCeZhR/Dc6P4MBDSPK7hTP27kaBQqVHomckQ6YFa9abif14r1sFtJ6E8ijXheH4oiBnUAk6bgD6VBGs2MgRhSU1WiAdIIqxNX5mlM54QQ408tfSVxFfTxGNTl7tazjqpl4rudbH8VM5V7hbFpcEpOAN54IIbUAEPoApqAIMReAUT8GZNrHfrw/qcj6asxU4WLMH6/gVKzKTp</latexit>• With ⇢(W ) = O(1<latexit sha1_base64="A+dXDVcQ/0+ahE0M+b653uJgHp4=">AAACL3icbVDLSgMxFM3UV62vUZe6CLZCu7DOFFE3QtGNOyvYB7TDkEnTNjSTDElGKEM3fo3b+jPiRtz6Dy5MHwvbeuDC4Zx7ufeeIGJUacf5sFIrq2vrG+nNzNb2zu6evX9QUyKWmFSxYEI2AqQIo5xUNdWMNCJJUBgwUg/6d2O//kykooI/6UFEvBB1Oe1QjLSRfPs415I9ka8X4A18yLtn7nmLia5fyvNCIefbWafoTACXiTsjWTBDxbd/Wm2B45BwjRlSquk6kfYSJDXFjAwzrViRCOE+6pKmoRyFRHnJ5IshPDVKG3aENMU1nKh/JxIUKjUIA9MZIt1Ti95Y/M9rxrpz7SWUR7EmHE8XdWIGtYDjSGCbSoI1GxiCsKTmVoh7SCKsTXCZuTWBEH2NAjX3StJW44uHJi53MZxlUisV3cvixWMpW76dBZcGR+AE5IELrkAZ3IMKqAIMXsArGIE3a2S9W5/W17Q1Zc1mDsEcrO9fpvmm9Q==</latexit>⇢)2 ) in iid scenarios

1/ log2 (n)) , exponential graphs have tran. iters. as O(n3 log22 (n))<latexit sha1_base64="nqBUf4hemZPRRNK5Y7/VmDtHk/s=">AAACJnicbVDLTgIxFO3gC/GFsnTTSExgQ2aQqEuiG3diIo8EhkmnU6Ch007ajgmZzLe4xZ9xZ4w7P8SF5bEQ8CRNTs65N/f0+BGjStv2l5XZ2t7Z3cvu5w4Oj45P8qdnLSViiUkTCyZkx0eKMMpJU1PNSCeSBIU+I21/fD/z2y9EKir4s55ExA3RkNMBxUgbycsXkse0xPtXPSaG/apXLfFy2csX7Yo9B9wkzpIUwRINL//TCwSOQ8I1ZkiprmNH2k2Q1BQzkuZ6sSIRwmM0JF1DOQqJcpN5+BReGiWAAyHN4xrO1b8bCQqVmoS+mQyRHql1byb+53VjPbh1E8qjWBOOF4cGMYNawFkTMKCSYM0mhiAsqckK8QhJhLXpK7dyxhdirJGvVr6SBGqWODV1OevlbJJWteJcV2pPtWL9bllcFpyDC1ACDrgBdfAAGqAJMJiAVzAFb9bUerc+rM/FaMZa7hTACqzvXwSrpVQ=</latexit>• Per-iteration communication and transient iteration complexity are nearly the best (up to log2 (n) )<latexit sha1_base64="Rfd5VbTfFINXp/ScGlofdqQD6Vk=">AAACGnicbVDLSsNAFJ34rPVVdelmsAh1U5JS1GXRjcsK9iFtKJPJpB06jzAzEUroV7itP+NO3LrxX1w4abOwrQcuHM65l3vvCWJGtXHdb2djc2t7Z7ewV9w/ODw6Lp2ctrVMFCYtLJlU3QBpwqggLUMNI91YEcQDRjrB+D7zOy9EaSrFk5nExOdoKGhEMTJWeu4zORzUKuJqUCq7VXcOuE68nJRBjuag9NMPJU44EQYzpHXPc2Pjp0gZihmZFvuJJjHCYzQkPUsF4kT76fzgKby0SggjqWwJA+fq34kUca0nPLCdHJmRXvUy8T+vl5jo1k+piBNDBF4sihIGjYTZ9zCkimDDJpYgrKi9FeIRUggbm1FxaU0g5digQC+9koY6u3hq4/JWw1kn7VrVu67WH+vlxl0eXAGcgwtQAR64AQ3wAJqgBTDg4BXMwJszc96dD+dz0brh5DNnYAnO1y+YwaGY</latexit><latexit sha1_base64="c+vFJb9PNEuhPF0Fo1C1f9fQwas=">AAAGwnicnVRLbxMxEN6WJjTh1YI4cbFoWqWHrpJAKRKX0ocKB0go6UPKppHX66Smu/Zie6tGi/8S/4f/woHZZJPm1aplpCizM+P5vpnx2A19pnSp9Gdu/sFCJvtwMZd/9PjJ02dLy8+PlYgkoUdE+EKeulhRn3F6pJn26WkoKQ5cn564F7uJ/+SSSsUEr+tuSJsB7nDWZgRrMLWWF347Lu0wHmsMR0yjmc85hHJNJeMd0IfOyMfSxJIQk8/lHC1CGfk0UYPI1wyIRAGPyyYmJnY0vdJuO66LEPA7XWPQGhoYa1RuMEhvo10RBDYa9dUl5spGn8ENf0XGPKSADJZMrBuEkOMgJ2BeinwIDNFsWUOFarG8Xphh5Wdbk/a+OJcqxITGJXszCPpoALL6XWOZS6SfwKkGtIOLPMkx8nm/pJW9jQMJxd2TvKOZ79G4agBvczbeFOAAry5kpP6nW/cCKjhtiUlyDSqmsHGIuXcgcXh+A+4QpA+RAr6ZBuxPAmaww0Is4ZZTlOT+gjWZlft6LjOK+mp/tG/jc5N/Zr0gsdNbwtj1I2rgssAuoP2r0Nxa89ih67GW101hEDMWMjZ6aJBJ2wI/V2gtgnQlVicJVTndqFEqE0riZk5TcMP2mTsFAinkwKq3KmcVGOfg2N2jk80ercSh3Bu+OvnBFzxQraWVkl3qCZpWyqmyYqVSay39dTxBogDeNOJjpRrlUqibcXKNCOTLO5GiMNgL3KENUDkOqGrGPdYGrYLFQ20h4cc16llHT8Q4UKobuBAZYH2uJn2JcZavEen2+2bMeBhpykkfqB35SAuUvNLIY5IS7XdBwUSy5FKRcwy7lTyN+TEYV4gL6I0aKyX2VMI4aVd5sjnTynHFLr+z336rrGzvpI1btF5Zr62iVba2rG3rk1WzjiySeZn5kNnL7Gf3sj+yP7OqHzo/l555YY1J9tc/oP7PWg==</latexit>

Topology

Per-iter. Comm.

Trans. Iters. (iid scenario)

Ring
2D-Grid
2D-Torus
1
2 -RandGraph
Static Exp

O(1)
O(1)
O(1)
O(n)
Õ(1)

O(n7 )
Õ(n5 )O(n5 )O(n3 )
Õ(n3 )• Can we achieve even better topology?
Center of Machine Learning Research< 32 >

One-peer exponential graph: topology• Split exponential graph into a sequence of one-peer realizations;• Each node has exactly one neighbor per iteration• O(1) per-iteration communication; same as ring; cheaper than gridCenter of Machine Learning Research< 33 >

One-peer exponential graph: weight matrix• We let ⌧ = dlog2 (n)e . The weight matrix W (k) is defined as<latexit sha1_base64="xRhZsuIzPzuwrdH8CNnFtRegh7Y=">AAACGXicbVBNS8NAEN3Ur1q/qh69LBahXkqioh6LXjxWsE2hjWWz2bRLNrthdyOUkB/h1f4ab+LVkz9GcNvmYFsfDDzem2Fmnp8wqrRtf1ultfWNza3ydmVnd2//oHp41FEilZi0sWBCdn2kCKOctDXVjHQTSVDsM+L60f3Ud1+IVFTwJz1OiBejIachxUgbyXWfs3p0ng+qNbthzwBXiVOQGijQGlR/+oHAaUy4xgwp1XPsRHsZkppiRvJKP1UkQThCQ9IzlKOYKC+bnZvDM6MEMBTSFNdwpv6dyFCs1Dj2TWeM9Egte1PxP6+X6vDWyyhPUk04ni8KUwa1gNPfYUAlwZqNDUFYUnMrxCMkEdYmoYUtvhCRRr7KF1U/oHyYVyomL2c5nVXSuWg4143Lx6ta865IrgxOwCmoAwfcgCZ4AC3QBhhE4BW8gYk1sd6tD+tz3lqyipljsADr6xf5QaDm</latexit><latexit sha1_base64="5mSAww8chZeUQIbr+nfKh/KOpjA=">AAACMnicbZDLSgMxFIYzXut4q7oUJFiEuikzVdSNUHTjsoK9QKeUTJq2oZlkSM4IpXTn07i1L6M7cesrCKbtLGzrgZCf7z+Hk/xhLLgBz3t3VlbX1jc2M1vu9s7u3n724LBqVKIpq1AllK6HxDDBJasAB8HqsWYkCgWrhf37iV97ZtpwJZ9gELNmRLqSdzglYFErexIASfAtDgRlXNhLdVvFvDzHgZ6AVjbnFbxp4WXhpyKH0iq3sj9BW9EkYhKoIMY0fC+G5pBo4FSwkRskhsWE9kmXNayUJGKmOZz+Y4TPLGnjjtL2SMBT+ndiSCJjBlFoOyMCPbPoTeB/XiOBzk1zyGWcAJN0tqiTCAwKT0LBba4ZBTGwglDN7Vsx7RFNKNjo5raESvWBhGY0T8M2l92R69q8/MV0lkW1WPCvChePl7nSXZpcBh2jU5RHPrpGJfSAyqiCKHpBr+gNjZ2x8+F8Ol+z1hUnnTlCc+V8/wJZ56m1</latexit><latexit sha1_base64="QYElXaLPrnTUhEJYVujMNPYGDEw=">AAAC3nicdVFNbxMxEPUuX2X5aApHLhYpKJHaaDdUwKVSBReORSJppThsvV7vxsnaXtnelsjylRviym/iH/BjkHDSBZEWRhrp6c3Mm9GbrK6YNnH8Iwhv3Lx1+87W3eje/QcPtzs7j8ZaNorQEZGVVKcZ1rRigo4MMxU9rRXFPKvoSbZ4u6qfnFOlmRQfzLKmU45LwQpGsPFU2vl+8dH2Fn2XWjZ38BBGKKMlE5Z4Te0iVChMbOLs0MHnEPFMfrKsgLuokmU67CGOzUxxy2XuevN9tif6fS+yQS/2kMFNf9dBdK5rTKhNOHcI/VebHc5XzSiK/9DSzKi6YJoO3G+R/aFXiRAVeXsrTDvdeBCvA14HSQu6oI3jtPMT5ZI0nApDKqz1JIlrM7VYGUYq6sUbTf2uBS7pxEOBOdVTu/bcwWeeyWEhlU9h4Jr9e8JirvWSZ75z5Ya+WluR/6pNGlO8nlom6sZQQS4XFU0FjYSrB8KcKUpMtfQAE8X8rZDMsLfS+DdvbMmkXBicabfJZjkTpYsi71dy1Z3rYDwcJC8HL94fdI/etM5tgSfgKeiBBLwCR+AdOAYjQII4GAdpcBaehZ/DL+HXy9YwaGceg40Iv/0CSPDkxQ==</latexit>

(k)
wij =

• An illustrating example

Center of Machine Learning Research

8
1
>
<2
1

>
:2
0

if log2 (mod(ji, n)) = mod(k, ⌧ )if i = jotherwise.

< 34 >

One-peer exponential graph: weight matrix• We let ⌧ = dlog2 (n)e . The weight matrix W (k) is defined as<latexit sha1_base64="xRhZsuIzPzuwrdH8CNnFtRegh7Y=">AAACGXicbVBNS8NAEN3Ur1q/qh69LBahXkqioh6LXjxWsE2hjWWz2bRLNrthdyOUkB/h1f4ab+LVkz9GcNvmYFsfDDzem2Fmnp8wqrRtf1ultfWNza3ydmVnd2//oHp41FEilZi0sWBCdn2kCKOctDXVjHQTSVDsM+L60f3Ud1+IVFTwJz1OiBejIachxUgbyXWfs3p0ng+qNbthzwBXiVOQGijQGlR/+oHAaUy4xgwp1XPsRHsZkppiRvJKP1UkQThCQ9IzlKOYKC+bnZvDM6MEMBTSFNdwpv6dyFCs1Dj2TWeM9Egte1PxP6+X6vDWyyhPUk04ni8KUwa1gNPfYUAlwZqNDUFYUnMrxCMkEdYmoYUtvhCRRr7KF1U/oHyYVyomL2c5nVXSuWg4143Lx6ta865IrgxOwCmoAwfcgCZ4AC3QBhhE4BW8gYk1sd6tD+tz3lqyipljsADr6xf5QaDm</latexit><latexit sha1_base64="5mSAww8chZeUQIbr+nfKh/KOpjA=">AAACMnicbZDLSgMxFIYzXut4q7oUJFiEuikzVdSNUHTjsoK9QKeUTJq2oZlkSM4IpXTn07i1L6M7cesrCKbtLGzrgZCf7z+Hk/xhLLgBz3t3VlbX1jc2M1vu9s7u3n724LBqVKIpq1AllK6HxDDBJasAB8HqsWYkCgWrhf37iV97ZtpwJZ9gELNmRLqSdzglYFErexIASfAtDgRlXNhLdVvFvDzHgZ6AVjbnFbxp4WXhpyKH0iq3sj9BW9EkYhKoIMY0fC+G5pBo4FSwkRskhsWE9kmXNayUJGKmOZz+Y4TPLGnjjtL2SMBT+ndiSCJjBlFoOyMCPbPoTeB/XiOBzk1zyGWcAJN0tqiTCAwKT0LBba4ZBTGwglDN7Vsx7RFNKNjo5raESvWBhGY0T8M2l92R69q8/MV0lkW1WPCvChePl7nSXZpcBh2jU5RHPrpGJfSAyqiCKHpBr+gNjZ2x8+F8Ol+z1hUnnTlCc+V8/wJZ56m1</latexit><latexit sha1_base64="QYElXaLPrnTUhEJYVujMNPYGDEw=">AAAC3nicdVFNbxMxEPUuX2X5aApHLhYpKJHaaDdUwKVSBReORSJppThsvV7vxsnaXtnelsjylRviym/iH/BjkHDSBZEWRhrp6c3Mm9GbrK6YNnH8Iwhv3Lx1+87W3eje/QcPtzs7j8ZaNorQEZGVVKcZ1rRigo4MMxU9rRXFPKvoSbZ4u6qfnFOlmRQfzLKmU45LwQpGsPFU2vl+8dH2Fn2XWjZ38BBGKKMlE5Z4Te0iVChMbOLs0MHnEPFMfrKsgLuokmU67CGOzUxxy2XuevN9tif6fS+yQS/2kMFNf9dBdK5rTKhNOHcI/VebHc5XzSiK/9DSzKi6YJoO3G+R/aFXiRAVeXsrTDvdeBCvA14HSQu6oI3jtPMT5ZI0nApDKqz1JIlrM7VYGUYq6sUbTf2uBS7pxEOBOdVTu/bcwWeeyWEhlU9h4Jr9e8JirvWSZ75z5Ya+WluR/6pNGlO8nlom6sZQQS4XFU0FjYSrB8KcKUpMtfQAE8X8rZDMsLfS+DdvbMmkXBicabfJZjkTpYsi71dy1Z3rYDwcJC8HL94fdI/etM5tgSfgKeiBBLwCR+AdOAYjQII4GAdpcBaehZ/DL+HXy9YwaGceg40Iv/0CSPDkxQ==</latexit>

(k)
wij =

• An illustrating example

Center of Machine Learning Research

8
1
>
<2
1

>
:2
0

if log2 (mod(ji, n)) = mod(k, ⌧ )if i = jotherwise.

< 35 >

One-peer exponential graph: weight matrix• We let ⌧ = dlog2 (n)e . The weight matrix W (k) is defined as<latexit sha1_base64="xRhZsuIzPzuwrdH8CNnFtRegh7Y=">AAACGXicbVBNS8NAEN3Ur1q/qh69LBahXkqioh6LXjxWsE2hjWWz2bRLNrthdyOUkB/h1f4ab+LVkz9GcNvmYFsfDDzem2Fmnp8wqrRtf1ultfWNza3ydmVnd2//oHp41FEilZi0sWBCdn2kCKOctDXVjHQTSVDsM+L60f3Ud1+IVFTwJz1OiBejIachxUgbyXWfs3p0ng+qNbthzwBXiVOQGijQGlR/+oHAaUy4xgwp1XPsRHsZkppiRvJKP1UkQThCQ9IzlKOYKC+bnZvDM6MEMBTSFNdwpv6dyFCs1Dj2TWeM9Egte1PxP6+X6vDWyyhPUk04ni8KUwa1gNPfYUAlwZqNDUFYUnMrxCMkEdYmoYUtvhCRRr7KF1U/oHyYVyomL2c5nVXSuWg4143Lx6ta865IrgxOwCmoAwfcgCZ4AC3QBhhE4BW8gYk1sd6tD+tz3lqyipljsADr6xf5QaDm</latexit><latexit sha1_base64="5mSAww8chZeUQIbr+nfKh/KOpjA=">AAACMnicbZDLSgMxFIYzXut4q7oUJFiEuikzVdSNUHTjsoK9QKeUTJq2oZlkSM4IpXTn07i1L6M7cesrCKbtLGzrgZCf7z+Hk/xhLLgBz3t3VlbX1jc2M1vu9s7u3n724LBqVKIpq1AllK6HxDDBJasAB8HqsWYkCgWrhf37iV97ZtpwJZ9gELNmRLqSdzglYFErexIASfAtDgRlXNhLdVvFvDzHgZ6AVjbnFbxp4WXhpyKH0iq3sj9BW9EkYhKoIMY0fC+G5pBo4FSwkRskhsWE9kmXNayUJGKmOZz+Y4TPLGnjjtL2SMBT+ndiSCJjBlFoOyMCPbPoTeB/XiOBzk1zyGWcAJN0tqiTCAwKT0LBba4ZBTGwglDN7Vsx7RFNKNjo5raESvWBhGY0T8M2l92R69q8/MV0lkW1WPCvChePl7nSXZpcBh2jU5RHPrpGJfSAyqiCKHpBr+gNjZ2x8+F8Ol+z1hUnnTlCc+V8/wJZ56m1</latexit><latexit sha1_base64="QYElXaLPrnTUhEJYVujMNPYGDEw=">AAAC3nicdVFNbxMxEPUuX2X5aApHLhYpKJHaaDdUwKVSBReORSJppThsvV7vxsnaXtnelsjylRviym/iH/BjkHDSBZEWRhrp6c3Mm9GbrK6YNnH8Iwhv3Lx1+87W3eje/QcPtzs7j8ZaNorQEZGVVKcZ1rRigo4MMxU9rRXFPKvoSbZ4u6qfnFOlmRQfzLKmU45LwQpGsPFU2vl+8dH2Fn2XWjZ38BBGKKMlE5Z4Te0iVChMbOLs0MHnEPFMfrKsgLuokmU67CGOzUxxy2XuevN9tif6fS+yQS/2kMFNf9dBdK5rTKhNOHcI/VebHc5XzSiK/9DSzKi6YJoO3G+R/aFXiRAVeXsrTDvdeBCvA14HSQu6oI3jtPMT5ZI0nApDKqz1JIlrM7VYGUYq6sUbTf2uBS7pxEOBOdVTu/bcwWeeyWEhlU9h4Jr9e8JirvWSZ75z5Ya+WluR/6pNGlO8nlom6sZQQS4XFU0FjYSrB8KcKUpMtfQAE8X8rZDMsLfS+DdvbMmkXBicabfJZjkTpYsi71dy1Z3rYDwcJC8HL94fdI/etM5tgSfgKeiBBLwCR+AdOAYjQII4GAdpcBaehZ/DL+HXy9YwaGceg40Iv/0CSPDkxQ==</latexit>

(k)
wij =

• An illustrating example

Center of Machine Learning Research

8
1
>
<2
1

>
:2
0

if log2 (mod(ji, n)) = mod(k, ⌧ )if i = jotherwise.

< 36 >DSGD over one-peer exponential graph<latexit sha1_base64="EfFSiEzhNe3q/PTCxJwpyCvBU7A=">AAAEA3icbVLLbhMxFJ0kPJrh1cISCVm0lERVo0yoeAghVSAhFqgKpW2K6hDZjjNx48do7KGJLC/5AL6DHWLLh/AnLPEko7RpY2k0R/f4+p577sUJZ9o0m39L5cq16zdurlTDW7fv3L23unb/SKssJfSQKK7SY4w05UzSQ8MMp8dJSpHAnHbw6F3Od77RVDMlD8wkoV2BYskGjCDjQ7210g+IacykRZzF0oXVTQCHOkGE2u1m4xURDkCB1dh+RiLhFGx0vtraqO42gPLPAiXpdkI9oOPEY2kY4iBOUTL0eVLJTGBPQhhWx3neFhykiNjI2Zarux4Dm+ANGM9e7FnmwDaAMRICAQslwhy597UL9AVlO0K413DMzsn6XPhOoyXmumsfFfGasqSPDK0vVxXNtUCdiZ49hUwCSPZ6XpGFU5Mt5hl1Z/Nyp86BZS2dzlVEjZ1z92ptlE69Qd415P2OF6SEVUhlv5hBb3W92WhOD7gKogKsB8Vp+yF+gX1FMuH9JxxpfRI1E9O1eUnCqQthpqnXNEIxPfFQIkF11077cuCJj/TBQKX+kwZMoxczLBJaTwT2NwUyQ32Zy4PLuJPMDF52LZNJZqgks0KDjAOjQL6JoM9SSgyfeIBIyrxWQIbIm2n8vi5UwUqNDMJ6oRPb17lgF4ZQ0jOi/NZ4C+H+vrMwF4Ox3XdukSR7zs5YvxN2z7ki2wypSqmwxd/ZgwKEfhjRZeuvgqNWI3reePaptb77thjLSvAweBzUgih4EewGH4J2cBiQ0r/yo/LTcq3yvfKz8qvye3a1XCpyHgQLp/LnPzLEUZU=</latexit>

Sample W (k) over one-peer exponential graph(k+ 12 )
(k)
xi
= xi
(k+1)
xi
=

X

(k)

(k)

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

j2Ni• DSGD with time-varying weight matrix;• Per-iteration communication cost is O(1); very efficientCenter of Machine Learning Research< 37 >

One-peer exponential graph: Periodic exact average• While one-peer exponential graph is sparse, it is effective to aggregate information<latexit sha1_base64="zJ9rywh9HNPFF17gbmxQne2Lut4=">AAADQHicbVJNb9NAELXNVxO+UjhyWZEgJYAtO0LABamCC9yKSJpKcRqt12NnlfWu5R1XRJZ/Bb+Ga/kV/ANuiCviwDpNVNIypzdvdjRv3myUC67R97/bzrXrN27e2mu1b9+5e+9+Z//BkVZlwWDMlFDFcUQ1CC5hjBwFHOcF0CwSMImW75r65BQKzZUc4SqHWUZTyRPOKBpqvm8/D6XiMgaJJET4jFFSjRagCsi8mnwq81xpIL0QaUnekFCodD7sy0GPcE0oMUWO/BQIlwgpFB75gGShRKwJLii2W60wgpTLigqeyqd1KGgEokq45Agu8gxcatTRFNyMculGKl7VpmtyUvWXz0IQYlCTi8QNTBqyWKHesMG2PqiNuqSgrArqStZhRnERa5NcoJNRowdkvFVj0kQVhMrVVj/pLUmYgt8zZGy2NjObnDTru0HPm3e6vuevg1wFwQZ0rU0czjt/wlixMjP2MkG1ngZ+jrOKFsiZgLodlhpyypbGgamBkmagZ9X6rDV5YpiYNBITZc6zZv/tqGim9SqLzMtmSX251pD/q01LTF7PKi7zEkGy80FJKQgq0vwREvMCGIqVAZQV5sKMsAU15qL5Se2dMZFSS6SR3lmlinWjuDZ2BZfNuQqOhl7w0nvxcdg9eLsxbs96ZD22+lZgvbIOrPfWoTW2mP3F/mqf2d+cM+eH89P5df7UsTc9D62dcH7/BacwB20=</latexit>

Theorem. Suppose ⌧ = log2 (n) is a positive integer. It holds thatW
for any integer k

(k+`)

W

0 and `(k+` 1)

⌧

···W

(k+1)

W

(k)

1 T
= 11
n

1.

• While each realization is sparser, a sequence (with length ⌧ ) of one-peer graphs will enableeffective global averaging<latexit sha1_base64="yrM27wpi+JLkNC2RVqrw9q6uyQo=">AAACjHicbVFdaxNBFJ2sH62r1lYffVkMgk9hV4sKRSgK4lOpoWkL2VDuzt40Q+ZjmbmrhGH+gq/61/w3ziYLmtYLwxzOmcM9d27VSOEoz38Pkjt3793f2X2QPnz0eO/J/sHTc2day3HCjTT2sgKHUmickCCJl41FUJXEi2r5qdMvvqF1wugzWjU4U3CtxVxwoI4qCdqr/WE+yteV3QZFD4asr9Org4Eta8NbhZq4BOemRd7QzIMlwSWGtGwdNsCXcI3TCDUodDO/Dhuyl5Gps7mx8WjK1uy/Dg/KuZWq4ksFtHA3tY78nzZtaf5+5oVuWkLNN43mrczIZN3kWS0scpKrCIBbEbNmfAEWOMX/2epSGbMkqNzWJL52XeCQpqXG79woBbr25XgcfNmFqSo/DmFb5CfBb1QO0p+E0Ltpgcai8v0d/FkP0tIhcdPqmOmvWkRb3FJxcye3wfnrUfF29Obr4fD4Y7+vXfacvWCvWMHesWP2hZ2yCeNswX6wn+xXspccJkfJh83TZNB7nrGtSj7/ARePy8E=</latexit>

Center of Machine Learning Research< 38 >

One-peer exponential graph: Periodic exact average<latexit sha1_base64="oRHeBFdbp1EAZ8ZAvny4vLvDnu4=">AAACanicbZDNSgMxEMfT9avWr7aexEuwCnqw7KqoF8GPi0eF1grdWrLZbBs2myxJVlq2+zw+jVfFd/AhzNaC1joQ+M9vZpjM34sZVdq2PwrW3PzC4lJxubSyura+Ua5UH5RIJCZNLJiQjx5ShFFOmppqRh5jSVDkMdLywpu83nomUlHBG3oYk06EepwGFCNtULd85Y7cQCKcOlnKMzdCuu8rk/yopwYcwEPoxlL43TS8sHPSekr3w4MMDtxRt1yz6/Y44KxwJqIGJnHXrRQqri9wEhGuMUNKtR071p0USU0xI1nJTRSJEQ5Rj7SN5CgiqpOOb83gniE+DIQ0j2s4pr8nUhQpNYw805mfoP7WcvhfrZ3o4LyTUh4nmnD8vShIGNQC5sZBn0qCNRsagbCk5q8Q95GxTht7p7Z4QoQaeSqbpp5PeW+a+So/IiuVjInOX8tmxcNR3TmtH9+f1C6vJ3YWwTbYAfvAAWfgEtyCO9AEGLyAV/AG3gufVtXasra/W63CZGYTTIW1+wUpH7yH</latexit>

1 Tk• We examine n 11 xTY

W (k) xk for a vector x<latexit sha1_base64="CsxMV/5HSHh9w5Ucgwq79zh1td4=">AAACKHicbVDLSsNAFJ34rPHV6tLNYBFclURFXRbduGzBPqANZTKZtEMnM2FmIpaQL3CrP+HXuJNu/RInbRam9cCFwzn3cu89fsyo0o4ztzY2t7Z3dit79v7B4dFxtXbSVSKRmHSwYEL2faQIo5x0NNWM9GNJUOQz0vOnj7nfeyFSUcGf9SwmXoTGnIYUI22k9uuoWncazgJwnbgFqYMCrVHNqg0DgZOIcI0ZUmrgOrH2UiQ1xYxk9jBRJEZ4isZkYChHEVFeurg0gxdGCWAopCmu4UL9O5GiSKlZ5JvOCOmJWvVy8T9vkOjw3kspjxNNOF4uChMGtYD52zCgkmDNZoYgLKm5FeIJkghrE05piy/EVCNfZWXVDygfl7VA5U9ktm1CdFcjWyfdq4Z727hu39SbD0WcFXAGzsElcMEdaIIn0AIdgAEBb+AdfFif1pf1bc2XrRtWMXMKSrB+fgHqIqY9</latexit>

k=0

1 T
• n 11 x is the global average<latexit sha1_base64="ohuirUBVVUBihC4gaSjD160ux7k=">AAACS3icbVDLSsNAFJ1UqzW+Wl26CS2Cq5KoqMuiG5cV+oI2lslkUodOZsLMRCwhe7/Grf6EH+B3uBMXTtqApvXAwJlz7uXee7yIEqls+8Mora2XNzYrW+b2zu7efrV20JM8Fgh3EadcDDwoMSUMdxVRFA8igWHoUdz3pjeZ33/EQhLOOmoWYTeEE0YCgqDS0rhaHwUCosRJE5aOQqgefKk/v+y+8zSuNuymPYe1SpycNECO9rhm1EY+R3GImUIUSjl07Ei5CRSKIIpTcxRLHEE0hRM81JTBEEs3mR+TWsda8a2AC/2Ysubq344EhlLOQk9XZlvKZS8T//OGsQqu3ISwKFaYocWgIKaW4laWjOUTgZGiM00gEkTvaqEHqNNROr/CFI/zqYKeTIuq5xM2KWq+zI5ITVOH6CxHtkp6p03nonl2d95oXedxVsARqIMT4IBL0AK3oA26AIFn8AJewZvxbnwaX8b3orRk5D2HoIBS+QeLxLP+</latexit><latexit sha1_base64="q3xCelEvzGgdmvXA5pxxk917Fns=">AAACQXicbZDLSgMxFIYz9VbrrdWN4CZYhLopMyrqRii6cVmhN+iNTCZtw2SSIcmIZRifxq2+hE/hI7gTt25M21nY1h8CP985h5PzuyGjStv2h5VZWV1b38hu5ra2d3b38oX9hhKRxKSOBROy5SJFGOWkrqlmpBVKggKXkabr303qzUciFRW8psch6QZoyOmAYqQN6ucPO6EUXj/2b+ykV4PNXlzyTxP4BPv5ol22p4LLxklNEaSq9gtWoeMJHAWEa8yQUm3HDnU3RlJTzEiS60SKhAj7aEjaxnIUENWNpyck8MQQDw6ENI9rOKV/J2IUKDUOXNMZID1Si7UJ/K/WjvTguhtTHkaacDxbNIgY1AJO8oAelQRrNjYGYUnNXyEeIYmwNqnNbXGF8DVyVTJPXY/y4Tzz1OSIJJczITqLkS2bxlnZuSyfP1wUK7dpnFlwBI5BCTjgClTAPaiCOsDgGbyAV/BmvVuf1pf1PWvNWOnMAZiT9fML0AOvDw==</latexit>•

TY

W (k) x is the partial average after T iterations

k=0• One-peer exp. achieves global average after log2 (n) iters.
<latexit sha1_base64="MWKDbdpJehpYlIXAlBVAvf95Ryk=">AAACMHicbVDLSsNAFJ34rPHV6tJNsAh1U5Iq6rLoxmUF+5A2lMlkkg6dzISZiVBCvsKt/oRfoytx61c4abMwrQcuHM65l3vv8WJKpLLtT2NtfWNza7uyY+7u7R8cVmtHPckTgXAXccrFwIMSU8JwVxFF8SAWGEYexX1vepf7/WcsJOHsUc1i7EYwZCQgCCotPY0oD8etBjsfV+t2057DWiVOQeqgQGdcM2ojn6MkwkwhCqUcOnas3BQKRRDFmTlKJI4hmsIQDzVlMMLSTecXZ9aZVnwr4EIXU9Zc/TuRwkjKWeTpzgiqiVz2cvE/b5io4MZNCYsThRlaLAoSailu5e9bPhEYKTrTBCJB9K0WmkABkdIhlbZ4nE8V9GRWVj2fsLCs+TJ/IjNNHaKzHNkq6bWazlXz4uGy3r4t4qyAE3AKGsAB16AN7kEHdAECEXgBr+DNeDc+jC/je9G6ZhQzx6AE4+cXeW2pAw==</latexit>

Center of Machine Learning Research< 39 >

Apply one-peer exponential graph to DSGD

Assumption
1 (1) Each fi (x) is L-smooth; (2) Each gradient noise is unbiased
Assumption
and has bounded variance 2 ; (3) Each local distribution Di is identical (iid)<latexit sha1_base64="d9lAKfyZ6FYMC2A7/KUYlPg4RnE=">AAACJnicbVDLSsNAFJ3UV62vaJdugkVwVZIi6rLqxmUF+4A2lMlk0g6dyYSZGzGEfovb+jPuRNz5IS5M2ixs64GBwzn3cs8cL+JMg21/GaWNza3tnfJuZW//4PDIPD7paBkrQttEcql6HtaUs5C2gQGnvUhRLDxOu97kPve7z1RpJsMnSCLqCjwKWcAIhkwamtUB0BfwgvRW61hEuTgdmjW7bs9hrROnIDVUoDU0fwa+JLGgIRCOte47dgRuihUwwum0Mog1jTCZ4BHtZzTEgmo3nYefWueZ4luBVNkLwZqrfzdSLLROhJdNCgxjverl4n9eP4bgxk1ZGMVAQ7I4FMTcAmnlTVg+U5QATzKCiWJZVouMscIEsr4qS2c8KSeAPb30ldTXeeK8Lme1nHXSadSdq/rlY6PWvCuKK6NTdIYukIOuURM9oBZqI4IS9Ipm6M2YGe/Gh/G5GC0ZxU4VLcH4/gVpgqdR</latexit><latexit sha1_base64="kiQDRF17n6GtGG6IU5zh/WPQJFg=">AAADcXicbVLrbtMwFHZaLlu4dfAL8cdag9QKUTWdBEj8GTeJH2iMat2KmlLZjttYje3Il0Fl5TV4IZ6C5+AFcNpItBuWohyf71y+cz7jImfa9Pu/g0bzxs1bt/f2wzt3791/0Dp4eK6lVYSOiMylGmOkac4EHRlmcjouFEUc5/QCL99V+MUlVZpJcWZWBZ1ytBBszggy3jVr/UowXTDhkNaWF5WvDDtxF35AJIPRfMY6P7oRZBpGn6LnmktpstewM6gDFgqljAoDhWSaVmFWYObppBCJFGZIQyytSP39EimGBKEwSjRbcPRtEPlCR3WhXBKUw9TPqxi2FQ0YvZ+xdWeW+g6swjuMpd0woSLd5rs/a7X7vf76wOtGXBttUJ/T2UHwM0klsdwXJrkvNYn7hZk6pHyfnJZhYjUtEFmiBZ14UyBO9dStt13Cp7aaby6V//zoa+92hkNc6xXHPpIjk+mrWOX8HzaxZv5q6pgorKGCbBrNbQ6NhJV0fj2KEpOvvIGIYp4rJBlSiBgv8E4XLOXSIKx3JnGprgiXYZgI+p1Izr1GLhkOS5dUZDB2w7LcBclJ6Tao3787Kcs622RUKspd/S/dWW3soFsiuTdbDyzR1BD/LjzvfxViX9orGV/V7bpxPujFL3pHXwbt47e1pnvgCTgEHRCDl+AYfASnYARI0A0+B+Pga+NP83ETNg83oY2gznkEdk7z2V9o3xwY</latexit>p= O(1/ T ), let ⌧ =log2 (n) be an integer, DSGD with one-peer exponential graph will converge at<latexit sha1_base64="L+6ct7wgTLh/ZiSscWv8eQuc4Ko=">AAAERnicbVPbbtMwGE7bAaOcNrjkxmJFasXomk4CbiaNMQRXY4x2mzSvleO4qVXHDrazgzy/BrwSr8BLcIe4Q/xpu0M3LCX64u8/f3+iTHBjW62fpXJl7tbtO/N3q/fuP3j4aGHx8a5RuaasS5VQej8ihgkuWddyK9h+phlJI8H2otG7gt87YtpwJTv2NGOHKUkkH3BKLFz1F0vfccQSLp0dMqVZ6qtdGTON4BORSB3B25g8zQprg4iM0TG3Q1TDCUlTgtbQp3q4gs1XbV3HN2rLSDALrCU5cFiopN+uy0YNRRBIIi4tS5heRptfPmxOIinJXmYMMrKTDLC0nAiUaJINgRcCUSWh/gTcLapOayWCJ9JX8UAT6kIPmTHU2HejtdD3OgjhlNhhFLn3HuEzLEkkCBrUcUS0O/E9Vx81fAOf9dpF+XiDJ3U0CYUNT1Li3aQf2fH+BcJ5MY8IaOauWvVce2XVj1vsuRDguFGoZUJ433dYp9CV1QQjGKQeMhL7Il0DYalknkZMVzGT8UU/BT7Xob+w1Gq2xgfdBOEULAXTsw1SfsOxonkKM6QCVDsIW5k9dERbTgWD8LlhGaEjkrADgJKkzBy68Qp59BxuYjRQGh5p0fj2qocjqTGnaQSWxXDNda64/B93kNvBm0PHZZZbJukk0SAXyCpU7COKuWbUilMAhGoOtSI6JDBnC1s7kyVSamRJZGY6cbEpCvbVKpbsmCpYShgi3tkBFadbsOP9LEm3vJuwlAi3BVpNvKejv5DAdc7/iavs5f/g3dtLXMWGWapy2HB9GaENoUHJ8LpuN8Fuuxm+aq5+bi+tb0w1nQ+eBs+CehAGr4P14GOwHXQDWvpbrpVflpuVH5Vfld+VPxPTcmnq8ySYOXPBP62kbyw=</latexit>

Theorem
Theorem 3 Under the above assumptions and with<latexit sha1_base64="8XuT+XsD4eOz7L8rsROE6r7+wGA=">AAACI3icbVDLSsNAFJ3UV62vqEs3wSK4KkkRdVl047JCX9CGMpnetEMnmTBzUyyhf+K2/ow7cePCP3Fh0mZhWw8MHM65l3vmeJHgGm37yyhsbe/s7hX3SweHR8cn5ulZS8tYMWgyKaTqeFSD4CE0kaOATqSABp6Atjd+zPz2BJTmMmzgNAI3oMOQ+5xRTKW+afYQXtDzk8YIpIJg1jfLdsVewNokTk7KJEe9b/70BpLFAYTIBNW669gRuglVyJmAWakXa4goG9MhdFMa0gC0myySz6yrVBlYvlTpC9FaqH83EhpoPQ28dDKgONLrXib+53Vj9O/dhIdRjBCy5SE/FhZKK6vBGnAFDMU0JZQpnma12IgqyjAtq7RyxpNyjNTTK19JBjpLnNXlrJezSVrVinNbuXmulmsPeXFFckEuyTVxyB2pkSdSJ03CyIS8kjl5M+bGu/FhfC5HC0a+c05WYHz/ApY5pdQ=</latexit>

⇣
2/3
1 X
log2 (n) ⌘(k) 2
Ekrf (x̄ )k = O p
+
2/3
T
T{z
nT |
}
T

1/3

k=1

extra overhead

Novel analysis; require new tricks to utilize periodic exact average to establish tight convergence
Center of Machine Learning Research< 40 >

Static v.s. one-peer exponential graph• Convergence rate of DSGD over static and one-peer exponential graphs are•

DSGD with one-peer exp. converges as fast as static exp.; a surprising result.

• DSGD with both graphs are with the same transient iteration complexity O(n3 log22 (n))<latexit sha1_base64="lNZa1ozyZOn9QRahF4Gptu1ga5c=">AAACJHicbVDLTsJAFJ36RHwVXbppJCawIS0SdUl0405M5JFAaabTASZMZ5qZqYY0fIpb/Bl3xoUbv8SFU+hCwJNMcnLOvblnjh9RIpVtfxkbm1vbO7u5vfz+weHRsVk4aUkeC4SbiFMuOj6UmBKGm4ooijuRwDD0KW7747vUbz9jIQlnT2oSYTeEQ0YGBEGlJc8sPJRY/7JH+dCr9qslVi57ZtGu2HNY68TJSBFkaHjmTy/gKA4xU4hCKbuOHSk3gUIRRPE034sljiAawyHuaspgiKWbzKNPrQutBNaAC/2Ysubq340EhlJOQl9PhlCN5KqXiv953VgNbtyEsChWmKHFoUFMLcWttAcrIAIjRSeaQCSIzmqhERQQKd1WfumMz/lYQV8ufSUJZJp4qutyVstZJ61qxbmq1B5rxfptVlwOnIFzUAIOuAZ1cA8aoAkQeAGvYAbejJnxbnwYn4vRDSPbOQVLML5/AQiepEg=</latexit>•

The communication cost saving in one-peer exponential graph is a free lunch

Center of Machine Learning Research< 41 >

Compare one-peer exp. with other topologies<latexit sha1_base64="ojASqRPRzS+vsRlNnCAtVe6aOZI=">AAAGWXicnVRbT9swFA6sdCy7wXjcizUKKg+Nmm6MPTIYYnvY2rFykZoOOY5bLGI7sh1EZfkf7dfsbWI/ZQ9zmnJpG5iYpaon5/Z95xz7hElMpKrXf83MPijNlR/OP3IfP3n67PnC4osDyVOB8D7iMRdHIZQ4JgzvK6JifJQIDGkY48PwdDuzH55hIQlnbTVIcJfCPiM9gqCyquPF0k4Q4j5hWkEbYjpdN0CYKSwI67vXpjSGwmiBkHEDxRORxtgNaBorYimklGnfaGR0oPC5Cnu6zROL3B8YA1bBpbKFRY3YzB7Y5pR64KatLSCTHvhkzfavSkgEpOUBBeFrBgAQBCCgJBri7llqoPisgkqz6q9VCrTs+8akPj/BmUwgwrrurVOaY7kr3xQUeWTQpLgPqywLvvF5n2yND7VdYSu6J+dAkTjCumks2nox2hRcjtbmIpX/06J7wFSCnoAom3vDVGp7kEW7AiYnt6BeQeQAI7jX03BZ88EWSaCwlxmDLO9nqFBR3utpFJTzxXvv3cXlNntBpToYPjMdxik29mLYOw92zhNzZ6ljQdeT9NdM5dJnzGVs2rYvZtQNAMbxmwzXWhiLjAG/ncJk9uHIp9z/ySF7diFXitP8xWMWXW2Dqy+7NsDxwnLdqw8PmBb8kbDsjE7reOFPEHGUUrtrUAyl7Pj1RHV1NnZkE7pBKrEdxCns444VGaRYdvWQrAErVhOBHhf2xxQYam9GaEilHNDQelKoTuSkLVMW2Tqp6r3rasKSVGGGcqBeGgPFQbY8QUQERioeWAEiQbKbgE6gfQfZ3nLHYELOT21z5FgpOpIZY2Pb5U82Z1o4aHj+W+/N18by5taocfPOS+eVU3V8Z8PZdD46LWffQaUfpZ+li9LvuYvyTHm+7OauszOjmCVn7JSX/gJhiLgI</latexit>

Topology

Per-iter. Comm.

Trans. Iters. (iid scenario)

Ring
2D-Grid
2D-Torus
1
2 -RandGraph
Static Exp
One-Peer Expo

O(1)
O(1)
O(1)
O(n)
Õ(1)
O(1)

O(n7 )
Õ(n5 )O(n5 )O(n3 )
Õ(n3 )
Õ(n3 )We recommend using one-peer exponential graph in deep training.

Center of Machine Learning Research< 42 >

Exponential graphs have shorter tran. iters.
• Illustration of the tran. iters. on DSGD (momentum version) for logistic regression• DSGD over one-peer exponential graph converges faster than other topologies

Comparison over 32 nodesCenter of Machine Learning Research< 43 >

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 256 Tesla V100 GPUs

• Wall-clock time to finish 90 epochs of training; measures per-iter communication• Validation accuracy after 90 epochs of training; measures convergence rate

Center of Machine Learning Research< 44 >

One peer is not slower than static exponential graph
Image classification: ResNet-50 for ImageNet; 8 ⇥ 8 = 64 GPUs.
<latexit sha1_base64="mBJ9MtwZ6LDcSY7zE7vBToOpUFE=">AAACwHicbVHLbhMxFHWGVxleaVmysUiRWEUzKSrZIPWxYVWVqGkrZaLI47lprPgx2B5osPwbXbKFX+Jv8CQjlWm5kuWjc3zvPb43LzkzNkn+dKIHDx89frL1NH72/MXLV93tnXOjKk1hTBVX+jInBjiTMLbMcrgsNRCRc7jIl8e1fvENtGFKntlVCVNBriSbM0psoGbdnd0hziwTYPAQf8L7H3bxrNtL+sk68H2QNqCHmjidbXduskLRSoC0lBNjJmlS2qkj2jLKwcdZZaAkdEmuYBKgJKHd1K3Ne/wuMAWeKx2OtHjN/pvhiDBmJfLwUhC7MHe1mvyfNqnsfDh1TJaVBUk3jeYVx1bhehK4YBqo5asACNUseMV0QTShNsyr1SVXamlJblo/cYWpDfs4ziR8p0oIIguXjUbeZbWZPHcj79siPfFuo1LC3Yn3TbZdgNIgXHN7d9aAlhomW4my3pt3h7c4zgxYqioZfN9WGITSYZPp3b3dB+eDfrrf3/sy6B0cNTvdQm/QW/QepegjOkCf0SkaI4qu0U/0C/2OjqJFpKKvm6dRp8l5jVoR/fgL46zfRg==</latexit>

One-peer and exponential graphs converge roughly the same; but one-peer is more comm. efficientCenter of Machine Learning Research< 45 >DSGD over one-peer Exp. achieves better linear speedup<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
one-peer exp.

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

DSGD over ring has more efficient comm. than PSGD; suffers from performance degradation
DSGD over one-peer exp. graph is more comm.-efficient without performance degradation[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
Center of Machine Learning Research< 46 >

Experiments in deep training (language modeling)

Model: BERT-Large (330M parameters)
Dataset: Wikipedia (2500M words) and
BookCorpus (800M words)
Hardware: 64 GPUs
Table. Comparison in loss and training time [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

[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< 47 >

A brief summary•

Exponential graphs are both sparse and effective. They are nearly best up to logarithm terms•

One-peer exponential graph is even sparser without hurting effectiveness<latexit sha1_base64="ojASqRPRzS+vsRlNnCAtVe6aOZI=">AAAGWXicnVRbT9swFA6sdCy7wXjcizUKKg+Nmm6MPTIYYnvY2rFykZoOOY5bLGI7sh1EZfkf7dfsbWI/ZQ9zmnJpG5iYpaon5/Z95xz7hElMpKrXf83MPijNlR/OP3IfP3n67PnC4osDyVOB8D7iMRdHIZQ4JgzvK6JifJQIDGkY48PwdDuzH55hIQlnbTVIcJfCPiM9gqCyquPF0k4Q4j5hWkEbYjpdN0CYKSwI67vXpjSGwmiBkHEDxRORxtgNaBorYimklGnfaGR0oPC5Cnu6zROL3B8YA1bBpbKFRY3YzB7Y5pR64KatLSCTHvhkzfavSkgEpOUBBeFrBgAQBCCgJBri7llqoPisgkqz6q9VCrTs+8akPj/BmUwgwrrurVOaY7kr3xQUeWTQpLgPqywLvvF5n2yND7VdYSu6J+dAkTjCumks2nox2hRcjtbmIpX/06J7wFSCnoAom3vDVGp7kEW7AiYnt6BeQeQAI7jX03BZ88EWSaCwlxmDLO9nqFBR3utpFJTzxXvv3cXlNntBpToYPjMdxik29mLYOw92zhNzZ6ljQdeT9NdM5dJnzGVs2rYvZtQNAMbxmwzXWhiLjAG/ncJk9uHIp9z/ySF7diFXitP8xWMWXW2Dqy+7NsDxwnLdqw8PmBb8kbDsjE7reOFPEHGUUrtrUAyl7Pj1RHV1NnZkE7pBKrEdxCns444VGaRYdvWQrAErVhOBHhf2xxQYam9GaEilHNDQelKoTuSkLVMW2Tqp6r3rasKSVGGGcqBeGgPFQbY8QUQERioeWAEiQbKbgE6gfQfZ3nLHYELOT21z5FgpOpIZY2Pb5U82Z1o4aHj+W+/N18by5taocfPOS+eVU3V8Z8PZdD46LWffQaUfpZ+li9LvuYvyTHm+7OauszOjmCVn7JSX/gJhiLgI</latexit>

Topology

Per-iter. Comm.

Trans. Iters. (iid scenario)

Ring
2D-Grid
2D-Torus
1
2 -RandGraph
Static Exp
One-Peer Expo

O(1)
O(1)
O(1)
O(n)
Õ(1)
O(1)

O(n7 )
Õ(n5 )O(n5 )O(n3 )
Õ(n3 )
Õ(n3 )

Center of Machine Learning Research< 48 >

However …
•

Periodic exact average for one-peer exp. only holds when network size n is a power of 2•

Not known when one-peer exp. performs well when n is not a power of 2•

Not known whether the transient iteration O(n<latexit sha1_base64="lNZa1ozyZOn9QRahF4Gptu1ga5c=">AAACJHicbVDLTsJAFJ36RHwVXbppJCawIS0SdUl0405M5JFAaabTASZMZ5qZqYY0fIpb/Bl3xoUbv8SFU+hCwJNMcnLOvblnjh9RIpVtfxkbm1vbO7u5vfz+weHRsVk4aUkeC4SbiFMuOj6UmBKGm4ooijuRwDD0KW7747vUbz9jIQlnT2oSYTeEQ0YGBEGlJc8sPJRY/7JH+dCr9qslVi57ZtGu2HNY68TJSBFkaHjmTy/gKA4xU4hCKbuOHSk3gUIRRPE034sljiAawyHuaspgiKWbzKNPrQutBNaAC/2Ysubq340EhlJOQl9PhlCN5KqXiv953VgNbtyEsChWmKHFoUFMLcWttAcrIAIjRSeaQCSIzmqhERQQKd1WfumMz/lYQV8ufSUJZJp4qutyVstZJ61qxbmq1B5rxfptVlwOnIFzUAIOuAZ1cA8aoAkQeAGvYAbejJnxbnwYn4vRDSPbOQVLML5/AQiepEg=</latexit>

log22 (n)) can be further improved to O(n3 )<latexit sha1_base64="59jnINaXRizikqvJ/rC9XJuwBJs=">AAACF3icbVBNT8JAEJ3iF+IX6tFLIzHBC2mVqEeiF29iIh8JVLLdbmFlu9vsbk1Iw3/win/Gm/Hq0f/iwS1wEPQlk7y8N5OZeX7MqNKO82XlVlbX1jfym4Wt7Z3dveL+QVOJRGLSwIIJ2faRIoxy0tBUM9KOJUGRz0jLH95kfuuZSEUFf9CjmHgR6nMaUoy0kZp3Zf54ftorlpyKM4X9l7hzUoI56r3idzcQOIkI15ghpTquE2svRVJTzMi40E0UiREeoj7pGMpRRJSXTq8d2ydGCexQSFNc21P190SKIqVGkW86I6QHatnLxP+8TqLDKy+lPE404Xi2KEyYrYWdvW4HVBKs2cgQhCU1t9p4gCTC2gRUWFjjCzHUyFcLr6SByi4em7jc5XD+kuZZxb2oVO+rpdr1PLg8HMExlMGFS6jBLdShARie4AUm8GpNrDfr3fqYteas+cwhLMD6/AHtt6Ar</latexit>3

Can we develop topologies that§ have O(1) per-iteration communication cost;<latexit sha1_base64="iV70ssKbGQo7F83MLS+bL1Cle/k=">AAACFXicbVBNS8NAEN3Ur1q/qh69LBahXkoiRT0WvXizgv2ANpTNZtMu3eyG3YlQQv+C1/pnvIlXz/4XDyZtDrb1wcDjvRlm5nmR4AZs+9sqbGxube8Ud0t7+weHR+Xjk7ZRsaasRZVQuusRwwSXrAUcBOtGmpHQE6zjje8zv/PCtOFKPsMkYm5IhpIHnBLIpMeqczkoV+yaPQdeJ05OKihHc1D+6fuKxiGTQAUxpufYEbgJ0cCpYNNSPzYsInRMhqyXUklCZtxkfusUX6SKjwOl05KA5+rfiYSExkxCL+0MCYzMqpeJ/3m9GIJbN+EyioFJulgUxAKDwtnj2OeaURCTlBCqeXorpiOiCYU0ntLSGk+pMRDPLL2S+Ca7eJrG5ayGs07aVzXnulZ/qlcad3lwRXSGzlEVOegGNdADaqIWomiEXtEMvVkz6936sD4XrQUrnzlFS7C+fgFGhJ9J</latexit>§ enable DSGD to converge with O(n3 ) transient iteration complexity;<latexit sha1_base64="59jnINaXRizikqvJ/rC9XJuwBJs=">AAACF3icbVBNT8JAEJ3iF+IX6tFLIzHBC2mVqEeiF29iIh8JVLLdbmFlu9vsbk1Iw3/win/Gm/Hq0f/iwS1wEPQlk7y8N5OZeX7MqNKO82XlVlbX1jfym4Wt7Z3dveL+QVOJRGLSwIIJ2faRIoxy0tBUM9KOJUGRz0jLH95kfuuZSEUFf9CjmHgR6nMaUoy0kZp3Zf54ftorlpyKM4X9l7hzUoI56r3idzcQOIkI15ghpTquE2svRVJTzMi40E0UiREeoj7pGMpRRJSXTq8d2ydGCexQSFNc21P190SKIqVGkW86I6QHatnLxP+8TqLDKy+lPE404Xi2KEyYrYWdvW4HVBKs2cgQhCU1t9p4gCTC2gRUWFjjCzHUyFcLr6SByi4em7jc5XD+kuZZxb2oVO+rpdr1PLg8HMExlMGFS6jBLdShARie4AUm8GpNrDfr3fqYteas+cwhLMD6/AHtt6Ar</latexit>§ and are valid for any network size n?

Center of Machine Learning Research< 49 >

PART 03
EquiTopo graphs are new state-of-the-art

Why does exponential graph suffer log(n) deterioration?
•

Exponential graphs are still not well-connected•

For example, node 0 never sends messages to nodes 3 and 5•

We need to develop topologies that every pair of nodes is connected in positive probability

Center of Machine Learning Research< 51 >

Basis weight matrix and graphDefinition Given a graph of size n, we introduce a set of doubly stochastic(u,n)
basis matrices {A(u,n) }nu=11 , where A(u,n) = [aij ] 2 Rn⇥n with<latexit sha1_base64="yCqvankYTKoG2MgKHut/W0hkYs0=">AAAES3icdVNLbxMxEN4mLZTl1cKRy4gGlEKJkgpRLpVaQCrHgvqS4hB5vbOJW68d2d62wfJf4ddwLXd+BzfUA94k9JGCpZVG8/hmvm9mk4HgxjabP2cq1dm5W7fn78R3791/8HBh8dGeUYVmuMuUUPogoQYFl7hruRV4MNBI80TgfnL0vozvH6M2XMkdOxxgJ6c9yTPOqA2u7mJljUjFZYrSArF4apPMfcCMS17GPWzxY5RAoafpoA8qA8O/ItRkbQVOELi0WqUFw5Bh0JbxVBWJGIKxivWpsZyBI5hDmJEbyKnVnKHxUCNu84urFysglz3xXVest/wXJ1+1fAndRx26XGbAOrRp1/FDf+HqAOESSIDsJ4n7XBYHBjxHA9LX4ITbPsQkwR6Xjgreky88ETRB4TYLH0+BBfyYCMwscRc1WtOhd0z4mGSastFsTvoVeB66JurU8QxqPFTWD+ElFLBMgCS5SglIqIU0cmwGlKFr5bkHQiYo/8E4rHm4WdK8TFQ2aHLCDfpGTFCmk/lionmvb//6xjzjnT5yDdQYxTi1mI7XZ0rVR4IxKtyWr1/Rd3lqB0DDAkKaCMWOcDtZ4BgnjBB3F5aajebowU2jNTGWosnb7i6ck1SxIg+XxkQYrd1qDmwn0Ag3IjAQKQwG8ke0h+1gSho22XGjC/fwLHhSyJQOX7jUkfdqhaO5McM8CZklPzMdK53/irULm73tOC4HhUXJxo2yQoBVUP4ukHKNzIaDTjllmpf3HO46LNKGnyq+1iZR6sjSxFyj4lJTTuyDXK1pcW4ae6uN1pvG60+rSxvvJsLNR0+ip1E9akVr0Ub0MdqOdiNW+Vb5Xjmr/KieVX9Vf1fPx6mVmUnN4+jam537A8F0ZN0=</latexit>

8 n 1
>
< n ,
(u,n)
1
,
aij
=
n
>
:
0,

if i = (j + u) mod n,
if i = j,otherwise.

Their associated graphs {G(A(u,n) )}nu=11 are called basis graphs.

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< 52 >

Basis weight matrix and graph: illustration
The set of basis graphs {G(A(u) )}5u=1 for n = 6<latexit sha1_base64="S8udKeKY4kOPtn/wQx52ec00VQU=">AAACNnicbVDLTgIxFO34RHyhLt00EhPYkBmDj40J6kKXmMgjYYB0SoGGznTSdkxIMx/g17jFT3Hjzrj1A1zYgVkIeJKbnJx7b+65xwsZlcq2362V1bX1jc3MVnZ7Z3dvP3dwWJc8EpjUMGdcND0kCaMBqSmqGGmGgiDfY6Thje6SfuOZCEl58KTGIWn7aBDQPsVIGamby7va9ZEaYsT0fVy46ehCVIxh0Y27Orp24o4+j82UXbKngMvESUkepKh2cz9uj+PIJ4HCDEnZcuxQtTUSimJG4qwbSRIiPEID0jI0QD6RbT19JoanRunBPhemAgWn6t8NjXwpx75nJhPjcrGXiP/1WpHqX7U1DcJIkQDPDvUjBhWHSTKwRwXBio0NQVhQ4xXiIRIIK5Nfdu6Mx/lIIU/OvaJ7MnGcxOUshrNM6mcl56JUfiznK7dpcBlwDE5AATjgElTAA6iCGsDgBbyCCXizJtaH9Wl9zUZXrHTnCMzB+v4FIZqslw==</latexit>•

Each basis graph G(A(u) ) is an one-peer graph; O(1) per-iteration communication overhead•

Each edge in a basis graph has the same label difference<latexit sha1_base64="u50DKW+x/CZ+0wv/42ZqyVriWBc=">AAACJ3icbVDLTsJAFJ3iC/FVHzs3E4kJbEhriLpEXegSEwETqGQ6ncKEaaeZmZpg039xiz/jzujS/3DhFLoQ8CSTnJxzb+6Z40aMSmVZX0ZhZXVtfaO4Wdra3tndM/cP2pLHApMW5oyLRxdJwmhIWooqRh4jQVDgMtJxRzeZ33kmQlIePqhxRJwADULqU4yUlvrmUS9AaogRS27TytVTUomrabVvlq2aNQVcJnZOyiBHs2/+9DyO44CECjMkZde2IuUkSCiKGUlLvViSCOERGpCupiEKiHSSafoUnmrFgz4X+oUKTtW/GwkKpBwHrp7MsspFLxP/87qx8i+dhIZRrEiIZ4f8mEHFYVYF9KggWLGxJggLqrNCPEQCYaULK82dcTkfKeTKua8knswSp7oue7GcZdI+q9nntfp9vdy4zosrgmNwAirABhegAe5AE7QABi/gFUzAmzEx3o0P43M2WjDynUMwB+P7F/u9pmw=</latexit>

Center of Machine Learning Research< 53 >

OP-EquiDyn: One-peer dynamic graph with equivalent label differences<latexit sha1_base64="rQNjbj8/wxUsDKm8yL6FjwEea+Y=">AAACQnicbVC7TgMxEPTxJrwClDQWAQmacIcQUCIeghIkQpCSEPmcPbDisw97DxFO+Qy+hhY+gl+gQ7QU+EIKAoxkaTSz692dMJHCou+/ekPDI6Nj4xOThanpmdm54vzChdWp4VDhWmpzGTILUiiooEAJl4kBFocSqmH7IPerd2Cs0OocOwk0YnatRCQ4Qyc1ixt1hHsMo+wYFBiGQI9uU3HYUdT9IsVDr4yuVK+ytfZ6d6XbLJb8st8D/UuCPimRPk6bxc96S/M0BoVcMmtrgZ9gI2MGBZfQLdRTCwnjbXYNNUcVi8E2st5hXbrqlBaNtHFPIe2pPzsyFlvbiUNXGTO8sb+9XPzPq6UY7TYyoZIUQfHvQVEqKWqap0RbwgBH2XGEcSPcrpTfMMM4uiwLA2NCrdvIQjtwStay+cZ5XMHvcP6Si81ysF3eOtss7e33g5sgS2SZrJGA7JA9ckJOSYVw8kieyDN58Z69N+/d+/guHfL6PYtkAN7nF64TsdM=</latexit>

Generate EquiDyn realization W (k)<latexit sha1_base64="WyotnpQhRU3pQMOPzsKPAHgxkhQ=">AAAC/nicbVLLbtNAFB2bVwmPBliyuSJGSoUaxRUCNkgFFsAulUhTKQ7ReHyTjGLPWDPjtJEVqfwMO8SWX+Eb+AUWXLvhkZQrWTq6j3PunOs4T6V13e53z79y9dr1Gzs3G7du37m727x3/9jqwgjsC51qcxJzi6lU2HfSpXiSG+RZnOIgnr+p6oMFGiu1+uCWOY4yPlVyIgV3lBo3f0RKS5WgctCTYg7BYjwPYGJ0BgX1aZNBQlsYGRfVAGgiAzdDIFFpoRo9A4sOgqHaD0cBRAubc4FlmGUriKJGz+ikEL/7M05UZxC8+li2SWlvFQAXQptEqik4XTMnOJFK1mrbZG9RoeEO4RTldOb+0A2IjsjgJbTD/Qgd34P38AQqBH+lxs1Wt9OtAy6DcA1abB29cfNnlGhRZOSOSLm1w7Cbu1HJjZMixVUjKizSfnM+xSFBxTO0o7I+ygoeUyYBcpA+crfO/jtR8szaZRZTJz1jZrdrVfJ/tWHhJi9GpVR54VCJC6FJkdb20YXpXgaFS5cEuDBkpAAx44YLR/9BY0Mm1nrueGw3nlImttp4RXaF2+ZcBscHnfBZ5+nRQevw9dq4HfaQPWJtFrLn7JC9Yz3WZ8I78k69c++Tf+5/9r/4Xy9afW8984BthP/tF9+C8EY=</latexit>

Pick vk from uniform distribution over the basis index set [nProduce basis matrix A(vk ) according to the definition
Generate weight matrix W (k) = (1 ⌘)I + ⌘A(vk )1]

Sample at kCenter of Machine Learning Research< 54 >

OP-EquiDyn: One-peer dynamic graph with equivalent label differences<latexit sha1_base64="rQNjbj8/wxUsDKm8yL6FjwEea+Y=">AAACQnicbVC7TgMxEPTxJrwClDQWAQmacIcQUCIeghIkQpCSEPmcPbDisw97DxFO+Qy+hhY+gl+gQ7QU+EIKAoxkaTSz692dMJHCou+/ekPDI6Nj4xOThanpmdm54vzChdWp4VDhWmpzGTILUiiooEAJl4kBFocSqmH7IPerd2Cs0OocOwk0YnatRCQ4Qyc1ixt1hHsMo+wYFBiGQI9uU3HYUdT9IsVDr4yuVK+ytfZ6d6XbLJb8st8D/UuCPimRPk6bxc96S/M0BoVcMmtrgZ9gI2MGBZfQLdRTCwnjbXYNNUcVi8E2st5hXbrqlBaNtHFPIe2pPzsyFlvbiUNXGTO8sb+9XPzPq6UY7TYyoZIUQfHvQVEqKWqap0RbwgBH2XGEcSPcrpTfMMM4uiwLA2NCrdvIQjtwStay+cZ5XMHvcP6Si81ysF3eOtss7e33g5sgS2SZrJGA7JA9ckJOSYVw8kieyDN58Z69N+/d+/guHfL6PYtkAN7nF64TsdM=</latexit>

Generate EquiDyn realization W (k)<latexit sha1_base64="WyotnpQhRU3pQMOPzsKPAHgxkhQ=">AAAC/nicbVLLbtNAFB2bVwmPBliyuSJGSoUaxRUCNkgFFsAulUhTKQ7ReHyTjGLPWDPjtJEVqfwMO8SWX+Eb+AUWXLvhkZQrWTq6j3PunOs4T6V13e53z79y9dr1Gzs3G7du37m727x3/9jqwgjsC51qcxJzi6lU2HfSpXiSG+RZnOIgnr+p6oMFGiu1+uCWOY4yPlVyIgV3lBo3f0RKS5WgctCTYg7BYjwPYGJ0BgX1aZNBQlsYGRfVAGgiAzdDIFFpoRo9A4sOgqHaD0cBRAubc4FlmGUriKJGz+ikEL/7M05UZxC8+li2SWlvFQAXQptEqik4XTMnOJFK1mrbZG9RoeEO4RTldOb+0A2IjsjgJbTD/Qgd34P38AQqBH+lxs1Wt9OtAy6DcA1abB29cfNnlGhRZOSOSLm1w7Cbu1HJjZMixVUjKizSfnM+xSFBxTO0o7I+ygoeUyYBcpA+crfO/jtR8szaZRZTJz1jZrdrVfJ/tWHhJi9GpVR54VCJC6FJkdb20YXpXgaFS5cEuDBkpAAx44YLR/9BY0Mm1nrueGw3nlImttp4RXaF2+ZcBscHnfBZ5+nRQevw9dq4HfaQPWJtFrLn7JC9Yz3WZ8I78k69c++Tf+5/9r/4Xy9afW8984BthP/tF9+C8EY=</latexit>

Pick vk from uniform distribution over the basis index set [nProduce basis matrix A(vk ) according to the definition
Generate weight matrix W (k) = (1 ⌘)I + ⌘A(vk )<latexit sha1_base64="siEO8RFwUB+28DLR16TgdRipUXw=">AAADpXic1VJLa9tAEF5LfaTqI057LJSlpk1ORgqh7aUQ2ksvhRRiO2AJs1qN7MX7ELujgBH6Ef15/Sc99NC1o0P9KPTagYWPb+abmf2YvJLCYRz/6AXhvfsPHh49ih4/efrsuH/yfOxMbTmMuJHG3uTMgRQaRihQwk1lgalcwiRffl7nJ7dgnTD6GlcVZIrNtSgFZ+ip2Unv+4R+pFEqocRplOYwF7ph1rJV2/BNtFFaWsabpG3OW/qWxt07xKa3rmIcmkSplqZp9Le6ffaQ8t/Uu8r/bFvQRed3lFoxX2A26w/iYbwJug+SDgxIF1ez/q+0MLxWoJFL5tw0iSvMfFcUXILvWzvwQ5dsDlMPNVPgsmZzOy1945mClsb6p5Fu2D8VDVPOrVTuKxXDhdvNrclDuWmN5YesEbqqETS/G1TWkqKh60OkhbDAUa48YNwKvyvlC+adQn+u0daY3JglstxtfaUp3Hrj1tuV7JqzD8bnw+Td8OLbxeDyU2fcEXlJXpMzkpD35JJ8IVdkRHjvZ/AqOA3OwtPwa3gdju9Kg16neUG2Ipz9BhfCF0E=</latexit>

2 1
2

Sample at k+1

Center of Machine Learning Research

6
6 0
6
6 0
6
W =6 1
6 2
6
6 0
4
0

1]

0
1
2

0
0

0
0
1
2

1
2

0
0

0

1
2

1
2

0

0
0

1
2

1
2

0
0

0
0
1
2

0

3
0
7
0 7
7
1 7
2 7
7
0 7
7
0 7
5
1
2

< 55 >

OP-EquiDyn: One-peer dynamic graph with equivalent label differences<latexit sha1_base64="rQNjbj8/wxUsDKm8yL6FjwEea+Y=">AAACQnicbVC7TgMxEPTxJrwClDQWAQmacIcQUCIeghIkQpCSEPmcPbDisw97DxFO+Qy+hhY+gl+gQ7QU+EIKAoxkaTSz692dMJHCou+/ekPDI6Nj4xOThanpmdm54vzChdWp4VDhWmpzGTILUiiooEAJl4kBFocSqmH7IPerd2Cs0OocOwk0YnatRCQ4Qyc1ixt1hHsMo+wYFBiGQI9uU3HYUdT9IsVDr4yuVK+ytfZ6d6XbLJb8st8D/UuCPimRPk6bxc96S/M0BoVcMmtrgZ9gI2MGBZfQLdRTCwnjbXYNNUcVi8E2st5hXbrqlBaNtHFPIe2pPzsyFlvbiUNXGTO8sb+9XPzPq6UY7TYyoZIUQfHvQVEqKWqap0RbwgBH2XGEcSPcrpTfMMM4uiwLA2NCrdvIQjtwStay+cZ5XMHvcP6Si81ysF3eOtss7e33g5sgS2SZrJGA7JA9ckJOSYVw8kieyDN58Z69N+/d+/guHfL6PYtkAN7nF64TsdM=</latexit>

Generate EquiDyn realization W (k)<latexit sha1_base64="WyotnpQhRU3pQMOPzsKPAHgxkhQ=">AAAC/nicbVLLbtNAFB2bVwmPBliyuSJGSoUaxRUCNkgFFsAulUhTKQ7ReHyTjGLPWDPjtJEVqfwMO8SWX+Eb+AUWXLvhkZQrWTq6j3PunOs4T6V13e53z79y9dr1Gzs3G7du37m727x3/9jqwgjsC51qcxJzi6lU2HfSpXiSG+RZnOIgnr+p6oMFGiu1+uCWOY4yPlVyIgV3lBo3f0RKS5WgctCTYg7BYjwPYGJ0BgX1aZNBQlsYGRfVAGgiAzdDIFFpoRo9A4sOgqHaD0cBRAubc4FlmGUriKJGz+ikEL/7M05UZxC8+li2SWlvFQAXQptEqik4XTMnOJFK1mrbZG9RoeEO4RTldOb+0A2IjsjgJbTD/Qgd34P38AQqBH+lxs1Wt9OtAy6DcA1abB29cfNnlGhRZOSOSLm1w7Cbu1HJjZMixVUjKizSfnM+xSFBxTO0o7I+ygoeUyYBcpA+crfO/jtR8szaZRZTJz1jZrdrVfJ/tWHhJi9GpVR54VCJC6FJkdb20YXpXgaFS5cEuDBkpAAx44YLR/9BY0Mm1nrueGw3nlImttp4RXaF2+ZcBscHnfBZ5+nRQevw9dq4HfaQPWJtFrLn7JC9Yz3WZ8I78k69c++Tf+5/9r/4Xy9afW8984BthP/tF9+C8EY=</latexit>

Pick vk from uniform distribution over the basis index set [nProduce basis matrix A(vk ) according to the definition
Generate weight matrix W (k) = (1 ⌘)I + ⌘A(vk )1]

Sample at k+2

Center of Machine Learning Research< 56 >

OP-EquiDyn v.s. OP-Exponential

OP-ExpSampled in a cyclic manner
Nodes with exponential label differences can be connected

Sampled in a random manner

OP-EquiDyn
Nodes with any label differences can be connected

Center of Machine Learning Research< 57 >

OP-EquiDyn has a network-size-independent spectral gap<latexit sha1_base64="y5vtzQ0MA9JqecVdc5dN8Raqi8w=">AAADNXicbVJLb9QwEE7CqyyvLRy5DOwiFUSXzQoBF6QKqAQShyL1JTXble1MEmsdO7Wd0lWaO7+Ga/krHLghrvwBDjjbIHVbRrL0eeab+cYzpoXgxg6H3/3g0uUrV68tXe/cuHnr9p3u8t1to0rNcIspofQuJQYFl7hluRW4W2gkORW4Q6dvm/jOIWrDldy0swLHOUklTzgj1rkmy/6DSCouY5QWIotHlibVZoZKYz6o4SNasBmCkrhaIGqIuUZmMYbPyNPMQk6s5kfQ39mvVqaP6z5QhBQlatKQ6GyeTag6RFg/KPm7mQQiUqW5zfIBfEhcHRBOpB+hJfAawmej/lPgc1UJmRKxcZBY6EQUUy4rIngqn9SdSGfK8SPXQEZptV5Hx20PsApRogmrwrqS9ZwQG3eZyLN4fzM6nowAIoEtPTIH2lajunanE6GM/2lNur3hYDg3uAjCFvS81jYm3T9RrFiZu5kyQYzZC4eFHVdEW84EuuKlwYKwKUlxz0FJcjTjar7LGh45TwyJ0u64ncy9ZzMqkhszy6ljNs8x52ON83+xvdImr8YVl0VpUbJToaQUYBU0H6NdrZg5QJhbEGfAMuImY9336SzIUKWmllCz8JQqNk3HzbjC88O5CLZHg/DF4PmnUW/tTTu4Je++99Bb8ULvpbfmvfc2vC2P+V/8r/6J/y04CX4EP4Nfp9TAb3PueQsW/P4LaXQHMg==</latexit>

Theorem. Let the one-peer directed weight matrix W (k) be generated by theabove EquiDyn algorithm. If we let ⌘ = 1/2, it then holds that
p
1
2
(k)
T
⇢ = EkW1n 1n k2 n2

• Such spectral gap is independent of network size, and holds for any size n• Recall that DSGD has transient iteration complexity O(n3 (1<latexit sha1_base64="H6qlWdM1LvOgAo35OVmsoe25FOM=">AAACJnicbVDLTgIxFO3gC/E1ytLNRGICC8gMEnVJdONOTOSR8EqndKCh007ajgmZzLe4xZ9xZ4w7P8SFHZiFgCdpcnLOvbmnxw0okcq2v4zM1vbO7l52P3dweHR8Yp6etSQPBcJNxCkXHRdKTAnDTUUUxZ1AYOi7FLfd6X3it1+wkISzZzULcN+HY0Y8gqDS0tDMPxbZ4KrolHtiwkuDqFyNS0OzYFfsBaxN4qSkAFI0huZPb8RR6GOmEIVSdh07UP0ICkUQxXGuF0ocQDSFY9zVlEEfy360CB9bl1oZWR4X+jFlLdS/GxH0pZz5rp70oZrIdS8R//O6ofJu+xFhQagwQ8tDXkgtxa2kCWtEBEaKzjSBSBCd1UITKCBSuq/cyhmX86mCrlz5SjSSSeJY1+Wsl7NJWtWKc12pPdUK9bu0uCw4BxegCBxwA+rgATRAEyAwA69gDt6MufFufBify9GMke7kwQqM719CyqTn</latexit><latexit sha1_base64="/eG/KTrpTrveS4xRgiZwFo7VD9A=">AAACJHicbVDLTgIxFO34RHyBLt00EhNXOEOIujEhunGJiTwShpBO6UBDZzq2dzRkMp/iFn/GnXHhxi9xYQdYCHiSJifn3Jt7erxIcA22/WWtrW9sbm3ndvK7e/sHh4XiUVPLWFHWoFJI1faIZoKHrAEcBGtHipHAE6zlje4yv/XMlOYyfIRxxLoBGYTc55SAkXqFoquGEt9gVz8pSCrpRaVXKNllewq8Spw5KaE56r3Cj9uXNA5YCFQQrTuOHUE3IQo4FSzNu7FmEaEjMmAdQ0MSMN1NptFTfGaUPvalMi8EPFX/biQk0HoceGYyIDDUy14m/ud1YvCvuwkPoxhYSGeH/FhgkDjrAfe5YhTE2BBCFTdZMR0SRSiYtvILZzwpR0A8vfCVpK+zxKmpy1kuZ5U0K2Xnslx9qJZqt/PicugEnaJz5KArVEP3qI4aiKIX9Iom6M2aWO/Wh/U5G12z5jvHaAHW9y8+ZqT+</latexit>• Substituting ⇢ =Center of Machine Learning Researchp⇢) 2 )

2/2 , DSGD over OP-EquiDyn has tran. iters. O(n3 )<latexit sha1_base64="59jnINaXRizikqvJ/rC9XJuwBJs=">AAACF3icbVBNT8JAEJ3iF+IX6tFLIzHBC2mVqEeiF29iIh8JVLLdbmFlu9vsbk1Iw3/win/Gm/Hq0f/iwS1wEPQlk7y8N5OZeX7MqNKO82XlVlbX1jfym4Wt7Z3dveL+QVOJRGLSwIIJ2faRIoxy0tBUM9KOJUGRz0jLH95kfuuZSEUFf9CjmHgR6nMaUoy0kZp3Zf54ftorlpyKM4X9l7hzUoI56r3idzcQOIkI15ghpTquE2svRVJTzMi40E0UiREeoj7pGMpRRJSXTq8d2ydGCexQSFNc21P190SKIqVGkW86I6QHatnLxP+8TqLDKy+lPE404Xi2KEyYrYWdvW4HVBKs2cgQhCU1t9p4gCTC2gRUWFjjCzHUyFcLr6SByi4em7jc5XD+kuZZxb2oVO+rpdr1PLg8HMExlMGFS6jBLdShARie4AUm8GpNrDfr3fqYteas+cwhLMD6/AHtt6Ar</latexit>< 58 >

OP-EquiDyn has a network-size-independent spectral gap<latexit sha1_base64="oRHeBFdbp1EAZ8ZAvny4vLvDnu4=">AAACanicbZDNSgMxEMfT9avWr7aexEuwCnqw7KqoF8GPi0eF1grdWrLZbBs2myxJVlq2+zw+jVfFd/AhzNaC1joQ+M9vZpjM34sZVdq2PwrW3PzC4lJxubSyura+Ua5UH5RIJCZNLJiQjx5ShFFOmppqRh5jSVDkMdLywpu83nomUlHBG3oYk06EepwGFCNtULd85Y7cQCKcOlnKMzdCuu8rk/yopwYcwEPoxlL43TS8sHPSekr3w4MMDtxRt1yz6/Y44KxwJqIGJnHXrRQqri9wEhGuMUNKtR071p0USU0xI1nJTRSJEQ5Rj7SN5CgiqpOOb83gniE+DIQ0j2s4pr8nUhQpNYw805mfoP7WcvhfrZ3o4LyTUh4nmnD8vShIGNQC5sZBn0qCNRsagbCk5q8Q95GxTht7p7Z4QoQaeSqbpp5PeW+a+So/IiuVjInOX8tmxcNR3TmtH9+f1C6vJ3YWwTbYAfvAAWfgEtyCO9AEGLyAV/AG3gufVtXasra/W63CZGYTTIW1+wUpH7yH</latexit>

1 Tk• We examine n 11 xTY

W (k) xk for a vector x<latexit sha1_base64="CsxMV/5HSHh9w5Ucgwq79zh1td4=">AAACKHicbVDLSsNAFJ34rPHV6tLNYBFclURFXRbduGzBPqANZTKZtEMnM2FmIpaQL3CrP+HXuJNu/RInbRam9cCFwzn3cu89fsyo0o4ztzY2t7Z3dit79v7B4dFxtXbSVSKRmHSwYEL2faQIo5x0NNWM9GNJUOQz0vOnj7nfeyFSUcGf9SwmXoTGnIYUI22k9uuoWncazgJwnbgFqYMCrVHNqg0DgZOIcI0ZUmrgOrH2UiQ1xYxk9jBRJEZ4isZkYChHEVFeurg0gxdGCWAopCmu4UL9O5GiSKlZ5JvOCOmJWvVy8T9vkOjw3kspjxNNOF4uChMGtYD52zCgkmDNZoYgLKm5FeIJkghrE05piy/EVCNfZWXVDygfl7VA5U9ktm1CdFcjWyfdq4Z727hu39SbD0WcFXAGzsElcMEdaIIn0AIdgAEBb+AdfFif1pf1bc2XrRtWMXMKSrB+fgHqIqY9</latexit>

k=0•

OP-EquiDyn has a network-size-independent rate•

While network size increases, consensus rate remains
almost unchanged

Center of Machine Learning Research< 59 >

OP-EquiDyn achieves new SOTA results
DSGD with different network topology<latexit sha1_base64="biDwsDzcGvfwNd3AuzHkHo8tDa4=">AAAGzXicnZRbUxMxFIAXpBXXG+ijLxkpTHnoTreK+IhcRB+0FQs4QyqTzaYlwyZZkyxDZ42v/iZ/iv/FB7Pd0tILIGZmZ7Pn9p2ckz1BHFGlq9XfM7N35grFu/P33PsPHj56vLD45ECJRGKyj0Uk5JcAKRJRTvY11RH5EkuCWBCRw+B0K9MfnhGpqOBN3Y1Ji6EOp22Kkbai48W5XzAgHcpTjayLOWq5EBOuiaS84w5VSYSkSSXGxoVaxDKJiAtZEmlqU0gYT32TYpNCTc510E6bIrbkTtcYsAIuhA0iK9RG9sCWYMwDl3VNibjywHurtq8ypSFQNg8kqVg1AAAIAWQ07HH3bGpg+loBpXrZXy1NkfKv6+PyfMEzFSNM0qq3xljOcpc/ayRzT1hnpIPKPHO+9HmbaLXtyq60J7plzlDTKCRp3Vja2nTaBC6nNYVM1P+U6BaYEmxLhLO+10ypsod4uCtRfHIFdYDIAX3ci0lcVnywSWMk7WUmIIv7AWk8Le6wG1OO89F7412Xy1X6KSdNYe83S4MoIcZeDHvnwc55bK496ojTsJP+qild2IyYjHTb1sX0qwHAKL/OSaVBiMwyEFenMB691/IJ8xtzsPwBXpLQ1L1KwwM73xK63eX/Qs+cboT3jYZMGAitBcunDOHhYAINvuyoAscLS1Wv2ltgcuP3N0tOfzWOF/7AUOCE2fmGI6TUkV+NdSvNrhq2AV2YKGKbf4o65MhuOWJEtdJejgYsW0kI2kLah2vQk172SBFTqssCa8mQPlHjukw4TXeU6PbrVkp5nGjCcQ5qJxHQAmQDG4RUEqyjrt0gLGl2+/AJsv9eNivdEUwgxKktjho5ShqqLGNjy+WPF2dyc1Dz/Ffey0+1pY3NfuHmnWfOc6fs+M66s+G8cxrOvoMLoPC2UC80ivViUvxe/JGbzs70fZ46I6v48y8JPdY8</latexit>

Topology

Per-iter. Comm.

Trans. Iters. (iid scenario)

Ring
2D-Grid
2D-Torus
1
2 -RandGraph
Static Exp
One-Peer Expo
O.-P. EquiDyn

O(1)
O(1)
O(1)
O(n)
Õ(1)
O(1)
O(1)

O(n7 )
Õ(n5 )O(n5 )O(n3 )
Õ(n3 )
Õ(n3 )O(n3 )•

OP-EquiDyn achieves O(1) comm., O(n3 ) transient iteration complexity, and holds for any size n•

Since DSGD has a transient complexity as O(n (1<latexit sha1_base64="59jnINaXRizikqvJ/rC9XJuwBJs=">AAACF3icbVBNT8JAEJ3iF+IX6tFLIzHBC2mVqEeiF29iIh8JVLLdbmFlu9vsbk1Iw3/win/Gm/Hq0f/iwS1wEPQlk7y8N5OZeX7MqNKO82XlVlbX1jfym4Wt7Z3dveL+QVOJRGLSwIIJ2faRIoxy0tBUM9KOJUGRz0jLH95kfuuZSEUFf9CjmHgR6nMaUoy0kZp3Zf54ftorlpyKM4X9l7hzUoI56r3idzcQOIkI15ghpTquE2svRVJTzMi40E0UiREeoj7pGMpRRJSXTq8d2ydGCexQSFNc21P190SKIqVGkW86I6QHatnLxP+8TqLDKy+lPE404Xi2KEyYrYWdvW4HVBKs2cgQhCU1t9p4gCTC2gRUWFjjCzHUyFcLr6SByi4em7jc5XD+kuZZxb2oVO+rpdr1PLg8HMExlMGFS6jBLdShARie4AUm8GpNrDfr3fqYteas+cwhLMD6/AHtt6Ar</latexit>

Center of Machine Learning Research<latexit sha1_base64="H6qlWdM1LvOgAo35OVmsoe25FOM=">AAACJnicbVDLTgIxFO3gC/E1ytLNRGICC8gMEnVJdONOTOSR8EqndKCh007ajgmZzLe4xZ9xZ4w7P8SFHZiFgCdpcnLOvbmnxw0okcq2v4zM1vbO7l52P3dweHR8Yp6etSQPBcJNxCkXHRdKTAnDTUUUxZ1AYOi7FLfd6X3it1+wkISzZzULcN+HY0Y8gqDS0tDMPxbZ4KrolHtiwkuDqFyNS0OzYFfsBaxN4qSkAFI0huZPb8RR6GOmEIVSdh07UP0ICkUQxXGuF0ocQDSFY9zVlEEfy360CB9bl1oZWR4X+jFlLdS/GxH0pZz5rp70oZrIdS8R//O6ofJu+xFhQagwQ8tDXkgtxa2kCWtEBEaKzjSBSBCd1UITKCBSuq/cyhmX86mCrlz5SjSSSeJY1+Wsl7NJWtWKc12pPdUK9bu0uCw4BxegCBxwA+rgATRAEyAwA69gDt6MufFufBify9GMke7kwQqM719CyqTn</latexit>

3) , the order O(n ) cannot be improved<latexit sha1_base64="59jnINaXRizikqvJ/rC9XJuwBJs=">AAACF3icbVBNT8JAEJ3iF+IX6tFLIzHBC2mVqEeiF29iIh8JVLLdbmFlu9vsbk1Iw3/win/Gm/Hq0f/iwS1wEPQlk7y8N5OZeX7MqNKO82XlVlbX1jfym4Wt7Z3dveL+QVOJRGLSwIIJ2faRIoxy0tBUM9KOJUGRz0jLH95kfuuZSEUFf9CjmHgR6nMaUoy0kZp3Zf54ftorlpyKM4X9l7hzUoI56r3idzcQOIkI15ghpTquE2svRVJTzMi40E0UiREeoj7pGMpRRJSXTq8d2ydGCexQSFNc21P190SKIqVGkW86I6QHatnLxP+8TqLDKy+lPE404Xi2KEyYrYWdvW4HVBKs2cgQhCU1t9p4gCTC2gRUWFjjCzHUyFcLr6SByi4em7jc5XD+kuZZxb2oVO+rpdr1PLg8HMExlMGFS6jBLdShARie4AUm8GpNrDfr3fqYteas+cwhLMD6/AHtt6Ar</latexit>

⇢)

2

3

< 60 >

OP-EquiDyn can also accelerate other decentralized methods

Gradient tracking

Center of Machine Learning Research< 61 >

Experiments: compare with other topologies•

We compare consensus rate (i.e., spectral gap)
between various topologies•

Network size is 4900•

EquiDyn converges the fastest

Center of Machine Learning Research< 62 >

Experiments: gradient tracking with different topologies•

We use GT to solve logistic regression with nonconvex regularizes•

Network size is 300•

GT with EquiDyn converges faster than OP-Exp

Center of Machine Learning Research< 63 >

Experiments: deep learning experiments•

EquiTopo graph has many variants, i.e., OU-EquiDyn supports undirected graphs•

EquiTopo graph outperforms other common topologies with 17 GPUs

Center of Machine Learning Research< 64 >

Summary
Can we develop topologies that§ have O(1) per-iteration communication cost;<latexit sha1_base64="iV70ssKbGQo7F83MLS+bL1Cle/k=">AAACFXicbVBNS8NAEN3Ur1q/qh69LBahXkoiRT0WvXizgv2ANpTNZtMu3eyG3YlQQv+C1/pnvIlXz/4XDyZtDrb1wcDjvRlm5nmR4AZs+9sqbGxube8Ud0t7+weHR+Xjk7ZRsaasRZVQuusRwwSXrAUcBOtGmpHQE6zjje8zv/PCtOFKPsMkYm5IhpIHnBLIpMeqczkoV+yaPQdeJ05OKihHc1D+6fuKxiGTQAUxpufYEbgJ0cCpYNNSPzYsInRMhqyXUklCZtxkfusUX6SKjwOl05KA5+rfiYSExkxCL+0MCYzMqpeJ/3m9GIJbN+EyioFJulgUxAKDwtnj2OeaURCTlBCqeXorpiOiCYU0ntLSGk+pMRDPLL2S+Ca7eJrG5ayGs07aVzXnulZ/qlcad3lwRXSGzlEVOegGNdADaqIWomiEXtEMvVkz6936sD4XrQUrnzlFS7C+fgFGhJ9J</latexit>§ enable DSGD to converge with O(n3 ) transient iteration complexity;<latexit sha1_base64="59jnINaXRizikqvJ/rC9XJuwBJs=">AAACF3icbVBNT8JAEJ3iF+IX6tFLIzHBC2mVqEeiF29iIh8JVLLdbmFlu9vsbk1Iw3/win/Gm/Hq0f/iwS1wEPQlk7y8N5OZeX7MqNKO82XlVlbX1jfym4Wt7Z3dveL+QVOJRGLSwIIJ2faRIoxy0tBUM9KOJUGRz0jLH95kfuuZSEUFf9CjmHgR6nMaUoy0kZp3Zf54ftorlpyKM4X9l7hzUoI56r3idzcQOIkI15ghpTquE2svRVJTzMi40E0UiREeoj7pGMpRRJSXTq8d2ydGCexQSFNc21P190SKIqVGkW86I6QHatnLxP+8TqLDKy+lPE404Xi2KEyYrYWdvW4HVBKs2cgQhCU1t9p4gCTC2gRUWFjjCzHUyFcLr6SByi4em7jc5XD+kuZZxb2oVO+rpdr1PLg8HMExlMGFS6jBLdShARie4AUm8GpNrDfr3fqYteas+cwhLMD6/AHtt6Ar</latexit>§ and are valid for any network size n?

One-peer EquiDyn is the answer!

Center of Machine Learning Research< 65 >

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< 67 >

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< 68 >

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< 69 >

Easy-to-use
Abundant documents

Center of Machine Learning Research< 70 >

Easy-to-use
Detailed tutorials

Center of Machine Learning Research< 71 >

Final summary•

Decentralized algorithms save remarkable communication compared to centralized ones•

Sparse and effective topologies make decentralized optimization practical for deep training•

We propose static exponential, one-peer exponential, and one-peer EquiDyn and justify
their superiority with strong theoretical and experimental evidences•

We introduced BlueFog to facilitate research and implementation of decentralized methods

Center of Machine Learning Research< 72 >

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