PaperlayerView exact revision on arXiv

Source-linked AI summary

Subsampled Rényi Differential Privacy and Analytical Moments Accountant

Yu-Xiang Wang, Borja Balle, Shiva Kasiviswanathan

arXiv:1808.00087v2cs.LGcs.CRstat.ML

TL;DR

Subsampling is central to private machine learning, but generic analytical conversion of a mechanism’s RDP parameters to those of its subsampled version was unavailable. The paper derives tight bounds for sampling without replacement, develops an analytical moments accountant for symbolic composition and conversion to (ϵ, δ)-DP, and reports improved privacy parameters over baseline approaches.

  • Problem

    Generic analytical bounds for the RDP parameters of subsampled mechanisms were unavailable beyond special cases, despite subsampling’s importance in differentially private algorithms.

  • Method

    The paper derives tight RDP amplification bounds for sampling without replacement and uses them in an analytical moments accountant that tracks privacy loss symbolically.

  • Results

    Upper and lower bounds match up to a multiplicative constant across three mechanisms, while composed subsampled Gaussian mechanisms achieve about an order of magnitude smaller ϵ than baseline approaches in high privacy and five orders in low privacy.

  • Takeaways & Limitations

    The results expand analytical RDP guarantees to subsampled Gaussian, Laplace, randomized-response, posterior-sampling, and other mechanisms, supporting flexible private-algorithm design.

  • Takeaways & Limitations

    The RDP bound can be substantially improved using more fine-grained per-instance RDP, so the standard bound is not always optimal.

Abstract

from arXiv · show

We study the problem of subsampling in differential privacy (DP), a question that is the centerpiece behind many successful differentially private machine learning algorithms. Specifically, we provide a tight upper bound on the Rényi Differential Privacy (RDP) (Mironov, 2017) parameters for algorithms that: (1) subsample the dataset, and then (2) applies a randomized mechanism M to the subsample, in terms of the RDP parameters of M and the subsampling probability parameter. Our results generalize the moments accounting technique, developed by Abadi et al. (2016) for the Gaussian mechanism, to any subsampled RDP mechanism.

1 Introduction

The paper addresses the lack of generic analytical RDP bounds for subsampled mechanisms by deriving bounds in terms of the original mechanism and sampling ratio. It also develops an analytical moments accountant and identifies phase-transition behavior as the RDP order increases.

  • 1 Introduction: The paper provides the first general result for RDP amplification under sampling without replacement, where a uniform subset of size m ≤ n is selected before applying a mechanism.The subsampling ratio is γ := m/n.
  • 1 Introduction: A tight RDP bound expresses the subsampled mechanism’s parameter in terms of the original mechanism’s RDP parameter and sampling ratio γ, applying to any RDP mechanism.The bound covers subsampled Gaussian, Laplace, randomized response, and posterior-sampling mechanisms.
  • 1 Introduction: As α increases, a phase transition occurs near γ^α*e^ϵM(α*) ≈ 1, separating sampling-dependent and mechanism-dependent regimes.Below the transition, the bound is O(αγ^2(e^ϵM(2) −1)); above it, behavior approaches ϵM(α) or O(γϵM(∞)).
  • 1 Introduction: The analysis introduces a ternary version of the Pearson–Vajda divergence as a new theoretical quantity for studying subsampling.The paper relates this quantity to the effects of subsampling and privacy definitions.
  • 1 Introduction: The analytical moments accountant tracks Rényi privacy parameters symbolically and converts them to (ϵ, δ)-DP using efficient numerical methods.Unlike the original moments accountant, it avoids specifying a discrete list of moments in advance; experiments confirm improved privacy parameters.
  • 1 Introduction: The paper emphasizes efficiently computable tight constants because asymptotic bounds alone provide limited practical guidance for privacy–utility trade-offs.The main result is the bound in Theorem 9, whose practical value depends on explicit constants.

2 Background and Related Work

This section introduces differential privacy, privacy-loss analysis, RDP, and moments accounting as the background for analyzing subsampled mechanisms. It connects these tools to private SGD and describes numerical optimization for converting privacy representations.

  • 2 Background and Related Work: Differential privacy provides information-theoretic protection against distinguishing neighboring datasets, with smaller ϵ and δ indicating stronger guarantees.The definition supports privacy-loss and composition analyses.
  • 2 Background and Related Work: Subsampling exploits randomness before applying a mechanism and can amplify an (ϵ, δ)-DP guarantee to approximately (O(γϵ), γδ)-DP.This amplification underlies private stochastic-gradient methods such as NoisySGD.
  • 2 Background and Related Work: The moments accountant tracks evaluations of the privacy-loss CGF, while convexity enables arbitrary-accuracy optimization by bisection in logarithmic time.The optimization remains possible with black-box or noisy access to the CGF or its derivative.
  • 2 Background and Related Work: RDP generalizes several differential-privacy notions by bounding α-Rényi divergence between outputs on neighboring datasets.Its functional form represents the privacy parameter as ϵM(α), with α = ∞ corresponding to pure DP.
  • 2 Background and Related Work: The paper’s subsampling problem is to bound ϵM◦subsample(α) from the RDP function ϵM(α) of the original mechanism.This targets a generic conversion unavailable beyond special cases such as Gaussian mechanisms under Poisson subsampling.

3 Our Results

The paper gives a general RDP amplification theorem for subsampled mechanisms, proves its bound is generally tight, and builds an analytical moments accountant for composition. The results cover arbitrary RDP mechanisms and include practical extensions, while exhibiting phase-transition behavior and scope for stronger bounds under additional assumptions.

  • Amplification theorem: Theorem 9 bounds the RDP of subsampling without replacement followed by M using M’s RDP parameters and sampling ratio γ.For integer α ≥ 2, the composed mechanism satisfies (α, ϵ′(α))-RDP when M satisfies (α, ϵ(α))-RDP.
  • Generality: The result applies to any Rényi-differentially-private mechanism, extending prior analytical bounds beyond subsampled Gaussian mechanisms.The paper specifically notes coverage of exponential-family mechanisms and pure-DP mechanisms such as Laplace and randomized response.
  • Refinements: Additional assumptions can strengthen Theorem 9 by replacing a coefficient bound with an exact forward finite-difference evaluation.The paper notes that these assumptions hold for the Gaussian mechanism.
  • Gaussian specialization: For subsampled Gaussian mechanisms, the upper bound simplifies to O(γ^2α/σ^2) when σ^2 is large, while the small-σ^2 regime is covered beyond earlier results.The small-σ^2 regime is explicitly identified as one not covered by Abadi et al. (2016).
  • Optimality: The upper bound is generally unimprovable: in one regime, it matches the lower bound up to a constant multiplicative factor, and elsewhere only a vanishing additive term separates them.The additive gap goes to 0 as γ → 0 and α → ∞.
  • Analytical moments accountant: The analytical moments accountant tracks CGFs symbolically for adaptive compositions, adjusts them for subsampling through Theorem 9, and supports privacy-parameter queries.Its conversion queries achieve oracle complexity O(log(λ*/τ)) for accuracy τ.
  • Analytical moments accountant: Compared with Abadi et al.’s accountant, the approach avoids predefined finite orders and numerical integration while supporting generic subsampled RDP mechanisms.The paper presents these properties as improving efficiency and accuracy when tracking ϵ and δ under composition.

4 Experiments and Discussion

