Strategic PAC Learnability via Geometric Definability

📄 arXiv: 2605.13426v1 📥 PDF

作者: Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, Alexander Shlimovich

分类: cs.LG, math.AG

发布日期: 2026-05-13

💡 一句话要点

通过几何可定义性提出战略PAC可学习性解决方案

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 战略分类 PAC学习 几何可定义性 样本复杂度 一阶逻辑 机器学习 博弈论

📋 核心要点

  1. 核心问题：现有方法在处理战略分类时，诱导的假设类可能导致样本复杂度失控，甚至变得不可学习。
  2. 方法要点：论文通过引入几何可定义性假设，确保假设类和成本诱导的邻域关系可以用一阶公式定义，从而控制学习复杂度。
  3. 实验或效果：在几何可定义性假设下，证明了学习性得以保留，并且样本复杂度与定义公式的复杂度相关。

📝 摘要（中文）

战略分类研究个体可以在一定成本下修改特征以影响分类器决策的学习环境。核心问题在于诱导的（战略）假设类的样本复杂度如何依赖于基础假设类的复杂度及可行操作的成本结构。先前研究表明，在某些自然设置中，诱导复杂度可以被控制。然而，本文展示了在一般情况下，这种保证并不成立，甚至在简单案例中也存在问题。为了解决这一问题，本文引入了几何可定义性假设，证明在此假设下，学习性得以保留，样本复杂度由定义公式的复杂度控制。

🔬 方法详解

问题定义：本文旨在解决在战略分类中，诱导假设类的样本复杂度如何受到基础假设类复杂度和成本结构的影响。现有方法在简单情况下可能导致诱导类的VC维度无限，造成学习问题不可解。

核心思路：论文提出通过几何可定义性假设来引入结构，使得假设类和成本诱导的邻域关系可以用一阶公式在实数域上定义。这种设计使得可以用算术运算、指数、对数和比较来描述假设和成本，从而控制学习复杂度。

技术框架：整体框架包括定义假设类和成本结构的几何可定义性假设，利用一阶逻辑公式来描述这些结构，确保在此假设下的学习性和样本复杂度的可控性。

关键创新：最重要的技术创新在于引入几何可定义性假设，解决了诱导假设类在复杂情况下失控的问题，与现有方法相比，提供了更为稳健的学习保证。

关键设计：关键设计包括使用一阶公式来定义假设类和成本结构，确保这些定义能够涵盖广泛的自然类和成本函数，如$ ext{l}_p$距离、Wasserstein距离等。通过这种方式，样本复杂度与定义公式的复杂度直接相关。

📊 实验亮点

在几何可定义性假设下，论文证明了学习性得以保留，样本复杂度与定义公式的复杂度直接相关。这一结果表明，战略行为不会导致学习问题的不可解性，提供了理论上的重要进展。

🎯 应用场景

该研究的潜在应用领域包括机器学习中的战略决策、个性化推荐系统和博弈论等。通过提供对战略分类的更好理解，能够帮助设计更有效的学习算法，提升分类器在动态环境中的适应性和准确性。

📄 摘要（原文）

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension $1$ on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over $\mathbb{R}_{\mathtt{exp}}$. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including $\ell_p$ distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.