Automated Random Embedding for Practical Bayesian Optimization with Unknown Effective Dimension

1 Introduction

Optimization [Boyd and Vandenberghe, 2004] is widely used in various fields, such as economics [Mehta and Grosan, 2015], machine learning [Freund and Schapire, 1997; Elsken et al., 2019], and reinforcement learning [Qian and Yu, 2021]. It aims to find the global optimal solution x∗ of the objective function f(x) in the D-dimensional search space X ⊂ RD , formally expressed as x∗ = argminx∈X⊂RDf(x). However, in black-box optimization scenarios, the expression of the objective function is unknown [Shahriari et al., 2016], where gradient-based optimization techniques are ineffective. In contrast, the derivative-free optimization methods [Zhou et al., 2019; Shahriari et al., 2016; Yu et al., 2025] can handle these complex optimization problems.

∗Corresponding Author.

Bayesian optimization (BO) [Srinivas et al., 2010; Shahriari et al., 2016; Garnett, 2023] is one of the most valuable derivative-free optimization methods for its excellent performance. However, the curse of dimensionality has persistently remained a critical issue in BO [Shahriari et al., 2016; Wang et al., 2016; Binois and Wycoff, 2022; Santoni et al., 2024]. As the dimension increases, more evaluations of the objective function are required to adequately explore the solution space, making BO challenging to locate the optimal solution efficiently within finite computational resources.

Random embedding (RE) [Wang et al., 2013; Wang et al., 2016; Qian et al., 2016] is an approach to addressing highdimensional optimization tasks with effective dimension. By constructing a mapping between a lower-dimensional subspace and the original search space via an embedding matrix, optimization can be performed in the low-dimensional subspace, thus alleviating the scalability issue for BO methods. This approach exploits the inherent effective dimension of high-dimensional optimization tasks, where the function value is influenced by only a few relevant dimensions. By focusing on these dimensions, random embedding significantly enhances the efficiency and performance of high-dimensional BO within limited resources. However, a critical challenge is how to accurately determine the effective dimension. Selecting an appropriate low-dimensional subspace to perform optimization is crucial for the efficacy of embedding technique: a too-small subspace fails to adequately capture the effective dimension of the function, resulting in a loss of optimal solution, while a too-large subspace diminishes the advantages of the reduced dimensionality provided by random embedding.

However, previously in practice, the dimensionality of the low-dimensional subspace is typically determined via heuristic or trial-and-error approaches. These methods require performing multiple optimizations across various subspaces to achieve a more effective solution, which incurs significant computational costs. Currently, there is no direct method to predict the effective dimension required to capture the fundamental characteristics of the target function [Papenmeier et al., 2022].

Problem. When using BO with RE for high-dimensional optimization tasks with unknown effective dimension, how to automatically determine the appropriate subspace dimension during optimization?

Contribution. To address the aforementioned problem, this paper proposes an effective approach to high-dimensional BO by developing a dynamic shared embedding Bayesian optimization (DSEBO) algorithm, which can automatically expand subspace dimension to handle tasks with unknown effective dimension. The shared embedding technique is introduced to leverage solutions from a low-dimensional subspace within a higher-dimensional subspace, thereby better guiding the initialization of the high-dimensional subspace and accelerating convergence. Based on the technique, DSEBO starts from a lower-dimensional subspace, dynamically determines the next subspace dimension according to the convergence of solutions in different subspaces, and facilitates transitions between various subspaces. The theoretical analysis derives a regret bound for DSEBO, highlighting its ability to balance approximation and optimization errors more effectively than GPUCB. Experiments on high-dimensional synthetic functions and real-world tasks show the effectiveness and superiority of DSEBO. The hyper-parameter experiments illustrate the robustness of DSEBO.

The subsequent sections present the related work and preliminaries, describe the proposed DSEBO method, show the theoretical and empirical results, and conclude the paper.

2 RelatedWork

This section reviews the related work: the high-dimensional optimization algorithms, and the multi-armed bandit (MAB) algorithms used for the subspace dimension selection.

2.1 High-Dimensional Optimization Algorithm

