Strongly Convex Sets in Riemannian Manifolds
Authors: Damien Scieur
David Martínez-Rubio
Thomas Kerdreux
Alexandre d'Aspremont
Sebastian Pokutta
Venue: ICLR 2026 Poster (2026)
Keywords: Strong convexity
Riemannian
Manifold
Frank-Wolfe
optimization
nonconvex
Primary area: optimization
TL;DR: We propose various definitions of strong convexity for uniquely geodesic sets in a Riemannian manifold, examine their relationships, introduce tools to identify strong convexity, and analyze the convergence of optimization algorithms over these sets

Abstract: Strong convexity plays a key role in designing and analyzing convex optimization algorithms and is well-understood in Hilbert spaces. However, the notion of strongly convex sets beyond Hilbert spaces remains unclear. In this paper, we propose various definitions of strong convexity for uniquely geodesic sets in a Riemannian manifold, examine their relationships, introduce tools to identify geodesically strongly convex sets, and analyze the convergence of optimization algorithms over these sets. In particular, we show that the Riemannian Frank-Wolfe algorithm converges linearly when the Riemannian scaling inequalities hold.

STRONGLY CONVEX SETS IN RIEMANNIAN MANI- FOLDS
Damien Scieur* Samsung AT Lab, Montreal, Canada.
David Martinez-Rubio" IMDEA Software Institute, Madrid, Spain.
Thomas Kerdreux" f Galeio,
Paris, France.
Alexandre d' d'Aspremont CNRS & D.I. École Normale Supérieure, Paris, France.
Sebastian Pokutta Zuse Institute Berlin & Technische Universität, Berlin, Germany.
ABSTRACT
Strong convexity plays a key role in designing and analyzing convex optimiza- tion algorithms and is well-understood in Hilbert spaces. However, the notion strongly convex sets beyond Hilbert spaces remains unclear. this paper, we propose various definitions of strong convexity for uniquely geodesic sets in a Riemannian manifold, examine their relationships, introduce tools to identify geodesically strongly convex sets, and analyze the convergence of optimization al- gorithms over these sets. In particular, we show that the Riemannian Frank- Wolfe algorithm converges linearly when the Riemannian scaling inequalities hold.
INTRODUCTION
In Euclidean space, strong convexity is key property of convex objects (e.g., normed spaces, func- tions, or sets). Algorithms exploiting strong convexity enjoy faster convergence, tighter generaliza- tion bounds, and stronger concentration properties. For example, strong convexity sharpens concen- tration inequalities for martingales (Pisier, 1975; 2011), enables faster projection-free optimization methods such as Frank- Wolfe (Demyanov and Rubinov, 1970; Garber and Hazan, 2015: Molinaro, 2020; Kerdreux et al., 2021b;c), and plays a key role in learning theory (Huang et al., 2017; Moli- naro, 2020; Kerdreux et al., 2021a; Dekel et al., 2017; Bhaskara al., 2020a;b) and bandit problems (Bubeck et al., 2018; Kerdreux et al., 2021d).
However, many modern machine-learnnng problems are posed in non-Euclidean settings such as metric spaces Riemannian manifolds. Examples include optimal transport, where entropy- regularized formulations like Sinkhorn divergences (Cuturi, 2013; Feydy et al., 2019) exploit Wasserstein geometry (Villani, 2009), well as Wasserstein barycenters, distributions spaces, or manifold-valle valued data. Such applications have spurred the development Riemannian optimization methods (Sun al., 2017; Allen-Zhu al., 2018; Hosseini and Sra, 2017: 2020).
curved
Recent years have seen a growing interest in Riemannian optimization for deep learning. For in- stance, specialized architectures such as DreamNet leverage Riemannian geometry to learn from symmetric positive definite (SPD) matrices in vision tasks (Wang et al., 2022a), while robotics ap- plications exploit manifold-awar optimization acquire complex motor skills (Wang et al., 2022b). Beyond applications. there is also progress in developing learning-to- -o-ttmmize frameworks on man- ifolds (Gao et al., 2022) and in designing Riemannian counterparts of neural network architectures, such as residual networks (Katsman et al., 2023). This trend has motivated comprehensive surveys (Fei al., 2025) highlighting the relevance of geometric optimization modern machine learning.
Yet, the role of strong convexity in non-Fuclidean settings remains poorly understood:
What does mean for set be strongly convex curved spaces.
and how can this structure be exploited algorithmically?
"Equal contribution (randomized order) Work conducted while the author was affiliated with the Zuse Institute Berlin (7IB).

---

Related Work. While strong convexity of functions extends relatively smoothly to metric and geodesic settings, the situation for sets far less clear. Beyond Euclidean spaces, no single accepted definition exists. Several alternatives have been proposed in metric spaces, particularly in non-positively curved (CAT(()) spaces (Aleksandrov, 1957), and related ideas have appeared in concentration inequalities (Gouic al., 2019; Ahidar-Coutris and in online learning (Paris, 2020; 2021). However, these notions are not equivalent and often diverge in their implications, falling short of providing the structural properties required by modern optimization algorithms.
al., 2020; Mérigot al., 2020)
While (Aleksandrov, 1957) and subsequent CAT(O) literature characterize curvature- based convex- ity of the ambient space, our work can be viewed as a set-level refinement of that idea. In CAT(O) spaces, convexity follows globally from nonpositive curvature; in our framework, we analyze how local curvature and the exponential map jointly induce strong convexity of specific subsets. Like- wise, (Paris, 2020; 2021) leverages geodesic convexity in online learning but does not quantify set curvature or provide conditions for algorithmic strong convexity. Our definitions, therefore, bridge these directions: they recover metric convexity when curvature is nonpositive, while additionally providing geometric and algorithmic tools that apply beyond CAT(O) settings.
Finally, the Riemannian scaling inequality in Eq. (RSI) is conceptually related to proximal smooth- ness (Davis et al., 2025), yet the two notions analytically opposite. Proximal smoothness (and its uniform normal inequality) requires an upper bound that holds uniformly over all outward tangent directions. In contrast, RSI provides a one-sided lower bound evaluated only at the LMO maxi- mizer within a restricted tangent subset. The two conditions are thus dual in structure and tailored distinct algorithmic regimes.
This paper provides the first systematic study of strong convexity of sets in Rie- mannian manifolds, bridging geometric structure and algorithmic benefits. We introduce novel properties of sets defined in Riemannian manifolds, provide examples, and demonstrate improved convergence rates when minimizing functions over such sets. For conciseness, proofs are deferred to Appendix A and technical results to Appendix B.
Contributions.
1. Section introduces various definitions of strongly convex sets in Riemannian manifolds and establishes relationships between them.
2. Section 3 introduces the notion of approximate scaling inequality and its link with what we call double geodesic strong convexity.
3. In Section 4, we prove that sublevel sets of geodesically smooth. strongly convex functions are strongly convex in Riemannian manifolds under mild conditions, providing a construc- tive perspective for identifying such sets.
4. In Section 5, we derive a linear convergence bound for the Riemannian Frank- Wolfe algo- rithm when the constraint set satisfies the (Approximate) Riemannian Scaling Incquality.
5. Appendices D and E provide examples of strong convex sets in Riemannian manifolds. More precisely, Appendix D) shows that Riemannian balls (with restricted radius) satisfy the strongest of our notions of Riemannian strong geodesic convexity. Appendix E details a simple linear minimization oracle for the sphere manifold.
Although strong convexity can be verified directly using their definitions, our results provide more practical, Fuclidean-style certification tools. In particular, (i) Geodesic balls with bounded radius are Riemannian strongly convex (Theorem D.4) and (ii) Sublevel sets of smooth, strongly convex functions are both geodesically and geadeslgy strongly convex (Theorem 4.2).
Impact. Defining and identifying strongly convex sets manifolds provides the necessary founda- tion to design algorithms that can exploit this structure. For example, once such sets are character- ized, the Riemannian Frank-Wo Wolle (RFW) achieves faster convergence, analogous to the Euclidean setting (Garber and Hazan, 2015; Braun et al., 2022). Extending these ideas to curved spaces thus offers both theoretical and practical tools for scalable Riemannian optimization in machine learning.
PRELIMINARIES, NOTATIONS, AND ASSUMPTIONS
Strong Convexity in Hilbert Spaces In Hilbert spaces, there exist many equivalent definitions of strongly convex sets (Goncharov and Ivanov, 2017). We recall here classical definitions.
2

---

