Fourier Representations for Black-Box Optimization over Categorical Variables

Hamid Dadkhahi, Jesus Rios, Karthikeyan Shanmugam, Payel Das

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

  1. 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.
  2. 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.

Table 1: Computation time per step (seconds) across different benchmarks.

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.

Figure 1: Optimization curves for RNA design (Puzzle #15), showing the superior sample efficiency of ECO and TCO variants compared to LEARNA and MCTS.

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

BibTeX
@inproceedings{dadkhahi2022fourier,
  author = {Hamid Dadkhahi and Jesus Rios and Karthikeyan Shanmugam and Payel Das},
  title = {{Fourier Representations for Black-Box Optimization over Categorical Variables}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21255},
}
Figure