Continuous black-box optimization with quantum annealing and random subspace coding

In random subspace coding in a $d$-dimensional space, the dimensionality of subspace $d_{s}$ is first determined. Let ${\cal I}=\{i_{1},\ldots,i_{d_{s}}\}$ denote the indices of randomly chosen coordinates from $[1,d]$, and $\{[l_{i},u_{i}]\}_{i\in{\cal I}}$ be closed intervals in respective coordinates. Here, $l_{i}<u_{i}$, $l_{i}\in\Re$ and $u_{i}\in\Re$. Random sampling of each interval $[l_{i},u_{i}]$ is performed using the Dirichlet process method [26]. Given a positive integer $N$, this method can generate an interval such that any point in $[0,1]$ along each selected coordinate is included in the interval with probability $1/N$. Throughout this paper, $N$ is fixed as $3$. Then, an axis-parallel hyperrectangle $R$ is determined as

Later on, we denote it as “rectangle” for simplicity. Using $m$ rectangles $R_{1},\ldots,R_{m}$, the random subspace coding is defined as $z_{k}=I({\bm{x}}\in R_{k})$, where $I(\cdot)$ is one if the condition is satified and zero otherwise.

Given a binary vector ${\bm{z}}=\{z_{k}\}_{k=1,...,m}$, a point ${\bm{x}}\in\Re^{d}$ corresponds to ${\bm{z}}$, if ${\bm{x}}$ is included in all rectangles with $z_{k}=1$ and not included in those with $z_{k}=0$. Let $P$ denotes the intersection of all rectangles with $z_{k}=1$,

Let $N$ denote the union of all rectangles with $z_{k}=0$,

Since the preimage of ${\bm{z}}$ is described as $P({\bm{z}})-N({\bm{z}})$, ${\bm{z}}$ is decodable if and only if $P({\bm{z}})-N({\bm{z}})\neq\emptyset$.

In CONBQA, the training dataset $D$ are encoded to binary dataset $D^{\prime}=\{({\bm{z}}_{1},y_{1}),...,({\bm{z}}_{n},y_{n})\}$ through random subspace coding. Here, $\{y_{i}\}_{i=1,...,n}$ is normalized by min-max normalization, and thus these values are nonnegative. Then, a QUBO is prepared from $D^{\prime}$ and its optimal solution ${\bm{z}}^{*}$ is obtained with a quantum annealing. Next, ${\bm{z}}^{*}$ decoded to a continuous vector ${\bm{x}}^{*}$, and fed to the black-box system.

To model an underlying function from $D^{\prime}$, a nonnegative linear model:

is employed, and trained with least-squares fitting to $D^{\prime}$. Let ${\bm{w}}^{*}=\{w_{k}^{*}\}_{k=1,...,m}$ denote the trained parameter vector. Thus, the acquisition function is defined as

The unique solution with maximum of $g({\bm{z}})$ has $z_{k}=1$ for $\forall k$. However, this solution may be a non-decodable solution, because it is almost impossible to exist the region, where all rectangles are intersected. That is, unconstrained maximization of the acquisition function may lead to a non-decodable solution. To keep the optimal solution decodable, we add the following constraint, ${\bm{z}}\in C$ where

The meaning of this constraint is that the data point do not belong to $R_{i}$ and $R_{j}$ when two rectangles are not intersected. The constrained problem is then described as

In Sec. III, we will present a proof that the optimal solution of Eq. (7) is decodable.

The problem by Eq. (7) is treated as a QUBO and solved by a quantum annealing. As done in many application studies of quantum annealing, constraints are replaced by a penality term as follows,

where $A$ and $B$ are positive hyperparameters. To make contributions from two terms comparable, we use $A=1/\max_{k}\{w_{k}^{*}\}$ and $B=1$. Once the solution ${\bm{z}}^{*}$ of Eq. (8) is obtained by quantum annealing, a point ${\bm{x}}^{*}$ is randomly sampled from the preimage $P({\bm{z}}^{*})-N({\bm{z}}^{*})$, evaluated to yield a new outcome $y^{*}$ by the black-box system. The new data point $({\bm{x}}^{*},y^{*})$ is then added to the dataset $D$, and the next iteration is put forward.

