Riemannian Projection-free Online Learning
Authors: Zihao Hu
Guanghui Wang
Jacob Abernethy
Venue: NeurIPS 2023 poster (2023)
Keywords: Online learning
Riemannian optimization
projection-free optimization
TL;DR: We study projection-free online optimization on Riemannian manifolds and get several sublinear regret guarantees.

Abstract: The projection operation is a critical component in a wide range of optimization algorithms, such as online gradient descent (OGD), 
for enforcing constraints and achieving optimal regret bounds. However, it suffers from computational complexity limitations in high-dimensional settings or 
when dealing with ill-conditioned constraint sets. Projection-free algorithms address this issue by replacing the projection oracle with more efficient optimization
 subroutines. But to date, these methods have been developed primarily in the Euclidean setting, and while there has been growing interest in optimization on 
 Riemannian manifolds, there has been essentially no work in trying to utilize projection-free tools here. An apparent issue is that non-trivial affine functions 
 are generally non-convex in such domains. In this paper, we present methods for obtaining sub-linear regret guarantees in online geodesically convex optimization 
 on curved spaces for two scenarios: when we have access to (a) a separation oracle or (b) a linear optimization oracle. For geodesically convex losses, and 
 when a separation oracle is available, our algorithms achieve $O(T^{\frac{1}{2}})$, $O(T^{\frac{3}{4}})$ and $O(T^{\frac{1}{2}})$ adaptive regret guarantees in the full
  information setting, the bandit setting with one-point feedback and the bandit setting with two-point feedback, respectively. When a linear optimization oracle is 
  available, we obtain regret rates of $O(T^{\frac{3}{4}})$ for geodesically convex losses 
and $O(T^{\frac{2}{3}}\log T)$ for strongly geodesically convex losses.

Riemannian Projection-free Online Learning
Zihao Hu', Guanghui Wang', Jacob Abernethy
College of Computing. Georgia Institute of Technology Google Research"
(zihaohu, (aaachuuggaagg36 edu, abernechyj@googee.com
Abstract
The projection operation is a critical component in a wide range of optimization algorithms, such online gradient descent (OGD), for enforcing constraints and achieving optimal regret bounds. However, suffers from computational complex- ity limitations in high-dimensional settings when dealing with ill-conditioned constraint sets. Projection-free algorithms address this issue by replacing the projection oracle with more efficient optimization subroutines. But to date, these methods have been developed primarily in the Enclidean setting, and while there has been growing interest in optimization on Riemannian manifolds, there has been essentially no work in trying to utilize projection-fis free tools here. An apparent issue is that non-trivial affine functions are generally non-convex in such domains. In this paper, we present methods for obtaining sub-linear regret guarantees in online geodesically convex optimization on curved spaces for two scenarios: when we have access to (a) separation oracle or (b) linear optimization orucle. For geodesically convex losses, and when a separation oracle available, our algo- rithms achieve O(T'/s), O(T%/4) and (T) adaptive regret guarantees the full information setting, the bandit setting with one-point feedback and the bandit setting with two-point feedback, respectively. When linear optimization oracle is available, we obtain regret rates O(T"/") for geodesically convex losses and (1 log T') for strongly geodesically convex losses.
1 Introduction
Online convex optimization (OCO) offers a framework for modeling sequential decision-makin problems (Hazan et al. 2016). The standard setting depicts the learning process zero-sum game between a learner and an adversary. At round t, the learner selects a decision x; from a convex set K. and observes the encountered convex loss function ft. The learner's goal is to minimize regret, defined as
Regrety = Σ f((x)) min XEA
f(()).
1=11
1=1
In Fuclidean space, OCO boasts a robust theoretical foundation and numerous real-world applica- tions, such as online load balancing (Molinaro (017). optimal control (Li al. 2019), revenue maximization (Lin et al. 2019). and portfolio management (Jézéquel et al. 2022). The standard approach for OCO is online gradient descent (OGD), which performs
X(+1 Ixxxx V),,
where 11 represents the orthogonal projection onto K,, ensuring the sequence {x,]7_ remains feasible. However, the projection operation can be computationally expensive in high-dimensional or complex feasible sets. Projection-free online learning provides a reasonable way to handle this situation. At the heart of this approach is the understanding that, in many cases, the complexity of
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table I: Summary of main results. Our approach allows invoke either Separation Oracle (SO) or Linear Optimization Oracle (LOO) for (T) times throughout the rounds. Notably, our results match those presented by Garber & Kretzu (2022).
Oracle
Losses
Feedback
Measure
Regret
esc-convex
full information bandit, one-point
adaptive regret
( Thm.
SO
gse-convex
expected adaptive regret
O(T Thm.
gse-convex
bandit, two-point
expected adaptive regret
O Thm.
LOO
gse-convex
full information
adaptive regret
O(T Thm.
strongly gsc-convex
full information
regret
O log T), Thm.
implementing an optimization oracle can be significantly lower than that of the orthogonal projection. As result, both practical and theoretical interests lie in replacing the projection operation with these optimization oracles. The two most well-known projection-free optimization oracles are:
(Linear optimization oracle) argmin (g. x)
XEK
and
(Separation oracle) g: (y - x, >0 E
Whereas much attention has been given to the development sub-lineat regret guarantees using optimization oracles in Euclidean space (Hazan & Kale, 2012) Levy & Krause 2019 Hazan & Minasyan 2020 Wan et al., 20222] Garber Kretzu 2022] Mhammedi 2022a] Wan et al. 2023), there considerably less research
cenpecttio-freee optimization on Riemannian manifolds. There numerous scenarios where the space feasible parameters is not a convex subset Euclidean space, but instead has a manifold structure with a Riemannian metrie; examples include non-negative PCA (Montanari & Richard 2015), K-means clustering (Carson et al. 2017) and computing Wasserstein- Barycenters (Weber & Sra (2022)). However, there has been significantly less research efficiently computing projections or projection-free optimization the Riemannian setting, even for highly- structured geodesically convex (gsc-convex) feasible like:
K
{x] 1sism
hx(x))
where each (x) is gsc-convex. In this paper focus projection-free optimization on Riemannian manifolds in the online setting. A Riemannian version of Online Gradient Descent (R-OGD) was given by Wann al. (2021):
X Ixxx (-ne (x)x)))
where I. is a gsc-convex and 1Ię is the metric projection onto K. This method achieves sub-linear regret guarantees for Riemannian OCO. The metric projection is often the most expensive operation, and it is not always clear how implement on manifold. In the present work, propose the use of two alternative operations: a separation oracle (SO) or a linear optimization oracle (LOO) on the Riemannian manifold, with definitions deferred to Section 3 It important to note that, in Euclidean space, both oracles rely on the definition of hyperplane. In the realm of Riemannian manifolds, there are two natural extensions of hyperplane: one is the sub-level set of Busemann function, known as a horosphere (Bridson & Haefliger 2013); the other relies on the inverse exponential map, outlined in ( While a horosphere is gsc-convex, the corresponding separation oracle exists if every boundary point of the feasible gsc-convex set has a locally supporting horosphere (Borisenko 2002). The existence of a separation oracle is assured for any gsc-convex sets on Hadamard manifolds (Silva Louzeiro et al.) (022), if defined via the inverse exponential map. Hence, we adopt this latter definition.
worth noting that this object typically non-convex (Kristály et al. 2016), leading to geometric complexities that necessitate careful management. Also, our work builds upon the findings of Garber & Kretzu (2022) and inherits the adaptive regret guarantee for gsc-convex losses, as defined by Hazan & Seshadhri (2009):
Adaptive Regret,- := (..emm))
1E f((x;) minXeR Ei f(x))
Our main contributions are summarized in Table More specifically,

---

