Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise
This work addresses optimization challenges in noisy, non-smooth settings, which is incremental but relevant for machine learning and data science applications.
The paper tackles the problem of solving unconstrained optimization under heavy-tailed noise and weak smoothness conditions by proposing normalized stochastic first-order methods with momentum, achieving complexity bounds that improve or match state-of-the-art results.
In this paper, we propose practical normalized stochastic first-order methods with Polyak momentum, multi-extrapolated momentum, and recursive momentum for solving unconstrained optimization problems. These methods employ dynamically updated algorithmic parameters and do not require explicit knowledge of problem-dependent quantities such as the Lipschitz constant or noise bound. We establish first-order oracle complexity results for finding approximate stochastic stationary points under heavy-tailed noise and weakly average smoothness conditions -- both of which are weaker than the commonly used bounded variance and mean-squared smoothness assumptions. Our complexity bounds either improve upon or match the best-known results in the literature. Numerical experiments are presented to demonstrate the practical effectiveness of the proposed methods.