Correlated-Sequence Differential Privacy

• URL: http://arxiv.org/abs/2511.18025v1
• Date: Sat, 22 Nov 2025 11:28:59 GMT
• Title: Correlated-Sequence Differential Privacy
• Authors: Yifan Luo, Meng Zhang, Jin Xu, Junting Chen, Jianwei Huang,
• Abstract summary: Correlated-Sequence Differential Privacy (CSDP) is designed for preserving privacy in correlated sequential data.<n>CSDP addresses two linked challenges: quantifying the extra information an attacker gains from joint temporal and cross-sequence links, and adding just enough noise to hide that information.<n>Tests on two-sequence datasets show that CSDP improves the privacy-utility trade-off by approximately 50% over existing correlated-DP methods.
• Score: 32.411989837842086
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Data streams collected from multiple sources are rarely independent. Values evolve over time and influence one another across sequences. These correlations improve prediction in healthcare, finance, and smart-city control yet violate the record-independence assumption built into most Differential Privacy (DP) mechanisms. To restore rigorous privacy guarantees without sacrificing utility, we introduce Correlated-Sequence Differential Privacy (CSDP), a framework specifically designed for preserving privacy in correlated sequential data. CSDP addresses two linked challenges: quantifying the extra information an attacker gains from joint temporal and cross-sequence links, and adding just enough noise to hide that information while keeping the data useful. We model multivariate streams as a Coupling Markov Chain, yielding the derived loose leakage bound expressed with a few spectral terms and revealing a counterintuitive result: stronger coupling can actually decrease worst-case leakage by dispersing perturbations across sequences. Guided by these bounds, we build the Freshness-Regulated Adaptive Noise (FRAN) mechanism--combining data aging, correlation-aware sensitivity scaling, and Laplace noise--that runs in linear time. Tests on two-sequence datasets show that CSDP improves the privacy-utility trade-off by approximately 50% over existing correlated-DP methods and by two orders of magnitude compared to the standard DP approach.

Related papers

• Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency [53.98433419539793]
  We study the problem of spectral graph clustering under edge differential privacy (DP)<n>Specifically, we develop three mechanisms: (i) graph perturbation via randomized edge flipping combined with adjacency matrix shuffling, which enforces edge privacy; (ii) private graph projection with additive Gaussian noise in a lower-dimensional space to reduce dimensionality and computational complexity; and (iii) a noisy power iteration method that distributes Gaussian noise across iterations to ensure edge DP while maintaining convergence.
  arXiv  Detail & Related papers  (2025-10-08T15:30:27Z)
• Improving Noise Efficiency in Privacy-preserving Dataset Distillation [59.57846442477106]
  We introduce a novel framework that decouples sampling from optimization for better convergence and improves signal quality.<n>On CIFAR-10, our method achieves a textbf10.0% improvement with 50 images per class and textbf8.3% increase with just textbfone-fifth the distilled set size of previous state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-08-03T13:15:52Z)
• Frequency Estimation of Correlated Multi-attribute Data under Local Differential Privacy [5.258253745672122]
  Local Differential Privacy (LDP) is a powerful tool to protect user data privacy.<n>Existing LDP mechanisms either split the privacy budget across all attributes or treat each attribute independently.<n>We propose Correlated Randomized Response (Corr-RR), a novel LDP mechanism that leverages correlations among attributes to substantially improve utility.
  arXiv  Detail & Related papers  (2025-07-23T13:52:45Z)
• KL-regularization Itself is Differentially Private in Bandits and RLHF [33.10013796063427]
  Differential Privacy (DP) provides a rigorous framework for privacy, ensuring the outputs of data-driven algorithms remain statistically indistinguishable across datasets that differ in a single entry.<n>While guaranteeing DP generally requires explicitly injecting noise either to the algorithm itself or to its outputs, the intrinsic randomness of existing algorithms presents an opportunity to achieve DP for free''
  arXiv  Detail & Related papers  (2025-05-23T22:22:02Z)
• Dual Utilization of Perturbation for Stream Data Publication under Local Differential Privacy [10.07017446059039]
  Local differential privacy (LDP) has emerged as a promising standard.<n>Applying LDP to stream data presents significant challenges, as stream data often involves a large or even infinite number of values.<n>We introduce the Iterative Perturbation IPP method, which utilizes current perturbed results to calibrate the subsequent perturbation process.<n>We prove that these three algorithms satisfy $w$-event differential privacy while significantly improving utility.
  arXiv  Detail & Related papers  (2025-04-21T09:51:18Z)
• 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)
• 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)
• Differentially Private Linear Regression with Linked Data [3.9325957466009203]
  Differential privacy, a mathematical notion from computer science, is a rising tool offering robust privacy guarantees. Recent work focuses on developing differentially private versions of individual statistical and machine learning tasks. We present two differentially private algorithms for linear regression with linked data.
  arXiv  Detail & Related papers  (2023-08-01T21:00:19Z)
• Over-the-Air Federated Learning with Privacy Protection via Correlated Additive Perturbations [57.20885629270732]
  We consider privacy aspects of wireless federated learning with Over-the-Air (OtA) transmission of gradient updates from multiple users/agents to an edge server. Traditional perturbation-based methods provide privacy protection while sacrificing the training accuracy. In this work, we aim at minimizing privacy leakage to the adversary and the degradation of model accuracy at the edge server.
  arXiv  Detail & Related papers  (2022-10-05T13:13:35Z)
• Contrastive Self-supervised Sequential Recommendation with Robust Augmentation [101.25762166231904]
  Sequential Recommendationdescribes a set of techniques to model dynamic user behavior in order to predict future interactions in sequential user data. Old and new issues remain, including data-sparsity and noisy data. We propose Contrastive Self-Supervised Learning for sequential Recommendation (CoSeRec)
  arXiv  Detail & Related papers  (2021-08-14T07:15:25Z)
• Differentially Private Federated Learning with Laplacian Smoothing [72.85272874099644]
  Federated learning aims to protect data privacy by collaboratively learning a model without sharing private data among users. An adversary may still be able to infer the private training data by attacking the released model. Differential privacy provides a statistical protection against such attacks at the price of significantly degrading the accuracy or utility of the trained models.
  arXiv  Detail & Related papers  (2020-05-01T04:28:38Z)

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.