Riemannian Stochastic Variance-Reduced Cubic Regularized Newton Method for Submanifold Optimization

Dewei Zhang () and Sam Davanloo Tajbakhsh ()
Additional contact information
Dewei Zhang: The Ohio State University
Sam Davanloo Tajbakhsh: The Ohio State University

Journal of Optimization Theory and Applications, 2023, vol. 196, issue 1, No 14, 324-361

Abstract: Abstract We propose a stochastic variance-reduced cubic regularized Newton algorithm to optimize the finite-sum problem over a Riemannian submanifold of the Euclidean space. The proposed algorithm requires a full gradient and Hessian update at the beginning of each epoch while it performs stochastic variance-reduced updates in the iterations within each epoch. The iteration complexity of $$O(\epsilon ^{-3/2})$$ O ( ϵ - 3 / 2 ) to obtain an $$(\epsilon ,\sqrt{\epsilon })$$ ( ϵ , ϵ ) -second-order stationary point, i.e., a point with the Riemannian gradient norm upper bounded by $$\epsilon $$ ϵ and minimum eigenvalue of Riemannian Hessian lower bounded by $$-\sqrt{\epsilon }$$ - ϵ , is established when the manifold is embedded in the Euclidean space. Furthermore, the paper proposes a computationally more appealing modification of the algorithm which only requires an inexact solution of the cubic regularized Newton subproblem with the same iteration complexity. The proposed algorithm is evaluated and compared with three other Riemannian second-order methods over two numerical studies on estimating the inverse scale matrix of the multivariate t-distribution on the manifold of symmetric positive definite matrices and estimating the parameter of a linear classifier on the sphere manifold.

Keywords: Riemannian optimization; Manifold optimization; Stochastic optimization; Cubic regularization; Variance reduction (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-022-02137-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:196:y:2023:i:1:d:10.1007_s10957-022-02137-5

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-022-02137-5

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().