We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube {0, 1} n . Our main result is the following structural theorem: any submodular function is ǫ-close in ℓ 2 to a real-valued decision tree (DT) of depth O(1/ǫ 2 ). This immediately implies that any submodular function is ǫ-close to a function of at most 2 variables and has a spectral ℓ 1 norm of 2 2 ) . It also implies the closest previous result that states that submodular functions can be approximated by polynomials of degree O(1/ǫ 2 ) (Cheraghchi et al., 2012). Our result is proved by constructing an approximation of a submodular function by a DT of rank 4/ǫ 2 and a proof that any rank-r DT can be ǫ-approximated by a DT of depth setting. In addition, we give improved learning algorithms for a number of related settings. We also prove that our PAC and agnostic learning algorithms are essentially optimal via two lower bounds: (1) an information-theoretic lower bound of 2 Ω(1/ǫ 2/3 ) on the complexity of learning monotone submodular functions in any reasonable model (including learning with value queries); (2) computational lower bound of n Ω(1/ǫ 2/3 ) based on a reduction to learning of sparse parities with noise, widely-believed to be intractable. These are the first lower bounds for learning of submodular functions over the uniform distribution.
In REF it is also shown that 2 Ω( −2/3 ) random examples (or even value queries) are necessary to PAC learn monotone submodular functions to 1 -error of .
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
ArXiv
ArXiv
Computer Science Mathematics