Details
| Original language | English |
|---|---|
| Title of host publication | Proceedings of The 12th Asian Conference on Machine Learning |
| Pages | 737-752 |
| Number of pages | 16 |
| Volume | 129 |
| Publication status | Published - 2020 |
| Externally published | Yes |
| Event | 12th Asian Conference on Machine Learning, ACML 2020 - Bangkok, Thailand Duration: 18 Nov 2020 → 20 Nov 2020 |
Publication series
| Name | Proceedings of Machine Learning Research |
|---|
Abstract
Algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem class, where “suitability” often refers to an algorithm's runtime. Due to possibly extremely long runtimes of candidate algorithms, training data for algorithm selection models is usually generated under time constraints in the sense that not all algorithms are run to completion on all instances. Thus, training data usually comprises censored information, as the true runtime of algorithms timed out remains unknown. However, many standard AS approaches are not able to handle such information in a proper way. On the other side, survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime, as we demonstrate in this work. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. Moreover, taking advantage of a framework of this kind, we advocate a risk-averse approach to algorithm selection, in which the avoidance of a timeout is given high priority. 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.
Keywords
- algorithm selection, risk-aversion, surrogate loss, survival analysis
ASJC Scopus subject areas
- Computer Science(all)
- Artificial Intelligence
- Computer Science(all)
- Software
- Engineering(all)
- Control and Systems Engineering
- Mathematics(all)
- Statistics and Probability
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Proceedings of The 12th Asian Conference on Machine Learning. Vol. 129 2020. p. 737-752 (Proceedings of Machine Learning Research).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Run2Survive
T2 - 12th Asian Conference on Machine Learning, ACML 2020
AU - Tornede, Alexander
AU - Wever, Marcel
AU - Werner, Stefan
AU - Mohr, Felix
AU - Hüllermeier, Eyke
N1 - Publisher Copyright: © 2020 A. Tornede, M. Wever, S. Werner, F. Mohr & E. Hüllermeier.
PY - 2020
Y1 - 2020
N2 - Algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem class, where “suitability” often refers to an algorithm's runtime. Due to possibly extremely long runtimes of candidate algorithms, training data for algorithm selection models is usually generated under time constraints in the sense that not all algorithms are run to completion on all instances. Thus, training data usually comprises censored information, as the true runtime of algorithms timed out remains unknown. However, many standard AS approaches are not able to handle such information in a proper way. On the other side, survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime, as we demonstrate in this work. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. Moreover, taking advantage of a framework of this kind, we advocate a risk-averse approach to algorithm selection, in which the avoidance of a timeout is given high priority. 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.
AB - Algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem class, where “suitability” often refers to an algorithm's runtime. Due to possibly extremely long runtimes of candidate algorithms, training data for algorithm selection models is usually generated under time constraints in the sense that not all algorithms are run to completion on all instances. Thus, training data usually comprises censored information, as the true runtime of algorithms timed out remains unknown. However, many standard AS approaches are not able to handle such information in a proper way. On the other side, survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime, as we demonstrate in this work. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. Moreover, taking advantage of a framework of this kind, we advocate a risk-averse approach to algorithm selection, in which the avoidance of a timeout is given high priority. 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.
KW - algorithm selection
KW - risk-aversion
KW - surrogate loss
KW - survival analysis
UR - http://www.scopus.com/inward/record.url?scp=85159966225&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85159966225
VL - 129
T3 - Proceedings of Machine Learning Research
SP - 737
EP - 752
BT - Proceedings of The 12th Asian Conference on Machine Learning
Y2 - 18 November 2020 through 20 November 2020
ER -