Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data

Noise-based certified machine unlearning currently faces a hard ceiling: the noise magnitude required to certify unlearning typically destroys model utility, particularly for large-scale deletion requests. While leveraging public data is a standard technique in differential privacy to relax this tension, its role in unlearning remains unexplored. We address this gap by introducing **Asymmetric Langevin Unlearning (ALU)**, a framework that uses public data to mitigate privacy costs. We prove that public data injection suppresses the unlearning cost by a factor of $O(1/n_{\mathrm{pub}}^2)$, guaranteeing a strict computational advantage over retraining. This establishes a new control mechanism: practitioners can mitigate the need for high noise—and the associated utility loss—by increasing the volume of public data. Crucially, we analyze the realistic setting of **distribution mismatch**, explicitly characterizing how shifts between public and private sources impact utility. We show that ALU enables "mass unlearning'' of constant dataset fractions -- a regime where standard symmetric methods become impractical -- while maintaining high utility. Empirical evaluations using variational Rényi divergence and membership inference attacks confirm that ALU effectively thwarts privacy attacks while preserving utility under reasonable distribution shifts.

AI systems must comply with several privacy regulations, among them the right to be forgotten, as mandated by the European Union's AI Act and Canada's Artificial Intelligence and Data Act (AIDA). This right allows any user to request the removal of the influence of their personal data from a trained AI system, but retraining the system from scratch for each such request is computationally prohibitive and cannot scale to the volume of requests encountered in modern deployments. A popular approach to enforcing forgetting of individual data points is Langevin Unlearning (Chien et al., 2024), which fine-tunes the model on the remaining data while injecting noise. This approach guarantees that unlearning quality improves with noise magnitude, but at the cost of model performance. Previous analyses have assumed that any data point may be subject to an unlearning request. We consider a setting in which a portion of the data will never be subject to such requests, namely publicly available, open-source data. We show how the presence of such data improves unlearning efficiency without requiring additional noise, and quantify how performance may degrade when public and private data differ significantly in nature. Our work motivates the inclusion of publicly available data when training large-scale AI systems, showing that it improves the efficiency of unlearning algorithms while limiting performance degradation.