  Adam is widely adopted in practical applications due to its fast convergence.
However, its theoretical analysis is still far from satisfactory. Existing
convergence analyses for Adam rely on the bounded smoothness assumption,
referred to as the \emph{L-smooth condition}. Unfortunately, this assumption
does not hold for many deep learning tasks. Moreover, we believe that this
assumption obscures the true benefit of Adam, as the algorithm can adapt its
update magnitude according to local smoothness. This important feature of Adam
becomes irrelevant when assuming globally bounded smoothness. This paper
studies the convergence of randomly reshuffled Adam (RR Adam) with diminishing
learning rate, which is the major version of Adam adopted in deep learning
tasks. We present the first convergence analysis of RR Adam without the bounded
smoothness assumption. We demonstrate that RR Adam can maintain its convergence
properties when smoothness is linearly bounded by the gradient norm, referred
to as the \emph{$(L_0, L_1)$-smooth condition. We further compare Adam to SGD
when both methods use diminishing learning rate. We refine the existing lower
bound of SGD and show that SGD can be slower than Adam. To our knowledge, this
is the first time that Adam and SGD are rigorously compared in the same setting
and the advantage of Adam is revealed.
