PAC-Private Responses with Adversarial Composition

• URL: http://arxiv.org/abs/2601.14033v1
• Date: Tue, 20 Jan 2026 14:53:39 GMT
• Title: PAC-Private Responses with Adversarial Composition
• Authors: Xiaochen Zhu, Mayuri Sridhar, Srinivas Devadas,
• Abstract summary: PAC privacy provides instance-based privacy guarantees for arbitrary black-box functions.<n>We introduce a new algorithm that achieves adversarial composition via adaptive noise calibration.<n>Experiments show that our method achieves high utility at extremely small per-step privacy budgets.
• Score: 11.108854725676006
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern machine learning models are increasingly deployed behind APIs. This renders standard weight-privatization methods (e.g. DP-SGD) unnecessarily noisy at the cost of utility. While model weights may vary significantly across training datasets, model responses to specific inputs are much lower dimensional and more stable. This motivates enforcing privacy guarantees directly on model outputs. We approach this under PAC privacy, which provides instance-based privacy guarantees for arbitrary black-box functions by controlling mutual information (MI). Importantly, PAC privacy explicitly rewards output stability with reduced noise levels. However, a central challenge remains: response privacy requires composing a large number of adaptively chosen, potentially adversarial queries issued by untrusted users, where existing composition results on PAC privacy are inadequate. We introduce a new algorithm that achieves adversarial composition via adaptive noise calibration and prove that mutual information guarantees accumulate linearly under adaptive and adversarial querying. Experiments across tabular, vision, and NLP tasks show that our method achieves high utility at extremely small per-query privacy budgets. On CIFAR-10, we achieve 87.79% accuracy with a per-step MI budget of $2^{-32}$. This enables serving one million queries while provably bounding membership inference attack (MIA) success rates to 51.08% -- the same guarantee of $(0.04, 10^{-5})$-DP. Furthermore, we show that private responses can be used to label public data to distill a publishable privacy-preserving model; using an ImageNet subset as a public dataset, our model distilled from 210,000 responses achieves 91.86% accuracy on CIFAR-10 with MIA success upper-bounded by 50.49%, which is comparable to $(0.02,10^{-5})$-DP.

Related papers

• Evaluation of Differential Privacy Mechanisms on Federated Learning [0.0]
  Federated learning is distributed across several clients without disclosing raw data.<n> Differential Privacy (DP) is a technique to protect sensitive data by adding noise to model updates.<n>This work implements DP methods using Laplace and Gaussian mechanisms with an adaptive privacy budget.
  arXiv  Detail & Related papers  (2025-10-09T11:32:36Z)
• Machine Learning with Privacy for Protected Attributes [56.44253915927481]
  We refine the definition of differential privacy (DP) to create a more general and flexible framework that we call feature differential privacy (FDP)<n>Our definition is simulation-based and allows for both addition/removal and replacement variants of privacy, and can handle arbitrary separation of protected and non-protected features.<n>We apply our framework to various machine learning tasks and show that it can significantly improve the utility of DP-trained models when public features are available.
  arXiv  Detail & Related papers  (2025-06-24T17:53:28Z)
• Breaking the Gaussian Barrier: Residual-PAC Privacy for Automatic Privatization [27.430637970345433]
  We show that the upper bound obtained by PAC Privacy algorithms is tight if and only if the perturbed mechanism output is jointly Gaussian with independent noise.<n>We introduce Residual-PAC (R-PAC) Privacy, an f-divergence-based measure to quantify privacy that remains after adversarial inference.<n>Our approach achieves efficient privacy budget utilization for arbitrary data distributions and naturally composes when multiple mechanisms access the dataset.
  arXiv  Detail & Related papers  (2025-06-06T20:52:47Z)
• An Interactive Framework for Implementing Privacy-Preserving Federated Learning: Experiments on Large Language Models [7.539653242367701]
  Federated learning (FL) enhances privacy by keeping user data on local devices.<n>Recent attacks have demonstrated that updates shared by users during training can reveal significant information about their data.<n>We propose a framework that integrates a human entity as a privacy practitioner to determine an optimal trade-off between the model's privacy and utility.
  arXiv  Detail & Related papers  (2025-02-11T23:07:14Z)
• 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)
• Private Fine-tuning of Large Language Models with Zeroth-order Optimization [51.19403058739522]
  Differentially private gradient descent (DP-SGD) allows models to be trained in a privacy-preserving manner.<n>We introduce DP-ZO, a private fine-tuning framework for large language models by privatizing zeroth order optimization methods.
  arXiv  Detail & Related papers  (2024-01-09T03:53:59Z)
• 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)
• Smooth Anonymity for Sparse Graphs [69.1048938123063]
  differential privacy has emerged as the gold standard of privacy, however, when it comes to sharing sparse datasets. In this work, we consider a variation of $k$-anonymity, which we call smooth-$k$-anonymity, and design simple large-scale algorithms that efficiently provide smooth-$k$-anonymity.
  arXiv  Detail & Related papers  (2022-07-13T17:09:25Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning [74.73901662374921]
  A differentially private model degrades the utility drastically when the model comprises a large number of trainable parameters. We propose an algorithm emphGradient Embedding Perturbation (GEP) towards training differentially private deep models with decent accuracy.
  arXiv  Detail & Related papers  (2021-02-25T04:29:58Z)

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.