How Much Data Is Sufficient to Learn High-Performing Algorithms?

Explore a 25-minute lecture on data-driven algorithm design and its impact on runtime and solution quality. Delve into Ellen Vitercik's research from Carnegie Mellon University, presented at the Deep Learning and Combinatorial Optimization 2021 conference. Discover generalization guarantees for data-driven algorithm design, addressing the challenge of volatile performance in combinatorial algorithms. Learn about the unifying structure that enables broadly applicable theoretical guarantees, covering parameterized greedy algorithms, clustering algorithms, integer programming, and selling mechanisms. Examine how these guarantees apply to algorithms with piecewise-constant, -linear, or piecewise-structured performance functions. Gain insights into novel bounds for dynamic programming algorithms used in computational biology and explore topics such as sequence alignment algorithms, automated configuration, and the intrinsic complexity of algorithmic performance.

Intro
Data-driven algorithm design
Sequence alignment algorithms
Automated configuration
This talk: Main result
Domains with piecewise structure
Primary challenge in combinatorial domains
Example: Sequence alignment
Algorithmic performance
Generalization bounds
Piecewise constant utility function
Primal & dual classes
Warmup: 1-dimensional parameters
Intrinsic complexity
Main result (informal)
Outline
Piecewise constant dual functions