First- and Second-Order Stochastic Adaptive Regularization with Cubics: High Probability Iteration and Sample Complexity
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915252647493632 |
|---|---|
| author | Scheinberg, Katya Xie, Miaolan |
| author_facet | Scheinberg, Katya Xie, Miaolan |
| contents | We present high-probability (and expectation) complexity bounds for two versions of stochastic adaptive regularization methods with cubics (SARC), also known as regularized Newton methods. The first algorithm aims to find first-order stationary points, while the second targets second-order optimality conditions. Both methods employ stochastic zeroth-, first-, and second-order oracles with specific accuracy and reliability requirements. These oracles, which have been previously used with other stochastic adaptive methods like trust-region and line-search algorithms, are applicable to various optimization settings including expected risk minimization and simulation optimization. In this paper, we establish the first high-probability iteration and sample complexity bounds for both first- and second-order SARC algorithms. Our analysis demonstrates that as in the deterministic case, they outperform other stochastic adaptive methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_13161 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | First- and Second-Order Stochastic Adaptive Regularization with Cubics: High Probability Iteration and Sample Complexity Scheinberg, Katya Xie, Miaolan Optimization and Control 49M37, 65K05, 90C15, 90C30, 90C26 We present high-probability (and expectation) complexity bounds for two versions of stochastic adaptive regularization methods with cubics (SARC), also known as regularized Newton methods. The first algorithm aims to find first-order stationary points, while the second targets second-order optimality conditions. Both methods employ stochastic zeroth-, first-, and second-order oracles with specific accuracy and reliability requirements. These oracles, which have been previously used with other stochastic adaptive methods like trust-region and line-search algorithms, are applicable to various optimization settings including expected risk minimization and simulation optimization. In this paper, we establish the first high-probability iteration and sample complexity bounds for both first- and second-order SARC algorithms. Our analysis demonstrates that as in the deterministic case, they outperform other stochastic adaptive methods. |
| title | First- and Second-Order Stochastic Adaptive Regularization with Cubics: High Probability Iteration and Sample Complexity |
| topic | Optimization and Control 49M37, 65K05, 90C15, 90C30, 90C26 |
| url | https://arxiv.org/abs/2308.13161 |