On the low-rank approach for semidefinite programs arising in synchronization and community detection

Introduction

Estimation problems in many fields, including signal processing, statistics and machine learning, are formulated as intractable optimization problems. A now popular technique to attempt solving some of these problems is to replace the difficult optimization problem by a surrogate tractable convex problem and take advantage of existing machinery for convex optimization. In many instances, the surrogate problem is obtained by considering a larger, convex feasible space, and thus it is often called a convex relaxation. Relaxations based on semidefinite programming are among the most popular.

While computing the maximum likelihood estimator (MLE) for either of the problems above is known to be computationally intractable, several heuristics have been proposed and studied. A particularly successful approach is based on Semidefinite Programming. Following the seminal work of [goemans1995maxcut] in the context of the Max-Cut problem, the maximum likelihood estimation problem (originally an intractable optimization problem in $n$ node variables) is relaxed to a semidefinite program (SDP) (a tractable problem on $n^{2}$ variables). Importantly, the solution to the SDP is only guaranteed to correspond to the solution of the original problem if it has rank 1. Enforcing this constraint explicitly would render the problem intractable. Remarkably, in some regimes, it is known that the solution of this semidefinite program is naturally of rank 1, and that furthermore this solution allows to identify the true labels ([abbe2014decoding, bandeira2014tightness, abbe2014exact, bandeira2015laplacian, Hajek_et_al_SBM_SDP]).

While SDP’s are known to be solvable up to arbitrary precision in polynomial time ([nesterov2004introductory]), the increase in dimension due to the lifting technique (the relaxation) and the semidefiniteness constraint render solving them rather slow in practice. This is mainly because intermediate iterates involve matrix decompositions of dense, full-rank matrices of size $n$. On the other hand, in certain regimes, the optimal solution is expected to have low rank. Indeed, in the problems studied here, the solution being rank 1 coincides precisely with it corresponding to the desirable MLE. It is then natural to attempt to reach the solution via a sequence of similarly simple objects instead.

The most popular and successful such low-rank approach is SDPLR, as proposed in (sdplr; burer2005local) (also in a particular form in (burer2002rank)). In a nutshell, the idea is to restrict the search space to matrices of bounded rank. While, after adding this rank constraint, the optimization problem is no longer convex (and it is hence unclear whether it is tractable or not), this approach is empirically successful for a variety of instances (sdplr; journee2010low; bandeira2014tightness; boumal2015staircase).

In this paper, we focus on a selection of well-studied problems, keeping in mind that the proposed analysis has the potential to generalize to many problems where semidefinite relaxations are successful yet demanding to solve. A more general setting will be the focus of a future publication.

It is also worth noting that semidefinite relaxations have been observed to work well on problems for which other standard heuristics seem to not perform well. One relevant example is the Multireference Alignment problem (Bandeira_Charikar_Singer_Zhu_Alignment). Furthermore, low-rank semidefinite programming has the potential to yield a posteriori certifiably correct algorithms (Bandeira_PCC) and is known to be robust to certain monotone adversary models (Feige_Kilian_bisection_01; Moitra_SBMadversary).

Because only $zz^{T}$ is measured, the labels can only be estimated up to a global sign flip. One can also consider more realistic noise models on which $Y_{ij}$ also takes binary values (abbe2014decoding) but, for the sake of simplicity, we will consider Gaussian noise. Since $\|zz^{T}\|=n$ and $\|\sigma W\|$ concentrates around a constant multiple of $\sigma\sqrt{n}$ (in operator norm), a natural way to parametrize the signal-to-noise ratio is by taking $\lambda=\frac{\sqrt{n}}{\sigma}$. For this reason, some authors consider the scaled model

