Metric-Projected Accelerated Riemannian Optimization: Handling Constraints to Bound Geometric Penalties
Authors: David Martínez-Rubio
Sebastian Pokutta
Venue: NeurIPS 2022 Submitted (2022)
Keywords: riemannian optimization
acceleration
constrained
proximal methods

Abstract: We propose an accelerated first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions over a compact and geodesically-convex set in Hadamard manifolds, that we access to via a metric-projection oracle. It enjoys the same rates of convergence as Nesterov's accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Even without in-manifold constraints, all prior fully accelerated works require their iterates to remain in some specified compact set (which is needed in worse-case analyses due to a lower bound), while only two previous methods are able to enforce this condition and these, in contrast, have limited applicability like to local optimization or to spaces of constant curvature. Our results solve an open question in (Kim and Yang, 2022) and an another question related to one posed in (Zhang and Sra, 2016). In our solution, we show we can use projected Riemannian gradient descent to implement an inexact proximal point operator that we use as a subroutine, which is of independent interest. 


Metric-Projected Accelerated Riemannian Optimization: Handling Constraints to Bound Geometric Penalties
Anonymous Author(s)
Affiliation
Address
email
Abstract
We propose an accelerated first-order method for the optimization of smooth and (strongly or not) geodesically-conve functions over compact and geodesically- convex in Hadamard manifolds, that we access via metrii-prooeection oracle. It enjoys the same rates of convergence as Nesterov's 's accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Even without in-manifold constraints, all prior fully accelerated works require their iterates to remain in some specified compact set (which is needed in worst-case analyses due a lower bound), while only two previous methods are able to enforce this condition and these, in contrast, have limited applicability, e.g., to local optimization or to spaces of constant curvature. Our results solve an open question in [KY22] and an another question related one posed [ZS16]. In our solution, we show we can use projected Riemannian gradient descent to implement inexact proximal point operator that we use as a subroutine, which of independent interest.
11
13
Introduction
14
Riemannian optimization concerns the optimization of a function defined over Riemannian manifold. is motivated by constrained problems that can be naturally expressed on Riemannian manifolds allowing to exploit the geometric structure of the problem and effectively transforming it into an unconstrained one. Moreover, there are problems that are not convex in the Euclidean setting, but that when posed as problems every geodesic, and this allows for fast optimization [Cru+06; CM12; BFO15; All+18 18]. That is, they geodesically convex (g-convex) problems, ef. Definition 1.1. Some applications of Riemannian optimization in machine learning include low-rank matrix completion [CA16; HS18; MS14; Tan+ 14; Van13), dictionary learning [CS17; SQW17], optimization under orthogonality constraints (EAS98; LM19], robust covariance estimation in Gaussian distributions [Wie 12], Gaussian mixture models [HS15], operator scaling [All+18], and sparse principal component analysis [GHT15; HW19b; JTU03J.
16
18
manifold with the right metric, convex when restricted to
20
21
22
23
24
25
28
Riemannian optimization, whether under g-convexity not, is extensive and active of research, for which one aspires to develop Riemannian optimization algorithms that share analogous properties the more broadly studied Euclidean first-order methods, such as the following kinds of Riemannian methods: deterministic [BFM17; 1ei+16; 2J,6), adaptive [KJM19], projection-free [WS17; WS19], saddle-point-escaping [CB19; SFF19; ZZS18; ZYF19; CB20], stochastic [HS17;
28
30
31
Moos of the notations this work have a link to their definitions. For example, if you click or tap on any instance of L, you will jump to the place where it is defined as the smoothness constant of the function we consider in this work.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

32
min-max KL17; 1ri+18], variance-reduced [SKM17; SKM19; ZRS16], and min max methods [ZZS22], among others.
33
34
Riemannian generalizations to accelerated convex optimization are appealing due to their better convergence rates with respect to unaccelerated methods, specially in ill-conditioned problems. Acceleration in Euclidean convex optimization is a concept that has been broadly explored and has provided many different fast algorithms. A paradigmatic example is Nesterov's Accelerated Gradient Descent (AGD), cf. [Nes83], which can be considered the first general accelerated method, where the conjugate gradients method can be seen as an accelerated predecessor in a more limited scope [Mar21]. There have been recent efforts to better understand this phenomenon in the Euclidean case [A017; 6BC16; DT14; WWJ16; DO19; Jou+20J, which have yielded some fruitful techniques for the general development of methods and analyses. These techniques have allowed for a considerable number of new results going beyond the standard oracle model, convexity, or beyond first-order, in wide variety of settings ITss008 BT09; WRM16; A015; A1117; A1I+16; Al118;; Car+17; DO18; Alll 8a; CDO18; HSS19; 9S19; DJ19; Gas+19; Iva+21; DN20; KG20; CMP21J, among many others. There have been some efforts to achieve acceleration for Riemannian algorithms as generalizations of
35
36
37
38
39
40
41
42
43
44
45
46
47
AGD, cf. Section 1.3. These works try to answer the following fundamental question:
Can a Riemannian first-order method enjoy the same rates of convergence as Euclidean AGD? 48
The question is posed under (possibly strongly) geodesic convexity and smoothness of the function to 50 be optimized. And we now know, due to the lower bound in [CB21]. that the optimization should be over a bounded domain and under bounded geodesic curvature of the Riemannian manifold. In this 51
49
52 work, we study this question in the case of Hadamard manifolds M of bounded sectional curvature,
53 where many of the applications lie [HS20]. Given a compact and uniquely geodesic g- g-convex set X'
54 that we access to via a metric- projeiciooootiionn oracle, we design first-order algorithms that enjoy the same
55 rates as AGD when approximating minzex fx)), up to logarithmic factors and up to geometric penalty factor, where : C M + is a differentiable function that is smooth and g-couvex (or strongly g-convex) in X' C N. See Section 1.1 for the definitions of these concepts. Importantly, our algorithm obtains acceleration without an undesirable assumption that most previous works had to made: that the iterates of the algorithm stay inside of a specified compact set without any mechanism for enforcing this condition. Only two previous methods are able to deal with some form of constraints, and they apply to the limited settings of constant sectional curvature manifolds and local optimization, respectively. Techniques in the rest of papers can handle neither constraints nor projections, due to fundamental properties of their methods. Removing this condition in general, global, and fully accelerated methods was posed as an open question in [K Y22), that we solve for the case of Hadamard manifolds. The difficulty of constraining problems in order to bound geometric penalties as well as the necessity of achieving this goal in order to provide full optimization guarantees something that has also been noted in other kinds of Riemannian algorithms, ef. [HS20). See Table I for a succint comparison among algorithms with some degree of acceleration and their rates.
56
58
59
60
61
62
64
66
67
68
The question concerning whether there are Riemannian analogs to Nesterov's algorithm that enjoy similar rates is a question that, to the best of our knowledge, was first formulated in [ZS16] 16]. In particular, since Nesterov's 's AGD uses proximal operator of function's ' linearization, they ask 72 whether there is a Riemannian analog to this operation that could be used to obtain accelerated rates in the Riemannian case. The natural candidate results in non-convex problem which is not amenable
70
71
74 to optimization. While we do not take this course of action, we show that, instead, a proximal step
75 with respect the whole function can be approximated efficiently in Hadamard manifolds and can be used along with an accelerated outer loop, when implemented and analyzed carefully, in the spirit of other Euclidean algorithms like Catalyst [LMH17]. It relies on Riemannian gradient descent (RGD) with projections, initialized at suitable warm-start point that we can find by exploiting the structure of the geometry and the metric projection. The Riemannian proximal point subroutine
76
77
78
79
we design is of independent interest. To the best of our knowledge, previously known Riemannian proximal methods either obtain asymptotic analyses, assume exact proximal computation, or work
80
81
82 with approximate proximal operators by using different inexactness conditions as ours, and do not
83
show how implement the inexact operators, cf. Section 1.3.
84
1.1 Preliminaries
85 We provide definitions of Riemannian geometry concepts that we use this work. The interested
86 reader can refer to [Pet06; Bac14] for an in-depth review of this topic, but for this work the following

---

