SIGNGD with Error Feedback Meets Lazily Aggregated Technique: Communication-Efficient Algorithms for Distributed Learning

In the 1-bit gradient compression methodology, the $m$ -th worker only uploads the sign of the gradient computed on its portion of the data, which suggests an update of the following form:

(3) $${𝝎}^{k+1}={𝝎}^k-\gamma \cdot \underset{m=1}{\overset{M}{\sum }}sign(\nabla f_m({𝝎}^k))$$

However, Ref. [ 20 ] presented some counterexamples to substantiate that naively using such a sign-based algorithm may not generalize or even converge. The $sign$ operator misses massive information about the local gradient’s magnitude and direction.

Thus, we employ an elegant error feedback technique to fix the abovementioned problems. The error feedback technique is performed as follows: scaling the signed vector by the ${\mathrm{\ell }}_1$ -norm of the gradient to ensure the magnitude of the gradient is not forgotten; locally storing the difference between the actual and compressed gradient, and adding it back into the next step so that the correct direction is not forgotten. We named this sign-based GD method with Error Feedback as _EF-SIGNGD (Algorithm 1) and applied it to the distributed system.

More specifically, in Algorithm 1, ${\text{𝒆}}_m^k$ represents the accumulated error from all compression steps in the previous $k$ iterations of worker $m$ . This residual error is added to the gradient step $\nabla f_m({𝝎}^k)$ to obtain the corrected direction ${\text{𝒈}}_m^k$ , i.e.,

(4) $${\text{𝒈}}_m^k=\nabla f_m({𝝎}^k)+{\text{𝒆}}_m^k$$

All workers will upload ${\Vert {\text{𝒈}}_m^k\Vert }_1$ and $sign({\text{𝒈}}_m^k)$ to the server, and the compression gradient is defined as the signed vector $sign({\text{𝒈}}_m^k)$ scaled by ${\Vert {\text{𝒈}}_m^k\Vert }_1/d$ , i.e.,

(5) $$𝒞({\text{𝒈}}_m^k):=\frac{{\Vert {\text{𝒈}}_m^k\Vert }_1}{d}sign({\text{𝒈}}_m^k)$$

and stores information about the magnitude. $d$ represents the parameter dimension. Therefore, the _EF-SIGNGD algorithm is updated by

(6) $${𝝎}^{k+1}={𝝎}^k-\gamma \cdot \underset{m\in ℳ}{\sum }𝒞({\text{𝒈}}_m^k)$$

Our focus here is to reduce the number of worker-to-server uplink communications, which also refer to uploads (the same as Ref. [ 16 ]). Table 1 shows the communication bits per upload of various algorithms. Compared with GD and _SIGNGD, we find a trade-off between the number of communication bits and convergence guarantee. In large-scale machine learning tasks, the dimension $d$ of the parameters is usually very large, so the cost of the extra $32M$  bits is negligible.

The basic idea of the lazily aggregated technique is that if the difference of two consecutive locally compressed gradients is small, then the redundant uploads may be skipped and the previous one in the server can be reused. This idea comes from a simple rewriting of the _EF-SIGNGD iteration Eq. ( 6 ) as

(15) $${𝝎}^{k+1}={𝝎}^k-\gamma \underset{m\in ℳ}{\sum }𝒞({\text{𝒈}}_m^{k-1})-\gamma \underset{m\in ℳ}{\sum }(𝒞({\text{𝒈}}_m^k)-𝒞({\text{𝒈}}_m^{k-1}))$$

The difference in two consecutive compressed gradients on worker $m$ , i.e., $𝒞({\text{𝒈}}_m^k)-𝒞({\text{𝒈}}_m^{k-1})$ , can be viewed as a refinement to $𝒞({\text{𝒈}}_m^{k-1})$ . Obtaining this refinement requires a round of communication between the server and the worker $m$ . If this refinement is small enough, i.e.,

$$\Vert 𝒞({\text{𝒈}}_m^k)-𝒞({\text{𝒈}}_m^{k-1})\Vert \ll \Vert \underset{m\in ℳ}{\sum }𝒞({\text{𝒈}}_m^{k-1})\Vert ,$$

then we can skip the communication between the server and the worker $m$ to reduce the communication rounds.

Generalizing on this intuition, the lazily aggregated _EF-SIGNGD algorithm, named _LE-SIGNGD, will be updated by

