Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyond

Abstract:Bayesian optimization (BO) is effective for expensive black-box optimization, but its performance often degrades on multimodal or high-dimensional problems. A promising remedy is to run multiple local search processes, such as trust region--based BO, and allocate evaluations to those with high potential. However, current best values do not always reflect the final performance of each process. We propose a trajectory-aware best-arm identification (BAI) framework that uses optimization history to guide this allocation. The proposed method extrapolates improvement trajectories, estimates final performance, and progressively eliminates low-potential candidates. For trust region--based BO, we theoretically show that the proposed BAI-guided allocation accelerates convergence to the global optimum under mild assumptions. Experiments on synthetic and real-world benchmarks demonstrate that our method improves BO on multimodal problems. We also show that the same mechanism can enhance other local or population-based optimizers, suggesting its potential as a general extension strategy for multimodal black-box optimization.

Machine Learning (cs.LG)

arXiv:2605.31050 [cs.LG]

(or arXiv:2605.31050v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2605.31050 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.