PaperlayerView exact revision on arXiv

Source-linked AI summary

Adaptive Machine Unlearning

Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Chris Waites

arXiv:2106.04378v1cs.LGstat.ML

TL;DR

Prior unlearning guarantees often assume deletion requests are independent of released models, despite users potentially choosing deletions adaptively based on those models. The paper reduces adaptive deletion guarantees to non-adaptive guarantees using differential privacy and max information, while showing prior methods can fail adaptively and that privacy noise can mitigate attacks.

  • Problem

    Prior deletion guarantees commonly assume deletion sequences are independent of released models, although model-dependent deletion requests can arise when users respond to revealed information.

  • Method

    The paper defines adaptive update requesters and reduces adaptive deletion guarantees to non-adaptive guarantees by combining differential privacy, post-processing, and max-information arguments.

  • Results

    The methodology provides model- and training-algorithm-agnostic guarantees for arbitrary adaptively chosen deletion sequences, while experiments show prior SISA variants can fail adaptively and small noise can break the attacks.

  • Takeaways & Limitations

    Differential privacy can mitigate adaptive deletion attacks at practical noise levels, extending protection beyond the paper’s formal theorem parameters.

  • Takeaways & Limitations

    The unlearning definition provides only a one-sided guarantee, and the theorem constants inherited from max-information bounds may be unhelpful in realistic settings.

Abstract

from arXiv · show

