Density Ratio Estimation-based Bayesian Optimization with Semi-Supervised Learning

## Abstract

Abstract Bayesian optimization has attracted huge attention from diverse research areas in science and engineering, since it is capable of efficiently finding a global optimum of an expensive-to-evaluate black-box function. In general, a probabilistic regression model is widely used as a surrogate function to model an explicit distribution over function evaluations given an input to estimate and a training dataset. Beyond the probabilistic regression-based methods, density ratio estimation-based Bayesian optimization has been suggested in order to estimate a density ratio of the groups relatively close and relatively far to a global optimum. Developing this line of research further, supervised classifiers are employed to estimate a class probability for the two groups instead of a density ratio. However, the supervised classifiers used in this strategy are prone to be overconfident for known knowledge on global solution candidates. Supposing that we have access to unlabeled points, e.g., predefined fixed-size pools, we propose density ratio estimation-based Bayesian optimization with semi-supervised learning to solve this challenge. Finally, we show the empirical results of our methods and several baseline methods in two distinct scenarios with unlabeled point sampling and a fixed-size pool and analyze the validity of our proposed methods in diverse experiments.

## 1 Introduction

Bayesian optimization (Brochu et al., ; Garnett, ) has attracted immense attention
from various research areas
such as hyperparameter optimization (Bergstra et al., ),
battery lifetime optimization (Attia et al., ),
chemical reaction optimization (Shields et al., ),
and nanophotonic structure optimization (Kim et al., ),
since it is capable of efficiently finding a global optimum
of an expensive-to-evaluate black-box function.
As studied in previous literature on Bayesian
optimization (Snoek et al., ; Martinez-Cantin et al., ; Springenberg et al., ; Hutter et al., ),
a probabilistic regression model, which can estimate a distribution of function evaluations
over inputs, is widely used as a surrogate
function;
A Gaussian process (GP) (Rasmussen & Williams, )
is a predominant choice for the surrogate function.
An analogy between probabilistic regression models in Bayesian optimization
is that they rely on an explicit function over function evaluations
$p(y\mid\mathbf{x},\mathcal{D})$
given an input to estimate, denoted as $\mathbf{x}$,
and a training dataset $\mathcal{D}$.

Beyond the probabilistic regression-based Bayesian optimization,
density ratio estimation (DRE)-based Bayesian optimization has been studied
recently (Bergstra et al., ; Tiao et al., ).
Furthermore,
likelihood-free Bayesian optimization,
which is equivalent to DRE-based Bayesian optimization with a particular utility function, has been proposed by Song et al. ().
Bergstra et al. () attempt to model two densities $p(\mathbf{x}\mid y\leq y^{\dagger},\mathcal{D})$ and $p(\mathbf{x}\mid y>y^{\dagger},\mathcal{D})$,
where $y^{\dagger}$ is a threshold for dividing inputs to two groups that are relatively close and relatively far to a global solution,
in order to estimate $\zeta$-relative density ratio (Yamada et al., ).
On the other hand,
instead of modeling two densities separately,
Tiao et al. (); Song et al. () estimate a density ratio
using class-probability estimation (Qin, ).
As discussed in the previous work,
this line of research provides a new understanding of Bayesian optimization,
which allows us to solve Bayesian optimization
using binary classification.
Moreover,
it can reduce the amount of computation required
for building surrogate functions.

However, the supervised classifiers utilized in the DRE-based Bayesian optimization are prone to be overconfident for known knowledge on global solution candidates or a region that have been already exploited.
In this paper,
supposing that we have access to unlabeled points,
we propose a novel DRE-based method with semi-supervised learning,
which is named DRE-BO-SSL, to solve this over-exploitation problem.
Although our direct competitors,
i.e., BORE (Tiao et al., ) and LFBO (Song et al., ),
show their strengths through theoretical and empirical analyses,
our algorithm betters an ability to consider a wider region that satisfies $p(\mathbf{x}\mid y\leq y^{\dagger},\mathcal{D})\geq p(\mathbf{x}\mid y>y^{
\dagger},\mathcal{D})$,
than the competitors,
as shown in Figure 1.
By this intuitive example in Figure 1,
we presume that DRE-BO-SSL appropriately balances exploration and exploitation
rather than the existing methods.
Compared to a supervised classifier,
e.g., random forests (Breiman, ),
gradient boosting (Friedman, ),
and multi-layer perceptrons,
our semi-supervised classifiers,
i.e., label propagation (Zhu & Ghahramani, )
and label spreading (Zhou et al., ),
are less confident in terms of the regions of global solution candidates
by using unlabeled data points;
see Figures 1 and 9
and Sections 1.1 and 3 for detailed examples and analyses.

To make use of semi-supervised classifiers,
we take into account *two distinct scenarios
with unlabeled point sampling
and with a predefined fixed-size pool*.
For the first scenario,
we randomly sample unlabeled data points
from the truncated multivariate normal distribution using a minimax tilting method (Botev, ),
in order that it is possible that a cluster assumption (Seeger, ) is assumed.
Finally, we demonstrate that our method shows superior performance
compared to the exiting methods in diverse experiments
including synthetic benchmarks,
Tabular Benchmarks (Klein & Hutter, ),
NATS-Bench (Dong et al., ),
and 64D minimum multi-digit MNIST search.
Note that Tabular Benchmarks, NATS-Bench,
and 64D minimum multi-digit MNIST search have access to fixed-size pools.
Furthermore,
in order to validate our methods,
we provide thorough analyses on the components of DRE-BO-SSL in Section 6 and the appendices.

To sum up,
our contributions are itemized as follows:

- •
we identify the over-exploitation problem of supervised classifiers in DRE-based Bayesian optimization;
- •
we propose DRE-based Bayesian optimization with semi-supervised learning, named DRE-BO-SSL for two distinct scenarios with unlabeled point sampling and a predefined fixed-size pool;
- •
we demonstrate the effectiveness of our method in various experiments including NATS-Bench and 64D minimum multi-digit MNIST search.

*We promise to release our implementation upon publication.*

Figure: (a) MLP, BORE, Iterations 1 to 5
Refer to caption: x1.png

### 1.1 Over-exploitation Problem

As illustrated in Figures 1 and 9,
the supervised classifiers used in DRE-based Bayesian optimization
suffer from the over-exploitation problem.
Interestingly,
many deep learning models also share a similar problem, which is called an overconfidence problem (Guo et al., ; Müller et al., ),
due to various reasons, but primarily due to overparameterization.
It is noteworthy that the definition of the over-exploitation problem in DRE-based Bayesian optimization
is different from the overconfidence problem in general classification.
The definition in DRE-based Bayesian optimization does not imply that a single data point has a high probability for a particular class,
but it implies that a few data points have high probabilities for a class of interest.
More precisely,
our definition indicates the problem of overconfidence over known knowledge on global solution candidates.
For example,
the definition in general classification includes
a case that 50% of data points are biased to one class
and the remainder is biased to another class.
On the contrary,
this definition does not include such a case
and it only includes a case that a small number of data points or the small region of a search space,
which is colored in yellow in Figures 1 and 9,
are biased to some particular class,
i.e., Class 1 in the DRE-based Bayesian optimization problems.

By the aforementioned definition,
at early iterations of Bayesian optimization,
a supervised classifier tends to
overfit to a small size of $\mathcal{D}_{t}$
due to a relatively large model capacity.
This consequence makes a Bayesian optimization algorithm
highly focus on exploitation.
Similar to our observation,
the imbalance of exploration and exploitation in the DRE-based approaches is also discussed in the recent work (Oliveira et al., ; Pan et al., ).
Moreover,
the consequence mentioned above is different from the characteristics of probabilistic regression-based Bayesian optimization
because the regression-based methods are capable of exploring unseen regions by dealing with uncertainties.
Besides, even though a threshold ratio $\zeta$ might be able to mitigate this problem,
an overconfident supervised classifier is likely to keep getting stuck in a local optimum
as $y^{\dagger}$ cannot change dramatically;
more detailed analysis on $\zeta$ is provided in Sections 6 and H.

