A Unified Theory of Random Projection for Influence Functions

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.