Introduction
Optimizing "black-box" functions—where the underlying objective is unknown and evaluations are expensive—is a cornerstone of modern scientific discovery, from drug design to materials science. A significant challenge arises when inputs are categorical variables (e.g., RNA bases: A, C, G, U) that lack a natural ordering. Unlike continuous domains, categorical spaces do not allow for gradient-based methods or simple local searches like "moving a little to the left."
Traditional approaches such as Simulated Annealing (SA) or Monte Carlo Tree Search (MCTS) often require a prohibitive number of evaluations to find optima. This paper addresses these inefficiencies by introducing surrogate models based on group-theoretic Fourier expansions, offering a path to high sample efficiency and dramatic computational speedups.
Methodology
The core innovation lies in using Fourier representations as surrogate models. These models provide a computationally inexpensive approximation of the expensive black-box function, allowing an optimizer to evaluate millions of virtual candidates before selecting the most promising ones for real-world testing.
Representation Techniques
- Abridged One-Hot Encoded Boolean Fourier: A simplified one-hot encoding that reduces variable count while remaining mathematically "complete and unique," ensuring it can represent any categorical function.
- Group-Theoretic Fourier Expansion: This treats categorical variables as elements of a finite Abelian group, utilizing complex exponentials to model intricate interactions between variables.
Optimization Frameworks
- ECO (Expert-Based Categorical Optimization): An adversarial online learning approach that treats Fourier components as "experts." It uses an exponential weight rule for rapid updates, making it exceptionally fast.
- TCO (Thompson-sampling based Categorical Optimization): A Bayesian approach utilizing a "sparse horseshoe prior" to balance exploration and exploitation. While more computationally intensive, it excels at handling uncertainty.
Experimental Evaluation
The proposed methods were evaluated across synthetic and real-world benchmarks, including the Latin Square problem, high-dimensional Pest Control, and RNA sequence optimization. Specifically, the researchers targeted RNA Design (inverse folding) using puzzles from the Eterna-100 dataset, comparing against specialized tools like LEARNA and MCTS-RNA.
Key Results
Computational Efficiency
The Fourier-based ECO algorithms demonstrated a massive reduction in overhead. As shown in the table below, ECO-F and ECO-G achieved up to a 100x speedup in computation time per step compared to COMBO, a leading Bayesian combinatorial optimizer.
Optimization Performance
In the Eterna-100 RNA design tasks, the Fourier-based methods significantly outperformed state-of-the-art baselines. By leveraging the inherent sparsity of biological functions—where low-order interactions often dominate—the models captured the essential "physics" of the problem more effectively than general-purpose search algorithms.
Furthermore, the TCO-F method exhibited remarkable sample efficiency, outperforming competitors like AdaLead using only 20% of the evaluation budget (100 samples vs. 500).
Conclusion and Future Work
By bridging the gap between search and learning, Fourier-based surrogate models provide a powerful new tool for combinatorial optimization. While the Bayesian TCO approach faces scaling challenges for very long sequences (e.g., RNA puzzles of length >180), the ECO framework offers a high-speed alternative. Future research will explore higher-order interactions and ensemble methods that combine Boolean and Group-theoretic representations to further enhance robustness across diverse categorical domains.
Summary updated