Lower Bounds and Accelerated Algorithms in Distributed
Optimization with Communication Compression
Kun Yuan (袁 坤)Center for Machine Learning Research @ Peking University

May 15, 2023

Joint work with

Yutong He(Peking U.)

Center of Machine Learning Research

Xinmeng Huang(UPenn)Yiming Chen
(Alibaba)

Wotao Yin
(Alibaba)<2>

PART 01
Basics and Motivation

Training deep neural network is notoriously difficult

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

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

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

min

x2Rd

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

where

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

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

Center of Machine Learning Research<5>

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

(k)

(k)

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

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

(k)
⇠i

•

Each node i samples data•

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

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

Vanilla parallel stochastic gradient descent (PSGD)•

Each node sends a full model (or gradient) to the server; proportional to dimension d•When model dimension d 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? Distributed optimization with communication compression

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>Ccommunication 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<9>Ccommunication 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< 10 >

Ccommunication compression algorithms• There are extensive studies in distributed learning with communication compression

Compressor

StaticQuant

AdaptQuant

Random-K

Top-K

……

Algorithm
development

Compressmodel

Compress
gradient

Compressdifference

Error
feedback……

• The combination of different compressors, algorithms, and strategies gives rise to
Q-SGD [Alistarh et. al., 2017], Mem-SGD [Stich et. al., 2018], EF21-SGD [Fatkhullin et. al., 2021],
CSER [Xie et.al., 2020], Double Squeeze [Tang et. al., 2019], Artemis [Philippenko et.al. 2022], etc.

Center of Machine Learning Research< 11 >

Fundamental open questions• What is the optimal complexity in distributed optimization with
communication compression?

• Can we develop effective algorithms that can attain the optimal
complexity?

Center of Machine Learning Research< 12 >

PART 02
Optimal Complexity Formulation

Function class and gradient oracle class• Function class. We let Fµ,L denote the set of all functions satisfying Assumption 1<latexit sha1_base64="BjvkIoJDDoOoG+LfgkBQ3IFQpzU=">AAAB/HicbVDLSsNAFJ3UV62vaJduBovgQkoiRV0WBXHhooJ9QBPCZDpph04mYWYihBB/xY0LRdz6Ie78GydtFtp6YOBwzr3cM8ePGZXKsr6Nysrq2vpGdbO2tb2zu2fuH/RklAhMujhikRj4SBJGOekqqhgZxIKg0Gek70+vC7//SISkEX9QaUzcEI05DShGSkueWXdCpCYYsewm9zInTE7vcs9sWE1rBrhM7JI0QImOZ345owgnIeEKMyTl0LZi5WZIKIoZyWtOIkmM8BSNyVBTjkIi3WwWPofHWhnBIBL6cQVn6u+NDIVSpqGvJ4uoctErxP+8YaKCSzejPE4U4Xh+KEgYVBEsmoAjKghWLNUEYUF1VognSCCsdF81XYK9+OVl0jtr2ufN1n2r0b4q66iCQ3AEToANLkAb3IIO6AIMUvAMXsGb8WS8GO/Gx3y0YpQ7dfAHxucP6aqU8w==</latexit>

Assumption 1 (Smoothness and Strong Convexity)

Each local objective fi has L(0)Lipschitz gradient and µ-strongly
convex.
Moreover,weassume
that
f
(x
)
P
n
inf x2Rd f (x)  with f = n1 i=1 fi .
<latexit sha1_base64="rYDByP0UcOwSsvrFG05pj+dw3gE=">AAACxHicbVFdb9MwFHXC1ygfK/DIyxUNUivRKJlg8DJpfIqHIQ1Et0lNGzmO05g5dmY7XYsVfiRviD+D2/UBNq5k6ejca/vcc7KaM22i6JfnX7t+4+atrdudO3fv3d/uPnh4pGWjCB0RyaU6ybCmnAk6MsxwelIriquM0+Ps9O2qfzynSjMpvpplTScVnglWMIKNo9Lu76TUNSbU7oYvSNXCe0xK4JJgDjL7RolhcwpBkVrWBlBiDcFBMDxgtSYlM99hpnDOqDCARQ5BUjXBUBslxYwvgUgxp4sQPklFpdPwDM4pYK2bioIpsYFOUPQXU9uPBu1gmDBRQGoX4AAkFTZlltkv7dTmbQtubpBwegbJO8oNDuCcmdLJ2ksKhYmNWyvaxD3sZO7F7VRAkbIgTLu9KIzWBVdBvAE9tKnDtPszySVx+oQh3Ckdx1FtJhYrwwinbSdpNHVmneIZHTsocEX1xK5DaOGpY3IopHLHGbJm/75hcaX1ssrc5Go7fbm3Iv/XGzemeDWxTNSNoYJcfFQ0HIyEVaKQM+VycobnDBPFnFYgJXa+GJd7x5kQX175KjjaCePd8Pnnnd7+m40dW+gxeoL6KEYv0T76iA7RCBHvtTfzau/M/+BzX/vNxajvbe48Qv+U/+MPhnnY+Q==</latexit>• Gradient oracle class. Each worker accesses local gradient rfi (x) via a stochastic oracle
Assumption 2 (Stochastic gradient) The gradient oracles {Oi : 1  i  n} satisfy
E⇣i [Oi (x; ⇣i )] = rfi (x)Center of Machine Learning ResearchandE⇣i [kOi (x; ⇣i )rfi (x)k2 ] 2,

8 x 2 Rd .

< 14 >

Compressor Class• Compressor class. Most compressors in literature are either unbiased or contractive• We let U! denote the set of unbiased compressors satisfying Assumption 3
Assump. 3 (Unbiased compressor)

E[C(x)] = x,

The compression operator C : Rd ! Rd satisfies

E[kC(x)xk2 ]  !kxk2 ,8 x 2 Rdfor constant !
0, where the expectation is taken over the randomness of the compression operator C.

• Identity operator I (i.e. no compression) is an unbiased compressor with ! = 0 .
Center of Machine Learning Research< 15 >Example: random quantization• Random quantization with 5 levels:

E[Q] = 0.6 × 0.5 + 0.4 * 0.75 = 0.6

Unbiased:Center of Machine Learning Research< 16 >

Compressor Class• Compressor class. Most compressors in literature are either unbiased or contractive• We let C denote the set of unbiased compressors satisfying Assumption 4
Assump. 4 (Contractive compressor)

E[kC(x)The compression operator C : Rd ! Rd satisfies

xk2 ]  (1)kxk2 ,

8 x 2 Rdfor constant 2 (0, 1], where the expectation is taken over the randomness of thecompression operator C.

• Identity operator I (i.e. no compression) is a contractive compressor withCenter of Machine Learning Research= 1.
< 17 >Example: Top-K compressor• Top-K:

Top-K Compressor

Contractive:, i.e.,

Center of Machine Learning Research< 18 >

Algorithm Class• Workers communicate directed with a central server. All iterations are synchronized.
• Each worker i 2 {1, · · · , n} is endowed with Ci .
• Zero-respecting property: # non-zeros increase only by local update or comm. with the server

C1 (·)

Center of Machine Learning Research

C2 (·)

C3 (·)

Complexity metric• Let x̂tA denote the output of algorithm A after t communication rounds<latexit sha1_base64="8LDCyLyGgM4bNtkT9KFX2nN5yNQ=">AAAB8nicbVBNSwMxEM3Wr1q/qh69BIvgqexKUY9VLx4r2A/YriWbZtvQbLIks2JZ+jO8eFDEq7/Gm//GtN2Dtj4YeLw3w8y8MBHcgOt+O4WV1bX1jeJmaWt7Z3evvH/QMirVlDWpEkp3QmKY4JI1gYNgnUQzEoeCtcPRzdRvPzJtuJL3ME5YEJOB5BGnBKzkd4cEsqdJ7+oBeuWKW3VnwMvEy0kF5Wj0yl/dvqJpzCRQQYzxPTeBICMaOBVsUuqmhiWEjsiA+ZZKEjMTZLOTJ/jEKn0cKW1LAp6pvycyEhszjkPbGRMYmkVvKv7n+SlEl0HGZZICk3S+KEoFBoWn/+M+14yCGFtCqOb2VkyHRBMKNqWSDcFbfHmZtM6q3nm1dler1K/zOIroCB2jU+ShC1RHt6iBmogihZ7RK3pzwHlx3p2PeWvByWcO0R84nz+GDJFs</latexit>• We define the complexity metric as<latexit sha1_base64="sSzQfgzVDwHMyB9gwuPpguS/5wA=">AAACZnicbVFda9RAFJ3Er3bVuraID74MLkIW6pJIUREKrUXwSSp028JOGiazk91LJ5M4cyO7DPmTvvnsiz/DyXYVbb0wcDj3Hs69Z/JagcU4/h6Et27fuXtvY7N3/8HDrUf9x9untmqMkGNRqcqc59xKBVqOEVDJ89pIXuZKnuWXR13/7Ks0Fip9gstapiWfaShAcPRU1m9PMiZrC6rSNDrcZS4qMtg9ymDI2szBftJe6CHdZyVopmSBzCEDTVnJcZ7n7lP77g/+0E6KiM05ukV7gdnhMH3ZybIFLaLF0Ku/0N9WzMBsjt6hP4hH8aroTZCswYCs6zjrf2PTSjSl1CgUt3aSxDWmjhsEoWTbY42VNReXfCYnHmpeSpu6VUwtfeGZKS0q459GumL/VjheWrsscz/ZnWSv9zryf71Jg8Xb1IGuG5RaXBkVjaJY0S5zOgUjBaqlB1wY8LtSMeeGC/Q/0/MhJNdPvglOX42S16O9z3uDg/frODbIM/KcRCQhb8gB+UiOyZgI8iPYDLaDneBnuBU+CZ9ejYbBWrND/qmQ/gLet7g7</latexit>nT✏ (A, {(fi , Ci )}ni=1 ) = min t 2 N : E[f (x̂tA )]min f (x)  ✏xo• It indicates the smallest number of iterations to achieve an ✏ - accurate solution<latexit sha1_base64="pxCsljL5+1ZnkmpQIdJjuiELoIU=">AAAB73icbVBNS8NAEJ3Ur1q/qh69LBbBU0mkqMeiF48V7Ae0oWy2k3bpZhN3N0IJ/RNePCji1b/jzX/jts1BWx8MPN6bYWZekAiujet+O4W19Y3NreJ2aWd3b/+gfHjU0nGqGDZZLGLVCahGwSU2DTcCO4lCGgUC28H4dua3n1BpHssHM0nQj+hQ8pAzaqzU6WGiuYhlv1xxq+4cZJV4OalAjka//NUbxCyNUBomqNZdz02Mn1FlOBM4LfVSjQllYzrErqWSRqj9bH7vlJxZZUDCWNmShszV3xMZjbSeRIHtjKgZ6WVvJv7ndVMTXvsZl0lqULLFojAVxMRk9jwZcIXMiIkllClubyVsRBVlxkZUsiF4yy+vktZF1bus1u5rlfpNHkcRTuAUzsGDK6jDHTSgCQwEPMMrvDmPzovz7nwsWgtOPnMMf+B8/gBPv5Ap</latexit>

