Fourier Representations for Black-Box Optimization over Categorical Variables

Hamid Dadkhahi, Jesus Rios, Karthikeyan Shanmugam, Payel Das

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:

  1. 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.
  2. 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 RNAfold simulator.
  • 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.

Table 1: Computational time per step (seconds). ECO methods demonstrate up to a 100x speedup over the COMBO baseline.

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.

Figure 1: Performance comparison on the Eterna-100 RNA design task (Puzzle #70). ECO-F significantly outperforms reinforcement learning and search baselines.

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

Abstract

Optimization of real-world black-box functions defined over purely categorical variables is an active area of research. In particular, optimization and design of biological sequences with specific functional or structural properties have a profound impact in medicine, materials science, and biotechnology. Standalone search algorithms, such as simulated annealing (SA) and Monte Carlo tree search (MCTS), are typically used for such optimization problems. In order to improve the performance and sample efficiency of such algorithms, we propose to use existing methods in conjunction with a surrogate model for the black-box evaluations over purely categorical variables. To this end, we present two different representations, a group-theoretic Fourier expansion and an abridged one-hot encoded Boolean Fourier expansion. To learn such representations, we consider two different settings to update our surrogate model. First, we utilize an adversarial online regression setting where Fourier characters of each representation are considered as experts and their respective coefficients are updated via an exponential weight update rule each time the black box is evaluated. Second, we consider a Bayesian setting where queries are selected via Thompson sampling and the posterior is updated via a sparse Bayesian regression model (over our proposed representation) with a regularized horseshoe prior. Numerical experiments over synthetic benchmarks as well as real-world RNA sequence optimization and design problems demonstrate the representational power of the proposed methods, which achieve competitive or superior performance compared to state-of-the-art counterparts, while improving the computation cost and/or sample efficiency, substantially.
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