## 2 Background and Related Work

##### Bayesian Optimization.

It is a principled and efficient approach
to finding a global solution of a challenging objective,
e.g., expensive-to-evaluate black-box functions (Brochu et al., ; Garnett, ).
To focus on a probabilistic regression model as a surrogate function,
we omit the details of Bayesian optimization here;
see (Brochu et al., ; Garnett, )
for details.
In Bayesian optimization,
GP regression (Rasmussen & Williams, )
is widely used as a surrogate function (Srinivas et al., ; Snoek et al., )
because of its flexibility with minimum assumptions on model and smoothness.
While GP is a probable choice,
Bayesian optimization with diverse surrogates
such as Student-$t$ process regression (Martinez-Cantin et al., ),
Bayesian neural networks (Springenberg et al., ),
and tree-based models (Hutter et al., ; Kim & Choi, )
has been proposed.
An analogy between such models is
that they model $p(y\mid\mathbf{x},\mathcal{D})$ explicitly,
so that it can be used to define an acquisition function
with the statistics of $p(y\mid\mathbf{x},\mathcal{D})$.

##### Density-Ratio Estimation.

Whereas knowing a data distribution $p(\mathbf{x})$ is important,
it is difficult to directly estimate $p(\mathbf{x})$ (Sugiyama et al., ).
For specific machine learning problems such as importance sampling (Kloek & van Dijk, )
and mutual information estimation (Bishop, ),
we can bypass direct density estimation
and estimate a density ratio.
More recently,
Rhodes et al. () tackle a density-chasm problem using telescopic density-ratio estimation,
which replaces an original problem with a set of logistic regression problems.
Since the work (Rhodes et al., ) suffers from the issue on distribution shift, the recent work (Srivastava et al., ) proposes a density ratio estimation method with multinomial logistic regression, which is capable of mitigating the distribution shift using multi-class classification.
In Bayesian optimization,
Bergstra et al. () have proposed a strategy with tree-structured Parzen estimators
to estimate a density ratio
as an alternative to probabilistic regression-based acquisition functions.
In addition,
the work (Tiao et al., ; Song et al., )
suggests methods with binary classifiers
in order to estimate class probabilities as a density ratio;
see Section 3 for details.

##### Semi-Supervised Learning.

It is a learning scheme with both labeled and unlabeled data (Zhu, ; Chapelle et al., ; Bengio et al., ).
To cooperate with labeled and unlabeled data,
this strategy generally utilizes geometry of data points
or connectivity between points,
and assigns pseudo-labels to unlabeled data points,
which referred to as transductive learning (Gammerman et al., ).
As a semi-supervised learning method on a similarity graph,
Zhu & Ghahramani () propose a label propagation algorithm
which iteratively propagates the labels of unlabeled data points using labeled data.
Zhou et al. () compute
the labels of labeled and unlabeled data points
by a weighted iterative algorithm with initial labels.
Belkin & Niyogi () predict pseudo-labels
by finding a linear combination of a few smallest eigenvectors of the graph Laplacian.

## 3 DRE-based Bayesian Optimization

Unlike probabilistic regression-based Bayesian optimization,
DRE-based Bayesian optimization employs
a density ratio-based acquisition function,
defined with a density $p(\mathbf{x}\mid y\leq y^{\dagger},\mathcal{D}_{t})$,
where $\mathbf{x}$ is a $d$-dimensional vector,
$y$ is its function evaluation,
$y^{\dagger}$ is a threshold,
and $\mathcal{D}_{t}=\{(\mathbf{x}_{i},y_{i})\}_{i=0}^{t}$ is a dataset of $t+1$ pairs of data point and evaluation.
In particular,
the work by Bergstra et al. ()
defines an acquisition function
based on $\zeta$-relative density ratio (Yamada et al., ):

$$ $A(\mathbf{x}\!\mid\!\zeta,\mathcal{D}_{t})\!=\!\frac{p(\mathbf{x}\!\mid\!y\! \leq\!y^{\dagger},\mathcal{D}_{t})}{\zeta p(\mathbf{x}\!\mid\!y\!\leq\!y^{ \dagger},\mathcal{D}_{t})\!+\!(1\!-\!\zeta)p(\mathbf{x}\!\mid\!y\!>\!y^{ \dagger},\mathcal{D}_{t})},$ (1) $$

where $\zeta=p(y\leq y^{\dagger})\in[0,1)$ is a threshold ratio.
We need to find a maximizer of (1),
by optimizing the following composite function:
$h(p(\mathbf{x}\mid y\leq y^{\dagger},\mathcal{D}_{t})/p(\mathbf{x}\mid y>y^{
\dagger},\mathcal{D}_{t}))$,
where $h(x)=(\zeta+(1-\zeta)x^{-1})^{-1}$.
Since $h$ is a strictly increasing function,
we can directly maximize $p(\mathbf{x}\mid y\leq y^{\dagger},\mathcal{D}_{t})/p(\mathbf{x}\mid y>y^{
\dagger},\mathcal{D}_{t})$.
In the previous work (Bergstra et al., ),
two tree-structured Parzen estimators are used to estimate the respective densities, $p(\mathbf{x}\mid y\leq y^{\dagger},\mathcal{D}_{t})$
and $p(\mathbf{x}\mid y>y^{\dagger},\mathcal{D}_{t})$.

While the work (Bergstra et al., ) utilizes two distinct tree-structured Parzen estimators,
Tiao et al. () propose
a method to directly estimate (1)
using class-probability estimation (Qin, ; Sugiyama et al., ),
which is called BORE.
Since it can be formulated as a problem of binary classification in which Class 1 is a group of the top $\zeta$ of $\mathcal{D}_{t}$ and Class 0 is a group of the bottom $1-\zeta$ of $\mathcal{D}_{t}$ in terms of function evaluations,
the acquisition function defined in (1) induces the following:

$$ $A(\mathbf{x}\mid\zeta,\mathcal{D}_{t})=\frac{p(\mathbf{x}\mid z=1)}{\zeta p( \mathbf{x}\mid z=1)+(1-\zeta)p(\mathbf{x}\mid z=0)}.$ (2) $$

By the Bayes’ theorem, (2)
becomes $A(\mathbf{x}\mid\zeta,\mathcal{D}_{t})=\zeta^{-1}p(z=1\mid\mathbf{x})/(p(z=1
\mid\mathbf{x})+p(z=0\mid\mathbf{x}))$.
Therefore, a class probability over $\mathbf{x}$ for Class 1
is considered as an acquisition function;
it is simply denoted as $A(\mathbf{x}\mid\zeta,\mathcal{D}_{t})=\zeta^{-1}\pi(\mathbf{x})$.
Eventually, the class probability is estimated by
various off-the-shelf classifiers such as random forests and multi-layer perceptrons.

Song et al. () have suggested a general framework of likelihood-free Bayesian optimization, called LFBO:

$$ $A(\mathbf{x}\mid\zeta,\mathcal{D}_{t})=\operatornamewithlimits{\arg\max}_{S: \mathcal{X}\to\mathbb{R}}\mathbb{E}_{\mathcal{D}_{t}}[u(y;y^{\dagger})f^{ \prime}(S(\mathbf{x}))-f^{*}(f^{\prime}(S(\mathbf{x})))],$ (3) $$

