Learning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis

on YouTube ↗52m

" summary

Shows that a learned empirical hardness model (features → runtime) predicts run time of black‑box SAT and MIP solvers with RMS error often <1 (i.e., better than order‑of‑magnitude) using random forests; uses that model to drive sequential model‑based algorithm configuration (SMAC‑style) and build portfolios (SATZilla/Hydra). Example: CPLEX/Gurobi solve ~25%/10% of FCC graph‑coloring instances under a 1‑minute cutoff, configured clasp reaches ~75%, and an 8‑solver portfolio improves further. Also yields simple interpretable rules (≈70% satisfiability accuracy) using LP‑slack features.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 1:03Intractability
3. 2:44Motivating Question
4. 10:31Overall View
5. 15:13Examples: EHMs for SAT, MIP
6. 19:01Modeling Algorithm Families
7. 24:11Deep Optimization
8. 29:59Visualizing Sequential Model-Based Optimization
9. 32:56Sequential Model-based Algorithm Configuration (SMAC)
10. 33:28Applications of Algorithm Configuration
11. 35:09Algorithm Selection
12. 40:42Hydra: Automatic Portfolio Synthesis
13. 42:51Building (& Evaluating) a Feasibility Tester • Data generated Nov 2015 - Feb 2016 using - the FCC's Nov 2015 interference constraints - the FCC's "smoothed ladder" simulator - varying simulation assumptions
14. 45:02Feasibility Testing via MIP Encoding
15. 46:31Feasibility Testing via SAT Encoding
16. 47:09Performance of the Algorithm Portfolio
17. 48:10A Simple Model Beats Random Guessing

" related talks

• 01h 14mMachine Learning For Algorithm DesignEllen Vitercik · Data-Driven Decision Processes Boot Camp 2022
• 28mBack to the Future: Going Beyond Worst Case AnalysisSanjeev Arora · KARPfest80
• 44mMachine Learning for Faster OptimizationBen Moseley · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond
• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 51mHow to Predict When Estimation is Hard: Algorithms for Learning on GraphsSasha Rakhlin · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 26mStop Explaining Black Box Models, Use Interpretable Models InsteadDr. Rudin · MLconf Online 2020
• 45mLLMs can't optimize schedules, but AI can!Tom Cools · Voxxed Days CERN 2026