Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: (Here and below, I will write "smooth" in the sense of differentiability, and
"gradient Lipschitz" for "smooth-in-the-optimization-sense")

The authors prove that in the noisy oracle model (so function values and
gradients are noisy, not exact), there is no accelerated Riemannian gradient
descent algorithm (Nesterov-type acceleration) that succeeds whp uniformly over
all manifolds and all geodesically convex functions. To show this, they
study the minimization of a particular smooth geodesically convex function on
the hyperbolic plane $\mathbb{H}^2$, namely the the intrinsic distance to a
fixed point ${x}^{\star}$ (i.e. ${x} \mapsto \mathrm{dist}({x}, {x}^{\star})$),
and prove the lower bound with this function; they also establish that this
function is not pathological among functions on the hyperbolic plane in the
sense that its gradient-Lipschitz constant is of near-minimal size.
The proofs use elementary properties of the hyperbolic plane -- gradient and
Hessian expressions for the distance, and the fact that ball volumes in the
hyperbolic plane are exponential in the radius -- as well as a reduction to a
"noisy query game" problem on which the lower bound is established.

main_review: ## Summary wrt decision

The paper is written, referenced, and motivated well, and provides a
noteworthy contribution to a problem that has seen extensive study in the
literature. The authors' contributions will no doubt help to focus future
research in this line: for example, by focusing on acceleration on
nonnegatively curved spaces, or on investigating the open problem of lower
bounds for optimization with exact gradients. My rating just reflects a few
points of confusion listed below that I had while reading the proofs -- I
expect to increase it after these are resolved in the discussion phase.

## Detailed comments

- Because the number of queries we should expect to have if acceleration in the
  hyperbolic plane is possible is only asserted, rather than shown (sentence at
  line 151), I am having some trouble reconciling the "no robust acceleration"
  claim with the guarantee of Theorem 3 -- maybe it would be helpful if this
  was spelled out in detail (i.e. both a precise illustration of this claim in
  line 151 and a precise definition of what is taken to be an accelerated
  method in this context). In particular, is the claim "... Nesterov-like
  acceleration in the hyperbolic plane [is] possible" equivalent to the
  existence of a guarantee like the one in Theorem 2? I think this equation is
  not labeled correctly ($d$ should be the squared distance to the optimum /
  the squared diameter of the domain; I'm looking at Theorem 7 in the cited
  reference [13]). Then if I interpret a formula like this in the context here,
  we have $L = r$ and $d = r^2$, and ignoring the noise term and the local
  linear rate would give a formula $\mathrm{dist}(x_k, x^\star) \leq r^3 /
  k^2$, so to get within distance $1$ wouldn't we expect to need time
  $O(r^{3/2})$? (should it be within distance $r$ instead?) If we're using the
  the local linear rate here to get the prediction, this feels like it might
  not preclude the existence of accelerated methods. If the intention was
  rather to demonstrate that the lower bound proved here is met by a
  non-accelerated gradient descent method (hence ruling out the possibility for
  acceleration to exist), it might be nice to have this discussed in detail as
  well. I am not up-to-date on the latest rates for smooth strongly
  geodesically convex optimization, but if I look at the cited reference [37],
  (Theorem 13 and Theorem 15), it seems like these rates are not necessarily
  inconsistent with the possibility of having an accelerated method (the key is
  that relative to the euclidean setting, these rates may have extra unsavory
  dependences involving $\zeta(\kappa, r) \approx r$ here; I would appreciate
  correction if sharper rates have already been established). 
  In general, the possibility of having these "extra constants" appear in the
  rates relative to the euclidean setting makes me feel that it may be hard to
  use a query complexity lower bound to show impossibility of acceleration
  without better upper bounds for vanilla gradient descent: for example, adding
  an "extra $r$" into the numerator as above (corresponding to a curvature term
  like the $\zeta(\kappa, r)$ in [37]) would lead us to expect to need $r$
  queries to get within distance $O(r)$ with an accelerated method, which would
  be consistent with Theorem 3's lower bound. I would appreciate some
  clarification on these points (I apologize if I am missing something
  obvious).
- It would nice to see additional comparisons to some pieces of related work,
  e.g. [1-2] below -- do these works suffer from the same limitations as the
  ones mentioned in lines 30-38?
- Have the authors considered higher-dimensional analogues of their lower bound
  -- for example for optimization on the hyperbolic space $\mathbb{H}^d$, or
  Hadamard manifolds of negative curvature? This feels out-of-scope, but it may
  be interesting to know whether the same ideas have direct implications for
  general negatively-curved spaces.

