Abstract
Deleting data from a trained machine learning (ML) model is a critical task in many applications. We propose a new approximate deletion method for linear and logistic models whose computational cost is linear in the feature dimension d and independent of the number of training data n. This is a significant gain over all existing methods, which all have superlinear time dependence on the dimension. We also develop a new feature-injection test to evaluate the thoroughness of data deletion from ML models.
Summary
This paper introduces the Projective Residual Update (PRU), an approximate data deletion method that achieves O(k²d) computational cost — linear in dimension d and independent of dataset size n. This is a significant improvement over Newton’s method (O(kd²)) and influence functions (O(d²)), which have superlinear dependence on dimension.
The key idea is to compute the projection of the exact parameter update (θ^{\k} - θ^{full}) onto the subspace spanned by the deleted data points {x₁, …, x_k}. This projection captures the most improvement possible for any gradient-based update in that subspace. The method leverages “synthetic data” — computing leave-k-out predictions ŷ_i^{\k} without explicitly computing the LKO model, using a generalization of the hat matrix from statistics.
Key Contributions
- PRU algorithm with O(k²d) cost, linear in d and independent of n
- Optimality proof: PRU achieves the maximum improvement in the span of deleted points among all gradient-based updates (Corollary 3)
- Feature Injection Test (FIT): new evaluation metric measuring removal of sensitive features
- Extension to logistic regression via iteratively reweighted least squares
- Theoretical analysis of outlier deletion scenarios
Methodology
The PRU algorithm: (1) Compute leave-k-out predictions ŷ’₁,…,ŷ’_k using the hat matrix H = X(X^TX + λI)⁻¹X^T, (2) Compute S⁻¹ = PseudoInverse(Σ x_i x_i^T), (3) Compute ∇L = Σ(θ^{full^T}x_i - ŷ’_i)x_i, (4) Return θ^{full} - FastMult(S⁻¹, ∇L). For logistic regression, the same approach applies through an IRLS reformulation.
Key Findings
- PRU is 3000x+ faster than retraining for d=3000, k=1
- PRU outperforms influence method on FIT for larger group sizes and sparse data
- Influence method performs better on L² distance for typical (non-outlier) deletions with small k
- PRU is more numerically stable than influence functions
- FIT reveals that L² distance alone is insufficient for evaluating deletion quality — a method can have small L² but fail to remove sensitive features
Important References
- Certified Data Removal from Machine Learning Models — Guo et al. (2020), Newton-step certified removal
- Understanding Black-box Predictions via Influence Functions — Koh & Liang (2017), influence function approach
- Towards Making Systems Forget with Machine Unlearning — Cao & Yang (2015), SQ-based unlearning