Amplification by mixing is a framework for privacy amplification introduced by Balle et al. (2019) in Privacy Amplification by Mixing and Diffusion Mechanisms. It studies conditions under which stochastic post-processing of a differentially private mechanism M by a Markov operator K produces a composed mechanism K . M that is strictly more private than M alone. The standard post-processing property of differential privacy guarantees K . M is at least as private as M; amplification by mixing identifies conditions on K — formulated as mixing properties of the associated Markov process — under which the privacy guarantee strictly improves.
The framework is organized around a hierarchy of uniform mixing conditions on the Markov operator K, in increasing order of strength: gamma-Dobrushin (sup_{x,x’} TV(K(x), K(x’)) ⇐ gamma), (gamma, epsilon)-Dobrushin (sup_{x,x’} D_{e^epsilon}(K(x) || K(x’)) ⇐ gamma, stated via hockey-stick divergence), gamma-Doeblin (there exists a distribution omega such that K(x) >= (1-gamma)*omega for all x), and gamma-ultra-mixing (K(x) << K(x’) and dK(x)/dK(x’) >= 1-gamma for all x, x’). These conditions correspond to local differential privacy (LDP) properties of K itself: gamma-Dobrushin is equivalent to (0, gamma)-LDP, gamma-ultra-mixing to (log(1/(1-gamma)), 0)-LDP.
The main amplification result (Theorem 1) states that if M is (epsilon, delta)-DP and K satisfies these conditions, the composed mechanism K . M achieves improved guarantees: (1) (epsilon, gammadelta)-DP if K is gamma-Dobrushin; (2) (epsilon, gammadelta)-DP if K is (gamma, epsilon_bar)-Dobrushin with epsilon_bar = log(1 + (e^epsilon - 1)/delta); (3) (epsilon’, delta’)-DP with epsilon’ = log(1 + gamma*(e^epsilon - 1)) and delta’ = gamma*(1 - e^{epsilon’-epsilon}(1-delta)) if K is gamma-Doeblin; (4) (epsilon’, gammadeltae^{epsilon’-epsilon})-DP with epsilon’ = log(1 + gamma(e^epsilon - 1)) if K is gamma-ultra-mixing.
Key Details
- The mixing conditions form a strict hierarchy: gamma-ultra-mixing implies gamma-Doeblin implies gamma-Dobrushin, and (gamma, epsilon)-Dobrushin implies gamma-Dobrushin.
- The (gamma, epsilon)-Dobrushin condition is the most directly relevant to unlearning analysis, as it uses the contraction coefficient alpha_epsilon(K) = sup_{x1,x2} D_{e^epsilon}(K(x1) || K(x2)) to quantify how much the hockey-stick divergence contracts when the kernel K is applied.
- The proofs for the Doeblin and ultra-mixing cases leverage the overlapping mixtures technique from Balle et al. (2018), decomposing distributions into shared and non-shared components.
- Amplification by mixing generalizes privacy amplification by iteration: each step of noisy SGD can be viewed as applying a Markov operator K to the current model distribution, and the mixing/contraction properties of K determine the per-step amplification.
- In Certified Unlearning for Neural Networks, the amplification by mixing framework provides the theoretical basis for the model clipping for unlearning analysis (Theorem 4.2), where each noisy-clipping iteration is a Markov operator whose contraction coefficient is bounded.