Embedding-based methods define a low-dimensional effective subspace where function values change dramatically, allowing optimization algorithms to operate within the subspace for lower computational costs. Linear embedding methods map low-dimensional points to high-dimensional space via an embedding matrix. Notable works include REMBO [Wang et al., 2016], a foundational method, and SREBO [Qian et al., 2016], which extends REMBO to sequential settings. HesBO [Nayebi et al., 2019] uses hash matrices for linear mapping, SIRBO [Zhang et al., 2019] employs sliced inverse regression to identify the effective dimension, and ALEBO [Letham et al., 2020] provides a comprehensive analysis of the embedding process. Using nested random subspaces to dynamically increase the optimization space from a low dimensionality to a high dimensionality approaching D, BAxUS [Papenmeier et al., 2022] can handle highdimensional tasks. Nonlinear embedding methods use complex functions to map subspaces to the original space, like VAEBO [Gómez-Bombarelli et al., 2018], which employs unsupervised learning to train variational encoders.

Apart from embedding-based methods, there are highdimensional optimization methods that do not rely on subspace embedding. In the BO field, one method is TuRBO [Eriksson et al., 2019], which handles high-dimensional tasks by dividing the optimization space into smaller regions for local optimization. SAASBO [Eriksson and Jankowiak, 2021] identifies and optimizes only on a few important dimensions. DuMBO [Bardou et al., 2024] relaxes additive structure constraints by using decentralized message-passing and a refined acquisition function. MCTS-VS [Song et al., 2022] employs Monte Carlo tree search to iteratively select a subset of variables and optimize them within a low-dimensional subspace. RDUCB [Ziomek and Bou-Ammar, 2023] uses random tree decompositions to build additive Gaussian process (GP) models, leveraging cycle-free pairwise-dimensional interactions for optimization. Recently, SBO-SE [Xu et al., 2025] and VBO [Hvarfner et al., 2024] introduce robust initialization strategies for the length-scale of GP kernel, addressing the vanishing gradient in high-dimensional BO. In the field of evolutionary algorithms, LMMAES [Loshchilov et al., 2019] approximates the covariance with a small set of evolution paths. DCEM [Amos and Yarats, 2020] proposes a differentiable cross-entropy method using a smooth top-k operation.

All these methods rely on special assumptions, such as effective dimension. The failure to meet these underlying assumptions can lead to a significant decline in performance.

2.2 Multi-Armed Bandit

The problem of selecting subspace dimension can be modeled as an MAB problem. Specifically, different candidate dimensions are treated as different arms in the MAB problem, where the convergence value of the optimized function on these dimensions serves as the reward for each arm.

The MAB problem [Sutton and Barto, 2018; Jin et al., 2022] centers on the trade-off between exploration and exploitation. For instance, Softmax [Sutton and Barto, 2018] employs the exponential probability rule for arm selection. Thompson Sampling (TS) [Jin et al., 2022] is a probabilistic model-based approach that samples arms according to their posterior distributions. Additionally, other algorithms like Extreme, Random, ϵ-Greedy, Expectation, Upper Confidence Bound (UCB), and the UCB-E algorithm, which extends the traditional UCB algorithm, are also widely adopted methods in practice.

3 Preliminaries

This section briefly introduces Bayesian optimization (BO), the optimal ϵ-effective dimension, and random embedding to explain the necessary preliminary knowledge and notation.

Bayesian Optimization. BO [Shahriari et al., 2016; Garnett, 2023] is a well-known derivative-free optimization method that strategically leverages prior knowledge to guide optimization. BO first constructs a surrogate model of the objective function, typically a Gaussian process, based on the observed dataset D. With the model, BO estimates the posterior distribution and calculates an acquisition function to balance "exploration" and "exploitation" in the search space X ⊂ RD , thus determining the candidate x ∈ X . A common acquisition function is UCB [Srinivas et al., 2010], defined as αUCB(x) = µt(x) + √κt+1σt(x), where µt(x) estimates the objective function and σt(x) represents model uncertainty. The hyper-parameter κ controls the trade-off between "exploration" and "exploitation" for efficient optimization. Details are provided in the Appendix A and Appendix A-H can be found in https://github.com/X-Xia0828/DSEBO.

Random Embedding. Random embedding [Wang et al., 2016; Wang et al., 2013; Nayebi et al., 2019] is a popular subspace embedding method, which can achieve dimensionality reduction when the high-dimensional optimization tasks have effective dimension (i.e., the function value is influenced by only a few relevant dimensions). However, it is challenging to meet the effective dimension assumption in real tasks. In this case, Qian et al. [2016] propose the concept of optimal ϵ-effective dimension to relax the assumption, defined as:

