Reducing Contextual Stochastic Bilevel Optimization via Structured Function Approximation
Authors: Maxime Bouscary
Jiawei Zhang
Saurabh Amin
Venue: ICLR 2026 Poster (2026)
Keywords: stochastic optimization
bilevel optimization
contextual stochastic optimization
parametrization
Primary area: optimization
TL;DR: By parametrizing the context‐specific lower‐level solutions, CSBO can be reduced to a standard SBO problem and solved with near-optimal sample complexity.

Abstract: Contextual Stochastic Bilevel Optimization (CSBO) extends standard stochastic bilevel optimization (SBO) by incorporating context-dependent lower-level problems. CSBO problems are generally intractable since existing methods require solving a distinct lower-level problem for each sampled context, resulting in prohibitive sample and computational complexity, in addition to relying on impractical conditional sampling oracles. We propose a reduction framework that approximates the lower-level solutions using expressive basis functions, thereby decoupling the lower-level dependence on context and transforming CSBO into a standard SBO problem solvable using only joint samples from the context and noise distribution. First, we show that this reduction preserves hypergradient accuracy and yields an $\epsilon$-stationary solution to CSBO. Then, we relate the sample complexity of the reduced problem to simple metrics of the basis. This establishes sufficient criteria for a basis to yield $\epsilon$-stationary solutions with a near-optimal complexity of $\widetilde{\mathcal{O}}(\epsilon^{-3})$, matching the best-known rate for standard SBO up to logarithmic factors. Moreover, we show that Chebyshev polynomials provide a concrete and efficient choice of basis that satisfies these criteria for a broad class of problems. Empirical results on inverse and hyperparameter optimization demonstrate that our approach outperforms CSBO baselines in convergence, sample efficiency, and memory usage.

Published as a conference paper at ICLR 2026
REDUCING CONTEXTUAL STOCHASTIC BILEVEL OPTIMIZATION VIA STRUCTURED FUNCTION
APPROXIMATION
Maxime Bouscary
Jiawei Zhang
Operations Research Center Massachusetts Institute Technology mbscryêmi terrrtmmitteee edu
Department of Computer Sciences
University of Wisconsin-Madison
j jzhang2924 22292244wwt @wii sc edu
Saurabh Amin
Laboratory for Information & Decision Systems Massachusetts Institute of Technology amins @mit @mit.mmti edu
ABSTRACT
Contextual Stochastic Bilevel Optimization (CSBO) extends standard stochastic bilevel optimization (SBO) by incorporating context-dependent lower-level prob- lems. CSBO problems are generally intractable since existing methods require solving a distinct lower-level problem for each sampled context, resulting in pro- hibitive sample and computational complexity, in addition to relying impractical conditional sampling oracles. We propose a reduction framework that approximates the lower-level solutions using expressive basis functions, thereby decoupling the lower-level dependence on context and transforming CSBO into a standard SBO problem solvable using only joint samples from the context and noise distribution. First, we show that this reduction preserves hypergradient accuracy and yields an e- stationary solution CSBO. Then, we relate the sample complexity of the reduced problem to simple metrics of the basis. This establishes sufficient criteria for a basis to yield e-stationary solutions with near-optimal complexity of Ö(E-s), matching the best-known rate for standard SBO up to logarithmic factors. Moreover, we show that Chebyshev polynomials provide concrete and efficient choice of basis that satisfies these criteria for a broad class of problems. Empirical results on in- verse and hyperparameter optimization demonstrate that our approach outperforms CSBO baselines in convergence, sample efficiency, and memory usage
INTRODUCTION
Many real-wort world optimization tasks involve solving bilevel problem where the lower-level solution depends on the upper-level uncertainty. Such tasks can be framed as Contextual Stochastic Bilevel Optimization (CSBO) problems:
min wERda
F(x) A B(g,n) [fx, v v (x, ())
(CSBO)
y" (x, arg min E [g(2, v. v. m)). veRdy
Vo E ERR
where P(e.n) denotes the joint distribution of Rd and Rd,, and Pyle denotes the conditional distribution of given &. Here, C TRds is the support of the random variable Ç. The dimension of the upper and lower-level variables and are d, and dy, respectively. The function far y, &, can be nonconvex in x, but g(r, y. g, and n, ensuring that the lower-level solution y (z. {) is uniquely defined. Our goal is to develop
E, 17) must be strongly convex with respect to y for any given x,
'The code is publicly available http://////ggggtoooo/o/ee/reeeee

---

Published as a conference paper at ICLR 2026
reduction framework that enables the use of existing stochastic bilevel optimization algorithms to compute an e-stationary point x", i.e. a point satisfying F (1*)) I é² where the expectation is taken over the randomness of the algorithm producing x=.
Stochastic Bilevel Optimization (SBO) is a special case of CSBO where the lower level is independent of Ç. in which case the solution to the lower level 1² depends only on In this setting, methods like
stocBiO (Ji et al. 2021) and STABLE (Chen et al. 2022) achieve sample complexity in O(e
estimators, sample complexities improve to ((--3) (Guo et al. 2021 Khanduri et al. 2021 Yang et al. 2023) or even (c)-)) CCh
With the use of variance reduction techniques or momentum-basee
et al. 2024). These results match the lower bound for single-level stochastic optimization (Fang
et al. 2018 Cutkosky & Orabona 2019 Arrevani et al. 2022), suggesting that SBO can be solved
efficiently in theory. This raises a natural question: can we achieve similarly efficient solutions in the
more general CSBO setting?
naive adaptation of SBO algorithms to CSBO computes e-stationary solutions by solving θ (E ?) lower-level problems at each iterate Te, each corresponding to different E, to estimate the hyper- gradient V (x:).. Specifically, using this naive approach to solve CSBO problems, the sample complexity increases from Ō(e to Ö(e D6.- and from Ö(E 3) to Ö(E with variance reduction methods. Using multilevel Monte Carlo methods, Hu et al. (2023b) reduces the sample complexity to (e However, the practical efficiency of their algorithm relies on the existence and knowledge of a reference point (o that is close to yo (x, {) for all e. which may not hold in practice. Alternativeyy, one can approximate (CSBO) by partitioning the context space E into N sub-regions and form SBO problem with N subproblems. While this approximation becomes more accurate as N increases, it introduces redundant computation across adjacent regions, resulting in slow convergence. In the specific case where E is discrete and of finite cardinality m. Guo et al. (2021) achieves a sample complexity in O(me -3) ) As such, their approach is not amenable to settings where & is continuous. In addition, all of the above algorithms require a sampling oracle from the conditional distribution T/ for any fixed ç. which can be impractical. For example, in inverse optimization or federated learning, although the joint distribution is often easily observable, the offline nature of the data or privacy constraints can prohibit conditional sampling. Our framework circumvents this limitation by needing only i.i.d. samples from the joint distribution, making it broadly applicable to realistic CSBO problems. This issue does not arise in standard SBO, where the lower-level distribution does not depend on g.
Despite recent progress, significant gap remains between the complexity and practicality of SBO and CSBO methods. Specifically, methods for solving CSBO suffer from the following drawbacks:
1. Sample inefficiency: existing CSBO algorithms incur at least a ( factor relative to the optimal O(c a) rate for SBO.
2. Oracle dependence: tional distributions P., & for all fixed E.
reliance on an often- unveaallveee oracle for sampling from the condi-
We show that, under mild conditions on and Pg. is in fact possible to achieve a Ō(c-3) complexity for CSBO matching that of SBO up to logarithmic factors using only samples from the joint distribution P(s..n)-
The main challenge in solving (CSO lies in the coupling between x and & through the lower level solutions {). To address it, we propose to decouple this dependency via a structured parameterization. Specifically, we parameterize y² (x, {) as Yςioi (W (x), E) - W (x)) where ((x) E Rd N is a context-indeee -ineeeediidee coefficient matrix, and N E + R- is vector of basis functions that captures the nonlinear dependence on ç. We then consider the following SBO problem:
min zER42
FRINT (x) A B(g.)) [ (I, W (x)), m)]
(SBO
S.L.
W (x) = arg min E ((E.)))P(em Ia W, n)], Vx E Rd WER
where faIM (x., W.E.n) A f(I. Importantly, the lower-level solution is function of x only, and the linearity of the parameteriza- tion yo in W preserves strong convexity of the lower-level problem, provided that t is not
and gø W. W. & g( Uaimi (W,E)...
2

---

Published as a conference paper at ICLR 2026
SBO with
CSBO conditions of Theorem 4.5
Oracle
CSBO
subproblems
Guo et al.
2021
Conditional
0 (mc"
Hu et al.
2023b
Conditional
(c
Ô (c
(
Ours
Joint only
(F-
Ō(e poly (M)( ma (
pply
(
Table 1: Comparison of sampling oracle assumptions and sample complexity bounds for SBO/CSBO.
ill-conditioned. Crucially, the lower-level objective is now expressed as an expectation over the joint distribution IP (S..n)) eliminating the need for conditional sampling.
Our framework begins by selecting a vector basis functions (NN to reformulate (CSBO) as a standard SBO instance 4 We then apply existing SBO algorithms to compute an e-accurate solution to [BB0 which we lift to corresponding solution to (CSBO) that is e-accurate if IIM] suitably expressive. Our analysis relates the regularities (SBO and the optimality gap the constructed solution to simple metrics on G[N], These relationships not only guide the choice of basis functions but also enable near-optimal sample complexity guarantees under appropriate conditions on [[N],
MAIN CONTRIBUTIONS
We propose a reduction framework for CSBO that leverages the efficiency of existing SBO algorithms. Importantly, our approach requires only samples from the joint distribution P ((..)) eliminating the need for conditional sampling from Pnl.- We show that when basis t is sufficiently expressive, the constructed solution is an 6-stationary point (CSBO)
(Theorem
We relate the regularity constants of the reformulated SBO problem (SBO and its sample complexity, to simple metrics on (Theorem 4.4). Crucially, this result establishes sufficient conditions for a basis to guarantee e-stationary solutions to CSBO with Ō(E iterations and sample complexity, improving the best-known complexity for CSBO by order of magnitude and matching the lower bound for nonconvex stochastic optimization up to logarithmic factors. We then show that Chebyshev polynomials choice of basis that achieves Ō(E-3) sample complexity under mild conditions g and I. satisfied many relevant settings (Theorem 4.5). Table compares prior SBO and CSBO methods with approach terms of sampling oracle requirements and sample complexity.
practical, concrete
We validate our framework empirically on inverse optimization and hyperparameter tuning tasks. Our method consistently outperforms basclines in both convergence rate and final loss. It also exhibits greater flexibility in allocating resources to challenging context regions, matching or surpassing other methods with fewer samples and reduced memory usage.
2 RELATED WORK
Our work lies at the intersection of three lines work: Stochastic Bilevel Optimization, Contextual Optimization, and Approximation Theory.
Stochastic Bilevel Optimization
Stochastic bilevel optimization (SBO), first introduced by Bracken & McGill (1973) has been extensively studied with a focus on the convergence and sample complexity of stochastic gradient methods (Ghadimi & Wang 2018 Chen et al. 2021 Khanduri et al. [021 Hong et al.) 2023 Kwon ctt al.] 2024:(C02 Chen et al. 2024). These works primarily address the standard setting in which the lower-level problem is independent of any external context.
3

---

Published as a conference paper at ICLR 2026
The CSBO framework Hu et al. 2023b) extends SBO by allowing the lower-level problem to vary with a context &, which introduces significant algorithmic and theoretical challenges. Their method leverages multilevel Monte Carlo estimators speed up lower-level optimization, but new lower-level problem is solved without warm start for each sample Ç. In contrast, our work introduces reduction-based framework that transforms any CSBO instance into structured SBO instance by parameterizing the lower-level solution across contexts. This enables the direct application of state-of-the-art SBO solvers including first-order and variance-reduced methods (Guo al. 2021
Khanduri et al. 2021; Dagréou et al. 2022. Chen et al., 2023 Shen & Chen 2023 Kwon et al. 2023
Lu & Mei 2024) without requiring conditional sampling or prior knowledge on y" Moreover, we prove that our approach achieves near-optimal sample complexity under mild assumptions, thereby closing the computational gap between SBO and CSBO for broad class of problems.
Contextual Optimization
Contextual Optimization (CO) refers to the problem of selecting an action 2 (ar that minimizes the expected cost conditioned on a context covariate A recent survey by |Sadana et al. (2024) provides a comprehensive overview of this literature. CO is closely related to the lower-level problem in CSBO, as both involve making context-dependent decisions under uncertainty.
Common approaches to CO include optimizing surrogate losses aligned with downstream decision
objectives (Elmachtoub & Grigas 2022. Bennouna et al. 2024), or learning decision rules such as linear (Ban & Rudin 2019) or neural network- baser policies (Oroojlooyjadid et al., (020). be interpreted as structured linear policy in the context variable
Our parameterization where expressiveness is achieved via a nonlinear basis transformation +(E). Unlike most CO formulations, however, our decision rule arises as the solution to bilevel problem where the upper- level objective depends on the learned representation of the lower-level solution. This structural coupling distinguishes our setting and motivates our complexity and approximation analysis.
Approximation Theory
Function approximation techniques have been employed to address SBO and other nested optimization problems. Recent work by |Petrulionyte et al. (2024) directly optimizes over function spaces in SBO. More commonly, neural network approximations have been used to solve Lagrangian relaxations (Lv et al. 2008) or to learn surrogates for the upper- or lower-level objective (Patel et al., 2022 Kronqvist et al. 2023 Dumouchelle et al. 2023 2024). While these models offer high expressiveness. their nonlinearity and overparameetrrzzatinn make it difficult to obtain tight or interpretable error
guarantees.
In contrast, our approach leverages classical tools from approximation theory, particularly orthogonal polynomials. Fourier and Chebyshev polynomials are well-known for their strong convergence prop- erties (Boyd 2001 Gautschi 2004 Chibara 2011). In particular, the uniform error of approximation of Chebyshev polynomials decreases exponentially when approximating analytic functions, and algebraic convergence for smooth functions (Trefethen) 2019). We use this property to construct expressive and well-conditioned approximations to the context-dependent solution y" (ar, :), and we derive explicit error bounds linking the basis approximation quality to the optimality gap of the original CSBO problem.
PRELIMINARIES
We first introduce the notation adopted throughout the paper. We use || |I denote the l2 norm of a vector and the spectral norm of matrix. The variance of random vector or matrix X is defined as E |||XX E [X] [ For brevity of notation, we refer to (0, 1......,, n) as [n]. We denote by Eg
and Varg the operators Eg-P, and Varg-Pg. Similarly, we denote by E, and Var the operators
En and Var,,-P,ee
Throughout the paper, we make the following assumptions about problem CSBO Assumption 3.1.
(i) The functions/ f. V.f, Vg. and V²g. are Ly,0, LI1, Lg1, and Lipsshitt continuous with respect to (x, y) for any fixed (E, 1), respectively.
(ii) The function g is p-strongly convex with respect y for all (z, E.n).
4

---

Published as a conference paper at ICLR 2026
(iii If 7 Puls. then the gradients (z(z,,.5,1)) Vg(z, y.C.) and g2g(z, 7). unbiased and have variance bounded by of. o and d 9. respectively, uniformly across 9.1:
all y/, and Ç.
Remark 3.2. Assumptions 3.1 (i) and 3.1 (ii) are standard in the SBO literature (Ghadimi Wang
2018 Yang et al. 202T; Hong al. 2023). Assumption 3.1 (iii) is also common in CSBO (Hu et al. 2023b Thoma et al. 20024) However, in contrast to (Hu et al. 2023b). we do not enforce the global Lipschitz continuity of g. thereby avoiding the implieit requirement that the lower-level variable lie in a bounded set. Moreover, we only require the variance of V (x, &, 11) to be bounded with respect the conditional distribution IP nlg. instead of the joint distribution (g..n)
We formally define the terms feature map and expressive basis which will be used frequently. Definition 3.3. A feature map &o = R- is mapping whose components the first N elements of a countable basis of functions 4. Definition 3.4. A countable basis of R), + {oRTEE,, is No exprrsseseive if the function N4 _ No is such that, for any O, there exists W 1Rda + 1dd, xN((e) satisfying:
6² u 2
Ee IIA con (x), y (2. E)
Vo E R4
L9,1'
where K = L 1 Lu.2rr Loobgebاo 4.n is a constant depending only on the regularities of f and g. In that case, we refer & [e) as Φf for conciseness.
1²
Example 3.5. Consider CSBO problem where y (xr E) cos(g cos(x)) and Pg UO, 1). Let + be the polynomial basis 4 (1,5,5², (.,,,,,.. ..... Then [[N] & (1...., EN-1) and the Taylor series of y* at O gives for N even and { E [0, 1]: [y (z, W ((x) < co
N < 1 -expresivee with N+ = (In 1), and de & vlNo(e)) (.., (No(c)-1)
N! Thus 4 is
REDUCTION FRAMEWORK AND SAMPLE COMPLEXITY GUARANTEES
Central to our approach is the parameterization of the lower-level solution using an expressive basis + to reformulate (CSBO) into (SBO ) an SBO problem with a single lower level. We address two main questions: (i) can an e-accurate solution to (CSBO) be constructed from solution to SBO ) (ii) does the reformulated problem preserve the structural assumptions (e.g.. strong convexity, Lipschitz continuity) required for applying efficient SBO algorithms? In this section, answer both questions affirmatively and show how this enables efficient solutions to (CSBO).
4.1 HYPERGRADIENT APPROXIMATION AND REDUCTION VALIDITY
We begin by bounding the discrepancy between the hypergradients of (CSOO) and (SB0g
Proposition 4.1. Under assumption 3./ the following holds for any x E Rd=
FV) - Fo. (x)] < K K. KEgllu (W*(x) - y (x, E)ll
(2)
where is defined in Definition 3.4
This result shows that if the parameterized solution yo- (w) closely approximates y" (x, () in expectation, then the hypergradient of the surrogate objective For a good approximation to that of the true objective F. However, directly bounding the right-hand side of equation 2 is nontrivial. as W* (x) is characterized implicitly. The regularities of g and the optimality W (x) in (SBO yield:
Proposition 4.2. Under assumption
3.1 have for any E de and W E xNo()),
2T.g.1
Ecllve- (W*(x),
(x,,
Bellvo- (W,E) - y² (1
(3)
This result allows us to control the right-hane side of equation by evaluating the error at a suitable W for which the expected distance between yo- (W,-) and y (x, -) is well characterized. Since expressive bases admit such W for any fixed e, it is sufficient to solve the surrogate problem (SBO to produce e-stationary solution to the original problem (CSBO).
5

---

Published as a conference paper at ICLR 2026
Theorem 4.3, Suppose that assumption
3.1 holds, and let d be expressive basis. (=*,)"(=*))
an Va -stationaary solution to 4 then (x",5 + yo (W*(x"),)) )) an e-stationary solution to (CSBO).
Proof. Combining Propositions
4.1
and 4.2
we obtain:
E V
x
E
V
F
II EIVF(()) - (F
22
+
K² (EE 1EEllUo (x*)),) (x*,
2
2
2K Lg, Rell (w))) v-(,,,,,,
+
E
2
1
1A3
62
I..
Lg2
where (1) uses Proposition 4.1 and the fact that (x*, W* (x*))) / -sttatiionary solution (SBO
(2) results from Proposition 4.2 and Jensen's inequality, and (3) holds since &e satisfies equation
This theorem essentially states that by working in the कh -paaaeerrzedd space, any off-the-shelf SBO solver can used to solve the CSBO instance. Since the upper and lower level expectations of (SBO are both taken over (g.n)) one can obtain solution to CSBO without conditional sampling oracle. Moreover, if Φ induces a smooth map & - Yoo (z. E), then gradient step at given generalizes to its neighbors, yielding computational efficiency and guarding against overfitting to context-specific noise.
4.2 GENERAL SAMPLE COMPLEXITY
Although expressive bases guarantee a small approximation error, achieving the condition in equa- tion may require & have large cardinality. In particular, the lower-level problem in (SBOg. may become high-ding nigh-dimensional or poorly conditioned as c - 0, especially if the basis functions are unbounded or highly correlated. To quantify these effects, we define the following metries:
M4 max
sup || (E)] (EEE SE=
and m+(e) min (1, Amin (E
where Ee Eg (S)) is the covariance matrix of the feature map Φ. Here, Mp(e)) upper bounds the maximum magnitude attainable by the feature map $ whereas (e) captures the non-degeneracy of &e by lower bounding the smallest eigenvalue of Eer. A small m) indicates that the feature vectors are concentrated near lower-dimensional subspace. The reformulation' lower level inherits strong convexity if and only if mo(c) positive. To ensure that the lower level of the reformulation remains strongly-convex we restrict our attention to bases satisfying mn (e) > for all > and refer to any such basis as well-conditioned.
tends to 0 for our asymptotic complexity analysis,
We show that the reformulation B can be solved efficiently by verifying that the functions fore (x, W, E. E. 94- (x., W. n) and their first and second order derivatives satisfy the assumptions Gf et al. (021)) provided in the Appendix [D.] [.2 Importantly, we express in lemmas C.4 and the Lipschitz constants and variance bounds terms of Mo (c) and mo (c). Substituting these regularity coefficients into Theorem of et al. (2021), we obtain the result below.
Theorem 4.4. Suppose that assumption 3.] holds and that & is well-conditioned. Then, be achieved with sample complexity in
c-stationary solution to (SBO+.)
δ +. poly (M)(e), mAte))
Fundamentally, this Theorem shows that the sample complexity (SBO scales polynomially in Mo (c) and 1 (c) While (o(e) is natural proxy for lower-level complexity (and hence for

---

Published as a conference paper at ICLR 2026
sample complexity), Theorem 4.4 shows that the complexity is governed by subtler interactions between & and Pg captured by (e(c) and ma(e). Specifically, the complexity remains well- controlled when:
1. The magnitude of d' grows slowly, ensuring that the Lipschitz and smoothness constants of the reformulation remain comparable to those of the original problem, and avoiding the need for significantly smaller step-sizes.
2. The conditioning of Φe decreases slowly, guaranteeing that the reformulation's lower level retains pronounced strong convexity.
Under these two favorable regimes, the number of iterations and samples required to obtain an c-accurate solution (SBO tightly controlled. Crucially, any expressive basis satisfying (c(c) ((1 and 1/m+(c)) ((1) results in near-optimal sample complexity 3(c-3).
In example 3.5 the monomial basis yields (c) ((n((=1)) and M²(c) = V (c)
Moreover, the covariance matrix Vig. coincides with the Hilbert matrix, implying m.((e)
@ (Np(c) (1 v2) -ANa(e)) Thus, under the uniform distribution, the monomial basis becomes
rapidly ill-conditioned as + O, despite the fact that (+ grows only logarithmically. In contrast, the Chebyshev basis satisfies NChebyshev (c) = ( )) and Mchebyshev (c) S VNCluebystee (c), while remaining cell-conditioned with 1/ L/MChhbyshev (c) O(Nchebyshey (c)) for any e 0. Theo-
rem 4.4 thus yields sample complexity in (c-33) for this specific choice of basis.
4.3 CHEBYSHEV BASIS AND HEAR-OPTIMAL SAMPLE COMPLEXITY
Theorems 4.3 and 4.4 established that any sufficiently expressive, well-conditioned basis yields an e-stationary solution to CSBO problems with a sample complexity depending on simple metrics involving the basis and context distribution. Example 3.5 illustrates that the basis choice is key to obtain strong convergence guarantees. We now provide sufficient conditions, satisfied in many practical settings, under which the basis constructed from Chebyshev polynomials (defined in [E.T) achieves near-optimal complexity guarantees. We emphasize that these conditions are not necessary, and that Chebyshev polynomials and other bases can yield near-optimal complexity when these conditions violated.
Theorem 4.5. Suppose that Assumption 3. holds, along with the following conditions:
(c.1) Either (i) there exists c > 0 such that the density of Fe is lower bounded by g on E, or (ii) the cardinality of is finite.
(c.2) The support E is bounded.
(c.3) The function G(r. y. & Eyll [9(2, y, E.) ( is analytic in (y, {) for any fixed x.
Then the Chebyshev polynomial basis & is well-conditioned with:
M4 Ō and m. (e)=
The conditions of Theorem 4.5 ensure that y (xx,)) can be efficiently approximated by truncated Chebyshev series. Specifically. (c.1) prevents the feature covariance matrix Σg, from becoming degenerate as e + 0: (c.2) avoids requiring periodicity or decay conditions at infinity for uniform approximation; and (c.3) guarantees analyticity of of (2. so that the uniform error of approximation of Chebyshev series decreases exponentially fast (Bernstein) 1912, Adcock & Huybrechs) [014 Trre
fethen 2019). Many applications satisfy these conditions, including Meta-Learning and Wasserstein DRO with Side Information (Hu et al., (023b). well as Tax Design, Reward Shaping, and Dynamic Mechanism Design (Thoma et al. 2024), which are naturally modeled with discrete or truncated continuous context distributions.
The proof builds on this exponentially fast decay for functions that are analytic in an open region bounded by Bernstein ellipse, and extends these convergence results multivariate analytic functions. As real-analytic functions on a bounded set 3 are analytically continuable in an open complex containing E, we results multivariate analytic functions to prove that the
7

---

Published as a conference paper at ICLR 2026
Chebyshev basis is expressive with Na growing aub-polynomially in c Together with the facts that Chebyshev polynomials are uniformly bounded by I, and that the degeneracy of the truncated series is bounded as m+(e) 52 (c) under condition (c.1)) we obtain the desired result.
Along with theorems
and 4.4 it follows that one can reduce (CSBO) to (SB using the Chebyshev basis and solve the latter with Ō(c=3) samples as the terms involving (c) and (fm
in theorem 4.4 collapse into polylogarithmic factors.
Corollary 4.6. Suppose that assumption 3.7 and the conditions of Theorem 4.3 hold. Then,
e-stationary solution to CSBO)) can be achieved with near-optimal sample complexity of O (E ()
In practice, the conditions of Theorem 4.5 are satisfied in many relevant settings where & is finite (e.g. SBO with multiple subproblems) or has bounded support and vanishing density (e-g.. uniform, truncated Gaussian, or mixture distributions), Notably, meta-learning and personalized federated learning, where & ranges over a finite number of tasks, and robust stochastic optimization with side information drawn from distribution with full support on a compact set all naturally satisfy these conditions.
5 NUMERICAL RESULTS
Many machine learning tasks can be formulated as CSBO, including hyper-parameter optimization (Shaban et al., 2019| Franceschi et al. 2018). inverse optimization (Ahuja & Orlin (001), meta- learning (Rajeswaran al.) 2019), reinforcement learning from human feedback (Chakraborty et al. 2024), and personalized lederated learning (Shamsian et al. 202T).
In the following experiments, we compare our proposed reduction framework against STOCB1O (Ji et al. 202T) applied to discretized SBO approximations of the original CSBO problems. For STOCBIO[N, J. the context space E is partitioned into N intervals of equal size, each treated as an independent subproblem, yielding a SBO formulation with subproblems.
Our method, denoted R& [N], uses the feature map x and STOCBIO[1] to solve the reduced problem. We experiment with monomial, Chebyshev, and Fourier bases; however, in the hyperparam- eter optimization task, we report only Chebyshev and monomial results, as Fourier and Chebyshev perform nearly identically in that setting. Importantly, for any fixed N, STOCBIO [N] and R. [M] have identical memory usage: dæ + Ndy. enabling a fair comparison under fixed resource constraints. Details of the numerical experiments are provided in Appendix A
5.1 INVERSE OPTIMIZATIION
Inverse optimization seeks parameters that explain observed decisions y as optimal solutions an underlying optimization problem. While traditionally approached through bilevel formulations, many inverse problems naturally fall into the CSBO setting, yet are rarely treated such in existing work.
We consider the Static Traffic Assignment (STA) problem (Beckmann et al. 1956), which models network equilibrium flows under fixed digginddsstnationn (OD) demand. Using Beckmann's convex- potential formulation and introducing penalty for constraint violations, we cast inverse capacity estimation as the following CSBO problem:
min B(E.))>PEE.)) Ily (x, nll
Σ Ue EE8
s.t. (x, = arg min
to (z + de(v)
where y01 {) is the equilibrium flow given edge capacities and OD demand &, 17 is the correspond- ing noisy observation of that flow, te is the edge performance function relating the flow to the travel time, and Av(v) penalizes infeasible flows and the violation of OD pairs demand constraints.
We simulate a two-edge network with a single OD pair. For every trial, we sample ground truth capacity vector x* and generate training and test sets with 10 i...d. samples (g, 17) each. The final solution (z, ((-)) )) is averaged over the last 10% epochs. Performance is evaluated via the test loss F(Z), evaluated over the test set after computing the exact lower-level solutions y , E). We also
8

---

Published as a conference paper at ICLR 2026
report the expected lower-level enror Ay - Ag
- 7(E)ll and the upper-level parameter error
x
0.08
0.40
0.07
0.06
0.25
4
0.20
0.02
0.03
0.01
0.65
0.00
0.00
100
Figure 1: Loss F(t) (left), lower level solution error Ay (center), and upper level solution error Az (right) of STOCBIO and our reduction framework using monomial, Fourier, and Chebyshev bases. The reference loss is Fiet F(x").
Figure demonstrates the advantage the CSBO reduction. As few as = 3 basis functions suffice to produce reasonable solutions, whereas STOCBIO struggles with instability or excessive sample requirements. By N = 5, all three bases close the optimality gap to within 3%, while STOCBıO achieves a comparable accuracy at N = 50. Beyond N 5, the lower-level error stops decreasing significantly for the monomial basis, while the more expressive Chebyshev and Fourier bases continue to reduce the error and consistently outperform STOCBIO every N.
RChobyshev and Reourier achieve the smallest loss for 2 10, whereas STOCB1O requires N 2 100, and still does not reach the same lower-level error. These results validate our theoretical claims: expressive bases can compactly approximate context-sensitive solutions in CSBO. Compared to partition-base based SBO approximations, the parameterization leverages the continuity of y" achieve better accuracy using an order of magnitude less memory or, with the same memory budget, an order of magnitude lower optimality gap.
5.2 HYPERPARAMETER OPTIMIZATION
Hyperparameter optimization has become the benchmark of choice for evaluating the performance of stochastic bilevel optimization (SBO) methods in practical, high-dimensional settings. Huu et al.) (2023a) introduced more challenging variant of this problem involving lemperature-dependen objectives. Instead simplifying the problem to a finite set of temperatures, we address the original formulation in which temperatures drawn from continuous distribution.
In this experiment, we aim to train a linear classifier for MNIST (LeCun et al. 1998) with the complication that a fixed fraction p 0.3 of the training labels have been randomly corrupted. Here, the upper level seeks to weight the training points to minimize the expected validation loss across distribution of model temperatures IPg, while the lower level computes, for each the model parameters y by minimizing a weighted and regularized training loss. Formally:
min Be-p.En-st [Ce(v* (x, E); D)]
s.t. (² = arg min ED~DaI (z) +>>bv/?
where Le is temperature-speeific convex loss, and Pg. Deat. and Demin denote the distributions over temperatures, validation data, and training data, respectively. This CSBO formulation encourages robustness to label noise while generalizing across temperatures.
Figure 2 compares our method R. [N] against STOCBIO[N] baselines. Algorithms that solve a separate inner problem for each sample & are omitted since they require a prohibitively large number of iterations to converge, even with the acceleration method of Hu et al. (2023b). By discretizing the context space into N subproblems, STOCB1O [N] yields lower final validation loss for larger N at the cost of slower convergence, since finer partitions require nearby regions of to be optimized independently and redundantly. For small N, the high and increasing training loss of STOCBIO[N]

---

Published as a conference paper at ICLR 2026
1.00
1.00
stactic[3]
stcmmo
Rewusa
sto:Blo[10]
stocBl0110]
Rewona
0.95
stoc812420)
0.93
shoetlnn 201
Raswed)
stocBiC(50)
stocBiO
Resevved
0.90
Valcocion loss
0.85
Triiiing
0.85
0.80
0.80
0.70
0.70
25000 30000
Epoch
Epoch
Figure 2: Moving average of the validation (left) and training (right) losses over epochs of stocBiO and monomial, Fourier, and Chebyshev bases on hyperparameter optimization.
(arising from the increase, on average, of the weights (x)) indicates its inability to accurately estimate y" across all contexts and adapt new training weights. Even for large N, it fails to accurately approximate y" in regions where it varies sharply in E.
In contrast, our method leverages shared structure by learning global coefficients across all contexts, which cuts computational overhead and enables the model to allocate resources to context regions that require them most. As a result, Cheebyshev [5] delivers both the fastest convergence and the lowest final training and validation losses; adding more basis functions yields only marginal gains. In comparison, the monomial basis lacks the expressiveness to substantially improve the accuracy of the lower-level solution approximation as N grows, and thus performs worse than other methods for N large.
6 CONCLUSION
We presented a framework that reduces any instance of CSBO to SBO problem by parameterizing the lower-level solution with expressive basis functions. This reduction decouples the upper-level decision from the context and eliminates the need for conditional sampling oracles, which are often impractical in real-world applications. We related the sampling complexity to simple basis-dependent metrics, establishing criteria for achieving solutions with near-optimal of magnitude better than existing CSBO methods and matching the nonconvex lower bound up to logarithmic factors. We then showed that Chebyshev polynomials satisfy these criteria under mild conditions, offering concrete and efficient choice of basis for a broad class of problems. We validated our method on inverse and hyperparameter optimization tasks, demonstrating faster convergence, lower final loss, and reduced memory usage compared to partition martition-based baselines. While we demonstrated that the Chebyshev basis is versatile choice, online learning of instance- specific bases could yield a parameterization with improved accuracy and parsimony. Establishing practical algorithms and theoretical guarantees for adaptive bases is left for future work.
((c-)) complexity, an order
ACKNOWLEDGMENTS
This work was supported by AFOSR Grant FA9550-23-1-0190 Additional support was provided to the author Jiawei Zhang by the Office of the Vice Chancellor for Research and Graduate Education at the University of Visconsin-Madison with funding from the Wisconsin Alumni Research Foundation.
REFERENCES
Ben Adcock and Daan Huybrechs. On the resolution power of fourier extensions for oscillatory functions. Journal of Computational and Applied Mathematics, 260:312-3366 2014. ISSN 0377-0427.
Ravindra K Ahuja and James Orlin. Inverse optimization. Operations research, 49(5):771-783, 2001.
10

---

Published as a conference paper at ICLR 2026
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization, 2022.
Gah-Yi Ban and Cynthia Rudin. The big data newsvendor: Practical insights from machine learning. Operations Research, 67(1):00-108, 2019.
Martin Beckmann, Charles B McGuire, and Christopher B Winsten. Studies in the economics of transportation. Technical report, 1956.
Omar Bennouna, Jiawei Zhang, Saurabh Amin, and Asuman Ozdaglar. Addressing misspecification in contextual optimization. arXiv preprint (xXiv:2409.10777 2024.
Serge Bernstein. Sur l' l'ordre de la meilleure approximation des fonctions continues par des polynómes de degré donné, volume Hayez, imprimeur des académies royales, 1912.
John P Boyd. Chebyshev and Fourier spectral methods. Courier Corporation, 2001.
Jerome Bracken and James T McGill. Mathematical programs with optimization problems in the constraints. Operations research, 21(1):37-44, 1973.
Souradip Chakraborty, Amrit Bedi, Alec Koppel, Huazheng Wang. Dinesh Manocha, Mengdi Wang, and Furong Huang. Parl: A unified framework for policy alignment in reinforcement learning from human feedback. In The Twelfth International Conference on Learning Representations, 2024.
Lesi Chen, Jing Xu, and Jingzhao Zhang. Bilevel optimization without lower-level strong convexity from the hyper-objective perspective. arXiv preprint arXiv:2301.00711 2023.
Tianyi Chen, Yuejiao Sun, and Wotao Yin. Closing the gap: Tighter analysis of altemnating stochastic gradient methods for bilevel problems. Advances in Neural Information Processing Systems, 34: 25294 25307, 2021.
Tianyi Chen, Yuejiao Sun, Quan Xiao, and Wotao Yin. A single-timescale method for stochastic bilevel optimization, 2022.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochastic bilevel optimization under relaxed smoothness conditions. Journal of Machine Learning Research, 25(151):1-51, 2024.
Theodore Chihara. An introduction orthogonal polynomials. Courier Corporation, 201 1.
Tianshu Chu, Dachuan Xu, Wei Yao, and Jin Zhang. Spaba: single-loop and probabilistic stochastic bilevel algorithm achieving optimal sample complexity. arXiv preprint arXiv:2405.18877, 2024,
Ashok Cutkosky and Francesco Orabona. Momentum-basee variance reduction non-convex sgd. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances Neural Information Processing Systems, 35:26698-261 10, 2022.
Justin Dumouchelle, Esther Julien, Jannis Kurtz, and Elias Boutros Khalil. Neur2ro: Neural two-stage robust optimization. In The Twelfth International Conference Learning Representations, 2023.
Justin Dumouchelle, Esther Julien, Jannis Kurtz, and Elias B Khalil. Neur2bilo: Neural bilevel optimization. arXiv preprint arXiv:2402.02555, 2024.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1): 9-26, 2022.
Cong Fang, Chris Junchi Li. Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic aath-integrated differential estimator. Advances in neural information processing systems, 31, 2018.
11

---

Published as a conference paper at ICLR 2026
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pp. 1578-1577. PMLR, 2018.
Walter Gautschi. Orthogonal polynomials: computation and approximation. OUP Oxford, 2004.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint 18X2::880.00224 2018.
Zhishuai Guo, Quanqi Hu, Lijun Zhang, and Tianbao Yang. Randomized stochastic variance-reduced methods for multi-task stochastic bilevel optimization. arXiv preprint arXiv:2105.022000 2021.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, 15(1): 2489-2512, 2014.
Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
Quanqi Hu, Zi-Hao Qiu, Zhishuai Guo, Lijun Zhang, and Tianbao Yang. Blockwise stochastic variance-reduced methods with parallel speedup for multi-block bilevel optimization, 2023a.
Yifan Hu, Jie Wang, Yao Xie, Andreas Krause, and Daniel Kuhn. Contextual stochastic bilevel optimization. Advances in Neural Information Processing Systems, volume 36, pp. 78412-78434. Curran Associates, Inc., 2023b.
Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 4882 4892. PMLR, 18 24 Jul 2021.
Prashant Khanduri, Siliang Zeng, Mingyi Hong, Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A near-optimal algorithm for stochastic bilevel optimization via double-momentum. In Advances in Neural Information Processing Systems, volume 34, pp. 30271-30283, Curran Associates, Inc., 2021.
Jan Kronqvist, Boda Li, Jan Rolfes, and Shudian Zhao. Alternating mixed-integer programming and neural network training for approximating stochastic two-stage problems. In International Conference on Machine Learning, Optimization, and Data Science, pp. 124-139. Springer, 2023,
Jeongyeol Kwon, Dohyun Kwon, Stephen Wright, and Robert D Nowak. A fully first-order method for stochastic bilevel optimization. In International Conference on Machine Learning, pp. 18083- 18113. PMLR, 2023.
Jeongyeol Kwon, Dohyun Kwon, and Hanbaek Lyu. On the complexity of first-order methods in stochastic bilevel optimization. arXiv preprint arXiv:2402.07101, 2024.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-basse based learning applied to document recognition. Proceedings of the IEEE, 86(1) 86(11))227--2324 1998.
Zhaosong Lu and Sanyou Mei. First-order penalty methods for bilevel optimization. SIAM Journal on Optimization, 34(2):1977-199,, 2024.
Yibing Lv, Tiesong Hu, Guangmin Wang, and Zhongping Wan. A neural network approach for solving nonlinear bilevel programming problem. Computers & Mathematics with Applications, 55 (12):2823-282) 2008
Afshin Oroojlooyjadid, Lawrence V Snyder, and Martin Takáč. Applying deep learning to the newsvendor problem. 1ISE Transactions, 52(4):444-46 2020.
Rahul Mihir Patel, Justin Dumouchelle, Elias Khalil, and Merve Bodur. Neur2sp: Neural two-stage stochastic programming. Advances in neural information processing systems, 95:23992-24002 2022.
12

---

Published as a conference paper at ICLR 2026
leva Petrulionyte, Julien Mairal, and Michael Arbel. Functional bilevel optimization for machine learning. arXiv preprint arXiv:2403.20233 2024.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in neural information processing systems, 32, 2019.
Utsav Sadana, Abhilash Chenreddy, Erick Delage, Alexandre Forel, Emma Frejinger, and Thibaut Vidal. A survey of contextual optimization methods for decision-making under uncertainty. European Journal of Operational Research, 2024.
Amirreza Shaban, Ching-An Cheng, Nathan Hatch, and Byron Boots. Truncated back- propparppattiion for bilevel optimization. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1723-1732. PMLR, 2019.
Aviv Shamsian, Aviv Navon, Ethan Fetaya, and Gal Chechik. Personalized federated learning using hypemeeworks. In International Conference on Machine Learning, pp. 9489-9502. PMLR, 2021.
Han Shen and Tianyi Chen. On penalty-based bilevel gradient descent method. In International conference on machine learning, pp. 30992-31015, PMLR, 2023.
Vinzenz Thoma, Bama Pasztor, Andreas Krause, Giorgia Ramponi, and Yifan Hu. Stochastic Bilevel Optimization with Lewer-Level Contextual Markov Decision Processes, June 2024. arXiv:2406.01575.
Lloyd N Trefethen. Approximation theory and approximation practice, extended edition. SIAM, 2019.
Junjie Yang, Kaiyi Ji, and Yingbin Liang. Provably faster algorithms for bilevel optimization. Advances in Neural Information Processing Systems, 34:13670-13682, 2021.
Yifan Yang. Peiyao Xiao, and Kaiyi Ji. Achieving O
(Ee-1.5) 1.5) complexity in hessian/jacobian-free stochastic bilevel optimization, arXiv preprint arXiv:2312.03807. 2023.
13

---

Published as a conference paper at ICLR 2026
A SPECIFICATIONS AND FURTHER NUMERICAL EXPERIMENTS
Experiments are run in parallel on an AMD EPYC 9734 processor. Each individual run uses 16MB for runtime ranging from 10 to 90 minutes, depending the application and parameters used.
We omit the DL-SGD and RT-MLMC schemes Hu et al. (023b) from our benchmarks because of their inner-loop strategy: both schemes use start from arbitrary yo and use the EPOCH GDG algorithm of Hazan & Kale (2014) without the projection step. In practice, these schemes perform best when either:
(x, : E }} is contained a small ball around some yo()), where (o(r) is known estimable from previous iterations.
2. The lower-level problem is sufficiently well-conditioned that only a few inner-loop steps suffice for convergence.
In our experiments, such a (z(z) does not exist since the lower level solutions y (xx vary sub- stantially in ę. Furthermore, depending the inner-loop step size, the solution either diverges or requires a large number of steps to provide a reasonable estimate of y" (and thus FF), resulting in an excessive runtime.
A.1 INVERSE OPTIMIZATION
In this experiment, we consider a network with two nodes, two edges, and a travel demand &
from 3
node to node We use the edge performance function Le (e( - la.e + a
with
and 8 4. To penalize negative flows and violation of the travel demand E. we define
Adtemand ((s
Ax(
yc
+ +
Σ 3E7
(ye
330
where = (resp. =) denotes the positive (resp. negative) part of 2, Ademand 100, and X = 50. Note that one only needs to penalize insufficient total flow since the edge performance function strictly increasing with respect to the flow The results are averaged over 50 runs, with 95% confidence intervals assuming normally distributed errors across runs. Each run uses a synthetic dataset generated with the following procedure. The free flow travel times and ground truth capacities x² are sampled from the uniform distribution supported on [1, 21,2| [&] and [0.2, 0.8] respectively. We generate Arrain 1000 training samples by drawing each context & independently from a standard uniform distribution. For each &, we compute the corresponding optimal flow y" (z*. () using gradient descent, and set v = y (a* {) + where ~ N(0, oo). We resample the noise until vj is non-negative. We follow the same procedure for the Theu 1000 samples forming the test set. We follow the same steps as in the hyper-paranters optimization experiment to select a, 3, Timners and set 10 and 10"
A.2 SYPER-PARAMETERS OPTIMIZATION
We compare the performance of our proposed algorithm with stocBio, a reference algorithm that outperforms other baseline algorithms BSA, TTSA, HOAG the MNIST Data Hyper-Cleaning task, a hyperparameter optimization problem. The dataset consists in 19,000 training and 1,000 validation images. The objective of Data hyper-cleaning involves training classifiers on dataset where each label has been randomly and independently corrupted with probability that is, each label is replaced by random class with chance p. The classifiers have losses with different temperatures. Formally, the objective function is:
min
EENPE
Σ
(r,
Deall
(X.
s.t. (x, arg min
(()) +|llll
P
(X.
14

---

Published as a conference paper at ICLR 2026
where L is the cross-yntropy loss and o()) is the sigmoid function. Here Pg (0.1,, 10) and we choose the regularization parameter À = 10-3. The results are averaged over 20 randomized trials. We use a batch size of 512 and use grid search to choose: the inner-loop stepsize & from {0.001, 0.01, 0, the outer-loop stepsize from {10* k E [-5, 5] J. and the number of inner-loop steps Tinne from {1, 10, 100). We choose a number of samples K = 10 and a scaling
10 to approximate (Bnj mi V22g(z, -1
II (I (I-s V22g(2, (2,
A.3 ADDITIONAL SBO BACKBONES
To demonstrate that our findings are not tied to particular choice of backbone solver, we include here two additional SBO solvers which differ substantially in design from STOCB1O: SUSTAIN Khanduri et al. (222)) and SOBA Dagréou et al. (2022). We follow the same setup as in the data- cleaning task. We compare the final training and validation losses of the solutions obtained on the n-subproblems SBO approximation (SOLVER) with the solutions obtained the single lower-level reformulation using n Chebyshev basis functions (RChehyshev (SOLVERR) ). The results are averaged over 5 randomly seeded runs. As shown in Table 2 the parametrization consistently improves both training and validation losses across all solvers for any fixed n. Further, a lower final loss can be achieved with fewer basis functions than subproblems. This indicates that the advantages of our parametrization are not specific to STOCBIO, but persist across several distinct SBO solvers.
Table 2: Performance comparison of various SBO solvers with and without reduction.
Method
n
Validation Loss
Training Loss
5
0.869 + 0.007
1.208 + 0.021
SOBA
10
1.015 + 0.011
1.405 + 0.017
50
1.348 + 0.024
1.838 + 0.034
5
0.659 + 0.014
0.790 1 0.030
Rchebyshev SSOAA]
10
0.653 = 0.013
0.783 = 0.027
50
0.656 + 0.012
0.786 + 0.029
5
1.133 + 0.006
1.335 1 0.025
SUSTAIN
10
1.167 1 0.010
1.540 1 0.015
50
1.326 0.018
1.887 T 0.018
5
0.890 T 0.011
0.972 T 0.026
RChebysov [USTAIN]]
10
0.905 1 0.008
0.975 0.012
50
0.903 + 0.009
0.968 + 0.028
5
0.941 0.010
0.848 0.027
STOCBIO
10
0.837 + 0.020
0.784 + 0.036
50
0.734 1 0.022
0.739 1 0.033
5
0.715 + 0.022
0.740 + 0.041
RChebysher STOCBIO)
10
0.706 - 0.010
0.729 + 0.023
50
0.713 + 0.017
0.733 + 0.026
B SIMILARITY OF HYPERGRADIENTS
We first prove Proposition 4.1
Proof. Let x E Rdd Recall that VF(x) = Egg, ()((I,,1)) and Fz = E Fo E.)), where:
vF(x, A v Va ().)))
- Vi2g(2. (1,
(x. A (W
- -V12g(z,y0 (W (w))),)),
15

---

Published as a conference paper at ICLR 2026
Consider sample (f. ri). For readability, define (z E) - llvo (x), (2 e)ll
and:
Ayv+) = V220(2, yo (W' (.)
A(y") =
Byy") = (x,
( = 222 yo (z) C(yo) V2I (4)
C(y") = Vef(0, (x,
We then write and bound [V (F m) using the triangular inequality as: |/ Fipe E,) - VF &. < (i
+ http://MMceccha.-0--ooo-ca...a.
-
( A(y"))((""""((((""
$ ,2, (1(())))) A(v"))))))))))))))) +|
+ BB(0)) (B(g)) -
+ [C(yo) - C(y))l - |B('")~'1
From the regularity of f, 9, and their gradient given in Assumption 3.1
we obtain:
||((v)) A(y"((())))) - (z,
Lg. (x,
[Bb()) B(r²) - (14+) -1 [B B(y")| BBy)) " || =
112
|[C(v)) C(v')ll - 1, (x,
||A(8)) )1 - Lg.1:
||A(y*)1I S Lg,11
[[C(v))] )1 & L5.0:
|[C(v*)] S Tsf.0:
where the second inequality uses the identity fact that (3y+))" and [B()*)"1 are upper bounded by 1/μ from the strong convexity of
< -1--11-11 |X-1----11
- and the
It follows that:
L (x, (2, ( s L
1
L Lngahig.loo (x, +
Le.. T2g.2
Ag (z.
112
(xy(F,E)
where K = L5a1 + Lazbo Larbagbio + Lr.
a
We then bound the difference between the hypergradients using Jensen's inequality:
V (x) - VF(x)]
< (e ( (z. E. VF v2(x,6,))
S K E(c..) [x,
= K (Eelly((W' (w))), y²xxx,
We then proceed with the proof of Proposition 4.2
Proof. Let Rdo, W Rd,xN, and G(z, ((z,y.E) & Enn 19(z, y, & E)m). As g is smoothh in (x,y) for any (E, n), and p-stronglyy convex in y for any fixed (x, E, n), so is G. Since W* (*) minimizes Eg [G(,,vo(, (,( E), we have in particular:
Bg [G(r, yo (x), & Eg GG(, yo (W,)),
(6)
Additionally, since y² (z, {) minimizes G(a, :: E), also holds that:
G(x,y" (x. () (( (z)) (x),
16

---

Published as a conference paper at ICLR 2026
Using the strong convexity of G at (x) thus obtain:
G(r, yo (W* (x). G(z, (). 2 (1))
vg e (7)
On the other hand, the smoothness of yields:
[G yo (W () G( v/ (x, E) 1. / (W,5) (x, ve
(8)
Taking the expectation over & on both sides in equation and equation 8 and using the incquality equation o we have:
2 R [G(x, yo (W" (x,
(Wllo( y² (x,
v Eg [G(x, yo (W,E), - (zx,
1
2 Ee llvv y" {x,,
<
(W Egllvv
/
As this holds for any a E Rdz, we obtain the desired result.
C REGULARITY OF EQUATION SBO [NN]
For readability, we refer this section to Ma (c) as Ms. and to mo as ma.
Lemma C.1. A μla, and B 0 with μ 2 0, then A B ž pld, B and B&AZ μB & Ida-
Proof. By the bilinearity of the Kronecker product we have:
A B pla, @ B (A - pla,) ( B
Since the Kronecker product of two positive definite matrix is positive definite, it holds that (A plda) & B > and thus B μA @ Ldz ł 0. With symmetrical argument, we obtain
B & A Z μB & Ida-
C.I STRONG CONVEXITY OF G4 (z, W) A B( (0(2, (E).),
Lemma C.2. Under assumptions 3.1 (ii) and if th is well-conditioned. G4 is pma (c)stonyy convex in W for any fixed Rdd..
Proof. We have for any fixed x de that Gp. is twice differentiable with respect to W as the expectation compositions of twice differentiable and linear mapping. Additionally:
V22 G (x. W) Eg [V2 (E) s ((E)
Go
Since is y-strongly convexity with respect to with μ > and Eg [E) = mo mo (c)
obtain using Lemma C.1 twice:
V22 (x, n& [Ia, (())
pla, & Eg [E)
= (c) INa(e)
ummole)la.
and conclude that G&p (z, W) is pmm pm (ersttogyy convex with respect to W for any x Rd,-
C.2 LIPSCHITZ CONTINUITY
Lemma C.3. Let h(,,, E.))) Rd= Bd x x Rd, + R and ((E) E - NR,, Suppose the following conditions hold:
1. h is L--iipscitt continuous with respect to (x, y) for any fixed (E, 11)
17

---

Published as a conference paper at ICLR 2026
2. There exists constant M such that:
|ς(())| S, AE E
Then the mapping he (x. C,C,1) respect (x. for all fixed (g,n): 17)
(,,)) m) + Mx, (C) ()))))) is &.M contiiis continuous with
Proof. Since h(,, C, 17) is L- L-Lipschitz continuous in (a, y) and supee= || - Mp. we have for any (z, W) and (a', W)): l (z, W, ho ( W .)n)ll
[/h(2; (.(O), ()((()))))))) h(x', (3
I IA3 I/3 WYB
[//(z, (4( - ((2 (' -
ML (I|= - x'| ([ (()(()II
ML (I| - - Ms W Will
LM M (11-~ I[ - W'I)
where (1) uses the sub-multiplicaatiity of 11. (2) follows from the Lipschitz continuity of and this inequality [|((E)]| < M, (3) uses again the sub-multipiicatiiity of || and the inequality (E)]l (e),), and (4) holds since s Mo. Therefore h4 is LM M-Lipschitz continuous in (x. W).
Lemma C.4. The following hold under assumption 3.1
1. The functions for W,E,n) Lo..Mo-LLpschiii with respect and W.
2. The gradients f. (x, W,E, n) and Vg (x. W,C, n) are J M& and Lg M2 Lipschitz. respectively, with respect and W.
3. The second order gradients Vi292- (z, E, and V2294- (z, W, are Ly Lipschitz with respect to x and W.
Proof. Under assumption 3.1 (i), the mappings f. Vf. Vg, and V2g, are Ly L Lg 1, and Lg.2 Lipschitz continuous with respect to (z, y) for any fixed (5, 7). respectively, Additionally, the chain rule gives:
Vi (z. W,G, n) = Vıf(<, (((E...))))
V2fo. (I, W,C, m) = V2/(x, (2)(
Vigo. (z, W,&, n) = Vig(c,WW((E)55
V 22 (x, W, m)) = V29(z, (())
1290. (x, W,C. 17) = Vi29(2, ())
V V2290. (Ir, W,C,
(O()), @ ((E)
can then use Lemma
C.3
to obtain the following:
h
1
M
Lipschitz coefficient of h(,, W ((),), w.r.t (x, W)
for
1
Lz,0
L
Vifec
Ia.
Lsa
1
Lf1Ms.
V2fa=
T
L5a
Lg113
V Vigss
la-
Lg.1
1
20
TT
Lg.1
Ma
1 M3
T
Lg.2
Mr
Mg
2 22294
Lg.2
M2
Lg
18

---

Published as a conference paper at ICLR 2026
and conclude using the inequality 1 I Mg.
C.3 BOUNDED VARIANCE
Lemma C.5. Under assumption 3.1 then for all &. y² (-,5) E) is LypLippchitz continuous with:
Lg
Ly
Proof. Let g(x, y. E) = (a, W.C.1) 7)) By definition of y", we have V2g(a, (2, (). = Then, by taking the derivative on both sides w.r.t using the chain rule, and the implicit function theorem, obtain:
V29 (00(,,"(x)).)) (x).5)
(1..) =0
It follows that
Lemma C.6. Let h(x, y.S. Rd x RR x E Rd + R and 1(g) - RR, Suppose the following conditions hold:
1. h(æ, y. U, 11) has, conditioned on &. variance bounded by o² i.e.
E h, B [h(x, U, E, n'1l so²; Vr e RR E , RRk
2. There exists a constant C such that:
[| V, SC, Vo E Rdd , E R Rdc
3. There exists a constant M such that:
(((EE) & M, AE
Then the mapping ho (a,, W) + Ma, W.(E), has a variance bounded by
M (o² ( (²).
Proof. Let (1 WT). Using the law of total variance we have:
Var(s.n) [2] = Egg [Var [Z E]] + Varg [En [Z {]]
For all & E holds that:
Var [Z {] = Enyl (O(E), - Eyyle [A(2,, ( ((E)))
< |1(())12 E,ys ||M(E, (E(). E, [f(z, w (E) 5
< 11(())11--0
where the second inequality follows from the sub-multiplicatiiityy of || and the fact that ((E) is deterministic when conditioned on g. and the last inequality holds under condition
Similarly, we have that for all & E E and under condition 2:
E [Z E]]l < ||E [A( W W &, ())()) [||
$ [[((E)] [Eye [M( W,G,)) [I]]
< [[((E)] C
Combining the above results, we obtain:
Var(g.)) [2] < Rg [[[((E)](23]] E. [|IE.le [Z <]]l]]
< S22 + Eg [[M(S))2 OP]
M² (o² + C2)
where the last inequality condition 3.
19

---

Published as a conference paper at ICLR 2026
Lemma C.7. Under assumption 3.1 the mappings Vifa (x, W.C.n), Vefae (x, W.C.w n), V299 (I, W.C. n), Vi200< (z, W. W.S.))) 7). and V22gu (x, W,5.7) 7) have a bounded variance for all and W such that |W (x)l Ao.
Proof. Under assumption 3.1 (iii) we have for any (z. that the variances of Vif U.S. (, and V2f S. 17) are upper bounded by oz. and the variance of V229(z, y. (. and V22g y, y.y.y.... 5.7) by 22.2- Thus these 4 functions satisfy the first condition of Lemma C.7 From the Lipschitz continuity of f and Vg (assumption 3.1 (i) we have for any (x, (I,9.5.7)
( (, < Lg,0
V. $ L,0
V. < 4g1
V 2.. S Lg.1
Taking the expectation over ~ P. Fl the second condition Lemma C.7 We then use the chain rule to get:
holds for theses 4 functions.
Vifar (x. W, E, n) = Vi,(2,
Vzfa- (x, C, 17) = V2,f<,, (2.(
V Vi2g4- (I., W,C. 77 = VI20(1, ())
V2290. (z, (. V22 (E).)) @ (E))
Since (E)] S M4. Lemma
C.6 applies and we obtain the following bounds:
a²
C
M
Bound on Var [h(x, W. E. n))
Vifar
Td
I.f.0
1
of + 7700
22
of
$
L-f00
M4
M (o) + 1,
V i200
9.2
$
Lg.1
M4
M (o2,2 12,1)
V2298-
Lg.1
M3
M (o + L2,1)
9.2
We conclude that these 4 mappings have a bounded variance.
The case of V2g4. requires extra care since not uniformly bounded. We have:
[/,, W (5), m) < V2 W (G), 5, (x.) + vx,,
< Lg [ (E) - y" (",,, E) + (12
Using the identity (a + b) < 2a 2 + 2b2. we have:
(Z W (E) 1) < We use the triangular inequality, the identity (a + b)2 < 20 + 26 and [| S Ms to bound:
= "",, ().
(E) y" (x. <)1 < ([) - (I
(x.
< 2 ((E) -
(z, I)
<
- (=))] [2] y (x 0
Finally, combining I|W W (x))] S Ao. equation 3 and equation 1 yields::
W y" (z, 2 2M + 2 (I)2(E) - v 2)12
4
< 2M +
B BellW' x² (x1
2
< 2M +
K2
20

---

Published as a conference paper at ICLR 2026
From Assumption 3.1 for any fixed Ç. V2g v. {n) is unbiased with variance bounded by gg.1
By definition of y we have y (29(z, y (, 0 for all & and it follows that: n))
B 220(2, v (x, E), m)ll = ,ar
Taking the expectation over yields:
(gg. (x, 5
Combining the above results we have:
Big.nl/Vag(,; ( m)1 - 21 E (E,n)
(W) (x, ()12 + (1.
V2g(2, (x, (,, m)
2²
21 n.1
2M
20
K2
Since V29 (2, W. = 22g (() T and | S Ms we obtain:
Var(g.)) (V200 (Ir, W, m)] s BE...)) |2000 (2,, W,S, n)ll
(9)
s (E [|] 22g (b((5) &, ())
2
4L. M + 21 M
20 20 M
K2
L2 2
s 4M
1 12 40
o2
K2
which concludes the proof.
D PROOF OF THEOREM 4.4
In this proof, use the notations S. =, and 2 denote relations up constant. We will show that under assumptions 3.1 and & is well-conditioned, the assumptions I and 2 Gf et al. (202T) hold for fa and ga. Namely, we want to show:
Assumption D.1. For any x E Rd:, E(E.)) [ov (z, W.S. is X-strongly convex and L-smooth.
and Assumption D.2. The following hold:
(i) Vife is Lfe-Lipschite continuous, V2fa. is L continuous, V29* is Lgy Lipschitz continuous, Vi200 Lg continuous, V22go is Lggy-Lipschitz con- tinuous, all with respect to (z, W).
(ii) Vife. 22f0. V29e. Vizlo. and VinJa have variance bounded by a².
(iii) (2. [f(z, 1| < C.
Bie (o(2, W, || C2 gzy"
Under assumption 3.1 and if ④ is well-conditioned, Lemma C.2 gives E(g.)) [g+ (x. W.E. 7)] is umn (m (e)-strongly convex with respect W for any x Rd, Further, we have from Lemma C.4 that V294 (z. W, W, is L M3 -ipchiiz continuous in W for all fixed (x, &. n). Taking the expectation over (E, 17) we obtain:
V 2 (( loo (z, W, m)] V.E(s.)) Ioo (x', W -.nii]
||B 22 (z, W,C. V (x', w))ll
E(g,.) [/| V (z, W,&, 17) V29D (x', W El
S Lg. 33 (I|= 2' + II W'l)
where the first inequality holds since assumption 3.1 lmplies that V299 (x,, W. W, 11) unbiased and the first inequality uses Jensen's 's inequality. Therefore Eeg..) [gs (x, W, E, 1)) is Lg MM. for any fixed x E dR and assumption D.1 holds with A (c) and L T,g, Mg.
21

---

Published as a conference paper at ICLR 2026
Using the implicit-function theorem, the accuracy of the estimate of F& degrades linearly with the gap [W; (x;x)) Hence !|W; - [xxr))] cannot diverge and there exists Ån < W*
oo such that the iterates We satisfy [W (2,
Ag- In particular, this is holds for RSVRB as per Lemma 6 of [uo et al. (2021). Henceforth, we restrict our analysis to
{(z, W)
IR x Rd,xNo(t), ||W- W (=)
- } for the rest the proof.
D.2 (ii) hold fo and go for with Lipchitz constant L and uniform variance bound o² given in the table below.
Lemma C.4 and Lemma C.7 show that assumption D.2 (i)
h
L
r²
V Visa.
Ls
03 + 7.0
V2f4.
Lg
M3 00 L7700
V294.
1g.1M3.
4M (I 43 + Ø2 + gg.1)
V i2200=
M3 (0 (12,1)
22
Lg
M1 (o).2 12211)
Further, Lemma C.4 also gives that fo and 96 are L, and MggMMa-Lipshhie continu- in (z, W), respectively. It follows that that ((,)) for (x, W,C, |l I Ly and [[Vg [gv (a, w)) I Lgo.M.. Hence condition D.2 (iii) hold for fi and go with Cfv Ly. and Cany = Mg.
Therefore Theorem Guo et al. (202I) holds. Before stating it we first bound some quantities in term of Mg and my.
Since is well conditioned, we have Eip 2 molNate) Therefore:
Rg (x0))
Ee [(W (1ro (())) (E)))((())
Eg [tr (W (
tr (W [xo) (EEE)((E) (xo)) )
2 matr (W* ( (mro)
my [" (zo)
m I
For any (zo. Wo) and by the y strong convexity of g we have:
B(g,)) Ios (Io. Wo. E. m)] 2 E(c.m) (xo, W (2o). E, E) + 1 Bie..) (l) and thus, taking Wo
2
Ee (I1W"
<
E ((m loo (20, Wo.g.1) ( (xoo) E.
14
Big.n) g(20,
E. 0, min gxo. (.
A..0
Combining the above results we obtain:
|| (20) Eg (x))
ma
24 g.0
μ m
22

---

Published as a conference paper at ICLR 2026
From Lemma 2.2 in Ghadimi & Wang 2018), (x))) is Lipschitz continuous in with constant
Lw
Loy L,,1 M pmg
Additionally, VF is Lipschitz continuous in with constant
LiyLog +
Lig A
[iv + LigLog Ls
Lyzyy
LiuyLigu A2
Lggy Le +
Livy
LF = Liy +
+ Ls
x
A
X2
2 + Logy
Togu 12 + L.g Iogy Lugry + T Ligu
T.g I.gvv
Ls +
X²
A
M
M
M
X M +
+
mip
m
m
M
+
Using the notations of Guo al. 2021). have ōw: - ||, Wxoxl)] with W, Wo ToT
and:
Vif (zo, Wo))ll $ M
[0/v
S
Vefo- (xr, Wo))ll & M
E 6 gryguu
V 120 (oo, Wo))l? S M
E gum.ol
S
V 22 (200, Wo))l S M
E 18 gl.ul
E| V2ga. (No, Wo)) s Mt
where the first inequalities follows from the Lipschitz constants given in Lemma C.4 and the last holds given equation 9.
Theorem of Guo al. (202 finally give:
T
< Fo(wo) Fo(x*)
CE [ōw.o] Tr T
E
V For (12)
(10)
2(T + 1)
T
+ 00 85a,0 + 81 6929,0 + 6 ]omy.o]
O (In(T + 2))
T
?/r
23

---

Published as a conference paper at ICLR 2026
where for 1:
6C 12
6C C L2 fy
7
C
M
Co =
2 fr
+
gay A
99y
Ty
A²
X
m
C =
60 fy
M
C2
X2
m
60 X
C2
M
C3
yoy
m4
6C
M
C4
1
m
1
31g
M
4Co
4
T.2 9m
1
T.2
T
gay
T
M
max
TX
m
VT
m
7 min
8VCLW
16
L2 + L + f
+ L
+ L2
guu
M
3/2
2
M24 m
2, 6
(2((C) + C2 + C3
= max
16ChT
7LF
1) J
(co + 1)1/3
Here the bounds on C' and y are obtain after considering all 4 possible cases. We can also bound and 6w,0 S (1[W + | (xo))l)) z me
|| 2T. Mo. thus || S m.g
Substituting in equation
10 we finally obtain:
T
Fo( (x²)
Fg (1:)
+ CE [ów:o]
2(T +
TT
+ 16gg.0 + 811,0 + 818.0 + 8gzy.0 + Sgyv.o]
O (In(T + 2))
M 12 m
M 18 m m4
M m
M o (In(T + 2)))
T
In particular, following the analysis in Cutkosky & Orabona (2019).
the sample complexity is
1 (c))
(ol)(mo(e))
CHEBYSHEV SERIES: UNIFORM CONVERGENCE AND CONDITIONING
For completeness, recall the definitions of d-dimensional Chebyshev polynomial and the Bernstein ellipse.
Definition E.1. Let (ki, ka) E Nd be multi-index. The k-th d-dimensional Chebyshev
polynomial is defined as:
i: (EI,..,
E--,1 E
II Tr (5,)
where Th, (E,) = cos(k, arccos(E;)) is the Chebyshev polynomial of the first kind with degree ky in the j-th dimension.
24

---

Published as a conference paper at ICLR 2026
Definition E.2. The Bernstein ellipse with parameter p is the complex set defined as:
=EC: e00 pe
[0, [0, 2T)
Lemma E.3.
Under assumptions 3.1 (i) and condition (c.3) y (x, E) is real-analytic over for any fixed x E R
Proof. Recall that G(z, v, {) Bny-Faie [0 M.E. m)]l Under assumption 3.1 (ii), g is u-strongly
convex in y for any fixed (n) Thus, G u-strongly convex in for any fixed (z, {) and (a,E) the unique solution to V2G(z, {) = 0. Additionally, since G is real-analytic in (y, E) for all Rd is V2G. Define H (z, {) VzG(zz E). Then (xx y (z, E) 0 for all x e R Further, the strong convexity of G with respect to gives that 22H then use the analytic implicit function theorem obtain that, for any fixed unique function y (x.{) real-analytic over E and solution to H (z, y, E) = 0 for all g E E. By unicity, we must have y y² and follows that y" is real-analytic over for any fixed Rds
22 is invertible. We can R there exists
Lemma E.4.
Let f be an analytic function in [-1,1]m that is analytically continuable to the open region Ep delimited by the Bernstein ellipse with parameter E (1, e1/3./ where it satisfies [f(x) S M for all (Ep). Then for each le its Chebyshev coefficients satisfy
|axl S 2Mp
Ep
R
Proof. Let F
( Since f is analytic in Ep, F is also analytic in E, as the
f
composition of the two analytic functions 2 + (= + 1 and x + f(x). From Theorem 3.1 of Trefethen (2019), the Chebyshev coefficients are given by
2 F())d=
4g
Ti 1=
and
1
(1+1) F(z)dz, 4k: 2 1.
|=|=1
F' analytic in the closure of Ep. we can expand the contour to |2| = without changing the value of these integrals. Since [F(z)] I M for all E Ep and E (1, e e!/2] we obtain for 0:
2
1ool
1 F(z)dz
12|mp
M
| dz
J|=1=p
4M In(p)
2M
and similarly for all & 2 1:
10x
(1+Ak) F(z)dz
|
M
|2]
(1++k)
dz
π
|+|=p
2M p
Otherwise, expand the contour |2| for any p. giving the same bound for all p and thus also for = P. Therefore |ag| < 2MP-* holds for any k: 2 0.
25

---

Published as a conference paper at ICLR 2026
Lemma E.5.
Let f be an analytic function in [-1,1] that is analytically continuable to the open region E delimited by m-dimennsional Bernstein space I Ep with (1, and [f(z) s M for all R (ET))
Then the coefficients of the m-dimensional Chebychev expansion:
0C
m
= f(a)
II Tw,
by
ki
such that, for any kı, .... km 2
m
|aki....km
S M
II (2p kt)
Proof. Let R A R. (F.)) be the projection of Ft onto Rd. We begin by defining two classes of functions:
f: 1-1,1] + IR analytically continuable to E (M)
sup 1f(x)] s M
EER
(M)
/=1-1, - IR the Chebychev coefficients of satisfy |akt....kll S M (2p ki)
Let the hypothesis of induction be that the statement holds for a dimension - 1 S m. Namely, (M) S (M))))(MM) We want to show that (1) (M) C (M).
Let f() E (M). For any fixed (I1,..., 21-1) E 1, define the single- variable function: 1 (oi,...,, 1)] A (xi....,
1 -1-1, m1), Vay E [-1,1]
Note that since f() H()) we have in partieular for any fixed
R that SU, f(0) (x1,....... (f1....,m--)le)) I SuPEER; (x)) s M. Since f()) is jointly rnal-tnalytic
all its variables and can be continued analytically to EV. the mapping 21 + 1(0) (21,..., -1 [ai]
also real-analytic and can be continued analytically to E. for any .(..).,,-11)) E Ft
Applying Lemma E.4 we have that the coefficients of the Chebyshev expansion:
P -.. -.. 1......,--110 (x)]
Cha (1,,...,.111)))) (3z)-
satisfy
[cky (#), (#1...., .1-1) S 2Mp k2, Vki 2 0.
Since this hold for any fixed (II,...,,III)) R we have sup SUP Ica, (2:) S -M.
Further, because f() is jointly analytic in all its variables and can be continued analytically to E,, for any fixed dı, the mapping (Ii, .2211) f() (2),,..,,,,,,11 is also analytic and can be continued analytically to E By definition.
Ck (21,..., 1-11) 4
1" π
2
p (a 0)
26

---

Published as a conference paper at ICLR 2026
ck2 is analytic on |-1,1]|-1 and can be continued analytically E/-1 as integration preserves analyticity. Therefore, cb2 E (2Mp By the induction hypothesis, it follows that Cia E (2 Thus, each Ci2 can be expanded as:
Ckty (21, (.-1)
ak
k
The (2:)
1
k1-1=1
with
a Ak.....oo-..dll (2Mp ku
(2p k:)
M II k2) xm1
It follows that for any (I1, (#1,...,, 21) E 1-,
p (xI,..... 01) = 1(0 (II,.... 21 [2y]
Cki (II..... 2 1) (2))
1-1
Th. (x:)
(xi(
k==0
kg =0
1-1=0
1=1
Gkj
1
(1;
k =
k==
1=1
with Ak S M MI step.
(2p k1). This shows that f() pl) completing the induction
The initialization (1 = 1) of the induction reduces to Lemma E.4
We conclude by induction that:
(m) (M) C (M)
Lemma E.6.
Let f = 4om fn where
1-1,1] mm
R
fn
Ek. >k. aki...... km 11 Tx; ; Vn 2 1
and a satisfies for p >
|ak Amm
S M
(2p (t)
Vki...,,km.
km 2 0.
1=1
Then the residual rn = SUP2E[-1,11
1f(x) - fn (x)) is bounded by
m 1 (1 (1
rn S M
Proof. By definition, the remainder after truncation is
f(x) - fa(x)
Σ
Ts. (2:).
k1.... 20
3j kynn
27

---

Published as a conference paper at ICLR 2026
Since (x:)] S 1 for all 2, [-1,1], we have
Iu
sup
akk km
Tk, (x:)
#E{ =E[-1,1Jm 1,1mm
Si 20
1=1
3j s. ky2n
km...km 20 3j s.t. Ry2n
Since lak.........
S M 11 1 (2p k:), ). it follows that
On M Σ
II
(2p k1)
ki.....mmmm 201=1
3 s.t. ky>n
M
Σ
II
(2p
ki)
M
(2p
ki
01=
Km ======- 1=
11=0
km
0 xm
20
m
n
Σ
2p
M
2p
k=0
Since > 1 we have:
2p
p-1
k=0
for the full sum, and for the truncated sum.
1- (1/p)"
2p h 2.
P
k=0
Substituting this back into our bound, get:
2(1 ( -1/11111)))) m
Fn S M
p p-
p-1
2
M
[1- - (1/p))mm
p
which gives the desired result.
Proposition E.7. Let & be the hasis of de-dimensional Chebyshev polynomials and
N(2) = O (E
If assumption 3.1 and the conditions of Theorem 4.5 hold, then No is expressive with No(e)
N
V Lg.
assume without loss of generality that E\] [-1, Indeed, the domain can be normalized by defining a scaling mapping S = [-1, dd and replacing with S(E) in (CSBO) and (BO0 Under assumptions (.1iioonn333111 (ii) and condition (c.3) we have from Lemma E.3 that y" (æ, -) is real-analytic over E for any fixed x E Rd., Hence there exists p E 122 such that y (x, -) is analytically continuable to the closure of E,. the open region delimited by the de-dimensional Bernstein space I Epp- Since 1f (x..) is analytic the compact
Proof. Since =\t is bounded under condition (c.2)
28

---

Published as a conference paper at ICLR 2026
set Ep, it is in particular continuous and y" (at,)) -) is bounded on Ep by some constant M. For any j E [dy] Using Lemma E.5 y (z, admits the de-dimensional Chebyshev expansion:
de
(z,
Σ
Thi (E.)
Adg
Rdg
==1
where for any .i...., km 2 O,
dg M
( Waig
S
(2p h.).
Let Wt be such that its j-th row contains the elements of (l)) Then
y yo (W (x)
dg The (&:)
kae
ky =
Kidg =0
Lemma E.6 then yields for any n 2
de
sup ye (WT(),, EEE
25 (z, E) S M
p- (
[ 1 (11111100 (110)))))
(11)
Define:
de
1/dc
n(E) A - In
1- 11-
ē
p
(I(()) and N(ē) 2 n(t)ds
(12)
M dly
2
Note that N(ē) θ (In (1/2)
é - 0. Furthermore, for any number of basis functions
N 2 N(ž), we have at least n 1//dg 2 n(ē) clements per dimension. As the right hand side of equation 11 decreases in n, have for any n(ē):
غ Jay
sup EEE
yo (W (x), oj E)
Vj [dy]
Since this holds for any j E [dy), obtain:
sup
| (z) 5².
EE
Lemma E.8. Let AN) E NNN be zero-indexed matrix containing the unweighted scalar product of d-dimensional Chebyshev polynomials. Then Amin (A(N) S2 (N-1).
Proof. We first consider the I-dimensional case and define B Ruxn satisfying:
1 [ (z))
BG,
For any zero-indexed vector v E R we have:
Bv =
2 vay
(x)x)
1=0
1
viT((o)) dr
=
1 /
Σ
es cos(i arccos(x)) dx
2
29

---

Published as a conference paper at ICLR 2026
After substituting cos(0) and dr =00 obtain for 5 :
0.
Bv
2s cos(i0)
sin(0)d0
J
2 cos(10)
1
Σ
sin
1=0
(6)
Us cos(ii)
do
2
On one hand, we know from Fourier theory that
i
J
cos(10) cos(jo)
=fi=j=0
otherwise.
and thus
n-
2
R-1
Σ
Us cos(i0)
dg = TUp +
|1a
On the other hand, we have using Sauchy-Schwarte inequality:
2
2
Σ us cos(i8) do 2
d0 + I Mo.ju|oraamm
Σ o (i0)
d0
Σ 2s cos cos(
5
Ue cos( (10)
d0 + ||0||2 /
Σ cos (i0) do
10.6]U|==6601
Σ
2/ cos cos((i))
d0 + 20
Hence we obtain:
8
n2
2
Σ
Us cos(
d0
(
π 2
26n ||'112
and we conclude using sin (8) >
18 for any 10,1) that:
Σ U/ cos(1))) )²
2
sin
8
v. Bu
do
2
8
28n
||011
||0|12
16n
2
2
x-1 Therefore we obtain for all n E No that Amia (B) > cB In with cp
32
Suppose first that N = nd for some n E N We can decompose (NN) we obtain:
B. Using Lemma C.
(N) -
CB
d
IN
n
d
I
N
N
30

---

Published as a conference paper at ICLR 2026
Consider arbitrary N N", and N such that N E [(n 1)4 + 1, n.n" Since A(M) is principal submatrix of A(a"), the Eigenvalue Interlacing Theorem gives:
(A(OM) 2 Amin (A(a*)
Amin
h
nd
where the second inequality the result of the case N n and the last equality hold since
N E [[n- - 1)d + 1, n="].
We conclude that Amin (A(N)) 22 (NV
Proposition E.9. Let 4 be the basis of de di-diiensional Chebyshev polynomials. condition (c.l)
holds, then m+ (c) Ω Nole))
Proof. Under condition (c.l) we have that is finite or there exists > such that the density of Pe lower bounded by c on
Suppose first that = is finite. Then for any N < | we have that (+) spans R.V Thus there polynomials of distinct order can interpolate
exists CN > such that Mg = CN Since n point, we have (E) < [| Therefore, for any N E N we have Es 2 min Cn JN and in particular (c)
[o with min E m Oz.
Suppose now that the density of Fş lower bounded by e gon E. Then:
Dg = E [+)E)
= E L (E) de + /" (())((S) (dP(E) gdg)
From Lemma E.8 have Amnin (f', (E) d (1/N Additionally, (dI(()) (dc)
the product of positive term and rank matrix. Therefore = for any
we have:
Amin (E+) (1/N
and we conclude that (E) = (e))
Combining the above results, we now prove Theorem 4.5
Proof. Suppose that assumption 3.1 and the conditions of Theorem 4.5 hold. The first state- ment of the theorem follows from Proposition E.7 Indeed we have that +b is expressive with
and since N(E) O (n (E-))) we obtain Na(e) O (In ()- Since & encodes multivariate Chebyshev polynomials, we have 2. s 1 for any [N+( and thus (c) S (N+(c) O (c-))) The second statement directly follows from
(e) N
2K
L..0
Proposition E.9 where substituting No(e) 0 (In)) into mo(e) = Ω Nole) gives (c)))
Ω In de (c (c-
F DISCLOSURE OF LARGE LANGUAGE MODELS USAGE
LLMs were used solely improve the clarity and readability of the main text (e.g., grammar and phrasing). No technical content, proofs, or experimental results were generated or modified using L.Mss.
31


Reviews:
[{"review_id": "YXjNUY0xXZ", "reviewer": "Reviewer_dYLE", "summary": "This paper studies a contextual stochastic bilevel optimization (SBO) problem, where the lower-level objective depends on both a random context and the upper-level variable. Compared to standard SBO, the main challenge lies in estimating the hypergradient: a naive approach requires solving multiple lower-level problems and sampling from a conditional distribution for arbitrary contexts. To address these challenges, the authors map the context to a feature space via Chebyshev polynomial bases, and parametrize the lower-level solution as a linear function of the resulting feature vector. This reformulation converts the contextual SBO into a standard SBO that avoids the need for conditional sampling. The paper further identifies conditions under which the transformed problem retains the regularity of the original one and demonstrates how to construct an approximate solution to the contextual SBO from the standard SBO solution.", "questions": "In light of the weaknesses discussed above, I have the following clarifying questions: \n- The authors suggest that the assumptions in Theorem 4.5 ensure the Cheyshev polynomial basis is expressive. In particular, they assume the function $G(x,y,\\xi)$ is analytic in $(y, \\xi)$. Could the authors elaborate on how restrictive this assumption is? For instance, in my understanding, an analytic function is typically defined for continuous variables, so this assumption will not hold when the context space $\\Xi$ is discrete. \n- Could the authors provide a more quantitative estimate of the feature-space dimension $N_{\\Phi}(\\epsilon)$? Specifically, how does it scale with other problem parameters?\n- I also find the definitions of feature map and expressive basis in Definitions 3.3 and 3.4 somewhat dense. To improve readability, it would be helpful to include concrete examples that illustrate these definitions.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- **Originality**: This paper introduces tools from approximation theory to tackle contextual SBO. To the best of my knowledge, this has not been explored in the existing literature. \n- **Significance**: The proposed method yields a simple reformulation of the original problem and eliminates the need for a conditional sampling oracle. Under suitable assumptions, it also improves the sample complexity for finding a stationary solution of the context SBO from the previously known $\\tilde{O}(\\epsilon^{-4})$ to $\\tilde{O}(\\epsilon^{-3})$.", "weaknesses": "- A central question for the proposed approach is how accurately the reformulated SBO problem approximates the original contextual SBO. In my view, this point is not clearly articulated in the paper; instead, much of the technical complexity is deferred to the notion of an expressive basis (Definition 3.4). Specifically, Definition 3.4 assumes that the approximation error can be made arbitrarily small by increasing the number of basis functions, but it is unclear to me whether this is always achievable in practice. Intuitively, to parametrize the lower-level solution $y^*(x,\\xi)$ as a linear map of the context features, some structural assumptions on the lower-level objective are needed, yet such assumptions are not explicitly discussed in the paper. \n- Another concern is that, after reformulation, the dimensionality of the lower-level subproblem increases from $d_y$ to $d_y \\times N_{\\Phi}(\\epsilon)$. To achieve a faithful approximation of the original contextual problem, $N_{\\Phi}(\\epsilon)$ may need to be large, potentially leading to significant computational overhead. In such cases, the reformulated approach may not offer a clear advantage over directly solving multiple lower-level subproblems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9aLHCxEyiW", "reviewer": "Reviewer_7i2v", "summary": "This paper studied the contextual stochastic bilevel optimization and proposed a novel method by approximating the lower-level solution using expressive basis functions. In this way, the contextual stochastic bilevel optimization problem is transferred back to standard stochastic bilevel optimization problem and can be solved by standard bilevel methods with enhanced convergence rate. This paper provided the sufficient conditions to make the approximation errors from the basis expression small and demonstrated the Chebyshev polynomial satisfies those conditions. Numerical experiments verify the effectiveness of the proposed methods.", "questions": "1. In Line 281, I don’t see why a small minimum eigenvalue implies a low-dimensional subspace. Shouldn’t the effective dimension be driven by the number of large eigenvalues instead? \n2. Numerical complexity of calculating the basis weight matrix when dimension is high. \n3. Missing references on first-order and variance reduction based bilevel methods: \n\n[1] On penalty-based bilevel gradient descent method. H Shen, T Chen. ICML 2023.\n \n[2] A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, Thomas Moreau. NeurIPS 2022. \n\n[3] Provably Faster Algorithms for Bilevel Optimization. Junjie Yang, Kaiyi Ji, Yingbin Liang. NeurIPS 2021.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Using an expressive basis to represent the context space is novel and effective, especially when the space is finite, as in predominate contextual stochastic optimization applications like meta-learning. \n2. This paper also offers two effective basis: Chebyshev and Fourier polynomial, which has been studied in approximation theory but have not be leveraged into bilevel optimization. The strategy has also been proved effective in experiments. \n3. The representation improves the convergence rate of existing literature on contextual bilevel optimization and matches that of stochastic bilevel optimization.", "weaknesses": "1. The proposed expressive basis seems only effective when the dimension of contextual variable is finite or has bounded support with non-vanishing density. But the authors also claim that meta-learning and distributionally robust optimization on the compact sets satisfy these conditions. \n2. It would be valuable to quantify the error introduced by vanishing densities that violate the assumption, to indicate how sensitive the method is on general contextual bilevel problems. \n3. In theory, how should $N_\\Phi$ scale with $\\epsilon$? The analysis suggests $N_\\Phi$ should be large. But in practice, $N=3$ gives a satisfactory result. Does that mean the analysis is not tight for problems with special structures? Could you comment on what determines $N$ and when theory predicts that small $N$ is enough?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PVytawnaIb", "reviewer": "Reviewer_yLsY", "summary": "The paper focuses on Contextual Stochastic Bilevel Optimization (CSBO) and proposes a reduction framework that approximates lower-level solutions with expressive basis functions, thereby decoupling the lower-level dependence on context. It formalizes the relationship between CSBO and standard SBO and makes it possible to achieve $\\(\\epsilon\\)$-stationarity with near-optimal sample complexity \n$\\(\\tilde{\\mathcal{O}}(\\epsilon^{-3})\\)$. Experiments on inverse problems and hyperparameter tuning demonstrate the effectiveness of the method.", "questions": "1. Although the paper achieves the near-optimal sample complexity $\\tilde{\\mathcal{O}}(\\epsilon^{-3})$, “Drawback 1” noted around line 80 appears unresolved. Please clarify what gap remains, whether it is fundamental or technical, and how the reduction might be extended to close it. \n\n2. The experiments compare primarily against \\textsc{StocBiO}. Why were other SBO algorithms excluded? Is it straightforward to plug your reduction into alternative SBO solvers (e.g., variance-reduced or momentum-based methods)? A minimal example illustrating such integration would be helpful.\n\n3. A minor suggestion: please use \\citet{} and \\citep{} appropriately to improve readability.\n\n4. See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a reduction framework for CSBO that leverages the efficiency of existing SBO algorithms and rigorously establishes the relationship between CSBO and SBO.\n\n2. The presentation is clear and well structured.", "weaknesses": "1. The theoretical analysis hinges on a $\\mu$-strongly convex lower-level problem. \n\n2. The treatment of high-dimensional scenarios and alternative basis functions(e.g., neural networks) is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "06LDy0VmBh", "reviewer": "Reviewer_YLFf", "summary": "This paper reduces the contextual stochastic bilevel optimization (CSBO) to standard stochastic bilevel optimization (SBO) via a function approximation characterized as a linear combination of basis functions. Under certain conditions, the CSBO and SBO have the same complexity of finding small hypergradient. Numerical experiments on inverse optimization and hyperparameter optimization seem to show the effectiveness of the proposed algorithm.", "questions": "See the weakness section.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea of reduction from CSBO to SBO is novel. To the best of my knowledge, this aspect is new in the literature.\n2. The presentation of the paper is clear.", "weaknesses": "1. The conditions required in Theorem 4.5 (c.1, c.2, c.3) are too strong. For example, as the authors described in line 68-line 69, the approach of Guo et al. 2021 is not amenable to settings where $\\xi$ is continuous. However the condition c.1 also requires $\\xi$ is discrete with finite cardinality. Therefore, it is unclear how this paper improves over Guo et al. 2021. Since these conditions are crucial to keep the complexity of CSBO the same as the SBO, this is a significant weakness. I suggest the authors to include a table to have a comprehensive comparison of this paper versus other baselines.\n\n2. It is unclear the relevance of the results in machine learning community. Are there any practical machine learning examples satisfying conditions (c.1, c.2, c.3), and using this paper's algorithm can provably improve state-of-the-art bilevel optimization baselines? In addition, what if these conditions do not hold? It may significantly increase the complexity of the algorithm.\n\n3. The experimental results are very weak. It is only tested on toy problems at small scale (e.g., MNIST dataset). In addition, the only baseline the paper considered was stocBiO, but there are lots of other bilevel optimization baselines which are missed.\n\n4. The formulation used in the task of hyperparameter optimization (Section 5.2) is not necessarily relevant in machine learning. For example, there are many formulations for the hyperparameter optimization tasks in the literature which use SBO instead of CSBO. Why the CSBO formula (5) is better?\n\n5. Using fixed basis function is not necessarily good. The authors do not consider learned basis functions, which may yield stronger approximation guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)