Preconditioned Gradient Descent for Overparameterized Nonconvex Burer-Monteiro Factorization with Global Optimality Certification
Preconditioned Gradient Descent for Overparameterized Nonconvex Burer-Monteiro Factorization with Global Optimality Certification
复制标题
DOI：
10.48550/arxiv.2206.03345
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
G. Zhang;S. Fattahi;Richard Y. Zhang
中科院分区：
文献类型：
--
作者：
G. Zhang;S. Fattahi;Richard Y. Zhang
我们考虑使用梯度下降法来最小化非凸函数f（X）=\phi（XX^{T}）$在$n\times r$因子矩阵$X$上，其中$\phi$是定义在$n\times n$矩阵上的光滑凸代价函数。虽然只有一个二阶稳定点$X$可以证明在合理的时间内找到，如果$X$是额外的秩亏，那么它的秩亏证明它是全局最优的。这种证明全局最优性的方法必然要求当前最优解X$的搜索秩r$相对于全局最小值X^{\星星}$的秩r^{\星星}$被过度参数化。不幸的是，过度参数化显著减慢了梯度下降的收敛速度，从$r=r^{\星星}$的线性速率到$r>r^{\星星}$的次线性速率，即使$\phi$是强凸的。在本文中，我们提出了一个廉价的预条件，恢复收敛速度的梯度下降到线性的过参数化的情况下，同时也使其不可知的全局极小$X^{\星星}$中可能的病态。
We consider using gradient descent to minimize the nonconvex function $f(X)=\phi(XX^{T})$ over an $n\times r$ factor matrix $X$, in which $\phi$ is an underlying smooth convex cost function defined over $n\times n$ matrices. While only a second-order stationary point $X$ can be provably found in reasonable time, if $X$ is additionally rank deficient, then its rank deficiency certifies it as being globally optimal. This way of certifying global optimality necessarily requires the search rank $r$ of the current iterate $X$ to be overparameterized with respect to the rank $r^{\star}$ of the global minimizer $X^{\star}$. Unfortunately, overparameterization significantly slows down the convergence of gradient descent, from a linear rate with $r=r^{\star}$ to a sublinear rate when $r>r^{\star}$, even when $\phi$ is strongly convex. In this paper, we propose an inexpensive preconditioner that restores the convergence rate of gradient descent back to linear in the overparameterized case, while also making it agnostic to possible ill-conditioning in the global minimizer $X^{\star}$.