Gaussian Differential Privacy

1 Introduction

• Existing (ε, δ)-DP composition bounds can be loose, computationally hard to optimize, and unable to represent composed guarantees with a single parameter pair.This limits modular design of complex private data-analysis algorithms.Source: §1 · p. 4

1.1 Our Contributions

• f-DP retains the hypothesis-testing interpretation of privacy while representing guarantees through a full trade-off function between type I and type II errors.It generalizes (ε, δ)-DP and measures indistinguishability of neighboring datasets through testing trade-offs.Source: §1 · p. 4, §1.1 · p. 5
• f-DP composes losslessly through an algebraic operation on trade-off functions, avoiding premature summarization of intermediate privacy guarantees.The composition bound is closed and tight in general.Source: §1.1 · p. 5
• Gaussian differential privacy defines a single-parameter family from testing N(0, 1) against N(µ, 1), and composition under broad hypothesis-testing privacy notions converges to GDP.The resulting central-limit approximation provides a computationally tractable way to analyze privacy loss under composition.Source: §1.1 · pp. 5–6
• A primal-dual connection lets f-DP import results from (ε, δ)-DP, yielding a simple route to privacy amplification by subsampling.This addresses a difficulty that makes subsampling analysis complex for divergence-based relaxations.Source: §1 · p. 5, §1.1 · p. 6
• The framework gives a substantially sharper privacy analysis for noisy stochastic gradient descent than prior divergence-based analyses, including the moments-accountant comparison shown in Figure 1.SGD requires both tight composition accounting and privacy amplification by subsampling.Source: §1 · p. 5, §1.1 · p. 6, Figure 1 · p. 6

2.1 Trade-off Functions and f-DP

• f-DP requires every neighboring-dataset mechanism pair to be at least as difficult to distinguish as a reference pair characterized by a trade-off function.The trade-off function gives the minimal type II error at each type I error and completely characterizes the achievable testing region; larger functions indicate harder discrimination.Source: §2.1 · p. 8
• Trade-off functions can be symmetrized without loss of generality, and f-DP exactly generalizes (ε, δ)-DP.For an f-DP mechanism, Proposition 2.4 uses fS = max{f, f^-1}; Proposition 2.5 states that (ε, δ)-DP holds if and only if fε,δ-DP holds.Source: §2.1 · pp. 9–10

2.2 Gaussian Differential Privacy

• GDP specializes f-DP to trade-off functions for two shifted normal distributions, using a single parameter µ that decreases privacy as it increases.The Gaussian mechanism M(S) = θ(S) + ξ with ξ ∼N(0, sens(θ)^2/µ^2) satisfies µ-GDP, and this characterization is pointwise tight at maximum-sensitivity neighboring datasets.Source: §2.2 · pp. 10–11

2.3 Post-Processing and the Informativeness of f-DP

• f-DP is preserved under arbitrary randomized post-processing, and its trade-off order exactly matches the Blackwell order, making it the most informative differential privacy notion in this sense.Blackwell’s theorem [Bla50] establishes the equivalence between trade-off-function comparison and the existence of a randomized post-processing map; the section contrasts this exact match with R´enyi differential privacy and (ε, δ)-DP.Source: §2.3 · pp. 12–13

2.4 A Primal-Dual Perspective

• f-DP is equivalent to an infinite collection of (ε, δ)-DP guarantees through the convex conjugate of its trade-off function.This primal-dual representation converts collections of (ε_i, δ_i)-DP guarantees into f-DP and converts f-DP back losslessly; for GDP, the conversion is exact and supports importing existing (ε, δ)-DP results.Source: §2.4 · p. 13
• Each (ε, δ)-DP guarantee corresponds to supporting linear functions of the complete f-DP trade-off function, so restricting δ values loses information.This illustrates why the dual representation can retain privacy information that a selected subset of (ε, δ)-DP guarantees omits.Source: Figure 4 · p. 14
• The primal-dual perspective uses trade-off functions for informative f-DP reasoning and (ε, δ)-DP for simpler two-parameter arguments, converting between them when needed.The approach enables composition analysis in f-DP and imports existing subsampling theorems for (ε, δ)-DP before converting the results back.Source: §2.4 · p. 14

2.5 Group Privacy

• For groups of size k, f-DP degrades to 1 − (1 − f)◦k-DP; for symmetric f, this remains a valid symmetric trade-off function.The operation is closed and tight: the bound generally cannot be improved, and privacy weakens as k increases.Source: §2.5 · pp. 14–15
• A µ-GDP mechanism provides kµ-GDP for groups of size k, while large-group ε-DP limits yield a Laplace trade-off function not representable by any (ε, δ)-DP pair.For µ = 1 and k = 4, the iterated ε-DP trade-off is within 0.005 of the limiting function uniformly over [0, 1].Source: §2.5 · pp. 14–15

3.1 A General Composition Theorem

• Theorem 3.2 shows that adaptive composition of fi-DP mechanisms is f1 ⊗···⊗fn-DP, and this bound is closed and tight.The proof uses the Neyman–Pearson lemma rather than Blackwell’s theorem, unlike earlier approaches [MV16].Source: §3.1 · p. 17

3.2 Central Limit Theorems for Composition

• Under composition, sufficiently private symmetric trade-off functions converge to Gµ, while nontrivial fixed leakage yields µ ≍√n and becomes non-private.For triangular arrays satisfying the theorem’s conditions, the composition is asymptotically 2K/s-GDP with approximation error γ →0; GDP uniquely tracks this limit among the parameterized families discussed.Source: §3.2 · pp. 17–19
• The GDP limit theorems reduce exact f1 ⊗···⊗fn accounting to one mean parameter µ, providing a computationally efficient approximation for adaptive compositions.Exact composition can be computationally hard [MV16], whereas the approximation evaluates a single GDP parameter.Source: §3.2 · pp. 18–19

3.3 Composition of (ε, δ)-DP: Beating Berry–Esseen

• For (ε, δ)-DP, separating ε and δ components yields a Gaussian–uniform approximation, with global tensor-product approximation in O(n) time and an O(1/n) error bound.The δ component composes as f0,1−(1−δ1)(1−δ2)···(1−δn), while Theorem 3.7 establishes the improved O(1/n) rate.Source: §3.3 · pp. 20–22
• The theorem extends to approximate DP with δ ≠ 0 through the decomposition (11).Source: §3.3 · p. 22
• For μ = 1, simulations suggest c ≈ 0.1, with n = 10 yielding pointwise difference below 0.013 between G1 and its target f^⊗n_{ε,0}.The simulation result is illustrated in the right panel of Figure 5.Source: §3.3 · p. 22
• Numerical evidence suggests the same O(1/n) rate for inhomogeneous composition when ε1, …, εn are roughly equal, but no formal or quantitative result is provided.Source: §3.3 · p. 22
• The analysis obtains an O(1/n) approximation rate for repeated (ε, 0)-DP composition, improving on what direct Berry–Esseen bounds for binomial distributions can provide.Direct binomial approximation is rate-limited by Berry–Esseen, whereas the proof exploits a smoothing effect analogous to the continuity correction for normal approximations.Source: §3.3 · p. 22

4.1 A Subsampling Theorem

• Theorem 4.2 states that subsampling an f-DP mechanism at ratio p yields Cp(f)-DP.The subsampled mechanism is M ◦ Samplem, with p = m/n.Source: §4.1 · p. 23
• Cp combines symmetrization and convexification to produce a symmetric trade-off function that remains a valid privacy guarantee.The operator takes the convexification of the minimum of fp and its inverse, and satisfies Cp(f) ⩽ min{fp, f−1p} ⩽ fp.Source: §4.1 · p. 23
• As the sampling ratio decreases from 1 to 0, Cp(f) monotonically interpolates between the original guarantee f and perfect privacy Id.Cp also preserves ordering: if f ⩾ g, then Cp(f) ⩾ Cp(g), and Cp(Id) = Id.Source: §4.1 · pp. 23–24
• Corollary 4.3 converts the theorem into a closed-form amplification result for (ε, δ)-DP mechanisms.The resulting parameters use ε′ = log(1 − p + pe^ε) and δ′ = pδ.Source: §4.1 · p. 24
• The f-DP bound is significantly tighter than the classical (ε, δ)-DP subsampling theorem because trade-off functions retain information lost by the two-parameter representation.For ε = 3, δ = 0.1, and p = 0.2, the gain appears as the region between Cp(fε,δ) and fε′,δ′; this flexibility compounds under repeated composition.Source: §4.1 · pp. 24–25, Figure 6 · p. 24

