提出可私密持续统计无界数据流的新算法，误差平滑且效率更高。
Private Continual Counting of Unbounded Streams
- 基于对数扰动的新型矩阵分解，解决未知数据规模下的隐私问题。
- 在任意时间点t，估计误差方差为O(log²⁺²ᵃ(t))，优于已有方法。
- 适合需要高隐私保障与低延迟的数据流场景，如实时监控系统。
我们研究输入规模n未知情况下的差分隐私持续计数问题。现有最优算法依赖于n的参数调优，无法直接适用。采用常见的'加倍技巧'虽无需预知n，但导致误差次优且不平滑。本文通过引入基于函数1/√(1−z)对数扰动的新颖矩阵分解，解决了该问题。所提算法具有平滑误差，在任意α>0及t≤n条件下，对前t个数据点的和进行私密估计时，方差为O(log²⁺²ᵃ(t))。算法空间复杂度O(t)，每轮均摊时间复杂度O(log t)，显著优于近似最优的有界输入算法（方差O(log n log t)，空间O(n)，预处理时间O(n log n)）。实验表明，当t达2²⁴时，本算法方差不足其1.5倍。
原文摘要 · Abstract (English)
We study the problem of differentially private continual counting in the unbounded setting where the input size $n$ is not known in advance. Current state-of-the-art algorithms based on optimal instantiations of the matrix mechanism cannot be directly applied here because their privacy guarantees only hold when key parameters are tuned to $n$. Using the common `doubling trick' avoids knowledge of $n$ but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function $\frac{1}{\sqrt{1-z}}$ studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any $α> 0$ and $t\leq n$ it is able to privately estimate the sum of the first $t$ data points with $O(\log^{2+2α}(t))$ variance. It requires $O(t)$ space and amortized $O(\log t)$ time per round, compared to $O(\log(n)\log(t))$ variance, $O(n)$ space and $O(n \log n)$ pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. (SODA 2023). Empirically, we find that our algorithm's performance is also comparable to theirs in absolute terms: our variance is less than $1.5\times$ theirs for $t$ as large as $2^{24}$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。