  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 well-established 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_0,L_1)$--smoothness is a more relaxed notion that captures such behavior in
non-convex optimization. In particular, it has been shown that under this
relaxed smoothness assumption, SGD with clipping requires $O(\epsilon^{-4})$
stochastic gradient computations to find an $\epsilon$--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 $O(\epsilon^{-3})$ which is order-optimal. Our designed learning
rate comprises the clipping technique to mitigate the growing smoothness.
Moreover, when the objective function is the average of $n$ components, we
improve the existing $O(n\epsilon^{-2})$ bound on the stochastic gradient
complexity to $O(\sqrt{n} \epsilon^{-2} + n)$, which is order-optimal as well.
In addition to being theoretically optimal, SPIDER with our designed parameters
demonstrates comparable empirical performance against variance-reduced methods
such as SVRG and SARAH in several vision tasks.
