太阳成集团tyc7111cc统计与运筹系

学术报告

Local geometry determines global landscape in low-rank factorization for synchronization

凌舒扬 长聘助理教授

（上海纽约大学）

报告时间： 2023年12月20日 (星期三) 上午10：00-11：00

报告地点：沙河主E404

报告摘要：The orthogonal group synchronization problem, which focuses on recovering orthogonal group elements from their corrupted pairwise measurements, encompasses examples such as high-dimensional Kuramoto model on general signed networks, ℤ2-synchronization, community detection under stochastic block models, and orthogonal Procrustes problem. The semidefinite relaxation (SDR) has proven its power in solving this problem; however, its expensive computational costs impede its widespread practical applications. We consider the Burer-Monteiro factorization approach to the orthogonal group synchronization, an effective and scalable low-rank factorization to solve large scale SDPs. Despite the significant empirical successes of this factorization approach, it is still a challenging task to understand when the nonconvex optimization landscape is benign, i.e., the optimization landscape possesses only one local minimizer, which is also global. In this work, we demonstrate that if the degree of freedom within the factorization exceeds twice the condition number of the ``Laplacian" (certificate matrix) at the global minimizer, the optimization landscape is absent of spurious local minima. Our main theorem is purely algebraic and versatile, and it seamlessly applies to all the aforementioned examples: the nonconvex landscape remains benign under almost identical condition that enables the success of the SDR. Additionally, we illustrate that the Burer-Monteiro factorization is robust to ``monotone adversaries", mirroring the resilience of the SDR. In other words, introducing ``favorable" adversaries into the data will not result in the emergence of new spurious local minimizers.

报告人简介：凌舒扬现任职于上海纽约大学，是数据科学的长聘助理教授。在加入上海纽约大学之前，他于2017年至2019年在纽约大学柯朗数学研究所和数据科学研究所担任柯朗讲师。他在2017年6月从加州大学戴维斯分校应用数学专业获得博士学位。他的研究兴趣主要在数据科学、信息科学、优化和信号处理等，主要成果发表在如Foundations of Computational Mathematics, Mathematical Programming, SIAM Journal on Optimization/Imaging Science, Applied and Computational Harmonic Analysis, IEEE Transactions on Information Theory, Journal of Machine Learning Research等杂志上。他的研究获得多项国家自然科学基金、科技部国家重点研发计划青年科学家项目以及上海市级和国家级青年人才计划的支持。

邀请人：夏勇