{"ID":2895324,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.09828","arxiv_id":"2507.09828","title":"Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization","abstract":"Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demonstrated in a wide range of applications. However, theoretical analyses of EI are limited compared with other theoretically established algorithms. This paper analyzes a randomized variant of EI, which evaluates the EI from the maximum of the posterior sample path. We show that this posterior sampling-based random EI achieves the sublinear Bayesian cumulative regret bounds under the assumption that the black-box function follows a Gaussian process. Finally, we demonstrate the effectiveness of the proposed method through numerical experiments.","short_abstract":"Bayesian optimization is a powerful tool for optimizing an expensive-to-evaluate black-box function. In particular, the effectiveness of expected improvement (EI) has been demonstrated in a wide range of applications. However, theoretical analyses of EI are limited compared with other theoretically established algorith...","url_abs":"https://arxiv.org/abs/2507.09828","url_pdf":"https://arxiv.org/pdf/2507.09828v3","authors":"[\"Shion Takeno\",\"Yu Inatsu\",\"Masayuki Karasuyama\",\"Ichiro Takeuchi\"]","published":"2025-07-13T23:37:31Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\"]","methods":"[]","has_code":false}