Lower bounds for finding stationary points I

• 成果类型: 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-01406-y
• 发表日期: 2020
• 页码: 71-120
• 关键词: convex-optimization; oracle complexity; descent; noisy

摘要

We prove lower bounds on the complexity of finding similar to-stationary points (points x such that similar to. f (x)similar to = similar to) of smooth, high-dimensional, and potentially non-convex functions f. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of f at a query point x. We show that for any (potentially randomized) algorithm A, there exists a function f with Lipschitz pth order derivatives such that A requires at least similar to-( p+1)/ p queries to find an similar to-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton'smethod, and generalized pth order regularization are worst-case optimal within their natural function classes.