We are grateful to the reviewer for their detailed feedback, which we will take into account when preparing the final version, if accepted.

Unlike in the Euclidean setting, the paper does not provide a corresponding lower bound to demonstrate the optimality of the obtained complexity result. Is it possible to apply the PEP to the Riemannian setting considered in this paper, in order to derive a lower bound result?

First, to the best of our knowledge, the optimality of silver step-size is not verified even in Euclidean space yet [1] (although it is conjectured to be the optimal [2]).

Second, the worst-case analysis in the Riemannian setting must account for both the function and the geometry of the manifold, unlike in the Euclidean case, where the analysis is function-centric. In particular, certain functions, such as the squared-distance function, are intrinsically tied to the geometric structure of the manifold [3]. These complexities make lower bound analysis substantially more challenging in the Riemannian context, even when using tools such as PEP. In particular, to use PEP, the key ingredient is the interpolating inequality. However, to the best of our knowledge, the only Riemannian version of the interpolating inequality we are aware of is Proposition 38 of [4], which requires to verify whether the condition holds for all $x \in M$ instead of $x = x_j$ for $j = 1, \dots, n$. Since such condition is hard to implement numerically, applying PEP to Riemannian setting does not seem direct at this stage (see also Introduction of [5]). We leave this as an open direction for future work.

Could the authors clarify whether any part of the theoretical results, was informed or assisted by PEP?

In this work, we did not directly utilize the PEP, as we were already aware of the target inequality (Lemma 5.2) from the Euclidean studies. However, certainly our analysis is based on the original silver step-size paper [1] which was heavily informed by PEP.

References

[1] Altschuler et al. Acceleration by stepsize hedging II: Silver stepsize schedule for smooth convex optimization. Mathematical Programming, 2024.

[2] Grimmer et al. Composing Optimized Stepsize Schedules for Gradient Descent. Arxiv 2024.

[3] Alimisis et al. A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization. AISTATS 2020.

[4] Criscitiello et al. Curvature and complexity: Better lower bounds for geodesically convex optimization. COLT 2023.

[5] Hu et al. Extragradient Type Methods for Riemannian Variational Inequality Problems. AISTATS 2024.

I would like to thank the authors for the response. It was helpful. I have clearly described the strengths and weaknesses of the paper in the previous comments.

We are grateful to the reviewer for their detailed feedback, which we will take into account when preparing the final version, if accepted.

The theory only guarantees for iteration counts of the form $n=2^k-1$.

1. In fact, under additional geodesic strong convexity, one can establish the same convergence rate with respect to $n$ for general $n \neq \ell (2^{k^{\ast}} - 1)$. One can proceed as follows: Consider $m = 2^{k^{\ast}} - 1$ number of inner-iterations and $\ell$ number of outer iteration, as in our restarting algorithm. Now, for general $0 < r < m$, observe the following bound:

$

d^2(x_{m\ell + r, x_)} &\leq 2d^2(x_{m \ell + r - 1}, x_) + 2 d^2(x_{m \ell + r -1}, x_{m \ell + r})\\ &= 2d^2(x_{m \ell + r - 1}, x_) + 2 ||\log_{x_{m\ell + r - 1}} x_{m\ell + r}||^2\\ &= 2d^2(x_{m \ell + r - 1}, x_) +2 \eta_{r-1}^2 ||\nabla f(x_{m \ell + r - 1})||^2\\ &\leq 2(1 + L^2 \eta_{r-1}^2) d^2(x_{m \ell + r - 1}, x_*).

$

Here, the first inequality is coming from triangular inequality, the second equality is coming from the definition of the logarithmic map, and the last inequality comes from geodesic $L$-smoothness condition applied on $x_{m \ell + r - 1}$ and $x_*$.

Inductively applying the above result, one gets $d^2(x_{m\ell + r}, x_*) \leq 2 \prod_{i=0}^{r-1} (1 + L^2 \eta_{i}^2)d^2(x_{m \ell}, x_*)$