which is versatile for any non-negative utility function $u(y;y^{\dagger})$,
where $f$ is a strictly convex function
and $f^{*}$ is the convex conjugate of $f$.
By the properties of LFBO,
it is equivalent to an expected utility-based acquisition function.
Along with the general framework,
Song et al. () prove that BORE is equivalent to the probability of improvement (Kushner, )
and LFBO with $u(y;y^{\dagger})=\mathbb{I}(y\leq y^{\dagger})$
is also equivalent to the probability of improvement,
where $\mathbb{I}$ is an indicator function.
Moreover, they show that
their method with $u(y;y^{\dagger})=\max(y^{\dagger}-y,0)$,
which can be implemented as weighted binary classification,
is equivalent to the expected improvement (Jones et al., ).

## 4 DRE-based Bayesian Optimization with Semi-Supervised Learning

Figure: Algorithm 1 DRE-BO-SSL

We introduce DRE-based Bayesian optimization with semi-supervised learning, named DRE-BO-SSL,
by following the previous studies in DRE-based and likelihood-free Bayesian optimization (Bergstra et al., ; Tiao et al., ; Song et al., ),
which were discussed in Section 3.

Similar to the standard Bayesian optimization
and existing DRE-based Bayesian optimization,
DRE-BO-SSL iterates the undermentioned steps as presented in Algorithm 1.
Firstly, a threshold $y_{t}^{\dagger}$ is calculated by considering $y_{1:t}$ with $\zeta$.
Secondly, labels $\mathbf{C}_{t}$ of data points in $\mathcal{D}_{t}$ are assigned to one of two classes;
a group of $y\leq y_{t}^{\dagger}$ is assigned to Class 1
and a group of $y>y_{t}^{\dagger}$ is assigned to Class 0.
If we are given unlabeled data points $\mathbf{X}_{u}$,
the corresponding points $\mathbf{X}_{u}$ are used,
but if not available it samples $n_{u}$ unlabeled data points $\mathbf{X}_{u}$ from $\mathcal{X}$ by utilizing a strategy described in Section 4.2.
Then, it estimates pseudo-labels $\widehat{\mathbf{C}}_{t}$ of a semi-supervised learning model
by following the procedure presented in Section 4.1 and Algorithm 2.
Using $\widehat{\mathbf{C}}_{t}$,
it chooses the next query point $\mathbf{x}_{t+1}$:

$$ $\mathbf{x}_{t+1}=\operatornamewithlimits{\arg\max}_{\mathbf{x}\in\mathcal{X}} \pi_{\widehat{\mathbf{C}}_{t}}(\mathbf{x};\zeta,\mathcal{D}_{t},\mathbf{X}_{u}),$ (4) $$

where $\pi_{\widehat{\mathbf{C}}_{t}}(\mathbf{x};\zeta,\mathcal{D}_{t},\mathbf{X}_{u})$ predicts a class probability over $\mathbf{x}$ for Class 1;
see (9).

We adopt a multi-started local optimization technique, e.g., L-BFGS-B (Byrd et al., ),
to solve (4).
However,
a flat landscape of $\pi_{\widehat{\mathbf{C}}_{t}}(\mathbf{x};\zeta,\mathcal{D}_{t},\mathbf{X}_{u})$ over $\mathbf{x}$ may occur,
so that optimization performance can be degraded.
To tackle this issue,
a simple heuristic of randomly selecting a query point among points with identical highest class probabilities complements our method.
Since the multi-started technique is utilized
and the output of $\pi_{\widehat{\mathbf{C}}_{t}}$ is bounded in $[0,1]$,
a flat landscape is easily recognized
by comparing the outcomes of the multi-started strategy.

### 4.1 Label Propagation and Label Spreading

Here we describe semi-supervised learning techniques (Zhu, ; Chapelle et al., ; Bengio et al., ) to build DRE-BO-SSL.
We cover a transductive setting (Gammerman et al., ),
which is to label unlabeled data by utilizing given labeled data,
and then an inductive setting, which is to predict any point
using pseudo-labels of unlabeled and labeled data.

Suppose that each data point is defined
on a $d$-dimensional compact space $\mathcal{X}\subset\mathbb{R}^{d}$.
We consider $n_{l}$ labeled points $\mathbf{X}_{l}\in\mathbb{R}^{n_{l}\times d}$,
their corresponding labels $\mathbf{C}_{l}\in\mathbb{R}^{n_{l}\times c}$,
and $n_{u}$ unlabeled points $\mathbf{X}_{u}\in\mathbb{R}^{n_{u}\times d}$,
where $c$ is the number of classes.
$\mathbf{X}_{l}$ and $\mathbf{C}_{l}$ are query points that have already been evaluated and their class labels;
we define
$\mathbf{X}_{l}=[\mathbf{x}_{0},\ldots,\mathbf{x}_{n_{l}-1}]^{\top}$ for $\mathcal{D}_{t}=\{(\mathbf{x}_{i},y_{i})\}_{i=0}^{n_{l}-1}$.
For the sake of brevity,
the concatenated data points of $\mathbf{X}_{l}$ and $\mathbf{X}_{u}$ are defined as
$\mathbf{X}=[\mathbf{X}_{l};\mathbf{X}_{u}]\in\mathbb{R}^{(n_{l}+n_{u})\times d}$.
Note that in our problem $c=2$ because we address the problem with two classes.

As shown in Algorithm 2,
we first initialize labels to propagate $\widehat{\mathbf{C}}\in\mathbb{R}^{(n_{l}+n_{u})\times 2}$;
it is initialized as $\widehat{\mathbf{C}}=[\mathbf{c}_{0},\ldots,\mathbf{c}_{n_{l}-1},\mathbf{c}_{n
_{l}},\ldots,\mathbf{c}_{n_{l}+n_{u}-1}]^{\top}$,
where $\mathbf{c}_{0},\ldots,\mathbf{c}_{n_{l}-1}$ are one-hot representations
$[\mathbf{C}_{l}]_{1:},\ldots,[\mathbf{C}_{l}]_{n_{l}:}$,
and $\mathbf{c}_{n_{l}},\ldots,\mathbf{c}_{n_{l}+n_{u}-1}$ are zero vectors.
Denote that $[\mathbf{C}]_{i:}$ is $i$th row of $\mathbf{C}$.
Then, we compute
a similarity between two data points $\mathbf{x}_{i},\mathbf{x}_{j}\in\mathcal{X}$,
so that we compare all pairs in $\mathbf{X}$.
For example, one of popular similarity functions, i.e., a radial basis function kernel, can be used:

$$ $w_{ij}=\exp\left(-\beta\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}^{2}\right),$ (5) $$

where $\beta$ is a free parameter given.
As discussed in the work (Zhu & Ghahramani, ),
we can learn $\beta$ in (5)
by minimizing an entropy for propagated labels $\widehat{\mathbf{C}}$:

$$ $H(\widehat{\mathbf{C}})=-\sum_{i=1}^{n_{l}+n_{u}}[\widehat{\mathbf{C}}]_{i:}^{ \top}\log[\widehat{\mathbf{C}}]_{i:}.$ (6) $$

See Figure 4 for the results of learning $\beta$
and Section E for analysis on the effects of $\beta$.
By (5),
we compute a transition probability from $\mathbf{x}_{j}$ to $\mathbf{x}_{i}$ by
$p_{ij}=w_{ij}/\sum_{k=1}^{n_{l}+n_{u}}w_{kj}$.
Note that similarities $\mathbf{W}\in\mathbb{R}^{(n_{l}+n_{u})\times(n_{l}+n_{u})}$ and transition probabilities $\mathbf{P}\in\mathbb{R}^{(n_{l}+n_{u})\times(n_{l}+n_{u})}$ are defined, where $[\mathbf{W}]_{ij}=w_{ij}$ and $[\mathbf{P}]_{ij}=p_{ij}$.
Moreover,
by the definition of $p_{ij}$,
$\mathbf{P}=\mathbf{D}^{-1}\mathbf{W}$,
where $\mathbf{D}$ is a degree matrix
whose diagonal entry is defined as $[\mathbf{D}]_{ii}=\sum_{j=1}^{n_{l}+n_{u}}[\mathbf{W}]_{ij}$.

