Tightness and Error Exponents of SDP with Logarithmically Many Communities
Abstract
We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with n=km vertices, we consider the regime k/log m→γ>0, with edge probabilities αlog m/m within communities and βlog m/m across them, for fixed α>β>0. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.
Related
- Radial-type error bounds for semidefinite feasibility problems without strict feasibility: qualitative estimates and asymptotic tightness
- The Transmitter Trojan Channel: Achievable Rates and Error Exponents
- Rényi divergences and binary state discrimination error exponents for fermionic quasi-free states
- Region bounds, error margins and certified positivity in the numerical conformal bootstrap; Or the first mathematically rigorous bounds on the 3d Ising CFT critical exponents
- A class of high-order discontinuous-Galerkin methods satisfying infinitely many entropy conditions with provable error estimates and strong convergence for general nonlinear conservation laws
BibTeX
@misc{guo2026tightness,
title = {{Tightness and Error Exponents of SDP with Logarithmically Many Communities}},
author = {Shengtao Guo and Ethan X. Fang and Junwei Lu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09303},
eprint = {2610.09303},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09303},
}
RIS
TY - UNPB
TI - Tightness and Error Exponents of SDP with Logarithmically Many Communities
AU - Shengtao Guo
AU - Ethan X. Fang
AU - Junwei Lu
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09303
UR - https://arxiv.org/abs/2610.09303
AB - We study a semidefinite programming (SDP) relaxation for community recovery when the number of communities grows logarithmically. In the balanced stochastic block model with n=km vertices, we consider the regime k/log m→γ>0, with edge probabilities αlog m/m within communities and βlog m/m across them, for fixed α>β>0. We derive the sharp asymptotic tightness boundary away from critical cases. When rare vertices cause tightness to fail while the bulk remains spectrally stable, the normalized matrix error of every near-optimal solution still vanishes. We prove matching high-probability exponents for this error and the normalized optimal objective gain, governed by the same local correction that determines tightness. Throughout this spectrally stable region, a single SDP solve followed by explicit rounding and refinement achieves exact community recovery above the information-theoretic threshold. This guarantee holds even when the planted community matrix is not an optimal solution to the SDP.
ER -