  We introduce a general framework for nonlinear stochastic gradient descent
(SGD) for the scenarios when gradient noise exhibits heavy tails. The proposed
framework subsumes several popular nonlinearity choices, like clipped,
normalized, signed or quantized gradient, but we also consider novel
nonlinearity choices. We establish for the considered class of methods strong
convergence guarantees assuming a strongly convex cost function with Lipschitz
continuous gradients under very general assumptions on the gradient noise. Most
notably, we show that, for a nonlinearity with bounded outputs and for the
gradient noise that may not have finite moments of order greater than one, the
nonlinear SGD's mean squared error (MSE), or equivalently, the expected cost
function's optimality gap, converges to zero at rate~$O(1/t^\zeta)$, $\zeta \in
(0,1)$. In contrast, for the same noise setting, the linear SGD generates a
sequence with unbounded variances. Furthermore, for the nonlinearities that can
be decoupled component wise, like, e.g., sign gradient or component-wise
clipping, we show that the nonlinear SGD asymptotically (locally) achieves a
$O(1/t)$ rate in the weak convergence sense and explicitly quantify the
corresponding asymptotic variance. Experiments show that, while our framework
is more general than existing studies of SGD under heavy-tail noise, several
easy-to-implement nonlinearities from our framework are competitive with state
of the art alternatives on real data sets with heavy tail noises.
