Open Problems:81 - Revision history

Krzysztof Onak: cleaning the header

2017-11-08T06:04:42Z

cleaning the header

Krzysztof Onak: Krzysztof Onak moved page Waiting:Rényi entropy estimation to Open Problems:81 without leaving a redirect: The problem is ready for publication

2017-11-08T06:03:42Z

Krzysztof Onak moved page Waiting:Rényi entropy estimation to Open Problems:81 without leaving a redirect: The problem is ready for publication

Ccanonne at 05:08, 20 October 2017

2017-10-20T05:08:45Z

Ccanonne at 05:06, 20 October 2017

2017-10-20T05:06:30Z

Ccanonne at 05:02, 20 October 2017

2017-10-20T05:02:09Z

Ccanonne: Created page with "{{Header |source=focs17 |who=Jayadev Acharya }} For any $\alpha \geq 0$, the ''Rényi entropy of order $\alpha$'' of a probability distribution $p$ over a discrete domain $\Om..."

2017-10-20T05:01:49Z

Created page with "{{Header |source=focs17 |who=Jayadev Acharya }} For any $\alpha \geq 0$, the ''Rényi entropy of order $\alpha$'' of a probability distribution $p$ over a discrete domain $\Om..."

New page

{{Header
|source=focs17
|who=Jayadev Acharya
}}
For any $\alpha \geq 0$, the ''Rényi entropy of order $\alpha$'' of a probability distribution $p$ over a discrete domain $\Omega$ is defined as
$$
H_\alpha(p) = \frac{1}{1-\alpha}\log\sum_{x\in\Omega} p(x)^\alpha
$$
for $\alpha\neq 1$, and $H_1(p) = \lim_{\alpha\to 1} H_\alpha(p)$.
In particular, $H_1$ corresponds to the Shannon entropy $H(p)=-\sum_{x\in\Omega} p(x) \log p(x)$. The problem of estimation Rényi entropy of a distribution $p$, given i.i.d. samples from it, was studied in {{cite|Acharya-17}}, where the authors obtain tight bounds for every integer $\alpha\neq 1$, and nearly-tight ones for every non-integer $\alpha \geq 0$. In the later, however, the sample complexity is only known up to a subpolynomial factor: resolving the exact dependence on $\alpha$ and the alphabet size would be interesting.

@@ Line 9: / Line 9: @@
 $$
 for $\alpha\neq 1$, and $H_1(p) = \lim_{\alpha\to 1} H_\alpha(p)$.
-In particular, $H_1$ corresponds to the Shannon entropy $H(p)=-\sum_{x\in\Omega} p(x) \log p(x)$. The problem of estimation Rényi entropy of a distribution $p$, given i.i.d. samples from it, was studied in {{cite|AcharyaOST-17}}, where the authors obtain tight bounds for every integer $\alpha\neq 1$, and nearly-tight ones for every non-integer $\alpha \geq 0$. In the later, however, the sample complexity is only known up to a subpolynomial factor: resolving the exact dependence on $\alpha$ and the alphabet size would be interesting.
+In particular, $H_1$ corresponds to the Shannon entropy $H(p)=-\sum_{x\in\Omega} p(x) \log p(x)$. The problem of estimation Rényi entropy of a distribution $p$, given i.i.d. samples from it, was studied in {{cite|AcharyaOST-17}}, where the authors obtain tight bounds for every integer $\alpha\neq 1$, and nearly-tight ones for every non-integer $\alpha \geq 0$. In the later case, however, the sample complexity is only known up to a subpolynomial factor: resolving the exact dependence on $\alpha$ and the alphabet size would be interesting.

@@ Line 2: / Line 2: @@
 |source=focs17
 |who=Jayadev Acharya
 }}
 For any $\alpha \geq 0$, the ''Rényi entropy of order $\alpha$'' of a probability distribution $p$ over a discrete domain $\Omega$ is defined as

← Older revision	Revision as of 06:03, 8 November 2017
(No difference)