Center of Machine Learning Research< 20 >

Find optimal complexity• The problem to find optimal complexity can be formulated into the problem<latexit sha1_base64="1LAOwxAqmbwyBnQO/Ic85i/rSNo=">AAACv3ichVFda9swFJW9bmuzj2bbY19EwyCFEOxS2j1s0Cww9jBoB01biFIjK9epiCRrkjwIwn9yD4P9m8lp+rG2sAtCh3PP0f1QrgW3Lkn+RPGTtafPnq9vtF68fPV6s/3m7aktK8NgxEpRmvOcWhBcwchxJ+BcG6AyF3CWz4dN/uwnGMtLdeIWGiaSzhQvOKMuUFn7N+GqyPwgXJhI6i4ZFX5Q15jYSmee+GHGSZ15/imtL1QgcwsOfuBb8bCur7VHj2tvpEchSSyfSXqxe6dE8R/bl8Ymq9634DnJCGjLRalwd9AjvhvMvdDjzu0LO7jVytqdpJ8sAz8E6Qp00CqOs/YvMi1ZJUE5Jqi14zTRbuKpcZwJqFuksqApm9MZjANUVIKd+OX+a/w+MFNclCYc5fCSvevwVFq7kHlQNjPZ+7mGfCw3rlzxYeK50pUDxa4KFZXArsTNZ+IpN8CcWARAmeGhV8wuqaHMhS9vlpDeH/khON3tp/v9ve97ncPPq3Wsoy20jbooRQfoEH1Fx2iEWPQxyqN5JOJBPItVrK+kcbTyvEP/RLz4CxSp3PE=</latexit>

inf

sup

A2A {Ci }n

sup

sup

n
n
i=1 ✓C {Oi }i=1 ✓O 2 {fi }i=1 ✓Fµ,L

T✏ (A, {(fi , Ci )}ni=1 )• In other words, given a class of functions Fµ,L , gradient oracles O 2 , compressors C ( being C or U! ),<latexit sha1_base64="BjvkIoJDDoOoG+LfgkBQ3IFQpzU=">AAAB/HicbVDLSsNAFJ3UV62vaJduBovgQkoiRV0WBXHhooJ9QBPCZDpph04mYWYihBB/xY0LRdz6Ie78GydtFtp6YOBwzr3cM8ePGZXKsr6Nysrq2vpGdbO2tb2zu2fuH/RklAhMujhikRj4SBJGOekqqhgZxIKg0Gek70+vC7//SISkEX9QaUzcEI05DShGSkueWXdCpCYYsewm9zInTE7vcs9sWE1rBrhM7JI0QImOZ345owgnIeEKMyTl0LZi5WZIKIoZyWtOIkmM8BSNyVBTjkIi3WwWPofHWhnBIBL6cQVn6u+NDIVSpqGvJ4uoctErxP+8YaKCSzejPE4U4Xh+KEgYVBEsmoAjKghWLNUEYUF1VognSCCsdF81XYK9+OVl0jtr2ufN1n2r0b4q66iCQ3AEToANLkAb3IIO6AIMUvAMXsGb8WS8GO/Gx3y0YpQ7dfAHxucP6aqU8w==</latexit>

the formulation seeks the optimal algorithm and the convergence complexity it has.

Center of Machine Learning ResearchFind optimal complexity• The problem to find optimal complexity can be formulated into the problem<latexit sha1_base64="1LAOwxAqmbwyBnQO/Ic85i/rSNo=">AAACv3ichVFda9swFJW9bmuzj2bbY19EwyCFEOxS2j1s0Cww9jBoB01biFIjK9epiCRrkjwIwn9yD4P9m8lp+rG2sAtCh3PP0f1QrgW3Lkn+RPGTtafPnq9vtF68fPV6s/3m7aktK8NgxEpRmvOcWhBcwchxJ+BcG6AyF3CWz4dN/uwnGMtLdeIWGiaSzhQvOKMuUFn7N+GqyPwgXJhI6i4ZFX5Q15jYSmee+GHGSZ15/imtL1QgcwsOfuBb8bCur7VHj2tvpEchSSyfSXqxe6dE8R/bl8Ymq9634DnJCGjLRalwd9AjvhvMvdDjzu0LO7jVytqdpJ8sAz8E6Qp00CqOs/YvMi1ZJUE5Jqi14zTRbuKpcZwJqFuksqApm9MZjANUVIKd+OX+a/w+MFNclCYc5fCSvevwVFq7kHlQNjPZ+7mGfCw3rlzxYeK50pUDxa4KFZXArsTNZ+IpN8CcWARAmeGhV8wuqaHMhS9vlpDeH/khON3tp/v9ve97ncPPq3Wsoy20jbooRQfoEH1Fx2iEWPQxyqN5JOJBPItVrK+kcbTyvEP/RLz4CxSp3PE=</latexit>

inf

sup

A2A {Ci }n

sup

sup

n
n
i=1 ✓C {Oi }i=1 ✓O 2 {fi }i=1 ✓Fµ,L

T✏ (A, {(fi , Ci )}ni=1 )•Very challenging to directly solve the above problem•

We will establish the lower bound first, then the upper bound, and finally show they match each other•

The algorithm to achieve the lower bound is optimalCenter of Machine Learning Research

PART 03
Find Lower BoundLower bound with unbiased compressors
Theorem 1 (Unbiased compression)

For every , L > 0, n 2, !
0, > 0, T(1 + !)2 , there exists a set of
local loss functions {fi }ni=1 ✓ Fµ,L , stochastic gradient oracles {Oi }ni=1 ✓ O 2 ,!-unbiased compressors {Ci }ni=1 ✓ U! , such that for any algorithm A 2 A
starting from a given constant x(0) , the lower bound complexity is given by
s
!
✓
◆
2
L
1
⌦
+ (1 + !)
ln
,
µn✏
µ
✏
<latexit sha1_base64="QU0uobkDjhBh+xieB4AFXSRmHAs=">AAAElXicbVNNTxsxEF1I2tL0C+ihh16sspVCSaNsVLVcqPgS6gEpVCKAhEPkdbwbC68dbC+wWu0v6r/prf+m482mpIAPyWhm3tt5z+NwIrixnc6fhcVa/cnTZ0vPGy9evnr9Znll9cSoVFPWp0oofRYSwwSXrG+5FexsohlJQsFOw8s9Vz+9ZtpwJY9tNmGDhMSSR5wSC6nhyuIvLBWXIyYtOlAaMWjOkI/3mbCkhVuH3zt+C/kSx+wKdV2IVcJigspEWcOGxwmZ9h2X6WawMe1av8i7BeTtmGmG2C3oMYggwyxSERKKEgG/xqAoldQNZIAuj4YcF8OcbwXFhUTYpCEAgBYnxI4Bkh9AFSdpCx06cmMVHRNjOUWxJiPupChNqGAlW2+e7Y7sjq3n2EoNblrHOBPpf05lyMHdEaIqAV+NUbok3Xuc9B9nvxhWFDBfSsfgALEoAoOJzBARsdLcjhPk7yDM5R1up/BBD9GWyxhFWiXgVsyvmYQBJBRAmn97kTc765WtYN8N0yhUqZwOKcBlmyFuKlyYNUBryGIuc3aVltf+qYBcjntuwAILFtkmjsCxmQ3dwtmLJGYTw4WSBdqYu1NsrrTNp4DDsrMAEjnPE0B6hsWax2O7Xv2BuQ3M5Gh+lptyO/wZwnfDO2kjZrgG7wmlKbBm7eHyWqfdKQ96GARVsOZV52i4/BuPFE0TWAkqiDHnQWdiB7nzF9ajaODUsAmhlyRm5xBKkjAzyMtXVaCPqbt4d2eRAt/L7DwiJ4kxWRJCp7s+c7/mko/VzlMbbQ5yLiepZZJOPxSlAlmF3BNFI1BNrcggIBT2BBYbFhwcsPCQG2BCcF/yw+Ck2w6+tr/87K5t71Z2LHnvvQ9e0wu8b96298M78voera3WNms7td36u/pWfb9+MG1dXKgwb73/Tr33F2MeftQ=</latexit>

