Efficient Dictionary Learning with Gradient Descent
Efficient Dictionary Learning with Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2018-09
影响因子：
2.3
通讯作者：
D. Gilboa;Sam Buchanan;John Wright
中科院分区：
文献类型：
--
作者：
D. Gilboa;Sam Buchanan;John Wright
随机初始化的一阶优化算法是解决机器学习中许多高维非凸问题的首选方法，然而一般的理论保证无法排除收敛到目标值较差的临界点。然而，对于一些高度结构化的非凸问题，通过研究目标函数的几何性质可以理解梯度下降的成功之处。我们研究了这样一个问题——完全正交字典学习，并为随机初始化的梯度下降收敛到全局最优解的邻域提供了保证。尽管目标函数具有指数级数量的鞍点，但所得的收敛速率在维度上是低阶多项式。这种高效的收敛可以看作是与鞍点相关的稳定流形法向负曲率的结果，并且我们提供的证据表明，这一特征也为其他重要的非凸问题所共有。
Randomly initialized first-order optimization algorithms are the method of choice for solving many high-dimensional nonconvex problems in machine learning, yet general theoretical guarantees cannot rule out convergence to critical points of poor objective value. For some highly structured nonconvex problems however, the success of gradient descent can be understood by studying the geometry of the objective. We study one such problem -- complete orthogonal dictionary learning, and provide converge guarantees for randomly initialized gradient descent to the neighborhood of a global optimum. The resulting rates scale as low order polynomials in the dimension even though the objective possesses an exponential number of saddle points. This efficient convergence can be viewed as a consequence of negative curvature normal to the stable manifolds associated with saddle points, and we provide evidence that this feature is shared by other nonconvex problems of importance as well.