Research map / Optimization / Nonconvex and smooth optimization
Convergence Rates of Constrained Expected Improvement
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.
Gives the first simple-regret (convergence-rate) upper bounds for constrained expected improvement (CEI), under frequentist RKHS assumptions and Bayesian GP-objective assumptions, validated with synthetic and benchmark experiments.
Problem
Convergence rates of constrained Bayesian optimization via the CEI acquisition function were unknown; the paper targets simple regret upper bounds for CEI in noise-free settings with a black-box constraint.
Approach
Analyzes CEI's multiplicative objective-times-probability-of-feasibility structure to bound simple regret by the posterior standard deviation at selected points, uses maximum information gain to obtain improved rates, and extends the analysis to a Bayesian (GP-sampled objective) setting with high-probability bounds plus a tolerance parameter for constraints.
Key results
- CEI achieves simple regret O(t^{-1/2} log^{(d+1)/2} t) for SE kernel and O(t^{-nu/(2nu+d)} log^{nu/(2nu+d)} t) for Matern kernels under frequentist assumptions, improving the direct extension of prior EI analysis for SE with d>=3.
- Under a Bayesian GP-objective assumption, CEI attains O(t^{-1/2} log^{(d+2)/2} t) for SE and a Matern rate with high probability 1-delta.
- Experiments on synthetic RKHS/GP problems and five benchmarks show sublinear/fast convergence of simple regret to zero, consistent with theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use maximum information gain to bound posterior standard deviation | CEI under frequentist RKHS assumptions · Squared exponential and Matérn kernels; stated dimensions and smoothness conditions | simple regret convergence rate: The improved rates are \mathcal{O} \left(t^{-\frac{1}{2}}\log^{\frac{d+1}{2}}(t) \right) for SE and \mathcal{O}\left(t^{ | Helped |
| Assume the objective is sampled from a Gaussian process rather than lying in an RKHS | CEI · Squared exponential and Matérn kernels | simple regret convergence rate: For SE, \log^{\frac{d+1}{2}}(t) -> \log^{\frac{d+2}{2}}(t); for Matérn, \log^{\frac{\nu}{2\nu+d}}(t) -> \log^{\frac{2\nu | Mixed |
| Use CEI with squared exponential and Matérn kernels on the synthetic and benchmark problems | CEI · Eight synthetic problems and five benchmark problems | simple regret | Helped |
Surprising findings
- Simple regret bounds for CEI match the known EI rates, and the constraint enters only through a constant factor 1/Phi(-B_c) that becomes asymptotically irrelevant under a tolerance parameter.
Limitations
- Noise-free setting only; extension to noisy constraints is non-trivial and not fully covered
- Requires an initial feasible sample for CEI to be defined
- Experiments are primarily validation rather than performance comparisons
Experimental setup
Datasets: synthetic functions sampled from RKHS of SE/Matern kernels synthetic GP prior samples five CBO benchmark test problems (including Hartmann-6 and Rosenbrock)
Benchmarks: synthetic RKHS and GP problems (d=2,4) five CBO test problems (including Hartmann 6D, Rosenbrock)
Metrics: simple regret log-log convergence rate
Baselines: direct extension of Bull (2011) EI analysis to constrained case
Builds on: constrained expected improvement expected improvement GP-UCB noise-free regret analysis (Vakili et al.)
Closest papers by meaning
- Boundary Exploration for Bayesian Optimization With Unknown Physical Constraints (ICML 2024 · similarity 0.84)
- Stochastic Bayesian Optimization with Unknown Continuous Context Distribution via Kernel Density Estimation (AAAI 2024 · similarity 0.84)
- Expected Hypervolume Improvement Is a Particular Hypervolume Improvement (AAAI 2025 · similarity 0.83)
- Constrained Bayesian Optimization under Partial Observations: Balanced Improvements and Provable Convergence (AAAI 2024 · similarity 0.83)
- A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization (ICML 2025 · similarity 0.83)
- BayeSQP: Bayesian Optimization through Sequential Quadratic Programming (NeurIPS 2025 · similarity 0.83)
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.