通过正向分布偏移，让难学问题变易学。
Positive Distribution Shift as a Framework for Understanding Tractable Learning
- 用合适训练分布替代真实分布，反向提升学习效率。
- 在标准梯度训练下，使原本计算困难的问题变得可解。
- 适合关注训练数据设计与算法效率优化的研究者。
我们研究一种场景：目标是基于目标分布 D(x) 学习目标函数 f(x)，但训练使用来自不同分布 D'(x) 的独立同分布样本，标签由真实目标函数 f(x) 给出。这种分布偏移（此处为协变量偏移）通常被视为负面因素，会阻碍学习。与此相反，我们主张若选择合适的 D'(x)，偏移可带来正面效果，即正向分布偏移（PDS）。这一视角对现代机器学习至关重要，许多创新聚焦于寻找优良的训练分布 D'(x)，而非改进训练算法。我们进一步指出，其优势多为计算性而非统计性，使原本计算困难的问题在标准梯度训练下变得可处理。本文形式化了 PDS 的多种变体，证明某些难学类在 PDS 下可被轻松学习，并与成员查询学习建立联系。
原文摘要 · Abstract (English)
We study a setting where the goal is to learn a target function f(x) with respect to a target distribution D(x), but training is done on i.i.d. samples from a different training distribution D'(x), labeled by the true target f(x). Such a distribution shift (here in the form of covariate shift) is usually viewed negatively, as hurting or making learning harder, and the traditional distribution shift literature is mostly concerned with limiting or avoiding this negative effect. In contrast, we argue that with a well-chosen D'(x), the shift can be positive and make learning easier -- a perspective called Positive Distribution Shift (PDS). Such a perspective is central to contemporary machine learning, where much of the innovation is in finding good training distributions D'(x), rather than changing the training algorithm. We further argue that the benefit is often computational rather than statistical, and that PDS allows computationally hard problems to become tractable even using standard gradient-based training. We formalize different variants of PDS, show how certain hard classes are easily learnable under PDS, and make connections with membership query learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。