High dimensional Bayesian Optimization via Condensing-Expansion Projection

## Abstract

Abstract In high-dimensional settings, Bayesian optimization (BO) can be expensive and infeasible. The random embedding Bayesian optimization algorithm is commonly used to address high-dimensional BO challenges. However, this method relies on the effective subspace assumption on the optimization problem’s objective function, which limits its applicability.
In this paper, we introduce Condensing-Expansion Projection Bayesian optimization (CEPBO), a novel random projection-based approach for high-dimensional BO that does not reply on the effective subspace assumption. The approach is both simple to implement and highly practical.
We present two algorithms based on different random projection matrices: the Gaussian projection matrix and the hashing projection matrix.
Experimental results demonstrate that both algorithms outperform existing random embedding-based algorithms in most cases, achieving superior performance on high-dimensional BO problems.
The code is available in https://anonymous.4open.science/r/CEPBO-14429 .

## 1 Introduction

For many optimization problems, the objective function $f$ lacks a closed-form expression, and gradient information is often unavailable, leading to what we are generally referred to as black-box functions [, , ].
Bayesian optimization (BO) is an efficient method for solving such optimization problems by modeling the unknown objective function through a probabilistic surrogate model, typically a Gaussian Process. The BO routine is a sequential search algorithm where each iteration involves estimating the surrogate model from available data and then maximizing an acquisition function to determine which point should be evaluated next.
As the input space dimension $D$ increases, typically $D\geq 10$, BO encounters the so-called ‘curse of dimensionality’ []. This phenomenon refers to the exponential increase in difficulty resulting from higher query complexity and the computational cost associated with calculating the acquisition function.

To address the issue, numerous studies have proposed high-dimensional BO algorithms [, , , , , ] that typically translate high-dimensional optimizations into low-dimensional ones by various techniques, and search the new point in the low-dimensional space.
However, these approaches can become inefficient when the maximum over the high-dimensional space cannot be well approximated by the maximum over the low-dimensional space.

In this paper, we introduce a novel search strategy in high-dimensional BO problems called the Condense-Expansion Projection (CEP) technique, which is both simple to implement and highly practical.
In each iteration of the sequential search, the CEP technique generates
a random projection matrix $\mathbf{A}\in\mathbb{R}^{d\times D}$, where $d\ll D$, to project the available data from the high-dimensional space to the low-dimensional embedding space by multiplying them with $\mathbf{A}$. It estimates the surrogate model and searches for the next point to evaluation in the low-dimensional embedding space. Subsequently, it projects the searched data point back to the high-dimensional space by multiplying it with $\mathbf{A}^{\top}$ for evaluation in the original space.

We utilize two distinct random projection matrices: the Gaussian projection matrix [] and the hashing projection matrix [, ], within the CEP technique,
resulting in the development of two algorithms, CEP-REMBO and CEP-HeSBO.
Our experimental results, comprising comprehensive simulation studies and analysis of four real-world datasets, demonstrate that both algorithms generally outperform existing random embedding-based algorithms, showcasting the superior performance of the CEP technique on high-dimensional BO problems.

## 2 Related Work

There is a substantial body of literature on high-dimensional BO.The most closely related approach is REMBO [] by fitting a Gaussian Process model in a low-dimensional embedding space obtained through a Gaussian random projection matrix. This approach has been further investigated by [, , , ] under various conditions.
[] proposed HeSBO that utilizes a hashing projection matrix.
However, these studies are based on the assumption of an effective subspace, where a small number of parameters have a significant impact on the objective function.
Similar to these studies, our approach evaluates the acquisition function over the embedding space. However, unlike these studies, our approach select the new point in the original space, implying that our approach does not relies on the effective space assumption. The second distinguishing aspect of our approach is that it generates a new random projection matrix in each iteration, thereby increasing the flexibility to accommodate the possibility that the global optimum may not be located in a single embedding space.

Besides the embedding approach, two other techniques warrant consideration: one based on the additive form of the objective function, and the other based on the dropout approach.
[] tackled the challenges in high-dimensional BO by assuming an additive structure for the function.
Other works along the line include GPs with an additive kernel [, ] or cylindrical kernels [].
However, this approach is limited by its reliance on the assumption of the additive form of the objective function.
[] applied the dropout technique into high-dimensional BO to alleviate reliance on assumptions regarding limited “active” features or the additive form of the objective function.
This method randomly selects subset of dimensions and optimizes variables only from these chosen dimensions via Bayesian optimization.
However, it necessitates “filling-in" the variables from the left-out dimensions.
The proposed “fill-in" strategy, which involves copying the value of variables from the best function value, may lead to being trapped in a local optimum, although the strategy is enhanced by mixing random values.

## 3 Method

### 3.1 Bayesian Optimization

We consider the optimization problem

$$ $\mathbf{x}^{*}=\arg\max\nolimits_{\mathbf{x}\in\mathcal{X}}f(\mathbf{x}),$ $$

where $f$ is a black-box function
and $\mathcal{X}\subset\mathbb{R}^{D}$ is some bounded set.
BO is a form of sequential model-based optimization, where we fit a surrogate model, typically a Gaussian Process (GP) model, for $f$ that is used to identify which parameters $\mathbf{x}$ should be evaluated next.
The GP surrogate model is $f\sim\mathcal{GP}\left(m(\cdot),k(\cdot,\cdot)\right)$, with a mean function $m(\cdot)$ and a kernel $k(\cdot,\cdot)$.
Under the GP prior, the posterior for the value of $f(\mathbf{x})$ at any point in the space is a normal distribution with closed-form mean and variance. Using that posterior, we
construct an acquisition function $\alpha(\mathbf{x})$ that specifies the utility of evaluating $f$ at $\mathbf{x}$, such as Expected Improvement [].
We find $\mathbf{x}_{\text{new}}=\arg\max\nolimits_{\mathbf{x}\in\mathcal{X}}\alpha(
\mathbf{x})$, and in the next iteration evaluate $f(\mathbf{x}_{\text{new}})$.
However, GPs are known to predict poorly for large dimension $D$ [], which prevents the use of standard BO in high dimensions.

### 3.2 Condensing-Expansion Projection

The framework of Condensing-Expansion Projection (CEP) is delineated through two essential projection procedures.

- •
Condensing Projection: transpose points from the original space into a reduced-dimensional embedding subspace, where the surrogate model is fitted from available data and the acquisition function is maximized to determine which point should be evaluated next.
- •
Expansion Projection: revert these points in the embedding subspace back to the original space, where the searched point is evaluated.

Figure: Figure 1: An illustration of CEP. The dimension of the original space is $D=3$, and the dimension of the embedding subspace is $d=2$. The five points in the orginal space is projected to the embedding subspace by Condensing Projection, then they are projected back to the original space by Expansion Projection. The optimal point (red dot) in the original space is still at the (approximately) optimal position after CEP.
Refer to caption: x1.png

Let us define an embedding subspace $\mathcal{Y}\subset\mathbb{R}^{d}$ of dimension $d$.
We generate a random projection matrix $\mathbf{A}\in\mathbb{R}^{d\times D}$.
Various methodologies exist for the construction of such a matrix, including the Gaussian random matrix, sparse random matrix [, ], and the Subsampled Randomized Hadamard Transform [].
In this paper, we utilize the Gaussian random matrix and the Hashing matrix.

Consider a point $\mathbf{x}\in\mathcal{X}$ within the original space $\mathcal{X}$.
In the condensing projection, we project $\mathbf{x}$ from the original space $\mathcal{X}$ to the embedding subspace $\mathcal{Y}$ by multiplying $\mathbf{x}$ with the matrix $\mathbf{A}$,
resulting in

$$ $\mathbf{y}=\mathbf{A}\mathbf{x}\in\mathcal{Y},$ $$

thereby reducing the dimension from $D$ in the original space to $d$ in the embedding subspace.
In the expansion projection, we project $\mathbf{y}$ back to $\mathcal{X}$ by multiplying $\mathbf{y}$ with the transposed matrix $\mathbf{A}^{\top}$, expressed as
as

$$ $\tilde{\mathbf{x}}=\mathbf{A}^{\top}\mathbf{y}=\mathbf{A}^{\top}\mathbf{A} \mathbf{x}.$ $$

This completes the Condensing-Expansion Projection,
which can be outlined as follows:
transforming a point from the original space to the embedding subspace and then restoring it back to the
original space, represented as

$$ $\mathbf{x}\rightarrow\mathbf{y}\rightarrow\tilde{\mathbf{x}}.$ $$

We outline an illustration in Figure1.

The CEP offers flexibility in selecting random projection matrix $\mathbf{A}$.
In this paper, we focus on two types: Gaussian random matrices
and Hashing random matrices.

###### Definition 1 .

(Gaussian Random Matrix)
Let $\mathbf{A}\in\mathbb{R}^{d\times D}$ be a random matrix with independent Gaussian entries.
For any $1\leq i\leq d$ and $1\leq j\leq D$, the element $a_{ij}$ defined
as

$$ $a_{ij}\sim\mathcal{N}\left(0,\frac{1}{d}\right).$ $$

###### Definition 2 .

(Hashing Random Matrix)
Let $\mathbf{A}\in\mathbb{R}^{d\times D}$ be a hashing random matrix.
Specifically,
(1) Each column of $\mathbf{A}$ has a single non-zero element that is selected at random. (2) This non-zero element has an equal probability $p=0.5$ of being either $+1$ or $-1$.

###### Theorem 1 .

Assume a matrix $\mathbf{A}$
satisfying Definition 1 or Definition 2,
it can be shown that

$$ $\mathbb{E}\left[\mathbf{A}^{\top}\mathbf{A}\right]=\mathbf{I}_{D}.$ $$

