# EE595A - Submodular Functions, Their Optimization And Applications - Spring Quarter 2011

### NOTE: The submodular course was taught again Fall Quarter, 2012 with updated and improved material (that continues to be updated), and then again in Spring 2014 that includes youtube videos.

# Instructor:

**Prof. Jeff A. Bilmes**--- Email me

Office: 418 EE/CS Bldg., +1 206 221 5236

Office hours: Wednesdays, 12:30-1:30, EEB-418

# Announcements

- (6/7) Dropbox slots have been created for final project reports and final slides.
- (5/17) Please take a look at your dropbox for final project comments.
- (5/13) Homework 2 is due one week from today. It consists of all things marked as a red "Exercise:" in the lecture slides since the last homework.
- (4/29/2011) One page revision 1 final project proposals due one week from today, on Friday May 6th, at 5:00pm using electronic submission.
- Homework 1 is posted.
- (March 28th) Welcome to the class!

# Information

Description: Submodular functions have a long history in economics, game theory, combinatorial optimization, electrical networks, and operations research. A submodular function operates on subsets of some finite ground set, and that has certain properties that make optimization either tractable or approximable where otherwise neither would be possible. The properties are quite natural, however, so submodular functions are both flexible and widely applicable to real problems. At this time, submodular functions are gaining significant interest in the area of machine learning.

This course will serve as an introduction to submodular functions including methods for their optimization, and how they have been (and can be) applied in many application domains. The material we will cover includes:

- Introduction to submodular functions, including definitions, real-world and contrived examples of submodular functions, properties, operations that preserve submodularity, submodular variants and special submodular functions, and computational properties.
- Background on submodular functions, including a brief overview of the theory of matroids and lattices.
- Polyhedral properties of submodular functions
- The Lovász extension of submodular functions. The Choquet integral.
- Submodular maximization algorithms under simple constraints, submodular cover problems, greedy algorithms, approximation guarantees
- Submodular minimization algorithms, a history of submodular minimization, including both numerical and combinatorial algorithms, computational properties of these algorithms, and descriptions of both known results and currently open problems in this area.
- Submodular flow problems, the principle partition of a submodular function and its variants.
- Constrained optimization problems with submodular functions, including maximization and minimization problems with various constraints. An overview of recent problems addressed in the community.
- Applications of submodularity in computer vision, constraint satisfaction, game theory, information theory, norms, natural language processing, graphical models, and machine learning

Course Format: Two two-hour lectures per week (WF 10:30-12:20 Mueller Hall (MUE)-155) per week.

Prerequisites: ideally knowledge in probability, statistics, convex optimization, and combinatorial optimization although these will be reviewed as necessary. The course is open to students in all UW departments. If you are in doubt about taking this course, please contact me.

Texts: We will be drawing from the book by S. Fujishige entitled "Submodular Functions and Optimization" 2nd Edition, 2005, but we will also be reading research papers that will be either posted here on this web page or listed at the end of the lecture slides.

Grades and Assignments: Grades will be based on a combination of a final project (35%), homeworks (35%), and the take home midterm exam (30%). There will be between 2-3 homeworks during the quarter.

Final project: The final project will consist of a 4-page paper (conference style) and a final project presentation. The project must involve using or dealing mathematically with submodularity in some way or another.

# Homework

There will be 2-3 homeworks for the quarter. Homework must be done and submitted electronically via the following link here.- Problem set 1 Due Tuesday, April 26th, 11:45pm.
- Problem set 2 Due Friday, May 20th, 11:45pm. It consists of all exercises mentioned in the lecture slides (please do them in chronological order).

# Lecture Slides

Lecture slides will be made available as they are being prepared --- they will probably appear here right before a given lecture, and they will be in PDF format (original source is latex). Note, that these slides are corrected after the lecture (and might also include some additional discussion we had during lecture). If you find bugs/typos in these slides, please email me.Lecture 1 from 3/30/11. | (last updated 4/1/11) | Introduction, Intuition, Submodular Definitions, Graph Submodular Functions, Operations on Submodular Functions |

Lecture 2 from 4/1/11. | (last updated 4/2/11) | More Submodular Functions, Max, Facility location, Determinant, Concave, Saturation, Diminishing Returns = Union/Intersection |

Lecture 3 from 4/6/11. | (last updated 4/6/11) | Abstract Independence, Subtrees of a graph, Intro Matroids, Rank, Properties of Matroids, Matroid examples (uniform, linear, cycle/graphic, partition) |

Lecture 4 from 4/8/11. | (last updated 4/9/11) | More on Partition Matroid, Systems of Disctinct Reps, Transversals, Transversal Matroids, |

Lecture 5 from 4/13/11. | (last updated 4/13/11) | Matroid Representability, Dual Matroid, Matroid and Greedy Algorithm, Matroid Restriction/Deletion/Contraction/Union/Intersection |

Lecture 6 from 4/15/11. | (last updated 5/27/11) | Polyhedra, Convex Polytopes, Linear Programming, Matroid Polytope, Optimization in Matroid Polytopes and Greedy algorithm |

