How well do local algorithms solve semidefinite programs?

DOI10.1145/3055399.3055451MaRDI QIDQ4978006zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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)