Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
Authors: Yuman Wu
Xiaochuan Gong
Jie Hao
Mingrui Liu
Venue: ICLR 2026 Poster (2026)
Keywords: Bilevel Optimization
Lower-level Uniform Convexity
Thery
Algorithm
Primary area: optimization
TL;DR: This paper provides new theory and algorithm for bilevel optimization with lower-level uniformly convex functions.

Abstract: Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-Łojasiewicz (PL) conditions for the lower-level function to establish non-asymptotic convergence to a solution with a small hypergradient. However, these assumptions may not hold in practice, and recent work (Chen et al. 2024) has shown that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients.

In this paper, we identify a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via lower-level uniform convexity. For uniformly convex lower-level functions with exponent $p\geq 2$, we establish a novel implicit differentiation theorem characterizing the hyperobjective's smoothness property. Building on this, we design a new stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on an oracle that provides stochastic gradient and Hessian-vector product information for the bilevel problems. Our algorithm achieves $\widetilde{O}(\epsilon^{-5p+6})$ oracle complexity bound for finding $\epsilon$-stationary points. Notably, our complexity bounds match the optimal rates in terms of the $\epsilon$ dependency for strongly convex lower-level functions ($p=2$), up to logarithmic factors. Our theoretical findings are validated through experiments on synthetic tasks and data hyper-cleaning, demonstrating the effectiveness of our proposed algorithm.

