Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization

• URL: http://arxiv.org/abs/2506.06530v1
• Date: Fri, 06 Jun 2025 20:52:47 GMT
• Title: Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization
• Authors: Tao Zhang, Yevgeniy Vorobeychik,
• Abstract summary: We introduce Residual PAC Privacy, an f-divergence-based measure that quantifies the privacy remaining after adversarial inference.<n>We also propose Stackelberg Residual-PAC (SR-PAC) privatization mechanisms for RPAC Privacy, a game-theoretic framework that selects optimal noise distributions.
• Score: 25.387857775660855
• License: http://creativecommons.org/licenses/by/4.0/
• 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 Privacy, an 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.

Related papers

• Meeting Utility Constraints in Differential Privacy: A Privacy-Boosting Approach [7.970280110429423]
  We propose a privacy-boosting framework that is compatible with most noise-adding DP mechanisms.<n>Our framework enhances the likelihood of outputs falling within a preferred subset of the support to meet utility requirements.<n>We show that our framework achieves lower privacy loss than standard DP mechanisms under utility constraints.
  arXiv  Detail & Related papers  (2024-12-13T23:34:30Z)
• Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
  Differential privacy (DP) can measure privacy loss by observing the changes in the distribution caused by the inclusion of individuals in the target dataset. DP has been prominent in safeguarding datasets in machine learning in industry giants like Apple and Google. We propose per-instance DP (pDP) as a constraint, measuring privacy loss for each data instance and optimizing noise tailored to individual instances.
  arXiv  Detail & Related papers  (2024-04-24T06:51:16Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification [54.1447806347273]
  Amplification by subsampling is one of the main primitives in machine learning with differential privacy. We propose the first general framework for deriving mechanism-specific guarantees. We analyze how subsampling affects the privacy of groups of multiple users.
  arXiv  Detail & Related papers  (2024-03-07T19:36:05Z)
• A Randomized Approach for Tight Privacy Accounting [63.67296945525791]
  We propose a new differential privacy paradigm called estimate-verify-release (EVR) EVR paradigm first estimates the privacy parameter of a mechanism, then verifies whether it meets this guarantee, and finally releases the query output. Our empirical evaluation shows the newly proposed EVR paradigm improves the utility-privacy tradeoff for privacy-preserving machine learning.
  arXiv  Detail & Related papers  (2023-04-17T00:38:01Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Privacy Amplification via Shuffled Check-Ins [2.3333090554192615]
  We study a protocol for distributed computation called shuffled check-in. It achieves strong privacy guarantees without requiring any further trust assumptions beyond a trusted shuffler. We show that shuffled check-in achieves tight privacy guarantees through privacy amplification.
  arXiv  Detail & Related papers  (2022-06-07T09:55:15Z)
• Decentralized Stochastic Optimization with Inherent Privacy Protection [103.62463469366557]
  Decentralized optimization is the basic building block of modern collaborative machine learning, distributed estimation and control, and large-scale sensing. Since involved data, privacy protection has become an increasingly pressing need in the implementation of decentralized optimization algorithms.
  arXiv  Detail & Related papers  (2022-05-08T14:38:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.