# CobBO: Coordinate Backoff Bayesian Optimization with Two-Stage Kernels

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

## Key facts

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

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

- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [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)
- [Batch Bayesian Optimization via Local Penalization](https://mlsanity.com/paper/1505.08052/) (2015)
- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search](https://mlsanity.com/paper/2007.00708/) (2020)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [BOCK : Bayesian Optimization with Cylindrical Kernels](https://mlsanity.com/paper/1806.01619/) (2018)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [High Dimensional Bayesian Optimization Using Dropout](https://mlsanity.com/paper/1802.05400/) (2018)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Scaling Gaussian Process Regression with Derivatives](https://mlsanity.com/paper/1810.12283/) (2018)
- [On the choice of the low-dimensional domain for global optimization via random embeddings](https://mlsanity.com/paper/1704.05318/) (2017)
- [Optimization, fast and slow: optimally switching between local and Bayesian optimization](https://mlsanity.com/paper/1805.08610/) (2018)
- [High Dimensional Bayesian Optimization via Supervised Dimension Reduction](https://mlsanity.com/paper/1907.08953/) (2019)
- [Bayesian Optimization Using Domain Knowledge on the ATRIAS Biped](https://mlsanity.com/paper/1709.06047/) (2017)
- [Practical Bayesian Optimization for Model Fitting with Bayesian Adaptive Direct Search](https://mlsanity.com/paper/1705.04405/) (2017)
- [Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods](https://mlsanity.com/paper/1310.1826/) (2013)
- [Learning to Race through Coordinate Descent Bayesian Optimisation](https://mlsanity.com/paper/1802.06179/) (2018)

## Abstract (arXiv)

Bayesian optimization is a popular method for optimizing expensive black-box functions. Yet it oftentimes struggles in high dimensions where the computation could be prohibitively heavy. To alleviate this problem, we introduce Coordinate backoff Bayesian Optimization (CobBO) with two-stage kernels. During each round, the first stage uses a simple coarse kernel that sacrifices the approximation accuracy for computational efficiency. It captures the global landscape by purposely smoothing away local fluctuations. Then, in the second stage of the same round, past observed points in the full space are projected to the selected subspace to form virtual points. These virtual points, along with the means and variances of their unknown function values estimated using the simple kernel of the first stage, are fitted to a more sophisticated kernel model in the second stage. Within the selected low dimensional subspace, the computational cost of conducting Bayesian optimization therein becomes affordable. To further enhance the performance, a sequence of consecutive observations in the same subspace are collected, which can effectively refine the approximation of the function. This refinement lasts until a stopping rule is met determining when to back off from a certain subspace and switch to another. This decoupling significantly reduces the computational burden in high dimensions, which fully leverages the observations in the whole space rather than only relying on observations in each coordinate subspace. Extensive evaluations show that CobBO finds solutions comparable to or better than other state-of-the-art methods for dimensions ranging from tens to hundreds, while reducing both the trial complexity and computational costs.