Published as a conference paper at ICLR 2026
BILEVEL OPTIMIZATION WITH LOWER-LEVEL UNIFORM CONVEXITY: THEORY AND ALGORITHM
Yuman Wu, Xiaochuan Gong, Jie Hao, Mingrui Liu" Department of Computer Science, George Mason University Fairfax, VA 22030, USA (ywu45, xgong2, jhao6, mingruil ) @gmu. edu
ABSTRACT
Bilevel optimization is a hierarchical framework where an upper-level optimization problem constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-Eoojasiewicz (PL) conditions for the lower-level function to establish non-asymplotic convergence to a solution with small hypergradient. However, these assumptions may not hold in practice, and recent work (Chen al. 2024) has shown that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients.
In this paper, we identify a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via lower- level uniform convexity. For uniformly convex lower-level functions with exponent p > 2. we establish novel implicit differentiation theorem characterizing the hyperobjective's 's smoothness property. Building on this, we design a new stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on oracle that provides stochastic gradient and Hessian-vector product information for the bilevel problems, Our algorithm achieves Ö(e-5p+6) oracle complexity bound for finding c-stationary points. Notably, our complexity bounds match the optimal rates in terms of the e dependency for strongly convex lower-level functions (p- = 2), up to logarithmic factors. Our theoretical findings are validated through experiments
synthetic tasks and data hyper-cleaning. demonstrating the effectiveness of our proposed algorithm.
INTRODUCTION
is hierarchical optimization framework where an upper-level optimization problem is constrained by a lower-level optimzation problem. Bilevel optimization plays crucial role in various machine learning applications, including meta-learning (Finn et al., (2017). hyperparameter optimization (Franceschi et al.) (0188.. data hypercleaning (Franceschi et al. 2017; [Shaban al.) 2019). continual learning (Borsos al., 2020; HHo et 2023). neural network architecture search (Liu et al. [20 2018). and reinforcement learning (Konda Tsitsiklis 1999). The bilevel optimization problem can be defined as:
Bilevel optimization (Bracken & McGill 1973
Dempe 2002)
min d(x) : f(x, y" (x)), xER
y² (x) E arg min g(x, v),
yERd,
where and g are referred to upper-level and lower-level functions respectively. A common assumption in bilevel optimization is that the lower-level function either strongly convex (Ghadimi
& Wang 2018 Hong al. 2023 Ji et al. 2021 Chen al. 2021a 2023 Hao al., 2024 K won
et al.] 2023a) or satisfies the Solyak-t.ojasiewei
(PI.) condition (Liu et 2022 Kwon et al. 2023b
Shen & Chen 2023) Huang 2024), which facilitates the design of algorithms with non-asymptotic
convergence guarantees for finding a solution with a small hypergradient. However, these assumptions
do not always hold in practice.
Coorreponddnnce Author: Mingrui Liu (mingruil gmu.edu).

---

Published as a conference paper at ICLR 2026
Recent work (Chen et al. 2024 has explored the relaxation of these conditions but has primarily yielded negative results. Specifically, they show that for general convex lower-level problems, bilevel optimization can be intractable with the goal of finding point with small hypergradient: the hyperobjective function can be discontinuous and may lack stationary points. This stark contrast between lower-level strong convexity (LLSC) and mere lower-level convexity (LLCC naturally raises the following question:
Can we identify an intermediate class of bilevel optimization problems that bridges the gap between LLSC and LLC, enabling the design of efficient algorithms of finding small hypergradients in polynomial time?
In this paper, we provide a positive answer to this question by introducing a function class that satisfies a property called lower-level uniform convexity (LLUCH This property serves as a natural interpolation between LLSC and LLC, controlled by an exponent p. Uniform convexity (Zálinescu 1983, Iouditski Nesterov 2014) is refined notion of convexity characterized by p 2 2, where p 2 corresponds to strong convexity.
Finding small hypergradients under LLUC presents several challenges. First, for uniformly convex lower-level functions, the Hessian of the lower-level objective may be singular, making it impossible to compute hypergradients directly using the standard implicit differentiation theorem applicable under LLSC (Ghadimi & Wang 2018). Second, the LLUC property inherently conflicts with the standard smoothness assumptions for the lower-level function (i.c., Lipschitz-contimuous gradient in terms of the lower-level variable), which are crucial for the theoretical analysis of existing bilevel optimization algorithms (Ghadimi & Wang. 2018 Hong et al.) 2023) Ji et al., 2021 Kwon et al., 2023a; Hao et al.) 2024). Consequently, addressing bilevel optimization under LLUC necessitates the development of a fundamentally different algorithmic framework and novel analysis techniques.
In this work, we tackle these challenges with two key innovations. First, we develop novel implicit differentiation theorem under LLUC, which characterizes the smoothness property of the hyperobjective, where the degree of smoothness depends on the uniformly convex exponent p. Second, to overcome the lack of standard smoothness assumptions for the lower-level function, we propose a new stochastic algorithm called UniBiO (Uniformly Convex Bilevel Optimization). After a warm-star start stage for the lower-level variable, UniBiO employs a normalized momentum update for the upper-level variable and multistage stochastic gradient descent with a shrinking ball strategy to update the lower-level variable. Notably, the lower-level updates are required only periodically rather than at every iteration. Our main contributions are summarized as follows.
We identify tractable class of bilevel optimization problems that interpolates between LLSC and LLC by leveraging the LLUC. Under this problem class, we develop a novel implicit differentiation theorem that provides an explicit hypergradient formula and establishes its smoothness property. This theorem is of independent interest and could be applied to other hierarchical optimization settings (e.g., multilevel and minimax optimization).
We design new stochastic algorithm named UniBiO, the first algorithm designed for bilevel optimization under LLUC. We prove that UniBiO achieves the oracle complexity Ö(c 65p+6 for finding an e-stationary point for the hyperobjective in the stochastic setting, where the oracle provides either stochastic gradients or Hessian-vector products. Notably, this oracle complexity matches the optimal complexity for strongly convex lower-level functions (p = 2) up to logarithmic factors.
We conduct experiments on both an synthetic task and data hypercleaning, which validate our theory and show the effectiveness of our proposed algorithm.
2 RELATED WORK
Bilevel Optimization with Lower-Level Strong Convexity, Early research on bilevel optimization
primarily focused on asymptotic convergence guarantees (Vicente et al., 1994 Anandalingam &
White 1990, White & Anandalingam 1993). A major breakthrough came with Ghadimi & Wang
(2018) which established the first non-asymptotic convergence guarantees for finding a solution
'Tee definition of i.UCCi given in Assumption 3.2
2

---

Published as a conference paper at ICLR 2026
with small hypergradient under the assumption that the lower-level function is strongly convex.
This work laid the foundation for a series of subsequent studies that improved either the complexity
or the simplicity of algorithm design (Hong et al., 2023] Chen et al., [021b] Ji et al. 202I; Kwon
let al. 2023a Hao et al.
2024 Gong et al., 2024a Chen et al. 22021a] la
Khanduri et al. 2022 Dagréou
al. 2022] Guo et al. 2021 Yang et al. 2021 Gong et al. 2024b). These works critically rely on
the implicit differentiation theorem from
Ghadimi & Wang (2018),
which is applicable under the
assumption of lower-level strong convexity. In contrast, our work does not assume LLSC, rendering
the standard implicit differentiation technique from Ghadimi & Wang (2018) inapplicable.
Bilevel Optimization with Lower-Level Nonconvexity, Bilevel optimization with nonconvex lower- level functions is generally intractable without additional assumptions (Daskalakis et al.) (021).
One common approach assumes that the lower-level function satisfies the folyak---jjasewwice (PL.) condition (Liu et al., 2022. K Kwon et al.] 2023b; Shen & Chen [023] [Huang] [024 Chen et al. 2024). Another line of work leverages sequential approximation minimization techniques (Liu et al.
2021a b 2020 to solve bilevel problems without assuming lower-level strong convexity, though these methods typically offer only asymptotic convergence guarantees. Additionally, (Arbel & Mairal (2022) employs Morse theory to extend implicit differentiation in the presence of multiple lower-level minima caused by nonconvexity. In contrast, our work focuses on a class of uniformly convex lower-level problems.
Bilevel Optimization with General Lower-level Convexity. Despite the negative results of Chen et al. (2024) under LLC from the hypergradient perspective, there is line of work which investigates algorithms converging to e-KKT solution of a corresponding constrained optimization problem (Lu & Mei 2024a b). In contrast, our work focuses on finding an solution with small hypergradient, not an KK solution for corresponding constrained problem.
Optimization for Uniformly Convex Functions. For an single-level optimization problem under uniform convexity, the work of louditski & Nesterov (2014) established first-order algorithms with optimal complexity upper bounds for nonsmooth functions with bounded gradients. Under high- order smoothness assumption, the work of [Song et al. (2019) designed high-order methods for uniformly convex functions. In addition, the work of Bai & Bullins (2024) derived lower bounds for class of optimization problems characterized by high-order smoothness and uniform convexity. In contrast, our work focuses on updating the lower-level variable using first-order methods under LLUC, without bounded gradients or smoothness assumptions.
PRELIMINARIES
Define || || as the Euclidean norm (spectral norm) when the argument is a vector (an square matrix). Define (..)) as the inner-product in Euclidean space. Denote @ by the Hadamard (element-win wwse) product. For any a E RR We adopt the notation [a] = (af: .......,)))) for E Ed to denote the element-wise power of vector., where p > O can be any positive number (e.g., integers or non- integers). We use asymptotic notation ((),,
to hide polylogarithmic factors in terms of 1/c. Define f Rd Rd + R the upper-level function, and g R R2 + R as the lower-level function. We consider the stochastic optimization setting: we only have noisy observation of f and g: f(x,y) = R.g.D, [F [F(x, y: {)] and g(x, y) = RD ( y; ()]. where Dy and D, underlying data distributions for upper-level function and lower-level functions respectively. We need the following definition of the differentiability in the normed vector space.
Definition 3.1 (Differentiabilityy Normed Vector Spaces). Let (X, || [Ix) and (Y, (Y, Ily) normed vector spaces, let E C X and 20 E be accumulation point of E. The function 8 E - Y is ((xo) J(x mo) 0.
defined to be differentiable at Zr if there exists a continuous linear function J J:X - Y (depending on and 2o) such that:
(xx)
lim 20-3300
|
zollx
In addition, J is defined the derivative of h in terms of x the point æo. i.e., J
dB(x)) dx 1==0
In the following, we will introduce the problem class of LLUC with corresponding assumptions in Section 3.1 and provide some examples within the problem class in Section 3.2
3

---

Published as a conference paper at ICLR 2026
3.1 THE LOWER-LEVEL. UNIFORM CONVEXITY PROBLEM CLASS
In this section, we introduce the assumptions that define the LLUC problem class. In particular, we identity the assumptions for both upper-level function J. lower-level function g and the hyperobjective o. We make the following assumptions throughout this paper.
Assumption 3.2. The following conditions hold for the lower-level function for some p 2 2.
For every v, g(r, y) is (n. p) -uniformmyy-ooeex with respect to y g(,, 2 g(x, m1
Vog(a, 21 v1), V2 122 vn) + # #llv2 11ll holds for any yı, 1/-
(ii g(x, y) is (Lo, Lmm-moooth in y for any given z: V w)l S Lo + L1 V x v) for any y and any æ.
(iii) Vug(a, y) is -Liisccct in x: (V)))) - Vog(>>))| - 1.11 - -x2ll for any 21 = (21, 22 = (22. E Rdd-dy
* (iv) v2 y) is 1 jointly in (z, y): II ( - V2 Kyg (22) 22 S 4,221221111 - 22 for any 21 = (I1. // ) 22 = (222 122) Rd,+4,
(v) dV Vvggamy) d'y
polan is defined in definition A.1 and 1/22 jointly Lipschitz diy "dy
exists
continuous with (ar, y):
d p dV. g(za.va) diva o0 vg(a)1)1
S 1212 z2|l holds for any 21 = ( 00 2||.
dy po
(21, v1). 22 = (x2, V2) E Rdatdy where
|| == sup||=||=1, ||
d' op
dV (Vvg((r.)) dls P(p-1)
We assume that the generalized Jacobian satisfies Amin
2 p 00 0.
(vi) ||
( d Dr
C' for some C' > O.
Remark: Assumption
3.2 specifies the key conditions imposed the lower-level function. In particular: (i) establishes uniform convexity (Zälinescu) 1983] louditski & Nesterov (014), a
generalization of strong convexity that offers greater flexibility. (ii) introduces relaxed smoothness condition (Zhang et al. 2020)) which differs from the standard L-smooth assumption. The standard T-smooth condition is incompatible with uniform convexity when the domain is unbounded, making
this relaxation more appropriate. (iii) and (iv) are standard assumptions commonly adopted in bilevel
optimization (Ghadimi & Wang 2018 Hong et al., 2023) Ji al. 2021 Kwon al. (2023)). (v) and (vi) impose differentiability of V yg(
(z. y) with respect to [y] oh (as defined in definition 3.1
with the complete definition in definition A.I). These two conditions are essential for developing
the implicit differentiation theorem under LLUC in Section 4 Note that the assumption (v) can be
replaced by the assumption that 4V aVog(a.y) is independent of [y]]--,, and more details can be found in
dly|or-1 Appendix B.2 When p- = 2. the uniformly convex function becomes strongly convex, the generalized Hessian becomes the standard Hessian matrix V (2, v). which is positive definite.
Assumption 3.3. The following conditions hold for the upper-level function f for some 2 2:
(i) Vz,(=, is ( 1/.i-joitlly Lipschitz in y): |/ [==((=)- Vaf(2e)) S L 11,11211 - 222 for any 21 = 111,,1),220 22 = (#2, 1/2) E Rdd,
(ii) ((..w)
Z|y by exists and (f.1 -ointly Lipschitz in (z, v): || 1 df(e)m))
di (22.v2) .va) d oy
S 11,11121
z2|l for any 21 (æ1, v1) E tdy, 22 (x2, v2) E tdy;
(iii)
of (r.
S 4,o0 for any x Rd and any y E 1Rd.
(iv) There exists c 0 such that 4(x)) inf, (xx) S Ao-
Remark 1: Assumption 3.3 characterizes the assumptions we need for the upper-level function f and the hyperobjective Φ. In particular: (i) and (iv) are standard assumptions in the nonconvex and bilevel optimization literature (Ghadimi & Lan 2013 Ghadimi & Wang 2018 Hong et al.) 2023| Ji et al.) 2021 Kwon et al. 2023a). (ii) and (ii) impose differentiabillty of f(z y) in terms of [ op (as defined in Definition A.I). which is satisfied for class of functions satisfying growth condition (See
4

---

Published as a conference paper at ICLR 2026
Appendix BB7 for more details). These two conditions are also crucial for the implicit differentiation theorem under LLUC in Section
Remark 2: If the differeeniaaiiliyy assumption in Assumption 3.2 (v) (vi) and Assumption 3.3 (ii) (iii)
hold with respect to the variable [y -a--aaa aa]a- with some vector E IR the analysis the implicit differentiation theorem in Section is the same in the case of 0. Without loss of generality, we simply assume a = for the clean presentation. More details are illustrated in Appendix [8.4]
Assumption 3.4. We access stochastic estimators through an unbiased oracle and they satisfy:
Eg-D, [l. V v w) م
Ec-D,
[exp(IVV,
uug(a, w)ll /o(1) S exp(1),
Eg-D,
- V <2, v) [|]]] S 02.2.
dF(a, v: df(x,
Eg-.Dy
d'y|-
dv, dyy -p-
dV
(2 v)
|"] 0
E
(3)
djy
Remark: Theorem 3.4 states that the stochastic oracle has bounded variance, which is a standard
assumption in nonconvex stochastic optimization (Ghadimi & Lan 20133 Ghadimi & Wang [0188 Ji
cet al. 2021). Additionally, it assumes that the stochastic first-order oracle for the lower-level problem
light-tailed, common requirement for high-probabilityy analysis in lower-level optimization (Lan
2012 Hazan & Kale, 2014; Hao et al.) 2024: Gong et al.) 2024a). Our unique assumptions under
LLUC are presented in Eq. (3). assuming bounded variance for generalized derivative and generalized
Hessian for upper-level and lower-level functions. When p 2, these assumptions recover the
standard ones in bilevel optimization under L.LSC (Ghadimi & Wang 2018 Hong et al. 2023).
We use Neumann series approach (Ghadimi & Wang 2018 hypergradient. Define
Ji et al. 2021 to approximate the
(f( = V F(z,vi))
Q-1 ? II (' ==1
1 dV GV, y:
dF
dly dpyjop-1
d/y)op-1
where fz(z, y: is the stochastic approximation of hypergradient ( and the randomness ę defined as E = (E. ((0), ((0), ...... ((0- 11) with ((v) (( ..... (.,,(((()))) ((
3.2 EXAMPLES
In this section, we provide two examples of bilevel optimization problems where the lower-level problem is uniformly convex. More examples can be found in Appendix A.2
Example 1. f(x,)) -² g(2,)) t ysin In this example, the LLUC holds with 4.
Example 2 (Data Hypercleaning). The data hypercleaning task (Shaban et al. 2019) aims to learn a set of weights X to the noisy training dataset Der, such that training model on the weighted training set can leads to a strong performance on the clean validation set Deat- The noisy set is defined as Der = {2,, 0: where each label T; is independently flipped to different class with probability 0 < p < 1. This problem can be formulated as a bilevel optimization task:
min Σ L(w" (X):E)
D
SEDiA
(5)
s.t. w" w*AA) arg min 10
Σ C.ED,
(l))) (.) + cllu||
DDul
where w represents the model parameters, and (xx) I+c- the sigmoid function. Note that the LLUC condition holds when the lower-level problem is l, norm regression (Woodruff & Zhang
5

---

Published as a conference paper at ICLR 2026
2013
Jambulapati et al.) 2022) problem for 2, with/without uniformly convex regularizer Sridharan & Tewari 2010).
W
If we choose L(w; <) in Equation 55) to be L(w; (i) = - w L. where Ci - (Is, is the i-th training sample. this case, the lower-level problem in Equation ( becomes
g(w, A) ||AXX 13 + cllu|lp
A diag ( /p
(A,))
(6)
7
[ :......;; :., Randd y = 11 ........ Fn]
E Rax1
w E R.
We know that g(w, A) is sum of two uniformly convex functions, and hence is uniformly convex by Assumption 3.2 (i): the summation of (HI, p) and (42.P) p)-uifformlyycooee functions is (21+H22P)) p)- uniformly-convex, The specific value of M* and μ22 can be found in Appendix A.2
The detailed proof included in Appendix A.2 The key characteristic is that the lower-level function g is not strongly convex function in terms of when 2.
4 IMPLICIT DIFFERENTIATION THEOREM UNDER LLUC
In this section, we present the implicit differentiation theorem under the LLUC condition. A key technical challenge arises from the singular Hessian of the lower-level function, which renders the standard implicit function theorem (Ghadimi & Wang. 2018) inapplicable in our setting. To overcome this, our theorem explicitly exploits the uniform convexity of the lower-level function and its high-order differentiability to establish the differentiaaility of the hyperobjective, along with its smoothness property. The formal statement is given in Theorem 4.1
Theorem 4.1 (Implicit Differentiation Theorem under LLUC). Suppose Assumption 3.2 and 3.3 hold.
Then & is differentiable in x and can be computed as the following:
dV VV (x))
df v (x))
vσ(()) Vv.(2, (z)) Vnng(a, (x))
(7)
(1)
(x))
In addition, the function & satisfies the following properties:
[[v((z1) - v Lo, |x1 22l p- + Loz1 xzll,
(8)
((x1) < ((x2) (V4(22), - xz) +22++ + (p L) 1|:0 æ2ll p-r +
Log
11:01 x2l1.
(9)
2
balleglee) Lo, 4011111 laalu luatea balla + 22.42,2222
where 1p plait
Loz = 1111 42222
Remark: Theorem 4.1 provides an explicit formula Eq. to calculate the hypergradient, as well as the smoothness property of characterized in Eq. (8). In addition, it includes the descent inequality Eq. (9) which plays crucial role in the algorithmic analysis under LLUC in Section 5 Notably, when 2, this theorem recovers the standard implicit function theorem under LLSC (Ghadimi & Waang 2018). Intuitively, as p increases, the lower-level function deviates further from strong convexity, and hence the smoothness property of the hyperobjective becomes worse. The proof of Theorem 4.1 is included in Appendix B.3
4.1 PROOF SKETCH
In this section, we provide proof sketch for the proof of Theorem 4.1 The key idea is to prove two things under Assumptions and and 3.3 (1) the optimal lower-level variable is Hölder continuous in terms of upper-level variable, which is stated in Lemma 4.2 (2) the generalized Hessian after the change of variable (i.c., y is replaced to 1y] has a positive minimum eigenvalue and hence is invertible, which is stated in Lemma B.2 These two lemmas can be regarded as counterparts of the implicit differentiation theorem under LLSC (Ghadimi & Wang 2018).
Lemma 4.2 (Hölder Continuity of the Lower-Level Optimal Solution Mapping). y²(x) is hölder continuous: for any x T2 E R&,,, we have (x2) y (z1))) & 4,1122 - x 2 where Ip is defined in Theorem 4.1

---

Published as a conference paper at ICLR 2026
Algorithm 1 EPOCIISSGD
Input: function 4), 71. Tí. D1. and total time T
2: Initialize: Wi. set T = 2(p 1) and k =
3: while Σ T, < T do
4: for ( ,.... Ta do
5: W1+11 IT wEB(w (eBsww,,Dg D&) (ut 7h (u)(w(==())
6: end for
7:
w1 k+1
Tn E/ wt
1
8:
Ta+1 = RR. Mk+1 = 72/2, Dk+1 = Dz/2#.
9:
A ++1
10: end while
Return w
This lemma shows that the optimal lower-level variable y (xx) is Hölder continuous in terms of the upper-leval variable z, with the exponent p-1' When p = 2. this lemma recovers the standard Lipschitz continuous condition of y (x) under LLSC (Ghadimi & Wang 2018 It is worth
Remark:
nothing that the existing bilevel optimization algorithms with nonasymptotic convergence guarantees
to e-stationary point all require the Lipschitzness of y (x) (Ghadimi & Waan 2018 Hong et al.
2023
al. 2021: Kwon al. 2023b; Chen al. 2024).
Building on Lemma we are ready to show the hyperobjective is differentiable everywhere and establish the smoothness property of the hyperobjective. The detailed proof of Theorem 4.1 included in Appendix B.3
ALGORITHM AND CONVERGENCE ANALYSIS
5.1 ALGORITHM DESIGN
In this section, we introduce our algorithm design techniques, leveraging our implicit differentiation theorem under LLUC. A natural approach is follows: for fixed upper-level variable z, one iteratively update the lower-level variable until it sufficiently approximates y (I), ensuring an accurate hypergradient estimation. The upper-level variable naive method may suffer from high oracle complexity. To design an algorithm with better oracle complexity, our algorithm updates the upper-level variable by normalized momentum, while the lower-level variable is updated by an variant of Epoch-SGD (Hazan & Kale 2014) periodically. The algorithm similar to the BO-REP algorithm in Hao al. (2024), but with crucial distinction: while BO-REP is designed for strongly convex lower-level problems and relaxed smooth hyperobjectives, our UniBiO algorithm is tailored for uniformly convex and relaxed smooth lower-level problems with Hölder-smooth hyperobjectives. Therefore, despite conceptual similarities in the update mechanism, UniBiO requires significantly different hyperparameter choices, such as the learning rate, periodic update intervals, and the number of iterations.
then be updated accordingly. However, this
The detailed description of our algorithm is illustrated in Algorithm 2 The algorithm starts from a warm-start stage, where the lower-level variable is updated by the epoch-SGD algorithm for certain number of iterations under the fixed upper-level variable To (line 3). After that, the algorithm follows update every I iterations (line
periodic update scheme for the lower-level variable, performing 4 6), while the upper-level variable is updated at each iteration using a normalized stochastic gradient with momentum (lines 7 ~ 8). For the lower-level update, our method employs variant of Epoch-SGD (described in Algorithm []. which integrates stochastic gradient descent updates with a shrinking ball strategy.
5.2 MAIN RESULTS
Before presenting the main result, we first introduce a few notations. Denote a(.) ) as the oalleerra generated by the random variables in the arguments. Define J, aEEi,.... E for > let be the filtration used to update {ye )T We use C₁ denote large enough constant.
7

---

Published as a conference paper at ICLR 2026
Algorithm 2 UNIBIO
Input: 7), 8, (. (K,,), (Re,), {Ki),T
2: Initialize: æ1. 1o, m1-1
3: y1 = -EPOCI--SDD(g(zo.)) a0.1, Ko,1, Ro,1, Ko)
4: for t 1, ......... do
5: if is multiple of / then
6: V/: SEOCH-SGGDgles
04,1 K,,1, Rr, Kτ)
7:
end if
8: my 8m4-1
(s, where V fxr v: is defined in Eq. (4)
9: Zt+-1 2t 17 Tmre
my
10: end for
Theorem 5.1. Under Assumptions 3.2
3.3 3.4 for any given ō (0, and
choose
01,1 =1)1, K₁, = (1), R₁,1 = 1). Kr Ö(e 2p+2), ( Q Q= Ö(1) 1
(E²²), and 1j = 3p)) (see Theorem D.1 for exact choices). Let = GAs Then with probability at least - 8 over the randomness in Fg, we have + Ei= B[[V((x)))) S where the expectation taken over the randomness in FT+1- The total oracle complexity 0(c-5pt0)
for
n
The full statement of (..erremm5.1jp included Section D Theorem shows that our algorithm UniBiO requires O -Bp+6) oracle complexity for finding an e-stationary point. To the best of our knowledge, this is the first nonasymptotic result under LLUC. In addition, when the lower function is strongly convex (p 2), the complexity bound becomes Ö(r=)), which matches the optimal rate in terms of the e dependency (Arjevani et al. 2023) for stochastic bilevel optimization under LLSC (Dagréou et al.) 2022: Chen et al. 2023). It remains unclear whether the complexity
Remark:
result terms of E is light for p >
5.3 PROOF SKETCH
In this section, we present sketch of the proof for Theorem 5.1
The complete proof can be found in Appendix [D] The key idea the proof resembles the proof Hao et al. (2024), but our proof under different problem setting (i.e., Hölder smooth hyperobjective and uniformly convex lower-level function). Define y/ y" (z,). Note that Algorithm uses normalized momentum update, therefore
||2241 zı|l 17. By the Hölder continuity of y* (z) (guaranteed by Lemma 4.2 know that llvi+1 - -ill S 1- Therefore the optimal lower-level variable moves slowly across iterations when 17 is small. Hence, the periodic update for the lower-level variable for the optimal lower-level variable the length of the period I is not too large. Lemma (5.2 [.3 devoted to control the lower-level error, while Lemma 5.4 devoted control the cummulative hypergradient bias over time. Given these lemmas, one can leverage the descent inequality Eq. (9)
still be good estimate
developed in Theorem 4.1 5.Too to establish the convergence rate. The following lemmas based Thcorems 3.2 to 3.4 The detailed proofs of this section can be found in Section[[]
Lemma 5.2. Under the same parameter setting as Theorem 5.1 for any sequence {#t. such that ån = To and [| - 5.1l n, let {ūe) } be the output produced by Algorithm 2 with input (it). Then with probability at least 5, for all t [T]] we have || 77 || < min(e/ 4L 1/L1).
Remark: Lemma 5.2 establishes a bound on the lower-level tracking error for any slowly varying sequence } under LLUC. A key advantage of this result is that it provides lower-level guarantees the upper-level variables, avoiding potential randomness
independently of the randomness dependency issues. Similar techniques have been employed in Hao et al. (022)). The main difficulty of the proof comes from a high probability analysis for handling the convergence analysis of epoch- SGD for the lower-level variable under lower-level uniform convexity and relaxed smoothness. The complete proof of Lemma 5.2 can be found in the proof of Lemma C.9 in the Appendix.
Corollary 5.3, Under the same setting in Theorem 5.1 let {xx} and {u } be the iterates generated by Algorithm 2 Then with probability at least 1 (denote this event as E) we have lly. - ye S min min(e/ATio (c/AT.22 T T/L1) for all & 1.
8

---

Published as a conference paper at ICLR 2026
(a) Deterministic case
(b) Noise N/ 0.01) (c) Noise ((0, 1.0) (d) Noise (0, 10)
Figure 1:
Convergence results for synthetic experiments on upper-level non-convex, lower- level uniform-convex bilevel optimization with varying uniform-convex parameter p
[2. 4, 6, 8) the deterministic case and stochastic case with different types of Gaussian noise (0
10) respectively.
5.2 We replace the any sequence { to the actual sequence T2 in the Algorithm 2 and obtains the same bound. The reason that the actual sequence in Algorithm satisfies the condition in Lemma 5.2
Remark: Corollary 5.3 is direct application of Lemma 5.2
Lemma 5.4. Define G := m. - VD(x,)) Under event E, we have Σ Blell S
TVT Bor Te 14.14 )) Q I-3 (I T.
1
Lemma 5.4 characterizes the cumulative bias of the hypergradient time. When is small (c.g., (E))) in Theorem 5.1) and 17 is small (c.g., O(E"P-3)), the cummulative bias grow with sublinear rate in terms of T. This lemma can be regarded generalization of the analysis of normalized momentum for smooth functions (Cutkosky & Mehta 2020) to bilevel problems with Hölder-smooth functions.
Remark:
6 EXPERIMENTS
Synthetic Experiment. We consider the following synthetic experiment in the bilevel optimization problem illustrated in Example in Appendix A g(x,8) y) 1 - y sin x, and f(x,, y) =
1リ> y ()) -1
-
+ sin(y
| S
(5)
where 1(-) is the indicator
function, p 2 2 is an even number. The goal of this experiment to verify the complexity results established in Theorem 5.1 In theory, expect that larger p will make our algorithm UniBiO converge slower.
We conduct experiments by implementing proposed algorithms with varying values of = [2, 4, 6, 8). The number of upper-level iterations is fixed at T 500, while the number of lower- level iterations is set to 100. To consider the effects of stochastic gradients, noise with different variances on the gradients, specifically NO, 10), (0, 1). and (N 0.01). Other fixed parameters are set / 0.9, 1 2.
introduce Gaussian
5, and D 1, with initialization at the point (Io, 9o) = (1, We tune the learning rates from (0.01, 0.1) for both upper-level and lower-level for every p [2, 4, 6, 8). The best learning rate choices for upper-level variable are [0.05, 0.03, 0.02, 0.01] for [2, 4, 6, 8), respectively, while the best lower-level learning rate corresponding to = [2, 8).
for every p a = [1, 1,
Figure presents the results for the deterministic setting (a) and the stochastic settings (b) (c) (d) with Gaussian noise with variances 0.01, 1 and 10 respectively. Our experimental results empirically validate the theoretical analysis of our algorithm. demonstrating that an increase in the lower-level parameter p leads a deterioration computational complexity. This observation aligns with our theoretical results. Additional experiments for various values of p and other bilevel optimization baselines (such as StocBiO (Ji et al.) 2021). TTSA (Hong et al.) 2023) and MA-SOBA (Chen et al.) 2023 are included in Appendix E.
Data Hypercleaning. To verify the effectiveness of the proposed UniBiO algorithm, we conduct data hypercleaning experiments (Shaban al. 2019) and compare with other baselines formulated

---

Published as a conference paper at ICLR 2026
Train ACC en. Epech
Tort ACC vt. Epech
Trais,CC va. raseing time (t1
TeEt vs. runsing time
044
(a) Training ACC
(b) Test ACC
(c) Training vCC's running time (d) Test ACC vs, running time
Figure 2: Results of bilevel optimization data hyper-cleaning with probability ý 0.1 and the uniformly convex regularizer !!l|| with p = 3. Subfigure (a), (b) show the training and test accuracy with the training epoch. Subfigures (c), (d) show the training and test accuracy with the running time.
in Eq. 5p. To evaluate this approach, we apply our proposed bilevel algorithms and other baselines to noisy version of the Stanford Natural Language Inference (SNLI) dataset (Bowman et al. 2015) (under Creative Commons Attribution-Shart task. The model used is a three-layer recurrent neural network with an input dimension of 300, hidden dimension of 4096, and an output dimension of 3, predicting labels among entailment, contradiction, and neutral. In our experiment, each training sample's 's label is randomly altered to one of the other two categories with probability 0.1. All the experiments are run on an single NVIDIA A6000 (48GB memory) GPU and AMD EPYC 7513 3 32-Core CPU. We have also included the experiment of p in Appendix [E.2 Our method achieves higher classification accuracy on both training and test sets compared with baselines, illustrated in Figure 4 Moreover, it demonstrates strong computational efficiency. Further details on parameter selection and tuning are provided in Appendix F The code is available https: /ttppa://ittuub... hww.:///oo.//m///mooorauu bilevel opt imi won lower -unlllunifoo www.uunioooooooooo - -i---rLLLLLMM------- Lab/
4.0 International License), a text classification
7 CONCLUSION
In this paper, we identify a tractable class bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via lower-level uniform convexity. We develop novel implicit differentiation theorem under LLUC characterizing the hyperobjective's smoothness property. Based on this, we introduce UniBiO, a new stochastic algorithm that achieves Ō(E (5p++ oracle complexity for finding c-stationary points. Experiments on an synthetic task and a data hyper-cleaning task demonstrate the superiority of our proposed algorithm. One limitation is that our algorithm design requires the prior knowledge p, but in practice, such knowledge of p may not be available. Designing universal bilevel optimization algorithm that adapts to p without explicit knowledge the spirit of Nesterov (2015) is an important challenge.
REPRODUCIBILITY STATEMENT
We provide Theorems and 5.1 in main text, the proof of Theorem Section B.3 and the proof of Theorem 5 in Section D. An anonymized code archive with training/evaluation scripts, configurations, seeds, and environment files is included in the supplementary materials. The dataset SNLI is accessible HuggingFacc under Creative Commons Aitribution-ShareA..e 4.0 International License. We include preprocessingssplitin scripts, and references to their dataset cards and licenses. These materials sufficiently support the reproduction of our results.
ACKNOWLEDDGEMENTS
We would like to thank the anonymous reviewers for their helpful comments. This work has been supported by the Presidential Scholarship. and the IDIA P3 fellowship from George Mason University, and NSF award #2436217, #2425687. The Computations were Hopper, research computing cluster provided by the Office of Research Computing at George Mason University (URL: https//orc..mm..cd
10

---

Published as a conference paper at ICLR 2026
REFERENCES
G Anandalingam and DJ White. A solution method for the linear static stackelberg problem using penalty functions. IEEE Transactions on automatic control, 35(10):1170-117) 1990.
Michael Arbel and Julien Mairal. Non-convex bilevel games with critical point selection maps. Advances in Neural Information Processing Systems, 35:8013-8026, 2022.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1-2): 165-214, 2023.
Site Bai and Brian Bullins. Tight lower bounds under asymmetric high-order h\"" older smoothness and uniform convexity. arXiv preprint arXiv:2409.10777 10773, 2024.
J Frédéric Bonnans and Alexander Shapiro. Perturbation analysis of optimization problems. Springer Science & Business Media, 2013.
Zalán Borsos, Mojmir Mutny, and Andreas Krause. Coresets via bilevel optimization for continual learning and streaming. Advances in neural information processing systems, 33: 15:11479-14899 2020.
Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. arXiv preprint arXiv: /508. 05326, 2015.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44, 1973.
Lesi Chen, Jing Xu, and Jingzhao Zhang. On finding small syper-gradients in bilevel optimization: Hardness results and improved analysis. In The Thirty Seventh Annual Conference on Learning Theory, pp. 947-980. PMLR, 2024.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294-25307, 2021a.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. A single-timescale stochastic bilevel optimization method. arXiv preprint ar arXiv:2102.046711 2021b.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. arXiv preprins vrXiv:236.112063 2023.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International conference machine learning, pp. 2260-2266 PMLR, 2020.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-267100 2022.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Stephan Dempe. Foundations of bilevel programming. Springer Science
& Business Media, 2002.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. agdel-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning, pp. 1126-1135. PMLR, 2017.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning (ICML), pp. 1165-1173, 2017.
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pp. 1568-1577. PMLR, 2018

---

Published as a conference paper at ICLR 2026
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-223 -2368, 2013.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:1802.022444 2018.
Xiaochuan Gong, Jie Hao, and Mingrui Liu. A nearly optimal single loop algorithm for stochastic bilevel optimization under unbounded smoothness. In Forty-first International Conference on Machine Learning, 2024a.
Xiaochuan Gong,
Jie Hao, and Mingrui Liu. An accelerated algorithm for stochastic bilevel optimization under unbounded smoothness. arXiv preprint arXiv:2409. 19212, 2024b.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.002666 2021.
Jie Hao, Kaiyi Ji, and Mingrui Liu. Bilevel coreset selection in continual learning: A new formulation and algorithm. Advances in Neural Information Processing Systems, 36, 2023.
Jie Hao, Xiaochuan Gong, and Mingrui Liu. Bilevel optimization under unbounded smoothness: new algorithm and convergence analysis. In The Twelfth International Conference on Learning Representations, 2024.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. Journal of Machine Learning Research, 15(1):2489- 2512, 2014.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Feihu Huang. Optimal bessian/facobian-fre nonconvex-pl bilevel optimization. arXiv preprint arXiv:2407.17823, 2024.
Anatoli Iouditski and Yuri Nesterov. Primal-dual subgradient methods for minimizing uniformly convex functions. arXiv preprint 1401.144 2014.
Arun Jambulapati, Yang P Liu, and Aaron Sidford. Improved iteration complexities for overconstrained p-norm regression. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 229-542, 2022.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference machine learning, pp. 4882 4892. PMLR, 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via momentum. Advances in Neural Information Processing Systems (NeurIPS), 34:30211-30283, 2021.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in neural information processing systems, 12, 1999.
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pp. 18083- 18113. PMLR, 2023a.
Jeongyeol Kwon, Dohyun Kwon, Steve Wright, and Robert Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01553, 2023b.
Guanghui Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133(1-2):365-33 2012.
Bo Liu, Mao Ye, Stephen Wright, Peter Stone, and Qiang Liu. Bome! bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35: 17248-17262, 2022.
12

---

Published as a conference paper at ICLR 2026
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. International Conferrence on Learning Representations, 2018.
Risheng Liu, Pan Mu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A generic first-order
algorithmic framework for bi-level programming beyond lower-level singleton. In International Conference on Machine Learning (ICML), 2020.
Risheng Liu, Xuan Liu, Xiaoming Yuan, Shangzhi Zeng, and Jin Zhang. A celteeffunctionbasee interior-point method for non-convex bi-level optimization. In International Conference on Machine Learning (ICML), 2021a.
Risheng Liu, Yaohua Liu, Shangzhi Zeng, Jin Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. Advances in Neural Information Processing Systems, 34: 8662-8675, 2021b.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1977-199,, 2024a.
Zhaosong Lu and Sanyou Mei. A first-order augmented lagrangian method for constrained minimax optimization. Mathematical Programming, pp. 1-42, 2024b.
Yu Nesterov. Universal gradient methods for convex optimization problems. Mathematical Programming, 152(1):381-400) 2015.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated tack-propagation for bilevel optimization. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1723-1732, 2019.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. arXiv preprint arXiv:2302.05185 2023.
Chaobing Song, Yong Jiang, and Yi Ma. Unified acceleration of high-order algorithms under h ({o) Ider continuity and uniform convexity. arXiv preprint arXiv: /906. 0058,, 2019.
Karthik Sridharan and Ambuj Tewari. Convex games in banach spaces. In COLT, pp. 1-13, 2010.
Luis Vicente, Gilles Savard, and Joaquim Júdice. Descent approaches for quadratic bilevel programming. Journal of optimization theory and applications, (2):37999,,, 1994.
Douglas J White and G Anandalingam. penalty function approach for solving bi-level linear programs. Journal of Global Optimization, 3:397-419 1993.
David Woodruff and Qin Zhang. Subspace embeddings ell) p-regression using exponential random variables. In Conference on Learning Theory, pp. 546-567. PMLR, 2013.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 14:13600-16622, 2021.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. International Conference Learning Representations, 2020.
Zălinescu. On uniformly convex functions. Journal of Mathematical Analysis and Applications, 95(2):344-374, 1983.
13

---

Published as a conference paper at ICLR 2026
A PROOFS IN SECTION
A.1 DEFINITION
Definition A.1.
dfaa.) 2-pa-1 and dugllayl - are defined as the following: for any y, define = - [y]0p-1
) is differentiable with Mathematically, there exist linear mappings J1. J2 such that for any Rd vector / E Rdd, and any small constant 5, the following statements hold:
and fxz 21,,2" V Vog(z,
fxx [a + = - (10,,0TT)) (J1. 0,
lim
|1hh|l
(10)
V y0, [z +-0h) 6h] @0h)0=1 --'0='111
V Vug( (t, = =0-TT) J20h
lim
6-20
|oh1|
In addition, we define J1 = 4f(a.)
df(2x," F-T) a/p)or
and J2 = (vyg(z.))
aung(a,
dz
dz
A.2 EXAMPLES
Example 1. Let functions f and g be defined as:
f(x,y) = y² g(2,8) = 71²² - y ysin z.
(11)
Now we verify the assumptions.
Assumption 3.2 (i): Since 1y² is a (1, 4)-unfform convex functioo ysin is a linear
function with y. so g(x, 1/² sin x is (1,4) uniform convex with y.
Assumption 3.2
(ii): V yn y)ll 3y² < 12 Glly² sin æ|| 12 6| V yo v)1l
hence we have L- 12, T, = 6.
Assumption
3.2 (iii): V vgg(a,)) y) = y²² - -snnn, so V vzg(z1.)) - Vug(22, w)ll sin 02
sin 1
22ll. Therefore 11.1 1.
Assumption
3.2
(iv): Vz y) = cos x. so (ang(z1,01) V (r2 U2)1
cos 122 CoS x
S [ x2l1. Therefore 4,2 1.
Assumption 3.2
(v): Vyg(a, y) y² sin x, so
dV Nol((.)
1 and
dV wol dggi
0. Therefore, 42.2 can take value 0 only for this assumption. To make 4, consistent with other assumptions, we can have 4g. 1.
dV 4|ya] pa
Assumption 3.2
(vi):]] dVVg(v..) 1, C =
Assumption 3.3
(i): Vxf(x.y) 0, so 1,11 O.
Assumption
3.3
(i): df(z.w) = 1, so
(f(().))) df(2z.02)
= 0, so 4,11
2/y/0
4|pa
Assumption 3.3
(i
df(z..) = 1, so 11.0 1.
d
Assumption 3.3 (iv): V Vyg(z, y² (x)) (x:)3 sin.r 0. so y²)x)
(sin xx)
therefore 4
sin x and As < 2.
Example 2.
In the data hypercleaning task, choose L(w, () in Eq. 5 to be
C(w; (.) = x - ".
Si (2,, T.)
i [n].
(12)
Then the lower-level objective is
g(u X) = 7
AA(W f) + +cl.+clluul c|lw|p
(13)
14

---

Published as a conference paper at ICLR 2026
where is the lower-level variable and À is the upper-level variable, and
ri
y1
( X
:
R
nxd
g
:
RR.
R
In
yn
Write = + R(.) with
G(w)= : (1w)===IAA\w - 1M
R(w) :- c.
By Assumption 3.2 (i), the sum of (Wr, p)- --n-ffommly-covvee function and a (12, -)uuuffrmlly convex function is (/1 + P2, -nn.l)-uooolll-oooeeee
We now identify and μ22-
By Eq.
16 we know that c| <| is (a.2"177 176, p) -uniformly convex. Hence 1/2 J 175
CP
By translation invariance of uniform convexity, it suffices to consider =1AXX Using the minimum singular value
Omin,p (M) = inf ||Mulpp-
||
together with standard l-f2 norm transitions for p 2 2, we obtain the lower bound
1 ||Ax!|| 2 (AX))
(14)
n. 1211/p
(Ax))
Therefore G is (Mi -uniifomly convex with [1
nd=/2-1/7
Combining the two parts via assumption 3.2 (i), the function in Eq. 13) is (1.P))-niformly convex with
(a min. (AX))
cp
1/2-1//
d1/2-1/pp
This establishes LLUC for the hypercleaning lower-level objective and quantifies its modulus.
Example 3.
Let p 2 2 be an even integer, and let the functions f and g be defined as:
-1
(
f(x,g)=
1in(y--1)
y (3) (8)
1 yp yysin (15) g(z,8) v) (8)=
p
y> 2 p-1
Now we verify the assumptions.
Assumption 3.2 (i): Note that y is a (1,p) uniform convex function, y sin r a linear
function with y. so g(z, y) 1 y ysin is (1, uniform convex with y.
Assumption 3.2
(i))
1) V (a 8)ll (p - 1)p²~ < 4(p - 2(p-1112211) 1) 11 y
sin x||
4(p 1) + 2
(r, 11, hence we have Lo = 4(p 1), Li 22(p-1).
Assumption 3.2
(iii): (g y) = y sin x, so | (2.
Vog((r2, w)ll
sin sin
|| z2||. Therefore 4,. 1.
Assumption
3.2
(iv): V Vzyg(I, y) = 00s x. so V Voyg(E1,8) v1) - V Vang(22, y2)l
cos x2 cos Φ
< [2] z2|1. Therefore lg.2
Assumption 3.2
(v): Vyg(z, y) y sin
dv vgg(zz))) and ax g(
d
0. Therefore, 1,.2 can take value only for this assumption. To make 1g2 consistent with other assumptions, we can have 1g.2 =
dVyg(0a.12)
d[pg]>p
Assumption 3.2 (vi):]l (V.g(ma)) 1, C 1.
Assumption 3.3 (i): (=f(x,8) = 0. so 4 R-2
0. To make 4,11 consistent with other
assumptions, have 1,1 (p-1) (3)
15

---

Published as a conference paper at ICLR 2026
y> (5)
Assumption 3.3 (ii):
df
cos
0,
y <<-
so from the mean-value value theorem, we have (
(x2, v2)
max
sin (1 32ll = (0-1))2) l (p-1)y²
1
d[y2]op op
(
and hence f,1 (p
(
Assumption 3.3
df(a.w) (iii):
S 1, 80 1.0 1.0 =.
Assumption 3.3 (iv): Vag(a, y (a)) = (v" (x(()))-11 sin r 0, so (x() = (sin x))
x>> D'
therefore 4 x sin sin and A. = 2.
Define x (Ii...., Td) Ra (y1,...., Ma) R p is even integer fraction of even number divide by an old number. Then we consider the following function
Example 4.
d
f(z,8) Σ
g(2,g)
1 p
lul
Σ
yi sin N,,
where sgn(-) is the sign function, p 2 2 is even number. Define yd (x) =
v)())) = (vi........
Note that Vyg(z,y"(x) = (sin 21,.., sin and ((x)
therefore we have (lvil" syn
32l" sgn(v7))
Enn byf sgn((()) = Di= i=l sin
All assumptions can be satisfied by choosing the problem-dependent parameters the following:
1
Lo
L1
4.1
1,22
C'
1,00
A
p
4(p 1)
2(p
1)
Vd
2d
d3
Table 1: Parameter values as functions of p and
( TD uniform-convex due to:
Assumption 3.2 (i):
g(x, v) is
11 2 - Illll1 >
pdd 1
(16)
Assumption 3.2 (ii): V ve y) = diag { {Ø- 1)x1 (p (p-1)88 and g( v) is
(4(p 1p 1)) -mmooth w.r.ty:
V Vor 8)|l2 = (p - 1) 1)(11))(0-2)1
< 4(p 1) 2(p 1)]1())(0-1) - sin(
S 4(p - 1) 2(p - 1) ,,g((, 2)
< 4(pp 1) 2(p 1) y v)1l2-
Assumption 3.2
(iii): The gradient V v0 v) = (yjo(e-)) is 1-Lipschitz continuuus
w.r.t. r.
Assumption 3.2 (iv) Vayg(e y) cos (x)) 1-jointly Lipschitz w.r.t. (xr y).
Assumption 3.2 and (vi): dV.g(u.))
is 0-jointly Lipschitz w.r.t. (x, and it satisfies
4---0111
the uniform bound:
dV V,, y)
Amax (I) =
d(y) (p--1)
16

---

((21,8"(22)) Published as a conference paper at ICLR 2026
Assumption 3.3
(i): Vaf(x.y) = 0 jointly Lipschitz w.r.t. (z.y):
Assumption 3.3 (ii) and (iii):
of (2.0)
= 1 is O-jointly Lipschitz and satisfies the uniform
bound:
df (r, v) dly (p-
S Vd
2
Assumption 3.3 (iv): ((00) - inf + S 2d A..
B PROOFS IN SECTION 4
B.1 PROOF OF LEMMA 4.2
Lemma B.1 (Restatement of Lemma 4.2 yf (x) is hölder continuous: for any 21, 32 E TRd,, we
have
[1y" - (x1))l & 421122 - xi11--t, where 1p = pl
(17)
Proof of Theorem B.7] Since g(x, -) is uniformly convex, for any y Rd we have the following p-th order growth condition:
v) 2 " (x1)) (Vyg(e1, (2i)).v (x1)), vn -ll mnll
p
(18)
g( y (a1)) + 11 ll (x1))).
In particular, if we let y = y/ (I22), then
g 4 (x2)) g(z1, (xI)) 2 - (x2) (I
(19)
Next, we follow the similar procedure as in proof of Proposition 4.32 Bonnans Shapiro (2013).
We consider the difference function h(y) = g(22, 3) 9( y), then we have
v h(y" (z1)) hly (x²)) ( y (x2)) 9(22, y (21)) S (hyy(())) h(y S 4.11 x1l| 11 (x2) y (x1))l
(20)
where in the first inequality we use g(z2, (I²)) S g y² (x1)), and in the second inequality we use the fact that g is 4,,1- -smooth Lipschitz constant of function h):
and mean value theorem obtain (denote x(x1, as the
k(11, x22 S sup [[ sup /V v Vyg(22, will s &bull x2ll
(21)
yERMH
yER*
Combining Eq. 19 and Eq.
yields
/ Ily (x2) y" ( - xill x1l1-11y"(ae - y (x11)l
Therefore, the Lemma is proved.
B.2 A TECHNICAL LEMMA UNDER A DIFFERENT ASSUMPTION
Lemma B.2 (Positive Definite Generalized Hessian).
dV av.g(a.y) dly by
an invertible matrix and
(Vvo(1.)) Amnin d(y] [1y]pp-1"
2 14, where Amin(-) denotes the minimum eigenvalue of a matrix.
Remark: If we do not directly assume the generalized Hessian is positive definite, under the
assumption that dV.g(ar.) -- is independent of y ( Lemma B.2 provides a characterization of the
minimum eigenvalue of generalized Hessian matrix, which plays a crucial role in establishing our implicit function theorem under the LLUC condition.
17

---

Published as a conference paper at ICLR 2026
Proof. Define [y]op-1, Since dv.glam) d| exists, then by Definition A.1
have for any h E R
and any z E IRA,, there exists linear map J2 dV. v(
4/p Pp IR xdy such that the following holds
Vyg(a, 1a 8h| V (I, 2" p-1) (J2, ot)
lim 6-0
0.
(22)
|öh
Since J2 is independent of = (by definition A. can take 0 in Eq. 22 equality and take norm on both sides, we have
rearrange this
IV yI, [8h] A V
0)1
||
lim 0
lim
(23)
||h2||
6-0 ||6%/||
By uniform convexity of g in terms of y, have
Vyg(2, )-) Veg(a, 0) 2 ~||[
2 M1ll |
2(r-11 = 111
(24)
where the first inequality holds because of the uniform convexity, the second inequality holds by the fact that ||v/| 2 l|v||2(p-1) for p 2 2, and the last equality holds by the definition of 2(p -orrr
Combining Eq. (33 and Eq.
24
we have
|220h|| |
lim
2 μ.
(25)
Since h can be vector with any direction, therefore J/2
aV.glayy
is an invertible matrix and d/
dVoo(1.)) Amin ( dy op-1
2 n.
B.3 PROOF OF THEOREM
Theorem B.3 (Restatement of Theorem 4.1..
Suppose Assumption 3.2 and 3.3 hold. Then o is
differentiable in & and can be computed as the the following:
dV V
(f y (x))
<Φ(x)= = V.f(z, Veyg(I, (x))
(26)
(x))==))o--11
In addition, the function satisfies the following properties:
[}(())) (1(x2)) I Lop ||
22 2221= + Lop || xzll,
(27)
((x1) < (x22) + (V0(2)), x2) + (p 1)L 1|, +
Loz 1| 122l2
(28)
p
2
*
where Ip plea
Le, 1061,11 + La2aa + lastea + Insleaaaa2) Los = 1,,11 + 4222a
balea + Lelliglne
Proof. Define y" (x) = [a* x'r Noting that V Vyg(E, y² (x)) = we take derivative terms of on both sides and use the chain rule, which yields
dz d' yg(a, (x))
V Vayla, (x))
(29)
dx dz)(r)
Therefore,
dz (x) dV Vygle, (x))
(30)
dx (x)
Now start derive the properties of +b
18

---

Published as a conference paper at ICLR 2026
we know that Amin ( aV (0())))) / 0 holds for any y, therefore we plug in y = v²()) and know that dV vg(z.a" (x))
By Lemma B.2
d
is invertible matrix. Hence we have
d=' dz'(x) (x)
dz dz (x) dr
dV dVgg(a,y (x)) (z)
V Vogg(, (x)
(31)
Therefore, z² =²(x) is differentiable with everywhere.
By Assumption 3.3 (iii), we know that J1 [(<a)==">)) (2)
exists. Therefore, we can use chain
rule to directly derive hypergradient formula:
(o(x)= df (x)) dx
dz (x) (f (2- (
dr
(z*(x)
dV dV (z))
(1,
vxf(I,y'(z)) v vayg(E,'"
dz(
dz'(x)
dv (x))
df (x)
-xf(a,y VayllE, (x))
(=)(
dly-()))op-1
(32)
Therefore, the final hypergradient can be computed as:
dV v (x)))
df
(Φ(2) = Vx, (a)) Vaug(z.v"<x))
(33)
(x)]oo-1
dly (z))
Define
dV Vyg(( v)
(f, y)
v(x v) = - V (, v)
(34)
dly)op -pyl
dly) op-1
Now start to prove the properties of Φ. By Assumption 3.2 (iii), we have for any 21, 222 the following inequality holds:
V Wog((11))) Vyg((22,)) w)ll </,11 - x2ll
V Va w)ll S 1,.1
(35)
so we have
dz (x))
d(y ddv((x)) (x=))o--
dV vvyg( (2, v (x)) d= (x)
1.
(r, (z)]
(36)
dr
dr
#
In addition, note that for any invertible matrices H, and H2, the inequality holds:
[H₂ HJ | (H1 H2) '1 s || ||| |||| Hall. therefore have dV (Vyo(i1 dly" (x1)) op
(37)
dV (I2,
(22)) (x2))
dV Vog(zi (0 (
d' y2 y (x2))
dly" (1r2 1p
dly (01)))9-11 d'y (xz) op-1
1222 (1æ²) 2
x21l + (x,) - 3² (x))
(38)
where the last inequality holds because of the L 1-2--oy Lipschitz in (z, u) for the matrix dV (Vg((r.))) (i.e., Assumption 3.2 (v)).
For the second part of hypergradient, we have
||o(,1, (F1) v(22. y (az2))
dV dV (a²))) dly (x2)))=)))
df(x2. (xz))
df y (a1))
Vang(Ta, (xx))
(x2) oop
dly [ 1o
dV v (22))
df (f ( (12)) (x2)
(V dV (m2))
df (m2))
V 1² (x2))
v (x1))
(xx))
(22))
(2x))o=)
19

