Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

Vitaly Feldman; Moshe Shenfeld

cs.LGOct 23, 2026

Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

Authors: Vitaly Feldman, Moshe Shenfeld

Organizations: Apple · The Hebrew University of Jerusalem

Abstract

The privacy analysis of differentially private stochastic gradient descent (DP-SGD) relies on bounds for the composition of subsampled mechanisms. The privacy of such a composition is bounded by that of a pair of product distributions, whose privacy loss is a sum of independent terms and has been analyzed via a variety of notions and concentration results. Yet, existing closed-form bounds either lose a logarithmic factor or require restrictive conditions on the noise scale and delicate analysis of subsampling. Further, while it is well known that sums of independent random variables are approximately Gaussian, existing CLT-based techniques give an approximation with a large error in $δ$ . We show that the privacy loss of this pair is approximately Gaussian as long as each step has a small privacy loss except with small probability. Specifically, its privacy loss distribution is close to a Gaussian with the same mean and variance, after truncating the rare large privacy losses. The closeness in both directions is up to a shift of $\varepsilon$ that grows only as $\ln(1/β)$ for an additive error $β$ in $δ$ and is a lower-order term in typical applications. In particular, the composition satisfies Gaussian differential privacy up to a lower-order shift of $\varepsilon$ and the additive error $β$ . We also give a simple way to analyze the resulting variance-based bounds for subsampled mechanisms which relies on the $χ^2$ divergence of a single step. For the Gaussian mechanism at sampling rate $1/t$ and $t>\ln^{3}(1/δ)$ , this gives the predicted rate for $σ\gtrsim\max\{1,\sqrt{\ln(1/δ)}/\ln(t)\}$ , whereas the standard Rényi-divergence analyses need $σ\gtrsim\sqrt{t\ln(1/δ)}/\ln(t)$ . We extend these results to random allocation (balls-and-bins sampling), and show that it explains the high accuracy of the connect-the-dots method.

Figures & tables

Figure 1: The error of the upper bound on

\varepsilon

\delta=10^{-6}

for the Gaussian mechanism with

\sigma=10

, whose privacy loss is distributed as

\mathcal{N}(1/(2\sigma^{2}),1/\sigma^{2})

, discretized on the grid

h\mathbb{Z}

by privacy buckets and by CtD, as a function of the grid spacing

h

, for a single step (left) and for the composition of

100

steps (right). The upper bounds are the pessimistic estimates of dp_accounting [ Goo26 ] with its default truncation of the tails, and the error is computed relative to the exact value. For small

h

, the error of privacy buckets is close to

th/2

, whereas that of CtD is of order

h^{2}

Figure 2: The ratio of the error of CtD to that of privacy buckets, in the setting of Figure 1 , as a function of the grid spacing

h

, for the composition of

t

steps.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Method	Scheme	Sufficient noise scale	Leading term
Quadratic Rényi bounds [ ACG+16 , MTZ19 ]	Poisson	$\sigma\gtrsim\sqrt{t\ln(1/\delta)}/\ln(t/\ln(1/\delta))$	$\sqrt{\ln(1/\delta)}/(\sigma\sqrt{t})$
$(\varepsilon_{0},\delta_{0})$ amplification with advanced composition	Poisson	$\sigma\gtrsim\sqrt{\ln(1/\delta)}$	$\ln(1/\delta)/(\sigma\sqrt{t})$
Reduction to Poisson subsampling [ FS25 ]	allocation	$\sigma\gtrsim\sqrt{\ln(t/\delta)}$ and the condition of the Poisson analysis	$\sqrt{\ln(t/\delta)}/(\sigma\sqrt{t})$
This work ( Claims D.4 and 5.4 )	both	$\sigma\ln\left(1+\frac{\sqrt{t}}{\sigma\sqrt{C\ln(1/\delta)}}\right)\gtrsim\sqrt{\ln(t/\delta)}$	$\sqrt{\ln(1/\delta)}/(\sigma\sqrt{t})$

Appendix

Table 1: Noise scales at which each analysis gives its leading privacy term for the Gaussian mechanism with Poisson subsampling at rate

1/t

or with

1

-out-of-

t

random allocation (lower-order terms omitted). For polynomially small

\delta

, the condition of this work holds for every fixed

\sigma\geq 1

once

t

is sufficiently large.

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 278 papers

May 7, 2026

Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds

We derive a tight analysis of the trade-off function for Differentially Private Stochastic Gradient Descent (DP-SGD) with subsampling based on random shuffling within the

f

-DP framework. Our analysis covers the regime

σ\geq \sqrt{3/\ln M}

, where

σ

is the noise multiplier and

M

is the number of rounds within a single epoch. Unlike

f

