||Submodular Functions: Learnability, Structure, and Optimization
||Maria-Florina Balcan, Nicholas J. A. Harvey.|
43rd Annual ACM Symposium on Theory of Computing (STOC 11),
San Jose, CA, June 2011.
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous
algorithmic applications. They have been used in many areas, including combinatorial optimization,
machine learning, and economics. In this work we study submodular functions from a learning theoretic
angle. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability.
In doing so, we uncover several novel structural results revealing ways in which submodular
functions can be both surprisingly structured and surprisingly unstructured. We provide several concrete
implications of our work in other domains including algorithmic game theory and combinatorial
At a technical level, this research combines ideas from many areas, including learning theory (distributional
learning and PAC-style analyses), combinatorics and optimization (matroids and submodular
functions), and pseudorandomness (lossless expander graphs).
Learning Theory, Submodular Functions, Matroids
In this paper we use Talagrand's inequality to prove a concentration inequality for Lipschitz,
monotone submodular functions.
We were unaware of prior work proving concentration for subadditive functions by
Schechtman in 2003, using Talagrand's inequality,
and by Hajiaghayi et al. in 2005, using self-bounding functions.
In 2009, Chekuri and Vondrak also proved a concentration inequality for Lipschitz,
monotone submodular functions, using the FKG inequality.
Their inequality achieves Chernoff-type concentration, which is somewhat better than the
Talagrand-like concentration that we achieve.
An earlier version of our paper only proved concentration for matroid rank functions.
After learning of the work of Chekuri and Vondrak, we improved our inequality
to its current form, in which it applies to arbitrary Lipschitz, monotone, submodular functions.
Perhaps the nicest way to prove such inequalities is using self-bounding functions.
In particular, this approach yields concentration for non-monotone functions;
it is not clear whether the FKG or Talagrand approaches do too.
See the note by Vondrak from 2010.