Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-Tailed Noise and Power of Symmetry

Abstract. We study large deviation upper bounds and mean squared error (MSE) guarantees of a general framework of nonlinear stochastic gradient methods in the online setting and in the presence of heavy-tailed noise. Unlike existing works that rely on the closed form of a nonlinearity (typically clipping), our framework treats the nonlinearity in a black-box manner, allowing us to provide unified results for a broad class of bounded nonlinearities, including many popular ones, like sign, quantization, normalization, as well as componentwise and joint clipping. We provide several strong guarantees for a broad range of step-sizes in the presence of heavy-tailed noise with symmetric probability density function, positive in a neighborhood of zero and potentially unbounded moments. In particular, for nonconvex costs, we provide a large deviation upper bound for the minimum norm-squared of gradients, showing an asymptotic tail decay on an exponential scale, at a rate [Formula: see text]. We establish the accompanying rate function, showing an explicit dependence on the choice of step-size, nonlinearity, noise, and problem parameters. Next, for nonconvex costs and the minimum norm-squared of gradients, we derive the optimal MSE rate [Formula: see text]. Moreover, for strongly convex costs and the last iterate, we provide an MSE rate that can be made arbitrarily close to the optimal rate [Formula: see text], improving on the state-of-the-art results in the presence of heavy-tailed noise. Finally, we establish almost sure (a.s.) convergence of the minimum norm-squared of gradients, providing an explicit rate which can be made arbitrarily close to [Formula: see text].