Adaptive regularization with cubics on manifolds

2018/06/30 by Naman Agarwal, Nicolas Boumal, Brian Bullins +1 · 28 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Arc (geometry) #Eigenvalues and eigenvectors #Generalization #Hessian matrix #Lipschitz continuity #Numerical analysis #Regularization (linguistics) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.1007/s10107-020-01505-1

published in Mathematical Programming 188(1), 85-134 (Springer Science+Business Media) · 48 pages, 3 figures

openalex created_date 2019/02/21 · openalex publication_date 2020/05/13 · arxiv created 2020/05/16 · arxiv updated 2020/05/19 · openalex updated_date 2026/08/05

Abstract

Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the popular trust-region method, its iterations can be thought of as approximate, safe-guarded Newton steps. For cost functions with Lipschitz continuous Hessian, ARC has optimal iteration complexity, in the sense that it produces an iterate with gradient smaller than ε in O(1/ε^1.5) iterations. For the same price, it can also guarantee a Hessian with smallest eigenvalue larger than -ε^1/2. In this paper, we study a generalization of ARC to optimization on Riemannian manifolds. In particular, we generalize the iteration complexity results to this richer framework. Our central contribution lies in the identification of appropriate manifold-specific assumptions that allow us to secure these complexity guarantees both when using the exponential map and when using a general retraction. A substantial part of the paper is devoted to studying these assumptions---relevant beyond ARC---and providing user-friendly sufficient conditions for them. Numerical experiments are encouraging.

Citations

• Local Minima and Convergence in Low-Rank Semidefinite Programming
• Deterministic Guarantees for Burer‐Monteiro Factorizations of Smooth Semidefinite Programs

Cited by

• Complexity guarantees and polling strategies for Riemannian direct-search methods
• Iso-Riemannian Optimization on Learned Data Manifolds
• Scalable Second-order Riemannian Optimization for K-means Clustering
• A Riemannian AdaGrad-Norm Method
• On Relatively Smooth Optimization over Riemannian Manifolds
• Probability-One Optimization of Generalized Rayleigh Quotient Sum For Multi-Source Generalized Total Least-Squares
• Riemannian trust-region methods for strict saddle functions with complexity guarantees
• Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method

Related

• Inexact Adaptive Cubic Regularization Algorithms on Riemannian Manifolds and Application
• Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
• Riemannian Adaptive Regularized Newton Methods with Hölder Continuous Hessians
• Adaptive Cubic Regularization Methods with Dynamic Inexact Hessian Information and Applications to Finite-Sum Minimization
• An Adaptive Cubic Regularization quasi-Newton Method on Riemannian Manifolds