# A Unified Theory of Random Projection for Influence Functions

arXiv: https://arxiv.org/abs/2602.10449 · HTML: https://mlsanity.com/paper/2602.10449/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 36 references that are in the map.
- First posted on arXiv 11 Feb 2026.

## Builds on (most cited first, 23 of 23)

- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Studying Large Language Model Generalization with Influence Functions](https://mlsanity.com/paper/2308.03296/) (2023)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [TRAK: Attributing Model Behavior at Scale](https://mlsanity.com/paper/2303.14186/) (2023)
- [Fast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis](https://mlsanity.com/paper/1806.03884/) (2018)
- [If Influence Functions are the Answer, Then What is the Question?](https://mlsanity.com/paper/2209.05364/) (2022)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Scaling Up Influence Functions](https://mlsanity.com/paper/2112.03052/) (2021)
- [DataInf: Efficiently Estimating Data Influence in LoRA-tuned LLMs and Diffusion Models](https://mlsanity.com/paper/2310.00902/) (2023)
- [FastIF: Scalable Influence Functions for Efficient Model Interpretation and Debugging](https://mlsanity.com/paper/2012.15781/) (2020)
- [What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions](https://mlsanity.com/paper/2405.13954/) (2024)
- [Interactive Label Cleaning with Example-based Explanations](https://mlsanity.com/paper/2106.03922/) (2021)
- [Intriguing Properties of Data Attribution on Diffusion Models](https://mlsanity.com/paper/2311.00500/) (2023)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Influence Functions for Scalable Data Attribution in Diffusion Models](https://mlsanity.com/paper/2410.13850/) (2024)
- [Most Influential Subset Selection: Challenges, Promises, and Beyond](https://mlsanity.com/paper/2409.18153/) (2024)
- [textttdattri: A Library for Efficient Data Attribution](https://mlsanity.com/paper/2410.04555/) (2024)
- ["Influence Sketching": Finding Influential Samples In Large-Scale Regressions](https://mlsanity.com/paper/1611.05923/) (2016)
- [Efficient Sketches for Training Data Attribution and Studying the Loss Landscape](https://mlsanity.com/paper/2402.03994/) (2024)
- [Better Training Data Attribution via Better Inverse Hessian-Vector Products](https://mlsanity.com/paper/2507.14740/) (2025)
- [GraSS: Scalable Data Attribution with Gradient Sparsification and Sparse Projection](https://mlsanity.com/paper/2505.18976/) (2025)
- [Taming Hyperparameter Sensitivity in Data Attribution: Practical Selection Without Costly Retraining](https://mlsanity.com/paper/2505.24261/) (2025)

## Built on by (most cited first, 1 of 1)

- [Certified Approximation for Interpretable Representer Landmarks](https://mlsanity.com/paper/2609.38901/) (2026)

## Abstract (arXiv)

Influence functions and related data attribution scores take the form of gtopF-1gprime, where Fsucceq 0 is a curvature operator. In modern overparametrized models, forming or inverting F∈ℝd× d is prohibitive, motivating scalable influence computation via random projection with a sketch P ∈ ℝm× d. This practice is commonly justified via the Johnson--Lindenstrauss (JL) lemma, which ensures approximate preservation of Euclidean geometry for a fixed dataset. However, JL does not address how sketching behaves under inversion. Furthermore, there is no existing theory that explains how sketching interacts with other widely-used techniques, such as ridge regularization and structured curvature approximations. We develop a unified theory characterizing when projection provably preserves influence functions. When g,gprime∈range(F), we show that: 1) Unregularized projection: exact preservation holds iff P is injective on range(F), which necessitates m≥ rank(F); 2) Regularized projection: ridge regularization fundamentally alters the sketching barrier, with approximation guarantees governed by the effective dimension of F at the regularization scale; 3) Factorized influence: for Kronecker-factored curvatures F=Aotimes E, the guarantees continue to hold for decoupled sketches P=PAotimes PE, even though such sketches exhibit row correlations that violate i.i.d. assumptions. Beyond this range-restricted setting, we analyze out-of-range test gradients and quantify a leakage term that arises when test gradients have components in ker(F). This yields guarantees for influence queries on general test points. Overall, this work develops a novel theory that characterizes when projection provably preserves influence and provides principled guidance for choosing the sketch size in practice.