Qinglin Meng

Qinglin Meng

PhD Candidate in Computer Science at Purdue University. Research in machine learning theory, reinforcement learning, and LLMs.

An Optimal Sauer Lemma Over ℓ-ary Alphabets

Published in arXiv preprint arXiv:2604.12952, 2026

We establish an optimal generalization of the classical Sauer-Shelah lemma to the multiclass setting over ℓ-ary alphabets. Our result gives tight bounds on the growth function for multiclass hypothesis classes and has implications for sample complexity in multiclass learning theory.

Steve Hanneke, Qinglin Meng, Shay Moran, Amirreza Shaeiri (alphabetical order)
Download Paper