Fourier Representations for Black-Box Optimization over Categorical Variables

• URL: http://arxiv.org/abs/2202.03712v1
• Date: Tue, 8 Feb 2022 08:14:58 GMT
• Title: Fourier Representations for Black-Box Optimization over Categorical Variables
• Authors: Hamid Dadkhahi, Jesus Rios, Karthikeyan Shanmugam, Payel Das
• Abstract summary: We propose to use existing methods in conjunction with a surrogate model for the black-box evaluations over purely categorical variables. To learn such representations, we consider two different settings to update our surrogate model. Numerical experiments over synthetic benchmarks as well as real-world RNA sequence optimization and design problems demonstrate the representational power of the proposed methods.
• Score: 34.0277529502051
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• BI-EqNO: Generalized Approximate Bayesian Inference with an Equivariant Neural Operator Framework [9.408644291433752]
  We introduce BI-EqNO, an equivariant neural operator framework for generalized approximate Bayesian inference. BI-EqNO transforms priors into posteriors on conditioned observation data through data-driven training. We demonstrate BI-EqNO's utility through two examples: (1) as a generalized Gaussian process (gGP) for regression, and (2) as an ensemble neural filter (EnNF) for sequential data assimilation.
  arXiv  Detail & Related papers  (2024-10-21T18:39:16Z)
• A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences [12.248793682283964]
  optimizing discrete black-box functions is key in several domains, e.g. protein engineering and drug design. We develop a unified framework to test a vast array of high-dimensional Bayesian optimization methods and a collection of standardized black-box functions. These two components of the benchmark are each supported by flexible, scalable, and easily extendable software libraries.
  arXiv  Detail & Related papers  (2024-06-07T08:39:40Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO) Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
  arXiv  Detail & Related papers  (2024-02-05T02:54:50Z)
• Simulation Based Bayesian Optimization [0.6526824510982799]
  This paper introduces Simulation Based Bayesian Optimization (SBBO) as a novel approach to optimizing acquisition functions. SBBO allows the use of surrogate models tailored for spaces with discrete variables. We demonstrate empirically the effectiveness of SBBO method using various choices of surrogate models.
  arXiv  Detail & Related papers  (2024-01-19T16:56:11Z)
• Performance Embeddings: A Similarity-based Approach to Automatic Performance Optimization [71.69092462147292]
  Performance embeddings enable knowledge transfer of performance tuning between applications. We demonstrate this transfer tuning approach on case studies in deep neural networks, dense and sparse linear algebra compositions, and numerical weather prediction stencils.
  arXiv  Detail & Related papers  (2023-03-14T15:51:35Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Surrogate modeling for Bayesian optimization beyond a single Gaussian process [62.294228304646516]
  We propose a novel Bayesian surrogate model to balance exploration with exploitation of the search space. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret.
  arXiv  Detail & Related papers  (2022-05-27T16:43:10Z)
• Bayesian Optimization over Permutation Spaces [30.650753803587794]
  We propose and evaluate two algorithms for BO over Permutation Spaces (BOPS) We theoretically analyze the performance of BOPS-T to show that their regret grows sub-linearly. Our experiments on multiple synthetic and real-world benchmarks show that both BOPS-T and BOPS-H perform better than the state-of-the-art BO algorithm for spaces.
  arXiv  Detail & Related papers  (2021-12-02T08:20:50Z)
• Trusted-Maximizers Entropy Search for Efficient Bayesian Optimization [39.824086260578646]
  This paper presents a novel trusted-maximizers entropy search (TES) acquisition function. It measures how much an input contributes to the information gain on a query over a finite set of trusted maximizers.
  arXiv  Detail & Related papers  (2021-07-30T07:25:07Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.