An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
Authors: Xu Shi
Rufeng Xiao
Rujun Jiang
Venue: NeurIPS 2025 poster ()
Keywords: Adaptive algorithm
Bilevel optimization
Riemannian manifolds
Complexity
Primary area: optimization
TL;DR: This paper introduces an adaptive Riemannian hypergradient descent algorithm for solving Riemannian bilevel optimization problems.

Abstract: Existing methods for solving Riemannian bilevel optimization (RBO) problems require prior knowledge of the problem's first- and second-order information and curvature parameter of the Riemannian manifold to determine step sizes, which poses practical limitations when these parameters are unknown or computationally infeasible to obtain. In this paper, we introduce the Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm for solving RBO problems. To our knowledge, AdaRHD is the first method to incorporate a fully adaptive step size strategy that eliminates the need for problem-specific parameters in RBO. We prove that AdaRHD achieves an $\mathcal{O}(1/\epsilon)$ iteration complexity for finding an $\epsilon$-stationary point, thus matching the complexity of existing non-adaptive methods. Furthermore, we demonstrate that substituting exponential mappings with retraction mappings maintains the same complexity bound. Experiments demonstrate that AdaRHD achieves comparable performance to existing non-adaptive approaches while exhibiting greater robustness.

An Adaptive Algorithm for Bilevel Optimization on Riemannian Manifolds
Xu Shi"
Rufeng Xiao
Rujun Jiang 1,2
School of Data Science, Fudan University
SShangaai Key Laboratory for Contemporary Applied Mathematics, Fudan University
{xshi22, rfxiao24) fudan.uaaenaa edu.
rjj rjjiangfuudan. edu. cn
Abstract
Existing methods for solving Riemannian bilevel optimization (RBO) problems require prior knowledge of the problem's first- and second-order information and curvature parameter of the Riemannian manifold determine step sizes, which poses practical limitations when these parameters are unknown or computationally infeasible to obtain. In this paper, we introduce the Adaptive Riemannian Hypergra- dient Descent (AdaRHD) algorithm for solving RBO problems. To our knowledge, AdaRHD the first method to incorporate a fully adaptive step size strategy that eliminates the need for problem-specific parameters in RBO. We prove that AdaRHD achieves an (11/e) iteration complexity for finding an e-stationary point, thus matching the complexity of existing non-adaptive methods. Furthermore, demonstrate that substituting exponential mappings with retraction mappings main- tains the same complexity bound. Experiments demonstrate that AdaRHD achieves comparable performance to existing non-adaptive approaches while exhibiting greater robustness.
Introduction
Bilevel optimization has garnered significant attention owing to its diverse applications in fields
such as reinforcement learning 449
35 meta-learning 6
hyperparameter optimization 87 88) and signal processing [50] 24). This paper focuses
[26] 773 195], adversarial learning 8
on "Riemannian bilevel optimization (RBO)"
23
54], framework that arises in applications
such as Riemannian meta-learning Riemannian min-max optimization formulation of RBO is as follows:
80 neural architecture search (77). image segmentation (28).
102
30 and low-rank adaption 188. The general
min M
F(x) v=))
s.t. y²(x) arg min g(x, v). yEM,
where May My are d=- and d di-dimensional complete Riemannian manifolds [54 the functions f.g: M2 x My + RR are smooth, the lower-level function g y) is geodesic strongly convex w.r.t. y. and the upper-level function ff not required to be convex.
To address Problem ( we extend the recent advances in Euclidean adaptive bilevel optimization 933 to propose an adaptive Riemannian hypergradient method. Although certain aspects of Euclidean
'qqual contributions. *Coresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

analysis extend naturally to Riemannian settings, the manifold's 's curvature parameters introduce many analytical challenges. We propose key technical difficulties in designing adaptive methods for solving RBO problems as follows:
(i) RBO necessitates that variables are constrained on Riemannian manifolds, making it intrinsically more complex than its Euclidean counterpart. Furthermore, critical parameters such as geodesic strong convexity, Lipschitz continuity, and curvature parameters over Riemannian manifolds are more computationally demanding to estimate than their Euclidean counterparts. Consequently, the geometric structure of the manifold creates distinct analytical challenges in the convergence analysis of adaptive algorithms.
(ii) Compared to single-level Riemannian (adaptive) optimization, RBO inherently involves inter- dependent variable updates, resulting in complex step size selection challenges arising from coupled (hyper)gradient dynamics.
(iii) Unlike non-adaptive RBO methods, adaptive step-size strategies can cause divergent behavior during initial iterations since the initial step size may be too large, which must be rigorously addressed to enable robust theoretical convergence analysis.
In this work, we present comprchensive convergence analysis that demonstrates our approach to resolving these challenges.
1.1 Related works
Table |smmmarzzss key studies on (Riemannian) bilevel optimization that are relevant to our methods. The table compares their applicable scenarios, whether they adaptive, and their computational complexity of first- and second-orde information. Note that constants, such as condition numbers, omitted from the complexity analysis for simplicity. For comprehensive review of the related works, please refer to Appendix A
Table I: Comparisons of first-order and second-order complexities for reaching e-stationary point. Here, "Fue" and "Rie" represent the feasible region the algorithms are Fuclidean space and Riemannian manifolds, respectively. The notations "Det", "F-S", and "Sto" represent the applicable problems as deterministic, function- sum, and stochastic, respectively. Additionally, Gy and Gg are the gradient complexities of f and g. respectively. JV, and HV, are the complexities of computing the second-order cross derivative and Hessian- product of The notation O denotes the omission of logarithmic terms in contrast to the standard O notation. Furthermore, the notation "NA" represents that the corresponding complexity is not applicahle.
Methods
Space
Adaptive
Type
G₁
G2
JV O(1ec)
HV, O(JE²)
D-TFBO 193
O(1/c)
O(1/c)
Euc
Det
S-TFBO 93
((1/e) O(1/e)
O(1/e)
Õ(1/e)
RHGD-HINV 33
O(1/c)
O(1/e)
O(1/c)
NA
RHGD-CG 33
O(1/e)
0(1/e)
0(1/e)
Ó(1/e)
Det
RHGD-NS
Rie
O(1/c)
Ó(1/))
0(1/) Ó(1/))
RHGD-AD 33
O(1/e)
O(1/e)
O(1/c)
O(1/c)
RSHGD-HINV
33
F-S
0(1/e)
0(1/e)
0(1/e) NA
RicBO [54
Det
O(1/e)
O(1/e)
O(1/e)
O(1/e)
Rie
X
RicSBO
Sto
O(1/e)
Ó(1/e)
O(1/e)
Ó(1e2)
RFASA 23
Det
O(1/63/2)
((1/6/2)
NA
Rie
x
RF'SA 2X
Sto
0(1/67/2)
0(1/612)
NA O O(1/e) Õ(1/e)
NA
AdaRHD-GD (Ours)
O(1/e)
O(1/e7)
(11/7)
Rie
Det
AdaRHD-CG (Ours)
((1/e)
O(1/e)
1.2 Contributions
This paper introduces the Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm, the first method to incorporate a fully adaptive step size strategy, eliminating the need for parameter-speciffc prior knowledge for RBO. The contributions of this work are summarized follows:

---

(i) We develop an adaptive algorithm for solving RBO problems, eliminating reliance prior knowledge of strong convexity, Lipschitzness, or curvature parameters. Our method achieves convergence rate matching those of non-adaptive parameter-dependent approaches. Furthermore, by replacing exponential mappings with computationally efficient retraction mappings, our algorithm maintains comparable convergence guarantees while reducing computational costs.
iii We establish upper bounds for the total iterations of resolutions the lower-level problem in Problem (T) and the corresponding linear system required for computing the Riemannian hypergradient. The derived bounds match the iteration complexity of the standard AdaGrad- Norm method for solving the strongly convex problems [92].
(iii) We evaluate our algorithm against existing methods on various problems over Riemannian manifolds, including the Riemannian hyperr-epressenation and robust optimization problems. The results demonstrate that our method performs comparably with non-adaptive methods while exhibiting significantly greater robustness.
2 Preliminaries
In this section, we review standard definitions and preliminary results on Riemannian optimiza- tion. All results presented here available in the literature [53 conciseness.
10
we restate them for 33 54
We first establish essential properties and notations for Riemannian manifolds. The definition of Riemannian manifold has been conducted in the literature [53] IO.. The Riemannian metric on Riemannian manifold .M at x E M is denoted by (;,)2 T.M x T + R, with the induced norm on the tangent space T.M defined ||u||a v (u, u)z for any
T.M. We then recall the definitions of exponential mapping and parallel transport. For an tangent vector u E T.M and a geodesic mapping Exp,, TTM + . is defined as (x) = y. The inverse the exponential mapping. Exp," :M- + Mr,, is called logarithm mapping [10] Definition 10.20], and the Riemannian distance between two points x, M is given by d(x, y) = ||Exp_ (v)lle = Expy (x)]ly- Parallel transport Prz T T2 M - T Ta is linear operator that preserves the inner product structure, satisfying (u, e).. = (Pazu, Pat u) for all u, E M.
[0, 1] + MM satisfying c(0)
c(1) y. and c0)
the exponential
We now define key properties of functions Riemannian manifolds. The Riemannian gradient (I(x) E T,M of a differentiable function f: M + is the unique vector satisfying
(Gf(x), u) [u), T.M.
where [u] denotes the directional derivative of f at along u 84
10
54
For twice-
differentiable f. the Riemannian Hessian Hz(x) is defined as the covariant derivative Gf(x). A function f: M + R is "geodesically (strongly) convex" if s(((t) is (strongly) convex w.r.t. t E [0, 1] for geodesics e: [] + Ω where C M is a geodesically convex set [54] Defini- tion 4]. Particularly, if f is twice- differentiable, j-geodesic strong convexity of is equivalent to (z) 2 pId, where Id the identity operator. Further, f is "geodesically Lipsschhit smooth" [[]f(z) Pf S L,d(x, v), VI, E M, and for twice-iifferentiable f, this property is equivalent Hf(x)) 3 Lyld.
Finally, for a bi-function f: Ma x M, ~ R. the Riemannian gradients of ʃ w.r.t. x and are denoted by f y) and f,f( (z, 3), respectively, while the Riemannian Hessians are Hzf(2z v) and fx, v). Moreover, the Riemannian cross-derivatives f TyMy + T,M, and fzr y): T, Ty. discussed in 33 [54, linear operators. Furthermore, the operator norm of a linear operator 9: Iy,M + Mg is defined as |||||2
sup
||[u]]|
WET, M,T,,M,,llull,--
Building on the concepts of Lipschitz continuity (ef. Definition B.I and geodesic strong convexity present the following proposition.
for functions defined on Riemannian manifolds,
Proposition 2.1 (10 33 54) ) For a function f -M- - R, if its Riemannian gradient G is
L-Lipschitz continuous, then for all xr y EU C M, it holds that
L d2 (x(z)) 2
f(y) < f(x) (9f(z), Exp_ ((v))
3

---

If is p-geodesic strongly convex, then for all N. E U, it holds that
14 f 2 f()) (Gf()), Exp, (v)),
d2 (x. v)-
(2)
2
Additionally, for the Lipschitzness of the functions and operators, and an important result of the trigonometric distance bound over the Riemannian manifolds, we present them in Appendix
3 Adaptive Riemannian hypergradient descent algorithms
determine step sizes for updating the variables using problem-specific parameters such as strong convexity, Lipschitzness, and curvature constants. However, these parameters are frequently impractical estimate compute, posing challenges for step size determination. This limitation underscores the need for adaptive RBO algorithms that operate without prior parameter knowledge.
Standard Riemannian bilevel optimization (RBO) approaches 23 33 54
3.1
Approximate Riemannian hypergradient
Prior to presenting our primary algorithm, we first introduce the Riemannian hypergradient, as the concept of our methodology relies this construct. Following general bilevel optimization frameworks, we define the Riemannian hypergradient of F(x) in Problem (I) as follows:
Proposition 3.1.
A33 (54) The Riemannian hypergradient of F(x) are given by
GF(x) = Gzf(x, 1f" (x)) ( g(x, y² (x)) (x)) E T.M.
(3)
3.1 fundamentally hinges on the implicit function theorem for Riemannian manifolds [0]. which necessitates the invertibility of the Hessian of the lower-level objective function g w.r.t y. In this paper, this requirement is satisfied as is geodesically strongly convex w.r.t. Consequently, y" (z) is unique and differentiable.
Proposition
However, the Riemannian hypergradient defined in (3) is computationally challenging to evalu- ate. First, the exact solution y (a(x: of the lower-level objective is not explicitly available, cessitating the use an approximate solution ý. we employ the adaptive Riemannian gradient descent method compute this approximation. Second, calculating the Hessian-inverse-veetee product Hy H,, 9 y² (9,)) y" (x))] in (3) incurs prohibitive computational costs. To address this, given the approximation ÿ of y (x), we can approximate the Hessian-inverse-veeto product H, 9(x, () (x: 5) by solving the linear system Hyg[v]] ú) f,f(x, 9). which is originated from the following quadratic problem:
R(x, 0, v) = = (v. Hgg((, 010)) (u, 9, 0))g- My
min
Denote è as the approximate solution of Problem 4 In this paper, we use the adaptive gradient descent method (cf. Steps T1 of Algorithm [T or the tangent space conjugate gradient method
[0] (cf. I6op of Algorithm I to obtain such é. Specifically, the tangent space conjugate gradient algorithm is presented Algorithm of Appendix C
Then, given the estimations ÿ and i, the approximate Riemannian hypergradient defined as follows,
23
3
is
GF g. Gzf 9) Pzyg(z, 9) T.Ma.
(5)
3.2 Adaptive Riemannian hypergradient descent algorithm: AdaRHD
Motivated by the recent adaptive methods 993 for solving general bilevel optimization, we employ the "inverse of cumulative (Riemannian) gradient norm" strategy to design the adaptive step sizes
92 90
i.e., adapting the step sizes based on accumulated Riemannian (hyper)gradient norms.
Given the total iterations T, set the accuracies for solving the lower-level problem of Problem (I) and linear system as e, = 1/T and e, = 1/T. Our Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm for solving Problem (1) is presented in Algorithm [ For simplicity, when employing the gradient descent (Steps) 15) and conjugate gradient (Step T6p to solve the linear system, respectively, denote AdaRHD as AdaRHD-GD and AdaRHD- respectively.

---

Algorithm Adaptive Riemannian Hypergradient Descent (AdaRHD)
1: Initial points Zo & _M, 1/o E MMy and Up E To M, initial step sizes do > 0, bp
> 0, and
cp > 0, total iterations T, and error tolerances cy = 6y T do
2: for 2, ..., T
3: Set = 0 and 1/. = 1/-1 K if and yo otherwise.
4:
while (2t, Vi v/))(((( [ly > cy do
5:
1 = by + (1 vt 11
6:
y1
*+1 E b24s 9 (9g(
7:
k == k: 1.
8:
end while
9:
Kr k.
10:
Set = 0 and vgt = p" k,-
4-1
No if >> 0 and uo otherwise.
V1-1
while IV R(Ee, V1 Kt
vi)
12 cv do
M1
12:
c4 = c + 1 R Ut .
13:
U/ n+1 =//-
V R(x, Ue Ke, ,2)).
D Gradient descent
14:
n= n
15:
end while
16:
Or set of = 0 and invoke of
TSCG
Hyg(ar, (.)))y 1)), 0f Gv). Conjugate
gradient
17:
N₂ =n
[F( Ki, ( = frr, v) P vi 1,,",
18:
di+1 of + +11 (I Ve v2 )
J++1 = ExPa. 1 (FI,, Ve ,0, N)))
20:
ai1l
21:
end for
3.3
Convergence analysis
This section establishes the errors between the approximate Riemannian hypergradient (5) and the exact Riemannian hypergradient (3), the convergence result of Algorithm I and the corresponding computation complexity.
3.3.1 Definitions and assumptions
Similar the definition of e-stationary point in general bilevel optimization 28
42 the
definition of an c-stationary point in Riemannian bilevel optimization [3 54 is given as follows.
Definition 3.1 (c-stationary point). A point x E M2 an c-stationary point of Problem if satisfies [[ 12 <
We first concern the upper bound of curvature constant ((F,c) defined Lemma B.1
Assumption 3.1. The manifolds M, and My are complete Riemannian manifolds. Moreover, M,, is Hadamard manifold whose sectional curvature is lower bounded by T < 0. Moreover, for all iterates st in the lower-level problem, the curvature constant Ç(T, d(ytt u² (xx))) defined in Lemma B.l is always upper bounded by a constant for all 2 0 and k 2 O.
Assumption 3.1 is commonly used in the Riemannian optimization, which ensures that the lower-level objective can be geodesically strongly convex [100, 54] and is essential for the convergence of the lower-level problem [33 (4)..
We then adopt the following assumptions concerning the fundamental properties the upper- and lower-level objectives of Problem 1
Assumption 3.2. Function [(x, v) is continuously differentiable and g(x, y) is twice continuously differentiable for all (x, y) Eu U, x My C Mr x Ma, and g(x, 4) is p- p-geodesic strongly convex E Uly for any Ud.
5

---

This assumption is prevalent in (Riemannian) bilevel optimization [28 43 42 57 Under this assumption, the optimal solution y (z) of the lower-level problem is unique for all E MM and differentiable [3 54), ensaring the existence of the Riemannian hypergradient (3.1)
[5| 51
23 33 [4].
Assumption 3.3. Function f(x,, y) is 1-pppscct continuous in l C MM x My The Riemannian y) are I.p-Lipschitz continuous in U. The Riemannian gradients Geg(z, y) and Gyg(r,)) y) are Ly Ly-Lipschitz continuous in U. Furthermore, the Riemannian Hessian Hyg(z, y), cross derivatives Gmyg(z, (2, y), (z, y) are p-Lipschite in U.
gradients (n](r,)) and Gy (x.
Assumption 3.3 is standard condition in the existing literature (Riemannian) bilevel optimization [28 43 42
33 54). These conditions ensure the smoothness of the objective function F in Problem
(1) and the Riemannian hypergradient GF defined in (3)
Assumption 3.4.
The minimum of F over Ma. denote F*, is lower-bounded.
Assumption 3.4 concerns the existence of the minimum of F, which is a common requirement in the
literature of adaptive (bilevel) optimization problems 900 92 93
3.3.2 Convergence results
Denote (I,y) == arg min R(.,y.0) We can then bound the estimation error of the proposed schemes of approximated hypergradient as follows.
Lemma 3.1 (Hypergradient approximation error bound). Suppose that Assumptions 3.7 3.2 3.3 and 3.4 hold. The error for the approximated Riemannian hypergradient generated by Algoritim satisfies,
F Ve .u ) GF( S Lid (vd(v()))) + - ( "1
where L1 == :1== 40 + La( L1 4p 4
Lemma 3.1 establishes that the error between the approximate and exact Riemannian hypergra- dients is bounded by the errors arising from the resolutions of the lower-level problem in Prob- lem (T) and the linear system 4. Consequently, we can actually integrate the stopping criterion F yt ) I 1/T into Algorithm/ 1 to enable early termination. By Lemma 3.1 this criterion ensures that (x; < (11/T), which implies that z; is an ((1/TT) point of Problem ( Moreover, integrating this criterion does not increase the overall computational complexity of Algorithm 1 since the norm of GF (rr.,i
K, v.a))) is already computed Step 20
Similar to Proposition 2 in [93] we derive upper bounds on the total number of iterations required to solve both the lower-level problem in Problem (I) and the linear system (4). However, owing to the geometric structures inherent in Riemannian manifolds, these bounds cannot be directly inferred from [93] Proposition 2] and require meticulous analysis.
Proposition 3.2. Suppose that Assumptions 3.7 3.2 3.3 and 3.4 hold. Then, for any 0 S t S T, the
numbers of iterations K2 and N₂ required Algorithm
satisfy:
(gg(C//b3)
b
Kr < log(1 + Cg/CC)
log
(n/b CL2
Ey
AdaRHD-GD:
log /g
N log(1 c C2)
log p
where Cb, C. b, T, b, and ē are constants defined in Appendix G
AdaRHD-CG:
4L c.
VLglu+ VL
N₂ log
Mlog
Remark 3.1. Proposition 3.2 provides upper bounds for the total tterations of the resolutions of the lower-level problem in Problem ( and the linear system 4.. Since 1/ log(1 + 6y) is of the same order as 1/Eg. it holds that Ke (1)/ey), which matches the standard AdaGrad-Noma for solving

---

strongly convex problems [92]. Additionally, we also have N, - and N; Olog((1/
when employing gradient descent and conjugate gradient methods, respectively. Moreover, similar to AdaGrad-Nar 192), the step size adaptation for the lower-level problem proceeds in two stages: iterations, while Stage requires at most ((log(1/Ey) iterations. Furthermore, due to geometric properties of Riemannian manifolds, these bounds cannot be directly derived from (93) and introduce additional technical challenges. Specifically, the constants Cb Co. b, G, b, and č are all related to curvature S, and increase as Ç increases.
Stage requires at most ((1/ 1og(1+
Based on Proposition 3.2, we have the following convergence result of Algorithm 1
Theorem 3.1. Suppose that Assumptions 3.1 by Algorithm 7 satisfies,
3.2
3.3
and hold. The sequence { generated
C T
+
[GFF(=)),,
0
where C' is a constant defined in Appendix G
Theorem 3.1 demonstrates that our proposed adaptive algorithm achieves convergence rate matching that of standard non-adaptive (Riemannian) bilevel algorithms (c.g., [28] 43 42
33
54 ), thereby
demonstrating its computational efficiency. Moreover, although Algorithm shares similar algo- rithmic structure with D-TFBO (93] and some Euclidean analyses extend naturally to Riemannian settings, its convergence analysis still presents significant theoretical challenges. For example, the geometric structure of Riemannian manifolds necessitates the use of the trigonometric distance bound (Lemma B.I instead of its Euclidean counterpart and requires incorporating the curvature constant into the step size adaptation (cf. Proposition 3.2). which substantially increases the analytical difficulty. We subsequently derive the complexity bound for Algorithm []
Corollary 3.1. Suppose that Assumptions 3.7 3.2 3.3 and 3.4 hold. Algorithm I Ineeds T = O(1/e)
iterations to achieve an e-accurate stationary point of Problem ( The gradient complexities of f and g are G = (11/e) and Gg = )(L/²), respectively. The complexities of computing the second-order cross derivative and Hessian-vector product of g are JVg = ((1/e) HV, = (11/2) for AdaRHD-GD,, and HV, = =((1c) for AdaRHD-CG, respectively.
Corollary 3.I demonstrates that the gradient complexity (Gg) and Hessian- vector product complexity (HV,) of AdaRHD-GG surpass those of non-adaptive Riemannian bilevel optimization methods by a factor of l/c. This gap originates from the additional iterations needed to guarantee the solution of the lower-level problem in Problem ①1 and linear system 4 which is necessitated by the lack of prior knowledge regarding the strong convexity, Lipschitzness, and curvature constants.
33 54
Designing algorithms to eliminate the 1/e-gap is interesting future direction. Potential strategies to bridge this gap could be drawn from adaptive methods in Riemannian optimization, such as sharpness-aware minimization
Riemannian manifolds (Riemannian SAM) [96]. Riemannian natural gradient descent (RNGD) (37], and the framework for Riemannian adaptive optimization (70]. Riemannian extensions of Euclidean approaches like adaptive accelerated gradient descent [61] adaptive proximal gradient method (adaPGM) [52], adaptive Barrilai-Borwein algorithm (AdaBB) [003. and adaptive Nesterov accelerated gradient (AdaNAG) (76) may also be viable alternatives to the inverse of cumulative gradient norms strategy 92] employed in Algorithm
3.4 Extend to retraction mapping
Given that retraction mapping is often preferred in practice for its computational efficiency over exponential mapping, this section demonstrates that its incorporation into Algorithm I achieves comparable theoretical convergence guarantees. A modified version of Algorithm [ incorporating retraction mapping, is presented in Algorithm33cc (ef. Appendix(). To formalize this extension, the second condition of Assumption
3.1 must be modified as follows.
Assumption 3.5. All the iterates of the lower-level problem generated by Algorithm 3 lie in a bounded
set belonging to My that contains the optimal solution, i.e., there exists a constant D > 0 such that
d(yž: y (I,)) < D holds for all t 2 and l 2 O.
Under Assumption 3.5 the curvature constant Ç(T, d(vt. , y (axz ))) in Assumption 3.1 is bounded by Additionally, it is necessary to consider the error between the exponential and retraction mappings.
its definition, thereby ensuring consistency with Assumption 3.T
7

---

Assumption 3.6. Given 21 E u S M (here M can be Mr or Myy and u E M, let 22 Retr (u). There exist constants Cu 2 1 2 0 such that (21, S Pullulls, and |[Ep= (22) 122))
(22)
u/la, S cnllulla.
Assumption 3.6 is standard (e.g..
33 Assumption 2] and 46 Assumption 1J) in bounding the
error between the exponential mapping and retraction mapping, given that retraction mapping is first-order approximation to the exponential mapping [33]
Then, similar to Theorem 3.1 we have the following convergence result of Algorithm 3
Theorem 3.2. Suppose that Assumptions 3.1
3.2
3.3
3.4
3.5
and 3.6 hold. The sequence {at [m=)r
generated by Algorithm satisfies,
Cretr
1 T
Σ [IF((=)) <
O
T
T
where Cretr a constant defined in Appendix
H
Algorithm| 3 achieves a convergence rate nearly identical to that of Algorithm ] while being more practical to implement. Furthermore, the complexity analysis of Algorithm 3 closely aligns with that of Algorithm D and is, therefore, omitted here.
4 Experimental results
In this section, adhering to the experimental framework established by [33 we conduct comprehen- sive experiments evaluate our algorithm against the RHGD method. Since the RieBO algorithm proposed by [54] shares the same algorithmic framework as RHGD, we categorize them as a single method for comparison. We designate RHGD-50 and RHGD-20 as configurations with maximum iteration limits for solving the lower-level problem in RHGD set to 50 and 20, respectively. For consistency, we exclusively employ Algorithm 3 in this section due to computational efficiency in practice. Detailed experimental settings and additional experiments are provided in Appendix | and our codes are available at battps://githu com/ Ruf cuuffengXiooAAie AdaRHD
4.1 Simple problem
In the first experiment, following 331, we consider a simple problem, which aims to determine the maximum similarity between two matrices X Ruxd and Y E Raxr, where 2 d 2 formulated
as:
(race(M* YWT)
max WeSt(d,))
8.t.
(W = arg min (M, X (M- W + AI), Mesd
where St(d,r) (W E Rdxr.
TWW W and sd (M E Rdxd M 0) represent the Stiefel manifold and the symmetric positive definite (SPD) matrices, respectively, and X > 0 is the regular parameter. The matrix W E St(d, r) aligns X and Y in a shared dimensional space, while the lower-level problem learns an appropriate geometric metric M E 5 197). Additionally, the geodesic strong convexity of the lower-level problem and the Hessian inverse expression can be found in Appendix H [33.. In this experiment, we generate random data matrices X and with two 100 and 1000, where d
sample sizes:
50 and = 20.
Uppur Osective
Upper
1
7mmen
Figure Performances of methods in 100.
Figure 2: Performances of methods in 1000.
Figures D and [ show the evolution of the upper-level objective function (Upper Objective) over time and the associated hypergradient estimation errors (Hypergrad error) across outer iterations.

---

Figure T corresponds to = 100, while Figure represents the 1000 case. These results demonstrate that our algorithm exhibits faster convergence and superior performance compared to RHGD while maintaining scalability with increasing sample dimensionality, confirming its efficiency and robustness. Moreover, although GD achieves quicker initial convergence, CG demonstrates greater robustness, as evidenced by its lower hypergradient estimation errors.
4.2 Robustness analysis
In the second experiment, also from [33 Section 4.2], address the deep hyper-reeressnnttion problem for classification, which a subclass of hyper-represennation problems [26] 73 95 59 74].
In contrast to the 2-layer SPD network employed for ETH-80 dataset classification in 33 to
demonstrate the efficacy of our algorithm, here we utilize a 3-layer SPD network 40 as the upper- level architecture optimize input embeddings over the larger AFEW dataset (20). comprising seven emotion classes. The training set contains 1,747 matrices with imbalanced class distribution (267,
235, 173, 292, 342, 288, and 150 samples per class, respectively). This optimization problem formulated as follows:
min A1: Ag. Ag
Σ
Yi log(SPDnet Dn A2, (A, (2,)A))))))
Deal
RED DED.i
s.L.
(M A2, Az) = arg min Σ (ER-(++1//2 IED
Y (n, + 11111
+
P
A1 St(, A2 St(di, d2), Ag E St(d2,)),
where SPDnet(;; A1, A3) denotes the 3-layer SPD network with layer parameters A1, A2, and A3 [40], the term y; represents the one-hot encoded label, and = {Di) denote a set of SPD 100,
matrices where D; $ Each matrix D; has dimensions of 400 400, and we
d2 = 20, and r =
In this study, we perform series of experiments with varying initial step sizes to evaluate the robustness and advantages of our proposed AdaRHD algorithm. To address computational constraints, we utilize a 5% subset of the AFEW dataset [20] rather than the full dataset, ensuring tractable training durations. For AdaRHD, we initialize hyperparameters ag. bp. and co to equal values and test performance across the range 10.2, 2, 10, 20}. For RHGD, we fix 7)r and Tl to equal values and evaluate the set {5, 1, 0.5, 0.1, 0.05]. To mitigate sampling bias and validate robustness, each algorithm is executed five times with distinct random seeds, each iteration employing a unique 5% data subset. This methodology enables systematic assessment of optimization sensitivity to step sizes and establishes the generalizability of our algorithm under practical constraints.
Voleasten ACC-PaY
Valeasoon Accuracy
Valowion
Valiceton
19
25
20
66
1M0
200
30
(a) AdaRHD-CG
(b) AdaRHD-GG GD
(c) RHGD-50
(d) RHGD-20
byporgped Norm
Prgeorrad Norm
Hyporgnd
Hyperred
113
312
312
(e) AdaRHD-CG
(f) AdaRHD-GD
RHGD-50
(h) RHGD-20
Figure 3: Epoch vs. validation accuracy and ergodic performance min.eto.:| Fl) v o under different initial step sizes for each algorithm. In the ligures for "AdaRHID-"" the labels indicate the values of 1/a0- 1/bn = 1/en; in figures "RHGD-X" the labels represent the values 1/-- 1/y
The results are presented Figure 3 and Table 2 It can be observed that the RHGD-50 and RHGD-20 fail when the initial step sizes are set to 5, 1. 0.5, whereas the corresponding configurations of

---

Table 2: Time to reach specific validation accuracy under different initial step sizes for each algorithm. The values outside the parentheses indicate the mean over five random trials, while the values inside the parentheses represent the standard deviation. "Step Size (A/R)" denotes the initial step sizes used in each method: 1/a0- = 1 b/bu = C/ca in the "AdaRHD-X X" algorithm: = fyy in the BRHGD-" algorithm. "X%" indicates the time required to reach the corresponding validation accuracy.
AdaRHD-CG
AdaRHD-GD
RHGD-50
RHGD-20
Step Size
50%
70%
85%
50%
70%
85%
50%
70%
85%
50%
70%
85%
287.20
464.79
1217.06
432.66
690.62
1488.26
I
5.0
(93.61)
(124.76)
(635.57)
(157.76)
(136.52)
(426.67)
1
1
131.84
191.51
245.63
200.26
317.31
421.99
1.0
(18.76)
(34.15)
(72.42)
(31.21)
(68.92) (88.31)
118.09
169.79
241.54
192.51
291.83
477.49
0.5
(19.91)
(28.59)
(33.09)
(22.86)
(54.21)
(120.17)
/
217.32
312.58
427.84
297.90
447.60
546.18
171.97
370.69
808
36.01
168.47
540.46
0.1
(38.96)
(33.66)
(53.40)
(42.60)
(53.50)
(66.68)
(68.61) ) (78.36)
(146.57)
(12.37)
(120.86)
(88.54)
251.47
415.51
633.46
358.25
504.80
648.86
137.8
715.91
1510.09
41.36
179.11
1067.92
0.05
(36.27) (49.75)
(96 54)
(32.89)
(15,58)
(42.91)
(136. 10)
(104. 62)
(363 41)
(6.88)
(157. 76)
(122.98)
AdaRHD remain relatively stable. Notably, even when using a step size greater than 1 (i.e., ag = by co 0.2), although the performance is less stable compared other settings, AdaRHD is still able to converge effectively. Table also shows that AdaRHD-CG consistently achieves 85% validation accuracy the shortest amount of time. On the other hand, step sizes of ag b0 co 1 yield the best performance among all initializations for the AdaRHD variants, while the corresponding RHGD configurations fail converge. These results further demonstrate the robustness of the proposed AdaRHD method, which significantly reduces the sensitivity to the choice of initial step size and greatly improves training efficiency. Moreover, although RHGD-20 requires the shortest time to reach 50% and 70% validation accuracies, it demands more time than our method to achieve 85% validation accuracy, demonstrating the efficiency of our approach. Meanwhile, the lower standard deviation exhibited by our method further highlights the robustness of our algorithm.
5
Conclusion
This paper proposes an adaptive algorithm for solving Riemannian bilevel optimization (RBO) prob- lems, employing strategies: gradient descent and conjugate gradient, to compute approximate Riemannian hypergradients. To our knowledge, this is the first fully adaptive RBO algorithm, incor- porating a step size mechanism, eliminating prior knowledge requirements of problem parameters. We establish that the method achieves an ((1/c) iteration complexity to reach an c-stationary point, matching the complexity of the standard non-adaptive algorithms. Additionally, we show that substi- tuting the exponential mapping with a computationally efficient retraction mapping maintains this complexity guarantee.
Notably, this work focuses exclusively on developing an adaptive double-loop algorithm for determin- istic Riemannian bilevel optimization (RBO) problems when the lower-level objective is geodesically strongly convex. Future research directions include: (1) designing single-loop adaptive algorithms
[ (2) extending the framework stochastic settings 333
23 54
via adaptive step sizes such in-
verse cumulative stochastic (hyper)gradient norms [92] or other strategies 22
47
86
58
96 770::
(3) addressing geodesically convex (non-strongly convex) lower-level objectives through regulariza- tion (2) or Polyak-t.jja ojjseeezz (PL) conditions [15]; and (4) investigating alternative adaptive step
size strategies [61 (96] 337 70
52 (6) to resolve the 1/e-gap in gradient (Gy) and Hessian-vector
product (HV,) complexities compared to non-adaptive Riemannian bilevel methods 33 54
Acknowledgements
We sincerely appreciate the reviewers for their invaluable feedback and insightful suggestions. This work is partly supported by the National Key R&D Program of China under grant 2023YFA 1009300, National Natural Science Foundation of China under grants 12171 100, and the Major Program of NFSC 023393360,239433
10

---

References
[1] P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2009.
[2] Jan Harold Alcantara and Akiko Takeda. Theoretical smoothing frameworks for general nonsmooth bilevel problems. arXiv preprint arXiv:2401.17853 2024.
[3] Gary Bécigneul and Octavian-Euger Ganea. Riemannian adaptive optimization methods, In International Conference on Learning Representations, 2019.
[4] Amir Beck. First-order methods in optimization, volume 25. SIAM, 2017.
[5] Tamir Bendory, Yonina C Eldar, and Nicolas Boumal. Non-convex phase retrieval from stft measurements. JEEE Transactions on Information Theory, 64(1):467 484, 2017.
[6] Luca Bertinetto, Joao F. Henriques, Philip Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. International Conference on Learning Representations, 2019.
Rajendra Bhatia. Positive definite matrices. Princeton university press, 2009.
[8] Nicholas Bishop, Long Tran-Thanh, and Enrico Gerding- Optimal learning from verified training data. In Advances in Neural Information Processing Systems, pages 9520-9529, 2020.
[9] Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217-2229, 2013.
[10] Nicolas Boumal. An introduction to optimization smooth manifolds. Cambridge University Press, 2023.
[1I] Nicolas Boumal and Pierre-antoine Absil. Rtrme: A riemannian trust-region method for low-rank matrix completion. In Advances in Neural Information Processing Systems, pages 406-414, 2011.
[12] Nicolas Boumal, Pierre-Antoine Absil, and Coralia Cartis. Global rates of convergence for nonconvex optimization on manifolds. IMA Journal of Numerical Analysis, 39(1):1-33, 2019.
[13] Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44, 1973.
[14] Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 547-555, 2011.
[15] Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small hyper-gradients in bilevel opti- mization: Hardness results and improved analysis. In Conference on Learning Theory, pages 947-980. PMLR, 2024.
[16] Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 2466-2488 PMLR, 2022.
[17] Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of altemna-- ing stochastic gradient methods for bilevel problems. In Advances in Neural Information Processing Systems, pages 25294-25300 2021.
[18] Anoop Cherian and Suvrit Sra. Riemannian dictionary learning and sparse coding for positive definite matrices. IEEE Transactions Neural Networks and Learning Systems, 28(12)22859 2871, 2016.
[19] Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau, A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Advances in Neural Information Processing Systems, pages (6698-267100 2022.

---

[20] Abhinav Dhall, Roland Goecke, Jyoti Joshi, Karan Sikka, and Tom Gedeon. Emotion recogni- tion in the wild challenge 2014: Baseline, data and protocol. In Proceedings of the International Conference on Multimodal Interaction, pages 461-466, 2014.
[21] Justin Domke. Generic methods for optimization-aan based modeling. In International Conference on Artificial Intelligence and Statistics, pages 318-326. PMLR, 2012.
[22] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(7):22212159, 2011.
[23] Sanchayan Dutta, Xiang Cheng, and Suvrit Sra. Riemannian bilevel optimization. arXiv preprint arXiv:2405. 15816, 2024.
[24] Rémi Flamary, Alain Rakotomamonjy, and Gilles Gasso. Learning constrained task similarities in graphregularized multi-task learning. Regularization, Optimization, Kernels, and Support Vector Machines, 103:1, 2014.
[25] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- hyperparameter optimization. In International Conference on Machine Learning, pages 1665-1173, PMLR, 2017.
[26] Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-lcarning. In International Conference on Machine Learning, pages 1568-1577. PMLR, 2018
[27] Daniel Gabay. Minimizing a differentiable function over differential manifold. Journal of Optimization Theory and Applications, 37:177-219, 1982.
[28] Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint
2018.
[29] Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration complexity of hypergradient computation. In International Conference on Machine Learning. pages 7744-3758. PMLR, 2020.
[30] Andi Han, Bamdev Mishra, Pratik Jawanpuria, and Junbin Gao. Nonconvex now.reecxnoccccveeeeeeo min-max optimization on riemannian manifolds. Transactions on Machine Learning Research, 2023.
[31] Andi Han, Bamdev Mishra, Pratik Jawanpuria, Pawan Kumar, and Junbin Gao. Riemannian hamiltonian methods for min-max optimization on manifolds. SIAM Journal on Optimization, 3373)1177711827, 2023.
[32] Andi Han, Bamdev Mishra, Pratik Kumar Jawanpuria, and Junbin Gao. On riemannian optimization over positive definite matrices with the bures-wassersted geometry. Advances in Neural Information Processing Systems, 34:8940-8953, 2021.
[33] Andi Han, Bamdev Mishra, Pratik Kumar Jawanpuria, and Akiko Takeda. A framework for bilevel optimization on riemannian manifolds. In Advances in Neural Information Processing Systems, volume 37, pages 103829-103872, 2024.
[34] Mehrtash Harandi, Mathieu Salzmann, and Richard Hartley. Dimensionality reduction on spd manifolds: The emergence of geometry- aware methods. IEEE Transactions Pattern Analysis and Machine Intelligence, 40(1 40(1):48- ):48-622 62, 2017.
[35] Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor- critic. SIAM Journal on Optimization, 33(1):147-110,
2023. 2023.
[36] Inbal Horev, Florian Yger, and Masashi Sugiyama. Geometry-aware principal component analysis for symmetric positive definite matrices. In Asian Conference on Machine Learning, pages 1-16. PMLR, 2016.
[37] Jiang Hu, Ruicheng Ao, Anthony Man-Cho So, Minghan Yang, and Zaiwen Wen. Riemannian natural gradient methods. SIAM Journal Scientific Computing, A2(1) 2024.
12

---

[38] Zihao Hu, Guanghui Wang, Xi Wang, Andre Wibisono, Jacob D Abernethy, and Molei Tao. Extragradient type methods for riemannian variational inequality problems. In International Conference on Artificial Intelligence and Statistics, pages 2080-2088. PMLR, 2024.
[39] Feihu Huang and Shangqian Gao. Gradient descent ascent for minimax problems on riemannian manifolds. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(7):8466 8467746666-77 2023.
[40] Zhiwu Huang and Luc Van Gool. A riemannian network for spd matrix learning. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 31, pages 2036-2042, 2017.
[41] Kaiyi Ji, Jason Lee, Yingbin Liang, and H Vincent Poor. Convergence of meta-learning with task-specific adaptation over partial parameters. In Advances in Neural Information Processing Systems, volume 33, pages 11490-1 1500, 2020.
[42] Kaiyi Ji, Mingrui Liu, Yingbin Liang, and Lei Ying. Will bilevel optimizers benefit from loops. In Advances in Neural Information Processing Systems, volume 35, pages 301 1-3023, 2022.
[43] Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[44] Michael Jordan, Tianyi Lin, and Emmiiouil-Vasilcioos Vlatakis-Gkaragkoumi First-order algorithms for min-max optimization in geodesic metric spaces. In Advances in Neural Information Processing Systems, volume 35, pages 6557-6574, 2022.
[45] Hiroyuki Kasai, Pratik Jawanpuria, and Bamdev Mishra. Riemannian adaptive stochastic gradient algorithms on matrix manifolds. In International Conference on Machine Learning. pages 3262-3271. PMLR, 2019.
[46] Hiroyuki Kasai, Hiroyuki Sato, and Bamdev Mishra. Riemannian stochastic recursive gradient algorithm. International Conference on Machine Learning, pages 2516-2524. PMLR, 2018.
[47] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[48] Max Kochurov, Rasul Karimov, and Serge Kozlukov. Geoopt: Riemannian optimization in pytorch. arXiv preprint arXiv:2005.028// 2020.
[49] Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In Advances in Neural Information Processing Systems, volume 12, pages 1014, 1999.
[50] Gautam Kunapuli, Kristin P Bennett, Jing Hu, and Jong-Shi Pang. Classification model selection via bilevel programming. Optimization Methods & Software, 23(4):475-489, 2008
[51] Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pages I 18033-18113 PMLR, 2023.
[52] Puya Latafat, Andreas Themelis, Lorenzo Stella, and Panagiotis Patrinos. Adaptive proximal al- gorithmss for convex optimization under local lipschitz continuity of the gradient. Mathematical Programming. 213:433-471, 2025.
[53] John M Lee. Riemannian manifolds: an introduction to curvature, volume 176. Springer Science & Business Media, 2006.
[54] Jiaxiang Li and Shiqian Ma. Riemannian bilevel optimization. Journal of Machine Learning Research, 26(18): 18)1 44, 2025.
[55] Lizhen Lin, Drew Lazar, Bayan Saparbayeva, and David Dunson. Robust optimization and inference manifolds. Statistica Sinica, 11:1999-1323 2024.
13

---

[56] Lizhen Lin, Brian St. Thomas, Hongtu Zhu, and David B Dunson. Extrinsic local regression on haanfold-valuee data. Journal of the American Statistical Association, 1266119 2017.
[57] Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. In Advances in Neural Information Processing Systems, volume 35, pages 17248-17262, 2022.
[58] Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Julien. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference on Artificial Intelligence and Statistics, pages 1306-1314 PMLR, 2021.
[59] Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International Conference on Artificial Intelligence and Statistics, pages 1540-1552. PMLR, 2020.
[60] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter optimization through reversible learning. In International Conference Machine Learning. pages 21 21-21222. PMIR, 2015.
[61] Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In International Conference on Machine Learning, pages 6702-676 6712. PMLR, 2020.
[62] David Martinez-Rubio, Christophe Roux, Christopher Criscitiello, and Sebastian Pokutta. Accelerated methods for riemannian min max optimization ensuring bounded geometric penalties. In International Conference Machine Learning, pages 280-288. PMLR, 2025.
[63] Bamdev Mishra, Hiroyuki Kasai, Pratik Jawanpuria, and Atul Saroop. A riemannian gossip approach to subspace learning on grassmann manifold. Machine Learning, 188-1783-1803 2019.
[64] Antonio Orvieto, Simon Lacoste-Julien, and Nicolas Loizou. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. In Advances in Neural Information Processing Systems, volume 35, pages 26943-26954, 2022.
[65] Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Machine Learning, pages 737-746. PMLR, 2016.
[66] Peter Petersen. Riemannian geometry, volume 171. Springer, 2006.
[67] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. In Advances in Neural Information Processing Systems, volume 32, pages
114, 2019.
[68] Soumava Kumar Roy, Zakaria Mhammedi, and Mchrtash Harandi. Geometry aware con- strained optimization techniques for deep learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4460-4469, 2018.
[69] Hiroyuki Sakai and Hideaki liduka. Riemannian adaptive optimization algorithm and its application to natural language processing. IEEE Transactions on Cybernetics, 52(8):7328- 7339, 2021.
[70] Hiroyuki Sakai and Hideaki liduka. A general framework of riemannian adaptive optimization methods with a convergence analysis. arXiv preprint UrXiv:2409.00885 2024.
[71] Hiroyuki Sato. A dai-yuan-type riemannian conjugate gradient method with the weak wolfe conditions. Computational Optimization and Applications, 64:101-118, 2016.
[72] Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport. SIAM Journal on Optimization, 19(2):1444-1472, 2019.
[73] Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propagation for bilevel optimization. In International Conference on Artificial Intelligence and Statistics, pages 1723-1732. PMLR, 2019.
14

---

[74] Daouda Sow, Kaiyi Ji, and Yingbin Liang. On the convergence theory for hessian- free bilevel algorithms. In Advances in Neural Information Processing Systems, volume 35, pages 4136-4149, 2022.
[75] Suvrit Sra and Reshad Hosseini. Conic geometric optimization on the manifold of positive definite matrices. SIAM Journal on Optimization, 25(1):713-739, 2015.
[76] Jaewook Suh and Shiqian Ma. An adaptive and parameter-free nesterov's 's accelerated gradient method for convex optimization. arXiv preprint arXiv:2505.11670, 2025.
[77] Rhea Sanjay Sukthanker, Zhiwu Huang. Suryansh Kumar, Erik Goron Endsjo, Yan Wu, and Luc Van Gool. Neural architecture search of spd manifold networks. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 3002-3009. International Joint Conferences Artificial Intelligence Organization, 2021.
[78] Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere it: Recovery by riemannian trust-region method. IEEE Transactions Information Theory, 63(2):885-914, 2016.
[79] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18: 11:1111-119, 2018.
[80] Hadi Tabealhojeh, Peyman Adibi, Hossein Karshenas, Soumava Kumar Roy, and Mchrtash Ha- randi. Rmaml: Riemannian meta-learning with orthogonality constraints. Pattern Recognition, 140:109563, 2023.
[81] Lloyd N Trefethen and David Bau. Numerical linear algebra. SIAM, 2022.
[82] Nilesh Tripuraneni, Nicolas Flammarion, Francis Bach, and Michael I Jordan. Averaging stochastic gradient descent on riemannian manifolds. In Conference On Learning Theory, pages 550-687. PMLR, 2018.
[83] Ioannis Tsaknakis, Prashant Khanduri, and Mingyi Hong. An implicit gradient-type method for linearly constrained bilevel problems. In ICASSP 2022-2022 IEEE International Conference Acoustics, Speech and Signal Processing, pages 1438-5443 IEEE, 2022.
[84] Loring W Tu. An Introduction to Manifolds. Springer, 2011.
[85] Bart Vandereycken. Low-rank matrix completion by riemannian optimization. SIAM Journal on Optimization, 1214):1214-122 2013.
[86] Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Advances in Neural Information Processing Systems, volume 32, pages 3732-3745 2019.
[87] Jiali Wang, He Chen, Rujun Jiang, Xudong Li, and Zihao Li. Fast algorithms for stackelberg prediction game with least squares loss. In International Conference Machine Learning, pages 10708-10716. PMLR, 2021.
[88] Jiali Wang, Wen Huang, Rujun Jiang, Xudong Li, and Alex Wang. Solving stackelberg prediction game with least squares loss via spherically constrained least squares reformulation. In International Conference on Machine Learning, pages 22665-22679) PMLR, 2022.
[89] Xi Wang, Deming Yuan, Yiguang Hong, Zihao Hu, Lei Wang, and Guodong Shi. Riemannian optimistic algorithms. arXiv preprint arXiv:2308. 200.:2208..6004,, 2023.
[90] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219) 2020.
[91] Quan Xiao, Han Shen, Wotao Yin, and Tianyi Chen. Alternating projected sgd for equality- constrained bilevel optimization. International Conference on Artificial Intelligence and Statistics, pages 987-1023, PMLR, 2023.
15

---

[92] Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. International Conference on Artificial Intelligence and Statistics, pages 1475-1485. PMLR, 2020.
[93] Yifan Yang, Hao Ban, Minhui Huang, Shiqian Ma, and Kaiyi Ji. Tuning-free bilevel optimiza- tion: New algorithms and convergence analysis. In International Conference on Learning Representations, 2025.
[94] Wei Yao, Chengming Yu, Shangzhi Zeng, and Jin Zhang. Constrained bi-level optimization: Proximal lagrangian value function approach and hessian-free algorithm. In International Conference on Learning Representations, 2024.
[95] Tong Yu and Hong Zhu. Hyper-parameter optimization: review of algorithms and applica- tions. arXiv preprint arXiv:2003.05689, 2020.
[96] Jihun Yun and Eunho Yang. Riemannian sam: Sharpness-aware minimization riemannian manifolds. In Advances Neural Information Processing Systems, volume 36, pages 65784 65800, 2023.
[97] Pourya Zadeh, Reshad Hosseini, and Suvrit Sra. Geometric mean metric learning. In Interna- PMLR, 2016.
tional Conference on Machine Learning, pages
[98] Emanuele Zangrando, Francesco Rinaldi, Francesco Tudisco, et al. debora: Efficient bilevel optimization-basee low-rank adaptation. In International Conference on Learning Represenia- tions, 2025.
[99] Hongyi Zhang, Sashank Reddi, and Suvrit Sra. Riemannian svig: Fast stochastic optimization on riemannian manifolds. In Advances Neural Information Processing Systems, volume 29, pages 4599-4607, 2016.
[100] Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. In Conference on Learning Theory, pages 1617-1638. PMLR, 2016.
[101] Jingzhao Zhang, Hongyi Zhang, and Suvrit Sra. R-spider: A fast riemannian stochastic optimization algorithm with curvature independent rate. arXiv preprint 1rXiv: 1111/1//140444 2018.
[102] Peiyuan Zhang, Jingzhao Zhang, and Suvrit Sra. Sion's 's minimax theorem in geodesic metric spaces and riemannian extragradient algorithm. SIAM Journal on Optimization, 33(4):2885- 2908, 2023.
[103] Danqing Zhou, Shiqian Ma, and Junfeng Yang. Adabb: Adaptive barzilai-borwein method for convex optimization. Mathematics of Operations Research, 2025.
[104] Pan Zhou, Xiao-Tone Yuan, and Jiashi Feng. Faster first-order methods for stochastic non- convex optimization riemannian manifolds. In International Conference on Artificial Intelligence and Statistics, pages 138-147, PMLR, 2019.
16

---

Appendix
A
Related works
Bilevel optimization: Bilevel optimization is first introduced by [13] and rooted in the Stackelberg
game [4
g
87
88 When the lower-level objective is strongly convex, various methods have been
proposed 28 17
42
19 57
35
51
Hypergradient- based approaches include approximate
implicit differentiation (AID) 21
65
iterative differentiation (TTD) 60] 25
73
29
Neumann
series (NS) 28];: and conjugate gradient (CG) 43 Recent studies address bilevel problems with
constraints on either the upper- or lower-level objective. For example, [16] 35 focus on scenarios
where constraints are imposed solely on the upper-level objective, whereas [83 91 [4] develop
methods for problems with lower-level constraints. For a comprehensive overview, we refer readers
to 43 42 51]
and the references therein.
Riemannian optimization: Riemannian optimization has attracted considerable attention due to its
broad applications, including low-rank matrix completion [TT 85]; phase retrieval [5] [9]] dictionary
learning 18 78 dimensionality reduction [34 82 and manifold regression [56 55 Various
methods have been developed, such as Riemannian (stochastic) gradient descent 27 9 5 12
nonlinear conjugate gradients [71]; and veriaece-reduced stochastic gradients (99] 101
For further details, see [10] and references therein.
Riemannian adaptive optimization: Several adaptive algorithms have been developed solve Riemannian optimization problems. Notable examples include the Riemannian adaptive stochastic gradient algorithm (RASA) [45, Riemannian A.MGGrad (RAMSGrad) []. modified RAMSGrad [69]. constrained RMSProp (cRMSProp) [68], sharpness-awe aware minimization on Riemannian manifolds (Riemannian SAM) [96.. Riemannian natural gradient descent (RNGD) (37] and a framework for Riemannian adaptive optimization 770 For a comprehensive overview of their application scopes, we refer readers to 770..
Riemannian bilevel optimization: Research on Riemannian bilevel optimization remains limited to (54) investigated hypergradient computation for such problems Riemannian manifolds and developed deterministic and stochastic algorithms, namely the algorithm for Rieman- nian bilevel optimization (RieBO) and the algorithm for Riemannian stochastic bilevel optimization (RieSBO), for solving Riemannian bilevel and stochastic bilevel optimization. respectively. In paral- lel, 133 proposed a framework termed Riemannian hypergradient descent (RHGD), which provides multiple hypergradient estimation strategies, supported by convergence and complexity analyses. The authors also extended their framework address Riemannian minimax and compositional optimization problems. By leveraging the value- funecffnniionn reformulation and the Lagrangian method, 23 introduced fully stochastic first-order approach, the Riemannian first-order fast stochastic approximation (RF?SA), which is applicable to scenarios where both objectives are stochastic or deterministie.
few recent studies.
Adaptive bilevel optimization: The closest related approach to our method is the D-TFBO proposed in [93], which tackles Euclidean bilevel optimization by employing a similar adaptive step size strategy. While some aspects of Euclidean analysis extend directly to Riemannian settings, geometric curvature introduces distortions that create unique analytical challenges. We derive convergence guar- antees similar to those of D-TFBO and enhance our algorithm's 's efficiency by replacing exponential mapping with retraction mapping, thereby reducing computational overhead. To our knowledge, this work presents the first fully adaptive method with theoretical convergence guarantees for solving Riemannian bilevel optimization problems.
B Additional preliminaries for Section 2
The Lipschitzness of the functions and operators in the Riemannian manifolds is defined as follows:
Definition B.1.
[3 Definition 1] For any x, 21, D2 E Uz. ys 91.82 E Uy where Uz x Uy S
M2 x Mg.
(i) function M2 > R is said to have L-Lipschitz Riemannian gradient in U2 if (f Gf(x2)lle < Ld(x11, Ø2).
17

---

(ii) finuciit f MM My is said to have L-Lipschitz Riemannian gradient in U2 x Ul if IIl ii (, (2f(2,y22lla S Ld(y (.y..12) V2), 119.f(1 y1) (.f (2) S Ld 82).
9. 32)
(.)((z,)))]l.. I Id(a11 02) and (19,](11.9) Gzf S
(ii)) linear operator ((r, v) M, + TaMe (eg. gnyg(a, y)). is said to be p-Lipschitz in Us x My if ( ((22, villas I pd(ar, 12) and [[ vn) - ((r y2 P S
p pd(y1.
(iv) a linear operator H(z, y) M,M, + My (e.g. Hyg(z,y)) is said to be p-Lipschitz in Ur x Uy if P H(x, V1 P H(r, v2)l I pdly1, V2) and [H([1, H22, y)lly S
X2).
Due to the curvature of Riemannian manifolds, the notion of distance differs from that Euclidean space. Accordingly, have the following trigonometrie distance bound Riemannian manifolds.
Lemma B.1 (Trigonometric distance bound [100, 99 32.) Let Da: Lb, Te E u S M and denote d(zs, Fe), d(Ea; Te) and e d(Ea, 2bb) as the geodesic side lengths. Then, holds that
a² S C(T, c)² + + (Exp (2s), Expr. (xc))
VF
is < 0 and <(T, if 2 0, and denotes the lower bound of the sectional curvature U [66] Section 3.1.3).
where ((T,c)
tanhi [Tic]
C Tangent space conjugate gradient algorithm
In this section, we introduce the tangent-space conjugate gradient method 81 10 Section 3.1
which is used in
Algorithm 2 Tangent Space Conjugate Gradient v" = TSCG(H,,(2 9,5
1: Let (ar E My y p r0
2: while 11Hyg(æ, 0) [0"] (z, 0) > c, do
3: Compute Hyg( (v")
4: a=
|r
1p
5:
wn+1 = + a p".
6:
n1l = -r" a
Hyg (2, 1)')
g1 |r
7:
1rm B
8:
1=1 p+1 + pm
9:
n -=
10:
end while
D Additional results of Section 3.4
Since the retraction mapping only affects the total number of iterations required for the lower- level problem Problem (T) to converge, without influencing the error bounds, the hypergradient approximation error bound (Lemma 3.1) remains consistent with that in Algorithm [] Moreover, analogous to Proposition 3.2 we establish the following upper bounds on the total number of iterations required to solve the lower-level problem in Problem (I) and the linear system (4)
Proposition D.1. Suppose that Assumptions 3.7
3.5 and 3.6 hold. Then, for any
< t S T, the iterations K, and N, required Algorithm sarisfy:
log(C (gg(C//b))
b
K₁ < log( 1 + +,,/ c,)C? (n/b - $12/52
log
Ey
18

---

Algorithm 3 AdaRHD with Retraction (AdaRHD-R)
1: Initial points Z0 & M2, M/o E My. and vp E T M, initial step sizes do > 0, bp
> 0, and
cn > 0, total iterations T, and error tolerances cy = 6 7.
2: for 0, 1, T do
3: Set l: and yf 1 K:-1 if and yo otherwise.
4:
while [1 Ø1, ve I[y Ey do
5:
b241 = by + [19 ut 1 y1 Retr of (- 1
6:
biei gug(2r,
7:
-= = 1.
8:
end while
9:
K2 k.
10:
Set n = and uft = pu No-1 ift >>
4-1
and dn otherwise.
M4-1
while R(Ee, V1 Kt
12 ke >
6n do
y1
12:
ci = c + V, V Ki ..,'
1/ a+1
R( Re Ue u.)))
Gradient descent D
14:
n= n 1. end while
15:
16:
Or set of = 0 and invoke of
TSCG
Hyg(ar, 26 Gyff v. uf, cx). Conjugate
gradient
17:
N₂ =n
(F(,,, u, No. 9of(re, (Ir, 2t sire)
g vi Mo,
18:
di+1 = of + || Vi Ki ,r
20:
T++1 = Retr,, (- 1 (Ft Vi (,,))))
az:1
21: end for
AdaRHD-GD:
N log (C2/c)) log(1 + Co/C?)
+ log
where Cb, Co b, T, b, 7 and { are constants defined in Appendix H
AdaRHD-CG:
4L9/ p.ee
VLg/ Viglu
N₂ S log
flog
2
E Extension to Riemannian min-max Problems
Riemannian min-max problems 44 attention. The general form of such problems is
[02
30 62 38
have recently attracted increasing
min max [xr y), M yEM,
(6)
which can be regarded as special case of the Riemannian bilevel optimization problem ( with g(x, y) -f(x, v).
g is geodesically strongly convex w.r.t y over My. the Riemannian hypergradient 3 reduces to (z) = (zf(x.yf y (z)), and the approximate Riemannian hypergradient becomes GF 9) =
G.f(x, 9) The pseudocode of the adaptive method for solving Problem (6) is summarized in Algorithm
Before establishing the convergence result of Algorithm we present the required assumptions.
Assumption E.1. The following conditions hold:
19

---

Algorithm 4 AdaRHD for Riemannian Min-Max Optimization
1: Initial points To E Ma and yo E MMg initial step sizes dg > 0, and bo > O, total iterations T, and error tolerance Fy = T
2: for 0, 2, ..... T do
3: Set = and initialize uf - 1/-11
K,-1 if 0, otherwise y/ = y/-
4: while (1 v2 > Ey do
5:
Update 1 = b8 + ( v Ill Vi k+ Expyt
6:
Gugle )) (- bets gug(oc, k+1 Retry!
Gug(ar:
7:
or Ur
retraction step
8:
+ +
9:
end while
Ke + k.
Compute FF ) gef yrr))
12: Update ui+1 = of ( 31 )lea
13:
Jt+1 ExPa,
(I (-1 (1()))
1 Ge4s
14:
or 2++1 = Retra
L (I (11)
retraction step
end for
(i) Assumptions used);
3.1 and 3.4 are satisfied (Assumptions 3.5 and 3.6are are required when retraction is
(ii) f(r y) is continuously difserentiable, and fxx is geodesically strongly convex y (ii) fæx y) is L-ipsscht continuous, and its Riemannian gradients f y) and gy (x, v) are Li-Liccchttz continuous.
We now state the convergence guarantee of Algorithm
Then, the sequence {xi]T generated by Theorem E.1. Suppose that Assumption E. holds.
Algorithm 4 satisfies
T-1 Σ
< Cmm = (
(IF T 1=
T
where Cmm is constant depending the curvature, Lipschitz, and strong convexity parameters. Moreover, the overall gradient complexity of Algorithm As (11/2).
F
Preliminary results for proofs
Lemma F.I. 90 Lemma 3.2] For any non-negative 01, OT, and 0i 2 1, we have
Σ
<
log Σ aq
+
-
04
Lemma F2. Suppose that Assumptions
3.1
3.2 and
3.3 hold. Then, the following statements hold,
(1) For 1 B2 E Ma it holds that
d(y (x1). yf (x2)) S L.d((11,
where Ly b- Le and (x) is the optimal solution of the lower-level problem in Problem 1
(2) The Riemannian hypergradient (x)) satsifies [[FF(z)]l= & 1 Lg/H) and for Fı, Mn it holds that
(GF((11) - (F))(( S Lrd(x1,22).
where LF == (L, + phz 11 (1 Lg 2
20

---

Proof. The proof' of Lemma F.2 can be derived from 28 Lemma 2.2]; here we provide them for completeness.
① For 21,42 22 E Mz. there exist two geodesics c : 10 + My and c2 : [0, 1] - Mr such that
( = y" (c2(t)) (c2(()) for t E [0, 1], and cz(0) 31 c2( 22- Then, have
d(y"(x)) (x1). (1z)) = J." || (t) ! [ID=
Lo
1 L: (c5(())lez(()dtt
Lu d(z), 22).
I where the first inequality follows from (x) : -H g(z, y (a) (a
2 By the definition of GF(x), from Assumptions 3.2 and 3.3 it holds that
g( [[) = [ (z)) Gzyllz y (x) 90 (x) (x))) (x))ll
= -119//(0, (x)) + 1 y (x))l s(,, wtw.:////ll.olaoaoo/ooo/l/////// (x))ll S11 + Lel
Furthermore, we have
( - GF(x))l2
< PP - (12))lo,
+ P v1 Byg(az v' (22)) (xa)
of (m1) laz [ 9( (((1,,"(<x))lll (2:))ll 9yf(x1, (x)))ll
+ 12,0(12,) (12))
p 21 g( (an (a1) (mt) H. (1'') (-(-2) |9 (m))))
+ 1 ( (12) |45" 9 yf ( (x)) /e - (12)) (12))
By Assumptions 3.2 and 3.3 for the first term of 7 we have
[P:9af(e1. Gaf(22, 8" (x2))llzz
<100s(m1 G. (x2)) ( + +1P ( (x2)) GnI (122))l
<L,d(yy (I)d))"()1)))) (x2)) + + ((), (LrLe + L1) d(x1)
4
We then consider the fourth term of we have
py p enf (x1)) - 9,f(22, ( (12)
py (21)) 9,f( ( (x()))
+ +19gf(211 ((21)""(22)) - Gyf(222 v² (x22)))l
Lاsا +bg 2(2
1
For the second term of 7 we have
1 y (z1) Lzg((2, v (z)) Pp (0z) laze
<IP g g (x (x))) ((s)
(mi) P 20 (22)))
v (x2)) g0 y² (12))
pLg +p) d((1)22). 1
<
For the third term of 7. we have
(p3)) H g( v (z1 v
(21))
H.y g( v vx2))) v((2))
< Hy g( v (x1)) H g(æ2, y (x))) ((())) (=())) + || (p)) g(02, v (x:)) (-(2)) -H, "(((22
-H,'s(12, v" (22)) (
<
p
+
pLg
2(z1)22).
21

---

where the last inequality follows from the operator norm satisfying
- -- = [B A)A s || - - BII.
(8)
Combining the above inequalities, we have (F()))())) G (F(22)lla
Lo4n + L1s
pLg d(11, 1
d(I),
p
1
1
وLg 1ra
[Lshig
+ +igh
d( d(
lig)
d(22,
1122
1
L
4
pLg +p)
+ وLg
+ Lg
(Lybg Ls )d(
+ Log
+
+ Ligاs
"
1
1
112
us
1
= Tug p4z
(+
Leg
d(x1, 82).
1
The proof is complete.
Denote v² (x) ;= arg min min R(x, v² (x), v) and 6* (x, arg mi,, R(x, y, V)..
Lemma E3. Suppose that Assumptions 3.7 3.2 and 3.3 hold. Then, the following statements hold,
(I) The objective R(x, v. v) is ju-strongly convex and Ly-smooth w.r.f. o;
(2) (x() satisfies ||0" (x) S 1 and i (z, y) also satisfies | (ll, S 4: n (3) For 22, E Ms and y1, 322 My. holds that
[0((z)) ( (x1) "o""(aa)'"" (12)
(x1)) S Lnd(2x1, 22), and || (1, - 6 wa)lla) S (nd( by ye )1 + Iny) and L, 1 + 1
(m2)))
where La := ==
1pp 122
Proof. I Since V2 y, v) Hyg(s, y). the strong convexity of R(x, y, v) follows from
Assumption 3.2 Then, by Assumption 3.3 for v1, E My we have
V.,((, v1) v R(a, y, lly & [H, v)llullu - 22l1y S L0ll11 -2lla-
2 For 0 (z, y). we have
V.R y, (z,
x) Gyf(2, 0,
which demonstrates that
| (x, (2, w)l,, ||H g(x, y) (z, (z.v) - ||, g(z, I|, 115yf w))l S 4 Since 0"(x) satisfies u² (z) 0 (z, y (z)). the desired result follows.
p
1 By the definition of 0² (x:). we have
1" (z1) (er) (22)
(01) o0 (x2) (m1)
H., g(21, y ff ( (21)) H,, " (22)) 9 (x2))) v(()))
The remaining proof is similar to that of Lemma F2 (2). thus, we omit it.
By the definition of 6*(x,, v). we have
||0 (I, Piu 00 (z. 1e), || (1,,,,), P H. g(z, 12)9,f(2 (x,,v))l1 12)
< |1, g( (z, - p I (z, + " 2(.,2))PP Hy glx, vz)) Go (x, (2) g1
S Ttf "'d(y) v2) + 1 P d(y,, y2), 2
"
where the second inequality follows from
g
22

---

Lemma F.4. Suppose that Assumptions d(y, Ki ,y' (x+))
3.1
3.2 and 3.3 hold. Then, for any t 2 0, we have
yy n?
and I' 6* (12, (
6n n1²"
ve
Proof. According to the termination conditions of Algorithm for the lower-level problem and the linear system, we have
(e V/ Ke) )1 y.
Eyy, and R(,, ve ) S Ev.
By the strong convexity of g and R (cf. Lemma we have
d d':i' k. (x+)) - 112 Geolar, ( - (z GuD (2c.
vr 112
and
U - (21, | S 122
V V. Mi , - V.R (22.31 Ke ,0' (x vi
|1 S
422
where we use the definitions (1 vf (x+)) and V tee Ve Ki, (1t, Ki) 1| 0.
Lemma F... Suppose that Assumptions
3.1 3.2 and 3.3 hold. Then, for any 2 0, we have
(Ft, ve o )² I C7:
where Cy (2 n²²
12.1, + 473)
$
Proof. By the definition of FF, we have
F Ki 1z )1?
@F( Kr, 2 - gF
- Fz v Kr, ,0 )
|1 + +2 22|0F xs Kr, o0 " b1
2
-2
P
vi K1)
( - 8* 00 u/ )| +
1iy) - P Peyo(ve. (0), (21.2t ))
2
1t Ki
||u," - 6" (0 vt 11 + A11 1h (0) + 41102 vi yo (2res ve )
2
4L212
417
12
n22
where the last inequality follows from Assumptions 3.1 3.2 3.3 Lemmas
and
G Proofs of Section 3.3
G.1 Proof of Lemma 3.1
Proof. By the definitions of uz (mt) and 07 (It,, )), we have
[ Kr (No) - (x:))l....
< 5119,S(mt, vi (z y² (1r, + 1 ())o Poyolse (ax)))
ST.dd(ut' " (xx)) + , v,, ue K.) 1o,, 11 pur
( (tre)ll
+11 w k()) Gryg( 1/" (ox (xr) (mx) Me. 112 (4x)lly
<Lyd(ur y (xx)) + 1, - p (Z (xx) (x=))) + ellvt (so)lo .y" (xx))
< Ly + ااع d(u . (xx)) + Lollou p Ki
Ca of (1:),,
(9)
23

---

where the third and fourth inequalities follow from Assumption 3.3 and Lemma F.3
respectively.
For llug pu (mr) oi (Iz))l
Me,
we have
llug Ni - (mr) Ke of (xx)))) Sllut (1 Mi ( I1 + 110g (2te; 1)
pu (2t, (x+))))
(+++ 4P
< o7 (m vi )1 +
dlutir,'' (x,)),
12
where the last inequality follows from Lemma Combining this result with 9 we obtain
F.3 1 and the fact that uz (xt) = b7 (1x, y² (st)).
(L, plz d 8" (xe) Lo Lol1o, -p of
[ (a k ) GF(x))la. -
1
Lig pls
d(yi " vx())) + Lg ||u, (x Vi a )1 + Tus + lsp)
d(yt' ( (x()))
$
122
L, + 4p Lg
[L + 1p
d(y,"', .y" (zx)) Lollu (1 ve )1
4²
The proof is complete.
G.2 Proof of Proposition 3.2
Inspired by Proposition in (93 we first give result that concerns the step sizes de, by, and Gu.
3.7 3.2 and 3.3 hold. Denote {T, K, N} as the iterations of (x.y. y. v}. Given any constants C. ag. C by C. 2 cu. then, we have
Proposition G.1. Suppose that Assumptions
AdaRHD-GD:
(1) either at S for any S T, or 3h T such that at, Ca. 0ti+1 Cai
(2) either by S for any k < K, or 3k K such that by, S Ch. bky+1 1 Cbi
(3) either ea S foror any n S N, or 3ag S N such that Ca2 S Co Guy+1 > Co
We then consider the case where Therefore, we do not need to consider the step size Ca.
the conjugate gradient method to solve the linear system.
AdaRHD-CG:
(1) either S for any 1 1 T, or 34 S T such that ar S C.. 0t1+1 > Cai
(2) either by S for any lo S K, or 3hg S K such that bv, I Co, bk, +1 > Cb:
G.2.1 Improvement on objective function for one step update
We first define threshold for oz:
C. = max max (2Lr, 0o)-
(10)
Lemma G.1. Suppose that Assumptions 3.1 3.2 and 3.3 hold. Then, we have
(1 (1-
LF
I th v M.. + fy.0
F(F441) S F(x.) 24,11
201+1
a441
20
(11)
Furthermore, if in Proposition G.I exists, then for any 1. 2 L1, we have
F(I411) < F(x,) 20111
1 [F(I, Vi
NN +
Cy.
(12)
4a
20
where Eyp f (Ey + Ev) and L : maxf V2L1, v2Lo} with Lı is defined in Lemma 3.1
24

---

Proof. Combining Lemma F.2 and Proposition 2.1 we have
LF
F( <F(x)) + (z)())) Expr. (#(+1)) x2 + d(
2
=F(x)) 1 (FF(x.). OF (I..Vt kt, w/tt))
+
LF
9F
Fe Ki
11:
2a
at+1
=F(r)) 2a++1
||gF(x>))lar
1
|r
Ni Tt. De ,14
11
20t+1
1
(F(()) .F
(zL, Ve
Ke .
LF
|F (Iu.1 12 )11²
2a,+1
205-1
=3()
[19F(x))l..
1
1
LF
2as+1
2at+1
as+1
(F((z) GF
(Z1.
Ke uz
)12
(13)
20,+1
By Lemma 3.1 it holds that
[F(xx) gr (1x, Di
-r
Ke u )|
5213 1f (x+)) + 21, (1104 -D (as) (xt, (xx)) (1x))
<i² (d v2 (xe) + 11 Pile (2 (0 (x=)))))))))
Therefore, by Lemma F.4 we have
GF(2.) GF (2. 21, (2 Ki u )|
1.2 (ey + tv) Ey,o
4
This Combine 13 deduces the desired result of 11
If in Proposition G.1 exists, then for t 2 t1, we have a++1 > C. 2 2LF. The desired result of 112 follows from The proof is complete.
Then, similar to 193 Lemma 8), we have the following upper bound for the step size d4. Lemma G.2. Suppose that Assumptions exist, we have S C. for all i < T.
and 3.4 hold. Ift, Proposition G. does not
the ln Proposition G.1 exists, have
at <Ca;
15 11i
2g0
at SCa + 2Fo +
t> f1.
ao
where
Lr
Fo = 2 - F*)
(14)
Proof. tt in Proposition
G.1 does not exist, then for any S T, it holds that S C..
tf in Proposition G.1 exists, then for any t &1, it holds that a++1 Ca. By Lemma G. for any
t 2 f1, it holds that
F(I41) F(x))
1 (F K. , NN
+
Ey,y
20,-1
4a
201+1
Removing the nonnegative term 201+1
19F(()))
have
[ Ke. 2. 112
< <4(F(z)) F(I++)) + 26y."
(15)
a+11
a++1
Summing 15 from t to 1, we have
[ (z v. K. N. 112,
26y.0 4 (F(x), F(2
26g.
4
(F(z)) F(x411))+
04+1
ai+1
G++1
K=b
t=h
1=h
i=1.
(16)
25

---

For F(zr),, by (II.. we have
( F(xo) + Σ
4-1
LF
Ki ,
41
Ey.0
Di
2
24i+1
==0
This combines with T6). by F(x++1)= 2 F", we have
( v, )
1 4 (F(zo) - F*) +
4
2L
[ vi
K1, 20 Ml
2f
a--1
a++1
1=0
<F(((z)) 1²) + 2I. Ei [5 Mi Ki No
)
af
ditl
<4(F(10) - F*) + 2L p
2(t + 1)Eg < <4(F(w0)
2L
2(t 1)e,,
+
F²) +
+
oj
ao
og
Since of = at + [1 Vi
Ki, u )|2 we have
[ 3/ K 22
Ni )1lee
F Di Ke ot )1. S dr1
| (2 Vi K.
)1
d141 =
ax
01+1 + at
a++1
a++1
SCa 4 - = 2
2(1 + 1)e
+
(17)
ag
The proof is complete.
Similar to (OO). we define the thresholds for the step sizes by and en as follows:
C = max
Lg / ..0..
Lg
bo). Ce = max cof.
(18)
Before proving Proposition 3.2 we need two technical lemmas.
Lemma G.3. Suppose that Assumptions
3./
3.2 and
3.3 hold. Then, we have
8 (st
k+1 n² (xt))
s
1 +
CT2
1
dlvi v (xx)).
02
k+1
bu+1
Proof. By Lemma B.I
have
( ( ,y (xx))
(19)
2
<d (x))) +
011
o/ + (g Exp (x1))
b
bu+1
<d x² (x+)) + G11ggg
M1 + buul
2
(g(xe, g( (t) 4 (v
b
1
C
df
v (x))).
bx+11
where the second inequality follows from the geodesic strong convexity of g, and the third inequality follows from
GGgg(e, 11 19 utt put (u,) (x))))
(vi
The proof is complete.
Lemma G.4. Suppose that Assumptions 3.1 3.2
and 3.3 hold. Then, we have
1
(gyg(re.)))) ui), (u (2x))) S
1 (xy, vi 11/
2I
26

---

Proof. By Assumption 3.3 given any My. it holds that
Lg d of (v/
g( (x:)) S g v) S g vt) (gyg(rr, vt), (x)))(()) +
(20)
2
Taking - Ex -- to Gug( ut)) in 20 derives
g( y² (x+) S g( vtt Lg (ggg(Te, at 11
7.g
Gyg (2 2/)
g( vtt) 2L,
11 vt Ma
2
Lg
which demonstrates that
g( v² (xx)) g( 2t)
2Lg 2 1gng 20 1li
-/1
1
(21)
By the geodesic strong convexity of g w.r.t. we have
g(E,, V.e.)"((,)))) - g vt) 2 (909(xr: v)) Exp, (v" (x))))))
This combines
21 implies that
(g vt) Exp,, 22 (y (st s gla,, (xe)) - gl v/) 11 sf Mig.
21g
The proof is complete.
Proof of Proposition 3.2
Proof. For AdaRHIDGGD, denote
log(C? (bg(C//b))
b
K log(1 t2,////// /2) (w/b- - CL /22
log
(22)
Cr.
and
log(C%/c3)
N gd
log
(23)
log(1 Cc/C?)
M
where b
max Lo (b)
1}. ē
max (Lgle
Cc), 1}.
b
C.
2T.
28y
2g a2a
+ log
Cb bo
+
with Cj =
213 n¹²
+
41
+ 11?
is defined in
12a
Lemma F.5 and ē = C. Lg
2
+ 812
+ 2 log
Co 1).
For AdaRHD-CG, denote
4T.11
LLi 1
Nog = 2
log
/log
pree
VLg/p11
We first show that K, S. K for all 0 ST.
If kj in Proposition G.1 does not exist, it holds that bk. s Cb. By 192 Lemma 21, must have If K, log(C] (12)
K, <
log(1tc./Cg) /CF since [1 vt )| 2 Ey and by S C. hold for all
log(1+c,/Cg)
k < K", we have
(
19 vt ||2
b4. -b, + 11 1
b
1+
ve
62 1-
log(CR/66))
K,-1
119g9(1e, wt
Kr
((1+
1/ logg1+e,//C)
bg
II
1+
2 by
1
Eg
> b/
Ey
-
by
C/
k=
(24)
which contradicts 6x, - Cr.
27

---

If 11 in Proposition log(C]/b0]
G.1 exists, then, we have by, S C2 and bk > Co. We first prove l -
(C)
If k1 log(1 (CCC)))
similar to (24 we have
log( (lg(/+//CC))
cg N1
1
C
which contradicts bk. I C..
By Lemma B.1 and the update mode of 3/2 hi we have
dg (x:))
(0g(Te: Vi 1)
<d((v ,y()))) +
2
(Qug(oe. 11) Exp Exp 11 (1ze)
bki
Dkn
11-1
(a)
geg Vt 1)
I <y( -1 100011100 (x+)) +
2
(g(xe.)( g( 1 11 cP - (a))))
Oki
bks
( Vi 161-11) 112
19 11
Sd 1- "00 (x:)) +
= d (vF. (2re) +
62,
b
k=
(6) Ki-1 "'"((x")) (xx)) +
11 u 112;:
S 201
Ei=o 11 (1e, vt /b8
19 vt 11be
(0)
2dd (1/ K-- "6 (x + 2d (y" (IC- ,), 3 (z+)) + clog
+
bg
No-1 ) |12kg-] ki-1 24 P vi-1
Ki- -2-
(4) 2cy 112
(I1-1:
h
19 (
2 31
Uo-1 + +c <log
+
12207
km
(e) 2cy n12
22
(bb
+
+ 2Ç
+ 5:
(25)
bo
where (a) follows from (2). (b) follows from the warm start of vp (c) follows from 10 Definition
10.1] and Lemma F.T (d) uses Lemmas F.2
and F.4 (e) follows from Lemma F5
and bbg
Co.
For any K > k1, by Lemma G.3
we have
( v (x:)) s
11
d dvt K-1 K (x:))) se
(
-
(K ks)
(0,00())))) (x:)
bK
6
(K
(K- k1)
2cy 112
22
Cb
<e
+
2s log
+ 5
(26)
bo
where the second inequality follows from bx 2 C. 2 2C
Lg and - x S e for 0 < x < 1,
p
- < 1
specifically, when bx 2 2 g it holds that 0 <
bx
< 1, and the third inequality follows
from (25)
Similar to 17). we have
1 Vi K- |1-
11 (efe.//))) D1)
w/2 < bbg
by = bx-1+
(27)
dy + bb-1
bx+1
Moreover, by the update mode of y and Lemma B.1
we have
2 (Cuoleeeii -1), Exp Exp 25 y1
1 (Te, Vi K
1112
(u(K)) S d -10k-1 (xx)) +
b%
bx
28

---

sd(1 "0 -2(()))) + ( 20, Vi
">1
(1 vi 1K-11 "1p
21
b%
bx lig
"00 (xe)) + (2r 81 K- "k1= -1
110 Vi 11 25
of
2bx 2bx(L1 Lg
bx Lig
(1 - //2Lg)
11 31
111
K-
S dl dl k1 22' (xx)) (1-11/2) 11/2Lg)
19999( (Te v/I1
<d K-1 ,00
(x))) (,0"~1,,""(x)))))
Lgg
bg
Lig
b&+1
(28)
where the second and third inequalities follow from Lemma G.4 and bx 2 C. 2 2 Lg tively.
respec-
"
By
25
,, we have
K
[
1
stag
(d(()) 30 (xx1) - dlyt" yy (si))) S Egg . (x+))
2gg
bx+1
k=
26y 122
20204 1²ag
+ 2ç log Ch
t5)
واك g
+
bo
Then, by 27
1-p/2Lg S 2, and bRs S Cb. we have
2cy 112
2L307
Cb
bo +
bK S C. + 2gg
+ 2 log
p2az
Denote b = C. 2g
26g
2 + 26 log Ca )
+ (). We need to show that $ - - 0.
12
Under 26 considering the monotonicity of t 0
6z w.r.t. b when 2 25Ing Lo it holds that
1.2
- نつج
12 as b > bk 2 Lg 1
La
Then, we have
bx
d (1 y (xx)) se ( - (K (K-k))
2Ey n12
20207 12ag
Cb
+ +5) =e - - (K (K-kk)) b- Ch
+2clog
bo
21.
(29)
Since 1 S Tog(1 /C,) by the definition of K in (22). it holds that K > Ki as b > 1 >> Ey.
log( log(Ch CZ/b1)
L, Ca) 1, it holds that b in (2)). Then, by (29 we have
11 vf MB; ELzd , se (1 6 (R-b) k1) I, (
2
(a) - (x-c into-c1z705 lox 1 Lg - Cb) Se
(b) -
(
log (1)
(116-223785
Egy
2
(30)
where (a) follows from the definition of K, and (b) follows from L,( < 1.
Lo(b-Co) > 1, it holds that i Lb(b-Ca) C.) in 22 and we have
2
119ys(ae, M1 S1Z0P0R R .v (xx)) Se - (1- (K- k.) L Lb(b 1y6b-C Cb)
(
2
Se - (016-c1z/05 log( (2(0- L.g -Cb)
Cy:
(31)
Above all, we conclude that after at most K iterations, the condition || vi M138 S cy is satisfied, i.c., K. < K holds for all t > 0. We complete the proof.
29

---

AdaRHD-GD: We show that N; S ge for all 0 5sts T.
If ny in Proposition does not exist, we have CN. S C.- Similar K2 of the lower-level problem, we have No < Cog())/c)) hold for all n < N2, we have
If N₂ log(C)
log(I+t./C2) C,)) by IV R(r,, Ke =1)) x. 2 cv and cn Co
[og(1+eu/Oo))
R.R,, Ve Ke No- - 111
NN N. +
VIV
K+ vi Di
)1
CN.-1
1+
y/
N--1
|V 10,
Ke,
20 II ==0
1+
c
1+
Ev
C
C?
which contradicts ON, CCo
If 71 in Proposition G.1 exists and N₂ n1. Then, it holds that Cn. S Ce and cns+1 > Co.
Similarly, we have n1 S log(C2//33 log(L+e./CC5)
By the update rule of have
vt tn and the definition of is (x1, K() = arg min My R(Fe, Ue Ki ,)), we
1 n2 - 0r (xe: Vi ukk
111
1/
V R(
Vr " uft11)
-" (Ie, Be Kee)
Gp1
Nx
og 1- -1 6* (z 1/ (()) =1/000 +
V VollIe B K. 124
12
Cp1
41
8" (22. ), V. R(2,, Vi
22 131
(a)
-1
0" vi x 1111 +
K: V R(a,, V1 , .06 1
1
Gni
R3.
R( V/ Ks u (1
V.R D1,, (i Ve Ke 00 (xxe ve
cn, Lg
2
1 1
8* (Iee Vt
K1)
|| +
V R(R, vi , 1if1 1
Cn
V R(xe, Wr o
M 19 0r (2t, Vc
+
n=0
Cy1
Kx
pu
1/-11
K:
ke-1 1/-1
No-1
8r
(Ie: Ki)
n11
Zimo | V. V
VV V K.
K.
) 112 /03
v1)112 /
N1-1 - 0 (0 Vt-
2
+2
8* (1111,1)11)) p"
K(-1)
K
0¹ (x
Vi. Kr
Ki-1
8--1
n1
+ log
Σ
|| o R( De Ke
+1
<2
1 1
K:-1
6* (II-1,
Ur
Ki K + 4 || 00 (20-1. vz- -1 1| xx + +
+
b,-1
+ log
|| R(xes vi , k2 /28
+1
30

---

(4) 2e
813 2 log
Co Co
+
1.
(32)
12a 122
where (a) follows from Baillon-Haddad Theorem 2E E My, it holds that
4
Theorem 5.8 (iv)], i.e., for y My and
(w- (*t,)) V. v( V R(a,, of (f),)))) I.g
R(r,,, V.R (r (
(
(33)
(b) follows from the warm start of eg. (c) uses Lemma F.I and (d) follows from Lemmas
F33
and
and Cx. I Ce.
Then, for all N > n1, we have
N 1t 0" (2 V/
K:
K.
.z Ks " 2 2 - 0 ( (xrssee)) Dr,, V R.R( Ve
1))
V
R(x Vr
N-1 8 (are; V/2
Ki)
#1
2
v/a
c2
On
(6)
N 6* (are: 1/1
12
1
4g
< 1/
(uN-11 80 (x vi K:), V. R.., Ke un 22
On
Gn
N 1 0* (xe; Ke)
1
- 0 (xx,, ve ). V. VollIa vi ot 1/2-1) kkc
Cn
11
1100
N-1
00
0"
1/
K:
(d)
e - 1::0 6r (1e. Kr 113
cn)
Kt
(e)
Se M(N mnl/ee
2EV
81?
2
log
Co
+1 )1)
112
n
Co
where (a) follows from 33
(b) follows from Cn C. Lg. (c) follows from
V,R(E, Dt 00 (x Vr
K+)
0 and the p-strong convexity of R, (d) follows from en 2 Co 2
Lg 2 μ and - x S e for 0- < 1, and (e) follows from 32
Similar to 27p. we have
|V & De
Ke ot NN
112
N-1
V R(r.v K. , .
CN = -
ye S Coy +
Σ
(34)
+ CN-1
Cn+1
R=B1
For the second term of (34). we note that
V.N 8* (01,,, v ?
V R(a, ve
K.
2 2 00
ve k*), V R. vi uu 12N-1)
1/ N1 11 80r,, Ki)
2
+
CN
| R(r, yi , (i
< 1/ N-1 -- 8 8* (ke)
+
2
V V.ll(ar v1
1 V,R (Io at - (x wh k::))
113
cn Lgg
V R(ra,
N
80 tt kk.
|13- 1,
1/
LN
2
V R(I, Ue Ki, 182))
8d
(Ier kr))
1/
Go 1 Lg
31

---

where the first inequality follows from (33. and the second inequality follows from oN 2 C. 2 lig.
Then, by 32). it holds that
V Rari o oz)) 11
N-1
(1:30-
Σ
S bu
0 - V1 k3)
- 100
(z
Cn+1
1,:t
11771
<4g o/ 0* (Ie, Ve 1 $1 v/:
26g
8/2
C₂.
S Lig
+
+ 2 2oo
+
112
4²a
Co
Combining 34
derives
26g
812
Ce
Gu S Ce + Lu
+
+
log
+ -11
122
42
Co
Denote ē: Cc Lg (az
2ty 817 + 2 2log
( +1)
Then, considering the monotonicity of w.r.t.
we have
| 0* ( v (e)
111 1 Se Se
2cy 112
817 1
Ce
+1 =cMl--nn))/ Ce
+
21og
2
cp
Lg
Since n1 < (og(Ce/cc)) by the definition of Nud in 23 holds that Ngd > n1. Then, similar to
log(I+en /2))
330 and we have
| R( Ve
od
S L3 uf - vi v/ |13 ug se-m(Nur-mit Lg 1 Cc) S Ev.
where the last inequality follows from the definition of Nga. This indicates that, after at most Nya iterations, the condition ./V. ve > I c is satisfied, i.e, No S Nya holds for all
t 0.
AdaRHD-CG: We show that N₂ < Neg for all TT
Denote Kg Ly From 10
Equation (6.19)], given E M2 and vi E My, we have
Kg
2N.
Fi
2N.
17 42
||u," 07 (zi, 2 N M1 S 4kg
| 07 (x V b )|3
VKg
//ig +
where the last inequality we use the setting of that ig. = and Lemma
F3
Then we have
12 V. vi on 11 s 1311000 (* (i 112 I 4x 4kg L33
(ig
-1
422
/Kig
which implies that, after at most Neg iterations, it holds that || R(1 vi
tr, vi
S ev. where
ve
1 Nog =oogg log
Arig 12g2 uiee
Vigg +1 1 Whig - 1
VVlglet VTg/u111
/log
log
/lo
We complete the proof.
G.3 Proof Theorem
Proof. t in Proposition G.1 does not exist, we have S C.. Then, by (11) in Lemma G. for t < T,, we have
[
< 2((((x)) ((((2))F(((+1)))
+
LF
[ K= os ) + Cy.v
0++1
a
a++1
32

---

where Ey.o is defined in Lemma G.1 Summing it from t = 0 to T - 1, we have
[gF(x)))
2
(F(zo) F(ær)) +
LF
T-1 1
FF
Ki o.
1
+
1
7-1
y,0
T
ac+1
T
06
2
T
T
d++1
t=0
1=
1=
1 T (FFzz) F²)++ +
LF
E,1
Fu +
+
(35)
4
40
T
an
(t where the second inequality follows from Σ ||9 defined in (1)..
Vi
).2,
I al S C. and Fg
If in Proposition G.I exists, for any 11, by in Lemma G.1 we have
[GF (3)))
(F((2))) F(x++))) +
LF [ Di
Ki v )
6.0
(36)
0++1
22+1
a++1
For any t 2 t1. by
12 in Lemma
G.1 we have
[[ < (F(xx) F(x2+1)) + Ey.0
(37)
at+1
dc-1
Summing (36) and (37
from 0 to T - 1, we have
FF
(2t)
[9F(
(F
T
0++11
T
Gc+l
a++1
t=0
S
1
Σ 2 (F(xz) -F(+++))
LF
f--1
@F Vi
Ke
T-1
Σ
Gy.v
00
1=0
22
ac+l
7 (F((r)) F*) +
LFC²
Fo
cyee
af
ag
T
ag
where the last inequality follows from Assumption 3.4 and as, S C., and Fu is defined in Lemma This result equivalent 35).
G.2
Then, since ac+1 S ar, by Lemma G.2
we have
Σ [GF(())) <
Ey.v
S
Fo
Cy.y
)
(c. + 2F% +
C.
2T 2Tey.
(38)
T
T
ao
Since 6y 1/T and 1/T, by the definition of cypu
f (cg Ev) in Lemma G.1 have
Then, by the definition of Fo. 38) is equivalent to Tx²
212
T-1
(Fo + 2T.² 22.2////// ( (Ca + 2 2Fo + 2T. / /am)))))
= =0
Σ
(GF(21)),, <
T 1=
T
Let C := (Fo + 21 (C,, 2(F agpe)
21 )). The proof is complete.
agn?
G.4 Proof of Corollary 3.1
Proof. By Theorem 3.1 have
T= O(1c).
For the resolution of the lower-level problem, we have
1 log(1 + -0
-
K,=
Similarly, for the resolution of the linear system, have
AdaRHD-GD:
1
N,
33

---

AdaRHD-CG:
For consistency, we retain the N₂ = O (105
Then, it evident that the gradient complexities of f and 9 are ; 0(1/c) and G, = ((1/2). respectively, The complexities of computing the second-order cross derivative and Hessian-vector product of JV, = (11/)), HV, 0(1/62) for AdaRHD-GD, and HV, (11ee) for AdaRHD-CG, respectively.
H Proofs for Section 3.4
This section provides the proofs of the results from Section
3.4
notations introduced in Section 3.3 such as Ca. Co. Co. etc.
Firstly, similar to Proposition G.I we first give lemma that concerns the step sizes d1, bb, and Ot.
Proposition H.1. Suppose that Assumptions 3./ the iterations of (a. V... Given any constants C.
3.2
3.3 3.5
and 3.6 hold. Denote {T, K, N) as
dg
Cb
bg.
Co then, we have
AdaRHD-GD:
(1) either at S C. for any S T, or 3t T such that at, Ca. 0t > Cai
(2) either b, S for any t S K, or 3hg S K such that bR, S Cr bkit1 Cbi
(3) either a S for any t S N, or 3n S N such that Cn. S Cc. Cni+1 > Ce-
We then consider the case where the conjugate gradient solves the linear system. Therefore, we do not need to consider the step size C,.
AdaRHD-CG:
(1) either 0, S for any S T, or 34 T such that a,, Cas Ut > Cai
(2) either by S for any t S K, or 3kg S K such that bj, S Co bk Coi
H.1 Proof Proposition D.I
H.1.1 Improvement on objective function for one step update
Similar to Lemma G.I
we have the following lemma. Lemma H.1. Suppose that Assumptions
3.7
3.2
3.3
3.5
and
3.6
hold. Then, we have
F(E++1) S F(x,)
1
[9F((.))
1
LF
[L ke No )12 +
Ev.v
2a,+1
20,+1
ax+1
20,41
Furthermore, if in Proposition
H.l exists, then t 2 t,, we have
F(x++1) S F(x.)
(IF
[F De Ki un 112, +
Ey,
(39)
204-1
4a++1
20
where LF (LFCu + 2cR(1s + Lg)/ Cy.v
L2 cv), I : max V2(
(c
++
I
'16
n
a
(re), (T and Cus en are defined Assumption
3.6
Proof. By Lemma F2
we have
LF
F(r+1)) s F(x:) + (GF(x:), Expe, (1)
2
LF
=F(n)) + (gF(x:)) Exp=, (a++1) Retr ( (1(+1)) + (GF(r)), Rotr,, (etr)) + a(0141,
<F(1t) + +cR 1 (1 |Reetr (I++1)12
(GF(x)) ( ,1N,))
a++1
34

---

+ Lecu 18F (11,311, 2²))) ",,",,,;") 112.
20
<F(())) + CR (1y (1 18F (I ui u/
11.2
Lpcu 11 ( w6 20
, lla.
lit1
1
[FF(a))
1
1IFF (i
Ke ) 11
1 |[FF(ze) 9F ( l1
at+1
ac-1
a++1
1
Lpcu + 2en (1y 14 (1gg/H1) 1 (GMa, of
=f(x))
|9](
1
201+1
20c+1
a141
1
gT(zz) - -ΩF (1r, Vi ,1(
+ 201+1
<F(1))
1
[gF(()))la
Lpen + 2en (1y 1g bslig/t)) [ Ve K. ,0 ,0t )1. +
cy."
201+1
201t1
at+1
20s+1
(40)
where the second inequality uses Lemma F22
2
and Assumption 3.6
I in Proposition H.1 exists, then for 41 we have a++1 > C. 2 2(Ire + + + +lggg//
The desired result of (39 follows from 40
The proof is complete.
Similar to T0 we define a threshold for parameters o, when giving an upper bound of the step size ag.
C. == max ao).
where LF (Lpc, + 2cRlly + l/ggg//)) is defined in Lemmas H.I
Similar to Lemma G.2 we have the following upper bound for the step size ag-
Lemma H.2. Suppose that Assumptions 3.7 3.2
3.5 and 3.6 hold. Iftt in Proposition H.1
does not exist, we have at I Ca for any i c r.
there exists
S T described in Proposition
H.I we have
0g SCa:
5 f1;
2t
at SC, 2F% +
2 t1.
a0
where we define
Lr
Fo = 2(F F*)
(41)
aB
The proof of Lemma H.2 closely paraliels that of Lemma G.2 with Lp. Here we of
requiring only the substitution of LF
we present the following technical lemma when substituting the exponential mapping with the retraction mapping.
Before proving Proposition D.I similar to Lemma G.3
Lemma H.3. Suppose that Assumptions 3.7
3.2
3.3
3.5
and hold. Then, we have
( k+1 (xx))
<
1
+
df &lvi (vi.v' (xz)),
02
b
where Ç = (Cuu 2DCR.
Proof. From Lemma B.1 by the definition that Retr k+1 of Dc
Gg( v we have bets
d Cuitt (xx)) df (wt. (xx)) Cd 11 -2 (Exp, - k+1 Exp of
2 (are)
nr of vt k+1 Exp (1x))
<dl(it (xx)) + Coull M2s - 2 (Exp
Retr -
+ 2 bx+1 (gvo(me Exp, y² (2x))
35

---

(d(iiv"(s))) (xx)) + (cullgg(@t Db + 2 (Soo(Te. Exp, un (xx)) us
1
+ +2D||Exp - vi
k+1 Retr
ot / ++1 1lyt
<e <d (xx))) + (Scu + 22DeR)llu((an at M1? 2 bett (Sussere w/),, Exp v (xte
1
(Cou 22
p
d P(h y (x:)).
(42)
bx+1
k+1
where the second inequality follows from Assumption 3.6 and
(Retr _ Vt
Exp (z))))
(90g(re, vt), Exp ut y (x1)))
bx+1
the third inequality follows from Assumption 3.5 by employing [10 Proposition 10.22], i.e.,
[Ex
(rt))l = d(vt y (mx)) s D.
and the fourth inequality follows from Assumption 3.6
Similar to (8). we define the following thresholds for the step sizes by and c,.
Lg Lg 3o0
C max
Ce = Lag co):
1
where Ç -= (Cu. + 2Dcc defined in Lemma H.3
Proof of Proposition D.I
Proof. For AdaRHD-GD. denote
log(C?/b3))
b
log
(43)
log(1 + +,, c2)
(n/6 - CL2 /62)
Ey
and
log(C%//3
log (
Ev )
N gd
log(1 cc/C?)
where
b
max
Lb Cc) 1}. ē
max(Ly(e Cc), 1]. b
C.
24g g
27 aa
+ 2 log
Ca bo
+ 5) with Cj =
21
+ 417) is defined in + nx
45.1²
Lemma
R55 and = Ca Tog
25 + 2t
+ 2 2log
Cn
+ +1).
co
For AdaRHD-CG, denote
4L312 prec
VLg/Ut+
Neg = マ llog
flog
VLgit-1
First, we show that K, < K for all 0 ST
If hy in Proposition H.1 does not exist, we have by, S Cb. By 92 Lemma 2], it holds that
K, < log(C] /bg)
log(C] (g((C)/b)) by 119y((r, (o0(,../))1.. 11 2 Ey and by I Cb holds for all /Cg()
K, >
[og(
< Kt, we have
11ggg( ve Ke- - 1
k =b + 110yg(zz, K. )11 = 6%
1+
62
K.-1
(1 vt 113
log(C]/6/)
213 k=
II
1+
2 b3
1
Ey
> bg
(1+
1
Cg
=..
ck
c
(44)
36

---

This contradicts bk. I Cb.
log(C) (b2)
If k in Proposition H.1 exists, we have bR, I C2 and bk > Cp. We first prove (gg
log(C) similar to (44. we have
If k
lyg()+
Ag
b 2 bp
1+ cg
> >g.
0g
which contradicts the setting that bR. S Cb.
By Lemma
H.3 we have
C v (mi) s dlitt" (1 -x(()))))
((1 + (v( -1, ) )-
(Exp 1/
12/2 Exp to
12 (m1))
2
(2) S (stt 1 ( (I+)) (cu
Gug(den Uki
-2 (Exx
Retr -1 2, -
-1 vt Exp Exp (1)3)))) w.
-1
26
11
+ 2 1 (gug(or. 1/= Exp -
-1
(2x))
bk:
vi
(0)
Guglser 1)
1
S dP <s -1
"/² 1)0((²))) (st)) Ceu
+
( 1, Exp -1- (x)e))))) 1
bki
bk.
ve
+ +D Exp 1 -11 Retr ki
kt
-
11,
v:
( dd (xx)) + (Seu + 2Dex)
gog(de. o/ 1
+ + +
(ggg(se: st 1), Exp - in
124 (xi) ye1-1
bK
11 Vt
h
Edl( (xx)) +
< d vxxe)) +
12
bh
p=0
19 vt') y1) /
20 ./" (xx)) +
K= (1
(Te, y: 11 /bg
p=
5 (ukK 11- 3 (xx-1)) + 2dl (1" (xx-1) 3² (xx)) + Clo
1 (zr, v/11
+
21 1 F()
K,-1 No-1
(g) 26g 12
8 1 Hi
G6 ( Vi)1
Elog
5
12af
b
(b) 2cy
2L
Cb by
+
+ 25 log
+
(45)
n22
p²agz
where (a) follows from the second inequality of 42). (b) follows from Assumption (c) follows
3.5
from Assumption 3.6 (d) follows from the convexity of g, (e) follows from the warm start of yf (f
follows from Lemma E. (g) follows from Lemmas F2 and F4 and (h) follows from Lemma F.
and bRg < Co.
For all K > k1, by Lemma
H.3 we have
I
-(vk-', Se - (k-
dl B (z+)) S
1
[
K-1 (xx))
, (2)))
b4
b2
c c
1.
(z)
2Ey 122 +
21209
+2 log Cb
+5
(46)
p²ag
bn
37

---

where the first inequality follows from b% 2 C. 2 L5Lg
and m S eem for 0 < m < 1,
"
L
specifically, we have C. 2 2g and it holds that 0 < +
< 1, and the second inequality
bg
follows from (45
Similar to 27 we have
19ug(ar, VE K- "133x ">33
K
(1 (01,))3))) 3
by bx
S bbg +
(47)
dx bx-1
bk+1
Similar to (88). we have
2 2 "1), Exp, ft - (122))
1909(1r
"1
dly 9 (x1)) s (111"-1.y0000 +5
"1
69c
bK
<d (x+)) + 19 ve -11111x--
[15 vi= "1
2b La
bKLo
(1 - //2l.ng)
19ug(rr, ( )|12
I d2 11- ,y" (1 1-1/2TTg)
K
11 (/)))))))
Lg
bx
Lg
bx+1
where the second inequality follows from Lemma and bx 2 Cb 2 25Lg Li
By 45
we have
(1
K (pggt,,,t\il
(V (xx) - dltt" V2 (1i))) S Ligd(ut" (x:))
2 Aem R1
bk+1
26y
20203 u2
Cbb
+5) +
LL1g
2 log
112
bo
Then, by 47 and
1-p/2ba < 2, we have
2ey
2L207
Ch bo
+ +5)
bK S C₁ + 2Lg
2 log
122
:2ag
26y Denote b Cb + 2T.
22 wa
+ 25log
Ca
+ 7).
Then, under (46)
considering the
by
monotonicity th
5 w.r.t when 2 2 La
it holds that $ - (
b2
L
bx
b
L
as
b bk 2 Lg
Ly n
we have
d y 5d (z))) se (e (c-
(K- -k)
2cg 42
2 12ag
2 log
Co bo
+
( (K k1) b Co.
2Lg
(48)
CCR (b))
Since k; log( fy by the definition of K in
43 it is obvious that K 2 k1. Therefore, similar
to 30 and 31) by we have
19 ve M1 S 13 o (x,)) se (x-(#) (R-
< Ey:
2
which indicates that after at most K iterations, the condition [g vi 11 S Ey is satisfied, i.e., K, < K holds for all 2 O.
Regarding the total number of iterations N₂ required to solve the linear system, since solving it does not involve retraction mapping, the total iterations match those of Algorithm T The proof complete.
38

---

0.5. To ensure consistency, the initial step sizes in H.2 Proof of Theorem 3.2
Proof. The proof of Theorem 3.2 follows similar approach to Theorem
3.1 requiring only the
substitution of Lp with Lp and the definition of the constant Cretr as
2 aop?
(Ca
2
Cretr = Fo +
+
Fb
aop2
where Fo defined in 41 of Lemma omitted.
H.2
Due to this structural similarity, the remaining proof is
I
Experimental details
This section expands the experiments discussed in Section and presents supplemental empirical evaluations. Subsection[L] detaall the experimental configurations, while Subsection [.2] includes an additional implementation further demonstrate the robustness of our proposed algorithm through additional empirical validation.
L.1
Experimental Settings
All implementations executed using the Geoopt framework [48]. matching the reference imple- mentation [33] to guarantee equitable comparison conditions. Furthermore, all the experiments are implemented based Geoopt [48] and are implemented using Python 3.8 Linux server with 256GB RAM and 96-core AMD EPYC 7402 2.8GHz CPU.
L1.1 Simple problem
For 100, the maximum number of outer iterations in RHGD
33 is set to 200, whereas for
n 1000, this number is increased to 400. In Algorithm 3 the number of outer iterations set to
T 1000 for AdaRHD-GG and T 10000 for AdaRHD-CG. Following (33), set À 0.01 and fix the step sizes in RHGD as = ag bp Co 2.
Algorithm are
For solving the linear system, we adopt the conjugate gradient (CG) method as the default approach in RHGD. For our algorithm, the CG procedure is terminated when the residual norm falls below tolerance of 10 10-10 or the number of CG iterations reaches 50. Note that the tolerance 10-10 10 for CG procedure can be seen as O ) with > 1 is constant, this will not influence the total iterations and the complexity results since the convergence rate of the CG procedure linear. Moreover, for the GD procedure, employ the stopping criteria specified in Algorithm S or terminate when the number of iterations reaches t5 500), where |-] denotes the floor function, and represents the iteration round This caan-start-inppired strategy aims rapidly obtain reasonable solution during early iterations, and progressively increase internal iterations to satisfy the gradient
norm tolerance e, in later stages.
For solving the lower-level problem, our algorithm follows the stopping criteria outlined in Algorithm or terminates when the number of iterations reaches min 500}. For RHGD, the maximum number iterations is set to either 50 or 20.
Moreover, the number of outer iterations in our algorithm is set to T 1000 for AdaRHD and T 10000 for AdaRHD-GD. Additionally, our algorithm terminates if the approximate hy- pergradient norm falls below 10 10-4 For RHGD, the maximum number of outer iterations is set to 200.
L..2 Robustness analysis
The experimental configurations in Subsection 4.2 are maintained consistently across all comparative analyses in Subsection 4.1 except that the number outer iterations is set be T =300 for AdaRHD-CG and T' 500 for AdaRHD-GD.
39

---

1.2 Additional experiments: hyper-representation problem
I.2.1 Shallow hyper-representation for regression
incorporating a Stiefel manifold constraint 40, 34 36] to preserve positive-defing -ostive-definiteness in learned representations. The SPD representation is transformed into Euclidean space using the matrix logarithm, thereby establishing bijection between SPD and symmetric matrices, followed by vectorizing the upper-triangular entries via the vec(.) operation. We maintain the problem framework established Subsection 4.2 replacing the cross-entropy loss with the least-squares loss. The revised problem is as follows:
In this subsection, we adopt shallow regression framework from 33
min (ES((,.))
Σ
(vea(log( ".AA)A (A)-
rED
(49)
(veaflog (A A D.AA))3-p + 111313
s.t.
(*(A)=
arg min
Σ
1
(E 11/2 tEDa
where À >> is the regular parameter. Following
33 we set 50, r 10, and 0.1.
In Problem (49) the upper-level objective optimized on the validation set, whereas the lower- level problem is solved on the training set. Following [33, each element y/ is defined by yi vec(Iog(A (A 8)8 ())A)) + 6i. where A and D; are randomly generated matrices, 3 is a randomly generated vector, and E; represents a Gaussian noise term. We generate n samples of D; evenly divided between the validation and training sets. To align with the step size initialization in [3), we initialize parameters ag. by. and co in our algorithm to 20. Moreover, we configure the number of outer iterations as T = 1000 for AdaRHD-CG and T = 10000 for AdaRHD All other settings align with Section
Upper ORIEORA
7
Epoche
Timej0
Figure 4: Shallow repee--epreesentation for regression (Left two column: 200, Right two column: n 1000).
In Figure we illustrate the validation set loss (Upper Objective) versus time for n = 200 and 1000, respectively. We observe that AdaRHD-CG converges more effectively and rapidly to a smaller objective loss compared to AdaRHD-GD and RHGD. Furthermore, note that although AdaRHD-GI initially converges more slowly than RHGD (potentially due to imprecise hypergradient estimation affecting the upper-level loss reduction), Figure 4 4demonstraes that AdaRHD-GD achieves lower objective loss than RHGD at specific time intervals. These results collectively highlight the efficiency and robustness of our algorithm, demonstrated in Section 4.1
1.2.2 Deep hyper-repressentatin for classification
In this subsection, we further evaluate the efficiency and robustness of our proposed algorithm by extending the deep hyper-representation classification framework introduced in Subsection 4.2 to dataset sampling ratios of 12.5% and 25%. For each configuration, five independent trials are executed using distinct random seeds. In each trial, a randomly sampled validation set is reserved for the ueper-level problem, with an equally sized training partition allocated to the lower-level task. All remaining experimental parameters align with those defined in Subsection 4.2
Figure the validation accuracy against outer epochs (iterations) with 12.5% and 25% dataset sampling ratios (due to computational constraints, a subset of the full dataset is utilized to ensure manageable training durations). Table 3 summarizes the computational time required to achieve specified validation accuracy thresholds across algorithms. For each random seed, an independent data subset sampled. Our algorithm exhibits rapid validation accuracy improvements during initial outer iterations, followed by more gradual advancement in later stages. This behavior likely originates from the inner-loop strategy: early iterations necessitate more intensive inner-loop computations to attain high precision, whereas later stages leverage accumulated progress, thereby requiring fewer
40

---

Treining Accuracy
Training AcCursyy
Epochs
Figure 5: Deep hyper-representation for classification (Left: sampling ratio 12.5%, Right: sampling ratio 25%)
inner-loop iterations. contrast, RHGD-20 inner iterations demonstrate rapid initial accuracy gains but experience pronounced degradation subsequently, particularly at the 25% sampling ratio, where its accuracy drops below that of our method. This instability is inherent in RHGD when fewer inner iterations are employed.
Furthermore, while RHGD-20 exhibits faster time-to- tamie-tt-00--ccuraaa its elevated variance (evident in Table 3) confirms inherent instability. Notably, our method achieves target accuracy faster than RHGD despite requiring additional outer iterations. This advantage, maintained under identical initial step sizes, demonstrates both the efficacy and stability of our adaptive approach in addressing Riemannian bilevel optimization problems.
Table 3: Time required each algorithm first achieve specified validation accuracy. "Time(s) X%% defined as the time clapsed until the validation accuracy first reaches X.. Values are presented as mean + standard deviation across five independent trials using fixed random seeds for all algorithms. Statistically significant results are marked in bold. "Data ratio" refers to the proportion of the full dataset.
AdaRHD-CG
AdaRHD-GD
RHGD-50
RHGD-20
data ratio = 12.5%
Time(s) 50%
878.60+ 90.44
1258.83 138.54
1188.66 3070.22
148.46
530.03
306.29
Time(s) to 70%
1666.17 96.74
1865.13 -:: 426.80 80
169.30
2085.61
236.33
data ratio 25%
Time(s) to 50%
2511.13
233.16
3408.80 508.51
3944.26 1 589.55
2598.87 645.08
I.2.3 Robust optimization on manifolds
In this subsection, following [54 Section 7.1], we consider the robust optimization on manifolds, which have the following forms:
min PED.
1 C.
s.t.
y arg min Σ p:l(y: Ei),
(50)
gE34
where A, E R" E 1,p; > 0} and S == ly E Rdddd 0} represent the multinomial manifold (or probability simplex) and positive definite matrix space, respectively. For robust Karcher mean (KM) problem, E(y: E.) in Problem (50) represents the geodesic distance of two positive definite matrices 77:
fly: E.) log(y log(y-1/2g.) 1/ 1/
where Ei's are the symmetric positive definite data matrices. For robust maximum likelihood es- timation (MLE) problem, E(y: &r) in Problem (50) represents the log likelihood of the Gaussian distribution [75]:
+ & Ty
1 E.
Elys (s) = log det
2
where & 's are sample vectors from the Gaussian distribution.
In this experiment, we set the step sizes as 1/m f/y 1/ag 1/bo = 1/co = 0.1, with all other settings identical those Section 4.2 For the robust Karcher mean problem, we set 20 and {5, 10, 20, 50), randomly generating the symmetric positive definite data matrices & ss. For the
41

---

robust maximum likelihood estimation problem, we set d = 50 and n E {100, 300, 500, 1000), and randomly generate the sample vectors from a Gaussian distribution with mean and covariance matrix being random positive semidefinite symmetric matrix. We use five different random seeds to conduct experiments for each group. The results are shown in F where the x-axis represents the average time, and the y-axis represents the average value of the ergodic performance mon ||ğ F 2/ of )ll Note that for the MLE experiment with the results of RHGD 20 because it fails to converge this case. As shown in Figure compared to RHGDD, AdaRHD achieves superior results more efficiently and robustly, which further demonstrates the superiority and robustness of our algorithm.
100, do not report
Popnergoo www.rraddrrr... Norm
1 1 ME Nottn
140
100
1800
608 Timelst
Timelsl
(a)
(b) 12 = 10
(c) = 20
(d) 50
Hypergrathen Norm
Hypoero acteen RiGHt
Timeto)
T[me5a)
Timadal
Timals!
(c) n = 100
(f) 12 = 300
g n
500
(h) 1000
Figure 6: Robust optimization manifolds (Top row: KM model with d 20 and different n, Bottom row: MLE model with d 50 different n1).
J Broader impacts
This paper proposes an algorithm for solving Riemannian bilevel optimization problems. No negative societal impacts are anticipated from this research that warrant disclosure.
42

---

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]
Justification: For the paper's contributions and scope, please refer Sections and which match the main claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations and future directions of our work, please refer to
Section 5
Guidelines:
The answer NA means that the paper has 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiiatinn asymptotic approximations only holding locally). ). The authors should reflect on 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 low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
43

---

Answer: [Yes]
Justification: We provide the full set of assumptions and complete (and correct) proof for each lemma, proposition, theorem, and corollary. The formal statements of these results provided Section B while detailed proofs are documented in Appendices and
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 proof's 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 the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We disclose all the information needed to reproduce the main experimental results of the paper, please refer Section and Appendix [] along with the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to 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 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 to 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 NeurlPS 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 to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
44

---

5. Open access to data and code
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?
Question:
Answer: [Yes]
Justification: We provide open access to all data and code in the supplementary materials. Furthermore, we include detailed instructions to replicate the experimental results presented in Section 4 and Appendix along with the corresponding codes in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpss:/niis.cce)
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. https/scccpbll/guuuueeeee heto://///iddsssdeeeuuuiiiii (roodeSSuisssiooniii ssioiil 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, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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:
We specify all the training and test details in Section 4 and Appendix !|
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core of the paper to a 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, 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: [Yes]
Justification: The values in Table and Figure 3 of Section 4.2, as well as Figure 5 Table independent trials conducted with fixed random seeds for each algorithm.
3l and Figure of Appendix [..222 are expressed as mean standard deviation across five
Guidelines:
The answer NA means that the paper does not include experiments.
45

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are 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).
It should be clear whether the error bar is the standard deviation 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 are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide sufficient information on the computer resources for all experi- ments, please refer Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as 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 into the paper).
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics ot
Answer: [Yes]
Justification: The paper conforms, in every respect, with the NeurIPS Code of Ethics, also discuss the broader impacts and technical limitations of this paper in Section and
Appendix [
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS 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., there a special consid- eration due to laws 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: [Yes]
46

---

Justification:
We discuss the broader impacts in Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 point that 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 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 is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do not release any data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets).
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-us use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Section and Appendix ! along with the supplementary materials, the creators and original owners of assets (e.g., code, data, models) are properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
47

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssi thoode 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.
If this information is not available online, the authors 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:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
We do not introduce any human subject.
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 to the NeurIPS Code of Ethics, workers involved 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:
We do not introduce any human subject.
Guidelines:
48

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on 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 adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The LLMs are not important, original, non-standard components of the core methods in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM for what should or should not be described.
49


Reviews:
[{"review_id": "2kkmUnsi8o", "reviewer": "Reviewer_FZvm", "summary": "This paper proposes AdaRHD, an adaptive method for Riemannian bilevel optimization (RBO) that achieves comparable complexity of other RBO methods, but that does not require any knowledge of problem parameters, which can be unknown or hard to estimate in practice. To this end, they adapt the double-loop version of the tuning-free bilevel optimziation method (D-TFBO), which is suitable for general bilevel problems, to the Riemannian setting. To adaptively compute step-sizes, AdaRHD (and D-TFBO) employ the \"inverse of cumulative gradient norm\" approach introduced to establish linear convergence for AdaGrad-Norm.\nSimilarly, AdaRHD adheres to the algorithmic structure of D-TFBO, efficiently computing the hypergradient in the inner-loop by solving a quadratic problem. To validate AdaRHD, two experiments are presented, in which AdaRHD is competitive with other RBO methods and seemingly are more robust to hyperparameter initialization.", "questions": "7.1: AdaRHD is an extension of D-TFBO to the Riemannian setting. What would be the main challenges to extend the single-loop variant of D-TFBO?\n7.2: Qualitatively speaking, does the step-size adaption also works in two stages like in AdaGrad-Norm or are there any differences?\n7.3: On the paragraph following Proposition 3.2, it is mentioned that epsilon_y and epsilon_v must be sufficiently small to achieve O(1/epsilon) complexity. How can such small epsilon be determined in practice? What happens if epsilon is not small enough? Do non-adaptive methods also have such a requirement?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strenghts: The paper is clearly-written, well-organized, presents relevant references to understand it and the results seem to be correct (although I did not check them carefully.) The experimental results corroborate that AdaRHD indeed achieves comparable performance to other RBO methods while dispensing with problem parameters and being more robust to different initializations.\nWeaknesses: AdaRHD seems to be a verbatim translation of D-TFBO to the Riemannian setting. Given that I am not an expert on RBO, I cannot fairly assess the technical merits of deriving theoretical results analogue to those of D-TFBO for the Riemannian setting, which seems to be the second main contribution of this paper. To clarify the difficulty of proving the theoretical results, passages such as the paragraph after Proposition 3.2 could elaborate a bit more on such obstacles. In the same vein, there could be some intuition of why the method works. For example, does step-size adaption also works in two stages like in AdaGrad-Norm? I would be happy to raise the clarity score to maximum with the addition of the above discussion/intuition.\nFinally, in my understanding, the main contribution is to propose a method that could be used off the shelf, but there are not quite enough experiments to be sure. Perhaps this would be clearer to an RBO expert, and I understand it can be difficult to add more experiments during the rebuttal phase.", "was_revised": true, "final_justification": "The authors have provided a comprehensive and thoughtful rebuttal that adequately addresses my primary concerns from the initial review. The theory is sufficiently novel and the experiments support it. I will raise my score.", "rebuttal": "Thanks for providing these valuable suggestions, and we will make the corresponding revisions and additions to our paper.\n\n### **Weaknesses**\n\n__*For novelty*__:\n\nWe appreciate this insightful feedback. Although AdaRHD may appear as a Riemannian extension of D-TFBO due to their similar algorithmic structures, the theoretical extension is highly non-trivial and introduces several technical challenges that D-TFBO does not address. Below, we outline the key difficulties and innovations:\n\n- (**Riemannian Curvature**) Due to the geometric structures in Riemannian manifolds, determining the upper bound for the iterations $K_t$ requires incorporating the curvature constant $\\zeta$, as demonstrated in Proposition 3.2. Specifically, the coefficient $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}$ in the second term of $K_t$ exhibits a quadratic relationship on $\\bar{b}$ while being influenced by the curvature $\\zeta$. This differs from the coefficient $\\frac{\\beta_{\\max}}{\\mu}$ ($\\frac{\\bar{b}}{\\mu}$ in our notation) in the second term of $P_t$ ($K_t$ in our notation) of [81, Proposition 2], which shows only linear dependence w.r.t. $\\bar{b}$. Consequently, this discrepancy and quadratic relationship of ours necessitates a more intricate analysis for $\\bar{b}$. Specifically, we must examine the monotonicity of $\\frac{\\mu}{\\bar{b}} - \\frac{\\zeta L_g^2}{\\bar{b}^2}$ w.r.t. $\\bar{b}$ and determine an appropriate value for it. The detailed derivation of $\\bar{b}$ can be found in lines 746–754. \n\n- (**Riemannian Distance**) Additionally, when establishing the upper bound of $K_t$, we must employ the trigonometric distance bound instead of Euclidean distance (Lemma G.3, Equation (24), and line 741). This also significantly increases the substantial challenges of the convergence analysis compared to Euclidean space. For instance, unlike the threshold $C_{\\beta}$ ($C_{b}$ in our notation) established in Equation (5) of [81], we should establish a complex threshold $C_b$ for convergence analysis (cf. Equation (18)).\n\n- (**Related Method**) In comparison to existing methods for RBO [19, 29, 48], our algorithm is the first to incorporate a fully adaptive step-size strategy, which eliminates the requirement for prior knowledge of problem-dependent parameters. This practical advantage enhances our method's applicability to RBO problems. Additionally, in Algorithm 1, we employ the conjugate gradient (CG) method [7, 69] to solve the linear system, which is more efficient than the gradient descent (GD) solver in [81]. The CG method significantly reduces computational costs while offering better convergence guarantees compared to the GD solver employed in D-TFBO [81]. At the same time, we have also observed in practice that AdaRHD-CG yields better results compared to AdaRHD-GD.\n\n__*For clarity*__: \n\nWe appreciate the valuable feedback and will incorporate a more detailed discussion to clarify the challenges in proving the theoretical results of AdaRHD, as well as the intuition behind the effectiveness of the method. In the revision, we will include in the article phrases such as: \"Similar to AdaGrad-Norm [80], the step-size adaptation operates in two stages: For the lower-level problem, Stage 1 requires at most $\\frac{\\log(C_b^2/b_0^2)}{\\log(1 + \\epsilon_y/C_b^2)}$ iterations, while Stage 2 requires at most $\\frac{1}{({\\mu}/{\\bar{b}} - \\zeta {L_{g}^2}/{\\bar{b}^2})}\\log\\left(\\frac{\\tilde{b}}{\\epsilon_y}\\right)$ iterations. Furthermore, due to the geometric properties of Riemannian manifolds (e.g., trigonometric distance bound), these upper bounds cannot be directly derived from [81], and will introduce additional difficulties.\"\n\n__*For experiments*__: \n\nWe sincerely apologize for any confusion. Due to space constraints, we only present the experimental results of two problems in the main text, and have included two additional experiments in Appendix I.2. Additionally, we appreciate your constructive advice. Here, following Sections 7.1 of [48], we incorporate two additional experiments, which have the following forms:\n$$\n\\min_{p \\in \\Delta_n} \\\\|p - 1/n\\\\|^2-\\sum_{i=1}^n p_i \\ell (y;\\xi_i) ~~ \\mathrm{s.t.} ~~ y \\in \\underset{y \\in \\mathbb{S}\\_{++}^d}{\\mathrm{argmin}} \\sum_{i=1}^n p_i \\ell(y;\\xi_i),\n$$\nHere, $\\Delta_n$ and $\\mathbb{S}\\_{++}^d$ represent the multinomial manifold (or probability simplex) and positive-definite matrix manifold, respectively, $\\ell(y;\\xi_i)$ represents the geodesic distance and log likelihood for the robust Karcher mean and robust maximum likelihood estimation problems, respectively. Please refer to [48, Sections 7.1] for details.\n \nWe use the same problem scales as those in [48] and set the step-size $\\eta_x$ = $\\eta_y = 1/\\alpha_0 = 1/\\beta_0 = 1/\\gamma_0 = 0.1$, the other settings remain the same as those in Section 4.2 of our paper. On the other hand, we have also added the results of the original experiments in our response to reviewer NqyN. In the revision, we will include larger-scale experiments on this problem.\n\nFor the robust Karcher mean experiment, the relationship between the ergodic performance $\\min_t \\\\|\\mathcal{G}F (x_t)\\\\|^2$ and epoch is shown in the table below:\n\n|Epoch|1|10|50|100|\n|:-----:|:--:|:--:|:---:|:---:|\n|AdaRHD-CG|1.31e+01 (5.84e+00)|5.43e-01 (5.89e-01)|8.50e-04 (1.70e-03)|2.71e-11 (3.14e-11)|\n|AdaRHD-GD|1.31e+01 (5.84e+00)|5.41e-01 (5.82e-01)|5.63e-04 (1.12e-03)|1.22e-11 (2.19e-11)|\n|RHGD-20|1.32e+01 (5.88e+00)|1.04e+01 (5.72e+00)|8.44e+00 (4.13e+00)|8.23e+00 (4.05e+00)|\n|RHGD-50|1.32e+01 (5.88e+00)|9.72e+00 (5.40e+00)|9.72e+00 (5.40e+00)|8.20e+00 (4.55e+00)|\n\nThe relationship between time (seconds) and epoch is shown in the table below:\n\n|Epoch|1|10|50|100|\n|:-----:|:--:|:--:|:---:|:---:|\n|AdaRHD-CG|0.79 (0.46)|37.70 (6.54)|126.76 (37.43)|180.48 (56.43)|\n|AdaRHD-GD|1.44 (0.39)|18.62 (3.63)|74.70 (6.64)|139.63 (8.58)|\n|RHGD-20|6.35 (2.58)|101.42 (47.05)|567.85 (194.74)|1199.52 (422.74)|\n|RHGD-50|11.57 (0.92)|144.27 (35.10)|764.78 (160.69)|1542.63 (365.48)|\n\nFor the robust maximum likelihood estimation experiment, the relationship between the ergodic performance $\\min_t \\\\|\\mathcal{G}F (x_t)\\\\|^2$ and epoch is shown in the table below (here, we do not report the results of RHGD-20 since it fails to converge under this step-size):\n\n|Epoch|1|10|50|100|\n|:-----:|:--:|:--:|:---:|:---:|\n|AdaRHD-CG|1.27e+01 (1.54e+00)|2.38e-01 (1.25e-01)|1.55e-06 (2.79e-06)|8.76e-08 (1.34e-07)|\n|AdaRHD-GD|1.27e+01 (1.54e+00)|1.97e-03 (8.39e-04)|2.56e-05 (2.36e-05)|1.22e-06 (1.54e-06)|\n|RHGD-50|1.42e+01 (1.70e+00)|3.86e-01 (2.45e-01)|6.09e-02 (7.52e-02)|4.11e-02 (5.99e-02)|\n\nThe relationship between time (seconds) and epoch is shown in the table below:\n\n|Epoch|1|10|50|100|\n|:-----:|:--:|:--:|:---:|:---:|\n|AdaRHD-CG|0.70 (0.80)|15.26 (2.85)|29.69 (2.68)|44.69 (2.80)|\n|AdaRHD-GD|6.05 (2.06)|17.87 (1.89)|29.76 (1.95)|44.80 (1.99)|\n|RHGD-50|2.62 (0.13)|26.66 (0.60)|129.08 (4.07)|257.49 (7.55)|\n\nAs shown in the tables above, AdaRHD can achieve superior results more efficiently and robustly compared to RHGD. Additionally, we emphasize that even when the initial step-size is set larger, such as 0.5, AdaRHD still converges, whereas RHGD-50 and RHGD-20 do not (due to character and time constraints, we do not present the corresponding results here), which further demonstrates the robustness of our algorithm.\n\n### **Questions**\n\n__*For Question 1*__: \n\nWe appreciate this insightful question. While maintaining a structure similar to S-TFBO [81], this single-loop extension requires replacing Euclidean (hyper)gradients with their Riemannian counterparts. However, this extension presents some primary challenges:\n\nFirst, the same as AdaRHD, in Riemannian space, we should use trigonometric distance bounds instead of Euclidean bounds. This fundamentally alters the convergence analysis for two stage step-size adaptation compared to S-TFBO [81]. For instance, in S-TFBO [81], the step-sizes for $v_{t+1}$ and $x_{t+1}$ are chosen as $\\frac{1}{\\varphi_{t+1}}$ and $\\frac{1}{\\alpha_{t+1}\\varphi_{t+1}}$ respectively, these step-sizes are not straightforward and require careful design. In the Riemannian setting, this step-size strategy may be ineffective, further complicating the convergence analysis due to both the trigonometric distance bounds and the absence of key inequalities that are valid only in Euclidean space.\n\nSecond, many technical results essential for proving AdaRHD’s convergence (e.g., Equations (24), (25), and (28)) rely on approximate solutions to the lower-level problem and linear system. However, it remains unclear whether these results naturally extend to the single-loop variant, as the latter does not solve subproblems with sufficient accuracy. In addition, although we have conducted preliminary experiments to extend S-TFBO [81] to the Riemannian setting without convergence analysis, the experimental results were unsatisfactory. This could be due to limitations in our implementation, and may also require better adaptation strategy. Consequently, this paper focuses solely on the double-loop structured algorithm. Nevertheless, we agree that extending the single-loop variant constitutes a promising research direction.\n\n__*For Question 2*__:  \n\nYes, you are correct that, similar to AdaGrad-Norm, AdaRHD's step-size adaptation also operates in two stages. For details, please refer to Proposition G.1 and our response to \"For clarity\" in Weaknesses.\n\n__*For Question 3*__:  \n\nWe sincerely apologize for this confusion. The condition that \"$\\epsilon_y$ and $\\epsilon_v$ are sufficiently small\" is introduced primarily to demonstrate that $\\frac{1}{\\log(1+\\epsilon_y)}$ has the same order as $\\frac{1}{\\epsilon_y}$, i.e., $\\frac{1}{\\log(1+\\epsilon_y)} = \\mathcal{O}(1/\\epsilon_y)$. In practice, this condition is unnecessary, and setting $\\epsilon_y = \\epsilon_v = 1/T$ (cf. line 1 of Algorithm 1) suffices.\n\n\n### **References**\nAll the referenced citations mentioned above have the same numbering as in the article."}, {"review_id": "XpIEfgGcGM", "reviewer": "Reviewer_NqyN", "summary": "This article studies deterministic adaptive optimization algorithm complexity for Riemannian bilevel optimization problems. Adaptive Riemannian hypergradient descent algorithm is proposed and analyzed to achieve a fast convergence compared to non-adaptive methods. This algorithm is further extended to allow for the use of retraction mappings to main a same complexity bound. Numerical experiments show comparable and more robust performance of the proposed method compared to non-adaptive approaches.", "questions": "-\tRegarding algorithm 1 (AdaRHD), should you add a stopping criterion to return an eps-stationary point? What would be the extra cost of this stopping criteria in terms of the computational complexity? \n-\tClarify the U_x and U_y in assumption 3.2.\n-\tShould you use f instead of F in assumption 3.4, or over M_x instead?\n-\tClarify the CG step in Proposition 3.2. What does it mean N_t in AdaRHD-CG, in terms of number of CG steps (could be more precise)?\n-\tAssumption 3.5 does the tilde D constant depend on t? If not, should you write i.e. there exists tilde D such that for all t>=0, ….\n-\tFig 3 of numerical results, is this about the best iteration performance, last iteration performance? The main theory is about ergodic performance, which is related to the best iteration min_t || GF (x_t ||^2. This is not so clear by reading Section 4. If Fig 3 is about last iteration, i.e. performance of x_t, then I think that a discussion about the best iteration performance should also be included. \n-\tThe epochs in Fig 3(a) and (b) should be made longer to see if the robustness of the proposed algorithm can be achieved, then t is large. Currently, it is too short to see that the algorithm converges to a similar performance level (y axis label is too small to read).", "limitations": "There is a lack of discussion how to address stochastic gradients which are of interest in machine learning. It seems that this problem is quite challenging. A discussion or citation could be included in the article.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength: The article is well written and easy to follow. Motivated by a recent article [81], the main idea is to extend recent adaptive methods from Euclidean spaces to Riemmanian manifolds. The proposed algorithm is based on an adaGrad-type gradient norm strategy (algo 1). A main challenge is to analyze the convergence rate of the proposed method. This is presented in Theorem 3.1 and 3.2 (whose proofs are not checked).\n\nWeakness: The extension of the algorithm 1 from [81] seems quite straightforward, therefore the originality of the algorithm is not strong. The main issue seems to be a lack of connection between convergence in theory and the numerical results. There is also a lack of discussion how to address stochastic gradients, which are of interest in machine learning. \n\nSome of the results and assumptions should be further clarified (including some typos).", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your recognition and your valuable constructive feedback. Your expert insights are essential to advancing our research.\n\n### **Weaknesses**\n__*For originality*__:\n\nWe appreciate your insightful comments. Intuitively, AdaRHD can be regarded as an extension of D-TFBO [81] to Riemannian manifolds, given their analogous algorithmic structures. However, the theoretical generalization is highly non-trivial and introduces several technical challenges. Below, we outline some key difficulties and innovations of our work:\n\n- (**Riemannian Curvature**) Owing to the geometric structures of Riemannian manifolds, deriving $K_t$ (the iterations of the lower-level problem) in Proposition 3.2 requires incorporating the curvature $\\zeta$. Specifically, the coefficient $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}$ in the second term of $K_t$ exhibits quadratic dependence on $\\bar{b}$ and depends on $\\zeta$. This contrasts with the coefficient $\\frac{\\beta_{\\max}}{\\mu}$ ($\\frac{\\bar{b}}{\\mu}$ in our notation) in the second term of $P_t$ ($K_t$ in our notation) in [81, Proposition 2], which only depends linearly on $\\bar{b}$. Consequently, this discrepancy and the quadratic dependence necessitate a more intricate analysis: we must examine the monotonicity of $\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2$ w.r.t. $\\bar{b}$. The detailed analysis is provided in lines 746–754.\n- (**Riemannian Distance**) When analyzing Proposition 3.2 and Theorem 1, we must employ the trigonometric distance (Lemma B.1) instead of Euclidean counterpart. This issue substantially increases the difficulty of the analysis compared to [81]. For instance, unlike the threshold $C_{\\beta}$ ($C_{b}$ in our paper) in [81, Equation (5)], our analysis necessitates a more sophisticated threshold $C_b$ (Equation (18)) to account for the manifold structure.\n- (**Related Method**) Compared to existing methods for RBO [19, 29, 48], our algorithm is the first to incorporate a fully adaptive step-size strategy. This eliminates the need for prior knowledge of computationally expensive parameters (e.g., curvature). Such adaptability significantly broadens the applicability of our method to RBO. Furthermore, we utilize a CG method [7, 69] to solve linear system in Algorithm 1. This technique significantly reduces computational costs (particularly Hessian-vector product,) and achieves better convergence guarantees compared to the gradient descent in [81]. \n\n__*For experiments*__:\n\nWe appreciate this observation and will incorporate related discussion in our revision. Please refer to our response to Questions 6 and 7.\n\n__*For stochastic setting*__:\n\nWe regret any confusion. Developing an adaptive stochastic method for RBO represents a promising direction, and we also briefly discuss potential extensions to it and cite relevant works in Appendix J. We will incorporate this discussion into the main text and further elaborate on its significance for machine learning.\n\nAlthough there exist adaptive stochastic methods for solving single-level problems over Riemannian manifolds (RSGD [B13], RSVRG [Z16], RSRG [K18], R-SPIDER [Z18; Z19], RASA [K19], RAMSGrad [B19], Riemannian SAM [Y24], RNGD [H24], and Riemannian adaptive framework [S25]), designing an adaptive stochastic method for RBO poses substantial challenges and may lie beyond this paper’s scope. Moreover, existing stochastic methods for RBO, RF2SA [19], RSHGD-HINV [29], and RieSBO [48], rely on well-tuned step-sizes. The inherent randomness in (hyper)gradient estimates, combined with Riemannian geometry, complicates the design of such an extension:\n- (**Stochastic Riemannian hypergradient**) Similar to the approximate Riemannian hypergradient in Equation (5), the stochastic variant needs to consider three distinct sources of randomness: stochastic Riemannian gradient, Hessian, and partial derivative. The simultaneous presence of these randomnesses significantly complicates the convergence analysis of adaptive stochastic RBO algorithms, making it more challenging than methods for single-level problems.\n- (**Maximum iterations for two stages of step-sizes**): In our paper, the two stages of step-sizes (Proposition G.1) necessitate a comprehensive analysis of all sequences $x_t$, $y_t^k$, and $v_t^n$; we further need to incorporate stochastic errors if in the stochastic setting. The challenge is particularly pronounced for $x_t$, which is updated by a stochastic approximate Riemannian hypergradient, affected by three distinct randomnesses (cf. the above analysis). These challenges highlight the difficulty of extending AdaRHG to the stochastic setting compared to [19, 29, 48].\n\nOn the other hand, we previously conducted some experiments in stochastic setting, but did not obtain impressive results, potentially due to our implementation limitations. Nevertheless, we believe this extension is a promising direction, though it may require better techniques to ensure both theoretical convergence and practical applicability.\n\n__*For clarity*__: We appreciate your insightful observations on the clarity of our paper. We will address these issues in our revision.\n\n[B13] Bonnabel. Stochastic gradient descent on Riemannian manifolds\n\n[Z16] Zhang et al. Riemannian SVRG: Fast stochastic optimization on Riemannian manifolds\n\n[K18] Kasai et al. Riemannian stochastic recursive gradient algorithm\n\n[Z18] Zhang et al. R-SPIDER: A fast Riemannian stochastic optimization algorithm with curvature independent rate\n\n[Z19] Zhou et al. Faster first-order methods for stochastic non-convex optimization on Riemannian manifolds\n\n[K19] Kasai et al. Riemannian adaptive stochastic gradient algorithms on matrix manifolds\n\n[B19] Bécigneul and Ganea. Riemannian adaptive optimization methods\n\n[Y24] Yun and Yang. Riemannian SAM: Sharpness-aware minimization on Riemannian manifolds\n\n[H24] Hu et al. Riemannian natural gradient methods\n\n[S25] Sakai and Iiduka. A general framework of Riemannian adaptive optimization methods with a convergence analysis\n\n\n### **Questions**\n__*For Question 1*__:\n\nWe appreciate your insightful question. Indeed, we can incorporate a stopping criterion, $\\\\|\\hat{G}F(x_t,y_t^{K_t},v_t^{N_t})\\\\|^2 \\le 1/T$, into the \"for loop\" of Algorithm 1 to terminate early, where $\\hat{G}F(x_t,y_t^{K_t},v_t^{N_t})$ denotes the approximate Riemannian hypergradient in Equation (5). By Lemma 3.1, $\\\\|\\hat{G}F(x_t,y_t^{K_t},v_t^{N_t})\\\\|^2 \\le 1/T$ also ensures $\\\\|GF(x_t)\\\\|^2 \\le O(1/T)$, implying that $x_t$ is an $O(1/T)$-stationary point. Furthermore, this modification does not increase the overall computational complexity, as we only need to perform an additional norm of hypergradient at each step.\n\n__*For Question 2*__:\n\nWe apologize for any confusion. The notations $\\mathcal{U}_x$ and $\\mathcal{U}_y$ denote the components of $\\mathcal{U}$, such that $\\mathcal{U} = \\mathcal{U}_x \\times \\mathcal{U}_y$, where $\\mathcal{U} \\subset \\mathcal{M}_x \\times \\mathcal{M}_y$.\n\n__*For Question 3*__:\n\nWe appreciate your careful reading. It should be \"The minimum of $F$ over $\\mathcal{M}_x$, denoted as $F^*$, is lower-bounded.\" As referenced in line 701, we only utilize the minimum of $F$ over $\\mathcal{M}_x$.\n\n__*For Question 4*__:\n\nWe apologize for any confusion. In both AdaRHD-GD and AdaRHD-CG, $N_t$ is reused to denote the total iterations required to solve the linear system, i.e., in AdaRHD-CG, $N_t$ represents the total iterations needed by Algorithm 2 to solve linear system at $t$-th iteration.\n\n__*For Question 5*__:\n\nWe apologize for any confusion. You are correct that $\\tilde{D}$ is independent of the iteration $t$, and we will address it in our revision.\n\n__*For Questions 6 and 7*__:\n\nWe apologize for not clearly explaining the numerical results and for omitting the key metrics, e.g., ergodic performance $\\min_t \\\\|GF (x_t)\\\\|^2$. It is true that Figure 3 only displays the performance of last iteration. Since we cannot include figures, we instead provide comparative tables summarizing the ergodic performance $\\min_t \\\\|GF (x_t)\\\\|^2$ for two step-sizes (0.1 and 5) with 5 seeds (owing to space constraints, we only present two step-sizes). Moreover, due to a previous storage mistake, $\\\\|GF (x_t)\\\\|^2$ was not recorded, so we reran the experiments in this period. Due to time constraints, we limited the epochs to 300, but it was enough to observe the efficiency and robustness of our algorithm.\n\nStep-size 0.1:\n\n|Epoch|1|50|100|200|300|\n|:-----:|:--:|:--:|:---:|:---:|:---:|\n|AdaRHD-CG|5.3e-01 (6.3e-02)|5.2e-02 (4.0e-03)|1.5e-02 (1.5e-03)|3.4e-03 (5.9e-04)|1.5e-03 (4.4e-04)|\n|AdaRHD-GD|2.1e-01 (4.9e-02)|4.3e-03 (3.4e-03)|2.4e-03 (4.4e-03)|4.7e-04 (9.2e-04)|1.8e-04 (3.7e-04)|\n|RHGD-20|1.3e+01 (1.8e+00)|4.9e-02 (3.2e-03)|1.7e-02 (7.2e-03)|8.5e-03 (1.1e-02)|7.3e-03 (1.2e-02)|\n|RHGD-50|6.6e+00 (1.2e+00)|5.0e-02 (4.8e-03)|1.3e-02 (4.3e-04)|3.1e-03 (6.2e-04)|1.8e-03 (1.1e-03)|\n\nStep-size 5:\n\n|Epoch|1|50|100|200|300|\n|:-----:|:--:|:--:|:---:|:---:|:---:|\n|AdaRHD-CG|1.1e+02 (1.0e+02)|2.7e-01 (1.1e-01)|1.6e-01 (1.1e-01)|4.4e-02 (4.2e-02)|2.6e-02 (2.2e-02)|\n|AdaRHD-GD|2.4e+04 (2.9e+04)|4.0e-02 (5.0e-02)|1.5e-03 (1.1e-03)|1.8e-04 (1.2e-04)|4.8e-05 (2.1e-05)|\n|RHGD-20|2.0e+04 (2.0e+04)|6.3e+02 (4.1e+02)|4.5e+02 (1.4e+02)|4.1e+02 (1.2e+02)|4.1e+02 (1.2e+02)|\n|RHGD-50|1.1e+04 (8.0e+03)|5.1e+02 (2.3e+02)|5.0e+02 (2.3e+02)|4.6e+02 (2.5e+02)|4.1e+02 (1.9e+02)|\n\nThese results show that our algorithm achieves superior performance while exhibiting greater robustness than RHGD, further validating the efficiency and reliability of our method. We will incorporate the figures of ergodic performance in our revision. Additionally, we appreciate the feedback regarding the y-axis label and will address this by increasing its font size in the revision.\n\n### **Limitation**\nThanks again for pointing this out. Please refer to our response to \"For stochastic setting\" in Weaknesses.\n\n### **References**\nThe reference numbers above correspond to those cited in the original paper."}, {"review_id": "WegHxIklRx", "reviewer": "Reviewer_TNoH", "summary": "This paper introduces the first fully adaptive method for Riemannian bilevel optimization, called the Adaptive Riemannian Hypergradient Descent (AdaRHD) algorithm.\nThe method is adaptive in the sense that it does not require prior knowledge of first- and second-order information or curvature parameters of the manifold (such as strong convexity, Lipschitz continuity, or curvature constants) to determine step sizes.\nThe algorithm is based on the approximate Riemannian hypergradient and furthermore employs an \"inverse of cumulative gradient norm\" strategy to design adaptive step sizes, inspired by [81].\nThis paper proves that their method achieves the same convergence complexity as existing non-adaptive methods.\nLastly, they also provide a variant achieving the same complexity bound and demonstrate the effectiveness of their method through experiments.", "questions": "- **Q1.** In the context of algorithm design, are there any novel and significant ideas the authors would like to highlight that did not appear in the Euclidean counterpart but are crucial for the proposed algorithm?\n\n- **Q2.** In the context of techniques in Riemannian optimization, are there any new techniques the authors would like to highlight that were required to be developed while establishing the analysis of AdaRHD or AdaRHD-R?", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**\n\n- This paper overcome technical challenges and also provide promised results that can be expected from the title. Indeed, bilevel optimization is challenging compared to single-level problem, and achieving the same complexity with non-adaptive algorithm for an adaptive algorithm. And the most of the among keywords, Riemannian optimization is challenging compared to Euclidean optimization, since calculation of parameters and even simple calculation laws like cosine law due to the distortion.\n\n- This paper introduces the algorithm which is the first of its kind, which achieves the all keywords appear in the title.\n\n- The paper is well organized and the authors did a good job on the presentation. \n\n**Weakness**\n\n- **W1.** To the best of this reviewer's understanding, this paper provides an extension of the algorithm introduced in [81] to Riemannian optimization. This reviewer believes that such work is not trivial and requires overcoming various technical difficulties. \nHowever, in the context of algorithm design, this reviewer is curious whether most of the key ideas for handling adaptiveness and the bilevel structure were perhaps already developed in the Euclidean case. \nThis point is closer to a question than a weakness; please see the related question.", "was_revised": true, "final_justification": "The authors have kindly addressed my questions, and I will maintain my original score.", "rebuttal": "We sincerely appreciate your recognition of our work, as well as your valuable insights and thoughtful feedback on this paper.\nAt the same time, we will make the corresponding additions to our revision.\n\n### **Weaknesses**\n__*For Weakness 1*__:\n\nWe appreciate the opportunity to clarify this point. You are correct that some key ideas for addressing adaptiveness and the bilevel structure are initially developed in the Euclidean setting [81]. In particular, the adaptive step-size design in our algorithm, AdaRHD, resembles that of D-TFBO [81], with the key distinction being the replacement of Euclidean gradients (hypergradients) with their Riemannian counterparts. Furthermore, certain aspects of the convergence proof are inspired by prior work in both the Euclidean [10, 75, 76, 81] and Riemannian [7, 9, 29] settings. Examples include the two stage adaptive step-size mechanism (see Proposition G.1) and specific properties of Riemannian (hyper)gradients (detailed in Appendix F).\n\nHowever, we point out that due to the geometric structures inherent in Riemannian manifolds, although certain aspects of Euclidean analysis extend naturally to Riemannian settings, there exist many theoretical challenges in the proof of the convergence analysis. More specifically, we will explain from the following points that the theoretical extension is not so intuitive and will encounter many technical difficulties:\n\n- Firstly, influenced by the curvature of the Riemannian manifolds, establishing the upper bound for the iterations $K_t$ (i.e., the total iterations for solving the lower-level problem at the $t$-th iteration) needs to consider the curvature constant $\\zeta$, as shown in Proposition 3.2. \n- Secondly, different from the distance defined in Euclidean space, the trigonometric distance bound (cf. Lemma B.1 in our paper) also raises a difficulty in the theoretical analysis. Moreover, establishing the convergence of AdaRHD requires a thorough analysis of all sequences, $x_t$, $y_t^k$, and $v_t^n$, whose convergence properties also fundamentally depend on the trigonometric distance bound. This dependency highlights the inherent theoretical challenges in analyzing AdaRHD.\n- Thirdly, in contrast to existing methods for Riemannian bilevel optimization (RBO) [19, 29, 48], our proposed algorithm is the first to incorporate a fully adaptive step-size strategy. This eliminates the requirement for prior knowledge of problem-dependent parameters (e.g., strong convexity, Lipschitz smoothness, or curvature bounds), which may be particularly challenging to estimate in Riemannian settings. This advantage makes our algorithm more practical in the applications of RBO.\n\n### **Questions**\n\n__*For Question 1*__: \n\nThanks for your insightful question. We will state some novel and significant ideas of algorithm design in the following points:\n\n- (**Compare to the Euclidean counterpart**) Compared to the Euclidean adaptive algorithm D-TFBO [81], we introduce a tangent space conjugate gradient method (Algorithm 2) for solving the linear system. Our AdaRHD-CG algorithm demonstrates superior computational efficiency, with D-TFBO's Hessian-vector product complexity being $O(1/\\epsilon^2)$, which is worse than ours $\\tilde{O}(1/\\epsilon)$, as evidenced by Table 1 (cf. first and last rows). In addition to the theoretical reduction in complexity, we have also observed in practice that AdaRHD-CG yields better results compared to AdaRHD-GD and RHGD (e.g., as demonstrated in the second subfigures of Figures 1 and 2, AdaRHD-CG achieves lower hypergradient errors compared to AdaRHD-GD and RHGD). This is likely since, in the current iteration, CG can achieve a better solution with less computational cost. We believe that applying it to the Euclidean counterpart should also yield good results.\n\n- (**Compare to related Riemannian method**) In Section 3.4, we extend our algorithm to employ retraction mappings for variable updates (AdaRHD-R), a computationally efficient alternative to exponential mappings preferred in practice. Among existing RBO methods, only RHGD [29] implements a similar extension. However, RHGD's performance critically depends on carefully tuned step-sizes requiring problem-specific parameters that are often impractical to obtain (especially the curvature $\\zeta$). Our algorithm maintains RHGD's convergence rate while eliminating this parameter dependence, demonstrating greater robustness in practical applications.\n\n__*For Question 2*__: \n\nWe appreciate this insightful question and would like to highlight the novel aspects of our theoretical techniques:\n\n\n- (**Riemannian Challenges**) Unlike Euclidean optimization, Riemannian optimization must account for the curvature $\\zeta$, rendering some standard results established in [81] (Euclidean space) inapplicable. Specifically, the coefficient $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}$ of the second term $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}\\log(\\frac{\\tilde{b}}{\\epsilon_y})$ includes $\\zeta$ and is a quadratic term w.r.t. the step-size $\\bar{b}$, which is different from $\\frac{\\beta_{\\max}}{\\mu}$ (equivalent to $\\frac{\\bar{b}}{\\mu}$ in our notations) in $P_t$ (equivalent to $K_t$ in our notation) of [81], as it demonstrates only linear dependence w.r.t. $\\bar{b}$. This raises a critical problem that we should consider a much complex analysis of the step-size $\\bar{b}$ (e.g., the monotonicity of $\\frac{\\mu}{\\bar{b}} - \\frac{\\zeta L_g^2}{\\bar{b}^2}$ w.r.t. $\\bar{b}$), please refer to lines 719-723 for the value of $\\bar{b}$. Furthermore, we need to use the trigonometric distance bound (Lemma B.1) instead of the classical Euclidean distance triangle inequality, which introduces theoretical challenges. For example, in the convergence analysis of the lower-level problem (i.e., establish the upper bound of $K_t$), it is different from the threshold $C_{\\beta}$ (equivalent to $C_{b}$ in our notation) established in Equation (5) of [81], we should establish a complex threshold $C_b$ for convergence analysis (cf. Equation (18)).\n\n\n- (**Retraction Challenges**) In order to be more practical, we extend our algorithm to update variables via retraction mappings. Since retraction mappings serve as first-order approximations of exponential mappings [29], the error between exponential and retraction mappings must be accounted for when updating variables $x_t$ and $y_t$ at each iteration, which introduces additional challenges in the theoretical analysis. Although [29] explores this extension and presents theoretical results, such as the convergence of the lower-level problem and technical findings under retraction mappings (see Appendix E in [29]), the convergence analysis of our AdaRHD-R algorithm differs significantly and presents unique challenges. Specifically, AdaRHD-R employs a two stage step-size adaptation mechanism (see the proof of Proposition D.1, lines 860–897), whose theoretical challenge surpasses that of the algorithm in [29], which relies on well-tuned step-sizes and extensive prior knowledge of RBO-specific parameters. Moreover, deriving the upper bounds for the total iterations of the two stage step-size is more intricate in comparison to AdaRHD. For example, Lemmas G.1 and H.1, as well as Lemmas G.3 and H.3, demonstrate that the definitions of several constants (e.g., $\\bar{L}_F$ in line 834, $\\bar{\\zeta}$ in line 852, and $C_b$ in line 857) in AdaRHD-R are more complex than those in AdaRHD, owing to the discrepancies between exponential and retraction mappings.\n\n### **References**\nAll the referenced citations mentioned above have the same numbering as in the article."}, {"review_id": "SQLlGxdAg0", "reviewer": "Reviewer_6VLZ", "summary": "The paper studies bilevel optimization on Riemannian manifolds. The paper proposes an adaptive hypergradient method for solving the bilevel problem on manifold. The idea is to normalize the hypergradient with a moving-average of gradient norm, following the existing works in the Euclidean space. The paper derives convergence results on manifolds and show a matching gradient/Hessian complexities as non-adaptive method. The paper shows some promising experiment results compared to non-adaptive method.", "questions": "I have the following comments and questions:\n\n1. The paper is largely based on prior works [1,2] for developing the adaptive algorithm for Riemannian bilevel optimization. The convergence analysis follows similarly from the existing works as well. Thus the contributions of the paper seem limited. The authors are expected to include more discussions on the significance of the results as well as whether there exists other technical contributions.\n\n2. In Proposition 3.2, the upper bound on K_t includes the curvature constant \\zeta. However for highly curved manifolds, the curvature constant is significantly large, which would renders the second term negative. I wonder what it means to have a negative term in this case?\n\n3. What is the role of curvature in the derived convergence and complexities? This is very important and should be extensively compared with the work in the Euclidean space where curvature is zero.\n\n4. The gradient and Hessian complexity of the lower-level problem is O(1/\\epsilon) worse compared to the non-adaptive methods, which could be the main bottleneck of the method. \n\n\n[1] Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis\n\n[2] A Framework for Bilevel Optimization on Riemannian Manifolds", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper presents a complete theoretical analysis and provides the first non-asymptotic convergence analysis for adaptive methods on manifolds. Experiment results demonstrate great promise.", "was_revised": true, "final_justification": "My concerns regarding the role of curvature has been well addressed.", "rebuttal": "We sincerely appreciate your valuable feedback and insightful comments on our work. Your constructive suggestions will enable us to further elaborate on the significance of our technical contributions in our revision.\n\n### **Questions**\n\n__*For Question 1*__: \n\nWe appreciate this insightful comment. Intuitively, AdaRHD can be regarded as an extension of D-TFBO [1] to Riemannian manifolds, given their analogous algorithmic structures. However, the theoretical generalization is highly non-trivial and introduces several technical challenges beyond D-TFBO. Below, we outline some key difficulties and innovations of this paper:\n\n- (**Curvature Constant**) Given the geometric structure of Riemannian manifolds, determining the upper bound for the iterations $K_t$ (i.e., the total iterations for solving the lower-level problem at $t$-th iteration) requires incorporating the curvature $\\zeta$, as established in Proposition 3.2. Specifically, the coefficient $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}$ in the second term $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}\\log(\\frac{\\tilde{b}}{\\epsilon_y})$ of $K_t$, demonstrates a quadratic dependency on $\\bar{b}$ while being influenced by the curvature $\\zeta$. This stands in contrast to the coefficient $\\frac{\\beta_{\\max}}{\\mu}$ ($\\frac{\\bar{b}}{\\mu}$ in our notation) in the second term of $P_t$ ($K_t$ in our notation) of [1, Proposition 2], where the dependence on $\\bar{b}$ is purely linear. Consequently, this discrepancy and the quadratic dependence necessitate a more intricate analysis: we must examine the monotonicity of $\\frac{\\mu}{\\bar{b}} - \\frac{\\zeta L_g^2}{\\bar{b}^2}$ w.r.t. $\\bar{b}$ and determine an appropriate value. The detailed derivation of $\\bar{b}$ is provided in lines 746–754 of this paper.\n- (**Inner Iteration**) Additionally, when deriving the upper bound for $K_t$, we must employ trigonometric distance bounds instead of Euclidean measures (Lemma G.3, Equation (24), line 741). This requirement substantially increases the difficulty of our convergence analysis relative to the Euclidean framework presented in [1]. Specifically, unlike the threshold $C_{\\beta}$ ($C_{b}$ in our notation) defined in Equation (5) of [1], our analysis necessitates a more sophisticated threshold $C_b$ (cf. Equation (18)) to account for the Riemannian manifold geometry. Furthermore, in Algorithm 1, we utilize a conjugate gradient method (Algorithm 2) to solve the linear system, which is more efficient than the gradient descent solver in [1]. This technique reduces computational costs (particularly Hessian-vector products) while offering better convergence guarantees, compared to [1]. We have also observed in practice that AdaRHD-CG outperforms AdaRHD-GD. This is likely because, in the current iteration, CG can obtain a better solution with lower computational cost.\n- (**Related Method**) Compared to existing methods for RBO, e.g., [2], our algorithm is the first to incorporate a fully adaptive step-size strategy. This eliminates the need for prior knowledge of problem-dependent parameters, which are computationally expensive to estimate on Riemannian manifolds (particularly the curvature $\\zeta$). Such adaptability significantly broadens the applicability of our method to RBO problems.\n\nFurthermore, building upon your insightful feedback, we will incorporate a more rigorous analysis in the revision to elucidate both the theoretical challenges and the intuitions underlying the method's effectiveness.\n\n__*For Question 2*__: \n\nWe apologize for the confusion. The second term, $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)} \\log\\frac{\\tilde{b}}{\\epsilon_y}$, is indeed non-negative, which is an oversight in our writing. We will explicitly clarify this in the revision of Proposition 3.2. Specifically, we have established the non-negativity of $\\frac{1}{(\\mu/\\bar{b} - \\zeta L_g^2/\\bar{b}^2)}$ in lines 746-748 of our paper: Considering the monotonicity of $\\frac{\\mu}{b} - \\frac{\\zeta L_g^2}{b^2}$ w.r.t. $b$ when $b \\ge 2\\zeta L_g\\frac{L_g}{\\mu}$, it follows that $0 < \\frac{\\mu}{\\bar{b}} - \\frac{\\zeta L_g^2}{\\bar{b}^2}$ as $\\bar{b} \\ge 2\\zeta L_g\\frac{L_g}{\\mu}$ (the definition of $\\bar{b}$ is given in line 746). Additionally, the element $\\log\\frac{\\tilde{b}}{\\epsilon_y}$ is also non-negative by the definition of $\\tilde{b}$ in line 721 of our paper. Therefore, even if the curvature constant is significantly large, the second term in $K_t$ is still non-negative.\n\n__*For Question 3*__: \n\nWe acknowledge the omission of a detailed discussion on curvature's role and will address this in our revision. You are correct that the curvature is zero in Euclidean space, and the farther the Riemannian manifold is from Euclidean space, the larger the curvature becomes. As shown in Lemma B.1, unlike the Euclidean distance bound $a^2 \\le b^2 + c^2 + 2 bc$, we use a trigonometric distance bound dependent on the curvature $\\zeta$. This bound is critical for convergence analysis (cf. Proposition 3.2, Lemmas G.3, H.3, and related results). Thus, curvature fundamentally influences convergence and complexity. Specifically, compared to D-TFBO [1]: Firstly, though our step-size adaptation also operates in two stages (cf. Propositions 3.2 and D.1), the maximum iterations per stage depend on $\\zeta$. For the lower-level problem (Proposition 3.2), Stage 1 requires at most $\\frac{\\log(C_b^2/ b_0^2)}{\\log(1+\\epsilon_y/C_b^2)}$ iterations, and Stage 2 at most $\\frac{1}{({\\mu}/{\\bar{b}} - \\zeta {L_{g}^2}/{ \\bar{b}^2})}\\log\\left(\\frac{\\tilde{b}}{\\epsilon_y}\\right)$ iterations. Here, $C_b, \\bar{b}, \\tilde{b}$ are all related to curvature $\\zeta$, and they increase as the curvature $\\zeta$ increases; Secondly, Lemma G.3 yields a technical result for the convergence of the lower-level problem:\n$$\nd^2(y_t^{k+1}, y^{\\*}(x_t)) \\le (1 + \\zeta L_{g}^2/b_{k+1}^2  - \\mu/b_{k+1}) d^2(y_t^{k}, y^{\\*}(x_t)),\n$$\nwhich is different from the Euclidean setting (cf. Inequality (b) of Equation (18) in [1]): \n$$\n\\\\|y_t^{k+1} - y^{\\*}(x_t)\\\\|^2 \\le (1-\\mu/b_{k+1})\\\\|y_t^k - y^{\\*}(x_t)\\\\|^2.\n$$\nWhen $\\zeta = 0$, this inequality in the Riemannian setting degenerates to the Euclidean setting. Therefore, the curvature $\\zeta$ plays an important role in areas such as the number of **inner iterations estimation** and **the distance inequalities** involved in the convergence analysis, which brings challenges to the analysis of our algorithm.\n\nIn the revision, we will include a detailed discussion on the role of curvature in our analysis, along with a comparative examination of its implications in Riemannian versus Euclidean settings.\n\n__*For Question 4*__: \n\nThanks for pointing this out. It is correct that the gradient and Hessian complexity of the lower-level problem is $O(1/\\epsilon)$ worse compared to the non-adaptive methods. We point out that the $O(1/\\epsilon)$ gap stems from two key factors: (1) the additional iterations required to ensure convergence for solving the lower-level problems and linear systems, due to the absence of parameter-specific prior knowledge in RBO; and (2) the adaptive step-size strategy employed, which utilizes the inverse of cumulative gradient norms [3]. However, we point out that the gradient and Hessian complexities for the lower-level problem are the same as the standard AdaGrad-Norm algorithm [3], as well as D-TFBO [1].\n\nFurthermore, we have discussed this gap and aim to address the $O(1/\\epsilon)$ gap by exploring alternative adaptive step-size strategies in future work (cf. Appendix I, lines 996–998). We will incorporate this discussion into the main text and provide a more detailed analysis in the revision. We believe that designing such an algorithm is an interesting direction, and the gap may be resolved by employing some other adaptive strategies from Riemannian and Euclidean settings: For Riemannian optimization, possible approaches include Riemannian SAM [4], RNGD [5], and the framework for Riemannian adaptive optimization [6]. In Euclidean optimization, alternatives such as adaptive accelerated gradient descent [7], AdaPGM [8], AdaBB [9], and AdaNAG [10] may be viable, rather than the inverse of cumulative gradient norms [3] of this paper. More specifically, with carefully designed adaptive step sizes, the method proposed in [7] (Euclidean space) achieves an improved convergence rate of $O(\\log(1/\\epsilon))$ compared to the $O(1/\\epsilon)$ rate of [3]. However, directly applying similar adaptation strategies from [7] to Riemannian manifolds introduces significant challenges in convergence analysis due to the geometric structure. Nevertheless, we argue that eliminating this $O(1/\\epsilon)$ gap through more refined algorithmic design and analysis represents a promising research direction.\n\n### **References**\n[1] Yifan Yang, Hao Ban, Minhui Huang, Shiqian Ma, and Kaiyi Ji. Tuning-free bilevel optimization: New algorithms and convergence analysis.\n\n[2] Andi Han, Bamdev Mishra, Pratik Kumar Jawanpuria, and Akiko Takeda. A framework for bilevel optimization on Riemannian manifolds.\n\n[3] Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent.\n\n[4] Jihun Yun and Eunho Yang. Riemannian SAM: Sharpness-aware minimization on Riemannian manifolds.\n\n[5] Jiang Hu, Ruicheng Ao, Anthony Man-Cho So, Minghan Yang, and Zaiwen Wen. Riemannian natural gradient methods.\n\n[6] Sakai, Hiroyuki, and Hideaki Iiduka. A general framework of Riemannian adaptive optimization methods with a convergence analysis.\n\n[7] Malitsky, Yura, and Konstantin Mishchenko. Adaptive gradient descent without descent.\n\n[8] Latafat, Puya, et al. Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient.\n\n[9] Zhou, Danqing, Shiqian Ma, and Junfeng Yang. AdaBB: Adaptive Barzilai-Borwein method for convex optimization.\n\n[10] Suh, Jaewook J., and Shiqian Ma. An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization."}]

Author rebuttal:

Meta-review: ## Summary
The paper introduces a new method for solving bilevel optimization problems on Riemannian manifolds. It adjusts the learning steps based on the strength of the gradients over time. This is a fresh idea and helps improve performance in tasks that involve such spaces.

## Strengths
- **New Idea**: Adapting step sizes using Riemannian gradients is a smart and original approach.
- **Experiments**: The authors tested their method and showed it performs better than existing approaches.
- **Reviewer Feedback**: All reviewers appreciated the idea and found the paper well-written and useful.

## Improvement Opportunities
- The initial version didn’t clearly explain some technical challenges, especially the transition from Euclidean settings to the manifold setup.
- More detailed experiments in the main paper would strengthen the results. (Already clarified during rebuttal).

## Rebuttal and Discussion
- Reviewers asked for more clarity and additional experiments.
- The authors responded well and provided new results.
- Reviewers were satisfied with the changes and felt their concerns were addressed.
- The discussion showed consistent engagement from the authors.

## Decision
I recommend **accepting** the paper. For the camera-ready version, please include the new results and edits discussed during the review.
Decision: Accept (poster)