Machine Learning for Faster Optimization
summary
A model augments classical algorithms with predicted parameters that are provably learnable from past instances and robust to modest input changes. Examples: sorted-array lookup gets log η runtime where η is prediction error; restricted‑assignment scheduling predicts weights per machine yielding a fractional scheme with competitive ratio min(log η, log m) and a rounding cost of Θ(log log m) (lower bound matching). Warm‑starting Hungarian with predicted duals reduces iterations proportional to the L1 dual error; experiments on geometric and synthetic data show up to ~10× speedups with few training samples.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:04Collaborators
- 1:45Machine Learning is Transforming Society
- 2:19Optimization Augmented with Machine Learning
- 6:15Learning Augmented Algorithms
- 10:24ERL: Desirable Analysis Framework
- 12:18Makespan Minimization
- 15:26What (not) to Predict?
- 19:53Prediction: Machine Weights
- 20:28Fractional Assignments via Weights
- 24:36Results on Robustness
- 26:13Learnability
- 30:09Summary for Restricted Assignment
- 30:22Predictions for Online Algorithms
- 31:19Warm-Start
- 32:28Pitfalls
- 33:02Weighted Bipartite Matching
- 37:39Does it Work?
related talks
01h 14mMachine Learning For Algorithm Design
01h 05mOptimization for Machine Learning I
54mProgramming Language Design and Implementation for the Machine Learning Era: A Personal(…)
32mTaming the Machine: Basics of ML Models Training and Inference Optimization
54mProgramming Language Design and Implementation for the Machine Learning Era: A Personal(…)
01h 04mPredicting and optimizing the behavior of large ML models
01h 10mBayesian Optimization and Machine Learning for Accelerating Experiments in the Physical Sciences
21mKeynote: Easier Machine Learning Thoughts From Scikit-Learn