While stochastic gradient descent (SGD) is still the de facto algorithm in deep learning, adaptive methods like Adam have been observed to outperform SGD across important tasks, such as attention models. The settings under which SGD performs poorly in comparison to Adam 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 a root cause of SGD's poor performance. Based on this observation, we study clipped variants of SGD that circumvent this issue; we then analyze their convergence under heavy-tailed noise. Furthermore, we develop a new adaptive coordinate-wise clipping algorithm (ACClip) tailored to such settings. Subsequently, we show how adaptive methods like Adam can be viewed through the lens of clipping, which helps us explain Adam's strong performance under heavy-tail noise settings. Finally, we show that the proposed ACClip outperforms Adam for both BERT pretraining and finetuning tasks.
The paper proposed a very interesting claim: When training a neural network, if the (stochastic) gradient noise is Gaussian-like, then SGD performs better than Adam; On the other hand if the gradient noise is Heavy tailed, then Adam perform better than SGD.
The paper supported this argument with experiments showing that ResNet50 on ImageNet, the noise is more like Gaussian while BERT on language learning tasks the noise is more heavy-tailed. The paper also gave a theoretical result showing that Adam converges in the regime of heavy-tailed noise. 
The experiment finding is quite surprising to me, since many papers (see e.g. 
A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
)  claim that the SGD noise is heavy-tailed for image recognization tasks such as CIFAR-10, CIFAR-100. The referred paper used rigorous statistical testing for the tail-index of the SGD noise, while this paper simply drew some image. 
Moreover, the theoretical result in this paper also worries me quite a bit, since from the bounds it seems that Adam is the dominating algorithm (both in the heavy-tail case and in Gaussian tail case). Moreover, SGD also converges in the heavy-tail noise case (by showing that the norm of x_t is not too large during the training process using martingale-based argument). Hence, the upper bound of the theoretical result is convincing enough to claim that Adam is better than SGD in certain regime. 
After Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement. I have higher my score: In particular, if the noise is indeed Gaussian as opposite to the "known results", this paper should be accepted.