RePASTA-CU: Certified Unlearning Beyond Global Smoothness and Uniform Gradient Bounds

Certified machine unlearning seeks to remove the influence of deleted data without retraining from scratch. Existing first-order guarantees for nonconvex models typically impose global smoothness or uniformly bounded gradients, and some methods use a comparison target different from retraining on the retained data. We propose RePASTA-CU, a checkpoint-based method that keeps non-private training and uses the model obtained by retraining on the retained dataset as its comparison target. It stores a checkpoint after $T-K$ clipped SGD updates, applies $K$ PASTA updates using only retained data after deletion, and adds Gaussian noise at release. Public clipping and projection bound the pre-release distance between the unlearned model and the retained-data retraining model; calibrating the release noise to this bound yields bidirectional $(\epsilon ,\delta )$-certified unlearning without smoothness, Lipschitz continuity, weak convexity, or uniformly bounded gradients. Under weak convexity on a bounded convex domain and a quadratic-growth bound on the raw second moment of stochastic subgradients, we prove an $O(K^{-1/6})$ root-mean-square Moreau-stationarity rate before release noise, with a separate noise-dependent term for the released model. Experiments on synthetic, image, text, federated, and convex tasks compare RePASTA-CU with R2D and other certified-unlearning methods across utility, certificate scale, stability, and deletion cost.