How well do local algorithms solve semidefinite programs?

DOI10.1145/3055399.3055451zbMATH Open1369.90118arXiv1610.05350OpenAlexW2539337210MaRDI QIDQ4978006FDOQ4978006

Authors:

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: 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 ErdH{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. 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 ErdH{o}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.

Full work available at URL: https://arxiv.org/abs/1610.05350

Recommendations

• Semidefinite programs on sparse random graphs and their application to community detection
• New abilities and limitations of spectral graph bisection
• Phase transitions in semidefinite relaxations
• scientific article; zbMATH DE number 2088028
• Local minima and convergence in low-rank semidefinite programming

zbMATH Keywords

community detectionsemidefinite program relaxationlocal algorithmnon-backtracking spectrum

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22)

Cited In (7)

• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• Suboptimality of local algorithms for a class of max-cut problems
• Semidefinite programs on sparse random graphs and their application to community detection
• Linear Programming and Community Detection
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• On the computational tractability of statistical estimation on amenable graphs

This page was built for publication: How well do local algorithms solve semidefinite programs?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978006)