Lower Bounds for Higher-Order Convex Optimization
This work addresses fundamental efficiency bounds for optimization algorithms, which is foundational for the broader ML/AI community, though it is incremental in refining existing theoretical understanding.
The paper tackles the limitations of higher-order optimization methods in convex optimization, proving that a polynomial dependence on approximation guarantees and smoothness parameters is necessary, and shows that Nesterov's accelerated cubic regularization method is nearly tight.
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.