We provide the first proof that gradient descent $\left({\color{green}\sf
GD}\right)$ with greedy sparsification $\left({\color{green}\sf TopK}\right)$
and error feedback $\left({\color{green}\sf EF}\right)$ can obtain better
communication complexity than vanilla ${\color{green}\sf GD}$ when solving the
distributed optimization problem $\min_{x\in \mathbb{R}^d}
{f(x)=\frac{1}{n}\sum_{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 ${\color{green}\sf EF}$ was first proposed by Seide et
al., this problem remained open until now. We show that ${\color{green}\sf 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 $\hat{x}$ such that
$\lVert {\nabla f(\hat{x})} \rVert^2 \leq \varepsilon$ in expectation,
${\color{green}\sf GD}$ with the ${\color{green}\sf Top1}$ sparsifier and
${\color{green}\sf EF}$ requires ${\cal O} \left(\left( L+{\color{blue}r}
\sqrt{ \frac{{\color{red}c}}{n} \min \left( \frac{{\color{red}c}}{n} \max_i
L_i^2, \frac{1}{n}\sum_{i=1}^n L_i^2 \right) }\right) \frac{1}{\varepsilon}
\right)$ 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$,
${\color{red}c}$ is the maximal number of clients owning any feature ($1\leq
{\color{red}c} \leq n$), and ${\color{blue}r}$ is the maximal number of
features owned by any client ($1\leq {\color{blue}r} \leq d$). Clearly, the
communication complexity improves as ${\color{red}c}$ decreases (i.e., as
features become more rare), and can be much better than the ${\cal
O}({\color{blue}r} L \frac{1}{\varepsilon})$ communication complexity of
${\color{green}\sf GD}$ in the same regime.

本研究首次证明具有贪心稀疏化和误差反馈的梯度下降算法可以在分布式优化问题中获得更好的通信复杂度，在研究中，我们特别关注了稀疏特性。