The proof of Theorem 1 is provided in the appendix 6.1.
Theorem 1 represents the isometry in expectation,
suggesting that the process of two projections, on average, preserves both the magnitude and direction of $\mathbf{x}$, thereby making the gap from $\tilde{\mathbf{x}}$ to $\mathbf{x}$ in the original space is zero on average.

Besides of the isometry in expectation, we also concern the concentration of $\tilde{\mathbf{x}}$ around the original point $\mathbf{x}$ in terms of the function $f$.
Assume that there exists a vector $\mathbf{g}\in\mathbb{R}^{D}$ such that, for $\mathbf{x}_{1},\mathbf{x}_{2}\in\mathcal{X}$ are within a neighborhood, i.e., $\mathbf{x}_{2}\in N_{\epsilon}(\mathbf{x}_{1})$ where $N_{\epsilon}(\mathbf{x}_{1})=\{\mathbf{x}\in\mathcal{X}:|\mathbf{x}-\mathbf{x}
_{1}|<\epsilon\}$, $|f(\mathbf{x}_{1})-f(\mathbf{x}_{2})|\leq|\mathbf{g}^{\top}(\mathbf{x}_{1}-
\mathbf{x}_{2})|$. Here $\mathbf{g}$ represents an upper bound on the rate of change of $f$ within the neighborhood.
Therefore the disparity between $f(\mathbf{x})$ and $f(\tilde{\mathbf{x}})$ can be bounded by $|\mathbf{g}^{\top}(\mathbf{x}_{1}-\mathbf{x}_{2})|$.
The following theorem provides the concentration of $\mathbf{g}^{\top}\tilde{\mathbf{x}}$ round $\mathbf{g}^{\top}\mathbf{x}$.

###### Theorem 2 .

(1) Assume a matrix $\mathbf{A}$
satisfying Definition 1,
then for any vector $\mathbf{x}\in\mathcal{X}$ and any vector $\mathbf{g}\in\mathbb{R}^{D}$, it holds that

$$ $\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x}- \mathbf{g}^{\top}\mathbf{x})^{2}\right]\leq\frac{3}{d}\|\mathbf{x}\|^{2}\| \mathbf{g}\|^{2}-\frac{1}{d}(\mathbf{g}^{\top}\mathbf{x})^{2}.$ $$

(2) Assume a matrix $\mathbf{A}$
satisfying Definition 2,
then for any vector $\mathbf{x}\in\mathcal{X}$ and any vector $\mathbf{g}\in\mathbb{R}^{D}$, it holds that

$$ $\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x}- \mathbf{g}^{\top}\mathbf{x})^{2}\right]\leq\frac{1}{d}\left(\|\mathbf{g}\|^{2} \|\mathbf{x}\|^{2}-\sum\limits_{i=1}^{D}x_{i}^{2}g_{i}^{2}\right).$ $$

The proof of Theorem 2 is provided in the appendix 6.2.
Theorem 2 states that the variance of $\mathbf{g}^{\top}\tilde{\mathbf{x}}$ with respect to $\mathbf{g}^{\top}\mathbf{x}$ diminishes as the dimension $d$ of the embedding subspace increases.
Hence, CEP can maintain the function in the original space well when $d$ is not small.

###### Definition 1 .

###### Definition 2 .

###### Theorem 1 .

###### Theorem 2 .

### 3.3 The CEPBO Algorithm

We employ Condensing-Expansion Projection in Bayesian Optimization, leading to the development of the Condensing-Expansion Projection Bayesian Optimization (CEPBO) algorithm.
In contrast to Random Embedding algorithms, sucha as REMBO[], HeSBO[] and ALEBO[], where a fixed projection matrix is employed,
the CEPBO algorithm dynamically generates a new projection matrix $\mathbf{A}_{t}$ during each iteration $t$.
Through Condensing Projection, which condenses available points from the original space to a new embedding subspace via multiplication with $\mathbf{A}_{t}$, CEPBO leverages past information to conduct BO within the embedding subspace. It then determines which point to evaluate next within this subspace.
Afterward, the selected point in the embedding subspace undergoes Expansion Projection, where it is projected back to the original space via multiplication with $\mathbf{A}_{t}^{\top}$. Subsequently, the objective function is evaluated at that point.
This approach bypasses the stringent assumption associated with effective dimension by facilitating the projection of a new embedding subspace with each search iteration.
This adaptability acknowledges the possibility that the global optimum may not be confined to a single search.

The detailed procedural flow of the algorithm is outlined in Algorithm1.
By using different random projection matrices at line 4 of the Algorithm1, we derive two algorithms: CEP-REMBO and CEP-HeSBO. These can be regarded as enhanced versions of REMBO and HeSBO, respectively.

Condense original space into the embedding subspace.
The core concept of employing Condensing Projection entails the creation of a new subspace $\mathcal{Y}$ with each iteration, where BO is subsequently performed.
However, as the historical trajectories remains preserved within the original space $\mathcal{X}$, the newly formed subspace must be equipped with the requisite information to enable effective BO.
To tackle this issue, the primary objective of Condensing Projection is to transfer the historical trajectories from the original space $\mathcal{X}$ into an embedding subspace $\mathcal{Y}$, thereby furnishing
the embedding subspace $\mathcal{Y}$ with the necessary information to facilitate BO.
At the current iteration $t$, let $\mathcal{D}_{t-1}$ represent the trajectories in the original space $\mathcal{X}$, given by:
$\mathcal{D}_{t-1}=\{(\mathbf{x}_{1},f(\mathbf{x}_{1})),(\mathbf{x}_{2},f(
\mathbf{x}_{2})),\ldots,(\mathbf{x}_{t-1},f(\mathbf{x}_{t-1}))\}.$
During this iteration, a new projection matrix $\mathbf{A}_{t}$ of dimensions $\mathbb{R}^{d\times D}$ is sampled.
This matrix serves as projecting the historical point from the original space $\mathcal{X}$ into a newly formed embedding subspace $\mathcal{Y}_{t}$:
$\mathcal{D}_{t-1}^{y}=\{(\mathbf{A}_{t}\mathbf{x}_{1},f(\mathbf{x}_{1})),(
\mathbf{A}_{t}\mathbf{x}_{2},f(\mathbf{x}_{2})),\cdots,(\mathbf{A}_{t}\mathbf{
x}_{t-1},f(\mathbf{x}_{t-1}))\}.$

Optimize over the embedding subspace.
The objective $f$ is fitted by a Gaussian Process model over the embedding subspace $\mathcal{Y}_{t}$:

$$ $f(\mathbf{x})\approx\mathcal{GP}\left(m(\mathbf{A}_{t}\mathbf{x}),k(\mathbf{A} _{t}\mathbf{x},\mathbf{A}_{t}\mathbf{x})\right).$ $$

Within the embedding subspace $\mathcal{Y}_{t}$, the dataset $\mathcal{D}_{t-1}^{y}$ informs the estimation of the hyperparameters $\theta_{t}$ for the Gaussian process, and the posterior probability of the Gaussian process is computed.
The acquisition function $\alpha$ (such as Expected Improvement) identifies the embedding subspace’s optimal point $\mathbf{y}_{t}^{*}$ within the embedding subspace, which is represented by the equation
$\mathbf{y}_{t}^{*}=\underset{\mathbf{y}\in\mathcal{Y}_{t}}{\arg\max}\ \alpha(
\mathbf{y}\,|\,\mathcal{D}_{t-1}^{y}).$

Project back and evaluate in the original space.
After searching the optimal point with the acquisition function, we need to project this point back to the original space $\mathcal{X}$ for objective function evaluation. Subsequently, we add this point to the historical trajectories.
To be more specific, we use the transpose projection matrix $\mathbf{A}_{t}$ to map the optimal point $\mathbf{y}_{t}^{*}$ from the embedding subspace back
to $\mathcal{X}$ by applying its transpose $\mathbf{A}_{t}^{\top}$, expressed as:
$\mathbf{x}_{t}^{*}=\mathbf{A}_{t}^{\top}\mathbf{y}_{t}^{*}.$
Subsequently, we evaluate the objective function at $\mathbf{x}_{t}^{*}$ within $\mathcal{X}$ to obtain $f(\mathbf{x}_{t}^{*})$. This data, denoted as $(\mathbf{x}_{t}^{*},f(\mathbf{x}_{t}^{*}))$, is then added to the historical trajectories $\mathcal{D}_{t-1}$, resulting in:
$\mathcal{D}_{t}=\mathcal{D}_{t-1}\cup\{(\mathbf{x}_{t}^{*},f(\mathbf{x}_{t}^{*
}))\}.$
This completes a full iteration cycle of the CEPBO algorithm.

Figure: Algorithm 1 CEPBO Algorithm

### 3.4 Address the boundary issue

Our approach, akin to REMBO, encounters the issue of excessive exploration along the boundary of $\mathcal{X}$.
To ensure the effective tuning of the acquisition function and to facilitate BO,
it is crucial for the embedding subspace $\mathcal{Y}$ to have a bounded domain.
However, random projections between the original space of dimension $D$ and the embedding subspace of dimension $d$ can lead to points exceeding domain boundaries after CEP. These exceedances occur in two scenarios: $\mathbf{y}=\mathbf{A}\mathbf{x}\notin\mathcal{Y},\;\tilde{\mathbf{x}}=\mathbf{
A}^{\top}\mathbf{y}\notin\mathcal{X}.$

To mitigate the issue, we employ the convex projection of the original space, $P_{\mathcal{X}}$, and that of the
embedding subspace, $P_{\mathcal{Y}}$, to rectify boundary transgressions.
Specifically, the convex projection within the original space $\mathcal{X}$ is defined as follows:

