Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods
Abstract
In this work, we propose a universal and adaptive second-order method for minimization of second-order smooth, convex functions. Precisely, our algorithm achieves $O(\sigma / \sqrt{T})$ when the oracle feedback is stochastic with variance $\sigma$, and obtains the improved $O( 1 / T^3)$ convergence with deterministic oracles. Our method achieves this rate interpolation without knowing the nature of the oracle a priori, which was enabled by a parameter-free step-size that is oblivious to the knowledge of smoothness modulus, variance bounds and the diameter of the constrained set. To our knowledge, this is the first universal algorithm that achieves the aforementioned global guarantees within second-order convex optimization literature.
Cite
Text
Antonakopoulos et al. "Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods." Neural Information Processing Systems, 2022.Markdown
[Antonakopoulos et al. "Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods." Neural Information Processing Systems, 2022.](https://mlanthology.org/neurips/2022/antonakopoulos2022neurips-extranewton/)BibTeX
@inproceedings{antonakopoulos2022neurips-extranewton,
title = {{Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods}},
author = {Antonakopoulos, Kimon and Kavis, Ali and Cevher, Volkan},
booktitle = {Neural Information Processing Systems},
year = {2022},
url = {https://mlanthology.org/neurips/2022/antonakopoulos2022neurips-extranewton/}
}