UBC Submodular Optimization CPSC 536S, Winter term 2, 2020
Course Outline
Submodular set functions have played a central role in the development of combinatorial optimization and could be viewed as the discrete analogue of convex functions. Submodularity has also been a useful model in areas such as economics, supply chain management and recently algorithmic game theory and machine learning. There has been a huge amount of work recently in approximation algorithms for various constrained submodular optimization models arising in practice, perhaps most prominently the social welfare maximization problem. We develop the basic properties of submodular functions and then present both classical methods and recent trends. Topics include: algorithms for unconstrained submodular maximization and minimization, polymatroids, local greedy algorithms, multilinear extensions and pipage rounding, Lovasz Extension and convex minimization, matroid constraints, multi-agent optimization, and many applications.
The course will be more theoretically focused as opposed to numerical. Hence a reasonable mathematical background (say in linear algebra) is recommended.
Instructor
Bruce Shepherd Email: fbrucesh@cs.ubc.ca Webpage: bshepherd.ca Office hours: Wednesday 13:30-15:00 (ICICS X839) or email to set up an appointment.
Lectures
Time: Tuesday and Thursday at 15:30-17:00 Hugh Dempster Paviliion 101
Teaching Assistant
Sikander Randhawa Office hours: Friday 11:30-12:30 (effective immediately. pls contact Sikander to set up online meetings. Updates on Piazza.)
Grading
Course grades will be based upon: 3 assignments (15% each), 3 quizzes (10% each), a take-home final exam (20%), and class participation! (5%).
Quiz Dates
all in class. tentatively the last Thursdays of January, February, March
Reading
There is no course textbook. The following may be useful supporting material in optimization generally.
- Submodular Functions and Optimization, by Satoru Fujishige.
- Combinatorial Optimization; a polyhedral perspective, by A. Schrijver.
- Convex Optimization: Algorithms and Complexity, by S. Bubeck.
- Understanding and using linear programming, by Matou\u{s}ek and G\"artner.
- Linear Programming, by V. Chv\'atal.
- The theory of linear and integer programming}, by A. Schrijver.
- A course in convexity, by A. Barvinok.
- Numerical Optimization, by Nocedal and Wright.
- Convex optimization, by Boyd and Vandenberghe.
- For graph theory: Bondy and Murty
- Primer on Complexity Theory.
What we've done so far...
Week 1.
Tuesday
Motivating Examples.
- Valuations and Pricing Optimization
- Cuts in Graphs. Minimum, Maximum and Sparsest Cuts.
- Submodular Welfare
Thursday
Understanding Submodulariy.
- How are submodular functions like concave/convex functions?
- Operations preserving submodularity.
Week 2.
Tuesday
Recognizing Submodulariy.
- Examples of Submodular Functions. Coverage functions, matroid rank functions, closure problems, facility location etc.
- Ring families, Intersecting and crossing families
- Submodularity in the Constraints
Thursday
Unconstrained Maximization.
- A Random Set is a 1/4-Approximation!
Week 3.
Tuesday
Lower Bounds for Unconstrained SO.
- We show that (somewhat amazingly) the Random Set Algorithm is optimal amongst a class of "myopic" non-adaptive algorithms.
- We mention stronger 1/2 lower bounds in both the oracle model and complexity model (assuming NP \neq RP)
Thursday
Double Greedy Algroithm.
- We prove that this is an (optimal) 1/2-approximation in expectation
Week 4.
Tuesday
Local Search.
- General discussion on neighbhourhood search. Examples where we dont know how to find local optima (max cut). Approximate Local Search.
- We show that a simple local search method is a 1/3-approximation for unconstrained submodular maximization.
Thursday
Extensions of Set Functions (continued).
- We define Convex, Concave, Multilinear and Lovasz Extensions of a set function.
- Quiz.
Week 5.
Tuesday Feb. 4
The Lovasz Extension of a Set Function is Convex IFF the Set Function is Submodular
Thursday Feb. 6
Polymatroids
- Definitions of Polymatroids and Extended Polymatroids.
- Summary of some basic facts and theorems (without proof) from convexity theory.
- Basics of LP Duality and Complementary Slackness.
Week 6
Tuesday Feb. 11
- The Greedy Algorithm for Extended Polytmatroids
- Equivalence of Separation and Optimization
- Solving Unconstrained Submodular Minimization (via Ellipsoid and Extended Polymatroids)
Thursday Feb. 13
The Ellipsoid Algorithm
Week 7
Reading Week
Week 8
Tuesday Feb. 25
- Projected Subgradient Methods. Convergence results statements.
- Comparison of runtime results for PSD versus Ellipsoid. In Polytime (strong/weak), Pseudo-Poly, epsilon-additive model (quantum, regular)
Thursday Feb. 27
Constrained Submodular Minimization
- Minimization Subject to Ring Families
- Parity Families
- Congruency Constrained Families
Week 9
Tuesday March 3
- Polynomial Inapproximability of Cardinality-Constrained Submodular Minimization
- Approximating Submodular Functions Everywhere. Learning a Submodular Function
Thursday March 5
- Further examples of Inapproximable Combinatorial Families
- Any good news? Submodular Node (Vertex) Cover)
- Blockers of Upwards-Closed Families
- B-Approximation for B-Bounded Blockers.
- Matching Inapproximability Result for B-Uniform Hypergraph Node Cover.
Week 10
Tuesday March 10
Intro to Constrained Maximization
- Definition of Generic Greedy Algorithm.
- Bad Example for Greedy Applied to Non-Monotone Functions
- Greedy is a (1-1/e)-Approximation For Monotone Submodular Maximization Subject to Cardinality Constraint
- Some Matroid Theory. Exchange Lemma.
Thursday March 12
- Definition of Generic Greedy Algorithm.
- 1/2-Approx for Monotone Submodular Maximization Subject to Matroid Constraint
- Introduction to p-Systems. Some examples.
- Tight (to constant factors) O(p)-Approx for p-systems
Week 11. Lectures Go Online.
Tuesday March 17
- Proof of the Partition Lemma Needed for Non-Monotone Maximization Over p-system.
Thursday March 19
- The Submodular Welfare Problem (SWP)
- SWP Can be Reduced to Monotone Maximization over a Partition Matroid.
- Motivating the Multilinear Extension
- Evaluating the Multilinear Extension
Week 12
Tuesday March 24
- Anlaytic Results for Multilinear Extensions.
- The Continuous Greedy Algorithm
Thursday March 26
- Rounding with Submodular Objectives in Matroid Polytope
Week 13
Tuesday March 31
Multi-Agent Submodular Optimization
- Submodular Welfare, Minimum Submodular Cost Allocation (MSCA)
- Applications to Multiway Cut, Metric Labelling and General Submodular k-Way Partition
- O(log^2(n)) MA Gap for Monotone Minimization
- (1-1/e) Gap for Multivariate Maximization
- Other Partitioning Objectives: Submodular Fair Allocation, Submodular Load Balancing
Thursday April 2
-
Continuous Submodularity
Week 14
Tuesday April 7
- Applications of Frank-Wolfe or Combinatorial Algorithm for SFM or Projected Subgradient Methods for SFM