With initial $\widehat{\mathbf{C}}$ and $\mathbf{P}$,
we repeat the following steps:
(i) computing the next $\widehat{\mathbf{C}}$;
(ii) normalizing $\widehat{\mathbf{C}}$ row-wise,
until a change of $\widehat{\mathbf{C}}$ converges to a tolerance $\varepsilon$
or the number of iterations propagated reaches to maximum iterations $\tau$.
In particular, label propagation (Zhu & Ghahramani, )
updates $\widehat{\mathbf{C}}$ and constrains the labels of labeled data to $\mathbf{C}_{l}$:

$$ $\widehat{\mathbf{C}}_{t+1}\leftarrow\mathbf{P}^{\top}\widehat{\mathbf{C}}_{t} \quad\textrm{and}\quad[\widehat{\mathbf{C}}_{t+1}]_{i:}\leftarrow[\mathbf{C}_{ l}]_{i:},$ (7) $$

for $i\in[n_{l}]$ at Iteration $t$.
On the other hand,
label spreading (Zhou et al., )
propagates $\widehat{\mathbf{C}}$ by allowing a change of the labels of labeled data with a clamping factor $\alpha\in(0,1)$:

$$ $\widehat{\mathbf{C}}_{t+1}\leftarrow\alpha\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D }^{-1/2}\widehat{\mathbf{C}}_{t}+(1-\alpha)\widehat{\mathbf{C}}_{0},$ (8) $$

where $\widehat{\mathbf{C}}_{0}$ is initial propagated labels,
which are defined in Line 1 of Algorithm 2.
Note that $\mathbf{D}^{-1/2}\mathbf{W}\mathbf{D}^{-1/2}$ can be pre-computed before the loop defined from Lines 4 to 7 of Algorithm 2.

By the nature of transductive setting,
it only predicts the labels of particular data using the known data (Gammerman et al., ),
which implies that it cannot estimate a categorical distribution of unseen data.
To enable it,
given unseen $\mathbf{x}$,
we define an inductive model with $\widehat{\mathbf{C}}$:

$$ $\widehat{c}_{i}=\frac{\mathbf{w}^{\top}[\widehat{\mathbf{C}}]_{:i}}{\sum_{j=1} ^{c}\mathbf{w}^{\top}[\widehat{\mathbf{C}}]_{:j}},$ (9) $$

for $i\in[2]$,
where $\mathbf{w}\in\mathbb{R}^{n_{l}+n_{u}}$ is similarities of $\mathbf{x}$ and $\mathbf{X}$
by (5).
$[\widehat{\mathbf{C}}]_{:i}$ denotes $i$th column of $\widehat{\mathbf{C}}$.
This inductive model is better than
or equivalent to other classifiers without unlabeled data in certain circumstances;
its analysis is provided in Section C.

### 4.2 Unlabeled Point Sampling

As described above,
if unlabeled points are not available,
we need to generate unlabeled points
under a transductive learning scheme.
However, it is a challenging problem
unless we know a landscape of $\pi_{\mathbf{C}}$ adequately.
Many studies (Seeger, ; Rigollet, ; Singh et al., ; Ben-David et al., ; Carmon et al., ; Wei et al., ; Zhang et al., )
investigate how unlabeled data can affect a model
and whether unlabeled data helps improve the model or not.

In order to make use of the theoretical findings of previous literature,
we define a cluster assumption:

###### Assumption 4.1 (Cluster assumption in (Seeger, 2000 ) ) .

Two points $\mathbf{x}_{i},\mathbf{x}_{j}\in\mathcal{X}$ should belong to the same label if there is a path between $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ which passes only through regions of relatively high $P(X)$,
where $P$ is a distribution over a random variable $X\in\mathcal{X}$.

Figure: (a) Beale
Refer to caption: x21.png

Figure: (a) Beale
Refer to caption: x25.png

By Assumption 4.1,
the idea of clustering on the Euclidean space
or spectral clustering on a graph
can be naturally applied in semi-supervised learning (Seeger, ; Joachims, ),
which is not the scope of this work.

To build DRE-BO-SSL associated with Assumption 4.1,
we sample unlabeled data points
from the truncated multivariate normal distribution
so that each sample is in a compact $\mathcal{X}$:

$$ $f(\mathbf{z})=\frac{\exp(-\frac{1}{2}\mathbf{z}^{\top}\mathbf{z})\mathbb{I}( \mathbf{l}\leq\mathbf{A}\mathbf{z}\leq\mathbf{u})}{P(\mathbf{l}\leq\mathbf{A}Z \leq\mathbf{u})},$ (10) $$

where $\mathbf{l},\mathbf{u}\in\mathbb{R}^{d}$ are lower and upper bounds,
$\boldsymbol{\Sigma}=\mathbf{A}\mathbf{A}^{\top}$ is a covariance matrix,
$\mathbb{I}$ is an indicator function,
and $Z\sim\mathcal{N}(\boldsymbol{0},\mathbf{I}_{d})$ is a random variable.
It is challenging to calculate a denominator of (10),
$P(\mathbf{l}\leq\mathbf{A}^{\top}Z\leq\mathbf{u})$,
and simulate from $f(\mathbf{z})$
because an integration of the denominator and an accept-reject sampling strategy from $f(\mathbf{z})$ are cumbersome in this multi-dimensional case.
To effectively sample from the truncated multivariate normal distribution,
we adopt the minimax tilting method (Botev, ).
Compared to the method by Genz (),
it yields a high acceptance rate and accurate sampling.
In this paper $\boldsymbol{\Sigma}$ is set as an identity matrix, and $\mathbf{l}$ and $\mathbf{u}$ are determined by a search space.
We will provide more detailed discussion on point sampling in Sections 6 and F.

###### Assumption 4.1 (Cluster assumption in (Seeger, 2000 ) ) .

## 5 Experiments

We test DRE-BO-SSL and baseline methods
in the following optimization problems:
synthetic benchmarks for a scenario with unlabeled point sampling,
and synthetic benchmarks,
Tabular Benchmarks (Klein & Hutter, ),
NATS-Bench (Dong et al., ),
and minimum multi-digit MNIST search
for a scenario with a fixed-size pool.
Note that Tabular Benchmarks, NATS-Bench, and minimum multi-digit MNIST search are defined with a fixed number of possible solution candidates, which implies that they are considered as combinatorial optimization problems.
By following the previous work (Tiao et al., ; Song et al., ),
we set a threshold ratio as $\zeta=0.33$
for all experiments;
the effects of a threshold ratio $\zeta$ are analyzed in Sections 6 and H.
To solve (4),
we use L-BFGS-B (Byrd et al., ) with 1000 different initializations.
All experiments are repeated 20 times with 20 fixed random seeds
and the sample mean and the standard error of the sample mean are reported.
Other missing details including the details of the competitors of our methods are presented in Section D.

Figure: (a) Sampling, LP
Refer to caption: x29.png

### 5.1 A Scenario with Unlabeled Point Sampling

##### Synthetic Benchmarks.

We run several synthetic functions
for our methods and the baseline methods.
For unlabeled point sampling,
we sample 100 points from $\mathcal{N}(\mathbf{x}_{1},\mathbf{I}_{d}),\ldots,\mathcal{N}(\mathbf{x}_{n_{l
}},\mathbf{I}_{d})$,
where $\lfloor n_{u}/n_{l}\rfloor$ or $\lfloor n_{u}/n_{l}\rfloor+1$ points are sampled from each truncated distribution, so that $n_{u}$ points are sampled in total.
As shown in Figure 2,
our methods outperform the baseline methods
incorporating labeled data with unlabeled points.
Interestingly,
out methods beat GP-based Bayesian optimization.
It implies that ours can fairly balance exploration and exploitation.
Furthermore,
we present the results of learning $\beta$ in Figure 4,
where $\beta$ is adaptively selected by (6) every iteration.

