Learning Theoretic Foundations of Data-Driven Algorithm Design

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.