Definition 3.1 (Optimal ϵ-Effective Dimension [Qian et al., 2016]). For any ϵ > 0, a function f : RD → R is said to have an ϵ-effective subspace Vϵ, if there exists a linear subspace Vϵ ⊆ RD , s.t. for all x ∈ RD , we have |f(x) - f(xϵ)| ≤ ϵ, where xϵ ∈ Vϵ is the orthogonal projection of x onto Vϵ. Let Vϵ denote the collection of all the ϵ-effective subspaces of f, and dim(V) denote the dimension of V. We define the optimal ϵ-effective dimension of f as dϵ = minVϵ∈Vϵ dim(Vϵ).

For a high-dimensional optimization problem x∗ = argminx∈X⊂RDf(x), a random matrix A ∈ RD×d with elements sampled from a Gaussian distribution N (0, σ2 ) embeds the d-dimensional subspace Z ⊂ Rd into the D-dimensional search space X ⊂ RD . The optimizer only needs to optimize z ∈ Z in the low-dimensional subspace, and then embed z into X through the matrix A to get the solution x = pX (Az). Here, pX(Az) = argminx∈X∥x-Az∥2 is to project illegal points (i.e. Az /∈ X) back to the X region. Subsequently, the objective function f is evaluated in the solution x, and the sample point (z, f(pX (Az))) is added to the subspace dataset. The optimizer uses the updated dataset to complete the next optimization iteration. See Appendix A for details.

4 The ProposedMethod

This section introduces the proposed dynamic shared embedding Bayesian optimization (DSEBO), to handle optimization tasks with unknown effective dimension.

4.1 Overview

To automatically identify the appropriate subspace for highdimensional BO tasks, the DSEBO algorithm is proposed, illustrated in Figure 1 with pseudo-code in Appendix B.

As shown in Figure 1, DSEBO operates in three stages: (a) optimizing in the di-dimensional subspace, (b) expanding to a new subspace, and (c) initializing the new subspace. DSEBO starts with a lower dimension dl, iteratively optimizes within the subspace until convergence (the convergence criteria will be introduced later), then expands to a higher-dimensional subspace to continue optimization. By gradually increasing and optimizing each subspace, the objective function is optimized while dynamically expanding the subspace dimension. DSEBO considers the differences in the optimal solutions obtained from each subspace when determining dimensionality changes. It also adjusts the scale of changes during optimization to adapt to functions with different dimensionalities. Besides, DSEBO uses a shared embedding matrix to share evaluation data among different subspaces, allowing data points from low-dimensional subspace to provide better initialization for new subspace, thus conserving the budget.

The following section will explain how data are shared between different subspaces and how dynamic strategy is designed to determine the next subspace dimension.

4.2 Dataset Initialization with Shared Embedding

Optimization is performed sequentially on multiple subspaces while dynamically expanding dimensions. However, independent random matrix mappings prevent sharing sampling points across different dimensional subspaces. Therefore, a proposed shared embedding technique enables the utilization of identical sampling points across different subspaces.

The shared embedding technique maintains a shared matrix S ∈ RD×dh , where D is the dimension of the search space and dh is the dimension of the largest subspace. Each subspace uses a part of this matrix to embed solutions into the search space. Specifically, for a subspace of dimension d, the first d rows of the matrix S form the embedding matrix Ad. This ensures that for any two subspaces Vi and Vj with dimensions di and dj (assuming di < dj), Adi and the first di rows of Adj are identical. Thus, Vi is a subspace within Vj, allowing Vj to share sampled data points from Vi.

Figure 2 illustrates the shared embedding process across different subspaces. A 3-dimensional vector z ∈ R3 is expanded to 5-dimensional z′ ∈ R5 by appending zeros. These vectors are then transformed into the search space RD using matrices A3 and A5, respectively, from the shared embedding matrix S. After embedding, the solutions x and x′ in the search space are identical, allowing them to share the same evaluation, i.e., f (A5z′ ) = f (A3z).

Based on the method, each new subspace uses data from the existing lower-dimensional subspace to initialize its dataset. The initialization algorithm is shown in Appendix C. In the first iteration t = 1, the dataset is empty and initialized with a random point. For dimension expansion, the current dataset D(t) is generated from the previous dataset D(t-1) by appending zeros to each solution vector z to expand it to the new subspace while keeping the original evaluation value y.

Through the proposed shared embedding technique, higherdimensional subspaces can reuse the evaluated data in lowerdimensional subspaces, since the function values of corresponding solutions remain invariant across subspaces due to the connection between subspace embedding matrices.