Now, observe $\prod_{i=0}^{r-1} (1 + L^2 \eta_{i}^2) \leq (1 + L^2(1 + \rho^{\lceil \log_{\rho} \kappa \rceil}))^{m}$, by the definition of the silver step-size, restarting scheme in Theorem 4.2, and $r < m$. This is just a constant with respect to $n := m\ell + r$, since $m = 2^{\lceil \log_{\rho} \kappa \rceil + 1} - 1$ is a fixed constant. And by Theorem 4.2 of our work, $d^2(x_{m \ell}, x_*) \leq \exp(-Cm\ell/\kappa^{\log_{\rho} 2})d^2(x_0, x_*)$. Thus, $d^2(x_{m\ell + r}, x_*) \leq C_{\kappa} \exp(-Cm\ell/\kappa^{\log_{\rho} 2})d^2(x_0, x_*).$ This implies one still achieves the same $\exp(-Cn/\kappa^{\log_{\rho}2})$ convergence rate for any $m\ell < n < m(\ell + 1)$ for any $\ell \in \mathbb{N}$, and therefore for general $n$. We will elaborate this in detail in the revision.

2. On the other hand, as the reviewer mentioned, for generalized geodesically convex case the theory is only valid for $n = 2^k -1$. In the Euclidean setting, theoretical guarantees for general $n \neq 2^k-1$ are derived from the analysis of the silver step-size under strong convexity [1]. However, interpretation of the co-coercivity condition used in [1] does not readily extend to the Riemannian setting, unlike the role played by Proposition 3.8. As a result, we cannot directly apply the strong convexity-based analysis to generalize the theory for arbitrary $n \neq 2^k -1$ in Riemannian setup. That said, our numerical experiments show that the algorithm performs well even when $n \neq 2^k - 1$. This suggests there is a possibility of a generalizing the proof for arbitrary $n$, though we do not currently have a complete answer. However, even in this case, the restriction $n = 2^k - 1$ is not severe, as the number of iteration is something one can choose freely, rather than some fixed parameter.

When working with the Wasserstein space, deterministic RGD usually cannot apply.

We agree that in Wasserstein space, a Monte Carlo approximation of the updates are often used rather than a closed form expression [8,9]. That said, we would like to make three remarks:

First, in the literature of stochastic optimization, the analysis of deterministic algorithm is typically a prerequisite. Since a theoretical analysis of the deterministic silver step-size method on Riemannian manifolds was previously lacking, we considered this an essential first step.

Second, as the reviewer pointed out, in our main application, potential energy minimization, the deterministic form of the gradient is typically available, making our current formulation applicable.

Third, the main challenge in the stochastic setting lies in controlling the variance. To do so, the common practice in Wasserstein gradient-based methods is to use Monte-Carlo approximation of the true gradient [8,9]. While omitted for clarity, our experiments show the algorithm remains effective with stochastic gradients given enough samples (e.g., 100 in our tests). If needed, we’re happy to include these results in the appendix for the camera-ready version. The interaction between large silver step-sizes and noisy/inexact gradients poses challenges for variance control (while maintaining the acceleration), even in Euclidean settings. We leave it to future work.

The assumption of generalized geodesic convexity is strong and less standard in general Riemannian manifolds. Maybe this is the reason why this definition has not been introduced in the context of Riemannian optimization in the literature.

We acknowledge that generalized geodesic convexity may indeed be a strong and potentially restrictive condition in general Riemannian manifolds. However, we would like to make two points:

First, Example D.8 shows the concept of generalized geodesic convexity is not vacuous on general Riemannian manifolds beyond Wasserstein space. The Bures–Wasserstein (BW) space, although rooted in Wasserstein geometry, is a genuine Riemannian manifold in its own right. Moreover, the space of symmetric positive definite (SPD) matrices is a Riemannian manifold, without a direct connection to Wasserstein geometry. These examples illustrate that the notion of generalized geodesic convexity is not limited to Wasserstein space and may be broadly applicable across general Riemannian manifolds.

