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

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2024.

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

- [Benign landscape for Burer-Monteiro factorizations of MaxCut-type semidefinite programs](https://mlsanity.com/paper/2411.03103/) (2024)

## Abstract (arXiv)

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.