MA-BBOB: A Problem Generator for Black-Box Optimization Using Affine Combinations and Shifts

• URL: http://arxiv.org/abs/2312.11083v1
• Date: Mon, 18 Dec 2023 10:23:09 GMT
• Title: MA-BBOB: A Problem Generator for Black-Box Optimization Using Affine Combinations and Shifts
• Authors: Diederick Vermetten, Furong Ye, Thomas B\"ack, Carola Doerr
• Abstract summary: We present the MA-BBOB function generator, which uses the BBOB suite as component functions in an affine combination. We show a potential use-case of MA-BBOB in generating a wide set of training and testing data for algorithm selectors.
• Score: 1.2617078020344619
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Choosing a set of benchmark problems is often a key component of any empirical evaluation of iterative optimization heuristics. In continuous, single-objective optimization, several sets of problems have become widespread, including the well-established BBOB suite. While this suite is designed to enable rigorous benchmarking, it is also commonly used for testing methods such as algorithm selection, which the suite was never designed around. We present the MA-BBOB function generator, which uses the BBOB suite as component functions in an affine combination. In this work, we describe the full procedure to create these affine combinations and highlight the trade-offs of several design decisions, specifically the choice to place the optimum uniformly at random in the domain. We then illustrate how this generator can be used to gain more low-level insight into the function landscapes through the use of exploratory landscape analysis. Finally, we show a potential use-case of MA-BBOB in generating a wide set of training and testing data for algorithm selectors. Using this setup, we show that the basic scheme of using a set of landscape features to predict the best algorithm does not lead to optimal results, and that an algorithm selector trained purely on the BBOB functions generalizes poorly to the affine combinations.

Related papers

• Landscape-Aware Automated Algorithm Configuration using Multi-output Mixed Regression and Classification [0.01649298969786889]
  We investigate the potential of randomly generated functions (RGF) for the model training. We focus on automated algorithm configuration (AAC) We analyze the performance of dense neural network (NN) models in handling the mixed regression and classification tasks.
  arXiv  Detail & Related papers  (2024-09-02T20:04:41Z)
• Impact of Training Instance Selection on Automated Algorithm Selection Models for Numerical Black-box Optimization [0.40498500266986387]
  We show that MA-BBOB-generated functions can be an ideal testbed for automated machine learning methods. We analyze the potential gains from AAS by studying performance complementarity within a set of eight algorithms. We show that simply using the BBOB component functions for training yields poor test performance.
  arXiv  Detail & Related papers  (2024-04-11T08:03:53Z)
• MA-BBOB: Many-Affine Combinations of BBOB Functions for Evaluating AutoML Approaches in Noiseless Numerical Black-Box Optimization Contexts [0.8258451067861933]
  (MA-)BBOB is built on the publicly available IOHprofiler platform. It provides access to the interactive IOHanalyzer module for performance analysis and visualization, and enables comparisons with the rich and growing data collection available for the (MA-)BBOB functions.
  arXiv  Detail & Related papers  (2023-06-18T19:32:12Z)
• 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)
• Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
  We show that PrivUnit achieves the optimal variance among a large family of locally private randomizers. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees.
  arXiv  Detail & Related papers  (2022-05-05T06:43:46Z)
• Per-run Algorithm Selection with Warm-starting using Trajectory-based Features [5.073358743426584]
  Per-instance algorithm selection seeks to recommend, for a given problem instance, one or several suitable algorithms. We propose an online algorithm selection scheme which we coin per-run algorithm selection. We show that our approach outperforms static per-instance algorithm selection.
  arXiv  Detail & Related papers  (2022-04-20T14:30:42Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Versatile Black-Box Optimization [6.92253842648213]
  We present Shiwa, an algorithm good at both discrete and continuous, noisy and noise-free, sequential and parallel, black-box optimization. Our algorithm is experimentally compared to competitors on YABBOB, a BBOB comparable testbed, and on some variants of it, and then validated on several real world testbeds.
  arXiv  Detail & Related papers  (2020-04-29T08:20:36Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  We propose a novel Bayesian optimization (BO) algorithm to tackle the challenge of model selection in this setting. In order to solve the resulting multiple black-box function optimization problem jointly and efficiently, we exploit potential correlations among black-box functions. We are the first to formulate the problem of stepwise model selection (SMS) for sequence prediction, and to design and demonstrate an efficient joint-learning algorithm for this purpose.
  arXiv  Detail & Related papers  (2020-01-12T09:42:19Z)

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.