Learning Theory for Kernel Bilevel Optimization
Authors: Fares El Khoury
Edouard Pauwels
Samuel Vaiter
Michael Arbel
Venue: NeurIPS 2025 poster ()
Keywords: bilevel optimization
kernel methods
learning theory
empirical process theory
U-statistic
generalization error bounds
Primary area: theory
TL;DR: We provide generalization error bounds for bilevel optimization problems where the inner objective is minimized over a reproducing kernel Hilbert space.

Abstract: Bilevel optimization has emerged as a technique for addressing a wide range of machine learning problems that involve an outer objective implicitly determined by the minimizer of an inner problem. While prior works have primarily focused on the parametric setting, a learning-theoretic foundation for bilevel optimization in the nonparametric case remains relatively unexplored. In this paper, we take a first step toward bridging this gap by studying Kernel Bilevel Optimization (KBO), where the inner objective is optimized over a reproducing kernel Hilbert space. This setting enables rich function approximation while providing a foundation for rigorous theoretical analysis. In this context, we derive novel finite-sample generalization bounds for KBO, leveraging tools from empirical process theory. These bounds further allow us to assess the statistical accuracy of gradient-based methods applied to the empirical discretization of KBO. We numerically illustrate our theoretical findings on a synthetic instrumental variable regression task.

