pith. sign in

arxiv: 2512.12572 · v2 · pith:EFBBYZTLnew · submitted 2025-12-14 · 💻 cs.LG · stat.ML

On the Accuracy of Newton Step and Influence Function Data Attributions

Ittai Rubinstein , Samuel B. Hopkins This is my paper

Pith reviewed 2026-05-21 17:42 UTC · model grok-4.3

classification 💻 cs.LG stat.ML
keywords data attributioninfluence functionsNewton steplogistic regressionscaling lawserror analysisconvex learningmodel interpretability
0
0 comments X

The pith

Newton step data attributions are asymptotically more accurate than influence functions for logistic regression models.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a new analysis of Newton step and influence function data attribution methods for convex learning problems without relying on global strong convexity assumptions. It proves that for sufficiently well-behaved logistic regressions the error bounds are asymptotically tight up to poly-log factors, producing scaling laws for the expected difference between the true retrained parameters and the approximations when removing k samples. A sympathetic reader would care because these laws clarify the relative accuracy of the two methods and their dependence on the number of parameters d, samples removed k, and training set size n, which is useful for applications like model interpretability and data unlearning.

Core claim

The central claim is that a new analysis without global strong convexity yields asymptotically tight bounds for Newton step and influence function data attributions in logistic regression, specifically that the expected L2 error of the Newton step approximation is tilde-Theta of kd over n squared and the difference between Newton step and influence function is tilde-Theta of (k plus d) times square root of kd over n squared, for average-case removals of k samples.

What carries the argument

A new analysis technique for the differences in learned parameters after removing subsets of training data, which operates under milder well-behaved conditions on the logistic loss to achieve tight asymptotic scaling laws.

Load-bearing premise

The logistic regression must satisfy sufficiently well-behaved conditions milder than global strong convexity.

What would settle it

Measuring the average L2 norm differences in parameter estimates for logistic regression models trained on datasets with varying sizes n and removal counts k, and checking whether the observed errors follow the claimed scaling with n, k, and d.

Figures

Figures reproduced from arXiv: 2512.12572 by Ittai Rubinstein, Samuel B. Hopkins.

Figure 1
Figure 1. Figure 1: Diagram of proof of Lemma 3.2. 3.2 θˆ T ∈ B The second portion of our proof will be to show that θˆ T lies within the region B around the first Newton step. We do this using ideas from self-concordant analysis [Bac10, HM24]. Lemma 3.2. θˆ T ∈ B Proof of Lemma 3.2. Assume for contradiction that θˆ T ∈ B / . Let θB denote the intersection between the line segment from θˆ T to θˆNS T and ∂B, and denote d def … view at source ↗
Figure 2
Figure 2. Figure 2: Diagram of proof of Lemma 3.3. Proof of Lemma 3.3. Let d def = θˆ T − θˆNS T and consider the segment θ(t) def = θˆNS T + td for t ∈ [0, 1]. Step 1: Bounded gradient at θˆNS T . By Lemma 3.1 and the dual pairing between ∥·∥Σ and ∥·∥Σ−1 , ⟨d, gθˆNS T ⟩ ≤ ∥d∥Σ [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
read the original abstract

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{\theta}_T - \hat{\theta}_T^{\mathrm{NS}}\|_2 \bigr] = \widetilde{\Theta}\!\left(\frac{k d}{n^2}\right), \qquad \mathbb{E}_{T \subseteq [n],\, |T| = k} \bigl[ \|\hat{\theta}_T^{\mathrm{NS}} - \hat{\theta}_T^{\mathrm{IF}}\|_2 \bigr] = \widetilde{\Theta}\!\left( \frac{(k + d)\sqrt{k d}}{n^2} \right). \]

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript introduces a new analysis of Newton Step (NS) and Influence Function (IF) data attribution methods for convex learning problems, with a focus on logistic regression. It avoids global strong convexity assumptions and proves asymptotic tightness (up to poly-log factors) of the error bounds under 'sufficiently well-behaved' conditions, yielding explicit scaling laws for the average-case effect of removing k samples: E[||θ̂_T - θ̂_T^NS||_2] = ~Θ(kd/n²) and E[||θ̂_T^NS - θ̂_T^IF||_2] = ~Θ((k+d)√(kd)/n²).

Significance. If the results hold, the work is significant for providing the first analysis of NS and IF attributions that does not rely on global strong convexity and for deriving matching upper/lower bounds that explain why NS is often more accurate than IF in practice. The explicit scaling laws under milder local conditions advance understanding of data attribution accuracy in convex models.

major comments (2)
  1. [Abstract and main theorem] Abstract and main theorem (presumably §3 or §4): The central claim of asymptotic tightness for the stated scaling laws relies on 'sufficiently well-behaved' logistic regression conditions that enable the new local analysis. These conditions (e.g., any local eigenvalue bounds, smoothness parameters, or data-distribution assumptions) must be stated explicitly in the theorem, as their current vagueness prevents verification that they are strictly milder than global strong convexity or that the matching bounds up to polylog factors follow directly from them.
  2. [§5] §5 (or the section deriving the IF-NS difference): The bound E[||θ̂_T^NS - θ̂_T^IF||_2] = ~Θ((k+d)√(kd)/n²) is load-bearing for the claim that NS is more accurate; the derivation should include a direct comparison showing when this term is o( the NS error term kd/n² ) under the same well-behaved conditions.
minor comments (1)
  1. [Abstract] Notation for the expectation E_{T ⊆ [n], |T|=k} should be clarified to specify whether it is uniform over subsets or weighted by some distribution on removals.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive feedback, which highlights important aspects of clarity in our theoretical claims. We address each major comment below and will incorporate revisions to strengthen the manuscript.

read point-by-point responses

  1. Referee: [Abstract and main theorem] Abstract and main theorem (presumably §3 or §4): The central claim of asymptotic tightness for the stated scaling laws relies on 'sufficiently well-behaved' logistic regression conditions that enable the new local analysis. These conditions (e.g., any local eigenvalue bounds, smoothness parameters, or data-distribution assumptions) must be stated explicitly in the theorem, as their current vagueness prevents verification that they are strictly milder than global strong convexity or that the matching bounds up to polylog factors follow directly from them.

    Authors: We agree that the conditions require explicit statement for full rigor and to facilitate verification. In the revised manuscript, we will restate the main theorem with precise definitions of the 'sufficiently well-behaved' conditions, including local lower and upper bounds on the Hessian eigenvalues (in a neighborhood of the optimum) and local smoothness parameters on the loss. These local conditions are strictly milder than global strong convexity, as they permit the Hessian to vary or become singular far from the optimum. We will also include a brief derivation sketch showing how the matching upper and lower bounds (up to poly-log factors) follow directly from these assumptions via the local analysis in §3. revision: yes

  2. Referee: [§5] §5 (or the section deriving the IF-NS difference): The bound E[||θ̂_T^NS - θ̂_T^IF||_2] = ~Θ((k+d)√(kd)/n²) is load-bearing for the claim that NS is more accurate; the derivation should include a direct comparison showing when this term is o( the NS error term kd/n² ) under the same well-behaved conditions.

    Authors: We thank the referee for this suggestion, which clarifies the practical implications. Under the same well-behaved conditions, the NS-IF difference is asymptotically smaller than the NS error whenever k = o(d), since (k + d)√(kd) = o(kd) in that regime. We will add a direct comparison paragraph in §5 that derives this o(·) relation explicitly from the local eigenvalue bounds, and we will state the precise regime (e.g., k ≪ d) under which the difference vanishes relative to the leading NS term, thereby reinforcing why NS is typically more accurate. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new analysis derives scaling laws from first-principles bounds on local properties.

full rationale

The paper presents a new analysis of Newton Step and Influence Function methods for convex problems that avoids global strong convexity assumptions. The asymptotic tightness claims and scaling laws E[||θ̂_T - θ̂_T^NS||_2] = ~Θ(kd/n²) and E[||θ̂_T^NS - θ̂_T^IF||_2] = ~Θ((k+d)√(kd)/n²) are obtained via direct bounding arguments under 'sufficiently well-behaved' local conditions rather than by fitting parameters to data or reducing to prior self-citations. Self-citations to [KATL19] and [RH25a] explain empirical observations but are not load-bearing for the new bounds, which are derived independently. No step equates a prediction to its input by construction or imports uniqueness via self-citation chains.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on convexity of the learning problem and the introduced 'sufficiently well-behaved' condition for logistic regression to achieve tightness without global strong convexity.