## Minor Typos/etc

- line 149: missing a "plane"
- line 151: might want to consistently call this the "plane" since 'models' for
  the hyperbolic plane aren't discussed?
- Theorem 3: first "at" should be "and"?
- line 212: "expected logarithm of the number of options"
- Proof of theorem 3: the specific simplification here requires $r \geq 1$;
  maybe express this in the hypotheses
- eqn before line 235: loose parenthesis in numerator

## Referenced works

[1] https://arxiv.org/abs/2002.04144

[2] https://arxiv.org/abs/2008.02252

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors show that when optimizing a hyperbolic function using noisy gradients, it is impossible to achieve speedup akin to that of Nesterov's momentum even when the function is geodesically convex. They do this by reformulating the optimization procedure as a query game. 
main_review: Strengths

* The result is interesting and has many application for machine learning on hyperbolic space.
* The proof technique is clever and is an overall nice construction.
* The proofs and constructions are clear and the intuition is well explained and provides good insight.

Weaknesses

* The proof is currently a bit limited in scope. In particular, it may be helpful to touch upon cases where the curvature $K$ of the hyperbolic space is not $-1$. These have seen practical use, but I expect the result to be quite similar.

Verdict

The paper is compact and well structured, and the central result is important both from a theoretical and practical standpoint. I advocate acceptance.


limitations_and_societal_impact: The authors adequately addressed limitations and potential negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work shows that an inexact accelerated gradient method for geodesically convex functions on a Riemannian manifold might not exist by showing a lower bound for an optimization problem in the Hyperbolic 2-space.

The proof is based on reduction to playing a game, in which there are $n$ probability distribution functions, and the player can make a query and receive an observation sampled from a specific distribution function and need to figure out which function generates the samples.

main_review: 

**1. (Significance)**

It is unclear to me how strong/applicable the negative result is. Specifically, does it say anything on problems like matrix completion [9, 28, 33], dictionary learning [11, 26], robust subspace recovery [39], mixture models [18]? Is acceleration not possible in these problems?  The authors might want to discuss the connections. 



**2. (Proof)**

I am not sure if the proof is correct and I have some questions.

2.1 (Between line 234-235) 

It looks to me that if the underlying optimization algorithm can only query function values but cannot get gradients, then the proof of this paper still applies and the number of the query needed would also be $\Omega(r)$, where $r$ is the condition number.  From the equation right above line 235, it looks like the linear dependency on the condition number $r$ is solely due to the number of points is $n = \exp( \Theta(r) )$ (right below line 234) in the Hyperbolic 2-space. That is, the $\Omega(r)$ complexity does not depend on whether the algorithm has the gradient information or not, which means that the gradient information does not help!? Something wrong?


2.2 (Intuition of the reduction)

In this rebuttal, can the authors provide an intuition why the proof can be reduced to playing a game?



**3. (Clarity)**

This paper is not self-contained from my perspective. For example, the authors should provide derivations of Fact 2. Also, the argument on line 170-175 does not appear to be rigorous. It would be helpful if the authors can provide the details in the supplementary and/or in this rebuttal.

limitations_and_societal_impact: The authors should addressed the limitation in this rebuttal.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper presents a lower bound on the complexity of a noisy gradient oracle for minimizing a strongly convex real-valued function defined on the hyperbolic plane. This gives answers regarding the acceleration phenomenon on Riemannian manifolds and limitations of previous works. A lower bound on the condition number of a strongly convex function in the hyperbolic plane is also provided.
main_review: Originality: The main idea and techniques presented in this paper surprised me by their originality. I have never seen this kind of arguments applied in deriving lower bounds for optimization, so, to the best of my knowledge this paper is quite novel. The related work is cited properly, there are 2-3 papers in Riemannian acceleration that could be included and discussed though.

Quality: The paper is a complete work presenting a lower bound in the noisy setting. As the authors mention, the only limitation of this work is that does not tackle the exact gradient oracle setting (without noise). In the noisy setting, theorem 3 implies that for minimizing a $1$-strongly convex and $O(r)$-smooth function $\Omega(r/\log(r))$ iterations are required, which is strictly bigger than $O(\sqrt{r})$ that an accelerated method would need if $r$ is sufficiently large (but still compatible with gradient descent). The authors prove also in theorem 6 that the assumption of a function with $O(r)$ condition number in the hyperbolic plane is not restricting. However, there are many parts of the paper that seem problematic to me:

