{"ID":2834762,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.02279","arxiv_id":"2512.02279","title":"Limitations of Membership Queries in Testable Learning","abstract":"Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the \\emph{testable learning} model of Rubinfeld and Vasilyan [RV23], 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 \\emph{refutation} of boolean concept classes, as presented in [Vadhan17, KL18], to testable learning with queries (TL-Q). This yields lower bounds for TL-Q via the reduction from learning to refutation given in [KL18]. The result is that, relative to a concept class and a distribution family, no $m$-sample TL-Q algorithm can be super-polynomially more time-efficient than the best $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.","short_abstract":"Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the \\emph{testable learning} model of Rubinfeld and Vasilyan [RV23], membership queries cannot decrease the time complexity of testable learning algorithms beyond the complexity of sample-...","url_abs":"https://arxiv.org/abs/2512.02279","url_pdf":"https://arxiv.org/pdf/2512.02279v1","authors":"[\"Jane Lange\",\"Mingda Qiao\"]","published":"2025-12-01T23:50:20Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.DS\"]","methods":"[]","has_code":false}