Error Feedback Shines when Features are Rare

arXiv2305.15264MaRDI QIDQ6437837

Author name not available (Why is that?)

Publication date: 24 May 2023

Abstract: We provide the first proof that gradient descent $left(colorgreensfGDight)$ with greedy sparsification $left(colorgreensfTopKight)$ and error feedback $left(colorgreensfEFight)$ can obtain better communication complexity than vanilla $colorgreensfGD$ when solving the distributed optimization problem $mi{n}_{xinmathbb{R}^d}f(x)=frac1nsu{m}_{i=1}^n{f}_i(x)$, where $n$ = # of clients, $d$ = # of features, and $f_1,dots,f_n$ are smooth nonconvex functions. Despite intensive research since 2014 when $colorgreensfEF$ was first proposed by Seide et al., this problem remained open until now. We show that $colorgreensfEF$ 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 $lVertablaf(hatx)Ver{t}^{2}leqvarepsilon$ in expectation, $colorgreensfGD$ with the $colorgreensfTop1$ sparsifier and $colorgreensfEF$ requires $calOleft(left(L+colorbluersqrtfraccolorredcnminleft(fraccolorredcnma{x}_i{L}_i^2,frac1nsu{m}_{i=1}^n{L}_i^{2}ight)ight)frac1varepsilonight)$ bits to be communicated by each worker to the server only, where $L$ is the smoothness constant of $f$, $L_i$ is the smoothness constant of $f_i$, $colorredc$ is the maximal number of clients owning any feature ($1leqcolorredcleqn$), and $colorbluer$ is the maximal number of features owned by any client ($1leqcolorbluerleqd$). Clearly, the communication complexity improves as $colorredc$ decreases (i.e., as features become more rare), and can be much better than the $calO(colorbluerLfrac1varepsilon)$ communication complexity of $colorgreensfGD$ in the same regime.

Has companion code repository: https://github.com/burlachenkok/ef21_with_rare_features

This page was built for publication: Error Feedback Shines when Features are Rare

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437837)