Error Feedback Shines when Features are Rare

Peter Richtárik, Elnur Gasanov, Konstantin Burlachenko

We provide the first proof that gradient descent $\left(\mathsf{GD}\right)$ with greedy sparsification $\left(\mathsf{TopK}\right)$ and error feedback $\left({\…