Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression

Introduction

Large-scale optimization is a critical step in many machine learning applications. Millions or even billions of data samples contribute to the excellent performance in tasks such as robotics, computer vision, natural language processing, healthcare, and so on. However, such a scale of data samples and model parameters leads to enormous communication that hampers the scalability of distributed machine-learning training systems. We urgently need communication-reduction strategies. State-of-the-art strategies include communication compression , decentralized communication , lazy communication , and beyond. This article will focus on the former.

The most common method of distributed training is Parallel SGD (P-SGD) . In P-SGD, the stochastic gradients that workers transmit to a server cause significant communication overhead in large-scale machine learning. To reduce this overhead, many recent works propose to compress the messages sent unidirectionally from workers to server or compress the messages between them bidirectionally . The method of compression is either sparsification or quantization or their combination . The literature reveals that bidirectional compression can save more communication, but leads to slower convergence rates.

Despite the quick progress made in compression techniques and their convergence, we do not yet understand the limits of algorithms with communication compression. Since unbiased and contractive compressibilities are the two representative characteristics, we use them to generally theorize two types of compressors. For each type, we intend to answer:

What is the optimal convergence rate that a distributed algorithm can achieve when using any compressor of this type?

Here, we assume that only unbiased compressibility or contractive compressibility can be utilized, not considering any additional special compressor design; after all, any special design in the literature has been heuristic, whose effectiveness can be explained at best and not proved or quantified. So, we further clarify our question: Given a class of optimization problems (specified below) and a type of compressors, if we choose the worst combination of them to defeat an algorithm, what will the convergence rate that the best-defending algorithm can reach? To our knowledge, they are fundamental questions not addressed yet.

This paper clarifies these open questions by providing lower bounds under the non-convex smooth stochastic optimization setting, and developing effective algorithms that match the lower bounds up to logarithm factors. In particular, our contributions are:

We establish convergence lower bounds for distributed algorithms with communication compression in the stochastic non-convex regime. Our lower bounds apply to any algorithm conducting unidirectional or bidirectional compression with unbiased or contractive compressors. We find a clear gap between the established lower bounds and the existing convergence rates.

We propose a novel nearly optimal algorithm with compression (NEOLITHIC) to fill in this gap. NEOLITHIC can adopt either unidirectional or bidirectional compression, and is compatible with both unbiased and contractive compressors. Using any combination, NEOLITHIC provably matches the above lower bound, under an additional mild assumption and up to logarithmic factors.

The convergence results of NEOLITHIC imply that algorithms using biased contractive compressors bidirectionally can theoretically converge as fast as those with unbiased compressors used unidirectionally (see discussion in Remark 2). Before out work, it is only established in that, for convex problems and unbiased compressors, algorithms with bidirectional compression can match with the counterparts with unidirectional compression.

We provide extensive experimental results to validate our theories.

All established results in this paper as well as convergence rates of existing state-of-the-art distributed algorithms with communication compression are listed in Table 1. The transient complexity, which measures how sensitive the algorithm is to the compression strategy (see Section 3), is also listed in the table. The smaller the transient complexity is, the faster the algorithm converges.

2 Related Works.

Distributed learning has been increasingly useful in training large-scale machine learning models . It typically follows a centralized or decentralized setup. Centralized approaches , with P-SGD as the representative, require a global averaging step per iteration in which all workers need to synchronize with a central server. Decentralized approaches, however, are based on neighborhood averaging in which each worker only needs to synchronize with its immediate neighbors. The local interaction between directly-connected workers can save remarkable communication overhead compared to the remote communication between a worker and the central server. Well-known decentralized algorithms include decentralized SGD , D2, and stochastic gradient tracking , and their momentum variants . The lazy communication is also utilized to reduce communication overhead in which workers conduct multiple local updates before sending messages. Lazy communication is also widely used in federated learning .

Communication compression.

To alleviate the communication overhead when transmitting the full model or stochastic gradient in distributed learning, communication compression is proposed in literature with two mainstream approaches: quantization and sparsification. Quantization is essentially an unbiased operator with random noise. For example, develop Sign-SGD by using only $1$ bit for each entry whose convergence is studied in . Q-SGD , as a generalized variant of Sign-SGD, compresses each entry with more flexible bits and enables a trade-off between convergence rates and communication costs. Sparsification, on the other hand, amounts to a biased but contractive operator. suggest randomly dropping entries to achieve a sparse vector to communicate, while suggest to transmit a certain number of the largest elements of the full model or gradient. The theories behind contractive compressors are limited to those in due to analysis challenges, and they are established with assumptions such as bounded gradients or quadratic loss functions . More discussions on unbiased and biased compressors can be found in . Communication compression can also be combined with other communication-saving techniques such as decentralization .

Error compensation.

The error compensation (feedback) mechanism is introduced by to mitigate the error caused by 1-bit quantization. study SGD with error-compensated quantization for quadratic functions with convergence guarantees. show that error compensation can reduce quantization-incurred errors for strongly convex loss functions in the single-node setting. However, their analysis is restricted to compressors with expectation compression error no larger than the magnitude of the input vector, which is not applicable to general contractive compressors, such as . Error-compensated SGD is studied in for non-convex loss functions with no establishment of an improved convergence rate. A recent work gives the first algorithm EF21, in the deterministic regime, using unidirectional compression with contractive compressors that rely only on standard assumptions. The later work extends EF21 to the stochastic regime but cannot show linear speedup in terms of the number of workers.

Lower bounds in optimization.

Lower bounds are well studied in convex optimization especially when there is no gradient stochasticity . In non-convex optimization, propose a zero-chain model and show a tight bound for first-order methods. By splitting the zero-chain model into multiple components, extend the approach to finite sum and stochastic problems. Recently, show the lower bounds in the decentralized stochastic setting by assigning disjoint components of the model to remote nodes in the graphs. For distributed learning with communication compression, a useful work establishes a lower bound for unidirectional/bidirectional compression for strongly convex problems with fixed learning rates and unbiased compressors. There are limited studies on lower bounds for non-convex distributed learning with unbiased/contractive compressions.

