Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
Srinadh Bhojanapalli TTI Chicago, email: Nicolas Boumal Princeton University, email: Prateek Jain Microsoft Research, email: Praneeth Netrapalli Microsoft Research, email:
Abstract
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer–Monteiro factorization approach for solving SDPs. We show that all approximate local optima are global optima for the penalty formulation of appropriately rank-constrained SDPs as long as the number of constraints scales sub-quadratically with the desired rank of the optimal solution. Our result is based on a simple penalty function formulation of the rank-constrained SDP along with a smoothed analysis to avoid worst-case cost matrices. We particularize our results to two applications, namely, Max-Cut and matrix completion.
中文速览
半正定规划（Semidefinite Program, SDP）在机器学习和组合优化中无处不在，但传统求解算法计算量巨大、难以扩展到大规模问题。为了降低复杂度，研究者们采用 Burer-Monteiro 因子分解，把变量矩阵写成低秩乘积形式，却由此引入了非凸性——局部最优解未必是全局最优解。本文提出一种简单的罚函数（penalty）形式，将约束吸收进目标函数，并证明：只要分解的秩 $k$ 满足 $k(k+1)/2 > m$（即约束数量 $m$ 的亚二次方量级），对几乎所有代价矩阵，任意近似二阶稳定点（approximate second-order stationary point）都是全局最优解；同时通过平滑分析（smoothed analysis）将结论推广到只能计算近似稳定点的实际算法场景，并以 Max-Cut 和矩阵补全为例验证了结论。这一结果为大规模 SDP 的高效低秩求解提供了严格的理论保障，说明适当提升秩参数就能使原本 NP 难的非凸问题变得"易于"优化。
原文 arXiv:1803.00186;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1803.00186v1