Variance-reduced Clipping for Non-convex Optimization

Gradient clipping is a standard training technique used in deep learning applications such as large-scale language modeling to mitigate exploding gradients. Recent experimental studies have demonstrated a fairly special behavior in the smoothness of the training objective along its trajectory when trained with gradient clipping. That is, the smoothness grows with the gradient norm. This is in clear contrast to the wellestablished assumption in folklore non-convex optimization, a.k.a. L–smoothness, where the smoothness is assumed to be bounded by a constant L globally. The recently introduced (L<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf>, L<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf>)– smoothness is a more relaxed notion that captures such behavior in non-convex optimization. It has been shown that under this relaxed smoothness assumption, SGD with clipping requires $\mathcal{O}\left( {{ \in ^{ - 4}}} \right)$ stochastic gradient computations to find an ϵ–stationary solution. In this paper, we employ a variance reduction technique, namely Spider, and demonstrate that for a carefully designed learning rate, this complexity is improved to $\mathcal{O}\left( {{ \in ^{ - 3}}} \right)$ which is order-optimal. Moreover, when the objective is the average of n components, we improve the existing $\mathcal{O}\left( {n{ \in ^{ - 2}}} \right)$ gradient complexity to $\mathcal{O}\left( {\sqrt n { \in ^{ - 2}} + n} \right)$, which is order-optimal as well.