Problem Setup

In this section, we introduce the notations and assumptions used throughout the paper. We consider standard distributed learning with $n$ parallel workers. The data in worker $i$ follow a local distribution $D_{i}$, which can be heterogeneous among all workers. These workers, together with a central parameter server, collaborate to train a model by solving

Each local objective $f_{i}$ has $L$-Lipschitz gradient, i.e.,

Gradient oracle class.

We assume each worker $i$ has access to its local gradient $\nabla f_{i}(x)$ via a stochastic gradient oracle $O_{i}(x;\zeta_{i})$ subject to independent randomness $\zeta_{i}$, e.g., the mini-batch sampling $\zeta_{i}\triangleq\xi_{i}\sim D_{i}$. We further assume that the output $O_{i}(x,\zeta_{i})$ is an unbiased estimator of the full-batch gradient $\nabla f_{i}(x)$ with a bounded variance. Formally, we let the stochastic gradient oracle class $O_{\sigma^{2}}$ denote the set of all oracles $O_{i}$ satisfying Assumption 2.

Compressor class.

The two widely-studied classes of compressors in literature are i) the $\omega$-unbiased compressor, described by Assumption 3, e.g., the stochastic quantization operator , and ii) the $\delta$-contractive compressor, described by Assumption 4, e.g., the rand-$k$ operator and top-$k$ operator .

for constant $\omega\geq 0$, where the expectation is taken over the randomness of the compression operator $C$.

for constant $\delta\in(0,1]$, where the expectation is taken over the randomness of the compression operator $C$.

We let ${\mathcal{U}}_{\omega}$ and ${\mathcal{C}}_{\delta}$ denote the set of all $\omega$-unbiased compressors and $\delta$-contractive compressors satisfying Assumptions 3 and 4, respectively. Note that the identity operator $I$ satisfies $I\in{\mathcal{U}}_{\omega}$ for all $\omega\geq 0$ and $I\in{\mathcal{C}}_{\delta}$ for all $\delta\in(0,1]$. Generally, an $\omega$-unbiased compressor is not necessarily contractive when $\omega$ is larger than $1$. However, since $C\in{\mathcal{U}}_{\omega}$ implies $(1+\omega)^{-1}C\in{\mathcal{C}}_{(1+\omega)^{-1}}$, the scaled unbiased compressor is contractive though the converse may not hold. Hence, the class of contractive compressors is strictly richer since it contains all unbiased compressors through scaling.

Algorithm class.

We consider a centralized and synchronous algorithm $A$ in which i) workers are allowed to communicate only directly with the central server but not between one another; ii) all iterations are synchronized, meaning that all workers start each of their iterations simultaneously. Each worker $i$ holds a local copy of the model, denoted by $x_{i}^{(t)}$, at iteration $t$. The output $\hat{x}^{(t)}$ of $A$ after $t$ iterations can be any linear combination of all previous local models, namely,

We further require algorithms $A$ to satisfy the so-called “zero-respecting” property, which appears in (see formal definition in Appendix A.1). This property implies that the number of non-zero entries of the local model of a worker can be increased only by conducting local stochastic gradient queries or synchronizing with the server. The zero-respecting property holds with all algorithms in Table 1 and most first-order methods based on SGD . In addition to these properties, algorithm $A$ has to admit communication compression. Specifically, we endow the server with a compressor $C_{0}$ and each worker $i\in\{1,\cdots,n\}$ with a compressor $C_{i}$. If $C_{i}=I$ for some $i\in\{0,\cdots,n\}$, then worker $i$ (or the server if $i=0$) conducts lossless communication. When $C_{i}\neq I$ for any $i\in\{0,\cdots,n\}$, algorithm $A$ conducts bidirectional compression. When $C_{0}=I$, algorithm $A$ conducts unidirectional compression on messages from workers to server. The definition of the algorithm class with bidirectional/unidirectional compression is as follows.

Given compressors $\{C_{0},C_{1},\dots,C_{n}\}$, write ${\mathcal{A}}^{B}_{\{C_{i}\}_{i=0}^{n}}$ for the set of all centralized, synchronous, zero-respecting algorithms admitting bidirectional compression in which i) compressor $C_{i}$, $\forall\,i\in\{1,\dots,n\}$, is applied to messages from worker $i$ to the server, and ii) compressor $C_{0}$ is applied to messages from the server to all workers.

Lower Bounds

With all interested classes introduced above, we are ready to define the lower bound measure. Given local loss functions $\{f_{i}\}_{i=1}^{n}\subseteq{\mathcal{F}}_{\Delta,L}$, stochastic gradient oracles $\{O_{i}\}_{i=1}^{n}\subseteq{\mathcal{O}}_{\sigma^{2}}$ (with $O_{i}$ for worker $i$), compressors $\{{\mathcal{C}}_{i}\}_{i=0}^{n}\subseteq{\mathcal{C}}$ (with ${\mathcal{C}}$ being either ${\mathcal{U}}_{\omega}$ or ${\mathcal{C}}_{\delta}$), and an algorithm $A\in{\mathcal{A}}$ to solve problem (1) (with ${\mathcal{A}}$ being either ${\mathcal{A}}^{B}_{\{C_{i}\}_{i=0}^{n}}$ or ${\mathcal{A}}^{U}_{\{C_{i}\}_{i=1}^{n}}$), we let $\hat{x}_{{A},\{f_{i}\}_{i=1}^{n},\{O_{i}\}_{i=1}^{n},\{C_{i}\}_{i=0}^{n},T}$ denote the output of algorithm $A$ using no more than $T$ gradient queries and rounds of communication by each worker node. We define the minimax measure as

