# Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly

arXiv: https://arxiv.org/abs/1904.09635 · HTML: https://mlsanity.com/paper/1904.09635/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2019.

## Built on by (most cited first, 11 of 11)

- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Minimax Rates for Robust Community Detection](https://mlsanity.com/paper/2207.11903/) (2022)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [Optimal Orthogonal Group Synchronization and Rotation Group Synchronization](https://mlsanity.com/paper/2109.13491/) (2021)
- [SDP Achieves Exact Minimax Optimality in Phase Synchronization](https://mlsanity.com/paper/2101.02347/) (2021)
- [Top-K ranking with a monotone adversary](https://mlsanity.com/paper/2402.07445/) (2024)
- [Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2203.03110/) (2022)
- [Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model](https://mlsanity.com/paper/2306.12968/) (2023)
- [Robust Detection of Planted Subgraphs in Semi-Random Models](https://mlsanity.com/paper/2508.02158/) (2025)

## Abstract (arXiv)

We study the statistical performance of semidefinite programming (SDP) relaxations for clustering under random graph models. Under the mathbbZ2 Synchronization model, Censored Block Model and Stochastic Block Model, we show that SDP achieves an error rate of the form [ expBig[-big(1-o(1)big)barn I^* Big]. ] Here barn is an appropriate multiple of the number of nodes and I^* is an information-theoretic measure of the signal-to-noise ratio. We provide matching lower bounds on the Bayes error for each model and therefore demonstrate that the SDP approach is Bayes optimal. As a corollary, our results imply that SDP achieves the optimal exact recovery threshold under each model. Furthermore, we show that SDP is robust: the above bound remains valid under semirandom versions of the models in which the observed graph is modified by a monotone adversary. Our proof is based on a novel primal-dual analysis of SDP under a unified framework for all three models, and the analysis shows that SDP tightly approximates a joint majority voting procedure.