Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

By Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith. 2007

147 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, background): “…closely to the classic problem of parameter estimation in statistics, and recent advances have pinpointed the optimal rates for functionals such as entropy, support size, and many others (see for instance [Pan04, RRSS09, VV11, JVYW15, WY16, AOST17, JVHW17, ADOS17] for some of the most recent work).”
Distribution Testing Lower Bounds via Reductions from Communication Complexity (2019, background): “Starting with [32, 10, 8], this includes the testing of symmetric properties [45, 54, 51, 52], of structured families [11, 35, 3, 17, 4, 20, 19], as well as testing under some assumption on the unknown instance [47, 24, 27, 26].”
INSPECTRE: Privately Estimating the Unseen (2018, background): “To circumvent this issue, (Raskhodnikova et al., 2009) proposed to study the problem when the smallest probability is bounded.”
Introduction to Property Testing (2017, background): “29 builds on [232], which presents two n-grained distributions with vastly different support sizes (i.”
Testing Properties of Collections of Distributions (2013, methodology): “Our analysis uses a technique called Poissonization [47] (which was used in the past in the context of lower bounds for testing and estimating properties of distributions in [42, 48, 49]), and hence we first introduce some preliminaries concerning Poisson distributions.”
A CLT and tight lower bounds for estimating entropy (2010, background): “We explicitly exhibit such a family of pairs of distributions D,D′ via a Laguerre polynomial construction that may be of independent interest.”
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs (2011, background): “The first strong lower bounds for additively approximating the support size were given in [35], showing that for any constant δ > 0, any estimator that obtains additive error at most (1/2−δ)n with probability at least 2/3 requires at least n/2 √ logn·log logn) samples.”
An Automatic Inequality Prover and Instance Optimal Identity Testing (2014, unknown): “[6], [4], [10], [11], [12], [3], [8]), and on establishing lower bounds [14], [18].”
Instance optimal learning of discrete distributions (2016, background): “…a long line of work considering distributional property testing, estimation, and learning questions from a worst case standpoint—typically parameterized via an upper bound on the support size of the distribution from which the samples are drawn (e.g. [8, 31, 5, 24, 10, 30, 36, 33, 32, 12, 34]).”
A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions (2017, background): “Motivated by databases, where each entry appears at least once, (Raskhodnikova et al., 2009) considered distributions whose non-zero probabilities are at least 1 k , ∆≥ 1 k def = {p ∈ ∆ : p(x) ∈ {0} ∪ [1/k, 1]} ,”
Chebyshev polynomials, moment matching, and optimal estimation of the unseen (2015, background): “To prevent the triviality, a conventional assumption [30] is to impose a lower bound on the non-zero probabilities.”
The Power of Linear Estimators (2011, background): “The first strong lower bounds for additively approximating the support size were given in [24], showing that for any constant ε ∈ (0, 12 ), any estimator that obtains additive error at most εn with probability at least 2/3 requires at least n/2 √ logn⋅log log n)”