Figure: (a) Naval
Refer to caption: x33.png

Figure: (a) CIFAR-10
Refer to caption: x36.png

### 5.2 Scenarios with Fixed-Size Pools

##### Synthetic Benchmarks.

Several synthetic benchmark functions are tested
for our methods and the baseline methods.
To generate a fixed-size pool for each benchmark, we uniformly sample 1000 points from a bounded search space before an optimization round is started.
As presented in Figure 3,
our methods perform better than the baseline methods.
It implies that the use of unlabeled data helps improve optimization performance.
Also, the results of learning $\beta$ are demonstrated in Figure 4.
Learned $\beta$ is likely to converge to some value
as iterations proceed according to the results.

##### Tabular Benchmarks.

Comparisons of our methods and the existing methods are carried out in these hyperparameter optimization benchmarks (Klein & Hutter, ),
as reported in Figure 5.
We can benchmark a variety of machine learning models, which are defined with specific hyperparameters and trained on one of four datasets: naval propulsion,
parkinsons telemonitoring,
and slice localization.
There exist 62,208 models, which are used as a pool in this paper, for each dataset.
Our algorithms show superior performance compared to other approaches.
Similar to the synthetic functions,
we argue that the adoption of a predefined pool leverages its performance.
In some cases, GP-based Bayesian optimization is better than our methods.

##### NATS-Bench.

NATS-Bench (Dong et al., ),
which is the up-to-date version of NAS-Bench-201 (Dong & Yang, ),
is used to test our methods and the baseline methods.
NATS-Bench is a neural architecture search benchmark
with three popular datasets: CIFAR-10, CIFAR-100, and ImageNet-16-120,
and it has 32,768 architectures, i.e., a fixed-size pool in this paper,
for each dataset.
Similar to the experiments mentioned above,
our methods work well in three datasets,
compared to the existing methods;
see Figure 6 for the results.

Figure: (a) Multi-digit MNIST
Refer to caption: x39.png

##### 64D Minimum Multi-Digit MNIST Search.

This task, which is proposed in this work, is to find a minimum multi-digit number,
where a fixed number of multi-digit MNIST images are given.
As visualized in Figure 7,
three random images in the MNIST dataset (LeCun et al., )
are concatenated.
Eventually, “000” and “999” are global minimum and global maximum, respectively.
Since inputs are images and each concatenated image consists of three different digit images,
this high-dimensional optimization problem is challenging.
The size of a fixed-size pool is 80,000.
As shown in Figure 7,
our methods show satisfactory performance compared to other baseline methods.

## 6 Discussion

We discuss interesting topics on our methods and the properties of DRE-BO-SSL.
Moreover, we provide more thorough discussion, limitations,
and broader impacts in the appendices.

##### Effects of the Number of Points and Sampling Distributions for Unlabeled Points.

We choose a distribution for unlabeled point sampling as the truncated multivariate normal distribution in order to satisfy the cluster assumption.
To analyze our algorithm thoroughly,
we demonstrate the effects of the number of sampled points and sampling distributions for unlabeled points in Section F,
varying the number of unlabeled points
and utilizing diverse sampling distributions,
i.e., uniform distributions, Halton sequences (Halton, ), and Sobol’ sequences (Sobol’, ).

Figure: (a) Beale, LP
Refer to caption: x41.png

##### Effects of Pool Sampling.

Because the computational complexity of label propagation and label spreading depends on a pool size,
we need to reduce a pool size appropriately in order to speed up the algorithms.
Therefore,
we uniformly sample a subset of the fixed-size set, which is used as unlabeled points.
Figure 8 reports elapsed times over subset sizes for pool sampling.
Larger subsets make the framework slower as expected.
More detailed analysis on the effects of pool sampling is demonstrated in Section G.

##### Effects of Threshold Ratios.

We study the effects of a threshold ratio $\zeta$
in order to understand how we can choose $\zeta$.
As shown in Figure 15,
both small $\zeta$ and large $\zeta$ generally represent worse performance;
see the results with $\zeta=0.01$ and $\zeta=0.8$.
While it has to depend on optimization problems,
$\zeta=0.33$ and $\zeta=0.5$ are generally appropriate choices according to this analysis.
The details of this study can be found in Section H and Figure 15.

##### Flat Landscape of Class Probabilities over Inputs.

Regardless of the use of either supervised or semi-supervised classifier,
a flat landscape of class probabilities can occur in the framework of DRE-based Bayesian optimization.
To overcome the issue of optimizing a flat landscape,
we add a simple heuristic
of selecting a random query point from points with identical highest class probabilities if the landscape is flat,
as described in Section 4.
Since off-the-shelf local optimization methods
struggle to optimize a flat landscape,
this simple heuristic is effective.

##### General Framework of DRE-BO-SSL.

As a future direction,
we expect that a general framework of DRE-BO-SSL can be defined,
which is similar to a likelihood-free approach by Song et al. ().
However, it is difficult to define an utility function involved in both labeled and unlabeled data.
For example, if we assume that
an utility function is $u(y;y^{\dagger})=\max(y^{\dagger}-y,0)$,
$y$ for an unlabeled data point is unknown.
Although it depends on the form of utility function,
we need to define $y$ of an unlabeled data point
by utilizing the information we have
if the utility function is related to $y$.

## 7 Conclusion

In this paper we have proposed a DRE-based Bayesian optimization
framework with semi-supervised learning, named DRE-BO-SSL.
Unlike the existing work such as BORE and LFBO,
our methods make use of semi-supervised classifiers
where unlabeled data points are sampled or given.
The superior results by our methods and the thorough analyses on the characteristics of DRE-BO-SSL exhibit the validity of our proposed algorithms.

#### Acknowledgments

This research was supported in part by the University of Pittsburgh Center for Research Computing through the resources provided. Specifically, this work used the H2P cluster, which is supported by NSF award number OAC-2117681.

## Appendix A Additional Comparisons of BORE and LFBO

Figure: (a) Random forests, BORE, Iterations 1 to 5
Refer to caption: x49.png

In addition to Figure 1,
we include additional comparisons of BORE and LFBO
by random forests (Breiman, ),
gradient boosting (Friedman, ),
and XGBoost (Chen & Guestrin, ) for the Branin function.
For Figures 1 and 9,
we use $\zeta=0.33$ and $\beta=0.5$.

## Appendix B Details of DRE-BO-SSL

Figure: Algorithm 2 Labeling Unlabeled Data

Algorithm 2 describes a procedure to label unlabeled data points;
see the main article for the details of DRE-BO-SSL.

## Appendix C Analysis of DRE-BO-SSL

Under the cluster assumption, i.e., Assumption 4.1,
a margin $\gamma$ is defined as a minimum distance between two decision boundaries.

###### Definition C.1 .

Let a compact connected decision set be $\mathcal{C}_{i}\subseteq\mathcal{X}$ for $i\in\{0,1\}$ and a boundary subset, i.e., a set of boundary points, of a compact connected set $\mathcal{S}$ be $\partial\mathcal{S}$. A margin $\gamma$ is defined as

$$ $\gamma=(2\mathbb{I}(\mathcal{C}_{1}\cap\mathcal{C}_{2}=\emptyset)-1)\min_{ \mathbf{x}_{1}\in\partial\mathcal{C}_{1}\backslash\partial\mathcal{X},\mathbf{ x}_{2}\in\partial\mathcal{C}_{2}\backslash\partial\mathcal{X}}\|\mathbf{x}_{1} -\mathbf{x}_{2}\|_{2}.$ (11) $$