In (2), we do not require the compressors $\{C_{i}\}_{i=0}^{n}$ to be distinct or independent. When ${\mathcal{C}}$ is ${\mathcal{U}}_{\omega}$ or ${\mathcal{C}}_{\delta}$, we allow the compressor parameter $\omega$ or $\delta$ to be accessible by algorithm $A$.

Our first result is for algorithms that admit unidirectional compression and $\omega$-unbiased compressors.

For every $\Delta,\,L>0$, $n\geq 2$, $\omega\geq 0$, $\sigma>0$, $T\geq(1+\omega)^{2}$, there exists a set of local loss functions $\{f_{i}\}_{i=1}^{n}\subseteq\mathcal{F}_{\Delta,L}$, stochastic gradient oracles $\{O_{i}\}_{i=1}^{n}\subseteq\mathcal{O}_{\sigma^{2}}$, $\omega$-unbiased compressors $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{U}}_{\omega}$ with $C_{0}=I$, such that for any algorithm $A\in\mathcal{A}^{U}_{\{C_{i}\}_{i=1}^{n}}$ starting from a given constant $x^{(0)}$, it holds that (proof is in Appendix A.3)

The bound in (3) is consistent with best-known lower bounds in different settings. When $\omega=0$, our result reduces to the tight bound for distributed training without compression . When $n=1$ and $\omega=0$, our result reduces to the lower bound established in under the single-node non-convex stochastic setting. When $n=1,\omega=0$ and $\sigma^{2}=0$, our result recovers the tight bound for deterministic non-convex optimization .

Linear-speedup.

When $T$ is sufficiently large, the first term $1/\sqrt{nT}$ dominates the lower bound (3). If an algorithm achieves an $O(1/\sqrt{nT})$ rate, it will require $T=O(1/(n\epsilon^{2}))$ gradient queries to reach a desired accuracy $\epsilon$, which is inversely proportional to $n$. Therefore, an algorithm achieves linear-speedup at $T$-th iteration if, for this $T$, the term involving $nT$ is dominating the rate.

Transient complexity.

Due to the compression-incurred overhead in convergence rate, a distributed stochastic algorithm with communication compression has to experience a transient stage to achieve its linear-speedup stage. Transient complexity are referred to the number of gradient queries (or communication rounds) when $T$ is relatively small so non-$nT$ terms still dominate the rate. The smaller the transient complexity is, the less gradient queries or communication rounds the algorithm requires to achieve linear-speedup stage. For example, if an algorithm can achieve the lower bound established in (3), it requires $(\frac{\Delta L\sigma^{2}}{nT})^{\frac{1}{2}}\geq\frac{(1+\omega)\Delta L}{T}$, i.e., $T=\Omega(n(1+\omega)^{2})$ transient gradient queries (or communication rounds) to achieve linear-speedup, which is proportional to the compression-related terms $(1+\omega)^{2}$. Here we mainly care about the orders with respect to $n$ and $\omega$ (or $\delta$ below) in transient complexity to evaluate how sensitive the algorithm is to compression. Transient complexity is also widely used in decentralized learning to gauge how network topology can influence the convergence rate.

2 Bidirectional Unbiased Compression

Theorem 1 applies to unidirectional compression where $C_{0}=I$. We next consider bidirectional compression with $C_{0}\in{\mathcal{U}}_{\omega}$. Since $\{C_{i}\}_{i=1}^{n}\subseteq{\mathcal{U}}_{\omega}$ with $C_{0}=I$ is a special case of $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{U}}_{\omega}$, the lower bound for algorithms that admit bidirectional compression is greater than or equal to that with unidirectional compression by following the definition of the measure in (2).

Under the same setting as in Theorem 1, there exists a set of local objectives $\{f_{i}\}_{i=1}^{n}\subseteq\mathcal{F}_{\Delta,L}$, stochastic gradient oracles $\{O_{i}\}_{i=1}^{n}\subseteq\mathcal{O}_{\sigma^{2}}$, $\omega$-unbiased compressors $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{U}}_{\omega}$ such that for any algorithm $A\in\mathcal{A}^{B}_{\{C_{i}\}_{i=0}^{n}}$ starting from $x^{(0)}$, the lower bound in (3) is also valid.

Theorem 1 and Corollary 1 indicate that distributed learning with both unidirectional and bidirectional communication compression share the same lower bound. It is intuitive since unidirectional compression is just a special case of bidirectional compression by letting $C_{0}=I$.

3 Unidirectional Contractive Compression

To obtain lower bounds for contractive compressors, we need the following lemma [54, Lemma 1].

It holds that $\delta\,{\mathcal{U}}_{\delta^{-1}-1}\triangleq\{\delta\,C:C\in{\mathcal{U}}_{\delta^{-1}-1}\}\subseteq{\mathcal{C}}_{\delta}$.

The above Lemma reveals that any $(\delta^{-1}-1)$-unbiased compressor is $\delta$-contractive when scaled by $\delta$. Therefore, if an algorithm $A$ admits all $\delta$-contractive compressors, it automatically admits all compressors in $\delta\,{\mathcal{U}}_{\delta^{-1}-1}$ due to Lemma 1. This relation, together with Theorem 1, helps us achieve the following lower bound with respect to $\delta$-contractive compressors.

For every $\Delta,\,L>0$, $n\geq 2$, $0<\delta\leq 1$, $\sigma>0$, $T\geq\delta^{-2}$, there exists a set of loss objectives $\{f_{i}\}_{i=1}^{n}\subseteq\mathcal{F}_{\Delta,L}$, a set of stochastic gradient oracles $\{O_{i}\}_{i=1}^{n}\subseteq\mathcal{O}_{\sigma^{2}}$, a set of $\delta$-contractive compressors $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{C}}_{\delta}$ with $C_{0}=I$, such that for any algorithm $A\in\mathcal{A}^{U}_{\{C_{i}\}_{i=0}^{n}}$ starting from $x^{(0)}$, it holds that (proof is in Appendix A.4)