Algorithm 1 Dynamic Dimension Expanding Strategy

Input: Current dimension d(t) , dimension range [dl, dh] 1: if t ≤ 2 then 2: ∆d(t) = ⌊ dh-dl β ⌋ 3: else 4: Compute the si = - bi+1-bi di+1-di , i ∈ {1, 2, . . . , n - 1} 5: smin, smax ←minn-1 i=1 si,maxn-1 i=1 si 6: if smin = smax then 7: ∆d(t) ←∆d(t-1) 8: else 9: ∆d(t) ← ⌊k∆d(t-1) ⌋, where k = sn-1-smin smax-smin +0.5 10: end if 11: end if 12: d(t+1) =min(d(t) +∆d(t) , dh) Output: The next dimension d(t+1) .

4.3 Dynamic Dimension Expanding Strategy

While the shared embedding technique enables new subspaces to reuse data from lower-dimensional subspaces, identifying optimal switching timing and targets remains challenging.

Intuitively, the subspace dimension should be updated when the current subspace converges. Specifically, if the optimal value in the subspace remains unchanged for T times, the process can be considered converged. The initial value of T is set to ⌊budget/2β⌋, controlled by a hyper-parameter β. To determine whether optimization has converged at the current dimension, T is updated as: T = ⌊(1+(d(t) -dl)/(dh-dl))· budget/2β⌋, where d(t) is the current subspace dimension, dl and dh are the lower and upper bounds of the dimension range. As d(t) increases, so does T . This aligns with the intuition that higher-dimensional subspaces demand more effort to converge. Based on the definition of T, when to update the subspace dimension is solved. Another problem is how much larger the dimension of the new subspace should be.

According to the relationship between subspace dimensions and convergence values, a dynamic dimension expanding strategy is designed to select the next subspace dimension within the specified range [dl, dh]. Starting from a small dimension dl, the strategy dynamically determines the subsequent dimension, and ultimately identifies a subspace where it can converge to an improved solution without excessively larger dimension. To achieve this, the dimensions of the optimized subspace and the corresponding optimal values are recorded as di and bi, where i indicates the i-th optimized subspace, with i ∈ {1, 2, . . . , n} representing that n subspaces have been optimized. Based on di and bi, the dynamic dimension expanding strategy is designed as Algorithm 1. This strategy determines the next dimension at the t-th iteration by calculating the dimension change ∆d(t) . Initially, if fewer than two subspaces have been optimized, ∆d(t) is set to ⌊(dh - dl)/β⌋, as stated in lines 1-2. Otherwise, the slopes of bi with respect to di are calculated according to: si = -(bi+1 - bi)/(di+1 - di), where i ∈ {1, 2, . . . , n - 1}. This equation measures the rate at which the optimal value improves as the dimensionality of the optimized subspace increases, quantifying the improvement of expanding the subspace. si are calculated for minimum optimization and should be inverted for maximum.

Next, a proportion value k is used to determine the change in the current dimension, defined by the formula: k = (sn-1 - smin)/(smax - smin) + 0.5, where smin = minn-1 i=1 si and smax = maxn-1 i=1 si. According to the equation, the most recent slope is min-max normalized to the range [0.5, 1.5] and then used to determine the change in the current dimension. The value of k reflects the impact of increasing the subspace dimension on the convergence value in the current context. If the value of k is within the range [1.0, 1.5], it indicates a significant impact of the dimension on the convergence value; otherwise it suggests a lesser effect. DSEBO then dynamically scales the change in dimension ∆d(t-1) from the previous iteration using the value of k, yielding the current dimension change ∆d(t) , as described in line 9. Subsequently, based on this dimension change, the new dimension is calculated as d(t+1) = min(d(t) +∆d(t) , dh), as shown in line 12.

We would like to emphasize that, unlike BAxUS [Papenmeier et al., 2022], which increases dimensions by splitting existing dimensions and eventually optimizes in the full space, DSEBO adopts the proposed dynamic dimension expanding strategy. Specifically, BAxUS relies on an exponential expansion with a manually specified dimensionality growth rate, whereas DSEBO automatically and nearly linearly expands the subspace dimension within a controllable range [dl, dh], leading to lower computational costs and better scalability.

5 Theoretical Analysis

