🤖 machine learning

OrderDP: A Theoretically Guaranteed Lossless Dynamic Data Pruning Framework

OrderDP 是一个在理论上得到保证、即插即用的动态数据剪枝框架，它通过随机选择一个子集并基于代理损失选择前 $q$ 个样本，实现了近乎无损的训练加速以及超过 40% 的成本降低。

原作者： Chenhan Jin, Shengze Xu, Qingsong Wang, Fan Jia, Dingshuo Chen, Tieyong Zeng

发布于 2026-06-09

📖 1 分钟阅读☕ 轻松阅读

原作者： Chenhan Jin, Shengze Xu, Qingsong Wang, Fan Jia, Dingshuo Chen, Tieyong Zeng

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位正试图为 1,000 名宾客烹饪一场盛大宴会的厨师。你有一份食谱，要求在开始烹饪之前，必须品尝完整个巨大仓库里的每一种食材。这种“全量品尝”能确保菜肴完美无瑕，但它非常耗时，并且会消耗大量的燃料（计算能力）。

数据剪枝（Data Pruning） 的概念是：说，“让我们只品尝一小部分更聪明、更精选的食材，以节省时间，并希望最终的菜肴味道同样出色。”

现有方法的问题在于，它们往往倾向于挑选那些最“辛辣”或“最有趣”的食材进行品尝。虽然这节省了时间，但却会使厨师对整体风味的理解产生偏差。最终的菜肴可能很棒，但厨师对于“为什么味道好”的直觉会产生偏差，导致不稳定性，或者让菜肴的味道与原版相比略有偏差。

由此，OrderDP 应运而生，这是一种新的方法。你可以将 OrderDP 视为一种智能的双步品尝协议，它保证了最终的菜肴与使用整个仓库进行品尝后的效果无法区分，且速度更快。

OrderDP 如何运作：“先品尝后选择”类比

OrderDP 不再试图在整个仓库中一次性挑选出“最好的”食材（这很难且带有偏见），而是每当它烹饪一批次时都会执行以下步骤：

随机舀取（探索）： 想象厨师从仓库里随机舀起一桶 100 种食材。这确保了仓库中的每一种食材都有公平的机会进入这个桶中，即使是那些平淡无奇的食材也不例外。
顶尖品尝（利用）： 从这 100 种食材中，厨师会品尝所有食材，并仅挑选出其中最“浓郁”或“信息量最大”的 60 种（在机器学习术语中，即那些具有最高误差或“损失”的食材）。
烹饪： 厨师仅使用这 60 种食材进行烹饪。
更新： 厨师根据这 60 种食材更新其食谱，但至关重要的是，他们下次只会重新品尝这特定的 60 种。桶中剩下的 40 种食材则保留它们之前被品尝过的“记忆”。

为什么这意义重大？

该论文声称 OrderDP 解决了其他方法面临的三个主要难题：

1. 没有“虚假”的味道（无偏训练）
其他方法通常试图通过数学手段“重新缩放”所保留食材的味道来修正其偏差。这就像是在极少数食材中加入大量的盐，以此来假装你品尝了整锅汤。这往往会出错。
OrderDP 不需要任何伪造。因为它是从随机舀取开始的，数学证明了这 60 种食材的“平均风味”是整个仓库的一个完全诚实的代表。论文称之为“代理损失（surrogate loss）”，这只是一个高级说法，意指“一个能引导出相同结果的新的、公平的目标”。

2. 没有“颤抖的手”（稳定性）
如果你观察论文中的图表，其他方法（如 InfoBatch）就像是一个在烹饪时手部不停颤抖的厨师——味道会剧烈跳动。OrderDP 则非常平稳。因为它不依赖极端的数学技巧来修复偏差，所以训练过程非常平滑且稳定，即使你丢弃了 70% 的数据也是如此。

3. “无损”的承诺
这里的“无损”意味着最终的菜肴味道与你品尝了每一种食材后的味道完全一致，误差极小（例如 0.1%）。

