Testing monotone high-dimensional distributions

ABSTRACT

A monotone distribution P over a (partially) ordered domain has P(y) ≥ P(x) if y ≥ x in the order. We study several natural problems of testing properties of monotone distributions over the n-dimensional Boolean cube, given access to random draws from the distribution being tested. We give a poly(n)-time algorithm for testing whether a monotone distribution is equivalent to or ε-far (in the L1 norm) from the uniform distribution. A key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the Boolean cube. We also introduce a method for proving lower bounds on testing monotone distributions over the n-dimensional Boolean cube, based on a new decomposition technique for monotone distributions. We use this method to show that our uniformity testing algorithm is optimal up to polylog(n) factors, and also to give exponential lower bounds on the complexity of several other problems (testing whether a monotone distribution is identical to or ε-far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution).

REFERENCES

• 1: D. Aldous. On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probability in Engineering and Information Sciences, 1:33--46, 1987.
• 2: T. Batu , L. Fortnow , E. Fischer , R. Kumar , R. Rubinfeld , P. White, Testing Random Variables for Independence and Identity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.442, October 14-17, 2001
• 3: Tuǧkan Batu , Sanjoy Dasgupta , Ravi Kumar , Ronitt Rubinfeld, The complexity of approximating entropy, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510005]
• 4: T. Batu , L. Fortnow , R. Rubinfeld , W. D. Smith , P. White, Testing that distributions are close, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.259, November 12-14, 2000
• 5: Tugkan Batu , Ravi Kumar , Ronitt Rubinfeld, Sublinear algorithms for testing monotone and unimodal distributions, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007414]
• 6: Merrick L. Furst , Jeffrey C. Jackson , Sean W. Smith, Improved learning of AC0 functions, Proceedings of the fourth annual workshop on Computational learning theory, p.317-325, August 05-07, 1991, Santa Cruz, California, United States
• 7: O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. Electronic Colloqium on Computational Complexity, 7(20), 2000.
• 8: W. C. Huffman and V. Pless. Fundamentals of Error Correcting Codes. Cambridge University Press, 2003.
• 9: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 10: Nathan Linial , Yishay Mansour , Noam Nisan, Constant depth circuits, Fourier transform, and learnability, Journal of the ACM (JACM), v.40 n.3, p.607-620, July 1993 [doi>10.1145/174130.174138]
• 11: Rocco A. Servedio, On Learning Monotone DNF under Product Distributions, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.558-573, July 16-19, 2001
• 12: A. Yao. Probabilistic computations: Towards a unified measure of complexity. In Symposium on Foundations of Computer Science, pages 222--227, 1977.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

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

General Terms:
Algorithms, Theory

Keywords:
distribution testing, monotone distributions, property testing, sublinear algorithms