Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.20200 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911574135930880 |
|---|---|
| author | Hopkins, Max Impagliazzo, Russell Ye, Christopher |
| author_facet | Hopkins, Max Impagliazzo, Russell Ye, Christopher |
| contents | 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 we obtain close to sample-optimal agnostic PAC learners: 1) and 2) are achievable using $O(d/α^2 + 1/α^{4})$ samples, while 3) requires $Θ(d^2/α^2)$ labeled samples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20200 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximate Replicability in Learning Hopkins, Max Impagliazzo, Russell Ye, Christopher Machine Learning 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 we obtain close to sample-optimal agnostic PAC learners: 1) and 2) are achievable using $O(d/α^2 + 1/α^{4})$ samples, while 3) requires $Θ(d^2/α^2)$ labeled samples. |
| title | Approximate Replicability in Learning |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2510.20200 |