Testing symmetric properties of distributions

ABSTRACT

We introduce the notion of a Canonical Tester for a class of properties on distributions, that is, a tester strong and general enough that "a distribution property in the class is testable if and only if the Canonical Tester tests it". We construct a Canonical Tester for the class of symmetric properties of one or two distributions, satisfying a certain weak continuity condition. Analyzing the performance of the Canonical Tester on specific properties resolves several open problems, establishing lower bounds that match known upper bounds: we show that distinguishing between entropy <α or >β on distributions over [n] requires n^{α/β- o(1)} samples, and distinguishing whether a pair of distributions has statistical distance <α or >β requires n^1-o(1) samples. Our techniques also resolve a conjecture about a property that our Canonical Tester does not apply to: distinguishing identical distributions from those with statistical distance >β requires Ω(n^2/3) samples.

REFERENCES

• 1: . Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, and N. Xie. Testing k--wise and Almost k--wise Independence. STOC 2007.
• 2: . Alon, E. Fischer, I. Newman, and A. Shapira. A combinatorial characterization of the testable graph properties: it’s all about regularity. STOC 2006.
• 3: . Batu. Testing Properties of Distributions. Ph.D. thesis, Cornell University, 2001.
• 4: . Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld. The complexity of approximating the entropy. STOC, 2002.
• 5: . Batu, E. Fischer, L. Fortnow, R. Kumar, R. Rubinfeld, and P. White. Testing random variables for independence and identity. FOCS, 2001.
• 6: . Batu, L. Fortnow, R. Rubinfeld, W.D. Smith, and P. White. "Testing that distributions are close". FOCS, 2000.
• 7: . Batu, R. Kumar, and R. Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. STOC, 2004.
• 8: . Blum and S. Kannan. Designing Programs that Check Their Work. STOC 1989.
• 9: . Blum, M. Luby, and R. Rubinfeld. Self--testing/correcting with applications to numerical problems. Journal of Computer and System Sciences 47(3):549---595, 1993.
• 10: . Chakrabarti, G. Cormode, and A. McGregor. A Near--Optimal Algorithm for Computing the Entropy of a Stream. SODA 2007.
• 11: . Charikar, S. Chaudhuri, R. Motwani, and V.R. Narasayya. Towards Estimation Error Guarantees for Distinct Values. PODS, 2000.
• 12: . Goldreich, S. Goldwasser, and D. Ron. Property Testing and Its Connection to Learning and Approximation. FOCS 1996.
• 13: . Goldreich and L. Trevisan. Three theorems regarding testing graph properties. Random Struct. Algorithms, 23(1):23--57, 2003.
• 14: . Guha, A. McGregor, and S. Venkatasubramanian. Streaming and Sublinear Approximation of Entropy and Information Distances. SODA 2006.
• 15: . Klinger. The Vandermonde Matrix. The American Mathematical Monthly, 74(5):571--574, 1967.
• 16: . Indyk and A. McGregor. Declaring Independence via the Sketching of Sketches. SODA 2008.
• 17: . Indyk and D. Woodruff. Tight Lower Bounds for the Distinct Elements Problem. FOCS, 2003.
• 18: . Raskhodnikova, D. Ron, A. Shpilka, and A. Smith. Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. FOCS 2007.
• 19: . Roos. On the Rate of Multivariate Poisson Convergence. Journal of Multivariate Analysis 69:120--134, 1999.
• 20: . Rubinfeld and M. Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing 25(2):252--271, 1996.
• 21: . Valiant. Testing Symmetric Properties of Distributions. ECCC report TR07--135, 2007.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
continuity, distribution testing, multivariate statistics, property testing, vandermonde matrices