Second, the generalized geodesic convexity condition stems from the well-known Euclidean inequality (3.1), which has guided algorithm design in prior work [2,3,4]. In this regard, we thought extending this concept to Riemannian manifolds may offer a promising direction for developing analogous algorithms in the non-Euclidean setting.

The numerical experiments, while illustrative, are somewhat limited in scope, focusing only on the Bures--Wasserstein space and the sphere.

We also included the experiments on mean-field training of the two-layer neural network in Appendix E.2.3.

The paper does not include comparisons with Nesterov-style Riemannian Gradient Descent, which would provide a valuable benchmark. Also, include theoretical convergence curve.

Our primary objective in this work was to demonstrate acceleration relative to standard RGD, and for that reason, we thought including the comparison between Nesterov-type results might dilute the message. That said, if needed, we can include the comparison between Nesterov-type RGD, and the theoretical convergence curve in the final version.

The Wasserstein space is not a bona fide Riemannian manifold. I wondered if the theorems 4.1 and 4.2 still applied.

Yes. As discussed in the proof of Corollary 6.1, the same argument applies by directly substituting the corresponding quantities for the Wasserstein space. These substitutions are based on Otto calculus and do not require the Wasserstein space to be a Riemannian manifold in the strict sense.

The first experiment in the Wasserstein space: maybe also consider a more challenging form of $V$ instead of a quadratic function.

We used the quadratic potential energy since the target function $\mathbb{E}[V(X)]$ admits the closed-form expression. Note that even solving the quadratic potential problem is nontrivial due to the underlying Riemannian structure. Instead, to demonstrate the broader applicability of our method, we also included an additional experiment in mean-field neural network training in Wasserstein space in Appendix E.2.3. If the reviewer has any specific suggestion for $V$, we are open to include additional experiments in the final version.

The second experiment on a sphere: why did not you choose another function that is generalized geodesically convex instead?

The main reason we chose this problem is because the Rayleigh quotient maximization problem is a widely recognized benchmark in the Riemannian optimization literature [5, 6]. In fact, even functions that just satisfy both geodesic convexity and geodesic smoothness are rare. For instance, on compact manifolds, globally geodesically convex functionals do not exist [7].

Points regarding the notations.

We appreciate the reviewer for carefully noticing these typos. We will fix these typos when we prepare the camera-ready version.

References

[1] Altschuler et al. Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule. ACM 2024.

[2] Altschuler et al. Acceleration by stepsize hedging II: Silver stepsize schedule for smooth convex optimization. Mathematical Programming 2024.

[3] Li et al. A simple uniformly optimal method without line search for convex optimization. ArXiv 2023.

[4] Shugart et al. Negative Stepsizes Make Gradient-Descent-Ascent Converge. Arxiv 2025.

[5] Alimisis et al. Momentum improves optimization on riemannian manifolds. AISTATS 2021.

[6] Kim et al. Accelerated gradient methods for geodesically convex optimization: Tractable algorithms and convergence analysis. ICML 2022.

[7] Jonathan W. Siegel. Accelerated Optimization with Orthogonality Constraints. Journal of Computational Mathematics, 2020.

[8] Salim et al. The Wasserstein proximal gradient algorithm. NeurIPS 2020.

[9] Bonet et al. Mirror and preconditioned gradient descent in wasserstein space. NeurIPS 2024.

We are grateful to the reviewer for their detailed feedback, which we will take into account when preparing the final version, if accepted.

The silver step-size schedule is not clearly explained.

Silver step-size is constructed recursively, starting from $n = 1$ where $\eta_0 = \rho - 1$ for $\rho = 1+ \sqrt{2}$. Then, given the sequence of the step-sizes at $n$ number of iterations, $\eta_i$ for $i = 0, \dots, n-1$, one constructs the new sequence of the length $2n + 1$ by

$

\eta_i^{new} &=\eta_i, \qquad i = 0, \dots, n-1,\\\\
\eta_n^{new} &= 1 + \rho^{k-1},\\\\
\eta_i^{new} &= \eta_{i-n-1}, \qquad i = n+1, \dots, 2n.

