Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910459440922624 |
|---|---|
| author | Agafonov, Artem Kamzolov, Dmitry Gasnikov, Alexander Kavis, Ali Antonakopoulos, Kimon Cevher, Volkan Takáč, Martin |
| author_facet | Agafonov, Artem Kamzolov, Dmitry Gasnikov, Alexander Kavis, Ali Antonakopoulos, Kimon Cevher, Volkan Takáč, Martin |
| contents | We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, which occurs typically in machine learning. We establish theoretical lower bounds and prove that our algorithm achieves optimal convergence in both gradient and Hessian inexactness in this key setting. We further introduce a tensor generalization for stochastic higher-order derivatives. When the oracles are non-stochastic, the proposed tensor algorithm matches the global convergence of Nesterov Accelerated Tensor method. Both algorithms allow for approximate solutions of their auxiliary subproblems with verifiable conditions on the accuracy of the solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_01570 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness Agafonov, Artem Kamzolov, Dmitry Gasnikov, Alexander Kavis, Ali Antonakopoulos, Kimon Cevher, Volkan Takáč, Martin Optimization and Control We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, which occurs typically in machine learning. We establish theoretical lower bounds and prove that our algorithm achieves optimal convergence in both gradient and Hessian inexactness in this key setting. We further introduce a tensor generalization for stochastic higher-order derivatives. When the oracles are non-stochastic, the proposed tensor algorithm matches the global convergence of Nesterov Accelerated Tensor method. Both algorithms allow for approximate solutions of their auxiliary subproblems with verifiable conditions on the accuracy of the solution. |
| title | Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2309.01570 |