---

Published as a conference paper at ICLR 2026
dV dV (o2))) (22))
df(r2, v Vaug(zn, (x1))
dv Vv (m1))
df y (a1)) (xr Jop-
Veyg(Ei, (x1))
(x2)
(x2) )op-
d(y((x1))
dV dV y (222))
df (x2))
dV y (x2))
(z2. V (x2))
V V (cxa)
V
dly (22) 1
(z2)
(x2
dy (22) |
[VV VV20(022 V (x2)) (xz)
(22))
dV dV v (x1))
df ((دح)
V Vogg(ar x
Vegg(z1.y
(21 /0p1
d'y (x1)
(a) 4.
V v0 (x22) - V V1 (x1))l
dv y (x1))
( (x1))
Vo (x2))
df 20 (x2)) (xz)) up-1
(1y }|p-1
(21))))
(22))=2)111
1..0
df (xn))
V v (21)))
oo (x²)) d'y" (xx))22) (22))op-
(xa))
Virg((22 y (w2))
V Vaug(ei, w (1n )1l 1o.1
(21)))))
(x1))
dV dV (12))
(x1))
(02 (12))
1..1
(32) cop-
dly (I1))
d(y) 1001
(0) 1000 IV Van((12, y (22)) Vano(Ei, V (x1)l + 1,,10
[d [d (mn))
dd vV (erly'((())) (122)
(x1)
dly((=2)) (x2))
41 df (x1))
df y (22))
(x)))
dly' (x2)]op~
1..b lalta 19111,0002 (1=) x22l + fly (z1) - y (x2)
(39)
1
where (a) holds because of Assumption 3.3 (ii)), Lemma B.2 and Eq. (35); (b) holds because of
triangle inequality of the norm, (c) holds because of Assumption 3.3 (iii) and Lemma B.2 (d) holds
because of Assumption 3.2 (iv), Assumption 3.3 (ii) and Eq. (38)
Therefore, the hypergradient satisfies the following property:
V4(2)) VV v² (z1)) + v(1 (z1)) - Vef (x2)) u(22. (x2)]l
$ <111(11=1 - x2ll + 1ly y (x2) + ||0(01, (x1) - 0(22, y (12)))
S (4,,1 + 14,00112 + 12.12.11 + 2 )||2 x21l + (11,1 + 2 Inala
l Iaulrola2 )) (z1) (x2))
1
4²2
4²
< (1111 + 1502 +
lanlsa + l2115,022 ||| x22l + (11,1 + 40002 + lgalla
1 1) 1) | 12||=
11
1
12
1 1
u²
(40)
Define Lop == -1p01pat 1o00 + balga + basygglui)) and Loz == 15.1 troooa + besles + Banleahio
1
1
Then we have
S Lop ||-11 x22 + Lopg 1011 s22l--
(41)
Furthermore, we have
((x1)- 2(z2) (V4(2)), x2)) // (V0(12 + t((1 22)) - V4(22), x2)
$ ||V0(02 + 1(21 x2)) v0(22)) x2 lll
$ |||| - -x2| 1211=9 (Lo, Lo, jdtt dt + ||ا| - x2ll L (Lozt)dt
1))
|1 x2|1 ا" + Løz || rz2
p
(42)
20

