Research map / Probabilistic and scientific modeling / Bayesian optimization
Black-Box Optimization with Implicit Constraints for Public Policy
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 CageBO, a conditional VAE-based latent-space Bayesian optimization method that handles implicit feasibility constraints in public policy problems, evaluated on synthetic functions and Atlanta police redistricting.
Problem
Black-box optimization over decision spaces with implicit (analytically undefined) feasibility constraints and high dimensionality, motivated by police redistricting.
Approach
Learn a conditional VAE on labeled feasible/infeasible historical decisions to map the feasible region to an unconstrained latent space, run GP-LCB Bayesian optimization in that latent space restricted to feasible latent support, and use a nearest-feasible-neighbor post-decoding step for infeasible decodings.
Key results
- CageBO attains the lowest objective values consistently on 30-d Keane's bump and Michalewicz, with the conditional generative model greatly improving BO on Michalewicz where VAE-BO and CON-BO do not.
- On the Atlanta redistricting case (78 regions, 6 zones), CageBO's plan achieves the lowest workload variance among MILP, SA, VAE-BO and BO baselines.
- Theory: expected cumulative regret bound of Õ(sqrt(T gamma_T) + sqrt(d)(n+T)^{d/(d+1)}), sublinear hence no-regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CageBO instead of the baseline methods | Constrained 30-dimensional Keane's bump optimization · Keane's bump function | objective value | Helped |
| Use CageBO instead of the baseline methods | Constrained 30-dimensional Michalewicz optimization · Michalewicz function | objective value | Helped |
| Use CageBO instead of the baseline methods | Police redistricting optimization · Synthetic 6 × 6 grid | workload variance | Helped |
| Use CageBO instead of the baseline methods | Police redistricting optimization · Atlanta | workload variance | Helped |
| Increase the observed dataset size (ablation) | CageBO · Synthetic experiments and police redistricting (6 × 6 grid and Atlanta) | optimal objective value | Helped |
| Increase the observed dataset size (ablation) | CageBO's CVAE · Synthetic experiments | ability to generate new feasible solutions | Helped |
Surprising findings
- VAE-BO and CON-BO do not yield satisfactory outcomes on Michalewicz despite using learned latent spaces, while CageBO's conditional model substantially helps.
Limitations
- Post-decoding relies on nearest observed feasible decisions, so accuracy depends on coverage of the feasible set by the data.
- Theoretical bound assumes GP prior and Lipschitz continuity and an encoder Lipschitz assumption that may not hold for the learned model.
- Fairness concerns: redistricting based on historical 911 calls may reinforce biased policing; debiasing is only proposed, not evaluated.
Experimental setup
Datasets: Synthetic Keane's bump and Michalewicz samples synthetic 6x6 grid redistricting Atlanta police 911 calls-for-service data (2021-2022)
Benchmarks: Keane's bump function (30-d) Michalewicz function (30-d) synthetic 6x6 grid police redistricting Atlanta police redistricting
Metrics: objective value convergence workload variance cumulative regret
Baselines: BO simulated annealing MILP VAE-BO CON-BO
Builds on: Bayesian optimization conditional variational autoencoder GP-UCB VAE-guided Bayesian optimization
Closest papers by meaning
- BBOWP-Bench: Evaluating LLMs on Black-Box Optimization Word Problems (NeurIPS 2026 · similarity 0.83)
- Posterior Inference with Diffusion Models for High-dimensional Black-box Optimization (ICML 2025 · similarity 0.83)
- Posterior Inference in Latent Space for Scalable Constrained Black-box Optimization (NeurIPS 2026 · similarity 0.82)
- Sharpness-Aware Black-Box Optimization (ICLR 2025 · similarity 0.82)
- BOIDS: High-Dimensional Bayesian Optimization via Incumbent-Guided Direction Lines and Subspace Embeddings (AAAI 2025 · similarity 0.82)
- MetaBox-v2: A Unified Benchmark Platform for Meta-Black-Box Optimization (NeurIPS 2025 · similarity 0.81)
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.