Smoothed analysis of the low-rank approach for smooth semidefinite programs
We consider semidefinite programs (SDPs) of size n with equality constraints. In order to overcome scalability issues, Burer and Monteiro proposed a factorized approach based on optimizing over a matrix Y of size n × k such that X = Y Y * is the SDP variable. The advantages of such formulation are twofold: the dimension of the optimization variable is reduced, and positive semidefiniteness is naturally enforced. However, optimization in Y is non-convex. In prior work, it has been shown that, when the constraints on the factorized variable regularly define a smooth manifold, provided k is large enough, for almost all cost matrices, all second-order stationary points (SOSPs) are optimal. Importantly, in practice, one can only compute points which approximately satisfy necessary optimality conditions, leading to the question: are such points also approximately optimal? To answer it, under similar assumptions, we use smoothed analysis to show that approximate SOSPs for a randomly perturbed objective function are approximate global optima, with k scaling like the square root of the number of constraints (up to log factors). Moreover, we bound the optimality gap at the approximate solution of the perturbed problem with respect to the original problem. We particularize our results to an SDP relaxation of phase retrieval.
This paper concerns the Burer-Monteiro (i.e. low-rank) factorization heuristic for solving SDP problems of the form   min     s.t.  A(X) = b, X \succeq 0.   The BM heuristic relies on the fact when the constraint set is compact, the above SDP has a global solution with rank up to square root of the **number of the linear constraints** (denoted as m). This allows one to perform substitution X = YY^* and then perform a heuristic numerical search in the low-dimensional subspace of Y. In general, there is no guarantee such heuristic search would find the global solution, i.e. Y such that YY^* solves the original SDP. Recent advances (Bounal et al. 2016b, 2018) show that for almost all matrix C, when A(YY^*) defines a smooth manifold, all second-order stationary points (SOSP) of the resulting nonconvex program are global optimal, provided the rank of Y scales as sqrt(m). In practice, numerical methods can at least find approximate SOSP in finite running time. This paper shows that on average (due to the smoothed analysis), all approximate SOSP's produce approximate global optima to the original SDP (measured in terms of the objective value), again so long as the rank of Y scales as sqrt(m).   Solving large-scale SDP is of broad interest to many scientific communities with computational components, including machine learning. The current work, combined with the other recent works, build a solid theoretical foundation for the practical relevance and viability of the BM heuristic.   The result is closely connected to another recent work Bhojanapalli et al 2018. The two papers address the same stability issue and share some similar points at the technical level. One importance difference is that the current work focuses on a feasible (constrained) version, whereas the other work deals with the penalty version in which the feasibility may not be guaranteed. They work under different technical conditions also, e.g., whether or not A(YY^*) defines a smooth manifold.    Additional comments:   * Theorem 1.1: From hindsight, it is clear that the perturbation is to avoid the worst cases so that a result can be stated for all C. But around theorem 1.1, this is not clearly explained. This could be confusing at an initial read.   * Eq (5): After the first (, I think it should be C instead of CY.   * Fig 1: What do you mean by size of the instance for the horizontal axis? It seems confusing if one were to read it against the last paragraph of the numerical experiment section.   * For the phase retrieval experiment, curious to know if the solver always returns approximate rank-one solutions.