Riemannian trust regions with finite-difference hessian approximations are globally convergent

Nicolas Boumal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

The Riemannian trust-region algorithm (RTR) is designed to optimize differentiable cost functions on Riemannian manifolds. It proceeds by iteratively optimizing local models of the cost function. When these models are exact up to second order, RTR boasts a quadratic convergence rate to critical points. In practice, building such models requires computing the Riemannian Hessian, which may be challenging. A simple idea to alleviate this difficulty is to approximate the Hessian using finite differences of the gradient. Unfortunately, this is a nonlinear approximation, which breaks the known convergence results for RTR. We propose RTR-FD: a modification of RTR which retains global convergence when the Hessian is approximated using finite differences. Importantly, RTR-FD reduces gracefully to RTR if a linear approximation is used. This algorithm is available in the Manopt toolbox.

Original languageEnglish (US)
Title of host publicationGeometric Science of Information - 2nd International Conference, GSI 2015, Proceedings
EditorsFrank Nielsen, Frank Nielsen, Frank Nielsen, Frederic Barbaresco, Frederic Barbaresco, Frank Nielsen
PublisherSpringer Verlag
Pages467-475
Number of pages9
ISBN (Print)9783319250397, 9783319250397
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event2nd International Conference on Geometric Science of Information, GSI 2015 - Palaiseau, France
Duration: Oct 28 2015Oct 30 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9389
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Conference on Geometric Science of Information, GSI 2015
CountryFrance
CityPalaiseau
Period10/28/1510/30/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Convergence
  • Manopt
  • Optimization on manifolds
  • RTR-FD

Fingerprint Dive into the research topics of 'Riemannian trust regions with finite-difference hessian approximations are globally convergent'. Together they form a unique fingerprint.

  • Cite this

    Boumal, N. (2015). Riemannian trust regions with finite-difference hessian approximations are globally convergent. In F. Nielsen, F. Nielsen, F. Nielsen, F. Barbaresco, F. Barbaresco, & F. Nielsen (Eds.), Geometric Science of Information - 2nd International Conference, GSI 2015, Proceedings (pp. 467-475). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9389). Springer Verlag. https://doi.org/10.1007/978-3-319-25040-3_50