Approximate Replicability in Learning
This work addresses the challenge of making learning algorithms more practical by relaxing strict replicability requirements, which is incremental as it builds on prior impossibility results to enable learning in tasks like threshold learning.
The paper tackles the problem of replicability in learning, which is often prohibitively costly, by proposing three relaxations—pointwise, approximate, and semi-replicability—and shows that for constant parameters, these lead to sample-optimal agnostic PAC learners with sample complexities of Θ(d/α²) for the first two and Θ(d²/α²) for the third.
Replicability, introduced by (Impagliazzo et al. STOC '22), is the notion that algorithms should remain stable under a resampling of their inputs (given access to shared randomness). While a strong and interesting notion of stability, the cost of replicability can be prohibitive: there is no replicable algorithm, for instance, for tasks as simple as threshold learning (Bun et al. STOC '23). Given such strong impossibility results we ask: under what approximate notions of replicability is learning possible? In this work, we propose three natural relaxations of replicability in the context of PAC learning: (1) Pointwise: the learner must be consistent on any fixed input, but not across all inputs simultaneously, (2) Approximate: the learner must output hypotheses that classify most of the distribution consistently, (3) Semi: the algorithm is fully replicable, but may additionally use shared unlabeled samples. In all three cases, for constant replicability parameters, we obtain sample-optimal agnostic PAC learners: (1) and (2) are achievable for ``free" using $Θ(d/α^2)$ samples, while (3) requires $Θ(d^2/α^2)$ labeled samples.