Learning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning Problems

on YouTube ↗33m

" summary

Proves that two natural algorithm families—agglomerative alpha-linkage clusterings and Feige–Langberg S‑linear SDP roundings for MaxCut—have sample complexity only theta(log N) pseudo-dimension. Key tools: partition the parameter line into polynomial intervals (clustering flips come from comparisons determined by eight points) and derive closed‑form, piecewise quadratic expressions for rounding. Practical procedure draws O(log N) instances, uses one hyperplane per sample, evaluates one parameter per interval and finds the empirically best parameter efficiently.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:36Learning the "best" algorithm
3. 1:32Example: Clustering Clustering webpages by topic
4. 2:04Example: Integer Quadratic Programming
5. 2:44Background Work
6. 3:05Algorithm Selection Model
7. 5:36Pseudodimension of COSTA
8. 7:26A rich class of clustering algorithms
9. 9:17Key Challenge
10. 12:55Pseudodimension bounds
11. 18:49Maximum Cut
12. 19:33Standard approximation approach
13. 20:32A family of SDP rounding techniques
14. 22:53Key Idea
15. 28:10Computationally Efficient Algorithm Selection
16. 29:50Summary

" related talks

• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 26mMathematical Approaches to ClusteringJoseph Ross · MLconf Online 2020
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 52mMax Cut with Linear Programs: Sherali-Adams Strikes BackTselil Schramm · Hyperbolic Polynomials and Hyperbolic Programming
• 01h 01mNearest Neighbor Methods IIIlya Razenshteyn · Foundations of Data Science Boot Camp 2018
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty