Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

We investigate the approximability of several classes of real-valued functions by functions of a small number of variables (juntas). Our main results are tight bounds on the number of variables required to approximate a function f:{0, 1}ⁿ → [0,1] within ℓ₂-error ϵ over the uniform distribution: If f is sub modular, then it is ϵ-close to a function of O(1/ϵ² log 1/ϵ) variables. This is an exponential improvement over previously known results FeldmanKV:13. We note that Ω(1/ϵ²) variables are necessary even for linear functions. If f is fractionally sub additive (XOS) it is ε-close to a function of 2^O(1/ϵ2) variables. This result holds for all functions with low total ℓ₁-influence and is a real-valued analogue of Fried gut´s theorem for boolean functions. We show that 2^Ω(1/ϵ) variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a PAC learning algorithm that runs in time 2^1/poly(ϵ) poly(n). For sub modular functions we give an algorithm in the more demanding PMAC learning model BalcanHarvey:[12] which requires a multiplicative (1 + γ) factor approximation with probability at least 1 - ϵ over the target distribution. Our uniform distribution algorithm runs in time 2^1/poly(γϵ) poly(n). This is the first algorithm in the PMAC model that can achieve a constant approximation factor arbitrarily close to 1 for all sub modular functions (even over the uniform distribution). It relies crucially on our approximation by junta result. As follows from the lower bounds in FeldmanKV:13 both of these algorithms are close to optimal. We also give applications for proper learning, testing and agnostic learning with value queries o- these classes.