Cheap Evaluations for Choosing Search Directions in High-Dimensional Bayesian Optimization

Bayesian optimization tunes expensive black-box systems by fitting a statistical model of past results and then searching that model for the next point to try. The search uses an "acquisition function," a score that trades off predicted quality against uncertainty. In hundreds of dimensions, maximizing that score becomes a hard problem of its own. A common fix is to maximize it only inside a small random slice of the space, a low-dimensional subspace, and to change the slice every iteration. The slices are usually drawn blindly, however, so most of the expensive evaluation budget is spent searching directions in which the objective barely changes. Many real problems also come with a cheap, imperfect version of the objective: a coarse simulation, a data subsample, or a smaller model. Methods that use these cheap versions mostly treat them as stand-ins for the true function value. They model the cheap-to-expensive relationship point by point, and they have been tested only in a handful of dimensions.

This note proposes using cheap evaluations for a different purpose: to rank candidate subspaces before any expensive query is spent. The observation behind it is that a biased low-fidelity function can predict the wrong value at a point and still be informative about how much the objective varies along a direction. Taking differences within a subspace cancels much of a smooth bias. We therefore spend cheap queries on screening many randomly rotated candidate slices. We keep the few where the cheap function shows the most room for improvement, and we maximize the expensive-fidelity acquisition function only inside those. One slot per iteration stays random, as a "doubt" check that detects when the cheap proxy has become misleading.

Core Claim

In high-dimensional problems with a cheap but biased proxy, the cheap budget is better spent choosing which subspaces the expensive acquisition step searches than modeling the proxy-to-target relationship at individual points. The resulting method should beat uniform random subspaces at equal total cost. It should also beat full-space multi-fidelity Bayesian optimization once the dimension reaches the hundreds. The gain should shrink in a predictable way as the proxy's sensitive directions rotate away from the target's, and an online check comparing the proxy's subspace rankings with the improvements actually realized should detect that rotation and fall back to random selection.

Concretely, at iteration $t$ we draw $M$ random orthonormal candidate bases $A_j \in \mathbb{R}^{D \times d}$, with $d$ small (around 5), centred at a point $c_t$. We spend $m$ low-fidelity queries in each candidate and fit a small local model $\hat f_L$ to them. Each candidate is scored by its predicted low-fidelity improvement,

$$s_j = f_L(c_t) - \min_{\lVert z \rVert \le r} \hat f_L(c_t + A_j z),$$

where $f_L$ is the cheap function, $z \in \mathbb{R}^d$ are coordinates within the subspace, and $r$ is a trust radius. Because $s_j$ is a difference within a single subspace, any constant offset between fidelities cancels. The top $k$ candidates, plus one candidate drawn uniformly at random, then receive standard upper-confidence-bound acquisition maximization under the global high-fidelity surrogate.

Relation to Prior Work

The method comes from subspace acquisition optimization. MS-UCB maximizes the acquisition function over a set of random low-dimensional slices. This removes the $\sqrt{D}$ penalty from its regret bound, but its convergence depends on how many slices it can afford, and it draws them uniformly. Our proposal keeps its inner optimization and replaces uniform drawing with cheap screening. LINEBO restricts the search to one-dimensional lines through the incumbent and Dropout BO restricts it to random coordinate blocks. Neither uses any information to choose the slice, and Dropout's results show that greedy slice reuse ("Copy") gets trapped unless random exploration is mixed in. That result motivates our random doubt slot. GIT-BO chooses a subspace from the data, using Fisher information from a tabular foundation model. It also found that centering at the centroid of the data is more stable than centering at the incumbent, which we adopt as one choice of $c_t$. GIT-BO is single-fidelity and capped at 500 dimensions, though, and our method only needs a surrogate that works within a subspace.

The closest work sits at the intersection of the two directions. BF-SSD combines random subspace descent with a line search over a corrected low-fidelity surrogate. It keeps no probabilistic model or acquisition function, it draws directions blindly, and it names informed sample placement as open. We use the cheap fidelity one step earlier, to choose directions rather than step sizes. GTBO screens before optimizing, but its screen is a rigid first phase restricted to axis-aligned variables, and it degrades on rotated problems such as LassoDNA. Our candidates are rotated and re-screened every iteration. Split-and-Doubt supplies the doubt principle: it keeps probing variables it has labelled unimportant, because early data is too sparse to trust. We implement doubt with a cheap random slot instead of its full-dimensional likelihood fitting, which becomes too expensive at large $D$.

Three papers constrain the design. CAMO models the relationship between fidelities with differential-equation kernels and reports up to a four-fold improvement in Borehole when high-fidelity samples are exponentially expensive, but it was tested only at $D \le 6$. That leaves open whether point-wise fidelity modeling survives high dimensions, which is the comparison we run. Lithography solvent discovery reports that a surrogate-guided baseline "achieved high proxy scores but zero EHS pass rate." Exploiting a proxy greedily can therefore be catastrophic, so the deception check is a required part of the method, not an extra. Finally, the MC acquisition-gradient work shows that full-space acquisition maximization with Adam works at moderate dimension, which makes it a baseline to beat rather than something to dismiss.

Research Program

The work has three parts. The first is the algorithm itself, which we call screened-subspace UCB. It runs with two surrogate options: a Gaussian process for $D \le 200$ and a TabPFN-style in-context surrogate, as in GIT-BO, for larger $D$. Its knobs are the number of candidates $M$, the probes per candidate $m$, the number kept $k$, and the slice dimension $d$. We will report sensitivity to each rather than tune them per task.

