Learning and testing submodular functions

  • Grigory Yaroslavtsev | Microsoft Reseach

Submodular functions capture the law of diminishing returns and can be viewed as a generalization of convexity to functions over the Boolean cube. Such functions arise in different areas, such as combinatorial optimization, machine learning and economics. In this talk we will give a brief overview of recent structural results about concise representations of submodular functions. Existence of small representations is useful for applications in learning such functions from examples and testing whether a given function is submodular with a small number of queries.

For the class submodular functions taking values in discrete integral range of size R we show a structural result, giving concise representation for this class by formulas. The representation can be described as a maximum over a collection of threshold functions, each expressed by an R-DNF formula. This leads to efficient PAC-style learning algorithms for this class, as well as testing algorithms with running time independent of the size of the domain.

Joint work with Sofya Raskhodnikova (SODA’13) and work in progress with Eric Blais, Krzysztof Onak and Rocco Servedio

Speaker Details

Penn State and Brown

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks