On Sample Reuse Methods for Answering k-wise Statistical Queries

This paper examines the computational and sample complexity of answering k-wise statistical queries, which were introduced by Felman and Ghazi [9] as a generalization to the standard statistical query model of Kearns [11]. In particular, our paper studies two sample reuse schemes: (1) reusing independent “pseudo-samples” for adaptive queries and (2) reusing dependent k-wise samples for non-adaptive queries. Comparing to a baseline non-reuse strategy, we show that the first reuse method offers a trade-off between k, the arity of the query, and M, the total number of queries to be answered. We also show that the second reuse method performs no worse than the baseline, and possibly better, from the perspective of variance reduction.