No-regret Online Learning over Riemannian Manifolds
Authors: Xi Wang
Zhipeng Tu
Yiguang Hong
Yingyi Wu
Guodong Shi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online optimization
Riemannian manifolds
Riemannian optimization

Abstract: We consider online optimization over Riemannian manifolds, where a learner attempts to minimize a sequence of time-varying loss functions defined on Riemannian manifolds. Though many Euclidean online convex optimization algorithms have been proven useful in a wide range of areas, less attention has been paid to their Riemannian counterparts. In this paper, we study Riemannian online gradient descent (R-OGD) on Hadamard manifolds for both geodesically convex and strongly geodesically convex loss functions, and Riemannian bandit algorithm (R-BAN) on Hadamard homogeneous manifolds for geodesically convex functions. We establish upper bounds on the regrets of the problem with respect to time horizon, manifold curvature, and manifold dimension. We also find a universal lower bound for the achievable regret by constructing an online convex optimization problem on Hadamard manifolds. All the obtained regret bounds match the corresponding results are provided in Euclidean spaces. Finally, some numerical experiments validate our theoretical results.

No-regret Online Learning over Riemannian Manifolds
Xi Wang AMSS
Zhipeng Tu AMSS
Yiguang Hong" Tongji University Shanghai, China yghonggiss ac
Chinese Academy of Sciences
Chinese Academy of Sciences Beijing, China
Beijing, China wangxi140mails. ucas. ac
tuzhipeng@amss.acco cn
Yingyi Wu
Guodong Shi
University of Chinese Academy of Sciences Beijing, China
The University of Sydney
NSW, Australia guodong shi @sydney edu.
wuyy@ucas.ac
Abstract
We consider online optimization over Riemannian manifolds, where learner attempts to minimize a sequence of time-varying loss functions defined on Rieman- nian manifolds. Though many Euclidean online convex optimization algorithms have been proven useful in a wide range of areas, less attention has been paid to their Riemannian counterparts. In this paper, we study Riemannian online gradi- ent descent (R-OGD) on Hadamard manifolds for both geodesically convex and strongly geodesically convex loss functions, and Riemannian bandit algorithm (R-BAN) on Hadamard homogeneous manifolds for geodesically convex functions. We establish upper bounds on the regrets of the problem with respect time horizon, manifold curvature, and manifold dimension. We also find a universal lower bound for the achievable regret by constructing an online convex optimiza- tion problem on Hadamard manifolds. All the obtained regret bounds match the corresponding results are provided in Euclidean spaces. Finally, some numerical experiments validate theoretical results.
Introduction
The online optimization has been widely studied in the past decades in online routing, spam filtering,
and machine learning 4 23 X. Without prior knowledge of loss functions, an online convex optimization algorithm predicts solutions before the loss function is revealed.
In this paper, we consider the following Riemannian online convex optimization (R-OCO) problem,
min E.CKC
fx(x),, 1,2,..,
where M is complete Riemannian manifold equipped with Riemannian metric and K. is geodesically convex (g-convex) subset of M. Here, (ft)==1,2..., sequence of unknown loss functions and every fo is geodesically convex (g-convex) function with sufficient smoothness. The R-OCO problem (I) extends the online convex optimization Euclidean spaces with potential applications in machine learning, such online principal component analysis (PCA), dictionary learning, and neural networks 28
"Correspondence author (Y. Hong, +86-10 886-10-82541888 82541888
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