(16) $${𝝎}^{k+1}={𝝎}^k-\gamma {\displaystyle \underset{m\in ℳ}{\sum }}𝒞({\widetilde{\text{𝒈}}}_m^{k-1})-\gamma {\displaystyle \underset{m\in {ℳ}^k}{\sum }}(𝒞({\text{𝒈}}_m^k)-𝒞({\widetilde{\text{𝒈}}}_m^{k-1}))=$$ $${𝝎}^k-\gamma \left({\displaystyle \underset{m\in {ℳ}^k}{\sum }}𝒞({\text{𝒈}}_m^k)+{\displaystyle \underset{m\in {ℳ}_c^k}{\sum }}𝒞({\widetilde{\text{𝒈}}}_m^{k-1})\right)=$$ $${𝝎}^k-\gamma {\displaystyle \underset{m\in ℳ}{\sum }}𝒞({\text{𝒈}}_m^k)+\gamma {\displaystyle \underset{m\in {ℳ}_c^k}{\sum }}\left(𝒞({\text{𝒈}}_m^k)-𝒞({\widetilde{\text{𝒈}}}_m^{k-1})\right)$$

where ${\widetilde{\text{𝒈}}}_m^k=\nabla f_m({\widetilde{𝝎}}_m^k)+{\text{𝒆}}_m^k$ , ${ℳ}^k$ and ${ℳ}_c^k$ are the sets of workers that do and do not communicate with the server in iteration $k$ , respectively. We will only use the fresh compressed gradients from the selected workers in ${ℳ}^k$ , and reuse the outdated compressed gradients from the rest of workers, which means

(17) $${\widetilde{𝝎}}_m^k:={𝝎}^k,\forall m\in {ℳ}^k;{\widetilde{𝝎}}_m^k:={\widetilde{𝝎}}_m^{k-1},\forall m\in {ℳ}_c^k,$$ $${\widetilde{\text{𝒈}}}_m^k:={\text{𝒈}}_m^k,\forall m\in {ℳ}^k;{\widetilde{\text{𝒈}}}_m^k:={\widetilde{\text{𝒈}}}_m^{k-1},\forall m\in {ℳ}_c^k$$

Therefore, the iteration process of _LE-SIGNGD can also be expressed as

(18) $${𝝎}^{k+1}={𝝎}^k-\gamma {\nabla }^k,{\nabla }^k:=\underset{m\in ℳ}{\sum }𝒞({\widetilde{\text{𝒈}}}_m^k)$$

The difference between two compressed gradients in worker $m$ at the current iterate ${𝝎}^k$ and the old copy ${\widetilde{𝝎}}^{k-1}$ is defined as

(19) $${\mathrm{\Delta }}_m^k:=𝒞({\text{𝒈}}_m^k)-𝒞({\widetilde{\text{𝒈}}}_m^{k-1})$$

We find that

(20) $${\nabla }^k={\nabla }^{k-1}+\underset{m\in {ℳ}^k}{\sum }{\mathrm{\Delta }}_m^k$$

Combining Eqs. ( 18 ) and ( 20 ), we can observe that, instead of requesting all fresh compressed gradients in _EF-SIGNGD, the lazily aggregated trick is to obtain ${\nabla }^k$ by refining the previously aggregated gradient ${\nabla }^{k-1}$ . If ${\nabla }^{k-1}$ is stored in the server, then we can scale down the per-iteration communication rounds from $M$ to $|{ℳ}^k|$ .

Designing a principled criterion to select a subset of workers ${ℳ}_c^k$ that does not communicate with the server at each iteration is critical. Our focus is on the trade-off between the communication cost and the convergence guarantee of the _LE-SIGNGD algorithm. Therefore, we compare the one-step descent amount of _EF-SIGNGD and that of _LE-SIGNGD. For _EF-SIGNGD, as shown in Lemma 3, the one-step descent is ${\mathrm{\Delta }}_{\text{EF}}^k$ . The one-step descent of _LE-SIGNGD is ${\mathrm{\Delta }}_{\text{LE}}^k$ , which will be specified in the following lemma.

Lemma 4 (_LE-SIGNGD descent) Under Assumption 1, ${𝝎}^{k+1}$ is generated by running the one-step _LE-SIGNGD iteration (Eq. ( 18 )) given ${𝝎}^k$ . The objective values satisfy

(21) $$f({𝝂}^{k+1})-f({𝝂}^k)⩽{\mathrm{\Delta }}_{\text{LE}}^k$$

(22) $${\mathrm{\Delta }}_{\text{LE}}^k:=-{\displaystyle \frac{\gamma }{2}}{\Vert \nabla f({𝝎}^k)\Vert }^2+{\displaystyle \frac{L^2{\gamma }^2}{2\rho }}{\Vert {\displaystyle \underset{m=1}{\overset{M}{\sum }}}{\text{𝒆}}_m^k\Vert }^2+$$ $$\left({\displaystyle \frac{\rho +L}{2}}-{\displaystyle \frac{1}{2\gamma }}\right){\Vert {𝝂}^{k+1}-{𝝂}^k\Vert }^2+{\displaystyle \frac{\gamma }{2}}{\Vert {\displaystyle \underset{m\in {ℳ}_c^k}{\sum }}{\mathrm{\Delta }}_m^k\Vert }^2$$

