发现粗粒度与细粒度分布偏移学习模型等价，突破了传统认知。
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
- 通过分支程序提升拒绝型学习器的区分能力，实现模型间转化
- 证明半空间类在无分布假设下TDS学习存在计算难问题
- 引入成员查询可绕过难题，实现高效半空间学习
近期关于分布偏移下可证明高效的算法研究聚焦于两种模型：PQ学习（Goldwasser等，2020）和TDS学习（Klivans等，2024）。TDS学习者可在检测到分布偏移时拒绝整个测试集，而PQ学习者仅能逐点拒绝异常样本。本文核心结果是：在无分布假设条件下，这两种模型存在惊人等价性。我们给出了任意布尔概念类上从PQ学习到TDS学习的高效黑箱归约。该等价性首次揭示了半空间等基础类在无分布假设下的TDS学习困难性。技术核心在于利用分支程序提升那些已拒绝目标域的TDS学习者的弱区分能力。此外，我们还证明：若赋予学习者成员查询能力，可避开上述困难，实现半空间在无分布假设下的高效可学习性。算法通过迭代对训练数据施加连续的Forster变换，逐步恢复大间隔分离器。
原文摘要 · Abstract (English)
Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al. (2024)). Algorithms for TDS learning are allowed to reject a test set entirely if distribution shift is detected. In contrast, PQ learners may only reject points that are deemed out-of-distribution on an individual basis. Our main result is a surprising equivalence between these two models in the distribution-free setting. In particular, we give an efficient black-box reduction from PQ learning to TDS learning for any Boolean concept class. This equivalence implies the first hardness results for distribution-free TDS learning of basic classes such as halfspaces. The main technical contribution underlying our equivalence is a method for boosting, via branching programs, the weak distinguishing power of TDS learners that have rejected the target domain. We also show that giving a learner access to membership queries sidesteps these hardness results and allows for efficient, distribution-free PQ learnability of halfspaces. Our algorithm iteratively recovers large-margin separators obtained by applying successive Forster transforms on the training data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。