$

Then, one conducts the gradient descent by $x_{i+1} = \exp_{x_i}(-\eta_i \nabla f(x_i))$ We will add more details about the silver step-size in the revised version.

Several key theoretical arguments, including Lemma 5.4 and its proof, are not clearly presented.

We will make our best effort to clarify the arguments in the revision. If the reviewer finds a specific part unclear, we would greatly appreciate it if the reviewer could point it out so that we can elaborate on it more thoroughly.

The study focuses on the exponential and logarithmic maps on the manifold, while omitting the consideration of the retraction map.

It is true our analysis is performed on exponential map and logarithmic map, and this is due to the use of metric distortion lemma which require the exact exponential map and logarithmic map. For the retraction map, one can consider the similar error analysis as in [1], while we did not pursue this generality.

Can the assumption of generalized geodesic convexity be relaxed to standard geodesic convexity?

The need of generalized geodesic convexity comes from deriving the key Equation (3.1). Therefore, avoiding the use of generalized geodesic convexity would depend on whether (a) one can derive Equation (3.1) without invoking the generalized geodesic convexity, or (b) one can prove the silver step-size acceleration without bringing Equation (3.1) type inequality.

Regarding (a), there has been an attempt to derive a similar inequality under standard geodesic convexity and $L_0$-smoothness (Lemma 2.3. of [2]). However, this approach does not recover the exact inequality we need: First, a constant $L$ is of the form $L_0d^2(x_i,x_j)$, which depends on the specific points involved. Second, the structure of the subtractive term differs from that in Equation (3.1).

Regarding (b), the current silver step-size analysis relies critically on the precise form of Equation (3.1) even in the Euclidean case. So generalized geodesic convexity appears necessary at this moment.

Moreover, even in the Euclidean case, the proof of Equation (3.1) implicitly uses the notion of generalized geodesic convexity (which coincides with standard convexity in the Euclidean setting) by introducing an auxiliary third point $z$. In this regard, we believe that deriving (3.1) without invoking generalized geodesic convexity, if possible, would require fundamentally different techniques from those used in existing proofs.

What challenges arise in establishing convergence rate estimates when $n \neq 2^k - 1$? Is it possible to achieve acceleration with silver step-size for geodesically strongly convex functions without employing a restarting strategy?

1. Under additionally geodesically strongly convex functional, one can establish the same convergence rate with respect to $n$ for general $n \neq \ell (2^{k^{\ast}} - 1)$. One can proceed as follows: Consider $m = 2^{k^{\ast}} - 1$ number of inner-iterations and $\ell$ number of outer iteration, as in our restarting algorithm. Now, for general $0 < r < m$, observe the following bound:

$

d^2(x_{m\ell + r, x_)} &\leq 2d^2(x_{m \ell + r - 1}, x_) + 2 d^2(x_{m \ell + r -1}, x_{m \ell + r})\\ &= 2d^2(x_{m \ell + r - 1}, x_) + 2 |\log_{x_{m\ell + r - 1}} x_{m\ell + r}|^2\\ &= 2d^2(x_{m \ell + r - 1}, x_) +2 \eta_{r-1}^2 |\nabla f(x_{m \ell + r - 1})|^2\\ &\leq 2(1 + L^2 \eta_{r-1}^2) d^2(x_{m \ell + r - 1}, x_*).

$

Here, the first inequality is coming from triangular inequality, the second equality is coming from the definition of the logarithmic map, and the last inequality comes from geodesic $L$-smoothness condition applied on $x_{m \ell + r - 1}$ and $x_*$.

Inductively applying the above result, one gets $d^2(x_{m\ell + r}, x_*) \leq 2 \prod_{i=0}^{r-1} (1 + L^2 \eta_{i}^2)d^2(x_{m \ell}, x_*)$

