Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910018248376320 |
|---|---|
| author | He, Chuan Lu, Zhaosong Sun, Defeng Deng, Zhanwang |
| author_facet | He, Chuan Lu, Zhaosong Sun, Defeng Deng, Zhanwang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_11214 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise He, Chuan Lu, Zhaosong Sun, Defeng Deng, Zhanwang Optimization and Control Artificial Intelligence Computational Complexity Machine Learning 49M05, 49M37, 90C25, 90C30 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. |
| title | Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise |
| topic | Optimization and Control Artificial Intelligence Computational Complexity Machine Learning 49M05, 49M37, 90C25, 90C30 |
| url | https://arxiv.org/abs/2506.11214 |