Introduction
Black-box optimization (BBO) is a critical tool for scenarios where objective functions are analytically inaccessible and computationally or physically expensive to evaluate. While BBO techniques for continuous and integer domains are well-established, optimizing over categorical variables remains a significant challenge. Categorical variables, such as nucleotides in an RNA sequence (A, C, G, U), lack a natural numerical ordering or distance metric, rendering standard gradient-based or distance-based surrogate models ineffective.
Traditional approaches often rely on search heuristics like Simulated Annealing (SA) or Monte Carlo Tree Search (MCTS). However, these methods typically require a high volume of function evaluations to converge. This paper introduces a novel framework that utilizes Fourier-based representations to build highly efficient surrogate models for categorical data, enabling state-of-the-art sample efficiency and significant computational speedups.
Fourier-Based Representations
The core innovation of this work lies in the mathematical representation of categorical choices. The authors propose two distinct Fourier-based approaches to map categorical variables into a space suitable for surrogate modeling:
- Abridged One-Hot Encoded Boolean Fourier Representation: Standard one-hot encoding for a variable with $k$ categories is often redundant. The authors introduce a reduced $(k-1)$ Boolean representation. They prove this form is both mathematically complete and unique, significantly reducing the number of interaction terms the surrogate model must learn, thereby improving tractability in high-dimensional spaces.
- Fourier Representation on Finite Abelian Groups: This approach leverages group theory, specifically cyclic groups, to represent categorical selections as complex exponentials. This provides an elegant mathematical foundation for capturing complex interactions between unordered variables without imposing an artificial hierarchy.
Optimization Frameworks: ECO and TCO
To leverage these representations, the authors developed two learning frameworks that wrap around traditional search algorithms like SA and MCTS:
- Expert-Based Categorical Optimization (ECO): An online regression method that treats individual Fourier terms as "experts." It utilizes a fast exponential update rule to adjust weights as new data arrives, prioritizing computational speed.
- TS-based Categorical Optimization (TCO): A Bayesian framework employing a regularized horseshoe prior and a No-U-Turn Sampler (NUTS). This approach enables Thompson Sampling, providing a more robust mechanism for balancing exploration and exploitation, albeit at a higher computational cost than ECO.
Experimental Evaluation
The proposed methods were evaluated against a variety of benchmarks, ranging from synthetic problems to complex biological design tasks:
- Synthetic Benchmarks: Latin Square ($n=25, k=5$) and Pest Control problems.
- RNA Sequence Optimization: Minimizing the Free Energy (MFE) of a 30-nucleotide sequence using the
RNAfoldsimulator. - RNA Inverse Folding: Solving puzzles from the Eterna-100 dataset (e.g., puzzles #15, #41, and #70), where the goal is to design a sequence that folds into a specific target structure.
Results and Discussion
The experimental results demonstrate that Fourier-based surrogates significantly outperform existing combinatorial Bayesian optimization (CBO) and reinforcement learning baselines.
Computational Efficiency
A standout result is the dramatic reduction in computational overhead. The online ECO methods (ECO-F and ECO-G) achieved a 50x to 100x speedup per optimization step compared to COMBO, a leading CBO baseline. This efficiency makes surrogate-assisted search viable for real-time or large-scale applications.
Sample Efficiency and RNA Design
In the RNA design tasks, the Fourier-based models exhibited superior sample efficiency. On the Eterna-100 puzzles, ECO-F paired with MCTS substantially outperformed state-of-the-art reinforcement learning (LEARNA) and standard MCTS-RNA within a limited budget of 500 evaluations. While the Bayesian TCO-F method is slower, it often achieved the best final results in longer runs due to its superior exploration capabilities.
Conclusion
By introducing abridged and group-theoretic Fourier representations, this paper provides a powerful new toolkit for categorical black-box optimization. These representations allow surrogate models to "hallucinate" thousands of evaluations, focusing expensive real-world queries only on the most promising candidates. Future work may involve ensemble models that dynamically select between ECO and TCO frameworks to leverage their respective strengths in speed and exploration across diverse problem landscapes.
Summary updated