Concentration Bounds for Discrete Distribution Estimation in KL Divergence

Clément L. Canonne, Ziteng Sun, Ananda Theertha Suresh
2/14/2023
stat.MLcs.DMcs.IT

No confident code implementation found for this paper.

Abstract

We study the problem of discrete distribution estimation in KL divergence and provide concentration bounds for the Laplace estimator. We show that the deviation from mean scales as $\sqrt{k}/n$ when $n \ge k$, improving upon the best prior result of $k/n$. We also establish a matching lower bound that shows that our bounds are tight up to polylogarithmic factors.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

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

81% match2025

Discrete Diffusion Models: Novel Analysis and New Sampler Guarantees

78% match2025

Estimation of discrete distributions in relative entropy, and the deviations of the missing mass

78% match2025

Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis

78% match2026

Nearly d-Linear Convergence Bounds for Diffusion Models via Stochastic Localization

77% match2026

Convergence Analysis of Discrete Diffusion Model: Exact Implementation through Uniformization

77% match2024

Cite this paper

@article{canonne2023concentration,
  title  = {Concentration Bounds for Discrete Distribution Estimation in KL Divergence},
  author = {Clément L. Canonne and Ziteng Sun and Ananda Theertha Suresh},
  year   = {2023},
  eprint = {2302.06869},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2302.06869v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2302.06869.svg)](https://codeofpaper.com/paper/2302.06869)

Discussion