Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization
Authors: He Chen
Jiajin Li
Anthony Man-Cho So
Venue: NeurIPS 2025 spotlight ()
Keywords: Bilevel optimization; Clarke stationarity; Weakly convex optimization; Set-valued functions
Primary area: optimization

Abstract: Solving bilevel optimization (BLO) problems to global optimality is generally intractable. A common surrogate is to compute a hyper-stationary point—a stationary point of the hyper-objective function obtained by minimizing or maximizing the upper-level objective over the lower-level solution set. Existing methods, however, either provide weak notions of stationarity or require restrictive assumptions to guarantee the smoothness of hyper-objective functions. In this paper, we eliminate these impractical assumptions and show that strong (Clarke) hyper-stationarity remains computable even when the hyper-objective is nonsmooth. Our key ingredient is a new structural property, called set smoothness, which captures the variational dependence of the lower-level solution set on the upper-level variable. We prove that this property holds for a broad class of BLO problems and ensures weak convexity (resp. concavity) of pessimistic (resp. optimistic) hyper-objective functions. Building on this foundation, we show that a zeroth-order algorithm that computes approximate Clarke hyper-stationary points with non-asymptotic convergence guarantees. To the best of our knowledge, this is the first computational guarantee for Clarke-type stationarity in nonsmooth BLO.  Beyond this specific application, the set smoothness property emerges as a structural concept of independent interest, with potential to inform the analysis of broader classes of optimization and variational problems.

