Back to Search
Start Over
Adaptive regularization with cubics on manifolds.
- Source :
-
Mathematical Programming . Jul2021, Vol. 188 Issue 1, p85-134. 50p. - Publication Year :
- 2021
-
Abstract
- Adaptive regularization with cubics (ARC) is an algorithm for unconstrained, non-convex optimization. Akin to the 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 - ε . 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 188
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 151025509
- Full Text :
- https://doi.org/10.1007/s10107-020-01505-1