cs.LGNov 3, 2026

Sample-Grained Approximate Unlearning with Provable Per-Sample Bounds

Authors: Yaxin Xiao, Yulin Jin, Li Tang, Haoyang LI, Huadi Zheng, Qingqing Ye, Haibo Hu

Organizations: The Hong Kong Polytechnic University · Yunnan University · Huawei Technologies Co., Ltd. · The Hong Kong Polytechnic University Research Centre for Privacy and Security Technologies in Future Smart Systems

Abstract

Machine unlearning aims to erase the influence of a designated forget set from a trained model while preserving strong utility on the retain set. Approximate unlearning methods efficiently achieve this goal without full retraining, but their effectiveness is primarily assessed using dataset-level aggregate metrics. These aggregate metrics can mask deviations from retraining at the level of individual samples. In this work, we focus on per-sample unlearning effectiveness. We introduce SALA (Sample-grained Likelihoods ALignment), a plug-in optimization framework that enables approximate unlearning methods to operate at the level of individual samples by steering each example toward its correct target distribution. To quantitatively assess this behavior, we further propose the sample-grained distribution gap, a metric that captures per-sample discrepancies between approximate unlearning and exact retraining output distributions. We provide theoretical guarantees showing that SALA contracts this gap and yields a bounded per-sample discrepancy to retraining. To make this framework practical, we develop a low-cost estimation method for the member and non-member target distributions. Extensive experiments on classification and generation tasks demonstrate that SALA reduces the sample-grained distribution gap by up to 86.67%86.67\% when paired with existing approximate unlearning baselines, while also improving robustness to unlearning hyperparameters.

Figures & tables

Appendix figures & tables17 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Behavioral Guarantees for Proxy-Based Unlearning

    May 11, 2026Virgile Dine, Teddy FuronMachine Unlearning

  2. Reference-Guided Machine Unlearning

    Mar 11, 2026Jonas Mirlach, Sonia Laguna, Julia E. VogtMachine Unlearning

  3. Multi-Objective Reference-Aligned Machine Unlearning

    May 29, 2026Rasa Khosrowshahli, Stephen Asobiela, Beatrice Ombuki-Berman +1Machine UnlearningCatastrophic Forgetting