arXiv CS open access

Can Rényi Accountants Beat Lossless Accountants for DP-SGD?

Jinho Bok · arxiv_cs

arXiv CS · Papers

cryptography cybersecurity privacy security

Recent frameworks in differential privacy (DP), such as privacy loss distributions and $f$-DP, provide lossless representations of the privacy leakage of mechanisms. These approaches are often considered to yield tighter $(\varepsilon, δ)$-DP guarantees than those obtained from relaxed notions such

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Can Rényi Accountants Beat Lossless Accountants for DP-SGD? Jinho Bok*

arXiv:2610.17120v1 [cs.LG] 12 Oct 2026

October 12, 2026

Abstract Recent frameworks in differential privacy (DP), such as privacy loss distributions and f DP, provide lossless representations of the privacy leakage of mechanisms. These approaches are often considered to yield tighter (ε, δ)-DP guarantees than those obtained from relaxed notions such as Rényi DP. But is that always the case? We study this question for differentially private stochastic gradient descent (DP-SGD) with fixed-size batches under replace adjacency. Our key observation is that in this setting, privacy accounting based on Rényi DP can use a pair of worst-case distributions (i.e., a dominating pair) that differs from the one used in the lossless frameworks. In particular, we characterize the worst-case distributions as two-dimensional Gaussian mixtures and derive an improved Rényi DP bound for DP-SGD. Numerical and asymptotic comparisons show that across various hyperparameter settings, a Rényi DP accountant based on the new bound can yield better privacy guarantees than those obtained from the lossless frameworks.

* Department of Statistics and Data Science, University of Pennsylvania. Email: jinhobok@wharton.upenn.edu

Contents 1

Introduction 1.1 Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2 3

Preliminaries 2.1 Privacy accounting via dominating pairs . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Rényi accountants versus lossless accountants . . . . . . . . . . . . . . . . . . . . . . 2.3 Differentially private stochastic gradient descent . . . . . . . . . . . . . . . . . . . . .

3 3 4 5

Dominating pairs for DP-SGD

Improved Rényi accountant for DP-SGD 4.1 Characterization of Rényi DP bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Theoretical results for implementation . . . . . . . . . . . . . . . . . . . . . . . . . . .

6 6 7

Numerical comparisons

Asymptotic comparisons 9 6.1 Comparison with lossless accountants . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 6.2 Comparison between Rényi accountants . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Discussion

References

A Deferred details for proofs A.1 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1.1 Proof of Lemma 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Derivative calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Proof of Proposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3.1 Proof of Lemma 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Proof of Proposition 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 Proof of Proposition 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.6 Proof of Corollary 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 16 17 19 20 24 25 25 28

B Deferred details for numerical comparisons B.1 Additional results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Numerical implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Mathematical derivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3.1 Point calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3.2 Maximum calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29 29 35 37 37 39

Introduction

Differential privacy (DP) [DMNS06] is widely regarded as a gold standard for data privacy and has been adopted in numerous areas [Abo18, ABD+ 23, XZA+ 23, CDE+ 24, FVH25]. A prominent problem in DP across different application domains is private optimization, where the goal is to train models while preserving the privacy of each individual’s information. Differentially private stochastic gradient descent (DP-SGD) [ACG+ 16] is the de facto standard algorithm for private optimization. Hence, quantifying the privacy leakage after multiple iterations (i.e., privacy accounting) of DP-SGD is a fundamental problem. Formally, this can be done by bounding the divergences between the outputs from adjacent datasets, i.e., two datasets such that one is obtained by replacing an individual record from the other. In the literature, there are two prototypical choices for the divergences: Rényi divergences and hockey-stick divergences. As frameworks for privacy accounting, the former is commonly called Rényi DP [Mir17], whereas the latter is often identified with equivalent frameworks such as privacy loss distributions (PLD) [DR16, MM18], privacy loss random variables (PRV) [GLW21], and f -DP [DRS22]. A conventional view is that the privacy guarantees1 based on hockey-stick divergences are tighter than those from Rényi DP [KJH20, GLW21, DRS22]. This is because hockey-stick divergences (and equivalent notions for privacy accounting) capture the entire privacy characteristic of a mechanism that can be losslessly converted to other DP notions, whereas Rényi DP is inherently lossy as a relaxed notion of DP. However, an underlying assumption of this argument is that they use the same pair of worst-case distributions (i.e., a dominating pair) to characterize the privacy leakage of a mechanism. We question this premise and ask: can Rényi DP provide better privacy guarantees by using a different pair of distributions?

1.1

Our contributions

We answer this question in the affirmative for DP-SGD with fixed-size batches (i.e., sampling without replacement). In particular, we propose an improved Rényi DP bound in this setting, using certain two-dimensional Gaussian mixtures as worst-case distributions (Section 4). This Rényi DP bound is characterized as the value of a one-dimensional maximization problem that can in general be solved numerically, and under certain conditions admits simple, explicit solutions. Through numerical comparisons (Section 5), we show that across various hyperparameter settings, our new Rényi DP bound yields tighter privacy guarantees than those from hockey-stick divergences. We note, however, that such improvement is not uniform over all choices of DP-SGD hyperparameters, and the privacy bounds in their original analytical forms are rather difficult to compare. We provide asymptotic comparisons (Section 6) where we compare limits of privacy parameters in the regime where they are convergent, illustrating the potential advantages of our new privacy bound based on analytical results. Such comparisons are also done against existing Rényi DP bounds [WBK21, BEBP24] where we demonstrate uniform improvements over theirs. Conceptually, our results reveal an interesting trade-off between the granularity of information used and the quality of worst-case distributions for privacy accounting. Indeed, hockey-stick divergences and their equivalent accounting formalisms—which, for example, characterize the privacy curve [MM18] or the Type I/II error curve [DRS22]—are based on the entire privacy characteristic and thus operate at the level of “function”. The vast amount of information needed in those frameworks handles key components of privacy accounting—e.g., composition of mechanisms, conversion to other DP notions—in a lossless manner, but also limits the corresponding 1 Throughout, we compare privacy guarantees from different approaches in (ε, δ )-DP (see Definition 1).

worst-case distributions to simultaneously satisfy many conditions (i.e., inequalities holding at all γ, as in Definition 3). On the other hand, Rényi DP only characterizes a certain moment bound and works at the level of “functional”; while such information is coarse and may incur loss—e.g., for conversion to other DP notions, the corresponding worst-case distributions only need to satisfy a coarse condition (i.e., an inequality at a single α; see also Definition 3). We believe that this discrepancy between the two frameworks merits further investigation, and hope that our case study in DP-SGD here motivates such inquiry.

1.2

Related work

Privacy accounting. Bounding the privacy leakage of mechanisms over composition has been a central topic in DP. The frameworks based on Rényi divergences are collectively called Rényi DP [Mir17], and related notions such as concentrated DP [DR16] and its variants [BS16, BDRS18] have also been widely studied. While Rényi DP is desirable due to its analytical convenience (e.g., composition expressed as a sum; see Fact 1), it is also known to be inherently lossy when converted to other notions of DP including (ε, δ)-DP (see, for example, [DRS22, Proposition B.7]). On the other hand, the second line of frameworks—e.g., PLD [DR16, MM18, SMM19], PRV [GLW21], f -DP [DRS22]—are lossless when converted to any other notion of DP. At a fundamental level, they are all based on a notion called Blackwell order [Bla51] and hence are equivalent to each other, sharing the same dominating pairs and privacy guarantees. See, for example, [RHL+ 26, Section 2] for a summary of such facts. Despite their lossless property, the resulting privacy bounds are often analytically cumbersome, and their evaluations often rely on different numerical approaches [KJH20, DGK+ 22, GKKM22, ZDW22, AGA+ 23]. Privacy of DP-SGD. For privacy accounting of DP-SGD, we follow the mainstream approach: first obtain a privacy bound for a single iteration of DP-SGD, and then extend that for multiple iterations by (adaptive) composition. Among this line of work, the original paper on DP-SGD [ACG+ 16] proposed a framework known as the moments accountant, which is now subsumed by Rényi DP [Mir17]. Since then, several works have provided tighter privacy guarantees for DP-SGD under Rényi DP [MTZ19, WBK21, BEBP24] as well as under the lossless frameworks [BDLS20, DRS22]. It is also worth mentioning that recent literature has developed alternative approaches [FMTT18, YS22, ABT24, BSA24, KR24, CL25], assuming that only the final iterate of DP-SGD is released. While those results provide improved privacy bounds (sometimes even convergent as the number of iterations increases), they are also based on restrictive assumptions such as loss functions being convex. In that sense, they provide a complementary perspective for the former approach. Subsampling schemes for DP-SGD. There are different ways to subsample the random batch in DP-SGD; a popular example is the Poisson subsampling [ACG+ 16], where each index is included in the batch independently. Furthermore, developing and analyzing new subsampling schemes for DP-SGD has gained attention in recent years [CGH+ 25, SF25, DÖ26]. We deliberately choose the combination of fixed-size batches and replace adjacency (Definition 1), because it is a practically relevant and analytically clean setting that exhibits a discrepancy between different privacy accountants in terms of the worst-case distributions. [LRKS25] discuss several nuances around subsampling schemes and adjacency notions for DP-SGD, highlighting how different (but seemingly similar) choices have disparate effects for privacy accounting. In a similar vein, we study the implications of a particular set of DP-SGD specifications for privacy accounting.

1.3

Notations

We denote [n] ≜ {1, . . . , n} and a ∨ b ≜ max{ a, b}, a ∧ b ≜ min{ a, b}. For a distribution P, P⊗T denotes the product distribution of T copies of P. ϕ and Φ respectively denote the PDF and CDF of N (0, 1); Ber( p) denotes the Bernoulli distribution with success probability p. We often write the distribution itself to denote an independent random variable/vector that is distributed as such; for example, aBer( p) + N (0, Id ) denotes a mixture distribution of N ( a, Id ) and N (0, Id ) with respective mixture weights p and 1 − p. We use standard big-O notation, with subscripted variables under O denoting factors that may depend on those variables.

Preliminaries

2.1

Privacy accounting via dominating pairs

As a formal notion, DP evaluates the effect of an individual’s data on the output of a mechanism by statistically comparing the outputs from adjacent datasets. Definition 1 (Replace adjacency and (ε, δ)-DP). Let S ≜ (z1 , . . . , zn ) and S′ ≜ (z1′ , . . . , z′n ). Then S and S′ are adjacent if there exists i∗ ∈ [n] such that zi = zi′ for all i ∈ [n] \ {i∗ }. A mechanism A is (ε, δ)-DP if for all adjacent datasets S, S′ and events E, P(A(S) ∈ E) ≤ exp(ε)P(A(S′ ) ∈ E) + δ .

Intuitively, smaller values of ε or δ mean that the two distributions A(S) and A(S′ ) are closer, and hence harder to distinguish. Formally, such privacy guarantees can be obtained by bounding the divergences between the two outputs. Definition 2 (Rényi divergence and hockey-stick divergence). Let P, Q be distributions. For α > 1, the Rényi divergence of order α between P and Q is defined as α Z 1 dP Dα ( P ∥ Q ) ≜ log (ω ) dQ(ω ) . α−1 dQ For γ ≥ 0, the hockey-stick divergence of order γ between P and Q is defined as (with x+ ≜ x ∨ 0) Z dP Hγ ( P∥ Q) ≜ (ω ) − γ dQ(ω ) . dQ + For any type of divergence under consideration, the corresponding (ε, δ)-DP guarantee can be obtained by first identifying a dominating pair [SMM19, ZDW22], and then converting the corresponding divergence bound to a (ε, δ)-DP bound. Dominating pair can be considered as “worst-case” distributions for quantifying the privacy leakage of a mechanism. Definition 3 (Dominating pairs). Let A be a mechanism. Then ( P, Q) is an (order-α) Rényi dominating pair for A if for all adjacent datasets S and S′ , Dα (A(S)∥A(S′ )) ≤ Dα ( P∥ Q) .

( P, Q) is a hockey-stick dominating pair2 for A if for all adjacent datasets S and S′ , Hγ (A(S)∥A(S′ )) ≤ Hγ ( P∥ Q) for all γ ≥ 0.

2 In the literature, dominating pairs usually refer to the hockey-stick dominating pairs. Also, in principle, privacy

accounting based on Rényi divergences can be formulated without the notion of dominating pairs. Here we choose to name and define dominating pairs according to the divergences, in order to highlight the conceptual difference between the corresponding privacy accountants.

A central concept in DP is composition, where a mechanism is built by composing other mechanisms. The notion of dominating pairs is particularly useful for handling composition, because the cumulative privacy leakage can be accounted by taking the corresponding product distributions as a dominating pair. Fact 1 (Composition using dominating pairs; [Mir17, Proposition 1], [ZDW22, Theorem 10]). For each k ∈ [ T ], let ( Pk , Qk ) be an order-α Rényi dominating pair for mechanism3 Ak (·, θ ) for all θ. Then (⊗kT=1 Pk , ⊗kT=1 Qk ) is an order-α Rényi dominating pair for the composed mechanism (for any initialization θ0 ) A ≜ A T ◦ A T −1 ◦ · · · ◦ A1 : S 7→ A T (S, A T −1 (S, . . . , A1 (S, θ0 )) . . . ), i.e., T

Dα (A(S)∥A(S′ )) ≤ Dα (⊗kT=1 Pk ∥ ⊗kT=1 Qk ) = ∑ Dα ( Pk ∥ Qk ) . k =1

Similarly, if ( Pk , Qk ) is a hockey-stick dominating pair for Ak (·, θ ) for all θ, then (⊗kT=1 Pk , ⊗kT=1 Qk ) is a hockey-stick dominating pair for A, i.e., Hγ (A(S)∥A(S′ )) ≤ Hγ (⊗kT=1 Pk ∥ ⊗kT=1 Qk ) for all γ ≥ 0 . The divergence bounds for the dominating pairs can be converted to (ε, δ)-DP bounds based on certain formulae [Mir17, BBG+ 20, ALC+ 21, ZDW22, RGC+ 26].

2.2

Rényi accountants versus lossless accountants

Throughout, we refer to the procedures of privacy accounting explained in Section 2.1 as Rényi accountants if they are based on Rényi divergences; similarly, we refer to the corresponding procedures based on hockey-stick divergences as lossless accountants. The latter term collectively denotes several accountants, including those based on PLD, PRV, f -DP, characteristic functions [ZDW22], and more; such abstraction is justified by the fact that the underlying notions of dominating pair and composition are all mathematically equivalent [ZDW22]. Both Rényi and lossless accountants are widely used and have been deployed in DP libraries such as Opacus [YSS+ 21] and JAX-Privacy [MAB+ 26]. A distinctive feature of lossless accountants is that they allow lossless conversion to (ε, δ)-DP, as demonstrated by the following necessary and sufficient condition. Fact 2 ([ZDW22, Lemma 5]). A is (ε, δ)-DP if and only if Hexp(ε) (A(S)∥A(S′ )) ≤ δ for all adjacent datasets S and S′ . On the other hand, such “if and only if” statement does not hold for Rényi divergences, and the conversions to (ε, δ)-DP bounds are inherently lossy; see, for example, [BS16, RGC+ 26]. This implies that if a Rényi accountant and a lossless accountant both use the same pair of distributions as their dominating pair, the latter would provide a privacy guarantee that is at least as good as (and often strictly better than) what the former would provide. Furthermore, for several mechanisms such a gap cannot be improved because both accountants share the same tight (i.e., the best possible) dominating pair in those cases [Mir17, ZDW22]. 3 Here, each mechanism A