Set Smoothness Unlocks Clarke Hyper-stationarity in Bilevel Optimization
He Chen SEEM
Jiajin Li Sauder School of Business University of British Columbia Vancouver, BC, Canada jiajin. @sauder. ubc. ca
The Chinese University of Hong Kong
Shatin, Hong Kong hchen@se. cuhk. edu.
Anthony Man-Cho So SEEM
The Chinese University of Hong Kong Shatin, Hong Kong
manchoso8se. cuhk edu.hk hk
Abstract
Solving bilevel optimization (BLO) problems to global optimality is generally in- tractable. common surrogate is to compute a hyper-stationary p stationary point of the hyper-objective function obtained by minimizing or maximizing the upper-level objective over the lower-level solution set. Existing methods, however, either provide weak notions of stationarity require restrictive assumptions guarantee the smoothness of hyper-objective functions. this paper, we eliminate these impractical assumptions and show that strong (Clarke) hyper-stationarity remains computable even when the hyper-objective nonsmooth. Our key in- gredient is new structural property, called set smoothness, which captures the variational dependence of the lower-level solution set on the upper-level variable. We prove that this property holds for broad class of BLO problems and ensures weak convexity (resp. concavity) of pessimistic (resp. optimistic) hyper-objective functions. Building this foundation, that computes approximate Clarke hyper-stationary points with non-asymptotic convergence guarantees. To the best of knowledge, this is the first compu- tational guarantee for Clarke-type stationarity in nonsmooth BLO. Beyond this specific application, the smoothness property emerges as a structural concept independent interest, with potential to inform the analysis of broader classes optimization and variational problems.
show that a zeroth-order algorithm
Introduction
Bilevel optimization (BLO) models hicrarchical decision makinng with two agents acting sequentially [13, 14]. The follower responds to the leader's decision by solving lower-level optimization problem, while the leader seeks an optimal strategy to minimize its upper-level objective subject to this reaction. The follower's attitude plays a central role: If the follower favorable (resp. adverse) the leader, the resulting BLO is termed optimistic (resp. pessimistic) [13, 51, 36]. Formally, the optimistic and pessimistic BLO take the following forms:
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Optimistic BLO:
Pessimistic BLO:
min min =ER yER"
F(x.y) y)
min max #ERm VER" subject to
F(x, y)
subject to
y E arg min (a, y'),
y arg f(z, y").
y'ER=
Y'ER"
These formulations appear in diverse domains such as Stackelberg games [14, 4, 50], hyperparameter optimization [17,3, 3, 6]. reinforcement learning [29, 55, 21], and interdiction games [36, 5], among others. A standard approach to tackle such nested problems is to reformulate them into single-level problems via hyper-objective functions. Let S(x)) == arg min (ar, y') denote the follower's optimal response set. The optimistic and pessimistic hyper-objectives are then defined as
(x(x) = min F(x,y), (
9p(x) = max F(z,y). VES(
(1)
Solving optimistic (resp. pessimistic) BLO is therefore equivalent to minimizing the corresponding hyper-objective iPo (resp. Pp)).
Despite the single-level reformulation, the resulting hyper-objective functions are highly nonconvex [8, 31J, which makes global optimization intractable. In practice, researchers therefore focus on finding stationary points rather than global minimizers, using algorithms such as implicit gradient descent [17, 18, 3] and fully first-order methods [32, 21J. These approaches assume that the lower- level problem strongly convex, ensuring a unique solution, i.e., S(x) = (x)), Under this assumption, the hyper-objective reduces to smooth function (p(x) = F(x, y (x)) [19]. One can then seek an e-approximate hyper-stationary point satisfying [[)(()) S 6. Convergence is well understood under smoothness and uniqueness assumptions [19], but these conditions rarely hold in practice. With multiple lower-level solutions, the existing methods break down.
To move beyond the singleton lower-level solution set, Kwon et al. [32] introduced penalty- based framework that allows multiple follower solutions. Building on this idea, Chen et al. [8] obtained refined scheme with near-optimal convergence. However, ensuring smoothness of the induced hyper-objective still demands strong regularity: The penalized model function ha (2c, y) == (ar, y) + fax, y) must satisfy, uniformly in a E [0, error bound Polyak-E.ojasiewicc (PL) condition in y. Such requirements are often unrealistic in practice, as F' and f typically have mismatched structures. More fundamentally, the Kurdyka-Lojasiewie: (KE) exponent is not preserved under summation [23], so smoothness of hyper-objective functions cannot be guaranteed.
Without relying on these stringent conditions, Chen et al. [7] and Khanduri et al. [28] proposed algo- rithms for nonsmooth hyper-objectives: however, by their zero-respecting nature (cf. [8. Thm. 3.2]), they cannot general approximate hyper-stationary points and thus only guarantee convergence to (approximate) Goldstein stationary points [20]-a relatively weak notion. By contrast, a separate line work studies alternative stationarity concepts via reformulations [35, 52, 38, 1, 39]; yet these notions (c.g.. KKT stationarity [37, Sec. 2.1] and penalization stationarity [54, Sec. 4.2]) are posed jointly in [x. y) and do not ensure that, for a stationary pair (#, y). the lower-level solution ý actually minimizes or maximizes F( y) over S(z).
Given the above discussion, existing algorithms either fail to approximate meaningful hyper- stationary point or rely on stringent assumptions to do so. This naturally leads fundamental question:
Can strong hyper-stationarity be computed in general settings where multiple lower-level solutions exist?
Addressing this question is challenging for a simple reason chain. When the lower level admits multi- ple solutions, the induced hypervobjective is typically nonsmooth and, under standard assumptions, no better than Lipschitz continuous [7, Corollary 6.1]. At precisely this level of regularity, computing (stronger) approximate Clarke stationary points is, in general, computationally intractable [30, 46]. Thus Lipschitz regularity alone is too weak for algorithmic purposes, motivating new, verifiable structural conditions that make meaningful hyper-stationarity attainable.
Our Contributions. In this paper, we address the above challenges and show that (strong) Clarke stationarity of hyper-objective functions computable for a broad class of BLO problems. As our key contribution, we identify hidden weak convexity/concavity structure of the hyper-objective

---

in nonconvex-PPP PL BLO. which places the analysis within the well-studde weakly convex/concave framework. Within this setting, approximate exper-stationarity admits a natural surre--uudiiffrential characterization that we leverage to obtain computable guarantees.
The foundation of our analysis is new concept, set smoothness (Definition 3), which extends classical smoothness to set-valued mappings and encompasses several variational regularity notions [40, 15, 7, 27]. Building on this notion, we prove two complementary statements. First, if the lower-level solution mapping is set smooth, then the optimistic (resp. pessimistic) hyper-objectin weakly concave (resp. weakly convex). Second, a broad and verifiable condition guarantees set smoothness: When the lower-level function satisfies error bound ceniitiion--iivveeentttitt the PE. condition-the solution mapping is set smooth. Together, these statements provide checkable criteria under which the hyper-objective inherits a weak convexity/concavity structure.
Once the hidden weak convexity/concavity of the hyper-objective in place, approximate Clarke hyper-stationary points can be computed by a simple inexact zeroth-order scheme. In the weakly convex case, results based on the Moreau envelope [12, 56, 41] provide convergence and complexity guarantees. For the weakly concave case, however, no existing algorithmic guarantee is known, and the absence a Moreau-type smoothing technique makes the analysis significantly more challenging. We overcome this by developing novel convergence proof based on Roondsted-Rockaaelllrr type approximation result [43, Theorem 2), and establish, to the best of our knowledge, the first general computational guarantee for finding approximate Clarke stationary points of nonsmooth hyper-objective functions.
Overall, these developments, particularly set smoothness, provide principled foundation for the computability of hyper-stationarity in BLO and open new avenues for other structured nonsmooth optimization problems.
Organization. This paper is organized as follows. Sec. 2 collects assumptions and preliminaries. See. 3 introduces set smoothness and uses it to reveal weak convexity/concuvity structure of the hyper-objective. Sec. 4 presents an inexact zeroth-order scheme and establishes convergence guarantees for computing approximate Clarke hyper-stationary points. See. concludes with final remarks.
Notation. The notation used in this paper is mostly standard. We use | to denote the Euclidean norm vector æ and ||A|] to denote the l2 norm of matrix A. We use BB (2z,r) r) denote the ball centering at with radius r, i.e., {x : || =|| < r}. For a scalar a E IR and set S C IR", we use a. a to denote their product {aæ æ E S}. We define the distance from vector x E R" to S by dist(æ, S) == min || =|| and the projection of æ onto S by (1) == arg minges || =||. We use Conv(S) denote the convex hull of S. For two sets S1. S IR"", define their Minkowski sum by S + S2 == {æ1 + x2 E St, E S2). and define their Hausdorff distance (with
respect || by
(5 max sup dist dist S2), sup dist Si) #2E8.
LIES:
For differentiable function IR" x R" + R, we use Vg to denote its gradient w.r.t. the joint variables (z. 8) and Vag (resp. vg) denote its gradient w.r.t. (resp. y).
2 Preliminaries
In this paper, we focus on nonconvex-Pi BLO problems and make the following assumptions:
Assumption (Lower-level Functions).
(A1). The function I is Ly-soooth and twice differentiable. Moreover, V is Hy-Lipschitz continuous, i.e., for all æ x2 I and yı 4/2 E R",
VV
VV W f 92)1 < Hy (1 x2ll 1lll yzll)-
(A2). The solution set S(x)) = arg min yin f( y) is nonempty closed convex for all x E mR..
Thht is, BLO problems with nonconvex upper-level objective and a lower-level function satisfying the PL condition.
3

---

(A3). There exists scalar 7 > 0 such that for all a E R and y E R".
S(s)( S + (x, y)
Assumption (Upper-level and Hyper-objective Functions).
(B1). The function F is M--Liscchit continuous and -m-shhoth.
(B2). There exists x' E I such that vo(x"") -xo (resp. (p((x*) < +00) for the optimistic (resp. pessimistic) seiting.
Assumptions (AI), (A2), and (B1) are standard in BLO settings; see, e.g., [21, 8, 19, 52, 1] and the references therein. Assumption (B2) guarantees that the hyper-objective functions are well-defined and is imposed without loss of generality. Assumption (A3) imposes an error bound in the lower-level variable that holds uniformly over the upper-level parameter. This requirement is strictly weaker than the strong convexity-in- conditions commonly used in prior work [18, 22, 21]. as it allows the solution set arg miny f (æ. y) be multi-valued. Under L smoothnes y. (A3) implies the PL inequality
L,
f(z 3) min f(z S
2 11 ff 8)1l for all æ E R R".
yER"
vice versus [33, Theorem 3.1]. Hence, our setting aligns with the widely adopted nonconvex- framework for BLO [45, 52, 35].
Under the standing assumptions, begin with the solution mapping 8, which under (A3) admits the following equivalent characterization:
S(x) {y E R": Vyf(z,y) = -
(2)
Furthermore, under Assumption 1, the solution mapping as well as the hyper-objective functions Po and Pp are the Lipschitz continuous.
Lemma (Lipschitz Continuity of S(x)). (cf. [7, Proposition 6.1 Under Assumption 1, the lower- level solution set function is Mg-Lipschitz continuous with Mg LJT, i.e., for any I 22 R
dи (S(z1), I Ms|læ - x2ll-
Lemma 2. (ef. [7, Proposition 5.3]) Suppose that Assumption and hold. For the optimistic (resp. pessimistic) setting, So (resp. (pp) is My-Lipschitz continuous with M₂ Mr(1 + LJr).
The Lipschitz continuity of the hyper-objective functions ensures that the Clarke and Goldstein subdifferentials are well defined.
Definition 1 (Clarke Subdifferential). (cf. [9, Definition 1.1J) For a Lipschitz continuous function g: T + I, the Clarke subdifferential g at a point x E R is defined by Ög(æ)) = Conv ({s E Rmm x' + x, Vg(a') exists, Vg(x') - 8}). We say that is an (e, 8) -approxiieteee Clarke stationary point of if
UUU 0g(z)
dist 0.
Sec.
=E2((0.8)
Remark 1. The Clarke subdifferential ôg reduces to the gradient Vg when g is smooth. Moreover, if g is convex, then 0g(x) coincides with the vanilla subgradients defined by {s g(z) 2 g(x)
(z x) V P.
Then, the Goldstein ð-subdifferential æ can be constructed by the convex hull of the Clarke subdifferentials taken over 5-neighborhood of æ. Here is the formal definition of Goldstein 5-subdifferential.
Definition 2 (Goldstein S-Sudiiffeeential), fef. [20, Definition 2.21) For Lipschitz continuous function Rm > IR and scalar 8 2 0, the Goldstein S-subdifferential of g at point x E R is defined by
(Lu
})
UUU 0g(z)) *x)
Osg(z) = Conv
We say that is an ( aappooxxxeeeeeee Goldstein stationary point of g if dist (0, dsg(x))

---

Leveraging the Lipschitz continuity of the hyper-objective, recent work has established the com- putability of (c, (eod))GGodstein hyper-stationary points [7]. However, Goldstein stationarity strictly weaker and does not, in general, imply Clarke stationarity. Indeed, there exists convex, 2- and point a such that æ is (G.d)_Goldstein stationary while
Lipschitz function 9 : R2 min dist((0, 0ī(z)) z 2: see [47, Proposition 2.7]. To obtain stronger algorithmic guar- antees for hyper-objective minimization, we therefore focus computing Clarke stationary points (and their (e, aapproxximaee variants).
V5
Despite the well-definedness, approximate Clarke stationarity is not achievable in finite time for general Lipschitz functions [30, 46]. A sufficient condition for its computability the weak convexity of g [12]. To elaborate on this, review some basic properties of weakly convex functions. Given a function g IRm + I and a scalar > O, we say that is r-weakly convex if the function g - _||==||2 is convex. The following equivalent characterizations useful for our analysis.
Lemma 3 (Equivalent Characterizations of Weak Convexity). (ef. [11, Theorem 3.1] and [2, Proposition 2.2]) For Lipschitz continuous function g R - R. the following statements are equivalent:
() is r-weakly convex.
(ii) For any E [0, 1] and æ1, 22 IRm,, we have
g (0xl + (1 -1-00a 0) s 0g(wi) + (1 (1-0)g(x²2) + _ 2001 - 0)] - x2112
(iii) For any 31, D2 E Th with 0g(x11) ) * Ø, and all subgradients v E 0g((x)), ). we have
" 00 - a1)) v g (x22 ) - g(x1) + || -
x1 -x1ll
For r-weakly convex function g: m IR with 7 (0, H define its Moreau envelope and the proximal mapping by
[(()) + ==1?? } 2
1
(x(xx) = inf zERe"
(x) prox,, (x) = arg min g(x)) +
|| =1|
*ER"
27
Clearly, prox,., (a)) is single-valued and well-defined, when g is r-weakly convex and 7 < J. Next, we provide the standard result, which establishes stationarity measure based on the gradient of the Moreau envelope.
Lemma (Properties of Moreau Envelope). (cf. [56, Proposition 2.1)) Suppose that g IR" R is a r-weakly convex function and < +. The following hold:
(i) gr (x) S g(x)
1-3r
- proxx., (x)
27
(ii) dist (g()) s ||0 , (z) I --. dist (0, (g()))
(ii) , (x) if and only if0 0g(x).
(iv) Vg. (a: + prox.,,
p (w))
Lemma (ii) and (iv) show that Vzy(x)) equals zero if and only x prox..g (z) and 0 E 0g(x). Thus Vg, (x)]l is valid Clarke stationarity measure. Moreover, by Lemma (iv), if / (x) e. then prrox,. (x) - x >ll Vg, (x)]l < 7e, hence dist (0, 0g (x))) < Equivalently,
[g)] Se
dist 0, 0g(z)
U xEB((,
Se.
Since Davis and Drusvyatskiy [12] establish non-asymptotic rates for finding ær with (z) Se when g is weakly convex, (3) implies that (c, approximaee Clarke stationarity is computable in
5

---

this regime. This observation motivates us to establish weak ceaa--covveitt-ooo type structure for hyper- objectives: see Sec.
Before leaving this section, we record weak concavity, a notion closely related to weak convexity. For function g IR" -> IR, say that g is r-weakly convex if -9 is r-weakly convex. We have the following facts.
Fact 1. If a function g 1.Th + RR is r-weakly concave, thenfor any 3i, 22 E R,, and v E 0g(x1), we have 9(æ2) S g(x1) + v² (x2 x1) + = x x1l1².
Fact 2. If a function g Im - R is r-smooth, then g is r-weakly convex and r-weakly concave, and the following inequality holds:
(0g(z1) + (1 0))(()2) - g (0z: (1- - - 20 0)|| =02ll?
3 Unveiling Hidden Structural Properties
This section is devoted to unveiling the hidden structural properties of the hyper-objective functions, which is the key contribution of this paper. Recall that the hyper-objective functions in (1) are defined by minimizing/maximizing the upper-level function w.r.t. y over the parameterized set S(z). We are motivated to investigate the property of the set-valued function S. Inspired by the smoothness of real-valued functions, we propose novel concept of smoothness for set-valued functions, formalized in Definition 3. As we will show, the lower-level solution set function S satisfies this smoothness property, which in turn ensures the weak concavity (resp. convexity) of Yo (resp. Ppp)
Definition 3 (Set Smoothness). For a set-valued function y _ = R" with convex domain do C Imm we say that it is L-smooth if for any æ 22 E dom()), 0 E [0, 1], and all y E (6x) (1 f)xz)), there exist y1 E (x1)) and y2 E (x22) such that
|0y1 + (1 - -0)y2 - yl S 0 - 0)| - x22 12:
(4)
2
11y1 12112 s L |
xz2 13.
(5)
The condition (4) can be viewed as a natural extension of the gradient- peadient-Lipschine Lipschitz smoothness condition for real-valued functions to the setting of set-valued mappings. It guarantees that a convex combination of ÿı (x)1)) and y/2 E (xx2) provides close approximation
point in (( + +1 0)xz2)
with an error that decays quadratically in ||æ æ2//. This yields the following set inclusion:
y' (0x) + (1 0)02) S ()())) + (1 - -1-0) (=)))))))))))))))))))))))))))))) + - 0(1 - 0)| - x2 12 B(O, 1).
(6)
Intuitively, (5) enforces a consistent branch selection between (aa1) and y(z2): The chosen
representatives yı and y/2 must remain aligned (Lipschitz-close) as the input varies, thereby excluding cross-branch pairings that could make the interpolation in (4) hold trivially while the underlying geometry is severely mismatched.
Example (Why the condition (5) is needed: A trivialization for the condition (4)). Define the set- valued map } - = I²² by Fxx) = [(2 x) i RJ. Pick 2 = a > 0, 22
and 0 1; then 0x1 + (1 0) // = 0 and (0) = {z,,0) 0) z E IR.. Choose y = 0 E (00). y/1 = (K, a) E (a).
and y2 ( K, a) E aa)a). We have
2 y1
+ 2
U2
= y.
so the condition (4) holds with zero emrr even though | y2l 2Va2 + K2 can be made arbitrarily large as - oc. Hence the condition (4) alone does not preclude severely mismatched pairings convex domain. In contrast, (5) enforces | y2ll S L| z2 = 4La?. which forces K² < (L 1)a² and thereby rules out such cross-branch selections unless the Lipschitz modulus correspondingly large.
With the notion of set smoothness in place, we now present our first main theoretical result. It shows that set smoothness serves as the key vehicle for establishing weak convexity/concvityy of parametric optimization problems with coupled constraints: Under mild Lipschitz-type assumptions, the induced value function inherits weak convexity (or weak concavity). This is formalized in Theorem below.

---

Theorem 1 (Implication of Set Smoothness), Consider real-valued function g I x R" + R and a set-valued function y R.' = R.. Let ((z) := maxyey(a) g(z, y) and D = {z o(x) > xo). Assume that 'D is nonempty closed conver set, y is Lyy-smooth on 'D, and is Mg-Lipschitz continuous w.E.f y. -moothh on D x Conv (UZED M())). Then, the function @ is p-weakly convex with M2 + (1 + Ly)..
We now instantiate the framework in the bilevel setting. Our first step is to certify set smoothness for the lower-level solution map. Under the error-bound (EB) condition in Assumption 1 (A3), the mapping S æ + arg millER= f(x, y) is Ls-smooth (Theorem 2). Combining this with Theorem shows that the pessimistic oyper-objecttve Pp inherits weak convexity (resp. the optimistic Po inherits weak concavity).
Theorem 2 (EB Implies Set Smoothness). If a function f R x R + R satisfies Assumption 1, then its associated solution set function S. + arg ungminger f(x, y) is Ls-smooth with Ls max ( -
Proof idea (why residual backfilling is essential) Fix æ1, and 0 E (0, and set x. = 0z + (1 02 Given any y E S(æ"), our goal is to select y E S((1) and y/2 E S(x2) so that (4) and (5) hold, A natural choice is to project y onto the endpoint fibers, yielding y; (1)
for i = 2. Using Lemma 1, it is easy to see that this naive selection satisfies (5).
However, even when each fiber S(x)) is convex, the midpoint 7² 0 ÿ + +11 (1-0) D2 may correspond, at æ", to a different local selection of the set-valued map S-)) than the given y E S(æ"). Consequently, in general multi-solution settings the naive midpoint error can be first-order,
- y = @(1 x221).
which motivates an additional correction to synchronize the selections.
We therefore align the midpoint and backfill the residual: First project the naive midpoint to the middle fiber, ò == (Ts(=") and then use the residual y - 4 to refine the endpoint representatives:
y/
Is Ø: (y ú)
2.
This construction cancels the first-order branch mismatch in the convex combination and leaves only a quadratic remainder. Consequently, (4) holds while (5) remains valid.
Think of S(x)) as family of convex "fibers". The direct projections Y1, may live on selections that are not synchronized with the selection containing y, so their convex combination carries first-order drift. Projecting ÿ" to S(x") identifies the correct selection at the midpoint; adding the same residual y - ÿ to both endpoints moves them to the same selection as y, making the first-order terms cancel in the average and exposing the desired ([ x22 behavior.
Remark 2.
Theorem 2 is not limited to the lower-level problem of BLO but applies to general parametric optimization problems. The established set smoothness property offers new insights into the structure of the solution mapping, which goes beyond the variational conditions considered the literature [40, 27, 15, 7, 53].
Remark 3 (Local Conditions are Sufficient). Suppose the solution mapping S is defined on a bounded convex domain C R To ensure Theorem 2, it suffices that Assumption 1 holds on the set x D. where
(U (US(z)) LED
y = Conv Conv
+ Ms diam(D) B)..
The following simple example shows that the set smoothness of S does not, in general, require Assumption This suggests that alternative sufficient conditions may guarantee set smoothness; identifying such conditions is an interesting direction for future work.
Example 2. Consider f 2² - R defined by ff fx, 3/ g(sin x + y), where g R R has a nonempty set of minimizers V = arg minzeR R 9()). Then the solution set admits a closed form:
S(z) = arg min f(z, v) = V - sin r == { sin : U E V.
pER
7

---

In particular, S is 1-smooth in the sense of Definition 3 (since it is translation of the fixed set V by the scalar sin r)), even though f need not satisfy Assumption
With Theorems and 2 in place, we now state our main result on the weak convexity/concavity the hyper-objective yoo (resp. spy).
Theorem 3 (Weak convexity/concavig of the hyper-objectives), Assume Assumplions I and 2. Let Ls be the sel-smoothness modulus of S from Theorem and define p = Mp Lis LF (1 + Ls).. Then the sollowing hold:
ii) The optimistic hyper-objective ipo is p-weakly concave.
iii The pessimistic hyper-objective (pp is p-weakly convex.
Proof of Theorem 3. Theorem 2 guarantees that the set-valued function S is Ls-smooth. Then, the result (ii) directly follows from Theorem I. Hence, we only need to prove (i). Note that
(x(x) = min F(z, y) max -F y). vES(2)
yES(#)
We that -Po is p-weakly convex by Theorem 1. It follows that po is p-weakly concave.
Theorem establishes the weak concavity/convexity of the hyper-objectives in nonconvex- PL bilevel optimization (BLO). This stands in contrast to classical results (e.g.. [19, Lemma 2.2]), which impose strong convexity of the lower level obtain smooth hyper-objectives. Our result is significant because it places the minimization of these generally nonsmooth hyper-objectives within the framework of weakly concave/convex optimization. As consequence, computing approximate Clarke hyper- stationary points becomes tractable-an avenue we pursue in the next section. Crucially, all of these developments hinge on the set smoothness property (Definition 3), highlighting the utility this notion.
Remark 4 (Lower-level Constraints Matter). Under Assumptions I and 2, imposing an upper- level constraint x E X C R" with X nonempty, closed, and convex preserves the conclusions of Theorem 3: The functions (o(x) + (x(x) and 9p(x) + (x(x) remain weakly concave and weakly convex, respectively, where ix denotes the indicator of X. contrast, adding a lower-level constraint E e can destroy the weak concavitylconvesity of the hyper-objectives, because the set smoothness of S may fail in this case; see Example 3. Developing structural conditions that recover such properties for lower-level constrained BLO is interesting direction for future work.
Example Let ) [0,1] [0, Consider the pessimistic bilevel problem with a lower-level
constraint:
min max #ER yER²
-1Ty
s.t.
(z, y arg arg min 11 (x, 2) v'EY
Assumptions 1 and are directly satisfied for (7), except the unconstrained lower level; the only deviation here is the added constraint y E y.
The lower-level solution set is the projection of (z, 2) onto the box V, hence
((0,)), 1)), x < 0.
S(x) ((x,1)) ((1,1)),
0 x 1 x #>1
Therefore the pessimistic hyper-objective is
1,
I x
px(x) =
1,
0 x <
2, 12
This function is not weakly convex. Indeed, for any p > 0 consider hx(x)) ()(x)) + f2² Then hp has left and right derivatives at 0 given by (0-) 0 and (0+ -1 (the quadratic term has zero slope at 0), which violates the monotonicity of one-sided derivatives required by convexity.
Then
Hence no p makes ho convex, i.c., Sp is not weakly convex.

---

Computing Approximate Clarke Hyper-stationarity
Equipped with the weak convexity/coneavity of the hyper-objectives, our next goal to establish the computability of Clarke stationary points. First-order methods are impractical here because sub- gradients the hyper-objectives are typically unavailable. In contrast, under mild conditions- F(z, -) is concave (resp. convex) so that the inner maximization (resp. minimization) is tractable, the function values of the hyper-objectives can be (approximately) evaluated given æ: [16, 44]. This motivates the use of zeroth-ordes methods for minimizing hyper-objectives [7, 34]. In particular, we adopt the inexact zeroth-order method (IZOM) Algorithm I, which employs a deterministic subroutine A to approximately evaluate (z)(z) (with additive accuracy w) by solving the inner problem in (1); see [7, 24-26] for practical implementations of A.
Algorithm Inexact Zeroth-ordee Method (cf. [7, Algorithm 2J)
Input: Radius > O, iteration number T E N, stepsize n), initial point E R inexact error w > and mode parameter {1,0}
for t= 0, ,.
do
Sample u4 from the the uniform distribution on the unit sphere in I..
Compute Al (T; + Eu,) and A (a: -Eu) by subroutine A
Set G(x,) (A (2x Eu,) Alt (x. Eu.))u u4
3:+11 = Et (ar.)) end for Output: & uniformly chosen from {2
Algorithm 2 Deterministic Subroutine A
Input: Accuracy w 0, iterate point E IR" and mode B (1,0)
if 3
then
Compute value ((x) satisfying (fxx)) (p(())] S w
else
Compute a value ((x) satisfying (p(x)) (pp())) S w
end if
Output: (x) ((x)
Let sppy denote the Moreau envelope of Pp with parameter 7, We quantify hyper-stationarity as the approximate Clarke stationarity measure, i.e., Definition 1,
follows: In the optimistic case while the pessimistic case we use the gradient norm of the envelope, i.e., || [/V (a:) These two criteria can be unified in principle via (3); in either form they are strictly stronger than the Goldstein stationarity measure; see Sec. 2.
We then present the main theorem of this section.
Theorem 4. Suppose that Assumptions I and 2 hold. Given an iteration number T E N, set ((m TT )),e= = O(T 1), ) O(m T for Algorithum 1. Then, the following hold:
()) Let A. (x()) min (a(a)) + 2M with Mo given in Lemma 2. For optimistic BLO, we have
with 10 (T (vm(A. +1) VT
E dist (0.U
iii Lety (0, ++) with p 0 given in Theorem 3, and Ap (p.((2o) min (p.) For pessimistic BLO, have
Vm Ap + +1)
V.p (+)]]]] =
Theorem 4 demonstrates, for the first time, that approximate Clarke hyper-stationarity is computable for nonconvex-Pi BLO both optimistic and pessimistic settings. This result significantly improves the existing computational guarantees for nonsmooth hyper-objective functions, which are mainly based on the Goldstein stationarity [7, 28). The proof of the optimistic case relies on Brøndsted- Rockafellar- like relation, details of which can be found in Appendix D.I.

---

Conclusion and Discussion
In this paper, we established the first thcoretical guarantce for computing approximate Clarke hyper- stationarity in nonconvex-PE BLO. The key step is unveiling the hidden structural properties of hyper-objective functions via the newly introduced smoothness concept for set-valued functions. Specifically, we proved that (i) the smoothness of the set-valued function y ensures the weak convexity of the function æ H max ((x, y): and (ii) the lower-level solution set function of BLO satisfies set smoothness. Consequently, we obtained the weak convexity/concavity of hyper- objective functions. With these properties in hand, we showed that an inexact zeroth-order method compute approximate Clarke stationary points of hyper-objective functions.
We believe that our developments contribute to deeper understanding of the computability properties of BLO and open up several directions for future research. First, with the established structural properties, our work calls for designing faster algorithms for computing Clarke hyper-stationarity Second, it would be valuable to generalize in other settings (e.g., structured lower-level constrained BLO [28]). Furthermore, our set smoothness property, along with Theorem 1, may find applications in other fields such coupled minmax optimization [48] and set-valued optimization [27], where set-valued functions play a central role.
methodology to establish adapted properties for BLO
Ackonwledgements
Jiajin Li was supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant RGPIN-2025-0581 Anthony Man-Cho So was supported in part by the Hong Kong Research Grants Council (RGC) General Research Fund (GRF) project CUHK 14204823.
References
[1] N. Abolfazli, Sharifi, M. Fazlyab, and E. Yazdandoost Hamedani. Perturbed gradient descent via convex quadratic approximation for nonconvex bilevel optimization. arXiv preprint arXiv:2504.1 17215, 2025.
[2] Atenas, C. Sagastizábal, P. J. Silva, and M. Solodov. A unified analysis of descent sequences in weakly convex optimization, including convergence rates for bundle methods. SIAM Journal on Optimization, 33(1):89-115, 2023.
[3] Q. Bertrand, Q. Klopfenstein, M. Blondel, S. Vaiter, A. Gramfort, and Salmon. Implicit dif- ferentiation of lasso-type models for hyperparameter optimization. In International Conference on Machine Learning, pages 810-821. PMLR, 2020.
[4] M. Brückner and T. Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 547-555, 2011.
[5] A. Caprara, M. Carvalho, A. Lodi, and G. J. Woeginger. Bilevel knapsack with interdiction constraints. INFORMS Journal on Computing, 28(2):319-333, 2016.
[6] H. Chen, H. Xu, R. Jiang, and A. M.-C. So. Lower-level duality based reformulation and ma- jorization minimization algorithm for hyperparameter optimization. In International Conference on Artificial Intelligence and Statistics, pages 784-792. PMLR, 2024.
[7] L. Chen, J. Xu, and J. Zhang. On bilevel optimization without lower-level strong convexity. arXiv preprint
0tth:2331.007111 2023.
[8] L. Chen, J. Xu, and J. Zhang. On finding small hyper-gradient, in bilevel optimization: Hardness results and improved analy sis. In The Thirty Seventh Annual Conference on Learning Theory, pages 947-980. PMLR, 2024.
[9] F. H. Clarke. Generalized gradients and applications. Transactions of the American Mathemati- cal Society, 205:247-262, 1975.
[10] H. Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990.
[11] A. Daniilidis and J. Malick, Filling the gap between lower-C1 and lower-C2 functions. Journal of Convex Analysis, 12(2):3 2005.
10

---

[12] D. Davis and D. Drusvyatskiy. Stochastic model-based minimization of weakly convex functions.
SIAM Journal on Optimization, 29(1)2007- 2019.
[13] S. Dempe. Foundations of Bilevel Programming. Springer Science Business Media, 2002.
[14] S. Dempe and A. Zemkoho. Bilevel optimization. In Springer Optimization and Its Applications, volume 161. Springer, 2020.
[15] A. L. Dontchev and R. T. Rockafellar. Implicit Functions and Solution Mappings, volume 543. Springer, 2009.
[16] Dutta and TT. Pandit. Algorithms for simple bilevel programming. Bilevel Optimization: Advances and Next Challenges, pages 253-291, 2020.
[17] L.. Franceschi, M. Donini, P. Frasconi, and M. Pontil. Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning, pages 1165- 1173. PMLR, 2017.
[18] L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-lcarning. In International Conference Machine Learning, pages 1568-1577. PMLR, 2018.
[19] S. Ghadimi and M. Wang. Approximation methods for bilevel programming, arXiv preprint arXiv:1802.022446 2018.
[20] A. A. Goldstein. Optimization Lipschitz continuous functions. Mathematical Programming, 13:14 22, 1977.
[21] M. Hong, H.-T. Wai, Z. Wang, and Yang. two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-184) 2023.
[22] K. Ji, J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning, pages 4882-4892. PMLR, 2021.
[23] R. Jiang and X. Li. Hölderian error bounds and Kurdyka- inequality for the trust region subproblem. Mathematics of Operations Research, 47(4):3025-3050. 2022.
[24] R. Jiang, N. Abolfazli, A. Mokhtari, and E. Y. Hamedani. Generalized Frank-Wolfe algorithm for bilevel optimization. arXiv preprint S11iv:2206.088666 2022.
[25] R. Jiang, X. Shi, and J. Wang. A near-optimal algorithm for convex simple bilevel optimization under weak assumptions. arXiv preprint arXiv:2409.00 08948, 2024.
[26] H. D. Kaushik and F. Yousefian. A method with convergence rates for optimization problems with variational inequality constraints. SIAM Journal Optimization, 31())2111-2198, 2021.
[27] A. A. Khan, C. Tammer, and C. Zalinescu. Set-valued Optimization. Springer, 2016.
[28] P. Khanduri, I. Tsaknakis, Y. Zhang, S. Liu, and M. Hong. A doubly stochastically perturbed algorithm for linearly constrained bilevel optimization. arXiv preprint arXiv:2504.044 254455504.04555, 2025.
[29] V. R. Konda and N. Tsitsiklis. On actor-critic algorithms. SIAM journal on Control and Optimization, 42(4): 146-1166, 2003.
[30] G. Kornowski and O. Shamir. Oracle complexity in nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 34:324-33. 2021.
[31] J. Kwon, D. Kwon, S. Wright, and R. Nowak. On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. arXiv preprint arXiv:2309.01753. 2023.
[32] J. Kwon, D. Kwon, S. Wright, and R. D. Nowak. A fully first-order method for stochastic bilevel optimization. International Conference on Machine Learning, pages 18083-18113. PMLR, 2023.
11

---

[33] F.-Y. Liao, L. Ding, and Y. Zheng. Error bounds, PL condition. and quadratic growth for weakly convex functions, and linear convergences of proximal point methods. 6th Annual Learning for Dynamics & Control Conference, pages 993-1005. PMLR, 2024.
[34] T. Lin, Z. Zheng, and M. Jordan. Gradient-free methods for deterministic and stochastic nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, 35: 2022.
[35] B. Liu, M. Ye, S. Wright, P. Stone, and Q. Liu. Bome! Bilevel optimization made easy: A simple first-order approach. Advances in Neural Information Processing Systems, 35:17248-17266 2022.
[36] J. Liu, Y. Fan, Z. Chen, and Y. Zheng. Pessimistic bilevel optimization: A survey, International Journal of Compulational Intelligence Systems, 11(1):725-736, 2018.
[37] R. Liu, Y. Liu, W. Yao, S. Zeng, and J. Zhang. Averaged method of multipliers for bi-level optimization without lower-level strong convexity. In International Conference on Machine Learning, pages 21839-21866. PMLR, 2023.
[38] S. Lu. Slm: A smoothed first-order lagrangian method for structured constrained nonconvex optimization. Advances in Neural Information Processing Systems, 36:80414-8044 2023.
[39] Z. Lu and S. Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1377-1999) 2024.
[40] B. S. Mordukhovich. Second-order Variational Analysis in Optimization, Variational Stability, and Control: Theory, Algorithms, Applications. Springer Nature, 2024.
[41] Nazari, D. A. Tarzanagh, and G. Michailidis. Adaptive first-and zeroth-order methods for weakly convex stochastic optimization problems. arXiv preprint urXiv:2005.092611 2020.
[42] Y. Nesterov and B. T. Polyak. Cubic regularization of newton method and its global performance. Mathematical programming, 108(1 (08(1):177--) 170- 2006.
[43] S. M. Robinson. Linear convergence of apsilon-subgradee descent methods for class of convex functions. Mathematical Programming, 86:41 150, 1999.
[44] Y. Shehu, P. T. Vuong, and A. Zemkoho. An incrtial extrapolation method for convex simple bilevel optimization. Optimization Methods and Software, 36(1):1-19, 2021.
[45] H. Shen and T. Chen. On penalty-based bilevel gradient descent method. arXiv preprint 23Xiv:2302.05 1855, 2023.
[46] L. Tian and A. M.-C. So. On the hardness of computing near-approximate stationary points of clarke regular nonsmooth nonconvex problems and certain DC programs. In ICML Workshop on Beyond First- Orrst-Order Methods in ML Systems, 2021.
[47] L. Tian, K. Zhou, and A. M.-C. So. On the finite-time time complexity and practical computation of approximate stationarity concepts of Lipsehitz functions. In International Conference on Machine Learning, pages 21 21360-21379. PMLR, 2022.
[48] Tsaknakis, M. Hong, and S. Zhang. Minimax problems with coupled linear constraints: Computational complexity and duality. SIAM Journal on Optimization, (3(4):2675-2702 2023. doi: 10.1137721M1466422.
[49] J.-P. Vial. Strong and weak convexity of sets and functions. Mathematics of Operations Research, 8(2):231-255 1983.
[50] Wang, H. Chen, R. Jiang. X. Li. and Z. Li. Fast algorithms for stackelberg prediction game with least squares loss. In International Conference on Machine Learning, pages 10708-10716. PMLR, 2021.
[51] W. Wiesemann, A. Tsoukalas, P.-M. Kleniati, and Rustem. Pessimistic bilevel optimization. SIAM Journal on Optimization, 23(1):353-38, 2013.
12

---

[52] Q. Xiao, S. Lu, and T. Chen. An generalized alternating method for bilevel optimization under the
condition. Advances Neural Information Processing Systems, 36: 63847-63873, 2023.
[53] W. Yao and X. Yang. Relative Lipschitz-like property of parametric systems via projectional coderivatives. SIAM Journal on Optimization, 33(3):2021-200 2023.
[54] W. Yao, H. Yin, S. Zeng, and Zhang. Overcoming lower-level constraints in bilevel opti- mization: A novel approach with regularized gap functions. arXiv preprint arXiv:2406.01992, 2024.
[55] S. Zeng, T. T. Doan, and J. Romberg. A two-time-scale stochastic optimization framework with applications in control and reinforcement learning. SIAM Journal on Optimization, 34(1): 946-978 2024.
[56] I.. Zhao, D. Chen, D. Zhu, and X. Li. Randomized coordinate subgradient method for nonsmooth optimization, arXiv preprint arXiv:2206. /4981, 2022.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The developments established in Sec. 3, 4 support the claims made in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We used Example to show that our work does not apply to the lower-level constrained case. In Sec. 5, we gave some remarks that reflect the limitations of our work and call for future research.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
14

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provided the full set of assumptions for our theoretical results, as detailed in Sec. and 4. Complete proofs can be found in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper focuses on the theoretical computability of hyper-stationarity for BLO and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
15

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper focuses on the theoretical computability of hyper-stationarity for BLO and does include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips.cc//ppc//ee/// wwt.ce/pppppppcccceeeeeeeeoeeeee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper focuses on the theoretical computability of hyper-stationarity for BLO and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This paper focuses the theoretical computability of hyper-stationarity for BLO and does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper focuses the theoretical computability of hyper-stationarity for BLO and does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
17

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///wwwpppppppppp/////aaaaaa
Answer: [Yes]
Justification: The authors are sure that the research conducted the paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper considers the theoretical computability of BLO. We do not see any potential negative societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper focuses on the theoretical computability of hyper-stationarity for BLO and poses such risks.
18

---

Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper focuses the theoretical computability of hyper-stationarity for BLO and does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi twwoeechoo...... com/ comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper focuses on the theoretical computability hyper-stationarity for BLO and does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
19

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification: This paper focuses on the theoretical computability of hyper-stationarit for BLO and does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper focuses the theoretical computability of hyper-stationarity for BLO and does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMSs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper focuses on the theoretical computability of hyper-stationarity for BLO and does not involve LLMs any important, original, non-standard components.
20

---

Guidelines:
The answer NA means that the method development in this research does not involve LLMS as any important, original, or non-standard components.
Please refer to our LLM policy (https: /ttpss:///uurippp/ /c//oomfferenccs//22///1111 for what should or should not be described.
21

---

A Missing Proofs for Sec. 2
A.1 Proof of Lemma
Proof. Thanks to Assumption 1 (A3), we have
dist(y1. S(x2)) S rl V y1)ll,
for any y E (())). Moreover, we have
v vff(z2 y1)ll Vyff(z2. v1) V f (x1, I Ly][æ1 x2ll,
where the equality follows from (z y1) = 0, and the incquality is due to the -ysooohhsssss of f. Putting them together yields dist(y) S(x2)) S Lyt |æ xzll for all yı S(z1).
By the same argument with and æt interchanged, we have dist (322, S(x1)) - I. T.yr|ar 22 for all y/2 E S(x1). By the definition of dH (x2)). we conclude
dist(y) S(x))) sup (ys }
du (S(z)), max
sup M)ES(())
Ly [ x2/|-
This completes the proof.
A.2 Proof of Lemma
Proof. We prove the Mo-Lipschitz continuity for App only, as the argument for yo is entirely analo- gous.
Then, suffices to show that for any æ1, 22 E comm((p))
(pp((11) (x(()) I Mp æ2||-
Note that S(x) is closed but not necessarily compact. We can only find a sequence {vī JeEN S S(x1) such that F(x1, w/") + sup)Es(mi) F(z1, y) = (a1)) Let v² = (s))))(()) Then, by v E S(x2), we have ()(2)) sup suppe)((s) F( y) 2 F(22, vř). This observation, combined with the Mp-Lipschite continuity of F, yields
F v fp(22) < F(zI, vt) F(x,, v S MF (|æ - x2ll + llst vεll).
where the last inequality follows from Assumption 2 (B1). Moreover, we have
( = dist S(x2)) S dn(((a)), S Ms|la, - =22l;
where the last inequality is due to Lemma 1. Then, we can see that for all E N,
F(x1, vt) (x22)) $ Mr(1 + Ms) - -xgl- Letting -+ oo and recalling F(x1,y)) < (x)), we obtain
(p(x1) (p(())p))))))))))))))))))))))) s Mp(1 + Ms) æzll,
which completes the proof.
A.3 Proof of Fact 1
Proof. By [49, Proposition 4.4], the weakly convex function -g is locally Lipschitz (hence so is g). so the Clarke subdifferential 0g is well defined. Moreover, the Clarke subdifferential satisfies 0(-g) -- 0g [10, Prop. 2.3.1]. Applying Lemma 3 (iii) to -g then yields the claim. D
22

