Learning Theoretic Foundations of Data-Driven Algorithm Design

Explore the foundations of data-driven algorithm design in this 45-minute lecture by Maria-Florina Balcan. Delve into machine learning techniques for solving combinatorial problems and understand how learning algorithms can be applied to algorithm design. Examine the concept of data-driven algorithm design, which utilizes learning and data to create algorithms suited for repeatedly solving instances of the same problem. Learn about uniform convergence and its implications for algorithm performance. Investigate general sample complexity using dual classes and pseudo-dimension for real-valued classes. Discover online algorithm selection techniques and regret guarantees. Gain insights into how data-driven algorithm design can overcome limitations of classic design methods by adapting algorithms to specific domains.

Intro
Machine Learning for Algorithm Design Learning algorithms for solving combinatorial problems. E.g.
Data-driven Algorithm Design Data-driven algo design: use learning & data for algo design. Suited when repeatedly solve instances of the same algo problem
Data-driven algorithm design: Problem Setup
Uniform Convergence Uniform convergence for any algo in Als, average performance over samples close to its expected performance. • Imply that Ā that does best over the sample has high expected performance
General Sample Complexity via Dual Classes
Pseudo-dimension (for real valued classes)
Pseudo-dimension, Uniform Convergence
Online Algorithm Selection (via online optimization of piecewise Lipschitz functions)
Online Regret Guarantees Existing techniques (for finite, linear, or convex case) select
Summary and Discussion Data-driven algo design can overcome major shortcomings of classic design by adapting the algo to the domain at hand. Different methods work better in different settings Learn an algo from a family that works best for a given domein.