Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

Vitaly Feldman, Jan Vondrák

Introduction

Researchers at IBM Research - Almaden have established a significant breakthrough in the structural complexity of submodular and XOS functions. These function classes are foundational to combinatorial optimization, game theory, and machine learning. This work demonstrates that complex submodular functions can be approximated by "juntas"—functions depending on a very small subset of variables—using significantly fewer variables than previously theorized. This shift from exponential to nearly linear variable dependency enables the design of the first efficient learning algorithms for approximating submodular functions within any constant factor.

Problem Statement: The Search for Juntas

In high-dimensional data analysis, functions $f: \{0, 1\}^n \to [0, 1]$ often involve a massive number of inputs ($n$). A core challenge in learning theory is determining if these functions can be approximated using only a small subset of "important" variables, a concept known as a junta.

This research focuses on two primary classes:

  1. Submodular Functions: Characterized by the law of "diminishing returns," where the marginal contribution of an element decreases as the set size increases.
  2. XOS (Fractionally Subadditive) Functions: A broader class frequently used as valuation functions in algorithmic game theory.

Prior to this study, the best-known bounds for submodular function approximation required an exponential number of variables relative to the error rate ($\epsilon$). This paper identifies the optimal number of variables required, facilitating the development of faster machine learning algorithms.

Methodology

The authors utilize a combination of combinatorial optimization and Fourier analysis:

  • Greedy Variable Selection: A novel iterative procedure identifies "influential" variables by measuring their marginal value over random sparse subsets of previously selected variables.
  • Boosting Lemma for Down-Monotone Events: A specialized boosting technique proves that once a critical set of variables is identified, the remaining variables have negligible collective impact.
  • Real-Valued Friedgut’s Theorem: The authors generalize Friedgut’s Theorem—which relates low "influence" to junta proximity—from Boolean outputs to real-valued outputs using $\ell_1$ and $\ell_2$ influences.
  • PMAC Learning Model: The structural results are applied to the "Probably Mostly Approximately Correct" (PMAC) model, focusing on multiplicative approximations (e.g., within a factor of $1+\gamma$) rather than simple additive errors.

Key Insights and Results

A primary discovery is the significant complexity gap between submodular and XOS functions. While submodular functions require only a logarithmic number of variables (relative to the total) for accurate approximation, XOS functions remain exponentially more complex.

The research identifies total $\ell_1$-influence as the optimal metric for generalizing junta theorems to real-valued functions, showing that submodular, XOS, and "self-bounding" functions all exhibit low total $\ell_1$-influence.

Summary of junta size lower and upper bounds for various function classes.

Major Theoretical Contributions:

  • Tight Bounds for Submodular Functions: A submodular function $f$ is $\epsilon$-close to a junta of only $O(\frac{1}{\epsilon^2} \log \frac{1}{\epsilon})$ variables, an exponential improvement over the previous $2^{O(1/\epsilon^2)}$ bound.
  • XOS Hierarchy: XOS functions are $\epsilon$-close to a junta of $2^{O(1/\epsilon^2)}$ variables. The established lower bound of $2^{\Omega(1/\epsilon)}$ confirms their inherent complexity relative to submodular functions.
  • New Learning Algorithms:
    • XOS Functions: A PAC learning algorithm operating in $2^{1/poly(\epsilon)} \cdot poly(n)$ time.
  • Submodular Functions: A PMAC algorithm achieving a $(1+\gamma)$ approximation in $2^{1/poly(\gamma\epsilon)} \cdot poly(n)$ time—the first to provide an arbitrarily good constant approximation for all submodular functions under uniform distributions.

Limitations and Future Directions

Despite these advances, several challenges remain. The multiplicative approximation (PMAC) for submodular functions is currently limited to monotone functions; its applicability to non-monotone functions is an open question. Additionally, most results assume a uniform or product distribution for inputs; extending these tight bounds to general, unknown distributions is a significant hurdle. Finally, there remains a small algorithmic gap: while a junta of size $O(1/\epsilon^2)$ is proven to exist, the current efficient discovery algorithm yields a slightly larger junta of size $O(1/\epsilon^5)$.

Summary updated

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