Transient complexity. With the discussion on transient complexity in Section 3.1, it is easy to derive the transient iteration complexity as $\Omega(n/\delta^{2})$ for the lower bound with $\delta$-contractive compressors.

4 Bidirectional Contractive Compression

Noting that $\{C_{i}\}_{i=1}^{n}\subseteq{\mathcal{C}}_{\delta}$ with $C_{0}=I$ is a special case of $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{C}}_{\delta}$, we can also establish the lower bound for algorithms that admit bidirectional compression and contractive compressors.

Under the same settings as in Theorem 2, there exists a set of loss objectives $\{f_{i}\}_{i=1}^{n}\subseteq\mathcal{F}_{\Delta,L}$, a set of stochastic gradient oracles $\{O_{i}\}_{i=1}^{n}\subseteq\mathcal{O}_{\sigma^{2}}$, a set of $\delta$-contractive compressors $\{C_{i}\}_{i=1}^{n}\subseteq{\mathcal{C}}_{\delta}$, such that for any algorithm $A\in\mathcal{A}^{B}_{\{C_{i}\}_{i=0}^{n}}$ starting form $x^{(0)}$, the lower bound (4) is also valid.

NEOLITHIC: A Nearly Optimal Algorithm

Comparing the best-known upper bounds listed in Table 1 with the established lower bounds in (3) and (4), we find existing algorithms may be sub-optimal. There exists a clear gap between their convergence rates and our established lower bounds. In this section, we propose NEOLITHIC to fill in this gap. Its rate will match the lower bounds established in (3) and (4) up to logarithm factors. NEOLITHIC can work with both unidirectional and bidirectional compressions, and it is compatible with both unbiased and contractive compressors. NEOLITHIC will be discussed in detail with bidirectional contractive compression in this section. It is easy to be adapted to other settings by simply removing the compression on the server side or utilizing unbiased compressors with proper scaling.

NEOLITHIC is built on a communication compression module listed in Algorithm 1, which we call fast compressed communication (FCC). Given an input vector $v^{(k,\star)}$ to communicate in the $k$-th iteration, FCC first initializes $v^{(k,0)}=0$ and then recursively compresses the residual with $c^{(k,r)}\triangleq C(v^{(k,\star)}-v^{(k,r)})$ and sends it to the receiver for $R$ consecutive rounds, see the main recursion in Algorithm 1. When FCC module ends, the sender will transmit a set of compressed variables $\{c^{(k,r)}\}_{r=0}^{R-1}$ to the receiver, and return $v^{(k,R)}=\sum_{r=0}^{R-1}c^{(k,r)}$ to itself. Quantity $v^{(k,R)}$ can be regarded as a compressed vector of original input $v^{(k,\star)}$ after FCC operation.

When $R=1$, the above FCC property (5) reduces to Assumption 4 for standard contractive compressors. When $R$ is large, FCC can output $v^{(k,R)}$ endowed with very small compression errors. The FCC protocol is also closely related to EF21 compression strategy If the roles of $v$ and $v^{\star}$ in Eq. (8) of are switched, we can get the single round of FCC recursions.. However, the major novelty of FCC is to utilize multiple such compression rounds to help develop algorithms that can nearly match the established lower bounds.

2 NEOLITHIC Algorithm

NEOLITHIC is described in Algorithm 2. The FCC module in NEOLITHIC communicates $R$ rounds per iteration. To balance gradient queries and communication rounds, NEOLITHIC will query $R$ stochastic gradients per iteration, see the gradient accumulation step in Algorithm 2. Compared to other algorithms listed in Table 1, the proposed NEOLITHIC takes $R$ times more gradient queries and communication rounds than them per iteration. Given the same budgets to query gradient oracles and conduct communication as the other algorithms, say $T$ times on each worker, we shall consider $K=T/R$ iterations in NEOLITHIC for fair comparison.

We introduce the following assumption to establish the convergence rates of NEOLITHIC.

There exists some $b^{2}\geq 0$ such that

When local distributions $D_{i}$ are identical across all workers, we have $f_{i}(x)=f(x)$ for each $i\in\{1,\dots,n\}$ and the above assumption will always hold. We first establish the convergence rate of NEOLITHIC using bidirectional compression with contractive compressors.

Given constants $n\geq 1$, $\delta\in(0,1]$ and Assumption 5, and let $x^{(k)}$ be generated by Algorithm 2. If $R=\lceil\frac{\max\{\ln\left({\delta T\max\{b^{2},\sigma^{2}\delta\}}/{\Delta L}\right),\ln(8)\}}{\delta}\rceil$ and the learning rate is set as in Appendix B.2, it holds for any $K\geq 0$ and compressors $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{C}}_{\delta}$ that (proof is in Appendix B.2)

When $\{C_{i}\}_{i=0}^{n}$ are $\omega$-unbiased compressors, we utilize the fact that $(1+\omega)^{-1}C_{i}$ is $(1+\omega)^{-1}$-contractive for all $i\in\{0,\dots,n\}$ to derive that

Under the same assumptions as in Theorem 3, it holds for any $K\geq 0$ and compressors $\{C_{i}\}_{i=0}^{n}\subseteq{\mathcal{U}}_{\omega}$ that

The convergence rates established in Theorem 3 and Corollary 3 are also valid for unidirectional compression when $C_{0}=I$. They can match the lower bounds established in Section 3 up to logarithm factors. Moreover, these rates are faster than other algorithms listed in Table 1.