Now, observe $\prod_{i=0}^{r-1} (1 + L^2 \eta_{i}^2) \leq (1 + L^2(1 + \rho^{\lceil \log_{\rho} \kappa \rceil}))^{m}$, by the definition of the silver step-size, restarting scheme in Theorem 4.2, and $r < m$. This is just a constant with respect to $n := m\ell + r$, since $m = 2^{\lceil \log_{\rho} \kappa \rceil + 1} - 1$ is a fixed constant. And by Theorem 4.2 of our work, $d^2(x_{m \ell}, x_*) \leq \exp(-Cm\ell/\kappa^{\log_{\rho} 2})d^2(x_0, x_*)$. Thus, $d^2(x_{m\ell + r}, x_*) \leq C_{\kappa} \exp(-Cm\ell/\kappa^{\log_{\rho} 2})d^2(x_0, x_*).$ This implies one still achieves the same $\exp(-Cn/\kappa^{\log_{\rho}2})$ convergence rate for any $m\ell < n < m(\ell + 1)$ for any $\ell \in \mathbb{N}$, and therefore for general $n$. We will elaborate this in detail in the revision.

2. On the other hand, for generalized geodesically convex case, we are currently unaware how to avoid such constraint. In the Euclidean setting, theoretical guarantees for general $n \neq 2^k-1$ are derived from the analysis of the silver step-size under strong convexity [3] without the use of restarting method. However, interpretation of the co-coercivity condition used in [3] does not readily extend to the Riemannian setting, unlike the role played by Proposition 3.8. As a result, we cannot directly apply the strong convexity-based analysis to generalize the theory for arbitrary $n \neq 2^k -1$ in Riemannian setup. That said, our numerical experiments show that the algorithm performs well even when $n \neq 2^k - 1$. This suggests that a generalization of the proof may be possible, though we do not currently have a complete answer. However, even in this case, we do not view the restriction $n = 2^k - 1$ as a critical drawback, as the number of iterations can be chosen freely in practice.

Paper Formatting Concerns

We appreciate the reviewer for carefully reviewing the paper and catching the typos, notation errors, and grammar errors. If accepted, we will fix these issues when we prepare the camera-ready version.

I believe the conclusion of Lemma D.6 is correct but the proof of the zeroth-order criterion is not sufficiently rigorous.

We appreciate the reviewer for noticing the missing detail. Your argument is correct, and the result holds due to the additional equality condition at $t = 0$, which was inadvertently omitted. Precisely, let $\phi(t) = (1-t) f(x) + tf(y) - (f \circ \gamma)(t)$. Then, $\phi(t) \geq 0$ and $\phi(0) = 0$ is the global minimizer. Therefore,

From here, one can proceed the same as in Lemma D.6. We will revise the statement to clarify this point if the paper is accepted.

References

[1] Han et al. Riemannian Accelerated Gradient Methods via Extrapolation. AISTATS 2023.

[2] Ansari-Önnestam et al. Adaptive Gradient Descent on Riemannian Manifolds with Nonnegative Curvature. Arxiv 2025.

[3] Altschuler et al. Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule. ACM, 2024.

We are grateful to the reviewer for their detailed feedback, which we will take into account when preparing the final version, if accepted.

Using barycenter problems to highlight the performance of a Riemannian method is like continuing to use the "MNIST" dataset as a benchmark.

Our experiment addresses the Rayleigh quotient maximization problem, not the barycenter problem. It is a standard benchmark in Riemannian optimization [1, 2]. We also included more complex problems, Bures-Wasserstein optmization (Section 6.1) and mean-field training of the neural network (Appendix E.2.3).

The adaptation from the Euclidean to the Riemannian case seems to not require any true heavy lifting.

We faced two major challenges:

1. Meaningful geometric interpretation of (3.1) is nontrivial. This required proving Proposition 3.8, which was possible by introducing the notion of generalized geodesic convexity.

2. A key challenge in extending gradient methods to Riemannian manifolds is the lack of closed-form expressions for displacements between non-consecutive iterates. In Euclidean space, one has $x_l - x_k = -\sum_{i=k}^{l-1}\eta_i \nabla f(x_i)$ for all $k < l$. Unlike constant/monotonically decreasing step-size gradient analyses (including the momentum), Euclidean silver step-size analyses employ this non-consecutive relationship heavily [4]. However, RGD only allows the accesses to consecutive terms like $\log_{x_k} x_{k+1}$, making it difficult to adapt Euclidean silver stepsize analyses directly. Our main contribution was showing that, perhaps surprisingly, pairwise relationships alone suffice to recover the desired guarantees, which we elaborated in Remark 5.5.