In this section, we present the regret analysis of the naive GPUCB algorithm and DSEBO. To begin, we define ϵ(d) as the approximation error associated with the d-dimensional subspace, formally expressed as ϵ(d) = minx∈Rd f(Φ(x)) - minz∈RD f(z), where Φ : Rd → RD denotes the embedding that maps a low-dimensional point into the original Ddimensional search space. Using this notation, we derive the simple regret bound for the naive GPUCB algorithm.

Here, simple regret is defined as rf(T) = minTt=1 f(Φ(xt)) - minz∈RD f(z), which measures the difference between the best function value found by the algorithm (after embedding the low-dimensional solution back into the high-dimensional space) and the true global optimum.

Theorem 5.1. Suppose that the search space X is compact and convex with dimension d, and every x ∈ X satisfies ∥x∥∞ ≤ b. For GP sample paths f with an RBF kernel, choose δ ∈ (0, 1), and define β(t) = 2 log (t2 2π2 /3δ) + 2D log (t2dbr√log (4Da/δ)) , where a and b are constants satisfying Pr (supx∈X |∂f/∂xj | > L) ≤ ae-(L/b)2 . By running the GPUCB algorithm with βt using an initialization with a zero mean function and a covariance function k(x, x′ ), the simple regret is bounded by O∗ (2ϵ(d) + √(log T)d+1 /T ), where O∗ omits logarithmic factors.

Due to space limitations, we defer the proof in this section to Appendix D. For DSEBO, the dimensions of the subspaces are updated periodically. Let the number of updates be H, and denote the subspaces in different phases as {Zh}Hh=1 , with dimensions {dh}Hh=1 and durations {Th}Hh=1 . We then present the following theorem. Theorems 5.1 and 5.2 stem from Srinivas et al. [2010] and Qian et al. [2016].

Theorem 5.2. Suppose each subspace Zh is compact and convex, and every x in the subspaces satisfies ∥x∥∞ ≤ b. For GP sample paths f with RBF kernel, pick δ ∈ (0, 1) and define

where a and b are constants such that Pr (supx∈Zh |∂f/∂xj| > L) ≤ ae-(L/b)2 . Running DSEBO with βt for the initialization of a GP with mean function zero and covariance function k(x, x′ ), we obtain a simple regret bound of O∗ (2 ∑Hh=1 ϵ(dh)Th/T + √∑Hh=1 (log Th)dh+1 /T ).

Remarks. We compare the theoretical results of DSEBO and GPUCB. It can be observed that the first term of DSEBO is larger than that of GPUCB, while the second term is smaller. This indicates that DSEBO effectively balances the trade-off between approximation error and optimization error. To illustrate this, assume that the approximation error satisfies ϵ(d′ ) = O∗ ((D - d′ )/D). Consider a common setting where T = 1000, H = 10, d = 20, D = 100, and the dimension of subspaces increasing evenly up to d, substituting these values into the bound yields an approximation error ratio between DSEBO and GPUCB of O∗ (1.25). This implies a modest increase in approximation error for DSEBO compared with GPUCB. However, the optimization error ratio between GPUCB and DSEBO is O∗ (100), indicating a significant reduction in optimization error for DSEBO. This implies that DSEBO sacrifices a little approximation error in exchange for a much lower optimization error to realize a lower total error (i.e., a better trade-off).

6 Experiment

This section evaluates the performance of the proposed DSEBO and shows its effectiveness and superiority through a series of experiments on both synthetic functions and realworld tasks. The code is available in https://github.com/ X-Xia0828/DSEBO.

The Setting of Synthetic Functions. We construct highdimensional objective functions based on synthetic functions meeting the optimal ϵ-effective dimension (as Definition 3.1). Specifically, let f : Rdf → R be a base testing function, with its domain adjusted to [-1, 1]df . The highdimensional synthetic function Fc : RD → R is crafted to simulate the minimization of f, defined by: Fc(x) = f(x1:df - c) - K-1 ∑Di=df+1 (xi - c)2 , where x ∈ RD is the input to Fc, and x1:df denotes the first df dimensions of x. The constant vector c ∈ Rd , filled with the scalar c, is introduced to shift the optimal solution away from the origin. The constant K modulates the influence of dimensions beyond the initial df . Evidently, Fc possesses an optimal ϵ-effective dimensionality df , with ϵ ≤ K-1 . In the experiments, we construct high-dimensional functions with D = 1000, 10000 respectively, de = 30 and K = 10000, based on 6 synthetic functions from http://www.sfu.ca/~ssurjano/optimization.html, including Levy, Griewank, Sphere, and so on. All experiments on synthetic functions are minimum optimization problems.

