Lower bounds for finding stationary points II: first-order methods

• 成果类型: Article
• 署名作者: Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron
• 署名单位: Stanford University; Stanford University; Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01431-x
• 发表日期: 2021
• 页码: 315-355
• 关键词: Optimization; complexity

摘要

We establish lower bounds on the complexity of finding similar to-stationary points of smooth, non-convex high-dimensional functions using first-order methods. We prove that deterministic first-order methods, even applied to arbitrarily smooth functions, cannot achieve convergence rates in similar to better than similar to -8/5, which is within similar to-1/15 log 1 similar to of the best known rate for such methods. Moreover, for functions with Lipschitz first and second derivatives, we prove that no deterministic first-order method can achieve convergence rates better than similar to -12/7, while similar to -2 is a lower bound for functions with only Lipschitz gradient. For convex functions with Lipschitz gradient, accelerated gradient descent achieves a better rate, showing that finding stationary points is easier given convexity.