{"id":5559,"date":"2025-07-24T07:04:24","date_gmt":"2025-07-24T07:04:24","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/07\/24\/2507-17316\/"},"modified":"2025-07-24T07:04:24","modified_gmt":"2025-07-24T07:04:24","slug":"2507-17316","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/07\/24\/2507-17316\/","title":{"rendered":"Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability"},"content":{"rendered":"

Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

arXiv:2507.17316v1 Announce Type: new
\nAbstract: We consider the problem of estimating a discrete distribution $p$ with support of size $K$ and provide both upper and lower bounds with high probability in KL divergence. We prove that in the worst case, for any estimator $widehat{p}$, with probability at least $delta$, $text{KL}(p | widehat{p}) geq Cmax{K,ln(K)ln(1\/delta) }\/n $, where $n$ is the sample size and $C > 0$ is a constant. We introduce a computationally efficient estimator $p^{text{OTB}}$, based on Online to Batch conversion and suffix averaging, and show that with probability at least $1 – delta$ $text{KL}(p | widehat{p}) leq C(Klog(log(K)) + ln(K)ln(1\/delta)) \/n$.
\n Furthermore, we also show that with sufficiently many observations relative to $log(1\/delta)$, the maximum likelihood estimator $bar{p}$ guarantees that with probability at least $1-delta$ $$
\n 1\/6 chi^2(bar{p}|p) leq 1\/4 chi^2(p|bar{p}) leq text{KL}(p|bar{p}) leq C(K + log(1\/delta))\/n,, $$ where $chi^2$ denotes the $chi^2$-divergence.<\/div>\n

\t

\n
<\/BR>
\n Dirk van der Hoeven, Julia Olkhovskaia, Tim van Erven
\n \t

\n
<\/BR>
\nGo to original source<\/a>
\n \t

\n
<\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability arXiv:2507.17316v1 Announce Type: new Abstract: We consider the problem of estimating a discrete distribution $p$ with support of size $K$ and provide both upper and lower bounds with high probability in KL divergence. We prove that in the worst case, for any estimator $widehat{p}$, […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,113,112],"tags":[3313,3314,921],"class_list":["post-5559","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-cs-lg","category-stat-ml","tag-delta","tag-divergence","tag-probability"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/5559"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=5559"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/5559\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=5559"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=5559"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=5559"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}