# Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization

arXiv: https://arxiv.org/abs/2302.11076 · HTML: https://mlsanity.com/paper/2302.11076/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 71 references that are in the map.
- First posted on arXiv 22 Feb 2023.

## Builds on (most cited first, 27 of 27)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Riemannian Adaptive Optimization Methods](https://mlsanity.com/paper/1810.00760/) (2018)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [CascadePSP: Toward Class-Agnostic and Very High-Resolution Segmentation via Global and Local Refinement](https://mlsanity.com/paper/2005.02551/) (2020)
- [Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation](https://mlsanity.com/paper/1603.03236/) (2016)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Machine Learning for Neuroimaging with Scikit-Learn](https://mlsanity.com/paper/1412.3919/) (2014)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [Sub-sampled Cubic Regularization for Non-convex Optimization](https://mlsanity.com/paper/1705.05933/) (2017)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [A neural network based on SPD manifold learning for skeleton-based hand gesture recognition](https://mlsanity.com/paper/1904.12970/) (2019)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Riemannian approach to batch normalization](https://mlsanity.com/paper/1709.09603/) (2017)
- [Escaping from saddle points on Riemannian manifolds](https://mlsanity.com/paper/1906.07355/) (2019)
- [On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry](https://mlsanity.com/paper/2106.00286/) (2021)
- [Efficient approaches for escaping higher order saddle points in non-convex optimization](https://mlsanity.com/paper/1602.05908/) (2016)
- [Adaptive regularization with cubics on manifolds](https://mlsanity.com/paper/1806.00065/) (2018)
- [Escaping Saddle Points in Constrained Optimization](https://mlsanity.com/paper/1809.02162/) (2018)
- [Stochastic Recursive Variance-Reduced Cubic Regularization Methods](https://mlsanity.com/paper/1901.11518/) (2019)
- [Inexact Non-Convex Newton-Type Methods](https://mlsanity.com/paper/1802.06925/) (2018)
- [Robust Principal Component Analysis on Graphs](https://mlsanity.com/paper/1504.06151/) (2015)
- [Analysis of Krylov Subspace Solutions of Regularized Nonconvex Quadratic Problems](https://mlsanity.com/paper/1806.09222/) (2018)
- [A new, globally convergent Riemannian conjugate gradient method](https://mlsanity.com/paper/1302.0125/) (2013)
- [A Cubic Regularized Newton's Method over Riemannian Manifolds](https://mlsanity.com/paper/1805.05565/) (2018)
- [A Stochastic Trust Region Method for Non-convex Minimization](https://mlsanity.com/paper/1903.01540/) (2019)
- [Sufficient Descent Riemannian Conjugate Gradient Method](https://mlsanity.com/paper/2009.01451/) (2020)

## Abstract (arXiv)

This work is on constrained large-scale non-convex optimization where the constraint set implies a manifold structure. Solving such problems is important in a multitude of fundamental machine learning tasks. Recent advances on Riemannian optimization have enabled the convenient recovery of solutions by adapting unconstrained optimization algorithms over manifolds. However, it remains challenging to scale up and meanwhile maintain stable convergence rates and handle saddle points. We propose a new second-order Riemannian optimization algorithm, aiming at improving convergence rate and reducing computational cost. It enhances the Riemannian trust-region algorithm that explores curvature information to escape saddle points through a mixture of subsampling and cubic regularization techniques. We conduct rigorous analysis to study the convergence behavior of the proposed algorithm. We also perform extensive experiments to evaluate it based on two general machine learning tasks using multiple datasets. The proposed algorithm exhibits improved computational speed and convergence behavior compared to a large set of state-of-the-art Riemannian optimization algorithms.