DP-FTRL Privacy Amplification Analysis — Conference Poster

Paper context

Paper title: Privacy Amplification for Matrix Mechanisms Abstract: A conference poster presenting privacy amplification analysis for correlated noise mechanisms (DP-FTRL), including background, goals, proof sketches with MoG mechanisms, and empirical results showing epsilon improvement. Paper body (method & results): Privacy Amplification for Matrix Mechanisms Christopher A. Choquette-Choo* Arun Ganesh† Thomas Steinke‡ Abhradeep Thakurta§ May 7, 2024 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 applica- ble 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”, 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 ε →0. 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 amplification algorithm also has practical empirical utility: we show it leads to significant improvement in the privacy-utility trade-offs for DP-FTRL algorithms on standard benchmarks. 1 Introduction Privacy amplification is key in differentially private (DP) machine learning (ML) as it enables tighter pri- vacy budgets under certain assumptions on the data processing. For example, one of the main contributions in the DP-SGD (DP Stochastic Gradient Descent) work by Abadi et al. [1] was the “moments accountant”, which relies on privacy amplification [3, 20] for bounding the privacy cost. Recently, privacy amplification analysis enabled Choquette-Choo et al. [5] to show that a class of DP-FTRL (DP Follow-The-Regularized- Leader) algorithms [6, 18, 25] is superior in privacy-utility tradeoffs to DP-SGD.1 At the heart of DP-FTRL is the matrix mechanism [7, 22]. Thus, bringing privacy amplification to matrix mechanisms (MMs) is an important area of research to enable better privacy-utility tradeoffs. The MM effectively computes the prefix sums ∑i≤t xi over a sequence of adaptively chosen vectors {xi : i ∈[n]}. This can be written as computing A · x where A is a lower triangular matrix with all ones and x = [x1| · · · |xn]⊤∈Rn×d. Observe that releasing Ax[i] releases the model parameters at step i in SGD and that if x is the clipped and averaged model gradient (e.g., as returned by any ML optimizer like SGD), then the DP release of Ax gives a DP-FTRL optimizer. The matrix mechanism factorizes A = B · C to minimize the error (introduced in B) in the prefix sum estimates, while ensuring C · x + z satisfies DP, where z is drawn from an isotropic normal distribution. We refer to B as the decoder and C as the encoder. MMs pose a major challenge for privacy amplification analysis. Standard privacy amplification exploits randomness in the selection of minibatches2 but requires that the noise added to each minibatch is inde- *Google DeepMind. cchoquette@google.com. †Google Research. arunganesh@google.com. ‡Google DeepMind. steinke@google.com. §Google DeepMind. athakurta@google.com. 1Precisely, they showed DP-FTRL is never worse, and often better, than DP-SGD—it “pareto-dominates”. 2E.g., for a data set D, a row x[i,:] = ∑d∈S ∇θℓ(θi; d), where S is a randomly chosen subset of D (e.g., sampled uniformly at random from D, or a subset from a random shuffling of D), ℓis a loss function, and θi is obtained via an SGD state update process. 1 arXiv:2310.15526v2 [cs.LG] 4 May 2024 pendent. In the matrix mechanism, a minibatch (xi) contributes to multiple rows of C · x + z, leading to correlated noise that prevents direct application of amplification. This challenge can be seen by the lim- itations of the amplification analysis of Choquette-Choo et al. [5] 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 a large range of ε where banded matrix mechanisms cannot simultaneously leverage the benefits of correlated noise and privacy amplification; in other words, they perform equivalent to, but no bet- ter than, DP-SGD3. 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., [6, 7, 18]. In this work, we provide a generic privacy amplification machinery for adaptive matrix mechanisms for any lower-triangular encoder matrix C that strictly generalizes the approach in [5]. 1.1 Our contributions Our main contribution is to prove a 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 machine learning tasks). We then demonstrate that our method yields both asymptotic improvements and experimental improvements in machine learning. Conditional composition (Sec. 3, Theorem 3.1): This is our main technical tool that gracefully handles dependence between queries in the rows of Cx; this arises due to multiple participations in rows of x for purposes of correlating noise. Specifically, we enable arbitrary queries C[i,:] · x conditioned on C[1:i−1,:] · x + z1:i−1. Standard composition theorems [9] only handle this via a pessimistic worst-case privacy guarantee that holds with certainty for each query. Theorem 3.1 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 [2, 11] to analyze privacy amplification by shuffling. We believe this theorem will be useful for analyzing correlated noise mechanisms beyond those studied herein. Matrix mechanism privacy amplification 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 et al. [5] because we enable “more randomness” in sampling—instead of participating w.p. bp in n/b rounds records can participate w.p. p in all n rounds. Recall we need to analyze the privacy of outputting Cx + z, where rows of x are chosen via uniform sampling. We use Thm. 4.8 to reduce Cx + z to a series of mixture of Gaussians (MoG) mechanisms for which we can use privacy loss distribution (PLD) accounting. MMCC is formally stated in Fig. 1. Binary tree analysis (Sec. 5): Letting σε,δ be the noise required for the Gaussian mechanism to achieve to satisfy (ε, δ)-DP, the binary tree mechanism requires noise σε,δ · p log n + 1. Owing to the versatility of conditional composition, we show that with shuffling, the (non-adaptive) binary tree mechanism only needs noise σε,δ ·O  min{ p log n, p log log(1/δ)}  . This is optimal given current amplification by shuffling results, which require n = Ω(log 1/δ), We believe this requirement is necessary, but if one could show the current amplification by shuffling results hold for any δ then our upper bound would improve to σε,δ · O(1). To the best of our knowledge, this is the first amplification guarantee (of any kind) for the binary tree mechanism. Empirical improvements (Sec. 6): For our empirical studies, we write a library implementing MMCC, which we are currently working on open-sourcing. 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. B for more discussion. Using this library, first we show that ε computed via MMCC for the binary tree mechanism matches the theoretical predictions of Ω( p log n) from Sec. 5. Then we apply our work to machine learning and show we can improve the privacy-utility tradeoff for binary-tree-DP-FTRL [18] entirely post-hoc. Finally, we empirically show that for the problem of minimizing ℓ2 2-error of all prefix-sums, a matrix mechanism 3In Choquette-Choo et al. [5], this region surfaces empirically even for larger ε ≈1. 2 analyzed with MMCC gets smaller error than independent noise mechanisms for much smaller ε than past work. 1.2 Problem Definition Matrix mechanism MM: Consider a workload matrix A ∈Rn×n, and consider a data set D = {d1, . . . , dm} ∈ Dm. Let x = [x1(D)| · · · |xn(D)]⊤∈Rn×d be a matrix s.t. each row xi : 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. Further, each of the xi has the following two properties. a) Decomposability: For the subset of the data set D that xi chooses (call it Si), we have xi(D) = ∑d∈Si gi(d) with gi : D →Rd is a vector valued function, and b) bounded sensitivity: ∀d ∈D : ∥gi(d)∥2 ≤1. Observe that if this randomized function is also a) computing the flattened model gradient, b) clipping each per-example gradient, and c) averages the result, then this retrieves DP machine learning. The class of (DP) MM are those that approximate Ax with low-error (by minimizing some function of Bz). Typically, one designs a pair of matrices B the decoder and C the encoder such that A = BC and Cx + z satisfies DP4, with z isotropic Gaussian noise. We assume C is non-negative for simplicity. Privacy amplification for the MM: In this work we study the problem of amplifying the DP guarantee of the MM if we incorporate the randomness in how the records of each xi are selected (from D), e.g., how the minibatch is sampled. We consider two selection strategies: 1) uniform sampling: each xi selects each entry of D independently w.p. p, and 2) shuffling: First the records of D are randomly permuted, and then each xi picks a fixed disjoint subset (of equal size) from D. Adaptivity: In our work we allow the choice of xi’s to be adaptive, i.e., xi can be chosen based on the first i −1 outputs of MM. Under adaptivity, we will only consider encoder (B) and decoder matrices (C) that are lower triangular. However, for non-adaptive choices of the xi’s we allow arbitrary choice of the matrices B and C. Unless mentioned specifically, all our results will be for the adaptive setting as this pertains to ML. 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 ε-hockey stick divergence between two distributions P, Q is defined as: Hε(P, Q) = Z x max{P(x) −eεQ(x), 0}dx = Ex∼P  max  1 − eε eln(P(x)/Q(x)) , 0  = Ex∼Q h max n eln(P(x)/Q(x)) −eε, 0 oi . A mechanism M satisfies (ε, δ)-DP if and only if for all adjacent databases D, D′ we have Hε(M(D), M(D′)) ≤ δ. From the definition, we see that to obtain the ε-hoc