Strengths
Besides from the strengths of having the theoretical results authors have, I want to emphasize the following.
This work usually states clearly the assumptions that is making, even though this could be improved, as I suggested. It was good to see the authors taking into account the non convexity of (1-\delta)\mathcal{K}. Some works ignore this fact, I wonder if they learn about this in the review of a paper. But the authors here are rigorous and work with the possible non-convex set.
The results with linear minimization oracle look fine to me
Weaknesses
# Main points of my review
Several results in this paper follow closely Garber and Kretzu (2022). This is not a criticism, of course there are several challenges in the Hadamard case that need to be surmounted.
I have several points of criticism though:
+ The paper contains some mistakes, and I am not sure if one could fix at least one of them while keeping the stated results (see below).
+ Moreover algorithm 4 has a regret guarantee in Theorem 2 which is non standard (algorithm plays a point and feedback is given for another point but the regret is still measured with respect to the played point). This seems an artifact of the proof, as in it was the notion that made the proof work, but without any other justification for this made-up definition of regret, usefulness of it or an application of it, the result is very weak.
+ Lemmas 3 and 4 yield that the number of iterations of algorithm 2 is exponential on R. This is not desirable. I do not want to criticize this point harshly, since Hadamard is hard and sometimes the geometry makes these exponential dependences appear, and this could be a result deserving its own paper. This dependence also appears in previous Riemannian online learning works. But rather, I just want to encourage the authors, possibly for future work, to try to improve this to a polynomial dependence (see below for a few comments on this).
While I think this works has value, I also think this is not ready for publication. At the very least the errors should be corrected, and the bandit results should not be presented as results (e.g. in the table) unless the authors can justify that the modify notion or regret makes sense. And in any case this should be clearly stated for the readers that only want to firstly check the introduction out.
# Proof Errors
Correct me if I am wrong but I think I found the following errors in your proofs. I can increase my score if the technical errors can indeed be fixed.
+ The proof of Lemma 1 is wrong, although fixable. The points y_{t+1} are not guaranteed to be in B_p(R) and so you cannot use lemma 29 as you stated it. However, if you look closely at Lemma 5 of Zhang and Sra, you will realize that the lemma actually says that \zeta depends on \kappa and c, which a stronger inequality than what you stated (dependence on \kappa and D). Using that stronger statement then you can show in your Lemma 1 that the \zeta in the proof depends on d(\tilde{y}_t, x) \leq D, and so the proof follows.
+ However, your lemma 2 has the same problem, and when you use it in the proof of lemma 4, you use it with the point y_i, which as you point out in L435, it is y_i \not \in \mathcal{K}. Therefore, the geometric deformation is not \zeta (which was defined as depending on D), and this does not seem to be so easily fixable.
# Other comments / suggestions
The results with linear minimization oracle look fine to me.
You should specify in lemma 5, that you always use y\in B_p(R), since you use f(x) = d(x y)^2/2 and you claim that it is \zeta smooth, which you can have because when you use lemma 5 in alg 6 it is always y\in B_p(R). But this is not stated and it was confusing for me.
This work usually states clearly the assumptions that is making, even though this could be improved, as I suggested. It was good to see the authors taking into account the non convexity of (1-\delta)\mathcal{K}. Some works ignore this fact, I wonder if they learn about this in the review of a paper. But the authors here are rigorous and work with the possible non-convex set.
"(pinpointing a compact set that contains the true optimum can improve time complexity) This makes metric projection onto a subset of Riemannian manifold seemingly indispensable, yet this operation is not only computationally taxing but can also lead to unwanted geometric distortion, which can undermine convergence. Certain works have depended on simplifying assumptions to prove results..." I disagree with the message that is given here. For several reasons:
+ Firstly, in many situations, one can "pinpoint" a compact set where the optimum is by just estimating the initial distance to minimizer and imposing ball constraints (and using a doubling trick or other tricks if necessary to avoid assuming knowledge of this distance ). In that case, the operation is "projection-free" according to your own definition in line 178, due to the simplicity of the operation, so not necessarily computationally taxing.
+ Secondly, while it is true that using projections can lead to greater geometric distortion that can undermine convergence (e.g. see https://arxiv.org/pdf/2305.16186.pdf where the authors make projected gradient descent work for smooth functions while quantifying the distortion), several works make use of projections to obtain algorithms that previously had to make the assumption of iterates staying in some set, and at the same time the geometric dependence on the convergence rates does not worsen. See for instance https://arxiv.org/pdf/2211.14645.pdf and theorem 7 in https://arxiv.org/pdf/2305.16186.pdf, and https://arxiv.org/pdf/2111.13263v2.pdf section 6
+ Thirdly, the works that mandate the iterates to be in a feasible set by assumption do so because they do not know how to enforce or guarantee their algorithms are in some feasible set, even if they have access to projections. It is not like the assumption is made to avoid projections that are "computationally taxing and with extra geometric distortions, which can undermine convergence" by using projections. Their techniques do not allow them to use projections and as explained above and more clever algorithms do without extra distortions.
You probably cannot compute \sigma_i in Algorithm 5 in close form. You probably would need a binary search and then have the algorithm be able to account for an error. Is that right?
# Exponential dependence on the diameter
Regarding the exponential nature of the constants in lemma 3 and running time in lemma 4, this phenomenon is very similar to the exponential constants that appear in the deformations of lemma 2 in https://arxiv.org/pdf/2012.03618.pdf However, in that paper they are interested on optimization, and they show that one can get away with this exponential complexity. The trick is a reduction from global optimization to approximately implementing a ball optimization oracle, so that the algorithms would only need to run in balls where R\sqrt{-\kappa} = O(1). The reduction goes as follows: optimize in one such constant-radius ball with linear rates (regularize as it is done in reductions if necessary, although you'd need smoothness of the losses) and then optimize in another ball with center equal to the previously computed point. In the online learning setting, it is harder but you could in principle try to run Riemannian OGC by minimizing the sort of FTRL objective you have by using this reduction (you'd have to optimize with linear rates in the intersection of constant curvature balls and your sets, but every time the infeasible projection would be easy). Or just implement the separation oracle by looking at making progress in constant-curvature balls. Anyway, maybe it doesn't work for you, but I hope it is useful to you to at least know that a problem of this kind has been sort of solved in Riemannian optimization.
# Minor suggestions / typos
L62 "While a horosphere gsc-convex" ->""While a horosphere is gsc-convex"
L200 "theLipschitz" -> "the Lipschitz"
L259 Alg 5. I would not say target vector y, since y is a point.
L269 Alg 6. "initial vector y" -> "initial vector y_i" (although again, I would not say initial *vector* )
# Edit after rebuttal
The authors provided fixes for the proof errors and a new algorithm two work with two point bandit feedback. I increased my score from reject to accept (from 3 to 7)
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.