We consider the problem of computing tight privacy guarantees for the
composition of subsampled differentially private mechanisms. Recent algorithms
can numerically compute the privacy parameters to arbitrary precision but must
be carefully applied.
Our main contribution is to address two common points of confusion. First,
some privacy accountants assume that the privacy guarantees for the composition
of a subsampled mechanism are determined by self-composing the worst-case
datasets for the uncomposed mechanism. We show that this is not true in
general. Second, Poisson subsampling is sometimes assumed to have similar
privacy guarantees compared to sampling without replacement. We show that the
privacy guarantees may in fact differ significantly between the two sampling
schemes. In particular, we give an example of hyperparameters that result in
$\varepsilon \approx 1$ for Poisson subsampling and $\varepsilon > 10$ for
sampling without replacement. This occurs for some parameters that could
realistically be chosen for DP-SGD.

我们考虑计算子采样差分私有机制组合的紧密隐私保证的问题。我们的主要贡献在于解决了两个常见的困惑：一是有些隐私估计者认为，子采样机制组合的隐私保证是通过自组合未组合机制的最坏情况数据集来确定的；二是泊松子采样有时被假设具有与无替换采样相似的隐私保证，但我们表明这两种采样方案的隐私保证可能存在显著差异。具体而言，我们给出了一个示例，其中泊松子采样的 ε≈1，而无替换采样的 ε>10。这对于实际可选择的 DP-SGD 参数而言是可能发生的。

在组合下避免子采样机制的隐私计算陷阱

Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under  Composition

We demonstrate a substantial gap between the privacy guarantees of the
Adaptive Batch Linear Queries (ABLQ) mechanism under different types of batch
sampling: (i) Shuffling, and (ii) Poisson subsampling; the typical analysis of
Differentially Private Stochastic Gradient Descent (DP-SGD) follows by
interpreting it as a post-processing of ABLQ. While shuffling based DP-SGD is
more commonly used in practical implementations, it is neither analytically nor
numerically amenable to easy privacy analysis. On the other hand, Poisson
subsampling based DP-SGD is challenging to scalably implement, but has a
well-understood privacy analysis, with multiple open-source numerically tight
privacy accountants available. This has led to a common practice of using
shuffling based DP-SGD in practice, but using the privacy analysis for the
corresponding Poisson subsampling version. Our result shows that there can be a
substantial gap between the privacy analysis when using the two types of batch
sampling, and thus advises caution in reporting privacy parameters for DP-SGD.

我们展示了 Adaptive Batch Linear Queries (ABLQ) 机制在不同类型的批量采样（洗牌和泊松子采样）下的隐私保证之间存在重大差距，这提示我们在报告 DP-SGD 的隐私参数时要小心。

DP-SGD 的隐私程度如何？

How Private is DP-SGD?

In this paper, we propose improved estimation method for logistic regression
based on subsamples taken according the optimal subsampling probabilities
developed in Wang et al. 2018 Both asymptotic results and numerical results
show that the new estimator has a higher estimation efficiency. We also develop
a new algorithm based on Poisson subsampling, which does not require to
approximate the optimal subsampling probabilities all at once. This is
computationally advantageous when available random-access memory is not enough
to hold the full data. Interestingly, asymptotic distributions also show that
Poisson subsampling produces a more efficient estimator if the sampling rate,
the ratio of the subsample size to the full data sample size, does not converge
to zero. We also obtain the unconditional asymptotic distribution for the
estimator based on Poisson subsampling. The proposed approach requires to use a
pilot estimator to correct biases of un-weighted estimators. We further show
that even if the pilot estimator is inconsistent, the resulting estimators are
still consistent and asymptotically normal if the model is correctly specified.

本文提出了一个基于子样本的改进逻辑回归估计方法，通过使用 2018 年 Wang 等人提出的最优子采样概率。无论是渐近结果还是数值结果都说明新的估计量具有更高的估计效率。我们还提出了一种基于泊松子采样的新算法，该算法不需要一次性近似最优子采样概率，避免了计算问题，并且当随机存储器的可用空间不足以存储全部数据时有计算优势。如果采样速率（子样本大小与全部数据样本大小的比例）不收敛于零，渐近分布表明泊松子采样可以产生更高效的估计量。我们进一步使用一个初始估计器来校正未加权估计器的偏差。我们还证明，即使初始估计器是不一致的，如果模型是正确的，则会产生一致和渐近正常的结果估计量。