# Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 30 Jan 2022.

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

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1706.00090/) (2017)
- [Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation](https://mlsanity.com/paper/2008.07146/) (2020)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Batched Gaussian Process Bandit Optimization via Determinantal Point Processes](https://mlsanity.com/paper/1611.04088/) (2016)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Replication or exploration? Sequential design for stochastic simulation experiments](https://mlsanity.com/paper/1710.03206/) (2017)
- [Streaming kernel regression with provably adaptive mean, variance, and regularization](https://mlsanity.com/paper/1708.00768/) (2017)
- [Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification](https://mlsanity.com/paper/2002.09954/) (2020)

## Built on by (most cited first, 13 of 13)

- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Quantum Bayesian Optimization](https://mlsanity.com/paper/2310.05373/) (2023)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Batch Bayesian Optimization for Replicable Experimental Design](https://mlsanity.com/paper/2311.01195/) (2023)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithm](https://mlsanity.com/paper/2410.23498/) (2024)
- [No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/2510.20725/) (2025)
- [(Private) Kernelized Bandits with Distributed Biased Feedback](https://mlsanity.com/paper/2301.12061/) (2023)
- [The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs](https://mlsanity.com/paper/2410.14533/) (2024)
- [Gradient-based Sample Selection for Faster Bayesian Optimization](https://mlsanity.com/paper/2504.07742/) (2025)
- [Representative Action Selection for Large Action Space Bandit Families](https://mlsanity.com/paper/2505.18269/) (2025)
- [Advancing Knowledge Tracing by Exploring Follow-up Performance Trends](https://mlsanity.com/paper/2508.08019/) (2025)
- [Principled Design of Expected Improvement for Continuous Simulation Optimization](https://mlsanity.com/paper/2610.18434/) (2026)

## Abstract (arXiv)

Computing a Gaussian process (GP) posterior has a computational cost cubical in the number of historical points. A reformulation of the same GP posterior highlights that this complexity mainly depends on how many unique historical points are considered. This can have important implication in active learning settings, where the set of historical points is constructed sequentially by the learner. We show that sequential black-box optimization based on GPs (GP-Opt) can be made efficient by sticking to a candidate solution for multiple evaluation steps and switch only when necessary. Limiting the number of switches also limits the number of unique points in the history of the GP. Thus, the efficient GP reformulation can be used to exactly and cheaply compute the posteriors required to run the GP-Opt algorithms. This approach is especially useful in real-world applications of GP-Opt with high switch costs (e.g. switching chemicals in wet labs, data/model loading in hyperparameter optimization). As examples of this meta-approach, we modify two well-established GP-Opt algorithms, GP-UCB and GP-EI, to switch candidates as infrequently as possible adapting rules from batched GP-Opt. These versions preserve all the theoretical no-regret guarantees while improving practical aspects of the algorithms such as runtime, memory complexity, and the ability of batching candidates and evaluating them in parallel.