论文标题
差异私人连续计数几乎紧密的错误界限
Almost Tight Error Bounds on Differentially Private Continual Counting
论文作者
论文摘要
私人联邦学习的第一个大规模部署在连续发布模型中使用差异化计数作为子例程（Google AI博客，标题为“具有正式差异隐私保证的联邦学习”）。在这种情况下，对错误的具体绑定对于减少隐私参数非常相关。连续计数的标准机制是二进制机制。我们提出了一种新颖的机制，并表明其平方误差既是渐近的最佳选择，又比二进制机理的误差小。我们还表明，我们的分析中的常数几乎是通过给出仅在较低阶段的常数中不同的非征膜下限和上限。我们的算法是计数矩阵的矩阵机制，并且每个释放需要恒定的时间。我们还使用对计数矩阵的显式分解，以对Denisov等人的私人学习算法的过度风险产生上限。 （神经2022）。对于任何连续计数机制，我们的下限是在近似差异隐私下连续计数的第一个紧密下限。它是使用$γ_F（\ cdot）$表示的一定分解规范的新的下限来实现的，就矩阵的奇异值而言。特别是，我们表明，对于任何复杂的矩阵，$ a \ in \ mathbb {c}^{m \ times n} $，\ [γ_f（a）\ geq \ frac {1} {\ sqrt {\ sqrt {m}}}}}} \ | a \ | a \ | _1，\ | \ \ \ | \ | 我们认为，该技术对于证明较大类别的线性查询的下限将很有用。为了说明这项技术的功能，我们显示了回答奇偶校验查询的平方误差的第一个下限。
The first large-scale deployment of private federated learning uses differentially private counting in the continual release model as a subroutine (Google AI blog titled "Federated Learning with Formal Differential Privacy Guarantees"). In this case, a concrete bound on the error is very relevant to reduce the privacy parameter. The standard mechanism for continual counting is the binary mechanism. We present a novel mechanism and show that its mean squared error is both asymptotically optimal and a factor 10 smaller than the error of the binary mechanism. We also show that the constants in our analysis are almost tight by giving non-asymptotic lower and upper bounds that differ only in the constants of lower-order terms. Our algorithm is a matrix mechanism for the counting matrix and takes constant time per release. We also use our explicit factorization of the counting matrix to give an upper bound on the excess risk of the private learning algorithm of Denisov et al. (NeurIPS 2022). Our lower bound for any continual counting mechanism is the first tight lower bound on continual counting under approximate differential privacy. It is achieved using a new lower bound on a certain factorization norm, denoted by $γ_F(\cdot)$, in terms of the singular values of the matrix. In particular, we show that for any complex matrix, $A \in \mathbb{C}^{m \times n}$, \[ γ_F(A) \geq \frac{1}{\sqrt{m}}\|A\|_1, \] where $\|\cdot \|$ denotes the Schatten-1 norm. We believe this technique will be useful in proving lower bounds for a larger class of linear queries. To illustrate the power of this technique, we show the first lower bound on the mean squared error for answering parity queries.
