Minimax estimation of functionals of discrete distributions

J Jiao, K Venkat, Y Han… - IEEE Transactions on …, 2015 - ieeexplore.ieee.org
We propose a general methodology for the construction and analysis of essentially minimax
estimators for a wide class of functionals of finite dimensional parameters, and elaborate on …

Minimax rates of entropy estimation on large alphabets via best polynomial approximation

Y Wu, P Yang - IEEE Transactions on Information Theory, 2016 - ieeexplore.ieee.org
Consider the problem of estimating the Shannon entropy of a distribution over k elements
from n independent samples. We show that the minimax mean-square error is within the …

A survey on distribution testing: Your data is big. But is it blue?

CL Canonne - Theory of Computing, 2020 - theoryofcomputing.org
The field of property testing originated in work on program checking, and has evolved into
an established and very active research area. In this work, we survey the developments of …

Estimation of wasserstein distances in the spiked transport model

J Niles-Weed, P Rigollet - Bernoulli, 2022 - projecteuclid.org
Estimation of Wasserstein distances in the Spiked Transport Model Page 1 Bernoulli 28(4),
2022, 2663–2688 https://doi.org/10.3150/21-BEJ1433 Estimation of Wasserstein distances …

An automatic inequality prover and instance optimal identity testing

G Valiant, P Valiant - SIAM Journal on Computing, 2017 - SIAM
We consider the problem of verifying the identity of a distribution: Given the description of a
distribution over a discrete finite or countably infinite support, p=(p_1,p_2,...), how many …

Optimal algorithms for testing closeness of discrete distributions

SO Chan, I Diakonikolas, P Valiant, G Valiant - … of the twenty-fifth annual ACM …, 2014 - SIAM
We study the question of closeness testing for two discrete distributions. More precisely,
given samples from two distributions p and q over an n-element set, we wish to distinguish …

Estimating the unseen: improved estimators for entropy and other properties

G Valiant, P Valiant - Journal of the ACM (JACM), 2017 - dl.acm.org
We show that a class of statistical properties of distributions, which includes such practically
relevant properties as entropy, the number of distinct elements, and distance metrics …

[HTML][HTML] On the quantum versus classical learnability of discrete distributions

R Sweke, JP Seifert, D Hangleiter, J Eisert - Quantum, 2021 - quantum-journal.org
Here we study the comparative power of classical and quantum learners for generative
modelling within the Probably Approximately Correct (PAC) framework. More specifically we …

Chebyshev polynomials, moment matching, and optimal estimation of the unseen

Y Wu, P Yang - The Annals of Statistics, 2019 - JSTOR
We consider the problem of estimating the support size of a discrete distribution whose
minimum nonzero mass is at least 1 k. Under the independent sampling model, we show …

Testing symmetric properties of distributions

P Valiant - Proceedings of the fortieth annual ACM symposium on …, 2008 - dl.acm.org
We introduce the notion of a Canonical Tester for a class of properties on distributions, that
is, a tester strong and general enough that" a distribution property in the class is testable if …