Beyond Membership: Limitations of Add/Remove Adjacency in Differential Privacy

2025/11/26 by Gauri Pradhan, Pradhan, Gauri, Joonas Jälkö +5
Computer Science · Social Sciences · #Adversarial Robustness in Machine Learning #Cryptography and Security (cs.CR) #Ethics and Social Impacts of AI #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2511.21804

openalex publication_date 2025/11/26 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28

Abstract

Training machine learning models with differential privacy (DP) limits an adversary's ability to infer sensitive information about the training data. It can be interpreted as a bound on adversary's capability to distinguish two adjacent datasets according to chosen adjacency relation. In practice, most DP implementations use the add/remove adjacency relation, where two datasets are adjacent if one can be obtained from the other by adding or removing a single record, thereby protecting membership. In many ML applications, however, the goal is to protect attributes of individual records (e.g., labels used in supervised fine-tuning). We show that privacy accounting under add/remove overstates attribute privacy compared to accounting under the substitute adjacency relation, which permits substituting one record. To demonstrate this gap, we develop novel attacks to audit DP under substitute adjacency, and show empirically that audit results are inconsistent with DP guarantees reported under add/remove, yet remain consistent with the budget accounted under the substitute adjacency relation. Our results highlight that the choice of adjacency when reporting DP guarantees is critical when the protection target is per-record attributes rather than membership.

Citations

• Auditing f-Differential Privacy in One Run
• Tighter Privacy Auditing of DP-SGD in the Hidden State Threat Model
• Nearly Tight Black-Box Auditing of Differentially Private Machine Learning
• Mean estimation in the add-remove model of differential privacy
• Privacy Auditing with One (1) Training Run
• SoK: Let the Privacy Games Begin! A Unified Treatment of Data Inference Privacy in Machine Learning
• Bayesian Estimation of Differential Privacy
• Unlocking High-Accuracy Differentially Private Image Classification through Scale
• Opacus: User-Friendly Differential Privacy Library in PyTorch
• Numerical Composition of Differential Privacy
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Deep Learning with Label Differential Privacy
• Adversary Instantiation: Lower Bounds for Differentially Private Machine\n Learning
• Differentially Private Learning Needs Better Features (or Much More Data)
• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks
• Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
• Membership Inference Attacks against Machine Learning Models
• Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
• Concentrated Differential Privacy
• The Composition Theorem for Differential Privacy
• THE USE OF CONFIDENCE OR FIDUCIAL LIMITS ILLUSTRATED IN THE CASE OF THE BINOMIAL
• Optimizing Canaries for Privacy Auditing with Metagradient Descent

Related

• Bounding Membership Inference
• Effects of Differential Privacy and Data Skewness on Membership Inference Vulnerability
• Membership Privacy for Machine Learning Models Through Knowledge Transfer
• Investigating Membership Inference Attacks under Data Dependencies
• Generalization Techniques Empirically Outperform Differential Privacy against Membership Inference