This paper examines the computational and sample complexity of answering \(\varvec{k}\) -wise statistical queries, which were introduced by Blum et al. (J. ACM 50(4), 506–519, 2003) as a generalization to the standard statistical query model of Kearns (J. ACM 45(6), 983–1006, 1998). In particular, our paper studies two sample reuse schemes: (1) reusing independent “pseudo-samples” for adaptive queries and (2) reusing dependent \(\varvec{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 \(\varvec{k}\) , the arity of the query, and \(\varvec{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.
