Estimating the unseen, improved estimators for entropy and other properties

DOI10.1145/3125643MaRDI QIDQ4640345zbMATH OpenOpenAlexFDO

Authors Gregory Valiant, Paul Valiant

Publication date 17 May 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3125643

zbMATH Keywords

distinct elementsentropy estimationstatistical property estimationunseen species

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Nonparametric estimation (62G05)

Recommendations

• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• Approximating entropy from sublinear samples
• Sublinear estimation of entropy and information distances
• Instance optimal learning of discrete distributions
• The complexity of estimating Rényi entropy

Cited in

(23)

• Chebyshev polynomials, moment matching, and optimal estimation of the unseen
• Sample complexity of the distinct elements problem
• Optimal disclosure risk assessment
• Minimax optimal conditional independence testing
• Guessing probability distributions from small samples
• Estimation of Wasserstein distances in the spiked transport model
• Approximating entropy from sublinear samples
• The subgraph testing model
• Efficient profile maximum likelihood for universal symmetric property estimation
• Approximate profile maximum likelihood
• Instance optimal learning of discrete distributions
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs
• A lower bound on the complexity of testing grained distributions
• A probability approximation framework: Markov process approach
• Testing distributions of huge objects
• Near-optimal estimation of the unseen under regularly varying tail populations
• Space-optimal profile estimation in data streams with applications to symmetric functions
• Support testing in the huge object model
• A scalable entropy estimator
• Complexity of high-dimensional identity testing with coordinate conditional sampling
• Sample efficient identity testing and independence testing of quantum states
• On distributed differential privacy and counting distinct elements
• New statistical and computational results for learning junta distributions

This page was built for publication: Estimating the unseen, improved estimators for entropy and other properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640345)