k admits an additional input θ that can be considered as an initialization or an output from

a previous iteration.

2.3

Differentially private stochastic gradient descent

Throughout, we consider a standard version of DP-SGD where at each iteration, a fixed-size batch is chosen uniformly at random (i.e., sampling without replacement). Definition 4 (DP-SGD with fixed-size batches). Given a dataset (z1 , . . . , zn ), loss functions θ ∈ Rd 7→ ℓ(θ, zi ) for i ∈ [n], and initialization θ0 , DP-SGD is a mechanism such that for k = 0, 1, . . . , T − 1, 1. samples b distinct elements Bk from [n] uniformly at random; 2. updates as θ k +1 ← θ k − η k

1 σC clipC (∇ℓ(θk , zi )) + ξ ∑ b i∈ B b k k

where clipC ( x ) ≜ x/(1 ∨ ∥ x ∥/C ), and ξ k ∼ N (0, Id ) are independent; and outputs θ T .

Dominating pairs for DP-SGD

What do the dominating pairs for one iteration of DP-SGD look like? Intuitively, the key point is whether the special index i∗ (see Definition 1) and the associated point zi∗ is used. It is straightforward to see that i∗ is included in the batch with probability p ≜ b/n. Also, if zi∗ is replaced with some other point z (zi′∗ from adjacent dataset, or zi with i ̸= i∗ from batch subsampling), the gradient can differ by at most ∥clipC (∇ℓ(θt , zi∗ )) − clipC (∇ℓ(θt , z))∥/b ≤ 2C/b. By scaling so that the Gaussian noise has unit variance, this difference in gradient becomes at most ∆ ≜ 2/σ. Combining these arguments, one can consider the following family of candidates for dominating pairs: {( aBer( p) + N (0, Id ), bBer( p) + N (0, Id )) : ∥ a∥ ≤ ∆, ∥b∥ ≤ ∆, ∥ a − b∥ ≤ ∆} . (1) For Rényi accountants, (1) is indeed sufficient for characterizing dominating pairs in the following sense: Lemma 1 ([BEBP24, Equation 56]). Define ρ(α, p, ∆) ≜

sup ∥ a∥≤∆, ∥b∥≤∆, ∥ a−b∥≤∆

Dα ( aBer( p) + N (0, Id )∥bBer( p) + N (0, Id )) .

(2)

Then ( P, Q) with Dα ( P∥ Q) = ρ(α, p, ∆) is an order-α Rényi dominating pair for DP-SGD (Definition 4), where ∆ = 2/σ. It can be shown that for each (α, p, ∆), the right hand side of (2) (as the maximum of a continuous function on a compact set) attains its maximum at some ( a, b) = ( a∗ , b∗ ). This implies that one can take a single pair ( a∗ Ber( p) + N (0, Id ), b∗ Ber( p) + N (0, Id )) as a Rényi dominating pair. On the other hand, for lossless accountants, at least two distinct elements from (1) need to be considered (see, e.g., [ZDW22, Section C.4] or [LRKS25, Section 7]). Lemma 2. Let ( P, Q) be a hockey-stick dominating pair for DP-SGD (Definition 4). Then for ∆ = 2/σ, Hγ ( P∥ Q) ≥ Hγ (∆Ber( p) + N (0, 1)∥N (0, 1)) 5

(3)

for all γ ≥ 1, and

Hγ ( P∥ Q) ≥ Hγ (N (0, 1)∥∆Ber( p) + N (0, 1))

(4)

