A theoretical technique introduced in CHIEN2024 for establishing tight certified unlearning guarantees. The key idea is to track the infinite Wasserstein distance (W_infinity) between the distributions of two PNSGD processes running on adjacent datasets (differing in one data point) as they evolve over training iterations.
The W_infinity distance between distributions mu and nu on (R^d, || . ||) is defined as:
W_infinity(mu, nu) = inf_{gamma in Gamma(mu, nu)} ess sup_{(x,y) ~ gamma} ||x - y||
where Gamma(mu, nu) is the set of all couplings. This is a true metric (satisfying the standard triangle inequality), unlike Renyi divergence which only satisfies a weak triangle inequality that doubles the divergence order alpha.
The central result (Lemma 3.3 in CHIEN2024) bounds the W_infinity distance between adjacent PNSGD learning processes for a fixed mini-batch sequence B:
W_infinity(nu_{T|B}^0, nu_{T|B}^{0,prime}) ⇐ min((1 - c^{Tn/b}) / (1 - c^{n/b}) * c^{n/b - j_0 - 1} * 2etaM/b, 2R)
where c = 1 - eta*m is the contraction rate, M is the Lipschitz constant, b is the mini-batch size, and j_0 identifies which mini-batch contains the differing data point. This is substantially tighter than the naive bound of 2R (the projection set diameter) used in prior work.
The tighter W_infinity bound has two critical consequences:
-
Better single-request unlearning: Through privacy amplification by iteration (Lemma 2.6), a tighter Z_B leads to exponentially smaller Renyi divergence bounds, making the unlearning guarantee non-vacuous.
-
Better sequential unlearning: Because W_infinity satisfies the standard triangle inequality, the bound for s sequential unlearning requests grows as Z_B^{(s+1)} = min(c^{K_s n/b} * Z_B^{(s)} + Z_B, 2R), which is linear in the number of requests. This contrasts with Langevin-dynamics-based analyses that use the weak triangle inequality of Renyi divergence, doubling the order alpha at each step and leading to exponential degradation.
This technique is also noted to be of independent interest for tightening differential privacy guarantees of PNSGD more broadly.