Clip21: Error Feedback for Gradient Clipping
Sarit Khirirat Eduard Gorbunov Samuel Horváth Rustem Islamov Fakhri Karray Peter Richtárik
Motivated by the increasing popularity and importance of large-scale training
under differential privacy (DP) constraints, we study distributed gradient
methods with gradient clipping, i.e., clipping applied to the gradients
computed from local information at the nodes. While gradient clipping is an
essential tool for injecting formal DP guarantees into gradient-based methods
[1], it also induces bias which causes serious convergence issues specific to
the distributed setting. Inspired by recent progress in the error-feedback
literature which is focused on taming the bias/error introduced by
communication compression operators such as Top-$k$ [2], and mathematical
similarities between the clipping operator and contractive compression
operators, we design Clip21 -- the first provably effective and practically
useful error feedback mechanism for distributed methods with gradient clipping.
We prove that our method converges at the same
$\mathcal{O}\left(\frac{1}{K}\right)$ rate as distributed gradient descent in
the smooth nonconvex regime, which improves the previous best
$\mathcal{O}\left(\frac{1}{\sqrt{K}}\right)$ rate which was obtained under
significantly stronger assumptions. Our method converges significantly faster
in practice than competing methods.