# Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness

arXiv: https://arxiv.org/abs/2309.01570 · HTML: https://mlsanity.com/paper/2309.01570/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2023.

## Built on by (most cited first, 4 of 4)

- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees](https://mlsanity.com/paper/2508.19712/) (2025)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)

## Abstract (arXiv)

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.