The Setting of Real-World Tasks. We evaluate DSEBO on three real-world datasets. The first dataset is the Microsoft Learning to Rank (MSLR) [Qin et al., 2010], specifically the MSLR-WEB-10K version, containing over 10000 queries, each with 136 features per website page. The second dataset is Lasso-Hard from LassoBench [Sehic et al., 2022], a 1000dimensional optimization task designed to identify sparse regression coefficients that minimize Lasso regression loss. The third dataset is LIMO [Eckmann et al., 2022], a framework for molecular generation aimed at optimizing specific properties by operating in a 1024-dimensional latent space. Further details of these datasets are provided in the Appendix E. All experiments on real-world tasks are minimum optimization.

The Setting of DSEBO. DSEBO requires specifying the subspace dimension search range [dl, dh], and a hyperparameter β. For any high-dimensional problems, the recommended initial subspace dimension is dl = 5, and the upper boundary of the search range is dh = min(D, 100), which is the setting for all experiments. Given that the performance of the Bayesian optimizer declines sharply for dimensions above 100, the search range is capped at 100. The hyper-parameter β controls the scale of the dimension expansion, and we set β = 12.0. The shared embedding matrix S ∈ RD×dh is initialized with elements independently sampled from the Gaussian distribution N (0, √1/dh).

6.1 Performance of High-dimensional Optimization

In this section, DSEBO is compared against high-dimensional optimization methods under limited resources. These methods include REMBO [Wang et al., 2016], SIRBO [Zhang et al., 2019], HesBO [Nayebi et al., 2019], VAEBO [GómezBombarelli et al., 2018], and ALEBO [Letham et al., 2020], all of which are based on subspace embedding techniques and REMBO serves as an ablated version of DSEBO without the dynamic dimension expanding strategy. We also compare with BAxUS [Papenmeier et al., 2022], which dynamically selects the next subspace dimension. For methods that do not rely on subspace embedding, we conduct TuRBO [Eriksson et al., 2019], SAASBO [Eriksson and Jankowiak, 2021], DuMBO [Bardou et al., 2024], MCTS-VS [Song et al., 2022], RDUCB [Ziomek and Bou-Ammar, 2023], SBO-SE [Xu et al., 2025], LMMAES [Loshchilov et al., 2019], DCEM [Amos and Yarats, 2020] and random search. For further details, refer to Appendix F. All methods are tested on high-dimensional optimization tasks with unknown effective dimensions, with hyper-parameters d = 30, 50 for synthetic functions and d = 50, 80 for real-world tasks. All methods are allocated 500 evaluation budget for optimization unless optimization either exceeds 8 hours of runtime (e.g., ALEBO, VAEBO, etc.) or encounters out-of-memory errors with 16 GB of RAM (e.g., SAASBO). All methods are independently repeated 10 times.

The best-so-far solutions found on partial synthetic functions and real-world datasets are shown in Figure 3 and 4. The horizontal axis represents the number of iterations, with each iteration consuming 1 budget unit. The vertical axis records the best-so-far function value. The remaining detailed results of synthetic functions with D = 1000, all results of synthetic functions with D = 10000 are shown in Appendix G. To further verify DSEBO's capability in handling high-dimensional optimization tasks, we also conduct experiments by adjusting the shifting scalar c and the effective dimension de of the synthetic functions, as shown in Appendix G.

The experimental results show (1) Superiority. Compared with other high-dimensional BO algorithms, DSEBO can find optimal solutions across almost all tasks, including real-world tasks and high-dimensional synthetic functions of different magnitudes. (2) Efficiency. In high-dimensional tasks with unknown effective dimensions, DSEBO dynamically expands the subspace dimension to find the optimal solution within limited resources. This allows DSEBO to achieve the optimal solution with minimal cost, whereas subspace-based methods require multiple complete optimization processes across different subspace dimensions [Wang et al., 2016] and nonsubspace-based methods require optimization in the original high-dimensional space, both consuming significant computational resources. (3) Continuous Improvement. Due to its ability to dynamically expand subspace dimensions, the performance of DSEBO continues to improve when other algorithms have converged. When the optimization process converges in the current subspace, DSEBO can expand to a larger subspace for further optimization, ensuring continuous progress. (4)