Lecture 7 from 4/20/11. | (last updated 5/27/11) | Base polytope equivalence, spanning set polytope, vector rank, polymatroid, side-by-side comparison of matroid and polymatroid, polymatroid examples, polymatroid functions, non-polymatroidal polytopes, most violated inequality problem |

Lecture 8 from 4/27/11. | (last updated 5/3/11) | most violated inequality problem, background: bipartite matching, matroid intersection, matroid intersection and traveling salesman problem (TSP), graphic matroid intersection example, alternating/augmenting sequences, border graphs, matroid partition problem |

Lecture 9 from 4/29/11. | (last updated 5/3/11) | more details on Matroid intersection and matroid partition problems, relating back to most violated inequality, key max/min theorem for submodular functions |

Lecture 10 from 5/4/11. | (last updated 5/5/11) | Matroid partition with flows, more most violated inequality, towards submodular function minimization (SFM), |

Lecture 11 from 5/6/11. | (last updated 5/10/11) | towards SFM, polymatroids and greedy, Lovász extension, |

Lecture 12 from 5/11/11. | (last updated 5/11/11) | Lovász extension, who's extension, Choquet integration, polymatroid extreme points, |

Lecture 13 from 5/13/11. | (last updated 5/17/11) | Still more about polymatroid extreme points, closure/sat, supp, dependence function (dep), greedy and extreme, |

Lecture 14 from 5/18/11. | (last updated 5/24/11) | greedy extreme, partially ordered sets, lattices, distributive lattices, modular and semi-modular lattices, why submodular is called submodular |

Lecture 15 from 5/20/11. | (last updated 5/24/11) | More on modular/distributed lattices, submodular lattices, ideal, boolean, join irreducible. Lattices and the supp, sat, and dep functions. dep and partial order, |

Lecture 16 from 5/25/11. | (last updated 5/26/11) | partial order of polymatroidal extreme points, more on supp, sat, dep., dep and greedy order, greedy and extreme points, |

Lecture 17 from 5/27/11. | (last updated 5/31/11) | Testing for polymatroidal extreme point is easlier than membership testing, tight sets, dimensionality of base polytope, base polytope existence, base polytope intersection, examples, early approaches to SFM for arbitrary g, |

Lecture 18 from 6/1/11. | (last updated 6/7/11) | saturation/exchange capacity, dep revisited, more on SFM |

Lecture 19 from 6/3/11. | (last updated 6/7/11) | SFM algorithm and proof, brief overview of modern approaches to SFM |

Lecture 20 from 6/9/11. | (last updated 6/11/11) | min-norm algorithm, tight modular bounds, min symmetric submodular functions, max of monotone submodular functions with various constraints (cardinality, knapsack, matroids), submodular set cover, accelerated (lazy) greedy algorithm, non-monotone max, polyhedral approaches to submodular max, final. |

# Actually Presented Lecture Slides, Spring, 2011

Lecture slides that were presented in class, along with all of the bugs and typos, my ink corrections of (perhaps some) of the bugs and typos, and any other little notes/discussions/drawings I drew on the slides during class. The above slides often contain more material than these as any discussions during class were added to the above after class. On the other hand, there might be a few hand-drawn figures in the below that I have not yet added to the above. Note: not all PDF readers can see the annotations in these slides (e.g., at least the Safari embedded reader on the iphone/ipad doesn't see them) --- the annotations were done with Adobe acrobat.- Lecture 1 from 3/30/11.
- Lecture 2 from 4/1/11.
- Lecture 3 from 4/6/11.
- Lecture 4 from 4/8/11.
- Lecture 5 from 4/13/11.
- Lecture 6 from 4/15/11.
- Lecture 7 from 4/20/11.
- Lecture 8 from 4/27/11.
- Lecture 9 from 4/29/11.
- Lecture 10 from 5/4/11.
- Lecture 11 from 5/6/11.
- Lecture 12 from 5/11/11.
- Lecture 13 from 5/13/11.
- Lecture 14 from 5/18/11. (annotations lost)
- Lecture 15 from 5/20/11.
- Lecture 16 from 5/25/11.
- Lecture 17 from 5/27/11.
- Lecture 18 from 6/1/11.
- Lecture 19 from 6/3/11.
- Lecture 20 from 6/9/11.

# Discussion Board

You can post questions, discussion topics, or general information at this link.# Relevant Books

There are many books available that discuss some the material that we are covering in this course. Some good books are listed below, but see the end of the lecture slides for books/papers that are relevant to each specific lecture.- Fujishige, "Submodular Functions and Optimization", 2005
- Narayanan, "Submodular Functions and Elecrical Networks", 1997
- Welsh, "Matroid Theory", 1975.
- Oxley, "Matroid Theory", 1992 (and 2011).
- Lawler, "Combinatorial Optimization: Networks and Matroids", 1976.
- Schrijver, "Combinatorial Optimization", 2003
- Gruenbaum, "Convex Polytopes, 2nd Ed", 2003.

# Important Dates

- Memorial Day, Monday, May 30th
- Final Project Reports, Time/Date TBD
- Final Project Presentations, Time/Date/Place TBD