The functions that may satisfy the generalized geodesic convexity/smoothness inequality seems small.

While this condition is new and few functions are known to satisfy it, as the reviewer mentioned we show in Appendix D.1 that it's non-vacuous with examples in popular spaces like Wasserstein, Bures–Wasserstein, and SPD matrices, along with verifiable criteria (Lemma D.6) and concrete examples (e.g., Example D.8). The fact that it is not vacuous suggests that it is worth further investigation. We believe that continued study will help clarify the scope of this condition.

The analysis is (strangely) limited to the nonnegative curvature case, and it would be valuable to see what happens for negative curvature.

Our proof does not readily extend to negative curvature case. In this case, the metric distortion inequality takes the form

for some curvature-dependent constant $\zeta > 1$ (Lemma 5.2, [2]). When the curvature is non-negative, $\zeta = 1$.

Naive application of our technique boils down to showing:

$\frac{f(x_*) - f(x_k)}{r_{k}} - \frac{1}{4r_{k}^2}\\|\nabla f(x_n)\\|^2 - \frac{1}{r_{k}}\langle\log_{x_n}x_*,\nabla f(x_n)\rangle - \zeta \sum_{i=0}^{n-1}\eta_{i}^{2} \\|\nabla f(x_i)\\|^2 - 2\sum_{i=0}^{n-1}\eta_{i}\langle \nabla f(x_i), \log_{x_i}x_*\rangle \geq \sum_{i,j = 0,\dots, *}\lambda_{ij}Q_{ij} \geq 0.$

For this to hold, $\eta_i$ or/and $r_k$ and $\lambda_{ij}$ should depend appropriately on $\zeta$, which poses two challenges if $\zeta > 1$.

1. Due to dependencies between $r_k, \eta_i, \lambda_{ij}$, and $Q_{ij}$, adjusting these parameters jointly is a much harder problem.

2. More importantly, since (5.1) is an inequality (unlike the equality in Euclidean case), coefficient matching technique used in Euclidean case fails, and proving $\lambda_{ij} \geq 0$ becomes harder. Our proof detoured this problem by showing that the nonzero coefficients actually coincide to the Euclidean ones. But when extending to negative curvature, since $\lambda_{ij}$ changes, such technique no longer works.

Since there are interesting non-negatively curved manifolds with broad applications, e.g., Wasserstein and Bures-Wasserstein space, we stayed with the non-negatively curved manifolds for this work. We defer the extension to negatively curved space to future work.

The empirical results suggest intense oscillations of the Riemannian silver step method ... render the current contribution to be primarily of theoretical value. ... is this a problem that also plagues the Euclidean case? How to ameliorate that?

The oscillation is expected under silver step-size scheme that involves occasional large step-sizes, as this step-size is designed to guarantee multi-step descent, rather than monotonic decrease in function value that one observes in gradient descent with constant/monotonically decreasing step-sizes (see [8]). Similar behavior is observed in neural network training with large step-sizes as well [10].

On the other hand, our experiments consistently show that the last iterates remain stable across multiple runs (see Figure 4) as the theory suggested, illustrating statistical robustness of the algorithm.

Lastly, while [4] does not provide the experimental result for $n \neq 2^k -1$, we observe similar oscillations in our experiments in Euclidean case too.

The need for the same inequality (3.1) has come up several times ... previous authors left it as an open problem.

In Proposition 3.8, we provided the sufficient condition for the inequality (3.1). Other than Proposition 3.8, we were unaware of study of this inequality in Riemannian setting (except the similar one in Lemma 2.3 of [3], but it is not the same) in any other works. We would be grateful if the reviewer can provide the reference.

