From Symmetry to Geometry: Tractable Nonconvex Problems

• DOI: 10.48550/arxiv.2007.06753
• Publication Date: 2020-01-01
• Authors: Zhang, Yuqian; Qu, Qing; Wright, John
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Computer Science - Information Theory; Computer Vision and Pattern Recognition (cs.CV); Information Theory (cs.IT); Computer Science - Computer Vision and Pattern Recognition; Machine Learning (stat.ML); 02 engineering and technology; Machine Learning (cs.LG); Statistics - Machine Learning; Optimization and Control (math.OC); 0202 electrical engineering, electronic engineering, information engineering; FOS: Mathematics; Mathematics - Optimization and Control

review paper, 38 pages, 10 figures, revision: correction of typos, adding more discussion on recent advances on deep learning<br/>As science and engineering have become increasingly data-driven, the role of optimization has expanded to touch almost every stage of the data analysis pipeline, from signal and data acquisition to modeling and prediction. The optimization problems encountered in practice are often nonconvex. While challenges vary from problem to problem, one common source of nonconvexity is nonlinearity in the data or measurement model. Nonlinear models often exhibit symmetries, creating complicated, nonconvex objective landscapes, with multiple equivalent solutions. Nevertheless, simple methods (e.g., gradient descent) often perform surprisingly well in practice. The goal of this survey is to highlight a class of tractable nonconvex problems, which can be understood through the lens of symmetries. These problems exhibit a characteristic geometric structure: local minimizers are symmetric copies of a single "ground truth" solution, while other critical points occur at balanced superpositions of symmetric copies of the ground truth, and exhibit negative curvature in directions that break the symmetry. This structure enables efficient methods to obtain global minimizers. We discuss examples of this phenomenon arising from a wide range of problems in imaging, signal processing, and data analysis. We highlight the key role of symmetry in shaping the objective landscape and discuss the different roles of rotational and discrete symmetries. This area is rich with observed phenomena and open problems; we close by highlighting directions for future research.<br/>