A No-go Theorem for Robust Acceleration in the Hyperbolic Plane
Authors: Linus Hamilton
Ankur Moitra
Venue: NeurIPS 2021 Poster (2021)
Keywords: geodesic convexity
acceleration
lower bounds

Abstract: In recent years there has been significant effort to adapt the key tools and ideas in convex optimization to the Riemannian setting. One key challenge has remained: Is there a Nesterov-like accelerated gradient method for geodesically convex functions on a Riemannian manifold? Recent work has given partial answers and the hope was that this ought to be possible. Here we prove that in a noisy setting, there is no analogue of accelerated gradient descent for geodesically convex functions on the hyperbolic plane. Our results apply even when the noise is exponentially small. The key intuition behind our proof is short and simple: In negatively curved spaces, the volume of a ball grows so fast that information about the past gradients is not useful in the future.

A No-go Theorem for Robust Acceleration in the Hyperbolic Plane
Linus Hamilton"
Ankur Moitra
Abstract
In recent years there has been significant effort adapt the key tools and ideas convex optimization to the Riemannian setting. One key challenge has remained: Is there Nesterov-like accelerated gradient method for geodesically convex functions on a Riemannian manifold? Recent work has given partial answers and the hope was that this ought to be possible. Here we prove that noisy setting, there no analogue of accelerated gradient descent for geodesically convex functions on the hyperbolic plane. Our results apply even when the noise is exponentially small. The key intuition behind our proof is short and simple: In negatively curved spaces, the volume of a ball grows so fast that information about the past gradients not useful in the future.
Introduction
Convex optimization 24 undergirds much of machine learning, theoretical computer science, operations research and statistics. Geodesically convex optimization is a natural generalization that replaces Euclidean space with a Riemannian manifold and we require that the function we want to minimize is convex along geodesics [3 It turns out that many optimization problems of interest, while non-convex in the Euclidean view, become geodesically convex when equipped with the right geometry. Some notable examples: The fastest known algorithms for computing Brascamp-Lied constants [1 3 and solving related problems like the null cone problem
exploit geodesic convexity. In machine learning, it arises in matrix completion 9 28 33 dictionary learning [1]] 26),
robust subspace recovery [39], mixture models [T8] and optimization under orthogonality constraints
[4]. In statistics, some basic problems like estimating the shape of elliptical distribution [35 16
or estimation matrix normal models [29] (4) are best viewed through the lens geodesic convexity.
In recent years there has been significant effort to adapt the key tools and ideas in convex optimization
the Riemannian setting. This includes giving new deterministic 37 stochastic 21 30
variance-
reduced [25] 36), projection-fres (34] adaptive [20] and saddle-point escaping 12 27 first-order
methods. Many new ingredients are needed because the traditional analyses the Euclidean setting
rely on the linear structure. Still, one of the key challenges has remained elusive thus far:
Is there a festerov-like accelerated gradient method for geodesically convex func- tions on a Riemannian manifold?
This question is particularly natural settings where the curvature is non-positive, since it inherits many useful properties of Euclidean space such as having unique geodesics between any pair of
DDepartment of Mathematics, Massachusetts Institute of Technology. Email: luh@mit. This work was supported in part by a Fannie and John Hertz Foundation Fellowship.
Departmeen of Mathematics. Massachusetts Institute Technology. Email: moitra@mit.cc edu. This work was supported in part by Microsoft Trustworthy AI Grant, NSF CAREER Award CCF-1453261. NSF Large CCF1565235, a David and Lucile Packard Fellowship, an Alfred P. Sloan Fellowship and an ONR Young Investigator Award.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

points. There has been notable partial progress. Zhang and Sra [8) were among the first to clearly articulate this question. They gave a method that achieves Nesterov-like like acceleration you start sufficiently close to the optimum. Since then, the aim has been to develop methods that achieve global acceleration. Ahn and Sra 2 gave partial answer by giving method that converges strictly faster than gradient descent and eventually accelerates. Martínez-Rubio [23] gave method that achieves global acceleration but at the expense of having hidden constants that depend exponentially on the diameter of the space.
In this work, our main contribution is to dash these hopes by showing that acceleration is impossible even in the simplest of settings where we want to minimize a smooth and strongly geodesically convex function over the hyperbolic plane. Our proof assumes that the gradient oracle returns an answer that has just an exponentially small amount of noise. In comparison, in the Euclidean setting is possible to achieve Nesterov-like acceleration with an inverse polynomial amount of noise. Of course, in realistic settings some amount of noise is usually unavoidable.
Theorem 1. Given access ò-noisy gradient oracle, any algorithm for finding point within distance r/5 of the minimum of a l-strongly convex and (rr)-mooth function in the hyperbolic plane that succeeds with probability at least 2/3 must make at least
Ω
logr + 1/6
queries in expectation. Here r is a bound on how far the optimum is from the origin.
Comment 1. While it may at first seem like a limitation to restrict to functions whose condition number depends on the radius, we show in Section 5 that in the hyperbolic plane this is inevitable in the sense that every geodesically convex function has a condition number that is at least linear in the radius.
See Theorem 3 for the full version. The key intuition is short and simple: In negatively curved spaces, the volume of a ball grows so fast that information about the past gradients is not useful in the future. Indeed for discrete approximations to the hyperbolic plane, like a 4-regular tree, it is not hard to make this intuition precise. This intuition also helps clarify why existing acceleration results need to assume that you are already within a constant neighborhood of the optimum or depend badly on the radius.
is more challenging to reason about general algorithms that can make queries anywhere they like and not just at discrete set of locations. The proof of our main result is based in terms of game where a player wants to find a hidden item in a set and can make queries to a noisy oracle. We prove information-theonn to convex optimization over curved spaces. The key point is that balls in hyperbolic space grow exponentially with their radius, and this is in turn related the size of the in our game. We believe that our query lower bounds for the noisy oracle game can be more broadly applicable, even beyond the realm of optimization.
abstraction
lower bound for this game, and then connect it back
The natural open question in our work is to prove similar lower bounds when we are given an exact gradient oracle. However any such algorithm that depends exact gradient computations, and fails with even an exponentially small amount of noise, would seem to be rather brittle to issues of practical concern, like rounding due machine precision.
Remark 1.
This paper is structured as follows: in Section we introduce the reader to the counterintuitive properties of the hyperbolic plane. Section 3 defines the noisy gradient problem and phrases it as a more general 'noisy query game'. Section 4 proves our crucial lower bound on general noisy query problems, and then applies it to prove our no-go theorem about acceleration in curved spaces.
2 The Hyperbolic Plane
This section serves an introduction to the hyperbolic plane H establishing the important facts we use for our proof as well as intuition for our main result. The first and most important fact about the hyperbolic plane is that it large:
Fact
10
The circumference and area of hyperbolic circle are both exponential in its radius.
For illustration, consider a tiling of the hyperbolic plane with congruent equilateral pentagons. As you can see, the number of pentagons at distance r from the origin grows exponentially in r.

---

