Edit-Neighboring Data Streams and Privacy under Continual Observation

• URL: http://arxiv.org/abs/2607.20727v1
• Date: Wed, 22 Jul 2026 20:54:44 GMT
• Title: Edit-Neighboring Data Streams and Privacy under Continual Observation
• Abstract summary: Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting.<n>We consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step.<n>We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams.
• Score: 12.49920379845039
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In this paper, we consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length $T$, every additive-noise mechanism incurs error $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ when required to be $\varepsilon$-DP under CO for edit-neighboring streams. This includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a `sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams---which arises naturally in reductions for problems under CO---must incur additive error scaling as $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ for any mechanism that is $\varepsilon$-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.

Related papers

• RAPTOR: Role-Aware Private Training for Mixture-of-Experts [68.5626338219096]
  RAPTOR is a Role-Aware Private Training framework.<n>RAPTOR alternates shared and expert optimization and targets each failure directly.<n> Experiments on Switch Transformer and OLMoE fine-tuning across GLUE tasks, and on DeepSeek-VL2-Tiny, show consistent gains over standard DP baselines.
  arXiv  Detail & Related papers  (2026-09-04T23:16:12Z)
• Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe [22.282174850598953]
  We study single-edit neighboring user streams, where one insertion/deletion shifts all subsequent updates.<n>A randomized buffering wrapper emits bins of size $[U,2U]$, reducing single-edit streams to a Hamming-style per-bin update stream.<n>We prove a certification theorem identifying when a non-adaptive Hamming-neighbor DP proof for a continual primitive lifts to adaptive inputs.
  arXiv  Detail & Related papers  (2026-07-08T09:44:27Z)
• Computing Maximal Per-Record Leakage and Leakage-Distortion Functions for Privacy Mechanisms under Entropy-Constrained Adversaries [19.239827561129513]
  We study three core problems: maximal per-record leakage, the primal leakage-distortion tradeoff, and the dual distortion minimization.<n>We develop efficient alternating optimization algorithms that exploit convexity-concavity duality.<n>This work provides a computational framework for auditing privacy risks and designing certified mechanisms.
  arXiv  Detail & Related papers  (2026-01-31T12:23:24Z)
• 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)
• Beyond Covariance Matrix: The Statistical Complexity of Private Linear Regression [66.93988594607842]
  Under privacy constraints, the complexity of private linear regression is emphnot captured by the usual covariance matrix.<n>We introduce an Information-Weighted Regression method that attains the optimal rates.<n> Notably, our results demonstrate that joint privacy comes at almost no additional cost.
  arXiv  Detail & Related papers  (2025-02-18T18:35:24Z)
• Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation [3.9476868147424162]
  We show that every differentially private mechanism that handles insertions and deletions has worst-case additive error at least $T1/4$ even under a relatively weak, event-level privacy definition. We present an item-level differentially private mechanism that, for all turnstile streams with maximum flippancy $w$, continually outputs the number of distinct elements with an $O(sqrtw cdot polylog T)$ additive error.
  arXiv  Detail & Related papers  (2023-06-11T16:54:39Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Nonparametric extensions of randomized response for private confidence sets [51.75485869914048]
  This work derives methods for performing nonparametric, nonasymptotic statistical inference for population means under the constraint of local differential privacy (LDP) We present confidence intervals (CI) and time-uniform confidence sequences (CS) for $mustar$ when only given access to the privatized data.
  arXiv  Detail & Related papers  (2022-02-17T16:04:49Z)
• Differentially Private Community Detection for Stochastic Block Models [22.526853379896252]
  We study the community detection problem while preserving the privacy of the individual connections. We present and analyze the associated information tradeoffs for three broad classes of differentially private community recovery mechanisms.
  arXiv  Detail & Related papers  (2022-01-31T18:59:19Z)
• Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming [10.952006057356714]
  We study the fundamental problem of frequency estimation under both privacy and communication constraints, where the data is distributed among $k$ parties. We adopt the model of multiparty differential privacy (MDP), which is more general than local differential privacy (LDP) and (centralized) differential privacy. Our protocols achieve optimality (up to logarithmic factors) permissible by the more stringent of the two constraints.
  arXiv  Detail & Related papers  (2021-04-05T08:15:20Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)

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.