CoChat
Sign Up
PreprintCited by 103Privacy-Preserving Technologies in DataStochastic Gradient Optimization TechniquesCryptography and Data Security

Remember What You Want to Forget: Algorithms for Machine Unlearning

Open access
Sekhari, Ayush, Acharya, Jayadev, Kamath, Gautam, Suresh, Ananda Theertha·2021·arXiv
DOI 10.48550/arxiv.2103.03279arXiv 2103.03279
Open this paper in CoChat — free accountOpen PDF

Abstract

We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset $S$ drawn i.i.d. from an unknown distribution, and outputs a model $\widehat{w}$ that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint $z \in S$ can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity. For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to $O(n/d^{1/4})$ samples, where $d$ is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of $O(n/d^{1/2})$ samples. This demonstrates a novel separation between differential privacy and machine unlearning.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2103.03279

Cites

38 of 38 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Approximate unlearning is usually guaranteed by differential privacy techniques, such as (ε, δ)-certified unlearning.

    “This approximation is usually guaranteed by differential privacy techniques, such as ( ε , δ ) -certified unlearning [41, 42].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [42]

    Section 3.2 (p. 7) says differential privacy can provide an unlearning guarantee, and the proof of Lemma 1 (p. 18) shows that an (ε, δ)-DP algorithm yields (ε, δ)-unlearning. The paper does not establish that approximate unlearning is *usually* guaranteed this way; it also develops an unlearning method that improves on direct DP approaches. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Based on the guarantee provided by certified unlearning, Guo et al. [41], Warnecke et al. [53], and Sekhari et al. [42] limit the distribution similarity between the unlearned model and the retrained model.

    “Based on the guarantee provided by certified unlearning , they limit the distribution similarity between the unlearned model and the retrained model.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [42]

    Section 2.2 (p. 5) defines an unlearning guarantee that makes the output after deletion difficult to distinguish from an output based on training on the remaining data. But the comparison includes applying the unlearning algorithm with no deletion requests to that retrained model; the paper explicitly distinguishes this from comparing directly with the retrained model’s output. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • Sekhari et al. [42] proposed a more general method of reducing the loss of unseen samples after an unlearning process.

    “Sekhari et al. [42] proposed a more general method of reducing the loss of unseen samples after an unlearning process.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [42]

  • Sekhari et al. [42] proposed an evaluation parameter to measure the unlearning capacity.

    “In addition, they proposed an evaluation parameter to measure the unlearning capacity.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [42]

  • Guo et al. [41], Warnecke et al. [53], and Sekhari et al. [42] provide a method of theoretical verification to verify the effectiveness of their proposed unlearning schemes.

    “Guo et al. [41], Warnecke et al. [53], and Sekhari et al. [42] provide a method of theoretical verification to verify the effectiveness of their proposed unlearning schemes.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [42]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 3

  1. Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making AI forget you: Data deletion in machine learning. In Advances in Neural Information Processing Systems 32 , NeurIPS '19, pages 3518-3531. Curran Associates, Inc., 2019.
  2. Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. Descent-to-delete: Gradient-based methods for machine unlearning. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory , ALT '21. JMLR, Inc., 2021.
  3. Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT , 2009b.

Cited by

Sorted by citations

Related

Authors
Sekhari, A., Acharya, J., Kamath, G., & Suresh, A. T.
Affiliations
  • Cornell University (US)
  • Massachusetts Institute of Technology (US)
  • Google (United States) (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2021
Volume
34
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2103.03279
arXiv
2103.03279
OpenAlex
W3135378441
Cited by
99
References
32
Citations by year
2026: 1 · 2025: 22 · 2024: 33 · 2023: 32 · 2022: 8 · 2021: 3
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by-nc-sa/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
Keywords
machine unlearning, generalization, convex loss functions, differential privacy, computational complexity, storage complexity, model modification, privacy-utility trade-off

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review