# Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 60 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Aleatoric and Epistemic Uncertainty in Machine Learning: An Introduction to Concepts and Methods](https://mlsanity.com/paper/1910.09457/) (2019)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [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)
- [Global Convergence of ADMM in Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1511.06324/) (2015)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [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)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Linear Convergence of Adaptive Stochastic Gradient Descent](https://mlsanity.com/paper/1908.10525/) (2019)
- [Decentralized High-Dimensional Bayesian Optimization with Factor Graphs](https://mlsanity.com/paper/1711.07033/) (2017)
- [Bayesian Optimization for Synthetic Gene Design](https://mlsanity.com/paper/1505.01627/) (2015)
- [Additive Gaussian Processes Revisited](https://mlsanity.com/paper/2206.09861/) (2022)
- [A warped kernel improving robustness in Bayesian optimization via random embeddings](https://mlsanity.com/paper/1411.3685/) (2014)
- [Trading Convergence Rate with Computational Budget in High Dimensional Bayesian Optimization](https://mlsanity.com/paper/1911.11950/) (2019)
- [Gaussian Process-Based Decentralized Data Fusion and Active Sensing for Mobility-on-Demand System](https://mlsanity.com/paper/1306.1491/) (2013)
- [INSPIRE: Distributed Bayesian Optimization for ImproviNg SPatIal REuse in Dense WLANs](https://mlsanity.com/paper/2204.10184/) (2022)
- [Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1409.2383/) (2014)

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

- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization](https://mlsanity.com/paper/2405.14540/) (2024)
- [Time-Varying Bayesian Optimization Without a Metronome](https://mlsanity.com/paper/2501.18963/) (2025)
- [Safe Bayesian Optimization for Complex Control Systems via Additive Gaussian Processes](https://mlsanity.com/paper/2408.16307/) (2024)
- [Asymptotic Performance of Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2505.13012/) (2025)
- [On Thompson Sampling and Bilateral Uncertainty in Additive Bayesian Optimization](https://mlsanity.com/paper/2510.11792/) (2025)
- [Leveraging Discrete Function Decomposability for Scientific Design](https://mlsanity.com/paper/2511.03032/) (2025)
- [Automated Random Embedding for Practical Bayesian Optimization with Unknown Effective Dimension](https://mlsanity.com/paper/2605.23473/) (2026)
- [STREGO: A Scalable Implementation of a Trust-Region Framework for Noisy Bayesian Optimization](https://mlsanity.com/paper/2610.14338/) (2026)

## Abstract (arXiv)

Bayesian Optimization (BO) is typically used to optimize an unknown function f that is noisy and costly to evaluate, by exploiting an acquisition function that must be maximized at each optimization step. Even if provably asymptotically optimal BO algorithms are efficient at optimizing low-dimensional functions, scaling them to high-dimensional spaces remains an open problem, often tackled by assuming an additive structure for f. By doing so, BO algorithms typically introduce additional restrictive assumptions on the additive structure that reduce their applicability domain. This paper contains two main contributions: (i) we relax the restrictive assumptions on the additive structure of f without weakening the maximization guarantees of the acquisition function, and (ii) we address the over-exploration problem for decentralized BO algorithms. To these ends, we propose DuMBO, an asymptotically optimal decentralized BO algorithm that achieves very competitive performance against state-of-the-art BO algorithms, especially when the additive structure of f comprises high-dimensional factors.