---

Published as a conference paper at ICLR 2026
B.4 GENERALIZATION OF ASSUMPTIONS
If there exists a constant a such that df(z,) ,V
1ly-o/9-Tt dy-4--p- -- exist and satisfy all of our assumptions,
we can choose (V aj)p-1, then y² (x) (+) + and we can derive the same hypergradient formula. Therefore we assume a = 0 without loss of generality. To show the fact that
the hypergradient formula is the same as in the case of a 0, we have
df(x,v" (x))
(x) (a, (x))
(
+ a)
dr
dr
d2
d( Vu [2 (z) + a)
(x, (2)(2)) +a)
Vaf(E, (x)) Vzugla, 12 (x)) +a)
dz*(x)
d=*(x)
dv (e (x)) -1 (f (x))
-af(z,y(()) Vazo(a,)(())
dly
dly((x)]<p-1
B.5 HYPERGRADIENT BIAS
Lemma B.4 (Hypergradient Bias). Suppose have inexact estimate ((x)) for the optimal lower- level variable y² (1)). Define ( = v.I(a, ((x)) - Vayg(>r, (())) dV dV.g(x..(=)) -1 (((x)(()))
Then we have
(Q(()) <<(x))I S (2)1a(()) - (x)]l
(43)
where Laz =1,11 + 4 + 1a.4/a + ooke
use almost identical arguments to prove that Vzf(z, () + vxx,z) y) is Lipschitz in (x, y). where v(x, y) is defined in Eq. (34). In particular, for any Ii I1. F2, 1h, V2, can follow the similar analysis of Eq. (39) and leverage the f,i-onnn Lipschitzness
Proof. Similar to the proof of Theorem
of fx, (i.e., Assumption 3.3 (i)) to show the following inequality holds:
V.I(E,, + u(11 V.J v( v2)
[V.[(r..)) - V.,( #2)ll [| vn) v(22, 82)
111(11=1 2all (1v1-v21)
dV v22
df (122 U2)
dV 1VVo(1111 (1)
df (x1,211) v1) d/yr opp11
(mng(e2: 82))
V (xr :1)
d(yz2 1p-1
d(yajop-1 up-1
d(yn jop-1
[dV vdValazg x2, y2)
off (22, v2) d[ya)spp1 1sp-1
dV (0)2,, (22) d 1p-1
df y2) dl [yy ip-1
$ 1,1111 - æ2l1 + I1li - 8/2 +
V 22g(202 M2))
Vang(er v1)
d [/y op-1
Vopg(er::1)
ddvio(02, U2)
(f(2
cdV (VL0,01100 v1)
df( yn) [1pz1op-1
Vayg(21,,) Mn)
d'yz) 1p-1
d d'yz]op-
19.2 ([|= .2|
S 11,1(1=1 - x2ll + 11y: y2 (l)) +
+ 11y1 y/ll))
-1.22110 [[
(dVyg(22,,) v2))
dV (Vgg(r2 3/2) d(vz) pp--
+ 1
(I (1) (211
dlyzlep-1
1
d'g1] 1p--1
d(ys)op-1
1..00222 + lealsa laalnalo22
(11251 - #2ll + I1ln - w + (
x2ll 1lln
82ll)
11
P
4²
=L, (112) - xall + Ilm wall).
(44)
Therefore, we have
[)Φ()) v S Val(a, Val(a, (-))"(()))] ||o(,, ((x)) v(a, ". (x)))l
<1,1110(2)) (x()) + (1r0092 + 1 + 1 [1((x) -
(45)
42
= Lool10(()) - (x)=)
21

---

Published as a conference paper at ICLR 2026
Therefore the proof is done.
B.6 HYPERGRADIENT IMPLEMENTATION
Lemma B.5, Denote H as
Q-1 q =
ΣI
('- C g=0
1
dV
dly]op-1
Under Theorems 3.2
3.4
have
dV y (x)) dly (x)]oo-11
1 (1 )) - μ
Bg[H]
Proof of Theorem B.5
We follow a similar proof as (Ghadimi & Wang 2018
Lemma 3.2). We have
dV, Gv, ((aw)) of
(dV vdvgga y (x)) dly^ (x:)op-1
Σ
1
Eg [
I
C
dly) op-
9=Q
V^ Q/
G Bc (l
dlyj
1
where the second inequality uses triangle inequality, and the last inequality is due Theorem B.2
Remark: Lemma B.4 provides the bias of the hypergradient due to the inaccurate estimate of the lower-level variable. This lemma is useful for the algorithm design and analysis in Section [ Also, in Section 5 we analyze the bias and variance of the estimated hypergradient fxx V, induced by
Neumann series and Algorithm and 2
B.7 SUFFICIENT AND NECESSARY CONDITION FOR THE DIFFERENTIABLITY ASSUMPTION
Lemma B.6 (Sufficient And Necessary Condition For the Differentiablity Assumption). Fix and set == 1
p-1 E (0, 1). Define the sign preserving, coordinatewise power map Sa R - Rd
by (z) = sgn(z) O |æ|a so that 24 sgn (y:) 1y4 p-1 where = Sa(z). Let h : g + R be differentiable near 0 and define r(z) ;= hS (z)). Then r(z) is differentiable at 0 with (r(0)= = 0 if and only if
[h(y))
lim 900 | p-2
Proof. By definition, r is differentiable at 0 with Vr(0) = lim [n(z)-r(0) 0.
[|]|
Let (z). Then
|||||| y/ 2(p ((0-1)) 1/2
(Sufficiency). Suppose lim,
[V 0. Since h is differentiable, for each there exists on Tw Tw
the line from ( to such that h(y) h((0) Vh(g) Hence
[2(2) - -r())
|b(y)) ||=||
h(0))
|
||=|||
Define M : max; lu:l. we have ||v|| S Vd. M and ||||| M MP-1 so
|y|
< Vd (p- (p-2) < (vd)
P- |2 (x-2) 2)
22

---

Published as a conference paper at ICLR 2026
Therefore
(r(z) - r
Vh(y)]l
sup
< (Vd)
lim sup y-+0
0.
||=||
11yl0~
2-0
Thus is differentiable at 0 with Vr(0) O.
(Necessity). Conversely, assume lim
r(s) |=|||
0. By standard result in calculus, have
rr(z) r(0) Vh(ty)
y dt
2 Vd (%.
|[ dt | (r-2) 2),
||||
|||||
where we used |2|| c 1 1)) 1/2 - vd 1 1
Since y = (z) is continuous in 2, - iff y O. Hence taking lim inf is equivalent to taking lim inf, y-0-
Taking lim inf, y- yields
1
Vh(v)l 1
0
lim inf y00
Vd
Since the ratio is nonnegative, it follows that lim, Finally, away from the origin, S. is differentiable with Jacobian
Tul O.
Vh(vil
(Sa(2) diag (a |2 --))
so for O, the chain rule gives Vr(2) (2) (z))
B.8 OTHER USEFUL. LEMMAS
Lemma B.7 (Variance). Under Theorems 3.2 to 3.4 we have
3 [(o} + 1000)00 + 2(g2) + 07
-
-,, of,
where of oz 4
Proof of Theorem
B.7 Following the proof of (Hong et al. 2023 Lemma 1) gives the result.
C PROOFS OF SECTION 5.3
C.1 CONVERGENCE GUARANTEE FOR MINIMIZING SINGLE-LEVEL UNIFORMLY CONVEX FUNCTIONS
In this section we consider the problem of minimizing single-level objective function v/ Rd + R:
min (ww)
(46)
wE24
Denote w arg min,erd a (wr) as the minimizer of w. Assume that we access (v((w) through an unbiased stochastic oracle, i.e., [vb((w; r)] (w))). We rely the following assumption for analysis in this section.
Assumption C.1. Assume function & is (n. uniiformy convex (see Theorem 3.2 In addition, the (w; noise satisfies E., (w Vv((w)(2/o')) < exp(1).
Lemma C.2. Under Theorem C.I there exists a constant G such that V d have
G, then
(xx) (x=))((x))) s G(pG/p)='T.
Proof of Theorem
C.2
By convexity of 2 and the Schwwrz inequality, have (xz) vxx") (Vú(z), x x²) < Gl x"1|.
By (μ, p)uuniform convexity vb
(xx) - (6x=)² > || x= Ir.
23

---

Published as a conference paper at ICLR 2026
Combing the above inequalities together gives || -51| s (pG/m)=T. Therefore,
(b(x)) - xx(x") - Gl| z'1l S G(pG/p)
Lemma C.3. Under Theorem
C.1 for any given w", let D be an upper bound on ||w1 w²1l and assume there exists constant G such that [Vb(w)] G. Apply the update
Wi+1 Wy 7 V Vu(wss m))
for T iterations. Then for any ó E (0, 1), with probability at least 1 ô we have
|| w0
8(G DD 3 log (2/(2/0)
(ww) - v(w)) - (2 + 0²) log(2/6)+
2yT
VT
Proof of Theorem C
Define the filtration H4 00 ..... Tt-1), where a()) denotes the we have
algebra. With minor abuse of notation, we use E = El. He]. By Theorem
V p (w:: )13
V (w:))) 112 + V Vui(w; (T) - v =
]
E,
exp
< Ee exp
4G
2
2G + 20
Vib(wr m&) Vei(w)))13)
exp
2
Er
exp
G + r²
exp(1),
(47)
where the first inequality uses Young's inequality, the second inequality due to Jensen's inequality, Since E.((Vv(we T.), Wt - w=) (Vb((s) (w;), Wi w²), then
X₁ = V (w)), wi w²) V (wri nT), we - --"
is a martingale difference sequence. Note that X can be bounded as
Xx & Vv(w:))ll w'll + (/v my) m;)
w'll 2GD + 2DI Ve(w;
where the last inequality uses ||w w'1l < l|ver - wi w| w| - w11l < 2D since v,, xx E B(wi, D). This implies that
X? 64(G2 + +
4D² (wm ( mm)l131
E,
exp
S Eg
exp
64(G2 + o²)
(ii(w me) me) 4G
< exp
E2
exp
< exp(1),
2
where the first inequality uses Young's inequality, the second inequality due to Jensen't 's inequality, and the last inequality uses Eq. 447.. By Theorem C.7 with probability at least 8/2, we have
Dt X, < 8(G + D3TTogg which implies
T
Vv((w)) w²) (Vb(wa we w²) S 8
o(G+o)D D)D 3 log(2/8)
(48)
VT
Next,
Σ (ub((m1=)111
V Vib(wa; )1
E cxp
E
Ey
exp
==
4G2 + 4
4G2 402
T- -t=1
V (Wr; TT )11
E
exp
Er
exp
40 4
40" + 402
Σts T
E
exp
exp(1)
4G2 + 4
24

---

Published as a conference paper at ICLR 2026
where the last inequality uses Eq.
447
Apply the above procedure inductively, obtain
)
E (V((w( m1)
E
exp
S exp(1T).
4G² + 4
By Markov's incquality, with probability at least 8/2. we have
Ve(ug ( $ o
By Theorem and Eq. (88) conclude that
| w011
8(G+ + DD (2/6)
(wx) - ((w)))(ww) S
s(")) 27
1og(1/)))
2>/
VT
Lemma C.4. Define D and Vk, choose n and Tı as
G(pG/n) 2
G(pG/n) 7 24 +
60 + o²)
A (ww)) V
and
Ti
G²
(49)
For any k, with probability at least (1 - -8)=-1 we have A I Vs log(2/8).
Proof of Theorem C.4 Ag VEL.
Denote & == log(2/0). We will prove the lemma by induction on k, i.e.,
Base Case. The claim is true for k = 1 since A S Vi by Theorem
Induction. Assume that A S Vg for some k 2 1 with probability at least (1 - 5)*-1 and now we prove the claim for :: 1. Since A₂ 2 p #|| w"|l [| by (u,p))uniform convexity, which, combined
with the induction hypothesis A VRa implies that
||t w'1l s (pAx/n)² DD
(50)
Apply Theorem C.3 with D D3 and hence with probability at least 8,
A k+1 ((w +((w))
s 2G +o²)(= + |/u1
11
8(G + DD)
+
2TTT.
VTh
< (G + (pAx/u)²
20(G + () 1² Vi
2yx
VTh
(G + 0z))
(pVzt/u))
20(G + (VVuu//))
24-2
2y1 Ti 2 p=2 (M-1)
/ (22
ViL
Vil
ViL
+
12
300
3
V&L
<
V4+14,
2
the second inequality is due to Eq. 50). the third inequality uses the induction hypothesis and the definition of y and Tg. and the fourth inequality is due to the choice of 71 and T; in Eq. (50).
where the first inequality uses Theorem C.3
Factoring in the conditioned event 4 S Vgl, which happens with probability at least (1 8)6-1 thus obtain that A Ve+14 with probability at least (1 - 5)*
25

---

Published as a conference paper at ICLR 2026
Theorem C.5. Under Theorem C.I given any å (0,1), set 8/kt for kt 1
(1;)(())))2
1) + 1)j. Set the parameters 111 Ti and D1 as
G(pG/u) 24 02))
== 602 + o²²
pG 1
D1 min
1og(2/8),
w
G
(51)
in Algorithm
Then with probability at least 1 - 8, we have
(60 + o²)) ェ.p (p/ p.) p- log(2/8) 0 0
(ww))= vb(w))
T2
(62 + +z²)) 2i (p/n) log(2/8) 1 (T a
11wf - w0 5
T
Proof of Theorem C.5
Recall T 2(pp 1)/p as defined in Algorithm By Theorem C.4 with
probability least 1 8.
(b + +1) v(w") = A1111 VV--1
G( log(2/0) < G(pG/1)
((7) (2 -1)+1 log(2/0)
2
I G(pGG 1og(2/0) (60 + + uা- (p/ (p/ F log(2/0)
T
T TTp-1
where the second inequality uses the definition of kt, the third inequality is due to r 2 1, and the last equality uses the definition of 7 and the choice of Ti as in Eq. (51). Also, by (4, -unnffomm convexity of zi we have
(w (ww") 1 | x w w"ll"
Combing the above inequalities yields the results.
Lemma C.6 (Hazan& & Kale 2014 Lemma 6)). Starting from an arbitrary point wi E IRd apply T
iterations of the update
Wi+1 We V We3 Te)
Then for any point w" E Rdd we have
Σ (V w²) < Vb(wni))) [[] w"
T
27
1=1
Lemma C.7 (Haann Kale, 2014 Lemma 14)). Let XI...., XT be martingale difference
sequence, i.e. E,[X,] = foor all f. Suppose that there exists T1, such that [x ////) s exp(1). Then with probability at least we have
Σ X.
3log(1/8)
Σ o6
C.2 PROOF OF L.MMA 5.2
We will use short hand y² y
Lemma C.S. Under Theorem 3.2 ify" Bly for some R > then for all ğ B(y: R),
(2(2L) Vo0(2,
T)T,
Lo
26

---

Published as a conference paper at ICLR 2026
Proof of Theorem C.8 For any y E By: R), let 1/ y and v/ then there exists Vó- V1..... ................................ 3// with j [1 1 y III such that |1y/ 9/-1ll I L/L1 for I.....J. We will prove V y0 v011 - (2' 1)L1/La for all i j by induction.
Base Case. For V/, by Theorem 3.2 we have
Lo Vog(z, v/1) - V va 16)l & (Lo + V 1bllb - v6ll s Tn
where the last inequality uses y6 = y" This implies that V 5 vfill Σ Lo/ L1-
Induction. Assume that Vug(a, a() & (2' 1)Lo/ L1 holds for some S j - 1. Then for 4 we have
Lo
V9, 16+1 - vz, 2111l S (Lo + L1 Dill. -3,1l 5
L1
where the last inequality uses the induction hypothesis. By triangle inequality and the induction hypothesis obtain 1V, v6+ I (2 1)Lr/Lu- Lu- Therefore, conclude that for any ÿ E B(y; R),
(2' 1)L- (2I4:118-v'n 1)L1
(2(2L) 11LL
|| (9( w1ll
To
To
Lo
where the last inequality uses || y2ll S 2R since ū, n² E B(y, R).
Lemma C.9 (Restatement of Theorem 5.2 For any given E (0, 1) and e > 0, set
8/(K))
for k = 1 logg(( K.
Ki,1 (2 - 1) where 7 = 2(p - 1)/p p is defined in Algorithm
Choose
{at1): [Kr,1), 1. 1. {Ki}
(2 1022all00261111 200o--6611-0 +61++1)
L Lo
=
min
(pGo/u)) log log(2/)) 96ll t=
G
L
R
c
1
t tz
min
22
Lo
AL L1
(52)
Ge(pG//1))=
602 + 02 o..1)
602 + (lgg (min(e/8l1) 1/ 1/2L 2)2(-1
01,1 = 24 + 1)
K₁,1 =
Gt
K,
(53)
For any sequence (5t) such that in To and | Tell ffr n satisfying
n (+, min
p-1
(54)
8lae
2
let {Tt} be the output produced by Algorithm have 11 Vi min(t/ (t/ALgg 1/
Then with probability at least
5, for all t E [T]
Proof of Theorem C.9 For / = 0, by Theorems
C.5 and C.8 and the choices of 00.1, Ko.1, Ro, 1 as in
Eq. 12 and Eq. (53). with probability least
/ we have 11 Øōll I min(e/88 1/2T.1]-
For t < I, we have
1
0.
S
11
W6ll
Σ
10 01 minfc/8Lo, 1/2L, 11pl 2 -
11 S min min(e/4Lo.
where the first inequality uses triangle inequality, the second inequality is due to t < and
Theorem 4.2 the last inequality uses the choice of n as in Eq. (54). For > I. apply
Theorems C.5 and C.8 with the choices of au,1, K,,, R4, in Eq. (52) and Eq. (53), then
follow the above procedure inductively, we obtain with probability at least that for all t,
llū. 0. < min(e/ mninee/TTog,1//
27

---

Published as a conference paper at ICLR 2026
C.3 PROOF OF LEMMA 5.3
Corollary C.10 (Restatement of Theorem 5.3). Let {at) and {ye} be the iterates generated by
Algorithm 2 For any given å (0, 1) and O, under the same parameter setting in Theorem C.9
with probability at least 1 - (denote this event as E) we have 18ve vill S min(e/ /// 1/ L1 for all 2 L.
Proof of Theorem C.10 yields the result.
By line of Algorithm 2 we have | Fz = 17. Setting { fxx
C.4 PROOF OF LEMMA 5.4
Lemma C.11. Under Theorems
3.2 and 3.3 define 6r. = m4 - ((re), then we have
((+++1) S ((xx)) [ + 2m1leell all|+ + (p - L)
Libe 1p?
11 x 1
p
2
Furthermore,
[ S As + T
(p (p-1)]a
np + Loz 1
2 _ |
p
Proof of Theorem C.I1 By Theorem we have
(p-
1)L
Lob
((1(+1) S (1x))) + (V F441 xe)
|2 22 -ー
+
a - xell
P
2
m
(p-
- 1)L
+ Laz 172
((x:) my Et: ||me|
n--1
P
=(xs) n mmll
mi
- (1-1)Ii
(p
n--r + Lo n?
ct.
||mm
p
(p - -1) 11ptt
L 12 1|
< (())) (x,)) + +ell + m//eell
+
+ 1?2
P
2
(p - 1)Los mp=t
L 2
S ((2)) - / < ( + 2n/l +
p
(55)
where the first equality uses the update rule (line 8) of Algorithm 2 the second inequality is due to Schwarz inequality, and the last inequality uses triangle mequality. Rearranging Eq. (55) and taking summation yields the result.
Lemma C.12 (Restatement of Theorem 5.4 Under Theorems
3.2 to
3. and event E, we have
T
σ1 +TV1 - Bog + TL, min {
P (1- 1) + 1- (Lo + Low
T
Elledl <
+
1-8
AL L1
Proof of Theorem
C212 Define é = &s(EE, y1i E.) - ( and S(a, = v - (bb(). By
Theorem 4.1 have
[|S( = (xx) ( (x++1) I)ll S Lo, 11xe - xz+ || | + Loze 1 - - 11l
S Lo, 11 + Loo
(56)
For all t 2 1, we have the following recursion:
Et+ = BEg + (1- 1--))411 + (35(21,
(57)
Unrolling the recursion gives
1-1 4+1=8' + (1- - 3)
t-1
Σ
c +
Σ
B (11-5;
i=0
1=0
28

---

Published as a conference paper at ICLR 2026
By triangle inequality and Eq. (56), we have
||e++1|| - 1 II + (1 - B)
8 1-11
+ (L, + Lise71
Σ
==0
S 3t |ell +(1 - 3)
Σ e'e 1-
+ 1-
B
(Lorn
(58)
(4)
(B)
Bounding (A). Observe that 61 81. Taking expectation and using Jensen's inequality, we have
E| = El - /
2 S 01
Bounding (B). By triangle inequality, we have
t-1 M:: E, (V U4: E.))
8 E
SE
8 (V
+ Σ (E, (V - v
1
(Laslles vē 221100 (1 ) (
3 V (1 Uoi yii E.) 13, f
Mii
E.]1112
Σ
8r
1=0
Loi
4..4. 1u 3)
11 9
min
(1-C)
Tn
where the second inequality uses Jensen's inequality and the fact that for i + j. & and & are uncorrelated, and the last inequality due to Theorem B.7 Theorem C.10
Returning to Eq. 58) we obtain
B||e++1|| < 5 01 + v1 - 301 + Lo, min
S c
1 11
+
1911E0 (1 (1-
)) +
B
(Lo + L0.1).
ALoz" L1
1
Summing from = 1 to T yields
T
Elleel <
01 1 B
+ TVT
Bor + Tlo min
{
1
+ Tg
(1- c)
11) Q
+
T
(Loinir' + L1021)
4L.zz
In
1
D PROOF OF MAIN THEOREM 5.1
Theorem D.1 (Restatement of Theorem 5.1 Under Theorems 3.2 to 3.4 for any given 8 (0,
and > set 8 = (/(Tk1) for kt L loga (( K -2
1) + 1)J, where T = 2(p-1)/p defined
in Algorithm 7 Choose {au,1 }. [Kt,1), ), (R, ), (Ke) as
(2. (201110006611+1) - L1
1.
min
(pGe/H) log(2/8)), 1130 361l
t=
Lo
G L
R
c L L1
t t
min
t2 1
Lo
(59)
G((pGr/n)= 04,1 24( + +,,,))
602 (G; + 221)
60² + (o/ K,
K2,1
G
(minfe/21e / 1/2L, 11--1
(60)
In addition, choose B, I and Q as
1 1-8 = min { 1, 2
{
(c.min
11-3 p
1- 1
p-1
(1
3)e
o. { n = 62 min c2min
Loi (p 1)L
LpL
Loz
Loo
(61)
29

---

Published as a conference paper at ICLR 2026
ME
(m
Q= In 44,
(62)
Let T C. Te
Then with probability least 8 over the randomness in Fg we have E I 6, where the expectation is taken over the randomness in Fr+1. The
total oracle complexity is 0).
Proof of Theorem
D.I
We apply Theorems C.11 and
C.12
to obtain that, under event &,
T
1 T
(p
1)
Laz
V
1 +
n
+
Eleell
TT
2
A
(p- 1) n1- +
Lidz
L
201
+2 - --81 + 2L min {
+
Tm
2
T(1 3)
4Tip In
2
Lo + - +
19,141100
(1
11 Q
C)
B
1
1
202016
1
1
+ 202 + 2)
+
2
p-r
+
+ 22/0
+
2cp-1
Ci
S,,
where the third inequality uses the choice v/ 8 and Q as Eq. (61 and Eq. (62 the last inequality is due to the choice of small enough constants C1, C2 and large enough constant C1.
Moreover, the total oracle complexity is (assume target accuracy e is small enough):
[T/l
0 T Σ
K2rQ = = (c -Spt0) Ō (c-5p-6)
(63)
5=
E ADDITIONAL EXPERIMENTS
E.1 MORE EXPERIMENTS FOR SYNTHETIC DATA
TTAA
113A
TTAA
(a) p =
(b) = 12
(C) = 20
Figure Results of bilevel optimization on the synthetic example 2 when p = {4, 12, 20). All algorithms are initialized at (zo, yo) = (0.001, 0.001), and the upper-level variable is updated for = 500 iterations. The performance of the algorithms was evaluated through the ground-truth hypergradient given by ( = sin(z) cos(sin(z)). For all algorithms, learning rates are optimally tuned with grid search over the range [0.01, 1].
In this section, we conducted extensive synthetic experiments to rigorously compare UniBiO against prominent LLSC-based algorithms, including StocBiO (Ji et al. 2021). TTSA (Hong et al. 2023), and MA-SOBA (Chen et al. 2023), under a deterministic setting. All experiments initialized at (Io, Yo) (0.001, 0.001). with the upper-level iteration number fixed at 500. Algorithm performance was evaluated through the ground- truth hypergradient given by < sin(x) cos(sin(z)) across varying p E (4, 12.
30

---

Published as a conference paper at ICLR 2026
Parameter Settings: For UniBiO and StocBiO, set Neumann series iterations Q = 10.
Momentum for UniBio and MA-SOBA was fixed at 0.9. The optimal upper- (Nu L) and lower-level
learning rates (Mx..) for each algorithm were determined through grid search over the range [0.01, 1]. Specifically the learning rates are: UniBiO (qU' = 0.02, QLL = 1.0); StocBiO (yuz = 0.5, 9L 0.1); TTSA (Muz. 0.1, TLLL 0.1); MA-SOBA (NEL 1.0, 7LL 0.01, 7 0.01). Other fixed parameters included: UniBio (1 = 10, N1 = 5, D1 = 1, T₁ = 100), StocBiO (the number of
inner iterations Tg 5), and MA-SOBA (the auxiliary variable is initialized at 20 0).
E.2 MORE EXPERIMENTS FOR DATA CLLENNCC
Train ACC un. Epoch
ACC Spock
ESRILACC va. ranning time
THEt runeing Cine
Hean
(a) Training ACC
(b) Tost ACC
(c) Training vsC running time (d) Test ACC vs. running time
Figure 4: Results of bilevel optimization data hyper-cleaning with noise ý 0.1 and = 4. Subfigure (a), (b) show the training and test accuracy with the training epoch. Subfigure (c), (d) show the training and test accuracy with the running time.
10t
reaning Ureee 22
Estimated convergence r(p)
Averaged Hypergradeent
Estimated slope k(p)
0.6
0.4
20.1
0.3
0.2
16a
Outer Iteration (log)
(a) Hypergradient decay and upper bound.
(b) Estimated slopes r(p) for different p.
Figure 5: Log-log plot of the convergence behavior of the averaged hypergradient norm under different uniform-convexity parameters p.
E.3 ESTIMATION THE CONVERGENCE RATE FOR DIFFERENT
We adopt the same configuration in the synthetic experiment under deterministic setting (i.e., no gradient noise) with outer iteration T 500 iterations in Algorithm 2 Recall that our theory guarantees power-law decay of the averaged hypergradient:
Σ (.))l ((((P))
Taking logarithms on both sides yields
log
/V (x;))
s <r(() log(t) +C,
where the slope -r(p) characterizes an upper bound on the convergence rate, and C is a universal constant.
31

---

Published as a conference paper at ICLR 2026
In Figure aa), the solid curve represents the empirically observed sequence of averaged hypergradient norms, whereas the dashed curve corresponds to the fitted power-law upper bound, obtained via linear regression on the log-log plot. We also report the runtime for different values of p.
Figure ())
reports the resulting fitted curves and the estimated slopes for p E {2,4, 8). As increases, the slope magnitude decreases, indicating slower convergence. This is consistent with complexity results as shown in Theorem 5.1
An additional observation is that the empirical convergence rates strictly faster than theoretical worst-case bound ( -3p+2) outer iterations required to find an e-stationary point (see Equation (63) This suggests either that our example not hard instance that the current complexity bound may
be tight; we leave a tighter characterization for future work. Note that there an extra D(c-5p+-9) inner iterations complexity which is reflected in the runtime result in Figure 5 In particular, the averaged inner iterations for various p = [2, 4, 6, 8] are [75, 172, 737, 3059,, which means that larger y significantly increases the inner-loop iterations (i.e., the choice of K2 as chosen in Theorem C.5 used the subroutine Epoch-SGD (i.e., Algorithm
F HYERPARAMETER SETTING
For fair comparison, we carefully tune the hyperparameters for each baseline, including upper- and lower-level step sizes, the number of inner loops, momentum parameters, etc. For the data hyper-cleaning experiments, the upper-level learning rate yj and the lower-level learning rate are selected from range (0.001, 0.1]. The best (n,,7) 7) are summarized follows: Stocbio: (0.01, 0.002), TTSA: (0.001, 0.02), SABA: (0.05, 0.02), MA-SOBA: (0.01, 0.01). SUSTAIN: (0.05, 0.05), VRBO: (0.1, 0.05). UniBiO: (0.05, 0.02). The number for neumann series estimation StocBiO and VRBO is fixed to 3, while it uniformly sampled from {1, 2, 3 in TTSA, and SUSTAIN. The batch size is to be 128 for all algorithms except VRBO, which uses larger batch size of 256 (tuned in the range of {63, 128, 256, 512, 1024]) at the checkpoint step and 128 otherwise. UniBiO uses the periodic update for low-level variable and sets the iterations momentum parameter / is fixed to 0.9 in MA-SOBA and UniBiO.
and the update interval 2. The
G THE USE OF LARGE LANGUAGE MODELS (LLMs)
LLMs are not involved in our research methodology or analysis. Their use is limited to polish the writing.
32


Reviews:
[{"review_id": "2nhDh1CTd1", "reviewer": "Reviewer_s2ox", "summary": "This paper introduces the concept of lower-level uniform convexity (LLUC) as an intermediate class between lower-level strong convexity (LLSC) and general convexity in bilevel optimization. Under LLUC (parameterized by exponent $p \\geq 2$), the authors (i) develop an implicit differentiation theorem characterizing the smoothness of the hyperobjective (showing that the hypergradient exists and is Hölder continuous with order depending on $p$), and (ii) propose **UniBiO**, a stochastic algorithm using normalized momentum for the upper level and a multistage Epoch-SGD with a shrinking-ball strategy for the lower level. They prove an oracle complexity of $\\tilde{O}(\\varepsilon^{-5p + 6})$ to find an $\\varepsilon$-stationary point, which reduces to the known optimal complexity when $p = 2$. Experiments on synthetic data and a data hypercleaning task are provided. The work aims to formalize a tractable intermediate class between LLSC and general convexity and provide the first theoretical and algorithmic results for this class.", "questions": "1. Can the authors provide a compelling, real-world machine learning example where the lower-level problem is uniformly convex with $p > 2$ but not strongly convex ($p = 2$)?\n2. What is the core algorithmic innovation in UniBiO compared to existing bilevel optimization frameworks such as BO-REP?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses an important and timely problem by extending bilevel optimization analysis beyond the conventional lower-level strong convexity (LLSC) assumption.\n2. The introduction of lower-level uniform convexity (LLUC) as an intermediate class is a novel theoretical contribution.\n3. A new implicit differentiation theorem is derived for the LLUC setting.", "weaknesses": "1. The practical motivation for LLUC is not sufficiently justified; the provided examples (e.g., $\\ell_p$-regression) appear contrived and do not reflect modern, complex bilevel learning tasks.\n2. The theoretical framework relies on multiple technical and non-standard assumptions to establish convergence.\n3. The proposed UniBiO algorithm appears structurally similar to existing methods (e.g., BO-REP), with limited algorithmic innovation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1puSRgx2Zy", "reviewer": "Reviewer_pm1j", "summary": "This paper addresses the challenge of bilevel optimization when the lower-level problem is not strongly convex. The authors identify a tractable problem class characterized by uniform convexity in the lower-level function. They establish a new implicit differentiation theorem for this class and propose a stochastic algorithm, UniBio, with a convergence guarantee of $\\widetilde{O}(\\epsilon^{-5p+6})$ for finding an $\\epsilon$-stationary point. Notably, this rate matches the optimal complexity for the strongly convex case ($p=2$). The theoretical findings are supported by experiments on synthetic and data hyper-cleaning tasks.", "questions": "1. In Algorithm 2 (line 8), a momentum term is utilized in the iterative update. What is the precise role of this term in the convergence analysis? Would its removal deteriorate the final oracle complexity?\n\n2. As noted in the weaknesses, the practical efficiency for larger values of the uniform convexity exponent `p` remains a concern. Could the authors include additional experiments, perhaps on a synthetic task, to explicitly investigate and demonstrate how the value of `p` influences the convergence speed and runtime of the proposed UniBio algorithm?\n\n3. The analysis heavily relies on the uniform convexity of the lower-level problem. Is there a potential extension of these results under a generalized Polyak-Lojasiewicz (PL) condition for the lower-level function? Could a similar tractable class and convergence guarantee be established under such a condition?\n\n4. A minor suggestion: please check some typos, such as “theoremthat” on page2; “$T_{k}$” in line 7 in Alg1 on page7.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper identifies a novel and tractable class of bilevel problems with uniformly convex lower-level functions, providing a crucial pathway between strong convexity and general convexity.\n\n2. The presentation is clear and well structured.", "weaknesses": "The oracle complexity $\\widetilde{O}(\\epsilon^{-5p+6})$ becomes prohibitively high for large $p$, creating a significant gap between theoretical tractability and practical efficiency for near-general convex problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mtXgizlMxV", "reviewer": "Reviewer_qtYP", "summary": "This paper identifies a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via lower-level uniform convexity (LLUC). For uniformly convex lower-level functions with exponent $p \\ge 2$, the authors establish an implicit differentiation theorem characterizing the smoothness of the hyperobjective. Building on this, they propose a stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on an oracle that provides stochastic gradient and Hessian-vector product information. The algorithm achieves an oracle complexity bound of $\\tilde{O}(\\epsilon^{-5p+6})$ for finding $\\epsilon$-stationary points.", "questions": "1. What is the difference between $[y]^{o\\~p-1}$ and $y^{o\\~p-1}$?\n\n2. In Assumption 3.3(iv), is the constant $\\Delta_{\\Phi}$ known? If not, would it be more appropriate to assume that $\\Phi$ is lower-bounded?\n\n\n3. In Lemma 4.3, would it be much better to analyze the error between the stochastic approximate hypergradient $\\hat{\\nabla}f(x_t, y_t;\\bar{\\xi}_t)$ and $\\nabla\\Phi(x_t)$, rather than $\\widehat{\\nabla}\\Phi(x_t)$? Since the former is used in Algorithm 2 and $\\widehat{\\nabla}\\Phi(x_t)$ is just an auxiliary quantity.\n\n4. In Theorem 5.1, the definitions of $I$ and $Q$ are not provided, and the detailed form of $\\delta$ is omitted. Moreover, standard convergence results for stochastic bilevel optimization [Ghadimi \\& Wang, 2018; Ji et al., 2021; Chen et al., 2021] typically state $\\frac{1}{T}\\sum_{i=1}^T \\mathbb{E}\\\\|\\nabla\\Phi(x_t)\\\\| \\le \\epsilon$ in expectation, not with high probability. Can the authors clarify why high probability and expectation are used simultaneously in their result?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. This paper introduces the concept of lower-level uniform convexity (LLUC) to bilevel optimization, which is new.\n\n2. For uniformly convex lower-level functions with exponent $p \\ge 2$, the authors establish an implicit differentiation theorem that characterizes the smoothness of the hyperobjective.\n\n3. The authors design a stochastic algorithm, termed UniBiO, with provable convergence guarantees, and their algorithm achieves $\\tilde{O}(\\epsilon^{-5p+6})$ oracle complexity bound for finding $\\epsilon$-stationary points.", "weaknesses": "1. My primary concerns relate to the assumptions and presentation of the paper:\n\n1-1. In Assumption 3.2(v), the notation $d[y]^{o~p-1}$ is not clearly given. Although the authors refer to Theorem 3.1, this theorem does not appear in the text. The authors also refer to Theorem A.1, this theorem also does not appear in the text (may be Definition A.1). Such omissions are critical, as this definition is important in the paper.\n\nMoreover, similar questions exist in this paper, e.g., in line 209, it should be Assumption 3.4, rather than Theorem 3.4.\n\n1-2. Some assumptions appear strong. In Assumption 3.2(v), the generalized Jacobian is assumed to satisfy $\\lambda_{\\min}\\left(\\frac{d\\nabla g(x,y)}{d[y]^{o\\~p-1}}\\right) > 0$. Does this imply that $\\frac{d\\nabla g(x,y)}{d[y]^{o\\~p-1}}$ is invertible at $y^{o\\~p-1}$? If so, Theorem 4.1 may simply review standard results for hypergradients [Ghadimi \\& Wang, 2018], rather than offering new insights.\n\n1-3. The definitions of $F$ and $G$ are not given in Assumption 3.4. Moreover, the paper focuses on stochastic methods for bilevel optimization, but there is insufficient discussion of stochastic settings.\n\n1-4. This paper is not well-written, which will make the reader confused. For example, in Sections 4.1 and 5.3, the authors introduce the proof sketches of some theorems. However, these statements can be moved to the appendix. Conversely, some important elements, such as the stochastic approximate hypergradient $\\hat{\\nabla}f(x_t, y_t;\\bar{\\xi}_t)$ in Algorithm 2, are only introduced in the appendix and should be moved to the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M4CHIdtTL9", "reviewer": "Reviewer_DjaX", "summary": "The paper introduces a new tractable problem class for bilevel optimization: lower-level uniform convexity (LLUC), and proposes an algorithm that achieves the $\\tilde{\\mathcal{O}}(\\epsilon^{-5p+6})$ oracle complexity bound for finding an $\\epsilon$-stationary point when the lower-level function is uniformly convex with an exponent $p \\ge 2$. The result in this paper recovers the known near-optimal rate when $p=2$.\n\nThe proposed algorithm consists of two loops: the inner loop applies Epoch-SGD (tailored to uniformly convex problems), and the outer loop applies normalized SGD with momentum to tackle nonconvex optimization under the generalized smooth assumption.", "questions": "Please see the weakness part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "I believe the main advantage of this paper lies in its originality, as it presents new categories of problems and studies the solution algorithms under these settings. \n\nMoreover, the proposed algorithms can recover the (near)-optimal complexity for known settings ($p=2$).\n\nThe Holder continuity of the lower-level optimal solution mapping (Lemma 4.2) and the implicit function theorem under the LLUC assumption (Lemma 4.3) presented in this paper are of independent interest and may also be helpful for other problems.", "weaknesses": "Although I appreciate the effort to introduce new problem classes for bilevel optimization in this paper, the assumptions of the introduced class do not look very clean:\n\n1. In the last item of  Assumption 3.2,  it is assumed that $\\lambda_{\\min} ( \\frac{{\\rm d} \\nabla_y g(x,y)}{{\\rm d} [y]^{\\circ (p-1)}} ) \\ge \\mu >0$. This assumption seems to be derived from the proof; can the authors provide practical examples that satisfy these conditions? For instance, does the application in Section 3.2 meet this assumption?\n\n 2. The second item of Assumption 3.4 looks strange. While the other items all assume bounded variance, the second part assumes that the noise follows a sub-Gaussian distribution. Could this be a typo?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)