Is submodularity testable?

C. Seshadhri, Jan Vondrák

Abstract

We initiate the study of property testing for submodularity on the boolean hypercube. Submodular functions are fundamental to combinatorial optimization, serving as the discrete analogue of convex functions. While many algorithms assume access to a submodular oracle, verifying this assumption is computationally challenging. We define the distance to submodularity as the minimum fraction of values in a function $f: \{0,1\}^n \rightarrow \mathbb{R}$ that must be modified to make it submodular. This paper presents the first non-trivial tester for submodularity, achieving a subexponential query complexity. Conversely, we establish a lower bound indicating that submodularity is significantly harder to test than simpler properties like monotonicity. Our analysis includes the construction of partial functions that cannot be extended to submodular functions despite appearing locally consistent, highlighting the global nature of submodular constraints.

Introduction

In combinatorial optimization, submodularity is a cornerstone property. A function is submodular if it satisfies the law of diminishing marginal returns: the incremental value of adding an element to a set decreases as the set grows. Formally, for a function $f: 2^V \rightarrow \mathbb{R}$, and for all $S \subseteq T \subseteq V$ and $i \notin T$, $f(S \cup \{i\}) - f(S) \geq f(T \cup \{i\}) - f(T)$.

Many powerful approximation algorithms, such as the greedy algorithm for set cover, rely on the submodularity of the underlying objective function. However, in practice, we often interact with these functions through an oracle. This raises a fundamental question: how can we verify if an oracle truly represents a submodular function? Given the exponential size of the domain ($2^n$), exhaustive verification is impossible. This leads us to the framework of property testing, where we aim to distinguish between functions that are submodular and those that are "far" from submodular by querying only a small fraction of the domain.

The Violated-Square Tester

The authors focus on a natural local check known as the Violated-Square Tester. In the boolean hypercube, a "square" is defined by a point $x$ and two indices $i, j$, consisting of the points $\{x, x+e_i, x+e_j, x+e_i+e_j\}$. A function is submodular if and only if every such square satisfies the marginal return condition: $$f(x+e_i) - f(x) \geq f(x+e_i+e_j) - f(x+e_j)$$

If a square fails this condition, it is a "violated square." The proposed tester operates by sampling random squares from the hypercube. If it detects a single violation, it rejects the function; otherwise, it accepts. The core of the theoretical challenge lies in bounding the relationship between the fraction of points that must be changed to fix the function (the distance to submodularity) and the density of these violated squares.

Key Insights: Submodularity vs. Monotonicity

A major contribution of this work is the realization that submodularity is fundamentally more complex than monotonicity. While monotonicity is a "first-order" property (dealing with whether a function is increasing), submodularity is a "second-order" property (dealing with the monotonicity of the derivatives).

The "Hidden Violation" Phenomenon

The authors demonstrate that submodularity can "hide" its violations. In many properties, being far from the property implies the existence of many local violations. However, the authors construct a function that is $\epsilon$-far from submodular—requiring $2^{n/2}$ changes to correct—yet contains only a single violated square in the entire hypercube. This suggests that a local tester might need a very high number of queries to find the "needle in the haystack."

Exponential Certificates

For properties like monotonicity, if a partial function cannot be extended to a full monotonic function, there exists a small "certificate" (often just two points) proving the violation. This paper proves that for submodularity, the smallest certificate of non-extendability can be exponentially large. They construct a partial function defined on $2^{\Omega(n)}$ points that cannot be extended to a submodular function, yet any proper subset of these points can be extended. This indicates that submodularity is a global property that cannot always be captured by local observations.

Results and Complexity

The paper provides two primary bounds on the query complexity of testing submodularity:

  1. Upper Bound: The authors prove the first non-trivial upper bound, showing that submodularity can be tested using $1/\epsilon^{O(\sqrt{n} \log n)}$ queries. While this is subexponential, it represents a significant improvement over the trivial $2^n$ brute-force approach.
  2. Lower Bound: They establish a lower bound of $1/\epsilon^{4.8}$ for any tester based on local squares. This confirms that submodularity is strictly harder to test than monotonicity, which typically requires only $O(n/\epsilon)$ queries.

Furthermore, the authors provide a formal reduction showing that testing submodularity is at least as hard as testing monotonicity, cementing its place as a more difficult class of property testing.

Conclusion and Future Directions

This research initiates the formal study of submodularity testing and provides the first mathematical tools to analyze the density of violations in the hypercube. While the gap between the subexponential upper bound and the polynomial lower bound remains large, the work highlights the unique structural difficulties of submodularity.

Future research may focus on closing this gap, potentially by exploring adaptive testers that can "search" for violations more intelligently than random sampling. Additionally, investigating whether specific subclasses of submodular functions, such as matroid rank functions, are easier to test remains an open and promising area of study.

Summary updated

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