Machine Unlearning via Algorithmic Stability
Open accessAbstract
We study the problem of machine unlearning and identify a notion of algorithmic stability, Total Variation (TV) stability, which we argue, is suitable for the goal of exact unlearning. For convex risk minimization problems, we design TV-stable algorithms based on noisy Stochastic Gradient Descent (SGD). Our key contribution is the design of corresponding efficient unlearning algorithms, which are based on constructing a (maximal) coupling of Markov chains for the noisy SGD procedure. To understand the trade-offs between accuracy and unlearning efficiency, we give upper and lower bounds on excess empirical and populations risk of TV stable algorithms for convex risk minimization. Our techniques generalize to arbitrary non-convex functions, and our algorithms are differentially private as well.
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
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?
When users revoke permissions over training data, merely removing those data from the original training dataset is not sufficient because attackers can still reveal user information from trained models.
“When users revoke permissions over some training data, it is not sufficient to merely remove those data from the original training dataset, since the attackers can still reveal user information from the trained models [28].”
From Machine Unlearning: A Survey (2024) · cites this paper as [28]
The Introduction (p. 3) says that merely deleting user data from a database without undoing computations derived from it is insufficient, and applies this concern to trained machine-learning models. It frames this as a reasonable expectation, however, and does not say that attackers can reveal user information from a trained model after the data is removed. The adversary discussion in §4.2 (p. 11) concerns disclosure of algorithmic state, not that specific claim. (LLM, conf=0.84)
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
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 · see citing works
Deep Learning with Differential Privacy
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978318 · Cited by 6,578 · see citing works
On Measures of Entropy and Information
Rényi, A. (1961) · Project Euclid (Cornell University) · Cited by 4,031 · see citing works
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856 · see citing works
Rényi Divergence and Kullback-Leibler Divergence
van Erven, T., & Peter Harremöes, D. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2320500 · Cited by 1,553 · see citing works
Problem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,454 · see citing works
Mironov, I. (2017) · 2017 IEEE 30th Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2017.11 · Cited by 1,255 · see citing works
High-Dimensional Probability: An Introduction with Applications in Data Science
Vershynin, R. (2018) · Cited by 1,031 · see citing works
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
Bassily, R., Smith, A., & Thakurta, A. (2014) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.56 · Cited by 645 · see citing works
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 · see citing works
An Efficient Method for Generating Discrete Random Variables with General Distributions
Walker, A. J. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355749 · Cited by 607 · see citing works
An optimal method for stochastic composite optimization
Lan, G. (2012) · Mathematical Programming · doi:10.1007/s10107-010-0434-y · Cited by 427 · see citing works
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 · see citing works
Algorithmic stability for adaptive data analysis
Bassily, R., Kobbi Nissim, B., Smith, A., Steinke, T., Stemmer, U., & Ullman, J. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897566 · Cited by 154 · see citing works
Privacy Amplification by Subsampling: Tight Analyses via Couplings and DivergencesPreprint
Balle, B., Barthe, G., & Gaboardi, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.01647 · Cited by 154 · see citing works
Coupling of Multidimensional Diffusions by Reflection
Lindvall, T., & Rogers, L. C. G. (1986) · The Annals of Probability · doi:10.1214/aop/1176992442 · Cited by 153 · see citing works
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 · see citing works
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 83 · see citing works
The total variation distance between high-dimensional GaussiansPreprint
Devroye, L., Mehrabian, A., & Reddad, T. (2018) · arXiv (Cornell University) · Cited by 74 · see citing works
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDPreprint
Allen-Zhu, Z. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.02982 · Cited by 42 · see citing works
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 · see citing works
MEXIT: Maximal un-coupling times for stochastic processes
Ernst, P., Kendall, W. S., Roberts, G. O., & Rosenthal, J. S. (2018) · Stochastic Processes and their Applications · doi:10.1016/j.spa.2018.03.001 · Cited by 8 · see citing works
On maximal agreement couplingsPreprint
Völlering, F. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.01511 · Cited by 1 · see citing works
Flagged first, then by citations
3 of the 26 references couldn’t be matched to a known paper.
Research works printed but not linked: 7
- [AZ17] Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. The Journal of Machine Learning Research , 18(1):8194-8244, 2017.
- [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
- [BE02] Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research , 2(Mar):499-526, 2002.
- [Chu91] Alexander Mikhailovich Chudnov. Game-theoretical problems of synthesis of signal generation and reception algorithms. Problemy Peredachi Informatsii , 27(3):57-65, 1991.
- [GGVZ19] 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 , pages 3518-3531, 2019.
- [Vil08] Cédric Villani. Optimal transport: old and new , volume 338. Springer Science & Business Media, 2008.
- [WS16] Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 29. Curran Associates, Inc., 2016.
Cited by
Sorted by citations
Xu, H., Zhu, T., Zhang, L., Zhou, W., & Yu, P. S. (2024) · ACM Computing Surveys · doi:10.1145/3603620 · Cited by 164 · see citing works
Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks Using an Incompetent Teacher
Chundawat, V. S., Tarun, A. K., Mandal, M., & Kankanhalli, M. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i6.25879 · Cited by 129 · see citing works
Remember What You Want to Forget: Algorithms for Machine Unlearning
Sekhari, A., Acharya, J., Kamath, G., & Suresh, A. T. (2021) · arXiv · doi:10.48550/arxiv.2103.03279 · Cited by 99 · see citing works
A Comprehensive Survey of Forgetting in Deep Learning Beyond Continual Learning
Wang, Z., Yang, E., Shen, L., & Huang, H. (2024) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2024.3498346 · Cited by 101 · see citing works
A Survey of Machine Unlearning
Nguyen, T. T., Huynh, T. T., Ren, Z., Nguyen, P. L., Liew, A. W.-C., Yin, H., & Nguyen, Q. V. H. (2022) · arXiv · doi:10.48550/arxiv.2209.02299 · Cited by 193 · see citing works
“Differential privacy [62] ✗ ✓ – – – ✓ ✓ – ✓ ✓ – ✓ ✗ ✗ ✗ ✓ Certified removal [55, 59, 109, 156] – ✓ ✗ ✗ – – ✓ ✓ ✓ ✓ – ✓ ✗ ✗ ✗ ✓ Statistical query learning [13] – ✓ ✗ – ✗ ✓ ✓ – ✓ – – ✓ ✗ ✗ ✗ – Decremental learning [24, 52] ✗ – ✗ – – ✗ ✓ ✓ – – – ✓ ✗ ✗ ✗ ✗ Knowledge adaptation [26] ✗ ✓ – – – – – – ✗ ✗ – ✓ – – – – Paramete…”
InfluentialGIF: A General Graph Unlearning Strategy via Influence Function
Wu, J., Yang, Y., Qian, Y., Sui, Y., Wang, X., & He, X. (2023) · International World Wide Web Conference (WWW) · doi:10.1145/3543507.3583521 · Cited by 58 · see citing works
On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning
Thudi, A., Jia, H., Shumailov, I., & Papernot, N. (2021) · arXiv · doi:10.48550/arxiv.2110.11891 · Cited by 48 · see citing works
Machine Unlearning: Taxonomy, Metrics, Applications, Challenges, and Prospects
Li, N., Zhou, C., Gao, Y., Chen, H., Zhang, Z., Kuang, B., & Fu, A. (2025) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2025.3530988 · Cited by 53 · see citing works
Exact-Fun: An Exact and Efficient Federated Unlearning Approach
Xiong, Z., Li, W., Li, Y., & Cai, Z. (2023) · Proceedings · doi:10.1109/icdm58522.2023.00188 · Cited by 33 · see citing works
Feature-Based Machine Unlearning for Vertical Federated Learning in IoT Networks
Pan, Z., Ying, Z., Wang, Y., Zhang, C., Zhang, W., Zhou, W., & Zhu, L. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3530529 · Cited by 30 · see citing works
SAFE: Machine Unlearning With Shard Graphs
Dukler, Y., Bowman, B., Achille, A., Golatkar, A., Swaminathan, A. D., & Soatto, S. (2023) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv51070.2023.01569 · Cited by 15 · see citing works
On the Effectiveness of Unlearning in Session-Based Recommendation
Xin, X., Yang, L., Zhao, Z., Ren, P., Chen, Z., Ma, J., & Ren, Z. (2024) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3616855.3635823 · Cited by 14 · see citing works
Goldfish: An Efficient Federated Unlearning Framework
Wang, H., Zhu, X., Chen, C., & Verı́ssimo, P. (2024) · International Conference on Dependable Systems & Networks/Proceedings · doi:10.1109/dsn58291.2024.00035 · Cited by 12 · see citing works
Machine unlearning in brain-inspired neural network paradigms
Wang, C., Ying, Z., & Pan, Z. (2024) · Frontiers in Neurorobotics · doi:10.3389/fnbot.2024.1361577 · Cited by 8 · see citing works
High-probability generalization bounds for pointwise uniformly stable algorithms
Fan, J., & Lei, Y. (2024) · Applied and Computational Harmonic Analysis · doi:10.1016/j.acha.2024.101632 · Cited by 7 · see citing works
Appro-Fun: Approximate Machine Unlearning in Federated Setting
Xiong, Z., Li, W., & Cai, Z. (2024) · International Conference on Computer Communications and Networks (ICCCN) · doi:10.1109/icccn61486.2024.10637564 · Cited by 7 · see citing works
TruVRF: Toward Triple-Granularity Verification on Machine Unlearning
Zhou, C., Gao, Y., Fu, A., Chen, K., Zhang, Z., Xue, M., Dai, Z., Ji, S., & Zhang, Y. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3565991 · Cited by 7 · see citing works
Data Redaction from Pre-trained GANs
Kong, Z., & Chaudhuri, K. (2023) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml54575.2023.00048 · Cited by 6 · see citing works
Fuzzy rough unlearning model for feature selection
Tang, Y., Zhao, S., Chen, H., Li, C., Zhai, J., & Zhou, Q. (2023) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2023.109102 · Cited by 6 · see citing works
Data Redaction from Conditional Generative Models
Kong, Z., & Chaudhuri, K. (2024) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml59370.2024.00035 · Cited by 4 · see citing works
A Decision-Making Process to Implement the ‘Right to Be Forgotten’ in Machine Learning
Hawkins, K., Alhuwaish, N., Belguith, S., Vranaki, A., & Charlesworth, A. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-61089-9_2 · Cited by 5 · see citing works
Toward Highly-Efficient and Accurate Services QoS Prediction via Machine Unlearning
Zeng, Y., Xu, J., Li, Y., Chen, C., Dai, Q., & Du, Z. (2023) · IEEE Access · doi:10.1109/access.2023.3291410 · Cited by 4 · see citing works
Approximate Data Deletion in Generative Models
Kong, Z., & Alfeld, S. (2023) · Frontiers in artificial intelligence and applications · doi:10.3233/faia230407 · Cited by 5 · see citing works
Human-inspired Perspectives: A Survey on AI Long-term Memory
He, Z., Lin, W., Zheng, H., Zhang, F., Jones, M. W., Aitchison, L., Xu, X., Liu, M., Kristensson, P. O., & Shen, J. (2024) · arXiv · doi:10.48550/arxiv.2411.00489 · Cited by 3 · see citing works
Ensuring User Privacy and Model Security via Machine Unlearning: A Review
Tang, Y., Cai, Z., Liu, Q., Zhou, T., & Ni, Q. (2023) · Computers, materials & continua/Computers, materials & continua (Print) · doi:10.32604/cmc.2023.032307 · Cited by 3 · see citing works
Ranjan, S., Mishra, D., & Singh, S. K. (2025) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbbio.2025.3571046 · Cited by 2 · see citing works
Ievlev, P., & Shashkov, T. (2026) · Probability and Mathematical Statistics · doi:10.37190/0208-4147.00308 · Cited by 2 · see citing works
On the Reliability of Membership Inference Attacks
Chowdhury, A. R., Kong, Z., & Chaudhuri, K. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00036 · Cited by 1 · see citing works
Ensuring Privacy and Security in Machine Learning
Velammal, & Aarthy, N. (2024) · Advances in computational intelligence and robotics book series · doi:10.4018/979-8-3693-2964-1.ch009
- Authors
- Ullah, E., Mai, T., Rao, A., Rossi, R., & Arora, R.
- Affiliations
- Johns Hopkins University (US)
- Adobe Systems (United States) (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2021
- Pages
- 4126-4142
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2102.13179
- OpenAlex
- W3134127610
- Cited by
- 26
- References
- 26
- Citations by year
- 2026: 1 · 2025: 5 · 2024: 9 · 2023: 9 · 2021: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Conference on Learning Theory
- Funders
- National Science Foundation (CAREER, 1943251, 1838139)
- 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 › Machine Learning and Data Classification
- Keywords
- machine unlearning, algorithm stability, Markov chain coupling, excess risk bounds, non-convex optimization, differential privacy
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
