CoChat
Sign Up
PreprintCited by 96Privacy-Preserving Technologies in DataStochastic Gradient Optimization TechniquesCloud Data Security Solutions

Descent-to-Delete: Gradient-Based Methods for Machine Unlearning

Open access
Neel, Seth, Roth, Aaron, Sharifi-Malvajerdi, Saeed·2020·arXiv
DOI 10.48550/arxiv.2007.02923arXiv 2007.02923
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

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.2007.02923

Cites

1 of 1 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?

  • The secret state approach ensures that an attacker cannot access the unlearned model after the unlearning operation, effectively hiding sensitive information in the unlearned model.

    “This effectively ensures that an attacker cannot access the unlearned model actually after the unlearning operation, which effectively hides any sensitive information in the unlearned model.”

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

    Section 2 (p. 6) says the unlearning algorithm’s secret output is not made public, but a model produced by the publishing function is publicly available. Section 1.1 (p. 3) attributes protection against membership inference to differential privacy of the published outputs, conditional on observers not seeing the secret state; it does not say the secret-state approach hides all sensitive information in the unlearned model. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • Neel et al.'s update-based unlearning method is designed to handle arbitrarily long sequences of unlearning requests with stable runtime and steady-state errors.

    “The method is designed to handle arbitrarily long sequences of unlearning requests with stable runtime and steady-state errors.”

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

  • Neel et al. [50] have proposed a protection method based on Gaussian perturbation in their unlearning scheme.

    “To counteract such attacks, Neel et al. [50] have proposed a protection method based on Gaussian perturbation in their unlearning scheme.”

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

  • The other studies [49, 50] did not provide a method for verifying the unlearning process.

    “The other studies [49, 50] did not provide a method for verifying the unlearning process.”

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

    The paper defines an indistinguishability-based unlearning guarantee (Model and Preliminaries, pp. 6–7) and proves that its algorithms satisfy it (Theorem 3.2, p. 11). Those passages do not establish whether it provides a method for verifying that an unlearning process was carried out; a search for verification and auditing found no passage that settles that point. (LLM, conf=0.69)

    Experimental — accuracy not yet measured

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: 14

  1. [AJM19] Kareem Amin, Matthew Joseph, and Jieming Mao. Pan-private uniformity testing. arXiv preprint arXiv:1911.01452 , 2019. · arXiv
  2. [BCCC + 19] Lucas Bourtoule, Varun Chandrasekaran, Christopher Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. arXiv preprint arXiv:1912.03817 , 2019. · arXiv
  3. [BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference , pages 635-658. Springer, 2016.
  4. [CY15] Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy , pages 463-480. IEEE, 2015.
  5. [CZW + 20] Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. arXiv preprint arXiv:2005.02205 , 2020. · arXiv
  6. [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference , pages 265-284. Springer, 2006.
  7. [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 715-724, 2010.
  8. [DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends R © in Theoretical Computer Science , 9(3-4):211-407, 2014.
  9. [GGHvdM19] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens van der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv:1911.03030 , 2019. · arXiv
  10. [GGVZ19] Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making AI forget you: Data deletion in machine learning. CoRR , abs/1907.05012, 2019. · arXiv
  11. [ISCZ20] Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models: Algorithms and evaluations. arXiv preprint arXiv:2002.10077 , 2020. · arXiv
  12. [MMRyA16] H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Ag¨ uera y Arcas. Federated learning of deep networks using model averaging. CoRR , abs/1602.05629, 2016. · arXiv
  13. [NRS07] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 75-84, 2007.
  14. [Vit85] Jeffrey S. Vitter. Random sampling with a reservoir. ACM Trans. Math. Softw. , 11(1):37?57, March 1985.

Cited by

Sorted by citations

Authors
Neel, S., Roth, A., & Sharifi-Malvajerdi, S.
Affiliations
University of Pennsylvania (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Pages
931-962
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2007.02923
arXiv
2007.02923
OpenAlex
W3148413297
Cited by
96
References
1
Citations by year
2026: 1 · 2025: 17 · 2024: 26 · 2023: 24 · 2022: 13 · 2021: 13 · 2020: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • Algorithmic Learning Theory
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 › Information Systems › Cloud Data Security Solutions
Keywords
machine unlearning, data deletion, convex models, gradient-based optimization, reservoir sampling, statistical indistinguishability, retraining

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