Limitations of Membership Queries in Testable Learning

Jane Lange, Mingda Qiao · 2025

Read Limitations of Membership Queries in Testable Learning by Jane Lange, Mingda Qiao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02279.txt.

Introduction

Membership queries let a learning algorithm ask for the label of any example it invents, a power that speeds many learning tasks. Jane Lange and Mingda Qiao prove in 2025 a limit on that power inside testable learning, where the algorithm must also verify its assumptions about the data distribution.

In that model, membership queries cannot lower the time complexity below what sample-only, distribution-specific learning already achieves. The negative result is useful: it tells algorithm designers not to chase query-based speedups where none exist. Testable learning matters because it promises learning guarantees that survive contact with data whose distribution is not fully known.

Catalog record

CREATORJane Lange, Mingda Qiao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE110 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02279

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Limitations of Membership Queries in Testable Learning Jane Lange, Mingda Qiao Abstract Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the testable learning model of Rubinfeld and Vasilyan [ 23 ] , membership queries cannot decrease the time complexity of testable learning algorithms beyond the complexity of sample-only distribution-specific learning. In the testable learning model, the learner must output a hypothesis whenever the data distribution satisfies a desired property, and if it outputs a hypothesis, the hypothesis must be near-optimal. We give a general reduction from sample-based refutation of boolean concept classes, as presented in [ 25 , 18 ] , to testable learning with queries (TL-Q). This yields lower bounds for TL-Q via the reduction from learning to refutation given in [ 18 ] . The result is that, relative to a concept class and a distribution family, no m m -sample TL-Q algorithm can be super-polynomially more time-efficient than the best m m -sample PAC learner. Finally, we define a class of “statistical” MQ algorithms that encompasses many known distribution-specific MQ learners, such as those based on influence estimation or subcube-conditional statistical queries. We show that TL-Q algorithms in this class imply efficient statistical-query refutation and learning algorithms. Thus, combined with known SQ dimension lower bounds, our results imply that these efficient membership query learners cannot be made testable. 1 Introduction In distribution-specific PAC learning, a learning algorithm is only required to output a competitive hypothesis when the data distribution satisfies some property. Distribution-specific PAC often allows for much more efficient learning than distribution-free PAC, but with the following shortcoming: if the distribution does not satisfy the property, then the behavior of the learner is completely undefined. A testable agnostic learning algorithm [ 23 ] alleviates this shortcoming by combining a distribution-specific learner with a tester for the desired property. It may output a hypothesis or it may reject the distribution and output \bot . The testable learner is run on i.i.d. samples from an unknown distribution \mathcal{D} over \mathcal{X}\times\{0,1\} , and has the following behavior: • Soundness: If the learner outputs a hypothesis h , then with high probability \Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq y]\leq\mathsf{opt}+\varepsilon, where \mathsf{opt} is the error of the best concept in the concept class. A semi-agnostic variant of this condition, with \mathsf{opt}+\varepsilon replaced by O(\mathsf{opt})+\varepsilon , has also been considered. • Completeness: If the distribution \mathcal{D} has the desired property, then the learner outputs a hypothesis (instead of \bot ) with high probability. There is a significant body of work studying the sample and time complexities of testable learning for various concept classes and distribution properties in both the agnostic ( \mathsf{opt}+\varepsilon ) and semi-agnostic ( O(\mathsf{opt})+\varepsilon ) settings [ 23 , 13 , 9 , 14 , 24 ] . There are efficient algorithms for testable learning in cases where distribution-free learning cannot be done efficiently. 1.1 The Power of Membership Queries in Agnostic Learning One might hope to testably learn more efficiently by strengthening the learner’s access to the data distribution. In the membership query (MQ) model, we think of the data as being drawn from a distribution \mathcal{D}_{x} over \mathcal{X} and labeled by some unknown function f:\mathcal{X}\to\{0,1\} . The learner gets i.i.d. samples from \mathcal{D}_{x} and may also query any point x\in\mathcal{X} and receive its label f(x) . The work of [ 12 ] shows that under the standard cryptographic assumption of one-way functions, membership queries can speed up agnostic learning in the distribution-specific setting, but not in the distribution-free setting. In the distribution-free setting, every concept class that can be agnostically learned with MQs can be agnostically learned with just random examples. In contrast, in the uniform-distribution-specific setting, there exists a concept class that can be learned strictly more efficiently with MQs. Separations exist for more “natural” concept classes under the stronger assumption that learning sparse parities with noise (LSPN) is hard. For example, over the uniform distribution on \{0,1\}^{n} , k -juntas can be learned in \mathop{\mathrm{poly}}(n)\cdot 2^{O(k)} time with membership queries [ 3 , 21 ] . On the other hand, there is a statistical query lower bound of n^{\Omega(k)} [ 5 ] , and if LSPN is hard then one cannot hope to do better than this bound with random examples. Similarly, polynomial-size decision trees can be learned improperly in polynomial time [ 19 , 15 ] and properly in n^{O(\log\log n)} time [ 1 ] with membership queries, while there is an SQ lower bound of n^{\Omega(\log n)} [ 2 ] , and LSPN implies one cannot do better than this bound either. 1.2 Limitations of Membership Queries in Testable Learning If membership queries do help in the distribution-specific setting but do not help in the distribution-free setting, one may then naturally wonder whether they ought to help in the testable setting as well. A testable learner with queries (TL-Q) has both sample access to the unknown data distribution and membership query access to the unknown function, and must satisfy the soundness and completeness guarantees of ordinary testable learning. Question 1.1 . How much can membership queries speed up the task of testable learning? Our results show that membership queries are quite weak in the TL-Q setting. Particularly, whenever agnostic learning with random examples is hard — as is believed to be the case for juntas and decision trees — testable learning is hard as well, even with queries. Theorem 1.2 ( Corollary 3.4 , informal) . If a concept class \mathcal{C} is agnostically testably learnable with queries in time t over a distribution \mathcal{D} , then it is agnostically learnable with random examples in time \mathop{\mathrm{poly}}(t) over \mathcal{D} as well. Corollary 1.3 . If LSPN is hard, then no concept class containing k -parities as a subset can be agnostically testably learned in n^{o(k)} time over the uniform distribution, even with membership queries. Furthermore, we show that SQ lower bounds rule out a large class of natural query-based learning algorithms. We define a class of “statistical” membership query (MQ-SQ) algorithms — those that use membership queries only to sample from particular distributions over the input domain. For example, algorithms that use MQs only to estimate influences or to make SQs over large subsets of \{0,1\}^{n} are MQ-SQ algorithms (this includes the aforementioned uniform-distribution algorithms of [ 19 , 15 , 1 ] ). We show that such algorithms cannot be “made testable” with respect to the uniform distribution without introducing non-statistical use of membership queries, due to the SQ lower bounds. Theorem 1.4 ( Theorem 4.6 , informal) . If a concept class \mathcal{C} is testably learnable in time t over a distribution \mathcal{D} by an MQ-SQ algorithm, then the SQ dimension of \mathcal{C} with respect to \mathcal{D} is at most \mathop{\mathrm{poly}}(t) . 1.3 Technical Overview Our reductions are through the intermediate task of refutation . Refutation, as presented in [ 25 , 18 ] , is the problem of distinguishing examples correlated with some function in the concept class from examples labeled uniformly at random. The work of [ 25 ] shows that in the distribution-free setting, refutation and realizable learning are polynomially equivalent, and the work of [ 18 ] shows an analogous statement in the

Read the complete text