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

Robert Kleinberg, Kevin Leyton-Brown, Brendan Lucier, Devon R. Graham

Introduction

Algorithm Configuration (AC) is a critical challenge in deploying complex solvers for SAT or Mixed Integer Programming (MIP). These solvers often feature numerous parameters that significantly impact performance. Finding the optimal configuration is computationally expensive, as it requires evaluating candidates across many problem instances. Existing theoretical approaches typically force a trade-off between being anytime (improving over time without a fixed budget) and adaptive (quickly discarding poor configurations).

The SPC Algorithm

Structured Procrastination with Confidence (SPC) bridges this gap. It is an anytime algorithm that maintains adaptivity by using a "thread pool" of configuration testers managed by a central scheduler.

Key Components

  1. Optimistic Scheduling: The scheduler selects configurations based on their Lower Confidence Bound (LCB) of average runtime, following the "optimism in the face of uncertainty" principle.
  2. Procrastination with Captimes: SPC uses a doubling timeout (captime) strategy. If a run exceeds the current captime, it is queued for later with a larger budget, preventing the algorithm from getting stuck on hard instances.
  3. Confidence via Empirical CDFs: The core innovation is the use of a sophisticated LCB derived from a modified empirical Cumulative Distribution Function (CDF). This allows SPC to mathematically prune configurations that are likely inferior even before their exact mean runtime is determined.

Empirical Evaluation

The authors evaluated SPC on benchmark SAT solver runtimes (minisat on CNFuzzDD instances) and public solver data for SPEAR and CPLEX across various problem distributions.

Performance Results

  • Efficiency: In minisat experiments, SPC identified a top 1% configuration within 10 CPU days. In contrast, the non-anytime LeapsAndBounds required over 100 CPU days to provide any result for the same problem.
  • Adaptivity: Real-world data often contains a few configurations that are orders of magnitude faster than others. SPC's LCB-based filtering allows it to focus resources on these high-performers early on.
  • Theoretical Optimality: The algorithm's runtime matches the performance of an optimal verification procedure (up to logarithmic factors), providing strong theoretical foundations for its empirical success.

Discussion and Future Work

SPC offers a "plug-and-play" experience for researchers, allowing them to run configuration tasks until resources are exhausted without pre-specifying error tolerances. While highly effective, future work remains in handling "non-resuming" environments where restarts are costly and scaling to massive, high-dimensional configuration spaces. The current model assumes a non-resuming environment, which is a key area for future investigation.

Summary updated

BibTeX
@inproceedings{kleinberg2019procrastinating,
  author = {Robert Kleinberg and Kevin Leyton-Brown and Brendan Lucier and Devon R. Graham},
  title = {{Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=JclfLHF8yss},
}
Figure