209. Benign landscapes for synchronization on spheres via normalized Laplacian matrices
Invited abstract in session WC-8: Advances in non-convex optimization, stream Optimization for machine learning.
Wednesday, 14:00-16:00Room: B100/7007
Authors (first author is the speaker)
| 1. | Andrew McRae
|
| Institute of Mathematics, EPFL |
Abstract
I will present new results on the nonconvex landscapes of synchronization problems on spheres. The key tool is a deterministic landscape condition extending a recent result of Rakoto Endor and Waldspurger. If a certain problem-dependent Laplacian matrix (potentially with diagonal preconditioner, e.g., in the normalized graph Laplacian) has small enough condition number, the nonconvex landscape is benign. Our extension, which is to use a preconditioner, gives tighter results for many problems. This has consequences for several applications. For a spherical relaxation of the problem of synchronization over the two-element group $Z_2$, we show that, for problem instances coming from several popular statistical models, relaxing to any higher-dimensional sphere (even the unit circle, which was proposed by Burer et al. for max-cut and by Bandeira et al. for synchronization) is tight, has a benign landscape, and gives exact statistical recovery throughout the asymptotic statistical regimes where exact recovery is possible. Second, we consider the global synchronization of networks of coupled oscillators under the (homogeneous) Kuramoto model. We prove new and optimal asymptotic results for certain random signed networks, and we give new and simple proofs for several existing state-of-the-art results. For certain network types, the Laplacian condition number result is optimal. This work appears in the preprint https://arxiv.org/abs/2503.18801.
Keywords
- Large-scale optimization
- First-order optimization
- Global optimization
Status: accepted
Back to the list of papers