Geometry of Factored Nuclear Norm Regularization
Geometry of Factored Nuclear Norm Regularization
复制标题
因式核范数正则化的几何
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Gongguo Tang
中科院分区：
文献类型：
--
作者：
Qiuwei Li;Zhihui Zhu;Gongguo Tang
这项工作研究了最小化由矩阵核范数 $\|X\|_*$ 正则化的一般凸损失函数 $f(X)$ 的非凸重构的几何形状。核范数正则化矩阵逆问题是机器学习、信号处理和控制领域许多应用的核心。文献中使用凸分析技术对核范数正则化的统计性能进行了广泛的研究。尽管具有最佳性能，但当使用标准甚至定制的快速凸求解器求解时，最终的优化具有很高的计算复杂性。为了开发更快、更具可扩展性的算法，我们遵循 Burer-Monteiro 的建议，将矩阵变量 $X$ 分解为两个较小的矩形矩阵 $X=UV^T$ 的乘积，并将核范数 $\|X\|_*$ 替换为 $(\|U\|_F^2+\|V\|_F^2)/2$。尽管分解公式的非凸性，我们证明当凸损失函数 $f(X)$ 是 $(2r,4r)$ 限制良好条件时，分解问题的每个临界点要么对应于原始凸优化的最优解 $X^\star$，要么是严格鞍点，其中 Hessian 矩阵具有严格负特征值。分解公式的这种几何结构允许许多局部搜索算法通过随机初始化收敛到全局最优值。
This work investigates the geometry of a nonconvex reformulation of minimizing a general convex loss function $f(X)$ regularized by the matrix nuclear norm $\|X\|_*$. Nuclear-norm regularized matrix inverse problems are at the heart of many applications in machine learning, signal processing, and control. The statistical performance of nuclear norm regularization has been studied extensively in literature using convex analysis techniques. Despite its optimal performance, the resulting optimization has high computational complexity when solved using standard or even tailored fast convex solvers. To develop faster and more scalable algorithms, we follow the proposal of Burer-Monteiro to factor the matrix variable $X$ into the product of two smaller rectangular matrices $X=UV^T$ and also replace the nuclear norm $\|X\|_*$ with $(\|U\|_F^2+\|V\|_F^2)/2$. In spite of the nonconvexity of the factored formulation, we prove that when the convex loss function $f(X)$ is $(2r,4r)$-restricted well-conditioned, each critical point of the factored problem either corresponds to the optimal solution $X^\star$ of the original convex optimization or is a strict saddle point where the Hessian matrix has a strictly negative eigenvalue. Such a geometric structure of the factored formulation allows many local search algorithms to converge to the global optimum with random initializations.
DOI：
10.1093/imaiai/iay003
发表时间：
2016-11
期刊：
2017 IEEE Global Conference on Signal and Information Processing (GlobalSIP)
影响因子：
--
作者：
Qiuwei Li;Gongguo Tang
通讯作者：
Qiuwei Li;Gongguo Tang