---

B Proof of Theorem 1
Proof. To establish the weak convexity of o, we verify the condition in Lemma 3 (i). Specifically, we show that there exists a constant p > 0 such that, for all 0 E [O, 1] and all æ 22 E D,
o(x") s ()(())) (1 - ())(2)) + 2 Lo - 0) æ - =x2l1²
(8)
where we let x vz + (1 22 for notation convenience.
By definition, <(x") maxy/ " 0(x", y¹). Hence (8) will follow if we show that, for all y V(x)),
g(Ø" y) 9 (())) (1 - 0) d(z2) S & 0(1 - 0) ||=| x221?
(9)
Taking the maximization over y E ()x") then yields (8).
We proceed via the Ly-smoothness of y. which guarantees the existence of y M(m) and y/2 E (2x) such that
|00 + (1 (1- 01-0)92 - yll 5 L 0(1 0)||01 x22l²
(10)
2
1/3 y211² S Ly ||:0] - x=211²
(11)
Then, using the fact that v(x:) = maxx'))(ar) ( 3/ g( y.) for 1, 2, we have
9 (x" v) (x((1) - (1 0))(22)
Sg (a y) 0g(x1121) - (1 - -0)g( 222 y/2
Lg 0(1 - 0) (120) -x212=2 2221² 2 11 y2 v²2l²),
Sg (x" y) 9 (a* Oy1 + (1 0)y2)
where the last inequality is due to the I, syssohootsssss of g on D x Conv(UsED (x)) and Fact 2. This, together with the M1,-Lisschitz continuity of g w.r.t. y and the set-smoothness inequalities (10) and (11), yields
9 (x .2) 0x( (1 ())((2)))
< M, |00y + (1 - 0)y² yll 0(1 0) (1le) =x2l1 |111 y22l²)
Lg 2
Mg 0(1 0)||=1 =221 +
Lg 0(1 - 0) (1m2 æ2l1 + L x2e1? 11?)
2
2
MgLy + Lg + Ly)
0(1 0)||m 22 1
2
for all y E )xx"). We prove the desired inequality (9) with = M,Ly + Lg + Ly).
C Proof of Theorem 2
We start by stating a lemma that will be used in the sequel.
Lemma 5. Under Assumption (AI), for any æ., 22 E RT and yı V2 E R", we have
(i) V (ff((1111)) - Vyf (x2, v22 - V (æ2, y2) (x1 22, 31 - -y2)
H, [|20 2:22 12 + | 12 112
(ii)
[V y ff y1) + (1 - 8) of (xz, 822) Vyf(2 y0)l
H, 0(1 0) (1mm - 2²11² + |1y/ 32ll²)
4 [0.
where x : 0x (1 0)3z and y 0yi (1 0)
23

---

Proof of Lemma 5. (i) The argument directly follows from [42, Lemma 1]: v (21, 91) /yf (#2, 92) VV y (x22 y2) (0) 22, y1 y2)
VV of (0) + ( x1) y1 & (y2 - y1)) (x) - 22, y1 - y2) dt
v (22 y/2) - 22. yl y2)ll
(VVyf (2) + +((az-z)) x1), y1 + t (z2 - y1)) - VV (z2, (21) 22. - Y22)
IIVVV, (3) (1) V! + (z22 vi)) VV v, (x2,, y2)) (2) -2,
22
y22) dt
||V (z) + (x² x1) y1 & (y2 y1)) VV vf (x2, y2) [
22. y1
y2)l dt
5 Hyt [(=) 22 y - yy2) |l [ - 22, y - -22) dt
H (Im] ==2l 11
y2ll
where the first inequality is due to Jensen's 's inequality; the second inequality is due to the Cauchy inequality; and the third inequality uses the Hy-Lipschitz continuity of VV yff.
(ii) Using the result of (i), we have
V n. (21, 91) Vul "a((""
. y²)
VV (20 .y) (x1 x.. y1 -0a-)
H || x z²11 + |1 y 2/(1²).
It follows from x. =xx (1 8) and yd fy + (1 f)yz that
V (2r, y1) - VyJ (m= v0) -1- v (a. v²) (x) y1 -92)l
H (1 0)2 (1 - 2ل2 21 + |1y/ - y2l'
(12)
2
Using the same arguments with (ær1, y1) replaced by (2'2, 8/2), we have
Vuf 822) V&f (x= 28") uVV of (x v²) (x2 x1. -311
H, 2
g2 (| x=11² | -
32ll²)
(13)
Then, the desired inequality follows from the weighted sum (x(++)+ - x13),, and the triangle inequality that
0VVV o. (x yy) (x) x2, 31 -y2)| + (1 8) V (22, v2) Vol (x 38) - AVV. (x" yy) (.02 I1, 3/2 yn)
V (f v1) v (2= v²) -1-0)1
> 0V ( +
0) v (x)2 y2) v, 30)||
We are now ready to prove Proposition 2. Fix 0 E [0, 1] and 1 32 E R" and let y S(Ox; + (1 )) Our goal is to construct E S(x1) and y/ E S(x2) such that (4) and (5) hold.
C.1 Step 1: Choose projection points as the candidate approximation points.
Let Ø1 = (3) and ÿ == Is (z). For simplicity, we write x" = Ax, + (1 A x and
y = 0ÿ + (1 0)g2. We start with giving basic estimates on 1 Tell and dist(y"
(( S(xx)) in
Claim
Claim 1. Let Lo = H1 + M2)/2. The following hold:
|1 T2ll < Ms| =22l
(14)
dist (v", (x²)) - Loo(1 0)]
(15)
24

---

with the Proof of Claim 1. We have
10 - 72 _ 111 - yl + 1l ÿ2
dist(y, S(x,)) )) + dist (i.
I du (S (z") S(())) + du (S (z") S((2))
- Ms [l] (0m: - 0))2)1 Ms mz (0x: + (1 0)w²))
= Ms|læi - æ2l1,
where the second inequality follows from y S(x") and the definition of the Hausdorff distance; the third inequality is due to Lemma 1 and x" fx1 + 0)22. This proves (14).
We then prove (15). First, by the -I-isshci continuity of VV yf and Lemma (ii), we have
| (z V1 + (1 - 0) ff (x 72) - V fff gg))
H1 0(1 - 0) (|02] - =22||² + | Ø2
(16)
2
$ H 0 - 0) (1 + M23 -221
where the second inequality is due to (14).
Since i1 E ((x)) and J2 S(22), we have the first-order optimality
(a (1) O,
V, 92) = O.
Substituting these identities into (16) yields
H 0(1 0) (1 +1+ M2) ||ا| =x21??
Vuf (x", - v 8²)ll S
2
Combining the error bound from Assumption 1, ((''""")))))) S T + (x r²)1,. preceding inequality, we obtain
dist ( (x0))) < HT 0(1 0) (1 + M2) ||| 2221
which accords with (15) with Lo = H1r(1 + M2)/2. Claim is proved.
Note that (15) controls only the distance from n² to the set S(x²); ); it does not guarantee that the specific point 0ÿ + (1 -0)z2 lies on the same branch as the metric projection "s( Hence one cannot conclude that [|@ğ: + (1 -1-60 f) - yl = ([ - x2 x2 in general. Therefore we cannot simply take y1 f1 and y/2 Ø2. which motivates the rectification in Step 2.
C.2 Step Translate the candidate approximation points
Let ÿ = Iss()) ÿ1 = 31 (y 8). and ÿ2 ÿ2 (y 8). We will bound the three quantities 1/ yll. dist(w1, S(x1)) )), and dist S(æ2))
Claim 2. Ler L1 = H,T (1 + 17M3) /2. The following hold:
| b/1 < 20(1 Ms ||=
x2l1
(17)
dist (ū.. S(x))))))) < L, (1-10) (|= 2211 dist (g2, S(x2)) S L -2212
(18)
Proof of Claim 2. We begin with the proof of (17). The non-expansiveness of the projection operator ss yields
l al ||T ss (v) S 1 y/ S 0 ll vll + 0) U02 all (19)
Moreover, by y: = II Is (y) for = 1,2, E S(x*), and the Ms Lipschitt continuity of S from Lemma 1, we have
| yl dist(y, S(x,)) _ du (S (z") S(x:) Ms || x x011. i= 1, (20)
25

---

Combining (19) and (20) leads to
1 yll - 0Ms x1 x=1|+((11111 +
Ms |0 x²1 = 20(1 8) || x2
We then continue prove (18). It suffices to upper bound || Vy (x 21 Il, due to Assumption (A3). By Lemma 5, we have (2) 91):
Hj ll 01ll?
V 01) (z 91) f 91 (0, 9ill -
Noticing y/ E S(x1), we have vyf(z) 01) 0, and thus
H 2
V (21, 01) - VV f y1 (0, 91 - -ni)l -
9 5 11
Using the triangle inequality and the identity D1 yı y
ÿ (by the definition of Ú1), we obtain
H1
vf 91)ll < VV v 91) (0. y - e) +
ly 0112.
(21)
2
We proceed to control VV v 9 (0, y U) To do so, we first estimate a closely related norm , (0, y U)ll We apply Lemma 5 again to obtain
H y
W (x" Ø) v (x" y) VV of (x", v) (0, Đ e)ll -
11
2
Note that both y and ý belong the set S(xx),, which leads to
VuJ (x. 0) vyf (x. v) 0.
follows that
VVV,f(e (x" u) (0. y أ))l s Hj B -91?
(22)
2
Putting everything together yields
/ 91
< [1 ( 91) - VV, v (a",)) (0,y 9) + |/ / (z (0. 9)
H1 1y - =
+ 2
H1
y 011 + H5 y 01
< VV,, y (2 31 VV of (x 3) [1 y r)1
2
<H H (1|201 - x01 + 01 yl1)
|y ~| + Hylly 01
Hy | - x1
H
$ 2
3/1 y
H 1/ ~||2 + H - 81
2
Hy
H 11 f + 2H 01
[2] 0
2
where the second inequality uses the definition of matrix's la norm and (22); the third inequality is due to the Hy-Lisschitz continuity of v and the triangle inequality; the forth inequality is due to the Cauchy inequality.
Combining the above estimate with | - x81| (1 - -0]||a - æell. (20) (with = 1), and the bound from (17), namely y اا
< 2(1 0). Ms| æ2ll. we obtain
Hy (1+ 17M3)
V v (x 0111
(1 - 0)7|(z] - x>2 1l.
(23)
2
Finally, armed with the error bound condition in Assumption (A3), we have
dist (#1, S(x1)) < Hyr (1 17M3)
(1 0)-0)²1[a; - 22212
2
By the symmetric arguments, we can also have dist (92, S(222) S HFT (1 + 17M3) 1ar-aaal -022| 1m
We finished our proof for Claim 2.
26

---

C.3
Step 3: Define approximation points
With the preparations in Steps 1-2, we now define the approximation points
y/1 IT (ū1),
== (..))
To establish the smoothness of S, it remains to show that there exists constant Ls > 0 such that
I.s 0(1 0) || - x2l1?;
10y: + 0) yl - 2
(24)
|ly: y2112 S Lssla - x211?
(25)
We first prove the inequality (24). We have
| + (1 - 8) - yll
110(11 ú1) + (1 (y ú2) (0ğ) + (1 f) f)ll
201 9ill + (1 0)l|y1 9ill [(0)] (1 - 0)0² y)ll
=0 distt 01. S(w)) )) + (1 0) dist(g2, S(æ2)) + |100 /
=0
(1 0) dist S(x2)) dist (y" S (x"))
where the second equality follows from y; [=.) (9.) and D; y: + y ÿ for i 1, 2; the final
one is due to ý = 11 s= (7").
This, together with (15) and (18), implies
|0y: (1 0)y2 yll S (Lo + Li)0(1 0)( =22/1²
Hence, (24) holds if Ls 2 2(L L1). It is left show (25).
To prove (25), we estimate the distance |// y/|l- ll To begin, we apply the triangle inequality to obtain
| 32ll S |/ F1 + 1 D2 + 1 y2ll-
Then, use the definition y: 1ls(m.)) (..) 1Is(m:) (y: + y 9) and notice y E S(x;) for 1, We have
1
y2l I |[(T( (51 (y 1)) s (o)))) )>1l
ll Tzll
+ [T(())) (Uz)) [[((2a) (?2 (g أ))l
(26)
< 1 3/l + || -2 + 11 yll
2 1 yl + |l - 5221.
where the second inequality follows from the non-expansiveness of the projectors (s()))) and (-)
Recall from (14) that y T2ll S Ms|lan æzll. and note that (17) further implies
1 yll < 20(1 - Ms |x] -xell S -Mslaa -x2ll ll
(27)
Combining (26) and (27) yields
| y2ll S 2Ms|| =x2l,
which proves (25) with Ls 2 4M3.
Finally, to ensure (24) suffices to choose
Ls 2 max 2(Lo + L1), 4M3 J. 41y "y M2 and L1 = (1 17M3), obtain
Recalling Ms LyT, Lo
2
Ls max 21 + 91.322) 4T33-2
This completes the proof of Theorem 2.
27

---

C.4 Proof of Remark 3
the proof of Theorem 2, Assumption is only used to guarantee Lemma and the estimations on the involved points. Notice that ensure Lemma 1, it suffices for Assumption to hold the set D x Conv Conv(U>ED S(x)) S D x V. We only need to check that the involved points belong to the set D x Y prove Remark 3.
As the domain of S is D, verify the set smoothness of S, we can choose æ 02 E D. Then, we have æ" E 'D due to the convexity of D, Hence, it suffices to check that y1. D2. y¹ V/, y/. D. 91. and d2 belong to the convex set y
First, recall that DI, E S(w1), Conv(Uner S(x)) due their definitions. We see that they belong the set V. We then focus on yn and y2. Recall that y: y: + (y 8) for = 1, 2. We see that for i 1,2,
(in)).y yy. y2 E S(x2), ÿ E S(æ"), and D E Conv (onv(S(a)) U(x2)) S
dist (i., (mx)) < 1;: y: 1/ ğll
By (27) and | - =22ll diam(D). for i = 1, 2, we further have
dist (qr, S(x))) S 2 Ms - diam(().
This implies that Ù, S(x,)) Ms (i) (O, 1) S y for i 1,2. We complete the proof.
D Proof of Theorem 4
We first introduce some background on zeroth-order methods before the formal proof. Let IP denote the uniform distribution on the unit sphere in R Given function g R - IR and radius > we define the randomized smooth approximation g by of (æ) Eu-r g( + su)]. We have the following properties for gf.
Lemma 6 (Basic Properties of Randomized Smoothing). The following hold:
(i Ifg g is Mi-Liccchttz continuous, then of is differentiable, MG-Lipschitz continuous, and salisfies
Ig(x)) - 9" (x)) S eMg-
(28)
(ii) Ifg is r-weakly convex (resp. concave), then of is r-weakly convex (resp. concave).
Proof. (i) See [34, Proposition 2.3].
(ii) If is w-eeklyy convex, then by the same arguments of Nazari et al. [41, Lemma 16], have the r rewk convexity gf. When is r-weakly concave, we note that - is r-weakly convex, and hence (-g)= is r-weakly convex. Due the simple fact (-g)- =f, we have the r-weak convexity of gf, i.e., the r-weak concavity of g"
As the approximation for a subdifferental 0g via randomized smoothing can be inexact, we need the following e-subdifferential.
Definition 4. Consider a convex function 9 Rmm R and scalar 0. We define the y-subdifferential of g at x E R by
0zg(x) = {s E R" g(x) 2 g(x) +
x) - v, V R"].
We then develop the convergence rates of IZOM for optimistic and pessimistic BLO, respectively. We remark that our analysis remains valid when the hyper-objective functions yo (resp. vp) are replaced with general M-Lipschitz continuous, p- p-weakly concave (resp. convex) functions.
D.1 Optimistic Case
To begin, we record celebrated proposition on subdifferential transportation.
Proposition 1. (cf. [2, Theorem 5.5] and [43, Theorem 2]) Let R + R be a proper lower semicontinuous convex function. Suppose that 2 0 and E 0zg(z). Then, for each r > 0, there a unique vector u E Rd such that
G -. 0g(( rv), || $ Vv.
28

---

Proposition 1 plays an important role in relating an e-subdifferential to the Clarke subdifferential at near point, leading the following lemma.
Lemma 7. Let IR - TR. be an M--lipschitz continuous and p-weakly concave funcctinn. Let of be the randomized upproximation of g with radius and 22 Then, for all R we have
dist (o. (0))))))))))((z)) - | (x)] + 10+1)vD.
0g(z))
(29)
Proof of Lemma 7. By Lemma 6 (ii), of is p-weakly concave, i.e., the function æ + 2112012 2- of (x) convex. Then, we know that for all 2, IR".
_ of (z) 2 2 ||==| - od (x) + (px - Vof(z))) (z 15-))) x).
This, together with Lemma 6 (i), implies
L |1 - g(z) 2 | g(x) + (px V (x))) (z x)) 2
which is equivalent to
pa - V E 0. (2 |0012 g(a:)
with
== M
For simplicity, we define ğ x + -||==1 - g(x)). Clearly, g is convex due to the p-weak concavity of g. Applying Proposition 1, we see that there exists v I with
|| S v/v such that
p Vg - e E Ög(2 + D)
(30)
Recall that - is p-weakly convex, and thus is regular according to [49, Proposition 4.5). Then, we have 0g(z) = pz + (z) for all RM by [10, Corollary of Proposition 2.3.3]. On the other hand, we have (()g) = 0g by [10, Proposition 2.3.1] ]] and Lipschitz continuity of g. Hence, we see that
0ğ(z) pz 0g(z),
V
In particular, we have
0ğ(x+ v) = p(= + v) - 0g(x + v).
This, together with (30), implies
Vg((x) + (p+ 1)0 E 0g(x + v).
follows that
dist 0z + v)) < V
+ (
[ + (p + 1)]|=//-
Observe that || S vv and
dist (0, 0g(2 + v)) 2 dist (0.UeeR(m](o))0(((3))) 2 dist (0(0ee(aww00g(z)))
We obtain the desired inequality
dist 0g(x)) <
Now, we are ready to prove the convergence rate for IZOM. To begin, we define the subdifferential approximation function G by
G(æ.) 2 (poo tuu) po(x, su.))
By [34, Lemma D.1], it holds that
E [[G(())) [x,] V B[I xx] s 16v 2mmm3
(31)
Since (p(x;) - Po (a:)) S w by the subroutine A, we have [[((a)) - G(x:))l S mm. This, together with the simple fact [|=(2=) < 21[ā(x.)) - -Gxz))) (zx) implies
due to the Cauchy inequality,
mw 2
B [|[(((=))|11)) [x,] 32
(mW
(32)
E
29

---

Next, we combine the update of IZOM and p-weak concavity of 4o to develop a sufficient decrease property for the 1-th iteration. Using Fact and the update 1 3t = (x)((a)))) of Algorithm 1, we obtain the following estimate:
(2(+1))
(x) (0)())) x1)+ + P -1 x2ll
(a)) (a.)
( ((x.)) 6 _)(1(((0))1*
(m)) v/ (m.) ((m)) - n [ (((=:))((x))
+ o (
(x,) (a.) ( G( / ( )1? + ? G(ax)) - -G + +
where the last inequality is due the Cauchy inequality.
We take expectation conditioning on æ, for the above inequality. Recall that E[G( = (2.)
by (31). We see that
(xxe) [
Bl]]((a)) G(
mr [lI [..].
2
Apply Lemma yo and use the Cauchy inequality. We obtain
dist (()))))( s 2
+ 1)aE.
Combining the above two inequalities with (32), have
B( [xc]] S (xx))) - dist (0.User(e.w))00Al
?
+ 2 (p 1)2e
4
+
mw
2
+ 11²
32 2 +2
mw 2
Recall that 20 0 vmll
) 0 ( ) and w 0 m
+ Ignoring some scalars,
further have
1 dist (o. (0:Ure((a..30000013 + 7
Bl S (
(33)
Summing (33) over t =0, 0,1,...7 T 1 and taking full expectation, obtain
(x))(( S ()(()))) 7
dist (0, 0lo0))) + +0(1)
E
Note that the definition of yields
dist (0. (o.U
Opo(z))
= Σ dist (0. 21
On the other hand, by Lemma (i) and -g-Lipschitz continuity of fo. (x0)) El(g( < Ms + po(wn) min (a)()) A..
Putting all the things together, we have
E dist (o.Usen(ewo)Opott13 opo()))
-0 A. +1 - n/T 0
(Vm(A, + 1
VT
where Vv /2EMo O(T-1).
30

---

D.2 Pessimistic Case
In this section, we let G(æ,) = z -p and use to denote pr, (x) for simplicity. Similar the arguments on (31), (32), we have the following due to [34, Lemma D.1]
and (5(x),) pp(2))) I given by Algorithm 1:
E E Ø
BlIG(z))) 16V2TmM²
(34)
B[|[G - G(
10000
(IIG(()))))) S 32 32
(35)
Invoking the methodology of Davis and Drusvyatskiy [12]. we first estimate || æx+1 Il for
t 0, .,,... T 1. To begin, the update of Algorithm and direct computation give the following
estimate:
[ 11+1/1
[ It rx;i)
=| 21112 + +
-x;)
=I - xx11² + | || + 2n)) ((; -x:) + 2n -
(#: xzo)
< L. x, + ( )| + (x,) " - xx;) + n G(æ,)) - G( )1 + n/|bt xz 11.
(36)
Taking expectation in (36) and using (34), (35), we obtain the following inequality:
El| xe+ [2..]
S(1 + n)) - xz 2 + V (m;) (d. - m4) + R[](((()))) G(ar)))
+ n B[I|@(xx;) |xc]]]
<(1 + () - 12112 + 2n) V (mx) - xe) + mww 2 + 32v 3333322 2 + 2
mmw 2 172
(37)
We then turn to estimate pp, (I1+1). By the definition of Pp.y, we have
(nn(a11) S (xx() + _ -1 111
1
27
This, together with (37), implies
Elpp (xx-1)) [x,]] - (t,)))
+ 7 2 x,11² + 7 v (x;)) ) ((= (x)) + 17 mww
+ 16v 2mm 2Tm 7 +
mw n2
27
2
?
Recall that of, is p-weakly convex by Theorem 3 and Lemma 6 (ii). Then, using Lemma (iii), we have
Vef(ax)) ((@; xx) S (..) (z(x)) + P ( xx112
S ( - (xx))))) + P || xx M:
where the second inequality is due to Lemma 6 (i). Combining the above two estimates gives
B Blypp, (x++ [aae]]
S (dx)) + 27
| xx212 + 1 ? (pp(tt)) - -pp((x))
+ p++1
| - xx mx.13)
+ 2n MM
2
17
maw
+ 16 2 ??
+ mWW r?2
+
27
?
= -Pp (Ix) + 11
(p:)(xt) - (xx))
+
(p + 1)7
|| b; - 12
+ 211 MM
2n
17
mww
+ 1111662mmmm 2.Tmm 2 + mw n
+ 27
31

---

where the equation uses Pp.> (21) (p((tt)
+ 27 1| xzl?² Recall that by Lemma 4, it holds that
Dt L. VVV.,, and
(2)) (Pp(xx)
1 1
7P
1 xr112
1 1- 70 + 1) | - xeel
24
27
We further have
21 & &M
B( ) S (p,s(22)) - -1 (1 - - + 1)) (ppn((2))11
7
mw
+ 16v 2TTM2 " + me8 2 2
+
2
8
?
Recall that 17 = 0 VmT
6 = (
/T
1
w
0
m m ) and 7 E (0, 1/ + 1)). Neglecting some
scalars, follows that
Elppp æ2l S (2;))(1))))))))))))))))) - n7 (1 (1->(p 1)) Vv,, (x,)1 (
(38)
T
Summing (38) over & = 0,, 1.1....T - and taking full expectation, we have
El (x0) (1 xp + 1))
E V Sp. (z. (2x))
Note that the definition of æ gives EtE T-1 V/ (x:))1 = TE V pp.. pp. (z) Also, notice that
Pp. (2)) (1pp(((0)) S (2))(20)) - min pp.y (x)) = A
Putting all the things together, we obtain
Ap +1 1/T
(Vmi(A, + +1)
= =0
VT
This completes the proof.
32


Reviews:
[{"review_id": "kfZNlXrk9B", "reviewer": "Reviewer_fL5D", "summary": "This paper investigates unconstrained bilevel optimization problems in which the lower-level problem admits multiple solutions. The central contribution is the introduction of a novel set-smoothness condition on the lower-level solution mapping. The authors show that under this condition, the associated hyper-objectives -- whether defined optimistically or pessimistically -- exhibit weak concavity (or weak convexity in the pessimistic case). This structural property enables the use of subgradient-based methods to find approximate Clarke stationary points efficiently. To this end, the authors develop a zeroth-order algorithm tailored for the bilevel setting.", "questions": "- Has Definition 2 (set-smoothness) appeared in prior literature, perhaps in the context of set-valued analysis or variational analysis? Understanding any precedent could help position the contribution more broadly.\n\n- Could the proposed method or analysis be extended to stochastic Bilevel settings?", "limitations": "This is a well-written and insightful paper that introduces a novel structural condition with meaningful implications for Bilevel optimization. While the algorithmic contributions are incremental, the conceptual clarity and technical rigor make it a valuable addition to the literature. I recommend acceptance.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\nTo the best of my knowledge, this is the first paper where the notion of set-smoothness has been introduced in the context of Bilevel optimization. The authors effectively leverage this idea to unify and strengthen several threads in nonsmooth optimization -- namely, Clarke stationarity, weak convexity, and zeroth-order methods -- to tackle a longstanding challenge in bilevel problems with multiple lower-level solutions. The presentation is concise and the logical development of the core ideas is clear and well-structured.\n\n\n**Weaknesses**\n\nThe main conceptual contribution is compelling, but the following must be clarified:\n\n- The core contribution of this submission lies in the introduction of the set-smoothness property, and I believe it might have significant future potential to advance understanding in multiple-solution settings — an area where progress has been notably limited. That said, to fully realize this potential, the submission should more clearly position the proposed condition within the broader context and articulate its implications in greater depth. In particular, it would be essential to discuss the algorithmic implication of results in Section 3 in greater details. \n\n\nAlso, the algorithmic developments could be more thoroughly distinguished and emphasized:\n\n- While the paper builds toward Clarke stationarity, the motivation for preferring Clarke subgradients over alternatives such as the Goldstein subdifferential could be more fully justified. Is this choice driven purely by analytical tractability, or does it yield practical benefits (e.g., stronger convergence guarantees, better empirical performance)?\n\n- The distinction between the proposed Algorithm 1 and the approach in [7] could be made more transparent. A line-by-line comparison or at least a clear summary of the differences would be helpful. If empirical performance comparisons are available, they would strengthen the case.\n\n- A discussion of how general the set-smoothness condition is would be valuable. For example, how does it relate to more common regularity conditions like error bounds or the Polyak-Łojasiewicz condition at the lower level? Are there natural examples where set-smoothness holds but other assumptions fail?", "was_revised": true, "final_justification": "I believe the potential of their conceptual contributions.", "rebuttal": "We sincerely thank reviewer fL5D for the valuable feedback and appreciation of our contributions! We address the concerns raised as follows.\n\n**The relation of set smoothness to other regularity conditions**\n\n(a) While one of our main contributions is to introduce the concept of set smoothness, we highlight that relating it to the lower-level PL condition is a second key contribution; see Proposition 2. Proposition 2 shows that set smoothness holds for a group of nonconvex-PL BLO problems that are widely studied in the literature. It provides valuable insight into the generality and practical relevance of the set-smoothness condition. \n\n(b) Great suggestion regarding natural examples where set smoothness holds while other assumptions fail. Here is a simple illustrative case: Consider the lower-level function $g(x,y)=h(\\sin(x)+y)$ for a function $h:R\\to R$ with a nonempty set of minimizers $V=\\arg\\min_z h(z)$. Then, the solution set function $S(x)=\\arg\\min_{y}h(x,y)$ satisfies $S(x)=V-\\sin(x)$. In this example, $S$ satisfies set smoothness yet no additional regularity assumptions are required on $h$ or $g$. This illustrates that when $g$ has a separate structure in $x$ and $y$, set smoothness may arise naturally. We will incorporate this discussion in the future version of our manuscript in response to your suggestion.\n\n**Preference on Clarke stationarity**\n\nAs noted in lines 150-153 of Sec. 2, Goldstein stationarity is a relatively weak condition, whereas Clarke stationarity is significantly stronger. For example, \nthere exists a differentiable function $f$ such that a point $x$ with $\\|\\|\\nabla f(x)\\|\\|\\geq1$ still satisfying Goldstein stationarity [31, Proposition 1]. In contrast, Clarke stationarity excludes such points, offering a more meaningful notion of stationarity.\nConsequently, employing Clarke stationarity would lead to much stronger theoretical convergence guarantees for algorithms. Following your suggestion, and given more space in the main body, we will provide a more detailed justification for our preference for Clarke stationarity in a future version of our manuscript.\n\n**Position of set smoothness in broader context**\n\nWe agree that discussing the implications of results in Sec. 3 would be highly insightful. As we mentioned in Sec. 5, our results may have potential implication in coupled minmax optimization. Indeed, our Proposition 1 may directly apply to the inner problem of coupled minmax problem (see reference [46]) under set smoothness condition, offering structural insights into such problems. \nFor algorithmic implication, the established weak convexity/concavity suggests that the problems fall within the broad class of weakly convex/concave optimization. This connection opens the door to utilizing established methods from that literature, such as subgradient methods, proximal point methods, and zero-order methods. \nWe will incorporate these discussion on the implication of our results in the future version of our manuscript.\n\n**Clarification on Algorithm 1 in Sec. 4**\n\nWe note that the main contribution of Sec. 4 is establishing the computability of Clarke hyper-stationarity for the concerned BLO, as we stated in lines 293-294 of Sec. 4. To achieve this goal, we do not necessarily need to design a new special algorithm. Instead, we utilize the established structural property in Sec 3 and extend a standard algorithm, i.e., the zero-order method, also used in [7], to both optimistic and pessmistic BLO. While previous works only show that it computes Goldstein stationarity, our analysis provides a stronger convergence guarantee to approximate Clarke stationary points. This is enabled by the weak convexity/concavity we established, as noted in lines 313-315. These results enhance the understanding of the computability of BLO and we leave designation of new efficient algorithms for computing Clarke stationarity for future work, as stated in lines 329-331.\n\n|*Has Definition 2 (set-smoothness) appeared in prior literature, perhaps in the context of set-valued analysis or variational analysis?*\n\nIndeed, we carefully reviewed related concepts for set-valued mappings in the literature on set-valued analysis and variational analysis, including but not limited to the classical reference [28] and a recent book [38]. To the best of our knowledge, the specific concept of set smoothness as defined in Definition 2 has not appeared in prior work. In Footnote 2, we provide a comparison between our proposed notion and existing concepts for set-valued functions. Given more space in the main body, we plan to present this comparison more explicitly in a future version of the paper.\n\n|*Could the proposed method or analysis be extended to stochastic bilevel settings?*\n\nCertainly. We believe it is quite natural to extend our methodology to stochastic/decentralized settings, which are practical for real applications. As the lower-level PL condition has also been adopted in such settings, we expect that similar properties and strong convergence results can be obtained.\n\nIf you have any additional concerns regarding our manuscript, we would be happy to provide further clarifications. Finally, we thank the reviewer for pointing out the format issue. We used the provided neurips_2025.sty file in our tex file without modifying the margins or font size. We will address any remaining minor discrepancies in a future version of our manuscript."}, {"review_id": "u3F9zK4E6V", "reviewer": "Reviewer_orA8", "summary": "The paper considers bilevel optimization problems in the non-convex/PL setting where the lower-level solution set is not necessarily a singleton. The authors introduce the notion of set smoothness and show that the solution set of the inner function in the considered setting is smooth. Then, they show that this smoothness implies the weak convexity (resp. the weak concavity) of the pessimistic (resp. optimistic) hyper-objective. With this regularity, they show that Clark stationarity can be obtained with a zeroth-order algorithm.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "### Strengths\n\n- **S1**: The paper is very well-written.\n\n- **S2**: The paper introduce the concept of set smoothness which offers new perspectives in analyzing bilevel optimization when the inner function is not strongly convex.\n\n- **S3**: The authors establish regularity properties of the hyper-objective based on the introduced set smoothness.\n\n- **S4**: The authors prove computability of Clark stationarity for non-smooth hyperobjectives.\n\n\n### Weaknesses\n\n- **W1**: The assumption on the convexity of $\\mathcal{S}(x)$ is strong for a non-convex inner function.\n\n\n\n#### Minor/Typo\n- For clarity, it would be useful to recall the definition of Goldstein stationarity\n- **Line 186**: \"Lemma 2 (ii) and (iv)\" -> \"Lemma 3 (ii) and (iv)\"\n- **Line 496**: \"$\\varphi(x_2)$\" -> \"$\\varphi_p(x_2)$\"", "was_revised": true, "final_justification": "The paper introduces the new concept of set smoothness, which opens the way for new analyses of bilevel optimization problems when the inner function is non-convex. For the novelty and the potential significance of this paper, I recommend acceptance.", "rebuttal": "We sincerely thank reviewer orA8 for recognizing our contributions and providing insightful comments. Below, we address the concerns raised.\n\n**On the convexity assumption on $S(x)$**\n\nThanks for pointing out this. We believe that this assumption is natural in BLO setting because defining the hyper-objective function involves minimizing the upper-level function over $S(x)$. If $S(x)$ were nonconvex, even evaluating the hyper-objective value generally become NP-hard. Furthermore, this assumption is weaker than the convexity of the lower-level function adopted in the literature (see e.g., [7, Assumption E.1], [42, Assumption 3.4], and [16, Chapter 9.1]). \n\nNevertheless, one can still weaken this convexity assumption. In our analysis, this convexity condition is primarily used to ensure the non-expansive property of the projection operator $\\Pi_{S(x)}$ in lines 580 and 620. Thus, it be replaced by a weaker condition, such as a non-expansive-type property of the projection, without affecting our main results in Sec. 3.\n\n**On the minor issues and typo**\n\nWe appreciate the reviewer's careful reading and pointing out the two typos. We will correct them accordingly. Also, given more space for the main body, we will include a brief recall of the definition of Goldstein stationarity for clarity in a future version of the manuscript."}, {"review_id": "gtk7vUzXXl", "reviewer": "Reviewer_PTCZ", "summary": "This paper proves that strong Clarke hyper-stationary points are computable for nonconvex-PL bilevel problems. The main results build on the following three arguments: \n1. The solution set of a smooth PL function satisfies the set smoothness introduced in this paper (Proposition 2). \n2. The hyper-objective is weakly convex/concave when the lower-level solution set is smooth (Proposition 1).\n3. A zeroth-order method can find strong Clarke stationary points for a weakly convex/concave objective (Section 4).\n\nAll the above arguments are novel. I especially appreciate Proposition 1 and Proposition 2, which are highly non-trivial and I think they definitely contribute a deeper understanding of bilevel optimization and other fields of optimization theory.", "questions": "I do not have additional questions.", "limitations": "One limitation is the dimension dependency in the upper bound, which comes from the use of the zeroth-order method. I can understand that the dimension dependency is hard to remove, but it is still a limitation compared to the existing dimension-free upper bounds (although they may require additional assumptions).", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The strengths of this paper are clear:\n1. The paper is well written.\n2. Proposition 1 and Proposition 2 are very novel and both solve important theoretical problems.\n\nI do not notice significant weaknesses; the only one I find is contained in the limitation part.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank reviewer PTCZ for appreciating our contributions to bilevel optimization and providing valuable feedback. We also hope that Proposition 1 and Proposition 2 will find their applications in other optimization fields. Below, we address the concern raised.\n\n**On the dimension dependency in the upper bound**\n\nThank you for the insightful observation and valuable comments. In Sec. 4, our primary goal is to establish the computability of Clarke stationarity, rather than to optimize the dimension dependence in the upper bound. That said, we agree that improving the dimension dependence is a compelling direction for future work. As you suggested, it may be possible to obtain a dimension-free upper bound under additional structural assumptions, which we believe is worth exploring further."}, {"review_id": "IOh3ajTsjG", "reviewer": "Reviewer_FxiL", "summary": "This paper studies bilevel optimization. The authors introduce a novel notion of set smoothness to characterize the solution set and hyper objective. Using this set smoothness, the authors prove that under a PL-like assumption, the hyper objective is weak convex(concave), enabling the computing of a Clarke hyper stationary point. The authors propose a zero-th order algorithm to compute it non-asymptotically.", "questions": "Do you think the zero-th order algorithm have implications for first order algorithms, which is more practical? What is the major gap between them?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The main strength of this paper is the theoretical contribution. The establishment of weak convexity (concavity) and computability of Clarke hyper stationary under PL-like condition is a novel and worthwhile contribution. The introduction of the set smoothness has technical novelty and implications for future work. \n\nThe weakness of the paper lies in its proposed algorithm. It is a zero-th algorithm and may not be practically efficient. The authors also do not provide empirical results.", "was_revised": true, "final_justification": "I will keep my score.", "rebuttal": "We express our sincere gratitude to reviewer FxiL for recognizing our contributions and insightful comments. Below, we address the concerns raised.\n\n**On the practical efficiency of the zero-order method**\n\nIn the algorithmic part of our work, the primary goal is establishing the theoretical computability of Clarke hyper-stationarity for the concerned BLO. To this end, it suffices to adopt a standard algorithm, i.e., a zero-order method, and utilize the developed structural properties. We view this computability result as a foundational step toward designing more efficient algorithms for computing Clarke hyper-stationary points. We did not provide empirical results in the current version because, to the best of our knowledge, no benchmark algorithms yet exist for computing Clarke hyper-stationary points. Given more space in the main body, we may include emprical experiments in a future version of our manuscript.\n\n|*Do you think the zero-th order algorithm have implications for first order algorithms, which is more practical? What is the major gap between them?*\n\nCertainly. We believe that the convergence guarantees established for the zero-order algorithm offer meaningful implications for first-order methods. In particular, one may expect stronger results—such as better dependence on the parameters and dimension—when using first-order algorithms.\n\nDespite the potential efficiency of first-order methods, the evaluation of the hyper-subgradient might be a challenge to implement them, as this involves computing the subgradient of parametric function $\\min_{y\\in S(x)} F(x,y)$ or $\\max_{y\\in S(x)} F(x,y)$. This is highly nontrivial especially when $S(x)$ has multiple elements. In comparison,zero-order methods only require evaluations of the hyper-objective value, which are readily approximated using simple bilevel algorithms, as we discussed in lines 297-298 and Footnote 3. \n\nThat said, exploring first-order methods for computing Clarke hyper-stationarity in BLO with multiple lower-level solutions is a promising direction. In particular, once an efficient oracle for computing the hyper-subgradient was developed, it may lead to stronger convergence guarantees and practically effective algorithms for computing Clarke hyper-stationarity.\n\nWe thank the reviewer for pointing out the format issue. We used the provided neurips_2025.sty file in our tex file without modifying the margins or font size. We will address any remaining minor discrepancies in a future version of our manuscript."}]

Author rebuttal:

Meta-review: This paper studies bilevel optimization problems in which the lower level problem does not necessarily admit a unique solution. To circumvent this obstacle, they introduce a notion of set-smoothness for the set of solutions to the lower level problem, which can be used to ensure that the composite function being optimized in the bilevel problem is weakly convex/weakly concave, even if the lower level problem is not convex. With this notion of set-smoothness, they are able to derive zeroth-order algorithms for solving the bilevel optimization problem when the set-smoothness condition holds. They are eventually able to prove convergence to a Clarke stationary point for the bilevel optimization problem with their new assumption.

The paper was well-received by the reviewers, who noted it was well-written, rigorous, and original. The paper could be improved by better explaining the relationship between the set smoothness condition proposed and those that already existed in the literature (e.g., the Aubin property, which is mentioned in the paper but largely skipped over). During the rebuttal period, all reviewers agreed that the paper should be accepted and that any concerns they had had were addressed by the authors. 

In the post-rebuttal discussion, I asked reviewers if they felt the paper did a good enough job positioning itself with respect to prior work, specifically referring to the Aubin property as an example. All reviewers found no problem with the submission in this regard so I wholeheartedly recommend acceptance.
Decision: Accept (spotlight)