Concentration of Submodular Functions and Read-$k$ Families Under Negative Dependence

Assume $X_1,\mathrm{\dots },X_n$ satisfy weak negative regression; we will prove that it also satisfies 1-negative association. Let $f$ and $g$ be monotone functions such that $f$ depends on $X_I$ for some subset $I\subseteq [n]$ and $g$ depends on $X_i$ for $i\notin I$. Without loss of generality, let us assume that $f$ and $g$ are non-decreasing.

First, define the function $F(a)=𝔼[f(X)|X_i=a].$ Evaluating the expectation $𝔼[f(X_I)g(X_i)]$, we can express it via the law of total expectation as

Next, we observe that by the definition of weak negative regression, $F(a)$ is non-increasing. Therefore, random variables $F(X_i)$ and $g(X_i)$ are negatively correlated, yielding

Converting $𝔼[F(X_i)]$ back into the terms of $f$ and $g$, we find

The overall inequality $𝔼[f(X_I)g(X_i)]\le 𝔼[f(X_I)]𝔼[g(X_i)]$ thus holds, which establishes that $X_1,\mathrm{\dots },X_n$ are 1-negatively associated, completing the proof. $\mathrm{⊲}$

Recall that we wish to prove that for any non-decreasing function $f$ depending on some subset $I\subseteq [n]$ and any $i\notin I$, we have that

By the definition of 1-negative association, we obtain that for any monotone functions $g$ which depends on $X_i$, the following inequality holds:

Without loss of generality, we may assume that $𝔼[f(X_I)|X_i=1]=0$ by shifting $f$ by a constant. By choosing $g$ to be the identity function, we can apply the law of total probability to obtain

Plugging this into Equation 1, we obtain

again by the law of total probability. Since $𝔼[X_i]>0$ and $\mathrm{Pr}[X_i=0]>0$, this implies that

which concludes the proof since $𝔼[f(X_I)|X_i=1]=0$. $\mathrm{⊲}$

Let’s first discuss the intuition for the construction of the counterexample. One can show via algebra that $𝔼[f(X_I)g(X_i)]-𝔼[f(X_I)]𝔼[g(X_i)]$ can be expanded as the following expression:

where the summation is over the values that $X_i$ takes with non-zero probability.

Now, suppose that for some values we have that

violating the weak negative regression property. This would imply that some of the summands are positive (since by monotonicity). In the case of binary random variables, the summation would only consist of a single summand so 1-negative association would be violated. For general random variables, the summation consists of multiple terms so the summation may still be negative even when a single summand is positive. Consequently, the random variables may still satisfy 1-negative association.

We now give the example. Consider the random variables $(X_1,X_2)$ which are uniformly distributed on their support set $\{(0,3),(1,1),(2,2),(3,0)\}$. By considering an identity function ${\mathrm{𝟙}}_x:\{0,1,2,3\}\to \{0,1,2,3\}$, we can show that that the distribution of $(X_1,X_2)$ does not satisfy weak negative regression:

However, for any pair of non-decreasing functions $f,g:\{0,1,2,3\}\to ℝ$, we have

where we have again assumed without loss of generality that $f(0)=g(0)=0$.

We claim that the quantity on the right hand side is always non-negative. In order to see this, observe that $f(2)g(2)\le f(i)g(j)$ for any $i,j\ge 2$ by monotonicity. As a result, we have

Further, we observe that $f(1)g(1)\le f(i)g(j)$ for any $i,j\ge 1$ by monotonicity. As a result, we have

Combining these two inequalities immediately and observing that $f(1)g(1)\ge 0$ by monotonicity implies our desired result. Hence, the distribution is 1-negatively associated. $\mathrm{⊲}$

Since 1-negative association and weak negative regression are equivalent for binary random variables and weak negative regression has been shown to be strictly stronger than cylinder negative dependence [23, Proposition 2.4], we also have that $1$-negative association is strictly stronger than cylinder negative dependence. Additionally, since weak negative regression is strictly stronger than $1$-negative association for general random variables and weak negative regression has been shown to be strictly weaker than negative association and negative regression [23, Proposition 2.4], we have that 1-negative association is strictly weaker than negative association and negative regression. We summarize these in the following corollaries.

Fix if $f$ is submodular and $\lambda >0$ if $f$ is supermodular. Observe that in order to prove the lemma, it suffices to prove

since we can iteratively apply the above inequality to each $X_i$ (note that we can do this because independent variables are also negatively associated). For simplicity of notation and without loss of generality, we will prove the inequality for $i=1$.

By considering the cases of $X_1=0$ and $X_1=1$ separately, we have

where the equality holds pointwise on the underlying probability space. Via simple algebraic manipulations, we can rewrite the right hand side as

Taking expectations, we now have that $𝔼[\exp (\lambda f(X_1,\mathrm{\dots },X_n))]$ can be written as

Observe that $X_1$ is clearly an increasing function of $X_1$. We claim that if either ($i$) $f$ is submodular and or ($ii$) $f$ is supermodular and $\lambda >0$, we have that $\exp (\lambda \cdot f(1,X_2,\mathrm{\dots },X_n)))-\exp (\lambda \cdot f(0,X_2,\mathrm{\dots },X_n))$ is an increasing function in $X_2,\mathrm{\dots },X_n$. Indeed, we first rewrite the function as

