Sampling algorithms: lower bounds and applications

ABSTRACT

We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form \genfunc, where \domain and \range are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x_i that any sampling algorithm needs to query to approximate f(x_1,\ldots,x_n).We define two quantitative properties of functions --- the it block sensitivity and the minimum Hellinger distance --- that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds.We also point out some connections between sampling and streaming algorithms and lossy compression schemes.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 2: Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Journal of Computer and System Sciences, v.52 n.2, p.299-307, April 1996 [doi>10.1006/jcss.1996.0023]
• 3: 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
• 4: J. O. Berger. Statistical Decision Theory and Bayesian Analysis. Springer-Verlag, 1985.
• 5: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 6: H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey, 1999. Available at http://www.cwi.nl/rdewolf.
• 7: Ran Canetti , Guy Even , Oded Goldreich, Lower bounds for sampling algorithms for estimating the average, Information Processing Letters, v.53 n.1, p.17-25, Jan. 13, 1995 [doi>10.1016/0020-0190(94)00171-T]
• 8: Shih-Fu Chang, Compressed-domain techniques for image/video indexing and manipulation, Proceedings of the 1995 International Conference on Image Processing (Vol. 1)-Volume 1, p.314, October 23-26, 1995
• 9: Moses Charikar , Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Towards estimation error guarantees for distinct values, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.268-279, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335230]
• 10: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. American Mathematical Society, 23:493-507, 1952.
• 11: P. Dagum , R. Karp , M. Luby , S. Ross, An optimal algorithm for Monte Carlo estimation, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.142, October 23-25, 1995
• 12: P. Diaconis. Group Representation in Probability and Statistics. IMS Lecture Series 11, Institute of Mathematical Statistics, 1999.
• 13: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 14: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, Testing and spot-checking of data streams (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.165-174, January 09-11, 2000, San Francisco, California, United States
• 15: Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
• 16: O. Goldreich and D. Ron. On testing expansion in bounded-degree graphs. Electronic Colloquium on Computational Complexity (ECCC), 2000. TR00-020.
• 17: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 18: W. Hoeding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58:13-30, 1963.
• 19: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 20: Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
• 21: L. Le Cam and G. Lo Yang. Asymptotics in Statistics - Some Basic Concepts, pages 24-30. Springer-Verlag, 1990.
• 22: Ashwin Nayak , Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.384-393, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301349]
• 23: Noam Nisan, CREW PRAMs and decision trees, SIAM Journal on Computing, v.20 n.6, p.999-1007, Dec. 1991 [doi>10.1137/0220062]
• 24: J. Radhakrishnan , A. Ta-Shma, Tight bounds for depth-two superconcentrators, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.585, October 19-22, 1997
• 25: Leonard J. Schulman , Vijay V. Vazirani, Majorizing estimators and the approximation of #P-complete problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.288-294, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301320]
• 26: D. Siegmund. Sequential Analysis - Tests and Confidence Intervals. Springer-Verlag, 1985.
• 27: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 28: Harry L. Van Trees, Detection, Estimation, and Modulation Theory: Radar-Sonar Signal Processing and Gaussian Signals in Noise, Krieger Publishing Co., Inc., Melbourne, FL, 1992
• 29: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 30: A.-C. Yao. Probabilistic computations: toward a unified measure of complexity. InProceedings of the 18th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 222-227, 1977.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Performance, Theory, Verification