Submodularity: Theory and Applications I

on YouTube ↗01h 04m

" summary

Defines submodularity as diminishing marginal gains and claims a practical recipe: convert a set function to the Lovász extension (a convex, piecewise‑linear extension), optimize over the base polytope, then threshold to recover an exact discrete minimizer. Key tools: Edmonds’ greedy for linear optimization (≈ n log n), base polytope geometry, Frank–Wolfe / minimum‑norm algorithms and ellipsoid for polynomial‑time guarantees. Examples tied to ML: sensor placement (mutual information submodular if observations are conditionally independent), coverage, graph cuts, and determinantal point processes.

AI-written summary · about

" chapters (21)

1. 0:00Start
2. 6:33Convex functions (Lovász, 1983)
3. 7:51Outline
4. 8:36Diminishing gains
5. 11:32Submodular set functions
6. 13:08Example: modular function
7. 16:34Example: sensing
8. 17:57Example: entropy
9. 19:26Submodularity and independence
10. 21:34Example: graph cuts
11. 23:03Log-supermodular distributions
12. 28:22Log-submodular distributions
13. 29:25Submodularity...
14. 35:18Deep Submodular Functions
15. 44:08Lovász extension: example
16. 44:59Alternative characterization
17. 45:45Submodular polyhedra
18. 47:27The magic of base polytopes
19. 53:29Putting things together
20. 54:12Submodular minimization
21. 55:28Different relaxation

" related talks

• 44mStructured Sparsity-Inducing Norms Through Submodular FunctionsFrancis Bach · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 48mFrom Predictions to Decisions: Limitations and Possibilities of Optimization from SamplesYaron Singer · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation IIJason Hartline · Economics and Computation Boot Camp 2015
• 51mMin-max Optimization: From Complexity to AlgorithmsEmmanouil Zampetakis · Adversarial Approaches in Machine Learning 2022
• 51mFirst-Order Methods and Hyperbolic ProgrammingJames Renegar · Hyperbolic Polynomials and Hyperbolic Programming
• 49mDiscrete Optimization using Log-Concave PolynomialsNima Anari · Hyperbolic Polynomials and Hyperbolic Programming
• 27mNonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to LearningGeorgina Hall · Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)