How much data is sufficient to learn high-performing algorithms? generalization guarantees for data-driven algorithm design

Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case guarantee. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that data-driven algorithm design can lead to significant improvements in performance. This approach uses a training set of problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set.

Authors

• Maria-Florina Balcan
• Dan F. DeBlasio
• Travis Dick
• Carl Kingsford
• Tuomas Sandholm
• Ellen Vitercik

Keywords

• Automated algorithm design
• automated algorithm configuration
• computational biology
• data-driven algorithm design
• machine learning theory
• mechanism design