# Scaling Bayesian Optimization With Game Theory

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 75 references that are in the map.
- First posted on arXiv 7 Oct 2021.

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

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [BOCK : Bayesian Optimization with Cylindrical Kernels](https://mlsanity.com/paper/1806.01619/) (2018)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [Practical heteroskedastic Gaussian process modeling for large simulation experiments](https://mlsanity.com/paper/1611.05902/) (2016)
- [Batched Gaussian Process Bandit Optimization via Determinantal Point Processes](https://mlsanity.com/paper/1611.04088/) (2016)
- [On the choice of the low-dimensional domain for global optimization via random embeddings](https://mlsanity.com/paper/1704.05318/) (2017)
- [Simulation optimization: A review of algorithms and applications](https://mlsanity.com/paper/1706.08591/) (2017)
- [A warped kernel improving robustness in Bayesian optimization via random embeddings](https://mlsanity.com/paper/1411.3685/) (2014)
- [Explicit Gradient Learning](https://mlsanity.com/paper/2006.08711/) (2020)
- [Regular Potential Games](https://mlsanity.com/paper/1707.06466/) (2017)
- [On the Exponential Rate of Convergence of Fictitious Play in Potential Games](https://mlsanity.com/paper/1707.08055/) (2017)

## Abstract (arXiv)

We introduce the algorithm Bayesian Optimization (BO) with Fictitious Play (BOFiP) for the optimization of high dimensional black box functions. BOFiP decomposes the original, high dimensional, space into several sub-spaces defined by non-overlapping sets of dimensions. These sets are randomly generated at the start of the algorithm, and they form a partition of the dimensions of the original space. BOFiP searches the original space with alternating BO, within sub-spaces, and information exchange among sub-spaces, to update the sub-space function evaluation. The basic idea is to distribute the high dimensional optimization across low dimensional sub-spaces, where each sub-space is a player in an equal interest game. At each iteration, BO produces approximate best replies that update the players belief distribution. The belief update and BO alternate until a stopping condition is met. High dimensional problems are common in real applications, and several contributions in the BO literature have highlighted the difficulty in scaling to high dimensions due to the computational complexity associated to the estimation of the model hyperparameters. Such complexity is exponential in the problem dimension, resulting in substantial loss of performance for most techniques with the increase of the input dimensionality. We compare BOFiP to several state-of-the-art approaches in the field of high dimensional black box optimization. The numerical experiments show the performance over three benchmark objective functions from 20 up to 1000 dimensions. A neural network architecture design problem is tested with 42 up to 911 nodes in 6 up to 92 layers, respectively, resulting into networks with 500 up to 10,000 weights. These sets of experiments empirically show that BOFiP outperforms its competitors, showing consistent performance across different problems and increasing problem dimensionality.