Optimal Testing for Properties of Distributions

Abstract

Given samples from an unknown distribution $p$, is it possible to distinguish whether $p$ belongs to some class of distributions $\mathcal{C}$ versus $p$ being far from every distribution in $\mathcal{C}$? This fundamental question has received tremendous attention in statistics, focusing primarily on asymptotic analysis, and more recently in information theory and theoretical computer science, where the emphasis has been on small sample size and computational complexity. Nevertheless, even for basic properties of distributions such as monotonicity, log-concavity, unimodality, independence, and monotone-hazard rate, the optimal sample complexity is unknown. We provide a general approach via which we obtain sample-optimal and computationally efficient testers for all these distribution families. At the core of our approach is an algorithm which solves the following problem: Given samples from an unknown distribution $p$, and a known distribution $q$, are $p$ and $q$ close in ${\chi }^2$-distance, or far in total variation distance? The optimality of our testers is established by providing matching lower bounds with respect to both $n$ and $\epsilon$. Finally, a necessary building block for our testers and an important byproduct of our work are the first known computationally efficient proper learners for discrete log-concave and monotone hazard rate distributions.

31 pages, extended abstract appeared as a spotlight in NIPS 2015

References in corpus (1)

• Learning mixtures of structured distributions over discrete domains

Cited by in corpus (32)

• Preference-based Online Learning with Dueling Bandits: A Survey
• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time
• Learning and Testing Causal Models with Interventions
• Learning Multivariate Log-concave Distributions
• Property Testing of Joint Distributions using Conditional Samples
• Priv'IT: Private and Sample Efficient Identity Testing
• Differentially Private Identity and Closeness Testing of Discrete Distributions
• Private Identity Testing for High-Dimensional Distributions
• Testing Conditional Independence of Discrete Distributions
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
• Pan-Private Uniformity Testing
• INSPECTRE: Privately Estimating the Unseen
• Connecting Robust Shuffle Privacy and Pan-Privacy
• Testing Markov Chains without Hitting
• Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
• Statistical Inference in the Differential Privacy Model
• The Broad Optimality of Profile Maximum Likelihood
• Differential Privacy in the Shuffle Model: A Survey of Separations
• Optimal Identity Testing with High Probability
• Testing Product Distributions: A Closer Look
• The Sample Complexity of Robust Covariance Testing
• On Distribution Testing in the Conditional Sampling Model
• Inference under Information Constraints III: Local Privacy Constraints
• As Easy as ABC: Adaptive Binning Coincidence Test for Uniformity Testing
• The Price of Tolerance in Distribution Testing
• Goodness-of-Fit Testing for Hölder-Continuous Densities: Sharp Local Minimax Rates
• Distribution-free inference for regression: discrete, continuous, and in between
• Testing Tail Weight of a Distribution Via Hazard Rate
• Communication Complexity of Distributed High Dimensional Correlation Testing
• Testing Determinantal Point Processes
• Testing Mixtures of Discrete Distributions
• Towards Testing Monotonicity of Distributions Over General Posets