where $\rho >0$ .

Remark 2 Different from Eq. ( 14 ) in _EF-SIGNGD, the sequence ${\{{𝝂}^k\}}_{k⩾0}$ has the following property:

(23) $${𝝂}^{k+1}={𝝎}^k-\gamma {\displaystyle \underset{m=1}{\overset{M}{\sum }}}{\text{𝒈}}_m^k+\gamma {\displaystyle \underset{m\in {ℳ}_c^k}{\sum }}{\mathrm{\Delta }}_m^k=$$ $${𝝂}^k-\gamma \nabla f({𝝎}^k)+\gamma {\displaystyle \underset{m\in {ℳ}_c^k}{\sum }}{\mathrm{\Delta }}_m^k$$

Lemmas 3 and 4 estimate the objective value descent by performing one iteration of the _EF-SIGNGD and _LE-SIGNGD methods, respectively, conditioned on a common iterate ${𝝎}^k$ . _EF-SIGNGD finds ${\mathrm{\Delta }}_{\text{EF}}^k$ by performing $M$ rounds of communication with all the workers, while _LE-SIGNGD yields ${\mathrm{\Delta }}_{\text{LE}}^k$ by performing only $|{ℳ}^k|$ rounds of communication with a selected subset of workers. Our pursuit is to select a subset ${ℳ}^k$ to ensure that _LE-SIGNGD enjoys larger per-communication descent than _EF-SIGNGD; that is

(24) $$\frac{{\mathrm{\Delta }}_{\text{LE}}^k}{|{ℳ}^k|}⩽\frac{{\mathrm{\Delta }}_{\text{EF}}^k}{M}$$

For simplicity, we choose the step size $\gamma =1/(\rho +L)$ , ignore the same residual error term, and obtain

(25) $${\Vert \underset{m\in {ℳ}_c^k}{\sum }{\mathrm{\Delta }}_m^k\Vert }^2⩽\frac{|{ℳ}_c^k|}{M}{\Vert \nabla f({𝝎}^k)\Vert }^2$$

If we can further show that

(26) $${\Vert {\mathrm{\Delta }}_m^k\Vert }^2⩽\frac{1}{M^2}{\Vert \nabla f({𝝎}^k)\Vert }^2,\forall m\in {ℳ}_c^k$$

then we can prove that Formula ( 25 ) holds. However, directly checking Formula ( 26 ) in the local worker is impossible because obtaining the fully aggregated gradient $\nabla f({𝝎}^k)$ requires information from all the workers. It does not make sense to reduce uploads if the fully aggregated gradient has been obtained. Instead, we approximate ${\Vert \nabla f({𝝎}^k)\Vert }^2$ in Formula ( 26 ) as follows:

(27) $${\Vert \nabla f({𝝎}^k)\Vert }^2\approx \frac{1}{{\gamma }^2}\underset{d=1}{\overset{D}{\sum }}{\alpha }_d{\Vert {𝝎}^{k+1-d}-{𝝎}^{k-d}\Vert }^2$$

where ${\{{\alpha }_d\}}_{d=1}^D$ are constant weights. The fundamental reason here is that, as $f$ is smooth, $\nabla f({𝝎}^k)$ can be approximated by weighted previous gradients or parameter differences.

Building upon Formulas ( 26 ) and ( 27 ), we will include worker $m$ in ${ℳ}_c^k$ if it satisfies

(28) $${\Vert {\mathrm{\Delta }}_m^k\Vert }^2⩽\frac{1}{{\gamma }^2{M}^2}\underset{d=1}{\overset{D}{\sum }}{\alpha }_d{\Vert {𝝎}^{k+1-d}-{𝝎}^{k-d}\Vert }^2$$

Although the intuition for Formula ( 28 ) is not mathematically strict, we will show that the convergence of the algorithm is guaranteed under this selection rule. In summary, _LE-SIGNGD can be implemented as follows: At iteration $k$ , the server broadcasts the learning parameter to all workers; each worker calculates the local gradient, adds the residual error, and compresses the local information; the worker in ${ℳ}^k$ selected by Formula ( 28 ) will upload the local information to the server; the server aggregates the fresh compressed gradient from the selected workers ${ℳ}^k$ and the outdated gradient information (stored in the server) from ${ℳ}_c^k$ to update the parameter. The _LE-SIGNGD algorithm is summarized in Algorithm 2.