On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting

• URL: http://arxiv.org/abs/2405.10976v1
• Date: Mon, 13 May 2024 03:31:13 GMT
• Title: On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting
• Authors: Takushi Yoshikawa, Ryoji Tanabe,
• Abstract summary: This paper argues the importance of considering the number of function evaluations used in the sampling phase when constructing algorithm portfolios. The results show that algorithm portfolios constructed by our approach perform significantly better than those by the previous approach.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Feature-based offline algorithm selection has shown its effectiveness in a wide range of optimization problems, including the black-box optimization problem. An algorithm selection system selects the most promising optimizer from an algorithm portfolio, which is a set of pre-defined optimizers. Thus, algorithm selection requires a well-constructed algorithm portfolio consisting of efficient optimizers complementary to each other. Although construction methods for the fixed-target setting have been well studied, those for the fixed-budget setting have received less attention. Here, the fixed-budget setting is generally used for computationally expensive optimization, where a budget of function evaluations is small. In this context, first, this paper points out some undesirable properties of experimental setups in previous studies. Then, this paper argues the importance of considering the number of function evaluations used in the sampling phase when constructing algorithm portfolios, whereas the previous studies ignored that. The results show that algorithm portfolios constructed by our approach perform significantly better than those by the previous approach.

Related papers

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  offline preference optimization is a key method for enhancing and controlling the quality of Large Language Model (LLM) outputs. We perform objective discovery to automatically discover new state-of-the-art preference optimization algorithms without (expert) human intervention. Experiments demonstrate the state-of-the-art performance of DiscoPOP, a novel algorithm that adaptively blends logistic and exponential losses.
  arXiv  Detail & Related papers  (2024-06-12T16:58:41Z)
• A Survey of Meta-features Used for Automated Selection of Algorithms for Black-box Single-objective Continuous Optimization [4.173197621837912]
  We conduct an overview of the key contributions to algorithm selection in the field of single-objective continuous black-box optimization. We study machine learning models for automated algorithm selection, configuration, and performance prediction.
  arXiv  Detail & Related papers  (2024-06-08T11:11:14Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• 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)
• Trajectory-based Algorithm Selection with Warm-starting [2.3823600586675724]
  We study the quality and accuracy of performance regression and algorithm selection models in the scenario of predicting different algorithm performances. We show promising performance of the trajectory-based per-run algorithm selection with warm-starting.
  arXiv  Detail & Related papers  (2022-04-13T14:00:55Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization [0.0]
  Feature-based algorithm selection aims to automatically find the best one from a portfolio of optimization algorithms on an unseen problem. This paper analyzes algorithm selection systems on the 24 noiseless black-box optimization benchmarking functions. We show that the performance of algorithm selection systems can be significantly improved by using sequential least squares programming as a pre-solver.
  arXiv  Detail & Related papers  (2021-09-17T07:17:40Z)
• 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)
• Towards Feature-Based Performance Regression Using Trajectory Data [0.9281671380673306]
  Black-box optimization is a very active area of research, with many new algorithms being developed every year. The variety of algorithms poses a meta-problem: which algorithm to choose for a given problem at hand? Past research has shown that per-instance algorithm selection based on exploratory landscape analysis can be an efficient mean to tackle this meta-problem.
  arXiv  Detail & Related papers  (2021-02-10T10:19:13Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.