Nonconvex landscapes for Z2 synchronization and graph clustering are benign near exact recovery thresholds
METADATA ONLY
Loading...
Author / Producer
Date
2024-07-18
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We study the optimization landscape of a smooth nonconvex program arising from synchronization over the two-element group $\mathbf{Z}_2$, that is, recovering $z_1, \dots, z_n \in \{\pm 1\}$ from (noisy) relative measurements $R_{ij} \approx z_i z_j$. Starting from a max-cut--like combinatorial problem, for integer parameter $r \geq 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 $\{ \pm 1 \}$ to the unit sphere in $\mathbf{R}^r$. 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 Erdős--Rényi 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
2407.13407
Publisher
Cornell University
Event
Edition / version
v1
Methods
Software
Geographic location
Date collected
Date created
Subject
Optimization and Control (math.OC); Statistics Theory (math.ST); FOS: Mathematics
Organisational unit
09679 - Bandeira, Afonso / Bandeira, Afonso
Notes
Funding
Related publications and datasets
Is previous version of: