Optimal bounds on approximation of submodular and XOS functions by juntas

Vitaly Feldman, Jan Vondrák

Abstract

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} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> → [0, 1] within ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> -error ε over the uniform distribution: If f is submodular, then it is ε-close to a function of O(1/ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">e</sub> 2) variables. This is an exponential improvement over previously known results [1]. We note that Ω(1/e <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) variables are necessary even for linear functions. If f is fractionally subadditive (XOS) it is ε-close to a function of 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1/e</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">)</sup> variables. This result holds for all functions with low total ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -influence and is a real-valued analogue of Friedgut's theorem for boolean functions. We show that 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ω(1/e)</sup> 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/poly(∈)poly</sup> (n). For submodular functions we give an algorithm in the more demanding PMAC learning model [2] which requires a multiplicative (1 + γ) factor approximation with probability at least 1 - ∈ over the target distribution. Our uniform distribution algorithm runs in time 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/poly(γ∈)</sup> poly(n). This is the first algorithm in the PMAC model that can achieve a constant approximation factor arbitrarily close to 1 for all submodular functions (even over the uniform distribution). It relies crucially on our approximation by junta result. As follows from the lower bounds in [1] both of these algorithms are close to optimal. We also give applications for proper learning, testing and agnostic learning with value queries of these classes.
BibTeX
@article{feldman2016optimal,
  author = {Vitaly Feldman and Jan Vondrák},
  title = {{Optimal bounds on approximation of submodular and XOS functions by juntas}},
  journal = {SIAM Journal on Computing},
  year = {2016},
  doi = {10.1137/140958207},
}
Figure