Experiments compare RDP bounds and composition methods for subsampled Gaussian, Laplace, and randomized-response mechanisms. The bounds are closely matched, and composition results vary by mechanism: RDP is eventually much better for Gaussian and at least competitive for Laplace and randomized response.

  • RDP bounds: For all three mechanisms, Figure 1 shows upper and lower RDP bounds matching up to a multiplicative constant across orders α.The Gaussian case also includes asymptotic approximations.
  • Composition comparison: For subsampled Gaussian, RDP initially performs worse than naïve and strong composition, while the lower bound indicates this is a fundamental limitation of the RDP-to-(ϵ, δ)-DP approach.The paper relates this effect to CGF-based conversion and notes it does not affect typical RDP usage.
  • Composition comparison: Figure 2 composes each mechanism for 600,000 accesses with δ = 1e−8, plotting ϵ against composition rounds k against naïve and calibrated strong-composition baselines.The RDP curves use the analytical moments accountant’s δ ⇒ ϵ query.
  • Composition comparison: As k grows, RDP composition yields about an order-of-magnitude smaller ϵ in the high-privacy regime and five orders of magnitude smaller ϵ in the low-privacy regime.These comparisons are reported for the subsampled Gaussian mechanism relative to baseline approaches.
  • Composition comparison: For subsampled Laplace and randomized response, the RDP approach achieves about the same or better ϵ bound than subsampling plus strong composition for every k.The comparison is reported across the corresponding high- and low-privacy panels.

5 Conclusion

The paper establishes tight RDP bounds for without-replacement subsampling, introduces an analytical moments accountant, and extends coverage to multiple subsampled mechanisms. Experiments report substantially improved composed privacy parameters, while future work targets broader mechanisms and data-dependent guarantees.

  • Tight upper and lower bounds characterize the RDP parameter of subsample-then-apply-M algorithms in terms of M's RDP parameter.
  • The analysis connects subsampling with linearized privacy variables, higher-order discrete differences of moment-generating functions, and ternary Pearson–Vajda divergence.
  • The analytical moments accountant composes RDP symbolically and efficiently converts it to (ϵ, δ)-DP for any chosen δ or ϵ.
  • The results extend RDP guarantees to subsampled Gaussian, Laplace, randomized-response, posterior-sampling, and other mechanisms.
  • Future work includes advanced private neural-network mechanisms, data-dependent per-instance RDP, subsampling-based statistical procedures, and sublinear exploratory algorithms.

B.1 A Sketch of the Proof of Theorem 9

The proof introduces ternary-|χ|α-differential privacy, exploits its clean subsampling behavior, bounds subsampled RDP through it, and converts back to RDP using several bounds.

  • Part 1: Ternary-|χ|α-divergence and Natural Subsampling: Ternary-|χ|α-divergence measures discrepancy among three distributions and underlies a privacy definition tailored to subsampling.
  • Part 1: Ternary-|χ|α-divergence and Natural Subsampling: Proposition 16 shows that subsampling scales ζ-ternary-|χ|α-DP to γζ-ternary-|χ|α-DP.
  • Part 1: Ternary-|χ|α-divergence and Natural Subsampling: The subsampling proof conditions on sampling events, adds dummy variables to align mixture components, and uses Jensen’s inequality to simplify mixture divergences.
  • Part 2: Bounding RDP with Ternary-|χ|α-DP: RDP of the subsampled mechanism is bounded by expressing it as a linear combination of binary-|χ|α-DP parameters through Newton’s series expansion.
  • Part 3: Bounding Ternary-|χ|α-DP using RDP: Binary and ternary-|χ|α-DP are equivalent up to a factor of 4, enabling RDP-based bounds on the ternary parameters.
  • Part 3: Bounding Ternary-|χ|α-DP using RDP: For j ≥2, the proof combines bounds ζ(j) ≤2e^(j−1)ϵ(j) and ζ(j) ≤e^(j−1)ϵ(j)(e^ϵ(∞)−1)^j.

B.5 Improving the Bound in Theorem 9

Under tightness and self-consistency assumptions, the paper derives tighter RDP bounds by replacing a general term with a more exact evaluation.

  • Tightness requires the RDP guarantee to be attained by adjacent-dataset distributions at every integer order.
  • Self-consistency requires the same adjacent-distribution pair to attain maximal |χ|α-divergence across the relevant parameter range.
  • For integer α ≥2, Theorem 27 gives tighter RDP bounds for subsampled mechanisms satisfying tightness and (α+1)-self-consistency.
  • The improved derivation replaces e^(j−1)ϵ(j) min{2,(e^ϵ(∞)−1)^j} with a more exact evaluation.

C Asymptotic Approximation of Rényi Divergence for Subsampled Gaussian Mechanism

The paper approximates subsampled Gaussian output distributions asymptotically by Gaussians, revealing how dataset-induced variance and mechanism noise shape Rényi divergence. The approximation is informative but restricted to a specific large-sample, vanishing-ratio regime.

  • The subsampled Gaussian mechanism releases a noisy mean over a random subset, yielding a Gaussian conditional on the sampled subset.
  • A sampling-without-replacement central limit theorem motivates approximating the resulting mixture distribution by a Gaussian.
  • The asymptotic analysis considers dataset size and subset size tending to infinity while γ=|J|/n tends to zero.
  • Dataset-induced variance can exceed or fall below added Gaussian noise, producing substantially different Rényi divergences.
  • The bad-data example matches the Theorem 9 upper bound at rate O(αγ^2/σ^2) for α ≪σ^2/γ.
  • For good data, subsampling variance dominates mechanism noise and the per-instance RDP loss can be γn times smaller than in the bad case.
  • Finite-difference operators compute all orders through O(α^2) evaluations rather than the naïve O(α^3).

E On Tightness and Self-consistency Guarantees

The paper emphasizes that RDP bounds must be realizable by underlying adjacent-dataset distributions, and proves tightness and self-consistency for the Gaussian mechanism.

  • RDP guarantees must correspond to actual distribution pairs, rather than merely conservative estimates that may not be jointly realizable.The paper notes that non-realizable bounds obscure where slack occurs across orders α.
  • Self-consistency reduces to showing that the same Gaussian pair maximizes the relevant |χ|α-divergence for every even α.The proof considers pairs N(0, σ2) and N(µ, σ2) with 0 ≤ µ ≤ 1.
  • For the Gaussian mechanism with sensitivity 1, ϵ(α) = α/(2σ2) is a tight and self-consistent RDP bound.The bound is attained by N(0, σ2) and N(1, σ2).
  • The relevant divergence increases monotonically with the mean separation µ, so its maximum occurs at µ = 1.This identifies the adjacent Gaussian pair as the maximizing pair.
  • The analysis relies on checking self-consistency through convexity of |χ|α-divergence over a convex polytope.For such distribution sets, checking the vertices suffices.

F Other Properties of Ternary-|χ|α-DP

This section relates |χ|α-based privacy to standard privacy measures and develops bounds connecting ternary divergences with Rényi and Pearson-Vajda divergences.

  • At α = 1, binary- and ternary-|χ|α-divergences reduce to total variation distance, while α = 2 yields the χ2-distance for the binary case.These special cases connect the generalized divergences to familiar privacy-related quantities.
  • Binary-|χ|α-DP implies (ϵ, δ)-DP through a tail bound on the privacy loss random variable.The conversion applies for all ϵ > 0.
  • The conversion proof uses Markov’s inequality after changing variables from p/q to e^(log(p/q)).This links divergence control to a privacy-loss tail probability.
  • A Hölder-based lemma bounds the relevant ternary quantity using Rényi divergence and Pearson-Vajda divergence.The result holds for conjugate exponents u, v ≥ 1 and integer j ≥ 2.
  • Choosing v = ∞, u = 1 recovers the earlier lemma, while u = v = 2 gives an even-order specialization.These parameter choices provide useful variants of the general bound.

G Analytical Moments Accountant and Numerically Stable Computation

