The DOI matches its DataCite record; 38 of the 38 references it cites were found in a registry or an index.
Remember What You Want to Forget: Algorithms for Machine Unlearning
Open accessAbstract
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.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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 source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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]
Experimental — accuracy not yet measuredThe cited source says what the claim attributes to it.
In the citing paper
“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]
The cited source says what the claim attributes to it.
In the citing paper
“In addition, they proposed an evaluation parameter to measure the unlearning capacity.”
From Machine Unlearning: A Survey (2024) · cites this paper as [42]
The cited source says what the claim attributes to it.
In the citing paper
“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]
The cited source says what the claim attributes to it.
In the citing paper
“They also improved the data unlearning capacity of convex loss functions, which saw a quadratic improvement in terms of the dependence of d over differential privacy, where d is the problem dimension.”
From Machine Unlearning: A Survey (2024) · cites this paper as [42]
The cited source says what the claim attributes to it.
In the citing paper
“They produced an unlearned model by removing the contribution of some samples from an already-trained model using a disturbance update calculated based on some cheap-to-store data statistics during training.”
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.
Citations
Cites
(2005) · Springer eBooks · doi:10.1007/0-387-27255-0_9 · Cited by 20,333
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000042 · Cited by 5,557
Membership Inference Attacks Against Machine Learning Models
Shokri, R., Stronati, M., Song, C., & Shmatikov, V. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.41 · Cited by 4,754
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Understanding Machine Learning: From Theory to Algorithms
Shalev-Shwartz, S., & Ben-David, S. (2014) · doi:10.1017/cbo9781107298019 · Cited by 3,115
(2015) · Cited by 2,857
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835
Problem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,456
Incremental and Decremental Support Vector Machine Learning
Cauwenberghs, G., & Poggio, T. (2000) · Cited by 1,152
Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., & Papernot, N. (2021) · 2021 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp40001.2021.00019 · Cited by 810 · cited 4×
“Bourtoule et al. (2021) provide unlearning algorithms using a sharding-based strategy, though in a weaker unlearning model (requiring only that it be possible that the output may have arisen), and without error guarantees. Ginart et al. (2019) introduced the probabilistic notion of unlearning, inspired by differential…”
BackgroundMethodInfluentialThe Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks
Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., & Song, D. (2018) · arXiv · doi:10.48550/arxiv.1802.08232 · Cited by 629
Towards Making Systems Forget with Machine Unlearning
Cao, Y., & Yang, J. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.35 · Cited by 622 · cited 1×
“1.1 Related work Cao and Yang (2015) introduced the term “machine unlearning,” and gave efficient deterministic algorithms for exact unlearning in certain settings.”
BackgroundInfluentialEternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks
Golatkar, A., Achille, A., & Soatto, S. (2020) · 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr42600.2020.00932 · Cited by 394
Agnostic Estimation of Mean and Covariance
Lai, K. A., Rao, A. B., & Vempala, S. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.76 · Cited by 237
The Complexity of Differential Privacy
Vadhan, S. (2017) · Information security and cryptography · doi:10.1007/978-3-319-57048-8_7 · Cited by 212
Multiple Incremental Decremental Learning of Support Vector Machines
Karasuyama, M., & Takeuchi, I. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2010.2048039 · Cited by 176
Stochastic Convex Optimization.
Shalev‐Shwartz, S., Shamir, O., Srebro, N., & Sridharan, K. (2009) · Conference on Learning Theory · Cited by 169
Certified Data Removal from Machine Learning Models
Guo, C., Goldstein, T., Hannun, A., & van der Maaten, L. (2019) · arXiv · doi:10.48550/arxiv.1911.03030 · Cited by 160
Lifelong Anomaly Detection Through Unlearning
Du, M., Chen, Z., Liu, C., Oak, R., & Song, D. X. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3363226 · Cited by 131
Mixed-Privacy Forgetting in Deep Networks
Golatkar, A., Achille, A., Ravichandran, A., Polito, M., & Soatto, S. (2021) · 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr46437.2021.00085 · Cited by 125
Private Stochastic Convex Optimization with Optimal RatesPreprint
Bassily, R., Feldman, V., Talwar, K., & Thakurta, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1908.09970 · Cited by 98
Descent-to-Delete: Gradient-Based Methods for Machine Unlearning
Neel, S., Roth, A., & Sharifi-Malvajerdi, S. (2020) · arXiv · doi:10.48550/arxiv.2007.02923 · Cited by 96
Formalizing Data Deletion in the Context of the Right to Be ForgottenPreprint
Goldwasser, S., & Vasudevan, P. N. (2020) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 78
Variational Bayesian Unlearning
Nguyen, Q. P., Low, B. K. H., & Jaillet, P. (2020) · arXiv · doi:10.48550/arxiv.2010.12883 · Cited by 62
Towards Probabilistic Verification of Machine Unlearning
Sommer, D. M., Song, L., Wagh, S., & Mittal, P. (2020) · arXiv · doi:10.48550/arxiv.2003.04247 · Cited by 38
Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes BackPreprint
Feldman, V. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.04414 · Cited by 35
Incremental and Decremental Learning for Linear Support Vector Machines
Romero, E., Barrio, I., & Belanche, L. (2007) · International Conference on Artificial Neural Networks · doi:10.1007/978-3-540-74690-4_22 · Cited by 33
When Machine Unlearning Jeopardizes Privacy
Chen, M., Zhang, Z., Wang, T., Michael Backes, A., Humbert, M., & Zhang, Y. (2021) · Figshare · doi:10.60882/cispa.24613773 · Cited by 33
Machine Unlearning via Algorithmic Stability
Ullah, E., Mai, T., Rao, A., Rossi, R., & Arora, R. (2021) · arXiv · doi:10.48550/arxiv.2102.13179 · Cited by 26
Incremental and Decremental Proximal Support Vector Classification using Decay Coefficients
Tveit, A., Hetland, M. L., & Engum, H. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45228-7_42 · Cited by 19
Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations.Preprint
Izzo, Z., Smart, M. A., Chaudhuri, K., & Zou, J. (2020) · arXiv (Cornell University) · Cited by 15
Machine UnlearningPreprint
Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., & Papernot, N. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1912.03817 · Cited by 9
Formalizing Data Deletion in the Context of the Right to Be Forgotten
Garg, S., Goldwasser, S., & Vasudevan, P. N. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45724-2_13 · Cited by 8
Robust Estimators in High-Dimensions Without the Computational Intractability
Diakonikolas, I., Kamath, G., Kane, D., Li, J., Moitra, A., & Stewart, A. (2019) · SIAM Journal on Computing · doi:10.1137/17m1126680
Self-citationWhen Machine Unlearning Jeopardizes Privacy
Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., & Zhang, Y. (2020) · arXiv · doi:10.48550/arxiv.2005.02205
Mixed-Privacy Forgetting in Deep Networks
Golatkar, A., Achille, A., Ravichandran, A., Polito, M., & Soatto, S. (2020) · arXiv · doi:10.48550/arxiv.2012.13431
Convex Optimization: Algorithms and Complexity
Bubeck, S. (2014) · arXiv · doi:10.48550/arxiv.1405.4980
Research works printed but not linked: 3
- 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.
- 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.
- Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Stochastic convex optimization. In COLT , 2009b.
Cited by
Sorted by citations
Erasing Concepts from Diffusion Models
Gandikota, R., Materzyńska, J., Fiotto-Kaufman, J., & Bau, D. (2023) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv51070.2023.00230 · Cited by 361
A Survey of Machine Unlearning
Nguyên, T. T., Huynh, T. T., Ren, Z. X., Nguyen, P. L., Liew, A. W., Yin, H., & Nguyen, Q. V. H. (2025) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3749987 · Cited by 540
Fast Yet Effective Machine Unlearning
Tarun, A. K., Chundawat, V. S., Mandal, M., & Kankanhalli, M. (2023) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2023.3266233 · Cited by 203
Fast Yet Effective Machine Unlearning
Tarun, A. K., Chundawat, V. S., Mandal, M., & Kankanhalli, M. (2021) · arXiv · doi:10.48550/arxiv.2111.08947 · Cited by 190
Chundawat, V. S., Tarun, A. K., Mandal, M., & Kankanhalli, M. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2023.3265506 · Cited by 162
Metadata
- Authors
- Sekhari, A., Acharya, J., Kamath, G., & Suresh, A. T.
- Affiliations
- Cornell University (US)
- Massachusetts Institute of Technology (US)
- Google (United States) (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2021
- Volume
- 34
- ISSN
- 2331-8422 (ISSN-L)
- 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
- green
- arxiv.org
- 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 › Computer Networks and Communications › 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
