论文标题
改进了非凸班的全球保证 - 通过等级过度参数化的蒙蒂罗分解
Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization
论文作者
论文摘要
我们考虑最大程度地减少两次不同的差异，$ l $ -smooth和$μ$ -strongly的凸目标$ ϕ $，$ n \ times n $ n $阳性半finite矩阵$ m \ succeq0 $，假设最小值$ m^{\ star} $降低了等级$ r^$ r^ll star}遵循burer- monteiro方法，我们相反，在因子矩阵$ x $ size $ n \ times r $上最小化nonconvex objection $ f（x）= ϕ（xx^{t}）$。这实际上将变量的数量从$ o（n^{2}）$减少到$ O（n）$的少量，并且免费实施了正面的半弱点，但以放弃原始问题的汇总为代价。在本文中，我们证明，如果搜索等级$ r \ ge r^{\ star} $被A \ emph {constant factor}相对于真实等级$ r^{\ star} $过度参数，即，尽管$ r> \ frac {1}} {1} {1} {4} {4} {4}（l/μ-1）优化可以保证从任何初始点到全局最佳的全球收敛。这在先前的等级过度参数阈值为$ r \ ge n $的情况下有了显着改善，在没有光滑度和较强凸度的情况下，我们表明这是敏锐的，但会将变量的数量增加到$ O（n^{2}）$。相反，没有排名过度参数化，我们证明，只有当$ ϕ $几乎完美地条件并且条件数量为$ l/μ<3 $时，就可以证明这样的全球保证是可能的。因此，我们得出的结论是，少量的过度参数化可能会导致非凸式居民的理论保证大大改善。
We consider minimizing a twice-differentiable, $L$-smooth, and $μ$-strongly convex objective $ϕ$ over an $n\times n$ positive semidefinite matrix $M\succeq0$, under the assumption that the minimizer $M^{\star}$ has low rank $r^{\star}\ll n$. Following the Burer--Monteiro approach, we instead minimize the nonconvex objective $f(X)=ϕ(XX^{T})$ over a factor matrix $X$ of size $n\times r$. This substantially reduces the number of variables from $O(n^{2})$ to as few as $O(n)$ and also enforces positive semidefiniteness for free, but at the cost of giving up the convexity of the original problem. In this paper, we prove that if the search rank $r\ge r^{\star}$ is overparameterized by a \emph{constant factor} with respect to the true rank $r^{\star}$, namely as in $r>\frac{1}{4}(L/μ-1)^{2}r^{\star}$, then despite nonconvexity, local optimization is guaranteed to globally converge from any initial point to the global optimum. This significantly improves upon a previous rank overparameterization threshold of $r\ge n$, which we show is sharp in the absence of smoothness and strong convexity, but would increase the number of variables back up to $O(n^{2})$. Conversely, without rank overparameterization, we prove that such a global guarantee is possible if and only if $ϕ$ is almost perfectly conditioned, with a condition number of $L/μ<3$. Therefore, we conclude that a small amount of overparameterization can lead to large improvements in theoretical guarantees for the nonconvex Burer--Monteiro factorization.