where ✏ is the desired accuracy.

Center of Machine Learning Research< 24 >

Consistency with existing lower bound<latexit sha1_base64="xvffmgBAl1A1PHEuZd+EAaEeJyk=">AAACX3icbVFda9swFJXdbu3SrvO2p7EXsTBIKQS7lHaPZXvZw2AdNG0hyoKsXDui+vCk60Iw/pN9G+xl/2RK4kG/LggdzrnnSjrKKyU9punvKN7YfPZ8a/tFb2f35d6r5PWbC29rJ2AkrLLuKucelDQwQokKrioHXOcKLvPrL0v98gacl9ac46KCiealkYUUHAM1TW4a9l1DyVumoMABKxwXDfOy1PznYdswXVPDoPJSWdPSAzrIDphdGvaZ/+WwWRu+rTrbMMTcnZMF+r+XOVnOcb/bpkk/Haaroo9B1oE+6epsmtyymRW1BoNCce/HWVrhpOEOpVDQ9ljtoeLimpcwDtBwDX7SrPJp6cfAzGhhXVgG6Yq962i49n6h89CpOc79Q21JPqWNayw+TRppqhrBiPVBRa0oWroMm86kA4FqEQAXToa7UjHnIRoMX9ILIWQPn/wYXBwOs+Ph0Y+j/unnLo5t8p58IAOSkRNySr6SMzIigvyJ4mgn2o3+xlvxXpysW+Oo87wl9yp+9w9ZObfx</latexit>

2⌦<latexit sha1_base64="7hPbLxmhkW66hlOsHJ+dAcUnUkw=">AAAB73icbVBNSwMxEJ2tX7V+VT16CRbBU9ktRT0WvXisYD+gXUs2zbahSXZNskJZ+ie8eFDEq3/Hm//GdLsHbX0w8Hhvhpl5QcyZNq777RTW1jc2t4rbpZ3dvf2D8uFRW0eJIrRFIh6pboA15UzSlmGG026sKBYBp51gcjP3O09UaRbJezONqS/wSLKQEWys1O1rNhL4oTYoV9yqmwGtEi8nFcjRHJS/+sOIJIJKQzjWuue5sfFTrAwjnM5K/UTTGJMJHtGepRILqv00u3eGzqwyRGGkbEmDMvX3RIqF1lMR2E6BzVgve3PxP6+XmPDKT5mME0MlWSwKE45MhObPoyFTlBg+tQQTxeytiIyxwsTYiEo2BG/55VXSrlW9i2r9rl5pXOdxFOEETuEcPLiEBtxCE1pAgMMzvMKb8+i8OO/Ox6K14OQzx/AHzucPyLKP0A==</latexit>2µn✏+ (1 + !)

s

✓ ◆!
L
1
ln
µ
✏

is the gradient noise, n is the number of nodes, and ! gauges the compression ratio<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><latexit sha1_base64="DG2xzlKYBSGANlkCmHyaiLAx90s=">AAAB7XicbVDLSgNBEJyNrxhfUY9eBoPgKexKUI9BLx4jmAckS5id9CZj5rHMzAphyT948aCIV//Hm3/jJNmDJhY0FFXddHdFCWfG+v63V1hb39jcKm6Xdnb39g/Kh0cto1JNoUkVV7oTEQOcSWhaZjl0Eg1ERBza0fh25refQBum5IOdJBAKMpQsZpRYJ7V6SsCQ9MsVv+rPgVdJkJMKytHol796A0VTAdJSTozpBn5iw4xoyyiHaamXGkgIHZMhdB2VRIAJs/m1U3zmlAGOlXYlLZ6rvycyIoyZiMh1CmJHZtmbif953dTG12HGZJJakHSxKE45tgrPXscDpoFaPnGEUM3crZiOiCbUuoBKLoRg+eVV0rqoBpfV2n2tUr/J4yiiE3SKzlGArlAd3aEGaiKKHtEzekVvnvJevHfvY9Fa8PKZY/QH3ucPkx+PJA==</latexit>• When n = 1 and ! = 0 , it recovers the lower bound in stochastic strongly-convex optimization• When n = 1 , ! = 0 and

2= 0 , it recovers Nesterov lower bound<latexit sha1_base64="FZNBztPrNSk0J3NsuOdiv2k3Liw=">AAACanicbVFdaxQxFM1M/air1bWCIn0JrsKWyjJTSvWlUOqLD4IV3LawWZdM9s5saD6myR1hGeahf7Fv/gJf+iPM7o5QWy+EnJxzDzc5yUolPSbJryheu3f/wcP1R53HTzaePus+3zzxtnIChsIq684y7kFJA0OUqOCsdMB1puA0O/+00E9/gvPSmu84L2GseWFkLgXHQE26l31zkL6nzGoo+EGyzS4qPqU1+7o4N0xBjn2WOy5q5mWh+Y/dpma6ogxKL5U1Dd2hzF84rFddX5ZyE5zmpjkN9F8Hc7KY4Xa70Um3lwySZdG7IG1Bj7R1POlesakVlQaDQnHvR2lS4rjmDqVQ0HRY5aHk4pwXMArQcA1+XC+jaui7wExpbl1YBumSvemoufZ+rrPQqTnO/G1tQf5PG1WYfxzX0pQVghGrQXmlKFq6yJ1OpQOBah4AF06Gu1Ix4yEbDL/TCSGkt598F5zsDtL9wd63vd7hURvHOtkib0ifpOQDOSSfyTEZEkF+RxvRy+hVdB1vxq/jrVVrHLWeF+Sfit/+ARsFu3E=</latexit>

2(n = 1, ! = 0)⌦Center of Machine Learning Research

µ✏

+

s

✓ ◆!
L
1
ln
µ
✏

<latexit sha1_base64="lMva3+O7HU6RBYA/UWFDP+Rs9YY=">AAACVHicbZHPSxwxFMczo7a6bXVrj16CS2GFssyIWC+C6KWHgha6KmyWJZN9Mxs2P8bkjbAM80e2h4J/SS89NLvOwWofhHz4ft8jyTdZqaTHJHmI4rX1jVevN7c6b96+297pvt+99rZyAobCKutuM+5BSQNDlKjgtnTAdabgJptfLP2be3BeWvMdFyWMNS+MzKXgGKRJd943p+knyqyGgp8mgbwsdKADdlfxKa3Z5dJpmIIc+8zfOaxZ7riovzY101UTHNOaKzkNMpReKmsa5mQxw4N2o5NuLxkkq6IvIW2hR9q6mnR/sqkVlQaDQnHvR2lS4rjmDqVQ0HRY5aHkYs4LGAU0XIMf16tQGvoxKFOaWxeWQbpSn07UXHu/0Fno1Bxn/rm3FP/njSrMT8a1NGWFYMTjQXmlKFq6TJhOpQOBahGACyfDXamY8ZANhn/ohBDS509+CdeHg/R4cPTtqHd23saxSfbIPumTlHwmZ+QLuSJDIsgP8jsiURT9iv7Ea/HGY2sctTMfyD8Vb/8FzFaztQ==</latexit>(n = 1, ! = 0,

= 0)

⌦

s

✓ ◆!
L
1
ln
µ
✏
< 25 >

Distributed optimization with compression• We construct adversarial objective functions• The odd element in f2 (x) can only be updated by receiving corresponding element from worker 1<latexit sha1_base64="6XIGOYULz7lUNhJkGZlFr0eTQ7M=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXspuKeqx6MVjBfsB7VKyabaNzSZLkhXL0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz249UaSbFvZnE1I/wULCQEWys1Ar71fLTeb9YcivuHGiVeBkpQYZGv/jVG0iSRFQYwrHWXc+NjZ9iZRjhdFroJZrGmIzxkHYtFTii2k/n107RmVUGKJTKljBorv6eSHGk9SQKbGeEzUgvezPxP6+bmPDKT5mIE0MFWSwKE46MRLPX0YApSgyfWIKJYvZWREZYYWJsQAUbgrf88ippVSveRaV2VyvVr7M48nACp1AGDy6hDrfQgCYQeIBneIU3RzovzrvzsWjNOdnMMfyB8/kDl9SOfw==</latexit><latexit sha1_base64="5Ra9nLvZWvhDk8yD+NHJEW4J5kA=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXsqulOqx6MVjBfsB7VKyabaNzSZLkhXL0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz249UaSbFvZnE1I/wULCQEWys1Ar7XvnpvF8suRV3DrRKvIyUIEOjX/zqDSRJIioM4VjrrufGxk+xMoxwOi30Ek1jTMZ4SLuWChxR7afza6fozCoDFEplSxg0V39PpDjSehIFtjPCZqSXvZn4n9dNTHjlp0zEiaGCLBaFCUdGotnraMAUJYZPLMFEMXsrIiOsMDE2oIINwVt+eZW0LiperVK9q5bq11kceTiBUyiDB5dQh1toQBMIPMAzvMKbI50X5935WLTmnGzmGP7A+fwBlk2Ofg==</latexit>

