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.