This gives intuition for our result: When attempting to minimize a function whose minimum lies somewhere within a ball of radius r, the hyperbolic plane forces you search over much larger area than any fixed dimension of Euclidean space would. This inherently makes it harder to exploit information from past queries about the function value and gradient, as you can in acceleration in the Euclidean case, when we are interested in reaching point far away from the origin.
2.1 Convexity
Definition 32
function from manifold (here, the hyperbolic plane HH?) to R is geodesically convex it is convex along any geodesic. This is equivalent to the Hessian of the function having nonnegative eigenvalues. We say that function is a-strongly convex if the eigenvalues of its Hessian are bounded below by a. Moreover it is 3-smooth if the eigenvalues of its Hessian are bounded above by B.
1 31
Note that even though a function f HP IR may live in the hyperbolic plane, its gradient at any point, denoted by V (z). lives space isomorphic to R And similarly its Hessian that point an ordinary 2 2 matrix. This is because the gradient and Hessian are local properties of function, and locally the hyperbolic plane looks Euclidean. This can be made formal through the concept of tangent spaces, but will not be needed for our purposes.
In this paper we will prove lower bounds for minimizing arguably the simplest geodesically convex function, the distance squared function:
Fact the hyperbolic plane, the distance squared function æ + d(æ, )²² is geodesically convex and its minimum is x=. At distance from x", this function is 1-strongly convex and (r/ tanh r)- smooth.
The strong convexity and smoothness come from the formula for its Hessian given in 15
2.2
Why Pirates Don't Search for Treasure in the Hyperbolic Plane
The purpose of this subsection is to provide intuition for our main theorem and is not required to understand our results. Imagine pirate who has buried treasure in the desert somewhere at distance 100 away from her. She does not remember exactly where the treasure is, but is possession of compass which points towards it. The compass' reading has error, though: the order of 10 16 degrees. (This setting is analogous to an algorithm able to make noisy queries to the gradient of some function.) In the Euclidean plane, the pirate could easily find the treasure: take compass bearing, walk 100 steps, and dig. An error 10-16 degrees would literally be subatomic.
However, if the pirate attempted this strategy in the hyperbolic plane, she would end up at distance just over 190 from her treasure. She would have started to walk away from the treasure after just few steps! (Specifically, constant number of steps that scales with log(1/ 11/10-16), Therefore, she

---

would have to repeatedly look at her compass every few steps in order to make progress towards the treasure. This is why gradient descent has only linear convergence hyperbolic spaces. Of course, this falls short of explaining why algorithm converges faster. One of the authors (though we won't say who) is indebted to the video game HyperRogue [22] for giving intuition about the hyperbolic plane. One level of this game features a similar scenario with pirates and compasses.
3 Optimization with Noisy Gradient Oracle
In this section we define the main model we will be interested in. Moreover we recall convergence bounds in the Euclidean case, particularly those that continue to hold in the presence of small amount of noise, as a point of comparison.
Definition 2. The radius-r gradient optimization model is as follows: There an unknown differen- tiable function f whose minimum is within distance of the origin. An algorithm may query points a within distance 1000r the origin Upon querying æ, the algorithm learns f() and the gradient (z))).
Definition 3. In the noisy version of the model, instead of learning the exact values of f(x) and ff(),, the algorithm receives f(x) + 21 and V f(x) + 22 where 21 and 2/ are noise. We do not require the noise to be of specific form such as Gaussian, uniform, etc we only require that the noise terms for different queries are independent.
Definition 4. We say noise c-non-concentrated if on any query, the probability distribution function of the noise is everywhere bounded above by c. We say noise is C-precise if the noise term never has magnitude larger than C.
In Euclidean space, small amount of noise does not preclude acceleration. As a point of comparison, we restate the key result (Theorem 7) from [3]
Theorem 2 (from [3).. There is an algorithm that, given C-precise noisy oracle access an L-smooth p-strongly convex function I and its gradient, along with a starting point at distance d from the minimum of f. outputs after oracle queries point I& such that
f(xx) - (lin) s so(Ld. min
+ min (k polyooyy(C, VL/H)
(The bound in the original paper is more precise, making big-O constants explicit and using a more refined notion of precision.) This theorem implies that accelerated gradient descent works in Euclidean space even in the presence of noise, provided that the noise has magnitude at most some inverse polynomial in Contrast our main result: in hyperbolic space, accelerated gradient descent impossible even with exponentially small noise.
The Noisy Gradient Task in the Hyperbolic Plane
Recall, will be interested in the simplest example of convex function in the hyperbolic plane: f(z) == dist(r, )²²², where x² is some point at distance r from the origin. Finding the minimum of is equivalent to locating x*. Without noise, an algorithm could locate x* exactly in one query, because any gradient is guaranteed to both point exactly at x and indicate the distance to x*. What about with noisy gradients?
Within the hyperbolic of radius r centered at the origin, our function f is O(r) and I-strongly convex. (As an aside, in Theorem 6 we show that for any f-smooth and a-strongly convex function in the hyperbolic disk we must have 3/a = ((r)). If Nesterov-like acceleration in the hyperbolic plane were possible should be able locate x= to within distance in time O(vr). Unfortunately, as we will show, this task is impossible. Even worse, is impossible to get any polynomial factor speedup in the convergence.
3 'The number 1000 is arbitrary and only affects constants inside big- notation. The reason this assumption as follows: if an algorithm were to query point r superexponentially far away from the origin and leam f(x) + noise, then f() would be so large that the noise term could be disregarded completely. Thus, removing this assumption would require more refined noise model, such multiplicative noise.

---

Theorem 3. In the radius-r noisy gradient optimization model in the hyperbolic plane, if queries receive noisy answers with --non-concentrated C- C-precise noise, then any algorithm that can find point within distance r/5 of the minimum of the function at succeeds with probability at least 2/3 must make at least
Ω logr log C. loge
queries. This true even the function is guaranteed to be 1-strongly convex and O(r) at every point within distance r from the origin.
To prove this result, we will generalize the noisy gradient model any setting in which an agent makes queries and receives probabilistic answers over a discrete set of possibilities. In this general setting, we will prove a lower bound on the number of queries needed determine the state of the world.
4.1 Noisy Query Games
Definition 5. A noisy query game is tuple (n, Q, f), with which the following one-player game is played: A secret number i" is chosen uniformly at random from {1, (1......, n). determine i To do so, the player may make a query q Q and receive an observation X X. The observation is sampled using some probability distribution function fq.:- (a)). The player wins when they can guess i* with probability least 2/3.
The player's goal is
We remark that for us X' will be region in Euclidean space and we will use |.Y' to denote its volume. The noisy game broadly seems to be natural model for class of noisy learning tasks. In particular, it generalizes the noisy gradient task in the hyperbolic plane, we show in the following comment:
Comment 2. Consider the noisy gradient task in which we place = ( points equally in circle of radius r in the hyperbolic plane, so that the points are distance r/2 apart. (This possible because circles are exponentially large- see [10], page 92 so greedily picking points one at time and removing a ball of radius r/2 around each runs out of volume only after exponentially many steps.) The secret number it corresponds to one of these points z². Define the function f(z) = dist(x, )²²² whose optimum is x². The player makes queries in Q := a region in the hyperbolic plane with radius (r)), and receives noisy gradient observations. Now the player can win if and only if they can locate the optimum of fx), among the discrete set of possibilities, with probability least 2/3.
We now state our lower bound for noisy query games:
Theorem 4. In a noisy query game (n, Q, X, suppose the noise is c-non--omcentrated. i.e. all probability distribution functions fa are everywhere bounded above by some constant c. Then for the player to be able to guess i" with probability at least 2/3, the player must make at least queries.
O l
Theorem is difficult to prove directly, because the player's knowledge a posterior distribution which change in complicated ways. To overcome this obstacle
the options 21,2, .1,2,...,n1) nn. and prove Theorem we will define an easier 'transparent' version of the noisy query game, where the player's knowledge is subset of (1,2....; n representing which options could possibly be the correct one. Then we will show that even in the easier version of the game, the player needs many queries in expectation succeed.
4.2 The Transparent Noisy Query Game
In a noisy query game, observations are sampled from probability distribution functions fy, on a space X. One way sample an observation from fg.i is to sample uniformly from the region under its graph. Let Gy.; denote this region. Note that the volume of Gg.s must be 1, because probabilities always sum to 1. In the transparent noisy query game, answer query q by telling the player point (x, y) uniformly sampled from the graph region Gy In the normal query game the player only learns I, the normal version can only be harder.
The key question is: How does the player's knowledge update when she receives an observation (z, y)? For any option i whose graph area Gg,s does not include the point (a, y), the player learns
5

---

that cannot possibly be correct. For the rest of the options, the player learns nothing. This is because observations are sampled uniformly and each Gg has unit area, by Bayes' rule the player's posterior on i* remains uniform over all remaining options. (Here we have assumed that the prior is uniform at the beginning.)
Indeed, this convenient property is the reason we defined this transparent version: It allows us to easily analyze the player's progress by tracking only the number of remaining possible options, rather than the messy details of what happens to the posterior distribution.
Lemma 5. Suppose all the fq are coon-concentrated distributions. Then in the transparent noisy query game, query decreases the logarithm of the number of possible remaining options by most log (c) in expectation.
Proof. Let m be the number of options remaining before the query. For convenience, use the notation N [z, y) for the number of graph areas Gg among the m remaining options, that contain (x. y). If the player receives the query result (I, y). they would be left with N(x, y) remaining options. So after the query, the expected number of options remaining is
/ G..
E,+
log (N(x,y) drdy
where the expectation taken uniformly at random from among the m remaining options. Moving the expectation inside the integral sign and using the assumption that all graph areas are contained within X' x c), we get that the above expectation equal to:
N(x; v) log (N v)) drdy m
[x
Since each graph has area 1, the integral [xx (xx y) is m. So by Jensen's inequality, subject to this restriction, the above quantity is minimized when N is constant the entire domain X' x [0, c]. The minimum value is
m/c/X m
log (m/clX() dody = log (m/cl/1) = log m log (c)
x'x [0]c
So the expectation of the logarithm of the number of possible options left decreases by at most log (c), desired.
Now can prove main lower bound for the noisy query game:
Let n, denote the number of possible remaining options after i steps. Thus have no = n. Now let X be a random variable that represents the cumulative progress the algorithm has made. In particular let
Proof of Theorem 4
X = log n log
Applying Lemma 5 and Markov's bound we have that X < 3E[X] with probability at least 2/3, the algorithm succeeds at being able to determine i* after T steps must have ny = 1. Putting everything together we have
0 = log nT log n
X > log -3/2' log(c)x1)
and rearranging completes the proof.

---

4.3
Proof of the Main Theorem
Our main result now follows easily from the machinery of noisy query games:
Proof of Theorem 3 Suppose we want to minimize the function f(x) = dist(z, z²)². This function 1-strongly convex and 2r-smooth within distance r of the origin. (As mentioned earlier, [[S] shows the eigenvalues of the Hessian are I and r/ tanh S 1.) First we apply the reduction in Comment 2 so that we have n = (r() points with pairwise distance at least r/2. Moreover x² is among them and corresponds the secret number i* in the noisy query game.
In the setting of Theorem a player makes queries within a certain region of the hyperbolic plane, and learns the (noisy) function value and gradient at their query point. They are tasked with finding point within distance r/5 of x². Because the n points have pairwise distance at least r/2, doing so requires figuring out which of the points is x So the player must win the query game, which by log Theorem takes least [og[[X]e]
queries.
We picked n = ( above, and the value of e is stated in Theorem assumptions. But what |.8%, i.e. the volume containing all query answers? Since the player queries are restricted to region in the hyperbolic plane of radius Or)), the true answer to their query is a function value in the interval [0, (rr)) along with a gradient in the disk B(0, O(r) C TR2, (Recall from Section 2. that the gradient lives in IR.2, not the hyperbolic plane.) By assumption, the noise causes error at most C, so the observed query answer must lie
[-C, + +C x B(0, + C) R
This is compact whose volume is polynomial in and C. In particular have |X| S C())C3). Therefore overall the player needs at least
log n (lcc) log(c) + O(log + log C)
r)
queries. This completes the proof.
5 Lower Bounds on the Condition Number
In Euclidean space, the function f(x) = | is 1-smooth and 1-strongly convex at every point. However, as we will show, the hyperbolic plane geodesically convex functions always have condition number that depends on the radius:
Theorem 6. Iff is a B-smooth, a-strongly convexfunction defined in hyperbolic disk of radius r, then 3/o 2 ((r).
Proof. First will give the intuition for the proof. Consider geodesic that dips a distance of I into the disk of radius r (see the picture below). On the one hand, due to a-strong convexity, the value of must vary large amount along this geodesic. But the other hand, this geodesic short, so by 9-smoothness / cannot vary much. These two properties will give us a lower bound on the condition number.
Now we proceed to the formal proof. Of all points at distance r 1 from the center of the disk, let x be at which is minimal. Without loss of generality suppose that f = 0 the center of the disk. By convexity and the minimality of x, we deduce that
f(v) 2 r f(x)
for all y on the cireumference of the disk. By a-strong convexity, f(z) > P(ar2). Now draw geodesic through æ. as pictured, perpendicular to the geodesic between the center of the disk and æ. This geodesic intersects the disk at two points y and y'. By 8-smoothness,
(r()) f(0') < f(x) (Bd(y.v/) 2
Finally, in hyperbolic geometry, the distance d(y, y/) is 01). See Lemma for an explicit calculation justifying this. Finally combining the three inequalities the previous paragraph gives 3/a 2 U(r). as desired.
L
7

---

y
Distance 7
Radius
Lemma 7. hyperbolic triangle with sides length v, whose altitude between those sides has length r 1, has a third side of length O(1).
Proof. This a straightforward calculation using formulas from [19
Let denote the length of the
third side and denote the measure of either angle adjacent to side c. (Those angles are equal because
the triangle is isoceles.) The hyperbolic law of cosines from 19 gives cos A [-1 (-1+cashh c) cosh
sinh esunh
The altitude length formula gives sin = sinh(r-1)
Using
sin
cos? gives:
sinh
1 sinh (aanh(r-11) 1) (-1 + cosh c) cosh?
sinh?
sinh² csinh2
Rearranging the above expression, get:
(I sinh (r
sinh2r r (-1 + cosh cosh r
sinh r
sinh2 c
As - oc the left-hand side tends to 1 0.86. Then solving the hinht-hand side for e gives solution, unique in the reals, that is approximately 3.31, which is O(1) as desired.
References
[1] P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
[2] Kwangjun Ahn and Suvrit Sra. From nesterov's estimate sequence to riemannian acceleration. pages 84-118, 2020.
[3] Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 172-181, 2018.
[4] Carlos Améndola, Kathlén Kohn, Philipp Reichenbach, and Anna Seigal. Invariant theory and scaling algorithms for maximum likelihood estimation. arXiv preprint arXiv:2003. 1300000..366..... 2020.
[5] Miroslav Bacák. Convex analysis and optimization in Hadamard spaces, volume 22. Walter de Gruyter GmbH & Co KG, 2014.
[6] Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 883-897 IEEF, 2018.
[7] Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Towards a theory of non-commutative optimization: geodesic first and second order methods for moment maps and polytopes. arXiv preprint arXiv: 1910. 1230. 2019.
[8] Peter Bürgisser, Ankit Garg, Rafael Oliveira, Michael Walter, and Avi Wigderson. Alternating minimization, scaling algorithms, and the null-cone problem from invariant theory. arXiv preprint arXiv:1711.08039 2017.

---

[9] Léopold Cambier and P-A Absil. Robust low-rank matrix completion by riemannian optimiza- tion. SIAM Journal on Scientific Computing. 38(5):8440-S44 S460, 2016.
[10] James W Cannon, William Floyd. Richard Kenyon, Walter R Parry, et al. Hyperbolic geometry. Flavors of geomelry, 31:59-115, 1997.
[11] Anoop Cherian and Suvrit Sra. Riemannian dictionary learning and sparse coding for positive definite matrices. IEEE transactions on neural networks and learning systems, 28(12)2885 2871,2016,
[12] Christopher Criscitiello and Nicolas Boumal. Efficiently escaping saddle points on manifolds. In Advances in Neural Information Processing Systems, pages 5987-5997, 2019.
[13] Olivier Devolder, François Glineur, Yurii Nesterov, et al. First-order methods with inexact oracle: the strongly convex case. CORE Discussion Papers, 2013016: 2013.
[14] Alan Edelman, Tomás A Arias, and Steven T Smith. The geometry of algorithms with or- thogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2)300-333, 1998.
[15] Ricardo Ferreira and Joao Xavier. Hessian of the riemannian squared distance function connected locally symmetric spaces with applications. In Controlo 2006, 7th Portuguese conference automatic control, volume 2. Citeseer, 2006.
[16] Cole Franks and Ankur Moitra. Rigorous guarantees for tyler's m-estimator via quantum expansion. arXiv preprint arXiv:2002.0007), 2020.
[17] Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of brascamp-lieb inequalities, via operator scaling. Geometric and Functional Analysis, 2801):100-145, 2018.
[18] Reshad Hosseini and Suvrit Sra. Matrix manifold optimization for gaussian mixtures. Advances in Neural Information Processing Systems, 28:910-918, 2015.
[19] Svante Janson. Euclidean, spherical and hyperbolic trigonometry. Notes, 2015.
[20] Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. Riemannian adaptive stochastic
gradient algorithms on matrix manifolds. 97:3262-3271, 2019.
[21] Masoud Badiei Khuzani and Na Li. Stochastic primal-dual method on riemannian manifolds of bounded sectional curvature. In 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 133-140. IEEE, 2017.
[22] Eryk Kopezyński, Dorota Celińska, and Marek Čtrnáct. Hyperrogue: Playing with hyperbolic geometry. In David Swart, Carlo H. Séquin, and Kristóf Fenyvesi, editors, Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture, pages 9-16, Phoenix, Arizona, 2017. Tessellations Publishing.
[23] David Martinez-Rubio. Acceleration in hyperbolic and spherical spaces. arXiv preprint arXiv:2012.03618. 2020.
[24] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
[25] Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance re- duced gradient algorithm with retraction and vector transport. SIAM Journal on Optimization, 29(2):1444 1472, 2019.
[26] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method. IEEE Transactions on Information Theory, 63(2):885 914, 2016.
[27] Yue Sun, Nicolas Flammarion, and Maryam Fazel. Escaping from saddle points on riemannian manifolds. Advances in Neural Information Processing Systems, pages 7276-7286, 2019.
[28] Mingkui Tan, Ivor Tsang, Li Wang, Bart Vandereycken, and Sinno Jialin Pan. Riemannian pursuit for big matrix recovery. In International Conference Machine Learning, pages 1539-1547, 2014.
[29] Tiffany M Tang and Genevera Allen. Integrated principal components analysis. arXiv preprint arXiv:1810.00832. 2018.

---

[30] Nilesh Tripuraneni. Nicolas Flammarion, Francis Bach, and Michael Jordan. Averaging stochastic gradient descent on riemannian manifolds. pages 350-687, 2018.
[31] Constantin Udriste. Convex functions and optimization methods on Riemannian manifolds, volume 297. Springer Science & Business Media, 2013.
[32]
lser1952770. Geodesic convexity and the geometric hessian. Available online at https hewethoverrlloo.nee////e/
[33] Bart Vandereycken. Low-rank matrix completion by riemannian optimization. SIAM Journal on Optimization, 23(2):121--223,, 2013.
[34] Melanie Weber and Suvrit Sra. Nonconvex stochastic optimization on manifolds via riemannian frank-wolfe methods. arXiv preprint arXiv: 1910.04199 2019.
[35] Ami Wiesel and Teng Zhang. Structured robust covariance estimation. Now Foundations and Trends, 2015.
[36] Hongyi Zhang, Sashank J Reddi, and Suvrit Sra. Riemannian svrg: Fast stochastic optimization on riemannian manifolds. Advances in Neural Information Processing Systems, 29:4592-46000 2016.
[37] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pages 1617-1638, 2016.
[38] Hongyi Zhang and Suvrit Sra. An estimate sequence for geodesically convex optimization. In Conference On Learning Theory, pages 1703-1723, 2018.
[39] Teng Zhang. Robust subspace recovery by geodesically convex optimization. arXiv preprint arXiv: 1386, 6011555577555,, 2012.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We include complete proofs of the promised lower bounds for geodesically convex optimization.
(b) Did you describe the limitations of your work? [Yes]
We emphasized both the necessity of noise in our lower bound, as well as the rationale for why some noise, perhaps due to machine precision, is natural in most practical settings.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The main results of the paper are lower bound for class of algorithms. Since we not give new algorithms, nor give new applications of existing ones, it does not seem like there could be any direct negative impacts of our owrk.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We fully explained all the assumptions we make in our lower bound. We also gave examples showing their necessity.
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are short and simple and fit within the main body of the submission.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
10

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]


Reviews:
[{"review_id": "waZxYYd3nVf", "reviewer": "Reviewer_XUX6", "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.\n\nThe 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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "\n\n**1. (Significance)**\n\nIt 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. \n\n\n\n**2. (Proof)**\n\nI am not sure if the proof is correct and I have some questions.\n\n2.1 (Between line 234-235) \n\nIt 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?\n\n\n2.2 (Intuition of the reduction)\n\nIn this rebuttal, can the authors provide an intuition why the proof can be reduced to playing a game?\n\n\n\n**3. (Clarity)**\n\nThis 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should addressed the limitation in this rebuttal.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "q-j8eRFShL", "reviewer": "Reviewer_seq7", "summary": "(Here and below, I will write \"smooth\" in the sense of differentiability, and\n\"gradient Lipschitz\" for \"smooth-in-the-optimization-sense\")\n\nThe authors prove that in the noisy oracle model (so function values and\ngradients are noisy, not exact), there is no accelerated Riemannian gradient\ndescent algorithm (Nesterov-type acceleration) that succeeds whp uniformly over\nall manifolds and all geodesically convex functions. To show this, they\nstudy the minimization of a particular smooth geodesically convex function on\nthe hyperbolic plane $\\mathbb{H}^2$, namely the the intrinsic distance to a\nfixed point ${x}^{\\star}$ (i.e. ${x} \\mapsto \\mathrm{dist}({x}, {x}^{\\star})$),\nand prove the lower bound with this function; they also establish that this\nfunction is not pathological among functions on the hyperbolic plane in the\nsense that its gradient-Lipschitz constant is of near-minimal size.\nThe proofs use elementary properties of the hyperbolic plane -- gradient and\nHessian expressions for the distance, and the fact that ball volumes in the\nhyperbolic plane are exponential in the radius -- as well as a reduction to a\n\"noisy query game\" problem on which the lower bound is established.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "## Summary wrt decision\n\nThe paper is written, referenced, and motivated well, and provides a\nnoteworthy contribution to a problem that has seen extensive study in the\nliterature. The authors' contributions will no doubt help to focus future\nresearch in this line: for example, by focusing on acceleration on\nnonnegatively curved spaces, or on investigating the open problem of lower\nbounds for optimization with exact gradients. My rating just reflects a few\npoints of confusion listed below that I had while reading the proofs -- I\nexpect to increase it after these are resolved in the discussion phase.\n\n## Detailed comments\n\n- Because the number of queries we should expect to have if acceleration in the\n  hyperbolic plane is possible is only asserted, rather than shown (sentence at\n  line 151), I am having some trouble reconciling the \"no robust acceleration\"\n  claim with the guarantee of Theorem 3 -- maybe it would be helpful if this\n  was spelled out in detail (i.e. both a precise illustration of this claim in\n  line 151 and a precise definition of what is taken to be an accelerated\n  method in this context). In particular, is the claim \"... Nesterov-like\n  acceleration in the hyperbolic plane [is] possible\" equivalent to the\n  existence of a guarantee like the one in Theorem 2? I think this equation is\n  not labeled correctly ($d$ should be the squared distance to the optimum /\n  the squared diameter of the domain; I'm looking at Theorem 7 in the cited\n  reference [13]). Then if I interpret a formula like this in the context here,\n  we have $L = r$ and $d = r^2$, and ignoring the noise term and the local\n  linear rate would give a formula $\\mathrm{dist}(x_k, x^\\star) \\leq r^3 /\n  k^2$, so to get within distance $1$ wouldn't we expect to need time\n  $O(r^{3/2})$? (should it be within distance $r$ instead?) If we're using the\n  the local linear rate here to get the prediction, this feels like it might\n  not preclude the existence of accelerated methods. If the intention was\n  rather to demonstrate that the lower bound proved here is met by a\n  non-accelerated gradient descent method (hence ruling out the possibility for\n  acceleration to exist), it might be nice to have this discussed in detail as\n  well. I am not up-to-date on the latest rates for smooth strongly\n  geodesically convex optimization, but if I look at the cited reference [37],\n  (Theorem 13 and Theorem 15), it seems like these rates are not necessarily\n  inconsistent with the possibility of having an accelerated method (the key is\n  that relative to the euclidean setting, these rates may have extra unsavory\n  dependences involving $\\zeta(\\kappa, r) \\approx r$ here; I would appreciate\n  correction if sharper rates have already been established). \n  In general, the possibility of having these \"extra constants\" appear in the\n  rates relative to the euclidean setting makes me feel that it may be hard to\n  use a query complexity lower bound to show impossibility of acceleration\n  without better upper bounds for vanilla gradient descent: for example, adding\n  an \"extra $r$\" into the numerator as above (corresponding to a curvature term\n  like the $\\zeta(\\kappa, r)$ in [37]) would lead us to expect to need $r$\n  queries to get within distance $O(r)$ with an accelerated method, which would\n  be consistent with Theorem 3's lower bound. I would appreciate some\n  clarification on these points (I apologize if I am missing something\n  obvious).\n- It would nice to see additional comparisons to some pieces of related work,\n  e.g. [1-2] below -- do these works suffer from the same limitations as the\n  ones mentioned in lines 30-38?\n- Have the authors considered higher-dimensional analogues of their lower bound\n  -- for example for optimization on the hyperbolic space $\\mathbb{H}^d$, or\n  Hadamard manifolds of negative curvature? This feels out-of-scope, but it may\n  be interesting to know whether the same ideas have direct implications for\n  general negatively-curved spaces.\n\n## Minor Typos/etc\n\n- line 149: missing a \"plane\"\n- line 151: might want to consistently call this the \"plane\" since 'models' for\n  the hyperbolic plane aren't discussed?\n- Theorem 3: first \"at\" should be \"and\"?\n- line 212: \"expected logarithm of the number of options\"\n- Proof of theorem 3: the specific simplification here requires $r \\geq 1$;\n  maybe express this in the hypotheses\n- eqn before line 235: loose parenthesis in numerator\n\n## Referenced works\n\n[1] https://arxiv.org/abs/2002.04144\n\n[2] https://arxiv.org/abs/2008.02252\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "I0QC5Wsqav-", "reviewer": "Reviewer_TFi3", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "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.\n\nQuality: 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:\n\n1. 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.\n\n2. 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.\n\n3. 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?\n\n4. 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.\n\n5. 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\nCheng, and Licheng Jiao. Accelerated first-order\nmethods for geodesically convex optimization on riemannian manifolds] (neurips 2017) ?\n\nMinor 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.\n\nClarity: 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.\n\nSignificance: 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.\n\nOverall, 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.\n\nGiven 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.\n\n \n\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work is theoretical and has no negative societal impact. The authors discuss the theoretical limitations of the paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "2SaCfhwoKW6", "reviewer": "Reviewer_mGYV", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "", "main_review": "Strengths\n\n* The result is interesting and has many application for machine learning on hyperbolic space.\n* The proof technique is clever and is an overall nice construction.\n* The proofs and constructions are clear and the intuition is well explained and provides good insight.\n\nWeaknesses\n\n* 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.\n\nVerdict\n\nThe paper is compact and well structured, and the central result is important both from a theoretical and practical standpoint. I advocate acceptance.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "There are no ethical issues. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)