Estimating the Unseen - An n/log(n)-Sample Estimator for Entropy and Support Size - Shown Optimal via New CLTs

Sep 4, 2026

Upload by Himbo

Presents a new characterization of the unobserved portion of a distribution, yielding sublinear-sample estimators with arbitrarily small additive constant error for properties including entropy and distribution support size. Provides matching lower bounds to resolve longstanding questions about sample complexity up to constant factors. Gives an algorithm using O(n/log n) samples, with linear time in the sample size, and proves Ω(n/log n) lower bounds. Uses new multivariate central limit theorems for generalized multinomial distributions.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages10

Reading Time25 min

AccessFree to download

Abstract

Introduction

Problem background: unobserved distribution mass

Main contributions: estimators and lower bounds

Estimating the Unseen: An n/log(n)-sample Estimator for Entropy and Support Size, Shown Optimal via New CLTs∗ † Gregory Valiant UC Berkeley Berkeley, California [gregory.valiant@gmail.com](gregory.valiant@gmail.com) Paul Valiant‡ UC Berkeley Berkeley, California [pvaliant@gmail.com](pvaliant@gmail.com) ABSTRACT We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear– sample estimators achieving arbitrarily small additive constant error for a class of properties that includes entropy and distribution support size. Additionally, we show new matching lower bounds. Together, this settles the longstanding question of the sample complexities of these estimation problems, up to constant factors. Our algorithm estimates these properties up to an arbitrarily small additive constant, using O (n/ log n) samples, where n is a bound on the support size, or in the case of estimating the support size, 1/n is a lower bound on the probability of any element of the domain. Previously, no explicit sublinear–sample algorithms for either of these problems were known. Our algorithm is also computationally extremely eﬃcient, running in time linear in the number of samples used. In the second half of the paper, we provide a matching lower bound of Ω(n/ log n) samples for estimating entropy or distribution support size to within an additive constant. The previous lower-bounds on these sample complexities weren/2O ( √log n) . To show our lower bound, we prove two new and natural multivariate central limit theorems (CLTs); the ﬁrst uses Stein’s method to relate the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance metric (also known as the Wasserstein metric) . We leverage this central limit theorem to prove a stronger but more speciﬁc central limit theorem for “generalized multinomial”distributions—a large class of discrete distributions, parameterized by matri- ∗Preliminary full versions, [39] and [40], available at: [http://www.eccc.uni-trier.de/report/2010/179](http://www.eccc.uni-trier.de/report/2010/179) and [http://www.eccc.uni-trier.de/report/2010/180](http://www.eccc.uni-trier.de/report/2010/180)[ ](http://www.eccc.uni-trier.de/report/2010/180)†Supported by an NSF graduate research fellowship.‡Supported by an NSF postdoctoral research fellowship. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for proﬁt or commercial advantage and that copies bear this notice and the full citation on the ﬁrst page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior speciﬁc permission and/or a fee. STOC’11, June 6–8, 2011, San Jose, California, USA. Copyright 2011 ACM 978-1-4503-0691-1/11/06 ...$10.00 . ces, that represents sums of independent binomial or multinomial distributions, and describes many distributions encountered in computer science. Convergence here is in the strong sense of statistical distance, which immediately implies that any algorithm with input drawn from a generalized multinomial distribution behaves essentially as if the input were drawn from a discretized Gaussian with the same mean and covariance. Such tools in the multivariate setting are rare, and we hope this new tool will be of use to the community. Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]: Miscellaneous General Terms: Algorithms, Theory. 1. INTRODUCTION Given samples from an unknown discrete distribution, what can we infer about the distribution? The empirical distribution of the samples roughly captures the portion of the distribution which we have observed, but what can we say about the unobserved portion of the distribution? Answers to this question are, at least implicitly, central to many estima

FAQs

What estimation problems does the paper address?

It focuses on estimating the entropy of a discrete distribution and estimating the distribution support size, emphasizing the unobserved portion of the distribution.

How many samples does the proposed method use?

The algorithm estimates entropy and support size within an arbitrarily small additive constant using O(n/log n) samples, where n bounds the support size.

How are the matching lower bounds proved?

The lower bound proof relies on new multivariate central limit theorems, using Stein’s method under the Wasserstein (earthmover) distance and applying them to generalized multinomial distributions.

Sep 4, 2026

Upload by Himbo