Abstract
We prove that any submodular function $f: \{0,1\}^n \to \{0,1,\dots,k\}$ can be represented as a pseudo-Boolean $2k$-DNF formula. By generalizing Håstad's switching lemma to pseudo-Boolean $k$-DNFs with bounded constants, we develop a PAC-learning algorithm under the uniform distribution that runs in time polynomial in $n$ and $k^{O(k \log k / \epsilon)}$. This significantly improves upon previous query complexities of $n^{O(k)}$ and enables the construction of an efficient property tester for submodularity.
Introduction
Submodular functions are fundamental to combinatorial optimization, economics, and machine learning, often described as the discrete counterparts to convex functions. They are defined by the property of diminishing returns: the marginal gain of adding an element to a set decreases as the set grows. While submodularity provides significant structure, learning these functions from data is notoriously difficult, typically requiring an exponential number of queries in the general case.
This research addresses a specific but vital class of submodular functions: those with a small, non-negative integer range $\{0, 1, \dots, k\}$. Prior to this work, the best-known algorithms for learning such functions had a query complexity of $n^{O(k)}$, which becomes impractical even for small values of $k$ as the number of variables $n$ increases.
Structural Representation: The Pseudo-Boolean DNF
The primary breakthrough of this paper is a structural theorem linking submodularity to circuit complexity. The authors prove that any submodular function with range $\{0, \dots, k\}$ can be represented as a pseudo-Boolean $2k$-DNF.
In classical Boolean logic, a DNF (Disjunctive Normal Form) is an OR of AND terms. A pseudo-Boolean DNF generalizes this by replacing the OR with a max operator and associating an integer constant with each term. Specifically, the function takes the maximum value among all satisfied terms. The authors show that the "diminishing returns" property of submodularity translates directly into a "width" constraint (the number of variables in each term) of this representation, limiting it to $2k$.
Generalizing Håstad’s Switching Lemma
To translate this structural representation into a learning algorithm, the authors revisit Håstad’s switching lemma. This lemma is a cornerstone of theoretical computer science, stating that a DNF formula simplifies into a shallow decision tree when most of its variables are randomly fixed.
Traditionally, the switching lemma applies only to Boolean (0/1) outputs. The authors successfully generalize this lemma to pseudo-Boolean DNFs. They demonstrate that as long as the constants associated with the terms are bounded, the probability of the function remaining complex after a random restriction is still manageable. This extension is non-trivial, as it requires accounting for the range of the function $k$ in the complexity bounds.
Learning Algorithm and Fourier Concentration
The generalized switching lemma implies Fourier concentration. In the context of Boolean functions, this means that the function's behavior is largely determined by its low-degree Fourier coefficients.
Leveraging this concentration, the authors adapt the Kushilevitz-Mansour algorithm. This algorithm is designed to learn functions with concentrated Fourier spectra under a uniform distribution using membership queries. By focusing on the low-degree coefficients, the algorithm can efficiently approximate the submodular function.
Key Performance Metrics
- Complexity: The algorithm runs in time $n^{O(1)} \cdot k^{O(k \log k / \epsilon)}$.
- Agnostic Learning: The approach works in the agnostic setting, meaning it can find the best submodular approximation even if the target function is not perfectly submodular.
- Efficiency: For a fixed $k$, the complexity is polynomial in $n$, a significant exponential improvement over the previous $n^{O(k)}$ benchmark.
Property Testing
Beyond learning, the paper introduces a property tester for submodularity. This tester can determine if a black-box function is submodular or "far" from submodular. For ranges up to $k = O(\sqrt{\log n / \log \log n})$, the tester requires only a polynomial number of queries in $n$. This provides a practical tool for verifying the structural assumptions often made in optimization tasks.
Conclusion and Future Directions
This work provides a powerful bridge between the structural properties of submodular functions and the tools of circuit complexity and Fourier analysis. While the algorithm is highly efficient regarding the number of variables $n$, its super-exponential dependence on the range $k$ remains a limitation. Future research may explore whether these techniques can be extended to functions with larger ranges or if learning can be achieved under non-uniform distributions.
Summary updated