SERENA: A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization
Authors: Yan Liu
Mingjie Chen
Chaojie Ji
Hao Zhang
Ruxin Wang
Venue: ICML 2025 poster (2025)
Keywords: variance reduction; recursive momentum; unified theory; Riemannian non-convex optimization
Primary area: optimization->everything_else

Abstract: Recently, the expansion of Variance Reduction (VR) to Riemannian stochastic non-convex optimization has attracted increasing interest. Inspired by recursive momentum, we first introduce Stochastic Recursive Variance Reduced Gradient (SRVRG) algorithm and further present Stochastic Recursive Gradient Estimator (SRGE) in Euclidean spaces, which unifies the prevailing variance reduction estimators. We then extend SRGE to Riemannian spaces, resulting in a unified Stochastic rEcursive vaRiance reducEd gradieNt frAmework (SERENA) for Riemannian non-convex optimization. This framework includes the proposed R-SRVRG, R-SVRRM, and R-Hybrid-SGD methods, as well as other existing Riemannian VR methods.  Furthermore, we establish a unified theoretical analysis for Riemannian non-convex optimization under retraction and vector transport. The IFO complexity of our proposed R-SRVRG and R-SVRRM to converge to $\varepsilon$-accurate solution is $\mathcal{O}\left(\min \{n^{1/2}{\varepsilon^{-2}}, \varepsilon^{-3}\}\right)$ in the finite-sum setting and ${\mathcal{O}\left( \varepsilon^{-3}\right)}$ for the online case, both of which align with the lower IFO complexity bound. Experimental results indicate that the proposed algorithms surpass other existing Riemannian optimization methods.

