Convergence Rates of Constrained Expected Improvement
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912812951928832 |
|---|---|
| author | Wang, Haowei Wang, Jingyi Dai, Zhongxiang Chiang, Nai-Yuan Ng, Szu Hui Petra, Cosmin G. |
| author_facet | Wang, Haowei Wang, Jingyi Dai, Zhongxiang Chiang, Nai-Yuan Ng, Szu Hui Petra, Cosmin G. |
| contents | Constrained Bayesian optimization (CBO) methods have seen significant success in black-box optimization with constraints. One of the most commonly used CBO methods is the constrained expected improvement (CEI) algorithm. CEI is a natural extension of expected improvement (EI) when constraints are incorporated. However, the theoretical convergence rate of CEI has not been established. In this work, we study the convergence rate of CEI by analyzing its simple regret upper bound. First, we show that when the objective function $f$ and constraint function $c$ are assumed to each lie in a reproducing kernel Hilbert space (RKHS), CEI achieves the convergence rates of $\mathcal{O} \left(t^{-\frac{1}{2}}\log^{\frac{d+1}{2}}(t) \right) \ \text{and }\ \mathcal{O}\left(t^{\frac{-ν}{2ν+d}} \log^{\fracν{2ν+d}}(t)\right)$ for the commonly used squared exponential and Matérn kernels ($ν>\frac{1}{2}$), respectively. Second, we show that when $f$ is assumed to be sampled from Gaussian processes (GPs), CEI achieves similar convergence rates with a high probability. Numerical experiments are performed to validate the theoretical analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11323 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence Rates of Constrained Expected Improvement Wang, Haowei Wang, Jingyi Dai, Zhongxiang Chiang, Nai-Yuan Ng, Szu Hui Petra, Cosmin G. Machine Learning Constrained Bayesian optimization (CBO) methods have seen significant success in black-box optimization with constraints. One of the most commonly used CBO methods is the constrained expected improvement (CEI) algorithm. CEI is a natural extension of expected improvement (EI) when constraints are incorporated. However, the theoretical convergence rate of CEI has not been established. In this work, we study the convergence rate of CEI by analyzing its simple regret upper bound. First, we show that when the objective function $f$ and constraint function $c$ are assumed to each lie in a reproducing kernel Hilbert space (RKHS), CEI achieves the convergence rates of $\mathcal{O} \left(t^{-\frac{1}{2}}\log^{\frac{d+1}{2}}(t) \right) \ \text{and }\ \mathcal{O}\left(t^{\frac{-ν}{2ν+d}} \log^{\fracν{2ν+d}}(t)\right)$ for the commonly used squared exponential and Matérn kernels ($ν>\frac{1}{2}$), respectively. Second, we show that when $f$ is assumed to be sampled from Gaussian processes (GPs), CEI achieves similar convergence rates with a high probability. Numerical experiments are performed to validate the theoretical analysis. |
| title | Convergence Rates of Constrained Expected Improvement |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.11323 |