Bayesian optimization tunes expensive black-box systems by fitting a Gaussian process (GP), a probabilistic model that predicts a function value and its uncertainty at any input, and then querying where the model expects gains. Exact GPs cost cubic time in the number of observations. The standard fix summarizes the data with a few hundred "inducing points," which are learned pseudo-observations. In high dimensions this fix breaks down, because a hundred points cannot cover a 300-dimensional box. Many real high-dimensional problems depend on only a handful of coordinates. We argue that this sparsity is what decides whether a small inducing budget is enough. If the model can learn cheaply, from the compressed model itself, which coordinates matter, then the number of inducing points needed should grow with the number of relevant coordinates $s$ and not with the ambient dimension $D$. Wrongly including extra coordinates should cost inducing points exponentially, and wrongly excluding real ones should cost regret linearly.
The proposal is a single-stage algorithm, Sparse-Support Variational BO. It learns sparse relevance weights inside a scalable variational GP, prunes coordinates with a two-step threshold adapted from sparse linear bandits, and sizes its inducing budget to the estimated support. We pair it with a regret analysis showing how sparsity, the size of the inducing budget, and support-recovery errors trade off against each other. The target setting has not been served before: sparse, high-dimensional problems with 5,000 to 50,000 evaluations. At that scale exact-GP sparse methods cannot run, and scalable methods ignore sparsity.
Core Claim
A variational GP with automatic relevance determination (ARD), meaning one length scale per coordinate, already ignores coordinates whose length scale is very long. The positions of inducing points along those coordinates then do not matter. So the real bottleneck is not where the inducing points sit. The bottleneck is whether the relevance weights can be estimated correctly and cheaply at large sample sizes, and how many inducing points the resulting kernel needs.
Our central claim has two parts. For a squared-exponential ARD kernel whose estimated support is $\hat S$, the inducing budget $m$ needed to keep the variational approximation error below $\epsilon$ grows roughly like $(\log n)^{|\hat S|}$, where $n$ is the number of observations. This follows because the eigenvalues of a smooth kernel restricted to $|\hat S|$ coordinates decay at an $|\hat S|$-dimensional rate. The corresponding cumulative regret decomposes as
$$R_T \;\lesssim\; \sqrt{T\,\beta_T\,\gamma_T(s)} \;+\; T\,\epsilon_m \;+\; C_{\text{supp}}\, s\log D ,$$
where $T$ is the number of rounds, $\gamma_T(s)$ is the maximal information gain of the kernel restricted to $s$ coordinates, and $\beta_T$ is the usual confidence-width multiplier from GP upper-confidence-bound analysis (the source of the square-root term). $\epsilon_m$ is the per-round bias from compression with $m$ inducing points. The last term is the price of support recovery, whose $s\log D$ form comes from compressed-sensing sample complexity.
The claim is falsifiable. At fixed $s$, the inducing budget our method needs should stay flat as $D$ grows from 50 to 1,000. The budget needed by ambient-space variational BO should not stay flat.
What Already Exists and Where This Differs
Three lines of work connect pairs of the three directions, and none connects all three.
The first line exploits sparsity with exact GPs, which caps it at small evaluation budgets. High-dimensional Bayesian optimization with sparse axis-aligned subspaces (SAASBO) puts a horseshoe-type shrinkage prior on inverse length scales and samples it with Hamiltonian Monte Carlo. That costs 20–30 seconds per step and limits it to roughly 500 evaluations. High Dimensional Bayesian Optimization using Lasso Variable Selection (LassoBO) instead adds an $L_1$ penalty to inverse length scales. It proves that these bound partial derivatives and gives sublinear regret, but it has no explicit $s\log D$ rate and still pays cubic cost. High-Dimensional Gaussian Process Bandits (SI-BO) estimates the subspace once, then commits to it. Its regret is polynomial in $D$, and it shows that a misaligned subspace inflates the function's complexity permanently. These papers supply our relevance-learning mechanism. We differ by making relevance learning run inside a compressed model and by re-estimating it continually instead of freezing it.
The second line scales GPs but ignores sparsity. Approximation-Aware Bayesian Optimization replaces the usual variational objective with the Expected Utility Lower Bound (EULBO). This objective jointly chooses inducing points, hyperparameters, and the next query so that the limited budget concentrates where decisions are made. With trust regions it scales to 80,000 evaluations in 256 dimensions. It gives no regret theory and optimizes inducing points in the full ambient space. We reuse EULBO as our training objective and add the one ingredient it lacks.
The third line consists of the numerical and theoretical constraints. Understanding High-Dimensional Bayesian Optimization (MSR) shows that many high-dimensional failures come from length scales initialized too short, which flattens the likelihood surface. It shows that scaling the initialization by $\sqrt{D}$ and perturbing about 20 random coordinates near the incumbent often matches specialized methods. We adopt its initialization, because sparse relevance learning in a variational model will otherwise stall in the same flat region.
When Do Neural Networks Outperform Kernel Methods? motivates the whole project. It shows that fixed kernels suffer the full curse of dimensionality when inputs are isotropic, and query points spread over a box are close to isotropic. Learned ARD relevance is the one axis-aligned form of "feature learning" a GP can afford, and we treat it that way.
On the bandit side, Thresholded Lasso Bandit supplies the pruning rule. It first applies a threshold, then applies a second threshold set by the size of the first support, which suppresses false positives. That paper also claims greedy play suffices under context diversity. Information Directed Sampling for Sparse Linear Bandits contradicts this claim in data-poor regimes, where it shows explicit information-seeking is needed. We address the contradiction head-on: our algorithm spends a small, explicit exploration allowance on candidate-inactive coordinates. The size of that allowance is a controlled experimental variable, not an assumption.
Research Program
The algorithm maintains a variational GP trained with EULBO inside a trust region. Its kernel is an ARD kernel whose inverse length scales $\rho_i = 1/\ell_i$ carry a shrinkage penalty added to the variational bound. This is the LassoBO penalty moved into the $\mathcal{O}(nm^2)$ objective. Length scales start at MSR's scaled value.
Every $K$ rounds, the algorithm applies two-step thresholding to $\rho$. The first threshold removes clearly inactive coordinates. The second threshold is set from the size of the first support, following the Thresholded Lasso logic, and removes false positives.
Coordinates judged inactive are handled by imputation. With probability $1-\eta$ they are fixed at the incumbent value, and with probability $\eta$ they are resampled, which reuses LassoBO's exploitation and exploration subspaces. Resampling keeps weak evidence flowing about dropped coordinates, so false negatives can be undone rather than becoming permanent as in SI-BO.
The inducing budget follows the estimated support size. The target is $m = c\,(\log n)^{|\hat S|}$, capped by compute. The inducing points themselves are optimized only in the retained coordinates. When the support changes, the inducing points are re-initialized from the current data projected onto the new support.
The theory work proves the decomposition above. It requires two conditions: support recovery succeeds after $\mathcal{O}(s\log D)$ informative rounds under a margin condition on the smallest active relevance, and the variational bias $\epsilon_m$ is controlled by the tail eigenvalues of the kernel restricted to $\hat S$. The analysis also quantifies the cost of each error type. Each false-positive coordinate multiplies the required $m$ by roughly $\log n$. Each false negative adds a bias term linear in $T$, which the exploration rate $\eta$ trades against a regret cost of order $\eta T$. We are not claiming a minimax-optimal rate. The deliverable is a bound whose dependence on $D$ enters only through the $s\log D$ term.
Baselines
The naive reference point is random search, together with ELBO-trained variational BO in the full ambient space with a standard initialization. These show what happens when neither sparsity nor decision-awareness is used.
The strongest existing competitor for long horizons is EULBO variational BO with trust regions, from Approximation-Aware Bayesian Optimization. It is the only cited method demonstrated at 10,000–80,000 evaluations in up to 256 dimensions. That paper reports that EULBO reached standard variational-GP reward levels with up to 10 times fewer evaluations, but no reported absolute result was found on Lacuna for its scores on Rover, Lasso-DNA, or the Guacamol tasks. We will therefore run it ourselves with the authors' settings. To isolate our ingredient, we will give it MSR's scaled initialization and the same ARD kernel without the penalty or thresholding. Both methods get identical inducing budgets at matched wall-clock time, identical trust-region rules, and the same tuning budget of a fixed small grid on the learning rate. Beating it means lower median regret at 5,000 and 20,000 evaluations across 20 seeds with non-overlapping interquartile ranges, or the same regret with at least 2 times fewer inducing points.
For short horizons, the strongest sparse competitors are SAASBO, LassoBO, and MSR. We run them up to the largest $n$ each can reach within the same per-step wall-clock limit, and we report where each stops.
On LassoBench Leukemia, CMA-ES is the reference evolutionary method. LassoBench reports an MSE of 0.015 for it, a 75% improvement over the best gradient-based baseline. Matching or beating 0.015 is our target there.
Three ablations isolate our contributions. The first freezes the support after an initial phase (SI-BO style) to test continual re-estimation. The second replaces two-step thresholding with a single threshold to test false-positive control. The third fixes $m$ instead of sizing it to $|\hat S|$.
Why not just…?
Why not just run LassoBO or MSR to pick the relevant coordinates, then fit an ordinary variational GP on them? This is the most serious threat, and we take it seriously. The weakness is that the selection step needs exact marginal likelihoods, so it is cubic in $n$. It can only be run on a subsample or early data, which makes it a frozen two-stage method. SI-BO's own analysis shows that frozen subspace errors inflate the function's complexity for the rest of the run. Our frozen-support ablation implements exactly this pipeline, with selection performed by LassoBO on the first 500 points. If it matches the full method on the long-horizon runs, then continual re-estimation is unnecessary, and the contribution shrinks to the theory and the inducing-budget rule. We will report that outcome plainly.
Why not just rely on trust regions, whose small volume already avoids the curse of dimensionality? LassoBO reports reaching lower regret than TuRBO significantly faster on Levy and Ackley at $D=300$. Sparse Bayesian optimization reports that TuRBO adjusted all parameters densely on 50-dimensional Hartmann6. Neither result was measured at horizons beyond a few thousand evaluations, where trust regions could plausibly catch up. Our dimension sweep answers this directly. If trust-region EULBO needs the same inducing budget as our method as $D$ grows, sparsity adds nothing.
Why not just use MSR's random coordinate perturbation, which already exploits sparsity by accident? Random perturbation succeeds when inactive coordinates have optima at the domain boundary, as MSR itself shows for Mopta08 and Lasso-DNA. The chance that a random pick contains the right active set falls combinatorially with $D$. Random perturbation also still runs on an exact GP. We test this with interior-optimum variants of the synthetic benchmarks, where the inactive coordinates' best values are shifted away from 0 and 1. Our method should hold up there, and MSR should degrade.
Proposed Experiments
The decisive check is the inducing-budget scaling sweep. We embed Hartmann6 and Levy with $s$ active coordinates, for $s \in \{2,4,6,8\}$, into $D \in \{50, 100, 300, 1000\}$, with interior optima. For each method we find the smallest $m$ that reaches a fixed simple regret within 10,000 evaluations. The core claim predicts three things: $m$ flat in $D$ and growing steeply in $s$ for our method; $m$ growing in $D$ for ambient EULBO; and a jump in required $m$ when we inject $k$ spurious active coordinates by overriding the threshold. If $m$ grows with $D$ for our method, the claim fails.
A second check probes the tension between greedy play and information-seeking exploration. We sweep the exploration rate $\eta$ from 0 to 0.2 on problems where one active coordinate has a small effect. Following the IDS paper, we predict that $\eta = 0$ loses that coordinate permanently. Following Thresholded Lasso, we predict that $\eta = 0$ is fine when all effects are large.
Real benchmarks test transfer. These are Rover (60 dimensions), Lasso-DNA (180), MuJoCo Hopper (33) and Ant (888), and LassoBench synthetic up to 1,000 dimensions, plus Leukemia (7,129) and RCV1 (19,959), the latter being where several methods ran out of memory. Guacamol Osimertinib and Fexofenadine MPO in the 256-dimensional latent space serve as a negative control, because their latent coordinates need not be sparse. On those tasks we expect only parity with EULBO, and a large win there would suggest our gains come from something other than sparsity.
Across all runs we report median best value versus evaluations, wall-clock time per step, the estimated support size over time, and precision and recall of support recovery on the synthetic problems, where the true support is known.
References
- High-dimensional Bayesian optimization with sparse axis-aligned subspaces
- High Dimensional Bayesian Optimization using Lasso Variable Selection
- High-Dimensional Gaussian Process Bandits
- Approximation-Aware Bayesian Optimization
- Understanding High-Dimensional Bayesian Optimization
- When Do Neural Networks Outperform Kernel Methods?
- Thresholded Lasso Bandit
- Information Directed Sampling for Sparse Linear Bandits
- LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso
- Sparse Bayesian optimization