We study the accuracy of differentially private mechanisms in the continual release model. A continual release mechanism receives a sensitive dataset as a stream of $T$ inputs and produces, after receiving each input, an accurate output on the obtained inputs. In contrast, a batch algorithm receives the data as one batch and produces a single output. We provide the first strong lower bounds on the error of continual release mechanisms. In particular, for two fundamental problems that are widely studied and used in the batch model, we show that the worst case error of every continual release algorithm is $\tilde \Omega(T^{1/3})$ times larger than that of the best batch algorithm. Previous work shows only a polylogarithimic (in $T$) gap between the worst case error achievable in these two models; further, for many problems, including the summation of binary attributes, the polylogarithmic gap is tight (Dwork et al., 2010; Chan et al., 2010). Our results show that problems closely related to summation -- specifically, those that require selecting the largest of a set of sums -- are fundamentally harder in the continual release model than in the batch model. Our lower bounds assume only that privacy holds for streams fixed in advance (the "nonadaptive" setting). However, we provide matching upper bounds that hold in a model where privacy is required even for adaptively selected streams. This model may be of independent interest.
翻译:我们研究持续释放模式中不同私人机制的准确性。 持续释放机制接收敏感数据集,其输入量为$T(T ⁇ 1/ 3})之流, 敏感数据集的金额比最佳批量算法高出一倍。 相比之下, 批量算法将数据作为一个批量接收, 并产生单一输出。 我们为连续释放机制的错误提供了第一个较强的下限。 特别是, 对于批量模型中广泛研究和使用的两大问题, 我们发现, 持续释放算法中最差的错误是$\tilde\Omega(T ⁇ 1/ 3}), 比最佳批量算法的要大一倍。 先前的工作只显示这两个模型中最差的差数( $T$) ; 此外, 对于许多问题, 包括连续释放机制属性的相加, 多式差很紧( Dwork et al., 2010; Chan et al. 2010) 。 我们的结果显示, 每一个连续释放算算算法模型最差的错误是$\ a mall a mall a pall a pall a privastrate demotion) -- shrelifile made made made made made made made made made 可能只是 a 需要保持更低。