Research map / Learning theory and algorithms / Prediction and decision losses
Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DuMBO, a decentralized message-passing BO algorithm that removes the low maximum-factor-size assumption on additive decompositions, using a tighter GP-UCB decomposition solved with ADMM and proven asymptotically optimal.
Problem
Scaling asymptotically optimal GP-based Bayesian optimization to high-dimensional functions relies on additive decompositions with low maximum factor size, which restricts applicability and can yield coarse approximations and over-exploration in decentralized BO.
Approach
Replace the overweighted additive upper bound on GP posterior std with a tighter decentralized approximation over factor-graph neighborhoods, and maximize the resulting acquisition function via ADMM over the factor graph with message passing, allowing arbitrary factor sizes without losing maximization guarantees.
Key results
- On 24d Powell, DuMBO attains minimal regret 496 vs 7,937 for DEC-HBO and 11,760 for ADD-GPUCB; SAASBO 3,901.
- On 6d Hartmann, DuMBO reaches 0.54 regret vs 0.69 for LineBO and 1.47 for DEC-HBO.
- On the 60d Rover task, DuMBO achieves 6.38 vs 7.01 for TuRBO and 10.07 for DEC-HBO (lower is better), matching the best among non-decomposing methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use DuMBO instead of DEC-HBO | BO on SHC · SHC | minimal regret: 0.005 -> 0.006 | Hurt |
| use DuMBO instead of the strongest method without known-decomposition access | BO on Hartmann · Hartmann | minimal regret: 0.89 -> 0.54 | Helped |
| use the known additive decomposition with DuMBO | DuMBO on Hartmann · Hartmann | minimal regret: 0.54 -> 0.53 | Helped |
| use DuMBO instead of the strongest method without known-decomposition access | BO on Powell · Powell | minimal regret: 667 -> 496 | Helped |
| use the known additive decomposition with DuMBO | DuMBO on Powell · Powell | minimal regret: 496 -> 469 | Helped |
| use DuMBO instead of the strongest method without known-decomposition access | BO on Rastrigin · Rastrigin | minimal regret: 1,073 -> 986 | Helped |
| use the known additive decomposition with DuMBO | DuMBO on Rastrigin · Rastrigin | minimal regret: 986 -> 678 | Helped |
| use DuMBO instead of TuRBO | BO on Cosmo · Cosmo | average negative reward: 5.82 -> 5.86 | Hurt |
| use the known additive decomposition with DuMBO | DuMBO on WLAN · WLAN | average negative reward: -120.67 -> -121.11 | Helped |
| use DuMBO instead of TuRBO | BO on Rover · Rover | average negative reward: 7.01 -> 6.38 | Helped |
| use the known additive decomposition with DuMBO | DuMBO on SHC · SHC | minimal regret: 0.006 -> 0.009 | Hurt |
Surprising findings
- On the WLAN task DuMBO is not best (-120.67 vs -116.58 for DEC-HBO and -121.11 for ADD-DuMBO on known decomposition).
- ADD-GPUCB and DEC-HBO perform worst on Powell because their low-MFS assumption mismatches the true decomposition.
Limitations
- Asymptotic optimality relies on the regret bound of DEC-HBO and on discrete or Lipschitz-type kernel assumptions.
- Experiments use only 5 replications and a small number of synthetic and real-world tasks.
- Additive decomposition must be inferred by MCMC when unknown, adding cost.
Experimental setup
Datasets: Six-Hump Camel Hartmann Powell Rastrigin Cosmo WLAN Rover
Benchmarks: Six-Hump Camel Hartmann Powell Rastrigin Cosmo WLAN Rover
Metrics: minimal regret average negative reward
Baselines: SAASBO TuRBO LineBO MS-UCB ADD-GPUCB DEC-HBO
Builds on: GP-UCB ADD-GPUCB DEC-HBO ADMM
Closest papers by meaning
- Vanilla Bayesian Optimization Performs Great in High Dimensions (ICML 2024 · similarity 0.90)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.88)
- BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability (NeurIPS 2026 · similarity 0.88)
- BOIDS: High-Dimensional Bayesian Optimization via Incumbent-Guided Direction Lines and Subspace Embeddings (AAAI 2025 · similarity 0.88)
- Understanding High-Dimensional Bayesian Optimization (ICML 2025 · similarity 0.87)
- Random Function Descent (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.