Proposition 1.1 (Strong Convexity of Sets in Hilbert Spaces (Goncharov and Ivanov, 2011),,2017)). Con- sider compact convex set C C R", its boundary âc, O, and norm ||=|| vxx, C is a-strongly convex w.z.t. ||. if and only if it satisfies the following equivalent assertions. (a) For all (x.y) E C C. t [0, and 2 IR" s.t. ||
have
(1 t)= + ty + a(1 t)e -
Intuitively, a set called strongly convex if. for all straight lines the set and all points p in the line, there exists ball around p of a certain radius that is contained in the set. (b) For all (x, v) E C x aC and w E Ne(u) (the normal cone of at v), we have
(w: v - x) 2 aalw||lle 1| x112
(scaling ineq.)
In the original definitions, a takes the value 1/2R, where R > O is the radius of some balls that are used for an alternative equivalent definition of strong convexity of sets (Vial, 1982; 1983; Goncharov and Ivanov, 2017). We use in this work since it is simpler for our purposes. We also note that (scaling ineq.) is equivalent to the following condition (Kerdreux et al., 2021h, Lemma 2.1):
Vlz, w) E EC x RR" (w: x)) 2 ai|Ww|l|e- xz|² where v E argmax (w;; z).
(2)
=EC
Moreover, Journée et al. (2010, Theorem 12) shows that the sublevel sets of L-smooth, μ-strongly convex functions (see Definition C.17) are themselves strongly convex. In particular, the following set is 1/(22/2s))) convex:
Qs = ( where min ((x).
Notations We now summarize the essential notations. The reader find in Appendix C no- tions about metric spaces (Appendix C.I), Riemannian manifolds (Appendix C.2), sets defined in Riemannian manifolds (Appendix C.3), and functions defined over a manifold (Appendix C.4).
A metric space is pair (M, dm)), where M is a set and d (z, y) a distance function between H. y M that satisfies positivity, symmetry, and the triangle inequal- [0, 1] + M between & and is a curve with no intrinsic acceleration satisfying (0) x. ((1) y. If any two points in M can be connected by such geodesic, it is geodesic metric space; if the geodesic is unique, it is uniquely geodesic.
Metric and Geodesic Spaces.
ity. A geodesic
Riemannian Manifolds. M a Riemannian manifold it is equipped with Riemannian metric which defines for all x E M an inner product (--)z on the tangent space T.M. The distance (x. y) is given by the length of the shortest geodesic connecting x and y. For all x M and v T.M, let [] - M be the geodesic satisfying 7(0) = with (0))) = v. The exponential map Exp,, T.M + M, is defined as Exp,, (e) = (1). Martan-Hadamara spaces (a.k.a. complete CAT(O) spaces) are complete, simply connected Riemannian manifolds with non- positive curvature (Definition C.4).
Main assumptions. In this paper, we will assume the following statements.
Assumption 1.2. The set C C M is compact and uniquely geodesically convex; ie., for any x, E C. there exists a unique minimizing geodesic contained entirely in C.
Assumption 1.3 (Distances Equivalence). Let the set C C M satisfies Assumption 1.2 and let d: C I + be a distance function, possibly different from the Riemannian distance. There exists 0 < IM < Lm such that for all pairs (x. v) C
Emll (xxp=>(0)) < d(z,v) v) S LM (xxp=(())l
(4)
Since we assume C to be uniquely geodesic, the inverse exponential map Exp, (v), also called logarithmic map, is well defined (see Remark in Appendix C.3 for more details).
3

---

Discussion Assumption 1.2 is standard and essentially requires that the exponential map is bi- jective. This condition is needed in many optimization settings; for example, the RFW algorithm relies on the inverse exponential map (Weber and Sra, 2023). Moreover, Assumption 1.3 becomes non-restrictive under Assumption 1.2: the exponential map is bijectíve, the metric distance can be taken to coincide with the norm of the logarithmic map. yielding fM L.M = (see Remark in Appendix C.3). We retain this assumption only to cover cases where an alternative distance d is used define strong convexity or smoothness of function f defined M.
2 STRONGLY CONVEX SETS IN RIEMANNIAN MANIFOLDS
Geodesic str. cvx
Double geodesic str. evx
Riemannian str. cvx
Tangent
No
Yes
Yes
Exp/Log
No
Exp + Parallel Transport
Log map
Meaning Exist a geodesic ball around geodesic points
Exist a geodesic ball the tangent space
Log-image of the set is Enclidean str. cvx.
Example
Same as double geodesic str cvx
Sub-level sets of smooth, strongly convex functions
Small balls in manifolds with bounded-curge
Table Summary of the three definitions of strong convexity introduced in this paper
We propose several definitions of strongly convex sets for Riemannian manifolds, which all collapse to Eq. (1) when M is the Euclidean space (see Table I for a summary).
Geodesic Strong Convexity The geodesic strong convexity adapts (1) using geodesics in M, with- out considering its Riemannian structure (i.e., the definition does not use the tangent space).
Definition 2.1 (Geodesic Strong Convexity). Let M be Riemannian manifold, and let C M satisfies Assumption 1.2. The set C is geodesically a-strongly convex w.r.t. the distance function
d M. M + IRt if. for all geodesics y joining x, y and every [0, 1], we have that the following ball is in C:
E M d(c((),)) S at(1 ttd
(5)
Riemannian Strong Convexity The following definition leverages the Riemannian structure of M via an assumption on the exponential map. The definition states that the inverse image of the set C C .M by the inverse exponential map at each E .M must be strongly convex in T&M for all the Euclidean sense. For a uniquely geodesic set C, the inverse exponential map is always well defined for any two points in C, cf. Remark 1.
Definition 2.2 (Riemannian Strong Convexity). Let M be a Riemannian manifold, and C S M satisfies Assumption 1.2. The set C is Riemannian a-stroongly convex set if. for all C.
Exp, (C) == ty T.M: y Exp= (z), (x), EE
is a-strongly convex w.r.f. Il. in the Euclidean sense (1).
Double Geodesic Strong Convexity In Definition 2.3, we now leverage the Riemannian structure through the existence of the tangent space and the exponential map provide another notion of strong convexity of a set, analogous to the Euclidean formulation in (1). For t E [o, 1]. we make the parallel between the term fx (1- f)y in (1) and (t), the geodesic ? joining y, and in M. Then,
(1) in M ensures that we have Exp,(t) (at(1 t)d (z. 3)2) C for all E M with || = 1.
Definition 2.3 (Double Geodesic Strong Convexity). Let M be Riemannian manifold, and C C M satisfies Assumption 1.2. The set C is a double geodesically a-strongly convex set w.E.t d(.,)) if. all geodesics "i joining x. y C and all t [0, 1].
Vz M ||=]|~(0) S at(( - t)d (x,
+
(xp exists and is in C.
(6)
The double geodesic strong convexity can also be rewritten in terms of the exponential map if Expx(1 (at(1-t)d (x. y)2) E for all of unit norm in M. this manner, mirrors the alge- braic expression of the Fuclidean definition provided in (1) but within the Riemannian setup. We
4

---

i Al deeth of altt oPPaaa)
Expacy
I-T Bette
Tingk
M
M
Figure 1: Illustration the different definitions of strong convexity.
(Left) Geodesic strong convexity (Definition 2.1): For each pair of points 2, y in the set C, it is possible to draw a "geodesic ball" centered at point on the geodesic 7(4) connecting x and y, such that the ball remains entirely within C. (Center) Riemannian strong convexity (Definition 2.2): For all C, the image of the set under the inverse exponential map. Exp_'((), (C), is strongly convex set. (Right) Double geodesic strong convexity (Definition 2.3): The image a ball in M of radius (1 l)d2 (z, y) under the exponential map (xp,xe) (-) is contained within C.
denote it as the double geodesic strong convexity also because the point (xpp)co(a((111)dPC( (()d((11)((r))))) is built via two geodesics, one between and y, and another starting (t).
Riemannian Scaling Inequality (RSI) In Euclidean space, (scaling ineq.) is an equivalent defini- tion of strongly convex set (Prop. 1.1), which helps in establishing convergence proofs of various algorithms. Here, we propose the notion of the RSI, which is the the Riemannian counterpart of (2).
Definition 2.4 (Riemannian Scaling Inequality (RST)). Let M a Riemannian manifold, and let C C M satisfies Assumption 1.2. The elements in the C then satisfy the RSI if. for some 0, for all x E C, w E T,
(x; 2 ai|l [|r
for all E argmax, sec (w; (x))=()))=
(RSI)
We now show some implications and equivalences between strong convexity notions and scaling inequality for manifolds. We summarize the links between these notions here.
Prop. 2.6 Hadamard
Prop 1.3
Riemannian
Geodesic Stron
Double Gendesic Prop. 3.3
Approx. RSI
Strong Convexity
Convexity
Strong Convexity
Riemannian
Prop. 2.5
Approx.
String Convexity
Hilbert spaces, the scaling inequality and global strong convexity of a set are equivalent notions (Proposition 1.1), but not in Riemannian manifolds. Instead, Proposition 2.5 states that the Rieman- nian strong convexity implies a RSI, the latter being valuable for analyzing algorithms (Section 5).
Proposition 2.5 (Riemannian Strong Convexity implies RSI). Let M be a Riemannian manifold, and C C. M satisfies Assumption 1.2. Let C be Riemannian a-strongly convex set (Definition 2.2). Then, the elements the set C also satisfy the RSI (Definition 2.4).
Proposition 2.6 (Riemannian Strong Convexity implies Geodesic Strong Convexity). Let M be Riemannian manifold, and C C M satisfies Assumption 1.2 and d(.,.) satisfies Assumption 1.3. Let Riemannian otstrongly convex sel (Definition 2.2). Then, the set is a geodesic m/LM) strongly convex set (Definition 2)
By the same arguments presented in Proposition 2.6, the Riemannian strong convexity implies the geodesic strong convexity of sets in Hadamad manifolds. This situation bears resemblance to the various notions of geodesically convex sets for Hadtaa-d manifolds (Boumal, 2020). should be noted that geodesic and double geodesic strong convexity (Definitions 2.1 and 2.3) become equivalent under mild assumptions, which is noteworthy as Definition 2.1 relies on the geodesic metric space structure of M, while Definition 2.3 leverages the manifold structure of M.
Proposition 2.7 (Equivalence between Geodesic and Double Geodesic Strong Convexity). Let M be a Riemannian manifold, and C C M satisfies Assumption 1.2 and d(.,,) satisfies Assumption 1.3. If C is a geodesic a-strongly convex set, then it is double geodesic L _ -strongly convex set. If the set C. is double geodesic a-strongly convex set, then it is geodesic (aa-stooggy convex
5

---

Examples of Riemannian Strongly Convex Sets As shown in Eq. (7), Riemannian strongly vex sets are the most restrictive case. For such sets C, the logarithmic image Txpp"(Cr is Fuclidean strongly convex. Intuitively, this occurs when the logarithmic map Exp, only slightly distorts C, which happens if the manifold M has bounded sectional curvature and C is not too large. In particular, on manifolds with bounded curvature, Theorem D.4 in Appendix D shows that balls with radius below a curvature-dependen bound are Riemannian strongly convex. This theorem applies to most practical cases, such as (but not limited to) spheres, hyperbolic spaces, Grassmann and Stiefel manifolds, the special orthogonal group, and the cone of symmetric positive definite matrices.
Examples of Geodesic Strongly Convex and Double Geodesic Strongly Convex Sets As shown Theorem 4.2 (see Section 4), level sets of smooth, strongly convex functions on Riemannian manifolds are strongly convex. This extends the Euclidean result of Journée et al. (2010, Thm 12).
3 DOUBLE GEODESIC STRONG CONVEXITY AND APPROXIMATE RSI
Since there is no apparent link between (double) geodesic strong convexity (Definition 2.2, 2.3) and the RSI, this section explore the link between those. We introduce the notion of approximate RSI (Definition 3.2) and demonstrate that the quality of the approximation depends the exponen- tial map operator (Definition 3.1). Those results will be useful to prove that the Riemannian FW algorithm (Algorithm admits global linear convergence rate under certain conditions.
3.1 DOUBLE GEODESIC STRONG CONVEXITY AND DOUBLE EXPONENTIAL MAP
We first introduce the double exponential map (Gavrilov, 2007; Dzhepko and Nikonorov, 2008; Nikonorov, 2013) and rewrite the double geodesic strong convexity with two geodesic paths.
Definition 3.1 (Double Exponential Map). Let M be a complete, connected Riemannian manifold. E M, Exp,(-) T&M -> MM be the exponential map
Let T&M be the tangent space to M at x. and T T.M- + T,,M be the transportation map between Tr. and M. We define the double exponential map E M as the function Expx(u, v): .T.M T,M - M, such that
Expx, v) = ExPExp, (u) (EEx,(())))
(double exponential map)
We also define hz(:,-) TTMxxxXX X + T&M as the (unique) exponential map operator, such that Exp, (ha v)) == Exp, (u, v), Vu, E T.M.
(Exponential Map Operator)
In particular, we can rewrite the double geodesic strong convexity of a set with the double exponen- tial map. Informally, Definition 2.3 takes into consideration the geodesic y between z and y and other geodesics departing from a 7()) that moves in every z direction, thus describing a closed ball the tangent space M. Therefore, (6) in Definition 2.3 becomes
Expx (7((), al(1 ()d((z))))) v))) E C,, for all B(0, C T.M.
(8)
This expression motivates the use of the term double to describe the notion of strong convexity.
3.2 APPROXIMATE RST AND ITS LINK WITH DOUBLE GEODESIC STRONG CONVEXITY
We now link the double geodesic strong convexity (Definition 2.3) with an approximate ver- sion of the scaling inequality (see Definition 3.2). When the exponential map operator satisfies h(u, v) = u + (basically, when the set is Euclidean), the double geodesic set strong convexity implies the RSI (Proposition B. Instead, in (Dzhepko and Nikonorov, 2008; Nikonorov, 2013), explicit approximations of the exponential map operator were proposed when the Riemannian man- ifold is symmetric has constant curvature, e.g., the Euclidean sphere Lobachevsky spaces (Dzhepko and Nikonorov, 2008). These approximations provide expansions of b (u, v) of the form
(u, v) = u + + (,, v),
where the term Re v) gives the quality of the approximation of hes (u, v) by u + v. The general expression of Rz (u, v) as series is given in (Gavrilov, 2007). Dzhepko and Nikonorov (2008) provide the explicit Taylor series for the Euclidean sphere (Dzhepko and Nikonorov, 2008, (6)) and Lobachevskii spaces (Dzhepko and Nikonorov, 2008, Section 3).

---

Definition 3.2 (Approximate RSI). Let M be Riemannian manifold, and C C M be a geodesi- cally c-strongly convex set (Definition 2.1). We then say that C satisfies the approximate RSI w.r. the distance -) and the residual r(-) : C - TM if. for all x E C. w T,M, and E argmaxxee (w; Exxp=(=))
(w:; Exp, (v)) alI x)) + (w;r()))
(Approx. RSI)
Proposition 3.3 demonstrates that the double geodesic strong convexity implies an approximate RSL. Proposition 3.3 (Double Geodesic Str. Cvx. implies Approximate RSI). Let M be a Riemannian manifold, and C C .M be a double geodesically a-strongly convex (Definition 2.3). We define Rg TTM x T.M > TaM, such that, for all x E C, the exponential map operator (Definition 3. is decomposed as
le v) u + v + Rg (u, v), V(u, v) E TaM, x ECC.
(10)
Then, the approximate RSI (Definition 3.2) is satisfied w.n.t. d(:;.) with the residual r(.) s.t. for all E C and w E T,M,
r(z) = Rv 1 22, (0), r (1/2) ( (Z)(e)))))) (T (12) w; .1....11123)
(Residual)
where v E argmax (w: Exp_" (x)))()))> x and 2" IIggaa/lells.
The approximate scaling inequality is meaningful in the regime where and situation, the scale of the residual r(-) is determined by (0) and dz, v). In some setting, the residual is such that the approximate term (w:; r(z))= in Definition 3.2 becomes negligible w.rt. the original term a:I [/] u)2. It should be noted that, in the analysis of the FW algorithm in Section 5, we select w == -V (x+), where Ia are the FW iterates.
close. In this
SUBLEVEL SETS OF GEODESICALLY STRONGLY CONVEX FUNCTIONS
Proving that a set is strongly convex might be difficult in practice. Hence, present the Rieman- nian counterpart of Eq. (3) for sublevel sets of geodesically smooth and strongly convex functions (Definition C.) These findings extend to the notion of geodesically convex functions (Rapesák, 2013) and (Boumal, 2020, Proposition 1 11.8). This result relies heavily on the following lemma.
Lemma 4.1 (Smoothness property). Let f be a geodesically L-smooth function (Definitions C.18 and C.19) defined on the geodesically closed subset C C M,, where M is an Hadaaadd manifold. We denote x² E argminnec f(x). Then,
[Vf(()]le S (2L(f(z) -(=f=))))=x)))
(11)
This result is based on the concept of functional duality in Riemannian manifold, which has been comprehensively studied in (Bergmann et al., 2021). The proof is deferred in Appendix B.2.
Theorem 4.2 (Geodesic Strong Convexity of Sublevel Sets), Let M be Riemannian manifold, and C C M satisfies Assumption 1.2. Let f : S M + R a proper, geodesically I.-smooth, and u-strongly convex function on C w.r.f. the distance function d satisfying Assumption 1.3. Let x" E C satisfying fz(=") = O. Let Q2 := {a f(x)- - f S $} C C be geodesically strictly convex for some s > 0, that is, every geodesic segment in Qs is in the interior of Q. except possibly for its endpoints. Then, Q2 is a geodesically strongly convex set with a = (22( max (fxi: 13)1/2.
Example: Unit sphere. Let consider S--1, the unit sphere manifold embedded in RR, with the distance function d(x; y) = arccos( (x;; v)). Let us fix Tp E M, and let ((x = de (x0, x). Let the set Q. {x: fxx) s). When s << (5)² the squared distance function is geodesically smooth and strongly convex function (the constants of which depend on s) (Lee, 2018, Lem. 12.15), (Sakai, 1996, p5153-154). As Q2 is also strictly convex set for < (T/2)²² the set Q. is geodesically strongly convex set, as shown in Theorem 4.2.
Example: Symmetric Positive Definite Matrices. The manifold M of positive definite matrices with the distance function d dx(XX,) (E, log" A((XX-Y)) is Cadaaa- manifold (Hosseini and Sra. 2015). Let us fix Xo M, and let f(X) = df (Xo, X). As M is a Cartan- Hadamard manifold, its distance function is strongly convex, and is also smooth in bounded sets. Therefore, the sets Q. (for& < f(0) are geodesically strongly convex, as shown in Theorem 4.2.
7

---

5 FRANK- WOLFE ON GEODESICALLY STRONGLY CONVEX SETS
The FW algorithm is a first-order method that solves constrained optimization problems in Banach spaces. Each iteration relies on a linear minimization step over the constraint region. It has recently been extended for constrained optimization over Riemannian manifolds. The Riemannian Frank-
Wolfe (RFW) algorithm (Weber and Sra, 2023; 2019) minimizes smooth convex functions / over compact and geodesically convex constrained sets C C M, i.e., it solves minimize fx), for x x C.
(OPT)
Algorithm Riemannian Frank-Wolfe (RFW) algorithm
Require: 2o E C C M; assume access to the geodesic map 7 [0, + M
for t 0, ...... do
1. Ut <- argmin (xx); Exps, (u))a
2. 8t < aergmin,eoo... <VV((x)) Exp,. (vt))
82 d (x),
3. 1 f (s:), where (0) 24 and 711 = U2.
end for
Remarkably, (Weber and Sra, 2023; 2019) proves similar convergence rates of RFW as the FW algorithm with comparable assumptions on the optimization problem as in the Hilbertian setting. For instance, when the function is geodesically convex and smooth and the set is compact convex, the RFW algorithm converges in O(1 (T) (Weber and Sra, 2023, Theorem 3.4.). Similarly, Weber and Sra (2023, Theorem 3.5.) show linear convergence of Algorithm when using short-step sizes, and the objective function is geodesically strongly convex and the optimum in the interior of the set.
In the Hilbertian setting, the FW algorithm admits various accelerated convergence regimes when the set is strongly convex. When the unconstrained optimum of f is outside the constraint set, the FW algorithm converges linearly (Demyanov and Rubinov, 1970). When the function strongly convex, the convergence rate reads O(1/T²) without assumption on the unconstrained optimum location (Garber and Hazan, 2015). The previous sections establish possible notions of strong convexity for sets in Riemannian manifolds. We now demonstrate that analog convergence regimes for the RFW algorithm on geodesically convex sets hold as in the case of the Hilbertian setting. These results complete the work of (Weber and Sra, 2023; 2019).
5.1 LINEAR CONVERGENCE OF RFW UNDER RSI
The scaling inequality (Proposition 1.1. is a convenient characterization of the strong convexity of the set (in Hilbertian setting) for establishing convergence rates (Kerdreux et al., 2021b). We follow the same path and establish the convergence rate of the RFW algorithm when the constraint set satisfies (approximate) Riemannian scaling inequalities. In Theorem 5.1, we prove the linear convergence of the RFW algorithm when the set C satisfies RSI and the unconstrained optimum of f is outside C. This generalizes (Demyanov and Rubinov, 1970) in a Riemannian setting.
Theorem 5.1 (Linearly Convergent RFW with RSI). Consider a geodesically corvex set C and a geodesically convex function ff that is L-smooth in C. Assume that any unconstrained optimum of lies outside the constraint set C, and in particular, there exists e >> 0 s.f. argmingec [[V(()) > c. Assume that, for all C, the (RST) holds. Then Algorithm I converges linearly:
S (f(x.) ffx="
f(x))) max(1/2, (c/(2
5.2 LOCAL LINEAR CONVERGENCE OF RFW UNDER THE APPROXIMATE RSI
Since the "exact" RSI could be too restrictive for some applications, this section provides similar convergence result when the feasible sets satisfy only approximately the RSI (Definition 3.2).
Theorem 5.2 (Linearly Convergent RFW on Double geodesically strongly convex Sets). Let M be Riemannian manifold. and C C M be a-double geodesically strong convex (Definition 2.3) set w.r.t. the distance d(.,.) satisfying Assumption 1.3. Assume that the function f + R is a geodesically convex T--smooth function, and there exists > 0 s.f. mingec [V]())] a > Assume
8

---

that there exists some constant C 0 s.t. the residual (10) of R.(:s-) satisfies
[| w))l S C max {1lu][ wella: [ Vo E EC, Vu, w E T.M.
(12)
Assume that 36 > 0: d(z,, v1)² = (ac) where C == C max { Indem se a
Then,
ac f f(x) = (f(zz) - f(x))) max 2 21. J.
The previous theorem thus states that, provided burn-in phase (that follows from the general O(//T) of the RFW algorithm) to ensure d(z,, v²)² S (ac) (28))(2 the iterates of the RFW algorithm converge linearly when the set satisfies the approximate RSI.
Discussion on the residual bound When the feasible set is Riemannian strongly convex (see examples in Appendix D), Eq. (12) is automatically satisfied, so that both the exact and approximate RSI hold. Morcover, the approximate RSI can be satisfied in settings where the exact RSI fails. For instance, Dzhepko and Nikonorov (2008) analyze the double exponential map on spaces of constant curvature, such as spheres and hyperbolic manifolds, and show that the residual admits an expansion of the form of Eq. (12). importantly, this constant does not need to be known in practice, since the RFW algorithm automatically switches to linear convergence once the condition satisfied.
Example I: Riemannian trust-region subproblem. When minimizing a function / on a Rieman- nian manifold, a common approach is the trust-region method. After iterations, it approximates ft f, where f. is usually a second-order approximation of f around Tt. Common trust region approaches minimize fa + A). where belongs to the tangent space of x; under the constraint that ||ه|| < 6y; we then use retraction on 2, + A to obtain the iterate 14+1. Alternatively, it is possible to solve the subproblem directly on the manifold:
T++1 = argmin fe(xr), subject to a EM,, d(a,, x) S o,
Using Theorem 4.2, we determine that the set is geodesically strongly convex. Therefore, if the set sufficiently small, the RFW algorithm converges linearly on this subproblem.
Example 2: Global Riemannian optimization through local subproblem solving For mani-
folds of curvature bounded in [Kminn kmax)) and defining K def max [|Kmin| Krmaxx ). Martínez-Rubio (2020) presented a reduction from global Riemannian g-convex optimization to optimization in Rie- mannian balls of radius O (()R)) ). It is required solve O(CR) of such ball optimization problems to an accuracy proportional to the final global accuracy (up to low polynomial factor). Here, A is the
initial distance to an optimizer, and ÇR is natural geometric constant. If we solve the subproblems using linear rates, the reduction only adds Ö(SR) factor to these linear rates.
5.3 NUMERICAL EXPERIMENT: MINIMIZATION OVER SPHERE
Numerical convergence of the RFW algo- rithm's 's iterates (Algo. 1) for minimizing a quadratic function over double geodesically strongly convex set in a unit sphere. The dimension of the problem is n = 500, xe is a vector of ones, and the func- tion f is random quadratic function parametrized as (x) A ||A(x - x²)]l²/2, where A is a random 250 x 500 matrix, and x" is generated at random such that dist(x", (ie) S. 4/2. The parameter R is set such that R = 0.9 dist(z" zx.), which ensures that the lution lies the boundary, and therefore, there exists > s.t. argmin VI f=)))]] > c. As predicted by Theorem 5.2, the rate is locally linear.
Figure 2:
Couvstaace NFW Thel Pap
7
RFW Duality Gep
10
104
1
78
50
100
150
#Cradiinn Oracle Calls
This section presents a numerical experiment illustrating the rates stated in Theorem 5.2. Let the manifold M be g--1 the unit sphere embedded in R Consider the problem min (x:)
subject
gn-1, dist xc) R R<5
(13)
9

---

Owing to the symmetries of the sphere, the linear minimization oracle for (13) can be formulated as a simple dieedemnnsionll problem (see Appendix E and Proposition E.2). The experimental setting and results have been reported in Fig. wherein the two regimes (global rate of O(t=!) and locally linearly convergent) are clearly distinguishable. This problem appears, for instance, when training a neural network with spherical constraints over hierarchical dataset.
Example 5.3 (Hierarchical NN with sphere constraints). Scieur and Kim (2021) trained neural network on a hierarchical dataset: "the classifier of each class belongs to a sphere whose center is the classifier of its super-class". The problem be formulated as in (13), where Ie is the separating hyperplane of the super-class, and f is the loss over the dataset.
5.4 EXAMPLE: FINITE-TEMPERATURE FREE ENERGY MINIMIZATION
We consider a minimization problem over a geodesic ball the SPD manifold:
min XES
f(X)
d(X,Xo) r.
(See Appendix F.) The following experiment illustrates how the theoretical rates manifest prac- tice. For a temperature T > 0, we seek
X E arg min F(X) = (x) 0-X3I
S(X) = -r( log X (T log(T - X)),
where E, is the electronic energy with chemical potential js enforcing Tr X No. Here X is the feiie-temperature density matrix. In standard electronic-structure computations, this problem is typically approached using the relaxed fixed-point iteration
Xk+1 (1 Xx au ((VE(Xx)),
where is chosen by a heuristic line search and the map & is computed from the eigen- decomposition (E(Xx) UAUT:
(UAAUT)= U diag(( + (/ -TU
Thus & applies the Fermi-Dirae function to the eigenvalues of the Hamiltonian, and the iteration amounts to minimizing a first-order (linearized) model of at Xg. A more controlled alternative is to linearize only the energy around reference point Xo, while keeping the entropy term exact. Let V (Xx))) denote the gradient at Xo- We consider the problem
min (V)(X)), X Xo)x TS(X) XEX
S.I.
d(X Sr.
with .) the chosen Riemannian distance and 0 trust-region radius. This trust-region subproblem provides a stable local model for updating Xo while explicitly controlling the geometric displacement measured by d.
CONCLUSION
We presented the first definitions for strong convexity of sets in Riemannian manifolds, studied their relationships, and provided examples of these sets. The global linear convergence the RFW algorithm serves tangible demonstration of the impact of developing theory around the strong convexity structure of these sets.
We expect strongly convex structure be helpful when developing Riemannian algorithms in the contexts where the Euclidean algorithm counterpart was leveraging such a structure, e.g., in the generalized power method (Journée et al., 2010), online learning (Huang al., 2017; Dekel al., 2017; Bhaskara et al., 2020a:b). and even more broadly, in the case of the use of strongification techniques, as (Molinaro, 2020).
10

---

ACKNOWLEDGMENTS
Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 45M14ZZMM05M22ZZBB and the Deutsche Forschungseemeinscaaftt (DFG) through the DFG Cluster of Excellence MATH+ (EXC-2046/1 and EXC-2046/2, project id 390685689). David Rubioo was partially funded by grant 1622224-10448NA-1000 and La Caixa Junior Leader Fep 2025. AdA would like to acknowledge support from a Google focused award, as well as funding by the French government under management of Agence Nationale de la Recherche part of the "Investissements d' avvenii" program, reference (NR-19-33A-000) (PRAIRIE 31A Institute). We would like to thank Editage (www.editage.co. for English language editing.
REFERENCES
A. Ahidar-Coutrix, T. Le Gouic, and Q. Paris. Convergence rates for empirical barycenters in metric spaces: curvature, convexity and extendable geodesics. Probability theory and related fields, 177(1):323 368, 2020.
A. Aleksandrov. Ruled surfaces in metric spaces. Vestnik Leningrad. Univ., 1957.
Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira, and A. Wigderson. Operator scaling via geodesically convex opti- mization, invariant theory and polynomial identity testing. In Proceedings of the 50th Annual ACM SIGACT Symposiun on Theory of Computing, pages 172- 181, 2018.
W. Ambrose. Parallel translation of riemannian curvature. Annals of Mathematics, 1956.
M. Bacák. Convex analysis and optimization Hadamard spaces. de Gruyter, 2014.
M. Bacak. Old and new challenges in hadamard spaces. arXiv preprint arXiv: 1807.01355 2018.
R. Bergmann, R. Herzog, S. Louzeiro, D. Tenbrinck, and J. Vidal-Núñez. Fenchel duality theory and a primal-dual algorithm on riemannian manifolds. Foundations of Computational Mathematics, pages 1-40, 2021.
Bhaskara, A. Cutkosky, R. Kumar, M. Purohit. Online learning with imperfect hints, In International Conference on Machine Learning, pages 822-831. PMLR, 2020a.
A. Bhaskara, A. Cutkosky, R. Kumar, and M. Purohit. Online linear optimization with many hints. arXiv:001000008, 2020b.
N. Boumal. An introduction to optimization on smooth manifolds. Available online, Aug. 2020.
N. Boumal, Mishra, P.-A. Absil, and Sepulchre. Manopt, a matlab toolbox for optimization on manifolds. The Journal of Machine Learning Research, 15(1), 2014.
G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokhtari, and S. Pokulta. Conditional gradient methods. arXiv preprint arXiv:2211.
2022.
M. R. Bridson and A. Haefliger. Metrie spaces of non-positive curvature, volume 319. Springer Science & Business Media, 2013.
Bubeck, M. Cohen, and Y. Li. Sparsity, variance and curvature in multi-armed bandits. In Proceedings of Algorithmic Learning Theory, pages 111-127. PMLR, 2018.
Burago, I. D. Burago, Y. Burago, S. Ivanov, S. V. Ivanov, A. Ivanov. A course metric geometry. volume 33, American Mathematical Soc., 2001.
Y. Burago, M. Gromov, and G. Perel' man. Ad alexandrov spaces with curvature bounded below. Russian mathematical surveys, 47(2):1-58 1992.
C. Crisciticllo and N. Boumal. Negative curvature obstructs accelratiin for geodesically convex optimization, with exact first-order oracles. CoRR, abs/2111. 2021. URL
org/
2111. 1326.1.
M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
D. Davis, Drusvyatskiy, and Shi. Stochastic optimization over proximally smooth sets. SIAM Journal on Optimization, 35(1):157-179, Jan 2025. doi: 10.1137/20m13220 1320225.
O. Dekel, Flajolet, N. Haghtalab, and Jaillet. Online learning with hint. In Advances Neural Informa- tion Processing Systems, pages 5299-5308, 2017.
V. F. Demyanow and A. M. Rubinov. Approximate methods in optimization problems. Modern Analytic and Computational Methods Science and Mathematics, 1970.

---

V. Dzhepko and Y. G. Nikonorov. The double exponential map spaces of constant curvature. Siberian Advances Mathematics, 18(1):21-29 29, 2008
Y. Fei, Y. Liu, C. Jia, Z. Li, X. Wei, and M. Chen. A survey of geometric optimization for deep learning: from euclidean space riemannian manifold. ACM Computing Surveys, 57(5):1-37 2025. 2025.
J. Feydy, T. Séjourné, F.-X. Vialard, S.-i. Amari, A. Trouve, and G. Peyré, Interpolating between optimal trans- port and mmd using Sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2681-2690, 2019.
Z. Gao, Y. Wu, X. Fan, M. Harandi, and Y. Jia. Learning to optimize on riemannian manifolds. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 45(5):5935 59,55995, 2022.
D. Garher and F. Hazan. Faster for the frank-wolfe method strongly-convex sets. In International Conference on Machine Learning, pages 541-549. PMIR, 2015.
A. V. Gavrilov. The double exponential map and covariant derivation. Siberian Mathematical Journal, 48(1): 56-61, 2007.
V. Goncharov and G. Ivanov. Strong and weak convexity of closed sets in Hilbert space. Springer, 2017.
T. I.. Gouic, Paris, P. Rigollet, and A. J. Stromme. Fast convergence of empirical harycenters in alexandrov spaces and the wasserstein space. arXiv preprint arXiv: 1900. 1908,00828, 2019.
H. Hopf and W. Rinow. Über den begriff der vollständigen differentialgeometticheen fläche. Commentarii Mathematici Helvetici, 3(1):209-225) 225, 1931.
R. Hosseini and S. Sra. Matrix manifold optimization for Gaussian mixtures. In Advances in Neural Informa- tion Processing Systems 28: Annual Conference Neural Information Processing Systems 2015, Decem- ber 7-12, 2015, Montreal, Quebec, Canada, pages 910-918, 2015. URL http:/ /wwppaaapaasee.ee/eeeeeeeeeeeee. www.pr..npss...................p www...ipp........ paper/ / 581 2-mmarrr:- x-mani Fold-opp opt.ppp.ii i zat on- fornnnoor-guusee an-mi xtures.
R. Hosseini and S. Sra. An altermative to EM for gaussian mixture models: Batch and stochastic Riemannian optimization. CoRR, abs/1776.003261 2017. URL http::::/aaxii..rrggg abs /at.s///7.....
03266.3267..
R. Hosseini and S. Sra. Recent advances in stochastic Riemannian optimization. Handbook of Variational Methods for Nonlinear Geometric Data, pages 527-554, 2020.
R. Huang, Lattimore, György, and C. Szepesvári. Following the leader and fast. rates online linear prediction: Curved constraint sets and other regularities. The Journal of Machine Learning Research, 18(1): 5325-5355, 2017.
Jost. Nonpositive curvature: geometric and analytic aspects. Birkhäuser, 2012.
M. Journée, Y. Nesterov, P. Richtárik, and R. Sepulchre. Generalized power method for sparse principal com- ponent analysis. Journal of Machine Learning Research, 11(2), 2010.
L. Katsman, E. Chen, S. Holalkere, A. Asch, A. Lou, S. N. Lim, and C. M. De Sa. Riemannian residual neural networks. Advances in Neural Information Processing Systems, 36:63502-63377 2023.
Kerdreux, Aspremont, and Pokutta. Local and global uniform convexity conditions. arXiv preprint arXiv:2102.0m 100.:20020051444 05134, 2021a. T. Kerdreux, A. d' Aspremont, and S. Pokutta. Projection-free optimization uniformly convex sets. In International Conference on Artificial Intelligence and Statistics, pages 19-27. PMLR, 2021b.
T. Kerdreux, L. Liu, S. Lacoste-Julien, and D. Scieur. Affine invariant analysis of Frank-Wolf strongly sets. In International Conference Machine Learning, pages 5398-5408. PMLR, 2021c
Kerdreux, C. Roux, A. d' d'Aspremont, and S. Pokutta. Linear bandits on uniformly convex sets. Journal of Machine Learning Research, 22((84):1-22 23, 2021d.
Lee. Introduction Riemannian manifolds. Springer, 2018.
M. Lezcano-Casado. Curvature- global convergence rates for optimization on manifolds of bounded geometry. arXiv preprint urXiv:2008.0225 2020.
D. Martínez Rubio. Global Riemannian accelcration in hyperbolic and spherical spaces. arXiv preprint bbg/ab///
arXiv:2012.03618, 2020. URL https: : / /arxiv..... org/ abs 021.2.2222111.......
D. Martínez- Rubio and Pokutta. Accelerated Riemannian optimization: Handling constraints with a prox to bound geometric penalties. arXiv preprint arXiv:2211.14642 2022. URL https: //ap:i//avivvv///a org/ abs/ 22 1. 645.
Q. Mérigot, A. Delalande, and F. Chazal. Quantitative stability of optimal transport maps and lincarization of the 2-wasserstein space. In International Conference on Artificial Intelligence and Statistics, pages 3186- 3196. PMLR, 2020.
W. Meyer. Toponogov's theorem and applications. Lecture Notes, Trieste 1989.
12

---

M. Molinaro. Curvature of feasible in offline and online optimization. arXiv:2002.05213, 2020.
Y. G. Nikonorov. Double exponential map on symmetric spaces. Siberian Advances in Mathematics, 23(3):
210-218 218, 2013.
Q. Paris. The exponentially weighted average forecaster in geodesic spaces non-positive curvature. arXiv:2002.00852. 2020.
Q. Paris. Online learning with exponential weights in metric spaces. 1rX1:22003.1388. 2021.
Petersen. Riemannian geometry, volume 171. Springer, 2006.
G. Pisier. Martingales with values in uniformly convex spaces. Israel Journal Mathematics, 20(3-4):326-
350, 1975.
G. Pisier. Martingales in Banach spaces (in connection with type and colype). course IHIP, Feb. 2-8, 2011.
Rapesák, Smooth nonlinear optimization Springer Science Business Media, 2013.
T. Sakai. On riemannian manifolds admitting function whose gradient is of constant norm. Kodai Mathemat- ical Journal, 19(1):9-51, 1996.
D. Scieur and Y. Kim. Connecting sphere manifolds hierarchically for regularization. International Confer- ence on Machine Learning, pages 9399-9409. PMLR, 2021.
Sun, Q. Qu, and Wright. Complete dictionary recovery over sphere I:: recovery by Riemannian trust- region method. IEEE Trans. Inf. Theory, 63(2) 914, 2017. doi: 00.1009911.2001.22221144 URL https:/ / /tc///ccii/// wrg/ /00 1109/111111 /TIT. 201 2632149.
Vial. Strong and weak convexity of sets and functions. Math. Oper. Res., 8(2):331225, 1983. doi: 10.1287/ MOOR.8.2.231. URL https:
/12///norr..////// w.toor...2233. 2.23....
J.PP. Vial. Strong convexity of and functions. Journal Mathematical Economics, 911-2)187-205,, 1982. doi: https://doi.or// 000116000000444400000000222322
C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
Wang, X.J. Wu, Z. Chen, T. Xu, and J. Kittlr. Dreamnet: deep riemannian manifold network for spd matrix learning. In Proceedings of the Asian conference on computer vision, pages 3241-3257, 2022a.
W. Wang, M. Saveriano, and F. J. Abu-Dakka. Learning deep robotic skills riemannian manifolds. IEEE Access, 10:114143-1 114152, 2022b.
M. Weber and S. Sra. Projection-Fie feeee nonconvex stochastic optimization on riemannian manifolds. arXiv preprint arXiv:1910.04194 2019.
M. Weber and Sra. Riemannian optimization via frolk-wolfe methods. Mathematical Progrumming, 199(1): 525-556, 2023.
H. Zhang
Sra. First-order methods geodesically convex optimization, Conference on Learning Theory, pages 1617-1638. PMLR, 2016.
H. Zhang and S. Sra. An estimate sequence for geodesically convex optimization. In Conference On Learning Theory, pages 1703-1723. PMIR, 2018.
13

---

CONTENTS
Introduction
Strongly Convex Sets in Riemannian Manifolds
Double Geodesie Strong Convexity Approximate RSI
3.1 Double Geodesic Strong Convexity and Double Exponential Map
3.2 Approximate RSI and its Link with Double Geodesic Strong Convexity
4 Sublevel Sets of Geodesically Strongly Convex Functions
7
5
Frank-Wolfe Geodesically Strongly Convex Sets
5.1 Linear convergence of RFW under RSI
Local Linear convergence
under approximate
5.3 Numerical Experiment: Minimization Over a Sphere
5.4 Example: Fimiea-temperature free energy minimization
10
A Missing Proofs
15
B Technical Proposition and Lemmas
20
B.1 Double Geodesic Strong Convexity implies RSI
20
B.2 Proof of Smoothness Property Lemma
Preliminaries and Notations
22
C.I Geodesic Metric Spaces
22
C.2 Riemannian Manifolds
22
C,3 Sets in Riemannian Manifolds
23
C.4 Functions Manifolds
23
Examples of Riemannian Strongly Convex Sets: Balls with Restricted Radius
25
D.1 Bounded curvature.
25
D.2 Strong Convexity and Smoothness of Distance Functions
25
D.3 Smoothness and Strong Convexity of Euclidean Pulled-Bar Function
25
D.4 Main result...
26
E Example of Simple Linear Minimization Oracle
27
RFW and Linear Minimization Oracle on the SDP manifold
28
The SDP manifold affine-invariant geometry
28
F2 A OieeDimensiooal Reduction for the LMO in an SPD Ball
30
E3 Algorithm for the IMO
32
E4 Numerical Experiment: Minimization Over an SPD Ball
34
G MATLAB code for the experiments
35
G.1 Suhroutine: Linear Max Oracle For Ball In Sphere
35
14

---

G.2 Sample Script: Random Quadratic Over Sphere With Ball Constraint
36
A MISSING PROOFS
Proof of Proposition 2.5
Proof. As the set is strongly convex in the Euclidean sense, obtain from (scaling ineq.) that, for all x E C and for all w E M, we have
(w: u) 2 all a||w||z||u xl12:
argmax (w; 2)
sEEx '(C)
As the exponential map is bijective over the set C.
argmax (wr z). Expx* =EExp=' (C)
argmax Exp, (x))a( =EC
Therefore, using e = Exp,, (u) gives us
(w;; Exp, (x)) 2 al| Exp, (x))l v E argmax(w:; Expa (z))
SEC
Proof of Proposition 2.6
Proof. First, we introduce the important notion of geodesic triangle. For the three points p. g, M, the set Aper the three minimizing geodesics joining these three points a geodesic triangle. A comparison triangle Aper is then triangle with the same side length as Apgr in metric space with a constant sectional curvature. Comparison theorems are then used to compare the angle between these triangles according to lower (Toponogoo''s theorem) or an upper bound (Rauch's theorem) on the sectional curvature of the geodesic metric space M.. We refer to (Burago et al., 1992: Meyer, 1989; Burago et al., 2001) for detailed treatment of such comparison theorems and to (Zhang and Sra, 2016; 2018) for their use in optimization contexts. It should be noted that comparison theorems do not only compare triangles, but also hinges, and result angle or length comparisons (Meyer, 1989, Theorem 2.2. B).
As the set C is a Riemannian strongly convex set (Definition 2.2), by using the definition of the strong convexity of sets in Hilbert spaces (1), we obtain
VI E M,, Vp, q E Exp= (C). Vt E [0, 1]. = T.M:: =|= (lp + (1 1)g)ll al(1 O)P alI then E Exp=
(14)
for some parameter a > We now consider arbitrary points x, y E M and & E M.t. (()
af(1-t)d 1t)dd (z, v). where (t): [0, + M is the geodesic between z and and ā det al alM > 0.
Due to Assumption 1.3 we have
fMll Exp_ (1) (3)ll S at - t)ll Ex)="(())
(15)
Now, (Martínez- Rubio and Pokutta, 2022, Corollary 24) using the Riemannian cosine law inequality for Bartan-Hadamar manifold in the geodesic triangle with vertices 2 and yt),, and the corresponding triangle in M via Exp,- (.), have
2(Ex, (z), Exp,, (y())) Exp_ (2) Exp. ( || Exp -1
7(1) (1) (3)112
2(Exp, (2), Exp. (t())) (x(t)()(tt)
Exp_ [3)] + Exp, Exp=" (>(1))112 Exp," ( (2)
Exp. (x())1
which implies
Exp_ 1 (8) - Exp_ (1(t)) < Exp (x)
(16)
Now, let Exp= (v). = Exp= (x) = 0, and = Exp- and note that Exp, ()())
t Expp- (v). Hence, combining (15) with (16) and using our new notation, we obtain
(mIl - (tp + - -))g)) - 0z - t)llp - -11l
and after using the value of = a and (14), we conclude that 2 = Exp,- (z) E Expx (C), and hence ह E C.
15

---

Proof of Proposition 2.7
Proof. (=) We start with C C M being a-geodesically strongly convex set. Now, let M such that
|| S t(1 t)d (a,
LM
As the distance function can be bounded as cl(x,)) v) S Tuull Exp= (y)ll, we have
||||| S LM t(1 (x,
d (xp(), at(1 (2,)),
As the set is geodesically strongly convex, we have (xp EC. (+) Now, we assume C. to be doubly exponentially strongly convex set with the parameter a. We construct the point z E M such that
d()(t), S (mat(1 t)d v).
As the distance function d can be bounded lmll Exp (z) - d()(tt, 2), have
Exp (()) (2) 3 at(1 txd As the is a-double exponentially strongly convex, we have 2 C.
d() & eyat(1 t)d (x. v)
Proof of Proposition 3.3
Proof. This proof is similar Proposition B.1 until (31). We then write
N2, (0) and (1/2) ( d (2
Hence, we have
wi Exp, (x)) 2 (w: Exp Exx,, (u w R(u, v) w))));
Using the same arguments as those in the proof of Proposition B.1, we obtain
a w: Exp_=ppp0-- (w)) 2 a d w]llw||z + (w: R( R(z (0), r (1/2) (z)
(o,))
Proof of Theorem 4.2
Proof. Let > O, and let consider (x, y) E Q and write y the geodesic between and y. On successively using the geodesic smoothness of f. Cauchy-SShwaare and Lemma 4.1, for smooth curves (f) (0) (t) and t, E [0, 1], we obtain
(a()))))) 4 - ff f (( + (1)((t)))())))
<f(((0) (V | Exp (0)))) (1)))) L $f6(0) - 5
( (d((),
((00)))))))))))))))
L
<(VFG(t) f F++ + L 1}
((t()))))))
(17)
16

