Global rates of convergence for nonconvex optimization on manifolds

DOI10.1093/IMANUM/DRX080MaRDI QIDQ5113326zbMATH OpenOpenAlexFDO

Authors Nicolas Boumal, P.-A. Absil, Coralia Cartis

Publication date 4 June 2020

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.08101

zbMATH Keywords

complexityRiemannian optimizationtrust-region methodgradient descentoptimization on manifolds

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Optimality conditions and duality in mathematical programming (90C46) Nonconvex programming, global optimization (90C26)

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 $varepsilon$. 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 $varepsilon$ in $O(1/varepsilo{n}^2)$ iterations. Furthermore, RTR returns a point where also the Riemannian Hessian's least eigenvalue is larger than $-varepsilon$ in $O(1/varepsilo{n}^3)$ iterations. There are no assumptions on initialization. The rates match their (sharp) unconstrained counterparts as a function of the accuracy $varepsilon$ (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.

Recommendations

• Erratum to: ``Global rates of convergence for nonconvex optimization on manifolds
• Globally convergent optimization algorithms on Riemannian manifolds: Uniform framework for unconstrained and constrained optimization
• Rate of convergence for proximal point algorithms on Hadamard manifolds
• Convergence rates of gradient methods for convex optimization in the space of measures
• Rates of Convergence for a Class of Global Stochastic Optimization Algorithms
• Global convergence of nonmonotone descent methods for unconstrained optimization problems
• Global convergence of ADMM in nonconvex nonsmooth optimization
• Global convergence of a curvilinear search for non-convex optimization
• On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
• Global optimality conditions for nonconvex optimization

Cited in

(64)

• An inexact Riemannian proximal gradient method
• Faster Riemannian Newton-type optimization by subsampling and cubic regularization
• Riemannian Optimization on the Symplectic Stiefel Manifold
• An accelerated first-order method for non-convex optimization on manifolds
• Nonlinear matrix recovery using optimization on the Grassmann manifold
• Riemannian proximal gradient methods
• Mini-workshop: Computational optimization on manifolds. Abstracts from the mini-workshop held November 15--21, 2020 (online meeting)
• Parameter-free accelerated gradient descent for nonconvex minimization
• Riemannian preconditioned coordinate descent for low multilinear rank approximation
• A Riemannian dimension-reduced second-order method with application in sensor network localization
• Quotient geometry with simple geodesics for the manifold of fixed-rank positive-semidefinite matrices
• A feasible method for general convex low-rank SDP problems
• Multivariate expectile-based distribution: properties, Bayesian inference, and applications
• On the optimization landscape of tensor decompositions
• Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangian
• Smoothing algorithms for nonsmooth optimization over the Stiefel manifold with applications to the graph Fourier basis problem
• New vector transport operators extending a Riemannian CG algorithm to generalized Stiefel manifold with low-rank applications
• Proximal quasi-Newton method for composite optimization over the Stiefel manifold
• An exact penalty approach for optimization with nonnegative orthogonality constraints
• Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
• Simple algorithms for optimization on Riemannian manifolds with constraints
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• An active-set proximal quasi-Newton algorithm for ℓ₁-regularized minimization over a sphere constraint
• Non-convex exact community recovery in stochastic block model
• Convergence and worst-case complexity of adaptive Riemannian trust-region methods for optimization on manifolds
• On the simplicity and conditioning of low rank semidefinite programs
• Trace Lasso regularization for adaptive sparse canonical correlation analysis via manifold optimization approach
• A brief introduction to manifold optimization
• Riemannian gradient descent methods for graph-regularized matrix completion
• Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact Riemannian submanifold embedded in Euclidean space
• Adaptive regularization with cubics on manifolds
• An adaptive Riemannian gradient method without function evaluations
• Sparse additive function decompositions facing basis transforms
• Riemannian trust regions with finite-difference Hessian approximations are globally convergent
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
• A Riemannian optimization approach to the radial distribution network load flow problem
• Structured Quasi-Newton Methods for Optimization with Orthogonality Constraints
• Nonconvex phase synchronization
• Rank optimality for the Burer-Monteiro factorization
• Memoryless quasi-Newton methods based on the spectral-scaling Broyden family for Riemannian optimization
• Gradient method for optimization on Riemannian manifolds with lower bounded curvature
• Globally convergent optimization algorithms on Riemannian manifolds: Uniform framework for unconstrained and constrained optimization
• A Riemannian Proximal Newton Method
• A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
• Geometric Methods on Low-Rank Matrix and Tensor Manifolds
• Retraction-based direct search methods for derivative free Riemannian optimization
• Proximal gradient method for nonsmooth optimization over the Stiefel manifold
• Riemannian Hamiltonian Methods for Min-Max Optimization on Manifolds
• Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization
• A Riemannian rank-adaptive method for low-rank matrix completion
• Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
• An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization
• Cholesky QR-based retraction on the generalized Stiefel manifold
• Riemannian optimization with a preconditioning scheme on the generalized Stiefel manifold
• Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy
• Recent Advances in Stochastic Riemannian Optimization
• On the quality of first-order approximation of functions with Hölder continuous gradient
• Approximate matrix and tensor diagonalization by unitary transformations: convergence of Jacobi-type algorithms
• Memory-efficient structured convex optimization via extreme point sampling
• Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
• Tracking and Regret Bounds for Online Zeroth-Order Euclidean and Riemannian Optimization
• First order methods for optimization on Riemannian manifolds
• Sequential quadratic optimization for nonlinear optimization problems on Riemannian manifolds
• Stochastic proximal gradient method FOR \(\ell_1\) regularized optimization over a sphere

This page was built for publication: Global rates of convergence for nonconvex optimization on manifolds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113326)