PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Testing for Properties of Distributions

Jayadev Acharya, Constantinos Daskalakis, Gautam Kamath

arXiv:1507.05952v3cs.DScs.ITcs.LGmath.ST

TL;DR

The paper asks how to distinguish distributions belonging to a class from those far from it in the small-sample regime. It introduces a χ2-based testing approach and applies it to obtain sample-optimal, computationally efficient testers, matching lower bounds, and proper learners for selected classes. The main scope includes monotonicity, log-concavity, unimodality, independence, and monotone hazard rate.

  • Problem

    Determining optimal sample complexity for testing basic distribution properties in the small-sample regime remains an open problem despite extensive statistical study.

  • Method

    The paper uses a χ2 statistic to compare an unknown p with a learned approximation q, reducing class testing to χ2-closeness versus total-variation separation.

  • Results

    The resulting testers are sample-optimal and computationally efficient, with matching lower bounds; the work also gives the first known computationally efficient proper learners for discrete log-concave and monotone-hazard-rate distributions.

  • Takeaways & Limitations

    The framework yields optimal testers across several fundamental distribution families and extends efficient proper learning to two classes in the low-sample regime.

  • Takeaways & Limitations

    For some classes, the base approach cannot obtain a χ2-accurate approximation throughout the entire support and therefore requires modified testing procedures.

Abstract

from arXiv · show

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 $χ^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 $\varepsilon$. 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.

1 Introduction

The paper studies whether sampled distributions belong to specified classes or are far from them, targeting the small-sample regime where optimal complexities remain unknown. It develops a χ2-based testing framework and applies it to obtain sample-optimal, computationally efficient testers and proper learners for several distribution families.

  • Problem: The central task is distinguishing p ∈ C from dTV(p, C) > ε using samples from an unknown discrete distribution.This composite property-testing problem is studied in the small-sample regime.
  • Contributions: The paper provides sample-optimal and computationally efficient testers for fundamental shape restrictions and independence properties.The contribution covers monotonicity, log-concavity, monotone hazard rate, unimodality, and product distributions.
  • Independence testing: For product distributions, the tester achieves Θ(n^(d/2)/ε2) samples when d is constant and all domain side lengths equal n.The result is stated as optimal, includes the first result for d ≥ 3, and improves the d = 2 dependence on ε while removing logarithmic factors.
  • Shape-restricted testing: Testing log-concave, monotone-hazard-rate, and unimodal distributions requires optimal Θ(√n/ε2) samples.The log-concave and monotone-hazard-rate testers are described as the first for the low-sample regime, while the unimodality tester improves ε dependence and removes logarithmic factors relative to monotonicity-based testers.
  • Optimality and learning: Matching lower bounds establish optimality in n, ε, and, when applicable, d, while proper learners are obtained for discrete log-concave and monotone-hazard-rate distributions.The learners use poly(1/ε) samples independent of n and achieve ε total-variation error.
  • χ2-based framework: The core algorithm distinguishes χ2-closeness from total-variation separation after approximating p with a learned distribution q.The two cases are χ2 distance O(ε2) when p belongs to the class and total variation distance Ω(ε) when p is ε-far from it.

2 Preliminaries

The paper formalizes distribution-property testing through probability distances, effective supports, distribution classes, and randomized sample-access guarantees.

  • Total variation distance is defined as half the ℓ1 distance between distributions, including when restricted to a subset.
  • The paper also uses χ2-distance and Kolmogorov distance to compare distributions.
  • A tester must accept distributions in class C and reject distributions at total variation distance at least ε from C, each with probability at least 2/3.
  • The considered classes include monotone, unimodal, log-concave, and monotone-hazard-rate distributions.
  • An η-effective support is any set containing at least 1−η probability mass, and flattening replaces probabilities on each part by uniform values.
  • Poissonization draws a Poisson number of samples so occurrence counts for different support elements become independent.

3 Overview

