Sampling algorithms
Authors:
Open Access
- 6 July 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 266-275
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.Keywords
This publication has 15 references indexed in Scilit:
- Towards estimation error guarantees for distinct values2000
- The quantum query complexity of approximating the median and related statistics1999
- Majorizing estimators and the approximation of #P-complete problems1999
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Let Sleeping Files Lie: Pattern Matching in Z-Compressed FilesJournal of Computer and System Sciences, 1996
- Lower bounds for sampling algorithms for estimating the averageInformation Processing Letters, 1995
- CREW PRAMs and Decision TreesSIAM Journal on Computing, 1991
- Statistical Decision Theory and Bayesian Analysis1985
- A theory of the learnableCommunications of the ACM, 1984
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963