Stage-dependent integer-binary encoding in factorization-machine black-box optimization
Authors: Ryo Ogawa, Mayumi Nakano, Yuya Seki, Shu Tanaka
Organizations: Graduate School of Science and Technology, Keio University, Kanagawa 223-8522, Japan · Keio University Sustainable Quantum Artificial Intelligence Center (KSQAIC), Keio University, Tokyo 108-8345, Japan · Department of Applied Physics and Physico-Informatics, Keio University, Kanagawa 223-8522, Japan · Human Biology-Microbiome-Quantum Research Center (WPI-Bio2Q), Keio University, Tokyo 108-8345, Japan · Green Computing System Research Organization, Waseda University, Shinjuku-ku, Tokyo 162-0042, Japan
Abstract
Black-box optimization (BBO) deals with problems where objective functions lack explicit analytical forms and are expensive to evaluate. Factorization machine with quadratic-optimization annealing (FMQA) constructs a surrogate model using a factorization machine (FM) and optimizes it with an Ising machine. Conventional FMQA applies a single integer-binary encoding throughout the optimization process, although the encoding best suited to surrogate learning may differ from the one best suited to Ising-machine solution search. We propose a stage-dependent FMQA framework and derive conversion formulas between one-hot and domain-wall QUBO matrices that preserve the surrogate objective over feasible integer states up to an additive constant. We evaluate the OhDw variant, which employs one-hot encoding for learning and domain-wall encoding for search, on the Rastrigin function with input dimensions N = 2 and 5 and discretization levels q = 61 and 301. Across all conditions, the dominant factor governing optimization performance is the encoding used in the learning stage, with one-hot encoding consistently yielding lower residual errors than domain-wall or binary encoding. The additional benefit of switching to domain-wall encoding for solution search is condition-dependent. For N = 5 and q = 301, OhDw achieves a lower residual error and solutions closer to the global optimum than one-hot-only FMQA, whereas for N = 5 and q = 61 the latter achieves a lower residual error. These results indicate that one-hot encoding in the learning stage is the primary performance driver and that stage-dependent encoding can provide further improvement under finer discretization.
Factorization machine with quadratic-optimization annealing (FMQA) is a black-box optimization method that combines a factorization machine (FM) surrogate with QUBO-based search by an Ising machine. When FMQA is applied to integer or discretized continuous variables via one-hot encoding, uniform random initial sampling can leave many binary variables never active in the initial training data, and the corresponding FM parameters receive no direct gradient updates from the observed responses. We address this by designing the initial training data to achieve complete marginal bit coverage, namely, ensuring that every binary variable obtained by one-hot encoding takes the value one at least once. We use two space-filling sampling methods, Latin hypercube sampling (LHS) and the Sobol' sequence, yielding LHS-FMQA and Sobol'-FMQA. On the human-powered aircraft wing-shape optimization benchmark with 17 and 32 design variables, both proposed methods achieved numerically higher mean final cruising speeds than the baseline FMQA, with the advantage more pronounced on the 32-variable problem.
Protein fitness optimization is a discrete search problem, and the representation used for prediction also determines the neighborhood graph traversed by an optimizer. We introduce Q-BioLat, a framework that maps pretrained protein-language-model embeddings to compact binary codes and fits a quadratic unconstrained binary optimization (QUBO) surrogate with unary and pairwise latent interactions. Our central contribution is an optimization-aware view of representation: binary encodings that are similar in pointwise predictive accuracy can induce different Hamming neighborhoods, local optima, and search trajectories. We formalize when a recoding is only a Hamming-isometric reparameterization and give a constructive example showing that exact pointwise agreement does not imply optimization equivalence. We study experimentally measured GFP and AAV fitness landscapes from ProteinGym. The internal QUBO surrogate is evaluated against labels withheld from QUBO fitting. A conservative retrieval analysis maps optimized codes to measured variants and reports their experimental fitness, while neural decoding of potentially unmeasured sequences is evaluated separately with an experiment-trained sequence surrogate and is interpreted only as model-based candidate prioritization. Across the reported comparisons, PCA followed by per-coordinate median thresholding yields a more balanced and decodable binary space than the post-hoc-zero-threshold AE/VAE baselines, despite the latter's low continuous reconstruction error. In the measured-library retrieval analysis, simulated annealing, genetic algorithms, and greedy hill climbing frequently return high-percentile variants; decoded candidates are reported separately using surrogate-predicted scores.
We introduce a physics-inspired continuous relaxation framework that yields substantially improved solutions for NP-hard combinatorial optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), binary sparse coding, and planted-solution Ising models. By parameterizing discrete binary variables as continuous wave-like states on the complex unit circle, we inherently smooth highly non-convex energy landscapes. We show that representing binary variables as complex phases reveals an implicit regularization mechanism that promotes convergence toward discrete states. Extracting this mechanism yields significant improvements even within standard real-valued optimization frameworks, using this regularizer explicitly. Empirically, this regularization yields vastly higher ground-state convergence rates than standard real-valued alternatives. Our models achieved zero error in large-scale 160x160 QUBO tasks under severe noise (sigma=0.25), and outperformed traditional algorithms (OMP and LASSO) in underdefined sparse coding with perfect recovery at sigma=0.15. The solver's robustness was further validated by recovering exact ground-state configurations in 8 out of 11 rigorously engineered planted-solution benchmarks.