f1 (x)

Center of Machine Learning Research<latexit sha1_base64="6XIGOYULz7lUNhJkGZlFr0eTQ7M=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXspuKeqx6MVjBfsB7VKyabaNzSZLkhXL0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz249UaSbFvZnE1I/wULCQEWys1Ar71fLTeb9YcivuHGiVeBkpQYZGv/jVG0iSRFQYwrHWXc+NjZ9iZRjhdFroJZrGmIzxkHYtFTii2k/n107RmVUGKJTKljBorv6eSHGk9SQKbGeEzUgvezPxP6+bmPDKT5mIE0MFWSwKE46MRLPX0YApSgyfWIKJYvZWREZYYWJsQAUbgrf88ippVSveRaV2VyvVr7M48nACp1AGDy6hDrfQgCYQeIBneIU3RzovzrvzsWjNOdnMMfyB8/kDl9SOfw==</latexit>

f2 (x)< 26 >

Intuition behind lower bound• With compression, the desired entry may not be able to communicate

Desired entry
is not updated

Desired entry
is not selected<latexit sha1_base64="6XIGOYULz7lUNhJkGZlFr0eTQ7M=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXspuKeqx6MVjBfsB7VKyabaNzSZLkhXL0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz249UaSbFvZnE1I/wULCQEWys1Ar71fLTeb9YcivuHGiVeBkpQYZGv/jVG0iSRFQYwrHWXc+NjZ9iZRjhdFroJZrGmIzxkHYtFTii2k/n107RmVUGKJTKljBorv6eSHGk9SQKbGeEzUgvezPxP6+bmPDKT5mIE0MFWSwKE46MRLPX0YApSgyfWIKJYvZWREZYYWJsQAUbgrf88ippVSveRaV2VyvVr7M48nACp1AGDy6hDrfQgCYQeIBneIU3RzovzrvzsWjNOdnMMfyB8/kDl9SOfw==</latexit><latexit sha1_base64="5Ra9nLvZWvhDk8yD+NHJEW4J5kA=">AAAB7XicbVBNSwMxEJ2tX7V+VT16CRahXsqulOqx6MVjBfsB7VKyabaNzSZLkhXL0v/gxYMiXv0/3vw3pu0etPXBwOO9GWbmBTFn2rjut5NbW9/Y3MpvF3Z29/YPiodHLS0TRWiTSC5VJ8CaciZo0zDDaSdWFEcBp+1gfDPz249UaSbFvZnE1I/wULCQEWys1Ar7XvnpvF8suRV3DrRKvIyUIEOjX/zqDSRJIioM4VjrrufGxk+xMoxwOi30Ek1jTMZ4SLuWChxR7afza6fozCoDFEplSxg0V39PpDjSehIFtjPCZqSXvZn4n9dNTHjlp0zEiaGCLBaFCUdGotnraMAUJYZPLMFEMXsrIiOsMDE2oIINwVt+eZW0LiperVK9q5bq11kceTiBUyiDB5dQh1toQBMIPMAzvMKbI50X5935WLTmnGzmGP7A+fwBlk2Ofg==</latexit>

f1 (x)

f2 (x)• It explains why communication compression converges slower than vanilla distributed SGD
Center of Machine Learning Research< 27 >

Intuition behind lower bound• What’s the probability that the desired entry is sent?
Desired entry
is not selected• We constructed an adversarial compressor: rand-s• In rand-s compressor, s elements will be uniformly randomly chosen from all d elementsd• Rand-s is an unbiased compressor (after scale) with ! =s<latexit sha1_base64="GN1g6mMAil1EkHO20X6IGcV8fPo=">AAACAXicbVDLSsNAFJ3UV62vqBvBzWAR3FgSKepGKLpxWcE+oAllMpm0Q2cmYWYilBA3/oobF4q49S/c+TdO2yy09cCFwzn3cu89QcKo0o7zbZWWlldW18rrlY3Nre0de3evreJUYtLCMYtlN0CKMCpIS1PNSDeRBPGAkU4wupn4nQciFY3FvR4nxOdoIGhEMdJG6tsHXszJAMEr6EUS4SzMM5XDUxf27apTc6aAi8QtSBUUaPbtLy+MccqJ0JghpXquk2g/Q1JTzEhe8VJFEoRHaEB6hgrEifKz6Qc5PDZKCKNYmhIaTtXfExniSo15YDo50kM1703E/7xeqqNLP6MiSTUReLYoShnUMZzEAUMqCdZsbAjCkppbIR4ik4Q2oVVMCO78y4ukfVZzz2v1u3q1cV3EUQaH4AicABdcgAa4BU3QAhg8gmfwCt6sJ+vFerc+Zq0lq5jZB39gff4A4lSV4w==</latexit>

1• The desired entry is sent with probability s/d = (1 + !) 1
<latexit sha1_base64="RaIIXK1sMWgu6FwMGay+KM/oYQQ=">AAAB/nicbVDLSgMxFM3UV62vUXHlJliEilhnpKgboejGZQX7gHYsmUymDU0mQ5IRylDwV9y4UMSt3+HOvzFtZ6GtBy4czrmXe+/xY0aVdpxvK7ewuLS8kl8trK1vbG7Z2zsNJRKJSR0LJmTLR4owGpG6ppqRViwJ4j4jTX9wM/abj0QqKqJ7PYyJx1EvoiHFSBupa++p0wBewZJ73BGc9NDRQ3rijrp20Sk7E8B54makCDLUuvZXJxA44STSmCGl2q4Tay9FUlPMyKjQSRSJER6gHmkbGiFOlJdOzh/BQ6MEMBTSVKThRP09kSKu1JD7ppMj3Vez3lj8z2snOrz0UhrFiSYRni4KEwa1gOMsYEAlwZoNDUFYUnMrxH0kEdYmsYIJwZ19eZ40zsrueblyVylWr7M48mAfHIAScMEFqIJbUAN1gEEKnsEreLOerBfr3fqYtuasbGYX/IH1+QNRCpPP</latexit>

Center of Machine Learning Research< 28 >

Intuition behind lower bound• In expectation, the desired entry will experience 1 + ω rounds to be sent

• Recall the lower bound complexity of standard distributed optimization as<latexit sha1_base64="ym03VIrw65FMaBAE9lNW6Ywc7jE=">AAACNnicbZDLSgMxFIYz3q23qks3wSLopsxIUZeiGxeKClaFTimZ9EwbTDJjckYowzyVG5/DnRsXirj1EUzrLLwdCPn5/nNIzh+lUlj0/SdvbHxicmp6ZrYyN7+wuFRdXrm0SWY4NHkiE3MdMQtSaGiiQAnXqQGmIglX0c3h0L+6A2NFoi9wkEJbsZ4WseAMHepUT/LwVEGPFaGEGDdDe2swD2PDeH5c5KHKCufo0hzhwGFIrZCJLkIjen3cKi9a6VRrft0fFf0rglLUSFlnnepj2E14pkAjl8zaVuCn2M6ZQcElFJUws5AyfsN60HJSMwW2nY/WLuiGI10aJ8YdjXREv0/kTFk7UJHrVAz79rc3hP95rQzjvXYudJohaP71UJxJigkdZki7wgBHOXCCcSPcXynvMxcOuqSHIQS/V/4rLrfrwU69cd6o7R+UccyQNbJONklAdsk+OSJnpEk4uSdP5IW8eg/es/fmvX+1jnnlzCr5Ud7HJzd3rfY=</latexit>

⌦

s

✓ ◆!
L
1
ln
µ
✏

• Since sending the desired entry require 1 + ω rounds, the lower bound with compression is<latexit sha1_base64="yby94vlCKCFlnTBOiISIPeskXjM=">AAACTHicbVDPSxtBFJ6N1mr6K63HXhaDECmE3SLWo7QXD4IKRoVMCLOTt8ng/Fhn3gph2D/Qiwdv/hW99KBIwUmyh1Z9MMzH973vzZsvK6RwmCR3UWNp+c3K29W15rv3Hz5+an3+cupMaTn0uJHGnmfMgRQaeihQwnlhgalMwll28Wumn12BdcLoE5wWMFBsrEUuOMNADVvc00MFY1ZRCTl2PJ2P9Jksoeqk36iZiVsVdZcWPc0t4/6g8lSVVXDohWlBp4GGwglpdEWtGE9wq76GrXbSTeYVvwRpDdqkrqNh65aODC8VaOSSOddPkwIHnlkUXELVpKWDgvELNoZ+gJopcAM/37yKNwMzinNjw9EYz9l/HZ4p56YqC52K4cQ912bka1q/xHx34IUuSgTNFw/lpYzRxLNk45GwwFFOA2DcirBrzCcsRIMh/2YIIX3+5Zfg9Hs33eluH2+3937WcaySr2SDdEhKfpA9sk+OSI9wck1+k3vyEN1Ef6LH6O+itRHVnnXyXzVWngDy4bbO</latexit>⌦ (1 + !)Center of Machine Learning Research

