Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification

Summary

The study proposes a framework utilizing optimal transport theory to derive mechanism-specific and mechanism-agnostic guarantees for subsampling mechanisms in differential privacy. It focuses on leveraging conditional optimal transport to establish tight bounds on privacy parameters such as α and β, crucial for various privacy scenarios including Rényi differential privacy and moments accounting. The experiments evaluate privacy guarantees under different mechanisms including Gaussian, Laplace, and randomized response, with specific settings for noise parameters and group sizes.

Strengths

- Defining partitions into events based on dataset manipulation scenarios. - Creating couplings between conditional distributions to ensure compatibility. - Bounding mixture divergences using worst-case mixture components. - Employing advanced joint convexity techniques to tighten divergence bounds. - Applying distance-compatible couplings to enhance robustness of privacy guarantees.

Weaknesses

This manuscript is too long, which are 100 pages. Lack of theoretical analysis in the main text

Questions

Will the approach be adopted to LDP?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

NA

Summary

The paper proposes a principled approach to analyzing group-privacy amplification through sub-sampling by generalizing the coupling arguments of Balle et al., 2018. This generalization extends the analysis from $1$-neighboring datasets to $K$-neighboring datasets. The core idea is to define a coupling between partitions of batches rather than the batches themselves, ensuring that the divergence of the output distribution, conditional on the partitioning, is bounded individually by the worst-case divergence. By carefully selecting the partitioning and the optimal coupling specific to the sub-sampling mechanism, the authors demonstrate that improved Rényi and Approximate DP bounds for group privacy can be achieved, surpassing the bounds obtained by applying privacy amplification by subsampling and group-privacy theorems separately. The paper shows that the combined analysis of grouping and subsampling can be tailored to a specific base mechanism, leading to mechanism-specific privacy amplification bounds that are superior to mechanism-agnostic bounds. Although the DP bounds presented are not in closed form, they can be numerically approximated to arbitrary precision using standard techniques from the literature. The paper also provides a comprehensive evaluation of how privacy is amplified for different group sizes under Gaussian, randomized response, and Laplace base mechanisms.

Strengths

- The paper presents an in-depth analysis of privacy amplification due to subsampling under groupings. This topic has not been extensively studied before, making it an interesting paper to read. - The paper demonstrates that there is a significant interplay between subsampling and grouping concerning privacy, which is not captured in standard analyses. This finding is an important contribution to the privacy community. - The paper argues that by considering the underlying base mechanism, the amplification bounds due to subsampling can be refined beyond the tight mechanism-agnostic bounds established by Balle et al., 2018. While the results indicate this improvement for group privacy, the paper also claims it applies more generally. This could be a significant finding (although I am not entirely convinced of its validity).

Weaknesses