$$ $P_{\mathcal{X}}:\mathbb{R}^{D}\to\mathbb{R}^{D},\;P_{\mathcal{X}}(\tilde{ \mathbf{x}})=\underset{\mathbf{z}\in\mathcal{X}}{\arg\min}\|\mathbf{z}-\tilde{ \mathbf{x}}\|_{2}.$ $$

Similarly, the convex projection within the embedding subspace $\mathcal{Y}$ is expressed as:

$$ $P_{\mathcal{Y}}:\mathbb{R}^{d}\to\mathbb{R}^{d},\;P_{\mathcal{Y}}(\mathbf{y})= \underset{\mathbf{z}\in\mathcal{Y}}{\arg\min}\|\mathbf{z}-\mathbf{y}\|_{2}.$ $$

Convex projection will lead to an issue where multiple distinctive values in the original space are mapped to identical boundary points within the embedding subspace, i.e.,
for $\mathbf{x}_{1}\neq\mathbf{x}_{2}$ such that $f(\mathbf{x}_{1})\neq f(\mathbf{x}_{2})$, the equality $P_{\mathcal{Y}}(\mathbf{A}\mathbf{x}_{1})=P_{\mathcal{Y}}(\mathbf{A}\mathbf{x}
_{2})$ holds.
Moreover, the substantial disparity between the dimensions $d$ and $D$ exacerbates the likelihood of such instances. This issue can undermine the precision of Gaussian process models and consequently, diminish the efficacy of optimization.
To mitigate this risk, a scaling strategy is implemented within the Condensing Projection and Expansion Projection phases to diminish the probability of such occurrences.
This involves scaling the projected points $\mathbf{A}\mathbf{x}$ using a reduction factor before applying convex projection, as follows:

$$ $\mathbf{y}=P_{\mathcal{Y}}\left(\frac{1}{\sqrt{D}}\mathbf{A}\mathbf{x}\right).$ $$

In a parallel procedure, the optimal points of the acquisition function in the embedding subspace $\mathbf{y}$ undergo an inverse scaling:

$$ $\tilde{\mathbf{x}}=P_{\mathcal{X}}(\sqrt{D}\mathbf{A}^{\top}\mathbf{y}).$ $$

In this context, the scaling factors $\frac{1}{\sqrt{D}}$ and $\sqrt{D}$ confine the scope of projection within the viable domain. These factors are verified through empirical experimentation.

## 4 Experiments

We conduct experiments to demonstrate the performance of the proposed method across various functions and
real-world scenarios.
In Section 4.1, we evaluate its performance on three benchmark functions.
In Section 4.2, we assess it across four real-world problems.
These experimental results indicate that our algorithms, CEP-REMBO and CEP-HeSBO, achieve superior results.

Because our approach, CEPBO, represents an advancement in the domain of the linear embeddings, our experiments focus on comparing it with other linear embeddings.
We aim to assess the improvement achieved by applying CEP compared to REMBO[] and HeSBO[], respectively. ALEBO is considered to achieve state-of-the-art performance on this class
of optimization problems with a true linear subspace.
Therefore, we chose REMBO[], HeSBO[], and ALEBO[] as the benchmark algorithms for our comparisons.

### 4.1 Numerical Results

We evaluated the performance of the algorithms using the following benchmark functions:
(1) the Holder Table function, (2) the Schwefel function, and (3) the Griewank function.
Each function’s input space was extended to a dimensionality of $D=100$. The Holder Table function has an effective dimension of $2$, whereas the Schwefel and Griewank functions are fully defined over the entire $D$-dimensional space.
To enhance the complexity of the optimization task, we introduced random perturbations into both the Schwefel and Griewank functions; for further details, please refer to the appendix 6.5.
The goal is to find the minimum value of these functions.
The number of initialization trials
for each algorithm was kept the same as the dimensionality of its embedding subspace. Each experiment is independently repeated 50
times, with 50 evaluations per experiment.
To assess the performance of the CEPBO algorithm under various embedding space dimensions, we take $d=2,5,10$ in the Holder Table function and $d=2,5,20$ in the Schwefel and Griewank functions. Since an effective dimension for the Schwefel and Griewank functions is 100, we prioritize the larger $d$ for assessment. In these experiments, we utilize expected improvement as the acquisition function.
We have also conducted an experiment using the well-known Hartmann function with $D=1000$ as reported in the appendix (6.3). The results shows that the CEP projection can significantly improve the performance of both REMBO and HeSBO.

Figure: Figure 2: The results of the optimization experiments for three functions across various embedding dimensions. From top to bottom: Holder Table, Schwefel, and Griewank functions.
Refer to caption: x2.png

We report the results in Figure 2.
For the Schwefel and Griewank functions, where embedding dimensions are smaller than the effective dimension of 100, the baseline algorithms nearly ceased functioning, settling in local optima, which is visually depicted as a flat horizontal line on the corresponding graphs.
Interestingly, even in the instance of the Holder Table function, where
the embedding dimension met or exceeded the effective dimension, a circumstance where the baseline algorithms typically perform well, the approached algorithms continued to show superior performance over all baselines.
Comparative the performance across a range of embedding dimensions $d$, the performance are similar and CEP-REMBO and CEP-HeSBO consistently surpassed all baseline algorithms. Therefore, the REMBO and HeSBO algorithms experienced substantial improvement with the integration of the Condense-Expansion Projection mechanism.

### 4.2 Real-World Problems

In this section, we evaluate the CEPBO algorithm on real-world optimization problems.
The test cases consist of lunar landing task in the realm of reinforcement learning with $D=12$ [], a robot pushing problem with $D=14$ [], a problem in neural architecture search with $D=36$ [], and a rover trajectory planning problem with $D=60$ [].
Algorithmic configurations and acquisition function selections strictly adhere to the settings outlined in the original papers.
For additional details, please refer to the appendix.
The optimization goal is to maximize the reward function, and each experiment is independently repeated 10 times, with 500 evaluations per experiment.

Figure: Figure 3: The results of the optimization experiments for four real-world scenarios. From left to right: Lunar landing, Robot pushing, NAS, and Rover planning.
Refer to caption: x3.png

Lunar Landing.  This experiment entails the task of devising a reinforcement
learning strategy for the lunar lander’s control mechanism, aiming to minimize fuel
consumption and proximity to the landing site while preventing a crash. The original space dimension is $D=12$.
In the first column of Figure 3, REMBO, HeSBO, and ALEBO algorithms become trapped in local optima to different extents. As the dimensionality of the embedding subspace $d$ increases from $d=2$ to $d=5$, notable performance improvements are observed for most algorithms, except REMBO.
The introduced CEP-REMBO and CEP-HeSBO approaches consistently demonstrate the ability to enhance and identify novel optimal resolutions.

Robot Pushing.  This scenario involves a robotics dual-arm manipulation
task where the robot’s arms are controlled by adjusting 14 modifiable parameters to push
two objects while tracking their movement trajectories.
The original space dimension is $D=14$.
The second column of Figure 3
demonstrates that the proposed CEP-REMBO and CEP-HeSBO methods significantly
outperform others when $d=2$. When increasing to $d=5$, all methods exhibit varying degrees of performance enhancement. This suggests that for optimization issues with moderate to low dimensionalities, escalating the dimensions of the embedding subspaces can notably bolster the algorithms’ efficacy. Notwithstanding these improvements, the CEP-REMBO and CEP-HeSBO methods consistently maintain their leading positions.

Neural Architecture Search (NAS).  The objective of this experiment is to identify an optimal
architecture for neural networks, paralleling the methodology utilized by []. Leveraging data
from the NAS-Bench-101 benchmark [], we have developed an optimization problem focused on searching for a
convolutional neural network architecture characterized by 36 dimensions.
The original space dimension is $D=36$.
In the third column of Figure 3, at an embedding
subspace dimension of $d=2$, the REMBO, HeSBO, and ALEBO algorithms rapidly converge to less than ideal solutions, hindering the exploration of superior neural network structures.
On the contrary, the CEP-REMBO and CEP-HeSBO methods maintain the capability to persistently optimize, discovering architectures
with improved accuracy. Increasing the subspace dimension to $d=5$ reveals the ALEBO’s enhanced ability
to perform on par with CEP-REMBO and CEP-HeSBO methods; however, CEP-HeSBO consistently exhibits the
highest performance across all conditions.

Rover Trajectory Planning.  This task involves optimizing a 2D
trajectory comprising of 30 pivotal points that collectively define a navigational path.
The original space dimension is $D=60$.
The fourth column of Figure 3 indicates that for an embedding
subspace dimension of $d=2$, the REMBO, HeSBO, and ALEBO algorithms can not successfully converge to an advantageous reward. In contrast, the CEP-REMBO and CEPHeSBO algorithms exhibit a capacity to consistently identify superior solutions.
This pattern is similarly observed when the subspace dimension is increased to $d=5$.

## 5 Conclusion

This paper proposes a Bayesian optimization framework utilizing the Condensing-Expansion Projection technique, free from reliance on the assumption of effective dimension.
The primary concept involves employing projection twice within each iteration: first, projecting to an embedding subspace, and then projecting back to retain optimization information in the original high-dimensional space.
The approach does not impose additional requirements on the projection matrix used, thereby significantly enhancing the applicability of the embedding-based Bayesian optimization algorithms. This flexibility enables the selection of a suitable projection matrix according to the problem’s characteristics beforehand.
This paper also theoretically verifies the properties of Condensing-Expansion Projection
under random Gaussian matrix and hashing matrix, providing that the transformed point $\tilde{\mathbf{x}}$ concentrates around the point $\mathbf{x}$ in the original space.
Finally, two new Bayesian optimization algorithms based on Condensing-Expansion Projection are proposed: CEP-REMBO and CEP-HeSBO based on the Gaussian projection matrix and the hash-enhanced projection matrix, respectively.
Empirically, this paper conducts comprehensive experiments to assess the performance of the proposed algorithms across diverse optimization scenarios.
The experimental results demonstrate that the Bayesian optimization algorithms based on Condensing-Expansion Projection achieved promising performance across these optimization functions, overcoming the reliance on effective dimension.