While our analysis relies on Assumption 5, the rates in Theorem 3 and Corollary 3 are polynomially independent of $b^{2}$. These results also imply that NEOLITHIC with bidirectional compression can perform as fast as its counterpart with unidirectional compression. In other words, imposing bidirectional compression can save communications in NEOLITHIC without hurting convergence rates. Before our work, it is established in literature that bidirectional compression leads to slower convergence than unidirectional compression. Our results also imply that, given $\delta=(1+\omega)^{-1}$, well-designed algorithms such as NEOLITHIC with $\delta$-contractive compressors can converge as fast as their counterparts using $\omega$-unbiased compressors despite unbiasedness. Before our work, the analysis based on unbiased compressors exhibits theoretically faster convergence for non-convex problems.

We remark that Assumption 5 is not required to obtain the lower bounds in Section 3. It is not known whether the lower bounds established in Section 3 can be achieved by NEOLITHIC when Assumption 5 does not hold. However, it is worth noting that Assumption 5 is already milder than those made in most works such as bounded gradients. To our best knowledge, only EF21-SGD is guaranteed to converge without Assumption 5, which, however, leads to a fairly loose convergence rate (see Table 1) that cannot show linear-speedup $O(1/\sqrt{nT})$.

Experiments

This section empirically investigates the performance of different compression algorithms with both synthetic simulation and deep learning tasks. We compare NEOLITHIC with P-SGD and its variants with communication compression: MEM-SGD, Double-Squeeze, and EF21-SGD.

We consider the following least-square problem:

Logistic regression.

We consider the following logistic regression problem:

2 Deep Learning Tasks

We implement all compression algorithms with PyTorch 1.8.2 using NCCL 2.8.3 (CUDA 10.1) as the communication backend. For P-SGD, we used PyTorch’s native Distributed Data Parallel (DDP) module. All deep learning training scripts in this section run on a server with 8 NVIDIA V100 GPUs in our cluster and each GPU is treated as one worker.

Image classification.

We investigate the performance of the aforementioned methods with CIFAR-10 dataset. For CIFAR-10 dataset, it consists of 50,000 training images and 10,000 validation images categorized in 10 classes. We utilize two common variants of ResNet model on CIFAR-10 (ResNet-20 with roughly 0.27M parameters and ResNet-18 with 11.17M parameters). We train total 300 epochs and set the batch size to 128 on every worker. The learning rate is set to 5e-3 for single worker and warmed up in the first 5 epochs and decayed by a factor of 10 at 150 and 250-th epoch.

All experiments were repeated three times with different seeds. For NEOLITHIC, we set $R=2$. Following previous works , we use top-$k$ compressor with different compression ratio to evaluate the performance of the aforementioned methods. As shown in Figure 2, Tables 2 and Table 3, NEOLITHIC consistently outperforms other compression methods and reaches the similar performance to P-SGD. It is worth noting that EF21-SGD, while guaranteed to converge with milder assumptions than ours, does not provide competitive performance in deep learning tasks listed in Tables 2, 3, and 4. We find our reported result for EF21-SGD is consistent with Figure 7 (the left plot) in .

The effect of compression ratio.

We also investigate the influence of different compression ratios. Table 3 is with a compression ratio of 1%, which indicates a harsher setting for compression methods. It is observed that NEOLITHIC still outperforms other compression methods.

Performance with heterogeneous data.

We simulate data heterogeneity among workers via a Dirichlet distribution-based partition with parameter $\alpha$ controlling the data heterogeneity. The training data for a particular class tends to concentrate in a single node as $\alpha\rightarrow 0$, i.e. becoming more heterogeneous, while the homogeneous data distribution is achieved as $\alpha\rightarrow\infty$. We test $\alpha=1$ and $10$ in Table 4 for all compared methods as corresponding to a setting with high/low heterogeneity.

Effects of accumulation rounds.

We also empirically evaluate the performance of NEOLITHIC with different choice of parameter $R$ in deep learning tasks. NEOLITHIC have slightly performance degradation in both compression scenarios as $R$ scales up. We conjecture that the gradient accumulation step, which amounts to using large-batch samples in gradient evaluation, can help in the optimization and training stage as proved in this paper, but it may hurt the generalization performance. We recommend using NEOLITHIC in applications that are friendly to large-batch training.

Conclusion

This paper provides lower bounds for distributed algorithms with communication compression, whether the compression is unidirectional or bidirectional and unbiased or contractive. An algorithm called NEOLITHIC is introduced to match the lower bounds under the assumption of bounded gradient dissimilarity. Future directions include developing optimal algorithms without the assumption, as well as discovering additional compression properties that might produce a better lower bound.

Acknowledgements

The authors are grateful to Professor Peter Richtarik from KAUST for the helpful discussions in the relation between FCC and EF21 and various other useful suggestions.

References

Appendix A Lower Bounds

In this section, we provide the proofs for Theorem 1 and 2. To proceed, we first introduce the zero-respecting property and zero-chain functions.

Now we consider the setup of distributed learning with communication compression. For each worker $i$ and $t\geq 1$, we let $y^{(t)}_{i}$ be the $t$-th variable at which worker $i$ queries its gradient oracle (with independent randomness $\zeta^{(t)}_{i}$) during the optimization procedure. We also let $x^{(t)}_{i}$ be the local model that worker $i$ produces after the $t$-th query. Note that $y^{(t)}_{i}$ is not necessarily the last-step local model $x^{(t-1)}_{i}$; it can be any auxiliary vector.

Following the above description, we now extend the zero-respecting property , which firstly appears in single-node stochastic optimization, to distributed learning with communication compression:

We say a distributed algorithm $A$ is zero-respecting if for any $t\geq 1$ and $1\leq k\leq d$, the following requirements are satisfied:

If worker $i$ queries at $y^{(t)}_{i}$ with $[y^{(t)}_{i}]_{k}\neq 0$, then one of the following must be true:

If the local model $x^{(t)}_{i}$ of worker $i$, after the $t$-th query, has $[x^{(t)}_{i}]_{k}\neq 0$, then one of the following must be true:

