When Are Nonconvex Problems Not Scary?

Abstract

In this note, we focus on smooth nonconvex optimization problems that obey: (1) all local minimizers are also global; and (2) around any saddle point or local maximizer, the objective has a negative directional curvature. Concrete applications such as dictionary learning, generalized phase retrieval, and orthogonal tensor decomposition are known to induce such structures. We describe a second-order trust-region algorithm that provably converges to a global minimizer efficiently, without special initializations. Finally we highlight alternatives, and open problems in this direction.

6 pages, 3 figures. New examples on phase synchronization and community detection added; emphasis on all local minimizers being global added; exposition is polished. This is a concise expository article that avoids much technical rigor. We will make a separate submission with full technical details in future

References in corpus (6)

• The Loss Surfaces of Multilayer Networks
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Simple, Efficient, and Neural Algorithms for Sparse Coding
• On the saddle point problem for non-convex optimization
• Fast matrix completion without the condition number
• Tensor vs Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations

Cited by in corpus (57)

• Non-convex Optimization for Machine Learning
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Matrix Completion has No Spurious Local Minimum
• Nonconvex phase synchronization
• Fast Algorithms for Robust PCA via Gradient Descent
• Global Optimality in Low-rank Matrix Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Learning One-hidden-layer Neural Networks with Landscape Design
• First-order Methods Almost Always Avoid Saddle Points
• Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information
• Accelerated Methods for Non-Convex Optimization
• A Geometric Analysis of Neural Collapse with Unconstrained Features
• Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
• Convolutional Phase Retrieval via Gradient Descent
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Inexact Newton Methods for Stochastic Nonconvex Optimization with Applications to Neural Network Training
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• Fair Principal Component Analysis and Filter Design
• Learning a Single Neuron with Gradient Methods
• Complete Dictionary Learning via ${\ell }_p$-norm Maximization
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Approximate Message Passing with Parameter Estimation for Heavily Quantized Measurements
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• On Gradient Descent Algorithm for Generalized Phase Retrieval Problem
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Recovery and Generalization in Over-Realized Dictionary Learning
• Short-and-Sparse Deconvolution -- A Geometric Approach
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• A Geometric Approach of Gradient Descent Algorithms in Linear Neural Networks
• On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Global Optimality in Distributed Low-rank Matrix Factorization
• PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
• Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
• On the Reconstruction Risk of Convolutional Sparse Dictionary Learning
• A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Implicit regularization and solution uniqueness in over-parameterized matrix sensing
• Tightness of a new and enhanced semidefinite relaxation for MIMO detection
• PCA by Determinant Optimization has no Spurious Local Optima
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Conditions for Exact Convex Relaxation and No Spurious Local Optima
• Parameter Critic: a Model Free Variance Reduction Method Through Imperishable Samples
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• Single-Look Multi-Master SAR Tomography: An Introduction
• On the Optimization Landscape of Maximum Mean Discrepancy
• Submodular + Concave