Abstract
A fundamental result in differential privacy states that the privacy guarantees of a mechanism are preserved by any post-processing of its output. In this paper we investigate under what conditions stochastic post-processing can amplify the privacy of a mechanism. By interpreting post-processing as the application of a Markov operator, we first give a series of amplification results in terms of uniform mixing properties of the Markov process defined by said operator. Next we provide amplification bounds in terms of coupling arguments which can be applied in cases where uniform mixing is not available. Finally, we introduce a new family of mechanisms based on diffusion processes which are closed under post-processing, and analyze their privacy via a novel heat flow argument.
Summary
This paper initiates a systematic study of privacy amplification by stochastic post-processing. Given a DP mechanism M producing outputs in X and a Markov operator K defining a stochastic transition from X to Y, the goal is to understand when the post-processed mechanism K composed with M is strictly more private than M alone. The standard post-processing property of DP guarantees K composed with M is at least as private as M; this paper identifies conditions under which privacy strictly improves.
The paper provides three types of amplification results, each associated with a different analytical approach:
1. Amplification from uniform mixing (Section 3). The authors define a hierarchy of mixing conditions for Markov operators — gamma-Dobrushin, (gamma, epsilon)-Dobrushin, gamma-Doeblin, and gamma-ultra-mixing — ordered by increasing strength. Theorem 1 establishes that if M is (epsilon, delta)-DP and K satisfies these conditions, then K composed with M satisfies improved (epsilon’, delta’)-DP guarantees. For example, if K is gamma-Dobrushin, then delta’ = gamma * delta (the delta parameter contracts by the Dobrushin coefficient). The (gamma, epsilon)-Dobrushin condition, which bounds the supremum of the hockey-stick divergence sup_{x,x’} D_{e^epsilon}(K(x) || K(x’)) ⇐ gamma, provides finer control by also amplifying epsilon. These mixing conditions correspond to local DP properties of the kernel K itself.
2. Amplification from couplings (Section 4). This approach generalizes the shifted Renyi divergence technique from Privacy Amplification by Iteration (Feldman et al., 2018) to a general measure-theoretic setting using explicit couplings instead of W_infinity distance. The key result (Theorem 2) states: for mu, nu in P(X), K in K(X, Y), omega in P(X), and pi in C(omega, mu), R_alpha(mu K || nu K) ⇐ R_alpha(omega || nu) + sup_{x in supp(nu)} R_alpha((H_pi K)(x) || K(x)). This is a measure-theoretic generalization of the shift-reduction lemma. The authors apply this to iterated Gaussian and Laplace mechanisms, and to noisy projected SGD with strongly convex losses, obtaining exponential improvement over Feldman et al.’s O(1/r) rate: the per-index RDP bound becomes epsilon_i = (2C^2/((n-i)sigma^2)) * (1 - 2etabetarho/(beta+rho))^{(n-i+1)/2}.
3. Diffusion mechanisms (Section 5). A family of mechanisms based on Markov semigroups (P_t){t>=0} that are closed under post-processing: P_s composed with M_t^f = M{t+s}^f. The main result (Theorem 6) provides generic Renyi DP guarantees via the “intrinsic sensitivity” Lambda(t), computed from the carre du champ operator of the semigroup’s generator. The Gaussian mechanism and the Ornstein-Uhlenbeck mechanism are shown to belong to this family.
Key Contributions
- Systematic framework for amplification by mixing via Markov operators, unifying several mixing conditions (Dobrushin, Doeblin, ultra-mixing) with their implications for privacy amplification.
- Definition of the contraction coefficient for hockey-stick divergence: alpha_epsilon(K) = sup_{x1,x2} D_{e^epsilon}(K(x1) || K(x2)), the key quantity controlling divergence contraction under Markov kernels.
- Measure-theoretic generalization of the shift-reduction lemma from Feldman et al. (2018) via transport operators and couplings (Theorem 2).
- Exponential improvement in privacy amplification by iteration for strongly convex losses, via strict contraction analysis.
- Introduction of diffusion mechanisms closed under post-processing, with the Ornstein-Uhlenbeck mechanism shown to match the optimally post-processed Gaussian mechanism.
Connection to Unlearning
This paper provides two key technical tools used in Certified Unlearning for Neural Networks (Koloskova et al., 2025):
-
hockey-stick divergence contraction under Markov kernels: The data processing inequality D_{e^epsilon}(mu K || nu K) ⇐ alpha_epsilon(K) * D_{e^epsilon}(mu || nu), where alpha_epsilon(K) = sup_{x1,x2} D_{e^epsilon}(K(x1) || K(x2)) is the contraction coefficient, is exactly the mechanism used in Koloskova’s Lemma A.2 and Theorem 4.2 for model clipping for unlearning.
-
Generalized shift-reduction lemma: Theorem 2 provides the coupling-based generalization of Feldman et al.’s shift-reduction lemma that Koloskova et al. adapt for the non-convex gradient clipping for unlearning analysis.