arXiv CSopen access

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

arXiv:2605.06259v1 [cs.LG] 7 May 2026

Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds Marten van Dijk∗ CWI Amsterdam Amsterdam, Netherlands [email protected]

Murat Bilgehan Ertan∗ CWI Amsterdam Amsterdam, Netherlands [email protected]

Abstract 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 p the f -DP framework. Our analysis covers the regime σ ≥ 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 ≥ 1 − a − δ, that is, only δ below the ideal random guessing diagonal 1 − a: For δ = 1/100 and σ = 1, roughly M ≈ 1.14 × 106 rounds and N ≈ 1.14 × 107 training samples suffice to achieve meaningful differential √ privacy. This is in contrast to recent negative results for the regime σ ≤ 1/ 2 ln M . Our concrete bounds can be composed over multiple √ epochs leading to δ having a linear in E dependency, which restricts E = O( 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 = c2M M with cM → 0, then the E-fold composed trade-off function satisfies f ⊗E (a) → 1 − a uniformly in a ∈ [0, 1] with √ δ having only an O( 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.

1

Introduction

Differential privacy [11, 10] is the de facto standard for privacy in machine learning, and DP-SGD [1] is the dominant mechanism for training deep models under DP constraints. Tight privacy accounting for DP-SGD is essential: a loose analysis translates directly into either an over-conservative model or, worse, a guarantee that is weaker than advertised. The f -DP framework [8] characterizes privacy through the trade-off function between an adversary’s false-positive and false-negative rates and provides, in a precise sense, the tightest available description of a mechanism’s privacy guarantee, subsuming both (ε, δ)-DP and Rényi DP [19]. Nevertheless, f -DP analyses of DP-SGD have so far focused almost exclusively on Poisson subsampling, in which each datapoint is independently included in each minibatch with a fixed probability [1, 8, 19, 20, 2, 24, 4]. Poisson subsampling is analytically convenient but practically uncommon: ∗ Affiliated with Vrije Universiteit Amsterdam.

Preprint.

deployed implementations of DP-SGD, and stochastic optimization more broadly, instead use random shuffling, in which the dataset is randomly permuted once per epoch and partitioned into minibatches of equal size [21]. This mismatch between the algorithm that is analyzed and the algorithm that is run has left the privacy guarantee of the deployed mechanism imprecisely characterized. For the shuffled mechanism specifically, Chua et al. [6, 7] upper-bound the trade-off function of shuffled DP-SGD (equivalently, lower-bound its privacy-loss curve δ(ε)) ,via explicit adversarial events, in the single-epoch [6] and multi-epoch [7] settings, with numerical evaluation showing substantial privacy loss at small σ. The impossibility result of Ertan √ and van Dijk [12] is in the same direction, additionally giving a closed-form threshold σ < 1/ 2 ln M below which the trade-off function is provably bounded away from 1−a. Further numerical tools appear in [3]. These results bound privacy in one direction only, and the bound expressions are not closed form in (σ, M, E); in particular, they do not yield matching closed-form characterizations of the trade-off function that one can inspect, differentiate, or invert to read off parameter requirements. We give a tight closed-form f -DP analysis of DP-SGD with random shuffling. For a single epoch p with M = N/m rounds and noise multiplier σ ≥ 3/ ln M , the trade-off function f satisfies ! s −3/σ 2
2 1 1+4·e e1/σ2 − 1 √ f (a) ≥ 1 − a − 2B · e1/σ · + · − O 1/M , 2 2 −1/σ M −1 (1 − e ) 2π uniformly in a ∈ [0, 1], where B is the Berry-Esseen constant. For suitable parameters this is close to the random guessing diagonal 1 − a which provides perfect privacy (no leakage at all). The O(1/M ) term in the lower bound is exactly expressed in concrete parameters σ and M in Theorem 4.1. This is a concrete non-asymptotic formula that can be evaluated directly to read off DP parameters; within the proof framework, which uses the Berry-Esseen theorem at its core, it is tight up to constants, since improving the dominant term requires improving the underlying Berry–Esseen estimate itself. √ Our regime is complementary to a recent impossibility result [12], which shows that for σ < 1/ 2 ln M the trade-off function lies far from the ideal random guessing diagonal 1 − a. Together, the two results map out the privacy landscape of shuffled DP-SGD: noise below the lower threshold cannot give meaningful privacy, while noise above the upper threshold is precisely characterized by the closed-form expressions we derive. Going beyond Berry–Esseen, a generalization of the central limit theorem based on an Edgeworth expansion for two terms (Theorem 5.1) establishes that, for fixed σ (independent of M ), as M → ∞ with the number of epochs scaling as E = c2M · M with cM → 0, the E-fold composed trade-off function satisfies f ⊗E (a) → 1 − a uniformly in a ∈ [0, 1] (Theorem 5.2).√The Berry–Esseenbased concrete bound only supports a lower bound f ⊗E (a) ≥ 1 − a − O(E/ M ) which restricts √ E = o( M ). So the improved asymptotic result is qualitatively stronger; deriving an explicit convergence rate for it remains an open problem. The closed-form bounds enable concrete parameter recommendations. Worked settings (Section 6) show that, with a single epoch, σ = 1, and δ = 10−2 , a dataset of size N ≈ 1.14 × 107 partitioned into M ≈ 1.14 × 106 minibatches achieves a meaningful DP guarantee. This is directly relevant to federated learning [18], where datasets often comprise the records of millions of users contributed across a small number of training rounds. Contributions are as follows: lower bound f (a) ≥ 1 − a − δ for single-epoch shuffled DP-SGD with 1. Closed-form p σ ≥ 3/ ln M , δ explicit in (σ, M ) of order O(M −1/2 ) for fixed σ, plus composition f ⊗E (a) ≥ (1 − δ)E − a (Theorem 4.1). As well as, worked f -DP parameter settings at federated-learning scale (Section 6). 2. An Edgeworth-type CLT refinement, Fn (x) = Φ(pn (x)) + o(1/n) uniformly on |x| ≤ o(n1/16 ), sharpening Berry–Esseen on the range used by the privacy analysis (Theorem 5.1). 3. For fixed σ, an asymptotic Gaussian-DP characterization yielding f ⊗E ≥ G √ 1/σ2 (and c

e

−1

→ 1 − a for c = 0) over E = c2M M epochs √ with cM → c as M → ∞, improving the separation dependence from O(µE) to O(µ E) (Theorem 5.2, Corollary 5.3). All proofs are deferred to the appendix, organized as a common adversarial reduction followed by two parallel tracks, non-asymptotic Berry–Esseen (Theorem 4.1) and asymptotic Edgeworth (Theorems 5.1 and 5.2). A proposition-level map for navigation is given in Appendix A. 2

2

Related Work

Privacy accounting for DP-SGD. Tightly accounting for the privacy of DP-SGD has driven a substantial body of work. The original moments accountant of [1] has been refined through concentrated and Rényi DP [5, 19, 20], tight (ε, δ)-composition [16], and divergence-based subsamplingamplification analyses [2, 24]; in parallel, the privacy-loss-distribution and privacy-loss-randomvariable frameworks [17, 15, 9] compute privacy guarantees numerically to within a small error. The f -DP framework [8, 4] characterizes DP via trade-off functions and provides a central limit theorem for composition. Almost all of this work targets Poisson subsampling. For the shuffled mechanism specifically, Chua et al. [6, 7] construct explicit adversarial events on the Adaptive Batch Linear Queries (ABLQ) abstraction underlying DP-SGD to upper-bound the trade-off function (equivalently, lower-bound the privacy loss δ(ε)), in the single-epoch [6] and multi-epoch [7] settings; their bound expressions are not closed form in (σ, M, E) and are evaluated numerically. The impossibility result of [12] is in the same direction: it upper-bounds the trade-off function √ via a different, analytically tractable suboptimal test and yields a closed-form threshold σ < 1/ 2 ln M below which the tradeoff function is provably bounded away from 1 − a. We provide the p matching closed-form lower bound on the trade-off function in the complementary regime σ ≥ 3/ ln M (Theorem 4.1).

3

Background: Differential Privacy (DP), DP-SGD and f -DP

Differential privacy (DP) [10] requires that the output of a randomized mechanism M is statistically similar on any two neighboring datasets d and d′ that differ in the contribution of a single individual. In the classical (ε, δ)-DP formulation, the mechanism satisfies P[M(d) ∈ E] ≤ eε P[M(d′ ) ∈ E] + δ for all measurable events E, where smaller ε and δ correspond to stronger privacy. We consider differentially private stochastic gradient descent (DP-SGD) [1] where the training dataset of N samples is randomly shuffled and then partitioned into M = N/m mini-batches of equal size m. In each round j ∈ {1, . . . , M }, the algorithm computes the gradient on the j-th mini-batch, clips each individual gradient to norm at most C, averages the clipped gradients, and adds Gaussian noise drawn from N (0, (Cσ/m)2 ) to the result. A single pass through all M rounds constitutes one epoch. This stands in contrast to Poisson subsampling, where each data point is independently included in each round with probability q = m/N . While Poisson subsampling is the more commonly analyzed variant in the DP literature due to analytical convenience, random shuffling (or close approximations of it) is the standard practice in machine learning frameworks. The f -DP framework [8] provides a more complete characterization of privacy by viewing the distinguishing task as a hypothesis test. Given neighboring datasets d and d′ , let H0 denote the null hypothesis that the underlying dataset is d and H1 the alternative that it is d′ . A rejection rule ϕ outputs 1 if H0 is rejected.2 The Type I error (false positive rate) and Type II error (false negative rate) are defined as α(ϕ) = E[ϕ | d] ∈ [0, 1]

β(ϕ) = 1 − E[ϕ | d′ ] ∈ [0, 1].

and

The trade-off function captures the fundamental trade-off between these two error types: f (a) = inf {β(ϕ) : α(ϕ) ≤ a}. ϕ

A mechanism provides strong privacy when its trade-off function f (a) is close to 1 − a, the “random guessing” diagonal corresponding to zero leakage: in this case, no rejection rule can simultaneously achieve low false positive and false negative rates. Conversely, if f (a) is far from 1 − a, the adversary can distinguish the two datasets with high confidence, indicating significant privacy leakage. The trade-off function provides a complete geometric representation of the privacy guarantee and subsumes both the (ε, δ)-DP and Rényi DP formulations as special cases [8]. The Gaussian trade-off function Gµ (a) = Φ(Φ−1 (1 − a) − µ), parameterized by µ ≥ 0, arises naturally from distinguishing two Gaussians differing by a shift of µ; smaller µ corresponds to stronger privacy (G0 (a) = 1 − a is the ideal). For E-fold composition (corresponding to E epochs), we write f ⊗E for the composed trade-off function. 2 The rejection rule can be probabilistic and output a probability ϕ after which a coin flip with bias ϕ decides whether the

null hypothesis will be rejected.

3

Adversarial model. We use the same adversarial model as in the prior work [12], which we briefly summarize here for intuition; the full technical derivation is given in Appendix B. In DP-SGD with random shuffling over a single epoch, each data record appears in exactly one of the M rounds. Consider two neighboring datasets d and d′ that differ in a single record. The privacy question is: can an adversary, observing the mechanism’s outputs, determine which dataset was used? The standard worst-case adversary in the DP framework is granted, in addition to the noisy batch updates produced by DP-SGD, auxiliary information that allows it to isolate the noisy contribution of the potentially differing record in each round (see [12], Proposition 4.3 for the formal derivation). Informally, this means the adversary can “subtract out” the known contributions of all other records, leaving only the noise and (possibly) the signal from the differentiating record. This is the strongest possible adversary: any privacy guarantee that holds against this adversary automatically holds against any weaker, more realistic adversary. After projecting onto the gradient direction and normalizing by the noise scale, the adversary’s observation in each round reduces to a scalar. Concretely, the adversary observes M samples
(xj )M j=1 ∼ N (e1 /σ, 1), . . . , N (eM /σ, 1) , where under H0 (dataset d) all ej = 0, and under H1 (dataset d′ ) exactly one ej = 1 for a uniformly random j ∈ {1, . . . , M } with the rest equal to zero. That is, under H0 every round produces pure noise N (0, 1), while under H1 the single round containing the genuine record produces a shifted observation N (1/σ, 1). By the Neyman–Pearson lemma, the optimal test thresholds the likelihood ratio, which reduces PM Xj /σ−1/(2σ2 ) 1 to thresholding the sample average of lognormal variables M . The trade-off j=1 e function f (a) = β(α−1 (a)) then characterizes the fundamental privacy guarantee of the mechanism. The full likelihood computation and the definitions of α(h) and β(h) as functions of the threshold h are given in Appendix B.

4

Main Theorem

Our first main result provides concrete, non-asymptotic bounds on the trade-off function of DP-SGD with random shuffling for a single epoch. Theorem 4.1. Let f be the trade-off function of DP-SGD for a single epoch with M rounds with subsampling based on random shuffling and noise multiplier σ. Let s e1/σ2 − 1 µ= , M −1 B ∈ [0.4097, 0.4748] be the universal constant in the Berry-Esseen theorem for independent and identically distributed random variables, and 2

δ

1 + 4 · e−3/σ 1 ≥ 2B · e · ·µ+ √ µ (1 − e−1/σ2 )2 2π ( ) 2 1 1 e1/σ √ + √ (1 + + ) µ2 1 − e−1/σ2 4 2π 2 2eπ 1/σ 2

1 1 µ3 + √ µ4 + √ 4 2eπ 32 2eπ 4.52 √ √ + M −25/24 2.88 ln M − 2.41/ ln M with

2

2

δ + B · e1/σ ·

1 + 4 · e−3/σ 1/σ 2 − 1)/2). 2 2 · µ ≤ 1/2 − Φ(−(e −1/σ (1 − e )

Then, for a ∈ [0, 1], f (a) ≥ 1 − a − δ and f ⊗E (a) ≥ (1 − δ)E − a. 4

(1)

4.1

Interpretation

p The condition of the theorem implies σ ≥ 3/ ln M : The left-hand side of (1) is at least 3B · √ √ 2 2 e3/(2σ ) / M − 1 ≥ e3/(2σ ) / M , and the right-hand side is at most 1/2, so σ cannot be too small. This naturally restricts our analysis to the regime complementary to the impossibility result of [12]. The Berry-Esseen term dominates. For large enough M , the first term involving the Berry-Esseen constant B dominates the lower bound on δ (for small σ), and the theorem can be approximately restated by replacing the lower bound on δ by ! −3/σ 2 2 1 + 4 · e 1 +√ · µ. (2) δ ≥ 2B · e1/σ · (1 − e−1/σ2 )2 2π This observation is important: within the Berry-Esseen proof framework, the B-term is the bottleneck. Any improvement to the concrete bounds requires improving the dominating Berry-Esseen approximation itself. This motivates the asymptotic approach of Section 5, which improves upon the Berry-Esseen approach. Lower bound on M . The approximate bound (2) yields a first lower bound on the number of rounds: " #!2 √ 2 1 1 + 4 · e−3/σ e1/σ2 − 1 3/(2σ 2 ) √ M ≥1+ 2B · e · . (3) + δ (1 − e−1/σ2 )3/2 2π A second lower bound arises from condition (1): #!2 " √ 2 e1/σ2 − 1 1 1 + 4 · e−3/σ 3/(2σ 2 ) √ M ≥ 1+ . (4) 3B · e · + 1/2 − Φ(−(e1/σ2 − 1)/2) (1 − e−1/σ2 )3/2 2π 2

For δ ≤ 23 (1/2 − Φ(−(e1/σ − 1)/2)), the first bound (3) implies the second. Since we require δ to be small for a meaningful DP guarantee, this condition is satisfied for practical parameter ranges, for example, δ = 0.01 allows σ ≤ 3.71 and, vice versa, σ = 1 allows δ ≤ 0.20. Gaussian noise and dataset size. Each round of DP-SGD adds Gaussian noise N (0, (Cσ/m)2 ) = N (0, (CσM/N )2 ) to the averaged clipped gradients. For DP-SGD to remain robust against this noise, CσM/N must be small, i.e., N must be sufficiently large relative to M . This creates a tension: M must be large enough for (3) to be satisfied, but M/N must remain small for utility. A caveat of using a large N relative to M is that the mini-batch size m = N/M is large, slowing convergence in a distributed DP-SGD setting with heterogeneously distributed training data and thus requiring more epochs, which in turn weakens the DP guarantee. From the concrete theorem to asymptotics. Theorem 4.1 can also be used to derive an asymptotic result: If δ = rδ · M −R and E = rE · M R , then f ⊗E (a) ≥ (1 − δ)E − a → e−rδ rE − a as M → ∞. √ 2 However, this leads to a weak asymptotic bound since δ ≈ 3B · M −(1−3/s )/2√for σ = s/ ln M √ 2 with s ≥ 3, hence we must have E = rE · M (1−3/s )/2 (which is at best O( M )). At the same time, we need M/N → v for some small constant v in order to be robust against the Gaussian noise 2 N (0, (CσM/N )2 ). The new asymptotic result of Section 5 is stronger as it only requires E = c√ MM with CM → 0 (E is sub-linear in M ) as M → ∞. This means that for E much larger than O( M ) (which leaks more privacy), we can still prove a comparable DP guarantee.

5

Asymptotic Analysis

The concrete bound of Theorem 4.1 is tight up to constant factors within the Berry-Esseen proof framework, but the Berry-Esseen term is the dominating factor in δ. If we want to improve, we must improve the dominating term. We introduce a new proof technique based on a generalization of the law of large numbers that replaces the Berry-Esseen approximation with a finer asymptotic estimate: 5

Privacy parameter vs. M (E = 1) = 0.5 = 0.75 = 1.0 = 1.5 = 2.0

(privacy parameter)

10 1

10 2

= 0.01

10 3

10 4

= 10 4

104

105

106

107

108

Number of rounds M

109

1010

1011

Figure 1: Privacy parameter δ vs. number of rounds M for σ ∈ {0.5, 0.75, 1, 1.5, 2}, computed from the full lower bound of Theorem 4.1 (E = 1); dashed lines mark δ = 0.01, 10−4 . The U-shape in σ (with σ ≈ 1 near-optimal) reflects the exponential growth of the Berry-Esseen coefficient for p small σ and its polynomial growth for large σ. Each curve begins at the smallest M satisfying σ ≥ 3/ ln M and the validity condition (1). Theorem 5.1. Let F (x) be a cumulative distribution for which all moments µk , k ≥ 1, exist with µ1 = 0 and µ2 = σ̄ 2 > 0. Suppose that the corresponding characteristic function ϕ(ξ) tends to 0 for ξ → ±∞. Let X1 , X2 , . . . be i.i.d. random variables with cumulative distribution F (x) and define the standardized sum X1 + · · · + Xn √ with cumulative distribution Fn (x) = P(Sn ≤ x). Sn = σ̄ n Let pn (x)

=

x + cn (1 − x2 ) + dn (3x − x3 ) + c2n (4x3 − 7x)

with cn and dn as defined by cn =

µ3 3/2 √ 6µ2 n

and dn =

µ4 − 3µ22 . 24µ22 n

Let 1 ≤ κn = o(n1/16 ). Then, restricted to |x| ≤ κn and for sufficiently large n, polynomial pn (x) is strictly increasing and invertible. Furthermore, uniformly in |x| ≤ κn , Φ(pn (x))

=

Fn (x) + o(1/n).

√ For completeness, Berry-Esseen implies Φ(x) = Fn (x) + O(1/ n) for all x. Theorem 5.1 yields only an asymptotic result, and we do not know its explicit convergence rate, which we need in order to obtain concrete parameter settings that improve over Theorem 4.1. The new asymptotic result does improve over the asymptotic result that can be derived from Theorem 4.1: √ Theorem 5.2. There exists sequences δM = o(1/M ) and γM = O( ln M /M ) such that the tradeoff function f of DP-SGD for a single epoch with M rounds with subsampling based on random shuffling and noise multiplier σ (σ is assumed to be a constant and not dependent on M ) satisfies Gµ+γM (a + δM ) − δM ≤ f (a) ≤ Gµ−γM (a − δM ) + δM + sM (a) for a ∈ [δM , 1 − δM ], 2/σ 2

e where µ (which depends on M ) is defined in Theorem 4.1 and sM (a) = √8πe·(M if a ≥ 1/2 + δM −1) and sM (a) = 0 otherwise.

Furthermore, f (a) ≥ (Gµ+γM ⊗ f0,δ̂M )(a) for a ∈ [0, 1], where

δ̂M = max{δM /a∗ , (1 − Gµ+γM (δM )) + δM } with a∗ = Gµ+γM (a∗ ). 6

Random shuffling: e1/ 2 1 Subsampled (DRS Cor. 5.4): 2(e1/ 2 (3/(2 )) + 3 ( 1/(2 )) 2)

105

Shuffle advantage ratio (monotone decreasing) sub / shuffle 2 (limit as 1 (limit as

1.4

0+) )

sub/ shuffle

104 103 102

Ratio

Asymptotic GDP- coefficient (per unit c)

Asymptotic GDP coefficient: shuffle vs. Poisson subsampling (DRS Cor. 5.4)1.5

101 100

1.3

midpoint

1.668

1.2 1.1 1.0

0.5

1.0

1.5

2.0

2.5

Noise multiplier

3.0

3.5

4.0

0.5

1.0

1.5

2.0

2.5

Noise multiplier

3.0

3.5

4.0

Figure 2: Asymptotic GDP-µ coefficient (per unit c = limM →∞ cM , E = c2M M ) for random shuffling (Theorem 5.2) vs. subsampled Gaussian (Cor. 5.4 of [8]). Left: both coefficients diverge as σ → 0+ and decay √ like 1/σ as+ σ → ∞ (log scale). Right: the ratio µsub /µshuffle decreases monotonically from 2 (as σ → 0 ) to 1 (as σ → ∞); marker: midpoint σ ≈ 1.668 where the ratio √ equals (1 + 2)/2 ≈ 1.207. Finally, let c ≥ 0 and suppose that cM → c as M → ∞ and consider a number of epochs E = c2M · M . Then, as M → ∞, f ⊗E (a) ≥ G √ (a) 2 M

c·

e1/σ −1 ⊗E

uniformly in a ∈ [0, 1]. If cM → 0 as M → ∞, then f (a) → 1 − a uniformly in a ∈ [0, 1]. In other words, E = c2M · M epochs with each epoch having M rounds tends not to leak any privacy for M → ∞ and CM → 0. Comparing random shuffling and poisson subsampling. This asymptotic result can be directly compared with the corresponding asymptotic for Poisson subsampling given by Corollary 5.4 in [8]. In the regime cM → 0, both random shuffling and Poisson subsampling converge to the randomguessing diagonal 1 − a. For E = c2M · M with cM → c, the trade-off function over E epochs with each epoch having M rounds converges to Gc·√2(e1/σ2 Φ( 3 )+3Φ(− 1 )−2) (a). 2σ

√

2σ

1/σ 2

− 1 (random shuffling, Theorem 5.2) and Figure 2 plots the two GDP coefficients e q
2 3 1 2 e1/σ Φ( 2σ ) + 3Φ(− 2σ ) − 2 (subsampled Gaussian, Cor. 5.4 of [8]), together with their ratio. √ The ratio is monotone in σ√on (0, ∞), with limits 2 as σ → 0+ and 1 as σ → ∞: random shuffling is asymptotically a factor 2 closer to the random-guessing diagonal in the low-noise limit, and the two regimes become equivalent in the high-noise limit. Separation. We may define the separation [8, 12] of a trade-off function f (a) from the random guessing diagonal 1 − a as the distance sep(f ) = max min ∥(a, f (a)) − (γ, 1 − γ)∥2 . a∈[0,1] γ∈[0,1]

If f ≥ g is a convex, decreasing and symmetric3 trade-off function g, then 1 sep(f ) ≤ sep(g) = √ (1 − 2a∗ ), where a∗ = g(a∗ ) 2 is the unique fixed point of g. √ Corollary 5.3. For constant σ, Theorem 5.2 implies sep(f ⊗E ) = O(µ E) as opposed to Theorem 4.1 which can only be used to derive sep(f ⊗E ) = O(µE). √ Both theorems yield the same µ√= O(1/ M ) dependency. The asymptotic improvement of Theorem 5.2 shows the much better O( E) dependency on the number of epochs E. 3 That is, g = g −1 with the inverse g −1 defined as g −1 (a) = inf{t ∈ [0, 1]

7

: g(t) ≤ a} for a ∈ [0, 1].

Table 1: Required number of rounds M at δ = 1/100, E = 1. MBE+1/√2π inverts the closed-form √
p lower bound: δ ≈ 2B · coef(σ) + 1/ 2π · (e1/σ2 − 1)/(M − 1). Mexact is the smallest M such that the full right-hand side of Theorem 4.1 (all six terms plus the validity condition (1)) satisfies δ ≤ 1/100, found by bisection. The closed-form expression matches the exact solve to within ∼0.1% across all σ shown, so two-term formula suffices for parameter selection. The last column is the minimum dataset size needed to keep the per-round noise CσM/N ≤ 0.1, computed from Mexact . σ MBE+1/√2π Mexact Min. N 0.50 0.75 1.00 1.50 2.00

1.57×109 3.72×106 1.14×106 3.23×106 1.49×107

1.57×109 3.72×106 1.14×106 3.23×106 1.49×107

7.87×109 2.79×107 1.14×107 4.85×107 2.98×108

Convergence rate. For Poisson subsampling, Corollary 5.4 in [8] provides an asymptotic result for CM → c for any constant c ≥ 0, not only for c = 0. However, this does not teach concrete parameter settings since the convergence rate as an explicit function of M and σ is unknown. Both for Poisson subsampling as well as for random shuffling, we need to have a concrete (closed formula) expression of the convergence rate of asymptotic results in order to derive concrete parameter settings. √ Open problem. Theorem 4.1 penalizes the trade-off function by its 1/ M Berry-Esseen term across the whole range a ∈ [0, 1]. We notice that even the Berry-Esseen term in the √ without √ lower bound of δ in Theorem 4.1 we still have the µ/ 2π = O(1/ M ) term. The advantage of Theorem 5.2 is that our new proof technique allows us to replace √ the Berry-Esseen term by a suitable lower bound Gµ+γM (a + δM ) − δM which maintains the 1/ M dependency for the separation but provides a much better asymptotic lower bound when considering the whole range a ∈ [0, 1]. This allows an improved analysis when considering multiple epochs E. As an open problem for future work, the sequences δM and γM (which characterize the convergence rate) can be made explicit such that we obtain a concrete result like Theorem 4.1 for multiple epochs that allows us to select tight practical parameters and also matches the asymptotic result of Theorem 5.2.

6

Concrete Parameter Settings

We now extract practical parameter settings from Theorem 4.1 and examine the interplay between σ, δ, M , E, and N . 6.1

Single-Epoch Regime (E = 1)

For the single-epoch case, the composition result simplifies to f (a) ≥ 1 − a − δ. For large enough M , the Berry-Esseen term dominates and δ is approximately given by (2). Consider σ = 1 and δ = 1/100. Inverting the two-term closed-form lower bound M ≈ 1.14 × 106 rounds4 , and the exact solve of Theorem 4.1 agrees to within 0.1% (see Table 1). To keep the Gaussian noise per round CσM/N small (say, at most 0.1), we need N ≈ 1.14 × 107 training samples. In a distributed or federated learning setting, a client contributing a single epoch of training over a dataset of this size can achieve a meaningful DP guarantee with δ = 0.01. As Figure 1 illustrates, the noise multiplier σ = 1 is near-optimal in minimizing the required M for a given δ level, reflecting the balance between the exponential growth of the Berry-Esseen coefficient for small σ and the polynomial growth of the noise terms for large σ. Table 1 summarizes the required parameters for several values of σ. 6.2

Multiple Epochs

√ Linear-in-E vs. conjectured E dependence. The composition bound f ⊗E (a) ≥ (1 − δ)E − a obtained by iterating Theorem 4.1 carries an effective δ · E penalty, and this linear-in-E scaling is the 4 All numerical evaluations in the figures and tables of this paper substitute the proven Shevtsova upper bound B = 0.4748

[22] for the universal Berry-Esseen constant in (3).

8

√ dominant source of slack for E ≫ 1. Two analyses suggest √ that the correct dependence may be E: our own asymptotic result already gives sep(f ⊗E ) = O(µ E) (Corollary 5.3), and the analogous Poisson-subsampling analysis of Dong et al. [8] shows that composing per-round trade-off functions converges to a Gaussian trade-off function Gµ , whose E-fold composition is Gµ√E . We therefore √ conjecture that the concrete (non-asymptotic) bound √ for random shuffling also obeys a E · δ penalty, and we leave a closed-form proof of this concrete E dependence as an open problem for future work. For E epochs, the composition guarantee becomes f ⊗E (a) ≥ (1 − δ)E − a. For (1 − δ)E to remain close to 1, we need δE to be small, i.e., δ ≪ 1/E. This places increasing demands on M and N as E grows, and the parameters quickly become impractical. Multi-epoch explosion. Consider E = 100 epochs. For the composition guarantee to be meaningful, we need (1 − δ)100 ≈ 1 − 100δ to be close to 1, which requires δ ≤ 1/10,000. Plugging δ = 10−4 into the lower bound (3) for σ = 1 pushes the required number of rounds to approximately M ≈ 1.14 × 1010 . To keep the Gaussian noise CσM/N manageable, we then need N ≳ 1.14 × 1011 , a dataset of one hundred billion samples. The explosion is driven by the quadratic dependence of M on 1/δ in (3): halving δ quadruples M , which in turn requires quadrupling N . For E = 4 epochs, the situation is more moderate: δ ≤ 1/400 suffices, requiring M ≈ 1.82 × 107 and N ≈ 1.82 × 108 (for σ = 1). While substantially larger than the single-epoch case, these numbers remain within the range of large-scale distributed learning systems. √ Even under the conjectured E δ scaling, large E√is impractical. Suppose hypothetically that the loss from the random-guessing√diagonal grows as E δ rather than E δ. Hitting a target δtgt over E epochs then requires δ < δtgt / E, and the rule of thumb M ≈ 114/δ 2 obtained by inverting (3) at σ = 1 (calibrated against the M ≈ 1010 figure for δ = 10−4 in the “Multi-epoch explosion” paragraph above) gives M ≈ 1.14 × 106 · E for δtgt = 10−2 , with the √ per-round noise condition CσM/N ≤ 0.1 adding N ≳ 10 M . So even under the more favorable E scaling, E = 100 already needs M ∼ 1.14 × 108 , N ∼ 1.14 × 109 , and E = 104 pushes both into the 1010 –1011 range. The single-epoch federated regime where Theorem 4.1 yields a meaningful guarantee at M ≈ 1.14 × 106 , N ≈ 1.14 × 107 , therefore remains the practical sweet spot for DP-SGD with random shuffling. Practical sweet spot. The analysis points strongly toward single-epoch training as the practical sweet spot for DP-SGD with shuffling. In the federated learning setting, where each client participates in only a small number of epochs (e.g., E = 1 or E = 4), the single-epoch guarantee f (a) ≥ 1−a−δ with δ = 0.01 and N ≈ 1.14 × 107 is achievable and directly applicable. Single-epoch DP is likely the most relevant regime for clients contributing local training data, and the fact that meaningful privacy can be guaranteed in this setting is a positive practical finding.

7

Conclusion

We have given a tight closed-form f -DP analysis of DP-SGD with random shuffling in the high-noise regime covered by Theorem 4.1, complementary to the small-σ impossibility result of Ertan and van Dijk [12]. The non-asymptotic Berry-Esseen bound (Theorem 4.1) is tight up to constants within its proof framework and yields transparent parameter recipes: at σ = 1 and δ = 10−2 , M ≈ 1.14 × 106 rounds and N ≈ 1.14 × 107 samples suffice in the single-epoch regime relevant to federated learning. Going beyond Berry-Esseen, an Edgeworth-type CLT refinement (Theorem 5.1) underpins the asymptotic Gaussian-DP √ characterization of Theorem 5.2, improving the multi-epoch separation from O(µE) to O(µ E) (Corollary 5.3); compared with the Poisson-subsampling asymptotic of [8], both regimes √ collapse to the random-guessing diagonal 1 − a as cM → 0, with random shuffling a factor 2 closer in the low-noise limit and the two coinciding as σ → ∞. Two open problems remain: making the sequences δM , γM in Theorem 5.2 explicit so as to obtain a concrete multi-epoch GDP-plus-small-error bound (rather than an improvement of the f0,δ -form Theorem 4.1, where √ the µ/ 2π separation contribution is√unavoidable) and, given that Corollary 5.3 and the analogous Poisson analysis both point toward a E δ rather than E δ multi-epoch penalty, a closed-form proof of this conjectured concrete dependence. 9

Acknowledgments The contribution of Marten van Dijk and Murat Bilgehan Ertan to this publication is part of the project CiCS of the research program Gravitation which is (partly) financed by the Dutch Research Council (NWO) under the grant 024.006.037.

References [1] Martín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 308–318. ACM, 2016. doi: 10.1145/2976749.2978318. URL https://doi.org/10.1145/2976749.2978318. [2] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 6280–6290, 2018. URL https://proceedings.neurips.cc/paper/2018/hash/ 3b5020bb891119b9f5130f1fea9bd773-Abstract.html. [3] Jeremiah Birrell, Reza Ebrahimi, Rouzbeh Behnia, and Jason Pacheco. Differentially private stochastic gradient descent with fixed-size minibatches: Tighter RDP guarantees with or without replacement. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL http://papers.nips.cc/paper_files/paper/2024/hash/ 14fef58f09f2ebe69306e0a322e3be2b-Abstract-Conference.html. [4] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie J. Su. Deep learning with gaussian differential privacy. CoRR, abs/1911.11607, 2019. URL http://arxiv.org/abs/1911.11607. [5] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I, Lecture Notes in Computer Science, pages 635–658, 2016. doi: 10.1007/ 978-3-662-53641-4\_24. URL https://doi.org/10.1007/978-3-662-53641-4_24. [6] Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. How private are DP-SGD implementations? In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024, Proceedings of Machine Learning Research, pages 8904– 8918. PMLR / OpenReview.net, 2024. URL https://proceedings.mlr.press/v235/ chua24a.html. [7] Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Scalable DP-SGD: shuffling vs. poisson subsampling. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL http://papers.nips.cc/paper_files/paper/ 2024/hash/81c252b45b3bd7d9bf080eb27794b762-Abstract-Conference.html. [8] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 02 2022. ISSN 1369-7412. doi: 10.1111/rssb.12454. URL https://doi.org/10.1111/rssb.12454. 10

[9] Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proc. Priv. Enhancing Technol., 2022(4):552–570, 2022. doi: 10.56553/POPETS-2022-0122. URL https://doi. org/10.56553/popets-2022-0122. [10] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014. doi: 10.1561/0400000042. URL https: //doi.org/10.1561/0400000042. [11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, Lecture Notes in Computer Science, pages 265–284. Springer, 2006. doi: 10. 1007/11681878\_14. URL https://doi.org/10.1007/11681878_14. [12] Murat Bilgehan Ertan and Marten van Dijk. Fundamental limitations of favorable privacy-utility guarantees for DP-SGD. volume abs/2601.10237, 2026. doi: 10.48550/ARXIV.2601.10237. URL https://doi.org/10.48550/arXiv.2601.10237. E-print states that the paper has been accepted at ACM CCS 2026. [13] C. G. Esseen. A moment inequality with an application to the central limit theorem. Scandinavian Actuarial Journal, 1956(2):160–170, 1956. doi: 10.1080/03461238.1956.10414946. URL https://doi.org/10.1080/03461238.1956.10414946. [14] William Feller. An Introduction to Probability Theory and Its Applications, volume II. John Wiley & Sons, 2nd edition, 1971. [15] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 11631–11642, 2021. URL https://proceedings.neurips.cc/ paper/2021/hash/6097d8f3714205740f30debe1166744e-Abstract.html. [16] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis R. Bach and David M. Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, JMLR Workshop and Conference Proceedings, pages 1376–1385. JMLR.org, 2015. URL http://proceedings. mlr.press/v37/kairouz15.html. [17] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], Proceedings of Machine Learning Research, pages 2560–2569. PMLR, 2020. URL http://proceedings.mlr.press/v108/koskela20b.html. [18] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Aarti Singh and Xiaojin (Jerry) Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, Proceedings of Machine Learning Research, pages 1273–1282. PMLR, 2017. URL http: //proceedings.mlr.press/v54/mcmahan17a.html. [19] Ilya Mironov. Rényi differential privacy. pages 263–275, 2017. doi: 10.1109/CSF.2017.11. URL https://doi.org/10.1109/CSF.2017.11. [20] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. CoRR, abs/1908.10530, 2019. URL http://arxiv.org/abs/1908.10530. [21] Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 11

2020, December 6-12, 2020, virtual, 2020. URL https://proceedings.neurips.cc/ paper/2020/hash/c8cc6e90ccbff44c9cee23611711cdc4-Abstract.html. [22] Irina Shevtsova. On the absolute constants in the berry-esseen type inequalities for identically distributed summands. 2011. URL https://arxiv.org/abs/1111.6554. [23] Alan Stuart and J. Keith Ord. "The normal d.f." Kendall’s Advanced Theory of Statistics. Vol. 1: Distribution Theory. originally by Maurice Kendall (5th ed.). Charles Griffin & Co., 1987. [24] Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled renyi differential privacy and analytical moments accountant. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, Proceedings of Machine Learning Research, pages 1226–1235. PMLR, 2019. URL http://proceedings.mlr.press/v89/wang19b. html.

A

Appendix Outline

The appendix is organized into a common adversarial reduction (Appendix B) and two parallel proof tracks: a non-asymptotic track based on Berry-Esseen (Appendices C and D, with a numerical sensitivity addendum in Appendix E) and an asymptotic track based on the Edgeworth expansion (Appendices F and G). Common setup (Appendix B). We state the worst-case adversarial model and reduce a single epoch of DP-SGD with random shuffling to a scalar hypothesis test. Under H0 (dataset d) the adversary observes M i.i.d. standard Gaussian rounds; under H1 (dataset d′ ) exactly one round, chosen uniformly by the shuffling permutation, is replaced by an N (1/σ, 1) observation. The corresponding likelihoods are written out in (5)–(6); by the Neyman–Pearson lemma the most powerful test at each fixed Type-I error level thresholds the likelihood ratio, equivalently the sample mean of the lognormal random variables Yj = exp(Xj /σ − 1/(2σ 2 )) with Xj ∼ N (0, 1). The trade-off function f (a) = β(α−1 (a)) defined by (7)–(8) is the object of study throughout the remaining appendices; this reduction is shared by both proof tracks. Non-asymptotic track: proof of Theorem 4.1. • Appendix C (Application of the Berry-Esseen Theorem). The Berry-Esseen theorem is stated and applied to the lognormal sample mean of (9). Proposition C.2 computes the mean u = E[Yj ] = 1, the second, third, and fourth central moments µk = E[(Yj − u)k ], and the third absolute central moment ρ3 = E[|Yj − u|3 ]. Proposition C.3 converts these into an explicit upper bound on the approximation error ϵn (h) between P[Ȳn < h] and the corresponding Gaussian probability, with separate√small-σ bound√(15) and large-σ bound (14). The closing subsection identifies σ = s/ ln n with s > 3 as a sufficient regime for the small-σ bound (15) to vanish as n → ∞. • Appendix D (Trade-Off Function: Full Proof). Lemma D.1 is an auxiliary result on symmetric convex trade-off functions: it suffices to prove the lower bound f (a) ≥ 1 − a − δ on the half-range a ∈ [1/2 − δ, 1/2] for it to extend automatically to all a ∈ [0, 1], together with the corresponding E-fold composition statement. The subsequent threshold analysis uses the slightly larger symmetric range a ∈ [1/2 − δ, 1/2 + δ]. The false-positive subsection (Proposition D.2) bounds α−1 (a). The false-negative subsection (Propositions D.3 and D.4) first expresses β(h) as an integral over an auxiliary standard-Gaussian variable z with integrand Φ(γ(h, z)), up to an error of size ϵ. The trade-off function subsection then performs the substitution h = α−1 (a): Proposition D.5 represents f (a) = β(α−1 (a)), up to the same error ϵ, as a truncated integral with integrand Φ(x − µ(z)), and Proposition D.6 bounds the tail truncation error. The Taylor-series subsection (Proposition D.7) expands Φ(x − µ(z)) to second order to obtain the lower bound (35); combined with Lemma D.1 and the preceding propositions, this completes the proof of Theorem 4.1. • Appendix E (Parameter Sensitivity). Numerical sensitivity of the required number of rounds M to the noise multiplier σ at three target privacy levels (Figure 3), inverting the closed-form two-term approximation of Theorem 4.1. 12

Asymptotic track: proofs of Theorems 5.1 and 5.2, and Corollary 5.3. • Appendix F (Edgeworth Expansion). Starting from the two-term Edgeworth expansion (44) of the standardized sum Sn , which holds for distributions whose moments are all finite and whose characteristic function tends to 0 at infinity, as is the case for the lognormal, we introduce the compact coefficients cn , dn defined in (45) and prove Theorem 5.1: for |x| ≤ κn = o(n1/16 ) the polynomial pn (x) is strictly increasing and invertible, and Fn (x) = Φ(pn (x)) + o(1/n) uniformly for |x| ≤ κn . The appendix then instantiates cn , dn explicitly for the lognormal case using Proposition C.2. • Appendix G (Trade-Off Function via Edgeworth Expansion). Mirrors the structure of Appendix D, using the approximation Fn = Φ ◦ pn + o(1/n) derived from the Edgeworth expansion (44) in place of the Berry-Esseen error bound. The false-positive subsection (Proposition G.1) gives the Edgeworth-based form of α(h), controls the inverse threshold α−1 (a), and identifies the admissible range of a. The false-negative subsection (Proposition G.3) gives the Edgeworth-based integral representation of β(h) with integrand Φ ◦ pM −1 (γ(h, z)). The trade-off function subsection (Proposition G.4; see Subsection G.3) substitutes h = α−1 (a) and characterizes f (a) asymptotically in terms of a Gaussian trade-off function Gµ+O(√ln M /M ) up to a sign-dependent O(1/M ) correction and an o(1/M ) residual. The closing subsection handles multi-epoch composition: Lemma G.5 extends Lemma D.1 to a two-function statement of the form f ≥ g ⊗f0,δ̂ , Proposition G.6 records two asymptotic properties of Gµ used in evaluating the δ̂ of Lemma G.5, and Proposition G.7 repackages the single-epoch bound from Proposition G.4 in the form ′ ′ ′ (a + δ f (a) ≥ GµM +γM M ) − δM required by Lemma G.5. The section then proves the multi-epoch lower-bound and limiting conclusions of Theorem 5.2, and closes with the proof of Corollary 5.3.

B

Adversarial Model: Full Details

We provide a self-contained derivation of the hypothesis-testing formulation underlying our privacy analysis. The adversarial model and the reduction to a scalar Gaussian test are due to [12]; we recall their derivation here in our own notation for completeness and to make the present paper self-contained. Setup. We consider two neighboring datasets d and d′ and a single epoch of DP-SGD with M rounds. The adversary observes a sample from the multi-dimensional distribution (xj )M j=1 where, ′ under d, all observations are pure noise, and under d , exactly one round (chosen uniformly at random by the shuffling permutation) contains a signal contribution from the differing record. The formal reduction from the DP-SGD mechanism to this scalar Gaussian observation model follows the framework of Ertan and van Dijk [12]. Worst-case adversary. The standard worst-case DP adversary is granted, in addition to the noisy batch updates, knowledge of each batch size and the partial sum of clipped gradients from all records other than the potentially differing one. As shown in [12] (Proposition 4.3), this auxiliary information allows the adversary to deterministically isolate the noisy contribution of the differing record in each round. Because Gaussian noise is isotropic, projecting onto the gradient direction and normalizing reduces the observation in each round to a scalar: pure noise N (0, 1) under d, or signal-plus-noise N (1/σ, 1) under d′ in the one round containing the genuine record. Hypothesis test. Let H0 correspond to dataset d and H1 to d′ . Let ϕ denote a rejection rule: given 5 the observation (xj )M j=1 , the rule outputs ϕ = 1 if H0 is rejected. The Type I error (false positive rate) is α(ϕ) = E[ϕ | d] ∈ [0, 1], and the Type II error (false negative rate) is β(ϕ) = 1 − E[ϕ | d′ ] ∈ [0, 1]. 5 The rejection rule can be probabilistic and output a probability ϕ after which a coin flip with bias ϕ decides whether the

null hypothesis will be rejected.

13

The trade-off function is

f (a) = inf′ {β(ϕ′ ) : α(ϕ′ ) ≤ a}. ϕ

Likelihood computation.

Under H0 , all observations are i.i.d. standard Gaussian: P[(xj )M j=1 | d] =

2 M Y e−xi /2 √ . 2π i=1

(5)

Under H1 , exactly one round j (uniform over {1, . . . , M }) contains the shifted observation: ′ P[(xj )M j=1 | d ]

=

2 2 M M 1 X e−(xj −1/σ) /2 Y e−xi /2 √ √ M j=1 2π 2π i=1,̸=j

=

2 M M 1 X xj /σ−1/(2σ2 ) Y e−xi /2 √ . e · M j=1 2π i=1

(6)

Optimal test statistic. By the Neyman–Pearson lemma, the uniformly most powerful test thresholds the likelihood ratio, which is equivalent to thresholding the sample average of lognormal variables. For h ≥ 0, define the Type I and Type II error rates parametrized by threshold h:   M X 2 1 exj /σ−1/(2σ ) > h d , (7) α(h) = P  M j=1 

 M X 2 1 β(h) = P  exj /σ−1/(2σ ) < h d′  . M j=1

(8)

The trade-off function is then f (a) = β(α−1 (a)). Computing this trade-off function requires 2 analyzing the distribution of the sample average of lognormal random variables Yj = eXj /σ−1/(2σ ) with Xj ∼ N (0, 1), which is the subject of Appendix C.

C

Application of the Berry-Esseen Theorem

Let {Yj }nj=1 be independent identically distributed random variables with E[Yj − u] = 0, E[(Yj − u)2 ] = σ̄ 2 and E[|Yj − u|3 ] = ρ3 . We define the normalized mean of {Yj }nj=1 as the random variable Pn Pn n √ 1X j=1 (Yj − u) j=1 (Yj − u) √ Ŷn = qP = (−u + = Yj ) · n/σ̄ n n n · σ̄ σ̄ 2 j=1 j=1

with cumulative probability distribution Fn (x).6 We define the k-th moment of F as µk = E[(Yj − √ u)k ]. We notice that E[Ŷn ] = µ1 · n/σ̄ = 0 and E[Ŷn2 ] = µ2 /σ̄ 2 = 1. For the density function of the normal distribution we use the notation 2

e−x /2 n(x) = √ 2π and by Φ(z) =

Rz −∞

n(x) dx we denote its cumulative probability distribution.

Theorem C.1. The Berry-Esseen theorem [13, 22] for identically distributed random variables states that there exists a universal constant B > 0 such that for all x and n |Fn (x) − Φ(x)| ≤ B · √

ρ3 . n · σ̄ 3

Universal constant B has been upper bounded to 0.4748 [22] and lower bounded to 0.4097 [13]. 6 Distribution F (x) is the n-fold convolution F n⋆ (xσ̄ √n), see page 141 of [14], of the cumulative distribution F = F n 1

corresponding to Yj − u, a single random variable minus the expectation.

14

The Berry-Esseen theorem generalizes the classical central limit theorem in that it also gives a bound on the maximal error of approximation between the normal cumulative distribution and the true cumulative distribution of the normalized mean. In this sense it characterizes the convergence rate towards the normal cumulative distribution. C.1

Sample Average

We apply the Berry-Esseen theorem to the independent identically distributed (lognormal) variables 2

Yj = eXj /σ−1/(2σ ) with Xj ∼ N (0, 1).

(9)

Proposition C.2. Let µk = E[(Yj − u)k ], where u = E[Yj ]. We have u

=

E[Yj ] = 1,

µ2

= σ̄ 2 = e1/σ − 1,

µ3

=

(e1/σ + 2)(e1/σ − 1)2 > 0,

µ4

=

(e4/σ + 2e3/σ + 3e2/σ − 3)(e1/σ − 1)2 > 0.

2

2

2

2

2

2

2

In addition ρ3 = E[|Yj − u|3 ] is equal to 2

2

3/σ − 3(1 − 2Φ(−3/(2σ)))e1/σ . ρ3 = (1 − 2Φ(−5/(2σ)))e +4(1 − 2Φ(−1/(2σ)))

Proof: We compute Z b

2

ekx/σ−kc/(2σ ) n(x) dx

−∞ 2

Z b

e−(x−k/σ) /2 k(k−c)/(2σ2 ) √ e dx 2π −∞ Z b−k/σ −x2 /2 2 e √ = ek(k−c)/(2σ ) dx 2π −∞ =

=

2

Φ(b − k/σ) · ek(k−c)/(2σ ) .

(10)

By taking b = ∞ and c = 1, we obtain the raw moments 2

E[Yjk ] = ek(k−1)/(2σ ) . In particular, u = E[Yj ] = 1 and

2

µ2 = σ̄ 2 = E[Yj2 ] − E[Yj ]2 = e1/σ − 1. Using the raw moments above and expanding central moments around u = 1, we obtain 2

2

µ3 = E[(Yj − 1)3 ] = e3/σ − 3e1/σ + 2 and

2

2

2

µ4 = E[(Yj − 1)4 ] = e6/σ − 4e3/σ + 6e1/σ − 3, which can be factored as given by the proposition. By using (10) for c = 1, we first compute Z b 2 (ex/σ−1/(2σ ) − 1)3 · n(x) dx −∞

Z b  = −∞

2

2

e3x/σ−3/(2σ ) − 3e2x/σ−2/(2σ ) 2 +3ex/σ−1/(2σ ) − 1 2

=

2



Φ(b − 3/σ)e3/σ − 3Φ(b − 2/σ)e1/σ . +3Φ(b − 1/σ) − Φ(b) 15

· n(x) dx

We use this equation to characterize ρ3

2

E[|eXj /σ−1/(2σ ) − 1|3 ] Z ∞ 2 = (ex/σ−1/(2σ ) − 1)3 · n(x) dx =

1/(2σ)

Z 1/(2σ) 2 + (1 − ex/σ−1/(2σ ) )3 · n(x) dx −∞ Z ∞ 2 = (ex/σ−1/(2σ ) − 1)3 · n(x) dx −∞

Z 1/(2σ) −2

2

(ex/σ−1/(2σ ) − 1)3 · n(x) dx

−∞ 2

2

2

2

=

(1 − 2Φ(−5/(2σ)))e3/σ − 3(1 − 2Φ(−3/(2σ)))e1/σ +3(1 − 2Φ(−1/(2σ))) − (1 − 2Φ(1/(2σ)))

=

(1 − 2Φ(−5/(2σ)))e3/σ − 3(1 − 2Φ(−3/(2σ)))e1/σ . +4(1 − 2Φ(−1/(2σ))) □

Proposition C.3. For

√

n 1X n Yj , with Ȳn = σ̄ n j=1

Ŷn = (Ȳn − 1) ·

(11)

the Berry-Esseen theorem implies r P[Ȳn < h] = Φ((h − 1) ·

n ) + ϵn (h) e1/σ2 − 1

(12)

with |ϵn (h)| at most 2

(1 − 2Φ(−5/(2σ)))e3/σ − 3(1 − 2Φ(−3/(2σ)))e1/σ +4(1 − 2Φ(−1/(2σ))) √ B· n · (e1/σ2 − 1)3/2 This is in turn bounded by r 8 −1/2 ≤B· ·n · π

2

2

.

46.115 + 0.375 · e1/σ + 5.625 · e3/σ 1+ σ2

(13)

2

! (14)

and (13) is also bounded by 2

≤B·

2

e3/(2σ ) 1 + 4 · e−3/σ √ · . n (1 − e−1/σ2 )3/2

(15)

The proposition characterizes the convergence rate or approximation error ϵn . For large σ the bound (14) is a tight approximation of (13) and for small σ the bound (15) is a tight approximation of (13). Proof: We have r Ŷn = (Ȳn − 1) ·

n

n e1/σ2 − 1

with Ȳn =

1X Yj , n j=1

where Ȳn is a sample average. We derive r P[Ȳn < h] = P[Ŷn < (h − 1) ·

n e1/σ2 − 1

r ] = Fn ((h − 1) ·

n ). e1/σ2 − 1

√ √ Taking x = (h − 1) · n/ e1/σ2 − 1 (which may depend on n) in the Berry-Esseen theorem yields ρ3 (12) with |ϵn (h)| ≤ B · √n·σ̄ 3 . From Proposition C.2 we obtain (13). 16

We want to understand how the convergence rate depends on√ σ. We first discuss large σ. A Taylor √ series expansion around 0 for x ≥ 0 teaches Φ(x) = 1/2 + x/ 2π − x3 /(6 2π) + Φ(5) (ξ)x5 /120 for some ξ ∈ [0, x]. We notice that |ϕ(5) (ξ)| is maximized for ξ = 0 over all real valued ξ. Similarly, for x ≥ 0, ex = 1 + x + eξ x2 /2 for some ξ ∈ [0, x] and within this range 0 ≤ eξ ≤ ex . We use this 2 to bound the nominator in (13). For the denominator we notice that e1/σ − 1 ≥ 1/σ 2 . Combining and reordering terms yields convergence rate given by (14). For small σ we have the following derivation. Together with 1 − 2Φ(−5/(2σ)) ≤ 1, 1 − 2 2 2 2Φ(−3/(2σ)) ≥ 0, 1 − 2Φ(−1/(2σ)) ≤ 1 and (e1/σ − 1)3/2 = e3/(2σ ) (1 − e−1/σ )3/2 , we bound (13) to (15). □ C.2

Necessary Lower Bound on σ

In order for DP-SGD to achieve a good utility, we need as small a noise multiplier σ as possible while still offering a solid privacy guarantee. We can derive an f-DP guarantee if |ϵn (h)| in Proposition C.3 converges to 0 for n → ∞. In order to establish convergence to 0, we need √ √ (16) σ = s/ ln n for some constant s > 3 such that the convergence rate of (15) is 2

2

|ϵh (h)| ≤ B · n−(1−3/s )/2 (1 + O(n−1/s ))

(17)

with a negative exponent in n (notice that in the application of the Berry-Esseen theorem σ may depend on n). √ For completeness, by substituting σ = s/ ln n in (14), we have r 2 8 −1/2 ·n · (1 + O(n3/s (ln n)/s2 )) |ϵh (h)| ≤ B · (18) π √ describing how the convergence rate depends on large s ≫ ln n. √ Imposing the lower bound s/ ln n on σ restricts our DP analysis. For smaller σ, we cannot use Berry-Esseen and we are left with complex formulas which we cannot compute efficiently or interpret (the distribution Fn of the sum of a small number n of identically distributed lognormal random variables is known to be difficult to approximate using simple interpretable formulas).

D

Trade-Off Function: Full Proof

We first prove an auxiliary lemma which we use in the proof of Theorem 4.1. Lemma D.1 is a generic property of symmetric convex trade-off functions, applicable beyond the random-shuffling setting. Lemma D.1. Let f be a symmetric convex trade-off function. Suppose that f (a) ≥ 1 − a − δ for some δ > 0 and for a ∈ [1/2 − δ, 1/2]. Then, for all a ∈ [0, 1], f (a) ≥ max{1 − a − δ, 0} = f0,δ (a) and

⊗E f ⊗E (a) ≥ f0,δ (a) = f0,1−(1−δ)E (a) = max{(1 − δ)E − a, 0}.

Proof of Lemma D.1: Since f is a symmetric convex trade-off function, the fixed point a∗ = f (a∗ ) indicates the point (a∗ , a∗ ) on the trade-off curve furthest away from the random guessing line 1 − a. We know that f (a) ≥ 1 − a − δ for a ∈ [1/2 − δ, 1/2]. Notice that f (1/2) ≥ 1/2 − δ and f (1/2 − δ) ≥ 1/2. Since f is decreasing and continuous, there exists a point a ∈ [1/2 − δ, 1/2] such that a = f (a). The trade-off function has exactly one fixed point a∗ . We conclude that a∗ ∈ [1/2 − δ, 1/2]. This means that the distance of the point (a∗ , a∗ ) on the trade-off curve to the √ random guessing line 1 − a is at most δ/ 2. Since the other points on the trade-off curve are at least this close to the random guessing line, we have that for all a ∈ [0, 1], f (a) ≥ 1 − a − δ. The remainder of the lemma follows from the definition of f0,δ and the known E-fold composition of f0,δ (see Section 3.3 in [8]). □ 17

D.1

False Positive Rate

We are ready to analyze α(h) of (7) with the probability density of (xj )M j=1 conditioned on d defined by (5). By using the definition of ȲM in (11) with the Yj defined in (9) and by using approximation (12) we obtain α(h)

= =

P[ȲM > h] = 1 − P[ȲM < h] r M ) − ϵM (h), 1 − Φ((h − 1) · 1/σ e 2 −1

(19)

for h ≥ 0. Since α(h) is strictly decreasing in h, α has an inverse α−1 . We define ϵ′M (a) = ϵM (α−1 (a)) and notice that |ϵ′M (a)| is at most (13) for n = M , which in turn is at most ϵ = (13) for n = M − 1. For the inverse α−1 (a) = h we derive r

α

−1

(a)

e1/σ2 − 1 (1 − ϵM (h) − a) · M r 2 1/σ e −1 1 + Φ−1 (1 − ϵ′M (a) − a) · , M −1

=

h=1+Φ

=

(20)

where |ϵ′M (a)| ≤ ϵ. We notice that (20) cannot be used to compute α−1 (a) exactly since ϵ′M (a) depends on α−1 and ϵM with only a known bound for the latter. As shown in Lemma D.1, in our characterization of trade-off function f (a) we only need to analyze a restricted range of a. For some κ > 0 with Φ(−κ) ≤ 1/2 − ϵ − δ, where δ plays the role of the δ used in Lemma D.1, we analyze f (a) for a ∈ [1/2 − δ, 1/2 + δ] ⊆ [Φ(−κ) + ϵ, 1 − Φ(−κ) − ϵ]. This implies (notice that |ϵ′M (a)| ≤ ϵ and observe that 1 − a is in the same restricted range as a) 1 − ϵ′M (a) − a ∈ [Φ(−κ), 1 − Φ(−κ) = Φ(κ)]. Applying the inverse of Φ yields |Φ−1 (1 − ϵ′M (a) − a)| ≤ κ.

(21)

Combining (20) and (21) proves: Proposition D.2. Let ϵ = (13) for n = M − 1. Let a ∈ [1/2 − δ, 1/2 + δ] with Φ(−κ) ≤ 1/2 − ϵ − δ for some δ > 0. Then, |ϵ′M (a)| ≤ ϵ, |Φ−1 (1 − ϵ′M (a) − a)| ≤ κ, and r r 1/σ 2 − 1 e e1/σ2 − 1 α−1 (a) ∈ [1 − κ · ,1 + κ · ]. (22) M M D.2

False Negative Rate

In order to analyze β(h) = 1 − E[ϕ | d′ ] defined by (8) with the probability density of (xj )M j=1 condiPM xj /σ−1/(2σ 2 1 ) tioned on d′ defined by (6), we notice that probability density (6) is equal to M e j=1 times the probability density (5) for d. This implies β(h)

=

1 − E[ϕ | d′ ] = E[1 − ϕ | d′ ]

=

E[(1 − ϕ) ·

M

1 X xj /σ−1/(2σ2 ) e | d]. M j=1

Since the probability density (5) is symmetric with respect to permutations of indices j ∈ {1, . . . , M }, we conclude that 2 β(h) = E[(1 − ϕ) · ex1 /σ−1/(2σ ) | d] 18

PM xj /σ−1/(2σ2 ) 1 Since 1 − ϕ applied to (xj )M is < h, j=1 is equal to 1 if and only if the average M j=1 e we have the integral Z 2 M Y e−xi /2 x1 /σ−1/(2σ 2 ) √ e · dx, β(h) = PM xj /σ−1/(2σ 2 ) 1 2π <h (xj )M j=1 e j=1 : M i=1 where dx denotes the product dx1 . . . dxM . Reordering terms gives Z 2 2 M e−(x1 −1/σ) /2 Y e−xi /2 √ √ · dx. PM xj /σ−1/(2σ 2 ) 1 2π 2π <h (xj )M j=1 e j=1 : M i=2 Notice that the range 0<

2 1 · ex1 /σ−1/(2σ ) < h M

translates into x1 < σ ln(M h) + 1/(2σ). We use the variable substitution z = x1 − 1/σ with z < σ ln(M h) − 1/(2σ) (notice that dx1 = dz). This yields the following proposition: Proposition D.3. We may characterize β(h) (the false negative rate as defined by (8)) as the integral Z σ ln(M h)−1/(2σ) Z PM xj /σ−1/(2σ2 ) β(h) = 1 < z=−∞ j=2 e M −1 M (xj )j=2 : 1 z/σ+1/(2σ 2 ) (h − M · e ) · MM−1 2 2 M Y e−xi /2 e−z /2 √ dx2 · · · dxM · √ dz. 2π 2π i=2

By using α as defined by (19) for M − 1, the inner multi-dimensional integral in Proposition D.3 is equal to 2

M ez/σ+1/(2σ ) − ) M −1 M −1 r 2 ez/σ+1/(2σ ) M −1 M − − 1) · Φ((h · ) 1/σ M −1 M −1 e 2 −1

1 − α(h · =

2

ez/σ+1/(2σ ) M − ), (23) M −1 M −1 where the absolute value of the ϵM −1 (.) term is at most ϵ as defined in Proposition C.3. The outer integral over the ϵM −1 (.) term is at most the expectation of the ϵM −1 (.) term with respect to the Gaussian distribution represented by z and therefore its absolute value is also at most ϵ. This proves: Proposition D.4. Let ϵ satisfy the condition of Proposition C.3. Then, Z σ ln(M h)−1/(2σ) 2 e−z /2 |β(h) − Φ(γ(h, z)) · √ dz| ≤ ϵ 2π −∞ with r 2 M ez/σ+1/(2σ ) M −1 γ(h, z) = (h · − − 1) · . 1/σ M −1 M −1 e 2 −1 +ϵM −1 (h ·

D.3

Trade-Off Function

In order to compute trade-off function f (a) we substitute h = α−1 (a) with α−1 (a) approximated by (20) in γ(h, z) of Proposition D.4. This yields (after reordering terms) r 2 M ez/σ+1/(2σ ) − 1 −1 ′ √ Φ(Φ (1 − ϵM (a) − a) · −√ ). (24) M −1 M − 1 e1/σ2 − 1 19

p This looks like the well known Gaussian trade-off function except for the ϵ′M (a) and M/(M − 1) terms. This shows that the trade-off function f (a) = β(α−1 (a)) is approximately an expectation (the integral in Proposition D.4) over Gaussian trade-off functions. Since we are interested in a DP guarantee that shows that the trade-off function f (a) is close to the ideal 1 − a, we will use approximations that lose the link to Gaussian trade-off functions. We rewrite (24) as

Φ(x − µ(z)) with x = Φ−1 (1 − ϵ′M (a) − a)

and

r 2 ez/σ+1/(2σ ) − 1 M −1 ′ √ µ(z) = √ − Φ (1 − ϵM (a) − a) · ( − 1). 2 1/σ M −1 M −1 e −1 Notice that r r M 1 1 −1= 1+ −1≤ M −1 M −1 2 · (M − 1)

and Proposition D.2 tells us |Φ−1 (1 − ϵ′M (a) − a)| ≤ κ. This shows that 2

ez/σ+1/(2σ ) − 1 κ √ − ϵ′′M (a) with |ϵ′′M (a)| ≤ . µ(z) = √ 2 1/σ 2 · (M − 1) M −1 e −1

(25)

Substituting these expressions into Proposition D.4 proves: Proposition D.5. Let ϵ, a and κ satisfy the conditions of Proposition D.2. Then, Z σ ln(M α−1 (a))−1/(2σ) 2 e−z /2 |f (a) − dz| ≤ ϵ Φ(x − µ(z)) · √ 2π −∞ with x = Φ−1 (1 − ϵ′M (a) − a) and 2

ez/σ+1/(2σ ) − 1 κ √ |µ(z) − √ . |≤ 2 2 · (M − 1) M − 1 e1/σ − 1

(26)

Proposition D.6. Let ϵ, a and κ satisfy the conditions of Proposition D.2. Let x = Φ−1 (1−ϵ′M (a)−a) and µ(z) satisfy (26) of Proposition D.5. Then, Z +∞ 2 e−z /2 dz Φ(x − µ(z)) · √ 2π −∞ Z σ ln(M α−1 (a))−1/(2σ) 2 e−z /2 ≥ dz Φ(x − µ(z)) · √ 2π −∞ Z +∞ 2 e−z /2 ≥ Φ(x − µ(z)) · √ dz (27) 2π −∞ −Φ(−(σ ln(M α−1 (a)) − 1/(2σ))). We have Φ(−(σ ln(M α−1 (a)) − 1/(2σ))) ≤ θ for 2

θ= For σ ≥

p

e−t /2 √ t · 2π

r t=σ ln(M (1−κ·

.

(28)

2 e1/σ −1 1 ))− 2σ M

3/ ln M and M ≥ max{8κ3 , 3}, we have θ≤

2.88 ·

√

4.52 √ · M −25/24 . ln M − 2.41/ ln M

The condition on M suggests to use a maximal κ of 2

κ = (e1/σ − 1)/2

(29) p which results in the condition M ≥ (e1/σ − 1)3 . After substituting σ ≥ 3/ ln M , we see that this condition is satisfied. 2

20

Proof: The integral can be upper and lower bounded as follows: Z +∞ 2 e−z /2 Φ(x − µ(z)) · √ dz 2π −∞ Z σ ln(M α−1 (a))−1/(2σ) 2 e−z /2 Φ(x − µ(z)) · √ ≥ dz 2π −∞ Z +∞ 2 e−z /2 = Φ(x − µ(z)) · √ dz 2π −∞ Z +∞ 2 e−z /2 − Φ(x − µ(z)) · √ dz 2π σ ln(M α−1 (a))−1/(2σ) Z +∞ 2 e−z /2 dz ≥ Φ(x − µ(z)) · √ 2π −∞ Z +∞ 2 e−z /2 √ − dz 2π σ ln(M α−1 (a))−1/(2σ) Z +∞ 2 e−z /2 = dz Φ(x − µ(z)) · √ 2π −∞ −Φ(−(σ ln(M α−1 (a)) − 1/(2σ))). By using (22), we derive

≥

1 σ ln(M α−1 (a)) − 2σ r e1/σ2 − 1 1 σ ln(M (1 − κ · )) − M 2σ

and we have Φ(−(σ ln(M α−1 (a)) − 1/(2σ))) r e1/σ2 − 1 1 ≤ Φ(−(σ ln(M (1 − κ · )) − )). M 2σ Formula 7.1.13 from Abramowitz and Stegun states for x ≥ 0, Z ∞ 2 2 1 1 √ p < ex e−z dz ≤ 2 x+ x +2 x + x2 + 4/π x √ which, after substituting t = 2 · x and reordering terms, yields r r 1 2 −t2 /2 1 2 −t2 /2 √ p e < Φ(−t) ≤ e . t + t2 + 4 π t + t2 + 8/π π √ 2 The right hand side is at most e−t /2 /(t · 2π). This yields the upper bound (28). √ √ We now consider σ = s/ ln M with s ≥ 3. We derive r 1 e1/σ2 − 1 σ ln(M (1 − κ · )) − M 2σ √ p s ln M = √ · ln(M − κ · M 1/2 M 1/s2 − 1) − 2s ln M √ 2 s ln M ≥ √ · ln(M − κ · M (1+1/s )/2 ) − . 2s ln M Notice that if M ≥ 8 · κ3 , then 2

κ · M (1+1/s )/2 ≤ κ · M 2/3 ≤ M/2. 21

(30)

(31)

From this we obtain the lower bound √

s · ln(M/2) − ln M

√

ln M . 2s

√ By noticing that this lower bound is increasing in s, and using s ≥ 3, we have that (31) is at least √ √ √   √ √ 3 ln M 1 3 ln 2 √ ln(M/2) − √ = 3− √ ln M − √ 2 3 2 3 ln M ln M √ √ 5 3 ln 2 √ ln M − √ = . 2 3 ln M Set

√ 5 √ 3 ln 2 . t = √ ln M − √ 2 3 ln M

For M ≥ 3, t > 0. Therefore, using the right hand side of (30), r 1 2 −t2 /2 p Φ(−t) ≤ e 2 π t + t + 8/π r 1 2 −t2 /2 ≤ e . 2t π Moreover,

(32)

√ 2 3 ln 2 5 √ 2t = √ ln M − √ , 3 ln M

and t2

= ≥

25 3(ln 2)2 ln M − 5 ln 2 + 12 ln M 25 ln M − 5 ln 2. 12

Consequently, 2

e−t /2 ≤ 25/2 M −25/24 . Combining these estimates gives p Φ(−t)

≤

√ 5

√

3

√

3 ln 2 ln M − 2√ln M

Notice that the upper bound holds for all σ ≥ D.4

2/π 25/2

· M −25/24 .

(33)

p 3/ ln M with M ≥ max{8κ3 , 3}.

Taylor Series Expansion and Proof of Theorem 4.1

Proposition D.7. Let ϵ, a and κ satisfy the conditions of Proposition D.2. Let x = Φ−1 (1−ϵ′M (a)−a) and µ(z) satisfy (26) of Proposition D.5. Then, Z +∞

2

e−z /2 Φ(x − µ(z)) · √ dz 2π −∞   s 2  1 1/σ e −1 1 κ  ≥1−a−ϵ− √ +√ −  2π M −1 8π M − 1  ( ) √ 2 2 e2/σ + e1/σ − 1 κ · e1/σ2 − 1 κ2 1 √ + + . (M − 1) 4(M − 1)2 (M − 1)3/2 8eπ 22

Substituting (29) and using s

e1/σ2 − 1 M −1 yields (after reordering and combining terms) the lower bound µ=

1 1−a−ϵ− √ µ 2π ( ) 2 1 1 e1/σ √ + √ − (1 + ) µ2 1 − e−1/σ2 4 2π 2 2eπ 1 1 − √ µ3 − √ µ4 . 4 2eπ 32 2eπ

(34)

(35)

Proof: In order to study the integral (27) we use a Taylor series expansion. For all positive x and µ, there exists a ξ ∈ [x − µ, x] such that Φ(x − µ) = Φ(x) − µΦ′ (x) +

µ2 ′′ Φ (ξ). 2

√ 2 /2 We notice that Φ′′ (ξ) = −e−ξ √ · ξ/ 2π, which absolute value is maximized over the real numbers for ξ = ±1, i.e., |Φ′′ (ξ)| ≤ 1/ 2eπ. We have Φ(x − µ) = Φ(x) − µΦ′ (x) +

µ2 1 ρ(x, µ) with |ρ(x, µ)| ≤ √ . 2 2eπ

(36)

This allows us to derive 2

Z +∞

=

e−z /2 Φ(x − µ(z)) · √ dz 2π −∞  −z2 /2 Z +∞  Φ(x) − µ(z)Φ′ (x) e 2 dz · √ µ(z) + ρ(x, µ(z)) 2π −∞ 2

(37)

We observe 2

Z +∞

e−z /2 Φ(x) · √ dz 2π −∞

=

Φ(x)

= Φ(Φ−1 (1 − ϵ′M (a) − a)) = 1 − ϵ′M (a) − a. and together with |ϵ′M (a)| ≤ ϵ we obtain Z +∞ 2 e−z /2 dz| ≤ ϵ. |(1 − a) − Φ(x) · √ 2π −∞ We notice that (26) implies Z +∞ |

2

e−z /2 µ(z) · √ dz 2π −∞ Z +∞ 2 2 ez/σ+1/(2σ ) − 1 e−z /2 √ √ − · dz| √ 2π M − 1 e1/σ2 − 1 −∞

Z +∞ ≤ −∞

2

κ e−z /2 κ · √ dz = . 2 · (M − 1) 2 · (M − 1) 2π

Applying (10) for b = ∞ and c = −1 with k = 1 and k = 0 yields after simplification s Z +∞ 2 2 ez/σ+1/(2σ ) − 1 e−z /2 e1/σ2 − 1 √ √ · dz = . √ M −1 2π M − 1 e1/σ2 − 1 −∞ 23

(38)

√ √ 2 Together with Φ′ (x) = e−x /2 / 2π ≤ 1/ 2π we obtain s −z 2 /2 e1/σ2 − 1 e | µ(z)Φ′ (x) · √ dz − · Φ′ (x)| M −1 2π −∞ κ κ 1 ≤ · Φ′ (x) ≤ √ , 2 · (M − 1) M −1 8π Z +∞

hence, 2

Z +∞

≤

e−z /2 dz| | µ(z)Φ (x) · √ 2π −∞ s κ 1 e1/σ2 − 1 1 √ +√ . M −1 2π 8π M − 1 ′

(39)

The bound (25) leads to the following derivation: First, 2

2

µ(z)

=

ez/σ+1/(2σ ) − 1 √ − ϵ′′M (a))2 (√ M − 1 e1/σ2 − 1

=

e2z/σ+1/σ − 2ez/σ+1/(2σ ) + 1 (M − 1)(e1/σ2 − 1)

2

2

e −2ϵ′′M (a) · √

z/σ+1/(2σ 2 )

M −1

√

−1

e1/σ2 − 1

+ ϵ′′M (a)2 .

Taking the expectation of µ(z)2 with respect to the normal distribution (we use (10) for b = ∞, c = −1 and k = 0, 1 and 2) yields 2

=

2

2

e1/σ − 1 e3/σ − 2e1/σ + 1 ′′ √ − 2ϵ (a) · + ϵ′′M (a)2 √ M (M − 1)(e1/σ2 − 1) M − 1 e1/σ2 − 1 √ 2 2 e1/σ2 − 1 e2/σ + e1/σ − 1 ′′ − 2ϵM (a) · √ + ϵ′′M (a)2 . (M − 1) M −1

Second, (25) states |ϵ′′M (a)| ≤ κ/(2(M − 1)) and from this we obtain the upper bound √ 2 2 e2/σ + e1/σ − 1 κ · e1/σ2 − 1 κ2 + + . (M − 1) 4(M − 1)2 (M − 1)3/2 √ Together with |ρ(x, µ(z))| ≤ 1/ 2eπ this proves Z +∞ 2 √ µ(z)2 e−z /2 | ρ(x, µ(z)) · √ dz| ≤ (40)/ 8eπ. 2 2π −∞

(40)

(41)

Now we are ready to lower bound (37) by using (38), (39), (40) and (41) together with the triangle inequality. This proves Proposition D.7. □ Proof of Theorem 4.1: We are ready to prove our first main result. We combine Propositions D.7, D.6 and D.5, where we use κ satisfying (29) leading to (35) with µ defined in (34) as the lower bound in Proposition D.4. This leads to f (a) ≥ (35) −

4.52 √ √ M −25/24 − ϵ 2.88 ln M − 2.41/ ln M

(42)

for ϵ, a and κ satisfying the conditions of Proposition D.2 where δ is defined as 1 − a minus the right hand side of (42). In order to be able to apply Lemma D.1, we require, for κ satisfying (29), 2

Φ(−(e1/σ − 1)/2) = Φ(−κ) ≤ 1/2 − ϵ − δ. 24

Sensitivity: required M vs. (closed-form two-term approximation) = 0.01 = 0.001 = 0.0001

Required number of rounds M

1015 1013 1011 109 107 0.5

1.0

1.5

2.0

Noise multiplier

2.5

3.0

Figure 3: Required rounds M vs. noise multiplier σ from the closed-form two-term approximation (within ∼0.1% of the exact Theorem 4.1 solve), for δ ∈ {10−2 , 10−3 , 10−4 } at E = 1. Each curve 2 is U-shaped: for small σ, M grows exponentially via the e3/(2σ ) factor in the Berry-Esseen bound 2 on δ; for large σ, M grows polynomially via the (1 − e−1/σ )−3 factor. The minimum sits near σ ≈ 1 for all δ.

This requirement translates into 1 3ϵ + √ µ 2π ( ) 2 1 1 e1/σ √ + √ + (1 + ) µ2 1 − e−1/σ2 4 2π 2 2eπ 1 1 + √ µ3 + √ µ4 4 2eπ 32 2eπ 4.52 √ √ · M −25/24 + 2.88 · ln M − 2.41/ ln M ≤

2

1/2 − Φ(−(e1/σ − 1)/2).

(43)

For ϵ we use upper bound (15) with n = M − 1: 2

2

2

−3/σ 1 + 4 · e−3/σ e3/(2σ ) 1/σ 2 1 + 4 · e · = B · e · ·µ ϵ≤B·√ 2 (1 − e−1/σ2 )2 M − 1 (1 − e−1/σ )3/2

Requirement (43) withp ϵ replaced by the above upper bound implicitly lower bounds M . Notice that this p implies σ ≥ 3/ ln M since three times the above upper bound is at least 3B ≥ 1/2 for σ = 3/ ln M . So, we do not need to repeat this condition in our first main result. Also the condition M ≥ 3 is implicitly satisfied (M = 1 leads to µ = ∞; M = 2 implies that three times the 2 2 2 above upper bound is equal to 3Be3/(2σ ) (1 + 4e−3/σ )/(1 − e−1/σ )3/2 ≥ 3B ≥ 1/2). □

E

Parameter Sensitivity (Berry–Esseen Track)

Figure 3 reports the required number of rounds M as a function of the noise multiplier σ, for three target privacy levels δ ∈ {10−2 , 10−3 , 10−4 } at E = 1. The curves invert the two-term closed-form lower bound on δ from Theorem 4.1, which agrees with the full theorem-solve to within ∼ 0.1% across the σ shown (cf. Table 1). All curves exhibit a U-shape, with the minimum near σ ≈ 1. 25

F

Edgeworth Expansion

The Berry-Esseen theorem provides an upper bound on the speed of convergence of the normalized mean of random variables to a normal distribution which only depends on the starting distribution F = F1 through the first two moments and third absolute moment. The Edgeworth expansion provides a better asymptotic estimate, which we will use for our asymptotic analysis. The speed of convergence depends in a complex way on F (not only on the moments of F ) and cannot be used to obtain concrete (non-asymptotic) convergence results for smaller n. We notice that all moments µk , k ≥ 1, exist for the lognormal distribution (in which we are interested for our hypothesis testing problem). Also the lognormal distribution has a characteristic function ϕ(ξ) with the property that its limit for ξ → ±∞ tends to zero, see Chapter XV in [14], and for this reason the Edgeworth expansion of the lognormal distribution exists, see Chapter XVI in [14], in particular Theorem 3 on page 515 (which requires µ1 = 0 and µ2 = σ̄ 2 ). For the construction of polynomials Rk (x), pages 505-506 define Hermite polynomials Hk (x) and polynomials Pk (x) are defined/constructed on pages 508-509 which needs Lemma 2 of page 485 for ξ = 0. We only need the Edgeworth expansion for two terms: Let F (x) be a cumulative distribution for which all moments µk , k ≥ 1, exist with µ1 = 0. Suppose that the corresponding characteristic function ϕ(ξ) tends to 0 for ξ → ±∞. Let X1 , X2 , . . . be i.i.d. random variables with cumulative distribution F (x). By using E[X1 ] = µ1 = 0 and E[X12 ] = µ2 = σ̄ 2 > 0, define the standardized sum (as before) Sn =

X1 + · · · + Xn √ , σ̄ n

Fn (x) = P(Sn ≤ x).

Write

µ3 µ4 − 3σ̄ 4 , λ4 = , 3 σ̄ σ̄ 4 where µk = E[X1k ] are central moments because E[X1 ] = 0. As n → ∞,    λ3 1 λ4 λ2 Fn (x) = Φ(x)+n(x) √ (1 − x2 ) + (3x − x3 ) + 3 (−x5 + 10x3 − 15x) +o(n−1 ) n 24 72 6 n (44) with convergence uniformly in x. λ3 =

For compact notation define λ3 λ4 µ4 − 3µ22 µ3 cn = √ = and dn = = . √ 3/2 24n 24µ22 n 6 n 6µ n

(45)

2

Then (44) is   c2n 2 3 5 3 Fn (x) = Φ(x) + n(x) cn (1 − x ) + dn (3x − x ) + (−x + 10x − 15x) + o(n−1 ). (46) 2 For ease of readability, we repeat Theorem 5.1: Let pn (x)

=

x + cn (1 − x2 ) + dn (3x − x3 ) + c2n (4x3 − 7x)

with cn and dn as defined by (45). Let 1 ≤ κn = o(n1/16 ). Then, restricted to |x| ≤ κn and for sufficiently large n, polynomial pn (x) is strictly increasing and invertible. Furthermore, for n → ∞ Φ(pn (x))

=

Fn (x) + o(1/n)

uniformly in |x| ≤ κn . The theorem states that for 1 ≤ κn = o(n1/16 ), we have the property that for all ϵ > 0, there exists an Nϵ such that for all n ≥ Nϵ and for all |x| ≤ κn , we have |Fn (x) − Φ(pn (x))| ≤ ϵ/n. The convergence rate in terms of Nϵ depends in a complex way on distribution F (and not just on its moments). 26

We will fix ϵ > 0 and write ϵn = ϵ/n. We have for n ≥ Nϵ and |x| ≤ κn Fn (x) = Φ ◦ pn (x) + ϵn (x),

(47)

where ϵn (x) indicates an error term whose absolute value is ≤ ϵn . In order to make (47) exact, ϵn (x) is a function of x. However, we will only work with the ϵn as an upper bound of the absolute value of ϵn (x). For this reason, we will simply write ϵn and remember that it indicates some suitable value whose absolute value is at most ϵn . Writing +ϵn or −ϵn will therefore have the same meaning. Furthermore, we will write |ϵn | to mean the upper bound on the absolute value of ϵn . So, we replace ϵn (x) by ϵn and replace ϵn by |ϵn | in our notation. We have −1 1 − a = Fn (x) ⇒ x = p−1 (1 − a − ϵn ). n ◦Φ

Notice that the Berry-Esseen theorem yields the same result, but for √ E[|X|3 ] Nϵ = 1, κn = ∞, pn (x) = x, ϵn = B · √ = O(1/ n). 3/2 n · µ2 Proof: First, p′n (x) = 1 − 2cn x + dn (3 − 3x2 ) + c2n (12x2 − 7).

(48)

Because cn = O(n−1/2 ), dn = O(n−1 ), and κn = o(n1/16 ), uniformly for |x| ≤ κn , p′n (x) = 1 + O(n−1/2 κn + n−1 κ2n ) = 1 + o(1). Thus p′n (x) > 0 on [−κn , κn ] for all sufficiently large n. Set un (x) = pn (x) − x = cn (1 − x2 ) + dn (3x − x3 ) + c2n (4x3 − 7x). Uniformly for |x| ≤ κn , un (x) = O(n−1/2 κ2n + n−1 κ3n ) = O(n−3/8 ) = o(1). Taylor’s theorem gives, for some ξ between x and x + un (x), Φ(pn (x))

=

Φ(x + un (x))

=

Φ(x) + un (x) · n(x) −

un (x)2 un (x)3 · xn(x) + · (ξ 2 − 1)n(ξ). 2 6

(49)

The function (ξ 2 − 1)n(ξ) is bounded on R. Also, uniformly for |x| ≤ κn , |un (x)|3 = O((n−3/8 )3 ) = O(n−9/8 ) = o(n−1 ). Hence the third-order remainder in (49) is o(n−1 ). Next, uniformly on |x| ≤ κn , x un (x)2 − c2n (1 − x2 )2

=

x 2cn (1 − x2 ) · [dn (3x − x3 ) + c2n (4x3 − 7x)] + [dn (3x − x3 ) + c2n (4x3 − 7x)]2

=

O(n−3/2 κ6n + n−2 κ7n ) = o(n−1 ).

Therefore −

c2 un (x)2 x = − n x(1 − x2 )2 + o(n−1 ). 2 2

Substituting this into (49), "

# 2 c Φ(pn (x)) = Φ(x) + n(x) cn (1 − x2 ) + dn (3x − x3 ) + c2n (4x3 − 7x) − n x(1 − x2 )2 + o(n−1 ). 2 27

The c2n -coefficient simplifies to the corrected Edgeworth polynomial: 4x3 − 7x −

x(1 − x2 )2 x − 2x3 + x5 = 4x3 − 7x − 2 2 x5 15x 3 = − + 5x − 2 2 1 5 3 = (−x + 10x − 15x). 2

Consequently,   c2 Φ(pn (x)) = Φ(x) + n(x) cn (1 − x2 ) + dn (3x − x3 ) + n (−x5 + 10x3 − 15x) + o(n−1 ). 2 Comparing this with (46) proves the theorem.

□

Notice that for the lognormal distribution that we study, see Proposition C.2, we have p µ3 1 1/σ 2 √ √ cn = = (e + 2) e1/σ2 − 1, 6σ̄ 3 · n 6 n µ4 − 3σ̄ 4 dn = 24σ̄ 4 · n  2 2 1  4/σ2 = e + 2e3/σ + 3e2/σ − 6 24n   2 2 2 1  1/σ2 e − 1 e3/σ + 3e2/σ + 6e1/σ + 6 . = 24n Also, notice that the ratio    1 1/σ 2 3/σ 2 2/σ 2 1/σ 2 e − 1 e + 3e + 6e + 6 24n dn =

1 1/σ 2 + 2 2 e1/σ 2 − 1 c2n 36n e   2 2 2 3 e3/σ + 3e2/σ + 6e1/σ + 6 . =
2 2 e1/σ2 + 2 In our asymptotic analysis we consider σ to be a constant independent of n = M . So, σ is not a function of M as this would change the asymptotic behavior of cM and dM .

G

Trade-Off Function via Edgeworth Expansion

G.1

False Positive Rate

We are ready to analyze α(h) of (7) with the probability density of (xj )M j=1 conditioned on d defined by (5). By using the definition of ȲM in (11) with the Yj defined in (9) and by using approximation (47) derived from Theorem 5.1 we obtain α(h)

= =

P[ȲM > h] = 1 − P[ȲM < h] r M 1 − Φ ◦ pM ((h − 1) · ) − ϵM (h), e1/σ2 − 1

for

r

r e1/σ2 − 1 e1/σ2 − 1 h ∈ [1 − κM · , 1 + κM · ] (50) M M such that the argument of Φ ◦ pM has an absolute value ≤ κM with κM = o(M 1/16 ) as defined in Theorem 5.1. Notice that ϵM (h) = o(1/M ) uniformly in h satisfying range (50). For the inverse α−1 (a) = h we derive r α

−1

−1 (a) = h = 1 + p−1 (1 − a − ϵM (h)) · M ◦Φ

28

e1/σ2 − 1 . M

(51)

Here, we need

−1 |p−1 (1 − a − ϵM (h))| ≤ κM (52) M ◦Φ in order to fit the range (50) for h. Proposition G.1. There exists an ϵM (h) with ϵM (h) = o(1/M ) uniformly in h satisfying range (50) such that the following holds:

(a) If h satisfies range (50), then r α(h) = 1 − Φ ◦ pM ((h − 1) ·

M ) − ϵM (h). e1/σ2 − 1

(b) Let |ϵM | = o(1/M ) indicate the supremum of values |ϵM (h)| for h in range (50). If M is large enough and √ √ a ∈ [M −1 / 4π ln M + |ϵM |, 1 − M −1 / 4π ln M − |ϵM |], then, for α(h) = a (the p false positive rate as defined by (7)), the solution h satisfies range (50) with κM replaced by κ′M = 2(1 + γ) ln M (and the above equation for α(h) holds). (c) Furthermore, let γ > 0 be a constant, then the inverse h = α−1 (a) satisfies r e1/σ2 − 1 −1 −1 −1 α (a) = 1 + pM ◦ Φ (1 − a − ϵM (h)) · , M where p −1 |p−1 (1 − a − ϵM (h))| ≤ 2(1 + γ) ln M . M ◦Φ Hence, h = α−1 (a) is in range (50) with κM replaced by κ′M . Proof: In our proof we need (52) to be more restrictive and for this reason we require −1 |p−1 (1 − a − ϵM (h))| ≤ κ′M ≤ κM M ◦Φ

for some suitable κ′M . Since pM (x) is increasing, the tighter bound is equivalent to |Φ−1 (1 − a − ϵM )| ≤ pM (κ′M ), which is implied by a ∈ [Φ(−pM (κ′M )) + |ϵM |, 1 − Φ(−pM (κ′M )) − |ϵM |]. We use

p κ′M = 2(1 + γ) ln M for some small constant γ > 0 and notice that

(53)

pM (κ′M ) = κ′M − κ′′M , where by Theorem 5.1 and equations (50) and (50), x + cn (1 − x2 ) + dn (3x − x3 ) + c2n (4x3 − 7x) κ′′M

2

3

3

cM · (κ′M − 1) + dM · (κ′M − 3κ′M ) − c2M · (4κ′M − 7κ′M ) ln M 2 3 3 = O(cM κ′M + dM κ′M + c3M κ′M ) = O( √ ). M √ ′ ′ ′′ This shows that for M large enough pM (κM ) = κM − κM ≥ 2 ln M . We apply the upper bound √ 2 Φ(−t) ≤ e−t /2 /( 2π · t) and obtain √ e− ln M Φ(−pM (κ′M )) ≤ Φ(− 2 ln M ) ≤ √ 4π ln M √ = M −1 / 4π ln M = o(1/M ). =

Hence, for α−1 (a) we restrict ourselves to the range √ √ a ∈ [M −1 / 4π ln M + |ϵM |, 1 − M −1 / 4π ln M − |ϵM |]. And for such a, α−1 (a) is in the range (50) with κM replaced by κ′M . 29

□

G.2

False Negative Rate

Proposition D.3 states that the false negative rate β(h) as defined by (8) is equal to the integral Z σ ln(M h)−1/(2σ) Z PM xj /σ−1/(2σ2 ) β(h) = 1 < z=−∞ j=2 e M −1 : (xj )M 2 j=2 1 (h − M · ez/σ+1/(2σ ) ) · MM−1 2 2 M Y e−z /2 e−xi /2 √ dx2 · · · dxM · √ dz. 2π 2π i=2

Proposition G.1 suggests that the inner multi-dimensional integral is equal to 2

ez/σ+1/(2σ ) M 1 − α(h · − ) M −1 M −1 r 2 M ez/σ+1/(2σ ) M −1 ) = Φ ◦ pM −1 ((h · − − 1) · M −1 M −1 e1/σ2 − 1 +ϵM −1 ,

(54)

where ϵM −1 is ϵM −1 (x) for x equal to the argument of α. This only holds true if the argument of α satisfies range (50). We first note that we will want to compute the trade-off function f (a) = β(α−1 (a)) and therefore we will restrict our evaluation of β(h) to the range (50) with κM replaced by κ′M as defined in (53) and in Proposition G.1. For z → −∞, we have that the argument of α(.) tends to its supremum hM/(M − 1). We need to check that hM/(M − 1) fits range (50) with κM for h fitting range (50) with κM replaced by κ′M . We first want to verify whether the upper bound r r M M e1/σ2 − 1 e1/σ2 − 1 ′ ·h≤ · (1 + κM · ) ≤ 1 + κM · , (55) M −1 M −1 M M p holds for M large enough with κ′M = 2(1 + γ) ln M . Since Theorem 5.1 holds for any κM = o(M 1/16 ) we have the liberty to use the next explicit definition for κM : We fix some constant γ ′ > 0 and define ′ M (M 1/16−γ + κ′M ) = o(M 1/16 ). (56) κM = M −1 This choice satisfies (55). Let us restrict z in the inner multi-dimensional integral to z ≤ σ ln(M (h − q)) −

1 2σ

(57)

for r M −1 e1/σ2 − 1 q= · (1 − κM · ). M M With this restriction on z, the argument of α is equal to 2

h·

M ez/σ+1/(2σ ) − M −1 M −1

≥ =

(58)

M M (h − q) − M −1 M −1 r M e1/σ2 − 1 = 1 − κM · . q· M −1 M h·

This means that for z satisfying (57), the argument of α fits range (50) with κM . We conclude that the inner multi-dimensional integral is equal to (54) for all z satisfying (57) with h satisfying range (50) with κM replaced by κ′M . 30

Proposition G.2. There exists an ϵM (h) = o(1/M ) uniformly in h satisfying range (50) with κM replaced by κ′M , see (53) and (56) for their definitions, such that the false negative rate β(h) as defined by (8) for h in this range is equal to β(h) = Z σ ln(M (h−q))−1/(2σ)

r 2 2 M ez/σ+1/(2σ ) M −1 e−z /2 √ Φ ◦ pM −1 ((h · − − 1) · ) · dz M −1 M −1 e1/σ2 − 1 2π z=−∞ Z Z σ ln(M h)−1/(2σ) PM xj /σ−1/(2σ2 ) ±|ϵM −1 | + 1 < z=σ ln(M (h−q))−1/(2σ) (x )M : M −1 j=2 e j j=2 1 z/σ+1/(2σ 2 ) ) · MM−1 (h − M · e 2 2 M Y e−xi /2 e−z /2 √ dx2 · · · dxM · √ dz, 2π 2π i=2

where q satisfies (58). The proposition implies that for all h in range (50) with κM replaced by κ′M , r Z +∞ 2 2 ez/σ+1/(2σ ) M −1 e−z /2 M √ − − 1) · ) · dz| ≤ ϵ′ , |β(h) − Φ ◦ pM −1 ((h · 2 M −1 M −1 e1/σ − 1 2π −∞ with

ϵ′ ≤ |ϵM −1 | + Φ(−(σ ln(M (h − q)) − 1/(2σ))).

Since h satisfies (50) for κM replaced by κ′M , r

e1/σ2 − 1 M h − (M − 1)(1 − κM · ) M r e1/σ2 − 1 ≥ M (1 − κ′M · ) Mr e1/σ2 − 1 −(M − 1)(1 − κM · ) rM 2 e1/σ − 1 ≥ ((M − 1)κM − M κ′M ) · . M For κM and κ′M defined by (53) and (56), M (h − q)

=

′

(M − 1)κM − M κ′M = M 17/16−γ .

√ By substituting σ = s/ ln M we have p p ′ ′ M (h − q) ≥ M 17/16−γ M 1/s2 − 1/M 1/2 = M 9/16−γ M 1/s2 − 1. ′

2

This is at least M 9/16−γ +1/(2s ) /e for M large enough and we have σ ln(M (h − q)) − 1/(2σ) ≥ =

σ(9/16 − γ ′ + 1/(2s2 )) ln M − σ − 1/(2σ) √ s . (9/16 − γ ′ )s ln M − √ ln M

Notice that Φ(−(σ ln(M (h − q)) − 1/(2σ)) √ √ ≤ Φ(−((9/16 − γ ′ ) ln M − 1/ ln M ) · s) 2

≤

e−t /2 √ t · 2π

=

M −(9/16−γ ) s /2 e(9/16−γ )s e−s /(2 ln M ) √ √ √ ((9/16 − γ ′ ) 2π ln M − 2π/ ln M )s

√ √ t=((9/16−γ ′ ) ln M −1/ ln M )·s ′ 2 2

′

31

2

2

The exponent of M is

−(9/16 − γ ′ )2 s2 /2 ≤ −1

for

√ s > 16 2/(9 − 16γ ′ ) ≈ 2.514 (rearranging terms leads to a quadratic equation in s which we solve for γ ′ → 0+ ; a larger γ ′ implies a larger lower bound on s). We have ϵ′ ≤ |ϵM −1 | + Φ(−(σ ln(M (h − q)) − 1/(2σ)) = o(1/M ). We may push this inside ϵM −1 = o(1/M ).

√ Proposition G.3. For M large enough, we have σ = s/ ln M for some s > 2.514. Then, uniformly for h in range (50) with κM replaced by κ′M , see (53) and (56) for their definitions, r Z +∞ 2 2 e−z /2 M ez/σ+1/(2σ ) M −1 √ ) · |β(h) − Φ ◦ pM −1 ((h · − − 1) · dz| = o(1/M ). M −1 M −1 e1/σ2 − 1 2π −∞ G.3

Trade-Off Function

In order to compute trade-off function f (a) we substitute h = α−1 (a) in Proposition G.3 with α−1 (a) approximated by (51), see Proposition G.1(c). After reordering terms, this yields Z +∞ f (a) = Φ ◦ pM −1 ( −∞ −1 p−1 (1 − a − ϵM (h)) · M ◦Φ

r

2

M ez/σ+1/(2σ ) − 1 √ −√ M −1 M − 1 e1/σ2 − 1

2

e−z /2 )· √ dz + o(1/M ) 2π

(59)

uniformly for a in the range given by Proposition G.1(b). Let −1 p−1 (1 − a − ϵM ), M ◦Φ r M ϵ = x·( − 1), M −1

x

=

µ(z)

=

2

ez/σ+1/(2σ ) − 1 √ . √ M − 1 e1/σ2 − 1

This notation simplifies (59) to Z +∞ 2 e−z /2 f (a) = dz + o(1/M ). Φ ◦ pM −1 (x + ϵ − µ(z)) · √ 2π −∞

(60)

(61)

The remainder of Appendix G.3 proves the next proposition. Proposition G.4. There exists a range [o(1/M ), 1 − o(1/M )] such that for a in this range, there √ exists a bounded 1/ 2πe ≥ ϵ ≥ 0 such that 2

f (a) = Gµ+O( √ln M ) (a + o(1/M )) − M

e2/σ · ϵ · sign(1/2 − a + o(1/M )) + o(1/M ), 2(M − 1)

where

s µ=

e1/σ2 − 1 . M −1

For a ≥ 1/2, the term with ϵ is at least zero and we have f (a) ≥ Gµ+O( √ln M ) (a + o(1/M )) + o(1/M ). M

In general, for all a ∈ [o(1/M ), 1 − o(1/M )], we have f (a) = Gµ+O( √ln M ) (a + o(1/M )) + O(1/M ). M

32

p Proof: Proposition G.1(c) states |x| ≤ κ′M = 2(1 + γ) ln M . Furthermore, p r √ (1 + γ) ln M M ln M |x| κ′M = O( |ϵ| = |x · ( − 1)| ≤ ≤ = √ ). (62) M −1 2(M − 1) 2(M − 1) M 2(M − 1) Notice that there exists a ξ ∈ [x − |ϵ| − |µ(z)|, x + |ϵ| + |µ(z)|] such that pM −1 (x + ϵ − µ(z)) = pM −1 (x) − (µ(z) − ϵ) · p′M −1 (ξ), √ √ where, see (48) and (50) together with cM −1 = O(1/ M ), dM −1 = O(1/M ), and |x| = O( ln M ) (and |ϵ| = O(|x|)), p′M −1 (ξ)

=

1 − 2cM −1 ξ + dM −1 (3 − 3ξ 2 ) + c2M −1 (12ξ 2 − 7)

=

1 + O(cM −1 (|x| + |µ(z)|) + (dM −1 + c2M −1 )(|x| + |µ(z)|)2 ) √ ln M |µ(z)| |µ(z)|2 + √ + 1 + O( √ ). M M M

= This shows that

pM −1 (x + ϵ − µ(z)) = pM −1 (x) − µ(z) + ϵ(z)

(63)

with

√ ln M |µ(z)| |µ(z)|2 + √ + )) |ϵ(z)| = O(|ϵ| + (|ϵ| + |µ(z)|)( √ M M M √ √ √ ln M |µ(z)| · ln M |µ(z)|2 · ln M = O( + + M √ M2 M 3/2 2 3 |µ(z)| |µ(z)| |µ(z)| · ln M √ + √ + ). (64) + M M M Later in our analysis we will use that the integral of |ϵ(z)| over √ z with respect to the normal distribution replaces (we use (60) with (10)) each term |µ(z)| with O(1/ M ). This gives √ Z +∞ 2 e−z /2 ln M |ϵ(z)| · √ dz = O( ). (65) M 2π −∞

After establishing (61) and obtaining equation (63), we now want to compute pM −1 (x). The definition of pM −1 (x) and pM (x) tells us that their difference is |pM −1 (x) − pM (x)| = O(

1 + |x|2 |x| + |x|3 ). + 3/2 M2 M

Notice that

pM (x) = y with y = Φ−1 (1 − a − ϵM (h)). √ ′ Together with |x| ≤ κM = O( ln M ) this shows ln M ). M 3/2 We may merge this error term into ϵ(z) without affecting the properties (64) and (65). This yields a refinement of equation (63), pM −1 (x + ϵ − µ(z)) = y − µ(z) + ϵ(z) with y = Φ−1 (1 − a − ϵM (h)). Substituting this into (61) yields Z +∞ 2 e−z /2 f (a) = Φ(y + ϵ(z) − µ(z)) · √ dz + o(1/M ). (66) 2π −∞ |pM −1 (x) − y| = |pM −1 (x) − pM (x)| = O(

Now we use a Taylor series expansion around y: There exists a ξ between y + ϵ(z) − µ(z) and y such that Φ(y − (µ(z) − ϵ(z))) (µ(z) − ϵ(z))2 = Φ(y) − (µ(z) − ϵ(z)) · n(y) − · yn(y) 2 3 (µ(z) − ϵ(z)) − · (ξ 2 − 1)n(ξ). (67) 6 33

We compute the integral in (66) with respect to each of these terms. We have, see (65) and (10), Z +∞ 2 e−z /2 dz (µ(z) − ϵ(z)) · √ 2π −∞ Z +∞ Z +∞ 2 2 2 ez/σ+1/(2σ ) − 1 e−z /2 e−z /2 √ √ √ (√ ) · ϵ(z) · = dz − dz 2π 2π M − 1 e1/σ2 − 1 −∞ −∞ s e1/σ2 − 1 = µ − ρ with µ = (68) M −1 √ Z +∞ 2 e−z /2 ln M ϵ(z) · √ dz = O( ). and ρ = M 2π −∞ In addition, we derive Z +∞

2

(µ(z) − ϵ(z))2 e−z /2 · √ dz 2 2π −∞ Z +∞ Z +∞ 2 2 µ(z)2 e−z /2 ϵ(z)2 − 2µ(z)ϵ(z) e−z /2 · √ dz + · √ dz, = 2 2 2π 2π −∞ −∞

where, after grouping terms and applying (10) for b = ∞, c = −1 and k = 0, 1 and 2, Z +∞ Z +∞ 2z/σ+2/(2σ2 ) 2 2 2 µ(z)2 e−z /2 e − 2ez/σ+1/(2σ ) + 1 e−z /2 · √ dz = dz · √ 2 2(M − 1)(e1/σ2 − 1) 2π 2π −∞ −∞ 2

2

2

2

=

e3/σ − 2e1/σ + 1 e2/σ + e1/σ − 1 = 2 1/σ 2(M − 1) 2(M − 1)(e − 1)

=

µ2 e2/σ + 2(M − 1) 2

2

(69)

and, see (65) and applying the technique of its derivation, √ Z +∞ 2 |ϵ(z)|2 − 2|µ(z)| · |ϵ(z)| e−z /2 ln M dz = O( 3/2 ). · √ 2 M 2π −∞ Similar to the derivation above, Z +∞ 2 (|µ(z)| + |ϵ(z)|)3 e−z /2 dz = O(1/M 3/2 ). · √ 6 2π −∞

(70)

(71)

We notice that |(ξ 2 − 1)n(ξ)| is bounded by a constant and also yn(y) is bounded by a constant. Therefore, combining (66) with equations (67), (68), (69), (70) and (71) gives ! 2 µ2 e2/σ f (a) = Φ(y) − (µ − ρ) · n(y) − + · yn(y) + o(1/M ). 2(M − 1) 2 We observe that this looks similar to the Taylor series expansion (µ − ρ)2 (µ − ρ)3 · yn(y) − · (ξ 2 − 1)n(ξ) 2 6 √ √ for some ξ between y and y − (µ − ρ). Since ρ = O( ln M /M ) and µ = O(1/ M ), we have √ µ2 ln M Φ(y − (µ − ρ)) = Φ(y) − (µ − ρ) · n(y) − · yn(y) + O( 3/2 ). 2 M Φ(y − (µ − ρ)) = Φ(y) − (µ − ρ) · n(y) −

This proves our final expression for f (a): √ f (a) = Φ(y − (µ + O(

2

ln M e2/σ ))) − · yn(y) + o(1/M ). M 2(M − 1) 34

Notice that for y = Φ−1 (1 − a − ϵM (h)), there exists a range a ∈ [o(1/M ), 1 − o(1/M )] that fits the range√ given by Proposition G.1(b) and for which sign(y) = sign(1/2 − a). Furthermore |yn(y)| ≤ 1/ 2πe. Substituting y = Φ−1 (1 − a − ϵM (h)) and noting that ϵM (h) = o(1/M ) yields an approximation of the Gaussian trade-off function: There exists a range √ [o(1/M ), 1 − o(1/M )] such that, for all a in this range, there exists a small bounded constant 1/ 2πe ≥ ϵ ≥ 0 such that √ f (a)

=

−1

Φ(Φ

(1 − a − o(1/M )) − (µ + O(

ln M ))) M

2

−

e2/σ · ϵ · sign(1/2 − a) + o(1/M ) 2(M − 1) 2

=

Gµ+O( √ln M ) (a + o(1/M )) − M

e2/σ · ϵ · sign(1/2 − a − o(1/M )) + o(1/M ). 2(M − 1)

Notice that for a ≥ 1/2 + o(1/M ) (we have y ≤ 0; the o(.) terms are sign agnostic) this is lower bounded by Gµ+O( √ln M ) (a + o(1/M )) + o(1/M ). M

□ G.4

Multiple Epochs and Proof of Theorem 5.2

We first prove an auxiliary lemma which we use in the proof of Theorem 5.2. Lemma G.5 is a generic property of symmetric convex trade-off functions, applicable beyond the random-shuffling setting. Lemma G.5. Let f and g be convex, continuous, decreasing and symmetric (that is, g = g −1 with the inverse g −1 defined as g −1 (a) = inf{t ∈ [0, 1] : g(t) ≤ a} for a ∈ [0, 1]) trade-off functions. In addition g is strictly decreasing over the whole interval a ∈ [0, 1]. Let a∗ = g(a∗ ) be the fixed point of g. Suppose that there exists a 0 < δ < a∗ such that f (a) ≥ g(a + δ) − δ for a ∈ [a∗ − δ, 1 − δ]. Define h(a) = max{g(a + δ) − δ, 0}. Let δ̂ = max{δ/a∗ , (1 − g(δ)) + δ}. Define ( k(a) =

a (1 − δ̂)g( 1− ) δ̂

if a ≤ 1 − δ̂,

0

if a ≥ 1 − δ̂.

Then, both h and k are convex, continuous, decreasing and symmetric trade-off functions and f (a) ≥ h(a) ≥ k(a) = (g ⊗ f0,δ̂ )(a) for a ∈ [0, 1], where f0,δ̂ (a) = max{1 − a − δ̂, 0} is the trade-off function of two uniform distributions T (U (0, 1), U (δ̂, 1 + δ̂)). Proof: The lemma assumes δ < a∗ , where a∗ is the unique fixed point of g, i.e., g(a∗ ) = a∗ . Since g is decreasing, this implies g(δ) − δ ≥ g(a∗ ) − δ = a∗ − δ > 0. We have that both values in the max definition of δ̂ are < 1 and function k is well defined. In addition, we have h(0) = g(δ) − δ > 0. Since g is a trade-off function less than the random guessing diagonal a → 1 − a, h(0) = g(δ) − δ ≤ 1 − δ − δ ≤ 1 and we have that h is well-defined. Since g is convex and decreasing, both h and k are convex and decreasing. 35

Notice that a ≤ g(δ) − δ if and only if a + δ ≤ g(δ) if and only if g(a + δ) ≥ g(g(δ)) since g is strictly decreasing. Since g is also symmetric (which implies that g 2 is the identity function), g(g(δ)) = δ. For this reason  g(a + δ) − δ if a ≤ g(δ) − δ, h(a) = (72) 0 if a ≥ g(δ) − δ. Let us compute h(h(a)). Since h is decreasing, we have h(a) ≤ h(0) = g(δ) − δ and from (72) we infer that h(h(a)) = g(h(a) + δ) − δ. If a ≤ g(δ) − δ = h(0), then h(h(a)) = g(h(a) + δ) − δ = g(g(a + δ) − δ + δ) − δ = g(g(a + δ)) − δ = a + δ − δ = a. This proves for a ≤ h(0), h−1 (a) = inf{t ∈ [0, 1] : h(t) ≤ a} = inf{t ∈ [0, 1] : h(t) ≤ h(h(a))} = h(a) (since h is strictly decreasing for a ≤ g(δ) − δ = h(0)). If a ≥ g(δ) − δ = h(0), then t = 0 realizes the infinum h−1 (a) = inf{t ∈ [0, 1] : h(t) ≤ a} = 0 which is equal to h(a) since a ≥ g(δ) − δ. This proves that h = h−1 is also symmetric. A similar analysis shows that, besides being convex, continuous and decreasing, k is also a symmetric trade-off function. In addition, k is equal to g ⊗ f0,δ̂ , where f0,δ̂ is the trade-off function of two uniform distributions T (U (0, 1), U (δ̂, 1 + δ̂)), see Section 3.3 in [8]. The lemma assumes that f is a symmetric trade-off function with lower bound f (a) ≥ h(a) for a ∈ [a∗ − δ, 1 − δ]. Since f is symmetric, it is also lower bounded by the symmetric complement h−1 (a) (which is equal to h(a)) for the range a ∈ [h(1 − δ), h(a∗ − δ)]. We first notice that 1 − δ ≥ g(δ) − δ and (72) implies h(1 − δ) = 0. Second, since g is decreasing, a∗ is a fixed point of g, and δ < a∗ , g(δ) − δ ≥ g(a∗ ) − δ = a∗ − δ. Hence, (72) implies that h(a∗ − δ) = g(a∗ − δ + δ) − δ = a∗ − δ. This proves that a∗ − δ is the unique fixed point of h and also proves that the two ranges [a∗ − δ, 1 − δ] and [h(1 − δ), h(a∗ − δ)] = [0, a∗ − δ] combine: f (a) ≥ h(a) for a ∈ [0, 1 − δ]. Again notice that 1 − δ ≥ g(δ) − δ and h(1 − δ) = 0. By the definition of h, see (72), we have that f (a) ≥ h(a) for a ∈ [0, 1] for the full range. We already derived that a∗ −δ is the fixed point of h. Since a∗ (1− δ̂) ≤ 1− δ̂, we have k(a∗ (1− δ̂)) = (1 − δ̂)g(a∗ ) = a∗ (1 − δ̂). Hence, a∗ (1 − δ̂) is a fixed point of k. Since δ̂ is defined as a value ≥ δ/a∗ , we have that the fixed point of k is smaller than the fixed point of h: δ̂ ≥ δ/a∗ if and only if a∗ (1 − δ̂) ≤ a∗ − δ.

(73)

The fixed points of the symmetric, convex, decreasing trade-off functions h and k define the intersection of the diagonal line a → a with the trade-off functions and denote the points on the trade-off functions that are farthest away from the random guessing diagonal a → 1 − a. Condition (73) implies that function k is smaller than h when considering the fixed points along the diagonal a → a. In particular, since h and k are decreasing, convex and symmetric, we have that h(a∗ (1 − δ̂)) ≥ k(a∗ (1 − δ̂)).

(74)

If we are able to prove that h(a) ≥ k(a) for a ∈ [0, a∗ (1 − δ̂)] or, equivalently, for a at most the value of k’s fixed point, then by symmetry and convexity of h and k, we have that h(a) ≥ k(a) for all a ∈ [0, 1]. Let a ∈ [0, a∗ (1 − δ̂)]. Then we have a ≤ a∗ (1 − δ̂) ≤ a∗ − δ ≤ g(δ) − δ (since a∗ = g(a∗ ) ≤ g(δ) because g is decreasing and δ ≤ a∗ ). From (72) we infer h(a) = g(a + δ) − δ. Also, a ≤ a∗ (1 − δ̂) ≤ 1 − δ̂, hence, k(a) = (1 − δ̂)g(a/(1 − δ̂)). We need to prove h(a) = g(a + δ) − δ ≥ (1 − δ̂)g(a/(1 − δ̂)) = k(a) for 0 ≤ a ≤ a∗ (1 − δ̂). 36

(75)

By the definition of δ̂, δ̂ ≥ (1 − g(δ)) + δ from which we obtain h(0) = g(δ) − δ ≥ 1 − δ̂ = k(0) showing (75) for a = 0. Together with (74) we conclude that (75) is satisfied for its end points a = 0 and a = a∗ (1 − δ̂). If h′ (a) ≥ k ′ (a) for a ∈ [0, x], then together with h(0) ≥ k(0) this implies h(a) ≥ k(a) for a ∈ [0, x]. Similarly, if h′ (a) ≤ k ′ (a) for a ∈ [x, a∗ (1 − δ̂)], then together with h(a∗ (1 − δ̂)) ≥ k(a∗ (1 − δ̂)) this implies h(a) ≥ k(a) for a ∈ [x, a∗ (1 − δ̂)]. We have h′ (a)

=

g ′ (a + δ),

k ′ (a)

=

g ′ (a/(1 − δ̂)).

Since g is convex, we have g ′′ ≥ 0 which implies that g ′ (a + δ) ≥ g ′ (a/(1 − δ̂)) if and only if a + δ ≥ a/(1 − δ̂). This means that h′ (a) ≥ k ′ (a) if and only if a ∈ [0, δ(1 − δ̂)/δ̂]. This shows that there indeed exists an x = min{δ(1 − δ̂)/δ̂, a∗ (1 − δ̂)} fitting the above argument. We conclude that h(a) ≥ k(a) for a ∈ [0, 1]. □ In order to characterize δ̂ when applying Lemma G.5 in our proof of Theorem 5.2, we need the next two properties: √ Proposition G.6. Let µ = O(1/ M ). (i) Let a = O(1/M ), then 1 − Gµ (a) = O(a). This is O(1/M ) and is o(1/M ) for a = o(1/M ). (ii) Let Gµ (a∗ ) = a∗ , then a∗ = Φ(−µ/2) = 21 − √µ8π + O(M −3/2 ). Proof: We rewrite 1 − Gµ (a) = 1 − Φ(Φ−1 (1 − a) − µ) = Φ(−(Φ−1 (1 − a) − µ)) = Φ(Φ−1 (a) + µ)). Since Φ is increasing, also Φ−1 is increasing and (30) implies ! ! r r 2 −t2 /2 2 −t2 /2 1 1 −1 −1 √ p e < −t ≤ Φ e . Φ t + t2 + 4 π t + t2 + 8/π π For t implicitly defined as the solution of 1 √ a= t + t2 + 4

r

2 −t2 /2 e , π

(76)

we have Φ−1 (a) ≤ −t. This implies (we use (30) and (76)) Φ(Φ

−1

(a) + µ)

≤ = ≤

Φ(−t + µ) = Φ(−(t − µ)) ≤

1 p (t − µ) + (t − µ)2 + 8/π

√ 2 t + t2 + 4 p eµt e−µ /2 (t − µ) + (t − µ)2 + 8/π 2t + 2 µt a· e . 2(t − µ)

r

2 −(t−µ)2 /2 e π

a·

Notice that, by rearranging (76), v r ! s u   u 1 1 1 2 1 t √ √ · t = 2 ln · ≤ 2 ln · . a t + t2 + 4 π a 2π t

(77)

Since a√= O(1/M ), the corresponding t of (76) cannot remain bounded. Thus, for M large enough, t ≥ 1/ 2π, and (77) implies p t ≤ 2 ln(1/a). 37

Moreover, since

√

t2 + 4 ≤ t + 2 for t ≥ 0, we have p p t + t2 + 4 ≤ 2t + 2 ≤ 2 2 ln(1/a) + 2.

Therefore, using the exact identity above once more, v r ! u u 1 2 1 t · t ≥ 2 ln · p . a 2 2 ln(1/a) + 2 π For a = O(1/M ), these upper and lower bounds imply √ t = Θ( ln M ). √ Together with µ = O(1/ M ) we get 1 − Gµ (a) = Φ(Φ−1 (a) + µ) ≤ a ·

2t + 2 µt e = O(a). 2(t − µ)

This proves the first property. For the second property we observe a∗ = Gµ (a∗ ) = Φ(Φ−1 (1 − a∗ ) − µ). This is equivalent to Φ−1 (a∗ ) = Φ−1 (1 − a∗ ) − µ = −Φ−1 (a∗ ) − µ, hence,

a∗ = Φ(−µ/2). √ Together with µ = O(1/ M ), the Taylor series expansion of the cumulative normal distribution around 0, see Stuart and Ord [23], gives the following approximation: a∗ = Φ(−µ/2) =

1 µ − √ + O(M −3/2 ). 2 8π □

This concludes the proof of the proposition.

Proposition G.7. Let f be the trade-off function of DP-SGD for a single epoch with M rounds with subsampling based on random shuffling and √ noise multiplier σ. There exists ′a sequence ′ ′ ′ 0 ≤ δM = o(1/M ) and sequence 0 ≤ γM = O( ln M /M ) such that for a ∈ [a∗ − δM , 1 − δM ], ∗ ′ , we have where a is the fixed point of GµM +γM s e1/σ2 − 1 ′ ′ ′ (a + δ f (a) ≥ GµM +γM . M ) − δM with µM = M −1 Proof: We first notice that Proposition G.4 implies that there exists a sequence 0 ≤ δM = o(1/M ) √ and a sequence 0 ≤ γM = O( ln M /M ) such that 2

f (a) ≥ GµM +γM (a + δM ) − √

e2/σ · sign(1/2 − a + δM ) − δM 8πe · (M − 1)

(78)

for a ∈ [δM , 1 − δM ]. We are going to construct a value xM ≥ 0 with xM = O(1/M ) that has the following property: Let a∗ = Φ(−(µM + γM + xM )/2), ∗ in other words, √ a is the fixed point of GµM +γM +xM by Proposition G.6. From (G.6) we infer that, if xM = O(1/ M ) (which will be satisfied since we will construct xM such that it is O(1/M )), then

a∗ =

1 µM + γM + xM √ − + O(M −3/2 ). 2 8π 38

(79)

We define

x2 ′ ′ δM = δM + √ M and γM = γM + xM . 8eπ

′ ′ . The definition of γM implies that a∗ is the fixed point of GµM +γM

The theorem follows if xM satisfies ′ ′ ′ ′ fM (a) ≥ GµM +γM +x (a + δM ) − δM for a ∈ [a∗ − δM , 1 − δM ].

Notice that if

(80)

x2 ′ a∗ ≥ δM + δM = 2δM + √ M , 8eπ

′ ′ ′ then [a∗ − δ√ M , 1 − δM ] ⊆ [δM , 1 − δM ] (because also 1 − δM ≤ 1 − δM ). This inequality is satisfied 2 ∗ for xM ≤ 8eπ · (a − 2δM ) (which will be satisfied since we will construct xM such that it is O(1/M ) and a∗ is characterized by (79)). ′ Since xM increases the parameters µM + γM to µM + γM + x and a + δM to a + δM and since ′ Gµ (a) is decreasing in both µ and a, (78) implies for a ∈ [1/2 + δM , 1 − δM ] ⊆ [1/2 + δM , 1 − δM ] inequality (80): 2

f (a)

≥

GµM +γM (a + δM ) − √

e2/σ · sign(1/2 − a + δM ) − δM 8πe · (M − 1)

≥ GµM +γM (a + δM ) − δM ′ ′ ≥ GµM +γM +x (a + δM ) − δM . ′ , 1/2 + δM ] we derive For a ∈ [a∗ − δM 2

fM (a)

≥ ≥

e2/σ · sign(1/2 − a + δM ) − δM 8πe · (M − 1) ′ GµM +γM (a + δM ) − [GµM +γM (a + δM ) − GµM +γM +xM (a + δM )] − δM (81)

GµM +γM (a + δM ) − √

if we can prove that [GµM +γM (a + δM ) − GµM +γM +xM (a + δM )] 2

2

≥

√

e2/σ x2 e2/σ ′ + [δM − δM ]= √ − √M . 8πe · (M − 1) 8πe · (M − 1) 8eπ

We use the Taylor series expansion given by (36): GµM +γM +xM (a + δM ) = Φ(Φ−1 (1 − a − δM ) − (µM + γM + xM )) x2 ≤ Φ(Φ−1 (1 − a − δM ) − (µM + γM )) − xM Φ′ (Φ−1 (1 − a − δM ) − (µM + γM )) + √ M 8eπ 2 x = GµM +γM (a + δM ) − xM Φ′ (Φ−1 (1 − a − δM ) − (µM + γM )) + √ M . 8eπ We need to prove 2

xM Φ′ (Φ−1 (1 − a − δM ) − (µM + γM )) ≥ √

e2/σ . 8πe · (M − 1)

(82)

′ Notice that for a ∈ [a∗ − δM , 1/2 + δM ] we have that t = Φ−1 (1 − a − δM ) − (µM + γM ) is ′ decreasing in a and Φ (t) as a function of t is positive and increasing for t < 0 and decreasing for ′ t > 0 with Φ′ (t) = Φ′ (−t). For this reason the left hand side of (82) is minimized for a = a∗ − δM or a = 1/2 + δM . We derive

Φ−1 (1 − (1/2 + δM ) − δM ) − (µM + γM ) = Φ−1 (1/2 − 2δM ) − (µM + γM ) 39

and, by using (79), ′ Φ−1 (1 − (a∗ − δM ) − δM ) − (µM + γM ) 2 x = Φ−1 (1 − a∗ + √ M ) − (µM + γM ) 8eπ 1 µ + γ + xM x2 M √M = Φ−1 ( + + O(M −3/2 ) + √ M ) − (µM + γM ). 2 8π 8eπ

We also have the approximation √ √ Φ−1 (1/2 + z/ 8π + O(M −3/2 ) = z/2 + O(M −3/2 ) for z = O(1/ M ). We may apply this formula to both quantities: Φ−1 (1/2 − 2δM ) − (µM + γM )

√ − 8π · δM + O(M −3/2 ) − (µM + γM )

=

(83)

and

= =

x2 1 µM + γM + xM √ + O(M −3/2 ) + √ M ) − (µM + γM ) Φ−1 ( + 2 8π 8eπ √ µM + γM + xM + x2M / e + O(M −3/2 ) − (µM + γM ) 2 √ µM + γM − xM − x2M / e − + O(M −3/2 ). 2

In absolute value, for M large enough, (83) is the largest and minimizes the Φ′ evaluation. This reduces (82) to proving √ xM Φ′ (−( 8π · δM + µM + γM ) + O(M −3/2 )) ≥ √

2

e2/σ . 8πe · (M − 1)

(84)

√ √ 2 By using Φ′ (t) = e−t /2 / 2π ≥ (1 − t2 /2)/ 2π, we derive ′

√

xM Φ (−( 8π · δM + µM + γM ) + O(M

−3/2

√ 1 − ( 8π · δM + µM + γM )2 /2 √ )) ≥ xM · 2π

and (84) follows from 2

e2/σ √ = O(1/M ). 4e · (M − 1) · (1 − ( 8π · δM + µM + γM )2 /2) √ ′ ′ We notice that δM = o(1/M ) and γM = γM + x = O( ln M /M ). Now the proposition follows from (80). □ xM = √

We are now ready to prove the main asymptotical result of Theorem 5.2. Proof of Theorem 5.2: Let fM be the trade-off function of DP-SGD for a single epoch with M rounds with subsampling based on random shuffling and noise multiplier σ. As a consequence of ′ ′ ′ Proposition G.7 we√have that there exists a sequence δM and a sequence γM with 0 ≤ δM = o(1/M ) ′ and 0 ≤ γM = O( ln M /M ) such that trade-off function fM satisfies ′ ′ ′ (a + δ f (a) ≥ GµM +γM M ) − δM ′ ′ ′ for a ∈ [a∗M − δM , 1 − δM ] where a∗M is the fixed point of GµM +γM where s e1/σ2 − 1 µM = . M −1

We define

′ ′ ′ ′ (δ δ̂M = max{δM /a∗M , (1 − Gµ+γM M )) + δM }

40

and apply Lemma G.5. This proves ′ fM (a) ≥ (GµM +γM ⊗ f0,δ̂M )(a) for a ∈ [0, 1].

This implies ⊗E fM ≥ GµM ·√E+γM ·√E ⊗ f0,1−(1−δ̂M )E ≥ GµM ·√E+γM ·√E ⊗ f0,δ̂M ·E .

From Proposition G.6 we infer that δ̂M = o(1/M ). Now we can take the limit with E = c2M · M and M → ∞ where cM → c for some constant c ≥ 0. Since the functions √ G. and f.,. are 2 continuous in their and since√δ̂M E = o(cM ) → 0 and γM · E → 0 as well as √ (hyper) parameters p √ µM · E = cM e1/σ2 − 1 M/(M − 1) → c e1/σ2 − 1, we have for M → ∞, ⊗E fM (a) ≥ G √ 1/σ2 c

e

−1

(a)

uniformly in a ∈ [0, 1]. If c = 0 we have the convergence f (a) → 1 − a. □ Proof of Corollary 5.3: For constant σ, Theorem 5.2 together with Proposition G.6.(ii) shows that sep(f ⊗E )

≤ ≤ ≤

sep(G(µ+γM )√E ⊗ f0,1−(1−δˆM )E ) √ 1 1 √ (1 − 2Φ(−(µ + γM ) E/2)) + √ (1 − (1 − δˆM )E ) 2 2 √ √ 1 1 √ ( √ (µ + γM ) E + O(M −3/2 E 3/2 ) + δˆM E) = O(µ E). 2 2π

Theorem 4.1 shows that for constant σ, 1 1 sep(f ⊗E ) ≤ √ (1 − (1 − δ)E ) ≤ √ δE = O(µE). 2 2 □

41