In essence, the above zero-respecting property requires that any expansion of non-zero coordinates in $x^{(t)}_{i}$, $y^{(t)}_{i}$, and other related vectors in worker $i$ is attributed to its historical local gradient updates, local compressions, or synchronization with the server. Meanwhile, it also requires that any expansion of non-zero coordinate in vectors held in the server is due to its own compression operation, or receiving compressed messages from workers.

To better illustrate the zero-respecting property, we take MEM-SGD as an example and show how it satisfies the zero-respecting property. MEM-SGD is listed in Algorithm 3, which conducts unidirectional compression. Following the notations in Definition 2, for any $t\geq 1$ and $1\leq i\leq n$, we have for MEM-SGD

For point 1, for any $1\leq k\leq d$, $[y^{(t)}_{i}]_{k}\neq 0$ is equivalent to $[x^{(t-1)}_{i}]_{k}\neq 0$.

While we only validate the zero-respecting property in MEM-SGD, one can easily follow the above procedure to verify that other algorithms, including those listed in Table 1, are zero-respecting. In fact, to our knowledge, the zero-respecting property is satisfied by all existing distributed algorithms with communication compression.

A.2 Zero-Chain Functions

We next introduce zero-chain functions, which can be combined with the zero-respecting property discussed in Appendix A.1 to prove the lower bounds for distributed learning under communication compression. As described in , a zero chain function $f$ satisfies

which implies that, starting from $x=0$, a single gradient evaluation can only make at most one more coordinate of the model parameter $x$ be non-zero.

We state some key zero-chain functions that will be used to facilitate the analysis.

The function $h(x)$ satisfies the following properties:

then $h_{1}$ and $h_{2}$ satisfy the following properties:

$\frac{1}{2}(h_{1}+h_{2})=h$, where $h$ is defined in Lemma 3.

$h_{1}$ and $h_{2}$ are also $L_{0}$-smooth with ${L_{0}}=152$.

where $\psi^{\prime}(z)$ and $\psi^{\prime\prime}(z)$ are the first- and second-order derivative of $\psi(z)$, respectively, $\phi^{\prime}(z)$ and $\phi^{\prime\prime}(z)$ are the first- and second-order derivative of $\phi(z)$, respectively, and the last inequality follows Observation 2 of that

Combining (9) with (8), we know $h_{k}$ is $L_{0}$-smooth for $k=1,2$. ∎

A.3 Proof of Theorem 1

Without loss of generality, we assume algorithms to start from $x^{(0)}=0$. We prove the two terms in the lower bound established in Theorem 1 separately by constructing two hard-to-optimize examples. The construction of the example, for each term in (3), can be conducted in three steps: 1) constructing local functions $\{f_{i}\}_{i=1}^{n}$ by following Lemma 3 and 4; 2) constructing compressors $\{C_{i}\}_{i=1}^{n}\subseteq{\mathcal{U}}_{\omega}$ and independent oracles $\{O_{i}\}_{i=1}^{n}\subseteq{\mathcal{O}}_{\sigma^{2}}$ that hamper algorithms to expand the non-zero coordinates of model parameters; 3) establishing a limitation, in terms of the non-zero coordinates of model parameters, for zero-respecting algorithms utilizing the predefined compression protocol with $T$ gradient queries and compressed communications on each worker, and finally we translate this limitation into the lower bound of convergence rate.

The proof of the first term $\Omega((\frac{\Delta L\sigma^{2}}{nT})^{\frac{1}{2}})$ is adapted from the first example in proving Theorem 1 of .

(Step 1.) Let $f_{i}=L\lambda^{2}h(x/\lambda)/L_{0}$, $\forall\,i=1,\dots,n$ be homogeneous and hence $f=L\lambda^{2}h(x/\lambda)/L_{0}$ where $h$ is defined in Lemma 3 and $\lambda>0$ is to be specified. Since $\nabla^{2}f_{i}=L\nabla^{2}h/L_{0}$ and $h$ is $L_{0}$-smooth (Lemma 3), we know $f_{i}$ is $L$-smooth for any $\lambda>0$. By Lemma 3, we have

Therefore, to ensure $f_{i}\in{\mathcal{F}}_{\Delta,L}$, it suffices to let

(Step 2.) We assume all compressors $\{C_{i}\}_{i=1}^{n}$ to be identities, meaning that there is no compression error in the entire optimization procedure. It naturally follows that $\{C_{i}\}_{i=1}^{n}\subseteq{\mathcal{U}}^{\omega}$ for any $\omega\geq 0$. We construct the stochastic gradient oracle $O_{i}$ on worker $i$, $\forall\,i=1,\dots,n$ as follows:

where $\mathds{1}(E)$ is the indicator of event $E$.

It is easy to see that $O_{i}$ is an unbiased stochastic gradient oracle. Moreover, since $f_{i}$ is zero-chain, by (11) and the definition of $O_{i}$, we have

Therefore, to ensure $O_{i}\in{\mathcal{O}}_{\sigma^{2}}$, it suffices to let

(Step 3.) Let $y^{(t)}_{i}$, $\forall\,t\geq 1$ and $1\leq i\leq n$, be the $t$-th variable at which worker $i$ queries gradient from oracle $O_{i}$, and let $x^{(t)}_{i}$ be the local model it produces after the $t$-th query. Let

be the final algorithm output after $T$ gradient queries on each worker. Since algorithms satisfy the zero-respecting property, as discussed in Appendix A.1, it holds that $[\hat{x}]_{k}\neq 0$ implies at least one $[x^{(t)}_{i}]_{k}$, where $0\leq t\leq T$, is non-zero, which further implies at least one $[O_{i}(y^{(t)}_{i};\zeta_{i}^{(t)})]_{k}$ is non-zero. Therefore, by considering the index of the last non-zero coordinate of $\hat{x}$ and using (11), we have

