Bayesian Optimization (BO) is a powerful framework for optimizing expensive, black-box functions. It works by maintaining a probabilistic surrogate model of the objective function, which provides both a predicted value and a measure of uncertainty for any unseen point. An acquisition function then uses this uncertainty to balance exploration (sampling where the model is uncertain) and exploitation (sampling where the model expects a good result).
Historically, Gaussian Processes (GPs) have been the default choice for surrogate modeling. GPs are mathematically elegant and provide exact, non-parametric uncertainty estimates. However, they suffer from a fatal flaw: computing the GP posterior requires inverting an $N \times N$ covariance matrix, where $N$ is the number of evaluated points. This introduces a cubic computational bottleneck—$\mathcal{O}(N^3)$ time complexity—and a quadratic $\mathcal{O}(N^2)$ memory footprint. As a result, traditional BO grinds to a halt after a few hundred iterations, making it entirely unsuited for large-scale datasets, high-dimensional search spaces, or settings requiring rapid, continuous evaluations (Klein et al.).
To break this bottleneck, a major research direction focuses on replacing GPs with neural surrogate models. By leveraging the parametric nature of neural networks, these methods achieve linear scaling ($\mathcal{O}(N)$) with respect to the number of observations, unlocking optimization at a scale previously deemed impossible.
The Core Challenge: Calibrating Neural Uncertainty
The primary reason GPs reigned supreme for so long is that standard neural networks are notoriously overconfident; they do not naturally produce the well-calibrated uncertainty estimates required to guide exploration. To build a viable neural surrogate, researchers must inject principled uncertainty estimation into deep architectures without reintroducing cubic complexity.
Bayesian Neural Networks and Monte Carlo Dropout
One direct alternative is the Bayesian Neural Network (BNN), which treats network weights as probability distributions rather than fixed points. Springenberg et al. demonstrated that by using a scale-adapted version of Stochastic Gradient Hamiltonian Monte Carlo (SGHMC), BNNs can serve as robust surrogates that scale gracefully to high-dimensional spaces while maintaining reliable uncertainty bounds.
Because full BNN inference can still be computationally demanding, many practical frameworks employ Monte Carlo (MC) Dropout as a scalable approximation. By leaving dropout active during both training and inference, passing an input through the network multiple times yields a distribution of outputs. This distribution acts as a proxy for epistemic uncertainty. This mechanism has been successfully utilized to navigate high-dimensional level set estimations (Ha et al.), optimize complex scientific simulations (Kim et al.), and guide causal discovery algorithms (Duong et al.).
Adaptive Bayesian Linear Regression
Another highly efficient strategy is to decouple representation learning from uncertainty estimation using Adaptive Bayesian Linear Regression (ABLR).
Input (x) ──► [ Deep Neural Network ] ──► Fixed-Dim Features φ(x) ──► [ Bayesian Linear Regression Layer ] ──► Mean & Variance
In this architecture, a standard deep neural network processes the raw, high-dimensional input and maps it to a fixed-dimensional feature space, $\phi(x)$. A formal Bayesian linear regression layer is then stacked on top of these features (Perrone et al.). Because the dimensionality of the feature space $\phi(x)$ is fixed and independent of the number of evaluated data points $N$, the matrix inversion required for the Bayesian update depends only on the feature dimension, not on $N$. Consequently, the computational complexity scales linearly ($\mathcal{O}(N)$), allowing the optimizer to ingest hundreds of thousands of historical data points (Horváth et al.).
To prevent overfitting when adapting to new tasks, Horváth et al. introduced nested dropout and Automatic Relevance Determination (ARD) to dynamically scale model complexity based on available data. Similarly, Kristiadi demonstrated that the Linearized Laplace Approximation (LLA) can turn a pre-trained neural network into a scalable surrogate by supporting mini-batch training updates, bypassing the memory exhaustion common to exact kernel methods.
Bypassing Surrogates via Classification and Density Estimation
Rather than trying to fix the uncertainty estimates of a regression model, some researchers ask a more radical question: Do we actually need to model the objective function's landscape to optimize it?
Inverse Density Estimation
Instead of modeling $y = f(x)$, we can model the distribution of inputs conditioned on performance. The landmark Tree-structured Parzen Estimator (TPE) approach by Bergstra et al. splits historical evaluations into two groups: "good" configurations and "bad" configurations. By using inverse density estimation to model these two groups separately, the algorithm selects next-step candidates that maximize the likelihood of belonging to the "good" distribution, achieving strict linear scaling.
Likelihood-Free Bayesian Optimization
Taking this a step further, Song et al. introduced Likelihood-Free Bayesian Optimization (LFBO). LFBO observes that standard acquisition functions (like Expected Improvement) can be mathematically rewritten as a ratio of two classifiers.
By framing the optimization step as a simple weighted binary classification problem—where the model learns to distinguish between promising and unpromising regions—LFBO completely decouples the optimization loop from probabilistic inference. This allows practitioners to use standard, highly optimized discriminative models (such as standard neural networks or gradient-boosted trees) directly as the optimizer's brain, eliminating cubic bottlenecks entirely.
Unlocking Structured Spaces and Multi-Task Learning
The shift from rigid, kernel-based Gaussian Processes to flexible neural architectures does more than just accelerate computation; it fundamentally expands the types of optimization problems we can solve.
Structured and High-Dimensional Inputs
GPs struggle with non-vectorial data because designing valid, expressive kernels for complex structures is incredibly difficult. Neural networks, however, excel at representation learning.
- Graphs: In Neural Architecture Search (NAS) or molecular generation, candidate designs are represented as graphs. Ma et al. and Yang et al. integrated Bayesian Graph Neural Networks (GNNs) to automatically extract structural features from graphs, providing calibrated uncertainties to navigate massive combinatorial spaces.
- Natural Language Embeddings: Li et al. utilized BNN surrogates to map high-dimensional text embeddings of candidate features (generated by Large Language Models) to their predicted utility, seamlessly bridging semantic spaces with quantitative optimization.
Scalable Contextual Bandits and Networks
In sequential decision-making, traditional contextual bandits rely on maintaining large statistical covariance matrices to manage exploration, which incurs a quadratic space complexity relative to the number of parameters. To scale these models to massive architectures, Ban et al. introduced EE-Net, which replaces the covariance matrix with a dedicated, learned "Exploration Network," reducing the space complexity to linear. For massive biological and financial networks where inputs and outputs are sparse and interconnected, Zhang et al. combined sequential updates with surrogate functions to reduce computational complexity from cubic to nearly linear.
Transfer and Multi-Fidelity Optimization
Neural surrogates are uniquely suited for transferring knowledge across different optimization tasks because their internal layers can learn shared representations. Volpp et al. demonstrated that neural acquisition functions can ingest massive historical datasets to meta-learn search strategies that generalize across tasks.
In human-in-the-loop systems, where optimization must adapt to individual users without starting from scratch, Liao et al. used a global BNN population model to capture shared performance patterns across a growing user base efficiently. Furthermore, for multi-fidelity optimization—where cheap, low-accuracy simulations guide expensive, high-accuracy evaluations—Li et al. showed that deep neural networks can be stacked to capture complex, non-linear correlations between different fidelities while maintaining strict linear scaling.
Key Foundational Work
Scalable Bayesian Optimization Using Deep Neural Networks (2015) — contributed 1 concept elements to this direction.
Algorithms for Hyper-Parameter Optimization (2011) — contributed 1 concept elements to this direction.