Correlation-Aware Variable Selection for High-Dimensional Bayesian Optimization

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.