Using D-Wave Advantage, we implement a hardware-assisted system for continuous black-box optimization. In the previous section, we proved that, if the hardware optimizer finds the optimal solution of Eq. (7), it is always decodable. In reality, however, a quantum annealer and other algorithms solve the QUBO problem defined by Eq. (8) and do not always return the ground state. Thus, there are the following three possible cases when the solution ${\bm{z}}^{*}$ is calculated by quantum annealing:

1. 1.

   Empty: $P({\bm{z}}^{*})=\emptyset$.

2. 2.

   Admissible: $P({\bm{z}}^{*})\neq\emptyset$ and $P({\bm{z}}^{*})\cap N({\bm{z}}^{*})\neq\emptyset$.

3. 3.

   Decodable: $P({\bm{z}}^{*})\neq\emptyset$ and $P({\bm{z}}^{*})\cap N({\bm{z}}^{*})=\emptyset$.

For a decoder, if ${\bm{z}}^{*}$ with decodable or admissible is recommended, the next data point ${\bm{x}}^{*}$ is randomly sampled from the region with $P({\bm{z}}^{*})\neq\emptyset$. On the other hand, when the solution is empty, ${\bm{x}}^{*}$ is randomly selected from the whole search space.

To test the performance, we employ a 6-dimensional function called Hartmann-6 [28] that is often used for testing global optimizers. In this testing function, whole search spaces are determined as $[0,1]$ in all coordinates. For all experiments, the parameters of random subspace coding are determined as $m=60$ and $d_{s}=2$. The performance of CONBQA is measured by regret $S_{T}$, which is the difference between the optimal value of Hartmann-6 and the best one observed so far in the black-box optimization. Thus, the purpose of the present continuous black-box optimization is to obtain small $S_{T}$ with as few iterations as possible. Figure 3 shows the regret in logarithmic scale against the number of iterations for CONBQA, AddGP based on UCB score, and random search. In the 15 initial steps, ${\bm{x}}$ is randomly sampled from the whole search space, and afterwords, iterations controlled by CONBQA or Add-GP are performed. Here, the average over 10 independent runs, where initial randomly-sampled data are different, is shown with the error indicating the standard deviation.

As a QUBO solver used in CONBQA, we employ D-Wave Advantage with hybrid solver service[29], simulated annealing using dwave-neal with default setting[30], and greedy search. It is remarkable that when the number of iterations is small, regardless of QUBO solvers, CONBQA outperforms Add-GP which performed best in a previous benchmark study [8]. Of course, in comparison with random search, better optimization performance of CONBQA is confirmed. This result indicates that our framework to solve continuous black-box optimization using random subspace coding and QUBO solvers as acquisition function optimizer is work well. In addition, among the CONBQA variants, the quantum annealer performed best. In particular, optimization result by quantum annealer is quite better than that by greedy search, indicating that the performance of continuous black-box optimization can possibly be improved by a better QUBO solvers, i.e., specialized hardware.

Next, we address the decordability in optimization process. Table 1 shows the fraction of empty, admissible, and decodable solutions in the iterations in CONBQA depending on the QUBO solvers. As an important fact, we have never observed empty solutions by three methods to solve QUBO. Simulated annealing and greedy search had a higher fraction of decodable solutions than the quantum annealer despite that they performed poorly in optimization (see Fig. 3). This result indicates that the solutions obtained from the simulated annealing or greedy search are well satisfying the constraint of Eq. (6), but tend to stuck at local minima with larger values of the first term in Eq. (8). On the other hand, quantum annealer recommends many admissible solutions, which were not fine-tuned for the constraint, but better optimization is realized. This means that the solutions by quantum annealer have smaller value of the first term in Eq. (8) instead of fulfilling the constraint exactly, and CONBQA could get closer to the global optimal solution.

