A formal definition of approximate machine-unlearning based on Renyi divergence, introduced in CHIEN2024 as an alternative to the standard (epsilon, delta)-unlearning definition.
Definition (Renyi Unlearning): Consider a randomized learning algorithm M and a randomized unlearning algorithm U. We say (M, U) achieves (alpha, epsilon)-RU if for any alpha > 1 and any adjacent datasets D, D’ (differing in one data point), the alpha Renyi difference satisfies:
d_alpha(rho, nu’) ⇐ epsilon
where U(M(D), D’) ~ rho and M(D’) ~ nu’. The alpha Renyi difference is defined as:
d_alpha(nu, nu’) = max(D_alpha(nu || nu’), D_alpha(nu’ || nu))
where D_alpha is the alpha Renyi divergence: D_alpha(nu || nu’) = (1/(alpha - 1)) * log(E_{x ~ nu’}[(nu(x)/nu’(x))^alpha]). See MIRONOV2017 for the original RDP definition and properties.
This definition relates to standard (epsilon, delta)-unlearning via the RDP to epsilon-delta DP conversion lemma (Proposition 3 in MIRONOV2017), making it interchangeable with the definition used in ZHANGB2024 and other works. The Renyi divergence formulation is particularly natural for the PNSGD-based analysis because the privacy amplification by iteration framework (Lemma 2.6) directly produces Renyi divergence bounds from W-infinity distance bounds.
A key advantage of working with Renyi divergence is that it provides tighter composition guarantees for sequential operations compared to (epsilon, delta)-DP composition. However, a disadvantage is that its weak triangle inequality (which doubles the order alpha) can lead to degraded bounds for sequential certified unlearning, motivating the W-infinity-based analysis in CHIEN2024.