4.2 Proof of the Subsampling Theorem

• The proof derives infinitely many (ε, δ)-DP guarantees, applies the classical subsampling theorem, and converts the resulting family back into Cp(f)-DP.The extension to general trade-off functions requires Proposition 4.5 and the condition g(x̄) ⩾ x̄.Source: §4.2 · p. 25

5 Application: Privacy Analysis of Stochastic Gradient Descent

• The analysis relies on f-DP’s composition and subsampling properties, replacing the moments accountant’s SGD-specific construction with general privacy tools.This approach is presented as a simple and improved analysis of private SGD.Source: §5 · p. 26

5.1 Stochastic Gradient Descent and Its Privacy Analysis

• The per-step Gaussian guarantee follows from clipping, sensitivity at most 2C/m, and Gaussian noise added to the averaged gradient.The deterministic gradient update does not change the privacy guarantee.Source: §5.1 · p. 27
• Theorem 5.1 gives Algorithm 1 the privacy guarantee Cm/n(Gσ−1)⊗T-DP.Each iteration is treated as a Gaussian mechanism on a subsampled dataset, then composed across T iterations.Source: §5.1 · pp. 26–28
• The exact tensor product Cm/n(Gσ−1)⊗T is computationally cumbersome, motivating analytical approximations that become nearly exact as T grows.The paper introduces asymptotic and Berry–Esseen analyses for this purpose.Source: §5.1 · p. 28, §5.3 · p. 29

5.2 Asymptotic Privacy Analysis

• When p tends to zero as T grows, the composition theorem gives uniform convergence under the scaling p ∼ 1/√T and supplies an explicit limit.The result targets iterative private mechanisms involving subsampling and is applied to NoisySGD.Source: §5.2 · pp. 28–29
• The asymptotic regime assumes T → ∞ with sampling fraction p = m/n → 0, while the paper notes that many deep-learning settings have small Em/n.The discussion relates the assumption to prior private-SGD analysis and gives AlexNet as an example.Source: §5.2 · pp. 28–29

5.3 A Berry–Esseen Privacy Bound

• The Berry–Esseen analysis yields sharp, computer-evaluable privacy guarantees but does not admit simple closed forms.Its moment calculations use the subsampled Gaussian trade-off functions Cp(Gμ).Source: §5.3 · pp. 29–30

6 Discussion

• f-DP generalizes (ε, δ)-DP while retaining hypothesis-testing semantics and enabling lossless reasoning about composition, post-processing, and group privacy.Its central-limit theorem identifies Gaussian differential privacy as the unique hypothesis-testing-based definition that can tightly handle composition.Source: §6 · p. 30
• The framework supports privacy amplification by subsampling and gives a tractable approach to analyzing iterative methods such as SGD.The paper states that the subsampling theorem significantly improves the state-of-the-art counterpart in the (ε, δ)-DP setting.Source: §6 · p. 30
• Extending the central limit theorem to inhomogeneous compositions could provide strong finite-sample privacy approximations for a broader range of problems.The proposed extension allows trade-off functions to differ across composed mechanisms.Source: §6 · pp. 30–31
• The subsampling guarantee may be improvable for some trade-off functions, although the bound is tight when f = 0 and the original mechanism is blatantly non-private.The paper also identifies local f-DP estimation and the correct complexity measure as open questions.Source: §6 · p. 31
• The f-DP framework may tighten minimax estimation bounds by replacing an (ε, δ)-DP constraint with a more stringent trade-off-function constraint.The upper bound remains valid for the estimator, while the lower bound may improve under the stronger constraint.Source: §6 · p. 31
• The paper reports evidence that f-DP can analyze diverse algorithms but leaves practical evaluation of the privacy definition to future work.This marks practical evaluation as a remaining scope boundary rather than a completed part of the study.Source: §6 · p. 31

Trade-off functions

• A function is a trade-off function if and only if it is convex, continuous, non-increasing, and satisfies f(x) ≤ 1 − x on [0, 1].The proof constructs a realizing pair of distributions on [0, 1] from any function with these properties and derives the conditions using optimal testing.Source: A Technical Details in Section 2 · pp. 35–36

Symmetry

• For an f-DP mechanism, symmetry is obtained by replacing f with fS = max{f, f−1}, where f−1 is the trade-off function with the hypotheses reversed.The reversal identity is T(P, Q) ↔ T(Q, P), and the left-continuous inverse handles non-strictly decreasing trade-off functions.Source: A Technical Details in Section 2 · p. 36

Gaussian and log-concave mechanisms

• For a log-concave density p, the shifted-distribution trade-off function is T(ξ, t + ξ)(α) = F(F−1(1 − α) − t), with Gaussian GDP as a special case.Log-concavity makes the likelihood ratio monotone, so Neyman–Pearson tests are threshold tests; the result is also necessary when the formula holds for every t > 0.Source: A Technical Details in Section 2 · p. 38

Primal-to-dual characterization

• For symmetric trade-off functions, Proposition 2.12 gives a primal-to-dual characterization, and its GDP specialization characterizes µ-GDP through the corresponding dual expression.The dual representation uses tangent lines with slope −e^ε and identifies the associated (ε, δ) envelope through the convex conjugate.Source: A Technical Details in Section 2 · p. 38

Group privacy

• For groups of size k, f-DP composes as 1 − (1 − f)◦k; in particular, µ-GDP becomes kµ-GDP.The composition operation preserves the trade-off-function class, and GDP composition follows from Gµ ˆ◦ Gµ′ = Gµ+µ′.Source: A Technical Details in Section 2 · pp. 39, 41

Asymptotic composition

• With µ fixed and ε = µ/k, repeated composition converges uniformly to GDP as k → ∞, while for ε = 0.5 the predicted limit is almost indistinguishable from composition even at k = 4.The small-k comparison uses Figure 8, where the distinction between the composed curve and predicted limit is described as almost invisible.Source: A Technical Details in Section 2 · p. 41, Figure 8 · p. 41

• The iterates are increasing and eventually follow linear dynamics below a threshold and flip-linear dynamics above it, with the transition determined by the initial value.For every n and initial x_0, the dynamics can switch at most from the linear regime to the flip-linear regime; the analysis splits into three initial-value cases.Source: A Technical Details in Section 2 · p. 43
• The three initial-value cases yield distinct limiting expressions, including e^{x_0} when x_0 < 1/(2e), an intermediate expression involving e^-1·(1/4)x_0, and e^-1(1−x_0) when x_0 is sufficiently large.The supplied result passages collect the cases and identify the corresponding regime boundaries, including x_0 = 1/2 and the intermediate interval [1/(2e), 1/2].Source: A Technical Details in Section 2 · p. 43
• Pointwise convergence of the non-increasing trade-off functions implies uniform convergence whenever the limiting function is continuous on the closed interval.This is the role of Lemma A.7, whose proof uses uniform continuity of the limit, a finite partition, and monotonicity of the approximating functions.Source: A Technical Details in Section 2 · pp. 43–44

B Conversion from f-DP to Divergence Based DP

