Source-linked AI summary
Deep Unlearning via Randomized Conditionally Independent Hessians
Ronak Mehta, Sourav Pal, Vikas Singh, Sathya N. Ravi
TL;DR
Repeatedly retraining models to remove requested samples can be costly, while Hessian-based approximate updates may be impractical for large models. The paper uses L-CODEC to select sample-relevant parameter subsets for approximate unlearning. It reports enabling approximate unlearning in large vision models and across vision and transformer settings.
Problem
Full retraining after deletion requests can require weeks of training and review, while Hessian-based approximate updates scale poorly for large models.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
The selection scheme reduces compute requirements for Hessian unlearning and supports approximate unlearning in large vision models.
Source: §8 · p. 8The theoretical discussion assumes minimizers satisfy Second Order Sufficiency conditions for nonconvex unlearning.
Source: §5.1 · p. 6
Abstract
from arXiv · showhide
Recent legislation has led to interest in machine unlearning, i.e., removing specific training samples from a predictive model as if they never existed in the training dataset. Unlearning may also be required due to corrupted/adversarial data or simply a user's updated privacy requirement. For models which require no training (k-NN), simply deleting the closest original sample can be effective. But this idea is inapplicable to models which learn richer representations. Recent ideas leveraging optimization-based updates scale poorly with the model dimension d, due to inverting the Hessian of the loss function. We use a variant of a new conditional independence coefficient, L-CODEC, to identify a subset of the model parameters with the most semantic overlap on an individual sample level. Our approach completely avoids the need to invert a (possibly) huge matrix. By utilizing a Markov blanket selection, we premise that L-CODEC is also suitable for deep unlearning, as well as other applications in vision. Compared to alternatives, L-CODEC makes approximate unlearning possible in settings that would otherwise be infeasible, including vision models used for face recognition, person re-identification and NLP models that may require unlearning samples identified for exclusion. Code can be found at https://github.com/vsingh-group/LCODEC-deep-unlearning/
1. Introduction
The right to be forgotten raises whether deleting data also requires updating models trained on it, while repeated full retraining can be infeasible. The paper proposes L-CODEC to identify sample-relevant parameter blocks for approximate unlearning without a full Hessian inverse.
Motivation
- Legislative efforts have pushed back against widespread collection and use of personal data, particularly for training machine-learning models.The introduction also notes that personal images have been used without consent, e.g..Source: §1 · p. 1
- The right to be forgotten raises whether deleting a person’s data also requires updating a model trained on it.The passage notes that GDPR and CCPA do not specify the extent to which data must be forgotten.Source: §1 · p. 1
- Repeated deletion requests make full retraining infeasible when production models require weeks of training and review.The paper frames the problem as updating a model to remove data without retraining.Source: §1 · p. 1
Contributions
- L-CODEC identifies a sample’s Markov blanket of parameters, enabling unlearning in deep models with hundreds of millions of parameters.The authors also demonstrate unlearning samples and entire classes in CNNs, ResNets, and transformers, including face-recognition and person re-identification models.Source: §1 · p. 1
- The proposed block-coordinate update approximates a full-network update while avoiding its costly or infeasible full Hessian inverse.The figure depicts selected parameter blocks associated with samples and identified through input perturbations.Source: Figure 1 · p. 2
2. Problem Setup for Unlearning
Approximate unlearning seeks an updated model close to one trained without the requested sample. The paper motivates selecting only sample-relevant parameters because Hessian-based updates can be impractical, and grounds its parameter-block approach in an assumption about subsets of samples and parameters.
Unlearning objective
- The framework seeks an updated hypothesis close or equivalent to one learned from the training set with the requested sample removed.An unlearning scheme takes a sample used to train the original model as input.Source: §2 · p. 2
- An unlearning update is intended to make the model (ϵ, δ)-forgetting for a given deletion request.For an empirical risk minimizer, the task is to identify the update term g(z′) that achieves this property.Source: §2 · p. 2
Rationale for approximate schemes
- Hessian-based updates can be impractical when the inverse needed for the update cannot be computed.The paper motivates alternatives that avoid calculating the full Hessian inverse.Source: §2 · p. 2
Parameter-selection rationale
- The Hessian inverse weights gradients according to second-order differences, and parameters with small gradients or little information may be unnecessary.The paper also interprets the inverse Hessian as a conditional covariance matrix [15,17].Source: §2 · p. 2
- The paper assumes that each subset of training samples has a subset of trained parameters associated with it.This assumption motivates selecting a parameter subset for unlearning.Source: §2 · p. 3
3. Related Work
Prior machine-unlearning work includes exact methods for selected classical models and approximate updates for linear models and some network settings. Other approaches offer absolute-privacy guarantees but require pipeline changes and do not scale satisfactorily to large deep-learning settings.
Prior unlearning methods
- Exact unlearning has been studied for SVMs, Naïve Bayes classifiers, and k-means [14], but these methods do not translate to stochastic models with millions of parameters.Approximate proposals include updates for linear models and last network layers [20], and full-network linearizations [16] [17].Source: §3 · p. 3
Alternative approaches
- Alternative schemes with absolute-privacy guarantees require pipeline changes such as sharding or aggregating weaker models, and scale unsatisfactorily in large deep-learning settings.The cited passage distinguishes these schemes from approaches operating under probabilistic frameworks [31].Source: §3 · p. 3
4. Randomized Markovian Block Coordinate Unlearning
The method selects a sufficient parameter subset before computing the full unlearning update, reducing the blockwise inverse problem from dimension d to a much smaller subset. It combines randomized conditional-independence estimation with incremental Markov-blanket selection.
4. Randomized Markovian Block Coordinate Unlearning
- Identifying zero entries in the unlearning update allows their coordinates to be skipped and reduces complexity from O(d^3) to O(p^3), where p ≪ d.The blockwise inverse can then omit parameters outside the sufficient update subset.Source: §4 · p. 3
- The selection procedure seeks a sufficient parameter subset before computing the full update, since thresholding the largest changes would require that full computation.The paper frames parameter selection probabilistically to identify regions of the network informative about a query sample.Source: §4 · p. 3
- CODEC can be inefficient on large discrete datasets because nearest-neighbor tie-breaking can become costly.Equal-valued points can force a nearest-neighbor search to expand all corresponding tree nodes.Source: §4 · p. 3
- Figure 2 routes perturbed samples, activations, and losses into L-FOCI, whose selected rows are layer slices used for unlearning.The activations are aggregated across perturbations.Source: Figure 2 · p. 4
- Adding small noise to tied values perturbs equal-value rankings while preserving the ranking between unique values, and the dependence measure remains correct in expectation.The passage relates this randomization to a criterion for conditional independence.Source: §4 · p. 4
- A randomized variant of the Chatterjee rank coefficient can support sensitivity analysis of input features or pixels and estimate their effect on the output.The passage presents this as an explainability application of the setup.Source: §4 · p. 4
4.1. Efficient Subset Selection that is also Sufficient for Predictive Purposes
- L-FOCI builds the sufficient set incrementally by moving the most dependent feature into it and estimating variance changes directly.This avoids permutation testing used by some information-theoretic measures.Source: §4.1 · p. 4
5. Deep Unlearning via L-FOCI Hessians
L-FOCI selects a sample-specific parameter subset from perturbed activations, allowing a blockwise Newton update without inverting the full model Hessian. Under nonzero layer-wise sampling probabilities, the method has an approximate forgetting guarantee and converges exponentially in expectation with respect to the precision gap.
5. Deep Unlearning via L-FOCI Hessians
- For linear layers, L-FOCI uses influential slices: each activation entry corresponds to a slice of parameters, finer than layerwise selection but coarser than individual parameters.For activation entry al,j, the associated parameter slice is wl[:, j].Source: §5 · p. 4
- The algorithm perturbs the sample, runs L-FOCI on activations and losses, estimates subset Hessians by finite differences, then applies a blockwise Newton update with DP noise.Activations are collected during forward passes; the original training pass stores gradients from the last and penultimate epochs.Source: §5 · p. 5
- The subsetted procedure costs O(md + dm log m + p^3), rather than O(d^3) for updating all parameters, with p ≪ d in reasonable settings.The terms correspond to forward passes, FOCI, and subsetted matrix inversion; sampling adds a linear computational load.Source: §5 · p. 5
5.1. Theoretical Analysis
- A lemma bounds the gradient-residual gap between the FOCI update and full unlearning; its proof attributes the result to limited propagation from selected layers and a Taylor expansion.The stated propagation to other layers is by 1/n.Source: §5.1 · p. 5
- With nonzero layer-wise sampling probabilities, the procedure is (ϵ′, δ′)-forgetting and converges exponentially fast in expectation with respect to the precision gap.The iteration bound is O(log 1/gϵ log 1/gδ), where gϵ = ϵ′ − ϵ and gδ = δ′ − δ.Source: §5.1 · p. 5
- For nonconvex models, the argument requires minimizers satisfying Second Order Sufficiency; when the Hessian is indefinite, a modified-Hessian Newton step is suggested.The paper also uses weight decay for approximate strong convexity and smooths the Hessian before inversion.Source: §5.1 · p. 6
6. L-FOCI in Generic ML Settings
The experiments assess L-CODEC and L-FOCI for Markov Blanket identification and CelebA attribute regularization. L-CODEC improves runtime and identification over raw-data CMI, while L-FOCI is faster but identifies an additional spurious feature in latent space; in CelebA, FOCI regularization gives the best reported result.
6. L-FOCI in Generic ML Settings
- Figure 3 compares L-CODEC and CODEC wall-clock time for sufficient-subset selection separately across CelebA attributes.Each attribute is shown as a pair of columns; further details are in the supplement.Source: Figure 3 · p. 6, §6 · p. 6
- Replacing CMI with L-CODEC improves runtime and Markov Blanket identification over raw data, with comparable results in latent feature space; L-FOCI is faster there but finds an extra spurious feature.The Table 1 caption reports that both methods run much faster than recent Markov Blanket identification schemes, while L-FOCI is not applicable to multidimensional raw data.Source: §6 · p. 6, Table 1 · p. 6
- In CelebA No Beard classification, FOCI selection gives the best result, maintaining high overall accuracy and high accuracy on samples with or without correlated attributes.Figure 4 compares regularization over all features, a random subset, and FOCI; green and red denote accuracy with and without the feature, respectively.Source: Figure 4 · p. 6, §6 · p. 7
7. L-FOCI for Machine Unlearning
The experiments apply L-FOCI to unlearning in MNIST and CIFAR-10 models, LEDGAR provision classification, VGGFace, and Market-1501 person re-identification. Across these settings, results show target-class or target-person performance declining while residual or overall performance changes more gradually, with outcomes depending on the privacy parameter.
7.1. Compare to Full Hessian Computation
- L-FOCI-selected subsets yield larger post-removal sample gradient norms than equally sized random subsets; higher-base-accuracy CIFAR-10 models support more removals.For models larger than logistic regression, estimating the full Hessian is infeasible, so the experiments use L-FOCI selection.Source: §7.1 · p. 7
- In an MNIST comparison against retraining at each step, many removals are supported before validation accuracy falls by more than a few percent.The comparison uses 1,000 training samples from each class and privacy parameters ε=0.1, δ=0.01.Source: §7.1 · p. 7
7.2. Removal in NLP models
- For LEDGAR, removed-class Micro F1 falls rapidly while overall Micro F1 changes more gradually; increasing ε permits more removals.The experiments use a fine-tuned DistilBERT model on 110,156 provisions with 13 commonly used labels.Source: §7.2 · p. 7
7.3. Removal from Pretrained Models
- For VGGFace, at privacy guarantee ε=10^-5, scrubbing consecutive images from one individual causes performance on that class to drop faster than performance on the residual set as samples scrubbed increase.Source: §7.3 · p. 7
7.4. Removal from Person re-identification model
- At ε=0.1, all Market-1501 samples for a person can be removed without noticeable mAP degradation, while ε=0.0005 supports fewer than 10 removals.After scrubbing, the model’s predictions for that person become meaningless while predictions for other classes remain possible with confidence.Source: §7.4 · p. 8
8. Conclusion
The conclusion emphasizes that selecting a subset of parameters for updates reduces the computational requirements of Hessian-based unlearning and enables approximate unlearning in some large vision models. It also cautions that the approach does not guarantee perfect forgetting and would require additional validation as part of a broader set of methods.
8. Conclusion
- The selection scheme updates a subset of parameters, significantly reducing the compute requirements of standard Hessian unlearning.The authors report approximate unlearning in large vision models, which they say had not previously been demonstrated.Source: §8 · p. 8
- The approach cannot guarantee perfect forgetting and would need additional validation as part of a suite of unlearning methods.The conclusion frames this as relevant to service-provider costs as opt-out laws are implemented.Source: §8 · p. 8
A.1.1. Proof of Lemma 1
The proof analyzes the gradient-residual gap between FOCI’s selected Hessian update and a full unlearning update. It argues that limited propagation from updated layers makes the gap shrink as the training set grows.
A.1.1. Proof of Lemma 1
- FOCI updates selected slices T while leaving the remainder R unchanged; the proof tracks the residual gradient norm after removing a sample from D.The residual dataset is D′ = D \ z.Source: §A.1.1 · p. 11
- For the three-layer analysis, updating intermediate layer L2 leaves L1 and L3 unchanged, and the proof argues that downstream propagation is minimal for large n.The argument relies on full model convergence and a term that tends to zero as n grows.Source: §A.1.1 · p. 11
- The gap between FOCI’s selected update and the full update is confined to the remainder R and shrinks as O(1/n^2).The lemma concerns the gradient residual norm of the two updates.Source: §A.1.1 · p. 11
A.1.2. Proof of Theorem 1
The theorem proof treats the update as randomized block coordinate descent and applies existing convergence results. Its appendix also reports experimental hardware and settings for Markov blanket selection.
A.1.2. Proof of Theorem 1
- With nonzero layer-wise sampling probabilities, the procedure is (ε′, δ′)-forgetting for ε′>ε and δ′>δ, and repeated application converges exponentially fast in expectation with the precision gap.The iteration bound is at most O(log 1/gδ), where gδ=δ′−δ.Source: §A.1.2 · pp. 11–12
- The proof casts the update as randomized block coordinate descent, with CODEC-derived sampling probabilities rather than random sampling at each step.It applies existing convergence rates and uses a separate lemma to obtain the probabilistic forgetting guarantee.Source: §A.1.2 · p. 12
B.2. Experimental Details; B.2.1. Markov Blanket Selection
- Experiments used PyTorch 1.8 and CUDA Toolkit 10.2 on Nvidia 2080 TIs and individual A100s; 5,000 samples generated data, and 100 trials/permutations tested CIT.Parallelization occurred only across runs.Source: §B.2 · p. 12, §B.2.1 · p. 12
B.2.2. L-CODEC vs CODEC Speed Results
The CelebA comparison measures L-CODEC and CODEC runtime for identifying sufficient subsets across attributes. Each attribute is shown as a pair of columns, with the remaining attributes available as conditioning variables.
B.2.2. L-CODEC vs CODEC Speed Results
- Each pair of columns corresponds to a CelebA attribute treated as the focal variable.The other attributes serve as potential conditioning variables.Source: §B.2.2 · p. 12
- L-CODEC and CODEC runtimes are compared for sufficient-subset identification, separately for each CelebA attribute.The figure caption identifies the comparison but supplies no runtime values or winning method.Source: Figure 9 · p. 12
- The comparison concerns identifying sufficient subsets for each attribute separately, rather than one joint subset across all attributes.The figure caption describes separate attribute-level comparisons.Source: Figure 9 · p. 12, §B.2.2 · p. 12
B.2.3. MNIST Toy Results
These supplementary results describe experimental settings and unlearning behavior across MNIST, CIFAR-10, LEDGAR, VGG-Face, and person re-identification, alongside L-CODEC parameter selection and an alternate Hessian approximation.
B.2.3. MNIST Toy Results
- MNIST logistic-regression experiments used SGD for 50 epochs and averaged main-paper results over 10 replications of 1,000 randomly selected samples to scrub.The privacy parameters were ϵ = 0.1 and δ = 0.01; distribution approximation used 1,000 perturbations.Source: §B.2.3 · p. 12
B.2.4.1 MNIST: Affects of l2 Regularization and Weight Decay
- Larger weight decay diminished removal effects and let the MNIST model support more removals before large performance drops.Figure 10 compares LFOCI unlearning with retraining under different weight-decay settings.Source: §B.2.4.1 · p. 12, Figure 10 · p. 12
B.2.4.2 CIFAR Retraining Comparisons: A Note on Batch Normalization
- Batch-normalized CIFAR retraining shows spikes when the final batch has size one; dropping that batch is incompatible with measuring removal of specific samples.The authors advise care with batch-normalized models and note that further theoretical and practical work may be needed.Source: §B.2.4.2 · p. 13, Figure 11 · p. 13
B.2.6. LEDGAR DistillBERT Details
- LEDGAR experiments fine-tuned DistilBERT on 110,156 provisions covering 13 common labels, then scrubbed provisions from Governing Laws and Terminations.Those two classes had the highest and lowest test-set support, respectively; the number removed varied with ϵ.Source: §B.2.6 · p. 13
B.2.7. VGG-Face Identification Scrubbing
- VGG-Face scrubbing removed 100 randomly ordered images for one identity, using ϵ = 0.0001 and δ = 0.01.The partial dataset contained 100 images per identity, and 100 perturbations estimated L-FOCI activation and loss distributions.Source: §B.2.7 · p. 13
B.2.8. Person Re-identification
- With lower ϵ, fewer samples could be unlearned while maintaining performance; on smaller re-identification datasets, more layers were selected for updates.The smaller datasets, PRID and QMUL GRID, have approximately two samples per class; activation maps compare scrubbed and non-scrubbed identities.Source: §B.2.8 · p. 14, Figure 12 · p. 15
C.3. Conditional Independence and Parameter Selection via L-CODEC
- L-FOCI starts with the parameter maximizing T(z′, w_p), then adds parameters while conditional dependence remains.The procedure returns a sufficient parameter set P; the algorithm is adapted from [1].Source: §C.3 · p. 14
D.4. Alternate Hessian Approximations
- K-FAC showed no observable validation-metric updates, while L-CODEC unlearned the same data points on the same model; non-sparse approximations may need a redesigned update step.The paper notes that a Hessian inverse for 50K+ parameters would require 10+GB alone, and cautions that broader applicability to non-sparse approximations is unresolved.Source: §D.4 · p. 14