Stage-dependent integer-binary encoding in factorization-machine black-box optimization

Technical Summary: Stage-dependent integer-binary encoding in factorization-machine black-box optimization

Problem Statement
Black-box optimization (BBO) addresses problems where objective functions lack explicit analytical forms and are expensive to evaluate. Factorization Machine with Quadratic-optimization Annealing (FMQA) is a prominent BBO approach that constructs a surrogate model using a Factorization Machine (FM) and optimizes it using an Ising machine. A critical component of FMQA is the conversion of integer or continuous variables into binary variables via integer-binary encoding (e.g., one-hot, domain-wall, or binary encoding) to formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model.

Conventional FMQA employs a single integer-binary encoding method throughout both the machine learning stage (surrogate model construction) and the solution search stage (Ising machine optimization). However, prior research suggests a trade-off: domain-wall encoding often yields superior solution search performance in Ising machines, while one-hot encoding has been observed to produce lower objective function values in the overall FMQA optimization process. This discrepancy implies that the encoding optimal for learning the surrogate landscape may differ from the encoding optimal for searching that landscape. Conventional methods, by fixing a single encoding, may fail to fully exploit the distinct capabilities of the FM and the Ising machine.

Methodology
The authors propose a stage-dependent FMQA framework that utilizes different integer-binary encoding methods for the machine learning and solution search stages. The core of this approach involves:

1. Dual-Encoding Strategy: The framework trains the FM surrogate model using an encoding suitable for learning (specifically one-hot encoding in the proposed "OhDw" variant) and then converts the resulting surrogate model into a different encoding suitable for search (specifically domain-wall encoding) before optimization by the Ising machine.
2. QUBO Matrix Conversion: To enable this switching, the authors derived mathematical conversion formulas between the QUBO matrices of one-hot and domain-wall encodings. These formulas ensure that the surrogate objective landscape is preserved over feasible integer states up to an additive constant.
   • The conversion from one-hot to domain-wall involves transforming diagonal and off-diagonal terms of the QUBO matrix $Q^{(oh)}$ to $Q^{(dw)}$ using specific summation relations (Eqs. 18–20).
   • The inverse conversion (domain-wall to one-hot) is also derived (Eqs. 22–24).
   • The computational complexity for these mutual conversions is established as $O(N^2q^2)$, where $N$ is the input dimension and $q$ is the number of discretization levels.
3. Algorithmic Workflow:
   • Learning Stage: An FM is trained on input-output data encoded using one-hot encoding.
   • Conversion: The trained surrogate model (represented as a QUBO matrix) is converted from one-hot to domain-wall encoding.
   • Search Stage: The converted QUBO, augmented with domain-wall encoding constraints, is optimized using an Ising machine (Fixstars Amplify Annealing Engine) to find candidate solutions.
   • Evaluation: Solutions are decoded, evaluated against the true black-box function, and added to the training dataset for the next iteration.

Key Contributions

1. Framework Proposal: Introduction of an FMQA framework that decouples the encoding choice between the learning and search stages, rather than fixing a single encoding throughout the process.
2. Theoretical Derivation: Derivation of mutual conversion formulas between one-hot and domain-wall QUBO matrices that preserve the surrogate objective landscape over feasible states, enabling the switching of encodings without losing the learned model's fidelity.
3. Empirical Decomposition: A numerical decomposition of the effects of integer-binary encoding into contributions from the learning stage and the solution search stage, evaluating them separately to understand their distinct impacts on performance.

Experimental Results
The proposed method was evaluated on the Rastrigin function, a multimodal benchmark problem, with input dimensions $N \in \{2, 5\}$ and discretization levels $q \in \{61, 301\}$. The performance of the proposed "OhDw" method (one-hot for learning, domain-wall for search) was compared against conventional single-encoding variants (Oh, Dw, Bi) and Bayesian Optimization (BO).

• Dominance of Learning-Stage Encoding: Across all conditions, the encoding used in the learning stage was the dominant factor governing optimization performance. Methods employing one-hot encoding for learning (Oh and OhDw) consistently achieved lower residual errors than those using domain-wall or binary encoding for learning.
• Stage-Dependent Benefits: The benefit of switching to domain-wall encoding for the search stage was condition-dependent:
  • For $N=5$ and $q=301$ (finer discretization, larger search space), the OhDw method achieved lower residual errors and solutions closer to the global optimum compared to the Oh method (one-hot only).
  • For $N=5$ and $q=61$, the Oh method slightly outperformed OhDw.
  • For $N=2$, no significant performance difference was observed between Oh and OhDw.
• Search Stability: Analysis of the solution search stage indicated that domain-wall encoding allows for more stable transitions between feasible states in the Ising machine, whereas one-hot encoding requires passing through constraint-violating states, potentially reducing search stability.

Significance and Claims
The paper claims that the choice of integer-binary encoding is not merely a representational choice but a design element that serves distinct roles in the learning and solution search stages of FMQA. The primary finding is that one-hot encoding in the learning stage is the primary driver of optimization performance, likely due to its superior ability to construct an accurate surrogate model. However, the study demonstrates that employing stage-dependent encodings—specifically combining one-hot for learning with domain-wall for search—can provide further improvements, particularly in scenarios with larger input dimensions and finer discretization where the search space is more complex.

The authors conclude that while the OhDw method shows promise, its generality requires further validation on a wider variety of benchmark functions and real-world design optimization problems. Additionally, systematic analysis of sensitivity to penalty coefficients and QUBO density differences remains a direction for future work.