STIMULUS: Achieving Fast Convergence and Low Sample Complexity in Stochastic Multi-Objective Learning
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912448944013312 |
|---|---|
| author | Liu, Zhuqing Dong, Chaosheng Momma, Michinari Shao, Simone Xu, Shaoyuan Gao, Yan Yang, Haibo Liu, Jia |
| author_facet | Liu, Zhuqing Dong, Chaosheng Momma, Michinari Shao, Simone Xu, Shaoyuan Gao, Yan Yang, Haibo Liu, Jia |
| contents | Recently, multi-objective optimization (MOO) has gained attention for its broad applications in ML, operations research, and engineering. However, MOO algorithm design remains in its infancy and many existing MOO methods suffer from unsatisfactory convergence rate and sample complexity performance. To address this challenge, in this paper, we propose an algorithm called STIMULUS( stochastic path-integrated multi-gradient recursive e\ulstimator), a new and robust approach for solving MOO problems. Different from the traditional methods, STIMULUS introduces a simple yet powerful recursive framework for updating stochastic gradient estimates to improve convergence performance with low sample complexity. In addition, we introduce an enhanced version of STIMULUS, termed STIMULUS-M, which incorporates a momentum term to further expedite convergence. We establish $O(1/T)$ convergence rates of the proposed methods for non-convex settings and $O (\exp{-μT})$ for strongly convex settings, where $T$ is the total number of iteration rounds. Additionally, we achieve the state-of-the-art $O \left(n+\sqrt{n}ε^{-1}\right)$ sample complexities for non-convex settings and $O\left(n+ \sqrt{n} \ln ({μ/ε})\right)$ for strongly convex settings, where $ε>0$ is a desired stationarity error. Moreover, to alleviate the periodic full gradient evaluation requirement in STIMULUS and STIMULUS-M, we further propose enhanced versions with adaptive batching called STIMULUS+/ STIMULUS-M+ and provide their theoretical analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_19883 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | STIMULUS: Achieving Fast Convergence and Low Sample Complexity in Stochastic Multi-Objective Learning Liu, Zhuqing Dong, Chaosheng Momma, Michinari Shao, Simone Xu, Shaoyuan Gao, Yan Yang, Haibo Liu, Jia Machine Learning Artificial Intelligence Recently, multi-objective optimization (MOO) has gained attention for its broad applications in ML, operations research, and engineering. However, MOO algorithm design remains in its infancy and many existing MOO methods suffer from unsatisfactory convergence rate and sample complexity performance. To address this challenge, in this paper, we propose an algorithm called STIMULUS( stochastic path-integrated multi-gradient recursive e\ulstimator), a new and robust approach for solving MOO problems. Different from the traditional methods, STIMULUS introduces a simple yet powerful recursive framework for updating stochastic gradient estimates to improve convergence performance with low sample complexity. In addition, we introduce an enhanced version of STIMULUS, termed STIMULUS-M, which incorporates a momentum term to further expedite convergence. We establish $O(1/T)$ convergence rates of the proposed methods for non-convex settings and $O (\exp{-μT})$ for strongly convex settings, where $T$ is the total number of iteration rounds. Additionally, we achieve the state-of-the-art $O \left(n+\sqrt{n}ε^{-1}\right)$ sample complexities for non-convex settings and $O\left(n+ \sqrt{n} \ln ({μ/ε})\right)$ for strongly convex settings, where $ε>0$ is a desired stationarity error. Moreover, to alleviate the periodic full gradient evaluation requirement in STIMULUS and STIMULUS-M, we further propose enhanced versions with adaptive batching called STIMULUS+/ STIMULUS-M+ and provide their theoretical analysis. |
| title | STIMULUS: Achieving Fast Convergence and Low Sample Complexity in Stochastic Multi-Objective Learning |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2506.19883 |