s

✓ ◆!
L
1
ln
µ
✏
< 29 >

Lower bound with contractive compressor

Theorem 2 (Contractive compression)

For every , L > 0, n 2, !
0, > 0, T(1 + !)2 , there exists a set of
local loss functions {fi }ni=1 ✓ Fµ,L , stochastic gradient oracles {Oi }ni=1 ✓ O 2 ,!-unbiased compressors {Ci }ni=1 ✓ C , such that for any algorithm A 2 A
starting from a given constant x(0) , it holds that
s
!
✓
◆
2
1 L
1
?
E[f (x̂) f ] = ⌦
+
ln
,
µn✏
µ
✏
<latexit sha1_base64="qBtEmdZ+UNhPHhk4wCs2L3BYrRo=">AAAEfHicbVNdb9MwFM3aAqN8bfDIA1csSC3rpqZCg5ehjcHEw6QNaR9Ic1s5jpNac+wudqZVUf4EP403fgoviOu0Y2WbH5Kre889vufYDsdSGNvt/lqo1Rv37j9YfNh89PjJ02dLy8+Pjc4zxo+Yljr7HlLDpVD8yAor+fdxxmkaSn4Snu24+skFz4zQ6tBOxryf0kSJWDBqMTVcrv0gSgsVcWVhV2fAETwBn3zm0tIO6ex97Pod8BVJ+Dn0XEh0yhMKVaKqESOSlE5xh1W6FaxOUe1B0Ssxb0c848AvUY8BCoZb0DFIzajErzEQ54q5gQzSFfFQkHJYiM2gHCggJg+xAWlJSu0IW4pdrJI078CeIzdWsxE1VjBIMhoJJ0VnlElese3Ps12TXbPtO7ZKg5vWMV6J9NdyFQp0NwKmU/TVGJ1VpDt3k/7j3CmHJHIWuvlyNkIHqIUYDaZqAlQmOhN2lIK/DUSo677t0kc9NLNCJRBnOkW3EnHBFQ6gsIDS/MtB0eq23ZzCwkjLyEzZm6gp5IlQBT/Pq+N9WzZnOsOw+FKexi2CwOKybK/FA+L26QNsQkH2ndqSSB7bFonRuytDeqUzGhThYyOkViWswhQQYKVSWBJzntlimt2r8CVSqXk2B75iIJlIRrY9+6HZhKtofuTmcGmlu96tFtwOglmw4s3WwXDpJ4k0y1M8eSapMadBd2z7hbMRb0HZJLnhY8rOaMJPMVQ05aZfVI+nhDe5O193NLFGe6vsfEdBU2MmaYhI56S5WXPJu2qnuY0/9Auhxrnlik03inMJVoN7iRCJjDMrJxhQhtcB7y/eY7TL4nt1JgQ3Jd8Ojnvrwcb6u2+9la1PMzsWvZfea6/lBd57b8v76h14Rx6r/a6/qrfq7fqfht9YbaxNobWFWc8L77/V2PgL42t3MA==</latexit>

Center of Machine Learning Research< 30 >

PART 04
Algorithm to Attain Lower Bounds

Optimal algorithm for distributed optimizationn<latexit sha1_base64="4s4k+h9xgjmrws+lvj2BUmbO47g=">AAACk3icbVHtahQxFM2MX3X8WhVB8E/sImxBlhkVFUqh1Cr+EeritoXNdshkMt3QfIxJxs4S8ga+oG8hPoGZ3RG09ULgcM65yc25Rc2ZsWn6I4qvXL12/cbGzeTW7Tt37w3uPzg0qtGEToniSh8X2FDOJJ1aZjk9rjXFouD0qDh71+lH36g2TMkvdlnTucCnklWMYBuofPAdCSZz10LEJESTyUnp0dcGl7AatVtwB6JKY+Iy76RHphG5YzuZP5GwylkwPIdrMxKFat35gmrqe2pt6G4Q2C6Kwr33uXOoZT5nEBkm4H7O/IdRuw17dmucD4bpOF0VvAyyHgxBXwf54CcqFWkElZZwbMwsS2s7d1hbRjj1CWoMrTE5w6d0FqDEgpq5W6Xm4bPAhDmVDkdauGL/7nBYGLMURXB2XzAXtY78nzZrbPV27pisG0slWT9UNRxaBbsVwJJpSixfBoCJZmFWSBY45GzDopIESXpOlBBYli5sxLs/CU68T0JE2cVALoPDF+Ps9fjl51fD3b0+rA3wBGyCEcjAG7ALPoIDMAUE/IoeR0+jzfhRvB3vxftraxz1PQ/BPxV/+g1ixch4</latexit>• Recall the problem

min

x2Rd

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

where

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

• We first consider the scenario in which the true gradient ∇𝑓! (𝑥) is known and no compression is used
• The optimal algorithm is Nesterov Acceleration. For k=1,2,…,T<latexit sha1_base64="7cjF8xWwzs/7t3zCPKBVnbykQs8=">AAAC/3icbVJNb9MwGHbC1ygf60CcuFhUoFbVqhhNwGXSBBeOQ6LbpKaNHNfJrNpOZDtobfCBv8KFAwhx5W9w499gpwHKyitFevR8+H39xmnJmTZR9DMIr1y9dv3Gzs3Ordt37u529+6d6KJShI5JwQt1lmJNOZN0bJjh9KxUFIuU09N08crrp++o0qyQb82ypFOBc8kyRrBxVLIXPFjN6oWFTw5hnClMamTrOMdCYHvRCEMYpyzv/1VLC/e3vI1pAH1kH/lQH226SjtYtVIcd5azhe+3YWlP8b4LJw636JVjXTJP2DobS5xyDLOE9d1pg0Zrld89pY11JZKaHSI7k3AddT4/4xA1N/aD/BmBmqZT3riSbi8aRU3BbYBa0ANtHSfdH/G8IJWg0hCOtZ6gqDTTGivDCKe2E1ealpgscE4nDkosqJ7Wzf+z8LFj5jArlPukgQ27maix0HopUucU2Jzry5on/6dNKpO9mNZMlpWhkqwbZRWHpoD+McA5U5QYvnQAE8XcrJCcY7cO455Mxy0BXb7yNjh5OkLPRgdvDnpHL9t17ICH4BHoAwSegyPwGhyDMSDB++Bj8Dn4En4IP4Vfw29raxi0mfvgnwq//wIRkOxr</latexit>

k

z =
k

1

1
x +
p

y = (1

k

k

)x +

p
gik = rfi (y k )
n
X
1
gik
gk =
n i=1
⌘ k
k+1
k
x
=y
g
p
Center of Machine Learning Research

1

p

x
z

k 1

+ (1

1 k 1
)z
p

k

(extrapolation)(true gradient)(precise communication)(gradient descent)< 32 >

Extension to stochastic and compressed scenario• A trivial extension: For k = 1,2,…,T<latexit sha1_base64="GdgOljXwdp6KJydv3AG1frvRN20=">AAADJ3icbVJdixMxFM2MX2v92K4++hIsypSyZSKLClJYXBAfV7C7C007ZNJ0NjTJDJOMtA3zb3zxr/giqIg++k/MTIfd7tYLgcs959x77iVxJrg2YfjH82/cvHX7zs7d1r37Dx7utvcenei0yCkb0lSk+VlMNBNcsaHhRrCzLGdExoKdxvOjCj/9xHLNU/XRLDM2liRRfMYpMa4U7XmD1cTOS/h8APEsJ9Si0uKESEnKRQ30II55ElyiWQn3t7g1qQsryT6qRAHaZGVld9VAGLeWk3k1b4PSdKl4Cwf2tsorV3XKJOJrrcX16jYWBSuxIrEg8F3gGr+BeMErVrcelazpF0ZUiXUhI8sHqJyoq22OIh4kl9Jqlx6qL1MZvrDKTO0oqR1F7U7YD+uA2wlqkg5o4jhqf8fTlBaSKUMF0XqEwsyMLckNp4KVLVxolhE6JwkbuVQRyfTY1i5L+MxVpnCW5u4pA+vqpsISqfVSxo4piTnX17Gq+D9sVJjZ67HlKisMU3Q9aFYIaFJYfRo45TmjRixdQmjOnVdIz4k7h3Ffq+WOgK6vvJ2cvOijl/2DDwedw7fNOXbAE/AUBACBV+AQvAfHYAio99n76v3wfvpf/G/+L//3mup7jeYxuBL+33+XTv2+</latexit>

k

z =

1

1
x +
p

y k = (1

k

)xk +

1

p
p
gik = rF (y k ; ⇠ik )nX1k
Ci (gik )
g =
n i=1
⌘ k
k+1
k
x
=y
g
p

x

k 1

+ (1

1 k 1
)z
p

