# Taking the GP Out of the Loop

arXiv: https://arxiv.org/abs/2506.12818 · HTML: https://mlsanity.com/paper/2506.12818/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 53 references that are in the map.
- First posted on arXiv 15 Jun 2025.

## Builds on (most cited first, 26 of 26)

- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Tree-Structured Parzen Estimator: Understanding Its Algorithm Components and Their Roles for Better Empirical Performance](https://mlsanity.com/paper/2304.11127/) (2023)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Local Gaussian process approximation for large computer experiments](https://mlsanity.com/paper/1303.0383/) (2013)
- [Convergence of Sparse Variational Inference in Gaussian Processes Regression](https://mlsanity.com/paper/2008.00323/) (2020)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation](https://mlsanity.com/paper/1911.12809/) (2019)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso](https://mlsanity.com/paper/2111.02790/) (2021)
- [Inducing Point Allocation for Sparse Gaussian Processes in High-Throughput Bayesian Optimisation](https://mlsanity.com/paper/2301.10123/) (2023)
- [Simulation optimization: A review of algorithms and applications](https://mlsanity.com/paper/1706.08591/) (2017)
- [A/B Testing: A Systematic Literature Review](https://mlsanity.com/paper/2308.04929/) (2023)
- [Scalable Bayesian Optimization Using Vecchia Approximations of Gaussian Processes](https://mlsanity.com/paper/2203.01459/) (2022)
- [Bayesian Optimization in Materials Science: A Survey](https://mlsanity.com/paper/2108.00002/) (2021)
- [Asynchronous Parallel Bayesian Optimisation via Thompson Sampling](https://mlsanity.com/paper/1705.09236/) (2017)
- [The Evolutionary Computation Methods No One Should Use](https://mlsanity.com/paper/2301.01984/) (2023)
- [Fast, Precise Thompson Sampling for Bayesian Optimization](https://mlsanity.com/paper/2411.17071/) (2024)

## Abstract (arXiv)

Bayesian optimization (BO) has traditionally solved black-box problems where function evaluation is expensive and, therefore, observations are few. Recently, however, there has been growing interest in applying BO to problems where function evaluation is cheaper and observations are more plentiful. In this regime, scaling to many observations N is impeded by Gaussian-process (GP) surrogates: GP hyperparameter fitting scales as O(N3) (reduced to roughly O(N2) in modern implementations), and it is repeated at every BO iteration. Many methods improve scaling at acquisition time, but hyperparameter fitting still scales poorly, making it the bottleneck. We propose Epistemic Nearest Neighbors (ENN), a lightweight alternative to GPs that estimates function values and uncertainty (epistemic and aleatoric) from K-nearest-neighbor observations. ENN scales as O(N) for both fitting and acquisition. Our BO method, TuRBO-ENN, replaces the GP surrogate in TuRBO with ENN and its Thompson-sampling acquisition with UCB = μ(x) + σ(x). For the special case of noise-free problems, we can omit fitting altogether by replacing UCB with a non-dominated sort over μ(x) and σ(x). We show empirically that TuRBO-ENN reduces proposal time (i.e., fitting time + acquisition time) by one to two orders of magnitude compared to TuRBO at up to 50,000 observations.