Timezone: »
Recently, [Valiant and Valiant] showed that a class of distributional properties, which includes such practically relevant properties as entropy, the number of distinct elements, and distance metrics between pairs of distributions, can be estimated given a SUBLINEAR sized sample. Specifically, given a sample consisting of independent draws from any distribution over at most n distinct elements, these properties can be estimated accurately using a sample of size O(n / log n). We propose a novel modification of this approach and show: 1) theoretically, our estimator is optimal (to constant factors, over worst-case instances), and 2) in practice, it performs exceptionally well for a variety of estimation tasks, on a variety of natural distributions, for a wide range of parameters. Perhaps unsurprisingly, the key step in this approach is to first use the sample to characterize the "unseen" portion of the distribution. This goes beyond such tools as the Good-Turing frequency estimation scheme, which estimates the total probability mass of the unobserved portion of the distribution: we seek to estimate the "shape"of the unobserved portion of the distribution. This approach is robust, general, and theoretically principled; we expect that it may be fruitfully used as a component within larger machine learning and data analysis systems.
Author Information
Paul Valiant (IAS; Purdue University)
Gregory Valiant (Stanford University)
More from the Same Authors
-
2020 Poster: Worst-Case Analysis for Randomly Collected Data »
Justin Chen · Gregory Valiant · Paul Valiant -
2020 Oral: Worst-Case Analysis for Randomly Collected Data »
Justin Chen · Gregory Valiant · Paul Valiant -
2019 Poster: Making AI Forget You: Data Deletion in Machine Learning »
Antonio Ginart · Melody Guan · Gregory Valiant · James Zou -
2019 Spotlight: Making AI Forget You: Data Deletion in Machine Learning »
Antonio Ginart · Melody Guan · Gregory Valiant · James Zou -
2018 Poster: A Spectral View of Adversarially Robust Features »
Shivam Garg · Vatsal Sharan · Brian Zhang · Gregory Valiant -
2018 Spotlight: A Spectral View of Adversarially Robust Features »
Shivam Garg · Vatsal Sharan · Brian Zhang · Gregory Valiant