Pairwise independent correlation gap
This work addresses a theoretical gap in understanding the impact of pairwise versus mutual independence in optimization, which is incremental but relevant for researchers in submodular functions and probability theory.
The paper tackles the problem of bounding the pairwise independent correlation gap for nonnegative monotone submodular set functions, showing that the ratio is upper bounded by 4/3 in specific cases such as n=3 or small/large marginal probabilities.
In this paper, we introduce the notion of a ``pairwise independent correlation gap'' for set functions with random elements. The pairwise independent correlation gap is defined as the ratio of the maximum expected value of a set function with arbitrary dependence among the elements with fixed marginal probabilities to the maximum expected value with pairwise independent elements with the same marginal probabilities. We show that for any nonnegative monotone submodular set function defined on $n$ elements, this ratio is upper bounded by $4/3$ in the following two cases: (a) $n = 3$ for all marginal probabilities and (b) all $n$ for small marginal probabilities (and similarly large marginal probabilities). This differs from the bound on the ``correlation gap'' which holds with mutual independence and showcases the fundamental difference between pairwise independence and mutual independence. We discuss the implication of the results with two examples and end the paper with a conjecture.