Our work has several limitations that can be addressed by future works.
For instance, while our analysis supports the concentration of the transformed point around the original point after employing CEP, we acknowledge the absence of $\epsilon$-subspace embedding to preserve the mean and variance functions of a Gaussian process. Although reference to [] suggests a potential avenue for such analysis, a more thorough examination is warranted. Another constraint of our study is the absence of an evaluation of CEP-based algorithms for optimization problems with billions of dimensions. Despite this potential, our approach lacks empirical validation, whereas REMBO has been shown to effectively address such challenges.

## 6 Appendix

### 6.1 Proof of Theorem 1

###### Proof.

(1) First, we consider the Gaussian Projection. Let $\mathbf{A}=(\boldsymbol{l}_{1},\cdots,\boldsymbol{l}_{d})^{\top}$, such that $\boldsymbol{l}_{i}=(\alpha_{i1},\cdots,\alpha_{iD})^{\top}$ is a $D\times 1$ vector where each element is from $\mathcal{N}\left(0,\frac{1}{d}\right)$ distribution.
It is easy to show that, given any vector $\mathbf{x}\in\mathcal{X}$ and any vector $\mathbf{g}\in\mathbb{R}^{D}$,

$$ $\mathbb{E}(\mathbf{A}^{\top}\mathbf{A})=\sum\limits_{i=1}^{d}\mathbb{E}\left( \boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\right)=\mathbf{I}.$ (1) $$

(2) Second, we consider the Hashing Random Projection.
For the Hashing Random Matrix, we rewrite
$\mathbf{A}=\mathbf{S}\mathbf{D}$, where $\mathbf{S}\in\mathbb{R}^{d\times D}$ has each column chosen independently and uniformly from
the $r$ standard basis vectors of $\mathbb{R}^{d}$ and $\mathbf{D}\in\mathbb{R}^{D\times D}$
is a diagonal matrix with diagonal entries chosen independently and uniformly on $b_{i}\in\{\pm 1\}$.

Let $\mathbf{S}=(\boldsymbol{s}_{1},\cdots,\boldsymbol{s}_{D})$, such that $\boldsymbol{s}_{i}$ is a random vector
taking the vector $e_{j}$
for equal probability, where $e_{k}$ is the $k$th standard unit vector of $\mathbb{R}^{d}$
for $k=1,\cdots,d$.
Then $\mathbb{E}(\boldsymbol{s}_{i})=\frac{1}{d}\boldsymbol{1}_{d}$ and $\mathbb{E}(\boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i})=1$, which follow that
$\mathbb{E}[(\mathbf{S}^{\top}\mathbf{S})_{ij}]=\mathbb{E}(\boldsymbol{s}_{i}^{
\top}\boldsymbol{s}_{j})=\mathbb{E}(\boldsymbol{s}_{i})^{\top}\mathbb{E}(
\boldsymbol{s}_{j})=\frac{1}{d^{2}}$
for $i\neq j$;
and $\mathbb{E}[(\mathbf{S}^{\top}\mathbf{S})_{ii}]=\mathbb{E}(\boldsymbol{s}_{i}^{
\top}\boldsymbol{s}_{i})=1$.
Obviously,

$$ $\mathbb{E}(\mathbf{A}^{\top}\mathbf{A})=\mathbf{I}.$ $$

∎

###### Proof.

### 6.2 Proof of Theorem 2

###### Proof.

(1) First, we consider the Gaussian projection. Let $\mathbf{A}=(\boldsymbol{l}_{1},\cdots,\boldsymbol{l}_{d})^{\top}$, such that $\boldsymbol{l}_{i}=(\alpha_{i1},\cdots,\alpha_{iD})^{\top}$ is a $D\times 1$ vector where each element is from $\mathcal{N}\left(0,\frac{1}{d}\right)$ distribution.
(1) follows that

$$ $\displaystyle\mathbb{E}[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x }-\mathbf{g}^{\top}\mathbf{x})^{2}]=$ $\displaystyle\mathbb{E}[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x })^{2}]-(\mathbf{g}^{\top}\mathbf{x})^{2}.$ (2) $$

In (2), we have,

$$ $\displaystyle\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A} \mathbf{x})^{2}\right]=\mathbb{E}\Big{[}(\sum\limits_{i=1}^{d}\mathbf{g}^{\top }\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\mathbf{x})^{2}\Big{]}$ $\displaystyle=$ $\displaystyle\mathbb{E}\Big{[}\sum\limits_{i=1}^{d}(\mathbf{g}^{\top} \boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\mathbf{x}\mathbf{x}^{\top} \boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\mathbf{g})+\sum\limits_{i\neq j}( \mathbf{g}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\mathbf{x})( \mathbf{g}^{\top}\boldsymbol{l}_{j}\boldsymbol{l}_{j}^{\top}\mathbf{x})^{\top} \Big{]}$ (3) $\displaystyle=$ $\displaystyle d\mathbb{E}[(\mathbf{g}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{ i}^{\top}\mathbf{x})(\mathbf{x}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{ \top}\mathbf{g})]+(d^{2}-d)\mathbb{E}(\mathbf{g}^{\top}\boldsymbol{l}_{i} \boldsymbol{l}_{i}^{\top}\mathbf{x})\mathbb{E}(\mathbf{g}^{\top}\boldsymbol{l} _{j}\boldsymbol{l}_{j}^{\top}\mathbf{x})^{\top}.$ $$

By (6) in Lemma 1,

$$ $\mathbb{E}[(\mathbf{g}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top} \mathbf{x})(\mathbf{x}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top} \mathbf{g})]=\frac{3}{d^{2}}\|\mathbf{x}\|^{2}\|\mathbf{g}\|^{2}.$ $$

Then we have

$$ $\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x})^{2} \right]=(\mathbf{g}\top\mathbf{x})^{2}+\frac{3}{d}\|\mathbf{x}\|^{2}\|\mathbf{ g}\|^{2}-\frac{1}{d}(\mathbf{g}\top\mathbf{x})^{2}.$ (4) $$

Therefore, we have

$$ $\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x}- \mathbf{g}^{\top}\mathbf{x})^{2}\right]=\frac{3}{d}\|\mathbf{x}\|^{2}\|\mathbf {g}\|^{2}-\frac{1}{d}(\mathbf{g}\top\mathbf{x})^{2}.$ $$

(2) Second, we consider the Hashing Random Projection.
For the Hashing Random Matrix, we rewrite
$\mathbf{A}=\mathbf{S}\mathbf{D}$, where $\mathbf{S}\in\mathbb{R}^{d\times D}$ has each column chosen independently and uniformly from
the $r$ standard basis vectors of $\mathbb{R}^{d}$ and $\mathbf{D}\in\mathbb{R}^{D\times D}$
is a diagonal matrix with diagonal entries chosen independently and uniformly on $b_{i}\in\{\pm 1\}$.

Let $\mathbf{S}=(\boldsymbol{s}_{1},\cdots,\boldsymbol{s}_{D})$, such that $\boldsymbol{s}_{i}$ is a random vector
taking the vector $e_{j}$
for equal probability, where $e_{k}$ is the $k$th standard unit vector of $\mathbb{R}^{d}$
for $k=1,\cdots,d$.
Then $\mathbb{E}(\boldsymbol{s}_{i})=\frac{1}{d}\boldsymbol{1}_{d}$ and $\mathbb{E}(\boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i})=1$, which follow that
$\mathbb{E}[(\mathbf{S}^{\top}\mathbf{S})_{ij}]=\mathbb{E}(\boldsymbol{s}_{i}^{
\top}\boldsymbol{s}_{j})=\mathbb{E}(\boldsymbol{s}_{i})^{\top}\mathbb{E}(
\boldsymbol{s}_{j})=\frac{1}{d^{2}}$
for $i\neq j$;
and $\mathbb{E}[(\mathbf{S}^{\top}\mathbf{S})_{ii}]=\mathbb{E}(\boldsymbol{s}_{i}^{
\top}\boldsymbol{s}_{i})=1$.

Applying Lemma 2,

$$ $\displaystyle\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A} \mathbf{x})^{2}\right]=$ $\displaystyle(\mathbf{g}^{\top}\mathbf{x})^{2}+\frac{1}{d}\left(\|\mathbf{g}\| ^{2}\|\mathbf{x}\|^{2}-\sum\limits_{i=1}^{D}x_{i}^{2}g_{i}^{2}\right).$ $$

Thus, we have,

$$ $\mathbb{E}\left[(\mathbf{g}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{x}- \mathbf{g}^{\top}\mathbf{x})^{2}\right]=\frac{1}{d}\left(\|\mathbf{g}\|^{2}\| \mathbf{x}\|^{2}-\sum\limits_{i=1}^{D}x_{i}^{2}g_{i}^{2}\right).$ $$

∎

###### Proof.

#### 6.2.1 Two Lemmas

###### Lemma 1 .

Let $\mathbf{A}=(\boldsymbol{l}_{1},\cdots,\boldsymbol{l}_{d})^{\top}$, such that $\boldsymbol{l}_{i}=(\alpha_{i1},\cdots,\alpha_{iD})^{\top}$ is an $D\times 1$ vector where each element is from zero mean
distribution with $E(\alpha_{ij}^{2})=1$ and $E(\alpha_{ij}^{4})=\gamma$, we have that, for any matrices $\mathbf{M}_{1}\in\mathbb{R}^{D\times d_{1}}$ and $\mathbf{M}_{2}\in\mathbb{R}^{D\times d_{2}}$, where $\boldsymbol{m}_{1i}$ and $\boldsymbol{m}_{2i}$ are their $i$-th row, respectively.