Adaptability. DSEBO starts from a lower initial subspace, which makes its initial evaluation values different (such as having a good initial value on synthetic functions while getting poor initial performance on real-world datasets), but DSEBO adapts to the specific tasks and continues to converge towards the optimal solution. (5) Necessity. The experimental results show that some high-dimensional embedding BO algorithms (such as REMBO) have obvious performance differences on different subspaces. This illustrates the necessity of designing a dynamic subspace dimension expanding strategy.

6.2 Performance of Dynamic Dimension Expanding

To further evaluate the performance of the dynamic dimension expanding strategy, we compare a series of MAB strategies, including Extreme Bandits (Extreme), Classic UCB (CUCB) [Auer et al., 2002], ϵ-Greedy [Langford and Zhang, 2007], Softmax strategy [Sutton and Barto, 2018], Successive Halving (S-Halving) [Karnin et al., 2013], UCB-E [Audibert et al., 2010], Thompson Sampling (TS) [Jin et al., 2022], Expectation strategy (Expectation), and Random strategy. Each MAB strategy selects different subspaces for optimization, with dimensions drawn from {10, 20, 30, 50, 70, 90, 100}. A detailed description of these algorithms is provided in the Appendix F. All strategies are allocated a budget of 500 evaluations, each subspace is initialized by one point, and the experiments are independently repeated 10 times. The experimental results on real-world tasks are presented in Figure 5, showcasing the best-so-far solution found (top) and the subspace dimension expansions (bottom). Results for synthetic functions are provided in the Appendix G.

Experimental results show that: (1) Superiority and TailorMade. DSEBO designs a dynamic dimension expanding strategy for high-dimensional BO problems with unknown effective dimensions. Compared with the general MAB strategies, it can converge to better performance on various tasks. (2) Effectiveness of Shared Embedding. Through experimental results on synthetic functions, it can be found that on tasks with particularly high dimensions, random strategy has the worst results, followed by strategies that explore larger subspace dimensions. Unlike DSEBO, other strategies cannot share data to explore different subspace dimensions. Therefore, exploration in different dimensions brings a huge overhead and reduces the convergence efficiency. (3) Reasonable Expansions. The results for four synthetic functions show that when the space dimension is below the effective dimension de, DSEBO rapidly increases it. However, once the effective dimension is exceeded, the growth rate slows down, reflecting the rationality of DSEBO in expanding subspace dimensions.

6.3 Hyper-Parameter Analysis

We conduct hyper-parameter analysis on β and the upper boundary of search range dh to verify the robustness of DSEBO under different hyper-parameter settings. The detailed results and analysis are shown in Appendix H. The hyperparameter analysis verifies that the chosen hyper-parameter values are reasonable, and shows the robustness of the DSEBO across different settings.

7 Conclusion and Discussion

Conclusion. This paper introduces the DSEBO method for automated random embedding in high-dimensional BO with unknown effective dimensions. We propose the dynamic shared embedding BO, which dynamically expands the subspace dimension during optimization. Utilizing a shared embedding matrix, one subspace can share the initial dataset from a lower-dimensional subspace. The dynamic dimension expanding strategy determines the dimension of the next subspace, thereby achieving better optimization performance within limited resources. The theoretical analysis establishes a regret bound for DSEBO, proofing its superior ability to balance approximation and optimization errors compared with GPUCB.

Discussion. Currently, due to the effective dimension being unknown during the optimization process, DSEBO is unable to halt dimension expansion near the effective dimension, which may lead to unnecessary increases in the subspace dimensionality. In the future, we will explore more adaptive strategies to identify the effective dimension and enable dynamic subspace adjustment (not just dimension expansion) and further integrate the dynamic dimension expansion strategy into other high-dimensional optimization methods, such as evolutionary algorithms, to improve optimization efficiency. Furthermore, we will explore the integration of DSEBO with multiple random embeddings [Cartis et al., 2023] or learned embedding from data [Garnett et al., 2014] methods to better address high-dimensional optimization tasks with effective dimension.

Ethical Statement

This work does not include any human subjects, personal data, or sensitive information. All testing datasets utilized are publicly accessible, and no proprietary or confidential information has been employed.

Acknowledgements

The authors would like to thank the anonymous reviewers for their valuable and insightful comments. This work is supported by the National Key Research and Development Program of China under Grant 2024YFC3308503, the National Natural Science Foundation of China (No. 62476091) and Ant Group.