By paying an extra factor of $L$ one should be able to get around generalized geodesic convexity assumption.

With only geodesic convexity and $L_0$-smoothness, a similar inequality can be obtained as shown in Lemma 2.3 of [3], but this is not precisely the same inequality needed. First, the constant $L = L_0d^2(x_i,x_j)$, now is not global and depends on the iterates. Second, the subtractive term is different from that in Equation (3.1). Since the precise form of Equation (3.1) is crucial for our proof, generalized geodesic convexity appears necessary at this moment.

The authors should discuss the implications and limitations of Equation (3.1) more thoroughly.

We interpret (3.1) via Proposition 3.8, as generalized geodesic convexity and geodesic smoothness. Geodesic smoothness is a standard concept, and we provide interpretations with examples in Appendix D.1 to illustrate generalized geodesic convexity.

If the authors could prove inequality 3.1 without invoking their sufficient condition for some nontrivial settings, that would be a valuable contribution on its own.

Even in the Euclidean case, the proof of Equation (3.1) implicitly uses the notion of generalized geodesic convexity by introducing an auxiliary third point $z$. In this regard, we believe that deriving (3.1) without invoking generalized geodesic convexity would require fundamentally different techniques from those used in existing proofs.

Is there a possibility of a Lyapunov function type analysis?

We did not pursue a Lyapunov functional-based argument in this paper. While it will be interesting to explore Lyapunov functions that capture multi-step function-value descent, we defer it to future work.

The hypersphere example is known to satisfy a Riemannian PL inequality.

Rayleigh quotient maximization problem does not satisfy PL. Here the minimizer is $x_* = v_{\max}$, the eigenvector corresponding to the largest eigenvalue of $H$. The Riemannian gradient is $\nabla f(x) = (x^T Hx)x - Hx$. When $x = v_k \neq v_{\max}$ is any eigenvector of $H$, $\| \nabla f(x) \|_{x}^2=0 < 2\mu(f(x) - f(x_*))$, hence contradicting Riemannian PL inequality.

PL functions cannot be solved at an accelerated rate, so that applies to the Riemannian case too. However, it is still possible that for the sphere, one can bypass that type of lower bound. Might the authors have some thoughts about that?

Firstly, since Rayleigh quotient problem does not satisfy Riemannian PL condition, the lower bound does not apply.

Secondly, typically the lower bound analysis is obtained by the worst-case constructions. However, many functions do not exhibit worst-case behavior and may admit faster convergence rates than the lower bound suggests (e.g., Introduction of [9] comes up with one example).

Thirdly, we are cautious about extending Euclidean lower bounds to specific Riemannian manifolds (e.g., the sphere). The metric distortion inequality (Lemma C.1), which is an equality in Euclidean space, can be a strict inequality on some non-negatively curved Riemannian manifolds. Thus, at least in principle, some Riemannian manifolds may allow potentially sharper convergence rates.

References

[1] Alimisis et.al. Momentum improves optimization on riemannian manifolds. AISTATS 2021.

[2] Kim et.al. Accelerated gradient methods for geodesically convex optimization: Tractable algorithms and convergence analysis. ICML 2022.

[3] Ansari-Önnestam et.al. Adaptive Gradient Descent on Riemannian Manifolds with Nonnegative Curvature. Arxiv 2025.

[4] Altschuler et.al. Acceleration by stepsize hedging II: Silver stepsize schedule for smooth convex optimization. Mathematical Programming. 2024.

[5] Li et.al. A simple uniformly optimal method without line search for convex optimization. ArXiv 2023.

[6] Shugart et.al. Negative Stepsizes Make Gradient-Descent-Ascent Converge. Arxiv 2025.

[7] Zhang et.al. Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds. NIPS 2016.

[8] Altschuler et.al. Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule. Journal of the ACM 2024.

[9] Grimmer et.al. Beyond Minimax Optimality: A Subgame Perfect Gradient Method. Arxiv 2025.

[10] Cohen et.al. Gradient descent on neural networks typically occurs at the edge of stability. ICLR 2021.