Abstract 1 Introduction 2 Preliminaries 3 Junta approximation of 𝒌–submodular functions 4 Towards testing 𝒌–submodularity in the ℓ𝟎-norm References

Testing k-Submodularity

Themistoklis Haris ORCID Department of Computer Science, Boston University, MA, USA    Diptaksho Palit ORCID Department of Computer Science, Boston University, MA, USA
Abstract

We initiate the study of property testing for k–submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While k–submodularity retains the diminishing-returns flavor of ordinary submodularity, it also introduces a pairwise monotonicity constraint comparing competing assignments of the same element. This additional local structure makes the testing problem qualitatively different from the classical case.

Our results show a sharp contrast between distance regimes. In the ℓp regime for p≥1, we prove that every bounded k–submodular function is close to a junta on the hypergrid. Combined with an implicit-learning tester for hypergrid domains, this yields a constant-query tester for k–submodularity. In the Hamming distance regime, k–submodularity admits two qualitatively different local witnesses – violated squares for diminishing marginal gains, and violated triangles for pairwise-monotonicity failures – and the latter has no counterpart at k=1. We prove density theorems for both witness types via repair on filters and ideals of partial partitions, yielding non-adaptive, one-sided sub-exponential-query testers for the two component properties of k–submodularity. We then exhibit a configuration in which the two repair directions are forced into opposition on a shared vertex, identifying a structural barrier to combining these into a tester for the full property.

Finally, for bounded-range functions, we give an adaptive tester for monotone k–submodularity via a pseudo-DNF representation and learning on the hypergrid. Several of the structural and learning tools developed here may be useful for testing other properties over product domains.

Keywords and phrases:
property testing, sublinear algorithms, submodular functions
Category:
RANDOM
Funding:
Diptaksho Palit: Supported by the U.S. National Science Foundation under Grant No. 2022446.
Copyright and License:
[Uncaptioned image] © Themistoklis Haris and Diptaksho Palit; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Streaming, sublinear and near linear time algorithms
Related Version:
Full Version: https://arxiv.org/pdf/2606.30433 [9]
Acknowledgements:
T.H. worked on k-submodularity testing as a final project for the 2024 Sublinear Algorithms course taught by Ronitt Rubinfeld. T.H. and D.P. started working on this project for a course on Sublinear Algorithms taught by Sofya Raskhodnikova [14]. We thank Fabian Spaeh for inspiring us to investigate this question through his work on k-submodular optimization.
Editors:
Mohit Singh and Tom Gur

1 Introduction

Submodularity is one of the canonical examples of a global property with a simple local interpretation. A set function is submodular when it satisfies the principle of diminishing marginal returns: the incremental value of adding an element can only decrease as the set to which it is added grows. Formally, a set function f:2[n]→ℝ is said to be submodular if, for all subsets X,Y⊆[n], it satisfies the inequality:

f⁢(X)+f⁢(Y)≥f⁢(X∩Y)+f⁢(X∪Y).

This local-to-global nature makes submodularity a natural target for property testing [8], where one is given oracle access to an unknown function and must distinguish functions satisfying a property from those that are far from satisfying it. Yet even for ordinary submodularity, the query complexity of testing remains poorly understood. Seshadhri and Vondrák [16] gave a tester using roughly (1/ε)n queries and proved a linear lower bound; the latter was later improved to a nearly quadratic lower bound by Hatami and Vondrák [10]. The resulting exponential gap has remained open, and has motivated the study of more structured regimes, such as bounded-range submodular functions [15] and testing under ℓp distance rather than Hamming distance [1].

In this work we ask what happens to this picture for a higher-dimensional analogue of submodularity. For a fixed integer k≥1, a point in [k+1]n can be viewed as a partial partition of the ground set [n]: each element is either assigned to one of k parts, or left unassigned. A function on these partial partitions is k–submodular if marginal gains diminish no matter which part an element is assigned to. The case k=1 is ordinary submodularity, while already for k=2 the domain has multiple incompatible directions in which a single element may be added. This function class has been studied extensively in optimization [12, 4], with applications including tensor placement [12] and online ad allocation [5].

From a testing perspective, k–submodularity is not merely submodularity on a larger domain. A useful characterization, due to Ward and Živný [17], decomposes k–submodularity into two conditions. The first is diminishing marginal gains, which generalizes the familiar submodular inequality inside each direction of the hypergrid. The second is pairwise monotonicity, a constraint comparing the marginal gains of assigning the same element to two different parts. One way to understand this decomposition is to separate two kinds of local interactions. When two partial partitions make compatible choices, k–submodularity behaves like ordinary diminishing returns along the corresponding direction. When they make incompatible choices for the same element, the join operation discards that element from both parts; the resulting inequality says that assigning the element to two different parts cannot have two strongly negative marginal gains at the same time. This second condition has no analogue when k=1, and it is the source of much of the new combinatorial structure in the testing problem.

We initiate the study of testing k–submodularity. Our results show a sharp contrast between two distance regimes. In the ℓp regime, analytic structure survives the passage from the Boolean hypercube to the hypergrid: we prove a junta-approximation theorem for k–submodular functions and combine it with an implicit-learning tester on hypergrids. In the Hamming distance regime, the local structure fragments: we obtain testers for the two local constraints by developing square and triangle witness structures, and show that their repair procedures expose a genuine obstruction to the standard local-repair paradigm for full k–submodularity. Along the way, we develop testing and learning tools for hypergrid domains that may be useful beyond this problem.

1.1 Our Results

We organize our contributions around three questions. First, does the analytic structure that makes submodularity testable in ℓp distance survive on the richer domain of partial partitions? Second, in the Hamming distance regime, can the local-violation framework for submodularity be adapted to the two distinct constraints that characterize k–submodularity? Third, can bounded range assumptions recover efficient testability for a meaningful subclass of k–submodular functions?

ℓ𝒑 testing from hypergrid junta structure

Our first result is a constant-query tester for k–submodularity in ℓp distance. Here and throughout this section, constant means independent of the ambient dimension n.

Theorem 1.

For all p≥1, there exists an adaptive, one-sided error ℓp-tester for k-submodularity making q=(pε)2⋅2(pε)2⁢log⁡(pε) queries.

The main structural input is not a black-box reduction to the submodular case. We prove that every bounded k–submodular function is close to a function depending on only a small number of coordinates, even though each coordinate can move in k competing directions. This requires choosing influential coordinates in a way that respects all parts of a partial partition, and uses the fact that k–submodular functions satisfy a self-bounding variance inequality.

Theorem 2.

Let f:[k+1]J→[0,1] be a k–submodular function and ε>0 be a small enough constant. Then there exists a k–submodular function h:[k+1]J→[0,1] that depends only on J′⊆J dimensions, where

|J′|=O⁢(1ε2⋅log⁡1ε),

and the function h satisfies

∥f−h∥2≤ε.

We then develop the testing component needed to turn this structure into an algorithm. The implicit-learning framework of Blais and Bommireddi [1] relies on identifying influential coordinates and checking consistency with a small junta. We formulate and analyze this framework on hypergrid domains using Fourier analysis over generalized product spaces, and simplify parts of the original argument by separating the learning and final testing samples.

Theorem 3.

Let p≥1. Suppose 𝒫⊆{f:[k+1]n→[0,1]} is a property of functions such that for any f∈𝒫 there exists a κ-junta h:[k+1]n→[0,1] satisfying ‖f−h‖2≤ε. Then, there exists a tester that, given query access to an unknown function f, will make ε−9⋅2O⁢(κ⁢log⁡κ) queries to f and with probability at least 2/3 accept if f∈𝒫 and reject if f is ε-far from 𝒫 in the ℓ2 norm.

Local testing in Hamming distance

Our second set of results addresses the Hamming-distance regime, where the Seshadhri–Vondrák local-repair paradigm for ordinary submodularity does not extend directly. Pairwise monotonicity is vacuous when k=1, but on the hypergrid its violations form a new witness shape – triangles – incomparable with the squares that witness diminishing-marginal-gain failures. Repair likewise shifts from Boolean subcubes to filters and ideals of partial partitions, and the density arguments must be re-proved in this setting. We obtain non-adaptive, one-sided testers for the two component properties of k–submodularity:

Theorem 4.

Let f:[k+1]n→ℝ be given via oracle access. There exist non-adaptive, one-sided error testers for the diminishing marginal gains and pairwise monotonicity properties with the following guarantees:

  • ■

    If f satisfies the property, the tester accepts with probability 1.

  • ■

    If f is ε-far from the property (i.e., at least ε⋅[k+1]n values must be modified to satisfy it), the tester rejects with probability at least 2/3.

The tester for diminishing marginal gains makes q=4⁢n2⋅(1/ε)Θ⁢(n⁢log⁡n) queries; the tester for pairwise monotonicity makes q=3⁢k⁢n⋅(1/ε)Θ⁢(n⁢log⁡n) queries.

Notably, only the pairwise-monotonicity tester has query complexity depending on k, despite k governing the structure of the domain.

Combined, these results expose a structural difference between k–submodularity and ordinary submodularity that the analytic (ℓp) regime does not see. In Section 4.3 we exhibit an explicit configuration (Figure 1) on a high item-weight filter in which repairing a triangle violation forces value changes in the opposite direction from those needed to repair an overlapping square violation, on a shared vertex. The two repair directions are not merely incompatible at one point – they are jointly inconsistent across an entire region. We record this as Observation 32: it rules out the natural component-wise extension of local repair to full k–submodularity, and isolates a concrete barrier that any sub-exponential local-witness tester must overcome by enlarging the witness vocabulary beyond squares and triangles.

Bounded range and monotone 𝒌–submodularity

Finally, we show that efficient Hamming-distance testing can be recovered for monotone k–submodular functions with bounded range. The result is again obtained through learning, but the relevant representation is no longer a junta. Instead, we utilize pseudo-DNF representations for functions on the hypergrid and prove that bounded-range monotone k–submodular functions have bounded-width pseudo-DNFs.

Theorem 5.

Let ε,δ∈(0,1) be constants. There exists a tester 𝒯 which, given query access to a function f:[k+1]n→{0,1,⋯,r} satisfies the following.

  1. 1.

    If f is monotone k–submodular, then 𝒯 accepts with probability ≥1−δ.

  2. 2.

    If f is ε-far from monotone k–submodularity, then 𝒯 rejects with probability ≥1−δ.

  3. 3.

    𝒯 makes at most poly⁢(n,1/ε,1/δ,(k⁢r)O⁢(r⁢k2⁢log⁡(r/ε))) queries.

The learning result for bounded-width pseudo-DNFs uses a hypergrid version of the switching-lemma/Fourier-sparsity route and yields a tester via the Kushilevitz-Mansour algorithm. We expect this learner to be useful beyond k–submodularity.

1.2 Prior Work

Testing whether a given function is submodular was first examined by Parnas, Ron and Rubinfeld [13], who studied the limited setting of testing for a class of matrices called Monge matrices. In its full generality, the problem was considered by Seshadhri and Vondrák [16]. They developed the local-witness and repair framework for Hamming-distance testing on the Boolean hypercube, proving an upper bound of (1/ε)O⁢(n⁢log⁡n) and a linear lower bound. The latter was later improved to Ω⁢(n2/log⁡n) by Hatami and Vondrák [10]. Blais and Bommireddi [1] subsequently studied the problem in the ℓp norm, and using an approximation result from [6], designed an implicit-learning tester with constant query complexity in the input length. Raskhodnikova and Yaroslavtsev [15] studied bounded-range submodular functions through a learning-based approach and proved a polynomial-time upper bound in this regime. Chakrabarty and Huang [3] studied the problem of testing for coverage functions, which are a special type of submodular function.

Our work is informed most directly by the three submodularity-testing frameworks of Seshadhri and Vondrák [16], Blais and Bommireddi [1], and Raskhodnikova and Yaroslavtsev [15]. These works provide the conceptual starting points for the three regimes we study. The passage to k–submodularity introduces new difficulties in each case: local witnesses split into squares and triangles in the Hamming regime, influential coordinates must account for competing assignments in the ℓp regime, and bounded-range learning requires representations over the hypergrid rather than the Boolean cube.

To our knowledge, there is no prior work on testing k-submodularity, though the property has been studied extensively from the optimization perspective [12, 4]. We also use the structural characterization of Ward and Živný [17], which identifies k–submodularity with the conjunction of diminishing marginal gains and pairwise monotonicity.

1.3 Technical Overview

The main technical theme is that the hypergrid introduces several inequivalent notions of locality. In the ℓp regime, locality is analytic and is captured by influential coordinates. In the Hamming regime, locality is combinatorial and is captured by small violated configurations. For bounded-range functions, locality appears through compact symbolic representations. In each part of the paper we develop the corresponding notion of locality for partial partitions.

The analytic regime: finding the right influential coordinates

The ℓp tester has two ingredients: a junta-approximation theorem for k–submodular functions, and a tester for properties that are close to juntas on the hypergrid. The obstacle in the first ingredient is that a coordinate has k possible nonzero directions. Several natural ways of declaring a coordinate influential in one part at a time almost work, but fail to interact correctly with the boosting lemma for down-monotone families (Lemma 12).

Our solution is to define the relevant influence threshold by looking across all partitions of the remaining coordinates. This lets the selection rule remain compatible with the combinatorial boosting argument while still respecting the multi-directional nature of the domain. The second key input is a variance bound: we prove that k–submodular functions are 2-self bounding (Lemma 14). Together, these ingredients yield a junta depending on only O⁢(ε−2⁢log⁡(1/ε)) coordinates.

Once the junta structure is established, the testing step is conceptually separate. We analyze implicit learning directly on [k+1]n using Fourier analysis over product domains. The tester identifies a candidate set of influential coordinates and then checks whether the observed behavior is consistent with a junta from the target property. Using an independent sample in the final testing stage also simplifies the decorrelation issues that arise in the original Boolean-domain analysis of [1].

The Hamming regime: local witnesses and repair

In Hamming distance, a tester needs many local witnesses whenever the function is far from the property. For ordinary submodularity, the relevant witness is a violated square in the Boolean hypercube, and the analysis of Seshadhri and Vondrák [16] shows that few violated squares imply a global repair.

