Generalization in portfolio-based algorithm selection
- URL: http://arxiv.org/abs/2012.13315v1
- Date: Thu, 24 Dec 2020 16:33:17 GMT
- Title: Generalization in portfolio-based algorithm selection
- Authors: Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik
- Abstract summary: We provide the first provable guarantees for portfolio-based algorithm selection.
We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
- Score: 97.74604695303285
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Portfolio-based algorithm selection has seen tremendous practical success
over the past two decades. This algorithm configuration procedure works by
first selecting a portfolio of diverse algorithm parameter settings, and then,
on a given problem instance, using an algorithm selector to choose a parameter
setting from the portfolio with strong predicted performance. Oftentimes, both
the portfolio and the algorithm selector are chosen using a training set of
typical problem instances from the application domain at hand. In this paper,
we provide the first provable guarantees for portfolio-based algorithm
selection. We analyze how large the training set should be to ensure that the
resulting algorithm selector's average performance over the training set is
close to its future (expected) performance. This involves analyzing three key
reasons why these two quantities may diverge: 1) the learning-theoretic
complexity of the algorithm selector, 2) the size of the portfolio, and 3) the
learning-theoretic complexity of the algorithm's performance as a function of
its parameters. We introduce an end-to-end learning-theoretic analysis of the
portfolio construction and algorithm selection together. We prove that if the
portfolio is large, overfitting is inevitable, even with an extremely simple
algorithm selector. With experiments, we illustrate a tradeoff exposed by our
theoretical analysis: as we increase the portfolio size, we can hope to include
a well-suited parameter setting for every possible problem instance, but it
becomes impossible to avoid overfitting.
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) - A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
Subset selection is a fundamental problem that can play a key role in identifying smaller portions of the training data.
We develop a novel factor 3-approximation algorithm to compute subsets based on the weighted sum of both k-center and uncertainty sampling objective functions.
arXiv Detail & Related papers (2023-12-17T04:41:07Z) - PS-AAS: Portfolio Selection for Automated Algorithm Selection in
Black-Box Optimization [4.842307002343618]
The performance of automated algorithm selection depends on the portfolio of algorithms to choose from.
In practice, probably the most common way to choose the algorithms for the portfolio is a greedy selection of the algorithms that perform well in some reference tasks of interest.
Our proposed method creates algorithm behavior meta-representations, constructs a graph from a set of algorithms based on their meta-representation similarity, and applies a graph algorithm to select a final portfolio of diverse, representative, and non-redundant algorithms.
arXiv Detail & Related papers (2023-10-14T12:13:41Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity.
We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level.
Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
arXiv Detail & Related papers (2023-04-12T14:51:47Z) - 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) - Leveraging Benchmarking Data for Informed One-Shot Dynamic Algorithm
Selection [0.9281671380673306]
A key challenge in the application of evolutionary algorithms is the selection of an algorithm instance that best suits the problem at hand.
We analyze in this work how such prior performance data can be used to infer informed dynamic algorithm selection schemes for the solution of pseudo-Boolean optimization problems.
arXiv Detail & Related papers (2021-02-12T12:27:02Z) - 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)
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.