Concentration Bounds for Discrete Distribution Estimation in KL Divergence Article Swipe

PDF

Clément L. Canonne , Ziteng Sun , Ananda Theertha Suresh ·

YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2302.06869

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.

Related Topics

Mathematical Analysis

Philosophy

Management

Economics

Concepts

Divergence (linguistics) Estimator Matching (statistics) Upper and lower bounds Mathematics Distribution (mathematics) Combinatorics Kullback–Leibler divergence Laplace transform Laplace distribution Estimation Relative standard deviation Applied mathematics Statistics Mathematical analysis Detection limit Philosophy Linguistics Management Economics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2302.06869
PDF: https://arxiv.org/pdf/2302.06869
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4321012209

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4321012209

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2302.06869

Digital Object Identifier
Title: Concentration Bounds for Discrete Distribution Estimation in KL Divergence

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2023

Year of publication
Publication date: 2023-02-14

Full publication date if available
Authors: Clément L. Canonne, Ziteng Sun, Ananda Theertha Suresh

List of authors in order
Landing page: https://arxiv.org/abs/2302.06869

Publisher landing page
PDF URL: https://arxiv.org/pdf/2302.06869

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2302.06869

Direct OA link when available
Concepts: Divergence (linguistics), Estimator, Matching (statistics), Upper and lower bounds, Mathematics, Distribution (mathematics), Combinatorics, Kullback–Leibler divergence, Laplace transform, Laplace distribution, Estimation, Relative standard deviation, Applied mathematics, Statistics, Mathematical analysis, Detection limit, Philosophy, Linguistics, Management, Economics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4321012209
doi	https://doi.org/10.48550/arxiv.2302.06869
ids.doi	https://doi.org/10.48550/arxiv.2302.06869
ids.openalex	https://openalex.org/W4321012209
fwci
type	preprint
title	Concentration Bounds for Discrete Distribution Estimation in KL Divergence
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10136
topics[0].field.id	https://openalex.org/fields/26
topics[0].field.display_name	Mathematics
topics[0].score	0.9970999956130981
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2613
topics[0].subfield.display_name	Statistics and Probability
topics[0].display_name	Statistical Methods and Inference
topics[1].id	https://openalex.org/T11871
topics[1].field.id	https://openalex.org/fields/26
topics[1].field.display_name	Mathematics
topics[1].score	0.9778000116348267
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2613
topics[1].subfield.display_name	Statistics and Probability
topics[1].display_name	Advanced Statistical Methods and Models
topics[2].id	https://openalex.org/T12072
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9732000231742859
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1702
topics[2].subfield.display_name	Artificial Intelligence
topics[2].display_name	Machine Learning and Algorithms
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C207390915
concepts[0].level	2
concepts[0].score	0.8034775853157043
concepts[0].wikidata	https://www.wikidata.org/wiki/Q1230525
concepts[0].display_name	Divergence (linguistics)
concepts[1].id	https://openalex.org/C185429906
concepts[1].level	2
concepts[1].score	0.730282187461853
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1130160
concepts[1].display_name	Estimator
concepts[2].id	https://openalex.org/C165064840
concepts[2].level	2
concepts[2].score	0.6781275868415833
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1321061
concepts[2].display_name	Matching (statistics)
concepts[3].id	https://openalex.org/C77553402
concepts[3].level	2
concepts[3].score	0.6258604526519775
concepts[3].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[3].display_name	Upper and lower bounds
concepts[4].id	https://openalex.org/C33923547
concepts[4].level	0
concepts[4].score	0.6135848164558411
concepts[4].wikidata	https://www.wikidata.org/wiki/Q395
concepts[4].display_name	Mathematics
concepts[5].id	https://openalex.org/C110121322
concepts[5].level	2
concepts[5].score	0.5832680463790894
concepts[5].wikidata	https://www.wikidata.org/wiki/Q865811
concepts[5].display_name	Distribution (mathematics)
concepts[6].id	https://openalex.org/C114614502
concepts[6].level	1
concepts[6].score	0.5589588284492493
concepts[6].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[6].display_name	Combinatorics
concepts[7].id	https://openalex.org/C171752962
concepts[7].level	2
concepts[7].score	0.5411104559898376
concepts[7].wikidata	https://www.wikidata.org/wiki/Q255166
concepts[7].display_name	Kullback–Leibler divergence
concepts[8].id	https://openalex.org/C97937538
concepts[8].level	2
concepts[8].score	0.47452986240386963
concepts[8].wikidata	https://www.wikidata.org/wiki/Q199691
concepts[8].display_name	Laplace transform
concepts[9].id	https://openalex.org/C183057437
concepts[9].level	3
concepts[9].score	0.4726133644580841
concepts[9].wikidata	https://www.wikidata.org/wiki/Q671617
concepts[9].display_name	Laplace distribution
concepts[10].id	https://openalex.org/C96250715
concepts[10].level	2
concepts[10].score	0.41970905661582947
concepts[10].wikidata	https://www.wikidata.org/wiki/Q965330
concepts[10].display_name	Estimation
concepts[11].id	https://openalex.org/C51989270
concepts[11].level	3
concepts[11].score	0.41461506485939026
concepts[11].wikidata	https://www.wikidata.org/wiki/Q623738
concepts[11].display_name	Relative standard deviation
concepts[12].id	https://openalex.org/C28826006
concepts[12].level	1
concepts[12].score	0.40843090415000916
concepts[12].wikidata	https://www.wikidata.org/wiki/Q33521
concepts[12].display_name	Applied mathematics
concepts[13].id	https://openalex.org/C105795698
concepts[13].level	1
concepts[13].score	0.31512704491615295
concepts[13].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[13].display_name	Statistics
concepts[14].id	https://openalex.org/C134306372
concepts[14].level	1
concepts[14].score	0.2031014859676361
concepts[14].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[14].display_name	Mathematical analysis
concepts[15].id	https://openalex.org/C119128265
concepts[15].level	2
concepts[15].score	0.0
concepts[15].wikidata	https://www.wikidata.org/wiki/Q900165
concepts[15].display_name	Detection limit
concepts[16].id	https://openalex.org/C138885662
concepts[16].level	0
concepts[16].score	0.0
concepts[16].wikidata	https://www.wikidata.org/wiki/Q5891
concepts[16].display_name	Philosophy
concepts[17].id	https://openalex.org/C41895202
concepts[17].level	1
concepts[17].score	0.0
concepts[17].wikidata	https://www.wikidata.org/wiki/Q8162
concepts[17].display_name	Linguistics
concepts[18].id	https://openalex.org/C187736073
concepts[18].level	1
concepts[18].score	0.0
concepts[18].wikidata	https://www.wikidata.org/wiki/Q2920921
concepts[18].display_name	Management
concepts[19].id	https://openalex.org/C162324750
concepts[19].level	0
concepts[19].score	0.0
concepts[19].wikidata	https://www.wikidata.org/wiki/Q8134
concepts[19].display_name	Economics
keywords[0].id	https://openalex.org/keywords/divergence
keywords[0].score	0.8034775853157043
keywords[0].display_name	Divergence (linguistics)
keywords[1].id	https://openalex.org/keywords/estimator
keywords[1].score	0.730282187461853
keywords[1].display_name	Estimator
keywords[2].id	https://openalex.org/keywords/matching
keywords[2].score	0.6781275868415833
keywords[2].display_name	Matching (statistics)
keywords[3].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[3].score	0.6258604526519775
keywords[3].display_name	Upper and lower bounds
keywords[4].id	https://openalex.org/keywords/mathematics
keywords[4].score	0.6135848164558411
keywords[4].display_name	Mathematics
keywords[5].id	https://openalex.org/keywords/distribution
keywords[5].score	0.5832680463790894
keywords[5].display_name	Distribution (mathematics)
keywords[6].id	https://openalex.org/keywords/combinatorics
keywords[6].score	0.5589588284492493
keywords[6].display_name	Combinatorics
keywords[7].id	https://openalex.org/keywords/kullback–leibler-divergence
keywords[7].score	0.5411104559898376
keywords[7].display_name	Kullback–Leibler divergence
keywords[8].id	https://openalex.org/keywords/laplace-transform
keywords[8].score	0.47452986240386963
keywords[8].display_name	Laplace transform
keywords[9].id	https://openalex.org/keywords/laplace-distribution
keywords[9].score	0.4726133644580841
keywords[9].display_name	Laplace distribution
keywords[10].id	https://openalex.org/keywords/estimation
keywords[10].score	0.41970905661582947
keywords[10].display_name	Estimation
keywords[11].id	https://openalex.org/keywords/relative-standard-deviation
keywords[11].score	0.41461506485939026
keywords[11].display_name	Relative standard deviation
keywords[12].id	https://openalex.org/keywords/applied-mathematics
keywords[12].score	0.40843090415000916
keywords[12].display_name	Applied mathematics
keywords[13].id	https://openalex.org/keywords/statistics
keywords[13].score	0.31512704491615295
keywords[13].display_name	Statistics
keywords[14].id	https://openalex.org/keywords/mathematical-analysis
keywords[14].score	0.2031014859676361
keywords[14].display_name	Mathematical analysis
language	en
locations[0].id	pmh:oai:arXiv.org:2302.06869
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2302.06869
locations[0].version	submittedVersion
locations[0].raw_type
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2302.06869
locations[1].id	doi:10.48550/arxiv.2302.06869
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2302.06869
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5071869723
authorships[0].author.orcid	https://orcid.org/0000-0001-7153-5211
authorships[0].author.display_name	Clément L. Canonne
authorships[0].author_position	first
authorships[0].raw_author_name	Canonne, Clément L.
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5001128596
authorships[1].author.orcid
authorships[1].author.display_name	Ziteng Sun
authorships[1].author_position	middle
authorships[1].raw_author_name	Sun, Ziteng
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5103890688
authorships[2].author.orcid
authorships[2].author.display_name	Ananda Theertha Suresh
authorships[2].author_position	last
authorships[2].raw_author_name	Suresh, Ananda Theertha
authorships[2].is_corresponding	False
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2302.06869
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Concentration Bounds for Discrete Distribution Estimation in KL Divergence
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10136
primary_topic.field.id	https://openalex.org/fields/26
primary_topic.field.display_name	Mathematics
primary_topic.score	0.9970999956130981
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2613
primary_topic.subfield.display_name	Statistics and Probability
primary_topic.display_name	Statistical Methods and Inference
related_works	https://openalex.org/W2105321464, https://openalex.org/W2887774187, https://openalex.org/W2388220555, https://openalex.org/W2485409820, https://openalex.org/W3048739257, https://openalex.org/W1665563134, https://openalex.org/W2963604926, https://openalex.org/W1616881371, https://openalex.org/W1520875569, https://openalex.org/W2199957582
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2302.06869
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2302.06869
best_oa_location.version	submittedVersion
best_oa_location.raw_type
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2302.06869
primary_location.id	pmh:oai:arXiv.org:2302.06869
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2302.06869
primary_location.version	submittedVersion
primary_location.raw_type
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2302.06869
publication_date	2023-02-14
publication_year	2023
referenced_works_count	0
abstract_inverted_index.a	44
abstract_inverted_index.$n	30
abstract_inverted_index.KL	9
abstract_inverted_index.We	0, 19, 41
abstract_inverted_index.as	27
abstract_inverted_index.in	8
abstract_inverted_index.of	4, 39
abstract_inverted_index.to	56
abstract_inverted_index.up	55
abstract_inverted_index.\ge	31
abstract_inverted_index.and	11
abstract_inverted_index.are	53
abstract_inverted_index.for	15
abstract_inverted_index.k$,	32
abstract_inverted_index.our	51
abstract_inverted_index.the	2, 16, 22, 35
abstract_inverted_index.also	42
abstract_inverted_index.best	36
abstract_inverted_index.from	24
abstract_inverted_index.mean	25
abstract_inverted_index.show	20
abstract_inverted_index.that	21, 48, 50
abstract_inverted_index.upon	34
abstract_inverted_index.when	29
abstract_inverted_index.bound	47
abstract_inverted_index.lower	46
abstract_inverted_index.prior	37
abstract_inverted_index.shows	49
abstract_inverted_index.study	1
abstract_inverted_index.tight	54
abstract_inverted_index.$k/n$.	40
abstract_inverted_index.bounds	14, 52
abstract_inverted_index.result	38
abstract_inverted_index.scales	26
abstract_inverted_index.Laplace	17
abstract_inverted_index.problem	3
abstract_inverted_index.provide	12
abstract_inverted_index.discrete	5
abstract_inverted_index.factors.	58
abstract_inverted_index.matching	45
abstract_inverted_index.deviation	23
abstract_inverted_index.establish	43
abstract_inverted_index.improving	33
abstract_inverted_index.divergence	10
abstract_inverted_index.estimation	7
abstract_inverted_index.estimator.	18
abstract_inverted_index.$\sqrt{k}/n$	28
abstract_inverted_index.distribution	6
abstract_inverted_index.concentration	13
abstract_inverted_index.polylogarithmic	57
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile