1
$\begingroup$

Let $P=(p_1,\ldots,p_k) \in \Delta_k$ be distribution supported on set of size $k$ and let $\hat{P}_n$ be an empirical version of $P$ based on an iid sample of size $n$.

Question

What's a good non-asymptotic tail-bound of the form $\text{Proba}(\|\hat{P}_n-P\|_2^2 \le \epsilon) \ge 1 - \delta$ ?


Take 1

One may write $\hat{P}_n = (X_1/n,\ldots,X_k/n)$, where $X_j$ is the number of times $j$ was observed in the sample. It's clear that $(X_1,\ldots,X_k) \sim \text{Multinomial}(p_1,\ldots,p_k)$.

Now, $\|\hat{P}_n-P\|_2^2 = (1/n^2)\sum_{j=1}^k (X_j-np_j)^2$, and so to have $\|\hat{P}_n-P\|_2 \le \epsilon$, it suffices to have $|X_j-np_j| \le n^2\epsilon^2/k$. Noting that $X_j$ has mean $\mathbb E[X_j] = np_j$ and variance $\operatorname{Var}[X_j] =np_j(1-p_j) \le n/4$, we may apply Hoeffding's inequality to obtain that

$|X_j-np_j| \ge \epsilon$ with probability at most $2\exp(-(n^2\epsilon^2/k)/2(n/4))=2\exp(-n\epsilon^2/k)$.

A direct computation then gives $$ \begin{split} \text{Proba}(\|\hat{P}_n-P\|_2^2 \le \epsilon) &= \text{Proba}(\sum_{j=1}^k (X_j-np_j)^2 \le n^2\epsilon^2) \ge \text{ Proba}(|X_j-np_j| \le n^2\epsilon^2/k\;\forall j)\\ &=1-\text{Proba}(\exists j\;|X_j-np_j| \ge n^2\epsilon^2/k)\\ & \overset{(a)}{\ge} 1 - \sum_{j=1}^k\text{Proba}(|X_j-np_j| \ge n^2\epsilon^2/k) \overset{(b)}{\ge} 1-2k\exp(-n\epsilon^2/k), \end{split} $$ where (a) is a union bound and (b) is Hoeffding bound obtained earlier.

Disclaimer: The multiplicative factor $k$ in the above bound is probably suboptimal.

$\endgroup$
2
  • 1
    $\begingroup$ Note that in the question you compare the squared norm of $P_n-P$ to $\epsilon$ while in Take 1 you consider the norm itself. $\endgroup$ May 20, 2019 at 8:33
  • $\begingroup$ That's a typo. Thanks. $\endgroup$
    – dohmatob
    May 20, 2019 at 17:08

2 Answers 2

1
$\begingroup$

I will answer the question as stated though I am not sure you wanted to square the norm of $P_n-P$. Let $e_1,\ldots,e_k$ be the standard basis of ${\bf R}^k$. Write $\mu:=\sum_{j=1}^k p_j e_j$. Let $d_t$ be independent random variables for $t=1,\ldots,n$ with ${\bf Pr}[d_t=(e_i-\mu)/\sqrt{n}]=p_i$ for $i=1,\ldots,k$. Then ${\bf Pr}[\| P_n-P\|_2^2 \ge \epsilon]= {\bf Pr}[\|\sum_{t=1}^n d_t \| \ge \sqrt{n\epsilon}] \le 2\exp(-n\epsilon/2)$ by Theorem 3 in [1]. This avoids the dependence on $k$ in the bound.

[1] Pinelis, Iosif. "An approach to inequalities for the distributions of infinite-dimensional martingales." In Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference, pp. 128-134. Birkhäuser, Boston, MA, 1992. See https://link.springer.com/chapter/10.1007/978-1-4612-0367-4_9#page-1

