Improved bounds on list replicability for PAC learning classes
Near-Optimal List Replicability from Littlestone Dimension
Machine Learning
Summary
This paper studies how to reliably reproduce learning results from limited data in a specific machine learning setting called PAC learning. It shows a much tighter limit, called the list replicability number, on how many possible solutions need to be considered to ensure replicability. The authors improve upon previous results by giving bounds that depend only on inherent complexity measures of the learning problem, and not on accuracy parameters. Their techniques involve new mathematical frameworks and stability ideas from privacy research.
What this means in practice
- •For machine learning engineers: Design learning algorithms with predictable reproducibility guarantees based on problem complexity.
- •For data privacy teams: Build stable learners that maintain performance while supporting privacy constraints informed by new stability bounds.
A theory result. No direct application yet.
Authors
Ari Blondal, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
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.