acceptodds
Under review as a conference paper at ICLR 2027

Correlation-Aware Variable Selection for High-Dimensional Bayesian Optimization

Abstract

Bayesian optimization (BO) is a sample-efficient framework for expensive black-box optimization, but its performance often deteriorates in high-dimensional spaces. Variable selection is a natural remedy because it reduces the search to a smaller active subspace. However, existing methods typically rely on axis-aligned importance scores, which do not model how variables act together, making them vulnerable when the objective is governed by correlated groups. We propose Correlation-Aware Variable Selection (CAVS), which learns variable importance from a lightweight Mahalanobis kernel with a low-rank-plus-diagonal structure. This design captures inter-variable correlations while avoiding the quadratic cost of a full metric. We prove that CAVS can obtain a sublinear cumulative regret bound. Experiments show that CAVS remains robust even when the objective is expressed in non-axis-aligned coordinates, where axis-aligned methods degrade, and achieves the best average rank among a comprehensive set of competitive baselines.

Primary area:
optimization
Keywords:
Black-box optimization, High-dimensional Bayesian optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_1MomOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper proposes CAVS, a variable-selection method for high-dimensional Bayesian optimization. It fits a GP with a low-rank-plus-diagonal Mahalanobis kernel and uses the learned metric to score and select variables. The acquisition function is optimized over the selected coordinates, while the remaining coordinates are filled using historical and random candidates. The paper provides a regret analysis and compares CAVS with existing BO methods on eight real-world tasks, alongside synthetic tests of kernel fitting and variable identification under rotation.

Critical strengths
  • The low-rank-plus-diagonal kernel provides a practical way to model correlated directions with fewer parameters than a dense Mahalanobis metric. This addresses a relevant modeling issue under the small evaluation budgets typical of BO.

  • The experiments cover eight real-world tasks, including the 888-dimensional Ant problem, and CAVS achieves the best reported average rank. This provides useful evidence that the method can work across different applications.

Critical weaknesses
  • The main claim of correlation-aware variable selection is not convincingly established. The method largely follows LassoBO, and the ablations mainly show improvements in kernel prediction rather than isolating the benefit of the proposed selection score. The rotation tests also preserve the original active coordinate set and clip out-of-bound inputs, so they do not cleanly demonstrate robustness to general non-axis-aligned active subspaces. This leaves the main motivation and additional contribution insufficiently supported.

  • The optimization evaluation is not strong enough to establish a reliable advantage. The synthetic experiments focus on fitting and variable identification, without controlled end-to-end optimization tests across ambient and effective dimensions. Embedding-based comparisons are limited to ALEBO. BAxUS is not evaluated, and the more recent DSEBO is not discussed, leaving the method’s position relative to these alternatives unclear. Only five seeds are used, and several reported gains are small relative to the variation—for example, HalfCheetah regret is 500 ± 404.4 for CAVS versus 619 ± 426.5 for Vanilla BO. More evidence is needed to distinguish consistent gains from run-to-run variation.

Questions for authors
  • How much of the improvement comes from the more flexible kernel, and how much comes from the selection score? Could you compare different selection scores while keeping the same learned surrogate?

  • The rotation tests only mix the original active coordinates and then clip out-of-bound inputs. What do these tests establish about robustness to non-axis-aligned subspaces? Could clipping itself affect the results?

  • Could you provide end-to-end optimization results on higher-dimensional synthetic functions, such as at 1,000 or 10,000 dimensions? Controlling both ambient and effective dimensions would help clarify where the method works.

  • How stable are the reported gains with only five seeds? Please run more seeds and use t-tests to check whether the improvements are statistically significant, especially on tasks with large variation such as HalfCheetah and Ant.

  • Could you expand the comparison with embedding-based methods, including REMBO [1], HeSBO [2], and DSEBO [3]? Both variable selection and embedding-based search approach high-dimensional optimization through dimensionality reduction, so a broader comparison would help establish the benefit of the proposed approach.

  • What background sample schedule NtN_t was used in the experiments? This affects both exploration and acquisition-optimization cost, but the practical setting is unclear.

[1] Wang et al. Bayesian Optimization in a Billion Dimensions via Random Embeddings. JAIR 2016.

[2] Nayebi et al. A Framework for Bayesian Optimization in Embedded Subspaces. ICML 2019.

[3] Qian et al. Automated Random Embedding for Practical Bayesian Optimization with Unknown Effective Dimension. IJCAI 2026.

9 comments

Thanks for your detailed review and constructive suggestions! Please find our responses below.

W1 & Q1 Contribution of the selection score

W1. The main claim of correlation-aware variable selection is not convincingly established. The method largely follows LassoBO, and the ablations mainly show improvements in kernel prediction rather than isolating the benefit of the proposed selection score.

Q1. How much of the improvement comes from the more flexible kernel, and how much comes from the selection score? Could you compare different selection scores while keeping the same learned surrogate?

Thank you for this helpful suggestion. Following your suggestion, we compare our selection score Mii=wi+∣Ri,:∣22\sqrt{M_{ii}}=\sqrt{w_i+\\|R_{i,:}\\|_2^2} with a diagonal-only baseline, wi\sqrt{w_i}, where wi=li−1w_i=l_i^{-1} is the learned weight of variable ii in the kernel’s diagonal component. This score also aligns with the coordinate-wise derivative bounds used in our subsequent regret analysis. Compared with this baseline, our selection score achieves better rank and group recall changes and better average end-to-end BO performance. With d = 10, its mean active-variable rank change is −5.399, compared with −5.058 for wi\sqrt{w_i} (lower is better), and its mean group recall decreases by 6.55 percentage points, compared with 7.43 percentage points for wi\sqrt{w_i}. Rotation comparison (https://anonymous.4open.science/r/CAVS-re/selection_score_rotation.md) reports these results.

The end-to-end BO ablation further shows that using our selection score improves average optimization performance while keeping the kernel architecture and fitting procedure fixed. Table 4 (https://anonymous.4open.science/r/CAVS-re/selection_score_results.md) reports final regret and average rank, and Figure 11 (https://anonymous.4open.science/r/CAVS-re/selection_score_rank.pdf) shows the average rank trajectory. CAVS achieves the best average BO rank of 1.2, versus 2.2 for wi\sqrt{w_i} and 2.5 for random selection. We evaluate all three variants on eight real-world tasks.

The end-to-end selection-score ablation is now included in Appendix A.9 (Table 4 and Figure 11), with a summary in Section 6.4.

W1 & Q2 Scope of rotation robustness

W1. The rotation tests also preserve the original active coordinate set and clip out-of-bound inputs, so they do not cleanly demonstrate robustness to general non-axis-aligned active subspaces. This leaves the main motivation and additional contribution insufficiently supported.

Q2. The rotation tests only mix the original active coordinates and then clip out-of-bound inputs. What do these tests establish about robustness to non-axis-aligned subspaces? Could clipping itself affect the results?

Thank you for this insightful question. The purpose of Figure 8 is to test whether variable-selection methods can continue to identify important variables when the objective depends on non-axis-aligned combinations of its active variables, with the active coordinate set held fixed. Our results show that CAVS better preserves active-variable rankings under these rotations, achieving the better mean rank change even when clipping is removed. As you pointed out, clipping can affect the results by distorting pairwise distances; CAVS's ranking advantage persists in both clipping-free experiments.

Following Reviewer BRxt's suggestion to test a clipping-free construction, we use two sampling strategies. Let ss denote the number of true active variables, with normalized coordinates zz and original bounds [−1,1]s[-1,1]^s. The shrunken cube restricts sampling to $

−1/s,1/s-1/\sqrt{s},1/\sqrt{s}

^s$ before rotation. For any orthogonal rotation QQ, ∣Qz∣∞≤∣Qz∣2=∣z∣2≤1\\|Qz\\|_\infty\leq\\|Qz\\|_2=\\|z\\|_2\leq1, so every rotated coordinate stays within the original bounds. The unit-ball setting samples uniformly from z∈Rs:∣z∣2≤1\\{z\in\mathbb{R}^s:\\|z\\|_2\leq1\\}, whose domain is invariant under orthogonal rotation.

The shrunken-cube results (https://anonymous.4open.science/r/CAVS-re/rotation_shrunken_cube.pdf) and unit-ball results (https://anonymous.4open.science/r/CAVS-re/rotation_unit_ball.pdf) show that CAVS achieves the best mean rank change in both settings: +7.545 and −2.361, respectively (rotated minus unrotated; lower is better). Its group-recall change is also best in the shrunken cube and better than LassoBO in the unit ball. The revised Figure 8 presents the unit-ball experiment, with protocol details in Appendix A.8.

W2 & Q3 Optimization in higher ambient dimensions

W2. The optimization evaluation is not strong enough to establish a reliable advantage. The synthetic experiments focus on fitting and variable identification, without controlled end-to-end optimization tests across ambient and effective dimensions.

Q3. Could you provide end-to-end optimization results on higher-dimensional synthetic functions, such as at 1,000 or 10,000 dimensions? Controlling both ambient and effective dimensions would help clarify where the method works.

Thank you for this suggestion. Following your suggestion, we conducted end-to-end BO experiments on two synthetic functions at 1,000 and 10,000 ambient dimensions as case studies. CAVS ranks second to DSEBO on Rastrigin30 in 1,000D and achieves a final objective close to HeSBO on Hartmann6 in 10,000D. On Rastrigin30, CAVS reaches −151.9, second to DSEBO (−72.1). On Hartmann6, it reaches 2.61, close to HeSBO (2.62), while MCTS-VS reaches 2.85. Figure 14 (https://anonymous.4open.science/r/CAVS-re/highdim_bo.pdf) shows the optimization trajectories. LassoBO and ALEBO are omitted at 10,000D because of their computational cost, and SAASBO is omitted at both dimensions because of its high computational complexity. These two case studies provide an initial assessment of CAVS at much larger ambient dimensions, complementing our main experiments on problems with hundreds of variables. Optimizing at this scale remains challenging, with room to further improve CAVS's performance.

We have added these high-dimensional case studies in Appendix A.14 (Figure 14) and summarized the results in Section 6.4.

W2 & Q4 Stability and statistical significance

W2. Only five seeds are used, and several reported gains are small relative to the variation—for example, HalfCheetah regret is 500 ± 404.4 for CAVS versus 619 ± 426.5 for Vanilla BO. More evidence is needed to distinguish consistent gains from run-to-run variation.

Q4. How stable are the reported gains with only five seeds? Please run more seeds and use t-tests to check whether the improvements are statistically significant, especially on tasks with large variation such as HalfCheetah and Ant.

Thanks for this important question. CAVS retains the best average rank of 2.9 after expanding the evaluation. On the two tasks you highlighted, it significantly outperforms six baselines on HalfCheetah and five on Ant; it also significantly outperforms twelve baselines on MOPTA08.

Following your suggestion, we expanded the evaluation to ten seeds for every method on all eight tasks. We test per-run final recorded objective values using two-sided Welch t-tests, with Holm correction across the eight tasks for each baseline at a significance level of 0.05. Table 7 (https://anonymous.4open.science/r/CAVS-re/real_world_results.md) reports all task-wise results and significance comparisons. Figure 5 (https://anonymous.4open.science/r/CAVS-re/main_average_rank.pdf) shows CAVS's average rank throughout the evaluation budget. In the expanded comparison, CAVS achieves the best average rank of 2.9, followed by LassoBO at 3.9 and the remaining methods at 4.0–11.5. Together, the expanded seed set and statistical tests support the aggregate performance advantage and identify the task-specific significant gains.

We have updated the ten-seed results in Section 6.3 (Table 1 and Figure 5) and added the statistical comparisons in Appendix A.15 (Table 7).

W2 & Q5 Comparisons with embedding-based methods; more baselines

W2. Embedding-based comparisons are limited to ALEBO. BAxUS is not evaluated, and the more recent DSEBO is not discussed, leaving the method’s position relative to these alternatives unclear.

Q5. Could you expand the comparison with embedding-based methods, including REMBO [1], HeSBO [2], and DSEBO [3]? Both variable selection and embedding-based search approach high-dimensional optimization through dimensionality reduction, so a broader comparison would help establish the benefit of the proposed approach.

[1] Wang et al. Bayesian Optimization in a Billion Dimensions via Random Embeddings. JAIR 2016.

[2] Nayebi et al. A Framework for Bayesian Optimization in Embedded Subspaces. ICML 2019.

[3] Qian et al. Automated Random Embedding for Practical Bayesian Optimization with Unknown Effective Dimension. IJCAI 2026.

Thanks for this valuable suggestion. Following your suggestion, we have now added REMBO, HeSBO, and DSEBO, a strong recent representative of adaptive embedding methods. Across all compared methods, CAVS achieves the best average rank of 2.9, compared with 7.5 for DSEBO, 10.2 for REMBO, and 10.6 for HeSBO. This expanded comparison supports CAVS's strong aggregate performance against both embedding-based and variable-selection methods on these benchmarks. Table 1 (https://anonymous.4open.science/r/CAVS-re/real_world_results.md) provides task-wise results, and Figure 5 (https://anonymous.4open.science/r/CAVS-re/main_average_rank.pdf) shows performance across the evaluation budget.

The expanded baseline comparison is now reported in Section 6.3 (Table 1 and Figure 5).

Q6 Background sampling schedule

Q6. What background sample schedule (N_t) was used in the experiments? This affects both exploration and acquisition-optimization cost, but the practical setting is unclear.

Thanks for pointing this out. The experiments use Nt=5N_t=5 random background vectors per iteration, generated by Latin hypercube sampling following LassoBO. Two history-based vectors constructed from the three best observations supplement these, giving seven background candidates per iteration.

We have clarified the experimental background sampling scheme in Section 4.4, Algorithm 1, and the Background sampling paragraph in Appendix A.6.


We hope our response has addressed your concerns. If we have missed anything, please let us know.

Reviewer_9FF1OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposed correlation-aware variable selection (CAVS) for Bayesian optimization. Using a Mahalanobis kernel that is formulated as the sum of a diagonal and a low-rank matrix, CAVS efficiently captures correlation between individual variables, and avoids the over-fitting problem and computational overhead of a full Mahalanobis kernel. The authors provided theoretical analysis for the effectiveness of CAVS, and verified its performance through numerical experiments.

Critical strengths
  1. The diagonal-and-low-rank formulation of Mahalanobis kernel is sound and practical. It extends beyond ARD RBF to capture inter-variable correlations, and avoids the overhead of a full-rank Mahalanobis kernel.
  2. The authors gave theoretical analysis to show that the cumulative regret of the proposed method is bounded.
  3. Experiments verified that the proposed method is effective and has an advantage over existing methods.
  4. Ablation studies are conducted for important design choices and hyperparameters.
Critical weaknesses
  1. The authors illustrate the importance of correlated variables by rotating the input space and observing performance degradation in existing methods, and they claim that CAVS additionally captures correlations. However, Figure 8 shows that CAVS also exhibits notable performance degradation under input space rotation. This raises the question of whether the performance gain is actually attributed to the correlation-aware nature of CAVS, or is merely a consequence of increasing parameter counts. The paper does not isolate the effect of correlation modeling from the effect of model capacity, so the source of the improvement remains unclear.
  2. The paper lacks an ablation study (or other quantitative measurements) on using full Mahalanobis kernels. The reasons for not using a full Mahalanobis kernel are therefore not sufficiently supported. It is unclear how would a full-rank kernel affect performance and computational cost compared with the kernel used in CAVS.
Questions for authors
  1. (W1) The source of the performance gain of CAVS is unclear. Please address the following questions: Why is CAVS still vulnerable to input space rotation? What are the parameter counts of each method? Can the authors provide experiments, e.g., a parameter-matched ablation, to separate the effect of correlation-aware design from the effect of increased model capacity?
  2. (W1) If using a full Mahalanobis kernel, would performance still degrate when the input space is rotated? Would the rank of R (d) affect robustness of CAVS against input space rotation?
  3. (W2) How much computational overhead and over-fitting risk would a full Mahalanobis kernal introduce in practice? Can the authors provide experiments to quantify this? Even low-dimensional experiments would be informative, if high-dimensional ones are infeasible.
4 comments

Thanks for your thoughtful feedback and valuable suggestions! Please find our responses below.

W1 & Q1 Correlation modeling and model capacity

W1. The authors illustrate the importance of correlated variables by rotating the input space and observing performance degradation in existing methods, and they claim that CAVS additionally captures correlations. However, Figure 8 shows that CAVS also exhibits notable performance degradation under input space rotation. This raises the question of whether the performance gain is actually attributed to the correlation-aware nature of CAVS, or is merely a consequence of increasing parameter counts. The paper does not isolate the effect of correlation modeling from the effect of model capacity, so the source of the improvement remains unclear.

Q1. (W1) The source of the performance gain of CAVS is unclear. Please address the following questions: Why is CAVS still vulnerable to input space rotation? What are the parameter counts of each method? Can the authors provide experiments, e.g., a parameter-matched ablation, to separate the effect of correlation-aware design from the effect of increased model capacity?

Thank you for your valuable question.

The original rotation test included clipping, which distorts pairwise distances and can affect kernel modeling. We therefore repeated the experiment using two clipping-free settings: a shrunken cube (as suggested by Reviewer BRxt) and a uniform unit ball. Both keep the rotated inputs within the bounds without clipping. As shown in the shrunken-cube results (https://anonymous.4open.science/r/CAVS-re/rotation_shrunken_cube.pdf) and unit-ball results (https://anonymous.4open.science/r/CAVS-re/rotation_unit_ball.pdf), CAVS achieves the most favorable mean rank change in both settings.

For the three methods in Figure 8, LassoBO and SAASBO each learn DD coordinate-wise lengthscales. CAVS learns DD diagonal weights and dDdD entries of the low-rank factor, giving (d+1)D(d+1)D kernel-shape parameters, where DD is the ambient dimension and dd is the low-rank dimension. SAASBO also infers one global shrinkage hyperparameter τ\tau, bringing its count to D+1D+1 when this prior hyperparameter is included. We exclude the GP mean, output scale, and observation-noise parameters from these counts because they add only O(1)O(1) scalars, independent of DD and dd, and do not change the parameter-complexity comparison.

To match CAVS’s parameter count, we constructed an equally weighted sum of d+1d+1 ARD kernels (denoted as the ARD-sum kernel), with independently learned lengthscales. The added parameter-matched comparison supports the correlation-aware design: CAVS achieves better mean rank change (−2.361 versus +0.867) and group-recall change (−7.28 versus −8.14 percentage points) than an ARD-sum model with the same parameter count. The ARD-sum model equally weights d+1d+1 ARD kernels with independently learned lengthscales, giving both models (d+1)D(d+1)D parameters.

Table 5 (https://anonymous.4open.science/r/CAVS-re/parameter_matched.md) reports the parameter-matched comparison. These results support the benefit of modeling correlations beyond increasing the parameter count.

The revised rotation analysis and added parameter-matched comparison are reported in Section 6.4 and Appendices A.8 and A.10 (Figure 8 and Table 5).

W1 & Q2 Kernel rank and rotation robustness

W1. However, Figure 8 shows that CAVS also exhibits notable performance degradation under input space rotation.

Q2. (W1) If using a full Mahalanobis kernel, would performance still degrate when the input space is rotated? Would the rank of R (d) affect robustness of CAVS against input space rotation?

Thanks for pointing this out. Yes. Variable identification also degrades with the full Mahalanobis kernel under rotation: the mean active-variable rank worsens by 5.38 positions and group recall falls by 3.96 percentage points. CAVS's ranking performance is robust to the choice of dd, with a more favorable mean active-variable rank change than the full kernel at every tested rank.

We tested d∈5,8,10,15,20d\in\\{5,8,10,15,20\\}, the configuration d=2sd=2s, and a full Mahalanobis kernel, where ss is the number of active variables. The comparison covers the same 22 function–dimension settings as Figure 8 (https://anonymous.4open.science/r/CAVS-re/rotation_unit_ball.pdf), at ambient dimensions of 300 and 500. Both the unrotated and rotated groups use uniform unit-ball sampling in the active coordinates, so no clipping is required.

Figure 12 (https://anonymous.4open.science/r/CAVS-re/rank_sensitivity.pdf) reports the complete rank-sensitivity comparison. CAVS's mean rank change ranges from −5.21 to +0.76 across the tested configurations, compared with +5.38 for the full kernel. Its group-recall changes range from −7.28 to −5.69 percentage points, compared with −3.96 for the full kernel. Together, these results support the robustness of CAVS's ranking advantage over the full Mahalanobis kernel across the tested rank settings.

We have added the kernel-rank comparison in Appendix A.11 (Figure 12) and summarized the findings in Section 6.4.

W2 & Q3 Full Mahalanobis kernel: cost and overfitting

W2. The paper lacks an ablation study (or other quantitative measurements) on using full Mahalanobis kernels. The reasons for not using a full Mahalanobis kernel are therefore not sufficiently supported. It is unclear how would a full-rank kernel affect performance and computational cost compared with the kernel used in CAVS.

Q3. (W2) How much computational overhead and over-fitting risk would a full Mahalanobis kernal introduce in practice? Can the authors provide experiments to quantify this? Even low-dimensional experiments would be informative, if high-dimensional ones are infeasible.

Thank you for this helpful suggestion. At 500 ambient dimensions, the full Mahalanobis kernel takes approximately 17 seconds to fit, compared with 6 seconds for CAVS. The full kernel also exhibits higher held-out prediction error: with 300 training observations, its average normalized test RMSE is 33.3% higher than CAVS's.

For timing, we use Hartmann6 with 300 observations and vary the ambient dimension. Figure 3 (https://anonymous.4open.science/r/CAVS-re/kernel_fitting_time.pdf) shows the full kernel's rapidly increasing fitting cost, while CAVS's fitting time remains comparatively stable. Figure 6 (https://anonymous.4open.science/r/CAVS-re/kernel_time_accuracy.pdf) further compares fitting time and predictive accuracy across 22 diagnostic tasks.

To assess the overfitting risk of the full Mahalanobis kernel, we compare training and test errors on 11 functions embedded in 300D and 500D, using 50, 100, 200, and 300 training observations. Figure 13 (https://anonymous.4open.science/r/CAVS-re/training_test_error.pdf) reports the results. The full Mahalanobis kernel attains lower training RMSE but higher test RMSE at every tested training-set size, indicating a greater tendency to overfit.

Together with the fitting-time measurements, these results support our low-rank-plus-diagonal kernel as an efficient design with stronger predictive generalization.

We have added the training–test error comparison in Section 6.2 and Appendix A.12 (Figure 13), complementing the fitting-time and prediction comparisons in Figures 3 and 6.


We hope our response has addressed your concerns. If we have missed anything, please let us know.

We thank the author for the detailed explanation and comprehensive additional experiments. This has resolved our primary concerns. We would raise the score to 3.

Dear Reviewer 9FF1,

Thanks for your positive feedback! We are glad that our explanations and additional experiments have resolved your primary concerns. We sincerely appreciate your time and constructive feedback, which have helped us improve the paper.

Best regards,

The Authors

Reviewer_eEPzOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Correlation-Aware Variable Selection (CAVS) for high-dimensional Bayesian optimization. The method employs a low-rank-plus-diagonal Mahalanobis kernel to model variable correlations, derives variable importance scores from the diagonal entries of the learned metric, and integrates variable selection with candidate completion to determine the input for the next evaluation. The paper also provides a cumulative regret analysis under the stated assumptions, along with experiments conducted on synthetic tasks and eight real-world benchmarks.

Critical strengths
  1. Kernel design integrates correlation modeling with parameter efficiency. A low-rank-plus-diagonal structure preserves both per-variable scales and correlated directions, while avoiding the quadratic parameter count required by a full, dense metric. The kernel comparisons in Figure 6 also provide empirical support for the trade-off between Gaussian process (GP) fitting time and predictive accuracy.

  2. The experiments cover multiple tasks and incorporate validation at various levels. Table 1 reports the results of five independent runs across eight real-world benchmarks, with CAVS achieving the best average rank. The paper also includes an analysis of variable identification under rotation, as well as sensitivity analyses regarding the low-rank dimension and selection threshold, ensuring that the evaluation is not based solely on final performance metrics.

Critical weaknesses

The connection between rotation robustness and end-to-end Bayesian optimization (BO) performance warrants further investigation. In Section 6.4 and Figure 8, the impact of rotation on variable identification is evaluated primarily through the average rank of true active coordinates and group recall, whereas the end-to-end optimization results presented in Table 1 are derived from real-world benchmarks. Comparing optimization performance on the same set of rotated and unrotated functions would provide a more direct assessment of whether improvements in variable identification translate into lower final regret.

Questions for authors

Regarding the rotated and unrotated functions used in Figure 8, are there any existing end-to-end Bayesian optimization (BO) results or analyses that could further clarify the relationship between improvements in variable identification and the final regret?

3 comments

Thank you for your positive assessment and constructive suggestion! Please find our responses below.

W1 & Q1 Variable identification and end-to-end BO

W1. The connection between rotation robustness and end-to-end Bayesian optimization (BO) performance warrants further investigation. In Section 6.4 and Figure 8, the impact of rotation on variable identification is evaluated primarily through the average rank of true active coordinates and group recall, whereas the end-to-end optimization results presented in Table 1 are derived from real-world benchmarks. Comparing optimization performance on the same set of rotated and unrotated functions would provide a more direct assessment of whether improvements in variable identification translate into lower final regret.

Q1. Regarding the rotated and unrotated functions used in Figure 8, are there any existing end-to-end Bayesian optimization (BO) results or analyses that could further clarify the relationship between improvements in variable identification and the final regret?

Thank you for this important question.

Yes. Our added results show that better active-variable ranking and higher recall lead to better end-to-end BO performance, and poorer ranking or recall lead to worse performance. We evaluate rotated and unrotated functions and compare their end-to-end BO outcomes with the identification diagnostics.

Table 6 (https://anonymous.4open.science/r/CAVS-re/identification_and_bo.md) reports the corresponding identification and optimization changes. On Sinprod4, active-variable rank improves by 6.04 positions and group recall increases by 8.89 percentage points, alongside a 16.6% normalized gain in final BO performance. On TwinHartmann6, both identification measures deteriorate alongside a normalized BO change of −30.1%. Coupledquad exhibits a substantial recall drop, while Rastrigin10 exhibits a substantial ranking deterioration; both show lower final BO performance. Thus, ranking and recall together indicate whether the search correctly prioritizes the influential variables and retains them, which is essential for effective optimization.

The added end-to-end BO results and identification diagnostics are now discussed in Section 6.4 and Appendix A.13 (Table 6).


We hope our response has addressed your concerns. If we have missed anything, please let us know.

Thank you for the response and additional experiments. The new results address my concern regarding the relationship between variable identification and end-to-end BO performance. I maintain my positive assessment and original rating.

Dear Reviewer eEPz,

Thank you for your positive feedback. We are glad that the additional experiments addressed your concern about the relationship between variable identification and end-to-end BO performance. Your suggestion helped us strengthen the evaluation, and we appreciate the time and care you devoted to reviewing our paper.

Best regards,

The Authors

Reviewer_BRxtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Correlation-Aware Variable Selection for high-dimensional Bayesian optimization, using a low-rank-plus-diagonal Mahalanobis kernel to capture correlations among variables and identify important dimensions efficiently.

Critical strengths
  • The motivation is clear: axis-aligned importance scores such as ARD lengthscales cannot represent correlated active groups. The low-rank-plus-diagonal Mahalanobis kernel, M = diag(ℓ⁻¹) + RR⊤, captures correlations with linear rather than quadratic parameter cost and yields a natural importance score (Sections 1, 4).

  • The empirical evaluation is broad: eight real-world benchmarks from 16D to 888D (e.g., MOPTA08, Lasso-DNA, Ant, MSLR) against ten baselines spanning non-selection, variable-selection and full-space methods. CAVS achieves the best average rank (Section 6; Table 1).

  • The design choices are supported by ablations. The full kernel attains the lowest normalized RMSE across 22 diagnostic tasks compared with diagonal-only and low-rank-only variants (Fig. 6), and performance is stable across the low-rank dimension d and the threshold α (Appendices A.4–A.5).

Critical weaknesses
  • Theorem 5.1 and Assumption 5.1 are stated for a single metric M, but Algorithm 1 (line 5) refits M at every iteration by penalized marginal likelihood on adaptively collected data. The proof (Appendix A.2) imports LassoBO's GP-UCB concentration results by substituting √M_ii for √ρ_i and does not address data-dependent kernel hyperparameters. The paper never states whether M is a fixed ground-truth metric or the running estimate, so the bound is not shown to hold for the algorithm as run.

  • The rotation test rotates only the active block, "preserving the relevant coordinate set" (Section 6.4; Appendix A.8). This is reasonable for variable selection, but it contradicts the claims that rotation "destroys its axis-aligned sparsity structure" (Section 1, Fig. 1) and "break[s] axis-aligned sparsity of active variables" (Appendix A.8). The active subspace stays axis-aligned; only the structure within the group changes. Moreover, rotated inputs are clipped to the domain before evaluation (Appendix A.8), which breaks isometry, so the claimed preservation of difficulty and distances is unverified.

Questions for authors
  1. Is M in Assumption 5.1 and Theorem 5.1 the true metric or the per-iteration estimate (call it M_t)? If the former, how does selection based on the estimate enter the bound? If the latter, what assumptions keep the UCB confidence bounds calibrated under data-dependent hyperparameters?

  2. How often does clipping occur (as a fraction of evaluated points, per function and dimension)? Do the Fig. 8 results persist under a clipping-free construction, e.g., shrinking the domain before rotating?

3 comments

Thanks for your careful reading and valuable comments! Please find our responses below.

W1 & Q1 Oracle-kernel regret analysis

W1. Theorem 5.1 and Assumption 5.1 are stated for a single metric M, but Algorithm 1 (line 5) refits M at every iteration by penalized marginal likelihood on adaptively collected data. The proof (Appendix A.2) imports LassoBO's GP-UCB concentration results by substituting √M_ii for √ρ_i and does not address data-dependent kernel hyperparameters. The paper never states whether M is a fixed ground-truth metric or the running estimate, so the bound is not shown to hold for the algorithm as run.

Q1. Is M in Assumption 5.1 and Theorem 5.1 the true metric or the per-iteration estimate (call it M_t)? If the former, how does selection based on the estimate enter the bound? If the latter, what assumptions keep the UCB confidence bounds calibrated under data-dependent hyperparameters?

Thank you for this valuable question. In Assumption 5.1 and Theorem 5.1, MM denotes the fixed true metric M∗M^*. The per-iteration estimate M^t\widehat M_t enters the bound through the selected coordinate set ItI_t: the bound measures the true importance left outside that set, ∑i∈[D]∖ItM∗_ii\sum_{i\in[D]\setminus I_t}M^*\_{ii}. Thus, selecting coordinates with larger true importance reduces the selection-dependent term and tightens the bound.

To make the role of variable selection explicit, we separate the regret bound into two components using the notation of Corollary 5.1:

RT≤βTC1TγT+π26⏟GP-UCB terms under the fixed kernel+Cc0∑t=1T∑i∈[D]∖ItM∗_ii,T12−1n(D−1)⏟variable selection and candidate completion term.R_T\leq\underbrace{\sqrt{\beta_T C_1T\gamma_T}+\frac{\pi^2}{6}}_{\text{GP-UCB terms under the fixed kernel}}+\underbrace{C\sqrt{c_0}\sqrt{\sum_{t=1}^T\sum_{i\in[D]\setminus I_t}M^*\_{ii}}\\,T^{\frac12-\frac1{n(D-1)}}}_{\text{variable selection and candidate completion term}}.

For the selection-dependent component, sublinearity does not require accurate variable selection. The second component can be bounded for any adaptive selection sequence. Specifically, let m∗=max⁡i∈[D]M∗_iim^*=\max_{i\in[D]}M^*\_{ii}, then,

∑t=1T∑i∈[D]∖ItM∗_ii≤Ttr⁡(M∗)≤TDm∗.\sum_{t=1}^T\sum_{i\in[D]\setminus I_t}M^*\_{ii}\leq T\operatorname{tr}(M^*)\leq TDm^*.

Combining this bound with the increasing background schedule in Corollary 5.1, the second component is O(T1−1/(n(D−1)))=o(T)O(T^{1-1/(n(D-1))})=o(T). This establishes sublinear cumulative regret under the oracle-kernel assumptions for any adaptive sequence ItI_t. More accurate variable selection further improves the bound through smaller omitted importance.

We analyze the true kernel for two reasons. First, this is a standard setting in BO regret analysis. Specifically, we adopt the classical known-kernel setting of GP-UCB [1]; this GP-UCB-based framework also underlies variable-selection analyses such as MCTS-VS [2] and LassoBO [3]. In our analysis, f∼GP(0,kM∗)f\sim\mathcal{GP}(0,k_{M^*}), and the same fixed kernel kM∗k_{M^*} constructs the posterior confidence bounds and controls cumulative posterior variance through γT\gamma_T.

Second, existing guarantees for data-dependent hyperparameters rely on specific adaptation mechanisms and assumptions. For example, A-GP-UCB [4] progressively expands the function class in an RKHS setting, while LB-GP-UCB [5] introduces candidate length scales over time and uses regret balancing to select among them. These works require specific algorithmic modifications that our method does not incorporate, so we analyze a fixed oracle metric rather than the per-iteration estimate M^t\widehat M_t.

We have clarified the oracle-kernel assumption and the role of estimated metrics in Section 5 and Appendix A.2, and updated the Abstract accordingly.

[1] Srinivas et al. Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting. IEEE Transactions on Information Theory, 2012.

[2] Song et al. Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization. NeurIPS 2022.

[3] Hoang et al. High Dimensional Bayesian Optimization using Lasso Variable Selection. AISTATS 2025.

[4] Berkenkamp et al. No-Regret Bayesian Optimization with Unknown Hyperparameters. JMLR 2019.

[5] Ziomek et al. Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal. NeurIPS 2024.

W2 & Q2 Clipping and rotation robustness

W2. The rotation test rotates only the active block, "preserving the relevant coordinate set" (Section 6.4; Appendix A.8). This is reasonable for variable selection, but it contradicts the claims that rotation "destroys its axis-aligned sparsity structure" (Section 1, Fig. 1) and "break[s] axis-aligned sparsity of active variables" (Appendix A.8). The active subspace stays axis-aligned; only the structure within the group changes. Moreover, rotated inputs are clipped to the domain before evaluation (Appendix A.8), which breaks isometry, so the claimed preservation of difficulty and distances is unverified.

Q2. How often does clipping occur (as a fraction of evaluated points, per function and dimension)? Do the Fig. 8 results persist under a clipping-free construction, e.g., shrinking the domain before rotating?

We thank the reviewer for this insightful question. Under the original full-domain sampling, clipping occurs for 43.9%–83.9% of points, depending on the function and ambient dimension. The ranking advantage reported in Figure 8 also persists without clipping: CAVS achieves the best mean active-variable rank change under both clipping-free settings, a shrunken cube (as you suggested) and a uniform unit ball.

The clipping-frequency table (https://anonymous.4open.science/r/CAVS-re/clipping_frequency.md) reports the fractions for each function and ambient dimension. Across the tested function–dimension settings, 43.9%–83.9% of evaluated points require clipping. We count a point as clipped if at least one rotated active coordinate falls outside its original bounds. Across all synthetic tasks, the orthogonal transformation acts on the union of the true active coordinates, while inactive coordinates remain unchanged.

To evaluate rotation without clipping, we use two sampling strategies in normalized active coordinates, with ss denoting the number of true active variables. The first samples from the shrunken cube $

−1/s,1/s-1/\sqrt{s},1/\sqrt{s}

^s$: for any orthogonal matrix QQ, ∣Qz∣∞≤∣Qz∣2=∣z∣2≤1\\|Qz\\|_\infty\leq\\|Qz\\|_2=\\|z\\|_2\leq1, so the rotated inputs stay within the original bounds. The second samples uniformly from the unit ball z:∣z∣2≤1\\{z:\\|z\\|_2\leq1\\}, which is invariant under orthogonal rotation.

As shown in the shrunken-cube results (https://anonymous.4open.science/r/CAVS-re/rotation_shrunken_cube.pdf) and unit-ball results (https://anonymous.4open.science/r/CAVS-re/rotation_unit_ball.pdf), CAVS's mean rank changes are +7.545 and −2.361, respectively, the best among the compared methods in both settings (lower is better). Its group-recall change is also best in the shrunken cube and better than LassoBO in the unit ball. These clipping-free results confirm that CAVS's advantage persists under the revised rotation settings.

The revised manuscript presents the unit-ball experiment in Figure 8 (https://anonymous.4open.science/r/CAVS-re/rotation_unit_ball.pdf) and describes its sampling and rotation protocol in Appendix A.8.


We hope our response has addressed your concerns. If we have missed anything, please let us know.

Dear Reviewer BRxt,

Thank you again for your careful review and helpful comments. With approximately 24 hours remaining in the discussion period, we would like to briefly follow up on our rebuttal.

In response to your concerns, we have:

  • Clarified the fixed oracle-kernel assumptions and how estimated variable selection enters the regret bound through the true importance of omitted coordinates.
  • Reported clipping frequencies and added two clipping-free rotation experiments: a shrunken cube, following your suggestion, and a uniform unit ball. CAVS achieves the best mean active-variable rank change in both settings. We also revised the wording to clarify that these tests rotate within the active coordinates.

We would appreciate hearing whether these responses have addressed your concerns. If any points remain unclear, we would be happy to clarify them before the discussion closes. Thank you again for your time!

Best regards,

Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

Dear Reviewers and Area Chair,

Thank you for your careful reviews and constructive feedback. We highlight the main changes in red in the revised manuscript and summarize them below.

Oracle-kernel regret analysis (BRxt). We clarified that the analysis uses a fixed true metric. The per-iteration estimate enters the regret bound through the selected coordinate set, and the bound measures the true importance left outside that set (Abstract, Section 5, Appendix A.2).

Clipping and rotation robustness (BRxt, 9FF1, 1Mom). The original rotation setup required clipping for 43.9%–83.9% of evaluated points. We revised the sampling procedure to keep rotated inputs within bounds and reran the experiments under two clipping-free settings, a shrunken cube and a uniform unit ball. CAVS retained the best mean active-variable rank change in both settings (Section 6.4, revised Figure 8, Appendix A.8).

Variable identification and end-to-end BO (eEPz). The added experiments connect variable identification to final BO performance on four synthetic tasks. On Sinprod4, better active-variable ranking and higher group recall accompanied better final performance. On the other three tasks, worse ranking or lower recall accompanied poorer final performance. These results support the role of active-variable identification in CAVS and show why ranking and recall are useful together when interpreting changes in final regret (Section 6.4, Appendix A.13, Table 6).

Correlation modeling and model capacity (9FF1). At the same parameter count, CAVS preserved active-variable rankings better than the ARD-sum kernel and had a smaller drop in group recall, supporting the benefit of modeling correlations. The full Mahalanobis kernel preserved recall better, while CAVS better preserved rankings across all tested ranks. CAVS also fit nearly three times faster at 500 ambient dimensions and achieved lower average test RMSE at every tested training-set size (Section 6.2, Appendices A.10–A.12).

Contribution of the selection score (1Mom). With the kernel architecture and fitting procedure fixed, our proposed score achieved the best average rank of 1.2, versus 2.2 for the diagonal score and 2.5 for random selection. This ablation shows that our proposed selection score contributes to CAVS’s end-to-end BO performance (Section 6.4, Appendix A.9, Table 4).

Expanded BO evaluation (1Mom). We added REMBO, HeSBO, and DSEBO and expanded the main evaluation to ten seeds. CAVS retained the best average rank of 2.9. The Welch tests with Holm correction show significant gains over 12 baselines on MOPTA08, six on HalfCheetah, and five on Ant. In two new synthetic case studies, CAVS ranked second to DSEBO on 1,000D Rastrigin30 and achieved a final objective close to HeSBO on 10,000D Hartmann6. We also specified the background sampling schedule (Section 6.3, Appendices A.6 and A.14–A.15).

Follow-up experiments with larger active sets (1Mom). We extended the clipping-free rotation tests to active blocks of up to 200 coordinates. CAVS achieved more favorable average changes in rank and recall than LassoBO. At 150 evaluations, CAVS achieved better mean final objectives on all three 1,000-dimensional BO tasks, with significant gains on Rastrigin30 and Rastrigin300 after Holm correction.

We address each reviewer’s questions in detail in the individual replies. Thank you again for your time and consideration.

Best regards,

Authors of Submission 30644

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.