提出三种近似可复现学习方法，让难学任务变为可行
Approximate Replicability in Learning
- 放宽可复现性要求，分三点设计近似方案
- 常数精度下样本复杂度接近最优，部分仅需O(d/α²)样本
- 适合研究学习稳定性与实际算法设计的学者
可复现性（Replicability）由Impagliazzo等人提出，指算法在输入重采样时仍保持稳定（需共享随机源）。然而该性质代价高昂：甚至简单阈值学习也不存在可复现算法（Bun et al. STOC '23）。本文针对PAC学习框架，提出三种自然的可复现性松弛：(1) 点对点式：对任意固定输入保持一致，但不强制全局一致；(2) 近似式：输出假设在多数分布上分类一致；(3) 半式：算法全可复现，但可额外使用共享未标记样本。在常数可复现性下，1)和2)可通过$O(d/α^2 + 1/α^4)$样本实现近乎样本最优的广义PAC学习；3)需$Θ(d^2/α^2)$标注样本。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。