Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression
Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regression
复制标题
DOI：
--
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Han Chen;Garvesh Raskutti;M. Yuan
中科院分区：
文献类型：
--
作者：
Han Chen;Garvesh Raskutti;M. Yuan
本文研究了具有低阶结构的高维张量回归问题的学习问题。与学习高维模型相关的核心挑战之一是计算，因为潜在的优化问题通常是非凸的。虽然凸松弛可以导致多项式时间算法，但它们在实践中往往很慢。另一方面，对于非凸方法，存在有限的理论保证。在本文中，我们提供了一个通用的框架，它为在不同的低阶结构假设下使用投影梯度下降算法学习高维张量回归模型提供了理论保证，该算法适用于潜在的非凸约束集$\theta$，其依据是它的\emph(局部化高斯宽度)。我们将我们的非凸投影梯度下降算法的理论结果与前人关于正则化凸逼近的结果进行了比较。凸方法和非凸方法的两个主要区别是：(I)从计算的角度看，非凸投影算子是否可计算，以及投影是否具有理想的压缩性质；(Ii)从统计上界的角度来看，非凸方法在许多例子中具有优良性。我们提供了三个低维结构的具体例子，它们解决了这些问题，并解释了非凸和凸方法的优缺点。我们用模拟来补充我们的理论结果，结果表明，在几种常见的广义低阶张量回归设置下，只要选择适当的投影下降算法的步长，投影梯度下降方法在统计误差和运行时间方面都是优越的。
In this paper, we consider the problem of learning high-dimensional tensor regression problems with low-rank structure. One of the core challenges associated with learning high-dimensional models is computation since the underlying optimization problems are often non-convex. While convex relaxations could lead to polynomial-time algorithms they are often slow in practice. On the other hand, limited theoretical guarantees exist for non-convex methods. In this paper we provide a general framework that provides theoretical guarantees for learning high-dimensional tensor regression models under different low-rank structural assumptions using the projected gradient descent algorithm applied to a potentially non-convex constraint set $\Theta$ in terms of its \emph{localized Gaussian width}. We juxtapose our theoretical results for non-convex projected gradient descent algorithms with previous results on regularized convex approaches. The two main differences between the convex and non-convex approach are: (i) from a computational perspective whether the non-convex projection operator is computable and whether the projection has desirable contraction properties and (ii) from a statistical upper bound perspective, the non-convex approach has a superior rate for a number of examples. We provide three concrete examples of low-dimensional structure which address these issues and explain the pros and cons for the non-convex and convex approaches. We supplement our theoretical results with simulations which show that, under several common settings of generalized low rank tensor regression, the projected gradient descent approach is superior both in terms of statistical error and run-time provided the step-sizes of the projected descent algorithm are suitably chosen.