证明： 作者进行了数学推导（收敛性和泛化分析），证明了 OrderDP 始终能找到最佳食谱，就像全量法一样，只是速度更快。
结果： 他们在标准的“品尝菜单”（数据集如 CIFAR-10、CIFAR-100 和 ImageNet）上进行了测试。
- 在 ImageNet（一个巨大的数据集）上，OrderDP 在保持准确率与全量法完全一致的同时，将烹饪时间缩短了 40%。
- 它击败了所有其他的“智能品尝”方法，包括目前的顶尖水平（state-of-the-art）。

总结

OrderDP 是一个“即插即用”的工具。你不需要改变你的厨房（模型架构），也不需要购买新设备。你只需要更换这种新的食材选择方式。

旧方法： 挑选“最好”的食材，猜测如何针对缺失的食材进行调整，然后听天由命。
OrderDP： 随机抓取一批，挑选出顶尖的部分，并信任数学证明——即这是一种对整体的公平代表。

论文结论指出，这种方法稳健、具有理论保证且在实践中更快，是任何想要在不耗尽计算预算的情况下训练 AI 模型的人士的可靠工具。

技术摘要：OrderDP —— 一个具有理论保证的无损动态数据剪枝框架

1. 问题陈述

数据剪枝（Data Pruning, DP）旨在通过有选择地移除信息量较低的样本，在保持近乎无损的模型性能的同时降低训练成本。然而，现有的动态剪枝策略面临两个关键局限性：

梯度估计偏差： 选择高信息量样本（例如基于损失值）的方法会引入相对于全数据集训练的梯度估计偏差。尽管一些方法试图通过重缩放（如 InfoBatch）来纠正这一点，但在极端剪枝率下，它们仍可能受到经验损失与期望损失之间差异的影响，导致尺度和方向上的偏差。
训练不稳定： 动态剪枝通常会导致梯度范数剧烈波动和测试准确率起伏。论文观察到，虽然在全数据集训练中梯度范数与性能强相关，但动态方法破坏了这种关系，导致优化动力学变得不规则且稳定性降低。

核心挑战在于设计一个既能确保无偏梯度估计、稳定收敛，又能实现对剪枝率精确控制的剪枝框架，且无需复杂的架构变更或退火调度。

2. 方法论：OrderDP

作者提出了 OrderDP（有序数据剪枝），这是一种受基于顺序统计量（order statistics）的随机优化启发而设计的即插即用动态框架。该方法将自适应样本选择集成到标准的随机梯度下降（SGD）流水线中。

核心机制

在每个迭代步 $t$ ：

探索（均匀采样）： 从全数据集 $D$ 中均匀随机抽取一个大小为 $s$ 的候选批次 $S_t$ 。这确保了每个样本都有被考虑的非零概率，从而保持多样性。
利用（基于排序的选择）： 根据得分值 $H_t(\theta_t, z_i)$ 对 $S_t$ 中的样本进行排序。OrderDP 使用瞬时损失 $L_i(\theta_t, z_i)$ 作为得分。选取得分最高的前 $q$ 个样本组成子集 $Q_t$ 。
更新： 使用在 $Q_t$ 上计算的次梯度更新模型参数。
得分刷新： 仅更新保留样本 $Q_t$ 的得分（损失）；其他样本保留其之前的得分，以避免全数据集的重新计算。

理论基础

OrderDP 被形式化为一个最小化代理损失 $L_q(\theta)$ 的优化算法，其中 $L_q(\theta)$ 定义为：
$L_q(\theta) := \frac{1}{q} \sum_{j=1}^n \gamma_j L^{(j)}(\theta)$
这里 $L^{(j)}$ 是第 $j$ 个排序后的单样本损失， $\gamma_j$ 是由两阶段采样过程（先进行大小为 $s$ 的均匀采样，再选择前 $q$ 个）的组合概率导出的权重。

其关键理论特性包括：

无偏性： OrderDP 产生的梯度估计器 $\tilde{g}_t$ 是代理损失 $L_q(\theta)$ 的无偏估计器，即 $E[\tilde{g}_t] \in \partial L_q(\theta_t)$ 。这与产生有偏估计器的原始经验损失方法形成对比。
收敛性： 在标准的凸性和 Lipschitz 假设下，OrderDP 在代理损失上实现了标准的 $O(1/\sqrt{T})$ 级 mini-batch SGD 收敛速率。
泛化性： 泛化误差由消失的优化项和有界的偏差项组成。偏差项取决于采样权重 $\{\gamma_j/q\}$ 与均匀分布之间的偏差。随着剪枝率降低（即 $q \to s$ ），该偏差趋于零，从而恢复标准 SGD 的行为。

3. 核心贡献

理论保证的无偏性： 不同于依赖启发式重缩放的现有动态方法，OrderDP 为一个定义良好的代理损失提供了严谨的无偏梯度估计理论保证。
精确的剪枝控制： 该框架通过参数 $s$ （探索规模）和 $q$ （利用规模）实现对剪枝率的精确控制，避免了基于阈值方法的波动问题。
稳定性与效率： 通过消除对退火的需求并保持稳定的梯度范数，OrderDP 比基准方法实现了更快的运行速度和更低的 GPU 时数，同时将训练成本降低了 40% 以上。
即插即用设计： 该方法不需要架构变更或辅助近似，使其能够轻松集成到现有的训练流水线中。

4. 实验结果

作者在 CIFAR-10、CIFAR-100 和 ImageNet-1K 上使用 ResNet-18 和 ResNet-50 骨干网络对 OrderDP 进行了评估。

准确率： 在各种剪枝率下，OrderDP 的准确率始终能达到或超过全数据集训练以及最先进的基准方法（包括 InfoBatch、UCB 和 $\epsilon$ $ϵ$ -greedy）。
- 在使用 ResNet-18 的 CIFAR-100 上，OrderDP 在 30% 剪枝时保持了全数据准确率，并且在 50% 和 70% 剪枝时，其准确率下降幅度比所有其他方法都要小。
- 在 ImageNet-1K 上，OrderDP 在 40% 剪枝时保留了全量准确率，并在 60% 剪枝时仅下降了 0.4%，表现优于在极端比例下表现挣扎的 InfoBatch。
效率： OrderDP 实现了最快的训练时间和最低的 GPU 时数。在 ImageNet-1K 上，它在保持准确率的同时，减少了约 40% 的总计算量。
鲁棒性： 该方法在不同架构（ResNet、Swin-Tiny、ViT-Base）和优化器（SGD、AdamW、LARS、LAMB）下均表现出鲁棒性。它还展现了卓越的稳定性，与通常需要后期退火来稳定训练的 InfoBatch 相比，OrderDP 具有更平滑的收敛曲线和更低的梯度方差。

5. 意义与主张

论文声称，OrderDP 通过提供一个既有理论完备性又具实证有效性的框架，解决了理解“近乎无损”剪枝时存在的根本性不完整问题。

理论严谨性： 该工作确立了只要将过程建模为最小化具有无偏梯度的特定代理损失，就可以将剪枝推向极端状态而不牺牲收敛保证。
实际应用价值： OrderDP 是一个稳健且易于适配的数据高效学习工具，为从业者提供了一个“甜点区（sweet spot）”，使他们能够在不损害模型性能的前提下，显著降低计算预算（节省高达 40-45%）。
稳定性： 通过解决现有动态策略中固有的训练不稳定和梯度偏差问题，OrderDP 即使在对准确率要求极高的资源受限场景下，也能实现可靠的加速。

作者强调，他们的方法并非发明了新的应用场景，而是提供了一种原则性的、感知损失的剪枝机制，在效率、稳定性和理论保证方面对现有策略进行了改进。