Machine Learning For Algorithm Design

on YouTube ↗01h 14m

" summary

Survey of concrete claims and tools: performance of parameterized combinatorial algorithms is piecewise constant in parameters on each input, so learning bounds follow from bounding the dual class and yield sample complexity ~O((log max input length)/ε^2) for sequence alignment; online configuration is impossible worst‑case but piecewise/Lipschitz structure gives no‑regret algorithms. Algorithms with predictions give provable consistency vs robustness tradeoffs (array search runs in time ~log |t−h| with predictor h; ski‑rental uses a tunable λ). Learning-to-prune uses an explore with prob 1/√j scheme, keeps average search size near the union of needed regions and drives mistakes → 0 (Pittsburgh map reduced nodes with ~0.06 mistake rate).

AI-written summary · about

" chapters (35)

1. 0:00Introduction to speaker
2. 0:37Machine learning for algorithms
3. 1:23Challenges in algorithmic tuning
4. 2:41Sequence alignment example
5. 4:08Algorithm selection issues
6. 6:11Harnessing data for design
7. 8:05Theoretical research surge
8. 9:14Algorithm configuration model
9. 12:34Generalization guarantees
10. 14:41Online algorithm configuration
11. 15:29Performance volatility
12. 17:05Formal model and guarantees
13. 19:44Structure in sequence alignment
14. 21:42Primal function complexity
15. 24:15Dual function advantages
16. 25:55Main theorem proof sketch
17. 30:21Applying theory to alignment
18. 30:59Online configuration results
19. 34:05Q&A on configuration
20. 37:20Algorithms with predictions
21. 39:08Binary search with predictions
22. 42:05Ski rental analysis
23. 43:31Incorporating predictions
24. 47:06Tradeoffs in tuning lambda
25. 50:20Proof sketch of bounds
26. 52:05Design principles
27. 55:15Q&A on predictions
28. 56:14Learning to prune
29. 58:40Formal prunings model
30. 1:01:05Pruning algorithm steps
31. 1:02:03Performance guarantees
32. 1:03:43Routing experiments
33. 1:04:34Future directions
34. 1:07:08Closing thoughts
35. 1:11:24Final Q&A

" related talks

• 44mMachine Learning for Faster OptimizationBen Moseley · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 52mLearning as a Tool for Algorithm Design and Beyond-Worst-Case AnalysisKevin Leyton-Brown · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 45mCharting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ...Gregory Valiant · Rigorous Evidence for Information-Computation Trade-offs
• 44mParsimonious Learning-Augmented AlgorithmsRavi Kumar · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 37mEfficient Algorithms for Reliable Machine LearningAdam R. Klivans · The Role of TCS in Modern Machine Learning
• 59mTesting Assumptions of Learning AlgorithmsArsen Vasilyan · Sublinear Algorithms Boot Camp 2024
• 39mA PAC Approach to Application-Specific Algorithm SelectionRishi Gupta · Learning, Algorithm Design and Beyond Worst-Case Analysis