The problems of recovering $z$ from $Y$ or $\mathcal{Y}$ are clearly equivalent. The former choice of notation has been used, for example, in (bandeira2014tightness; bandeira2015laplacian) and has the advantage of highlighting the fact that the observation is an entry-wise noisy version of the ground truth, while the latter has been used in (javanmard2015phase) and has the advantage of highlighting the spike model interpretation of the problem and making a more transparent connection with the well-studied spike model in random matrix theory and the BBP transition phenomenon (BBP_MC_BBP_2005; Feral_Peche_BBPWigner) (this connection had already been made in (singer2010angular)). For the sake of completeness, we will state our results in both notation choices.

The most natural approach to recovering $z$ is to consider the MLE, which solves

It is readily seen that solutions of this problem are the same as those of

which is known to the NP-hard in general. In fact, when $Y\succeq 0$ this is known as the little Grothendieck problem (briet2014grothendieck; bandeira2013approximating), and, when $Y$ corresponds to the Laplacian of a graph, it corresponds to the Max-Cut problem (goemans1995maxcut).

Following the now standard lifting technique (dating back at least to goemans1995maxcut ), we set a new variable $X=xx^{T}$ and write the equivalent formulation

Problems \eqrefeq:littleGrothendieck and \eqrefSDP:rank1 are equivalent. One arrives at a tractable SDP formulation by dropping the problematic rank constraint:

By construction, problem \eqrefSDP:fullrank has the same solutions if $Y$ is replaced with $\mathcal{Y}$ (but it will have a different optimal value, since $Y$ and $\mathcal{Y}$ are scaled versions of each other.)

Recall the model \eqrefeq:noisemodel:sigma (or equivalently \eqrefeq:noisemodel:lambda). It is known that, as long as $\sigma<\sqrt{\frac{n}{2\log n}}$, or equivalently $\lambda>\sqrt{2\log n}$, with high probability, the solution $X$ of \eqrefSDP:fullrank is unique and corresponds exactly to the ground truth $X=zz^{T}$. We refer to this phenomenon as exact recovery. It is also known that on the other side of this threshold exact recovery is information-theoretically impossible, showcasing the efficiency of semidefinite relaxations for this type of task (bandeira2014tightness; bandeira2015laplacian).

While exact recovery is impossible for constant $\lambda$ (or, equivalently, $\sigma\sim\sqrt{n}$), simply taking the top eigenvector of $\mathcal{Y}$ is known to produce an estimator that correlates non-trivially with the ground truth, precisely when $\lambda>1$ (Feral_Peche_BBPWigner; singer2010angular). This phenomenon is often referred to as the BBP transition (BBP_MC_BBP_2005). This motivates the question of whether \eqrefSDP:fullrank gives meaningful results for the constant $\lambda$ regime (Montanari_SDPdetectionSBM; javanmard2015phase; Guedon_SBMgrothendieck). In the context of community detection, this question was first addressed by Guedon_SBMgrothendieck. In (Montanari_SDPdetectionSBM), a phase transition is shown to exist at $\lambda=1$: similarly to what happens with the top eigenvalue of $\mathcal{Y}$ (Feral_Peche_BBPWigner). For $\lambda<1$, the value of \eqrefSDP:fullrank with cost $\mathcal{Y}$ converges (in probability) to $2$, and for $\lambda>1$ its limit is strictly larger than $2$. javanmard2015phase give fascinating predictions, based on non-rigorous statistical mechanics tools, for the behavior of both \eqrefSDP:fullrank and \eqrefeq:littleGrothendieck as a function of $\lambda$.

In transiting from \eqrefSDP:rank1 to \eqrefSDP:fullrank, one effectively replaces the constraint $\operatorname{rank}(X)\leq 1$ by the vacuous constraint $\operatorname{rank}(X)\leq n$, thus going from a combinatorial problem to a tractable but high-dimensional SDP. One of the insights of sdplr; burer2005local is that relaxing the rank only partially, as $\operatorname{rank}(X)\leq p$ for variable $p$, gives access to a family of low-dimensional (but nonconvex) nonlinear optimization problems, which can be put to good use to understand both \eqrefSDP:rank1 and \eqrefSDP:fullrank.