Is Submodularity Testable?

C. Seshadhri, Jan Vondrák

TL;DR

This paper initiates the formal study of property testing for submodularity on the boolean hypercube. The authors present the first non-trivial, subexponential-time algorithm to detect if a function is "far" from being submodular and prove that providing a "certificate" that a partial function cannot be extended to a submodular one may require an exponentially large number of points.

What Problem Does This Paper Address?

In combinatorial optimization, submodular functions are the "convex functions" of the discrete world. They exhibit a "diminishing returns" property that makes them essential for everything from sensor placement to viral marketing. Most algorithms for these problems assume they have access to an "oracle" that provides submodular values.

But what if the oracle is lying? Or what if the data is noisy?

The authors tackle the challenge of property testing: given a function $f: \{0, 1\}^n \to \mathbb{R}$, can we efficiently distinguish whether $f$ is submodular or "$\epsilon$-far" from submodular (meaning we’d have to change more than an $\epsilon$-fraction of its values to make it submodular)? While testing simpler properties like monotonicity is well-understood, submodularity is globally defined and much harder to verify through local checks.

Methods

The authors focus on a "natural tester" called the Violated Square Tester.

  1. The Local Check: A function is submodular if and only if for every "square" in the hypercube (defined by a point $x$ and two directions $i, j$), the sum of values at the "opposite" corners is less than or equal to the sum of the other two corners: $f(x) + f(x + e_i + e_j) \leq f(x + e_i) + f(x + e_j)$.
  2. The Algorithm: The tester simply samples random squares and checks for violations.
  3. Analytical Tools: To bound the performance, the authors use a mix of combinatorial counting, reduction from monotonicity testing, and Linear Programming (LP) duality (specifically Farkas’ Lemma) to analyze how local violations relate to global distance.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The "data" consists of mathematical constructions of functions on the $n$-dimensional boolean hypercube $\{0, 1\}^n$. The authors introduce several novel "hard" function constructions based on lattices to prove lower bounds on testing efficiency.

Key Insights and Ideas

  • Submodularity as "Second-Degree Monotonicity": The authors observe that submodularity is essentially the monotonicity of marginal values. This allows them to reduce the problem of testing monotonicity to testing submodularity, proving that submodularity testing is at least as hard as monotonicity testing.
  • The "Hiding" Problem: Unlike monotonicity, where a single pair of points can prove a violation, submodularity violations can be "hidden." The authors construct functions that are very far from submodular but contain only a single violated square, suggesting that local testers might struggle.
  • Exponential Certificates: One of the most striking findings is about partial functions. If you are given values for only some points on the hypercube, how many points do you need to prove the function cannot be extended to a submodular one? For many properties, this "certificate" is small. For submodularity, the authors prove it can be $2^{\Omega(n)}$—exponentially large.
  • The Gap: There is a significant gap between the upper bound (subexponential time) and the lower bound (polynomial time). This suggests that while we have the first non-trivial tester, the "optimal" way to test submodularity remains a deep mystery.

Key Results

  • Upper Bound: The authors prove that if a function is $\epsilon$-far from submodular, the density of violated squares is at least $\epsilon^{O(\sqrt{n} \log n)}$. This leads to a subexponential time tester—the first result better than the trivial $2^n$ brute-force check.
  • Lower Bound: They show that for any $\epsilon$, there exist functions that are $\epsilon$-far from submodular but have a violated square density of less than $\epsilon^{4.8}$. This implies that a tester based on random squares cannot be "too" efficient (i.e., it can't just be linear in $1/\epsilon$).
  • Non-Extendability: They prove the existence of a "minimally non-extendable" partial function defined on $2^{\Omega(n)}$ points. Removing even one point from this set makes the function extendable to a submodular one.

Limitations and Future Work

The primary limitation is the massive gap between the subexponential upper bound and the polynomial lower bound. The authors explicitly pose the question: Is there a polynomial-time tester for submodularity?

Future directions include:

  1. Closing the gap between the current bounds.
  2. Investigating adaptive testers (where the next query depends on previous results), which might be more powerful than the non-adaptive random sampling used here.
  3. Testing specific subclasses of submodular functions, such as rank functions of matroids, which are critical in matroid theory.

Summary updated

Abstract

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f:{0,1}^n \rightarrow R. The distance to submodularity is the minimum fraction of values of $f$ that need to be modified to make f submodular. If this distance is more than epsilon > 0, then we say that f is epsilon-far from being submodular. The aim is to have an efficient procedure that, given input f that is epsilon-far from being submodular, certifies that f is not submodular. We analyze a very natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be very efficient in terms of epsilon. This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.
BibTeX
@inproceedings{seshadhri2011is,
  author = {C. Seshadhri and Jan Vondrák},
  title = {{Is Submodularity Testable?}},
  booktitle = {ICS},
  year = {2011},
  url = {https://openreview.net/forum?id=lCImQWKyoMt},
}
Figure