Submodularity: Theory and Applications II

on YouTube ↗01h 04m

" summary

Greedy selection provably achieves a 1-1/e ≈ 0.63 approximation for monotone submodular maximization under a cardinality constraint and is optimal with oracle access; the multilinear relaxation plus a continuous greedy (Frank–Wolfe–style) optimizer and rounding yields 1-1/e−ε for many downward-closed constraints; a distributed random-partition + merge scheme matches centralized greedy empirically; unconstrained non‑monotone optimization uses the double‑greedy algorithm with a 1/2 guarantee; curvature and semi‑gradient modular bounds improve guarantees and enable variational inference bounds on partition functions.

AI-written summary · about

" chapters (32)

1. 0:00Intro
2. 1:06Application: Information Gathering
3. 2:39Application: Data Summarization
4. 7:03Maximizing monotone functions
5. 9:23How good is greedy? in practice...
6. 10:30How good is greedy? ... in theory
7. 13:36Proof Sketch
8. 15:30Questions
9. 17:27More complex constraints: budget
10. 18:59Relax: Discrete to continuous
11. 20:54Multilinear extension
12. 22:11Compare: Multilinear vs. Lovász ext.
13. 23:18Illustration of Continuous Greedy
14. 26:17Continuous submodular maximization
15. 29:40Distributed greedy algorithms
16. 31:48Distributed Greedy (GREEDI)
17. 32:04Empirical Performance
18. 33:38Non-monotone functions
19. 36:10Submodular maximization: summary
20. 38:32Submodular vs. modular optimization
21. 40:45General strategy
22. 40:59Sub- and superdifferentials
23. 43:21Semigradient polyhedral structure
24. 45:28Guarantees
25. 46:53From optimization to distributions
26. 47:49Key challenge
27. 50:04Application: Semantic Segmentation
28. 51:16Outline
29. 51:56Active learning / diagnosis
30. 53:41Problem Statement
31. 54:51Adaptive greedy policy
32. 57:01Adaptive submodularity

" related talks

• 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
• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 57mComputationally Efficient Alternatives to Nonconvex-Nonconcave Min-Max OptimizationNisheeth Vishnoi · Adversarial Approaches in Machine Learning 2022
• 30mOn Approximation Guarantees for Greedy Low Rank OptimizationSahand Negahban · Optimization, Statistics and Uncertainty
• 27mTalk by Ali Kavis (UT Austin)Ali Kavis · Joint IFML/MPG Symposium 2024
• 49mDiscrete Optimization using Log-Concave PolynomialsNima Anari · Hyperbolic Polynomials and Hyperbolic Programming
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)