Efficiency Through Procrastination: Approximately Optimal Algorithm Configuration with Runtime Guarantees

Algorithm configuration methods have achieved much practical success, but to date have not been backed by meaningful performance guarantees. We address this gap with a new algorithm configuration framework, Structured Procrastination. With high probability and nearly as quickly as possible in the worst case, our framework finds an algorithm configuration that provably achieves near optimal performance. Moreover, its running time requirements asymptotically dominate those of existing methods.

Authors

• Robert Kleinberg Cornell University
• Kevin Leyton-Brown University of British Columbia
• Brendan Lucier Microsoft Research

Keywords

• Constraints and Satisfiability: Constraints and Satisfiability
• Constraints and Satisfiability: Evaluation and Analysis
• Constraints and Satisfiability: Solvers and Tools
• Machine Learning: Learning Theory