Learning Submodular Functions

Abstract

This paper considers the problem of learning submodular functions. A problem instance consists of a distribution on {0,1}[superscript n] and a real-valued function on {0,1}[superscript n] that is non-negative, monotone and submodular. We are given poly(n) samples from this distribution, along with the values of the function at those sample points. The task is to approximate the value of the function to within a multiplicative factor at subsequent sample points drawn from the distribution, with sufficiently high probability. We prove several results for this problem. • There is an algorithm that, for any distribution, approximates any such function to within a factor of √n on a set of measure 1 − ϵ. • There is a distribution and a family of functions such that no algorithm can approximate those functions to within a factor of Õ(n[superscript 1/3]) on a set of measure 1/2 + ϵ. • If the function is a matroid rank function and the distribution is a product distribution then there is an algorithm that approximates it to within a factor O (log(1/ϵ)) on a set of measure 1 − ϵ. Our study involves a twist on the usual learning theory models and uncovers some interesting extremal properties of submodular functions.