Using Definition C.1,
we claim that a semi-supervised classifier
in DRE-BO-SSL can mitigate the over-exploitation problem presented in Section 1.1,
because it can expand a decision set $\mathcal{C}_{1}$ for Class 1
by reducing $\gamma$ with unlabeled data.
However, we need to verify if a large decision set
is derived from the characteristics of non-parametric classifiers,
since a semi-supervised classifier we use is converted to the Nadaraya-Watson non-parametric model (Nadaraya, ; Watson, ) without unlabeled data.
As shown in Figure 12,
there is no strong relationship between the performance of
semi-supervised classifiers without unlabeled data,
i.e., the Nadaraya-Watson estimator,
and one of semi-supervised classifiers with unlabeled data.
It implies that configuration selection for a semi-supervised classifier is dependent on a class of objective function,
and the presence of unlabeled data is likely to be effective
for alleviating the over-exploitation problem.

Singh et al. () provide a sample error bound of supervised and semi-supervised
learners, related to $\gamma$, $n_{l}$, $n_{u}$, and $d$.
This work proves that
a semi-supervised learner can be better than any supervised learners,
by assuming that $n_{u}\gg n_{l}$ and access to perfect knowledge of decision sets.
However,
these theoretical results cannot be directly applied in our sequential problem
because this work assumes that both labeled and unlabeled data points are independent and identically distributed.
Nevertheless,
these results can hint a theoretical guarantee on better performance of semi-supervised classifiers with unlabeled data points.
Further analysis for the circumstances of Bayesian optimization is left for future work.

###### Definition C.1 .

## Appendix D Experiment Details

Here we present the missing details of the experiments shown in the main part.

To carry out the experiments in our work,
we use dozens of commercial Intel and AMD CPUs
such as Intel Xeon Gold 6126 and AMD EPYC 7302.
For the experiments on minimum multi-digit MNIST search,
the NVIDIA GeForce RTX 3090 GPU is used.

To minimize (6) for finding an adequate $\beta$ of label propagation and label spreading,
we use L-BFGS-B with a single initialization,
which is implemented in SciPy (Virtanen et al., ),
for all the experiments in Figures 2,
3,
5, 6,
and 7.
For the other empirical analyses,
we set $\beta$ as a specific fixed value;
see the corresponding sections for the details.

To reduce the computational complexity of DRE-BO-SSL for a scenario with a fixed-size pool,
we randomly sample 2,000 unlabeled points from the predefined pool for all experiments excluding synthetic benchmark functions.
More thorough analysis can be found in Section G.

To compare baseline methods with our methods,
we assess optimization algorithms using a simple regret:

$$ $\textrm{simple regret}(f(\mathbf{x}_{1}),\ldots,f(\mathbf{x}_{t}),f(\mathbf{x} ^{*}))=\min_{i=1}^{t}f(\mathbf{x}_{i})-f(\mathbf{x}^{*}),$ (12) $$

where $\mathbf{x}^{*}$ is a global optimum.

Our proposed methods and baseline methods are implemented with scikit-learn (Pedregosa et al., ),
PyTorch (Paszke et al., ),
NumPy (Harris et al., ),
SciPy (Virtanen et al., ),
XGBoost (Chen & Guestrin, ),
and BayesO (Kim & Choi, ).
Scikit-learn and SciPy are under the BSD 3-Clause license,
NumPy is under the modified BSD license,
XGBoost is under the Apache 2.0 license,
and BayesO is under the MIT license.
On the other hand,
PyTorch is under its own license;
refer to its repository for the license.

### D.1 Details of Baseline Methods

As the competitors of our method,
we test the following baseline methods:

- •
Gaussian process, EI and UCB: It is a Bayesian optimization strategy, which is defined with GP regression with the Matérn 5/2 kernel (Rasmussen & Williams, ). Expected improvement (Jones et al., ) and GP-UCB (Srinivas et al., ) are used as acquisition functions.
- •
Random forest, BORE and LFBO: These are BORE and LFBO that employ random forests (Breiman, ) with 1000 decision trees. Minimum samples to split are set to 2 for these baselines.
- •
Gradient boosting, BORE and LFBO: These methods are BORE and LFBO with gradient boosting classifiers (Friedman, ) with 100 decision trees. Learning rate for the classifier is set to 0.3.
- •
XGBoost, BORE and LFBO: Similar to gradient boosting, BORE and LFBO with XGBoost have 100 decision trees as base learners with learning rate of 0.3.
- •
MLP, BORE and LFBO: These methods are built with two-layer fully-connected networks. The detail of the multi-layer perceptron is described as follows.

The architecture of a multi-layer perceptron is

- First layer: fully-connected, input dimensionality $d$, output dimensionality $32$, ReLU;
- Second layer: fully-connected, input dimensionality $32$, output dimensionality $1$, Logistic,

where $d$ is the dimensionality of the problem we solve.

Note that most configurations for the baseline methods
follow the configurations described in the work (Song et al., ).

### D.2 Details of Synthetic Benchmarks

Here we describe the details of synthetic benchmarks.

##### Beale Function.

This function is defined as follows:

$$ $f(\mathbf{x})=(1.5-x_{1}+x_{1}x_{2})^{2}+(2.25-x_{1}+x_{1}x_{2}^{2})^{2}+(2.62 5-x_{1}+x_{1}x_{2}^{3})^{2},$ (13) $$

where $\mathbf{x}=[x_{1},x_{2}]\in[-4.5,4.5]^{2}$.

##### Branin Function.

It is defined as follows:

$$ $f(\mathbf{x})=\left(x_{2}-(5.1/4\pi^{2})x_{1}^{2}+(5/\pi)x_{1}-6\right)^{2}+10 \left(1-(1/8\pi)\right)\cos(x_{1})+10,$ (14) $$

where $\mathbf{x}=[x_{1},x_{2}]\in[[-5,10],[0,15]]$.

##### Bukin6 Function.

This benchmark is given by the following:

$$ $f(\mathbf{x})=100\sqrt{|x_{2}-0.01x_{1}^{2}|}+0.01|x_{1}+10|,$ (15) $$

where $\mathbf{x}=[x_{1},x_{2}]\in[[-15,-5],[-3,3]]$.

##### Six-Hump Camel Function.

It is given by the following:

$$ $f(\mathbf{x})=\left(4-2.1x_{1}^{2}+x_{1}^{4}/3\right)x_{1}^{2}+x_{1}x_{2}+(-4+ 4x_{2}^{2})x_{2}^{2},$ (16) $$

where $\mathbf{x}=[x_{1},x_{2}]\in[[-3,3],[-2,2]]$.

### D.3 Details of Tabular Benchmarks

**Table 1: Search space for Tabular Benchmarks. “tanh” and “relu” represent hyperbolic tangent and ReLU, respectively.**
| Hyperparameter | Possible Values |
| --- | --- |
| The number of units for 1st layer | {16, 32, 64, 128, 256, 512} |
| The number of units for 2nd layer | {16, 32, 64, 128, 256, 512} |
| Dropout rate for 1st layer | {0.0, 0.3, 0.6} |
| Dropout rate for 2nd layer | {0.0, 0.3, 0.6} |
| Activation function for 1st layer | {“tanh”, “relu”} |
| Activation function for 2nd layer | {“tanh”, “relu”} |
| Initial learning rate | {$5\times 10^{-4}$, $1\times 10^{-3}$, $5\times 10^{-3}$, $1\times 10^{-2}$, $5\times 10^{-2}$, $1\times 10^{-1}$} |
| Learning rate scheduling | {“cosine”, “constant”} |
| Batch size | {8, 16, 32, 64} |

The search space of Tabular Benchmarks (Klein & Hutter, )
is described in Table 1.
To handle categorical and discrete variables,
we treat them as integer variables by following the previous literature (Garrido-Merchán & Hernández-Lobato, ).

