提出高效且可证明的算法，解决特征分布偏移下的期望估计问题。
Efficient and Provable Algorithms for Covariate Shift
- 基于有标签训练数据和无标签测试数据，估计任意有界函数的期望值。
- 首次给出无限制函数下的样本复杂度与计算保证，实现理论突破。
- 适合关注分布偏移理论与鲁棒学习的研究者使用。
协变量偏移是处理训练与测试分布差异（即分布偏移）时广泛采用的假设，其核心在于标签在特征条件下的分布保持不变，但特征本身的分布存在差异。尽管该问题研究广泛，但相关算法的理论保证仍十分有限。本文聚焦于估计任意未知且有界的函数 𝐟 在测试分布下的期望值 𝔼_{𝐱̃∼p_test} 𝐟(𝐱̃)，仅需利用有标签训练样本 (𝐱ᵢ, 𝐟(𝐱ᵢ)) 和无标签测试样本 𝐱̃ᵢ；该问题为多个经典学习任务的核心子问题。本文提出若干高效算法，提供可证明的样本复杂度与计算性能保证。更重要的是，首次对 𝐟 无限制情形下的算法进行了严格分析，为协变量偏移问题奠定了坚实的理论基础。
原文摘要 · Abstract (English)
Covariate shift, a widely used assumption in tackling {\it distributional shift} (when training and test distributions differ), focuses on scenarios where the distribution of the labels conditioned on the feature vector is the same, but the distribution of features in the training and test data are different. Despite the significance and extensive work on covariate shift, theoretical guarantees for algorithms in this domain remain sparse. In this paper, we distill the essence of the covariate shift problem and focus on estimating the average $\mathbb{E}_{\tilde{\mathbf{x}}\sim p_{\mathrm{test}}}\mathbf{f}(\tilde{\mathbf{x}})$, of any unknown and bounded function $\mathbf{f}$, given labeled training samples $(\mathbf{x}_i, \mathbf{f}(\mathbf{x}_i))$, and unlabeled test samples $\tilde{\mathbf{x}}_i$; this is a core subroutine for several widely studied learning problems. We give several efficient algorithms, with provable sample complexity and computational guarantees. Moreover, we provide the first rigorous analysis of algorithms in this space when $\mathbf{f}$ is unrestricted, laying the groundwork for developing a solid theoretical foundation for covariate shift problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。