Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization
Tao Zhang, Yevgeniy Vorobeychik · 2025
Read Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization by Tao Zhang, Yevgeniy Vorobeychik (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06530.txt.
Introduction
Tao Zhang and Yevgeniy Vorobeychik set out a new privacy frame that frees a past one from a tight bind to one chance form. Their paper is from two thousand twenty-five.
The past frame, PAC Privacy, gives a case-by-case way to guard data in complex systems. Its known tools rest on a cap tied to bell-shaped noise. The team shows that cap is tight just when the output and noise are jointly of that shape. They give two fix steps that work past that case. Waste of the privacy spend is left, though. Their new frame gauges what privacy is left after a foe's best guess, by a broad gap gauge. A game form picks the best noise.
Catalog record
| CREATOR | Tao Zhang, Yevgeniy Vorobeychik |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 102 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06530
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization Tao Zhang, Yevgeniy Vorobeychik Abstract The Probably Approximately Correct (PAC) Privacy framework [ 1 ] provides a powerful instance-based methodology for certifying privacy in complex data-driven systems. However, existing PAC Privacy algorithms rely on a Gaussian mutual information upper bound. We show that this is in general too conservative: the upper bound obtained by these algorithms is tight if and only if the perturbed mechanism output is jointly Gaussian with independent Gaussian noise. To address the inefficiency inherent in the Gaussian-based approach, we introduce Residual-PAC (RPAC) Privacy , an f f -divergence-based measure that quantifies the privacy remaining after adversarial inference. When instantiated with Kullback–Leibler divergence, Residual-PAC Privacy is governed by conditional entropy. Moreover, we propose Stackelberg Residual-PAC (SR-PAC) privatization mechanisms for RPAC Privacy, a game-theoretic framework that selects optimal noise distributions through convex bilevel optimization. Our approach achieves tight privacy budget utilization for arbitrary data distributions. Moreover, it naturally composes under repeated mechanisms and provides provable privacy guarantees with higher statistical efficiency. Numerical experiments demonstrate that SR-PAC certifies the target privacy budget while consistently improving utility compared to existing methods. I Introduction Artificial intelligence systems now operate across increasingly critical domains—from healthcare diagnostics and autonomous transportation to personalized financial services and national security infrastructure. While demonstrating powerful capabilities, these data-driven systems introduce significant privacy risks as their training and operational data becomes increasingly sensitive and complex. Individual information can be inadvertently exposed through seemingly harmless outputs. Given the expanding scale of modern data pipelines, robust and reliable privacy guarantees have become essential rather than merely desirable. The past two decades have witnessed the emergence of numerous privacy definitions and frameworks designed to address information leakage risks. Among these, Differential Privacy (DP) [ 2 ] stands as perhaps the most influential, providing strong worst-case guarantees against adversarial inference. In its canonical formulation, DP quantifies the maximum change in output probabilities induced by modifying a single data point, thereby ensuring indistinguishability between neighboring datasets. This theoretical foundation has inspired substantial research and practical deployment in tools used by major organizations (e.g., Apple [ 3 ] ) and governments (e.g., US Census Bureau [ 4 ] ). Other privacy notions, such as Maximal Leakage [ 5 , 6 ] , mutual information-based criteria, such as Mutual Information Differential Privacy (MI-DP) [ 7 ] , and Fisher information-based metric [ 8 , 9 , 10 ] , have been proposed to capture different adversarial models and to offer alternative trade-offs between privacy and utility. Provable privacy guarantees for modern data‐processing algorithms face two major obstacles. First, worst‐case frameworks like DP require computing global sensitivity, which is generally intractable (NP-hard [ 11 ] ). In addition, computing the optimal privacy bound of DP under composition is, in general, a #P-complete under composition task [ 12 ] . Likewise, enforcing MI-DP requires a white-box analysis of every possible input distribution, which is seldom available. In practice, finding the minimal noise needed to meet a target guarantee is intractable for most real-world algorithms, especially when the effect of each operation on privacy is unclear. Empirical or simulation-based methods (e.g., testing resistance to membership inference [ 13 ] ) address specific threats but lack rigorous, adversary-agnostic assurances. Bridging this gap requires a new, broadly applicable framework that can quantify and enforce privacy risk without relying on ad-hoc sensitivity analyses. A promising alternative has recently emerged: the Probably Approximately Correct (PAC) Privacy framework [ 1 ] . Drawing inspiration from PAC learning theory [ 14 ] , PAC Privacy fundamentally redefines the privacy objective as the information-theoretic hardness of reconstructing sensitive data given arbitrary information disclosure processing. PAC Privacy shifts the paradigm from indistinguishability to inference impossibility by characterizing the probability that any adversary—regardless of strategy or computational power—can accurately infer private data under a specified reconstruction criterion. At the heart of PAC Privacy lies the concept of PAC Advantage Privacy (PAC-AP) , which extends the framework to arbitrary adversarial inference tasks by quantifying the adversary’s improvement in success probability through an f -divergence measure. When the f -divergence is instantiated as the Kullback–Leibler (KL) divergence, PAC-AP specializes to a mutual information-based criterion, providing a natural and information-theoretic characterization of privacy risk. A closed-form upper bound on mutual information—derived from the maximum entropy property of the Gaussian distribution—serves as the foundation for automatic PAC privatization algorithms, which operate via end-to-end black-box simulations. This approach circumvents the need for direct mutual information computation and enables practitioners to certify privacy risk with high statistical confidence, even when the internal structure of the data processing mechanism is unknown or intractable. In addition, PAC Privacy also enjoys elegant composition properties: when the composed mechanisms are independent, the total privacy loss can be bounded by the sum of the individual mutual information budgets. However, the upper bound provided by automatic PAC Privacy algorithms (see Theorem 3 and Corollary 2 of [ 1 ] , and Theorem 1 of [ 15 ] ) is generally conservative. In particular, for a given privacy budget, the mutual information achieved under the noise distribution constructed by these algorithms is strictly less than the designated privacy budget unless the mechanism output is Gaussian and the noise is independent, zero-mean Gaussian. The privacy budget is exactly attained—i.e., the true mutual information matches the privacy bound—if and only if these Gaussian conditions hold. As a result, this conservativeness leads to a “waste” of privacy budget. To maximize privacy budget efficiency, PAC Privacy defines optimal perturbation (Definition 9 of [ 1 ] ) as the noise distribution that minimizes utility loss (e.g., \ell_{2} norm or noise power) while ensuring the mutual information remains within the privacy budget. Crucially, this mutual information constraint intricately links the noise distribution to both the data distribution and mechanism, often making the identification of optimal noise intractable, especially when the joint distribution lacks a closed-form or exhibits complex dependencies. We address the limitations imposed by the conservativeness of automatic PAC Privacy algorithms. First, we introduce the notion of Residual-PAC Privacy , using f -divergence, to quantify the privacy that remains after information has been leaked by a data processing mechanism. While PAC-AP measures the amount of privacy loss incurred by a given mechanism, our Residual-PAC Privacy framework provides a complementary perspective by characterizing the remaining privacy guarantee that persists despite adversarial inference. When f -divergence is instantiated as KL divergence, our Residual-PAC Privacy is fully characterized by the conditional entropy up to a known constant that does not depend on the mechanism or the applied noise. We formally characterize the conservativeness from the automatic PAC Privacy algorithms. The closed-form upper bound obtained by Theorem 3 of [ 1 ] forms the theoretical foundation of the automatic PAC Privacy algorithms. Algorithm 1 of [ 1 ] leverages this result to perform end-to-end automatic privatization, systematically constructing a Gaussian noise distribution that implements any designated privacy budget as an upper bound on mutual information. Importantly, we show that the Gaussian noise distribution constructed by Algorithm 1 of [ 1 ] is the unique solution to a constrained optimization problem that seeks to minimize the noise magnitude (specifically, the trace of the covariance matrix of the Gaussian noise) subject to