Finite-Time Analysis of Stochastic Nonconvex Nonsmooth  Optimization on the Riemannian Manifolds
Authors: Emre Sahinoglu
Youbang Sun
Shahin Shahrampour
Venue: NeurIPS 2025 poster ()
Keywords: Riemannian Optimization
Nonsmooth Optimization
Nonconvex Optimization
Primary area: optimization

Abstract: This work addresses the finite-time analysis of nonsmooth nonconvex stochastic optimization under Riemannian manifold constraints. We adapt the notion of Goldstein stationarity to the Riemannian setting as a performance metric for nonsmooth optimization on manifolds. We then propose a Riemannian Online to NonConvex (RO2NC) algorithm, for which we establish the sample complexity of $O(\epsilon^{-3}\delta^{-1})$ in finding ($\delta,\epsilon$)-stationary points. This result is the first-ever finite-time guarantee for fully nonsmooth, nonconvex optimization on manifolds and matches the optimal complexity in the Euclidean setting. When gradient information is unavailable, we develop a zeroth order version of RO2NC algorithm (ZO-RO2NC), for which we establish the same sample complexity. The numerical results support the theory and demonstrate the practical effectiveness of the algorithms.

Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds
Emre Sahinoglu Northeastern University sainnglu.n@hoorhhesttomm edu
Youbang Sun
Tsinghua University ybsun@mail. tsinghua.ede edu. cn
Shahin Shahrampour
Northeastern University
s. shahhraappourr@hhhhhassste...
Abstract
This work addresses the finite-time analysis of nonsmooth nonconvex stochas- tic optimization under Riemannian manifold constraints. We adapt the notion Goldstein stationarity to the Riemannian setting as performance metric for nonsmooth optimization manifolds. We then propose Riemannian Online NonConvex (RO2NC) algorithm, for which we establish the sample complexity 3 in finding (6, c)-stationary points. This result is the first-ever finite-time time guarantee for fully nonsmooth, nonconvex optimization on manifolds and matches the optimal complexity in the Euclidean setting. When gradient information is unavailable, we develop a zeroth order version of RO2NC algorithm (ZO-RO2NC), for which we establish the same sample complexity. The numerical results support the theory and demonstrate the practical effectiveness of the algorithms.
1 Introduction
Gradient-batd iterative optimization algorithms are frequently used as numerical solvers for machine learning problems, many of which deal with search spaces with manifold structures. This includes deep learning [61] natural language processing 34,, principal component analysis (PCA) [9]]
dictionary learning [1] (66, Gaussian mixture models (29 and low-rank matrix completion [27]
Riemannian optimization methods [ 54 offer a toolkit to solve optimization problems with
manifold constraints and have attracted great interest due to their wide range of applications. However, unfortunately, conventional Riemannian optimization algorithms require access to the derivative of smooth function, often falling short in highly nonsmooth, nonconvex problems such as training neural networks.
In this paper, we consider stochastic Riemannian optimization of an objective function f M:M- + R,
min sEM
(1)
where F is stochastic nonsmooth objective function, defined on d-dimensional complete manifold M that can embedded in the Euclidean space, and corresponds to random data samples. Many important problems can be formulated as nonsmooth Riemannian optimization over smooth manifolds, including sparse PCA, compressed modes physics, unsupervised feature selection, and robust low-rank matrix completion [10] 30). This problem setting is also commonly encountered in deep neural networks, where optimization algorithms must be able to cope with deep nonlinear layers with ReLU activations
2 20 21 55 69].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table 1: Convergence rates of various algorithms over nonsmooth, nonconvex objectives: Composite objectives are in the form of f() + h(x), where f is smooth and h is possibly nonsmooth and convex. Fully nonsmooth objectives can be written as f(x) (x, v)], where F is nonsmooth and nonconvex. Our work is the first to provide the finite-time analysis of the fully nonsmooth setting. t and indicate that the objective is defined Stiefel manifold or compact manifold, respectively.
REFERENCE
METHOD
SETTING
OBJECTIVE
CONVERGENCE
23
SUBGRADIENT
DETERMINISTIC
NONSMOOTH
ASYMPTOTIC
PROXIMAL GRADIENT
DETERMINISTIC
COMPOSITE
O
59
PROX. GRAD. SPIDER
STOCHASTIC
COMPOSITE
O
44
R-ADMM
DETERMINISTIC
COMPOSITE
O(e
16
AUG. LAGRANGIAN
DETERMINISTIC
COMPOSITE
O
16
AUG. LAGRANGIAN
STOCHASTIC
COMPOSITE
50
SMOOTHING
DETERMINISTIC
COMPOSITE
O
60
SMOOTHING
STOCHASTIC
COMPOSITE
O(E
OUR WORK
SUBGRADIENT
STOCHASTIC
NONSMOOTH
0(8-
There exists a scant literature on the theory of nonsmooth Riemannian optimization, mainly focusing on the asymptotic results and leaving the finite-time analysis unexplored. In fact, even in the Euclidean setup, finite-time results for the nonsmooth, nonconvex setting have been studied only recently in the last few years. This is perhaps not surprising; the finite-time analysis of smooth, nonconvex optimization usually carried out by finding a stationary point x such that [=)]l S c. However, for nonsmooth, nonconvex functions, finding such e-stationary point is in fact intractable. Instead, the notion of Goldstein stationarity has recently been analyzed by [66) to provide non-asymptotic results. Goldstein stationarity does not directly evaluate [==)] and instead considers the convex hull of subgradients of points in the ô-neighborhood of x..
To address nonsmooth problems on Riemannian manifolds, this stationarity criterion can be adapted to the Riemannian setting using the Riemannian 8 Ō-subdifferential definition of [32]. However, the
finite-time analysis of finding such (6, c)-stationary points on Riemannian manifolds is a tantalizing challenge that has remained elusive.
Our Contributions. In this paper, we address the finite-time analysis of nonsmooth, nonconvex stochastic Riemannian optimization:
We adapt the notion of Goldstein stationarity 45 66 to the Riemannian setting, providing a metric to evaluate the finite-time performance of nonsmooth, nonconvex optimization on manifolds. We then propose a Riemannian Online to NonConvex (RO2NC) algorithm that can be analyzed using regret bounds in online optimization. Our proposed algorithm can utilize retraction as computationally efficient alternative for exponential mapping.
We theoretically prove that RO2NC achieves the sample complexity of 0(8-1e-3) in finding (ô, e)-stationary points. We first establish this result using parallel transports (Theorem 3.1) and then extend it to projections (Theorem 3.3). This rate is first ever finite-immee result the fully nonsmooth, nonconvex optimization on manifolds and matches the optimal sample complexity in the Euclidean setting (13). It is derived under mild technical assumptions applicable to standard manifolds (e.g., Stiefel, Hadamard, Grassmann) without the need for restrictive assumptions on the objective function (e.g., weak convexity). which is assumed to be Lipschitz continuous.
Extending our results to the zeroth order oracle setting, we show that ZO-RO2NC can achieve the same rate (Theorem 4.2) using a gradient estimator relying solely on stochastic function value queries, Our proposed gradient estimator samples vectors on the tangent space instead of the manifold, resulting in more computational efficiency without costly manifold- specific computations. We show that the gradient estimator satisfies certain distance bounds the Goldstein subdifferential set, which is sufficient achieve the Goldstein stationarity criterion. The main merit of this result is streamlining the zeroth order analysis without recourse to more challenging alternative estimators that require the calculation of volume and surface of manifolds, which could be computationally demanding.
2

---

1.1 Highlights of the Technical Analysis
RO2NC Algorithm Design. Developed by [3, O2NC is an optimal algorithm for finding Goldstein stationary points of nonsmooth, nonconvex objectives in the Euclidean space. O2NC works based on the interplay of two algorithms. At each epoch, an action A is generated via an online learning algorithm and is used to update the variable 2++1 = I4 + D.. Then, gradient Ir evaluated at random point wi = It + sA, with ~ unif [0, 1] and is given to the online learning algorithm as a feedback to update Dr- (i) One difficulty in the Riemannian setting is that r++1 = 2t + A does not ensure feasibility. We must keep the iterates { on the manifold M,, which requires the updates, i.e., Jt+1 Retra, (A.). (ii) Also, since the action and
the use of retractions feedback of the online learning algorithm belong to different tangent spaces, we must transport these vectors via parallel transports and/or projections. (i) and (ii) together introduce a technical challenge different from the Euclidean setting: we can no longer rely the classical regret analysis in online optimization to streamline the intra-epoch analysis. Instead, we must creatively choose the right benchmark action at each epoch using projections and/or parallel transports to judiciously analyze the error terms caused by the manifold geometry.
Adapting Goldstein Stationarity to Riemannian Setting, In the Euclidean setting, the Goldstein subdifferential set is defined as a convex hull of Euclidean differential sets at different points. In the Riemannian setting, subdifferential sets at different points possibly belong to different tangent spaces, so is required to transport those sets to a common tangent space. We choose the parallel transport operation in the definition of Riemannian Goldstein subdifferential set as it preserves the length of the vectors unlike the projection operation. Upper bounding the minimum norm element in the Goldstein differential set requires transportation of gradients at different points, where the distortion caused by parallel transport along the closed loops is analyzed with the curvature of the manifold (c.f. Lemma 2.9 Using similar approach, we derive upper bound on the distance between zeroth order gradient estimates and Goldstein subdifferential set by quantifying the effect of parallel transport along geodesic triangles (c.f. Lemma 4.11
Zeroth Order Riemannian Gradient Estimator. In the Euclidean setting, the analysis of zeroth order gradient estimator for nonsmooth objectives is carried out through smoothing. The key is that the gradient of the smoothed objective Ss estimated by a stochastic gradient estimator gs, such that [[gs(x)) = [zx) [45] Lemma 1. Extending this approach to the Riemannian setting introduces a great challenge. The smoothed objective fs necessitates the volume calculation a manifold set, which is computationally expensive. To make the estimation practical, we define an objective hi based on efficiently sampling a vector in the tangent space, such that [[]s(x)) = gradh& (z), where 95 is the Riemannian gradient estimator. However, the inclusion property E[gs(2)] E 0sf(x) of the Euclidean setting does not hold anymore in the Riemannian setting. We address this technical challenge by deriving an upper bound on the distance between these two terms function of the curvature and 5 (c.f. Lemma A.5). We further compute a bound on the Lipschitz constant of his (Lemma A.3) and show that the 06-11-33 convergence rate is preserved.
1.2 Literature Review
Nonsmooth, Nonconvex Techniques in the Euclidean Setting. Given that calculating c-stationary point for nonsmooth, nonconvex functions is intractable in general, various assumptions or conditions have been proposed in the literature (e.g., weak convexity (8] [4] In recent years, the finite-time
convergence analysis of the Goldstein stationarity, proposed by [66]. has gained much interest. Their algorithm is guaranteed to reach (6, ))stttioonary point with the complexity of 0(--18-1. [13
improved this rate to 06-33-1) with the introduction of an online to nonconvex conversion method. The method was then extended various settings, such as decentralized optimization (5I).
For some optimization applications, gradient evaluations are not possible, and only zeroth order information is available. To solve these problems, [40] proposed gradient estimator, which is calculated at point x and requires evaluation of f(x + tv). In nonsmooth, nonconvex optimization, the convergence rate for finding (6, c)-stationary points with gradient-fre methods was analyzed by [45]. Later (37] proved that the optimal dimensional dependence of (dd) in the zeroth order setting could be achieved with O2NC.
Manifold Optimization. Due to the unique properties of manifolds, many Euclidean optimization algorithms have been adapted to the Riemannian setting. Utilizing manifold operations, these
3

---

methods are able to match the convergence rates of their Euclidean counterparts, These Riemannian
algorithms include gradient descent methods [ 65], projection- free methods [ [3] and accelerated
methods 36 48
The convergence results also cover various settings, such as min-max [3 49 68
variance reduction [54], online optimization [6] 46
52
53
62), and decentralized optimization
57). However, the majority of the studies here focus on smooth and sometimes geodesically convex objective functions, leaving the nonsmooth optimization relatively underexplored.
For the gradient-free optimization setting, zeroth order methods have been adapted from Euclidean to the Riemannian setting 42
c0 The Riemannian zeroth order methods have also been extended
to different settings, such as online Riemannian algorithms 46 52 62
and accelerated algorithms
(26]
Nonsmooth, Nonconvex Optimization on Manifolds. The optimization task becomes more chal- lenging when the objective function is nonsmooth and nonconvex over the Riemannian manifold. Some techniques have been developed and analyzed in nonsmooth, nonconvex optimization, such as (i) subgradient-oriented methods, (ii) proximal point methods, and (iii) operator splitting methods. In -rrientet methods [4] [17 18 23 25 32], at iteration & a direction gr in the tangent space of the manifold is calculated from the current previous subgradient evaluations. The next iterate Te-1 is then calculated based on manifold operations, such as retractions or exponential mappings. For proximal point algorithms p [5| 28 B3 , the algorithm solves sub-prot problem in each iteration. The objectives for the sub--uublee problemss are formulated by an approximation of the original function combined with an additional penalty term. However, in some cases, solving the sub- sub-problems is just as difficult as the original problem, making these methods difficult to implement. The operator- splitting methods 39] divide the original problem into several sub-problems that are easy to solve using techniques such as the alternating direction method of multipliers ( (ADMM). These methods either lack convergence guarantees (38 or need further technical conditions 67
2
Preliminaries
In this section, we first provide a brief introduction on manifolds and useful notatiins/deffmitions. Then, introduce Goldstein stationarity and state our technical assumptions.
2.1 Background on Manifold Optimization
We consider the optimization task in equation defined on M, which is embedded submanifold in the Euclidean space. We denote by T.M the tangent space of the manifold at point x. We denote the sphere (and ball) with radius r on T by (r) (and (r)) respectively. The set of pairs (x. Ex) where & E T,M is referred to as the tangent bundle, denoted by TM. Similarly, the set of pairs (I., 8z. such that (s2, {x) 0 for every & E TaM is called the normal bundle, denoted by N.M Let x(M) denote space of vector fields on M and V : TM x TM- + T.M, (E, 7) - Ven E TM denote the Levi-Civita connection manifold M. We adapt the Euclidean metric the embedded to denote the inner product and norm, respectively.
[
manifold and use (5)) and
Geodesics on the manifolds are generalizations of lines in Euclidean space, curves with constant speed that are locally distance-minimizingg Consequently, we can define the distance between two points on the manifold as the length of geodesic 7, dist(r. y) == inf,, J (t)](t) where 7() x and (11 = y. With the help of geodesics, we next introduce the exponential mapping and retraction operations. From an optimization perspective, both exponential mapping and retraction are used to traverse manifold M. The exponential mapping on a Riemannian manifold defines a geodesic on the manifold 7()= = Expz (Iv) and the distance between x and (x), is dist(ar Exp, (v)) = |||| Exponential mappings are hard to compute in general; as mitigation, retractions Retr, (-) T.M M are introduced as first-order approximations of exponential mappings and are easier to compute. Based on the definition of distance, we denote by B(x, 6) == {y E M dist(x, 3) < 8) ball centered at z with radius 8 32
Given that the tangent space T.M is defined with respect to point x, vectors defined in different tangent spaces are not directly comparable. To this end, we can use the notion of parallel transport, which is a linear, isometric mapping from one tangent space to another, defining a way to transport the local geometry along a curve. We denote parallel transport along the minimizing geodesic by Pa : T.M- + M, which preserves the inner products such that (u, v) (P2, (u), P2 (v))

---

for u, U E T.M. As a computationally efficient alternative to parallel transports, we can use vector transports M specific case of which projection. For x, E M the orthogonal projection onto tangent space can be defined as Projr, T,M - TyM, mapping & E TrM to Proir, (E) E MyM such that (Projr,,M((5)4 vector transports (and projections) are not necessarily isometric, requiring more delicate analysis.
Projr, (M)) = O. While more efficient than parallel transports,
2.2 Goldstein Stationarity on Riemannian Manifolds
Using concepts defined in Riemannian geometry, we next provide the following notions for optimiza- tion on manifolds. As result of Rademacher's 's theorem and local equivalence of the Riemannian distance with Euclidean distance in a chart, every Lipschitz function defined on a Riemannian
manifold M is differentiable almost everywhere with respect the Lebesgue measure M (32
Definition 2.1. We define the Riemannian subdifferential of f at I, denoted by 0f(x) conv ( grad (zi) m - I, 2 E 2 C T,M, where Q2 {r E M is differentiable 2} and conv denotes the convex hull operator.
Here, g()) denotes the Riemannian gradient, defined as the unique tangent vector that satisfies df(=)<< (gradf(z). {) for all & E T.M. Although the sequence (xi) lies in different langent spaces MT. i, the limit lim (x)) can still be defined in a weak sense. Specifi- cally, it is characterized as the vector satisfying lim fgra X Xxx)) + (grad X (x)) for any smooth vector field X on M [23] For smooth function f defined on an embedded subman- ifold in the Euclidean space ((r) = Projr, ( fV)(z)) This also holds for the subdifferential sets and the Riemannian subdifferential set is the projection of the Euclidean subdifferential set onto
the tangent space at xr
Definition 2.1 extends the notion of the Clarke subdifferential to the Riemannian setting, following prior work such as 23 BT. Among the various subdifferential concepts, the Clarke subdifferential particularly useful due to its inclusivity and well-behaved analytical properties, which facilitate the study of convergence in nonsmooth optimization. We next provide the definition for d-subdifferential in the neighborhood of point x.
Definition 2.2. Let f be a Lipschitz continuous function on M. ô-subdiffereenial of x E M is defined as (x == el conv(["g. (0)()) y E el B(x, 8)}, where cl denotes the closure.
Different from the Euclidean 5-subdifferential set, the Riemannian 8-subdifferential requires transport operation Pg.. since the tangent spaces are not identical. Next, we introduce the Riemannian version of Goldstein stationarity.
Definition 2.3. Given Lipschitz continuous function f M + R, a point x E .M and 5 >> 0 denote f == min(llgll : g e Ög (z)). point x called (6, -)-stationary point of f-) [[grad((=)]] <.
This definition generalizes the Euclidean Goldstein stationarity to the Riemannian setting. The main difference is that parallel transport operations and Riemannian subdifferentials are used in 5-subdifferential set due to Riemannian geometry.
Let X and Y be vector fields on M. Since M C RR is an embedded submanifold of Euclidean space equipped with Euclidean metric, X and Y can be extended in R". Applying ambient covariant derivative V and decomposing it into tangential and normal components gives Vx (VxY)T (VxY)= The second fundamental form
4 is II (LMM)x((M) - +[N given by II (V where T(NM) denotes the space of smooth normal vector fields.
2.3 Technical Assumptions
We now introduce a series of assumptions about the problem setting, all of which are considered standard in the relevant literature and are needed for our analytical results. We have the following assumption the manifold and its second fundamental form.
Assumption 2.4. We assume that the manifold M is an embedded submanifold of the Euclidean space and that the norm of the second fundamental form is bounded by C for all unit vectors we have [[)()))))) || < C. This implies that the curvature
E, n E TM, i.c., for all |||| ||7|||
5

---

tensor R(X, Z is bounded by constant Ke, i.e., R((XY)) I Ke | sectional curvature is bounded by a constant K2 for any vector fields X, Y. E (.M).
Z|| and the
The above assumption the bounded second fundamental form connects the extrinsic and intrinsic geometries. As discussed in [4], a stronger condition than bounded sectional curvature, but required to measure the extrinsic difference on vectors, caused by transport operations. For more discussion, see Appendix [ In Riemannian optimization, variable updates may involve exponential mappings and retractions. Although exponential mapping has theoretically favorable properties, retractions are preferred in practice due to their computational efficiency. We have the following assumptions retraction curves.
Assumption 2.5. For the retraction curve Retx,(tE) with E T,,, we assume that
di Retr, [t)) < ||<|| and Retr, (t5) - C*||e[|?
where C" is constant depending the manifold properties.
Since retractions are approximations exponential mappings, the above assumption can be thought as the cost of applying retractions instead of exponential mappings. It is presented in simplified form for analytical clarity; however, the proposed implementation can be readily extended to more general retraction- based settings, such as projection- based or smooth first-order retractions (see Appendix [). Assumption [2.3 is satisfied by various matrix manifolds and commonly used retraction curves. In particular, for exponential mappings on any manifold M, the first condition holds with equality, while the second condition holds with C' C. where C' is defined in Assumption 2.4 On the Stiefel manifold Sl n)) [X R=xP: X Ip). for polar decomposition retraction
Retrx (tt) (X + (4, + T)) Assumption 2.5 holds with C' 1 (see Appendix B
Next, we provide the following standard assumptions on the objective function, applicable to a diverse range of commonly used objectives.
Assumption 2.6. We assume that the objective function has the form f(z) = E,, [F(r, v/), where denotes the random index. The stochastic component of the function F(-.) M R is L(v) Liissiitt for any v, i.e., it holds that
[F(z, v) - Fly, m) S div) y), for any y M. L(v) has a bounded second moment such that [v) S L22 We also assume that f is lower bounded on M, i.e., infrem fxx > -00
Assumption 2.7. We assume that the stochastic Riemannian oracle returns unbiased estimates, i.c.. Igaad F ((x, v)] gradf(x))
Furthermore, assume that the second moment of the stochastic gradient is bounded such that E2 [[gradF((x, vx, =)| G2, and we denote its variance by o².
Assumption 2.7 is standard in stochastic optimization with first order oracles 24
With the definitions
and assumptions provided above, introduce the following lemma, which extends the result of 43 Theorem 4.1] on geodesic paths to broken geodesic paths.
Lemma 2.8. Suppose M is an embedded submanifold of the Euclidean space with second fundamental form bounded by C. Lety: [0, t] - MM be a broken geodesic (a piecewise smooth curve with finite number of curve segments, each of which is a geodesic) and v E T. Then, we have
[P) Projr (r < C|]o|[length(?),
where the parallel transport computed along the path 7-
This result allows us to measure the distortion between an intrinsic parallel transport operation and an extrinsic projection operation the manifold. We note that for the Euclidean case, the second fundamental form is 0. For the extension of Euclidean algorithms to the Riemannian setting, Lemma 2.8 characterizes the extra terms raised by the Riemannian geometry.
For sequence of points S, = (= let us define the parallel transport operator over S. as Ps, Pg_ a. o P - o... o P2 and its inverse operator as (P3,)-1. In general. (gradf()) II difficult to compute directly. The following lemma provides an analyzable upper bound on f which will be used in our analysis.

---

Lemma 2.9. Let Assumption
2.4 hold. For sequence of points { which satisfies
dist(x,, Fz+1) < Vt E {0, (0....... T 1}, a set of gradient vectors V, = gradf(w;) Tw,
with Vr I L. 1ist( wx) - D, and point y that satisfies dist(w,, y) S 8 = DT, Vt
{0, T 1), we have that
T-1
ggradf -
Σ t=0
(P'..
P Ze+1 (V)) (V.) 3LLC.. )-
The summands all live in T2 M, so they can be summed. In the following sections, we design our algorithms and provide analytical bounds for the right-hand side of Lemma 2.9
First Order Setting
In this section, we develop algorithms to find (6, c)-stationary points of nonsmooth nonconvex stochastic objectives and provide theoretical guarantees for their finite-time convergence rates. Our algorithms adapt the O2NC conversion of [13] to the Riemannian setting, and instead of directly implementing online Riemannian optimization, our specific formulation of the problem allows us to utilize techniques of Fuclidean online algorithms with transport operations between tangent spaces.
3.1 The Structure of RO2NC versus O2NC
To understand O2NC, let us observe that for any algorithm with the update rule 1e411 It A., one can write ((++1) = f(x;)) + (A,, V.) where V, = So Vf(z, + sA,) For Euclidean problems, the O2NC approach proposed by 13 designed an algorithm to overcome the nonconvexity by observing that
- Σ (a. A. u) -v.. Σ (ge, u):
where A, can generated via an online learning algorithm and gr are the stochastic gradients provided to the online learning algorithm. The above equation holds for any in hindsight, so the first summation corresponds to the regret of the online algorithm. For the last term we have freedom to select a suitable u. Specifically, the selection of u = - D DΣ E[gel/1) ET=1 - EEg.]]l with a suitable parameter D facilitates the Goldstein stationarity analysis. To have an efficient Riemannian adaptation for the O2NC algorithm, we encounter some major challenges:
(i) Since the iterates constrained be the manifold, we must use retractions in the updates, so we have Ti+1 = Retr,, (A,). Also, for the gradient evaluation part, we use the update wa = Retrz, (sA.) for randomly selected iterates are connected with a line segment as Ø++1 = 2j + A., parameterized to have zero acceleration. However, for manifolds with general retraction eurves, need to handle additional terms that contain the velocity and acceleration of the retraction curves.
unif 1]. In the Euclidean setting, two consecutive
(ii) Unlike the Euclidean case where setting different variables belong to various tangent spaces. Performing calculations using these variables necessitates operations such parallel transport or projection, making the analysis more challenging compared to its Euclidean counterpart. This affects both algorithm design and technical analysis. For the design of RO2NC, we first consider the parallel transport in Section 3.2 and then consider a more efficient version of our algorithm with projections Section 333] As for the analysis cannot simply use the benchmark u as in [33, and must cleverly design optimal elaborated in the next section.
directly add and subtract vectors, in the Riemannian
3.2 RO2NC with Parallel Transport
In this section, we consider the RO2NC algorithm where the actions A, are updated via parallel transport operations. The updates are similar vein to online gradient descent and allow us to rework the Euclidean regret analysis with the use of parallel transports. The algorithm is formally stated in Algorithm| [ and works based on an inner loop indexed by (iteration) and an outer loop indexed by k (epoch). In this section, except in the algorithm outline, omit & for notational convenience.
7

---

Algorithm Riemannian Online to NonConvex (RO2NC)
Input: K E N. T E N, initial point To,r E M, clipping parameter D, step size D/GVT for 1 to K do
Initialize 2 = 1,7 As.0 =
for = 0 to T
do
#k,++1 = Retr.., ( (Ak,t)
~ 10,
Wk.t Rotx (R,,)
get gradient fk.t = grad F FUTTE, () where PR,t is random index (based data) if Using Parallel Transport then
Ik,t Pg Wk.e ".,,44 (Ik,t) E T 22, M
set Ar,441 = Pg
PR (ARie)
79,,
end if
if Using Projection then
set 4,,1+1 Proir... M (k, 79k,e)
end if
clip 4k,t41 on the convex BT. k,,4 M (D)
end for Set Wy to L.
end for
Sample Wout unif Wi,..., WK
Output: Wont
At the 1-th iteration in each epoch, we parallel transport both A, and gt. to update A clip( Pg mess (At) ng?)); where o is the parallel transported version of Jt- We have the following convergence result for RO2NC.
Theorem 3.1. Let 6, E (0, 1) and suppose that Assumptions 2.4.2.2.66 2.7 hold. Running Algorithmm
with parallel transports for N = KT rounds T -(6N) and D 8/T gives an output that satisfies the following inequality
Afldrraff [| S C1(8N) 35TC2,
where constants C1, C2 given in the Appendix
e Remark 3.2. To find a (8, sttatiooaayy point, we can choose = min 6LC, S å to get a (8', e)-staiionary point. Then, choosing N 0 is sufficient for E|] Er]ggrad/ (Wout) I1a] S e.
Theorem 3. indicates that for nonsmooth nonconvex optimization on Riemannian manifolds, RO2NC has the same complexity as its Euclidean counterpart [3] The distortion caused by the curved geometry can be controlled with suitable selection of parameters. Similar to the Euclidean setting, for smooth objectives, an e-taationary point can be found in (c--)) iterations by selecting Oc)).
A key innovation in the analysis of Theorem
3.1 is the choice of
Σ 0 (Pg. ) Po #-+1 (V,)
Ur = PP (-D
(PS.
P
(V,)
where V, = E[g.]. The main idea behind this selection is to transport the gradient vectors along the path {2T, T1, 21) to create a base vector un and then choose u = Ps. (uo). Although the best actions for Algorithm I are time-dependent, they still be analyzed with parallel transports.
3.3 RO2NC with Projection
We now address the case where parallel transport operations are costly and RO2NC use projections instead. While more efficient, the introduction of projections bring forward technical challenges as they lack the isometry property (unlike parallel transports). In this case, at the 1-th iteration each epoch, we calculate A, 19: in the ambient space and project it to the tangent space of M at iterate Jt-1 to obtain A The convergence of Algorithm with projection operations presented the following theorem.

---

hold. i with projections for N KT rounds with T O(ôN)ā and D 8/T gives output that satisfies the following inequality
Theorem 3.3. 5, c E (0, and suppose that Assumptions 2.4 2.42.5 hold. Running Algorithm
S Cs(DN) (lllrad
C28 N +LC,
where constants C3. C2 are given in Appendix E
Remark 3.4. Theorem 3.3 implies that N
O 0(8-1cc0 and 8 = O(c) is sufficient to have ||s I e, since 8 1 and d < (6N)-3 order-wise. So, follow the same argument in Remark
B|]
Theorem 3.3 shows that the same complexity can be achieved using projections instead of parallel
transport operations, greatly improving the efficiency of RO2NC from an implementation perspective. While the implementation of the algorithm relies solely on projection operations, the analysis makes use of parallel transport to upper bound the term [grrad((w (Wont) )lg in our theorem.
The projection-bas based analysis allows us to first calculate u - -D D'D V E/= in the ambient space and then project it back to the tangent space to get u4 = ProjT, M (u), which again highlights key novelty in our analysis.
2-1 Vell directly
4 Zeroth Order Setting
In this section, we consider the case where gradient queries unavailable and only noisy function evaluations can be obtained. In the context of online learning, this is analogous to a system with two-point bandit feedback. One common approach to address the nonsmooth problems in this setting is to derive a gradient estimator ga based on function values and use that the gradient-based algorithms replacement of grad F.
For zeroth order optimization in the Euclidean setting [37 the gradient estimator constructed with F(x=ōu, v),, where is uniformly sampled from unit sphere. In the Riemannian setting, + 8u is replaced with Exp,, (fu), and u is sampled uniformly from a sphere in T.M. Then, the Riemannian gradient estimator is given as follows,
d
g8 (x)
(ōu), v) F(Exp,(-Ou) ou), D)),,
25
where d is the dimension of T.M. Two major problems arise from the Riemannian formulation: (i) In the Euclidean setting, we have V //((x) EV.VV/Ce fxx+(x+22 + 5u)] E (z)()), which implies that the expectation of the gradient estimator is included in the Goldstein subdifferential set 45) However, in the Riemannian setting, stating the relation between [x8]] and fzf is a challenge in itself. (ii) Also, the geometric relation O (x)) S Ou+ef(x) used in the Euclidean zeroth order analysis 37 does not hold in the Riemannian setting due to distortion caused by the manifold geometry.
We first define h2(x) == f (u)dz_ where pz is a uniform measure over By, (0) C T.M. By analyzing the relationship between gradh (x)) and 0s.(rr) in Lemma A.5 we introduce the following lemma to address the above two challenges.
Lemma 4.1. Consider point y and set of points {T=) which satisfy dist(y, S 2- The gradient estimator ga satisfies Em[gg(x::] E 0sJ(xx)) + (r,,M( and P2.. (3,((1)) c 0yf(y) + BI.M L2C, where + denotes the Minkowski sum of two sets, C denotes the bound on the second fundamental form (Assumption 2.4) and K2 bounds the sectional curvature of the manifold.
With the help of Lemmas 4.1 and A.5
we bound (woud) [|s in terms of ||gradh g (wout) )14 and we then employ that inequality for the following theorem, providing the finite-time convergence guarantee using the zeroth order gradient estimator.
Theorem 4.2. Let ö, E (0, 1) and suppose that Assumptions 2.42.5 2.6 hold. Running Algorithm for N = KT rounds with T = O(8N) and D = 8/T using the zeroth order gradient estimator in equation gives an output that satisfies
Elllgrad (w |l Cs(8N) 8T.Co.
where Cs and Co are given in Appendix E

---

First Order Oracle
Zeroth Order Oracle
parallel D 3.0e004 y: 1.0c 05
projection 5.0e-04 n: 5.0e-07
projection 0:
paralle' ::00 04
07
parallel D 3.0e05 v: 3.0e-7
projection 3:0000:0 ry: 1.0e-00
0.8
projection D 5.0+05 5.0+07
projection 1:00-:04
1.0-07
paralla D: q
paralle 3.0e-64 q 1:0e066
Gradien Nom
projection D. 1.0c044 1.0-077
paralle 1.0e64 1.c-77
Gralient
0.4
100000
Etrations
leraaioos
Figure 1: Evaluation of gradient norms both settings; D: clipping parameter, vy: step size.
The theorem considers Algorithm I with parallel transports, but a similar result can be obtained with projections. In our analysis, we show that although extra terms arise due to the introduction of zero order gradient estimator and the approximation to Goldstein subdifferential sets, these additional terms can be controlled by a careful adjustment of 5. Consequently, the overall iteration complexity with respect to (ô,e) can maintained in the zeroth order setting.
Numerical Experiments
We provide the following numerical experiments validate our results.
Model and Setup. We consider the sparse principal component problem defined on the Euclidean unit sphere Sm-1 in R" The parallel transport operations have closed-form solutions spheres. The objective function can written as min
Ax + | ||] where = E/vv' and y ~ (), is sampled from a multivariate Gaussian distribution. For RO2NC, we choose our retraction curves to be Retr, (v) (x + w)/ || + o/|. and we use exponential mappings for calculating the gradient estimator in ZO-RO2NC.
Evaluation and Results. Since the direct evaluation of the Goldstein subdifferential and f requires calculation over convex hull, which is highly impractical, we instead as an upper bound.
evaluate | (P
P2 m.. (gradf(w:) (grdd
In our experiments for RO2NC, we illustrate the decay of the gradient norms. We run Algorithm
I using both parallel transport and projection operations for K 500 epochs, each consisting of
T 200 iterations. Convergence
the algorithms depends on the selection parameters D and n. For both settings, 17 is chosen orders of magnitude smaller than D. and the plot is reported in Fig.
1 We can see that the performance of the projection approach is comparable with that of parallel transport approach. Optimization with the zeroth order oracle is more sensitive to the selection of parameters and the convergence slower than the first order setting, but with suitable choice of parameters ZO-RO2N2 indeed converges.
6 Conclusion, Limitations, and Future Work
We addressed the finite-time analysis of nonsmooth, nonconvex stochastic Riemannian optimization. We proposed the RO2NC algorithm, which guaranteed find the Riemannian extension of (ò, e)- Goldstein stationary points with 0 sample complexity. When gradient information is unavailable, we introduced ZO-RO2NC with a zeroth order gradient estimator, which also achieves optimal sample complexity. While our stationarity condition is defined via parallel transport of Clarke subdifferential, alternative notions, such different transport maps or subdifferentials, may also be considered. Furthermore, a deeper analysis of curvature effects and their role in optimality remains an open direction. Finally, designing adaptive algorithms that can exploit curvature information more effectively can be an interesting problem for future research.
10

---

Acknowledgments
The authors gratefully acknowledge the support of NSF Award as well as Northeastern TIER 1 Program for this research.
References
[1] P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. Princeton University Press, 2008
[2] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neural networks.
In International conference on machine learning, pages 1120-1128. PMLR, 2016.
[3] Silvere Bonnabel. Stochastic gradient descent riemannian manifolds. IEEE Transactions Automatic Control, 58(9))2217-22299 2013.
[4] Pierre B Borckmans, S Easter Selvan, Nicolas Boumal, and P-A Absil. A riemannian subgradient algorithm for economic dispatch with valve-point effect. Journal of computational and applied mathematics, 255:848-866 2014.
[5] Nicolas Boumal. An introduction to optimization smooth manifolds. Cambridge University Press, 2023.
[6] Hengchao Chen and Qiang Sun. Decentralized online riemannian optimization with dynamic environments. arXiv preprint arXiv:2410.05/28, 2024.
[7] Shixiang Chen, Alfredo Garcia, Mingyi Hong, and Shahin Shahrampour. Decentralized rie- mannian gradient descent on the stiefel manifold. In International Conference on Machine Learning, pages 1594-1605, PMLR, 2021.
[8] Shixiang Chen, Alfredo Garcia, and Shahin Shahrampour. On distributed nonconvex optimiza- tion: Projected subgradient method for weakly convex problems in networks. IEEE Transactions on Automatic Control, 67(2):662-675, 2021.
[9] Shixiang Chen, Shiqian Ma, Anthony Man-Cho So, and Tong Zhang. Proximal gradient method for nonsmooth optimization the stiefel manifold. SIAM Journal Optimization, 30(1):210-239, 2020.
[10] Shixiang Chen, Shiqian Ma, Anthony Man-Cho So, and Tong Zhang. Nonsmooth optimization over the stiefel manifold and beyond: Proximal gradient method and recent variants. SIAM Review, 66(2):319-352, 2024.
[11] Anoop Cherian and Suvrit Sra. Riemannian dictionary learning and sparse coding for positive definite matrices. JEEE transactions on neural networks and learning systems, 28(12):2859- 2871, 2016.
[12] Christopher Criscitiello and Nicolas Boumal. An accelerated first-order method for non-convex optimization on manifolds. Foundations of Computational Mathematics, 23(4): 1333-1999,, 2023.
[13] Ashok Cutkosky, Harsh Mehta, and Francesco Orabona. Optimal stochastic non-smooth non- convex optimization through online-to-non-conve conversion. In International Conference Machine Learning, pages 6643-6670. PMLR, 2023.
[14] Damek Davis and Dmitriy Drusvyatskiy. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):207-233) 2019.
[15] Glaydston de Carvalho Bento, João Xavier da Cruz Neto, and Paulo Roberto Oliveira. A new approach to the proximal point method: convergence on general riemannian manifolds. Journal of Optimization Theory and Applications, 168:743-755, 2016.
[16] Kangkang Deng, Jiang Hu, and Zaiwen Wen. Oracle complexity of augmented lagrangian methods for nonsmooth manifold optimization. arXiv preprint 2441v2240..05121, 2024.

---

[17] Kangkang Deng, Zheng Peng. and Weihe Wu. Single-loop ( stochastic smoothing algorithms for nonsmooth riemannian optimization. arXiv preprint arXiv:2505.09483 2025.
[18] Gunther Dirr, Uwe Helmke, and Christian Lageman. Nonsmooth riemannian optimization with applications to sphere packing and grasping. In Lagrangian and Hamiltonian Methods for Nonlinear Control 2006: Proceedings from the 3rd IFAC Workshop. Nagoya, Japan, July 2006, pages 29-45. Springer, 2007.
[19] Alan Edelman, Tomás A Arias, and Steven T Smith. The geometry of algorithms with or- thogonality constraints. SIAM journal on Matrix Analysis and Applications, 20(2):303-353, 1998.
[20] Yanhong Fei, Yingjie Liu, Chentao Jia, Zhengyu Li, Xian Wei, and Mingsong Chen. A survey of geometric optimization for deep learning: from euclidean space to riemannian manifold. ACM Computing Surveys, 57(5):1-37, 2025.
[21] Yanhong Fei, Yingjie Liu, Xian Wei, and Mingsong Chen. O-vit: Orthogonal vision transformer. arXiv preprint arXiv: 12133, 2022.
[22] Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex opti- mization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
[23] P Grohs and S Hosseini. E-subgradient algorithms for locally lipschitz functions on riemannian manifolds. Advances in Computational Mathematics, 42(2):333-360) 2016.
[24] Philipp Grohs, Martin Holler, and Andreas Weinmann. Handbook of Variational Methods for Nonlinear Geometric Data. Springer, 2020.
[25] Philipp Grohs and Seyedehsomaych Hosseini. Nonsmooth trust region algorithms for locally lipschitz functions riemannian manifolds. IMA Journal of Numerical Analysis, 36(3):1167- 1192, 2016.
[26] Chang He, Zhaoye Pan, Xiao Wang, and Bo Jiang. Riemannian accelerated zeroth-order algorithm: Improved robustness and lower query complexity. In International Conference on Machine Learning, pages 17972-18009. PMLR, 2024.
[27] Gennadij Heidel and Volker Schulz. A riemannian trust-region method for low-rank tensor completion. Numerical Linear Algebra with Applications, 25()::2177 2018.
[28] Najmeh Hoseini Monjezi. Soghra Nobakhtian, and Mohamad Reza Pouryayevali. A proximal bundle algorithm for nonsmooth optimization on riemannian manifolds. IMA Journal of Numerical Analysis, 43(1)2293-3 2023.
[29] Reshad Hosseini and Suvrit Sra. Matrix manifold optimization for gaussian mixtures. Advances in neural information processing systems, 28, 2015.
[30] Seyedehsomaych Hosseini, Boris Sholimovich Mordukhovich, and André Uschmajew. Nons- mooth optimization and its applications. Springer, 2019.
[31] Scyedehsomaych Hosseini and MR Pouryayevali. Generalized gradients and characterization of epi-lipschitz sets in riemannian manifolds. Nonlinear Analysis: Theory, Methods & Applications, 74(12):3884-3895 2011.
[32] Seyedehsomayeh Hosseini and André Uschmajew. A riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM Journal on Optimization, 27(1) 27(1):133-189 2017.
[33] Wen Huang and Ke Wei. Riemannian proximal gradient methods. Mathematical Programming. 194(1):371-413, 2022.
[34] Pratik Jawanpuria, Mayank Meghwanshi, and Bamdev Mishra. Geometry-aware domain adaptation for unsupervised alignment of word embeddings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 3052-3058, 2020.
12

---

[35] Michael Jordan, Tianyi Lin, and Emmanouil- Vasileios Vlatakis- Matakkis-Garagkoumiii First-order algorithms for min-max optimization in geodesic metric spaces. Advances in Neural Information Processing Systems, 35:6557-65744 2022.
[36] Jungbin Kim and Insoon Yang. Accelerated gradient methods for geodesically convex optimiza- tion: Tractable algorithms and convergence analysis. In International Conference on Machine Learning, pages 11255-1122 1182.. PMLR, 2022.
[37] Guy Kornowski and Ohad Shamir. An algorithm with optimal dimension-depenneence for zero- order nonsmooth nonconvex stochastic optimization. Journal of Machine Learning Research, 25(122):1-14, 2024.
[38] Artiom Kovnatsky, Klaus Glashoff, and Michael M Bronstein. Madmm: generic algorithm for non-smooth optimization on manifolds. In Computer Vision-ECCY 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part V 14, pages
680-696. Springer, 2016.
[39] Rongjie Lai and Stanley Osher. A splitting method for orthogonality constrained problems. Journal of Scientific Computing, 58:431-449 2014.
[40] Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-free optimization methods. Acta Numerica, 28:287 404, 2019.
[41] John M Lee. Introduction to Riemannian manifolds, volume 2. Springer, 2018.
[42] Jiaxiang Li, Krishnakumar Balasubramanian, and Shiqian Ma. Stochastic zeroth-order rieman- nian derivative estimation and optimization. Mathematics of Operations Research, 48(2): 183- 1211, 2023.
1883-
[43] Jiaxiang Li, Krishnakumar Balasubramanian, and Shiqian Ma. Zeroth-order riemannian aver- aging stochastic approximation algorithms. SIAM Journal Optimization, 34(4):3314 2024.
[44] Jiaxiang Li, Shiqian Ma, and Tejes Srivastava. A riemannian admm. arXiv:2211.02163, 2022.
arXiv preprint
[45] Tianyi Lin, Zeyu Zheng, and Michael Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35:26160-266 26175, 2022.
[46] Alejandro Maass, Chris Manzie, Dragan Nesic, Jonathan Manton, and Iman Shames. Tracking and regret bounds for online zeroth-order euclidean and riemannian optimization. SIAM Journal on Optimization, 32(2):445-46) 2022.
[47] Oren Mangoubi and Aaron Smith. Rapid mixing of geodesic walks on manifolds with positive curvature. The Annaly of Applied Probability, 28(4):2501-2543, 2018
[48] David Martínez-Rubin Global riemannian acceleration in hyperbolic and spherical spaces. In International Conference on Algorithmic Learning Theory, pages 768-826 826. PMLR, 2022.
[49] David Martínez-Rubiä and Sebastian Pokutta. Accelerated riemannian optimization: Handling constraints with a prox to bound geometric penalties. In The Thirty Sixth Annual Conference on Learning Theory, pages 359-393. PMLR, 2023.
[50] Zheng Peng, Weihe Wu, Jiang Hu, and Kangkang Deng. Riemannian smoothing gradient type algorithms for nonsmooth optimization problem on compact riemannian submanifold embedded in euclidean space. Applied Mathematics Optimization, 88(3):85, 2023.
[51] Emre Sahinoglu and Shahin Shahrampour. An online optimization perspective on first-order and zero-order decentralized nonsmooth nonconvex stochastic optimization. In 41st International Conference on Machine Learning, volume 235, pages 43043 43059. PMLR, 2024.
[52] Emre Sahinoglu and Shahin Shahrampour. Decentralized online riemannian optimization beyond hadamard manifolds. arXiv preprint arXiv:2509.07779, 2025.
13

---

[53] Emre Sahinoglu and Shahin Shahrampour. Online optimization on hadamard manifolds: Curvature independent regret bounds on horospherically convex objectives. arXiv preprint arXiv:2509. /236, 2025.
[54] Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance re- duced gradient algorithm with retraction and vector transport. SIAM Journal on Optimization, 29(2):1444 1422-442, 2019.
[55] Suvrit Sra and Reshad Hosseini. Geometric optimization in machine learning. Algorithmic Advances in Riemannian Geometry and Applications: For Machine Learning, Computer Vision, Statistics, and Optimization, pages 73-91, 2016.
[56] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere ii: Recovery by riemannian trust-region method. IEEE Transactions on Information Theory, 63(2):885 914,, 2016.
[57] Youbang Sun, Shixiang Chen, Alfredo Garcia, and Shahin Shahrampour, Retraction-fre decen- tralized non-convex optimization with orthogonal constraints. arXiv preprint arXiv:2405.11590. 2024.
[58] Yue Sun, Nicolas Flammarion, and Maryam Fazel. Escaping from saddle points on riemannian manifolds. Advances in Neural Information Processing Systems, 32, 2019.
[59] Bokun Wang, Shiqian Ma, and Lingzhou Xue. Riemannian stochastic proximal gradient methods for nonsmooth optimization over the stiefel manifold. Journal of machine learning research, 23(106):1-33, 2022.
[60] Hongye Wang. Zhaoye Pan, Chang He, Jiaxiang Li, and Bo Jiang. Federated learning on rieman- nian manifolds: A gradient-free projection-baset approach. arXiv preprint arXiv:2507.22883 2025.
[61] Jiayun Wang. Yubei Chen, Rudrasis Chakraborty, and Stella Yu. Orthogonal convolutional neural networks. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 1 11505-1155 -1515, 2020.
[62] Xi Wang. Zhipeng Tu, Yiguang Hong, Yingyi Wu, and Guodong Shi. Online optimization over riemannian manifolds. Journal of Machine Learning Research, 24(84):1-67, 2023.
[63] Melanie Weber and Suvrit Sra. Projection-free nonconvex stochastic optimization on riemannian manifolds. IMA Journal of Numerical Analysis, 42(4):3241-327)) 2022.
[64] Melanie Weber and Suvrit Sra. Riemannian optimization via frank-wolfe methods. Mathemati- cal Programming, 199(1): 5:525-556, 2023.
[65] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference learning theory, pages 1617-1638. PMLR, 2016.
[66] Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie. Complexity of finding stationary points of nonconvex nonsmooth functions. In International Conference on Machine Learning, pages 11 11173-11188 PMLR, 2020.
[67] Junyu Zhang, Shiqian Ma, and Shuzhong Zhang. Primal-dual optimization algorithms over ric- mannian manifolds: an iteration complexity analysis. Mathematical Programming, 184(1):445- 490, 2020.
[68] Peiyuan Zhang, Jingzhao Zhang, and Suvrit Sra. Sion's minimax theorem in geodesic metric spaces and riemannian extragradient algorithm. SIAM Journal on Optimization, 33(4):2885- 2908, 2023.
[69] Qingru Zhang, Minshuo Chen, Alexander Bukharin, Pengcheng He, Yu Cheng. Weizhu Chen, and Tuo Zhao. Adaptive budget allocation for parfmeter-efficient fine-tuning. In The Eleventh International Conference on Learning Representations, 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Our main contributions in this work are referenced high level in the abstract, expanded upon the introduction, and developed in detail across Sections and
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed limitations and future work the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
We have stated our theoretical assumptions in Section 2.3.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: This mostly a theory work, and experiments are for the proof of concept. We have provided the choice of all hyperparameters for reproducibility.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification: The anonymized code for the numerical experiments is available at the follow- ing
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
ioc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
ssicnlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The same justification as Q4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Error bars do not apply to the convergence of our algorithms. We do not make comparisons.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The experiments are toy examples. They can be run on laptop.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
We read the link and made sure the paper conforms with all components of ethics.
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theory work at the interface of online and Riemannian optimization. We do not anticipate any negative societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
There are no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We did not LLMs for the derivation of results.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
21


Reviews:
[{"review_id": "yDJwRYTN5U", "reviewer": "Reviewer_eVKg", "summary": "This paper presents finite-time results for optimizing nonconvex, nonsmooth functions over Riemannian manifolds. The approach is built upon the recent online-to-nonconvex framework and existing work in Riemannian gradient sampling. The authors also discuss the zero-order case, drawing on known results from the Euclidean setting. While the core ideas may not be surprising, difficulties can arise when generalizing analysis from the Euclidean to the manifold setting.", "questions": "See above.", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "I have two technical questions:\n* In Assumption 2.7, I don't understand the rationale behind the notation grad F(x,\\nu), which seems not defined. If it is meant to be the Riemannian gradient of function x \\mapsto F(x, \\nu) for fixed \\nu, then one possible issue is that why we can write E_\\nu [grad F] = grad f. This implicitly assumes F(., \\nu) is differentiable at x for D-a.s. \\nu, needs a careful justification, and may not be true even in the Euclidean setting.\n* Another issue is on the evaluation of g_{k,t} in Algorithm 1. How can you ensure the function F(c, v_{k,t}) is actually (Riemannian) differentiable at the point w_{w,t}? If it is not, then such an evaluation seems rather intractable. This issue may be due to the fact that the curve s_{k,t} \\mapsto Retr_{x_kt}(s_{k,t} \\Delta_{k,t}) is not sufficiently generic, which allows F(., \\nu_{k,t}) to be non-differentiable at any point along it.\n\n\nOther comments:\n* the objective f is not defined in Eq.1\n* L55: weakly convexity -> weak convexity\n* L157: I cannot see why B(x,\\delta) is an open ball.\n* Definition 2.1. It may be better to clarify the meaning of \\lim_l grad f(x_l), since {grad f(x_l)}_l are in different tangent spaces.\n* For the known facts mentioned in Section 2.2, it would be better to provide concrete citations for verification and reference; e.g., L178--L182 and L185--L189. \n* Definition 2.3. Why is the function f defined on an Euclidean space?\n* the function f may need to be assumed to be lower bounded on manifold M; otherwise, C1, C3, C5 may not be upper bounded wrt T.\n* In Lemma 2.9, what are {w_t}_t? You may need to define them before using them to define \\nabla_t. Besides, from the proof, you may need additional assumption like dist(w_t, y) <= \\delta. Also, RO2NC is not defined here, hence please try to avoid use that term in the proof.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and evaluation of our paper. \n\n> In Assumption 2.7, I don't understand the rationale behind the notation ...\n\nYes, $\\text{grad} F(x,\\nu)$ is the *stochastic Riemannian gradient* with respect to $x$. We are not sure whether the reviewer is concerned about the \"existence of Riemannian gradient\" or \"its unbiased-ness\", so we provide answers to both:\n\n(i) Existence of Riemannian gradient: Given the Lipschitz continuity of $F(\\cdot,\\nu)$ stated in Assumption 2.6, Rademacher's Theorem ensures that the function is differentiable almost everywhere as noted in lines 178-181. This justifies our use of the Riemannian gradient in the stochastic setting. Please note that *nonsmooth* in our work does not mean that the function is not differentiable at all. It is nondifferentiable for a set that has measure zero (e.g., ReLU function). Our assumption is standard; for example, [11] used the same assumption to analyze the nonsmooth Euclidean setting. \n\n(ii) Unbiased-ness of Riemannian gradient: In stochastic Riemannian optimization, it is a standard assumption that the first-order oracle returns an unbiased estimate of the gradient; please see [39,52]. This assumption is commonly used in the Euclidean setting as well. \n\n[11] Cutkosky, A., Mehta, H. and Orabona, F., 2023, July. Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion. In International Conference on Machine Learning (pp. 6643-6670). PMLR.\n\n[39] Li, Jiaxiang, Krishnakumar Balasubramanian, and Shiqian Ma. \"Zeroth-order Riemannian averaging stochastic approximation algorithms.\" SIAM Journal on Optimization 34.4 (2024): 3314-3341.\n\n[52] Wang, Bokun, Shiqian Ma, and Lingzhou Xue. \"Riemannian stochastic proximal gradient methods for nonsmooth optimization over the Stiefel manifold.\" Journal of machine learning research 23.106 (2022): 1-33.\n\n> Another issue is on the evaluation of $g_{k,t}$ in Algorithm 1...\n\nWe believe this question is partly related to the previous one. As mentioned above, stochastic Riemannian gradient exists almost surely, and the random selection of $s$ is sufficient to ensure differentiability almost surely. This perturbation-based argument is widely adopted in the literature (known as **randomized smoothing**) and provides a practical means to circumvent nondifferentiability in stochastic settings. Please see the following references. \n\n[Ref] A Gradient Sampling Method\nWith Complexity Guarantees for Lipschitz Functions\nin High and Low Dimensions, Davis, Damek, et al. 2022\n\n[Ref] Optimal Stochastic Non-smooth Non-convex Optimization through\nOnline-to-Non-convex Conversion, Cutkosky, Ashok, Harsh Mehta, and Francesco Orabona, 2023\n\n> Other comments:\n\nWe thank the reviewer for their careful assessment of our submission. We agree with the reviewer on all of the comments and address them in detail below:\n\n1,2,3,4,5- The reviewer is correct in these comments. We will revise the text accordingly to address these points.\n\n6- We originally used this definition since the manifold is assumed to be embedded in the Euclidean space, but we agree with the reviewer that it is unnecessary to define $f$ on the Euclidean space. We will revise the notation accordingly to reflect $f:\\mathcal{M} \\to R$.\n\n7- We agree that $f$ must be lower bounded, otherwise minimizing $f$ does not even make sense. This is implicitly assumed, but we will clarify this assumption in the revised version of the paper.\n\n8- The reviewer is correct that referencing the algorithm would improve the clarity of Lemma 2.9. Therefore, in the revised version we will place this lemma after the introduction of algorithm in section 3. Then, the issues related to the use of $w_t$ will be resolved."}, {"review_id": "QRMIBz9Lwg", "reviewer": "Reviewer_nJPA", "summary": "This submission presents the first finite-time analysis of nonsmooth, nonconvex stochastic optimization problems under Riemannian manifold constraints. This fills a theoretical gap where previous literature had only considered smooth or asymptotic cases.\n\nThis submission has made following contributions: \n\n- Goldstein Stationarity on Manifolds: The authors adapt the Goldstein stationarity to the Riemannian setting, forming a meaningful convergence criterion for nonsmooth optimization on manifolds.\n\n- It proposes the RO2NC Algorithm, which is an adaptation of the Online-to-NonConvex method to the Riemannian setting.\n\n- It establishes strong theoretical results: a sample complexity of O(δ⁻¹ϵ⁻³), matching the best-known Euclidean bounds.", "questions": "I am just wondering its performance in realistic applciations.", "limitations": "NA", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am not familiar with this field and cannot comment too much on the strength and weakness. But it seems to me this work is a solid contribution to the optimization community. The following contributes make sense to me:\n\n- Adapting the notion of Goldstein stationarity to the Riemannian setting. \n- Adapting the O2NC algorithm to Riemannian setting. \n- A strong theoretical performance bound is established. \n\n\nWeakness:\n\n- The empirical evaluation for this method is limited. I am sure how it indeed performs in realistic applications.", "was_revised": true, "final_justification": "The authors solve most of the concerns from other reviewers. Thus I will keep the rating", "rebuttal": "> I am just wondering its performance in realistic applciations.\n\nWe thank the reviewer for their evaluation. Several works have investigated the Online-to-Nonconvex Conversion (O2NC) method in Euclidean spaces, with empirical performance demonstrated on real-world datasets, as shown in [47]. In contrast, our work focuses on the Riemannian extension of O2NC, where we validate the performance of RO2NC specifically on the sphere manifold (please see the supplementary materials for experiments). Our work is focused on establishing the ***first iteration complexity on nonsmooth nonconvex stochastic optimization on manifolds***; therefore, our experiments are a proof concept that the proposed algorithm works. However, generally speaking, manifold optimization can be applied to various realistic applications, including on-robot learning (to impose safety constraints) [Ref1] or training neural networks (to provide stability) [Ref2]\n\n\n[Ref1] Liu, P., Bou-Ammar, H., Peters, J. and Tateo, D., 2025. Safe reinforcement learning on the constraint manifold: Theory and applications. IEEE Transactions on Robotics.\n\n[Ref2] Arjovsky, M., Shah, A. and Bengio, Y., 2016, June. Unitary evolution recurrent neural networks. In International conference on machine learning (pp. 1120-1128). PMLR."}, {"review_id": "8TE9KEdaRB", "reviewer": "Reviewer_PRvR", "summary": "This submission studies the problem of minimizing a nonconvex and nonsmooth stochastic function $f$ over a Riemannian manifold $\\mathcal M$. The development is similar to that in the Euclidean in the sense that one must work with the Goldstein subdifferential to obtain meaningful results. Explicitly, the notion of stationarity used herein requires defining the $\\delta$-subdifferential at $x\\in\\mathcal M$ as the closed convex hull of the set $\\cup_{y\\in\\mathrm{cl}(B(x,\\delta))}P^g_{y,x}(\\partial f(y))$ where $P^g_{y,x}$ is the parallel transport taking the tangent space at $y$ to the tangent space at $x$. Then, a point is $(\\delta,\\epsilon)$-stationary once its $\\delta$-subdifferential contains a point which has norm at $\\epsilon$.\n\nWith these definitions in place, the paper enumerates a number of technical assumptions related to 1) boundedness of the second fundamental form of $\\mathcal M$, 2) the quality of the retraction in approximating the exponential mapping, 3) Lipschitz continuity of the deterministic part of the objective, 4) unbiased of the stochastic oracle and boundedness of the second moment of the gradient.\n\nThe proposed method is inspired by the Online to NonConvex (O2NC) approach and uses retractions for the updates to ensure that the iterates remain constrained to the manifold and uses parallel transport or projections to compare points from different tangent spaces. The corresponding algorithm (RO2NC) is studied under both of these settings (parallel transport or projections) yielding similar theoretical guarantees (though different techniques are used in their analysis).\n\nFinally, a zeroth order method is proposed which admits the same overall iteration complexity.", "questions": "1. For Assumption 2.5, the only examples provided are the polar retraction for the Stiefel manifold and the actual exponential mapping. Consequently, this assumption appears to be quite strong. Are there any other examples where this assumption holds?\n\n2. In Assumption 2.7, we require an unbiased estimate for the gradient. Some recent works in the Euclidean setting have managed to bypass the assumption that the oracle always returns the minimal norm subgradient. As such, I wonder if such techniques could be applied in the Riemannian setting as well.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The main problem at hand, nonconvex and nonsmooth optimization over Riemannian manifolds is of a great interest. This is, to my knowledge, the first paper to provide rigorous iteration complexity results and does so with zeroth and first order methods. While the overall approach is similar to O2NC, the modifications required to conform to the Riemannian setting are not straightforward. Furthermore, I find the paper to be well-written overall and the development to be clear.\n\nI believe that the main limitations of this work regard the required assumptions; a concern which I expand upon in the questions below. \nI also note that some experimental validation of this theory is provided, but is contained in the supplement. I believe it would be relevant to include the experiment in the main text.", "was_revised": true, "final_justification": "I am happy with the revisions that the authors have agreed to make. \nI believe there is currently a gap in the literature regarding nonsmooth and nonconvex optimization on manifolds (even in the deterministic setting). While the techniques employed are not so surprising, I believe that this is an interesting contribution.", "rebuttal": "We thank the reviewer for constructive feedback and valuable suggestions.\n\n> I also note that some experimental validation of this theory is provided, but is contained in the supplement. I believe it would be relevant to include the experiment in the main text.\n\nWe should be able to fit the numerical experiments in the main text in the revised version. The main reason we did not do so at first place was that the focus of the paper is on the theoretical analysis, but we can definitely address this given more space.\n\n> For Assumption 2.5, the only examples provided are the polar retraction for the Stiefel manifold and the actual exponential mapping. Consequently, this assumption appears to be quite strong. Are there any other examples where this assumption holds?\n\nIn practice, commonly used retraction curves typically satisfy both of the required conditions. As noted in Lines 229–235, exponential maps and polar decomposition-based retractions are representative examples. Additionally, retractions based on QR decomposition and the Cayley transform on the Stiefel manifold also fulfill these properties. More generally, any second-order retraction of type $\\mathrm{Retr}_x(t\\xi) = x + t\\xi + O(t^2) + o(t^2)$ satisfies the second condition of Assumption 2.5 by construction. The first condition can be interpreted as a form of nonexpansiveness of the retraction map, which is likewise satisfied by the aforementioned examples. Even in cases where the nonexpansiveness condition does not hold exactly, for second order retractions  it can be shown that there exists a constant $c$ such that $d(x,retr_x(v))\\le c||v||, \\forall v : ||v||\\le \\frac{D}{c}$. Therefore, by updating the clipping parameter $D$ as $D/c$, our results remain valid. We will definitely clarify the more general conditions and their implications in the revised version. \n\n> In Assumption 2.7, we require an unbiased estimate for the gradient. Some recent works in the Euclidean setting have managed to bypass the assumption that the oracle always returns the minimal norm subgradient. As such, I wonder if such techniques could be applied in the Riemannian setting as well.\n\nWe appreciate the reviewer’s observation, which raises an interesting point. We found the following recent arXiv work related to the reviewer's question\n\n``Subgradient Regularization: A Descent-Oriented Subgradient Method for Nonsmooth Optimization\" by Li and Cui \n\nbut it seems that this type of oracle is particularly well-suited for deterministic optimization settings. In contrast, our work focuses on stochastic objectives, where randomness plays a central role. In particular, we employ random sampling of gradient evaluation points to address issues arising from nondifferentiability. \nIf there is a particular reference in Euclidean optimization that analyzes the stochastic setting with the suggested oracle, we are more than happy to look into it and explore the possibility of extension to Riemannian setting."}, {"review_id": "fBNSbnAdNP", "reviewer": "Reviewer_9Da2", "summary": "This paper presents an Riemannian adaptation of the Online to NonConvex (O2NC) algorithm, namely the RO2NC algorithm. The proposed RO2NC algorithm introduces appropriate adaptions of retraction and vector transport to implement the essential algorithmic framework of the O2NC on an embedded manifold setting. The finite-time analysis of the proposed RO2NC algorithm for solving the optimization problem $\\arg\\min_{x\\in\\mathcal{M}} f(x)$ on a Riemannian manifold $\\mathcal{M}$ is presented with appropriate assumptions: \n* Assumption 2.4 demands a bounded second fundamental form of the manifold.\n* Assumption 2.5 proposes some constraints on the retraction map as an alternative of the Riemannian geodesic map.\n* Assumption 2.6 and 2.7 propose standard constraints on the non-convex objective function.\n\nIn particular, Assumption 2.4 should be highlighted, as it is a stronger assumption than the typical assumption on a bounded sectional curvature on a manifold, i.e., Assumption 2.4 yields a bounded sectional curvature but not vice-verse. Note that this Assumption 2.4 CANNOT be relaxed in the finite-time analysis. The finite-time analysis is presented on RO2NC algorithm with the following settings:\n* Theorem 3.1: Moving points with a retraction map, and moving tangent vectors with the parallel translation along a minimal geodesic.\n* Theorem 3.2: Moving points with a retraction map, and moving tangent vectors with the orthogonal projection (in the ambient space).\n* Theorem 4.2: Moving points with a retraction map and moving tangent vectors with the parallel translation, with the estimated gradient in use.\n\nThe analysis states that all of the above settings converge (in the sense of an adaptation of the Goldstein Stationarity criterion on the subdifferential set) with the theoretically optimal converging rate. Moreover, the rates seem to be in the same order under appropriate choices of parameters. Some numerical experiments are conducted (with different tuning parameters) on the sparse principal component problem on $n-1$ dimensional sphere. The reported results demonstrate converging trends. However, the converging rates or the finally converged stationary neighborhood are not addressed nor demonstrated.", "questions": "\\textbf{Most important question:} Theorem 2.8 states that \\|\\mathrm{proj}_{T_y\\mathcal{M}}(v) - P_{x,y}^g(v)\\|<C\\|v\\|\\mathrm{dist}(x,y)$ where $\\mathrm{proj}_{T_y\\mathcal{M}}$ is the orthogonal projector in the ambient space and P_{x,y}^g:T_x\\mathcal{M}\\to T_y\\mathcal{M} is the parallel translation along a minimal geodesic from x to y. Note that the parallel translation is path-dependent, i.e., the parallel translation along a different path that connects x and y (other than a minimal geodesic) is different from P_{x,y}^g. However, in the derivations that appeal to Theorem 2.8, e.g., line 863 and line 904, a geodesic polygon with vertices x\\to y_1\\to \\cdots\\to y_n\\to x is involved, where n \\geq 2. Take line 904 as an example that traversals the vertices x\\to y_1\\to y_2\\to x with the vector v parallel translated along the path, Theorem 2.8 should not be applicable to the composed parallel translations P_{y_2,x}^g\\circ P_{y_1,y_2}^g\\circ P_{x,y_1}^g. However, the derivation seems to be concluding as follows:\n\\begin{equation*}\n\t\\|\\mathrm{proj}_{T_x\\mathcal{M}}(v) - P_{y_2,x}^g\\circ P_{y_1,y_2}^g\\circ P_{x,y_1}^g(v)\\| < C\\|v\\|(\\mathrm{dist}(x,y_1)+\\mathrm{dist}(y_1,y_2) + \\mathrm{dist}(y_2,x)).\n\\end{equation*}\nDo the above bounds hold for any geodesic triangle or polygon with more vertices? If so, please state it appropriately as this is not what Theorem 2.8 says. If that is not the case, I do not see a workaround to get to the claimed results of the finite-time analysis.\n\nOther concerning questions are listed below:\n* In all of the derivations associated with the parallel translation, except for the one that appeals to Theorem 2.8, only the isometric nature of the parallel translation is used. Is the analysis applicable to any other isometric vector transport?\n* The vector transport by orthogonal projection is much less restrictive compared to the parallel translation, yet they both obtain the same converging rates as claimed. Are there any insights to explain this less intuitive result?\n* In Assumption 2.5, the constraint $\\|d/dt \\mathrm{Retr}_x(t\\xi)\\|\\leq \\|\\xi\\|$ is odd to me. We usually see assumptions about the $\\|O(t^2)\\|$ term in $\\mathrm{Retr}_x(t\\xi) = x + t\\xi + O(t^2) + o(t^2)$. Is the assumption proposed in this paper met in general? \n* The numerical experiment section is weak in its current state. It is only showing different converging trends (depends on the algorithmic parameter) that stagger around $0.1$. \n\nThe less concerning questions are listed below:\n* The online to non-convex framework even in the Euclidean setting is not that straightforward, not to mention its adaptation in the Riemannian setting that involves retraction and vector transport. It would be nice to include some pictures for visual aid.\n* Line 320 to Line 321 is confusing. Does that mean the analysis is based on the parallel translation, and the analysis does not apply to the implementation?\n* Line 328: What is a two-point bandit feedback?\n* Typos: (Line 889) the square of $\\|\\Delta_t-u_t\\|$ is missing; (Line 906) Assumption 2.5.", "limitations": "This paper discussed its limitations, i.e., how the curvature of a manifold affects the analysis, is an open question.\nThe main problem of this paper is stated in the \"Questions\" box.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall, this paper has a clear structure and it reads well. Necessary background and related literature are reviewed and addressed appropriately. The effort in making appropriate adaptations of the O2NC and the Goldstein Stationarity criterion to the Riemannian setting is worth noting. The presented finite-time analyses are nontrivial yet not entirely convincing to me. In particular, the derivation that appeals to Theorem 2.8 is problematic to me, and the specific questions are elaborated in the following section. It hurts the credibility of this paper. The experimental section is less ideal. In particular, the presented RO2NC algorithm is not compared with existing algorithms, e.g., the basic stochastic gradient method, which makes it hard to interpret the optimal converging rates claimed in previous analyses. The demonstrated results stagger around the objective values of $0.1$, which does not demonstrate the converged stationary neighborhood.", "was_revised": true, "final_justification": "The authors addressed my concern, especially the major one. Therefore, I would like to raise the score.", "rebuttal": "We thank the reviewer for their time and their detailed review of our work. Please see our response below to address the specific comments. \n\n> Most important question: Theorem 2.8 states ...\n\nWe thank the reviewer for highlighting this important point. Yes, the bounds hold for any geodesic triangle or polygon with more vertices. In fact, in the proof of Theorem 2.8, we primarily require two conditions: (i) the original vector must lie in the tangent space at the initial point of the path, and (ii) the path must be traversed along geodesics, so that the instantaneous distortion can be quantified using the second fundamental form, noting that the set of points with nonzero acceleration has measure zero. Therefore, the extension of the proof to a path is rather straightforward with the upper bound depending on the total length of the path. We will  include the corresponding discussion in the revised version.\n\n> In all of the derivations associated with the parallel translation ...\n\nThis is an interesting question. We employ parallel transports for two key reasons, namely its isometric nature and the fact that it provides a well-defined characterization of distortions. However, as long as one can quantify the distortion introduced by a given transport method along a trajectory, our analysis can, in principle, be extended to accommodate alternative forms of isometric vector transports. As an example, an isometric vector transport under locking condition has been analyzed in [28]. We will add a discussion on this note in the revised version.\n\n> The vector transport by orthogonal projection is much less restrictive ...\n\nOur reported convergence rate matches that of the Euclidean case, suggesting a natural interpretation: in the regime of nonsmooth, nonconvex stochastic optimization, the complexity of the optimization problem, itself, dominates the ``geometric overhead\" introduced by the curvature. From this viewpoint, vector transport should not be seen as a relaxation of parallel transport or as a mechanism that inherently exacerbates convergence. Instead, it often offers a more practical implementation route (reduced per-iteration computational cost) with a trade-off that the isometry might not hold. The iteration complexity bounds for vector transport and parallel transport are generally equivalent [28,39], but the analysis of vector transport is often more involved, as demonstrated in our setting.\n\n> In Assumption 2.5, the constraint ...\n\nIn practice, commonly used retraction curves typically satisfy both of the required conditions. As mentioned in Lines 229–235, exponential maps and polar decomposition-based retractions are representative examples. In addition, retractions based on QR decomposition or the Cayley transform on the Stiefel manifold also satisfy these properties. The second-order retraction, suggested by the reviewer, satisfies the second condition of Assumption 2.5 by construction. For the first condition of Assumption 2.5, it can be shown that for second-order retractions there exists a constant $c$ such that $d(x,retr_x(v))\\le c||v||, \\forall v : ||v||\\le \\frac{D}{c}$. Therefore, if we use the suggested condition, by updating the clipping parameter $D$ as $D/c$, our results remain valid. Since the suggested second-order retraction is more general, we will definitely clarify the more general conditions and their implications in the revised version. Thank you for this constructive comment.\n\n> The numerical experiment section is weak in its current state...\n\nThe reviewer has a correct observation about the staggering values; however, this is not a weakness of the experiment design; it is a phenomenon arising from the measuring technique, not the algorithm itself. As we noted in Lines 1098–1100, we evaluate an upper bound on the original $\\delta$-norm stationarity criterion. While the Goldstein stationarity definition is theoretically the most appropriate criterion for nonsmooth objectives, in practice, it is intangibly expensive to compute subdifferentials at all points within a $\\delta$-ball and to determine the minimum-norm element in their convex hull. As a practical alternative, we use an upper bound given by the average of sampled gradients. However, for fully nonsmooth objectives, this upper bound may remain nonzero even when the iterates are close to a minimizer. A simple illustrative case is the function $f(x) = |x|$: sampling gradients in a $\\delta$-neighborhood around the origin yields values whose average norm is influenced more by the number of samples than by $\\delta$. In our experiments, the plots reflect convergence in terms of this upper bound. Achieving lower values depends heavily on using larger epoch lengths $T$.\n\n> The online to non-convex framework even in the Euclidean setting is not that straightforward...\n\nThis is a good suggestion. During the brief rebuttal period, we focused on addressing the technical concerns of reviewers, but we will consider generating visual illustrations for the algorithm in the revised version.\n\n> Line 320 to Line 321 is confusing...\n\nIn general, the definition of norm delta involves ``parallel transports\", so we use them in the analysis of both algorithms. For each case, we do analyze the algorithm that is implemented, but the analysis of the projection-based algorithm (and not its implementation) also involves parallel transports. We will rephrase the sentence to avoid confusion.  \n\n> Line 328: What is a two-point bandit feedback?\n\nThe two-point bandit feedback method (introduced in Line 334) is a widely used technique for estimating gradients in zeroth-order optimization [22,33,54]. It provides a gradient estimate based solely on function evaluations at two points, making it particularly useful when gradient information is not directly accessible.\n\n> Typos: (Line 889)\n\nThanks for catching this. We will fix it in the revised version."}]

Author rebuttal:

Meta-review: This paper provides the first finite-time analysis for nonsmooth nonconvex stochastic optimization under Riemannian manifold constraints, introducing the RO2NC algorithm and its zeroth-order variant with optimal sample complexity. The contribution is novel and significant, and experiments support the theory.

All reviewers gave positive scores. Most reviewers raise concerns about the motivation and practicality of the key assumptions (e.g., uniform convexity and independence), as well as the clarity of proofs. The rebuttal partially addressed these issues, but the manuscript would benefit from further theoretical and experimental revisions.  Although I recommend acceptance, I strongly encourage the authors to revise the paper carefully to better justify their assumptions, clarify proofs, and improve presentation.
Decision: Accept (poster)