  While stochastic gradient descent (SGD) is still the \emph{de facto}
algorithm in deep learning, adaptive methods like Clipped SGD/Adam have been
observed to outperform SGD across important tasks, such as attention models.
The settings under which SGD performs poorly in comparison to adaptive methods
are not well understood yet. In this paper, we provide empirical and
theoretical evidence that a heavy-tailed distribution of the noise in
stochastic gradients is one cause of SGD's poor performance. We provide the
first tight upper and lower convergence bounds for adaptive gradient methods
under heavy-tailed noise. Further, we demonstrate how gradient clipping plays a
key role in addressing heavy-tailed gradient noise. Subsequently, we show how
clipping can be applied in practice by developing an \emph{adaptive}
coordinate-wise clipping algorithm (ACClip) and demonstrate its superior
performance on BERT pretraining and finetuning tasks.
