# Fourier Representations for Black-Box Optimization over Categorical Variables

arXiv: https://arxiv.org/abs/2202.03712 · HTML: https://mlsanity.com/paper/2202.03712/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 69 references that are in the map.
- First posted on arXiv 8 Feb 2022.

## Builds on (most cited first, 16 of 16)

- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining](https://mlsanity.com/paper/2006.09191/) (2020)
- [Conditioning by adaptive sampling for robust design](https://mlsanity.com/paper/1901.10060/) (2019)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [AdaLead: A simple and robust adaptive greedy search algorithm for sequence design](https://mlsanity.com/paper/2010.02141/) (2020)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [BOSS: Bayesian Optimization over String Spaces](https://mlsanity.com/paper/2010.00979/) (2020)
- [Autofocused oracles for model-based design](https://mlsanity.com/paper/2006.08052/) (2020)
- [Sparsity information and regularization in the horseshoe and other shrinkage priors](https://mlsanity.com/paper/1707.01694/) (2017)
- [Generating and designing DNA with deep generative models](https://mlsanity.com/paper/1712.06148/) (2017)
- [Learning to Design RNA](https://mlsanity.com/paper/1812.11951/) (2018)
- [Population-Based Black-Box Optimization for Biological Sequence Design](https://mlsanity.com/paper/2006.03227/) (2020)
- [Mercer Features for Efficient Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2012.07762/) (2020)
- [Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework](https://mlsanity.com/paper/2012.07320/) (2020)
- [Combinatorial Black-Box Optimization with Expert Advice](https://mlsanity.com/paper/2006.03963/) (2020)

## Built on by (most cited first, 4 of 4)

- [Biological Sequence Design with GFlowNets](https://mlsanity.com/paper/2203.04115/) (2022)
- [Random Postprocessing for Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2309.02842/) (2023)
- [Simulation Based Bayesian Optimization](https://mlsanity.com/paper/2401.10811/) (2024)
- [Tight L_∞ Sample Complexity for Low-Degree and Sparse Boolean Polynomials](https://mlsanity.com/paper/2606.17319/) (2026)

## Abstract (arXiv)

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.