SERENA:
A Unified Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-Convex Optimization
Yan Liu 12
Mingjie Chen
*3
Chaojie Ji
Hao Zhang?
Ruxin Wang?
Abstract
Han & Gao, 2021b; Dodd al., 2024). In this paper,
focus on the following finite-sum or online optimization
Recently, the expansion of Variance Reduction (VR) to Riemannian stochastic non-convex op- timization has attracted increasing interest. In- spired by recursive momentum, we first intro- duce Stochastic Recursive Variance Reduced Gra- dient (SRVRG) algorithm and further present Stochastic Recursive Gradient Estimator (SRGE) in Euclidean spaces, which unifies the prevailing variance reduction estimators. We then extend SRGE to Riemannian spaces, resulting in uni- fied Stochastic rEcursive vaRiance reducEd gradi- eNt frAmework (SERENA) for Riemannian non- convex optimization. This framework includes the proposed R-SRVRG, R-SVRRM, and R-Hybrid- SGD methods, as well as other existing Rieman- nian VR methods. Furthermore. we establish a unified theoretical analysis for Riemannian non- convex optimization under retraction and vector transport. The IFO complexity of our proposed R- SRVRG and R-SVRRM to converge to e-accurate solution is O (minfrr {n 1/2g-2,0 --=3)) in the finite- sum setting and O (s-9) for the online case, both of which align with the lower IFO complexity
problems on Riemannian manifold M.
Sa (σ) (finite-sum),
min f(x) REM
Bff (z,w)) (online),
where M R is smooth non-convex function. The finite-sum represents the minimization of the average of component functions, capturing the empirical risk min- imization problem. When n is very large or even infinite, f(x) is typically modeled via the online form, which in- dexed by a random variable w. Numerous applications can be expressed as given in (1), including principal component analysis (PCA) (Sato al., 2019), low-rank matrix comple- tion (LRMC) (Boumal & Absil, 2011), Riemannian centroid (RC) computation (Yuan et al., 2016), among others.
Due to the special geometric structure of the parameter space involved such optimization problems, traditional Euclidean optimization methods may not be the optimal choice in these situations. Riemannian optimization method (Absil et al., 2008) directly advances the iterative solution along the geodesic path toward the optimum, thereby pre- serving the geometric structure of the problem, and effec- tively addressing these issues. In fact, by exploiting intrinsic properties of Riemannian manifold, the problem (1) can be regarded as an unconstrained optimization problem defined over the manifold spaces. One of the classical methods is the Riemannian steepest descent (R-SD) algorithm (Udriste, 2013; Zhang & Sra, 2016). However, the requirement for each iteration of R-SD to traverse n component functions renders the process impractical when n is extremely large. In contrast, the Riemannian stochastic gradient descent (R- SGD) (Bonnabel, 2013) method computes the stochastic gradient for each iteration of one sample (or a mini-batch samples), significantly reducing the computational cost per iteration. However, R-SGD exhibits slow convergence at- tributed to the high variance (Bottou et al., 2018).
bound. Experimental results indicate that the pro- posed algorithms surpass other existing Rieman- nian optimization methods.
1. Introduction
Riemannian optimization have received increasing interest in machine learning (Sato et al., 2019; Zhou et al., 2021;
'Fqual contribution. 'School of Statistics and Data Science, Nankai University, Tianjin, China Department of Applied Math- ematics, The Hong Kong Polytechnic University, Hong Kong, China "Shenzhen Institutes Advanced Technology, Chinese Academy of Sciences, Shenzhen. China 'Department of Mathe- matics, The University of British Columbia, Vancouver, Canada. Correspondence Hao Zhang <h.zhang10Ge MiraanttO@sat..ccmm Ruxin Wang <II. wang @ siat.ac.cn>..
Variance reduction (Gower et al., 2020) has also been ex- tended to Riemannian manifolds for improving performance. For instance, Riemannian stochastic variance reduced gra- dient (R-SVRG) (Zhang et al., 2016; Kasai et al., 2016;
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
Sato al., 2019), Riemannian stochastic recursive gradi- ent (R-SRG) (Kasai et al., 2018b; Han & Gao, 2021b), and Riemannian stochastic path integrated differential estima- tor (R-SPIDER) (Zhang et al., 2018; Zhou et al., 2021)
We also develop the R-SVRRM and R-Hybrid-SGD algorithms by extending the SVRRM and Hybrid-SGI estimators to Riemannian manifolds.
We introduce the stochastic recursive gradient estima- tor, which unifies variance reduction methods (see Ta- ble 1). We further propose the Stochastic rEcursive vaRiance rEduced gradieNt frAmework (SERENA) for Riemannian optimization by extending SRGE to Riemannian spaces. Our proposed algorithms can be regarded as special cases of this framework (see Sec- tion 5).
are generalized from the Ruclidean versions in (Johnson & Zhang, 2013; Nguyen et al., 2017: Fang et al., 2018). Variance reduction enjoys more favorable complexity in Riemannian non-convex optimization. Specifically, the In- cremental First-order Oracle (IFO) complexity of R-SVRG to achieve an e-accurate solution is O (12/38- (Han & Gao, 2021b), which improves upon O (e of R-SGD. The R-SRG and R- R-SIIDER algorithms further enhance the com- plexity to O (e-3) (Zhou et al., 2021), matching the lower bound for stochastic non-convex optimization complexity in Euclidean spaces (Arjevani et al., 2023). However, a "hybrid" algorithm that combines two existing stochastic estimators through convex combination to design a hybrid offspring--iheertingg the advantages of its underlying esti- yet to be developed in the field of Riemannian stochastic optimization.
By providing an upper bound on the variance of Rie- mannian stochastic estimator within the SERENA framework, we establish unified theoretical analysis for general non-convex functions under retraction and vector transport. Specifically. we derive convergence results and IFO complexity for several algorithms un- der both finite-sum and online settings.
The experimental results on various tasks and datasets demonstrate that our proposed R-SRVRG and R- SVRRM algorithms outperform existing methods.
In the Euclidean search space, Tran-Dinh et al. (2022) de- signed a hybrid stochastic estimator to balance the variance and bias, which can be regarded as a convex combination of the AARAH-type estimator and the SGD estimator. Based on this, they proposed the Hybrid-SGD algorithm, which can be seen extension of the stochastic recursive mo- mentum (STROM) method. Although they stated that their approach could be extended to cover SVRG-type methods, they did not provide explicit formulations. A general re- cursive momentum estimator, stochastic variance reduced recursive momentum (SVRRM) (Liao et al., 2024), was proposed by incorporating loopless-SVRG (Kovalev al., 2020) into STORM. Jiang al. (2024) also introduced similar stochastic estimator, but these approaches iterate based on the Euclidean space.
2. Preliminaries
Riemannian manifold (Absil et al., 2008; Boumal, 2023) M is manifold that is equipped with a smoothly varying inner product (s-)a on tangent space T, for every x E M. The induced norm is given by ||u]|= := / (u, u), for u e T.M. In iterative optimization algorithms on manifold M, an iteration is performed by following geodesies emanating from and tangent to u E T.MM A locally shortest path on the manifold with constant speed is called a geodesic curve 7 : [0. 1] + M, which is generalized concept of straight lines in Euclidean space.
If M is a complete manifold, the exponential mapping is de- fined for all vectors u T.M (Absil et al., 2008; Sato et al., 2019), then we can use the exponential mapping update. However, for some Riemannian manifolds, the closed form of the exponential map is not available. Alternatively, we can retract the variable x into the manifold M by defining retraction to update. Retraction Rg : TT.M - .M approxi- mates the exponential map and maps a tangent vector & to 2 (5) such that (0) The retraction curve is defined as c(t) := R. (tE) and R : .M- - TzM denotes the inverse retraction if R has smooth bijection. One advantage of using retraction is that it can reduce computational costs compared to the exponential map.
While integrating SVRG-type estimators into hybrid stochastic estimator allows us to achieve a unified form of variance reduction algorithms, there is currently no related work on Riemannian stochastic optimization. Furthermore, the theoretical analyses of various Riemannian stochastic algorithms differ significantly, and in some cases, the con- struction of a Lyapunov function is required. A natural ques- tion arises: "Is there a unified formulation for Riemannian stochastic variance reduction methods and, consequently, a simple and unified theoretical framework?" This paper provides a compelling affirmative answer. Specifically, our main contributions are summarized as follows.
and (R)[() = E.
Motivated by recursive momentum, we propose the SRVRG estimator and extend it to Riemannian mani- folds. We establish an improved complexity bound for Riemannian SRVRG (R-SRVRG), which achieves the optimal complexity.
A common approach for performing the addition of tangent vectors in different tangent spaces is to use the parallel transport PV T&M + TyM, which transports vector the geodesic curve y that connects z to y such that the induced vector fields are in parallel. However, the parallel
2

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
translation can sometimes be computationally expensive, and it does not have explicit formula for certain manifolds (Sato et al., 2019). Vector transport T TMM @ TM + TM is used as an alternative (Absil et al., 2008), it satisfies:
(5) The function f is average retraction L (--iiscchiz. That
is, there exists a constant L > 0 such that for all z,y E X, IE' [[] grad fi(x))1² grad (t) < L where py is the parallel transport operator.
1) T has an associated retraction R, i.e., for x E . and
(6) Difference between vector transport T and parallel transport P associated with the same retraction R is bounded. That is, for all y, = Re) E X and u T,M, there exists a constant @ 2 0 such that IT Pgull [|]]
4 E M,, Te(1) is a tangent vector at (c); 2) To, (5) - S. where Ç E T and x E MM 3) (yy + byj2) - (TTe + +Tee(y)), where a, b E C, 91. y2 E T, and E ... Similar to (Zhou al., 2021; Han & Gao, 2021a;b), we implicitly assume vector transport is isometric, which means that (TH u, T) = (u, v). for all u, E T2M and x E M.
The following assumptions are also standard (Sato et al., 2019; Zhou et al., 2021; Han & Gao, 2021b).
In this paper, our analysis focuses on retraction and vec- tor transport, which are more general and efficient. It is common use the incremental first-order oracle (IFO) com-
Assumption 2.3. (1) The neighbourhood X' is also to- tally normal neighbourhood of x where exponential map is a diffcomorphism.
plexity to measure the total complexity of stochastic opti- mization algorithms in achieving e-accurate solution.
(2) There exists μ, v, 6yp > 0 where for all z,y (E) E X with [|E]| & oy.e. we have ||Ell < pu((z, y) and d(x, v) < v|Ell-
(e-accurate solution and IFO complexity) The e-accurate solution of stochastic algorithm is an output for which the expected gradient norm does not exceed e. i..., E III grad fx)) []] & For problem (I), Incremental first-order oracle (IFO) takes an index i E {l....,, n) and a point 2, and returns the pair (fi(z), fa) E T2M).
Definition 2.1.
Notations. For notation simplicity, we omit the subscripts for norm and inner product. Define A = v grad ʃ [(rr]
A = grad frx)), and Åo = E [f (mo) f(x.) Denote [n] = [I,...,n). L = L + OG. Vf((z)) and grad f((z) represent stochastic gradient in Euclidean space and stochastic Riemannian gradient of f((x),, respectively. It holds that E [grad f((x)] = grad f(x) grad fL(()
n).
The IFO complexity effectively captures the overall compu- tational cost of first-order Riemannian algorithm, as the evaluations of the objective function and gradient typically dominate the per-iteration computations.
[y Eies grad fa(x)) is a mini-batch Riemannian stochastic gradient on T.MM. We use f(n) = (g)(n) to represent the existence of constants e and N, such that [(()) < clg(n)]
always holds for all 2 N. We denote O(+) to further hide poly-logarithmic factors and use f(n) to represent the existence of c1, C2, and N, such that ei [g(n)) < [f(m) & calg(n)) holds for all n 2 N.
2.1. Assumptions
@(g(n))
We present the following assumptions, which are necessary for the convergence analysis. Note that these assumptions are standard in the analysis of optimization algorithms in- volving retraction and vector transport (Kasai et al., 201 Sb; Sato et al., 2019; Han & Gao, 2021b; Zhou et al., 2021).
3. Stochastic Recursive Variance Reduced Gradient Algorithm
Assumption 2.2. (1) Iterate sequences generated by algo- rithms stay continuously in a neighbourhood X' C M around an optimal solution r.. Additionally, X' is a totally retractive neighbourhood of x, where retraction R is a diffeomorphism.
Recursive momentum, as proposed by Cutkosky & Orabona (2019), serves to achieve variance reduction and can es- sentially be regarded as a specific case of the Hybrid-SGD (Tran-Dinh et al., 2022) algorithm. Hybrid- is derived from the combination of SARAH-type estimator and SGD.
(2) Assume each loss fi and the objective function f are twice continuously differentiable. Norms of Rieman- nian gradient. That is grad f(()]] < G for all
STORM
I E X' where G G>0 0.
Uk (1 3) (TK-1 Vin, (Fx-1)) + V (Ttk)
(3) Stochastic gradient and has bounded variance. That is, for all x E X. E [grad f((z)) = grad f(x),
gradf((a) is unbiased
Hybrid SGD
2J (1 9) (1
V/ (f+11) (TR)
E [[grra f(()) grad [== <
SARAH-type estimator
(4) The objective function f is retraction L-smooth with respect to retraction R. That is, for all x, = (E) e X. there exists a constant L > 0 such that f(y) <
The first row represents the STORM estimator, while the second row corresponds to the Hybrid-SGD. When in = ju. then Hybrid-SGD reduce to STORM estimator. We propose a Riemannian extension of Hybrid-SGin AaDid called R-Hybrid-
f(x) + (grad {()),)) + [1
3

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
SGD, as outlined below,
tends SRGE to the Riemannian spaces. Notably, our frame- work also encompasses several existing Riemannian opti- mization methods, such R-SGD, R-SVRG (Zhang et al., 2016; Sato et al., 2019), and R-SRG (Kasai et al., 2018b).
(1 3)TT (Uk-1 grad Lin (1== + 3 grad fig (2x) + (1 3) grad fye (zx).
(2)
When is jk-- we get R-SRM (Han & Gao, 2021 In- spired by hybrid estimator, propose stochastic recursive variance reduced gradient (SRVRG) algorithm, which inte- grates the SVRG-type estimator with SARAH. In the s-th outer loop,
4.1. Stochastic Recursive Gradient Estimator
Motivated by hybrid stochastic estimator (Tran-Dinh et al., 2022), we introduce the stochastic recursive gradient esti- mator (SRGE) as follows,
"x - (1 (1-3)) (V (1 (Ti-)),
Uk = (1 (1-8) + Brx + (1 (1-33 B3 (wk wk-1), (6)
(3)
where ufg = VíJ. (xf) - VSja ( + V)) 8
where E [ux] Vf (1x), E [wr
wx-1] = V (xx)
represents the point which the true gradient is caleulated in the outer loop of SVRG algorithm. Note that if we choose R jR. SRVRG reduces to SVRRM (Liao et al., 2024) or SSVR-FS (Jiang et al., 2024) algorithm. The primary advan- aage of SRVRG lies in its ability to select a larger parameter 3 when ng. is an SVRG-type estimator, which facilitates a more rapid reduction in the variance of of. By extending it to Riemannian manifolds, we obtain Riemannian SRVRG (R-SRVRG). The key step of R-SRVRG is similar to (3) except the vector transport T.
f(x-11) Let us focus on the "error in tk of (6)" which
we denote as D = uk - vf(xx). It is easy to see that
E I 11 < (1 - B) II I - [1] + SE I1 V (xx)]]
+ (1 B) (TCe - 1k-1 (z)) V (+=-
The second term on the right-hand side is expected to be controlled by a sufficiently small 3. Under the bounded vari- ance assumption (Assumption 2.2 (3)), it possible to estab- lish a non-increasing upper bound for B[llu= - V (axx)]²²) For instance, if 2y is a variance reduced estimator, then B[Ilux ( - O when k - 2a (Gower et al., 2020). The third term is of order O[| xx-1ll) under the assumption of L-smooth, which can be controlled by a small step size nj. Consequently, the variance is expected to decrease. On the other hand, the bias of 2 smaller than fk when < Bias [rx] || [ex - V (Ixx (1 -1-B3 3) 11 Vf (zx-1)]l. Therefore, we can get im- proved performance by balancing bias and variance of SRGE. Indeed, if B = 0 is chosen in (6) and to repre-
of= = (1 - -)T (vh-1 - grad Jz, (x)-
+ B grad for (xf)) - -Tay' (grad fo (xz) - o9)) (4)
+ (1 - B) grad ITA (=+),
where 23 = H.-1. uo = grad (zz) and [B] = b, [ = 1 = b' Our theoretical results (Theorem 5.3 and
Corollary 5.4) show that the IFO complexity of R-SRVRG matches the lower-bound complexity (Zhou & Gu, 2019: Arjevani et al., 2023). Additionally, experimental results indicate that R-SRVRG significantly outperforms R- R-Hybrid- SGD. Setting Ia = Ts enables the derivation of the Rie- mannian SVRRM (R- (R-SVRRM) algorithm,
Table 1. Stochastic Recursive Gradient Estimator. Given 8, the second and third columns represent the types of stochastic gradi- ent estimators for and w. respectively. while the last column indicates the corresponding algorithms.
ox = (1 (1-
- grad J (2k-1) + 3 (grad fz. (=f) Tef (grad fr. (zg) - 16)) (5)
(vh-1 3)T -1-B)
Uk
Wk: Wk-1
Methods SARAH-type
3 3=0 0
SGD
SGD SVRG-type
SGD
B =
+ (1 - B) grad fr. (zt).
SVRG-type
SGD
SGD
STORM
The specific algorithms are provided in the Appendix A.
SGD
SARAH
Hybrid-SGD
B E (0.1)
SVRG
SGD
SVRRM
4. Stochastic Recursive Variance Reduced Gradient Framework for Riemannian Non-convex Optimization
SVRG
SARAH
SRVRG
sents the true gradient, then SRGE reduce to SARAH-type estimator. When B = 1, SRGE can specifically configure Uy to correspond to either SGD or SVRG-type estimator. Furthermore, if , E (0, 1). SRGE can cover several other algorithms, including Hybrid-SGD. STORM, SVRRM, and our proposed SRVRG, see Table for details.
In this section, we first introduce the Stochastic Recursive Gradient Estimator (SRGE) and then propose a Stochastic Recursive Variance Reduced Gradient framework (SER- ENA) for Riemannian non-convex optimization, which ex-
4

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
4.2. Riemannian Stochastic Recursive Variance Reduced Gradient Methods
by setting 1 and choosing SVRG-type estima- tor in (7). Furthermore,
achieve Riemannian
AbaSVRG (Han & Gao, 202 by implementing batch size adaptation in the outer loop.
By extending SRGE to Rimannian manifold M, we estab- lish unified stochastic recursive variance reduced gradi- ent framework (SERENA) for Riemannian stochastic al- gorithms as presented in Algorithm 1. In the s-th outer loop.
2 = grad (xf Tai (grad (x - -%)), (9)
where [ = b'.
of = B1- (vR-1 ( + Bug + (1 3) w
Riemannian probabilistic gradient estimator (R-PAGE) was proposed by Demidovich et al. (2024) as an exten- sion of the PAGE (Li al., 2021) in Euclidean space. where PAGE is SARAH-type algorithm.
(7)
when ui is SVRG-type estimator, up grad fz, (+1)) T (grad fz, (xr)) - vg), when ug is SG estimator, = grad I (xi). Vector transport employed to integrate gradient information in (7), as the Riemannian stochastic gradient of zf. - and zá are defined on disjoint tangent spaces. The SERENA framework includes various Rieman- nian stochastic optimization algorithms, among which are the algorithms we proposed. Several of these are listed be- low. For single-loop algorithms, such as R-Hybrid-SChl -SD and R-SRM, as well loopless algorithms like R- R-PAGE, S in Algorithm 1. And we omit the superscript for these algorithms to simplify notation, in Equations (8)
grad fis (zxx), with probability p
gradfz (xx) +Tx (Un-1 gzad (x
(10)
where [8] = b. |Z] = and "o" represents "other- wise".
5. Convergence Analysis for SERENA
We introduce unified convergence theorem in this section. All proofs can be found in the Appendix B. To simplify the notation, we denote L = 222pv²² 2 in this section.
and (10).
Algorithm 1 Stochastic rEcursive vaRiance reducEd gradi- eNt frAmework (SERENA)
Theorem 5.1. Suppose that Assumptions 2.2 and 2.3 hold, Let K Sm denote the number of total iterations, if there exist M1,M2, Wk.s Ak >> 0 such that the Rieman- nian stochastic estimator vf (7) in SERENA satisfies
Input: Step size 1/. outer loop size S, in- ner loop size m., batch size b. U, initial point To.
for 1,2,..... ..... do =² -1
||-1! M Σ
Tr [|02|1 +222002 (11)
2:
3: Sample B uniformly random from [n]] of size 6.
4: of =grad fs (zz)-
5: zi- Rag( (-nuū).
Then we have E [lgrad f (xx()](
&
9āg
+
anModoo"
+
ok
201
6: for A: k= 1....... ,m do
2Mada² where &p = 2
2 + 1).
7:
Sample Ia and Ts uniformly at random from [n]]
with I&l = JJ = V'
n
i f= max for for all ks E 1n-1],
2
8:
Calculate SERENA estimator ot-
m-1
8 m-1
9:
2b+1 R )
[S] r = Σ Yk,0. and Ả = Σ
Σ Ak
10: end for
11: T. :
Theorem 5.1 indicates that convergence results can be ob- tained when the variance of (7) has an upper bound, specif- ically when it satisfies (1)). Next, we will present conver- gence results for several specific algorithms.
12:
end for Output: xe uniformly selected at random from
13:
(xt) k [m - 1]. 8 E (S).
5.1. Convergence for R-SRVRG and R-SVRRM
R-SRM (Han & Gao, 2021a) was proposed by extend- ing STORM to Rimannian manifold.
We first prove that the variance of estimator (4) and (5) satisfy the inequality (11).
0g = -11- -1 (vk-1
grad F (2)=-))
(8)
Lemma 5.2. Suppose that Assumptions 2.2 and 2.3 hold.
+ *grrad (xx).
Then the variance of R-SRVRG estimator (4) has an up-
per bound (11) with Mi 1² Em. MM2 ((se))
Riemannian SVRG (R-SVRG) (Zhang et al., 2016; Kasai et al., 2016; Han & Gao, 2021b) captured
The = (1 - ())) and A (1 -3))((k-1) + B.
5

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
Stochastic Method
Riemannian Stochastic Method
Finite-sum
Online
Riemannian SGD
SGD
O (s (s
o (E
(Hosscini & Sra, 2020)
Riemannian SVRG
0 nn + 82
0 (s 10/33)
(Han & Gao, 2021b)
SVRG-type
Riemannian AbaSVRG
0 (1213g-2)
0 (6-10/3)
(Han & Gao, 2021b)
Riemannian SVRG
O
O 10110)
Riemannian SRG
0 (n++
(Kasai al., 2018b)
Riemannian AbaSRG
(
0 (
(Han & Gao, 2021b)
SARAH-type
Riemannian SPIDER
O (min/n fminnn+n// +,,1
0 ((=
(Zhou et al., 2021)
Riemannian PAGE
(Demidovich al., 2024)
Riemannian PAGE
0 n + 1/2
0 (E
Riemannian SRM
Ö (
STORM
(Han & Gao, 2021a)
Riemannian SRM
(minfn, E t
(
Hybrid-SGD
Riemannian Hybrid-SGD"
(min n, 8 } + 3-
0 (
SVRRM
Riemannian SVRRM'
(min n 1/2 8
0 0
SRVRG
Riemannian SRVRG"
min 1/2
0 (
Table The IFO complexity of Riemannian stochastic methods for non-convex optimization with retraction and vector transport. The results presented in this paper are highlighted in bold.
The variance of the estimator for R-SVRRM has a simi- lar upper bound with M, = 2i. +28 Lm3 Th.s = (1 3))(((--)))) and A (1 - 23.
for both R-SRVRG and R-SVRRM in finite-sum case. While under online setting, we set b O (e-2), v Then
M2 = [(bem)
b'
Consequently, we have the following convergence results for R-SRVRG and R-SVRRM.
S s
② (max (n-1/2e-2, 11)-)
(finite sum) online
+ (E-1)
Theorem 5.3. Suppose that Assumptions 2.2 and 2.3 hold.
The IFO complexity of Riemannian SRVRG or Riemannian SVRRM to oblain e-accurate solution is
Then the output Fe after running K Sm iterations of
R-SRVRG algorithm satisfies E [|grad f (1x))]
0 (min(n)126_2,--9)) (finite-sum)
(p1n+401)
( (K))
where
20. Kb
212 Lm
( (online)
P1
+
2.
Φ1
m(1-nL)
?? P8 cm3
290
Similarly, satisfies 4p2)+
the output DCc of R-
Remark 5.5. We establish an O complexity for non-convex finite-sum problems, which is not worse than O (n1/2g-2), Notably, our complexity is superior in the regime n > (0(=-)) which is significant for large-scale machine learning applications. the online setting, our result achieves the best-known complexity of O (s (Li et al., 2021; Arjevani al., 2023).
IFO
SVRRM
algorithm
E [|grad/ I (1E))
22 62k
(1 1 2K3). where 602
+
242Kb
A7.2 (1.2+.8² Em²)
+2, Φ2 = 7(1-)))
cm²²
9b'
2
23V
Corollary 5.4. Suppose that Assumptions 2.2 and 2.3
hold. Set B m- for both R-SRVRG and R-SVRRM algorithms. Denote 1) min ZL'
Remark 5.6. Corollary 5.4 indicates that if 3 and t' satisfy (online case), our proposed algorithm can achieve optimal complex- ity. This highlights the advantages of our algorithm in terms of parameter selection.
ZT: 2 for R-
JV
V max
1 E (finite-sum case)
JV. SRVRG, and min 2I' Alvmiitue for R-SVRRM.
Choose b- min {n, -2 and / 1
max e
6

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
5.2. Convergence for R-Hybrid-SGD
pg 0s
(ps7+100)1 (uen)o"
where 45 2 (12m²
=2(12² + +1)
+
20gh
Lemma 5.7. Suppose that Assumptions 2.2 and 2.3 hold. Choose th grad f (ao). [Bo] bo- then the variance of the R- R-Hybrid-SGD estimator is bounded above by inequality 1) and
Φ
1-1L
n'm²2
28
Corollary 5.14. Suppose that Assumptions 2.2 and 2.3 hold.
(11), where MM = I.2, M2 1, Ykki = (1 (1-3)2kk 3))(k))),,
Set m = v and = min { -1]
2T. 224v Choose = n,
A = - 3)2(k 1) (0g + 3.
R' = 2/3 in finite-sum setting and b = θ (5= D' θ E 1/3) under online case, then the IFO complexity of
b0
Building Lemma 5.7 and Theorem 5.1, we obtain the following convergence result for R-Hybrid-SGD.
R- SVRG to obtain s-accurate solution is
Theorem 5.8. Suppose that Assumptions 2.2 and 2.3 hold. Then the output Içç after running K iterations of Rieman-
0
( n (
(fiite-sum)
nian Hybrid-SGD algorithm satisfies E ||grad f (x()]l]
O E 10/3) (E-10/3)
(online)
vaáo Oak
+
40gn+ 200k
(2
(1
bng
+ K33)
where Pa =
Remark 5.15. The IFO complexity result of the R-SVRG that we present in Theorem 5.13 matches the optimal com- plexity of the existing SVRG-type algorithms (Han & Gao, 2021b; Li al., 2021).
2
+1) and 03 = I-nl.
+1)
n 1²1
23
Corollary 5.9. Suppose that Assumptions 2.2 and 2.3 hold, min {1. 11, /B
Set 3 K
{
21 2T. J. If we choose bo
Convergence Analysis for R-PAGE
min(n,Ki/3 under finite-sum case and bo KK/3 in
Theorem 5.16. Suppose that Assumptions 2.2 and 2.3 hold. Then the output Iς after running K iterations of
online setting. Then the IFO complexity of Riemannian Hybrid-SGD to obtuin e-accurate solution is
R-PAGE algorithm satisfies E |Ilerad (xx))(² <
zado + Pek
f So (minfn, 9) (fnite-sum)
{ ( (online)
Papt-de 200
+ +1) and do where Yo = b'p
1) 1-
17n2 2
5.3. Convergence for Other Riemannian Algorithms
Corollary 5.17. Suppose that Assumptions 2.2 and 2.3
Convergence Analysis for R-SRM
hold. Set p - b48 V/ < vb and n = min
2T. 2L
Theorem 5.10. Suppose that Assumptions 2.2 and 2.3 hold. Then the output Ieç after running K iterations of R-SRM algorithm satisfies T.
Choose b v. in the finite-sum setting and b - under online case. Then the IFO complexity of Riemannian PAGE to obtain E-accurate solution is
1872
[[lerad (s<()l1) &
(pon4404)0² 20
2K3) ,² B
where 61 f1= =
B +1)
10 C0(e-2+e-)) {olutvie3))
{ (n 10(nt VVE=V (finite-sum)
6o.
and Φ1 =
1-nL-
(online)
Corollary 5.11. Suppose that Assumptions 2.2 and 2.3 hold. Set 3 = K2233, n min { min(n, Jen(nnK''. K1/3} under finite-sum case and bu = /1/3 in online setting. Then the IFO complexity of Riemannian Hybrid-SGD to obtain e-accurate solution is
Remark 5.18. Although Demidovich et al. (2024) have pro- posed R-PAGE, they only provided convergence results under exponential map and parallel transport. To our knowl- edge, this is the first theoretical result on R-PAGE under retraction and vector transport in the non-convex setting. Furthermore, this result is consistent with the lower bounds for both finite-sum and online problems.
1 v3 }- we choose by =
2 J.
O (minntr (min(n,=')++->) (0(E-)) (E (online)
(finite-sm))
6. Experiments
Remark 5.12. Although our proof requires that vo grad fa, (ro) be batch gradient with sufficiently large batch size, the complexity can be enhanced from Ö (s-3) (Han& & Gao, 2021a) to O (s (x-3) in the online setting.
In this section. we compare the proposed R-SRVRG, R- SVRRM, and --Hybrid-SGD algorithms (dashed line) with several Riemannian algorithms (solid line) across different tasks, including R-SD, R-CG (Absil et al., 2008), R-SGD, R- SRM, R-SPIDER, R-AbaSRG, R-AbaSVRG, and R-PAGE. For our proposed algorithms and VR- VR-based methods, a fixed step size is considered. We established an inner loop size m = vni for both our methods and the VR methods, with
Convergence Analysis for R-SVRG
Theorem 5.13. Suppose that Assumptions 2.2 and 2.3 hold, Then the output xę after running K Sm itera- tions of R-SVRG algorithm satisfies E [|grad / (+²) <
7

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
14
R-90
R:60
R:50
Oplimalit (log)
R-500
R-C0
12
R-50D
R:OG
Optimality gap (log)
R.GG
R-500
R-SRM
8:5AM
R-5RM
R-SPIDER
Test MSE
R-SPIDER
R-SPIDER
R-AbsSRG
R AboBRG
R-Ab:5RG
R-AbaSVRG
R AboSvRG
-
R-Ab:SVRG
R-PAGE
R.PAGE
R.PAGE
R-SAVRG
R-SAVRG
R-SRVANG
R-SVARM
R-5VARM
R-SVRIMM
SQD
R-Hybrldd
ReHyyrrd--50
0
-15
10
20
30
40
10
15
5
10
15
20
25
30
IFOln
IFOln
IFO/n
(a) PCA on Mnist
(b) LRMC on Movielens
(c) RC on YaleB
R-9D
Optimaltty gap (log)
R-GG
R-SGD
Optimality gep (log)
R-80D
R-SRM
R-SPIDER
Test MSE
R-SAM
R-SPIDER
R-AbaSRG
21
R-SPIDER
R-AbaSRG
R-PAGE
B-AbadVRG
20
R-AbaSRG
R-AbaSVRG
R-AbaSVRO
R-PAGE
R-Htbrid-SGD
R-SRVRG
R-5VRRM
18
19
R-SAVRG
R-SVRRM
R-PAGE
-10
8- B-ityrrs--SG
R-SRVRG
R-SVRAM
R-Hybrid-SGD
10
15
25
IFO/n
IFOln
IFO/n
(d) PCA ijennl
(c) LRMC on Jester
(1) RC on Kylberg
Figure 1. The comparison of the performance of our proposed algorithm (dashed line) with other methods (solid line) across different
tasks and datasets.
a mini-batch size V' = vi for the VR methods and V' / for our methods. We selected the same parameters for R-SRVRGG and R-SVRRM. Similarly, we chose identical parameters for R- R-SRM and R-Hybrid-SGD for comparison. Except for R-PAGE, the parameters of the other algorithms are referenced from (Han & Gao, 2021b). In Figure I, the r-axis represents IFO (n), while the y-axis represents the optimality gap (which precalculated) or test mean square error (MSE). All experiments are implemented Matlab based on the code from the Man-Opt package (Boumal et al., 2014) and (Han & Gao, 2021b) on i7-1075H 2.6GHz CPU processor. The Appendix C presents more experimental results and details.
volves minimizing the reconstruction error between the projected data points and the original data over the set of orthogonal projection matrices U St(r, d), i.e., cin. n >== ||=, UU x; 112- In fact, PCA is equivalent to the following problem on the Grassmann man- ifold, minueGr(r.d) - - x! UUTx, x, Figures 1 (a) and (c) illustrate the performance of various algorithms in addressing the PCA problem on the MNIST dataset (LeCun et al., 1998) with (n, d, r) (60000, 784, 5) and ijennl dataset from LibSVM (Chang & Lin, 2011) with (n, d, (49990, 22, 5), respectively. It can be observed that Our R-SRVRG and R-SVRRM algorithms outperform alternative methods, while the R-Hybrid algorithm demonstrates superior performance compared to the R-SRM algorithm.
We consider PCA and LRMC problems on Grassmann manifold, and Riemannian centroid (RC) computation on symmetric positive definite (SPD) manifold. The experi- mental results demonstrate that proposed R-SRVRG and R-SVRRM algorithms perform superiorly across mul- tiple tasks. As an improvement over R- R-Hy, our R-SRVRG shows significantly better performance. Addi- tionally, the selection of the parameter 3 and the constant step size n for the proposed R-SRVRG, R-SVRRM, and R-Hybrid-SGD algorithms demonstrate robustness across various scenarios (see Appendix C).
LRMC on Grassmann Manifold Given matrix A Rdxa with missing entries, the rank-r matrix comple- tion problem is to minu, [[Pa(A) (uV)') with U E Rdxr, V E Rexn, where Ω is the set of in- dices for which we know the entries in X, and the op- erator Pn acts as Pa (Xxz) = X, if (i,j) E Ω and Pn (X.;) = 0 otherwise. Since the factorization into U and V not unique and depends only on the column space of U, the problem is defined on the Grassmann manifold Gr(r, Partitioning ai,..., , an, is equivalent n. Ei= I/Po, (a.) Pa, (Uv,))l
PCA on Grassmann Manifold The PCA problem in-
to minueGrir.d) 1 where Pa, is the sampling operator for the i-th column.
hhttps://githui com wtt. jow.andanna///a//mmmmmmom.a AbaVR
8

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
Given U, V; in this admits closed form solution. Figures 1 (b) and (e) show that our proposed algorithms R-SRVRG and R-SVRRM are slightly better than that of all other algo- rithms on datasets Movielens- 1M (Harper & Konstan, 2015) and lester (Goldberg et al., 2001).
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
RC on SPD Manifold Given n points {XI..... x E + Let || || denote the Frobenius norm, and log(-) represent the principal matrix logarithm. Then the Rieman- nian centroid is derived from the solution to the problem minces Ei= llog CC-1/XXc--1/211
References
Absil, P.-A., Mahony, R., and Sepulchre, R. Optimization algorithms on matrix manifolds. Princeton University Press, 2008.
We com- pare algorithms on Extended Yale B dataset (Wright al., 2008) and Kylberg dataset (Kylberg, 2011). 1). From Figure (c) and (f), we observe that R-SRVRG and R-SVRRM still perform better compared to the other algorithms.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, D. J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199 (1):165 214, 2023.
7. Conclusion
Bonnabel, S. Stochastic gradient descent on riemannian manifolds. IEEE Transactions Automatic Control, 58 09:22117-222,200
This paper first combines SVRG-type estimator with SARAH-type one to propose the SRVRG estimator and extend it to Riemannian manifolds. Subsequently, we in- troduce a unified variance reduced estimator, SRGE, and based on this, propose unified framework for Riemannian stochastic variance reduction algorithms, named SERENA. Additionally, we provide unified theoretical analysis for Riemannian stochastic variance reduction algorithms under retraction and vector transport, which is more general and ef- ficient than using the exponential map and parallel transport. Theoretical results indicate that the IFO complexity of our proposed R-SRRGG R-SVRRM, and R-Hybrid-SGi match the lower bound of complexity for non-convex stochastic optimization. Experimental results also demonstrate the superiority of our proposed algorithms. However, cur- rent framework is limited to smooth problems. Therefore, future work will involve extending this framework and the- oretical analysis to address non-smooth optimization chal- lenges on Riemannian manifolds. Furthermore, Riemannian second-order methods have garnered increasing attention, such as the RNGD (Hu et al., 2024), R-SQN-VR (Kasai al., 201 and R-SVRC (Zhang& & Davanloo Tajbakhsh, 2023) algorithms. We will explore the integration of this framework with second-order information to enhance the convergence rate.
Bottou, L., Curtis, F. E., and Nocedal, J. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Boumal, N. An introduction to optimization on smooth manifolds. Cambridge University Press, 2023.
Boumal, N. and Absil, P.-a. Rurme: A riemannian trust- region method for low-rank matrix completion. In Ad- vances in Neural Information Processing Systems, vol- ume 24. Curran Associates, Inc., 2011.
Boumal, N., Mishra, B., Absil, P.-A., and Sepulchre, R.
Manopt, a matlab toolbox for optimization on manifolds. Journal of Machine Learning Research, 15(1):1455-144 1459, 2014.
Chang, C.-C. and Lin, C.-J. Libsvm: library for sup- port vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):1-27, 2011.
Cutkosky, A. and Orabona. F. Momentum-based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, volume 32, 2019.
Demidovich, Y., Malinovsky, G., and Richtárik, P. Stream- lining in the riemannian realm: efficient riemannian opti- mization with loopless variance reduction. arXiv preprint SCVv:2203306677 2024.
Acknowledgments
This paper was supported in part by the National Key R&D Program of China (2022YFA1008000, the National Natural Science Foundation of China (12471308, 12101334, 62472415), the Guangdong Provin- cial Science and Technology Plan (2022B1515130000 2025A15150101033, the Excellent Young Scholars of Shen- zhen (RCYX2023121 1090247060), and the General Re- search Fund of Research Grants Council (15304721).
Dodd, D., Sharnock, I.., and Nemeth, C. Leammin-rrate-rre stochastic optimization over riemannian manifolds. In International Conference on Machine Learning. 2024.
Fang, C., Li, J., Lin, Z., and Zhang, T. Spider: near- optimization via stochastic path- integrated differential estimator. In Advances in Neural Information Processing Systems, volume 31, 2018
optimal

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
Goldberg, K., Roeder, T., Gupta, D., and Perkins, C. Eigen- taste: A constant time collaborative filtering algorithm. Information Retrieval, 4: 4:133-151, 2001.
Kylberg, G. Kylberg texture dataset 1.0. Technical Re- port 35, Centre for Image Analysis, 2011.
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, Gradient- based learning applied document recognition. Proceed- ings of the IEEE, 86(1 1):2288 22224, 1998.
Gower, R. M., Schmidt, M., Bach, F., and Richtárik, P. Variance-reduced methods for machine learning. Pro- ceedings of the IEEE, 108(1 (9111)::168-19855 2020.
Li, Z., Bao, H., Zhang, X., and Richtarik, P. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, volume 139, pp. 0286-6295) 2021.
Han, A. and Gao, Riemannian stochastic recursive mo- mentum method for non-convex optimization. In Inter-
national Joint Conference on Artificial Intelligence, pp. 2505-2511, 8 2021a.
Liao, S., Liu, Y., Han, C., and Guo, T. Momentum-based variance-reduced stochastic bregman proximal gradient methods for nonconvex nonsmooth optimization. Expert Systems with Applications, pp. 125960, 2024.
Han, A. and Gao. J. Improved variance reduction methods for riemannian non-convex optimization. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 44 (11):7610-7623, 2021b.
Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. SARAH: novel method for machine learning problems using stochastic recursive gradient. In International Con- ference on Machine Learning, volume 70, pp. 2613-2621, 2017.
Harper, F. M. and Konstan, J. A. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems, 1-4):1-19, 2015.
Hosseini, R. and Sra, S. An alternative for gaussian mixture models: batch and stochastic riemannian opti- mization. Muthematical Programming, 181(1):187-223, 2020.
Pennec, X., Fillard, P., and Ayache, N. A riemannian frame- work for tensor computing. International Journal of Computer Vision, 66:41-66, 2006.
Hu, J., Ao. R., So, A. M.-C., Yang, M., and Wen, Z. Rie- mannian natural gradient methods. SIAM Journal on Scientific Computing, (11)):2204A2311 2024.
Sato, H., Kasai, H., and Mishra, B. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. SIAM Journal on Optimization, 29(2): 1444-1472, 2019.
Jingg W. Yang. S., Yang, W., and Zhang, L. Efficient sign-based optimization: Accelerating convergence via variance reduction. arXiv preprint arXiv:2406.00489, 2024.
Tran-Dinh, Q., Pham, N. H., Phan, D. T., and Nguyen, L. M. A hybrid stochastic optimization framework for compos- ite nonconvex optimization. Mathematical Programming. 19 191(2):0055-177 2022. 2022.
Johnson, R. and Zhang, T. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, 2013.
Udriste, C.
Convex functions and optimization methods on Riemannian manifolds, volume 297. Springer Science & Business Media, 2013.
Kasai, H., Sato, H., and Mishra, B. Riemannian stochastic variance reduced gradient on grassmann manifold. arXiv preprint 1xXvv:6605007366 2016.
Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., and Ma, Y. Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelli- gence, 31(2):1102277, 2008
Kasai, H., Sato, H., and Mishra, B. Riemannian stochastic quasi-newton algorithm with variance reduction and its convergence analysis. In International Conference on Artificial Intelligence and Statistics, volume 84, pp. 269- 278, 20.
Yuan, X., Huang, W., Absil, P.-A., and Gallivan, K. A. Ari- mannian limited memory bígs algorithm for computing the matrix geometric mean. Procedia Computer Science, 80:2147-2157, 2016.
Kasai, H., Sato, H., and Mishra, B. Riemannian stochastic recursive gradient algorithm. In International Conference on Machine Learning, volume 80, pp. 2516-2524, 2018b.
Zhang, D. and Davanloo Tajbakhsh. S. Riemannian stochas- tic variance-reduced cubic regularized newton method for submanifold optimization. Journal of Optimization Theory and Applications, 196(1):324-361, 2023.
Kovalev, D., Horváth, S., and Richtárik, P. Don't jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. Inter- national Conference on Algorithmic Learning Theory, volume 117, pp. 451-467, 2020.
Zhang, H. and Sra, S. First-order methods for geodesically convex optimization. In Conference on Learning Theory, volume 49, pp. 1617-1638, 2016.
10

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
Zhang, H., J. Reddi, S., and Sra, S. Riemannian svrg: Fast stochastic optimization riemannian manifolds. In Ad- vances in Neural Information Processing Systems, vol- ume 29, 2016.
Zhang, J. Zhang, H., and Sra, S. R-spider: A fast rie- mannian stochastic optimization algorithm with curva- ture independent rate. arXiv preprint arXiv:1811.041 1.4494,, 2018.
Zhou, D. and Gu, Q. Lower bounds for smooth nonconvex finite-sum optimization. In International Conference Machine Learning, volume 97, pp. 7574-7583, 2019.
Zhou, P., Yuan, X.-T., Yan, S., and Feng. J. Faster first- order methods for stochastic non-convex optimization on riemannian manifolds. IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(2):459-477 2021.

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
A. Specific Algorithms
Here, we list the algorithms proposed in this paper, including R-SRVRG, R-SVRRM, and R-Hybrid-SGD.
Algorithm Riemannian SRVRG
Input: Step size outer loop size S, inner loop size m. batch size b, b' initial point To.
for = ........ do
2: z6 - -1
3: Sample B uniformly random from [n] of size and calculate vi grad sis (z())-
4:
zi (-rr)))
5: for 1: = .,..., m do
6: Sample 1 and Ts independently from [xx]-
7: Calculate ut = (1 grad fi, (xf) + $ (grad fn. (xi) - -Tag (grad (x) -6)) + (1
B)T " (=f-1-gre - fI, (xf-1))
8:
# Rez(-
9:
end for
10:
T,- 2m
11:
end for
12: Output: zę uniformly selected at random from {af] k E [m - 1], s E [S].
Algorithm 3 Riemannian SVRRM
Input: Step size 7). outer loop size inner loop size m, batch size b. 8' initial point To.
1: for = 1,2, S do
2: # = --
3: Sample B uniformly at random from [n]] of size and calculate vg = grad fe (ait).
4: "i = Rog. (-10g)-
5: for k= 1...., do
6: Sample I randomly from [m]-
(1 B) grad fza (xt) + B (grad fI, (2t) Tag (grad fi. (x)) v8)) + (1
7: Calculate uk
B)T= (ug-1 grad fr. (a%_1)
8:
#1+1 = (-v(-)
9: end for
10: F. mm
11:
end for
12: Output: de uniformly selected at random from {af} k E [m 1], E [S].
Algorithm 4 Riemannian Hybrid-SGD
Input: Step size 17, mini-batch size by. the initial point B.,3.
1: Sample B uniformly random from [r]] of size by-
2: to grad fs (zo).
3: = R., (-noo.
4: for k= 1,=,..., K do
5: Sample ig and ju independently from [n].
6: Calculate Us 3 grad fú, (xx) + (1 - 3) grad fún (2x) + (1 - B)TTr (uk-1 - grad Sio (xx-1) 1))
Tk+1 R.g (-11))
8: end for
9: Output: de uniformly selected at random from {ax K k=
12

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
B. Missing Proofs
B.1. Useful Lemma
Lemma B.1. (Retraction Lipschitzess with vector transport (Lemma A.2 in (Han & Gao, 2021b))). Suppose that the norm of gradient is bounded by G (Assumption 2.2 (2)). f is average retraction L Lipiscchitzz (Assumption 2.2 (5)), and the difference between parallel transport Py and vector transport Ty under same retraction is bounded (Assumption 2.2 (6)).
Then for all x, y (g) X,
E Ilggrad fi(x) - Ty grad f(())l < LIEII,
where ī. (I4 + BG).
Lemma B.2. (Lemma I in (Han & Gao, 2021b)) Suppose Assumptions 2.2 and 2.3 hold and consider the estimator " = grad JB (xf) - T (grad (15)) v8), where |B") = V/ and vg = -grad [a(ar) [B] = b. We have
B [10g grad I (=1))
k < 4 1131200 2
+ 1 lbcnt b Σ E [|]]
o²
1=0
where L = Li + AG.
B.2. The proof in Section 5
B.2.1. THE PROOF OF THEOREM 5.1
Proof. In the k-th inner loop of s-th outer loop, by retraction L-smooth in Assumption 2.2 (4), we have
f ( < f (zf)) - (grad/ f (af) net) + 2²2
2 ||
f (xft) n|| 1 (ug grad (x:)) vt) + 1²2 L, ||/l1
2
(af) 17 ( 7
||=,|| 2
|
" llt grad f (=t))l
2
1 mL
(x+) 1
||o]]| 2
2 llu grad f (=1))²
where the second incquality is due to the fact 2 (a, b) < |a|| + ||6|| for any vector a, b E Rdd Taking expectation of the above inequality and summing over is 0, ....... m obtain
m
m "
E (= < E (x+)
1
[
+
E
llu
grad f (x+))²²]
2
2
k=o
< E (x+)
17
11 nT
E [1e]21]]
MM
B E [[I0|P]]
+
M22
1
2102
2
2
2
k=0
==0
k=0
[ 17
1- nル
E [1]]1P]]
Mi
Tg
n/22
X1.2
2
2
k=
k=0
k=0
m-1
where the second inequality follows from (11) and the last inequality is due to the definition of rī =
Σ
0 and the
K=
fact Σ 1k.0 The for any i E [k], le [m 1]. Telescoping this inequality over from 1 to S and noting that
x I. = zn
we have
E I (m
< E [f (2o) -17
1 - L
9 m-1
E |
M
8 m-
Σ
E
|
2
+
nM2
Σ Σ
S m-1
Aoo
2
2
2
==1 O=
1=1
k==
==1
k=0
13

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
By definition o and A, the following inequality is satisfied:
E [f (=m)
E Ef (āa)) 1 11 700--PMMi Mi
Σ
9
E
[1u81]]]
MM2Ao²
2
2
Denote = (Znt_yeMMi") and Âo EE (žo)] fxx)). Therefore.
2
5 m-1 1
MMZdo²
(12)
2Φ
Considering that zg is chosen from {at) [((.ess]) uniformly at random, we obtain
SmE [lgrad f (x())1²
E Iggrad of (=:)
k= 0
m
5 m
E
|Iggrdd f (xx) - vfll"
2
E
||
k=
8
s
2
2
2
n [|];|1]]]
+ M2dk0²
+ 2
E
[|
k=
==
m-1
m--
< 2Min
Σ
E
||
+2M2A +2
Σ
E
|
k=0
5 m-1
= =2 =M +
Σ
Σ
E
[|021]]
+ +2M2Ao²
km0
pnM2do²
2M22o²
2Φ
where the second inequality utilizes the (11), by definition of I' and Å, the third inequality holds. The last equality is due to o (Min'f + 1). and the last inequality follows (12). Dividing both sides by K Sm gives
Φāo + dK
snM22oo 2M2Ão²
E I (xx))²
<
20K
K
This completes the proof.
B.2.2. THE PROOF OF RIEMANNIAN SRVRG AND RIEMANNIAN SVRRM METHODS The proof of Lemma 5.2
Proof. Let us first denote 82 grad fz, (zt) grad f(xz), of of grad ff (x+). Note that ut grad fū (x.) T-E (grad Sr. (x:) v8). I, and Ts are independent, |I] [ = V. Obviously, Ez, (5g - T 86-1l = 0 and 46
Ey [ For Riemannian SRVRG (4), we have
| 1l
(1 grad fr, (xf)) + Bug + (1 - --BTT (Vi_1 - grad fz (of_1)) - grad f (af)
|(1 B A (1 - 3)T xi 02_1 56_1 + -30 + 30r
||||||= | |ليه || + - /3>1| 0 - -TzL - _ /| + 3
(1
+2(1 3)² (T d 5%
T )2-1) + 2(1 8)8 (T - 02) + +2 3)8 1)38(z
TTi 8 12 0%
14

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
Taking the expectation w.r.t. I& conditioned Jk. we obtain
Bi, || = 99- || 19] + (1-27) BI,
| xx
86-11 19 + 3 [[1011]]
+ +2(11 3)8 (Tri - 02)
Taking the expectation w.r.t. Ts and noting that LB, IIx [x]lH = B. [LET [-Ja]]], E.y [o]] = -0, we have
Th) ||ARI|] = (1- 8)² || مع ||] + (1 - By ||62-T25 T 62- 12] + S. [10021]]
Then taking the expectation over all the randomness and using the Lemma B.2, we obtain
B | (1 (1- -3)
T
A 1 |1
+1 -)
1 To 02 2
R-1
0² )2)
g2
E || 2
+ [(bca)
Noting that
_ |]] = grad fIz (x+) - T grad fIe (0% - (grad f (xf) Tzt grad f(a 119
27
By using the fact B[[|
|[-]||a] < ||||=|| 11,) we have
| |
< (1 3)2E || 11
+ (1 (12
grad fia (x T grad fu (ok- 1|]]
6'
2 1-1
o²
+ 3
Σ
[I021]]] 27
+ 1 (bee))
b
1=0
By applying the Lemma B. have
E ||:II <1
--- ||
(1 - B)
i²,,² |1 [1]]] +
knL k-1
E
||0u|| ?]
(Dcn) 02)
b
Recursively applying this inequality gives
i.212 2 k-1
()) [|02||]] + B2kLi k-1
||-1||]
<
(1
- 3)
(1 - 3) 2 1E [|b=11]]]
V ==
{bbn) 0²
o²
+ +11 - B)
+,32 Σ (1 (3) 2( 1-)
1) 1 (b<)) b
L3 Σ (1-
[102|1]]]
8mm Lij 2
Σ (1 33) 2k IE [102111]
1
1=0
d²
+ ((1 3) 2k + B) 1 [(cc)] b
For Riemannian SVRRM, by the difinition of og in (5), we have
E [lož grad ff (x
= E =[100 B) grad fz, (xt) + Bug + (1 - 3TT o2-n (uă grad fr, (xf_1)) - grad of (a [²]
15

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
(1 -)FE | (vă_1 grad ((2 11) |
+ E ||01 - 39) (grad Izn (112) grad I (xft) - T (grad Jz, -
-gadd (()) + 8 (ug grad I (=))))
< (1 - -)))))//1 |1:8_1 grad/ f (o% ||]] + 2 [luβ grad f (#2)1²)
+ + - B) grad fr. (xf) grad f (2t) T (grad fr. (x grad fx (
< < - -1=)))-| [106_1 grad f (= + +2(1 - 3((- fz. (2t) Tel grad fr. (zx-1) |
+ + |luf - g f (=2
2(1 1)2
< (1 - f) |1
grad / grad
(xf_1) 11]
R
||og_111
+ 2
[
grad / (xrt)1
< (1 ") [1 grad f (z [1]] 2(1 - i)2
b' E |100
11]]
2k.3²
2n
0² E [|]:|]]] + 28 (Den) b
+
where the second equality holds due the unbiasedness of grad fi, (3x),, grad fú, (x and Blug] grad (=ff) The first inequality is due to the fact |la + b1|² < 2||a|| + 2|16|| the second inequality follows B|[l [[æ]]|]] < |[[|=]]]] By using the Lemma 1. we have the third inequality, the last is due to the Lemma B.2.
Recursively applying this inequality, we have
n b
2,3²m² Lip
E
|
Σ (1-33 1-333222 3)2(k-i-1) 'B |
+
Σ (1 3) 1 [|I2|1]]
t=
o²
((1 B)2a + +23) 1 [ben]
b
The proof of Theorem 5.3 and Corollary 5.4
Proof. Given the similarities in the theoretical analysis of R-SRVRG and R-SVRRM, we will use R-SRVRG as example to present the proof. Note that Mi Therefore, we have
8 Lm3
M2 1(bem)
Thi = (1 ()2(kki-1), and A -1- + B.
Σ (1
2)2((11
1
7k,0
1 1- (1 $3
k=0
m-1
ΣΣ
A
1 K = AA
==1 k=
According to Theorem 5.1, we have
E Igrad f (xx)
<
Φi +
(1pn + 402) 02
(1
8 + K3) =3).
Φ1K K
20 Kh
where 1
2x² 812 em=
+ 2, 01 = 17
1-nL
Setting 8 = =m-1 . min (
96
236
21 2L, 2L.m//1400p
then we can derive that 2 < 1
< Φ1 < 7.
2
In finite-sum case, if we choose b = min {n, -2 2 and / f max
Vn Ej. we observe that
1
> e². Consequently,
we have E [llgrad / (x=)
<
_04_ n
+
18 KD-
mn +
m)
K
<
2000 nk
+ 360
bb
To obtain e-accurate solution, we require
16

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
K- = θ (VBB2 which is derived from the fact E [[lgrad _ (are)]l
v3 E |Igrad (xx))l Therefore, the total IFO
<
complexity is given by S (b + 3mb') = v8
min on,o² o -2
+
36'
F O (min (nt1/2-=,0-3))
Under online setting, denote -2 2 and
e, then we have |Igrad f (xx)))
20 nk
+
360" KB
< To obtain
E-accurate solution, we require K - θ
(>bbE>)
Consequently, the total IFO complexity is given by S (b + 3mb)) =
vB V
b+
35' 8 ) 0 (E- The proof of Riemannian SVRRM is similar to R-SRVRG, thus we omitted it.
B.2.3. THE PROOF OF RIEMANNIAN HYBRID-SGD
The proof of Lemma 5.7
Proof. Let first denote As uk -gaadd (Ira), ōR,i = grad Si, (1Tx)) -grad (1xx) and ok, -gaad Jix (1x) - -grad (uxk).
E A [P] E
| grad Súg (xx) + (1 B) grad Sia (xxx) + (1 -B)TEE (UX-1 - -gad Sie (Irx- 1)) grad f (wx))
|||a -B)TT AK + (1 3) (des - -Tei ( ) + 30x.. 1|]
E
||a [12] + ||(-= - 3) (ou.s The 8u- 8k-13) ) + 38s.s |1]
(1 3)
(1 ME
||-~1 11²
+ (1 3))2
||aus T 8k 8 1,
2
+ BZB [1b0 ||]
|| grad fox (IX-1) grad fox (Txx) 11]
< (1 3)
||--1|| + (1 3)2E
+ |
< (1 3) || + (1 3) ||18-111 =1
+ 88002
where the first incquality is due to the fact Ei|l= [[x]||]]
[[|[=||]] and 8k.j T 7 grad fyx (Tx)
The grad fi (==-1) - grad ((xx) - The grad f (I)- while the last inequality is derived from Lemma B.2. There- fore, by applying this inequality recursively, we have
E [|A < (1 - 2)) 1) || |2]
+ 2 1=0
(1
8) 2)
E [10:11]]
2] + B2
(1 - 1)2 02
1=
Note that uo = grad fiso (Ir) and |Bol = bo. then we obtain
k-1
(1 - () E ||:0|] + 82 k-1
(1 B) 2(k 2( 0² +++ (1 (1 2(k-1) 1 1
[|A
< i 22
b0
i=0
+ +B² + (1 - 3)2(k 2(1-11) 1) L lonennoo
< 1 1
(1 (1- BB [10011]] 2
bo
where the first inequality is due to Blllvo - grad ((0)) = B[]l grad (2o) - grad f(x0))] = [(o 86. the last
inequality follows that 32 Σ (1 3) 2) 1-
8²
< 2 < B, the proof completed.
The proof of Theorem 5.8 and Corollary 5.9
Proof. By Lemma 5.7, we know that M1 M2 1, Th.i = (1- - 13))2 and d (1 - -3) 1) 100ent + B. Therefore,
bo
m-1 1 r = Σ
1 -
7k.0 <
<
1- 1- - 3)2
3
k=0
17

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
K-
1 [bo<n)
1 [bo
+ +B3
+ KB = A.
5 (2 B)
6n
k=
According to Theorem 5.1, we have
Ps
(1pm) + 403) 0² 1 ([(05))) + KB kg))
B [lerad / (xx))l²
<
Φ3K K
203
bo,3
where 03 = =/ (1 L 2B
and 4p3 = 2 2 (2L22²² + 1).
Set B K-2/3 and 11 = min {
vl 22 22
then < 43 < 3,
Φ3 2. Therefore,
240.
20o
201 (boen)
E Iggrad f (xx)1?] < nk
K2/3
K1/3hb
Note that v) = θ (K-1/3), if we set bo = min(n, K1/$} under finite-sum case, then we have E ||erad / (xx)))
24
40
To obtain e-accurate solution, we require K θ (e-"), thus the total IFO complexity given by
nk k2/3
bo
3К
O mni + 9). In online setting, set bo K2/3 then the total IFO complexity is given by
bo
+ 3К
O (s-
B.2.4. THE PROOF OF OTHER RIEMANNIAN STOCHASTIC ALGORITIIMS
The proof for R-SRM Algorithm. The upper bound of variance for R-SRM as Lemma B.3. The Lemma B.3 states that MI = 2i², M2 2, 7h.i = (1 - 3)2(k-1), and A (1 3) 2))((=1) Lin
by + 233 Based on this, we obtain the convergence result 5.10 for R-SRM (The proof is similar to Theorem 5.8, thus we omitted it).
Lemma B.3. Suppose that Assumptions 2.2 and 2.3 hold. Choose up = grad f8, (2o). |Bol = bo. then the estimator of
R-SRM (8) satisfies
2800² (1 (1-3) 3)) 1 (bo on BE ||0|1
E ||al1]]
2n Σ (1
3)
2))((--0))))
60
1=0
Proof. Define 5R- grad Sop (Ix) grad (Ixx).
E |luk
V (Ix))1
27 1|]
E
V Via (0k) + +11 B)TT (Uk-1 (xk-1) V (xsx)
||a - -33)Ta (tk-1 vf(xx-1)) (1 - 3) Tree 8x-1 - -6x) + +B0 1']
E
(1 3)
||uk11 V (I )|{] E [1 - B)
Taa 6k-1 0z) + 188 ||]
Trih 8k-1 62 521"] + +282 [|
(1 "E
11k1 V (Ix- )|
+ B)
< (1 EE
||uk- f (xx )
2 8)
| Vfii, (2x-1)
Vfi. (Ex)) |13
+ 2 ||
(1 3)
[|u--1 v (x==-))1² )|3
+ + -3),,"
||0011| |
where the third equality is due to T 5k-1 5y = and E [5x] The first inequality follows that ||a +
b112 < 2||a||2 + 2|16112 the second follows from T -k-1
V i (Ix-1) - V /i (Ise) THe Vs(==-1) - Vʃ (zx) and
E||a - |[=]|||] < []] By applying Lemma B.2, the last inequality holds true. Recursively applying this inequality and noting that un = grad Ss. (æo). [Bol bo, we can reach the final result.
18

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
The proof of R-SVRG (Theorem 5.13 and Corollary 5.14)
Lemma B.4. (Lemma in (Han & Gao, 2021b)) Suppose Assumptions 2.2 and 2.3 hold and consider the estimator of RSVRG. We have
k <
E [|o]|]]] + pbent o² b LL
|
y
Proof. By Lemma B.4, Mi = 6, 7h,s = k, M2 = _s0em) A 1. Thus we have f m², = Sm, P55 = z m
2
11 C
+ 11) 03
According to Theorem 5.1, we obtain
28
(fSn + 405) 1 [bben)
IIgrad f (x<))
E
+
Ø5
2035/
Consider the parameter setting m v and r7 min 21. 2Lp f. then we have E [Igrad f (=<))l
<
20A. 1
+
1872
In
b
finite-sum setting. if we choose b n and b' n2233, then we require that K - (E
to obtain E-accurate solution.
Consequently, the total IFO complexity given by S(b + 2mb') = Sn 2K o 2/8
Under online case, choosing
b = + (E- and b' = θ (s (=-1/)), then we require K = + 3) Therefore, the total IFO complexity to obtain E-accurate solution is S (b (b+ 2mb') e (b 2mb') 0 (5 10/3).
The proof of R-PAGE (Theorem 5.16 and Corollary 5.17)
We first present a necessary lemma.
Lemma B.5, Suppose Assumptions 2.2 and 2.3 hold. If the estimator ug defined as (10), then we have
2
k-1
p)
k
'E
||:s| 2]
+ 1 [ben) b
o²
0
Setting b = n. in finite-sum settings, we have
1.2 k-1
E
A
Σ
(1-
p)*
Kー
'
||: !1]
1=0
Proof. Denote A2 = - grad (IL)) By the definition of e in (10), we have
E
|
pE
Σ
grad fs (Ix) grad (xx)
+ (1 p) E
Th Uk- 1
+
1
Σ
grad Ss (IN)) - T grad Sa (1I--1) - grad / (xx)
1
iEB
+ 1 (bcn) paz
= =11- E
Thk Uk-1 +
grad fi (xx) T grad fi (RA-1)) grad f (2x)
EEB'
= (1 - p) E
A
+ B
grad fa (xx) - - grad fo (ax-1)) + The grad I (xx-1) - grad I (xx))
#k-1
2
+ 1 [bbn]] b
19

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
po?
= (1 B) B ||4x~11] =|]]
+ 1 [ben)
b
+ - p) E
grad Si (IrA) - -Tet grad Si (17--1) + Toa grad I (IX-1) grad (Ia))
1/
iEB'
< (1 p) IE || 11]
(1 p)
E
grad fi (Irs) - Th grad fi (1o- 1|| + 1 [(ben) b
po²
V
(1 p) 1
po²
< (1 E
| 1
|| + 1 [bbn)]
b'
where the second equality is due to Assumption 2.2 (3), the first inequality holds since EI[l= [|x]][]] < ||||=||]] By using the Lemma 1. the last inequality holds. Recursively applying this inequality gives
k-1
2 k-1
E
|| 12]
<
(1 p) ">"EEE
E
||0:1|
2
[ben)
Σ (1 11-p) 11-p) -
1. 2 k-1
a²
Σ (1 - p)
k E ||0:|| 2]
+ 1 [ben)
A
b
1=0
In finite-sum settings, if we choose b = nt, then we have
L' k-1
E
|
2
Σ
(1-p) p)* "B [|u:1]]]
1=0
The proof of Theorem 5.16 and Corollary 5.17
Proof. By Lemma B.5, we have Mi
1.2 M2
(8cm)) b
Tk,i = =11-))~-
Ax 1. Thus
Tk,0s
A K Sm
Ak.
k=0
According to Theorem 5.1, it is easy to obtain
Po +
Pon + 406
1 1nbenj02
E Igaad f (xx))1
<
deo
200
b
L'n"" 2 + 1) and de (I-nL- p'p
Eznn') 2/p )20))) Set p
V D' & vb and n & min I V 1 b4bs
}.} then 22//447 21.
where P6
2 < Po < E/4 < de
< 4-
In finite-sum setting, if we set b = n, then we have E [ggad ff (x=))l²
<
200.
To obtain s-accurate solution, it is necessary
nn
to satisfy the condition 203. nk
& e2, which implies that the number of iterations K must be least
200
Consequently. the 7g
total IFO complexity is b + K (pb (1 p) b') = bb
2n
n2
Under online setting, we obtain E Igraad ff (zs))1?
<
200 n
18g2 To obtain s-accurate solution, require
20 AiK & 3/4
b
and
280² < 2 b
Thus K = 0
Vbek 6ez
and b = O(E
Consequently, the total IFO complexity is b+ K (pb + (1 - b)
2.
25'6K' b + 647
0
+ 36668
0 + )
20

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
C. Experiment Details and Additional Experiment Results
C.1. Geometry of Specific Riemannian Manifolds
C. 1.1.1. GRASSMANN MANIFOLD
The Grassmann manifold Gr(r, d) has the structure of a Riemannian quotient manifold (Absil et al., 2008), i.., Gr(r, d) St(r, dr)O(r), where St(r, d) is the Stiefel manifold, which the set of matrices of size d x with orthonormal columns. An element of the Grassmann manifold is represented by d X orthogonal matrix U with orthonormal columns, satisfying the condition U I. Any element is considered equivalent U if it can be expressed as UR for any R O(r). We use the polar-based retraction Rx. which is commonly used for Riemannian optimization (Zhou et al., 2021; Han & Gao, 2021b; Boumal et al., 2014). Denote pf represents the extraction of polar factors from polar decomposition. Then Rx(V (V) pf(X= + V), the inverse retraction is Rx (Y) Y (x
X. The associated vector transport the orthogonal projection to the horizontal space, i.c., Tx (V) = (I- V. Although the vector transport method not isometric, it is feasible create isometric vector transport using singular value decomposition (SVD), albeit at a high computational cost. Nevertheless, Han & Gao (2021b) demonstrated that non-isometric vector transport performed effectively.
8-50
R-50
R-80
Gradient norm (log)
Gradient (log)
R-00
B-500
Optimality gap (tog)
R-CG
R-600
R-5AM
R-SPIDER
0
R-SPIDER
-5
R.AboSRG
AROSVVG
8 R-AbeRRG
8 RbbbSR
B-AbaSVRG
R.PAGE
B.PAGE
R-SAVRG
-10
R-SRVRG
R-SRVRG
-1
R-SVARM
R-Hbbid-SGD
R-SVRAM
5..
R-SVRRM
R-HybrisSSG
10
20
30
40
50
10
20
30
40
50
60
10
20
30
40
50
IFO/n
IFO/n
IFO/n
(a) PCA on Mnist
(b) PCA on ijennl
(c) PCA on Synthetic
R-SD
Gradient norm (log)
0
R-900
Test MSE (log)
-1
R-D0
R-SGD
R-3RM
Optimality gap (log)
R.CG
R-SRM
R-SGD
R-SPIDER
R-SPIDER
R-AbsSRG
R.PAGE
R-AbaSVRG
-2
R-PAGE
R-AbsSVRO
R-AbiGRG
-5
R-AbaSRG
R-AbSVVRG
R-SAVRR
R:SVARM
R-SVRAM
R-SAVRG
-10
RHHybris-SGD
R-Hybrid-800
R-SVRRM
-10
R-Hybrid-SGD
10
20
50
10
20
5
15
25
30
IFO/n
IFO/n
IFO/n
(d) PCA on Synthetic
(e) LRMC on Synthetic
(f) RC on Synthetic
Figure 2. Convergence results for the PCA problem terms of gradient norm on Mnist and ijennl, along with additional results on synthetic dataset.
1.2. SYMMETRIC POSITIVE DEFINITE (SPD) MANIFOLD
The symmetric positive definite (SPD) manifold Sd defined as the set of d x d symmetric positive definite matrices, represented as S (X dd X X, X 0). By endowing S with the
Riemannian metric + at X E sd_, the SPD
(AIRM) (Pennec et al., 2006) defined as (U, V) ir txxx=trxx-xxx (X-) for U, E S manifold + forms a Riemannian manifold. We adopt the retraction Rx (V) = X + V + i V----vl from (Kasai et al., 2018b; Han & Gao, 2021b), along with the isometric vector transport. Note that the isometric vector transport can be derived by parallelization for S.4. That is, For any X, Y E S the expression T 5 = By B& holds, where Bx E dddd represents the orthonormal basis on S and B TxSd_ - defined such that B (Bx, U)x
21

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
C.2. Parameter Settings and Additional Experiment Results
For the probability p of PAGE in all experiments, we select from 20 40 b b' vn. For R- R-Hybrid-SGD, we set [ 0.01 across all experiments.
the mini-batch size is to be
80
160
320
C.2.1. PCA ON GRASSMANN MANIFOLD
For all double-loop algorithms, we set 0.03 on MNIST and 1 0.9 on ijennl'. The step sizes for R-SRM and R-Hybrid-SGD are set to 0.05 and 0.3 on datasets MNIST and ijcnnl, respectively. In the experiments conducted on Mnist and ijenn1, our proposed algorithm selected parameters 3 = 0.1 and 3 = 0.5, respectively. In fact, the algorithm exhibits insensitivity to the choice of 3. Figure (a) and (b) illustrate the comparison of gradient norm descent when the algorithms solve the PCA problem on the MNIST and ijennl datasets, respectively. The results demonstrate that proposed R-SRVRG and R-SVRRM perform more effectively. Figure 2 (c) and (d) present the comparison of the performance on the synthetic dataset with (n, d, r) = (10', 200, 5) in terms of optimality gap and gradient norm, where the synthetic data is sourced from (Han & Gao, 2021b). Similar observations can be made.
C.2.2. LRMC ON GRASSMANN MANIFOLD
We set 7)- = 7 x 10 on Moviclens- 1 and r) = 9 x 10 6 on Jester' for both R-SRVRG and R-SVRRM. The step sizes for R-SRM and R-Hybrid-SGii are set to 10 - and 5 10-6, respectively, on Movielens 1M with 6040 users (d) and 3706 movies (n) (Harper & Konstan, 2015) and Jester (Goldberg al.. 2001) with 24983 users and 100 jokes. In the experiments conducted the Movielens- 1M and Jester datasets, our proposed algorithm utilized parameter values of 3 0.5 and 0.1, respectively. Figure 2 (e) demonstrates the performance of solving the LRMC problem on synthetic data with r)) = (20000, 100, 5) (sourced from (Han & Gao, 2021b)). It can be observed that our R-SRVRG and R-SVRRM exhibit superior performance.
C.2.3. RC ON SPD MANIFOLD
For the experiments conducted on the Extended Yale B dataset, we set 1) = 0.03 for all VR methods and 7) = 0.04 for both R-SRM and R-Hybrid-SGD, For Kylberg" dataset, we r - 0.04 for R-AbaSRG and R-AbaSVRG methods, and choose 7 0.05 for the other methods. We set 8 0.5 for our proposed algorithms in the experiments conducted both Yale B and Kylberg datasets. In Figure 2 (f), compare the performance of solving the RC problem on synthetic data with (n, d, cn) (5000, 5)7 Our proposed R-SRVRG and R-SVRRM continue to demonstrate excellent performance.
C.3. Sensitivity of parameter 8
We demonstrate the robustness of parameter 3 in the proposed R-SRVRG, R-SVRRM. and R- R-Hybrid-SGD algorithms,, respectively. Figure 3 illustrates the effect of parameter /3 on the R-SRVRG algorithm across different tasks and datasets, indicating that the algorithm is robust to the selection of 3. In Figures 4 and 5, we present the effects of parameter / on both the R-SVRRM algorithm and the R-Hybrid-SGl algorithm, indicating that our proposed algorithms exhibit insensitivity to the selection of (.
Phttp:/ http:::/yynnn..eccc Lecun wttpt////w/////////e//eee/aaaata
'https: hhergsas//etpnaaassse.eeelllleee
22

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
14
R.SRVRG(B.1)
R-SRYR
--SAVRRIO..
Oplimality (log)
2
R-
R-SRVRO/22
R-SRVRO/8.5
Optimality gap (log)
R-GAVRGIO
R-SRVRGI0.3
R
R-SRVRG
R-SAVRG/0.4
R-
Test MSE
R-SAVRRG0-5
R
R-SRVRG
R-SAVRGO
7)
R-SAVRGA-
-
R-SRVRO
R-SRVROIO
R-SAVRRIO
2-
0
-15
10
20
30
40
10
15
5
10
15
20
25
30
IFOln
IFO/n
(a) PCA on Mnist
(b) LRMC on Movielens
(c) RC on YaleB
R-SVRRMA..
R-SRVRGIO.1)
R-BRVRG(O.1)
Optimaltyy gap (log)
R-SVARWAS.
R R-SRVRG
R-SRVRG(033
Optimality gep (log)
B-SRVRG(O.3)
R-SRVRG/D.2)
R-SVARWWB.. 60)
R-3RVRG(0.4)
R-SRYRG/D
R-SVARMAA... B)
R-5VARMAS.75 751
R-SVARMM,
R-SVARMAS.T 7)
Test MSE
21
20
R-SAVAG(O.5)
a-SRVAG(O.8)
R-SRVRO(03)
R-SRVRG0077
-6
R-SRVRG(a.7)
R R-SRVRG
R-SRVROJLS)
R-SRVROjB.8)
R-SVARMA/..
19
R-SRVRO(03)
R R-SRVRGI0.9
-10
IFOln
IFOln
IFO/n
(d) PCA ijennl
(c) LRMC on Jester
(1) RC on Kylberg
Figure Robustness of parameter 3 the R-SRVRG algorithm.
R-SVRAMOO.1
R-SVARMO
Optimality gap (log)
8-SVRRMND.2
8-SVRRMAD3)
-R-SVRRMO
Optimality gap (log)
R-SVARMOO
2-SVARMO.J
10
4-SVARMO.4
R.SVRAMOO
R-SVARMAB.)
D-SVAAMO...
R-SVRRMIO
Test
8
R-SVARMB..
-5
R-SVARMND.
R-SVARIMI..)
R-SVARMN 8)
R-SVARMMIL
R-SVARMND 9)
R-SVARMMIO. 5)
1-SVRRMO.J)
10
-10
IFO/n
IFO/n
IFO/n
(a) PCA Mnist
(b) LRMC on Movielens
(c) RC YaleB
24
R-SVRRMIO.S)
R-SVRRMO.1
R- R-SVARMAN
Optimality (log)
R-SVRRMIO.50
R-SVRRMIO.I
23
R.SVRRM0.2
A-SVRRMO0.)
Optimality gap (Bog)
R- R-SVRRMAOO. 3)
R R-SVARIAIO 2
-5
R-SVRAMIO 75)
R-SVARMIDB.. 65)
R-SVRAMIO.T
Test MSE
R.SVRAMO
R-SVRAMO
R-SVARIAIO 5)
R R-SVARIAIC 6)
R R-SVRRIADD.
R-SVRAMIO.1
R.SVRAM0.7)
-5
R-SVARIAJO
R-SVARMIO.BR
R.SAARIAI.
10
R-SVRRMID..)
R-SVRRIAIO
-15
-15
10
40
10
20
30
40
50
60
5
15
26
30
IFOln
IFOIn
IFO/
(d) PCA on ijcnnl
(c) LRMC on Jester
(f) RC on Kylberg
Figure 4, Robustness of parameter / in the R-SVRRM algorithm.
23

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
14
S0000)
1)
R-yybrd-Sdbo..1
Optimality (log)
S-ppo 3)
2)
Optimaile sap dooe
Rdhbrid-DD0.3
R-1ypnts-G000 4)
R-Myorld-5000-11
RHhbrid-SD044
S0Di
Test MSE
R-berid
R-10)rid-S0000.11
R-tybrd SQD0077
R-1yens--G2200
R-Habid
8 B- 90D
R-Hyeris-SG00..0
B-tybmt-SCDo
0
10
20
30
40
10
15
5
10
15
20
25
30
InO
IFO/n
(a) PCA on Mnist
(b) LRMC on Movielens
(c) RC on YaleB
R-Hybrd-5000 50
R SG00000
R-Hyeris 900
Oplimaltty gap (log)
SG
R- 31
20
Oplimality gep (log)
R-
24hybro-5GD004 4)
Test MSE (log)
4)
R-Hyeris-S00j.4)
R+tybrid S0D
Rotybrid 5
21
Hyprii--5D00
Hyprid-SSD00
R-HDeris-90Dj..8)
S-Hy)rid-S00/0.5)
Rotybrdd SGD/0.)
20
500/0.7
0.
R-Hteris-S00(a.7)
R4hybrid S0D008)
22
R4tybrid SGD/0.9
19
50000
18
IFOln
IFOln
IFO/n
(d) PCA ijennl
(c) LRMC on Jester
(1) RC on Kylberg
Figure Robustness parameter the R-Hybrid-SOO algorithm.
R-SRVRGHle
R RRVRRGGGe-55
R R-5RVRG
Optimality gap (log)
R-SRVRG(Be-2
R- R-SRVRG(B--
Optimality gap (log)
R R-SRVRG(5e-2)
R-SRVRO/6e
R SRVRRO(00
R (-SRVRO(0e-2)
R-SRVRG/T--3)
10
---SRVRG(T=-5
88 --SRVRG(7--2
Test MSE
--SRVRRG(G--)
B- R-SRVRG(B--2
R-SRVRG
8
SRVRG(D--6)
SRVRRGBe--2
-5
6
-10
IFOIn
IFOln
IFO/n
(a) PCA Mnist
(b) LRMC on Movielens
(c) RC YaleB
(1-3)
Optimality (log)
23
BRVROISe-6
Optimalitty lity gap (log)
SRVRRGG
-5
R-
R.SAVRO/Te (1
Test MSE
R-SRVRO(8--2)
R-S
-5.
-10
-15
-15
10
20
40
10
20
30
40
50
60
5
10
15
20
25
30
IFOln
IFOIn
IFO/n
(d) PCA on ijennl
(e) LRMC on Jester
(f) RC on Kylberg
Figure 6. Robustness of step sizes in the R-Hybrid-SGD algorithm.
C.4. Sensitivity of step sizes
Figures 6, 7, and 8 illustrate the effects of different constant step sizes on our proposed algorithms. As observed in Figures and 7, the selection of step size relatively insensitive for the R-SRVRG and R-SVRRM algorithms. Figure shows a
24

---

SERENA: A Unified Framework for Riemannian Non-Convex Optimization
somewhat greater impact of step size the R-Hybrid-SGD algorithm, which also indicates that improved algorithm, R-SRVRG, enhances the robustness of the method.
R-SVRRM 2
44
8-SVRRMM4-2
Optimality gap (log)
Re
12
Optimality gap (log)
8-SVRRM5-22
R-SVERu((e-3
R-SVERM(Ge-5)
--SVRRMMG-2)
10
-R-VRAM77-2
R-SVARMBBe
Test MSE
R-SVARMBB--)
R-SVRAMBe-2
R-SVRRM(De-2)
8
R-SVRRMDeSS)
R-SVRAM0e221
-10
-15
10
5
15
25
30
IFOln
IFOln
IFO/n
(a) PCA on Mnist
(b) LRMC on Movielens
(c) RC on YaleB
R-SVRRMJ
R-SVRRM(44-6
R-SVRRM
Optimality (log)
R-SVRRM(Se-1)
R-SVERM
Optimality gap (log)
R-SWRRMIGe-0
R-SVRMM
R-5VRRM(7C-1)
22
R-SVRRMITe-0
R-SVRRMK76-)
R-GVRRM(2e-1)
R-SVRRM((D-1)
Test MSE
21
R-SVRRM(AA-))
R-SVRRMBB--)
-5"
A.SVRAM36-21
R-SVRRMNB--2
-15
10
20
30
40
10
20
30
40
50
60
5
10
15
20
25
30
IFOln
IFO/n
IFO/
(d) PCA on ijennl
(c) LRMC on Jester
(f) RC on Kylberg
Figure 7.
Robustness of step sizes in the R- R-Hybrid-SGD algorithm.
R-llyero-SDDje--3
R-HlyrissGGD(ee-
Optimality gap (log)
R-yeerd-800 S0D/5e
R-Hyyrls
Optimality gep (log)
R-Heerd-8000 80D
R S0D0
20
10
B-HyaridsSSDDye
0
R-Hybro-SGDjfe
R-lybrd--500 SGD
Test MSE
8
R-llyarie-GGD00-0
R-lyyrrss-GDD5--
R-tybnts-GDije-
R-tybrtt-SGDDpe-)
0
2
IFO/n
IFOIn
IFO/n
(a) PCA Mnist
(b) LRMC on Movielens
(c) RC YaleB
R-Htybrd-SaD/ee-1
#-Hyybids-SG 40
Optimality (log)
0
R-Hybrid 66D
23
Optimallit gap (log)
R-Hybrid-800 S0D/7e11
PHiybrio-S0Djee
Test MSE (log)
R-Hyarid-30D
R-Hytrrds-3DD
A-Hybrid-3DDTe2
R-lybrid 50D
21
B-
R-
R-tyynid-SGDjaa-3)
R-Hybrid-33D(0e-2
-5
10
20
30
40
10
20
30
40
50
60
5
10
15
20
25
30
IFOIn
IFO/n
(d) PCA on ijennl
(e) LRMC on Jester
(f) RC on Kylberg
Figure 8. Robustness of step sizes in the R- R-Hybrid-SGD algorithm.
25


Reviews:
[{"review_id": "K7ySJ8YVNm", "reviewer": "Reviewer_JLi5", "summary": "This paper proposes a generalization of stochastic recursive variance reduced gradient framework (SERENA) that unifies various gradient-like objects that serve as the first order information for Riemannian optimization. Based on the appropriate formulation of the gradient estimator proposed in this framework, the existing variance reduced algorithms on Riemannian optimization and the new Riemannian adaptations of existing Euclidean variance reduced algorithms are subsumed under the same framework which established a unified theoretical analysis on convergence. The convergence results of the newly proposed Riemannian adaptations, namely the Riemannian stochastic recursive variance reduced gradient algorithm (R-SRVRG), the Riemannian stochastic variance reduced momentum algorithm (R-SVRRM) and a Riemannian hybrid stochastic gradient descent algorithm (R-Hybird-SGD) are established, among which the R-SRVRG achieves the optimal incremental first-order oracle(IFO) complexity. The numerical experiments demonstrate superior performances of the proposed R-SRVRG and R-SVRRM in terms of IFO-complexity, i.e., the convergence with fewer stochastic gradient computations.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging feedback and valuable comments and suggestions. We will respond to each point below.\n\n1. Methods And Evaluation Criteria:\n\nThank you for your insightful comments regarding the evaluation criteria and complexity analysis in our paper. As you mentioned, R-SRVRG makes $4b'$ calls to IFO computation and 1 call to Riemannian update in the inner iteration, while R-SVRRM makes $3b'$ calls to IFO computation and 1 call to Riemannian update in the inner iteration. In fact, for the R-SRVRG and R-SVRRM algorithms, the value of parameter $b'$ is closely related to $m$ (because Corollary 5.4 indicates that setting $\\sqrt{\\beta/b'} = \\varepsilon$ or $\\sqrt{\\beta/b'} = n^{-1/2}$ can ensure the optimal complexity of R-SRVRG and R-SVRRM, and $\\beta = m^{-1}$). When $m=n$ or $m=\\varepsilon^{-2}$, $b'$ can be set to 1, the ratio $(b+ 4mb')/(m+1)= \\Theta((n+\\varepsilon^{-2})/m)$ between IFO calls and update calls can be a small constant $\\mathcal{O}(1)$, our algorithm requires $S(1+m) = \\Theta(\\varepsilon^{-3})$ or $\\Theta(n^{-1/2}\\varepsilon^{-2})$ Riemannian updates. If we set $m = b'$, only $\\Theta(\\varepsilon^{-2})$ Riemannian updates are needed, but the ratio will be $\\Theta(\\varepsilon^{-1})$ or $\\Theta(n^{1/2})$. \n\nFrom an experimental perspective, we recorded the time taken for 1 IFO call, 1 Riemannian update, and 1 vector transport across different problems and datasets. The average time for a single IFO call is 0.634s, which is 3.65 times the average time for a Riemannian update and 4.7 times the average time for a vector transport. This indicates that a significant portion of the algorithm's runtime is consumed by IFO calls, especially when a larger batch size is selected in the inner loop. Thus we can choose a smaller batch size $b'$.\n\nFurthermore, we also performed a comparison of the performance of various algorithms with the x-axis representing runtime. The results show that our proposed algorithm remains comparable to the best-performing algorithms. see https://anonymous.4open.science/r/SERENA-RiemanOptimization/.\n\n2. Experimental Designs Or Analyses:\n\nIn the experimental design, we selected the RC problem on the SPD manifold. As you mentioned, this problem is indeed a convex optimization problem. We chose this problem because both papers  (Han \\& Gao, 2021a, 2021, Han \\& Gao, 2021b, Kasai et al., 2018) tested their algorithms on this issue; thus, to facilitate comparisons between algorithms, we opted for the same problem.\n\n3. Other Comments Or Suggestions:\n\n(1) Thank you very much for your suggestion. We will reduce the discussion on manifolds and exponential mappings in subsequent versions.\n\n(2) We apologize for any confusion caused. Due to space limitations, we provided only a simplified definition of IFO complexity in the submission. We will include a complete version and further explanations in subsequent papers.  The definition \"For problem (1), an Incremental first-order oracle (IFO) takes an index $i \\in \\\\{1,\\ldots,n\\\\}$ and a point $x$, and returns the pair $\\left(f_i(x), \\operatorname{grad} f_i(x) \\in \\mathrm{T}_x \\mathcal{M}\\right)$. \" and the explanations \"The IFO complexity effectively captures the overall computational cost of a first-order Riemannian algorithm, as the evaluations of the objective function and gradient typically dominate the per-iteration computations.\"\n\n3. We will modify $[n]$ to $\\\\{1,\\ldots,n\\\\}$.\n\n4. The first line of the formula above Equation (2) denotes the stochastic estimator for the Stochastic Recursive Momentum (STORM) algorithm, while the second line corresponds to the stochastic estimator for the Hybrid-SGD algorithm. The Hybrid-SGD estimator can be interpreted as a convex combination of the SARAH-type estimator and the stochastic gradient estimator. When $i_k = j_k$, the Hybrid-SGD reduces to STORM. And we propose a Riemannian extension of Hybrid-SGD, called R-Hybrid-SGD, as outlined in Equation (2). We will modify the formula above Equation 2 as follows:\n\n$v_k = \\overbrace { (1 - \\beta )( {v_{k - 1} - \\nabla {f_{{i_k}}}({x_{k - 1}})} ) + \\nabla {f_{{i_k}}}({x_k}) }^{STORM} \\approx   \\overbrace{(1 - \\beta )(\\underbrace {  {v_{k - 1} + \\nabla {f_{{i_k}}}({x_{k }}) - \\nabla {f_{{i_k}}}({x_{k - 1}})}}_{SARAH-type \\\\;estimator}) + \\beta \\nabla f\\_{j_k} (x_k)}^{Hybrid-SGD}.$\n\n5. Thank you for the reminder, we will modify it.", "claims_and_evidence": "The claims made in this submission are accurately stated and supported by convincing evidence and discussions.", "methods_and_evaluation_criteria": "The proposed evaluation criteria, the use of the optimality gap/mean squared error along with IFO complexity as evaluation criteria is appropriate, as one of the compelling contributions of this paper is a unified theoretical analysis on IFO complexity. However, I would also expect the complexity discussion on the Riemannian update, retraction or exponential map. \n\nWhile an analysis on IFO complexity alone is usually sufficient for a Euclidean stochastic first order algorithm with neglectable vector update, the update computation in a Riemannian setting is almost always a nontrivial primitive.  It is important to include the impact of the Riemannian update in the complexity analysis, especially when the ratios between the IFO call and update call are different. For example, R-SRVRG (Algorithm 2) makes $4b'$ calls to IFO computation and $1$ call to Riemannian update in the inner iteration, while R-SVRRM (Algorithm 3) makes $3b'$ calls to IFO computation and $1$ call to Riemannian update in the inner iteration. With that being said, a throughout complexity discussion that examines the profile of IFO computation and Riemannian update derails from the main focus and scope of this paper, as the profile significantly varies depending on the optimization problem, the Riemannian manifold and the choice of retraction map. I would prefer a simple discussion that reports the ratios between the IFO calls and update calls in different algorithms. It is recommended to also include the elapsed time (on average) for each call as a more practical reference.", "theoretical_claims": "Yes, I checked and confirmed the correctness of the proofs in appendix B. In particular, I read the proof of Theorem 5.3 and Corollary 5.4 in details.", "experimental_designs_or_analyses": "The experimental designs and analyses are solid to me. Other than the missing discussion on the impact of the Riemannian update, which was mentioned in the ``Methods And Evaluation Criteria'' section, I am a bit puzzled with the experiment on the Riemannian centroid. To the best of my knowledge, the Riemannian centroid (RC) problem on the SPD manifold with the affine-invariant metric is a convex optimization problem, as the SPD manifold with the affine-invariant metric is totally geodesically convex. How does that fit in this paper, which focuses on Riemannian non-convex optimization? While the convex optimization is certainly a more feasible setup than a non-convex one, does any experimental result pick out the implications brought by the convex condition with the RC?", "relation_to_broader_scientific_literature": "This paper propose a Riemannian framework (SERENA) for stochastic gradient estimators that adapts the existing Riemannian variance reduced algorithms including the Riemannian SRM, Riemannian SVRG and Riemannian PAGE. The R-SVRRM and R-SRVRG derived from SERENA not only outperforms (in terms of IFO complexity) the above-mentioned variance reduced algorithms, but also outperforms other existing Riemannian variance reduced algorithms that are not in SERENA. In addition, SERENA provides a unified theoretical analysis on IFO complexity for the algorithms it subsumes, which provides a different angle of interpretations for the existing algorithms.", "essential_references_not_discussed": "I am not aware of any other missing/not-cited related work that is essential to this paper.", "other_strengths_and_weaknesses": "This submission is well written and organized. Readers can expect a fluent reading experience with it. The idea of proposing Riemannian adaptation of framework that unifies existing algorithms and derives new algorithms is always significant. As there are too many details in algorithmic designs vanish in the Euclidean setting, an appropriate adaptation that leads to one or more better Riemannian algorithms sheds some lights on the interpretations of the vanished algorithmic designs, which could have more implications beyond the scope of stochastic optimization.", "other_comments_or_suggestions": "Here is a list of minor things and suggestions.\n\n1. As the paper mostly (if not always) works with the retraction, the discussion on manifolds and exponential mapping in the Preliminaries section 2 is too restrictive and unnecessary. It is not a good idea to mention a unique existence of geodesic globally:\n\t``If there exists a unique geodesic between any two points on $\\mathcal{M},\\cdots$''\n\tThis is quite rare in practice (although the SPD manifold is one of those examples), so mentioning it might give the incorrect impression that the paper is limited to such cases.\n1. The IFO complexity is not clearly defined. For those readers that are less familiar with the stochastic optimization like me, it could be difficult to relate IFO complexity with the counts of the call to stochastic gradient computation via Definition 2.1, especially when Def 2.1 says IFO complexity but it only defines what IFO is. The similar issue occurs to me in the Experiment section 6, which states that\n``In Figure 1, the $x$-axis represents IFO(n)''.\nMeanwhile, the figures says IFO/n and Def 2.1 says IFO takes an index and a point to return a gradient.\n1. The $[n]$ in Def 2.1 is not defined before.\n1. In section 3, check equation (2) and the equation above of a SARAH-type estimator. The $i_k$ and $j_k$ are not consistent with each other. Equation (2) should be Riemannian adaptation of that SARAH-type estimator, I tend to think this is a typo that will cause confusions, or correct me if there are reasons for that.\n1. Appendix B.2.' title, ``The proof in Section 4'', I believe it should be Section 5.", "questions_for_authors": "I do not have a question for the authors that would likely change my evaluation of the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SjORcTAetU", "reviewer": "Reviewer_oiW7", "summary": "This paper proposes a unified stochastic recursive variance reduced gradient framework for Riemannian non-convex optimization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your thorough review and useful comments. Please find our responses below.\n\n1. Methods And Evaluation Criteria: \n\nThank you for your valuable feedback regarding the applicability of our proposed methods. First, please allow me to explain why the RNGD method was not compared previously.\n\n(1) The RNGD algorithm utilizes an approximation of the Riemannian Hessian, making it a second-order method, while this paper primarily focuses on Riemannian stochastic variance reduction methods, which are the first-order methods. \n\n(2) This paper provide a unified framework and theoretical analysis, which cannot encompass the RNGD algorithm.\n\nWe compared our proposed R-SRVGR and R-SVRRM with RNGD on the LRMC and PCA problems, respectively. The results indicate that the performance of our algorithms is comparable to that of RNGD. In particular, when the x-axis represents running time, ours perform better in most experiments. See details in https://anonymous.4open.science/r/SERENA-RieOptimization\n\nWe will replace the last sentence in the conclusion and add references. \"Furthermore, Riemannian second-order methods have garnered increasing attention,  such as the RNGD[1], R-SQN-VR[2], and R-SVRC[3] algorithms. We will explore the integration of this framework with second-order information to enhance the convergence rate.\".\n\n2. Other Strengths And Weaknesses:\n\nAlthough the optimal complexity of the Riemannian VR method has been established in previous work, R-SRVRG and R-SVRRM show better performance. Theoretically, we first provide a unified analytical framework, as the analyses of different algorithms previously varied significantly. Additionally, there are new theoretical insights; for instance,  when the other parameter settings adhere to those specified in the Corollary 5.4 in finite-sum case, our algorithms can guarantee optimal complexity as long as $mb'= \\min\\\\{n,\\varepsilon^{-2}\\\\}$ is satisfied and R-AbaSRG needs $ b' = m = n^{1/2}$. This indicates that our algorithms exhibits superiority in parameter selection, i.e., robustness and a broader range.\n\n3. Other Comments Or Suggestions:\n\n(1) We will correct the typo. \n\n(2) Assumption 2.2(1) follows papers (Zhou et al., 2021, Han & Gao, 2021b, Kasai et al., 2018), and it is difficult to relax. In Assumption 2.2(2), the boundedness of the Riemannian Hessian is unnecessary, and we will remove it. More details for assumptions, see 2 in our rebuttal to Reviewer PqwF.\n\n(3) We will change $\\tilde x$ to $\\tilde x_{s-1}$ and provide the necessary explanations as follows \" $\\tilde x_{s-1}$ represents the point at which the true gradient is calculated in the outer loop of SVRG algorithm\". For Equation (3) and (7), we will add superscript $s$ and indicate that it refers to the $s$-th outer loop. In second line after Equation (7), it is \"SG\".\n\n(4) We will add the caption for Table 1 as follows: Given $\\beta$, the second and third columns represent the types of stochastic gradient estimators for $u$ and $w$, respectively, while the last column indicates the corresponding algorithms.\n\n(5) In Algorithm 1, $|\\mathcal{I}_k| = |\\mathcal{J}_k| = b'$, we will add \" of size $b'$ \" at the end of line 7. After Algorithm 1, we will add the following note \"For single-loop algorithms, such as R-Hybrid-SGD and R-SRM, as well as loopless algorithms like R-PAGE, $S=1$ in Algorithm 1. And we omit the superscript for these algorithms to simplify notation, as in Equations (8) and (10).\".\n\n(6) R-SRM, R-SVRG, and R-PAGE can be classified as special cases of Algorithm 1. These three algorithms are highlighted because they each exemplify distinct types: R-SRM has a single-loop structure with its stochastic estimate represented as a convex combination of SARAH-type and SG stochastic estimates. In contrast, R-SVRG employs a double-loop structure, while R-PAGE can be regarded as a loopless SARAH-type algorithm. We present these specific forms of the stochastic estimates to facilitate theoretical analysis. \n\n(7) For our R-SRVRG and R-SVRRM, $S = \\frac{K}{m} = \\Theta (\\frac{1}{\\sqrt {mb'} {\\varepsilon ^2}})$. The optimal complexity can be guaranteed as long as $mb'= \\min\\\\{n,\\varepsilon^{-2}\\\\}$ is satisfied in finite sum case, thus $S = \\Theta (\\max \\\\{  n^{-1/2} {\\varepsilon ^{-2},\\frac{1}{\\varepsilon }} \\\\})$. Similarly, in the online case, $mb'= \\varepsilon^{-2}$, $S = \\Theta ({\\varepsilon ^{ - 1}})$. For R-SVRG, $S = \\Theta(\\varepsilon^{-2}n^{-1/3})$ in finite-sum case and $S= \\Theta(\\varepsilon^{-4/3})$.\nWe will include the choice of $S$ in corollary.\n\n[1] Hu,J. et al. Riemannian natural gradient methods. SIAM J. Sci. Comput., 2024.\n\n[2] Kasai, H. et al. Riemannian stochastic quasi-newton algorithm with variance reduction and its convergence analysis. In AISTATS, 2018.\n\n[3] Zhang, D. and Davanloo Tajbakhsh, S. Riemannian stochastic variance-reduced cubic regularized newton method for submanifold optimization. J. Optim. Theory Appl., 2023.", "claims_and_evidence": "The algorithm and its analysis are presented with derivations and proofs, but clarification on assumptions and the construction of the variance reduced gradient needed.", "methods_and_evaluation_criteria": "The applicability of the proposed methods is fine. But it lacks a comparison with SOTA Riemannian natural gradient methods, see, \n\nHu, J., Ao, R., So, A.M.C., Yang, M. and Wen, Z., 2024. Riemannian natural gradient methods. SIAM Journal on Scientific Computing, 46(1), pp.A204-A231.", "theoretical_claims": "The proofs seem correct.", "experimental_designs_or_analyses": "As commented earlier, it lacks a comparsion with Riemannian natural gradient methods.", "relation_to_broader_scientific_literature": "The paper proposes a unified variance-reduced gradient estimator on manifolds by consolidating existing methods from both Euclidean and Riemannian optimization literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The optimal complexity for Riemannian variance-reduced methods, e.g., R-SRM (Han & Gao, 2021a), has already been established in prior work. This paper primarily unifies existing methods and follows standard proof techniques to recover the same complexity guarantees, offering limited new theoretical insights for the field.", "other_comments_or_suggestions": "- **Page 2, Line 57:** Typo – \"euclidean\" should be \"Euclidean.\"\n\n- **Assumption 2.2(1):** The requirement that all iterates stay within a totally retractive neighborhood of $x_*$ seems restrictive. Can this assumption be relaxed?\n\n- **Assumption 2.2(2):** Is the assumption of a bounded Riemannian Hessian necessary for the analysis? \n\n- **Equation (3):** What does $\\tilde{x}$ represent? Please clarify.\n\n- **Table 1:** Can you explain the meaning of each column for better clarity?\n\n- **Second Line After Equation (7):** Should \"SGD\" be \"SG\"? It seems like it should refer to \"stochastic gradient\" rather than \"stochastic gradient descent.\"\n\n- **Algorithm 1:**  \n  - What are the sizes of $I_k$ and $J_k$?  \n  - How is $v_k^s$ computed? Note that Equation (7) provides the formula for $v_k$, not $v_k^s$.\n\n- **Paragraph After Algorithm 1:**  \n  - The connections between R-SRM, Riemannian SVRG, and R-PAGE with Algorithm 1 are not clearly explained.  \n  - Additionally, some of these methods follow a single-loop structure, while Algorithm 1 appears to be a two-loop framework. Please clarify these distinctions.\n\n- **Section 5:** The choice of \\( S \\) is missing in the convergence analysis. Please specify how it is determined.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p8fdMmVrXm", "reviewer": "Reviewer_vLDf", "summary": "In this paper, the authors provide a unified framework for several Stochastic Recursive Variance Reduced Gradient algorithms. They first propose a new algorithm that integrates recursive momentum with variance reduction techniques, called Stochastic Recursive Variance Reduced Gradient (SRVRG), and extended it to Riemannian manifolds. Next, they propose a unified framework (SERENA), which includes SRVRG and extends to other variance reduction methods. Via studying their unified formulation, they derive Incremental First-order Oracle (IFO) complexity of finite-sum problems and online problems. These complexities are shown to match the theoretical lower bound for stochastic non-convex optimization.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the encouraging feedback and valuable comments.\n\nWe introduce the SRVRG estimator, which is proposed for the first time in both Euclidean space and Riemannian space. Numerical experiments illustrate the superiority of the R-SRVRG algorithm. Furthermore, we present a unified framework for Riemannian stochastic variance reduction methods and provide a unified theoretical analysis by giving an upper bound on the variance of the Riemannian stochastic estimators. Our proposed algorithm can achieve optimal complexity while also offering a wide range of parameter choices. For example, when other parameter settings are as outlined in the Corollary 5.4, $\\beta$ and $b'$ only need to satisfy $\\sqrt {\\frac{\\beta }{{b'}}}  = \\max \\{ {\\frac{1}{{\\sqrt n }},\\varepsilon } \\}$ (finite-sum case) or $\\sqrt {\\frac{\\beta }{{b'}}}  =  {\\varepsilon }$ (online case) for the R-SRVRG algorithm to achieve optimal complexity. Other methods often directly specify parameters in order to achieve optimal complexity, such as in the analysis of R-AbaSRG for online case, $b' = \\varepsilon^{-1}$. Furthermore, experimental results demonstrate robustness of parameters.", "claims_and_evidence": "Claims made in the submission are well supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed framework makes sense as it unifies/generalizes a range of previous works.", "theoretical_claims": "I did not check the correctness of proofs for theoretical claims.", "experimental_designs_or_analyses": "I did not check the soundness/validity of the experimental designs.", "relation_to_broader_scientific_literature": "The key contributions of the paper provides connections among several previous works, including SGD, SVRG-type, SARAH-type, Hybrid-SGD, STORM, SVRRM and the newly proposed SRVRG. (see Table 1 in the paper)", "essential_references_not_discussed": "I am not aware of any essential references not discussed.", "other_strengths_and_weaknesses": "Strengths:\n- SERENA unifies several variance reduction techniques, achieving optimal IFO complexities for both finite-sum and online settings, improving upper bound results compared to prior analysis.\n- The unified approach paves the way for further exploration of variance reduction techniques in manifold optimization.\n- The formulation of recursive gradient estimators adapted to the geometry of Riemannian manifolds can influence future algorithm design.\n\nWeaknesses:\n- While the unification and improvements are valuable, the core ideas are extensions of well-established variance reduction methods in Euclidean spaces.", "other_comments_or_suggestions": "I have no other comments or suggestions.", "questions_for_authors": "I have no other questions for the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nTibW4ilau", "reviewer": "Reviewer_1swq", "summary": "The paper proposes the combination of SVRG and SARAH for stochastic variance reduced non-convex optimization, and extends it to the Riemannian setting. Combinations of Riemannian stochastic methods with or without variance reduction, existing or proposed in this paper,  all can be subsumed into a unified update with mix parameter beta which was proved to converge at a rate matching existing IFO complexity lower bound in the finite-sum or online setting. Experimental results are provided to demonstrate the slight advantage of the proposed Riemannian methods over existing ones.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your valuable comments.\n\n1. We will increase the discussion on the motivation behind the proposed SRVRG algorithm. The motivation for proposing SRVRG is that when $u_k$ is an SVRG-type estimator, parameter $\\beta$ can be larger, which allows the variance of $v_k$ to decrease more rapidly (see the formula in the right column on lines 168-170 of the paper). Our theory also demonstrates that the range of $\\beta$ is relatively expansive. Corollary 5.4 indicates that setting $\\sqrt{\\beta/b'} = \\varepsilon$ or $\\sqrt{\\beta/b'} = n^{-1}$ can ensure the optimal complexity of R-SRVRG, which means that $\\beta$ and $b'$ can balance each other. In contrast, Corollary 5.10 indicates that the R-SRM algorithm requires $\\beta = K^{-2/3} = \\mathcal{O}(\\varepsilon^{2})$ to achieve optimal complexity. This is the reason why our algorithms perform better. Experimental results also validate the robustness of $\\beta$. \n\n2. Although the updates in our proposed algorithm are somewhat more complex, the average time for a single IFO call is 0.634s, which is 3.65 times the average time for a Riemannian update and 4.7 times the average time for a vector transport. This indicates that a significant portion of the algorithm's runtime is consumed by IFO calls, especially when a larger batch size $b'$ is selected in the inner loop. Our algorithm allows for a trade-off between the inner loop size $m$ and the batch size $b'$ (because in Corollary 5.4, $m = \\beta^{-1}$), meaning that for the same $m$, our algorithm can support smaller batch sizes. Therefore, even when the x-axis represents running time, our algorithm still performs well. The comparison of algorithm performance with time on the x-axis demonstrates that our algorithm is comparable to the best-performing algorithms. See https://anonymous.4open.science/r/SERENA-RiemanOptimization/.\n\n3. For the parameters of the other algorithms, we adopted most of the settings from (Han\\&Gao,2021b). Additionally, we performed parameter optimization for certain algorithms, such as R-PAGE. The reason that algorithms R-SRVRG and R-SVRRM, as well as R-SRM and R-Hybrid-SGD, are selected with the same parameters is that algorithm R-SRVRG can cover R-SVRRM, and similarly, algorithm R-Hybrid-SGD can cover R-SRM.\n\n4. Thank you very much for other comments or suggestions. The final part of the definition of the exponential mapping will be modified to $\\dot{\\gamma}(0)=\\frac{d}{d t} \\gamma(t)|_{t=0}=u$.  The first condition of vector transport will be modified to ''1) $\\mathcal{T}$ has an associated retraction $R$, i.e., for $x \\in \\mathcal{M}$ and $\\iota, \\xi \\in \\mathrm{T}\\_x \\mathcal{M}, \\mathcal{T}\\_\\xi(\\iota)$ is a tangent vector at $R_x(\\iota)$'' with the symbol $y$ is changed to $\\iota$.", "claims_and_evidence": "I feel that the motivation of coming up with the combination of SVRG and SARAH for stochastic variance reduction is missing. Given a lot of existing combinations, why does the proposed combination stand out? Although experimental results demonstrate the proposed method converges faster, it is just slightly faster and measured in terms of IFO. Since the update is more complicated than existing ones, I guess this method doesn't work well in practice, e.g., in terms of running time.\n\nThus, I feel the contribution mainly lies in theoretical investigation on the combination of SVRG and SARAH, and a unified perspective that integrate all existing combinations.", "methods_and_evaluation_criteria": "Evaluation of the methods looks reasonable.", "theoretical_claims": "I didn't check proofs.", "experimental_designs_or_analyses": "yes. My concern on experimental design is that there are so many baseline methods. It's unclear what is a good way to set their hyper-parameters in order for a fair comparison with the proposed method. For example, in the first paragraph of Section 6, it says \"We selected the same parameters for R-SRVRG and R-SVRRM. Similarly, we chose identical parameters for R-SRM and R-Hybrid-SGD for comparison\". But why?\n\nAlso, as I mentioned previously, it might be a totally different case if the x-axis is running time.", "relation_to_broader_scientific_literature": "The paper proposes a new combination of R-SVRG and R-SARAH, and further provides a unified perspective on Riemannian stochastic variance reduced methods.", "essential_references_not_discussed": "Literature work seems complete.", "other_strengths_and_weaknesses": "NULL", "other_comments_or_suggestions": "In Section 2, about exponential map definition, the derivative of r(t) should be evaluate at 0.\n\nThe first condition of vector transport seems incorrect. Also, why two notations for it, T_x^z and T_{\\xi}(y)?", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ktvazNP40s", "reviewer": "Reviewer_PqwF", "summary": "The paper presents a variance reduction framework for Riemannian non-convex optimization. The proposed framework covers many existing variance reduction algorithms on manifolds and theoretical analysis matches the best known results in the Euclidean space. Numerical experiments are conducted on PCA, LRMC and RC problems and benchmarked against extensive baselines. The performance of the proposed algorithm seems promising.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable comments. You are primarily concerned with the contributions of this paper compared to previous variance reduction algorithms in Euclidean space, as well as whether the assumptions made in this paper can be satisfied. Additionally, you are interested in the impact of the parameter  $\\beta$ on convergence and the simplification of symbols in the theorem. Below, we will address each of these points in detail.\n1. Compared to previous work in Euclidean space, our contributions are as follows.\n \n(1) Firstly, we propose the SRVRG estimator, which does not exist in Euclidean space. Secondly, we present a unified theoretical analysis for the first time.  In non-convex settings, the theoretical analysis of various variance reduction algorithms shows significant differences even in Euclidean space, with some requiring the construction of Lyapunov functions.\n\n(2) Our Corollary 5.4 indicates that SRVRG exhibits superiority in parameter selection. For instance, in finite-sum case where $ n < \\varepsilon^{-2} $, when the other parameter settings adhere to those specified in the Corollary, it is sufficient for $ \\beta $ and $ b'$ to satisfy ${\\beta}/{b'} = n^{-1} $ to achieve optimal complexity. Given that $ \\beta = m^{-1} $, it follows that $ mb' = n $. For other algorithms, although some can also achieve optimal complexity, the parameters in their analyses are fixed; for example, in R-AbaSRG, $ b' = m = n^{1/2}$. Our experimental results also validate the robustness of $\\beta$. We will add a remark after Corollary 5.4 to clarify the following point, for example, \"Corollary5.4 indicates that if $ \\beta $ and $ b'$ satisfy $\\sqrt {\\frac{\\beta }{{b'}}}  = \\max \\\\{ {\\frac{1}{{\\sqrt n }},\\varepsilon } \\\\}$ (finite-sum case) or $\\sqrt {\\frac{\\beta }{{b'}}}  =  {\\varepsilon }$ (online case), our proposed algorithm can achieve optimal complexity. This highlights the advantages of our algorithm in terms of parameter selection.\".\n\n2. Due to space limitations, we omitted the explanation of the assumptions outlined below. \n\n(1) Assumption 2.2 (1) is to avoid a bad case in Riemannian optimization. Namely, the sequence $\\{x_k\\}$ may converge to an optimum $x_*$, while the connecting retraction $\\{R_{x_k}(\\xi_k)\\}$ does not converge where $x_{k+1}=R_{x_k}(\\xi_k)$. This assumption is also employed in papers (Zhou et al., 2021, Han \\& Gao, 2021b, Kasai et al., 2018). \n\n(2) In Assumption 2.2 (2), the boundedness of the Riemannian Hessian is unnecessary, and we will remove it. \nAssumptions 2.2 (1) to (3) clearly hold for compact manifolds, including sphere, (compact) Stiefel and Grassmann manifolds. For non-compact manifolds, like SPD matrices, the assumptions hold by choosing a sufficiently small neighbourhood $\\mathcal{X}$. \n\n(3) Assumption 2.2 (4) generalizes the notion of smoothness on the euclidean space to Riemannian manifold and is satisfied if $\\frac{d^2 f(R_x(t \\xi))}{d t^2} \\leq L$ for all $x \\in \\mathcal{X}, \\xi \\in T_x \\mathcal{M}$ with $\\||\\xi\\||=1$. \nAssumption 2.2 (5) and (6) are necessary due to our reliance on vector transport to approximate parallel transport. These two assumptions can be derived by requiring the vector transport $\\mathcal{T}$ to be isometric and satisfy $\\|| \\mathcal{T}\\_{x}^y u- \\mathrm{D}R_x(\\xi)[u] \\|| \\leq c_0 \\|| \\xi \\|| \\|| u \\||$, where $\\mathrm{D}R_x(\\xi)[u]=\\frac{d}{d t} R_x(\\xi+t u)|_{t=0}$ is the differentiated retraction. Assumption 2.2 (6) is ensured by Taylor approximation in a compact set $\\mathcal{X}$.\n\n(4) Assumption 2.3 (1) ensures that the Riemannian distance can be expressed in terms of the inverse exponential map. Assumption 2.3 (2) hence relates the exponential map with the retraction. Indeed, we have $\\left\\|R_x^{-1}(y)\\right\\| \\leq \\mu\\left\\|\\operatorname{Exp}_x^{-1}(y)\\right\\|$ and $\\left\\|\\operatorname{Exp}_x^{-1}(y)\\right\\| \\leq \\nu\\left\\|R_x^{-1}(y)\\right\\|$. This assumption remains valid when $\\mathcal{X}$ is sufficiently small. These assumptions are also standard as in (Sato et al., 2019, Han \\& Gao, 2021b)\n\n3. The experimental results in the appendix C.3 indicate that the algorithm is robust to $\\beta$. Theoretically, Corollary 5.4 indicates that setting $\\sqrt{\\beta/b'} = \\varepsilon$ can ensure the optimal complexity of the algorithm, which means that $\\beta$ and $b'$ can balance each other, and when a larger $b'$ is chosen, the algorithm will be more robust  to $\\beta$.\n\n4. We will simplify the symbols in the theorem, such as $\\mathcal{L} = {{\\tilde L}^2}{\\mu ^2}{\\nu ^2}$.", "claims_and_evidence": "It is a bit unclear what is the extent of the contributions of this paper. The paper seems to propose a unified framework (based on hybrid-SGD, a method already proposed in the Euclidean space). In this regard, the contribution seems limited, given the analysis would readily follow from the paper. On the other hand, it seems the paper also establishes a recursive variance reduction framework, which seems novel, provided no such algorithms exist in the Euclidean space.", "methods_and_evaluation_criteria": "The evaluation criteria is standard for the problem and the datasets/problem instances are commonly used as benchmarks for Riemannian non-convex optimization.", "theoretical_claims": "I briefly went through the proof in the appendix. The proof seems to be correct.", "experimental_designs_or_analyses": "The experiment designs are standard. However, the analyses of the experiment results lack depth and insights. For example, how does the change in beta improves the convergence.", "relation_to_broader_scientific_literature": "Established a unified framework, which completes the variance reduction methods for Riemannian optimization.", "essential_references_not_discussed": "All the key related works have been cited.", "other_strengths_and_weaknesses": "It is unclear about the contributions of this work, relative to existing works in the Euclidean space.", "other_comments_or_suggestions": "(1) the presentation of the results can be improved. The constants in the theorems can be simplified.\n\n(2) Assumption 2.2(2), Riemannian Hessian bounded not written out explicitly.\n\n(3) There are too many assumptions and it is unclear when such assumptions are satisfied.", "questions_for_authors": "Please clarify the contributions relative to the prior variance reduction methods in the Euclidean space.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All the reviewers are of the opinion that the paper has good merits. The unified viewpoint is interesting worth presenting to the community. In the final version, please take care of the minor corrections and include explanations.
Decision: Accept (poster)