# Limitations of Membership Queries in Testable Learning

arXiv: https://arxiv.org/abs/2512.02279 · HTML: https://mlsanity.com/paper/2512.02279/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 29 references that are in the map.
- First posted on arXiv 1 Dec 2025.

## Builds on (most cited first, 12 of 12)

- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Testable Learning with Distribution Shift](https://mlsanity.com/paper/2311.15142/) (2023)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Properly learning decision trees in almost polynomial time](https://mlsanity.com/paper/2109.00637/) (2021)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [From average case complexity to improper learning complexity](https://mlsanity.com/paper/1311.2272/) (2013)
- [Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds](https://mlsanity.com/paper/2404.02364/) (2024)
- [Testably Learning Polynomial Threshold Functions](https://mlsanity.com/paper/2406.06106/) (2024)
- [Quality control in sublinear time: a case study via random graphs](https://mlsanity.com/paper/2508.16531/) (2025)

## Built on by (most cited first, 2 of 2)

- [Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift](https://mlsanity.com/paper/2605.07005/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

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 [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 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.