The second part is a deception monitor. Every iteration yields pairs of (low-fidelity score, realized high-fidelity improvement) for the selected slices and the random slot. A running Spearman rank correlation $\rho_t$ between the two then sets $k$. When $\rho_t$ is near zero or negative, the method spends its slots on random subspaces and reduces to MS-UCB. This bounds how much worse it can do than uniform selection: its loss is at most the low-fidelity spend.

The third part is an analysis of when screening helps. In a model where the low-fidelity function equals the target plus a smooth bias, the difference score $s_j$ preserves the target's ranking of subspaces as long as the bias varies less within a slice than the target does. This gives a testable prediction: the gain should depend on the angle between the dominant sensitive directions of the two fidelities, not on how large the bias is.

Baselines

The do-nothing reference is uniform random subspace UCB in the style of MS-UCB. It uses the same $d$, the same surrogate, and the same inner optimizer, and it receives the low-fidelity budget converted into extra high-fidelity queries at the task's cost ratio. Beating it means lower median simple regret at equal total cost. No reported numeric regret value was found on Lacuna for MS-UCB; the file reports only that it beat REMBO, HeSBO and LineBO up to $D=100$ and on Gisette.

The strongest single-fidelity competitor is GIT-BO, which ranked #1 in optimization performance across its 60 benchmark variants against SAASBO, TuRBO and BAxUS. No per-benchmark regret number was found on Lacuna. We run it on our $D \le 500$ tasks using its own subspace dimension, $r=10$, and charge it the same total cost. Beating it requires a statistically significant improvement in the regret-versus-cost curve on at least the rotated synthetic tasks.

The strongest multi-fidelity competitor is full-space multi-fidelity UCB in the style of BOCA, with the acquisition function maximized by Adam using the method of Wilson et al.. Where it runs within the compute budget, we also include CAMO's kernel. All methods get the same restart and step budget for inner optimization and the same wall-clock cap.

On the zeroth-order tasks, the strongest competitor is BF-SSD. It reports flipping MNIST-CNN predictions within a 7,000-evaluation budget, which only its high-fidelity counterpart matched. Matching that success under a smaller high-fidelity-equivalent budget counts as beating it.

Three ablations isolate what drives the method. Shuffled scoring spends the same low-fidelity queries but ranks subspaces randomly, so it tests whether the cheap information matters or merely the extra probing. Removing the doubt slot and the monitor tests the safeguard. Restricting candidates to coordinate blocks tests whether rotation matters, and is a GTBO-like control.

Why not just…?

Why not just run multi-fidelity Bayesian optimization in the full space? It is the natural reading of the gap, and Adam-based acquisition maximization may scale further than the low-dimensional tests of CAMO suggest. Against it, MS-UCB's analysis says inner-optimization error grows with $D$, and multi-fidelity acquisition adds a fidelity coordinate to an already hard search. We do not assume this settles it. The dimension sweep from 50 to 500 directly measures where, if anywhere, the full-space method falls behind. If it never does, the claim fails.

Why not just use the cheap evaluations once to estimate an active subspace, then run single-fidelity Bayesian optimization inside it? This is the most serious threat. It is GTBO's two-phase design made rotation-aware, for example by applying Fisher information from a low-fidelity surrogate, and it may capture most of the gain more cheaply. Split-and-Doubt shows that one-shot splits fixed on early data permanently lose variables that were misidentified. That evidence comes from axis-aligned problems, though. We include this one-shot pipeline as a full baseline and build tasks where the low-fidelity function's sensitive directions are globally aligned with the target's but locally rotated. If one-shot matches us even there, the continual-screening claim is wrong and we will report it as such.

Why not just spend the cheap budget on more random subspaces? If probing alone, without ranking, explains the gain, the method has no reason to exist. The shuffled-scoring ablation answers this exactly, at identical low-fidelity spend.

Proposed Experiments

The synthetic suite embeds Ackley, Levy, Griewank and Hartmann-6, the functions used by GTBO and MS-UCB, into $D \in \{50, 100, 300, 500\}$ under a random rotation. This removes the axis-aligned advantage. Each function gets a constructed low-fidelity version made of three parts: a smooth additive bias, extra noise, and a rotation of its active subspace by a controlled angle $\theta$ from 0° to 90°. Cost ratios are 1/10, 1/100 and 1/1000.

The real tasks are the three where BF-SSD defined a natural cheap fidelity: dual kernel ridge regression on California Housing, the black-box attack on an MNIST CNN, and soft-prompting DistilBERT. We add MOPTA08 ($D=124$) as a single-fidelity control. Its low fidelity is the true function, so any gain there must come from screening alone.

The metrics are simple regret against cumulative cost in high-fidelity-equivalent units, over 20 seeds, plus wall-clock time and the monitor's correlation $\rho_t$.

Three checks decide the claim. First, on the rotated synthetic tasks with small $\theta$, the method must beat both uniform subspaces and shuffled scoring at every cost ratio, and its margin should grow as the cheap fidelity gets cheaper. Second, as $\theta$ approaches 90°, the gain must fade, the monitor must push $k$ toward zero, and regret must stay within the low-fidelity overhead of MS-UCB. This is the protection against a deceptive proxy that the solvent study shows is necessary. Third, on the locally rotated tasks, continual screening must beat the one-shot active-subspace pipeline. If it does not, the result reduces to "screen once" and the note's central claim is refuted.