# Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2019.

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

- [Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond](https://mlsanity.com/paper/2106.04033/) (2021)
- [A Survey of Methods for Automated Algorithm Configuration](https://mlsanity.com/paper/2202.01651/) (2022)
- [Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cuts](https://mlsanity.com/paper/2204.07312/) (2022)
- [AC-Band: A Combinatorial Bandit-Based Approach to Algorithm Configuration](https://mlsanity.com/paper/2212.00333/) (2022)
- [Formalizing Preferences Over Runtime Distributions](https://mlsanity.com/paper/2205.13028/) (2022)
- [Utilitarian Algorithm Configuration for Infinite Parameter Spaces](https://mlsanity.com/paper/2405.18246/) (2024)
- [Utilitarian Algorithm Configuration](https://mlsanity.com/paper/2310.20401/) (2023)
- [Practical, Utilitarian Algorithm Configuration](https://mlsanity.com/paper/2510.14683/) (2025)
- [Distribution-Aware Algorithm Design with LLM Agents](https://mlsanity.com/paper/2605.14141/) (2026)

## Abstract (arXiv)

Algorithm configuration methods optimize the performance of a parameterized heuristic algorithm on a given distribution of problem instances. Recent work introduced an algorithm configuration procedure ("Structured Procrastination") that provably achieves near optimal performance with high probability and with nearly minimal runtime in the worst case. It also offers an textitanytime property: it keeps tightening its optimality guarantees the longer it is run. Unfortunately, Structured Procrastination is not textitadaptive to characteristics of the parameterized algorithm: it treats every input like the worst case. Follow-up work ("LeapsAndBounds") achieves adaptivity but trades away the anytime property. This paper introduces a new algorithm, "Structured Procrastination with Confidence", that preserves the near-optimality and anytime properties of Structured Procrastination while adding adaptivity. In particular, the new algorithm will perform dramatically faster in settings where many algorithm configurations perform poorly. We show empirically both that such settings arise frequently in practice and that the anytime property is useful for finding good configurations quickly.