---

Therefore, to ensure that (t) E Qss can identify sufficient condition on d(r((t) such that
(Vi(((t)- f* L 1)
d((((),(0)))
ss
2
=d(r((),ce(t)) v sufficient condition
L max M 1} (V8- (--((((())) r*)
2
(18)
As f is strongly convex, on using Definition C.18 and because (I,, v) E Q.. we obtain
S((()) 1- -11 dP (x,
Since v- is concave function, have -
1/ S vx
y Therefore,
2/2
udl
(x.y)
(1 - t)tpdd (
Vf(((t)- s Vs- (1 t)t
V
2
4/8
Hence, we have
L max Mi 1} (Vo- VIG(1)
2
1)l (2,
2/
(19)
L ( 1}
4/8
=(1 -tt
t)t
d
(I,1))
(20)
2
2 max 1}
Therefore,
c()()),(()) s (1 t)t
8 (I,
23L max 1} 2
2
d()(t),c(())) S V L {MM 13
((-vi(((tt) fr)
L m Ci/: 13
(18)
(Vi((t)- - f(a(t)) f S.
d()(t), S
2
Hence, ( is in the set Q., which is the definition of geodesic strong convexity.
Proof of Theorem 5.1
Proof. This proof is based on (Demyanov and Rubinov, 1970; Garber and Hazan, 2015; Kerdreux al., 2021b), but in in a Riemannian setting. Using the geodesic smoothness (Definition C.19) of at T++1 (s:), we obtain
L (or, ((1))) 1
f(x++1) S ((x)) v (xx); (x +
As y is a geodesic between x, and it, we have d(zr, (st)) sid(a, v)) and (r(ss)) 8, (vt). Hence, we now have
- 2
d vt). [(x+1) S (xx) 8e( (x()) Exp (vx)) +
According to the short-step rule for st (Algorithm 1), for all s E [0, 1]. we now have
L 3 d (z) v.).
f(1+11) S f(x)) - s( - Exp:.. +
2
17

---

After using the optimality of Ut. have <- (z;); Expx. (vi))= f (2:); Expa. (2*))as
where x² C is a solution to (OPT). Then, owing to the geodesic convexity f, we have
- - f(z) 2 (V)(z); Exp. ()))
Hence, is the case in the Hilbertian setting, the FW gap the primal gap at Te, i.e.,
V f Expa. (ve))= upper bounds
f(x)) fl)) (v:))2.
We write h = ((x)) f(x²). and hence have
L h441 h₂ 8/2) s/2( (z()) Exp (u+));
dd vz).
(21)
2
Now, with = argmin V ||= > 0, after using the (RSI) at ia and since - VV((z)) E T,,M, obtain
(<V)(z)); Exp. (v)))=
(x)) 2 (xcd(ae, vz)²
such that, for all [0, 1), have
h41 S
- (1 + T.S- are) ( dF vt).
(22)
Then, if accLL < 1, by choosing = ac/ in (22), we have h411 S h4 (al-aa/(2L)) else, we have ac < and on selecting s = 1, we simply have h4+1 h2/2. Hence,
het1 S h4 m1x(1/2 (or(22)))
Proof of Theorem 5.2
Proof. As in the proof of Theorem (5.1), (21) is satisfied, i.c.,
L + st (12, (x), vz).
h441 < h1,111111111 st/2) s./2(- (4t/2(-V/ (xx); Exp (w)),. (v)))
(23)
Now, from Proposition 3.3, C is double geodesically a-strongly convex, an approximate RSI satisfied (Definition 3.2) at x. with - f(()) Tr, M with the residual r(z:) as in (Residual), i.e.,
1 r(x)) = Rz. 1 (0), r
a
(24)
Tea (1/2)
Hence,
combining with argmin zec [V(()) {- (zz:); Expe, (1:)),, as follows:
lower-bound
(-V Exp,, (v))) (v:)), 2 acd(x1, (-V())()
On substituting this inequality in (23), for all [0, 1]. we have
h44 S h1 s/2) + Ls ac) d + ((()))
(25)
We use (12) to bouer-bound the term ||r( 1e Hence, we are first required to obtain an upper bound on Il (m) and || a of (I,, uz)=" ==" |1 We first note that
of (x,. ox)= I1 (1/2) (1/2)
of vz).
df
Furthermore, by definition of the exponential mapping, we have 11 (0) Exxp..((x))ll and according Assumption 1.3, we have
1 1. (0)l
d((s))))
em
18