for all 0 < γ < 1. In particular, it follows that neither (∆Ber( p) + N (0, 1), N (0, 1)) nor (N (0, 1), ∆Ber( p) + N (0, 1)) is by itself a hockey-stick dominating pair; recall from Definition 3 that a dominating pair should simultaneously satisfy the inequalities for all γ ≥ 0. Nonetheless, the conditions (3) and (4) are sufficient, and accordingly lossless accountants can provide the following privacy guarantee for DP-SGD [DRS22, ZDW22, LRKS25]. Proposition 1 (Privacy guarantee from lossless accountants; [ZDW22, Corollary 32]). For each p ∈ e ) for DP-SGD (Definition 4) such that eQ (0, 1) and σ > 0, there exists a hockey-stick dominating pair ( P, (3) holds with equality for all γ ≥ 1 and (4) holds with equality for all 0 < γ < 1. Consequently, if ⊗ T ⊗ T e Hexp(ε) Pe ∥ Q ≤ δ then DP-SGD with T iterations is (ε, δ)-DP.

The discussion so far highlights the key difference between Rényi and lossless accountants that we study in this work: Rényi accountants can take a single element from (1) as a dominating pair, whereas lossless accountants need4 to take two distinct elements from (1) and “combine” them as in Proposition 1. In particular, this suggests that different dominating pairs can be used for those accountants.

Improved Rényi accountant for DP-SGD

4.1

Characterization of Rényi DP bound

We show that for the problem (2) of maximization over Gaussian mixtures, it suffices to consider two-dimensional Gaussians whose means a, b and 0 form an isosceles (∥ a − 0∥ = ∥ a − b∥ = ∆); this effectively reduces the problem (2) over d-dimensional vectors to a one-dimensional problem. In words, this implies that for each iteration of DP-SGD, there exist two-dimensional Gaussian mixtures that serve as a dominating pair. See Figure 1 for an illustration. Theorem 1. If d ≥ 2, for (2) we have p ρ(α, p, ∆) = max Dα ∆(1, 0) × Ber( p) + N (0, I2 ) ∆(u, 2u − u2 ) × Ber( p) + N (0, I2 ) . (5) u∈[0,1/2]

Proof sketch. The proof proceeds by reducing (2) to simpler problems. It is straightforward to check ∥ a∥2 ⟨ a, b⟩ that the Rényi divergence in (2) for each a, b only depends on the covariance matrix . ⟨ a, b⟩ ∥b∥2 Thus, we can assume d = 2. Furthermore, we show that it suffices to consider such covariance matrices that are maximal in the Loewner order. This leaves only a few possible cases, from which we derive (5) by ruling out most of the cases based on direct comparisons. See Appendix A.1 for a complete proof. 4 This “necessity” argument assumes using the mainstream approach of using dominating pair as explained in Section 2.1. Whether such approach can be bypassed is an open question; see also Sections 2.1 and 7 for discussion.

Figure 1: Illustration of the Gaussian mixtures that serve as a Rényi dominating pair √ for DP-SGD (see (5)); here p = 0.2, ∆ = 4.5, u = 0.3. The points (0, 0), ∆(1, 0), and ∆(u, 2u − u2 ) (each corresponding to the mean of the mixture component) form an isosceles. Theorem 1 provides a one-step Rényi DP bound. Our proposed Rényi accountant is based on this one-step bound, and uses Rényi composition (Fact 1) as well as conversion from Rényi DP to (ε, δ)-DP from [BBG+ 20, Theorem 20] to calculate the following privacy bound for DP-SGD.5 Corollary 1 (Privacy guarantee from (5)). For any α > 1 and δ ∈ (0, 1), DP-SGD (Definition 4) with T iterations is (ε, δ)-DP with 2 1 1 ε = Tρ α, p, + log 1 − − log(δα) , (6) σ α α−1 where ρ satisfies (5).

4.2

Theoretical results for implementation

The problem (5) over u ∈ [0, 1/2] is parametrized by α, p and ∆ (equivalently σ). We explore simple and sufficient conditions for these hyperparameters, under which the solutions of the problem (5) are explicitly determined. For numerical implementation with hyperparameters outside of those conditions, we use a branch-and-bound approach to iteratively update an upper bound on (5)—see Appendix B.2 for details. Proposition 2 (Sufficient conditions for characterizing (5)). Consider the problem (5) over u ∈ [0, 1/2]. (a) (Large α) (5) is maximized at u = 0 if

σ2 log(2/p) α ≥ 2∨ 1+ 2(1 − p )

(b) (Small p) (5) is maximized at either u = 0 or u = 1/2 if σ2 > α and ! ! −1 √ √ 2 6 (12 2 + 8)α + 8 2 − 8 + p ≤ 1+ 3+ e σ2 σ2 − α . σ2 − α

5 Recently, [RGC+ 26] provided an optimal procedure for converting Rényi DP guarantees to ( ε, δ )-DP guarantees,

which would in principle provide a tighter bound. Nonetheless, we focus on the formula from [BBG+ 20], as it has a simple closed form, is convenient for implementation (see Proposition 3), and can already provide privacy bounds that improve over those from lossless accountants (see Section 5).

p = 0.01, σ = 2, δ = 10−6 30

Our bounds Birrell et al. Wang et al. Lossless accountants

25 20

Our bounds Birrell et al. Wang et al. Lossless accountants

8 Privacy ε

Privacy ε

p = 0.01, σ = 6, δ = 10−6 10

6 4

10 2

0 250

500

1000

2000 4000 Iterations T

8000

16000

32000

250

500

1000

2000 4000 8000 16000 32000 64000 Iterations T

Figure 2: Accounted privacy ε for noise multipliers σ ∈ {2, 6}. Our bounds improve over existing bounds as the number of iterations increases. p = 0.04, σ = 4, δ = 10−6

p = 0.0025, σ = 4, δ = 10−6 3.5

30 Privacy ε

Privacy ε

2.5

Our bounds Birrell et al. Wang et al. Lossless accountants

3.0

2.0 1.5 1.0

0.5 0.0

0 250

500

1000

250

2000 4000 8000 16000 32000 64000 Iterations T

500

1000

2000 4000 Iterations T

8000

16000

Figure 3: Accounted privacy ε for subsampling rates p ∈ {0.0025, 0.04}. The improvements from our bounds over existing bounds are more prominent for larger p. The proof is deferred to Appendix A.3. Another question lies in choosing the Rényi order α for Corollary 1. We show that for the final converted ε, the curve α 7→ ε(α) is unimodal in α. This implies, for example, that calculating (6) over integers 2 ≤ α ≤ αmax only requires evaluation at O(log αmax ) orders, based on binary search (for sufficiently large αmax ). Proposition 3 (Unimodality in Rényi order). For any T, p, σ and δ ∈ (0, 1), ε in (6) as a function of α ∈ (1, ∞) is unimodal, i.e., minimized at a unique point. The proof is deferred to Appendix A.4.

Numerical comparisons

We numerically compare the (ε, δ)-DP guarantees from three different Rényi accountants (ours from Corollary 1, [BEBP24], [WBK21]) and lossless accountants (Proposition 1), for different values of the DP-SGD hyperparameters p (subsampling rate), σ (noise multiplier), and T (number of iterations). Our code for reproducing the numerics can be found at: https://github.com/jinhobok/ renyi vs lossless dpsgd. Figure 2 displays numerical values of ε for different values of σ, whereas Figure 3 displays those for different values of p. Throughout, it can be observed that our privacy bounds always 8

improve over those from existing Rényi accountants. Furthermore, while our bounds are sometimes larger than those from lossless accountants (for small T here; see also Appendix B.1 for other cases), they improve over those as the number of iterations increases. This is consistent with the original motivation of this work on using different dominating pairs: compared to Rényi accountants, lossless accountants use another dominating pair whose corresponding privacy guarantee becomes relatively loose as the number of compositions increases (see Section 3). We observe similar findings over broader ranges of the parameters; the full results can be found in Appendix B.1.

Asymptotic comparisons

In addition to the numerical comparisons, we compare different privacy accounting methods for DP-SGD based on their asymptotics as the subsampling rate p → 0. This simplification helps us provide a theoretical explanation about how our privacy guarantees may improve over those from existing accountants.

6.1

Comparison with lossless accountants

Here, we compare our bounds with those provided by lossless accountants in the asymptotic regime T → ∞, p → 0 and T p2 → ν ∈ (0, ∞). We focus on this regime because the privacy guarantee from the lossless accountants converges to that of the Gaussian mechanism; this is the celebrated central limit theorem, originally formulated in f -DP [DRS22, Corollary 4]. For notational simplicity, throughout this subsection we fix ε and let δ denote the limiting value (limit superior if the limit is not guaranteed to exist) of the corresponding privacy parameter. Lemma 3 (Limit of δ for lossless accountants). If T → ∞, p → 0 and T p2 → ν, the limiting privacy parameter δ = δL (ε) for lossless accountants satisfies ε µ ε µ ε δL (ε) = Φ − + −e Φ − − , µ 2 µ 2 q 2 where µ ≜ 2ν(e4/σ Φ(3/σ ) + 3Φ(−1/σ ) − 2).

The following is a simple upper bound for the limiting δ for our accountant, in the same asymptotic regime. As a caveat, we note that this result is based on a Rényi DP bound with Rényi order that may not be an integer. Proposition 4 (Limit of δ for our accountant). If T → ∞, p → 0 and T p2 → ν, the limiting privacy parameter δ = δ(ε) for our accountant satisfies ε/λ λ ε ε2 ε δ(ε) ≤ exp − + , λ+ε λ+ε 2λ 2 2

where λ ≜ 2ν(e4/σ − e2/σ ).

Proof. For each α, from Proposition 5 the limiting Rényi DP bound is given as να(e4/σ − e2/σ ). Plugging this in Corollary 1 and rearranging, we obtain 2 2 1 1 α −1 δ(ε) ≤ 1− exp((α − 1)(να(e4/σ − e2/σ ) − ε)) . (7) α α The conclusion follows with α = 1 + ε/λ in (7).6 9

T p2 = ν = 0.5, σ = 2

Privacy log δ

−3 −4 −5 −6 −7 −8 2000

4000

Our bounds, ε = 2 Limit (ours), ε = 2 Lossless accountant, ε = 2 Limit (lossless), ε = 2

8000 16000 p Iterations T , with p = ν/T Our bounds, ε = 3 Limit (ours), ε = 3 Lossless accountant, ε = 3 Limit (lossless), ε = 3

32000 Our bounds, ε = 4 Limit (ours), ε = 4 Lossless accountant, ε = 4 Limit (lossless), ε = 4

Figure 4: Illustration of privacy bounds for finite T and their asymptotic limit (Lemma 3 and Proposition 4; note that the latter is a limit superior). Here, p depends on T, keeping T p2 = ν. As ε increases, our bounds provide better privacy guarantees than those from lossless accountants. The privacy bounds become closer to their limits as T increases. Figure 4 illustrates the privacy parameter δ (in log scale) for (ε, δ)-DP obtained from finite T, as well as their limiting values. It can be observed from the plot that as ε increases, our bounds yield smaller δ than those from lossless accountants, both for finite T and the limits. In fact, the following result can be shown: Corollary 2 (Comparison between limiting δ). In the setting of Lemma 3 and Proposition 4, µ2 > λ and 1 1 1 ε2 + log ε + Oµ,λ (1) . log δ(ε) − log δL (ε) ≤ − − 2 λ µ2

See Appendix A.6 for its proof. Here, the right hand side eventually decreases to −∞ as ε increases, illustrating how our privacy bounds may improve over those from lossless accountants.

6.2

Comparison between Rényi accountants

In this subsection, we provide a simple comparison between Rényi accountants, focusing on their one-step Rényi DP bounds. Namely, we consider our bound (Theorem 1) and bounds from [WBK21] and [BEBP24], comparing their asymptotic expansions in the subsampling rate p. As highlighted in [BEBP24, Section 3.4], the one-step Rényi DP bound ρW from [WBK21, The2 orem 9] satisfies ρW = 2α(e4/σ − 1) p2 + Oα,σ ( p3 ), whereas the one-step Rényi bound ρB from 2 2 [BEBP24, Theorem 3.4] satisfies ρB = α(e4/σ − e2/σ ) p2 + Oα,σ ( p3 ). Thus, [BEBP24] provides an improvement by a factor of roughly 4 (leading term of 8αp2 /σ2 versus 2αp2 /σ2 , for large σ) over [WBK21] in Rényi DP. In the following, we present the asymptotic expansion of our bound (5) in p. Notably, while its 2 2 leading order term α(e4/σ − e2/σ ) p2 is exactly the same as that in [BEBP24], its next order term 6 This choice of α is loosely based on first-order optimality: it is straightforward to check that the derivative of (7)

being 0 is equivalent to λα − (ε + λ/2) − log(α/(α − 1)) = 0. For α = 1 + ε/λ, this last line is equal to λ/2 − log(1 + λ/ε) which is close to 0 for small λ.

σ=3 1 × 10

−3

Our bounds, p = 0.005 Expansion (ours), p = 0.005 Birrell et al., p = 0.005 Expansion (Birrell et al.), p = 0.005 Our bounds, p = 0.01 Expansion (ours), p = 0.01 Birrell et al., p = 0.01 Expansion (Birrell et al.), p = 0.01

Rényi DP

8 × 10−4 6 × 10−4 4 × 10−4 2 × 10−4 0 5

10 Rényi order α

Figure 5: Illustration of Rényi DP bounds and their asymptotic expansions (Proposition 5, truncated at p3 terms). For [BEBP24], we set the tuning parameter to be m = 4. The actual bounds are close to the asymptotic expansions when the Rényi order α is small, but they deviate more as α increases, in particular for the bounds from [BEBP24]. (cubic in p) is strictly smaller. We remark that the bound from [BEBP24] has a tuning order m that controls the degree of the Taylor expansion in their result, and m ≥ 4 is explicitly suggested. Proposition 5. The one-step Rényi DP bound ρ = ρ(α, p, 2/σ ) from (5) satisfies 4 2 8 4 2 α 12 ρ = α(e σ2 − e σ2 ) p2 − (e σ2 − e σ2 − 2e σ2 + 2e σ2 ) p3 + Oα,σ ( p4 ) , 2

whereas the one-step Rényi DP bound ρ B from [BEBP24] (for any tuning order m ≥ 4) satisfies q 4 2 4 24 12 4 α ( α + 2) 2 2 2 σ σ ρ B = α(e − e ) p + (e σ2 − 1)(e σ2 − 4e σ2 + 6e σ2 − 3) p3 + Oα,σ ( p4 ) . 2

(8)

(9)

See Appendix A.5 for its proof. It can be checked that for our bound, the third-order term is strictly negative, whereas the bound from [BEBP24] has a strictly positive third-order term. This is consistent with the difference between the plots in Figure 3: for larger p, the bound from [BEBP24] is further from our bound, as the difference between the p3 terms becomes more prominent. Figure 5 illustrates the asymptotic expansions (up to p3 terms) as well as their limitations, where their quality of approximation depends on other hyperparameters.

Discussion

In this work, we studied Rényi accountants and lossless accountants for DP-SGD with fixed-size batches under replace adjacency. In particular, we characterized the privacy guarantee of a Rényi accountant as the value of a one-dimensional problem, and provided numerical illustrations as well as theoretical explanations on how it can improve over privacy guarantees from lossless accountants throughout different hyperparameter settings. An interesting follow-up question is to study whether the notion of hockey-stick dominating pair (Definition 3) can be relaxed, e.g., for inequalities in γ holding for a subset of [0, ∞). While 11

such a modification is known to be invalid if done “naı̈vely” [LRKS25, Section 7], it may be possible that there are other valid approaches, especially for specific mechanisms. More generally, one can ask what types of divergences can be used for privacy accounting—e.g., for handling data processing inequality and composition [MPST21, CCY26]. At a fundamental level, we believe that understanding the powers and limits of different privacy accountants is an important question for both theorists and practitioners of differential privacy.

AI use We used OpenAI’s GPT-5.6 to assist with generating new content for this paper, including formulating mathematical claims, writing code for numerical experiments, and proofreading. We reviewed and verified all AI-assisted content, and all writing in the main text and appendix was prepared by the authors who take full responsibility for the content of the paper.

References [ABD+ 23] Temilola Adeleye, Skye Berghel, Damien Desfontaines, Michael Hay, Isaac Johnson, Cléo Lemoisson, Ashwin Machanavajjhala, Tom Magerlein, Gabriele Modena, David Pujol, Daniel Simmons-Marengo, and Hal Triedman. Publishing Wikipedia usage data with strong privacy guarantees. arXiv preprint arXiv:2308.16298, 2023. [Abo18] John M. Abowd. The U.S. census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, page 2867, 2018. [ABT24] Jason M. Altschuler, Jinho Bok, and Kunal Talwar. On the privacy of noisy stochastic gradient descent for convex optimization. SIAM Journal on Computing, 53(4):969–1001, 2024. [ACG+ 16] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308–318, 2016. [AGA+ 23] Wael Alghamdi, Juan Felipe Gomez, Shahab Asoodeh, Flavio Calmon, Oliver Kosut, and Lalitha Sankar. The saddle-point method in differential privacy. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of PMLR, pages 508–528, 2023. [ALC+ 21] Shahab Asoodeh, Jiachun Liao, Flavio P. Calmon, Oliver Kosut, and Lalitha Sankar. Three variants of differential privacy: Lossless conversion and applications. IEEE Journal on Selected Areas in Information Theory, 2(1):208–222, 2021. [BBG+ 20] Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato. Hypothesis testing interpretations and Renyi differential privacy. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, volume 108 of PMLR, pages 2496–2506, 2020. [BDLS20] Zhiqi Bu, Jinshuo Dong, Qi Long, and Weijie Su. Deep learning with Gaussian differential privacy. Harvard Data Science Review, 2(3), 2020. 12

[BDRS18] Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, page 74–86, 2018. [BEBP24] 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 Advances in Neural Information Processing Systems, volume 37, pages 11087–11131, 2024. [BGL14] Dominique Bakry, Ivan Gentil, and Michel Ledoux. Analysis and geometry of Markov diffusion operators, volume 348 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer, Cham, 2014. [BL76] Herm Jan Brascamp and Elliott H. Lieb. On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation. Journal of Functional Analysis, 22(4):366–389, 1976. [Bla51] David Blackwell. Comparison of experiments. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, pages 93–102, 1951. [BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In International Conference on Theory of Cryptography, pages 635–658, 2016. [BSA24] Jinho Bok, Weijie J. Su, and Jason Altschuler. Shifted interpolation for differential privacy. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of PMLR, pages 4230–4266, 2024. [CCY26] Rodrigo Cruz, Flavio P. Calmon, and Qian Yu. A complete characterization of tensorizable f -divergences. arXiv preprint arXiv:2608.28556, 2026. [CDE+ 24] Rachel Cummings, Damien Desfontaines, David Evans, Roxana Geambasu, Yangsibo Huang, Matthew Jagielski, Peter Kairouz, Gautam Kamath, Sewoong Oh, Olga Ohrimenko, Nicolas Papernot, Ryan Rogers, Milan Shen, Shuang Song, Weijie Su, Andreas Terzis, Abhradeep Thakurta, Sergei Vassilvitskii, Yu-Xiang Wang, Li Xiong, Sergey Yekhanin, Da Yu, Huanyu Zhang, and Wanrong Zhang. Advancing differential privacy: Where we are now and future directions for real-world deployment. Harvard Data Science Review, 6(1), 2024. [CGH+ 25] Lynn Chua, Badih Ghazi, Charlie Harrison, Pritish Kamath, Ravi Kumar, Ethan Jacob Leeman, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Balls-and-bins sampling for DP-SGD. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of PMLR, pages 946–954, 2025. [CL25] Eli Chien and Pan Li. Convergent privacy loss of noisy-SGD without convexity and smoothness. In International Conference on Learning Representations, pages 12238–12260, 2025. [DGK+ 22] Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. In Proceedings on Privacy Enhancing Technologies, volume 2022, pages 552–570, 2022. 13

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, Berlin, 2006. [DÖ26] Andy Dong and Ayfer Özgür. Less random, more private: What is the optimal subsampling scheme for DP-SGD? arXiv preprint arXiv:2605.07072, 2026. [DR16] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016. [DRS22] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society, Series B, Statistical Methodology, 84(1):3–54, 2022. [Fle10] Bruno Fleury. Concentration in a thin Euclidean shell for log-concave measures. Journal of Functional Analysis, 259(4):832–841, 2010. [FMTT18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In Symposium on Foundations of Computer Science, pages 521– 532. 2018. [FVH25] Ferdinando Fioretto and Pascal Van Hentenryck, editors. Differential Privacy in Artificial Intelligence: From Theory to Practice. Emerald Publishing Limited, 2025. [GKKM22] Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Faster privacy accounting via evolving discretization. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of PMLR, pages 7470–7483, 2022. [GLW21] Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. In Advances in Neural Information Processing Systems, volume 34, pages 11631–11642, 2021. [KJH20] Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using FFT. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, volume 108 of PMLR, pages 2560–2569, 2020. [KR24] Weiwei Kong and Mónica Ribero. Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses. arXiv preprint arXiv:2407.05237, 2024. [LRKS25] Christian Janos Lebeda, Matthew Regehr, Gautam Kamath, and Thomas Steinke. Avoiding pitfalls for privacy accounting of subsampled mechanisms under composition. In 2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 996–1006, 2025. [MAB+ 26] Ryan McKenna, Galen Andrew, Borja Balle, Vadym Doroshenko, Arun Ganesh, Weiwei Kong, Alex Kurakin, Brendan McMahan, and Mikhail Pravilov. JAX-Privacy: A library for differentially private machine learning. arXiv preprint arXiv:2602.17861, 2026. [Mir17] Ilya Mironov. Rényi differential privacy. In Computer Security Foundations Symposium, pages 263–275, 2017. [MM18] Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 247–264, 2018. 14

[MPST21] Xiaosheng Mu, Luciano Pomatto, Philipp Strack, and Omer Tamuz. From Blackwell dominance in large samples to Rényi divergences and back again. Econometrica, 89(1):475–506, 2021. [MTZ19] Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint arXiv:1908.10530, 2019. [RGC+ 26] Anneliese Riess, Juan Felipe Gomez, Flavio Calmon, Julia Schnabel, and Georgios Kaissis. Optimal conversion from Rényi differential privacy to f -differential privacy. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of PMLR, pages 105180–105192, 2026. [RHL+ 26] Matthew Regehr, Bingshan Hu, Ethan Leeman, Pasin Manurangsi, Pierre Tholoniat, and Mathias Lécuyer. Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity. arXiv preprint arXiv:2602.15815, 2026. [SF25] Moshe Shenfeld and Vitaly Feldman. Privacy amplification by random allocation. In Advances in Neural Information Processing Systems, volume 38, pages 96188–96230, 2025. [SMM19] David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. In Proceedings on Privacy Enhancing Technologies, volume 2019, pages 245–269, 2019. [vEH14] Tim van Erven and Peter Harremoës. Rényi divergence and Kullback-Leibler divergence. IEEE Transactions on Information Theory, 60(7):3797–3820, 2014. [WBK21] Yu-Xiang Wang, Borja Balle, and Shiva Kasiviswanathan. Subsampled Rényi differential privacy and analytical moments accountant. Journal of Privacy and Confidentiality, 10(2), 2021. [XZA+ 23] Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher Choquette, Peter Kairouz, Brendan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of Gboard language models with differential privacy. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track), pages 629–639, 2023. [YS22] Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). In Advances in Neural Information Processing Systems, volume 35, pages 703–715, 2022. [YSS+ 21] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.12298, 2021. [ZDW22] Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of PMLR, pages 4782–4817, 2022.

Deferred details for proofs

A.1

Proof of Theorem 1

The proof proceeds with successive steps of simplifying the problem (2). Reduction with respect to Loewner order. We first claim that it suffices to consider positive semidefinite matrices that are maximal in the Loewner order. For that, let a′ , b′ ∈ Rd be such that ′ 2 ∥ a∥2 ⟨ a, b⟩ ∥a ∥ ⟨ a′ , b′ ⟩ ⪯ , ⟨ a, b⟩ ∥b∥2 ⟨ a ′ , b ′ ⟩ ∥ b ′ ∥2 or equivalently, ∥sa + tb∥2 ≤ ∥sa′ + tb′ ∥2 for all s, t ∈ R. Consider a linear map A : Rd → Rd such that A(sa′ + tb′ ) = sa + tb for all s, t ∈ R,

A(u′ ) = 0 for all u′ ∈ span{ a′ , b′ }⊥ .

Then A is well-defined, since sa′ + tb′ = 0 implies sa + tb = 0. Furthermore, A T A ⪯ Id because for any x ∈ Rd , writing as x = sa′ + tb′ + x ⊥ with x ⊥ ∈ span{ a′ , b′ }⊥ we have x T A T Ax = ∥sa + tb∥2 ≤ ∥sa′ + tb′ ∥2 ≤ ∥sa′ + tb′ + x ⊥ ∥2 = ∥ x ∥2 . Now consider a (randomized) post-processing map z 7→ Az + N (0, Id − AA T ) (note that Id − AA T ⪰ 0, from A T A ⪯ Id ). Then from its definition, a′ Ber( p) + N (0, Id ) and b′ Ber( p) + N (0, Id ) are respectively mapped by this post-processing to aBer( p) + N (0, Id ) and bBer( p) + N (0, Id ). By data processing inequality, Dα ( aBer( p) + N (0, Id )∥bBer( p) + N (0, Id )) ≤ Dα ( a′ Ber( p) + N (0, Id )∥b′ Ber( p) + N (0, Id )) Reduction to d = 2. For each fixed a, b, maximizing the objective in (2) is equivalent to maximizing 2 2 exp((α − 1)ρ(α, p, ∆)) = E[(1 − p + pe⟨a,Z⟩−∥a∥ /2 )α (1 − p + pe⟨b,Z⟩−∥b∥ /2 )1−α ] , (10) where Z ∼ N (0, Id ) . In particular, (10) only depends on the joint distribution(⟨ a, Z ⟩, ⟨b, Z ⟩) ∼ 2 2 ∥ a∥ ⟨ a, b⟩ ∥ a∥ ⟨ a, b⟩ N 0, . By reparametrizing the covariance matrix as Σ ≜ , it ⟨ a, b⟩ ∥b∥2 ⟨ a, b⟩ ∥b∥2 suffices to maximize (10) over all 2 × 2 positive semidefinite matrices Σ. Further reduction within 2 × 2 covariances. The constraints ∥ a∥ ≤ ∆, ∥b∥ ≤ ∆, ∥ a − b∥ ≤ ∆ are together equivalent to Σ11 ≤ ∆2 , Σ22 ≤ ∆2 , Σ11 + Σ22 − 2Σ12 ≤ ∆2 . First, it suffices to consider Σ such that at least two of the inequalities are equalities. Indeed, if 0 0 Σ22 < ∆2 and Σ11 + Σ22 − 2Σ12 < ∆2 , one can consider Σ + ε for a sufficiently small ε > 0, 0 1 which dominates Σ in the Loewner order and still satisfies the constraints; a similar argument 2 2 2 2 applies 11 < ∆ and Σ11 + Σ22 − 2Σ12 < ∆ . If Σ11 < ∆ and Σ22 < ∆ , one can consider if Σ 1 1 Σ+ε . 1 1 16

Thus, we have three (possibly overlapping) cases: Σ11 ≤ ∆2 , Σ22 = ∆2 , Σ11 + Σ22 − 2Σ12 = ∆2

(11)

Σ11 = ∆ , Σ22 = ∆ , Σ11 + Σ22 − 2Σ12 ≤ ∆ .

(13)

Σ11 = ∆2 , Σ22 ≤ ∆2 , Σ11 + Σ22 − 2Σ12 = ∆2 2

(12)

The third case (13) is redundant: the partial derivative of (10) with respect to Σ12 is equal to 2

α(1 − α) p2 E[e⟨a,Z⟩−∥a∥ /2 (1 − p + pe⟨a,Z⟩−∥a∥ /2 )α−1 × e⟨b,Z⟩−∥b∥ /2 (1 − p + pe⟨b,Z⟩−∥b∥ /2 )−α ] , which is negative. Combined with Σ12 ≥ ∆2 /2 from (13), it follows that (10) is maximized at Σ12 = ∆2 /2 in this case. This implies Σ11 + Σ22 − 2Σ12 = ∆2 , and hence the case (13) subsumed in the first two cases (11) and (12). For √ (11), without loss of generality we can parametrize as (with d = 2) b = ∆(1, 0) and a = ∆(u, 2u − u2 ) for some u ∈ [0, 1/2]. Thus the maximum of (10) subject to (11) is equal to p max Dα ∆(u, 2u − u2 ) × Ber( p) + N (0, I2 ) ∆(1, 0) × Ber( p) + N (0, I2 ) . u∈[0,1/2]

√ Similarly, for (12) we can let a = ∆(1, 0) and b = ∆(u, 2u − u2 ); the maximum of (10) subject to (12) is then equal to p max Dα ∆(1, 0) × Ber( p) + N (0, I2 ) ∆(u, 2u − u2 ) × Ber( p) + N (0, I2 ) . u∈[0,1/2]

We show that the latter is always at least as large as the former, i.e., it only suffices to consider the second case (12). Lemma 4. For any u ∈ [0, 1/2], p Dα ∆(1, 0) × Ber( p) + N (0, I2 ) ∆(u, 2u − u2 ) × Ber( p) + N (0, I2 ) p ≥ Dα ∆(u, 2u − u2 ) × Ber( p) + N (0, I2 ) ∆(1, 0) × Ber( p) + N (0, I2 ) . See Appendix A.1.1 for its proof. This completes the proof of the theorem.

A.1.1

Proof of Lemma 4 α R dP Since ( ω ) dQ(ω ) = exp((α − 1) Dα ( P∥ Q)), it suffices to compare the integrals. Let a = dQ √ ∆(1, 0) and b = ∆(u, 2u − u2 ) (with u ∈ [0, 1/2]); for this subsection only, we write ϕ( x ) to denote specifically the density of N (0, I2 ) at x ∈ R2 . Furthermore, let ℓ be the perpendicular bisector of the line segment ( a, b). Then there are two halfspaces determined by ℓ, namely: a+b H + ≜ x ∈ R2 : b − a, x − ≤0 , 2 a+b − 2 H ≜ x ∈ R : b − a, x − ≥0 . 2

Finally, define R : R2 → R2 to be the √ reflection across ℓ. Then the integral corresponding to Dα (∆(1, 0) × Ber( p) + N (0, I2 )∥∆(u, 2u − u2 ) × Ber( p) + N (0, I2 )) is Z

((1 − p)ϕ( x ) + pϕ( x − a))α ((1 − p)ϕ( x ) + pϕ( x − b))1−α dx

H+

+ =

H−

H+

((1 − p)ϕ( x ) + pϕ( x − a))α ((1 − p)ϕ( x ) + pϕ( x − b))1−α dx ((1 − p)ϕ(y) + pϕ(y − a))α ((1 − p)ϕ(y) + pϕ(y − b))1−α dy

((1 − p)ϕ( x ) + pϕ( x − a))α ((1 − p)ϕ( x ) + pϕ( x − b))1−α dx

H+

((1 − p)ϕ( R( x )) + pϕ( x − b))α ((1 − p)ϕ( R( x )) + pϕ( x − a))1−α dx ,

where the second equality holds as R is the reflection across ℓ (y = R( x ) ⇒ R( a) = b, R(b) = a). √ Similarly, the integral corresponding to Dα (∆(u, 2u − u2 ) × Ber( p) + N (0, I2 )∥∆(1, 0) × Ber( p) + N (0, I2 )) is Z

((1 − p)ϕ( x ) + pϕ( x − b))α ((1 − p)ϕ( x ) + pϕ( x − a))1−α dx

H+

+ =

H−

H+

((1 − p)ϕ( x ) + pϕ( x − b))α ((1 − p)ϕ( x ) + pϕ( x − a))1−α dx ((1 − p)ϕ(y) + pϕ(y − b))α ((1 − p)ϕ(y) + pϕ(y − a))1−α dy

((1 − p)ϕ( x ) + pϕ( x − b))α ((1 − p)ϕ( x ) + pϕ( x − a))1−α dx

H+

((1 − p)ϕ( R( x )) + pϕ( x − a))α ((1 − p)ϕ( R( x )) + pϕ( x − b))1−α dx .

Then their difference can be written as Z

((1 − p)ϕ( x ) + pϕ( x − a))α ((1 − p)ϕ( x ) + pϕ( x − b))1−α dx

− =

H+

((1 − p)ϕ( x ) + pϕ( x − b))α ((1 − p)ϕ( x ) + pϕ( x − a))1−α dx

( f ((1 − p)ϕ( x ), pϕ( x − a), pϕ( x − b)) − f ((1 − p)ϕ( R( x )), pϕ( x − a), pϕ( x − b))) dx ,

(14)

where f (u, v, w) ≜ (u + v)α (u + w)1−α − (u + w)α (u + v)1−α for u, v, w > 0.

We claim that for each fixed v, w with v ≥ w, u 7→ f (u, v, w) is decreasing. To see this, by writing t ≜ (u + v)/(u + w) ≥ 1 we have f (u, v, w) = (u + w)(tα − t1−α ) = (v − w)

t α − t 1− α , t−1

where the function g(t) ≜ tα − t1−α is convex for t ≥ 1. Thus, t 7→ (tα − t1−α )/(t − 1) = ( g(t) − g(1))/(t − 1) is increasing in t. Since t is decreasing in u, f is decreasing in u, proving the claim. Going back to (14), it is straightforward to check that for x ∈ H + , ∥ x − a∥ ≤ ∥ x − b∥ (since a ∈ H + ) and ∥ R( x )∥ ≤ ∥ x ∥ (since 0 ∈ H − , from ∥ a∥2 ≥ ∥b∥2 ). These respectively imply ϕ( x − a) ≥ ϕ( x − b) and (1 − p)ϕ( x ) ≤ (1 − p)ϕ( R( x )). Combining these with the aforementioned claim on f (with u = (1 − p)ϕ( x ) or (1 − p)ϕ( R( x )) and v = pϕ( x − a), w = pϕ( x − b)), we have f ((1 − p)ϕ( x ), pϕ( x − a), pϕ( x − b)) − f ((1 − p)ϕ( R( x )), pϕ( x − a), pϕ( x − b)) ≥ 0 ,

implying that (14) is nonnegative, as desired. 18

A.2

Derivative calculations

Here, we record additional notation and details for F and its derivatives that are used throughout our proofs. The calculations in this subsection serve as preliminaries for mathematical arguments in other parts. The one-step Rényi bound ρ(α, p, ∆) in (5) can be written as exp((α − 1)ρ(α, p, ∆)) = max F (u) , where with a = ∆(1, 0), b = ∆(u,

√

u∈[0,1/2]

2u − u2 ) and Z ∼ N (0, I2 ), F is defined as

F (u) ≜ E[(1 − p + p exp(⟨ a, Z ⟩ − ∥ a∥2 /2))α (1 − p + p exp(⟨b, Z ⟩ − ∥b∥2 /2))1−α ] . (15) −1/2 1 u X 2 2 x α y 1 − α ∼N ∆ ,∆ , First, by letting h( x, y) ≜ (1 − p + pe ) (1 − p + pe ) and −u u 2u Y we have F (u) = E[h( X, Y )] , where from Gaussian integration by parts, 2 ∂ ∂ ∂2 2 F (u) = −∆ E h( X, Y ) + ∆ E h( X, Y ) + 2 h( X, Y ) ∂y ∂x∂y ∂y 2 ∂2 ∂ ∂ + = ∆2 E − h( X, Y ) . 2 ∂y ∂x∂y ∂y ′

(16)

As notation, we define v( x ) ≜ pe x /(1 − p + pe x ), w(y) ≜ pey /(1 − p + pey ). In particular, they satisfy 0 ≤ v( x ), w(y) ≤ 1 and ∂ v( x ) = v( x )(1 − v( x )), ∂x

∂ w(y) = w(y)(1 − w(y)) . ∂y

We will often write v = v( x ) and w = w(y) for conciseness. It is straightforward to see that ∂ h( x, y) = αvh( x, y), ∂x

∂ h( x, y) = (1 − α)wh( x, y) , ∂y

and ∂2 h( x, y) = αv(1 + (α − 1)v)h( x, y), ∂x2

∂2 h( x, y) = α(1 − α)vwh( x, y), ∂x∂y

∂2 h( x, y) = (1 − α)w(1 − αw)h( x, y) . ∂y2 Based on those derivatives, for (16) we have F ′ (u) = ∆2 α(α − 1)E[w(Y )(w(Y ) − v( X ))h( X, Y )] .

(17)

Similarly, we have ∂2 ∂2 ∂ F ( u ) = ∆ α ( α − 1)E + − w(w − v)h( X, Y ) ∂y2 ∂x∂y ∂y ∂ ∂ 4 3 2 2 = ∆ α ( α − 1)E + − 1 (−(α + 1)w + αw v + 2w − wv)h( X, Y ) ∂y ∂x 4 = ∆ α(α − 1)E − 3(α + 1)w3 (1 − w) + 2αw2 (1 − w)v + 4w2 (1 − w) − w(1 − w)v + (α − 1) (α + 1)w4 − αvw3 − 2w3 + vw2 + αw2 v(1 − v) − wv(1 − v)w2 2 2 2 3 2 2 + αv(−(α + 1)w + αw v + 2w − wv) + (α + 1)w − αw v − 2w + wv h( X, Y ) , ′′

which implies ′′

F ( u ) = ∆ α ( α − 1)E

A.3

(α + 1)(α + 2)w4 − 2α(α + 1)w3 v + α(α − 1)w2 v2 − 4(α + 1)w3 2 2 2 + 5αw v − (α − 1)wv + 2w − wv h( X, Y ) . 4

(18)

Proof of Proposition 2

Throughout the proof, as in the earlier parts we use ∆ = 2/σ for notational convenience. As noted in Appendix A.2, we characterize the problem (5) in terms of the function F (15) (see also the notations and calculations there for reference). (a) We show that (15) (hence (5)) is maximized at u = 0 under a slightly more general condition, that is, (α − 1)(1 − p)∆2 α p exp ≥ . (19) 2 α−1 Indeed, if α ≥ 2 then (19) is implied by p exp((α − 1)(1 − p)∆2 /2) ≥ 2 ⇔ α ≥ 1 + 2 log(2/p)/(∆2 (1 − p)). For (15), we have 2

F (u) = E[(1 − p + pe⟨a,Z⟩−∥a∥ /2 )α (1 − p + pe⟨b,Z⟩−∥b∥ /2 )1−α ] 2

≤ E[(1 − p + pe⟨a,Z⟩−∥a∥ /2 )α (e p⟨b,Z⟩− p∥b∥ /2 )1−α ] 2

= e(α−1) p∆ u E[(1 − p + pe⟨a,Z⟩−∥a∥ /2 )α e−(α−1) p⟨b,Z⟩ ]

= e(α−1) p∆ u+(α−1) p ∆ u E[(1 − p + pe⟨a,Z−(α−1) pb⟩−∥a∥ /2 )α ] 2

2 2

= e(α−1) p∆ u+(α−1) p ∆ u E[(1 − p + e−(α−1) p∆ u × pe⟨a,Z⟩−∥a∥ /2 )α ] , 2

2 2

where the first inequality is from Jensen’s inequality 1 − p + pe x ≥ e px (and 1 − α < 0); the first equality is from ∥b∥2 = 2∆2 u, the second equality is from considering Gaussian shift Z → Z + (α − 1) pb, and the last equality is from ⟨ a, b⟩ = ∆2 u. The last line can be further bounded as e(α−1) p∆ u+(α−1) p ∆ u E[(1 − p + e−(α−1) p∆ u × pe⟨a,Z⟩−∥a∥ /2 )α ] h α i 2 2 2 2 2 2 2 = e(α−1) p∆ u+(α−1) p ∆ u E e−(α−1) p∆ u (1 − p + pe⟨a,Z⟩−∥a∥ /2 ) + (1 − p)(1 − e−(α−1) p∆ u ) α 2 2 2 2 2 2 ≤ e(α−1) p∆ u+(α−1) p ∆ u e−(α−1) p∆ u F (0)1/α + (1 − p)(1 − e−(α−1) p∆ u ) , 2

2 2

by Minkowski’s inequality (on Lα norm) and F (0) = E[(1 − p + pe⟨a,Z⟩−∥a∥ /2 )α ]. Thus, we have α 2 2 2 2 2 2 F (u) (20) ≤ e(α−1) p∆ u+(α−1) p ∆ u e−(α−1) p∆ u + (1 − p) F (0)−1/α (1 − e−(α−1) p∆ u ) . F (0) In particular, the right hand side can be concisely written as a function of x ≜ (α − 1) p∆2 u: α T ( x ) ≜ e(1+(α−1) p)x e− x + (1 − p) F (0)−1/α (1 − e−x ) .

From

log T ( x ) = (1 + (α − 1) p) x + α log(e− x + (1 − p) F (0)−1/α (1 − e− x ))

= −(α − 1)(1 − p) x + α log(1 + (1 − p) F (0)−1/α (e x − 1)) ,

we have

α(1 − p) F (0)−1/α e x T ( x ) = T ( x ) −(α − 1)(1 − p) + 1 + (1 − p) F (0)−1/α (e x − 1) ′

≤ T ( x )(−(α − 1)(1 − p) + α(1 − p) F (0)−1/α e x ) αe x ≤ (1 − p) T ( x ) −(α − 1) + (α−1)∆2 /2 , pe

where the last inequality is from F (0)1/α ≥

E[( pe⟨a,Z⟩−∥a∥ /2 )α ]

x = (α − 1) p∆2 u ≤ (α − 1) p∆2 /2, the last line is at most 0 if 2

αe(α−1) p∆ /2 −(α − 1) + (α−1)∆2 /2 ≤ 0 ⇔ p exp pe

1/α

(α − 1)(1 − p)∆2 2

= pe(α−1)∆ /2 . Since 2

≥

α . α−1

Thus, (19) implies T ′ ( x ) ≤ 0; since T (0) = 1, from (20) we have F (u)/F (0) ≤ 1 for all u ∈ [0, 1/2], as desired. (b) For F as in (15), its first and second derivatives can be written as (see Appendix A.2 and the notations there) F ′ (u) = ∆2 α(α − 1)E[w(w − v)h( X, Y )], ′′ 4 F (u) = ∆ α(α − 1)E (α + 1)(α + 2)w4 − 2α(α + 1)w3 v + α(α − 1)w2 v2 − 4(α + 1)w3 2 2 2 + 5αw v − (α − 1)wv + 2w − wv h( X, Y ) . We claim that under the stated condition, for u ∈ (0, 1/2) if F ′ (u) = 0 then F ′′ (u) > 0. This indeed implies that the maximum only occurs at the boundary {0, 1/2}.

The derivatives can be expressed as sums of expected monomials (in w, v) under the tilted measure e [ f ( X, Y )] ≜ E[ f ( X, Y )w(Y )h( X, Y )] for f ≥ 0 . (21) E E[w(Y )h( X, Y )] 21

Then e [w − v] = 0, F ′ (u) = 0 ⇔ E e [q(v, w)] > 0 , F ′′ (u) > 0 ⇔ E

where q(v, w) ≜ (α + 1)(α + 2)w3 − 2α(α + 1)w2 v + α(α − 1)wv2 − 4(α + 1)w2 + 5αwv − (α − 1)v2 + 2w − v. Expanding q(v, w) in descending order (in v − w), we have q(v, w) = (α − 1)(αw − 1)(v − w)2 + (w(3α + 2 − 4αw) − 1)(v − w) + w(1 − w)(1 − 2w) . Thus e [q(v, w)] = (α − 1)E e [(αw − 1)(v − w)2 ] + E e [w(3α + 2 − 4αw)(v − w)] + E e [w(1 − w)(1 − 2w)] , E (22) e [v − w] = 0 from F ′ (u) = 0. where we used E e is that the density of ( X, Y ) is strongly The key property that we use for the tilted measure P log-concave, up to a change of basis. Claim. For u ∈ (0, 1/2), if α∆2 /4 < 1 then the Hessian of the negative log-density of ( X, Y ) under −1 1 u 2 2 e P is bounded below (in Loewner order) by (1 − α∆ /4) ∆ . u 2u

e ( X, Y ) has density proportional to w(y)h( x, y)ψ( x, y) ∝ exp(y + α log(1 − Proof. Under P, −1/2 1 u x y 2 2 p + pe ) − α log(1 − p + pe ))ψ( x, y) where ψ( x, y) is the density for N ∆ ,∆ . u 2u −u Thus its negative log-density is (up to an additive normalization constant)

−y − α log(1 − p + pe x ) + α log(1 − p + pey ) − log ψ( x, y) , whose Hessian is −1 u 1 0 0 0 2 1 − αv( x )(1 − v( x )) + αw(y)(1 − w(y)) + ∆ u 2u 0 0 0 1 − 1 α∆2 1 u ∆2 . ⪰ 1− u 2u 4

Here, the inequality holds from v( x )(1 − v( x )) ≤ 1/4 and

1 u u 2u

−1

⪰

(23)

1 0 . 0 0

In particular, this strong log-concavity is useful for bounding the expectations of polynomials in v, w. e [w] = E e [v], then Lemma 5 (Polynomial bounds). If E ∆2 e [ w2 ] ≤ (E e [w])2 exp E , 1 − α∆2 /4 2 2 2∆ ∆ 2 2 e [(v − w) ] ≤ (E e [w]) E exp , 1 − α∆2 /4 1 − α∆2 /4 √ √ 2 2 ( 3 2α + 2 2 ) ∆ ∆ 2 e [w(3α + 2 − 4αw)(v − w)]| ≤ (E e [w]) |E exp . 1 − α∆2 /4 1 − α∆2 /4 22

(24) (25) (26)

The proof is deferred to Appendix A.3.1. By the lemma, for (22) we have 2 e [(αw − 1)(v − w) ] ≥ −(α − 1)E e [(v − w) ] ≥ −(E e [w])2 2(α − 1)∆ exp ( α − 1)E 1 − α∆2 /4 2

∆2 1 − α∆2 /4

√ 2 2 ∆ 2α + 2 2 ) ∆ e [w(3α + 2 − 4αw)(v − w)] ≥ −(E e [w]) exp , E 1 − α∆2 /4 1 − α∆2 /4 ∆2 2 e e e e E[w(1 − w)(1 − 2w)] > E[w − 3w ] ≥ (E[w]) 1 − 3E[w] exp , 1 − α∆2 /4 2 (3

√

respectively by (25), (26), and (24). Thus, e e e E[q(v, w)] > (E[w]) 1 − (E[w]) exp

∆2 1 − α∆2 /4

√

∆2 3 + ((3 2 + 2)α + 2 2 − 2) 1 − α∆2 /4 (27) e In order to show that the right hand side is nonnegative, it suffices to upper bound E[w]. First, we have Y pe p u∆2 p ∆2 e e e e E[ w ] ≤ E ≤ exp E[Y ] + ≤ exp E[Y ] + , 1− p 1− p 1 − α∆2 /4 1− p 2 − α∆2 /2 where the second inequality is from Herbst’s argument [BGL14, Proposition 5.4.1] and the e [Y ] , aforementioned strong log-concavity, and the last inequality is from u ≤ 1/2. For E Stein’s lemma yields X −∆2 /2 u 2 1 E − w(Y )h( X, Y ) = ∆ E[∇(w(Y )h( X, Y ))] Y −u∆2 u 2u X −∆2 /2 u e 2 1 e ⇒E − =∆ E [∇ log w(Y )h( X, Y )] Y −u∆2 u 2u e [v( X )] u αE 2 1 =∆ e [w(Y )] , u 2u 1 − αE

where the last equality follows from derivative calculations in Appendix A.2. Thus e [Y ] = ∆ 2 u ( 1 + α E e [v] − 2αE e [w]) = ∆2 u(1 − αE e [w]) ≤ ∆ , E 2 2

e [v] = E e [w] and the inequality is from E e [w] ≥ 0, u ≤ 1/2. where the last equality is from E This implies 2 p ∆ ∆2 e E[ w ] ≤ exp + , 1− p 2 2 − α∆2 /2

and thus for (27), if 2 √ √ p ∆ 3∆2 ∆2 exp + 3 + ((3 2 + 2)α + 2 2 − 2) ≤ 1, 1− p 2 2 − α∆2 /2 1 − α∆2 /4

e [q(v, w)] > 0, as desired. The form displayed in Proposition 2 is obtained by we have E plugging in ∆ = 2/σ. 23

A.3.1

Proof of Lemma 5

g etc. to denote that the underlying measure is the tilted measure g Cov, We use notation such as Var, e P (21). The Hessian lower bound (23) for the negative log-density implies the following:7 • By Brascamp-Lieb inequality [BL76, Theorem 4.1], 1 g [ G ( X, Y )] ≤ e ∇ G ( X, Y )T ∆2 1 u Var E ∇ G ( X, Y ) . u 2u 1 − α∆2 /4

• By log-Sobolev inequality [BGL14, Corollary 5.7.2], 2 u 2 T 2 1 g e Ent[ G ( X, Y ) ] ≤ E ∇ G ( X, Y ) ∆ ∇ G ( X, Y ) , u 2u 1 − α∆2 /4

(28)

(29)

g [ G ( X, Y )2 ] ≜ E e [ G ( X, Y )2 log G ( X, Y )2 ] − E e [ G ( X, Y )2 ] log E e [ G ( X, Y )2 ]. where Ent

For (24), it is a reverse Hölder inequality which can be obtained from the following standard techniques (see [Fle10, Equation 15], for example): (29) with G ( x, y) = w(y)r/2 implies 2 r 2 ∆2 2 e 2∆2 u × r wr (1 − w)2 ≤ e [ wr ] , × E E 2 1 − α∆ /4 4 2 − α∆2 /2 0 1 2 ≤ 1. From d r] e since ∇ G ( x, y) = and u ≤ 1/2, ( 1 − w ) log E [ w = dr r (r/2)wr/2 (1 − w) g [ wr ] ≤ Ent

g [ wr ] Ent e [wr ] , integration over r ∈ [1, 2] yields r2 E

1 ∆2 ∆2 e [w2 ] − log E e [w] ≤ e [ w2 ] ≤ (E e [w])2 exp log E ⇒ E . 2 2 − α∆2 /2 1 − α∆2 /4 ∆2 e [ v2 ] ≤ (E e [v])2 exp Note that the same arguments yield E . 1−α∆2 /4 v (1 − v ) e [v − w] = 0. By (28) with G ( x, y) = For (25), we have ∇(v − w) = and E − w (1 − w ) v ( x ) − w ( y ), ∆2 e [v2 (1 − v)2 − 2uv(1 − v)w(1 − w) + 2uw2 (1 − w)2 ] E 1 − α∆2 /4 ∆2 2∆2 ∆2 2 2 2 e e ≤ E[v + w ] ≤ (E[v]) exp . 1 − α∆2 /4 1 − α∆2 /4 1 − α∆2 /4

g [v − w] ≤ e [(v − w)2 ] = Var E Finally, for (26) we have

g [w(3α + 2 − 4αw), v − w]| e [w(3α + 2 − 4αw)(v − w)]| = |Cov |E q g [w(3α + 2 − 4αw)]Var g [v − w] , ≤ Var

7 While the following inequalities are usually stated for Hessian lower bounds that are of the form cI (rather than for

anisotropic matrices as inour case), they readily extend to general positive definite matrices K by considering a change x x 1/2 of basis 7→ K and the chain rule. y y

e [v − w] = 0 and the inequality is from Cauchy–Schwarz inequality. where the equality is from E Then, 1 e [2∆2 u × w2 (1 − w)2 (3α + 2 − 8αw)2 ] E 1 − α∆2 /4 2 2 (3α + 2)2 ∆2 e 2 ∆2 2 (3α + 2) ∆ e ≤ E[w ] ≤ (E[v]) exp . 1 − α∆2 /4 1 − α∆2 /4 1 − α∆2 /4

g [w(3α + 2 − 4αw)] ≤ Var

Here, the first inequality holds from (28), the second inequality holds from (1 − w)2 (3α + 2 − e [w2 ]. Combined with the 8αw)2 ≤ (3α + 2)2 , and the last inequality is from the earlier bound on E g [v − w], we have earlier bound (25) on Var √ 2 2 2 ( 3α + 2 ) ∆ ∆ 2 e [w(3α + 2 − 4αw)(v − w)]| ≤ (E e [v]) |E exp . 1 − α∆2 /4 1 − α∆2 /4 This completes the proof.

A.4

Proof of Proposition 3

Fix T, p, σ, δ and write ε in (6) as ε(α). By [vEH14, √ Corollary 2], for each u ∈ [0, 1/2] the map α 7→ (α − 1) Dα (∆(1, 0) × Ber( p) + N (0, I2 )∥∆(u, 2u − u2 ) × Ber( p) + N (0, I2 )) is convex over α ∈ (1, ∞). This implies that κ (α) ≜ (α − 1)ρ(α, p, ∆), as a pointwise supremum over u ∈ [0, 1/2] as in (5), is also convex. For ε(α) = we have

Tκ (α) + (α − 1) log(α − 1) − α log α − log δ , α−1

(30)

1 ∂2 ((α − 1) log(α − 1) − α log α − log δ) = > 0, 2 ∂α α ( α − 1)

implying that the numerator of (30) is strictly convex. Hence, for distinct α, α′ > 1 and 0 < s < 1,

(sα + (1 − s)α′ − 1)ε(sα + (1 − s)α′ ) < s(α − 1)ε(α) + (1 − s)(α′ − 1)ε(α′ ) ≤ (sα + (1 − s)α′ − 1)(ε(α) ∨ ε(α′ )) , implying that ε is strictly quasiconvex and hence has at most one minimizer in (1, ∞). Finally, we show that there indeed exists a finite minimizer. As α 7→ Tρ(α, p, ∆) is increasing by the monotonicity of Rényi divergence [vEH14, Theorem 3] and α 7→ log(1 − 1/α) − log(δα)/(α − 1) is increasing over α ∈ (1/δ, ∞) (from derivative calculation), their sum ε(α) is also increasing over α ∈ (1/δ, ∞). Furthermore, it is straightforward that limα→1 ε(α) = ∞. Combining those, ε has a unique finite minimizer, as desired.

A.5

Proof of Proposition 5

Recall that for (5) we have exp((α − 1)ρ(α, p, ∆)) = maxu∈[0,1/2] F (u), where F is as defined in (15). In particular, F can be written as F (u) = E[(1 + pA)α (1 + pB)1−α ] ,

√ 2 2 where A ≜ e⟨a,Z⟩−∥a∥ /2 − 1, B ≜ e⟨b,Z⟩−∥b∥ /2 − 1 (with a = ∆(1, 0), b = ∆(u, 2u − u2 ), Z ∼ N (0, I2 )). A key simplification in the small-p regime is that we can specify the maximizer of F. 25

Claim. For all sufficiently small p (as a function of α, ∆), u = 1/2 attains the maximum of F. Proof. We consider the Taylor expansion of F in p. The first derivative is ∂ F (u) = E[αA(1 + pA)α−1 (1 + pB)1−α − (α − 1) B(1 + pA)α−1 (1 + pB)−α ] , ∂p ∂ where ∂p F (u)

p =0

= αE[ A] − (α − 1)E[ B] = 0. Similarly, the second derivative is

∂2 F (u) = E[α(α − 1) A2 (1 + pA)α−2 (1 + pB)1−α ∂p2

− 2α(α − 1) AB(1 + pA)α−1 (1 + pB)−α + α(α − 1) B2 (1 + pA)α−1 (1 + pB)−α−1 ] , 2

∂ where ∂p 2 F (u)

= α(α − 1)E[( A − B)2 ] = α(α − 1)(e∆ − 2eu∆ + e2u∆ ) following from calcu2

p =0

lations for moment generating functions of Gaussians: E[( A − B)2 ] = E[e2⟨a,Z⟩−∥a∥ − 2e⟨a+b,Z⟩−∥a∥ /2−∥b∥ /2 + e2⟨b,Z⟩−∥b∥ ] = e∆ − 2eu∆ + e2u∆ . 2

(31)

Then by Taylor’s theorem at p = 0, F (u) = 1 + where

2 2 α ( α − 1 ) ∆2 (e − 2eu∆ + e2u∆ ) p2 + Rα,∆ ( p, u) , 2

1 Rα,∆ ( p, u) ≜ 2

Z p 0

(z − p)

∂3 F (u) dz . ∂p3 p=z

In particular, let p0 (α, ∆) > 0 be such that sup p∈[0,p0 (α,∆)],u∈(0,1/2] |(∂4 /(∂u∂p3 )) F (u)| ≤ Cα,∆ for some Cα,∆ > 0. Such p0 (α, ∆) and Cα,∆ always exist: by Gaussian integration by parts as in (16), we have 3 2 ∂2 ∂ ∂4 2 2 ∂ α 1− α F ( u ) = ∆ E (1 + B ) + (1 + A)(1 + B) (1 + pA) (1 + pB) , ∂u∂p3 ∂B2 ∂A∂B ∂p3 ′ (1 − p ( α, ∆ ))c (1 + whose absolute value is at most a sum of finitely many terms of the form Cα,∆ 0 ′ . E[(1 + A) a (1 + B)b ]) for finite a, b, c and Cα,∆ By the mean value theorem,

∂3 ∂3 (z − p) F (1/2) − 3 F (u) dz ∂p3 ∂p p=z p=z 0 ! Z 4 ∂ 1 p 1 2 ≤ (z − p) sup F (u) − u dz 3 2 0 2 p∈[0,p0 (α,∆)],u∈(0,1/2] ∂u∂p C p3 1 −u , ≤ α,∆ 6 2

1 | Rα,∆ ( p, 1/2) − Rα,∆ ( p, u)| = 2

Z p

which implies 2 2 2 α ( α − 1 ) ∆2 (e + 2eu∆ − e2u∆ − 2e∆ /2 ) p2 + Rα,∆ ( p, 1/2) − Rα,∆ ( p, u) 2 2 2 2 α(α − 1) ∆2 /2 (e − eu∆ )(e∆ /2 + eu∆ − 2) p2 + Rα,∆ ( p, 1/2) − Rα,∆ ( p, u) = 2 α ( α − 1) 2 1 Cα,∆ p3 1 ∆2 /2 2 ≥ ∆ − u (e − 1) p − −u 2 2 6 2 1 α(α − 1) 2 ∆2 /2 C p − u p2 ∆ (e − 1) − α,∆ , = 2 2 6

F (1/2) − F (u) =

implying that for all sufficiently small p (as a function of α, ∆), F is maximized at u = 1/2 as desired. Given the claim, we consider the third-order Taylor expansion. From h ∂3 F ( u ) = α ( α − 1 ) E (α − 2) A3 (1 + pA)α−3 (1 + pB)1−α − 3(α − 1) A2 B(1 + pA)α−2 (1 + pB)−α ∂p3 i + 3αAB2 (1 + pA)α−1 (1 + pB)−α−1 − (α + 1) B3 (1 + pA)α (1 + pB)−α−2 , h ∂4 F ( u ) = α ( α − 1 ) E (α − 2)(α − 3) A4 (1 + pA)α−4 (1 + pB)1−α ∂p4

− 4(α − 1)(α − 2) A3 B(1 + pA)α−3 (1 + pB)−α + 6α(α − 1) A2 B2 (1 + pA)α−2 (1 + pB)−α−1 i − 4(α + 1)αAB3 (1 + pA)α−1 (1 + pB)−α−2 + (α + 2)(α + 1) B4 (1 + pA)α (1 + pB)−α−3 , 4

∂ it readily follows that sup p∈[0,p0 (α,∆)],u∈[0,1/2] ∂p 4 F ( u ) = Oα,∆ (1) uniformly over u ∈ [0, 1/2]. Fur-

thermore,

∂3 F (u) ∂p3

p =0

= α(α − 1)[(α − 2)E[ A3 ] − 3(α − 1)E[ A2 B] + 3αE[ AB2 ] − (α + 1)E[ B3 ]] ,

where E[ A3 ] = e3∆ − 3e∆ + 2, 2

E[ A2 B] = e(2u+1)∆ − 2eu∆ − e∆ + 2, 2

E[ AB2 ] = e4u∆ − e2u∆ − 2eu∆ + 2,

E[ B3 ] = e6u∆ − 3e2u∆ + 2 ,

from calculations similar to (31) based on moment generating functions. Then by Taylor’s theorem, 2 2 α ( α − 1 ) ∆2 F (u) = 1 + e − 2eu∆ + e2u∆ p2 2 2 2 2 2 2 2 2 α ( α − 1) + (α − 2)e3∆ − 3(α − 1)e(2u+1)∆ + 3αe4u∆ − (α + 1)e6u∆ + 3e∆ + 3e2u∆ − 6eu∆ p3 6 + Oα,∆ ( p4 ) . By the earlier claim, it suffices to consider u = 1/2 for maximizing F. Then exp((α − 1)ρ(α, p, ∆)) = 1 + α(α − 1)(e∆ − e∆ /2 ) p2 − 2

2 2 2 α(α − 1) 3∆2 (e − e2∆ − 2e∆ + 2e∆ /2 ) + Oα,∆ ( p4 ) , 2

from exp((α − 1)ρ(α, p, ∆)) = maxu∈[0,1/2] F (u). Plugging in ∆ = 2/σ, we obtain the first part of Proposition 5. The second part is based on the analytical expressions in [BEBP24]; here we only record relevant details. From [BEBP24, Theorem 3.4] with order m ≥ 4, the coefficient of p3 for the asymptotic expansion of exp((α − 1)ρB ) is given as p α2 (α − 1) Mσ,2 Mσ,4 2 p ! 2− j ! (32) j −1 3 α2 (α − 1) Mσ,2 Mσ,4 3 ℓ ℓ−1 α + − 1 , ×∑ 1 − 1 + ∏ ∏ 6 α − 1 ℓ= α α j j =0 0 ℓ=0 2

where Mσ,2 = e4/σ − 1, Mσ,4 = e24/σ − 4e12/σ + 6e4/σ − 3 from [BEBP24, Equation 41]. Thus (32) is equal to q ( α + 2) α ( α − 1) (e4/σ2 − 1)(e24/σ2 − 4e12/σ2 + 6e4/σ2 − 3) , 2 as desired. Converting this expansion into an expansion for ρB , we obtain the second part.

A.6

Proof of Corollary 2

We first show µ2 > λ. From their definitions (see Lemma 3 and Proposition 4), this is equivalent to showing 2 2 2 e4/σ Φ(3/σ ) + 3Φ(−1/σ ) − 2 > e4/σ − e2/σ . 2

Let f (y) ≜ e4y (Φ(3y) − 1) + 3Φ(−y) + e2y − 2. Then 2

f ′ (y) = 8ye4y (Φ(3y) − 1) + 3e4y ϕ(3y) − 3ϕ(−y) + 4ye2y 2

= 8ye4y (Φ(3y) − 1) + 4ye2y 2

= 4ye2y (1 − 2e2y Φ(−3y)) ≥ 4ye2y (1 − e−5y /2 ) > 0 , 2

for all y > 0; here the second equality holds from 3e4y ϕ(3y) = 3ϕ(y) = 3ϕ(−y), and the penulti2 mate inequality holds from standard Gaussian tail bound Φ(−3y) ≤ e−(9/2)y /2. Since f (0) = 0, this implies that f (1/σ) > 0 for all σ > 0, proving µ2 > λ. For the bound on log δ(ε) − log δL (ε), we combine an upper bound on log δ(ε) and a lower bound on log δL (ε): ε ε2 + − log ε + Oλ (1) , 2λ 2 ε2 ε log δL (ε) ≥ − 2 + − 2 log ε − Oµ (1) . 2µ 2 log δ(ε) ≤ −

Corollary 2 clearly follows from these two inequalities. From Proposition 4, we have λ ε2 ε δ(ε) ≤ exp − + , ε 2λ 2 which implies (33). For (34), recall the following standard inequality: 1 1 1 − 3 ϕ( x ) ≤ Φ(− x ) ≤ ϕ( x ) for all x > 0 . x x x 28

(33) (34)

For ε ≥ µ2 ∨ 16, using this inequality for Lemma 3 yields 1 ε µ 1 ε µ 1 ε − ϕ − −e × ϕ + δL (ε) ≥ ε/µ − µ/2 (ε/µ − µ/2)3 µ 2 ε/µ + µ/2 µ 2 1 1 1 ε µ = − − ϕ − ε/µ − µ/2 ε/µ + µ/2 (ε/µ − µ/2)3 µ 2 1 ε µ µ − ϕ − ≥ 2 2 2 3 ε /µ − µ /4 (ε/(2µ)) µ 2 3 3 3 µ µ ε µ µ ε µ ≥ − 2 ϕ − = 2ϕ − , ε2 2ε µ 2 2ε µ 2 where the second inequality holds from ε/µ − µ/2 ≥ ε/(2µ) ⇔ ε ≥ µ2 , and the last inequality holds from µ3 /(2ε2 ) ≥ 8µ3 /ε3 ⇔ ε ≥ 16. This implies (34), as desired.

Deferred details for numerical comparisons

B.1

Additional results

We record the values of ε for (ε, δ)-DP guarantees from different accountants over a grid of hyperparameters T ∈ {250, 500, 1000, 2000, 4000, 8000, 16000, 32000, 64000}, p ∈ {0.0025, 0.01, 0.04}, σ ∈ {1, 2, 3, 4, 6, 8} and δ ∈ {10−6 , 10−8 }. We omit values of ε for sets of hyperparameters where all accounting methods yield ε ≥ 20, as such large values are often considered as being outside of practically meaningful regime. In some cases, the bounds from [BEBP24] are excessively large due to the remainder terms in their Taylor expansion; we only record that ε ≥ 100 in those cases. As the main interest of this paper is to compare Rényi accountants against lossless accountants, the column named “Relative difference” in the tables records how small ε from our Rényi accountant (which always improves over other Rényi accountants covered here) is relative to ε from lossless accountants, in percentage. In particular, the percentages are colored green if they are negative (i.e., ε from our Rényi accountant is smaller) and colored red otherwise (i.e., ε from our Rényi accountant is larger). Our code for reproducing the numerics can be found at: https://github.com/jinhobok/renyi vs lossless dpsgd. The results are presented in Tables 1 through 6. Across those hyperparameter choices, our privacy bounds improve over those from lossless accountants, except for particular cases (if σ = 1, or T is small). In particular, those improvements generally become more prominent as the number of iterations increases, allowing longer training with better privacy guarantees. Relatedly, many of the settings where lossless accountants provide better privacy guarantees are when T is small, where the accounted privacy ε is already small (e.g., less than 1) across different accountants. Altogether, those results illustrate that a Rényi accountant can provide better privacy guarantees than lossless accountants.

Table 1: Accounted privacy ε for δ = 10−6 and p = 0.0025. σ

T 250 500 1000 2000 4000 8000 16000 ≥ 32000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000

Rényi accountants Lossless accountants Our bounds Birrell et al. Wang et al. 6.40 ≥ 100 6.84 5.10 6.84 ≥ 100 7.73 5.68 7.72 ≥ 100 9.51 6.53 9.49 ≥ 100 13.06 7.80 13.03 ≥ 100 15.16 9.76 15.77 ≥ 100 17.89 12.86 19.11 ≥ 100 23.35 17.87 ≥ 20 for all accountants 1.03 1.43 1.10 0.33 1.08 1.52 1.15 0.42 1.12 1.66 1.25 0.58 1.19 1.78 1.45 0.81 1.34 2.02 1.86 1.16 1.64 2.36 2.61 1.68 2.23 2.90 3.79 2.45 3.24 3.92 5.57 3.59 4.77 5.50 8.26 5.31 0.40 0.46 0.43 0.14 0.41 0.48 0.48 0.20 0.43 0.52 0.58 0.28 0.48 0.57 0.77 0.41 0.58 0.68 1.10 0.59 0.79 0.88 1.59 0.86 1.14 1.23 2.31 1.24 1.65 1.76 3.36 1.81 2.41 2.53 4.94 2.65 0.21 0.23 0.24 0.09 0.22 0.24 0.28 0.13 0.24 0.27 0.37 0.19 0.28 0.32 0.53 0.27 0.37 0.41 0.76 0.39 0.53 0.58 1.10 0.57 0.77 0.82 1.59 0.83 1.12 1.17 2.31 1.20 1.63 1.68 3.38 1.75 0.09 0.09 0.12 0.05 0.10 0.10 0.16 0.08 0.12 0.13 0.23 0.11 0.16 0.17 0.33 0.16 0.23 0.25 0.47 0.23 0.33 0.35 0.68 0.34 0.48 0.50 0.99 0.49 0.69 0.71 1.43 0.71 1.00 1.02 2.08 1.03 0.05 0.05 0.08 0.04 0.06 0.07 0.12 0.05 0.08 0.09 0.17 0.08 0.11 0.12 0.24 0.11 0.16 0.18 0.34 0.17 0.24 0.25 0.50 0.24 0.34 0.36 0.72 0.35 0.50 0.51 1.04 0.50 0.72 0.73 1.50 0.73

Relative difference

+25.48% +20.32% +18.26% +21.63% +33.46% +22.59% +6.96% +215.71% +155.55% +93.95% +46.97% +15.32% −2.74% −9.16% −9.80% −10.34% +187.32% +107.41% +53.13% +18.47% −1.01% −8.12% −8.45% −8.72% −9.05% +128.03% +66.77% +27.26% +4.31% −5.40% −6.18% −6.40% −6.67% −6.92% +63.54% +26.27% +5.53% −2.07% −2.63% −2.84% −3.06% −3.28% −3.53% +33.10% +10.21% +1.16% +0.30% −0.28% −0.61% −0.83% −1.05% −1.27%

Table 2: Accounted privacy ε for δ = 10−6 and p = 0.01. σ

T 250 500 1000 ≥ 2000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000

Rényi accountants Lossless accountants Our bounds Birrell et al. Wang et al. 13.77 ≥ 100 15.14 10.27 15.11 ≥ 100 17.86 12.90 17.79 ≥ 100 23.29 16.96 ≥ 20 for all accountants 1.77 3.27 2.21 1.34 1.99 3.96 2.89 1.80 2.44 4.93 4.02 2.51 3.32 6.00 5.76 3.61 4.75 8.14 8.42 5.28 7.00 10.89 12.63 7.84 10.48 15.83 19.31 11.83 15.83 23.23 29.82 18.16 ≥ 20 for all accountants 0.69 0.96 1.17 0.61 0.85 1.18 1.67 0.86 1.15 1.55 2.39 1.25 1.65 2.09 3.45 1.81 2.41 2.90 5.02 2.64 3.51 4.11 7.44 3.88 5.18 5.88 11.17 5.75 7.75 8.58 16.81 8.61 11.72 12.83 26.75 13.07 0.41 0.54 0.80 0.40 0.55 0.71 1.14 0.57 0.78 0.96 1.63 0.83 1.12 1.32 2.35 1.20 1.63 1.84 3.42 1.75 2.37 2.62 5.01 2.55 3.46 3.76 7.44 3.75 5.10 5.49 11.20 5.55 7.63 8.08 16.92 8.31 0.24 0.30 0.49 0.23 0.34 0.41 0.70 0.34 0.48 0.56 1.01 0.49 0.69 0.77 1.45 0.71 0.99 1.09 2.10 1.03 1.44 1.55 3.06 1.50 2.10 2.22 4.49 2.19 3.07 3.21 6.62 3.21 4.52 4.68 9.90 4.73 0.17 0.21 0.35 0.17 0.24 0.29 0.51 0.24 0.35 0.39 0.73 0.35 0.50 0.55 1.05 0.50 0.72 0.78 1.51 0.73 1.04 1.10 2.20 1.05 1.51 1.58 3.21 1.53 2.20 2.28 4.72 2.24 3.22 3.31 6.98 3.28

Relative difference

+34.03% +17.13% +4.85% +31.35% +10.68% −3.03% −7.93% −10.02% −10.77% −11.44% −12.82% +13.75% −1.45% −7.56% −8.62% −8.93% −9.44% −9.98% −10.00% −10.29% +3.35% −3.72% −5.36% −6.58% −6.81% −7.16% −7.59% −8.08% −8.16% +0.66% −0.74% −1.84% −2.73% −3.39% −3.65% −3.94% −4.25% −4.44% +2.40% +1.28% +0.40% −0.31% −0.90% −1.30% −1.51% −1.76% −1.97%

Table 3: Accounted privacy ε for δ = 10−6 and p = 0.04. σ

≥ 250 250 500 1000 2000 ≥ 4000 250 500 1000 2000 4000 8000 ≥ 16000 250 500 1000 2000 4000 8000 16000 ≥ 32000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000

Rényi accountants Lossless accountants Our bounds Birrell et al. Wang et al. ≥ 20 for all accountants 5.45 16.66 9.07 5.45 7.31 20.89 13.02 7.79 10.59 29.34 20.08 11.48 15.22 46.26 29.75 17.37 ≥ 20 for all accountants 2.58 4.63 5.31 2.66 3.63 6.11 7.70 3.86 5.22 8.37 11.52 5.68 7.68 11.49 17.09 8.46 11.53 17.02 26.73 12.80 17.42 24.96 41.03 19.73 ≥ 20 for all accountants 1.71 2.57 3.55 1.75 2.43 3.43 5.15 2.54 3.50 4.71 7.62 3.72 5.09 6.62 11.40 5.50 7.57 9.46 17.06 8.21 11.43 13.77 26.96 12.44 17.31 21.59 41.49 19.16 ≥ 20 for all accountants 1.03 1.40 2.16 1.03 1.48 1.87 3.13 1.49 2.13 2.57 4.56 2.18 3.08 3.61 6.69 3.19 4.52 5.18 9.98 4.71 6.66 7.56 15.06 7.01 9.99 11.26 24.17 10.56 15.15 16.72 36.49 16.16 ≥ 20 for all accountants 0.74 0.97 1.55 0.73 1.06 1.30 2.24 1.05 1.52 1.79 3.25 1.53 2.21 2.52 4.76 2.23 3.22 3.59 7.03 3.27 4.73 5.18 10.54 4.83 7.00 7.64 15.92 7.19 10.53 11.42 25.63 10.85 15.97 17.07 38.84 16.63

Relative difference

+0.01% −6.22% −7.82% −12.39% −3.07% −6.02% −8.06% −9.27% −9.96% −11.69% −2.10% −4.22% −5.82% −7.47% −7.84% −8.09% −9.67% +0.25% −1.19% −2.29% −3.27% −3.94% −4.90% −5.39% −6.23% +1.89% +0.78% −0.17% −0.93% −1.51% −2.08% −2.68% −2.96% −3.98%

Table 4: Accounted privacy ε for δ = 10−8 and p = 0.0025. σ

T 250 500 1000 2000 4000 8000 ≥ 16000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000

Rényi accountants Lossless accountants Our bounds Birrell et al. Wang et al. 8.70 ≥ 100 9.14 7.11 9.14 ≥ 100 10.03 7.83 10.03 ≥ 100 11.81 8.85 11.79 ≥ 100 15.36 10.32 15.33 ≥ 100 19.76 12.53 20.37 ≥ 100 22.49 15.98 ≥ 20 for all accountants 1.45 2.00 1.55 0.59 1.53 2.10 1.61 0.68 1.58 2.28 1.71 0.80 1.65 2.44 1.91 1.03 1.80 2.68 2.32 1.43 2.10 3.13 3.12 2.04 2.69 3.67 4.46 2.94 3.82 4.75 6.49 4.28 5.56 6.53 9.52 6.27 0.58 0.67 0.62 0.18 0.59 0.69 0.66 0.25 0.62 0.74 0.76 0.36 0.67 0.79 0.96 0.51 0.77 0.90 1.33 0.73 0.97 1.11 1.90 1.05 1.36 1.49 2.74 1.51 1.97 2.11 3.96 2.19 2.85 3.01 5.77 3.17 0.31 0.34 0.34 0.12 0.32 0.35 0.38 0.17 0.34 0.38 0.47 0.24 0.38 0.43 0.65 0.34 0.47 0.52 0.92 0.49 0.65 0.71 1.32 0.70 0.93 0.99 1.90 1.01 1.34 1.41 2.74 1.46 1.94 2.01 3.97 2.11 0.13 0.14 0.16 0.07 0.14 0.15 0.20 0.10 0.16 0.17 0.28 0.14 0.20 0.22 0.40 0.20 0.28 0.31 0.58 0.29 0.40 0.43 0.83 0.42 0.58 0.61 1.19 0.61 0.83 0.86 1.71 0.87 1.20 1.23 2.47 1.26 0.07 0.08 0.11 0.05 0.08 0.09 0.15 0.07 0.10 0.12 0.21 0.10 0.14 0.16 0.30 0.15 0.20 0.22 0.42 0.21 0.29 0.31 0.60 0.30 0.42 0.44 0.87 0.43 0.60 0.62 1.24 0.62 0.87 0.89 1.79 0.89

Relative difference

+22.41% +16.75% +13.31% +14.31% +22.37% +27.47% +145.95% +126.50% +96.51% +60.06% +25.92% +2.75% −8.75% −10.84% −11.35% +225.05% +136.65% +73.70% +31.47% +5.50% −7.39% −9.75% −9.97% −10.20% +162.02% +90.81% +42.81% +12.65% −3.41% −7.70% −7.84% −8.00% −8.22% +87.97% +41.64% +13.14% −1.18% −4.39% −4.59% −4.72% −4.85% −5.01% +50.48% +19.14% +2.65% −1.60% −2.12% −2.52% −2.64% −2.77% −2.90%

Table 5: Accounted privacy ε for δ = 10−8 and p = 0.01. σ 1

T 250 500 ≥ 1000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000 250 500 1000 2000 4000 8000 16000 32000 64000

Rényi accountants Lossless accountants Our bounds Birrell et al. Wang et al. 18.37 ≥ 100 19.75 13.45 19.71 ≥ 100 22.46 16.45 ≥ 20 for all accountants 2.36 4.19 2.87 1.89 2.65 5.11 3.54 2.33 3.09 6.24 4.79 3.10 3.99 7.53 6.77 4.35 5.59 9.68 9.85 6.27 8.15 13.19 14.52 9.20 12.01 18.13 21.61 13.71 18.13 27.83 34.43 20.79 ≥ 20 for all accountants 0.93 1.27 1.43 0.76 1.10 1.52 2.01 1.07 1.41 1.93 2.85 1.52 1.97 2.57 4.07 2.19 2.85 3.50 5.89 3.17 4.13 4.88 8.59 4.61 6.04 6.92 12.70 6.77 8.90 10.08 19.11 10.04 13.26 14.84 29.96 15.08 0.54 0.70 0.97 0.50 0.69 0.90 1.37 0.71 0.95 1.19 1.95 1.01 1.35 1.61 2.79 1.46 1.94 2.23 4.03 2.11 2.80 3.13 5.85 3.06 4.07 4.45 8.59 4.46 5.95 6.41 12.74 6.55 8.78 9.34 19.22 9.70 0.30 0.39 0.60 0.30 0.41 0.52 0.85 0.42 0.59 0.69 1.21 0.61 0.84 0.95 1.74 0.87 1.20 1.32 2.49 1.26 1.72 1.86 3.60 1.81 2.49 2.65 5.25 2.63 3.61 3.80 7.70 3.82 5.29 5.49 11.44 5.60 0.21 0.28 0.43 0.21 0.30 0.37 0.62 0.30 0.43 0.49 0.88 0.43 0.61 0.68 1.26 0.62 0.87 0.95 1.81 0.89 1.25 1.33 2.61 1.28 1.80 1.89 3.78 1.85 2.60 2.71 5.51 2.69 3.78 3.90 8.13 3.91

Relative difference

+36.60% +19.82% +24.53% +13.65% −0.15% −8.28% −10.80% −11.39% −12.39% −12.77% +22.59% +3.14% −7.30% −9.80% −10.12% −10.48% −10.84% −11.40% −12.10% +8.97% −3.13% −6.21% −7.53% −8.14% −8.29% −8.65% −9.04% −9.47% −0.19% −2.01% −3.13% −4.01% −4.71% −5.06% −5.25% −5.50% −5.59% +0.83% −0.27% −1.14% −1.83% −2.37% −2.83% −3.02% −3.19% −3.43%

Table 6: Accounted privacy ε for δ = 10−8 and p = 0.04. σ

B.2

Rényi accountants Lossless accountants Our bounds Birrell et al. Wang et al. ≥ 20 for all accountants 6.60 20.32 10.60 6.67 8.84 25.49 15.32 9.31 12.29 33.95 22.39 13.46 17.52 50.86 34.36 20.03 ≥ 20 for all accountants 3.13 5.78 6.23 3.24 4.34 7.57 8.96 4.62 6.14 9.91 13.09 6.71 8.83 13.79 19.39 9.90 13.06 19.33 30.53 14.80 19.73 29.57 45.64 22.53 ≥ 20 for all accountants 2.07 3.22 4.21 2.13 2.91 4.20 6.06 3.06 4.15 5.63 8.78 4.43 5.98 7.77 12.93 6.49 8.72 10.99 19.36 9.60 12.97 16.08 30.47 14.38 19.61 23.90 46.09 21.89 ≥ 20 for all accountants 1.25 1.76 2.57 1.26 1.77 2.31 3.69 1.81 2.53 3.12 5.34 2.62 3.64 4.32 7.82 3.81 5.29 6.11 11.52 5.57 7.75 8.76 17.36 8.21 11.52 12.79 26.47 12.26 17.46 19.02 41.09 18.54 ≥ 20 for all accountants 0.90 1.22 1.86 0.89 1.28 1.62 2.66 1.28 1.82 2.19 3.84 1.85 2.62 3.02 5.57 2.68 3.79 4.26 8.18 3.90 5.52 6.10 12.08 5.71 8.15 8.81 18.22 8.43 12.07 12.96 28.19 12.59 18.27 19.38 43.45 19.07

Relative difference

−1.07% −5.05% −8.69% −12.53% −3.18% −6.19% −8.55% −10.79% −11.75% −12.44% −2.59% −4.71% −6.46% −7.88% −9.13% −9.82% −10.40% −0.73% −2.17% −3.36% −4.37% −5.04% −5.71% −5.96% −5.87% +0.64% −0.48% −1.36% −2.14% −2.72% −3.33% −3.29% −4.13% −4.18%

Numerical implementation

Here, we record several details related to the numerical implementation of privacy accountants used for Appendix B.1. Implementing Rényi accountants. For Rényi accountants, we evaluate the Rényi DP bounds for integer orders 2 ≤ α ≤ 256, convert each bound into (ε, δ)-DP bound using [BBG+ 20, Theorem 20], and choose the minimum ε among them. For [BEBP24], we calculate Rényi DP bounds with tuning orders m ∈ {3, 4, 5} (the values used throughout numerical results in [BEBP24]) and report the minimum among the converted ε.

Our Rényi accountant requires8 calculating the maximum of Rényi divergences over u ∈ [0, 1/2], as stated in (5). The evaluation at each u is done by first evaluating F (u) (15), and then converting that to the corresponding Rényi divergence J (u) ≜ (log F (u))/(α − 1). In particular, we express (15) as a one-dimensional integral and characterize a valid upper bound J (u) and lower bound J (u) for J (u) (see Appendix B.3.1 for details). Based on these, we use a branch-and-bound approach as follows. • Initialization: [ℓ, r ] ← [0, 1/2] stored in a max heap, whose key Q(ℓ, r ) satisfies Q(ℓ, r ) ≥ maxu∈[ℓ,r] J (u) (calculating the key requires J (ℓ), J (r ) and a “curvature” upper bound; see Appendix B.3.2 for details); a global lower bound B ← J (0) ∨ J (1/2). • Update: at each iteration, 1. If the heap is empty or the key of the maximum item minus B is at most a predetermined threshold γ, terminate and output the key (B if the heap is empty). 2. Otherwise, pop the maximum item [ℓ, r ] from the heap and calculate J (m) and J (m) for m ← (ℓ + r )/2. Update the global lower bound B ← B ∨ J (m).

3. For each interval-key pair ([ℓ, m], Q(ℓ, m)) and ([m, r ], Q(m, r )), push it to the heap if and only if its key is larger than B. In particular, it is guaranteed that the output is at least as large as the theoretical Rényi DP bound, and has an additive error of at most γ; see Appendix B.3.2 for details. Before this procedure for evaluation of (5) at a particular α, we first (approximately) calculate (5) using standard libraries such as SciPy, in order to choose the Rényi order α. As described in Proposition 3, this can be done with O(log αmax ) evaluations, and here we use the approximations of those evaluations for faster implementation. For the chosen α, we implement the aforementioned branch-and-bound procedure with ball arithmetic from python-flint, guaranteeing that the final numerical value (based on the upper endpoint from ball arithmetic) is at least as large as the theoretical value. Implementing lossless accountants. For lossless accountants, we use the algorithm from [DGK+ 22] for implementation, with the length of discretization interval set as 10−4 . Runtime analysis. In order to attain an additive error of at most γ (in Rényi DP, for each Rényi 2 √ γ )) many evaluaorder α) for the branch-and-bound approach, it suffices to have O(α3/2 max / ( σ tions of the functions J, J and the key Q; see Appendix B.3 for further details. While our accountant is based on multiple steps including branch-and-bound and numerical integrals, its implementation in practice can be done reasonably fast. This is in part due to the fact that only logarithmically many Rényi orders need to be evaluated (Proposition 3). In Figure 6, we record the median runtimes (with 10th and 90th percentiles as error bars) from 20 runs of the Rényi accountants with αmax = 64, where our accountant runs within time comparable to that of [WBK21]; the runtimes were measured on a consumer-grade laptop with Intel Core i7-13700H CPU and 16GB LPDDR5 RAM. We emphasize that our implementation of other Rényi accountants is based on specific codebases ([WBK21] from Google’s dp-accounting and [BEBP24] from their codebase; note that all integer Rényi orders 2 ≤ α ≤ 64 are evaluated for those) which we did 8 The numerical optimization over u ∈ [0, 1/2] can be bypassed under conditions in Proposition 2. In our numerical

implementation, for simplicity we only check (19).

p = 0.01, σ = 2, δ = 10−8

p = 0.01, σ = 6, δ = 10−8 T = 1000 T = 10000

T = 1000 T = 10000

0.8

0.7

0.6

Time (seconds)

0.8

0.5 0.4 0.3

0.2

0.1

0.0

0.0 Our accountant

Birrell et al.

Wang et al.

Our accountant

Birrell et al.

Wang et al.

Figure 6: Median runtimes of Rényi accountants, for p = 0.01, σ ∈ {2, 6}, δ = 10−8 , and T ∈ {1000, 10000}. The error bars represent the 10th and 90th percentiles. In this setting, our accountant runs faster for T = 10000 because the binary search based on the unimodality in Rényi order (see Proposition 3) terminates earlier. not further optimize. Furthermore, in general the runtimes may vary across different choices of T, p, σ, δ and αmax . Our only claim here is that our accountant can be run within a reasonable amount of time, and the measured runtimes for other Rényi accountants in the figure should only be considered as a reference of scale.

B.3

Mathematical derivations

Here, we record remaining mathematical details about calculating values related to J (u) = (log F (u))/(α − 1) (see Appendix B.2): recall that F is defined as in (15) and the Rényi DP bound (5) is equal to maxu∈[0,1/2] J (u). Throughout, we assume that α ≥ 2 is an integer. B.3.1

Point calculation

Here, we explain how the upper bound J (u) and the lower bound J (u) of J (u) are evaluated (see Appendix B.2 for how they are used). Recall the notations around F (u) from (15). Define √ β ≜ ∆ 2u and V ≜ ⟨b, Z ⟩/β ∼ N (0, 1). Then from Var[⟨ a, Z ⟩] = ∆2 and Cov[⟨ a, Z ⟩, ⟨b, Z ⟩] = ∆2 u = β2 /2, we have r β2 d β ⟨ a, Z ⟩ = V + ∆2 − W , 2 4 where W ∼ N (0, 1) is independent of V; note that such reparametrization is valid even if u = 0. Then √ 2 2 2 2 F (u) = E[(1 − p + pe( β/2)V + ∆ − β /4W −∆ /2 )α (1 − p + pe βV − β /2 )1−α ] √ 2 2 α 2 2 α (1 − p)α−k pk E[(1 − p + pe βV − β /2 )1−α e(kβ/2)V +k ∆ − β /4W −k∆ /2 ] =∑ k k =0 α (35) 2 2 2 2 α =∑ (1 − p)α−k pk ek(k−1)∆ /2−k β /8 E[(1 − p + pe βV − β /2 )1−α e(kβ/2)V ] k k =0 Z ∞ α 2 2 2 2 α =∑ (1 − p)α−k pk ek(k−1)∆ /2−k β /8 (1 − p + pe βv− β /2 )1−α e(kβ/2)v ϕ(v)dv , k −∞ k =0 37

where we are left with one-dimensional integrals. For each k, we decompose the integral into three parts with truncation: Z ∞

−∞

(1 − p + pe βv− β /2 )1−α e(kβ/2)v ϕ(v)dv =

Z R

(1 − p + pe βv− β /2 )1−α e(kβ/2)v ϕ(v)dv −L | {z }

(I)

Z −L

(1 − p + pe βv− β /2 )1−α e(kβ/2)v ϕ(v)dv −∞ | {z } (II)

Z ∞

(1 − p + pe βv− β /2 )1−α e(kβ/2)v ϕ(v)dv , |R {z } (III)

for some L, R > 0 chosen to meet the desired accuracy (in our implementation, we start with L = R = 8 and increase them if needed); see also the final paragraph in Appendix B.3.2 for the accuracy criterion. Lower bound J (u). F (u) ≜

Z R

−L

We only use (I) for (35), which yields a valid lower bound F (u) of F (u): ! α 2 2 2 2 α ∑ k (1 − p)α−k pk ek(k−1)∆ /2−k β /8 (1 − p + peβv−β /2 )1−α e(kβ/2)v ϕ(v) dv . k =0

Then a lower bound J (u) of J (u) is defined as J (u) ≜ (log F (u))/(α − 1). Upper bound J (u). For (II) and (III), we use two simple upper bounds for the factor (1 − p + 2 2 pe βV − β /2 )1−α ; namely, (1 − p)1−α and p1−α e(1−α) βV −(1−α) β /2 . Those yield Z −L

Z −L

ϕ(v)dv ∧ p1−α e−(1−α) β /2 e(k/2+1−α) βv ϕ(v)dv −∞ −∞ 2 2 kβ k 1−α k β /8 1−α k2 β2 /8+(α−1)(α−k ) β2 /2 = (1 − p ) e Φ −L − ∧p e Φ −L − +1−α β , 2 2

(II) ≤

Z ∞

(1 − p )

1−α (kβ/2)v

Z ∞

(1 − p)1−α e(kβ/2)v ϕ(v)dv ∧ p1−α e−(1−α) β /2 e(k/2+1−α) βv ϕ(v)dv R R kβ k 1−α k2 β2 /8 1−α k2 β2 /8+(α−1)(α−k ) β2 /2 = (1 − p ) e Φ −R + ∧p e Φ −R + +1−α β . 2 2

(III) ≤

Hence for (35), we have a valid upper bound F (u) of F (u): α α kβ 1−k k k (k−1)∆2 /2 (1 − p ) p e Φ −L − F (u) ≜ F (u) + ∑ k 2 k =0 ! 2 2 α k ∧ (1 − p)α−k pk+1−α ek(k−1)∆ /2+(α−1)(α−k) β /2 Φ − L − +1−α β k 2 α 2 α kβ +∑ (1 − p)1−k pk ek(k−1)∆ /2 Φ − R + k 2 k =0 ! 2 2 α k ∧ (1 − p)α−k pk+1−α ek(k−1)∆ /2+(α−1)(α−k) β /2 Φ − R + +1−α β . k 2 38

Then an upper bound J (u) of J (u) is defined as J (u) ≜ (log F (u))/(α − 1). B.3.2

Maximum calculation

Here, we explain how upper bound Q(ℓ, r ) of maxu∈[ℓ,r] J (u) (see Appendix B.2) is evaluated. First, for all t ∈ [0, 1] we have J (ℓ + t(r − ℓ)) ≤ (1 − t) J (ℓ) + tJ (r ) + max | J ′′ (u)| u∈[ℓ,r ]

(r − ℓ)2 t (1 − t ) 2

(36)

(r − ℓ)2 ≤ (1 − t) J (ℓ) + tJ (r ) + max | J (u)| t (1 − t ) , 2 u∈[ℓ,r ] ′′

where the first inequality is a standard result from linear interpolation, and the second inequality is from J ≥ J (see Appendix B.3.1). Thus, once we can evaluate a valid upper bound κ (ℓ, r ) of maxu∈[ℓ,r] | J ′′ (u)|, we can set Q(ℓ, r ) ≜ max

t∈[0,1]

(r − ℓ)2 (1 − t) J (ℓ) + tJ (r ) + κ (ℓ, r ) t (1 − t ) 2

(37)

where the maximum over t ∈ [0, 1] can be evaluated as a quadratic function. For calculating κ (ℓ, r ), first note that F ′′ (u) 1 − | J (u)| = α − 1 F (u) ′′

F ′ (u) F (u)

1 ≤ α−1

F ′′ (u) F ′ (u) + F (u) F (u)

(38)

For bounding | F ′ (u)| and | F ′′ (u)|, from (17) and (18) we have (see Appendix A.2 for the notations below) (39) | F′ (u)| ≤ ∆2 α(α − 1)(E[wvh( X, Y )] + E[w2 h( X, Y )]) , and

| F′′ (u)| ≤ ∆4 α(α − 1) (α + 1)(α + 2)E[w4 h( X, Y )] + 2α(α + 1)E[w3 vh( X, Y )]

+ α(α − 1)E[w2 v2 h( X, Y )] + 4(α + 1)E[w3 h( X, Y )] + 5αE[w2 vh( X, Y )] + (α − 1)E[wv2 h( X, Y )] + 2E[w2 h( X, Y )] + E[wvh( X, Y )] .

(40)

From these, we derive two upper bounds κ1 (ℓ, r ) and κ2 (ℓ, r ) for maxu∈[ℓ,r] | J ′′ (u)|, from which we take κ (ℓ, r ) ≜ κ1 (ℓ, r ) ∧ κ2 (ℓ, r ). First bound κ1 (ℓ, r ).

From (38), since F (u) ≥ 1 we have

| J ′′ (u)| ≤

1 (| F ′′ (u)| + | F ′ (u)|2 ) . α−1

(41)

For bounding (39) and (40), it suffices to bound E[vi w j h( X, Y )] for finitely many (i, j). This is done similarly as in Appendix B.3.1, where the denominator in the power of 1 − p + peY is bounded by

1 − p and peY . To be specific, we have9 E[vi w j h( X, Y )] = E[ pi+ j eiX + jY (1 − p + pe X )α−i (1 − p + peY )1−α− j ] α −i α−i =∑ (1 − p)α−i−k pk+i+ j E[e(i+k)X + jY (1 − p + peY )1−α− j ] k k =0 α −i α−i ≤∑ (1 − p)α−i−k pk+i+ j E[e(i+k)X + jY (1 − p)1−α− j ] ∧ E[e(i+k)X + jY ( peY )1−α− j ] k k =0 α −i 2 α−i ≤∑ (1 − p)1−i− j−k pi+ j+k e(∆ /2)((i+k)(i+k−1)+2rj(i+ j+k−1)) k k =0 ! 2 α−i (1 − p)α−i−k p1+k+i−α e(∆ /2)((i+k)(i+k−1)+2r(α−1)(α−i−k)) . ∧ k (42) Then κ1 (ℓ, r ) is defined as the final bound from the chain of inequalities (i.e., from sequentially applying the final upper bounds) in (41), (39), (40), and (42). Second bound κ2 (ℓ, r ).

Consider a tilted measure E′ [ f ( X, Y )] ≜

E[ f ( X, Y )h( X, Y )] for f ≥ 0 . E[h( X, Y )]

Since F (u) = E[h( X, Y )], for (39) we have F ′ (u) ≤ ∆2 α(α − 1)(E′ [wv] + E′ [w2 ]) ≤ 2∆2 α(α − 1) , F (u)

(43)

from 0 ≤ v, w ≤ 1; similarly, for (40) we have

F ′′ (u) ≤ ∆4 α(α − 1) ((α + 1)(α + 2) + 2α(α + 1) + α(α − 1) + 4(α + 1) + 5α + (α − 1) + 2 + 1) F (u)

= 2∆4 α(α − 1)(2α2 + 7α + 4) .

(44)

Thus, from (38) we have

| J ′′ (u)| ≤

1 (4∆4 α2 (α − 1)2 + 2∆4 α(α − 1)(2α2 + 7α + 4)) = 2∆4 α(4α2 + 5α + 4) ≜ κ2 (ℓ, r ) . α−1 (45)

Remaining details for implementation. For our implementation of the branch-and-bound approach (see Appendix B.2), we choose J (u) and J (u) to satisfy J (u) − J (u) ≤ γ/2. Then the key Q(ℓ, r ) from the maximum item [ℓ, r ] satisfies (see (37)) Q(ℓ, r ) ≤ ( J (ℓ) ∨ J (r )) +

γ (r − ℓ)2 + κ (ℓ, r ) , 2 8

which in particular implies Q(ℓ, r ) − B ≤

γ (r − ℓ)2 + κ (ℓ, r ) . 2 8

9 The binomial expansion of (1 − p + pe X )α−i is valid since i ≤ 2 for the right hand sides of (39) and (40), and α ≥ 2.

Thus, if

γ (r − ℓ)2 ≤ , (46) 8 2 then Q(ℓ, r ) − B ≤ γ. Since B ≤ maxu∈[0,1/2] J (u) ≤ Q(ℓ, r ) (if the heap is empty then B = maxu∈[0,1/2] J (u) is the output), this guarantees that the output from the branch-and-bound approach has an additive error of γ. From (45), we know that κ (ℓ, r ) = O(∆4 α3max ) = O(α3max /σ4 ), √ and thus for (46) it suffices to have r − ℓ = O( γσ2 /α3/2 implies that for the bisection in max ). This 2 √ γ )) evaluations of J, J and Q. / ( σ the branch-and-bound approach, it needs at most O(α3/2 max κ (ℓ, r )

Can Rényi Accountants Beat Lossless Accountants for DP-SGD?

Analyze & explore related research in Conceptio

Related documents