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

This paper derives confidence intervals (CI) and time-uniform confidence
sequences (CS) for the classical problem of estimating an unknown mean from
bounded observations. We present a general approach for deriving concentration
bounds, that can be seen as a generalization and improvement of the celebrated
Chernoff method. At its heart, it is based on a class of composite nonnegative
martingales, with strong connections to testing by betting and the method of
mixtures. We show how to extend these ideas to sampling without replacement,
another heavily studied problem. In all cases, our bounds are adaptive to the
unknown variance, and empirically vastly outperform existing approaches based
on Hoeffding or empirical Bernstein inequalities and their recent
supermartingale generalizations. In short, we establish a new state-of-the-art
for four fundamental problems: CSs and CIs for bounded means, when sampling
with and without replacement.

本文引导出了计算未知均值的置信区间和时间均匀置信序列的一般方法，并应用于研究有界均值、有限抽样和无限抽样等多个问题。

使用赌博方法估计有限随机变量的均值

Estimating means of bounded random variables by betting

Sampling is a fundamental technique, and sampling without replacement is
often desirable when duplicate samples are not beneficial. Within machine
learning, sampling is useful for generating diverse outputs from a trained
model. We present an elegant procedure for sampling without replacement from a
broad class of randomized programs, including generative neural models that
construct outputs sequentially. Our procedure is efficient even for
exponentially-large output spaces. Unlike prior work, our approach is
incremental, i.e., samples can be drawn one at a time, allowing for increased
flexibility. We also present a new estimator for computing expectations from
samples drawn without replacement. We show that incremental sampling without
replacement is applicable to many domains, e.g., program synthesis and
combinatorial optimization.

本文提出了一种通过随机程序进行无替换采样的优雅方法，包括逐步构造输出的生成性神经模型，且该方法即使在指数级的输出空间下也高效。此外，本文还提出了一种新的估计量来计算无替换采样的期望，并表明此方法适用于程序合成和组合优化等许多领域。