Near-Optimal List Replicability from Littlestone Dimension
Abstract
We study the list replicability number in the realizable PAC learning framework and prove that every concept class $H$ over a countable domain with Littlestone dimension $d$ and dual VC dimension $v^*$ satisfies \[ \mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. \] This matches the worst-case lower bound of $2^{Ω(d)}$ up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound $\mathrm{LR}(H)\le 2^{2^{O(d)}}$ of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of $2^{O_ε(d^2)}$ for fixed accuracy $ε>0$ implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of $ε$. The $2^{O(d\log d)}$ bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The $2^{O(dv^*)}$ bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper establishes near-optimal upper bounds on the list replicability number for concept classes with finite Littlestone dimension, exponentially improving previous state-of-the-art results. It introduces a novel inductive framework leveraging irreducibility from differential privacy and a globally stable majority-vote learner, providing rigorous theoretical insights into the relationship between replicability, stability, and combinatorial complexity measures in PAC learning.
Methodology
The paper introduces a novel inductive framework for bounding the list replicability number of concept classes. The core innovation lies in leveraging the combinatorial property of "irreducibility" from differentially private learning to construct a learner that reduces the problem to a class of strictly smaller Littlestone dimension. Additionally, the authors provide a second bound using a globally stable learner based on the majority vote of multiple Empirical Risk Minimization (ERM) runs, utilizing tools from stable regularity. The theoretical proofs are rigorous, establishing near-optimal bounds that significantly improve upon previous doubly exponential results.
Results & evaluation
This is a purely theoretical paper in the domain of learning theory. There are no empirical experiments, datasets, or benchmark evaluations. The "results" are mathematical theorems and bounds. Therefore, experimental evaluation is not applicable in the standard sense, but the strength of the theoretical bounds serves as the primary metric of success.
Reproducibility
The paper is fully reproducible in the mathematical sense. All definitions, lemmas, and theorems are clearly stated, and the proofs are provided in detail. There is no code or experimental setup to reproduce. The clarity of the mathematical exposition is high, allowing other researchers to verify and build upon the results.
Limitations
The bounds are for the realizable PAC learning framework over countable domains. The sample complexity bounds derived are somewhat loose (e.g., $2^{O(d^2 \log d)}$), which may not be tight for all practical scenarios. The results are theoretical and do not provide immediate algorithmic implementations for large-scale machine learning tasks, though they inform the design of stable and private learners.
Broader impact
The results have significant implications for the intersection of learning theory, privacy, and stability. By nearly matching the lower bounds for list replicability, the paper clarifies the fundamental limits of replicable learning. This contributes to the broader goal of making machine learning models more trustworthy and robust. The techniques developed, particularly the use of irreducibility in this context, may inspire new approaches in differentially private learning and stable learning algorithms. The paper establishes near-optimal upper bounds on the list replicability number for concept classes with finite Littlestone dimension, exponentially improving previous state-of-the-art results. It introduces a novel inductive framework leveraging irreducibility from differential privacy and a globally stable majority-vote learner, providing rigorous theoretical insights into the relationship between replicability, stability, and combinatorial complexity measures in PAC learning.
Author of this paper? Send a correction.