  Traditional analyses in non-convex optimization typically rely on the
smoothness assumption, namely requiring the gradients to be Lipschitz. However,
recent evidence shows that this smoothness condition does not capture the
properties of some deep learning objective functions, including the ones
involving Recurrent Neural Networks and LSTMs. Instead, they satisfy a much
more relaxed condition, with potentially unbounded smoothness. Under this
relaxed assumption, it has been theoretically and empirically shown that the
gradient-clipped SGD has an advantage over the vanilla one. In this paper, we
show that clipping is not indispensable for Adam-type algorithms in tackling
such scenarios: we theoretically prove that a generalized SignSGD algorithm can
obtain similar convergence rates as SGD with clipping but does not need
explicit clipping at all. This family of algorithms on one end recovers SignSGD
and on the other end closely resembles the popular Adam algorithm. Our analysis
underlines the critical role that momentum plays in analyzing SignSGD-type and
Adam-type algorithms: it not only reduces the effects of noise, thus removing
the need for large mini-batch in previous analyses of SignSGD-type algorithms,
but it also substantially reduces the effects of unbounded smoothness and
gradient norms. We also compare these algorithms with popular optimizers on a
set of deep learning tasks, observing that we can match the performance of Adam
while beating the others.
