Fully Decentralized Certified Unlearning

Hithem Lamri, Michail Maniatakos; Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2026, pp. 24577-24586

Machine unlearning (MU) seeks to remove the influence of specified data from a trained model in response to privacy requests or data poisoning. While certified unlearning has been analyzed in centralized and server-orchestrated federated settings (via guarantees analogous to differential privacy, DP), the decentralized setting--where peers communicate without a coordinator--remains underexplored. We study certified unlearning in decentralized networks with fixed topologies and propose \methodname, a random-walk procedure that performs one projected gradient ascent step on the forget set at the unlearning client and a geometrically distributed number of projected descent steps on the retained data elsewhere, combined with subsampled Gaussian noise and projection onto a trust region around the original model. We provide (i) convergence guarantees in the convex case and stationarity guarantees in the nonconvex case, (ii) (\varepsilon,\delta) network-unlearning certificates on client views via subsampled Gaussian Renyi DP (RDP) with segment-level subsampling, and (iii) deletion-capacity bounds that scale with the forget-to-local data ratio and quantify the effect of decentralization (network mixing and randomized subsampling) on the privacy-utility trade-off. Empirically, on image benchmarks, \methodname matches a given (\varepsilon,\delta) while achieving higher test accuracy than decentralized DP baselines and reducing backdoor accuracy (ASR) to the random-guessing baseline ((~ 10%)).