忠实的数据选择：统计极限与可扩展算法

问题

数据选择通常被定义为“最小化仅用该子集训练的模型的总体误差”的问题。但仅凭数据能否真正实现这一目标，即统计极限在哪里，此前并不清楚。

方法

作者首先证明了一个信息论下界。他们构造了一类分类问题：如果没有在量级上大于训练数据的验证数据，那么即使存在好的子集，任何选择器也无法找到它（利用了具有大 girth 的 cubic 图和奇偶约束）。因此，他们将目标改为“忠实性（faithfulness）”。这一标准考察用子集训练的模型分布是否接近用全量数据训练的模型分布。他们将训练建模为 ULA（Unadjusted Langevin Algorithm），并用轨迹累积梯度不一致 G_T(I) 为两个参数分布之间的 KL 散度给出上界。由于最小化 G_T 是 NP-hard 问题，他们提出了一种局部搜索方法，每次接受的交换都会降低该上界。它也可以把其他选择器的结果作为起点，对其进行改进。每个样本的梯度用单个初始检查点来近似。

结果

• 作者证明，在压缩比 λ<1/3 时，对于任何学习器与选择器的组合，都存在期望超额风险不低于 Ω(n/(n+v)) 的问题。因此，要使选择误差降为 0，验证数据规模 v 必须在量级上大于训练数据规模 n。
• 在同一类问题上，全量数据训练以及由知道分布的预言机选出子集进行训练，都能达到 O(1/log n) 量级的较小误差。也就是说，好的子集是存在的，但仅凭数据无法找到。
• 该下界在对训练样本数的依赖上是 tight 的。当验证数据 v=Θ(λn/ε²) 时，选择误差可以降到 ε。
• 作者报告称，在用 SGD 训练的模型中，G_T 与忠实性差距（faithfulness gap）呈现相关性。
• 在 CIFAR-10 和 CIFAR-100 上，所提出的交换式局部搜索取得了与现有静态数据选择基线相当的性能。作者没有声称超越了基线。

局限

实验仅限于 CIFAR-10/100 图像分类，性能与现有方法相当，没有明显优势。忠实性上界依赖于用 ULA 近似 SGD 的假设，每个样本的梯度也只用单个初始检查点来近似。局部搜索不能保证得到 NP-hard 问题的最优解。此外，这一方法本身也无法绕开下界。作者也指出，只有在全量数据训练本身效果已经很好时，它才有意义。

意义

在选择数据选择（剪枝）方法时，本文提供了一个理论依据：如果没有大规模验证数据，“找到了最优子集”这一说法是无法验证的。作为替代，本文提出了一种仅用训练数据即可计算、并能保证与全量数据训练之间差距的标准。它可以在不使上界变差的前提下改进任何选择器的结果，这一点在实践中也很有用。

关键术语

忠实性（Faithfulness）

这一标准衡量用子集训练的模型与用全量数据训练的模型在多大程度上服从相同的分布。即使不知道真实分布，也可以仅用训练数据来估计。

压缩误差与选择误差

压缩误差表示样本中是否存在好的子集，选择误差表示选择算法能否真正找到该子集。本文证明了后者存在下界。

ULA(Unadjusted Langevin Algorithm)

这是一种在梯度下降中加入高斯噪声的训练模型。它可以把训练结果当作参数的概率分布来处理，因此便于计算 KL 散度的上界。

轨迹累积梯度不一致

这是在整个训练路径上，累积子集平均梯度与全量数据平均梯度之间差异的值。减小这个值，忠实性上界就会变小。

原文

• arXiv 摘要页
• PDF
• HTML 全文
• Hugging Face

作者: Ahmed Mehdi Inane, Mahdi Haghifam, Gintare Karolina Dziugaite, Ioannis Mitliagkas · 发布 2026-10-21 · 许可 CC BY 4.0 · 基于全文分析

本解读是 AI 阅读论文后撰写的摘要，请以论文原文为准。