Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
This provides a more efficient solution for optimization problems in noisy environments, such as machine learning and signal processing, though it is incremental as it builds on existing stochastic methods.
The paper tackles convex composite optimization under heavy-tailed noise by showing that a vanilla accelerated stochastic proximal subgradient method achieves optimal first-order oracle complexity without modifications like clipping or normalization, with numerical experiments validating the results.
We study convex composite optimization problems, where the objective function is given by the sum of a prox-friendly function and a convex function whose subgradients are estimated under heavy-tailed noise. Existing work often employs gradient clipping or normalization techniques in stochastic first-order methods to address heavy-tailed noise. In this paper, we demonstrate that a vanilla stochastic algorithm -- without additional modifications such as clipping or normalization -- can achieve optimal complexity for these problems. In particular, we establish that an accelerated stochastic proximal subgradient method achieves a first-order oracle complexity that is universally optimal for smooth, weakly smooth, and nonsmooth convex optimization, as well as for stochastic convex optimization under heavy-tailed noise. Numerical experiments are further provided to validate our theoretical results.