PaperlayerView exact revision on arXiv

Source-linked AI summary

Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling

Xujun Che, Depeng Xu

arXiv:2609.01944v1cs.CR

TL;DR

Privacy accounting for structured participation may rely on Poisson-based formulas even without independence, but the precise scope of that substitution is unclear. This paper characterizes when negative dependence preserves dominance, identifies reversals, and locates a finite crossover threshold.

  • Problem

    Privacy accountants assume Poisson subsampling, while deployed systems use different samplers; mismatches can silently invalidate reported guarantees.

  • Method

    The paper analyzes Rényi and hockey-stick divergences under negative dependence, using occupancy expectations, couplings, and sign-balanced noise Gram matrices.

  • Results

    Negative association guarantees integer-order remove-direction dominance, while random allocation reverses dominance below order 3/2 and below (1-q)^t, then crosses at finite γ★.

  • Takeaways & Limitations

    Poisson-based accounting is sound only within identified dependence and threshold regimes; outside them, implementers need alternative privacy accounting.

  • Takeaways & Limitations

    Candidate asymptotic laws for the crossover remain partly heuristic, with uniform Edgeworth error control left as an open problem.

Abstract

from arXiv · show

Poisson subsampling is the default sampler in differentially private optimization because its independence makes privacy amplification tractable. Practical systems, however, are moving toward structured participation: random allocation (balls-in-bins), per-epoch allocation, random check-ins, schemes widely believed to be at least as private as Poisson subsampling at the matched rate. We isolate the probabilistic mechanism behind this belief and delimit it exactly, for Gaussian mechanisms up to correlated-noise matrix mechanisms. (1) If the participation indicator vector is negatively associated (NA), then at every integer Rényi order $α\ge2$, exactly at all finite parameters, its remove-direction Rényi divergence is dominated by that of the marginal-matched independent scheme. For fixed gradient sequences, this extends to the mechanism level whenever the noise strategy's Gram matrix is sign-balanced, an $O(t^2)$-checkable condition. (2) The integer-order restriction is essential. For random allocation with $k=1$, we prove a linear law for the Rényi-difference criterion: at large $t$, dominance reverses for every $α<3/2$, including KL divergence, while the crossing order tends to $3/2$ independently of $σ$. (3) We also localize the known failure of rate-matched Poisson domination exactly: below $(1-q)^t$, the hockey-stick ordering reverses, so substituting the Poisson pair into composition machinery is unsound. An upper-tail argument yields a finite crossover $γ_\star$, connecting this threshold picture to the Rényi boundary at $3/2$. Together, these results give a substitution map for privacy accounting: when Poisson-based computations remain sound for structured participation, where they fail, and what sound alternatives cost in deployment.

1 Introduction

The paper asks when structured participation can safely reuse Poisson-based privacy accounting, identifying negative dependence as the mechanism and locating exact failure boundaries.

  • Motivation: Up to 4× of the reported guarantee can be missed when deployed samplers differ from Poisson assumptions.Fixed-size batches and shuffling can silently invalidate accounting.
  • Motivation: Random allocation is a practical replacement because it concentrates batch sizes, matches shuffling utility, and admits sound or exact accounting.It uses rate q = k/t and has privacy close to matched-rate Poisson subsampling in prior analyses.
  • Contributions: For every integer α≥2, negatively associated participation is dominated by the marginal-matched independent scheme in remove-direction Rényi divergence.The result holds at all finite parameters with no rate inflation.
  • Contributions: Under sign balance, the same dominance extends to fixed-gradient mechanism-level analysis with an O(t^2)-checkable condition.The result covers uniform k-subsets, per-epoch balls-in-bins, and random check-ins.
  • Contributions: Below (1−q)^t, allocation exceeds the rate-matched Poisson hockey-stick curve, making Poisson substitution unsound in that threshold window.An upper-tail ordering establishes a finite crossover γ★ beyond the reversal region.

2 Setup

