Bayesian optimization tunes expensive black-box systems such as robot controllers or molecule generators. It does this by fitting a Gaussian process (GP), a probabilistic regression model that reports both a prediction and its uncertainty, to every evaluation so far, and then choosing the next query from that model. Once there are tens of thousands of evaluations, the exact GP becomes too expensive. Practitioners then switch to sparse GPs, which summarize all the data through a small set of $m$ "inducing points," a few hundred virtual anchor locations. Where those anchors sit matters a great deal. Recent work shows that placing them where the optimizer expects good values, rather than spreading them evenly, can cut the number of evaluations by up to an order of magnitude. The danger is that the guess about where good values lie is only a prediction. It may come from the model's own acquisition function, from a cheap simulator, or from a model pretrained on a related task. If that guess is wrong, the anchors pile up in the wrong place, the model goes blind elsewhere, and nothing in current methods notices.
We propose to treat the guidance for placing inducing points the way learning-augmented online algorithms treat machine-learned advice: as an untrusted hint whose error we measure as we go. Concretely, the inducing budget is split between a pool that follows the hint and a pool that keeps global coverage. A trust weight moves budget between the two pools based on how well each pool predicted the points the optimizer has just evaluated. This check costs nothing extra, because every new evaluation is already a held-out test of the model that chose it. The goal is twofold. When the hint is accurate, the method should behave like a fully hint-directed sparse GP. When the hint is wrong, it should never do much worse than a sparse GP that uses a fixed fraction of the budget for coverage.
Core Claim
Approximation-Aware Bayesian Optimization motivates this work. It replaces the standard evidence lower bound used to train sparse GPs with an "expected utility lower bound" (EULBO). EULBO concentrates inducing points where the acquisition function promises high utility, and it reports up to 10x fewer evaluations on Lunar Lander, Rover, Lasso DNA and Guacamol. The weighting it uses is computed from the approximate model itself. EULBO therefore trusts that weighting completely and has no recourse if the weighting is wrong.
Our claim is that inducing-point placement can be made error-sensitive in the sense of the learning-augmented literature, and that this protection costs only a constant fraction of the budget. The two properties we want are:
- consistency: near-EULBO behaviour when the hint is good;
- robustness: a guaranteed floor equal to an evidence-lower-bound-trained sparse GP with $\beta m$ coverage points, where $\beta$ is a fixed floor fraction.
The trust weight is driven by measured prequential error, meaning each pool's log-loss on each new point before that point is added to the data.
The structure borrows from two lines of work. Better and Simpler Learning-Augmented Online Caching combines a prediction-following algorithm with a robust one as black boxes. Double Coverage with Machine-Learned Advice blends advice with a safety net through an explicit trust parameter. We take the idea of an adaptive, error-keyed weight from Optimistic Online Non-stochastic Control via FTRL. That paper tunes its regularizer to accumulated prediction error, so that regret falls to $O(1)$ under perfect predictions and stays $O(\sqrt{T})$ under failed ones. The difference here is in what is being allocated. Those papers allocate actions. We allocate representational capacity inside an approximate posterior. The prediction is a weighting over the search space rather than a scalar or combinatorial hint, which addresses the open problem in Direction 1 of handling high-dimensional, probabilistic predictions.
Research Program
The model is a single sparse variational GP whose $m$ inducing points are partitioned at round $t$ into two pools.
- The hint pool has size $\lfloor (1-\beta)\lambda_t m \rfloor$ and is trained with EULBO, or with any hint weighting $w(x)$.
- The coverage pool holds the remaining points, never fewer than $\beta m$. It is trained with the standard evidence lower bound.
After the optimizer evaluates $x_t$ and observes $y_t$, we score each pool by the predictive log-loss of a sub-model conditioned on that pool's inducing points alone: $\ell^{h}_t$ for the hint pool and $\ell^{c}_t$ for the coverage pool. The trust weight is then updated by exponential weights:
$$\lambda_{t+1} = \frac{\exp(-\gamma \sum_{s\le t} \ell^{h}_s)}{\exp(-\gamma \sum_{s\le t} \ell^{h}_s) + \exp(-\gamma \sum_{s\le t} \ell^{c}_s)},$$
Here $\gamma$ is a learning rate. Inducing points move between pools by re-initializing the reassigned points at the other pool's locations, followed by a few gradient steps. The two sub-model scores cost $O(m^2)$ each per evaluation, which is negligible next to sparse GP training.
The theoretical work has three pieces.
- Prequential regret. Standard exponential-weights analysis gives cumulative log-loss within $O(\sqrt{T})$ of the better pool in hindsight. If log-loss is bounded, the per-round gap therefore vanishes at rate $1/\sqrt{T}$.
- Robustness. The coverage pool alone has a KL gap no larger than that of an evidence-lower-bound sparse GP with $\beta m$ points. This bounds the damage a misleading hint can do to posterior fidelity away from the hinted region.
- Consistency. As the hint's error $\eta \to 0$, the hint pool wins the log-loss comparison and $\lambda_t \to 1$, so the model approaches EULBO with $(1-\beta)m$ points.
The open question we will study, not assume, is how far log-loss on the optimizer's own queries tracks the hint error that matters for optimization. These queries are not a random sample, because they are biased toward the hinted region. For that reason the coverage pool also scores a small reservoir of queries drawn under the coverage-only acquisition. We will measure how large this reservoir must be.
To control hint quality we build a corrupted hint $w_\eta = (1-\eta) w_{\text{good}} + \eta\, w_{\text{decoy}}$.
- $w_{\text{good}}$ concentrates on the region of the best solutions found in long reference runs.
- $w_{\text{decoy}}$ concentrates on a known inferior local optimum.
This gives a full consistency–robustness curve over $\eta \in [0,1]$. We also test natural hints: EULBO's own acquisition, and a surrogate pretrained on a related Guacamol objective.
Baselines
The naive reference is a standard sparse variational GP trained with the evidence lower bound using all $m$ points, the baseline in Approximation-Aware Bayesian Optimization. It is the "ignore the hint" algorithm and fixes the robustness floor.
The strongest existing method is EULBO-SVGP from the same paper, run with the hint as its utility weighting. Its reported evidence is "up to 10 times fewer function evaluations" on Lunar Lander, Lasso DNA and Guacamol. No reported result was found on Lacuna for EULBO's exact final rewards or molecular scores, so we will reproduce it. Beating it means two things. First, at $\eta \ge 0.5$ we must reach a higher best-found reward at every evaluation budget. Second, at $\eta = 0$ we must stay within the run-to-run spread of EULBO.
All methods share the same $m$, kernel, acquisition function (expected improvement), batch size, number of seeds (at least 20), and wall-clock budget per round. Hyperparameter tuning gets an equal grid budget per method, and our tuned values are $\gamma$ and $\beta$.
The ablation that isolates the key ingredient is a fixed split, which freezes $\lambda_t$ at a constant. We report it both at $0.5$ and at the best constant chosen with knowledge of $\eta$. That second version is an oracle that our method cannot beat in hindsight. Our target is to match it within noise without being told $\eta$.
A fourth comparison replaces the log-loss trust signal with a simple observed-improvement signal, which tracks whether queries in the hinted region beat the incumbent. This tells us whether probabilistic scoring matters.
For the regression sanity check on Kin40K, the hint predicts where test queries will fall. Exact Gaussian Processes on a Million Data Points reports test RMSE 0.099 for the exact GP and 0.273 for its sparse approximation. These numbers bracket the achievable range.
Why not just…?
Why not just use a fixed split of the inducing budget? This is the real threat. If the oracle-tuned fixed split works well across all $\eta$, an adaptive weight adds little. The contribution then reduces to not having to know $\eta$, which matters only if a fixed ratio tuned under one hint quality transfers poorly to another. The $\eta$ sweep settles this directly. If a single untuned ratio such as $0.5$ comes within noise of the oracle at every $\eta$, we will report that and recommend it. The FTRL control results in Optimistic Online Non-stochastic Control via FTRL suggest otherwise, since static mixing gives up the gains available from accurate predictions. But that is a different setting, so we test the question rather than assume the answer.
Why not just run an exact GP? Exact Gaussian Processes on a Million Data Points removes the approximation entirely, but it needs eight GPUs and $O(n^2)$ work per conjugate-gradient iteration. A Bayesian optimization loop retrains at every round. On Guacamol, with up to 80,000 evaluations, we will run the exact GP at matched wall-clock time. If it wins there, the inducing-point problem is moot for that regime, and our method's value is confined to tighter compute budgets.
Why not just randomize queries, as BOHB does? BOHB: Robust and Efficient Hyperparameter Optimization at Scale keeps its guarantees by sampling a fixed fraction of configurations uniformly at random. That protects which points get queried, but it does nothing for the model's representation. If every inducing point sits in the decoy region, randomly queried points far away are still poorly modelled. We include EULBO plus a 10% random-query fraction as a baseline. If it matches our method at high $\eta$, then robustness in query choice is enough, and robustness in representation is unnecessary.
Why not just use nearest-neighbour GPs, which need no inducing points? Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression shows that predicting from the $m$ nearest neighbours is robust to misspecification as data become dense. Its authors note, however, that approximate neighbour search degrades in high dimensions, and the 180-dimensional and 256-dimensional tasks are far from dense. We include it on Lunar Lander (12 dimensions), where it should be strongest, and on Lasso DNA, where we expect it to fail.
Proposed Experiments
The benchmarks are Lunar Lander, Rover (60 dimensions), Lasso DNA, and Guacamol Osimertinib and Fexofenadine MPO, all taken from the EULBO paper.
The decisive check is the consistency–robustness curve: best-found reward at a fixed evaluation budget, plotted against $\eta$ in steps of $0.25$, for each method. The proposal succeeds if three conditions hold:
- the curve lies on or above EULBO near $\eta = 0$;
- it stays on or above the evidence-lower-bound sparse GP at $\eta = 1$, where EULBO is expected to fall below it;
- it tracks the oracle fixed split throughout.
A second check plots $\lambda_t$ against the true $\eta$ to confirm that the trust signal identifies bad hints within a few hundred evaluations, along with the size of the reservoir needed to correct for biased query selection. A third check uses Kin40K with test-region hints, measuring RMSE against the 0.099 and 0.273 bracket. It tests whether the mechanism carries over to plain regression.
A clean negative result would also be informative: the log-loss trust signal never separates the two pools before the budget runs out. That would show that self-scored queries are too biased to verify hints on, and it would point toward reserving explicit verification evaluations.
References
- Approximation-Aware Bayesian Optimization
- Better and Simpler Learning-Augmented Online Caching
- Double Coverage with Machine-Learned Advice
- Optimistic Online Non-stochastic Control via FTRL
- Exact Gaussian Processes on a Million Data Points
- BOHB: Robust and Efficient Hyperparameter Optimization at Scale
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression