Residual-PAC Privacy: Automatic Privacy Control Beyond the Gaussian Barrier

The Probably Approximately Correct (PAC) Privacy framework [xiao2023pac] provides a powerful instance-based methodology to preserve privacy in complex data-driven systems. Existing PAC Privacy algorithms (we call them Auto-PAC) rely on a Gaussian mutual information upper bound. However, we show that the upper bound obtained by Auto-PAC is tight if and only if under the data distribution, the unperturbed output is Gaussian and the noise is independent Gaussian. We propose two approaches for addressing this issue. First, we introduce two tractable post‐processing methods for Auto-PAC, based on Donsker–Varadhan representation and sliced Wasserstein distances. However, the result still leaves "wasted" privacy budget. To address this issue more fundamentally, we introduce Residual-PAC (R-PAC) Privacy, an f-divergence-based measure to quantify privacy that remains after adversarial inference. To implement R-PAC Privacy in practice, we propose a Stackelberg Residual-PAC (SR-PAC) automatic privatization algorithm, a game-theoretic framework that selects optimal noise distributions through convex bilevel optimization. Our approach achieves efficient privacy budget utilization for arbitrary data distributions and naturally composes when multiple mechanisms access the dataset. Our experiments demonstrate that SR-PAC obtains consistently a better privacy-utility tradeoff than both PAC and differential privacy baselines.