Similarly, considering that the non-zero coordinates of $y^{(t)}_{i}$ can be tracked back to the non-zero coordinates of past gradient queries and using (13), we have

By induction for (14) with respect to $t=1,\dots,T$, we reach

By Lemma 2 of , which is derived from the Chernoff bound, we have

Therefore, by combining (17) and (18), we have

then (10) naturally holds and $p=\min\{\frac{G_{\infty}^{2}}{\sigma^{2}}\left(\frac{\Delta L\sigma^{2}}{3nTL_{0}\Delta_{0}G_{\infty}^{2}}\right)^{\frac{1}{2}},1\}$ by (12). Without loss of generality, we assume $d\geq 2$, which is guaranteed when $T=\Omega(\frac{\sigma^{2}}{nL\Delta})$. Thus, using the definition of $p$, we have that

which, combined with (19) and that $\Delta_{0},\,L_{0},\,G_{\infty}$ are universal constants, leads to

Example 2.

Without loss of generality, we assume $n$ is even; otherwise we can consider the lower bound for the case of $n-1$.

(Step 1.) Similar to but different from the construction of Example 1, we let $f_{i}=L\lambda^{2}h_{1}(x/\lambda)/L_{0}$, $\forall\,1\leq i\leq n/2$ and $f_{i}=L\lambda^{2}h_{2}(x/\lambda)/L_{0}$, $\forall\,n/2<i\leq n$, where $h_{1}$ and $h_{2}$ are defined in Lemma 4, and $\lambda>0$ will be specified later. By the definitions of $h_{1}$ and $h_{2}$, we have that $f_{i}$, $\forall\,1\leq i\leq n$, is zero-chain and $f(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)=L\lambda^{2}h(x/\lambda)/L_{0}$. Since $h_{1}$ and $h_{2}$ are also $L_{0}$-smooth, to let $f\in{\mathcal{F}}_{\Delta,L}$, it suffices to make (10) hold.

where the last inequality follows the definition of $s$. Therefore, the above construction gives $\{C_{i}\}_{i=1}^{n}\subseteq{\mathcal{U}}_{\omega}$.

be the final algorithm output after $T$ rounds of communication on each worker. By (24), we have

Combining (26), (25), (18), and(19), we have that

then (10) naturally holds. Since $T$ is assumed to be no less than $(1+\omega)^{2}$, we have $d=\lfloor 5T/(1+\omega)\rfloor\geq 5T/(1+\omega)-1\geq 4T/(1+\omega)\geq 4(1+\omega)\geq 4$. Then it is easy to verify

which, combined with (27) and that $\Delta_{0},\,L_{0}$ are universal constants, leads to

In Example 2 in the proof of Theorem 1, it holds that

Therefore, one round of communication can increase $B^{(t)}$ at most by $1$.

A.4 Proof of Theorem 2

Theorem 2 essentially follows the same analysis as in Theorem 1. The only difference is that we shall construct compressors in proving $\Omega(\frac{\Delta L}{\delta T})$ by using the rand-$s$ operators with shared randomness and $s=\lceil\delta d\rceil$. There is no scaling procedure in compression. One can easily verify that

Appendix B Convergence of NEOLITHIC

Let $v^{(k,r)}$ be the $r$-th intermediate variable generated in FCC (i.e., Algorithm 1) for any $0\leq r\leq R$. Since $C$ is $\delta$-contractive, we have

Iterating the above inequality with respect to $r=R-1,\dots,1,0$, we reach

B.2 Proof of Theorem 3

It is observed from Algorithm 1 that the vector $v^{(k,R)}$ returned by the FCC operator satisfies

where (32) and (33) follow the implementation of Algorithm 2, and we use the notation of $\Omega^{(k)}$ in (34). ∎

Let the auxiliary sequence be $y^{(k)}:=x^{(k)}-\gamma\Omega^{(k)}$, $\forall\,k\geq 0$. Under Assumption 1, if learning rate $0<\gamma\leq\frac{1}{2L}$, it holds that for any $k\geq 0$,

By Lemma 6 and the definition of $y^{(k)}$ for $k\geq 0$, we directly have that

Since $\hat{g}_{i}^{(k)}=\frac{1}{R}\sum_{r=1}^{R}O_{i}(x^{(k)};\zeta_{i}^{(k,r)})$ is a unbiased estimator of $\nabla f_{i}(x^{(k)})$, and by Assumption 2, we have

Taking global expectation over (36), and plugging (37) and (38) into it, we reach

where we use Young’s inequality in (39), and (40) holds by Assumption 1. Using $y^{(k)}-x^{(k)}=-\gamma\Omega^{(k)}$ and that

in (40), we reach the conclusion in this lemma. ∎

Therefore, by using Young’s inequality and (38), we have

For any $1\leq i\leq n$, using the similar argument, we have that

Taking the average of (42) over all $1\leq i\leq n$, and using (43) and Assumption 5, we further have that

Since $R$ is sufficiently large such that

we have that $4(1-(1-\delta)^{R})\geq 3$ and hence

With Lemma 8, we easily reach its ergodic version:

We let $R$ sufficiently large so that $\theta\triangleq 4(1-\delta)^{R}<1$. Under Assumptions 2, 4, 5, it holds for any $K\geq 0$ that,

Let $\theta=4(1-\delta)^{R}$, then by Lemma 8 and noting $\Psi^{(0)}=0$, we have

Therefore, by taking the average of (46) over $k=0,\dots,K-1$ and using $\Psi^{(0)}=0$, we further have

Given the above lemmas, now we prove the convergence rate of NEOLITHIC.

Let the communication round be $R=\left\lceil{\max\left\{\ln\left({\delta T\max\{b^{2},\sigma^{2}\delta\}}/{\Delta L}\right),\ln(8)\right\}}/{\delta}\right\rceil$ and learning rate as in (52). Under Assumptions 1, 2, 4, 5, it holds that for any $K\geq 0$,