The testing framework learns a near-proper hypothesis, checks its distance to the target class, and then applies χ2-testing; extensions handle several distribution properties.

  • The algorithm decomposes testing into near-proper learning, computation of distance to the class, and χ2-testing.
  • Near-proper learning outputs q close to the class in total variation and close to p in χ2-distance on an effective support.
  • If q is far from the class, the algorithm can reject without drawing further samples from p.
  • The χ2-testing stage distinguishes class membership from total variation distance at least ε using the learned guarantees.
  • The framework directly tests monotonicity, log-concavity, and monotone hazard rate, while Kolmogorov’s max inequality enables unimodality testing.

4 A Robust χ2-ℓ1 Identity Test

The paper develops a robust χ2-based identity tester that separates χ2-closeness from ℓ1-farness and supports class testing through explicit hypotheses and effective-support modifications.

  • The identity problem distinguishes χ2-distance at most ε2/2 from ℓ1-distance at least ε between unknown p and known q.
  • The tester accepts when p belongs to C and rejects when dTV(p, C) ≥ε, each with probability at least 2/3.
  • For log-concave and monotone-hazard-rate classes, the tester restricts attention to an effective support S and ignores the remainder.
  • Kolmogorov’s maximal inequality handles hidden low-measure intervals while retaining O(√n/ε2) sample complexity and also enables unimodality testing.
  • The statistic Z is analyzed through separated means and variances, after which Chebyshev’s inequality yields the testing guarantee.

5 Testing Monotonicity

Monotonicity testing over multidimensional grids combines an oblivious decomposition with learning and distance computation to obtain efficient testers.

  • The resulting tester applies to every d ≥1 and achieves the paper’s optimal monotonicity-testing guarantees.
  • For monotone distributions over [n]d, an oblivious decomposition partitions the domain into O((d log(n)/ε2)d) rectangles whose flattening is χ2-close.
  • The decomposition effectively reduces the support size to logarithmic in n, enabling a Laplace estimator to learn a χ2-close hypothesis.
  • A linear program checks whether the learned hypothesis is close in total variation to the monotone class before χ2-testing.
  • The linear program operates on the decomposition, giving complexity polynomial in (d log(n)/ε)d rather than the naive nd.
  • The monotonicity analysis motivates more sophisticated learning and structural methods for log-concavity, monotone hazard rate, and unimodality.

6 Testing Unimodality

The paper develops an efficient unimodality tester by replacing a logarithmic union-bound overhead with a non-oblivious decomposition and Kolmogorov’s max-inequality. It obtains a tester with sample complexity proportional to the square root of the domain size, divided by ε^2, under ε > n^-1/4.

  • Mode-dependent decomposition: The unknown mode prevents using Birgé’s sample-oblivious decomposition directly for unimodal distributions.If the mode were known, the domain could be split into two intervals and monotonicity testing applied to each.
  • Mode-dependent decomposition: A union bound over all n possible modes introduces a logarithmic barrier and is unsatisfactory relative to the lower bound.The paper identifies the resulting complexity as √n/ε^2.
  • Improved tester: The improved approach uses a non-oblivious domain decomposition together with Kolmogorov’s max-inequality to remove that barrier.This replaces the union-bound strategy while retaining an efficient testing framework.
  • Main result: For ε > n^-1/4, the paper gives an algorithm for testing unimodality over [n].This is stated as the main unimodality result.

7 Testing Independence of Random Variables

For independence testing, the paper relates χ2-distance between product distributions to the distances of their coordinates and combines this structure with its robust χ2-ℓ1 testing framework. The resulting algorithms achieve optimal sample complexity, including Θ(n/ε^2) for two variables over [n].

  • Product-distribution structure: The paper models independent distributions over X = [n_1] × ... × [n_d] as product distributions in Π_d.It first bounds χ2-distance between product distributions using the individual coordinate distributions.
  • Learning step: A χ2-learning procedure outputs a product distribution q from samples drawn from p in Π_d.The supplied passages state the procedure and its product-class output, while the surrounding framework uses these guarantees for testing.
  • Testing framework: The learned product approximation fits the robust χ2-ℓ1 testing framework, yielding an independence tester for arbitrary d.The result is obtained by applying Theorem 2 to the learning guarantees.
  • Sample complexity: For general dimensions, the paper states a product-domain sample-complexity bound in terms of the coordinate sizes n_1,...,n_d.The displayed expression is split across the supplied passages, which state the product over coordinates and the resulting Θ bound.

8 Testing Log-Concavity