• The section's central goal is converting f-DP trade-off functions into divergence-based DP guarantees, including Rényi divergence.The framework provides a general tool followed by explicit formulas for broad divergence classes.Source: B Conversion from f-DP to Divergence… · pp. 44, 47
• For any divergence satisfying data processing, a functional maps each trade-off function to the corresponding divergence value, independently of the representing distributions.This follows because equal trade-off functions imply equal divergence values, while larger trade-off functions yield smaller divergence values.Source: B Conversion from f-DP to Divergence… · pp. 44–45
• The general F-divergence formula enables direct computation of several divergences from a trade-off function, including total variation and KL divergence.The construction represents the trade-off function using a uniform distribution and a density derived from its derivative, with an atom accounting for f(0).Source: B Conversion from f-DP to Divergence… · pp. 45–46
• The resulting functional is central to the paper's central limit theorem, where it is denoted kl(f).The section also specializes the conversion to Rényi differential privacy and gives a simple expression for µ-GDP.Source: B Conversion from f-DP to Divergence… · pp. 46–47
• Trade-off-to-divergence conversion is lossless and unimprovable, whereas reverse conversions between divergences can require case-by-case analysis.This difference reflects that trade-off functions preserve the full type-I/type-II error trade-off while divergences often summarize distributions by numbers.Source: B Conversion from f-DP to Divergence… · pp. 47, 49
• The full collection of Rényi divergences still does not induce Blackwell's order, so Rényi comparison can disagree with hypothesis-testing informativeness.The paper gives an analytical proposition establishing two distribution pairs with the relevant Rényi and testing-order mismatch.Source: B Conversion from f-DP to Divergence… · pp. 47–48

Proof of Lemma C.1

• The key lemma compares two pairs of randomized algorithms and shows that one joint testing problem is at least as difficult to distinguish as the other.The proof constructs rejection rules by conditioning on the shared input and assembling optimal tests for each slice.Source: C A Self-contained Proof of the… · p. 49

Well-definedness of ⊗

• The comparison lemma implies that equivalent representations of f produce equivalent product trade-off functions, making the composition tensor ⊗ well-defined.Equality in the premise yields equality in the conclusion, while the general result gives the needed inequality.Source: Figure 10 · p. 49, C A Self-contained Proof of the… · p. 50, Figure 11 · p. 50

Composition theorem

• For a two-step composition, if M1 is f-DP and M2(·, y) is g-DP for every fixed y, then the combined mechanism is f ⊗ g-DP.The proof applies Lemma C.1 to the output of M1 and the conditional mechanism M2, with the product-distribution construction illustrated in Figure 12.Source: C A Self-contained Proof of the… · pp. 50–51, Figure 12 · p. 51

Proof of Lemma C.1

• The proof of Lemma C.1 uses Neyman–Pearson optimal tests, slicing a joint rejection rule by the shared input and recombining the resulting tests.The constructed test preserves the target level because the slice levels are averaged under the same input distribution, while its power meets the required comparison.Source: C A Self-contained Proof of the… · pp. 51–52

Basic properties

• The ⊗ product is well-defined, commutative, associative, has identity Id, respects inversion, and composes GDP parameters by squared addition.For GDP, G_µ1 ⊗ G_µ2 ⊗ · · · ⊗ G_µn = G_µ with µ = √(µ1^2 + · · · + µn^2).Source: D Omitted Proofs in Section 3 · p. 52

Asymptotic degeneration

• The proposition states that lim n→+∞ f⊗n(α) = 0 for every α ∈ (0, 1], and that this convergence is exponentially fast.Source: D Omitted Proofs in Section 3 · p. 53

Berry–Esseen central limit theorem

• Theorem 3.4 bounds the composition uniformly between shifted Gaussian trade-off functions, G_µ(α + γ) − γ and G_µ(α − γ) + γ.The error parameter γ comes from applying Berry–Esseen to the normalized log-likelihood ratio under both hypotheses.Source: D Omitted Proofs in Section 3 · pp. 54, 55, 58, 60
• The Berry–Esseen proof represents each symmetric trade-off function as T(P,Q_i), reducing composition to testing product distributions whose log-likelihood ratio is an independent sum.Neyman–Pearson threshold tests and normalization by the functionals kl, κ2, and κ3 enable classical Berry–Esseen bounds to control the composed trade-off function.Source: D Omitted Proofs in Section 3 · pp. 55, 57, 58