Learning Theory for Kernel Bilevel Optimization
Fares EI Khoury" Université Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
Edouard Pauwels Toulouse School of Economies, Université Toulouse Capitole, 31080 Toulouse, France
Samuel Vaiter CNRS & Université Côte d' Azur, Laboratoire A. Dieudonné, 06108 Nice, France
Michael Arbel
Université Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
Abstract
Bilevel optimization has emerged as technique for addressing a wide range of machine learning problems that involve outer objective implicitly determined by the minimizer of an inner problem. While prior works have primarily focused on the parametric setting, gearning-theoreti foundation for bilevel optimization in the nonparametric case remains relatively unexplored. In this paper, we take a first step toward bridging this gap by studying Kernel Bilevel Optimization (KBO), where the inner objective is optimized over reproducing kernel Hilbert space. This setting enables rich function approximation while providing a foundation for rigorous theoretical analysis. In this context, we derive novel finite-sample generalization bounds for KBO, leveraging tools from empirical process theory. These bounds further allow us to assess the statistical accuracy of gradient- based methods applied to the empirical discretization of KBO. We numerically illustrate our theoretical findings on synthetic instrumental variable regression task.
Introduction
Bilevel optimization involves a nested structure where one optimization problem, called outer- level, is constrained by the solution of another one, called inner-level [19]. This formulation has found applications in a broad spectrum of machine learning fields, including hyperparameter tuning [43, 13, 28], meta-learning [14, 59], inverse problems [34], and reinforcement learning [35, 48], making it powerful tool in theoretical and practical contexts. Its widespread use naturally raises fundamental questions about the generalization properties of models learned through this procedure as the number of data samples increases. Several existing works have studied the generalization and convergence of bilevel algorithms under the assumption that the inner-level problem is strongly convex and that its parameters lie in a finite -intensiini space. These include analyses of the convergence of stochastic bilevel optimization algorithms [3, 24, 29, 38] and approaches based algorithmic stability [7, 78). The strong convexity assumption ensures a unique inner-level solution, which is crucial for stability and convergence analysis in bilevel optimization. Moreover, restricting the inner- level parameters to a finite-dimensional space does not cover possibly richer infinite-dimensionn spaces, as in kernel methods, where the parameter's dimension may grow with the sample size. This sample size dependence in nonparametric methods poses additional challenges as solutions different sample sizes are not directly comparable. In contrast, the finite-dimensional setting, generalization bounds can be derived by quantifying the convergence of inner-level finite-sanee sample solutions toward the infinite samples population solution limit, within fixed Euclidean space.
"Correspondence to: fares. el el- a1-Xhoury@inria..tt
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Albeit theoretically convenient, strong convexity and finite dinntesdiiniioallity limit models expressive- ness, restricting them to linear functions. Moving beyond linear models requires either relaxing the strong convexity assumption to accommodate more expressive models, such as deep neural networks [30], or considering nonparametric bilevel problems, where the inner-level variable lies in an expres- sive infinite-dimensionn function space, such as Reproducing Kernel Hilbert Space (RKHS) [63]. Early works in bilevel optimization for machine learning followed the latter approach, developing methods for hyperparameter selection in kernel-based models [39, 41J. These works leverage the representer theorem [64] to transform the infinite-dimensional problem into a fimite-dimensional one, with dimension depending on the sample size. However, they do not address how sample size impacts generalization. Another line of research instead focuses on relaxing the strong convexity assumption, proposing bilevel algorithms in the absence of convexity [4, 42, 66]. Yet, non-convex bilevel optimization is a very hard problem in general [47, 4, 17], and strong generalization guarantees in this setring remain out of reach due to instabilities of the inner-level solutions. Overall, learning theory for bilevel problems beyond the strongly convex parametric setting is essentially lacking.
In the present work, we take an initial step toward developing learning theory that goes beyond the finite-dimensional setting. Specifically, we propose to study Kernel Bilevel Optimization (KBO) problems, where the inner objective Lin : Rd x H + R finds an optimal inner solution h&g in an RKHS H. for given parameter w in Rd while the outer objective Lout Rd x H. + R optimizes the parameter w over a closed subset of TRd, given the inner solution h::
min F(w) == Lw, h() s.t. WEC
h = arg min Lin (w, h).
(KBO)
hCH
In particular, we focus on objectives that are expectations of point-wiss losses, a common setting in learning theory. RKHS provides natural framework to study learning-theoreee arguments, and has been instrumental for many fruitful results in pattern recognition and machine learning. They allow to describe very expressive non-linear models with simple and stable algorithms,, while enabling a rich statistical analysis and featuring adaptivity to the regularity of the population problem [65, 63, 33). Our choice is also motivated by the relevance of kernel methods, even in the deep learning era. They remain competitive for some prediction problems, such as those involving physics [26, 44]. Additionally, the mathematics of kernel methods are useful to describe the limiting behavior of deep network training for very large models [37, 11]. In this limit, the problem becomes (strongly) convex in an parameterizations, a major bottleneck in the analysis of such models. This point of view was leveraged by Petrulionyté et al. [58] who introduced functional bilevel optimization, and our setting can be seen as special case for which the underlying function space is an RKHS. From a practical perspective, our setting is amenable to first-order methods using implicit differentiation techniques [31, 6, 15).
function space, simplifying the difficulties of non-convex model
Contributions. We leverage empirical process theory and its extension to U-processes [67] to derive uniform generalization bounds for the value function of (KBO), quantifying the discrepancy between F and its plug-in estimator F in terms of both their values and gradients. Classical empirical process results [72] do not directly apply here, as our functional setting involves processes taking values in an space rather than real numbers. To address this, we exploit the RKHS structure to represent the resulting error terms as real-valued U-processes, enabling the use of results from Sherman [67]. The control in terms of gradients is crucial to study first-order optimization methods, since F is typically non-convex and iterative methods seek to find approximate critical points where ||V is small. Our result relies on an equivalence we establish between V and a plug-in statistical estimate of VJF that more amenable to a statistical analysis. We then use our uniform bounds to provide generalization guarantees for grudient descent and projected gradient descent applied to F. Under specific assumptions, we show convergence rates for sub-optimality measures that depend on the sample sizes and the number of algorithmic iterations. This illustrates the practical relevance of our generalization bounds on simple bilevel algorithms. For large number of steps, gradient algorithms applicd to the empirical (KBO) find approximate critical points of the population (KBO) up to statistical error which we control.
Organization of the paper. In Section 2. we describe (KBO), give two application examples, and explain implicit differentiation in an RKHS. In Section 3, we present the empirical (KBO) and state our first main result on the gradient of its value function. Section provides uniform generalization bounds for (KBO), with applications to bilevel gradient methods, as well as a sketch of the proof of our main result. Finally, Section 5, we illustrate our theoretical findings with experiments on synthetic data for the instrumental variable regression problem.

---

2 Kernel bilevel optimization
2.1 Problem formulation
We consider the (KBO) problem with RKHS H. which is space of real-valued functions defined on a Borel input space X C. IR and associated with a reproducing kernel K : X x X + R. We interested, in particular, in (regularized) objectives expressed as expectations of point-wise loss functions, a formulation widely adopted in machine learning as it allows the loss functions to represent the average performance over some data distribution. Specifically, given two probability distributions P and Q supported on X' x y for some target space y C IRS, we consider objectives of the form:
Lout(w, (w, h)) = EG oou (w, h()), [in(w, h) = Ee [win h(z), y)1 + 2 11
where ii and lout 12 R R + E represent the inner and outer point-wise loss functions, A > O is the regularization parameter which is fixed through this work, and || Il denotes the norm in the RKHS H. The regularization term in Lin often used in practice to prevent overfitting by penalizing overly complex models. In our setting, it ensures strong convexity of h + Lin (w, h) under mild assumptions on lin. which will be critical to leverage functional implicit differentiation.
Assumptions. Through the paper, we make the following five assumptions to derive generalization bounds while retaining simple and modular presentation.
(A) (Measurability of K). K is measurable on X' x X.
(B) (Boundedness of K). There exists constant >> 0 such that K (2,z) K. for any x X. (C) (Compactness of y). The subset y of R7 is compact.
(D) (Regularity of C.n and Cout). The functions Lin and lout are of class C jointly in their first two arguments (4r, v), and their derivatives are jointly continuous in (w, U, y)-
(E) (Convexity of (. For any (w, v) E R2 x 129 the map e + Lin (w, v, y) is convex.
Assumptions (A) and (B) on K hold for wide class of kernels, such as the Gaussian, Laplacian, and Matérn [61] kernels. They also hold if K is Mercer kernel [50], i.e., a continuous, positive-definit kernel on a compact domain X. Specifically, a kernel built using neural network features, e.g., neural tangent kernel [37], satisfies these assumptions on the space of images, which is compact since the pixel values have bounded range. Assumption (C) on ) is a mild assumption that holds in most supervised learning applications. such as classification where y is finite, or cases where V = [0. 1js, enabling the representation of complex data, like images. Assumption (D) on the point-wise objectives is a mild regularity assumption, which is met for the most commonly used loss functions in practice, including the squared loss, logistic loss, cross-entropy loss, and KI. divergence. Finally, Assumption (E) is essential to ensure the existence and uniqueness of a smooth minimizer hg. is a relatively weak assumption that was recently considered in [58] in the context of functional bilevel optimization, and that holds in many cases of interest, as discussed in Section 2.2.
Remark 2.1. Assumptions (B) to (D) can be relaxed at the expense of weaker yet more technical assumptions, such as finite moment assumptions on IP and Q. and suitable polynomial growth of the kernel and some partial derivatives of bm and lout. It is also sufficient to require that Assumption (D) holds on 21 RR Rt where t/ is an open neighborhood of and that Assumption (E) holds for any E C and E V. We prefer to keep these stronger yet simpler assumptions for clarity.
2.2 Examples of (KBO) in machine learning
To illustrate the relevance of (KBO), we consider two examples that highlight its applicability.
Hyperparameter selection under distribution shift. In this application, the aim is to select the best hyperparameters for a machine learning model, e.g., regularization parameters, while accounting for distribution shift between the training and test data, i.e., when the training and test data distributions Dirain and Diest are different [57, 28). This can be viewed as an instance of (KBO) when using models in an RKHS. At the inner-level, the model h is trained to minimize the regularized training squared error loss, with the hyperparameter w > representing the weight for the data fitting term. At the outer-level, the task is to select the hyperparameter that maximizes the model's 's performance on the
3

---

distribution-shiffee test data. Both inner and outer objectives can thus be formulated as:
1 Low h)) B [M(a) - -w"] Lin(w: h)) -
2 (a..))>Dnn [b(x)) u² m ||
This formulation could be used for domain adaptation [12] or domain generalization [73] to choose hyperparametees that perform well on the distribution-shiitedd test data.
Instrumental variable regression. It is technique used address endogeneity in statistical modeling by leveraging instruments to estimate causal relationships [53]. The goal is to estimate a function + (t) parameterized by vector w. that satisfies y (t) + e, where y R is the observed outcome, t is the treatment, and is the eπror term. The key issue is that is endogenous, which means that it correlated with e, making direct regression inconsistent. Indeed, such correlation leads to biased estimates of fm (1) as the assumption of exogeneity, i.e., independence of and c, is violated. To resolve this, one can use an instrumental variable x, uncorrelated with e but correlated with i. to recover the relationship between y and without being directly affected by the bias introduced by c, typically via two-stage least squares regression [68. 51]. As shown in [58], this approach can be naturally expressed as bilevel problem with inner and outer objectives of the form:
Lout (w, h) = Ex.v [M(()) uP²
Lmn(w, h) = 2 En,, [lh(z)) - fu(()) +
1
2 II
2
where can be chosen to be in an RKHS to allow flexibility in the estimation while retaining uniqueness of the solution has a key property in bilevel optimization.
2.3 Implicit differentiation in an RKHS
stationarity measure in (KBO) is the gradient F(w)) of the value function F. Computing V.(ww. however, is challenging and will be addressed in this section. At a high level, our approach proceeds in two steps. First, we derive an abstract, a priori intractable, expression for VF(Ww) using implicit differentiation in an RKHS, which is the main source of difficulty. Then, we leverage the structure of our problem to reformulate the gradient in Proposition 2.2 using the solution of regression problem in the RKHS (the adjoint problem). This more concrete formulation can be approximated with finite samples and will later serve as the foundation of our statistical analysis. Formally, evaluating the gradient requires computing the Jacobian ou which can be viewed as a linear operator from H to Rd Indeed, hü depends implicitly on w. A key ingredient for computing hut is the implicit function theorem [36]. which guarantees the differentiability of the implicit function w + hy and allows characterizing hu as the unique solution of a linear system of the form:
Ln Liin (w, h() + Ouh 07 Tin (w, ht) = 0,
where Of Lin (w, htt is an operator from H. itself representing the Hessian of Lin w.r.t h, while 22 Lin h2) is an operator from H to Rd representing the cross derivatives of Lin w.r.t. to w and h. Applying such result requires h +> (w, to be Fréchet differentiable with invertible Hessian operator and jointly Fréchet differentiable gradient map (w, h) - Ön Lin (w, h). All these properties are satisfied in our setting under Assumptions (A) to (E) as shown in Propositions B.1 to B.3 of Appendix B.I. Furthermore, when Lout is Fréchet differentiable, which is our case under Assumptions (A) to (D) (Proposition B. of Appendix I), then by composition with w + (w, hw). the map + F(w) must also be differentiable with gradient obtained using the chain rule:
VF(w)= = Loue (+)) + A, Loua (w, hw)
The above expression for the gradient is intractable as it involves abstract operators, namely the derivatives On 07 and F the last two of which arise when replacing h by its expression in
Equation (1). In Proposition 2.2 below, we derive an explicit expression for V.((W) which exploits the particular structure of the objectives Lin and Lout as expectations of point-wise losses.
Proposition 2.2 (Expression of the total gradient). Under Assumptions (A) to (E), F is differentiable on I2, with grudient F.W),, for any w E [Rd, given by:
F((w) = Eg [ (w, (z), y)l + Ep Li (w.
(2)
where the adjoint function at E H is the unique minimizer of a strongly convex quadratic objective a + Lodj (w, a) defined on 7 as:
1 _Bp [l (w, (z). az)) + Eg [oll (w, (z))),, v) a(x)] + A
Lody (w,a) =
2/2 lalb, (3)
2
2
4

---

where But and Out are the first-order partial derivatives of lout w.r.t. w and v, while 0e in and in denote the second-order partial derivatives of lin w.r.f. w and
Proposition 2.2 is proved in Appendix and relies essentially on proving Bochner's integrability [25, Definition 1, Chapter 2] of some suitable operators H. and then applying Lebesgue's 's dominated convergence theorem for Bochner's s integral [25, Theorem 3, Chapter 2] to interchange derivatives and expectations. The expression in Proposition 2.2 provides natural way for approximating V F.Ww) by estimating all expectations using finite-sample averages, as we further discuss in Section 3.
3 Fimite-sample approximation of (KBO)
In this section, we consider an approximation of (KBO) when only a finite number of i.i.d. samples (z,, Missinn and (zy. B/ Jis/sm from and Q are available. This set- ting is ubiquitous in machine learning as it allows finding tractable approximate solutions to the original problem. As we are interested in approximately solving (KBO) using gradient methods, our focus here is to derive estimators for both the value function F(w) and its gradient V.(W), whose generalization properties will be studied in Section 4.
Plug-in estimation
F
V: diff
V: diff
VF
VF
Plug-in in estimation
A commutative diagram illus- trating that plug-in in statistical estimation and differentiation can be interchanged for F and f resulting in single gradi- ent estimator.
Figure I:
In Section 3.1, we follow a commonly used approach of first deriving a plug-in estimator f of the value function, then considering its gradient V.(ww) an approximation to V.(W). In Section 3.2, we show that this approximation is equivalent to a second estimator, more amenable to statistical analysis, obtained by directly computing plug-in estimator of V.F based on its expression in Equation (2). Figure! summarizes such equivalence.
3.1 Value function: plug-in estimator and its gradient
A natural approach for finding approximate solutions to (KBO) is to consider an approximate problem obtained after replacing the objectives Tin and Toout by their empirical approximations T.jn and Toout:
A
Boou (w, h)
lout (w, M(B)), (s))) Tein (w, h) = 72 Σ lnn (w, ((Ta), ys) + P
m
A plug-in estimator F(w) is then obtained by first finding solution dn minimizing h -> Brin (ws, lt), that meant approximate the optimal inner solution his and subsequently plugging into Toout This procedure results in the following empirical version of (KBO):
min F(w) = Lowe(w, hw) s.t. hws = arg min Lin (w, h). WEC
kEH
The inner problem still requires optimizing over a, potentially infiniteddimensional, RKHS. However, its finite-sum structure allows equivalently expressing it as finite-dimensional bilevel optimization, by application of the so-called representer theorem [64]:
m
min F(w) wEC
love (w, (K 9w), Uj)
m
(KBO)
s.t. Pu = arg min
Σ (n (K 7); vi) + 2 Ky.
YER"
Here, K E Ruxn and K E I xx are matrices containing the pairwise kernel similarities between the data points, i.e., K, = K (x,,, x and K, == K(ã,, while y is parameter vector in IR" repre- senting the inner-level variables. The optimal solution 7u enables recovering the prediction function he by linearly combining kernel evaluations at inner-level samples, i.e., ho = >m ( :). The formulation in (KBO) enables deriving an expression for the gradient VF(w) in terms of
5

---

the Jacobian m. by direct application of the chain rule. Unlike awh which requires solving the feinittedimensionaal linear system Equation (1), 0=hm can be obtained by solving a finite- dimensional linear system using the implicit function theorem (see Proposition C.1 of Appendix C). Hence, (KBO) falls into a class of optimization problems for which a rich body of literature has proposed practical and scalable algorithms, leveraging the expression of V.(ww) [38, 3, 24]. Solving (KBO) thus provides a practical way to approximate the solution of the original population problem (KBO), as proposed by several prior works on bilevel optimization involving kernel methods [39, 41].
Non-applicability of existing results. Despite its practical advantages, the above approach yields algorithms that are not directly amenable to a statistical analysis. The key challenge is to be able to control the approximation error between the true gradient V.F(w) and its approximation VF(w) as the sample sizes n and m increase. Existing statistical analyses for bilevel optimization, such as [7. 78]. consider objectives that are expectations finite sums of point-wise losses, we do here. While these results can be applied to our setting for each fixed nt they do not capture the generalization behavior as grows. In particular, they require both the inner- and outer-level parameters to lie in spaces of fixed dimensions, that are independent of n and m. That is because these parameters are expected converge to some fixed vectors as n. m + +00. In contrast, in our setting, the inner-level parameter lies in R", so its dimension grows with n and is not expected to converge to any well-defined object. Existing non-kernel generalization bounds are discussed in Appendix A.
Relation to instrumental variable regression. Our formulation is related to instrumental variable regression, which is special case, but differs in that we study regularized inner problems with fixed X, independent of the sample sizes. In contrast, the instrumental variable regression literature typically considers un-regularized population problems (A = 0). for which closed-form expression of the inner minimizer is available [32, 68, 76, 45]. Our contribution lies in an orthogonal direction: we handle more general inner objectives, for which even the analysis of regularized problems raises new obstacles that had not been tackled before. Moreover, some prior works have provided convergence rates in the instrumental variable regression setting [1, 2, 22, 23]. Yet, these studies focus on asymptotic results with sieve estimators, meanwhile we leverage the RKHS structure to provide finite- sample bounds. More recently, Meunier et al. [51] established minimax optimal rates under source assumptions by exploiting bounds for vector-valued kernel ridge regression [46] via a spectral filtering technique [52]. However, this approach not applicable to our case, as requires the losses to be quadratic in w. as further discussed in Appendix A.
Next, we provide an equivalent expression for V V.w,,, essential for our analysis in Section 4.
3.2 Plug-in estimator of the total gradient
We now consider an priori different approach for approximating the total gradient F based on direct plug-in estimation from Equation (2), and show that it recovers the previously introduced estimator (.W)). Such approach consists in replacing all expectations in Equation (2) by empirical averages, then replacing h", and a by their fimite-sample estimates hnw and a... This yields the following estimator of the total gradient:
1 m Σ Osloullw, he
1 71
VF(W)=
+
(w, (.)
(4)
Just as in Section 3.1, AC can be estimated by Aw the minimizer of the empirical objective h + Lin (wr, h). Similarly, oz can be approximated by aw. the minimizer of a + Lnndy (w, a) defined as:
Trads (w, a)
1 x 2n
Σ of (ws, (aa)) (x:) + m
1
Σ
m
Oolone (we (2.). + Ialli
(5) which serves as the empirical counterpart of the adjoint objective Ludi given in Equation (3). Both functions h. and ب can be expressed linear combinations of kernel evaluations with some given parameter vectors whose dimensions increase with the sample size (see Proposition C. for An and Lemma C.2 for a.. both in Appendix C). However, these parameters are not required to compute the plug-in estimator V FWW in Equation (4), since only the function values of h. and d., are needed.

---

This property is precisely what makes VF(w) suitable for a statistical analysis. Indeed, its estimation error depends on the approximation errors of h. and بي which always belong to the same space H regardless of the sample size, and are expected to approach their population counterparts. This contrasts with V.Www) obtained by implicit differentiation, whose analysis would need controlling space as - +00.
the behavior of the vector % that resides a growing-dimensionn
The next proposition establishes a link between practical applications and thcoretical analysis by demonstrating that, surprisingly, both estimators F(()) and V. ((w)) are precisely equal.
Proposition 3.1. Under Assumptions (A) to (E), the gradient V V (w)) of the plug-in in estimator F(w)
of F(w) defined in (KBO) is equal to the plug-in estimator FW() of the total gradient F.W))) introduced in Equation (4).
Proposition 3.1 is proved in Appendix C and relies on application of the representer theorem [64] to provide explicit expressions for both estimators in terms of Yw. kernel matrices K and K and partial derivatives of the point-wise objectives in and fout. Both expressions are then shown be equal using optimality conditions on the parameters defining سي. The result in Proposition 3.1 precisely says that the operations of differentiation and plug-in estimation commute the case of (KBO). Such commutativity property does not necessarily hold anymore if one considers spaces other than an RKHS, such as L2 [58, Appendix FJ. The main difficulty arises from the argmin constraint and the use of implicit differentiation, which may introduce non-linear dependencies between inner- and outer-level variables, making the exchange of differentiation and discretization nontrivial. Next, we
leverage the expression of the plug-in estimator F(w)) to provide generalization bounds.
4 Generalization bounds for (KBO)
In this section, we present our main result: a maximal inequality that controls how well both F and V approximated by their empirical counterparts, uniformly over compact subset Q of Id..
4.1 Maximal inequalities for (KBO)
The following theorem provides finite-sample bounds on the uniform approximation errors on the objective and its gradient in expectation over both inner- and outer-level samples.
Theorem 4.1 (Maximal inequalities). Fix any compact subset Ω of 1R Under Assumptions (A) to (E), the following maximal inequalities hold:
-(w) F(w)] s (
1 Vn
VF(w)) - -FWW)- sc
(c
sup WES
sup LWE
Vn
where the expectation is taken over the finite samples, and is a constant that depends only on St the dimension d, the regularization parameter X, K, and local upper bounds on Li Lout, and their partial derivatives over suitable compact sets.
Theorem 4.1 states that the estimation error can be decomposed into two contributions each resulting from finite-sample approximation of Lin and Lout with a parametric rate of 1/vm and 1/vo up to constant factor C. We provide a detailed expression for the constant in Theorem E.7 of Appendix The restriction to compact subset f instead of the whole space Id allows controlling the complexity of some function classes indexed by the parameter w. Without further assumptions on the objectives, we obtain constant C' that can grow with the diameter of the subset Ω
Role of X. The regularization parameter À simultaneously controls the strong convexity of the inner objective (see Proposition B.3 of Appendix B)),, the boundedness and Lipschitz continuity of the inner solutions (see Appendix 1.1), the smoothness of the outer objective (see Proposition D.4 of
Appendix D.2), the modulus of continuity of Lin. Lins Louts Lout and their partial derivatives (see Appendix E. and maximal inequalities for certain processes (see Appendix E.2). Larger values of yield smoother problems that are faster to optimize with larger step sizes, but introduce a larger statistical bias, while smaller values of À reduce bias but make optimization and generalization more delicate, with the error tending to +00 as - O. Selecting therefore involves trade-off between bias (regularized vs un-regularized problems), variance (finite sample population, as
7

---

done in our study), and optimization efficiency (step size). Under our assumptions, the dependence of the constants on cannot be quantified. precluding generalization guarantees as - 0. Stronger assumptions are required to obtain quantitative control on X.
Probabilistic and variance bounds. The most difficult quantity control is the expectation of the maximal differences, which we have established. Once this expectation is bounded, high-probability bound on the maximal differences can be derived via Markov's inequality. Moreover, since these differences are bounded (see Proposition E.4), we can also bound their variance. Indeed, let Z E [0, =] be a random variable representing the maximal difference between F or VFF and their respective plug-in estimators. Then. Zz) S [[[Z/2]] - B[Z/2], which implies that Var(Z) S =B|Z].
We outline the general proof strategy for Theorem 4.1 in the following section, with a full proof provided in Appendix E.
4.2 General proof strategy for Theorem 4.1
The main strategy behind the proof of Theorem 4. in Appendix E consists of three steps: (step 1) obtaining a point-wise wise error decomposition of the errors into manageable error terms that holds almost surely for any w E S2, then applying maximal inequalities to suitable empirical processes (step 2) and some degenerate U-processes (step 3) to control each of these terms. The final error bounds are obtained by combining all these bounds as shown in Appendix E.3.
Step 1: point-wise error decomposition. A main challenge in controlling the errors in Theorem 4. is the non-linear dependence of both estimators F(w) and Vi(w) on the empirical distributions, as they are obtained via plug-in procedure. We address this by breaking down the errors into components based on the discrepancies between expected values and their empirical counterparts of individual point-wise losses and their derivatives, all evaluated at the optimal solution li.. Specifically, we denote by doue and den the errors on the objectives defined as 8out = |Laue h() - Lowe (w, hg)l and 66n := |Lin (w, hū) Lin (wo, I. Moreover, we quantify the errors between the partial derivatives of these objectives and their empirical counterparts. To simplify our proof outline, we slightly abuse notation by denoting 0,u 0, 0,, 8 and 6 to refer to these errors in terms of partial derivatives. For instance, 0, is defined as |0, Lout (oma(w,,1 h.) - -h Lout (w, h ll,,, with similar definitions for the other terms (see Appendix E. We get F(w)-F((u.) I C( + 6,) and |V+ - (i()] S C( + On + 0 + 0 Si, + Or Proposition E.4 formalizes this step and includes the exact constants. The error terms in both decompositions are amenable to statistical analysis using empirical process theory as we discuss next.
Step 2: maximal inequalities for empirical processes. Some of the error terms, namely 8out and 5.55 can be controlled directly using empirical process theory. For example, 50ut is associated to the family of random functions vm (onLaaaa (w, ht) - Looee (w:, h )wes,, which defines an empirical process, scaled and centered empirical average of real- functions indexed by the parameter w. Thus, provided that suitable estimates of the class complexity are available (as measured by its packing number in Proposition F.1 of Appendix F), which are easy to obtain in our setting, we show in Proposition E.5 of Appendix E.2 that maximal inequality of the following form follows from classical results on empirical processes: IEg [supwen 80nt] S C/vm.
Step 3: maximal inequalities for degenerate U-processes. Step 2 cannot be readily applied to the remaining terms involving partial derivatives w.r.t. h (0,,5ut 0, 02 8in a 5-mh =: Dj.. These associated to processes that are not real-valued anymore, but take values in space. In fact, one could apply step 2 to get an error per dimension, but then summing the errors yields a divergent sum. While the recent work in [56] develops an empirical process theory for functions taking values in a vector space, the provided complexity estimates would result in an unfavorable dependence on the sample size. Instead, we leverage the structure of the RKHS to control these errors using maximal inequalities for suitable degenerate U- U-processes of order 2 indexed by the parameter w and for which such inequalities were provided in the seminal works of Sherman [67], Nolan and Pollard [54]. U U-processes of order 2 are generalization of empirical processes and involve empirical averages of real-valued functions which depend on pairs of samples, instead of a single one as in empirical processes. In our case, these functions arise when taking the square of any term in D2, and exploiting the reproducing property of the RKHS. This approach, presented in Proposition E.6 of Appendix E.2, allows us to obtain maximal inequalities for the terms in DA.- For example, it is of the
dimensiaai
8

---

following form for 0, Eg (supwen 0x I C/vm. Combining the maximal inequalities from steps and with the error decomposition from step I allows to obtain the result of Theorem 4.1.
Discussion. A Atrrnatte approaches to U-processes could be used to derive generalization bounds, could employ
although these would result in degraded sample dependence. Specifically, variational formulation of the RKHS norm appearing in some of the eπror terms, such as 0, to express them the error of some real-valued empirical process which standard results could be applied. However, this comes at the cost of considering processes indexed not only by the finite- dimensional parameter w. but also by functions in the unit RKHS ball. As a result, these families have much larger complexities as measured by their covering/packing numbers [77, Lemma D.2], which directly impacts the generalization rate. In contrast, our proposed approach bypasses this challenge by using real-valued U prrocessess indexed by of employing a more general empirical process theory for degenerate U- U-processes [67].
parameters, at the expense
To illustrate the implications of Theorem 4.1, we next provide convergence results for bilevel gradient methods.
4.3 Applications to empirical bilevel gradient methods
A typical strategy to solve (KBO) is to obtain empirical samples and apply a bilevel optimization algorithm to (KBO), for which our results offer statistical guarantees. Below, we present the generalization error for bilevel gradient descent. Generalization results for the projected bilevel gradient descent are directed to Appendix E.4.
Bilevel gradient descent. It is the simplest gradient-based method for solving the unconstrained (KBO) problem, i.e., when C = RRd. performs the update w/+1 wi - v/(.F(u))) for all t 2 where 7) > 0 is the step size. The algorithm requires access to the strongly convex inner-level solution and its derivative, which can be obtained using implicit differentiation.
Corollary 4.2 (Generalization for bilevel gradient descent). Consider Assumptions (A) to (E) and fix > O. Assume further that K in (KBO) is almost surely definite, and that there exists c > O such that wnf Lou (w. U, y) - 2|| > -00. Fix wo E Rd and let Wt+1 = W/ F( ( for all t 2 0, where 17 > O is the step size. Then, there exist constants î and such that for any 0 < 1j < Tj any 1 >> O, the following holds:
- sum | (impunpI/VVV i-000
min V=(i:)]]] S ()
(
1 v
1 S (m Vn
(
+
V vn
The additional assumption on lout serves as device to ensure the almost sure boundedness of the sequence priori. It is rather mild, as it can be enforced by small perturbation of the form (w, v. v) + loui(4 (w. v, y) + c||w]]? assuming lout 2 O, which is typical in applications. Any other device that ensures a priori boundedness could also be considered. The assumption on K is satisfied almost surely for most commonly used kernels. The proof of Corollary 4.2 follows from Theorem 4. and can be found in Appendix E.4. Corollary 4.2 also highlights key algorithmic insight: the convergence of the bilevel method requires striking a balance between data availability (sample sizes and m) and computational budger (number of gradient steps). This trade-off arises because the total convergence error combines a statistical component, due to approximating the population gradient from finite samples, and an optinization component, due to performing only a limited number of (projected) gradient steps. Ensuring the right balance when designing practical algorithms prevents either insufficient data or limited computation from dominating the overall error.
5 Numerical experiments
Setup. To empirically validate our theoretical results, we consider the instrumental variable regression problem discussed in Section 2.2, in which we assume linear dependence on w for the function fa of the form fa (t) = w ét),, where @(t) E Rd denotes the feature map. We chose this particular problem because it allows us to derive closed-form expressions of the exact value function and its gradient, as well as their plug-in estimators, which are detailed in Appendix I.2. We use the Gaussian kernel and follow the experimental setup of Singh et [68], generating synthetic data that remain fixed across all runs. We vary n between 100 and 5, 5,000, setting
The case

---

* m is analyzed separately in Appendix I.5, For the instrumental variable z, we consider two distributions: a p-dimensional standard Gaussian and a p-dimensional Student's t-distribution with degrees of freedom v E (2.1, (2.1,2.5, 2.5, 2.9). Further details on the experimental setup are provided in Appendix I.4, We optimize the outer loss in (KBO) using gradient descent, where the step size is selected using backtracking line search and wi is randomly drawn from (O, 1)a. The stopping criterion is when [VF(( |I 10-5, where i is the iteration index. Our code is available at https:/ gig.t...b.... www.oo//aareeeeeourrr/r/////
Scalable approximations for F and V.F. Since the expressions of F and V.F involve expectations, they are intractable to compute exactly. We approximate them accurately using their plug-in estimators F and V.F derived in Appendix 1.2, and evaluate them using a large number of samples. To make this computation scalable, we approximate the kernel using a random Fourier features approximation [60], as detailed Appendix L.3. Specifically, we use 1, 1,000,000 samples and 26,000 random features, and handle memory constraints via a block decomposition strategy with block size of 1,000.
Results. The plots in Figure 2 show the generalization behavior as a function of the number of inner samples n. (a) and (b) display the generalization emor at initialization for the value function and the gradient, respectively. (c) presents the generalization bound for the gradient norm at the final iteration, while (d) shows the bound for the minimum gradient norm across all iterations. These results align with our theoretical findings, as all curves closely follow the expected theoretical slope. Additionally, Figure of Appendix 1.5 shows that balanced sample sizes lead to improved optimization behavior.
(P - Rtwall
10
10-2
10
10
10
10'
10
Gaussian kernel
Theoreiical slape Student dist (2 2.5)
Goussian dist
Student dist (urm 2.1)
Student dist (p 1 2.9)
Figure 2: Illustration of gradient descent on (KBO) for the instrumental variable regression task using synthetic data. The plots are averaged over 50 runs and displayed on a log-log scale. The line represents the mean across all runs, and the shaded region indicates the 95% confidence interval.
Conclusion and perspectives
Summary. In this work, we established the first generalization bounds for (KBO). These results are crucial for understanding the generalization properties of algorithms for solving (KBO). They offer rigorous guarantees on the algorithm's performance on unseen data-a fundamental criterion for any algorithmic design-and help control overfitting. Given that our bounds are of order (1//m 1/vz), this highlights the equal importance of both outer- and inner-level sample sizes the overall generalization error. Our findings can impact current practices, particularly in hyperparameter optimization, where the validation dataset is typically much smaller than the training set.
Limitations and future work. This paper takes first step toward providing generalization results for bilevel gradient-based based methods in nonparametric setting. While theoretical analysis focused on a full-batch bilevel setting with exact gradiens,, extending this framework to stochastic variants, such as those in [3, 29, 21, 24], remains an open challenge. A promising direction would be to consider approximate kernel representations, such as random Fourier features or neural tangent kernels, which enable scalable learning using kernel methods while preserving useful theoretical properties. Furthermore, the constants in our bounds are likely conservative; we did not investigate their tightness or potential for improvement. A deeper analysis of their optimality could provide valuable insights and constitutes an avenue worth exploring. Additionally, providing generalization guarantees for the un-regularized problem. possibly in the form of minimax optimal rates for (KBO), is a worthwhile future direction. This requires controlling the constants as X - O. provided additional source assumptions are made, as discussed in [69, 70]. Finally, broadening our framework to cover non-smooth losses, such as the hinge loss in SVMs is an interesting direction for future work.
10

---

Acknowledgments and Disclosure of Funding
This work was supported by the ANR project BONSAI (grant ANN-23-CE22-0011--00 EP acknowl- edges funding from the Al Interdisciplinary Institute ANITI through the French Investments for the Future P program under grant agreement ANR- 10--P33-00006 the Air Force Office Scientific Research, Air Force Materiel Command, USAF under grant number 1-8655-22-1-70111 TSE-P; the ANR project Chess (grant ANR- 17-EURE-O00 0010); the ANR project Regulia; and the Institut Universitaire de France (IUF). EP and SV acknowledge support from the ANR project MAD. SV also thanks the PEPR PDE-AI program SANR-23-PEIA-000 and the 31A Côte d' Azur Chair BOGL.
References
[1] C. Ai and X. Chen. Efficient estimation of models with conditional moment restrictions containing unknown functions. Econometrica, 71(6):1995-1843, 2003.
[2] C. Ai and X. Chen. Estimation of possibly misspecified semiparametric conditional moment restriction models with different conditioning variables. Journal of Econometrics, 141(1):5-43, 2007.
[3] M. Arbel and J. Mairal. Amortized implicit differentiation for stochastic bilevel optimization. In International Conference on Learning Representations (ICLR), 2022.
[4] M. Arbel and J. Mairal. Non-convex bilevel games with critical point selection maps. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[5] S. Arora, S. Du, S. Kakade, Y. Luo, and N. Saunshi. Provable representation learning for imitation learning via bi-level optimization, In International Conference on Machine Learning (ICML), 2020.
[6] S. Bai, J. Z. Kolter, and V. Koltun. Deep equilibrium models. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[7] Bao, G. Wu, C. Li, J. Zhu, and B. Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[8] Bauer, S. V. Pereverzev, and L. Rosasco. On regularization algorithms in learning theory. Journal of Complexity, 23(1):52-72, 2007.
[9] A. Beck. Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB. SIAM, 2014.
[10] A. Beck. First-order methods optimization. SIAM, 2017.
[11] M. Belkin, Ma, and Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning (ICMI., 2018.
[12] S. Ben--avvd, J. Blitzer, K. Crammer, and F. Pereira. Analysis of representations for domain adaptation. In Advances in Neural Information Processing Systems (NIPS), 2006.
[13] Y. Bengio. Gradient-based optimization of hyperparameters. Neural Computation, 12(8): 1909, 2000. ISSN 0899-7667, 1530-888X. 8880. doi: 10. 10.1162009976660000011111111
[14] I.. Bertinetto, J. F. Henriques, P. Torr, and A. Vedaldi. Meta-learning with differentiable closed-form solvers. In International Conference on Learning Representations (ICLR), 2019.
[15] M. Blondel, Q. Berthet, M. Cuturi, R. Frostig, S. Hoyer, F. Llinares-López, F, Pedregosa, and J.PP. Vert. Efficient and modular implicit differentiation. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[16] S. Bochner. Lectures on Fourier integrals, volume 42. Princeton University Press, 1959.
[17] Bolte, Q.-T. L,, E. Pauwels, and S. Vaiter. Geometric and computational hardness of bilevel programming. Mathematical Programming, pages 1-36, 2025.
11

---

[18] J. Bradbury, R. Frostig, P. Hawkins, M. Johnson, C. Leary, D. Macllurrn G. Necula, A. Paszke, J. VanderPlas, Wanderman-Miine and Q. Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
com/ wtwp:ocoooaa/..eeccccc. jjaxmm/jaa
[19] W. Candler and R. Norton. Mulei-Level Programming and Development Policy, volume 1. World Bank, 1977.
[20] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foun- dations of Computational Mathematics, 7(3):331-368, 2007. doi: 10.1007/s10208-0055 006--199------
[21] T. Chen, Y. Sun, and W. Yin. Closing the gap: Tighter analysis of alternating stochastic gradient methods for bilevel problems. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[22] X. Chen and D. Pouzo. Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals. Econometrica, 80(1):277-321, 2012.
[23] X. Chen and D. Pouzo. Sieve Wald and QLR inferences on semi/nonpaaamettric conditional moment models. Econometrica, 83(3):1013-107)) 2015.
[24] M. Dagréou, Ablin, S. Vaiter, and T. Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. In Advances in Neurul Information Processing Systems (NeurIPS), 2022.
[25] J. Diestel and J. J. Uhl. Vector Measures, volume 15 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 1977. ISBN 978-0-8218-1515-1.
[26] N. Doumèche, F. Bach, G. Biau, and C. Boyer. Machine Learning Research (JMLR), 2025.
informed kernel learning. Journal of
[27] H. W. Engl, M. Hanke, and A. Neubauer. Regularization of Inverse Problems. Springer, 1996.
(28) L. Franceschi, P. Frasconi, S. Salzo, R. Grazzi, and M. Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International Conference on Machine Learning (ICML), 2018.
[29] S. Ghadimi and M. Wang. Approximation methods for bilevel programming. arXiv preprint arXiv.1802.02246, 2018.
[30] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. The MIT Press, 2016. http: / //ww:.deepppp/ www..eeeeaanninbooooooo org. org.
[31] A. Griewank and C. Faure. Piggyback differentiation and optimization. In Large-scale PDE- constrained optimization, pages 148-164. Springer, 2003.
[32] Hartford, G. Lewis, K. Scyton-Browny and M. Taddy. Deep IV: flexible approach for
counterfactual prediction. In International Conference on Machine Learning (ICML), 2017.
[33] Hofmann, B. Schölkopf, and A. Smola. Kernel methods machine learning. The Annals of Statistics, 36(3):1171-1220, 2008.
[34] G. Holler, K. Kunisch, and R. C. Barnard A bilevel approach for parameter learning in inverse problems. Inverse Problems, 34(11):115012 2018. doi: 10.1088/1361 0098//361-66220/aa47777
[35] M. Hong, H.-T. Wai, Z. Wang, and Z. Yang. A two-timescale stochastic algorithm framework for bilevel optimization: Complexity analysis and application to actor-critic. SIAM Journal on Optimization, 33(1):147-180, 2023.
[36] A. D. loffe and V. M. Tihomirov. Theory of Extremal Problems. Scries: Studies in Mathematics and its Applications 6. Elsevier, 1979.
[37] A. Jacot, Gabriel, and C. Hongler. Neural Tangent Kernel: Convergence and Generalization in Neural Networks. In Advances in Neural Information Processing Systems (NIPS), 2018.
12

---

[38] K. Ji. J. Yang, and Y. Liang. Bilevel optimization: Convergence analysis and enhanced design. In International Conference on Machine Learning (ICML), 2021.
[39] Keerthi, V. Sindhwani, and O. Chapelle. An Efficient Method for Gradient-Based Adaptation of Hyperparameters in SVM Models. In Advances in Neural Information Processing Systems (NIPS), 2006.
[40] M. R. Kosorok. Introduction to Empirical Processes and Semiparametric Inference. Springer Series in Statistics. Springer, New York, 2008. URL / 978-0-387-7440 -7977-5.
[41] G. Kunapuli, K. P. Bennett, J. Hu, and J.-S. Pang. Classification model selection via bilevel programming. Optimization Methods & Software, 23(4):475 2008
[42] Kwon, Kwon, S. Wright, and R. D. Nowak, On penalty methods for nonconvex bilevel optimization and first-order stochastic approximation. In International Conference Learning Representations (ICLR), 2024.
[43] J. Larsen, L. Hansen, C. Svarer, and M. Ohlsson. Design and regularization neural networks: The optimal use of a validation set. In Neural Networks for Signal Processing VI. Proceedings of the 1996 IEEE Signal Processing Society Workshop, pages 62-71, Kyoto, Japan, 1996. IEEE. doi: 10.1 TT9/NNNP.199.....8....
[44] M. Letizia. G. Losapio. M. Rando, G. Grosso, A. Wulzer, M. Pierini, M. Zanetti, and Rosasco. Learning new physics efficiently with nonparametric methods. The European Physical Journal C, 82(10):879, 2022.
[45] Z. Li, H. Lan, V. Syrgkanis, M. Wang, and M. Uehara. Regularized DeepIV with Model Selection. arXiv preprini arXiv: 240.:24263. 2024.
[46] Z. Li, D. Meunier, M. Mollenhauer, and A. Gretton. Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm. Journal of Machine Learning Research (JMLR), (5(111):1-51) 2024. URL httpa////mmmoo/a//eeeeeeeeeeeeee wwwprg//appss/aaaaa Serapess/25//// 22t///322223333/// html.
[47] R. Liu, Y. Liu, S. Zeng, and Zhang. Towards gradient-based bilevel optimization with non-convex followers and beyond. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[48] R. Liu, Liu, S. Zeng, Zhang, and Y. Zhang. Value-function-basl sequential minimization for bi-level optimization. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023.
[49] L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito, and A. Verri. Spectral Algorithms for Supervised Learning. Neural Computation, 1888)11873-1977 2008. doi:
[50] Mercer. Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society A, 209:415-446, 1909.
[51] D. Meunier, Z. Li, T. Christensen, and A. Gretton. Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal. arXiv preprint arXiv:2411.19653 2024.
[52] D. Meunier, Z. Shen, M. Mollenhauer, A. Gretton, and Li. Optimal Rates for Vallud Spectral Regularization Learning Algorithms. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[53] W. K. Newey and J. L. Powell. Instrumental variable estimation of nonparametric models. Econometrica, 71(5):1565-1578 2003.
[54] D. Nolan and D. Pollard. U-processes: rates of convergence. The Annals of Statistics, pages 780-799, 1987.
[55] S. Oymak, M. Li, and M. Soltanolkotabi. Generalization guarantees for neural architecture search with train-validatin split. In International Conference on Machine Learning (ICML., 2021.
13

---

[56] J. Park and K. Muandet. Towards empirical process theory for vector- functions: Metric entropy of smooth function classes. In International Conference on Algorithmic Learning Theory, pages 1216-1260. PMIR, 2023.
[57] F. Pedregosa. Hyperparameter optimization with approximate gradient. In International Conference on Muchine Learning (ICML), 2016.
[58] I. Petrulionyté, J. Mairal, and M. Arbel. Functional Bilevel Optimization for Machine Learning. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[59] Q. Pham, C. Liu, D. Sahoo, and H. Steven. Contextual transformation networks for online continual learning. In International Conference on Learning Representations (ICLR), 2021.
[60] A. Rahimi and B. Recht. Random Features for Large-Scale Kernel Machines. In Advances in Neural Information Processing Systems (NIPS), 2007.
[61] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. The MIT Press, 2006.
[62] W. Rudin. Real and Complex Analysis. McGraw-Hill, New York, 3rd edition, 1987. ISBN 978-008 778-0070542341.
[63] B. Schölkopf and A. J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. The MIT Press, 2002.
[64] B. Schölkopf, R. Herbrich, and J. Smola. A Generalized Representer Theorem. In D. Helm- bold and B. Williamson, editors. Computational Learning Theory, pages 416-426, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. ISBN 978-3-540-4458144
[65] J. Shawe-Taylor and N. Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge, UK, 2004.
[66] H. Shen and T. Chen, On penalty-based bilevel gradient descent method. In International Conference on Machine Learning (ICML), 2023.
[67] R. P. Sherman. Maximal Inequalities for Degenerate U-Processes with Applications to Optimization Estimators. The Annals of Statistics, 22(1) 22(1):439 459, 1994. URI. https:
[68] R. Singh, M. Sahani, and A. Gretton. Kernel Instrumental Variable Regression. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[69] S. Smale and D.-X. Zhou. Learning theory estimates via integral operators and their approxima- tions. Constructive Approximation, (6(2):153-172 2007.
[70] B. K. Sriperumbudur, K. Fukumizu, A. Gretton, A. Hyvärinen, and R. Kumar. Density estimation in infinite dimensional exponential families. Journal of Machine Learning Research (JMLR), 18(57):1-59, 2017.
[71] A. W. van der Vaart. Asymptotic Statistics, volume 3. Cambridge University Press, 2000.
[72] A. W. der Vaart and J. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Series in Statistics. Springer-Verlag, New York, 1996. doi: 10.1007/978- 111007/97-1-4757-5555 2545-2.
[73] Wang, C. Lan, C. Liu, Y. Ouyang, T. Qin, W. Lu, Chen, W. Zeng, and S. Y. Philip. Generalizing to unseen domains: A survey on domain generalization. JEEE transactions on knowledge and data engineering. 35(8):8052 8072, 2022.
[74] R. Wang, C. Zheng, G. Wu, X. Min, X. Zhang, J. Zhou, and C. Li. Lower bounds of uniform stability in gradient-based bilevel algorithms for hyperparameter optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[75] C. Williams and M. Seeger. Using the Nyström Method to Speed Up Kernel Machines. In Advances in Neural Information Processing Systems (NIPS), 2000.
14

---

[76] L. Xu, Y. Chen, S. Srinivasan, N. de Freitas, A. Doucet, and A. Gretton. Learning Deep Features in Instrumental Variable Regression. In International Conference on Learning Representations (ICLR), 2021.
[77] Z. Yang, Jin, Z. Wang, M. Wang, and M. I. Jordan. On Function Approximation in Reinforce- ment Learning: Optimism in the Face of Large State Spaces. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[78] X. Zhang, H. Chen, B. Gu, T. Gong, and F. Zheng. Fine-graines analysis of stability and gener- alization for stochastic bilevel optimization. In Proceedings of the Thirty-Third International Joint Conference Artificial Intelligence, pages 5508-5516, 2024.
15

---

Appendices
Roadmap. In Appendix A, we review existing non-kernel generalization bounds in the bilevel optimization literature and explain why minimax optimal rates cannot be obtained in our setting. We begin the theoretical appendices by presenting and establishing regularity properties of the objective functions in Appendix B. In Appendix C, introduce the gradient estimators. Appendix D is dedicated proving the boundedness and Lipschitz continuity of h and h along with local boundedness and Lipschitz properties of fin, lout, and their derivatives. The generalization results are provided Appendix E. Appendix F, we establish maximal inequalities for bounded and Lipschitz families of functions. Differentiability properties of the objectives are studied in Appendix G. Appendix H contains auxiliary technical lemmas used throughout the proofs. Finally, further details on the experiments and additional numerical results are provided in Appendix I.
Notations. denotes the Euclidean norm in Rd ||-1| denotes the norm in the RKHS H. || |lop denotes the operator norm, and || ||H denotes the Hilbert-Schmide norm. (5 denotes the inner product on H. and -) denotes the Silbert-Schmidt inner product. K (x,-)) denotes the feature map, for any x E X. For any two normed spaces E and F. C F`) denotes the space of continuous linear operators from to F. For any two probability distributions P and 2, @ Q denotes the product measure of P and @ Given two Hilbert spaces (H1, - and (H2, (., H2), the tensor product of u E H1 and
Hz, denoted by u U, is an operator from H2 H1 defined, for any E H2, (u @ u) = (u, e) For any U1...., E R, diag ( (1 Un)) E Rax* denotes diagonal matrix of size n x n, where the diagonal entries are Bj... U, and all the off-diagonal entries are O. 1m denotes a vector of size m where all entries are 1. 1,x denotes the identity matrix of size n. For any vector space over R. Idy denotes the identity operator on V. Given compact set K., diamm(.) denotes its diameter. v² denotes the transpose of either a vector matrix, depending on the context.
Contents
A Further Discussion
17
Regularity and Differentiability Results
17
B.1 Regularity of the objectives
17
B.2 Differentiability of the value function
18
Gradient Estimators
19
Preliminary Results
D.I Boundedness and Lipschitz continuity of hü, and h
22
D.2 Local boundedness and Lipschitz properties of lins lowe, and their derivatives
23
E Generalization Properties
24
E.1 Point-wise estimates
24
E.2 Maximal inequalities
29
E,3 Proof of Theorem 4.1
33
E,4 Generalization for bilevel gradient methods
33
F Maximal Inequalities for Bounded and Lipschitz Family of Functions
34
G Differentiability Results
38
16

---

H Auxiliary Technical Lemmas
41
I Details on Experiments and Additional Numerical Results
43
L1
Closed-form expression for h
44
1.2
Plug-in estimators for F(w) and F
44
I.3
Scalable approximations for F(w) and F(w) via random Fourier features
45
1.4
Additional details on the experimental setup
47
1.5
Additional experimental results
A
Further Discussion
Existing generalization bounds for the non-kernel case. Bao et al. [7] laid foundational work towards understanding generalization in bilevel optimization by analyzing uniform stability in full- batch bilevel optimization. Their generalization criterion compares the population outer loss evaluated the output of randomized algorithm to the empirical outer loss evaluated using the same algorithm. Given number x between 0 and 1, they obtain decay rate of O(T"/ /m) for unrolled optimization, which decreases as 1/m in outer sample size, but increases with the number of outer iterations T made. This criterion differs from ours, which instead compares the population outer objective at the theoretically optimal inner solution h to the empirical loss evaluated at the empirical solution fw.. Complementing this upper bound, Wang et al. [74] established lower bounds on the uniform stability of gradient-based bilevel algorithms, demonstrating rate of 52(7/m). Building on [7], Zhang et al. [78] extended the analysis to stochastic bilevel optimization, establishing on-average stability bounds and deriving generalization rate of O(/vm²) due the presence of stochastic gradients. In related context, Oymak et al. [55] studied generalization in neural architecture search using bilevel formulation, showing that approximate inner solutions and Lipschitz continuity of the outer loss yield generalization bound of (1)/m + 1/va). Arora et al. [5] investigated representation learning for imitation learning via bilevel optimization, offering generalization bounds of order (1///)) that depend both on the size of the dataset and the stability of learned representations.
Difficulty of obtaining minimax rates in our setting, Although spectral filtering yields minimax rates [51] in the kernel instrumental variable regression setting [68]. it fundamentally relies on linear operator representation of the inner minimizer, typically characterized through the spectral decomposition of a compact, self-adjoint covariance operator (see, e.g., [20, 8)). This formulation allows one to apply functional calculus on the spectrum, with filter functions (such as Tikhonov regularization and truncated SVD) controlling the contribution of small eigenvalues [27, 49]. Under suitable source conditions, this enables the derivation of minimax optimal convergence rates for kernel ridge regression and other problems involving quadratic losses. In our framework, however, the inner objective is generally not quadratic w, and the mapping w -> ht, is nonlinear. Moreover, regimes where spectral filtering is
we consider fixed X, in contrast to the most effective for minimax analysis. As a result, the source condition assumption and the spectral filtering tools that underpin minimax guarantees in the quadratic case do not apply directly in our setting.
B Regularity and Differentiability Results
B.1 Regularity of the objectives
The following propositions establish differentiability of considered objectives. We defer their proof to Appendix G.
Proposition B.1 (Differentiability of Lijn and Trout). Under Assumptions (A) to (D), for any (w, h) E Rd x H. the functions Lin and Lout admit finite values at (w, hi), are jointly differentiable in (w,, h). with gradients given by:
b (w, h(x), E Rdd 00, Di (w, h) = EE [0, (w, h(x), v)] E Rd, 0,
O Touue (u,,h) h)) = E.Q 10w lout
O, Toou h)) MC))) ()),,,,))- H,
Or Lin , 12) Ep 10 h(z),)) )) Xh H.
17

---

Similarly. the empirical estimates Lin and Lout admit finite values, and are differentiable with gradients admitting similar expressions as above with and Q replaced by their empirical estimates P. and Qm
Proposition B.2 (Differentiabillty of Lin). Under Assumptions (A) to (D). for any (w. h) E R the function (w, h) - Ön Lin (w,(w, h) is differentiable with partial derivatives given by:
02,, (w, h) Ep [0 Cn h(x), h(x),)) (x, E L(H,
8% Lin (w, = EP [0 (w, v) & (xx, + AIdx E L(H, H).
Moreover, for any w E ER and h E H. the operators Be,n, Lin (ws Lun h) and or (w, h) - A Idw are Hiihier--Schmid, i.e., bounded operators with finite filbert-Schhidd norm. The sume conclusions hold for the empirical estimate (w, h) + GnL (w, h) with partial derivatives admitting similar expressions as above with IP replaced by its empirical estimate P,..
Proposition B.3 (Strong convexity of the inner objective in its second variable and invertibility of the Hessians). Under Assumptions (A) to (E), h + (ws h) and h + L (nnw,,) h) are X-strongly convex for any w Rd. Moreover, for any w E Rdd and H. the Hessian operators 0g Lin (w.h) and Li (w, h) are invertible with their operator norm bounded by 7.-
Proof. By Assumption (E), we know that + lin v. v) is convex for any E R& and V. Moreover, by Proposition B.I, (r, y) + Ln (w, h(x), 3) is integrable for any E Rd and h E H. Consequently, by integration, we directly deduce that h + Ep [Riz (w, h(x), y) is convex for any w Idd Finally, h + Lin(us h) == Ep [e,n (w, h(x),, v)] + 3 ||A||3 must be X-strongly convex, for any w E Rdd as sum of convex function and a A-strongly convex function. Similarly, we deduce that h + Lin (w, h) is X-strongly convex, for any E Rd.. Invertibility follows from the expression of the Hessian operator Proposition B.2
B.2 Differentiability of the value function
Proposition B.4 (Total functional gradient V.F), Assume Assumptions (A), (B), (D) and (E) hold.
For any w E RR, the total functional gradient V F(w) satisfies:
F(Ww) - (we, W() + Le Lin (w, h )o E Bd.
(6)
where aty is the unique minimizer of the following quadratic objective:
Ladj (w, a) (a, Hw + (a, dw) for any a E H.
(7)
with H. = 08 Ii (w, N(): H - H being the Hessian operator and dus = Öh Dout (w,, MD) H.
Proof. By applying Propositions B.1 and B.3, we know that + Lin(w, h) has finite values, is X-strongly convex and Fréchet differentiable. Moreover, by Proposition B.2, 0g Lin is Fréchet differentiable on RRd x H. and, a fortiori, Hadamard differentiable. Therefore, by the functional implicit differentiation theorem [36, 58, Theorem 2.1], deduce that the map r> h is uniquely defined and is Fréchet differentiable with Jacobian h, solving the following linear system for any w Idd;
22 Lin (w, Ouh (w, = O.
Using that 0f Lin (w, ht) is invertible by Proposition B.3, we can express Ou as:
auh O Lmm (w, h() (0 Lan h2))
Furthermore, Lout is jointly Fréchet differentiable by application of Proposition B.1, so that w + F(w) also differentiable by composition of the functions (w, h) + Loue h) and + (w, ht). For given E d the gradient of F is then given by the chain rule:
VF(w) = T_ Ioo (w, + 0h, Or Toone ht).
(8)
Substituting the expression of h into Equation (8) yields:
VF(w)= Loue hm) 02, Lin (w, h (2) (w, hw,) (h))
18

---

To conclude, it suffices to notice that the function a appearing in Equation (6) must be equal to -H d Indeed, a is defined as the minimizer of the quadratic objective Lady (w, a) in Equation (7) which is strongly convex since the Hessian operator is lower-bounded by À ldæ. Consequently, the minimizer a exists and uniquely characterized by the optimality condition:
o + dw = O.
The above equation is a linear system in H. whose solution is given by a = -Ha'd dw-
C Gradient Estimators
Proposition C.1 (Expression of V VF(w) by implicit differentiation). Under Assumptions (B) to (E), for any w E Rd, the gradient F(w)) of the discretized kernel bilevel optimization problem (KBO) is given by:
V((w)=
Dout 1m
Din M m w.v
m
where K and K are the Gram matrices in Rax" and mx with entries given by Kij == K K( xz) and Kij (I,,,, and M E R=xx, R" Dout E R Dout Rdxm Din E R=*x, and Din Rdxx are defined as:
M = KD +nAlnxm
== K D
Dout
= (Dokow (w, ha (B3). 03)) 15ism"
Dout = (Osfourlw, (Tt), B3)) isism"
D diag (Bgemlls has (at), 31) 1sign
Din (02,olilw., (w wi) 1515m
Proof.
Let w E Rd. Recall the expression of F(w):
F(w)=
lout (wi hes (Tt)):
m j=1
À |1 s.t. hw arg min Lin(us h): n2 Σ ln (w, h(x;), vs)
NEW
By the representer theorem, it is easy to see that h must be a linear combination of (( ....,, :(
h Σ (zz.).
(9)
Hence, finding how amounts to minimizing Lin (w, ht) over the span of (K(x), (x)..)..... K(x,, )), iee. over functions TT of the form /7 >m (y)+ (Ii,)) for E IR. Restricting the objective such functions results the following inner optimization problem which finiteddimensional:
Yw = arg min yER
Σ =
ln (w, (K (K)). + 2
Y KY,
where we used that (h (1:))) (N7(i)))sssm = K 7, we can express F(w) as follows:
y and |
7 Ky. Similarly, using that
F(w) Σ Lont (wo, (K
Differentiating the above expression w.r.t. and applying the chain rule result in:
V((w)= 1 m Σ
m
Bott (w, (K (K4,), D1)
m Σ (w K Oouluut (w, (K (K))j.00)
m 1=1
19

---

where aw denotes the Jacobian of 9. We can further express the above equation in matrix form get:
F((w) Dot Im + -ww K D
(10)
Moreover, application of the implicit function theorem" allows directly express the Jacobian "w as a solution of the following linear system obtained by differentiating the optimality condition for 7 w.r.t
D K (w D +mAlnxn) K 0.
M
A solution of the form aw - Din M always exists by invertibility of the matrix M. The result follows after replacing Yw by Di, M in Equation (10).
w,y Lemma C.2 (Estimator of the total functional gradient). Let R. Consider the following functional estimator:
VF(W) 1
Solourlw, has (2,). v.) - Σ
L ln hn (z)
Then, under Assumptions (A) to (E), (w) admits the following expression:
FF(w)= Dout 1m
Din
K
u]
Rdd
Bw
n1
where Dout Din Dout, and Din are the same matrices given in Proposition C.I, while aw R and B. E R are solutions the linear system:
MK
Mu
71
u
(11)
u
M
p
Ba
e
where the vector u and matrix M are the same as Proposition C.I, while p and are non-negative scalars.
Proof. Let E Rdd We start by providing an expression of åة as linear combination of the kernel evaluated the inner training points 2;, i.e., K (x;,) -), and some element H that we will characterize shortly. From it, will obtain the expression of VF(w).
Expression of a Recall that aw is the unique minimizer of Ludy in Equation (5), which admits, for any a H. the following simple expression by the reproducing property:
1 n 2n
Lods (w, a)
Σ
(w,
a, Oylout (wi has (Tz),, (())),
+ 1
H
Hence, by application of the representer theorem, it follows that ån admits expression of the form:
a Σ (aw)) B
(12)
Therefore, it possible to recover d by minimizing a + Lue a) over the span of (5, ((..)))..., K(rx,) +)). )). Hence, to find the optimal coefficients á., = ((áw)))sisn and B,,.
"In the where the matrix K is non-invertible. needs restrict the orthogonal complement of the null space of K. Such restriction is valid since the resulting solution hr will not depend on the component belonging to the null space of K.
20

---

we first need to express the objective Lodi in terms of the coefficients E R" and 3 IR for given a².3 E H of the form a².3 (a), - PC. To this end, note that the vector
(5(z))...... (zxn)) is exactly equal to = K D as defined in Proposition C.I. Moreover, using the reproducing property, we directly have:
KK
in
(a aB
E)
a B
3
7L
K
[x
T
H
2 IK
Ht.
B
We can therefore express the objective Lawy follows:
Leady (w, )
1 2n
[a
3
K
K
u
a
K
a
IK
3
u
|
B
Hence, the optimal coefficients سw = ((áw)) and 3. are those minimizing the above quadratic form and are characterized by the following optimality condition:
M
M
(K (KDin v.v +nAl nxn) K v. +nXlnxn)
K D in +nAlnxn)
H
T (KD
Din nd
|IS
772
M
P20
Expression of V.(Ww). The result follows directly after expressing V.F(w) in vector form using the notations Dout and Din from Proposition C.I and recalling that (1:))))
[K
u
Proof of Proposition 3.1. Let Rd. Define
VF(w) = 1 Σ O (T.). + Σ ln (w De (
where hnw and a are given by Equations (9) and (12). We will show that Vi(w)= vf(w). By Proposition C.1 and Lemma C.2, we know that V((w) and V.(ww) admit the following expressions:
1 Dout m
1
Vi(w)
D
in
M
m
m
1 Dout Lm
1
) B
VF(w)
Din
K
m
n
w.v
Taking the difference of the two estimators yields:
VF(w) - v+(w)=
1 Din M u
m
K
u]
[
71
Din w.y M-1 u
m
M
K
u]
[
8w
n
where the term + (MK âr Bu, Mu) is equal 0 by definition of & and 8_, solutions of the linear system (11) Lemma C.2.
D Preliminary Results
In this section, Ω is an arbitrary compact subset of Rd with hull denoting its convex hull, which also compact. We also consider arbitrary fixed positive value A such that À S as this would allow us to simplify the dependence on of the boundedness and Lipschitz constants.
21

---

D.1 Boundedness and Lipschitz continuity of h and hw
Proposition D.1 (Boundedness of ho and hw). Under Assumptions (A) to (E), the func- tions w + | h and w + l are bounded over hull(S2) by Byxx (U) (0,6m (w, O, y)l > O. Moreover, for all w E hull([t) and X. (x) and hew (2) take value in the compact interval V==
x where B =
1 [-x Br Br C R.
H and | Let w E hull( Using Lemma H.2, we know, for any Proof. Boundedness of ||
H. that:
1 x 110, Lin h | h 11 I
This is particularly valid for h Thus,
| I 5 11 Lin 0)
Using the expression of the partial derivative Li established in Proposition B.1, we obtain:
| H S 1 18 (0 (we 0, (2 (0,
By Assumption (B), K is bounded by k. Hence, Jensen's inequality yields:
|| H S x F 10p0an 0. v\ K(x, )1 S
Ep 8 (w,
By Assumption (C), y is compact, which implies that hull( x is compact. From Assumption (D), we know that the function (w, + O,l (w, 0) is continuous. Given that every continuous function compact space is bounded, we obtain:
BVR
+00,
where B=
sup (
O.lmn(, > 0.
To prove that
|
ByR =
we follow similar approach to that of ||
1l S BVR More
precisely, investigate the case where the expectation is with respect the empirical estimate P, of P.
hg (x) and (x) belong V. Let E hull( and X. By the reproducing property, the Cauchy-Schwarc inequality, and Assumption (B), we have:
and (xx S VK |iol--
(x)( Vk I
Using the bound on | and
already proved in the first part this proof, we get:
(x)(
Br
and
(hw S
BR X
This concludes the proof.
Proposition D.2 (Lipschitz continuity wf he)) Under Assumptions (A) to (E), the function w
hy is L -Lisschitz continuous hull(S2), where I. == seppeehal(())vvee.ee) ||02, Cin v. v.y)ll 0, and V is the compact interval introduced in Proposition D.I.
Proof. To prove this proposition, we adopt the strategy of finding an upper bound for the Jacobian, which serves as the Lipschitz constant.
Let hu)) Using Propositions B.1 and B.3, know that h Lin(w, h) is X-strongly convex and Fréchet differentiable. Also, by Proposition B.2, On Lin is Fréchet differentiable on æ x H, and,
22

---

a fortiori, Hadamard differentiable. Then, by the functional implicit differentiation theorem [36, 58, Theorem 2.1], the Jacobian 0=hī H. + E2 can be expressed as:
0 --0 Lan (w, (()) (0% Lon (())
We have:
11a olo 1 110 Lin (w, 1 | (KhLm((w,ht)) op
10 no Lin (wo, mwm
Ep Lin (w, (C K(x, -) llpp
Ep
|06 1o lan (1)) 8) [K 11x2
v x
[10g Lm (1)) v
(13)
where the first line uses the sub- mub-uultiplicative property of the operator norm || Ilopp the second line stems from the fact that h + Lix (w, is X-strongly convex, for any w E R as proved in Proposition B.3, the third line follows from Proposition B.2, the fourth line uses Jensen's 's inequality, and the last line is a direct consequence of the boundedness of K by K. (Assumption (B)). According to Proposition D.I, h (z) E
Bx which is a compact interval of IE where == suPWetul(()) 10,lin (w, 0, v)l O. By Assumption (C), y is compact set, hence hull( x Vxxy compact. Besides, by Assumption (D), (w, v.y) + d, (w> v, y) continuous over the domain hu)l( x V x V. Since every continuous function on compact set is bounded, this leads to:
| x
Ep o (n h (x).
L ==
sup (E) Vyy
| (u, v, v, +00.
Substituting this bound into Equation (13) means that LVK is an upper bound on 110 ht olpp' Thus, the result follows as desired.
D.2 Local boundedness and Lipschitz properties of lins lowt, and their derivatives
Proposition D.3 (Local boundedness). Under Assumptions (A) to (E), the functions (w, x., y) + ooue (w. h (xr). y). (w, xr y) > Oylout (w, h (x)) y), and (w, x. + aphout(w (, (r),,) are bounded over hf)) x X x y by some positive constant Mout Similarly, the functions (w, x, y) +
Dn (w, he (x), (w, xr y) + Hlinlus hi (x). and (w, x. y) + o En (w, ht (x), V) are bounded over (f)) x x y by some positive constant Min. The constants Mont and Min are defined as:
Mout ==
sup maxx [[oouw( v)1, 110 (ws w)1l, O (w. v,,) > 0, "E
Min =
sup max (10,eilw,,,, v)l 1 (w, v, w) 1102 wio (w, I)) > 0,
where V TR. is the compact interval defined in Proposition D.I.
Proof. By Proposition D.I, we have that (z) E EV= = Assumption (D), we know that i,n, louts and their partial derivatives are all continuous on hull x V x y. Also, Y' is compact by Assumption (C). Thus, hull(S?) V x y is compact. As every continuous function defined over a compact space is bounded, we obtain that:
x 1- Bx Bx C R. for any I E X. From
sup (E) sup WE
Roue(w, 1 (x), v)1 <
sup vV
Roo v, v)1 < +00,
10 (w, h (z), v)1l
sup VEV
||0 (w,, U. v) < +00,
where E ((v), ( {w, )}} and o E (ún, out). This implies the desired result.
23

---

Proposition D.4 (Local Lipschitz continuity). Under Assumptions (A) to (E), there exists a positive constant Lipout so that for any (z,y) in X x V, the functions + Lou h (z), y), w + Ostoua (x), y), and w + deLout (w, (x), y) are locally Lipout -Lipschitz continuous over hull( Similarly, there exists positive constant Lip that for any (2x, y) in X the functions y) are locally Lip Lipschitz continuous over hull(St). The constants Lipout and Lipin are defined, for any X A.
A
++ 0,lin (w, (x), y), ++ 8Glan(u (w (x)) y), and w + 02 -a,yliaatu (n 11
Lipout = (A + Mink) max (Mouts Mout) >0 0
Lipin (A Mink) max (Mans Min) 0,
where:
Mout =
sup max (108 lore (w,, v. willop 100 foue (w, v. w)|l 102 loue (ws, v.u)l) (w,
> 0,
Min =
sup eE
max (1 wll) 00 (m v. w)ll Oi (ms 1. (w, v; v) > 0,
with Mont and Min being the positive constants defined in Proposition D.3, and V C R is the compact interval defined in Proposition D.
Proof. For any (w, x. E hull(S?) X' x V. we have: WoV h (z), 1) (oulouc(w, h (z), 8) + Oolour (z).g)auhz
g) (x)]
- 11 lowe (w, h (2)), w)ll - 10 (w, (z). v)1 1 (I )ll
Mout 1 Mink
Mont (A + Mink))
X
where the first line uses the chain rule, the second line applies the triangle inequality and the reproducing property of the RKHS H. the third line follows from Proposition D.3 to bound the derivatives of Lout, from Proposition D.2, which states that the function + hū is LyR -ips-hit continuous with L = supwehal(()) VEV.EE L (w, v, v)ll < Min, to bound [i t lop: and from Assumption (B) to bound || 11 and the last line a direct consequence of X S In similar way, obtain:
Mout (A + Minki)
Mont (A Mink)
VV (w. (, w)l S
VV (.), S
Msn (A + Msnk)
Min (A + Mink))
V (W, v)ll S
Ve 1 (x), v)
A
A
Min (A + Msn
V Pe (w, (z), 2l)
<
X
Combining all these bounds concludes the proof.
E Generalization Properties
As before, let Ω be an arbitrary compact subset of IRd
E.1 Point-wise estimates
We present a point-wise upper bound on the value error [F(w) F(w) and gradient error VF(w) - -F))) To this end, we introduce the following notation for the error between the
inner and outer objectives and their empirical approximations evaluated at the optimal inner solution h
gout = Looe(w, hi:) Troaa (w, n=)
8
Lin h()) Teem (ws, nw)
24

---

By abuse of notation, we introduce the following errors between partial derivatives of Lin and Live (resp. Lout and Lowa) evaluated at (w,)))) i.e.,
Ono
00 Lou hw) On Doc )(m)
8ut
O Loue (w, h(2 Ow Lo bneews hi:)
H
0, = On (w, (w, kww) - On Din (wi, k(n)
0 = Lu (w, (ww O Lin (w, |
11
0 = (w, (w,tw) - BRILnww, )
Se
Sw = L Lin kid) Oe Sh, (w, nww op
Proposition E.1. Under Assumptions (A) to (E), the following holds for any w E Q2:
| hnw 1x - 1 Ti (w,
Ono
Proof. Let w E Q. The function h + Lin (ws h) is X-strongly convex and Fréchet differentiable by Propositions B.1 and B.3. Moreover, dn is the minimizer of h + Tin h) by definition. Therefore, using Lemma H.2, we obtain a control on the distance H the optimum h of Lin (w,, h) in terms of the gradient 0₂ Ten (w,, h):
||| how 11 S 1 (whLi(ww.))) hi)
Vh E H.
In particular, choosing h = ho yields the inequality. The fact that @ (ws, (w, nww follows from the optimality of h which implies that On Lin (wo htt) O.
Proposition E.2. Under Assumptions (A) to (E), the following inequalities hold for any w E Qt
Ex =
Lone(w, 1/)) Loon )aw) S Coue
On E
b Lowa (w, hw) On Louelus (ww)l
s Cout
h
hew
71.
0 Lout
8w Lone (w, (( O. Done (w, hww)
5 Cout
how
74
8g E
0g Lin (w, (w) 86. Lim (wi, (ws, how)
S Cin
h/
Prw
op
7t"
83 F
02 I.m (w, )S) 02 Ti (ws Res)
I Cin
|
New
The positive constants Cout and Oin are defined as:
Cout == max (Mout Fc, Mouth, Mout vk) > 0,
Cin == max MMnRRRR ManK, Min v dx > O,
where Mout, Mouts and Min are the positive constants defined Propositions D.3 and D.4.
Proof. Lipschitz continuity of some functions of interest. Let w E Ω. According to Proposition D.I, both (x) and (x) lie in the compact interval V = [- Ex Bx C IR, for any X, where B = SUPwehal(().ee) f (w, 0, 0,y) > O. By Assumption (C), y compact set. Hence, Ω xxXX y is compact set well. Furthermore, by Assumption (D), (w, v, + (w, (w,,,,,.. v. v.y). (w. v. v) + loue v. v, and their derivatives are all continuous over the compact domain 52 x V x². Therefore, these functions and their derivatives are bounded on this domain. In particular, this also holds when takes the specific values h (z) or h (z). Let be either h (x)) or (z)), for any
25

---

E N. For any Ω and y E V, we have:
O (w, 0,8) v
sup
1 (w, (w v.8)] S Mout < +00,
wEVY
0 (w, 0,8)
@ (w: u. v) I Mout +00,
sup wEn,vEV.yEy
10 Lout 0,0)
10 (w, U. v) & Mout < +00,
sup
VE
10 (w, 8, 0,0)
sup
1n v, v) S Min < to0,
wEA
|10, w.o lin lin(ws, U. 0, v sup
v. u. S Min < +00.
wEALEEV.YEY
This means that E V + Loul(w, V E + Plin V) and v E EV + 02 Di (nn(w v, y) are Lipschitz continuous, with Lipschitz constants Mon. Mont, Mout, Min, and Min. respectively, for any w E Ω and E V.
V dulour (w,y),
+ Owlout (w, v, y).
Upper bounds. We have:
Ext = Toullw,h)) - Lowe (w, (w)h
1
lweelw, (ig)) 1
Low (w, hw 95))
m j=1
1 m
lowe(w, (aalww,,())))) (a,)) (3)) Lowe(w, (K))).)
m
Mont
Σ j=1
hi (ā,)) - (a
m
s Mout V
Ih's Rrw Imx
where the first line uses the definition of (w, + [wo h), the second line applies the triangle inequality, the third line leverages the fact that v -> loue(ws (wo, v, y) is -iss-Lipschitz continuous, for any E Ω and V, and the last line follows from the reproducing property of the RKHS H. Schwar''s inequality, and Assumption (B) to bound || [IK by Vk. Similarly, we obtain:
E s Mouth |int hew 1xx"'
Ou S Moue Int hew 1
0F < Menti/
Fillitt I Rullxx' De S Minki I hw
Combining all the bounds finishes the proof.
Proposition E.3. Under Assumptions (A) (E), the following inequalities hold for any Ω:
1 1l Cen Im (w. (/0) S Cins
[i0 (w, 1l Couts
where Cout and Oin are the positive constants defined in Proposition E.2.
Proof. Let w S..
Upper bound |0 Toout (wi, 1 We have:
|| Louel (w, br)l Eg 10 (w, (x). Kx, ))
I Ex 1 (w. ht x) [[(x 11x
< V 1 (w. 1 (x),
where the first line follows from Proposition 1. the second line results from the triangle inequality, and the last line uses Assumption (B) to bound [|K( )1x by VR. Furthermore, we know by
26

---

Proposition D.I that (w, h (z), y) belongs to the compact subset f2 x V x 3) and by Proposition D.3 that out (w, h (x).y) y) bounded by a constant Mout on hull( J. Hence, it follows that:
||0 Loat (we, b=)l S VRMMut S Cour.
where Cout is defined in Proposition E.2.
Upper bound L (w, ktt op According Proposition B.2, 0 -. Lin (wi, h() Hilbert- Schmidt operator, which points to:
|1 This means that to find upper bound on j Lin (w, h
S $1 Linn ww)l
Σ
Puy, Lin (w, k()
(14)
H
it suffices to establish upper op
bound on 102 Lin (w, hi) || for any I fl....,d] d}. For fixed (1.....,d) ......,d,,... we have:
Lsn (w, hw) = Ee [ Cn h (z), (2, 1|
S Ep Je Lan (z), v) ||([,, )1
x Er
10 Lan (z), Ki
where the first line follows from Proposition B.2, the second line is consequence of Jensen's inequality applied on the convex functtion || 112 and the last line applies Assumption (B) to bound [K ((xx,,))i, )l by s. Incorporating this upper bound into Equation (14) yields:
|0 Lin (w, h2) 1l,p S sv Ee [1 eI. h (x), w)] dx s Mon dd S Cin
where we used Proposition D.3 to bound 0h in (w, (z),,, y) by the constant Min.
Upper bound on [8 Lin (w, hww) Il.p. The derivation of this upper bound follows the same steps as the previous one, with the only differences being the of f.,. instead of Lins and h instead of hü- Note that in the last step of each the three upper bounds, we used the fact that the functions we are dealing with are continuous by Assumption (D) on Ω V y), which is compact because Q is compact, compact by Assumption (C), and V is compact interval of R defined in Proposition D. Hence, those functions are bounded.
Proposition E.4 (Approximation bounds). Under Assumptions (A) to (E), the following holds for any w E Ω:
F(w) - F(w)] & 8out + Cout 0r
Ci Ono + CouC 0R5i0
VF(w)- VF(w) <dn
X2
Cout P2, + Cout 1
Cin
C2
+
in
On
X
A
X2
where the constants Cin and Cout are given in Proposition E.2.
Proof. In all what follows, we fix a value for w in Q. We start by controlling the value function, then its gradient.
Control on the value function. By the triangle inequality, we have:
F(w) - F(w)) s Loue(w, h%)) Low (w, hw)) + Loue(w. hD) Dowe (wi, hww)
(15)
dout
Egut
27

---

According to Proposition E.2, the enror term E is controlled by the norm of the difference h hw Moreover, by Proposition E.I, we know that h hrw S L.., Enu < Cout P - hw H
} 0 Therefore, combining both bounds yields E < ",,"0, The upper bound on the value function follows by substituting the previous inequality into Equation (15).
Control on the gradient. By Proposition B.4, we have the following expression for the total gradient V.F:
V.(ww) 0g (we, hw)) 0 Lin (w,))) (oR Tin (w, Or. Tout hw)-
Similarly, the gradient estimator VF is defined by replacing Lout and Lin by their empirical versions Trous and Tans and hi, by fhw arg min Tur (we, h) in the above expression, i.e.,
VF(w)= Oa Troae (w, )w) th [w hw)) (oRT (w, (w, On Ontrrnelus (w,))w,
To simplify notations, for any h E H. we introduce the following operators R(h), R(h): 7 - 82 R(h) 03 Lim (we, h) (0 Tun (w, h)) and R(hh) = 0 T.in (w) (oR Tein (wo, 11)
The difference VF(w)- - VF(w) can be decomposed as:
VF(w)) - VF(w)
-Oouoouelue (w, h() - Ow Ow (wo, hi)) + (owLoulww, ha) o Du Rw)) - -R((ww) (On (ws hw) - On (w, nt)) + (oh (w, On Looeel, Rw)))
- -(R(S)) R((ww) OrLooulus hw)-
By taking the norm of the above equality and using the triangle inequality, we obtain the following upper bound:
VF(w)- -F [W])
Ou LoLoon (w) On Duttrnllus (w, kw) + To (ws, 1ww - Ow Tooto (wo Riw)
ogue
a Eout
+ [RWkw 1l,p, | (w, hid) On Dn (w, hid + +IonnCourlu (w, hid) On (w, hww 111/
Os 5oue
On Bg
+ [|(0 - ni(hw)) op 110 Lone ll
(16)
Next, we provide upper bounds on |e((tt) R((ww) and [R(hw) in terms of derivatives of Lin and Lin-
Upper bounds on || [R(ht) R((hww) and | By application of Propositions B.2 and B.3, we deduce that oe, Lin (in kt), oR Thin (w, ht), 02 (w, all bounded operators. Moreover, since Lin and Lim are X-strongly convex in their second argument by Proposition B.3, it follows that 0z Lin (enlw,, h2) 2 AIdx and 0f (w, 2 AIdx. We can therefore apply Lemma H. which yields the following inequalities:
(w, hww)), and Li hw) are
R(h)) - R(hww)
|00 (w, hi) - og (w, (w,, ||02 Lin h
< x
op
1
a2 Lin (w, hw) - Le ii (w, (w).hw))l |
A
1
02 Iem (wo, how
5
A
28

---

By applying the triangle inequality to both terms of the first inequality above, we obtain:
R(hL) - R(()w))
1 X 1102 i Lin (w, hol
[ohLin (w, h(n) - -0f (w, k() 10 + -1of (w,nt))) 0% Ln (wo, hww
02.6r
Boin Linl,,hh - Su, Is (w, mwn)
1op
+ n Iim(ww (w)) - Ohe (w (w. new l
0 B'r
Final bound. We can now substitute the above bounds on [R(hh) (hw) and B(chw)lo into Equation (16) to obtain the following upper bound on the gradient error: -F(W)-VF(C <0.0out + Egt + - bi Tinlws mا))l I!.,, (Ono + Ör Fg
op
+ 110p hall (x2 12 De (w hi)l (0R00 - 0f + 1 (o, + 0e E2)
(17)
Furthermore, by Proposition E.3, have the following upper bounds on the derivatives of Lin and Lout:
L1 (w, 1x S Cout:
10 Lin (w, (on(ww,)))) owll S Cin:
S SCn.
Incorporating the above bounds into Equation (17), we further get:
+ Can
VF(w) - VF(w)) <0.0 + O.s Funt
(0n5mut + Ön F
X
(Cin X2
1 +F + x (0 (0 + 0 2. E
+ Cout
(0R
By Proposition E.2, can upper-bound the error terms O. Fout and On Flgue by Cout | nn I
and E and &h Ein by Cin | - R H Furthermore, since | hew 11 S fnn by Proposition E.I, we can further show that the gradient error satisfies the desired bound:
V VF(w) <on + Cin On + Cout
Cin 87 1 2 o
X2
Cout [12
(1+2Cin
Cin
C2 X
+
X
E.2 Maximal inequalities
Proposition E.5 (Maximal inequalities for empirical processes). Let A be positive constant. Under
Assumptions (A) to (E), the following maximal inequalities hold for any A:
B2
sup goul LEE
Xmm c(S) max (Mout Lipout diam(a) AM
d c()) Xm d_((0) max Mout Lipout diam(()), AM2))
EQ sup
gout Lwe
where e(S2 a positive constant greater than that depends only on and while Lip and Most positive constants defined in Propositions D.3 and D.4.
29

---

Proof. We will apply the result of Proposition F.3 which provides maximal inequalities for real-valued empirical processes that are uniformly bounded and Lipschitz in their parameter. To this end, consider the parametrie families:
Thu = { x y (x, v) + ow, (w, (C v) w EE Tou {X y (z, + loul(w, (x), y) w E !2).
1 Isisd
For any 0 < S d, these real-valued functions are uniformly bounded by a positive constant Mout thanks to Proposition D.3. Moreover, by Proposition D.4, the functions - Our our (w, h (z:), y)
and w + lour(w, (z),, y) are all X Lipoou-Lippchit for any (z, y) E X x y. Hence, Proposi- tion F.3 is applicable to each of these families, with D set Q and Z set to X V. We treat both 5ou and 0, separately.
A maximal inequality for 6 For / readily apply Proposition F.3 with p to get the following maximal inequality for 60"!:
EQ
sup goul
EE
sup wESt
E (x,w)) Boulww, A (z),
Love (w, h (Tz),
WEn
c(I) 22m
diam AM Mwt).
A maximal inequality for 0 We now turn to 8 which involves vector-valued processes (as an error between the gradient and its estimate). While the maximal inequalities in Proposition F.3 hold for real-valued processes, we will first obtain maximal inequalities for each component appearing in 8gut and then sum these control 0yr To this end, we first use the Cauchy-Schie Schwwrz
inequality which implies that Eg (supwen du S Eg (0,) to control Eg (supwen (0, Simple calculations show that:
Thus we only need
2
Eg
sup aa gout WEn
<BQ
sup (0 LWER
Eq
sup WER
E (xx))~ (ouloue (x))
lout (w,))
1=1
==1
2
d
c(2) max(Mout LiPour diam AM2ut)
X3m
where the last inequality follows by application of Proposition F.3 with p 2 to each term in the right-hand side of the first inequality for 1 < l < d. We get the desired bound on Ee (supwen 6o. by taking the square root of the above inequality.
Proposition E.6 (Maximal inequalities for RKHS-valued empirical processes). Let A be a positive constant. Under Assumptions (A) to (E), the following maximal inequalities hold for any 0 < S A:
Eg
sup Öp 5ort WES
< X m (c((2) max Moou,,Ioone diam AM (ot..
Ep
sup 6 LWE
A in (c( max (Min, Tim diam(A), A
))
7
Ep
gin w.h 8th wen
sup 82
S i d (c(() max (Mi,, Lin,t diam(S)), AM
Ep
sup 0f WES
S X - (c(2) max (M diam(S)), AM
30

---

where dΩ) is a positive constant greater than 1 that depends only on D and d, Low, li Lin,1 : Lin,2, Mout. MIn.1, and Min.2 are positive constants defined as:
Lout.1 = Lip Mouthi, Lim,1 == Lipin Mink Lin = 2 Lip Mink",
Mout,1 Monn,, Min,1 Min,, Mm M2nn2
and Lipout Lipins Mout. and Min are positive constants given in Propositions D.3 and D.4.
Proof. Consider parametrie families of real-valued functions indexed by Ω of the form:
Teaa = [tw ((2, y). (x', v2)) + fa(w, x, x. x', ) (x, x") E S2},
where {1,2]. is an integer satisfying 0 s d 2, and fo (w, 2, y) real-valued functions given by:
fi (w, d h (x), (w, v, + 8n (w, A ()) f2+1: (w, + Pi (w: (z), 1 isls d.
for (w, x. + a (1 (x()),
For any 1 + 2, the real-valued functions fa are uniformly bounded by a positive constant Mnn thanks to Proposition D.3. Moreover, since the kernel K is bounded by due to Assumption (B), follows that all elements tu of Ts.a are uniformly bounded by Min.a = M N3 Moreover, for in
1 < + the functions w + fa(w, H. y) are - Lip -Lipschitz for any (x,, y) X y by Proposition D.4. Hence, it follows that the map w + tw ((x, y), y')) is X - Lin,a- with Lin,a == 2 Lip;n. Mink" for any (I. y) and (a', in X' x V. Similarly, for O, we get same properties, albeit, with different constants, i.e., the family To.a is uniformly bounded by constant Mout,a = MM M with Mout introduced in Proposition D.3, and is X - in its parameter with Lout,a
Lipout Mout ht where Lip given in Proposition D.4. Hence, the maximal inequality in Proposition F.4 is applicable to each of these families with Z set to X' x J, For conciseness, in all what follows,
and D set either to P for < s < d + 2, or Q for will write (x, y) and = (æ,, y:) and ž = (ā), 05) for 1 S i S and 1 S S m.
Maximal inequalities for 0gt and 0, We control 6 first as o will be dealt with similarly. Using Cauchy-Schwarz Schwarz inequality and standard calculus, have that:
Eg
sup 0,.8% 8out wen
<BQ
sup (8, gout )2
1 m
: EB
sup wEn
E E( [ppoout (w, (xx
m j=1
H
m
2 m
=Eq
sup E. 2 C880 (z, (2, wen
Σ m 1-j=1
Egno (2,
m
where (2, 2/) = aelout (w, (x), 0, (w, (x'), V')'('r xx) To.1- The last term is pre- cisely what Proposition F.4 controls when applying it to the family Tu,1 and choosing ID to be Q Therefore, the following maximal inequality holds by application of Proposition F.4:
< X 2 3m-m- (c((2) max I diam AM Maae,)) 1))
Eq sup 8ptt WEE
where e(l2) is a positive constant greater than 1 that depends only on S and d. We obtain a similar inequality for 8, by carrying out similar calculations, then applying Proposition F.4 the family Ti,1 and choosing IP for the probability distribution D. The resulting bound is then of the form:
< - - (c(12) max (Mm, diam AM MR.1 1
Ep sup O wen
31

---

A maximal inequality for 0 o5 We have:
Ep
sup 8 LEE
8th
(a)
Ep
sup (
w, )tr)
LWE
1
Ep
sup
E (a
K))
d u li (w, v4 (
wEll
==1
op.
(e)
Ep
sup
E (x. (
1
Σ
WEl
==1
d
n Σ
(d)
Eg
sup
E (a (w, (z,
(1 (2re,)
0
my mn
wEll
i=1
n
2 n
E2 sup E P (2, + wen
Σ n 1,=1
w.i 24)
Σ
E2 E [u,r(2,2))l]
where we introduced (,, := 8 on (w, h (1). u) of ( (x)), ",) (xx, x') E T2+1.1- Here, (a) follows from the Cauchy-Schward inequality, (b) is obtained by definition of 02 10, 8 while (c) uses the general fact that the operator norm of an operator is upper-bounded by its Hilbert-Schmide norm which is finite in our case by application of Proposition B.2. Moreover, (d) further uses the Hilbert-Schmid norm of an operator in terms of the norm of its rows, while (e) simply expands the squared RKHS norm and uses the reproducing property in the RKHS H. Each term the last item (c) is precisely what Proposition F.4 controls when applying it to the familics T2-1,1 for 1 < ( S d and choosing TT to be Therefore, the following maximal inequality holds by direct application of Proposition R4:
Ep sup 0 wen
6 gim
S - - dd (c(D) max (Mm, diann (M...)
W.N
where c(12) is positive constant greater than that depends only on Q and d.
A maximal inequality for 05.... We will use similar approach for 02 2
5tm. We have:
Ee sup 07 WEE
gin
(a)
N E2
sup (0% 8
LwE
(6)
sup
E [a
60 K(x,))
west
()) @ K(x,,)) .)
op-
(c)
Ea
sup WeR
( [8 (1), ((Er))
ae (w. (x:)) ve) v:) K(r,,)) 8 K
HS.
(d)
Ex
sup Eg PPPP (2, (2) + west
to (z 2,)
2
Σ
Eg- (2,
+,==1
1=1
32

---

//) x') E T2.2. Here, (a) follows from the Cauchy-Schwand incquality, (b) is obtained by definition of 02,62, while (c) uses the general fact that the operator norm of an operator upper-bounded by its Hilbert-Schmidd norm which is finite in our case by application of Proposition B.2. Moreover, (d) further uses the identity in Lemma H.3 for computing the Schhmit norm of sum/expectation of tensor-produet operators. The last item (d) is precisely what Proposition F.4 controls when applying it to the family T2,2 and choosing to be P. Therefore, the following maximal inequality holds by direct application of Proposition F.4:
where we introduced tw (2, = on
Eg
sup 55 WER
S W - (c(0) max (Mm.Z diam diam AM.
where c(S2) is positive constant greater than that depends only on St and d.
E.3
Proof of Theorem 4.1
Theorem E.7 (Generalization bounds). The following holds under Assumptions (A) to (E):
F(w) - F(w))
Cout dàn2
sup wei
2 Am
E
sup WER
VF(ww= FF(W
2
d
Cin
Cout A
2 + 3
Cin
+
C
in
1
A
X²
m
m
where the constants Cin and Cout are given in Proposition E.2.
Proof. Using the point-wise estimates in Proposition E.4 and taking their supremum over S2 followed by the expectations over data, the following error bounds hold:
- sup F(w) - F(wil wEn
<Eg
sup gout WER
Cout
EP
sup On
A
WE
Cin
E
sup
VF(w) VF(WW/]
<Eq
sup dout LEE
+
EQ
sup Sout LWER
A
Cout
Cin
C2
+
1
+
Ep
sup 0, 8in LWE
A
X2
Cou
Cout
Ep
sup LEn
Ep
sup 2 8 tee
X2
Furthermore, we can use the maximal inequalities in Propositions E.5 and E.6 to control each term appearing in the right-hand side of the above inequalities:
sup F(w) - FFw! <R m -1 wen
Coun - -x-(1+))).
VF(ww) Fデ(w ||
<R m - + C.n (1++)
E sup WED
C2 2 +
Cm
Coutn (1++))
1 +
)
X2
+ Con -2+ + Couth"" 2 xx-(1++)
where the constant R depends only on the Lipschitz constants Lipin and Lipouts the upper bounds Mnn and Mont, the bound the kernel, the set Ω and the dimension d. Rearranging the obtained upper bounds concludes the proof.
E.4 Generalization for bilevel gradient methods
Proof of Corollary 4.2. Consider that infw.r.y lout (w, U, y)
c||w]| > 0, which entails
Loue(w, v. y) 2 c||w||2 for all v, y. Using Proposition D.I and setting B = supwey (D (wo. 0, v)
33

---

we have almost surely that:
F(wo) - max lols 3n wEy
lour v: v. =: E.
Therefore, for any w such that F(w) S F(wo). we have || E//c. Define Q as the ball of radius v centered at O. Using the fact that VF VF in Proposition 3.1 and the representation in Equation (4), it is clear from Proposition D.2 and Assumption (D) that V is Lipschitz on with deterministic constant L. follows from standard results on gradient descent for nonconvex F with Lipschitz gradient (see, e.g., [9, Theorems 4.25, 4.26)) that if we take 1/L, then almost surely:
Flwr) F(wo) and wa Ω for all / 0.
V((w)) 0 as
2c.
Vi(wi)|| solvt+ for all 0, where č is deterministic constant.
min.
The corollary then follows by combining Proposition 3.1 and the uniform bound in Theorem 4.1.
Bilevel projected gradient descent. Considering the constrained (KBO) problem and assuming that C is convex and compact, the projected gradient descent initialized at wo E C iterates the following recursion W/+1 [w 1 ((xx) for all O, where II denotes the orthogonal projection onto C and 1) > 0 is the step size. The algorithmic requirements are the same as the gradient descent algorithm, with the additional cost of computing the projection, which is typically cheap for basic sets such as balls. In the constrained setting, the optimality condition should take the constraints into account. To this end, we consider the gradient mappings G. + , (w πe(( - v)V and G +> 1 7) (w - [T (V])) [10, Section 10.3). This captures the stationarity of the recursion, and any local minimum of F on C satisfies G, = 0 for all rj >
Corollary E.8 (Generalization for bilevel projected gradient descent). Consider Assumptions (A) to (E) and fix À > Assume further that in (KBO) is almost surely definite, and that C is convex and compact. Fix wo E C and let We+1 = llw(w; 1/ ((w))) where y) > O is the step size and t 0 the iteration index. Then, there exist constants fj and >> 0 such that for any < 1 and >> 0, the following holds:
min [[G]((a)]]]] S ( (
,E lim [[G(Ww))|] S 1-:00
V(+T)
Proof. We choose Ω C. All iterates obviously remain in Ω. Similarly as in the proof of Corollary 4.2, we know that V is Lipschitz and that F is bounded on Ω with deterministic constants. It then follows from classical analysis on the nonconvex projected gradient algo- rithm (see, e.g., [10. Theorem 10.15)), that for sufficiently small 17, we have almost surely that min.; (wi) S 8/VT+T for a deterministic constant ē >> 0, and that G,(4:) - as i + Using the fact that the orthogonal projection is 1-Lipschitz, (see, e.g., [10, Theorem 6.42)), we also have for all w E Ω:
[[,((w) G, (w) VF(w)]]
The result follows by combining Proposition 3.1 and the uniform bound in Theorem 4.1.
F Maximal Inequalities for Bounded and Lipschitz Family of Functions
Let Z be subset of Euclidean space and Ω be a compact subset of Idd. Denote by @* Z the k-th tensor power of Z, for any 2 1. Consider a parametric family T of real-valued functions defined over Z and indexed by parameter Ω i.e.,
T
12 12 2 (2) E ?}
(18)
34

---

For given probability measure μ on 2. denote by L2(H) the space of square y-integrable real- valued functions. We denote by |l = ED [f(=) the Ly(u)-norm of any function f E L2(H). For any > O, we denote by D (c, TT,T,AU L2) the c-packing number of T w.r.t I2(μ). The next proposition provides a control on such a number under regularity conditions on the family T.
Proposition F.1 (Control on the packing number). Assume that Q is a compact subset of IRd, that the parametric family T defined in Equation (18) uniformly bounded by a positive constant M, and that there exists positive constant L so that, for any probability measure on Z, w tw (z) is L-Lipschitz for any E Z. Then, there exists a positive constant c(It) greater than that depends only on St and d so that, for any probability measure μ. on Z, the following bound holds for any c C M:
D (c, (2()) S c(s)) (max (L))iam(S))
e
Proof. First using [40, Lemma 9.18] and [40, Paragraph 8.1.2). we know that the e-packing number D (c, L,, [p)) is smaller than the 5 -bracketing number Nj (5. T, L2(x)). Hence, we only need to control the bracketing number. To this end, recall that the function + (=) is L-Lipschitz for
any E 2, so that (71, Example 19.7] ensures the existence of a positive constant c(S2) that depends only on Q for which the following inequality holds for any E < Ldiam((2):
1 1 NJ (c, T, L2(14) & c(2) (
(.
Morcover, since the e-bracketing number is decreasing in e, it holds that:
[diam(())
Nn (e, T, T, L2(1)) - Nn (e_, L2(u)) S c(1))
for any c < Ldiam and c_ I L di). Taking the limit when c- approaches Ldiam(12) yields
Nn (e, L2(u)) S c(I) for any 2 (lam Hence, we have shown so far that for any >
Nú (c, L2(r)) s c(1)) max (1. (1(ddiaam((0) ))
Moreover, by noticing that max(1, Ldiam(()) that:
max(M.L-diam(D)) for any S M, we further have
max (M, L d(iam(5)))
Ni (c, T, I2()) s c())
Finally, recalling that D (c, T, L2(m)) - N1 (, L2(n)), we get that D (C,TLL22))
<
2cc((2) maxi diam((()))
The desired bound follows after redefining c(N) to include the factor
2d (i.e,, ((2) 24(((2)).
L
Theorem F.2 (Maximal inequality for degenerate, bounded, and Lipschitz U U-processes). Let be either or 2. Consider parametric family T 28 (Z1...., 2x) + (21...... 2x) dexed by a parameter E Ωt where Q is compact subset of Rd. For a given probability distribution D over Z, assume that all elements tu are degenerate w.r.t. D, meaning that:
R | E of real-valued functions over 8 in-
EEND [t)) =0,
if k = 1
EEND (2, EZ-D
=0, Vz
if k: 2.
Furthermore, assume that all functions in T are uniformly bounded by a positive constant M and that there exists a positive constant L so that w + (=(2z,,..., 2x. is L-Lipschitz for any (21.... .., 24)) E x Z. Given i...d. samples (21)1sis from D, consider the following U-statistic U
if k: =
Uk ==
i=1
a
ty (2 2g),
k 2.
n2
1)
35

---

Then, there exists a universal positive constant c(f2) greater than 1 that depends only on St and d such that for any p {1,2}:
Ep sup LEE
Unlul"
~n- nn-4c( (c() max ( diam))) M2)
Proof. Maximal inequality for degenerate U- prpocesssss We will first apply the general result in [67, Maximal inequality] which controls ED [supwer ( in terms of the packing number of T. First note, by assumption, that the functions (21, [x) are uniformly bounded by positive constant M. Therefore, the constant function (22...., 2k) = M is an envelope for T, i.e. T satisfies T(21..... =*) 2 supweR (z...,. =x) for any (21...., 24) E & 2. The envelope T is, a fortiori, square u-integrable for any probability measure on @* Z. Hence, we can apply [67, Maximal inequality] with the choice T for the envelope function and set the integer m appearing in the result to m to get the following bound:
|TT) I 1,x Bn
En Lee
sup
U (w)
In TE
z0p
de
(19)
where I' is a positive universal constant that depends only on d and that we choose to be greater than 1, while Ann are suitably chosen probability measures @* Z that possibly depend on the samples 21...., En and other random variables, and 6, ||T')| == supwen l|t Ipl... Here, the expectation symbol the right-hand side is over randomness on which ft, might depend. Note that the original result in [67, Maximal inequality] is stated using a slightly different definition of the packing number but which still equivalent the statement above in our setting".
In our setting, the envelope function is constant and equal to M, and by definition dn S 1. Hence, the inequality in Equation (19) further becomes:
I <n-tMrE MIE [D(((e T, L2((m))) zip
ED
sup LEn
U
de
(20)
We simply need control the packing number D (e (TII p T, In(()) independently of the proba- bility measure μ.
Control on the packing number. We have shown that the constant function T(2),..., == M is an envelope for T which is, fortiori, square j-integrable for any probability measure with [|]] p.2 M +oc. Moreover, the functions w + (=1 -.,,) are T.-Lipschitz for any (z,...., 2x) E 8 z. We can therefore apply Proposition F.1 which ensures the existence a positive constant c(ft) greater than 1 and that depends only Ω and that the following estimate on the e-packing number of the class T w.r.t. L2(2)) holds:
D (e (11T'1 T, L,(()) s <(())
max
L diam (22)
11)
11
(1)
Ve E (0,
(21)
Combining Equation (21) with Equation (20) yields:
S n MTE S. (Ae (Ac-d)ain) 2d0 de n A
(' (' de
En sup
1 | wen
$2
< 2n Te((s)) max (L diam(A)) M?)
'The constant I' appearing in [67, Maximal inequality] depends only k, p and m. i.e., I' == g(k, p, m). Since, we are only interested k < and p < and m is fixed to we choose to be maxige g(c, p, so that is the same in all our cases.
'In [67, Maximal incqualityl. the author considers modified version of the e-packing number (call it D(e, T, Lz(p))) associated to L2(μ) but endowed with a normalized version of the standard norm on Le(n): Il, = I1/1p. Both numbers related by the following identity: D (e, T, L2(()) !Til,.2'
D( T, (x)),, thus making the statement (19) equivalent to the original statement [67, Maximal inequality].
36

---

where, for the last inequality, we used that A v A c(S2) za max
1)
since A
M
is greater than 1. The desired result follows after redefining c(52) as 2Tc(2) z which is positíve constant that depends only on Ω2 and d.
The following two propositions are particular instances of Theorem F.2 and will be used to obtain the main bounds.
Proposition F.3 (Maximal inequality for empirical processes). Consider a parametric family T == w E { of real-valued functions defined over subset Z of a Euclidean space and indexed by a parameter E QN where St is compact subset of Rd Assume that all functions in TT are uniformly bounded by a positive constant M and that there exists a positive constant so that w + t2) is L-Lipschitz for any 2 E Z. Consider a probability distribution IB over Z and let (4))sssn be i...d. samples drawn frow I1 then there exists positive constant c(S2) greater than 1 that depends only on 92 and d, such that for any integer p E {1,2]:
(2 2 (z)
1 Σ (2)
n
Ep
sup WE
E B (z)]
$
((2) max(Maaa diam (
Proof. The upper bound is direct consequence of Theorem F.2. Indeed consider the family S of functions of the form (z) = (z) EgED [M (3)), ) for any 2 E 2. Then clearly, the process & - (2,) is degenerate of order k = 1, and the family S is uniformly bounded by
2M and is 2-iipschiiz. Hence, by Theorem F.2, the following maximal inequality holds:
ED
sup Len
U U/sw!"
S 2n i c(()) max (M diam diam)))), M²)
We get the desired upper bound by redefining c(s2) to contain the factor 2.
Proposition F.4 (Maximal inequality for U Urprrcessss of order 2). Consider a parametric family z/)
T = (Z x Z (2,2') tw,,,) E R w E Ω of real-valued functions indexed by parameter E Ω, where Q is a compact subset of Rd and 2 is subset of Euclidean space. Assume that the functions in T are symmetric in their arguments, i.e., tw (z, = tw (z',, 2). Additionally, assume that
all functions in T are uniformly bounded by positive constant M and that there exists positive constant so that w + (2, z²) is L-Lipschitz for any (z, E Z x Z. Consider a probability distribution ID over Z and let (2i)1sisn be i.i.d. samples drawn from D, and define the following statistic:
a
2 ni Σ
Tw == R (2, z +
Σ
La (2,,
Ezar (/w (Z, z:)l
n
Then there exists universal positive constant c(fl) greater than 1 that depends only on Ω and d such that:
Ep
sup LEE
|T]|
S - c(?) max (ML diam()),, M?)
1
Proof. The proof will proceed by first decomposing Tu, into a sum of a degenerate U- U-process and term of order O The maximal inequality for degenerate U-processes from [67] will be employed to obtain the desired bound.
Decomposition of Tw. Consider the following function defined over Z x Z and indexed by elements Ω:
sw 22,2') = (z, EE-D (2, - EEAD Itw 23, + DD (t,(E,z)),
(22)
By direct calculation, we decompose To into two higher order terms and third term, U involving Sw, which happens to be Ustttiisti:
sw
Tu
n(n (1
Sw (zi, (z)
n - 1) $1==1
1
(2i, 2z)
n
Σ (2,
1=1
37

---

Using the triangle inequality in the above equality and recalling that, by assumption, tw (2, x²) is uniformly bounded by a positive constant M, it follows that:
1 n²(n 1)
2.M
| [
+
(26, S
[R +
n
Furthermore, taking the supremum over followed by the expectation over samples yields:
2M
ED
sup
Tw
S ED
sup
U
+
(23)
TWE
n
Hence, only remains to control the first term in the above inequality. To this end, we will use a maximal inequality for degenerate U-processes due to [67].
Maximal inequality for degenerate U-processes. We will first check that UR is degenerate statistic for given w E Ω. Simple calculations show that for any 2 in Z:
BEND (2, 2)] = EEED (sw(2, =)] 0.
The above equalities precisely ensure that 02 8. is a degenerate U-statistic for TD. Consider now the family S == {2 x 2 9 (z, 2") + 6u(2z=') E IR w E 22.. We show that S is uniformly bounded and Lipschitz which allows to directly apply the result stated in Theorem F.2, which is a special case of the more general result in [67, Maximal inequality]. First note, by assumption, that the functions (2, 2') are uniformly bounded by positive constant M. Hence, using Equation (22). it follows that (=, is uniformly bounded by 4.M. Moreover, the functions + (z, z²) are L-Lipschitz for any 2, in Z. Hence, from Equation (22), we directly have that w - (2, 2²) is 4L-Lipschitz for any 2, Z. We can directly apply Theorem F.2 with le 2 and p 1 to S and get the following maximal inequality:
ED
sup LER
[
I 4n 44- ((() max (ML diam({)), (S),
We obtain an upper bound Em (supwen [w]]] by combining the above inequality with Equation (23), then noticing that 2M < 2c( max (I.iiam( .) so that:
Ep
sup [rw| WE
< 6n 6n-'c((0 c(S)) max (ML diam ,
M1?)
Finally, the desired result follows by redefining c(s2) to include the factor in the above inequality.
G Differentiability Results
The proofs of Propositions B.1 and B.2 are direct applications of the following more general result. Proposition G.1. Let U be open non-trivial subset of R.d Consider real-valued function (: (w, v) + E(ws v. u) defined on U x IR x y that is of class C jointly in (w, v) and whose derivatives are jointly continuous in (w, v. v). For a given probability distribution IB over X Y consider the following functional defined over x H:
L(w, h) == Ep [f( h(x),)))) v)]
Under Assumptions (A) to (C), the following properties hold for L:
L admits finite values for any (w,h) E H.
(w,h) F L[w, h) is Fréchet differentiable with partial derivatives T_I(w,,)) h) and L, h)) at any point (w, h)) u x H given by:
0.L(w, h) = Ep 10_ (xx), v)] E R2,
d,w, Ep [0, h(z), v) K(x,)) H.
38

---

The map (w.h) + Jr,LWw, h) is differentiable. Moreover, for any (w. h) E E H. its partial derivatives P h) and 02 h) at (w, h) are Hilbert-Schmide operators given by: L [( h) ED [ww, h()), v) K -)] E C(H,R"), 0 LWw, hi) = ED [ofe(w, h(z), (x,,) & K(x,)) -)] E ((H,
Proof. Finite values. Fix w E U and h E H. We will first show that h is bounded on X. By the reproducing property, we know that [h(x)) & | v /K(z, x)) for any E X. Moreover, the kernel K is bounded by a constant K thanks to Assumption (B). Consequently, [b(x))] is upper-bounded by || VK for any E X.
Denote by I the compact interval defined as I = |- || VR, |1 H V Vnl. By Assumption (C), the set y is compact that I Y' is also compact. Moreover, we know, by assumption on that (w, v, v, + f(w, v, y) is continuous on V x IR x y. Therefore, (v,y) + E(w, v, y) must be bounded by some finite constant C' on the compact set I x ). This allows to deduce that (z, y) E(wr, h(x)), v) is bounded by C' for any (I, E X' x y' and fortiori ID-integrable, which shows that L(w, h) is finite.
Fréchet differentiability of L. Let (w,, hi) E U x H. Consider (wi, 1t)221 a sequence of elements in U x H converging to it, i.e., (wy, h2) - (wi, h) with (wy, h2)) o (w, for any j 2 0. Define the sequence of functions ry : X' x y + E for any (a. E & x ) as follows:
ry r, y) (wy h,))),)) e(w, v() (0 (w, Mx), K(Ix,),, 1)# (0we(w, v), - -w) [1(w5, h2) - (w, h)ll
(24)
We will first show that EE [ryy (2, w) converges to 0 by the dominated convergence theorem [62. Theorem 1.34]. By the reproducing property. note that f(w, h(z),)) = f(w, (h. K K(x, )), y). Hence, since é is jointly differentiable in (w, for any y. it follows that (w, h) + f(w, h(x), y) is also differentiable for any (x, y) by composition with the evaluation map (w, h) + (w, (h. K(x, ))x which is differentiable. Hence, the sequence ry ry y) converges to 0 for any (z.y) E X y. Moreover, by the mean-value theorem, there exists O S eg S 1 such that:
(5, = ((ooe (1),) - ane (w: M()).))) v) K(x, h13 - 11 - (owe hg(() - 0 (wr, Mx), ,), - w)
[I(ws, h1) - (w, hi]l
(awww.hh))) h2)) We will show that ry (2. y) is bounded for j large enough. We first construct compact set that will contain all elements of the form (wj, hx)), y) and (w,, (x), y) for all j large enough. Since w is element in the open set 24 there exists closed ball B(w, R) centered at w and with some radius It small enough so that B(w,, R) is included in U. For all j large enough, wy and Wj belong to B(w, R) as these sequences converge to Moreover, hy and h2 are convergent sequences. Consequently, they must be bounded by some constant B. By the reproducing property, and recalling that the kernel K is bounded by K by Assumption (B), follows that max(1 / (z)]. hyyx)) < Bx. Consider now the set W := B(w, R) B1 (0, Bx) x y which is product of compact sets (recalling that y is compact by Assumption (C)), where B1 (0. Bx) the closed ball in R centered at and of radius Bx. For j large enough, we have established that (wj, (x)) u) and (mz, hy (z), v) belong to W for any (x. v) E X x V. Since, by assumption on E, 8,8(i, v) and 0_,((w, v, y) are continuous, they must be bounded on the compact set W by some constant C. This allows to deduce from the expression of r y) above that r v) is bounded, and a fortiori dominated by an integrable function (a constant function). We then deduce that Ep [[ry (I. v) converges to 0 by application of the dominated convergence theorem [62, Theorem 1.34].
where (wy, h,) = (1 (1- (w, cy(Wy,
Recalling Equation (24), ED (1, y) admits the following expression:
Ep (2, v)] = Mww,, hT) - T.(w, h) - Ep [ E (w, h(x), y) K(x, :), h, - =]] - (ED [Wwe(w, Mxx) v)). .wg - w) [1 h,) hill
(25)
39

---

The convergence to 0 of the above expression precisely means that L is differentiable at (w. h) provided that the linear form g + Ep [0, / (w, h(z)) y) (xx,)). ).gky) is bounded. To establish this fact, consider the AaHu-valued function (ar, v) + 0,6 (w, h(x), y) K (z. .). This function is Bochner- integrable in the sense that Ep [1I (w, h())),)) (x,, )ll is finite [25, Definition 1, Chapter 2].
Indeed, we have the following:
Ep [ (w, M(x), v) (x, MMdl = Es a (w, h(x). v) (K( x)
S VRDD 1 (w, h(x)) v)ll < +00,
where, for the inequality, we used that (a. y) + a, hxx) y) is bounded as shown previously. Consequently, ED [Ope (w, h(x),, v) K (xx, -)] is an element in H satisfying:
(En [o,e (w, h(x). v) (xx, 19) = Es [(0ee (w, h(r),)) ((a, ((2,)).)))l Vg E H.
The above property follows from [25, Theorem 6, Chapter 2] for Bochner- innterrr-i functions that allows exchanging the integral and the application of continuous linear map (here the scalar product with an element g). The above identity establishes that g + Ep (0,e (w, h(z), y) K (x. .).9) x) is bounded and provides the desired expression for 0, h). The expression for 0., (us,) h) directly
follows from the last term in Equation (25).
Fréchet differentiability of 0r L. We use the same proof strategy for the differeeniaabiliyy of L.
Let (we, h) U H. Consider (we, hy) a sequence of elements in H x H. converging to it,
i.e. (wj, h2) + (w, h) with (wi,h)) # hw) for any j 2 0. Define the sequence of functions
8y : X x y + H as follows:
hy) (w, bill sy(,,,) (o,l (w,, (x)()) 0,l (4s, M(x), v)) K(x,-)
0e (w: h(x), v) ((x,)) @ K(x, (hy h) w) 0h Mw h(x) K ((x.)).
(26)
We will first show that ED
converges to by the dominated convergence theorem for Bochner-integrable functions [25, Theorem 3, Chapter 2). By the reproducing property, note that a, (x=), y) K (x. = 0oe(w, (h, ((H,, (x. Hence, since (w, v) + 0,6(w, v.y)
is jointly differentiable in (w, v) for any y. it follows that h) + 8, h(z), Kr(( :) is also differentiable for any (I, y) by composition with the evaluation map (w, h) + (w, (h, K (x, which is differentiable. Hence, the sequence s,(2, v) converges to 0 for any (z.y) E X x V. Moreover, by the vean-value theorem, there exists S e S such that:
(1w,, h2) - (w, hill s5(,,)) - -ee
v) K(x,,) @ ((x, (h; h)
+ (w, - w) 0 M.. (,))))))
- oee (w, h(x),)) K(O,) :) @ K(x,) :) (h3 h) (w, ww) T 0 h (z), v) K (2,
where h,) = (1 (1- ew),,, h) + cy(wy, hy). Using the same construction as for the Fréchet differentiability, we find compact set W containing all elements (wy, hy(z), v) and (0,, hy(z). v) for any (I.y)= E X x y and all j large enough. On such set, aRE(w, v, y) and 02, lls, v. are bounded by some constant C. Consequently, we can write:
[I(w,, ht)) - (w, h)ll [|s) v)ll $2C' [K(x,) -) 8 K(x, :) (h2 - 1i)l + 20 |ww, - wil |[(x, 1 <2Ck 11b, - 1l1 + 2C (wy - wll
This already establishes that (), is bounded so that ED [lls] (z., ((F.,))))) w)ll converges to 0 by appli- cation of the dominated convergence theorem. Recalling Equation (26), ED [s,( v)] admits the following expression:
(wy,, hy) (w, h)ll ED [s) e)1 -i, h2) 0g
En [0ft (w, h())))))))) v) K (z. @9 K(a,) (hy - hi] (wy - w)) EED [o [ww, h(x)) v) K K(x,)) )].
40

---

The convergence to 0 of the above expression precisely means that L is differentiable at (w, h) provided that: (1) ED [ (w: h(x). y) K(x, -] is an element in Hd, and (2) the linear map g + Ep [ (w,, h( (K -) & (2x D)9] is bounded. Using the same strategy estab- lish Bochner's integrability of (z,z) + a,e (w, h(r),)) v) (x,,), :), we can show that (z.y) + L (w, h(x), 3) (xx,) is also Bochner-integrand
so that Ep [ h(x), y) (z, -)] is in- consider deed an element in Hd. This also establishes the expression of Lw, h). Similarly, the pverator-valued function Ç: (ar, v) + 8.e. (w, h(x), u) (xx,,) @ (xx,)) with values in the space of Hillbert-Schmie operators on H. The Hilbert-Schmiddt (HS) norm of such function satisfies the following inequality:
Ep [[ h(x), (xx,) @ ((x,)) mss == En [[ v) ((x,, 2)] S RC < toc.
Therefore, the function ş is Bochner-integrable, so that ED [ h K (z. @ K (ar, :]] is Hilbert-Schmidt operator satisfying:
Ep [øge(w, M(z), (x, @ K(x, -)] = IE, [oge (w, h(x),))))))))))))))) (K(z, @ K(x, ))g} Vy H.
The above property follows from [25, Theorem 6, Chapter 2] for Bochner-integrable functions that allows exchanging the integral and the application of a continuous linear map (here the scalar product with element g). Hence, from the above identity, we deduce the desired expression for of (w,h).
H Auxiliary Technical Lemmas
Lemma H.1. Let A and A' be two bounded operators from H. to IR,, and B and B' be bounded and invertible operators from H to itself. Assume that B 2 Aldy and B' 2 Aldu. Then, the following inequalities hold:
|| X2
|AB'I-A(BB)) ABB
op S
| 1--ll B'llop + || A' Alllpp
|AB-11 op
11Alop
-A
|A((')) < X -1 Ilp'
Proof.
By the triangle inequality and the sub-multiplicative property of the operator norm llops we
have:
|AB 1AB-I-A((B3) -AB-I-A'(B')-11 1lop S (1B8-'-A(B)-1111 + - - 1lop
(BB-1-(B))-)) + (00)))))___((1----00_0__)_))-1 (BA
1 | Allop ||B 1B---(B')-- (B') + ||4 A'l
A'llop (BB)) op
|| Allo BB- (B' (B') op + ||4 - A'll (B') loop
< Allop || 1lap 11'1|1 -Blon, (B') + -114- - A'l (B')
Bloop
op (27)
Since B 2 Aldx and B' 2 A Aldx, we obtain:
B op
and ||(B')-11(p S X
Substituting these into Equation (27), we get:
||Allop | B - B'llop + || A'llop- X²
| 1 A'(BB) <
This proves the first inequality. The remaining two inequalities follow directly from the sub- multiplicative property of the operator norm dlop and the assumptions B 2 AIdx and B' 2 AldR
Lemma H.2. Let f : 71 + R be a A-strongly convex and Fréchet differentiable function. Denote by h E H its minimizer. Then, for any E H. the following holds:
1| 10llxx S 1101l(
41

---

Proof. Let h E H.
Case 1: h²" The proof straightforward.
Case 2: + hi. Given that f is X-strongly convex, we have:
A
f(h) f(h²) 2 (O.J(h"), - 10)x +
|| ht" 11
2
X
and f(h²) - I(N) 2 (O. 11 +
||
h- 11
After summing these two incqualities, noticing that f 0, and rearranging the terms, obtain:
(0n,((),,--1))) 2 A 11-11"1p 11
After using the Cauchy-Schwarz inequality, get:
[0,5(1)) |/ 10 10 2 11h 11"l12
Dividing by ||h h" 11x + 0 concludes the proof.
Lemma H.3, Let X be a subset RR,, y be subset of R&, and D be a probability distribution over X x y. Given i..dd samples (x,, yilsssn drawn from D, consider function X x y - R of
class C such that the operator A : H + H. defined as:
1 Σ 71
= B( D. K(
gl,, Me (()))
K (())))
Hilbert-Schmidt Then, the following holds:
||| 1i -B( g(x, v)g(e', .'' (x
1
Σ
g( w)) (2))
n² T===
2
Blw g( ( ())((, k² (x, mii)
Proof. Define s (x,)) ((x,,))(( @ K(x,)) and En g(T,, (Ix,-) &
() We have:
|||| -|s- || + || 2 (s. (s,8)mm) H)
(28)
42

---

Next, we compute each of the following quantities: ||s HS. |$] HS. and (s, H) separately. Simple calculations yield:
|| liss (=)))))) (9(2, y) (x, @ (x, Ill
& K(x', 1))) (xaa) // g(x v)g(2', v/) (K( @ (, K(2', HS
(B( (0 y) ((x -) @ [z, -) lo
(ora)) a/ (( v)9((' K xx)
||$]
( UI K (( (x.,))
HS
122
g(2,, (I ) K( -), Σ ((2,,, K(z),))
n²
HS
g(z,. (x @ K(x,.)). ( K, @ K(z )ss
i.j
n2
1,==1
( (o(,,y)K(z, ) K(x )), + (( @ K(t;.))
(s, Hs
i=1
E (n ())(a,)) v) (K(x,-) @ K( -), K(x..)) @ K (2,,, Hssl
El..y) g( (1) ( (z, x:)]
After substituting the obtained results into Equation (28) and rearranging, we obtain:
1
|| = (e
( v)g(2' 8/)
Σ
g( (1)((, (x),
n² $J==
2
E (L.w))D g(z,, (1)((1)))) 8) 2.))
I Details on Experiments and Additional Numerical Results
In this section, provide details on the experimental setting used to obtain Figure and include additional numerical results Appendix I.5. We recall the formulation of the instrumental variable regression problem introduced in Section 2.2:
1 - E(r,)> [In((a)) - w1² 2
min F(w)= = Lone(w, (Z) weRd
1 s.t. h arg min Lin (w, h1) Elzise - -T000] + | hE7t
where (t)) ( (1).... (T)) E Rd is the feature map. We begin by deriving a closed-form expression for An (the empirical counterpart of ht), which is key to obtaining closed-form expressions for F(w) and FW(W), and thus accurate approximations of F(w) and F.F)w..
43

---

I.1 Closed-form expression for h.
Let E Id. By the first-order optimality condition, the gradient of T.in with respect to its second argument must vanish at has i.e. oj Ln (w, hw) O. Proposition B.I implies that h satisfies the following equation:
(Zi( - ((t)))((a))) + Ahw 0,
with (I,; sissin being samples drawn from the distribution PP. After using the reproducing property of the RKHS H and rearranging the terms, we arrive at the following closed-form expression for hw:
h = (5x
3)) w E H,
where Σx - Ady is an operator from to with Σ Σド
the empirical covariance operator and क - ((4),((,,))) n E.= K( :) (( being
= 10,,..,, E Hd. Next,
we compute closed-form expression for Σx 4, which can be determined as the solution (b......ba) ba)T HH of the following minimization problem:
b arg min b S. - by o,. for any 1 S bEE
After expanding the terms and rearranging, this minimization problem is equivalent to:
bi arg min (bbb((z))..... b(()n) [(bellz), for any 1 S d,
bEH
where, for any e1. e1...., Cn. e E R. (I(e,..... en e) = 1
2n E ot - E @i(t,)e; + 2²²2. By
the representer theorem, for any 1 S I d, by can be expressed
S, (..K(zx)))
=
where č; (ÉI.).... TT. R2 satisfies:
d cf Ke, K c: +
è arg min 1 (Kc]).... cil....., K ciln, cf Kc.) = 2n c K2 c C
F
2
where F,
(tx))) E R By the first-order optimality condition, we have:
Ve, Vi (K&)
ē:)
KK ēiJn, oj K k() O. which results in é; (K +ndlnxm) F.ER".
Using this, we obtain:
b = c. (K(1))) K (zns
T, for any < l U d, and thus: h. = w.. w.
Now that we have obtained a closed-form expression for has we can express F(w) and V in closed-form, we will see next.
1.2 Plug-in estimators for F(w) and VF(ww)
Let (ā,, (ej,ū))ssss be m samples drawn from Q and w E Rdd We have:
F(w) = 2m
1 m
(T(()))) M1 2
Bw 3/
2m
j=1
where B = 16(51),... [T E gmmdd and ý = (ū),... Fm T E Rmm, For any 1 5 l < d and
1 5 j 5 m. have:
(xt))) F (K +nAInnxa)
K
44

---

As consequence, we obtain:
b(ā;) = (2)).......... (a()))) = =c¹ K E CR"
where Č [11, (c,--..,co cd] (K +nAl axn)
F Raxd with F [i Fal R This
implies that = K C Ruxd and hence:
F(w) 1
2m w ( K KCW 1. Ly K Cw + 2m
K C
(29)
2m
On the other hand, using Appendix C, we get:
(KCW-KKKTTT) (KŌ) VF(w)- K K (KŌW- (KŌW-S) m ( KC
Rd.
(30)
m
The exact expressions of F(w) and V((ww) involve expectations and are therefore intractable to compute analytically. A natural approach is to approximate these quantities using their plug-in estimators F(w) and V.(w), evaluated with very large number of inner and outer samples, n and m. However, this approach quickly becomes computationally and memory-intensive. In particular, storing the kernel matrices K and K requires O(n²) and ((n) space, respectively. incurs cubic time complexity of O(n²), which
Moreover, computing the inverse (K +nAlnxa) prohibitive for large-scale applications. To alleviate these computational bottlenecks, potential strategies rely on classical techniques in kernel methods such as Random Fourier Features (RFF), which approximate kernel functions in a mnte-dimenniona. feature space and enable more efficient gradient computations [60], and Nyström approximations, which mitigate the computational burden of full kernel matrices by using a low-rank approximation of the kernel [75]. In our experiments, we leverage the closed-form expressions of the plug-in estimators, and replace the kernel evaluations with their approximations via RFF. This enables us to construct efficient and scalable approximations of F(w) and V.F(w), while significantly reducing both the memory usage and the computational cost. Our approach will be discussed in the following.
1.3 Scalable approximations for F(w) and F(w))) via random Fourier features
Random Fourier Features (RFF) provide a way to approximate shitt-invariant kernels (i.e., kernels that satisfy K(x, x²) G(z x') for some function G X' + I)) by mapping the data into randomized feature space. To avoid the high computational burden of building the full kernel matrix from all pairwise kernel evaluations, RFF use randomized feature map & : X RD, with D being the number of Fourier features, to approximate the kernel as follows:
K(x, x') R (bxx) (xx),, for any x, E X.
Now, we derive the expression of the feature map th. Let E X. By Bochner theorem [16], we have that:
(x-xa)) K(r,x')= = (2xr)p E Bl
[e-""(==a)) = (2xTpp
1
E w [cos(w (x x') x'))] (31)
where G is the Fourier transform of G. For any b IR the following product-to-sum identity holds:
2 cos(w' T x + b) cos(w" T x' + b) = cos(2b b + w (x + z')) + cos(w T (x x()). In partieular, when b (1(0,,21) 2T) (the uniform distribution over [0, 2m)) get:
12 cos(ww _0-200
+ b) cos(w" x' + +b]] =Ep-21 [cos(2b + w + 2')i|
+ cos(w xx))
However, we have:
1 2n
E,-2((022)) (c0s(2b+ TT (xx x'))|
cos(2b + w (ar + x²)) db
2n
1
[2b + w (x 1> 0.
4m
45

---

Thus:
(0,2x) [ cos(w') x + b) cos T x' + b)] cos(w (x - x2]).
Substituting this back into Equation (31), we arrive at:
(xx, = -E (2m)e ((w),6-(((022))
V2 cos(ww T x b)v cos(ww (w| x'' + b) (27) (2 G(w) and andbb..... bI....,,b ~0 2 bn
Using D samples W WD
we obtain by Monte Carlo
estimation:
((x,2)
~
Σ
D
V
2 cos w xb))
(v cos cos(ww) x' + bii)
This implies that:
(bxx) V cos W x+)), where W (Wi,.... WD) R and b bp) E R...
2
In practice, one typically chooses D < and D < m, which reduces the space complexity of storing K from Onn²) to O(nD), and that of storing K from O(nm) to O((n + D) This results in significant computational and memory savings. Using the RFF approach, the two kernel matrices K and K can then approximated as:
K and K EET,
where E = [1b())....... (In))T E BaxD and Ehr (vt)), ...., ((t,)...,"ūmm.. E RmxD common term in Equations (29) and (30) is K C, which can be approximated using the push-through identity
follows:
KČ + mmInnx)) " = + " =T
R m
Here, instead of inverting a matrix size n, invert matrix of size D x D, which leads to significant computational savings in time, especially when D < n. Consequently, using this approximation, we get:
JJ 1
F(w)= 2m
JE
2m 1813
m
1
VJ(w)
m
where J = -ET= + px) -TE Dxd, As mentioned earlier, very large number of samples n and m is required to obtain accurate approximations of F(w) and V using the RFF approach. To cope with the issue of storing the two matrices E Rax and E Rm* in memory, we implement this method in blocks. More precisely, we divide our data (I 4)sssgn and (āj, isism into blocks, then compute E ET F. F. y, and |0|| as follows:
= Σ (a))(a)) Σ> Σ
(1))((=)
Σ E E DXD
REB
BEB
m
ETE (a,)((a)))
Σ
Σg
((T)
Σ
T E DxD
BEB
BEB
E Σ (x:) (1), Σ Σ
= Σ F ER
BEB (x.))e
BсB
ETy (ūt)ūū = Σ Σ
{E)ū = E ERD,
BEB (3.0)B
BEB
11912 Σ 1912.
BEB
where B denotes the set of blocks, and the subscript B indicates that the corresponding quantity is computed using only the data contained in block B. These wise computations make possible to precisely approximate F(w) and (F(w) in scalable manner. As a result, we can efficiently approximate both F(w) and V.FWW) through their plug-in estimators when choosing large sample sizes and
46

---

1.4 Additional details on the experimental setup
We use the JAX framework [18] to run our experiments on an NVIDIA RTX 6000 ADA GPU. The experiments take approximately 15 hours to complete.
Choice of the kernel. In our experiments, consider the Gaussian kernel defined, for any z, x' X, as ((r,
-ليي where a 0 is the bandwidth parameter controlling the smoothness. Since the Gaussian kernel is mranlation-invariian Bochner's theorem is applicable. In this case, using the same notations as in Appendix I.3, have G(z)
1all2 20
for any z X. Its Fourier transform
G is then given by G(w) (2TT²) 8 -l for any w E R. As a consequence, we obtain:
(2 G(w)
(2xr) (2ma²)=
11
2T
1 = -N ( (2x0.22bxx))
e
0²
which implies that Wi...., WD N(0 2 Lpxp).
Choice of the statistical model and hyperparameters. Wesetp 4, 0.01, and 0.2. We generate synthetic data as follows:
Par -(1, == tc,
where ~ (0, 0.025), ~t ~ (0,, 1)d, and (t)) (sin(t + 1).... sin(t t + d)) We consider two cases for the distribution P. of the instrumental variable z: (i) a p-dimensional standard Gaussian, i.c., Ps = (0, 4 4pxp), and (ii) p-dimensional Student's s t-distribution with degrees of freedom E
2.9). All random variables are fixed across runs for reproducibility.
1.5
Additional experimental results
Here, we retain the same experimental setup as in the main paper and extend the analysis by providing additional experimental results in the scenario where both and vary simultaneously
the range 100 to 5000. In Figure 3, we visualize the results using heatmaps for four key quantities: - (wo)), V.F(w)) - ( |I F []. and min;=o.....7 T F (w:: Il. with on the r-axis and m on the y-axis. We report the results only for the case where the instrumental variable is sampled from a p-dimensional standard Gaussian, since the cases where æ is sampled from p-dimensional Student's f-distribution with degrees of freedom V/ E {2.1, 2.5, 2.9} exhibit similar trends. From the heatmaps, diagonal of the plots, i.e., when m = n. This pattern suggests that matching the number of samples in the two dimensions leads to more accurate estimation of both the objective function and its gradient, as well as improved convergence behavior during optimization.
observe that the lowest eπrors across all four metrics occur along the
Distribution of the Instrumental vartable: standard Gaussian
[/(wa] - Ras)
[V [f(mm)
[
min [[/((.)) )
100
100
100
100
-1.5
-2.0
-2.
5000
5000
5000
5000
1000
500
1000
100
5000
12
12
Figure Ilustration of gradient descent on (KBO) for the instrumental variable regression task using synthetic data, with an instrumental variable sampled from a standard Gaussian distribution. The logs of the means of the four quantities across 50 runs are displayed.
47

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper claims to provide new generalization bounds for bilevel optimization using kernel perspective. These contributions thoroughly discussed and validated in both the theoretical and experimental sections. The proofs are available in the appendix.
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 be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper is of theoretical nature. We clearly explain and discuss the theoretical assumptions under which the results are applicable. Additionally, we include a separate "Limitations" section in the conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (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 or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
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
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
48

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We state all assumptions in the paper and include proof sketch of our result in the main text; complete proofs are provided 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 in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if 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 perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We conduct experiments on the instrumental variable regression task using synthetic data. All essential details needed to reproduce the experiments are provided in the main text, with additional information available in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
49

---

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: [Yes]
Justification:
We made our code available at htttps://github... httpe//bbccoo/ttrteeeeeaooooro//
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/ httpe//guuidee/oeeeuuuuuee
wwwsssssonoiiiiyi.o 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: / //tpps.ccppbllliee/ cc/public/geieeccccccccccc wtwp///g///////eee//eeccce/sseet http://ooeSSuiisseeeeeeee
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. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental setting is provided in the main, and additional details are available in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We
experiments 50 times and report error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
50

---

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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We report these additional experimental details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https https://neet :/tppp::///uuupp/// cc cctppblic////cccccccccccccccclcc httpe/titihiiieliiiiiieeeieeeeee
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics. The research conducted in our paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There are no immediate societal impacts of our work given that it is mostly theoretical.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
51

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that 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 or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper 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 does not involve data or models with high risk misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We cite the papers we used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
52

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/c datasttss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets in this work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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.
53

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core methods of this research do incorporate LLMs any significant unusual way.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy pectp::/neuurjee http://s..../ooooeeeeee///////3/ for what should or should not be described.
54


Reviews:
[{"review_id": "FcE4QtjZNY", "reviewer": "Reviewer_9Xjf", "summary": "This paper develops the first finite-sample generalization bounds for nonparametric bilevel optimization with inner optimization on reproducing kernel Hilbert spaces. Specifically, it gives an explicit gradient expression using implicit differentiation and then derives uniform generalization bounds for both the bilevel value function and its gradient using empirical process and U-process theory.", "questions": "- Could the authors comment on the possibility of relaxing Assumptions (C) and (D)?\n- Can your framework extend to stochastic bilevel algorithms (e.g., [3,24])?", "limitations": "Yes. The limitations and scope are clearly discussed in Section 6.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The work is technically solid, leveraging advanced empirical process methods to handle infinite-dimensional inner spaces for both function and gradient approximations.\n- The paper is overall clearly written. The main ideas and proof strategies are well organized, with clear motivation, literature review, and fully discussed theoretical assumptions.\n- Bilevel methods underpin many ML tasks (hyperparameter tuning, meta-learning, causal inference), yet lack nonparametric generalization theory. This fills a fundamental gap.\n- It introduces a novel perspective to investigate the theoretical properties of bilevel optimization with kernels, which may largely inspire future work to loosen the inner problem's constraints.\n\n**Weaknesses**\n- The assumptions (e.g., smoothness and convexity) are relatively strong and may not hold in more complex or practical settings. It would be valuable to validate these assumptions empirically for real-world kernels, though this is admittedly a challenging task.\n- Analysis focuses on basic gradient methods.", "was_revised": true, "final_justification": "The authors' response addressed my concern. My recommended score remains unchanged at 5, as it was based on my original recognition of the work, which was not initially affected by these concerns.", "rebuttal": "Dear Reviewer,\n\nThank you for providing feedback and highlighting the strengths of our paper. Below, we address your concerns and welcome any further questions.\n\n### **1- Assumptions** \nWe will add the following discussion on the assumptions.\n- **Assumption (A) – Boundedness of the kernel $K$.** We require $K$ to be bounded, which holds for the most commonly used kernels (Gaussian, Laplacian, Matérn, spline, etc.). It also holds if $K$ is a Mercer kernel, i.e., a continuous, positive‐definite kernel on a compact domain $\\mathcal{X}$. For instance, a kernel built using neural network features (e.g., Neural Tangent Kernel) satisfies this assumption on the space of images, which is compact (pixel values have bounded range). \n- **Assumption (B) – Compactness of the set of the labels $\\mathcal{Y}$.** In most supervised learning applications, this assumption is immediately met. For example, in regression tasks one often has $y\\in [a,b]$ (e.g., probabilities in [0,1] or physical measurements on a known scale), which is compact. Similarly, in classification problems $\\mathcal{Y}=${$1,\\dots,C$} is compact.\n- **Assumption (C) – Regularity of pointwise losses.** This assumption holds for most loss functions used in practice, including the squared loss, logistic loss, cross-entropy loss, and KL divergence. This assumption no longer holds when considering SVM with the hinge loss. To handle such a case, one would need to extend the analysis to a non-smooth setting, which would be an interesting future work direction.\n- **Assumption (D) – Convexity of the inner loss.** What makes this convexity assumption mild is the fact that it is made on the variable $v$, which corresponds to the value taken by a prediction model $h$. This is weaker than making a convexity assumption with respect to the parameters of such a model. For instance, as discussed in (Petrulionyte et al., 2024), in the case of a neural network model, convexity in the parameters would not hold in general, but it would still hold in the values taken by the model for most commonly used losses in practice, such as the squared loss, logistic loss, cross-entropy loss, and KL divergence.\n\n### **2- Extension to stochastic bilevel algorithms** \nWe thank the reviewer for this insightful question. While our theoretical analysis focuses on a **full-batch** bilevel setting with **exact gradients**, the proposed framework could be extended to stochastic variants. A promising direction would be to consider **approximate kernel representations**, such as **random Fourier features** or **Neural Tangent Kernels**, which enable scalable learning using kernel methods while preserving useful theoretical properties. These extensions lie beyond the current scope of our work and represent an exciting direction for future research. We will make sure to clearly highlight this point in the conclusion of the revised version.\n\nBest regards,\n\nAuthors\n\n---\n\n**Reference**\n\n(Petrulionyte et al., 2024) I. Petrulionyte, J. Mairal, and M. Arbel. Functional Bilevel Optimization for Machine Learning. NeurIPS 2024."}, {"review_id": "Ma57PeltMn", "reviewer": "Reviewer_cVHc", "summary": "The paper studies generalization properties of Kernel Bilevel Optimization (KBO). This task comes with many additional challenges compared to existing work (e.g. the parameter space growing with sample size for kernel methods), which the authors solve with several technical contributions. \n\nThe first contribution is showing that differentiation and plug-in emprical estimation of gradient derived via implicit differentiation commute under specified assumptions. Secondly, based on the commutative property the authors derive generalization bounds in Theorem 4.1 using the maximal inequalities for degenerate U-processes of order 2. These two results form the core of the paper and the intuition behind the proofs is well described. There is an additional result for gradient descent solver of KBO. Numerical experiments match the the theoretical bounds asymptotically when the sample size of the inner and outer loops are the same (m=n), although the scaling in terms of $m\\neq n$ is not explored numerically.", "questions": "* In the first block equation in 2.2, is the distribution of $x,y$ in the expectation different, i.e., that one of them is on train and the other on the test data? I think it would be useful to explicitly highlight in the equation.\n* In the experiments you show an experiment when $m = n$ which does not demonstrate the theoretical scaling of $1/sqrt(n) + 1/sqrt(m)$. Could you vary $m$ and $n$ to show the scaling in both dimensions? This might reveal that the upper bounds are not tight in this regime, but it would be still very important to know.\n* L213: Claim that [6, 61] do not hold for parameter dimension growing with $n$, thus not for kernel methods. Is it possible to make some comparison for the asymptotic scaling in m or n?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Overall, the paper in my opinion makes significant contribution and is written with great detail (although I checked the appendices only very quickly).\n\nFor weaknesses, I have mostly minor suggestions hoping to help with clarity for other readers and a remark, that I would like to see the experimental results when $m\\neq n$, perhaps as a figure in the appendices.\n\nSuggestions for clarity:\nThis is a long paper and I imagine that it was difficult to fit it into the page requirement.\n* If I understand correctly Sec 2.3. is about the difficulty to performing implicit differentiation (which is needed for KBO) for a kernel method. If this is the main point of Sec 2.3. and Prop 2.1, I think the clarity of the text would be improved if this was briefly stated at the beginning to motivate the section. Generally, I would like to better understand the purpose of Prop 2.1 (I guess it is later explained as motivating the plug-in estimate in 3.2), and also to have explained the intuition how it gets around the intractibility of the block equation above. \n* L156: Can you specify which of the operator is abstract and intractable? My guess it is the $\\nabla_h$, but it would improve clarity to be precise.\n* Literature review: I find the literature review very short, which might be also due to the page limit restrictions. Nevertheless, I want to ask the authors to extend this and perhaps include a short section in the appendices that gives:\n    * A short paragraph of few sentences on computational aspects of solving KBO and existing approaches. \n    * A few sentences about the existing generalization results for Bilevel optimization. There is a paragraph in L207 saying why the existing results don’t hold for kernel bilevel optimization, but it would be useful to have some information about the scaling of the existing bounds for the non-kernel case.\n\nL224: “and show that it recovers the previously introduced estimator $\\nabla \\hat{F}(\\omega)$”, this is technically not accurate as only $\\hat{F}(\\omega)$ was introduced previously and its gradient is firstly written right below.", "was_revised": true, "final_justification": "I am very happy with the paper and the way the authors addressed my questions. I decided to keep the scores.", "rebuttal": "Dear Reviewer,\n\nThank you for your thoughtful review of our paper and for your valuable suggestions for improvement. We answer your concerns below and are happy to clarify any further concerns you may have.\n\n### **1- Clarifying the purpose of Section 2.3** \nThank you for this helpful comment. As suggested, we will explain at the beginning of the section the following idea: Section 2.3 adresses the challenge of performing implicit differentiation for KBO. This first requires deriving an abstract, a priori intractable, expression for the implicit gradient, from which we derive a more concrete expression in Proposition 2.1. By concrete we mean that it requires solving a regression problem in the RKHS (the adjoint problem), which can be approximately solved using finite samples, and plug it into an expectation (which can be also approximated using finite samples). Hence, Proposition 2.1 lays the ground for defining a plug-in estimate, later used in our statistical analysis, and which allows getting around the intractability of the implicit gradient.\n\n### **2- Abstract operators in L156** \nThank you for noticing this point, the phrasing is indeed vague. The operators we meant include $\\partial_h$, but also $\\partial_h^2$ and $\\partial_{\\omega, h}^2$, which appear when replacing the Jacobian $\\partial_\\omega h^\\star_\\omega$ by its expression in Equation 1. We will make sure to be precise about which operators we had in mind in the revised version.\n\n### **3- Literature review** \nThank you for the suggestion. We will add the following in the appendix of the revised version of our paper, which also answers your question about L213.\n- **Computational aspects of KBO.** The computational complexity of KBO algorithms typically scales cubically in sample size as for many kernel methods. For example, in the case of kernel instrumental variable regression (Singh et al., 2019), solving the inner level system costs $\\mathcal{O}(n^3)$, and performing vector matrix products operations costs $\\mathcal{O}(mnd)$, leading to a total complexity of $\\mathcal{O}(n^3+mnd)$. To improve scalability, potential strategies rely on classical techniques in kernel methods such as **Random Fourier Features**, which approximate kernel functions in a finite-dimensional feature space and enable more efficient gradient computations (Rahimi & Recht, 2007), and **Nyström approximations**, which mitigate the computational burden of full kernel matrices by using a low-rank approximation of the kernel (Williams & Seeger, 2001).\n\n- **Existing bounds for the non-kernel case.** Bao et al. (2021) laid foundational work in this direction by analyzing uniform stability in full-batch bilevel optimization. Their criterion for generalization compares the population outer loss evaluated at the output of a randomized algorithm to the empirical outer loss evaluated using the same algorithm. Given a number $\\kappa$ between 0 and 1, they obtain a decay at a rate of $\\mathcal{O}(T^\\kappa / m)$ for unrolled optimization, which decreases as $1/m$ in outer sample size, but increases with the number of outer iterations made. The generalization criterion is unlike the one we consider and which compares the population outer objective at the theoretically optimal inner solution $h^\\star_\\omega$ to the empirical loss evaluated at the empirical solution $\\hat{h}_\\omega$. Complementing this upper bound, Wang et al. (2024) established lower bounds on the uniform stability of gradient-based bilevel algorithms, demonstrating a rate of $\\Omega(1/m)$. Building on (Bao et al., 2021), Zhang et al. (2024) extended the analysis to stochastic bilevel optimization, establishing on-average stability bounds and deriving a generalization rate of $\\mathcal{O}(1/\\sqrt{m})$ due to the presence of stochastic gradients. In a related context, Oymak et al. (2021) studied generalization in neural architecture search using a bilevel formulation, showing that approximate inner solutions and Lipschitz continuity of the outer loss yield a generalization bound of $\\mathcal{O}(1/\\sqrt{n}+1/\\sqrt{m})$. Arora et al. (2020) investigated representation learning for imitation learning via bilevel optimization, offering generalization bounds of order $\\mathcal{O}(1/\\sqrt{m})$ that depend both on the size of the dataset and the stability of learned representations.\n\n### **4- Clarification on $\\nabla \\widehat{\\mathcal{F}}(\\omega)$** \nWe apologize for the confusion at L224 and thank you for pointing this out. We considered two estimators: $\\nabla \\widehat{\\mathcal{F}}(\\omega)$ (first defined in L199 in the text as the gradient of $\\widehat{\\mathcal{F}}(\\omega)$) and $\\widehat{\\nabla\\mathcal{F}}(\\omega)$ which is indeed defined after L224 in Equation 4. In L224, we were referring to the first estimator $\\nabla \\widehat{\\mathcal{F}}(\\omega)$. To make this clear in the text, we plan to add in Section 3 a reference to Proposition B.1 in Appendix B, where the detailed expression of the first gradient estimator $\\nabla \\widehat{\\mathcal{F}}(\\omega)$ is provided.\n\n### **5- Inner and outer distributions in Section 2.2** \nThank you for the suggestion. You are correct: the expectations correspond to different distributions (training for the inner and test for the outer). We will update the equation in the revised version of our paper to explicitly highlight this distinction for clarity.\n\n### **6- Experiments** \nThank you for suggesting the addition of experimental results in the case where $m \\neq n$: we find this to be a valuable and interesting experiment. To provide these results, we retain the same experimental setup as in the main paper and vary both $m$ and $n$ simultaneously between 100 and 5000. For each distribution (standard Gaussian and Student’s $t$-distribution with degrees of freedom 2.1, 2.5, and 2.9), we plot heatmaps of the quantities of interest, with $n$ on the $x$-axis and $m$ on the $y$-axis. These quantities include $|\\mathcal{F}(\\omega_0)-\\widehat{\\mathcal{F}}(\\omega_0)|$, $\\lVert\\nabla\\mathcal{F}(\\omega_0)-\\widehat{\\nabla\\mathcal{F}}(\\omega_0)\\rVert$, $\\lVert\\nabla\\mathcal{F}(\\omega_T)\\rVert$, and $\\min_{i=0,\\ldots, T}\\lVert \\nabla\\mathcal{F}(\\omega_i)\\rVert$. We plan to include them in the appendix of the revised version of our paper. Here, since all cases show similar trends, we report only the results for the Gaussian case and focus on the quantity $\\lVert\\nabla\\mathcal{F}(\\omega_0)-\\widehat{\\nabla\\mathcal{F}}(\\omega_0)\\rVert$. The following table summarizes the results for $m, n \\in$ {$100, 500, 1000, 5000$}.\nAs observed, the quantity decreases as both $m$ and $n$ increase, and so is the upper-bound. However, we are unable to experimentally assess the tightness of the upper-bound at this stage.\n\n|$n \\backslash m$ | $\\mathbf{100}$ | $\\mathbf{500}$ | $\\mathbf{1000}$ | $\\mathbf{5000}$ |\n|:----------------:|:----------------:|:----------:|:--------------:|:-------------:|\n| $\\mathbf{100}$ |0.0340 | 0.0289 | 0.0235 | 0.0200 |\n| $\\mathbf{500}$ |0.0265 | 0.0110 | 0.0090 | 0.0076 |\n| $\\mathbf{1000}$ |0.0195 | 0.0081 | 0.0066 | 0.0056 |\n| $\\mathbf{5000}$ |0.0152 | 0.0063 | 0.0044 | 0.0023 |\n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n(Singh et al., 2019) R. Singh, M. Sahani, and A. Gretton. Kernel Instrumental Variable Regression. NeurIPS 2019.\n\n(Rahimi & Recht, 2007) A. Rahimi and B. Recht. Random Features for Large-Scale Kernel Machines. NIPS 2007.\n\n(Williams & Seeger, 2001) C. K. I. Williams and M. Seeger. Using the Nyström Method to Speed Up Kernel Machines. NIPS 2001.\n\n(Bao et al., 2021) F. Bao, G. Wu, C. Li, J. Zhu, and B. Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. NeurIPS 2021.\n\n(Wang et al., 2024) R. Wang, C. Zheng, G. Wu, X. Min, X. Zhang, J. Zhou, and C. Li. Lower bounds of uniform stability in gradient-based bilevel algorithms for hyperparameter optimization. NeurIPS 2024.\n\n(Zhang et al., 2024) X. Zhang, H. Chen, B. Gu, T. Gong, and F. Zheng. Fine-grained analysis of stability and generalization for stochastic bilevel optimization. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024.\n\n(Oymak et al., 2021) S. Oymak, M. Li, and M. Soltanolkotabi. Generalization guarantees for neural architecture search with train-validation split. ICML 2021.\n\n(Arora et al., 2020) S. Arora, S. Du, S. Kakade, Y. Luo, and N. Saunshi. Provable representation learning for imitation learning via bi-level optimization. ICML 2020."}, {"review_id": "ouMBoM4Zmo", "reviewer": "Reviewer_ELKB", "summary": "The paper proposes the formalism of kernel bilevel optimization, a way to frame a specific instance of a recently proposed functional bilevel optimization setting in terms of reproducing kernel Hilbert spaces (RKHSs) - thereby making it nonparametric. The inner optimization problem is given by a classical ridge regression / Tikhonov regularized objective with a generic loss function, which is often found in the kernel literature and allows for the application of a representer theorem.\n\nA gradient-based plugin estimator is investigated. The theoretical core contributions are worst-case inequalities for the distances between the empirical and analytical versions of the objective as well as its gradient in expectation. The regularity assumptions are typical and relatively mild. The bounds exhibit an additive dependence on a split sample with 1/sqrt in both sample sizes each. They also exhibit a generic multiplicative constant which is briefly explained in the main text and in a more detailed form throughout the appendix. For example, a typical diameter-type dependence on the compact parameter domain (outer objective) as well as a regularization parameter dependence (inner objective) are the two most obvious properties reflected in the constant.\n\nThe authors propose a gradient scheme and give generalization bounds in expectation, showing a similar sample dependence as before as well as an additional 1/sqrt dependence on the iteration number under additional positive definiteness assumptions. The structure and assumptions of this bound seem to be classical within the context of first-order optimization theory. Finally, a very basic synthetic experiment for the specific instance of kernel instrumental variable regression framework as proposed by Sing et al. (2019) is performed, supposedly confirming the theoretical findings.", "questions": "I suggest the authors address the following two points:\n\n1) Using the additional space in order to expand the remarks and discussions around the constants in the main text and add some additional insight about how they depend on parameters related to the problem and the gradient scheme. In particular, I believe the interplay between regularization theory in the inner objective and optimization theory in the outer objective should be interesting to the reader. Furthermore, expanding the discussion of the constants might allow to highlight connections to available results in a more direct way. Note that Corollary 4.2 could specifically benefit from additional remarks.\n\n2) Discussing available results for the applications they list as motivation in order to consider KBO. In particular, how do these results relate to the new findings in the new, more general KBO setting? In particular, for kernel instrumental variable regression as given by [1], the two stage estimator allows the direct application of high-probability lower and optimal upper bounds for kernel ridge regression with vector-valued kernels [2], leading to minimax optimality for the instrumental variable procedure [3]. It seems reasonable to believe that similar arguments can be made for the inner objective of KBO under suitable assumptions about loss and noise, potentially leading to a fundamental lower bound. It might also be insightful to briefly mention relevant classical upper and lower bounds for general gradient schemes in the context of the outer objective in the main text. \n\nA minor technical point:\n\nMeasurability of the kernel needs to formally be required in order to ensure that expectations of functions and embedded variables in the RKHS are well-defined (e.g. [4, Chapter 4]). I think this could be added to the formal assumptions, in particular since the rest of the paper is written quite rigorously. \n\nThere is another very general question which is outside of the scope of the paper. I wondered the following:\n\nTwo-stage kernel instrumental variable regression as given by [1] uses a vector-valued ridge estimate in *both* stages.\nThe work [3] proposes to use a general spectral algorithm [5] for the *first* stage. \nIt is known that general spectral algorithms include iterative schemes such as gradient descent. If, instead of in the first stage, one uses a general spectral algorithm in the *second stage*, this might lead to a very similar (or even the equivalent) estimator that the present paper proposes in the special instance of instrumental variable regression and could lead to optimal rates by repeating the arguments by [3]. Incorporating loss calibration results [4] could allow to transfer these rates to more general losses.\nMaybe the authors also have some better intuition or opinions about this.\n\n[1] Singh et. al. Kernel instrumental variable regression. NeurIPS 2019.\n\n[2] Li et al. Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm. JMLR 2024.\n\n[3] Meunier et al. Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal. arXiv:2411.19653 2024.\n\n[4] Steinwart & Christmann. Support Vector Machines. 2008.\n\n[5] Meunier et al. Optimal rates for vector-valued spectral regularization learning algorithms. NeurIPS 2024.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "I see the main contribution of the paper in the abstract framing of nonparametric bilevel optimization with generic loss functions and the first steps towards analyzing KBO theoretically, which this paper manages to do well. \n\nThe derived error bounds are of relatively simple type (analytical regularized loss vs. empirical regularized loss, no ground truth assumptions and corresponding convergence theory for $\\lambda \\to 0$, only expectation bounds, no high probability bounds under noise assumptions, no fast rates, no lower bounds), but sufficiently outline core properties of the proposed estimator under relatively weak assumptions as a first step towards a theory of KBO. I do think that the main paper could benefit from a bit more insight that the appendix provides, in particular with regard to the structure of the multiplicative constants in the bounds. This could make connections to related theory more clear. This will also open up additional avenues for further investigation, which I believe are plentiful.\n\nNevertheless, I believe the contribution should be sufficient for the paper to be accepted, as this can be addressed during the rebuttal phase by adding suitable comments and using the additional space.\n\n**Strengths**\n\nTo my understanding, this is the first time that kernel-based bilevel optimization is discussed in this form of abstraction.\n\nGenerally good presentation and accessibility; newcomers to the field should be able to read and understand the basics of this work without significant issues.\n\nAppropriate degree of mathematical rigor, formalism and attention to detail in technical writing.\n\nThe generality of the proposed formalism will allow more targeted investigations based on known theory and techniques from adjacent fields and allow more detailed analyses.\n\n**Weaknesses**\n\nThe paper lists two applications as motivation in order to investigate general KBO, in particular distribution shift and instrumental variable regression—the latter is specifically investigated in the experiment. However, the authors do not compare their theoretical results and their proposed gradient scheme to existing results for those applications (to which they are inherently related). It is left unclear when (and how) their results extend these applications and/or give new insights.\n\nI also believe that the main paper hides a lot of theoretical insight in the generic multiplicative constants, which are given in full detail the appendix. In particular, connections to regularization theory and vector-valued regression (inner objective) and general optimization (outer objective) will become more obvious and make the results comparable to related work in those fields; see “Questions” section.", "was_revised": true, "final_justification": "The authors have addressed all points and I maintain my rating.", "rebuttal": "Dear Reviewer,\n\nThank you for your detailed review and thoughtful comments. We are pleased that you found our paper strong and appreciate the constructive suggestions to improve it. Below, we provide detailed responses to your remarks, and we would be happy to address any further questions you may have, should any of our responses require clarification.\n\n### **1- Discussion of the constants** \nWe agree that a more explicit expression would be beneficial. In our case, the most interesting dependence is w.r.t. $\\lambda$ as it (1) controls the strong convexity of the inner objective and the smoothness of the outer objective (see Proposition C.4 of Appendix C.2), crucial for optimization, and (2) allows providing generalization for the un-regularized problem ($\\lambda= 0$) by controlling the behavior of such constant as $\\lambda$ approaches 0, provided additional source assumptions are made (e.g., Smale & Zhou, 2007; Sriperumbudur et al., 2017). Under our current relatively weak assumptions, we are not able to characterize the exact dependence of the constants on $\\lambda$, especially to control the behavior of the constant as $\\lambda$ decreases to 0: parts of the terms in the constant have only a qualitative dependence on $\\lambda$. Providing more quantitative estimates would require stronger regularity assumptions such as Lipschitzness of some of the derivatives. Our choice of assumptions is partly motivated by the simplicity of the resulting proofs; however, it is possible to adapt the proofs to get more quantitative dependence on $\\lambda$ and provide generalization errors for un-regularized problems, which would be a great future work direction. We will still add a discussion on the constants and, in particular, discuss how the regularization parameter affects both generalization and optimization: large $\\lambda$ yields smoother problems that are faster to optimize using large step sizes, but introduces a large bias in the statistical estimation. When $\\lambda$ is a parameter to select, a trade-off that accounts for the bias (un-regularized vs regularized problems), variance (finite sample vs population as done in this study) and optimization (step size) must be found.\n\n### **2- Remarks on the gradient scheme** \nCorollary 4.2 informs practical algorithm design choices. Indeed, it underscores that the convergence of the bilevel algorithm requires a careful balance between data availability (sample sizes) and computational budget (number of gradient steps).  We will make sure to discuss that right after Corollary 4.2.\n\n### **3- Connection with existing results in IV** \nThank you for raising this point, we will include a discussion on that based on the following. Indeed, our problem formulation is related to IV, which is a particular case, with the important difference that our setting currently only considers regularized inner problems (fixed $\\lambda$, independent of sample size), while typical studies on IV consider un-regularized population problems. It is more challenging to study the latter, and existing literature on the topic made important effort in that direction, obtaining minimax optimal rates depending on source assumptions, as mentioned in your questions. The challenge in our case, lies in an orthogonal direction: by considering more general inner objectives, even the study of generalization for regularized problems presents additional obstacles that have not been addressed before (see also the answer to the general question). A next natural step would be to study un-regularized problems, after which a more direct comparison with existing results on IV could be made. This is unfortunately beyond the scope of this work.\n\n### **4- Can existing mimimax results on IV be used for KBO?** \nIt would be great to obtain minimax rates for KBO. However, it is unclear to us how the techniques used in the context of IV can be used for the KBO. Results for IV heavily rely on the closed-form expression of the first stage, while KBO assumes general loss structure for the inner problem (no closed-form of the minimizer in general). We believe the non-linear dependence of the inner solution on the outer parameter, in the general case, is precisely what makes it hard to apply existing results on IV and two stage regression (see also the response to the general question).\n\n### **5- Measurability of the kernel** \nWe agree that explicitly including this assumption would make the exposition more rigorous and self-contained. We will add a corresponding measurability condition to our list of formal assumptions in the revised version.\n\n### **6- General question** \nThank you for this insightful question. We will add a discussion based on the following points. \n\n- **Spectral techniques.** The idea of spectral filtering is powerful as it allows treating several algorithms in a unified manner as illustrated in (Meunier et al., 2024a). To our knowledge, using the results on spectral filtering for the outer loss suggests that such loss must be a quadratic loss in $\\omega$. This is true when using a regression loss and if the inner solution has a linear dependence in the outer parameter. Such linearity arises when the inner objective is also a regression loss, as in KIV, but is no longer true in general: using general losses in the inner level, yields a non-linear dependence on the outer parameter, that is even implicit. Because of this, it is unclear to us at this stage how to directly transfer the minimax results in (Meunier et al., 2024b) to our setting.\n\n- **Surrogate loss and calibration.** The approach based on surrogate loss and calibration, suggests two directions:\n  - Using a regression loss as surrogate for either both or one of the losses. However, this would imply using the estimators arising from the use of such calibrated regression losses. It is unclear to us how to construct computable calibrated losses in the form of a quadratic loss from the general losses we considered. Additional assumptions on the structure of these losses would be needed.\n  - The other direction is to treat the general losses as surrogate for the quadratic losses, but this means one has to derive statistical bounds for these general losses (which is what the current work does), and then transfer those to control quadratic errors.\n\nOverall, it remains unclear to us how to directly leverage the results in the case of  KIV on KBO without restriction on the form of the loss to be essentially quadratic. \n\nBest regards,\n\nAuthors\n\n---\n\n**References**\n\n(Smale & Zhou, 2007) S. Smale and D.-X. Zhou. Learning theory estimates via integral operators and their approximations. Constructive Approximation 2007.\n\n(Sriperumbudur et al., 2017) B. Sriperumbudur, K. Fukumizu, A. Gretton, A. Hyvärinen, and R. Kumar. Density estimation in infinite dimensional exponential families. JMLR 2017.\n\n(Meunier et al., 2024a) D. Meunier, Z. Shen, M. Mollenhauer, A. Gretton, and Z. Li. Optimal rates for vector-valued spectral regularization learning algorithms. NeurIPS 2024.\n\n(Meunier et al., 2024b) D. Meunier, Z. Li, T. Christensen, and A. Gretton. Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal. arXiv:2411.19653 2024."}, {"review_id": "HqfzKuKcWO", "reviewer": "Reviewer_11HJ", "summary": "The paper considers bilevel optimization in the rkhs. The algorithm  involves using grading method like in the parametric case.", "questions": "1. what is the essential challeng of doing kernel version?\n2. is cobvergence rate optimal?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The introduction is well written, showing the importance and challenge of the problem.  However, the analysis is not quite different from the parametric case. One just need to carefully treat the concept of gradient in function space. The empirical process technique used is also just the same as the parametric case.  The result showing that both the function value and its gradient has some uniform convergence property, which is expected. Convergence of the gradient algorithm is also standard. Thus I'm not too enthusiastic about the work. The problem itself is important, and this is probably a reasonable start.", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer,\n\nThank you very much for your review. We are glad to hear that you found the paper clear and that it addresses an important problem. We appreciate your feedback and understand your concerns, which we address in detail below. Please feel free to reach out with any further questions.\n\n### **1- Main challenge in KBO: Beyond empirical processes** \nOur analysis required considering objects that are not standard empirical processes. The functional setting involves processes that take values in an **infinite-dimensional space** (as opposed to real-valued processes). Hence, we cannot apply classical empirical process theory to those: one could apply the classical result to get an error per dimension, but then summing the errors yields a divergent sum. Instead, we had to use results on $U$-processes (Step 3 in Section 4.2), which, to our knowledge, **have not been used** in the analysis of finite-dimensional problems. Considering these $U$-processes was key for obtaining the $1/\\sqrt{n}$ and $1/\\sqrt{m}$ rates. As discussed in the last paragraph of Section 4.2, using other \"simpler\" techniques results in slower rates. We will clarify this technical novelty in the introduction and throughout the text.\n\n### **2- Convergence rates of (projected) gradient algorithms** \nWhile our convergence rates resemble those of classical gradient algorithms, their derivation in our setting is far from standard due to the functional nature and statistical dependencies specific to the bilevel kernel framework. In particular, the parameter updates do not rely on the exact gradient, but rather on a **data-dependent** gradient estimator arising from the empirical bilevel problem $\\widehat{\\text{KBO}}$. This introduces two main sources of errors: (1) a **statistical error**, which stems from approximating the population gradient and depends on the sample sizes, (2) an **optimization error**, which arises from performing a finite number of (projected) gradient descent steps.\n\n### **3- Optimality of the convergence rates** \nWe did not investigate the optimality of the convergence rates, as the primary goal of our paper is to provide the first finite-sample generalization bounds for nonparametric bilevel optimization. We agree that studying the optimality of these rates is an interesting future research direction and plan to include this point in the conclusion of the revised version.\n\nBest regards,\n\nAuthors"}]

Author rebuttal:

Meta-review: The paper presents the first finite-sample generalization bounds for nonparametric bilevel optimization, where the inner problem is solved over a reproducing kernel Hilbert space. The work's primary strength is its technical rigor and novelty, leveraging advanced empirical and U-process theory to handle the infinite-dimensional setting of the RKHS. The core contributions include showing that differentiation and empirical estimation commute, and using this property to derive generalization bounds for both the objective function and its gradient. Thus I recommend the paper to be accepted.
Decision: Accept (poster)