Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data Ahmed Mehdi Inane 1 2 Vincent Quirion 1 2 Gintare Karolina Dzugaite 3 Ioannis Mitliagkas 3
arXiv:2605.11170v1 [cs.LG] 11 May 2026
Abstract
of the European Union, 2024) and Canada’s Artificial Intelligence and Data Act (AIDA) (Parliament of Canada, 2022) establish fundamental principles including the “right to be forgotten,” which mandates that individuals can request removal of their personal data from trained systems. While the most straightforward approach to these requests—retraining from scratch—provides perfect guarantees, it is computationally prohibitive for modern deep learning models. Consequently, the field has gravitated toward approximate methods, particularly the family of noise-based injection and finetuning, such as Langevin Unlearning (Chien et al., 2024a; Koloskova et al., 2025). These methods offer certifiable privacy guarantees but operate under a strict trade-off: the magnitude of noise required to certify the data erasure degrades the model’s utility.
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/n2pub ), 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.
In this work, we address this limitation by exploring an idea established in Differential Privacy (DP) but unexplored in machine unlearning: the integration of public data. We operate under the realistic assumption that while sensitive user data must be unlearnable, there often exists a corpus of public data that is not subject to retraction requests. We propose Asymmetric Langevin Unlearning (ALU), a framework that leverages this public data as a mechanism to improve the privacy-utility trade-off. To our knowledge, the only prior work exploring mixed-privacy unlearning is Golatkar et al. (2021), who introduced Mixed-Linear Forgetting for computer vision tasks. Their approach requires architectural modifications to achieve forgetting through network linearization, limiting its applicability. In contrast, ALU operates directly on standard training pipelines. Intuitively, public data acts as a stability anchor; it ensures that the weight distributions of the originally trained model and the retrained model remain naturally close. This proximity reduces the need for noise injection to bridge the gap between distributions, thereby preserving utility.
1. Introduction The widespread adoption of machine learning across diverse applications has prompted regulatory responses aimed at protecting user privacy and data rights. Legislative frameworks such as the European Union’s AI Act (Parliament &
• We prove that injecting public data creates a more favorable initialization for the unlearning process, reducing the unlearning cost by a factor of O(1/n2pub ) (Theorems 3.1 and 3.2). This structural advantage enables two capabilities:
1
Université de Montréal 2 Mila, Quebec AI Institute 3 Google DeepMind. Correspondence to: Ahmed Mehdi Inane <[email protected]>.
1
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
– Mass Unlearning: Unlike prior methods where noise requirements are independent of total dataset size, ALU allows for unlearning constant fractions of the private dataset (Corollary 3.1), ensuring robustness to large-scale deletion. – Computational Advantage: We revisit the efficiency of unlearning compared to retraining from scratch. While standard Langevin Unlearning is known to be efficient asymptotically, we establish a stronger result: ALU maintains a strict computational advantage over retraining even in finite-step regimes.
Gaussian) controlling distributional closeness. Langevin Unlearning (LU) (Chien et al., 2024a) instantiates this scheme with L = LDr , the loss on the retain set, and ξt ∼ N (0, Id ). This reduces to projected noisy gradient descent (PNGD) (pseudocode in Appendix E). LU provides certifiable approximate unlearning guarantees by minimizing the Rényi divergence between postunlearning and post-retraining weight distributions (Chien et al., 2024a;b). However, these guarantees require that the entire original training process satisfies differential privacy (DP). This necessitates injecting substantial noise starting from the very first training iteration, which compromises the utility of the base model even before any unlearning request. In this work, we improve upon Chien et al. (2024a) by leveraging public data to mitigate this “privacy tax”. We demonstrate that anchoring the training process with public data allows us to reduce the noise magnitude required during both learning and unlearning while satisfying the same guarantees. By assuming the initialization satisfies a logSobolev inequality—a mild condition satisfied by Gaussian initialization—we derive data-dependent bounds showing that public data acts as a stabilizer, effectively “subsidizing” the privacy cost of the private data. Concurrent approaches like (Koloskova et al., 2025) require only smoothness assumptions, but such data-agnostic bounds depend primarily on projection set geometry rather than exploiting the structural advantage of public data.
• We depart from the idealized assumption of identical private-public distributions. We derive a new generalization bound Theorem 4.1 that explicitly quantifies the trade-off between the benefits of noise reduction, and the penalties of distribution mismatch between public and private sources. • We introduce a rigorous evaluation methodology using variational estimation of the Rényi divergence to validate our bounds. Our experiments confirm that ALU successfully defends against membership inference attacks (U-LiRA) while preserving significantly higher utility than symmetric baselines.
2. Related work 2.1. Machine unlearning
3. Asymmetric Langevin Unlearning
Machine unlearning algorithms eliminate the influence of designated training data (the forget set) while balancing unlearning efficacy, model utility, and computational efficiency. Three canonical strategies illustrate the trade-offs: random re-initialization achieves perfect unlearning but destroys utility; retraining from scratch provides optimal guarantees but incurs prohibitive costs; no intervention preserves utility but achieves no unlearning. Unlearning paradigms diverge between exact unlearning, which matches the retraining baseline but limits expressivity or efficiency (Cao & Yang, 2015; Yan et al., 2022), and approximate unlearning, which provides certified approximations of retraining (Nguyen et al., 2020; Guo et al., 2023; Chien et al., 2024b; Koloskova et al., 2025).
3.1. Preliminaries Motivation. Our approach is motivated by a realistic data setting, well-established in the privacy machine learning literature (Alon et al., 2019; Amid et al., 2022; Ganesh et al., 2023; Lowy et al., 2024), that leverages public data to improve the privacy-utility trade-off. We introduce this asymmetric data model to Langevin Unlearning, which allows us to relax the restrictive Differential Privacy (DP) assumption over the entire dataset. By explicitly modeling this asymmetry, we can leverage public data to enhance the unlearning process to improve both efficacy and model performance without compromising privacy guarantees. Notation. We consider probability distributions defined over a compact parameter space Θ, where stochasticity arises from three sources: the weight initialization distribution π0 , the training data distribution Ptrain , and the inherent randomness of the optimization procedure. We denote by P(Θ) the set of probability distributions supported on Θ. We study the weight distributions πSt , where S ∈ {L, U, R} identifies the training regime and t denotes the iteration count. A key quantity in our analysis is the Rényi divergence of order α between distributions P and Q, denoted
2.2. Langevin Unlearning A common approach to machine unlearning is to run a noisy projected gradient method starting from the trained weights, targeting a distribution close to retraining. Formally, at iteration t, θt+1 = ΠΘ [θt − η∇θ L(θt ) + ξt ] ,
(1)
where L is a surrogate loss (e.g., empirical loss on a retain set), η is the step size, and ξt is injected noise (often 2
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Dα (P ∥Q) (Definition 3.2). We use Ppub and Ppriv to represent the distributions of public and private data, respectively.
Definition 3.2. For probability measures P, Q with P ≪ Q, their Rényi divergence of order α ∈ (0, +∞) \ {1} is α dP 1 Dα (P ∥Q) = log EQ , α−1 dQ
Problem Setting. We consider empirical risk minimization over a dataset D = Dpub ∪ Dpriv comprising two components: a public set Dpub with npub samples from a distribution Ppub , and a private set Dpriv with npriv samples from a distribution Ppriv . The training loss is P 1 LD (θ) = npub +n ℓ(θ, x). Only the private data x∈D priv is subject to unlearning requests, while public data remains permanently available. We employ T PNGD iterations with projections onto Θ ⊂ Rd (radius R) to obtain θT . Since PNGD injects Gaussian noise at each step, it induces probability distributions over the parameter space. To ensure convergence and certifiable guarantees, we assume the initialization distribution satisfies a Log-Sobolev inequality (LSI): Definition 3.1. (Log-Sobolev inequality (Gross, 1975)) A probability measure P ∈ P(Rd ) satisfies a Log-Sobolev inequality with constant C if
dP where dQ is the Radon-Nikodym derivative. This generalizes KL divergence (α → 1), reverse-KL (α → 0), and connects to ε-differential privacy in the limit α → ∞ (Mironov, 2017).
The effectiveness of unlearning is measured by T +K K Dα (πU ∥πR ), while the presence of public data T T helps control Dα (πR ∥πL ), creating favorable conditions for the unlearning process. 3.2. Unlearning Performance We now present theoretical guarantees for asymmetric Langevin unlearning that demonstrate how public data improves unlearning efficiency. Our analysis adapts the prior work of Chien et al. (2024a) by relaxing global differential privacy assumptions, and providing explicit characterization of how public and private data contributions differ in the unlearning bounds. The following result explains how public data reduces reliance on differential privacy constraints:
C I(Q, P ), (2) 2 where the KL divergence and I(Q, P ) = i h DKL denotes ∀Q ∈ P(Rd ), DKL (Q∥P ) ≤
EQ ∥∇ log pq ∥2 is the relative Fisher information.
Theorem 3.1 (The role of public data in shrinking the learning / retraining mismatch.). Suppose that the loss is Lsmooth and M -Lipschitz, and that the initialization distribution satsifies a C0 -log Sobolev inequality. Moreover, suppose that the PNGD updates project onto a compact set Θ of radius R. Then at learning iteration T, we have the following upper T bound on the Rényi divergence between the retraining πR T and learning πL distributions:
Weight Distributions We analyze three distributions induced by PNGD on D = Dpub ∪ Dpriv given a request Dforget ⊆ Dpriv (Figure 1): T • Learning distribution πL : results from T iterations on D with θ0 ∼ π0 , representing the pre-unlearning model; K : results from K fine• Unlearning distribution πU T tuning iterations on D\Dforget initialized from θ ∼ πL ;
−1 −1 TY T T 2M 2 η 2 n2forget TX Dα (πR ∥πL ) ≤ h(t′ , η, σ), α (npub + npriv )2 σ 2 t=1 ′
T • Retraining distribution πR : results from T iterations on D \ Dforget with θ0 ∼ π0 , serving as the retraining baseline.
Learning procedure (T iterations)
t =t
−1 2 where h(t′ , η, σ) = 1 + Cησ′ , and 0 < Ct′ ,1 ≤ (1 + t ,1
Unlearning Procedure (K iterations)
as
2K
−1 ηL)2K C0 + 2ησ 2 (1+ηL) (1+ηL)2 −1 are log Sobolev constants of the distributions of the intermediate PNGD updates. Using the support’s radius allows to loosely upper bound those 4τ constants (Chien et al., 2024a): Ct′ ,1 ≤ 6e ησ2 (4τ 2 + ησ 2 ) with τ = R + ηM .
as
Figure 1. Training pipelines showing the relationship between learning, unlearning, and retraining with public data injection. The T T divergence Dα (πR ∥πL ) quantifies how public data helps maintain similarity between retraining and original learning distributions, facilitating subsequent unlearning.
Proof sketch. The proof follows the analytical framework of Chien et al. (2024a, Theorem 3.3), adapted to leverage the presence of public data in the training set. By distinguishing between public and private data contributions in the gradient updates, we reduce the privacy erosion (Chourasia et al., 2021) of each PNGD update. Full proof details are presented in Appendix B.1.
Following Chien et al. (2024a), we measure unlearning quality via Rényi divergence. 3
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
This bound reveals that we can fix noise magnitude σ to be arbitrarily small to preserve performance while controlling the divergence through public data volume. When npub ≫ nforget , the learning and retraining distributions remain close regardless of noise level, providing favorable initial conditions for unlearning (Figure 3b). Specifically, the public data reduces the squared sensitivity of the gradient updates by a factor of (npub + npriv )2 .
Privacy budget ε = 1, training for T = 10000 iterations
Noise σ 2
20
0.1
t=1
t′ =t
h(t′ , η, σ)
0.4
0.5
0.6
0.7
0.8
0.9
distribution after T + K iterations is upper bounded by T +K K T T Dα (πR ∥πU ) ≤ Dα (πL ∥πR ) 2Kσ 2 η × min gα,η,L (k, σ), exp − , αC̃
t =t
npriv npriv + npub
0.3
T T Figure 2. Required noise magnitude σ to bound Dα (πR ∥πL ) as a function of the forget fraction c = nforget /npriv . Values are computed assuming a strongly convex loss (Chien et al., 2024a), for a binary classification task. Details are deferred to Appendix B.3.
T −1 T −1
−1 T −1 TY X
0.2
nforget npriv
2M 2 η 2 c2 X Y h(t′ , η, σ), ε ′ t=1
2M 2 η 2 c2 2 σasym ≥ ε
10
0
Corollary 3.1 (LU noise vs ALU noise). Consider the setting where the forget set size constitutes a constant fraction of the private data (i.e., nforget = cnpriv for some 2 2 c ∈ (0, 1]). Let σsym and σasym be the noise variances required to bound the Rényi divergence between the learning and retraining distributions by a fixed ε in the symmetric and asymmetric settings, respectively. These variances satisfy the following lower bounds:
!
15
5
This dependency allows us to characterize a regime where asymmetric unlearning provides meaningful guarantees while symmetric methods fail: the unlearning of a constant fraction of the private dataset.
2 σsym ≥
Symetric LU ALU with 4000 points ALU with 8000 points ALU with 12000 points
2
where gα,η,L (k, σ) = .0 6
QK k=1
2
2ησ 1 + (1+ηL) 2C U,k
−1/α
, and
2K −1 < Ck ≤ (1 + ηL)2K C + 2ησ 2(1+ηL) 2−1 , and C̃ (1+ηL) 4τ 2 4τ 2 +2ησ 2 exp 2ησ . 2
≤
Moreover, if the loss function is m-strongly convex and the 2 initial log-Sobolev constant satisfies C > σm , we get the following exponential decay of the Rényi divergence with respect to the unlearning iteration: 2Kσ 2 η T +K K T T . Dα (πR ∥πU ) ≤ Dα (πL ∥πR ) exp − Cα
Proof sketch. The proof follows immediately from Theonforget npriv rem 3.1, by considering that npublic +npriv = c npublic +npriv . Remark. A limitation of the standard symmetric setting 2 (npub = 0) is that the required noise variance σsym has no dependency on the total number of training points when unlearning a constant fraction c. This implies that increasing the dataset size does not mitigate the unlearning cost, rendering the bound vacuous for large cohorts where the required high noise magnitude destroys utility.
This theorem establishes the convergence guarantee for Langevin unlearning by showing that the Rényi divergence between the unlearning and retraining distributions decreases exponentially with unlearning iterations K, with the convergence rate controlled by the initial divergence T +K K Dα (πR ∥πU ). When combined with Theorem 3.1, this reveals the mechanism by which public data improves unlearning: the quadratic reduction in initial divergence from public data injection translates directly into tighter convergence bounds.
In contrast, our framework introduces an explicit dependency on the dataset composition. The required noise n scales with the ratio nprivpriv +npub , meaning the sensitivity of the distribution effectively decays as public data is added. This allows the learning distribution to remain arbitrarily close to the retraining distribution—even for large forget sets—provided sufficient public data is available. We illustrate this advantage in Figure 2. Theorem 3.2 (Convergence guarantee of Langevin unlearning (Chien et al., 2024a, Theorem 3.2)). Suppose that the loss is L-smooth and M -Lipschitz, and that the learning distribution of weights at time T satisfies a C log-Sobolev K inequality. Then, the Rényi divergence between πU (the unlearning distribution after K iterations) and the retraining
Remark (On the tractability of Log-Sobolev constants) While Theorems 3.1 and 3.2 provide explicit convergence bounds, we acknowledge that the Log-Sobolev constants (LSI) (Ct , C̃) are difficult to estimate for deep neural networks and may scale poorly with dimension. However, our core contribution—the role of public data—operates 4
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
independently of these absolute constants. Specifically, the quadratic reduction in gradient sensitivity (Theorem 3.1) acts as a multiplicative factor that improves the divergence bound relative to the baseline, regardless of the specific value of the LSI constant. Thus, even if the absolute convergence rate is loose due to a large C, the relative advantage of injecting public data remains theoretically guaranteed.
match). Assuming the data generating distributions share the same support, that the weight space Θ is compact and that the loss is M -Lipschitz wrt θ, we have the following upper bound on the generalization error on the private data after performing K iterations of unlearning, and initializing T a weight θ0 from πL : npub
D∞ (Ppriv ∥Ppub )
EπUK [LPpriv ] ≤ |e npub +nretain {z
Computational advantage Assuming the loss is mstrongly convex, the computational advantage of ALU over retraining is determined by the training budget T , the privacy requirement ε and the fraction of private data to unlearn nforget /npriv . When T is small, unlearning is more expensive than retraining in traditional settings (npublic = 0). ALU overcomes this via the public data ratio, remaining efficient (K < T ) only if npublic /npriv ≥ C · T β · ε−1/2 · (nforget /npriv ) − 1, where β = σ 2 η/Cα. Here, public data acts as a buffer that facilitates distribution alignment without consuming the privacy budget. Conversely, in the large T regime, the cost of unlearning scales as O(log(ntotal )) (Chien et al., 2024a). In this state of convergence, the addition of any data reduces the initial divergence, ensuring unlearning is strictly more efficient than retraining. See Appendix D and Proposition D.1 for a derivation of a sufficient condition characterizing the computational advantage of unlearning over retraining.
distribution mismatch penalty
+ M · diam(Θ) ·
q |
} EπRT +K [LPtrain ]
T +K 1 K) ∥πU 2 Dα (πR
{z
}
unlearning approximation error
where LP (θ) := Ex∼P [ℓ(θ, x)] denotes the risk over distribution P ; Ptrain is the mixture of Ppub and Ppriv used
during training; and D∞ (P ∥Q) = log ess sup pq is the infinite Rényi divergence representing the worst-case regret (Erven & Harremoës, 2014).
Proof sketch. The proof uses the Kantorovitch-Rubinstein duality (Theorem C.1) to bound the performance gap by the T +K K dual of the Wasserstein distance between πU and πL , then relates this to Rényi divergence via standard inequalities leveraging the compactness of the weight space Θ. For private data evaluation, importance weighting introduces a mismatch penalty controlled by the worst case regret, D∞ (Ppriv ∥Ppub) , weighted by the public data fraction. See Appendix C for full proof details.
4. Performance Without Noise: The Role of Distribution Alignment
When npub → ∞:
LU faces a fundamental dilemma: increasing noise improves unlearning guarantees but degrades model performance. Our asymmetric approach breaks this trade-off by leveraging public data abundance rather than noise amplification. However, the effectiveness of this strategy depends on the relationship between public and private data distributions.
1. Aligned distributions (D∞ (Ppriv ∥Ppub ) ≈ 0): The distribution mismatch penalty vanishes, and the unlearned model’s performance on unseen private data is guaranteed to be at least as good as the retrained model’s performance on the training mixture. This represents the ideal scenario where public data injection preserves performance.
We now analyze when public data injection preserves performance, and when it introduces new challenges. Our results reveal that performance preservation is not automatic – it depends on the distributional alignment between public and private data. When these distributions are similar, public data acts as a performance stabilizer, allowing effective unlearning without quality degradation. Conversely, when distributions differ significantly, performance impacts emerge, though they remain more controlled than noisebased approaches.
2. Misaligned distributions (D∞ (Ppriv ∥Ppub ) ≫ 0): The exponential penalty term dominates, causing the upper bound to become vacuous. While this confirms that performance degradation will occur, the bound’s looseness prevents us from quantifying the actual extent of this degradation. The true performance impact may be better than this worst-case guarantee suggests.
5. Experiments
We evaluate post-unlearning performance on the private data distribution only, reflecting realistic deployment scenarios where the primary concern is maintaining model quality on the sensitive data that remains after unlearning. Performance analysis on the full mixture of public and private distributions is provided in Appendix C for completeness. Theorem 4.1 (Generalization Bound under Distribution Mis-
Our theoretical analysis provides upper bounds on the Rényi T +K K divergence Dα (πR ∥πU ) that governs unlearning performance. However, these bounds involve iteration-dependent log-Sobolev constants that are difficult to estimate in practice, making it unclear how tight our theoretical guarantees actually are. To gain empirical insight into the behavior of 5
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
this divergence, we estimate its value using samples from the weight distributions. To our knowledge, this is the first attempt to evaluate unlearning performance through direct estimation of the Rényi divergence between the parameter distributions. Building on Birrell et al. (2021; 2023), we leverage the variational representation of the Rényi divergence for numerical estimation.
after initial training), while another set trains from scratch on the retain set only. This procedure yields N weight samples from each distribution. We approximate the variational Rényi representation (Equation (Lemma A.2)) using neural network discriminators to parameterize the function space Mb (Ω). This approach follows established practices in divergence estimation (Birrell et al., 2021; 2023; Belghazi et al., 2021) (pseudo-code in Appendix G.1).Complete details on discriminator architecture and training procedures are provided in Appendix G.
Theorem 5.1. (Convex conjugate variational approximation of the Rényi divergence (Birrell et al., 2023)) Let P,Q two probability distributions supported on Ω, such that P ≪ Q, and let Mb be the space of bounded measurable functions on Ω. Then, ∀α ∈ (0, +∞) \ {1}, Z Dα (P ∥Q) gdQ = sup α g∈Mb (Ω),g<0 Z α−1 1 + |g| α dP + α−1 (log α + 1) . α−1
Results. Figure 3a presents our Rényi estimation results, demonstrating the effectiveness of public data injection for improving unlearning efficiency. The experiments are conducted using N = 30000 models for each distribution and averaged across 5 discriminator trainings with spectral normalization. The PNGD noise scale is σ = 0.01 and α = 2. The results show that increasing public data volume reduces T +K K Dα (πR ∥πU ), with the divergence decreasing both as a function of unlearning iterations and public data proportion. To understand the mechanism driving these improvements, we conduct an ablation study examining the initial conditions after a single unlearning iteration. Figure 3b isolates the effect of public data on the starting distributions by meaT +1 1 suring Dα (πR ∥πU ) as a function of public data volume. Rather than directly improving the unlearning procedure itself, public data creates more favorable initial conditions by ensuring the learning and retraining weight distributions begin in closer proximity. This mechanistic understanding validates our theoretical framework: public data primarily controls the initial gap between distributions (Theorem 3.1), which then propagates through the unlearning iterations to produce the final performance gains.
This variational representation of Rényi divergence allows T +K K us to obtain estimates of Dα (πR ∥πU ) using trained models as samples. We emphasize that this is not intended as a practical evaluation methodology for machine unlearning, as it requires training numerous models to obtain sufficient samples for reliable statistical estimation. Standard approaches like membership inference attacks (MIAs) (Shokri et al., 2017; Carlini et al., 2021; Hayes et al., 2024) remain more suitable for practical evaluation. Our goal is purely investigative: to understand how the Rényi divergence behaves empirically and assess whether our theoretical bounds, despite containing intractable constants. We present our findings in two parts: Sections 5.1 and 5.2 investigate the behaviour of the upper bounds provided respectively in Theorem 3.2 and Theorem 4.1, while Section 5.3 provides standard membership inference attack and utility evaluations to contextualize our approach within existing unlearning assessment practices.
5.2. Distribution Alignment and the Unlearning-Utility Trade-off Theorem 4.1 characterizes a trade-off caused by public data injection: as we increase public data volume, the unlearning approximation error decreases, yet the distribution mismatch penalty simultaneously grows. The balance between these competing terms determines whether public data injection preserves or degrades model performance. To empirically investigate this trade-off, we conduct experiments across two distinct distributional regimes: one where the public and private domains exhibit moderate visual alignment, and another where they are substantially misaligned.
5.1. Evaluating the Rényi Divergence Experimental Setup. We evaluate our approach on a multiclass image classification task using two domains from the DomainNet dataset (Peng et al., 2019): Quickdraw (sketches) and Clipart (stylized images), each containing 24 classes. We select these visually distinct domains to investigate how public-private data alignment affects unlearning and utility (Figure 5).
We fix K = 5 unlearning iterations and evaluate performance using the DomainNet dataset across two domain pairs. The aligned regime pairs Quickdraw (public) and Clipart (private), which despite visual stylistic differences share semantic structure. The misaligned regime pairs Infograph (public) and Real (private), which exhibit greater distributional divergence. We measure model performance
The experimental configuration treats Clipart images as private data (subject to unlearning) and Quickdraw images as public data (permanently retained). For a training set of size n = npub + npriv , we train models using cross-entropy loss and PNGD updates. To obtain samples from the weight K T distributions πU and πR , we train N models in parallel: one set undergoes unlearning (fine-tuning on the retain set 6
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data 3.4 3.2
3.2
3.0
D ( RT + 1 U1 )
D ( RT + K UK)
3.0 2.8 2.6 2.4 2.2 2.0
2.8 2.6
10K public points, 12K forget points 15K public points, 7K forget points 20K public points, 2K forget points
2
4
6
2.4 8
10
Unlearning Iteration (K)
12
14
10000
T +K K (a) Variational Rényi divergence Dα (πR ∥πU ) vs. public data proportion. Increasing public data volume and unlearning iterations both consistently reduce divergence, confirming improved unlearning efficacy.
12000
14000
16000
Number of Public Points
18000
20000
(b) Ablation study: initial distribution alignment (K = 1). The T +1 1 divergence Dα (πR ∥πU ) decreases as the public data volume increases, validating the more favorable initialization provided by public data injection.
Figure 3. Rényi divergence estimation across varying public data (Clipart) volumes.
U-LiRA Confidence
via loss on the private data distribution Ppriv after unlearning, comparing against the retraining baseline on the training mixture. Results are summarized in Table 1. Table 1. Unlearning vs Retraining Performance Across Distribution Alignments (K = 5, Private: 20000 points, Forget Set: 10000 points) Public Domain
Private Domain
Public Points
Unlearn Loss
Retrain Loss
Rel. Diff (%)
Quickdraw Quickdraw Quickdraw
Clipart Clipart Clipart
10000 30000 40000
3.102 3.102 3.099
2.976 2.965 2.989
4.23 4.62 3.68
Infograph Infograph Infograph
Real Real Real
10000 30000 40000
2.233 2.238 2.233
2.495 2.496 2.504
10.53 10.34 10.81
1.0 0.8 0.6 0.4 0.2 0.0
25 000 private points, 50 000 public points 25 000 private points, 0 public points
0
5
10
Unlearning Steps (K)
15
Figure 4. U-LiRA confidence scores after K unlearning iterations as violin plots with quartiles.
The results reveal a contrast between the two regimes. In the aligned setting, the relative performance gap remains modest (3.68–4.62%) across varying public data volumes, suggesting that the mismatch penalty remains manageable and the approximation error reduction dominates. In contrast, the misaligned setting exhibits a persistent performance gap (10.34–10.81%), with minimal sensitivity to public data volume. This indicates that when distributional divergence is large, increasing public data fails to overcome the mismatch penalty, rendering the approximation error reduction insufficient to improve generalization.
LiRA membership inference attack for unlearning (Hayes et al., 2024; Carlini et al., 2021). Given a training set, forget set, and specified learning and unlearning algorithms, the adversary’s goal is to infer whether a model’s weights θ were K drawn from the unlearning distribution πU or the retrainT +K ing distribution πR . Intuitively, lower attack accuracy indicates that the unlearning and retraining distributions are harder to distinguish, i.e., better unlearning. In its most basic form, U-LiRA can be formalized via Bayes’ rule under a uniform prior on whether the forget set was included during training. Letting P (θ | ·) denote the likelihood of observing model parameters θ under a given distribution, and P (· | θ) as the posterior probability that θ was drawn from that distribution, we have
5.3. Practical Evaluation of LU in the Asymmetric Setting
K P (πU | θ) =
We now adopt standard evaluation methodology from the unlearning literature (Hayes et al., 2024), highlighting the benefit of public data injection. We provide an overview here and defer details to Appendix H.
K P (θ | πU ) . T +K K P (θ|πU ) + P (θ | πR )
By selecting a one-dimensional representation of the models f : Θ → R and assuming that the induced distributions T +K K f♯ πU and f♯ πR are Gaussian, we can estimate the likelihood terms P (θ | ·) from a tractable number of model samples.
Evaluation Method. This evaluation is based on the U7
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
6. Future Work
Experimental Setup. For the sake of completeness, we focus this next set of experiments on a sentiment analysis task on the IMDB dataset of movie reviews (Maas et al., 2011). This is a binary classification task, where an LSTM (Hochreiter & Schmidhuber, 1997) learns to recognize if a review is either negative or positive. We use the Amazon reviews dataset from Zhang et al. (2015) as the public data source. We use a forget set of 100 uniformly sampled examples from the IMDB dataset. For both experiments, i.e., with and without public data injection, we generate N = 50 models to estimate each likelihood density, and report the empirical distribution of probabilities assigned to the right origin distribution by U-LiRA (confidence scores) T +K K for 50 models test (25 from πU , and 25 from πR , where T = 50 and K = 1 → 15). Figure 4 highlights that without public data injection, U-LiRA is able to identify a large proportion of models confidently and correctly, even after a number of unlearning steps. This observed discriminative power is heavily impacted by public data injection. We can also observe that modes of the confidence scores generally decrease with the number of unlearning steps, highlighting the unlearning effectiveness of LU.
Our framework opens several compelling avenues for research into the interplay of public data and unlearning. Algorithmic extensions include studying ALU in pretraining/fine-tuning regimes and developing adaptive algorithms that leverage domain adaptation to optimally balance distribution alignment with unlearning efficiency. We also envision a constrained optimization approach where the unlearning objective is regularized to keep the weight distribution close to a public-only reference. Theoretically, addressing the intractable log-Sobolev constants in current Langevin analysis remains a priority. Transitioning to alternative isoperimetric assumptions (Chewi et al., 2021; Mousavi-Hosseini et al., 2023; Altschuler & Chewi, 2024) or adopting weaker divergence measures could yield more tractable bounds than those provided by Rényi divergence. Finally, extending analysis from weight distributions to output distributions would facilitate blackbox evaluation. Finally, as highlighted by Tramèr et al. (2024), large-scale datasets scraped from the web are not inherently privacyneutral and may contain sensitive or copyrighted information. Applications should ensure that public datasets used for initialization do not introduce secondary leakage, ensuring that the efficiency gains of ALU do not come at the cost of unintended exposure from the public source.
Now that we’ve observed the effect of public data injection on the unlearning effectiveness of LU, we change our focus towards its impact on model utility. To this end, we report in Table 2 the average model accuracies over the 75 models we trained for each model distribution, on a test set of 10, 000 unseen samples from the IMDB dataset. As the Amazon reviews dataset appears to be a good auxiliary public data source for the IMDB review classification problem (close data distributions), we also include an experiment in which a uniformly sampled 40% of its labels are flipped, thus increasing distribution mismatch between public and private sources.
7. Conclusion We have studied Langevin unlearning under the assumption of asymmetric data sources, where datasets contain both private and public data. Our theoretical analysis demonstrates that this framework fundamentally improves the unlearning-utility trade-off by enabling control over unlearning guarantees through data supplementation rather than noise amplification. The framework provides fine-grained analysis of how distributional alignment between public and private data affects this trade-off: when distributions are well-aligned, public data injection preserves utility while maintaining unlearning guarantees, while misaligned distributions introduce controlled performance penalties that remain more manageable than traditional noise-based approaches.
Table 2. Unlearned and Retrained Model Test Accuracies (IMDB, 25000 private points) Public Dataset (Points)
Flipped Labels
Unlearned Acc. (%)
Retrained Acc. (%)
None (0) Amazon Reviews (50 000) Amazon Reviews (50 000)
0% 0% 40%
82.59 81.42 80.40
82.54 82.15 80.80
From Table 2, we can observe that model accuracy does decrease from the injection of public data. However, this drop in accuracy is rather negligible compared to the extent to which public data injection improves the unlearning effectiveness of LU, which is highlighted by Fig. 4. As expected, the drop in accuracy is proportionately much lower when the quality of auxiliary public data is high (1.17% for unlearned and 0.39% for retrained) than when it is low (2.19% for unlearned, an ≈ 1.87 times increase, and 1.74% for retrained, an ≈ 4.46 times increase).
Impact statement This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
8
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
References
Chewi, S. Log-concave sampling. Book draft available at https://chewisinho. github. io, 9:17–18, 2023.
Alon, N., Bassily, R., and Moran, S. Limits of private learning with access to public data, 2019. URL https: //arxiv.org/abs/1910.11519.
Chewi, S., Erdogdu, M. A., Li, M. B., Shen, R., and Zhang, M. Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev, December 2021. URL http://arxiv. org/abs/2112.12662. arXiv:2112.12662 version: 1.
Altschuler, J. M. and Chewi, S. Shifted Composition III: Local Error Framework for KL Divergence, December 2024. URL http://arxiv.org/abs/2412. 17997. arXiv:2412.17997 [math].
Chien, E., Wang, H., Chen, Z., and Li, P. Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning, 2024a. eprint: 2401.10371.
Altschuler, J. M. and Talwar, K. Resolving the mixing time of the langevin algorithm to its stationary distribution for log-concave sampling. arXiv preprint arXiv:2210.08448, 2022.
Chien, E., Wang, H., Chen, Z., and Li, P. Stochastic Gradient Langevin Unlearning, 2024b. eprint: 2403.17105. Chourasia, R., Ye, J., and Shokri, R. Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent, February 2021. URL https://arxiv.org/ abs/2102.05855v5.
Amid, E., Ganesh, A., Mathews, R., Ramaswamy, S., Song, S., Steinke, T., Suriyakumar, V. M., Thakkar, O., and Thakurta, A. Public data-assisted mirror descent for private model training, 2022. URL https: //arxiv.org/abs/2112.00193.
Donsker, M. D. and Varadhan, S. S. Asymptotic evaluation of certain markov process expectations for large time, i. Communications on pure and applied mathematics, 28 (1):1–47, 1975.
Belghazi, M. I., Baratin, A., Rajeswar, S., Ozair, S., Bengio, Y., Courville, A., and Hjelm, R. D. MINE: Mutual Information Neural Estimation, August 2021. URL http:// arxiv.org/abs/1801.04062. arXiv:1801.04062 [cs].
Erven, T. v. and Harremoës, P. Rényi Divergence and Kullback-Leibler Divergence. IEEE Transactions on Information Theory, 60(7):3797–3820, July 2014. ISSN 0018-9448, 1557-9654. doi: 10.1109/TIT.2014. 2320500. URL http://arxiv.org/abs/1206. 2459. arXiv:1206.2459 [cs].
Birrell, J., Dupuis, P., Katsoulakis, M. A., Rey-Bellet, L., and Wang, J. Variational Representations and Neural Network Estimation of Rényi Divergences, July 2021. URL http://arxiv.org/abs/2007. 03814. arXiv:2007.03814 [stat].
Ganesh, A., Haghifam, M., Nasr, M., Oh, S., Steinke, T., Thakkar, O., Thakurta, A., and Wang, L. Why Is Public Pretraining Necessary for Private Model Training?, 2023. URL https://arxiv.org/abs/ 2302.09483. eprint: 2302.09483.
Birrell, J., Pantazis, Y., Dupuis, P., Katsoulakis, M. A., and Rey-Bellet, L. Function-space regularized Rényi divergences, February 2023. URL http://arxiv. org/abs/2210.04974. arXiv:2210.04974 [stat].
Gibbs, A. L. and Su, F. E. On choosing and bounding probability metrics, September 2002. URL http://arxiv. org/abs/math/0209021. arXiv:math/0209021.
Cao, Y. and Yang, J. Towards Making Systems Forget with Machine Unlearning. In 2015 IEEE Symposium on Security and Privacy, pp. 463–480, 2015. doi: 10.1109/ SP.2015.35.
Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and Soatto, S. Mixed-Privacy Forgetting in Deep Networks, 2021. URL https://arxiv.org/abs/ 2012.13431. eprint: 2012.13431.
Carlini, N., Chien, S., Nasr, M., Song, S., Terzis, A., and Tramèr, F. Membership inference attacks from first principles. IEEE Symposium on Security and Privacy, 2021. doi: 10.1109/sp46214.2022.9833649.
Gronwall, T. H. Note on the derivatives with respect to a parameter of the solutions of a system of differential equations. Annals of Mathematics, 20(4):292–296, 1919.
Caron, M., Touvron, H., Misra, I., Jégou, H., Mairal, J., Bojanowski, P., and Joulin, A. Emerging properties in self-supervised vision transformers, 2021. URL https: //arxiv.org/abs/2104.14294.
Gross, L. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4):1061–1083, 1975. Guo, C., Goldstein, T., Hannun, A., and Maaten, L. v. d. Certified Data Removal from Machine Learning Models, 2023. URL https://arxiv.org/abs/1911. 03030. eprint: 1911.03030.
Chen, H.-B., Chewi, S., and Niles-Weed, J. Dimension-free log-sobolev inequalities for mixture distributions. Journal of Functional Analysis, 281(11):109236, 2021. 9
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225–1234. PMLR, 2016.
Miyato, T., Kataoka, T., Koyama, M., and Yoshida, Y. Spectral Normalization for Generative Adversarial Networks, February 2018. URL http://arxiv.org/ abs/1802.05957. arXiv:1802.05957 [cs].
Hayes, J., Shumailov, I., Triantafillou, E., Khalifa, A., and Papernot, N. Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy, May 2024. URL http://arxiv.org/abs/2403. 01218. arXiv:2403.01218 [cs].
Mousavi-Hosseini, A., Farghly, T. K., He, Y., Balasubramanian, K., and Erdogdu, M. A. Towards a complete analysis of langevin monte carlo: Beyond poincaré inequality. In The Thirty Sixth Annual Conference on Learning Theory, pp. 1–35. PMLR, 2023. URL https://proceedings.mlr.press/ v195/mousavi-hosseini23a.html.
Hayes, J., Shumailov, I., Triantafillou, E., Khalifa, A., and Papernot, N. Inexact unlearning needs more careful evaluations to avoid a false sense of privacy. In 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pp. 497–519, 2025. doi: 10.1109/SaTML64287.2025.00034.
Neyman, J. and Pearson, E. S. Ix. on the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 231(694-706):289–337, 1933.
Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural Computation, 9(8):1735–1780, 1997. doi: 10. 1162/neco.1997.9.8.1735. Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization, 2017. URL https://arxiv.org/abs/ 1412.6980. Koloskova, A., Allouah, Y., Jha, A., Guerraoui, R., and Koyejo, S. Certified Unlearning for Neural Networks, June 2025. URL http://arxiv.org/abs/2506. 06985. arXiv:2506.06985 [cs]. Lamperski, A. G. Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning. ArXiv, December 2020. URL https: //www.semanticscholar.org/paper/ ede5a9ae87c1dee98098c243f6b44c30804acbdf. Lowy, A., Li, Z., Huang, T., and Razaviyayn, M. Optimal differentially private model training with public data. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024. Maas, A. L., Daly, R. E., Pham, P. T., Huang, D., Ng, A. Y., and Potts, C. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142–150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http://www.aclweb. org/anthology/P11-1015. Mironov, I. Renyi Differential Privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263–275, August 2017. doi: 10.1109/CSF.2017. 11. URL http://arxiv.org/abs/1702.07476. arXiv:1702.07476 [cs]. 10
Nguyen, Q. P., Low, B. K. H., and Jaillet, P. Variational Bayesian Unlearning. In Advances in Neural Information Processing Systems, volume 33, pp. 16025–16036. Curran Associates, Inc., 2020. URL https://proceedings. neurips.cc/paper/2020/hash/ b8a6550662b363eb34145965d64d0cfb-Abstract. html. Oquab, M., Darcet, T., Moutakanni, T., Vo, H., Szafraniec, M., Khalidov, V., Fernandez, P., Haziza, D., Massa, F., El-Nouby, A., Assran, M., Ballas, N., Galuba, W., Howes, R., Huang, P.-Y., Li, S.-W., Misra, I., Rabbat, M., Sharma, V., Synnaeve, G., Xu, H., Jegou, H., Mairal, J., Labatut, P., Joulin, A., and Bojanowski, P. Dinov2: Learning robust visual features without supervision, 2024. URL https://arxiv.org/abs/2304.07193. Parliament, E. and of the European Union, C. Regulation (eu) 2024/1689 of the european parliament and of the council of 13 june 2024 laying down harmonised rules on artificial intelligence and amending regulations (ec) no 300/2008, (eu) no 167/2013, (eu) no 168/2013, (eu) 2018/858, (eu) 2018/1139 and (eu) 2019/2144 and directives 2014/90/eu, (eu) 2016/797 and (eu) 2016/798 (artificial intelligence act). Official Journal of the European Union, July 2024. URL https://eur-lex. europa.eu/eli/reg/2024/1689/oj/eng. Entered into force: 1 August 2024. Parliament of Canada. An act to enact the consumer privacy protection act, the personal information and data protection tribunal act and the artificial intelligence and data act and to make consequential and related amendments to other acts. Bill C-27, 44th Parliament, 1st Session, 2022. URL https://www.parl.ca/legisinfo/ en/bill/44-1/c-27. Digital Charter Implementation Act, 2022.
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Peng, X., Bai, Q., Xia, X., Huang, Z., Saenko, K., and Wang, B. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1406–1415, 2019. Raginsky, M., Rakhlin, A., and Telgarsky, M. Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis, 2017. URL https://arxiv. org/abs/1702.03849. eprint: 1702.03849. Shokri, R., Stronati, M., Song, C., and Shmatikov, V. Membership inference attacks against machine learning models, 2017. URL https://arxiv.org/abs/1610. 05820. Tramèr, F., Kamath, G., and Carlini, N. Position: Considerations for Differentially Private Learning with Large-Scale Public Pretraining. In Proceedings of the 41st International Conference on Machine Learning, pp. 48453–48467. PMLR, July 2024. URL https://proceedings.mlr.press/ v235/tramer24a.html. ISSN: 2640-3498. Vempala, S. and Wibisono, A. Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices. In Wallach, H., Larochelle, H., Beygelzimer, A., Alché-Buc, F. d., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips. cc/paper_files/paper/2019/file/ 65a99bb7a3115fdede20da98b08a370f-Paper. pdf. Villani, C. et al. Optimal transport: old and new, volume 338. Springer, 2009. Xu, P., Chen, J., Zou, D., and Gu, Q. Global convergence of langevin dynamics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018. Yan, H., Li, X., Guo, Z., Li, H., Li, F., and Lin, X. ARCANE: An Efficient Architecture for Exact Machine Unlearning. volume 5, pp. 4006–4013, July 2022. doi: 10. 24963/ijcai.2022/556. URL https://www.ijcai. org/proceedings/2022/556. ISSN: 1045-0823. Ye, J. and Shokri, R. Differentially Private Learning Needs Hidden State (Or Much Faster Convergence), March 2022. URL https://arxiv.org/abs/ 2203.05363v2. Zhang, X., Zhao, J., and LeCun, Y. Character-level convolutional networks for text classification. In Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 1, NIPS’15, pp. 649–657, Cambridge, MA, USA, 2015. MIT Press. 11
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
A. Unlearning performance bounds A.1. Proof of Theorem 3.2 Theorem. (Chien et al., 2024a) Suppose that the loss is L-smooth and M -Lipschitz, and that the learning distribution of K weights at time T satisfies a C log-Sobolev inequality. Then, the Rényi divergence between πU (the unlearning distribution after K iterations) and the retraining distribution after T + K iterations is upper bounded by: ! K−1 X 1 T +K K T T Dα (πR ∥πU ) ≤ Dα (πL ∥πR ) exp − Rk α k=0
where Rk > 0 depend on the problem setting (Chien et al., 2024a). Moreover, if the loss function is m-strongly convex 2 and the initial log-Sobolev constant satisfies C > σm , we get the following exponential decay of the Rényi divergence with respect to the unlearning iteration: 2Kσ 2 η T +K K T T Dα (πR ∥πU ) ≤ Dα (πL ∥πR ) exp − Cα We provide the proof of (Chien et al., 2024a), Theorem 3.2, slightly modified to our setting. Specifically, we relax the assumption that the learning and retraining processes have converged to their stationary distribution (infinite training). In order to prove this theorem, we will use the following lemmas: Lemma A.1 (Characterizing the log-Sobolev constants of the PNGD updates (Chewi, 2023)). Consider the PNGD update: h i p θk+1 = ΠΘ θk − η∇LD (θk ) + 2ησ 2 Wk , θ0 ∼ π where π satisfies a C-Log Sobolev inequality. Then, we have the following: • If L is L-smooth, then for the gradient update h(θ) = θ − ∇θ L(θ), we have that the distribution of h♯ π satisfies a (1 + ηL)2 × C log-Sobolev inequality. Moreover, if L is m-strongly convex and η < L1 , then h♯ π satisfies a (1 − ηm)2 × C log Sobolev inequality (Altschuler & Talwar, 2022). • π ∗ N (0, σ 2 Id ) satisfies a a C + σ 2 log-Sobolev inequality • ΠΘ♯ π satisfies a C log-Sobolev inequality By composing the aforementioned statements, we get that π1 satisfies a (1 + ηL)2 × C + 2ησ 2 -log Sobolev inequality. Moreover, if L is m-strongly convex and η < L1 , we have that π1 satisfies a (1 − ηm)2 × C + 2ησ 2 Lemma A.2 (Data Processing inequality for the Rényi divergence (Erven & Harremoës, 2014)). For any α ≥ 1, any function h : Rd → Rd and distributions P, Q supported on Rd , we have: Dα (h♯ P ∥h♯ Q) ≤ Dα (P ∥Q) with equality if h is bijective Lemma A.3 ((Vempala & Wibisono, 2019; Chien et al., 2024a) characterizing the Rényi divergence between two distributions convoluted with Gaussians). Let Pt = P ∗ N (0, 2tσ 2 Id ) and Qt = Q ∗ N (0, 2tσ 2 Id ). Then, ∀α > 0: ∂Dα (Pt ∥Qt ) Gα (Pt ∥Qt ) = −ασ 2 ∂t Fα (Pt ∥Qt ) h α i h α i with Gα (P ∥Q) = EQ pq ∥∇ log pq ∥2 denoting the relative Rényi information and Fα (P ∥Q) = EQ pq = exp((α − 1)Dα (P ∥Q) Lemma A.4. Lower bound of the G-F ratio (Vempala & Wibisono, 2019) If Q ∈ P(Θ) satisfies a C log Sobolev inequality, then ∀P ∈ P(Θ): Gα (P ∥Q) 2Dα (P ∥Q) ≥ Fα (P ∥Q) α2 C 12
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Lemma A.5. Grönwall’s inequality (Gronwall, 1919) Let I = [a, b] denote an interval on the real line. Let β and u be real-valued continuous functions defined on I. If u is differentiable in the interior of I and satisfies for all t in the interior of I: ∂u(t) ≤ β(t)u(t) dt then we have: Z t u(t) ≤ u(a) exp
β(s)ds
a
for all t ∈ I Lemma A.6. Universal upper bound on the log Sobolev constant for measures with compact support (Chen et al., 2021) Let P a probability measure supported on a compact set with radius R. Then, for each σ > 0, P ∗ N (0, σId ) satisfy a log Sobolev inequality with constant upper bounded by 6(4R2 + σ) exp
4R2 σ
Proof. Using these results, we have: T +K T +K K K Dα (h♯ πR ∥h♯ πU ) ≤ Dα (πR ∥πU )
( Lemma A.2)
K,1,t K The PNGD updates preserve the log-Sobolev inequality for the resulting distributions: let πU = h♯ πU ∗ T +K,1,t K T T = h ♯ πU ∗ N (0, 2tσ 2 Id ). Since πL and πR satisfy a log-Sobolev inequality (initializaN (0, 2tσ 2 Id ) and πR T +K K tion distributions) and the loss function is L-smooth, then by Lemma A.1 the distributions πU , πL satisfy respectively K,1,t T +K,1,t CU,K , CL,T +K log Sobolev inequalities. Using Lemma A.1 on the distributions πU , πR yields that they respectively satisfy (1 + ηL)2 CU,K + 2ησ 2 and (1 + ηL)2 CL,T +K + 2ησ 2 log Sobolev inequalities for all t ∈ [0, η]. Upper bounding the distributions convolved with Gaussian distributions: Using Lemma A.3, we have that, ∀α > 0: T +K,1,t K,1,t T +K,1,t K,1,t Gα (πR ∥πU ) ∂Dα (πR ∥πU ) = −ασ 2 T +K,1,t K,1,t ∂t Fα (πR ∥πU ) K,1,t and since πU satisfies a CU,K,t = (1 + ηL)2 CU,K + 2tσ 2 log-Sobolev inequality, we can use Lemma A.4 to upper bound the derivative of the Rényi divergence with respect to t ∈ [0, η]: T +K,1,t K,1,t ∂Dα (πR ∥πU ) 2σ 2 K,1,t T +K,1,t ) ≤− ∥πU Dα (πR ∂t αCU,K,t
Thus, by Grönwall’s inequality (Lemma A.5), we have ∀t ∈ [0, η]: Z t T +K,1,t K,1,t T +K K Dα (πR ∥πU ) ≤ Dα (h♯ πR ∥h♯ πU ) exp − 0
2σ 2 ds αCU,K,s
Z t
2σ 2 − ds α ((1 + ηL)2 CU,K + 2sσ 2 ) 0 Z t 2σ 2 T +K K ≤ Dα (πR ∥πU ) exp − ds α ((1 + ηL)2 CU,K + 2sσ 2 ) 0 T +K K ≤ Dα (h♯ πR ∥h♯ πU ) exp
(Lemma A.2)
Computing the integral yields: Z t Z 2σ 2 1 t 2σ 2 − ds = − ds α ((1 + ηL)2 CU,K + 2sσ 2 ) α 0 (1 + ηL)2 CU,K + 2sσ 2 0 1 = − log (1 + ηL)2 CU,K + 2tσ 2 − log (1 + ηL)2 CU,K α 1 2tσ 2 =− log 1 + α (1 + ηL)2 CU,K 13
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Thus, by setting t = η, we get: T +K,1,η K,1,η Dα (πR ∥πU )≤
1+
2ησ 2 (1 + ηL)2 CU,K
−1 α
T +K K Dα (πR ∥πU )
Finally, using the data processing inequality for the projection of PNGD and iterating over the number of unlearning iterations, we get: T +K,1,η K,1,η T +K+1 K+1 Dα (πR ∥πU ) ≤ Dα (πR ∥πU ) −1 α 2ησ 2 T +K K ≤ 1+ Dα (πR ∥πU ) 2 (1 + ηL) CU,K −1 K α Y 2ησ 2 T T ≤ Dα (πR ∥πL ) 1+ 2 (1 + ηL) CU,k k=1
A.2. Tracking the log-Sobolev constants For a generic, L-smooth non-convex loss function L, one can derive the following recurrence relation, ∀k ≥ 1 upper bounding the log-Sobolev constants: C1 ≤ (1 + ηL)2 C0 + 2ησ 2
(Lemma A.1)
4
2
2
2
C2 ≤ (1 + ηL) C0 + (1 + ηL) 2ησ + (1 + ηL) ... CK ≤ (1 + ηL)
2K
C0 + 2ησ 2
K−1 X
(1 + ηL)2
k=0
(1 + ηL)2K − 1 ≤ (1 + ηL)2K C0 + 2ησ 2 (1 + ηL)2 − 1
(3)
If we add the assumption that the loss is convex, then the map h(θ) = θ − η∇θ L(θ) is 1-Lipschitz for η < L2 (Hardt et al., 2016) and we can reduce (1 + ηL) to 1 in the aforementioned bounds: CK ≤ C0 + 2Kησ 2
(4)
Finally, assuming m-strong convexity yields that the map h(θ) is 1 − ηm-Lipschitz, which allows for the following 2 σ2 ) (Chien et al., 2024a): contractive recurrence on the log-Sobolev constants ∀k ≥ 1 by setting η < m (1 − mC 0 Ck ≤ (1 − ηm)2 Ck−1 + 2ησ 2 ≤ Ck−1 Ck ≤ (1 − ηm)2K C0 + 2ησ 2
(1 − ηm)2K − 1 ≤ C0 (1 − ηm)2 − 1
K,1,t Thus, we have that ∀t ∈ [0, η], πU satisfies a C0 log-Sobolev inequality thus we have by Lemma A.4: T +K,1,t K,1,t ∂Dα (πR ∥πU ) 2σ 2 T +K,1,t K,1,t ≤− Dα (πR ∥πU ) ∂t αC
Thus, by Grönwall’s inequality (Lemma A.5), we have ∀t ∈ [0, η]: T +K,1,t K,1,t ∂Dα (πR ∥πU ) T +K K ≤ Dα (h♯ πR ∥h♯ πU ) exp ∂t
Z t
2σ 2 − ds αC 0 2tσ 2 T +K K ≤ Dα (h♯ πR ∥h♯ πU ) exp − αC 14
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Thus, by setting t = η and using similar steps as the non convex proof above, we get the following result: 2Kησ 2 T +K K T T Dα (πR ∥πU ) ≤ Dα (πR ∥πL ) exp − αC The message conveyed by the strongly convex proof is that if we have a universal iteration independent upper bound on the log Sobolev constants at each timestep of the PNGD updates, then we could have a more meaningful upper bound on the Rényi divergence. The non convex Equation (3) and convex Equation (4) recurrence bounds are non contractive and iteration dependent, so they do not allow to establish a convergence rate for Theorem 3.2. This is where the projection step of PNGD comes in handy, as it allows to leverage the geometry of the set Θ to get a more informative bound: Lemma A.7 (Log Sobolev inequality on measures supported on a compact set (Chen et al., 2021), Corollary 1). Let π be a probability measure on Rd supported on a compact set Θ with radius R ≥ 0. Then, for each t ≥ 0, µ ∗ N (0, tId ) satisfy a log sobolev inequality with constant C controlled by: 2 4R C ≤ 6 4R2 + t exp t Proposition A.1 (Universal bound on the log Sobolev constants of distributions induced by PNGD updates (Chien et al., 2024a)). Suppose that L is M Lipschitz. Let θ0 ∼ π0 ∈ P(Θ) where Θ is a compact set of radius R and denote by πk the distribution θk , the k-th iterate of PNGD (Equation (1)). Then, ∀k ≥ 0, πk satisfies a log-Sobolev inequality with constant Ck controlled by: 4(R + ηM )2 Ck ≤ 6 4(R + ηM )2 + 2ησ 2 exp 2ησ 2 We can thus derive a similar bound to the strongly convex setting, for the non convex/convex settings: )2 K Using Proposition A.1, we have ∀k ≥ 0 that πU satisfies a C̃ = 6 4(R + ηM )2 + 2ησ 2 exp 4(R+ηM log Sobolev 2 2ησ inequality. Thus, using Lemma A.4, we have: T +K,1,t K,1,t ∂Dα (πR ∥πU ) 2σ 2 T +K,1,t K,1,t Dα (πR ∥πU ) ≤− ∂t αC̃
Thus, by Grönwall’s inequality (Lemma A.5), we have ∀t ∈ [0, η]: T +K,1,t K,1,t ∂Dα (πR ∥πU ) T +K K ≤ Dα (h♯ πR ∥h♯ πU ) exp ∂t
Z t
2σ 2 ds − αC̃ 0 2tσ 2 T +K K ≤ Dα (h♯ πR ∥h♯ πU ) exp − αC̃
Finally, similarly to the strongly convex proofs, we can deduce that: T +K K T T Dα (πR ∥πU ) ≤ Dα (πR ∥πL ) exp
2Kησ 2 − αC̃
B. On training with public data B.1. Proof of Theorem 3.1 Theorem 3.1 (The role of public data in shrinking the learning / retraining mismatch.). Suppose that the loss is L-smooth and M -Lipschitz, and that the initialization distribution satsifies a C0 -log Sobolev inequality. Moreover, suppose that the PNGD updates project onto a compact set Θ of radius R. T Then at learning iteration T, we have the following upper bound on the Rényi divergence between the retraining πR and T learning πL distributions: −1 TY −1 T T 2M 2 η 2 n2forget TX Dα (πR ∥πL ) ≤ h(t′ , η, σ), α (npub + npriv )2 σ 2 t=1 ′ t =t
15
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
−1 2K 2 −1 where h(t′ , η, σ) = 1 + Cησ′ , and 0 < Ct′ ,1 ≤ (1 + ηL)2K C0 + 2ησ 2 (1+ηL) (1+ηL)2 −1 are log Sobolev constants of the t ,1 distributions of the intermediate PNGD updates. Using the support’s radius allows to loosely upper bound those constants 4τ (Chien et al., 2024a): Ct′ ,1 ≤ 6e ησ2 (4τ 2 + ησ 2 ) with τ = R + ηM . Proof. The following proof is an adaptation of the proof of Theorem 3.2 in Chien et al. (2024a) to the asymmetric data setting. Consider the following updates done during training. Recall that we are using full batch projected noisy gradient descent: h i p t+1 t t θL = ΠΘ θL + η∇LDpub ∪Dpriv (θL ) + 2ησ 2 Wt (Wt ∼ N (0, Id )) i h p t+1 t t (Wt ∼ N (0, Id )) θR = ΠΘ θR + η∇LDretain (θR ) + 2ησ 2 Wt Let’s divide each optimization step into the following: p t,1 t t θL = θL + η∇LDpub ∪Dpriv (θL ) + ησ 2 Wt p t,1 t t θR = θR + η∇LDretain (θR ) + ησ 2 Wt Therefore, we can write h i p t,1 t+1 θL = ΠΘ θL + ησ 2 Wt i h p t,1 t+1 θR = ΠΘ θR + ησ 2 Wt .
(5) (6)
t,1 t,1 t t,1 t,1 t t t , θR , θL , θL , πL be the distributions of respectively θR , πR , πL Let πR t t The main question we try to tackle here is: what is Dα (πR ∥πL )? t,1 t,1 We first compare the distributions πR and πL . By composition theorem of the Gaussian mechanism for Rényi Differential privacy (Mironov, 2017), and equivalently for the Rényi divergence, we have: t,1 t,1 t t Dα (πR ∥πL ) ) ∆2F ∥πL Dα (πR ≤ + 2 (7) α α 2σ where ∆F is the l2 sensitivity of the gradient update. For the next computations, let npub denote the number of public points, nforget denote the number of points to forget, and nr−priv denote the number of remaining private points in the retain set. Computing the sensitivity in the asymmetric setting yields:
∆F = max η∥∇LDretain (θ) − ∇LDpub ∪Dpriv (θ)∥ θ
X X 1 1 ∇ℓ(θ, di ) − ∇∥ℓ(θ, di )∥ θ npub + nr−priv npub + nr−priv + nforget di ∈I∪II di ∈I∪II∪III X 1 1 ≤η − ∥∇ℓ(θ, di )∥ npub + nr−priv npub + nr−priv + nforget di ∈I∪II X η + ∥∇ℓ(θ, di )∥ npub + nr−priv + nforget di ∈I∪II∪III 1 1 nforget M η ≤ M η(npub + nr−priv ) − + npub + nr−priv npub + nr−priv + nforget npub + nr−priv + nforget 2M ηnforget ≤ npub + nr−priv + nforget | {z } = max η∥
ε
Lemma B.1. (Ye & Shokri, 2022) For any distributions ξt , ξt′ both satisfying Ct,1 -LSI, we have: −1 Dα(t) (ξt , ξt′ ) Dα (ξt ∗ N (0, ησ 2 I), ξt′ ∗ N (0, ησ 2 I)) ησ 2 ≤ 1+ α α(t) Ct,1 16
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
where α(t) =
α−1 ησ 2 1+ C
t,1
By combining the data processing inequality (projection) and Lemma B.1, we get the following recurrence inequality: ! −1 T +1 T +1 T T Dα(T ) (πR ∥πL ) Dα (πR ∥πL ) ε2 ησ 2 ≤ + 2 1+ α α(T ) 2σ CT,1 −1 −1 T T Dα(T ) (πR ∥πL ) ε2 ησ 2 ησ 2 = 1 + + 1 + 2σ 2 CT,1 α(T ) CT,1 ! −1 −1 −1 T T 2 2 Dα(T −1) (πR ∥πL ) ησ ε ε2 ησ 2 ησ 2 1+ + ≤ + 2 1+ 1+ 2σ 2 CT,1 α(T − 1) 2σ CT,1 CT −1,1 ! T T Dα(T −2) (πR ∥πL ) ε2 ε2 ≤ [B(T ) + B(T − 1)] + B(T − 2) + 2 2 2σ α(T − 2) 2σ −1 QT 2 (where B(t) = k=t 1 + Cησk,1 ) ! T T T Dα(0) (πR ∥πL ) ε2 ε2 X + 2 ≤ B(i) + B(0) 2 2σ i=1 α(0) 2σ T
ε2 X B(i) 2σ 2 i=0 −1 T T ε2 X Y ησ 2 = 1+ 2σ 2 t=0 ′ Ct′ ,1
(since Dα(t) (π0 ∥π0 ) = 0)
≤
t =t
The upper bound on the log Sobolev constants can be tracked in a similar fashion as in Proposition A.1 because of the projection onto the compact set Θ. Corollary 3.1 follows immediately from the previous theorem: Corollary 3.1 (LU noise vs ALU noise). Consider the setting where the forget set size constitutes a constant fraction of the 2 2 private data (i.e., nforget = cnpriv for some c ∈ (0, 1]). Let σsym and σasym be the noise variances required to bound the Rényi divergence between the learning and retraining distributions by a fixed ε in the symmetric and asymmetric settings, respectively. These variances satisfy the following lower bounds: 2M 2 σsym ≥ 2M 2 σasym ≥
−1 TY −1 2 2 2 T X
η c ε
h(t′ , η, σ),
t=1 t′ =t T −1 TY −1 X
2 2 2
η c ε
!
′
h(t , η, σ)
t=1 t′ =t
npriv npriv + npub
2
Starting with the bound of Theorem 3.1, we have: T T Dα (πR ∥πL )≤
−1 TY −1 2αM 2 η 2 n2forget TX h(t′ , η, σ). (npub + npriv )2 σ 2 t=1 ′ t =t
B.2. Proof of Corollary 3.1 One sufficient condition to satisfy an upper bound ε on the Rényi divergence is: −1 TY −1 2αM 2 η 2 n2forget TX h(t′ , η, σ) ≤ ε (npub + npriv )2 σ 2 t=1 ′ t =t
⇐⇒
−1 TY −1 2αM 2 η 2 n2forget TX h(t′ , η, σ) ≤ σ 2 . (npub + npriv )2 ε t=1 ′ t =t
17
.
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data n
n
n
n
forget forget priv forget Since npublic +npriv = npriv npublic +npriv , we set c = npriv and can thus write:
T −1 T −1
2αM 2 η 2 c2 X Y σ ≥ ( h(t′ , η, σ)) ε ′ t=1 2
t =t
npriv npublic + npriv
2 (8)
When the loss is m-strongly convex, we can also derive a right hand side that is completely independent of σ: σ2 ≥
4αc2 M 2 (1 − exp(−mηT )) εm
npriv npublic + npriv
2 (9)
Compressed Version B.3. Numerical Setup for Strongly Convex Losses Following Chien et al. (2024a), we evaluate our bounds using binary logistic regression on D = {(xi , yi )}ni=1 : L(θ, D) = −
λ 2 1 Pn T i=1 log s(yi θ xi ) + 2 |θ|2 n
where s(·) is the sigmoid function. To ensure M -Lipschitzness, gradients are clipped during training, which preserves the λ-strong convexity and ( 14 + λ)-smoothness of the objective (Ye & Shokri, 2022).For the results in Figure 2, we adopt the MNIST configuration from Chien et al. (2024a): λ = 0.0119, T = 104 , npriv = 3000, M = 1, α = 2, and η = 1/L. We set the target privacy budget to ε = 1 and vary the forget set fraction to compute Equation (9).
C. Proof of Theorem 4.1 Proposition. Assuming the data generating distributions share the same support, that the weight space Θ is compact and that the loss is M -Lipschitz wrt θ, we have the following upper bound on the generalization error on the private data after T performing K iterations of unlearning, and initializing a weight θ0 from πL : Eθ∼πU Ex∼Ppriv [L(θ, x)] ≤ exp |
npub D∞ (Ppriv ∥Ppub ) Eθ∼πR [Ed∼Ptrain [L(θ, d)]] + npub + nretain {z } distribution mismatch penalty
r M × diam(Θ) ×
1 Dα (πR ∥πU ) 2 | {z }
unlearning approximation error
where D∞ (P ∥Q) = log ess supx∼Q p(x) q(x) is the infinite Rényi divergence (worst case regret (Erven & Harremoës, 2014)) and ptrain denotes the mixture of distributions Dpub and Dpriv used for training the model. In order to prove Theorem 4.1, we will use the following quantities to define a set of preliminary lemmas. C.0.1. P ERFORMANCE ON THE TRAINING DISTRIBUTION MIXTURE Definition C.1 (Wasserstein distance). The Wasserstein-1 distance is defined as Z W1 (µ, ν) = inf d(x, y) dγ(x, y), γ∈Π(µ,ν)
X ×X
where: • µ and ν are probability measures on a metric space (X , d), • d(x, y) is the distance between points x, y ∈ X , 18
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
• Π(µ, ν) is the set of all couplings of µ and ν, i.e., the set of joint distributions γ on X × X such that the marginals of γ are µ and ν: Z Z γ(x, y) dy = µ(x), γ(x, y) dx = ν(y). X
X
Definition C.2 (Total Variation Distance). Let P and Q be two probability measures on a measurable space (Ω, F). The total variation distance between P and Q is defined as T V (P, Q) = sup |P (A) − Q(A)| (10) A∈F Z 1 = |dP − dQ| (11) 2 Ω 1 = ∥P − Q∥T V . (12) 2 Theorem C.1. (Kantorovich Rubinstein’s duality, (Villani et al., 2009), Theorem 5.10) If µ, ν have a bounded support Ω, then W1 (µ, ν) = sup Ex∼µ [h(x)] − Ey∼ν [h(y)],
(13)
∥h∥L ≤1
where ∥h∥L ≤ 1 denotes the set of 1-Lipschitz functions on Ω Let f : Θ → R such that f (θ) = ED∼Ptrain [LD (θ)], where Ptrain denotes the training data distribution (a mixture of Ppriv and Ppub . Since L(., D) is M −Lipschitz, so is f . Then, we have that: E θ∼πU [L(θ, D)] − E θ∼πR [L(θ, D)] = Eθ∼πU [f (θ)] − Eθ∼πR [f (θ)] D∼Ptrain
(Fubini’s theorem)
D∼Ptrain
≤ M × W1 (πU , πR )
(By Theorem C.1)
Now, we need to find an upper bound on the 1-Wasserstein distance in terms of the Rényi divergence between πR and πU . The following results will be useful in deriving it: Proposition C.1. (Pinsker’s inequality) For two probability distributions P, Q, we have 2T V (P, Q)2 ≤ KL(P ||Q).
(14)
Proposition C.2. (Monotonicity of Rényi divergence, (Erven & Harremoës, 2014)) For 1 ≤ α1 ≤ α2 and probability measures P, Q, KL(P ||Q) ≤ Dα1 (P ||Q) ≤ Dα2 (P ||Q). The KL lower bounds any Rényi divergence since it is obtained by the limit α → 1. Proposition C.3. (Upper bounding W1 with T V (Gibbs & Su, 2002)) If the distributions P, Q share a support Ω and diam(Ω) = sup(x,y)∈Ω×Ω d(x, y) is finite, then we have W1 (P, Q) ≤ diam(Ω)T V (P, Q).
(15)
Using the results above, we have Eθ∼πU [f (θ)] − Eθ∼πR [f (θ)] ≤ M W1 (πU , πR ) ≤ M × diam(Θ) × T V (πU , πR ) r 1 ≤ M × diam(Θ) × KL(πU , πR ) 2 r 1 ≤ M × diam(Θ) × Dα (πU , πR ) 2
(By Proposition C.3 and compactness of Θ) (By Proposition C.2) (By Proposition C.2)
Thus, we obtain that the generalization error of learning + unlearning is upper bounded by: Proposition C.4. Assuming that L is M -Lipschitz, we have r Eθ∼πU [ED∼Ptrain [L(θ, D)]] ≤ Eθ∼πR [ED∼Ptrain [L(θ, D)]] + M × diam(Θ) × 19
1 Dα (πU ∥πR ) 2
(16)
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
C.0.2. A DAPTING THE BOUND TO T HEOREM 4.1 We would like to evaluate the performance of the model obtained after unlearning. Proposition C.4 provides a generalization bound on a mixture of distributions, namely on public data + private data. In most practical scenarios, one would want to quantify the ”lost” performance on private data after forgetting one of its subsets. Thus, we would like to upper bound the quantity EπU ED∼Ppriv [LD (θ)] . The training data distribution used for either retraining or unlearning can be considered as generated from a mixture of the distributions I and II. Assuming the sampling proportions for training are consistent, one can write that the data distribution used in retraining is Ptrain =
npub nr−priv Ppub + Ppriv . npub + nr−priv npub + nr−priv
Fix any θ ∈ Θ. We have that ED∼Ptrain [L(θ, D)] =
nr−priv npub ED∼Ppub [L(θ, D)] + ED∼Ppriv [L(θ, D)] npub + nr−priv npub + nr−priv Z
ED∼Ppriv [L(θ, D)] =
ppriv (x)L(θ, x)dx
ppriv (x) L(θ, x)dx ptrain (x) ptrain (x) ppriv (x) = Ex∼Ptrain L(θ, x) ptrain (x) Z
=
≤ Ed∼Ptrain [ess supx∈Supp(Ppub )∪Supp(Ppriv )
pppriv (x) L(θ, d)] ptrain (x)
ppriv (x) Ed∼Ptrain [L(θ, d)] ptrain (x) ≤ exp(D∞ (Ppriv , Ptrain ))Ed∼Ptrain [L(θ, d)]. ≤ ess supx∈Supp(Ppub )∪Supp(Ppriv )
Moreover, we have by convexity of the Rényi divergence (Erven & Harremoës, 2014) in its second argument that D∞ (Ppriv ∥Ptrain ) ≤
npub (Ppriv ∥Ppub ). npub + nr−priv
Thus we also have Ed∼Ppriv [L(θ, d)] ≤ exp
npub D∞ (Ppriv ∥Ppub ) Ed∼Ptrain [L(θ, d)]. npub + nr−priv
(17)
Thus, we can adapt proposition C.4 to evaluate the risk only on private data. Note that so far, the only assumption made on the difference between the data generating distributions I and II is that they share the same support. The following bound might be refined with additional assumptions, such as covariate shift or conditional shift. We can thus take the expectation of θ with respect to πU to get Eθ∼πU Ed∼Ppriv [L(θ, d)] ≤ exp
npub D∞ (Ppriv ∥Ppub ) Eθ∼πU [Ed∼Ptrain [L(θ, d)]] , npub + nr−priv
and using proposition C.4 to upper bound Eθ∼πU [Ed∼Ptrain [L(θ, d)]], we prove proposition 4.1: npub D∞ (Ppriv ∥Ppub ) Eθ∼πR [Ed∼Ptrain [L(θ, d)]] + npub + nretain r 1 M × diam(Θ) × Dα (πR ∥πU ). 2
Eθ∼πU Ex∼Ppriv [L(θ, x)] ≤ exp
20
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
C.1. Retraining performance bound on the training error T [Ex∼p (Eθ∼πR train [L(θ, x)]]): The upper bound could be further improved to include the optimal distribution, i.e by linking T [Ex∼p Eθ∼πR train [L(θ, x)]] to arg minπ∈P(Rd ) Eθ∼π [Ex∼ptrain [L(θ, x)]]. However, standard generalization bounds for Langevin dynamics (Raginsky et al., 2017; Xu et al., 2018) do not directly apply to our setting due to the projection operator ΠΘ in the PNGD updates. These classical results focus on unconstrained non-convex optimization, whereas our bounded domain introduces additional complexity. The most relevant analysis we are aware of is Lamperski (2020), who study generalization properties of projected Stochastic Gradient Langevin Dynamics, though their work considers the infinite-data regime.
D. When to unlearn, when to retrain ? In the following section, we will assume that the loss function is m-strongly convex to simplify the computations. Nonconvex analysis follows the same flavor, but is hardly interpretable due to the presence of the log-Sobolev constants. As a reminder of ALU, we remind the reader that (1) one learns the whole dataset through T iterations of PNGD, (2) unlearns by fine-tuning on the retain set using the same PNGD updates. As opposed to (Chien et al., 2024a;b) that defines the retraining cost as the number of PNGD steps required to get ε-close to the stationary distribution of retraining from scratch, we define the cost of retraining as T , i.e the same number of steps used to train the model prior to unlearning. This is a more realistic setting in practice as practitioners may choose the number of training steps to be an arbitrary number. The cost of T +K K unlearning is defined as the minimum amount of unlearning iterations, K, so that Dα (πR ∥πU ) ≤ ε, for a given ε > 0. The following result gives a sufficient condition on when ALU is more advantageous than retraining, under the assumption that the loss is m-strongly convex. Note that a similar but hard-to-interpret result could be derived for non-convex losses, due to the presence of the log-Sobolev constants. Proposition D.1 (Sufficient condition guaranteeing that ALU is more efficient than retraining). Assume that the conditions of Theorem 3.2 are satisfied, and that the loss function is m-strongly convex. Then, a sufficient condition guaranteeing that unlearning is more advantageous than retraining is Cα log 2σ 2 η
4αM 2 n2forget mεσ 2 (npublic + npriv )2
! < T − log (1 − exp(−mηT )) .
Proof. Using the results from Theorems 3.1 and 3.2, with the assumption that the loss is m-strongly convex, we have that: T +K K T T Dα (πR ∥πU ) ≤ Dα (πR ∥πL ) exp
2Kσ 2 η − Cα
.
By setting the right hand side to be less than ε, we obtain a sufficient condition on K: 2Kσ 2 η T T Dα (πR ∥πL ) exp − ≤ε Cα T T Dα (πR ∥πL ) Cα log ε ⇒ ≤ K. 2σ 2 η Therefore, a sufficient condition for unlearning to be computationally more efficient than retraining is: Cα log
4αM 2 n2forget εmσ 2 (npublic +npriv )2
2σ 2 η
≤ T − log(1 − exp(−mηT )).
(By Theorem 3.1 and strong convexity of the loss)
This bound contains many dependencies between the control knobs that practitioners have in hand thanks to ALU. We ask the following questions: 21
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Small number of learning iterations: To analyze the computational advantage in this regime, we examine the sufficient condition when T is small. Using the first-order Taylor approximation 1 − exp(−mηT ) ≈ mηT and noting that for small 2 T , the term exp(− 2σCαηT ) ≈ 1, the inequality yields: 4αM 2 n2forget εmσ 2 (npublic + npriv )2
!
2σ 2 η (T − log(mηT )) Cα 2 2 2 nforget εmσ 2 npriv exp 2σ ηT exp − 2σ η log(mηT ) × ≤ ⇒ npublic + npriv npriv 4αM 2 Cα Cα {z } | log
≤
≈1
⇒
npriv nforget × npublic + npriv npriv
2
2
≤
−2σ 2 η εmσ Cα (mηT ) 4αM 2
n
denote the fraction of private data that needs to be forgotten, we have: Letting c = nforget priv
npriv npublic + npriv ⇒(
2
−2σ 2 η
εmσ 2 (mηT ) Cα ≤ 4αM 2 c2
2σ 2 η npublic 4αM 2 c2 (mηT ) Cα + 1)2 ≥ 2 npriv εmσ √ σ2 η σ2 η 2 αM (mη) Cα npublic 1 nforget ≥ ×T Cα × √ × ⇒ −1 npriv m npriv ε | {z }
Const.
In the regime where T is small, the feasibility of unlearning is subject to a trade-off between the forget ratio, ε, and the n n available public data. This relationship is formally captured by the inequality npublic + 1 ≥ C · T β · ε−1/2 · nforget , where priv priv 2 β = σ η/Cα. In the private-only scenario where npublic = 0, the efficiency of unlearning is limited; the√algorithm only n remains faster than retraining if the fraction of data to be forgotten is sufficiently small to satisfy nforget ≤ CTεβ . Under these priv conditions, attempting to unlearn a larger portion of the dataset or imposing a stricter privacy guarantee (smaller ε) forces the unlearning iterations K to surpass the original training budget T , rendering retraining a more viable option. However, the introduction of public data (npublic > 0) provides a computational buffer that fundamentally alters this dynamic. By increasing the ratio npublic /npriv , practitioners can compensate for high forget ratios or stringent privacy requirements, ensuring that the gradient updates remain stable and non-private enough to allow K < T . Large number of training iterations (training to convergence) In this case, (Chien et al., 2024a) proved that the computational benefit of unlearning against retraining has a non-negligible benefit, that scales as O(log(ntotal )), with probability 1 − R1d .
E. Langevin Unlearning pseudo-code Algorithm 1 Training with Projected Noisy Gradient Descent (PNGD) 1: θ0 ∼ π0 {Sample from initialization distribution} 2: for t = 0 to T − 1 do 3: gt ← ∇θ LD (θt ) {Compute gradient on full dataset} 4: ξt ∼ N (0, 2ησ 2 Id ) {Sample Gaussian noise} 5: θt+1 ← ΠΘ [θt − ηgt + ξt ] {Update and project} 6: end for 7: return θT
22
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Algorithm 2 Langevin Unlearning 1: θ0U ← θT {Initialize from trained model} 2: for k = 0 to K − 1 do 3: gk ← ∇θ LDretain (θkU ) {Compute gradient on retain set only} 4: ξk ∼ N (0, 2ησ 2 Id ) {Sample Gaussian noise} U 5: θk+1 ← ΠΘ [θkU − ηgk + ξk ] {Update and project} 6: end for U 7: return θK
F. DomainNet data The following is a snippet of samples from the DomainNet dataset, where we extracted two domains, Clipart and Quickdraw. The classes are aggregated into 24 meta-classes Table 3, following (Peng et al., 2019).
Clipart face
Clipart campfire
Quickdraw face
Quickdraw campfire
Domain Adaptation: Sample Images from Clipart and Quickdraw Clipart toaster
Clipart flashlight
Clipart flamingo
Clipart knee
Quickdraw toaster
Quickdraw flashlight
Quickdraw flamingo
Quickdraw knee
Figure 5. The two domains of public and private data used for Sections 5.1 and 5.2 (Peng et al., 2019). Both datasets share the same number of classes, with Clipart being a collection of stylized images representing the private data, and Quickdraw representing a collection of hand-draw sketches.
Domain Adaptation: Sample Images from Clipart and Quickdraw infograph axe
real axe
infograph mushroom
real mushroom
infograph spider
infograph bathtub
infograph lollipop
infograph stove
real spider
real stove
real bathtub
real lollipop
Figure 6. The two domains of public and private data used for Section 5.2 (Peng et al., 2019). Both datasets share the same number of classes, with Infograph being a collection of stylized images representing the public data, and Real representing a collection of real-life images.
23
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data Table 3. Class aggregation for experimental dataset. Individual classes are grouped into 24 superclasses. Superclass
Individual Classes
Furniture
bathtub, bed, bench, ceiling fan, chair, chandelier, couch, door, dresser, fence, fireplace, floor lamp, hot tub, ladder, lantern, mailbox, picture frame, pillow, postcard, see saw, sink, sleeping bag, stairs, stove, streetlight, suitcase, swing set, table, teapot, toilet, toothbrush, toothpaste, umbrella, vase, wine glass
Mammal
bat, bear, camel, cat, cow, dog, dolphin, elephant, giraffe, hedgehog, horse, kangaroo, lion, monkey, mouse, panda, pig, rabbit, raccoon, rhinoceros, sheep, squirrel, tiger, whale, zebra
Tool
anvil, axe, bandage, basket, boomerang, bottlecap, broom, bucket, compass, drill, dumbbell, hammer, key, nail, paint can, passport, pliers, rake, rifle, saw, screwdriver, shovel, skateboard, stethoscope, stitches, sword, syringe, wheel
Cloth
belt, bowtie, bracelet, camouflage, crown, diamond, eyeglasses, flip flops, hat, helmet, jacket, lipstick, necklace, pants, purse, rollerskates, shoe, shorts, sock, sweater, t-shirt, underwear, wristwatch
Electricity
calculator, camera, cell phone, computer, cooler, dishwasher, fan, flashlight, headphones, keyboard, laptop, light bulb, megaphone, microphone, microwave, oven, power outlet, radio, remote control, spreadsheet, stereo, telephone, television, toaster, washing machine
Building
The Eiffel Tower, The Great Wall, barn, bridge, castle, church, diving board, garden, garden hose, golf club, hospital, house, jail, lighthouse, pond, pool, skyscraper, square, tent, waterslide, windmill
Office
alarm clock, backpack, binoculars, book, calendar, candle, clock, coffee cup, crayon, cup, envelope, eraser, map, marker, mug, paintbrush, paper clip, pencil, scissors
Human Body
arm, beard, brain, ear, elbow, eye, face, finger, foot, goatee, hand, knee, leg, moustache, mouth, nose, skull, smiley face, toe, tooth
Road Transportation
ambulance, bicycle, bulldozer, bus, car, firetruck, motorbike, pickup truck, police car, roller coaster, school bus, tractor, train, truck, van
Food
birthday cake, bread, cake, cookie, donut, hamburger, hot dog, ice cream, lollipop, peanut, pizza, popsicle, sandwich, steak
Nature
beach, cloud, hurricane, lightning, moon, mountain, ocean, rain, rainbow, river, snowflake, star, sun, tornado
Cold Blooded
crab, crocodile, fish, frog, lobster, octopus, scorpion, sea turtle, shark, snail, snake, spider
Music
cello, clarinet, drums, guitar, harp, piano, saxophone, trombone, trumpet, violin
Fruit
apple, banana, blackberry, blueberry, grapes, pear, pineapple, strawberry, watermelon
Sport
baseball, baseball bat, basketball, flying saucer, hockey puck, hockey stick, snorkel, soccer ball, tennis racquet, yoga
Tree
bush, cactus, flower, grass, house plant, leaf, palm tree, tree
Bird
bird, duck, flamingo, owl, parrot, penguin, swan
Vegetable
asparagus, broccoli, carrot, mushroom, onion, peas, potato, string bean
Shape
circle, hexagon, line, octagon, squiggle, triangle, zigzag
Kitchen
fork, frying pan, hourglass, knife, lighter, matches, spoon, wine bottle
Water Transportation
aircraft carrier, canoe, cruise ship, sailboat, speedboat, submarine
Sky Transportation
airplane, helicopter, hot air balloon, parachute
Insect
ant, bee, butterfly, mosquito
Others
The Mona Lisa, angel, animal migration, campfire, cannon, dragon, feather, fire hydrant, mermaid, snowman, stop sign, teddy-bear, traffic light
G. Details about the Rényi estimation G.0.1. N EURAL R ÉNYI ESTIMATION Following the works of Birrell et al. (2021; 2023), two variational representations of the Rényi divergence between two distributions P, Q have been proposed. The first draws inspiration from the Donsker–Varadhan dual representation (Donsker & Varadhan, 1975) of the KL divergence: Theorem G.1 (Donsker–Varadhan Rényi divergence (Birrell et al., 2021)). Let P, Q be two distributions on (Ω, M) and α ∈ R, α ̸= 0, 1. Then, for any set of functions Φ with Mb (Ω) ⊂ Φ ⊂ M(Ω), Z Z Dα (P ∥Q) 1 1 (α−1)ϕ αϕ = sup log e dP − log e dQ . (18) α α ϕ∈Φ α − 1 If in addition (Ω, M) is a metric space with the Borel σ-algebra, then Equation (18) holds for all Φ satisfying Lipb ⊂ Φ ⊂ M(Ω), where Lipb denotes the set of bounded Lipschitz functions. Here, M(Ω) denotes the space of measurable real-valued functions on Ω, and Mb (Ω) the subspace of bounded functions. 24
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
While this representation allows sample-based estimation, it involves exponential terms that yield high-variance estimates in practice. To mitigate this issue, Birrell et al. (2023) proposed a convex conjugate formulation: Theorem G.2 (Convex conjugate Rényi divergence (Birrell et al., 2023)). Let P, Q be probability distributions supported on Ω, with P ≪ Q, and let Mb (Ω) denote the space of bounded measurable functions. Then, for all α ∈ (0, +∞) \ {1}, Dα (P ∥Q) = sup α g∈Mb (Ω), g<0
Z g dQ +
1 α−1
Z
α−1
|g| α dP +
1 (log α + 1). α
(19)
This convex conjugate formulation removes the exponential dependence and provides more stable numerical estimates, making it preferable for our setting. Neural network parameterization. To approximate Φ = {g ∈ M(Θ) : g < 0} we use the class gθ of two-layer MLPs with spectral normalization (Miyato et al., 2018), LeakyReLU activations, and a polysoftplus output activation as in Birrell et al. (2023). The polysoftplus activation offers superior numerical stability compared to ReLU. It is defined as 1 polysoftplus(x) = − 1x<0 + (1 + x)1x≥0 . (20) 1−x The discriminator network gθ is trained to maximize the variational bound in Equation (Lemma A.2) using samples T +K K R N {θiU }N . The optimization objective becomes: i=1 ∼ πU and {θj }j=1 ∼ πR max θ
N 1 X N
gθ (θjR ) +
j=1
N 1 X
1 α − 1 N i=1
α−1 1 |gθ (θiU )| α + (log α + 1) . α
(21)
To reduce estimator variance, we repeat the discriminator training five times with different random initializations and report the average. We use a learning rate of value 0.0001 with Adam optimizer (Kingma & Ba, 2017), and train the discriminators for 30000 epochs with batch size b = 6000. This procedure used N = 30,000 model samples, which makes it computationally intensive and better suited for theoretical validation than for large-scale empirical benchmarking. Although regularization and repeated runs alleviate variance, Rényi divergence estimation remains a statistically challenging task. Developing scalable and lower-variance estimators is therefore an important direction for future work. T +K K G.0.2. S AMPLING FROM πU AND πR
We conduct experiments on the DomainNet dataset (24-class image classification) Figure 5. We choose the domain Clipart as the private data domain, which are stylized images, and Quickdraw, a collection of hand-drawn sketches as the public domain. Image embeddings are extracted using DinoV2 (Oquab et al., 2024), a self-supervised vision transformer. We specifically use vit small patch16 224 dino (Caron et al., 2021). All images are resized to 224 × 224 prior to feature extraction. On these embeddings, we train 30,000 linear classifiers on the full dataset D = Dpub ∪ Dpriv for T = 20 iterations, and subsequently fine-tune them on the retain set Dr = D \ Dforget for K ∈ {1, 5, 10, 15} additional iterations. This procedure K yields 30,000 samples from the unlearning distribution πU . For comparison, we train another 30,000 linear classifiers directly on the retain set Dr for T + K iterations, producing T +K samples from the retraining distribution πR . All models are trained using the same projected noisy gradient descent (PNGD) update with noise scale σ = 0.01, learning rate η = 0.001, batch size b = 1024, and radius R = 1.0 using SGD. To assess robustness across dataset splits, we fix the total training set size to Ntrain = 42,000, and vary the public and forget set sizes as (|Dpub |, |Dforget |) ∈ {(10,000, 12,000), (15,000, 7,000), and (20,000, 2,000)}. The remaining private data in the retain set is fixed to have size 20,000. The resulting divergence estimates are reported in Figures 3a and 3b. G.1. Pseudo-code 25
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
Algorithm 3 Rényi Divergence Estimation via Variational Representation T +K K 1: Input: Samples {θiR }N , {θjU }N i=1 ∼ πR j=1 ∼ πU , order α, discriminator architecture 2: Initialize discriminator network gϕ with spectral normalization 3: for epoch = 1 to num epochs do 4: Sample minibatch from retraining samples {θiR } 5: Sample minibatch from unlearning samples {θjU } 6: Compute variational objective:
L=
N N α−1 1 1 X 1 1 X gϕ (θiR ) + |gϕ (θjU )| α + (log α + 1) N i=1 α − 1 N j=1 α
(22)
7: Update ϕ to maximize L via gradient ascent 8: end for b α (π K ∥π T +K ) = Lb1/α 9: Output: Estimated divergence D U R
H. Evaluation with U-LiRA H.0.1. U-L I RA DETAILS U-LiRA, introduced by Hayes et al. (2025) as an adaptation of the LiRA membership inference attack (Carlini et al., 2021) to the unlearning setting, formalizes unlearning evaluation as a binary hypothesis test. The goal is to distinguish K between two distributions over model parameters: the unlearning distribution πU , obtained by training on the full dataset and subsequently applying the target unlearning algorithm to remove the influence of the forget set, and the retraining T +K distribution πR , obtained by training from scratch without the forget set. Letting P (θ | ·) denote the likelihood of observing model parameters θ under a given distribution, the Neyman–Pearson lemma (Neyman & Pearson, 1933) implies that the most powerful test for this discrimination problem is achieved by thresholding the likelihood ratio K P (θ|πU ) T +K P (θ|πR )
for model parameters θ. T +K K Since directly computing P (θ | πU ) and P (θ | πR ) is infeasible in practice, U-LiRA employs a series of approximations. K First, the two distributions are approximated empirically by sampling: the adversary trains N models under πU (full training T +K followed by unlearning) and N models under πR (training from scratch without the forget set).
To reduce the sample complexity required for a low-variance estimate, U-LiRA projects models into a one-dimensional representation space via a statistic f : Θ → R (since we only run the attack on forget sets of size 1, we follow Hayes et al. (2025) and choose f to be the model’s confidence score on the forget example, rescaled by the logit function ω ϕ(ω) = ln 1−ω ). The test is then conducted on the surrogate likelihood ratio K P (f (θ)|f (πU )) . T +K P (f (θ)|f (πR ))
As a final simplifying approximation, U-LiRA models the projected distributions as Gaussians K 2 f (πU ) ≈ N (µU , σU ),
T +K 2 f (πR ) ≈ N (µR σR ),
2 2 where the parameters (µU , σU ) and (µR , σR ) are estimated directly from the N sample models of each distribution.
In 5.3, we presented the attack through the lens of Bayes’ rule (following Algorithm 1 of Hayes et al. (2025)), providing a more intuitive explanation for readers less familiar with hypothesis testing concepts. H.0.2. E XPERIMENTAL SETUP We evaluate unlearning in binary sentiment classification of IMDB reviews (Maas et al., 2011), with Amazon product reviews (Zhang et al., 2015) as public data. Models are 2-layer LSTMs (Hochreiter & Schmidhuber, 1997), trained to 26
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
minimize cross-entropy loss with projected noisy gradient descent (Gaussian noise variance σ 2 = 0.01, projection onto an ℓ2 ball of radius 100). For each trial, the forget set consists of a 100 datapoints sampled uniformly from the IMDB reviews dataset. Following the U-LiRA framework, we generate 75 model samples from two distributions: K • Unlearning distribution πU : models trained on 25,000 private datapoints plus the forget set for T epochs, then finetuned without the forget set for K epochs. T +K • Retraining distribution πR : models trained from scratch on the same 25,000 private datapoints (excluding the forget set) for T + K epochs.
We repeat this sampling process both with and without the inclusion of the 50,000 public datapoints during training and unlearning.
27