# Optimal and Adaptive Monteiro-Svaiter Acceleration

arXiv: https://arxiv.org/abs/2205.15371 · HTML: https://mlsanity.com/paper/2205.15371/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2022.

## Built on by (most cited first, 24 of 24)

- [Super-Universal Regularized Newton Method](https://mlsanity.com/paper/2208.05888/) (2022)
- [The Price of Adaptivity in Stochastic Convex Optimization](https://mlsanity.com/paper/2402.10898/) (2024)
- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [RECAPP: Crafting a More Efficient Catalyst for Convex Optimization](https://mlsanity.com/paper/2206.08627/) (2022)
- [Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods](https://mlsanity.com/paper/2211.01832/) (2022)
- [Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method](https://mlsanity.com/paper/2308.14742/) (2023)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications](https://mlsanity.com/paper/2502.02002/) (2025)
- [Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization](https://mlsanity.com/paper/2306.02212/) (2023)
- [Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization](https://mlsanity.com/paper/2510.00823/) (2025)
- [A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions](https://mlsanity.com/paper/2311.10886/) (2023)
- [Gradient-Normalized Smoothness for Optimization with Approximate Hessians](https://mlsanity.com/paper/2506.13710/) (2025)
- [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024)
- [Faster Acceleration for Steepest Descent](https://mlsanity.com/paper/2409.19200/) (2024)
- [Halpern Iteration Achieves tildeO(ε-1/p) pth-Order Oracle Complexity for Monotone Variational Inequalities](https://mlsanity.com/paper/2608.08463/) (2026)
- [Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis](https://mlsanity.com/paper/2210.12860/) (2022)
- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees](https://mlsanity.com/paper/2508.19712/) (2025)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)
- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)
- [Near-Optimal Acceleration for Smooth ℓp / ℓq Nondual Convex First-Order Oracle Optimization](https://mlsanity.com/paper/2609.21880/) (2026)
- [Optimal High-Order Methods for Solving Monotone Variational Inequalities](https://mlsanity.com/paper/2609.23557/) (2026)
- [Near-Optimal Convex Optimization with Lazy Second-Order Oracles](https://mlsanity.com/paper/2610.03222/) (2026)

## Abstract (arXiv)

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≥ 2 we improve the complexity of convex optimization with Lipschitz pth 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.