Organizations: School of Science and Engineering, Shenzhen Institute of Artificial Intelligence and Robotics for Society, The Chinese University of Hong Kong, Shenzhen, China · Data Science and Analytics Thrust, Information Hub, Hong Kong University of Science and Technology (Guangzhou), China · Internet of Things Thrust, Information Hub, Hong Kong University of Science and Technology (Guangzhou), China
Despite legal mandates for the right to be forgotten, AI operators routinely fail to comply with data deletion requests. While machine unlearning (MU) provides a technical solution to remove personal data's influence from trained models, ensuring compliance remains challenging due to the fundamental gap between MU's technical feasibility and regulatory implementation. In this paper, we introduce the first economic framework for auditing MU compliance, by integrating certified unlearning theory with regulatory enforcement. We first characterize MU's inherent verification uncertainty using a hypothesis-testing interpretation of certified unlearning to derive the auditor's detection capability, and then propose a game-theoretic model to capture the strategic interactions between the auditor and the operator. A key technical challenge arises from MU-specific nonlinearities inherent in the model utility and the detection probability, which create complex strategic couplings that traditional auditing frameworks do not address and that also preclude closed-form solutions. We address this by transforming the complex bivariate nonlinear fixed-point problem into a tractable univariate auxiliary problem, enabling us to decouple the system and establish the equilibrium existence, uniqueness, and structural properties without relying on explicit solutions. Counterintuitively, our analysis reveals that the auditor can optimally reduce the inspection intensity as deletion requests increase, since the operator's weakened unlearning makes non-compliance easier to detect. This is consistent with recent auditing reductions in China despite growing deletion requests. Moreover, we prove that although undisclosed auditing offers informational advantages for the auditor, it paradoxically reduces the regulatory cost-effectiveness relative to disclosed auditing.
Figures & tables
Fig. 1: Framework for Auditing Machine Unlearning (MU) Compliance.
Fig. 2: Auditor’s Two-stage Compliance Auditing Process: Investigation and Enforcement. In the investigation phase, the auditor performs m independent inspection tests via probabilistic MU verification and declares non-compliance if any test fails (zero-tolerance). In the enforcement phase, the auditor imposes a fine and mandates corrective unlearning upon detecting non-compliance.
Fig. 3: The auditor’s optimal inspection intensity m∗(ϵ) in ( 8 ) and detection probability Detect(m∗(ϵ),ϵ) in ( 3 ) versus unlearning certification level ϵ .
Fig. 4: Illustration of how the auditor adjusts equilibrium inspection intensity m∗ in response to increasing unlearning data proportion η . Here, the boundary that separates the gray and red regions is defined by ηth(p) in ( 13 ).
Fig. 5: Theoretical-empirical Alignment: The model utility u(ϵ) , derived from the empirical test loss and the calibrated theoretical upper bound based on ( 1 ), versus the unlearning certification level ϵ (illustrated for η=0.02 ). Here, the model characteristic parameter is calibrated to G=2,000 to guarantee that the calibrated theoretical curve provides a consistent bound on the empirical test loss across practical parameter settings.
Fig. 6: (a) The AI operator’s unlearning certification level ϵ∗ versus the non-compliance fine p in the NE. (b) The AI operator’s unlearning certification level ϵ∗ and (c) the auditor’s inspection intensity m∗ versus the unlearning data proportion η in the NE. Here, in Fig. 6(a) , we vary the unlearning data proportion η over {0.05,0.15,0.25} for each curve, and in Figs. 6(b) and 6(c) , we vary the non-compliance fine p over {10,20,30} for each curve.
Fig. 7: Performance comparisons in terms of (a) the auditor’s expected payoff (which measures regulatory cost-effectiveness) in the equilibrium and (b) the AI operator’s empirical payoff in the equilibrium, under the three mechanisms (TRA, SUA, SDA). Here, the non-compliance fine is set to p=20 .
Machine unlearning has been extensively studied in response to growing privacy concerns and regulatory requirements. However, auditing whether unlearning algorithms have truly erased the influence of specific data remains an open challenge. The lack of reliable and practical auditing mechanisms can lead to critical privacy risks, such as residual information leakage. This paper initiates a systematic investigation into whether existing unlearning algorithms can truly forget the designated data. We propose the first practical and general-purpose auditing framework for machine unlearning, inspired by the concept of proof of ignorance. Our framework addresses the key practicality limitations of existing methods by eliminating the need for retraining-from-scratch baselines, avoiding the training of large numbers of shadow models, and requiring no intrusive intervention in the original training process. To evaluate the effectiveness of our framework, we first conduct validation experiments to verify its soundness and completeness. We then perform comprehensive experiments across six datasets and ten representative unlearning methods. The results demonstrate that our framework reliably distinguishes between successful and failed unlearning. In particular, we observe that retraining-based and fine-tuning-based methods can achieve effective unlearning, even when the target data remain in the original dataset. In contrast, de-optimization-based methods fail to achieve true unlearning and instead degrade the model's performance. Fisher/Hessian-based methods also fail to unlearn requested data, even formal certification is provided. Moreover, we show that our framework is robust against fake unlearning attempts and generalizes well to large language models.
The removal of learned data from Machine Learning models through Machine Unlearning (MU) has been widely studied; however, there has yet to be an agreed-upon scheme for auditing MU. Existing work has shown that a dishonest model owner can falsify evidence to avoid executing MU, while curious auditors (and adversaries) can infer the privacy-sensitive properties of the model and its training data even with limited access. Yet auditing of MU under mutual distrust between the model owner and the auditor remains unexplored. We provide an information-theoretic proof for this scenario: for convex ML models, a generic audit scheme that relies solely on querying the model for behavioral signals cannot identify insufficiently unlearned models without revealing membership information of the retained set. Therefore, auditing MU under the assumption of a dishonest model owner and an honest-but-curious auditor faces an inherent privacy-audit tradeoff. Our empirical results on convex models strongly supports this result, while further experiments demonstrate that this privacy-audit tension persists in non-convex models. Our results call for a more careful consideration of the privacy-audit tension under a realistic auditor threat model, and serve as a foundation for more scrutiny of designs of privacy-preserving audit schemes for the MU pipeline. We also release our code implementation at https://github.com/LiouTang/Behavioral-Unlearn-Audit.
Liou Tang, James Joshi, Ashish Kundu
University of Pittsburgh, Pittsburgh, PA, USA · Cisco Research, San Jose, CA, USA
There is a growing demand for efficient data removal to comply with regulations like the GDPR and to mitigate the influence of biased or corrupted data. This has motivated the field of machine unlearning, which aims to eliminate the influence of specific data subsets without the cost of full retraining. In this work, we propose a statistical framework for machine unlearning with generic loss functions and establish theoretical guarantees. For squared loss, especially, we develop Unlearning Least Squares (ULS) and establish its minimax optimality for estimating the model parameter of remaining data when only the pre-trained estimator, forget samples, and a small subsample of the remaining data are available. Our results reveal that the estimation error decomposes into an oracle term and an unlearning cost determined by the forget proportion and the forget model bias. We further establish asymptotically valid inference procedures without requiring full retraining. Numerical experiments and real-data applications demonstrate that the proposed method achieves performance close to retraining while requiring substantially less data access.
Jingyi Xie, Linjun Zhang, Sai Li
Institute of Statistics and Big Data, Renmin University of China, Beijing 100872, China · Department of Statistics, Rutgers University, Piscataway, NJ 08854, USA · Department of Statistics and Data Science, Tsinghua University, Beijing 100084, China