# Bounds in Query Learning

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2019.

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

- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Simple online learning with consistent oracle](https://mlsanity.com/paper/2308.08055/) (2023)
- [The Dimension of Self-Directed Learning](https://mlsanity.com/paper/2402.13400/) (2024)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Agnostic Online Learning and Excellent Sets](https://mlsanity.com/paper/2108.05569/) (2021)
- [Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization](https://mlsanity.com/paper/2605.22964/) (2026)
- [Optimal Quantum-Classical Separations for Exact Learning](https://mlsanity.com/paper/2609.38073/) (2026)

## Abstract (arXiv)

We introduce new combinatorial quantities for concept classes, and prove lower and upper bounds for learning complexity in several models of query learning in terms of various combinatorial quantities. Our approach is flexible and powerful enough to enough to give new and very short proofs of the efficient learnability of several prominent examples (e.g. regular languages and regular ω-languages), in some cases also producing new bounds on the number of queries. In the setting of equivalence plus membership queries, we give an algorithm which learns a class in polynomially many queries whenever any such algorithm exists. We also study equivalence query learning in a randomized model, producing new bounds on the expected number of queries required to learn an arbitrary concept. Many of the techniques and notions of dimension draw inspiration from or are related to notions from model theory, and these connections are explained. We also use techniques from query learning to mildly improve a result of Laskowski regarding compression schemes.