Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis
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.
Code (1)
Tasks
Survival AnalysisSimilar Papers 제목 키워드 기반
Personalized Survival Predictions for Cardiac Transplantation via Trees of Predictors
Given the limited pool of donor organs, accurate predictions of survival on the wait list and post transplantation are crucial for cardiac transplantation decisions and policy. However, current clinical risk scores do no…
Decision MakingDiagnosticSpecificitySurvival AnalysisSurvive at All Costs: Exploring LLM's Risky Behaviors under Survival Pressure
As Large Language Models (LLMs) evolve from chatbots to agentic assistants, they are increasingly observed to exhibit risky behaviors when subjected to survival pressure, such as the threat of being shut down. While mult…
Survival Dynamics of Neural and Programmatic Policies in Evolutionary Reinforcement Learning
In evolutionary reinforcement learning tasks (ERL), agent policies are often encoded as small artificial neural networks (NERL). Such representations lack explicit modular structure, limiting behavioral interpretation. W…
Reinforcement LearningORS: A novel Olive Ridley Survival inspired Meta-heuristic Optimization Algorithm
Meta-heuristic algorithmic development has been a thrust area of research since its inception. In this paper, a novel meta-heuristic optimization algorithm, Olive Ridley Survival (ORS), is proposed which is inspired from…
Multi-Modal Mamba Modeling for Survival Prediction (M4Survive): Adapting Joint Foundation Model Representations
Accurate survival prediction in oncology requires integrating diverse imaging modalities to capture the complex interplay of tumor biology. Traditional single-modality approaches often fail to leverage the complementary …
Computational EfficiencyMambaPredictionSurvival Prediction