Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy

在差分隐私（DP）连续计数任务中，我们接收一系列增量，目标是输出这些增量的近似累加总和，同时不会透露有关任何特定增量的太多信息。尽管它很简单，但差分隐私连续计数在理论和实践中都受到了重视。现有的差分隐私连续计数算法要么在空间使用方面效率低下，要么添加过多的噪声，导致效用不佳。最实用的DP连续计数算法是向值添加精心相关的高斯噪声。选择这种噪声的协方差可以用下三角矩阵的因式分解来表达（该矩阵计算前缀和）。我们提出了两种来自该类的方法（针对不同的参数范围），用于实现DP连续计数，可以实现接近最优的效用，并且只需要对数或多对数空间（和时间）。我们的第一种方法基于一类Toeplitz矩阵的空间有效的流矩阵乘法算法。我们展示了为了将此算法实例化为DP连续计数，只需找到一个近似于复平面上圆上平方根的低次有理函数即可。然后，我们应用并扩展了近似理论中的工具来实现这一点。我们还为任意多步导出了目标函数的高效闭合形式，并展示了直接数值优化可以高度实用地解决问题。我们的第二种方法将我们的第一种方法与类似于二叉树机制的递归构造相结合。

解决问题：论文旨在解决不泄露隐私的情况下对数据流进行差分隐私连续计数的问题，现有算法要么空间利用效率低，要么添加过多噪声，影响效用。

关键思路：论文提出了两种基于高斯噪声的不同ially private continual counting算法，通过对矩阵的分解和递归构造，实现了对数据流的差分隐私连续计数，并且只需要对数或多对数空间和时间。

其他亮点：第一种方法基于一个类Toeplitz矩阵的流式矩阵乘法算法，通过找到在复平面上的一个圆上的平方根的低次有理函数来实例化该算法，论文还应用和扩展了逼近理论中的工具，为任意步骤导出了有效的闭式形式的目标函数，并展示了直接数值优化是解决该问题的高度实用的解决方案。第二种方法则结合了第一种方法和类似于二叉树机制的递归构造。

相关研究：最近在这个领域中，还有一些相关的研究，如“Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams”和“Differentially Private Continuous Data Release via Kernel Mean Embedding”。