When Are Nonconvex Problems Not Scary?
arXiv:1510.06096
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.
arXiv comment6 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 (18)
- The Loss Surfaces of Multilayer Networks
- Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
- Guaranteed Matrix Completion via Non-convex Factorization
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank- Updates
- Simple, Efficient, and Neural Algorithms for Sparse Coding
- New Algorithms for Learning Incoherent and Overcomplete Dictionaries
- 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
- Dropping Convexity for Faster Semi-definite Optimization
- More Algorithms for Provable Dictionary Learning
- Complete Dictionary Recovery over the Sphere
- A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
- The local convexity of solving systems of quadratic equations
- Provable Tensor Methods for Learning Mixtures of Generalized Linear Models
- Fast Exact Matrix Completion with Finite Samples
Cited by in corpus (58)
- 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
- Fast, Robust and Non-convex Subspace Recovery
- 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
- The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences
- Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
- 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
- Learning a Single Neuron with Gradient Methods
- An Unconstrained Layer-Peeled Perspective on Neural Collapse
- Fair Principal Component Analysis and Filter Design
- Complete Dictionary Learning via -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
- Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
- On Gradient Descent Algorithm for Generalized Phase Retrieval Problem
- 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 Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
- On the Global Convergence of Continuous-Time Stochastic Heavy-Ball Method for Nonconvex Optimization
- On the Reconstruction Risk of Convolutional Sparse Dictionary Learning
- PCA by Optimisation of Symmetric Functions has no Spurious Local Optima
- Distributed Gradient Methods for Nonconvex Optimization: Local and Global Convergence Guarantees
- A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guarantees
- Global Optimality in Distributed Low-rank Matrix Factorization
- Tightness of a new and enhanced semidefinite relaxation for MIMO detection
- Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
- PCA by Determinant Optimization has no Spurious Local Optima
- Implicit regularization and solution uniqueness in over-parameterized matrix sensing
- Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
- Single-Look Multi-Master SAR Tomography: An Introduction
- Stochastic Approximation for Online Tensorial Independent Component Analysis
- Parameter Critic: a Model Free Variance Reduction Method Through Imperishable Samples
- Submodular + Concave
- Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
- Conditions for Exact Convex Relaxation and No Spurious Local Optima
- On the Optimization Landscape of Maximum Mean Discrepancy