Research map / Learning theory and algorithms / Sample complexity
Continual Counting with Gradual Privacy Expiration
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a binary-tree-style continual counting algorithm under differential privacy with gradual expiration that achieves O(log T/ε) max error for a broad class of expiration functions, with a matching lower bound.
Problem
Continual binary counting under differential privacy where the privacy loss for a data item grows with elapsed time (privacy with gradual expiration), aiming for better accuracy than the O(log^2 T/ε) of standard continual counting.
Approach
Uses a pan-private-style dyadic interval noise scheme on an unbounded stream, adds noise for intervals containing the current time, splits privacy budget unevenly across dyadic levels proportional to (ℓ+1)^(λ-1), and delays output by B steps, yielding expiration g(d)=O(1+log^λ d) with O(log T/ε) error.
Key results
- Algorithm achieves maximum additive error O(log(T)/ε) with expiration g(d)=O(1+log^λ d) for λ≥1 and B=O(log(T)/ε), matching a lower bound of Ω(log(T)/ε).
- Lower bound: for any ε-DP algorithm with max additive error C, the sum of expiration g(j) over j<2C must be at least log(T/6C)/ε.
- Empirically, the algorithm has significantly lower worst-case privacy loss than the block-restart baseline for large d at the same MSE (1000).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed gradual-expiration counting algorithm instead of the interval-reset binary-mechanism baseline | Continual counting · Empirical privacy loss at large elapsed time d | privacy loss | Helped |
| Use the proposed gradual-expiration counting algorithm instead of the interval-reset binary-mechanism baseline | Continual counting · Empirical privacy loss at small elapsed time d | privacy loss | Hurt |
| Increase λ (ablation) | Proposed gradual-expiration counting algorithm · Empirical privacy loss at large elapsed time d | privacy loss | Hurt |
| Decrease λ (ablation) | Proposed gradual-expiration counting algorithm · Empirical privacy loss at early elapsed time | privacy loss | Hurt |
| Use the theorem's expiration function as a predictor of empirical privacy loss | Proposed gradual-expiration counting algorithm · Empirical privacy loss across elapsed times | privacy loss | No clear effect |
| Use an interval-reset baseline with fixed round length W | Continual counting baseline · Empirical privacy loss for large elapsed time d | privacy loss | Hurt |
Surprising findings
- The baseline achieves lower privacy loss than the proposed algorithm for small d, a trade-off the authors acknowledge.
Limitations
- Results are for pure differential privacy; approximate DP analog not established.
- Gap remains for slower-growing expiration functions and the baseline is better at small d.
- Empirical evaluation uses only an all-zero input stream and a single baseline.
Experimental setup
Metrics: mean-squared error maximum additive error worst-case privacy loss
Baselines: binary mechanism (Chan et al.) block-restart privacy budget baseline
Builds on: binary tree mechanism pan-privacy continual counting (Dwork et al.) privacy with expiration (Bolot et al.) Laplace mechanism
Closest papers by meaning
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.89)
- The Flajolet-Martin Sketch Itself Preserves Differential Privacy: Private Counting with Minimal Space (NeurIPS 2020 · similarity 0.89)
- The Price of Differential Privacy under Continual Observation (ICML 2023 · similarity 0.88)
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.86)
- Privately Counting Partially Ordered Data (ICLR 2025 · similarity 0.85)
- Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.