---

When plugging these two bounds in the residual r(xz) (24), with the growth condition the residual (12), we have
a²
[r(x))l x |r(x)]l
max {
(66M 168M
(t); (x),)))))
(26)
M
a²
I vi) max {
d(zs, ve): 48 }.
a
(27)
166M
On using d(z,, v4) S and with Č= C max {a² (166 a (4e2))(4))))) we have ||(()))l2, S Cd (2,, v,). Hence, using the Cauchy-Schwart Schwartz inequality and V fz;))))ll)) ll I òL, (25) becomes
h+t1 S he(1 s/2) + Lss ac) df (x.. vt) + 2
5T, vz)
(28)
s he(1 s/2) + d Us) Ls ac - 5LCC (20, (x),
(29)
As we assumed d(z;, 0x)2 < (acc)/ (28T,C) we have -ac + SL 0x) S - < 0. Let us consider 8* := (ac - dLCdd(Ir, (xt, 0.) )))) > O. If 8" > 1. then the choice of s results in h4+1 S h2/2. Else, 8* E [0, 1]. and we select = st. We hence obtain h411 I h₂(1 - 8 /2) S
1 - (2L). Overall, obtain
het1 S h4 max ac/(2
19

---

B TECHNICAL PROPOSITION AND LEMMAS
B.1 DOUBLE GEODESIC STRONG CONVEXITY IMPLIES RSI
Proposition B.1 (Double Geodesic Str. Cvx. implies RSI). Let C C. M be double geodesic a-strongly convex set (Definition 2.3) in a complete connected Riemannian manifold M. Let us assume that the double exponential map operator (Definition 3.1) 1) is such that hg(u, (. u) = u + v, V(u,v) E T.M.M
(30)
The RSI in Definition 2.4 is then satisfied.
Proof. Let us consider a E C, w E T,M, and E s.t.
V E argmax (w;; Exp3 (x))..
#EC
Then, by (8), which is equivalent to Definition 2.3 with t = 1/2, we have Exp (1/2) (2, w)z) E C, where 7a,0(-) is the geodesic joining x, and v and = are unit norm wh,re
vector T (1/2) Then, by optimality of v. for all = E T (1/2) with ||=|| = 1, we have
w: Exp_ (x))))p(o))) 2 ( (w: Exp."' (Exp,,..(1/7)) ee
(z. 0)2)
Let us first recall that, by definition of the exponential map, for the geodesic Nr and for all E [0, 1]. have Exp,, (t> (0)) (t))(t) such that
write
wo Expx '
ww Exp=" (
(Expexp, (1,,,..00) (x,
(31)
We can hence write this in terms of the double exponential map and subsequently in terms of the exponential operator map. We use
ExpExp, (0)) (z)))))))) = Exp, ()),.:(): (122)) (2) (()))))))
Hence, on using the assumption (30) on the exponential operator, we have
Expexp, (0)) ( d (c. u)2) Exp, (2 + (1720011/21) p (2)(())))2))
When plugging the last equality in (31), we obtain
1 / w; Y,, ()) + (ur; (T2m.(1122) (2 2
w: Exp_" (w)
x
should be noted that (0) Exp, (v), such that
wi Exp, (w)) 2 2( wi 2 (11).0112))-1 (1)))))))))
With [ 21
I and the isometry property of
I (1/2) (1/2)
we have
w: I
(1/2)
a ( (()
(T (1/2) wi I ( a
(
(32)
(122 w;
a d (z. (2 w)2) (1/2)
(33)
4
Hence, for all of unit norm in T (1/2)M, we obtain
w: Expx (xxp=(())) (0))
2 2 (1 a (x,
(34)
2 dl v) (T (2
(35)
T2.012/2)
Furthermore, by maximizing over 2, for the best z", we obtain (1)...(//2)
p (1.2))
(a.0(1/2)
Then, because the parallel transport r r (1/2) is an isometry, we finally have
ww Exp_ (6)) 2 a df - 1/2
2 (d
2
20

---

B.2 PROOF OF SMOOTHNESS PROPERTY LEMMA
First, we introduce the Fenchel conjugate of a function defined on a manifold.
Definition B.2. (Bergmann et al., 2021) Let us Suppose that f f - IR where C C M is a strictly convex set, where M is Gartan-Hadamar manifold. For m M, the m-Fenchel conjugate of defined as the function fm. T + R such that
8m (Em)
sup wETmM
{(Ems x) - f (Expm x));
(36)
where M is the cotangent bundle TM
In particular, need the following property.
Lemma B.3. (Bergmann et al., 2021, lem. 3.7) Let us suppose that f.f - R are proper functions, where C C M is strictly convex and M is Cartan-Hadamie manifold, and let m VEC. C. Then,
if f S f()) vp ep then Im 2 (Em) Em T.M.
(37)
We now ready prove Lemma 4.1.
Lemma 4.1 (Smoothness property). Let f be a geodesically L-smooth function (Definitions C.18 and C.19) defined on the geodesically closed subset C C. M, where M is an Cartan- Hadamard manifold. We denote x² E argmin f(z). Then,
[f(())le & (
(11)
Proof. As is geodesically smooth function, for all p E C, we have f(p) S f(p), where
f(p) = f(x) + (V)()), Exp,- +
2 (x, Ap EC
Therefore, according to Lemma B.3, we have f (Em) 2 fm (Sm), for all m E M. Using the definition (36),
Fi (5m) sup ZETTM
(5m: Z)z f(Exp... (2))
the particular case wherein m I, we obtain
T, (t()x)= = sup (Ex, Z) f(x) (Vf()) Z)2 1 M
1
=-f(x) +
1 Vf(x)
2T.
Therefore, the inequality ff(Ex) 2 (Ex))) can be written as
1
27. E. V)()) S +
In particular, at &x = 0, we have the desired result,
(0) sup (0, Z) ((xxpx()) ZET..
sup ZET...M
(Z)) inf f(z) =
SEC
21

---

C PRELIMINARIES AND NOTATIONS
Our primary goal defining several notions of strong convexity for sets in metric spaces that are well-suited for analyzing and designing optimization algorithms. In this study, we first focus on the case of complete and connected n-dimensional Riemannian manifolds. We now recall some useful concepts.
C.I GEODESIC METRIC SPACES
Definition C.1 (Metric space), A metric space is a pair (M, dy). where M is a set, and dm : M x M IR+ is distance function (the metric), i.e., it satisfies positivity, symmetry, and the triangle inequality.
Definition C.2 (Geodesics). A geodesic 7(1) [0 + M between two points x, E iisa smooth curve such that 7(0) = I, 7(1)= = y, and (t) =
Definition C.3 (Geodesic metric space). A metric set is geodesic metric space if. for all x, y E M, there exists a geodesic that connects x and y. When this geodesic is unique, the set is considered
uniquely geodesic.
Definition C.4 (Non-positively curved spaces). If. for all geodesics 7 and for all elements M,, the metric dm satisfies (e.g.. (Paris, 2021, Covollary 2.5.))
dm(x, ((t)) S (1 t)d (0)) + tdm(x,,(1))² t(1 ((1=))dx(((0)))(1)))
(38)
then M is non-positively curved space.
This non-positive curvature indicates that the function f(.) d=)(=x)2 is geodesically strongly convex (see Definition 18) for all reference point x E M. In particular, are geodesic metric spaces generalizing Hilbert spaces which are well-suited for convex optimization purposes (Jost, 2012; Bridson and Haefliger, 2013; Bacák, 2014; Bacak, 2018).
spaces
Definition C.5 (Caataan-Hddmaan spaces), A Cartan-Hallmmrr space M (a.ka. CAT(O) space or space of non-posilive curvature) is geodesically metric space that is non-positively curved.
C.2 RIEMANNIAN MANIFOLDS
In this section, we assume that M is n-dimensional Riemannian manifold, for instance, the group of rotations SO(n); hyperbolic spaces; spheres; or the manifold of symmetric positive definite ma- trices.
Definition C.6 (Connected manifolds), A manifold M is connected if. for all x. y E M, there exists continuous path joining those points.
Definition C.7 (Tangent space). For a point x E M, a tangent vector is the tangent of a parame- terized curve passing through and all the tangent vectors at form the tangent space T T.M. Definition C.8 (Riemannian Metric (Metric Tensor)). Let M be Riemannian manifold. Rie- mannian metric on M is smooth (0,2)-tensor field
9 g:I- Q M + 9s E Bil(T,M X T,M,R)
such that for each point M, the bilinear form In satisfies symmetry, positive-definttnnss and smoothness. The metric tensor equips M with a notion of angle, length, and volume.
Definition C.9 (Inner Product at Point). Given a Riemannian manifold (M. g), the inner product a point a E M the bilinear form
(;)x=: 9z.
which is symmetric and positive-definite
Definition C.10 (Complete Manifold). A Riemannian manifold (M.g) is complete if for all x E M, the exponential map Exp,, defined the whole tangent space T.M.
Complete Riemannian manifold and Riemannian metric A connected Riemannian manifold is also a metric space. Furthermore, the length of a continuous piecewise smooth path ? [o, 1] - M is defined as L(>) : So (t)l We denote Pa.ay as the set of continuous piecewise smooth paths joining x and y. We have the Riemannian metric (x, y) = inf L(r) as a distance (Boumal, 2020, Theorem 10.2) and (M,dM) is metric space.
22

---

C.3 SETS IN RIEMANNIAN MANIFOLDS
Importance of sets when optimizing on Manifolds. When M is connected compact Rieman- nian manifold, and f geodesically convex function on M (Definition C.18), then f is constant (Boumal, 2020, Corollary 11.10). This result motivates the optimization of geodesically convex functions over subsets C of these manifolds.
Assumptions for Sets in Riemannian Manifolds In this paper. we will make the assumption that we are working on a subset C c M that is imiquely geodesically convex, defined as the set C. being both convex and uniquely geodesic.
Definition C.11 (Geodesic Convex Closed Subset of a Manifold). We say that closed subset C of a manifold M is convex if for any two points I, E C, there exists geodesic from I to that is distance minimizing and is contained C.
Definition C.12 (Uniquely Geodesic Subset of Manifold). We say that a subset C of a manifold M is uniquely geodesic for every two points x, y E C, there is only one geodesic between and that contained in C.
Assumption C.13. The set S M compact, convex, and uniquely geodesic.
For instance, open hemispheres and Cartan-Hadamard manifolds, that is, complete simply con- nected manifolds of non-positive sectional curvature everywhere, are uniquely geodesic. Hence, their compact counterparts are geodesically convex subsets. However, closed hemisphere is uniquely geodesic.
The exponential map parameterizes the manifold by mapping vectors in the tangent spaces M. For x E M,, it is in general local diffeomorphism: however, when M is complete (Hopf and defined on the whole tangent space as follows.
Rinow, 1931),
Definition C.14 (Exponential Map). Let M be Riemannian manifold. For all x -M and T,M, let the geodesic : [0.1] - M satisfying 7()) = with (0) t. The exponential map at X, Exp,: T.M + M, defined as Exp. = 71).
Remark (Bijective Exponential Map and Logarithmic Map in the Right Domain), For uniquely geodesically convex sets C and x E C, define the set
C₂ (u TTMM: t Exp,(tu), for E [0, 1], is minimizing and Exp,, (v) E C},
then, the exponential map from x restricted to this set is well defined and bijective in C, that is, Evp,(y) C2 C is bijective function. In this work will always refer the inverse of the exponential map, or logarithmic map, the inverse of this restriction: Exp."" :C - Cz. Note that generally in the literature the logarithmic map is not defined using this restriction.
The exponential map links the manifold and its tangent spaces, but vectors belonging to different tangent spaces not directly comparable. Using the Levi-Civita connection, we define parallel transport operator between two points x, E M in the manifold (Ambrose, 1956).
Definition C.15 (Parallel Transport Operator). For all x, y E M, the parallel transport map I'V. T.M- + TyM combines vectors from different tangent spaces by transporting them along geodesics and such that (T gg = (u;; v) for all (u, v) E T.M.
C.4 FUNCTIONS OVER MANIFOLDS
We first define the Riemannian gradient of f at x as the unique element f E T,M, such that the directional derivative Df (v; (z))) for all T.M.
We now recall the notion of relative geodesic (strong) convexity and smoothness for a function f: M R w.r.t. distance function d. M M R- (see, for instance, (Zhang and Sra, 2016)).
Definition C.16 (Distance function), A function d M x M + R- is called a distance function if satisfies positivity, symmetry, and the triangle inequality.
Remark The distance could differ from the distance function d associated with the manifold M.
23

