Sample-Grained Approximate Unlearning with Provable Per-Sample Bounds

AI summary

Overview

Research area: Machine unlearning and privacy-preserving machine learning, with a focus on making approximate unlearning match exact retraining at the level of individual samples.

Technical level: Advanced. The paper combines a plug-in optimization framework, per-sample distribution estimation, and formal bounds involving total variation, Bhattacharyya coefficients, and Gaussian assumptions.

Scope: The paper proposes SALA, a sample-grained alignment framework for approximate unlearning, together with a per-sample evaluation metric (DNO), formal guarantees, and an efficient target-distribution estimator (SMSE), evaluated on image classification and text generation.

What This Paper Is About

Approximate unlearning aims to remove a designated forget set from a trained model without the cost of full retraining, but its success is usually judged by dataset-level averages. Those averages can hide cases where individual samples still behave very differently from the exactly retrained model. The paper introduces sample-level targets, a metric, and theoretical bounds to make approximate unlearning align with retraining sample by sample.

Key Contributions

1. Sample-grained unlearning framework (SALA): SALA assigns each training sample a role-specific target distribution: retain samples are aligned to member behavior, and forget samples to non-member behavior. It minimizes a per-sample z-score relative to these targets and can be plugged into existing approximate unlearning methods.

2. Per-sample metric and theoretical guarantee: The paper defines Distribution Non-Overlap (DNO) to measure per-sample discrepancies between approximate unlearning and exact retraining output distributions. It proves that SALA's InDist constraint yields an upper bound on DNO, with a forget-set-only variant that retains a bound under an additional retain-consistency condition on the base unlearning algorithm.

3. Efficient distribution estimator (SMSE): SMSE estimates per-sample member and non-member distributions using split–merge training with Federated Averaging and checkpoint ensembles, reducing preparation from multiple shadow-model training runs to approximately one structured training run.

4. Automated hyperparameter selection and stopping: SALA uses InDist, the fraction of samples within a preset z-band of their targets, to probe candidate hyperparameters cheaply and to stop unlearning once a threshold such as 0.95 is exceeded. This reduces sensitivity to manually tuned hyperparameters.

Main Findings

• Aggregate metrics conceal sample-level failures: On CIFAR-10, SalUn reaches ToW = 0.95 while its DNO remains 0.9009 and its RULI attack accuracy remains 92.38%. On ImageNet-1000, SalUn again reaches ToW = 0.95 but has DNO = 0.9256 and RULI = 92.30%. Dataset-level similarity to retraining therefore does not eliminate per-sample deviation or unlearning-aware privacy leakage.

• SALA substantially reduces per-sample gap: Across CIFAR-10, ImageNet-1000, and WikiText-103, SALA achieves DNO values of 0.1365, 0.1268, and 0.1048, respectively, the lowest among approximate methods in the reported comparison. The abstract states that SALA reduces the sample-grained distribution gap by up to 86.67% when paired with existing approximate unlearning baselines.

• Privacy leakage is reduced: SALA keeps RULI close to random guessing, at 52.15%, 52.35%, and 50.92% on the three datasets, compared with 92.38% for SalUn on CIFAR-10 and 50.00% for exact retraining.

• Utility and efficiency are preserved: SALA maintains a small dataset-level gap to retraining and, according to the paper, reduces runtime by more than an order of magnitude relative to retraining across all three datasets. On CIFAR-10, exact retraining takes 1625.53 ± 5.33 seconds.

• Theory matches practice: Under the instantiation τ = 0.95, Z_cut = 2, and a clipped normal offset, Theorem 3.1 yields a closed-form DNO upper bound of about 0.10, which the paper compares with an empirical SALA DNO of about 0.11 in Section 5.3.

• SMSE estimates are more accurate than a single-run baseline: On CIFAR-10, SMSE raises the Pearson correlation for the non-member mean μ_out from 0.41 to 0.92 and lowers DNO_est from 0.4580 to 0.1801, at 1.00× nominal training cost versus 1.24× for the Laplace plus self-influence baseline.

• SMSE preserves model utility: The paper reports at most a 0.18% accuracy drop on vision tasks and a 0.99 PPL increase on WikiText-103 compared with standard training.

• Reduced variants remain effective: SALA-SMSE and SALA with only the forget set have higher DNO than full SALA, consistent with estimation error and relaxed retain-side constraints, but remain substantially below the corresponding SalUn baseline.

Methodology in Plain English

The method starts from the observation that a model should treat each sample in one of two ways: if the sample is kept, its output should look like the output of a model trained with that sample; if the sample is forgotten, its output should look like the output of a model that never saw it. SALA estimates these two reference distributions per sample and converts the model's current output score into a z-score relative to the appropriate reference.

