Privacy Amplification for Matrix Mechanisms
Authors: Christopher A. Choquette-Choo
Arun Ganesh
Thomas Steinke
Abhradeep Guha Thakurta
Venue: ICLR 2024 spotlight (2024)
Keywords: differential privacy
privacy amplification
matrix mechanism
Primary area: societal considerations including fairness, safety, privacy
TL;DR: We propose an algorithm for computing privacy guarantees of the matrix mechanism with privacy amplification.

Abstract: Privacy amplification exploits randomness in data selection to provide tighter differential privacy (DP) guarantees. This analysis is key to DP-SGD's success in machine learning (ML), but, is not readily applicable to the newer state-of-the-art (SOTA) algorithms. This is because these algorithms, known as DP-FTRL, use the matrix mechanism to add correlated noise instead of independent noise as in DP-SGD.

In this paper, we propose "MMCC'' (matrix mechanism conditional composition), the first algorithm to analyze privacy amplification via sampling for any generic matrix mechanism. MMCC is nearly tight in that it approaches a lower bound as $\epsilon\to0$. 
To analyze correlated outputs in MMCC, we prove that they can be analyzed as if they were independent, by conditioning them on prior outputs. Our "conditional composition theorem'' has broad utility: we use it to show that the noise added to binary-tree-DP-FTRL can asymptotically match the noise added to DP-SGD with amplification. Our algorithm also has practical empirical utility. We show that amplification leads to significant improvement in the privacy/utility trade-offs for DP-FTRL style algorithms for standard benchmark tasks.

Published as conference paper ICLR 2024
PRIVACY AMPLIFICATION FOR MATRIX MECHANISMS
Christopher A. Choquette-Choo" Abhradeep Thakurta
Arun Ganesh
Thomas Steinke
ABSTRACT
Privacy amplification exploits randomness in data selection to provide tighter differential privacy (DP) guarantees. This analysis is key to DP-SGD's success in machine learn- ing (ML), but, is not readily applicable to the newer state-of-the-art (SOTA) algorithms. This because these algorithms, known as DP-FTRL, use the matrix mechanism to add correlated noise instead of independent noise in DP-SGD.
In this paper, propose "MMCC". the first algorithm analyze privacy amplification via sampling for any generic matrix mechanism. MMCC is nearly tight that approaches a lower bound as 0. To analyze correlated outputs in MMCC, prove that they can be analyzed as if they were independent, by conditioning them on prior outputs. Our "con- ditional composition theorem" has broad utility: binary-tree- ----rree---FFRR DP-FTRL can asymptotically match the noise added to DP-SGD with amplifi- cation. Our algorithm also has practical empirical utility. We show that amplification leads to significant improvement in the privacy/utility trade-offs for DP-FTRL style algorithms for standard benchmark tasks.
show that the noise added to
1 INTRODUCTION
Privacy amplification is key in differentially private (DP) machine learning (ML) as it enables tighter privacy budgets under certain assumptions the data processing. For example, of the main contributions in the DP-SGD (DP Stochastic Gradient Descent) work by Abadi et al. (2016) was the "moments accountant", which relies privacy amplification (Kasiviswanathan al., 2008; Bassily al., 2014) for bounding the privacy cost. Recently, privacy amplification analysis enabled Choquette-
et al. (2023a) to show that class DP-FTRL (DP Seelow-The-Regulriizeee Leadee) algorithms (Smith & Thakurta, 2013; Kairouz et al., 2021) was superior in privacy-utility tradeoffs to DP-SGD. At the heart of DP-FTRL is the construct of matrix mechanism (MeKenna et al., 2021; Denisov et al., 2022) that effectively computes the prefix sums Etst X; over sequence of adaptively chosen vectors fx, E [m]] (given by A X, where A is R=xd). Matrix mechanism corresponds
a lower triangular matrix of all ones and x factorizing A = B C to minimize the eтror in the estimation of the prefix sums, while ensuring C- x + satisfies DP, where is drawn from an isotropic normal distribution. Bringing privacy amplification matrix mechanisms is thus important area of research to enable better privacy-utility tradeoffs. (In the rest of the paper, we will refer to matrix as the decoder matrix, and C as the encoder matrix.)
"Google DeepMind. cchoquette@gooogle Google Research, arunganesi@@ooggle.cmm com.
*Google DeepMind. steeink@@ooole. com.
'Google DeepMind. athakurta@gocgll. com.
'Precisely, they showed DP-FTRL worse, and often better, than DP-SGD-ir "paret--oonoteee

---