where $T=KR$ is the total number of gradient queries (or rounds of compressed communications) on each worker.

Averaging (35) over $k=0,\dots,K$, and using the fact that $y^{(0)}=x^{(0)}$ and $f(y^{(K+1)})\geq f^{\star}$, we have

By the definition of $\Omega^{(k)}$ and using the Young’s inequality, it holds that

Assume the learning rate $\gamma$ is sufficiently small such that

where we use $\Delta\geq f(x^{(0)})-f^{\star}$. By choosing

and hence $1-\theta=\Omega(1)$ and $\gamma$ satisfies (50). Plugging (54) and (55) into (53), and applying the notation $T=KR$, we reach

where the last inequality follows that $\theta^{\frac{1}{3}}\Delta^{\frac{2}{3}}L^{\frac{2}{3}}\max\{b^{\frac{2}{3}},\sigma^{\frac{2}{3}}\delta^{\frac{1}{3}}\}=O(\Delta L/\delta^{\frac{1}{3}}T^{\frac{1}{3}})$ because of (55). ∎

Appendix C More Details of Table 1

There exist mismatches between some rates listed in Table 1 and those established in literature. The mismatches exist because

we have strengthened the vanilla rates by relaxing their restrictive assumptions (say, Double-Squeeze) or uncovering the hidden terms (say, CSER);

we have extended the vanilla rates to the same setting as NEOLITHIC (say, extend MEM-SGD to non-convex and smooth setting, or transform QSGD to the distributed setting).

With these modifications, these baseline algorithms can be compared with NEOLITHIC in a fair manner. Next we clarify each modification one by one.

There is a slight inconsistency between the original rate in and the one listed Table 1 due to the following reasons:

We noticed that the rate stated in [31, Corollary 3] is not optimal following [31, Theorem 2] since the authors set the learning rate as $\theta\sqrt{M/T}$ where $\theta$ is a universal constant. The rate in [31, Corollary 3] can be slightly improved in terms of $\sigma^{2}$, $b^{2}$, $\Delta=f(x^{(0)})-\min_{x}f(x)$ by involving them into the learning rate. We manually optimize the learning rate by choosing $\Theta((L+(T(1+\omega)L\sigma^{2}/\Delta M)^{1/2}+(\omega LTb^{2}/n\Delta)^{1/2})^{-1})$.

$M$ is the total mini-batch size on all workers in Q-SGD (see the paragraph of contribution, page 2, ). For a fair comparison with other methods in Table 1, We set $M=n$ to make the number of total gradient queries per iteration equivalent in all algorithms.

C.2 CSER

While [68, Corollary 1] does not have a $O(1/T)$ term in the convergence rate, it does impose another condition $T\gg n$ to the convergence statement. If $T\gg n$ holds, then $1/\sqrt{nT}\gg 1/T$ and hence the $1/T$ term is dominated by $1/\sqrt{nT}$ and thus hidden in the notation $O(\cdot)$. However, the condition does not appear in the convergence theorem of NEOLITHIC. To conduct a fair comparison, we have to remove condition $T\gg n$ from its convergence theorem, which thus incurs additional $O(1/T)$ term in the rate accordingly. The rate we provided in Table 1 is hence more precise than that in .

C.3 Double-Squeeze

The original rate of Double-Squeeze established in is based on an unrealistic assumption that accumulated compression errors are bounded by unknown $\epsilon$ (see [62, Assumption 1.3]). This makes its rate incomparable with other methods. However, we can remove the unrealistic assumption and easily derive a comparable bound where $\epsilon$ can be explicitly replaced with $O(G/\delta^{2})$. We plug $O(G/\delta^{2})$ into [62, Corollary 2] to get the rate listed in our Table 1.

Iterating (56) for $t,t-1,\dots,0$ and noting $\boldsymbol{\delta}_{0}^{(i)}=0$, we reach

Again by Young’s inequality and $\delta$-contraction, we have

C.4 MEM-SGD

We notice that only the rate for strongly convex problems is established in the original MEM-SGD paper . To compare it fairly with NEOLITHIC, we derive its convergence rate in the non-convex setting by ourselves.

The key steps of our derivation are listed as follows.

The recursion formula of MEM-SGD is $\mathbf{y}_{t+1}=\mathbf{y}_{t}-\frac{\eta}{n}\sum_{i=1}^{n}\nabla f_{i}(\mathbf{x}_{t},\xi_{t}^{i})$ with $\mathbf{y}_{t}\triangleq\mathbf{x}_{t}-\frac{1}{n}\sum_{i=1}^{n}\mathbf{e}_{t}^{i}$. In fact, one can easily check that

Following the derivation of (40), one can obtain

Setting $\eta\leq\frac{1}{2L}$ such that $\frac{\eta(1-\eta L)}{2}\geq\frac{\eta}{4}$ and rearranging (61), we have

By the definition of $\mathbf{y}_{t}$ and step 1., we have

Averaging (62) with (63) plugged into, we reach

Setting the learning rate $\eta=(2L+(\frac{L\sigma^{2}}{n\Delta})^{1/2}+(\frac{L^{2}G^{2}}{\delta^{2}\Delta})^{1/3})^{-1}$ in (64) leads to the rate we listed in Table 1.

C.5 Comparison with More Algorithms

Several additional comments are as follows:

All three algorithms utilize unidirectional, unbiased, and independent compressors.

All algorithms conduct an imbalanced number of compressed communications and of gradient queries. We therefore list the communication and gradient query complexity separately in Table 6. The result of Q-SGD is slightly tuned by us, see the argument in Appendix C.1.

MARINA (with $O(1/\epsilon^{2})$) and SASHA (with $O(1/\epsilon^{3})$) have better communication complexity than QSGD (with $O(1/\epsilon^{4})$) when $\epsilon$ is sufficiently small.