TY - GEN
T1 - Riemannian trust regions with finite-difference hessian approximations are globally convergent
AU - Boumal, Nicolas
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Convergence
KW - Manopt
KW - Optimization on manifolds
KW - RTR-FD
UR - http://www.scopus.com/inward/record.url?scp=84950342083&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84950342083&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-25040-3_50
DO - 10.1007/978-3-319-25040-3_50
M3 - Conference contribution
AN - SCOPUS:84950342083
SN - 9783319250397
SN - 9783319250397
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 467
EP - 475
BT - Geometric Science of Information - 2nd International Conference, GSI 2015, Proceedings
A2 - Nielsen, Frank
A2 - Nielsen, Frank
A2 - Nielsen, Frank
A2 - Barbaresco, Frederic
A2 - Barbaresco, Frederic
A2 - Nielsen, Frank
PB - Springer Verlag
T2 - 2nd International Conference on Geometric Science of Information, GSI 2015
Y2 - 28 October 2015 through 30 October 2015
ER -