Optimal algorithms for testing closeness of discrete distributions

DOI10.1137/1.9781611973402.88MaRDI QIDQ5384050zbMATH OpenOpenAlexFDO

Authors Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.3946, http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.88

Mathematics Subject Classification ID

Characterization and structure theory of statistical distributions (62E10) Randomized algorithms (68W20)

Abstract: We study the question of closeness testing for two discrete distributions. More precisely, given samples from two distributions $p$ and $q$ over an $n$-element set, we wish to distinguish whether $p=q$ versus $p$ is at least $eps$-far from $q$, in either $el{l}_1$ or $el{l}_2$ distance. Batu et al. gave the first sub-linear time algorithms for these problems, which matched the lower bounds of Valiant up to a logarithmic factor in $n$, and a polynomial factor of $eps.$ In this work, we present simple (and new) testers for both the $el{l}_1$ and $el{l}_2$ settings, with sample complexity that is information-theoretically optimal, to constant factors, both in the dependence on $n$, and the dependence on $eps$; for the $el{l}_1$ testing problem we establish that the sample complexity is $Theta(max{n}^{2/3}/ep{s}^{4/3},n^{1/2}/ep{s}^2).$

Recommendations

• Testing closeness of discrete distributions
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Which Distribution Distances are Sublinearly Testable?
• Collision-based Testers are Optimal for Uniformity and Closeness
• Testing k-modal distributions: optimal algorithms via reductions

Cited in

(43)

• Two-sample hypothesis testing for inhomogeneous random graphs
• Hypothesis testing for high-dimensional multinomials: a selective review
• Testing shape restrictions of discrete distributions
• Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials
• Minimax optimality of permutation tests
• Local minimax rates for closeness testing of discrete distributions
• Higher criticism to compare two large frequency tables, with sensitivity to possible rare and weak differences
• Analysis of COVID-19 evolution based on testing closeness of sequential data
• Asymptotic distribution and detection thresholds for two-sample tests based on geometric graphs
• An automatic inequality prover and instance optimal identity testing
• _p testing and learning of discrete distributions
• Which Distribution Distances are Sublinearly Testable?
• A chasm between identity and equivalence testing with conditional queries
• Recovering structured probability matrices
• Learning discrete distributions from untrusted batches
• Proofs of proximity for distribution testing
• Communication complexity of statistical distance
• Sample-optimal identity testing with high probability
• Instance Optimal Distribution Testing and Learning
• Two Party Distribution Testing: Communication and Security
• Quantum Chebyshev's Inequality and Applications
• The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
• On the Optimal Analysis of the Collision Probability Tester (an Exposition)
• Near-Optimal Closeness Testing of Discrete Histogram Distributions
• Optimal stopping rules for sequential hypothesis testing
• Collision-based Testers are Optimal for Uniformity and Closeness
• Testing probability distributions using conditional samples
• Testing closeness of discrete distributions
• Topics and Techniques in Distribution Testing: A Biased but Representative Sample
• Anonymous whistleblowing over authenticated channels
• Sublinear time algorithms for earth mover's distance
• Simpler distribution testing with little memory
• Locally sharp goodness-of-fit testing in sup norm for high-dimensional counts
• Local goodness-of-fit testing for Hölder-continuous densities: minimax rates
• Distribution testing with a confused collector
• Private distribution testing with heterogeneous constraints: your epsilon might not be mine
• Complexity of high-dimensional identity testing with coordinate conditional sampling
• Learning and testing irreducible Markov chains via the k-cover time
• Testing product distributions: a closer look
• Conditional independence testing for discrete distributions: beyond ^2- and G-tests
• Sample efficient identity testing and independence testing of quantum states
• Locally differentially private two-sample testing
• Testing cluster structure of graphs

This page was built for publication: Optimal algorithms for testing closeness of discrete distributions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384050)