Research map / Learning theory and algorithms / Sample complexity
Private Continual Counting of Unbounded Streams
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.
Introduces logarithmically perturbed matrix factorizations of continual counting that let the matrix mechanism run on unbounded streams without a doubling trick, achieving smooth O(log^{2+2α} t) variance with O(t) space.
Problem
Differentially private continual counting over unbounded streams where the input length n is unknown in advance; existing optimal matrix factorizations require n for their privacy guarantees, while doubling tricks yield non-smooth error.
Approach
Factorize the Toeplitz matrix of continual counting using generating functions 1/sqrt(1-z) multiplied by logarithmic perturbations (ln(1/(1-z)))^gamma and (ln of that)^delta with gamma < -1/2, making the column norm of R finite so noise can be calibrated without knowing n, and computing coefficients in amortized O(log t) time per step.
Key results
- The logarithmic matrix method achieves O(log^{2+2α} t) variance for any α>0 with O(t) space and amortized O(log t) time per round, without knowledge of n.
- Empirically, the variance of the proposed algorithm is less than 1.5x that of the Sqrt Matrix algorithm for t as large as 2^24.
- The paper proves privacy-relevant bounded sensitivity (finite column norm of R) and O(log^{1+α}(n)) row norm of L.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Logarithmic Matrix Method instead of the bounded-input Sqrt Matrix | Continual counting · Continual counting through t = 2^24 | variance: less than 1.5× theirs | Mixed |
| Use the Logarithmic Matrix Method rather than independent noise for the unbounded component | Hybrid mechanism · Unbounded continual counting | variance | Helped |
| Set δ = -γ instead of δ = 0 (ablation) | Logarithmic Matrix Method · Continual counting, t > 2^10 | variance | Helped |
| Set δ = -6γ/5 instead of δ = 0 (ablation) | Logarithmic Matrix Method · Continual counting, t > 2^10 | variance | Helped |
| Set δ = -6γ/5 rather than δ = -γ (ablation) | Logarithmic Matrix Method · Continual counting, t > 2^20 | variance | Helped |
| Use δ = -γ instead of δ = 0 (ablation) | Logarithmic Matrix Method · Continual counting, n greater than 1,000 | error: roughly 1.5× slower | Helped |
| Use δ = -6γ/5 instead of δ = -γ (ablation) | Logarithmic Matrix Method · Continual counting, n greater than 2^20 | error | Helped |
| Switch from exact computations to order-K coefficient approximations around t = 2^11 (ablation) | Approximate Logarithmic Matrix Method · Continual counting through t = 2^24 | variance | No clear effect |
| Use asymptotic coefficient approximations (ablation) | Logarithmic Matrix Method · Continual counting, large inputs | running time: greater than 5× improvement | Helped |
| Use a standard doubling trick in the Hybrid Matrix (ablation) | Hybrid Matrix · Unbounded continual counting near powers of 2 | variance smoothness | Hurt |
Surprising findings
- Using the hybrid mechanism with the proposed factorization gives exactly O(log^2 t) variance with improved constants, in contrast to the loss of smoothness typical of doubling tricks.
Limitations
- Computational cost of computing the matrix coefficients (FFT-based, about 12 polynomial multiplications per doubling) is higher than the O(1) per-step cost of Sqrt Matrix.
- Asymptotic error is slightly suboptimal: O(log^{1+α} n) row norm rather than the optimal log n, and the exact O(log^2 t) rate is not achieved by a single Toeplitz decomposition.
- Choice of alpha and delta involves tradeoffs in numerical stability and speed.
Experimental setup
Metrics: variance of added noise root mean squared additive error expected maximum additive error running time space
Baselines: Binary mechanism Hybrid Binary mechanism Smooth Binary Sqrt Matrix Hybrid mechanism with independent noise
Builds on: matrix mechanism binary mechanism hybrid mechanism sqrt matrix factorization (mcount^{1/2}) Flajolet-Odlyzko asymptotic expansion
Closest papers by meaning
- Constant Matters: Fine-grained Error Bound on Differentially Private Continual Observation (ICML 2023 · similarity 0.91)
- Continual Counting with Gradual Privacy Expiration (NeurIPS 2024 · similarity 0.89)
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.89)
- Privately Counting Partially Ordered Data (ICLR 2025 · similarity 0.88)
- Differentially Private Equivalence Testing for Continuous Distributions and Applications (NeurIPS 2024 · similarity 0.86)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.85)
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.