What type of study is this?

This is a Quantitative Study study.

October 8, 2025Open Access

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

DHDirk van der HoevenLeiden University JOJulia Olkhovskaia TETim van ErvenUniversité Paris-Sud

Key Points

The proposed estimator significantly reduces KL divergence with high probability under certain conditions.
In the worst case, KL divergence bounds depend on sample size and support size, impacting accuracy.
The study provides both upper and lower bounds for KL divergence, demonstrating its broad implications.
With sufficient observations, the maximum likelihood estimator meets criteria indicating a reliable estimate.

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 p, with probability at least δ, KL (p \| p) C\K, (K) (1/δ) \/n, where n is the sample size and C > 0 is a constant. We introduce a computationally efficient estimator p^OTB, based on Online to Batch conversion and suffix averaging, and show that with probability at least 1 - δ KL (p \| p) C (K ( (K) ) + (K) (1/δ) ) /n. Furthermore, we also show that with sufficiently many observations relative to (1/δ), the maximum likelihood estimator p guarantees that with probability at least 1-δ 1/6 χ² (p\|p) 1/4 χ² (p\|p) KL (p|p) C (K + (1/δ) ) /n\, , where χ² denotes the χ²-divergence.

AI에게 질문

Bookmark

View Full Paper