Optimal and Adaptive Monteiro-Svaiter Acceleration

Author name not available (Why is that?)

Publication date: 30 May 2022

Abstract: We develop a variant of the Monteiro-Svaiter (MS) acceleration framework that removes the need to solve an expensive implicit equation at every iteration. Consequently, for any

p g e 2

we improve the complexity of convex optimization with Lipschitz

p

th derivative by a logarithmic factor, matching a lower bound. We also introduce an MS subproblem solver that requires no knowledge of problem parameters, and implement it as either a second- or first-order method by solving linear systems or applying MinRes, respectively. On logistic regression our method outperforms previous second-order momentum methods, but under-performs Newton's method; simply iterating our first-order adaptive subproblem solver performs comparably to L-BFGS.

Has companion code repository: https://github.com/danielle-hausler/ms-optimal

This page was built for publication: Optimal and Adaptive Monteiro-Svaiter Acceleration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6400613)