提出无需强凸假设的牛顿步与影响函数误差分析，解释为何牛顿步更准。
On the Accuracy of Newton Step and Influence Function Data Attributions
- 不依赖全局强凸性，建立新分析框架
- 证明牛顿步误差约与kd/n²成正比，影响函数更复杂
- 揭示牛顿步在多数情况下比影响函数更准确
数据归因旨在通过估计移除某些训练点后模型预测的变化来解释模型输出，广泛应用于可解释性、责任分配、遗忘学习和隐私保护。尽管在逻辑回归这类简单情形下，现有对影响函数（IF）和单次牛顿步（NS）等主流方法的数学分析仍存在两大局限：一是依赖全局强凸性假设，实践中常不成立；二是所得界随参数量d和移除样本数k的增加而急剧恶化。因此，这些分析不足以回答诸如“各方法误差的渐近尺度如何”或“对给定数据集哪个方法更准确”等根本问题。本文针对凸学习问题，首次提出不假设全局强凸性的NS与IF分析，并首次解释了[KATL19]与[RH25a]观察到的NS通常比IF更准确的现象。我们证明，在足够良好的逻辑回归中，边界在多对数因子内渐近紧致，给出了平均情况样本移除下的误差尺度： $$ \mathbb{E}_{T \subseteq [n],\, |T| = k} \bigl[ \|\hatθ_T - \hatθ_T^{\mathrm{NS}}\|_2 \bigr] = \widetildeΘ\!\left(\frac{k d}{n^2}\right), \qquad \mathbb{E}_{T \subseteq [n],\, |T| = k} \bigl[ \|\hatθ_T^{\mathrm{NS}} - \hatθ_T^{\mathrm{IF}}\|_2 \bigr] = \widetildeΘ\!\left( \frac{(k + d)\sqrt{k d}}{n^2} \right). $$
原文摘要 · Abstract (English)
Data attribution aims to explain model predictions by estimating how they would change if certain training points were removed, and is used in a wide range of applications, from interpretability and credit assignment to unlearning and privacy. Even in the relatively simple case of logistic regressions, existing mathematical analyses of leading data attribution methods such as Influence Functions (IF) and single Newton Step (NS) remain limited in two key ways. First, they rely on global strong convexity assumptions which are often not satisfied in practice. Second, the resulting bounds scale very poorly with the number of parameters ($d$) and the number of samples removed ($k$). As a result, these analyses are not tight enough to answer fundamental questions such as "what is the asymptotic scaling of the errors of each method?" or "which of these methods is more accurate for a given dataset?" In this paper, we introduce a new analysis of the NS and IF data attribution methods for convex learning problems. To the best of our knowledge, this is the first analysis of these questions that does not assume global strong convexity and also the first explanation of [KATL19] and [RH25a]'s observation that NS data attribution is often more accurate than IF. We prove that for sufficiently well-behaved logistic regressions, our bounds are asymptotically tight up to poly-logarithmic factors, yielding scaling laws for the errors in the average-case sample removals. \[ \mathbb{E}_{T \subseteq [n],\, |T| = k} \bigl[ \|\hatθ_T - \hatθ_T^{\mathrm{NS}}\|_2 \bigr] = \widetildeΘ\!\left(\frac{k d}{n^2}\right), \qquad \mathbb{E}_{T \subseteq [n],\, |T| = k} \bigl[ \|\hatθ_T^{\mathrm{NS}} - \hatθ_T^{\mathrm{IF}}\|_2 \bigr] = \widetildeΘ\!\left( \frac{(k + d)\sqrt{k d}}{n^2} \right). \]
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。