1. The constant $c$ which bounds the distribution should be between $0$ and $1$ and potentially $c \rightarrow 0$, in which case $\log(c) \rightarrow -\infty$. How is this possible to happen in Theorem 3? If you do the same in Lemma 5, it means that you reduce the options by a negative number. You can still put $c=1$ and vanish $\log(c)$ term though. In any case, I do not understand why this $c$-bound on the distribution is essential for the analysis.

2. When $C \rightarrow 0$ the same as above happens with the $\log(C)$ term, which is weird since the noise is assumed to be small. I think there is a mistake in 234, namely the volume of $\mathcal{X}$ is not $O(r^4 C^3)$, but $O(r^4+2 C r^2+2 r^3 C +4 r C^2+r^2 C^2 +2 C^3)$ (if I did the calculation correctly). Thus, when $C=0$ the analysis seems to be valid without the $\log(C)$ term in the lower bound. Given that point I cannot understand what is the role of noise after all. Would be happy if the authors could indicate where exactly introducing noice is needed in the analysis.

3. It is a bit surprising that the result is based on the squared distance function, which is a very easy-to-minimize one. I see that this is comfortable for being able to compute the condition number, but is there any other point that this specific form for $f$ is needed?

4. In comment 2, I don't understand how one can put exponentially many points in a circle with mutual distance $r/2$, when the circumference is $O(e^r)$. I think you can put exponential amount of points only in distance $O(1)$, do I miss something? I don't think that $O(1)$ distance change any result though, the authors themselves write in 152 that the minimization goes until accuracy $1$ and then in theorem 3, until $r/5$, I cannot see why this changes.

5. I understand that given a bound like in Theorem 3, in order to achieve acceleration we must initialize close to the minimizer and stay always in such a neighborhood ($r$ must be small). I don't understand how that explains also the exponential dependence on the domain in [23]. Can you explain? Could you also comment on the relantionship of your result with the one in [Yuanyuan Liu, Fanhua Shang, James Cheng, Hong
Cheng, and Licheng Jiao. Accelerated first-order
methods for geodesically convex optimization on riemannian manifolds] (neurips 2017) ?

Minor issues: i) The function $dist(x,x^*)^2$ is $2$-strongly convex and $2 \frac{r}{tanh(r)}$-smooth, you can multiply with $0.5$ to get an $1$-strongly convex function. ii) In which point of the proofs the probability $2/3$ arise? iii) End of 234 there is an extra parenthesis.

Clarity: The paper is well-written and the main results clearly stated. There are points though that more explanation could be added, see my previous comments. I particularly like the intuitive explanation in section 2.2.

Significance: Given that my previous points are addressed (because in the current form there are points that do not make sense to me), the paper proves that adding noise in the oracle used for optimization of a cost function in the hyperbolic plane is much worse than doing the same in the Euclidean space. This is because the circumference of a circle in the hyperbolic plane is $O(sinh(r))=O(e^r)$ and the area is $O(e^{2r})$. To the best of my understanding this problem is orthogonal to the very problem of acceleration with a non-noisy oracle. For instance, in the sphere the behaviour of circles is exactly the opposite, i.e. the circumference is $O(sin(r))$, thus I would expect that adding noise to an oracle for optimizing in the spherical case to yield to better results than the Euclidean case. In [38] for instance, the effect of curvature seems to be symmetric between the positive and negative case. This is the case also in  [Foivos Alimisis, Antonio Orvieto, Gary Bécigneul, Aurelien Lucchi, Momentum Improves Optimization on Riemannian Manifolds]. I do believe that optimization itself is more difficult in lower curvature, but so far the main problem seems not to be that, but rather non-linearity. Non-linearity on the other hand does not seem to affect directly the noise as discussed previously with the example of the sphere.

Overall, I believe that these are good to know results regarding how noise behaves in negative curvature, but I don't think that are directly related to the problem of acceleration with non-noisy oracle.

Given the above, I think that there are many issues for the authors to address and vote for rejection. I am willing to change my evaluation though if my main concerns are answered in the rebuttal.

 







limitations_and_societal_impact: The work is theoretical and has no negative societal impact. The authors discuss the theoretical limitations of the paper.
review_title: null

Meta-review: While reviewers felt the intuition behind the paper is relatively straightforward, ultimately they agreed that the results could provide useful  for practical applications.
Decision: Accept (Poster)