-DP analyses for Poisson subsampling, which yield non-closed implicit formulas that can be machine computed but are non-transparent, random shuffling admits a tight analysis yielding transparent and interpretable closed-form bounds. Our concrete bounds, derived via the Berry-Esseen theorem, are tight up to constant factors within the proof framework. We demonstrate worked parameter settings for a single epoch (

E=1

) with a corresponding trade-off function

\geq 1-a-δ

, that is, only

δ

below the ideal random guessing diagonal

1-a

: For

δ= 1/100

and

σ= 1

, roughly

M \approx 1.14\times 10^6

rounds and

N \approx 1.14\times 10^7

training samples suffice to achieve meaningful differential privacy. This is in contrast to recent negative results for the regime

σ\leq 1/\sqrt{2 \ln M}

. Our concrete bounds can be composed over multiple epochs leading to

δ

having a linear in

E

dependency, which restricts

E=O(\sqrt{M})

. To go beyond Berry--Esseen, we introduce a new proof technique based on a generalization of the law of large numbers that yields an asymptotic random guessing diagonal-limit result: if

E=c_M^2M

with

c_M\to 0

, then the

E

-fold composed trade-off function satisfies

f^{\otimes E}(a)\to 1-a

uniformly in

a\in[0,1]

with

δ

having only an

O(\sqrt{E})

dependency. We compare this asymptotic regime with the corresponding Poisson subsampling asymptotic, and highlight the characterization of explicit convergence rates as an open question.

Marten van Dijk, Murat Bilgehan Ertan

CWI Amsterdam · ∗Affiliated with Vrije Universiteit Amsterdam.

Differentially Private Stochastic Gradient Descent Differential Privacy Gaussian Differential Privacy

Ask PDF

Feb 19, 2026

Efficient privacy loss accounting for subsampling and random allocation

We consider the privacy amplification properties of a sampling scheme in which a user's data isused in

k

steps chosen randomly and uniformly from a sequence (or set) of

t

steps. This sampling scheme has been recently applied in the context of differentially private optimization (Chua et al., 2024a; Choquette-Choo et al., 2025) and communication-efficient high-dimensional private aggregation (Asi et al., 2026), where it was shown to have utility advantages over the standard Poisson sampling. Theoretical analyses of this sampling scheme (Feldman & Shenfeld, 2025; Dong et al., 2025) lead to bounds that are close to those of Poisson sampling, yet still have two significant shortcomings. First, in many practical settings, the resulting privacy parameters are not tight due to the approximation steps in the analysis. Second, the computed parameters are either the hockey stick or Renyi divergence, both of which introduce overheads when used in privacy loss accounting. In this work, we demonstrate that the privacy loss distribution (PLD) of random allocation applied to any differentially private algorithm can be computed efficiently. When applied to the Gaussian mechanism, our results demonstrate that the privacy-utility trade-off for random allocation is at least as good as that of Poisson subsampling. In particular, random allocation is better suited for training via DP-SGD. To support these computations, our work develops new tools for general privacy loss accounting based on a notion of PLD realization. This notion allows us to extend accurate privacy loss accounting to subsampling which previously required manual noise-mechanism-specific analysis.

Vitaly Feldman, Moshe Shenfeld

Apple · The Hebrew University of Jerusalem · *Work partially done while author was an intern at Apple.

Differential Privacy Privacy-Utility Tradeoff

Ask PDF

May 27, 2026

Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy

We design a class of additive noise mechanisms that satisfy

(\varepsilon, δ)

-differential privacy (DP) for scalar, real-valued query functions with known sensitivities, with a particular focus on moderate and low-privacy regimes. These mechanisms, which we call mixture mechanisms, are constructed by mixing multiple Gaussian distributions that share the same variance but differ in their means and mixture weights. The resulting distributions can be interpreted as convex combinations of a zero-mean Gaussian (as used in the analytic Gaussian mechanism) and additional Gaussians whose means depend on the sensitivity of the query function. We derive tight conditions on the variances required for

(\varepsilon, δ)

-DP and provide efficient algorithms to compute them. Compared to the analytic Gaussian mechanism, our mechanisms yield substantially lower expected noise amplitudes (

l_1

-loss) and variances (

l_2

-loss for zero-mean distributions). In the low-privacy regime that motivates our design, our mechanisms approach optimality, mitigating nearly all of the optimality gap of the analytic Gaussian mechanism.

Huikang Liu, Aras Selvi, Wolfram Wiesemann

1Shanghai Jiao Tong University · 2UCL School of Management · 3Imperial Business School

Differential Privacy

Ask PDF

Abstract

Differential Privacy

Explore similar work

Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds

Efficient privacy loss accounting for subsampling and random allocation

Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy