标题： PAC可学习性在执行性存在情况下的表现 显示英文标题

标题： PAC Learnability in the Presence of Performativity

摘要： 在机器学习模型在现实应用中广泛采用之后，表现性现象，即测试分布中的模型相关变化，变得越来越普遍。不幸的是，由于模型通常仅基于原始（未偏移）分布的样本进行训练，这种表现性变化可能导致测试时的性能下降。在本文中，我们通过经典的PAC（可能近似正确）学习框架，研究了表现性二分类问题是否可学习以及何时可学习的问题。我们提出了几种表现性场景，特别是考虑了标签分布中的线性偏移，以及标签和特征的更一般变化。我们构建了一个表现性经验风险函数，该函数仅依赖于原始分布的数据和表现性效应类型，并且是对分类器在偏移分布上的真实风险的无偏估计。最小化这种表现性风险表明，在标准二分类设置中任何PAC可学习的假设空间对于所考虑的表现性场景仍然是PAC可学习的。我们还对我们的表现性风险最小化方法进行了广泛的实验评估，并在合成和真实数据上展示了其优势。 显示英文摘要

摘要： Following the wide-spread adoption of machine learning models in real-world applications, the phenomenon of performativity, i.e. model-dependent shifts in the test distribution, becomes increasingly prevalent. Unfortunately, since models are usually trained solely based on samples from the original (unshifted) distribution, this performative shift may lead to decreased test-time performance. In this paper, we study the question of whether and when performative binary classification problems are learnable, via the lens of the classic PAC (Probably Approximately Correct) learning framework. We motivate several performative scenarios, accounting in particular for linear shifts in the label distribution, as well as for more general changes in both the labels and the features. We construct a performative empirical risk function, which depends only on data from the original distribution and on the type performative effect, and is yet an unbiased estimate of the true risk of a classifier on the shifted distribution. Minimizing this notion of performative risk allows us to show that any PAC-learnable hypothesis space in the standard binary classification setting remains PAC-learnable for the considered performative scenarios. We also conduct an extensive experimental evaluation of our performative risk minimization method and showcase benefits on synthetic and real data.