EE563 - Submodular Functions, Optimization, and Applications to Machine Learning, Spring Quarter, 2018

This page is located at

A version of this class was taught previously, and its contents and slides can be found at


Prof. Jeff A. Bilmes --- Email me
Office: 418 EE/CS Bldg., +1 206 221 5236
Office hours: TBD, EEB-418 (+ online)


Class is held: Mon/Wed 10:30-12:20, EEB, Room 042.


Submodular Functions, Optimization, and Applications to Machine Learning

Description: This class will be a thorough introduction to submodular functions.

This class will be a thorough introduction to submodular functions. Applications of submodularity are vast, and include areas in in computer vision, constraint satisfaction, game theory, social networks, economics, information theory, structured convex norms, natural language processing, sensor networks, graphical models and probabilistic inference, and other areas of machine learning. Submodularity is a good model for cooperation, complexity, and attractiveness as well as for diversity, coverage, and information.

In this class, we will learn about a variety of properties of submodularity and supermodularity. Motivated by applications, we'll cover submodularity's definitions, its properties, the many operations that preserve submodularity, variants and extensions of submodularity, and certain special submodular functions, and computational properties. The goal of this section will be to develop a deep intuitive understanding of both submodular and supermodular functions.

Other topics we will overview include: the theory of matroids and lattices, polyhedral properties of submodular functions, subdifferentials and superdifferentials, the Lovasz extension (i.e., the Choquet integral) of submodular functions and convex and concave extensions in general.

As for submodular optimization, we'll discuss submodular maximization algorithms in the unconstrained and constrained (i.e., knapsack, matroid, combinatorial, etc.) cases, the ever important greedy algorithm and its uses. For submodular minimization, we'll give 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 (as well as discuss both unconstrained and constrained cases).

Other problems we'll discuss include submodular cover problems, submodular flow problems, the principle partition of a submodular function and its variants. We'll see, for example, how submodularity can be used to solve non-submodular problems, for example difference of submodular programs, and submodular relaxation strategies.


Homework must be done and submitted electronically via the following link
  1. See Canvas announcements

Lecture Slides

Lecture slides will be made available as they are being prepared --- they will probably appear soon 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. The slides are available as "presentation slides" and also in (mostly the same content) 2-up form for printing. After lecture, the marked up slides will appear under the "presented slides" column (and might include typo fixes, ink corrections, and other little notes/discussions/drawings that occured during class).
Lec. # Slides 2-Up Slides Lecture Date Last Updated Contents Presented Slides Video
1 pdf pdf 3/26/2018 3/26/2018 Logistics, Motivation, Applications. pdf
2 pdf pdf 3/28/2018 3/28/2018 Machine Learning Apps (diversity, complexity, parameter, learning target, surrogate). pdf
3 pdf pdf 4/2/2018 4/2/2018 Info theory exs, more apps, definitions, graph/combinatorial examples pdf
4 pdf pdf 4/4/2018 4/4/2018 Graph and Combinatorial Examples, Matrix Rank, Examples and Properties, visualizations pdf
5 pdf pdf 4/9/2018 4/9/2018 More Examples/Properties/ Other Submodular Defs., Independence, Matroids pdf
6 pdf pdf 4/11/2018 4/11/2018 Matroids, Matroid Examples, Matroid Rank, Partition/Laminar Matroids pdf
7 pdf pdf 4/16/2018 4/16/2018 Laminar Matroids, System of Distinct Reps, Transversals, Transversal Matroid, Matroid Representation, Dual Matroids pdf
8 pdf pdf 4/16/2018 4/16/2018 Dual Matroids, Other Matroid Properties, Combinatorial Geometries, Matroids and Greedy. pdf
9 pdf pdf 4/23/2018 4/23/2018 Polyhedra, Matroid Polytopes, Matroids to Polymatroids pdf
10 pdf pdf 4/30/2018 4/30/2018 Matroids to Polymatroids, Polymatroids pdf
11 pdf pdf 5/2/2018 5/2/2018 Polymatroids, Polymatroids and Greedy, pdf
12 pdf pdf 5/7/2018 5/7/2018 Possible Polytopes, Extreme Points, Polymatroids, Greedy, and Cardinality Constrained Maximization pdf
13 pdf pdf 5/9/2018 5/9/2018 Constrained Submodular Maximization pdf
14 pdf pdf 5/14/2018 5/14/2018 Submodular Max w. Other Constraints, Cont. Extensions, Lovasz Extension pdf
15 pdf pdf 5/16/2018 5/16/2018 Cont. Extensions, Lovasz Extension, Choquet Integration, Properties pdf
16 pdf pdf 5/21/2018 5/21/2018 More Lovasz extension, Choquet, defs/props, examples, multiliear extension pdf
17 pdf pdf 5/23/2018 5/23/2018 Finish L.E., Multilinear Extension, Submodular Max/polyhedral approaches, Most Violated inequality, Still More on Matroids, Closure/Sat pdf
18 pdf pdf 5/30/2018 5/30/2018 Closure/Sat, Fund.\ Circuit/Dep pdf
19 pdf pdf 6/6/2018 6/6/2018 Min-Norm Point Definitions, Proof that min-norm gives optimal Review \& Support for Min-Norm, Computing Min-Norm Vector for B_f pdf
Lec. # Slides 2-Up Slides Lecture Date Last Updated Contents Presented Slides Video

Discussion Board

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