Skip to yearly menu bar Skip to main content


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

Kimon Antonakopoulos · Ali Kavis · Volkan Cevher

Hall J (level 1) #815

Keywords: [ acceleration ] [ Stochastic Optimization ] [ second-order methods ] [ universal methods ] [ Convex Optimization ] [ Adaptive 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.

Chat is not available.