How Well Do Local Algorithms Solve Semidefinite Programs?
This work addresses the dichotomy between local algorithms and SDP relaxations in high-dimensional statistics and machine learning, providing insights for graph partitioning problems, but it is incremental as it builds on existing models and methods.
The paper investigates the performance of local algorithms in solving semidefinite programming (SDP) relaxations for graph bisection on Erdős-Renyi random graphs, showing that a simple local algorithm achieves at most 8/9 suboptimality and 1+O(1/d) suboptimality for large degree, and a more sophisticated local algorithm matches empirical SDP values well.
Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this phenomenon, we study a classical SDP relaxation of the minimum graph bisection problem, when applied to Erdős-Renyi random graphs with bounded average degree $d>1$, and obtain several types of results. First, we use a dual witness construction (using the so-called non-backtracking matrix of the graph) to upper bound the SDP value. Second, we prove that a simple local algorithm approximately solves the SDP to within a factor $2d^2/(2d^2+d-1)$ of the upper bound. In particular, the local algorithm is at most $8/9$ suboptimal, and $1+O(1/d)$ suboptimal for large degree. We then analyze a more sophisticated local algorithm, which aggregates information according to the harmonic measure on the limiting Galton-Watson (GW) tree. The resulting lower bound is expressed in terms of the conductance of the GW tree and matches surprisingly well the empirically determined SDP values on large-scale Erdős-Renyi graphs. We finally consider the planted partition model. In this case, purely local algorithms are known to fail, but they do succeed if a small amount of side information is available. Our results imply quantitative bounds on the threshold for partial recovery using SDP in this model.