Convergence of Bayesian Bilevel Optimization
Authors: Shi Fu
Fengxiang He
Xinmei Tian
Dacheng Tao
Venue: ICLR 2024 spotlight (2024)
Keywords: Hyperparameter optimization
Bayesian optimization
Convergence rate
Bilevel optimization
Learning theory
Primary area: learning theory
TL;DR: We establish convergence guarantees for a bilevel approach combining SGD and Bayesian optimization to jointly optimize models and hyperparameters.

Abstract: This paper presents the first theoretical guarantee for Bayesian bilevel optimization (BBO) that we term for the prevalent bilevel framework combining Bayesian optimization at the outer level to tune hyperparameters, and the inner-level stochastic gradient descent (SGD) for training the model. We prove sublinear regret bounds suggesting simultaneous convergence of the inner-level model parameters and outer-level hyperparameters to optimal configurations for generalization capability. A pivotal, technical novelty in the proofs is modeling the excess risk of the SGD-trained parameters as evaluation noise during Bayesian optimization. Our theory implies the inner unit horizon, defined as the number of SGD iterations, shapes the convergence behavior of BBO. This suggests practical guidance on configuring the inner unit horizon to enhance training efficiency and model performance.

Published as a conference paper at ICLR 2024
CONVERGENCE OF BAYESIAN BILEVEL OPTIMIZATION
Shi Fu' Fengxiang He Xinmei Tian' Dacheng Tao
Uniiersity Science and Technology of China,
UUniversity of Edinburgh,
a Nanyynn Technological University
fs fs311@mail 1@maill ust C. edu. cn, F. H.Heeed.ac.oo uk, xinmei@uste. edu. da dacheng. tao@gmailllaaaam com
ABSTRACT
This paper presents the first theoretical guarantee for Bayesian bilevel optimization (BBO) that we term for the prevalent bilevel framework combining Bayesian opti- mization the outer level tune hyperparameters, and the inner-level stochastic gradient descent (SGD) for training the model. We prove sublinear regret bounds suggesting simultancous convergence of the inner-level model parameters and outer-level hyperparameters to optimal configurations for generalization capability. A pivotal, technical novelty in the proofs is modeling the excess risk of the SGD- trained parameters evaluation noise during Bayesian optimization. Our theory implies the inner unit horizon, defined as the number of SGD iterations, shapes the convergence behavior of BBO. This suggests practical guidance configuring the inner unit horizon to enhance training efficiency and model performance.
INTRODUCTION
Hyperparameter optimization is crucial step in the practical implementation of deep learning. Inappropriate hyperparameter configurations can lead to poor model performance and ineffective utilization in real-world systems. Bayesian optimization, relying on probabilistic models, is an effective approach for hyperparameter tuning (Snock et al. (2012). It can identify near-optimal configurations within few iterations, even non-convex and derivative-free scenarios (Frazier (2018). However, it often focuses solely on hyperparameters while neglecting model parameters. In contrast, bilevel optimization furnishes an alternative framework that concurrently optimizes hyperparameters and model parameters in unified architecture (Colson et al. (2007); |Fanceschh] ct al. (2018)). Specifically, bilevel optimization nests an inner-level problem of model parameter optimization within an outer-level problem of tuning hyperparameters (Bao et al. (2021).
Bayesian bilevel optimization, merging outer-level hyperparameter tuning with inner-level model parameter optimization via SGD, shows significant promise in engincering applications. Notably, the most common application is training neural network parameters with inner SGD, while tuning critical hyperparameters like learning rates and layer widths with outer Bayesian optimization (Nguyen et al.) (2020) Dewancker et al. (2016) Snoek et al. (2015)). However, the underlying working mechanisms and theoretical convergence guarantees of this approach remain unclear. Additionally, properly configuring the inner unit horizon presents challenges. Limited inner SGD iterations can impede model convergence, reducing the accuracy of outer Bayesian optimization evaluations. Thus, more Bayesian iterations may be needed to ensure hyperparameter convergence. However, excessive SGD iterations waste resources, revealing trade-ofi between model training and hyperparameter tuning iterations (Hasanpour et al. (i et al. (2017)). While multi-fidelity Bayesian optimization also examines this trade-off (Nguyen et al. (2020), it focuses more on utilizing fidelities to reduce optimization costs. Conversely, objective to deduce the optimal inner unit horizon that enables simultaneous convergence model parameters and hyperparameters to generalization optima.
At the outer layer, Bayesian optimization is adopted for hyperparameter tuning. We utilize two acquisition functions: Expected Improvement (EI) and Upper Confidence Bound (UCB). Regarding E1. Bull (201T) studied its convergence in noise-free settings, while Gupta al. (2022) recently pro- vided convergence analysis in noisy settings with the standard predictive mean incumbent. For UCB, Srinivas et al. (2010) first introduced the method and derived regret bounds scaling ((TTTr),

---

Published as a conference paper at ICLR 2024
where "i denotes the maximum information gain between T observations and the Gaussian process model. Chowdhury& & Gopalan (2017) further improved it through an enhanced algorithm.
Previous theoretical studies have relied on certain noise assumptions, including bounded (Srinivas
ct al. (2010); Nguyen & Gupta (017)) or sub-Gaussian noise (Chowdhury & Gopalan (0117):
Gupta et al. (2022)). However, these assumptions do not adequately capture the intricacies of integrating SGD and Bayesian optimization a bilevel framework. A key limitation in most prior martingale difference sequence. This approach does not align with hyperparameter optimization, where the objective function often represents generalization performance (Snoek et al. (2012)) Another drawback of prior works (Srinivas et al.) (2010); Chowdhury & Gopalan (2017)) is the use of UCB balancing coefficients that increase rapidly, which has been shown to be over-exploratory for many practical problems (De Ath et al. (2021) )
works is their modeling of the noise {ex)
To tackle these challenges, pivotal innovation of our work involves modeling the excess risk of inner- level SGD-trained parameters as the primary noise source during outer-level Bayesian optimization. This perspective facilitates more adaptable convergence guarantees for the bilevel setting. Modeling the SGD excess risk is critical since it builds a connection between the analytical frameworks of Bayesian optimization and bilevel optimization. The distinct objectives and assumptions of these two frameworks pose difficulties in ensuring theoretical convergence. Our approach bridges this gap, enabling a comprehensive convergence analysis for BBO.
By modeling the excess risk of SGD as noise, we derive sublinear regret bounds for BBO, guarantecing simultaneous convergence of model parameters and hyperparameters to optimal configurations for generalization capability. This is accomplished through carefully configuring the inner unit horizon. By determining the SGD-tt--Byessian iteration trade-off, we optimize this ratio improve computational efficiency. Furthermore, we optimize the UCB balancing coefficients based on the iteration ratio, enhancing flexibility and mitigating excessive exploration resulting from rapidly escalating coefficients in previous works. Our analyses provide valuable insights into balancing computational resources in engineering applications. The main contributions of this work include:
1. We provide a novel theoretical analysis of convergence guarantees for generalization performance within a BBO framework. A key technical innovation is modeling the excess risk of SGD-trained parameters as evaluation noise in outer-level Bayesian optimization. This tackles theoretical analysis challenges by bridging the analytical frameworks of Bayesian optimization and bilevel optimization.
2. We establish regret bound of ((VTTT) for BBO using the El function, with a noise assumption more aligned with practical scenarios. Our regret bound achieves savings of v'T compared to Gupta al. (2022). This achievement is realized by optimizing the ratio of SGD iterations N to Bayesian optimization iterations T, also offering implementation guidance.
3. We introduce adaptable balancing coefficients 3, for the UCB acquisition function. Through this adaptation, we establish a sublinear regret bound for BBO with the UCB that holds even with fewer SGD steps, enhancing the flexibility of the inner unit horizon. Additionally, overcome the limitations of rapidly increasing coefficients from previous analyses.
2 RELATED WORK
Hyperparameter optimization is crucial for leveraging deep learning's capabilities (Yang & Shami (2020): Elsken al. (0019). Techniques span Bayesian optimization (Wu al. (2019); Victoria &
Maragatham (2021)), decision theory (Bergstra & Bengio (012)), multi-fidelity methods (Li et al.
(2017). ) and gradient- based approaches (Maclaurin et al. (2015)) We focus on BBO, exploring
Bayesian optimization and bilevel frameworks' relevant aspects for hyperparameter tuning.
Bayesian optimization. Bayesian optimization (BO) (Osorre & Osborne (2010): Kandasamy et al.
(2020) is a prevalent approach for hyperparameter tuning by efficiently exploring and exploiting hyperparameter spaces (Nguyen et al. (2017)) Gaussian processes (Bogunovic et al. (2018) are commonly used priors in BO to model uncertainty and estimate objective function distributions
(Bro (010)); Wilson et al. (0014)). Among acquisition functions guiding queries in BO, the El acquisition function (Jones& & Welch (1998); Malkomes & Garnett (2018); Scarlett et al. (2017); Qin ct al. (2017) is one of the most widely utilized for balancing coraationexpllotation (Nguyen &
Oshome (2020) Zhan & Xing (2200). Other acquisitions like UCB (Valko et al. (2013)) knowledge
2

---

Published as a conference paper at ICLR 2024
gradient (Frazier et al. (2009); Scott et al. (2011), Thompson sampling (Chowdhury & Gopalan (2017)) and predictive entropy search Hernández-Looaan et al. (2014)) cater to various scenarios.
Theoretical analyses of Bayesian optimization have been conducted to understand their convergence properties (Ryzhov ( et al. (2020)) The EI has been studied under specific conditions (Vazquez & Bect (2010); ( Gupta et al. (202T). Adapting EI for noisy evaluations poses challenges. Wang & de Freitas (2014) addressed this issue by introducing an alternative incumbent selection criterion that necessitates an additional global optimization step. Nguyen & Gupta (2017) used the best-observed value as the incumbent, showing sublinear convergence with a minimum improvement stopping condition. Gupta et al. (2022) analyzed EI convergence with the standard predictive mean incumbent. For UCB, (eiinvvvs et al. (2010) established regret bound as ((VTTr) This approach was subsequently enhanced by (Janz et al. (2020)) via a modified UCB algorithm.
Bilevel optimization. Bilevel optimization offers an alternative framework for hyperparameter tuning by concurrently optimizing hyperparameters and model parameters a nested architecture (Colson et al. (2007) Franceschi et al. (2018 2018)/aa (Bao et al. (202T)). These methods encompass implicit gradient (Bengio| Lukettia et al. (2016))eedreooos (2016)
et al. (2020), hypernet- works (Lorraine & Duvenaud ( (2018 Mac Kay et al. (2019)), unrolled differentiation (Franceschi ct al. M et al. (2015) Bao et al. (2021)) ), and cross-validation (Bergstra & Bengio (2012)) ). Implicit gradient- based methods estimate the model's 's performance gradient with respect to hyperparameters without explicit computation (Lorraine et al. (2020). Hypernetworks generate model weights conditioned on hyperparameters. Cross-validation approximates optimal hyperparam- eters using grid search (Abas et al. (2020)) or random search (Bergstra & Bengio (2012). Unrolled differentiation involves optimizing the inner problem over multiple iterations (Fu al. (016)).
Remark. While Bayesian and bilevel optimization have advanced theoretically, extending conver- gence guarantees to BBO remains challenging. Bayesian optimization analyses often disregard the impact of model parameter convergence on noise during evaluations, instead relying on unrealistic noise assumptions. Theoretical bilevel optimization analyses struggle to extend to the non-convex, nonlinear, and derivative-free scenarios inherent to Bayesian optimization.
3 PRELIMINARIES
We consider bilevel optimization involving model parameters and hyperparameters. Let 2, O and A denote the data space, the parameter space, and the hyperparameter space, respectively. Given hyperparameters À E A, model parameters A Ô and distribution DD on the data space 2, the expected error L(X, 0) is defined as Eg-D(e(A, 0, 2)]. where é A x θ x Z - IR is the bounded loss function. Our objective to find the hyperparameter- parameter pair that minimizes the expected error over unknown distribution. This objective entails nesting two search problems:
A arg min L (A, 02), where 0 = arg min L (A, 0). xea
(3.1)
The inner-level objective is to determine the optimal model parameters, denoted 0% for given hyperparameter A. It's worth noting that the value of 0 depends on the choice of the hyperparameter X. At the outer level, the goal is to identify the optimal hyperparameter X which determines its associated model parameters 0i., collectively minimizing the expected error. This bilevel structure is very classic and has been applied in many practical scenarios, such as in Darts (Liu al. (2018)).
Regret. Similar to Gupta et al. (0022). we employ regret as a convergence measure. We define X and 83- as the global minimum points, as shown in Equation 3.1 During the t-th iteration at the outer level, the output hyperparameters are denoted as X²- Simuitancously, the inner level, using these hyperparameters xt, we optimize the model parameters through N steps of SGD, denoted as 0NNV The cumulative regret Rr at iteration T is calculated as the sum of instantaneous regrets: A
RT- Σr Tt, where r, = L(X", ) L(x (AA,,ON). ON) Our objective is to demonstrate that Rr exhibits almost sublinear growth, specifically limr- R 0.
3.1 INNER LEVEL OF BBO: MODEL TRAINING BY SGD
At the inner level, our goal is to optimize the model parameters by minimizing the expected error. Given the limited knowledge of data distribution, direct access to this expected error is challenging.
3

---

Published as a conference paper at ICLR 2024
As solution, we utilize SGD to optimize the empirical error, serving proxy for improving model parameters. Previous studies, such as Hardt et al. (2016), have shown SGD's s effectiveness in achieving strong generalization performance. Let Sth { ji=ı denote the training dataset, with n representing the number of training samples. Formally, the inner-level problem is defined as: mingee I." (x,0,
0, (*r) = - e (x,, =(") Below, present some essential definitions.
Definition 1. (Lipschitz, smoothness, and convexity). Let constants K,y 0. Consider the function A θ x Z + R. We define the following properties:
Lipschitz Continuity: The loss ((A, 2) is said to be K- K-Lipschitz continuous with respect to B if [e{(), 2) e(), 82, 2] I K1 - 02ll for any 02, 82, 2, A.
Smoothness: The loss E(A, 0, 2) is said to be 7-Smooth with respect to if VoL((, 01, Vol(A, 02 2)]l - 0110 02 for any 01, 2,
Convexity: The loss f(A. 0, 2) is said to be convex with respect to @ if e(), 01, 2 E(X, 2) + (VoE(A, 82, 2), 01 - 02) for any 0,, 2,,
The above definitions are standard concepts that have been widely adopted in related works such as Ghadimi & Wang (2018) Ji Liang (2023). Grazzi al. 2020), and et al. (202T).
Remark Our BBO theoretical framework can be extended non-smooth and non-convex situations. Emphasizing BBO convergence, we've mentioned these concepts for clarity, The proposed structure is highly adaptable for various scenarios. Drawing on insights from Charles & Papailiopoulos (2018), the framework extends to non-convex situations under a j-graddentt- dominance condition. For non-convex conditions, Theorem [ indicates an excess risk of O ((N-1/2 1/2 1/1/22p1/// 1/2 + 1-1/4 3344 log N). In addition, eliminate the smoothness assumption, adding a term 7/vN
N to the excess risk bound, where 1j is the step size. Alternatively, relaxing the assumption to a-Hölder continuity introduces an additional term O (N'>ari-o - log N) the excess risk bound. The detailed content is in Appendix
3.2 OUTER LEVEL OF BBO: HYPERPARAMETEE TUNING BY BO
At the outer level, the model parameters 8 remain fixed, and our objective is to identify the hyperpa- rameters X E A that minimize the expected error L (X, fx). Critically, the function ((x, 0%) has uniquely determined value for each This uniqueness arises because. although 8 arg min (A, 0) fie
might represent set when À specified, for any 0 in this set, the loss function ((A, 8%) consistently yields the unique value min L(A, 0). Therefore, we may treat L(A, 8%) as function solely dependent lge
on A, allowing to conceptualize it mapping function from A to I.
3.2.1 REGULARITY ASSUMPTIONS
As noted by Scarlett et al. (2117). ). Bayesian optimization can be viewed from two distinct perspectives: Bayesian and non- Bon-BBaeii Departing from the standard Bayesian optimization framework, this work adopts a more agnostic, non- non-Bayesian setting (Srinivas et al. (0100). Specifically, we assume that hyperparameter space A is compact set. We also posit the reward function [. 0%) lies within reproducing kernel Hilbert space (RKHS) He (A) of functions mapping from A to R. characterized by a positive semi-definite kernel function k A A + R. This RKHS Hd (A) determined by its kernel function k<-,-) -) and features an inner product (-, 1) satisfying the reproducing property: L(A, 02) (L(.,")) ), ((X,)) )) for all L(. 8t) E (A). Hence, the kernel & effectively represents the evaluation map at each À E A through the RKHS inner product. The RKHS norm, defined as [[ 8* ] VLL(. L(, 0:)) We assume the RKHS norm of the unknown L(.,0") is bounded by B. This assumption suggests the smoothness of the functiinn. This relationship is showcased in the following example that the inequality [[(1,, 8 L(x2, (%, ((((,))),,((>).)) k(),, ))
[| 8*) (1))ll=(l(((.>))>) k(d2. lle by the Cauchy-Schwerr inequality.
3.2.2 GAUSSIAN PROCESS (GP) REGRESSION
Bayesian optimization employs GPs as flexible surrogate models for the objective function, leveraging their versatile priors and tractable posteriors (Rasmussen & Williams (006)). Initially, we assume
4

---

Published as a conference paper at ICLR 2024
GP prior, denoted GPA (0, k)+ for the unknown reward function (() over A, with k(,-)) representing the kernel function associated with the RKHS (A).). The algorithm collects where yt = L (>e, xx.) + Es. and 6, N (0, denotes independent and identically distributed Gaussian noise for all t. Consequently, given the history H1:t = 91 let (A) = k. (A. A), the posterior distribution over L(,, 8.)) remains a GP, denoted as (T.((;) H1a-1, 1, A) = - (A), (A))). where
observations y: ly,...., 3/]² at points A, . )e),
(e(A)= = (A)" (K, + 1 Vt, de (A, A: (x, (A))) (K, +o=0)=11 Kg (X), where we define k2 (A) [k AA1: I. function k is fixed and well-defined with () 1.
...k (A,, A)I", KK. [m: (X,X))xxEE We assume the kernel
3.2.3 ACQUISITION FUNCTION
Acquisition functions are vital in Bayesian optimization as they guide the choice of the next evaluation point. They quantify the potential improvement of each candidate point. This section explores two prevalent acquisition functions: UCB (Srinivas et al. (2010)) and EI (Jones & Welch (1998).
Upper Confidence Bound. The UCB acquisition balances exploration and exploitation by selecting points with potential improvement while considering evaluation uncertainty. It is defined as:
(CB((A) -A) (
(3.2)
where 3r denotes coefficients regulating the trade-off. The - (A) term promotes exploitation by favoring points with lower estimated mean values, thereby increasing the likelihood of improved outcomes. The a--1 (A) term drives exploration by prioritizing highly uncertain points.
Expected Improvement. The EI quantifies the expected enhancement in the incumbent relative to the objective funetion value. Typically, the incumbent is chosen as the minimum GP mean observed so far, denoted as μi = minx, A, P4- (Az), consistent with Gupta et al. (2022). The El is defined as (A) = E mmxx(p - L(X, 02), 0} H1 The closed-form expression for EI can be derived as:
IT - ( + (
M - (A)
if (A)) > 0, where ø is the standard normal p.d.f. and & is the c.d.f. When 1=-1(A) = 0, we set EI{(A) = O.
(A) = (ui - -
(A)
4
MAIN RESULTS
This section presents theoretical analyses of the convergence guarantees for BBO. Specifically, We derive an excess risk bound for the inner-level SGD-trained model parameters. We also establish regret bounds for the outer-level Bayesian optimization that ensures simultancous convergence of model parameters and hyperparameters. The BBO algorithms are detailed in the Appendix. Based on the convergence analysis, we characterize the trade-off between model training and tuning.
4.1 INNER LEVEL OF BBO: EXCESS RISK BOUND
First, we present the excess risk bound for inner-level optimization.
Theorem 1. Suppose that the function f(), 0, 2) is K-Lipschitz continuous, 7-smooth and convex with respect to 9, uniformly bounded by M. We perform SGD with step sizes n; = = VN S 2// on sample 5t" drawn from the distribution D al the inner level. This involves performing N steps
m and obtaining the output result 0% Let Sual = {2(a1] Ji=1 represent the validation set drawn from the distribution D. The validation error is defined L (X, ,. Sual)= = m -. E(), 8N a!
Choose N X nt X m. Then, with a probability of at least 1 - 5, we have:
I voll NN, sval) L(A, O N 1/2 N)
The complete expression is given by Loal (A, 0N Sval) L(,, 03) S x(NNN- where s(N) = O 1Kllog N log(1/0) + M (Too(11/8) + M M Vog(2/5) + log 3/2 (N/6))
5

---

Published as a conference paper at ICLR 2024
Remark 2. In outer-level Bayesian optimization, the objective is to minimize the expected error L(A, 82). However, as the data distribution is unknown, L(,, 0%)) cannot be evaluated directly. Instead, the validation loss L val (A, 0N S serves as a proxy to observe L 02). Specifically, given hyperparameters À and model parameters 0% from inner-level SGD, the difference between L (X, 0x SSaa) and [A,, (xx) represents noise when evaluating I(x,0% 0x) in outer optimization. Analyzing the convergence of this excess risk bound I, val (A, NN Swal) L(,,, 8x) is of interest.
4.2 OUTER LEVEL OF BBO: REGRET BOUND
This section presents regret bounds for the outer-level Bayesian optimization. The subsequent lemma delineates the concentration of the posterior mean around the true objective function, thereby constituting the theoretical basis for the ensuing regret analysis. Notably, explicated in Section 3.2
L(x, 0%) may be considered as functions mapping from A to R.
finctiiit Lemma 2. let L(-, (0): A + I be a member of the RKHS of real-valued functions on with kernel k. with RKHS norm bounded by Consider the noise term & L (Ne, AN Suaat) ) L (Ne, 0%
then, with probability at least 1 8, the following holds for all X E A and 1 1:
(A) L(>, 0,1 / 33= (N)N-) (
Subsequently, we introduce the definition of maximum information gain, which will prove useful in bounding the cumulative regret.
Definition 2. Given the set AT (A1,... Ar) C A, let LAy (.,0)) = (A, xx and AAr = La, (s, (..6*)= EAy, where EA, ~ N o2 With I (-:-) denoting the mutual information, the maximum information gain after iterations is defined as PT = maxAreA / (yAr A ().)).
Notably, the maximum information gain "r differs under various kernel selections. According the results from Srinivas al. (2010), for the Squared Exponential kernel, "T (log d-1 (T))) whereas based on the findings in Vakili et al. 2021). for the Matérn-i/ kernel, YT ((
4.2.1 REGRET BOUND FOR BBO WITH EI FUNCTION
In the ensuing analysis, we establish the primary theoretical contribution of this work, specifically, the regret bound for Bayesian bilevel optimization with the EI acquisition function. For the sake of clarity in notation, we define the auxiliary function r(2) = (2) + Φ(2).
Theorem 3. Let 5 (0, 1). Assume that the true underlying function ((2,0%) in terms of lies in the RKHS Ha(A) associated with the kernel k (A, Furthermore, consider the noise Specifically, assume that (-,6")lle < B and define Br /B2 + + By executing algorithm [ with El acquisition and the prior -, the cumulative regret is bounded as:
term Et = Lool (Ne, ON, Sual) - L ()t,0%,)
GP^ (0, (), with probability at least -5,
VTVTTI
+TN-3).
R1 0
T (BT) -Br
If we select N x T, we attain:
Ry - 1 (VTTT)
Proof Sketch of Theorem 3 Adapting Bayesian regret analysis the bilevel optimization context
with noise induced by SGD poses a central challenge. To bound the cumulative regret Rr, the initial
step involves constraining the instantaneous regrets r,, defined as r; xx= 0N L 0z-). ,N - xx xx
Each instantaneous regret ra can be decomposed into three terms: Y; L (xt AN
x7
(At ) 14t + 11tht L (A,,8- (.)). where 1if" denotes the incumbent.
The first term, L (xt $4.0% 0x - and the excess risk result from Theorem yielding an upper bound of ((N log N). For the
L x can be bounded by applying concentration inequalities

---

Published as a conference paper at ICLR 2024
second term, A 0/ 14: the bound is given by 3 (V2T + +11 (Ae)+ (1 v V (Ae)).
where (Ac) = max [ur - L (A,, .)) To bound the last term μi² - L (X",, (x,,)))) our approach involves initially establishing lower and upper bounds on the EI acquisition value by leveraging the properties of 7(2). A pivotal technical challenge arises in bounding the discrepancy between the GP posterior mean (+) and the true function value L(. ) at A, and X", which requires considering the The optimality of X from maximizing the EI acquisition leads to an upper bound given by: 1+ ((,
SGD-induced noise as detailed in Lemma
2
+ (B. + 1) (>.)). as shown in Lemma 15
Bounding and summing the three constituent terms allows us to derive the cumulative regret Ry- Employing auxiliary results related to the cumulative sums of improvement terms [242)) and predic- tive variances (x{))), as documented in Gupta et al. (2022) and Chowdhury & Gopalan (2017), and setting N = T, we attain the bound Ry = O(VTT))
Comparision with previous works. Through appropriate selection of N, our regret bound is denoted as Ry- = O( (vTrr) In contrast, Nguyen & Gupta (2017) established a regret bound of P(TTVToo T) for El with the best-observed value y as the incumbent. They further introduced an additional assumption constraining the variance function values to exceed a lower bound k. Thus, their bound escalates markedly as K + co. The work most analogous to ours is Gupta al. (2022).
which also utilizes EI with the standard incumbent μuر" = minx,EA, Me-1 (A₃). and possesses regret bounds of R V(TTVT), Our regret bound thus achieves theoretical savings of VTT.
Furthermore, It's worth noting that Gupta et al. (2022) assumed conditional Suus-aaa noise, while Nguyen & Gupta (2017) assumed bounded noise. Additionally, both studies assumed that the noise sequence {e:Ji= constitutes a martingale difference sequence, signifying that E[er|E<r]] = for all t T. In comparison, the inner-level SGD-optimized model parameters, is E = L nal (Xe. 0%, Swal) - L(), 8x The conditional expectation E [Ex E<c] = O does not hold here. This is because NN depends on the training set 5tr while 07 does not. This modeling more aligns closely with practical scenarios when leveraging Bayesian optimization for hyperparameter tuning.
assumption regarding the noise Et, denoted the excess risk of
Moreover, prior research has primarily restricted its regret definition to hyperparameters. In contrast, as outlined Section 3. our approach uniquely defines regret to include both model parameters and hyperparameters. This broader view adds complexity to our theoretical analysis by necessitating the establishment of a sublinear regret bound. Our derived bound offers theoretical validation for the convergence of both model parameters and hyperparameters towards their optimal values.
Practical insights: Inner Unit Horizon as the Same Order of Outer-Level Iterations.. By judiciously selecting the number of inner-level SGD optimization iterations as N = T, attained the regret bound RT = (T)TT)) This further provides practical guidance into better balancing the iterations between inner-level SGD and outer-level Bayesian optimization.
Specifically, if the number of SGD iterations N is substantially less than T, such as O(VT), the regret becomes R (T (Tr/(T(T)//) -/AA)) Since "r monotonically increases and T(2) monotonically decreases to zero, when -> oo, we have Yr -> oo and T(T1/4) T/1
Consequently, R = O (T/TT/((TTTTT - will exhibit rapid growth. Indeed, this suggests that having too few inner SGD iterations results in a faster increase in the regret bound. In contrast, N significantly exceeds T, then 37 + B², maintaining a constant order instead of diminishing. Hence, the regret Rt ((VTTT) remains unchanged, indicating unnecessary SGD iterations being performed and wasted resources.
In summary, the optimal inner unit horizon N for convex functions scales as N x T. Moreover, demonstrate in Section F.1 that for non-convex functions, the optimal N x T2, This choice of N strikes an effective balance between SGD and Bayesian optimization iterations.
4.2.2 REGRET BOUND FOR BBO WITH THE UCB FUNCTION
Next, we establish the regret bound for the Bayesian bilevel optimization with the UCB acquisition.
Theorem 4. Let d E 10. Assume that the true underlying function L(X, 03) in terms of X lies in the RKHS Hs(A) associated with the kernel (2, X). Additionally, consider the noise term E Lool (Ne, ON (vvl)) I. T.,,,, 0%.) Specifically, assume that T. (1, 0. )lkk S B and let
7

---

Published as a conference paper at ICLR 2024
8 = to 3 By running algorithm with Be and the prior GPA. (0, (), with probability at least 8. the cumulative regret is bounded as:
RT 0 (v (V + TN TN
we select N x T, obtain that:
R -0 1100(VTT (VTTT)
This proof approach is similar to Theorem but employs a different acquisition function. The instantaneous regret v2 can be decomposed into two terms: + L
Proof Sketch of Theorem
L (x*, The first term, identical to the first term in Theorem 3 can be established using the same methodology, yielding the bound of ONN-1/2 log N). Through the utilization Lemma and the selection X as specified Algo- rithm 2 we can demonstrate that the second term can be upper-bounded as follows: 2,, (A₂) ). By summing the upper bounds of the two terms mentioned above and taking into account that
(At O (xt,
ET (Ar) O (vTrr) as demonstrated in Chowdhury & Gopalan (2017), the final result
can be deduced: Rr O (V(²² TN -N- T TN-1/2 with probability at least 6. By
selecting N T, we can further establish that: Ry O (VTh)).
Comparision with previous works. For the UCB. 3g plays crucial role in balancing exploration and exploitation. In previous work, [Srinivas al. (010)) introduced the GP-UCB algorithm with 3. (2 3007, log" (1/8))1/2, while slightly improved variant, the IGP-UCB algorithm, presented in Chowdhury & Gopalan 2017), used 3. = + R 2
In(1/5)). In both cases, the balancing coefficient 3r tends to increase rapidly with f, especially when the Matérn-w kernel is used. In practice, this leads to numerous unnecessary explorations in Bayesian optimization (De Ath et al. (2021)). However, in our work, we have chosen the balancing coefficients Br /B² (NN)N As result, can appropriately adjust the ratio of the number of iterations N in the inner level to the number of iterations T in the outer level to control B..
Furthermore, by choosing N I we can obtain regret bound O (BVTTT). which is tighter than the regret bound O B B +TVVT associated with Chowdhury & Gopalan 2017). Our assumptions regarding noise are also more aligned with reality. This approach enables us to achieve an improved balance between exploration and exploitation in Bayesian optimization. Moreover, our regret bound provides theoretical assurance for the convergence of both model parameters and hyperparameters to their respective optima, whereas Choowdhury & Gopalan (2017) only guarantees the convergence of hyperparameters.
Practical insights: Flexibility the Inner Unit Horizon. choice of N =; is also reasonable for the UCB function. If N is significantly larger than T, the coefficient B² + 7N-1 tends to approach B², remaining constant rather than approaching zero, and the regret bound remains Ry = ((TTT)) showing change. This implies that inner-level SGD involves many futile iterations.
However, it's important to note that, unlike the situation for the El acquisition function mentioned above, N is significantly smaller than T, for instance, = (vT)), T), then the regret bound becomes Rr = O(T3/4 ).r). For the SE kernel, where ?r = Olog d+1 (T)), the regret bound Ry still exhibits sublinear growth. the case of the Matérn-v kernel, with yr (T =42) when 2v > the regret bound Ry can also exhibit sublinear growth.
In summary, the UCB acquisition offers greater flexibility in choosing the number of iterations for inner-level SGD iterations compared to EI. With fewer SGD iterations, the noise in function evaluations increases. Therefore, our theoretical analysis shows that UCB is more resilient to the influence of noise compared to EI. which aligns with the experimental findings in Hu et al. (2021).
5 EXPERIMENTS
We conducted numerical results in this section. In the inner level, we employ SGD to train a CNN with two convolutional layers and one fully connected layer the MNIST dataset. In the outer level,
8

---

Published as a conference paper at ICLR 2024
Bayesian Optimization uses the El and UCB functions to adjust hyperparameters like the learning rate. We fix the number of iterations for the outer-level BO and compare the number of iterations for the inner-level SGD under different scenarios, along with their respective convergence outcomes, as detailed the table below. We initially present the results when utilizing the acquisition function.
(1) Setting the number of outer Bayesian optimization steps 20.
SGD Iteration
100
500
1,000
2,000
3,000
Performance
3.15 + 0.75
2.73 + 0.03
2.70 + 0.04
2.43 + 0.12
2.46 + 0.13
(2) Setting the number of outer Bayesian optimization steps as 40.
SGD Iteration
500
1,000
2,000
3,000
4,000
Performance
3.45 E 0.85
2.42 + 0.23
2.44 + 0.55
2.39
0.09
2.51 + 0.09
(3) Setting the number of outer Bayesian optimization steps as 60.
SGD Iteration
1,000
2,000
3,000
4,000
6,000
Performance
2.58 0.58
2.40 + 0.35
2.34 + 0.28 2.10 + 0.08 2.25 0.17
The experiments are aligned with our theoretical analysis. Fixing the Bayesian optimization's 's iteration number, the loss function decreases the SGD) steps rise initially, while suboptimal hyperparameters cause high loss. Specifically, with only 20 outer-level iterations, excessively low tuning led to high loss even at high SGD steps. For 40 outer-level iterations and over 1,000 SGD steps, overtraining and inadequate tuning. For 60-step outer-level iterations, the loss at over 4,000 SGD steps is less than the 40-step setting, due more adequate tuning. Yet, insufficient tuning still occurs at 6,000 SGD steps under the 60-step setting.
signs of
Then we present the results when utilizing the UCB acquisition function.
(1) Setting the number of outer Bayesian optimization steps as 20.
SGD Iteration
100
500
1,000
2,000
3,000
Performance
2.93 E 0.60
2.59 E 0.47
2.49 + 0.34
2.39
0.07
2.31 E 0.13
(2) Setting the number of outer Bayesian optimization steps as 40.
SGD Iteration
500
1,000
2,000
3,000
4,000
Performance
2.56 + 0.53
2.34 0.45
2.29 +: 0.29
2.27 + 0.30
2.22 + 0.16
(3) Setting the number of outer Bayesian optimization steps 60.
SGD Iteration
1,000
2,000
3,000
4,000
6,000
Performance
2.57 + 0.27
2.26 + 0.28
2.23 + 0.17
2.19 + 0.19 2.20 + 0.10
When utilizing the UCB acquisition function for the outer Bayesian optimization, while keeping the number of steps for the outer Bayesian optimization fixed, we gradually increase the number of iterations for the inner SGD optimization. We can observe that initially, as the number of SGD itcrations increases, the loss decreases gradually. However, when the number of SGD steps becomes excessively large, the decrease in loss tends plateau.
CONLUSION
Through solid analysis, we derive sublinear regret bounds guaranteeing simultaneous convergence of model parameters and hyperparameters to optimal configurations for generalization capability and providing insights into optimally balancing computations between model training and hyperparameter tuning. This theoretical foundation demonstrates the potential of Bayesian bilevel optimization for non-convex, derivative- free hyperparameter tuning. Future work may enrich this area through empirical studies, alternate acquisitions, and extensions to neural networks.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
We appreciate Hang Yu from the University of Sydney for his assistance experiments. This work supported by NSFC project No. 62222117 and the Fundamental Research Funds for the Central Universities under contracts WK3490000005 and KY2100000117.
REFERENCES
tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. CoRR, abs/1012.2599, 2010.
Mohamad Aqib Haqmi Abas, Nurlaila Ismail, NA Ali, S Tajuddin, and Nooritawati Md Tahir. Agarwood oil quality classification using support vector classifier and grid search cross validation hyperparameter tuning. Int. J, 8, 2020.
Fan Bao, Guoqiang Wu, Chongxuan Li, Jun Zhu, and Bo Zhang. Stability and generalization of bilevel programming in hyperparameter optimization. Advances in neural information processing systems, 34:4529-4541 2021.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
Yoshua Bengio. Gradient-based optimization of hyperparameters. Neural computation, 12(8): 1889-1900, 2000.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
Ilija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with gaussian processes. Advances in neural information processing systems, 31, 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626, 2020.
Adam D Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge global optima. In International Conference Machine Learning, pp. 744-753, 2018.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pp. 844-853. PMLR, 2017.
Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview bilevel optimization. Annals of operations research, 153:235-256, 2007.
George De Ath, Richard M Everson, Alma AM Rahat, and Jonathan E Fieldsend. Greed is good: Ex- ploration and exploitation trade-offs bayesian optimisation. ACM Transactions on Evolutionary Learning and Optimization, 1(1):1-22, 2021.
Ian Dewancker, Michael McCourt, and Scott Clark. Bayesian optimization for machine learning: A practical guidebook. arXiv preprint 161iv:1612.04888 2016.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1) 1997)21997-2 2019.
Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient- based hyperparameter optimization. In International Conference on Machine Learning, pp. 1165-1173. PMLR, 2017.
10

---

Published as a conference paper at ICLR 2024
Luca Franceschi, Paolo Frasconi, Saverio Salzo, Riccardo Grazzi, and Massimiliano Pontil. Bilevel programming for hyperparameter optimization and meta-learning. In International conference on machine learning, pp. 1568-1577. PMLR, 2018.
1. Frazier. A tutorial on bayesian optimization. In arXiv preprint arXiv: 2018.
Peter Frazier, Warren Powell, and Savas Dayaník. The knowledge-gradieng policy for correlated normal beliefs. INFORMS Journal on Computing, 21(4):599-6) -13,, 2009.
Jie Fu, Hongyin Luo, Jiashi Feng, Kian Hsiang Low, and Tat-Seng Chua. Drmad: distilling reverse- mode automatic differentiation for optimizing hyperparameters of deep neural networks. arXiv preprint wwXiv:1601.009111 2016.
Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 1802.02244 2018.
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In International Conference on Machine Learning, pp. 3748-3758. PMLR, 2020.
Sunil Gupta, Santu Rana, Huong Ha, Svetha Venkatesh, et al. Sub-linear regret bounds for bayesian optimisation in unknown search spaces. Advances in Neural Information Processing Systems, 33: 16271-16281, 2020.
Sunil Gupta. Santu Rana, Svetha Venkatesh, et al. Bayesian optimistic optimisation with exponentially decaying regret. In International Conference on Machine Learning, pp. 19390-10400. PMLR, 2021.
Sunil Gupta, Santu Rana, Svetha Venkatesh, et al. Regret bounds for expected improvement al- gorithms in gaussian process bandit optimization. In International Conference on Artificial Intelligence and Statistics, pp. 8715-8737. PMLR, 2022.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Seyyed Hossein Hasanpour, Mohammad Rouhani, Mohsen Fayyaz, and Mohammad Sabokrou. Lets keep simple, using simple architectures to outperform deeper and more complex architectures. arXiv preprint
2016.
José Miguel Hernández-Looate Matthew W Hoffman, and Zoubin Ghahramani. Predictive entropy search for efficient global optimization of black-box functions. Advances in neural information processing systems, 27, 2014.
Jiabin Hu, Yuze Jiang, Jiayu Li, and Tianyue Yuan. Alternative acquisition functions of bayesian optimization in terms of noisy observation. In Proceedings of the 2021 European Symposium on Software Engineering, pp. 112-119, 2021.
David Janz, David Burt, and Javier González. Bandit optimisation of functions in the matérn kernel rkhs. In International Conference Artificial Intelligence and Statistics, pp. 2486-2495. PMLR, 2020.
Kaiyi Ji and Yingbin Liang. Lower bounds and accelerated algorithms for bilevel optimization. J. Mach. Learn. Res., 24:22-1, 2023.
Kaiyi Ji. Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning, pp. 4882-4892, PMLR, 2021.
Schonlau M. Jones, D. R. and W. J. Welch. Efficient global optimization of expensive black-box functions. In Journal of Global Optimization, 13(4):455 492, 1998.
Kirthevasan Kandasamy, Karun Raju Vysyaraju, Willie Neiswanger, Biswajit Paria, Christopher Collins, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly. The Journal of Machine Learning Research, 21(1):3098-3 3124, 2020.
11

---

Published as a conference paper at ICLR 2024
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Learning, pp. 795-811 195-811,220 2016.
condition. In European Conference on Machine
Yunwen Lei and Ke Tang. Stochastic composite mirror descent: Optimal bounds with high probabili- ties. In Advance in Neural Information Processing Systems, pp. 1534-1534, 2018.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819, 2020.
Yunwen Lei and Yiming Ying. Sharper generalization bounds for learning with gradient-dominated objective functions. In International Conference Learning Representations, 2021. 2021.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel Sundit-based approach to hyperparameter optimization. The journal of machine learning research, 18(1):6765-688 6816, 2017.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.0900 2018.
Jonathan Lorraine and David Duvenaud. Stochastic hyperparameter optimization through hypernet- works. arXiv preprint arXiv: 1802.09419, 2018.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In International conference on artificial intelligence and statistics, pp. 1540-1552. PMLR, 2020.
Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient-based tuning of continuous regularization hyperparameters. In International conference on machine learning. pp. 2952-2960. PMLR, 2016.
Matthew MacKay, Paul Vicol, Jon Lorraine, David Duvenaud, and Roger Grosse. Self-tuning networks: Bilevel optimization of hyperparameters using structured best-response functions. arXiv preprint arXiv: arX00:9903.03088, 2019.
Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient- -baed hyperparameter optimization through reversible learning. In International conference machine learning, pp. 2113-2122 PMLR, 2015.
Gustavo Malkomes and Roman Garnett. Automating bayesian optimization with bayesian optimiza- tion. Advances in Neural Information Processing Systems, 31, 2018.
Vu Nguyen and Gupta. Regret for expected improvement over the best-observed value and stopping condition. In Proceedings of the Ninth Asian Conference Machine Learning, volume 77 of Proceedings of Machine Learning Research, pp. 279-294, PMLR, 15-17 Nov 2017.
Vu Nguyen and Michael A Osborne. Knowing the what but not the where in bayesian optimization. In International Conference on Machine Learning, pp. 7317-7326. PMLR, 2020.
Vu Nguyen, Sunil Gupta, Santu Rane, Cheng Li, and Svetha Venkatesh. Bayesian optimization in weakly specified search space. In 2017 IEEE International Conference on Data Mining (ICDM), 2017.
Vu Nguyen, Sebastian Schulze, and Michael Osborne. Bayesian optimization for iterative learning. Advances in Neural Information Processing Systems, 33:9361-995 93771, 2020.
Michael Osborne and Michael Alan Osborne. Bayesian Gaussian processes for sequential prediction. optimisation and quadrature. PhD thesis, Oxford University, UK, 2010.
Fabian Pedregosa. Hyperparameter optimization with approximate gradient. In International conference on machine learning, pp. 737-746. PMLR, 2016.
Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. Advances in Neural Information Processing Systems, 30, 2017.
12

---

Published as a conference paper at ICLR 2024
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian processes for machine learning. Adaptive computation and machine learning. 2006.
Ilya O Ryzhov. On the convergence rates of expected improvement methods. Operations Research, 64(6):151--1288, 2016.
Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. Lower bounds on regret for noisy gaussian process bandit optimization. In Conference Learning Theory, pp.
PMLR, 2017.
Warren Scott, Peter Frazier, and Warren Powell. The correlated knowledge gradient for simulation optimization of continuous parameters using gaussian process regression. SIAM Journal on Optimization, 2163)996-1026, 2011.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Md. Mostofa Ali Patwary, Prabhat, and Ryan P. Adams. Scalable bayesian optimization using deep neural networks. International Conference on Machine Learning, 2015.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process op- timization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning. ICML'10, pp. 1015-1022, 2010.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference Artificial Intelligence and Statistics, pp. 82-90. PMLR, 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas. and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: 1309.66300.899 2013.
Emmanuel Vazquez and Julien Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions, Journal of Statistical Planning and inference, 140(11): 3088-3095, 2010.
A Helen Victoria and Ganesh Maragatham. Automatic tuning of hyperparameters using bayesian optimization. Evolving Systems, 12:217-223, 2021.
Martin Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Ziyu Wang and Nando Freitas. Theoretical analysis of bayesian optimisation with unknown gaussian process hyper-parameters. arXiv preprini 1rXivv1406.77555 2014.
Aaron Wilson, Alan Fern, and Prasad Tadepalli. Using trajectory data improve bayesian opti- mization for reinforcement learning. The Journal of Machine Learning Research, 15(1):253-282, 2014.
Jia Wu, Xiu-Yun Chen, Hao Zhang, Li-Dong Xiong, Hang Lei, and Si-Hao Deng. Hyperparameter optimization for machine learning models based bayesian optimization. Journal of Electronic Science and Technology, 17(1):2644) 2019.
Li Yang and Abdallah Shami. On hyperparameter optimization of machine learning algorithms: Theory and practice. Neurocomputing, 415:295 2020.
Dawei Zhan and Huanlai Xing. Expected improvement for expensive optimization: a review. Journal of Global Optimization, 78(3):507-544 2020.
13

---

Published as a conference paper at ICLR 2024
A BAYESIAN BILEVEL OPTIMIZATION ALGORITHMS
In this section, we will present the algorithms employed in this study. To commence, we will introduce Bayesian bilevel optimization utilizing the expected improvement acquisition function as follows.
Algorithm 1: Bayesian bilevel Optimization with El acquisition
Input: Place a Gaussian process prior on I(>,0% 0x)
for 0, 1,
..... ...,,
1 do
for j = 0, ...., . - 1 do
Update model parameters using SGD: end
xxt = 8%, -nj VoV 82 2/7
Observe UI (Ne, A. Smaa) and Update posterior distribution L using all data. Select the next hyperparameter Ae+1 by maximizing the acquisition function (T) with the incumbent n4 min Pc-1 (A₃).
A411 argmax, E [max (ut L (2,03).0) Hid]
end
Return points X argmin sigs 14-1 (Ax) and AN for all stST. X
Next, we will introduce Bayesian bilevel optimization using the upper confidence bound acquisition function.
Algorithm 2: Bayesian bilevel optimization with UCB acquisition
Input: Place a Gaussian process prior on L(>, (5)
for f = 0, 0......,
do
for j = 0, 1, ,..,, N do
8xt 02, my Vol (Me, 0x:0))))))
end
Yr represents the observation of L(),, 83 where y1 Lall (Xe, BN Swal).
Update the posterior probability distribution L using all available data. Select the next hyperparameter A by maximizing the acquisition function UCB;(A).
A = argmaxx (- (a() + (4410,(A))
end
Return points x = >₂ and N for all ST X
B PROOF OF THEOREM 1
At the inner level, keep the hyperparamettess À fixed and treat them constants, while employ SGD to train and optimize the model parameters 0. To establish an upper bound on the excess risk Leal (A, ON ,Svaa) ) L(>, 02), we introduce effective decomposition method:
L pat (X,0% Seal) L (A, L (Λ, N smal) L (A, ON.0N. S
Term 1
L St)) L" (A, + (T) (B.1)
Temm2
Term 3
Next, we proceed upper bound the excess risk by individually upper bounding Term 1, Term 2, and Term 3.
Upper Bounding Term 1
Directly upper bounding Term is challenging because there is no direct connection between the validation error T val (>, 0N Swal) and the training error 1 (), 0N Str). However, we can
14

---

Published as a conference paper at ICLR 2024
observe that both the validation set S and the training set Str are drawn from the distribution D. Therefore, by using the expected error L(x, 8x) Bewp[((A, 8% .)] as bridge, we can establish connection between the validation enror and training error. This allows to decompose
T, (2, 0N Swal) 1. (2,0%, (trr) into:
T,ual (X, 0x sual) T. (N,0N,
= L.al (1.0% Soal) 1(),08) + I(2,0N) - 1 (A, .5tr
(B.2)
Term 4
Tonn
Lemma 5.
Let the validation error be I, vo (A, 0N .svul)= = E E(), ON 22 )aa). Similarly, let the
training error be (X, 0% , + Ei=1 E(), 0x =24"), By choosing N = n = m and vj x N-
we can establish that, with probability of at least 1 -d,
Led (x, s L (X,0% Str) O (N log log.v).
To prove Lemma provide the definition of stability below, along with some useful concentration inequalities.
We use (S)) to represent the model obtained when applying algorithm A to the dataset S. Note that we omit the dependency of the notation on A, which should be clear from the context. Additionally, omit the hyperparameters À since we keep them fixed and treat them as constants at the inner level. Two datasets are considered neighboring datasets they differ by only one example.
Definition (Uniform Stability Bousquet & Elisseeff (2002)) A randomized algorithm is e uniformly stable if for all neighboring datasets S E D we have sup, [e (0(5), (0(S"), s e.
Lemma (MeDiarmid's Inequality). Consider independent random variables Z,," ... 7n E and mapping Z" + R. for all i E {1.... , and for all 21, , 24 Z, the function satisfies
1 (21, 21-1, 2is Zitls'' , & (21, Fi 24, 2441," ". , Sc
then,
2t
... Zn. ,.,) Ed (Zi...., Zn) t|) 2 exp
nc²
Furthermore, for any 8 E (0,1) the following inequality holds with probability least 5
1ó (Z1, ..... Zn. - E (Zz, Z.)1 CV (log((2//)
V2
Lemma 7 (Chernoff's Bound Wainwright taking values in {0, 1}. Let X E/= Xj and = E[X}. Then for any 5 > 0 with probability
Let X1...., Xe be independent random variables
at least 1 -exp (- uØ² (2 - i)) we have X < (1 + 8)P. Furthermore, for any E (0, with probability least 8 we have
X X +og (1/0) + V log(1/)))
Lemma 8 (Generalization Error (Bousquet et al. (0220)). We employ ((S) to represent the model obtained when applying algorithm the dataset S. Under the uniform stability condition (3) with parameter and the uniform boundedness of the loss function E(-,.) S M, we have that for any E (0, 1), with a probability of at least
I (O(S)) 1. 1. (0(S)) (< (0 log ( M n-
(
n log
Proof of lemma 5 For the sake of brevity in the proof, omit the hyperparameters X. Consider two samples, and S" each consisting of n data points, differing by only a single example. As we run SGD these samples, generate gradient updates 0,,-.., Oy and 0 .., Byy for samples $ and
15

---

Published as a conference paper at ICLR 2024
S", respectively. Now, let's assume, without loss of generality, that the difference between S and S solely attributed to the first example. Applying the Lipschitz condition to E(., 2), we obtain:
(0v. e (f'x= =)1 I KŌN,
(B.3)
where 8y 1|O 0' It's worth noting that during the j-th iteration, there is probability of (n 1)/n that the sample selected by SGD is the same in both sets S and S'. The properties of convexity and y-smoothness, as outlined in (Hardt al. (2016), establish that for any pair of 0 and 0', the following holds:
(V V)(00,))0
Ve(02)) vE(O',=)1
In the event that je is not equal to based on the inequality fi _ 2/7 we can deduce that:
10++1 0+1ll
|10; 0/12
21j (v 00)) n (e Ve Ve 20)
21) v} (0),),2)))))) v Ve
< |0,
0/12
(/,1,
< |0
03112
(B.4)
In the scenario where the probability selecting a different example is 1/n, i.e., je 1, we can utilize the triangle inequality and the previously mentioned inequality to establish the following:
|0 - f++Ll
|00 11 ve (0), =j.) ( V (O,, VV (0,,
n1
< |10, 0B1l + 2n;K.
By merging the two cases mentioned above, conclude that for every
|10 اl11| < 110 0jll 2n, K[
where ll represents the indicator function. By solving the recursive inequality, we obtain:
10 - 0'42/1 < 2K Σ ny G.=1 S 2Kn
Σ |.
(B.5)
j=1
Invoking Lemma whereby X, = [= and holds with probability of at least 1 -
N/n, we obtain the subsequent inequality that
D-= S N/ + 22N log(1/8).
Consequently, with a probability at least 1 - 8, the following inequality is satisfied:
03+1 0f+1l < 2Kn(NNnn //n log(1/6) -2Nn-1 log(1/8)).
Then derive the ensuing incquality with probability of at least 1 - 8:
[[@(S) - ((S'))l s 2Kn(N/n + log(1/6)) + /2Nn (og(1/6))
Substituting the inequality back into Eq. B.3 we arrive at the following result holding with probability of at least - 5:
L (B(S); 2) e (((S'))
log + 22Nn
(B.6)
Subsequently, can bound Term by applying lemma with a stability parameter 22 log(1/8) +
With probability of at least 8, we obtain:
L IA,, -" (A,0%,5*) = OnNN' log log (1/5) - M / log-loo (1/5)-
(B.7)
16

---

Published as a conference paper at ICLR 2024
Next, begin by addressing Term 4, denoted L (x, O ,5aa)) L(A, )₂ where S {apol) 1= Notably, 0x is obtained by training Str which is independent of gmal Then, have:
L (A,0%) E| (>, 1. sval)).
Furthermore, since f(), 0, 2) is uniformly bounded by M, observe that for Sual and goall differing by only one example, we have
L (2, S -L S,
1 m
Σ e (A.0x
1o)) - Σ l (2.00 =2t01))
M
m
Then we can apply lemma 6 with
M to obtain, with probability at least 1 8.
v (>, ON smal) L. (2, ON)
My 2m
log(2/6).
(B.8)
By substituting inequalities B.8 and B.7 into equation B.2
establish that, with probability of
at least 1 - 6,
va (A, ON gwal) L (N,0N.5
=0 (nn log log(1/0) (1/5) M log(/1)((1/) M m log
M log(2/6))
By the choice of x n m and 1j N we can deduce that, with a probability of least
L val (N,ON, Sual) L
(N- log N)
(B.9)
Upper Bounding Term 2
We introduce the following lemma to bound Term 2, which quantifies the optimization error.
Lemma 9 (Optimization Error (Lei & Tang 2018)). Assuming that the function E(0) is convex and
L-Lipschitz continuous with respect 6, we run SGD with step sizes T) = = VN Then, with probability of at least 5, we can establish that:
(0) - inf
L'* inf = O(N - log (N/6)).
Lemma 10. Select d E (0, 1). Set the step size of SGD 1): = Jx. Then, with probubility of 1 8, we achieve:
1 (>, (X,ON, 1r (2, 00 St) (N log
log (N/6)).
Proof of Lemma 10
We should take note that, based on equality 3.1
with 0 arg min L(A, 0), we
derive
1 (2,02, 2 inf T (A.0.5
From lemma 9 we can obtain
"r (A, S inf L (A, 0, Str) = 1N
log
Combining the above two incqualities, we derive
- (A, ,trr " SAr = -" (>, N. (tr)) inf t (2,0, + inf Lr (2,0,5t)) 1 (2, STM)
=0 -O(N-i log (N/6))
17

---

Published as a conference paper at ICLR 2024
Upper Bounding Term 3
Lemma 11. Choose a value for 8 from the interval (0, 1). Then, with a probability of 8, we obtain:
T 02,0, (2, 0 (
It is worthy of note that 8x, is independent of Str Moreover, as E(A, 8, 2) is uniformly bounded by M, we can discern that for Str and 5tr differing by only one example, there exists:
Proof of lemma 17
L (A) -
(t) -1"
LnTh -
Ee(,,0 - -E((N00==
M
i=1
i=1
Consequently, we can invoke Lemma 6 with c= M
to attain, with probability of at least 1 - 6:
- (A,0), L (A M
log(2/8).
2n
By the choice of N x n, we can deduce that, with probability of at least 1 -
Lr (X, S ((, o (NT
Through the aforementioned handling of Terms 2, and 3, we can ultimately derive the excess risk bound that we are interested in.
Proof of Theorem 7 Combining Term in lemma 5| Term 2 in lemma 10 Term in lemma []
with the decomposition B.1 by the choice of N x n x m and 1) x N-2, we can deduce that, with probability of at least 0,
yal (2,0% Swal (2,05)
o ((x² log N (1/6) + M (lo((1/5) + M /lg((25) + log 4/2 (N1/6)
k
(N-1/2)
When we neglect constants like K, M, and 6, we can derive the result:
1ooal (2, (Saa)) L. (A, 03) o (N log N)
The proof is complete.
C PROOF OF LEMMA
In previous works, the assumptions regarding the noise e, differ from those in our work. Srinivas et al.] (2010) and Nguyen & Gupta (2017) assume that the noise is uniformly bounded by ar, whereas Chowdhury Gopalan (2017) and Gupta et al. (2022) assume that the noise is conditionally R-sub-
Gaussian. Furthermore, most prior research assumes that the noise sequence { martingale
difference sequence. In contrast, our noise follows E, = L val (Xe, NN Swal) - (Ae, 8%,). which clearly does not align with the assumptions made in previous works. Consequently, cannot directly apply theorems similar to those in previous research that express the concentration of the posterior mean around the true objective function.
We follow the framework in Srinivas et al. (2010) to prove lemma
Let's revisit the posterior mean function denoted as nr(-) and the posterior covari- ance function denoted as ke(-s)) as discussed in Section 3.2.2, taking into account the data points (Xi, V:) for 1,...,tt t.. It becomes apparent that the RKHS norm associated with the kernel k can be expressed as:
Proof of lemma 2
[L. 8*) I12, = ||L( 0:) +
Σ L (Ni, 02,))
(C.1)
18

---

Published as a conference paper at ICLR 2024
This suggests that (A) and Mr. (A) equivalent for any t. Given that the reproducing property holds, ie., (L(., 8.), kel,, 2)),, = L(2, 0x) for any L(.,0") E Hx, (A), then,
(m(A)) 1(203)1 (x,A, 1) 11 0,), ox( llme I(.,8,)lla.
(C.2)
Recall that the posterior mean function is given by:
(x(A) = kx(2)) (Kr+ -1 y
Then, also have:
(me, I(,0,)) = LL(,,, 02)" (K, + d²1) -1
yv.
(C.3)
where (A(),))) = [L(11, 8% ).... L(),, (1,,,0%,)7 1r. Additionally, the RKHS norm of 44 is given by: | = v. (K, + 0²1) v-- + o²)) y: yel..
(C.4)
Moreover, for we obtain:
pc(),) = - Ki (K + 0² Y1
S Kr + +021) (K, + 1² -1
yt - 0'8, (K, + d²1) y
y 0² 8 (K, + o²1) -1 yt
(C.5)
where 8,, represents I-dimensional vector where only the i-th element is equal to 1, while all other
elements are set to O. Then, referring to Equation C.1 we can derive:
l - L(.,0")l1e. = 11me - -(.00")11 +
Σ (me(A,s) - L (Ar,0,))))
=1lmell + ([ - 2 Km,, I(,00)) + to (m)(A) - L (Mr,0%,))
(C.6)
The noise sequence is = {= with E, =y; L 02.). Taking into account equation C.5 we can express this as follows:
(mr(Ar) - (2,,0 0 Σ (et 026 (K, 0²1) -1 y,)²
S o (Ki+
yil1 - 26,"" (Ke + 0²1)
Y: +
| (C.7)
Considering IL(,,0")] l is bounded by B, the upper bound of the noise from Theorem 1 and the positive definiteness of K, II we can substitute equations C.3 C.4
and C.7 into equation C.6
derive, with probability at least - 6:
l| L(. 11
||,(,00)113 < Ba - (NN
vo (K,+ 021) V: + -2 2|
(C.8)
Combining inequalities C.2
and C.8 we obtain that
(A(()) - L (A, 03) 3 210 (
The proof is completed.
19

---

Published as a conference paper at ICLR 2024
D PROOF OF THEOREM 3
First, we will bound the instantaneous regret, given by rr. L (xt, .2x
(A*,0%)). Next,
will aim to find an upper bound for the sum Rr = Σi=1
t=1 Pt.
To derive an upper bound for Tt. we decompose into three constituent terms follows:
r2 L
xx Ox xx
(x",0%-)
L
x 0 L
NJ (N5 0xz
at xx²
ut
+
u4 (x000x))
(D.I)
Term
Term
Term
We introduce the function T(=) = xz)2) + 6(2), where t and & represent the cumulative distribu- tion function (c.d.f.) and probability density function (p.d.f.) of the standard normal distribution, respectively. Now, we define the function (A) as follows: (A) = max {ur"" - L (A. (.00))))))) .0). In this expression, (A) assumes positive values when the prediction is lower than the minimum GP mean observed so far up that point. For all other cases, (A) is set zero. The process of finding the new query point involves maximizing the expected improvement:
X = argmax, E (I(()).
Upper Bounding Term 6. Lemma 12. Choose 8 E (0, and N x m. Then with probability at least 1 8, we have
L (xt. 0% L. (x2 S Sa(N)N-
where az( (N) O (log N).
Proof of lemmal
72
We decompose Term 6 into two constituent terms.
xt
(xt OxF)
= L
xx N
B. Lual . Sval) + I (xt (At, Sual) sual)- - L (Xt.
0
Loal (x NN. Suat). it is noteworthy that ON is derived through training on the dataset Sth which remains independent of the dataset Soal, Consequently, we can establish the following relationship:
In regard to L
x AN x
(xt.0N 1 1xt,o%)=BB = =E
[..aal =T..t (xt,
ON , ,,, smmL)
Moreover, given that E(A, 0, 2) is uniformly bounded by M, when considering datasets Sval and Sval', which differ by only single example, the following assertion be made:
L ral x NN . stma)
L (xt,0% .
(xt ON ,, 2(a) - Σ (2t.0N 2 2x
22 23d)
M
Then we can apply lemma
with e m
to obtain, with probability least 1 8,
(xt ON
x Sual)
(xt0N x+ )
M
1 log
2m
As for the second term Loal (xt, ON S
L (xt 0,+ we can apply the result from Theorem
to obtain:
L val
xx -, 1% Sval
L (xt,0%, 1t:00=
S S(NNN=
20

---

Published as a conference paper at ICLR 2024
where ((V) = O (log* N). Then, combining the above two incqualities and choosing x m, we
deduce that, with probability of least 1 1 6,
T. (xt 1xt 1. (A
(D.2)
where a<NN) O (log² N). The proof is complete.
Upper Bounding Term?
When addressing Terms 7 and 8, adopt the proof framework outlined in Gupta et al. (2022).
with the ability to adapt and apply certain lemmas from Gupta et al. (2022) to our proof following appropriate adjustments.
Lemma 13. (Gupta et al. (2022))
Choose value for 8 from the interval (0. Then, with
probability of 0, we oblain
I (At. 0x+ ut S 3r (2 m (3r + 1) (Ax) + (
Upper Bounding Term 8.
Initially, we establish both the lower and upper bounds for the acquisition function. The following lemma draws inspiration from Lemma 9 in Wang & de Freitas (2014).
Lemma 14. Choose å E (0, 1). For X E A, E T, define Ie (A) max {0, L (2, Then with probability at least we have
((AA) - 3:ot-1(M) & EL(A) S ((A) + (3. + 1))
Proof of lemma 74
If of- (A) O. then (L(A) = ((A) = 0. which leads to trivial result. Now, /¹ -(2.05)
let's assume that 1 > 0. Define g
and M4T - oz-1(A)
We can then establish
1e-1(A)
that:
(L(A) = o (u).
According to lemma 2 can conclude that Iu - 9) S 3, with a probability of least 8. Since 72)2) > 0, T is a non-decreaingg function, and for 2 > 0, 7(2) I + Therefore, we have:
EI((A) < 0. a. (A)r (max (0,4) + (3)
S (A) (max (0, 9} + + +1 = I(A) + (3. + o)
If (A)) 0, the lower bound is straightforward as (A((A) is non-negative. Let's consider the case where (A) > Since (I,(A) 2 and r(2) 2 for all 2, and r(2) + T(-2) 2. Therefore,
we can write:
E.T((A) 2 0 (A)7 (g 3.)
2 o (q- -B) l()) B1oc-1(2).
The proof is now complete.
Lemma 15. Choose E 0.5). Then, with a probability of at least 25, we obtain:
1+ 3c T(B.) 3, ) (Te (Te (3. ((-+1))t-1AA))
n - I (())00)) <
Proof of lemma 75 If o (X+) 0, as per the definition of Elz(A), we find that EI(X*) = Ix(**) 0, which leads to trivial result. Now, let's consider the case where 1--1(X*) 0. If
L (X", 0g. > pt the lemma remains trivial. We will now explore the case where (X", (.))) S nt.
21

---

Published as a conference paper at ICLR 2024
we know that L(X", (--) -14-1(2") 2 -310)_1(X)) with probability of of' 8. Combining this with the fact that L(X", (--) - ure the following holds:
Based lemma 2
conclude that with probability of 1 8,
1 - 14-1 (X*)
0t-1 (X*) 2 -
Recalling the definition of the El acquisition function, with a probability of least 1 8, we can conclude that:
[ ( ((i=M()(x) 20--1
= (2*)
O--1 (1-)
Combining the above inequality with the previously established result E1, (X*) 1( 3,0,-1 (X*) as proven in Lemma [4 we obtain:
3, 1)7 (x*)..
7(-))
Using the above inequality in conjunction with the fact that r(2) 2 +(==)) for Br, we obtain
T(8r)
1+ 3,
4 (A*) & (((:)) -18 EI, EI') S
EI. (X).
(D.3)
- -
In accordance with Algorithm A = argmax (A). When combined with the upper bound from
Lemma 14
deduce:
EI, (X*) S ET, (A.) S (A,) (8. 1) (Ax)
(D.4)
Utilizing the inequalities
D.3 and D.4, we obtain
p4 - L (X", (x)) Le (A²)
1+ Bt
EL (X*)
T(3.) -B,)
1 3r
(I, (8 (20).
(D.5)
((8))- -B:)
The proof of lemma 15 is complete.
Upper bounding the immediate regret. r; = L (Xt. L (X*, (1),0))). Combining lemma 12
for Term 6, lemma 13 for Term and lemma 15 for Term 8, conclude with high probability that:
1+ 3, ((3))
Tt S
3. + 2 [4((A)) + (3t + 1) 01- +aN)N
(D.6)
Upper bounding the eumulative regret. Rr Σ Tt. Based on the above inequality, we can derive an upper bound for the cumulative regret as follows:
Σ n
T
1 Br (((3r-
Br + (2
Σ +(2))((1
T
+1) Σ 0 (Ne)
TT(NN)--
Term
Term 10
(D.7)
We now introduce lemma 16 and lemma 17 from Gupta et al. (2022) and Chowdhury & Gopalan (017) to assist in bounding Term 9 and Term 10.
Lemma 16. Gupta et al, 2002 Select from the interval (0, 1). Then, with a probability of at least
1 6, we can establish that:
T
Σ 1(xc) = o (STVTT)
22

---

Published as a conference paper at ICLR 2024
Lemma 17. Chowdhury & Gopalan (2077) Let .i...., de represent the points selected by algorithm
7 The sum of the predictive standard deviations at these points can be expressed in terms of the maximum information gain. To be more precise:
I Σ 0 T01-1(A0) (A)) (2)= =0(VTT))
Ultimately, based the above analysis,
demonstrate Theorem 3 as follows.
Proof of Theorem By combining the results in Lemma T6 Lemma 17 with Inequality D.7 derive an upper bound for the cumulative regret Σ Ft follows:
BT + +T ((BT) Br
R
o
(D.8)
t=
where Br = /B² 1B++ to -
N we select N x T, we can deduce that:
R7 Σ rt 0 1=000TT) (VTTT):
(D.9)
E PROOF OF THEOREM 4
In this section, we present the proof for Theorem 4
Proof of Theorem follows:
To derive an upper bound for Tt, decompose it into two constituent terms as
r2 T,
NN T. 03.)
NN L (1t 0x7 + (xt - (3
(E.1)
Term 11
Term
From inequality D.2 we can derive an upper bound for Term 11:
L (xt. 0%% - L (x= S Sa(NNN-
(E.2)
Where ax (N) = Oloo 3/2 N). Notice that at each round 2 1, based on the selection of X in we have
Algorithm i.e., A argmax, a (A) B
-M:-1(A") + (,0,- -m-- - + (.ot-1(At)).
From lemma we have
-(XX707-) - - (10
(xx, (x+00)) - 1 - 3,0,-
Utilizing the above three inequalities, we can derive an upper bound for Term 12:
L (xt 03+ L (2*,05-) < L (xt,0 03 1 -4-1(1*) (10)-1(A*))
< L (xt 0x/
Mr ( 1.0,-1(17))
28 (2,)
(E.3)
23

---

Published as a conference paper at ICLR 2024
By combining the upper bound E.2 for Term 11 and the upper bound E.3 for Term 12 with Equation E.1 we obtain
RT Σ Tt S 2
O-- (1t) Ta(N)
From lemma 17 We have > Oz- (At) - O (VTT)). Additionally, according to the definition,
have BT B 2T (N)NNN Hence with probability least 1 6,
= VB22 + TN-1)
(E.4)
If we select N x T, we can obtain that:
Rr 00 0 (vTTM)
(E.s)
F EXTENSIONS
In this section, we present some extensions of our analyses. We consider two extensions: extension to non-convex scenarios and extension to non-smooth scenarios.
F.1 EXTENSION TO NON-CONVEX SCENARIOS
In this section, we extend Theorem | to non-convex loss functions as follows.
Theorem 18. Suppose that the function E(x, 0, 2) is K-Lipschitz and 7-smooth with respect to 0,
uniformly bounded by M, and also satisfies z V Vol 0, 2)ll² p(E(,,
(1), μ >
2j+1 We perform SGD with step sizes = 2μ(+11² on a sample Stx drawn from the distribution D at
the inner level. Let Seal = {zp i=1 represent the validation set drawn from distribution DD Suppose y S p/4. Choose N n x m. Then, with probability of at least 8, we have:
L (X, Seal) L(,, 0x) ((N 4 + N 2 #) log N)
As a comparison, if ff 2) 2) is convex and my x N then we have:
L eal (x, ON, Swal) L(A, 0%) o (N log.N)
Proof of Theorem
18
To establish an upper bound of the excess risk of the inner-level SGD, denoted - L (A, 0)). we introduce highly effective decomposition method:
as I yall (x, AN
val (N,0N, Sual) L (A,05) L vol (>, ON Swal)
L(A,ON) + L(A, ON) L (A, 0Ι) (F.I)
As clucidated in Remark 5 Lei & Ying (202T), based on the pointwise hypothesis stability analysis
and the optimization error bound in Karimi et al. (016)), it was shown with probability least 1
(Charles & Papailiopoulos (2018) that
L(>, NN) L (A, 03) =
(F.2)
Vnuuō
N 24p281
From the equation B.7 the proof Theorem I
Section
we obtain
L (>, O tr (2,0N, Selecting N = m = n. we obtain
St)) (,,NNsstr
o (nNN' log log (1/6) + M Mvn n log (1/6)
(F.3
L (A, M.aaN L() = = N - - log N)
The proof is complete.
Practical insights: Inner Unit Horizon as the Square of Outer-Level Iterations for Non-convex functions. Unlike the case with convex, for the non-convex situation, the optimal number of inner- level SGD optimization iterations N T Hence, we attained the regret bound Ry = O ((TTr)..
24

---

Published as a conference paper at ICLR 2024
F.2 EXTENSION TO NON-SMOOTH SCENARIOS
In this section, we extend Theorem D to non-smooth loss functions as follows. We remove the smoothness assumption by introducing additional term v/N in the excess risk bound. Moreover, we adopt alternative criteria, including weaker conditions, such as defining a-Hölder continuity as: Definition 4. Let > 0, a E 1]. We say Vgl is a-Hölder continuous if for any 01, 82, 2, X,
[Vel(2,01.3) Vel(A, 02. 2)1l - 7/10 02112.
The theorem is updated as follows
Theorem 19. Suppose that the function E(A, 8, 2) is K -ipischhitz continuous, and convex with respect to 0, uniformly bounded by M. Let 3.- We perform SGD with step sizes Ti rj 22 N on sample Str drawn from the distribution D at the inner level. Let Soal { Ji=1 represent the validation set drawn from the distribution D. Choose N x m. Then, with probability of at least 1 - 8, we have:
L (X, 0N Seal) L(),0)) - -N Plg((N) N log((N) (ogg(N++N+ - log(N))
Furthermore, ( 0,2) is a-Hlölder continuous, then have:
1, 1, 0, stal) 1(),0%) =0 - log((N log(N) N Plg((N +N- log()))
As a comparison, (), is smooth, then have:
L (>, Sval) ((x,0)) O (000)=OON-PPPP (N-Plog(N) + - log(N))
Proof of Theorem 19 Similar to the proof of Theorem in Section B for establishing upper bound on the excess risk L Lval (2, Sval) - L(A, 02). we employ an effective decomposition method:
L val 1N - L (1,05) = val Seal) - L (A. str
Term
+ L ON St)) L (A, 02, + to
L (2,0)).
Term
Term 11
Regarding Term 10 and Term 11, based on Lemma 10 and Lemma
we derive:
1h (>, 0N S*r)) I," (2,0%, Str)
dr (>, A, (x,6%.8*)) -2,
0 (NN+ + log()))
o (N~ log(Av)).
(F.4)
For Term we decompose it as follows:
Lval (2,0 Swal) -L (A, Bo,NN,S str) I vol (>, -.A (2, (2.0% S(T)
As demonstrated in B.8 we utilize Lemma with M to acquire, with a probability of at least
1-8. 8,
1
v (>, 0N Swal) I (2, RN) s My 2m
l2g(2/8).
(F.5)
Choose xxn n m, we obtain:
val (A. BN sval) I (2, = =0 )
(F.6)
Concerning the generalization error L(A, NN - L (A, (N.0N, , Theorem 3.3 in Bassily al. (2020), we obtain, with a probability of at least 6,
Stt), by combining Lemma with
L(),0N) " (N.0N. o N log N + N log N + N
(F.7)
25

---

Published as a conference paper at ICLR 2024
Then, obtain:
L val (A, (A,0% 5 L(A, 85) - =0 ONN logg N N (og + - (ogg log(N))
Furthermore, if E(A, 0, 2) is a- Hölder continuous, then by combining Lemma g with Proposition G.I. Lei & Ying 2020), we obtain, with a probability of at least 6,
L(A, 8 L (2.0% 5th) (N
log + N log
(F.8)
Then, obtain:
L pal (x, 0% Stal) 1(),03) -0 -N log(N) + N Plg((N + - -=g((N)
The proof is complete.
26


Reviews:
[{"review_id": "EcsIXG5c5l", "reviewer": "Reviewer_pR2Q", "summary": "This is paper presents the first convergence analysis of Bayesian bilevel optimization where the outer level is hyperparameter tuning and the inner level is SGD. The key results are sublinear regret bounds showing the convergence behaviors of both outer and inner optimization problems. The key technical novelty is modeling the excess risk of SGD training as the noise of the outer Bayesian optimization. This paper doesn’t have experiments.", "questions": "1. Why is modeling the noise as a martingale difference a key limitation? Why does this approach not align with hyperparameter optimization? See fourth line of page 2.\n2. In third line of Section 3.2, you assume function L has a uniquely determined value for each \\lambda. In my understanding, it is needed otherwise some \\theta rather than \\theta* may lead to lower value given some \\lambda and it would be hard to define regret. However, do you have more justification on this assumption especially in practical scenarios?\n3. What’s $\\varphi(N)$ in Theorem 1?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. First convergence analysis of BBO is important, which is the main contribution of this paper.\n2. I appreciate the innovation that modeling the excess risk of inner level SGD-trained parameters as the primary noise source of outer-level BO. It makes great sense in this problem setting.\n3. I like “practical insights” sections, which are helpful.\n4. The whole paper is well written and easy to follow except some notation problems mentioned below.", "weaknesses": "1. Motivation of BBO is not very clear. No detail is shown in “significant promise in engineering applications” in 2nd paragraph of Introduction.\n2. Convexity assumption in Definition 1 is strong. How can you assume the loss function is convex given potentially non-convex objective function? I want to learn more justification from the author.\n3. L is taken as both loss function and Lipschitz constant, which introduces some confusion.\n4. Upper bound in Theorem 1 is too vague, only showing dependence on N. How does it depend on other terms?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mtiRS6jbsE", "reviewer": "Reviewer_66Ye", "summary": "The paper focuses on Bayesian bilevel optimization (BBO), which combines outer-level Bayesian opti- mization for hyperparameter tuning with inner-level stochastic gradient descent (SGD) for model parameter optimization. The paper proves sublinear regret bounds for BBO using expected improvement (EI) and upper confidence bound (UCB) acquisitions. This provides theoretical assurance that BBO enables simul- taneous convergence of parameters and hyperparameters. For EI, the optimal number of SGD iterations is shown to be N ≍ T 2, balancing training and tuning. This achieves regret savings compared to previous works. For UCB, sublinear regret is proven even with fewer SGD iterations, showing UCB is more robust to SGD noise. The UCB balancing coeﬀicients are adapted based on the SGD/Bayesian iteration ratio. The analysis bridges the gap between Bayesian and bilevel optimization frameworks by modeling SGD excess risk, which enables adapting convergence guarantees to the BBO setting.", "questions": "(1) How do the convergence guarantees extend to deep neural network training? Are there any unique challenges posed by DNNs?\n\n(2) For the inner-level SGD, will using SVRG or introducing acceleration techniques lead to better corresponding results compared to standard SGD?\n\n(3) Do assumptions such as the bounded RKHS norm of the objective function correspond cleanly to properties of other priors?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) The paper provides a new theoretical analysis bridging the frameworks of Bayesian optimization and bilevel optimization by modeling the excess risk of SGD-trained parameters as noise to tackle challenges in convergence guarantees for BBO generalization performance.\n\n(2) Based on a noise assumption better suited to practical situations, the authors derive sublinear regret bounds for Bayesian bilevel optimization using the expected improvement function, which is better than previous work.\n\n(3) By introducing adaptable balancing coeﬀicients $\\beta_t$ for the UCB acquisition function, the paper establishes a sublinear regret bound for BBO with UCB that holds with fewer SGD steps, enhancing inner unit horizon flexibility and overcoming limitations of rapidly increasing coeﬀicients from previous analyses.", "weaknesses": "(1) The current paper is primarily theoretical with a lack of numerical experiments on actual data, which limits the persuasiveness. Experiments using real-world hyperparameter tuning tasks could offer tangible evidence of the convergence behavior and help assess how well the assumptions fit such scenarios.\n\n(2) This paper focuses solely on Gaussian process priors for the Bayesian optimization portion, but the choice of prior may significantly impact the convergence guarantees. The current analysis leverages nice properties of GP priors and posters but may not directly extend to other priors that require different proof techniques, which could limit wider applicability.\n\n(3) Bayesian optimization is adopted for hyperparameter tuning at the outer layer, so the algorithm in this paper may require extensive sampling and integration to estimate the posterior distribution, making it computationally demanding and diﬀicult to apply to high-dimensional complex problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yCjPg4ejXb", "reviewer": "Reviewer_PGhy", "summary": "This paper introduces the initial theoretical assurance for Bayesian bilevel optimization (BBO). It is proved sublinear regret bounds suggest simultaneous convergence of the inner-level model parameters and outer-level hyperparameters to optimal configurations for generalization capability.", "questions": "My concerns are about the experimental results.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This work conducts lots of theoretical analysis Bayesian bilevel optimization (BBO). Specifically, a novel theoretical analysis of convergence guarantees for generalization performance within a BBO framework is provided.\n\n2. A regret bound for BBO using the EI function is discussed in this work.\n\n3. A significant advancement in this research lies in the conceptualization of SGD excess risk as a form of noise within the framework of Bayesian optimization. This approach allows for the adjustment of noise assumptions to better match real-world scenarios and greatly simplifies convergence analysis.", "weaknesses": "I can't find any experimental results in this work. I understand this work puts more attention on the theoretical analysis in Bayesian bilevel optimization (BBO). However, the authors should also conduct experiments to substantiate the theoretical analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5L9gkOs9ao", "reviewer": "Reviewer_1wgY", "summary": "This paper provides a proof for the convergence of the Bayesian Bi-level optimization (BBO). By modeling the excess risk of the SGD-trained parameters, a regret bound is established for BBO with EI function, which bridges the analytical frameworks of Bayesian optimization and Bi-level optimization. Moreover, the authors introduce adaptable balancing coefficients to give a sublinear regret bound for BBO the UCB acquisition function.", "questions": "What is the fundamental difficulty of establishing convergence of BBO compared with other Bi-level algorithms?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is theoretically solid. Useful regret bounds are provided and a convergence framework for BBO is established.\n\n2. The paper is well-organized. The motivation, technique, proof schemes, and results are clearly stated.\n\n3. Some tricks presented in the paper are interesting. For example, the adaptation of balancing coefficients could be a useful technique in other Bayesian applications.", "weaknesses": "1. The regularity assumptions are not intuitive. It would be better if the authors provided some real applications and models satisfying these assumptions.\n\n2. Some assumptions are restrictive from the view of optimization, like the Lipschitz continuity and smoothness conditions in Theorem 1. Only a few classes of functions *simultaneously* satisfy them on $\\mathrm{R}^d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)