用更弱的约束实现分布偏移下的高效学习，首次让DNF公式在均匀分布下可快速学习。
Iterative Chow Filtering for Learning with Distribution Shift
- 提出迭代查夫滤波，通过低阶查夫参数筛选不匹配训练分布的测试点。
- 在均匀分布下对DNF公式实现准多项式时间学习，性能接近普通PAC学习。
- 适用于常数深度电路和多项式阈值函数，显著优于已有方法。
Goel等人近期提出了首个在挑战性的PQ框架下处理分布偏移的高效算法。该框架中，学习者接收带标签的训练样本、无标签的测试样本，需对测试集正确预测，但可对分布外样本选择不预测。其结果依赖于强假设的${\cal L}_2$夹逼近似，导致对如DNF公式等基础函数类边界较差。本文证明，较弱的${\cal L}_1$夹逼已足够实现高效的PQ学习。由此，我们首次获得在均匀分布下对DNF公式的准多项式时间学习算法，并几乎达到普通PAC学习的保证。更广泛地，对常数深度电路和常数次数多项式阈值函数等类别的边界有指数级改进。核心技术是迭代查夫滤波：利用低阶查夫参数识别并剔除与训练分布不兼容的测试点。
原文摘要 · Abstract (English)
Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled training examples, unlabeled test examples, and must make correct predictions on the test set but is allowed to abstain from predicting on out-of-distribution points. Their results rely on ${\cal L}_2$ sandwiching approximations, a strong requirement that leads to poor bounds for several basic function classes such as DNF formulas. Here, we show that the weaker notion of ${\cal L}_1$ sandwiching suffices for efficient PQ learning. As a consequence, we obtain the first quasipolynomial-time PQ learning algorithm for DNFs under the uniform distribution and essentially match the guarantees known for ordinary PAC learning. More broadly, our bounds provide exponential improvements for several classes including constant depth circuits and constant degree polynomial threshold functions. Our main technical ingredient is Iterative Chow Filtering, a new procedure that uses low-degree Chow parameters to identify and remove test points incompatible with the training distribution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。