Concentration of U-statistics for exchangable distributions (and the unbounded case)

Question

Consider the following so-called $U$-statistic of order 2: $$U = \frac1{\binom{m}{2}} \sum_{i < j} h(w_i,w_j)$$ where $w_1,\dots,w_m$ are IID from some distribution and $h$ is symmetric. If $|h(w_1,w_2)| \le B$ a.s., then a classical result gives the following concentration inequality: \begin{align} \mathbb P( | U - \mathbb E U| \ge t) \le 2 \exp(- m t^2 /(8B^2)). \end{align} (Maybe there are better constants known here.)

I have the following two questions:

• It seems to me that this immediately generalizes to the case where $(w_1,\dots,w_n)$ has an exchangeable distribution, due to de Finetti's theorem saying that any such distribution is a result of a mixture of IID ones. More precisely, there is a random measure $G$, such that conditional on $G$, $w_1,\dots,w_n$ are IID draws from $G$. By conditioning on $G$, using the inequality above for the IID case, and then taking expectations, we get the result for the exchangeable case. Is this argument correct?

• What is the state of the art in terms of concentration bounds for such $U$-statistics, esp in the case where $h$ is not bounded? Are there clear generalization known, esp. for the exchangable case? The above argument seems to rely on boundedness of $h$ in a critical way.

EDIT: I should say that for the first point, it might be that we have to assume $h$ to be surely bounded (?)

EDIT: As was pointed out, the argument in point one is flawed. In the hindsight, one needs extra conditions. The case where $w_1=w_2=\dots=w_m$ is an example of an exchangeable distribution for which the concentration (with $m$ in the exponent) need not hold.

Answer 1

I do not think the conclusion will hold for a general exchangeable sequence. In a more general case, you have to assume that U-statistics itself are not degenerated ($w_i\neq w_j$ for $i\neq j$) and the concentration bound is still not so good as shown in [Arcones].

However, for the case where exchangeable pairs exists (like independent yet not necessarily identical), [Lester Mackey et.al] Coro 5.2. might be what you want.

I think the following paper Matrix Concentration Inequalities via the Method of Exchangeable Pairs is what you want to/what you should read. Instead of considering exchangeable random variables, the usual way of thinking independence, which started by C.Stein (Stein's original paper), is to consider independent pairs of random variables. This is also natural from a categorical view since we can only discuss the commutativity of one diagram (commutativity of diagrams is equivalent to exchangeability if we formalized the category appropriately, see Category-theoretic structure for conditional independence.)

The definition given in [Lester Mackey et.al] is:

Let $Z$ and $Z′$ be random variables taking values in a Polish space $\mathcal{Z}$. We say that $(Z, Z′)$ is an exchangeable pair if it has the same distribution as $(Z′,Z)$. In particular, $Z$ and $Z′$ must share the same distribution.

[Arcones] Arcones, Miguel A. "A Bernstein-type inequality for U-statistics and U-processes." Statistics & probability letters 22.3 (1995): 239-247.

[Lester Mackey et.al] Mackey, Lester, et al. "Matrix concentration inequalities via the method of exchangeable pairs." The Annals of Probability 42.3 (2014): 906-945. https://arxiv.org/pdf/1201.6002.pdf

Answer 2

I might have misunderstood.

But it seems that for the first point, your proof does not work in general since there will be a $\mathbb{E}(U|G)$ and not $\mathbb{E}(U)$. And from then I do not see how to conclude.