论文标题
关于在一个维度中找到平滑函数的固定点的复杂性
On the complexity of finding stationary points of smooth functions in one dimension
论文作者
论文摘要
我们表征了查询一维非凸的固定点但平滑函数的查询复杂性。我们根据所考虑的算法是确定性的还是随机的，以及Oracle输出$ 1^{\ rm st} $ - 订购还是$ 0^{\ rm th} $ - 和$ 1^{\ rm st st} $ - 订购信息。我们的结果表明，此任务的算法通过合并随机性或$ 0^{\ rm th} $ - 订单信息可证明受益。我们的结果还表明，对于每个维度$ d \ geq 1 $，梯度下降仅使用$ 1^{\ rm st} $ - 仅订购查询是最佳的确定性算法。
We characterize the query complexity of finding stationary points of one-dimensional non-convex but smooth functions. We consider four settings, based on whether the algorithms under consideration are deterministic or randomized, and whether the oracle outputs $1^{\rm st}$-order or both $0^{\rm th}$- and $1^{\rm st}$-order information. Our results show that algorithms for this task provably benefit by incorporating either randomness or $0^{\rm th}$-order information. Our results also show that, for every dimension $d \geq 1$, gradient descent is optimal among deterministic algorithms using $1^{\rm st}$-order queries only.
