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 worstcase 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 GoodTuring 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

2022 Poster: What Can Transformers Learn InContext? A Case Study of Simple Function Classes »
Shivam Garg · Dimitris Tsipras · Percy Liang · Gregory Valiant 
2022 Poster: FiniteSample Maximum Likelihood Estimation of Location »
Shivam Gupta · Jasper Lee · Eric Price · Paul Valiant 
2020 Poster: WorstCase Analysis for Randomly Collected Data »
Justin Chen · Gregory Valiant · Paul Valiant 
2020 Oral: WorstCase 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