The Global Optimization Geometry of Low-Rank Matrix Optimization
The Global Optimization Geometry of Low-Rank Matrix Optimization
复制标题
DOI：
10.1109/tit.2021.3049171
复制
发表时间：
2017-03
影响因子：
2.5
通讯作者：
Zhihui Zhu;Qiuwei Li;Gongguo Tang;M. Wakin
中科院分区：
文献类型：
--
作者：
Zhihui Zhu;Qiuwei Li;Gongguo Tang;M. Wakin
本文考虑了一般的秩约束优化问题，即最小化一般目标函数${f}({X})$在具有至多r个秩数的矩形${n}×{m}$矩阵的集合上。为了解决秩约束问题，同时也为了减少计算负担，我们将${X}$分解为${U}{V}^{\mathm{T}}$，其中${U}$和${V}$分别是${n}×{r}$和${m}×{r}$然后对小矩阵${U}$和${V}$进行优化。刻画了非凸分解问题的全局优化几何，证明了只要原目标函数f满足受限的强凸性和光滑性，相应的目标函数就满足鲁棒严格鞍性，从而保证了求解该分解问题的许多局部搜索算法(如噪声梯度下降算法)在多项式时间内全局收敛。我们还对矩阵分解问题的优化几何进行了全面的分析，其中我们的目标是找到${n}\次{r}$和${m}\次{r}$矩阵${U}$和${V}$使得${U}{V}^{\mathm{T}}$逼近给定的矩阵${X}^\star$。除了稳健的严格鞍点性质外，我们还证明了矩阵分解问题的目标函数不存在伪局部极小值，并且不仅对于$\mathm{ank}({X}^\star)={r}$的精确参数化情形，而且对于$\mathm{rann}({X}^\star)的过度参数化情形和$\mathm{rann}({X}^\star)>；{r}$的欠参数化情形，都服从严格鞍点性质。这些几何性质意味着一些迭代优化算法(如梯度下降)通过随机初始化收敛到全局解。
This paper considers general rank-constrained optimization problems that minimize a general objective function ${f}( {X})$ over the set of rectangular ${n}\times {m}$ matrices that have rank at most r. To tackle the rank constraint and also to reduce the computational burden, we factorize $ {X}$ into $ {U} {V} ^{\mathrm {T}}$ where $ {U}$ and $ {V}$ are ${n}\times {r}$ and ${m}\times {r}$ matrices, respectively, and then optimize over the small matrices $ {U}$ and $ {V}$ . We characterize the global optimization geometry of the nonconvex factored problem and show that the corresponding objective function satisfies the robust strict saddle property as long as the original objective function f satisfies restricted strong convexity and smoothness properties, ensuring global convergence of many local search algorithms (such as noisy gradient descent) in polynomial time for solving the factored problem. We also provide a comprehensive analysis for the optimization geometry of a matrix factorization problem where we aim to find ${n}\times {r}$ and ${m}\times {r}$ matrices $ {U}$ and $ {V}$ such that $ {U} {V} ^{\mathrm {T}}$ approximates a given matrix $ {X}^\star $ . Aside from the robust strict saddle property, we show that the objective function of the matrix factorization problem has no spurious local minima and obeys the strict saddle property not only for the exact-parameterization case where $\mathrm {rank}( {X}^\star) = {r}$ , but also for the over-parameterization case where $\mathrm {rank}( {X}^\star) and the under-parameterization case where $\mathrm {rank}( {X}^\star) > {r}$ . These geometric properties imply that a number of iterative optimization algorithms (such as gradient descent) converge to a global solution with random initialization.