On Connections Between Submodularity and Concavity

Friday, February 27, 2015 - 9:00am - 9:50am
Keller 3-180
Jeff Bilmes (University of Washington)
In this work, we provide a more complete picture on the relationship
between submodularity with concavity by extending some of the results
connecting submodularity with convexity to the concave aspects of
submodular functions. We first show the existence of the
superdifferentials and tight modular upper bounds of a submodular
function. While it is hard to characterize this polyhedron, we obtain
inner and outer bounds on the superdifferential along with certain
specific supergradients that have been useful and practical in some
machine learning applications (which we briefly survey). We also show
connections between optimality conditions over the superdifferentials
and submodular maximization, and show how forms of approximate
optimality conditions translate into approximation factors for
maximization. Lastly, we consider versions of the discrete separation
theorem and the Fenchel duality theorem when seen from the concave
point of view.

Joint work with Rishabh Iyer (
MSC Code: