Lower Bounds for Higher-Order Convex Optimization

Abstract

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.

References in corpus (6)

• Sub-sampled Newton Methods with Non-uniform Sampling
• Tight Complexity Bounds for Optimizing Composite Objectives
• Second-Order Stochastic Optimization for Machine Learning in Linear Time
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems

Cited by in corpus (3)

• On the Randomized Complexity of Minimizing a Convex Quadratic Function
• Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
• The gradient complexity of linear regression