Lower bounds for finding stationary points I
Lower bounds for finding stationary points I
复制标题
DOI：
10.1007/s10107-019-01406-y
复制
发表时间：
2017-10
影响因子：
2.7
通讯作者：
Y. Carmon;John C. Duchi;Oliver Hinder;Aaron Sidford
中科院分区：
文献类型：
--
作者：
Y. Carmon;John C. Duchi;Oliver Hinder;Aaron Sidford
我们证明了寻找光滑的、高维的和潜在的非凸函数的驻点(点)的复杂性的下界。我们考虑基于Oracle的复杂性度量，其中算法被授予访问查询点x处的值和所有派生函数的权限。我们证明了对于任何(潜在随机的)算法，存在一个具有Lipschitzpth阶导数的函数，使得至少需要查询才能找到一个非平稳点。我们的下界在常数范围内是尖锐的，它们表明了梯度下降法、三次正则化牛顿法和广义p阶正则化在它们的自然函数类内是最坏情况下的最优的。
We prove lower bounds on the complexity of finding-stationary points (pointsxsuch that) of smooth, high-dimensional, and potentially non-convex functionsf. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives offat a query pointx. We show that for any (potentially randomized) algorithm, there exists a functionfwith Lipschitzpth order derivatives such thatrequires at leastqueries to find an-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton’s method, and generalizedpth order regularization are worst-case optimal within their natural function classes.