First-order non-convex Riemannian optimization algorithms have gained recent popularity in structured machine learning problems including principal component analysis and low-rank matrix completion. The current paper presents an efficient Riemannian Stochastic Path Integrated Differential EstimatoR (R-SPIDER) algorithm to solve the finite-sum and online Riemannian non-convex minimization problems. At the core of R-SPIDER is a recursive semi-stochastic gradient estimator that can accurately estimate Riemannian gradient under not only exponential mapping and parallel transport, but also general retraction and vector transport operations. Compared with prior Riemannian algorithms, such a recursive gradient estimation mechanism endows R-SPIDER with lower computational cost in first-order oracle complexity. Specifically, for finite-sum problems with <inline-formula><tex-math notation="LaTeX">$n$</tex-math><alternatives><mml:math><mml:mi>n</mml:mi></mml:math><inline-graphic xlink:href="zhou-ieq1-2933841.gif"/></alternatives></inline-formula> components, R-SPIDER is proved to converge to an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math><alternatives><mml:math><mml:mi>ε</mml:mi></mml:math><inline-graphic xlink:href="zhou-ieq2-2933841.gif"/></alternatives></inline-formula>-approximate stationary point within <inline-formula><tex-math notation="LaTeX">$\mathcal {O}\big (\min \big (n+\frac{\sqrt{n}}{\epsilon ^2},\frac{1}{\epsilon ^3}\big)\big)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi mathvariant="script">O</mml:mi><mml:mfenced separators="" open="(" close=")"><mml:mo movablelimits="true" form="prefix">min</mml:mo><mml:mfenced separators="" open="(" close=")"><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:msqrt><mml:mi>n</mml:mi></mml:msqrt><mml:msup><mml:mi>ε</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mfrac><mml:mo>,</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:msup><mml:mi>ε</mml:mi><mml:mn>3</mml:mn></mml:msup></mml:mfrac></mml:mfenced></mml:mfenced></mml:mrow></mml:math><inline-graphic xlink:href="zhou-ieq3-2933841.gif"/></alternatives></inline-formula> stochastic gradient evaluations, beating the best-known complexity <inline-formula><tex-math notation="LaTeX">$\mathcal {O}\big (n+\frac{1}{\epsilon ^4}\big)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi mathvariant="script">O</mml:mi><mml:mfenced separators="" open="(" close=")"><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:mn>1</mml:mn><mml:msup><mml:mi>ε</mml:mi><mml:mn>4</mml:mn></mml:msup></mml:mfrac></mml:mfenced></mml:mrow></mml:math><inline-graphic xlink:href="zhou-ieq4-2933841.gif"/></alternatives></inline-formula>; for online optimization, R-SPIDER is shown to converge with <inline-formula><tex-math notation="LaTeX">$\mathcal {O}\big (\frac{1}{\epsilon ^3}\big)$</tex-math><alternatives><mml:math><mml:mrow><mml:mi mathvariant="script">O</mml:mi><mml:mfenced open="(" close=")"><mml:mfrac><mml:mn>1</mml:mn><mml:msup><mml:mi>ε</mml:mi><mml:mn>3</mml:mn></mml:msup></mml:mfrac></mml:mfenced></mml:mrow></mml:math><inline-graphic xlink:href="zhou-ieq5-2933841.gif"/></alternatives></inline-formula> complexity which is, to the best of our knowledge, the first non-asymptotic result for online Riemannian optimization. For the special case of gradient dominated functions, we further develop a variant of R-SPIDER with improved linear rate of convergence. Extensive experimental results demonstrate the advantage of the proposed algorithms over the state-of-the-art Riemannian non-convex optimization methods.
Paper
References (58)
Scroll for more · 38 remaining