Learning pseudo-Boolean k-DNF and submodular functions

Sofya Raskhodnikova, Grigory Yaroslavtsev

TL;DR

This paper provides a breakthrough in learning submodular functions with small integer ranges by proving they can be represented as "pseudo-Boolean" DNF formulas. By generalizing Håstad’s switching lemma to this new setting, the authors develop a PAC-learning algorithm and a property tester that are significantly more efficient than previous methods for functions with discrete, bounded outputs.

What Problem Does This Paper Address?

Submodular functions are the "convex functions" of the discrete world, characterized by the property of diminishing returns: adding an element to a small set increases the function value more than adding it to a larger set. They are foundational in economics, game theory, and combinatorial optimization.

However, learning these functions from data is notoriously difficult. General submodular functions require an exponential number of queries to learn. Previous research often settled for coarse approximations or specific, limited distributions. This paper tackles a specific but important subclass: submodular functions where the output is a non-negative integer bounded by some value $k$ (i.e., $f: \{0, 1\}^n \to \{0, 1, \dots, k\}$). The challenge was to find a learning algorithm whose complexity doesn't explode as the number of variables $n$ grows, even if it depends heavily on the range $k$.

Methods

The authors bridge the gap between structural complexity and computational learning theory using three main pillars:

  1. Structural Representation: They prove a new structural theorem: every submodular function with range $\{0, \dots, k\}$ can be represented as a pseudo-Boolean $2k$-DNF. While a standard DNF uses OR gates, a pseudo-Boolean DNF uses a max operator over terms, where each term has an associated integer constant.
  2. Generalized Switching Lemma: A cornerstone of circuit complexity is Håstad’s switching lemma, which says that if you randomly fix most variables in a DNF, the remaining function simplifies into a shallow decision tree. The authors successfully generalize this lemma to handle pseudo-Boolean DNFs with bounded constants.
  3. Fourier Analysis & Learning: The switching lemma implies "Fourier concentration"—meaning the function's behavior is mostly captured by its low-degree Fourier coefficients. This allows the authors to adapt the Kushilevitz-Mansour algorithm, a classic tool for learning functions with concentrated Fourier spectra, to learn these submodular functions under a uniform distribution.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The results are proven mathematically for the entire class of submodular functions with the specified range.

Key Insights and Ideas

  • The DNF Connection: The most surprising insight is that the "diminishing returns" property of submodularity translates directly into a "width" constraint on a DNF-like representation. Specifically, a range of $k$ implies a width of $2k$.
  • Constants Don't Break the Lemma: Traditionally, switching lemmas are for Boolean (0/1) outputs. The authors showed that as long as the constants in the pseudo-Boolean DNF are bounded, the probability of the function remaining "complex" after random restriction only increases by a factor related to the range $r$, which is manageable.
  • Agnostic Learning: Because the algorithm relies on Fourier concentration, it naturally extends to the agnostic setting. This means the algorithm still performs well even if the target function isn't perfectly submodular, finding the "closest" submodular hypothesis.

Key Results

  • Learning Complexity: The proposed PAC-learning algorithm runs in time polynomial in $n$ (the number of variables). Specifically, the complexity is $n^{O(1)} \cdot k^{O(k \log k / \epsilon)}$.
  • Improvement over Prior Work: Previous best-known bounds for this setting had a query complexity of $n^{O(k)}$. For a fixed $k$, the new algorithm is exponentially faster with respect to $n$.
  • Property Testing: The paper derives the first property tester for submodularity that uses a number of queries polynomial in $n$ for ranges up to $k = O(\sqrt{\log n / \log \log n})$. This allows researchers to quickly check if a black-box function is "close" to being submodular.

Limitations and Future Work

  • Dependence on $k$: While the algorithm is efficient in $n$, it is super-exponential in the range $k$. If $k$ is large (e.g., $k \approx n$), the algorithm becomes computationally infeasible.
  • Uniform Distribution: The PAC-learning results assume that the input examples are drawn from a uniform distribution. Learning under arbitrary or "product" distributions remains a more difficult challenge.
  • Range Constraints: The structural result specifically requires a discrete, bounded integer range. Extending these insights to continuous submodular functions or those with very large ranges would require different techniques.

Summary updated

Abstract

We prove that any submodular function f: {0,1}^n -> {0,1,...,k} can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Hastad's switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f:{0,1}^n -> {0,1,...,k}. Our algorithm runs in time polynomial in n, k^{O(k \log k / \epsilon)}, 1/\epsilon and log(1/\delta) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC '11), Gupta, Hardt, Roth, Ullman (STOC '11), Cheraghchi, Klivans, Kothari, Lee (SODA '12)] implies only n^{O(k)} query complexity for learning submodular functions in this setting, for fixed epsilon and delta. Our learning algorithm implies a property tester for submodularity of functions f:{0,1}^n -> {0, ..., k} with query complexity polynomial in n for k=O((\log n/ \loglog n)^{1/2}) and constant proximity parameter \epsilon.
BibTeX
@inproceedings{raskhodnikova2013learning,
  author = {Sofya Raskhodnikova and Grigory Yaroslavtsev},
  title = {{Learning pseudo-Boolean k-DNF and submodular functions}},
  booktitle = {SODA},
  year = {2013},
  url = {https://openreview.net/forum?id=MfnvBXsUdh},
}

Loading related content...

Figure