Learning What Works Best When

on YouTube ↗42m

" summary

Presents an algorithmic advance that computes exact projection via InFiX of separable convex functions onto submodular base polytopes, amortizing to O(n) submodular-minimizations and proving a quadratic bound on discrete-Newton iterations versus previous n^8 bounds; shows faster exact solves than Frank–Wolfe in cardinality cases. Builds an empirical Max‑Cut study: a 3,300-instance library, 37 implemented heuristics run on EC2 with standardized runtimes; finds no single winner, and that selection raises best-solution hit rate 15→37% (48% with parallel portfolios).

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 6:25Outline
3. 34:07Interpreting Heuristic Performance
4. 36:38Heuristic Class Performance

" related talks

• 01h 04mSubmodularity: Theory and Applications IStefanie Jegelka · Foundations of Machine Learning Boot Camp 2017
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 01h 04mSubmodularity: Theory and Applications IIAndreas Krause · Foundations of Machine Learning Boot Camp 2017
• 33mLearning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning ProblemsVaishnavh Nagarajan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 00mOn Approximating the Covering Radius and Finding Dense Lattice SubspacesDaniel Dadush · Lattices: Geometry, Algorithms and Hardness 2020
• 48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from SamplesYaron Singer · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 43mComputational and Statistical Tradeoffs via Convex RelaxationVenkat Chandrasekaran · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 46mSmooth Nonconvex Min-Max OptimizationMeisam Razaviyayn · Adversarial Approaches in Machine Learning 2022