A Certified Unlearning Approach without Access to Source Data
Umit Yigit Basaran, Sk Miraj Ahmed, Amit Roy-Chowdhury, Başak Güler · 2025
Read A Certified Unlearning Approach without Access to Source Data by Umit Yigit Basaran, Sk Miraj Ahmed, Amit Roy-Chowdhury, Başak Güler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06486.txt.
Introduction
Umit Yigit Basaran, Sk Miraj Ahmed, Amit Roy-Chowdhury, and Basak Guler present a method for removing data from a trained model in two thousand twenty-five. Privacy rules now ask that private or protected data be erased from models. Most older methods need the full set of data used to train the model, which is often no longer at hand.
The team uses a stand-in data set that is close in form to the source data. Noise is scaled by the gap between the two sets, with set bounds on how the model acts after removal. Tests on made-up and real data show the method works well while the model stays useful.
Catalog record
| CREATOR | Umit Yigit Basaran, Sk Miraj Ahmed, Amit Roy-Chowdhury, Başak Güler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06486
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Certified Unlearning Approach without Access to Source Data Umit Yigit Basaran, Sk Miraj Ahmed, Amit Roy-Chowdhury, Başak Güler Abstract With the growing adoption of data privacy regulations, the ability to erase private or copyrighted information from trained models has become a crucial requirement. Traditional unlearning methods often assume access to the complete training dataset, which is unrealistic in scenarios where the source data is no longer available. To address this challenge, we propose a certified unlearning framework that enables effective data removal without access to the original training data samples. Our approach utilizes a surrogate dataset that approximates the statistical properties of the source data, allowing for controlled noise scaling based on the statistical distance between the two. While our theoretical guarantees assume knowledge of the exact statistical distance, practical implementations typically approximate this distance, resulting in potentially weaker but still meaningful privacy guarantees. This ensures strong guarantees on the model’s behavior post-unlearning while maintaining its overall utility. We establish theoretical bounds, introduce practical noise calibration techniques, and validate our method through extensive experiments on both synthetic and real-world datasets. The results demonstrate the effectiveness and reliability of our approach in privacy-sensitive settings. 1 Introduction Machine learning models have achieved remarkable success across a wide range of applications by leveraging large-scale datasets. However, growing concerns about data privacy and regulatory requirements—such as the General Data Protection Regulation ( GDPR 2016 ) , California Consumer Privacy Act ( CCPA 2018 ) , or the Canadian Consumer Privacy Protection Act ( CPPA 2023 ) —have led to a pressing demand for mechanisms that allow the removal of specific data points from trained models. Among these mechanisms, certified unlearning has emerged as a cornerstone, formalizing data removal with rigorous guarantees. In contrast to heuristic methods, certified unlearning ensures that the influence of removed data is provably eliminated from the model, offering both privacy compliance and practical utility. This is typically achieved by bounding the statistical discrepancy between a model retrained without the forget data and an approximated model that simulates this retraining. While fully retraining a model from scratch on the retained data is a straightforward and rigorous solution, it becomes computationally prohibitive for large-scale models and frequent deletion requests. Certified unlearning instead provides a practical alternative: it enables efficient, provably correct data removal without exhaustive retraining ( Guo et al. 2019 ; Neel et al. 2021 ; Sekhari et al. 2021 ; Chien et al. 2024 ; Zhang et al. 2024 ) . Existing certified unlearning methods generally focus on two key aspects. First, they approximate the retrained model using an efficient technique, often leveraging a single-step Newton update ( Guo et al. 2019 ; Sekhari et al. 2021 ; Zhang et al. 2024 ) . Second, they inject noise based on differential privacy ( Dwork 2006 ) principles—commonly via a Gaussian mechanism—to ensure that the retrained and unlearned models are statistically indistinguishable. We adopt this single-step update approach in our work as it strikes a balance between efficiency, theoretical grounding, and empirical effectiveness, as supported by prior studies. Despite their promise, these methods often rely on the assumption that the source data remains accessible during unlearning. A critical challenge arises when the unlearning mechanism has no access to the source data samples. This limitation may stem from privacy constraints, as the original model may have been trained by a different organization or a third party; resource restrictions, as old data may be deleted due to memory constraints; or regulatory barriers, as data retention policies or security concerns may prohibit storing the source data. As a result, existing unlearning methods that rely on access to the source data become impractical or infeasible. Consequently, a key open question emerges: • What if the unlearning mechanism has no access to the original training samples, and instead must rely entirely on a surrogate dataset that mimics these statistical properties to achieve certified unlearning? This problem is related to zero-shot unlearning, where no information about the true dataset is available during forgetting, beyond the model. While several relevant methods ( Foster et al. 2024 ; Chundawat et al. 2023 ; Cha et al. 2023 ) have been proposed, no theoretical guarantees exist. A more tractable scenario in practice is when the unlearning mechanism has access to a surrogate dataset that mimics the statistical properties of the source data up to a specified level of fidelity. Summary statistics, learned from this surrogate dataset, are then used to guide the unlearning process. For instance, consider a case where a person requests their data to be deleted, but the organization no longer retains the original training data due to regulatory or resource limitations. Instead, the organization uses publicly available data or previously generated surrogate datasets that closely resemble the source data distribution to facilitate the unlearning process. Alternatively, the individual may provide a new set of data samples (e.g., images)—distinct from the source data but with some statistical discrepancy—specifically to facilitate the unlearning process. In this work, we address precisely this scenario. We study certified unlearning when the unlearning mechanism has no access to source (retain) samples, but instead relies on samples from a surrogate dataset that mimics the source data up to a fidelity criterion. Our goal is to establish formal certified unlearning guarantees during unlearning, and how the unlearning performance changes as a function of the distance between the surrogate and source data. Main Result. We propose a certified unlearning framework that does not require access to the original retain data samples. Instead, we leverage a surrogate dataset where the samples are generated from a distribution that may be different from the original. By carefully scaling the noise based on the statistical distance between the source and surrogate datasets, we provide rigorous indistinguishability guarantees on how closely the unlearned model mimics the truly retrained model. These guarantees are explicitly dependent on the distance between the source and surrogate data. Formally, let \mathcal{D} denote the source dataset drawn from a distribution \rho , whereas \mathcal{D}_{s} denotes a surrogate dataset drawn from a distribution \nu . Both distributions share the support \mathcal{X}\times\mathcal{Y} , where \mathcal{X} represents the feature space and \mathcal{Y} represents the label space. Suppose we want to remove a set of samples \mathcal{D}_{u} from \mathcal{D} . We define \boldsymbol{w}^{\ast}_{r} as the model retrained from scratch on the original retain data \mathcal{D}_{r}=\mathcal{D}\backslash\mathcal{D}_{u} and \widehat{\boldsymbol{w}}_{r} as the model produced by our unlearning mechanism that uses \mathcal{D}_{s} in place of the source dataset \mathcal{D} . Throughout the paper, we focus on classification models. Under typical assumptions ( 4.1 ) about the loss function used to train the model, we prove that the norm of the difference between the model retrained from scratch over the original retain data, \boldsymbol{w}^{\ast}_{r} , and the model approximated with our unlearning mechanism using the surrogate dataset, \widehat{\boldsymbol{w}}_{r} , is upper bounded as ( Theorem 4.2 ), \|\boldsymbol{w}^{\ast}_{r}-\widehat{\boldsymbol{w}}_{r}\|_{2}\leq\Delta where \Delta is a function of the statistical distance between the two distributions \rho and \nu . Then, by carefully scaling the noise as a function of the statistical distance between \rho and \nu , we achieve certified unlearning without direct access to the retain data. Technical details are provided in Section 4 . Contributions. Our contributions