Functional preliminaries

• The appendix verifies that the theorem’s kl, κ2, κ3, and shadow functionals are well-defined and nonnegative, with their identities obtained through density changes of variables and symmetry.The kl functional is controlled at endpoint singularities using log |f′(x)| ≤ |f′(x)| − 1 and Jensen’s inequality.Source: D Omitted Proofs in Section 3 · pp. 55–56

Proof of the composition CLT

• The triangular-array composition converges uniformly to the GDP trade-off function as γn → 0 and µn → 2K/s under the stated moment conditions.Berry–Esseen bounds, vanishing maximum privacy loss, and control of third moments yield pointwise convergence; continuity and Lemma A.7 upgrade it to uniform convergence.Source: D Omitted Proofs in Section 3 · pp. 60, 62

Tensoring with f0,δ

• Tensoring with f0,δ is derived from testing shifted uniform distributions, yielding the trade-off function f0,δ(α) = max{1 − δ − α, 0} and the associated product-test construction.The proof identifies the optimal test on the nonoverlapping intervals and uses an optimal test for P versus Q on the overlapping region.Source: D Omitted Proofs in Section 3 · p. 62

Proof of Theorem 3.6

• For approximate-DP compositions, the δ terms converge as δ(n) → 1 − e^-δ, while the pure-DP factors converge to GDP with parameter µ, producing the combined limiting trade-off function.The proof combines the product identity for f0,δ with Theorem 3.5 and uniform convergence of the pure-DP factors.Source: D Omitted Proofs in Section 3 · pp. 63–64

Corollaries for pure ε-DP

• The corollaries provide Berry–Esseen-style bounds for pure ε-DP composition, with a homogeneous-case derivation highlighting a 1/√n convergence rate.The bounds sandwich the composed trade-off function between shifted GDP curves, and the homogeneous calculation uses explicit moment functionals for fε,0.Source: D Omitted Proofs in Section 3 · p. 64

Moment calculations

• For homogeneous pure ε-DP, the relevant moment functionals are kl(fε,0) = εt, κ2(fε,0) = ε2, κ3(fε,0) = ε3, and κ̄3(fε,0) = ε3(1 − t4).These identities follow by evaluating the two-point log-likelihood-ratio distribution, with t = tanh ε.Source: D Omitted Proofs in Section 3 · p. 65

Proof of Theorem 3.7

• The proof establishes that both σ_n → 1 and the normalized cdf F_n → Φ converge at rate 1/n.The rate for F_n is obtained through Lemmas E.1 and E.2, with the latter proving sup_x∈R |F_n(x) − Φ(x)| = O(1/n).Source: E Proof of Theorem 3.7 · pp. 66, 67, 69
• The proof replaces linear interpolation of binomial-tail points with randomized Neyman–Pearson tests for B(n,p) versus B(n,q), parameterized by a threshold k and boundary randomization c.Adding an independent U[0,1] variable makes the cdf of X+Y a bijection, uniquely determining the optimal test for each type I error.Source: E Proof of Theorem 3.7 · p. 66

Lemma E.1

• For ε = 1/√n, Lemma E.1 uses careful Taylor expansions to control the variance and related quantities needed for the Gaussian limit.The expansion uses tanh x = x − x^3/3 + o(x^4) and combines separate expansions of the relevant factors.Source: E Proof of Theorem 3.7 · pp. 67–68

Lemma E.2

• Lemma E.2 proves the cdf approximation by reducing it, via Fourier inversion, to characteristic-function estimates controlled through Taylor expansion.The proof splits the Fourier-domain error into three integrals and bounds each by O(1/n), using local and tail estimates.Source: E Proof of Theorem 3.7 · pp. 68–70

Proof of Lemma E.3