### D.4 Details of NATS-Bench

Figure: Figure 10: Neural network architecture in NATS-Bench. Orange blocks are optimized.
Refer to caption: x79.png

**Table 2: Search space for NATS-Bench. There exist $8^{5}=$ 32,768 models.**
| Hyperparameter | Possible Values |
| --- | --- |
| Output channels of 1st convolutional layer | {8, 16, 24, 32, 40, 48, 56, 64} |
| Output channels of 1st cell stage | {8, 16, 24, 32, 40, 48, 56, 64} |
| Output channels of 1st residual block | {8, 16, 24, 32, 40, 48, 56, 64} |
| Output channels of 2nd cell stage | {8, 16, 24, 32, 40, 48, 56, 64} |
| Output channels of 2nd residual block | {8, 16, 24, 32, 40, 48, 56, 64} |

We describe the search space for NATS-Bench (Dong et al., )
in Figure 10
and Table 2.

### D.5 Details of Minimum Multi-Digit MNIST Search

Since multi-digit MNIST, which is composed of images of size $(28,84)$, is high-dimensional,
some of the methods used in this work, e.g., methods with random forests, gradient boosting, and XGBoost,
struggle to process such data.
Therefore, we embed an original image to a lower-dimensional vector using an auxiliary convolutional neural network.
The convolutional neural network is trained to classify a three-digit image to one of labels from “000” to “999,”
with the following architecture:

- First layer: convolutional, input channel $1$, output channel $8$, kernel size $3\times 3$, padding 1, ReLU, max-pooling $2\times 2$;
- Second layer: convolutional, input channel $8$, output channel $16$, kernel size $3\times 3$, padding 1, ReLU, max-pooling $2\times 2$;
- Third layer: convolutional, input channel $16$, output channel $32$, kernel size $3\times 3$, padding 1, ReLU, max-pooling $2\times 2$;
- Fourth layer: fully-connected, input dimensionality $960$, output dimensionality $128$, ReLU;
- Fifth layer: fully-connected, input dimensionality $128$, output dimensionality $64$, ReLU;
- Sixth layer: fully-connected, input dimensionality $64$, output dimensionality $1000$, Softmax.

The Adam optimizer (Kingma & Ba, ) with learning rate $1\times 10^{-3}$ is used to train the network for 100 epochs.
To train and test the model fairly,
we create a training dataset of 440,000 three-digit images, a validation dataset of 40,000 three-digit images, and a test dataset of 80,000 three-digit images
using a training dataset of 55,000 single-digit images, a validation dataset of 5,000 single-digit images, and a test dataset of 10,000 single-digit images in the original MNIST dataset (LeCun et al., ).
For example, supposing that a test dataset has 1,000 single-digit images per class – it is not true for the MNIST dataset, but it is assumed for explanation – and we would like to generate a three-digit image “753,”
$10^{9}$ combinations for “753” can be created.
We therefore randomly sample a fixed number of three-digit images from a vast number of possible combinations.
In addition, an early stopping technique is utilized
by comparing the current validation loss to the average of validation losses for the recent five epochs.
Eventually,
our network achieves $99.6\%$ in the training dataset,
$97.0\%$ in the validation dataset,
and $96.9\%$ in the test dataset.

To construct a fixed-size pool,
we use 80,000 embeddings of dimensionality 64,
which are derived from the outputs of the fifth layer without ReLU, by passing the test dataset of three-digit images through the network.

## Appendix E Discussion on a Free Parameter in Label Propagation and Label Spreading

Figure: (a) Beale, LP
Refer to caption: x80.png

In the Bayesian optimization process of DRE-BO-SSL, a free parameter $\beta$ in label propagation and label spreading is learned every iteration by minimizing (6);
see Figure 4 for the results on learned $\beta$.
Furthermore,
to show the effects of $\beta$,
we empirically analyze $\beta$
as depicted in Figure 11.
We sample 1,000 unlabeled points and use all of them as unlabeled points without pool sampling.
For the cases of four benchmark functions,
higher $\beta$ tends to show better performance
than lower $\beta$.
These results considerably correspond with the results in Figure 4.

## Appendix F Discussion on Unlabeled Point Sampling

Figure: (a) Beale, LP
Refer to caption: x88.png

Figure: (a) Beale, LP
Refer to caption: x96.png

We design two studies
to analyze the effects of the number of unlabeled points $n_{u}$ and sampling strategies in a process of unlabeled point sampling,
where unlabeled points are not provided
and $\beta=0.5$ is given.

For the first study,
we conduct five settings,
no unlabeled data, which implies that transductive learning is not used,
and $n_{u}=10,100,1000,10000$.
Interestingly,
the tendency of the number of unlabeled points
are unclear as presented in Figure 12.
It implies that a setting for the number of unlabeled data points depend on the characteristics of benchmark functions,
which is common in Bayesian optimization and black-box optimization.
Besides,
$\gamma$ is different across benchmarks and iterations
and it lets optimization results sensitive to $n_{u}$.
Therefore, we cannot determine a suitable setting without access to a black-box function of interest.

As another elaborate study,
we test the effects of sampling strategies.
Four strategies,
the truncated multivariate normal distributions,
uniform distributions,
Halton sequences (Halton, ),
and Sobol’ sequences (Sobol’, ),
are compared.
As depicted in Figure 13,
the normal distribution is better than
the other sampling methods in four cases
and shows robust performance in most of the cases,
but it is not always the best.
Similar to the previous study on the effects of $n_{u}$,
we presume that it is also affected by $\gamma$,
which is hard to define in practice.

## Appendix G Discussion on Pool Sampling

Figure: (a) Beale, LP
Refer to caption: x104.png

To see the impact of an additional hyperparameter,
i.e., the size of a subset of the original pool,
which is introduced to speed up semi-supervised learning algorithms,
we demonstrate numerical analysis on pool sampling
where the size of a predefined pool is 4,000
and $\beta=0.5$ is given.
Based on Figures 8 and 14,
we can accelerate our framework without significant performance loss.

## Appendix H Discussion on a Threshold Ratio

Figure: (a) Beale, LP
Refer to caption: x112.png

Figure 15 demonstrates the effects of a threshold ratio $\zeta$,
where we use $\beta=0.5$.
It follows the setting described in Section E.
As presented in Figure 15,
a smaller $\zeta$, for example, $\zeta=0.01$ or $\zeta=0.1$ tends to show worse performance than a larger $\zeta$,
which implies that the over-exploitation is not due to conservative $y^{\dagger}$.
Interestingly, the results with $\zeta=0.8$ also generally under-perform.
We presume that it is basically due to over-exploration.

## Appendix I Limitations

As discussed above, our algorithms slow down if a pool size is significantly large.
As presented in Figure 8,
elapsed times are certainly dependent on subset sizes.
To tackle this issue, we suggest a method to randomly select a subset of the pool,
but a more sophisticated subsampling method can be devised for our framework.
In particular,
we can leverage the impacts of the subset of the pool
by utilizing the geometric information of unlabeled data points.

## Appendix J Impact Statement

Our work does not have any direct negative societal impacts
because it proposes a new Bayesian optimization method to optimize a black-box function.
However, in the sense of optimization,
this line of research can be used in optimizing any objectives including unethical optimization tasks.

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 3
presentation: 3
questions: None.
soundness: 2
strengths: - Bayesian optimization based on a standard Gaussian Process model incurs high computational costs when the sample size is large. The density-ratio-based approach, as discussed in works such as [Bergstra et al. (2011)], [Tiao et al. (2021)], and [Song et al. (2022)], could serve as an effective alternative. In this sense, the topic addressed in this paper is important.

- The authors' approach of identifying issues based on experimental observations, such as those in Figure 1, and formulating the problem generally to address these issues is practical, as it reflects real-world challenges in data analysis.