The R-OCO problem ( can be understood as learning process of T rounds. At each round t 1,2,3.... T, an online learner chooses a strategy 2, from the g-convex subset K. Later or simultaneossly, the adversary (or nature) produces g-convex loss function fa K. - R of which the learner has no prior knowledge. Finally, the learner receives the feedback and suffers the loss fa( Generally, there are two types of information feedback. One is the full information feedback, where the entire function ft is revealed to the learner; the other is the bandit feedback, where only the value f((zz) is revealed. The goal of the R-OCO is to minimize the regret, defined as
R(T) Σ f((z))
min Σ f((x), EE
which measures the difference between the cost by { and the best-fixed point chosen in hindsight. An algorithm is called no-regret [32), the regret the algorithm goes sublinearly with the time horizon T'.
For carrying out optimization on a manifold, some classical methods treat the manifold as subset of an ambient Euclidean space and employ Euclidean constrained optimization techniques. For instance, [30 presented an algorithm for the online PCA problem, where the variables were updated in an embedding Euclidean space and then projected onto a manifold. However, in practical applications, the dimension an embedding Fuclidean space can be too high (e.g.. g.. the Grassmann manifold [3],, and the projection can be expensive to compute (e.g., the manifold of symmetric positive definite (SPD) matrices (37] ). An alternative approach termed Riemannian optimization makes use of intrinsic geometry of manifolds so that Riemannian optimization an unconstrained problem, and thus avoiding high dimension embedding and high computing cost for the projection. Furthermore, this viewpoint has shown benefits from the g-convexity, by which a nonconvex optimization problem can be converted into a g-convex one [6]. Consequently, it is important to take a Riemannian approach in our problem (I)
optimize directly the manifold as
Although there were many existing algorithms for offline manifold optimization problems
31
very few results were obtained about the Riemannian online optimization problem. [35 proposed an online algorithm for estimating hidden Markov chains on Hadamard homogeneous spaces and [9] analyzed Riemannian adaptive methods on products in the regret sense. More recently, [29] studied
zeroth-order online optimization problem on Hadamard manifolds with a sublinear assumption.
This paper aims to design no-regret algorithms for the R-OCO problem in both full information feedback and bandit feedback. The contribution of this paper summarized as follows:
Contribution
We propose Riemannian online gradient descent algorithm (R-OGD) for the R-OCO problem in the full information feedback, and then establish upper regret bounds of the R-OGD algorithm for g-convex and strongly g-convex functions.
We introduce Riemannian bandit algorithm (R-BAN) for the R-OCO problem in the bandit feedback and then establish an upper regret bound for g-convex functions. Moreover, we develop a key technique to analyze the derivative of a local integration homogeneous manifolds, which can be applied to estimate gradients in Riemannian optimization and beyond.
We focus on the worst-case regret and present universal lower regret bound of R-OCO algorithms with g-convex losses on Hadamard manifolds, which matches the upper bound achieved by the R-OGD algorithm for g-convex functions.
The established lower and upper bounds on the achievable bounds of R-OCO match their counterparts for Euclidean online convex optimization e.g., 38 24 20
I. We briefly list our results in Table [
Related Work The Euclidean online convex optimization was introduced in (38) Inspired by the gradient descent method, 38 proposed the online gradient descent algorithm (OGD) of which the upper regret bound was proven to be O(VT). Then 24 proceeded with the study of the OGD algorithm and established an upper regret bound O (lo T) for strongly convex functions. addition, gave universal lower bound of (VVT) for online algorithms, which indicated that the bounds 3 and 24 are essentially optimal. In the bandit setting, (20 provided a detailed exposition of one-point bandit algorithm. By modifying the gradient in the OGD algorithm to randomized

---

Table 1: Comparison of regrets between our work and corresponding results in Euclidean spaces. T: the time horizon; n: dimension of the manifold; Ç and A: constants relied on the sectional curvature bound K, the dimension n and the domain IC.
Full information,
Full information, strongly g-convex
Bandit feedback
Universal lower bound S2(VT)
g-convex
Our Work
V(
O [og T
O o ((+ 20
Fuclidean
((VT)
38
0 (log T 24
2(VT)
estimator, the upper regret bound attained O(T?) and O(T3) for convex loss functions and strongly convex loss functions, respectively. By extending the one-point bandit algorithm, [3] developed multi-point bandit algorithm and presented upper regret bounds O( and O log I') for convex and strongly convex loss functions. The Riemannian online algorithms proposed in this paper in the full information feedback and the one-point bandit feedback settings are extensions of the algorithms in ([38) 24 20 to Riemannian manifolds.
Riemannian optimization has drawn much research attention in the past decades. Many basic algorithms in Euclidean spaces such as the gradient descent method, Newton's method, and trust- region methods have heen adapted into Riemannian setting (2 5 31]. Some research of Riemannian stochastic optimization (R-SO) was intended to deal with time-varying optimization problems 12 36 37 35). Among them, [36] provided the first global complexity analysis for the R-SGD algorithm on geodesically convex problems over Hadamard manifolds, and [35] proposed an online algorithm deal with hidden Markov chains on Hadamard homogeneous spaces. When performed in batch, R-SO methods are to minimize the average regret in the case of knowing the prior distribution of the loss functions. In these sense, the R-SO can be viewed as kind of R-OCO problems and R-OCO algorithms can handle settings without prior knowledge.
The results about the R-OCO problem quite limited. 7 proposed regularized online optimization methods via a Riemann-Lipschiz continuity condition, which focused on convex functions from an ambient Euclidean space. In the full information setting, [9 constructed regret upper bounds of Riemannian adaptive methods for g-convex functions, which required a product manifold structure. When the form of loss function was available, Hadamard manifolds for the tracking error in asymptotic sense well as regret bounds by assuming the sublinearity of the term Vr, which is summation of distance between the minimizer of ft and fi+1. In contrast, the regret bounds established for our online gradient- bal--bdddddddiiii Riemannian optimization algorithms are sublinear for any time, matching those for Euclidean online optimization.
29 proposed a zeroth-order online algorithm on
2 Preliminaries
Riemannian manifolds A manifold M is topological space locally diffeomorphic to Euclidean spaces. The tangent space T.M is linearization of manifold M at point æ. A vector field X is a map assigning every point M with tangent vector X(x) T,M, which can be also viewed as differential operators over smooth functions on M, i.e., the operation xff) defines a function (x)) lim,-,o )(f(E(t)) fx)) on M, where is curve that starts at 2 with tangent vector (x)).
A Riemannian manifold is smooth manifold M equipped with metric tensor (or called Rieman- nian metric), which defines an inner product (. in every tangent space T.M of x E M. The Riemannian metric brings distance structure on M. A curve is geodesic if it locally minimizes the length, which is an analog of a straight line in Euclidean spaces. On Riemannian manifolds, geodesic is uniquely determined by the start point and initial tangent vector. In this way, the exponential map exp,, : T.M + M is defined by mapping a vector X E T..M to x1) E M for the geodesic 7 such that (0) and (0) X.
Curvature reflects the geometry manifolds. We focus on sectional curvature, which is the Gauss curvature of two-dimensional submanifold. Following (36), we consider the Hadamard manifold, which simply connected and complete manifold with nonpositive sectional curvature. The Cartan- Haaun-addmarrd theorem [[] shows that the exponential map exp is diffcomorphism from the
3

---

langent space T.M = R" to the manifold M. Therefore, the exponential map has an global inverse exp, (-) on Hadamard manifolds, and the distance d(r. y) can be expressed as |eex, (y)lla.
Isometries of Riemannian manifolds have been widely studied differential geometry 11 10 An isometry é M -> M is diffeomorphism preserving distance, i.e., d(x,, y) d(((#), (ly) for all y E M. It is remarked that all isometries of a Riemannian manifold form a Lie group G. A Riemannian manifold is homogeneous manifold if the group of isometries G acts on M transitively, i.e. for any points y E M there exists an isometry such that δ(x) = y. Some properties of homogeneous manifolds are used in our work, for example, the Killing field that represents the infinitesimal symmetry of isometries. We leave those properties in the appendix, due to the space limitation.
Function Classes A set K. is called geodesically convex (g-convex) if, for any points z, y E K. there admits geodesic y C IC connecting x and y. function convex (or g-convex) if for any geodesic Y [0, 1] + M,
IR is called geodesically
((((()) s (1 - ())(((()) + (f(((1)), W [0.
The g-convexity has some equivalent conditions. When is differentiable, which means that there exists a gradient (x) such that
= for any vector field X, the g-convexity is
equivalent to
f(y) 2 + (V]()).xx,
Vr, E M.
Furthermore, if is twice differentiable, the g-convexity is equivalent to
(ess( X)= = ((X([(z)) (VxX) 2 0, Vo E M, E T.M,
where V is the Levi-Civita connection of M, which is an analog of the differential vector fields in Euclidean spaces (see (17). A differentiable function f M R is geodesically u-strongly convex (or u-stronggy g-convex) if there exists a constant μ >> 0 such that for any a, E M,
f(v) 2 f (Vf(x), exp, exp_
H de (2.
We term a function to be geodesically L-Lipschitz (or g- g-L-Lipschitz) if there exists constant L > 0 such that.
If(y) - f(=)] < L d(x, v), Vr, M, When f is differentiable, the g- L-LLLipschitzeess is equivalent to
|V/(()]| < L, Lv M.
3 Riemannian Online Convex Optimization with Full Information Feedback
This section is devoted to the study of the R-OCO problem in the full information feedback. Here, we first propose our R-OGD algorithm and then analyze upper regret bounds of R-OGD for both g-convex and strongly g-convex functions. In addition, universal lower regret bound is presented to illustrate that the regret bound of the R-OGD algorithm is tight up constant the g-convex case.
3.1 Riemannian Online Gradient Algorithm
In the full information setting, we consider the following assumptions, which were used in the literature of Euclidean online convex optimization and Riemannian optimization (e.g.. [38 36
Assumption 1. There exists x² E M such that x* = arg min Σt= fe(x).
Assumption 2. (M.g) g) is a Hadamard manifold with the sectional curvature lower bounded by
constant -k (K 2 0).
Remark 1. The Hadamard manifold plays an important role in Riemannian geometry [22]. Some well-known spaces, such as the Euclidean space Ra, the hyperbolic space H and the manifold of SPD matrices, are all Hadamard manifolds [36]
Assumption 3. The g-convex set IC is a bounded set with diameter D, i.e.,
d(x, 4) S D, Vx, K.

---

Assumption 4. For all t= ...... T, ft are differentiable and g-L-Lipschizz
We now propose Riemannian online gradient descent algorithm (R-OGD) in Algorithm 1 where the exponential map replaces the vector addition in the Euclidean online gradient descent 38
Algorithm 1: Riemannian Online Gradient Descent Algorithm (R-OGD)
Input: Manifold M, time T, step sizes { Output: { { for L to T do
Play 2y and observe the function ft; Update
2++1 = Px(exp,,, (=
where Px is the Riemannian projection mapping of x onto K, that is, (x( := arg minyex d(x; y):
Return J4+11 and suffer from the loss f<(x));
end
3.2 Regret Upper Bounds
In Theorems D and 2 we present upper bounds of the regret along the R-OGD algorithm for g-convex Vi.dd tanh (Vrid) By direct observation,
and strongly g-covvex functions, respectively. Take Ç(Ki, d)
an increasing function of the variables x and when red 0.
Theorem (Convex Case). Suppose that Assumptions 7 hold, and ft is g-convex for any t = 1....,T. Then the R-OGD algorithm with step sizes {ar LVCC..DY guarantees the following
regret bound for all 2 1,
R(T) S D C(R, DJT.
Theorem (Strongly-convex Case). Suppose that Assumptions 7 hold, and ft p-strongly g- T.
1 guarantees the convex for any f = I.. Then the R-OGD algorithm with step sizes {ar, pt following regret bound for all T
T2C(Ks, D) 2p
R(T) &
log T).
The proofs of Theorems D and are in the appendix. A major challenge in proving Theorems I and
is that there is no vector space structure on Riemannian manifolds. Thanks to the trigonometric distance bound proposed in (36), we manage to obtain the regret ((VT) and O log T) for gocoeex and strongly g- g-convex loss functions, respectively. By gradually moving zero, the results recover the regret bounds for Euclidean gradient descent in [38 and 24]]
Theorems and also reveal the influence of curvature on the regret bounds. Since Ç(K, d) is an increasing function of K, the upper regret bounds in the R-OGD algorithm are larger than those in Euclidean spaces and the increase of ş. raises the upper regret bound. Therefore, proper Riemannian metric should be chosen the optimization to avert the high sectional curvature bound.
3.3 Regret Lower Bound
This section is intended to answer the question whether there exists an algorithm that attains a tighter regret bound than (VTT) for g-convex functions. Theorem provides a negative answer. Theorem 3. Suppose that Assumptions [ hold. Then for any Hadamard manifold M, the Rieman- nian online convex optimization incurs the regret Q(DLVT) for any possible strategy in the worst case.
The proof of Theorem 3 is in the appendix. The result illustrates that, as in Euclidean spaces, the regret of Riemannian online comvex algorithm can not be less than R(VT) in the worst case. Moreover, Theorem shows that the regret of the R-OGD algorithm in Theorem T is tight up to constant.
5

---

Riemannian Online Convex Optimization with Bandit Feedback
In this section, consider the Riemannian online convex optimization with the one-point bandit feedback. We first present the Riemannian bandit algorithm (R-BAN) on Hadamard homogeneous manifolds and then analyze the (expected) upper regret bound for our algorithm. the rest of this section, for any point we denote B& (x) as the geodesic ball centered at x with radius 5, and (z) as the geodesic sphere centered at x with radius 8.
4.1 Riemannian Bandit Algorithm
In the bandit setting, Assumptions are slightly modified as follows.
Assumption 5. MM is an n-dimensional homogeneous Hadamard manifold with the sectional curva- ture lower bounded by a constant -k (K 0).
Remark 2.
The homogeneous Hadamard manifold has been widely studied in differential geometry [T] The property of homogeneity has received much attention in machine learning [33 35
It has been seen that many manifolds often considered in Riemannian optimization, such as the Euclidean space RR," the Hyperbolic space H and the manifold of SPD matrices, are Hadamard homogeneous manifolds.
Note that on Hadamard homogeneous manifolds, the volume and surface area of geodesic ball is only related to the radius but not to the center of the ball, thus we denote V, as the volume of (x) and Sg the surface area ((n 1)- volume) of Ss(x) for all in the manifold M.
Assumption 6. centered at p. and also contained in a ball with rudius D, iee.
There exists interior point p K. such that the set K. contains ball with radius
BA(p) C C BD(p)-
Assumption 7. For any t t= 1....., T, fe is differentiable, g- g-L-Lipschitz and bounded by C.
Inspired by the Euclidean bandit algorithm, we replace the gradient (x() with a randomized estimator and propose our R-BAN in Algorithm 2 on Hadamard homogeneous manifolds.
Algorithm 2: Riemannian Bandit Algorithm (R-BAN)
Input: Manifold M, time T, step size a, parameters 8, Output: Sequence {
for t= 1 to T do
Pick o, uniformly from Ss(y:);
Play and observe fe fzz);
Construct the gradient estimator
expr (xt)
gt = Se(
expr: (x+)
Update y, with the rule
Vt+1 ( (-og::)
where we denote P(1-))K as the projection mapping onto the shrinking set
(1 --- = (c au))lu - exp, (æ), x E K..
Return Fa and suffer from the loss fx());;
end
4.2 Challenges from Geometry
Since Algorithm 2 is an extension the Euclidean bandit algorithm in (0), is worth reviewing the analysis in (20). In the Euclidean setting, we uniformly choose I, on the Ss())) and update ye by the rule
gr f(xt)
1me-velll
(2)
U++1 = P(1-r)u(u oz..))

---

The basic idea for the analysis is to introduce the smoothed loss function 200
1 / fi(u)du,
(z) (z) = EuER (uE
V8 Bs(w)
where ff convex approximation of ft when å is small. is shown that 39. an unbiased estimator of the gradient v (Bt), hence the bandit algorithm is actually an expected gradient descent method [20] with the loss function f. In this way, an Euclidean regret bound of the bandit algorithm is established by [20].
Back to the Riemannian case, we attempt to generalize the analysis of 20 in parallel by defining the "Riemannian version" " of the smoothed loss function,
1
f((z) = EuE Eu
f((u)
Vg Bs(x))
where w is the volume element with respect to the metric g. Analyzing this smoothed loss function in the Riemannian space, however is fundamentally challenging due to the following two reasons.
(i) The gradient hard to compute. Computing the gradient f. quite different from that in Euclidean spaces, due to the absence of the commutativity of the derivative operator V and the integration operator JBs(wa) In Euclidean spaces, the derivative operator commutes with the
integration operator [.(( Accordingly, for the Euclidean smoothed loss function f.
1 V
f fi((uddu
f (ye) = Ba(z))
fe(u)du= = V6 Br(U.))
(3)
which implies [ V f. (ye). However, Riemannian manifolds the derivative operator V does not commute with the integration operator JB.(w))) Consequently, the equation (3) fails for functions on Riemannian manifolds.
(ii) The convexity may be lost. Another essential challenge for regret analysis is the convexity of J.. In Euclidean spaces, may not hold for a Riemannian manifold. Through calculation, the Hessian of fc on Riemannian manifolds is
easily conclude the convexity of f.P. However, the convexity
1 V/ Bs(w)
(esssf)
(H)ss + (V, V((())))
where is Killing field such that 17(x) X. Since the quadratic form Hess(ff) (z) n. (x())) can be negative some 1) M, the g-convexity of Se is violated for some small 8.
4.3 Gradient Bound and Approximate g- g-Convexity
To address the difficulty (i), propose key technique to analyze the derivative of local integration by introducing the Killing vector field. With the help this technique, we manage to compute the gradient of f in Lemmal
Lemma 1. Let M be a homogeneous Hadamard manifold, and f be a C2 function on M. Then the smoothed function f(x) V Ba(o)) fw satisfies,
1) vf(x) = v. (s f(1)
exp, (())
St EueSs(a)
[(()) exp= 'w) |oxx= (w)ll
Ve E M:
Texp= [w]]]
V.
2) ff((()) < C. then
S$ C < 3 nKKC
[Vi(()] <
V
for all 8 0.
7

---

Remark 3. The proof of Lemma can be found in the appendix. The first part of the lemma establishes a gradient estimator of ft(x), while the second part gives us easy-to coymppte bound of the gradient. the proof, we develop a key technique that transforms derivation of integration on (3(x) to integration of derivative of corresponding Killing vector field on B3 B2x)), i...
x( x( Ba(m)
f(u)w) = S n(f())w.
(4)
Bg(m)
where is Killing field with (xx) - X. This technique does not rely on the curvature and other specific manifold structures. Hence, the technique can be a basic tool for optimization on homogeneous spaces and maybe in broader areas.
For difficulty (ii, we notice that though the function fo may not be g-convex, it is very close to be g-convex.
Lemma 2. Suppose that M a Hadamard homogeneous manifold, and K. is a convex and bounded set of M. Then there exists constant only related to the set K such that for any g-convex and g- s f.
flv) - f(z) exp, (v)) 2 Rx,
The proof of Lemma 2 is in the appendix. It is worth mentioning that the constant describes how close smoothed function is to be g-convex. Notice that,
sup a.y.uKK
(VGexpī' o())
<(z)
VG Ox,
does not depend on the function ft. and the time T. Moreover, for a certain manifold M, once the set K. is fixed and the explicit expression of á is given, We briefly list the bound of é in the following two kind of manifolds.
compute the constant p as finite number.
Let manifold M be Euclidean space, then we can find the isometry ((2) + Hence we can conclude that = and f is convex, which coincides with the result in Euclidean spaces.
(2) Let M be 2-dimensional Poincaré disk, and then the isometry & from y has the closed form
Φx o oy.
where (x))) 2=z and (y(2) out bound p
v- 1- y=
Therefore, if K. has diameter D, we can figure
p S 16 tanh(D/22 t2nh tanh (D/2)
D
1 tanh(D/2)) I-
which implies that p may grow exponentially with respect D.
Although the value of is generally difficult to calculate, our algorithm analysis and parameter selection do not depend on the specific value of p (see Theorem 4).
4.4 Regret Bound
With the above effort, we carry out the analysis of the expected regret bounds of Algorithm Denote B nK, A /C(D D) + 3L 2C/rr and A VA
2pl.
VI.
Theorem 4. Suppose that Assumptions 7 and 5 hold, and fe is g-convex for any 1,...
T.
D Take t = f. a C 7 CDn ((n.D)
Then the expected regret of Algorithm is
A
upper bounded by
B[R(T)) < 2T V nCDD
8

---

The proof of Theorem can be seen in the appendix. Theorem shows that the regret of the Rie- mannian bandit algorithm achieves O (T for g-convex loss functions on homogeneous Hadamard manifolds, which is the same as the regret bounds Euclidean spaces [20].
Our work is different from the result in 29 in two aspects. First, in (29] the sublinear regrets bounds depends the assumption of sublinearity of the term Vr, while in Theorem | the sublinear regret bound is expressed explicitly with the time horizon T with no additional assumptions. Second, to estimate the gradient. [29] used biased estimator of the gradient, while in our bandit algorithm the gradient estimator 9, of the smoothed function is unbiased.
5 Numerical Experiment
We validate our findings Riemannian manifolds in both g-convex and strongly g-convex losses. We also compare our results with the Riemannian zeroth online (R-OZO) algorithm [29] if possible (the R-OZO is only suitable for strongly g-convex cases). All experiments
performed with the on a 64 bit Windows platform with a 3.4 GHz CPU (AMD Ryzen5 2600) and the code used for the numerical experiments is provided in the supplementary materials.
help of Pymanopt toolbox [4 2
5.1 Strongly Convex Cases
For strongly g-convex cases, we apply our R-OGD and R-BAN algorithms to the Fréchet mean problem, which is also known as finding the Riemannian centroid of set of points on a manifold with many applications, such as diffusion tensor magnetic resonance imaging (DT-MRI), radar signal processing, and batch normalization of neural networks [66] 27 [5]. In this subsection, we study an online form of the Fréchet mean problem to average a set of N time-varying points {A,,1, Ar,, Ac.,. ...,, Ar, manifold. The loss function is defined as
N Σ dX,, A.s), 1,2,....7
f((x))
where dXX, Y) is the Riemannian distance of the manifold. is remarked that fo is g-convex and 2-strongly g-convex [18] so that we can apply our algorithms. In particular, we test the R-OGD and the R- R-BAN algorithm, respectively, on the manifold of SPD matrices and in the hyperbolic space, and we also compare our R-BAN algorithm with the R-OZO in 29).
Fréchet mean the SPD Manifold On the manifold of SPD matrices {X E R= X, X > 0}_ we run the R-OGD algorithm with two kinds of step size: the step size for convex case a, = D/(L//LLC D)t) (R-OGD-C) and the step size for strongly g-convex case aa = 1/(2t) (R-OGD-SC). In these two cases, we set (n, N, T) = [100, 10, 1000]. Matrices AG, are randomly generated by the method in Pymanopt toolbox. We plot the average regret R(t)/t /t versus the learning round and the running time in Figures sublinearly with / and the average regret of the R-OGD-SC converges faster than that of R-OGD-C terms of the iteration as well as the running time, which are consistent with the results Theorems T and 2
((a) ((b) As seen, the regrets of the R-OGD algorithm go
Fréchet mean on the Hyperbolic Space
We test the performance of the R-BAN algorithm in the
hyperbolic space H" = {I E R=+1| 2n+1 + Σi=1 x² -1}. The data A, is randomly generated by normal Gaussian distributions. Consider the case [n, N T [100, 10, 10000 and set d = 0.399 (which is four times the theoretical value) and a 0.006. Figures [(b) and ( compare the average performance between the R-BAN algorithm and the R-OZO algorithm for 100 random runs. We observe that our R-BAN algorithm can achieve sublinear expected regret with less information, since the R-OZO needs function values of two points in this case.
5.2 Convex Cases
An example of Riemannian optimization problems, which g-convex but not strongly g-convex, is the operator scaling problem defined the manifold of SPD matrices {X Ra XT =X X, 0).
h
http://www.yymanpp..cco BSD 3- --Cauuse License

---

24
20111
Leanzing
Leaning oocada
(a) Fréchet mean: SPD manifold
(b) Fréchet mean: hyperbolic
(c) Operator scaling
Figure 1: Average regret vs learning rounds
MOA
20014
233
3.1
300
32
0.8
08
25
100
(a) Fréchet mean: SPD manifold (b) Fréchet mean: hyperbolic
(c) Operator scaling
Figure 2: Average regret vs running time
The operator scaling problem has drawn abundant interest in many areas, such as computing non- commutative rank (26) and computing Brascamp-Lieb constants (21). In this subsection, we study an online form of the operator scaling problem. Given a tuple of time-varying matrices .... Ar,N), the online operator scaling can be formulated in terms of minimizing the log capacity of operator Tx(X) = Σi= A AAA
Af, that is
fx(,,) log det (T()))) - log det(X,), 1, T..
test our R-OGD and R-BAN algorithms for the case [n, N, [,, 100000). The entries of Ai, are generated from the normal Gaussian distribution. We test the R-OGD with with taking the Lipschitz constant = and test the R-BAN with ó 0.22 (which five times the theoretical value) and 0.002 for 100 differennt runs. The result in Figures [[c] and [(c) shows the (expected) sublinear regret in this case, which supports our thcoretical results.
Conclusion
We considered online optimization problem Riemannian manifolds in the full information and bandit feedback setting. We developed the R-OGD algorithm on Hadamard manifolds and the R- R-BAN algorithm Hadamard homogencous manifolds. The upper regret bounds of the R-OGD and R-BAN algorithm, together with a universal lower regret bound were established with the influence of curvature clearly indicated. All of the regret bounds matched their Euclidean counterpart.
limitation of our work is that we do not take retraction into consideration. A retraction map is cheap approximation of the exponential map on manifolds and is sensible choice in many real scenarios. In future work, we intend to design Riemannian online optimization methods with retraction map, so that the resulting algorithms can be more effective in large-scale optimization problems.
Acknowledgement
This work is supported in part by Shanghai Municipal Science and Technology Major Project under Grant 2021S000000000 and the National Natural Science Foundation of China under Grant 61733018, and in part by Australian Research Council under Grant 1P190103615.
10

---

References
[I] Jacob Abernethy, Peter Bartlett, Alexander Rakhlin, and Ambuj Tewari. Optimal strategies and minimax lower bounds for online convex games (Technical Report No. UCCB/ECCS-2008-19) Technical Report. University of California, Berkeley, United States, 2008
[2] P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2009.
[3] Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Proceedings of the 23rd Annual Conference on Learning Theory (COLT), June 2010.
[4] Shmuel Agmon. The relaxation method for linear inequalities. Canadian Journal of Mathemat- ics, 6:382 -92,,,,,2,11 1954.
[5] Kwangjun Ahn and Suvrit Sra. From Nesterov's estimate sequence Riemannian acceleration. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 84 64-118. PMLR, 09-12 Jul 2020.
[6] 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.
[7] Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos. Online and stochastic optimization beyond Lipschitz continuity: A Riemannian approach. In International Conference on Learning Representations, 2020.
[8] Sébastien Arnold, Pierre-Antoine Manzagol, Reza Babanezhad Harikandeh, Ioannis Mitliagkas, and Nicolas Le Roux. Reducing the variance in online optimization by transporting past gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[9] Gary Becigneul and Octavian- Bugen Ganea. Riemannian adaptive optimization methods. In International Conference on Learning Representations, 2019.
[10] Valerii Berestovskii and Yurii Nikonorov. Riemannian manifolds and homogeneous geodesics. Springer, 2020.
[11] Marcel Berger. Geometry i. Springer Science & Business Media, 2009.
[12] Silvere Bonnabel. Stochastic gradient descent on Riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217-22) 2013.
[13] Nicolas Boumal and P-A Absil. Low-rank matrix completion via preconditioned optimization on the Grassmann manifold. Linear Algebra and its Applications, 475:200-239, 2015.
[14] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovic. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. CORR, abs/2104, 13478. 2021.
[15] Daniel Brooks, Olivier Schwander, Frederic Barbaresco, Jean- Yves Schneider, and Matthieu Cord. Riemannian batch normalization for SPD neural networks. In H. Wallach, H. Larochelle. A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[16] Guang Cheng. Hesamoddin Salehian, and Baba Vemuri. Efficient recursive algorithms for computing the mean diffusion tensor and applications to DTI segmentation. In European Conference on Computer Vision, pages 390-401. Springer, 2012.
[17] Shingg-Sher Chern, Weihuan Chen, and Kai Shue Lam. Lectures on differential geometry, volume 1. World Scientific, 1999.

---

[18] Charlan Dellon da Silva Alves, Paulo Roberto Oliveira, and Ronaldo Malheiros Gregório. la Riemannian weighted centers of mass applied to compose an image filter to diffusion tensor imaging. Applied Mathematics and Computation, 390: 25603, 2021.
[19] Jiashi Feng, Huan Xu, and Shuicheng Yan. Online robust PCA via stochastic optimization. In Advances neural information processing systems, pages 404 412.. Citeseer, 2013.
[20] Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without gradient. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, page 385-394, USA, 2005. Society for Industrial and Applied Mathematics.
[21] Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling. Geometric and Functional Analysis, 28(1):100-145, 2018.
[22] Mohammad Ghomi and Joel Spruck. Total curvature and the isoperimetric inequality in Cartan- Hadamard manifolds, 2021.
[23] Elad Hazan. Introduction online convex optimization. arXiv preprint arXiv: 1909.05207, 2019.
[24] Elad Hazan, Adam Kalai, Satyen Kale, and Amit Agarwal. Logarithmic regret algorithms for online convex optimization. In International Conference on Computational Learning Theory, pages 499-511 9933513. Springer, 2006.
[25] Jiang Hu, Xin Liu, Zai-Wen Wen, and Ya-Xiang Yuan. A brief introduction to manifold optimization. Journal of the Operations Research Society of China, 8(2):199-28) 22999992244111 2020.
[26] SK Ivanov, AM Kamchatnov, T Congy, and N Pavloff. Solution of the Riemann problem for polarization waves in two-component Miss-Einttein condensate. Physical Review E, 96(6):062202, 2017.
[27] J Lapuyade-Lahorgue and F Barbaresco. Radar detection using Siegel distance between autoregressive processes, application to HF and X-band radar. In 2008 IEEE Radar Conference, pages 1-6. IEEE, 2008
[28] Kuang- Lee and David Kriegman. Online learning of probabilistic appearance manifolds for hideo-based recognition and tracking. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) volume 1, pages 852-859. IEEE, 2005.
[29] Alejandro Maass, Chris Manzie, Dragan Nesic, Jonathan Manton, and Iman Shames. Online zeroth-order optimisation Riemannian manifolds. arXiv preprint arXiv:2010.002/1, 2020.
[30] Jiazhong Nie, Wojeiech Kotlowski, and Manfred K Warmuth. Online PCA with optimal regret. The Journal of Machine Learning Research, 17(1):62226607) 2016.
[31] Wolfgang Ring and Benedikt Wirth. Optimization methods on Riemannian manifolds and their application to shape space. SIAM Journal on Optimization, 22(2):596-677, 2012.
[32] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian pro- cess optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
[33] Hao Tang, Zhiao Huang, Jiayuan Gu, Bao-Liang Lu, and Hao Su. Towards scale-invariant graph- related problem solving by iterative homogeneous GNNs. Advances in Neural Information Processing Systems, 33, 2020.
[34] James Townsend, Niklas Koep, and Sebastian Weichwald. Pymanopt: A python toolbox for optimization on manifolds using automatic differentiation. Journal of Machine Learning Research, 17(137):1-5, 2016.
12

---

[35] Quinten Tupker, Salem Said, and Cyrus Mostajeran. Online learning of Riemannian hidden Markov models homogeneous Hadamard spaces. In Frank Nielsen and Frédéric Barbaresco, editors, Geometric Science of Information, pages 37-44, Cham, 2021. Springer International Publishing.
[36] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference Learning Theory, pages 1617-1638, 2016.
[37] Pan Zhou, Xiao-Tong Yuan, and Jiashi Feng. Faster first-order methods for stochastic non- convex optimization on Riemannian manifolds. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 138-147. PMLR, 16-18 Apr 2019.
[38] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, page 928 9889.35. AAAI Press, 2003.
13


Reviews:
[{"review_id": "w4srLQuwxro", "reviewer": "Reviewer_6h8i", "summary": "This paper takes online learning algorithms designed for the Euclidean space (algorithms for online convex optimization with convex or strongly convex functions in the full information case. Or the convex case with bandit feedback) and generalizes them so they work in Hadamard manifolds with the corresponding notions of geodesic convexity. In the bandit case the manifolds are also assumed to be homogeneous. \n\nA lower bound of \\Omega(\\sqrt{T}) on the expected regret is provided. \n\nThe regret bounds are greater than those in the Euclidean counterparts and in the bandit case (the main contribution) they are greater by a factor that depends on the dimension and that is not given in the paper ( its value is not worked out). This fact makes the claim in the abstract \"All the obtained regret bounds match the corresponding results in Euclidean spaces.\" be false and misleading, in my opinion.", "questions": "", "limitations": "", "rating": 6, "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": "**Comments on Theoretical results**\n\nThe lower bound proceeds analogously to the Euclidean case. The contribution of this lower bound is on noting the Busemann functions can be used with the lower bound technique coming from the Euclidean case.\n\nThe proofs in the full information setting are a simple consequence of the existing theory and the geometric lemma of Zhang and Sra.  The regret in this setting is increased (with respect to the Euclidean case) by a factor of a natural geometric constant depending on the diameter of the optimization set and a lower bound on the sectional curvature of the manifold. The analysis is an immediate consequence of the Euclidean analysis and a previously given geometric lemma in Zhang and Sra 2016 (actually the analysis is essentially the same as the analysis of Theorem 9 and Theorem 11 in that paper).\n\n\nThe main contribution of this work is, in my view, the algorithm for the bandit case, which requires more geometric machinery to be obtained. The final pseudoregret upper bound worsens with respect to the Euclidean case by a factor that contains some \"constants\" that among other things, depend on the dimension. (there is also the detail that for their bound to be true T must be quite large, but I consider this to be a less important detail). This is a nice result, but I think that regardless of the final value, a bound on those \"constants\" should be provided.\n\n**Some important \"constants\" are not worked out: $\\\\epsilon(n)$ and $\\\\rho$**\n\nTheir magnitude should be provided in the form of a bound. \\\\rho appears in the regret and \\\\epsilon(n) appears in the lower bound required for T by the regret theorem. The \"constants\" depend on the dimension, bound on the sectional curvature and diameter, and the paper without providing a magnitude of these constants is incomplete.\n\n\n**Mathematical typos (not serious, I believe)**\n\nIn Table 1: the lower bounds should use \\Omega\n\nPseudocode of Algorithm 1 is not using the learning rates provided as input.\n\nIn the equalities before (27), after 'Applying Lemma 9 again, we obtain', after the first equality I believe one should be adding the 1/V_\\delta times the integral of the divergence (as opposed to substracting). I believe the same conclusion reached in (27) can be reached though.\n\nIn the last page of the appendix, I believe there is a \\kappa missing in the second summand of the rhs of the first inequality (and then the error carries forward) after 'Moreover, we get'\n\nAlso, the last equality of that set of lines seems to have the wrong constants. In particular, the r disappears despite of it being part of \\delta. And the 2 that is in front of T^{3/4} seems to belong to the \\sqrt{\\Delta} inside the parentheses.\n\n\n**Experiments**\n\nThe learning rate in the hyperbolic case seems to have been taken constant. Which I guess it is fine since the aim is to showcase the applicability of the method, but it should be reported in the main paper.\n\nAbout the learning rate in the SPD, I might be wrong, but I think L should be equal to D in this case and therefore it should be \\\\eta_t = \\\\sqrt{tanh(D\\\\kappa)/(D\\\\kappa t)}, which is not the same thing that appears in the code\n\n\n**Other comments**\n\nIn the comparison with related work it is said that \"[12], [37], [38], [36]  assume prior knowledge of loss functions which is different from the framework of our R-OCO\". While this is true, and as pointed out above, the analysis of some theorems in 37 is almost identical to the analysis of the full information case in this paper, while you seem to be implying they are very different things. This is essentially because the analysis provided is a mirror descent like analysis (but working with the \\\\ell_2 norm only) \n\nOther works have made other uses of mirror descent analyses in Riemannian manifolds, and though they apply to the offline setting, there are connections between those and the online learning setting. For instance the paper \"Global Riemannian Acceleration in Hyperbolic and Spherical Spaces\" defines a mirror descent type of method and combines it with a gradient descent method to obtain acceleration.\n\nl277 while it is true that f_t is 2-strongly convex, a citation to such a result should be provided, since it is not obvious a priori this is the case for someone that does not work in the field.\n\n\n\n**Conclusion** \n\nWhile I think the paper is interesting and of value, I think it needs some changes before it can be published. The magnitude of the \"constants\" \\epsilon(n) and \\rho should be worked out. There are some mathematical typos that need to be fixed.\n\n\n---\n\nThere are other non-math typos that I list below:\n\nThe Assumption environment contains a typo so all assumptions say \"Assmuption\"\n\nl41 'can be much expensive' rephrase\n\nl88 'However, These studies' typo in capitalization\n\nl122 'A function...' -> 'A differentiable function'\n\nl143 'with the diameter D' ->  'with diameter D'\n\nl163 'Theorems 1 and 2 also reveals' -> 'Theorems 1 and 2 also reveal'\n\nl179 'In the following of this section' -> In the rest of this section\n\n\nAlgorithm 2. The for has two 'do's\n\nl203 In equation (2) it should be \\tilde{g}_t instead of \\tilde{g_t} \n\nl206 'expected gradient descent method' Do you mean stochastic gradient descent method? If not, please clarify or provide a citation that defines expected gradient method\n\nl220 space missing after '(2)'. Note that in l213 there is a space after '(1)'\n\nl224 'qudratic' typo\n\nl235 'The first part of the lemma proceeds the result in [18]' rephrase\n\nl237 'that transform' ->  'that transforms'\n\nl256 '5-7 holds' -> '5-7 hold'\n\nl443 'lisence' -> 'license' \n\n\nThe lines in the appendix should be numbered. \nIn the equation below (5) there is f(x^\\star) that should be f_t(x^\\star). Same for the equation after (6)\n\n'by the strongly convexity' -> 'by the strong convexity' \n\nin the second line of the inequality preceding (11), there is an L that should be a 1\n\nLemma 10 'Let M be a n-dimensional' ->  'Let M be an n-dimensional'\n\n'is consist of' -> 'consists of'\n\nIn (19) the first V_r should have (x) not (\\kappa)\n\nproof of lemma 2 'without the loss of generality' ->  'without loss of generality'\n\nafter (25). It says it is by Lemma 6 but it is by Lemma 1\n\n'and become a Jacobi field' -> 'and becomes a Jacobi field'\n\nAfter 'Let us look back on the function', there is \\gamma_{0}(s). This notation is not consistent with the notation used before, that had the s in the subscript.\n\nIn the equation below that one you have \\gamma_1(s) = exp_{\\xi(s)}(V(s)) but it should be \\gamma_1(s) = exp_{\\xi(s)}(V(\\xi(s)))\n\nlemma 11 'with the diameter D' -> 'with diameter D' ; Also 'are a series of smooth functions and there exists' ->  'be a series of smooth functions and assume there exists'\n\npage 25 'To estimate the term E' E is not using mathbb. Same at the end of the page\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": "12"}, "extra_text": {}}, {"review_id": "HfibYNBY30D", "reviewer": "Reviewer_BgPU", "summary": "The paper proposes Riemannian variations of online optimization problems. Two algorithms (one in the general case and one for bandits) are proposed for (strongly) geodesically convex functions. Error bounds are derived under various regularity conditions on the manifold. The algorithm is evaluated numerically on computing Karcher means.", "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 paper is easy to read and follow\n* The subtleties when working on Riemannian manifolds are addressed well\n\nWeaknesses\n\n* The applications of online learning on Riemannian manifolds are questionable. \n\nComments\n\n* I would $\\textbf{strongly}$ recommend using Fréchet mean instead Karcher mean in the paper. The two refer to the same thing, but Karcher himself has noted that terminology of \"Karcher mean\" arose in the 90's and misasigns contribution [1].\n* On that note, I would also recommend incorporating some more recent work on the application of Fréchet means [2, 3, 4]\n* In particular, the Riemannian batch normalization algorithms of [2, 3] could be of potential interest, as one must maintain a moving average of previous data points as one updates the network.\n\nVerdict\n\nThe proposed method is technically sound and the paper is well structured. Outside of my comments, I believe this to be a strong paper. As such, I tend accept.\n\n[1] https://arxiv.org/abs/1407.2087\n[2] https://arxiv.org/abs/1909.02414\n[3] https://arxiv.org/abs/2003.00335\n[4] https://arxiv.org/abs/1111.3120\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "FmqWzJxi6_R", "reviewer": "Reviewer_Aqzk", "summary": "The paper considers the problem of online optimization over manifolds of negative curvature (Hadamard) in the full-information and bandit setting, providing upper bounds for the regret which match the Euclidean case. Prior work has considered the same problem in a zero-order oracle regime and provided only asymptotic results. The theoretical analysis is an adaptation of [40] in the convex case and [18] in the strongly-convex case, using the law of cosines for geodesic triangles on Hadamard manifolds developed in [37] and new geometric results based on the extra assumption of homogeneity. Experimental results in the simple problem of Karcher mean estimation are also included. ", "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": "Originality: I find the main idea of the paper to be a reasonable continuation of previous trends in Riemannian Optimization, thus I am not surprised by its originality. Riemannian methods have gain interest during the last years due to applications in important problems relevant to neurips community (e.g. operator scaling). Technically, the work adapts directly theoretical analysis from the Euclidean case taken from previous work, surpassing obstacles occuring by the geometry of manifolds. In the convex case the well-known law of cosines developed in [37] (which has been used in numerous papers in the area) turns to be enough for a simple adaptation, but in the strongly convex case the authors develop a way to compute the gradient of the integral of a volume form exploiting the assumption that the manifold is homogeneous and the existence of Killing vector fields implied by it. They also prove a sub-convexity property for the same \"smoothed loss function\" and the deviation from convexity turns out not to affect the final regret bound critically. This is because the extra \"Riemannian\" term appears in the bound as $\\lambda T$ and there is anyway a term $2 \\alpha c T$ even in the Euclidean case.\n\nObjections: \nI think that the proof of commutativity of gradient and integral can still be done in the manifold case and without homogeneity. The integral of a differential form can be written by definition as the sum of pullbacks of the function through different charts of a coordinate system choosing some partition of unity. Here the manifold is of negative curvature, thus the ball $B_{\\delta}(x)$ can be covered only be one system of coordinates (geodesically normal coordinates based at point $x$). Thus the covariant derivative at $x$ is going to become covariant derivative at $0$ in the geodesically normal coordinate system (should be easy to check using the definition of derivative with limits) and now you have the derivative of an integral over the lift of $B_{\\delta}(x)$ in the tangent space $T_x M$. You can now put the derivative inside the integral, do the chain rule, and use that the differential of geodesically normal coordinates at the origin is the identity and arrive to the result. Do I miss something?\n\nRegarding the sub-convexity result (lemma 2), I again doubt that homogeneity is essential but didn't have time to check in detail. I worry a bit about the constant $\\rho$ which is defined as the supremum of the divergence of a vector field over the working geodesically convex domain. At least this constant is $0$ in the Euclidean case because the isometry $\\phi$ can be chosen to be the identity thus $V=0$ and the Euclidean case is recovered, still it is pretty unclear how such a constant depends on the curvature and a bound for the domain $\\bar {K}$. Could for instance $\\rho$ depending exponentially bad on the domain? This is important in my opinion and an answer could be provided by a formula of divergence based on the determinant of the metric and partial derivatives of it, that the authors could find easily on the internet.\n\nRegarding related work, I am not familiar enough with the literature in online learning to have a strong opinion, the paper though explains clearly the difference with [28], which seems to be in the same topic.\n\nQuality: The paper is technically adequate for the area of Riemannian Optimization. As noted above, I think that it introduces unnecessary technicalities and assumptions. I would like to see some intuitive explanation for the necessity of homogeneous assumption and the resulting existence of Killing vector fields, homogeneous manifolds though are already a rich class of practical cases for machine learning tasks. The paper is sufficiently complete, two things that I think are important: i) I don't see the reason that manifolds of positive curvature are not treated, usually optimization behaves even better on positive curvature. Such an algorithm on the sphere (which is homogeneous) could serve as excellent basis for online PCA which is an important problem. ii) I find the experimental section quite poor because it considers only the (in most cases) strongly convex problem of Karcher mean estimation. Another problem to implement on SPD manifold which is just geodesically convex is operator scaling.\n\nClarity: The paper is in general clearly written, there are parts that are difficult to be followed by readers without strong background in geometry, but this is the case with lots of papers in the area. Below are some minor comments about readability and typos:\n\nAlgorithm 1: the step-size $\\eta_t$ is missing\n\nLemma 10: I find the notation $V_r(p)$ misleading, since the volume of the ball of radius $r$ centered at $p$ does not depend on $p$ because of homogeneity. Then $V_r(\\kappa)$ is introduced for a similar ball in a model space, I think this notation must be improved.\n\n224: \"quadratic\"\n\nI don't understand the reason that the step-size is denoted $\\eta_t$ in full-information and $\\nu$ in bandit (since the last is also time-dependent). I see that the authors adopted the notation from the relevant Euclidean papers, but since both cases are presented in the same paper now, one notation needs to be used.\n\n\nSignificance: The results are added to the big literature of Riemannian algorithms, with significance for neurips community due to its practical applications. The authors comment that do not treat the even more practical case of retraction-based gradient descent which would be useful, but still the exponential map is computable in SPD and hyperbolic space. Overall, I believe that the paper contains non groundbreaking but good to know results towards the correct direction.\n\nGiven all the above, I believe that the paper is a good contribution, but has issues that could make a second reviewing round beneficial. Thus in my opinion it is slightly above acceptance.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed some of the limitations of their work, but didn't discuss others, as mentioned in the completeness part above. Also, I worry for the constant $\\rho$ which appears in the upper bound inside $\\Lambda$ and some care should be taken about it.\n\nThere is not direct societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "ADEebnkqzUG", "reviewer": "Reviewer_7KFW", "summary": "In this paper, the authors derived Riemannian online learning algorithms with first-order derivative information on Hadamard manifolds, with various problem settings (including full information geodesically-convex, full information geodesically-strongly-convex and bandit feedback). In each setting, the authors proved the regret of their proposed algorithms matched their vector space counterparts (up to Riemannian geometric constants). In deriving their proofs, the authors introduced new analytic tools and insights to Riemannian optimization research, which could facilitate further developments in this area.", "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": "Originality:\n\n-- The Riemannian geometry analysis of Lemma 1 and Lemma 2 seems to be highly original in the Riemannian optimization community. The other parts of their results are original as well, especially since they need to envision using Riemannian geometry lemmas such as Lemma 1 to alleviate challenges blocking a direct generalization of the vector space analysis.\n\nQuality:\n\n-- I find the paper well-written and the results convincing. The authors also carefully reviewed related work. The experiments do not seem exciting from a practical viewpoint, but they are sufficient to support the theoretic results.\n\nClarity:\n\n-- The paper presents ideas clearly and is easy to follow. Each assumption and claim (lemma / theorem) is preceded or followed by some discussion of its implication, to help the readers navigate through the development.\n\n-- Possible typo: Line 288, should probably be \"R-OGD-SC converges faster than that of R-OGD-C ...\"\n\nSignificance:\n\n-- This paper is the first to generalizes finite iteration regret bound analysis to Riemannian online learning algorithms.\n\n-- Riemannian geometry lemmas such as Lemma 1 and Lemma 2 provide new analytic tools to analyze optimization and learning problems on Riemannian manifolds.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations of their work. No specific potential negative societal impact is introduced by this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers online optimization problems in Hadamard manifolds - i.e., simply connected, complete Riemannian manifolds with everywhere non-positive sectional curvature. The authors consider several different settings - full-gradient versus gradient-free algorithms against both convex or strongly-convex objectives - and they provide bounds that mirror the corresponding bounds for the Euclidean case.

The reviews speak for themselves and the concerns raised during the review phase were addressed by the authors. As a result, there were no reservations about making an "accept" recommendation.

In preparing the camera-ready version of their paper, the authors should make sure to include all the comments made by the reviewers. In addition, I would have the following recommendations/questions:
- An aspect which has regrettably been overlooked in the paper is what the Hadamard requirement really means. By the Cartan-Hadamard theorem, every $n$-dimensional Hadamard manifold is diffeomorphic to $\mathbb{R}^n$, so the topology of these manifolds is trivial. This is a crucial limitation, because barycentric constructions cannot be defined otherwise (at the very least, not easily), and it is not possible to use the theory of the paper to solve optimization problems defined on, say, a matrix group – like the set of invertible matrices $\mathrm{GL}(n)$, or the set of orthogonal matrices $\mathrm{O}(n)$. The paper doesn't make any such allusions but, at the same time, it's important to state clearly - and early - that Hadamard manifolds are topologically (and diffeomorphically) trivial.
- The section on Riemannian manifolds should be expanded, and the authors should be careful with the notation they employ: I am strongly in favor of representing vector fields as differential operators (which they do, sometimes explicitly other times implicitly), but this should be carefully explained, and some elements of the appendix should be transferred to the main text. In this regard, the authors might find helpful Lee's textbooks on smooth and Riemannian manifolds - the notation is already quite close, so this would essentially be a matter of fixing a few glitches, as in the definition of the Hessian.
- I would also be curious to see a comparison between the authors' work and recent Riemannian approaches to online optimization like the 2019 ICLR paper by Bécigneul and Ganea ("Riemannian adaptive optimization methods") and the 2020 ICLR paper by Antonakopoulos et al. ("Online and Stochastic Optimization beyond Lipschitz Continuity: A Riemannian Approach"). A more detailed presentation of previous works on the topic - like Bonnabel's (2013) paper - would also help with the positioning of this work. [To be clear, the settings and results are quite different and there is no issue of an overlap, but explaining these differences would be helpful to the reader]
Decision: Accept (Poster)