Probably certifiably correct algorithms

This post is based on two papers (one and two). The task is to quickly solve typical instances of a given problem, and to quickly produce a certificate of that solution. Generally, problems of interest are NP-hard, and so we consider a random distribution on problem instances with the philosophy that real-world instances might mimic this distribution. In my community, it is common to consider NP-hard optimization problems:

minimize subject to .     (1)

In some cases, is convex but is not, and so one might relax accordingly:

minimize subject to ,     (2)

where is some convex set. If the minimizer of (2) happens to be a member of , then it’s also a minimizer of (1) — when this happens, we say the relaxation is tight. For some problems (and distributions on instances), the relaxation is typically tight, which means that (1) can be typically solved by instead solving (2); for example, this phenomenon occurs in phase retrieval, in community detection, and in geometric clustering. Importantly, strong duality ensures that solving the dual of the convex relaxation provides a certificate of optimality.

At this point, it seems that our original task has been accomplished, provided the convex optimization is sufficiently fast. In the cases of phase retrieval, community detection and k-means clustering, the program (2) amounts to a semidefinite program, which can certainly be solved in polynomial time, but the runtimes scale much worse than alternatives like Wirtinger flow, degree-profiling and Lloyd’s algorithm. On the other hand, the fast alternatives fail to produce certificates of optimality.

To get around this, we first recall how to prove that (2) is typically tight. First, there is a planted solution that solves (1) with high probability (the randomness is in and/or ). For example, in the case of phase retrieval, is the ground truth. The goal is to prove that is typically the unique solution of the relaxation (2). To do so, construct a function such that typically certifies the optimality of . In phase retrieval, leverages the golfing scheme, in community detection, is completely determined by complementary slackness, but in k-means clustering, is only partially determined by complementary slackness (the rest is chosen by an artform of sorts; note the difference between this choice and that choice). Once we have , it remains to show that for each , is typically dual feasible, and for positive semidefinite programs, this amounts to checking whether a certain random matrix is positive semidefinite (so spectral estimates like these become useful here).

At this point, it seems pretty easy to overcome the fact that fast solvers like Wirtinger flow fail to produce optimality certificates: Take the fast solver’s solution, plug it into the function , and then check that the output is dual feasible. Since dual feasibility can be tested by spectral methods, this should be particularly fast. This is Afonso‘s main point in this paper.

The only difficulty here is that the power method (for example) uses a random initialization. As such, while the power method will quickly converge with high probability, there is a small probability that it will take some time before converging. Since we can only run finitely many iterations of the power method, this naturally leads one to treat the power method’s output as a test statistic for a hypothesis test (see section 3.1 in this paper). Overall, one may compute , run the power method, and then perform a hypothesis test. In the end, one may quickly say something like “ is the unique solution to (1) with confidence level 0.9999″. Indeed, unlike traditional statistics, it’s rather inexpensive to produce high levels of confidence here. For example, running the power method twice will change the confidence level from to .