On the landscape of synchronization networks: A perspective from nonconvex optimization

Shuyang Ling, Ruitu Xu, Afonso S. Bandeira

Research output: Contribution to journalArticle

Abstract

Studying the landscape of nonconvex cost functions is key towards a better understanding of optimization algorithms widely used in signal processing, statistics, and machine learning. Meanwhile, the famous Kuramoto model has been an important mathematical model for studying the synchronization phenomena of coupled oscillators over various network topologies. In this paper, we bring together these two seemingly unrelated objects by investigating the optimization landscape of a nonlinear function E(\bfittheta ) = 2 1 \sum 1\leq i,j\leq n aij(1 - cos(\theta i - \theta j)) associated with an underlying network and exploring the relationship between the existence of local minima and the network topology. This function arises naturally in the Burer-Monteiro method applied to \BbbZ 2 synchronization as well as matrix completion on the torus. Moreover, it corresponds to the energy function of the homogeneous Kuramoto model on complex networks for coupled oscillators. We prove that the minimizer of the energy function is unique up to a global translation under deterministic dense graphs and Erd\H os-R\'enyi random graphs with tools from optimization and random matrix theory. Consequently, the stable equilibrium of the corresponding homogeneous Kuramoto model is unique and the basin of attraction for the synchronous state of these coupled oscillators is the whole phase space minus a set of measure zero. In addition, our results address when the Burer-Monteiro method recovers the ground truth exactly from highly incomplete observations in \BbbZ 2 synchronization and shed light on the robustness of nonconvex optimization algorithms with respect to certain types of so-called monotone adversaries. Numerical simulations are performed to illustrate our results.

Original languageEnglish (US)
Pages (from-to)1879-1907
Number of pages29
JournalSIAM Journal on Optimization
Volume29
Issue number3
DOIs
StatePublished - 2019

Keywords

  • Dynamical system
  • Kuramoto model
  • Nonconvex optimization
  • Optimization landscape
  • Synchronization on networks

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'On the landscape of synchronization networks: A perspective from nonconvex optimization'. Together they form a unique fingerprint.

  • Cite this