How Well Do Local Algorithms Solve Semidefinite Programs?

Understand

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\H{o}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.