For k–submodularity, a single witness shape is no longer sufficient. Using the characterization of Ward and Živný [17], we separate the property into diminishing marginal gains and pairwise monotonicity. Diminishing marginal gains is witnessed by generalized violated squares, while pairwise monotonicity is witnessed by violated triangles. We prove density statements for both witnesses by designing repair procedures on large inclusion-closed regions of the hypergrid: ideals {Y⪯X} and filters {Y⪰X}. This gives sub-exponential testers for the two component properties.

The same repair viewpoint also yields a structural observation about the full Hamming-distance problem (Observation 32, illustrated in Figure 1). On high item-weight filters, the repair direction needed for a violated square is forced into conflict with the repair direction needed for an overlapping violated triangle on a shared vertex. This is not a limitation of our proof – it is a structural property of the problem: any tester built on the squares-and-triangles vocabulary, no matter how the repair is organized, must encounter a configuration of this kind. A sub-exponential tester for full k–submodularity in Hamming distance therefore requires an enriched witness vocabulary, not merely a more clever combination of square and triangle repairs.

The bounded-range regime: representation before testing

For bounded-range monotone k–submodular functions, we take a representation-theoretic route. We first show that such functions admit bounded-width pseudo-DNF representations over the hypergrid. This representation captures the monotone threshold-like structure imposed jointly by bounded range and diminishing marginal gains.

We then prove a hypergrid switching lemma for pseudo-DNFs, using low-depth k-ary decision trees in place of binary trees. Combined with Fourier analysis on the hypergrid, this implies sparse Fourier approximation for bounded-width pseudo-DNFs. The resulting learner, together with the Kushilevitz-Mansour algorithm [11], yields the bounded-range tester.

1.4 Discussion and Open Problems

Our results leave several natural questions open. The most immediate is whether full k–submodularity can be tested in Hamming distance with sub-exponential query complexity. Our component testers for diminishing marginal gains and pairwise monotonicity show that each constraint has many local witnesses when violated, but the repair procedures for the two constraints can be forced to conflict. Resolving this – either by exhibiting a richer witness family with a compatible repair procedure, or by proving a sub-exponential lower bound that confirms the barrier is fundamental – is, in our view, the right next step in this regime.

A second direction is to understand the bounded-range setting without monotonicity. Our tester in this regime relies on a pseudo-DNF representation for monotone k–submodular functions, and it is unclear whether a comparable representation exists for non-monotone functions.

Finally, it would be interesting to prove lower bounds for testing k–submodularity. The known lower bounds for submodularity do not transfer directly, since natural embeddings can destroy pairwise monotonicity. Thus even formulating the right hard instances appears to require using the genuinely multi-part structure of the domain.

1.5 Organization

The paper is organized as follows. In Section 2, we formally define the problem and related structures on the hypergrid. In Section 3, we prove the junta approximability theorem for k–submodular functions. In Section 4, we develop Hamming-distance testers for diminishing marginal gains and pairwise monotonicity, and analyze the obstruction to combining their repairs into a local-repair tester for full k–submodularity. We refer to the full version of the paper [9] for the analysis of the hypergrid implicit-learning theorem and construction of our ℓ0 tester for monotone k–submodularity in the bounded range regime.

2 Preliminaries

Definition 6 (Partial partition).

A partial partition of [n] into k subsets is defined X=(X1,…,Xk), where each Xi⊆[n] and Xi∩Xj=∅ for all i≠j∈[k]. We let Xk+1=[n]∖∪i=1kXi, and this allows us to associate partial partitions of [n] into k subsets with the hypergrid [k+1]n (each element of [n] is associated to a bucket in [k+1], yielding a vector in [k+1]n). If e∉Xk+1, we say that e∈X. We impose a partial order on partial partitions by defining X⪯Y if and only if Xi⊆Yi for all i∈[k]. We let |X| denote the item-weight of a partial partition, which is the total number of items picked. Numerically, this is equal to ∑i=1k|Xi|.

Definition 7 (Marginal gains).

Define the marginal gains of a function f on a partial partition X with respect to an index i∈[k] and an element e∈Xk+1 as

Δf⁢(X,i,e):=f⁢(X1,…,Xi∪{e},…,Xk)−f⁢(X).

Letting Xei:=(X1,…,Xi∪{e},…,Xk), we can rewrite this as Δf⁢(X,i,e)=f⁢(Xei)−f⁢(X).

Definition 8 (k–submodularity).

A function f:[k+1]n→ℝ is k–submodular if, for all partial partitions X,Y, the following holds.

f⁢(X)+f⁢(Y)≥f⁢(X⊔Y)+f⁢(X⊓Y),

where X⊓Y:=(X1∩Y1,⋯,Xk∩Yk) and

X⊔Y=((X1∪Y1)∖⋃i≠1(Xi∪Yi),⋯,(Xk∪Yk)∖⋃i≠k(Xi∪Yi)).

The following theorem of Ward and Živnỳ [17] gives us an equivalent definition of k–submodularity, one that is described by two more intuitive properties. The intuition is that every local comparison between two partial partitions can be decomposed into compatible and conflicting moves. Compatible moves are governed by the usual diminishing-returns principle: adding an unassigned element to part i becomes less valuable as the current partial partition grows. Conflicting moves arise only when the same element could be assigned to two different parts. For example, comparing Xei and Xej gives Xei⊓Xej=X and Xei⊔Xej=X, so the k–submodular inequality becomes

Δf⁢(X,i,e)+Δf⁢(X,j,e)≥0.

Thus pairwise monotonicity is the local condition that prevents two competing assignments of the same element from both being too costly.

Theorem 9 ([17]).

A function f:[k+1]n→ℝ is k–submodular if and only if the following two conditions hold.

  • ■

    Diminishing marginal gains. For all partial partitions X,Y such that X⪯Y, e∉Y, and i∈[k], the following holds.

    Δf⁢(X,i,e)≥Δf⁢(Y,i,e).
  • ■

    Pairwise monotonicity. For all partial partitions X, e∉X, and i≠j∈[k], the following holds.

    Δf⁢(X,i,e)+Δf⁢(X,j,e)≥0.

3 Junta approximation of 𝒌–submodular functions

In the following two sections, we prove the structural and algorithmic ingredients behind our ℓp tester for k–submodularity. The structural ingredient is a junta approximation theorem for k–submodular functions on the hypergrid. The main difficulty is choosing influential coordinates in a way that accounts for all k directions of a coordinate while still giving a dimension-independent approximation.

This approximation theorem, combined with an implicit learning tester for properties on hypergrids with a good junta approximation, yields the desired tester.

We prove the following approximation theorem.

Theorem 10 (Reminder of Theorem 2).

Let f:[k+1]J→[0,1] be a k–submodular function and ε>0 be a small enough constant. Then there exists a k–submodular function h:[k+1]J→[0,1] that depends only on J′⊆J dimensions, where

|J′|=O⁢(1ε2⋅log⁡1ε),

and the functions h satisfies

∥f−h∥2≤ε.

Before we get to the proof of Theorem 2, we first set up some necessary machinery.

3.1 Setup

There are three main parts to the setup.

Boosting lemma.

We cite the following boosting lemma due Goemans and Vondrák [7].

Definition 11 (Down-monotone family).

Let X be a finite set and ℱ⊆2X be a collection of subsets of X. The family ℱ is called down-monotone if the following condition holds.

A∈ℱ∧B⊆A⟹B∈ℱ.
Lemma 12 ([7] Boosting lemma).

Let X be a finite set and ℱ⊆2X be a down-monotone family. For p∈(0,1), define

σp:=Pr⁡[X⁢(p)∈ℱ],

where X⁢(p) is a random subset of X such that each element is picked independently with probability p. Then

σp=(1−p)ϕ⁢(p),

where ϕ⁢(p) is a non-decreasing function for p∈(0,1).

Self–bounding functions and concentration.

A very useful tool in bounding the variance of submodular functions comes from the literature of concentration for self–bounding functions.

Definition 13 (Self–bounding function).

A function f:𝒳n→[0,1] is 𝛂-self–bounding if there exist functions fi:𝒳n−1→[0,1] such that for all x1,⋯,xn∈𝒳 and all i∈[n], the following conditions hold.

  1. 1.

    0≤f⁢(x1,⋯,xn)−fi⁢(x1,⋯,xi−1,xi+1,⋯,xn)≤1; and

  2. 2.

    ∑i=1n(f⁢(x1,…,xn)−fi⁢(x1,x2,…,xi−1,xi+1,…,xn))≤α⁢f⁢(x1,…,xn).

Lemma 14 ([2] Bounded variance lemma).

If a function f:𝒳n→[0,1] is α-self–bounding then

Var⁢[f⁢(X)]≤α⋅𝔼⁢[f⁢(X)].
Bounded variance of 𝒌–submodular functions.

Submodular functions that are Lipschitz are self–bounding, which allows us to bound their variance. We show that a similar property holds for k–submodular functions.

Definition 15 (Lipschitz function).

A function f:[k+1]n→[0,1] is α-Lipschitz if |Δf⁢(X,j,i)|≤α for all i∈[n] and j∈[k].

Lemma 16.

Let f:[k+1]n→[0,1] be 1–Lipschitz and k–submodular. Then:

Var⁢[f]≤2⋅𝔼⁢[f].
Proof.

We prove this by showing that f is 2-self–bounding, and invoking Lemma 14. For i∈[n], define the function fi as

fi⁢(x1,⋯,xi−1,xi+1,⋯⁢xn):=minj∈[k+1]⁡{f⁢(x1,⋯,xi−1,j,xi+1,xn)}.

Then the first condition

0≤f⁢(x1,…,xn)−fi⁢(x1,…,xi−1,xi+1,…,xn)≤1

holds trivially (by choice of minimum value and the range of f being [0,1]). By pairwise monotonicity of f, the following holds.

f⁢(x1,…,xn) −fi⁢(x1,…,xi−1,xi+1,…,xn)
≤2⋅(f⁢(x1,…,xn)−f⁢(x1,…,xi−1,k+1,xi+1,…,xn)).

Here, xi=k+1 corresponds to item i not being put into any bucket. Finally, the following holds for all i∈[n] due to the marginal gains property.

f⁢(x1,…,xn)−f⁢(x1,…,xi−1,k+1,xi+1,…,xn)
≤f⁢(x1,⋯,xi,k+1,⋯,k+1)−f⁢(x1,⋯,xi−1,k+1,⋯,k+1).

This yields the desired condition.

