Adaptive regularization with cubics on manifolds

Journal article

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 𝑂(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.

Authors: Agarwal, N; Boumal, N; Bullins, B; Cartis, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Mathematical Programming
• Volume: 188
• Issue: 2021
• Pages: 85–134
• Publication date: 2020-05-13
• Acceptance date: 2020-04-07
• DOI: 10.1007/s10107-020-01505-1
• EISSN: 1436-4646
• ISSN: 0025-5610
• Language: English
• Keywords: FFR; lipschitz regularity; Newton’s method; complexity; cubic regularization; optimization on manifolds