论文标题
一阶方法需要指数时间来收敛到非凸功能的全局最小化器
First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions
论文作者
论文摘要
机器学习算法通常在一类非凸功能的功能上执行优化。在这项工作中，我们为识别非凸功能的全球最小化器的基本硬度提供了界限。具体而言，我们设计了一个参数化的非凸功能家族，并采用统计下限进行参数估计。我们表明，参数估计问题等同于给定家族中功能识别问题。然后，我们声称非凸优化至少与函数识别一样困难。共同证明，任何一阶方法都可以花费指数时间与全球最小化器收敛。
Machine learning algorithms typically perform optimization over a class of non-convex functions. In this work, we provide bounds on the fundamental hardness of identifying the global minimizer of a non convex function. Specifically, we design a family of parametrized non-convex functions and employ statistical lower bounds for parameter estimation. We show that the parameter estimation problem is equivalent to the problem of function identification in the given family. We then claim that non convex optimization is at least as hard as function identification. Jointly, we prove that any first order method can take exponential time to converge to a global minimizer.