- The paper provides a clear and concise overview of existing methods such as density-ratio-based Bayesian optimization and label propagation, making it accessible even for readers who are not well-versed in this field.
summary: This paper proposes the DRE-BO-SSL method, which introduces the concept of semi-supervised learning to address the over-confidence (over-exploitation) issue observed in density-ratio-based Bayesian optimization problems. In general Bayesian optimization, Bayesian regression models such as Gaussian Process models are often used; however, this study focuses on the density-ratio-based approach discussed in works such as [Bergstra et al. (2011)], [Tiao et al. (2021)], and [Song et al. (2022)]. The main contribution of the proposed method is the incorporation of traditional semi-supervised learning approaches, such as label propagation and label spreading, into density-ratio-based Bayesian optimization. According to the authors, this allows for resolving the over-confidence (over-exploitation) problem in density-ratio-based BO.
weaknesses: - This study aims to tackle the over-confidence and over-exploitation problem in density-ratio-based Bayesian optimization. However, it remains unclear why a semi-supervised learning approach based on label propagation would effectively address this issue. Similarly, the rationale behind using the sampling method in Equation (10) for unlabeled point sampling was not clearly explained, making the motivation difficult to grasp. If the authors rely solely on experimental evaluations without clear explanations, presenting these findings at a top-tier conference like ICLR may be premature; more thorough discussions and theoretical analyses are needed.

- In my opinion, the proposed DRE-BO-SSL method lacks originality for top-tier conferences like ICLR, as it simply applies label propagation—traditional semi-supervised learning techniques—to existing density-ratio-based Bayesian optimization. Deeper considerations are necessary, such as whether other semi-supervised learning methods might prove ineffective or what outcomes might arise if a semi-supervised learning approach were applied to Gaussian Process-based Bayesian optimization.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: - How \zeta^-1 p(z=1|x)/(p(z=1|x) + p(z=0|x)) is derived from (2)?

- How the threshold for y is determined from zeta?

- In 64D MNIST, the authors mentioned that the problem is to find the 'minimum' multi-digit number. This means that there exists multiple global minimum? (i.e., all images with '000' are global minimum?)
soundness: 2
strengths: - To my knowledge, a combination of the density ratio based BO and SSL has not been widely studied.

- The paper is well-organized and easy to follow.
summary: The paper proposes semi-supervised learning (SSL) based Bayesian optimization (BO). The basic idea is to use label propagation (spreading) to utilize unlabeled points. The authors claim that SSL provides a better classification resulting from which a better solution should be obtained.
weaknesses: - The fundamental assumption of SSL is that p(X) provides some information about p(Y∣X) (since the unlabeled data are sampled from P(X)), which has been discussed in classical text such as [1]. However, there is no discussion or fundamental justification of the situations in BO where this hypothesis holds. In other words, the paper fails to show a rationale why SSL is effective for BO.

[1] Chapelle, et al., Semi-Supervised Learning, MIT Press, 2006.

- In fact, the relation between p(X) and p(Y|X) is highly unclear in the experimental settings, and therefore, it is unclear why SSL is effective. In the synthetic data, X is from uniform and nothing is related to Y. In tabular benchmark and NATS-Bench, the candidate points are uniform grid according to the tables in appendix. Therefore, it is quite unclear why unlabeled points is informative for applying SSL. In 64D MNIST, samples in the same three digits may consists of low-dimensional manifold. On the other hand, the number of three digits, the target to be optimized, would not continuous in the pixel space (e.g., 000 and 100 would be relatively close in the pixel space, but the value of y is largely different. In other words, proximity in X space is not fully informative about proximity in Y space). For me, validity as a BO benchmark problem of 64D MNIST is not clear.

- SSL methods used in the paper is most classical methods (proposed in 2002 and 2003), no more recent methods are mentioned in detail.

- How SSL avoids the overconfidence issue. Mathematical detailed mechanisms are not shown.

- It is unclear how the cluster assumption and f(z) is related. Since f(z) is (truncated) standard normal, the cluster structure should become quite simple and nothing is related to Y. Therefore, here again, I currently do not think f(z) satisfies the requirement of SSL.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: - \Sigma, upper/lower bounds u,l for the truncated normal are not properly defined. How should we set or estimate these values?
- How this particular way of sampling is related to the cluster assumption?
soundness: 3
strengths: The proposed method is novel and represents a good contribution to Density Ratio Estimation-based Bayesian Optimization (DRE-based BO). By using semi-supervised learning in DR-based BO to address the overconfidence issue, the authors offer a promising approach with nice empirical results. The concept of employing semi-supervised learning is intriguing and shows potential in solving the general overconfidence problem in DRE.
summary: The paper proposes a novel Bayesian optimization (BO) method called DRE-BO-SSL, which combines semi-supervised learning (SSL) with Density Ratio Estimation-based BO (DRE-BO). It addresses the common issue of overconfidence in classifiers used in DRE-based BO methods like BORE and LFBO, particularly when early-stage data is limited. By incorporating SSL techniques—specifically estimating pseudo-labels through label propagation and label spreading—the method refines class label predictions and improves classifier accuracy. This approach enhances the exploration-exploitation trade-off, mitigating the tendency to over-exploit due to overconfident classifiers.
Instead of fitting a regressor to observed data, DRE-BO-SSL uses a classifier to guide the search, computing the acquisition function in terms of class probability ratios. Comparative experiments on synthetic and real problems demonstrate that DRE-BO-SSL outperforms traditional Gaussian Process-based BO and recent density ratio-based approaches across a wide range of tasks. The empirical results show that integrating SSL techniques into DRE-based BO effectively improves performance by leveraging unsupervised data sampling to address overconfidence issues.
weaknesses: While the proposed method is novel, several significant issues need to be addressed:
- There is no clear explanation of how the overconfidence problem is resolved through the use of semi-supervised learning. Although Appendix C attempts to elucidate the reasoning or mechanism by which semi-supervised learning mitigates overconfidence, the explanation lacks clarity and fails to provide a compelling rationale. In fact, Figure 12 appears to indicate that unlabeled data may not be necessary, which contradicts the premise that semi-supervised learning is essential for addressing the overconfidence issue.

- As the authors themselves acknowledge, the proposed method does not offer theoretical guarantees within the context of Bayesian Optimization. This omission raises concerns about the method's validity and applicability.

These shortcomings suggest that the paper does not adequately justify the need for the proposed method, nor does it thoroughly explain how the method effectively addresses the identified problem. Addressing these issues would strengthen the contribution and impact of the work.

Another issue, rather minor compared to the above motivation issue, is that the presentation of the paper should be improved. For example, \zeta is used in the Introduction before it is properly defined in Section 3.

Meta-review: This paper presents a Bayesian Optimization (BO) method that integrates Semi-Supervised Learning (SSL) with Density Ratio Estimation (DRE)-based BO to address over-confidence issues in classifiers. By using SSL techniques like label propagation to refine class predictions, the method aims to improve exploration-exploitation balance. The paper has some strengths such as novel combination of DRE-based BO and SSL to address the over-confidence classifier problem. Furthermore, it shows competitive empirical performance against traditional BO methods. However, it also has some relevant weaknesses like lack of a theoretical justification. The paper does not convincingly explain why SSL resolves the over-confidence issues. Moreover, it has empirical limitations such as relevant experimental benchmarks, and some results suggest unlabeled data may not always be beneficial. The SSL methods used are outdated, with limited exploration of alternatives or modern approaches. The paper also has some presentation issues. Important details, such as thresholds and parameter definitions, are unclear. While the concept of integrating SSL into DRE-based BO is novel and shows some promise, the paper needs significant revisions to address theoretical gaps, improve clarity, and provide stronger empirical and methodological justifications.

Decision: Reject