Skip to main content
added 252 characters in body
Source Link
TOM
  • 2.3k
  • 13
  • 23

Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for $$P(||X_1+\cdots+X_n||_{2}>x)?$$

In particular, is it true, that the one dimensional case (Hoeffding's inequality) is the best? That is, is the latter probability at most $2\exp(-\frac{x^2}{2n})$$C_d\exp(-\frac{x^2}{2n})$? (the conctand $C=C_d$ is needed to account for the effects of the norm for $x$ small, that is, for $x<\sqrt{d}$ we can take all variables taking values $e_i$ and $-e_i$ with probability $1/2$, where $e_i$ stand for the usual basis of $\mathbb{R}^d$.

Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for $$P(||X_1+\cdots+X_n||_{2}>x)?$$

In particular, is it true, that the one dimensional case (Hoeffding's inequality) is the best? That is, is the latter probability at most $2\exp(-\frac{x^2}{2n})$?

Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for $$P(||X_1+\cdots+X_n||_{2}>x)?$$

In particular, is it true, that the one dimensional case (Hoeffding's inequality) is the best? That is, is the latter probability at most $C_d\exp(-\frac{x^2}{2n})$? (the conctand $C=C_d$ is needed to account for the effects of the norm for $x$ small, that is, for $x<\sqrt{d}$ we can take all variables taking values $e_i$ and $-e_i$ with probability $1/2$, where $e_i$ stand for the usual basis of $\mathbb{R}^d$.

Source Link
TOM
  • 2.3k
  • 13
  • 23

Best possible concentration inequality in high dimensions

Let $X_1,\ldots,X_n$ be independent random variables in $\mathbb{R}^d$ with $EX_i=0$ and $||X_i||_{2}\leq 1$. What is the best known exponential upper bound for $$P(||X_1+\cdots+X_n||_{2}>x)?$$

In particular, is it true, that the one dimensional case (Hoeffding's inequality) is the best? That is, is the latter probability at most $2\exp(-\frac{x^2}{2n})$?