Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees

الأصل · EN

We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube {0,1}ⁿ. Our main result is the following structural theorem: any submodular function is ε-close in ℓ₂ to a real-valued decision tree (DT) of depth O(1/ε²). This immediately implies that any submodular function is ε-close to a function of at most 2ᵒ⁽¹/ε²⁾ variables and has a spectral ℓ₁ norm of 2ᵒ⁽¹/ε²⁾. It also implies the closest previous result that states that submodular functions can be approximated by polynomials of degree O(1/ε²) (Cheraghchi et al., 2012). Our result is proved by constructing an approximation of a submodular function by a DT of rank 4/ε² and a proof that any rank-r DT can be ε-approximated by a DT of depth 5/2(r+(1/ε)). We show that these structural results can be exploited to give an attribute-efficient PAC learning algorithm for submodular functions running in time O(n²) · 2ᵒ⁽¹/ε⁴⁾. The best previous algorithm for the problem requires nᵒ⁽¹/ε²⁾ time and examples (Cheraghchi et al., 2012) but works also in the agnostic 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Ω⁽¹/ε²/³⁾ on the complexity of learning monotone submodular functions in any reasonable model; (2) computational lower bound of nΩ⁽¹/ε²/³⁾ 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.