Testing that distributions are close

By Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White. 2000

341 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “Speciﬁcally, the sample complexity of our private closeness tester is Related Work During the past two decades, distribution property testing [3] – whose roots lie in statistical hypothesis testing [23, 22] – has received considerable attention by the computer science community, see [25, 7] for two…”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “In the past two decades there has been a lot of work from the computer science, information theory, and statistics community on various distribution testing problems in the non-asymptotic (small-sample) regime, where the domain size k could be potentially larger thanm (See [13, 12, 37, 10, 49, 4, 3,”
Testing Properties of Collections of Distributions (2013, background): “To gain some intuition before delving into the detailed proof, consider first the special case that m = 2 (which was studied by Valiant [48], and indeed the construction is the same as the one he analyzes (and was initially proposed in [12]).”
Estimating the Unseen (2013, background): “For estimating entropy, or any other property whose value is invariant to relabeling the distribution support, the ﬁngerprint of a sample contains all the relevant information (see [21], for a formal proof of this fact).”
The specious art of single-cell genomics (2021, methodology): “We also present results with the L1 norm (shown in Supplementary Materials), as L1 is more suitable for measuring distance in high dimensions, particularly in comparison to other L norms [29, 30], and is commonly applied to transcriptomic data [31–33], with comparable performance to the probabilisti”
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs (2011, background): “For such properties, the fingerprint of a sample contains all the useful information about the sample: for any estimator that uses the actual samples, there is an estimator of equal performance that takes as input only the fingerprint of the samples (see [6, 9], for an easy proof).”
On Testing Expansion in Bounded-Degree Graphs (2000, methodology): “In addition, the current work has inspired work on testing distributions, as initiated in [4].”
Sublinear algorithms for testing monotone and unimodal distributions (2004, methodology): “The following fact upper bounds the collision probability when the maximum and minimum probability values are not too far away from each other [ 3 , 2].”
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures (2016, background): “Starting with [5], this broad question has been extensively investigated in TCS with a focus on discrete probability distributions.”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, methodology): “The two distributions have 1 distance close to ε and the insight of Batu et al. (2000) is that in the two-sample setting is quite difficult to distinguish between variations in observed frequencies due to the perturbation of the entries and due to the random mixture of heavy and light entries.”
Differentially private anonymized histograms (2019, methodology): “Anonymized histograms are also referred to as histogram of histograms [1], histogram order statistics [2], profiles [3], unattributed histograms [4], fingerprints [5], and frequency lists [6].”
A Framework for Probability Density Estimation (2007, background): “Furthermore, recent results show that L1 density approximation of a discrete distribution requires sample sizes supra-polynomial in the cardinality of the support [2].”
Demystifying fixed k-nearest neighbor information estimators (2016, methodology): “As a byproduct of our investigations, we obtain nearly tight rates of convergence of the `2 error of the well known fixed k nearest neighbor estimator of differential entropy by Kozachenko and Leonenko.”