87 notions will be enough. A Riemannian manifold (M, g) is a real C manifold M equipped with 86 a metric g, which is a smoothly varying, i.e. C inner product. For x E MM, denote by T,M the tangent space of M at x. For vectors v, w. E TT,M, we denote the inner product of the metric by 90 (u, w)x and the norm it induces by ||u||a det v (w, v)2. Most of the time, the point æ is known from context, in which case we write (v, w) or |||]].
89
81
92 A geodesic of length É is curve 7: [0, + M of unit speed that is locally distance minimizing.
93 A uniquely geodesic space is a space such that for every two points there is one and only one geodesic that joins them. In such case the exponential map Exp,, TzM .M and the inverse exponential map Log, -M- + T.M are well defined for every pair of points, and are as follows. Given y E M, U E M,,,, and geodesic ? of length |||=]| such that >(0) x. >(Ilel) (0) = w/|loll. we have that (v) = and Log.. (v) = u. We denote by d(x y) the distance between and y, and note that it takes the same value as Log, (v)ll. The manifold M comes with natural parallel transport between vectors in different tangent spaces, that formally is defined from a
94
95
y-
97
99
100
way of identifying nearby tangent spaces, known as the Levi-Civita connection V [Lev77]. We use this parallel transport throughout this work.
101
102
Given 2- 2-dimensional subspace V C TyM of the tangent space of point z, the sectional curvature at Z with respect to V is defined as the Gauss curvature, for the surface Exp,, (V) at x. The Gauss curvature at point x can be defined as the product of the maximum and minimum curvatures of the curves resulting from intersecting the surface with planes that are normal to the surface at x. A Hadamard manifold is complete simply connected Riemannian manifold whose sectional curvature is non- non-positivee like the hyperbolic space or the space of n X n symmetric positive definite matrices with the metric (X, A def Tr(A-1X YY) where X, Y are in the tangent space of A. Hadamard manifolds are uniquely geodesic. Note that in a general manifold Exp, (-) might not be defined for each & E M, but in Hadamard manifold of dimension the exponential map at any point is global diffeomorphism between T.M = R" and the manifold, and so the exponential map is defined everywhere. We now proceed to define the main properties that will be assumed on our model for the function to be minimized and on the feasible set X.
103
105
106
107
108
109
111
112
113
Definition 1.1 (Geodesic Convexity and Smoothness). Let f : N CM- + R be a differentiable function defined on an open set N contained in a Riemannian manifold M. Given L 2 p > O, we
115
116
say that f is L-smooth in X if for any two points 2, y E X, f satisfies
L
fly) S f(x) + (V)(z), Log. (v))
d(z, y)
2
117
Analogously, we say that f is μ p-strongly g-conver in X, if for any two points v. E X, we have
f()) 2 (x) + (og + 4 ddd,,))
118
If the previous inequality is satisfied with O, we say the function is g-convex in X. Definition 1.2 (Metric projection operator). Let M be a Hadamard manifold and let X M be a closed g-convex subset of M. A metric projection operator onto X' is a map Px : M + X satisfying d(xr, (x)) S d(x;, y) for all y E X.
119
120
121
122 A consequence of the definition is that the projection is single valued and non non-expansive, the latter meaning (x), (x(()))) & d(x, v), cf. [Bac14, Thm 2.1.
123
124 We present the following fact about the squared distance function, when one of the arguments is fixed. The constants (D. ōn below appear everywhere in Riemannian optimization because, among other things, Fact 1.3 yields Riemannian inequalities that are analogous to the equality in the Euclidean cosine law of a triangle, ef. Corollary B.3, and these inequalities have wide applicability in the analyses of Riemannian methods.
125
126
127
128
sec- Fact 1.3 (Local information of the squared distance). Let M be a Riemannian manifold of sec- tional curvature bounded by [Kiin kmax] that contains a uniquely g-convex set X C M of diameter
130
D co. Then, given x, y E X we have the following for the function tz : -M- - R, y >> _d(a, u)
131
vΦ = - Log, (x)
and
8dllie|2 < Hess & (w)[u, o) S <n||o||3
132 where
D DD M coth(D (1Kmmnl) if < 0
<D def
1
if > 0
3

---

133 and
1
if Kimxx S 50
8D def
D FTmax cot D (OoDDD/Fmooe Fmaax)
if Kmmxx > 0
134
In particular, Da is å D-strongly g-convex and (D ED-smooth in X. See [Lez20] for proof.
135
1.2
Notation.
136
Let M be uniquely geodesic n-dimensional Riemannian manifold. Given points 2, y, E M, we abuse the notation and write y in non- -aniiuugu and well-defined contexts in which we should
137
138
write Log. (y). For example, for
T.M we have (u. y x) (U. y) (v. Log (v) Log, (z)) = {u, (y);; || yll = || Log, (y)ll: 1| - | Log Log, (v)ll; and
139
lyy - -||-- = Tog., (v) = d(y, x). We denote by X' a compact, uniquely geodesic g-convex set of
140
diameter D contained in an open set C M and we use 1x for the indicator function of X, which
142
at points in X' and too otherwise. For a vector v E T,,,, we use (v) E T.-M to denote the parallel transport of y from M to T.MM along the unique geodesic that connects y to z. We call
143
144 f N M + R a differentiable L-smooth g-convex function we want to optimize over X. We use
E to denote the approximation accuracy parameter, Tu E X for the initial point of our algorithms, and
146 R del 2(=)==") for the initial distance to an arbitrary minimizer x² E arg min f(x) The big
147 O notation (-) omits log factors and (-) omits log factors except those with respect to LR /. The latter will be useful to describe the rates of convergence for the strongly g g-convex case, by emphasizing that there is no extra dependence on E. Note that in the setting of Hadamard manifolds, the bounds on the sectional curvature are Kimin I Kmax I 0. Hence for convenience, given that we der <D= = D coth D DV //mmmlll) 2 and 5 def 1. If M, we use II () E T for the projection of v onto the closed ball with center at 0 and radius D.
148
149
150
151
optimize over X, we define Ç
152
153
1.3
Our results and comparisons with related work
154 In this work, we optimize functions defined over Hadamard manifolds M of finite dimension n and of sectional curvature bounded in [Kmin Km As all previous related works discussed in the sequel, we assume that we can compute the exponential and inverse exponential maps, and parallel transport of vectors for our manifold. The differentiable function f to be optimized defined over an open set N C .M that contains a compact g-convex set X' of finite diameter D, that we access via a metrii-projeccton oracle. Our function f is L-smooth and g-convex (or p-strongly g-convex) in X and we have access to it via gradient oracle that can be queried at points in X. For the setting we just described, we show in Theorem 2.2 and Theorem 2.4 that the algorithms we propose find a point yr E X such that f(r) min (x) S after calling the gradient oracle and the metric- projeic-pooecttion oracle the following number of times: V(s2VLRR
155
156
157
158
159
161
162
163
for the g-convex case and O (c² /L/ Rog( [)) for the p-strongly g- g-convex case, where Rg def d(zg..") x²) and To E X' is an initial point. That is, the algorithms enjoy the same rates as AGD in the Euclidean space up to a factor of 22 D2 x2 Ri coth² /1 I) (our geometric penalty) and up to universal constants and log factors. Note that as the minimum curvature Kmin approaches O we have Ç ++1.
184
165
186
167
168
We emphasize that our algorithms only need to query the gradient of f at points in X' and the L-smoothness and p-strong g-convexity of f only need to hold in X. This is relevant because in Riemannian manifolds the condition number L/μ μ in a set can increase with the size of the set, cf. MMr222, Proposition 27]. Intuitively, although there are twice differentiable functions defined over the
169
170
171
172
Euclidean space whose Hessian constant everywhere, in other Riemannian cases the metric may preclude having such global condition and the larger the (compact) set is, the greater the maximum eigenvalue of the Hessian over this set (i.c., its smoothness constant) can be for any smooth and strongly g-convex function. And similarly with the minimum one, i.e., its strong g-convexity constant.
173
174
175
176
Compare this, for instance, with the bounds on the Hessian's 's eigenvalues of the squared distance function in Fact 1.3, which are tight for spaces of constant curvature [Lez20].
177
178
Now we proceed to compare our results with previous works. We have summarized most of the following discussion in Table 1. We include Nesterov's 's AGD in the table for comparison purposes
179
Note that the original method in [Nes83] needed to query the gradient of the function outside of the feasible set, and this was later improved to only require queries at feasible points [Nes05] as in our work, hence our choice of citation in the table.

---

180
There are some works on Riemannian acceleration that focus on empirical evaluation or that work under strong assumptions [Liu+17; 11i+19; HW19a; Ali+20; Lin+20], see [Mar22] for instance for a discussion on these works. We focus the discussion on the most related work with guarantees. [7S18] obtain an algorithm that, up to constants, achieves the same rates as AGD in the Euclidean space, for T-smooth and j--ttrongy g-convex functions but only locally, namely when the initial
181
182
183
184
point starts in small neighborhood N of the minimizer x": a ball of radius ((H/L)) around it. [AS20] generalize the previous algorithm and, by using similar ideas as in [ZS18] for estimating a
185
186
187
lower bound on f. they adapt the algorithm to work globally, proving that it eventually decreases the objective as fast as AGD. However, as [Mar22] noted, it takes as many iterations as the ones needed by RGD to reach the neighborhood of the previous algorithm. The latter work also noted that in fact RGD and the algorithm in [ZS18] can be run parallel and combined to obtain the same convergence rates as in [AS20], which suggested that for this technique, full acceleration with the rates of AGD only happens over the small neighborhood N in [ZS18]. Note however that [AS20] show that their algorithm will decrease the function value faster than RGD, but this is not quantified. [JS21] developed a different framework, arising from [AS20] but with the same guarantees for accelerated fidst-order methods. We do not feature it in the table. [CB21] showed that in ball of center
188
189
190
192
194
195
M and radius ((1/L) 1/3) containing x", the pullback function f o Exp,- T.M - R is strongly convex and smooth with condition number O(L/p),
196
they argue that using AGD on the pullback over the corresponding pulled-back Fuclidean ball in the tangent space results in local acceleration as well. In short, acceleration is possible in small neighborhood because there the manifold is almost Fuclidean and the geometric deformations are small in comparison to the curvature of the objective. These techniques do not work with the g-convex case since the neighborhood becomes a
198
199
200
201
202
point (μ/L 0).
Finding fully accelerated algorithms that are global presents a harder challenge. By a fully accelerated algorithm we mean one with rates with same dependence as AGD on L, E, and it applies, on p. [Mar22] provided such algorithms for g-convex functions, strongly or not, defined over manifolds of constant sectional curvature and constrained to a ball of radius R. In the convergence rates, there is a geometric factor of c = cos(RVK) RRV)) (RK))-(()) -(()) for sectional curvature K > 0, and c cosh( (RV-K)(())
204
206
207
when K < 0, cf. Table 1. When R R O(1), they recover the same rates as AGD, which for those manifolds is more general than the local assumption in the previous set of works. For larger values of / []. there is also full acceleration, but note that grows rapidly when K < O, since there is an exponential dependence on R. When K > O the geometric penalty also grows fast, but this is more natural since the minimum condition number of function in a ball of radius R grows similarly [Mar22]. The geometric penalties are large in some regimes because the algorithm bounds uniformly, over the whole domain, the worst-case deformations that can occur. On the other hand, for manifolds of bounded sectional curvature, [K [22 design algorithms with the same rates as AGD up to universal constants and a factor of C, their geometric penalty. However, they need to assume that the iterates of their algorithm remain in X' and point out on the necessity of removing such an assumption, which they leave as an open question. Our work solves this question for the case of Hadamard manifolds. In their technique, they show that they can use the structure of the accelerated scheme to move lower bound estimations on f(x") from one particular tangent space to another without incurring extra errors, when the right Lyapunov function is used. By moving lower bounds here we mean finding suitable lower bounds that are simple (a quadratic in their case), if pulled- -bak 222
208
209
210
211
212
213
214
216
217
218
220
to one tangent space, if we start with a similar bound that is simple when malled-back to another tangent space.
224
225
Lower bounds. In this paragraph, we omit constants depending on the curvature bounds in the big-O notations for simplicity. [HM21] proved an optimization lower bound showing that acceleration in Riemannian manifolds is harder than in the Euclidean space. [CB21] largely generalized their results. They essentially show that for a large family of Hadamard manifolds, there is a function that is smooth and strongly g-convex in a ball of radius It that contains the minimizer x², and for which finding a point that is R/5 close to x² requires (2(R)) calls to the gradient oracle. Note that these results do not preclude the existence of a fully accelerated algorithm with rates Ö(R)+AGD rates, for instance. But they show that even we want to perform unconstrained optimization, so no in-manifold constraints are originally imposed, we need to optimize over bounded domain in order to bound geometric penalties. A similar statement is provided in the case of smooth and only g-convex functions.
226
227
229
230
231
232
234
5

---

Table 1: Convergence rates of related works with provable guarantees for smooth problems over uniquely geodesic manifolds, in chronological order with respect to when the works were publicly available. Column K? refers to the supported values of the sectional curvature, G? to whether the algorithm global (any initial distance to minimizer is allowed). Here L. and L' mean they are local respectively. Column F?
algorithms that require initial distance D((L/p) ///)) and (((L/)) refers to whether there is full acceleration, meaning dependence on L, μr. and E like AGD up to possibly log factors. Column C? refers whether the method supports constraints. All methods require their iterates to be in some specified compact set, but the works with X just assume the iterates will remain within the constraints, while the ones with / can force this condition with a projection oracle. Also, here B is like // but with the constraints limited to ball. See Section 1.3 for the value
e in [Mar22]. We use W def V log( LR "In [CB21], a condition is required on the covariant
derivative of the metric tensor, cf. [CB21, Section 6].
Method
g-convex
p-st. g-covex
K?
G?
F?
C?
[Nes05, AGD]
((v
LI
O(W)
0
/
/
V
[7S18, Theorem 11]
O(W)
bounded
I
/
[AS20, Theorem 3.1]
O-(L + +W)
bounded
/
[Mar22, Remark 30)
0r +W)
E
bounded
/
x
X
[Mar22, Theorems 6 & 8]
Ölev
LNG
O'(c. W)
ctant,ş 0
B
[CB21, Section 6]
O(W)
bounded"
I.'
/
B
[KY22, Corollaries 1 & 2]
V
LRK.
0(5-W)
bounded
V
/
X
Theorems 2.2 & 2.4
Ōl5² LRG
Or((3.
Hadamard
/
V
296
Handling constraints to bound geometric penalties. Due to the lower bounds, it becomes crucial for a fully accelerated algorithm restrict the optimization to a set X' of finite diameter D, or otherwise a worst-case analysis incurs an arbitrary large geometric penalty in the rates. In our algorithm and in all other known fully accelerated algorithms, learning rates depend on this diameter. This is natural: estimation errors due to geometric deformations depend on the diameter via the constants ÇD. dD. the cosine-law inequalities Corollary B.3, or other analogous inequalities, and the algorithms take these errors into account. All other previous works are not able to deal with any constraints and hence they simply assume that the iterates of their algorithms stay within one such specified set, except for [Mar22] and [CB21] that enforce a ball constraint, as we explained above. However, these two works have their applicability limited to spaces of constant curvature and to local optimization, respectively. Note that even if one could show in some settings that given a choice of learning rate, convergence implies that the iterates will remain in some compact set, then because the learning rates depend on the diameter of the set, and the diameter of the set would depend on the learning rates, one cannot conclude from this argument that the assumption these works make going to be satisfied. In contrast, in this work, metric projections and, consequently, we can handle general constraints to bound geometric penalties and accelerate method without any other extra assumptions, solving an open question in [KY22]
237
238
239
240
241
242
243
244
245
246
247
249
design the first accelerated algorithm that supports
251
253
Some other works study and use Riemannian metric projections in other contexts, see [Wal74; HP13; BHP13; Bac14; ZS16] and references therein. Among them, [ZS16] introduced several, both deterministic and stochastic, unaccelerated first-order methods that work with in-manifold constraints by using metric-projection oracles. Our Algorithm uses their projected RGD subroutine, cf. Remark 2.3.
254
255
257
258
Finding a global minimizer. In our work, we do not need to assume that the set X' contains a global minimizer, namely point x such that V f==")= O. We find an e-minimizer with respect to the minimum value of f at X. All other previous works assume that the set contains the minimizers of f. with the exception of [Mar22], where the algorithm
260
forgo this assumption if one has access to a bound L on the Lipschitz constant of f when restricted to their ball constraint B, and 262
263 in such a case the rates have a log( f. D/e)) factor instead of a log(L.D, /e) factor. Note this is natural since if a global minimizer is in the set, then we have L O(DD). We note that also

---

285
obtain a logarithmic dependence that involves the Lipschitz constant , of f in X (the logarithmic
266
dependence involves the scale invariant quantity {c for C' ,,,x L, which is O(5) if x E X) but in contrast in our case, our method does not require access to the Lipschitz constant of f in X.
Riemannian proximal methods There have been some works that study proximal methods in Riemannian manifolds, but most of them focus on asymptotic results or assume the proximal operator can be computed exactly [Wan+15; BFM17; BCO16; Kha+21; Cha+21]. The rest of these works study proximal point methods under different inexact versions of the proximal operator as ours and
269
270
271
272
they do not show how implement their inexact version in applications, like our case of smooth and g-coveex optimization. [AK14] provide a convergence analysis of an inexact proximal point method but when applied optimization they assume the computation of the proximal operator is exact. [TH14] uses a different inexact condition and proves linear convergence, under growth condition on f. [Wan+16] 16] obtains linear convergence of an inexact proximal point method under a different
273
274
275
278
277
growth assumption on f and under an absolute error condition on the proximal function.
2
Algorithm and Pseudocode
279
In this section, we present our Riemannian accelerated algorithm for constrained g-convex optimiza- tion, or Riemacon Recall our abuse of notation for points .M to mean Log, (p) in contexts in 281 which one should place a vector in T and note that in our algorithm 2g and ys are points in M whereas 2/ E Ta M, 2k 2k E Ty M.
Algorithm 1 Riemacon: Riemannian Acceleration Constrained g-Convex Optimization
Input:
Initial point zo E X C C. Diff. function f:W C. .M- + R for a Hadamard manifold M that is L-smooth and g-convex in X, final iteration T (not required to be known in advance).
Parameters:
Geometric penalty & def 4(2n - 3 < 86 - 3 0()).
Implicit Gradient Descent learning rate A def L2D/L.
Mirror Descent learning rates 7)2- = a,//.
Proportionality constant in the proximal subproblem accuracies: 4 (1+1)"
Definition:
(computation of this value is not needed)
def A, ) where y def arg min yex (f(y) + 1 d(
Prox. accuracies: Ok
78A
1: yo Io: Ag 200AE
2: 20
2o + 0 T2,M;
20
3o
+ 20
vo + + M
3: for k to do
4: 0g + 21 k+325
A + ON/E + A Ap- = Ein 0 + An = A A(k+1+644) + 200
5:
58
6:
2x + EXP ye-1 (
ag - My-- +
-k-
A Az_1t 1 = Expy
2k
-b--1
o Coupling
7:
2t + hht
vu-1 (=k-1 + Logz, (y:-1) Logg, (Expyn 20
(2
8:
yk f oh minimizer of the proximal problem m {f()) + Logz, (yx)/A
d(I y) (cf. Remark 2.3). Approximate subgradient o Mirror Descent step Moving the dual point to T M o Easy projection done so the dual point is not very far
1
2x
9:
U
10:
V + Ny (2 )++t+ + Logm (I+) + I((O,))
+ = on
11:
UN
12:
=
UE
M
13:
end for
14:
return yr.
283 We start with an interpretation of our algorithm that helps understanding high-level ideas. The fol-
284
lowing intends to be qualitative explanation, and we refer to the pseudocode and the supplementary material for the exact descriptions and analysis. Euclidean accelerated algorithms can be interpreted,
285
286
cf. [AO17], as combination of a gradient descent (GD) algorithm and an online learning algorithm
Riemaconn rhymes with "rima con" in Spanish.
7

---

with losses being the affine lower bounds f(xx) + (Vf(z)), (- zx) we obtain on f(-) by applying convexity at some points zg. That is, the latter builds a lower bound estimation on f. By selecting the next query to the gradient oracle as a cleverly picked convex combination of the predictions given by these two algorithms, one can show that the instantaneous regret of the online learning algorithm can be compensated by the local progress GD makes, which leads to accelerated convergence. In Riemannian optimization, there are two main obstacles. Firstly, the first-order approximation of at point yields functions that are affine but only with respect to its respective T,M, and so combining these lower bounds that are only simple in their tangent spaces makes obtaining good global estimations not simple. Secondly, when one obtains such global estimations, then one naturally incurs an instantaneous regret that is worse by a factor than is usual in Euclidean acceleration. This factor is a geometric constant depending
287
286
280
291
292
294
296
the diameter D of a set X' where the iterates and (possibly constrained) minimizer lie. As a consequence, the learning rate of GD would need to be multiplicatively increased by such constant with respect to the one of the online learning algorithm in order for the regret to still be compensated with the local progress of GD (and the rates worsen by this constant). But if we fix some X' of finite diameter, because GD's learning rate is now larger, it is not clear how to keep the iterates in X. And if we do not have the iterates in one such set X,, then our geometric penalties could grow arbitrarily.
298
289
300
302
303
304
We find the answer in implicit methods. An implicit Euclidean (sub)gradient descent step is one that computes, from point F E X, another point y/: = 2g Xty E X. where 2/ E O(f + Ixx) [yt)
(yt),,nnn is subgradient of f + 1x at y6- Intuitively, if we could implement a Riemannian version of an implicit GD step then it should be possible to still compensate the regret of the other algorithm and keep all the iterates in the set X. Computing such an implicit step is computationally hard in general, but we show
306
308
that approximating the proximal objective hax ((v) + 2x ((( 3)²² with enough accuracy yields an approximate subgradient that can be used to obtain an accelerated algorithm as well. In particular, we provide an accelerated scheme for which we show that the error incurred by the approximation of the subgradient can be bounded by some terms we can control, cf. Lemma A.2, namely a small term that appears in our Lyapunov function and also term proportional to the squared norm of the approximated subgradient, which only adds a constant to the final convergence rates. We also provide warm start in Lemma A.4 and an analysis that shows that using the projected Riemannian gradient descent in [ZS18] 18) initialized at the warm start point achieves the desired accuracy of the subproblem fast, cf. Remark 2.3. This proximal approach works by exploiting the fact that the Riemannian Moreau envelop is convex in Hadamard manifolds [AF05] and that the subproblem h2, defined with
310
312
314
316
318
319
our À /nn/L, is strongly g-convex and smooth with a condition number that only depends on the geometry. Besides of these steps, we use a coupling of the approximate implicit RGD and of a mirror descent (MD) algorithm, along with technique in [K Y22] to move dual points to the right tangent spaces without incurring extra geometric penalties, that we adapt to work with dual projections. cf. Lemma A.3. Importantly, the MD algorithm keeps the dual point close to the set X' by using the projection in Line 12, which implies that the point Tg is close to X' as well, and this is crucial to
320
321
322
328
324
325
keep low geometric penalties. This MD approach is mix between sellow-therrgullarized- algorithms, that do not project the dual variable, and pure mirror descent algorithms that always project the dual variable. In the analysis, we note that partial projection also works, meaning that defining new dual point that is closer to all of the points in the feasible set but without being full projection leads to the same guarantees. Because we use the mirror descent lemma over TyMM, M, what
326
327
328
329
we described translates to: we can project the dual z onto a ball defined on - that contains the pulled- -ucked-back set Logg,, (X') and by means of that trick we can keep the iterates Tg. close to X. And at the same time, the point for which we prove guarantees, namely yk. is always in X.
331
332
333
We leave the proof' of most of our results the supplementary material and state our main theorems below. Using the insights explained above, we show the following inequality on tha defined below, that will be used as a Lypapunov function to prove the convergence rates of Algorithm 1.
334
335
338
Proposition 2.1. [1] By using the notation of Algorithm 1, let
E 6-1 1
1/2 Ax(f(vn) f(x*)) + 2 -
xx x2'13_
+
11yl
2/
1/111 11
2
337
Then, for all k 2 1, we have (1 - Awrr < 1.
Finally, we can state our theorem for the optimization of L-smooth and g-convex functions.
339 Theorem 2.2. Let M be a fimtee-dimensional Hadamard manifold of bounded sectional curvature, let f : NNC c M + R be an L-smooth and g g-convex differentiable function in a compact g- g-convex
8

---

set X C N of diameter D, and x² E arg minzex [(x). For Ro d(xoo x²); and all k 2 1, LR 342 the iterates Vv: of Algorithm I satisfy yu E X and f(y)) f(x²) - o x=a
(7). That is, after
343
iterations we find an e-minimizer. Moreover, the total number of queries to the gradient and projection oracles can be bounded by Ö(c²V
T = OlCV
LRa E
LR
344
345
We note that a straightforward corollary from our results is that if we can compute the exact Rie- mannian proximal point operator and we use it as the implicit gradient descent step in Line 8 of
346
347
A Algorithm I, then the method is an accelerated proximal point method. One such Riemannian
348
algorithm was previously unknown in the literature as well.
349
Now we show that Line 8 can be implemented efficiently. The essential part is being able to have and use point with the guarantees of our warm start, cf. Lemma A.4.
350
351
Remark 2.3 (Solving the subproblems). Let A be the unaccelerated Riemannian gradient descent algorithm in [ZS16, Theorem 15J. This algorithu takes function h M - R with minimizer at y when restricted to X C M that is yl utrotoynyyy 8-convex and I -smooth in X, where M is a Hadamard manifold of bounded sectional curvature and X is geodesically
352
353
compact set with diameter D and returns a point Pt satisfying (px) hyyyy) S E' after querying a gradient oracle for hy and (x++())))++ 'dpp.. )2 times?. a prrjic-projection oracle Px for X for 1. = O((s + "/' })gg (he(po))huly" +)
355
356
357 If we apply this algorithm to + h2 (y) def
= f(y) + 2x x( y)² we have y" + yie L' + 2L and oe t L//2D. so the condition number is L'/p' O((D)) = O(). This computed taking into 358
359
account that f is L-smooth and O-strongly g-convex and using the C2D/ />-mmoothness and 1/ //S-strong g- y-ooveiiity of the second summand, which is given by Fact 1.3 and (1). If initialize the method with
360
Po det Px (Exp,;, (- L. Whg (1rk))) where r't del Px((x)) then using (L/(2n)-strong g- g-convexity of b& to bound T' T'd(po, )² & 4G2D (ha(()))))))))) h(y?),, using Lemma A.4 with t- Fgg p <- yi and 362
361
using the guarantees on A, we have that find a point yv satisfying h& (yw) h4 (vt) I A
78A
364 in Õ()) queries to the gradient and projection oracles. See Remark A.5 for the computation of this value. We note that any other algorithm with linear convergence rates for constrained strongly g-convex, smooth problems that works with a metric-projection oracle can be used as a subroutine to obtain an accelerated Riemannian algorithm.
366
367
366
We introduce the algorithm for y-strongly g-convex functions via a reduction to Algorithm 1, for simplicity. We note that the reverse Riemannian reduction yields extra factors in the rates depending on Rg and the curvature, but this reduction does not yield any extra factors in the rates and it actually is slightly better than the usual convergence that is obtained when one analyzes these kinds of accelerated algorithms directly, by having a μ factor instead of L inside of the logarithm.
370
372
Theorem 2.4. [4] Under the same assumptions as in Theorem 2.2, let now f be p-strongly g-covexx. Applying the reduction in [Mar22, Theorem 7J, we obtain an algorithm that finds an e-minimizer of by querying the gradient oracle and projection oracle O O'(s² v log( (Ra) times.
374
375
3
Conclusion and future directions
377
In this work, we pursued an approach that, by designing inexact Riemannian proximal methods, yielded accelerated optimization algorithms that can work with metric projection oracles. Conse- quently we were able to work without an undesirable assumption that most previous methods required, whose potential satisfiability is not clear: that the iterates stay in certain specified geodesically
378
379
381
set without enforcing them to be in the set. A future direction of research is the study of whether there are algorithms like ours that incur even lower geometric penalties or that do not ineur log(1/e) factors. Another interesting direction consists of studying generalizations of our approach to manifolds of
382
383
384
negatiee or of bounded sectional cuvature manifolds.
'In their theorem, the authors only stated that O( + () log( 422²)) queries to the gradient oracle are enough, but in their proof they show this more refined statement, that we use.

---

References
385
386
[AFOS]
Daniel Azagra and Juan Ferrera. "Inf-convolution and regularization of convex functions on Riemannian manifolds of nonpositive curvature". In: arXiv preprint math/0505496 (2005) (cit. on p. 8).
387
388
389
[AK14]
P Ahmadi and H Khatibzadeh. "On the convergence of inexact proximal point algorithm on Hadamard manifolds". In: Taiwanese Journal of Mathematics 18.2 (2014), pp. 419-
391
433 (cit. on p. 7).
392
[Ali+19]
Foivos Alimisis. Antonio Orvieto, Gary Bécigneul, and Aurelien Lucchi. "A Continuous- time Perspective for Modeling Acceleration in Riemannian Optimization". In: arXiv preprint arXiv:1910. 10782 (2019) (cit. on 5.).
393
394
[Ali+20]
Foivos Alimisis, Antonio Orvieto, Gary Bécigneul, and Aurelien Lucchi. "Practical Ac- celerated Optimization on Riemannian Manifolds". In: arXiv preprint arXiv:2002.04144 (2020) (cit. on p. 5).
396
398
[6]++16]
Zeyuan Allen Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. "Even Faster Acceler- ated Coordinate Descent Using Non-Uniform Sampling". . In: Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. 2016, pp. 1110-1119 (cit. on p. 2).
389
400
401
[AII+18]
Zeyuan Allen-Zhu, Ankit Garg, Yuanzhi Li, Rafael Oliveira, and Avi Wigderson. "Op- erator scaling via geodesically convex optimization, invariant theory and polynomial identity testing". In: Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing. 2018, pp. 172-181 (cit. on p. I).
403
405
406
[A111]]
Zeyuan Allen-Zhu. "Katyusha: The First Direct Acceleration of Stochastic Gradient Methods". In: J. Mach. Learn. Res. 18 (2017),
407
(cit. on p. 2).
408
[All18a]
Zeyuan Allen-Zhu. "Katyusha X: Practical Momentum Method for Stochastic Sum-of- Nonconvex Optimization", In: Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 15, 2018. 2018, pp. 179-185 (cit. p. 2).
409
410
[Al118b]
Zeyuan Allen-Zhu. "Natasha 2: Faster Non-Convex Optimization Than SGD". In: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018, Montréal, Canada. 2018, pp. 2680-2691 (cit. on p. 2).
413
415
418
[AO15]
Zeyuan Allen Zhu and Lorenzo Orecchia. "Nearly-Linews Time Positive LP Solver with Faster Convergence Rate". In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015.
417
418
419
2015, pp. 229-22222 2-6 (cit. on p. 2).
420
[A017]
Zeyuan Allen Zhu and Lorenzo Orecchia. "Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent", In: 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 1, 2017, Berkeley, CA, USA. 2017, 3:1-3:22 (cit. on pp. 2p. 7).
422
424
[AS20]
Kwangjun Ahn and Suvrit Sra. "From Nesterov's Estimate Sequence to Riemannian Acceleration". In: arXiv preprint arXiv:2001.0883 (2020) (cit. on pp. 5, 6). Miroslav Bacák. "Convex analysis and optimization in Hadamard spaces". In: Convex Analysis and Optimization in Hadamard Spaces. de Gruyter, 2014 (cit. on pp. 2, 3, 6). Glaydston de Carvalho Bento, João Xavier da Cruz-Neto, and Paulo Roberto Oliveira. "A New Approach the Proximal Point Method: Convergence on General Riemannian Manifolds", In: J. Optim. Theory Appl. 168.3 3 (2016), pp. 743-755 (cit. on p. 7).
425
[Bac14]
427
428
[BC016]
429
430
[BFM17]
Glaydston de Carvalho Bento, Orizon P. Ferreira, and Jefferson G. Melo. "Iteration- Complexity of Gradient, Subgradient and Proximal Point Methods on Riemannian Manifolds". In: J. Optim. Theory Appl. 173.2 (2017), pp. 548-562 (cit. pp. 1, 7).
432
[BF015]
GC Bento, OP Ferreira, and PR Oliveira. "Proximal point method for special class of nonconvex functions on Hadamard manifolds". In: Optimization 64.2 (2015), pp. 289- 319 (cit. on p. 1).
435
436
437
[BHP13]
A Barani, S Hosseini, and MR Pouryayevali. "On the metric projection onto c-convex subsets of Hadamard manifolds". In: Revisia matemática complutense 26.2 (2013), pp. 815-826 826 (cit. on p. 6).
438
439
10

---

440
[BT09]
Amir Beck and Mare Teboulle. "A Fast Iterative Shrinkage-Trreshodding Algorithm for Linear Inverse Problems". In: SIAM J. Imaging Sci. 2.1 (2009), pp. 183-202 (cit. on p. 2).
441
442
[CA16]
Léopold Cambier and Pitrre-Antoine Absil. "Robust Low-Rank Matrix Completion by Riemannian Optimization". In: SIAM J. Scientific Computing 38.5 (2016) (cit. on p. 1). Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. ""dd.."""nnm ""Convex Until Proven Guilty": Dimension- Free Acceleration of Gradient Descent on Non-Convex Functions". In: Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. 2017, pp. 354-663 (cit. on p. 2).
444
445
[Car+17]
448
447
448
449
[CB19]
Chris Crisciticllo and Nicolas Boumal. "Efficiently escaping saddle points on manifolds". In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada. 2019, pp. 5985-5995 (cit. on p. 1).
451
453
[CB20]
Chris Criscitiello and Nicolas Boumal. " "An accelerated first-order method for non- convex optimization on manifolds". In: arXiv preprint arXiv:2008.0223 (2020) (cit. on
454
455
p. 1).
496
[CB21]
Christopher Criscitiello and Nicolas Boumal. "Negative curvature obstructs acceleration for geodesically convex optimization, even with exact first-order oracles". In: CoRR 0bs/2111.13266 (2021) (cit. on pp. 2, 5,
458
459
[CD018]
Michael Cohen, Jelena Diakonikolas, and Lorenzo Orecchia. "On Acceleration with Noise-Corrupted Gradients". In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018. 2018. pp. 1018-1027 (cit. on p. 2).
460
461
462
463
[Cha+21]
Shih-Sen Chang, Jen-Chih Yao, M Liu, and I.C. Zhao. "Inertial proximal point algorithm for variational inclusion in Hadamard manifolds". In: Applicable Analysis (2021), pp. 1- 12 (cit. on p. 7).
464
465
486
[CM12]
Glaydston de Carvalho Bento and Jefferson G. Melo. "Subgradient Method for Convex Feasibility on Riemannian Manifolds", In: J. Optim. Theory Appl. 152.3 (2012), pp. 773-
467
468
785 (cit. on p. 1).
469
[CMP21]
Francisco Criado, David Martínez-Rubio, and Sebastian Pokutta. "Fast Algorithms for Packing Proportional Fairness and its Dual". In: arXiv preprint arXiv:2109.032: (2021) (cit. on p. 2).
470
471
[Cru+06]
João Xavier da Cruz Neto, Orizon Pereira Ferreira, L. R. Lucambio Pérez, and Sándor Zoltán Németh. "Convex- and Monotone- Tornsborm Mathematical Programming Problems and a Proximal-Like Point Method". In: J. Glob. Optim. 35.1 (2006), pp. 53-
479
475
69 (cit. on p. 1).
478
[CS17]
Anoop Cherian and Suvrit Sra. "Riemannian Dictionary Learning and Sparse Coding for Positive Definite Matrices". In: IEEE Trans. Neural Networks Learn. Syst. 28.12 (2017), pp. 2859-2877 (cit. on p. 1).
477
478
[CS19]
Ashok Cutkosky and Tamás Sarlós. "Matrix-Free Preconditioning in Online Learning". In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019. Long Beach. California, USA. 2019, pp. 1455-1464 (cit. on p. 2).
480
482
[D119]
Jelena Diakonikolas and Michael I. Jordan. "Generalized Momentum-Based Methods: A Hamiltonian Perspective". In: CoRR abs/1906.004433 (2019) (cit. on p. 2).
483
[DN20]
Nikita Doikov and Yurii E. Nesterov. "Contracting Proximal Methods for Smooth Convex Optimization". In: SIAM J. Optim. 30.4 (2020), pp. 31 3146-3169 (cit. on p. 2). Jelena Diakonikolas and Lorenzo Orecchia. "Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method". In: 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 1 11-14, 2018, Cambridge, MA, USA. 2018, 23:1-23:19 (cit. on p. 2).
485
486
[D018]
488
489
490
[D019]
Jelena Diakonikolas and Lorenzo Orecchia. "The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods". In: SIAM Journal on Optimization 29.1 (2019), pp. 660-689 (cit. on p. 2).
481
492
493
[DT14]
Yoel Drori and Mare Teboulle. "Performance of first-order methods for smooth convex minimization: novel approach". In: Math. Program. 145.1-2 (2014), pp. 451 482 (cit. on p. 2).
495
11

---

496
[EAS98]
Alan Edelman, Tomás A. Arias, and Steven Thomas Smith. "The Geometry of Algo- rithms with Orthogonality Constraints". In: SIAM Matrix Analysis Applications 20.2 (1998), pp. 303-353 (cit. on p. 1).
497
498
[Gas+
Alexander Gasnikov, Pavel E. Dvurechensky, Eduard A. Gorbunov, Evgeniya A. Vorontsova, Daniil Selikhanovych, César A. Uribe, Bo Jiang, Haoyue Wang, Shuzhong Zhang, Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, Yuanzhi Li, and Aaron Sidford. "Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Deriva- tives". In: Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA. 2019. pp. 1392-1393 (cit. on p. 2).
500
502
504
505
[GHT15]
Matthieu Genicot, Wen Huang, and Nickolay T. Trendafilov. "Weakly Correlated Sparse Components with Nearly Orthonormal Loadings". In: Geometric Science of Information -Second International Conference, GSI 2015, Palaiseau, France, October 28-30, 2015, Proceedings. 2015, pp. 484-490 (cit, on p. 1).
508
507
508
509
[HM21]
Linus Hamilton and Ankur Moitra. "A No-go Theorem for Acceleration in the Hyper- bolic Plane". In: arXiv preprint arXiv:2 (eo::1001.0557 (2021) (cit. on p. 5).
510
[HP13]
Seyedehsomayehh Hosseini and Mohamad Pouryayevali. "On the metric projection onto prox-regular subsets of Riemannian manifolds". In: Proceedings of the American Mathematical Society 141.1 (2013), pp. 233-244 (cit. on p. 6).
512
[HS15]
Reshad Hosseini and Suvrit Sra. "Matrix Manifold Optimization for Gaussian Mixtures". In: Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada. 2015, pp. 910-918 (cit. on p. 1).
515
517
518
[HS17)
Reshad Hosseini and Suvrit Sra. "An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization". In: CoRR 7os/1706.03267 (2017)
519
520
(cit. on p. 1).
521
[HS18]
Gennadij Heidel and Volker Schulz. "A Riemannian trust-region method for low-rank tensor completion". In: Numerical Lin. Alg. with Applic. 25.6 (2018) (cit. on p. 1).
522
523
[HS20]
Reshad Hosseini and Suvrit Sra. "Recent advances stochastic Riemannian optimiza- tion". In: Handbook of Variational Methods for Nonlinear Geometric Data (2020),
524
525
pp. 527-554 (cit. on p. 2).
526
[HSS19]
Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni. "Near- Olear-Optimal Methods for Minimizing Star-Convex Functions and Beyond". In: CoRR abs/1996.11188 (2019) (cit. on p. 2).
528
529
[HW19a)
Wen Huang and Ke Wei. "Extending FISTA to Riemannian Optimization for Sparse PCA" In: arXiv preprint arXiv: 05485 (2019) (cit. on p. 5). Wen Huang and Ke Wei. "Riemannian Proximal Gradient Methods". In: arXiv preprint 1.Xiv:1909.004
530
531
[HW 19b]
532
(2019) (cit. on p. 1).
533
[Iva+21]
Anastasiya Ivanova, Dmitry Pasechnyuk, Dmitry Grishchenko, Egor Shulgin, Alexander V. Gasnikov, and Vladislav Matyukhin. "Adaptive Catalyst for Smooth Convex Opti- mization". In: Optimization and Applications 12th International Conference, OPTIMA 1021, Petrovac, Montenegro, September 27 - October 1, 2021, Proceedings. Fd. by Nicholas N. Olenev, Yuri G. Eytushenko, Milojica Jacimovic, Michael Yu. Khachay, and Vlasta Malkova. Vol. 13078. Lecture Notes in Computer Science Springer, 2021, pp. 20-37 (cit. on p. 2).
534
535
536
537
538
[Jou+20]
Pooria Joulani, Anant Raj, András György, and Csaba Szepesvári. "A simpler approach
541
to accelerated optimization: iterative averaging meets optimism". ". In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Vol. 119. Proceedings of Machine Learning Research. PMLR, 2020,
543
pp. 4984 (cit. on p. 2).
545
[JS21]
Jikai Jin and Suvrit Sra. "A Riemannian Accelerated Proximal Extragradient Framework and its Implications". In: CoRR abs/21 11 1.02663 (2021) (cit. on p. 5).
546
547
[TU03]
Ian T Jolliffe, Nickolay T Trendafilov, and Mudassir Uddin. "A modified principal component technique based on the LASSO". In: Journal of computational and Graphical Statistics 12.3 (2003), pp. 531-547 (cit. on p. 1).
548
549
[KG20]
Dmitry Kamzolov and Alexander Gasnikov. "Near-optimal hyperfast second-order method for convex optimization and its sliding". In: arXiv preprint arXiv:2002.000550 (2020) (cit. on p. 2).
551
12

---

553
[Kha+21]
Konrawut Khammahawong, Poom Kumam, Parin Chaipunya, and Juan Martínez- Moreno. "Tseng's 's methods for inclusion problems on Hadamard manifolds". In: Opti- mization (2021), pp. 1-35 (cit. on p. 7).
554
555
[KJM19]
Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. "Riemannian adaptive stochas- tic gradient algorithms on matrix manifolds", In: Proceedings of the 36th International Conference Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California. USA. 2019, pp. 3262-3271 (cit. on p. 1).
557
859
580
[KL17]
Masoud Badiei Khuzani and Na Li. "Stochastic Primal-Dual Method on Riemannian Manifolds of Bounded Sectional Curvature". In: 16th IEEE International Conference on Machine Learning and Applications, ICMLA 2017, Cancun, Mexico, December 18-21, 2017. 2017. pp. 133-144 (cit. on p. 2).
561
562
563
584
[Y22]]
Jungbin Kim and Insoon Yang. "Nesterov Acceleration for Riemannian Optimization".
In: arXiv preprint arXiv:2202.02000 (2022) (cit. on pp. 2, 6, 8, 22).
566
[Lev77]
Tullio Levi-Civita. The absolute differential calculus (calculus of tensors). Courier Corporation, 1977. ISBN: 978-0-486-3 322--3 (cit. on p)
587
568
[Lex20]
Mario Lezcano-Casado. "Curvature-Dependant Global Convergence Rates for Optimiza- tion on Manifolds of Bounded Geometry". In: arXiv preprint arXiv:2008.00 02511 (2020) (cit. p. 4).
569
[Lin+20]
Lizhen Lin, Bayan Saparbayeva, Michael Minyi Zhang, and David B. Dunson. "Accel- erated Algorithms for Convex and Non-Convex Optimization on Manifolds". In: CORR Abs/2010.08908 (2020) (cit. on p. 5).
572
573
574
[Liu+17]
Yuanyuan Liu, Fanhua Shang, James Cheng, Hong Cheng, and Licheng Jiao. "Ac- celerated First-order Methods for Geodesically Convex Optimization on Riemannian Manifolds". In: Advances Neural Information Processing Systems 30: Annual Confer- ence on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. Ed. by Isabelle Guyon, Ulrike von Luxburg. Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett. 2017, pp. 4868-4877 (cit. on p. 5).
575
576
577
578
580
581
[LM19]
Mario Lezcano- Casndo and David Martínez-Rubic. "Cheap Orthogonal Constraints in Neural Networks: A Simple Parametrization of the Orthogonal and Unitary Group". In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA. 2019, pp. 3794-3803 (cit. on p. 1). Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. "Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice". In: J. Mach. Learn. Res. 18 (2017), 212:1-212:54 (cit. on p. 2).
582
583
584
585
[LMH17]
587
588
[Mar21]
David Martinez-Rubio. "Acceleration in first-order optimization methods: promenading beyond convexity or smoothness, and applications". PhD thesis. University of Oxford, 2021 (cit. on p. 2).
590
581
[Mar22]
David Martinez-Rubio. "Global Riemannian Acceleration in Hyperbolic and Spherical Spaces". In: International Conference on Algorithmic Learning Theory, 29-/ April 2022, Paris, France. Ed. by Sanjoy Dasgupta and Nika Haghtalab. Vol. 167. Proceedings of Machine Learning Research. PMLR, 2022, pp. 768-826866 (cit. on pp. 4-6, 9, 21).
592
583
594
595
[MS14]
Bamdev Mishra and Rodolphe Sepulchre. "R3MC: A Riemannian fhreer algorithm for low-rank matrix completion". In: 53rd IEEE Conference on Decision and Control, CDC 2014, Los Angeles, CA, USA, December 15-17, 2014. 2014, pp. 1137-1142 (cit. on
596
597
598
p. 1).
599
[Nes05]
Yurii Nesterov. "Smooth minimization of non moo-sh functions". In: Math. Program. 103.1 (2005), pp. 127-152 (cit. on pp. 4, 6).
600
[Nes83]
Yurii Nesterov. "A method of solving a convex programming problem with convergence rate O(1/k2)". In: Soviet Mathematics Doklady. Vol. 27. 1983, pp. 372-376 (cit. on pp. 2, 4).
602
604
[Pet06]
Peter Petersen. Riemanmian geometry. Ed. by S Axler and KA Ribet. Vol. 171. Springer, 2006. ISBN: 978-0-387-29403- (cit. on p. 2). Weijie Su, Stephen P. Boyd, and Emmanuel J. Candès. "A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights". In: J. Much. Learn. Res. 17 (2016), 153:1-153:4; (cit. on 2).
605
[SBC16]
607
13

---

609
[SFF19]
Yue Sun, Nicolas Flammarion, and Maryam Fazel. "Escaping from saddle points on Riemannian manifolds". In: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada. 2019, pp. 7274-7284 (cit. on p. 1).
610
612
613
[SKM17]
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. "Riemannian stochastic variance reduced gradient". In: CoRR abs/1702.05594 (2017) (cit. on p. 2).
615
[SKM19]
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. "Riemannian Stochastic Variance Reduced Gradient Algorithm with Retraction and Vector Transport". In: SIAM Journal on Optimization 29.2 (2019), pp. 1444-1472 (cit. on p. 2).
618
617
618
[SQW17]
Ju Sun, Qing Qu, and John Wright. "Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method". In: IEEE Trans. Inf. Theory 63.2 (2017), pp. 885-914 (cit. on p. 1).
620
621
[T]
Mingkui Tan, Ivor W. Tsang, Li Wang, Bart Vandereycken, and Sinno Jialin Pan. "Rie- mannian Pursuit for Big Matrix Recovery". In: Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing. China, 21-26 June 2014. 2014, pp. 1539-1547 (cit. on p. 1).
622
623
624
625
[TH14]
Guo-ji Tang and Nan-Jing Huang. "Rate of convergence for proximal point algorithms on Hadamard manifolds". In: Oper: Res. Lett. 42.6-7 (2014), pp. 383-387 (cit. on p. 7).
[Tr++18]
Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael I. Jordan. " "Averag- ing Stochastic Gradient Descent on Riemannian Manifolds". In: CORR 0bs//882.09912 (2018) (cit. on p. 2).
628
629
630
[Tse08]
Paul Tseng. "On accelerated proximal gradient methods for convex-concate optimiza- tion". In: submitted to SIAM Journal on Optimization 2.3 (2008) (cit. on p. 2).
[Van13]
Bart Vandereycken. "Low-Rank Matrix Completion by Riemannian Optimization". In:
633
SIAM Journal on Optimization 23,2 (2013), pp. 1214-1236 (cit. on p. I).
634
[Wa17]]
Rolf Walter. "On the metric projection onto convex sets in Riemannian spaces". In: Archiv der Mathematik 25.1 (1974). pp. 91-98 (cit. on p. 6).
635
636
[Wan+15]
Jinhua Wang, Chong Li, Genaro López-Acedo, and Jen-Chih Yao. "Convergence analy- sis of inexact proximal point algorithms on Hadamard manifolds". In: J. Glob. Optim. 61.3 (2015), pp. 553-573 (cit. on p. 7).
638
639
[Wan+16] 16]
Jinhua Wang. Chong Li, Genaro López-Acedo, and Jen-Chih Yao. "Proximal Point Algorithms on Hadamard Manifolds: Linear Convergence and Finite Termination". In:
641
SIAM J. Optim. 26.4 (2016), pp. 2696-2729 (cit. on 7).
642
16]
Ke Wei, Jian-Feng Cai, Tony F Chan, and Shingyu Leung. "Guarantees of Riemannian optimization for low rank matrix completion". In: arXiv preprint arXiv: 0603006600 (2016) (cit. on p. 1).
643
644
[2]
Ami Wiesel. "Geodesic Convexity and Covariance Estimation". In: IEEE Trans. Signal Process. 60.12 (2012). pp. 6182-6189 (cit. on p. 1).
646
647
[WRM16]
Di Wang, Satish Rao, and Michael W. Mahoney. "Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction". In: 43rd International Col- loquium on Automata, Languages, and Programming, ICALP 2016, July I 11-15, 2016, Rome, Italy, 2016, 50:1-50:1 13 (cit. on p. 2).
648
649
650
851
[WS17]
Melanie Weber and Suvrit Sra. "Frank- Wolle methods for geodesically convex optimiza- tion with application to the matrix geometric mean". In: CoRR abs/17100.177/ (2017) (cit. on p. 1).
653
654
[WS19]
Melanie Weber and Suvrit Sra. "Nonconvex stochastic optimization on manifolds via Riemannian Frank-Woll methods". In: CoRR abs/1910.04194 (2019) (cit. on p. 1).
655
696
[WW116]
Andre Wibisono, Ashia C. Wilson, and Michael I. Jordan. "A Variational Perspective on Accelerated Methods in Optimization". In: CoRR abs/1603. .02445 (2016) (cit. on p. 2). Hongyi Zhang, Sashank J. Reddi, and Suvrit Sra. "Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds". In: Advances in Neural Information Process- ing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain. 2016, pp. 4592-4600 (cit. on p. 2).
658
[7RS16]
659
660
681
662
[ZS16]
Hongyi Zhang and Suvrit Sra. "First-order Methods for Geodesically Convex Optimiza- tion". In: Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016. 2016, pp. 1617-1638 (cit. on pp. 1, 2, 6, 9, 21, 24).
663
664
14

---

685
[ZS18]
Hongyi Zhang and Suvrit Sra. "An Estimate Sequence for Geodesically Convex Opti- mization", In: Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018. Ed. by Sébastien Bubeck, Vianney Perchet, and Philiippe Rigollet. Vol. 75. Proceedings of Machine Learning Research. PMLR, 2018, pp. 1703-1723 (cit. on pp. 5, 6, 8).
686
667
668
689
[ZYF19]
Pan Zhou, Xiao-Tong Yuan, and Jiashi Feng. "Faster First-Order Methods for Stochastic Non-Convex Optimization on Riemannian Manifolds". In: The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan. 2019, pp. 138-147 (cit. on p. 1).
671
672
673
674
[ZZS18]
Jingzhao Zhang, Hongyi Zhang, and Suvrit Sra. "R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate". In: CoRR abs/ 181 .04494 (2018) (cit. on p. 1).
675
678
677
[77S22]
Peiyuan Zhang, Jingzhao Zhang, and Suvrit Sra. "Minimax in Geodesic Metric Spaces: Sion's Theorem and Algorithms". In: CoRR abs/2202.06950 (2022) (cit. on p. 2).
678
Checklist
679
680
1. For all authors...
681
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
683
(b) Did you describe the limitations of your work? [Yes] See Section 3.
684
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
685
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
687
2. If you are including theoretical results...
688
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the begin- ning of Section 1.3. Alternatively, see the statements of Theorem 2.2 and Theorem 2.4. (b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
692
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
695
696
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
697
688
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
689
700
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
701
(a) your work uses existing assets, did you cite the creators? [N/A]
702
(b) Did you mention the license of the assets? [N/A]
703
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
705
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
706
707
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
708
5. If you used crowdsoureing conducted research with human subjects...
710
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
711
712
(b) Did you describe any potential participant risks, with links to 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]
715
15


Reviews:
[{"review_id": "wqlFQYdwCmV", "reviewer": "Reviewer_HxJc", "summary": "The authors present \"an accelerated first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions over a compact and geodesically convex set in Hadamard manifolds, that we access to via a metric-projection oracle\". For this oracle, they use \"projected Riemannian gradient descent to implement an inexact proximal point operator\". \nThe analysis aims to establish 'an accelerated rate' up to multiplicative factors induced by the manifold's sectional curvature (Line 166, Fact 1.3, Lines 149-155), as well as some log factors (Remark A.5, Line 838, Remark 2.3). An extensive list of recent work on Riemannian optimization has been provided. \n", "questions": "It would be helpful to provide a remark, specifically gathering all of the \"universal constants\" and \"logarithmic factors\" (e.g., Remark A.5, Line 838, Remark 2.3, etc); and/or the source of their introduction into the analysis. \n\nFootnote 0: some of the links seem to be broken; for example, for \\kappa_\\min. \n\nThere is an impossibility argument on Lines 246-250 that I did not follow. Could you please elaborate?\n\nA short discussion on the gains from the 'approximate' computation (Remark 2.3), in some of the Riemannian optimization instances, could be helpful.\n\nSome examples/references for the note on Lines 365-367 could be useful. (\"We note that any other algorithm with linear convergence rates for constrained strongly g-convex, smooth problems that works with a metric-projection oracle can be used as a subroutine to obtain an accelerated Riemannian algorithm.\")\n\nCould the authors elaborate on \n- \"due to fundamental properties of their methods\" on Line 63; \n- \"which is not amenable to optimization\" on Line 73-74;\n\nIn relation to \"The Riemannian proximal point subroutine we design is of independent interest\", on Lines 79-80 (and in the abstract), it might be beneficial to present this subroutine in an algorithmic form instead of plain text. \n\n\nAre there any limitations of the presented algorithm or analysis that the authors feel could inform a better comparison with the existing literature as well as future work? Including possibilities of alternatives in certain aspects. Other examples: any further details regarding the multiplicative factors (Line 382), or any indication or difficulty in extending to other manifolds (Lines 383-384)?\n", "limitations": "Please see previous comments on the discussion of technical contributions as well as on logarithmic factors. \n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The writing and the flow are excellent but only provide a very high level idea of the work and contributions of the current paper. A considerable part of the paper, up until the middle of page 7, out of 9 pages, focuses on review of background material, review of previous works, and \"insights\", and the technical statements and proofs have been presented in the appendices. I would also leave a proper assessment of the claims to reviewers with close familiarity to those recent works cited upon which the paper claims advantages. As an example a lot of the background reviewed on Lines 85-152 remains unused within the main paper. \n", "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_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DNcVRKHtra7", "reviewer": "Reviewer_9V2i", "summary": "This paper proposed an accelerated first-order optimization algorithm for smooth and\n(strongly) geodesically-convex functions over a compact and geodesically-convex set\non Hadamard manifolds. It is proven in this paper that this Riemannian algorithm\nenjoys the same convergence rate as the Euclidean AGD algorithm without convex constraints. \nThough there exist some relavent works, none of them fully generalize the Euclidean AGD \nconvergence results to the Riemannian setting.", "questions": "The requirements of a geodesically convex function over a geodesically-convex set on Hadamard manifolds\nare quite strong and already limit the usage for many important applications. The author gives two manifolds in\nthe paper, one is a hyperbolic manifold and the other one is the manifold of SPD manifold. Giving a few applications\nwould be helpful.\n\nThe metric projection oracle seems not easily available. Giving a few examples and potentials in applications\nwould be useful.\n\nThe algorithm needs the value of \\zeta_{2D}. How do users get this value?", "limitations": "I think the authors need to comment on the implementation and numerical performance of this proposed algorithm.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The contribution of this paper is on the theoretical aspect. It is interesting in the sense \nthat it firstly gives an algorithm that fully extends the Euclidean AGD to the Riemannian setting\nwith constraints. However, numerically, this algorithm is hard to use. It involves quite a \nfew unknown operators and parameters, and expensive operators.", "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_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "APk1U6e1Nwb", "reviewer": "Reviewer_qP9H", "summary": "The paper proposes accelerated first-order methods for optimizing smooth and geodesically convex functions on Hadamard manifolds. ", "questions": "see above", "limitations": "see above", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Acceleration on Riemannian manifolds is an important and timely topic that has recently received a lot of interest in the optimization community. The literature review is comprehensive and the background section is well-written. The theoretical results are well-motivated and presented.\n\nMy main concern is the metric projection oracle and the resulting comparison results with existing methods. If I understand correctly, the complexity results are given with respect to the number of queries to the metric projection oracle. However, the cost of one such query is not clear to me from the text (also not from Rmk. 2.3). If you factor in this cost, does the method still compare favorably to prior methods? Please clarify, if I am misunderstanding. \n\nHow practical is the proposed method? Can Alg. 1 (including the subproblems) be implemented efficiently for at least some classical problems, e.g., some of the examples listed in the first paragraph of the introduction?", "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_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject