Lower Bounds for Higher-Order Convex Optimization
By Naman Agarwal, Elad Hazan. 2017
49 citations recorded by the source corpus.
State-of-the-art methods in convex and non-convex optimization employ higher-order derivative information, either implicitly or explicitly. We explore the limitations of higher-order optimization and prove that even for convex optimization, a polynomial dependence on the approximation guarantee and higher-order smoothness parameters is necessary. As a special case, we show Nesterov's accelerated cubic regularization method to be nearly tight.
Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- H. Brendan McMahan
- Blake E. Woodworth
- Nati Srebro
- Jialei Wang
- Peter Richtárik
- Jakub Konecný
- Sebastian U. Stich
- Max Simchowitz
In Computational Mechanics
- H. Brendan McMahan
- Jialei Wang
- Nati Srebro
- Blake E. Woodworth
- Max Simchowitz
- Zeyuan Allen-Zhu
- Peter Richtárik
- Jakub Konecný
In Numerical Analysis
- Jialei Wang
- H. Brendan McMahan
- Nati Srebro
- Blake E. Woodworth
- Max Simchowitz
- Tengyu Ma
- Jason D. Lee
- Shusen Wang
Citations in the corpus
- Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “In the case of the gradient oracle, we “smooth out” a standard non-smooth lower bound construction [20, 26]; previous work has used a similar approach in slightly different settings [2, 12].”
- On the Randomized Complexity of Minimizing a Convex Quadratic Function (2018, background): “Subsequent works generalized these constructions to query models which allow for high-order derivatives [3, 9]; these lower bounds are only relvant for non-quadratic functions, since a second order method can, by definition, minimize a quadratic function in one iteration.”