Certified minimax unlearning with generalization rates and deletion capacity
AUTHORs: 
Jiaqi Liu, Jian Lou, Zhan Qin, Kui RenAuthors Info & Claims
Article No.: 2744, Pages 62821 - 62852
Abstract
We study the problem of (ε, δ)-certified machine unlearning for minimax models. Most of the existing works focus on unlearning from standard statistical learning models that have a single variable and their unlearning steps hinge on the direct Hessian-based conventional Newton update. We develop a new (ε, δ)-certified machine unlearning algorithm for minimax models. It proposes a minimax unlearning step consisting of a total Hessian-based complete Newton update and the Gaussian mechanism borrowed from differential privacy. To obtain the unlearning certification, our method injects calibrated Gaussian noises by carefully analyzing the "sensitivity" of the minimax unlearning step (i.e., the closeness between the minimax unlearning variables and the retraining-from-scratch variables). We derive the generalization rates in terms of population strong and weak primal-dual risk for three different cases of loss functions, i.e., (strongly-)convex-(strongly-)concave losses. We also provide the deletion capacity to guarantee that a desired population risk can be maintained as long as the number of deleted samples does not exceed the derived amount. With training samples n and model dimension d, it yields the order O(n/d1/4), which shows a strict gap over the baseline method of differentially private minimax learning that has O(n/d1/2). In addition, our rates of generalization and deletion capacity match the state-of-the-art results derived previously for standard statistical learning models.
References
[1]
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, volume 70, pages 214-223. PMLR, 2017.
[2]
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, volume 32, pages 11279-11288, 2019.
[3]
Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap. In Conference on Learning Theory, volume 195, pages 2482-2508. PMLR, 2023.
[4]
Digvijay Boob and Cristóbal Guzmán. Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. Mathematical Programming, pages 1-43, 2023.
[5]
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy, pages 141-159. IEEE, 2021.
[6]
Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In International Conference on Machine Learning, volume 139, pages 1092-1104. PMLR, 2021.
[7]
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.
[8]
Chong Chen, Fei Sun, Min Zhang, and Bolin Ding. Recommendation unlearning. In Proceedings of the ACM Web Conference 2022, pages 2768-2777. ACM, 2022a.
[9]
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. Graph unlearning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 499-513. ACM, 2022b.
[10]
Min Chen, Weizhuo Gao, Gaoyang Liu, Kai Peng, and Chen Wang. Boundary unlearning: Rapid forgetting of deep networks via shifting the decision boundary. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7766-7775. IEEE, 2023.
[11]
Jiali Cheng, George Dasoulas, Huan He, Chirag Agarwal, and Marinka Zitnik. Gnndelete: A general strategy for unlearning in graph neural networks. In The Eleventh International Conference on Learning Representations. OpenReview.net, 2023.
[12]
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations. OpenReview.net, 2023a.
[13]
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. In The Eleventh International Conference on Learning Representations. OpenReview.net, 2023b.
[14]
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference on Machine Learning, volume 80, pages 1125-1134. PMLR, 2018.
[15]
Jimmy Z. Di, Jack Douglas, Jayadev Acharya, Gautam Kamath, and Ayush Sekhari. Hidden poison: Machine unlearning enables camouflaged poisoning attacks. In Advances in Neural Information Processing Systems, volume 37, 2023.
[16]
Simon S Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, volume 70, pages 1049-1058. PMLR, 2017.
[17]
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Third Theory of Cryptography Conference, volume 3876, pages 265-284. Springer, 2006.
[18]
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9:211-407, 2014.
[19]
Farzan Farnia and Asuman Ozdaglar. Train simultaneously, generalize better: Stability of gradient-based minimax learners. In International Conference on Machine Learning, volume 139, pages 3174-3185. PMLR, 2021.
[20]
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, and Chiyuan Zhang. Ticketed learning-unlearning schemes. In The Thirty Sixth Annual Conference on Learning Theory, pages 5110-5139. PMLR, 2023.
[21]
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, volume 32, pages 3513-3526, 2019.
[22]
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9304-9312, 2020a.
[23]
Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. In Computer Vision-ECCV 2020: 16th European Conference, volume 12374, pages 383-398. Springer, 2020b.
[24]
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 792-801. IEEE, 2021.
[25]
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, volume 27, pages 2672-2680, 2014.
[26]
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516-11524. AAAI Press, 2021.
[27]
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, volume 119, pages 3832-3842. PMLR, 2020.
[28]
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, volume 130, pages 2008-2016. PMLR, 2021.
[29]
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, volume 70, pages 1885-1894. PMLR, 2017.
[30]
Yunwen Lei, Zhenhuan Yang, Tianbao Yang, and Yiming Ying. Stability and generalization of stochastic gradient methods for minimax problems. In International Conference on Machine Learning, volume 139, pages 6175-6186. PMLR, 2021.
[31]
Yuantong Li, Chi-Hua Wang, and Guang Cheng. Online forgetting process for linear regression models. In International Conference on Artificial Intelligence and Statistics, pages 217-225. PMLR, 2021.
[32]
Shen Lin, Xiaoyu Zhang, Chenyang Chen, Xiaofeng Chen, and Willy Susilo. Erm-ktp: Knowledgelevel machine unlearning via knowledge transfer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 20147-20155, 2023.
[33]
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In International Conference on Machine Learning, volume 119, pages 6083-6093. PMLR, 2020.
[34]
Junxu Liu, Mingsheng Xue, Jian Lou, Xiaoyu Zhang, Li Xiong, and Zhan Qin. Muter: Machine unlearning on adversarially trained models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4892-4902, 2023.
[35]
Luo Luo, Yujun Li, and Cheng Chen. Finding second-order stationary points in nonconvex-strongly-concave minimax optimization. In Advances in Neural Information Processing Systems, volume 35, pages 36667-36679, 2022.
[36]
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In The Sixth International Conference on Learning Representations. OpenReview.net, 2018.
[37]
Ananth Mahadevan and Michael Mathioudakis. Certifiable machine unlearning for linear models. arXiv preprint arXiv:2106.15093, 2021.
[38]
Alessandro Mantelero. The eu proposal for a general data protection regulation and the roots of the 'right to be forgotten'. Computer Law & Security Review, 29(3):229-235, 2013.
[39]
Ronak Mehta, Sourav Pal, Vikas Singh, and Sathya N Ravi. Deep unlearning via randomized conditionally independent hessians. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10422-10431. IEEE, 2022.
[40]
Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, volume 132, pages 931-962. PMLR, 2021.
[41]
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
[42]
Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational bayesian unlearning. In Advances in Neural Information Processing Systems, volume 33, pages 16025-16036, 2020.
[43]
Asuman E. Ozdaglar, Sarath Pattathil, Jiawei Zhang, and Kaiqing Zhang. What is a good metric to study generalization of minimax learners? In Advances in Neural Information Processing Systems, volume 35, pages 38190-38203, 2022.
[44]
Alexandra Peste, Dan Alistarh, and Christoph H Lampert. SSSE: efficiently erasing samples from trained machine learning models. arXiv preprint arXiv:2107.03860, 2021.
[45]
Sebastian Schelter, Stefan Grafberger, and Ted Dunning. Hedgecut: Maintaining randomised trees for low-latency machine unlearning. In International Conference on Management of Data, pages 1545-1557. ACM, 2021.
[46]
Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In Advances in Neural Information Processing Systems, volume 34, pages 18075-18086, 2021.
[47]
Pranay Sharma, Rohan Panda, Gauri Joshi, and Pramod Varshney. Federated minimax optimization: Improved convergence analyses and algorithms. In International Conference on Machine Learning, volume 162, pages 19683-19730. PMLR, 2022.
[48]
Takashi Shibata, Go Irie, Daiki Ikami, and Yu Mitsuzumi. Learning with selective forgetting. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 989-996. ijcai.org, 2021.
[49]
Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. In The Sixth International Conference on Learning Representations. OpenReview.net, 2018.
[50]
Vinith Suriyakumar and Ashia C Wilson. Algorithms that approximate data removal: New results and limitations. In Advances in Neural Information Processing Systems, volume 35, pages 18892-18903, 2022.
[51]
Ayush K Tarun, Vikram S Chundawat, Murari Mandal, and Mohan Kankanhalli. Fast yet effective machine unlearning. IEEE Transactions on Neural Networks and Learning Systems, 2023.
[52]
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. In Advances in Neural Information Processing Systems, volume 32, pages 12659-12670, 2019.
[53]
Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. Machine unlearning via algorithmic stability. In Conference on Learning Theory, volume 134, pages 4126-4142. PMLR, 2021.
[54]
Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 347-450, 2017.
[55]
Cheng-Long Wang, Mengdi Huai, and Di Wang. Inductive graph unlearning. In 32nd USENIX Security Symposium, pages 3205-3222. USENIX Association, 2023a.
[56]
Weiqi Wang, Zhiyi Tian, Chenhan Zhang, An Liu, and Shui Yu. Bfu: Bayesian federated unlearning with parameter self-sharing. In Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security, pages 567-578. ACM, 2023b.
[57]
Alexander Warnecke, Lukas Pirch, Christian Wressnegger, and Konrad Rieck. Machine unlearning of features and labels. In 30th Annual Network and Distributed System Security Symposium. The Internet Society, 2023.
[58]
Ga Wu, Masoud Hashemi, and Christopher Srinivasa. Puma: Performance unchanged model augmentation for training data removal. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8675-8682, 2022.
[59]
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning, volume 119, pages 10355-10366. PMLR, 2020.
[60]
Zhaomin Wu, Junhui Zhu, Qinbin Li, and Bingsheng He. Deltaboost: Gradient boosting decision trees with efficient machine unlearning. Proceedings of the ACM on Management of Data, 1(2): 1-26, 2023.
[61]
Haocheng Xia, Jinfei Liu, Jian Lou, Zhan Qin, Kui Ren, Yang Cao, and Li Xiong. Equitable data valuation meets the right to be forgotten in model markets. Proceedings of the VLDB Endowment, 16(11):3349-3362, 2023.
[62]
Haonan Yan, Xiaoguang Li, Ziyao Guo, Hui Li, Fenghua Li, and Xiaodong Lin. Arcane: An efficient architecture for exact machine unlearning. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, pages 4006-4013. ijcai.org, 2022.
[63]
Zhenhuan Yang, Shu Hu, Yunwen Lei, Kush R Vashney, Siwei Lyu, and Yiming Ying. Differentially private sgda for minimax problems. In Uncertainty in Artificial Intelligence, volume 180, pages 2192-2202. PMLR, 2022.
[64]
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax optimization. arXiv preprint arXiv:2006.14592, 2020.
[65]
Junyu Zhang, Mingyi Hong, Mengdi Wang, and Shuzhong Zhang. Generalization bounds for stochastic saddle point problems. In International Conference on Artificial Intelligence and Statistics, volume 130, pages 568-576. PMLR, 2021.
[66]
Liang Zhang, Kiran K Thekumparampil, Sewoong Oh, and Niao He. Bring your own algorithm for optimal differentially private stochastic minimax optimization. In Advances in Neural Information Processing Systems, volume 35, pages 35174-35187, 2022a.
[67]
Shuijing Zhang, Jian Lou, Li Xiong, Xiaoyu Zhang, and Jing Liu. Closed-form machine unlearning for matrix factorization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pages 3278-3287, 2023.
[68]
Siqi Zhang, Yifan Hu, Liang Zhang, and Niao He. Uniform convergence and generalization for nonconvex stochastic minimax problems. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022b.
[69]
Zijie Zhang, Yang Zhou, Xin Zhao, Tianshi Che, and Lingjuan Lyu. Prompt certified machine unlearning with randomized gradient smoothing and quantization. In Advances in Neural Information Processing Systems, volume 35, pages 13433-13455, 2022c.
Recommendations
IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks
KDD '24: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data MiningGraph Neural Networks (GNNs) have been increasingly deployed in a plethora of applications. However, the graph data used for training may contain sensitive personal information of the involved individuals. Once trained, GNNs typically encode such ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 Neural Information Processing Systems Foundation, Inc.
Publisher
Curran Associates Inc.
Red Hook, NY, United States
Publication History
Published: 30 May 2024
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Nov 2024