Learning Shuffle Ideals with Membership Queries and Contrastive Examples

S. Mahmoud Mousawi; Pierluigi San Pietro; Sandra Zilles

cs.FLSep 26, 2026

Learning Shuffle Ideals with Membership Queries and Contrastive Examples

Authors: S. Mahmoud Mousawi, Pierluigi San Pietro, Sandra Zilles

Organizations: University of Regina, Canada · DEIB-Politecnico di Milano and CNR-IEIIT, Italy · Alberta Machine Intelligence Institute, Canada

Abstract

This paper studies learning of shuffle ideals with membership queries as well as with contrastive queries---a form of membership query that reveals not only whether a selected word $w$ is in the target language or not, but also provides a most similar word $w'$ that belongs to the target language if %and only if $w$ does not. For both settings, it is shown that even some very simple classes of shuffle ideals cannot be learned efficiently. By contrast, we obtain positive learnability results for classes of shuffle ideals that meet certain structural conditions. In the case of membership queries, these structural conditions are related to the previously studied notion of universal words, and raise new questions in word combinatorics. In the case of contrastive queries, the structural conditions relate to partitioning sets of words that are listed in shortlex order.

On the Sample Complexity of Active Learning with Membership Queries
Sep 23, 2026Ganghua Wang, Shaddin DughmiActive Learning Statistical Learning Theory
Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California
What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1Sample Compression Halfspace Learning
Purdue University · Stanford University · Google Research +1
Optimal Quantum-Classical Separations for Exact Learning
Sep 29, 2026Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. MandeBoolean Function Learning
IBM Research · QuICS, University of Maryland · University of Liverpool

Sep 23, 2026J/K move · Enter open · S save

On the Sample Complexity of Active Learning with Membership Queries

Ganghua Wang, Shaddin Dughmi

Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California

Active Learning Statistical Learning Theory

Open paper AskPDF arXiv

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

Abstract

Explore similar work

On the Sample Complexity of Active Learning with Membership Queries

What is Learnable in Valiant's Theory of the Learnable?

Optimal Quantum-Classical Separations for Exact Learning