Optimal and Adaptive Monteiro-Svaiter Acceleration
Yair Carmon, Danielle Hausler, Arun Jambulapati, Yujia Jin, Aaron Sidford
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\ge 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 problems our method outperforms previous accelerated second-order methods, but under-performs Newton's method; simply iterating our first-order adaptive subproblem solver is competitive with L-BFGS.
BibTeX
@inproceedings{
carmon2022optimal,
title={Optimal and Adaptive Monteiro-Svaiter Acceleration},
author={Yair Carmon and Danielle Hausler and Arun Jambulapati and Yujia Jin and Aaron Sidford},
booktitle={Advances in Neural Information Processing Systems},
editor={Alice H. Oh and Alekh Agarwal and Danielle Belgrave and Kyunghyun Cho},
year={2022},
url={https://openreview.net/forum?id=n3lr7GdcbyD}
}