Risk-Controlling Model Selection via Guided Bayesian Optimization
Authors: Bracha Laufer-Goldshtein
Adam Fisch
Regina Barzilay
Tommi Jaakkola
Venue: Accepted by TMLR ()

Abstract: Adjustable hyperparameters of machine learning models typically impact various key trade-offs such as accuracy, fairness, robustness, or inference cost. Our goal in this paper is to find a configuration that adheres to user-specified limits on certain risks while being useful with respect to other conflicting metrics. We solve this by combining Bayesian Optimization (BO) with rigorous risk-controlling procedures, where our core idea is to steer BO towards an efficient testing strategy. Our BO method identifies a set of Pareto optimal configurations residing in a designated region of interest. The resulting candidates are statistically verified, and the best-performing configuration is selected with guaranteed risk levels. We demonstrate the effectiveness of our approach on a range of tasks with multiple desiderata, including low error rates, equitable predictions, handling spurious correlations, managing rate and distortion in generative models, and reducing computational costs.

Published in Transactions on Machine Learning Research (10/2024)
Risk-Controlling Model Selection via Guided Bayesian Opti- mization
Bracha Goldshein
blaufer@touer..oo tou.
Deportment of Electrical Engineering
Avi University
Adam Fisch Google DeepMind
fisch&google.cc com
Regina Barzilay
regina @csanl..cammmm mit edu
Compuler Science and Artificial Intelligence Laboralory (CSAIL) Massachusells Institute of Technology
Tommi Jaakkola
tommi&kcaal. mit, edu
Computer Science and Artificial Intelligence Laboratory (CSAIL)
Massachusetts Institute of Technology
Reviewed on OpenReview: https: openreview. net/ forun? id= Bu
Abstract
Adjustable hyperparameters of machine learning models typically impact various key trade-offs such as accuracy, fairness, robustness, inference cost. Our goal in this paper is to find a configuration that adheres to user-specifted limits on certain risks while being useful with respect to other conflicting metrics. We solve this by combining Bayesian Optimization (BO) with rigorous risk-controlling procedures, where our core idea is to steer BO towards an efficient testing strategy. Our BO method identifies a set of Pareto optimal configurations residing in designated region of interest. The resulting candidates statistically verified, and the best-performing configuration is selected with guaranteed risk levels. We demonstrate the effectiveness of our approach on a range of tasks with multiple desiderata, including low error rates, equitable predictions, handling spurious correlations, managing rate and distortion in generative models, and reducing computational costs."
1 Introduction
Deploying machine learning models in the real-world requires balancing different performance aspects such as low error rate, equality in predictive decisions (Hardt et al., 2016; Pessach & Shmueli, 2022), robustness to spurious correlations (Sagawa et al., 2019; Yang et al., 2023), and model efficiency (Laskaridis et al., 2021; Menghani, 2023). In many cases, we can influence the modcl's behavior favorably via hyperparamoters that determine the model configuration. However, selecting a configuration that accurately aligns with user- specified requirements on test data can be particularly challenging. This complexity is amplified when the process involves numerous possible configurations that demand significant resources evaluate, such those necessitating the retraining of large neural networks for novel settings.
Bayesian Optimization (BO) is widely used for efficiently selecting configurations of functions that require expensive evaluation, such as hyperparameters that govern the model architecture or influence the training procedure (Shahriari et al., 2015; Wang et al., 2022; Bischl et al., 2023). The basic concept behind BO is to substitute the costly function of interest with a cheap, easily optimized probabilistic surrogate model. This surrogate is then used to select promising candidate configurations while balancing exploration and
Ouu code available https://gåthhi: wwwp:/ach.abbaaaaaeeeaaaa http:/rrccha-aaffee/uiidd..

---

Published in Transactions on Machine Learning Research (10/2024)
Demographic Parity
Region of Interest
Bound
Error
Model
Minimize
Demographic Parity
M
22
Sensitive Attribute Female
Error
Figure 1: Demonstration of GuideBO for algorithmic fairness with gender as sensitive attribute (left). We would like to set the model configuration À A2] to minimize the difference in demographic parity, while bounding the overall prediction error by a. Our method (right): (i) defines a region of interest in the objective space, (ii) identifies Pareto optimal solutions in this region, (iii) statistically validates the chosen solutions, and (iv) sets À to the best-performing verified configuration.
exploitation. Beyond single-function optimization, BO has been extended to handle multiple objectives. this context, the goal is to find a set of Pareto optimal configurations that represent the best possible tradc-offs for the given objectives (Karl al., 2022). Additionally, BO can accommodate multiple incquality constraints (Gardner et al., 2014). Nevertheless, none of these mechanisms provide formal guarantees model behavior at test time, and can suffer from unexpected fluctuations from the desired final performance (Letham et al., 2019; Feurer et al., 2023).
The Learn then Test (LTT) framework (Angelopoulos et al., 2021) addresses model configuration selection from a different perspective. establishes a rigorous statistical testing approach for simultancously con- trolling multiple risk functions. The procedure is model-agnostic, distribution-fres and yields finite-sample guarentees. While LTT provides exact theoretical verification, its practical application becomes challenging when dealing with large configuration spaces. The increased computational costs and potential loss of sta- tistical power hinder the identification of useful configurations. To mitigate these challenges, the recently proposed Purelo Tesling method (Laufer-Goldshtein et al., 2023) combines the strengths of multi-objective optimization and statistical testing. The fundamental idea is to leverage multi-objective optimization to sig- nificantly reduce the space of potential configurations. This approach aims to identify Parcto optimal config- urations that are promising candidates for testing. While this method enhances computationa and statistical efficiency, the identified subspace may still include configurations that are irrelevant. may focus on con- figurations that are either valid yet inefficient, or that highly improbable meet the constraints. Therefore, when considering expansive configuration spaces, this strategy can again become costly and statistically loose.
In this work, we introduce GuideBO, new synergistic approach to combine optimization and testing to achieve efficient model selection under multiple risk constraints. Our approach centers around the concept of the "region of interest" in the objective space, which aligns with the goal of achieving testing efficiency while operating within a limited compute budget. To define the region of interest, we consider factors such data sample sizes, user-specified limits, and required cortainty levels. Consequently, we propose an adjusted BO procedure, recovering the part of the Pareto front that intersects with the defined region of interest. The resulting focused optimization procedure recovers dense set of configuratinns, representing candidates that are both effective and likely to pass the test. In the final step, we apply statistical testing to filter this chosen set and identify highly-performing configurations that exhibit verified control.
We demonstrate that GuideBO is a flexible approach applicable across diverse contexts for both predictive and generative models. It effectively tunes various types of hyperparameters that impact the model-whethn prior to training or post-training. Specifically, we show its applicability in the domains of algorithmic fairness, robustness to spurious correlations, rate and distortion in Variational Autoencoders (VAFs), accuracy-cost
2

---

Published in Transactions on Machine Learning Research (10/2024)
trade-offs for pruning computations of large-scale Transformer models, and early-time classification in large language models (LLMs). See Fig. 1 for an example and a high-level illustration of GuideBO.
Contribution. Our main ideas and results can be summarized as follows:
1. We introduce the region of interest in the objective space, which significantly reduces the search space for candidate configurations, thereby leading to more elficient statistical testing with fewer computations.
2. We define a new BO procedure to identify configurations that are Pareto optimal and lie in the defined region of interest. These configurations are subsequently validated through statistical testing.
3. Our approach facilitates risk-controlled model selection in complex and costly settings that necessitate model retraining or involve extensive configuration spaces. We present a broad range of problems, where our approach can be valuable for valid control and effective optimization of diverse performance aspects, including classification fairness, predictive robustness, generation capabilities, model compression and runtime reduction.
4. Through empirical experiments, demonstrate that GuideBO selects highly efficient and verified configurations under practical budget constraints, outperforming baselines.
2 Related work
Conformal prediction and risk control. Conformal prediction is a popular model-agnostic and distribution-free uncertainty estimation framework that returns prediction sets or intervals containing the true value with high probability (Vovk, 2002; Vovk et al., 2015; 2017; Lei et al., 2013; 2018; Gupta et al., 2020; Barber et al., 2021). Coverage validity, provided by standard conformal prediction, has recently been extended to controlling general statistical losses, allowing guarantees in expectation (Angelopoulos et al., 2022) with user-defined probability (Bates et al., 2021). Our contribution extends the foundational work of Angelopoulos et al. (2021), which addresses the broader scenario of controlling multiple risk functions. This is achieved by selecting an appropriate low-dimensional hyperparameter configuration using multiple hypothesis testing (MHT). Additionally, we draw upon the recently introduced Pareto Testing et al., 2023) that further improves computational and statistical efficiency
method LLaufer-oldshhee by solving a multi-objective optimization (MOO) problem and focusing the testing procedure over the approximated Pareto optimal set. In this paper, we point out that recovering the entire Parcto front is redundant and costly and suggest instead to recover focused part of the front that is aligned with the purpose of efficient testing. This enables highly-expensive hyperparameter tuning that involves retraining of large models with a limited compute budget.
Black-box model selection under multiple objectives. The demand for automating the creation of ma- chine learning pipelines is rapidly increasing. Hyperparameter optimization aims streamline this process by fine-tunig model configurations with minimal manual intervention. However, this challenging black-box optimization problem that often involves trade-offs among factors such as predictive performance (Schmucker et al., 2021), computational time (Wang et al., 2019; Lu et al., 2019), and fairness (Pfisterer et al., 2019; Martinez et al., 2020). In this context, we focus on model selection with multiple objectives, incorporating user-specified statistical constraints on certain losses.
Bayesian Optimization (BO). BO is a commonly used sequential model-based optimization technique efficiently find an optimal configuration for a given black-box objective function (Shahriari al., 2015; Frazier, 2018; Wang et al., 2022). It can be applied to constrained optimization problems (Gardner et al., 2014) multi-objective scenarios involving several conflicting objectives (Karl et al., 2022). However, when used in model hyperparamacter tuning, the objective functions can only be approximated through validation data, resulting in no guarantees on test time performance. To account for that we resort to statistical testing, and utilize the effectiveness of BO to efficiently explore the configuration space and identify promising candidates for testing.
BO and Conformal Prediction. Several recent works proposed to integrate conformal prediction into BO in order to improve the optimization process under model misspecification and in the presence of
3

---

