Written By: Qingyang Xu (website)

Date Created: June 12, 2022

Last Modified: January 1, 2024

High-Dimensional Probability

Chapter 2. Concentrations of sums of independent RV

Date: June 12, 2022

2.1 Motivation

Goal: prove finite-sample concentration bounds $\mathbb{P}(|\frac{1}{N}\sum_i X_i-\mu|>t)$ of independent RV

Proposition 2.1.2 (Tails of normal distribution). Let $g \sim N(0, 1)$. Then for all $t>0$, we have

$$ \Big(\frac{1}{t} -\frac{1}{t^3} \Big) \phi(t) \le \mathbb{P}(g \ge t) \le \frac{1}{t} \phi(t) $$

Issue: approximating the tail probability using CLT yields exponential tail $\mathcal{O}(e^{-cN})$ but the approximation error $\mathcal{O}(1/\sqrt{N})$ is very large, due to the Berry-Esseen CLT

$$ |\mathbb{P}(Z_N \ge t)-\mathbb{P}(Z \ge t)| \le \frac{\rho}{\sqrt{N}} $$

Solution: use techniques (Hoeffding, Bernstein inequalities) which bypass CLT approximation for special distributions (sub-Gaussian, sub-exponential) which capture a large class of RV