- The authors argue that tailoring privacy amplification through subsampling to a specific mechanism can yield better bounds than the tight amplification bounds established by Balle et al., 2018. However, it appears that the paper only demonstrates privacy amplification under subsampling for Approximate-DP with groups of size 2 or larger. Does this imply that for the standard setting with no grouping (i.e., group size of 1), there is no additional subsampling amplification achievable by tailoring the analysis to the mechanism? - I remain unconvinced that tailoring the analysis to a specific mechanism can result in tighter amplification-due-to-subsampling bounds for a group size of 1. Could the authors provide an example of two mechanisms, $\mathcal{M}_1$ and $\mathcal{M}_2$, that both satisfy $(\epsilon, \delta)$-DP tightly, but for some subsampling mechanism $S$, mechanism $\mathcal{M}_1 \circ S$ is $(\epsilon', \delta')$-DP while $\mathcal{M}_2 \circ S$ cannot achieve $(\epsilon', \delta')$-DP? - The figures in the paper (Figure 4 to Figure 10, Figure 13 to 15, Figure 17 to 20) do not include a baseline comparison with the separate application of tight amplification by subsampling and group privacy as described in lines 58-64. Without this comparison, it is unclear the gap between the bounds in this paper and the standard approach. - Definition 2.2 of Rényi divergence is misleading; a concave function $f(\bullet) = \frac{1}{\alpha - 1} \log(\bullet)$ needs to be applied to your expression for $R_\alpha(m_x\Vert m_{x'})$ to obtain the Rényi divergence. The paper's expression for $R_\alpha(m_x\Vert m_{x'})$ is typically referred to as the $\alpha$th moment of the privacy loss random variable. Although the moment $R_\alpha$ may be jointly convex (a property heavily used in the paper), the Rényi divergence is not jointly convex due to the mapping $f$ being concave. Additionally, showing that $R_\alpha$ shrinks by a factor of $p$ on subsampling does not mean that the Rényi divergence shrinks by a factor of $p$ due to the concavity of $f$. - The paper does not provide analytical bounds to help understand the asymptotics of the subsampling amplification results proved. Without the asymptotics, it's hard to verify claims of tightness. ### Minor Concerns: - The privacy amplification results are not presented in a closed-form solution, making them difficult to operationalize. - The subsampling bounds for Rényi DP have not been compared with other existing works, such as [1,2]. - The placement of figures does not match the respective appendices where they are discussed, making referencing the figures very challenging. References: [1] Steinke, Thomas. "Composition of differential privacy & privacy amplification by subsampling." arXiv preprint arXiv:2210.00597 (2022). [2] Zhu, Yuqing, and Yu-Xiang Wang. "Poisson subsampled Rényi differential privacy." International Conference on Machine Learning. PMLR, 2019.

Questions

I don't have any specific questions. I encourage authors to explain or address the problems I described in the weakness section. Based on how convincing the answers are, I'm open to adjusting my score.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Authors discuss some of the limitations of the paper. Following are some additional limitations that need addressing. - The ansatz is unwieldy for finding general use. - Closed-form asymptotics for the presented bounds are missing. - It's not clear if mechanism-specific subsampling bounds can be strictly better than mechanism-agnostic subsampling bounds for group size=1.

Summary

The authors propose a general framework for deriving mechanism-specific differential privacy guarantees for amplification by subsampling. The current methods are generally only tight in a mechanism-agnostic sense, but may possibly be significantly more private. The authors propose a new framework using conditional optimal transport, which allows stronger mechanism-specific subsampling guarantees, while still recovering the mechanism-agnostic guarantees. They also derive guarantees for privacy accountants in a unified manner. As an application, they derive tight guarantees for group privacy, where previously only a weak bound is known.

Strengths

- The problem being studied is important and relevant for practical applications. - The framework derived in this paper seems general and broadly applicable.

Weaknesses

- The authors only demonstrate improvements in the privacy bounds using their framework for group privacy. It would be interesting to see if their general framework could give improvements in other practical areas. It would also be good to demonstrate utility improvement in practice when doing DP training with these improved bounds.

Questions

- Is there any intuition about the types of scenarios where this new framework gives improvements over existing mechanism-agnostic bounds?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

- See weaknesses.

Summary

The authors propose a framework for privacy accounting of amplification by subsampling. An existing principle for this problem is to consider couplings between the output distribution of the mechanism on neighboring datasets and apply joint convexity of the privacy measure at hand. The primary contribution is to select the optimal coupling and minimize the resulting privacy bound by viewing it as an optimal transport problem.

Strengths

The paper provides a novel technical framework for accounting of subsampling amplification. The authors are able to reproduce important closure properties of dominating pairs using their framework (e.g. Proposition K.3), suggesting their framework may be used to analyze mechanisms that previously evaded accurate accounting (e.g. shuffling).

Weaknesses

The main technical result Theorem 3.4 did not feel clearly motivated in terms of Theorem 3.3 and the experiments in Appendix B. It was not clear to me from the justification provided on p.4 lines 171-174 why Theorem 3.4 is able to improve substantively upon the preceding result.

Questions

Small editorial suggestions: - It is difficult to follow the quantifier constraints in some places e.g. p.5 l.193 - p.4 l.178 Missing $y^{(1)}$ and $y^{(2)}$ under sum - p.36 l.852 should this be $x'$ not $x$?

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

4

Limitations

While the paper leverages their framework to provide new tighter bounds for the group privacy setting, the framework is only used in the other privacy accounting settings to reproduce known results (from e.g. Zhu et al 2022 or Balle et al 2018). A future direction for this work, which the authors do mention, is to apply the framework to address the practical gaps in privacy accounting for machine learning.

Summary

This work proposed a novel analysis of mechanism-specific amplification via subsampling. The authors decompose the subsampled mechanism into two parts: batch subsampling + mechanism. Then the analysis decompose the probability density into sums of pdf of every batch. The authors then provide upper bound to the divergence and specifically applied to group privacy under poisson distribution. The empirical analysis shows that the proposed analysis is able to significantly improves upon prior mechanism-agnostic group privacy bounds.

Strengths

- The paper proposed novel analysis for group privacy. The application to poisson subsampling + gaussian mechanism seems solid. - Solid theoretical guarantees. - Simulation results look promising.

Weaknesses

- Theorem 3.4 + proposition 3.5 themselves seem very costly to compute. I appreciate the authors for providing example of poisson subsampling. Still I'm wondering whether, e.g. proposition 3.5, is easy to solve for non Poisson distribution. - Similar to the previous point, a small weakness for Theorem 3.7 is it's unclear how hard it is to solve for mechanisms such as Laplace. If it does not have a closed form (or closed form hard to derive), it might lead to un-tight upper bound or costly numerical simulation in practice. (Edit: I see the Laplace analysis in the appendix) - The theoretical guarantees consist of a lot of notation. Might be helpful for the authors to add small interpretation of the bounds in e.g. Eq 2 and Eq 4 for better readibility. - Could the authors add group size = 1 in the experiment for completeness?

Questions

See above.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A