Talks
Spring 2015

# Chebyshev Polynomials, Moment Matching and Optimal Estimation of the Unseen

Tuesday, Mar. 17, 2015 9:50 am10:15 am PDT

We consider the estimation of the support size of a discrete distribution using independent samples whose minimum non-zero mass is at least $\dpi{300}\inline \frac{1}{k}$. We show that, to achieve an additive error of $\dpi{300}\inline \epsilon k$ with probability at least 0.9, the sample complexity is within universal constant factors of $\dpi{300}\inline \frac{k}{\log k}\log^2\frac{1}{\epsilon}$, which improves the state-of-the-art result $\dpi{300}\inline \frac{k}{\log k} \frac{1}{\epsilon^2}$ due to Valiant-Valiant. The apparatus of best polynomial approximation and its duality to the moment matching problem play a key role in both the impossibility result and the construction of linear-time estimators with provable optimality.