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 (?)

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.

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.

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 (?)