Published in Transactions on Machine Learning Research (10/2024)
observation noise (Stanton et al., 2023; Salinas et al., 2023). These works go in different direction from our approach, guaranteeing coverage over the approxination of the surrogate model, while ours provides validity on configuration selection. Another recent work (Zhang et al., 2023) utilizes online conformal prediction for maintaining a safety violation rate (limiting the fraction of unsafe configurations found during BO), which differs from our provided guarantees and works under the assurpttion a Gaussian observation noise.
Multi-Objective Optimization (MOO). Simultaneously optimizing multiple black-box objective functions was traditionally performed with evolutionary algorithms, such NSGA-II (Deb et al., 2002), SMS-EMOA (Emmerich et al,, 2005) and MOEA/D (Zhang & Li, 2007). Due to the need for numerous eval- nations, evolutionary methods can be costly. Alternatively, BO methods are more sample efficient and can be combined with evolutionary algorithms. Various methods were proposed exploiting different acquisition functions (Knowles, 2006; Belakaria et al., 2019; Paria et al., 2020) and selection mechanisms, encouraging diversity the objective space (Belakaria et al., 2020) or in the design space (Konakovic Lukovic et al., 2020). The central idea behind our approach is to design a Obltt-Objecctve BO (MOBO) procodure that recovers a small set of valid and efficient configurations. Subsequently, we calibrate this chosen set using MHT (Angelopoulos et al., 2021).
Additional related work is given in Appendix A.
3 Problem formulation
Consider an input X E X' and an associated label Y E y drawn from joint distribution PXY Pxy?. We learn a model fx: X' + V/ where À E A S R" is an n-dimensional hyperparamcter that determines the model configuration. The model weights are optimized over a training set Drrain by minimizing a given loss function, while the hyperparameter À determines different aspects of the training procedure or the final setting of the model. For example, À can weigh the different components of the training loss function, affect the data on which the model trained, or specify the final mode of operation in a post-processing procedure.
We wish to select a model configuration À according to different, often conflicting performance aspects, such as low error rate, fairness across different subpopulations and low computational costs. In many practical scenarios, we would like to constrain several of these aspects with pre-specified limits to guarantee a desirable performance in test. time. Specifically, we consider a set of objective functions of the form é Pxx x A - IR. We assume that there are e constrained objective functions f,,.... les where (A = Exxy (fx)) and L; y'y'x x + R is a loss function. In addition, there is a free objective function Étren defining a single degree of freedom for minimization. The selection of is carried out based on two disjoint data subsets: (i) validation set D (X,, 1 and (ii) a calibration set Deal (x,, (i) We will use the validation data to identify a set of candidate configurations, and the calibration data to calibrate the identified set. The constraints are formulated by an (or, r-irk control criterion as was defined by Angelopoulos et al. (2021):
PD (A)(A) S ax) 2 1- ViE (l......c.
(1)
where a is the upper bound of the i-th objective function, and is the desired confidence level, both selcted by the user. Note that the probability in (1) is defined over the randomness of the calibration data Deat: namely if 6 = 0.1, then the selected configuration will satisfy the constraints at least 90% of the time across different calibration datasets.
We provide here a brief example of our setup in the context of algorithmic fairness and derive additional applications in $6. In many cases, we wish to increase the fairness of the model without significantly sacrificing performance. For example, we would like to encourage similar true positive rates across different subpopulations, while constraining the expected error. One approach to enhancing fairness involves adding crimess-promottng terms to the standard cross-entropy loss function (Lohaus et al., 2020; Padh et al., 2021; Chuang & Mrouch, 2020). In this case, À contains the weights assigned to each loss term, which are then combined to form the overall training loss. Adjusting these weights leads to different accuracy-fainees trade-offs for the resulting model. Our goal is to select a configuration À that optimizes fairness, while guaranteeing that the overall error would not exceed a certain limit with high probability.
We also address unsupervised learning problems, which do involve labels. For generality, our problem formulation uses both X and Y.
4

---

Published in Transactions on Machine Learning Research (10/2024)
4 Background
In our method, two critical components play a central role: optimization of multiple objectives and statistical testing for configuration selection. We hereby provide a short overview on these topics.
Multi-Objective Optimization (MOO), Consider an optimization problem over a vector-valued func- tion {(A) (f1())....,.4 (A)()) consisting of d objectives. When dealing with conflicting objectives, there is no single optimal solution that simultaneously minimizes all objectives. Instead, there is a set of optimal configu- rations representing different trade-offs among the given objectives. This is the Pareto optimal set, defined by:
Ap (AEA: (X' EA X'
(2)
((X) < ((A), and for some where X' < X denotes that X' dominales X if for every i E (1, (I,...d) d). E (1,...d), dd, (x( < (()). Accordingly, the Pareto optimal set consists of all points that are not dominated by any point within A. Given an approximated Pareto front P, a common quality measure is the hypervolume indicator (Zitzler & Thiele, 1998) defined with respect to a reference point r E R*:
3= - 1 dR
HV(P; r) 10=/
(3)
where H(P:r) = {z f R
and _)(².)) is the Dirac delta function that equals 1 if a E H(²rr) and 0 otherwise. An illustration is provided in Fig. B.I. The reference point defines the boundaries for the hypervolume computation. It is usually set to the nadir point that is defined by the worst objective values, so that all Pareto optimal solutions have positive hypervolume contributions (Ishibuchi et al., 2018). For example, in model compression with error and cost as objectives, the reference point can be set to (1.0, 1.0), since the maximum error and the maximum normalized cost equal 1.0. The hypervolume indicator measures both the individual contribution of each solution to the overall volume, and the global diversity, reflecting how well the solutions are distributed. It can be used to evaluate the contribution of a new point to the current Pareto front approximation, defined as the Hypervolume Improvement (HVT):
P
HVI(((2),P::) HV(((A) UP; -V HP: r).
(4)
where ((A) P denotes the extended set consisting of the current approximated Pareto front and a new point (()). The expression in (4) represents the increase in hypervolume achieved by adding a new point ((A). The hypervolume indicator serves both as a performance measure for comparing different algorithms and as a score for maximization in various MOO methods (Emmerich et al., 2005; 2006; Bader & Zitzler, 2011; Daulton et al., 2021).
BO. BO is an effective method for optimizing black-box objective functions that are costly to evaluate (e.g. selecting the hyperparameters of large neural networks). These methods employ a surrogale model to approximate the expensive objective function and iteratively select new configurations using an acquisition function that balances exploration and exploitation. Formally, we assume a total budget of N iterations, representing the maximum number of allowed function evaluations. We start with an initial set of random configurations
) and their associated objective values Lo (((A)),.... ((AN.)), where No < N. We then perform N - No iterations, each time adding one configuration to the current set C., 1 1 n < N - No, where |c,l denotes the set sizc. Commonly, Gaussian Process (GP) (Williams & Rasmussen, 2006) serves as a surrogate model, providing an estimate with uncertainty given by the Gaussian posterior. We assume a zero-mean GP prior g()) ~ ((A, characterized by a kernel function A A x + R. Let K E IRCCa denote the vector of covariance values K; = <(>,>;) between new point À and a given point X E Cn, and K a |c,l x |c,.] matrix with elements Kij = =(A, X1), i.j E (1...., .....,,C..]:: [- In addition, we define the label vector q E RRCC. consisting of the given objective values 9i = ((x,), E {1,.... I..I.. Based on these definitions, the posterior distribution of the GP is given by A, C.) = N (p(A), A)), with μ²(A) = x(K + + -' q and Σ(A, A) = k(A, - (K + o'1) k. Here o² is the observation noise variance, i.c. E(X,) ~ (g)(),), o²). The next configuration for evaluation, is selected by optimizing an acquisttion function defined on top of the surrogate model. Common acquisition functions include: probability of improvement (PI) (Kushner, 1964), expected improvement (EI) (Močkus,
Co
5

---

Published in Transactions on Machine Learning Research (10/2024)
1975), and lower confidence bound (LCB) (Auer, 2002). For MOO, a GP is fitted to each objective. Then, one approach is to perform scalarization (Knowles, 2006), which converts the problem back into a single- objective optimization, allowing the use of standard acquisition functions. Alternatively, one can employ modified acquisition functions designed for the multi-objective context, such as expected hypervolume improvement, (EHVT) (Emmmrrich et al., 2006) and predictive entropy search for multi-objective optimization (PESMO) (Hernández-Lobato et al., 2016). After selecting a new configuration, it evaluated and added to the updated set C++1- This process is repeated until the maximum number of iterations is reached.
Learn then Test (LTT) & Pareto Testing. Angelopoulos et al. (2021) have introduced LTT, which is statistical framework for configuration selection based on multiple hypothosis testing (MHT). Given a set of constraints of the form of Eq. (1), & null hypothesis is defined as Hx : 3 i where (((A) > a; i.e., that at least one of the constraints is not satisfied. For a given configuration, we can compute the p-value under the hillhhypothesis based on the calibration data. If the p-value is lower than the significance level 5, the null hy- pothesis is rejectod and the configuration is declared to be valid. When testing multiple model configurations simultaneously, this becomes an MHT problem. In this case, it is necessary to apply a correction procedure to control the Homily-wise error rate (FWER), i.e. to ensure that the probability of one or more wrong rejections is bounded by 5. In large configuration spaces, this can be computationally demanding and result in inefficient testing. In order to mitigate these challenges, Pareto Testing was proposed et al., 2023), where the testing is focused on the most promising configurations identified using MOO. Accordingly, only Pareto optimal configurations are considered and are ranked by their approximated p-values from low to high risk. Then, Fixed Sequence Testing (FST) (Holm, 1979) is applied over the ordered set, sequentially testing the configurations with fixed threshold 8 until failing to reject for the first time. Although Parcto Testing demonstrates enhanced testing efficiency, it recovers the entire Parcto front, albeit focusing only
small portion of it during testing. Consequently, the optimization budget is not directly utilized in a way that enhances testing efficiency, putting an emphasis on irrelevant configurations on one side and facing an excessive sparsity within the relevant area on the other, as illustrated in Fig. 2.
5 Method
Our approach involves two main steps: (i) performing BO to generate a small set of potential configurations, and (ii) applying MHT over the candidate set to identify valid configuaatonss. Considering the shortcomings of Pareto Testing, we argue that the two disjoint stages of optimization followed by testing are suboptimal, especially for resource-intensive MOO. As an alternative, we propose adjusting the optimization procedure for better testing outcomes by focusing only on the most relevant parts in the objective space. To accomplish this, we need to (i) specify a region of interest guided by our testing goal, and (ii) establish BO procedure capable of effectively identifying configurations within the defined region. In the following we describe these steps in details.
5.1 Defining the Region of Interest
We aim to define a region of interest within the objective space Ro+1, where we soek to identify candidato configurations that are likely to be valid and efficient during the process of MHT. We start with the case of single constraint (c - 1). Recall that in the testing stage we define the null hypothesis Hy : ((A) a for candidate configuration X, and compute a p-value for given empirical loss over the calibration data feal 1 =j= ((1,, Yj: A valid p-value px has to be super-uniform under the null hypothesis, ie. P (PA < M, for all u [0, 1]. As demonstrated in (Angelopoulos et al., 2021), a valid p-value can be computed based on concentration inequalities that quantify the proximity of the sample loss to the expected population loss. If the loss is bounded by 1, we can apply Hoeffding's incquality to derive the following p-value (see Appendix B.1):
PX == e (2m((---al())
(5)
where (+) = max(-,0) For a given significance level 6, the mull hypothesis is rejected (the configuration is declared to be risk-controlling), when /HF < 8. By rearranging (5), we obtain that the maximum empirical
6

---

Published in Transactions on Machine Learning Research (10/2024)
loss ((A) that can pass the test with significance level 8 is given by (see Appendix B.1):
max a V log (1/6)
(6)
2m
As an example, consider the error rate as loss function, and assume that we would like bound the error rate by 5% (a 0.05), with significance level of 8 0.1. By (6), if the empirical loss of a calibration set of size safe and its error will not exceed 5% on new unseen data drawn from the same distribution.
5000 is up to max = 4%, then we have enough evidence to declare that this configuration is
In the BO procedure, we are interested in identifying configurations that are likely to be both valid and efficient. On the one hand, in order to be valid the loss must not exceed amax, On the other hand, from efficicncy considcrations, we would like to minimize the free objective as much as possible. This means that the constrained loss should be close to m (from bellow) due to the inverse relation wetween the free objective and the constrained objective. An illustration demonstrating this idea is provided in Fig. 2, where the irrelevant regions are: (i) the brown part on the right where the configurations are not satisfying the constraint, and (ii) the green part on the left where the configurations are not effectively minimizing f2 Ideally, we would like to find configurations with expected loss equal to the limiting testing threshold a amax However, during optimization we can only evaluate the loss over a finite-size validation data with |Daal k samples. To account for that, we construct an interval [elow ghizh] around a max based on the size of the validation data. In this region, we wish to include empirical loss values that are likely to correspond to an expected value of max based on the evidence provided by the validation data. Let ()PE((A) (A) $ ,,-,, X) denote the empirical loss computed over Dval- We define the region R(a, k, m, d, 7) containing (A) values that are likely to be obtained under (A) = a mmx with at least - 2y probability. Specifically, there exists a region R(aa k. m, 7), with 7 E (0, 0.5], such that:
IP ((T (A) E R(a, k, m. 6,
= a maxx 2 1 - 2yy
For instance, by applying Hoeffding's inequality, we can derive the following region of interest:
log (1/7)
log (1/7)
R(a, ks m. 5,)))
a max
max
(8)
2k
2k
ghigh
Note that sctting y is an empirical decision that is independent of both the MHT procodure and the chosen significance level 5. For small y the region expands, accommodating more optional configurations but with a lower density, Conversely, a larger Y produces smaller region, leading to denser sampling around the limiting value. Also note that, whenever k increases, the width of the region decreases, reflecting a growing confidence that the observed losses are representative of actual expected loss. In practice, we use the tighter Hoeffding- Bentkus inequality for the p-value computation in Eq. (5) and for defining the region of interest by Eqq. (6) and (8) (see Appendix B.1).
In the case of multiple constraints, the null hypothesis is defined as HA 3 where L((A) > a,, i.c that at least one of the constraints is not satisfied. A valid p-value is given by PA = max PA,i, where px is the p-value corresponding to the i-th constraint (see Appendix. B.2). Consequently, we define the region of interest in the multi-constraint case the intersection of the individual regions (as illustrated in Fig. B.2):
I R(ai, k m, m,d, r)s = (an....,o.))
R(a, k, 6,
(9)
5.2 Local Hypervolume Improvement
Given our definition of the region of interest, we derive BO procedure that recovers Pareto optimal points in the intersection of R(a, k, m, 6,)) and P. Our key idea is to use the HVI in Eq. (4) as an acquisition function, while modifying it to capture only the region of interest. To this end, we properly define the reference point r E gc+1 to enclose the desired region.

---

Published in Transactions on Machine Learning Research (10/2024)
Full Pareto Front
GuideBO
Low risk, inefficient
Region of Interest
High risk, efficient
Budget 10
Gap
e
Figure 2: Left: Illustration the different parts of the Pareto front. The green region consists of configurations that are low risk (&1 < a) but inefficient in terms of the free objective lz. The brown region consists of configurations that efficient but high risk (&1 a) and cannot pass the test. In the middle, define the region of interest containing configurations that likely to be both valid and efficient. Right: comparing GuideBO to full Pareto front recovery for optimization budget N 10. In the full Pareto front method there is no control on the distribution of the configurations over the front, while GuideBO focuses on the region of interest. As a result, comparing the chosen valid configurations (marked by v), there exists a noticeable advantage in favor of GuideBO in minimizing Eg.
Region of Interest
2
Recall that the reference point defines the upper limit in each direction. Therefore, for the constrained dimensions we set (I, using the upper bound in Eq. (8). As
Ti chigh i =
for the unconstrained dimension 1,+1, we can use the maximum possible value of free.. However, this approach may unnecessar- ily expand the defined region to include the green area shown in Fig. 2. In this region, the configurations meet the constraint but are sub-optimal with respect the free objective. Instead, determine the final dimension based on the lower limiting values. Specifically, set rc+1 to the point the free axis that corresponds to the intersection of the lower limits of the constrained dimensions:
flow max a high
E,
(10) Figure 3: GuideBO for two objectives. Ej is controlled at a while &g is minimized. The shaded area corresponds to our defined region of interest.. A reference point (in (11) red) is defined accordingly to enclose the region of interest.
To+1 gtree (ftrce)
where
Afree = arg min
( [elow
plon
where we use the GP posterior mean as our objective estimator, i.e. 9 = μ. As a result, we obtain the following reference point:
(
ghigh
Itrese (Atrec))
(12)
We select the next configuration by maximizing the HVI (4) with respect to this reference point:
A, = arg max HVI
(13)
which leads to recovering only the relevant section, rather than the entire front. We evaluate the objective functions on the new selected configuration, and update our candidate set accordingly. The BО process continues iterating until the maximum budget N is reached. The resulting of candidate configurations is denoted as CRO, Our proposed BO method, GuideBO, is summarized Algorithm and illustrated in Fig. 3 for c=

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 1 GuideBO: Testing Guided Bayesian Optimization
Definitions: li....,fe le and ffree are the objective functions, 91y..., 9c and fivee their associated sur- rogale models. flow,... ,..., flow and phigh ..... fhigh are the lower and upper bounds, respectively, for the first objectives. Co (Ao,...: ANo is an initial pool of configurations and Lo (e(A)).... R(AN.)) are the associated objectives. N is our total budget. ParetoFront() filters Pareto optimal objective values.
1: function BO(E, Co. Lo: {el ,...., eow,, {e) ....,,e N)
2: Nmax f N -Col
r (hishh ...., thigh, maxXECo Crrco (A))
Initialize reference point.
4: for = 0,,,, Nmax - do
5: Fit 9 on (Cn, Lx).
Fit surrogate models.
6:
Te+1 t Dieee (Atrnn); Atrre = arg min (an......,9..... - |
klow lll
D. Update ref. point.
P < ParetoFront(Ca)
Filter Pareto front according Eq. (2).
8:
An+1 = arg m HVT(G(A),Pr))
D Optimize acquisition function.
9:
Evaluate e(An+1)
b Evaluate new configuration.
10:
C.+1= + Cn U Am+1-
> Add new configuration.
11:
Cn+1 t Cn U((nn+)).
b Add new objective values.
12:
CBO CNamax
return CBO
13:
Note that in MOBO it is common to use an HVT-based acquisition function that also takes into account the predictive uncertainty as in EHVI (Emmerich et al., 2005) and SMS-EGO (Ponweiser et al., 2008). However, our preliminary runs showed that these approaches do not work well in the examined scenarios with small budget (N [10, 50)), as they often generated points outside the region of interest. Similarly, for these scenarios the random scalarization approach, proposed in (Paria al., 2020), was less effective for generating well-distributed points inside the desired region.
5.3 Testing the Final Selection
We follow (Angelopoulos al., 2021; Lanfer-Goldshtein et al., 2023) for testing the selected candidato set. Prior lesting we filter and order the configurations in the set CBO, Specifically, we retain only Pareto optimal configurations from CBO, and then sort the remaining configurations by increasing p-values, approximated by D Next, we recompute the p-values based on Deal and perform FST, where we start testing from the first configuration and continue until the first time the p-value exceeds 5. As result, we obtain the validated set (valid, and choose a configuration minimizing the free objective:
X arg min Erree (A). AeColld
(14)
The method is summarized Algorithm C.I. consequence of (Angelopoulos et al., 2021; Laufer- Goldshtein et al., 2023) we achieve a valid risk-controlling configuration, as we now formally state.
Theorem 5.1. Let Dval {X,, Yi and Deal {X,, kmm be two disjoint datasets. Suppose the p-value px, derived from Drat, is super-uniform under Hx for all X. Then the output X of Algorithm C.1 satisfies Eq. (1).
The proof is provided in Appendix B.3. Note that in situations where we are unable to identify any statistically valid configuration (i.c., Cvalid 0), we set X null. To avoid this situation, the user should select. limits a1 o1,..., Ue that are likely to be feasible. In practice, this can be achieved using the initial pool configurations Co, which is generated at the start the BO procedure. This repre- sentative set provides an indication of the possible achievable limits. Specifically, the user may select ag iminxec. (A), maxxec, (())), E c],, and can further refine this choice during the BO iter- ations more function evaluations are accumulated.

---

Published in Transactions on Machine Learning Research (10/2024)
6 Applications
We demonstrate the effectiveness of GuideBO across various tasks with diverse objectives. In each sctting, the definition of varies, affecting the model differently either during or after training.
Classification Fairness. In many classification tasks, it is important to take into account the behavior of the predictor with respect different subpopulations. Assuming binary classification task and a binary sensitive attribute a = 1-,,1), we consider the Difference of Demographic Parity (DDP) as a. fairness score (Wu et al., 2019):
DDP()) = E [I = -1] - E [c = =1].
(15)
We define the following loss, parameterized by = A2], which consists of two regularization terms that prompt fairness:
R(f:A) = BCE(f) + A1 DDP(f) + 22- MixUP(f),
(16)
where BCE() is the standard binary cross-entropy loss, and DDP(J) and MixUP(() reguralize the model's fairness. DfP( is the hyperbolic tangent relaxation of (15) (Padh et al., 2021), and MfxUP(f) is a mixup regularization interpolating samples between groups (Chuang & Mrouch, 2020) (see Appendix D for further details). Changing the values of X leads to different models that trade-off accuracy for fairness. In this setup, we have 2-dimensional hyperparamter À and two objectives: (i) the error of the model ferr = E [](A()))]] and (ii) the DDP defined in Eq. (15) (adp(A) = DDP(fx).
Classification Robustness. Predictors often rely on spurious correlations found in the data (such as background features), which leads to sigmificant performance variations among different subgroups. Recently, Ixmailov et al. (2022) demonstrated that models trained using expected risk minimization surprisingly learn core features in addition to spurious ones. Accordingly, they proposed enhance model robustness by retraining the final layer different configurations, balancing the trade-off between robustness to differences in subpopulations and overall performance across the entire population.
balanced datasct. We modify their approach to generate
Given a dataset 'D (cither the training set or a part of the validation set), we define a paramcterized dataset Dx as follows. Suppose the data consists of samples (X, Y,G), where G E G is the group label and G is the set of all groups present the data. We denote by [g]-dimensional hyperparameter combination that lies in the | probability simplex. The vector À consists of the probabilities of each group appearing in Dx. To create DA, we first sample the group membership label according to X, and then uniformly sample example from the chosen group, allowing for repetition in sampling. Consequently, À is [g]-dimensional hyperparannttr that controls the proportion of each group in Dx. The dataset is considered evenly balanced across groups when all probabilities are equal to 1/|g). It is equivalent to the original dataset when À matches the prior probability over G. We define two objective functions: (i) the average error Lece (A) = E [1 and (ii) the worst error over all subgroups Eworst-err (A) = max,eg E [_)А(X) [G 99)
Robust and Selective Classification. We also examine the case of selective classification and robustness. The selective classifier can abstain from making a prediction when it is unsure (Geifman & El- El-Yaniv, 2017). Specifically, the model abstains when its confidence is lower than threshold T, i.e. fa(x) < T, where fx(x) denotes the probability of the predicted class. This approach can potentially enhance prediction performance by trading-off coverage, defined as the proportion of the population for which the classifter provides a prediction. In this case, we have a [g] + 1-dimensional hyperparameter X' = (A, and an additional objective function of the mis-coverage rale Emis-cover (X') = EE [1
VAE. Variational Autoencoders (VAEs) (Kingma & Welling, 2013; Rezende et al., 2014) are generative models that leverage a variational approach to learn the latent variables underlying the data, and can generate new samples by sampling from the latent prior distribution. We focus on 8-VAE (Higgins et al., 2016), which balances the reconstruction error (distortion) and the Kullback Leibler (KL) divergence (rate):
R(f: B) Epp(()) (x))) |- lo (x|x)]] + B Epais) [Dxr(e<((<)]]]]])]]
(17)
where z RR is the latent embedding, f consists of an encoder ge (z(xx) and a decoder po (x|z), parameterized by @ and 0, respectively, and p(z) is the latent prior distribution. Generally, models with low distortion
10

---

Published in Transactions on Machine Learning Research (10/2024)
perform high-quality reconstruction but generate less realistic samples and vice versa. We define the hyperparameter À = (3, D) consisting of the KT, penalty strength B and the latent dimension D. We specify two objectives Ereco and (KLD(f) defined by the left and right terms in (17), respectively.
Transformer Pruning. We adopt the multi-dimennional transformer pruning scheme proposed in (Laufer- Goldshtein al., 2023), which involves three strategies for reducing computational complexity: (i) token pruning, removing unimportant tokens from the input sequence, (ii) layer early-exiting, computing part of the model's layers for easy examples, and (iii) head pruming, removing a portion of attention heads from the model architecture. We obtain À = (A1, A2, As) with the three thresholds controlling the pruming strength in each dimension, and consider two objectives: (i) the accuracy difference between the full model and the pruned model laiff-cc (A) = E [11 ((x)= - [x())))+ and (ii) the respective cost ratio feost (A) = E ((A(X)) C((X))
Early Time Classification. We adapt the early time classification scheme proposed by Ringel et al. focus (2024) for prodicting the label of given input data stream quickly as possible. Specifically?, employing LLMs for the task of reading comprehension, where the goal is to analyze a long document (given as context) and select an answer to a provided question. Let x r'(X) denote a heuristic confidence measure of the prediction made based on the input X received until time & (e.g. the maximum predicted probability). We define the stopping-ting for input X as r(X) = {min, : (X) 2 X or t = fmax). In this setting, the hyperparameter À (21,,2,.... .2,..., A,,ax)) consists the thresholds for all possible stopping times t =
We have two objectives: (i) the accuracy difference between the full-time prediction and the early-time prediction Lditt-acoA)) E [(x) [x(x)=))+] and (ii) the normalized halt time Lime (A) = E (r()//tmxx)
7 Experiments
We describe the experimental setup and present our main results. Further experimental details, as well as additional results are provided in Appendixes D and E, respectively. In the experiments we demonstrate the efficiency of the proposed method compared to baselines in two main ways: (i) For a fixed budget, we show that GuideBO achieves the lowest values for the free objective function compared baselines; (ii) For fixed level of the objective function, we show that GuideBO requires the smallest budget to achieve that level. Additional ablation studies are conducted to highlight the robustness of GuideBO.
7.1 Baselines
We define several baselines. We emphasize that in the second testing stage, both GuideBO and the baselines follow the same testing procedure that guarantees risk control. The baselines differ only in their optimization mechanisms during the first stage; thus, they all be considered variants of Pareto Testing (Laufer- Goldshtein et al., 2023). We define two simple basclines and three multi-objective optimizers aimed at recovering the full Pareto front:
UNIFORM defines a uniform grid of configurations in the hyperparameter space. RANDOM a uniform random sampling for 1, and Latin Hypercube Sampling (LHS) (MeKay et al., 2000) for 1.
HVI uses the same acquisition function as in GuideBO, defined in Eq. (4). The key difference is that the reference point is defined in the standard way by the maximum possible loss values, rather than our focused reference point (12).
EHVI (Emmerich et al., 2006) similar to HVI but includes uncertainty in the hypervloume computation. Here too the reference point is defined by the maximum possible loss values.
PAREGO (Knowles, 2006; Cristescu & Knowles, 2015) uses random scalarization with Tchebycheff function to convert the multi-objective function into singlo-objective, then employs EI as the acquisiiion function. We use the SMAC3 implementation (Lindauer et al., 2022).
In addition, We provide results for the task of early time classification of structured time series data, as described in Appendix D.
11

---

Published in Transactions on Machine Learning Research (10/2024)
Table 2: Tasks Details
Task
n
(L...... (frwe)
(best Ei, worst (rve)
(worst Ei,,,., best (rrw))
N
No.
Fairness
2
(Err., DDP)
(0.154, 0.145)
(0.225, 0.01)
10
5
Robustness
(Avg. Error, Worst Err.)
(0.045, 0.62)
(0.089, 0.11)
30
20
Selective & Robust. 5
(Avg. Error, Mis-cover, Worst Err.)
(0.045, 0.0, 0.62)
(0.089, 0.0, 0.11)
30
20
VAE
2
(Recon. Err., KLD)
(0.001, 88)
(0.07, 0.001)
10
5
Pruming
3
(Ace. Difference, Rel. Cost)
(0.0, 1.0)
(0.8, 0.0)
50
30
Time Class. 10
(Acr. Difference, Halt. Time)
(0.0, 1.0)
(0.12, 0.1)
50
30
7.2
Datasets
Here we describe the datasets used for each task. Table 1 summarizes the number of samples for each validation/calibraat
dataset according to the different splits Fairness. We use the Adult (Dua et al., 2017) dataset, which consists of samples of individuals with 14 features as an input. The goal is to predict whether their annual income is above 50kS. Gender is considered as a sensitive attribute.
We use the following datasets:
Table 1: Datascts Details
Dataset
Train
Validation
Calibration
Test
Adult
32,559
3,618
4,522
4,523
CelebA
162,770
19,867
9,981
9,981
Robustness + Robust and selective classifica-
MNIST
50,000
10,000
5,000
5,000
tion. We use CelebA (Lin et al., 2019) and consider a bi- nary prediction task of whether a person has a blond hair. The spurious correlation is associated with the gender at- tribute, resulting in |g] groups: (blond, female), (blond, malc), (non-blond, female), (non-blond, malc).
AG News
120,000
2,500
2,500
2,600
Quality
1,537
1,536
1,536
VAE. We use the MNIST datasel. (LeCun, 1998), which consists of grayscale images of handwritten digits. Pruning. We use AG News (Zhang et al., 2015) dataset where the task is to predict the category (out of four options) of news articles based on their content.
Marly-Time Classification. We use the QuALITY dataset (Pang et al., 2022), which consists of triplets with a question, multiple choice answers, and long context, along with the corresponding correct choice.
The long context is partitioned into tmax = 10 segments.
7.3 Evaluation
We emphasize again the purpose each data split. The training data is used to learn the model parameters. The validation data used for selecting candidate hyperparameter configurations, using either GuideBO (Algorithm 1) or the baseline procedures. The same data is also used for ordering the chosen configurations before testing. The calibration data is used for the FST procedure over the ordered set of chosen configura- tions. The final selected X (14) determines the model sctup. Lastly, the performance of the selected model is assessed on the test. datasel.
Since the same testing procedure is applied across all methods, the chosen configuration is guaranteed to satisfy the specified constraints, as we verify empirically (see Fig. E.1). Therefore, our primary metrics for evaluating the efficiency of each method are: (i) its ability to minimize the free objective function within a given budget, and (ii) its capacity to reach certain levels of the free objective with the least budget.
We repeat the experiments with 5 random seeds over the optimization procedure. For each seed, further generate 20 random splits of calibration and test subsets. Accordingly, we obtain 5 x 20 100 random trials, and report the mean and standard deviation across all trials. For each task, we choose the values of a according to the objective values obtained for the initially generated configurations. Table 2 lists the range values for each objective. We select values that lie within the range defined by these extreme points, ensuring they are not too close to either boundary. This is because values that are too small may not be statistically achicvable, while excessively large values can be trivially satisfied, with tighter control not significantly improving the free objective. We set 8 0.1 and ? 0.01.
7.4 Results
Minimization of the free objective function for a given budget. We examine the fol- lowing scenarios: Fairness error is controlled and DDP is minimized; Robustness avg. er-
12

---

Published in Transactions on Machine Learning Research (10/2024)
Method Uniterm
Kethod
0.6
Method
0.150
Propased
Unitom
Unitarm
Random
EHVI
Worst Error
EHVI
0.4
EHvI
0.075
RareGo
0.3
PareGo
Worst
0.3
ParEGO
0.050
0.2
0.1
0.000
0.165
0.17
0.175
0.28
0.053
0.065
0.075
0.085
0.005
0.065
0.075
0.085
4:
4:
(a) Fairness
(b) Robustness
(c) Selective Robustness
1.0
Method
Method
GuideBO
Uniform
0.6
Unitorm
30
Random
EHVI
EHvI
HVI
0.6
ParteGSO
Reletive
0.4
ParEGO
Method
GuideBO
0.3
0.4
Uniform
Random
EHVI
0.1
HVI
PareGO
0.02
0.02
0.03
0.04
0.025
0.075
0.125
0.175
0.025
0.05
0.075
0.1
81
d:
(d) VAE
(e) Pruning
(f) Early Classification
Figure The values of the free objective functions across tasks and different limits. The objectives are evaluated over Prest for the configuration that was chosen by each method. GuideBO consistently surpasses the baselines in nearly all cases. In contrast, the performance of the baselines exhibits significant variability.
ror is controlled and worst error is minimized; Robustness and selective classification error and miscoverage are controlled while worst error minimized; VAE reconstruction error is con- trolled and KLD is minimized; Pruning error difference is controlled and relative cost is min- imized; Early time classification error difference is controlled and relative cost is minimized.
Results are presented in Fig. 4 showing the values of the free objective function, evaluated over test data, across all tasks and a levels. To summarize the results, we rank the methods in each scenario, and report the counts of all rankings, as well as the average rank in Fig. 5. We observe that GuideBO consistently outperforms all baselines in nearly all
0
10
20
GuideBO
22
0
0
1.1
HVI
0
7
8
8
1
0
3.1
Method
EHVI
1
6
5
8
1
3.4
cases. The multi-objective baselines outperform the simple baselines that distribute configurations across the entire space. Moreover, the baselines exhibit inconsistent. performance, delivering satis- factory results for certain tasks or specific values, but falling short in others. This inconsistency be attributed to the arbitrary distribution of the configurations for the basclines. As result, we sometimes randomly obtain configurations that are close to the testing limit (thus efficient), while at other times, the closest configuration relatively far (thus inefficient). In contrast, GuideBO achieves dense sampling of the relevant part of the Pareto front, leading to more precise and stable control across various conditions.
ParEGO
1
7
4
5
5
3.6
2
Random
0
5
2
4
9
4
4.2
Uniform
1
1
2
7
11
4.9
3
Avg. Rank
Rank
Figure 5: Rank count across settings and the average rank. GuideBO is ranked first in almost all cases, while the baselines have an inconsistent performance.
13

---

Published in Transactions on Machine Learning Research (10/2024)
Additional Results. We first show that the constraints satisfied in all cases by both GuideBO and the baselines in Fig. F.1. In addition, we show the objective values obtained by the different methods as a function of the budget (see Fig. E.2) and present the budget required to achieve specific objective levels (see Fig. E.3). The results show that GuideBO consistently outperforms the baselines. Furthermore, we explore the influence of varying the budget N in comparison to dense uniform grid (with 1000 points) Fig. E.4. We show that N = 100 is sufficient to match (and sometimes outperform) the performance of the dense grid, highlighting the computational advantage of the proposed method. Furthermore, we conducted five additional experiments for the early-time classification task using various structured time-series datasets with large hyperparameter spaces ranging from 8 to 12 dimensions, demonstrating again that GuideBO is preferable over the baselines (see Table D.1 and Fig. E.5). We also examine the influence of the parameter y in Fig. E.6, showing that the method is generally insensitive to Moreover, Fig. E.7 shows that using the proposed region is preferable over a single-sided upper bound at a, implying that it is important to exclude inefficient configurations. Finally, we present examples of GuideBO's outcomes Fig. E.8, highlighting its effectiveness in identifying relevant configurations within the defined region of interest, opposed to recovering the entire front.
Limitations and future work. While our proposed method establishes an efficient mechanism for selecting rist-controlling model configurations and improves upon previous work, it has some limitations. Multi- fidelity optimization is a popular method for hyperparameter optimization, where resources are allocated efficiently (Li et al., 2018; 2020). In this approach, additional resources (e.g., more epochs) are allocated to promising configurations that performed well with fewer resources, while configurations that showed poorer performance are discarded. Our current method cannot. be directly applied in this setting. Moreover, the calibrated selection procedure requires splitting the data between the validation set used for selecting the subset of promising configurations, and the calibration set used for their verification. Although this is commonly done in other conformal prediction and risk control methods (Angelopoulos et al., 2021; Bai et al., 2022; Ringel et al., 2024), in many practical settings there is only limited available data. Another issue is that there might be a distribution shift between the /otltattiooallaaaaioon data and test data, and thus the selected configuration might not be risk-controlling with respect to shifted test data distributions (Gibbs & Candès, 2024; Zollo et al., 2024). These challenges should be explored in future work.
8 Conclusion
We introduce versatile framework designed for reliable model selection. This framework is capable of meeting statistical risk limitations while simultaneously optimizing other conflicting metrics. We establish confined region within the objective space that is a promising target for statistical testing. Our proposed method, referred to as GuideBO, is employed to pinpoint configurations that are Parcto optimal and lic in the specified region. We statistically validate the set of candidate configurations using multiple hypothesis testing to achieve verified control guarantees. The broad applicability and effectiveness of our approach are demonstrated for tuning different types of hyperparameters across various tasks and objectives, including high-accuracy, fairness, robustness, generation and reconstruction quality and cost and time considerations.
Acknowledgments
We thank the anonymous reviewers for helpful discussions and feedback. B.L.G. was supported in part by Schmidt Sciences, LLC.
References
E Alpaydin and C Kaynak. Optical recognition of handwritten digits. uci machine learning repository, 1998.
Anastasios N Angelopoulos, Stephen Bates, Emmanuel J Candès, Michael 1 Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint orXiv:2110.0100 2021.
Anastasios N Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint ar Xiv:22000..00 02814, 2022.
14

---

Published in Transactions on Machine Learning Research (10/2024)
D Anguita, A Ghio, L Oneto, X Parra, JL Reyes-Ortiz, et al. A public domain dataset for human activity recognition using smartphones. In 21th Europenn Symposium on Artāficial Neural Networks, Compulational Intelligence and Machine Learning (ESANN), pp. 437 442. CLACO, 2013.
Peter Auer. Using confidence bounds for exploitatioon-exploratin trade-offs. Journal of Machine Learning Research, 3NNov):397-42 2002.
Johannes Bader and Eckart Zitzler. Hype: An algorithm for fast hypervolume- many-objective opti- mization. Evolutionary computation, 19(1):45-76, 2011.
Yu Bai, Song Mei, Huan Wang, Yingbo Zhou, and Caiming Xiong. Efficient and differentiable conformal prediction with general function classes. In International Conference on Learning Representations, 2022.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+.. The Annals of Statistics, 49(1):486-507, 2021.
Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free, risk-controlling prediction sets. Journal of the ACM (JACM), 68(6):1-34, 2021.
Syrine Belakaria, Aryan Deshwal, and Janardhan Rao Doppa. Max-value entropy search for multi-objective bayesian optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
Syrine Belakaria, Aryan Deshwal, Nitthilan Kannappan Jayakodi, and Janardhan Rao Doppa. Uncertainty- aware scarch framework for multi-objective bayesian optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06):10044 100522000421 2020.
Bornd Bischl, Martin Binder, Michel Lang, Tobias Piclok, Jakob Richter, Stefan Coors, Janck Thomas, Theresa Ullmann, Mare Becker, Anne- Boulesteix, et al. Hyperparameter optimization: Founda- tions, algorithms, best practices, and open challenges. Wiley Interdisciplinory Reviews: Data Mining and Knowledge Discovery, 13(2):e1484, 2023.
Juergen Branke. Meda and multiobjective evolutionary algorithms. Multiple criteria decision analysis: state of the art surveys, pp. 977-1008, 2016.
Jürgen Branke and Kalyanmoy Deb. Integrating user preferences into evolutionary multi-objective optimiza- tion. In Knowledge incorporation in evolutionary computation, pp. 461-477. Springer, 2005.
Jürgen Branke, Thomas KauBler, and Harmut Schmeck. Guidance in evolutionary multi-objective optimiza- tion. Advances in engineering software, 32(6):499 507, 2001.
Clément Chadebec, Louis Vincent, and Stephanic Allassonniere. Pythac: Unifying generative autoencoders in python a benchmarking use case. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and Curran A. Oh (eds.), Advances in Newral Information Processing Systems, volume 35, pp. Associates, Inc., 2022.
Weiyu Chen and James Kwok. Multi-objective deep learning with adaptive reference vectors. Advances in 2022.
Newral Information Processing Systems,
Yanping Chen, Eamonn Keogh, Bing Hu, Nurjahan Begum, Authony Bagnall, Abdullah Mueen, and Gustavo Batista. The uer time series classification archive. http://www.ce es. uer www.uurr..euuuee.... edu--eamon//time tiie_sereee_________e____ data/, 2015.
Ching- Yao Chuang and Youssef Mroueh. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
Cristina Cristescu and Joshua Knowles. Surrogate-based multiobjective optimization: Parego update and test. In Workshop on Compulational Intelligence (UKCT), volune 770, 2015.
Samuel Daulton, Maximilian Balandat, and Eytan Bakshy. Parallel bayesian optimization of multiple noisy objectives with expected hypervolume improvement. Advances in Neural Information Processing Systems, 34:2187-2200 2021.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Kalyanmoy Deb and Jayavelmurugan Sundar. Reference point based multi-objective optimization using evolutionary algorithms. In Proceedings of the 8th annual conference on Genelàc and ecolulionary compu- tation, pp. 635 642, 2006.
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182-197, 2002.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comples Rendus Mathematique, 350(5-6):313-31) 2012.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1810::0010008000 2018.
Dheeru Dua, Casey Graff, et al. Uci machine learning repository, 2017.
Michael Emmerich, Nicola Beume, and Boris Naujoks. An emo algorithm using the hypervolume measure as selection criterion. In International Conference on Evolutionary Culti-Criterion Optimization, pp. 62-76. Springer, 2005.
Michael TM Emmerich, Kyriakos C Giannakoglon, and Boris Naujoks. Single-and multiobjective evolu- tionary optimization assisted by gaussian random field metamodels. IEEE Transactions on Evolutionary Computation, 10(4):421-439, 2006.
Matthias Feurer, Katharina Eggensperger, Edward Bergman, Florian Pfisterer, Bernd Bischl, and Frank Hutter. Mind the gap: Measuring generalization performance across multiple objectives. In International Symposium on Intelligent. Dala Analysis, pp. 130-142. Springer, 2023.
Carlos M Fonseca and Peter J Fleming. Multiobjective optimization and multiple constraint handling with evolutionary algorithms. i. a unified formulation. IEEE Transactions on Systems, Man, and Cybernetics- Part A: Systems and Humans, 28(1):26-32 1998.
Peter I Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv:1807.0284 000108817,0, 2018
Johannes Fürnkranz and Eyke Hüllermeier. Preference learning and ranking by pairwise comparison. In Preference learning, pp. 65-82. Springer, 2010.
Jacob Gardner, Matt Kusner, Kilian Weinberger, John Cunningham, et al. Bayesian optimization with incquality constraints. In International Conference on Machine Learning, pp- 937-945. PMLR, 2014.
Yonatan Geifman and Ran El-Yaniv. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
Isaac Gibbs and Emmanull J Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 256162): -3, 2024.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-fre binary classification: predic- tion sets, confidence intervals and calibration. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Daniel Hernández-Lobato, Jose Bernandez-Lobato Amar Shah, and Ryan Adams. Predictive entropy search for multi-objective bayesian optimization. In International conference on machine learning, pp. 1492-1501. PMLR, 2016.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In International conference learning representations, 2016.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pp. 409-426, 1994.
Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavion journal of stalistics, pp. 65-70, 1979.
D Ienco and R Gactano. Tiselac: time series land cover classification challenge. https://www
timeserieeclssiifcatiioo http:/iiiaatttocooneennrrppppppe denn/eeccripionn php7DataasttTTislla, http:///aaaaaapppooooopoppptaaat 2007.
Hisao Ishibuchi, Ryo Imada, Yu Setoguchi, and Yusuke Nojima. How to specify a reference point in hyper- volume calculation for fair performance comparison. Evolutionary computation, 26(3):411-440, 2018.
Pavel Ixmailov, Polina Kirichenko, Nate Gruver, and Andrew G Wilson. On feature learning in the presence spurious correlations. Advances in Newral Information Processing Systems, 35:38516 38532, 2022.
Florian Karl, Tobias Pielok, Julia Moosbauer, Florian Pfisterer, Stefan Coors, Martin Binder, Lennart Schnei- der, Janek Thomas, Jakob Richter, Michel Lang, et al. Multi-objective hyperparameter optimization an overview. arXiv preprint arXiv:2206.00 07498, 2022.
Diederik P Kingma and Max Welling. Auto-cncoding variational bayes arXiv preprint arXiv:1312.6114 2013.
Joshua Knowles. Parego: A hybrid algorithm with on-line landscape approximation for expensive multiob- jective optimization problems. IEEE Transaclions on Evolutionary Compulation, 10(1):50 66, 2006.
Mina Konakovic Lukovic, Yunsheng Tian, and Wojeiech Matusik. Diversity-guided multi-objective bayesian optimization with batch evaluations. Advances in Newral Information Processing Systems, 11-17708-17722 2020.
HJ Kushner, A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise. Journal of Basic Enginecring, 86(1):97-106, 1964.
Stefanos Taskaridis, Alexandros Kouris, and Nicholas Lane. Adaptive inference through early-exit net- works: Design, challenges and directions. In Proceedings of the 5th International Workshop on Embedded and Mobile Deep Learning, pp. 1-6, 2021.
Bracha Goldstnn, Adam Fisch, Regina Barzilay, and Tommi Jaakkola. Efficiently controlling mul- tiple risks with pareto testing. ICLR, 2023.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun wwm/exxb/mmist/// 1998.
Jing Lei, James Robins, and Larry Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278 287, 2013.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statislical Associalion, 113(523):1094 1111, 2018.
Benjamin Letham, Brian Karrer, Guilherme Ottoni, and Eytan Bakshy. Constrained bayesian optimization with noisy experiments. Bayesian Analysis, 14(2), 2019.
Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Jonathan Ben-Taur, Moritz Hardt, Ben- jamin Recht, and Ameet Talwalkar. A system for massively parallel hyperparameter tuning. Proceedings of Machine Learning and Systems, 2:230 246, 2020.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18 (185):1-522 52, 2018.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Fu Zhang, and Sam Kwong. Pareto multi-task learning. Advances in neural information processing systems, 32, 2019.
17

---

Published in Transactions on Machine Learning Research (10/2024)
Xi Lin, Zhiyuan Yang, Qingfu Zhang, and Sam Kwong. Controllable pareto multi-task learning. anXiv preprint or Xrv::200000000 0.3663, 2020.
Marius Lindauer, Katharina Eggensperger, Matthias Feurer, André Biedenkapp, Difan Deng, Carolin Ben- jamins, Tim Ruhkopf, René Sass, and Frank Hutter. Smac3: versatile bayesian optimization package for hyperparameter optimization. J. Mach. Learn. Res., 23:54 1, 2022.
Michael Lohaus, Michael Perrot, and Ulrke Von Luxburg. Too relaxed be fair. In International Conference on Machine Learning, pp.
PMLR, 2020.
Zhichao Lu, lan Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf. Nsga-net: neural architecture scarch using multi-objective genctic algorithm. In Proceedings of the genelic and ecolutionary compulation conference, pp. 419 427, 2019.
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In International Conference on Machine Learning, pp. 6597-6607. PMLR, 2020.
Natalia Martinez, Martin Bertran, and Guillermo Sapiro. Minimax pareto fairness: A multi objective perspective. In International conference machine learning, pp. 6755-6764. PMLR, 2020.
Michael D McKay, Richard J Beckman, and William J Conover. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 42(1):55 61, 2000.
Gaurav Menghani. Efficient deep learning: A survey on making deep learning models smallor, faster, and better. ACM Compuling Surveys, 55(12):1-33 37, 2023.
Giovanni Misitano, Bekir Afsar, Giomara Lárraga, and Kaisa Miettinen. Towards explainable interactive multiobjective optimization: R-ximo. Autonomous Agents and Multi-Agent Systems, 36(2):43, 2022.
Jonas Močkus. On bayesian methods for seeking the extremum. In Optimization Techniques IFIP Technical Conference: Novosibirsk, July 1-7, 1974, pp. 400-404. Springer, 1975.
Aviv Navon, Aviv Shamsian, Gal Chechik, and Ethan Fetaya. Learning the pareto front with hypernetworks. arXiv preprint 0rX1v:2010.04104, 2020.
Kirtan Padh, Diego Antognini, Emma Tejal-Glaude, Boi Faltings, and Claudiu Musat. Addressing fairness in classification with mones-agiostic multi-objective algorithm. In Uncertainty in Artificial Intelligence, pp. 600 609. PMLR, 2021.
Richard Yuanzhe Pang, Alicia Parrish, Nitish Joshi, Nikita Nangia, Jason Phang, Angelica Chen, Vishakh Padmakumar, Johnny Ma, Jana Thompson, He He, et al. Quality: Question answering with long input texts, yes! In 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 5336-534 2022.
Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi-objective bayesian optimization using random scalarizations, In Uncertainty in Artificial Intelligence, pp. 766 -76. PMLR, 2020.
Dana Pessach and Erez Shmneli. A review on fairness in machine learning. ACM Computing Surveys (CSUR), 55(3):1-44, 2022.
Florian Pfisterer, Stefan Coors, Janek Thomas, and Bernd Bischl. Multi-objective automatic machine learn- ing with autoxgboostme. arXio preprint arxiv: 1908. 10796, 2019.
Wolfgang Ponweiser, Tobias Wagner, Dirk Biermann, and Markus Vineze. Multiobjective optimization on a limited budget of evaluations using model-assistae assisted-metttt selection. In International conference on parallel problem solving from nature, pp. 7784-794 Springer, 2008
18

---

Published in Transactions on Machine Learning Research (10/2024)
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference on machine learning, pp- 1278-1 1286. PMLR, 2014.
Liran Ringel, Regev Cohen, Daniel Freedman, Michael Flad, and Yaniv Romano. Early time classification with accumulated accuracy gap control. arXiv preprint arXiv:2402.0083 00857, 2024.
Michael Ruchte and Josif Grabocka. Scalable pareto front approximation for deep multi-objective learning. In 2021 IEEE international conference on data mining (ICDM), pp. 1306-13111 IEEE, 2021.
Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang, Distributionally robust neural networks for group shifts: shifts: On the importance of regularization for worst-case generalization. arXiv preprinl arXiv:1911.08991 2019.
David Salinas, Jacek Golebiowski, Aaron Klein, Matthias Seeger, and Cedric Archambeau. Optimizing hyperparamcters with conformal quantile regression. arXiv preprint rxXi:2305.03623 2023.
Robin Schmucker, Michele Donini, Muhammad Bilal Zafar, David Salinas, and Cédric Archambeau. Multi- objective asynchronous successive halving. arXiv preprint arXiv:2166. 12639, 2021.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objoctive optimization. Aduances in neural information processing systems, 31, 2018.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148-175, 2015.
S Stanton, W Maddox, and AG Wilson. Bayesian optimization with conformal prediction sets. In Artificial Intelligence and Statistics, 2023.
Chang Wei Tan, Geoffrey Webb, and François Petitjean. Indexing and classifying gigabytes of time series under time warping. In Proceedings of the 2017 STAM international conference. on data mining, pp. 282 290. SIAM, 2017.
Vladimir Vovk. On-line confidence machines are well-calibrated. In The 48rd Annual IEEF Symposium on Foundations of Computer Science., 2002.
Vladimir Vovk, Ivan Petej, and Valentina Fedorova. Large-scale probabilistic predictors with and without guarantees of validity. In Advances in Neural Information Processing Systems (NewrIPS), 2013.
Vladimir Vork, Jieli Shen, Valery Manokhin, and Min-ge Xie. Nouparametric predictive distributions basod conformal prediction. In Proceedings of the Sizth Workshop on Conformal and Probahilistic Prediction and Applications, 2017.
Tobias Wagner and Heike Trautmann. Integration of preferences in hypervolume-based multiobjective evolu- tionary algorithms by means of desirability functions. IFEE Trunsactions on Evolutionary Computation, 14(5):688 701, 2010.
Bin Wang, Yanan Sun, Bing Xuc, and Mengjie Zhang. Evolving deep neural networks by multi-objective particle swarm optimization for image classification. In Proceedings of the genetic and evolutionory com- putation conference, pp. 490-498, 2019.
Handing Wang, Markus Olhofer, and Yaochu Jin. A mini-review on preference modeling and articulation in multi-objective optimization: current status and challenges. Compler & Intelligent Systems, 3:233-245, 2017.
Xilu Wang, Yaochu Jin, Sebastian Schmitt, and Markus Olhofer. Recent advances in bayesian optimization. arXiv preprint arXio:2206.088: 03301, 2022.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. MIT press Cambridge, MA, 2006.
19

---

Published in Transactions on Machine Learning Research (10/2024)
Maciej Wolezyk, Bartosz Wójeik, Klaudia Balazy, Igor T Podolak, Jacek Tabor, Marek Smieja, and Tomasz Trzcinski. Zero time waste: Recycling predictions in early exit neural networks. Advances in Neural Information Processing Systems, 34:2516 2528, 2021.
Yongkai Wu, Lu Zhang, and Xintao Wu. On convexity and bounds of fairness- classification. In The World Wide Web Conference, pp. 3356-3362, 2019.
Bin Xin, Lu Chen, Jie Chen, Hisao Ishibuchi, Kaoru Hirota, and Bo Liu. Interactive multiobjective opti- mization: A review of the state-of-the-art. IEEE Access, 1411256411278 2018.
Yuzhe Yang, Haoran Zhang, Dina Katabi, and Marzych Ghassemi. Change is hard: A closer look subpopulation shift. arXiv preprinl arXie:2302. 1 12254, 2023.
Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6):712-71,, 2007.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
Yunchuan Zhang, Sangwoo Park, and Osvaldo Simeone. Bayesian optimization with formal safety guarantees via online conformal prediction. ar preprint 17812,36.17815, 2023.
Eckart Zitzler and Lothar Thiele. Multiobjective optimization using evolutionary algorithms a comparative case study. In International conference on parallel problem solving from nature, pp. 292-301. Springer, 1998.
Thomas P Zollo, Todd Morrill, Zhun Deng, Jake Snell, Toniann Pitassi, and Richard Zemel. Prompt risk control: A rigorous framework for responsible deployment of large language models. In The Twelfth Internaiional Conference on Learning Representations, 2024.
A Additional related work
Gradient-Based MOO. When dealing with differentiable objective functions, gradient-based MOO algorithms can be utilized. The cornerstone of these methods is Multiple-Gradient Descent (MGD) (Sener & Koltun, 2018; Désidéri, 2012), which ensures that all objectives convergence at a Pareto optimal point. Several extensions were proposed to enable convergence to a specific point on the front defined by a preference vector (Lin et al., 2019; Mahapatra & Rajan, 2020), or learning the entire Pareto front, using a preference-conditionel model (Navon et al., 2020; Lin et al., 2020; Chen & Kwok, 2022; Ruchte & Grabocka, 2021). However, this line of rescarch focuses on differentiable objectives, optimizing the loss space used during training (e.g. cross entropy loss), which is lypically different from the ultimate non-differentiable metrics used for evaluation (e.g. error rates). Furthermore, it focuses on recov- cring a single multiple (possibly infinitely many) Parcto optimal points, without addressing the actual selection of model configuration under specific constraints, which is the problem tackle in this paper.
decreased simultancously, leading to
Incorporating user preferences in MOO. Another area of research has explored integrating decision maker preferences into multi-objective optimization (Branke, 2016; Wang et al., 2017; Xin et al., 2018). These methods are typically classified based on the stage in which they are applied in the optimization process: before, during, or after optimization (Branke Deb, 2005). Preferences can be specified in various ways, such as using reference points representing an "ideal" solution (Deb & Sundar, 2006), imposing con- straints (Fonseca & Fleming, 1998), setting maximal or minimal trade-offs (Branke et al., 2001), and using desirability functions that non-linearly scale the objectives to [0, 1] (Wagner & Trautmann, 2010). Addition- ally, preferences can be learned by asking the decision maker to rank solutions or seleet the most preferred solution from a set (Fürnkranz & Hüllermeier, 2010). Another interactive preference learning approach involves incorporating explanations that help the decision maker in understanding the trade-offs between objectives (Misitano al., 2022). In this paper, we focus on preferences provided by the user as hard limits on certain objectives, which require validation through statistical testing. Our BO procedure aims to extract set of promising configurations that are designed to achieve tight, control guarantees.
20

---

Published in Transactions on Machine Learning Research (10/2024)
B Mathematical Details
B.1 Derivation of the Region of Interest
Suppose the loss is bounded above by 1, then Hoeflding's inequality (Hoeffding, 1994) is given by:
P (((A) E(() -t) 2mt?
(18)
and
(((A) - E(A) 2 S 2mi?
(19)
for t> O. Taking u = e -mmm?? we have
v
log(1/u)
hence:
2m
log (1/u)
P ((A) - ((A) - -V
((A)-
S U,
(20)
2m
and
log (1/u) 2m
P ((2) ((A)-((A) 2
S
(21)
This implies an upper confidence bound
log (1/u) 2m
())(=)((A)) - +
(22)
and a lower confidence bound
log (L/u)
( = ((A))
(23)
2m
In addition, we can use Hoeffding's inequality to derive a valid p-value under the null hypothesis H ((X)
a. By (20), we get:
P ((2) (12) (11))-55
log (1/u)
S P (P(())-(()) ((A)
log (1/u)
-v
<
(24)
2m
2m
Rearranging the incquality inside the probability for {(A) < a, obtain:
log (1/u)
((A) a
2m
log (1/u)
a a-((2) Z
2m
(25)
2m(a {(2))² 2 2 log (1/ (1/u)
2m(a {()))² 2 < log (u)
2m(a-1(2)) < u.
Thus for {(2) < a, we obtain:
P 2m(a--))())) < <
(26)
where we inserted (+)+ max(-; 0) since we assume ε(A) < a. Note that this statement also holds for ((A) 2 a, as have P < u) u, which valid Vu [0, 1). This implies that H -2m(a-((A)) is
21

---

Published in Transactions on Machine Learning Research (10/2024)
super-uniform, hence is valid p-value required. Comparing PX to 6, yields the maximum empirical loss (()), evaluated over a calibration set of size m, which can pass the test with significance level d:
log (1/8)
max a
(27)
2m
This can be equivalently obtained from the upper bound defined in Eq. (22).
The region of interest in Eqs. (7) and (8) is obtained based on Eqs. (20) and (21) (where + y and k)): 2op (A) E R(a, k. m, 6, 7) & (A) = a max
(A)) - log (1/7)
log (1/7)
2001(1 (2) +
2k
2k
(28)
log (1/r) 2o00 2 ((()) V
log (1/r) 2k:
1 P
popt (A) S (1()) V
P
2 1 - 27.
2k
Eqs. (20): ST
Eqa. (21): ST
Since the probability defined on the left-hand side in non-negative and bounded by 1, we have 0 < S 0.5. In practice, we use much smaller values of y < 0.5 to ensure a sulficiently wide region that encompasses all potential configurations around a maxx
A tighter alternative to Hoeffding p-value was proposed in (Bates et al., 2021) based Hooffding and Bentkus inequalities. The Hoeffding- Bentkus p-value is given by:
PX min (exp(-no (E(A) A a, a)), ePP (Binom(m, a) S [m(())1))
(29)
where hi (a, b) a (g) + (1 - a) log( ( A max(a, b) and e denotes the natural exponent. For the Binomial tail probability instead (without the factor):
binary risk functions (e.g. error)
Bin PX
P(Binom(m,.) a) S [mm(()]).
(30)
Note that for a given we can numerically extract from Eqs. (29) or (30) the upper and lower bounds corresponding to 1 22 confidence interval, and use it to define the region of interest as in Eq. (8).
When the loss is unbounded, can alternatively use p-value defined by the central limit theorem, which is asymplotically valid. Assuming that the loss has finite mean and variance, we define:
((A)
CLT 1 1- px
(31)
a(A)/
where o(A) - b ( - {()))2 denotes the empirical standard deviation, and + is the normal cumulative distribution function. We obtain that limsupm--s P CL I u) u.
B.2 valid p-value for multiple constraints
We prove that taking the maximum p-value across constraints is valid v-value for the combined hypothesis. Lemma B.1. Let pxd be p-value for Hx, (A) > ac, for each i E c}. Define == maxisise PA. Then, for all X such that HA: : Ei where (((A) > ag holds, we have:
P P S < Su,
(32)
where u E 1].
Proof. Let I C .l. be the set all true null hypotheses (unsatisfied constraints) at A. We have:
sw)=p =P P P(pA uu) SP max px, su) -P (n PaJ Su
max P (px.) S u).
(33)
jEG
GET
Since for each j J, (pxs S Su) S.u u, we have maxjes IP (px. S u) u, implying that P Ppx S u) u. 7
22

---

Published in Transactions on Machine Learning Research (10/2024)
B.3 Proof of Proposition 5.1
The proof is based on (Angelopoulos et al., 2021; Lanfhr-Goldshteinn et al., 2023), which we repeat here for completeness.
Proof. Recall that val and Deal are two disjoint, i.dd. datasets. Therefore, Deal is i.idd w.r.t the returned configuration set optimized Algorithm over Daal-
We now prove that the testing procedure returns set of valid configurations with FWER bounded by 6. Let Hx be the first true null hypothesis in the sequence. Given that px is super uniform p-value under Hx, the probability of making a false discovery at X is bounded by 5. This means that the event that Hx is rejected (false discovery) occurs with probability lower than 8. However, if Hx fails to be rejected (no false discovery), then all other Hx that follow in the sequence also fail to be rejected (regardless of if HA is true or not). Therefore, the probability of making any false discovery bounded by 6, which satisfies the FWER control requirement.
B.4 Hypervolume
An illustration of the hypervolume defined in Eq. (3) is given in Fig. B.1 for the 2-dimensional case. It can seen that the hypervolume equivalent to the volume the union of the boxes created by the Pareto optimal points and the reference point.
C
Figure B.1: An illustration of the hypervolume in the 2-dimensional case. The reference point is marked in red and three Pareto optimal points are marked in blue.
B.5 Region of Interest
An illustration of the region of interest defined in Eq. (9) given in Fig. B.2 for the 3-dimensional case (two constraints and single free objective function). The volume is defined by the intersection of the regions defined by each constrained dimension.
23

---

Published in Transactions on Machine Learning Research (10/2024)
3
2
Region of Interest
high
slow
2
slow
hhigh
e
Figure B.2: An illustration of the region of interest in the 3-dimensional case.
C
Algorithms
Our overall proposed method is summarized in Algorithm C.1.
Algorithm C.1 Configuration Selection
Definitions: f is configurable model set by an hyperparameter A. Deal (X,, Y.)_,, and Deat (X,, Yi) are two disjoint subsets of validation and calibration data, respectively. (c) are constrained objective functions, and free is free objective. (a.)....a.) are user-specifted bounds for the constrained objectives. A is the configuration space. the tolerance. N the optimization budget, and N, is the size the intial pool configurations. PARETOOPTIMALSET)) returns Pareto optimal points.
function SELECT(Peal: Deat A, (ee,,..,,.],,,,..
2: Compute flow ghigh for i (l.....e} based on (8) and (9)
Determine the region of interest.
3: Co. Lo Randomly sample initial pool of configurations of size No CBO + & Co. Lo, {elow to..,
Generate an initial pool.
[ flow), {e hhigh ,....,,, hhgh N)
BO via Algorithm 1.
+ PAAEETOOPPTIAASST(CO99))
Filter Pareto optimal points according Eq. (2).
Compute px over Deat for all CP
Compute approximated p-values.
7:
Order configurations uccording to increasing paal
b Order configurations.
Compute 1faa over Deat for À
P. Compute p-values.
9:
Apply FST: Cvalid = (X() : J}. J min, 15 pp 2 5}
b Apply FST.
10: X arg min xccool (X)
select the best-performing configuration.
11:
return X
D Implementation and dataset details
We provide here further details on the datasets, application specifications, model architectures, training procedures, and examined scenarios.
Initialization. For GuideBO, HVI and EHVI we randomly sample an initial set size No, and perform N No iterations BO. We use a uniform grid for n and LHS for n n> 1. The values of N and N, for each task are provided in Table 2. For PAREGO we use the default initialization defined by the SMAC3 implementation.
Fairness. For computing DDP(f), the indicator f()))=0 o with (Padh et al., 2021). In addition, we define a linear interpolation in the input space: It Ty (1 1) I- for i 10 where #1 and x-1 represent. samples with attributes 1 and -1,
Eq. (15) relaxed using tanh(c- max(0, f f(x))
24

---

Published in Transactions on Machine Learning Research (10/2024)
respectively. The mixup regularization is defined by:
MixUP(f) = E. [Ex
x1)lll.
(34)
regularizing the expected inner product between the Jacobian on mixup samples and the difference _-1 - #1 (Chuang & Mrouch, 2020). Our model is a 3-layer feed-forward neural network with hidden dimensions [60, 25). We train all models using Adam optimizer with learning rate le - for 50 epochs and batch size 256.
Robustness. We use ResNet-50 model pretrained on ImageNet. Following (Izmailov et al., 2022), we train the models for 50 epochs with SGD with a constant learning rate of le - 3, momentum decay of 0.9, batch size 32 and weight decay of le - 4. We use random crops and horizontal flips as data augmentation. We use half of the CelebA validation data to train the last layer, and the other half for BO.
VAE. We use the implementation provided by (Chadebec et al., 2022) of ResNet-based encoder and decoder, trained using AdamW optimizer with 31 = 0.91, B2 0.99, and weight decay 0.05. We set the learning to le - 4 and the batch size to 64. The training process consisted of 10 epochs. We use binary-cross entropy reconstruction loss for training the model, and the mean squared error normalized by the total number of pixels (728) as the reconstruction objective function for hyperparameter tuning.
Pruming. We use a BERT-base model (Devlin et al., 2018) with 12 layers and 12 heads per layer. We follow the recipe in Glaufor-Goldshtiin et al., 2023) and attach a prediction head and a token importance predictor per layer. The core model is first finetuned on the lask. We compute the attention head importance scores based on 5K held-out samples out of the training data. We freeze the backbone model and train the carly-cxit classifiers and the token importance predictors the training data (115K samples).
Each prediction head is 2-layer ford-forward neural network with 32 dimensional hidden states, and ReLU activation. The input is the hidden representation of the [CLS] token concatenated with the hidden repre- sentation of all provious layers, following ( (Wolezyk et al., 2021).
Similarly, each token importance predictor is a 2-layer ferd-forward neural network with 32 dimensional hidden states, and ReLU activation. The input is the hidden representation of each token in the current layer and all previous layers (Wolezyk et al., 2021).
Early-Time Classification. We adapt the setup described in (Ringel et al., 2024), and use the processed model outcomes that appear in their implementation'. The context of cach question is divided into sentences, which are grouped into bmax = 10 sets. The input sequence until time I is provided as a prompt that includes the context sentences up to timestep t, along with the question and its four options, labeled 'A', 'B', 'C', and 'D'. The prompt concludes with "The answer is: in)'... The prompt processod by the Vi3 model.
We provide additional results for structured time series data, following (Ringel et al., 2024). The details of all datasets are summarized in Table D.1. Each dataset is partitioned into four distinct parts: 80% for training and the remaining 20% are equally divided to validation, calibration and test subsets. For each dataset we define an exist point every fixed number of timesteps (hop-size) and obtain a hyperparameter dimension n ranging from 8 to 12. A standard LSTM is used for feature extraction with one recurrent layer with a hidden size of 32, except for each with a hidden size of 256. The output of the last recurrent layer followed by two fully connected classification heads, one for classifying the label and the other for estimating the classification confidence. The loss consists of two terms: cross-entropy loss for the label, and binary cross entropy loss (weighted by 0.2) for whether the classifier is correct or not. The models are trained with Adam optimizer, with a learning rate of 0.001, and a batch size of 64.
where the model consists of recurrent layers,
E Additional Results
In this section, we describe additional experiments and results.
25

---

Published in Transactions on Machine Learning Research (10/2024)
Table D.1: Summary structured time-series datasets.
Dataset
# Fealures
# Classes
# Samples
# Timesteps
Hop Size
Tiselac
10
9
99687
23
2
12
ElectricDevices
7
16637
96
8
12
PenDigits
10
10992
8
8
Crop
24
24000
46
4
12
VallxingSttcinngttading
6
10299
206
20
11
0.175
0.125
0.05
0.05
Method
Foot
Method
Method
GuideBO
GuideBO
0.04
GuideBO
0.075
Uniform
0.09
Uniform
0.03
Unifurm m
0.050
Randam
Random
Random
0.02
0.02
RIVI
0.01
Fvi
0.01
HVI
0.000
0.00
0.00
81
(a) Fairness
(b) Robustness
(c) Selective Robustness
Method
0.175
Method
0.10
Method
GuideBO
GuideBO
0.035
0.030
Unitorm
EHVI
Accuracy Difference
0.125
Unitorm
DYVI
Random
0.08
Unitorm
Rardom
0.025
0.100
HVI
0.020
ParEGo
ParFGG
Accuracy
0.04
ParFOO
0,015
0.050
0.02
0.010
0.025
0.005
0.00
0.000
0.01
0.02
0.03
0.04
0.025
0.075
0.125
0.175
0.025
0.05
0.075
0.1
(d) VAE
(e) Pruning
(f) Early Classification
Figure E.1: The values of the constrained objective functions across tasks and difforent limits (marked by dashed red lines). The objectives are evaluated over Dusst for the configuration that was chosen by each method. All method satisfy the limits due to the testing procedure.
Satisfying Constraints and Tighter Control. We show the values of the constrained objective functions in Fig. E.1, where the red dashed lines depict the limit. We see that the constraints are satisfied by all methods as expected, since in any case the configurations are validated through the testing procedure. Notably, GuideBO obtains tighter control compared to baselines in nearly all cases. This consistent with our carlier finding that GuideBO better minimizes the free objective function.
Varying Optimization Budget. In this experiment fixed the constraint (a limit) for each task and varied the optimization budget (number of crratiionsffuntiionn evaluations). We show the improvement in the free objective function as function of the optimization budget across tasks on Fig. E.2. It can be seen that GuideBO delivers consistently strong performance in all scenarios, while the other baselines have mixed others. In addition, for each task we define three
results, excelling in some cases and underperforming levels of the free objective: between 90% of the maximum value and 110% of the minimum value obtained by the different baselines, and order these levels from high to low value. We compare the budget that is required for each baseline to reach certain level in all tasks and for all defined levels. Results shown in
26

---

Published in Transactions on Machine Learning Research (10/2024)
0.200
Method
0.50
Method
0.175
GuideBO
GuideBO
Uniform
C.45
Uniform
kandom
Random
0.125
EHVI
Worst Error
0.40
EHVI
HVI
HVI
0.100
ParEGO
ParEGO
0.075
C.35
0.050
0,025
0.000
0.25
10
20
30
25
30
35
50
Budget
Budget
(a) Fairness (a 0.17)
(b) Robustness (a 0.055)
0.6
Method
Method
GuideBO
GuideBO
0.5
Uniform
Uniform
25
Random
Randem
Worst Error
20
ParEGO
0.2
10
0.1
Budget
Budget
(c) Selective Robustness (o1 0.065, 02 = 0.05)
(d) VAE (a 0.02)
Method
1.00
Method
0.7
GuideBO
GuideBO
0.6
Uniform
Uniform
Relative Cost
RAndom
0.90
EHVI
Halt Time
0.85
EHVI
HVI
HVI
0.4
ParEGO
0.80
ParEGO
0.3
0.75
0.2
0.70
0.1
0.65
40
50
60
80
90
100
30
35
50
Budget
Budget
(e) Pruning (a = 0.025)
(f) Early Classification (a 0.05)
Figure E.2: The value of the free objective as function of the budget across different tasks. In each case the limit is fixed. GuideBO consistently performs well across all cases, whereas the other baselines show inconsistent performance, achieving better results in some instances and worse in others.
Fig. E.3. If method cannot reach certain level within the total maximum budget, bar is displayed for that method at that level. We observe that in almost all cases (15 out of 18 scenarios), GuideBo requires the least budget compared to the baselines, and in many instances, it can reach levels that are unattainable by the other baselines. These results indicate that GuideBo requires fewer iterations to achieve the same or better results compared to the baselines.
Comparing dense grid. We examine the effect of varying the optimization budget N. We show results for the pruning task with N E (20,50, 100). In addition, we compare to dense grid with uniform sampling
27

---

Published in Transactions on Machine Learning Research (10/2024)
Method
Mechod GuideB unitomm
GuiceOO Jritom
BНV)
Random BHVI
40
Random
MV
EHM
Nin Butgee
ParcCo
Min Budges
Budget
20
20
10
0.12
Levels
0.00
6.64
0.36
Lovels
0:35
0.34
(c)
Selective Robustness (ar
(a) Fairness (a 0.17)
(b) Robustness (a 0.055)
0.065, 02 0.05)
16
Method
Method
Nethod GuiteSO
cuid:60
14
Unitarm
Unroomm
Rancom
Random
BHM
EHVI
30
ParfGG
Min Budget
20
10
17.96
13.64
5.32
0.39
0.29
0.18
0.85
0.79
0.74
Levels
Levels
Lovels
(d) VAE (a = 0.02)
(e) Pruning (a: 0.025)
(f) Early Classification (a 0.05)
Figure E.3: The budget that is required to achieve several different levels of the free objective function across different tasks. In nearly all cases (15 out of 18 scenarios), we find that GuideBO requires the smallest budget compared to the baselines. Moreover, often achieves levels that the other baselines cannol reach.
Method
GuideBO
0.20
GuideBO N 50
GuideBO N 100
Relative Cost
Uniform N 1000
0.10
0.05
0.00
0.025
0.075
0.125
0.175
Q1
Figure E.4: Results of the proposed method AG News (pruning task) for different number of evaluations, and with grid of uniform thresholds. Accuracy reduction is controlled and cost is minimized.
of all 3 hyperparmeters with a total N 1000 configurations. We see on Fig. E.4 that the relative cost gradually improves with the increase in N. reaches (and some cases outperform) the dense grid bascline with N 100 (that is 10% decrease in budget). This indicates that using our proposed method we can significantly decrease the required budget without scarifying performance.
28

---

Published in Transactions on Machine Learning Research (10/2024)
Method
Methoo
GuideBo
GuideB
0.8
GuideBo
Unitorm
0.0
Unstoem
Unitoem
Random
Random
Random
EHM
EHM]
EHV]
HVI
HVV
MVT
Falt Time
ParCGo
ParcGo
1-ait Time
PartGO
0.4
0.2
0.0
0.0
0.0
0.025
0.1
0.25
(a) Quality
(b) Crop
(c) PenDisiss
06
Unioom
0.5
Unilcam
0.30
Rendom
Random
0.0
Ellvi
HV
EHS
HiV
0.00
Halt Iime
Foreco
Holt Timee
Parebo
Hott Tima
c.00
0:04
Guideso
Random
01
6:02
HV
PwItGD
0.0
0.0
0:00
0.75
(d) ElectricDevices
(e) Tiselac
(f) WalkingSittingttaniing
Figure E.5: The values of the free objective functions across datasets and different limits for the task of early time classification. GuideBO is ranked first in 20 out of 24 cases.
Additional experiments for early-time classification task with different datasets. We conducted additional experiments for the task of early time classification with different datasets. Following (Ringel al., 2024), we show results on five additional structured time series datasets that are publicly available via the acon toolkit": Tiselac (Ienco & Gaetano, 2007); ElectricDevices (Chen et al., 2015), PenDigits (Alpaydin & Kaynak, 1998), Crop (Tan et al., 2017), and Valkingg model serves as the base sequential classifier for all datasets. Results of all experiments on early time classification (including Quality datasct) are presented on Fig. E.5. The average rank for cach method across datasets and a levels is: GuideBO: 1.2, HVI: 2.8, Random: 3.2, EHVI: 3.4, ParEGO: 4.1, Uniform: 5.2. We conclude that, similar to our previous results, GuideBO outperforms the basclines in nearly all cases, ranking first in 20 out of 24 scenarios.
(A (Anguita et al., 2013). An LSTM
Influence of 7 We examine the influence of 7. which determines the boundaries of the region of interest. Figure E.6 shows the scores obtained for different values of 7. We observe that in most cases there is no noticeable difference in the performance with respect to 7. However, it appears that moderate values, neither too large nor too small, are preferable.
Ablation study - onc-sided upper bound. We compare the proposed method to the case that the BO search is constrained by one-sided bound at the upper limit defined by a. This means that the reference point is set to r; = 0; for i e 1......,, C, while re+1 is set according to the maximum value of Gree, as in the standard full Pareto front approach. Figure E.7 shows the values of the free objective across tasks. We see that in most cases performing the search in the defined region of interest is preferable to a single-sided bound. This shows the benefit, of removing low risk, inefficient configurations from the search space (the green section in Fig. 2).
Demonstration of BO Selection. We show the outcomes of the BO procedure across several tasks in Fig. E.S. We compare the proposed method to HVI that recovers the entire Pareto front. The reference point defined in (12) is marked by a green square, and the boundaries of the region of interest are depicted
http::://wwww.eenttolllll /sttabll/
29

---

Published in Transactions on Machine Learning Research (10/2024)
0.10
0.0001
0.35
0.0001
0.0001
6,001
0.30
0.1
Worst Error
0.1
0.1
0.06
0.25
0.20
0.20
0.04
0.15
0.15
0.05
0.05
0.00
0.00
0.165
0.17
0.175
0.18
0.055
0.065
0.075
0.085
0.005
0.065
0.075
0.085
81
(a) Fairness
(b) Robustness
(c) Selective Robustness
20.0
Y
0.200
V
17.5
0.0001
0.175
0.0003
0.000:
0.001
0.001
0.001
0.01
0.01
Delativv Cost
0.125
10.0
0.100
7.5
0.0/5
3.0
0.2
2.5
0.025
0.000
0.0
0.02
1.03
0.04
0.05
0:
(d) VAE
(e) Pruning
(f) Early Classification
Figure E.6: Influence of 7. Showing the scores of the free objective for different values of 7, which controls the width of the region of interest, defined in Eq. (8).
by dashed lines. The blue points correspond the configurations in the initial pool Co, while the red points correspond the configurations selected by the BO procedure. We see that the specified region is significantly smaller compared to the entire front. Moreover, we observe that by GuideBO we obtain dense set of configurations in the region of interest as desired. In contrast, for HVT we obtain samples all over the front. In addition, the distribution of points is not always evenly spread along the front, so that certain part of the front are denser than other. This explains why HVI (and similarly the other baselines) is inferior compared to GuideBO since for certain a values the distribution of the selected configurations is sparse near the limiting value.
30

---

Published in Transactions on Machine Learning Research (10/2024)
Methed
0.5
Method
Method
0.10
GuideBO
GurdeBO
Guide9O
Limit
0.4
Usder Limit
Limit
0.08
Worst Ereer
0.04
0.2
0.02
0.1
0.165
0.17
0.175
0.10
0.055
0.065
0.075
0.085
0.055
0.063
0.075
0.085
(a) Fairness
(b) Robustness
(c) Selective Robustness
0.200
Method
Mothed
Mcthad
Upper
GuideBO
Upper Limit
GuideBO
0.8
Upppor Limit
GuideBO
0.150
Reletive Cosc
0.125
0.6
K.D
1.5
0.100
0.4
10
0.050
0.2
0.025
0.000
0.0
0.02
(d) VAE
(e) Pruning
(f) Early Classification
Figure E.7: Ablation study comparing the proposed method with two-sided region to one-sided upper bound, defined by the limit a. The plots present the scores obtained for the free objective.
31

---

Published in Transactions on Machine Learning Research (10/2024)
0.15
0.15
DDP
DDP
0.10
0.05
0.00
0.00
0.15
0.16
0.17
0.18
0.19
0.16
0.18
0.20
Eror
(a) Fairness (GuideBO, 0.17)
(b) Fairness (Full)
80
KLD
40
20
20
0
0.01
0.02
0.03
MSE
MSE
(c) VAE (GuideBO, a = 0.03)
(d) VAE (Full)
1.0
1.0
0.8
Relative Cost
Relative Cost
0.6
0.4
0.4
0.2
0.2
0.0
ome
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Accuracy Difference
Accuracy Difference
(e) Pruning (GuideBO, 0.075)
(I) Pruning (Full)
0.9
0.8
Halt Time
Halt
0.6
0.4
0.00
0.08
0.00
0.05
0.15
Accuracy Diffrence
Accuracy Diffrence
(g) Early Class. (GuideBO, a = 0.05)
(h) Early-Time Class. (Full)
Figure E.8; Demonstration of the selection outcomes of the BO procedure, comparing the proposed method (left) to full recovery of the Pareto front by HVI (right): the green square is the defined reference point, the blue points correspond to the initial set of configurations, and the red points correspond to selected configurations. Dashed lines enclose the region of interest.
32


Reviews:
[{"review_id": "a0l9qRwdyU", "reviewer": "Reviewer_aZFZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Pros\n- By providing a statistically validated method for model selection that ensures adherence to user-specified risk limits, this approach has an impact on the real-world deployment of learning models, where balancing multiple aspects under risk constraints could be crucial.\n- The proposed algorithm steps are easy to understand and not overly complex in practical terms, making its potential for broader application quite feasible.\n- The idea of deriving a region of interest guided by the testing goal is interesting to me. This technique of incorporating the testing goal into the optimization process could potentially attract attention from other relevant communities, such as researchers in the targeted learning field.\n- The method leverages the efficiency of BO to explore the configuration space, coupled with a focused optimization strategy that avoids the computational burden of evaluating irrelevant configurations. It therefore inherits the advantages of BO.\n- The authors' illustration figures are well-done and effectively convey the overarching concepts of the algorithm to the readers.\n\n## Cons\n- This method requires $X$ and $Y$ as input, thus it appears unsuitable for many semi-supervised (or unsupervised) learning problems in machine learning. What modifications to the algorithm and theory would be necessary to extend it to these different settings?\n- Although the overall structure is clear, the current version lacks readability. Many sentences are presented in a wordy way, and some math symbols are not well-defined or self-consistent. Significant improvements in writing and presentation are needed, please refer to the subsequent comments for details.\n- In the testing stage (i.e., the claimed risk-controlling), the authors primarily follow the proof techniques from LTT [R1]. This results in theoretical advancements in statistical efficiency being incremental. However, considering TMLR's criteria, this should not be regarded as a significant drawback.\n  - [R1] Angelopoulos, Anastasios N., et al. \"*Learn then test: Calibrating predictive algorithms to achieve risk control.*\" arXiv preprint arXiv:2110.01052 (2021).\n- I think some of the proofs in the appendix have issues, which might again weaken the contributions and solidness. Technically,\n  1. The analysis simultaneously uses $P$ and $\\mathbb{P}$ in one equation (like Eq. 26) without clarifying the distinction between the two. Do you mean to suggest that $P(\\cdot)$ represents the vanilla probability, while $\\mathbb{P}(\\cdot)$ denotes the empirical probability (with finite sample)?\n  2. Concentration inequalities require the values of the random variables to be valid. Thus, the authors assume the upper bound of the $\\hat{\\ell}^{cal}$ and $\\hat{\\ell}^{opt}$ does not exceed $1$. Is this assumption too strict and therefore meaningless in practice? If the loss exceeds this range, how should we scale the $\\alpha^{max}$ and $R(\\alpha,k,m,\\delta,\\gamma)$ to ensure our theoretical framework remains effective? Please provide a comment on this.\n  3. Note that the $m$ is the number of random variables, not $n$. So I guess the Hoeffding’s inequality in Eq. 17 should be $P\\left(\\hat{\\ell}^{cal}(\\boldsymbol{\\lambda}) -\\ell(\\boldsymbol{\\lambda})\\leq -t\\right) \\leq e^{-2mt^2},$ or $P\\left(\\hat{\\ell}^{val}(\\boldsymbol{\\lambda}) -\\ell(\\boldsymbol{\\lambda})\\leq -t\\right) \\leq e^{-2kt^2}$.\n  \n  4. According to the  super-uniform $P(p\\_{\\boldsymbol{\\lambda}}^{\\mathrm{HF}}\\leq u)\\leq u$, shouldn't we obtain that $p\\_{\\boldsymbol{\\lambda}}^{\\mathrm{HF}}=e^{-2 n(\\alpha-\\hat{\\ell}(\\boldsymbol{\\lambda}))^2}$? How do we transform the coeff $-2n$ in Eq. 24 into $-2m$, and what does $(\\cdot)\\_+$ represent? Shouldn't the square function always be non-negative?\n  5. When deriving Eqs. 7 and 8 in the main body, one assumption the authors did not mention but implicitly used is that $\\gamma=e^{-2kt^2}$ for $t>0$, with $0<\\gamma\\leq \\frac{1}{2}$ (hand calculations, may not be true). This corresponds to the second line of Eq. 26 in the appendix. Please address this oversight and provide clarification on it.\n  6. (Minor) In Eq. 27, it's unclear what the operation between the two scalars $\\hat{\\ell}\\wedge \\alpha$ represents, and the factor $e$ is also undefined. Meanwhile, the Eqs. 17, 18, and 19 should end with commas, not periods.\n- Due to the lack of theoretical analysis from an optimization side (e.g., iteration bounds or sample complexity), the contributions of this paper rely heavily on empirical experiments (Sec. 6 and App. E). Unfortunately, most tasks in the experiments involve no more than $5$ hyperparameters in configuration, which represents a relatively small optimization space, potentially not convincing and undermining the paper's contributions. \n  - I highly recommend that the authors include higher-dimensional model selection experiments to better highlight the advantages of the proposed algorithm. Additionally, plotting wall-clock time versus the number of hyperparameters $n$ would help illustrate the 'efficiency gap' between the new algorithm and the baselines in high-dimensional settings. Visualizing the region of interest (in low-dimensional toy cases) could further enhance the presentation of experiments.\n- (Minor) The authors didn't submit the code for verification.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission 2917 introduces GuideBO, a novel method that integrates Bayesian optimization with rigorous risk control to find hyperparameter configurations meeting user-defined constraints while optimizing other designed metrics. \nThis algorithm first introduces the concept of a \"region of interest\" $R$ in the objective space $\\mathbb{R}^{c+1}$, which significantly reduces the search space for candidate configurations. \nComputationally, the method modifies the traditional BO procedure to focus on Pareto optimal configurations $\\hat{\\mathcal{P}}$ within the defined region of interest $\\mathcal{C}_n$. After identifying candidate configurations, the method applies statistical testing tools (i.e. Learn then Test, LTT) to obtain the $(\\alpha, \\delta)$ -risk-controlling prediction. \nEmpirical experiments show that GuideBO effectively selects efficient and verified configurations under practical budget constraints, outperforming several baseline methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- (important) For changes on the simulations and proofs, please refer to the weaknesses above.\n- The related work section is comprehensive but could benefit from a more structured approach. I suggest the authors discuss directly related works (Stanton et al., 2023; Salinas et al., 2023) in a separate paragraph rather than within a long domain description. Additionally, consider discussing some work on black-box model selection under multiple objectives (e.g. some work mentioned in [R2]), as the current \"Additional related work\" merely extends the MOO paragraph.\n  - [R2] Karl, Florian, et al. \"*Multi-objective hyperparameter optimization in machine learning—An overview.*\" ACM Transactions on Evolutionary Learning and Optimization 3.4 (2023): 1-50.\n- Eq. 1 falls into the typical definition of risk-controlling prediction. I suggest that the authors relate it to the concept and literature of $(\\alpha, \\delta)$- RCP.\nIn Eq. 3, the RHS should be $H(\\hat{\\mathcal{P}}; \\mathbf{r})$ to be consistent with the definition provided below.\n- The BO part in Sec. 4 could be quite confusing. What does $\\|\\mathcal{C}_n\\|$ refer to here? Is it the same as $N_0$ defined earlier? The $\\mathbf{l}$ is not defined. The authors also seem to use $\\kappa,k, \\mathbf{k},k_i$ inconsistently, lacking clear notation for each. \nWhat do you mean by \"After a new configuration is selected, it is evaluated and added to the pull\", is that \"pool\"?\nI'm familiar with BO and can infer the meanings, but for someone else, this might be somehow difficult to grab.\n- Could the authors briefly summarize the limitations of their work?\n- In Section 5.3, it should be $\\mathbf{\\lambda}^*=\\arg\\min_{\\mathbf{\\lambda}\\in\\mathcal{C}^{valid}}$. Similarly, in Algorithm C.1, the step should be $\\mathbf{\\lambda}^*\\gets \\arg\\min_{\\mathbf{\\lambda}}$.\n- Please fix typos:\n  - page 1, paragraph 3, \"Addressing from a different prospective\": \"prospective\" should be \"perspective\"\n  - page 2, \"...and identify highly-preforming configurations\": \"highly-preforming\" should be \"highly-performing\"\n  - page 3, paragraph 2, \"However, when used in model hyperparamaeter tuning ...\": \"hyperparamaeter\" should be \"hyperparameter\"\n  - Similarly, on page 3 & page 10, the word \"hyperparmeter\" should be \"hyperparameter\"\n  - after Eq.5, \"to be risk-condoling\" should be \"risk-controlling\"\n- Some observed incorrect sentences:\n  - page 10: \"(i) difference between the full-time prediction the early-time prediction\" -> add \"and\"\n  - Algorithm 1: \"ParetoFront() filter Pareto optimal objective\"  -> \"filters\"\n  - Fig. 5 caption: \"Presents ...\" -> consider \"Presentations of ...\"\n  - Conclusion: \"lie the specified region\"-> add ''in\"; \"The broad applicability and effectiveness is demonstrated\" ->  \"are\"", "broader_impact_concerns": "This paper is a general algorithmic research that has no ethical implications and does not require an impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6lffIZkaIm", "reviewer": "Reviewer_5hEm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths ###\n- The proposed framework is applicable to a wide variety of problems.\n- GuideBO is mathematically well-motivated and the approach is novel, as far as I know.\n- The paper is clearly written.\n- Experiments are done on a wide variety of problems and GuideBO is ranked first in terms of the objective value obtained in the majority of cases.\n- Ablations are carried out on the strictness of the constraints and the size of the region where the proposed configurations lie.\n\n### Weaknesses ###\n- There are no theoretical guarantees on whether GuideBO is able to find the optimal configuration, even in the convex setting.\n- The authors argue that GuideBO leads to more efficient statistical testing with fewer computations, but take an indirect approach in the experiments by fixing the budget of proposed configurations. A more direct and complete approach would be, for a set of objective values L, compare the N that is needed to achieve an objective smaller than L for each baseline.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of hyperparameter optimization when there are constraints on quantities that must be estimated from data. For example, selecting the learning rate to minimize the classification error while bounding the worst case error on sensitive subgroups. The proposed approach GuideBO consists of two stages: 1) identify Pareto optimal configurations that lie in a region where the constraints are satisfied with high probability and 2) perform statistical testing on the identified configurations to find the one that optimizes the objective while rejecting the null hypothesis that at least one constraint is not satisfied. Experiments are done on a variety of settings like fairness, generative modeling, and network pruning. GuideBO outperforms existing baselines in terms of the objective value obtained.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "### Critical ###\n- Empirically illustrate the budget size that is needed achieve an objective smaller than L, for a range of values of L.\n\n### Other ###\n- Discuss the possibility of theoretical guarantees.\n\n### Questions ###\n- How is the filtration for Pareto optimal configurations done? (Line 7 of Algorithm 1)", "broader_impact_concerns": "Since GuideBO is a general-purpose optimization algorithm, there are no direct societal impacts. No broader impact statement is included.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fqK4fMi5f3", "reviewer": "Reviewer_x3Gv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strength* — I found the paper quite clear and the proposed strategy, which combines a Bayesian strategy with a hypothesis testing step, seems to me an interesting combination and progress with respect to previous contributions. One of the key aspects of the method is the identification of a suitable feasible subspace of hyperparameters that allows the resizing of the space to be explored to search for Pareto configurations.\n\n*Weaknesses* — The proposed strategy might result in a ```null``` set of hyperparameters, but this limitation might be avoided by choosing different input tolerances. As anticipated, the paper is globally well written; however, the portion on the numerical exploration of the strategy is more confusing as various experiments are presented and discussed in a quite compressed space.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on the problem of optimally tuning hyperparameters in machine learning by combining a Bayes-Optimal strategy aiming at identifying a subset of Pareto optimal model configurations related to a specific *region of interest*, aptly identified according to user-specified tolerances, subsequently selected according to a statistical hypothesis testing. The strategy is tested in a number of numerical experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The analysis relies on the adoption of a Gaussian process as a surrogate model. Do the authors expect this choice to be important for the efficacy of the algorithm? (e.g., is it possible that the algorithm might benefit from fat-tailed processes depending on the functional form of $\\ell$?)\n- On page 6, the authors assume that efficiency and validity are sort-of completely anti-correlated, and this justifies the assumption that the loss has to take values around $\\alpha^{\\rm max}$. This is not very clear to me: could the author clarify this step?\n- Is the acquisition function optimization step possibly going to suffer non-convexity issues?\n- From what I understand, it is assumed everywhere that $\\boldsymbol\\lambda\\in\\mathbb R^d$ with $d\\ll m,k$. Is this correct?\n- In the *Classification robustness* experimental setup, do the authors create $\\mathcal D_{\\boldsymbol\\lambda}$ by allowing repetion in the sampling? In this case, it should be specified.\n\nMinor aspects:\n- The notation in Eq. 4 is not very clear (in particular, what $\\boldsymbol\\ell(\\boldsymbol\\lambda)\\cup\\hat{\\mathcal P}$ means is not specified).\n- On page 5, there is confusion in the notation regarding $\\kappa$ and $k$.\n- Right before Eq. 7, $\\hat\\ell_1^{\\rm opt}$ does not seem to be defined.\n- In line 1 of the Algorithm on page 8, do the authors mean $\\ell_c^{\\rm high}$?", "broader_impact_concerns": "There are no concerns about the ethical implications of the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method for constrained Bayesian optimization, where the goal is to optimize an unknown function (e.g. find optimal training hyperparameters for a machine learning model) while controlling risks (such as enforcing fairness constraints). The paper introduces the concept of a "region of interest" for satisfying the user constraints, and the proposed method aims to find the intersection of the Pareto front with this region of interest.

The paper is well-written, and provides sufficient evidence for the claims made. The reviewers engaged with the authors on the technical details of the proofs and experiments, and the current version of the paper includes the necessary clarifications. In particular, during the rebuttal stage the authors added new experiments with higher-dimensional optimization problems. 

Overall, this is a strong high-quality paper, and it will be a valuable contribution to TMLR.
Decision: Accept (poster)