Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves \(O(\sigma / \sqrt{T})\) convergence when the oracle feedback is stochastic with variance \(\sigma^2\), and improves its convergence to \(O( 1 / T^3)\) with de...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-12
Main Authors: Antonakopoulos, Kimon, Kavis, Ali, Cevher, Volkan
Format: Article
Language:English
Subjects:
Algorithms
Convergence
Optimization
Smoothness
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves \(O(\sigma / \sqrt{T})\) convergence when the oracle feedback is stochastic with variance \(\sigma^2\), and improves its convergence to \(O( 1 / T^3)\) with deterministic oracles, where \(T\) is the number of iterations. Our method also interpolates these rates without knowing the nature of the oracle apriori, which is enabled by a parameter-free adaptive 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 with such global guarantees within the second-order optimization literature.
ISSN:2331-8422