---

Definition C.17 (Euclidean Smoothness and Strong Convexity). In the euclidean case, a function called Lmooohhh μi-ttrongly convex if the function is differentiable and satisfies, Vx, y E domf
5 1 f()) ( f(z) - Vf
x|12
In the case of geodesic space, this definition takes the following forms:
Definition C.18 (Geodesic (Strong) Convexity). Lei C be uniquely geodesic set. A function f C M + is geodesically j-strrongy convex (resp. convex if μ 0) w.rdt. if, for all 2,y E C, we have
E 10, f(r(t) S (1-t)f(z)) +tf(v) -t(1- v), H #20 O.
(39)
Definition C.19 (Geodesic Smoothness). Let C be a uniquely geodesic set. A function f S M + IR geodesically L-smooth in C w.r.t. d for all x. y we have
(f(x) - f(x) (V Exp (w))
- 4 2xp='(x)>
L20.
Note that when the function is also geodesic (strongly) convex, the smoothness condition can be simplified by removing the absolute value. Indeed, (strong) convexity implies that the argument of the absolute value is nonnegative.
Finally, we state the following assumption on the relation between the distance function used to define smoothness and strong convexity and the distance function associated with the manifold M. This assumption allows us to use distances whose value is within some constant factors from the Riemannian distance Exp, (y)ll, which corresponds to the definition below with lM = LM = 1.
Assumption C.20 (Distances Equivalence). Let M satisfies Assumption 1.2 and let d M M + R be distance function, possibly different from the Riemannian distance. There exists Tm S LM such that for all pair (2.y) y) E ECa
Emll
I d(x,y) v) S T.ull Exp=*(y)ll
(40)
24

