2024/07/18 by McRae, Andrew D., Abdalla, Pedro, Bandeira, Afonso S. +1 · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2407.13407
We study the optimization landscape of a smooth nonconvex program arising from synchronization over the two-element group Z2, that is, recovering z1, …, 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 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.