$$ $E\left[(\mathbf{M}_{1}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top} \mathbf{M}_{2})(\mathbf{M}_{2}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{ \top}\mathbf{M}_{1})\right]=\mathbf{M}_{1}^{\top}[(\gamma-3)\mathbf{W}_{2}+2 \mathbf{M}_{2}\mathbf{M}_{2}^{\top}+\text{tr}(\mathbf{M}_{2}\mathbf{M}_{2}^{T} )\mathbf{I}]\mathbf{M}_{1},$ (5) $$

where $\mathbf{W}_{2}=\text{diag}\{\boldsymbol{m}_{21}^{\top}\boldsymbol{m}_{21},
\cdots,\boldsymbol{m}_{2D}^{\top}\boldsymbol{m}_{2D}\}$.
Particularly, for Gaussian projection,

$$ $E\left[(\mathbf{M}_{1}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top} \mathbf{M}_{2})(\mathbf{M}_{2}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{ \top}\mathbf{M}_{1})\right]=2\mathbf{M}_{1}^{\top}[\mathbf{M}_{2}\mathbf{M}_{2 }^{\top}]\mathbf{M}_{1}+\text{tr}(\mathbf{M}_{2}\mathbf{M}_{2}^{T})\mathbf{M}_ {1}^{T}\mathbf{M}_{1},$ (6) $$

###### Proof.

Since $\mathbf{M}_{1}^{\top}\boldsymbol{l}_{i}=\sum\limits_{j=1}^{D}\alpha_{ij}
\boldsymbol{m}_{1j}$ and
$\mathbf{M}_{2}^{\top}\boldsymbol{l}_{i}=\sum\limits_{j=1}^{D}\alpha_{ij}
\boldsymbol{m}_{2j}$, where $\boldsymbol{m}_{1j}^{\top}$
and $\boldsymbol{m}_{2j}^{\top}$ are the $j$th row of $\mathbf{M}_{1}$ and $\mathbf{M}_{2}$ respectively, it
follows that,

$$ $\mathbf{M}_{1}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\mathbf{M}_{2} =(\sum\limits_{j=1}^{D}\alpha_{ij}\boldsymbol{m}_{1j})(\sum\limits_{j=1}^{D} \alpha_{ij}\boldsymbol{m}_{2j})^{\top}=\sum\limits_{j=1}^{n}\alpha_{ij}^{2} \boldsymbol{m}_{1j}\boldsymbol{m}_{2j}^{\top}+\sum\limits_{j_{1}\neq j_{2}} \alpha_{ij_{1}}\alpha_{ij_{2}}\boldsymbol{m}_{1j_{1}}\boldsymbol{m}_{2j_{2}}^{ \top}.$ $$

$$ $\mathbf{M}_{2}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i}^{\top}\mathbf{M}_{1} =(\sum\limits_{j=1}^{D}\alpha_{ij}\boldsymbol{m}_{2j})(\sum\limits_{j=1}^{D} \alpha_{ij}\boldsymbol{m}_{1j})^{\top}=\sum\limits_{j=1}^{n}\alpha_{ij}^{2} \boldsymbol{m}_{2j}\boldsymbol{m}_{1j}^{\top}+\sum\limits_{j_{1}\neq j_{2}} \alpha_{ij_{1}}\alpha_{ij_{2}}\boldsymbol{m}_{2j_{1}}\boldsymbol{m}_{1j_{2}}^{ \top},$ $$

Since $E(\alpha_{ij}^{4})=\gamma$, so, we have that

$$ $\displaystyle E\left(\sum\limits_{j=1}^{D}\alpha_{ij}^{2}\boldsymbol{m}_{1j} \boldsymbol{m}_{2j}^{\top}\right)\left(\sum\limits_{j=1}^{n}\alpha_{ij}^{2} \boldsymbol{m}_{2j}\boldsymbol{m}_{1j}^{\top}\right)$ $\displaystyle=$ $\displaystyle\gamma\sum\limits_{j=1}^{D}\boldsymbol{m}_{1j}\boldsymbol{m}_{2j} ^{\top}\boldsymbol{m}_{2j}\boldsymbol{m}_{1j}^{\top}+\left(\sum\limits_{j_{1} \neq j_{2}}\boldsymbol{m}_{1j_{1}}\boldsymbol{m}_{2j_{1}}^{\top}\boldsymbol{m} _{2j_{2}}\boldsymbol{m}_{1j_{2}}^{\top}\right),$ $$

$$ $\displaystyle E\left(\sum\limits_{j_{1}\neq j_{2}}\alpha_{ij_{1}}\alpha_{ij_{2 }}\boldsymbol{m}_{1j_{1}}\boldsymbol{m}_{2j_{2}}^{\top}\right)\left(\sum \limits_{j_{1}\neq j_{2}}\alpha_{ij_{1}}\alpha_{ij_{2}}\boldsymbol{m}_{2j_{1}} \boldsymbol{m}_{1j_{2}}^{\top}\right)$ $\displaystyle=$ $\displaystyle\left(\sum\limits_{j_{1}\neq j_{2}}\boldsymbol{m}_{1j_{1}} \boldsymbol{m}_{2j_{2}}^{\top}\boldsymbol{m}_{2j_{1}}\boldsymbol{m}_{1j_{2}}^{ \top}\right)+\sum\limits_{j_{1}\neq j_{2}}\boldsymbol{m}_{1j_{1}}\boldsymbol{m }_{2j_{2}}^{T}\boldsymbol{m}_{2j_{2}}\boldsymbol{m}_{1j_{1}}^{T},$ $$

$$ $E\left(\sum\limits_{j=1}^{D}\alpha_{ij}^{2}\boldsymbol{m}_{1j}\boldsymbol{m}_{ 2j}^{\top}\right)\left(\sum\limits_{j_{1}\neq j_{2}}\alpha_{ij_{1}}\alpha_{ij_ {2}}\boldsymbol{m}_{2j_{1}}\boldsymbol{m}_{1j_{2}}^{\top}\right)=0,$ $$

$$ $E\left(\sum\limits_{j_{1}\neq j_{2}}\alpha_{ij_{1}}\alpha_{ij_{2}}\boldsymbol{ m}_{1j_{1}}\boldsymbol{m}_{2j_{2}}^{\top}\right)\left(\sum\limits_{j=1}^{D} \alpha_{ij}^{2}\boldsymbol{m}_{2j}\boldsymbol{m}_{1j}^{\top}\right)=0.$ $$

Combing the four equations above, it is easy to verify that,

$$ $\displaystyle E\left[(\mathbf{M}_{1}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{i }^{\top}\mathbf{M}_{2})\mathbf{M}_{2}^{\top}\boldsymbol{l}_{i}\boldsymbol{l}_{ i}^{\top}\mathbf{M}_{1}\right]$ $\displaystyle=$ $\displaystyle(\gamma-3)\sum\limits_{j=1}^{n}\boldsymbol{m}_{1j}\boldsymbol{m}_ {2j}^{\top}\boldsymbol{m}_{2j}\boldsymbol{m}_{1j}^{\top}+2\mathbf{M}_{1}^{\top }\mathbf{M}_{2}\mathbf{M}_{2}^{\top}\mathbf{M}_{1}+\text{tr}(\mathbf{M}_{2} \mathbf{M}_{2}^{T})\mathbf{M}_{1}^{T}\mathbf{M}_{1}.$ $$

∎

###### Lemma 2 .

For the Hashing random projection

$$ $E\left[(\mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M}_{2})( \mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M}_{2})^{\top}\right]= \mathbf{M}_{1}^{\top}\mathbf{M}_{2}\mathbf{M}_{2}^{\top}\mathbf{M}_{1}+\frac{1 }{d}\mathbf{M}_{1}^{\top}\mathbf{M}_{1}\text{tr}(\mathbf{M}_{2}\mathbf{M}_{2}^ {\top})-\frac{1}{d}\mathbf{M}_{1}^{\top}\mathbf{W}_{2}\mathbf{M}_{1}.$ $$

###### Proof.

For the Hashing Random Matrix projection, we rewrite
$\mathbf{A}=\mathbf{S}\mathbf{D}$, where $\mathbf{S}\in\mathbb{R}^{d\times D}$ has each column chosen independently and uniformly from
the $r$ standard basis vectors of $\mathbb{R}^{d}$ and $\mathbf{D}\in\mathbb{R}^{D\times D}$
is a diagonal matrix with diagonal entries chosen independently and uniformly on $b_{i}\in\{\pm 1\}$.

Let $\mathbf{S}=(\boldsymbol{s}_{1},\cdots,\boldsymbol{s}_{n})$, such that $\boldsymbol{s}_{i}$ is a random vector
taking the vector $e_{j}$
for equal probability, where $e_{j}$ is the $j$th standard unit vector of $\mathbb{R}^{d}$
for $j=1,\cdots,r$.
Then $E(\boldsymbol{s}_{i})=\frac{1}{d}\boldsymbol{1}_{d}$ and $E(\boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i})=1$, which follow that
$E[(\mathbf{S}^{\top}\mathbf{S})_{ij}]=E(\boldsymbol{s}_{i}^{\top}\boldsymbol{s
}_{j})=E(\boldsymbol{s}_{i})^{\top}E(\boldsymbol{s}_{j})=\frac{1}{d^{2}}$
for $i\neq j$;
and $E[(\mathbf{S}^{\top}\mathbf{S})_{ii}]=E(\boldsymbol{s}_{i}^{\top}\boldsymbol{s
}_{i})=1$.
We have that,

