In privacy under continual observation we study how to release differentially
private estimates based on a dataset that evolves over time. The problem of
releasing private prefix sums of $x_1,x_2,x_3,\dots \in\{0,1\}$ (where the
value of each $x_i$ is to be private) is particularly well-studied, and a
generalized form is used in state-of-the-art methods for private stochastic
gradient descent (SGD). The seminal binary mechanism privately releases the
first $t$ prefix sums with noise of variance polylogarithmic in $t$. Recently,
Henzinger et al. and Denisov et al. showed that it is possible to improve on
the binary mechanism in two ways: The variance of the noise can be reduced by a
(large) constant factor, and also made more even across time steps. However,
their algorithms for generating the noise distribution are not as efficient as
one would like in terms of computation time and (in particular) space. We
address the efficiency problem by presenting a simple alternative to the binary
mechanism in which 1) generating the noise takes constant average time per
value, 2) the variance is reduced by a factor about 4 compared to the binary
mechanism, and 3) the noise distribution at each step is identical.
Empirically, a simple Python implementation of our approach outperforms the
running time of the approach of Henzinger et al., as well as an attempt to
improve their algorithm using high-performance algorithms for multiplication
with Toeplitz matrices.

研究在随时间不断变化的数据集上发布差分隐私估计值的问题，提出了一种替代二进制机制的简单方法，该方法生成噪声的平均时间为常数，噪声方差比二进制机制少约 4 倍，并且在每个步骤中具有相同的噪声分布。