Research map / Learning theory and algorithms / Combinatorial and search optimization
Utilitarian Algorithm Configuration for Infinite Parameter Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces COUP, a utilitarian algorithm configuration procedure that uses optimistic UCB-style bandit search with captime doubling to optimize expected utility over infinite (continuous) configuration spaces, and is also faster than UP on finite sets.
Problem
Utilitarian algorithm configuration (maximizing expected utility of runtime with near-optimality guarantees) previously only worked over small finite configuration sets; continuous or uncountable parameter spaces could not be searched.
Approach
Replace UP's successive-elimination core with a UCB-style optimistic procedure (OUP) that stops running suboptimal configurations rather than eliminating them, and extend it to COUP by sampling a growing set of configurations in phases with anytime gamma and epsilon schedules; also proposes a balanced captime doubling condition.
Key results
- OUP proves a meaningful epsilon in much less time than UP, often by an order of magnitude or more, and is consistently faster than the naive Hoeffding procedure.
- COUP's total configuration time is only a small factor more than OUP applied directly to the same set of configurations, while remaining anytime.
- On percentage-gap experiments, COUP and OUP outperform many runs of the other procedures and eventually identify the optimal configuration for every seed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OUP instead of UP | Utilitarian algorithm configuration on finite configuration sets · minisat, cplex_rcw, and cplex_region | configuration time to prove an ε guarantee | Helped |
| Use OUP instead of the naive Hoeffding procedure | Utilitarian algorithm configuration on finite configuration sets · minisat, cplex_rcw, and cplex_region | configuration time to prove an ε guarantee | Helped |
| Search an expanding configuration space with COUP instead of using OUP on the same configurations | COUP · cplex_rcw, log-Laplace utility | total configuration time | Hurt |
| Replace the original captime-doubling condition with the refined condition (ablation) | OUP and UP · Log-Laplace utility; other utility functions show similar improvement | optimality guarantee and time per configuration | Helped |
| Focus exploration on γ by using ε_p = e^{-p/30} and γ_p = e^{-p/3} (ablation) | COUP · cplex_rcw, log-Laplace utility | configuration-space exploration | Mixed |
| Focus exploration on ε by using ε_p = e^{-p/3} and γ_p = e^{-p/30} (ablation) | COUP · cplex_rcw, log-Laplace utility | optimality guarantee | Mixed |
| Use the balanced schedule ε_p = γ_p = e^{-p/5} (ablation) | COUP · cplex_rcw, log-Laplace utility | exploration of configurations and instances | Mixed |
| Explore configurations first, then tighten ε using ε_p = e^{-p^3/300} and γ_p = e^{-p^2/30} (ablation) | COUP · cplex_rcw, log-Laplace utility | configuration search efficiency | Helped |
| Use COUP or OUP instead of Successive Halving, Hyperband, AC-Band, or ICAR | Utilitarian algorithm configuration · minisat, cplex_rcw, and cplex_region | percentage gap to best configuration | Mixed |
| Use Hyperband instead of COUP | Algorithm configuration on cplex_rcw · cplex_rcw | speed of finding a good configuration | Mixed |
Surprising findings
- OUP backtracks on cplex_region because COUP sampled a relatively good configuration in phase 5, which OUP exploited to prove optimality in less total time than in phase 4.
- A simple naive Hoeffding-based approach can beat UP for small epsilon when its captime parameter is well chosen.
Limitations
- Experiments limited to three existing datasets and two utility functions, as the authors acknowledge.
- Requires a user-specified utility function, which can be hard for end users to choose.
- Assumes restarting runs is not possible in experiments.
Experimental setup
Datasets: minisat cplex_rcw cplex_region
Benchmarks: minisat cplex_rcw cplex_region
Metrics: epsilon-optimality guarantee vs runtime percentage gap to best configuration total configuration time
Baselines: Utilitarian Procrastination (UP) naive Hoeffding-based procedure Successive Halving Hyperband AC-Band ImpatientCapsAndRuns Structured Procrastination with Confidence
Builds on: Utilitarian Procrastination Successive Elimination Upper Confidence Bound Hoeffding's inequality
Closest papers by meaning
- Practical, Utilitarian Algorithm Configuration (AAAI 2026 · similarity 0.94)
- Utilitarian Algorithm Configuration (NeurIPS 2023 · similarity 0.88)
- ImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool (NeurIPS 2020 · similarity 0.86)
- Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees (AAAI 2020 · similarity 0.83)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.81)
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.