# Formalizing Preferences Over Runtime Distributions

arXiv: https://arxiv.org/abs/2205.13028 · HTML: https://mlsanity.com/paper/2205.13028/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 55 references that are in the map.
- First posted on arXiv 25 May 2022.

## Builds on (most cited first, 8 of 8)

- [ParamILS: An Automatic Algorithm Configuration Framework](https://mlsanity.com/paper/1401.3492/) (2014)
- [A PAC Approach to Application-Specific Algorithm Selection](https://mlsanity.com/paper/1511.07147/) (2015)
- [Learning-Theoretic Foundations of Algorithm Configuration for Combinatorial Partitioning Problems](https://mlsanity.com/paper/1611.04535/) (2016)
- [How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design](https://mlsanity.com/paper/1908.02894/) (2019)
- [LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration](https://mlsanity.com/paper/1807.00755/) (2018)
- [Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration](https://mlsanity.com/paper/1902.05454/) (2019)
- [Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis](https://mlsanity.com/paper/2007.02816/) (2020)
- [A Bayesian Approach to Tackling Hard Computational Problems](https://mlsanity.com/paper/1301.2279/) (2013)

## Built on by (most cited first, 2 of 2)

- [Utilitarian Algorithm Configuration for Infinite Parameter Spaces](https://mlsanity.com/paper/2405.18246/) (2024)
- [Utilitarian Algorithm Configuration](https://mlsanity.com/paper/2310.20401/) (2023)

## Abstract (arXiv)

When trying to solve a computational problem, we are often faced with a choice between algorithms that are guaranteed to return the right answer but differ in their runtime distributions (e.g., SAT solvers, sorting algorithms). This paper aims to lay theoretical foundations for such choices by formalizing preferences over runtime distributions. It might seem that we should simply prefer the algorithm that minimizes expected runtime. However, such preferences would be driven by exactly how slow our algorithm is on bad inputs, whereas in practice we are typically willing to cut off occasional, sufficiently long runs before they finish. We propose a principled alternative, taking a utility-theoretic approach to characterize the scoring functions that describe preferences over algorithms. These functions depend on the way our value for solving our problem decreases with time and on the distribution from which captimes are drawn. We describe examples of realistic utility functions and show how to leverage a maximum-entropy approach for modeling underspecified captime distributions. Finally, we show how to efficiently estimate an algorithm's expected utility from runtime samples.