Given separation oracle, we attain adaptive regret bounds of O(T ((T")) and (+T for gse-convex losses in the full information setting. the bandit convex optimization setting with one- point feedback and the bandit convex optimization setting with two-point feedback, respectively.
Assuming access linear optimization oracle, we provide algorithms that enjoy ((T))) adaptive regret for gsc-convex losses and ( log T') regret for strongly gsc-convex losses.
We highlight some key differences between convex sets on Hadamard manifold and in Euclidean space. In particular, shrinking a gse-convex set towards an interior point does not preserve convexity. and the Minkowski functional on Hadamard manifold is non-convex. These results, which may not be well-known within the machine learning community, could be of independent interest.
The technical challenges of this paper can be divided into two parts.
Firstly, for the separation oracle, we need bound the "thickness" of part of the feasible set cut by the separating hyperplane. While in Euclidean space, this can be achieved through convex combination argument (Garber & Kretzu 2022), the task becomes challenging on manifolds due to the varying metric at different points and the non-convex nature of the separating hyperplane. Fortunately, this problem can be addressed using the Jacobi field comparison technique. Also, unlike in Euclidean space, one cannot directly construct a separation oracle for (1 - 8)AC using separation oracle for X. This poses significant challenges in the bandit setting. Nonetheless, we have identified a novel solution to this issue in the two-point feedback setting.
Secondly, in Euclidean space, the linear optimization oracle is typically invoked by online Frank- Wolfe (OFW) (Hazan & Kale 2012] Kretzu & Garber 2021) to achieve no-regret online learning. The analysis of OFW relies on the fact that the Hessian a linear function zero everywhere. But on Hadamard manifolds, such functions' existence implies that the manifold has zero sectional curvature
everywhere (Kristály et af.) (0T6). The algorithms in Garber & Kretzu (2022) do not require affinity and serve starting point for results. However, the analysis still needs to be conducted carefully due to the non-convexity of the separating hyperplane on manifolds.
2 Related Work
In this section, we briefly review previous work on projection-fres online learning in Euclidean space as well as online and projection-free optimization on Riemannian manifolds.
2.1 Projection-free OCO in Euclidean Space
Linear Optimization Oracle. The pioneering work of Hazan & Kale 2012) first introduced an
online variant of the Frank-Wolfe algorithm (OFW) and achieved (TT regret for convex functions.
Hazan & Minasyan 2020) proposed a randomized algorithm that leverages smoothness to achieve
(T expected regret. The insightful analysis of Wan & Zhang (022)) and Kretzu & Garber
(002 demonstrated that OFW indeed attains (T*))) regret for strongly convex functions. Garber &
Kretzu 2022) showed that it is possible to achieve (TT)44 adaptive regret and OTT log T) regret for convex and strongly convex functions, respectively. [Mhammedi (20226) illustrated how to obtain Ö(T%/s) regret for convex functions, where Ö(-) hides logarithmic terms. Our results are in line with those of Garber Kretzu (022) and inherit the adaptive regret guarantee.
Separation Oracle and Membership Oracle. Levy & Krause (0019) demonstrated that it is possible to achieve O(VT)) and (log T') regret bounds for convex and strongly convex functions when the feasible set is sublevel set of smooth and convex function. Mhammedi (2022a) generalized the idea of Levy Krause (0199) and showed how obtain O(VT) and Ollo T') regret guarantees for general convex sets. Garber & Kretzu (2022) provided algorithms that ensure O O(VT) and O(T3/44 adaptive regret guarantees for convex losses in the full information and bandit settings, respectively.
For the one-point feedback setting, we allow the point at which we play and the point where we receive feedback to differ, thereby bypassing fundamental challenge posed by Riemannian geometry. In the case of two-point feedback, however, we eliminate this non-standard setting.
3

---

2.2 Online and Projection-free Optimization on Manifolds
Online Optimization on Manifolds. Bécigneul & Ganea (2019) demonstrated that a series of adaptive optimization algorithms can be implemented each factor manifold being assigned a learning rate. [Antonakopoulos et al. (2020) proposed using Follow the Regularized Leader with a strongly gsc-convex regularizer to achieve O(VT) regret when the loss satisfies Riemannian Lipschitzness, |Wang et al. (2021) introduced Riemannian OGD (R-OGD) and showed regret guarantees in full information and bandit convex optimization settings. Hu al. (0233 considered achieving optimistic and dynamic regret Riemannian manifolds.
product of Riemannian manifolds, with
Projection-free Optimization on Manifolds. Rusciano (2018) provided a non-constructive cutting hyperplane method on Hadamard manifolds. By comparison, our algorithms are constructive and deterministic. [Weber& & Sra (2022b) proposed Riemannian Frank-Wolfe (RFW) for gsc-convex opti- mization and showed some practical applications on the manifold of SPD matrices. In subsequent work, Weber & Sra (002a) generalized RFW to the stochastic and non-convex setting. We use RFW subroutine invoke the linear optimization oracle and establish sub-linear regret guarantees. Hirai et al. (2023) implemented the interior point method on Riemannian manifolds and used a self-concordant barrier to enforce the constraint.
3 Preliminaries and Assumptions
In this section, lay the groundwork for our study by presenting an overview of Riemannian manifolds, the separation oracle and the linear optimization oracle within these spaces. Additionally, establish key definitions and assumptions that will be integral to the following sections.
Riemannian Manifolds. We provide key notations in Riemannian geometry that will employed throughout this paper. Readers looking for more comprehensive treatment are encouraged to consult Petersen (006);; Lee (018). Our proof also relies on the concept of the Jacobi field, and we provide some backgrounds in Appendix E.I We consider an n-dimensional smooth manifold .M equipped with a Riemannian metric g. This metric confers a point-wise inner product (u, v)x at every point E M,, where u, dimension n, encompasses all vectors tangent to x. The Riemannian metric also determines the norm of tangent vector u as: ||u|| == / (u, u). A geodesic (t) [0, c| + M is a piecewise smooth curve with constant velocity that locally minimizes the distance between its endpoints, say, and y. The Riemannian distance between these two points is given by d(x, y) == [ [t) = J (1)(0)] It's important to note that the Riemannian distance remains invariant under reparameterizations of (t). Consider a geodesic ?(t)= [0, 1] + .M with 70) = x, 711) y and 4(0) = v. The exponential map Expx(v) transforms v E T E M, and the inverse exponential map Expx performs the inverse operation, mapping y M to E M. The inverse exponential map also offers a handy way to express the Riemannian distance: d(x, y) = |Expx"y/
vectors in the tangent space T&M at This tangent space, vector space of
The sectional curvature at point x E .M is contingent on two-dimensional subspaces of Mx,, and describes the curvature near x. Generally, geodesics diverge on manifolds with negative sectional curvature, converge manifolds with positive sectional curvature, and manifolds with zero sectional curvature are locally isometric to Euclidean space. In line with Zhang & Sra (2016); Wang et al. (202I), we primarily explore Hadamard manifolds, which are simply connected manifolds with non-positive curvature that admit a unique global minimizing geodesic between any pair of points. A set IC M is geodesically convex (gsc-convex) if it includes the geodesic connecting and y for any x, y E JC. A p-strongly gsc-convex (or gsc-convex, when = 0) function f M - IR fulfills
f(y) f(x) + (vf(x), y) + gd(x,y)?
for any x.y E M, where fx(x) E T&M is the Riemannian gradient.
Optimization Oracles on Riemannian Manifolds. In this part, introduce the concept of separation oracle and a linear optimization oracle on Riemannian manifolds.
A separation oracle, given point y not in the gsc-convex set XC, returns non-convex separating hyperplane that satisfies the following condition:
(- (-Expy x.g) g) 0, Vx KC,
(2)

---

where g E Ty.M. Even with the non non-convexity of the separating hyperplane, for certain goc-eo
sets like IC = {x) maxigism hx(x) < 0} where each (x( is gso-convex, separation oracle can be
efficiently implemented by Lemma 18 and Remark
On the other hand, a linear optimization oracle is responsible for solving the following problem:
argmin (g. Expxxxx
XEX
on a gsc-convex set K. where X K and g E M. Although this objective is not gsc-convex, can still be solved in closed form for certain problems. Examples include computing the geometric mean and the Bures- Wasserstein barycenter on the manifold of SPD matrices (Weber & Sra (022b).
In this paper, we rely on a series of definitions and assumptions, which we introduce here for clarity and reference in subsequent sections.
The manifold M is Hadamard with sectional curvature bounded below by so the sectional curvature of M lies the interval [K. O.
Assumption 1.
Assumption 2. The manifold M is a homogeneous Hadamard manifold with sectional curvature bounded below by K. For every E [T]. the inequality lff(x)) < M holds. For the bandit setting with two-point feedback, we additionally require M to be symmetric.
Assumption 3.
The set K. .M is gsc-convex decision set and satisfies Bp(() S S (R). Here, Br(r) represents the geodesic ball centered at E K. with radius r.
& Assumption 4. For every E [T] and E (R), the function f((x) is gsc-convex (or strongly gsc-convex), and the norm of its gradient is bounded by G, ie., [[V S G.
Let us make two important comments. First, the homogeneity and the symmetry of A allows us to employ the unbiased estimator presented in Wang et al. (2023) for the bandit setting. It should be noted that homogeneous and symmetric Hadamard manifolds include two of the most commonly used ones: the hyperbolic space and the manifold of SPD matrices. Second, the projection onto a geodesic ball, denoted as (R: (-), ), is considered projection-free as can be computed to an c
precision using log('/4) bisections
Definition 1. We define a geometric constant ( as ( = 2R/-
Definition 2. Fixing p E for any c co), we define cKC = {Expp (cExp,'xx) xx)xxxx)Xxxx> E K.). Definition 3. We call ý E -M an infeasible projection ofy E M onto a simply connected closed set M if for every point z E Kc, the inequality d(ý, z) S d(y, z) holds. We define OIp(K,y) as an infeasible oracle for KC which, given any y. returns an infeasible projection of y onto K.
We note that, in Euclidean space where the sectional curvature is zero everywhere, we have ( lim 2R coth(2/t/ 1. We also observe that the definition of the infeasible projection in Garber & Kretzu (022) requires Æ to be convex, which is indeed unnecessary. This distinction OCO, we construct an infeasible projection oracle onto K (1 - K,, which may be non-convex (Theorem 6
essential because, the case of the epparation-oracl-bbieee
4 Warm-up: the High-level Idea
We briefly illustrate the overarching strategy of achieving regret guarantees. Our basic algorithm is Algorithm which generates a sequence [yr)²= by R-OGD that does not necessarily fall within the feasible set. A key insight is that we can build an infeasible projection oracle using either separation oracle or a linear optimization oracle, resulting in a sequence {yr)T= that exhibits a desirable regret guarantee (as shown in Lemma D The design of the infcasible projection oracle rests on a straightforward fact: whenever Yt deviates significantly from IC, we can call upon either oracle to produce descent direction and then apply Lemma 2 to gauge the progress. Additional error terms, arising from the fact that y, may not necessarily lie in IC, can be quantified by leveraging the boundedness of the gradient in Assumption 4
2This fact well-kkoo aell-knownnn in Euclidean space Gröttcchll et al. 2012.. but it appears we are the first to observe its counterpart on manifolds.
A comprehensive explanation of this observation can be found in Remark 5
5

---

Algorithm 1: Infeasible Riemannian OGD
Data: horizon T, feasible set K, step-sizes {n Yr infeasible projection oracle O (Ir(K..))
for ,,..., .T do
Play y:, and observe (ft)
Update y++1 = ExPy. (- (()))))) and set ÿ,+1 = (Ir(K,
end
We have the following guarantee for Algorithm T
Lemma 1. (Proof in Appendix A.7) Assume yt E (p(R) and let V, = f((E)) and K. S (R) be
a gsc-convex subset of M. Consider C K. as simply connected and compact set, and O (Ip(K.)) be an infeasible projection oracle as Definition
1) Suppose all losses are gsc-convex on (R).. Fix some rj > and let nye 1) for all 2
Algorithm 7 guarantees that the adaptive regret is upper-bounded by:
1A = ss S [T] Σ f(()) min E f((x)) S x(ys:x1) XIER
n
De 2118
Vell
21
2
2) Suppose all losses o-Strongly gsc-convex Bp (R) for some a Algorithm 7 guaranttes that the static regret is upper bounded by:
>> 0. Let m3 or for all 1
T
T
T
V
f((5))
min Σ f((x XEX
2at
Remark 1.
To apply Lemma we need to ensure that Yr E (R) for any [T). In the case of
separation oracle, we have K. = (1 - 5)K for some E (0, 1), and ÿc E C (p(R) by Lemma With linear optimization oracle, we have K. = K. and ÿ. E (R) is guaranteed by Lemma 6
Lemma 2. (Proof in Appendix A.22) Consider K S K. C IB BP() as simply connected and compact subset of M. y & K and g E My.M satisfies (Expy z. 2 Q, where Q > 0, then consider For र0 and ||g|| S C. assume d(y 2) S 2R, then we have
y
d(ý,z)² < d(y 2)
q² [C
Unlike Garber & Kretzu 2022), in Lemma
we also do not require to be gsc-convex.
Riemannian OCO with a Separation Oracle
In this section, we show how to use separation oracle to construct an infeasible projection or- acle and achieve sublinear regret guarantees. We note that we rely on an infeasible projection oracle onto (1 - 8)AC rather than directly onto K. While we have a separation oracle that re- sults in (-Exp, x, g) > 0, using Lemma 2 on this separating hyperplane may lead to minus- cule progress, given that Q can be arbitrariyy small. Consequently, achieving sublinear regret with only O(T) oracle calls becomes unfeasible. In contrast, constructing an infeasible pro- jection onto (1 K)A always ensures meaningful progress, as quantified by Lemmas and
Algorithm 2: Infeasible Projection onto (1 - 8)A with a Riemannian Separation Oracle Data: feasible gsc-convex set K, radius r, squeeze parameter 8, initial point Yo.
y1 = Yo) for i 1,... do
y, & then
SOx returns ga satisfying (-Expy, x, g.)
Y+1 = Expy, (-rgg, where 7 Tg
58 and F defined in Equation 3
else
returny y y:
end
end

---

Lemma 3. (Proof in Appendix B.1) Let E p K and let g TyM be the output of the separation oracle for y. Then, under Assumptions and any z (1- 6)K, where
we have that (-Expy
or brllg] for g) 2,8., 2.g)
x2
r) sinh -
T.
(3)
sinh (onh(v-x(22m)
In Euclidean space, we can establish that (y g) > 6r gg Garber & Kretzu 2022 Lemma 11). However, as indicated in Lemma 3] the result on manifolds is significantly worse with respect to R. given the exponential nature of sinh. It is an interesting line of inquiry to explore whether this dependence unavoidable
3 to implement an infeasible projection oracle onto (1 - 5)K, the number of calls to the separation oracle is bounded in Lemma
Based on Lemma
Lemma 4. (Proof in Appendix
B.2) Under Assumptions and 3 Let 0 < < 1 and set = 6r
-
Algorithmm executes at most (1 -)x)) (1))))))))) iterations and returns y E K. such
52
that d(y, z)= S d(yo, z)² holds for any z (1 8)A.
In the full information setting, with separation oracle, infeasible R-OGD is shown in Algorithm 3
Algorithm 3: Infeasible R-OGD with separation oracle
Data: feasible gsc-convex set K, radius r, step-size and squeeze parameter d. y1 = p
5)K. for 1, ,....,T do
T
Play y, and receive (v)))
Y++1 = Exps, (+)
Update Ye+1 as the output of Algorithm 2 with set K,, radius r, squeeze parameter and initial point Y1+1-
end
We can show the following regret guarantee for Algorithm 3
Theorem 1. (Proof in Appendix B.3) Under Assumptions
and Set
2B GVCT
and 5 2/T
then the regret of Algorithm ( E minx/ex Ei f((x)) s GGRVCT.
3 upper bounded by
and the number of calls to the separation oracle is O(T).
Moving on, demonstrate how to achieve sublinear regret guarantee in the bandit convex optimization setting. A major challenge is that, while Buclidean space, we can construct a separation oracle on (1 - K using the separation oracle on A. (Garber & Kretzu 2022 Lemma 1 11.). On Hadamard manifolds, (1 - 8) can even be non-convex (Theorem 6) thus a separation oracle for (1 - 8) may not exist. For Riemannian BCO with one-point feedback, in Algorithm 4 we address this by resorting to non-standard setting: we play 2 E J. but we receive feedback at 2, where Z₁.
2, are nearby points. We present the algorithm and the corresponding regret guarantee in Algorithm and Theorem
Algorithm 4: One- -hint bandit convex optimization on manifolds with separation oracle T). Data: feasible gsc-convex set KC, radii (R, r), step-size 17, squeeze parameters ( ý1 for t 1,..., T do
= p.
Sample 2, Sy. (5'); play 2,
Expp
Expp 2, 1+7
/1 8' sinb((-<(R+r))
(=
EXpo |Eppy with K., radius r, squeeze parameter 5 and initial point Ys+1-
Observe fi(z.): g: = fz(ze)
Y1+1 Expy. (-7g:)
ÿtt1 < Output of Algorithm
2
end
'A exponential dependence on the diameter is common manifolds with strictly negative curvature. For instance, the volume of geodesic ball grows exponentially with its radius in hyperbolic space, whereas this dependence only polynomial in Euclidean space. This property has been leveraged to construct lower bounds for convex optimization on manifolds (Criscitiello Boumal 2022)
7

---

Theorem 2. (Proof in Appendix B. Under Assumptions and Ser = T 6 = T
=T
== T=T-2, Then regret of Algorithm is upper bounded by
(U 1 minxxeK Eims f((x))) = -
and the number of calls to the separation oracle is O(T).
Remark 2. An acute reader may notice a discrepancy between the step-size 1j O (T-)) our work and the step-size = = ( in Garber Kretzu (2022 Theorem 15). It is important to highlight that our 17 is equivalent to 8 as per Garber & Kretzu (2022). ensuring that the parameters are in fact consistent. This reasoning is also applicable to Theerem
Interestingly, in the context of the two-point feedback setting, we can get rid of the non-standard setting by adapting the algorithm. In Algorithm S we adhere to the loop invariants: Y: E IC. Each round involves constructing an unbiased gradient estimator gr at x2 using the two-point feedback. Subsequently, we map gr to the tangent space of Yı and execute online gradient descent in that space. A key advantage of this parallel transport is the ability to employ the separation oracle on K. to construct an infeasible projection onto - o). Upon meticulous analysis, we observe that, at each round, an additional distortion arises from this parallel transport:
E 3K and
Sg Eg y: Expy, x Expx, S
Billg: |] 0080 = 0(8),
V
This distortion accumulates to O(vT) when choosing 0 ensuring the regret bound remains unaffected. The regret assurance of Algorithm is detailed Theorem
Algorithm 5: Two-point bandit convex optimization manifolds with separation oracle Data: feasible gsc-convex set K. radii (R, r). step-size v) parameters (6, 8); E (0, 1), E (0, 1),
(3) (-x(R+r)
sinh Sinh(v-R(Rtr))
Initialize x1 E -3KK y1 Expp Expp 'x1
YKEK
for t f do
Sample 2, ~ (5') Play Z, and its antipodal point 2,
Observe ft at 2, and 2t
Construct ge by g: = (fe(zz) - fz()))
Exp |EEp= z.ll
y'+1 = Expy, [
ye+1 +- Output of Algorithm 2 with K., radius squeeze parameter and initial point y'
Xc+1 Expp (sExp, ye.1) // Xe+1 BK
end
Theorem 3. (Proof in Appendix
Under Assumptions upper bounded by
B.5
aand
Set = 1, = 3 T
then the regret of Algorithm
xx En(e))) }} -0(VT) (
sup [
E
min Σ f((z))
and the number of calls to the separation oracle OTT).
Riemannian OCO with a Linear Optimization Oracle
In this section, we focus on performing projection-free OCO on Riemannian manifolds utilizing linear oracle. The linear oracle is invoked inside the Riemannian Frank-Wolfe (RFW) algorithm (Weber & Sra 2022b). We outline how to obtain separating hyperplane by RFW, as detailed in Algorithm and Lemma

---

Algorithm 6: Separating Hyperplane via RFW
Data: feasible gsc-convex set K. error tolerance e, initial point K, target vector y.
for i = 1,... do
Vi = argmin 1( (-Expx, y, Expx/x))
if (Expx, y. Expx: vi) S or y( I 3e then
return x Xi end
argmin (d(y, Expx, (oExpx v.))) x++1 Expx, Ex,,xx v.)
(oExpx,vv)))
end
Lemma 5. (Proof in Appendix C.I Under Assumptions 7 aadd 3 For any y E (P).), Algorithm
terminates after at most ([ 2| iterations and returns x E K. satisfies:
1) y)² I d(x1,y)²
2) At least one of the following holds: d)x, 3E or VZ E K:: (Expy z, Expy xx) 2 2c.
3) If d(y, KC) S then d(x. y 3e.
Remark 3. Note that the second item of Lemma Lrrviidprovides a separating hyperplane between y and
K. One of the challenges in its proof is to find analog of the Euclidean identity (z -y y)
||X - 1 - (z x.y x) on manifolds, which initially appears to be a daunting task. However, a clever application of Lemma 30 (Appendix] E provides solution.
Algorithm 7: Closer Infeasible Projection via LOO
Data: feasible gsc-convex set K, X E K. initial point yo. error tolerance e, step size T.
Y1 = ( (n)No
if dl d(xo, )2 < 3e then
I return x Xo. y1. end
for i 1, 1,.... T do
X; f- Output of Algorithm with K,, feasible point x;-1, initial point y: and tolerance e. if (d( d(xx; y:)² > 3e then
Y41 = Expx, ((1 7) F)xxxx y:)
else
return X + x + Ys.
end end
Algorithm demonstrates how to "pull" an initial point Yo towards using RFW, while Lemma verifies that the output of Algorithm is indeed an infeasible projection onto K.
Lemma 6. (Proof in Appendix
C.2 Under Assumptions
and 3 Fix O. Setting 7
2r 1, iterations, and returns (x,y)
2(xo.yo)²
Algorithm stops after at most max <d(xo.vo) No)
de
K. x B R) such that
Y d(y,2)² S d(yo. 2)2 and y)² 3c.
Given that Lemma 6 provides infeasible projection oracle, we can combine Algorithms 1 and 7 to
achieve sublinear regret by setting error tolerance as o(1). However, RFW requires (1//)
w(1) iterations in the worst-case scenario (Lemma and the resulting algorithm necessitates (7)
calls to the linear optimization oracle. Garber & Kretzu (2022) utilize a block trick to address this challenge: the time horizon T is broken into B blocks, and the infcasible projection is computed once in each block. We demonstrate that this trick can be implemented on Riemannian manifolds in Algorithm & We present the regret guarantees for gsc-convex and strongly gsc-convex losses in Theorem and Theorem respectively.
Theorem (Proof in Appendix C.3) Under Assumptions and Fixing Th and e; as 7 R
and e = 60 2 respectively, for any i E {1, ..... Setting B = 1/2, Then the regret of

---

Algorithm 8: Block OGD on manifolds with a linear optimization oracle
Data: horizon T, feasible gsc-convex set K, number of blocks B, step-sizes (mirer error
tolerances {<i) 1=1
Choose Xp, x E
Yo = Xo, 1..... , B do
Xo. Y1= = X1, V = 0 M
for f
Play Xo: observe (x0)
V = V + (fo)
end
YB+1 = Expy, y. (-72 V1).
for i ..... T
1 do
(.) E k
Bp (2) output of Algorithm 7
with input K, x;-2, 1(1-1)B41 and e;.
Y(t-1)B+1 yi-1i V. 0 E Ty.
for 8 = 1,.... B do
Play x and observe (x( V. V. + (+
end
Y.B+1 Expy Vi). end
Algorithm 8 for gsc-convex losses is bounded by
5 (2 + CV1807 + +4T% + 20T min Emooil s GR XIEK t=s
[((x))
sup 1=
and the number of calls to the linear optimization oracle is bounded by T.
Theorem 5. (Proof in Appendix C.4) Under Assumptions 1 3and
Suppose all losses {f)
are a-stroogly gsc-convex for some known a: > 0 and T 2 3B. Choosing = a(i+3)
20G
and
1 aiB for any I,..., B. With B (aR) 3 T and assume T 3B, the regret guarantee of Algorithm is bounded by
Σ f(xx)
T
min xEK
f(()
(20/35 D)(G*
1
2 2
In 3
VTG
aR
And the number of total calls to the linear optimization oracle is bounded by CT.
7 Conclusion and Perspective
This paper pioneers the exploration of projection-free online optimization on Riemannian manifolds. The primary technical challenges originate from the non-convex nature of the Riemannian hyperplane and the variable metric. These challenges are tackled effectively with the aid of the Jacobi field comparison, enabling us to establish spectrum of sub-linear regret guarantees. Interested readers may question the difficulty of generalizing these techniques from Hadamard manifolds to CAT(s) manifolds. Some hints toward this generalization are provided in Appendix F..
There are several promising directions for future research. First, there exists the potential to refine the regret bounds, particularly for strongly gsc-convex losses via separation oracle. In the context of the separation oracle, reducing the dependence on the number of calls about the diameter of the decision set would be an intriguing objective. Moreover, devising an efficient method to optimize the linear optimization oracle objective, argmin (g. Exp=, x)), remains a notable open problem. This paper does not discuss the membership oracle, primarily because related work (Mhammedi) [022a]] Lu et al.) 2023) heavily relies on the convexity of the Minkowski functional in Euclidean space, property not guaranteed to hold on Hadamard manifolds (Theorem 7). However, this does not rule out the potential for executing OCO or convex optimization on manifolds using membership oracle. Thus, uncovering alternative strategies to tackle this issue remains compelling research question.
10

---

Acknowledgments
We would like thank five anonymous referees for constructive comments and suggestions. We gratefully thank the AI4OPT Institute for funding, as part of NSF Award 21 22533... We also acknowl- edge the NSF for their support through Award 118-1910077. GW would like to acknowledge an ARC-ACO fellowship provided by Georgia Tech. We would also like to thank Xi Wang from UCAS and Andre Wibisono from Yale for helpful discussions.
References
Ahn, K. and Sra, S. From nesterov's estimate sequence riemannian acceleration. In Conference on Learning Theory, pp. 84-118. PMLR, 2020.
Alimisis, F., Orvieto, A., Bécigneul, G., and Lucchi, A. A continuous-time perspective for modeling acceleration in riemannian optimization. In International Conference on Artificial Intelligence and Statistics, pp. 1297-1307. PMLR, 2020.
Antonakopoollos K., Belmega, R. V., and Mertikopoulos, P. Online and stochastic optimization beyond lipschitz continuity: riemannian approach. In ICLR 2020-nnttrnationall Conference on Learning Representations, pp. 1 1-20, 2020.
Bacák, M. Convex analysis and optimization in Halamard spaces. de Gruyter, 2014.
Bécigneul, G. and Ganea, O. Riemannian adaptive optimization methods. In 7th International Conference on Learning Representations, 2019.
Borisenko, A. Convex sets hadamard manifolds. Differential Geometry and its Applications, 17 (2-3):111-121, 2002.
Bridson, M. R. and Haeflige,, A. Metric spaces of non-positive curvature, volume 319. Springer Science & Business Media, 2013.
Carson, T., Mixon, D. G., and Villar, S. Manifold optimization for k-means clustering. In 2017 International Conference on Sampling Theory and Applications (SampTA), pp. 73-77. IEEE, 2017.
Criscitiello, C. and Boumal, N. Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles. In Conference on Learning Theory, pp. 496-542 PMLR, 2022.
Garber, D. and Kretzu, B. New projection- algorithms for online convex optimization with adaptive regret guarantees. arXiv preprint arXiv:2202.04721, 2022.
Grötschel, M., Lovász, L.,, and Schrijver, A. Geometric algorithms and combinatorial optimization, volume 2. Springer Science Business Media, 2012.
Hazan, E. and Kale, S. Projection-fis online learning. arXiv preprint arXiv:1206.4653 2012.
Hazan, E. and Minasyan, E. Faster projection-free online learning. Conference on Learning Theory, pp. 1877-1893, PMLR, 2020.
Hazan, E. and Seshadhri, C. Efficient learning algorithms for changing environments. In Proceedings of the 26th annual international conference on machine learning, pp. 393-400, 2009.
Hazan, E. et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
Hirai, H., Nieuwboer, H., and Walter, M. Interior-pole point methods on manifolds: theory and applications. arXiv e-prints, pp. arXiv-2303, 2303, 2023.
Hu, Z., Wang, G., and Abernethy. J. Minimizing dynamic regret on geodesic metric spaces. arXiv preprint arXiv:2302.086:: 00..2222...6. 2023.
Jaggi, M. Revisiting frank-wolfe: Projection-free sparse convex optimization. International conference machine learning, pp. 427-435. PMLR, 2013,

---

Jézéquel, R., Ostrovskii, D. M., and Gaillard, P. Efficient and near-optimal online portfolio selection. arXiv preprint arXiv:2209. 2022.
Kowalski, O. and Vanhecke, L. Ball-homogeneous and disk-homogeneous riemannian manifolds. Mathematische Zeitschrift,, 180:429-444 444, 1982.
Kretzu, B. and Garber, D. Revisiting projection trrectioo--reeeeeeo online learning: the strongly convex case. In International Conference on Artificial Intelligence and Statistics, pp. 3592-3600. PMLR, 2021.
Kristály, A., Li, C., López-Acedo, G., and Nicolae, A. What do 'convexities" imply hadamard manifolds? Journal of Optimization Theory and Applications, 170:1068-1074, 2016.
Lee, J. M. Riemannian manifolds: an introduction to curvature, volume 176. Springer Science Business Media, 2006.
Lee, J. M. Introduction to Riemannian manifolds, volume 2. Springer, 2018.
Levy, K. and Krause, A. Projection free online learning over smooth sets. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1458-1466. PMLR, 2019.
Li, Chen, X., and Li, N. Online optimal control with linear dynamics and predictions: Algorithms and regret analysis. Advances in Neural Information Processing Systems, 32, 2019.
Lin, Q., Yi, H., Pang, J., Chen, M., Wierman, A., Honig, M., and Xiao, Y. Competitive online optimization under inventory constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3(1):1-28, 2019.
Lu, Z., Brukhim, N., Gradu, P., and Hazan, E. Projection-free adaptive regret with membership oracles. International Conference on Algorithmic Learning Theory, pp. 1055-1073, PMLR, 2023.
Mhammedi, Z. Efficient projection-free online convex optimization with membership oracle. In Conference Learning Theory, pp. 5314-5390. PMLR, 2022a.
Mhammedi, Z. Exploiting the curvature of feasible sets for faster projection-free online learning. arXiv preprint arXiv:2205.11477 2022b.
Molinaro, M. Online and random-order load balancing simultaneously. In Proceedings of the Twehty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1638-1650. SIAM, 2017.
Montanari, A. and Richard, E. Non-negative principal component analysis: Message passing algorithms and sharp asymptotics. IEEE Transactions on Information Theory, 62(3):1458-144 1484, 2015.
Petersen, P. Riemannian geometry, volume 171. Springer, 2006.
Rusciano, A. A riemannian corollary of helly's theorem. arXiv preprint arXiv:1804.10738 2018.
Sakai, Riemannian geomelry, volume 149. American Mathematical Soc., 1996.
Silva Louzeiro, M.. Bergmann, R., and Herzog, R. Fenchel duality and separation theorem hadamard manifolds. SIAM Journal on Optimization, 32(2):854 873, 2022.
Udriste, C. Convex functions and optimization methods on Riemannian manifolds, volume 297. Springer Science & Business Media, 2013.
Wan, Y. and Zhang, L. Projection-free online learning over strongly convex sets. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10076-10084, 2021.
Wan, Y. Tu, W.W.., and Zhang, Online frank-wolfe with arbitrary delays. Advances in Neural Information Processing Systems, 35:19703-19715, 2022.
12

---

Wan, Y., Zhang, L., and Song, M. Improved dynamic regret for online foank-wolfe. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 3304-3327 PMLR, 12-15 Jul 2023. URL
mlr wttess/v195wwan2a.... .tmmlll
Wang, X., Li, C., and Yao, J.-C. On some basic results related to affine functions on riemannian manifolds. Journal of Optimization Theory and Applications. 170(3):783-803, 2016.
Wang, X., Tu, Z.,, Hong, Y., Wu, Y., and Shi, G. No-regret online learning over riemannian manifolds. Advances in Neural Information Processing Systems, 34:28323-28335, 2021.
Wang, X., Tu, Z., Hong, Y., Wu, Y., and Shi. G. Online optimization over riemannian manifolds. Journal of Machine Learning Research, 24(84):1-67, 2023.
Weber, M. and Sra, Projection-free nonconvex stochastic optimization on riemannian manifolds. IMA Journal of Numerical Analysis, 42(4):324133271, 2022a.
Weber, M. and Sra, S. Riemannian optimization via frank-wolfe methods. Mathematical Program- ming, pp. 1-32, 2022b.
Zhang, H. and Sra, S. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pp. 1617-1638. PMLR, 2016.
13

---

A Omitted Proofs in Section
A.1 Proof of Lemmal
Proof. Fix t, since Ye+1 is an infeasible projection of y++1 onto K, and yi+1 = Expy. (-77 Ve), (e),by by
Lemma 29
we have for any x E K,
d(yc-1.x)= < d(y(+1,x) S (d(yc+1..0) + d(vr, 2 Cespy.yytt... 2 (ExPy, ve+1. Expy. x
(4)
<CnilVe + d(y,, x)2 + 2m (v, Expy.'x x
To verify that < represents the correct geometric distortion, we need to show d(ýr, x) S 2R holds for any yz E (R( and x E K. Since K S K S (p(R), we can demonstrate this by the triangle inequality:
d(yr, x) & d(yr, p) + d(p, 2R.
Rearranging Equation 4 we have
V Expy. y. z x)2
d(
Smell
+
(5)
2n
21/
2
Fix S ssees T and sum over [s, c). we have
V Expy, x)
x)²
1
d(vi,x)2
+
Vell
21/
217e
21/-1
2
t=8-1
tms
Using gse-convexity of fe(-) and set 1/: = 17, we have
Σ - f((x) -
x(}
176
!==s
|ell
21
2
In case all losses are a-strongly gsc-convex, using fely) - fx(x) (V)( -Exp x) ad(x.)) and set (,, (I, we have
2
T
T
ne 1.
T
Σ -(()))
d(y x)
c
d(yr, x)?
2
2m
2
21)t
21
Setting
1 we get the guarantee for the strongly gsc-convex case.
A.2 Proof of Lemma 2
Proof. By Lemma 29
d( 5) (Expy "ý, Expy z) C2 + d(y, - (-7g, Exp, 12)
C2 + d(y,z)² 22Q
=d(y Q²
CC2'
where the first inequality relies on Lemma 29 and d(y,2) 2) < 2R, the third inequality holds because -(Exp, 2,
12.0,12,811 g) 2 Q. and for the last line, we plug in 7 2-2
Q
14

---

B Omitted Proofs in Section 5
The technical difficulty lies in constructing an infeasible projection oracle using separation oracle. The following lemma is instrumental to the later results.
B.1
Proof of Lemma 3
Proof. Let x = Expy (OTTE) TBll + Expy 2 if we can show x E IC, then by the definition of the separation oracle, we have
(-Exp, x, =-rllggl1 (Expy 2.8) 0,
which in turn implies ( -Eppy" 2, g) 8f |g|| Note that when -2 0)K C K.
thus there exists positive such that K. for any (1 8)K. Let sinbly- v-r(R++)
T. By Lemma 19 we have (ōF) C K. Thus we only need to ensure d(x, I 87 because this implies
x B2 (or) K. We define an admissible family of curves:
r: 00 1] 0, 1] M
(1, + Expy (1(py 2z sōrv))
where v=
g lisll
Then [(1, 0) z and r(1, = x. Let (t( = ar(t.s) which is variation field 8e
of the variation r, and thus a Jacobi field. We can compute Jz(
ar(ss) 0 and by Lemma de
14
D=J+())l==== = brv.
To apply Lemma we need reparametrize to make it unit speed. Let [(t, = R(s))
where
s)) |xpx sōrv| |Expy 2 of 2 or & 2R Then we have Jz(t)= = (R((s) and (t),(t) R(s)
R(s)
Now we can apply Lemma 15
sinh (V-K((s)) D.J.(0))
[|,(11) - (R)(
V-K
(6)
sinh (v (VV
sinh (V-RR(s))8F
V-RR(s)
V-RR(s)
We would like to have d(x, 2) S 0r, and it suffices to choose such that
d(x,2) 2) < /' [Ja(())ldds sinh(V~#(2R + r)) 87 s 87.
V-R +))
We then find a valid F is
- r) 7= (= sinh(v~ + sinh(V-* + r)) (R+
B.2 Proof of Lemma
Proof. We use k to denote the number of iterations in Algorithm 2 then for any < k. we have
y: & K. By Lemma we have (-Exp, -1 1z, g:) 2 8f for any (1 8)A. We then invoke
Lemma 2 with C' lggll.. I..QQ 87 get
82F2 d(y 2)² < 22
Ç
holds for any (1 - 8). To ensure the geometric distortion Ç is valid here, we need to prove d(y,, z) < 2R holds for any i and (1 8)K, which can be guaranteed by induction. The case of i = is straightforward. As E Bp( (1 - 5)K C (R). we have
d(v1,z) 2) < d(yi. p) + d(z, p) 2R.
15

---

Now assume d(y., z) I 2R holds for some i 2 1 and any z E (1 - 6)K, then by Lemma 29 and
Lemma 2
d(y++1,2) z)² SC(K, d(y,, z)) d(y++1. d(y, 2)² - 2 EExpy y Expy. 2) (Expy: yi+1, Expy, / 2)
SC(K,2R) y:) + d(y;,
y.) + d(y 2)² 2 Exxy. y Expy. 2) 82/²
sd(y;, Ç S (2R)²
Thus, we know d(y;, z) 5 2R holds for any 2 and z E (1-
By Equation 7 d(y. 2)² < d(y1, 2)² for all z E (1 - 8)C. Since y1 is the projection of yo onto
Bp (R), we have y 2)² < d(yu. z)2 holds for z (R( Thus, we indeed have d(y. z)² Σ
d(yo, 2)2 for any z E (1 5)K.
remains to bound the number of iterations in Algorithm 2 We must be careful because, on manifolds,
(1 - 5)K is not guaranteed to be gsc-convex (Theorem 60. Note that argmin (((--)) 6)C d(y,, x)² is
consistently non-empty because (1 - 8)K is closed set. Letx; argminxe 8yx d(y,, x)2 and invoke Equation
7 we have
d(yc+1, (1 -))K) d(ys+1, xi+1)²
82
6²
<d(y)+1,x;)) S d(yi, x;)² Ç
d(y (1- (1-
5
The first inequality is due to the definition of x1+1 and the second one follows from Equation
7
We
also need show d(y1, (1 5)K) S d(yo: (1 K)) to finish the proof. We have
d(yr,xi) < x,) S ((yo.x)).
(8)
where the first inequality is again due the definition of x7, while the second comes from Y1 the metric projection of yo onto Bp (R) and xō E (1 8) S (R). Reminding = Yv and unrolling the recurrence, we have
d(y, (1 (1- 8)/0) - d(yo, (1 (1- 01-8)K3² (k - 1)822
Thus, in the worst case, need
k S (d(yo. (1 (1-8))122 d(y, (1 (1-6))333)
82p2
iterations stop.
B.3 Proof of Theorem 1
Proof.
Combining Algorithm with Lemma 4 we know ÿ, E thus Algorithm plays a feasible
point at each round. For a fixed interval 1 [s,e] C [T], let x, = argmin 2t=o fc(x) and
x Expp ((1 0 Exp "xr)) Then
d(x),x)) d(Exp, ((1 E)pxp xx),, d(Expx, (dExpx) p). x1) dd( p. x1) S 8R.
By Lemma
4 y: E IC is infeasible projection of y (1 5)K. Then by Lemma 1
Σ (f(())) - f((x)) S d(),,x1)² T DE | (2:))1))1
2R
nCCT
+
2n
2
17
2
On the other hand, by the gradient-Lipschitness. we have
f(()) f((x)) S G (.d(,,,)))) S GôR.
Combining the above two equations, we have
GR8 + P&p
2R
Σ (f(())) - f((x)))
2 T
16

---

Setting
28 GVCT
and =
1 2/T
< 1. then we have
-((()))) - & GRV
where we use 2 1. It remains to bound the number of calls to the separation oracle. Denote x argmmnnx(1-0ox d(x, 8r). Due to Y141 Expy. (en))(()))))
d(y,+1, (1 5)K) - v++1) v d(x;, Vt) + d(y,, Yo+1) S (1 8)K3 +
where the first inequality is because x E (1 (1- - 8)K, the second is due to the triangle inequality, while the third one follows from the definition of x and yr+1 Expy. (+.)))( Squaring both sides,
we have
d(y++1 (1- S d(yr, 8)13) 2d. (1 8)KCGG + G22
(9)
S dyy (1 8)13)² 25 + G²
where the second inequality is because
v.)) = d( Expy. (oExpy, p)) = ōd(ÿ p) S RR. d(Er, (1-8)() - d(yr, Expp ((1 - s))))
Combining Equation
( with Lemma 4
we can bound the number of separation oracle calls as:
d(yr+1, (1 8)/C)² d( (1-5)K) +1)
Nealls
82,2
d(Sr. (1 (1- -))1)3 + 2R0nG + G2 d(fe+1, -8)/)² +1)
82F2
(10)
2RGNT
GTITT)
<<
+T
728
7282
BRVV
16R
+
+1
T.
72
72
where use 81 = K)K and thus d(A1, -)K.) 0 to derive the third inequality. L
B.4 Proof of Theorem 2
We first prove Lemma 7 which characterizes the relation between 8' and т.
Lemma 7. For gsc-convex subset IC C M where M is Hadamard, any point y E K. and
(r) C KC (R),,, we have
V=
By sinh (V-R(R+ri) c(1+T)k
Proof. The proof of this proposition takes inspiration from Lemma 19 Wang et al., 2023). but with several significant adjustments. Notably, Lemma 19 hinges on the gsc-convexity of K. to bound the radius of the geodesic ball IBy (f), where E (I - r),,, which resides within A.. However, the gsc-convexity of (1 7) is unknown (iaxnoowrTheerffrre Therefore, we must explore alternative strategies that leverage the gsc-convexity of K. meet objectives.
Let v E Ty.M be a unit vector such that ||v|| 1 and z = Expy((1rgg The goal is to find (Exp 'y and z' 1+7
the maximum 0 which ensures (1 T)K for any Let y' Expp
Exp & 147 (
immediate to see z' E iff E (1 T)C. We denote (s) as the geodesic satisfying (0) = y' and (+(1)= z'.
Expp
'ee conjecture that Hadamard manifolds, (1 T)K gse-convex for any
17

---

We define an admissible family of curves:
1 r :: 0,
7 [0.1] +
(t, + Expy (t(Expy' E (s))).
We can verify that r(O, 1) y, ((, I'
Exp, ( Expy'y
P. and
[(1, 1) = z'. We also denote w - 1). The idea of the proof is to show d(p. w) S by Lemma 15| which implies w E since Bp(r) S K. Combining with the fact that y E K. and x'
on the geodesic connecting y and w, we have z' E K. Thus 2 E (1 +
We notice that s) ar(.t) is Jacobi field since it is variation field of (t(t) Exp, (dExpy' ( Let R(s) d(I s), r)). To apply Lemma 15 we need to normal-
ize the geodesic (t)))= = Yos ((+))
Since M is Hadamard, by Lemma 15
||v(L, s)ll 2 R[s)]VV;, 4, s0)
(11)
Remind that [I](1, = [x+(s) de
= (s)] = d(y',z) z²). Now we use Lemma 20 to bound
d(y',z') We construct A (p. z) Euclidean space, a comparison triangle A (p. y. 2) with
comparison points y' E [ and x'
[p. 2]. We restrict y'p. = dz(p, y') and d x')
dE(p, z'), then by Lemma 20 we have
d(y': x') S dz(F',z (z')
(12)
On the other hand, is immediate verify
A (p. 7) is similar (p, y', by considering
d= z')
d(p.z')
d(p.y') dg(p) yp'
(p'''zz') d(p,z)
1 T
d(p.y) dg (p'
Thus we have
OTr d(y, 1+7'
de(y' 24 1+ dz dy
(13)
1+7
where the first equation is due to the property of similar triangles, the second one follows from the definition of the comparison triangle, and the last one is due to the definition of z.
Combining Equations
and (3). we have
[|0(1,
OTr
V e00 s)1l S
S
(14)
R(s)
(1 ((s)
We also need apply Lemma 15 & 1tr Since the sectional curvature of M is lower bounded by K. we have
sinh (V-RI(()
(+-))
1
||V v(0, s)
(15)
T
Putting Equations
14
and
[5
together, we have
+ T
sinh (V-xR(s) 1+r
1 1
lrr
1
8
-RR((s) H+
R(s)
7
R(+))
(16)
sinh (V-R((s) (L+))
Dr.
V-) 1+1
Now we can bound 0. Note that
R(s) d(T s). [(1, =
<dly, d(y' x²) <
T
R +
0Tr
< 7
(R (R+
1
1+ 1
By Lemma 21 have
sinh (v Rks)s
1+r
sinh (v - (
(s)sss) (L+z)
V ( r)
18

---

Thus we can take
0 -
sinh (v (V +r)
to ensure ||0 (++, [)] S The length of the curve (++, .)
can be bounded by
(
ds S..
This implies d(p, w) S r and thus w E K. Then we know z' E K. because z' lies on the geodesic
connecting and y, with both endpoints in K. This finally leads to the fact that (1 + T)K. 0
Now we give the proof of Theorem
Proof of Theorem Algorithm
4 always plays feasible points because by
V-x(Rt+) +)
8' sinh (- Tr
and Lemma we have 2, E (1 r)C and 2e E K.
By the first item Lemma 23
E
[( BL. Expy. x) EE
[ [
yel Expy. x)]
V8 So
E (xp()
(17)
where f((x) is smoothed version of f((x). More specifically, / f((u)
f((x) = Vs Bx
where w is the volume form.
Applying Lemma to Algorithm we know ÿc is an infeasible projection of yv over (1 - 8)C,
which means
d(v+1, x)² S (()++1,x)² < d(y,, x)2 Cr 1g: 2n/ (B1. - x
(18)
holds for any x E (1 - 8)A, where the second inequality is due to Lemma 29
Equation (8 is equivalent to
d(vr, ( d(vr+1,,,' n + l|::12
B Expy Xx
(19)
2n
2
By the third item of Lemma 23 we have
f(3.)- - f(x) <
v fyy.), -Expy x) + PG
S8
(Bc. -Expy. xxxpyx) + 2.'pPG
Vi
E
(20)
Sz d(ýr,x)
c((x+1,x)) x)2
S8
[|s
+ 28' pG.
Vj
2n
2
V
where p is a constant solely depends on K.
Combining Equations
19 and (0). we have
E
(M())) fi(x))
2R S
S
Σ E [lgg:1 + 28 pGT
(21)
V5
2V.-
t=
holds for any x (1 8)K, where the fact that d(ý., x) S 2R. We also need to bound
E f(())) (3) and E (xr) f((x1)] For the former term,
E [(())) - f(()))) =E [fo - + - f((x)) +E ((())) f(0)
(22)
<G d(zr, zz) + G8' + G8' < GTR+2GGG
19

---

where we use Lemma 22 and the gradient Lipschitzness. Similarly, for the latter term,
(x.) - s((x1)
=E ((x) - f(())) + BB [f(()) ft(x))]
(23)
<G8' +G x() S G8' G&R.
By the second term of Lemma 23
we have
Sg gr 2
8' + nlwl) 2 M²2
(24)
Combining Equations
21
22
23
and
24 summing from = s to e, we get
E
(f((z)) - f((xi))
(1((.)) -((5))
I2 (((()))) -((xi))
Σ (f(x))) - -(0x))
c
=F
+
2R
So
ncM²
So
SGTR + IG
+
T 2p8
GO
(G8' + G
Vgy
1212
nsM2
SGTTR+ 2G8) T+
+ nlkk)
+ m//l) 208 (G8' + G
2
8'
(25)
After plugging in 17 = T = T
T
: and 8'
v=((Btr) T we see sinh (V-x(B+r))
8' < T y and
sinh (V-x(R+ +r) T
8
V-R(R(r)
Then
(Jr(2)) - s((xi)) =0 =0
E
as claimed.
Denote X E xrg 8)K d(x, St). We bound the number of calls the separation oracle.
Due to Y141 Expy, (-7g;)
d(y(+1, (1 8)K) s d(x) yt-1) E d(x;, + s(5r, 8)AC + nllg/ll
Squaring both sides, we have
d(yr+1, - 8) < d(y,, (1 8)K))² + 2d(;. (1 8)K) + m
(26)
s d (1 8)K))² + 25 + M?²
where the second inequality is because d(vr, (1 8) x d(y,, Exp, Expp ())) y.)) =(ye, Expy, (dExpy. p)) 8d(ýi, p) - 8R
and lgg: || (z,)) < M. Combining Equation (26) with Lemma we can bound the number of
separation oracle calls as:
d(y++1, (1 (1-8)K)2 -))))=d((p)) d(f (1- 8)AC}2
8)1C2
+1)
Nealls
82F2
d(yr, (1 (1- -0/))² 2R88M m22 d(F (1- +1)
82,2
[=1
2RMC1T
M +T
(27)
728
8282
2RMCT
"
M²(T 1?
+T
72
8
72
-T 2RMS
M
T +
T
72
where the last inequality follows from ý p (1 8)A and thus d(51, (1 8)KC 0.
20

---

B.5 Proof of Theorem 3
Proof. We maintain the loop invariant X2 E BK. So by Lemma 19 B Xg. 8') KC, which means z,
and z are feasible points.
For the two-point feedback setting, by Lemma 23
fx(x)) fi(x)= < ff - Expx, x) + 2G
S8 E [B Exppx xx)px>>>] + 28' PG
(28)
V/
Ss E [Bi, -xy: x) 1, x- Expx,' x)] 28' pG.
Vi
By Lemma 17 of Wang al. (203))
Ss E
S nG(( + 1n:88).
V88
Thus,
So E (Bt, rx: Ex:y,, x Expx,')) S Sa E [||g:l|] <d(xx.
Vi
Vi.
SnG(1 + 1K/0'2) 5(1 -3)d(y,, p) S nGRC(1 - 3)(1 + |m|
(29)
=nGR sinh(V ( 8'
(1 ||<|0²2 = O(8),
V-x(Rtr)
where we use the (-smoothness of jd((x y) and the definition of 8'.
Since Y++1 is an infeasible projection of y'+1 onto (1 - 8)K.
d(ye-1,)) d d(y'+1, x)2 < d(y,, x) )² Cd(ye. - (Expy) Veu Expy! : x)
=dly,,)² + (7> 2| - 2 (-7l Expy. x) x) + <1 |g. 2|2 2n (g.. Exp,," _
holds for any x E Kc, which means
gg: - y: Expy, x) d(yr, x)2 d(y+t1,x))
+
(30)
2n
2
Taking expectation and using
Sw Vir
n n/rsl. have
Sa.
So
+ TTSS8
E [BB. Exp,
x - Vn (d)y,,x)² d(y++1,x)) x)²)
V/
2Vs.
(31)
1 n 8
n/k]|
< + nlxl) (d(yt, d(y x) +
28' +
11C 6²2
2n
2
Combining Equations
28
29
30
and 31 and summing from to e, we have
(x(xx)) f((x)) -0(1)- 8'T + n
(11)))
E
holds for any x E 8).
Following Equations (22 and 2.3 and taking x = Expp ((1 - -5)Expp'xx we have
[f((z)) - f((xx)) = =(
and
[((x) - (((x)) +8)
21

---

In sum,
E [f((zz) f((x')] - 0 =0
-0
110" + (6 8'YT + n
1=
By choosing = 1,10=11111 = T then 8' = =0 ( and we can get O O(VTT regret.
Denote x xrg d(x. yr) and we again bound the number of calls to the separation oracle.
Due to y'+1 = Expy, (-11
d(y(+1: ())) - y( v44) s d(x d(+1.
<d(Er, (1 (1- 8)K) + n - d(v,, (1 8)K + nō'G
where we use || = - - f((z,) - 8G by Assumption 4 Squaring both sides, we have
< d(y,, 10-1(116))00))) (1-))))))) 2d(y,,, (1 (1-81 8))) G2
(32)
I d(y,,, (1-1000000 (1-))))²² 26 G + 7
where the second inequality is again due to Y: E IC and d(yr, - (1-) & d(yr, Exp, ((1 - 6)Expp'yy y.)) = d(y,, Expy. (6Expy, p)) = öd(y,, p) s S..
Combining Equation (32) with Lemma 1 we can bound the number of separation oracle calls as:
d(y2+1s (1 5)K)² - dly (1-8)K3² +1)
Noalla
8272
d(yr, (1 -)KC) + 2Rrno + - -- +1)
(33)
82
t=1
28'n RR =
G2
TT+T
8F2
82
where the last inequality follows from ý1 = p E (1 - 8) and thus d(f1, (1-8)1 = Since
= 1, 1- B = T and
V- 8' (1 3) sinh (V-x(R+r))
8 V-x(R +
S 8r.
sinh (V-k R R
Plugging these parameters into Equation we have
2r RGT
GTT
Nealls SC.
+ 72
+T=0(T
p2
C Omitted Proofs in Section 6
We have the following convergence guarantee for RFW.
C.1 Proof of Lemma
Proof. Since Algorithm is indeed RFW with line-search (Algorithm 9 when f(x) d(x, 2)2 which is Ç gsc-smooth by Lemma 27 and (x(x) -Exp= y, the upper bound the number of iterations follows from Lemma 26 with = Ç and D 2R. Item follows from the line-search because fxx:) d(x;, y) 2/2 /2 does not increase increases.
For item 2, 1ggortthm@sstop when either d(x y² < 3E or d(x, y)² > 3e and (Exp3" yy
"x, Exp3 'x)= <
6. For the first case, ieem obviously holds. Now we consider the second case. We first show (Expy 1z, x + (Exp² z, Expx yy) 2 y(x follows. By Lemma 30 we have
(Expy 2, Expy xx) 2
2 (d(y, 2)² + d(y. x)2 - -d(xx 2)²)
(Expx" z, Expx (r)) > (d(x,y) + d( z)² d(y, z)²).
22

---

Adding the above two inequalities we have (Expy'z Expy xx) + (Expx z, Expx y) 2 d(x, y) Now item follows from
(Expy" -z. z, Expy x) 2 d(xxy)² (Expx z, Expx y) 3c (Expx v; Expx y) 2c.
For the third item, denote x* argminxex d(x, y)² Suppose d(² d(x", yy² < and d(x,y) y)2 2 > 3c. Denote f(x) = x) and fx(x) = Expxx by. For the last iteration, (Expx ' vi, Expx y)
max vel
(Expx -V)(x)) se.
which implies
d(x,y)² -dly, -2ʃ(x) -()((x) 2/(xx) S 2- x", Vs(())
22 52mxx ( -Expx 'v, v.((x) s 2e.
VER
And thus
y(x,))² S d(y, 3c
as claimed.
C.2 Proof of Lemma
Before proving Lemma 6 need the following lemma.
Lemma 8. Consider Algorithm 7 and fix some such that 0 < 3e d(xo: yo)?. Setring
doxo we have ys) I d(xu. Vo) Vo) for any i.
2e
Proof. For all i > 1, we define the sequence y; by the relation y; = Expx, ((1 (11-7)Ein Expx, E .ys-1),
and y E [0, 1). From this, can deduce the following sequence of inequalities:
d(x;-1,y:) ||Expx ,yll
= (1 - E Vi-
< v(-1)
The inequality follows since
(0, 1).
By the first item Lemma 5 for any i 1, we have y.),, S d(x;-1-y3) yz). Combining this with the previous inequality, we get
d(x;,y.) S ((xx)11yy-11)
d(x1,y1)
d(xu: y1)
d(xo. yo).
where the last inequality follows from the fact that x E K. and yı is the projection of yo onto B (R
while S (R).
Proof of Lemma Given that y is the projection of yo onto (R) and X. S (R),, we have Vz K. :dd(., 2)² < d(yo, 2) The lemma trivially holds when d(xo. yo)² < 3e or d(x), y1)² I 3e.
Without loss of generality, we assume that d(x), y1) > 3e. Let > be the number of iterations in Algorithm 7 This means that y&)² < 3e and d(x;,,,)² > 3e for any < k. According the second item of Lemma we obtain (Expy. 2, Expy, x:) 2 2e for all < k and E K. Lemma
also gives d(x,,y)) d(xo. yo) for all i k.
23

---

Applying Lemma with g -Expy; x, C = d(xo: Vo), and Q = 2e, we deduce that for every 1 Isick k
4Ea
4Ea
I d(z,y++1)2 sd(zyy;)
{d)² S d().
(34)
(d(xo,No)*
Consequently, for any z K. the returned point y satisfies d(y, x)² < d(yy,,2) 2)² S d(yo, 2)).
Because p E K. we have d(y, p) S d(y,. < R, which implies y E (R).. Note that x E K. as it the output of Algorithm Thus, we know Algorithm returns (x. E K Bp(H)).
Now bound the number of iterations in Algorithm i < k. Using Equation (3).
Denote x argmin d(x, y:)² for any
d(y++1, =d =(x V+41) S d(x)
4e²
4Ea
<d)x
yd)) d(y;,
yo)
By applying the inequality d(y,,K)² S d(yo, and subsequently performing telescoping sum, we can demonstrate that
4662
4ic
4ic
d(y:+1,K)² S k(),,K)² (d(xu: yo) S K))
(d(xx, Yo) S d(yo, xo)²
(d(xx, yo)²
After at most k = (Cd(xo. yo) yo)
(d) yo)² /))/4e iterations, we have d(yk, K.)² < c. By the third item of Lemma 5 the next iteration will be the last one, and the returned points x, satisfy d(x,y) < 3c, as claimed.
C.3 Proof of Theorem
We first prove Lemma
9 which bounds the regret of the infeasible projection for gsc-convex losses.
Lemma 9, With some fixed block size B, ni T and & e for any i L..... T Assume all losses are gsc-convex. We use i(t) to denote the block index of round t. Then the regret of playing Vi(e)-1 as defined Algorithm 8 can be bounded by
CnBGT
4R²
sup [[
f1l min
4RKG +
X
2
1
Proof. For convenience, we assume B divides T. Let T. ( 1)B + + 1....,iB) iB} be the set of rounds in the i-th block. By Lemma 6 Yi41 is the infeasible projection of y.B+1 onto K:
d(ý;-1,))² x(yiBt1,x)²
holds for any E K.. By Algorithm
8
have
B
( Σ Vi(bio-1)
YiB+1 Expy
17
V ffo (B-1))
Expy,
IET.
Thus
d(S,-1, < x(y:
<d(5 B²2
21) Σ VV -Epp
LET.
where the last inequality is due to Lemma 29 and | [x)))l < G. This is equivalent to
d(ý d(ýi-1,x) d(}++1,x)
CnBBC2
Σ
v
LExpy_
x)
(35)
2n
2
TE
24

---

For certain interval [s,c] S [T), let ig and &e be the smallest and the largest block indices such that Tr and T are fully contained in e]. Then we have
(G. 1)B
( -100-11)-- -EXP Exp x)
(V(((i,--2)
ExPE xx)
t=
(36)
V1((+-1), -xpp x)
Σ
(..((..)) -
B+1
There are some undesirable terms in blocks i, - and i. + 1, and we can bound them by noticing
(V -Expy y00
x
I V (V:0
||Expy 200 x S G- = 2GR.
(37)
Combining Equations
35
36
and
37 we have
f((x)) -
V -Expy ((
1=
d(v:-1.x)² -d(++11x))
GnBBG2
+ +2RR-22 2B
(38)
27
i=
4R²
SnBGTT
+
+ 4BGR.
2
where the last inequality due to the number of blocks [s, e] is upper bounded by T B"
Now we give the proof of Theorem
Proof of Theorem We still use i(l) to denote the block index of the 1-th round. For an interval do the following decomposition
[s,e] e] S [T],
Σ (1)(x(0)1)-
(f((x(0))1) f2(3 f+(35(0)=))
Σ
(Je(F1())1)= - fx(x))
(39)
1=
V - Expx -100-1)
Σ (1 -xa-)) fx(x))
t=
t=
Algorithm calls Algorithm 7 in each block to compute infeasible projection. By Lemma Vc) E x ppp(P) RR), which satisfies d(x,, Vi), & 3r, = 36. Thus
6 and
Algorithm
Vf((x-)1)) Exxp Exxxx.o. X:t J100-1) I 3z)))) & V3eG.
(40)
Combining Equations
39
40 and Lemma have
4R
BnBGTT
Σ (1((xo)- - f((x)) < 4RGB
GT
2
holds for any x E K.. By plugging in n, and B, we get the claimed regret bound.
We also need to bound the number of calls the linear optimization oracle. Note that d(x,, ý1) due to the initialization, and for any 2 2, we have d(x;, y.)² < 3e due to Lemma 6 By Algorithm
g have
iB
T
Yas+1 Expy...
-17
Σ
V ve((i-1))
Vi 1, 1,...
B
(=(i-))B-1
25

---

Therefore
dint1)) dd(x; ( + 1I S v3e + nBG.
(41)
Squaring both sides, have
d(x I( & (3ee+
nBG)* - 6e G216
(42)
where (a + 6)2 < 2(a² + b²) is used.
By Lemma 6 on the i-th block, Algorithm 7 stops after at most
(d (d(
max
+1,1
4e
iterations. According to Lemma 5 each iteration calls the linear optimization oracle for at most <T 27 -2] 2] times. Thus in the i-th block, the number of calls the linear optimization oracle is bounded by
27ç
Nealls = max
+ 1,1
4e2
T There are B blocks in total, so the total number of calls to the linear optimization oracle is at most
T (((1 15
11BBGGap
B'CCy") 5) 27Ç
Neatts S B (1+2* 2 25
2E
Plugging in the values of B, 7 and find Neatts S T claimed.
C.4 Proof of Theorem 5
Proof. Based on similar argument as in Equation 35 we have
TE
x aB
V -Expy__ x)
d(y d(ý)-1,x)²
MET:
(43)
d()r-1,))² x(F
G3B
aB
dly dlý,-1,
2m
2
CBG²
ai
where we apply the strong gsc-convexity on the i-th block under the help of Lemma 28 the last inequality follows from the definition of 77.. we consider the sum of regret over each block in Equation (3)
T Σ - {BG²
(44)
On the other hand, since fe(-) is G-Lipschitz, by Lemma 6
(45)
V - V3BG
4-1
i=1 TET.
26

---

where we use the fact that for the first block, i(t) 1 and thus Xi(1)-1 = -i(1)-1-
Now as we
combine Equations (44 and (45)
have
#
3 SBG²
( S V3BG
Von +
a
By plugging in (<)) we get the stated regret guarantee.
Now it remains to bound the number of calls the linear optimization oracle. Note that for each by Lemma 6 d(x;,; Vz)² 2 < 3eg. In view of Algorithm we also have
block i E B
[T]
(++1)8
((+1)K+1 = EXPy, -
Σ
VI((i))
1=$+11
By the triangle inequality,
d(x;-1, V:B+1) & d(x; 1(B--1,, S Squaring both sides and making use of (a + 6)2 < 2(a² + b²). we have
BG
(46)
d(B+-1. ) < 66,- 2B2 G² n/.
(47)
By Lemma 6. the number of iterations in Algorithm| 7 for the + 1-th block is at most
(BBx (d((x V-B+1 ) ei+1) + 1,
max
de
30e + 22 1h
+ 4B
max
+1,1
4e
(48)
61e? + BBBGAn
< maax
+ +1,1
4e
16e;-1 +
CB
S max
S 1+1,1
e41
441
Thus, the number of calls to the linear optimization oracle is bounded by
16
GB*
27R² Ei
Neolls
+
+51)
4+1
6+
2
16(1 + 3)
2 + 3)
+ 2)
Ra
(i+3)%
(49)
(i + 1)1
4002 (i 1)
20G
im2
Ro
<0.32
(i+ (1+3)
where the last line follows from ( 1, 1-3
and
< ++
holds for any i 2 2. On the other hand,
we have
f
(1 +
3) <
Σ
2
< Σ
2
(50)
3
B
2
1=5
5=5
Combining Equations ÇT.
50 and plugging in B =
(
T2//, we get the claimed Noatis S
D Some Basic Facts about Convex Sets on Hadamard Manifolds
In this section, we highlight two significant characteristics convex sets Euclidean space which do not apply to Hadamard manifolds, emphasizing the fundamental differences between these two spaces. Our counterexamples are constructed within the Poincaré half-plane, HH? Therefore, understanding some basic properties of this unique manifold will prove beneficial.
27

---

Lemma 10. (Udriste 2013 be described by
Wang et al.
2016 Kristály et al. 2016) The Poincaré half plane H² can
M [(t1,t2)
R 122 0}
with metric
dij
ghs (u,
i= 1,2.
We have the following conclusions about geodesics and the distance on the Poincaré half-plane.
1) For the geodesic connecting = (t1, 12) and y = ($1, 82), let
5 + 2² - f2 t
V(s bzn)) 12 + $2
Day
Tay
2(81 - 11)
then the geodesic "ay = (Nay: r'ey) connecting x and y is,
Toy(s) {
t1
ift1 $1
Day Tzy tanh ((1 (1- artanh bay -h Pxy
+ s. artanh
buy-61) Twy
i + $1
(51)
(20( = (2l-s)lnlatt-ll)
if = 81
if # 81.
(52)
cosh (11 (1- s)aaranh 1ay
1 aatannh
"1
Indeed, we have (N (s) bay)² (s))² = r for any E [0, 1] when tı + 81.
2) The distance between two points (wi, v1) and (u2, v2) can be calculated by
da((us v1), U2), = arcosh (1- (u2 )2 + (u2 - Un )2
2u1
D.1 Shrinking Gsc-convex Sets on Hadamard Manifolds Does Not Preserve Convexity
In the context of projection-free online learning on manifolds, the set eCC Exp, (cExp, x) x E IC takes pivotal role, particularly when < 1. Consider a convex set K. in Euclidean space, then the convexity of cK guaranteed for any positive c. Nonetheless, this property does not necessarily hold Hadamard manifolds. We can construct counterexample within the Poincaré half-plane Hi? To achieve this, we rely on the following lemma.
Lemma 11. On the Poincaré half- half-plane HP, the mid-point of the geodesic Yay which connects x (- xx,,1) and y = (2, p) is (0, XX2 + x22).
Proof. By symmetry we know (2) O. To compute 22 (2), note that bay 0 and Txy
2 + n then by Lemma 10
Yag (2)
X2 + nr2
X2 + 112
cosh arctanh Vx+ arctanh
A
A
V
where we use the fact that arctanh(.) is an odd function and cosh(0) 1.
Now we prove the following theorem.
Theorem 6. There exists counter-example on the Poincaré half plane H such that the radially contracted set (1 11-a a)K where (0,1) non-convex.
Proof. Let = (0.1), - (-1, vー (1. w = (0. 33. Observe that Yuo is an are satisfying {(A, + 1===
=3]] 3) and, by Lemma 11 w is its midpoint. Following this, we calculate Tpu, Ypu. and Tppo and shrink these three geodesics by factor of (1 a). Let's denote the resulting geodesics as Tpp's Tmo,, and Tpor. Ultimately, we demonstrate that for some a, w' positioned beneath Yutor, implying that the radial contraction of K. does not encompass geodesic, hence proving
28

---

its non-convexity. We first compute Ypu and Ypo to facilitate this. Note that Dyu -1 and Ppu 22 by Lemma I0] we can write down
Ppa (8) = -1 V2tann, (1- 8) arctanh
V2
and
V2
m (s)
cosh (1 - 8) arctanh
V2
By symmetry, we have
Io0 (8) = 1 v2 tanh (1- s) arctanh
V2
and
V2
cosh (1 s) arctanh
v2
We can also compute Ypnr (8) = (0,, v3
Now we have
v 7mu x)) -1 v2 tanh a arctanh
(-x2)):
2
cosh
arctanh
v/ = 7ppp - -a) =
v2 tanh arctanh
V2
v2
coshi
arctann
and w/ (0, (1,e(1-a) v3)
We just need to demonstrate that for some E (0, 1), w/ is positioned
below Yu'r' (2), where
00,
3 + 2 tanh a arctanh (-12)
2
by Lemma 11 Specifically, we need to show 3x E (0, 1).
(- 1 V2
3 2V2 tanh arctann (l-a))ln <
We set .1, then
3 2v2 tanh
arctanh
ell (1-a) v3 0.036
2
Therefore, the set (1 aC fails to contain the geodesic Yore (8) and is thus non-convex.
D.2 Non-convexity of the Minkowski Functional on Hadamard Manifolds this part, we show the Minkowski functional (Gauge function), which defined as
Expp z
The (x) inf > 0: Expp
E E
(53)
be non-convex Hadamard manifolds, where K. is gsc-convex set of Hadamard manifold M and p is an interior point K.
Theorem 7. The Minkowski functional defined in Equation can be non-convex on Hadamard manifolds.
29

---

Proof. We again construct a counterexample on the Poincaré plane H
M (21,12) R 12 0).
To verify the geodesic convexity,
verify equivalent statement: function fs gsc-convex iff f is convex when restricted to any geodesic. That f()(t) S (1 (1- (-)((((())) + (f(r(1)) holds for any geodesic y(t): [0, 1] M. The counterexample is as follows.
Assume K' is the gse-convex set consists of all points (u,, u2) such that u² + u S and U2 > I 13). = 2) and p = (0, 1). We show that (c) is non-convex on the geodesic "oy-
We first compute buy -2 and Tzy 2. By Lemma 10 we have
(-2) cosh ((1 (s) arctanh (-2))
Yay(s) (s) = -2 tanh (1 (1-3) 3) arctanh
(54)
= cos ((s) s), sin (s)):
where let ((s) tanh ((1 8) arctanh (-2)) to the elaboration. We denote
Tay (8) (-2 cos (s)), 2si (s)). Then we compute the geodesic 7pz connecting and
p = (0, 1). and we have
(2 +2+ cos (s)) (2 (2
(2snn 0(s))²
-1
7 8 cos 0(s)
(s)
2 cos (s))
4(1 + cos 0()))
and (s) (s)² Now can compute the intersection of (sp with X. the solution (91,92) of the following system of equations
(q) -
-p= (s)) + vB = (s) +1
ni
3
The intersection point is 1
/3 bp:(
For each E [0, 1]. we can evaluate the Minkowski
(x) functional at (8) w.r.t. K. as
(())())
h(s) = da((-2
0(s)), (0, 1))/dz
(0,
(x)
where dg is the hyperbolic distance defined in the second item of Lemma 10 If the Minkowski functional is gsc-convex, then we should have h(s) I (1 s)h(0) + s h(I) for any s E [0, 1]. However, by numerical computation, find
1 h()))
1 h11 0.0057
h(1/2)
2 2
which refutes the assumption that h(s) is convex. Thus our conclusion is established.
E Technical Lemmas
E.1
Background on the Jacobi Field
The role of the Jacobi field as an essential tool for understanding the impact of curvature on the behavior of neighboring geodesics cannot be overstated. To make discussion comprehensive and self-containee we will introduce related definitions and properties sourced from Lee (2006) and Lee (2018).
We define an admissible curve as a continuous map. >(t) b] + M, representing a piecewise regular eurve segment. An admissible family of curves, the other hand, is continuous map st. Ja, b) (-c,c) > M which is smooth on each rectangle [a;-1, ag] x (-c.c) c) for a finite ax b. Here, I, [t) T[t, s) is recognized
admissible curve for each s E (-e,e). t). When 7()) is admissible and [tt, 0) 7(), we refer to I' as a variation of (().
subdivision ag
Upon an admissible curve r, we can delineate two sets of curves: the principal curves (a((), which hold constant, and the transverse curves (t) (s) l'(t, s), which consider t as constant. We
30

---

consider I as a variation through geodesics if each principal curve (t) = r(t, s) is geodesic segment. For an admissible family of curves we define a vector field along as map V (a, bj x (-c,6) + TM such that (t,,s) E Tr(cs) and for each V(s, 1) is piecewise smooth. The Jacobi field is a vector field along a variation through geodesics and formally defined as follows.
Lemma 12. Lee 2018 Theorem 10.1, The Jacobi Equation) Let (M,g) be a Riemannian manifold, be geodesic in M, and J be vector field along 7, If J is the variation field of variation through geodesics, then J needs to satisfy the following Jacobi Equation:
D.J + R(J, 9) 0,
where R is the Riemann curvature endomorphism. A smooth vector field J satisfying the Jacobi Equation is called Jacobi field.
Given initial values of J and D at one point, the Jacobi Equation can be uniquely determined by the following proposition.
Lemma 13. (Lee 2018 Prop. 10.2, Existence and Uniqueness of Jucobi Fields) Let (M,g) g) be Riemannian manifold a I M is geodesic where I is an interval. Fix a E I, let p = 7(a), u, M, there a unique Jacobi field J along Y which satisfies
-
{aa)= = u,
D.J(a)= =
The Jacobi field seems to be complicated object to study, but the following lemma shows we can write down the initial conditions of the Jacobi field for certain variations through geodesics.
Lemma 14. Lee 2018 Lemmna 10.9) Let (M.g) be a Riemannian manifold, be an interval containing O, and I - M be geodesic. Suppose J : - M be a Jacobi field with J(0) O. M is geodesically complete or 1 compact, then J is the variation field of the following variation of
s(t,s) = Exp, (t(u++ (t(u+
where p (0), 7(0), and == D,
The advantage of introducing the Jacobi field is the norm of (t) can be bounded by the initial value (O)]] shown in the following Lemma 15
Definition 4. We define
if K = 0
(kk, t)
{ sin(Vit), VK
if K > 0
ik <.
V=R
Lemma 15. Lee 2018 Theorem. 11.9) Suppose (M,g) is Riemannian manifold, 7 [0, + M
unit-speed geodesic segment, and J is any Jacobi field along y such that (0) 0. For each
c E I. let -(- be the function defined by Definition
1) afll sectional curvatures of M are bounded above by a constant R2, then
[|](t)] 2 s(max{(0 (i,max(0,n2),110 [()()))
for all t. E bi), where by = if K2 & 0, and bj = min (b. TTa)) Kf2 > O.
2) If all sectional curvatures of M are bounded below by a constant K1, then [J(t)] S s0min(0, k1), [D)(()))
for all t E [0, b2), where by is chosen so that ry (b2) is the first conjugate point to 7(0) along y if there is one, and otherwise b.
E.2 Miscellaneous Technical Lemmas
Lemma 16.
(Bacák 2014 Section 2.1) Let M be Hadamard manifold, f M - (-oc, oo) be gsc-convex lower semicontinuous function. Then any B-sublevel set of f:
{x E M: fxx) 33
is closed gsc-convex set.
31

---

Lemma 17. (Bacák 2014 Section 2.2) Let M be Hadamard manifold. fo M - (-00, o0) for I.... m series of gsc-convex lower semicontinuous functions. Then supre(m] fi) gsc-convex.
Lemma 18. For a K = mx|maxisism hx(x) I 03 S M where each hz(x) is gsc-convex, M is Hadamard and any y & K, there exists g E MyM such that
(-Expy xg,7'xxg)... O, E
Proof. By Lemma 17 maxicism (x) is gsc-convex. Further, by Lemma 16 K. is a gsc-convex subset of M. For some y & K, there exists j E [m]] such that (y) 0. If not, we have hy( S holds for any i 1, ..... m., which implies y K. and leads to a contradictory. Applying the gsc-convexity for any x E K., we have
(Exp, x, Vhz(y)) 2 hy(y) hx)x))
where the second inequality is because hy and (x) O. This is valid separation oracle between y and K.
Remark 4. Given k= (x|mmxisssm (x) S 0} where each (x(x) is gsc-convex and y & K. we can check the sign of hy for fori=1..... until we find 1 such that h (y) > 0, then using the proof of Lemma 18 we obtain
(Expy'x, x, (h--(y)
for every E K. This gives us separation oracle between y and K. The computation of this separation oracle requires no more than m rufuuction value evaluations and a single gradient evaluation. This is efficiently implementable when is of moderate size.
Remark 5. Using Gauss's Lemma (Lee) 2006 Theorem 6.8), we can efficiently compute the projection onto a geodesic ball. Consider x & Bp(r) ( for which aim to compute its projection onto Br(r). First, we determine the geodesic segment, denoted as 7()). connecting x and p. This segment intersects the geodesic ball at point Gauss's 's Lemma then tells that the tangent vector of (t) at z is orthogonal to the geodesic sphere (T). This indicates that z is the projection of x onto (r()). By performing (log (?)) rounds of binary search on 7()), we can approximate z to within an c precision. each round, suffices to verify if the condition d(xx, p) 2 r met.
Lemma 19. (Wang et al. 2023 Lemma 45) Suppose the sectional curvature of M is in [K1, K2] where N1 & 0 and R2 2 Assume a gsc-convex set K. satisfies Br(r) S. K. S. [P(RR where R S 2
when R2 > Then for any E (1 T)K, the geodesic ball By ((k2.R+r)-rr' s(NI,R+T)
E K. where s(,;)) is
defined in Definition 4
Lemma 20. (Bridson & Haeffiger 2013 Chapter II.1) Suppose A(p. q.r) is triangle Hadamard manifold M and ((p, q. r is comparison triangle in Euclidean space such correspond- ing side lengths are the same for both triangles. Then for any E (p.q]. y p..)) [p. q). y E [p, f) satisfying d(p,x) = (p, x) and d(p.y) = (p(p. V). we have d(x, y) S dx
Lemma 21. The function sinh increasing for any x E [0, oo].
Proof. We denote g(x) sinh then
g'(x) x cosh x sinh x
x²
It suffices to show h(x) == x cosh x- - sinh x 2 holds for any x E [0, oo). This is obvious because
h())- = and f1(x)) = x sinh x 2 0 for any x E [0, oo). It remains to compute g' g'(0). By LAôpital's rule.
x cosh x sinh
sinnh 0.
g' (0) lim z
lim +0
z²
2x
Lemma 22. Let f M + R be goc-convex and G- G-Lischhitz on a gsc-comvex set K. S M. Then
f(x) = V, Bx(5)
1
{
f(u)w
satisfies
1f(x) f(x)) S G8.
32

---

Proof. We have
If(x) f(x) |Bjv|| (Exp, (ōv) f(x)] [|]]= (Exp, (ōv)) [()]
(55)
E ||v|== [G]|8v||| - G6.
where M. The first inequality is due to Jensen's inequality, and the second one is by the gradient Lipschitzness of f.
Definition Given homogeneous Riemannian manifold M, we use Ss and Vs to denote the surface area and the volume of a geodesic ball with radius 5.
We note that on homogeneous Riemannian manifolds, the volume and the area of geodesic ball only depend its radius (Kowalski & Vanhecke 1982), Ss and Va well-defined.
Remark 6.
Lemma 23. (Wang et al. 2023 Lemmas I and 13) For homogeneous Hadamard manifold (M, g) with sectional curvature lower bounded by K I O, f be a C and gsc-convex function defined on M such that [f] I C for any E M.. We define
1 V/2 { f(u)w
f(x)
Vs Bx(6)
where w is the volume element, and
Expx (u)
g(u) = f(u)
Expx (u)
is corresponding gradient estimator: Then we have
!) S: g() is unbiased estimator of V f(x). More specifically, for any M,
Ss
Eues
g(((() x (x()).
V
2) The expected norm of (g)( can be bounded by
E (
(0)
S8
g(()
x
Sa
n s (" m|k(6)
V/J
V8
3) Suppose K. M is a gsc-convex and fxx)) I G. then ff satisfies
fly) - (100-(vv(6
(xp= (TF))
-2p8G,
where p solely depends on the set K.
Remark 7. From the proof of Lemma 23 we can figure out the formal definition of p is
(VGExpa'
sup x.y
s.1.
x(xx= =.
VG dx.
By Wang et al. (2023). this quantity can be (cD) even on a 2-dimensional Poincaré disk.
Algorithm 9: Riemannian Frank-Wolfe with line-search
Data: feasible gsc-convex set IC, initial point Xg E K. gsc-convex objective f(-). for i O,... do
argmin ( (V (xx)) Exp, x)} σ; argmin e (Expx, (oExp=,) vx)))
X;+1 = Expx, Ex, v;)
end
33

---

Lemma 24. (Weber & Sra 2022b Theorem 1) Suppose the diameter of the gsc-convex set K. S M upper bounded by D and f gsc-convex as well as gsc-smooth on K. With linear optimization oracle in hand, the primal convergence rate of Algorithm Saaahmmmeeee yenn be described by
2LD
[(x+) - f(x") S
k+2
Lemma 25.
(Weber & Sra 2022h Lemma 2) Under the same assumptions as in Lemma 24 for Expx, (n/Exxx v) with E [0,1]
step Xk+1
f(x++1) f(xx) (V Expx, 1 v)
Lemma 26. Under the same assumptions as in Lemma 24 denote
g(x) = max
maxx (-Expx v. vxxx))
vEK
If Algorithm run for K 2 rounds, then there exists k such that 1 S K and
27LD2
g(xx.) S 4(K +
Proof. The proof is adaptation of Jaggi (013 Theorem 2). We first assume the duality gap is
large the last one third of K iterations, then get contradictory to prove conclusion. For simplicity, we define h& = fxx)) - f(x") and 9k (xx)..
To ease the elaboration, we denote C' == 2LD2, a 3. b b and d = K We assume holds for the last one third of the iterations. More specifically,
&C K+2
gk
bC
for k {[ad] 2..... .2....Ky K].
d
By Lemma 25 with 7 = k42
we have
2
2LD
het1 Sha
k k+ gk
(k: + 2)2
(56)
C
-h4 1 lk
(k: + 2)2
Plugging in the assumption that the duality gap is large, we arrive at
2 PC
C
h1+1
h4
+ 2
(k+ + 2)2
2bC
C
< hk
(57)
d²
add
2bC
C/a²
hg
d²
K.,K, for all & = [dd] 2, .., K, when the second inequality follows from [ad] -2 2 k S K implies
ad < k + d.
Denote kmin Tod] and hmin hu then there are K- kiiin +1 K (--((ad) -2) > (1 - add steps in the last one third iterations. Thus summing Equation (57) from k = [ad] 2 to K, have
2bC - C//22
hK+1 < Bmin - (1 ald
d² - (1 odd 2ab - 1/a C
< ad
d ad
(58)
(1 - (1 - a) (2ab - 1/a))
ad
< 0,
34

---

where Amin & C is due to Lemma 24 while for the last step, we plug in the values = and ad b= 27, However, hK+1 < 0 is impossible because hK+1 f(xx+1) f(x*). Thus, there always g.
exists k, in the last one third iterations of K such that
DC
27 2LD
27L.D
g(xx.) 1
8
K
K2
4(K+2)
Lemma 27. (Ahn & Sra 2020 Prop. H.1) Let M be a Riemannian manifold with sectional curvatures
lower bounded by K S O and the distance function d(x) = =d((,, p)² where E M. For D 2 0,
d(-) is Ç gsc-smooth within the domain {u E M. d(u,p) S D) where Ç = V-RD coth(v-ni))
the geometric constant defined in Definition
7
Lemma 28. Suppose fx( is a-strongly gsc-convex for any = I,...,N, N, then E fi(x) is o -tronngyy gsc-convex.
Proof. By the a-strongly gsc-convexity of each fx(x,,
f((y) 2 f((x) + (V (x). Expx (y)) + &
d(xx v)²
Summing from = 1 to N,, we have
N
Σ
M(yy)
f(() [x)(x), yx) +
Σ
a
d
yx,
2
==1
(59)
+ 1 ) y(x,
Σ f(()) + ff((), Exp
This indeed implies Σ fily) is a--strongly gsc-convex.
Lemma 29. (Zhang & Sra 2016 Lemma 5). Let M be Riemannian manifold with sectional
curvature lower bounded by K 0. Consider a geodesic triangle fully lies within M with side lengths a, b, we have
a² 2 c)b? c² -2be
where C(n, c) := coccohh -kcc).
Lemma 30. (Sakai 1996 Prop. 4.5) Let M be Riemannian manifold with sectional curvature
upper bounded by K I O. Consider N, gsc-convex subset of M with diameter D. For geodesic triangle fully lies within N with side lengths a, b, c, have
a² > 12 + -bcc cos A.
E.3 Extension to CAT(K) Spaces
not difficult generalize the result in this work CAT(k) spaces, which are simply connected manifolds with sectional curvature upper bounded by s. To achieve this extension, the following adjustments would be necessary in our manuscript:
We may assume that the sectional curvature lies in the range [K,, K]. In this context, can replace Lemma in our draft with Alimisis et al. (2020) Corollary 2.1). When K 0, we must further assume that the diameter of the decision set is upper-bounded by VK"
The separation theorem, specifically for Hadamard manifolds as outlined Silva Louzeiro et al. (2022), would require generalization to CAT(k) spaces. This change ensures that the separation oracle remains well-defined.
Lemma requiresss modification to accommodate the recomputation of the Jacobi field. considering the manifold's sectional curvature. Lemmas 15 and 19 will be instrumental in achieving this.
35


Reviews:
[{"review_id": "hMSzH7jdjJ", "reviewer": "Reviewer_xiK4", "summary": "The authors propose a generalization for online learning on the Riemannian manifolds via separation and linear optimization oracles. The core idea here is to use the oracles to construct an infeasible projection, which may not be the nearest point in the constrain/decision set $\\mathcal{K}$, but are in $\\mathcal{K}$ and is closer to a shrunk feasible set $(1-\\delta)\\mathcal{K}$ than the original point. The interesting point finding here is that because there is a buffer between $\\mathcal{K}$ and $(1-\\delta)\\mathcal{K}$, we have a constant distance decrease of $O(\\delta^2)$ (Lemma 4 eq (5) in the appendix) w.r.t. by the separating oracle direction to the shrunk set $(1-\\delta)\\mathcal{K}$, and hence the projection to $\\mathcal{K}$ can be done in constant time to $\\delta$. This means we can construct an infeasible/inaccurate projection by the separation oracle in $O(1/\\delta^2)$ time, and the algorithm follows from replacing the projection part with the infeasible projection and bound the errors. The authors also consider the linear optimization oracles, and it's done by constructing the separation oracles using the linear optimization oracles in Frank-Wolfe. Actually, this draft is a combination between Garber & Kretzu (2022) and Wang et al. (2021), where the authors generalize the online learning by SO/LOO framework by Garber & Kretzu (2022) with the tools and assumptions in Wang et al. (2021). ", "questions": "1. L32: Computing the orthogonal projection of \"polytope\" to half-spaces is NP-hard, but point projection is not. So this is unrelated to the draft.\n2. L161: May you explain the existence of g in Lemma 18 implies an efficient implementation?\n3. Assumptions & Lemma 19 requires $R\\leq \\pi/\\sqrt{4\\kappa_2}$, but it's not in the assumptions and coefficients.\n4. Lemma 29 is different from the original paper. Please note that you use the monotonicity of $x coth(x)$ here.\n5. L179: Please cite the projection algorithm in $O(\\log(1/\\epsilon)$\n6. Algorithm 2 takes $\\delta$ as an input but the $\\delta$ doesn't appears in the algorithm. Please at least define $\\gamma$ as a function.\n7. Appendix L430 eq (3): Please annotate that the later line suffices the inequality.\n8. Algorithm 2: It's also using one membership oracle at each step.\n9. Appendix L456: You use the bounded gradient property, not the Lipschitzness of the gradient.\n10. Algorithm 4: This looks pretty much like the R-BAN. Why R-BAN sample from a sphere but the algorithm samples from a ball?", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The idea of constructing an infeasible projection (the solution is feasible to $\\mathcal{K}$) and providing guarantees to a shrunk set $(1-\\delta)\\mathcal{K}$ is very interesting, and it's good to see it works on the Riemannian manifold. The introduction is pretty well-written, and there is no major error in the proof, and generalizing the result from Euclidean space to the Riemannian space may be challenging in some corner cases.", "weaknesses": "The major weakness of the paper is its complexity, the lack of experiments, and the limiting assumptions.\n\nFirst, the proof in the paper is pretty complex and is not self-contained. To verify any proof in the paper, the readers usually need to go to Garber & Kretzu (2022) and Wang et al. (2021), which have another set of symbols and may again point to other papers. And this may lead to confusion for both the authors and the readers. For example, the Lemma 19 in the draft points to Wang et al. 2023 Lemma 45, which requires the curvature to be also upper-bounded, but such assumption and coefficient disappears in the draft. Garber & Kretzu (2022) assume that the feasible set contains the origin. The paper generalized it to arbitrary point $p$, but in that case, the shrinking set $\\mathcal{K}$ should be redefined toward $p$ for $(1-\\delta)\\mathcal{K}\\subset\\mathcal{K}$, but it is also not done. The proof in the paper is mostly correct when self-contained, but it is very time-consuming to verify the mentioned errors from cited lemmas by chasing around the links, so I am not very sure about the correctness of the theoretical paper.\n\nSecond, I am not very sure about the practical aspect of the paper due to its limiting assumptions and lack of experiments. Surely, theoretical papers may not have been experimented with, but the paper is too complex to verify its correctness, so it would be good to show the reader that it works in a sense. I am concerned about the limitation in the assumptions because most of the examples mentioned in the draft's introduction don't fit the assumption, e.g., the spherical constraint in K-means clustering. The manifold must be bounded, containing a non-empty unit ball, and contained within a unit ball of radius $\\leq \\pi/\\sqrt{4\\kappa_2}$ (Lemma 19). And I am unsure when the separation oracle and linear optimization oracle are cheaper than the projection in a practical example. Please give the readers more examples to understand when the setting would be suitable.\n\nFinally, the paper is a direct combination between Garber & Kretzu (2022) and Wang et al. (2021). Most of the work here looks like a Riemannian generalization of Garber & Kretzu's (2022)'s framework with Wang et al. (2021,2023)'s tools, replacing the distance with exponential maps and bound them with Wang et al. (2021,2023)'s inequalities. And there are not many new surprising results, but double the complexity. It is not necessary to be novel to publish, but given that I'm not convinced that the results are totally correct, I would recommend a weak rejection. This draft should be more suited to a journal than a conference.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions. We appreciate the time and effort spent in reviewing our work, and we will revise the draft accordingly. Below, we address your specific questions and concerns:\n\n> For example, the Lemma 19 in the draft points to Wang et al. 2023 Lemma 45, which requires the curvature to be also upper-bounded, but such assumption and coefficient disappears in the draft. Garber & Kretzu (2022) assume that the feasible set contains the origin. The paper generalized it to arbitrary point $p$, but in that case, the shrinking set $\\mathcal{K}$ should be redefined toward $p$ for $(1-\\delta)\\mathcal{K}\\subset \\mathcal{K}$, but it is also not done.\n\nThis might be a misunderstanding. As you pointed out, Lemma 19 requires the sectional curvature to be both lower and upper bounded. We assumed the manifold to be Hadamard and defined the curvature lower bound in Assumption 1, and the sectional curvature of Hadamard manifolds is upper bounded by $0$ (Lines 149-151), so we did not overlook this point. Additionally, we defined the shrinking set  $(1-\\delta)\\mathcal{K}$ for some fixed $p$ in Definition 2.\n\n> The proof of the paper is pretty complex and is not self-contained.\n\nWe acknowledge that our proof is somewhat complex due to the Jacobi field technique. To make the paper more accessible, we have introduced related background in Appendix E.1. We plan to further improve readability in the revised version and welcome any comments or suggestions.\n\n> I am not very sure about the practical aspect of the paper due to its limiting assumptions and lack of experiments. $\\dots$ Please give the readers more examples to understand when the setting would be suitable.\n\nWe mainly consider Hadamard manifolds, a standard assumption (Zhang and Sra, 2016; Wang et al., 2021). While more restrictive than general Riemannian manifolds, practical examples exist, such as the geometric mean and the Bures-Wasserstein barycenter on the manifold of SPD matrices (Line 165). In these two specific examples, Weber & Sra (2022b) demonstrate that, WLOG, the feasible set can be assumed to be $\\mathcal{K}=\\\\{X|L\\preceq X\\preceq U\\\\}$, where $L$ and $U$ are SPD matrices. Weber & Sra (2022b) establish that the linear optimization oracle for $\\mathcal{K}$ admits a closed-form solution. We show a separation oracle for $\\mathcal{K}$ can also be efficiently implemented. Under the affine-linear metric, we have $\\left<A,B\\right>_Y=\\text{tr}(Y^{-1}AY^{-1}B)$ and $\\text{Exp}_Y^{-1}X=Y^{\\frac{1}{2}}\\log(Y^{-\\frac{1}{2}}XY^{-\\frac{1}{2}})Y^{\\frac{1}{2}}$. By some computation, for any $X\\in\\mathcal{K}$, we have:\n$$\\left< -\\text{Exp}_Y^{-1}X,Y \\right>_Y>0\\text{ when }Y\\succ U$$\nand \n$$\\left< -\\text{Exp}_Y^{-1}X,-Y \\right>_Y>0\\text{ when }Y\\prec L$$\nThus both optimization oracles can be efficiently computed. We agree that numerical experiments would enhance our work and will include some experiments on the SPD manifold in the revised version.\n\n> The paper is a direct combination between Garber \\& Kretzu (2022) and Wang et al. (2021).\n\nThank you for your comment. We acknowledge the similarities between our work and the works of Garber & Kretzu (2022) and Wang et al. (2021, 2023), but it also features several significant and novel contributions:\n\n1.  We identify that the shrinking set $(1-\\delta)\\mathcal{K}$ is non-convex and subsequently extend the definition of infeasible projection initially presented by Garber & Kretzu (2022) to accommodate non-convex settings.\n2.  Quantifying the progress made with each call to the separation oracle presents a highly non-trivial challenge. We overcome this in Lemma 3, where we amalgamate Lemma 19 (equivalent to Lemma 45 in Wang et al. (2023)) with meticulous computation involving Jacobi field comparisons.\n3.  Concerning the linear optimization oracle, deriving a separating hyperplane using Riemannian Frank-Wolfe stands as the principal hurdle. We manage to overcome this through an innovative application of Riemannian cosine laws. For further insights, we refer readers to Remark 2 and the proof of Lemma 5 in our manuscript.\n\n> L161: May you explain the existence of g in Lemma 18 implies an efficient implementation?\n\nWe consider a gsc-convex set $\\mathcal{K}=\\\\{x|\\max_{1\\leq i\\leq m}{h_i(x)}\\leq 0\\\\}$ where each $h_i(x)$ is gsc-convex. Given a point $y\\notin\\mathcal{K}$, we can check the sign of $h_i(y)$ for $i=1,\\dots,m$ until we find $i^*$ such that $h_{i^*}(y)>0$, then by Lemma 18, we have\n\n$$\n-\\left<\\operatorname{Exp}_{y}^{-1}x,\\nabla h_{i^*}(y)\\right> >0\n$$\n\nholds for any $x\\in\\mathcal{K}$ and thus we get a separation oracle between $y$ and $\\mathcal{K}$. Computing this separation oracle requires at most $m$ function value evaluations and $1$ gradient evaluation, which can be easily implemented when $m$ is moderate.\n\n> Assumptions \\& Lemma 19 requires $R\\leq \\pi/\\sqrt{4\\kappa_2}$, but it's not in the assumptions and coefficients.\n\nIn Assumption 1, we assumed $\\mathcal{M}$ is Hadamard, so $\\kappa_2=0$. In this case, we do not need to assume the manifold is bounded because for any two different points, there exists a global length-minimizing geodesic connecting them.\n\n> L179: Please cite the projection algorithm in $O(\\log(1/\\epsilon))$.\n\nLet $B_p(r)$ be a geodesic ball with center $p$ and radius $r$ and $x$ be a point outside of $B_p(r)$, and we intend to compute the projection of $x$ onto $B_p(r)$. We first compute the geodesic connecting $x$ and $p$, say, $\\gamma(t)$, which intersects the sphere at $z$. Then by Gauss’s Lemma (Theorem 6.8, Lee 2006), the tangent vector of the geodesic $\\gamma(t)$ at $z$ is perpendicular to the geodesic sphere $S_p(r)$, which means $z$ is the projection of $x$ onto $B_p(r)$. So it suffices to do $O(\\log(1/\\epsilon))$ binary search on the geodesic $\\gamma(t)$ to get an approximation of $z$ up to $\\epsilon$ precision. For the $t$-th binary search, we merely need to verify whether $d(x_t,p)\\geq r$ is true, which is computationally efficient."}, {"review_id": "2C2rmWYVsP", "reviewer": "Reviewer_puFc", "summary": "The authors study online learning on homogeneous Hadamard manifolds with geodesically-convex, Lipschitz losses. They focus on projection-free methods and in particular they develop algorithms that use either a separaton oracle or a linear optimization oracle. They study adaptive regret algorithms for the full information and the bandit feedback settings. \n", "questions": "see above", "limitations": "see above", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Besides from the strengths of having the theoretical results authors have, I want to emphasize the following.\n\nThis work usually states clearly the assumptions that is making, even though this could be improved, as I suggested. It was good to see the authors taking into account the non convexity of (1-\\delta)\\mathcal{K}. Some works ignore this fact, I wonder if they learn about this in the review of a paper. But the authors here are rigorous and work with the possible non-convex set.\n\nThe results with linear minimization oracle look fine to me", "weaknesses": "# Main points of my review\n\nSeveral results in this paper follow closely Garber and Kretzu (2022). This is not a criticism, of course there are several challenges in the Hadamard case that need to be surmounted. \n\nI have several points of criticism though:\n\n+ The paper contains some mistakes, and I am not sure if one could fix at least one of them while keeping the stated results (see below). \n+ Moreover algorithm 4 has a regret guarantee in Theorem 2 which is non standard (algorithm plays a point and feedback is given for another point but the regret is still measured with respect to the played point). This seems an artifact of the proof, as in it was the notion that made the proof work, but without any other justification for this made-up definition of regret, usefulness of it or an application of it, the result is very weak.\n+ Lemmas 3 and 4 yield that the number of iterations of algorithm 2 is exponential on R. This is not desirable. I do not want to criticize this point harshly, since Hadamard is hard and sometimes the geometry makes these exponential dependences appear, and this could be a result deserving its own paper. This dependence also appears in previous Riemannian online learning works. But rather, I just want to encourage the authors, possibly for future work, to try to improve this to a polynomial dependence (see below for a few comments on this).\n\nWhile I think this works has value, I also think this is not ready for publication. At the very least the errors should be corrected, and the bandit results should not be presented as results (e.g. in the table) unless the authors can justify that the modify notion or regret makes sense. And in any case this should be clearly stated for the readers that only want to firstly check the introduction out.\n\n# Proof Errors\n\nCorrect me if I am wrong but I think I found the following errors in your proofs. I can increase my score if the technical errors can indeed be fixed.\n\n+ The proof of Lemma 1 is wrong, although fixable. The points y_{t+1} are not guaranteed to be in B_p(R) and so you cannot use lemma 29 as you stated it. However, if you look closely at Lemma 5 of Zhang and Sra, you will realize that the lemma actually says that \\zeta depends on \\kappa and c, which a stronger inequality than what you stated (dependence on \\kappa and D). Using that stronger statement then you can show in your Lemma 1 that the \\zeta in the proof depends on d(\\tilde{y}_t, x) \\leq D, and so the proof follows.\n\n+ However, your lemma 2 has the same problem, and when you use it in the proof of lemma 4, you use it with the point y_i, which as you point out in L435, it is y_i \\not \\in \\mathcal{K}. Therefore, the geometric deformation is not \\zeta (which was defined as depending on D), and this does not seem to be so easily fixable.\n\n\n# Other comments / suggestions\n\nThe results with linear minimization oracle look fine to me.\n\nYou should specify in lemma 5, that you always use y\\in B_p(R), since you use f(x) = d(x y)^2/2 and you claim that it is \\zeta smooth, which you can have because when you use lemma 5 in alg 6 it is always y\\in B_p(R). But this is not stated and it was confusing for me.\n\nThis work usually states clearly the assumptions that is making, even though this could be improved, as I suggested. It was good to see the authors taking into account the non convexity of (1-\\delta)\\mathcal{K}. Some works ignore this fact, I wonder if they learn about this in the review of a paper. But the authors here are rigorous and work with the possible non-convex set.\n\n\"(pinpointing a compact set that contains the true optimum can improve time complexity) This makes metric projection onto a subset of Riemannian manifold seemingly indispensable, yet this operation is not only computationally taxing but can also lead to unwanted geometric distortion, which can undermine convergence. Certain works have depended on simplifying assumptions to prove results...\" I disagree with the message that is given here. For several reasons:\n    + Firstly, in many situations, one can \"pinpoint\" a compact set where the optimum is by just estimating the initial distance to minimizer and imposing ball constraints (and using a doubling trick or other tricks if necessary to avoid assuming knowledge of this distance ). In that case, the operation is \"projection-free\" according to your own definition in line 178, due to the simplicity of the operation, so not necessarily computationally taxing.\n    + Secondly, while it is true that using projections can lead to greater geometric distortion that can undermine convergence (e.g. see https://arxiv.org/pdf/2305.16186.pdf where the authors make projected gradient descent work for smooth functions while quantifying the distortion), several works make use of projections to obtain algorithms that previously had to make the assumption of iterates staying in some set, and at the same time the geometric dependence on the convergence rates does not worsen. See for instance https://arxiv.org/pdf/2211.14645.pdf and theorem 7 in https://arxiv.org/pdf/2305.16186.pdf, and https://arxiv.org/pdf/2111.13263v2.pdf section 6 \n    + Thirdly, the works that mandate the iterates to be in a feasible set by assumption do so because they do not know how to enforce or guarantee their algorithms are in some feasible set, even if they have access to projections. It is not like the assumption is made to avoid projections that are \"computationally taxing and with extra geometric distortions, which can undermine convergence\" by using projections. Their techniques do not allow them to use projections and as explained above and more clever algorithms do without extra distortions.\n\n\nYou probably cannot compute \\sigma_i in Algorithm 5 in close form. You probably would need a binary search and then have the algorithm be able to account for an error. Is that right?\n\n# Exponential dependence on the diameter\n\nRegarding the exponential nature of the constants in lemma 3 and running time in lemma 4, this phenomenon is very similar to the exponential constants that appear in the deformations of lemma 2 in https://arxiv.org/pdf/2012.03618.pdf However, in that paper they are interested on optimization, and they show that one can get away with this exponential complexity. The trick is a reduction from global optimization to approximately implementing a ball optimization oracle, so that the algorithms would only need to run in balls where R\\sqrt{-\\kappa} = O(1). The reduction goes as follows: optimize in one such constant-radius ball with linear rates (regularize as it is done in reductions if necessary, although you'd need smoothness of the losses) and then optimize in another ball with center equal to the previously computed point. In the online learning setting, it is harder but you could in principle try to run Riemannian OGC by minimizing the sort of FTRL objective you have by using this reduction (you'd have to optimize with linear rates in the intersection of constant curvature balls and your sets, but every time the infeasible projection would be easy). Or just implement the separation oracle by looking at making progress in constant-curvature balls. Anyway, maybe it doesn't work for you, but I hope it is useful to you to at least know that a problem of this kind has been sort of solved in Riemannian optimization.\n\n# Minor suggestions / typos\n\nL62 \"While a horosphere gsc-convex\" ->\"\"While a horosphere is gsc-convex\"\nL200 \"theLipschitz\" -> \"the Lipschitz\"\nL259 Alg 5. I would not say target vector y, since y is a point.\nL269 Alg 6. \"initial vector y\" -> \"initial vector y_i\" (although again, I would not say initial *vector* )\n\n# Edit after rebuttal\nThe authors provided fixes for the proof errors and a new algorithm two work with two point bandit feedback. I increased my score from reject to accept (from 3 to 7)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Your insightful comments and constructive criticism are highly valued. We've responded to your specific questions and concerns in the following sections.\n>The paper contains some mistakes, and I am not sure if one could fix at least one of them while keeping the stated results.\n\nThank you for bringing this matter to our attention. We have indeed found that the geometric distortion was underestimated, but we have identified a quick fix based on Lemma 5 from Zhang & Sra (2016):\n$$\na^2 \\leq \\zeta(\\kappa,c) b^2+c^2-2bc\\cos A.\n$$\n\nFirst, we amend Definition 1 to express $\\zeta$ as $\\zeta \\coloneqq \\zeta(\\kappa,2R)$. \n\nFor the proof of Lemma 1, it suffices to ensure that the inequality $d(\\tilde{y}_t,x)\\leq 2R$ holds for any $\\tilde{y}_t\\in B_p(R)$ and $x\\in\\tilde{\\mathcal{K}}$. Because $\\tilde{\\mathcal{K}}\\subseteq \\mathcal{K}\\subseteq B_p(R){}$, by the triangle inequality:\n$$\nd(\\tilde{y}_t,x)\\leq d(\\tilde{y}_t,p)+d(p,x)\\leq 2R.\n$$\n\nIn the proof of Lemma 4, we have utilized Lemma 2. To validate that $\\zeta$ describes the correct geometric distortion, we need to prove that $d(y_i,z)\\leq 2R$ holds for any $i\\geq 1$ and $z\\in(1-\\delta)\\mathcal{K}$. This can be achieved through induction. The case for $i=1$ is easy. As $y_1\\in B_p(R)$, $z\\in(1-\\delta)\\mathcal{K}\\subseteq B_p(R)$, the following relationship holds:\n$$\nd(y_1,z)\\leq d(y_1,p)+d(z,p)\\leq 2R.\n$$\nNow assume $d(y_i,z)\\leq 2R$ holds for some $i\\geq 1$ and any $z\\in(1-\\delta)\\mathcal{K}$, then $\\zeta$ is a valid geometric distortion. By Lemma 5 of Zhang \\& Sra (2016) and our Lemma 2,\n\n$$\nd(y_{i+1},z)^2\\leq \\zeta d(y_{i+1},y_i)^2+d(y_i,z)^2-2\\left<\\text{Exp}_{y_i}^{-1}y_{i+1},\\text{Exp}_{y_i}^{-1}z\\right>  \\leq d(y_i,z)^2-\\frac{\\delta^2\\bar{r}^2}{\\zeta}\\leq (2R)^2.\n$$\n\nThus $d(y_{i},z)\\leq 2R$ holds for any $i\\geq 1$ and $z\\in(1-\\delta)\\mathcal{K}$, and the mistake was fixed.\n\n> Moreover algorithm 4 has a regret guarantee in Theorem 2 which is non standard $\\dots$\n\nThank you for your keen observations. We employed this non-standard setting to circumvent a fundamental difficulty on Hadamard manifolds, where $(1-\\delta)\\mathcal{K}$ is non-convex. During the rebuttal phase, we discovered a method to eliminate this drawback and achieve $O(\\sqrt{T})$  regret by using an SO for $\\mathcal{K}$ within the two-point feedback setting. The revised algorithm is outlined below:\n\n> Algorithm: Riemannian Projection-free BCO with Two-point Feedback   \n> Parameters: $\\beta, \\delta, \\delta'$; $\\delta\\in(0,1)$, $\\beta\\in(0,1)$, $\\delta'=(1-\\beta)\\frac{\\sqrt{-\\kappa}(R+r)}{\\sinh(\\sqrt{-\\kappa}(R+r))}\\cdot r$.        \n> Initialize  $x_1\\in\\beta\\mathcal{K}$, $y_1=\\text{Exp}_p(\\frac{\\text{Exp}_p^{-1}x_1}{\\beta})\\quad$   //$y_1\\in\\mathcal{K}$     \n>For $t=1,\\dots,T$:       \n>\n>> Sample $z_t\\sim\\mathbb{S}_{x_t}(\\delta')$\n>>\n>> Play $z_t$ and its antipodal point       \n>>\n>> Observe $f_t$ at $z_t$ and the antipodal point   \n>>\n>>Construct $g_t$ by the estimator in Algorithm 3 of  Wang et al. (2023)        \n>>\n>>$y_{t+1}'=\\text{Exp}\\_{y_t}\\left( -\\eta \\frac{S\\_{\\delta'}}{V_{\\delta'}} \\Gamma_{x_t}^{y_t}g_t \\right)$\n>>\n>>$y_{t+1}\\leftarrow$Output of Algorithm 2 with $\\mathcal{K},r,\\delta$ and $y_{t+1}'\\quad$ //$y_{t+1}\\in\\mathcal{K}$\n>>\n>>$x_{t+1}=\\text{Exp}_p(\\beta \\text{Exp}\\_p^{-1}y\\_{t+1})\\quad$ // $x_t\\in\\beta\\mathcal{K}$\n>\n>End For\n\nProof Sketch: following (15), (18) in our draft, we have\n$$\nE[\\hat{f}\\_t(x_t)-\\hat{f}\\_t(x)]\\leq \\frac{S_{\\delta'}}{V_{\\delta'}}E[\\left< g_t,-\\Gamma_{y_t}^{x_t}\\text{Exp}^{-1}_{y_t}x\\right>+\\left< g_t,\\Gamma_{y_t}^{x_t}\\text{Exp}^{-1}_{y_t}x-\\text{Exp}^{-1}_{x_t}x\\right>]+2\\delta'\\rho G.\n$$\n\nFor the two-point feedback model, by Lemma 17 of Wang et al. (2023), $\\frac{S_{\\delta'}}{V_{\\delta'}}E[\\\\|g_t\\\\|]=O(1)$. Thus,\n$$\n\\frac{S_{\\delta'}}{V_{\\delta'}}E[\\left< g_t,\\Gamma_{y_t}^{x_t}\\text{Exp}^{-1}\\_{y_t}x-\\text{Exp}^{-1}_{x_t}x\\right>]\\leq\\frac{S\\_{\\delta'}}{V\\_{\\delta'}}E[\\\\|g_t\\\\|]\\cdot \\zeta d(x_t,y_t)=O(1)\\cdot \\zeta(1-\\beta)d(y_t,p)=O(\\delta'),\n$$\n\nwhere we use the $\\zeta$ smoothness of $\\frac{1}{2}d(x,y)^2$ and $1-\\beta=O(\\delta')$.\nSince $y_{t+1}$ is an infeasible projection of $y_{t+1}'$ onto $(1-\\delta)\\mathcal{K}$,\n$$\nd(y_{t+1},x)^2\\leq d(y_{t+1}',x)^2\\leq d(y_t,x)^2+\\zeta\\eta^2\\frac{S_{\\delta'}^2}{V_{\\delta'}^2}\\\\|g_t\\\\|^2-2\\eta\\frac{S_{\\delta'}}{V_{\\delta'}}\\left< g_t,-\\Gamma_{y_t}^{x_t}\\text{Exp}^{-1}_{y_t}x\\right>\n$$\nholds for any $x\\in(1-\\delta)\\mathcal{K}$. Combining the above inequalities, we have\n$$\nE[\\hat{f}_t(x_t)-\\hat{f}\\_t(x)]\\leq\\frac{d(y_t,x)^2-d(y\\_{t+1},x)^2}{2\\eta}+O(\\eta)+O(\\delta').\n$$\nholds for any $x\\in(1-\\delta)\\mathcal{K}$. Also, following (20), (21) and taking $x=\\text{Exp}_p((1-\\delta)\\text{Exp}^{-1}_p x^*)$, we have $E[f_t(z_t)-\\hat{f}_t(x_t)]=O(\\delta')$ and $E[\\hat{f}_t(x)-f_t(x^*)]=O(\\delta+\\delta')$. \n\nIn sum,\n$$\n\\sum_{t=1}^TE[f_t(z_t)-f_t(x^*)]=O\\left(\\frac{1}{\\eta}+(\\eta+\\delta+\\delta')T\\right).\n$$\nChoosing $\\eta,\\delta,\\delta'=O(\\frac{1}{\\sqrt{T}})$, we get $O(\\sqrt{T})$ regret.\n\nYour comments or suggestions on this idea would be greatly appreciated. We are more than willing to replace the current BCO result with this revised version, as it resolves the problem related to the non-standard setting.\n\n> Lemmas 3 and 4 yield that the number of iterations of algorithm 2 is exponential on R $\\dots$\n\n Thanks for your detailed suggestions. We will consider this interesting problem in the near future.\n\n> You should specify in lemma 5, that you always use $y\\in B_p(R)$. You probably cannot compute $\\sigma_i$ in Algorithm 5 in close form.\n\nThank you for your insightful suggestion. You are indeed correct, and we appreciate your pointing this out. We will provide more detailed discussions in our revised version.\n\n> \"(pinpointing a compact set that contains the true optimum can improve time complexity) $\\dots$ without extra distortions.\n\nThank you for sharing your insightful understanding of Riemannian metric projection. We will make sure to carefully revise these sentences in the updated version of our work."}, {"review_id": "zEFjFkun5i", "reviewer": "Reviewer_4T7s", "summary": "The paper focuses on constrained Riemannian online optimization on the Hadamard manifold. Existing Riemannian online optimization methods often require projections, which present computational complexity challenges in high-dimensional settings. To address this issue, the authors have developed a projection-free Riemannian online optimization structure, implemented under two scenarios - the separation oracle and the linear optimization oracle.\n\nInitially, they explore the Infeasible R-OGD and Infeasible Riemannian bandit algorithm under a separation oracle, for which the regret bounds are proved to be $\\mathcal O(\\sqrt T)$ and $\\mathcal O(T^{\\frac{3}{4}})$ respectively for geodesically convex functions. Furthermore, they consider the Block R-OGD under a linear optimization oracle, and provide a proof for regret bounds of $\\mathcal O(T^{\\frac{3}{4}})$ and $\\mathcal O(T^\\frac{2}{3})$ for geodesically convex and geodesically strongly convex functions respectively. It's noteworthy that all these regret bounds match their respective Euclidean counterparts.", "questions": "- I'd appreciate if the authors could expound on their primary insights in this paper. Specifically, it would be beneficial to understand the significant challenges encountered while extending the Euclidean projection-free algorithm to the Riemannian manifold. \n\n- Additionally, I'm interested in knowing whether the proposed Riemannian projection-free method could be easily extended to $cat(K)$ spaces. If this is not feasible, could the authors shed light on the primary hurdles that prevent such an extension?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "-  Originality & Significance: Althogh the paper has retricted novelty (discuss in the following), it provides, to my best of knowledge.  the first no-regret guarantee for projection-free Riemannian OCO. Also, it is nice to see that all regret bounds match their Euclidean counterparts.\n\n- Clarity & Significance: The paper is well-organized, techinally sound and easy to follow. The assumption is standard in the literature of Riemannian optimization and Riemannian OCO.", "weaknesses": "- Retricted novelty: The majority of the analysis leans heavily on the Euclidean Analogue and Jacobian/Hessian comparison. Although it is the standard structure in Riemannian optimization literature, it would have been enriching to see some novel conceptual ideas that engage more specifically with the geometry of the problem.\n\n- Positive curvature: The study focuses on the Hadamard manifold, known for its non-positive sectional curvature. Conversely, in practical scenarios, there's considerable work undertaken within spaces possessing positive sectional curvature like SO(3). The methodology and algorithms presented in this paper appear, at first glance, to be easily extendable to accommodate $cat(K)$ spaces. However, the authors have not provided any explanation or context for why such positive curvature spaces were not considered in their study.  A consideration of such spaces could have added more depth and wider applicability to the research.\n\n- Possible typo: formula about $\\bar r $ after l227: there should be a additional $r$ at RHS.  \n Algorithm 5: $y$ seems to be a point rather than a tangent vector.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and helpful feedback. We will revise typographical errors accordingly. We have addressed your specific questions and concerns below.\n> I'd appreciate if the authors could expound on their primary insights in this paper. Specifically, it would be beneficial to understand the significant challenges encountered while extending the Euclidean projection-free algorithm to the Riemannian manifold.\n\n_Repeated from response to Reviewer xiK4, Comment 4, with brief revisions._\n\nThank you for the question. Our work builds heavily on Garber & Kretzu (2022) and Wang et al. (2021, 2023), but we have several novel contributions:\n\n1.  We identify that the shrinking set $(1-\\delta)\\mathcal{K}$ is non-convex and subsequently extend the definition of infeasible projection initially presented by Garber & Kretzu (2022) to accommodate non-convex settings.\n2.  Quantifying the progress made with each call to the separation oracle presents a highly non-trivial challenge. We overcome this in Lemma 3, where we amalgamate Lemma 19 (equivalent to Lemma 45 in Wang et al. (2023)) with meticulous computation involving Jacobi field comparisons.\n3.  Concerning the linear optimization oracle, deriving a separating hyperplane using Riemannian Frank-Wolfe stands as the principal hurdle. We manage to overcome this through an innovative application of Riemannian cosine laws. For further insights, we refer readers to Remark 2 and the proof of Lemma 5 in our manuscript.\n\n> Additionally, I'm interested in knowing whether the proposed Riemannian projection-free method could be easily extended to CAT$(\\kappa)$ spaces. If this is not feasible, could the authors shed light on the primary hurdles that prevent such an extension?\n\nIt is not too difficult to generalize the results in our paper to CAT$(\\kappa)$ spaces. To achieve this extension, the following adjustments would be necessary in our manuscript:\n\n1.  We may assume that the sectional curvature lies in the range $[\\kappa,K]$. In this context, we can replace Lemma 30 in our draft with Corollary 2.1 from Alimisis et al. (2020). When $K>0$, we must further assume that the diameter of the decision set is upper-bounded by $\\frac{\\pi}{\\sqrt{K}}$​.\n2.  Lemma 3 would need to be revised to recompute the Jacobi field, taking into account the sectional curvature of the manifold. Notably, in the case of manifolds with positive curvature, an initial computation provides $\\bar{r}=O\\left(\\frac{\\sin(\\sqrt{K}(R+r))}{\\sqrt{K}(R+r)}\\right)\\cdot r$, a relation that does not exhibit exponential dependence on $(R+r)$.\n3.  The separation theorem, specifically for Hadamard manifolds as outlined in Silva Louzeiro et al. (2022), would require generalization to CAT$(\\kappa)$ spaces. This change ensures that the separation oracle remains well-defined.\n \nWe discovered that delving into all of these details did not offer additional insights and might have actually diminished the readability of the text. Therefore, we chose not to include them in the current version. However, we recognize the importance of this matter and will provide further discussions on this subject in the revised version."}, {"review_id": "9VOQxxfL3B", "reviewer": "Reviewer_FXr6", "summary": "The paper considers Riemannian online optimization problems over sets of constraints and tries to tackle them by avoiding projections onto the constraint set. This is an already established line of research in Euclidean optimization and the results follow the structure of Garber and Kretzu (2022). The results of the latter are adapted to the Riemannian setting using well-known geometric bounds.", "questions": "1. I see some slight discrepancy in the selection of parameters and worst-case regret bounds between this paper and Garber and Kretzu (2022) (I will refer to that as GK from now on). Could you explain why this is happening? To be more specific: \n\nTheorem 1 in this paper and Theorem 6 in GK do not have exactly the same constants. I think you choose $c=1/2$ and $c_1=4$, but I cannot see how the regret bound and the bound in the number of oracle calls become the same for $\\zeta=1$.\n\nThe parameters $\\eta$ and $\\delta$ in Theorem 2 of this paper are not chosen the same way as the ones in Theorem 7 of GK with respect to $T$. This is quite worrying.\n\nTheorem 3 in both papers have the same parameters (for $\\zeta=1$), but the regret bound features slightly different constants.\n\nDiscrepancies like that seem not to be the same among Lemmas 1 and Theorems 4 between the papers.\n\n\n2. I struggle to understand Algorithm 5, I think that after the if statement, you should have $< \\exp^{-1}_{x_i}(y),\\exp^{-1}_{x_i}(v_i) > \\leq \\epsilon$ or $d(x_i,v_i)^2 \\leq 3 \\epsilon$. Is that true?\n\n3. As I see the results, it should pretty straightforward to have similar ones for manifolds of positive curvature (with $\\zeta=1$ and $\\bar r=r$). Is there any specific reason that you didn't attempt that?\n\n", "limitations": "The authors adequately discuss some limitations of their work in the conclusion of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is concerned with problems of profound importance for the neurips community. It is well-written and can be followed easily by people with reasonable background in Riemannian optimization. The use of geometric bounds (law of cosines in negative curvature, spread of Jacobi fields) is clearly explained. The authors pay special attention in computability issues behind the separating and linear oracles used, building upon the contributions of Weber and Sra (2022b). The convergence guarantees much the ones of the Euclidean setting in Garber and Kretzu (2022) up to constants.", "weaknesses": "I am not thrilled by the level of originality since the paper follows closely the one by Garber and Kretzu (2022) and used geometric bounds that are well-known in the Riemannian optimization community for quite some time. Still, it is a clearly-written concrete contribution to a problem of interest, thus I think that publication in the conference is totally justifiable.\n\nThere are some points in the paper that I find peculiar as I specify in my questions' section. This is the main reason that I give a score only slightly above the acceptance threshold (which I will revisit in case the authors answer me concerns convincingly).\n\nI would advise the authors to revisit the title of the paper. When I see \"On ...\" I automatically form the impression that the paper features some vague discussion about a research topic without really useful contributions, which is not the case here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your detailed and constructive feedback. Your specific questions and concerns have been addressed as follows.\n> I see some slight discrepancy in the selection of parameters and worst-case regret bounds between this paper and Garber and Kretzu (2022) (I will refer to that as GK from now on). Could you explain why this is happening? \n\nThanks for the question on the discrepancy between our paper and Garber and Kretzu (2022). We  clarify these concerns item by item as follows.\n\n1)  The discrepancy between our Theorem 1 and Theorem 6 of Garber & Kretzu (2022) might stem from a misunderstanding. Upon closer examination, we can observe that Theorem 6 of Garber & Kretzu omitted the dependence on $c_1$​, so its guarantee can be rewritten as:\n$$\n\\text{Reg}\\_T\\leq\\left(GRc+\\frac{Gc_1r}{4}+\\frac{4GR^2}{c_1r}\\right)\\sqrt{T}.\n$$\nIn our work, the parameters correspond to $c=\\frac{1}{2}$ and $c_1=\\frac{4R}{r}$. By substituting these values into Theorem 6 of Garber & Kretzu (2022), we obtain:\n$$\n\\text{Reg}\\_T\\leq\\left(GRc+\\frac{Gc_1r}{4}+\\frac{4GR^2}{c_1r}\\right)\\sqrt{T}=\\frac{5GR\\sqrt{T}}{2}.\n$$\nThis result matches the guarantee of our Theorem 1 when setting $\\zeta=1$. Similarly, we can compute the number of oracle calls in Theorem 6 of Garber & Kretzu (2022):\n$$\nN_{calls}\\leq \\left(\\frac{c_1R}{cr}+\\frac{c_1^2}{4c^2}+1\\right)T=\\left(\\frac{8R^2}{r^2}+\\frac{16R^2}{r^2}+1\\right)T.\n$$\nThis is in agreement with our result, once again, when setting $\\zeta=1$ and $\\bar{r}=r$.\n2) We appreciate your diligence in pointing out the apparent difference between our Theorem 2 and Theorem 7 of Garber & Kretzu (2022). This discrepancy was due to a typographical error. The correct parameters were used in the proof of Theorem 2 (Line 524). We will fix this in the revised version.\n3) The discrepancy between our Theorem 3 and Theorem 3 of Garber & Kretzu (2022) is due to numerical rounding. The regret guarantee of Theorem 3 in our paper is\n$$\n\\text{Reg}_T\\leq GR\\left(\\left(\\frac{5}{2}\\zeta^2+\\sqrt{180}\\zeta+\\frac{4}{\\zeta}\\right)T^{\\frac{3}{4}}+20T^{\\frac{1}{2}}\\right).\n$$\nAfter choosing $\\zeta=1$, we find $\\frac{5}{2}\\zeta^2+\\sqrt{180}\\zeta+\\frac{4}{\\zeta}=19.9164\\approx 20$, which leads to the same result as Theorem 7 of Garber & Kretzu (2022):\n$$\n\\text{Reg}_T\\leq 20GRT^{\\frac{1}{2}}+20GRT^{\\frac{3}{4}}.\n$$\n\n\n> I struggle to understand Algorithm 5, I think that after the if statement, you should have $< \\text{Exp}^{-1}_{x_i}(y),\\text{Exp}^{-1}_{x_i}(v_i) > \\leq \\epsilon$ or $d(x_i,v_i)^2 \\leq 3 \\epsilon$. Is that true?\n\n Thanks for pointing out this. Sorry there is a typographical error and this line verifies if $\\left<\\text{Exp}_{x_i}^{-1}y,\\text{Exp}_{x_i}^{-1}v_i\\right>\\leq\\epsilon$ or $d(x_i,y)^2\\leq 3\\epsilon$ holds. If $d(x_i,y)^2 \\leq 3 \\epsilon$ holds, then we have completed the necessary tasks because $x_i$ is sufficiently close to the target point $y$. And if $\\left<\\text{Exp}_{x_i}^{-1}y,\\text{Exp}_{x_i}^{-1}v_i\\right>\\leq\\epsilon$ holds, by the definition of $v_i$, we have\n$$\n\\left<\\text{Exp}_{x_i}^{-1}y,\\text{Exp}_{x_i}^{-1}x\\right>\\leq \\left<\\text{Exp}_{x_i}^{-1}y,\\text{Exp}_{x_i}^{-1}v_i\\right>\\leq \\epsilon\n$$\nholds for any $x\\in\\mathcal{K}$. This relationship can be leveraged to construct a separating hyperplane between $y$ and $\\mathcal{K}$, as outlined in Lines 542-546.\n\n> I would advise the authors to revisit the title of the paper.\n> \nThanks for your thoughtful suggestion. We will be more than happy to remove the word \"On\" in the title.\n\n> As I see the results, it should pretty straightforward to have similar ones for manifolds of positive curvature (with $\\zeta=1$ and $\\bar r=r$). Is there any specific reason that you didn't attempt that?\n\n_Repeated from response to Reviewer 4T7s, Comment 2, with brief revisions._\n\nIt is not too difficult to generalize the results in our paper to manifolds of positive curvature and even to CAT$(\\kappa)$ spaces. To achieve this extension, the following adjustments would be necessary in our manuscript:\n\n1.  We may assume that the sectional curvature lies in the range $[\\kappa,K]$. In this context, we can replace Lemma 30 in our draft with Corollary 2.1 from Alimisis et al. (2020). When $K>0$, we must further assume that the diameter of the decision set is upper-bounded by $\\frac{\\pi}{\\sqrt{K}}$​.\n2.  Lemma 3 would need to be revised to recompute the Jacobi field, taking into account the sectional curvature of the manifold. Notably, in the case of manifolds with positive curvature, an initial computation provides $\\bar{r}=O\\left(\\frac{\\sin(\\sqrt{K}(R+r))}{\\sqrt{K}(R+r)}\\right)\\cdot r$, a relation that does not exhibit exponential dependence on $(R+r)$.\n3.  The separation theorem, specifically for Hadamard manifolds as outlined in Silva Louzeiro et al. (2022), would require generalization to CAT$(\\kappa)$ spaces. This change ensures that the separation oracle remains well-defined.\n \nWe discovered that delving into all of these details did not offer additional insights and might have actually diminished the readability of the text. Therefore, we chose not to include them in the current version. However, we recognize the importance of this matter and will provide further discussions on this subject in the revised version."}, {"review_id": "oklSZtvhit", "reviewer": "Reviewer_2HSe", "summary": "The authors present online algorithms for geodesically convex losses on Riemannian manifolds. Their algorithms do not call the expensive operation of projection onto a feasible set. Instead of projection, they rely on two oracles to provide a direction of descent: a separation oracle and a linear oracle. Both require an extension of the concept of hyperplanes from Euclidean space to the manifold, for which they use an inverse exponential map. This map transforms points on the manifold into tangent space vectors, enabling operations on the manifold without the need for explicit projection operations. In addition, they also consider the projection onto a geodesic ball, which is computable with high accuracy and thus effectively projection free. Their algorithms give adaptive regret guarantees which are sublinear in the horizon. ", "questions": "I am not sure why $\\tilde{\\mathcal{K}} = (1-\\delta) \\mathcal{K}$ is considered as the feasible set for the separation oracle. ", "limitations": "The authors have acknowledged the limitations of their work, specifically the absence of a membership oracle, and have discussed potential enhancements to their algorithms. These improvements include utilizing the separation oracle for strongly convex losses, reducing the reliance on the number of calls regarding the set's diameter and a faster method to optimise the objective in the linear oracle. ", "rating": 8, "confidence": 1, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The authors' contribution is significant as they address the challenge of projecting onto a Riemannian manifold, which is computationally expensive and can lead to geometric distortions. This area of research seems relatively less explored. \n\n- The writing style is clear and they provide a comprehensive background on Reimannian geometry, making it easy for a read to grasp the problem and motivation. \n", "weaknesses": "As I am not familiar with this area, I am unable to identify any weaknesses or limitations. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time and effort you put into understanding our work. Your supportive and constructive review means a lot to us. Below, we have provided answers to your specific questions and addressed your concerns.\n> I am not sure why $\\tilde{\\mathcal{K}} = (1-\\delta) \\mathcal{K}$ is considered as the feasible set for the separation oracle.\n\n Thanks for your question. The main reason is we want to make sufficiently large progress for each call to the separation oracle. By Lemma 2, we need a separating hyperplane $-\\left<\\text{Exp}_y^{-1}z,g\\right>\\geq Q$ and the progress at each call is on the order of $O(Q^2)$. A separating oracle may generate a separating hyperplane in the form of $-\\left<\\text{Exp}_y^{-1}x,g\\right> > 0$ for any $x\\in\\mathcal{K}$, but the corresponding $Q$ could be arbitrarily small, even as low as $T^{-100}$. This could lead to a significant number of oracle calls. By computing an infeasible projection onto $\\tilde{\\mathcal{K}} = (1-\\delta) \\mathcal{K}$, we can achieve projection-free online learning with a more reasonable $O(T)$ oracle calls. This idea is briefly outlined in our draft (Lines 218-223)."}]

Author rebuttal:

Meta-review: I thank the reviewers for their comments. I took the discussion as well as the author feedback into consideration. there seems to be general consensus among the reviewers that the paper is interesting (now that the error has been fixed). I am a bit unhappy over the rushed presentation and the generally low quality of the paper. i will recommend acceptance - this is an optimistic descent step - and I strongly urge the authors to revise their work thoroughly for the camera-ready version, taking the comments of the reviewers into account.
Decision: Accept (poster)