Data deletion algorithms aim to remove the influence of deleted data points from trained models at a cheaper computational cost than fully retraining those models. However, for sequences of deletions, most prior work in the non-convex setting gives valid guarantees only for sequences that are chosen independently of the models that are published. If people choose to delete their data as a function of the published models (because they don't like what the models reveal about them, for example), then the update sequence is adaptive. In this paper, we give a general reduction from deletion guarantees against adaptive sequences to deletion guarantees against non-adaptive sequences, using differential privacy and its connection to max information. Combined with ideas from prior work which give guarantees for non-adaptive deletion sequences, this leads to extremely flexible algorithms able to handle arbitrary model classes and training methodologies, giving strong provable deletion guarantees for adaptive deletion sequences. We show in theory how prior work for non-convex models fails against adaptive deletion sequences, and use this intuition to design a practical attack against the SISA algorithm of Bourtoule et al. [2021] on CIFAR-10, MNIST, Fashion-MNIST.

1 Introduction

Machine unlearning seeks a cheaper alternative to full retraining while preserving retraining-like model behavior, but prior guarantees often fail when deletion requests adapt to published models. The paper develops a differential-privacy-based reduction to support adaptive deletions and demonstrates failures of prior methods experimentally.

  • Motivation: Machine unlearning aims to remove deleted data’s influence without repeatedly paying the prohibitive time and money costs of full retraining.The target is an algorithmic middle ground between compliant retraining and doing nothing.
  • Approach: The resulting methodology is model- and training-algorithm agnostic, accommodates arbitrary non-convex models, and can be combined modularly with prior deletion algorithms.The paper describes a variant of SISA combined with differentially private aggregation as one implementation route.
  • Adaptive deletion: Prior deletion guarantees assume deleted points are independent of training randomness and previously released model information, an assumption adaptive users may violate.Users may request deletion because deployed models reveal information about them.
  • Evidence: Two SISA variants that perfectly delete under non-adaptive sequences exhibit adaptive sequences that strongly separate their model distributions from the retraining baseline.The paper evaluates this theoretical failure pattern on CIFAR-10, MNIST, and Fashion-MNIST.
  • Evidence: Small amounts of noise, insufficient for the paper’s theorems, empirically break the adaptive deletion strategies used in the experiments.This provides evidence that differential privacy can mitigate adaptive attacks at practical levels beyond the formal guarantees.
  • Approach: The paper gives a generic reduction from adaptive to oblivious deletion guarantees by obscuring internal algorithmic randomness with differential privacy.The reduction applies when the base deletion algorithm handles oblivious sequences and released information about its randomness is differentially private.

2 Preliminaries

The paper formalizes sequential additions and deletions, adaptive requesters, model updates, publication, and one-sided unlearning guarantees. It also introduces differential privacy and max-information as the tools connecting published information to adaptive behavior.

  • Update model: An update is a datapoint paired with either an addition or deletion operation, and an update sequence is an ordered stream of such requests.Datasets evolve by applying each operation sequentially.
  • Algorithms: The training algorithm maps datasets to collections of models, while the update algorithm uses the dataset, request, and current state to produce updated models.The sequential update algorithm also updates its internal state after each request.
  • Publication: Published objects can expose model information through a publication mapping, including aggregate predictions or other model aggregations.Access is provided round by round through publication functions.
  • Requesters: An adaptive update requester maps interaction history to the next update, whereas a nonadaptive requester is independent of published objects and has a sequence fixed before interaction.The requester may be randomized.
  • Guarantees: Sequential unlearning requires, at every update step, that events under updated models are not substantially more probable than under full retraining, with failure probability bounded by γ.The formal definition quantifies over datasets and update requesters.
  • Guarantees: The paper’s unlearning guarantee is one-sided: it prevents increased observer confidence that full retraining was not used, but does not prevent increased confidence that it was used.Events are defined over model collections, which is stronger than defining them only over observable outputs.
  • Privacy tools: Differential privacy bounds how outputs change on neighboring datasets, and its post-processing property preserves the same privacy parameters after data-independent transformations.The paper applies privacy to collections of random bits parameterizing randomized algorithms rather than their training datasets.
  • Privacy tools: Max-information measures dependence between an algorithm’s input dataset and output, and differential privacy provides a bounded-max-information guarantee used in the reduction.The paper states this connection through Theorem 2.1.

3 A Reduction from Adaptive to Nonadaptive Update Requesters

The paper reduces adaptive deletion guarantees to non-adaptive guarantees by protecting the learning and unlearning randomness with differential privacy, then applying max-information bounds.

  • The learning algorithm draws randomness once, passes it to unlearning, and thereby makes subsequent models and state deterministic given requests and that randomness.The randomness is represented as internal state throughout the update sequence.
  • Prior analyses assume internal randomness is independent of updates, but adaptive requesters can make updates depend on published information.The paper identifies this dependence as the central obstacle to extending non-adaptive guarantees.
  • If publishing functions are differentially private in the internal randomness and unlearning is valid for non-adaptive requests, the same pair obtains adaptive deletion guarantees with adjusted parameters.Theorem 3.1 states the transformed guarantee parameters as α′ = α + ϵ′, β′ = β + δ′, and γ′ = γ + δ′.
  • The proof uses post-processing, max information, and conditional resampling of randomness to remove dependence between the randomness and adaptive requests.Resampling from the prior distribution reduces the analysis to the non-adaptive case.

4 Distributed Algorithms

The distributed algorithms independently shard data, retrain only affected shard models, and combine non-adaptive exact guarantees with the reduction to support adaptive requests under private publication.

  • 4 Distributed Algorithms: The distributed framework creates k independent shards, trains one model per shard, and permits arbitrary single-shard models, training procedures, and prediction aggregation.The framework is a modified SISA-style construction.
  • 4 Distributed Algorithms: For deletions, the update removes a point from every shard containing it and retrains only the corresponding models; additions sample shards independently with probability p.The unlearning state stores the shards and ensemble models.
  • 4 Distributed Algorithms: RAdistr is a (0, 0, 0)-unlearning algorithm for Adistr against non-adaptive update requesters.This exact guarantee is the base case for the adaptive reduction.
  • 4 Distributed Algorithms: Under differential privacy in the shard random seeds, Theorem 4.1 converts the non-adaptive guarantee into an (α, β, γ)-unlearning guarantee for adaptive requesters.The theorem assumes 0 < ϵ ≤ 1/2 and 0 < δ < ϵ.
  • 4 Distributed Algorithms: For p = 1/k, the runtime analysis gives high-probability bounds on the number of single-shard retrainings, with separate bounds for non-adaptive and adaptive requests.The adaptive analysis uses either direct bounds or a max-information reduction to the non-adaptive case.
  • 4 Distributed Algorithms: Prediction outputs are privately aggregated, privacy loss is tracked across requests, and full retraining resets the privacy budget when it is exhausted.Private aggregation is used to make published predictions differentially private in the models and hence in the random seeds.

5 Evaluation of Unlearning Guarantees

The evaluation shows that adaptive deletion sequences can break SISA’s guarantees, while modest DP-SGD noise can defeat the practical attack with limited accuracy degradation.

  • 5 Evaluation of Unlearning Guarantees: SISA can fail to provide nontrivial adaptive deletion guarantees even when only aggregate classification outputs are public.The evaluation covers both label-only and full-model settings.
  • 5 Evaluation of Unlearning Guarantees: In the toy construction, an ensemble trained on three random partitions correctly classifies roughly 2/3 of training points, enabling an adversary to delete those points.After deletion, the remaining points are misclassified, whereas full retraining restores approximately 2/3 training accuracy.
  • 5.2 Experiments for the Full-Model Setting: The practical attack guesses shards from neural-network confidence, targets the first k/2 shards, and compares their post-deletion accuracy with non-targeted shards.Under full retraining, symmetry makes the test statistic’s expected value 0.5.
  • 5.2 Experiments for the Full-Model Setting: On CIFAR-10, MNIST, and Fashion-MNIST, modest DP-SGD noise makes 95% confidence intervals include 0.5 while accuracy remains close to the no-noise models.The result provides evidence that differential privacy can improve deletion guarantees under adaptivity beyond the theory’s nontrivial regime.

6 Conclusion and Discussion

The paper identifies adaptive deletion as a blindspot in prior work and develops a general reduction from adaptive to oblivious deletion guarantees. Its guarantees are broadly applicable but depend on parameter choices, and the inherited constants may be impractical.

  • Prior deletion guarantees often assume deleted points are independent of previously released models, an assumption that fails when users respond to model disclosures.The paper highlights this as an important blindspot in the data deletion literature.
  • The proposed methodology reduces guarantees for adaptively chosen deletion sequences to guarantees for obliviously chosen sequences.The reduction is described as model- and training-algorithm agnostic and supports arbitrary sequences of adaptively chosen points.
  • The resulting framework can be combined with prior non-adaptive deletion algorithms and differentially private aggregation in a modular way.The paper presents the pipeline as broadly applicable to existing learning and deletion methods.
  • The theorem constants inherited from max-information bounds may not provide useful parameters in most realistic settings.The paper expects future improvements to these constants and reports empirical evidence that differential privacy mitigates adaptive attacks at practical levels.
  • The deletion guarantees are parameterized and are not meaningful without specifying their parameters.The paper warns that large parameter values can yield weak guarantees that may be described misleadingly.

A Proof of Theorem 3.1

The proof converts differential privacy of published outputs into bounded dependence between randomness and adaptive updates. Conditioning on a high-probability good event then transfers non-adaptive unlearning guarantees to adaptive sequences with adjusted parameters.

  • A max-information bound controls the joint distribution of the algorithm’s randomness and the adaptive update sequence relative to independent marginals.This control is used to compare adaptive updates with non-adaptively chosen updates.
  • Theorem 3.1 assumes differential privacy for the sequence of publishing functions and a non-adaptive (α, β, γ)-unlearning algorithm.Under these assumptions, the theorem establishes adaptive unlearning guarantees with modified parameters.
  • The update sequence is a post-processing of previously published objects, so differential privacy is preserved for the adaptive updates.The proof applies the post-processing property before invoking the connection between differential privacy and max information.
  • Conditioning on the good event for the update sequence preserves the non-adaptive unlearning comparison for every event in model space.The proof first obtains a high-probability good event and then applies the non-adaptive guarantee to the conditioned analysis.
  • Combining the two probability comparisons yields the adaptive deletion guarantee with failure probability accumulated from the non-adaptive guarantee and the conditioning step.The proof concludes by combining Equations (3) and (4).

B Missing Details from Section 4

The distributed construction gives exact non-adaptive unlearning and extends it to adaptive requests through private publishing. Its shard updates preserve sampling distributions, while adaptive requests incur additional runtime and parameter costs.

  • Deleting a point from every shard containing it preserves the property that each retained element is sampled into a shard with probability p.The same sampling invariant supports the distributed unlearning analysis across sequential deletions.
  • RAdistr is a non-adaptive (0, 0, 0)-unlearning algorithm for Adistr.This exact guarantee is the base case for the adaptive reduction.
  • The adaptive guarantee for RAdistr follows by combining the exact non-adaptive result with Theorem 3.1’s differential-privacy reduction.The construction treats shard randomness jointly and applies the general theorem to the distributed algorithms.
  • For p = 1/k, the initial number of single-shard retraining calls is N^0 = k, with later counts controlled by binomial-tail bounds.The runtime theorem distinguishes non-adaptive and adaptive update requesters.
  • Adaptive runtime bounds include logarithmic dependence on (n + t)/ξ, whereas non-adaptive bounds use logarithmic dependence on 1/ξ.The theorem gives separate high-probability bounds for the two requester types.

C.1 Proof of Theorem 5.1

The proof constructs a lookup-table SISA instance where an adaptive requester deletes correctly classified duplicates. This makes the unlearning output concentrate on models with zero remaining accuracy, unlike full retraining.

  • There exist SISA learning and unlearning algorithms for which, for any α and β, γ < 1/4, the unlearning algorithm fails to satisfy (α, β, γ)-unlearning.The theorem establishes failure against an adaptive update requester.
  • The counterexample uses duplicated feature vectors, random shard assignment, and a lookup-table model that predicts labels only for examples present in its shard.The ensemble predicts by taking the mode across shard models.
  • The adaptive requester deletes exactly the training points that the initial ensemble classified correctly.The deletion sequence is determined from the published predictions.
  • After these deletions, the event of zero ensemble accuracy occurs exactly when both copies of every remaining point lie in the same shard.The event is defined over the remaining dataset and shard model parameters.
  • The adaptive unlearning scheme assigns probability one to the zero-accuracy event, while the corresponding retrained model assigns it probability 1/3^(n−t).The proof compares the conditioned unlearning event with the probability under fresh random partitioning.
  • For sufficiently large n, the retraining probability is bounded by 1/3^(0.01n), yielding the separation required for the theorem with probability 1 − γ.The argument chooses n large enough to satisfy both the tail and event-probability conditions.

C.2 Failures in (0, 0, 0)-Unlearning Beyond Section 5.1

The section tests adaptive attacks against ASISA and RASISA in a more realistic setting using thresholded nearest-neighbor-like predictions. Confidence intervals distinguish adaptive deletion from full retraining sufficiently to reject perfect unlearning for sequences of at least 200 deletions.

  • C.2 Failures in (0, 0, 0)-Unlearning Beyond Section 5.1: ASISA and RASISA use a thresholded prediction rule that returns the label of the closest point to a query when sufficiently near.This relaxes the earlier construction's requirement that every point be copied twice.
  • C.2 Failures in (0, 0, 0)-Unlearning Beyond Section 5.1: The experiment publishes aggregated discrete predictions, adaptively deletes correctly classified points, and compares remaining-point accuracy with a retraining scenario.The tested hypothesis predicts lower accuracy after adaptive deletion than after retraining.
  • C.2 Failures in (0, 0, 0)-Unlearning Beyond Section 5.1: The analysis estimates the probability that adaptive deletion drives training accuracy below a cutoff using trial-level indicators and confidence intervals.Non-overlapping confidence intervals provide a basis for rejecting the null hypothesis.
  • C.2 Failures in (0, 0, 0)-Unlearning Beyond Section 5.1: For deletion sequences of 200 points or more, confidence intervals differed reliably enough to reject perfect (0, 0, 0)-unlearning at p ≤0.05.Figure 2 compares the adaptive-deletion statistic with the statistic after full retraining.
  • C.2 Failures in (0, 0, 0)-Unlearning Beyond Section 5.1: With τ = 6.5, the MNIST model achieved approximately 91.2% held-out test accuracy before deletion.The experiment sampled 1,000 points labeled either 0 or 1 and deleted uniformly random subsets of correctly predicted points.

C.3 Full Experiment Details of Section 5.2

The section documents the datasets, model architecture, optimization settings, computing environment, and numerical representation used for the Section 5.2 experiments.

  • C.3 Full Experiment Details of Section 5.2: All models use momentum with mass 0.9, while DP-SGD experiments use a per-example gradient clipping bound of 0.1.Some experiments reduce batch size to lower computational cost.
  • C.3 Full Experiment Details of Section 5.2: The model architecture uses two convolutional layers with Tanh activations and max pooling, followed by flattening and two dense layers.The convolutional layers have 16 and 32 output channels, respectively.
  • C.3 Full Experiment Details of Section 5.2: The experiments use MNIST, Fashion-MNIST, and CIFAR-10 as common benchmark datasets.MNIST contains 70,000 28 × 28 handwritten-digit images across 10 classes; the passage begins the corresponding Fashion-MNIST description.
  • C.3 Full Experiment Details of Section 5.2: Experiments run in JAX on one Tesla V100 GPU with CUDA 11.0, taking approximately 1–6 minutes per trial.Trial duration varies with shard count, iterations, image size, and related settings.
  • C.3 Full Experiment Details of Section 5.2: Table 1 reports indicator confidence intervals, held-out accuracy before and after deletion, DP-SGD noise multipliers, and shard-targeting accuracy.The indicator intervals use 300 trials; held-out accuracy uses 5,000-point test sets and two-standard-deviation intervals.
  • C.3 Full Experiment Details of Section 5.2: Table 2 lists the remaining hyperparameter settings separately for each dataset.The table is organized by dataset rather than presenting a single shared configuration.
Loading 2106.04378v1…