A black-box optimization method with polynomial-based kernels and quadratic-optimization annealing
Yuki Minamoto, Yuya Sakamoto · 2025
Read A black-box optimization method with polynomial-based kernels and quadratic-optimization annealing by Yuki Minamoto, Yuya Sakamoto (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-04225.txt.
Introduction
Yuki Minamoto and Yuya Sakamoto wrote this research paper, published in 2025. It introduces kernel-QA, a black-box optimization method that builds a stand-in model of a costly function from simple polynomial pieces, then hands the search to annealing hardware built for binary problems.
Black-box optimization tackles functions you can only test, not inspect, common in design and tuning. The method fits its surrogate directly in a quadratic binary form, which Ising machines can attack efficiently. Tests ranged over artificial landscapes from single-valley to many-valley, with up to eighty real inputs or six hundred forty binary ones. The method shone on problems with many local traps and high dimension. The authors present it as a sturdy, scalable option for hard search tasks.
Catalog record
| CREATOR | Yuki Minamoto, Yuya Sakamoto |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-04225
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A black-box optimization method with polynomial-based kernels and quadratic-optimization annealing Yuki Minamoto, Yuya Sakamoto Abstract We introduce kernel-QA, a black-box optimization (BBO) method that constructs surrogate models analytically using low-order polynomial kernels within a quadratic unconstrained binary optimization (QUBO) framework, enabling efficient utilization of Ising machines. The method has been evaluated on artificial landscapes, ranging from uni-modal to multi-modal, with input dimensions extending to 80 for real variables and 640 for binary variables. The results demonstrate that kernel-QA is particularly effective for optimizing black-box functions characterized by local minima and high-dimensional inputs, showcasing its potential as a robust and scalable BBO approach. keywords black-box optimization, Annealing, Ising, Quantum, Bayesian 1 Introduction Black-box optimization (BBO) is a promising tool in various sectors where the objectives are expensive to evaluate black-box functions such as complex numerical simulations or experimental measurements. For such optimization problems, a serial optimization method is typically chosen. Here, an evaluation point in the search space is determined at each “cycle” (i.e., an iteration of the optimization loop) using information gathered from previous evaluations as shown in Fig. 1(a) . Typically, a model function is constructed in each cycle based on a relatively small dataset consisting of input-output pairs to/from the black-box function (plus some uncertainty information for some cases). Then, an input set that may minimize the model function is obtained as a potentially optimal input during the optimization step (2) in Fig. 1(a) . Subsequently, the black-box function is evaluated with the newly obtained input set, and finally, the new input-output pair is added to the dataset before repeating the next cycle. ((a)) Figure 1: A flow of a typical serial optimization for a black-box objective function. Among existing serial optimization methods, Bayesian optimization stands out for its efficiency in dealing with expensive-to-evaluate black-box functions by building a probabilistic model ( Frazier 2018 ; Snoek et al. 2012 ; Shahriari et al. 2016 ) . In Bayesian optimization, the Gaussian process (GP) regression typically plays a central role in searching the next evaluation point, balancing the need to explore regions of high uncertainty (to gather more information, typically called “exploration”) with the need to exploit regions with low expected values (in case of minimization problem as in this study, called “exploitation”). This exploration makes Bayesian optimization particularly effective for complex black-box functions. However, the performance of Bayesian optimization degrades as the dimensionality of the search space increases, a challenge known as the curse of dimensionality. This issue arises because the volume of the search space grows exponentially with the number of dimensions, rendering the Gaussian process model less informative. Consequences of high dimensionality include (i) optimization of the model function (step (2) in Fig. 1(a) ) becomes increasingly difficult, (ii) high cost in the construction of acquisition function ( Baptista and Poloczek 2018 ) , and (iii) insensitivity of the constructed function to the inputs (due to the complexity of the used kernel function) ( Hvarfner et al. 2024 ) . As a result, the number of evaluations needed to find an optimal solution becomes prohibitively large, and the method’s ability to exploit the model’s predictions diminishes. Factorization machine with quadratic-optimization annealing (FMQA) 1 1 1 FMQA originally stands for factorization machine with quantum annealing. However, this method is also straightforwardly incorporated with simulated annealers and gate-based quantum computers with a quantum approximate optimization algorithm (QAOA). Thus, a factorization machine with quadratic-optimization annealing may be more appropriate and general, and this point is acknowledged by the authors of the original FMQA study ( Kitai et al. 2020 ) . is another serial optimization method for BBO, which has been proposed and applied initially in material informatics ( Kitai et al. 2020 ; Inoue et al. 2022 ; Kim et al. 2022 ; Nawa et al. 2023 ) . The key in FMQA is to use factorization machine (FM) ( Rendle 2010 ) as a surrogate model for the black-box objective function. The use of an FM model allows the use of Ising machines 2 2 2 An Ising machine is designed to solve combinatorial optimization problems quickly by mimicking the spins’ behavior in an Ising model. In an Ising machine, a QUBO problem to be solved is encoded as a network of spins, where each spin represents a binary variable, and the interactions between spins represent the constraints or relationships between these variables. The machine then searches for the spin configuration that minimizes the system’s energy, which corresponds to the optimal solution to the problem. Such QUBO solvers include quantum annealers ( Dwave ) and simulated annealers implemented on GPU or FPGA ( Amplify ) . (simulated or quantum annealing) to solve an optimization problem represented by the model function in a Quadratic Unconstrained Binary Optimization (QUBO) manner at each cycle since a quadratic formulation defines the FM model. FMQA has also been extended and applied to problems with integer/real variables ( Izawa et al. 2022 ) and network ( Mao et al. 2023 ) . FMQA can handle a relatively large number of decision variables since the model function is optimized using Ising machines. However, the cost of model construction at each cycle is not negligible for large-dimension problems: Rendle 2010 has reported that the cost of training an FM is \mathcal{O}(n\cdot kd) , where n , k and d are the number of samples in the (current training) dataset, the size of the latent embedding vector (the model hyperparameter), and the number of decision variables (problem dimensions), respectively. Also, stochastic gradient descent typically used to construct an FM may yield locally optimal model coefficients, which is not ideal for a BBO context. Bayesian optimization of combinatorial structures (BOCS) is a type of Bayesian optimization method where optimization of acquisition function may be performed with simulated or quantum annealing, thereby circumventing the consequence (i) ( Baptista and Poloczek 2018 ; Kadowaki and Ambai 2022 ) . However, the Gibbs sampling used in the model (acquisition function) construction costs \mathcal{O}(n^{2}d^{2}T) , where T is the number of iterations ( Baptista and Poloczek 2018 ) . This paper focuses on high-order BBO problems where the number of initial samples is small relative to the input dimensions. For such problems, we propose an approach that mitigates the curse of dimensionality, particularly within serial optimization. The method we will propose here is named polynomial-based kernels and quadratic-optimization annealing (kernel-QA). Using low-order polynomial-based kernels for the model function resolves the abovementioned issues (i)–(iii), especially for high-dimensional BBO problems. The proposed method has been evaluated on different benchmark landscapes, highlighting the method’s robustness and efficiency in handling problems, including high-dimensional ones, where traditional methods typically falter in terms of cost or performance. The rest of the paper is structured as follows. We describe the formulation of the proposed BBO method in Sec. 2 . The technique is then assessed using the test functions and conditions described in Secs. 3.1 and 3.2 . The results of the assessments are presented and discussed in Sec. 4 . and important findings in the present study are summarized in the conclusions. 2 Method The keys in kernel-QA are utilizing a QUBO solver (or similar fast optimization solver with/without native constraint support) and the fast construction of