Abstract
State-of-the-art methods in mathematical optimization employ higher-order derivative information. 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. This refutes the hope that higher-order smoothness and higher-order derivatives can lead to dimension free polynomial time algorithms for convex optimization. As a special case, we show Nesterov’s accelerated cubic regularization method and higher-order methods to be nearly tight.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 774-792 |
| Number of pages | 19 |
| Journal | Proceedings of Machine Learning Research |
| Volume | 75 |
| State | Published - 2018 |
| Externally published | Yes |
| Event | 31st Annual Conference on Learning Theory, COLT 2018 - Stockholm, Sweden Duration: Jul 6 2018 → Jul 9 2018 |
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability
Keywords
- Convex Optimization
- Higher-Order Optimization
- Lower Bounds
- Newton’s method
- Second-Order Optimization