  We introduce a new method for estimating the support size of an unknown
distribution which provably matches the performance bounds of the
state-of-the-art techniques in the area and outperforms them in practice. In
particular, we present both theoretical and computer simulation results that
illustrate the utility and performance improvements of our method. The
theoretical analysis relies on introducing a new weighted Chebyshev polynomial
approximation method, jointly optimizing the bias and variance components of
the risk, and combining the weighted minmax polynomial approximation method
with discretized semi-infinite programming solvers. Such a setting allows for
casting the estimation problem as a linear program (LP) with a small number of
variables and constraints that may be solved as efficiently as the original
Chebyshev approximation problem. Our technique is tested on synthetic data and
used to address an important problem in computational biology - estimating the
number of bacterial genera in the human gut. On synthetic datasets, for
practically relevant sample sizes, we observe significant improvements in the
value of the worst-case risk compared to existing methods. For the
bioinformatics application, using metagenomic data from the NIH Human Gut and
the American Gut Microbiome Projects, we generate a list of frequencies of
bacterial taxa that allows us to estimate the number of bacterial genera to
approximately 2300.
