LAMBDA: Covering the Solution Set of Black-Box Inequality by Search Space Quantization

• URL: http://arxiv.org/abs/2203.13708v1
• Date: Fri, 25 Mar 2022 15:24:05 GMT
• Title: LAMBDA: Covering the Solution Set of Black-Box Inequality by Search Space Quantization
• Authors: Lihao Liu, Tianyue Feng, Xingyu Xing, Junyi Chen
• Abstract summary: Black-box functions are broadly used to model complex problems that provide no explicit information but the input and output. Covering as much as possible of the solution set through limited evaluations to the black-box objective function is defined as the Black-Box Coverage (BBC) problem.
• Score: 1.345821655503426
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Black-box functions are broadly used to model complex problems that provide no explicit information but the input and output. Despite existing studies of black-box function optimization, the solution set satisfying an inequality with a black-box function plays a more significant role than only one optimum in many practical situations. Covering as much as possible of the solution set through limited evaluations to the black-box objective function is defined as the Black-Box Coverage (BBC) problem in this paper. We formalized this problem in a sample-based search paradigm and constructed a coverage criterion with Confusion Matrix Analysis. Further, we propose LAMBDA (Latent-Action Monte-Carlo Beam Search with Density Adaption) to solve BBC problems. LAMBDA can focus around the solution set quickly by recursively partitioning the search space into accepted and rejected sub-spaces. Compared with La-MCTS, LAMBDA introduces density information to overcome the sampling bias of optimization and obtain more exploration. Benchmarking shows, LAMBDA achieved state-of-the-art performance among all baselines and was at most 33x faster to get 95% coverage than Random Search. Experiments also demonstrate that LAMBDA has a promising future in the verification of autonomous systems in virtual tests.

Related papers

• Non-Myopic Multi-Objective Bayesian Optimization [64.31753000439514]
  We consider the problem of finite-horizon sequential experimental design to solve multi-objective optimization problems. This problem arises in many real-world applications, including materials design. We propose the first set of non-myopic methods for MOO problems.
  arXiv  Detail & Related papers  (2024-12-11T04:05:29Z)
• LAMBDA: Covering the Multimodal Critical Scenarios for Automated Driving Systems by Search Space Quantization [33.87626198349963]
  Black-Box Optimization (BBO) was introduced to accelerate the scenario-based test of automated driving systems (ADSs) All the subspaces representing danger in the logical scenario space, rather than only the most critical concrete scenario, play a more significant role for the safety evaluation. We propose LAMBDA (Latent-Action Monte-Carlo Beam Search with Density Adaption) to solve BBC problems.
  arXiv  Detail & Related papers  (2024-11-30T15:57:05Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Covariance-Adaptive Sequential Black-box Optimization for Diffusion Targeted Generation [60.41803046775034]
  We show how to perform user-preferred targeted generation via diffusion models with only black-box target scores of users. Experiments on both numerical test problems and target-guided 3D-molecule generation tasks show the superior performance of our method in achieving better target scores.
  arXiv  Detail & Related papers  (2024-06-02T17:26:27Z)
• Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning [77.61565726647784]
  We propose a simple black-box search method that first clusters and prunes the search space to focus exclusively on influential prompt tokens. Our findings underscore the critical role of search space design and optimization in enhancing both the usefulness and the efficiency of black-box prompt-based learning.
  arXiv  Detail & Related papers  (2023-10-19T14:25:06Z)
• Black Box Optimization Using QUBO and the Cross Entropy Method [11.091089276821716]
  Black box optimization can be used to optimize functions whose analytic form is unknown. A common approach to realize BBO is to learn a surrogate model which approximates the target black box function. We present our approach BOX-QUBO, where the surrogate model is a QUBO matrix.
  arXiv  Detail & Related papers  (2022-06-24T22:57:24Z)
• Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization [32.856318660282255]
  Black-box multi-objective optimization (MOO) using expensive function evaluations (also referred to as experiments) We propose a general framework for solving MOO problems based on the principle of output space entropy (OSE) search. Our OSE search based algorithms improve over state-of-the-art methods in terms of both computational-efficiency and accuracy of MOO solutions.
  arXiv  Detail & Related papers  (2021-10-13T18:43:39Z)
• Projection & Probability-Driven Black-Box Attack [205.9923346080908]
  Existing black-box attacks suffer from the need for excessive queries in the high-dimensional space. We propose Projection & Probability-driven Black-box Attack (PPBA) to tackle this problem. Our method requires at most 24% fewer queries with a higher attack success rate compared with state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-05-08T03:37:50Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  We propose a novel Bayesian optimization (BO) algorithm to tackle the challenge of model selection in this setting. In order to solve the resulting multiple black-box function optimization problem jointly and efficiently, we exploit potential correlations among black-box functions. We are the first to formulate the problem of stepwise model selection (SMS) for sequence prediction, and to design and demonstrate an efficient joint-learning algorithm for this purpose.
  arXiv  Detail & Related papers  (2020-01-12T09:42:19Z)
• DEFT-FUNNEL: an open-source global optimization solver for constrained grey-box and black-box problems [0.0]
  DEFT-FUNNEL is an open-source global optimization algorithm for general constrained grey-box and black-box problems. The code as well as the test sets used for experiments are available at the Github repository.
  arXiv  Detail & Related papers  (2019-12-29T11:43:53Z)

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.