Testing Shape Restrictions of Discrete Distributions

Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, Ronitt Rubinfeld

TL;DR

This paper introduces a unified algorithmic framework for testing whether an unknown discrete probability distribution belongs to a "shape-constrained" class (like monotone or log-concave). The authors provide a general algorithm with near-optimal sample complexity and demonstrate its efficiency across various distribution families, also establishing tight lower bounds for these problems.

What Problem Does This Paper Address?

In many real-world scenarios, we assume that data follows a probability distribution with a specific structure or "shape." For example, we might assume a distribution is "monotone" (probabilities decrease or stay the same) or "log-concave" (the logarithm of the probabilities forms a concave function). The challenge is to efficiently verify if an unknown distribution, accessed only through samples, actually possesses such a structural property. This is known as "property testing" for distributions. While previous work tackled specific shape constraints, this paper aims to provide a general, unified approach that works for a broad range of these properties, offering both efficient algorithms and theoretical guarantees.

Methods

The core of the paper is a general algorithm called TESTSPLITTABLE. Its strategy is inspired by how monotonicity testing was previously done: it recursively partitions the domain of the distribution. The algorithm attempts to find a "succinct decomposition" of the distribution into a small number of intervals where the distribution is approximately "flat" (close to uniform within each interval).

The algorithm proceeds in three stages:

  1. Decomposition: It recursively splits the domain, trying to identify intervals where the distribution is either very flat or has very little total probability mass. If it needs too many splits, it rejects, indicating the distribution likely doesn't have the desired shape.
  2. Approximation: If a good decomposition is found, the algorithm learns an approximation of the distribution's "flattened" version. This is efficient because the decomposition limits the complexity of the approximation.
  3. Projection: Finally, it checks if this learned approximation is indeed close to the target class of distributions.

A key innovation is the focus on a structural property called "(Succinctness)," which formalizes the idea that distributions in the class can be well-approximated by piecewise constant functions on a small number of intervals. The authors also develop a generic method for proving lower bounds, which helps establish the near-optimality of their algorithms.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithms that work with sample access to an arbitrary distribution, rather than specific datasets.

Key Insights and Ideas

  • Unified Framework: The most significant insight is the development of a single algorithmic framework that can test a wide variety of shape-constrained distribution properties. This moves beyond case-by-case analysis.
  • "Succinctness" as a General Criterion: The paper identifies a crucial structural property ("Succinctness") that allows a broad class of distributions to be tested efficiently. This property essentially means the distribution can be well-approximated by simple shapes (like piecewise constant functions) over a small number of domain segments.
  • Decomposition Strategy: The recursive splitting approach, inspired by prior work, proves to be a powerful general technique for identifying and exploiting the structure of these distributions.
  • Near-Optimal Guarantees: The authors not only provide efficient algorithms but also prove matching lower bounds, showing that their sample complexity is essentially the best possible (up to logarithmic factors).
  • Tolerant Testing Extension: The techniques are extended to "tolerant testing," where the goal is to distinguish between distributions that are very close to the property and those that are far away, also yielding tight bounds.

Key Results

  • General Tester: An algorithm TESTSPLITTABLE is presented that can test membership in any "(γ, L)-splittable" class of distributions.
  • Sample Complexity: For many common shape-constrained classes (monotone, unimodal, log-concave, etc.), the algorithm achieves sample complexity of approximately $O(\sqrt{n}/\epsilon^{7/2})$ or $O(\sqrt{tn}/\epsilon^{7/2})$, which is near-optimal.
  • First Non-Trivial Testers: For several classes (e.g., t-modal, log-concave, piecewise-polynomial), this paper provides the first known non-trivial testers.
  • Tight Lower Bounds: Generic methods are used to prove lower bounds, showing that testing these properties requires at least $\Omega(\sqrt{n}/\epsilon^2)$ or $\Omega(n^{1/4}/\epsilon^2)$ samples for many classes, matching the upper bounds.
  • Tolerant Testing Bounds: Nearly tight upper and lower bounds are derived for tolerant testing of these shape-constrained distributions.

Limitations and Future Work

  • Scope of "Succinctness": While the framework is general, its applicability depends on whether a given distribution class satisfies the "(Succinctness)" criterion. The paper demonstrates this for many common classes but acknowledges that not all structured distributions might fit this mold.
  • Full Version Details: The extended abstract focuses on the main theorem and its proof. Many details regarding the applications to specific classes, proofs of structural theorems, and the full treatment of lower bounds and tolerant testing are deferred to a full version of the paper.
  • Computational Efficiency: While the algorithms are described as computationally efficient, the exact complexity depends on the specific class and the PROJECTIONDISTC subroutine, which is assumed to be efficient for the classes considered.
  • Future Work: The authors suggest that their framework could be applied to other distribution classes. The extension to tolerant testing also opens avenues for further research in that direction.

Summary updated

Abstract

We study the question of testing structured properties (classes) of discrete distributions. Specifically, given sample access to an arbitrary distribution D over [n] and a property P, the goal is to distinguish between D in P and l_{1}(D,P)>epsilon. We develop a general algorithm for this question, which applies to a large range of "shape-constrained" properties, including monotone, log-concave, t-modal, piecewise-polynomial, and Poisson Binomial distributions. Moreover, for all cases considered, our algorithm has near-optimal sample complexity with regard to the domain size and is computationally efficient. For most of these classes, we provide the first non-trivial tester in the literature. In addition, we also describe a generic method to prove lower bounds for this problem, and use it to show our upper bounds are nearly tight. Finally, we extend some of our techniques to tolerant testing, deriving nearly-tight upper and lower bounds for the corresponding questions.
BibTeX
@article{canonne2018testing,
  author = {Clément L. Canonne and Ilias Diakonikolas and Themis Gouleakis and Ronitt Rubinfeld},
  title = {{Testing Shape Restrictions of Discrete Distributions}},
  journal = {Theory Comput. Syst.},
  year = {2018},
  doi = {10.1007/s00224-017-9785-6},
}
Figure