A Grothendieck-type inequality for local maxima
Andrea Montanari111Department of Electrical Engineering and Department of Statistics, Stanford University
Abstract
A large number of problems in optimization, machine learning, signal processing can be effectively addressed by suitable semidefinite programming (SDP) relaxations. Unfortunately, generic SDP solvers hardly scale beyond instances with a few hundreds variables (in the underlying combinatorial problem). On the other hand, it has been observed empirically that an effective strategy amounts to introducing a (non-convex) rank constraint, and solving the resulting smooth optimization problem by ascent methods. This non-convex problem has –generically– a large number of local maxima, and the reason for this success is therefore unclear.
中文速览
把一类重要的半正定规划（SDP）问题转化成低秩非凸优化之后，梯度上升算法在实践中效果出奇地好，但理论上始终说不清楚"为什么局部最优就够用"。本文针对在椭球体（elliptope）上最大化线性泛函这一核心SDP，严格证明了：当秩约束为 k 时，**所有**局部极大值与SDP全局最优解之间的差距都不超过 $(9/\sqrt{k})\,n\|A\|_2$；在典型应用场景中 $\|A\|_2 = O(1)$、SDP最优值为 $\Theta(n)$，因此只需将 k 取为与问题规模 n 无关的固定常数，就能把相对误差压到任意小。这一结论从理论上解释了为何用少量维度（如 k=20）做非凸松弛即可逼近精确SDP解，为大规模图聚类等实际算法提供了坚实的理论保证，同时也在Grothendieck不等式与非凸优化全局结构之间建立了新的联系。
原文 arXiv:1603.04064;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1603.04064v1