∑i=1n(f(x1,⋯,xn) −fi(x1,⋯,xi−1,xi+1,⋯,xn))
≤∑i=1n2⋅((f(x1,⋯,xn)−f(x1,⋯,xi−1,k+1,xi+1,⋯,xn))
≤∑i=1n2⋅(f⁢(x1,⋯,xi,k+1,⋯)−f⁢(x1,⋯,xi−1,k+1,⋯))
≤2⋅f⁢(x1,⋯,xn).

We have thus shown that f is 2-self–bounding, and by Lemma 16, Var⁢[f]≤2⋅𝔼⁢[f]. ◀

3.2 Weak junta approximation

We first prove the following “weak” junta approximation for k–submodular functions.

Theorem 17 (Weak junta approximation).

Let f:[k+1]J→[0,1] be a k–submodular function and ε∈(0,1) be a constant. Then there exists a k–submodular function h:[k+1]J→[0,1] that depends only on J′⊆J dimensions, where

|J′|≤32ε2⋅log⁡8⁢|J|ε2,

and the function h satisfies

∥f−h∥2:=(𝔼x∈[k+1]J⁢[(f⁢(x)−h⁢(x))2])12≤12⋅ε.

We prove Theorem 17 by first describing a procedure to construct the set J′ and then showing that there exists a J′-junta satisfying the desired properties.

Let S⊆J and P:J→[k+1]n be some partition function over J. We denote by SP the point on the hypergrid obtained by placing each i∈S into bucket P⁢(i). We denote by S⁢(δ)P a random set generated by sampling each element in S independently with probability δ.

Algorithm 1 Identifying the junta set J′.

First we show that the number of indices picked by Algorithm 1 is small.

Claim 18.

The set J′ output by Algorithm 1 satisfies |J′|≤2α⁢δ.

Proof.

Let P be an arbitrary partition of J, and X be an arbitrary subset of J. For any i∈X, let X<i denote the set of items in X that were added to S before i in Algorithm 1. Define

XP+:={i∈X∣Δf⁢(X<i,P,P⁢(i),i)>α}.

Then by diminishing marginal gains, at the end of the execution of Algorithm 1, we have

𝔼⁢[f⁢(S⁢(δ)P+)] =f⁢(∅)+∑i∈S⁢(δ)P+Δf⁢(S⁢(δ)<i,P+,P⁢(i),i)
>𝔼⁢[|S⁢(δ)P+|]⋅α. [Assuming ⁢f⁢(∅)=0⁢ WLOG]

Next, we show that 𝔼⁢[|S⁢(δ)P+|]≥δ⋅|S|2. If that is true, then

1≥𝔼⁢[f⁢(S⁢(δ)P+)]>δ⋅|S|⋅α2⟹|S|≤2δ⁢α.

To prove our claim, we observe that by construction, for all u∈S,

Pr⁡[u∈S⁢(δ)P+]=Pr⁡[u∈S⁢(δ)]⋅Pr⁡[Δf⁢(S⁢(δ)<u,P,P⁢(u),u)>α]>δ2.

Writing |S⁢(δ)P+|=∑u∈SXu, where Xu is the indicator for whether u∈S⁢(δ)P+, we get

𝔼⁢[|S⁢(δ)P+|]=∑u∈SPr⁡[Xu]≥δ⋅|S|2.

⊲

Next, we show that for all partitions P and any “unimportant” coordinate i∈J∖J′, the probability of the marginal gains on top of J′ being large with respect to P when adding i to P⁢(i) is very small if we sample elements from J′ with probability kk+1 rather than δ.

Claim 19.

For all i∈J∖J′, all j∈[k], and all partitions P:J′→[k], the following holds.

PrJ′⁢(kk+1)⁡[Δf⁢(J′⁢(kk+1)P,j,i)>α]≤(1k+1)12⁢δ.
Proof.

Consider the following family of points

ℱ={X∈[k+1]n∣X⪯JP′⁢ and ⁢Δf⁢(X,j,i)>α}

This is a down-monotone set – if Y⪯X∈ℱ then Y∈ℱ. This is due to diminishing marginal gains – Δf⁢(Y,j,i)≥Δ⁢(X,j,i). If we let σp:=Pr⁡[J′⁢(p)P∈ℱ] for p∈(0,1), then by Lemma 12,

σp=(1−p)ϕ⁢(p),

for some non-decreasing function ϕ. The termination condition of Algorithm 1 guarantees that

σδ:=Pr⁡[J′⁢(δ)P∈ℱ]=(1−δ)ϕ⁢(δ)≤12,

which implies ϕ⁢(δ)≥12⁢δ for δ≤12. Since ϕ is non-decreasing, we have

ϕ⁢(kk+1) ≥ϕ⁢(δ)≥12⁢δ⟹
σkk+1 =(1−kk+1)ϕ⁢(kk+1)≤(1k+1)1/2⁢δ.

⊲

We now define our junta function. Let J¯:=J∖J′. Define h:[k+1]n→[0,1] as

h⁢(X):=𝔼Y∈[k+1]J¯[f⁢(XJ′,Y)], (1)

where xJ′ is the point in the hypergrid where the coordinates in J′ are assigned as they were in J and the coordinates in J¯ are non-assigned.

First, we show that h is k–submodular.

Claim 20.

The function h defined in Equation 1 is k–submodular.

Proof.

We have to show that h satisfies the two following conditions.

  1. 1.

    Diminishing marginal gains. Let X,Z∈[k+1]n with Z⪯X and e∉X. Let j∈[k]. Then, we have

    Δh⁢(Z,j,e)=h⁢(Zei)−h⁢(Z)={0,if ⁢j∉J′𝔼Y∈[k+1]J¯[f⁢((Zei)J′,Y)−f⁢(ZJ′,Y)],otherwise.

    If j∉J′, then Δh⁢(X,j,e)=0 as well, so the diminishing marginal gains condition holds. Otherwise, by the k–submodularity of f, we know that for all y∈[k+1]J¯,

    f⁢((Zei)J′,Y)−f⁢(ZJ′,Y)≥f⁢((Xei)J′,Y)−f⁢(XJ′,Y)

    which allows us to conclude that Δh⁢(Z,j,e)≥Δh⁢(X,j,e), and thus that h satisfies diminishing marginal gains.

  2. 2.

    Pairwise Monotonicity. Let X∈[k+1]n, i≠j∈[k] and e∈Xk+1. If e∉J, then 12⁢(h⁢(Xei)+h⁢(Xej))=h⁢(X). Otherwise, by the pairwise monotonicity of f,
    12⁢(h⁢(Xei)+h⁢(Xej))=𝔼Y∈[k+1]J¯12⁢[f⁢((Xei)J′,Y)−f⁢((Xej)J′,Y)]≥𝔼Y∈[k+1]J¯[f⁢(XJ′,Y)]=h⁢(X).

We can thus conclude by Theorem 9 that h is k–submodular. ⊲

Our final step is to show that h is a good approximation to f in the ℓ2-norm.

Definition 21 (Bad points).

A point XJ′ in the restricted hypergrid is called bad if there exists i∈J¯ and j∈[k] such that

Δf⁢(XJ′,j,i)>α,

or there exists i∈XJ′

Δf⁢(XJ′∖i,XJ′⁢(i),i)<−α.

The ℓ2 distance can be bounded as below.
∥h−f∥22 =𝔼X∈[k+1]J[(f⁢(X)−h⁢(X))2] =𝔼XJ′∈[k+1]J′[𝔼Y∈[k+1]J¯[(f⁢(XJ′,Y)−𝔼Y′∈[k+1]J¯[f⁢(XJ′,Y′)])2]] =𝔼XJ′∈[k+1]J′[VarY∈[k+1]J¯[f⁢(XJ′,Y)]] ≤Pr⁡[XJ′⁢ is bad]+𝔼XJ′∈[k+1]J′⁢ good[VarY∈[k+1]J¯[f⁢(XJ′,Y)]]. [Because ⁢f⁢(X)≤1]

We first show that for appropriate parameters to Algorithm 1, the probability that a point is bad is small.

Claim 22.

If we set δ=log⁡(k+1)2⁢log⁡(8⋅k⋅|J|⋅ε−2) in Algorithm 1, then

PrXJ′∈[k+1]J′⁡[XJ′⁢ is bad]≤ε28.
Proof.

Recall that we consider a uniform distribution over XJ′∈[k+1]J′. This distribution is the same as sampling a partition P:J′→[k] uniformly at random and returning J′⁢(kk+1)P. To see this, fix an arbitrary point X∈[k+1]J′. Let A:={i∈J′:xi=k+1} and B=J′∖A. The probability of generating this particular X with the latter sampling procedure is

Pr⁡[X]=(1k+1)|A|⋅(kk+1)|B|⋅(1k)|B|=1(k+1)|J′|

So, via a union bound, Claim 19 and by plugging in δ=log⁡(k+1)2⁢log⁡(8⋅k⋅|J|⋅ε−2), we get that

Pr⁡[XJ′⁢ is bad] =PrJ′⁢(kk+1),P:J′→[k][⋃j∈[k]⋃i∈J¯(Δf⁢(J′⁢(kk+1)P,j,i)>α)]
≤|J¯|⋅k⋅(1k+1)1/2⁢δ
≤ε28.

⊲

Finally, we show that for appropriate parameters to Algorithm 1, the variance of f⁢(XJ′,⋅) when XJ′ is good is small.

Claim 23.

If we set α=ε216 in Algorithm 1, then

𝔼XJ′∈[k+1]J′⁢ goodVar⁢[f⁢(XJ′,⋅)]≤ε28.
Proof.

When XJ′ is good, we have that the marginal gain Δf⁢(XJ′,j,i) of adding any i∈J¯ to any bucket j∈[k] is at most α. Because of diminishing marginal gains, this bounds the marginal gains of f⁢(XJ′,⋅) over its entire domain by α. Also, the marginal gains of f⁢(XJ′,⋅) are at least −α, because if there existed some Y≥XJ′, i∈J¯ and j∈[k] with Δf⁢(Y,j,i)<−α, then by pairwise monotonicity we must have for all j′≠j that Δf⁢(Y,j′,i)≥α as

Δf⁢(Y,j,i)+Δf⁢(Y,j′,i)≥0.

But this contradicts the upper bound of α to the marginal gains. Thus, f⁢(XJ′,⋅) is α–Lipschitz and we can appeal to Lemma 14 to get

Var⁢[f⁢(xJ′,⋅)]≤2⁢α⋅𝔼⁢[f⁢(xJ′,⋅)]≤ε28.

⊲

We are now ready to finish the proof of Theorem 17.

Proof of Theorem 17.

We let J′ by the output of Algorithm 1 with input f and parameters

δ=log⁡(k+1)2⁢log⁡(8⋅k⋅|J|⋅ε−2),α=ε216.

Then the function h defined by Equation 1 is the desired junta function. Indeed, combining (22) and (23), we get

∥h−f∥22≤ε28+ε28=ε24.

To bound the size of J′, we use Claim 18 to get

|J′|≤2α⁢δ=32⋅1log⁡(1+k)⋅1ε2⋅log⁡8⋅k⋅|J|ε2≤32ε2⋅log⁡8⁢|J|ε2.

◀

Using the weak junta approximation, we are able arrive at our final junta approximation.

3.3 Proof of Theorem 2

Let f:[k+1]n→[0,1] be a k–submodular function. We will prove a bound of |J|≤4000ε2⁢log⁡1ε2 for the size of the approximating junta.

Observe that this bound holds trivially for ε<n−1/2, because then we are allowed to choose J=[n]. For contradiction, suppose that there is ε∈(n−1/2,1/2) for which the statement of Theorem 2 does not hold. Let ℰ⊂(n−1/2,1/2) be the set of all ε for which the statement does not hold, and pick an ε∈ℰ such that ε<2⁢infℰ. Then, the statement still holds for ε2=ε2<12⁢ε.

By the statement of Theorem 2 for ε2, there is a subset of variables J′ of size |J′|≤4000ε2⁢log⁡1ε≤213ε2 and a k–submodular function g depending only on J, such that ∥f−g∥2≤ε2≤12⁢ε.

Now we apply Theorem 17 to g with parameter ε. Thus, there exists a k–submodular function h such that ∥g−h∥2≤12⁢ε, and h depends only on a subset of variables J′′⊆J′, |J′′|≤32ε2⁢log⁡8⁢|J′|ε. We have |J′|≤213ε2, and therefore |J′′|≤32ε2⁢log⁡216ε3≤32ε2⁢log⁡1ε3 (using ε≤12). We conclude that |J′′|≤32ε2⁢log⁡1ε3≤4000ε2⁢log⁡1ε as required in Theorem 2. By the triangle inequality, we have ‖f−h‖2≤‖f−g‖2+‖g−h‖2≤12⁢ε+12⁢ε=ε.

However, this would mean that the statement of Theorem 2 holds for ε as well, which is a contradiction. ∎

4 Towards testing 𝒌–submodularity in the ℓ𝟎-norm

In this section, we develop the local-witness theory for the two constraints that characterize k–submodularity in Hamming distance. For diminishing marginal gains, the witnesses are generalized violated squares. For pairwise monotonicity, the witnesses are violated triangles. We prove that if either constraint is far from being satisfied, then the corresponding witnesses are dense enough to be found by a non-adaptive one-sided tester. The key step in both cases is a repair argument over ideals and filters in the hypergrid.

4.1 Setup

An inductive argument shows that absence of violating squares is equivalent to the diminishing marginal gains property:

Proposition 24.

A function f:[k+1]n→ℝ satisfies the diminishing marginal gains property if and only if it has no violating squares.

Proof.

If a function satisfies the diminishing marginal gains property, then it is easy to see that it has no violating squares: take Y=Xgj. We show the converse by considering X⪯Y, e∉Y and i∈[k]. Suppose e1,…,eℓ are the elements of Y not in X⊓Y that have Y⁢(e)≠k+1. Then we have that:

f⁢(Xei)−f⁢(X)≥f⁢(Xe,e1i,Y⁢(e1))−f⁢(Xe1Y⁢(e1))

By induction we can telescopically build the partial partition Y on the right hand side and recover the diminishing marginal gains property. ◀

Definition 25 (Violating triangle).

Let X∈[k+1]n, i≠j∈[k], and e∈Xk+1. We call {x,Xei,Xej} a triangle. For a function f:[k+1]n→ℝ, this is called an f–violating triangle if

f⁢(Xei)+f⁢(Xej)2<f⁢(X),

that is, it violates the pairwise monotonicity condition.

4.2 Testing diminishing marginal gains

Algorithm 2 A tester for diminishing marginal gains.

We prove the following theorem.

Theorem 26.

Algorithm 2 has the following properties.

  1. 1.

    If f has diminishing marginal gains, then Algorithm 2 accepts with probability 1.

  2. 2.

    If f is ε-far from diminishing marginal gains, then Algorithm 2 rejects with probability at least 2/3.

  3. 3.

    Algorithm 2 makes q=4⁢n2⋅(1/ε)Θ⁢(n⁢log⁡n) queries.

Items 1 and 3 are easy to verify – they are direct consequences of Theorem 9 and the description of Algorithm 2, respectively. The rest of this section will be dedicated to proving Item 2.

Intuitively, our proof proceeds as follows. We first show that if a function f has a “low density” of violating squares, then it can be made to have the diminishing marginal gains property by changing the values of only a “few” points. By contrapositive, this means that a function that is “far” from diminishing marginal gains must have a “high density” of witnesses, which implies the correctness of our tester. To “repair” a function f towards diminishing marginal gains, we modify its values over a union of ideals and filters, defined as follows.

Definition 27 (Ideal).

Let X∈[k+1]n. The Ideal of X is defined as

I⁢(X):={Y∣Y⪯X}.
Definition 28 (Filter).

Let X∈[k+1]n. The Filter of X is defined as

F⁢(X):={Y∣X⪯Y}.

We start with the following “repair” lemma for violating squares.

Lemma 29 (Square repair lemma).

Let f:[k+1]n→ℝ be a function in which {X,Xei,Xgj,X(e,g)(i,j)} is an f–violating square. There is a way to change only the values of the ideal I⁢(X) or the filter F⁢(X(e,g)(i,j)) to obtain a function f′ in which {X,Xei,Xgj,X(e,g)(i,j)} is no longer an f′–violating square, and no additional f′–violating squares have been introduced.

Proof.

Because {X,Xei,Xgj,X(e,g)(i,j)} is an f–violating square, we have

ΔX:=f⁢(X)+f⁢(X(e,g)(i,j))−f⁢(Xei)−f⁢(Xgj)>0.

Fix any constant Δ≥ΔX. We obtain f′ by subtracting Δ from f⁢(Y) for all Y∈I⁢(X). Clearly, this repairs the f–violating square itself, but we must also argue that it does not introduce any new f′–violating squares.

Let {Y,Ye′i′,Yg′j′,Y(e′,g′)(i′,j′)} be an f′–violating square that is not f–violating. If Y⋠X, then none of the values in the square were modified. So we can assume Y⪯X. We consider the following cases.

  1. 1.

    Neither Ye′i′⋠X nor Yg′j′⋠X. Then the points Ye′i′,Yg′j′,Y(e′,g′)(i′,j′) are not modified. Thus, the value of this square is

    (f⁢(Y)−Δ)+f⁢(Y(e′,g′)(i′,j′))−f⁢(Yg′j′)−f⁢(Ye′i′)=f⁢(Y)+f⁢(Y(e′,g′)(i′,j′))−f⁢(Yg′j′)−f⁢(Ye′i′)−Δ≤−Δ.
  2. 2.

    Only Ye′i′⋠X and Yg′j′⪯X. Then the points Ye′i′,Y(e′,g′)(i′,j′) are not modified. Thus, the value of this square is

    (f⁢(Y)−Δ)+f⁢(Y(e′,g′)(i′,j′))−(f⁢(Yg′j′)−Δ)−f⁢(Ye′i′)=f⁢(Y)+f⁢(Y(e′,g′)(i′,j′))−f⁢(Yg′j′)−f⁢(Ye′i′)≤0.

    The case of Ye′i′⪯X and Yg′j′⋠X is symmetric and identical.

  3. 3.

    Both Ye′i′⪯X and Yg′j′⪯X. Then Y(e′,g′)(i′,j′)⪯X, and all the points are modified. Thus, the value of this square is

    (f⁢(Y)−Δ)+(f⁢(Y(e′,g′)(i′,j′))−Δ) −(f⁢(Yg′j′)−Δ)−(f⁢(Ye′i′)−Δ)
    =f⁢(Y)+f⁢(Y(e′,g′)(i′,j′))−f⁢(Yg′j′)−f⁢(Ye′i′)≤0.

As a result, we have shown that no new violating squares are introduced after changing all the values in I⁢(X), and the original violating square rooted in X is repaired. An identical argument suffices to prove that subtracting Δ from the filter F⁢(X(e,g)(i,j)) has the same consequence. ◀

The proof of this lemma also implies the following corollary.

Corollary 30.

Let f:[k+1]n→ℝ be a function and X∈[k+1]n be a domain point. For any constant Δ>0, the function f′ obtained by subtracting Δ from f⁢(Y) for all Y∈I⁢(X) or all Y∈F⁢(X) does not introduce any new f′–violating squares.

Next, we prove the following density lemma.

Lemma 31.

Let f:[k+1]n→ℝ be a function with m violating squares. If m≤εn⁢log⁡n⋅(k+1)n for ε∈(0,e−5), then f can be made to have diminishing marginal gains by changing at most ε⋅(k+1)n values.

Proof.

The proof is a counting argument on the number of points we will need to change by the square repair procedure above. We enumerate all m violating squares and arrange them in order of item-weight (equal to ∑i=1k|Xi|) of the bottom point. We split the hypercube evenly based on item-weight. It can be verified that this split occurs at weight n⁢kk+1.

  1. 1.

    For violating squares where the bottom vertex has item-weight ≤n⁢kk+1, we repair them by modifying values in the ideal. Let I denote the bottom vertex in these violating squares. Then the total number of modified points is |∪X∈II⁢(X)|.

  2. 2.

    For violating squares where the bottom vertex has item-weight >n⁢kk+1, we repair them by modifying values in the filter. Let F denote the top vertex in these violating squares. Then the total number of modified points is |∪X∈FF⁢(X)|.

We first prove the counting argument for Item 1. We estimate this cardinality by combining two different bounds across levels of the hypergrid. Let Lj:={X∈[k+1]n:|X|≤j}. Then we can write

|⋃X∈II⁢(X)|=∑j=0n⁢kk+1|⋃X∈I(I⁢(X)∩Lj)|.

We can bound these terms in two ways. First, we have

|⋃X∈I(I⁢(X)∩Lj)|≤∑X∈I|I⁢(X)∩Lj|=∑X∈I(|X|j)≤|I|⋅(n⁢kk+1j).

Second, there is the more trivial bound of

|⋃X∈I(I⁢(X)∩Lj)|≤|Lj|=(nj)⋅kj.

This second bound is reminiscent of the binomial distribution Bin⁢(n,kk+1). Combining this with a Chernoff bound, we can get an upper bound on the number of points with item-weight far from the mean. Now we just have to use the correct bound depending on j.

  1. 1.

    If j≤n⁢kk+1−α⁢n⁢kk+1 for some constant α, then
    ∑j=0n⁢kk+1−α⁢n⁢kk+1(nj)⋅kj =(k+1)n⁢∑j=0n⁢kk+1−α⁢n⁢kk+1(nj)⋅(kk+1)j⁢(1k+1)n−j =(k+1)n⋅Pr⁡[Z≤n⁢kk+1−α⁢n⁢kk+1] [Z∼Bin⁢(n,kk+1)] =(k+1)n⋅Pr⁡[Z≤(1−δ)⁢n⁢kk+1] [Letting ⁢δ=αn⁢kk+1] ≤(k+1)n⋅e−δ2⁢n⁢k/2⁢(k+1) [Chernoff bound] =(k+1)n⋅e−α2/2.

  2. 2.

    If j>n⁢kk+1−α⁢n⁢kk+1, then

    ∑j=n⁢kk+1−α⁢n⁢kk+1n⁢kk+1|I|⋅(n⁢kk+1j) =|I|⋅∑j=0α⁢n⁢kk+1(n⁢kk+1j)
    ≤|I|⋅(n⁢kk+1)α⁢n⁢kk+1
    ≤|I|⋅nα⁢n
    =|I|⋅eα⁢n⁢ln⁡n.

Finally, setting α=12⁢ln⁡ε−1 yields
|⋃X∈II⁢(X)| =∑j=0n⁢kk+1|⋃X∈I(I⁢(X)∩Lj)| [Splitting by item-weight] =∑j=0n⁢kk+1−α⁢n⁢kk+1|⋃X∈I(I⁢(X)∩Lj)|+∑j=n⁢kk+1−α⁢n⁢kk+1n⁢kk+1|⋃X∈I(I⁢(X)∩Lj)| [Splitting the sum] ≤∑j=0n⁢kk+1−α⁢n⁢kk+1(nj)⋅kj+∑j=n⁢kk+1−α⁢n⁢kk+1n⁢kk+1|I|⋅(n⁢kk+1j) [Discussed bounds] ≤(k+1)n⋅e−α2/2+|I|⋅eα⁢n⁢ln⁡n [From case analysis] ≤(k+1)n⋅e−α2/2+m⋅eα⁢n⁢ln⁡n [|I|≤m] ≤(k+1)n⋅e−α2/2+(k+1)n⋅εn⁢ln⁡n⋅eα⁢n⁢ln⁡n [m≤(k+1)n⋅εn⁢ln⁡n] =(k+1)n⋅ε18⁢ln⁡ε−1+(k+1)n⋅εn⁢ln⁡n⋅ε−12⁢n⁢ln⁡n [α=1/2⋅ln⁡ε−1] ≤(k+1)n⋅(ε18⁢ln⁡ε−1+ε12⁢n⁢ln⁡n) [Simplifying] ≤ε2⋅(k+1)n. [ε∈(0,e−5)]

This concludes the counting argument for Item 1.

The counting argument for Item 2 is almost identical. We split the filters by level, and for j≥n⁢kk+1+α⁢n⁢kk+1, the Chernoff-inequality based upper bound still holds. For j<n⁢kk+1+α⁢n⁢kk+1, we get the following bound.

∑j=n⁢kk+1n⁢kk+1+α⁢n⁢kk+1|⋃X∈F(F⁢(X)∩Lj)| ≤∑X∈F|F⁢(X)∩Lj|
=∑j=n⁢kk+1n⁢kk+1+α⁢n⁢kk+1∑X∈F(n−|X|j−|X|)⁢kj−|X|
≤∑j=n⁢kk+1n⁢kk+1+α⁢n⁢kk+1∑X∈F(nk+1j−|X|)⁢kj−|X|
≤∑j=n⁢kk+1n⁢kk+1+α⁢n⁢kk+1∑X∈F(nk+1)j−|X|⁢kj−|X|
≤∑j=n⁢kk+1n⁢kk+1+α⁢n⁢kk+1∑X∈Fnj−|X|
≤∑j=n⁢kk+1n⁢kk+1+α⁢n⁢kk+1|F|⋅nj−n⁢kk+1
≤|F|⋅nα⁢n⁢kk+1
≤|F|⋅nα⁢n
=|F|⋅eα⁢n⁢ln⁡n.

The rest of the counting argument is exactly the same and thus omitted.

In conclusion, we need to modify ≤ε⋅(k+1)n values to make f have diminishing marginal gains. ◀

We are now ready to finish the analysis of our tester.

Proof of Theorem 26.

We prove each part separately.

  1. 1.

    By Theorem 9, a function with diminishing marginal gains does not have any f–violating squares. As a result, the tester will always accept.

  2. 2.

    By the contrapositive of Lemma 31, a function that is ε-far from diminishing marginal gains has at least (k+1)n⋅εn⁢ln⁡n violating squares. The total number of squares is (n2)⋅k2⋅(k+1)n−2=Θ⁢(n2⁢(k+1)n). Thus, by the witness lemma, n2⋅(1/ε)Θ⁢(n⁢log⁡n) queries suffice to catch an f–violating square with high probability.

  3. 3.

    This follows trivially from the design of the algorithm.

This completes the analysis of Algorithm 2. ◀

4.3 An obstruction to component-wise local repair

The component testers of the previous two sections each rest on a dense witness theorem and a local repair argument. A natural attempt at a tester for full k–submodularity is to apply both component testers in parallel and union-bound the failure probability over the two repair arguments. We now show that this attempt cannot succeed: there exist configurations on which the repair direction prescribed by a triangle witness is forced to oppose the repair direction prescribed by an overlapping square witness on a shared vertex.

For ideals rooted at item-weight ≤n⁢kk+1, the repairs for both witness types proceed downward and can be aligned. The obstruction lives in the upward direction. On filters rooted at item-weight >n⁢kk+1, repairing a violated square requires subtracting Δ>0 from a vertex, whereas repairing a violated triangle in the same filter requires adding Δ>0 to that vertex. The configuration in Figure 1 realizes both demands simultaneously on the vertices x2 and x3.

Figure 1: A configuration on a high item-weight filter realizing two incompatible local violations. The red edges form a violating triangle on item 5 above x1: assigning item 5 to part 1 (giving x2) or to part 2 (giving x3) both yield marginal −1, summing to −2<0. The blue edges form two violating squares for diminishing marginal gains on items 3 and 4 in part 3, above x8 (left) and x9 (right). Repairing the triangle requires raising f⁢(x2) or f⁢(x3); repairing the squares requires lowering the same values.

The configuration is not isolated to a small region of the hypergrid. Embedding the same value pattern into any high-item-weight filter on a larger domain produces an instance of the same conflict, so an ideal-only repair strategy that avoids upward filters cannot route around it without losing the balance argument that makes the component testers work.

Observation 32 (Component-wise repair is insufficient).

For every k≥2 there exist functions f:[k+1]n→ℝ and high item-weight filters on which a violated triangle witness and an overlapping violated square witness prescribe local repairs of opposite sign on a common vertex. In particular, the standard component-wise repair argument – repair triangles and squares independently and combine via union bound – does not yield a tester for k-submodularity.

Observation 32 does not rule out a Hamming-distance tester for k-submodularity; it shows only that obtaining one will require either a richer witness vocabulary that simultaneously certifies both component constraints, or a non-local repair scheme that mediates between square and triangle repairs across the hypergrid.

References

  • [1] Eric Blais and Abhinav Bommireddi. Testing submodularity and other properties of valuation functions. arXiv preprint arXiv:1611.07879, 2016. arXiv:1611.07879.
  • [2] Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration inequalities. In Summer school on machine learning, pages 208–240. Springer, 2003. doi:10.1007/978-3-540-28650-9_9.
  • [3] Deeparnab Chakrabarty and Zhiyi Huang. Recognizing coverage functions. SIAM Journal on Discrete Mathematics, 29(3):1585–1599, 2015. doi:10.1137/140964072.
  • [4] Alina Ene and Huy Nguyen. Streaming algorithm for monotone k-submodular maximization with cardinality constraints. In International Conference on Machine Learning, pages 5944–5967. PMLR, 2022. URL: https://proceedings.mlr.press/v162/ene22a.html.
  • [5] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab S Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In European Symposium on Algorithms, pages 182–194. Springer, 2010. doi:10.1007/978-3-642-15775-2_16.
  • [6] Vitaly Feldman and Jan Vondrák. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45(3):1129–1170, 2016. doi:10.1137/140958207.
  • [7] Michel X Goemans and Jan Vondrák. Covering minimum spanning trees of random subgraphs. Random Structures & Algorithms, 29(3):257–276, 2006. doi:10.1002/RSA.20115.
  • [8] Oded Goldreich, Shari Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653–750, 1998. doi:10.1145/285055.285060.
  • [9] Themistoklis Haris and Diptaksho Palit. Testing k-submodularity. CoRR, abs/2606.30433, 2026. doi:10.48550/arXiv.2606.30433.
  • [10] Pooya Hatami and Jan Vondrák. Testing real-valued modularity and submodularity, 2016. URL: https://www.ias.edu/sites/default/files/math/csdm/15-16/HatamiVondrak.pdf.
  • [11] Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331–1348, 1993. doi:10.1137/0222080.
  • [12] Naoto Ohsaka and Yuichi Yoshida. Monotone k-submodular function maximization with size constraints. Advances in Neural Information Processing Systems, 28, 2015.
  • [13] Michal Parnas, Dana Ron, and Ronitt Rubinfeld. On testing convexity and submodularity. SIAM Journal on Computing, 32(5):1158–1184, 2003. doi:10.1137/S0097539702414026.
  • [14] Sofya Raskhodnikova. CS 599: Sublinear Algorithms (Spring 2025). https://cs-people.bu.edu/sofya/sublinear-course/, 2025. Retrieved on 10 October, 2025. URL: https://cs-people.bu.edu/sofya/sublinear-course/.
  • [15] Sofya Raskhodnikova and Grigory Yaroslavtsev. Learning pseudo-boolean k-dnf and submodular functions. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1356–1368. SIAM, 2013. doi:10.1137/1.9781611973105.98.
  • [16] Comandur Seshadhri and Jan Vondrák. Is submodularity testable? Algorithmica, 69(1):1–25, 2014. doi:10.1007/S00453-012-9719-2.
  • [17] Justin Ward and Stanislav Živnỳ. Maximizing k-submodular functions and beyond. ACM Transactions on Algorithms (TALG), 12(4):1–26, 2016. doi:10.1145/2850419.