for simplicity of notation.

Let us first consider the case when and $f$ is submodular. We have that $A_1$ is ($i$) positive because the exponential function is always positive and ($ii$) non-increasing in $X_2,\mathrm{\dots },X_n$ because $f$ is non-decreasing and . We also have that $A_2$ is ($i$) negative because the argument in $\exp (\cdot )$ is negative, so the exponential is in $(0,1)$ ($ii$) non-decreasing since and the difference of $f$ evaluated at $X_1=1$ and $X_1=0$ is non-increasing by definition of submodularity. Hence, our expression of interest is the product of a function $A_1$ which decreases towards 0 and a function $A_2$ which increases towards $0$. The product will be negative and monotonically increasing towards $0$.

Now, let us consider the case when $\lambda >0$ and $f$ is supermodular. We have that $A_1$ is ($i$) positive because the exponential function is always positive and ($ii$) non-decreasing since $\lambda >0$, $f$ is monotone, and $\exp (\cdot )$ is also monotone. We also have that $A_2$ is ($i$) positive because the argument of $\exp (\cdot )$ is positive since $f$ is monotone so the exponential is greater than $1$ and ($ii$) non-decreasing since $\lambda >0$ and the difference of $f$ evaluated at $X_1=1$ and $X_1=0$ is non-decreasing by definition of supermodularity. As a result, the product will be positive and non-decreasing, as desired.

Since we have shown that the $A_1{A}_2$ is also monotone, we now have that the first term in Equation 3 can be written as the product of monotone functions of disjoint subsets, one of which is the singleton set. By 1-negative association, we have that the first term is upper bounded by

Consequently, the entire expression in (3) is upper bounded by

Since $X_1$ and $X_1^{\ast }$ have the same marginal distributions, the above is exactly equal to

And since $X_1^{\ast }$ is independent with $X_2,\mathrm{\dots },X_m$ by assumption, the above is equal to

In particular, observe that this is in the exact same form as Equation 3, except with $X_1$ replaced with $X_1^{\ast }$. Note that when we transformed the left-hand side of Equation 2 to Equation 3, we never used any properties of the random variables $X_1,\mathrm{\dots },X_n$ other than the fact that they take values in $\{0,1\}$. As a result, we can reverse the direction of all of the equalities to show that the above expression is equal to

which completes the proof of the lemma. $◀$

Now, we will complete the proof of our main result. Combining the theorem below with Claims 8 and 9 immediately gives a proof of Theorem 2. Here, our proof will rely heavily on the proof of the Chernoff bound for submodular functions under independence given in [6].

Let $X_1^{\ast },\mathrm{\dots },X_n^{\ast }$ be independent random variables with the same respective marginals as $X_1,\mathrm{\dots },X_n$ and let be a parameter to be set later. Let us decompose $f(X_1^{\ast },\mathrm{\dots },X_n^{\ast })={\sum }_{i=1}^n{Y}_i^{\ast }$, where

Let us denote $𝔼[Y_i^{\ast }]={\omega }_i$ and ${\mu }_0={\sum }_{i=1}^n{\omega }_i=𝔼[f(X_1^{\ast },\mathrm{\dots },X_n^{\ast })]$. By the convexity of the exponential and the fact that $Y_i^{\ast }\in [0,1]$, we have that

Combining the above with Lemma C.1 from [6], we have that

Now, we can follow the proof of the standard Chernoff bound:

The first equality follows since $\exp (\lambda \cdot x)$ is a monotone function, the first inequality follows by Markov’s inequality, the second inequality follows by Lemma 8, and the final inequality follows Equation 4.

Finally, we can choose $\lambda$ such that $\exp (\lambda )=1-\delta$, which gives

where we used ${(1-\delta )}^{1-\delta }\le \exp (-\delta +{\delta }^2/2)$ for $\delta \in (0,1]$ in the final inequality. $◀$

Let $f(X_1,\mathrm{\dots },X_m)={\sum }_{j=1}^n{f}_j(X_{P_j})$ be the quantity of interest, and note that $f$ is the sum of supermodular functions so it is supermodular as well.

We will follow the standard proof via exponential moments. Let $\lambda >0$; we have

where the inequality follows by Markov’s. Since $f$ is supermodular, we have by Lemma 11 that

In the new proof of concentration of read-$k$ families, given in the Appendix, we show that

Combining equations 7–10, we have

Let ${\lambda }^{\prime }=k\lambda$; since $\lambda >0$ is a parameter we set, we can view ${\lambda }^{\prime }>0$ as a parameter as well. We will abuse notation and replace ${\lambda }^{\prime }$ with $\lambda$, so we have

for any $\lambda >0$. Now, observe that the right hand side of the inequality is the exact same as in the proof of the standard Chernoff bound under independence, except with an additional exponent $1/k$. As a result, we can follow the original proof of the Chernoff bound to show that

which was our desired result. $◀$