The performance of CONBQA is tested further with three additional benchmark functions from 2013 IEEE CEC Competition on Niching Methods for Multimodal Optimization [31]. Among the 20 functions provided, three high-dimensional functions of $F_{12}$ (5D), $F_{11}$ (10D), and $F_{12}$ (10D) are chosen. Their dimensionality is 5, 10, and 10, respectively. To try some experimental settings with different number of encoding bits, $m$, we perform CONBQA with simulated annealing. In these testing functions, whole search space are determined as $[0,1]$ in all coordinates. Figure 4 shows the regret in logarithmic scale against the number of iterations for CONBQA with $m=20,60$, and $100$, Add-GP, and random search. For random subspace coding, $d_{s}=2$ is used. The average over 10 independent runs, where initial 15 randomly-sampled data are different, is shown with the error indicating the standard deviation.

For relatively low-dimensional dataset of $F_{12}$ (5D), CONBQA is superior in finding better solutions in comparison with Add-GP regardless of $m$. In this case, $m=60$ shows the better optimization performance. If $m$ is increased, the resolution of random subspace coding becomes high, which is discussed in the next subsection, and we can get closer to the optimal solution in principle. On the other hand, the regression model becomes complicated, and in an early stage of iterations, an accurate prediction model is difficult to construct by statistical problems. Thus, an appropriate value of $m$ will be determined by this trade-off and is strongly depending on the target problem.

For 10-dimensional datasets ($F_{11}$ (10D) and $F_{12}$ (10D)), CONBQA outperforms Add-GP in an early stage, but slightly worse than Add-GP at the final stage of optimization. This is because CONBQA cannot get exactly to the optimal point due to the finite resolution of random subspace coding. Note that this resolution problem can be resolved by using large $m$, but the trade-off described above should be appeared. Thus, it is not always necessary to make $m$ larger to obtain better optimizations. In applications such as experimental and simulation conditions tuning in physics, chemistry, and materials science, the number of iterations is severely limited. That is, the early stage of optimization is more important for these applications. In such cases, CONBQA would be preferred over Add-GP.

In the benchmark, CONBQA was applied to up to 10 dimensional problems. Since the ability of Ising machines is growing rapidly, CONBQA will likely be applied to problems with higher dimensionality in the future. To estimate how many bits are necessary for CONBQA, we investigated the resolution of random subspace coding for $d=10,100$, and $1000$. The resolution is characterized by the average size of the intersection of all rectangles enclosing a randomly chosen point which is represented by $R_{I}$. The size of a rectangle is measured by the average of its edge lengths. If $R_{I}$ is small, in a decoder, the possible region of ${\bm{x}}^{*}$ is small when ${\bm{z}}^{*}$ is given. Thus, the high resolution by random subspace coding is realized when $R_{I}$ is small enough.

Figure 5 shows $R_{I}$ depending on the number of bits for $d=10,100$, and $1000$ for $d_{s}=2$. Here, the average over 50 randomly chosen points is shown with the error indicating the standard deviation. In our benchmarking in Sec. IV B, if 100 bits are used for 10-dimensional problems, a better performance than Add-GP in an early stage of optimization is realized in CONBQA. According to this fact, $R_{I}\simeq 0.4$ would be enough to work CONBQA effectively for $d=10$. Thus, with 10,000 bits, it is possible to reach sufficiently high resolution for 1,000-dimensional problems. For 100-dimensional problems, 1,000 bits will be sufficient. On the other hand, to get more closer to the optimal solution at the final stage of optimization, it is important to improve a resolution. In this case, we will need ten times more bits for each dimension of problems at least. Notice that statistical aspects are totally disregarded in this analysis: solving a high-dimensional problem may require a prohibitive number of black-box evaluations. Then, the required number of bits is strongly depending on target problems. Nevertheless, CONBQA has a potential to solve high-dimensional continuous black-box optimization problems that are difficult to solve by conventional methodologies when more bits will be used in quantum annealer.