Error Feedback Shines when Features are Rare

We provide the first proof that gradient descent left(colorgreensf GDright) with greedy sparsification left(colorgreensf TopKright) and error feedback left(colorgreensf EFright) can obtain better communication complexity than vanilla colorgreensf GD when solving the distributed optimization problem minx∈ ℝd f(x)=frac1nsumi=1n fi(x), where n = # of clients, d = # of features, and f1,dots,fn are smooth nonconvex functions. Despite intensive research since 2014 when colorgreensf EF was first proposed by Seide et al., this problem remained open until now. We show that colorgreensf EF shines in the regime when features are rare, i.e., when each feature is present in the data owned by a small number of clients only. To illustrate our main result, we show that in order to find a random vector hatx such that lVert nabla f(hatx) rVert2 ≤ varepsilon in expectation, colorgreensf GD with the colorgreensf Top1 sparsifier and colorgreensf EF requires cal O left(left( L+colorbluer √ fraccolorredcn min left( fraccolorredcn maxi Li2, frac1nsumi=1n Li2 right) right) frac1varepsilon right) bits to be communicated by each worker to the server only, where L is the smoothness constant of f, Li is the smoothness constant of fi, colorredc is the maximal number of clients owning any feature (1≤ colorredc ≤ n), and colorbluer is the maximal number of features owned by any client (1≤ colorbluer ≤ d). Clearly, the communication complexity improves as colorredc decreases (i.e., as features become more rare), and can be much better than the cal O(colorbluer L frac1varepsilon) communication complexity of colorgreensf GD in the same regime.