Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization

• URL: http://arxiv.org/abs/2109.08377v4
• Date: Tue, 26 Apr 2022 08:16:27 GMT
• Title: Benchmarking Feature-based Algorithm Selection Systems for Black-box Numerical Optimization
• Authors: Ryoji Tanabe
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Feature-based algorithm selection aims to automatically find the best one from a portfolio of optimization algorithms on an unseen problem based on its landscape features. Feature-based algorithm selection has recently received attention in the research field of black-box numerical optimization. However, there is still room for analysis of algorithm selection for black-box optimization. Most previous studies have focused only on whether an algorithm selection system can outperform the single-best solver in a portfolio. In addition, a benchmarking methodology for algorithm selection systems has not been well investigated in the literature. In this context, this paper analyzes algorithm selection systems on the 24 noiseless black-box optimization benchmarking functions. First, we demonstrate that the first successful performance measure is more reliable than the expected runtime measure for benchmarking algorithm selection systems. Then, we examine the influence of randomness on the performance of algorithm selection systems. We also show that the performance of algorithm selection systems can be significantly improved by using sequential least squares programming as a pre-solver. We point out that the difficulty of outperforming the single-best solver depends on algorithm portfolios, cross-validation methods, and dimensions. Finally, we demonstrate that the effectiveness of algorithm portfolios depends on various factors. These findings provide fundamental insights for algorithm selection for black-box optimization.

Related papers

• 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)
• On Constructing Algorithm Portfolios in Algorithm Selection for Computationally Expensive Black-box Optimization in the Fixed-budget Setting [0.0]
  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.
  arXiv  Detail & Related papers  (2024-05-13T03:31:13Z)
• 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)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors. We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
  arXiv  Detail & Related papers  (2021-07-20T11:23:21Z)
• 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)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
  arXiv  Detail & Related papers  (2020-07-06T15:20:17Z)
• 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)
• 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.