Black Box Optimization Using QUBO and the Cross Entropy Method
- URL: http://arxiv.org/abs/2206.12510v1
- Date: Fri, 24 Jun 2022 22:57:24 GMT
- Title: Black Box Optimization Using QUBO and the Cross Entropy Method
- Authors: Jonas N\"u{\ss}lein, Christoph Roch, Thomas Gabor, Claudia
Linnhoff-Popien, Sebastian Feld
- Abstract summary: 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.
- Score: 11.091089276821716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Black box optimization (BBO) 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 which can then be solved via
white box optimization methods. In this paper we present our approach BOX-QUBO,
where the surrogate model is a QUBO matrix. However, unlike in previous
state-of-the-art approaches, this matrix is not trained entirely by regression,
but mostly by classification between 'good' and 'bad' solutions. This better
accounts for the low capacity of the QUBO matrix, resulting in significantly
better solutions overall. We tested our approach against the state-of-the-art
on four domains and in all of them BOX-QUBO showed significantly better
results. A second contribution of this paper is the idea to also solve white
box problems, i.e. problems which could be directly formulated as QUBO, by
means of black box optimization in order to reduce the size of the QUBOs to
their information-theoretic minimum. The experiments show that this
significantly improves the results for MAX-$k$-SAT.
Related papers
- High-Dimensional Bayesian Optimization Using Both Random and Supervised Embeddings [0.6291443816903801]
This paper proposes a high-dimensionnal optimization method incorporating linear embedding subspaces of small dimension.
The resulting BO method combines in an adaptive way both random and supervised linear embeddings.
The obtained results show the high potential of EGORSE to solve high-dimensional blackbox optimization problems.
arXiv Detail & Related papers (2025-02-02T16:57:05Z) - Sharpness-Aware Black-Box Optimization [47.95184866255126]
We propose a Sharpness-Aware Black-box Optimization (SABO) algorithm, which applies a sharpness-aware minimization strategy to improve the model generalization.
Empirically, extensive experiments on the black-box prompt fine-tuning tasks demonstrate the effectiveness of the proposed SABO method in improving model generalization performance.
arXiv Detail & Related papers (2024-10-16T11:08:06Z) - Efficient Black-box Adversarial Attacks via Bayesian Optimization Guided by a Function Prior [36.101904669291436]
This paper studies the challenging black-box adversarial attack that aims to generate examples against a black-box model by only using output feedback of the model to input queries.
We propose a Prior-guided Bayesian Optimization (P-BO) algorithm that leverages the surrogate model as a global function prior in black-box adversarial attacks.
Our theoretical analysis on the regret bound indicates that the performance of P-BO may be affected by a bad prior.
arXiv Detail & Related papers (2024-05-29T14:05:16Z) - Reinforced In-Context Black-Box Optimization [64.25546325063272]
RIBBO is a method to reinforce-learn a BBO algorithm from offline data in an end-to-end fashion.
RIBBO employs expressive sequence models to learn the optimization histories produced by multiple behavior algorithms and tasks.
Central to our method is to augment the optimization histories with textitregret-to-go tokens, which are designed to represent the performance of an algorithm based on cumulative regret over the future part of the histories.
arXiv Detail & Related papers (2024-02-27T11:32:14Z) - Predictive Modeling through Hyper-Bayesian Optimization [60.586813904500595]
We propose a novel way of integrating model selection and BO for the single goal of reaching the function optima faster.
The algorithm moves back and forth between BO in the model space and BO in the function space, where the goodness of the recommended model is captured.
In addition to improved sample efficiency, the framework outputs information about the black-box function.
arXiv Detail & Related papers (2023-08-01T04:46:58Z) - How to Robustify Black-Box ML Models? A Zeroth-Order Optimization
Perspective [74.47093382436823]
We address the problem of black-box defense: How to robustify a black-box model using just input queries and output feedback?
We propose a general notion of defensive operation that can be applied to black-box models, and design it through the lens of denoised smoothing (DS)
We empirically show that ZO-AE-DS can achieve improved accuracy, certified robustness, and query complexity over existing baselines.
arXiv Detail & Related papers (2022-03-27T03:23:32Z) - Black-Box Optimization via Generative Adversarial Nets [6.46243851154653]
We present agenerative adversarial nets (OPT-GAN) to guide search on black-box problems.
Experiments demonstrate that OPT-GAN outperforms other classical BBO algorithms.
arXiv Detail & Related papers (2021-02-07T19:12:09Z) - Black-Box Optimization Revisited: Improving Algorithm Selection Wizards
through Massive Benchmarking [8.874754363200614]
Existing studies in black-box optimization for machine learning suffer from low generalizability.
We propose a benchmark suite, OptimSuite, which covers a broad range of black-box optimization problems.
ABBO achieves competitive performance on all benchmark suites.
arXiv Detail & Related papers (2020-10-08T14:17:30Z) - 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)
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.