The analytical moments accountant tracks privacy-loss CGFs symbolically, enabling flexible RDP and (ϵ, δ)-DP queries, while additional procedures address computational and numerical limitations.

  • Analytical moments accountant: The accountant maintains the sum of mechanism CGFs symbolically and supports RDP and (ϵ, δ)-DP queries for heterogeneous adaptive mechanism sequences.It can evaluate the aggregate CGF at any positive λ.
  • Privacy conversion: RDP converts to (ϵ, δ)-DP through univariate optimization, while α = 1 and α = +∞ are tracked separately.The optimization problems are solved using the accountant’s CGF-query procedures.
  • Flexibility: The accountant keeps all λ ≥ 1 symbolically, unlike prior approaches that require a predefined discrete list of orders.This supports dynamic choices of privacy parameters.
  • Complexity: O(1) time composes a new mechanism, O(L) space stores L unique mechanisms, and CGF queries take O(L) time.The same structure supports privacy queries with stated CGF-evaluation complexity.
  • Complexity: The analytical accountant is an exponential improvement over the naïve array-based implementation, which uses O(λmax) time and space.The naïve implementation also cannot choose λmax dynamically.
  • Approximation: For subsampled mechanisms, exact RDP evaluation can cost O(α2), so the method switches above αthresh to an optimization-based upper bound.The bound is expressed as a log-sum-exp over α + 1 terms, with further improvement possible under a geometric-series condition.
  • Feasibility and stability: CGF upper bounds that lack valid shape properties can be projected into a feasible set without changing the accountant’s computational guarantees.The projected bound is convex, increasing, zero at 0, and preserves the relevant monotonicity.
  • Numerical stability: Numerical cancellation and error propagation make accurate closed-form χj-divergence computation difficult for large j, which remains an open problem.Finite-difference and signed-log representations reduce overflow but do not fully resolve large-j inaccuracies.

H Properties of Cumulant Generating Functions and Rényi Divergence

The paper uses structural properties of cumulant generating functions to establish efficient privacy optimization and gives a first-principles proof of CGF convexity.

  • CGF properties: A CGF is infinitely differentiable, convex, and passes through the origin under the stated finiteness conditions.For non-degenerate distributions, convexity is strict.
  • CGF properties: The derivative of a CGF increases monotonically from the infimum to the supremum of the random variable’s support.This monotonicity underpins optimization over the privacy parameter.
  • CGF properties: Privacy-loss CGFs additionally satisfy K_M(-1) = 0.This is a structural constraint specific to privacy-loss random variables.
  • Optimization: These CGF properties provide the computational basis for the analytical moments accountant.They support efficient querying even with black-box access to CGFs or their derivatives.
  • Proof strategy: The paper proves CGF convexity from first principles using Hölder’s inequality rather than a variational characterization of Rényi divergence.The proof combines convexity arguments with conjugate exponents.
  • Optimization: The resulting optimization problem is log-convex, while the alternative problem is unimodal or quasi-convex.These properties imply unique minimizers and enable bisection or convex optimization to arbitrary precision.

I Rényi Divergence of Exponential Family Distributions and RDP

The section derives Rényi divergence and RDP guarantees for exponential-family mechanisms, using the log-partition function’s local Lipschitz and smoothness properties. It also refines the bound by optimizing the locality parameter and replacing a uniform term with a potentially tighter expression.

  • Rényi divergence: The Rényi divergence between natural exponential-family distributions is expressed through the log-partition function A evaluated at a convex combination of their natural parameters.
  • Rényi divergence: At α = 1, the Rényi divergence becomes the Kullback–Leibler divergence and equals the Bregman divergence associated with A.
  • Exponential-family mechanisms release θ by sampling from an exponential-family distribution, whose normalization constant A is the log-partition function.
  • RDP guarantee: Under assumptions on parameter sensitivity, local Lipschitzness, and local smoothness, the mechanism satisfies (α, ϵ(α))-RDP for α ∈ (1, κ/∆ + 1] when κ ≥ ∆.
  • RDP refinement: For fixed α, κ can be optimized over feasible values, and the term 2B(α∆)∆ can be improved to [B((α −1)∆) + B(∆)]∆.
Loading 1808.00087v2…