Leveraging Per-Example Privacy for Machine Unlearning

This work focuses on developing fine-grained theoretical insights to quantify unlearning difficulty at the level of individual data points for fine-tuning-based unlearning. Unlike other unlearning methods that lack theoretical guarantees for non-convex models, our approach builds on recent advances in differential privacy to provide per-instance guarantees using Rényi divergence. While our theoretical analysis applies to Langevin dynamics, we empirically demonstrate that the derived guarantees—and their trends—continue to hold for fine-tuning, even in the absence of explicit noise. Our results show that per-instance privacy levels computed from training dynamics reliably predict unlearning difficulty, offering a principled and practical way to assess unlearning performance. Furthermore, our method identifies harder-to-unlearn data more effectively than existing heuristics, providing a more precise tool for guiding unlearning strategies. These findings pave the way for adaptive and efficient unlearning methods tailored to the properties of specific data points.