{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T15:36:03Z","timestamp":1771515363521,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>We study federated unlearning, a novel problem to eliminate the impact of specific clients or data points on the global model learned via federated learning (FL). This problem is driven by the right to be forgotten and the privacy challenges in FL. We introduce a new framework for exact federated unlearning that meets two essential criteria:<jats:italic>communication efficiency<\/jats:italic>and<jats:italic>exact unlearning provability.<\/jats:italic>To our knowledge, this is the first work to tackle both aspects coherently. We start by giving a rigorous definition of<jats:italic>exact<\/jats:italic>federated unlearning, which guarantees that the unlearned model is statistically indistinguishable from the one trained without the deleted data. We then pinpoint the key property that enables fast exact federated unlearning: total variation (TV) stability, which measures the sensitivity of the model parameters to slight changes in the dataset. Leveraging this insight, we develop a TV-stable FL algorithm called FATS, which modifies the classical FedAvg algorithm for TV Stability and employs local SGD with periodic averaging to lower the communication round. We also design efficient unlearning algorithms for FATS under two settings: client-level and sample-level unlearning. We provide theoretical guarantees for our learning and unlearning algorithms, proving that they achieve exact federated unlearning with reasonable convergence rates for both the original and unlearned models. We empirically validate our framework on 6 benchmark datasets, and show its superiority over state-of-the-art methods in terms of accuracy, communication cost, computation cost, and unlearning efficacy.<\/jats:p>","DOI":"10.14778\/3641204.3641220","type":"journal-article","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T22:05:43Z","timestamp":1714687543000},"page":"1119-1131","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Communication Efficient and Provable Federated Unlearning"],"prefix":"10.14778","volume":"17","author":[{"given":"Youming","family":"Tao","sequence":"first","affiliation":[{"name":"Shandong University, P.R. China"}]},{"given":"Cheng-Long","family":"Wang","sequence":"additional","affiliation":[{"name":"KAUST, Saudi Arabia"}]},{"given":"Miao","family":"Pan","sequence":"additional","affiliation":[{"name":"University of Houston, U.S.A."}]},{"given":"Dongxiao","family":"Yu","sequence":"additional","affiliation":[{"name":"Shandong University, P.R. China"}]},{"given":"Xiuzhen","family":"Cheng","sequence":"additional","affiliation":[{"name":"Shandong University, P.R. China"}]},{"given":"Di","family":"Wang","sequence":"additional","affiliation":[{"name":"KAUST, Saudi Arabia"}]}],"member":"320","published-online":{"date-parts":[[2024,5,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Titouan Parcollet, Pedro Porto Buarque de Gusm\u00e3o, et al.","author":"Beutel Daniel J","year":"2020","unstructured":"Daniel J Beutel, Taner Topal, Akhil Mathur, Xinchi Qiu, Javier Fernandez-Marques, Yan Gao, Lorenzo Sani, Kwing Hei Li, Titouan Parcollet, Pedro Porto Buarque de Gusm\u00e3o, et al. 2020. Flower: A friendly federated learning research framework. arXiv preprint arXiv:2007.14390 (2020)."},{"key":"e_1_2_1_2_1","volume-title":"42nd IEEE Symposium on Security and Privacy (SP","author":"Bourtoule Lucas","year":"2021","unstructured":"Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. 2021. Machine unlearning. In 42nd IEEE Symposium on Security and Privacy (SP 2021). IEEE, 141--159."},{"key":"e_1_2_1_3_1","volume-title":"Peter Wu, Tian Li, Jakub Kone\u010dn\u00fd, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar.","author":"Caldas Sebastian","year":"2018","unstructured":"Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Kone\u010dn\u00fd, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. 2018. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01097 (2018)."},{"key":"e_1_2_1_4_1","volume-title":"36th IEEE Symposium on Security and Privacy (SP","author":"Cao Yinzhi","year":"2015","unstructured":"Yinzhi Cao and Junfeng Yang. 2015. Towards making systems forget with machine unlearning. In 36th IEEE Symposium on Security and Privacy (SP 2015). IEEE, 463--480."},{"key":"e_1_2_1_5_1","volume-title":"29th ACM SIGSAC Conference on Computer and Communications Security (CCS","author":"Chen Min","year":"2022","unstructured":"Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. 2022. Graph unlearning. In 29th ACM SIGSAC Conference on Computer and Communications Security (CCS 2022). 499--513."},{"key":"e_1_2_1_6_1","volume-title":"3rd Theory of Cryptography Conference (TCC","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In 3rd Theory of Cryptography Conference (TCC 2006). Springer, 265--284."},{"key":"e_1_2_1_7_1","volume-title":"Sequential Informed Federated Unlearning: Efficient and Provable Client Unlearning in Federated Optimization. arXiv preprint arXiv:2211.11656","author":"Fraboni Yann","year":"2022","unstructured":"Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. 2022. Sequential Informed Federated Unlearning: Efficient and Provable Client Unlearning in Federated Optimization. arXiv preprint arXiv:2211.11656 (2022)."},{"key":"e_1_2_1_8_1","unstructured":"Antonio Ginart Melody Guan Gregory Valiant and James Y Zou. 2019. Making ai forget you: Data deletion in machine learning. 3513--3526 pages."},{"key":"e_1_2_1_9_1","volume-title":"37th International Conference on Machine Learning (ICML","author":"Guo Chuan","year":"2020","unstructured":"Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. 2020. Certified data removal from machine learning models. In 37th International Conference on Machine Learning (ICML 2020). 3832--3842."},{"key":"e_1_2_1_10_1","volume-title":"Federated Unlearning: How to Efficiently Erase a Client in FL? arXiv preprint arXiv:2207.05521","author":"Halimi Anisa","year":"2022","unstructured":"Anisa Halimi, Swanand Kadhe, Ambrish Rawat, and Nathalie Baracaldo. 2022. Federated Unlearning: How to Efficiently Erase a Client in FL? arXiv preprint arXiv:2207.05521 (2022)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"234","DOI":"10.69554\/TCFN5165","article-title":"Understanding the scope and impact of the california consumer privacy act of 2018","volume":"2","author":"Harding Elizabeth Liz","year":"2019","unstructured":"Elizabeth Liz Harding, Jarno J Vanto, Reece Clark, L Hannah Ji, and Sara C Ainsworth. 2019. Understanding the scope and impact of the california consumer privacy act of 2018. Journal of Data Protection & Privacy 2, 3 (2019), 234--253.","journal-title":"Journal of Data Protection & Privacy"},{"key":"e_1_2_1_12_1","volume-title":"Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335","author":"Harry Hsu Tzu-Ming","year":"2019","unstructured":"Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. 2019. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335 (2019)."},{"key":"e_1_2_1_13_1","volume-title":"Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al.","author":"Kairouz Peter","year":"2021","unstructured":"Peter Kairouz, H Brendan McMahan, Brendan Avent, Aur\u00e9lien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. 2021. Advances and open problems in federated learning. Foundations and Trends\u00ae in Machine Learning 14, 1--2 (2021), 1--210."},{"key":"e_1_2_1_14_1","volume-title":"Learning multiple layers of features from tiny images. Master's thesis","author":"Krizhevsky Alex","unstructured":"Alex Krizhevsky. 2009. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto (2009)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"2278","DOI":"10.1109\/5.726791","article-title":"Gradient-based learning applied to document recognition","volume":"86","author":"LeCun Yann","year":"1998","unstructured":"Yann LeCun, L\u00e9on Bottou, Yoshua Bengio, and Patrick Haffner. 1998. Gradient-based learning applied to document recognition. Proc. IEEE 86, 11 (1998), 2278--2324.","journal-title":"Proc. IEEE"},{"key":"e_1_2_1_16_1","volume-title":"29th IEEE\/ACM International Symposium on Quality of Service (IWQOS","author":"Liu Gaoyang","year":"2021","unstructured":"Gaoyang Liu, Xiaoqiang Ma, Yang Yang, Chen Wang, and Jiangchuan Liu. 2021. FedEraser: Enabling efficient client-level data removal from federated learning models. In 29th IEEE\/ACM International Symposium on Quality of Service (IWQOS 2021). IEEE, 1--10."},{"key":"e_1_2_1_17_1","volume-title":"41st IEEE International Conference on Computer Communications (INFOCOM","author":"Liu Yi","year":"2022","unstructured":"Yi Liu, Lei Xu, Xingliang Yuan, Cong Wang, and Bo Li. 2022. The right to be forgotten in federated learning: An efficient realization with rapid retraining. In 41st IEEE International Conference on Computer Communications (INFOCOM 2022). IEEE, 1749--1758."},{"key":"e_1_2_1_18_1","volume-title":"20th International Conference on Artificial Intelligence and Statistics (AISTATS","author":"McMahan Brendan","year":"2017","unstructured":"Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017. Communication-efficient learning of deep networks from decentralized data. In 20th International Conference on Artificial Intelligence and Statistics (AISTATS 2017). PMLR, 1273--1282."},{"key":"e_1_2_1_19_1","volume-title":"32nd International Conference on Algorithmic Learning Theory (ALT","author":"Neel Seth","year":"2021","unstructured":"Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. 2021. Descent-to-delete: Gradient-based methods for machine unlearning. In 32nd International Conference on Algorithmic Learning Theory (ALT 2021). PMLR, 931--962."},{"key":"e_1_2_1_20_1","volume-title":"Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoc Viet Hung Nguyen.","author":"Nguyen Thanh Tam","year":"2022","unstructured":"Thanh Tam Nguyen, Thanh Trung Huynh, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoc Viet Hung Nguyen. 2022. A survey of machine unlearning. arXiv preprint arXiv:2209.02299 (2022)."},{"key":"e_1_2_1_21_1","volume-title":"35th Annual Conference on Neural Information Processing Systems (NeurIPS 2021). 1807","author":"Sekhari Ayush","year":"2021","unstructured":"Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. 2021. Remember what you want to forget: Algorithms for machine unlearning. In 35th Annual Conference on Neural Information Processing Systems (NeurIPS 2021). 18075--18086."},{"key":"e_1_2_1_22_1","volume-title":"Membership Inference Attacks Against Machine Learning Models. In 38th IEEE Symposium on Security and Privacy (SP","author":"Shokri Reza","year":"2017","unstructured":"Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. 2017. Membership Inference Attacks Against Machine Learning Models. In 38th IEEE Symposium on Security and Privacy (SP 2017). IEEE Computer Society, 3--18."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"2430","DOI":"10.1109\/JSAC.2020.3000372","article-title":"Analyzing user-level privacy attack against federated learning","volume":"38","author":"Song Mengkai","year":"2020","unstructured":"Mengkai Song, Zhibo Wang, Zhifei Zhang, Yang Song, Qian Wang, Ju Ren, and Hairong Qi. 2020. Analyzing user-level privacy attack against federated learning. IEEE Journal on Selected Areas in Communications 38, 10 (2020), 2430--2444.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"e_1_2_1_24_1","volume-title":"7th IEEE European Symposium on Security and Privacy (EuroS&P","author":"Thudi Anvith","year":"2022","unstructured":"Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot. 2022. Unrolling sgd: Understanding factors influencing machine unlearning. In 7th IEEE European Symposium on Security and Privacy (EuroS&P 2022). IEEE, 303--319."},{"key":"e_1_2_1_25_1","volume-title":"32nd International Conference on Algorithmic Learning Theory (ALT","author":"Ullah Enayat","year":"2021","unstructured":"Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora. 2021. Machine unlearning via algorithmic stability. In 32nd International Conference on Algorithmic Learning Theory (ALT 2021). PMLR, 4126--4142."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-57959-7","volume-title":"The eu general data protection regulation (gdpr). A Practical Guide","author":"Voigt Paul","year":"2017","unstructured":"Paul Voigt and Axel Von dem Bussche. 2017. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing 10, 3152676 (2017), 10--5555.","edition":"1"},{"key":"e_1_2_1_27_1","volume-title":"Inductive Graph Unlearning. In 32nd USENIX Security Symposium (USENIX Security","author":"Wang Cheng-Long","year":"2023","unstructured":"Cheng-Long Wang, Mengdi Huai, and Di Wang. 2023. Inductive Graph Unlearning. In 32nd USENIX Security Symposium (USENIX Security 2023). 3205--3222."},{"key":"e_1_2_1_28_1","volume-title":"31st ACM Web Conference (WWW","author":"Wang Junxiao","year":"2022","unstructured":"Junxiao Wang, Song Guo, Xin Xie, and Heng Qi. 2022. Federated unlearning via class-discriminative pruning. In 31st ACM Web Conference (WWW 2022. 622--632."},{"key":"e_1_2_1_29_1","volume-title":"38th IEEE International Conference on Computer Communications (INFOCOM","author":"Wang Zhibo","year":"2019","unstructured":"Zhibo Wang, Mengkai Song, Zhifei Zhang, Yang Song, Qian Wang, and Hairong Qi. 2019. Beyond inferring class representatives: User-level privacy leakage from federated learning. In 38th IEEE International Conference on Computer Communications (INFOCOM 2019). IEEE, 2512--2520."},{"key":"e_1_2_1_30_1","volume-title":"Federated unlearning with knowledge distillation. arXiv preprint arXiv:2201.09441","author":"Wu Chen","year":"2022","unstructured":"Chen Wu, Sencun Zhu, and Prasenjit Mitra. 2022. Federated unlearning with knowledge distillation. arXiv preprint arXiv:2201.09441 (2022)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.001.2200198"},{"key":"e_1_2_1_32_1","volume-title":"Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747","author":"Xiao Han","year":"2017","unstructured":"Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747 (2017)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455610"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3641204.3641220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T23:15:44Z","timestamp":1731885344000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3641204.3641220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":33,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.14778\/3641204.3641220"],"URL":"https:\/\/doi.org\/10.14778\/3641204.3641220","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"2024-05-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}