Advancing the Lower Bounds: An Accelerated, Stochastic, Second-Order Method with Optimal Adaptation to Inexactness
Abstract
We present a new accelerated stochastic second-order method that is robust to both gradient and Hessian inexactness, typical 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.
Cite
Text
Agafonov et al. "Advancing the Lower Bounds: An Accelerated, Stochastic, Second-Order Method with Optimal Adaptation to Inexactness." International Conference on Learning Representations, 2024.Markdown
[Agafonov et al. "Advancing the Lower Bounds: An Accelerated, Stochastic, Second-Order Method with Optimal Adaptation to Inexactness." International Conference on Learning Representations, 2024.](https://mlanthology.org/iclr/2024/agafonov2024iclr-advancing/)BibTeX
@inproceedings{agafonov2024iclr-advancing,
title = {{Advancing the Lower Bounds: An Accelerated, Stochastic, Second-Order Method with Optimal Adaptation to Inexactness}},
author = {Agafonov, Artem and Kamzolov, Dmitry and Gasnikov, Alexander and Kavis, Ali and Antonakopoulos, Kimon and Cevher, Volkan and Takáč, Martin},
booktitle = {International Conference on Learning Representations},
year = {2024},
url = {https://mlanthology.org/iclr/2024/agafonov2024iclr-advancing/}
}