(extrapolation)zk(stochastic gradient)(communication compression)(gradient descent)• Does not work well. Stochastic gradient and compression introduces too much noise.
Center of Machine Learning Research< 33 >

Upper bound and nearly-optimal algorithms• A refined algorithm: For k = 1,2,…,T/R<latexit sha1_base64="CfoJ93+1dHuY3a6DNsBEGWKMOdM=">AAADUHicbVJdixMxFM20fqz1q6uPvgSLMqW7pSOLCrKwuCC+CGu1uwudtmTSzGxoJjMkGWkb8hN92Td/hy8+KJpJh1pbLwxzueece++5JMoZlarX++bV6jdu3rq9d6dx9979Bw+b+4/OZVYITAY4Y5m4jJAkjHIyUFQxcpkLgtKIkYtodlriF1+IkDTjn9UiJ6MUJZzGFCNlS5N9L16O9czA58cwjAXCOjA6TFCaIjN3QAeGEU38v2hu4OEO15HasJQcBqXIDzZZuWkvKygMG4vxrJy3Qam6lLy5BTs75aWtWmUyoSutDp11HbGCmPWYvgllkU60OA7MuB9yFDEE3/l23hsYzqkVa392INqm7fZIVr3Wcl7JaSnnWzNSpK5Eqj98OjW+W+MA9ldtStOdwJ2wdLb2RJRbPXGrT5qtXrfnAu4mQZW0QBVnk+Z1OM1wkRKuMENSDoNerkYaCUUxI6YRFpLkCM9QQoY25SglcqTdxgY+s5UpjDNhP66gq24qNEqlXKSRZZa+5DZWFv+HDQsVvx5pyvNCEY5Xg+KCQZXB8nXBKRUEK7awCcKC2l0hvkL2HMq+wYY9QrBteTc5f9ENXnaPPh61Tt5W59gDT8BT4IMAvAIn4D04AwOAva/ed++n96t2XftR+133VtRa9QePwT9Rb/wBJOYMpg==</latexit>

zk =

1

xk +

k

1
p

1

k

xk 1 + (1y = (1

)x +

gik =

rF (y k ; ⇠i

p
R
1 X

R r=1

p

z

k

(k,r)

)

1 k 1
)z
p

(extrapolation)(large-batch stochastic gradient)

n

1X
k
g =
MSC(gik , R)
n i=1
⌘ k
xk+1 = y kgp(multi-step compression)(gradient descent)• The communication and sample budget are the same as previous algorithms
Center of Machine Learning Research< 34 >

Upper bound and nearly-optimal algorithms• Multi-step compression (MSC) protocol:

Input: Origical vector v and compression round R<latexit sha1_base64="xtos0FG/Lm+rqodYukiLK/FjYsc=">AAACJnicbVDLSgMxFM34tr6qLt0EW8FVmRFREYSiG11ZxWqhHUomk6mhmWRI7hTL0K9x46+4caGIuPNTzLRdaPWsDufc5wkSwQ247qczNT0zOze/sFhYWl5ZXSuub9walWrK6lQJpRsBMUxwyerAQbBGohmJA8Hugu5Z7t/1mDZcyRvoJ8yPSUfyiFMCVmoXT1rAHiCIsguZpHA8wJead6wrcI9RUBqXe2VMZIipiu1gkw/CWqVWKV+X28WSW3GHwH+JNyYlNEatXXxthYqmMZNABTGm6bkJ+BnRwKlgg0IrNSwhtEs6rGmpJDEzfjZ8c4B3rBLiyB4VKQl4qP7syEhsTD8ObGVM4N5Mern4n9dMITryM54nwCQdLYpSgUHhPDMccm3DEH1LCNXc3orpPdGEgk22YEPwJl/+S273Kt5BZf9qr1Q9HcexgLbQNtpFHjpEVXSOaqiOKHpEz+gVvTlPzovz7nyMSqeccc8m+gXn6xu1RKVB</latexit>•

With MSC, we can prove<latexit sha1_base64="/PpzOmN2Cl46YBH3ldJKBV3DjaQ=">AAACAnicbZBLSwMxFIUz9VXra9SVuAm2Qt2UmSIqiFB0o7sK9gFtLZn0tg3NZIYkU6hDceNfceNCEbf+Cnf+G9PHQlsPBD7OuZdwjxdyprTjfFuJhcWl5ZXkamptfWNzy97eKasgkhRKNOCBrHpEAWcCSpppDtVQAvE9DhWvdzXKK32QigXiTg9CaPikI1ibUaKN1bT3bgTTjHD2ADjTv4+zztEQX2Anc960007OGQvPgzuFNJqq2LS/6q2ARj4ITTlRquY6oW7ERGpGOQxT9UhBSGiPdKBmUBAfVCMenzDEh8Zp4XYgzRMaj93fGzHxlRr4npn0ie6q2Wxk/pfVIt0+a8RMhJEGQScftSOOdYBHfeAWk0A1HxggVJouKKZdIgnVprWUKcGdPXkeyvmce5I7vs2nC5fTOpJoHx2gLHLRKSqga1REJUTRI3pGr+jNerJerHfrYzKasKY7u+iPrM8fM26VWw==</latexit>

Initialize v (0) = 0;
for r = 0, · · · , R<latexit sha1_base64="UoT1/6wASNIG4MQFN0mAeAV6l/Q=">AAACDHicbVDLTgIxFO3gC/GFunTTCCawkMwQo25IiG5cIpFHAgPplA40tDOTtkNCJvMBbvwVNy40xq0f4M6/scAsFDxJk5Nzzs3tPU7AqFSm+W2k1tY3NrfS25md3b39g+zhUVP6ocCkgX3mi7aDJGHUIw1FFSPtQBDEHUZazvh25rcmREjqew9qGhCbo6FHXYqR0lI/m8tPelGhXoxhBXZlyPuRqJhxL6qfWzHWjijGeZ0yS+YccJVYCcmBBLV+9qs78HHIiacwQ1J2LDNQdoSEopiRONMNJQkQHqMh6WjqIU6kHc2PieGZVgbQ9YV+noJz9fdEhLiUU+7oJEdqJJe9mfif1wmVe21H1AtCRTy8WOSGDCofzpqBAyoIVmyqCcKC6r9CPEICYaX7y+gSrOWTV0mzXLIuSxf35Vz1JqkjDU7AKSgAC1yBKrgDNdAAGDyCZ/AK3own48V4Nz4W0ZSRzByDPzA+fwD1wpmt</latexit>

v

1 do

<latexit sha1_base64="CfJtTd3aGUoVJViuGTI0WeLdED8=">AAACE3icbVDLSgNBEJyNrxhfUY9eBhNBJIbdIOpFCHrxGMU8IAlhdnY2GTK7s8z0imHJP3jxV7x4UMSrF2/+jZOHoNGChqKqm+4uNxJcg21/Wqm5+YXFpfRyZmV1bX0ju7lV0zJWlFWpFFI1XKKZ4CGrAgfBGpFiJHAFq7v9i5Ffv2VKcxnewCBi7YB0Q+5zSsBInexBC9gduH7iSzXEeXVmF1rUk6AL+PrQyeNv25PDTjZnF+0x8F/iTEkOTVHpZD9anqRxwEKggmjddOwI2glRwKlgw0wr1iwitE+6rGloSAKm28n4pyHeM4qHzVWmQsBj9edEQgKtB4FrOgMCPT3rjcT/vGYM/mk74WEUAwvpZJEfCwwSjwLCHleMghgYQqji5lZMe0QRCibGjAnBmX35L6mVis5x8eiqlCufT+NIox20i/aRg05QGV2iCqoiiu7RI3pGL9aD9WS9Wm+T1pQ1ndlGv2C9fwFj5506</latexit>

compress v

v

into c

(r)

= C(v

v

(r)

PR 1 (r)= r=0 cEkv (R)<latexit sha1_base64="5UwAeUPuF6IZp0e1aMySRyfjD1s=">AAACH3icbVBNS8NAFNzU7/oV9ehlsQr1YEmKqEdRBI9arBWatmw2L3bpZhN2N4US+0+8+Fe8eFBEvPlv3LQ9aHVgYZh5j7czfsKZ0o7zZRVmZufmFxaXissrq2vr9sbmrYpTSaFOYx7LO58o4ExAXTPN4S6RQCKfQ8Pvned+ow9SsVjc6EECrYjcCxYySrSROvbRrhcR3fX97GLoPfTbWbm2P8QHuO89tKvY44DL7oEXANdkv13DZiQ3djt2yak4I+C/xJ2QEprgqmN/ekFM0wiEppwo1XSdRLcyIjWjHIZFL1WQENoj99A0VJAIVCsb5RviPaMEOIyleULjkfpzIyORUoPIN5N5GDXt5eJ/XjPV4UkrYyJJNQg6PhSmHOsY52XhgEmgmg8MIVQy81dMu0QSqk2lRVOCOx35L7mtVtyjyuF1tXR6NqljEW2jHVRGLjpGp+gSXaE6ougRPaNX9GY9WS/Wu/UxHi1Yk50t9AvW1zdtB6C3</latexit><latexit sha1_base64="uLXwmqIZ/YSC+I6Ck25jqbnqKuc=">AAACH3icbVBLTwIxGOz6RHytevTSyJrAQbJLDHoxIXLxiIk8ElhJt3ShodvdtF0SsuGfePGvePGgMcYb/8YCe0DwS5pMZ75JO+NFjEpl21NjY3Nre2c3s5fdPzg8OjZPThsyjAUmdRyyULQ8JAmjnNQVVYy0IkFQ4DHS9IbVmd4cESFpyJ/UOCJugPqc+hQjpamuWcZhoA1SQmsEr+DoOcmLwsSClKsQWnhxhXewml+SC1bXzNlFez5wHTgpyIF0al3zp9MLcRwQrjBDUrYdO1JugoSimJFJthNLEiE8RH3S1pCjgEg3meebwEvN9KAfCn24gnN22ZGgQMpx4OnNAKmBXNVm5H9aO1b+rZtQHsWKcLx4yI8Z1NlnZcEeFQQrNtYAYUH1XyEeIIGw0pVmdQnOauR10CgVnXLx+rGUq9yndWTAObgAeeCAG1ABD6AG6gCDF/AGPsCn8Wq8G1/G92J1w0g9Z+DPGNNfO66fVQ==</latexit>

(r)

(R)

)

