Technical Summary: Extending Kernel Trick to Influence Functions

Problem Statement

Influence functions, originally developed in robust statistics and adapted to machine learning by Koh and Liang [1], provide a method to estimate how model parameters and outputs change when training data points are perturbed or removed. This capability is critical for machine unlearning, interpretability, and privacy. However, the standard application of influence functions to large-scale deep learning models faces a significant scalability bottleneck.

The core computational challenge lies in the Inverse Hessian–Vector Product (IHVP), $H_{\theta^*}^{-1} \nabla_\theta L_{D_f}(\theta^*)$, required to approximate the change in parameters ($\theta_r^*$) after removing a forget set $D_f$. In the original formulation, the Hessian matrix $H_{\theta^*}$ scales with the square of the number of model parameters ($d_\theta$). For large models (e.g., deep neural networks), materializing and inverting this matrix is infeasible. While iterative methods like Conjugate Gradients (CG) avoid materializing the Hessian, they still rely on Hessian–Vector Products (HVPs) that scale with model size, making the process computationally expensive when $d_\theta$ is large relative to the dataset size.

Methodology

The authors propose a dual representation of influence functions that shifts the computational complexity from scaling with model size ($d_\theta$) to scaling with dataset size ($|D|$) and output dimension ($d_{out}$). This approach is grounded in the theory of linearizable models and the Neural Tangent Kernel (NTK).

1. Linearization and Reparameterization

The method assumes the model $f(\cdot, \theta)$ is "linearizable," meaning its behavior throughout training can be approximated by its linearization around a reference point $\theta'$ (typically initialization). The authors define a linearized model $f^{lin}$ and a corresponding regularized empirical risk $\hat{L}_D(\theta)$.

Key to the derivation is Proposition 3.1, which establishes that for any subset of data, the difference between the optimal parameters of the linearized model and the full dataset lies in a specific linear subspace of $\mathbb{R}^{d_\theta}$:
$$\hat{\theta}_r^* - \hat{\theta}^* = \nabla_\theta f(X, \theta')^\top \Delta \alpha_r^*$$
where $\Delta \alpha_r^* \in \mathbb{R}^{d_{out}|D|}$.

This observation allows the authors to reparameterize the optimization problem. Instead of optimizing over the high-dimensional parameter space $\theta$, they optimize over the dual variable $\Delta \alpha$. The constrained problem in $\theta$ is transformed into an unconstrained problem in $\Delta \alpha$ space:
$$\tilde{L}_D(\Delta \alpha) := \frac{1}{|D|} \sum_{(x,y) \in D} \left( \ell(g^{lin}(x, \Delta \alpha), y) + \frac{\lambda}{2} \|\phi(\Delta \alpha) - \theta'\|_2^2 \right)$$
where $g^{lin}$ involves the empirical NTK, $K(\cdot, \cdot) = \nabla_\theta f(\cdot, \theta') \nabla_\theta f(\cdot, \theta')^\top$.

2. Dual Influence Functions

In the $\Delta \alpha$ space, the influence of removing data points is approximated by solving a linear system involving the Hessian of the dual risk, $H_{\Delta \alpha^*}$. Crucially, this Hessian scales with $d_{out}|D| \times d_{out}|D|$ rather than $d_\theta \times d_\theta$.

The approximation for the change in the dual variable is:
$$\Delta \alpha_r^* \approx \frac{|D_f|}{|D|} H_{\Delta \alpha^*}^{-1} \nabla_{\Delta \alpha} \tilde{L}_{D_f}(0)$$
The authors show that this system can be solved efficiently. Specifically, if the forget set $D_f$ is large, the dimension of the linear system to be solved actually decreases because the known components of $\Delta \alpha_r^*$ corresponding to $D_f$ can be isolated.

3. Estimating Changes

Once $\Delta \alpha_r^*$ is obtained, changes in model outputs and loss for test points can be estimated using the NTK:

• Output Change: $f^{lin}(x_t, \hat{\theta}_r^*) - f^{lin}(x_t, \hat{\theta}^*) \approx K(x_t, X) \Delta \alpha_r^*$
• Loss Change: Estimated via the gradient of the dual loss with respect to $\Delta \alpha$.

This formulation allows the computation of influence for models with infinitely many parameters, provided the NTK admits an analytical form.

Key Contributions

1. Dual Representation: The paper introduces a dual formulation of influence functions where computational complexity depends on the dataset size ($|D|$) and output dimension ($d_{out}$) rather than the model parameter count ($d_\theta$).
2. Efficiency for Large Models: The method provides an efficient alternative to original influence functions when $d_\theta \gg d_{out}|D|$. It avoids the need to compute HVPs with respect to the massive parameter space.
3. Infinite Width Applicability: The framework extends influence analysis to infinitely wide neural networks by leveraging the analytical NTK, allowing for the estimation of parameter and output changes in the limit of infinite parameters.
4. Computational Shortcut: The authors identify that in the dual space, the linear system size decreases as the size of the forget set ($|D_f|$) increases, offering a counter-intuitive efficiency gain for large-scale unlearning tasks.

Experimental Results

The authors validate their method on linearized versions of Fully Connected Neural Networks (FCNN) and Convolutional Neural Networks (CNN) trained on MNIST and CIFAR-10 subsets.

• Runtime: The $\Delta \alpha$-space method consistently outperforms the original $\theta$-space method in both "cold-start" (first execution) and "warm-start" (repeated execution) scenarios. The performance gap widens as the model size increases relative to the dataset.
• Accuracy: The unlearning performance (measured by the relative $\ell_2$ distance between unlearned and retrained parameters, and accuracy on the forget set) is comparable to the original method.
• Effect of Regularization ($\lambda$): Experiments on nonlinear models show that larger values of the regularization constant $\lambda$ make the training dynamics of nonlinear models more closely resemble their linearizations. This improves the reliability of the dual representation for nonlinear models, though it comes at the cost of lower test accuracy.
• Infinitely Wide Networks: The method successfully estimates output and loss changes for infinitely wide FCNNs and CNNs, with estimates closely matching actual changes computed via Kernel Gradient Descent.

Significance and Claims

The paper claims that the dual representation offers a scalable solution for machine unlearning and influence analysis in settings where the model size is prohibitively large for traditional parameter-space methods.

• Scalability: It enables the estimation of influence for models where evaluating the original influence functions in parameter space is infeasible.
• Theoretical Extension: It provides a theoretical bridge to analyze influence in the infinite-width limit of neural networks.
• Limitations: The authors explicitly state that the method is limited to linearizable models. While large regularization ($\lambda$) can approximate non-linear models as linearizable, this degrades model performance. Additionally, the method requires materializing or implicitly operating on the NTK matrix, which scales with the product of dataset size and output dimension, potentially becoming a bottleneck for very large datasets with many classes.

The work does not claim to solve the unlearning problem for all deep learning models but rather provides a specialized, efficient tool for scenarios where the dataset is small relative to the model capacity or where the model can be effectively treated as linear.