Centralized concentration conjecture for empirical relative entropy

At least 7 years old · documented by

Let PP be a distribution on a finite alphabet of size kk, let P^n,k\hat{P}_{n,k} be its empirical distribution from nn independent samples, and let D(P^n,k∥P)D(\hat{P}_{n,k} \| P) denote the relative entropy. There exist constants g1>0g_1>0 and g2>0g_2>0 such that, for every t>0t>0, Centralized concentration conjecture.

P(∣D(P^n,k∥P)−E[D(P^n,k∥P)]∣≥t)≤g1e−g2min⁡{n2t2k−1,nt}.\mathbb{P}\left(\left|D(\hat{P}_{n,k} \| P)-\mathbb{E}[D(\hat{P}_{n,k} \| P)]\right| \geq t \right) \leq g_1 e^{-g_2 \min\left\{ \frac{n^2t^2}{k-1}, nt \right\}}.

This conjecture is motivated by the asymptotic chi-squared behavior of 2nD(P^n,k∥P)2nD(\hat{P}_{n,k}\|P) and standard concentration bounds for sub-exponential random variables. The source does not indicate that it has been proved or disproved.

References

Primary source

Jay Mardia, Jiantao Jiao, Ervin Tánczos, Robert D. Nowak and Tsachy Weissman, “Concentration Inequalities for the Empirical Distribution”, arXiv:1809.06522 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.