Machine Learning for Online Algorithm Selection under Censored Feedback
- URL: http://arxiv.org/abs/2109.06234v1
- Date: Mon, 13 Sep 2021 18:10:52 GMT
- Title: Machine Learning for Online Algorithm Selection under Censored Feedback
- Authors: Alexander Tornede and Viktor Bengs and Eyke H\"ullermeier
- Abstract summary: 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.
- Score: 71.6879432974126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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. As the latter is known to exhibit a heavy-tail
distribution, an algorithm is normally stopped when exceeding a predefined
upper time limit. As a consequence, machine learning methods used to optimize
an algorithm selection strategy in a data-driven manner need to deal with
right-censored samples, a problem that has received little attention in the
literature so far. In this work, we revisit multi-armed bandit algorithms for
OAS and discuss their capability of dealing with the problem. Moreover, we
adapt them towards runtime-oriented losses, allowing for partially censored
data while keeping a space- and time-complexity independent of the time
horizon. In an extensive experimental evaluation on an adapted version of the
ASlib benchmark, we demonstrate that theoretically well-founded methods based
on Thompson sampling perform specifically strong and improve in comparison to
existing methods.
Related papers
- Frugal Algorithm Selection [1.079960007119637]
There is no single algorithm that works well for all instances of a problem.
In this work, we explore reducing this cost by choosing a subset of the training instances on which to train.
We approach this problem in three ways: using active learning to decide based on prediction uncertainty, augmenting the algorithm predictors with a timeout predictor, and collecting training data using a progressively increasing timeout.
arXiv Detail & Related papers (2024-05-17T19:23:30Z) - Scalable and Decentralized Algorithms for Anomaly Detection via
Learning-Based Controlled Sensing [40.14838268469627]
We develop an anomaly detection algorithm that chooses the processes to be observed at a given time instant.
The objective of the detection algorithm is to identify the anomalies with an accuracy exceeding the desired value.
arXiv Detail & Related papers (2021-12-08T11:20:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models.
The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning.
We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z) - Towards Meta-Algorithm Selection [78.13985819417974]
Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates.
We show that meta-algorithm-selection can indeed prove beneficial in some cases.
arXiv Detail & Related papers (2020-11-17T17:27:33Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model.
The advantages of state-of-the-art algorithms are discussed and illustrated.
arXiv Detail & Related papers (2020-09-28T15:22:24Z) - 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.