$$ $\displaystyle\mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M}_{2}$ $\displaystyle=(\sum\limits_{i=1}^{D}b_{i}\boldsymbol{s}_{i}\boldsymbol{m}_{1i} ^{\top})^{\top}(\sum\limits_{i=1}^{D}b_{i}\boldsymbol{s}_{i}\boldsymbol{m}_{2i }^{\top})$ $\displaystyle=\sum\limits_{i=1}^{D}b_{i}^{2}\boldsymbol{m}_{1i}\boldsymbol{s}_ {i}^{\top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top}+\sum\limits_{i\neq j}b_ {i}b_{j}\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{j} \boldsymbol{m}_{2j}^{\top}$ (7) $$

From (6.2.1), we have,

$$ $\displaystyle E\left[\mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M }_{2}\right]\left[\mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M}_{ 2}\right]^{\top}$ $\displaystyle=$ $\displaystyle E\left(\sum\limits_{i=1}^{D}b_{i}^{2}\boldsymbol{m}_{1i} \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top}+\sum \limits_{i\neq j}b_{i}b_{j}\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{\top} \boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top}\right)\left(\sum\limits_{i=1}^{D} b_{i}^{2}\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i} \boldsymbol{m}_{2i}^{\top}+\sum\limits_{i\neq j}b_{i}b_{j}\boldsymbol{m}_{1i} \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top}\right)^{\top}$ $\displaystyle=$ $\displaystyle\sum\limits_{i=1}^{D}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{ \top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top})(\boldsymbol{m}_{1i} \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top})^{\top}+ \sum\limits_{i\neq j}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{\top}\boldsymbol {s}_{i}\boldsymbol{m}_{2i}^{\top})(\boldsymbol{m}_{1j}\boldsymbol{s}_{j}^{\top }\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})^{\top}$ $\displaystyle+\sum\limits_{i\neq j}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{ \top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})(\boldsymbol{m}_{1i} \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})^{\top}= :E_{1}+E_{2}+E_{3}.$ $$

Specifically, we have that

$$ $\displaystyle E_{1}=\sum\limits_{i=1}^{D}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{ i}^{\top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top})(\boldsymbol{m}_{1i} \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top})^{\top}= \sum\limits_{i=1}^{D}\sum\limits_{k=1}^{d}\frac{1}{d}(\boldsymbol{m}_{1i} \mathbf{e}_{k}^{\top}\mathbf{e}_{k}\boldsymbol{m}_{2i}^{\top})(\boldsymbol{m}_ {1i}\mathbf{e}_{k}^{\top}\mathbf{e}_{k}\boldsymbol{m}_{2i}^{\top})^{\top}$ $\displaystyle\ \ =\sum\limits_{i=1}^{D}(\boldsymbol{m}_{1i}\boldsymbol{m}_{2i} ^{\top})(\boldsymbol{m}_{1i}\boldsymbol{m}_{2i}^{\top})^{\top}.$ $\displaystyle E_{2}=\sum\limits_{i\neq j}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{ i}^{\top}\boldsymbol{s}_{i}\boldsymbol{m}_{2i}^{\top})(\boldsymbol{m}_{1j} \boldsymbol{s}_{j}^{\top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})^{\top}= \sum\limits_{i\neq j}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{i}^{\top}\boldsymbol {s}_{i}\boldsymbol{m}_{2i}^{\top})E(\boldsymbol{m}_{1j}\boldsymbol{s}_{j}^{ \top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})^{\top}$ $\displaystyle\ \ =\sum\limits_{i\neq j}(\boldsymbol{m}_{1i}\boldsymbol{m}_{2i} ^{\top})(\boldsymbol{m}_{1j}\boldsymbol{m}_{2j}^{\top})^{\top}$ $\displaystyle E_{3}=\sum\limits_{i\neq j}E(\boldsymbol{m}_{1i}\boldsymbol{s}_{ i}^{\top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})(\boldsymbol{m}_{1i} \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{j}\boldsymbol{m}_{2j}^{\top})^{\top}= \sum\limits_{i\neq j}\boldsymbol{m}_{1i}E(\boldsymbol{s}_{i}^{\top}\boldsymbol {s}_{j}\boldsymbol{m}_{2j}^{\top}\boldsymbol{m}_{2j}\boldsymbol{s}_{j}^{T} \boldsymbol{s}_{i})\boldsymbol{m}_{1i}^{T}$ $\displaystyle\ \ =\sum\limits_{i\neq j}\boldsymbol{m}_{1i}\boldsymbol{m}_{2j}^ {\top}\boldsymbol{m}_{2j}E(\boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{j} \boldsymbol{s}_{j}^{T}\boldsymbol{s}_{i})\boldsymbol{m}_{1i}^{T}=\sum\limits_{ i\neq j}\boldsymbol{m}_{1i}\boldsymbol{m}_{2j}^{\top}\boldsymbol{m}_{2j}E( \boldsymbol{s}_{i}^{\top}\boldsymbol{s}_{j})^{2}\boldsymbol{m}_{1i}^{T}$ $\displaystyle=\frac{1}{d}\sum\limits_{i\neq j}\boldsymbol{m}_{1i}\boldsymbol{m }_{2j}^{\top}\boldsymbol{m}_{2j}\boldsymbol{m}_{1i}^{T}$ $\displaystyle\ \ =\frac{1}{d}\mathbf{M}_{1}^{\top}\mathbf{M}_{1}\text{tr}( \mathbf{M}_{2}\mathbf{M}_{2}^{\top})-\frac{1}{d}\mathbf{M}_{1}^{\top}\mathbf{W }_{2}\mathbf{M}_{1}$ (8) $$

where $\mathbf{W}_{2}=\mathrm{diag}\{\boldsymbol{m}_{21}^{\top}\boldsymbol{m}_{21},
\cdots,\boldsymbol{m}_{2n}^{\top}\boldsymbol{m}_{2n}\}$.
Thus, we have,

$$ $E\left[(\mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M}_{2})( \mathbf{M}_{1}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{M}_{2})^{\top}\right]= \mathbf{M}_{1}^{\top}\mathbf{M}_{2}\mathbf{M}_{2}^{\top}\mathbf{M}_{1}+\frac{1 }{d}\mathbf{M}_{1}^{\top}\mathbf{M}_{1}\text{tr}(\mathbf{M}_{2}\mathbf{M}_{2}^ {\top})-\frac{1}{d}\mathbf{M}_{1}^{\top}\mathbf{W}_{2}\mathbf{M}_{1}.$ $$

∎

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

### 6.3 An experiment with a higher dimension

To assess the performance of the CEPBO algorithm in higher dimensions,
we conducted simulations using the well-known Hartmann function.
Specifically, we utilized the Hartmann function with an original space dimension of $D=1000$ and set the embedded space dimension to $d=6$ as well.

Figure: Figure 4: The results of the optimization experiments for Hartmann function.
Refer to caption: x4.png

The results are reported in Figure 4. In this setup, ALEBO, REMBO, and HeSBO were identified as the best-performing configurations.
The experimental results demonstrate that our proposed algorithm still maintains a certain level of superiority, with the CEP-REMBO algorithm being the optimal one. Additionally, the results indicate that incorporating the CEP projection mechanism can significantly improve the performance of both REMBO and HeSBO algorithms.

### 6.4 Details of machine information

The entire experiment in this paper is programmed in Python and run under the Linux system, using open-source Bayesian optimization libraries such as Ax[] and BoTorch[] for assistance. The experimental equipment is equipped with 2 AMD EPYC 7601 processors, each with 32 cores and a base clock frequency of 2.2GHz. The experiment is conducted in the form of parallel processing, with different independent repeating experiments distributed to different CPU cores for acceleration. In addition, the system has a memory capacity of 768GB, providing sufficient memory space for large-scale data processing and complex algorithm operation.

### 6.5 Modified Schwefel function and Griewank function

To investigate the efficacy of the proposed method within the complex context of high-dimensional optimization problems that entail numerous local minima, we applied a Schwefel function of $D=100$ and a Griewank function of $D=100$.
In the context of the Schwefel function and Griewank function, every dimension qualifies as an effective dimension, hence $d_{e}=D=100$.
We increased the optimization challenge by altering the Schwefel function and Griewank function. This alteration involved the adjustment of positions within different dimensions where minimum values are attained, thereby making the optimization of the Schwefel function and Griewank function more challenging.
The modified Schwefel function is:

$$ $f(\mathbf{x})=\sum_{i=1}^{D}\frac{x_{i}^{2}}{4000}-\prod_{i=1}^{d}\cos\left( \frac{x_{i}}{\sqrt{i}}\right)+1,$ (9) $$

Where $b_{i}\sim\mathcal{N}(0,1)$. We maintain the constancy of $b_{i}$ values across different independent repeated experiments, while allowing $b_{i}$ values to vary across different dimensions.

The modified Griewank function can be expressed as:

$$ $f(\mathbf{x})=\sum_{i=1}^{D}w_{i}(x_{i}-b_{i})^{2}-\prod_{i=1}^{d}\cos\left( \frac{x_{i}}{\sqrt{i}}\right),$ (10) $$

where $w_{i}\sim\mathcal{N}(0,1)$ and $b_{i}\sim\mathcal{N}(0,1)$. We ensure that the values of $w_{i}$ and $b_{i}$ remain consistent within various independent repeat experiments, while differing across the several dimensions.

### 6.6 Details about Real-World Problems

#### 6.6.1 Lunar landing

