Recent Progress on Submodular Function Minimization

on YouTube ↗32m

" summary

Recent results give concrete algorithms and bounds for submodular minimization when a minimizer has ≤ k elements: a deterministic weakly‑polynomial algorithm with parallel depth poly(k) (current exponent about k^6–k^7) and a randomized strongly‑polynomial method using ~n·poly(k) oracle queries. Key tools are the Lovász extension and duality to the base polytope, a new sparse dual certificate notion, a contraction trick when f* is near zero, and truncated mirror descent to produce the certificate in poly(k) iterations.

AI-written summary · about

" chapters (14)

1. 0:00Submodular function minimization intro
2. 1:46Problem definition and oracle access
3. 3:34State-of-the-art algorithms gaps
4. 6:32Motivation for sparse minimization
5. 8:00Parallel query models limits
6. 10:28Sparsity improve parallel algorithms?
7. 12:20Convex optimization with Lovász extension
8. 15:09Duality and base polytope
9. 19:54First-order methods challenges
10. 23:12Near-zero minimum values
11. 25:19Truncated mirror descent
12. 27:31Summary of techniques
13. 28:39Open problems future directions
14. 29:49Q&A