Nonconvex landscapes for Z2 synchronization and graph clustering are benign near exact recovery thresholds

We study the optimization landscape of a smooth nonconvex program arising from synchronization over the two-element group Z2, that is, recovering z1, dots, zn ∈ ± 1 from (noisy) relative measurements Rij ≈ zi zj. Starting from a max-cut--like combinatorial problem, for integer parameter r ≥ 2, the nonconvex problem we study can be viewed both as a rank-r Burer--Monteiro factorization of the standard max-cut semidefinite relaxation and as a relaxation of ± 1 to the unit sphere in Rr. First, we present deterministic, non-asymptotic conditions on the measurement graph and noise under which every second-order critical point of the nonconvex problem yields exact recovery of the ground truth. Then, via probabilistic analysis, we obtain asymptotic guarantees for three benchmark problems: (1) synchronization with a complete graph and Gaussian noise, (2) synchronization with an ErdHos--R'enyi random graph and Bernoulli noise, and (3) graph clustering under the binary symmetric stochastic block model. In each case, we have, asymptotically as the problem size goes to infinity, a benign nonconvex landscape near a previously-established optimal threshold for exact recovery; we can approach this threshold to arbitrary precision with large enough (but finite) rank parameter r. In addition, our results are robust to monotone adversaries.