Author: Eiko

Time: 2025-02-17 13:04:14 - 2025-02-17 13:04:14 (UTC)

High Dimensional Statistics

• Concentration and its uses

• Sub-Gaussian random variables

• Sub-Exponential random variables

Concentration

Let $X_i$ be a sequence of i.i.d random variables

Basic Concentration Inequality

$$\mathbb{P}[f(|X-\mu |)\ge f(t)]\le \underset{f}{min}\frac{\mathbb{E}f(|X-\mu |)}{f(t)}$$

U-Statistics

Canonical statistics $\sum X_i/n\sim \mathbb{E}X$, suppose we want to estimate $\mathbb{E}|X_1-X_2|$, we would consider using $\sum _{i<j}\frac{|x_i-x_j|}{(\genfrac{}{}{0ex}{}{n}{2})}$.

The $U$-statistics are of the form

$$U=\frac{1}{(\genfrac{}{}{0ex}{}{n}{2})}\sum _{i<j}g(x_i,x_j)$$

where $g$ is a symmetric function of two variables.

Imagine that we have $\parallel g{\parallel }_{\mathrm{\infty }}<b$ or assume $|x|<b$,

$$\begin{array}{rl}U(x_1,\dots ,x_n)-U(x_1,\dots ,x_j^{\prime },\dots ,x_n)|& \le \frac{1}{(\genfrac{}{}{0ex}{}{n}{2})}\sum _{i,i\ne j}|g(x_i,x_j)-g(x_i,x_j^{\prime })|\\ & \le \frac{2b(n-1)}{(\genfrac{}{}{0ex}{}{n}{2})}\\ & =\frac{4b}{n}.\end{array}$$

$$\mathbb{P}(|U-\mathbb{E}U|\ge t)\le 2\exp (-\frac{n{t}^2}{8b^2}).$$