In this experiment, our goal is to learn a strategy that controls the lunar lander, so that the lunar lander can minimize fuel consumption and distance from the landing target, while avoiding crashes. This optimization task was proposed by Eriksson[]. The simulation environment of the control task is implemented through OpenAI gym (^1^11www.gymlibrary.dev/environments/box2d/lunar_lander/). The state space of the lunar lander includes its coordinates $x$ and $y$, linear velocities $x_{v}$ and $y_{v}$, its angle, its angular velocity, and two boolean values indicating whether each leg is in contact with the ground. At any moment, the current controller state can be represented with an $8$-dimensional vector. After obtaining the state vector, the controller can choose one of four possible actions, corresponding to pushing the thrusters left, right, up or none. In the experiment, it can be considered as a $D=12$ optimization problem. Once the parameters are determined, the corresponding rewards can be obtained through in-game feedback. If the lander deviates from the landing pad, it loses rewards. If the lander crashes, it gets an extra $-100$ points. If it successfully controls the lander to stop, it will get an extra $+100$ points. Each leg touching the ground gets $+10$ points. Igniting the main engine gets $-0.3$ points per frame. Each frame starts side engine for $-0.03$ points. The goal of the control task optimization is to maximize the average final reward on a fixed set of 50 randomly generated terrains, initial positions, and speed combinations. We observe that even minor perturbations can have an impact on the simulation.

#### 6.6.2 Robot pushing

This paper follows the experimental setup of Wang[], Eriksson[] et al., and also realizes the simulation of using two robot arms to push two objects in the Box $2\mathrm{D}$[] physics engine. In the simulation environment, the parameters of the robot arms are simulated to push two objects, and the trajectories of the object movements are recorded at the same time. A total of 14 parameters are used by the two robot arms, which respectively specify the position and rotation of the robot hands, the pushing speed, the moving direction, and the pushing time. The lower bounds for these parameters are

$$ $[-5,-5,-10,-10,2,0,-5,-5,-10,-10,2,0,-5,-5],$ $$

and the upper bounds are

$$ $[5,5,10,10,30,2\pi,5,5,10,10,30,2\pi,5,5].$ $$

The initial positions of the objects are designated as $s_{i0}$ and $s_{i1}$, and the end positions as $s_{e0}$ and $s_{e1}$. The target positions of the two objects are indicated by $s_{g0}$ and $s_{g1}$. The reward is defined as

$$ $r=\left|s_{g0}-s_{i0}\right|+\left|s_{g1}-s_{i1}\right|-\left|s_{g0}-s_{e0} \right|-\left|s_{g1}-s_{e1}\right|,$ $$

namely the distance by which the objects move towards their target positions.

#### 6.6.3 NAS

In this paper, referring to the settings of Letham[] and others, by parameterizing operations and edges respectively, the optimal architecture search problem in NASBench-101 is set as a continuous high-dimensional Bayesian optimization problem.
Specifically, $L$ different operations are represented by one-hot encoding.

Since two of the seven nodes are fixed as input and output nodes, the remaining five optional nodes, each node corresponds to three different operations, which generate a total of 15 different parameters.
We optimize these parameters in the continuous $[0,1]$ space.
For each node, we take the "operation" corresponding to the maximum value of the three operations under that node as the "operation" adopted by that node, and use one-hot encoding to represent the specific "operation" used under that node.

Since NASBench-101 uses a $7\times 7$ upper triangular adjacency matrix to represent edges, it generates a total of $\frac{7\cdot 6}{2}=21$ possible edges.
And the five optional vertices can have three different operations, so under this encoding there are about $2^{21}\cdot 3^{5}\approx 510M$ unique models,
After removing a large number of unreasonable input and output models and models with more than 9 edges, the search space still has about $423k$ unique models.
We convert these 21 possible edges into 21 binary parameters that are similarly optimized in a continuous $[0,1]$ space.
We rank the continuous values corresponding to these 21 binary parameters and create an empty adjacency matrix.
Then, we add edges to the adjacency matrix in the percentile order of the 21 binary parameters iteratively, while pruning parts that are not connected to the input or output nodes, until reaching the limit of 9 edges.
Finally, the combination of adjacency matrix parameters (21) and one-hot encoded "operation" parameters (15) constitutes a 36-dimensional optimization space.
The Bayesian optimization algorithm only needs to be optimized in a high-dimensional space with $D=36$, and the boundary constraint is $[-1,1]^{36}$.
Each vector $\mathbf{x}\in\mathbb{R}^{36}$ can be decoded into a DAG and lookup evaluated in NASBench-101.

#### 6.6.4 Rover planning

To explore the performance of the proposed method in complex high-dimensional optimization scenarios, we considered a two-dimensional trajectory optimization task aimed at simulating detector navigation missions. This optimization task was proposed by Wang[], and the experimental setup by Wang[] was continued to be used here, with the optimization objective being to maximize the reward function. The problem instance is described by defining the starting position $s$, the target position $g$, and a cost function on the state space. The goal of the problem is to optimize the detector’s trajectory on rugged terrain. The trajectory consists of a set of points on a two-dimensional plane, and there are 30 points in this instance, which can be fitted into a B-spline curve, so it is considered a high-dimensional optimization problem with $D=60$. Through a set of trajectories, $\boldsymbol{x}\in[0,1]^{60}$, and a specific cost function, we can calculate the cost of a trajectory $c(\boldsymbol{x})$.

The reward for this problem is defined as

$$ $f(\boldsymbol{x})=c(\boldsymbol{x})+\lambda\left(\left|\boldsymbol{x}_{0,1}-s \right|1+\left|\boldsymbol{x}_{59,60}-g\right|_{1}\right)+b.$ $$

The reward function is non-smooth, discontinuous, and concave. The four input dimensions involved in the reward function respectively represent the starting and target positions of the trajectory. Set $\lambda=-10,b=5$, any collision with objects along the trajectory will incur a penalty of $-20$, which is the collision cost of the trajectory. Thus, in addition to penalties in the reward function caused by collisions, adverse deviations from the trajectory’s starting point will also incur additional penalties.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: - My biggest concern is for the authors to provide empirical comparison against the method BAxUS. 
- In Section 3.4, addressing the boundary issue, the authors apply scaling to the two convex projections. What is the motivation for this scaling?
soundness: 3
strengths: -	The writing is easy to understand.
-	CEPBO generates new projection matrix every iteration, compared to REMBO, HeSBO and ALEBO use fixed matrix during the optimization process. Even more recent methods such as BAxUS [1] and Bounce [2] do not apply this technique. They only sample 1 projection matrix during each subspace.
-	The authors provide some theoretical analysis for CEPBO.
summary: This paper proposes CEPBO, a high-dimensional BO method following subspace embedding technique. In each iteration, CEPBO samples an embedding matrix A_t based on one of the two techniques: (1) Gaussian projection matrix (similar to the embedding matrix of REMBO) or (2) hashing projection matrix (similar to the embedding matrix of HESBO and BAxUS). CEPBO then project observed data in original space X to embedded space Y, build GP in Y. After maximizing acquisition function in Y, CEPBO project the proposed data point back to X to evaluate f(x).
weaknesses: -	The authors did not mention BAxUS (2022) [1] and Bounce (2023) [2], two recent methods that follows subspace embedding techniques. Specifically, BAxUS focuses on continuous high-dimensional optimization problems, and has been shown to outperform HeSBO and ALEBO in many problems. Bounce extends BAxUS to categorical and mixed domains. BAxUS even mitigates the needs of choosing effective dimension d, which makes the method more robust compared to REMBO, HeSBO and even ALEBO, which require a specific choice of d. CEPBO still requires d as a hyper-parameter, which seems to be not as robust as BAxUS.
-	The highest dimension of real-world problems is only 60. Recent high-dimensional BO papers have at least one real-world problem with D>100 [1-7].

[1] Papenmeier, Leonard, Luigi Nardi, and Matthias Poloczek. "BAxUS: Increasing the scope as you learn: Adaptive Bayesian optimization in nested subspaces." Advances in Neural Information Processing Systems 35 (2022).

[2] Papenmeier, Leonard, Luigi Nardi, and Matthias Poloczek. "Bounce: reliable high-dimensional Bayesian optimization for combinatorial and mixed spaces." Advances in Neural Information Processing Systems 36 (2023): 1764-1793.

[3] Wang, Linnan, Rodrigo Fonseca, and Yuandong Tian. "LA-MCTS: Learning search space partition for black-box optimization using monte carlo tree search." Advances in Neural Information Processing Systems 33 (2020): 19511-19522.

[4] Eriksson, David, and Martin Jankowiak. "SAASBO: High-dimensional Bayesian optimization with sparse axis-aligned subspaces." Uncertainty in Artificial Intelligence. PMLR, 2021.

[5] Song, Lei, et al. "MCTS-VS: Monte carlo tree search based variable selection for high dimensional bayesian optimization." Advances in Neural Information Processing Systems 35 (2022).

[6] Ziomek, Juliusz Krzysztof, and Haitham Bou Ammar. "RDUCB: Are random decompositions all we need in high dimensional Bayesian optimisation?." International Conference on Machine Learning. PMLR, 2023.

