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

Understand

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 approximation ratio or runtime bound.
• Worst-case instances, however, may be rare or nonexistent in practice.