The paper tests discrete log-concavity through a specialized χ2-learning procedure and a general robust testing theorem. It also derives computationally efficient proper learning algorithms for log-concave distributions, including a refined near-optimal sample bound.

  • Main tester: The log-concavity section’s main result is an algorithm for testing distributions over [n].The tester is paired with polynomial time complexity in n and 1/ε.
  • Optimality: For ε > n^-1/5, the paper states an optimal tester for log-concavity over [n].This result is presented as Corollary 4 after the preceding tester theorem.
  • Main tester: The log-concavity tester has sample complexity O(1/ε^5) and time complexity poly(n, 1/ε).The stated guarantee applies to the testing procedure described in the section.
  • Proper learning: Proper learning of discrete log-concave distributions is achieved with sample complexity ˜O(1/ε^4) and polynomial time.The learner outputs q in LCD_n with dTV(p,q) ≤ ε.
  • Method: The tester is obtained by combining the guarantees of Lemma 8 with the general testing theorem.Lemma 8 supplies a learned log-concave approximation and an effective support on which χ2-distance is controlled.

9 Testing for Monotone Hazard Rate

The paper applies its χ2-learning and robust testing framework to monotone hazard rate distributions. It obtains computationally efficient testers and proper learners, with sample complexity depending logarithmically on n and polynomially on 1/ε.

  • Main tester: The monotone hazard rate section develops a main tester for distributions over [n].The tester is derived by combining the learning guarantees of Lemma 9 with an appropriate variant of Theorem 2.
  • Technical condition: The testing procedure uses a modification of Theorem 7 when χ2 guarantees hold only on a known effective support.This support-specific requirement is stated as an explicit technical condition.
  • Optimality: For ε above the stated n-dependent threshold, the paper identifies an optimal monotone hazard rate tester.This conclusion is presented after the main tester theorem.
  • Learning step: The method first applies a χ2-learner whose output is a monotone hazard rate distribution together with an effective support.On that support, the learner controls χ2-distance to the input distribution.
  • Guarantee: If p is ε-far from MHR_n in total variation, the algorithm either outputs a monotone hazard rate approximation and a set S or rejects.The stated rejection guarantee is paired with sample complexity O(log(n/ε)/ε^4) and polynomial time.
  • Proper learning: Proper learning for MHR_n uses O(log(n/ε)/ε^4) samples and time poly(n, 1/ε).The learner outputs q in MHR_n satisfying dTV(p,q) ≤ ε.

10 Lower Bounds

The paper derives matching lower bounds for testing monotonicity, independence, unimodality, log-concavity, and monotone hazard rate using Paninski-style hard instances. These bounds establish the optimal dependence on n and ε for the considered classes.

  • Hard-instance construction: Paninski-style perturbations are constructed so that distributions far from the target class remain difficult to distinguish from the uniform distribution.The construction uses paired probability perturbations and a class Q whose members are separated from the uniform distribution in total variation.
  • One-dimensional lower bounds: If the uniform distribution belongs to C, testing C requires at least Ω(√n/ε^2) samples.The reduction applies whenever C contains the uniform distribution, yielding the one-dimensional lower bounds for several classes.
  • Monotonicity: Any algorithm for testing monotonicity over [n]^d requires Ω(n^(d/2)/ε^2) samples.The higher-dimensional construction places paired perturbations along the first coordinate and shows that every monotone distribution remains far from the hard instances.
  • Proof mechanism: The variance analysis of the χ^2 statistic uses Poissonized counts with independent Xi distributed as Poisson(mp_i).The proof bounds the statistic’s mean and variance through the moments of the Poisson distribution.
  • Proof mechanism: The lower-bound analysis extends the hard-instance argument by partitioning the support and comparing total variation contributions on a subset A and its complement.The proof uses dTV(p,q)=dTV(p_A,q_A)+dTV(p_Ā,q_Ā) and handles separate cases according to the mass outside A.

C.1 A Structural Result for Monotone Distributions on the Hypergrid

