Faster exact unlearning for federated learning without gradient sharing
Efficient Exact Unlearning for Federated Zeroth-Order Optimization
Machine LearningArtificial IntelligenceDistributed, Parallel, and Cluster ComputingNetworking and Internet Architecture
Summary
When many devices learn together without sharing their private data, it can be hard to completely erase a user's data if they want it deleted later. The authors found ways to carefully organize this learning so that the model updates can be partially reused, making this deletion process much quicker and exact. Their methods avoid sending complicated gradient information, which reduces communication costs a lot. They prove these methods give the same result as retraining from scratch on the remaining data and show the approach saves time in experiments.
What this means in practice
- •For edge device engineers: Enable faster and exact deletion of user data in federated learning models on edge devices without extra communication of gradients.
- •For mobile app backend teams: Reduce communication costs drastically in federated learning-based personalization services by using zeroth-order optimization with efficient unlearning.
Authors
Weijun Yin, Yanqing Yao, Falko Dressler, Di Wang, Youming Tao
Abstract
Federated zeroth-order optimization (FedZOO) reduces the memory and communication costs of collaborative training for edge intelligence by avoiding backpropagation while communicating only random seeds and scalar coefficients. However, existing methods lack efficient mechanisms for exact unlearning to fully remove the influence of training data when users request deletion. A key insight is that total variation stability of the learning algorithm creates overlap between model distributions before and after data deletion, allowing exact unlearning to reuse computation through coupling. Based on this observation, we jointly design two stable zeroth-order learning algorithms and their corresponding exact-unlearning procedures: \textsc{FedZOO-S} obtains stability through client and mini-batch subsampling, enabling \textsc{FedZOUL-S} to perform efficient unlearning by preserving earlier updates and restarting from the first affected step. \textsc{FedZOO-NS} further combines subsampling with Gaussian noise to increase overlap between update distributions; \textsc{FedZOUL-NS} exploits this overlap through rejection--reflection coupling to reuse affected updates when the coupling is accepted. We prove exact unlearning for both algorithms: the model and saved state have the same joint distribution as retraining with the corresponding learner on retained data. We further establish stability and convergence guarantees for the learning algorithms and derive upper bounds on expected unlearning cost. Experiments demonstrate effective unlearning with competitive model utility and up to $56.1\%$ less cumulative unlearning time than re-optimization. Compared with first-order baselines, our methods reduce communication overhead by up to approximately four orders of magnitude.