During unlearning, SALA adds a guidance loss that pushes each sample's z-score toward zero, with separate weights for retain samples, forget samples, and a harder-to-forget subset. It also measures InDist, the fraction of samples whose outputs fall inside a fixed z-band around their targets. A short probe run tests several hyperparameter settings and picks the one with the best coverage; the full run then stops automatically once InDist passes a threshold such as 0.95. The theoretical result connects this coverage constraint to a bound on DNO.

Because obtaining the reference distributions through many shadow-model retrainings is expensive, SMSE splits the training data into two halves, warms up shared weights, trains one branch on each half, merges the branches with Federated Averaging, and fine-tunes on the full set. Late-stage checkpoints from the two branches serve as an ensemble: for any sample, one branch saw it and the other did not, giving member and non-member score estimates from a single structured training run.

The paper evaluates SALA on CIFAR-10 with ResNet-18, ImageNet-1000 with ResNet-50, and WikiText-103 with GPT-2, covering random sample unlearning, class-wise unlearning, and sequence unlearning. DNO is computed over 64 tasks on CIFAR-10 and 16 tasks on ImageNet-1000 and WikiText-103, with 12 approximate unlearning baselines on CIFAR-10 and five representative baselines on the larger datasets.

Why This Matters

Impact on research: The paper shifts attention from dataset-average gap-to-retrain scores to per-sample behavior, showing that a model can look successfully unlearned on average while individual samples remain far from their retrained counterparts. It provides a metric, a guidance mechanism, and bounds that make this level of analysis measurable and actionable.

Real-world applications:

• Regulatory deletion requests: Supporting compliance with the right to be forgotten under GDPR Article 17 by removing individual records without full retraining.
• Foundation-model providers: Allowing model owners to remove user data, copyrighted text, or sensitive sequences from deployed models at lower cost than retraining.
• Privacy auditing: Giving auditors a per-sample test for whether forgotten data still influences model outputs, including against unlearning-aware membership inference attacks such as RULI.
• Sensitive domains: Enabling record removal in healthcare, finance, and other settings where individual data deletion must be demonstrated rather than assumed.

Industry relevance: SALA is designed as a plug-in addition to existing approximate unlearning methods, uses an automated probe and stop criterion instead of manual tuning, and targets roughly single-training-run preparation cost through SMSE. Those properties matter for production systems that must handle repeated deletion requests efficiently.

Future Directions

• Relaxing distributional assumptions: The framework models per-sample scores as Gaussian and validates this experimentally, but broader score functions, architectures, and data modalities may require different or more flexible target families.

• Improving SMSE fidelity and cost: SMSE still relies on a structured split–merge training procedure and checkpoint ensembles. Better variance estimation and lower-cost alternatives could tighten the estimation-error term in the adjusted DNO bound.

• Extending beyond classification and text generation: Evaluating SALA on other modalities, larger foundation models, and sequential or repeated unlearning requests would test how broadly the per-sample guarantees hold.

• Standardizing per-sample evaluation: DNO and InDist could become part of unlearning benchmarks and audit reports, but this requires agreed protocols for estimating reference distributions and for adversarial evaluation under adaptive attackers.

• Relaxing access requirements: The forget-set-only variant still needs a retain-consistency condition on the base unlearning algorithm. Weakening this requirement would make provable per-sample unlearning practical in settings where the full retain set is unavailable.

Target Audience

This paper is most useful for machine unlearning researchers, privacy and security engineers, and graduate students with a background in machine learning and probability. It also suits model-platform teams and compliance-oriented practitioners who need to evaluate whether deletion requests are genuinely satisfied at the individual level, rather than only in aggregate benchmarks.

Authors’ abstract

Machine unlearning aims to erase the influence of a designated forget set from a trained model while preserving strong utility on the retain set. Approximate unlearning methods efficiently achieve this goal without full retraining, but their effectiveness is primarily assessed using dataset-level aggregate metrics. These aggregate metrics can mask deviations from retraining at the level of individual samples. In this work, we focus on per-sample unlearning effectiveness. We introduce SALA (Sample-grained Likelihoods ALignment), a plug-in optimization framework that enables approximate unlearning methods to operate at the level of individual samples by steering each example toward its correct target distribution. To quantitatively assess this behavior, we further propose the sample-grained distribution gap, a metric that captures per-sample discrepancies between approximate unlearning and exact retraining output distributions. We provide theoretical guarantees showing that SALA contracts this gap and yields a bounded per-sample discrepancy to retraining. To make this framework practical, we develop a low-cost estimation method for the member and non-member target distributions. Extensive experiments on classification and generation tasks demonstrate that SALA reduces the sample-grained distribution gap by up to $86.67\%$ when paired with existing approximate unlearning baselines, while also improving robustness to unlearning hyperparameters.