$\endgroup$
7
  • $\begingroup$ Nice. Also reference 1 is really nice. Thanks $\endgroup$
    – dohmatob
    May 20, 2019 at 17:09
  • $\begingroup$ Can you accept the answer? $\endgroup$ May 20, 2019 at 17:46
  • $\begingroup$ Answer accepted. $\endgroup$
    – dohmatob
    May 20, 2019 at 17:54
  • $\begingroup$ Hum, it seems this result would hold for countably supported (not just finitely supported) $P$. Also, unfortunately, I don't have access to ref [1]. I was wondering whether the ideas presented there can be used to bound a general $L_p$-norm (where $1 \le p \le \infty$, and my original problem corresponds to the case $p=2$) of $\hat{P}_n-P$ ? $\endgroup$
    – dohmatob
    May 21, 2019 at 5:59
  • $\begingroup$ Pinelis' paper covers $L^p$ for $p \ge 2$ provided $p$ is finite. I can send you the proof if you write to me at [email protected] Note the inequality definitely fails for $p=\infty$ where you need the $k$-dependence. $\endgroup$ May 21, 2019 at 7:47
3
$\begingroup$

A self-contained proof.

  • Step 1: $\mathbb{E} \|\hat{P}_n - P\|_2^2 \leq \frac{1}{n}$.
  • Step 2: McDiarmid's inequality.

Let $X_i$ be the number of samples of $i \in \{1,\dots,k\}$. Then $X_i \sim \text{Binom}(p_i,n)$. \begin{align*} \mathbb{E} \|\hat{P}_n - P\|_2^2 &= \frac{1}{n^2} \sum_{i=1}^k \mathbb{E} \left( X_i - \mathbb{E} X_i \right)^2 \\ &= \frac{1}{n^2} \sum_{i=1}^k \text{Var}(X_i) \\ &= \frac{1}{n^2} \sum_{i=1}^k n P(i) (1-P(i)) \\ &\leq \frac{1}{n^2} \sum_{i=1}^k n P(i) \\ &= \frac{1}{n} . \end{align*} Jensen's inequality now implies $\mathbb{E} \|\hat{P}_n - P\|_2 \leq \sqrt{\frac{1}{n}}$.

Now to apply McDiarmids, let $Y_j \in \{1,\dots,k\}$ be the $j$th sample, for $j=1,\dots,n$. Write $f(\vec{Y}) = \|\hat{P}_n - P\|_2$. Suppose we change $Y_j$ to $Y_j'$, changing $\hat{P}_n$ to $\hat{P}_n'$. Then the vector $v := \hat{P}_n - \hat{P}_n'$ has two nonzero entries, a $\frac{1}{n}$ and a $\frac{-1}{n}$, so $\|v\|_2 = \frac{\sqrt{2}}{n}$. By the triangle inequality, \begin{align*} \left| f(\vec{Y}) - f(\vec{Y}') \right| \leq \|v\|_2 = \frac{\sqrt{2}}{n} . \end{align*} So McDiarmid's gives \begin{align*} \Pr\left[ \|\hat{P}_n - P\|_2 \geq \sqrt{\frac{1}{n}} + \epsilon \right] \leq \exp\left(-n\epsilon^2 \right) . \end{align*}

In particular, assume $\epsilon \geq \sqrt{\frac{1}{n}}$ and let $\alpha = (2\epsilon)^2$:

For $\alpha \geq \frac{4}{n}$, \begin{align*} \Pr\left[ \|\hat{P}_n - P\|_2^2 \geq \alpha \right] \leq \exp\left( \frac{- n \alpha}{4}\right) . \end{align*}

I first learned of Step 1 here: https://cstheory.stackexchange.com/a/18498/8243

$\endgroup$
2
  • $\begingroup$ Excellent answer. Thanks! $\endgroup$
    – dohmatob
    May 21, 2019 at 5:49
  • $\begingroup$ Hum, it seems this result would hold for countably supported (not just finitely supported) $P$. Right ? $\endgroup$
    – dohmatob
    May 21, 2019 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.