---
res:
  bibo_abstract:
  - "Differential privacy with gradual expiration models the setting where data items\r\narrive
    in a stream and at a given time t the privacy loss guaranteed for a data item\r\nseen
    at time (t − d) is εg(d), where g is a monotonically non-decreasing function.\r\nWe
    study the fundamental continual (binary) counting problem where each data\r\nitem
    consists of a bit, and the algorithm needs to output at each time step the sum
    of\r\nall the bits streamed so far. For a stream of length T and privacy without
    expiration\r\ncontinual counting is possible with maximum (over all time steps)
    additive error\r\nO(log2\r\n(T)/ε) and the best known lower bound is Ω(log(T)/ε);
    closing this gap\r\nis a challenging open problem.\r\nWe show that the situation
    is very different for privacy with gradual expiration by\r\ngiving upper and lower
    bounds for a large set of expiration functions g. Specifically,\r\nour algorithm
    achieves an additive error of O(log(T)/ε) for a large set of privacy\r\nexpiration
    functions. We also give a lower bound that shows that if C is the additive\r\nerror
    of any ε-DP algorithm for this problem, then the product of C and the privacy\r\nexpiration
    function after 2C steps must be Ω(log(T)/ε). Our algorithm matches\r\nthis lower
    bound as its additive error is O(log(T)/ε), even when g(2C) = O(1).\r\nOur empirical
    evaluation shows that we achieve a slowly growing privacy loss\r\nwith significantly
    smaller empirical privacy loss for large values of d than a natural\r\nbaseline
    algorithm.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Joel Daniel
      foaf_name: Andersson, Joel Daniel
      foaf_surname: Andersson
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Rasmus
      foaf_name: Pagh, Rasmus
      foaf_surname: Pagh
  - foaf_Person:
      foaf_givenName: Teresa Anna
      foaf_name: Steiner, Teresa Anna
      foaf_surname: Steiner
  - foaf_Person:
      foaf_givenName: Jalaj
      foaf_name: Upadhyay, Jalaj
      foaf_surname: Upadhyay
  bibo_volume: 37
  dct_date: 2024^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1049-5258
  dct_language: eng
  dct_publisher: Neural Information Processing Systems Foundation@
  dct_title: Continual counting with gradual privacy expiration@
...