Sampling lower bounds via information theory

ABSTRACT

We present a novel technique, based on the Jensen-Shannon divergence from information theory, to prove lower bounds on the query complexity of sampling algorithms that approximate functions over arbitrary domain and range. Unlike previous methods, our technique does not use a reduction from a decision promise problem. As a result, it gives stronger bounds for functions that possess a large set of inputs, each two of which exhibit a gap in the function value.We demonstrate the technique with new query complexity lower bounds for three fundamental problems: (1) the "election problem", for which we obtain a quadratic improvement over previous bounds, (2) low rank matrix approximation, for which we prove the first lower bounds, showing that the algorithms given for this problem are almost optimal, and (3) matrix reconstruction.In addition, we introduce a new method for proving lower bounds on the expected query complexity of functions, using the Kullback-Leibler divergence. We demonstrate its use by a simple query complexity lower bound for the mean.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 3: Ziv Bar-Yossef , Christos H. Papadimitriou, The complexity of massive data set computations, University of California at Berkeley, Berkeley, CA, 2002
• 4: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece [doi>10.1145/380752.380810]
• 5: 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
• 6: 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]
• 7: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 8: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 9: P. Drineas and R. Kannan. Pass efficient algorithm for approximating large matrices. Manuscript, 2002.
• 10: Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509922]
• 11: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 12: O. Goldreich , L. Trevisan, Three Theorems Regarding Testing Graph Properties, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.460, October 14-17, 2001
• 13: G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 1996.
• 14: M. Gutman. Asymptotically optimal classification for multiple tests with empirically observed statistics. IEEE Transactions on Information Theory, 35(2):401--408, 1989.
• 15: T. Kailath. The divergence and Bhattacharyya distance measures in signal selection. IEEE Transactions on Communication Technology, COM-15(1):52--60, 1967.
• 16: S. Kullback and A. Leibler. On information and sufficiency. IEEE Transactions on Information Theory, 22:79--86, 1951.
• 17: J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1):145--151, 1991.
• 18: Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
• 19: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 20: Jaikumar Radhakrishnan , Amnon Ta-Shma, Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators, SIAM Journal on Discrete Mathematics, v.13 n.1, p.2-24, Jan. 2000 [doi>10.1137/S0895480197329508]
• 21: D. Siegmund. Sequential Analysis - Tests and Confidence Intervals. Springer-Verlag, 1985.
• 22: G. T. Toussaint. On some measures of information and their application to pattern recognition. In Proc. Conference on Measures of Information and Their Applications, pages 21--28, 1974.
• 23: J. Ziv. On classification with empirically observed statistics and universal data compression. IEEE Transactions on Information Theory, 34:278--286, 1988.

INDEX TERMS

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

General Terms:
Theory

Keywords:
Jensen-Shannon divergence, lower bounds, query complexity