Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds

SPIDER (Stochastic Path Integrated Differential EstimatoR) is an efficient gradient estimation technique developed for non-convex stochastic optimization. Although having been shown to attain nearly optimal computational complexity bounds, the SPIDERtype methods are limited to linear metric spaces....

Full description

Saved in:
Bibliographic Details
Main Authors: ZHOU, Pan, YUAN, Xiao-Tong, FENG, Jiashi
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/9004
https://ink.library.smu.edu.sg/context/sis_research/article/10007/viewcontent/2019_AIS_Riemannian.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-10007
record_format dspace
spelling sg-smu-ink.sis_research-100072024-07-25T08:16:31Z Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds ZHOU, Pan YUAN, Xiao-Tong FENG, Jiashi SPIDER (Stochastic Path Integrated Differential EstimatoR) is an efficient gradient estimation technique developed for non-convex stochastic optimization. Although having been shown to attain nearly optimal computational complexity bounds, the SPIDERtype methods are limited to linear metric spaces. In this paper, we introduce the Riemannian SPIDER (R-SPIDER) method as a novel nonlinear-metric extension of SPIDER for efficient non-convex optimization on Riemannian manifolds. We prove that for finitesum problems with n components, R-SPIDER converges to an -accuracy stationary point within O min n + √ n 2 , 1 3 stochastic gradient evaluations, which is sharper in magnitude than the prior Riemannian first-order methods. For online optimization, R-SPIDER is shown to converge with O 1 3 complexity which is, to the best of our knowledge, the first non-asymptotic result for online Riemannian optimization. Especially, for gradient dominated functions, we further develop a variant of R-SPIDER and prove its linear convergence rate. Numerical results demonstrate the computational efficiency of the proposed method 2019-04-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9004 https://ink.library.smu.edu.sg/context/sis_research/article/10007/viewcontent/2019_AIS_Riemannian.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Graphics and Human Computer Interfaces
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Graphics and Human Computer Interfaces
spellingShingle Graphics and Human Computer Interfaces
ZHOU, Pan
YUAN, Xiao-Tong
FENG, Jiashi
Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds
description SPIDER (Stochastic Path Integrated Differential EstimatoR) is an efficient gradient estimation technique developed for non-convex stochastic optimization. Although having been shown to attain nearly optimal computational complexity bounds, the SPIDERtype methods are limited to linear metric spaces. In this paper, we introduce the Riemannian SPIDER (R-SPIDER) method as a novel nonlinear-metric extension of SPIDER for efficient non-convex optimization on Riemannian manifolds. We prove that for finitesum problems with n components, R-SPIDER converges to an -accuracy stationary point within O min n + √ n 2 , 1 3 stochastic gradient evaluations, which is sharper in magnitude than the prior Riemannian first-order methods. For online optimization, R-SPIDER is shown to converge with O 1 3 complexity which is, to the best of our knowledge, the first non-asymptotic result for online Riemannian optimization. Especially, for gradient dominated functions, we further develop a variant of R-SPIDER and prove its linear convergence rate. Numerical results demonstrate the computational efficiency of the proposed method
format text
author ZHOU, Pan
YUAN, Xiao-Tong
FENG, Jiashi
author_facet ZHOU, Pan
YUAN, Xiao-Tong
FENG, Jiashi
author_sort ZHOU, Pan
title Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds
title_short Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds
title_full Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds
title_fullStr Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds
title_full_unstemmed Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds
title_sort faster first-order methods for stochastic non-convex optimization on riemannian manifolds
publisher Institutional Knowledge at Singapore Management University
publishDate 2019
url https://ink.library.smu.edu.sg/sis_research/9004
https://ink.library.smu.edu.sg/context/sis_research/article/10007/viewcontent/2019_AIS_Riemannian.pdf
_version_ 1814047689622421504