Bayesian optimization tunes a model's hyperparameters by fitting a Gaussian process to past trials and using it to pick the next trial. A Gaussian process (GP) is a probabilistic regression model that predicts a value and an uncertainty at every point. Multi-fidelity tuning runs thousands of cheap, truncated training runs, so the GP must absorb tens of thousands of observations. Exact GP inference costs cubic time in the number of observations. The cheap fixes are a GP that predicts only from a query's nearest neighbors, or a preconditioned iterative solver, and both work poorly once the search space has more than a handful of dimensions. We argue that the cost problem and the dimensionality problem have one shared cause, and so one shared fix. Hyperparameter objectives usually vary along a few directions that need not follow the coordinate axes. If we estimate those directions from the GP's own gradient predictions and use them only inside the kernel, while still searching the original space, then nearest neighbors become meaningful again and local GP prediction becomes both cheap and accurate.
A concrete example shows what we mean by directions that do not follow the axes. Efficient Hyperparameter Tuning via Trajectory Invariance Principle found that transformer loss curves collapse when the product of learning rate and weight decay, $\eta\lambda$, is held fixed. In log coordinates, that means the loss is flat along $\log\eta - \log\lambda$ and varies only along $\log\eta + \log\lambda$. That is a linear one-dimensional subspace lying diagonally across two axes. A per-axis lengthscale cannot represent it. A kernel that measures distance after a learned linear projection can. Our proposal is to discover such subspaces automatically and without derivatives of the objective, and to use them to make GP surrogates scale.
Core Claim
Use a linear projection only to define the GP kernel's distances, never as the search space. This avoids the boundary failures of embedding-based Bayesian optimization. In a regime with many low-fidelity evaluations, it also turns nearest-neighbor and preconditioned GP inference from degraded high-dimensional approximations into accurate low-dimensional ones.
The projection $W \in \mathbb{R}^{D\times d}$ maps the $D$ hyperparameters to $d$ directions. It is estimated from a gradient diagnostic matrix computed under the GP posterior rather than from true derivatives:
$$ H = \frac{1}{N}\sum_{i=1}^{N} \mathbb{E}_{\text{post}}\!\left[\nabla f(x_i)\nabla f(x_i)^\top\right] = \frac{1}{N}\sum_{i=1}^{N}\left(\nabla\mu(x_i)\nabla\mu(x_i)^\top + \Sigma_\nabla(x_i)\right). $$
Here $f$ is the validation loss and $x_i$ are $N$ evaluated or sampled configurations in log-scaled coordinates. The term $\nabla\mu$ is the gradient of the GP posterior mean. The term $\Sigma_\nabla$ is the posterior covariance of that gradient, which is available in closed form because the derivative of a GP is a GP. We take $W$ to be the top-$d$ eigenvectors of $H$. The surrogate then uses the kernel
$$ k(x,x') = k_0\!\left(W^\top x,\; W^\top x'\right) + \sigma_\perp^2\, k_1\!\left(x,x'\right), $$
where $k_0$ is a standard stationary kernel. The second term is a weak, long-lengthscale residual kernel with variance $\sigma_\perp^2$. It keeps the model honest when the subspace is wrong. Nearest-neighbor search, the choice of preconditioner, and the subset used to fit kernel parameters all operate in the $d$-dimensional projected coordinates.
Relation to Prior Work
Three groups of prior work shape this proposal.
The first group motivates it and also constrains it. Bayesian Optimization in a Billion Dimensions via Random Embeddings (REMBO) searches a random linear embedding and clips out-of-box points back to the boundary. Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization (ALEBO) shows that this clipping folds the space non-linearly. ALEBO replaces clipping with a polytope constraint and a projection-derived Mahalanobis kernel. Both methods search inside the embedding, so both must worry about the inverse map back to the original space. We search in the original box and use the projection only for distances, so there is no inverse map to get wrong.
Both methods also keep exact GP inference, so neither addresses cost in the number of observations. Non-linear alternatives such as High-Dimensional Bayesian Optimization with Manifold Gaussian Processes and High Dimensional Bayesian Optimization with Kernel Principal Component Analysis learn curved latent spaces. The second paper reports that its kernel-PCA manifold stabilizes too early and is overtaken by linear PCA on BBOB F21/F22. We take that as evidence for keeping the projection linear and estimating it cheaply.
The second group supplies the method. Coupled Input-Output Dimension Reduction builds gradient diagnostic matrices whose eigenvectors give the dominant input subspace. That approach needs exact Jacobians from adjoint solvers. We replace those Jacobians with GP posterior gradients, in the spirit of Bayesian Optimization with Gradients, which treats gradients as GP-distributed. That paper feeds observed gradients into the GP, at a cost growing as $(d+1)^3$. We infer gradients from the GP instead and need none observed.
For scalable inference we reuse two methods. Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression (GPnn) fits kernel parameters on a subset and predicts from nearest neighbors. Preconditioning for Scalable Gaussian Process Hyperparameter Optimization builds variance-reducing preconditioners for iterative solvers. Both report degradation as input dimension grows, and that degradation is the failure we target.
The third group sets up the tension we test. Approximation-Aware Bayesian Optimization (EULBO) argues that sparse GPs waste their small set of summary points, called inducing points, on unpromising regions, and steers them toward high-utility regions. GPnn instead shows that local prediction is robust for regression. Neither paper studies how a projection changes this. We expect that local prediction in a good subspace concentrates modeling capacity near the current best configurations automatically, because acquisition queries cluster there.
Research Program
The method alternates three steps inside a standard Bayesian optimization loop. First, every $T$ iterations it fits a small exact GP on a few thousand evaluations and computes $H$ in closed form. Second, it chooses $d$ by an eigenvalue-gap rule and updates $W$. Third, between updates it predicts with a GPnn-style local GP in the projected coordinates, and it optimizes expected improvement over the original box.
Multi-fidelity is handled by treating the training budget as one extra input coordinate. That coordinate is always kept in the projection, so it is never projected away.
We will analyze two questions. The first is when the posterior-expected diagnostic matrix recovers the true subspace. The posterior covariance term should keep the estimate from being dominated by noise early on, and we will measure recovery by principal angles to known subspaces. The second is how neighbor quality depends on $d$ rather than $D$, which is the mechanism behind our scalability claim.
One extension tests the critique in Isometric Projection, which argues that a single global projection cannot follow a twisted manifold. In this variant, $H$ is computed only over each query's neighborhood, giving each region its own projection. Because prediction is already local, this costs little. The variant should help when the dominant directions change across the space, for example when the learning-rate/weight-decay invariance breaks at large batch sizes, as the trajectory-invariance paper reports.
Baselines
The naive reference points are random search and an exact GP with per-axis lengthscales, refit on a random subsample capped at 2,000 points. The subsample cap is what practitioners actually do when $n$ grows. Our method must beat both on regret measured against wall-clock time, with surrogate fitting time included.
The strongest dimension-reduction competitor is ALEBO, from Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization, run with its own embedding dimension rule and exact GP. That paper reports that ALEBO optimized $D=1000$ Hartmann6 while REMBO failed to beat random search. It gives no numeric regret in the file. Beating ALEBO means lower simple regret at matched evaluations once $n$ exceeds a few thousand, where its exact GP must subsample.
The strongest scalable-GP competitors are GPnn in the original space with per-axis lengthscales and EULBO from Approximation-Aware Bayesian Optimization. EULBO reports reaching standard SVGP reward with up to 10 times fewer evaluations. GPnn reports training on $1.6\times10^6$ points in about 30 seconds. Both get the same evaluation budget, the same fidelity schedule and the same wall-clock limit. EULBO gets the same number of inducing points as our neighborhood size.
The strongest practical hyperparameter-search competitors are LFBO from A General Recipe for Likelihood-free Bayesian Optimization, run from lfbo-ml/lfbo, and BOHB from BOHB. LFBO reports consistently outperforming TPE, SMAC, BORE and GP methods on almost all HPOBench and NAS-Bench-201 tasks, and being about 5 times faster than GP-EI on NAS-Bench-201 CIFAR-10. We found no reported numeric regret on Lacuna for LFBO on HPOBench. We will therefore rerun it under our protocol and report its regret curves alongside ours.
Two ablations isolate the key ingredient. The first replaces the gradient-estimated $W$ with a random projection, a PCA of evaluated points, or a full Mahalanobis matrix learned by marginal likelihood. The second removes the residual kernel.
Why not just…?
Why not just use per-axis lengthscales with a nearest-neighbor GP? Per-axis lengthscales reweight each coordinate separately and cannot express a diagonal invariant such as $\log\eta - \log\lambda$. In that case the nearest neighbors still include points that differ greatly along the direction that matters. The ablation on rotated benchmarks, where the true subspace is deliberately off-axis, directly measures this. If per-axis GPnn matches us on unrotated JAHS-Bench-201, we will report that the gain is specific to off-axis structure.
Why not just learn a full Mahalanobis kernel by marginal likelihood, as ALEBO does? This is the most serious threat, because it captures the same geometry. Our bet is cost and stability. Fitting $Dd$ projection entries by marginal likelihood at large $n$ is exactly the high-dimensional, non-convex fit that degrades. The diagnostic matrix, by contrast, is a closed-form eigenproblem on a small GP. The Mahalanobis ablation is run at equal wall-clock time. If it matches us on both regret and time, the contribution narrows to the claim that kernel-only projections make local GPs work, and we will say so.
Why not just drop GPs and use LFBO or tree-based surrogates? These scale easily, and LFBO has strong reported HPOBench results. However, LFBO itself notes that it lacks calibrated uncertainty and becomes over-confident. That should hurt most when the budget is small relative to dimension. We test this by comparing regret in the first 10% of the budget, and by reporting surrogate negative log-likelihood on held-out trials. If LFBO wins at every budget, the method has no practical case beyond the uncertainty estimates it provides.
Why not just tune learning rate and weight decay online with hypergradients? Online Learning Rate Adaptation with Hypergradient Descent handles only continuous, differentiable hyperparameters within one run. Our JAHS-Bench-201 space includes discrete architecture and resolution choices, which hypergradients cannot tune, so we do not compete on that axis.
Proposed Experiments
The first experiment uses synthetic problems where the true subspace is known. We embed Hartmann6 and Ackley in $D=100$ and $D=1000$ through a random rotation, so the true subspace is off-axis, and add cheap noise so that $n$ can reach 50,000. We measure principal angles between the recovered and true subspaces, simple regret against both evaluations and wall-clock time, and neighbor recall, meaning the fraction of true-subspace neighbors that are retrieved.
The second experiment uses JAHS-Bench-201 (14 dimensions, with fidelity) and HPOBench multi-fidelity families. Here many low-fidelity evaluations are cheap, so large $n$ arises naturally. Metrics are regret and surrogate negative log-likelihood on held-out configurations, averaged over 20 seeds.
The third experiment is a small transformer sweep over learning rate, weight decay, warmup and batch size. It checks whether the method rediscovers $\log\eta+\log\lambda$ as the leading direction at small batch size. It also checks whether the leading direction rotates at large batch size, where the trajectory-invariance paper reports that the invariance breaks; that is the setting where the per-region variant should earn its cost.
Three outcomes would decide the proposal. It is falsified if recovered subspaces do not beat random projections in principal angle at moderate $n$. It is also falsified if GPnn's error in projected coordinates fails to stay flat as $D$ grows from 100 to 1000 while ambient-space GPnn's error rises. Finally, regret at matched wall-clock time must improve over ALEBO, the learned-Mahalanobis ablation and LFBO on at least the rotated and JAHS tasks; if it does not, the gain is not worth claiming.
References
- Efficient Hyperparameter Tuning via Trajectory Invariance Principle
- Bayesian Optimization in a Billion Dimensions via Random Embeddings
- Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization
- High-Dimensional Bayesian Optimization with Manifold Gaussian Processes
- High Dimensional Bayesian Optimization with Kernel Principal Component Analysis
- Coupled Input-Output Dimension Reduction: Application to Goal-oriented Bayesian Experimental Design and Global Sensitivity Analysis
- Bayesian Optimization with Gradients
- Leveraging Locality and Robustness to Achieve Massively Scalable Gaussian Process Regression
- Preconditioning for Scalable Gaussian Process Hyperparameter Optimization
- Approximation-Aware Bayesian Optimization
- Isometric Projection
- A General Recipe for Likelihood-free Bayesian Optimization
- BOHB: Robust and Efficient Hyperparameter Optimization at Scale
- Online Learning Rate Adaptation with Hypergradient Descent