The setup represents participation and Gaussian or matrix-mechanism outputs as a pair of distributions, then evaluates privacy through hockey-stick and Rényi divergences under zero-out adjacency.

  • Adjacency and privacy profiles: Under zero-out adjacency, remove and add privacy correspond to the two orderings of the same adjacent-input distribution pair.The differing example’s contribution is replaced by zero, and the remove direction measures visibility of presence.
  • Adjacency and privacy profiles: The full privacy profile is the hockey-stick curve γ↦Hγ(P∥Q), with δ(ε)=H_e^ε(P∥Q) for the remove direction.Composition requires domination across all γ, not only at a target ε.
  • Canonical mechanism: The canonical pair uses a participation distribution π over t steps, marginal probabilities q_c, a strategy matrix M, and positive-definite noise covariance Σ.Its Gram matrix is G=M^⊤Σ^-1M, and the likelihood ratio measures evidence for the differing user’s presence.
  • Canonical mechanism: Diagonal M=I and Σ=diag(σ_c^2) give per-step Gaussian noise, while general (M,Σ) covers correlated-noise matrix mechanisms.Later sections specialize to isotropic noise Σ=σ^2I.
  • Mechanism-level reduction: For fixed gradient sequences, the mechanism has the same likelihood-ratio law as the canonical pair with G replaced by the Hadamard product G◦W.Here W_c,c′ is the inner product of the differing example’s fixed gradient vectors.
  • Mechanism-level reduction: Full adaptivity remains an open gap for matrix mechanisms, so the paper’s mechanism-level results concern the fixed-sequence worst case sup_W∈E_t.Standard Gaussian mechanisms admit a reduction for arbitrary adaptive algorithms, whereas the corresponding matrix-mechanism extension is unresolved.
  • Divergences: Rényi order α controls tail weighting, ranging from KL as α↓1 toward worst-case behavior as α→∞.Rényi divergences are determined by the hockey-stick curve for α>1.
  • Negative association: Negative association requires nonpositive covariance between increasing functions of disjoint coordinate blocks.Uniform k-subset indicators are negatively associated, and the paper uses closure properties for unions and blockwise nondecreasing functions.

3 Integer-order dominance for negatively associated participation

Negative association lets structured participation inherit the marginal-matched independent scheme’s remove-direction Rényi guarantees at every finite integer order α≥2. At the mechanism level, this extends to sign-balanced Gram matrices, covering several practical schemes while excluding fixed-batch shuffling and leaving frustrated cases conditional.

  • General dominance principle: The comparison applies whenever the participation indicators are negatively associated, not only for uniform k-subsets.This supports per-epoch balls-in-bins and random check-ins in addition to random allocation.
  • General dominance principle: For every integer α≥2, NA participation has remove-direction Rényi divergence no larger than its marginal-matched independent counterpart, exactly at finite parameters and without rate inflation.The proof uses occupancy expectations and supermodular ordering; positive semidefiniteness is not required when the Gram matrix is symmetric and elementwise nonnegative.
  • Mechanism-level extension: At the mechanism level, sign balance is an O(t^2)-checkable condition under which the adversary’s worst case reduces to the absolute Gram matrix.Sign balance is weaker than elementwise nonnegativity and permits negative off-diagonal entries.
  • Applications: Random allocation satisfies the guarantee for all integers α≥2 and 1≤k≤t, exactly and with no rate inflation.For isotropic noise, the occupancy formulation requires no restriction α≤t.
  • Applications: Per-epoch allocation and random check-ins likewise inherit integer-order domination at their matched marginal rates.Their indicator vectors are negatively associated, including independent unions of NA blocks for per-epoch allocation.
  • Scope boundaries: Fixed-batch shuffling and capped allocation are outside the theorem because coupling across examples can destroy the required independence or negative-dependence structure.Fixing row sums helps through negative dependence, whereas fixing column sums induces positive dependence across examples.

4 The boundary in the Rényi order: 𝛼0 = 3/2

For k=1, the Rényi-difference criterion has a linear asymptotic law whose root is α0=3/2, making the integer-order guarantee fail below that boundary. The analysis also explains why the boundary is σ-independent and why low-order accounting must not substitute Poisson for allocation.

  • Why the boundary is 3/2: The sign of Ψ(α) weights the positive and negative lobes of Δ(γ), with the balance occurring at 3/2 rather than 2.Orders below 2 emphasize the small-threshold lobe, while larger orders emphasize the large-threshold lobe; Ψ(2)<0 because the negative lobe has greater raw mass.
  • Proof strategy: The proof combines exact integer moment identities with Taylor expansion and uniform remainder control over compact subsets of [1,4).The remainder term is O(t^-5/2)=o(t^-2), while the leading moment terms determine the linear law.
  • The linear law and reversal boundary: The criterion Ψ(α) has asymptotic sign −(2α−3), with root α0=3/2 independently of σ.The law holds for fixed real α∈[1,4) as t→∞ with σ fixed, uniformly on compact subsets.
  • The linear law and reversal boundary: For every fixed α∈(1,3/2), allocation eventually has larger Rényi divergence than Poisson, including KL divergence.For fixed α∈(3/2,4), the ordering reverses in favor of allocation.
  • Scope and practical implication: The restriction α<4 is a proof boundary, while the authors expect the linear law to extend to all real α>1.The stated theorem remains restricted because of the available kernel bound.
  • Scope and practical implication: Low-order Rényi accounting and KL analyses must not substitute rate-matched Poisson for allocation, whereas integer orders α≥2 remain safe in the remove direction.For allocation at k=1, the dominance margin at α=2 is exact but can be extremely small.

5 The boundary in the threshold: exact failure below (1 −𝑞)𝑡

Rate-matched Poisson does not dominate random allocation across the full privacy profile: below (1−q)^t, the hockey-stick ordering reverses exactly. An upper-tail argument establishes a finite crossover beyond which allocation becomes more private, while composition based on the unmatched pair is unsound.

  • Exact failure window: For every γ∈(0,(1−q)^t], Hγ(PPois∥Q)=1−γ exactly, while Hγ(Palloc∥Q)>1−γ.Thus allocation has strictly larger remove-direction hockey-stick divergence throughout this exact low-threshold window.
  • Practical scope: The reversal occurs at large δ: at σ=1, δ at γ=1 is approximately 0.064, 0.032, and 0.016 for t=64,256,1024.Typical DP-SGD targets δ≤10^-5 are therefore unaffected by this large-δ reversal region.
  • Accounting consequence: The rate-matched Poisson pair is not a dominating pair for allocation, so feeding it into composition machinery is unsound.The paper notes that a final printout can still appear correct at δ=10^-5, but the underlying substitution is invalid.
  • Exact failure window: The same threshold creates an add-direction failure: rate-matched Poisson reports δ=0 beyond t log(1/(1−q))≈k, while allocation remains positive.At k=1 and t=64, the threshold is 1.0079, with allocation’s truth about 5×10^-7 at σ=1.
  • Scope of the reversal: The exact failure window is compatible with small-σ reversal at every fixed γ≥1, while different iterated limits describe a distinct low-noise, fixed-δ regime.The paper distinguishes fixing γ and sending σ→0 from fixing the privacy-loss scale ε=Θ(1/σ^2).

6 The crossover: existence, finiteness, and cost

The paper proves that allocation’s privacy profile is worse than matched Poisson below a finite threshold but better in the sufficiently large-threshold tail. The crossover’s behavior depends strongly on the sampling regime, with asymptotic revival for fixed k and apparent divergence in the dense regime.

  • Existence and finiteness: Small-threshold reversal is driven by upper-tail ordering, so allocation cannot be dominated by matched Poisson across all γ.Allocation’s likelihood-ratio tail eventually falls below Poisson’s, preventing the reversal from extending indefinitely.
  • Existence and finiteness: At t = 2 and k = 1, allocation leaks more at γ = 1, but the ordering flips beyond γ★.Table 3 obtains γ★ by bisection and ε★ = log γ★ by deterministic quadrature.
  • Regime dependence: In the amplification regime with fixed k, ε★ → 0 at rate Θ(1/t), while its height remains strongly σ-dependent.The crossover therefore approaches γ★ = 1 as training length increases.
  • Regime dependence: In the dense regime k = t/2, Monte Carlo brackets indicate a diverging crossover, with the reversal window appearing to swallow every fixed threshold.Under calibrated noise, the γ = 1 gap loses statistical significance by t = 32.
  • Limits and accounting cost: The candidate second-order laws are not fully proved: heuristic covariance and boundary steps lack uniform Edgeworth error control.The validity threshold λ3 ≪ 1 can require t ≳ 1.7 × 10^5 at σ = 0.5, and dense-regime readings rely on Monte Carlo evidence.
  • Limits and accounting cost: In deployment, fixed-k configurations operate beyond the small-threshold unsafe region, whereas dense configurations have no threshold safely supported for rate-matched substitution.Sound alternatives are direct profile computation or an inflated-rate Poisson bound.

7 High-accuracy accounting for allocation, and its integration into deployed pipelines

The paper develops certificate-checked allocation accounting and maps it onto RDP, PLD, and f-DP pipelines. Matched Poisson reuse is sound for the remove direction under specified conditions, while full-profile pipelines require direct computation or rate inflation.

  • Accounting implementation: For k = 1, both privacy profiles reduce to one-dimensional convolutions computable by FFT to near machine precision.The implementation uses tilted convolution to avoid FFT dynamic-range loss.
  • Accounting implementation: The accountant uses mass and shape certificates, but its ±8% deepest-point band is calibrated from shape residuals rather than rigorously certified end to end.Its results agree with the deterministic quadrature of Table 3.
  • RDP pipelines: Matched Poisson RDP reuse is sound for the remove direction for any NA sampler at integer orders α ≥ 2, without rate adjustment.For k = 1, this reuse is strictly conservative in the remove direction.
  • RDP pipelines: Mechanism-level reuse with correlated noise additionally requires a sign-balanced Gram matrix, checkable by an O(t^2) sign-pattern two-colouring.The recommendation applies to fixed gradient sequences; fully adaptive gradients remain outside the guarantee.
  • PLD and f-DP pipelines: PLD and f-DP pipelines must not consume the rate-matched Poisson pair because it does not dominate allocation’s full privacy profile.Sound options are an inflated-rate Poisson pair or direct allocation-profile computation.
  • PLD and f-DP pipelines: The inflated-rate substitute costs 2× to 168× in δ relative to direct computation, while direct computation removes that cost at the price of one convolution.The inflated-rate route preserves the existing Poisson code path.
  • Deployment example: At t = 256, σ = 1, k = 1, the reported ε values are 0.93 for RDP reuse, 0.56 for inflated-rate PLD, and 0.33 for direct allocation PLD.At t = 1024, the corresponding values are 0.68, 0.23, and 0.14.

8 Related work

The paper situates its contribution among privacy amplification, structured participation, deployment pitfalls, correlated-noise mechanisms, shuffling, and negative-dependence theory. Its distinctive contribution is identifying when negative association yields dominance and where matched Poisson substitution fails.

  • Amplification and deployment: Prior amplification analyses largely rely on Poisson independence, while deployed samplers increasingly use structured participation.The paper addresses the resulting gap between accounting assumptions and implementation.
  • Structured participation: Random allocation offers concentrated batch sizes, utility comparable to shuffling, and exact or sound accounting, but its matched-rate Poisson comparison is not uniformly valid.Earlier work established close privacy bounds and incomparability results.
  • Matrix mechanisms: For matrix mechanisms, the paper identifies sign balance as a decidable sufficient condition under which negative dependence beats independent participation.This extends the comparison beyond diagonal-noise settings.
  • Shuffling and negative dependence: Random check-ins receive their guarantee directly from negative association, without requiring a shuffling argument.This connects the paper’s mechanism to classical structured-participation analyses.
  • Shuffling and negative dependence: Negative association is the probabilistic framework used to compare participation vectors through covariance inequalities and product inequalities.Uniform k-subset indicators are a canonical NA example.

9 Discussion and open problems

The paper identifies unresolved boundaries around its guarantees, including Gaussian and integer-order scope, conjectural mechanism-level extensions, and open crossover laws.

  • Scope and assumptions: Theorem 3.2 and its corollaries are Gaussian-specific and apply only at integer Rényi orders, while mechanism-level extension beyond sign-balanced G remains conjectural.The stated theorem still holds for general negatively associated schemes at all finite parameters.
  • Open analytical problems: The linear law and candidate laws for crossover locations are developed for k=1, with two heuristic steps still requiring theorem-level justification.The open agenda calls for uniform Edgeworth error control and a sharper ε★ constant.
  • Open analytical problems: Uniqueness of the crossover sign change remains conjectural, despite certificate-checked numerics charting γ★ across three regimes.Theorem 6.2 establishes a finite crossover γ★ within an explicit interval; only uniqueness remains conjectural.
  • Open analytical problems: The dense-regime statements rely on Monte Carlo evidence, and proving γ★→∞ there remains an open problem.The intermediate small-σ window is also unresolved, including the balance between single-big-jump and collective-fluctuation behavior.
  • Matrix mechanisms: For matrix mechanisms, the conjectured extension covers every PSD G, but the unresolved complement grows with α and cannot be settled by the |G|-relaxation alone.A supermodularity argument that survives the inner supremum is identified as the missing tool.

10 Conclusion

Negative association supports Poisson-style privacy accounting for structured participation at integer Rényi orders, with sign balance extending the result to fixed-gradient mechanisms; the boundary is explicit for k=1.

  • 10 Conclusion: Negative association yields remove-direction dominance by the marginal-matched independent scheme at every integer Rényi order and all finite parameters.Under sign balance, the same guarantee holds at the mechanism level for fixed gradients.
  • 10 Conclusion: For k=1 allocation, the reused values asymptotically cover the add direction as well.
  • 10 Conclusion: The analysis also locates where this privacy-accounting principle stops for random allocation.The supplied conclusion passage introduces this boundary without detailing its threshold.

Ethical Considerations

The work is mathematical and numerical, with no human subjects, personal or user data, or interaction with deployed systems; its intended impact is defensive.

  • Ethical Considerations: The study analyzes published participation schemes for DP-SGD through proofs and direct computation of associated divergence curves.
  • Ethical Considerations: It involves no human subjects, personal or user data, or measurement of or interaction with deployed systems, so no IRB or comparable review applied.
  • Ethical Considerations: The intended impact is defensive: preventing unsound privacy accounting for samplers being adopted in practice.

A Negative-association toolkit and proofs for Sections 2 and 3

The appendix develops the negative-association proof toolkit, reduces Gaussian privacy calculations to Gram-matrix forms, and analyzes frustrated-triangle configurations with certified comparisons and switch thresholds.

  • Gaussian reduction: The Gaussian likelihood-ratio distribution depends on the mechanism through the Gram matrix G◦W, and every likelihood-ratio functional therefore agrees with the canonical pair.
  • Negative-association toolkit: Uniform random k-subset indicators are negatively associated, and independent unions and disjoint nondecreasing transformations preserve negative association.
  • Negative-association toolkit: Negative association gives a product inequality for nonnegative nondecreasing functions, with nonnegativity essential to the induction.
  • Frustrated triangle: At α=2 and k=1, the frustrated-triangle comparison has a unique positive switch threshold a★=0.420120… within the positive-definite range.
  • Frustrated triangle: For a<a★, the balanced configuration W° globally maximizes the objective and yields mechanism-level dominance; beyond a★, a sign-vector configuration takes over and the shortcut fails.
  • Certified matrix analysis: Computer-assisted certification reduces the rank-≤2 search to two candidate families, while switch thresholds decrease with α and depend non-monotonically on k.The certificate covers the tabulated cells and uses rigorous interval branch-and-bound on the torus.

B Proofs for Sections 4 and 5

The proofs establish exact hockey-stick identities and moment expansions for allocation and Poisson likelihood ratios, then control Taylor remainders and tail regions to derive the stated asymptotic comparisons. They also identify an exact hockey-stick threshold and qualify the crossover law by its asymptotic validity window and heuristic steps.

  • Exact identities: The add/remove conversion follows from an exact density identity, yielding H_γ(Q∥P) = γH_1/γ(P∥Q) + 1 − γ.The compensator is necessary because the corresponding pointwise integral diverges logarithmically at γ = 0, while its expectation removes the divergence.
  • Moment expansions: Allocation moments are organized by coinciding pairs and triples among balls thrown into t bins, producing the leading t^-2 and t^-3 terms.Two coinciding pairs contribute at order t^-2, while three pairs contribute at order t^-2 only when three balls form a triangle in one bin.
  • Rényi comparison: For α≥2, cancellation of the linear-in-v terms leaves a nonnegative coefficient, so the corresponding Rényi comparison follows by logarithm monotonicity.The cancellation uses A(α−2) = 3B; the v^2 and v^3 terms assemble into the stated coefficients, with positivity immediate for α≥2.
  • Remainder control: The proof controls the remainder by splitting γ into three regions and combining kernel bounds, concentration inequalities, and high-order moment estimates to obtain |J_α| ≤ C(σ,A)t^-5/2.Rosenthal and Burkholder–Rosenthal bounds control allocation and Poisson tails, while the compact central window uses Berry–Esseen estimates.
  • Hockey-stick threshold: The hockey-stick threshold is exact for Poisson: δ_add(ε) = 0 for ε ≥ t log(1/(1−q)), while δ_add(ε) > 0 below it; allocation remains positive for every ε.The Poisson upper bound follows from dQ/dPPois ≤ (1−q)^-t, whereas Gaussian-mixture full support gives strict positivity below the threshold.
  • Asymptotic boundary: The small-z crossover law is only a candidate asymptotic result: its expansion requires λ3 ≪ 1 and its derivation is heuristic at two identified steps.The stated approximation is ε★ ≈ [κ3/(2v) + v/12]/t within the validity window.
Loading 2609.01944v1…