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

28/10/2015
Auteurs : Nicolas Boumal
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14349

Résumé

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.

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

Collection

application/pdf Riemannian trust regions with finite-difference Hessian approximations are globally convergent Nicolas Boumal

Média

Voir la vidéo

Métriques

111
9
1.8 Mo
 application/pdf
bitcache://29c95e07ec6bcc1a5ee44744a50f3eb75f1283d4

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14349</identifier><creators><creator><creatorName>Nicolas Boumal</creatorName></creator></creators><titles>
            <title>Riemannian trust regions with finite-difference Hessian approximations are globally convergent</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><subjects><subject>RTR-FD</subject><subject>Optimization on manifolds</subject><subject>Convergence</subject><subject>Manopt</subject></subjects><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Tue 22 May 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">29c95e07ec6bcc1a5ee44744a50f3eb75f1283d4</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24715</version>
        <descriptions>
            <description descriptionType="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.

</description>
        </descriptions>
    </resource>
.

Ditch the Hessian Hassle with Riemannian Trust Regions Nicolas Boumal, Inria & ENS Paris Geometric Science of Information, GSI 2015 Oct. 30, 2015, Paris The goal is to optimize a smooth function on a smooth manifold The Trust Region method is like Newton’s with a safeguard