# From Symmetry to Geometry: Tractable Nonconvex Problems

arXiv: https://arxiv.org/abs/2007.06753 · HTML: https://mlsanity.com/paper/2007.06753/

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2020.

## Built on by (most cited first, 29 of 29)

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features](https://mlsanity.com/paper/2203.01238/) (2022)
- [An Unconstrained Layer-Peeled Perspective on Neural Collapse](https://mlsanity.com/paper/2110.02796/) (2021)
- [Are All Losses Created Equal: A Neural Collapse Perspective](https://mlsanity.com/paper/2210.02192/) (2022)
- [Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifold](https://mlsanity.com/paper/2209.09211/) (2022)
- [Symmetries, flat minima, and the conserved quantities of gradient flow](https://mlsanity.com/paper/2210.17216/) (2022)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation](https://mlsanity.com/paper/2406.04112/) (2024)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Neural Collapse in Multi-label Learning with Pick-all-label Loss](https://mlsanity.com/paper/2310.15903/) (2023)
- [A Global Geometric Analysis of Maximal Coding Rate Reduction](https://mlsanity.com/paper/2406.01909/) (2024)
- [Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective](https://mlsanity.com/paper/2109.09859/) (2021)
- [Convergence and Recovery Guarantees of the K-Subspaces Method for Subspace Clustering](https://mlsanity.com/paper/2206.05553/) (2022)
- [On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks](https://mlsanity.com/paper/2209.14501/) (2022)
- [Unique sparse decomposition of low rank matrices](https://mlsanity.com/paper/2106.07736/) (2021)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [A Geometric Approach to k-means](https://mlsanity.com/paper/2201.04822/) (2022)
- [Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?](https://mlsanity.com/paper/2302.10963/) (2023)
- [Learning with Noisy Labels Using Collaborative Sample Selection and Contrastive Semi-Supervised Learning](https://mlsanity.com/paper/2310.15533/) (2023)
- [Provable Meta-Learning with Low-Rank Adaptations](https://mlsanity.com/paper/2410.22264/) (2024)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [Unveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression](https://mlsanity.com/paper/2405.18237/) (2024)
- [Complex fractal trainability boundary can arise from trivial non-convexity](https://mlsanity.com/paper/2406.13971/) (2024)
- [On the Necessity of Metalearning: Learning Suitable Parameterizations for Learning Processes](https://mlsanity.com/paper/2401.00532/) (2023)
- [Sharper Convergence Rates for Nonconvex Optimisation via Reduction Mappings](https://mlsanity.com/paper/2506.08428/) (2025)
- [Joint Model and Data Sparsification via the Marginal Likelihood](https://mlsanity.com/paper/2605.29908/) (2026)
- [Rapid mixing for Gibbs measures in Riemannian manifolds](https://mlsanity.com/paper/2606.13453/) (2026)

## Abstract (arXiv)

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.