axioms (2)
  • domain assumption The learning problem is convex
    Standard for logistic regression analysis and required to apply the attribution methods.
  • ad hoc to paper The model satisfies sufficiently well-behaved conditions allowing local analysis
    Key premise introduced to replace global strong convexity and enable the tight bounds.

pith-pipeline@v0.9.0 · 5929 in / 1417 out tokens · 85623 ms · 2026-05-21T17:42:14.244177+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 2 internal anchors

  1. [1]

    Lecture 5: Sub-exponential random variables and orlicz norms

    [APAR19] scribe Aleksandr Podkopaev and lecturer Alessandro Rinaldo. Lecture 5: Sub-exponential random variables and orlicz norms. Scribed lecture notes 36-710 / 36-709, Spring 2019, Carnegie Mellon University, Department of Statistics & Data Science, Pittsburgh, PA, USA, February

    work page 2019

  2. [2]

    An automatic finite-sample robustness metric: when can dropping a little data make a big difference?arXiv preprint arXiv:2011.14999,

    11 [BGM20] Tamara Broderick, Ryan Giordano, and Rachael Meager. An automatic finite-sample robustness metric: when can dropping a little data make a big difference?arXiv preprint arXiv:2011.14999,

    work page arXiv 2011

  3. [3]

    Insufficient statistics perturbation: Stable estimators for private least squares.arXiv preprint arXiv:2404.15409,

    [BHH+24] Gavin Brown, Jonathan Hayase, Samuel Hopkins, Weihao Kong, Xiyang Liu, Sewoong Oh, Juan C Perdomo, and Adam Smith. Insufficient statistics perturbation: Stable estimators for private least squares.arXiv preprint arXiv:2404.15409,

    work page arXiv

  4. [4]

    [BNL+22] Juhan Bae, Nathan Ng, Alston Lo, Marzyeh Ghassemi, and Roger B. Grosse. If influence functions are the answer, then what is the question? In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, Neur...

    work page 2022

  5. [5]

    Influence functions in deep learning are fragile

    [BPF21] Samyadeep Basu, Phillip Pope, and Soheil Feizi. Influence functions in deep learning are fragile. In9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7,

    work page 2021

  6. [6]

    What is your data worth to gpt? llm-scale data valuation with influence functions.arXiv preprint arXiv:2405.13954,

    [CAB+24] Sang Keun Choe, Hwijeen Ahn, Juhan Bae, Kewen Zhao, Minsoo Kang, Youngseog Chung, Adithya Pratapa, Willie Neiswanger, Emma Strubell, Teruko Mitamura, et al. What is your data worth to gpt? llm-scale data valuation with influence functions.arXiv preprint arXiv:2405.13954,

    work page arXiv

  7. [7]

    Optimizing ml training with metagradient descent.arXiv preprint arXiv:2503.13751,

    [EIC+25] Logan Engstrom, Andrew Ilyas, Benjamin Chen, Axel Feldmann, William Moses, and Aleksander Madry. Optimizing ml training with metagradient descent.arXiv preprint arXiv:2503.13751,

    work page arXiv

  8. [8]

    Studying large language model generalization with influence functions.arXiv preprint arXiv:2308.03296,

    [GBA+23] Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, et al. Studying large language model generalization with influence functions.arXiv preprint arXiv:2308.03296,

    work page arXiv

  9. [9]

    Fastif: Scalable influence functions for efficient model interpretation and debugging

    [GRH+21] Han Guo, Nazneen Rajani, Peter Hase, Mohit Bansal, and Caiming Xiong. Fastif: Scalable influence functions for efficient model interpretation and debugging. InProceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10333–10350,

    work page 2021

  10. [10]

    Approxima- tions to worst-case data dropping: unmasking failure modes.arXiv preprint arXiv:2408.09008,

    [HBN+24] Jenny Y Huang, David R Burt, Tin D Nguyen, Yunyi Shen, and Tamara Broderick. Approxima- tions to worst-case data dropping: unmasking failure modes.arXiv preprint arXiv:2408.09008,

    work page arXiv

  11. [11]

    Datamodels: Understanding predictions with data and data with predictions

    [IPE+22] Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Understanding predictions with data and data with predictions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimor...

    work page 2022

  12. [12]

    A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm

    [JNG+19] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. A short note on concentration inequalities for random vectors with subgaussian norm.arXiv preprint arXiv:1902.03736,

    work page internal anchor Pith review Pith/arXiv arXiv 1902

  13. [13]

    [KATL19] Pang Wei Koh, Kai-Siang Ang, Hubert H. K. Teo, and Percy Liang. On the accuracy of influence functions for measuring group effects. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors,Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Pr...

    work page 2019

  14. [14]

    Understanding black-box predictions via influence functions

    [KL17] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Doina Precup and Yee Whye Teh, editors,Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1885–1894. PMLR,

    work page 2017

  15. [15]

    The approximate fisher influence function: Faster estimation of data influence in statistical models.arXiv preprint arXiv:2407.08169,

    [LW24] Omri Lev and Ashia C Wilson. The approximate fisher influence function: Faster estimation of data influence in statistical models.arXiv preprint arXiv:2407.08169,

    work page arXiv

  16. [16]

    Influence functions for scalable data attribution in diffusion models

    [MEB+] Bruno Kacper Mlodozeniec, Runa Eschenhagen, Juhan Bae, Alexander Immer, David Krueger, and Richard E Turner. Influence functions for scalable data attribution in diffusion models. In The Thirteenth International Conference on Learning Representations. 13 [MIE+24] Aleksander Madry, Andrew Ilyas, Logan Engstrom, Sung Min (Sam) Park, and Kristian Geor...

    work page 2024

  17. [17]

    Tutorial presented at the 41st International Conference on Machine Learning (ICML 2024), Vienna, Austria, July 22,

    work page 2024

  18. [18]

    Trak: Attributing model behavior at scale.arXiv preprint arXiv:2303.14186,

    [PGI+23] Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Madry. Trak: Attributing model behavior at scale.arXiv preprint arXiv:2303.14186,

    work page arXiv

  19. [19]

    Rescaled influence functions: Accurate data attribution in high dimension.arXiv preprint arXiv:2506.06656,

    [RH25a] Ittai Rubinstein and Samuel B Hopkins. Rescaled influence functions: Accurate data attribution in high dimension.arXiv preprint arXiv:2506.06656,

    work page arXiv

  20. [20]

    [RH25b] Ittai Rubinstein and Samuel B. Hopkins. Robustness auditing for linear regression: To sin- gularity and beyond. InProceedings of the Thirteenth International Conference on Learning Representations (ICLR 2025),

    work page 2025

  21. [21]

    A scalable estimate of the extra-sample prediction error via approximate leave-one-out.arXiv preprint arXiv:1801.10243,

    [RM18] Kamiar Rahnama Rad and Arian Maleki. A scalable estimate of the extra-sample prediction error via approximate leave-one-out.arXiv preprint arXiv:1801.10243,

    work page arXiv

  22. [22]

    Remember what you want to forget: Algorithms for machine unlearning

    [SAKS21b] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors,Advances in Neural Information Processing Systems 34: Annual Conference on Neural Informati...

    work page 2021

  23. [23]

    Suriyakumar and Ashia C

    [SW22] Vinith M. Suriyakumar and Ashia C. Wilson. Algorithms that approximate data removal: New results and limitations. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors,Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA,...

    work page 2022

  24. [24]

    Introduction to the non-asymptotic analysis of random matrices

    [Ver10] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices.arXiv preprint arXiv:1011.3027,

    work page internal anchor Pith review Pith/arXiv arXiv

  25. [25]

    Newflu- ence: Boosting model interpretability and understanding in high dimensions.arXiv preprint arXiv:2507.11895,

    [ZAK+25] Haolin Zou, Arnab Auddy, Yongchan Kwon, Kamiar Rahnama Rad, and Arian Maleki. Newflu- ence: Boosting model interpretability and understanding in high dimensions.arXiv preprint arXiv:2507.11895,

    work page arXiv