Published as a conference paper ICLR 2024
Matrix mechanism poses a major challenge for privacy amplification analysis of DP-FTRL style algorithms. Standard privacy amplification exploits randomness in the selection of minibatches but requires that the noise added to each minibatch independent. In the matrix mechanism, minibatch (given by x;) con- tributes to multiple rows of C X + z, thus preventing direct application of amplification. This challenge can be seen by the limitations of the amplification analysis Choquette-Choo et al. (2023a) which only applies to a special class of "b-banded" matrix mechanisms (i.e., the first b principal diagonals of C are non-zero), that in-turn leads to multiplicatively higher sampling probabilities preventing the full benefits of amplification. Resulting from these limitations is large region of epsilons where banded matrix mecha- nisms cannot simultaneously leverage the benefits of correlated noise and privacy amplification; in other words, they perform equivalent to, but better than, DP-SGD* Further, since their analysis only applies to the special banded case, matrix mechanisms from the extant literature cannot leverage amplification and correlated noise, e.g., Kairouz et al. (2021); Choquette-Choo al. (2023b); Denisov et al. (2022).
In this work, we provide generic privacy amplification machinery for adaptive matrix mechanisms for any trian-triangula encoder matrix C that strictly generalizes the approach in (Choquette- -Choo et al., 2023a).
1.1 OUR CONTRIBUTIONS
Our main contribution is to prove general privacy amplification analysis for any matrix mechanism, i.e., arbitrary encoder matrices C for non-adaptively chosen x, and for lower-triangular C's when x is adaptively chosen (which is the typical situation for learning tasks). We then demonstrate that our method yields both asymptotic improvements and experimental improvements.
Conditional composition (Sec. 3, Theorem 3.1): This is our main technical tool that gracefully handles dependence between the queries Cia.1 xx and C(++1.: x that arises due to multiple participation of single row of the data matrix x. Standard composition theorems (Dwork & Roth, 2014) only handle this via a pessimistic worst-case privacy guarantee that holds with certainty for each query (in our application, a query is Cia.g xx conditioned on x Z1.-11). Theorem 3. relaxes this to holding with high probability (over the randomness of the algorithm) leading to significantly better guarantees. This generalizes an idea previously used in (Erlingsson et al., 2019; Balle et al., 2020) to analyze privacy amplification by shuffling. We believe this theorem will be useful for analyzing correlated noise mechanisms beyond those studied herein.
Matrix mechanism with uniform sampling via MMCC (Sec. 4): We prove amplified privacy guarantees for the matrix mechanism with uniform sampling, using Theorem 3.1, that are nearly-tight in the low-epsilon regime (as ε 0). We improve over Choquette-Choo al. (2023a) because we enable "more randomness" in sampling- instead of participating w.p. bp in n/b rounds, data records can participate w.p. p in all n rounds.
Recall we need to analyze the privacy of outputting Cx + where rows of are chosen via uniform sampling. We use Thm. 4.3 to reduce Cx + z to a series of mixture of Gaussians (MoG) mechanisms for which we can use privacy loss distribution (PLD) accounting (see the proof sketch of Thm. 4.3 in Sec. 4). Our algorithm MMCC formally stating this reduction is given in Fig. 1. We plan to publicly release a library implementing MMCC with the final manuscript. The analysis of MoG mechanisms included in this library has other uses, such as tighter privacy guarantees for DP-SGD with group-level DP or for linear losses, see App. F for more discussion.
Enss Vol(O,; d), where is randomly chosen subset of D (c.g., sampled u.a.r. from D, or a subset from a random shuffling of D), is a loss function, and 6 is obtained via an SGD state update process. IIn Choquette-Choo et al. (2023a), this region surfaces empirically even for larger As 1.
B.g., for a data set D, a row X =
2

---

(Kairouz Published as a conference paper at ICLR 2024
Binary tree analysis (Sec. 5) Letting de be the noise required for the Gaussian mechanism achieve satisfy 8)-P,, the binary tree mechanism requires noise 0e,8 vlog n. Owing the versatility of conditional composition, we show that with shuffling, the (non-adaptive) binary tree mechanism only needs noise g, min vlog Vlog log(1/5)}. This is optimal given current amplification by shuffling results, which require n ((log 1 1/8)². To the best of our knowledge, this is the first amplification guarantee (of any kind) for the binary tree mechanism.
Empirical improvements (Sec. 6): First we implement and show that e computed via MMCC for the binary tree mechanism matches the theoretical predictions of (V n) from Sec. 5. Then we apply our work machine learning and show we can improve the privacy-utility tradeoff for binary-tree-DP-FIRE
et al., 2021) entirely post-hoc. Finally, we show that the "every round" sampling enabled by MMCC achieves better amplification than the "b-min-sep" sampling of Saoouuette-Choo et al., 2023a).
1.2 PROBLEM DEFINITION
Matrix mechanism (MM): Consider workload matrix A Ruxn, and consider data set D {di, (di,-..,day) dm) E DDm Let = (D) (D)) Raxd be matrix s.t. each row x; D Rd is a randomized function that first selects a subset of the data set D, and then maps it to a real valued vector. Furthermore, each of the x; has the following two properties. a) Decomposability: For the subset of the data set D that x, chooses (call it S,), we have (D) = Edes; (i( with g. D - Rd is vector valued function, and b) bounded sensitivity: Vd E D: (d)lle S 1. Matrix mechanism corresponds to the class of DP algorithms that approximates Ax with low-error. Typically, one designs a pair of matrices A BC ( which we will call the decoder and the encoder matrices respectively) s.t. Cx + z satisfies DP$ (with z being isotropic normal noise), and Bz is minimized in appropriately chosen norm. We will assume C non-negative for simplicity.
Privacy amplification for MM: In this work we study the problem of amplifying the DP guarantee of MM if we incorporate the randomness in the selection of the subsets of D by each function X;- In particular we consider two selection strategies: i) uniform sampling: each x; selects each entry of D independently w.p. p, ii) shuffting: First the records of D are randomly permuted, and then each x, picks fixed disjoint subset (of equal size) from D.
Adaptivity: In our work we allow the choice of x, 's to be adaptive, i.c., x; can be chosen based on the first i outputs of MM. Under adaptivity, will only consider encoder (B) decoder matrices (C) that are lower triangular. However, for non-adaptive choices the x; 's we allow arbitrary choice of the matrices B and C. Unless mentioned specifically, all our results will be for the adaptive setting.
2 BACKGROUND AND RELATED WORKS
2.1 PRIVACY LOss DISTRIBUTIONS (PLD)
Suppose we have a DP mechanism M that outputs a sample from the continuous distribution P M(D) when given database D, and outputs a sample from Q = M(D') when given D'. The e-hockey stick divergence between two distributions P, Q is defined as:
e
0)
He(P,Q) - max( e ( Ofdr E
max cln(P(o)/Q())
"We believe this requirement is fundamental and thus de,8 min / Vog n, Vlog log(1/6)} is optimal, but if were removed, our result would improve to ((1) G2,5- We the zero-out adjacency (Ponomareva et al., 2023) define DP in this paper.
3

---

Published as a conference paper ICLR 2024
A mechanism M satisfies (e if and only if for all adjacent databases D, D' we have (E(M()),(DD))) I 8. From the definition, we see that to obtain the e-hockey stick divergence between P and Q, it suffices to know their privacy loss distribution (PLD):
Definition 2.1. The privacy loss random variable for P and Q is given by sampling x P, and computing In(P(z)/Q(z)) The PLD of P and Q is the distribution of this random variable.
We frequently use the notion of dominating PLDs:
Definition 2.2 (Definition 7 in (Zhu et al., 2022)). The PLD of P.Q dominates the PLD of P Q' if for any H. Q) 2 HP(P', (P). We will also say random variable L dominates random variable L' if for any E, (L) 2 Hc(T'), where HT) = Re-r. [max {1 (1-66-(,0)
Informally, a PLD dominates another PLD if any privacy guarantee satisfied by mechanisms with the domi- nating PLD is also satisfied by mechanisms with the dominated PLD. In particular, if the PLD of some pair of distributions P, Q dominates the PLDs of all pairs M(D),M(D) for adjacent D, D', then if Hz Q) S 8, M satisfies (DP..
2.2 PRIVACY AMPLIFICATION
Privacy amplification via sampling analyzes the improvement in privacy given by randomly sampling a minibatch of examples instead of choosing it deterministically. Roughly, a (c. 6DP mechanism run on a batch where each example participates with probability p satisfies (log(1 - p + pe 0)DP.. The relative + pef) gets better as gets smaller: log(1
+ pe*) 2e pe for < 1. but log(1 - p + pe=) Rs log(1/p) for large E. The benefits of privacy amplification via sampling in the independent noise setting of DP-SGD, i.e., the decoder matrix C = I. are extremely well-studied (Song et al., 2013; Bassily et al., 2014; Abadi et al., 2016; Mironov et al., 2019; Steinke, 2022; Koskela et al., 2020) with tight analyses. In particular, (1-p) (O, o²) + pp. (11, a²) " and since each round of DP-SGD has independent randomness, composing this PLD with itself times gives a tight dominating PLD, i.e. tight (s, curve, for DP-SGD.
improvement from E to log(1
round of DP-SGD is dominated by the PLD of (O, o²) and
3 CONDITIONAL COMPOSITION
We first show a conditional composition theorem, which allows us to analyze a sequence of adaptive mech- anisms using nigh-probabilite instead of worst-case privacy guarantees for each mechanism. We state con- ditional composition formally as Theorem C.2. This is a generalization of an idea used in (Erlingsson et al., 2019; Balle et al., 2020) to analyze amplification by shuffling.
Theorem 3.1 (Informal version of Theorem C.2). Let M1, be a sequence of adaptive mechanisms, where each M, takes D and the previous mechanisms' output as input. Suppose there is some "bad" event E that happens with probability at most dbad over the randomness of M1, for any input D. If the composition of the worst-case privacy guarantees of M1,M2,.. each conditioned on E not happening satisfies (e, D), then the composition of M1, M2,... ... satisfies (c,8 + 8bad)-DP.
The proof is given in App. C. To apply Theorem 3.1 to correlated noise mechanisms, we observe that they can be viewed as a sequence of adaptive independent-noiss mechanisms:
Observation 3.2. Let M + X, x X2 x ... X,, be a mechanism that takes a dataset D and outputs the tuple (21, .n)) drawn from the distribution M(D). Let M; Xi x X2
Xi-1 x + Xx be the mechanism that takes x4,, 2/.. ,,,,,,,,, x/-1 and a datasel and outputs x' with probability (or likelihood) MCD) [zv [===20 21/22 = x11 x22 = 222 Ri-1 = x/-1] The output distributions of M and the composition of M1,Ma .. are the same.
4

---

Published as conference paper ICLR 2024
Algorithm 1 Matrix Mechanism Conditional Composition algorithm, p,
1: Input: Matrix C, sampling probability p. noise standard deviation o, probabilities $1, 62.
2: (Pig),,EE <Probabill Boudda p, ō1).
Pi.j is high-probability upper bound on the probability that an example participated in round j. conditioned on output in rounds t
3: for E in] do
4: PLD; t PLD of MrMoc (PP. (Cr))em))
5: PLD + convolution of (PLD)
6: return min (fe: PLD satisfies (c, (c,62)-DP)).
Figure 1: Algorithm MMCC for computing amplified privacy guarantees the matrix mechanism. The is given in Fig. 5 in App. C.
subroutine ErobabilityTaalBBoo
4 PRIVACY ANALYSIS FOR MATRIX MECHANISMS
In this section, we give an algorithm for computing an upper bound on the privacy guarantees of the matrix mechanism, and prove its correctness.
4.1 MIXTURE OF GAUSSIANS MECHANISMS
The key tool in our privacy analysis is mixture of Gaussians mechanism, generalization of the Gaussian mechanism with sampling. Here we define these mechanisms under the add adjacency, i.e. D' contains an example zeroed out in D.
Definition 4.1. A mixture of Gaussians (MoG) mechanism is defined by two lists, a list of probabilities {PI, .P.....PPp p. with E.P. 1,ps E [0, 1], list of sensitivities {ct, .2. and noise level o. For simplicity, we will assume 2 O. Given D, the mechanism (MMoC(PPPPP.--.. outputs (0, d.). Given D', samples s from the distribution with support (cibe(t)) and associated probabilities {pr ve(k) and outputs z N(s, o²). In other words, is Gaussian mechanism where the sensitivity is a random variable distributed according {piten {Gi)ee
{e1, ..... C₁
A vector mixture of Gaussians (VMoG) mechanism My is the same as a MoG mechanism, except the sensitivities c; are allowed be vectors c; instead of sealars, and our output sampled from multivariate Gaussian z ~ NO,, 0² II) or z ~ N(s, 0². I)..
For our proofs, we will need prove few properties of MoG mechanisms. We give these properties and their proofs in App. B. It will be easier for us to work with a special case of MoG mechanisms, where the probabilities and sensitivities arise from a product distribution:
Definition 4.2. A product mixture of Gaussians (PMoG) mechanism is defined by lists {pi..... p& and (C1....ck and a noise level a. The mechanism MPMMc((P1... .Pk], (ci...., cx)) is defined equiv- alently as MMoo(Ulliss P: -Igss( - S e 2 {Eies c E 2 2).
4.2 MATRIX MECHANISM CONDITIONAL COMPOSITION
The high-level idea of our algorithm, MMCC (short for matrix mechanism conditional composition), for analyzing the matrix mechanism with amplification is the following: The output of each round conditioned on the previous rounds' output is a MoG mechanism. For each round, we specify a MoG mechanism that dominates this MoG mechanism with high probability. Then by Theorem 3.1, it suffices to compute the
5

---

Published as a conference paper ICLR 2024
privacy loss distribution of each of the dominating MoGs, and then use composition get our final privacy guarantee. MMCC is given in Fig. 1. In App. C, we prove that MMCC computes valid DP guarantee:
Theorem 4.3. Let be the output of MMCC(CC p, a, ō1, 82). The matrix mechanism with matrix C, uniform sampling probability p. and noise level a satisfies (s, 01 + d2)-DP.
We give a high-level overview of the proof. The proof proceeds in three steps. First, we show the ma- trix mechanism is dominated by a sequence of adaptively chosen scalar MoG mechanisms, by analyzing the distribution for each round conditioned on previous rounds and applying vector-to-scalar reduction (Lem. B.4). Second, we simplify these MoG mechanisms by showing that each is dominated by PMoG mechanism with probabílities Pi,j depending on the outputs from previous rounds. Third, we show that with high probability Pı.j S Pi.j for all i, i.e., the upper bounds generated by Probabi 1 TityTaiii Bounds hold. We then apply Theorem 3.1.
To get sense for how tight MMCC is, if in MMCC we instead set Pi.j = for all i,j. this is equivalent to analyzing the matrix mechanism as if each row were independent. Since the rows are actually correlated, expect this analysis to give a lower bound on the true value of e. So we can use maxi, Paa/P as roughly an upper bound on the ratio of the reported by MMCC and the true & value. In particular, as + 00, for Pi, computed by Probabill wwwbbiiiiyaaaa Bounds this ratio approaches 1, L.e MMCC gives tight & guarantees in the limit as + 00.
Tightness:
Sampling scheme of (Choquette-Choo et al., 2023a): The techniques used in MMCC are complementary Choo et al., 2023a): In App. D, we give a generalization of MMCC that analyzes the matrix mechanism under their "6-min-sep sampling." For b 1, this is the same as i.idd sampling every round so this generalization retrieves MMCC. For b-banded matrices this generalization retrieves exactly the DP-SGD-liik analysis of (Choquette-Choo et al., 2023a). other words, this generalization subsumes all existing amplification results for matrix mechanisms.
to those in (Choquette- Chhoo
Benefits of i...d. sampling: MMCC is the first analysis that allows us to benefit from both correlated noise and privacy amplification via i..d. (i.e., maximally random) sampling. In Sec. 6.3 demonstrate that the combination of benefits allows us to get better Ey éz-error for computing all prefix sums than independent-noise mechanisms, for much smaller than prior work.
5 AMPLIFICATION VIA SHUFFLING FOR NON- ADAPTIVEE BINARY TREE
this section, we show that amplification allows us to improve the privacy guarantees of the binary tree mechanism of (Dwork et al., 2010; Chan et al., 2011). We consider the setting where first the data set D is randomly permuted (call it II),)), and each function x; (in the definition of MM from Section 1.2) picks the i-th data record in II( Roughly speaking, using privacy amplification by shuffling (see Section 1.2) we improve for this mechanism by Q( ((VTog /n//logg /og log(1 (1))), while maintaining that each example partici- pates once. For simplicity throughout the section we restrict to the case where n is a power of 2.
Binary tree mechanism: The binary tree computes sums of rows of x over the intervals [1 1). 2) 2)..... (n n1,[1 : 2). [3 4)....,
n]. : 4].... [1 r2] with noise. That is, it outputs v.s.d. where Zj.A ~ N (0, Equivalently, is a (non-
EE 1)-2/ X 2j.k osjSiogn.0Sk
square) matrix mechanism where for each j, k pair there is row of C where the entries in the interval [k- 2' 11: (k + 1). same level j. In the single-epoch setting (without shuffling), each row of x; is sensitivity-I function computed on the ith example in D. The binary tree mechanism then satisfies the privacy guarantees distin- guishing z and Cc, + where e; is an elementary vector. Since each row of is included in log + 1 of the
.22 2 are I and the remaining entries are O. We refer to all the noisy sums indexed by the
6

---

Published as a conference paper ICLR 2024
sums, we have ||Ce/ll2 = vlog + I, i.c. the binary tree mechanism satisfies (o V Vlog(n) DP.
Log((1/)) log(1/6)
We now analyze the binary tree mechanism under shuffling. To apply Theorem 3.1, we need the following analysis of "approximate shuffling" given in Lem. 5.1, proven in App. C.
Lemma 5.1 (Simplification of Lem. C.4 in App. C). Suppose we run Gaussian mechanisms on n inputs, where the order of the inputs is chosen according to a distribution such that no input appears in certain position with probability more than 1/n'. Then for ô 2 2-Q(nn), 2,80 80 2 O, this set of mechanisms satisfies
(o(
(1(1/60)1n(11)
+ n n'ó0 DP.
ove
Theorem 5.2.
The non non-adaptive binary tree
mechanism run on II(D)
satisfies
(o
v (ing(1/6) log (1g(1/))
DP for o (al.llll/////////// (1))(1)))))))) log log(1/5)), 6 e [2 R(m), 1/m].
The proof of Theorem 5.2 is given in App. C. We give a summary here: For the "top" levels E [log (log longloogggo (g))) log nl, the number of sums per level (i.e., n' in Lem. 5.1) less than log(1/8) so we cannot apply Lem. 5.1. Instead we use the unamplified privacy analysis of the Gaussian mechanism to analyze the privacy of the corresponding noisy sums. For the remaining levels,
combine Theorem 3.1 and Lem. 5.1 show level j's privacy parameter is exponentially decaying in log j. i.e. the top Ollog log(1/5)) levels dominate the privacy guarantee. Note that the theorem proven in the non-adaptive case; our argument for adaptivity in Sec. 4 implicitly requires independence of participations across examples, which does not hold for shuffling.
6 EMPIRICAL IMPROVEMENTS
We implement MMCC by building on methods in the open-source dp accountins ing Python library (DP Team, 2022), and perform empirical studies of the amplification benefits from MMCC. PLD accounting for MoG mechanisms is currently open-sourced as part of the ap.accounting library. We plan to open- source our implementation of MMCC which builds on www.acoounting There are some challenges the implementation which we discuss in App. F. For simplicity we use ô,, d2 5/2 in MMCC.
6.1 BINARY TREE MECHANISM AMPLIFICATION
In this section, show how the privacy guarantee of the binary tree mechanism empirically improves if we use sampling and MMCC. In App. E we repeat this study for a different matrix mechanism proposed by (Fichtenberger et al., 2023).
As a baseline, we fix constant c, and consider the binary tree mechanism under single-parie pongle-paticcipation con- straint, with a e colo(()) + 1. By the analysis of the Gaussian mechanism, for all that are powers of 2. the binary tree mechanism with this choice of a under satisfies (e, 5DDD for the same E, 6. In other words, as we increase n., the privacy guarantee of the unampli- fied mechanism remains fixed. Then, for the same and that are powers of we use MMCC to compute a privacy guarantee for the binary tree mechanism with subsampling probability 1/n and the same choice of a. By the analyses in Section we expect that with subsampling, the value of & will decrease as 32(vlogm) n).
cungle-participation constraint without amplification
In Fig. 2, we observe that empirical improvement in due to amplification is roughly proportional to Vlog(n) 1. We also observe two improvements e (i.e., σ) increases. First, the multiplicative im- provement in increases; second, empirical improvements better match linear fit /lo((n) 1. Both
7

---

Published as conference paper ICLR 2024
(unampliffed
junamplified
(unamplified Stewing he Jisuua
>-620isdsg 2w32572
p-odesiriig lie 2441
INA0 ursamp C. batter
10gin)
bgght
l0g0t
Figure 2: Multiplicative improvement of our amplification analysis (roughly) matches v log(n) + A higher ratio (> 1) indicates amplification is better. We plot 2 E (1, 10) with
ev log(() (n) so is fixed for unamplified sinlee-aaticipaation. 5 10
65
Analysis Method
Choqett Dheee 2013
1.0
Text Accuracy
0.00
Privacy Budee
Ampiifiariis None (kalrouz at 2023)
0.4
MMCE (0ars)
1.5 2.0 Privacy Budget.
40
52
100
200
Noise Standard Devistion, e
Figure 3: Our amplification analysis leads to sig- nificant gains over Kairouz al. (2021) on prac- tical ML experiments (CIFAR-10), entirely post- hoc.
Figure 4: MMCC gives tighter & than the analy- sis of (Choquette-Cie Chho al., 2023a) for a DP- mechanism of height 4. Ran n 512 steps with I6
these improvements are explained by the fact that (as discussed in Sec. 4) as a - co, MMCC reports tighter E.
6.2 LEARNING EXPERIMENTS WITH BINARY-TREE-DP-ET
A motivating reason for us to study matrix mechanisms is that the analysis of Kairouz et al. (2021) has a suboptimal scaling in the amount of noise added, which manifests in their experiments with DP machine learning. We reproduce the centralized DP training on CIFAR-10 from Choquette- -hheetee-hhho et al. (2023b), in- cluding model architecture, tuning setup, hyperparameter choices, and optimizations to the tree aggregation mechanism for ML; we these as baseline results.
Fig. 3, we re-analyze the baseline using MMCC and show significant improvements in privacy-utility tradeoffs for DP-FTRL via binary trees. In particular, observe that these benefits become larger becomes small. Note that these improvements are entirely "post-hoc," i.c. the algorithm is the same, but with better privacy analysis.
6.3 I.L.D SAMPLING ENABLES BETTER AMPLIFICATION THAN 6-MIN-SEP SAMPLING
The prior work of (Choquette-Choo et al., 2023a) gives an amplification result using a sampling scheme we call "b-min-sep sampling" for b-banded matrices. In their sampling scheme, each example participates in
8

---

Published as a conference paper at ICLR 2024
n/b rounds with sampling probability bp. In contrast, MMCC enables sampling each example in all n rounds with probability "more random" form of sampling. We compare the two amplification analyses using the DP-FTRL-TreeResse
algorithm of (Kairouz et al., 2021), which sequentially runs n n/2h-1 height-h binary tree mechanisms, each binary tree mechanism run for 2 rounds. This corresponds to matrix mechanism that is 2 -banded, so we can apply the results of (Choquette-Choo et al., 2023a). Fig. 4, we compare the computed as a function of using MMCC and the analysis of (Choquette-Chor
& for DP-FTRL-TreeResine et al., 2023a), in the setting of n = 512,7 p = 1/16, h = 4, and we see that indeed the more random sampling enabled by MMCC allows for improved privacy guarantees compared to b-min-sep sampling.
7 DISCUSSION, FUTURE DIRECTIONS, AND CONCLUSION
this paper, we proposed MMCC, which gives tight amplification guarantees for sampling in the limit as é + O. One limitation of our work is that we are not able to prove adaptivity for non-lower triangular C, which captures important matrix mechanisms like the "fully efficient" binary tree mechanism (Honaker, 2015). It is important future direction to fully understand what combinations of privacy amplification and correlated noise allow the same privacy for non- non-adaptive and adaptive inputs. In addition, there are many potential improvements to MMCC, as well open problems that naturally follow from our work. Another open problem that we make progress towards is proving DP-FTRL strictly dominates DP-SGD, i.e. for any >> DP-FTRL achieves strictly better utility than DP-SGD under an appropriate definition of utility. In particular, we conjecture that a tighter amplification analysis than that of MMCC could show that even for e close to 0, DP-FTRL with matrix mechanism where C is close to but not equal to the identity has strictly better utility than DP-SGD.
Our interest in the matrix mechanism is primarily motivated by the works of (Denisov et al.. 2022; Choquette- Cinquette-Chooeee et al., 2023b;a) which considered the problem of choosing C that optimizes (a proxy for) the utility of DP-FTRI. The utility of DP-FTRL. can be written as a function of C-1, and thus can be optimized under a constraint of the form "the matrix mechanism defined by C satisfies given privacy definition".. Without amplification, this constraint can usually be easily written as e.g. C E where is a convex set of matrices, which makes optimizing under this constraint easy. An interesting question is whether we can solve the same problem, except the privacy constraint accounts for amplification. This would likely require designing function that takes C,p, p, a and approximates that is differentiable in C (unlike MMCC, which is an algorithmic computation that is not easily differentiable).
In these works, DP-FTRL is always strictly better than DP-SGD without amplification, but with amplifi- cation for small the optimal choice of C' with amplification is the identity, i.e. the optimal DP-FTRL is just DP-SGD (with independent noise). If we could optimize C under an amplified privacy constraint, we conjecture the following (perhaps surprising) statement could be proven as a corollary: As long as we are not in the full-batch setting, even with amplification by sampling, the optimal choice of C is never the identity for = > 0. In other words, despite its ubiquity, DP-SGD is never the optimal algorithm to use (ignoring computational concerns).
Due to space constraints, we defer the discussion of other future directions to App. A.
REFERENCES
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, pp. 308-318, 2016
'Note that (Choquette-Chore Choo al., 2023a) showed that DP-FTRL is always least good as DP-SGD, but in their results for small DP-SGD is just as good DP-FTRL, i.e. DP-FTRL is not strictly better.
9

---

Published as conference paper ICLR 2024
Borja Balle, Peter Kairouz, H Brendan McMahan, Om Thakkar, and Abhradeep Thakurta. Privacy amplifi- cation via random check-ins. In NeurIPS, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algo- rithms and tight eтror bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464 473, 2014.
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. on Information Systems Security, 14(3):66:122622 November 2011.
Christopher Choquette-Choo Arun Ganesh, Ryan McKenna, H Brendan McMahan, Keith Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A unified approach to private training. arXiv preprint arXiv:2306.08/53, 2023a. URL ht //axxiv//// org.ab//335.bb.....b 08153.
Christopher A. Choquette-Choo Hugh Brendan McMahan, J Keith Rush, and Abhradeep Guha Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceed- ings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 5924-5963. PMLR, 23-29 Jul 2023b. URL htttps::/pproeettte press /2022/ wwwgohttee choo23a html.
mmlr.
Sergey Denisov, H. Brendan McMahan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators adaptive streams. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 5910-5924. Curran Associates, Inc., mewpeeeeddiinn.e.eiieeeeeeeeeeee neurips cc/ cc/paper.pppee files/ wwwes/papeeeeeeeeeeeeeeaeeeeeeee /ttpe///ppp///2///1//ee conper-conferene..dde
2022. URL https: / http://pooeeeenng...c
DP Team. Google's differential privacy libraries., 2022. differential-privant
https: htt.aa...ooo//oo////// googgeo
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4)2111-477, 2014.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium Theory of computing, pp. 715-724, 2010.
Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In ACM- SIAM Symposium on Discrete Algorithms (SODA), 2019, URL https::///// //arxii org/ 12469.
Vitaly Feldman, Ilya Mironov. Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 2022. doi: 10. 10.1109/FOCS55999, 20220000220
10

---

Published as a conference paper ICLR 2024
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay, Constant matters: Fine-grained error bound on differentially private continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, JCML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Rexearch, pp. 10072-10092. PMLR, 2023. URL https: /ttp://////cc///ppeeeooeee mlr. press// v202 www.chhheeeeeeeecccccoooo html.
Arun Ganesh. Tight group-level dp guarantees for dp-sgd with sampling via mixture of gaussians mecha- nisms, 2024.
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A unifying framework for differentially private sums under continual observation, 2023.
James Honaker. Efficient use of differentially private binary trees, 2015.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Prac- tical and private (deep) learning without sampling or shuffling. In ICML, 2021.
Shiva Prasad Kasiviswanathan and Adam Smith. On the 'semantics' of differential privacy: A bayesian formulation. Priv. Confidentiality, 6(1), 2014. doi: 10.29012/jpe.v6i1..33 URL ht https: /doi. org/10. 2901 2/ jpc. v6i1. 634.
Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. What can learn privately? In 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS), pp. 531-540, 2008
Antti Koskela, Joonas Jälkö, and Antti Honkela. Computing tight differential privacy guarantees using fft. In International Conference on Artificial Intelligence and Statistics, pp. 2560-2569, PMLR, 2020.
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajhalla Hdmm: Optimizing error of high-dimensional statistical queries under differential privacy. arXiv preprint 1.Xiv:2106.12/16 2021.
Ilya Mironov, Kunal Talwar, and Li Zhang, R) ''enyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 190,:1100..003000 2019. URL https: / aarxi.. org abs//ab///// / 1100/ 10530.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy MI.: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 17:1113-1201, jul 2023. doi: 10. 10.1613/jain, 1. 14149 URL https:/ / http///o.ooo////o///ooo .org/ 10. 311661113Faaa
1449.
Adam Smith and Abhradeep Thakurta. (nearly) optimal algorithms for private online learning full- information and bandit settings. In Advances in Neural Information Processing Systems, pp. 2733-2741, 2013.
Shuang Song. Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-248. IEEE, 2013.
Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling. arXiv preprint arX1v:2210.00597, 2022. URL https: //trx/aaaivv.///a////a/.e.l orgg abs 2210 00597.
Salil Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pp- 457. Springer, 2017.
11

---

Published as a conference paper ICLR 2024
Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via char- acteristic function. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceed- ings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Pro- ceedings of Machine Learning Research, pp. 4782-4817 4817. PMLR, 28 30 Mar 2022. URL https:
/pproceedings.. mlr, htt.eedddiig........ssssss/sl// wwt.sp//ssl////eeeee.e html.
12

---

Published as conference paper ICLR 2024
A MORE FUTURE DIRECTIONS
First, tail bound the conditional sampling probabilities Piy approach p as cc. However, for finite a, Pi.j can be much larger than p. i.e. the computed by MMCC can he much larger than the true e. We believe the values of Pt., we compute are not tight and can be improved. In particular, in computing Pi,, we give a tail bound on the maximum of the dot product of a Gaussian with a set of vectors, and the values of Pig we compute effectively correspond to the case where this tail bound is attained by every dot product. This overly pessimistic, and it should be possible to obtain tighter & via a more refined tail- kail-bounding approach.
Second, while MMCC has polynomial dependence on n (whereas computing Hg via e.g. numerical inte- gration would require time exponential in rt), empirically we found that even with many optimizations for runtime, running MMCC for R 2000 still took several hours. practice, we would often like to run for larger n, do multiple sequential runs of MMCC in order to e.g. compute the smallest that gives certain e via binary search. In turn, it is practically interestigg/mmporani to make MMCC more efficient, or discover another algorithm that gives comparable to or better than MMCC, but with a smaller runtime.
PROPERTIES OF MoG MECHANISMS
The following lemma informally lets us show that domination for the remove adjacency (i.e., D contains an example zeroed out in D') is equivalent to domination for the add adjacency (i.e., D)' contains example zeroed out in D). Thus, we usually only need to prove statements under one of the two adjacencies, and it implied for the other as well.
Lemma B.1 (Lemma 29 in (Zhu al., 2022)). The PLD of P. dominates the PLD of P. P.Q' if and only if the PLD of Q, P dominates the PLD of Q', P.
B. MONOTONICITY MoG MECHANISMS
The following shows the privacy guarantees of a MoG mechanism are "monotonic" in the sensitivity random variable c;:
Lemma B.2. Let Ppi.P2....PP pa {c1, (2,,,...... C2...., c and (d,,,y,,.. c.,...cr d'e3 be such that (i) each c, is non- negative and (ii) df is entry-wise greater than equal c, for all i.e. each - c; is non-negative.
Then the PLD of
MyMoc(IPi.Pe P2. .p....pp) pkt, (cr, C2, ca,,.,
is dominated by the PLD of
MyMoc((eI.P2... pk}, cc....,....
Proof. By Lem. B.1, it suffices to only consider the remove adjacency, i.c. given D we sample c, and then sample from Nic,, and given D' from N(0 I²I). The privacy loss of outputting x is:
2(c,, x) - ||ci1|2
PL(x) In Σ pr exp
20²
Let S Rdd be monotonic if for any E S.y such that y - is non-negative, y is also in S. In other words, increasing any subset of the entries of x E S gives another vector in S. Since all c; are non-negative, y is non-negative, then the privacy loss of outputting y is larger than that of outputting x. So for any
13

---

Published as conference paper ICLR 2024
VMoG mechanism and any the set of outputs St {x PL(x) Pearson lemma it suffices to consider only the sets St in the definition of (e, 8)-DP, i.e. mechanism satisfies (e, 8)-DP if and only if
2 t} monotonic. By the Neyman-
:L: Pr (x E S.) S.) 2
6 gMM((D)
Pr
[ E St]
So, in order to show that to show the first VMoG mechanism is dominated by the second, it suffices to show the probability that ~ NC,,, is in any monotonic set S is at most the probability that x ~ N I) is in S. This is immediate by coupling of the two random variables: we let the first random variable be c, + z and the second random variable be c + z, where the choice of and Gaussian noise z are the same for both random variables. For any monotonic S, since cq is non-negative, C, is in S only if c + is S. giving that the probability x ~ N(c, I2 is in at most the probability x ~ N(c, o2 is in S.
Since the above proof holds for any C; of satisfying the assumptions in the lemma, it also holds if c; are fixed/non-adaptive but the entries in C; chosen adaptively (while still satisfying the assumptions in the lemma), i.e. the jth coordinate of c; is chosen only after seeing the first 1 coordinates of the output. In the scalar case, get the following corollary:
Corollary B.3. Let (p1.P2....PP pk), (c1, Ck) and (p', P2.... phr 12........ ........].. be such that for all T, Eiee 2T P' Z EiazTT Pi. In other words, the random variable induced by {p; hi, feihe is stochasti- cally dominated by the random variable induced by (p')is (d We also assume c₁2 2 0 for all i.
Then the PLD of
MM MMMGl(P1,Pa
......PP.. ......p...
(c1, ..,))
is dominated by the PLD of
MMoalfP'iPp P2... ... Phe 3, fci, .2....... Hr.)).
Cor. B.3 follows from Lem. B.2 since by allowing duplicate &j values, we can reduce to the setting where the probabilities are the same, and < ce for all c. For example, if c; is 0 or 1 w.p. 1/2 and ce is 0, or 2 w.p. 1/3, we can use {p:} = (1/3, 1/6, 1/6, 1/3), {c} = (0, 0, 1, 1}. and {c] = 1,
B.2 DIMENSION REDUCTION FOR MoG MECHANNSMM
We now give the following lemma, which lets us reduce the dimensions of VMoG mechanism. Lemma B.4. Let C1, C2,...,CA Ck E R= Let ci, ca...., c2 E R" be vectors such that (CC.),;lle S c(()) for all i, i.e. the entries of c, upper bound the E2-norms the corresponding rows of Ct. Then the PLD of
MvMoo(IPie P2......... ............ .pp,...,p)...... (c1, (c.,
is dominated by the PLD of
MyMool(pi.P.. .p..........P...
(c/, C2 ......,, ck.)).
Furthermore, this holds even if the rows of each c, are adaptively chosen and c, are fixed, i.e. the jth row of all c; is chosen by an adversary after seeing the first j - 1 rows of the output of the VMoG mechanism, as long as the assumption (I(c.);:ll2 S cj()) holds.
We need the following lemma, which we can apply multiple times prove Lem. B.4:
14

---

Published as conference paper ICLR 2024
Lemma B.5. Let W1, w2.... we > be positive scalars and let C1, C2,... Cj. R be arbitrary vectors. Then for any E and a > 0:
max Σ 1i exp((c,.x)) e -e .0/
max Σ wn exp(Ilcil(2 o 0
< (EmN((.OO))
Proof. E. wyweeeyee exp([|e:|lo as function of x is continuous, increasing in æ, and has range RR. So, there exists some such that E, wy exp(I|c;ll2 () = ef. For this choice of I, let l = w, exp(1ic; 1 (). Then we have for all 2:
max Σ wi exp([|c:l12 c0, e.:0)= = Σ max {wy exp([|c;|12 x) 1, 0}.
Now, by linearity of expectation and the fact that max (E ai E, b,bb S Σ, max as b:}:
max Σ wi exp((c..x)) - ce.
Ex-NNO,
max (w; exp((c,, x)) - t, 0}
Fx [max {w, exp((c,, x)) - 1, 0)]
Σ Ee,N((,00)) [max {w; exp([|c:|122)) 4, 03]
EExNN(0,02) Σ max {wr exp([Ic:|12 4.
EE-N(0,0
max Σ w. exp([Ic:l222) -5,0
Proof of Lem. B.4. Lem. B.2 holds for adaptively chosen c; and fixed c' (using the notation of that lemma), so by Lem. B.2 it suffices to prove the lemma for adaptive c; and fixed cf such that [[(;));=l] = cf()) for all i,j. Further, by Lem. B. it suffices show the lemma under the remove adjacency. That is, = N(c,, TTInpp) Q = NO0, dfT P = N(c,, II Q' = N(0, TTT,), and suffices to show (P, Q) < (P Q') for all e.
We have:
P(x) Q(x) E .
H. (P.Q) Ex~Q
max
Exprexp(|Ix c:il /202)
-,, /
max
exp(1 exp(|x(12//00 /202)
2(c,, x) ||cal12
=Ex- N(0,
max
Σ Pt exp
05,0
20
15

---

Published as conference paper ICLR 2024
To reflect the fact that e2 can be chosen adaptively, let Cr (X1:--1 denote any adversary's ss adaptive choice of the jth row of c2 after observing the first j rows of x. We can then write H₂ (P, Q) as:
2(c=)(X1s-1),x) x2) - [[:.,
(X1:) 1)11 - -e,, -6,0 of0
Ex, Ko... ~N(0000)
max
Σn Pt II
exp
2x²
jEIn]
e 011
2(ci,(Xx..j 1). x,) (x13)(11)-11)))
Ex, (x.
(1,0N10,0
max
Σ Pc II
exp
2x²
JE(m)
(1)
Note that the values of all Ci2 in (1) are constants with respect to the inner expectation. So for any realization of X1, X2:
1n choosing
(-
[|Cin((X: 21
(x1:5-
w; P: exp
20
exp
20
jE(n-1]
and observing that by assumption || (x1:n-1))l c((n),, inner expectation (1) as:
apply Lem. B.5 to upper bound the
(1) < Ex, -.
max Σ P:
II
jEIn-1]
||c,,
(2) c((n)2 - cf .6 }
exp
exp
202
20²
We then iteratively repeat this argument for rows 1, n 2, ... 1 to get:
H²(PQQ) & Ex, x x.. 1.
max
ΣpL Pi
2/c,, (x1-)) 1).
22 - c)(2)2
II exp jE(n-1)
exp
e.
20
20²
Ex )
max
Σ P
()c))(x11-1),xx)) (x..((1:y-1))
(2c((j)ar -(()))))))(())))) -
II exp jE|n-2]
II exp
202
202
JE /n-2
Ex No N(0000)000
max
Σ
(x13 x,) co (x:3-111))
2c 2c) - c((1)² - -ee
II
exp
exp
202
202
/E|n-3]
16

---

Published as conference paper ICLR 2024
( - - - -6,0
/
S Ra N(0,02))
max Σ
exp
20²
JE(N)
2/c x) - 1c/ll2
E 0 (P)
N(0,0ft)
max
Σ ps exp
20²
As corollary to the above "matrix-to-vector reduction", we have "vector-to-scalar reduction" for MoG mechanisms:
Corollary B.6. The PLD of
MMM.a((p.PP....... pkl, (ci, cx..
is dominated by the PLD of
MMoo(Lpi,P2. paj. (1lc1l12.11111 ||ea|12 ..... |lcull2).
C DEFERRED PROOFS
C.I PROOF OF THEOREM C.2
We will need the following lemma, which shows domination is preserved by composition:
Lemma C.1 (Theorem 10 in (Zhu et al., 2022)). Let M be an adaptive sequence of mechanisms, i.e, each mechanism receives the output of all previous mechanism and the database. Suppose for all and joint outputs x of M1....Mi-.. the PLD of M,(x, D) and Ma(r, D') is dominated by the PLD of P., Qi. Then letting M be the composition of these mechanisms, the PLD of M(D),M(DD) is dominated by the PLD of Pi x P2 x ...,QQ Q1 x Q2 X
Similarly, if L,, Lg,.. .., La and L,, Lt ....... Lg random variables such that L dominates L,, for all then L1 + L2 + LA dominates L₁ + L/2 ....+ Lig.
(Zhu et al., 2022), only the first part of Lem. C. is stated. However, the proof allows arbitrary measures. ie.. measures that don't integrate to I, which implies the second part of Lem. C.I.
Theorem C.2. Let Mi : D - X,,2; X4 x D + X2, Mg : Xi x X₂ x D MM, be sequence of adaptive mechanisms, where each M; takes a dataset in D and the output of mechanisms M Mi-1 input. Let M be the mechanism that outputs (x1 Mn Fix any two adjacent datasets D, D'.
MM(D),
M2(31, D),..., In
Suppose there exists "bad events" " Ei C X1, E2 S X1 X2 ........E-111 C. x X3 x x. Xn-1 such that
Pr M)
Bi:
E E. 8
and pairs of distributions (P1, Q1), (P2, Q2) ... (Pns Qn) such that the PLD of M1(D) and Mi(D') is dominated by the PLD of Pı, Q1 and for any i 2 1 and "good" output (I1, Z2,... 22) $ E.. the PLD of M 12 Ri, D) and M4+1 F,, D') is dominated by the PLD of P411, Qu+l. Then for all
H((M(D).M(D)) H. (P x x P,, Q1 Q2 ... x Q,) +
17

---

Published as conference paper ICLR 2024
Algorithm 2 @rrobbllittyyallloonrsspoopppp
1: Input: Matrix C, sampling probability p. noise standard deviation o, probability 61.
2: 8' (Cn
nnz is the number of non-zeros.
3: Φ (1 8')
Tail bound on normal distribution; here, is the standard normal CDF.
4: for j.j m|] do
5:
if Crj = 0 then
6:
PLj =
7: else
St.j minimum Pr Pr(Cn's By. (C.--1.j. C15-1.5) > 2), ftd. Bern(p)
8:
$1, a tail bound on the dot product of first 1 entries of Cx and C1s-15j.
Edi =1(C
9:
Ci.j a tail bound on the privacy loss participation in round j after outputting first i rounds
peexple..)
10:
Pij pexple.a)+(1-ppp
return (
Figure 5:
Algorithm for computing Pi.j, tail bound on conditional probability of participating in round j given first outputs.
Proof. Let Li be the privacy loss random variable of M, and let La be the privacy loss random variable of Pi x P2 x ... x PR, Q1 x Q2 .... x Qn We want to show Hz(L,) I Hz())) + 8 for all 6.
Let I4 be the random variable coupled with Li, with the coupling defined follows: If 3i (I1, T2.....; E Es, then Li -o, otherwise Li = L1. Let E = {x|3i (21, E E.}. Then for all
HL Ex max c1-ce-hicn .0]]
+ Pr(r E EJ- [max {1 ec- b1)),, ,0] E) Pr(z $ EJ.EB. B2 max e- Lm)), 00} & E
x
(L1) Prir E]
Eg max {1 f1-68-L168) Lz(2x( 00]
x
E s He(())) + Pr(x E H. (L)) + 5.
So it suffices to show L is dominated by L2. We consider the following process for sampling L₁: For each i, if for any < i, (I1, .2..... Err) E Ep, then we let L = -o deterministically. Otherwise we sample Mi( #4-1, D). L1,; = Pr (F) b
Prw.-Mido.......... [1,1=1]] Then Li = E, L1,-- Similarly, let
L2, be the privacy loss random variable for P,, Qi, and let L2 = Σ; L2 By assumption, the distribution
of L conditioned on æ1, . I4-1 always dominated by L2 So by Lem. C.1, L is dominated by T2-
[T
C.2 PROOF OF THM. 4.3
Before stating the proof, in Fig. 5 we give ProbabilityTail the subroutine used to compute the values of pi.j-
Proof of Thm. 4.3. For simplicity in the proof we only consider remove adjacency, i.e. D contains a sensitive example zeroed out in D'. By symmetry the proof also works for add adjacency. By quasi-convexity
18

---

Published as a conference paper ICLR 2024
of approximate DP, suffices prove the theorem assuming the participation of all examples except the sensitive example is deterministic, i.e. we know the contribution of all examples except the sensitive example x, so we can assume these contributions are zero. So, let x be the matrix used in the matrix mechanism if we were to sample the sensitive example in each round. Then, the matrix mechanism is a VMoG mechanism with probabilities {p S) (1 p)" p)"-1$$}} |c|n] and sensitivities {Ejes C.
Our proof proceeds in three high-level steps:
1. We show the matrix mechanism is dominated by sequence of adaptively chosen MoG mecha- nisms.
2. We show each of the adaptively chosen MoG mechanisms is further dominated by PMoG mech- anism.
3. We show these PMoG mechanisms are with high probability dominated by the PMoG mechanisms in MMCC, and then apply Theorem C.2.
Step 1 (matrix mechanism dominated by sequence of MoG mechanisms): Let f be the function that takes a matrix M and returns vector f(M) where the ith entry of this vector is the f--norm of the ith row of M. Using triangle inequality, for any x such that each row of has norm at most f(Ejes C,y))) is entrywise less than or equal to Ejes C..- So by Lem. B.4 the matrix mechanism is dominated by the
VMoG mechanism with probabilities {p) p)"= sg[n and sensitivities {Ejes C.. Ssgii Note that this is exactly the mnn-adappivv) matrix mechanism where each x; = 1 (prior to sampling), i.e. it suffices to prove the privacy guarantee holds for this choice of So, for the rest of the proof we will assume the input of the matrix mechanism (prior to sampling) is the all ones vector.
Now, let f denote the output of rounds to i. By Observation 3.2, this random variable is the same as the composition over of outputting 0; sampled from its distribution conditioned on 01.i-1. Let S, denote the set of rounds in [i] in which we sample the sensitive example. Abusing notation to let Pr denote a likelihood, the likelihood of the matrix mechanism (M()) outputting 0, in round conditioned on f1:-11 is:
Σ TCM
Pr [S =T 014-11 Tw)(D)
Pr NNNNEe C. D
[Ts 0t]
The likelihood of M(D') outputting 0g in round i (conditioned on f1s--1, which doesn't affect the likelihood since since each coordinate of is independent when sampled from MMD')) is
Pr
[Te 0z)
No
In other words, the distribution of 0, conditioned on 01:11 under M(D)) is exactly the same as the pairs of output distributions given by the MoG mechanism.
{
MasoG
Pr [S T 115-11 (TNeTD)
Cas Custren
TCM
JET
So the matrix mechanism with x being all ones is the same as the sequence of (adaptively chosen) MoG mechanisms given by
"Note that since C is lower-triangular, so the choice of the distribution of the ith row of Cx by an adaptive adversary depends only rows I i - 1 of Cx z. That is, an adversary who chooses the jth row of x after sceing the j 1st first rows of the matrix mechanism satisfies the adaptivity condition Lem. B.4.
19

---

Published as conference paper ICLR 2024
(ussa
{ (IrBiD)
)
Pr
[S, T 010-1]
Tgl
jeT
iE[n]
Step 2 (each MoG is dominated by a PMoG): To achieve step 2, we use the following lemma: Lemma C.3. Let
2,0
pexp
20
Pi.j (10ua-,.Cu---
(naaaii(CCaaae [Cruu- + 11-pp
pexp
20
The random variable induced by probabilities
{ILET Pij [h -iii) TSM and support
jEjr Cuptrgi stochastically dominates the random variable induced by probabilities (Pr = Thms- = 01.1-1) (1a-1]]rc(1 and the same support.
Proving Lem. C.3 completes the step as with this lemma and Cor. B.3, the PLD of
(L
Masoc
(wellD) [S T|r--1 01--1l
Castrea
TCM
jeT
is dominated by the PLD of
MrMsoG ((Pr))et)) (Cis))em))
Proof of Lem. C.3. Sampling according to probabilities (Pr) = T 01a-illrgu
is equivalent to the following process: We start with T and for each j [1] add T with probability Pr(T U {5} S S S S1i-1:11 = 01.-1]. Similarly, sampling T according to pio)
[IljTT Pt.j [ls (1-p)))
is equivalent to the same process, except we add j with probabil-
TCH
ity Pi.j- If we show that Pr[T U S St T 01--11 S Ps,j for all T.j, then we can couple these sampling processes such that with probability 1, E ŽjeT Ct, is at least as large for the second process as for the first, which implies the lemma. The posterior distribution of St satisfies:
Pr [S = T1--1 01.-10 x +N0(D)
Pr [S, T] Pr [Ta-1 = 01:-11/5; = T T~B(D)
(00i-11,jee C1a-15) - Ejer C1ai-1e)
x (T - -p)--171 exp
exp
20²
Hence:
Pr|T U (5) S C S,, Ti--1 -1
20

---

Published as a conference paper ICLR 2024
ErSTUGY) (1-
2/015-1, Cha-15)-
Eyer Cuu-tty
exp
2
2(01: ser
Oi 15) Eyer
Cla 1,3' 1
Ererr T p)i
T exp
2n
Fix some 7" 2 TUUUUO {i}. Consider the term in the numerator sum corresponding T", and the two terms in the denominator sum corresponding to 7" and T" \ (i). The ratio of the numerator term to the sum of the two denominator terms is:
218 1. 15)) Ever CLa 1.
p exp
20²
2(8:n-1, Cra-i,))
Eyer Cua-tyy
[>perro Cua-t 20
p- exex
2n²
+ +11 exp
exp
Since entries of C are non-negative, have Eyer C1a-1.8 1| 2 Eyers C1a-1
|[C ll hence this ratio and thus Pr[TU C S C Si, Tha-1 = 01:-1] are at most pij. which proves the lemma.
Step 3 (replacing Pı,j with Pi,j via conditional composition): By Theorem C.2 and Cor. B.3, it now suffices to show that w.p. 1 - 51, Pijj S Pi.j for all í.j simultaneously. The bound trivially holds for entries where C.j- 0, we only need the bound hold for all mnz(C) pairs i, such that Ci 0. Furthermore, if Ci. is the first non-zero entry of column j, then C1a-15 is the all zero-vector, so we get Pt.j = Pt., = p.
So, there are only nnz(CC n "non-trivial" pairs we need to prove the tail bound for: by a union bound, we can show each of these bounds individually holds w.p. (nz(C)-n By definition of pt,j Pi.j, this is equivalent showing 10 C1:-1.5) S ||Cr:-1,5122 82, for each of these i, pairs. We have:
&
(01--1, C1a-11)
Σ (Lu-11))C1A-11))) + (21 jeE.
C1a-15).
The first term is tail bounded by St.j with probability 1 [[nns(C]-n) by definition, the second term is drawn from N (0, |C o²) and thus tail bounded by |[Crs-1llly with the same probability by definition. union bound over these two events gives the desired tail bound on (01s-1, C1a-15).
6
C.3 PROOF LEM. 5.1
Proof. Since each 0 S p: I 1/n', the mechanism is the same as the following: For each example we choose a subset S C [n] of size n' according to some distribution that function of the p;, and then choose i uniformly at random from the elements of S, and include the example in the ith subset. By quasi-convexity of approximate DP, suffices to prove the DP guarantee for a fixed choice of S. For any fixed choice of S, the mechanism is equivalent the shuffled Gaussian mechanism over n' coordinates. Each unshuffled
Gaussian mechanism satisfies 22 DDP, and then the lemma follows by the amplification via shuffling statement of Theorem 3.8 of of (Feldman et al., 2022).
21

---

Published as conference paper ICLR 2024
C.4 PROOF THEOREM 5.2
We first analyze simplified case where = 0 if i + 8", and otherwise for D and x; 0 for D'. We later give a proof for the general case.
Proof of Theorem 5.2 in simplified case. Let Tj.k be the value of the noisy sum Σ k. 2/ +
kj T Tos n.05k<n/22 and let (D) be the distribution of these values under dataset D. We consider a single sensitive example; let i" be the (random) coordinate of x;- that this example contributes to.
Now, again abusing notation to let Pr denote a likelihood, we have for any j:
Pr T>)(
=
Pr O5k"5nn22" TW@(D) (TiA)ogteem/ = 10, =00 R.' 2 +1 1 < (k* + 1) 23
Σ
Pr r~@(D)
k* . 215 s (k* +1) 20 (Ty:
other words, for any j. the distribution of the j-th level of the tree, {Ty, 1osss/223// conditioned on the higher levels the tree, {Ty,a), "/>ssosss///// is the output distribution mechanism described Lem. 5.1, where the probabilities are
Pr 2- +155 1)+ 2 spookknpps (0/ssoosststt///// T>)(D)
Pi.
We now show high probability bound each of these probabilities. We have:
Pr r~0(D)
k 21 < (k+ -2 2 (T (trrh//s///tt////s0sss//// = 10y
(k+1))2 Σ 1:2141
Pr.~e(D)
[Ty:Aly>s0sk<////>== - h/tp:///aakkkkooooo...aa//a///a/
En Pr)we(D)
[Tywh)ssooshenpp) = (00s)/
(F +15 +14
Σ 1-221 I/ exp
(k+1)
2
+15 (1550/2*tt555<++2222))
Σ gosjsksssksk exp
20
(k+1).2)
Jrink g²
1 21 exp
1 exp
J
2/
max4e(n) [ exp
min HI +151((++))))))))))))<). exp (-
2
(log n - j) max T3 min 2 Ti'
cxp
d²
22

---

Published as conference paper ICLR 2024
With probability 8/2, by union bound for all 2n pairs k we have |T,A| S (2 so the above bound is at most:
2
(logn j)2 In mm(4//6)
exp
n
1v 2221n(()/5) In2 Ifo
in turn this is most:
log nogn-j
2
/
Now, by Theorem C.2 and Observation 3.2 it suffices to show that conditioned on this probability 1 6/2 event, the binary tree mechanism satisfies (o v (og log
.5/2 -DP. For log n
8/4 -DP by the (o Vlog(1/6) log log(n/6)
16e log log(16n/6)) s j Σ log n, releasing Tj.k satisfies
analysis of (unamplified) Gaussian mechanism. For levels S < logn 16e log log( (og(()n/)))) our upper bound the conditional probabilities and Lem. 5.1 with do 6/8n' log shows that, conditioned on the high-proo probability event, the distribution of the privacy loss of outputting {Tj, conditioned on levels
j' j satisfies (o
Vlu(n//0) In(1/)) 8/4 n -DP, with n'' = [v
By basic composition, the
ovn'
27
overall privacy loss distribution conditioned on the 8/2 probability event satisfies:
(o v log((16)) log (1/(
2//4 In(1/6)
+0
Σ
8/2 -DP.
on4
j==lo - 16e log log (6//8)
Here we use the upper bound on 8 which is equivalent to log(n/ö) = Ollog(1/0).. We conclude by bounding the sum as:
2 In(1/5)
Σ
on
j=log 16e log log
log n- 16 log log( (0g())/)))
In(1/8) (n(o/)) log 16e log log
/ II((1/0) o(1 2-1/44
2/4 /mn(1/)
2
1=0
We now discuss how to extend the proof to more general case. In other words, we choose some y with each row having 2-norm at most for D, and then set y' for to be y with the first row zeroed out. Then, x is chosen by shuffling the rows of y or yr.".
Lemma C.4. Under the above setup, for some & that divides n, consider the mechanism that chooses random size equipartition of (ni, P (S1, S2........5 of [n] according to some distribution and out- puts (01, 02,..., 02), 0, N(Eees, y1, Suppose for any two equipartitions P. P', the probability of choosing P is at most times the probability of choosing Pt, and let n' [k/cl.
23

---

Published as conference paper ICLR 2024
Then, for any 2 2e Ioc, 60
2
0.
if = (((In((160)) then this mechanism satisfies
(o
(in(1/6o) In(1/6) avn
+ n' 60
-DP.
Proof. Recall that y1 is the example differing between D and D' By post-processing and quasi-convexity. we can instead analyze the mechanism that for each S, also publishes all but element in S; and specif- ically for the S; including I (the sensitive element), the element of S; not published must be 1. This is k.
equivalent saying: without loss of generality we can assume
Next, the assumption on the distribution over P implies that the distribution is in the convex hull of distri- butions over that deterministically choose k- n elements of P. with 1 being one of these n' unchosen elements, and then uniformly shuffle the remaining n' elements. In terms of privacy guarantees, each in- dividual mechanism using one of these distributions equivalent to n' Gaussian mechanisms on shuffled elements. Then, by quasi-convexity, the privacy guarantees of this mechanism are no worse than those of a Gaussian mechanism over n' shuffled elements. We conclude using the analysis of amplification by shuffling in (Feldman et al., 2022).
Next, we use the following black-box reduction from (s, guarantees to high-probability privacy loss bounds:
Lemma C.5 ((Kasiviswanathan & Smith, 2014)). If mechanism satisfies ()-P), then the probability the privacy loss of its output exceeds 25 is at most 8
Now, the high-level idea is that the (c. DDD guarantee on outpuiting levels j' > j implies high-proot probability bound on the privacy loss of outputting these levels via Lem. C.5, which in turn implies bound on in Lem. C.4 if we use the posterior distribution over shuffles as the distribution in that lemma. Then, we can use Lem. C.4 to get an (c, 6)-DP guarantee for round conditioned on the previous rounds, and as before the resulting per level decays geometrically and we can use basic composition.
Proof of Theorem 5.2. By the upper bound on 6, log(poly (n) /6) O (8))). So, for any con- stant C1 and another constant C2 depending on 61, releasing levels log n c1 log log 1/8 log satisfies
22 /lg(/////// 1/8) log (og()/6) 8/n2 -DP by analysis of the Gaussian mechanism.
Now, we will show by induction that releasing levels j to log n. j S log e₁ log log 1/6, satisfies (Ez, 5,)- DP for:
C 22/log(1/8) log log 1/8)
Ca log(1/8)
Σ
Ej
0V2iogn-3
j log n n- log (1/6)
8 n
89 = =l=log n ei log log(1/8)
(1 + boghlug
the inequality on Ej we assume ei is sufficiently large. The base case of log n - ei log log 1 holds by the aforementioned analysis of the Gaussian mechanism. Now, assuming releasing levels j -1 to log n satisfies (E,, 6DD we will prove releasing levels j to log n satisfies (E,, -DP. Consider the output distribution of level j. conditioned most The privacy loss being at most I implies that conditioned on levels j + 1 to log n's output, no shuffle is more than times as likely any other shuffle, and thus the same is true for equipartitions of the data into
the event that the privacy loss of releasing levels j
log is
24

---

Published as a conference paper ICLR 2024
the sums in level j. Then by Lem. C.4, level j satisfies, say, ( (Sv/log (1/5))
o V22nngn- 6 6/n2)-DP for some sufficiently
large constant c3. assuming C1 is sufficiently large and o 2 ci log (166 log log (18) for a sufficiently large constant C₁- We have
62 (2Vlog(1/)) log log (1/6) + 4ea (1/8)
8jt1 S
So Ej 1/2 for all j. again assuming 2 c4 / (og(1/)) log (1/6) for sufficiently large c4, by Lem, C.5 this event happens with probability at least /e. Then assuming releasing levels j + to log n satisfies (Es+1. 6DP1)-DP by Thm. 4.3 and basic composition, have proven releasing levels to log satisfies (ej, oj)- for
6g log(110) E = E++1+ +
a /2loonm-3' = 65+1 1/e) + 6/n².
The claimed non-recursively defined values for ey: o follow by unrolling the above recursive formula and plugging in the base case j = log π C1 log log 1/6. Now, the full binary tree mechanism with shuffling satisfies (Eo. 6p) for Eo o (1/(1 log log(1/6)
80 S 5 as desired. (Note that the between the constants C C2, C3, there are no circular dependencies, i.e. there does exist set of constants satisfying the assumptions in the proof.)
D EXTENDING MMCC TO "b-MIN-SEP SAMPLING"
(Choquette- Choo al., 2023a) analyzed the b-banded matrix mechanism under the following scheme, which we'll call "b-min-sep sampling": We partition the dataset D into b equal-size subsets, D1, D2,-- .. D₁. To compute X4, we independently include each element of D; (med 6). (where divides i) with probability by; here, we write the sampling probability in these rounds as bp instead of to reflect the fact that the average example still participates in fraction p of rounds in expectation for any choice of 6.
say i (mod
b if
We give a generalization of MMCC that analyzes the matrix mechanism under b-min-sep sampling, that matches the analysis of (Choquette-Chie et al., 2023a) when C is b-banded but can generalize to arbitrary lower triangular matrices. other words, this generalization of MMCC subsumes the analysis in (Choquette- Choo et al., 2023a).
Note that if we want to analyze the privacy guarantee for an example in D,, 1- this is the same as analyzing the privacy guarantee for an example in D1, if we use C with the first i rows/columns cut off. Then, without loss of generality we only need to state a privacy analysis for examples in D1 to get a privacy guarantee that holds for all examples simultaneously, for each D; we can compute privacy guarantee using the above reduction, and then take the worst of these. Further, for some classes matrices, such as Toeplitz matrices, the examples in D2 will have the worst privacy guarantee and thus suffices to only analyze these examples.
We now show Generalized MMCC given in Fig. 6, computes valid privacy guarantec under b-min-sep sampling.
Theorem D.1. Let be the output of b-min-sep sampling, sampling probability p. noise level a satisfies ( + 5D2 (for examples in D
Then the matrix mechanism with matrix C,
25

---

Published as conference paper ICLR 2024
Algorithm 3 Generalized-WCce
1: Input: Matrix C, sampling probability p. noise standard deviation probabilities 61, 62. min-sep b.
2: Delete all columns of except columns 1, b + 26 11...
3: (PiJ jigjm],je[[x/bb] "Generalizede www.rrrbbaailaalaaaaae.
bp, o, v,66)).
b Pi.j is high-probability upper bound on the probability that an example participated in round j. conditioned output in rounds i
<(b)
4: Pi.j = P(i- 11-116111666144111
5: C =
6: for i E [n/ do
PL.D; PLD of MrMMM (1P))) be(la/o)) (C bellm/o)))
7:
8: PLD convolution of (PLD:
9: return min (fs: PLD satisfies (c, DD)-))).
Figure 6: Extension of MMCC to b-min-sep sampling.
Algorithm 4 4empee.iioorroaalllll//lllleCeCe
1: Input: Matrix C E Rmx", sampling probability noise standard deviation probability 6,. > nns is the number of non-zeros.
2: 8' C-(naa())--)
51
3: --1(1 8¹)
Tail bound on normal distribution; here, the standard normal CDF.
4: for i E [m].j E [n] do
5:
if CCC = then
6:
Pij =
7: else
8:
8ij = minimum 8 s.t. Pr(E, ty (C Cia-1,5") > s) 2 88,
,y. i.d. Bern(y)
Si. is a tail bound on the dot product of first - 1 entries of Cx and C1a-15
Gijj =1(C1:--1,,12
9:
20t
Cijj tail bound on the privacy loss of participation in round after outputting first i rounds
Pi. = pesp(e..))
10:
(1xp
11: return (em
Figure 7: Generalization of
26

---

Published as conference paper ICLR 2024
y-ddail20n Libo
Age 021
4020830-4)
Figure 8: Plot of multiplicative improvement in e for the optimal continual counting matrix mechanism as a function of Vlog(n) +I ||Ceill2- We plot n 2", E 21, 77. We use a c||Cei so the value in the unamplified single-participation setting is fixed. All e are for ā = 10-6.
Proof. The algorithm is almost the same as Thm. 4.3, so we just need to justify the key differences. In ((6) and (3) the choice of (
particular, we need to justify (1) the deletion of columns, (2) the choice of Pi.j
(1) is justified by the proof of Theorem 4 in (Choquette-Choo et al., 2023a), which observes that the products of columns of C for which j (mod b) * and the corresponding rows of are independent of D1. i.e. we can treat their products as public information. So does not affect the privacy analysis to delete these rows/columns from C/x, and then view the resulting generated by i.idd sampling every round with probability bp.
(2) and (3) are both justified if to rows of Cx + z instead of a single row. Each these sequential mechanisms is a VMoG mech- anism, which Cor. B.6 allows us to reduce to the scalar PMoG mechanism defined in terms of C in Generaliae zed MMCC. The probabilities pit) are then valid to use in the conditional composition by the same argument as in Thm. 4.3, up to the adjustment to use bō1 instead of 61. This adjustment is valid, since only use fraction 1/b of the values generated by General wew.edooaabbba.. Detaability iitytiaaliii 1Buunds, ie. are union bounding over 1/b as many "bad" events as in the original proof, so we can increase the allowed probability for each "bad" events by (which is implicitly done by increasing 51 by b).
conditional composition sequential mechanisms corresponding
One can verify that (i) for = 1, General Zedd-MCC equivalent to MMCC, and that (ii) if is banded, Generalized-Mee MMCC is equivalent to the privacy analysis (Choquette- Chhu et al., 2023a).
MORE EMPIRICAL E COMPUTATIONS
(Fichtenberger et al., 2023; Henzinger et al., 2023) showed that a post-processiig of the matrix mechanism using the following lrian-araa matrix achieves + o(1) times the optimal Ey error for prefix sums (without amplification): Cijj = f(i - j), where ʃ is defined as
f(k) = {
O,
for & < 0
1, f(k: - 1). (1-
for k 0
for A > 0
Similarly to the binary tree mechanism, we will consider the unamplified paglee-articippation setting as a baseline. In this case, the sensitivity of this matrix mechanism is |Cee i.e. the f2-norm of the first column of C. So again, setting a c c||Ceıl|z results in a fixed e for a fixed Our comparison will be applying the same matrix mechanism with subsampling probability 1/n and the same choice of a.
27

---

Published as conference paper ICLR 2024
In Fig. we we reproduce the plots in Fig. but for this matrix mechanism instead of the binary tree mechanism. The éz-norm of the columns of this matrix asymptotically are O O(vlog n:); because of this, and to make a direct comparison the binary tree mechanism easier, we use v /log(n) +1 I as the x-axis and plot the least squares linear regression. Because the columns this matrix are less orthogonal than those of the matrix for the binary tree mechanism, there is less benefit from amplification in this setting than the binary tree mechanism setting, so we use a larger range of values с E {10, 20, 40) for the noise multiplier to better demonstrate the behavior of the improvement in e.
For sufficiently large a, the improvement in & due to the amplification analysis is again roughly proportional to (log(n) 1. For the same reasons as for the binary tree mechanism, the fit of the linear regression better increases: here, because the columns of this matrix are less orthogonal of is needed for the fit to improve. Here, the constant multiplier in the improvement is smaller; this makes sense as these matrices improve on the error of the binary tree mechanism by constant, and thus the amount by which we can improve the privacy analysis of this matrix mechanism without violating lower bounds is smaller than for the binary tree mechanism.
average, a larger value
F IMPLEMENTATION DETAILS
To implement the MMCC algorithm, extend the class ate class, MixtureGaussi antaananPaviaa which can be used along with other tools in the dp.accounting .nd pld library to implement MMCC. We discuss our implementation and some challenges here. The dp account ing.ntiiiiii....nn. pld library uses the con- vention that privacy losses are decreasing; we use the same convention in the discussions in this section for consistency. Our implementation is currently open-sourced as part of the dp.accounti ng ing library, and PLD accounting for MoG mechanisms can be done using dp.accounting, ppd. wtt.pppp...p........eeeep PLDAccount ant and dp.accounting ww..vepp. htt.r//icn..eattttttttttttttaaan
the open-source Python library db.acccouniing.ple. We Additi weetttiieiisseeiiiiiiie
to cre- that represents the privacy loss distribution of MMMGG
F.1 EXTENDING A
In order to perform all the necessary computations in MMCC, we need to implement the following methods in MixtureGaussiard wtt.Gauussiiaar.vccc..........
1. A method to compute the CDF of the mixture of Gaussians distribution.
2. A method to compute the privacy loss at x.
3. An inverse privacy loss method, i.e. method which takes and computes the smallest achieving this E.
Given the probabilities and sensitivities (2I.P2..... ... Pk and {cr, ......, cx), easily be done by just summing the PDFs/CDFs of the Gaussians in the mixture. This takes at most O(k) times the runtime of the corresponding method for the (subsampled) Gaussian mechanism.
well a, the first two
The third is more problematic. For the subsampled Gaussian mechanism with sampling probability p and sensitivity the privacy loss function (under the remove adjacency) is:
--2
In pexp
+ +1-1)
20
account inwpuutiinn//ie http:tiiggddddgdoopeneeet accaccunni
28

---

Published as a conference paper at ICLR 2024
This function is easily invertible. However, if we consider MMoc((p, p}, (c1, o2)), the privacy loss
x is:
In pexp (201 eg)
-202 cB
(1 p) exp
20²
20²
Because this function includes the sum of two exponential functions of æ, it is not casy to invert. We instead use binary search to get the smallest multiple of A which achieves the desired privacy loss, where A is a parameter we choose that trades off between efficiency and accuracy. That is, if is the privacy loss function, and we want compute the inverse privacy loss of y, return by overestimating v, we also overestimate the privacy loss since we assume the privacy loss is decreasing. Hence this approximation is "pessimistie," i.e. does not cause us report an (s, 0D-P guarantee that not actually satisfied by MMMGG
L (w) A -A. Note that
Note that using binary search requires a (log multiplicative dependence on Ar, that is not incurred for e.g. the subsampled Gaussian for which we can quickly compute the exact inverse privacy loss. Indeed, we observed that this inverse privacy loss method is the bottleneck for our implementation.
F.2 EFFICIENTLY REPRESENTING PMOG AS MoG
As discussed in the previous section, the runtime of our implementation has linear dependence on the number of components in the MoG. However, MMCC, we are actually using PMoGs, which are MoGs with potentially 2n components. So, even just listing the components can be prohibitively expensive.
We instead choose another approximation parameter 4g, and round each entry of C up to the nearest multi- ple of 22. By Lemma B.4, this only worsens the privacy guarantee, i.e. any privacy guarantee we prove for the rounded version of C also applies to the original C. After this rounding, the number components in any MoG we compute the PLD of is most [max, ||e_ , 1/42 + (max, |le, C is the maximum row norm of C). Furthermore, we can compute the probabiiities/seniiiviii with PMoGs. In particular, for each Pi.j Crj pair, we can construct the probability mass function (PMF) of the random variable that is Cj. w.p. Pi. and O) otherwise, and then take the convolution of all such PMFs for row to get the PMF of the discretized sensitivity for the PMoG. For each row, this be done in at most n convolutions, each convolution between two PMFs that have support size at most 2 and max; lee / + n. So the convolutions can be done in time Ommxx elle, ClI, /A2 + n), i.c. our overall runtime is (n max; [|le,_ /A2] + n²²), i.e. polynomial instead of exponential n if e.g. all entries of C are bounded by constant. By doing the convolutions in divide-and-conquer fashion, and using FFT for the convolutions, we can further improve the runtime to Ö(n max; e||e, ClI, /A2] + n²), i.. nearly linear the input size and 1/ 1/2 if the entries of C are bounded by a constant.
efficiently since we are working
F.3 COMPUTING 85.j
Similar to computing the probabilities and sensitivities for the PMoGs, any overestimate of st,j can be used place of 82,j to get a valid privacy guarantee from MMCC by Lemma B.3. Since 8i,; only appears in a lower order term in the definition of eij. weaker tail bound will not affect the privacy guarantee as much. So, in our implementation, we use the following simple and efficient approximation: We use the binomial CDF to obtain exact tail bound t on [|х Ex S' Ty in the definition of s.j. We then take the sum of the t largest values of (Ciii-ij 1 to be our overestimate of s
29

---

Published as a conference paper ICLR 2024
F.4 COMPUTING ALL ROW PLDS
Putting this all together, we must compute PLDs in MMCC, one for each row of C. Though only an (nn) overhead in runtime over computing a single PLD, this O(n) overhead is undesirable as each PLD computation is already quite expensive due to the aforementioned difficulties. However, this component is embarrassingly parallel, which we leverage to massively speed up runtimes.
Note that for some special classes of matrices, will have that multiple rows share the same PLD, which also allows us to dramatically speed up the calculation even without parallelization. For example, this is the case for the binary tree mechanism due to symmetry, well for as b-banded Toeplitz C due to the fact that rows 2b- 1 to n of p and C' are the same (up to an offset in indices that doesn't affect the PLD).
F.5 APPLICATIONS BEYOND MATRIX MECHANISMS
We believe that MoG mechanisms/Mi x www.eaussiinnriiaaaaaeaa vacy analysis of mechanisms beyond the matrix mechanism. We discuss two examples here.
are useful analytic tools for pri-
Privacy amplification via iteration on linear losses: Consider running DP-SGD with sampled minibatches. To get a (e, 8)-DP guarantee, we can compute the PLD for the subsampled Gaussian mechanism, and then compose this PL.D with itself n times. For general non-convex losses, this accounting scheme is tight, even if we only release the last iterate.
For linear losses, we can give a better privacy guarantee for releasing only the last iterate, similarly to (Feld- man et al., 2018): Releasing the last iterate is equivalent in terms of privacy guarantees to Gaussian mecha- nism with random sensitivity Binom(n, p) and variance no² Using Mi xtureGaus i anP r rivacyLoss we get tight (z, (DDP guarantees for this mechanism. Empirically, we found that these can be lot tighter than composition of subsampled Gaussians. For example, using n = 128, = 1/128, a = 1 we found that composition of subsampled Gaussians gives proof of (.806, 10-9)-DP, whereas analyzing the last iterate as a MoG mechanism gives proof of (.291, 10-9)-PP. We conjecture a similar improvement possible for all convex losses, rather than linear losses.
Tight group privacy guarantees for DP-SGD: Consider analyzing the privacy guarantees of DP-SGD under group privacy. That is, we want to give privacy guarantee for pairs of databases differing in k > 1 examples. One way of doing this is to compute a DP guarantee for k 1, then use an example- to-group privacy theorem such as that of (Vadhan, 2017), which shows an (e, 0)-DP mechanism satisfies (ke, k exp(k=)8) > for groups of size k. This is overly pessimistic, since the black-box theorem doesn't 't account for the specific structure of the mechanism. We can instead get relatively tight guarantees via Mi xtuurGauus ai vacylooss: If each example is sampled independently. then the privacy loss of a group of i examples in each round of DP-SGD is dominated by Gaussian mechanism with sensitivity Binomm(, p). Then, we can use Mi stureGauss: iisiirPrrr r va cosss to analyze the composition of n of these MoG mechanisms. Further, note that e.g. in the case where we instead sample a random batch size B in each round (i.e. different examples' participations within the same round are longer independent), we can still use xixureGaussian wwwaanPrivccyyyc rivacyLoss to get a tight analysis by adjusting the sensitivity random variable used. See the follow-up note (Ganesh, 2024) for more details.
30


Reviews:
[{"review_id": "37lOUfIv9Y", "reviewer": "Reviewer_9Vpe", "summary": "This paper considers the problem of privacy amplification due to subsampling or shuffling for the matrix mechanism, which applies to famous algorithms such as binary-tree based algorithm or DP-FTRL. This problem should be interesting to the DP community.", "questions": "Please refer to the section above.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper proposes MMCC, the first algorithm to analyze privacy amplification for general matrix algorithm. By this method, the paper shows an improved privacy amplification result for the binary-tree based algorithm. Furthermore, the conditional composition theorem, as a side product, should have broader utility. Finally, empirical results reveal a performance improvement due to the better accounting for FTRL.", "weaknesses": "Generally speaking, I do not have too much to complain about this paper. The paper considers an interesting question with some nice results. It also lists some reasonable future directions which may help further strengthen the paper. Some minor comments:\n\n1. Although the new privacy amplification applies and improves DP-FTRL, I still believe this paper is more interesting to the DP theory community. Therefore, ICLR might not be the best fit for this paper.\n2. As compared to other FFT-based accounting methods, this algorithm should be much more time-consuming. It remains an interesting question to reduce the running time for some specific use cases.\n3. I would like to see the authors further improve the clarity of the paper. For now, the paper is not quite friendly to the readers who do not have full background on DP-FTRL or DP accounting. One specific suggestion is to explain how DP-FTRL and binary-tree based algorithm fit into the framework defined in section 1.2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YrG3pxzGZE", "reviewer": "Reviewer_FAAy", "summary": "This paper proposes an algorithm to improve the privacy analysis for general matrix mechanisms, a major building block behind DP-FTRL. The paper first proposes a “conditional composition theorem”; then the paper characterizes \"high-probability PLD\" of matrix mechanisms through Mixture of Gaussian mechanisms.", "questions": "Can the author comment about the novelty of Theorem 3.1? It seems to be a simple extension of Lemma A.1 in [1]?\n\n[1] Cohen, Edith, and Xin Lyu. \"The Target-Charging Technique for Privacy Accounting across Interactive Computations.\" NeurIPS (2023)", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work is important for the further development of DP-FTRL. The idea of characterizing the worst-case of matrix mechanism through MoG is interesting. The experiment shows improved privacy-utility tradeoff for DP-FTRL.", "weaknesses": "I don't see major problem with this paper. \n\nHowever, I did not check the details of the proof (though the high-level idea in the maintext makes sense to me).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w3ui0iFNpH", "reviewer": "Reviewer_5cQP", "summary": "This paper presented an algorithm for calculating tight privacy guarantees of a generic matrix mechanism. The paper opens with a conditional composition theorem which improves the analysis when the noises are correlated. Building on the first theorem, the paper then derives privacy guarantees for the matrix mechanism under uniform sampling. The paper also includes a case study where the algorithm is applied to the binary tree mechanism, backed by experimental evidence.", "questions": "None", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical results look novel and sound. The proposed algorithm is also demonstrated effectively in experiments. \n2. The conditional composition theorem could be potentially useful for analyzing general DP mechanisms that involves correlated noise.", "weaknesses": "This paper could be more easy to understand if the author could define the matrix mechanism formally in the beginning with some intuitive interpretation of each variable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m6AAbK9hLY", "reviewer": "Reviewer_aP5d", "summary": "Given a set of workload queries, the matrix mechanism identifies a set of basis vectors, adds noise to these basis vectors, and then computes DP answers to workload queries via linear combinations of the perturbed basis vectors. This unique algorithm structure poses a challenge to quantifying the privacy amplification by subsampling in matrix mechanism -- each subsampled sensitive data is possibly reused multiple times in computing different basis vectors (in which case the final noise added to each query is correlated). Due to the lack of such privacy amplification results in prior works, the DP-FTRL algorithm (which uses matrix mechanism as a crucial component) in general does not exhibit better performance than the DP-SGD algorithm. \n\n- In this paper, the authors prove novel bounds for privacy amplification by subsampling for matrix mechanism. The proof decomposes the output distribution into the composition of multiple mixtures of Gaussian mechanisms, where each mixture component is the conditional distribution of the next basis vector given the participation histories of sensitive data and noisy observations in prior rounds.     \n- By using this analysis, the authors improve the existing unamplified privacy guarantee for the binary-tree-FTRL algorithm under shuffling by a multiplicative factor of $\\Omega(\\sqrt{\\log(n)})$ where $n$ is the size of the dataset. This improvement is supported by numerical experiments. \n- Finally, the authors show that this improved privacy analysis enables performance gain for the DP binary-tree-FTRL algorithm under small $\\varepsilon$ under the CIFAR-10 dataset centralized setup.", "questions": "- Could the authors discuss more about the computation cost and numerical stability of the proved privacy bound? See weakness for more details.\n\n- Related to the above question, given an arbitrary pair of $\\varepsilon, \\delta$ values, how computationally feasible is it to compute the appropriate noise scale that ensures $(\\varepsilon, \\delta)$-DP of the proposed algorithm?\n\n- In the proof of Lemma B.4, page 15, the third inequality from top $Pr_{x\\sim M(D)}[x\\geq t]\\leq Pr_{x\\sim M(D')}[x\\geq t]$, is there a typo and $M(D')$ is meant to be $M'(D)$? I'd also like more clarifications regarding why this inequality suffices to show the MoG mechanism $\\mathcal{M}$ is dominated by a MoG mechanism $\\mathcal{M'}$. Specifically, how this inequality suffice to bound the term $-e^{\\varepsilon}Pr_{x\\sim M'(D')}[x\\geq t]$ in the dominance term $H_{\\varepsilon}(M'(D), M'(D'))$.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel bounds for privacy amplification by subsampling in matrix mechanisms. The proof involves several interesting new techniques, such as conditional composition and the analysis of the mixture of Gaussians mechanism. These techniques are of independent interest and may shed light on privacy amplification by subsampling/shuffling for other algorithms in the literature.\n\n- Comparison with related works are discussed thoroughly, making it easy to follow the significance of the results.", "weaknesses": "- The computation cost for the privacy bounds seems high. Namely, the authors need to compute the privacy loss random variable for the product mixture of the Gaussians mechanism, which involves combinatorially many mixture components. Such procedures seem likely to suffer from high computation cost and numerical instability (especially under a small number of rounds or a small $\\varepsilon$).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)