The structural result partitions the hypergrid into rectangles on which a monotone distribution can be flattened while preserving a controlled χ^2 approximation. This supports efficient learning and testing procedures based on interval-mass estimates and χ^2 statistics.

  • Structural decomposition: A monotone distribution on [n]^d can be approximated by flattening it over a partition into b^d rectangles.The construction extends the one-dimensional piecewise-constant decomposition to the hypergrid and controls the resulting χ^2 distance.
  • Structural decomposition: Choosing γ=2 log(n)/b bounds the approximation expression by (1+2γ)^d−1.This is the key quantitative consequence used to establish the structural lemma.
  • Partition construction: The interval partition can be constructed with O(b log b) samples.The resulting intervals satisfy the required mass properties for the subsequent estimation procedure.
  • Mass estimation: With m′=O(b log b/ε^2) samples, the estimator produces a distribution constant on each interval and multiplicatively accurate on intervals with mass above 1/(2b).The guarantee holds with probability at least 9/10 for every interval whose true mass exceeds the threshold.
  • Unimodality extension: For unimodal testing, the procedure removes exceptional intervals and discards the largest interval-level χ^2 statistic to handle a possible outlier.The remaining statistic retains the needed behavior in both the in-class and far-from-class cases.
  • Product estimation: For product distributions, independent add-1 estimates on each coordinate are combined into a product estimate.The coordinate-wise independence enables the resulting approximation analysis.

F Details on Testing Log-Concavity

The log-concavity tester first builds a piecewise-constant empirical approximation and then searches for a nearby log-concave distribution through a linear program. The construction provides χ^2 control on an effective support containing most of the probability mass.

  • Algorithm outline: The algorithm first flattens an empirical distribution into O(1/ε^(3/2)) pieces before constructing a proper log-concave candidate.The proper candidate is obtained by solving a feasibility linear program over logarithmic probability variables.
  • Empirical partition: The domain outside a central high-probability region is partitioned into intervals of mass Θ(ε^(3/2)), with at most constantly many exceptions.The empirical partition is designed so that ordinary intervals have mass between explicit lower and upper bounds.
  • Approximation analysis: On intervals to the left of the mode, flattening gives a multiplicative 1+O(1/j) approximation, followed by analogous treatment on the right.The analysis excludes a small number of boundary and exceptional intervals before establishing the effective-support guarantee.
  • Approximation analysis: The resulting approximation is multiplicative on most intervals, while the excluded intervals account for only O(ε) probability mass.The effective support is formed by removing boundary, exceptional, and mode-containing intervals.
  • Proper learning step: The linear program searches for logarithmic probabilities satisfying log-concavity constraints and approximation constraints relative to the empirical flattening.If feasible, the output is a distribution in the log-concave class; when the input is log-concave, the analysis guarantees χ^2 closeness on a set of mass at least 1−O(ε).

G Details on MHR testing

The MHR tester combines an interval decomposition with a linear program expressed through the survival function. It uses multiplicative approximation on most of the mass and establishes lower bounds through perturbations that remain far from MHR distributions.

  • Algorithm outline: The MHR procedure first obtains a distribution q that is O(ε^2)-close in χ^2 distance on intervals carrying 1−O(ε) mass.The approximation is multiplicative within the retained intervals and parallels the decomposition used for unimodality.
  • Linear-program test: A feasible linear-program solution implies the existence of an MHR distribution within O(ε) total variation distance.When p is MHR, the construction guarantees feasibility; otherwise feasibility provides a nearby MHR witness for the intermediate candidate.
  • Interval decomposition: Heavy elements are treated as singletons, while the remaining domain is greedily partitioned into intervals of mass approximately Θ(1/b).The MHR structural lemma bounds the number of contiguous heavy-element regions.
  • Interval decomposition: Discarding intervals whose per-element probabilities differ substantially from neighboring intervals removes at most log(n/ε)/(bε) probability mass.Choosing b sufficiently large makes the discarded mass O(ε).
  • Linear-program test: The second stage uses a linear program over fi=log(1−Fi) to enforce that the candidate is a distribution and satisfies the MHR condition.The constraints also impose multiplicative closeness between the candidate and q, separately handling heavy and light elements.
  • Lower bound: MHR testing requires Ω(√n/ε^2) samples in the lower-bound construction.The hard distributions are shown to be ε-far from every MHR distribution for a suitable perturbation constant.
Loading 1507.05952v3…