Improving search efficiency via adaptive acquisition function selection in discrete black-box optimization

• URL: http://arxiv.org/abs/2605.10856v1
• Date: Mon, 11 May 2026 17:03:01 GMT
• Title: Improving search efficiency via adaptive acquisition function selection in discrete black-box optimization
• Abstract summary: In black-box optimization, it is important to identify promising solutions efficiently within a limited number of trials.<n>We propose a hybrid method that uses BOCS as the main search framework and generates alternative unevaluated points.<n>We show that its effectiveness comes from selecting points that promote search progress within Hamming-distance neighborhoods.
• Score: 0.7734726150561088
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In discrete-variable black-box optimization, the number of candidate solutions grows combinatorially, while each evaluation is often expensive. Therefore, it is important to identify promising solutions efficiently within a limited number of trials. Bayesian Optimization of Combinatorial Structures (BOCS), an existing parametric method, works effectively when only a small amount of data is available. However, as the number of observations increases, BOCS tends to repeatedly propose points that have already been evaluated, which leads to search stagnation. A random-point addition strategy has been proposed to address this issue when an evaluated point is proposed, but it cannot sufficiently exploit information from promising data obtained so far. In this study, we propose a hybrid method that uses BOCS as the main search framework and generates alternative unevaluated points using a Gaussian process only when search stagnation is detected. In the Gaussian-process-based component, multiple Lower Confidence Bound (LCB) acquisition functions are adaptively selected to dynamically control the balance between exploitation and exploration. Numerical experiments using fully connected Quadratic Unconstrained Binary Optimization (QUBO) and Higher-order Unconstrained Binary Optimization (HUBO) as black-box functions show that the proposed method finds solutions with better objective values than the conventional random-point addition method in both settings. Additional analyses show that its effectiveness comes from selecting points that promote search progress within Hamming-distance neighborhoods, rather than simply adding low-energy points near promising solutions. Experiments with sparse surrogate models for quantum annealer applications further suggest the importance of retaining near-fully connected representational capacity.

Related papers

• Adam assisted Fully informed Particle Swarm Optimization ( Adam-FIPSO ) based Parameter Prediction for the Quantum Approximate Optimization Algorithm (QAOA) [1.024113475677323]
  The Quantum Approximate Optimization Algorithm (QAOA) is a prominent variational algorithm used for solving optimization problems such as the Max-Cut problem.<n>A key challenge in QAOA lies in efficiently identifying suitable parameters that lead to high-quality solutions.
  arXiv  Detail & Related papers  (2025-06-07T13:14:41Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment.<n>We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO) Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
  arXiv  Detail & Related papers  (2024-02-05T02:54:50Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  In this paper, we show a natural connection between non-dominated solutions and the extreme quantile of the joint cumulative distribution function. Motivated by this link, we propose the Pareto-compliant CDF indicator and the associated acquisition function, BOtied. Our experiments on a variety of synthetic and real-world problems demonstrate that BOtied outperforms state-of-the-art MOBO acquisition functions.
  arXiv  Detail & Related papers  (2023-06-01T04:50:06Z)
• Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
  This paper proposes a novel surrogate-based global optimization algorithm to solve linearly constrained mixed-variable problems.<n>The proposed approach is based on constructing a piecewise affine surrogate of the objective function over feasible samples.<n>The two algorithms are evaluated on several unconstrained and constrained mixed-variable benchmark problems.
  arXiv  Detail & Related papers  (2023-02-09T15:04:35Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Bayesian Optimization over Permutation Spaces [30.650753803587794]
  We propose and evaluate two algorithms for BO over Permutation Spaces (BOPS) We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly. Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for spaces.
  arXiv  Detail & Related papers  (2021-12-02T08:20:50Z)
• Efficient Exploration in Binary and Preferential Bayesian Optimization [0.5076419064097732]
  We show that it is important for BO algorithms to distinguish between different types of uncertainty. We propose several new acquisition functions that outperform state-of-the-art BO functions.
  arXiv  Detail & Related papers  (2021-10-18T14:44:34Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  Reinforcement learning aims to find an optimal policy by interaction with an environment. Policy gradients for local search are often obtained from random perturbations. We develop an algorithm utilizing a probabilistic model of the objective function and its gradient.
  arXiv  Detail & Related papers  (2021-06-22T16:07:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity search [0.0]
  We propose the Bayesian optimisation of Elites (BOP-Elites) algorithm. By considering user defined regions of the feature space as 'niches' our task is to find the optimal solution in each niche. The resulting algorithm is very effective in identifying the parts of the search space that belong to a niche in feature space, and finding the optimal solution in each niche.
  arXiv  Detail & Related papers  (2020-05-08T23:49:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.