Global rates of convergence for nonconvex optimization on manifolds

Abstract

We consider the minimization of a cost function $f$ on a manifold $M$ using Riemannian gradient descent and Riemannian trust regions (RTR). We focus on satisfying necessary optimality conditions within a tolerance $\epsilon$. Specifically, we show that, under Lipschitz-type assumptions on the pullbacks of $f$ to the tangent spaces of $M$, both of these algorithms produce points with Riemannian gradient smaller than $\epsilon$ in $O(1/{\epsilon }^2)$ iterations. Furthermore, RTR returns a point where also the Riemannian Hessian's least eigenvalue is larger than $-\epsilon$ in $O(1/{\epsilon }^3)$ iterations. There are no assumptions on initialization. The rates match their (sharp) unconstrained counterparts as a function of the accuracy $\epsilon$ (up to constants) and hence are sharp in that sense. These are the first deterministic results for global rates of convergence to approximate first- and second-order Karush-Kuhn-Tucker points on manifolds. They apply in particular for optimization constrained to compact submanifolds of ${\mathbb{R}}^n$, under simpler assumptions.

33 pages, IMA Journal of Numerical Analysis, 2018

References in corpus (2)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation

Cited by in corpus (87)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Bispectrum Inversion with Application to Multireference Alignment
• A Dimension Reduction-Based Joint Activity Detection and Channel Estimation Algorithm for Massive Access
• Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Interactive Dimensionality Reduction for Comparative Analysis
• Asynchronous and Parallel Distributed Pose Graph Optimization
• A Riemannian rank-adaptive method for low-rank matrix completion
• Trivializations for Gradient-Based Optimization on Manifolds
• Efficiently escaping saddle points on manifolds
• Riemannian Optimization on the Symplectic Stiefel Manifold
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method
• Towards Riemannian Accelerated Gradient Methods
• Adaptive regularization with cubics on manifolds
• Compressive gate set tomography
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Riemannian adaptive stochastic gradient algorithms on matrix manifolds
• Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy
• Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form
• An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints
• Precoder Design for Massive MIMO Downlink with Matrix Manifold Optimization
• The basins of attraction of the global minimizers of non-convex inverse problems with low-dimensional models in infinite dimension
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Escaping from saddle points on Riemannian manifolds
• Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Provably robust estimation of modulo 1 samples of a smooth function with applications to phase unwrapping
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• Economical Quasi-Newton Self Consistent Field Solver
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
• A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance
• Riemannian Smoothing Gradient Type Algorithms]{Riemannian Smoothing Gradient Type Algorithms for Nonsmooth Optimization Problem on Compact Riemannian Submanifold Embedded in Euclidean Space
• An Alternating Manifold Proximal Gradient Method for Sparse PCA and Sparse CCA
• EigenGame: PCA as a Nash Equilibrium
• Parameter-free accelerated gradient descent for nonconvex minimization
• New vector transport operators extending a Riemannian CG algorithm to generalized Stiefel manifold with low-rank applications
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Newton retraction as approximate geodesics on submanifolds
• Error bound and exact penalty method for optimization problems with nonnegative orthogonal constraint
• Two-sample Test with Kernel Projected Wasserstein Distance
• Analysis of the Optimization Landscapes for Overcomplete Representation Learning
• Variance reduction for Riemannian non-convex optimization with batch size adaptation
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Semi-Riemannian Manifold Optimization
• An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization
• Convergence Analysis of Riemannian Stochastic Approximation Schemes
• Projection Robust Wasserstein Barycenters
• Simple algorithms for optimization on Riemannian manifolds with constraints
• Short-and-Sparse Deconvolution -- A Geometric Approach
• Decentralized Riemannian Gradient Descent on the Stiefel Manifold
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• The Proxy Step-size Technique for Regularized Optimization on the Sphere Manifold
• Kernel-based Translations of Convolutional Networks
• Gradient Method for Optimization on Riemannian Manifolds with Lower Bounded Curvature
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
• Riemannian Stochastic Variance-Reduced Cubic Regularized Newton Method for Submanifold Optimization
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• On the simplicity and conditioning of low rank semidefinite programs
• An inexact augmented Lagrangian method for nonsmooth optimization on Riemannian manifold
• Multichannel Sparse Blind Deconvolution on the Sphere
• Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
• A Brief Introduction to Manifold Optimization
• Accelerated Algorithms for Convex and Non-Convex Optimization on Manifolds
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Smoothed analysis of the low-rank approach for smooth semidefinite programs
• Topological Interference Management with User Admission Control via Riemannian Optimization
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming
• Proximal algorithms for constrained composite optimization, with applications to solving low-rank SDPs
• Blind Demixing for Low-Latency Communication
• Riemannian conditional gradient methods for composite optimization problems
• Riemannian Proximal Gradient Methods (extended version)
• Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold
• Non-Convex Exact Community Recovery in Stochastic Block Model
• An Inexact Manifold Augmented Lagrangian Method for Adaptive Sparse Canonical Correlation Analysis with Trace Lasso Regularization
• Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds
• BN-invariant sharpness regularizes the training model to better generalization
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization
• An Inexact Riemannian Proximal Gradient Method
• A Novel Riemannian Optimization Approach to the Radial Distribution Network Load Flow Problem
• On the convergence of Jacobi-type algorithms for Independent Component Analysis
• Riemannian preconditioned coordinate descent for low multi-linear rank approximation
• The duality structure gradient descent algorithm: analysis and applications to neural networks