Trajectory-Aware Certified Decentralized Unlearning via SGD Stability

Decentralized Unlearning (DU) aims to remove the influence of specific clients from a collaboratively trained global model. However, existing methods suffer from strong reliance on static, problem-specific hyperparameters or restrictive convexity assumptions, limiting their general applicability. To overcome these limitations, we propose TRAjectory-aware CErtified Decentralized Unlearning (TRACE-DU), a generic unlearning framework for decentralized training. TRACE-DU introduces a fine-grained sensitivity analysis that leverages local SGD updates and decentralized training dynamics, thereby eliminating the need for convexity assumptions and reducing dependence on manually tuned parameters. By integrating strategic checkpoint selection with calibrated noise perturbation, the proposed framework enables efficient certified unlearning. Moreover, we exploit historical model trajectories to extend this framework, enabling it to naturally support sequential unlearning requests from an arbitrary number of clients. We provide theoretical guarantees for certified unlearning and derive sensitivity bounds under both convex and non-convex loss functions. Experimental results demonstrate that our framework outperforms state-of-the-art baselines across diverse metrics.

Machine learning models are often trained collaboratively by many devices in a decentralized system, where there is no central server coordinating the training. In some cases, a client may ask to leave and have their data forgotten. This paper studies how to make decentralized system forget clients efficiently and reliably. We propose a novel method which tracks how each client’s updates influenced the model during training. It further selects a suitable earlier model to add carefully calibrated noise, enabling the efficient and certified removal of clients’ influence. We also extend this framework to support multiple deletion requests over time. Experiments on image and text tasks demonstrate the great performance of our framework.