Tight Bounds on $\ell_1$ Approximation and Learning of Self-Bounding Functions

Understand

We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube ${0,1}^n$.

• Informally, a function $f:{0,1}^n \rightarrow \mathbb{R}$ is self-bounding if for every $x \in {0,1}^n$, $f(x)$ upper bounds the sum of all the $n$ marginal decreases in the value of the function at $x$.
• Self-bounding functions include such well-known classes of functions as submodular and fractionally-subadditive (XOS) functions.
• They were introduced by Boucheron et al.