---

D EXAMPLES OF RIEMANNIAN STRONGLY CONVEX SETS: BALLS WITH RESTRICTED RADIUS
In this section, we always make use of the Riemannian distance d, y) || Exp, (y)ll- The Riemannian strongly convex set, in Eq. (7), is the most restrictive of our definitions. It implies that, for all points æ the set C, the logarithmic image in the Euclidean sense. Intuitively, we can expect that such a situation arises when the logarithmic map Exp= does not affect the shape of too much, which is the case when the sectional curvature of M is bounded and the set C is not too large.
around x. i.e., Exp, (C), is strongly convex
In this section, we show that some sublevel sets of the function r d (x, xn)² are Riemannian strongly convex. Before proving the main theorem, we first introduce some concepts and two known results: 1) distance functions and Pokutta, 2022), and 2) locally, Euclidean pulled-back functions of geodesically smooth, strongly convex functions smooth and strongly convex in the Euclidean sense (Criscitiello and Boumal, 2021).
locally geodesically smooth and strongly convex (Martínez-Rubil
D.1 BOUNDED CURVATURE
In the following, we make an assumption regarding the curvature of our manifolds. Let us recall that, given Iuooddieenioonal subspace V C T.M of the tangent space of point x. the sectional curvature at x with respect to V is defined as the Gauss curvature for the surface Exp=(V) at r. The Gauss curvature at point x can be defined as the product of the maximum and minimum curvatures of the curves resulting from intersecting the surface with planes that are normal to the surface at x. See more details on curvature tensor R (Petersen, 2006). Our assumption is as follows.
Assumption D.1. The sectional curvatures of M are contained in the interval [Kminy Kmax] and the covariant derivative of the curvature tensor is bounded as || < F.
This assumption not overly restrictive. The majority of the applications of Riemannian optimiza- tion are in locally symmetric spaces, which satisfy V O, for instance, constant curvature spaces, the SPD matrix manifold with the usual metric, SO(n.. and the Grasmannian manifold (Lezcano- Casado, 2020).
D.2 STRONG CONVEXITY AND SMOOTHNESS OF DISTANCE FUNCTIONS
We now state fact regarding the smoothness and strong convexity of the distance squared point, that is central to many Riemannian optimization algorithms. In the sequel, we use the notation
K def max [Kminl: li K)
Proposition D.2. (See (Martónez-Rubie and Pokutta, 2022)) Let us consider a uniquely geodesic Riemannian manifold M of sectional curvature bounded B6mins Femaxl and ball Bag (r) in M of radius centered at xo. The function + md, xo)² is then 8,-strongly convex and G-ssmoth in Buo (r), where o, and Go are the geometric constants defined by
5. der (rv Kminn coth(r (KMin))
if KKmin S 5.
8, del 1
if KTmax
if Kimin 0²
r / cot(r /Kmax)
if Frmax
(41)
In the case of Cartan-Hadamard manifolds, 8, = and Gr
[r Kimin Tr Kmiin 1].
D.3 SMOOTINEES AND STRONG CONVEXITY OF EUCLIDEAN PULLED-BACK FUNCTION
Under Assumption D.1, (Criscitiello and Boumal, 2021, Proposition 6.1) showed that the Euclidean pulled-back function x + [[Expzo (x)) of a smooth, strongly convex function f defined in a ball of restricted radius in M is also smooth, strongly convex (in the Euclidean sense) in ball of the same radius.
Proposition D.3. (Informal, see (Criscitiello and Boumal, 2021, Proposition 6.1)for details). Let M be uniquely geodesic Riemannian manifold that satisfies Assumption D. and that contains
25

---

B( defined as Ba r) : fx E M: Ing) sr),
and let
(0, for Mi ||l| S rr.
As shown above, we also defined the malled-back ball to Tzn Let us assume the function f M + R is L-smooth, j--strongly geodesically convex in the ball Bl r), and has its minimizer x² Blznef T.). Then, if
min 1 K
I
AK
4F
the pulled-back back Euclidean function >> J (Expao (x)) is L-smooth, and u-sstrongly convex over the ball r).
One can relax the assumption of the minimizer being in the hall as this is only used to show that the Lipschitz constant of the function the ball most 2Lr. For instance, if the distance between the minimizer and Zref is R, the Lipschitz constant can be bounded by OLL)), and we could use this bound to conclude similar statement.
D.4
MAIN RESULT
Using Propositions D.2 and D.3, prove that balls and other sets obtained from sublevel sets of smooth and strongly g-convex functions small regions are Riemannian strongly convex.
Theorem D.A. Let M be uniquely geodesic Riemannian manifold that satisfies Assumption D.I, and let the function f x + 1 2dM(z; zo) Do E M. Then, the sublevel sets
1 C, = fx f(x) S 20
are Riemannian strongly convex ifr s 2/ min
IK K, where Gr and 8, are the smoothness and strong convexity parameters of the function 1d((s, in C, (see Eq. (41)).
This implies that Riemannian balls in these generic manifolds are geodesically strongly convex sets. We note that the greatest that satisfies the condition Theorem D.4 is roughly a constant, consid- ering constant curvature bounds. Being able to optimize in these sets is important as Martinez-Rubio (2020) proved that one can reduce global geodesically convex optimization to the optimization over these sets.
Impact the space curvature Curvature enters our results only through (i) the convexity radius of the manifold and (ii) bounds ensuring the exponential/log map distorts norm distances by trolled factors. These constants influence only the strong convexity modulus a but do not affect the qualitative nature of our results. Any manifold used in practice (SPD, Stiefel, Grassmann, sphere, hyperbolic models) has bounded curvature on compact regions; hence the assumptions of Theorem D.4 and Assumption 1.3 always hold for feasible of sufficiently small diameter.
26

---

E EXAMPLE OF A SIMPLE LINEAR MINIMIZATION ORACLE
When the curvature is constant (spheres or hyperbolic spaces) and the domain is a ball, the linear minimization oracle be simplified into one-dimensional problem.
Theorem E.1 (Linear minimization oracle in ball in constant curvature manifold). Let
B def B(xr, r) C M be closed Riemannian ball in manifold M a constant sectional curvature. If the curvature is positive, let us assume T < T convex. Given point and direction E T,M, define
2VR so that the ball is uniquely geodesically
det Exp2
(Exp (zo).
u3) (xo)
{or (M, = =r}.
The solution of aargmmnn B (v, Exp_" (z)) can then be found in l.
A direct consequence of Theorem E. is that the problem of approximating solution of the linear max oracle can be solved by solving an alternative one- mie-dmmesioonl problem.
Proposition E.2. Let U1 U2 be an orthonormal basis for the linear subspace span (Exp," (xx))" v}.
The solution of argmin,eBBl (v, (xpp"(=)) can then be obtained by solving the following one- dimensional problem,
min a(o)uu
pE[-
where p(Ø) and a()) over o E [- as p()) = cos( + sin())u2
a( argmin Dist (Fxp,(op(o))) xo) = (42)
a>0
The solution ó can computed using a oneddimensional solver, e.g., bisection the Newton- Raphson method. It should be noted that finding a()) is also a one-dimensional problem, and it can also be solved using similar techniques. In some cases, there are simple formulas for a(Ø), e.g., when the manifold is a sphere.
Proposition E.3. Let M = gn-1
be the unit sphere. Then, a()) in Eq. (42) reads
2tan -1 6(0) + V a² b(0)² d²
(Φ))
a = = b()) = pT)(
c= 1-2 sin (
+
27

---

F RFW AND LINEAR MINIMIZATION ORACLE ON THE SDP MANIFOLD
We now present the derivation of the Riemannian Frank-Wole (RFW) update for the case where the feasible region is geodesic ball in the SPD manifold equipped with the affine-invariant metric. Throughout this section we drop iteration subscripts when unambiguous.
Given the current iterate X S++ and gradient G TxS++. the linear minimization oracle (LMO)
associated with the trust region
B(X,)) :- (V E EST+ : v) mr}
the problem
min VEST
logx logxx()))
s.t. d(x, r.
(43)
At first sight, problem (43) appears difficult: the feasible set is curved and the objective de- pends on the Riemannian logarithm. However, we show below that the LMO admits a simple dinedinnn parametrization. In particular, every optimal solution lies in -io-dimensional subspace spanned by {logx (Xo), G}.
F.1 THE SDP MANIFOLD WITH AFFINE-INVARIANT GEOMETRY
We first define the SPD manifold with affine-invrriant geometry below.
Definition F.1 (SPD manifold with affine-invariant geometry). The space of symmetric positive definite matrices
S++ =X E
EX R"X" X- X
forms a smooth Riemannian manifold when endowed with the affine-invariant metric. For any X,Y E 84+ and any A, U, V E TxS++, the associated operators are:
d(X, Y) = ||oog(X11/8X' 1/13)|
11211111
(44)
logx (Y) 1/2 log( (X 1111111X 1/3/2/111/11111 x/2
(45)
expx (A) = X exp 11112AX--11 1/2) x1/2,
(46)
(U, V)x (X-1//UX-11/ 1/2 x X-1/Xx--11 V Tr (X-IUX--V)).
(47)
The main advantage of this geometry is its invariance under congruent transformations from the set GL(n) = {A E R=*" : det(A) #0):
Theorem F.2 (Affine invariance of the SPD metric). Let S (X E S" X > 0) and
(U,V)x tr (x Ux--v_
X St U,V E TxS++.
For A E GL(n), define the congruence action
: S4: Sn S++
x AXAT.
Then A is isometry for this metric, i.e.
(d (X) d x (X) (x) = (U.
for all X E Sh_ and all U.V E T
Proof. Since A is linear, its differential satisfies
dΦ d = AUAT.
Also, (AXAT)-1 = - A! Hence
(AUAT, AVAT) AXAT
= =ir -(x(A-Txxx--aa)
28

---

By cyclicity of the trace,
tr(A MA)) = tr(M),
M
(d (d)x())(U), d 2xx0)//22)2//00 = - (U,
As consequence, the distance function is also invariant under congruent transforms.
Corollary F:3 (Affine invariance of the distance). Lei d(X,Y) be the geodesic distance induced by (x-)x tr(x -U For any A GL(n),
d (AXA", AYAT) d(x,Y).
Proof. For any smooth curve 7(t) joining X to Y, define 7(1) AT(1)AT, By metric invariance,
a)))) [[((t)])>()-
Thus Length(5) = Length(7). Taking the infimum over all curves gives
d(AXA", AYA = d(X,Y).
Theorem F44 (Equivariance of the exponential map under congruence). Let S4+ be endowed with the affine-invarionn invariant metric
(U, V = -
XES U.V E Txx+++
For any GL(n), consider the congruence action
① A S S+++
4 AXAT.
Then the Riemannian exponential satisfies the equivariance identity
(10x)x((12(X))U)) (x(expx(U)),
X XES, U TxS.
Equivalensly,
eXPAXA (AUAX)(AAAA)) (U)x
Proof. Since A is isometry (Theorem F.2), maps geodesics geodesics while preserving their speeds. Let (t) be the unique geodesic with initial data
700) = X,
7(0) = U. r(1) expx (U).
Define 7(t) (a(((t)) AT By isometry,
7(0) AXAT. (() AUAT,
(t) is geodesic.
Uniqueness of geodesics with prescribed initial conditions implies
7(t (t
Evaluating at 1 1,
A eexpx(U) = - eAPAXAT(AUAA).
29

---

F.2 A
REDUCTION FOR THE LMO IN AN SPD BALL
We now show that the LMO can be reduced to a one dimensional problem. First, the proposition below parametrize the solution of the LMO V by V Exxxx, (("))"" where p" is unit norm vector.
Proposition F.5 (Directional reduction of the LMO). For any unit tangent direction E Tx. with | 1, define a(p) 0 as the unique solution of
d (Xo, expx, (a(p) =r
Then every solution of the IMO lies in the set
r = expx, (a(p) P S++ Illlxx = =1].
Moreover,
V argmin a(p) (Gks p) x
Proof. Since the objective V (Ga, logx, (V)) x, is smooth and C is compact, optimal solution exists. If y were in the interior of C, a sufficiently short geodesic move along (- grad) would decrease the objective while remaining feasible, contradicting optimality. Thus d(Xo, V*) =
For any unit direction p E S hence it intersects the boundary d(., Xo) may be written as expx,, (a(p)p) for some p. establishing the representation of l'.
S++ the function a + d(Xo. expx, (ap)) is strictly increasing,
unique app) >> O. Therefore every boundary point
Along each such geodesic ray,
(Gy, logx, (expxx (ap))) x. = ax X+>
so minimizing over the boundary reduces to minimizing ( p) over unit vectors p.
Proposition F.6 (Reduction two-dimensional subspace.). Proposition F.5, the direction p belong to the subspace
p E span(logx, Gk).
Proof. Let W == span (Xo), GR3 C Tx. For any unit tangent vector p E S we decompose
p= PW P.1. Pw W, P1 P
llplxx =1
We need to show that (i) a(p) = a(pw) and (ii) (Gx,P) x, (Gr,Pw)xx
(i) The boundary constraint depends only on the angle with logx, (Xo). Because the affine-invariant metric is preserved under congruence transformations, so is its induced distance:
d(AXAT AYAT) d(X,Y)
AA GL(n).
Let Xg E ST+ and define
Z = x==x²"1 X 1/2 1/2 12xxx 1/2
Take an eigen-decomposiiion
Z z= eexp(AA)
with Q orthogonal and A diagonal. Then set
A: Q -= 1/2
This A satisfies
AX,A =I, In these coordinates the geodesic from I in direction is t + exp(t with p = ApAT, and the distance to X, becomes
AX,A exp(A).
d ex,xx (Ip) d (xxp(()))xxp(())) ex)(Ip))
30

---

For the invarriit metric, distances from exp(A) depend only on the radial component of in the direction of A, ie. on the angle between p and All components of p orthogonal contribute only tangentially and do not change d(exp(A), exp(tt)). Thus the map
I + d (Xo. expxx (4p)
completely determined by the angle between p and logx, (-o)), and is strictly increasing in Since p and its projection pw have the angle with logx, (Xo), they induce the same boundary- hitting parameter:
((p) a(pw).
(ii) The objective only depends on the projection onto span (.x.. Since pu orthogonal to Gs in the Riemannian metric.
(G x² (G&,Pw)xx
Combining (i) and (ii). for every feasible p.
alp) (G x)x, a(pw) PW)x
Hence any direction p is no better than its projection pw, and no minimizer can have component outside W. The search can therefore be restricted without loss of optimality to the two-dimensional subspace W.
This yields practical one-dimensional formulation. Theorem F.7 (Angular parametrization of the LMO). Let
W span (logx. (Xo); Gk] C Sx,
and choose an orthonormal basis {u1, u2) W. W. For & E [- n. define
p cos in + sin(d) u2,
llp())llx, =1
and let a(Φ) be the unique scalar such that
d (Xo, expx, (a())
Then, solving the LMO Eq. (43)
min VEST
(G, (V)
d(X,V) sr. s.1.
(48)
equivalent to solve the dimenniiii problem
min
a(δ) (G, p(d))
ΦE[-
and then form V ((("))
Proof. By Proposition F.6, any optimal direction lies W, so we can write = p()) for a unique [-,,-]] TT. By part (i) of that proposition, the boundary parameter depends only the angle with logx, (Xo), hence on d, giving a = a(()). By part (ii), the objective depends only on the projection of onto span Gx) hence
(Gk,P)x, a()) (Gx))(o))
Thus minimizing over all feasible p is equivalent minimizing over [-T,, n]. as claimed.
Both (²) and the outer minimization over & can be solved efficiently using one- -ne-dimensional solvers such bisection Newton's 's method.
31

---

F.3 ALGORITHM FOR THE LMO
We present two equivalent versions of the LMO. The first (Algorithm 2) operates directly in the affine-invariant geometry. The second (Algorithm 3) uses congruence transform to simplify all expressions.
Using affine invariance (Theorem F.2), introduce the normalized variables
X = X 1/2
xxx
1/2
Xu = Xx 1-2 X 1/2
In these coordinates we have
Xx =1,
Xo exp(AA,
for some symmetric matrix A. At I, the affine-invarian metric coincides with the Frobenius struc- ture:
(U, V), VV,.
| |.]|.
Moreover,
log, (Y) lYog(Y)
exp,(S) = =xx(())
In this normalized geometry, all Riemannian quantities at X reduce to standard matrix exponen- tials, logarithms,, and Frobenius inner products. The LMO therefore becomes a two-parameter search (ø, a) over symmetric matrices of unit Frobenius norm, yielding the simplified algorithm in Algorithm 3.
Algorithm 2 LMO SPD ball (affine-invarian invariant geometry)
Require: Xo, X2 E S4 radius r > 0, gradient Gs
Ensure: V
(A) Construct the 2D subspace W
1: 01 logxe (Xo); U1 f- u1/llurlxxa
2: 91 = G5 (Gk, u1)x, un; U2 = 91 / Xx
(B) Angular parametrization
3: For o E [-m, m)m set
p(0) = cos su + sin sininn u2.
(C) Reduced objective
F(ø) = a()) (Gr,p(o))xa
a()) exp,
More explicitely,
logg X 1/2 x11 exp(a 1/2 "(0)) x1! xo 1/2
a solves
(D) Final ID minimization
arg
min F(ø), DE -,
p² p'= a" a'=a(0").
4: return V' = =xxx,, (a'p*)
32

---

Algorithm 3 LMO SPD ball in normalized coordinates
Require: Xx E =.44, radius 0, gradient G₃
Ensure: V*
1: (Normalization)
2: M <-
1/2
3: Compute eigendecomposition
M = eex((A]Q"
with diagonal (and symmetric).
4: Define the congruence:
At Q 1-1
Then
= AXA,
Xx = I No = exp(A).
5: Transform the gradient:
G. AG&A =Q _xx,
1/2 Gr 122 122201200
(A) Construct the 2D subspace
6: #1 log( Xo) A; in + u1 / ||..
7: 91 = G. (G2, ui) u2 = 91 /1/ll91l1e
(B) Angular parametrization
8: For o E [-n, [- n], define
p()) = cos Φu + sin ó
(C) Solve for (d)
9: For each Φ define (0)) > as the solution of
log( exp(-A/1 exp(a())r(o) exp(- exp(-A/2)) =
(This a ID root-finding problem.) Define the reduced objective
F(Ø) a (Õx, p()))r-
(D) Final ID minimization
arg S
min
F(Ø), p'='(ő"), a' a' aa=0(""). a()').
11: Compute the normalized solution
V = exp(a" p²).
12: (E) Map back to original coordinates
Since X AXAT with A Q X-11/2 1/2
V A -- T X x
13: return V*.
33

---

F.4 NUMERICAL EXPERIMENT: MINIMIZATION OVER AN SPD BALL
10-1
Linear Convergence
RFW Dual Gap
REW Duality Gap
10
10
10
10
100
15 # Gradient Ornele Calls
Gradient Oradle Calls
Figure 3: Convergence of the RFW algorithm (Algo. 1) for minimizing geodesically smooth convex function over geodesic ball in the SPD manifold endowed with the affinc-invariant metric. The dimension is 50, the center Xa random, the radius is 0.1, and the objective is f(X) = }jd(X, Y)² with Y placed just outside the ball at distance 1.01 x (the closer to r, the harder the instance). As predicted by Theorem 5.2, the iterates display a clear transition from the global O(L regime to a locally linear rate. Interestingly, the curve suggests the possibility of a global linear rate for this particular geometry (SPD with the affine-invariant metric), the observed behavior matches the minimum of the two theoretical regimes.
This experiment tests the convergence guarantees of Theorem 5.2 the SPD manifold S++" endowed with the affine-invariant geometry. We consider the problem
min S(X) XEST
s.t.
Xo) Sr,
(49)
where f(X) )d(X. and Y is chosen such that d(Xn, Y) r. forcing the optimizer to lie on the boundary of the feasible set. The resulting convergence curve in Fig. displays the two characteristic regimes: global sublinear phase followed by sharp transition rate ensured by the strong convexity of the SPD ball. This benchmark validates the theoretical predictions and confirms that the geometric structure of the feasible region governs the accelerated behavior of RFW.
the linear
34

---

G MATLAB CODE FOR THE EXPERIMENTS
To run the experiment, is required to have sufficiently recent version Matlab, and the toolbox Manopt (Boumal al., 2014).
G.1 SUBROUTINE: LINEAR MAX ORACLE FOR BALL IN A SPHERE
function
(w, R, x0, manifold)
2
% Solve the problem
: % max w z iin exp-x"(-1)(C),
% where C == fx: dist (x) R]
6 Assume that the sphere has radius = 1!
7
8 % Define the two basis vector of the subspace u_l and u_2
9 ul w;
ul = ul/norm (ul);
manifold.. log (x, x0);
u2 u2-ul sul =u2);
13
if norm (u2)
15
u2 = u2/ ///oorm(22)) (u2);
p = @(phi) cos (phi) sul sphi)))
alpha (p) solve sincoseq (x0's *x, xx,00x x0'x0'>p. *p.(1 -2* sin (2)2)
fhandle @ phi)
%same minimum
since w*u2 = 0.
options optimset( TTol'' .eps);
[best-phi] fminbnd ( (fandlee -pi pi, options);
manifold exp p(best phi), (1pha(p( phi))):
else
alpha solve_sincoser (x0' *x, *x,xxxx0 x0'xu,,, ,1 -2 (R/2) 2))); % best
direction: ul
26
v = manifold ex, ul, alpha);
end
35

---

G.2 SAMPLE SCRIPT: RANDOM QUADRATIC OVER A SPHERE WITH BALL CONSTRAINT
% Generate the problem data.
2 50;
5 n = 25; % Slower convergence when n < -> non-strongly convex
case
nlter = 500;
s dualgap = ze,os(1, nlter);
: Manifold: this code uses manop, see https /// www. manopt. org
manifold (pherefactoryyd));
% Define the problem cost function and its derivatives. = (nndn(n.d)
A'*A;
13 = A/norm(A);
xstar manifold.. rand ();
@(x) 0.5*(x-xstar) *>=xxxxstarr;;
mgrad = @(x) manifold egrad2rgrad Ax(x-xstar));
L norm (A); % Worst case
% Create the problem set 18
x_center = manifold rand radius-ratio 0.9; % <I: xstar is oustide
22 radius max manifold. dx center xstar) (sstar*rraaee radius ratio (x_entrr
setFunction @(x) manifold. dist x)<=radius max
x_center; % Main loop RFW
for i=1:(nlter
gradx = mgrad (x);
linear max pracle(-gradx: x, radius max center, manifold);
dualgap(i) maanfoold inner(x, gradx, manifold. log(x, v));
32
step size -manifold inner gradx, manifold log v) / (L
manifoll dxst 2)
33
step-size min(step (step-size. 1);
manifold (xx manifold log(x, v), step size);
35
end v linear_man wwa.mmooooccee-graa.... x, radius_max, x_center, manifold);
dualgap (nd) -manifold ixner gradx, manifold. (xg v));
% Max at eps, otherwise the result is numerically meaningless semilogy (1:length (dualgap), max (duualaap legend ({ 'WW Dual Gap }
LLM USAGE
The authors acknowledge the use of a large language model (LLM) to assist with improving the clarity and presentation of the manuscript.
36


Reviews:
[{"review_id": "yfLUHrKtRR", "reviewer": "Reviewer_66fh", "summary": "This paper provides the first systematic study of strong convexity of sets in Riemannian manifolds, bridging geometric structure and algorithmic benefits. Authors introduce novel properties of sets defined in Riemannian manifolds, provide examples, and demonstrate improved convergence rates when minimizing functions over such sets.", "questions": "1. This article has theoretical significance and is well written, however， this paper lacks practical experiments. Can some practical application scenarios of the proposed algorithm be added.\n2. If it is possible to discuss the application of the proposed theory in practical scenarios in the main text.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Authors introduce various definitions of strongly convex sets in Riemannian manifolds and establishes relationships between them.\n2. This paper introduces the notion of approximate scaling inequality and its link with what they call double geodesic strong convexity.\n3. Authors prove that sublevel sets of geodesically smooth, strongly convex functions are strongly convex in Riemannian manifolds under mild conditions, providing a constructive perspective for identifying such sets.\n4. Authors derive a linear convergence bound for the Riemannian Frank–Wolfe algorithm when the constraint set satisfies the (Approximate) Riemannian Scaling Inequality.\n5. This paper also provides examples of strong convex sets in Riemannian manifolds. More precisely, Appendix D shows that Riemannian balls (with restricted radius) satisfy the strongest of the notions of Riemannian strong geodesic convexity. Appendix E details a simple linear minimization oracle for the sphere manifold.", "weaknesses": "This article has theoretical significance and is well written, however， this paper lacks practical experiments. Can some practical application scenarios of the proposed algorithm be added.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DVRARWcUiX", "reviewer": "Reviewer_6e96", "summary": "This paper addresses a critical gap in Riemannian optimization by providing the first systematic definition and analysis of strongly convex sets on Riemannian manifolds. Unlike prior work that focused on strong convexity of functions (Zhang & Sra, 2016; 2018) or limited notions of set convexity in metric spaces, this work introduces three rigorous definitions of strongly convex sets (i.e., geodesic, Riemannian, double geodesic) that naturally extend Euclidean strong convexity.", "questions": "1. While this paper provides theoretical conditions for strong convexity (e.g., Theorem 4.2, Theorem D.4), it offers limited guidance on how to verify these conditions for a given manifold and set in practice.\n\n2. The results in this paper heavily depend on manifold curvature (e.g., Theorem D.4’s radius bound, Proposition D.2’s smoothness/strong convexity constants), but it does not fully explore how curvature impacts algorithmic performance or the practicality of strong convexity.\n\n3. The related work section mentions prior notions of set convexity in metric spaces (e.g., Aleksandrov, 1957; Paris, 2020) but fails to provide a systematic comparison of the proposed definitions to these alternatives.\n\n4. This paper mainly focuses on convex objectives (geodesically convex f), but many practical Riemannian optimization problems are non-convex (e.g., training manifold-valued neural networks, Katsman et al., 2023). Can the framework be extended to non-convex objectives with strongly convex feasible sets?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Propositions 2.5–2.7 establish a hierarchy of strong convexity notions, clarifying when each definition is applicable (e.g., double geodesic strong convexity is equivalent to geodesic strong convexity under mild distance equivalence assumptions).\n\n2. Theorem 4.2 extends a classic Euclidean result (Journée et al., 2010) to Riemannian manifolds, showing that sublevel sets of geodesically smooth, strongly convex functions are themselves strongly convex.\n\n3. The paper leverages the Riemannian Scaling Inequality to prove linear convergence of the Riemannian Frank-Wolfe (RFW) algorithm (Theorems 5.1–5.2).", "weaknesses": "1. While this paper provides theoretical conditions for strong convexity (e.g., Theorem 4.2, Theorem D.4), it offers limited guidance on how to verify these conditions for a given manifold and set in practice.\n\n2. The results in this paper heavily depend on manifold curvature (e.g., Theorem D.4’s radius bound, Proposition D.2’s smoothness/strong convexity constants), but it does not fully explore how curvature impacts algorithmic performance or the practicality of strong convexity.\n\n3. The related work section mentions prior notions of set convexity in metric spaces (e.g., Aleksandrov, 1957; Paris, 2020) but fails to provide a systematic comparison of the proposed definitions to these alternatives.\n\n4. This paper mainly focuses on convex objectives (geodesically convex f), but many practical Riemannian optimization problems are non-convex (e.g., training manifold-valued neural networks, Katsman et al., 2023). Can the framework be extended to non-convex objectives with strongly convex feasible sets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oDYPdXTfx0", "reviewer": "Reviewer_QN9G", "summary": "This paper considers strongly convex sets in Riemannian manifolds and proposes several definitions, which generalize the Euclidean counterparts. In addition, the linear convergence rate of Riemannian FW algorithm can be derived via the proposed Riemannian scaling inequality condition.", "questions": "1. the scaling inequality is quite similar to the uniform normal inequality in https://www.heldermann-verlag.de/jca/jca02/jca02008.pdf and https://arxiv.org/pdf/2002.06309. It would be better to mention them in your paper.\n2. Could you provide some concrete examples of $C$ that satisfy Assumption 1.2?\n3. In lines 243-245, the authors mention \"This theorem applies to most practical cases ...\". Could the authors explain more about this part? I am curious about the implication of results in this paper on specific optimization over manifolds (e.g., SPD, SO(3), Stiefel manifolds).", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Studying strongly convex sets in Riemannian manifolds is interesting, which requires a good understanding of both convex analysis and Riemannian optimization/geometry.", "weaknesses": "1. I did not see the practical improvement/implication of this paper's results on optimization over manifolds (e.g., SPD, SO(3), Stiefel manifolds, Grassmann manifolds). It would be great if the authors can explicitly provide some new results for concerte examples.\n2. The numerical experiments are limited and only for sphere constraints. In this case, this paper is quite related to (https://arxiv.org/abs/1911.11955). In addition, there are several papers of optimization over SPD and Stiefel manifolds with linear convergence rate, e.g., (https://arxiv.org/abs/2001.01700, https://arxiv.org/abs/2112.06556). It would be better to compare with these papers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HApH40yRtg", "reviewer": "Reviewer_51us", "summary": "The paper studies the notion of strong convexity in the setting of reimannian manifolds (and geodesic spaces). Though strong convexity is a well studied and natural notion in Euclidean space, generalization of this concept to manifolds is non trivial. The present paper studies various versions of such a definition and presents fast convergence of natural algorithms under these definitions. In particular, they show that a version of Frank-Wolfe converges linearly for strongly convex optimization", "questions": "-> Further discussion of the assumptions are very important. For example, assumption 1.3 seems very strong to me. In particular, it is seems like a strong quantitative local Euclidean property that could potential make the difficultly of the RM setting a bit moot (I understand that there is still variation in the metric and this leads to technical difficulties; but it would be good discuss the \"conceptual\" hurdles. \n-> Getting log(1/eps) rates for Geodesic optimization actually happens to be an important problem in subfields of theoretical computer science (eg https://arxiv.org/pdf/1910.12375) and has garnered interest in the field. Unfortunately most proposed algorithms work under assumptions that are hard to check or make assumptions the algorithm work only is \"near Euclidean\" settings. It would be interesting to see a discussion of the present paper in this context (or related applications)", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Generalization of the toolkit of optimization to the setting of manifolds has considered an interesting and important problem for the past several years, due to both theoretical and practical motivation. Systemizing Euclidean definition to the manifold setting is an important step and understanding what assumptions lead to fast algorithms is an important step", "weaknesses": "Though the problem is interesting, I personally think that the definitions presented in the paper are not particularly insightful and it is not clear how generally applicable and useful the defnition would be. As presented, the definition come off as a \"syntactic\" generalization of the Euclidean case and thus fail to convey insight into the RM optimization problem", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "36L134Ojoy", "reviewer": "Reviewer_ArMd", "summary": "This paper proposes a Riemannian Frank–Wolfe (RFW) algorithm with linear convergence guarantees under a novel set of strong convexity assumptions for constraint sets on manifolds. It extends the classical Euclidean FW framework and introduces several definitions of strong convex sets tailored to geodesic settings. The theoretical development is comprehensive and the main results are sound.", "questions": "Which practical ML objectives/constraints on common manifolds (e.g., sphere, SPD, Grassmann) actually satisfy your assumptions (geodesic convexity + RSI, or approximate RSI + gradient lower bound)? Please provide at least one end-to-end experiment and a concrete example to check/estimate the RSI constant and strong-convexity modulus on real data.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper generalizes linear convergence guarantees of the FW method from Euclidean to Riemannian settings under appropriately defined curvature-aware convexity.\n\n2. The paper provides formal geometric characterizations and includes theoretical examples of sets satisfying the RSI condition.", "weaknesses": "1. Although the paper motivates the RFW method via machine learning applications (e.g., Example 5.3), there are no real ML experiments. In particular, the neural network loss mentioned in Example 5.3 is not geodesically strongly convex, and the main convergence theorems do not apply to such cases. This weakens the practical relevance of the proposed method.\n\n2. The three definitions of strongly convex sets—geodesic, Riemannian, and double-geodesic—are introduced in sequence, but are somewhat hard to digest. A clearer summary (e.g., a comparison table showing hierarchy, assumptions, and known examples) would greatly help readability.\n\n3. The proposed notion of strong convexity (and RSI) is in contrast with proximal smoothness (prox-regularity) in Euclidean space, where the corresponding inequalities (see Davis, Drusvyatskiy, and Shi, SIAM J. Optim. 2025) take the opposite form (i.e., bounding curvature from above instead of below). The paper should clarify that this is due to fundamentally different settings: the current work focuses on Riemannian geometry, while prox-regularity is established in embedded space.\n\nreferences:\nDavis, D., Drusvyatskiy, D., and Shi, Z. (2025). Stochastic Optimization Over Proximally Smooth Sets. SIAM Journal on Optimization, 35(1), 157–179.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)