vk2  (1

)R kvk2<latexit sha1_base64="w1tYV+JNx73g1E2L/fCznXwDFR0=">AAACBXicbVC7SgNBFJ31GeMraqnFYCLEJuwGUcugjWUE84AkhtnJTTJkdnaZuSuEJY2Nv2JjoYit/2Dn3zh5FJp4YOBwzr3cOcePpDDout/O0vLK6tp6aiO9ubW9s5vZ26+aMNYcKjyUoa77zIAUCiooUEI90sACX0LNH1yP/doDaCNCdYfDCFoB6ynRFZyhldqZIwOqQ3P8Psnr01GOYkixDxSZ7gG2M1m34E5AF4k3I1kyQ7md+Wp2Qh4HoJBLZkzDcyNsJUyj4BJG6WZsIGJ8wHrQsFSxAEwrmaQY0ROrdGg31PYppBP190bCAmOGgW8nA4Z9M++Nxf+8Rozdy1YiVBQjKD491I3lJKuthHaEBo5yaAnjWti/Ut5nmnG0xaVtCd585EVSLRa888LZbTFbuprVkSKH5JjkiUcuSInckDKpEE4eyTN5JW/Ok/PivDsf09ElZ7ZzQP7A+fwBnUWXYw==</latexit>

send c(r) to the target•

It holds that<latexit sha1_base64="C2Yf28y293O9gvGQpx661pSi7kc=">AAACD3icbZDLSsNAFIYnXmu9RV26GWyVSqEkRdSNUHTjsoK9QBvLZDJph04mYWZSKKFv4MZXceNCEbdu3fk2TtMstPWHgY//nMOZ87sRo1JZ1rextLyyurae28hvbm3v7Jp7+00ZxgKTBg5ZKNoukoRRThqKKkbakSAocBlpucObab01IkLSkN+rcUScAPU59SlGSls98ySOPKQILI4ekpIo26cTeAVT1lSGeEbFnlmwKlYquAh2BgWQqd4zv7peiOOAcIUZkrJjW5FyEiQUxYxM8t1YkgjhIeqTjkaOAiKdJL1nAo+140E/FPpxBVP390SCAinHgas7A6QGcr42Nf+rdWLlXzoJ5VGsCMezRX7MoArhNBzoUUGwYmMNCAuq/wrxAAmElY4wr0Ow509ehGa1Yp9Xzu6qhdp1FkcOHIIjUAI2uAA1cAvqoAEweATP4BW8GU/Gi/FufMxal4xs5gD8kfH5A8mSmfc=</latexit>

update v (r+1) = v (r) + c(r)end for<latexit sha1_base64="9bfIA4IIe2ytgPbXHTI9DaX3pmk=">AAAB+XicbVBNS8NAEN34WetX1KOXYBE8laSIeix68VjBfkAbymY7aZduNmF3Uiyh/8SLB0W8+k+8+W/cpjlo64OBx3szzMwLEsE1uu63tba+sbm1Xdop7+7tHxzaR8ctHaeKQZPFIladgGoQXEITOQroJApoFAhoB+O7ud+egNI8lo84TcCP6FDykDOKRurbdg/hCYMwAzlwwljN+nbFrbo5nFXiFaRCCjT69ldvELM0AolMUK27npugn1GFnAmYlXuphoSyMR1C11BJI9B+ll8+c86Nku81JdHJ1d8TGY20nkaB6YwojvSyNxf/87ophjd+xmWSIki2WBSmwsHYmcfgDLgChmJqCGWKm1sdNqKKMjRhlU0I3vLLq6RVq3pX1cuHWqV+W8RRIqfkjFwQj1yTOrknDdIkjEzIM3klb1ZmvVjv1seidc0qZk7IH1ifP97hk9E=</latexit>

Center of Machine Learning Research<latexit sha1_base64="DzzKM2ZTO1qBuXvQ1BXXvw8eNDA=">AAACCnicbVA7T8MwGHTKq5RXgJHF0CCVpUoqBIwVLIylog+pLZXjOq1Vx4lsp1IUdWbhr7AwgBArv4CNf4ObZoCWkyyd775P9p0bMiqVbX8buZXVtfWN/GZha3tnd8/cP2jKIBKYNHDAAtF2kSSMctJQVDHSDgVBvstIyx3fzPzWhAhJA36v4pD0fDTk1KMYKS31zWNr8pCU6mdT2FUBnFgQSWjV00uXck/FVt8s2mU7BVwmTkaKIEOtb351BwGOfMIVZkjKjmOHqpcgoShmZFroRpKECI/RkHQ05cgnspekUabwVCsD6AVCH65gqv7eSJAvZey7etJHaiQXvZn4n9eJlHfVSygPI0U4nj/kRQzqoLNe4IAKghWLNUFYUP1XiEdIIKx0ewVdgrMYeZk0K2Xnonx+VylWr7M68uAInIAScMAlqIJbUAMNgMEjeAav4M14Ml6Md+NjPpozsp1D8AfG5w+noZhb</latexit>v (R) ! v as R ! 1< 35 >

Upper bound and nearly-optimal algorithms• A refined algorithm NEOLITHIC: For k = 1,2,…,T/R<latexit sha1_base64="CfoJ93+1dHuY3a6DNsBEGWKMOdM=">AAADUHicbVJdixMxFM20fqz1q6uPvgSLMqW7pSOLCrKwuCC+CGu1uwudtmTSzGxoJjMkGWkb8hN92Td/hy8+KJpJh1pbLwxzueece++5JMoZlarX++bV6jdu3rq9d6dx9979Bw+b+4/OZVYITAY4Y5m4jJAkjHIyUFQxcpkLgtKIkYtodlriF1+IkDTjn9UiJ6MUJZzGFCNlS5N9L16O9czA58cwjAXCOjA6TFCaIjN3QAeGEU38v2hu4OEO15HasJQcBqXIDzZZuWkvKygMG4vxrJy3Qam6lLy5BTs75aWtWmUyoSutDp11HbGCmPWYvgllkU60OA7MuB9yFDEE3/l23hsYzqkVa392INqm7fZIVr3Wcl7JaSnnWzNSpK5Eqj98OjW+W+MA9ldtStOdwJ2wdLb2RJRbPXGrT5qtXrfnAu4mQZW0QBVnk+Z1OM1wkRKuMENSDoNerkYaCUUxI6YRFpLkCM9QQoY25SglcqTdxgY+s5UpjDNhP66gq24qNEqlXKSRZZa+5DZWFv+HDQsVvx5pyvNCEY5Xg+KCQZXB8nXBKRUEK7awCcKC2l0hvkL2HMq+wYY9QrBteTc5f9ENXnaPPh61Tt5W59gDT8BT4IMAvAIn4D04AwOAva/ed++n96t2XftR+133VtRa9QePwT9Rb/wBJOYMpg==</latexit>

zk =

1

xk +

k

1
p

1

k

xk 1 + (1y = (1

)x +

gik =

rF (y k ; ⇠i

p
R
1 X

R r=1

p

z

k

(k,r)

)

1 k 1
)z
p

(extrapolation)(large-batch stochastic gradient)

n

1X
k
g =
MSC(gik , R)
n i=1
⌘ k
xk+1 = y kgp(multi-step compression)(gradient descent)• As R ! 1 , the refined algorithm will approach to vanilla Nesterov; the introduced noise can be controlled<latexit sha1_base64="z+QvhiF/t1yo5wevwaSkejd3ngA=">AAAB83icbVBNS8NAEJ3Ur1q/qh69LBbBU0mkqMeiF49V7Ac0oWy2m3bpZhN2J0Ip/RtePCji1T/jzX/jts1BWx8MPN6bYWZemEph0HW/ncLa+sbmVnG7tLO7t39QPjxqmSTTjDdZIhPdCanhUijeRIGSd1LNaRxK3g5HtzO//cS1EYl6xHHKg5gOlIgEo2gl/4H4mBBfqAjHvXLFrbpzkFXi5aQCORq98pffT1gWc4VMUmO6nptiMKEaBZN8WvIzw1PKRnTAu5YqGnMTTOY3T8mZVfokSrQthWSu/p6Y0NiYcRzazpji0Cx7M/E/r5thdB1MhEoz5IotFkWZJPbPWQCkLzRnKMeWUKaFvZWwIdWUoY2pZEPwll9eJa2LqndZrd3XKvWbPI4inMApnIMHV1CHO2hAExik8Ayv8OZkzovz7nwsWgtOPnMMf+B8/gBzOpFS</latexit>

