CoChat
Sign Up
PreprintCited by 70Privacy-Preserving Technologies in DataAdversarial Robustness in Machine LearningCloud Data Security Solutions

Adaptive Machine Unlearning

Open access
Gupta, Varun, Jung, Christopher, Neel, Seth, Roth, Aaron, Sharifi-Malvajerdi, Saeed, Waites, Chris·2021·arXiv
DOI 10.48550/arxiv.2106.04378arXiv 2106.04378
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

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

Cites

0 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 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 [49]

    Section C.2 (pp. 21–22) describes a method for testing an unlearning guarantee: compare outcomes after deletion with outcomes after full retraining and use confidence intervals to assess the difference. The paper uses that method to reject a perfect-unlearning guarantee for the tested SISA algorithms. This contradicts the unqualified claim that it provides no method for verifying unlearning, although the test is not a certificate for an individual deletion request. (LLM, conf=0.86)

    Checked by a reasoning model — may be wrong.

    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

The publisher hasn’t deposited this paper’s reference list.

Research works printed but not linked: 24

  1. Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. SIAM Journal on Computing , (0):STOC16-377, 2021.
  2. Lucas Bourtoule, Varun Chandrasekaran, Christopher Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In Proceedings of the 42nd IEEE Symposium on Security and Privacy , San Francisco, CA., 2021.
  3. 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.
  4. Cynthia Dwork and Vitaly Feldman. Privacy-preserving prediction. CoRR , abs/1803.10266, 2018. URL http://arxiv.org/abs/1803.10266 . · arXiv
  5. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science , 9(3-4):211-407, 2014.
  6. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages 486-503. Springer, 2006a.
  7. 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, 2006b.
  8. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science , 349(6248):636-638, 2015a.
  9. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2 , pages 2350-2358, 2015b.
  10. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 117-126, 2015c.
  11. Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Indrajit Ray, Ninghui Li, and Christopher Kruegel, editors, Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015 , pages 1322-1333. ACM, 2015. doi: 10.1145/2810103.2813677. URL https://doi.org/10.1145/2810103.2813677 . · DOI · Paper page
  12. Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making AI forget you: Data deletion in machine learning. CoRR , abs/1907.05012, 2019. URL http://arxiv.org/abs/1907.05012 . · arXiv
  13. Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. arXiv preprint arXiv:2012.13431 , 2020a. · arXiv
  14. Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In European Conference on Computer Vision , pages 383-398. Springer, 2020b.
  15. 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
  16. Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual , 2020. URL https://proceedings.neurips.cc/paper/2020/hash/ 0172d289da48c48de8c5ebf3de9f7ee1-Abstract.html .
  17. Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld. A new analysis of differential privacy's generalization guarantees. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume 151, page 31. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020.
  18. Yann Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE , pages 2278-2324, 1998.
  19. Seth Neel and Aaron Roth. Mitigating bias in adaptive data gathering via differential privacy. In International Conference on Machine Learning , pages 3720-3729. PMLR, 2018.
  20. Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory , pages 931-962. PMLR, 2021.
  21. Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Ulfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. The 35th AAAI Conference on Artificial Intelligence , 2021.
  22. Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar. Max-information, differential privacy, and post-selection hypothesis testing. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) , pages 487-494. IEEE, 2016.
  23. Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. arXiv preprint arXiv:2103.03279 , 2021. · arXiv
  24. Michael Veale, Reuben Binns, and Lilian Edwards. Algorithms that remember: Model inversion attacks and data protection law. CoRR , abs/1807.04644, 2018. URL http://arxiv.org/abs/1807.04644 . · arXiv

Cited by

Sorted by citations

Related

Authors
Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi-Malvajerdi, S., & Waites, C.
Affiliations
  • Meta (Israel) (IL)
  • University of Pennsylvania (US)
  • Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2021
Volume
34
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2106.04378
arXiv
2106.04378
OpenAlex
W3211914940
Cited by
67
References
0
Citations by year
2025: 11 · 2024: 27 · 2023: 19 · 2022: 8 · 2021: 2
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • neural information processing systems
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
  • Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
Keywords
machine unlearning, data deletion, differential privacy, privacy-preserving machine learning

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