Source-linked AI summary
Descent-to-Delete: Gradient-Based Methods for Machine Unlearning
Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi
TL;DR
The paper addresses how to delete data from trained convex models without repeatedly retraining them from scratch. It combines gradient-based optimization with reservoir sampling and distinguishes internal-state from output-only guarantees. The resulting algorithms handle arbitrarily long update sequences while maintaining bounded per-update runtime and steady-state error, with improved tradeoffs for sufficiently high-dimensional data.
Problem
Existing models retain deleted data’s influence, while retraining from scratch after each request has enormous computational cost.
Method
The paper combines perturbed gradient descent with partitioning, parameter aggregation, and reservoir sampling, analyzing perfect and output-only unlearning.
Results
The algorithms provide strong unlearning with runtime and steady-state accuracy that do not grow with update-sequence length, including improved tradeoffs for sufficiently high-dimensional data.
Takeaways & Limitations
Output-only indistinguishability enables more efficient deletion algorithms than indistinguishability of the entire internal state.
Takeaways & Limitations
The analysis assumes updated datasets remain at least n/2 in size and does not appear to yield perfect unlearning for non-strongly-convex functions with non-trivial parameters.
Abstract
from arXiv · showhide
We study the data deletion problem for convex models. By leveraging techniques from convex optimization and reservoir sampling, we give the first data deletion algorithms that are able to handle an arbitrarily long sequence of adversarial updates while promising both per-deletion run-time and steady-state error that do not grow with the length of the update sequence. We also introduce several new conceptual distinctions: for example, we can ask that after a deletion, the entire state maintained by the optimization algorithm is statistically indistinguishable from the state that would have resulted had we retrained, or we can ask for the weaker condition that only the observable output is statistically indistinguishable from the observable output that would have resulted from retraining. We are able to give more efficient deletion algorithms under this weaker deletion criterion.
1 Introduction
The paper develops efficient deletion for convex models while distinguishing guarantees over internal state versus observable outputs and strong versus weak update efficiency. Its gradient-based and partitioned methods target statistically indistinguishable retraining outcomes under arbitrarily long update sequences.
- Motivation: Deleting a database record does not remove its influence from existing predictive models, motivating model-level data deletion.Existing models may reveal information about specific training points.
- Motivation: Full retraining after every deletion is computationally expensive, so approximate statistical indistinguishability offers an alternative deletion criterion.The criterion compares model-output distributions with those produced by full retraining.
- Conceptual distinctions: The paper distinguishes perfect unlearning, which protects the entire internal state, from weaker unlearning, which protects only observable outputs.This distinction permits more efficient algorithms under the weaker criterion.
- Conceptual distinctions: Strong unlearning keeps per-update runtime constant or logarithmic in update-sequence length, whereas weak unlearning may grow polynomially; prior work was weak.The paper gives the first strong unlearning algorithms.
- Results and techniques: The first algorithm performs a few gradient updates followed by Gaussian perturbation, yielding strong perfect unlearning for strongly convex and smooth losses.Without strong convexity, strong algorithms may require secret state, while weak algorithms offer an accuracy–computation tradeoff.
- Results and techniques: The second algorithm uses bootstrap sampling, random partitioning, independent optimization, parameter averaging, and reservoir sampling to update only modified partitions.It improves accuracy–runtime tradeoffs when data dimension is sufficiently large.
2 Model and Preliminaries
The paper formalizes unlearning for convex models through update sequences, published outputs, indistinguishability, accuracy, and computational cost. Its convergence tools exploit proximity to optima and, for strong-convexity results, low optimizer sensitivity to individual updates.
- Model and update sequences: An update adds or deletes one data point, and an update sequence may contain arbitrarily many such operations.Datasets are multisets, and each update is a data point paired with an add or delete operation.
- Model and update sequences: The unlearning algorithm updates a model using the dataset, one update, and a prior model, while a publishing function maps its secret state to the public model.The public guarantee concerns whether published outputs could have arisen from retraining or from an update sequence.
- Unlearning criteria: (ε, δ)-unlearning requires published outputs after every update to be statistically indistinguishable from outputs produced by full retraining.The notion extends prior approximate deletion to sequences containing both additions and deletions.
- Assumptions: The dataset-size assumption n_i ≥ n/2 supports bounds stated using the original training size while permitting arbitrarily long sequences with additions.The assumption is presented as a notational convenience rather than a necessary condition.
- Optimization preliminaries: The analysis assumes convex, closed parameter domains and uses projected gradient descent, whose convergence improves when initialization is close to the optimum.For strongly convex losses, the paper uses low sensitivity of the optimizer to individual data updates.
- Unlearning criteria: Strong unlearning keeps accuracy independent of sequence length and update cost growing at most logarithmically with the update index; weak unlearning allows polynomial growth.The paper also distinguishes perfect unlearning, which uses the published prior model as input, from ordinary unlearning, which may maintain secret state.
3 Basic Perturbed Gradient Descent
The basic construction combines projected gradient descent with Gaussian perturbation: each update starts near the current optimizer, converges toward the new one, and publishes a noisy parameter. The resulting tradeoffs support strong and perfect unlearning under strong convexity, while regularization extends guarantees to merely convex losses with weaker sequence dependence.
- Perturbed gradient descent: Perturbed gradient descent runs until the parameter is within Euclidean distance α of the optimizer, then publishes it after adding Gaussian noise.The same basic idea is used by both training and deletion algorithms.
- Perturbed gradient descent: Each update initializes gradient descent at the previously learned parameter, enabling faster convergence because the starting point remains near the updated optimum.Strong convexity and the sensitivity bound control how far the optimum moves after an update.
- Runtime–accuracy tradeoff: The computational budget is parameterized by I iterations, corresponding to approximately nI gradient computations per update, with runtime traded against accuracy.For weak algorithms, I denotes the iteration count at the first update.
- Strongly convex losses: Under strong convexity, Theorem 3.1 gives strong (ε, δ)-unlearning and an (α, β)-accuracy guarantee for the perturbed-gradient procedure.The theorem assumes losses that are m-strongly convex, L-Lipschitz, and M-smooth.
- Strongly convex losses: The same construction yields perfect unlearning with the same asymptotic runtime–accuracy tradeoff when per-update runtime is at least logarithmic in the relevant parameters.The additional runtime lets the update algorithm recover from Gaussian noise in the saved state.
- Regularized convex losses: For convex losses, adding a strongly convex regularizer produces a regularized objective with strong-convexity, Lipschitzness, and smoothness parameters controlled by the regularizer.The regularized construction provides strong unlearning guarantees, while the later theorem provides weak unlearning with update iterations growing as i^2I.
- Regularized convex losses: The regularized method can trade sequence dependence against runtime by using T_i = i^(2ξ)·I iterations for any constant ξ ≥ 1.Theorem 3.5 corresponds to ξ = 1 and gives weak unlearning with an accuracy guarantee.
4 Perturbed Distributed Descent
Perturbed distributed gradient descent combines bootstrap sampling, random partitioning, independent optimization, and model publishing to support efficient unlearning. Reservoir sampling preserves the required sample distribution while limiting updates to affected partitions, yielding strong unlearning and accuracy guarantees under stated assumptions.
- Computation: Only partitions containing modified sampled points need parameter updates, allowing the gradient budget to be concentrated on smaller partitions.The partition size reduction by a factor of K provides the runtime improvement over basic gradient descent.
- Algorithm: The method bootstraps the dataset, randomly partitions the sample, independently optimizes each partition, averages the parameters, and publishes a perturbed model.The construction addresses the lack of a fixed data-generating distribution under arbitrary additions and deletions.
- Algorithm: Reservoir sampling with replacement maintains each sampled dataset with the correct marginal distribution after additions and deletions.The maintained sample at round i is distributed as PB(Di), according to Lemma 4.2.
- Guarantees: Reservoir sampling modifies at most s_i = Õ(B/n) sampled data points with high probability, bounding the number of affected partitions per update.This bound supports allocating the round-i computation budget across modified partitions.
- Guarantees: Theorem 4.5 establishes that RA is a strong (ε, δ)-unlearning algorithm for A with respect to the publishing function.The theorem also gives an (α, β)-accuracy guarantee under strong convexity, smoothness, Hessian regularity, and specified sampling and optimization parameters.
- Guarantees: The distributed method improves over the basic perturbed gradient-descent bound under the parameter regime identified in Remark 4.6.The improvement applies for the stated range 1 ≤ ξ ≤ 4/3 and the corresponding condition in the theorem’s comparison.
A Probabilistic Tools
This appendix collects probabilistic tools used in the paper’s proofs, including conditional indistinguishability, Gaussian concentration and mechanisms, expectation bounds, and Chernoff bounds.
- Conditional probability: Lemma A.1 relates conditional guarantees over a random variable Z to an unconditional guarantee for X.The proof decomposes events according to a high-probability good event over Z.
- Gaussian tools: Lemma A.2 states a Gaussian tail bound for Z ∼ N(0, σ^2I_d).The bound is used as a concentration tool for isotropic Gaussian noise.
- Gaussian tools: Lemma A.3 gives the Gaussian mechanism condition for two Gaussian distributions with equal covariance and nearby means.It supports indistinguishability arguments based on bounded Euclidean distance between means.
- Concentration: Lemma A.4 provides an expectation-based bound for nonnegative random variables and independent samples.The lemma is paired with standard concentration arguments elsewhere in the analysis.
- Concentration: Lemma A.5 states a Chernoff bound for a binomial random variable X ∼ Binomial(m, p).This tool bounds repeated sampled points in the reservoir-sampling analysis.
B Proof of Sensitivity Lemma 2.12
The appendix proves the sensitivity lemma by combining strong convexity with Lipschitz loss changes under deletion, then reducing additions to the deletion case.
- Strong-convexity claim: Claim B.1 derives a lower bound on h(θ)−h(θ*) from m-strong convexity around the minimizer θ*.The proof uses the minimizer property and the definition of strong convexity.
- Sensitivity proof: The sensitivity proof analyzes deleting a point z from D and compares the minimizers associated with D and D′.If z is absent, the claim is immediate; otherwise the proof applies the strong-convexity claim and loss regularity.
- Sensitivity proof: The deletion bound extends to additions by treating an addition as the reverse of a corresponding deletion.The proof defines a deletion update u′ and invokes the established deletion result.
C Proofs of Lemmas in Section 4
The proofs in this section establish that reservoir sampling remains correctly distributed through updates and that each update changes only a small number of sampled points with high probability.
- Lemma 4.2: Lemma 4.2 is proved by induction over updates, starting from an initial sample drawn from PB(D0).For deletions, conditioning on the update preserves conditional independence and gives each replacement element the updated empirical distribution.
- Lemma 4.2: For additions, the reservoir-sampling-with-replacement operation directly preserves the required sample distribution.The proof cites the standard reservoir-sampling construction for this case.
- Lemma 4.3: Lemma 4.3 bounds repeated copies of any data point by modeling its count as Binomial(B, p) with p ≤ 2/n.Since μ = 2B/n ≥ 1, a Chernoff bound controls the number of modified sampled points with high probability.
D Proof of Theorem 3.2
The proof establishes the unlearning guarantee by induction over updates, combining convergence, sensitivity, and Gaussian-noise bounds, then derives an accuracy guarantee for every update step.
- The induction argument shows RA is an (ǫ, δ)-unlearning algorithm for A.The proof controls successive updated parameters using convergence, sensitivity, and Gaussian-tail bounds before applying Lemma A.1.
- Gaussian perturbation and the optimizer characterization support the published-output analysis at every update step.The proof models published parameters as noisy versions of secret parameters and compares them with the optimizer of each updated dataset.
- The accuracy statement holds for any update step with probability at least 1 −β −δ/2.This conclusion uses the theorem’s noise choice, Gaussian-tail bounds, and M-smoothness of the loss.
E Proof of Theorem 3.5
The proof of Theorem 3.5 establishes unlearning through an inductive parameter bound and then derives accuracy using convergence, Gaussian noise, and the theorem’s regularization and sampling choices.
- The proof assumes every updated dataset retains at least n/2 points, enabling the sensitivity bound used throughout the induction.The dataset sizes satisfy ni ≥ n/2 under Assumption 2.6.
- The accuracy analysis combines convergence bounds, the choice of σ, Gaussian tails, and M-smoothness to obtain the theorem’s guarantee.The proof first establishes intermediate expectation and high-probability bounds before completing the result with the selected B and regularization parameters.
F Proof of Theorem 4.5
The proof of Theorem 4.5 analyzes a partition-and-average algorithm under non-adaptive updates, coupling its maintained partitions with retraining and controlling affected partitions across rounds.
- The algorithm partitions data, optimizes each partition independently, averages the learned parameters, and publishes a perturbed average.The maintained state includes per-partition parameters, their average, published parameters, and the number of affected points.
- Reservoir-sampling control bounds the maximum number of affected points through the update sequence with high probability.The proof conditions on the event that the maximum affected count is at most 10B/n log(2i/δ).
- The proof couples the maintained and retrained partitioned datasets because the update sequence is non-adaptive and independent of the algorithm’s internal randomness.Under this coupling, the corresponding partitioned datasets are equal with probability one.
- The induction tracks unchanged and changed partitions separately, applying convergence and sensitivity bounds to affected partitions.The resulting bounds are then combined across partitions to control the averaged parameters and published outputs.
- The proof concludes that RA is an (ǫ, δ)-unlearning algorithm for A.The conclusion follows after applying Lemma A.1 to the retraining and update-output distributions.