arXiv Analytics

Sign in

arXiv:1307.3301 [cs.DS]AbstractReferencesReviewsResources

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

Vitaly Feldman, Jan Vondrak

Published 2013-07-12, updated 2015-03-30Version 3

We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}). Our main results are tight bounds on the number of variables required to approximate a function $f:\{0,1\}^n \rightarrow [0,1]$ within $\ell_2$-error $\epsilon$ over the uniform distribution: 1. If $f$ is submodular, then it is $\epsilon$-close to a function of $O(\frac{1}{\epsilon^2} \log \frac{1}{\epsilon})$ variables. This is an exponential improvement over previously known results. We note that $\Omega(\frac{1}{\epsilon^2})$ variables are necessary even for linear functions. 2. If $f$ is fractionally subadditive (XOS) it is $\epsilon$-close to a function of $2^{O(1/\epsilon^2)}$ variables. This result holds for all functions with low total $\ell_1$-influence and is a real-valued analogue of Friedgut's theorem for boolean functions. We show that $2^{\Omega(1/\epsilon)}$ 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^{poly(1/\epsilon)} poly(n)$. For submodular functions we give an algorithm in the more demanding PMAC learning model (Balcan and Harvey, 2011) which requires a multiplicative $1+\gamma$ factor approximation with probability at least $1-\epsilon$ over the target distribution. Our uniform distribution algorithm runs in time $2^{poly(1/(\gamma\epsilon))} poly(n)$. This is the first algorithm in the PMAC model that over the uniform distribution can achieve a constant approximation factor arbitrarily close to 1 for all submodular functions. As follows from the lower bounds in (Feldman et al., 2013) 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.

Comments: Extended abstract appears in proceedings of FOCS 2013
Categories: cs.DS, cs.CC, cs.LG
Related articles: Most relevant | Search more
arXiv:1907.05401 [cs.DS] (Published 2019-07-11)
Computational Concentration of Measure: Optimal Bounds, Reductions, and More
arXiv:1207.0560 [cs.DS] (Published 2012-07-03, updated 2013-08-24)
Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
arXiv:2306.11951 [cs.DS] (Published 2023-06-21)
On the Optimal Bounds for Noisy Computing