具有分布转变的可测试学习

Nov, 2023

Testable Learning with Distribution Shift

Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

TL;DR在学习分布转移的基本问题中，我们提出了一个新模型，称为可测试学习，可以通过一个相关的测试来得到分类器在测试分布上的性能证明，并证明了对于一些常见概念类别如半空间、半空间的交、决策树等，以及具有低次 $L_2$- 夹逼多项式逼近器的任何函数类别都可以在这个模型下学习。

Abstract

We revisit the fundamental problem of learning with distribution shift, in which a learner is given labeled samples from training distribution $D$, unlabeled samples from test distribution $D'$ and is asked to output a classifier with low test error. The standard approach in this setti

learning with distribution shift testable learning efficient algorithms halfspaces decision trees

发现论文，激发创造

学习中的分布偏移的高效差异性测试

提供了可靠与高效的算法来测试本地化的差异距离，进一步扩展了 TDS 学习模型并改进了之前相关的工作，同时提供了针对常数深度电路的指数级改进，与低维凸集的首个正面结果。

Jun, 2024

学习带有分布偏移的半空间交集：改进算法和 SQ 下界

针对高斯训练分布的交叉半空间集的可测试学习，证明了一种新的上界算法，能在多项式时间内实现 TDS 学习，且达到精确度 e，扩展了 TDS 学习工具库。

Apr, 2024

处理任意协变量偏移学习的容错算法

研究在任意分布转移下的学习问题，重点关注 PQ 学习、TDS 学习两个框架以及谱异常移除技术对多项式回归及容忍可测试学习的影响。

Jun, 2024

针对测试时攻击与分布偏移的可靠学习

本文讨论机器学习算法在环境未完全准确的情况下的应用，尤其是面对对抗攻击和分布变化的情况下，引入新的鲁棒性可靠性保证，并提供优秀的学习方案，分析了可靠性区域，同时分别分析了近似对数凹分布和平滑概率分布下的线性分类器和光滑边界分类器的可靠性区域中可靠性区域的概率质量上界。

Apr, 2023

(几乎) 通过分歧差异证明分布偏移下的误差界

本研究通过使用无标签测试数据来推导深度神经网络在分布转移下的误差（几乎）保证上界，并提出了一种理论上合理、在实践中表现更优的 “不一致损失” 用于评估误差保证上界的较紧估计。

Jun, 2023

测试者学习半空间的通用算法

本研究提出了一种普适性的半空间测试学习算法，它可以在所有满足 Poincaré 不等式的分布上获得较小误差，具体实现是使用 sum-of-squares 算法检查分布的超对称性。

May, 2023

多项式阈值函数可测学习

该研究论文介绍了可测试学习的概念，并研究了在测试者接受标准高斯数据的情况下，多项式阈值函数的可测试学习。研究结果表明，任意常数阶的多项式阈值函数在多项式时间内可以以超出误差 ε 的程度可测试地学习，与测试属性的典型模型相匹配。同时，该研究证明了直接证明可测试学习（而非愚弄测试者）的方法在多项式阈值函数上是行不通的。

Jun, 2024

分布偏移下的统计检验

本文介绍了在分布偏移下的统计检验，提出了一种通过重新采样构建辅助数据集的一般化检验方法，可用于处理强化学习和因果推断等多个领域的问题。

May, 2021

通过分布式鲁棒性优化应对标签漂移

本论文提出了一种基于分布鲁棒优化的模型，通过设计并分析梯度下降 - 近端镜像上升算法，用一次训练获得一个对多种标签偏移都具有稳健性的单一分类器，并在 CIFAR-100 和 ImageNet 上的实验中展示出其显著的性能提高。

Oct, 2020

作为双样本检验代理的分类准确性

探究在高维情况下对分类器的精度验证，证明一种基于排列组合的测试方法具有连续性及德克斯特拉极限分布的高斯近似测试也具有连续性，并以高斯分布为例进一步研究了线性判别分析和 Hotelling's 测试等方法的功率。

Feb, 2016