영향 함수를 위한 랜덤 투영의 통일된 이론

A Unified Theory of Random Projection for Influence Functions

영향 함수 및 관련 데이터 귀속 점수는 $g^{ op}F^{-1}g^{ angle}$의 형태를 가지며, 여기서 $F geq 0$는 곡률 연산자입니다. 현대적인 과매개변수 모델에서 $F mathbb{R}^{d imes d}$를 구성하거나 역전시키는 것은 어렵기 때문에, 랜덤 투영을 사용하여 스케치 $P mathbb{R}^{m imes d}$를 통해 확장 가능한 영향 계산을 수행하는 것이 일반적입니다. 이러한 방식은 일반적으로 Johnson-Lindenstrauss (JL) Lemma를 통해 정당화되며, 이는 고정된 데이터 세트에 대해 유클리드 기하학적 특성을 근사적으로 유지하는 것을 보장합니다. 그러나 JL은 스케치가 역전산에 어떻게 영향을 미치는지에 대한 설명을 제공하지 않습니다. 또한, 정규화된 회귀(ridge regularization) 및 구조화된 곡률 근사(structured curvature approximations)와 같은 널리 사용되는 다른 기술과의 상호 작용을 설명하는 기존 이론은 없습니다. 본 연구에서는 투영이 영향 함수를 증명적으로 보존하는 조건을 특성화하는 통일된 이론을 개발했습니다. $g, g^{ angle} text{range}(F)$에 속할 때, 다음을 보여줍니다. 1) 정규화되지 않은 투영: 정확한 보존은 $P$가 $ ext{range}(F)$에서 단사 함수일 때 성립하며, 이는 $m geq ext{rank}(F)$를 필요로 합니다. 2) 정규화된 투영: 정규화된 회귀는 스케칭의 제약 조건을 근본적으로 변경하며, 근사 보장 범위는 정규화 규모에서의 $F$의 효과적인 차원에 의해 결정됩니다. 3) 분해된 영향: Kronecker 곱으로 표현되는 곡률 $F=A E$의 경우, 분리된 스케치 $P=P_A P_E$에 대해서도 보장이 유지됩니다. 이는 이러한 스케치가 행렬 간 상관 관계를 보이는 점을 고려하면 i.i.d. 가정에 위배되지만, 여전히 유효하다는 것을 의미합니다. 이 범위를 벗어나, 범위 밖의 테스트 기울기를 분석하고, 테스트 기울기의 일부가 $ ker(F)$에 속할 때 발생하는 누수(leakage) 항을 정량화합니다. 이를 통해 일반적인 테스트 지점에 대한 영향 쿼리에 대한 보장을 제공합니다. 전반적으로, 본 연구는 투영이 영향 함수를 증명적으로 보존하는 조건을 특성화하는 새로운 이론을 개발하고, 실제 환경에서 스케치 크기를 선택하기 위한 합리적인 지침을 제공합니다.

Influence functions and related data attribution scores take the form of $g^{\top}F^{-1}g^{\prime}$, where $F\succeq 0$ is a curvature operator. In modern overparametrized models, forming or inverting $F\in\mathbb{R}^{d\times d}$ is prohibitive, motivating scalable influence computation via random projection with a sketch $P \in \mathbb{R}^{m\times 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,g^{\prime}\in\text{range}(F)$, we show that: 1) Unregularized projection: exact preservation holds iff $P$ is injective on $\text{range}(F)$, which necessitates $m\geq \text{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=A\otimes E$, the guarantees continue to hold for decoupled sketches $P=P_A\otimes P_E$, 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.