• A separate treatment of the two integrands cannot work because the resulting alternative integrand is not integrable, with ϕ_n(0)=1 causing persistent behavior near zero.The characteristic function ϕ_n is not in L1(R), since X + Y has a piecewise-constant density; therefore the usual absolutely integrable Fourier-inversion shortcut is unavailable.Source: E Proof of Theorem 3.7 · p. 74
• The proof of inversion formula E.3 proceeds by applying the general inversion formula to F_n and justifying the limiting integral through domination.Because ϕ_n is continuous and decays like 1/|t|, the integrand is dominated by O(t^-2 ∧ 1), allowing the limit to equal the Lebesgue integral.Source: E Proof of Theorem 3.7 · p. 74
• Subtracting the two inversion formulas avoids requiring ϕ_n to be integrable, after which taking a → −∞ completes the proof.The Riemann–Lebesgue lemma cannot be applied directly because ϕ_n(t)/t is not integrable; subtracting the formulas yields the needed relation before taking the limit.Source: E Proof of Theorem 3.7 · p. 75

Tightness

• Releasing one uniformly selected individual is exactly (0, 1/n)-DP, showing the subsampling theorem is generically unimprovable.The corresponding trade-off function is f0,1/n, and tests attain every point on the curve.Source: F Omitted Details in Section 4 · p. 75

Symmetrization

• The symmetrization operator maps a general trade-off function to a symmetric one by combining f, f−1, and a linear interpolation or maximum depending on interval overlap.When [0, ¯x] and [f(¯x), 1] are disjoint, interpolation fills the gap; when they overlap, the maximum is used.Source: F Omitted Details in Section 4 · pp. 76, 78, Figure 13 · p. 77
• A mechanism satisfying (ε, 1 + f∗(−eε))-DP for every ε ⩾ 0 also satisfies Symm(f)-DP.This general tool converts a collection of ordinary DP guarantees into an f-DP guarantee and subsumes the symmetric case.Source: F Omitted Details in Section 4 · p. 76

Privacy amplification by subsampling

• Subsampling analysis separates cases where the differing individual is included or excluded, then averages their type-I and type-II errors with probabilities p = m/n and 1 − p.Neighboring sampled datasets provide an additional inequality, yielding a linear program for the best lower bound on β.Source: F Omitted Details in Section 4 · pp. 79–80
• The resulting bound is β ⩾ p(−eεα + 1 − δ) + (1 − p)(1 − α) = −eε′α + 1 − δ′, so the subsampled mechanism is (ε′, δ′)-DP.The proof obtains the bound by minimizing the associated linear program and then reparameterizing ε′ and δ′.Source: F Omitted Details in Section 4 · pp. 80–81

Integral identities

• For symmetric trade-off functions, the unique fixed point and the derivative-based function g(x) organize the χ2 and KL calculations used in the limit analysis.The proof identifies where the derivative crosses −1 and expresses the relevant integrals through changes of variables involving f−1.Source: G Omitted Proofs in Section 5 · pp. 82–84

Proof strategy

• The Section 5 proof reduces the asymptotic result to computing limits for the functionals in Theorem 3.5.The analysis considers the small-sampling regime and rescales the relevant quantities according to T ∼ p−2.Source: G Omitted Proofs in Section 5 · p. 83

Regularity conditions

• The assumption ∫ g(x)^4 dx < +∞ ensures the needed powers of g are integrable, while dominated convergence justifies exchanging limits and integrals.This supplies the regularity needed for the asymptotic expansions of the divergence functionals.Source: G Omitted Proofs in Section 5 · p. 84

Asymptotic expansion

• The expansions identify the limiting constant through χ2 and KL terms, while the third-order functional is negligible because κ3(Cp(f)) = o(p2).Consequently, T · κ3(Cp(f)) → 0 in the regime T → p0.Source: G Omitted Proofs in Section 5 · p. 84

Gaussian limit

• Under the stated assumptions, all limits in Theorem 3.5 hold and the composition converges to a Gµ limit.The Gaussian trade-off function case satisfies the required fourth-power integrability condition because the resulting integral is a finite combination of standard-normal moment generating functions.Source: G Omitted Proofs in Section 5 · pp. 84–86