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.