Center of Machine Learning Research< 36 >

Upper bound and nearly-optimal algorithms

Theorem 1 (Upper bound)<latexit sha1_base64="aQP5xWNlxciBcNpi1n5icQOKPMs=">AAAEaXiczZNba9RAFIDT3VXrWrVVFNGXwa2wa+uyKaK+CEURFAUr2Avs7JbJ5CQZOpd05qRaQ/A/+uYf8MU/4WQ3Ym375osDIYdzn+/MiXIpHI5G3xda7c6Fi5cWL3evLF29dn155caOM4XlsM2NNHYvYg6k0LCNAiXs5RaYiiTsRgcva/vuEVgnjP6IxzlMFEu1SARn6FX7K62vVBuhY9BI+m90YqxickB2M9CkQCHFF6FTUuhI+CIx4Ub59M4Z69YJZkCYTI0VmClv0r5QCo4wJF0aQSp0CYfFrNDDqksIVQyzKCpfVeOk/3n6dvAomVKHzE4IeU6orxZDOXPiTJbvq4pKSLBPE8t4SZ1IFZtuVN6jIJpC7oQ0uiJrpB+uUaMgZQPqDi2W84B3M886iT6ZJ/Tq37HUijTDQfNbp6Djkx1/ysACWT2nsT7lscHBKslE7C8sTTpngGCV81w8AeZDa645zOGaxGdqCq8OG8CuhuvBoe8MxRH8n3z/gItBIqv+ifLwFOX95d5oOJodclYIG6EXNGdrf/kbjQ0vlIfKJXNuHI5ynJTMouASqi4tHOSMH7AUxl7UTIGblLNNqciDon7F/pX7zw9lpj0ZUTLl3LGKvGfNyZ221crzbOMCk2eTUui8QNB8XigpJEFD6rUjsbDAUR57gXE/UMEJz1g9dr+cXQ8hPH3ls8LOxjB8Mnz8YaO3+aLBsRjcC+4H/SAMngabwetgK9gOeOtHe6l9q327/bOz0rnTuTt3bS00MTeDv06n9wuJi3uq</latexit>(Informal) When utilizing unbiased compressors, the algorithm converges at
s
!
✓
◆
2
L
1
K
?
E[f (x ) f ] = Õ+ (1 + !)
ln
,
µn✏
µ
✏
where Õ(·) hides logrithm terms that are independent of ✏. When using contractive compressors, the algorithm converges at
s
!
✓
◆
2
1 L
1
K
?
E[f (x ) f ] = Õ
+
ln
.
µn✏
µ
✏
Center of Machine Learning Research< 37 >

Upper bound and nearly-optimal algorithms<latexit sha1_base64="1LAOwxAqmbwyBnQO/Ic85i/rSNo=">AAACv3ichVFda9swFJW9bmuzj2bbY19EwyCFEOxS2j1s0Cww9jBoB01biFIjK9epiCRrkjwIwn9yD4P9m8lp+rG2sAtCh3PP0f1QrgW3Lkn+RPGTtafPnq9vtF68fPV6s/3m7aktK8NgxEpRmvOcWhBcwchxJ+BcG6AyF3CWz4dN/uwnGMtLdeIWGiaSzhQvOKMuUFn7N+GqyPwgXJhI6i4ZFX5Q15jYSmee+GHGSZ15/imtL1QgcwsOfuBb8bCur7VHj2tvpEchSSyfSXqxe6dE8R/bl8Ymq9634DnJCGjLRalwd9AjvhvMvdDjzu0LO7jVytqdpJ8sAz8E6Qp00CqOs/YvMi1ZJUE5Jqi14zTRbuKpcZwJqFuksqApm9MZjANUVIKd+OX+a/w+MFNclCYc5fCSvevwVFq7kHlQNjPZ+7mGfCw3rlzxYeK50pUDxa4KFZXArsTNZ+IpN8CcWARAmeGhV8wuqaHMhS9vlpDeH/khON3tp/v9ve97ncPPq3Wsoy20jbooRQfoEH1Fx2iEWPQxyqN5JOJBPItVrK+kcbTyvEP/RLz4CxSp3PE=</latexit>

inf

sup

A2A {Ci }n

sup

sup

n
n
i=1 ✓C {Oi }i=1 ✓O 2 {fi }i=1 ✓Fµ,L

T✏ (A, {(fi , Ci )}ni=1 )• The lower bound and upper bound are nearly matched<latexit sha1_base64="1gpI8GDwc1SFdbqG8ISbFS1FxJc=">AAADGHictVJdaxQxFM2MX3X92uqjL8FF2aW4zJSivghFEXwQWsFtC5vtkslmZkPzMSZ3xCXMz/DFv+KLD4r42jf/jZnZEWrrqxdCDufec3Nyk6yUwkGS/IriS5evXL22cb134+at23f6m3cPnKks4xNmpLFHGXVcCs0nIEDyo9JyqjLJD7OTl03+8AO3Thj9DlYlnylaaJELRiFQ881ojImisMwy/6qe5kOypOA/1qPH+TFxQO0M40fPsSd7ihe0JpLnMCS5pcwTJwpFj7drT1SFNeGlE9LoGm/hYbpFTCMYEffegl8L3rSVdWiiz/ZJA/1HS6woljDqNky00ZXKuMWE9IINAkIuuG8NMyr9Xt05wv/dEu72eX+QjJM28EWQdmCAutif90/JwrBKcQ1MUuemaVLCzFMLgkle90jleEnZCS34NEBNFXcz3z5sjR8GZoFzY8PSgFv2rMJT5dxKZaGymYk7n2vIf+WmFeTPZl7osgKu2fqgvJIYDG5+CV4IyxnIVQCUWRG8YrakYTYQ/lIvDCE9f+WL4GB7nD4Z77zdGey+6Maxge6jB2iIUvQU7aLXaB9NEIs+RV+ib9H3+HP8Nf4R/1yXxlGnuYf+ivj0N4nnAG0=</latexit>

E[f (x̂)f ?] = ⌦
= Õ

s

✓ ◆!
L
1
+ (1 + !)
ln
µn✏
µ
✏
s
✓ ◆!
2
L
1
+ (1 + !)
ln
µn✏
µ
✏
2

• The established lower bound is tight. Our algorithm is optimal.
Center of Machine Learning Research< 38 >

PART 05
Empirical Studies

Least square with synthetic data

Center of Machine Learning Research< 40 >

Logistic regression with synthetic data

Center of Machine Learning Research< 41 >

PART 05
More resultsUnbiased compression on generally-convex and non-convex scenarios• We also study generally-convex and non-convex scenarios
Unbiased compressor• Lower bound and upper bound are nearly matched (up to logarithm terms)• The lower bound is tight. Our proposed NEOLITHIC is nearly optimalCenter of Machine Learning Research< 43 >

Contractive compression on generally-convex and non-convex scenarios• We also study generally-convex and non-convex scenarios
Contractive compressor• Lower bound and upper bound are nearly matched (up to logarithm terms)• The lower bound is tight. Our proposed NEOLITHIC is nearly optimalCenter of Machine Learning Research< 44 >

Deep learning experiments• 8 workers, 1% compression ratio (top-k compressors), minibatch=128, R=2, ResNet18/ResNet20

Center of Machine Learning Research< 45 >

Deep learning experiments• 8 workers; 4-bit quantization (unbiased); minibatch=128; R=2

Table 2: Accuracy comparison with di↵erent algorithms on CIFAR-10.
Methods

ResNet18

ResNet20

PSGD
QSGD
MEM-SGD
Double-Squeeze
NEOLITHIC

93.99 ± 0.52
92.86 ± 0.34
94.47 ± 0.27
93.35 ± 0.39
93.87 ± 0.46

91.62 ± 0.13
90.24± 0.22
91.36 ± 0.07
90.89 ± 0.14
91.25 ± 0.14

Center of Machine Learning Research< 46 >

Summary•Compression is critical to save communication in distributed learning•

We establish the optimal complexity for distributed learning with communication compression•

We propose NEOLITHIC to nearly attain this optimal complexity•

Our results hold for non-convex, generally-convex, and strongly-convex scenarios

Center of Machine Learning Research< 47 >

References

X. Huang, Y. Chen, W. Yin, K. Yuan, "Lower Bounds and Nearly Optimal Algorithms in Distributed Learningwith Communication Compression", NeurIPS 2022

Y. He, X. Huang, Y. Chen, W. Yin, K. Yuan, “Lower Bounds and Accelerated Algorithms in Distributed
Optimization with Communication Compression”, arXiv 2305.07612

Center of Machine Learning Research< 48 >

Thank you!
Kun Yuan homepage: https://kunyuan827.github.io/
We have openings for PhD students and PostDocs