Skirting Additive Error Barriers for Private Turnstile Streams

• URL: http://arxiv.org/abs/2602.10360v1
• Date: Tue, 10 Feb 2026 23:10:34 GMT
• Title: Skirting Additive Error Barriers for Private Turnstile Streams
• Authors: Anders Aamand, Justin Y. Chen, Sandeep Silwal,
• Abstract summary: We study differentially private continual release of the number of distinct items in a turnstile stream.<n>For streams of length '23, additive error of $(T1/4)$ is necessary, even without any space restrictions.<n>We show that this error lower bound can be circumvented if the algorithm is allowed to output estimates with both additive emphand multiplicative error.
• Score: 15.938776246823275
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study differentially private continual release of the number of distinct items in a turnstile stream, where items may be both inserted and deleted. A recent work of Jain, Kalemaj, Raskhodnikova, Sivakumar, and Smith (NeurIPS '23) shows that for streams of length $T$, polynomial additive error of $Ω(T^{1/4})$ is necessary, even without any space restrictions. We show that this additive error lower bound can be circumvented if the algorithm is allowed to output estimates with both additive \emph{and multiplicative} error. We give an algorithm for the continual release of the number of distinct elements with $\text{polylog} (T)$ multiplicative and $\text{polylog}(T)$ additive error. We also show a qualitatively similar phenomenon for estimating the $F_2$ moment of a turnstile stream, where we can obtain $1+o(1)$ multiplicative and $\text{polylog} (T)$ additive error. Both results can be achieved using polylogarithmic space whereas prior approaches use polynomial space. In the sublinear space regime, some multiplicative error is necessary even if privacy is not a consideration. We raise several open questions aimed at better understanding trade-offs between multiplicative and additive error in private continual release.

Related papers

• Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model [61.40326886123332]
  We give the first sublinear space differentially private algorithms for the fundamental problem of counting distinct elements in the turnstile streaming model.<n>Our result significantly improves upon the space requirements of the state-of-the-art algorithms for this problem, which is linear.<n>When a bound $W$ on the number of times an item appears in the stream is known, our algorithm provides $tildeO_eta(sqrtW)$ additive error using $tildeO_eta(sqrtW)$ space.
  arXiv  Detail & Related papers  (2025-05-29T17:21:20Z)
• Near-Optimal Differentially Private k-Core Decomposition [2.859324824091086]
  We show that an $eps$-edge differentially private algorithm for $k$-core decomposition outputs the core numbers with no multiplicative error and $O(textlog(n)/eps)$ additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error.
  arXiv  Detail & Related papers  (2023-12-12T20:09:07Z)
• Differentially Private Clustering in Data Streams [56.26040303056582]
  We provide the first differentially private algorithms for $k$-means and $k$-median clustering of $d$-dimensional Euclidean data points over a stream with length at most $T$.<n>Our main technical contribution is a differentially private clustering framework for data streams which only requires an offline DP coreset or clustering algorithm as a blackbox.
  arXiv  Detail & Related papers  (2023-07-14T16:11:22Z)
• 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)
• Private Isotonic Regression [54.32252900997422]
  We consider the problem of isotonic regression over a partially ordered set (poset) $mathcalX$ and for any Lipschitz loss function. We obtain a pure-DP algorithm that has an expected excess empirical risk of roughly $mathrmwidth(mathcalX) cdot log|mathcalX| / n$, where $mathrmwidth(mathcalX)$ is the width of the poset. We show that the bounds above are essentially the best that can be
  arXiv  Detail & Related papers  (2022-10-27T05:08:07Z)
• List-Decodable Covariance Estimation [1.9290392443571387]
  We give the first time algorithm for emphlist-decodable covariance estimation. Our result implies the first-time emphexact algorithm for list-decodable linear regression and subspace recovery.
  arXiv  Detail & Related papers  (2022-06-22T09:38:06Z)
• Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error [10.632986841188]
  We bridge the gap between the exponents of $n$ in the upper and lower bounds on the additive error with two new algorithms. It is possible to solve the locally private $k$-means problem in a constant number of rounds with constant factor multiplicative approximation.
  arXiv  Detail & Related papers  (2021-05-31T14:41:40Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

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.