Continual Counting with Gradual Privacy Expiration

• URL: http://arxiv.org/abs/2406.03802v1
• Date: Thu, 6 Jun 2024 07:20:16 GMT
• Title: Continual Counting with Gradual Privacy Expiration
• Authors: Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, Jalaj Upadhyay,
• Abstract summary: We show that our algorithm achieves an additive error of $ O(log(T)/epsilon)$ for a large set of privacy expiration functions. Our empirical evaluation shows that we achieve a slowly growing privacy loss with significantly smaller empirical privacy loss for large values of $d$ than a natural baseline algorithm.
• Score: 15.87191465142231
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time $t$ the privacy loss guaranteed for a data item seen at time $(t-d)$ is $\epsilon g(d)$, where $g$ is a monotonically non-decreasing function. We study the fundamental $\textit{continual (binary) counting}$ problem where each data item consists of a bit, and the algorithm needs to output at each time step the sum of all the bits streamed so far. For a stream of length $T$ and privacy $\textit{without}$ expiration continual counting is possible with maximum (over all time steps) additive error $O(\log^2(T)/\varepsilon)$ and the best known lower bound is $\Omega(\log(T)/\varepsilon)$; closing this gap is a challenging open problem. We show that the situation is very different for privacy with gradual expiration by giving upper and lower bounds for a large set of expiration functions $g$. Specifically, our algorithm achieves an additive error of $ O(\log(T)/\epsilon)$ for a large set of privacy expiration functions. We also give a lower bound that shows that if $C$ is the additive error of any $\epsilon$-DP algorithm for this problem, then the product of $C$ and the privacy expiration function after $2C$ steps must be $\Omega(\log(T)/\epsilon)$. Our algorithm matches this lower bound as its additive error is $O(\log(T)/\epsilon)$, even when $g(2C) = O(1)$. Our empirical evaluation shows that we achieve a slowly growing privacy loss with significantly smaller empirical privacy loss for large values of $d$ than a natural baseline algorithm.

Related papers

• Differentially Private Approximate Pattern Matching [0.0]
  We consider the $k$-approximate pattern matching problem under differential privacy. The goal is to report or count allimate variants of a given string $S$ which have a Hamming distance at most $k$ to a pattern $P$. We give 1) an $epsilon$-differentially private algorithm with an additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) an $epsilon$-differentially private algorithm with an additive error $O(epsilon-1
  arXiv  Detail & Related papers  (2023-11-13T15:53:45Z)
• Online Robust Mean Estimation [37.746091744197656]
  We study the problem of high-dimensional robust mean estimation in an online setting. We prove two main results about online robust mean estimation in this model.
  arXiv  Detail & Related papers  (2023-10-24T15:28:43Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  We show that an algorithm can obtain $O(log T)$ regret with just $O(sqrtT)$ hints under a natural query model. We also show that $o(sqrtT)$ hints cannot guarantee better than $Omega(sqrtT)$ regret.
  arXiv  Detail & Related papers  (2021-11-09T16:50:18Z)
• 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)
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries [49.453751858361265]
  We give an algorithm for this task that achieves an expected $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the $ell_infty$ error bound of $O(frac1epsilonsqrtk log frac1delta)$ holds not only in expectation but always.
  arXiv  Detail & Related papers  (2020-12-16T17:58:45Z)
• Differentially Private Online Submodular Maximization [16.422215672356167]
  We consider the problem of online submodular functions under a cardinality constraint with differential privacy feed (DP) A stream of $T$ submodular functions over a common finite ground set $U$ arrives online, and at each time-step the decision maker must choose most $k$ elements of $U$ before observing the function. The decision maker obtains a payoff equal to the function evaluated on the chosen set, and aims to learn a sequence of sets that achieves low expected regret.
  arXiv  Detail & Related papers  (2020-10-24T07:23:30Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
  A widely-used method to preserve the underlying hierarchical structure of the data is to find an embedding of the data into a tree or an ultrametric. In this paper, we provide a new algorithm which takes as input a set of points isometric in $mathbbRd2 (for universal constant $rho>1$) to output an ultrametric $Delta. We show that the output of our algorithm is comparable to the output of the linkage algorithms while achieving a much faster running time.
  arXiv  Detail & Related papers  (2020-08-15T11:06:45Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.