[7] Ngo, Lam, et al. "CMA-BO: High-dimensional Bayesian Optimization via Covariance Matrix Adaptation Strategy." Transactions on Machine Learning Research.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 3
questions: The paper is clearly written, and I have no question.
soundness: 3
strengths: The paper explores a simple and fast method of using random projections to accelerate the BO. Many experimental results indicate that the proposed method is competitive.
summary: The authors consider low-dimensional Bayesian optimization (BO) using random linear projections. The variables for optimization are projected onto a low-dimensional space, and the next query point is selected using BO within this space. The point is then transformed back to the original variable space using the transpose of the projection matrix. The method is justified by the property that the “expectation” of the inner product of projection matrices is the identity matrix.
weaknesses: The use of low-dimensional space is not generally new, and it is not surprising that the method would yield certain benefits. However, the explanations and theory provide are insufficient to understand from which perspective the proposed method would offer such advantages.
My major concern is that the process of mapping the candidate point back to the pre-image will be arbitrary. Can the authors explain why they did not consider using the pseudoinverse of A? In general, finding the pre-image is an ill-posed problem. The authors have to be cautious about using A^\top. Can the authors guarantee that the deviation of the proposed method from the best result of the true pre-image will be minimal? The equality of the expectation of A^\topA and the identity matrix in Eq. (1) is insufficient.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: See “Weaknesses”
soundness: 3
strengths: This work presents two algorithms based on the existing random projection matrices: the Gaussian projection matrix and the hashing projection matrix, and Condensing-Expansion Projection Bayesian optimization. Experimental results demonstrate that the algorithms outperform existing random embedding-based algorithms on high-dimensional BO problems. The presentation of this paper is good. The research field of this paper is significant. The overall structure is relatively clear.
summary: This work introduces a search strategy in high-dimensional BO problems called the 
Condense-Expansion Projection technique. It generates a random projection matrix to project the high-dimensional data to the low-dimensional embedding space. Then it projects the searched data point back to the high-dimensional space for evaluation in the original space. The random projection matrices are the existing Gaussian projection matrix and the hashing projection matrix. They result in the development of two algorithms: CEP-REMBO and CEP-HeSBO. The experiments demonstrate the effectiveness of the both algorithms on simulation and real-world datasets.
weaknesses: This work could be improved from several angles.

1.It is common knowledge that approximation methods can reduce the performance of algorithms. And one of the main advantage of approximation methods is reducing the complexity of the algorithm. The motivation of this work is: “In high-dimensional settings, Bayesian optimization (BO) can be expensive and infeasible.” How does this work validate the motivation of “expensive”? Please provide a specific complexity analysis comparing the proposed method to standard high-dimensional BO, and to include runtime comparisons in the experiments. 

2.The Condensing-Expansion technique on random projections has been proposed and successfully applied in many fields, such as federated learning [1]. The random projection matrices are the existing Gaussian projection matrix and the hashing projection matrix. They have been applied in many fields. This work is a simple migration without novelty. It is trivial. Could you more clearly articulate the novelty of applying this technique to Bayesian optimization specifically? Are there unique challenges or benefits in this domain? Additionally, please provide a more thorough comparison to how these techniques are used in other fields to highlight any key differences or innovations in the proposed approach.

[1] Song Z, Wang Y, Yu Z, et al. Sketching for first order method: efficient algorithm for low-bandwidth channel and vulnerability[C]//International Conference on Machine Learning. PMLR, 2023: 32365-32417.

3.There is no organization section. To improve the readability of this paper, It would be better to add the organization section.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. The comparison methods are outdated, and the experiments are unconvincing. As mentioned in the "weaknesses", high-dimensional Bayesian optimization is a rapidly evolving field, with at least 60 highly relevant works published since 2013, including at least 20 based on embeddings. Comparing only with the older methods like REMBO and HesBO is insufficient, and even ALEBO, published in 2020, is no longer the state-of-the-art. Can the authors conduct thorough comparative experiments with relevant works (such as [1-7]) from the past three years to demonstrate the superior performance of CEPBO?

2. Why did the authors limit the optimization in the benchmark function experiments to only 50 iterations? In Figure 2, ALEBO clearly does not converge on the Holder Table function. Does this seem fair and reasonable? Was the choice of 50 iterations deliberately designed by the authors?

3. A key issue in high-dimensional BO is the choice of subspace dimension. The related work relies on "whether the low-dimensional subspace can cover the effective subspace of the objective function". Although CEPBO does not explicitly rely on the concept of effective dimensionality, the method is still influenced by the potential complexity of the objective function. In practice, the selection of the low-dimensional space (i.e., the setting of d) directly impacts the algorithm's performance, as d determines the proximity between x and \tilde{x} in the Condensing-Expansion Projection. Although CEPBO relaxes the strong assumption of effective dimensionality, how to select d remains an unresolved issue. How do the authors address this problem?

4. Another key issue in high-dimensional BO is the boundary issue, which is affected by the choice of subspace boundaries and embedding matrix. The embedding matrix in this paper is fixed, so I won't address that further here. However, in Section 3.4, why is the scaling factor chosen as \sqrt{D}? From experience, I know that this is a crucial parameter, yet the authors have fixed it without providing any theoretical justification or hyperparameter analysis. I couldn’t find a relevant explanation for this decision. One of the key factors affecting the embedding methods is the ability to determine the scale of the embedding according to the problem. How do the authors address this problem?

5. The authors conducted experiments on 4 real-world problems. However, these problems are not high-dimensional tasks (the dimensions are 12, 14, 36, and 60 respectively). Could the authors add real-world high-dimensional tasks, such as problems with D > 200?

6. A small question: do all the proofs in the appendix assume that x takes values in the real space \mathbb{R}^D ? If the feasible domain of x is constrained, especially when it is not symmetric around the origin, do these theorems still hold?

7. Based on the above question, intuitively, the Condensing-Expansion Projection may be influenced by the shape of the feasible domain. Could the authors provide additional experiments under different function characteristics, particularly with complex feasible domains? Test functions can be found at https://numbbo.github.io/coco/testsuites/bbob. 

8. Based on the current experimental results, when the function has an intrinsic effective dimension d_e, if the experimental setting uses d > d_e, other methods based on the effective dimension assumption maybe outperform CEPBO, which may affect the practicality of CEPBO. Could the authors add these experiments? If CEPBO can achieve good performance, this paper will be very exciting and practical!
soundness: 2
strengths: - The novel method cleverly circumvents the strong assumption of "effective dimension", which is very exciting. If the doubts in "Questions" can be answered, this article will undoubtedly make a great contribution.

- Sufficient mathematical derivation and proof of the feasibility of Condensing-Expansion Projection.

- Sufficient experiments in real environments. Detailed experimental description in the Appendix.
summary: This paper introduces a high-dimensional Bayesian optimization framework that uses the Condensing-Expansion Projection technology to avoid the assumption of effective dimensions. The new algorithm CEPBO is proposed based on two methods of Gaussian and hash-augmented projection matrices. Experiments show the effectiveness of CEPBO in various optimization tasks.
weaknesses: - There is a notable absence of comparisons with more recent methods. The paper only compares REMBO (2013), HesBO (2019), and ALEBO (2020), which are several years old. It fails to include the latest embedding-based approaches such as CoBO [1], BAxUS [2], MAVE-BO [3], and DSO [4]. Additionally, other high-dimensional Bayesian optimization algorithms not based on embeddings, like Vanilla BO [5], and MCTS-VS [6], are also missing from the comparison. To my knowledge, TurBO [7] has demonstrated strong performance in handling high-dimensional optimization tasks, yet it is not included in the comparative experiments. 

- This paper merely demonstrates the feasibility of CEP (Formulas 2 and 3). Specifically, when the solution x is transformed into the solution \tilde{x} through CEP, the authors prove the effect of d on the difference between x and \tilde{x}. However, the selection of d directly affects the success probability of CEP, but how to determine the appropriate d is not discussed. From another perspective, in the method presented, the solution space is \mathbb{R}^D, and the search subspace is \mathbb{R}^d, which is a subspace of the solution space. The gap between these spaces is enormous, and for the optimal solution x^* \in X, the probability of successfully finding the optimal solution in the subspace has not been proven or theoretically guaranteed, which is the key issue.

- The experiment raises doubts about whether it was deliberately designed to create scenarios favorable to the algorithm. For example, in Figure 2, ALEBO did not converge on the Holder Table function, yet the results were truncated by the authors at 50 iterations. Similarly, the experiments on real-world problems involve dimensions no greater than 100, which cannot be considered as high-dimensional tasks. This raises doubts about whether CEPBO is truly capable of handling high-dimensional problems in practical applications.

- Typos. Although I focused on the content of the article, I still found many typos. This paper needs to be carefully checked, otherwise it cannot be published. For example, there are two "as" in line 144. In line 233 (line 9 of Algo.1), the subscript t of y_t is incorrectly bolded (at the end of this line). 

- The paper was not well prepared, with the above typos and many other details. For example, the text in Figure 3 is too small and completely unreadable.

[1] Advancing bayesian optimization via learning correlated latent space. NeurIPS 2023. 

[2] Increasing the scope as you learn: Adaptive bayesian optimization in nested subspaces. NeurIPS 2022. 

[3] An adaptive dimension reduction estimation method for highdimensional bayesian optimization. 2024. 

[4] Dual-space optimization: Improved molecule sequence design by latent prompt transformer. 2024. 

[5] Vanilla Bayesian Optimization Performs Great in High Dimensions. ICML 2024. 

[6] Monte carlo tree search based variable selection for high dimensional bayesian optimization. NeurIPS 2022. 

[7] Scalable Global Optimization via Local Bayesian Optimization. NeurIPS 2019.

Meta-review: The paper proposes CEPBO, a high-dimensional Bayesian optimization (BO) strategy leveraging random embedding techniques, specifically Gaussian and hashing embeddings. Building on this idea, the authors introduce two algorithms: CEP-REMBO and CEP-HeSBO. Numerical experiments are presented to demonstrate the effectiveness of both algorithms.

While the reviewers agree that the paper is well-written and the proposed approach appears computationally efficient, they raise the following concerns:
- The contribution of the work is viewed as somewhat incremental, described as a `simple migration` of existing techniques (Reviewer 3Z1k).
- The theoretical guarantees are unsatisfactory (Reviewers jdJn and u58t).
- Important baselines are missing, such as BAxUS and Bounce (requested by Reviewer GQqE), as well as REMBO, HeSBO, and ALEBO (requested by Reviewer u58t).

During the rebuttal, the authors were unable to adequately address these concerns or convince the reviewers of the significance of their contribution. As a result, I recommend rejecting the paper.

Decision: Reject