Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning
Authors: Christopher A. Choquette-Choo
Hugh Brendan McMahan
J Keith Rush
Abhradeep Guha Thakurta
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential privacy
matrix mechanism
machine learning
artificial intelligence
private learning

Abstract: We introduce new differentially private (DP) mechanisms for gradient-based machine learning (ML) training involving multiple passes (epochs) of a dataset, substantially improving the achievable privacy-utility-computation tradeoffs. Our key contribution is an extension of the online matrix factorization DP mechanism to multiple participations, substantially generalizing the approach of DMRST2022. We first give a non-trivial reduction of the problem with per-iteration vector contributions to the simpler one of scalar contributions. Using this, we formulate the construction of optimal (in total squared error at each iterate) matrix mechanisms for SGD variants as a convex program. We provide a closed form solution to the dual function, leading directly to an efficient optimization algorithms.

While tractable, both solving the convex problem offline and computing the necessary noise masks during training can become prohibitively expensive when many training steps are necessary. To address this, we design a Fourier-transform-based mechanism with significantly less computation and only a minor utility decrease.

Extensive empirical evaluation on two tasks, example-level DP for image classification and user-level DP for language modeling, demonstrate substantial improvements over the previous state-of-the-art. Though our primary application is to ML, we note our main DP results are applicable to arbitrary linear queries and hence may have much broader applicability.

Under review as a conference paper at ICLR 2023
MULTI-EPOCH MATRIX FACTORIZATION MECHANISMS FOR PRIVATE MACHINE LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
We introduce new differentially private (DP) mechanisms for gradient- gradient-based ma- chine learning (ML) training involving multiple passes (epochs) of dataset, sub- stantially improving the achievable contribution is extension of the online matrix factorization DP mechanism multiple participations, substantially generalizing the approach of Denisov et al. (2022). We first give conditions under which it is possible to reduce the problem with per-iteration vector contributions to the simpler one of scalar contributions. Using this, formulate the construction of optimal (in total squared error at each iterate) matrix mechanisms for SGD variants as a convex program. We propose efficient optimization algorithm via closed form solution the dual function. While tractable, both solving the convex problem offline and computing the neces- sary noise masks during training can become prohibitively expensive when many training steps are necessary. To address this, we design a tranrirrttansfoomm based mechanism with significantly less computation and only a minor utility decrease. Extensive empirical evaluation two tasks: example-level DP for image clas- sification and user-level DP for language modeling, demonstrate substantial im- provements the previous state-of-the-art. Though our primary application is to ML, we note our main DP results are applicable to arbitrary linear queries and hence may have much broader applicability.
tradeoff'. Our key
INTRODUCTION
Differentially private stochastic gradient descent (DP-SGD) the de facto standard algorithm for DP machine learning (ML) (Song et al., 2013; Abadi et al., 2016 However, obtaining state- of-the-art privacy-utility tradeoffs critically requires use of privacy amplification techniques like shuffling (Erlingsson et al., 2019; Feldman et al., 2022) (Poisson) subsampling (Bassily et al., 2014; Zhu & Wang, 2019; Wang et al., 2019). These in turn require strong assumptions on the manner in which data is processed that rarely valid in applications of DP-SGD. implementing these procedures is often impractical (Kairouz et al., 2021).
Kairouz et al. (2021) recently proposed the DP-FTRL framework that avoids reliance amplifica- tion by sampling. through using DP streaming of prefix sums (Dwork et al., 2010; Chan et al., 201 I; Honaker, 2015). DP-FTRL can often match (or outperform) DP-SGD in privacy-utility tradeoff'.. Indeed, this algorithm enabled McMahan & Thakurta (2022) to train the first known provably DP ML model user data production setting.
Several works have since focused on this primitive as an instantiation of the streaming matrix mech- anism; in particular, Denisov al. (2022) showed that leveraging optimal matrix mechanisms led to significant empirical improvements, though their work was restricted to the single-epoch setting. Shown Figs. and 3, we achieve substantially improved privacy-utility tradeoffs, with compara- ble computation. Our methods outperform all prior work, including DP-SGD with amplification, to as low as 2. To accomplish this, we propose a formalism for measuring multi- partiiiartiiiitiioon sensitivity, given in Section 2, significant extension to the single-participation sensitivity used in in Denisov et al. (2022). We show in Section 3 how one may compute matrix mechanisms optimized for this multi- participation setting. This generalization enables application of optimized streaming matrix mechanisms to settings where each example (or user) may contribute to multiple elements of the data matrix (the matrix formed by stacking unnoised batch gradients in ML).

---

Under review as a conference paper at ICLR 2023
CIFAR10 Privacy versus Accuracy Tradeoff
80
Nonprivate Baseline
lest Accuracy
Mechanism
2 2003 [Ours)
20000:0 (Karouz
Opt Decir m400)es (Ours)
DP-3D Amplikction
MF(c-1n-100 (Denisay all
MFik= 100000 (Ours)
50
Privacy Bucget, r
Figure I: Our optimal multi-epoch matrix and FFT-based mechanisms outperform all others, including DP-SGD with amplification, low ε 4. Using sensitivity calculation of Theorem 2.1 and stamping (Section 5), we optimize a single pass (k = 1) matrix of Denisov et al. (2022) but apply it here with pass. We use online Honaker-based decoder equivalent that of Kairouz et al. (2021) except for a significant improvement to tree-completion in Appendix D.3. Models trained for 20 epochs on CIFARIO with a batch size of 500. We repeat each setting 12 times and show 95% bootstrapped confidence intervals. Empirical setup is in Section 5.1.
We also explore the computational tradeoff's of our approaches. In particular, computing optimal matrix factorizations may become intractable when large numbers of training steps are required as we discuss in Section 4. While this uncommon DP, it can be a limitation when training with SGD for cxample-level privacy. To reduce this cost, we propose and investigate an approach based on the Fast Fourier Transform (FFT) (Nussbaumer, 1981), which is near-optimal for the single-epoch setting and efficiently computable for most, if not all, ML. settings. Indeed, we find this approach still outperforms the mechanisms from the extant literature, even under multiple participations.
the federated algorithms for user-level
Contributions 1) We provide framework for computing the sensitivity of matrix mechanisms under general participation schemas. To do this, prove new theorem bounding sensitivity for multi-dimensional data contributions. This allows us to reduce the problem to that of measuring sen- sitivity for scalar contributions alone (Section 2). We extend the results of Denisov et al. (2022) to the optimization problems corresponding to these generalized notions of sensitivity, showing that the algorithms proposed there can be applied in our setting (Section 3). 3) We propose and analyze factorization based on the Fourier transform which is near optimal for the single-epoch setting and can be efficiently extended handle multiple epochs (Section 4). 4) We perform detailed empirical comparisons of our mechanisms with both the prior matrix mecha- others (in
a computationalll--ffiicoi
nism approaches and DP-SGD, We show that the methods proposed here outperform particular, DP-SGD with amplification), to privacy budgets low & 2, and without any need for privacy amplification (Section 5). 5) We will upload all code used in the final manuscript.
Related work The core privacy primitive here is the matrix mechanism (Li al., 2015). Its long history of study and application was mostly in the offline setting (McKenna et al., 2018; Edmonds al., 2020; Yuan et al., 2016; Hardt & Talwar, 2010). Fichtenberger al. (2022); Denisov et al. (2022) independently applied it to the adaptive streaming setting, where outputs are released one- by-one and privacy analysis must account for an adversary adaptively defining the inputs. Denisov et al. (2022) connected the matrix mechanism to DP ML, via the DP-FTRL algorithm of Kairouz et al. (2021), and showed that computing optimal factorizations significantly improves the privacy- uility-computation tradeoffs when needing only single pass (epoch) over the training data.
Example- and user-level DP, and the connection to federated learning (FL) In addition to example-level DP, we consider user-level DP. As observed by McMahan et al. (2018), private FL. algorithms are well suited to providing user-level DP or other multi-example units of privacy, e.g. document-level, as bounding the sensitivity of single user's contribution to an aggregate update is made straightforward by the per-user data processing pattern inherent in FL. However, our primary application is to datacenter training, where user data can be processed in a fixed shuffled order, unlike cross-device FL. We use the term 'participation' to denote the event that example (user or client in FL) contributes to the gradient sum (or a model update in FL) x; for a given step/iteration (round in FL.) i. Individual contributions x, are scaled so their maximum l norm is Ç. Our
2

---

Under review as a conference paper at ICLR 2023
mechanisms compute sums over individual clipped contributions, and then post post-process by dividing by the batch size (or clients/round) to compute an average gradient (or model update). We assume < 1, applying appropriate scaling needed. Appendix A summarizes terminology and notation.
2 PRIVACY FOR ADAPTIVE STREAMS WITH MULTIPLE PARTICIPATIONS
We define and efficiently bound the sensitivity of the multi-participttion adaptive streaming (con- tinual release) setting, by generalizing Denisov ct al. (2022, Sec. 2). We assume a database of m examples (or users in FL, records in general DP application) that is processed as stream over n steps. A set of B examples is selected on each step i, and processed via an adaptively chosen function (e.g., computing gradient at the current model), producing vector of lg norm at most Ç- These vectors are summed and provided to the DP mechanism as x; E R", which then releases a privatized function of [x,,..., sum X;, we say it participates on step i. We are primarily interested in the case where m/ B < n, and hence each example used on more than one step. This is the multiple epoch setting of ML.
[.i....,x,]] Xi]. the stream so far. When partieular example contributes the
Two data streams x and x are said to be neighboring if they differ in the contributions derived from a single example, either by zeroing out all of its contributions, or by replacing them arbitrarily subject to the norm bound Ç. Thus, the participation pattern does not change (all records contribute to the same steps in x and x, with only the vectors associated with one record changing). We define a participation schema II as the set of possible participation patterns श E II, with each t C [n] indicating a set of steps in which single example might participate. Assuming each record contributes at most once Lsingle-participation II {{1), (2).... {n} }). recovers the standard streaming setting. This captures. for example, training with minibatch SGD using a single pass (epoch) over training dataset. At the other extreme, we have every-step participation with { [m]] where each record contributes to every step. This captures learning with full gradient descent, where we compute the gradient on the full training dataset on every iteration.
Fixed-epoch-order participation We focus participation, where each example participates at most k times, with any adjacent participations exactly b steps apart: formally, II is the set of all ı such that |-|| < k, and if = //1........) we have vjj E (2...... ting, and (k=n, b- b-17,,b-1--artttte -particccciiiiiionnnnn recovers every-step participation, and for example (k-3, b-2)- participation has II = {11,3 3J,,,, (2, 4, j. We focus on this participation schema because: 1) It encompasses multi-epoch SGD training using a data processing pattern celposuppo by modern ML infrastracture. 1 The only requirement is that rather than shuffling the dataset for each epoch, the dataset is shuffled once and the same order of minibatches is used for each epoch. With this setup, ht epochs of training on dataset of size m with batch size B gives n = mk/ B total train- ing steps, and satisfies (k, m/ B) -aattitcciiatoonn 2) We show (e.g.. Eq. (3)) in importance cases this participation schema allows for the efficient computation of sensitivity. 3) We will see in Section 3 that the more possible participation patterns n, the more constrained the problem of finding optimal mechanisms becomes. Hence, a relatively restrictive (but practical) schema like (k: b) participation yields more favorable privacy- utility tradeoffs.
generalization of the above two, (k,
k). k.......,.4.,
1 = b. Note b-n)----apaartiipaattt
recovers the single-epoch set-
Sensitivity of linear queries on multi- purti-particcpatiin adaptive streams Consider a full-rank square query (or workload) matrix A E IR we wish to compute the function x + Ax in a differentially private manner, where we consider inputs x and outputs Ax to be elements of Raxd under geometry inherited from the Frobenius inner product. We utilize the matrix mechanism (Li et al., 2015), which, provided a factorization A BC, computes the estimate
Ax (Cx + z)
(1)
where z is a sample from appropriately scaled isotropic Gaussian noise. The scale is determined by the sensitivity of the mapping x + Cx; roughly, how much outputs of this mapping can vary (in &
'This contrast to Poisson, or independent fxed-sized batch sampling, with replacement across steps, as is assumed by many works (Abadi et al., 2016a; Bassily et al., 2014: Zhu & Wang. 2019; Wang et al., 2019). Many works in fact process batches in a shuffled order without replacement and then incorrectly apply DP analysis for, e.g., Poisson sampling. Indeed, we perform this same- incorrectt-naall for our DP-SGD baseline because reproduces the previous state-of-the-art results for DP-SGD.
3

---

Under review as a conference paper at ICLR 2023
norm) when we swap the input stream x for neighboring one x. We refer to this matrix C as the "encoder", as it encodes x as Cx before adding Gaussian noise. Similarly, we call B the "decoder".
Let N be the set of all pairs of neighboring streams and D := {x - x (x. x) E N} represent the set of all possible deltas between neighboring x, X. The definition of 2 implies it is symmetric
(u E 2 -u E )). We will say D satisfies the participation schema IT if the indices of all nonzero elements in each vector u E D corresponds some π E II. Critically, for linear queries D fully captures the sensitivity of the query:
Definition 1. The sensitivity of the matrix factorization mechanism Eg. (1) is defined
sensp (C) =
sup (x,
||Cx - -C sup |Cule uED
Convexity of || Cullø in u implies that s ||Cu|l SSPPuccov( |Cul| F. and hence with- loss of generality (wlog), we take D to be convex as needed. It is illustrative consider some specific Ds for scalar per-step contributions with Ç = d = 1. Single-pariicipation corresponds to [n]] are the standard basis vectors. Noting
② = convfae; la E [-1.1]. [n]} where e, for ||Cu| = Cull and convexity of ||Cull, we see the maximum will be achieved at some e,, recov- measurement of sensitivity of Li al. (2015, Proposition 3).
ering the mmx--2- (ee-norm--vee-cooe Every-step participation corresponds to the for ball, D = [x ||| S 1).
Conditions allowing the reduction to per-iterate scalar contributions ML, examples are used to calculate gradients of d > 1 dimensions, and so wish to consider Raxd with rows X; E IR corresponding to the sum of gradients for examples participating in step i. In order to compute sensitivity, one may hope that the sensitivity for each x; Rd can be bounded by only considering some appropriately worst-case I; E R.. More formally, consider a fixed participation schema 11, and further assume (wlog) Ç 1. Then, for vector-valued contributions we have
Dj = conv {G Raxd x
3
II s.t. || S 1 for i E x and GG.)) for & T)
In the d case, we have a much simpler polytope. 11 = conv(DH) where
D = U ( I E if E π, 0 otherwise }.
xEll
One might hope to show sens (C) S scns (C), and the authors in fact initially conjectured this to be true. To our surprise, while this inequality holds under a variety of assumptions, it does not hold in general (Appendix H.2 gives counterexample). Empirically we have observed that for various query matrices A and (k, bapttiiiiiitiionnn with d = 1, the optimal C satisfy (or almost satisfy) the condition C C 2 0 (element-wise non non-negativity). In this case, we can show:
Corollary 2.1. When per-step contributions bounded by ( for any participation schema 11 and dimensionality d 2 1, when C C 2 O elementwise, we have sensp (C) = sensp) (C).
In particular, this implies that if C is optimal in the d = 1 case and satisfies CT 2 0, it is also optimal in the > 1 case. This result is a corollary of Theorem H.1, which establishes additional conditions under which sensøg (C)= < senso; (C) holds. All proofs are in Appendix H onwards.
Difficulty of computing sens(C) C) In general, computing sens(C) is a convex quadratic maximiza- tion problem over a convex set, which can be NP-hard. Even the simple case of computing the sensitivity for arbitrary matrix C' under every-step participation with scalar (d = 1) contributions is NP- is exactly the problem of computing the lx--2 operator norm (Tropp, 2004). (In fact, is useful observe sens (+) can always be viewed an operator norm, see Appendix B). This hardness is in stark contrast to the single-partee angle-participation setting, where calculating sensitivity is trivial. However, we can in some cases compute sensitivity exactly by brute force. Take d 1. Observe DH is finite set and so a direct calculation by using Eq. (2) is often possible. But, ['Hl = | and observing the symmetry |Cu|| = |C(-u) can reduce the computational cost only by half. In general [T] may be exponential in k, but in the special case of (k, b) paarticciiptio,, we have |TT| = b
We conjecture it is "almost" true; tightly bounding the necessary error is interesting open question.
4

---

Under review as a conference paper at ICLR 2023
(the number of steps in one epoch). Hence, for modest numbers of epochs k directly computing sen- sitivity is possible, e.g., in our StackOverflow experiments in Section 5.2, we can reduce u E Dj to only 342 2 = 10, 944 vectors. Theorem H.1 can be used to translate bounds from scalar to higher dimensions, though without such a translation it is not clear how to generalize a brute-force method.
Computing sensitivity when C 2 0 Let X = CTC. C. When X has only nonnegative elements, one may reduce the problem of computing senso) (C) to
sens (C) = max
CullF = max Vu Xu = max D
1 X 7. 1,
(3)
where X [s.9]] E I kkk is the submatrix of X formed from the rows and columns selected by n, |T]| = k and 1 E RR*. The first equality follows from Corollary 2.1, and then the max must be achieved by the maximum- magnniuue nonnegative vector u. specifically 1 As noted above, the matrices we consider satisfy this property, and hence we can compute the exact sensitivity efficiently for (k, b) participation.
Upper-bounding sensitivity As an alternative to structural conditions on C or X allowing effi cient exact computation of sensitivity for d > 1, we can look to (reasonably tight) upper bounds on the sensitivity of C. In the case of (k, partiiiiiiit,,,, one efficient method of computing upper bounds for the tatiple-participatioo sensitivity of C has shown itself to be particularly useful:
Theorem 2.1. Let C RTx", and take some participation schema 11, with k max ||| the maximum number of participations. With Cp..) representing selecting the columns of the matrix C indexed by x and |1-112 the spectral matrix norm, let X max |. Then sensp) (C) AvR.
In the (k, b)- pa-ppicciipaiionn case, II| = b. The complexity of computing the largest eigenvalue of the subselected C matrix cubic in k. Thus, computing this upper bound is of order bk easily computable for the range of k, b considered here (k < 100, b I 500).
Differential Privacy Guarantee Using our generalization of adaptive streams to multiple partic- ipations we obtain the following result (a straightforward generalization of Denisov al. (2022, Theorem 2.1)). The proof is identical that in Denisov et al. (2022), except we replace the sensitivity bound with that for multiple participations obtained via Corollary 2.1.
Theorem 2.2. Let A R be a lower-triangular full- full-rank query matrix, and let A = BC be any factorization with the following property: for any two neighboring streams x E Rnxd, we have |[[(x - |) S K. Let ~ (O, 2 with a large enough so that M(x) = Ax BZ B(Cx Z) satisfies (e. 8)-DP (or p-zCDP p-Gaassian DP) in the nonadaptive continual release model. Then, M satisfies the same DP guarantee (with the same parameters) even when the rows of the imput are chosen adaptively.
OPTIMIZING MATRIX MECHANISMS FOR MULTIPLE EPOCHS
We now present methods for computing optimal matrix mechanisms that are specialized to a spe- cific participation schema II and query matrix A. For example, Fig. 2 shows the optimal factoriza- tion for the query matrix A representing SGD with momentum and coldown under (k=6, b=342)- participation, used in Section 5.2. Specializing the mechanism both the participation pattern and the specific query workload enables as to obtain state-of-the-art results in ML (Section 5).
We follow the approach of Denisov al. (2022) which showed empirical improvements over prior methods in single-epoch settings. We begin by defining the loss of interest, i.e., the total variance of noise added, for the mechanism defined in Eq. (1). Note that this loss characterizes other downstream tasks like DP Mean Estimation. Given D, assume that we may represent D = conv(D) for some finite set D-as as we have seen, this is the case, e.g., in (k, ppartiiciiattion Then the loss which corresponds to total squared error of factorization, at a fixed privacy level, may be expressed as:
C(B, C) = sens (C) B 2
where
sens (C) = sup || Cu 1 sup CCll..
(4)
uE
uED
5

---

Under review as a conference paper at ICLR 2023
A matrix
matrix
C matrix
C
The optimal factorization A = BC under (k=6, ----334--artiiiipalll constructed by solving the optimization problem Eq. (5). Matrix encodes SGD with momentum 0.95 and learning-rate cooldown schedule for the last 25% of rounds, as used in our StackOverlow experi- ments (Section 5.2). The constraints on sensitivity imposed by this participation schema are evident in the resulting matrices. For example, the white diagonals with period of 342 in X = C C show that the columns C that could correspond might participate are in fact orthogonal. See Fig. 13 in Appendix F,4 for larger view.
Figure 2:
pair of rounds (i.j) where the same user
Observing that va the mechanism consider the constrained version of the problem of minimizing this loss where sens (C) S 1. Since for any C, B ACI produces the minimum-FFobeneee Frobeneous norm B B-matrix, it is sufficient solve:
(a (2 has identical loss, we conclude that we may
min L (ACt, C) Cisens C
min
||A
(5)
With the change of variables
= C C, equivalently:
min
tr( tr(ATAx where scns ( I sup T Xu.
(6)
SCnSE (X)=1
WED
Theorem 3.1. Let finite D = {u: )/= be given, and assume that the vectors {ui]ez span R Assume that A is full-rank, and for E R define Hy = [u,...., un] diag(v)2/2 U= H.H. Define the Lagrangian as L (X, v) == tr(A tr(ATAX-I) E Vu (u Xu Su-1) Then, for La- grange multipliers v such that the U full-rank, the minimizer X (v) of for this fixed v may be represented X (v) = U- (UŽ -U= A
A U and the Lagrange dual function for the problem Eq. (6) can be expressed in closed form in terms of the dual variables v:
g(v)= = inf L(X, v) = 2t ((U ((UŠATAU?)))
A
Σ uE
where the Lagrangian has a finite, positive-definite minimizer in the primal variable; if the vectors {u} span R", the prob- lem Eq. (6) has finite minimizer by Lemma I.I. Any setting of the dual variables corresponding to this minimizer is contained a neighborhood uniformly satisfying this full-rank property, and so it is valid to differentiate expression for g with respect such v (as will do in Appendix I.1).
Remark. The restriction that yields full-rank U serves to restrict
Corollary 3.1. In the same setup Theorem 3.1. the gradient of the dual function g is: 8v.
8g
u TU- (OAATAU) U uu - 1. Moreover, a maximizer of the dual v* must satisfy:
v"= diagpart ((H7.A (HH..TAA..)+)) AH.))
The optimal value of the problem defined in Eq. (6) is (v*).
Remark. In the iaggle-articipattinn case of Denisov et al. (2022), H, = diag(v)), and Eq. (8) recovers the fixed point expression of that paper's Theorem 3.2. Our Corollary 3.1 implies that the optimization methods presented in Denisov et al. (2022) may applied, with suitable translation, to setting; these methods to generate the optimal matrices studied empirically in Section 5.
DP-PREFIX SUM ESTIMATION
Our work has two types of computation costs: optimization costs are those associated with op- timizing and generating (or, computing) mechanism whereas noise generation costs those

---

Under review as a conference paper at ICLR 2023
associated with using the mechanism to sample noise for DP prefix sum release. Note that once optimized, a single mechanism can be reused indefimitely to generate noise for other runs by simply resampling new noise and applying the same decoder. The best known methods for computing the optimal factorizations scale as at least O(n²) (Yuan et al., 2016; Denisov et al., 2022). This opti- mization cost become intractable when grows too large. Thus, in this section we focus on reducing optimization computation at small decrease in the achievable privacy-utility tradeoff.
A prime candidate for this goal is the Discrete Fourier Transform (DFT) because there are known algorithms both for nearly-optimal private convolutions (Fawaz et al., 2013) which are intimately related to the DFT, and for efficient calculation of the DFT using the Fast Fourier Transform (FFT) (Nussbaumer, 1981). We present an FFT-based mechanism that reduces the noise genera- tion costs. We then prove rigorous DP guarantees for it and show that these lead to near-optimal privacy-utility tradeoffs in the single-epoch setting. We provide two improvements over prior work: 1) extending the result to the multi-epoch and multi-dimensional setting and 2) providing explicit non-asympiotic analysis of the algorithm's 'ss utility.
Let A represent the (Toeplitz) matrix all Is on or below the main diagonal and Os elsewhere; i.e., the prefix-sum matrix. In this section, we perform our analysis in the Fourier domain. To release Ax, we define a circulant matrix Acire E 2n2x2n with a corresponding input vector Xext = concat(x, O,), O, E {0)" that the first entries of Xext Thus, we study the DP release of Xeit Note, to be consistent with the literature on FFT, in this section, and in Appendix J, we will index all the vectors and matrices with starting index of zero.
equal to Ax (see Appendix J.1).
Theorem J.1 of Gray (2006) (restated in Appendix J.1) shows there exists a diagonal E such that Acirc F EF for diagonal Σ, where F is the DFT matrix. Then, Acire can then be factorized as Acire = Ceire where Beire 1'2 and Ceire = ///FF.
The (complex-valle) -valued) matrix mechanism specified by the factorization above (and presented as Al- gorithm 1 of Appendix C) is nearly optimal in the class of matrix-factorizztion-b
mechanisms, as we show in Appendix J. Though we prove a simple zCDP guarantee for any participation schema instead use Corollary 2.1
having at most k = max |<]] participations in Theorem 1. when the participation schema is known in advance (as in our experiments with (k, b), b)-participation).
Theorem 4.1. Under k-participation, Algorithm 1 satisfies (k D)=cCDP
The optimal FFT decoder Observe from Theorems 2.1 and 2.2 that the privacy guarantee of our multi- coltippprticciaaioon adaptive setting is independent of the choice of decoder, B. Thus, instead of taking Beire above, we take the optimal decoder using the Moore-Penrose pseudoinverse of the encoder, i.e., Beire SC cire- We do using equivalent encoder C R=*2n as shown in Appendix K. We find that this leads to significant improvements in the privacy-utility tradeoff (see Fig. 9 in Appendix E) no additional computational overhead.
Computation Costs Though we define the optimal FFT decoder as pseudoinverse, observe that we do not need to optimize (or even compute) the decoder; by Appendix K, the problem is reduced to that of solving highly structured linear system. However, we find that even suboptimal imple- mentations using the pseudoinverse can still factorize a mechanism for 10, 000 in 146 minutes on a V100 GPU, remaining well within practical requirements since we need only generate a mech- anism once, before it can reused indefinitely for training. In contrast, computing optimal matrices becomes practically difficult near se 10, 000, taking 24 hours to compute an effective factorization for n = 8, 192 using batch-priority cloud CPU resources. We remark that this regime of n is highly practical, e.g., standard federated benchmarks use n 2000 (Reddi et al., 2020) and our central image classification use n = 2000. In terms of noise generation, the FFT mechanism shows prefer- able asymptotic properties, scaling as Ond n). However, even the optimal matrix mechanism with runtime scaling as Odd?), noise generation on GPU (even with significantly suboptimal implementation) takes negligible time. Further, noise from our mechanisms can be pre-generated needed. We discuss these tradeoffs in Appendix C.
7

---

Under review as a conference paper at ICLR 2023
5 EMPIRICAL EVALUATION
We compare four main mechanism classes: tree-based mechanisms (Honaker, 2015). including 'tre-ccoppletion of Kairouz et al. (2021); our FFT mechanism; our optimal factorizations; and DP-SGD with (though incorrect) amplification via Poisson Subsampling (Abadi et al., 2016b).
When computing optimal factorizations by solving Eq. (6), we may vary the sensitivity constraint set 'D to encode different participation schemas. We compute optimal factorizations for the (k, b)- participation setting. An encoder C factorized for one value of can be applied for another, by simply computing its new sensitivity (due to our Section 2), though this will alter its privacy-utility tradeoffs. For example, our MF1,6 6e in Fig. 3 uses this to extend Denisov et al. (2022) to ls > 1.
When applying mechanism that is determined independently of the number of participations (e.g., FFT or tree aggregation) or extending an optimal mechanism for & participations to a larger number of participations, the sensitivity may scale poorly in k. In such cases, it may actually have lower sen- sitivity to reuse a single encoder multiple times over the course of n steps, and hence more favorable privacy-utility tradcoffs. We term this approach encoder stamping. This also provides a straightfor- ward method for extending any factorization to handle more iterations without, c.g., re-optimizing Eq. (6). Combined with our Section 2, stamping lets us apply mechanisms from Denisov et al. (2022), e.g., MF(k-1, n-1000) x in Fig. 1; mechanisms with stamping have "xs" appended in this way. Discussion of stamping and its relation to existing literature are Appendix D.4.
The manner in which baselines from the extant literature map to this setting can be found in Ap- pendix D. Since the matrix mechanism reduces privacy cost of training to that of the release of a single Gaussian mechanism, accounting in our case becomes quite simple; see Appendix D.2.
5.1 EXAMPLE-LEVEL DP FOR AN IMAGE CLASSIFICATION TASK.
We train image classification models on CIFAR1O (Krizhevsky, 2009) which has become de facto standard for comparing DP ML algorithms- algorithns--sffcciennly easy for existing DP algorithms to achieve nontrivial accuracy, but not so simple so as to be unable to differentiate approaches. Details on our full setup are in Appendix E; generally, they match those of Kairouz et al. (2021). Notably, we make improvements on their Online Honaker-based approach by not just completing the tree with virtual steps, but also zeroing out noise from virtual steps as detailed in Appendix D.3. We find this led significant improvements around a few percentage points. For all matrix mechanisms except the Denisov et al. (2022) baseline and our Optimal MF(A: 20, dim = 2000) 1, we optimize over the stamps s by the losses Appendix D.5, which we find well match the ordering in MI. accuracy.
In contrast to Section 5.2, in this section we only compare factorizations of the prefix-sum matrix; we do not incorporate momentum or cooldown directly into the mechanisms, though we use both momentum and cooldown as postprocessing for the port results for the best settings we find (with both). For DP-SGD, we report results for the best setting (no momentum, with cooldown). Details are in Appendix E.
mechanisms and re-
Main results (Figure 1) First, see that the optimal factorization for the target (k. (20, 100) setting outperforms all other mechanisms across (nearly) all privacy levels, only slightly underperforming SP-SGD with amplification E = 2. To the best of our knowledge, this represents the first empirical demonstration of an MI. algorithm which is competitive with DP-SGD into this high-privacy regime, without any amplification by sampling. The FFT (optimal decoder) mechanism outperforms all baselines, again well toward the high-privacy regime at s s 4. Though at a worse privacy-utility tradeoff compared with our multi-epoch optimal matrices, this mechanism shows promise for outperforming prior work when grows too large for generating optimal factorizations.
5.2 USER-LEVEL DP FOR NEXT WORD PREDICTION TASK
User-level DP for language models is an important real-word task (McMahan & Thakurta, 2022). There is much history in the DP language modelling literature, which we briefly describe in Ap- pendix F.I. Here, we use the standard benchmark: StackOverflow next-word prediction (Reddi et al., 2020). Our experimental setup fixes the same model and hyperparameters as Kairouz et al. (2021) and Denisov et al. (2022) except notable changes below. Details are in Appendix F.2.
8

---

Under review as a conference paper at ICLR 2023
StackOverflow NWP Accuracy vs Privacy
Zoomed view of high accuracies
0.26
0.255
0.25
0.5
Test Set accuracy
0.24
Test set accuracy
0.23
0.245
DP-GDM, 2052e
0.22
MF6, 6e (Ours)
0.21
(Ours)
0.240
MF1, 1e (Denisov
0.20
Honaker, 6e (Kairouz'21)
0.235
DP-SGDM, 6e
0.19
0.0
2.5
5.0
7.5
10.0
12.5
15.0 17.5
20.0
10 15
20
D at 5= 10
DP = 10
Figure 3: Our 6F achieves within 2% relative difference in performance from the non- private baseline at 8.8, 8 = 10-6. Our MF1,6e, though worse, outperforms all baselines from the literature. Select runs were replicated multiple times, with bootstrap 95% intervals shown. DP-GDM, 20-52 is the extreme case of every-round participation (342x more computationally ex- pensive than epochs of training), and hence generally infeasíble. The server learning rate 7/s was optimized over 0.5 and 1.0, and additionally 0.25 for = 2. The blue bands give the non-private baseline accuracy for epochs of training with 77 = 1.0 and 0.5.
Notable changes from prior work We use much higher 1000 clients per round (= 100 in prior work)-enabled mainly by our multi-epoch factorizations. We also zero out large updates with for norm greater than 100 (rather than scaling down to our clipping norm of Ç = 1) as we found this improved the stability of noisy training (see Table 2 in Appendix F.3). This may have enabled more consistent success of higher server learning rate n, 1.0.
We conducted initial simulations which verified that two observations from Denisov et al. (2022) for the single-epoch setting extended to our multi-epoch and large-batch (1000elients/roundd instead of 167) setting. First, linear server learning rate cooldown from 1 x to 0.05x over the final 512 rounds offered small improvement over constant rates (more so in the higher-privacy regime). Second, optimizing a factorizing with momentum and this cooldown schedule, rather than applying both as post-processing, consistently offers small benefit. See Appendix F.2 for details. Thus, for our primary investigation we fix these preferable design choices and compare the following algorithms.
Algorithms All algorithms train for 6 epochs 2052 rounds, and a large-batch 1000 clients/round (better for DP training) unless otherwise noted. Honaker, 6e the DP-FTRL algorithm of Kairouz et al. (2021), trained for 2048 rounds (a power of 2). MF1, (Denisov et al., 2022) is the state- of-the-art for single-epoch training, using 167 clients/round and 1=1. MF1, 6e uses our Eq. (3) to take the (non-negative) (k= (-=ti--otimizzed matrix of the previous approach and compute the sensi- tivity under (k=6, ----444---artiippule
allowing us to train for 6 epochs (2048 rounds) with large batches. 6F6,6e is our approach directly optimizing the matrix factorization for (k=6, 6=342). participation via Eq. (6). DP-SGDM, 6e is the DP DP-FedAvg algorithm of McMahan et al. (2018), to 2052 rounds, and accounted with Poisson sampling an incorrect, though standard, accounting computation, as noted in Section 1. DP-GDM, 2052e is full-batch gradient descent for 2052 rounds and 2052 epochs, or 342x the computation cost of our epoch runs. We compute the exact privacy cost for this approach, and estimate the accuracy from experiments with 1000 clients per round for eepeeimemmtt
computational efficiency, following the methodology of Kairouz et al. (2021). This is essentially an upper bound on the best privacy-accuracy tradeoffs with unlimited computational resources.
Main results (Figure 3) We find that our MF6, 6e, is the best feasible private result at 25.25% accuracy and (17.7, 10 10--1-0-0-0- -DP. This exceeds the non-private baseline of 25. 25.2% accuracy reported by Kairouz et al. (2021), is within the margins of small hyperparameter tuning differences of our improved non-private baselines (25.43%) and private full-batch gradient descent (25.31%) 1).. At (8.84, 10 -DP, MF6, 6e achieves 24.94% accuracy, substantially improving over the previous state-of-the-art at this privacy level given by 1F1, at 24.11% accuracy, and considerably im- proves both the accuracy and privacy of Honaker, 6e (24.86% accuracy (21.0, 10 DDPP). In fact, we achieve better accuracy at E = 8.84 than prior methods achieve at E = 17.7. DP-SGDM,66 is outperformed by MF6, 6e and MF1,6e across all values evaluated. Fig. 12 in Appendix F shows results for each learning rate separately, with numeric results in Tables 4 and 5.
Discussion and conclusions can be found in Appendix G.

---

Frank de Hoog. A algorithm for solving toeplitz systems of equations. Linear Alge- bra and its Applications, 88 08-89:123-133 1987. ISSN 0024-3795. doi: htps://doi.org 10.1016/00244775587799090001 Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference computer and communications security, pp. 308-318, 2016a.
Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Con- ference Computer and Communications Security, Oct 2016b. doi: 10.1145/2976749.297558 URL http:/ / /ttp//xxx/// doi. .oo.oorg///oo.oooooooo..oo.oo..r org 10. http//..1111////1 www.:1115/2999 77997 2978318.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Proc. of the 2014 IEEE 55th Annual Symp. on Foundations of Computer Science (FOCS), pp. 464-473, 2014.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryplography Conference, pp. 635-658. Springer, 2016.
S. L. Campbell and C. D. Meyer. Generulized inverses of linear trunsformations / S. L. Campbell, C. D. Meyer. Pitman London San Francisco, 1979. ISBN 0273084224.
Lei Cao, Darian Mclaren, and Sarah Plosker. Centrosymmetric stochastic matrices. Linear and Multilinear Algebra, 70(3):449-44 2022.
Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In Proceedings of the 28th USENIX Conference on Security Symposium, SEC' 19, pp. 267-284, USA, 2019. USENIX Asso- ciation. ISBN 9781939133069.
Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert- Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Úlfar Erlingsson, Alina Oprea, and Colin Raf- fel. Extracting training data from large language models. In 30th USENIX Security Sympo- sium (USENIX Security 21), pp. 6633-2650. USENIX Association, August 2021. ISBN 978-1- 939133-24-3, URL https::///// //t////wwww/ www.. usenix .eaeniiiorrg//oooooo htt///oafeeeeeeeeeeeeeeeertoooot presentation/ cwaoonnaaaanniiiiiiiiiiaaamiiiin -etriiieettttttnn.nn
T.HH. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. on Information Systems Security, 14(3):26:1226:244 November 2011.
Soham De. Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlock- ing high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 13650, 2022.
URL https: :/ta:://www /tt::///www.t. www.:.iiiieeieire........... wwtpeett..ooc/ceeeeeeeeeeeeeeeee
Sergey Denisov, Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators adaptive streams, 2022. URL https: /ttp//axvvv/////////////.///.atl org. /2002.2222..2 08312.
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under con- tinual observation. In Proc. the the Forty-Second ACM Symp. Theory of Computing (STOC' 10), pp. 715-724, 2010.
Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The Power of Factorization Mech- anisms in Local and Central Differential Privacy, pp. 425-438. Association for Computing Ma- chinery, New York, NY, USA, 2020. ISBN 9781 9781490369794, URL https: : /doi. org/ axg/10 1C.
3384297.
10

---

Under review as a conference paper at ICLR 2023
Ü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 Proceedings of the Thirtieth Annual ACM-SIAM Symposium Discrete Algo- rithms, pp. 2468-2479. SIAM, 2019.
Nadia Fawaz, S Muthukrishnan, and Aleksandar Nikolov. Nearly optimal private convolution. In European Symposium on Algorithms, pp. 445-456. Springer, 2013.
Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 954-964. IEEE, 2022.
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation, 2022. URL httpps://aaaaaat org abs/2202. 11205.
Robert Gray. Toeplitz and circulant matrices: review. 2006.
Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, 2010.
Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differ- entially private continual counting. Personal communication, 2022.
James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differen- fial Privacy (TPDP 2015), London, UK, 2015.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Journal of Machine Learning Research, 17(17)1-51, 2016. URL http: / jmlr. htggpappers/117115 135. html.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. ICML, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009.
Chao Li, Gerome Miklau, Michael Hay, Andrew Megregor, and Vibhor Rastogi. The matrix mech- anism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24: 757-781, 2015.
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy. Proc. VLDB Endow. 11(10): 1206-1219, jun 2018. ISSN 2150-8097, doi: 10.14778/3231551.3333888 URL https:// 00..
Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations (ICLR),
2018. URL https::// http:a/wwww.eeeeeeeeadd.dddo-oo. wtw.t//pppai---30.11100000
H. Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential pri- vacy guarantees. Google Al Blog, 2022. URL https: //ai aaii.googlebooo cwm/ 2022/
02/ffederaeed-11 lenedddlerrning-ee - httrmll.hllll......mmmmmmmmmm..m
Henri Nussbaumer. The fast fourier transform. Fast Fourier Transform and Convolution Algo- rithms, pp. 80-111. Springer, 1981.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization. CoRR, abs/2003.00295. 000900 2020. URL https: http:////xivvvoooo org/ abs/ 2003. 00295.
Congzheng Song and Vitaly Shmatikov. Auditing data provenance in text-generation models. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 196-206. 2019.

---

Under review as a conference paper at ICLR 2023
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differ- entially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pp. 245-244225 IEEE, 2013.
Joel Tropp. Topics in Sparse Approximation. PhD thesis, The University of Texas Austin, 2004.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled renyi differential privacy and analytical moments accountant. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, pp- 1226 1235, 2019.
Ganzhao Yuan, Yin Yang. Zhenjie Zhang, and Zhifeng Hao. Optimal linear aggregate query pro- cessing under approximate differential privacy. CoRR, abs/1602.04302, 2016. URL http: www.aiiwwwgg.a////a/aaee.aaa/e/e /102.. 04302.
Yuging Zhu and Yu-Xiang Wang. Poisson subsampled rényi differential privacy, In International Conference on Machine Learning, pp. 7634-7642. PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
A
SUMMARY OF NOTATION AND TERMINOLOGY
The following table summarizes the notation used throughout the paper:
Number of steps of the streaming linear query (SGD steps or FL rounds)
d
Dimension of per-step user contributions.
X; RR or Rd
Sum of per-example gradients (or per-user model updates) on step i.
Rxdd
Stream of inputs X,. equiv. matrix with rows x, (so X(t.))) Clipping norm that limits the size of per-example contributions to X;.
Participation pattern, the set of steps that an example could participation in. Participation schema, set sets of steps (set of all π an example could participate in.
= {x x (x, x) E N). the set of deltas between neighboring input streams x, x. Corners of I when assumed to be a polytope, D = conv(D). participation schema II with at most participations, separated by exactly Lower-triangular linear query matrix to be factorized as A BC.
(ks, bpppaticciptioonn
A E R
T E R
T A for convenience.
Amia (A), Amax (A).
Smallest and largest eigenvalues of real matrix A. Conjugate (Hermitian) transpose of A.
A*
X
matrix X that is "optimal" context-dependent sense.
A
Peooreeeerroeee pseudoinverse matrix A.
Ajjl
The (i, tht entry of matrix A.
A [i. and (ud
The thh row and jth column. Number of encoder C replications (stamps) into block-diagonal matrix. Convex hull of the set S.
conv (S)
[n]]
-L,,..,,22 n2
|X |F
The Frobenius norm of matrix X.
We utilize terminology from federated learning as well as standard centralized training, which gen- erally map as follows:
Centralized
Federated
example
user or client
batch size
clients-per-round
DP-SGD
DP-FedAvg
step or iteration
(communication) round
gradient
model update
B GENERALIZED SENSITIVITY AS AN OPERATOR NORM
Eq. (2) shows that our generalized notion sensitivity can be viewed directly as a particular operator norm. To this, view C. Vi + V2 linear operator from vector space V to V2. Then with || (() the vector norm on V, and similarly for V2, an operator norm is defined as
||C|l)))))
max sI [Cull(2)
13

---

Under review as a conference paper at ICLR 2023
Because the Gaussian mechanism and thus are interested in the lg sensitivity, (1l 11-1122 and we define the norm
u (1) |u]l == inf { 0: }
the vector norm induced by D (the fact that D is a closed, convex, symmetric set ensures this is a norm). Note + ||u| S Thus, have
scns (C) ||
(9)
C THE FFT MECHANISMS AND REDUCING COMPUTATION
Algorithm DP-Prefix Sum Computation via FFT (with 1)
Inputs: Data vector x E R" (with each | S () and zCDP parameter p.
DDT Can the DFT of (defined in Eq. (34)). Let vDFT be the first n coordinates.
[sm]
F DFT matrix in 2n-dimensions, where the k-th row of F is given by
1
_2
[..]
exp
a {O..... 2n 13
22n
2n
(2,, w) + (diag(vDFF) standard complex Normal in 2n-dimensions). F
(s, 2) Xo: Xo + X1.
Σ
Fa
(F*51/2. w)
4np
Output + Z.real (0....,
We propose two FFT mechanisms. First, we propose the FFT mechanism which is described in Algorithm 1. This mechanism has the same computation complexity- no optimization costs and O O(dd n) noise generation- the Honaker method used in Kairouz al. (2021) but at bet- ter privacy-utility tradeoff, as shown in Fig. 9. The privacy and utility analysis can be found in Appendix J.
The FFT Optimal Decoder (FFT_Opt_Dec) mechanism presented in Section 4 represents taking (a real-valued translation of) the encoder C from Algorithm and using the optimal decoder, defined in terms of the Moore-Penrose pseudoinverse of C. Similarly to Algorithm 1, there is no need to construct literal matrix multiply by in the case of noise defined by the optimal decoder; noise generation time of the mechanism, however, increases by logarithmic factor to O(dd log n) (as discussed in Appendix K). This complexity is still feasible for many steps (which we will discuss below) and comes with significant utility benefits (see Fig. 1).
All the mechanisms we study scale as either O(n)) or O(n polylog(n)). For our n = 2000 step environments, and even far beyond to GPUs with runtime on the order of seconds per step (including computing and applying gradients and noise). The main challenge in these cases are storing the n² + nd coordinates GPU memory (the former for the decoder matrix, the latter for the noise samples). Given that each of the d coordinates of noise can sampled independently, this algorithm straightforwardly parallelizable and work may be partitioned across many processors when needed. Noises could instead be pre- generated in an entirely separate process, and stored on disk, to be loaded into memory row-by-row concurrently with training.
10, 000, our algorithms can be efficiently realized on
Outside of computation, both our FFT mechanisms take ((nd) space as all noises for the x E Raxd must be pre- rre-generated. This is in contrast all prior work, and even optimal factorizations, which require only ((d) space to generate the noise at the current step. Again, we note that space ofter much cheaper this is typically not the limiting factor.
14

---

Under review as a conference paper at ICLR 2023
D MECHANISMS UNDER CONSIDERATION: BASELINES, SUBTLETIES, AND LOSSES.
D.1 BASELINES
Kairouz et al. (2021) and Denisov et al. (2022) both present approaches for ML model training which can be understood as instances of the matrix mechanism-the former grounded in the binary- tree mechanism as refined by Honaker (2015), and the latter explicitly optimizing factorization under single participation. These two works yield two natural baselines:
Kairouz et al. (2021) explores 'tree restarts' (generalized as our notion of "stamps', s, in Section 5) and the so-called 'tre--completion trick' for the Honaker siimator-from-boee variant of the binary tree method for computing differentially private prefix sums; the matrix-factorization perspective on this estimator allows us to implement slightly optimized versions of these methods; see Appendices D.3 and D.4.
Denisov et al. (2022) computes optimal factorizations of various optimization-reltted ma- trices, though only for single epoch. For these matrices, leverage the results in Sec- tion to directly compute the sensitivity of the encoder matrices for multiple participations.
These papers be combined in other ways as well; e.g., the results of Denisov et al. (2022) show that the 'fully efficient estimator' of Honaker (2015) may be used as drop-in replacement for the estimator from below in Kairouz et al. (2021). We focus the two mechanisms specified above as the natural baselines for the present work.
D.2 PRIVACY ACCOUNTING
The matrix mechanism Eq. (1) conceptually adds isotropic Gaussian noise in some encoded space. In our case, we encode matrix of gradients (clipped to & norm () computed over the course of training. denoted by G. with the matrix C, and add Gaussian noise each entry in the matrix CG. Under the assumption that the matrix factorization has been appropriately scaled so C has sensitivity 1, this Gaussian noise will have standard deviation a Ç= in each coordinate, where is the 'noise multiplier' parameter determining the privacy level of the mechanism (see Table 3 for example).
Privacy costs are computed as a single application of the Gaussian mechanism to GC using the PLDAccountant provided by the Google DP Library". We also use this accountant to analyze DP-(S)GD baselines (which require more complex accounting), yielding a small improvements in over the Renyi-DP accounting used in prior works.
D.3 IMPROVEMENTS TO" 'TREE COMPLETION BY REMOVING NOISE FROM VIRTUAL STEPS
The "tree completion" trick of Kairouz et al. (2021) is used on the last step of any restart (in ours, stamp) reduce the noise added this step. This is achieved by adding virtual steps (with inputs) until the final step of that level in the tree, because this noise will be the lowest in that level. In this section, we show how further improve on this trick and that our matrix mechanisms make analyzing such tricks casier. Our implementations of the binary-trec baslines Honaker (2015); Kairouz, et al. (2021) utilize these improvements.
For the online Honaker estimate, Honaker (2015) obtain a DP estimate for the release node i E [n]] (representing the prefix sum until i) but summing the corresponding subtrees prior to this node. These are exactly the subtrees corresponding to the binary representation of this node (Honaker, 2015). Then, the variance required to release node i, with subtrees of height 0, I,.... 4 1, is
4
1/23
0² 2. 21-12-HH o²
where
cj =
Σ (1/21)
Notice that reaching a new height in the tree decreases the variance needed. In Kairouz et al. (2021) and just before terminating on some non-power-of step n' < n, they run n' virtual steps
phttps://gf thub. httpggttt.......o.oooeeee hamm/goolle//ii aferreettitiiiirrrreererriiiilla
fferential
15

---

Under review as a conference paper at ICLR 2023
on zero gradients. This enables their mechanism use the minimal noise for the power-of-two-ster for the final real step.
However, notice that in both these cases, the methods assume that these virtual steps must be priva- tized. Indeed, they do not need to be because we know apriori that these steps are virtual, i... not corresponding to real gradients. Thus, in our methods we account for this in our mechanism and reduce the noise of the final step accordingly. Importantly, this can be computed without altering the asymptotic runtime and storage complexity of the algorithm: on the last step, the contributions of the virtual steps to the power-of-two noise can be calculated using, e.g., a second binary tree, and removed. This leads significant benefit in the loss as we observed in Table I in Appendix D.5.
We believe this oversight of prior works showcases the power of our matrix mechanism approach. Indeed, let Crree be matrix representing the (complete) binary tree used in the mechanisms of Honaker (2015); Kairouz al. (2021) with 2 [00g2(n) leaves; for the sake of concreteness, as- sume this is the matrix constructed in Appendix C of Denisov et al. (2022). Let BHon represent the in our language, the decoder used by (Kairouz al., 2021).
Honaker
The tree completion trick of (Kairouz et al., 2016) can be understood as follows. The matrix Biion Cuee is of size 2 [n)] x (0)) In the case that n is not a power of two, the penulti- mate rows and columns of this matrix will go unused. However, for this factorization, the variance added by On the final row will be quite small, due to the binary tree's redundancy in encoding estimates of this sum. The matrix we wish to factorize is a prefix-sum matrix S of size n x n;; this matrix can be expressed as any one of family of transformations of the (potentially larger) product B Boon Cuee:
S P,BHon Crree E,
where E embeds a n-dimensional vector into 2[))g2()]] dimensions by padding with zeros, and P; projects back down to n dimensions in a similarly axis-aligned way, taking the first n - rows of
its right-hand matrix argument, and only one, but any of the jth rows for n S j S 2 20oog200], To minimize the Frobenius norm of the constructed decoder in the factorization of S, we may simply pick the row with the lowest le norm; in the case BHon. this is the final row.
One more optimization becomes clear when tree completion is formulated in this manner. Similar to our optimal decoder of Section 4, any decoder can be used without changing the sensitivity of the encoder. Noting that nonzero entries in the decoder increase zero out the columns of the decoder corresponding to these virtual steps- this decreases the loss, preserves the same error in the DP estimate of the prefix sum (the inputs are O), and maintains the same DP guarantee. In other words, we need not account for the noise, or the error it introduces, of virtual steps. We now provide
loss of Eq. (4),
simply
rigorous explanation.
The image of Ciee E can be contained in an axis-aligned subspace; effectively, the subspace corre- sponding elements that may be nonzero in the binary tree when run for n steps. In other words, the columns of the decoder corresponding to rows of the encoder that are removed via the projection need not be included: because the input is not processed. Therefore, denoting the projection onto this subspace by II, we may write:
S = B.o = (P,BHonLI) (I.CuceE)
further reducing the variance of the decoder (without increasing the sensitivity of the encoder) in this incomplete binary tree case.
In our implementations of the online Honaker mechanism, we freely use these tricks, in addition to exact calculations of the sensitivity of the mechanism enabled by noting that the encoder is all- nonnegative and the observations of Section 2, leading to some improvements in these mechanisms over those in the existing literature. No changes to accounting are required, as privacy is inherited from the matrix mechanism perspective.
16

---

Under review as a conference paper at ICLR 2023
D.4 STAMPING: REPEATED MECHANISMS IN THE MATRIX-FACTORIZAN SETTING
In stamping, we define a new encoder matrix as the Kronecker producct of some given encoder C with an X s identity matrix I, creating new sn-dimensional linear DP query mechanism. Assuming C is of shape n X n, the resulting encoder is an sn x sn block-diagonal encoder matrix, formed by 'repeating' the matrix C along the diagonal.
Kairouz et al. (2021) explored 'restarting" their binary-tree based prefix sum estimation mechanism, treating the number of restarts used as a hyperparameter, and treating the result of a 'completed' application of the binary tree as fixed. For linear operators A with constant columns below the diagonal, this approach may be used to construct a new factorization from existing one. This constant-columns property, or a block-based variant thereof, is required to simply treat the output from a 'completed' application of the existing mechanism as fixed; for general matrix A, there is no clear prefix property which can be leveraged for this purpose.
Taking the matrix view, one may construct a similar encoder/decoder pair for the prefix- matrix by reusing the initial decoder B on the block-diagone and fixing the columns to simply repeat the final row of this decoder below the block-diagonal; notice that the constant-column property of the prefix sum matrix guarantees that this construction appropriately factorizes A. The noise that the matrix mechanism thus constructed adds can implemented as a 'restarted" tree mechanism; however, since compute sensitivities exactly for decoders of this structure in Section 2, the privacy properties of these mechanisms we construct to replicate the 'restarts' of (Kairouz et al., 2021) may not be identical to those presented there, where accounting is performed by composition.
perspective additionally allows one to apply the 'stamping' construction to any linear operator A (e.g. the momentum matrix), where reuse of fixed previous outputs is not possible. A 'stamped' factorization of any A may be obtained, for example, by matrix pseu- doinversion: letting B A (C @ I) This defines legitimate factorization of any A requiring only suitable don-degenyy assumptions on C, and indeed represents the optimal decoder for the stamped encoder.
The
The pseudoinverse-basee construction can, even in the prefix-sum case, quite different from a construction designed to replicate 'restarted' mechanisms. For example, if C is matrix represen- tation of the binary-tree encoder and = 1, then the resulting decoder matrix represents the full, rather than online, Honaker decoder (Honaker, 2015); the validity of this mechanism in the adaptive streaming setting was only shown quite recently by Denisov et al. (2022).
For comparability with existing literature (and preserve potential for efficient implementa- tion). however, all of the tree-based mechanisms we explore in the main body have decoders which replicate the setting of composition". All other stamped mechanisms used the optimal decoder.
Optimizing over 8 Considering instantiation enables us to directly analyze and minimize (over s) the stamped mechanism's 's multi-epoch loss Eq. (4) without running compute intensive ML ex- periments. Indeed, we observe in Table 1 of Appendix D.5 that for mechanisms which were not explicitly optimized for the (k:, papttiiiiattoon setting, there exist stamped mechanisms (s >> 1) with much lower loss that correspondingly led to much more performant ML models (e.g.. Figures and 8 of Appendix D).
Interestingly, with our capacity to measure mechanisms at a single shot in the multi-epoch setting, see a similar trend as was observed for restarts in Kairouz al. (2021): that 'stamped" mecha- nisms have lower total loss than their non-stamped full-tree counterparts in the 20-epoch, 100 steps / epoch setting (see Table 1); training performance of these 'stamped' mechanisms on CIFARIO 10 can be found in Fig. 7. However, there is significant improvement in our approach in that we can now directly tune this hyperparameter without the need to actually run ML training. This lets us reduce computation by only analyzing the loss of the generated matrices and then running the mechanism with the lowest loss.
"We show how the optimal binary-tree decoder differs from the online, composition hased decoder in Fig. 6
17

---

Under review as a conference paper at ICLR 2023
Per-Rerate 100)
goometry
0.20
0.00
MrDee 500 ape-4 38
MFDe- 10 1050000 eps-4
Percoand unttace Eneale
0.7
Per coreoddd vartannce 820ad0
0.00
MP0x-20 1000-200m--00000 20000000000 4pam4433
0.07
0.66
0.00
0.44
Mfib-20,nn-200 2000), 30
0.03
0.22
FFTia-400sss opane 4.30
Honskerje-2200xt apoind 30
0.52
Beration
Periterate D2- geometry
variance
geometry
0.244
Perround venance Exeale
0.12
Per connd varfance Faratt
0.10
0.28
0.66
Honaaerije 2000ec ape--d Honakeripww0000 spumd.33
2970002000120 opum4.35
2000
Figure 4: Per-iterate variance for prefix-sum factorizations. All mechanisms above yield the same privacy 8) (4.38, 10 5) in the (ks b) (20, 100) setting). but have different total variances (the integral of the curves above).
D.5 FACTORIZATION LOSSES AND PER-ITERATE VARIANCE
As first measure of the privacy-utility tradeoff, compare the losses of each mechanism from Eq. (4) for factorizations of the matrices under consideration.
We compare measured losses of several factorizations of the prefix-sum matrix for the (k:, b) (20, 100) setting of the CIFAR experiments in Table 1. We plot the per-iterate variance of the mech- anisms Fig. 1, along with several variations, in Fig. distribution of factorizations of the momentum and cooldown matrix (described in Section 5) at fixed variance level, and with various privacies, computed for the (ks b) (6, 342) participation setting.
Fig. 5, we plot the per-iterate variance
Figs. and both demonstrate the effect of (k, particiiippaso on the optimization problem. Partic- ularly interesting to consider are the aptimally-factorizee matrices; in both cases, the epoch structure clearly visible the manner which the mechanisms distribute variance. see also the fect of 'stamps' in the variance distribution, effectively proxy for the epoch structure directly accounted for by the optimal mechanisms.
18

---

Under review as a conference paper at ICLR 2023
(k, b) (20. 100)
Mechanism
Computation for Steps, d
Prefix Sum Loss
(Online) Honaker(n 2000)
5.8e6
Ooglog)) Noise Generation
(Online) Honaker(n 1000)x2
3.3e6
(Online) Ho 400)x5
e.
(Online) Honaker(n 200)x10
2.0e6
(Online) Honaker(n = 100)X20
2.1c6
Optimal Decoder Honaker(n 2000)
2.4c6
(n²)) Noise Generation
Optimal Decoder (onaker(n = 1000)x2
1.6e6
Optimal Decoder Honaker(n 400)x5
1.2e6
Optimal Decoder Honaker(n 200)x10
1.4e6
Optimal Decoder Honaker(n 100)x20
1.8e6
On Optimization
MF(k 20, n 2000)
6.5e5
( Noise Generation
MF(K = 10, = 1000)x2
8.8e5
MF(A n1 500)x4
1.2c6
MF(k = 1, = 100)x20
2.5e6
MF(K 1, 2000)
1.6e6
MF(k 1, 1000)x2
1.37e6
MF(A: I, 500)x4
1.4e6
МF(A = 1, 400)x5
1.5e6
MF(A = 1, 72 200)x10
1.8c6
MF(K 1, x00)x20 X20
2.5c6
FFT 2000)
2.3e6
Onnlogn) Noise Generation
FFT(n = 1000) X2
1.8e6
FFT 400)x5
1.6e6
FF = 200)x10
1.9e6
FF 100)x20
2.5e6
FFT Optimal Decoder(n 2000)
2.2e6
O( n) Noise Generation
FFT
Optimal Decoder(n = 1000)x2
1.5c6
FFT
Optimal Decoder(n 400)x5
1.1e6
FFT
Optimal Decoder(n = 200)x10
1.2c6
FFT
Optimal Dеcoder(1 = 100)x20
1.7e6
Table 1: Loss for various prefix-sum factorizations, computed via Eq. (4), in multiple-participation setting for 20 epochs with 100 steps per epoch. Lowest-loss mechanism in each class bolded. Note that "(Online) Honaker' corresponds the restarted decoder. By evaluating the dual problem (Sec- tion 3), 6.53e5 represents a lower bound on the optimal loss; the optimal matrix factorization is within 0.2% this optimal value. Though up to On² noise generation can be tolerated practically for large ML training runs, we find that the stamped FFT optimal decoder obtains the best privacy- utility tradeoffs while requiring only O(n log (n)) time. Sensitivity is calculated exhaustively with contributions constrained +1 for all matrices except FFT ones, where sensitivity is calculated using Theorem 1.
19

---

Under review as a conference paper at ICLR 2023
Per-round iterate variance for different mechanisms All mechanisms scaled to total variance 13.28, (k, b)=(6, 342)
M Mhrr
0.10
Per-round variance in iterate
0.08
0.06
0.04
0.02
MF(k=6.n=2052), eps=7.01
MF(k=1.n=2048) eps-9.81
Honaker(n=2048) eps-22.85
0.00
500
1000
1500
2000
Iteration
Figure 5: Per-iterate variance for momentum + cooldown matrix factorizations. Privacy measured in the (k, b) = (6,342) setting.
CIFAR10 Accuracy
Test accuracy
0.60
0.55
0.50
Mechanism
opttacoserronakkrrr--00ss
Honakar(n-200j-33
M=(k=1,n=20000)
MFlk-200n=20000
epsilon
Figure 6: Comparing the optimal decoder, i.c., OptDecoderHonnaer,, with the standard stamping decoder (including fixing the output of each block), i.e., Online Honaker, with the optimal factor- ization.
E DETAILS AND ADDITIONAL EXPERIMENTS FOR CIFAR10.
train image-classfficttion models using the CIFARIO dataset as hosted in censorflow dasssrfo.odddtsttts.....o containing 50,000 training and 10,000 test examples. We evalu- ate and compute test accuracies on the entire test set, following the open-sourced code of Kairouz et al. (2021). We reuse the network architecture, dataset processing and initialization strategies presented in Kairouz et al. (2021); in particular, the architecture we use can found their Table 2 (b).
20

---

Under review as a conference paper at ICLR 2023
Optimization setup and hyperparameters We train all mechanisms for 20 epochs with batch size of 500, yielding 100 steps per epoch and 2000 total. After performing some small initial grid searches, settled on using linear learning rate cooldown to 0.05 the initial learning rate over the last 500 steps of training. We found this consistently improved utility for all mechanisms and privacy levels.
As mentioned in Section 5, for this 20-epoch training setup, we only compare factorizations of the prefix-sum matrix, and do not include any factorizations of matrices which incorporate momentum of learning rate cooldown directly in the mechanism itself (Denisov et al., 2022). We sweep over learning rates of values (1 x 10', 2 10', 10') for in {-2, -1); for all mechanisms and noise levels, optimal values were in the interior of this sweep. We sweep over momentum values of 0, 0.85, 0.9, 0.95 though find nonzero momentum works best for all matrix mechanisms, and no momentum works best for DP-SGD at our scale as found previously by Kairouz et al. (2021).
For Honaker and FFT-based factorizations, there no known a-priori way to choose the optimal number of for given (k, b) setting. Therefore we treat the value as a hyperparameter, and sweep across it, for 8 E 21, 5, 10, 20). As can seen Table I, the optimal 8 for both of these factor- izations was in the interior of this sweep. As shown, e-g., in Fig. 7, the training-time performance of these mechanisms matched the expected order for computed loss. This value s represents an extra hyperarameter which must be set for the Honaker and FFT mechanisms; to the best of our knowl- edge, computing the loss for various instantiations of these mechanisms via Eq. (4) represents the only known method for setting this parameter other than simply training models.
We also apply our sensitivity analysis of Section 2 to the matrices Denisov et al. (2022) which optimized for k 1. In doing so, we can also optimize the number of stamps which do. We report the best results as identified by the losses in Table 1.
CIFAR10 Privacy / Accuracy
0.70
0.65
Test accuracy
Mochanism
HonakerJn= 200)x200
Honaker/n- 2000)
Honakor/n-11000
0.45
Honaberine 1000)s2
Honaker::=4400)x5
0.40
2
10
12
16
18
opsilon
Figure 7: DP-FTRLL-Hnaker baseline ablation with respect to number of 'stamps' s.
21

---

Under review as a conference paper at ICLR 2023
CIFARIO Privacy Accuracy
0.65
Test Test accuracy
0 0.60
0.55
MF(K-S,n=5000x4
MFlk-Inn1100:200
1F1k=100n=1000)p
MF(k=20.n=2000)
10
12
16
18
apsilon
Figure 8: Ablation prefix-sum factorizations, optimized for different number of epochs, and 'stamped" appropriate. Performance improves the geometry used for computing the factoriza- tion approaches that used for training.
CIFAR10 Privacy versus Accuracy Tradcoff
Nonprivate Baseline
lest Accuracy
Mechanism
Honskerr'n= (K))rouz'2))
M0Cc=20.n= 2003l4 (Ouns)
DP 5GD Amplficaaon
Opt
LP(e-1a-100 (Denisov et all
MFik-1 1- 1-000 (Ours)
50
Privacy Buciget,
Figure 9: Our optimal multi-epoch matrix and FFT-based mechanisms outperform all others, including DP-SGD with amplification, as low as E 2 4. Using our sensitivity calculation of Theorem 2.1 and stamping (Section 5), we optimize single pass (k 1) matrix of Denisov et al. (2022) but apply it here with > pass. We use an online Honaker- of Kairouz al. (2021) except for a significant improvement to tree-completion in Appendix D.3. Models trained for 20 epochs on CIFAR10 with a batch size of 500. We repeat each setting 12 times and show 95% bootstrapped confidence intervals. Empirical setup Section 5.1.
decoder equivalent to that
22

---

Under review as a conference paper at ICLR 2023
F ADDITIONAL STACKOVERFLOW DETAILS
F.1 PRIVACY AND LANGUAGE MODELLING
Language models trained on user data are an important real-world application of DP training. as these models can memorize their training data if appropriate mitigations not applied (Carlini et al., 2019; Song & Shmatikov, 2019; Carlini et al., 2021). Since one user might contribute 1000s of tokens (training examples) tees (McMahan et al., 2018). Building on the approach of Kairouz et al. (2021), Google recently announced the first-ever launch of language model trained on user data with formal user-level DP guarantee (p = 0.81 zCDP), further demonstrating the importance of this application (McMahan & Thakurta, 2022).
dataset, it is particularly important consider user-level guaran-
The StackOverflow next-word prediction task, introduced in (Reddi et al., 2020), has become benchmark problem for DP training, and our experimental setup here fixes the same model and adapts hyperparmaeters from previous work including Kairouz et al. (2021); Denisov et al. (2022).
F.2 HYPERPARAMETER TUNING AND INITIAL EXPERIMENTS
All rums server momentum 0.95 and learning-rate rate cooldown schedule for the last 25% of rounds. Zeroing outlier updates and using 1000 clients/round (6 epoch runs) allows the use of the higher server learning rates. MF1,1e replicates the result of single-epoch training from Denisov et al. (2022); note that with 167 clients/round and this mechanism, the higher learning rate does not appear to help. Fig. 10 gives preliminary experimental results which informed the main experiments used in the paper. Note that the y-axis range (Test set accuracy) is highly compressed, and so the primary point of comparison is on epsilons. For example, Denisov et al. (2022) shows that cross-run variation of 0.002 or more is typical.
The 6 horizontal lines give test-set accuracy for various non-private training mechanisms. The "Un- noised MF" runs correspond to the same code path used for privacy, but without any noise addition. In particular, these use momentum with learning rate cooldown; the other unnoised runs use stan- dard FL implementation with momentum but a fixed learning rate schedule; "cpr=167" corresponds to one epoch of training (167 clients/round), and "cpr=50" is clients/rounds (only about 1/3 of an epoch). This last non-privvv non-private baseline uses the best hyperparameters for FedAvgM from Reddi et al. (2020).
The two "Unnoised MF" runs with accuracies between 0.246 and 0.248 are functionally identical, and the line near 0.248 accuracy is the same except it does not use learning-rate cooldown. Thus, for the given learning rates, we the higher-epsilon private runs adding sufficiently small noise that the accuracy is essentially equivalent to unnoised baselines with the same hyperparameters. However, using larger learning rates can achieve accuracy over 25%, even with privacy as in the case of the MF-6-6 run, hence motivating the inclusion of larger learning rates in the main experiments.
The MF (Matrix Factorization) runs with "prefix" in the name correspond to computing an optimal factorization of the prefix-sum matrix (lower triangular matrix of ones) and then applying momen- tum (and possibly learning rate cooldown) as post-processing. The other MF runs directly factor the momentum or momentum+cooldown matrix.
F.3 IMPACT OF ZEROING-OUT LARGE-NORM UPDATES
We observed that zeroing out updates with an lo norm greater than 100ç = 100 greatly stabilized training, allowing learning rates, particularly for MF6, 6e. We conducted ablation experiments where turned off this zeroing, which produced large fraction of unconverged runs as detailed in Table 2. The number of updates zeroed increases significantly with larger amounts of noise and larger learning rates, as shown in Fig. 11.
23

---

Under review as a conference paper at ICLR 2023
Unnoised MFG, (Ours) s1.0,c100
Mechanism
MF6. 62 (Ours) 50.1.100
50,5,c10
Honaber, (Kairou/21) 5,c10
Unnolsed, fixed cpr-167 s3.0.c0.5
MF1 1a (Denso22) prefis so 5.c10
MF1. (Denisor s0.5cc.0
prefix
HF1. 6e (Ours) 50 5.1,0
MFG, 62 (Ours) 51 61.0,c100 scheduue
0.250
conldown
fixed
0.240
cpr-167
Unnoised MF11 le prefix 20.5.c1.0
5,c10
0.244
Unnoised, fixed cpr=50 c00
0.242
5
10
15 epsilon
20
25
30
Figure 10: Preliminary experimental results and non-private (unnoised) baselines. The notation
8X, 8X,cY eY indicates a server learning rate and client learning rate V
Zeroing multiplier
Zeroing multiplier
1000
1000
Updates zeroed 1000)
800
Mechanism
MF6, 6e (Ours)
600
MF1, (Ours)
Honaker, (Kairouz
server Ir
400
0.25
0.5
200
1.0
Round number
Round number
Figure 11: Number of large-magnitude updates zeroed per training round.
Unconverged runs with
Mechanism
Zeroing
No Zeroing
DP-SGDM,66 6e, 7), 0.5
0 of 3
of 2
DP-SGDM,6e. 6e, 77. 0.5 0 of 3
0 of 2
MF6, 6e, 1/s 0.5
0f
3 of 4
6F6,6e, 1.0
of
of
Table 2: Number of divergent training runs with and without zeroing of user updates with f norm greater than 100; 7/ gives the server learning rate.
24

---

Under review as a conference paper at ICLR 2023
StackOverflow Privacy
Zoomeed accuracy regime
0.26
0.25
0.24
Test set accuracy
set accuracy
Mec Rechanism
6
DR GDM, 2052e
1.0
MF6,
MF1, (Durs)
0.25
MF1, (Danisov
0.235
DP SGDM, 6e
5.0
12.5
20.0
12.5 15.0 10
Figure 12: Complete data used Fig. showing results for server learning rates 7e 0.5 and 1.0, as well as 0.25 when ==2. All algorithms use momentum 0.95 and a client learning rate of 1.0. For the and epoch runs, we observe MF generally tolerates larger learning rates, though lower learning rates perform better for all algorithms at s=
F.4 COMPLETE RESULTS
In this section we give additional details on our main grid of experiments. Fig. 12 uses the same data as Fig. but shows results for each learning rate individually. Tables and give the mean, minimum, maximum, and standard deviation of test-set accuracy corresponding to Fig. 12, well as the number of replicated experiments ('count').
Table 3 gives the noise multipliers to achieve our various privacy targets Due to change in the accountant used, we have slightly different targets around 8.8 for the different methods. Note the noise multipliers here are incomparable between the MF and (S)GD mechanisms in terms of the total noise introduced. For matrix factorization, we sample
(O, (²2²) for noise multiplier 2; this noise is applied after mapping the raw gradients/updates through the linear map C which normalized so the total sensitivity is Ç. For the (S)GD mechanisms, we add noise (0, (²2²) independently each model update. In all cases, noise is added to the of per-user updates, so the effective noise in the average update scales down with the number clients per round.
Noise multiplier z
target
MF
DP-SGD (6e)
GD (2052e)
17.648
0.341
0.402
15.518
8.841
0.600
8.824
0.491
27.493
2.000
2.231
0.757
106.023
Table 3: Noise multiplier parameters for the StackOverflow experiments to achieve various as at
5 10-6 Privacy computed using the PLD accountant, Appendix D.2.
25

---

Under review as a conference paper at ICLR 2023
Test accuracy
clients/round
1/a
mcan
min
max
count
1000
2.00
0.25
0.22654
0.00009
0.22648
0.22660
0.50
0.22592
0.00013
0.22581
0.22606
1.00
0.21869
0.21869
0.21869
8.82
0.25
0.23154
0.00015
0.23143
0.23164
2
0.50
0.23447
0.00033
0.23419
0.23495
4
1.00
0.23135
0.00041
0,23106
0,23164
17.65
0.25
0.23290
0.00002
0.23289
0.23291
2
0.50
0.23728
0.00014
0.23710
0.23741
4
1,00
0.23571
0.00019
0.23558
0.23585
342477
2.00
0.50
0.24074
0.24074
0.24074
1.00
0.24056
0.00097
0,23886
0,24125
8.82
0,50
0.24640
0.00011
0.24632
0.24647
2
1.00
0.25279
0.00019
0.25261
0.25306
4
17.65
0.50
0.24686
0.00025
0.24668
0.24704
1.00
0.25370
0.00039
0,25312
0.25394
Table 4: Test set accuracy statistics for DP-SGDM, 6e (1000 clients/round) and DP-GDM,2052e (342,477 clients/round)) Accuracy for DP-GDM, 2052e was estimated with 1000 clients/round with an appropriately scaled noise multiplier. The count columns gives the number of repeated trials of the given configuration, with 77, indicating the server learning rate.
Test set accuracy
Y/+
std
min
Honaker, 6e (Kairouz')l 21)
2.00
0.25
0.20951
0.00134
0.20857
0.21046
2
0.50
0.19535
0.001 14
0.19429
0.19655
0.00011
0.00011
0.00011
8.84
0,50
0.23952
0.00101
0.23881
0.24023
1,00
0,23799
0.00212
0.23649
0,23949
2
17.65
0.50
0.24422
0.00037
0.24383
0.24456
1.00
0.24675
0.00128
0.24540
0.24810
MF1, le (Denisov's 22)
2.00
0.25
0.19674
0.00057
0.19633
0.19715
0.50
0.00993
0.00108
0.00017
0.00169
2
8.84
0.25
0,23500
0.00009
0.23493
0,23506
2
0.50
0.24105
0.00083
0.24019
0.24190
4
1.00
0.23909
0.00196
0.23767
0.24132
17.65
0.25
0.23576
0.00019
0.23562
0.23590
0.50
0.24503
0.00056
0.24408
0.24565
6
1.00
0.24522
0.00102
0.24424
0.24628
3
MF1, 6e (Ours)
2.00
0.25
0.22953
0.00046
0,22921
0.22985
0.50
0.22324
0.00017
0,22308
0.22341
1.00
0.00010
0.00010
0.00010
8.84
0.50
0,24516
0.24516
0,24516
1.00
0.24676
0.00044
0.24628
0.24714
17.65
0.50
0.24628
0,24628
0.24628
1.00
0.25194
0.00085
0.25124
0.25288
MF6, 6c (Ours)
2.00
0.25
0.22978
0.00038
0.22939
0.23014
0.50
0.23237
0.00078
0.23147
0.23286
3
1.00
0.22413
0.00055
0.22365
0.22472
8.84
0.24509
0.00010
0.24497
0.24515
1.00
0.24897
0.00081
0.24804
0.24955
17.65
0.50
0.24632
0.00015
0.24618
0.24648
3
1.00
0.25265
0.00025
0.25240
0.25291
Table 5: Test set accuracy for matrix-factorization based mechanisms. Note: Some epoch runs
were conducted with shuffling between epochs, and some were conducted using fixed order for all epochs (as required by our DP analysis). We saw no impact of reshuffling on the final test set accuracy, and include all runs in these results regardless of the shuffling setting.
26

---

Under review as a conference paper at ICLR 2023
A matrix for momentum 0.95 and Ir cooldown
X = C'C matrix
20.0
342
0.25
17.5
684
15.0
684
0.20
12.5
0.15
1026
10.0
0.10
1368
1368
0.05
1710
0.00
2052
2052
342
684
1026
1368
1710
2052
684
1026
1368
1710
2052
B matrix
matrix
0
18.39
0.2273
0.2000
15.00
684
684
0,1500
10.00
1026
0,1000
5.00
0,0500
1368
1368
0.00
0.0000
-4.56
0.0288
2052
2052
1026
1710
684
1026
1368
1710
2052
Figure 13: A detailed view of the matrices shown in Fig. 2.
F.5 OPTIMAL MATRIX MECHANISMS
G DISCUSSIONS AND CONCLUSIONS
Our work significantly improves the privacy-utility tradeoff's in DP ML. Indeed, our work outper- forms the state-of-the-art (and, DPSGD with amplification) by 2 5 percentage points across many privacy levels-and low that we compare our mechanisms with DPSGD on level-groume using well well-performing but not state-of-the-arn models and training protocols- e.gocols-e.g...... very large models, augmentations prior clip- ping (De et al., 2022), public data usage, and large batch sizes can all aid training. Many, if not all, of these techniques are applicable our setting and can thus be used with our mechanisms to realize additional absolute performance gains, again, likely beyond the performances achieved by DPSGD.
2 2-with practically implementable assumptions. We remark
The major limitation our approach Though our optimal FFT decoder bridges the gap between the mechanisms without optimizer costs and our optimal mechanism, it still leaves some room for improvement in the privacy-utility tradeoff. We believe this is important area for future work.
computation required to generate the optimal matrices.
H ANALYSIS FOR SECTION
H.1 FROM SCALAR TO VECTOR CONTRIBUTIONS
Theorem H.1. Let C E Bank which satisfies
[[Culla <
Vu (-1,1)*
27

---

Under review as a conference paper at ICLR 2023
and let G E RRxd such that each row [ir) [k] satisffes [[G[a]]l of the following conditions hold:
1. Suppose at least one
1. We have k = 1 or k parlicipations.
2. All the entries of CT C non-negative.
3. The rows of G are all co-linear. G(t.) = u, Gir us E {-1,1}, i> 1.
4. The rows of are all orthogonal, (G....) G1aaa = O, + J. jije [k].
Then,
CG F S
(10)
Furthermore, the following statements are also true without assuming conditions (1)-(3 above.
|CG|| (log k).
we replace the condition on G to Vi e [K], G.agl S 1, then |CG||| S 1.
Note Theorem H.1 generally applied to Cj.=). the sub-matrix of some C E g=x= formed by keeping only columns selected by particular participation pattern π.
Theorem H.1. Let = [c1 let we write F(tl for the (ih entry of G. It will also be useful to note
C2
Ck with each c; E IR" being a column vector. Also
||CG 1 tr (CGG(CC)) ) tr(CT CGG In the following prove each of the individual cases of Theorem H.1.
(11)
When = 2: For & 1, we have
|CG]| = ||c| l1
Σ I1.f
5 || l1
fu-cill: c1
max vE(#1)
An equivalent argument is used in Denisov et al. (2022, Thm. 3.1).
For
2, we have the following:
2
Σ Si. Eohun
CCG
Σ
|c 1
+ (291.1192.((r,,.)))) + ... (291
i=1
2
$
||c.112 + (21gp.n)1 19p.1 + + (21g
i=1
2
Σ
||:1|| 2 + ( + - ((e), c2)1 + .... (sf.n)) + + (ei, c2)l
(12)
1=1
||c,1| + ||ca 2 + 2| c2) max ((c) + c2)² (ci - -0,--,,)² c²,
|Cul 2 1,
max =
where Eq. (12) follows from the standard A.M. 2 G. M. inequality.
All the entries CT C are non-negative: Let X CTC and G GGT Observe G [-1, 1]. and using Eq. (11), when X is elementwise non-negative, ir (XG) is maximized when
G kxc üü by choosing 1* Hence,
||CG|| < Ir(C Cau |Ca/|p
||Cul] 2 ue(=1}
max
(13)
Eq. (13) completes the proof.
28

---

Under review as a conference paper at ICLR 2023
The rows of G are co-linear: By the convexity of |[CG Ip with respect the matrix G, may assume the rows of G are of lo norm 1. Under the colinearity assumption, this translates to
(r.:) u, [1.]]. with each u, {+1}. Let u [u ......., unl E {-1.1}². Then for the matrix
GG we have the following:
[G [6. (G.)) G(a)) u.u, (G( ((a))) u.uy
which implies
GG uu
(14)
Using Eq. (14) with Eq. (11), we have
|CG = tr(CG(CG))) = tr(CC Cuu T) ك max uf(
|Cul S 1.
The rows of G are all orthogonal This condition implies G GG
T is diagonal matrix with
diagonal entries in [0, IJ. and so Eq. (11) implies ||CG|| S tr(X). ) It thus sufficient show
tr(X)= S max tr(Xuu")
nE(-1,1)*
We give a construction for a u that shows this. Observe
k
tr (r(uuu] tr( +
u4
u X [i
[
b,
Observe we can choose =
1 and then = sign(b; since by depends only on C and the previously fixed Uj for j < i, ensuring the double sum on the right is non-negative, completing the proof.
|CG]| F (log k) without assuming conditions (1)-(4): We will prove this claim via proba- bilistic argument. First notice that due convexity, we have the following:
max |Cull <1 Wc {
Vx R |[xx| 1| S |1
(15)
We now observe the following for Normal distributions:
||CG|| Ez~
||G22|
[| 0 max iE[k]
[Gall log k:
O (log k).
(16)
The first inequality in Eq. (16) follows from Eq. (15), and the first equality in Eq. (16) follows from expectation of the maximum of Gaussian random variables.
Replacing the condition on G to Vi E [k]. Gralh < 1, then |[CG]/ S 1: First notice that since ||CG| / is convex function, the maximum happens at the extreme points of the constraint set G = {G Vi E [k)), GG.gg ll = 1}. We use Claim H.1 to identify the extreme points of G.
Claim H.1 (Theorem in Cao al. (2022)). The set of extreme points of the set of row- stochastic matrices are precisely the set of row permutation matrices, i.e., set of the matrices with entries {0, Exd and each row has exactly one non-zero entry.
Notice that the constraint on any matrix G E G is oblivious to the sign, meaning, we can flip the sign of any set of entries in G and the new matrix will still be in This along with Claim H.1 immediately implies that the set H {H E {-1, 0, 1] vi E [k], || llo H H = 1} the of extreme points of the set G. (If the set of extreme points of & is larger than A. then the signs of any such extreme point can be flipped to create new extreme point of row-stochastic matrices, which would violate Claim H.
It is not hard to observe that for any H E H. there exists an uh (+1* s.t. Since, [Culll2 < max Cull2 for any choice uH, and the fact that max || is reached
|CH]| P |Cu I|g-
uE{#1}+
G
one of the matrices in H. the claim in Theorem H.1 follows.
29

---

Under review as a conference paper at ICLR 2023
H.2 A COUNTEREXAMPEE FOR GENERAL C
Theorem H.1 indicates the possibility of the following conjecture being true, because of it being true
in many special cases: If max
||Cull2 S 1, then ||CG|| S for all G with row f--norm
uE{#1}
at most one. Unfortunately, we show that the conjecture is not true when k > 2, as shown by the following counterexample with n = and 2:
2
1
1
2
1
C
-1 and G
2
-1
244
v5
-1
2
1
2
Direct calculation shows max (1 |Culll = 1, but |[G]|| = VII x 1.049.
H.3 PROOF OF COROLLARY 2.1
Corollary 2.1 Restated. When per-step contributions bounded by Ç ( 1, for any participation pattern IT and dimensionality d 2 1, when C C 2 elementwise, we have
senspy it (C) sensø (C).
Proof. To see sensgg (C) 2 senssa (C), suppose u* = arg max |Cul22. and observe we can construct G such that ||CG|| = ||Cu" by taking rows G (u, .) R for i [n).
For the other direction, for each æ E II, we apply Theorem H.1 to the matrix C, Ctas) and observe C C 2 0 sufficient to imply C 20. O.
Note The condition CT 2 0 is sufficient but not in fact necessary for Corollary 2.1 to hold. In particular, for (k, b) paartiicipation 11, the sub-matrices C C for π E 11 "touch" only k entries of the n² 626² entries of C' C: the other entries of C C could fact be negative. However, did not need to use this observation for any of the matrices in our experiments.
H.4 PROOF OF THEOREM 2.1
Theorem 2.1 Restated. Let C E 12xx and take some participation pattern II, with k max |o| the maximum number of participations. With Cj.² representing to selecting the columns of the matrix C indexed by and ll:112 the spectral matrix norm, let X max Then
xell (/,))l
sens (C)&
S AVT.
Proof. By assumption we have ||u]| I Vh, and so
max |Cull2 < max max |[C|; T ll ||uI|2 S AvI. #ell ue
D
I ANALYSIS FOR SECTION 3
I.1 PROOF OF THEOREM 3.1
Theorem 3.1 Restated.
Let a finite D = /u be given, and assume that the vectors {u,) span R Assume that A is full-rank, and for E 12* define
H. = [u,,..., upg diag(v)1/2 Then, for Lagrange multipliers such that the U is full-rank, the Lagrange dual function g can be expressed in closed form in terms of the Lagrange multipliers:
U-H
g(v) inf L(X, v) 2r (U+))) XDPD
Σ Vu
(17)
uED
30

---

Under review as a conference paper at ICLR 2023
Proof. Since there is some finite set of vectors R" specifying D, the supremum in Eq. (5) may be reduced to a maximum over these elements.
Our problem then takes the form:
inf
tr(ATAX-)
PD
s.t.
u Xu I 1, VuED.
(18)
Recall that we have defined Hv jui...., un! (viagv)2,, and U = H,H, Now, note:
Σ Vn ( (v) H.H...
(19)
Introducing Lagrange multipliers Vu O, for the problem Eq. (18) form the Lagrangian for positive-definite X:
(A E Vn Xu
(20)
= (I(ATAX-1) AX +tr (E
-'v, Vu
(21)
= tr(A tr AX + (UX)
Σve Vu-
(22)
For fixed v, any finite minimizer of L for positive-definite X must correspond to zero of this Lagrangian's gradient. We then compute the gradient
0L - + 0X
(23)
U and A are full-rank by assumption; therefore Lemma I.2 is applicable, and Eq. (23) has a unique positive-definite zero (and indeed, the infimum in Eq. (18) becomes a minimum):
U (U A A
(24)
Note that Eq. (23) also immediately implies that if U is not full-rank, then there is no finite positive- definite minimizer of X. Letting g(v) minx L(X,, v) be the Lagrange dual function and plugging back into Eq. (22), we have
g(v)
min ( AX PD
to (UX)
Σ V
min tr (XU) + tr (UX) - Σ Vu
using Eq. (23)
min 2r (UX) Σ Vn
PD
u
2ir (UU- A AU A Σ
using Eq. (24)
u
= 2tr ((U*A - Σ Vn
1.1.1 PROOF OF COROLLARY 3.1
Corollary 3.1 Restated. In the same setup as Theorem 3.1, maximizzr of the dual v* must satisfy:
v' diagpart (HH (EZ.)ATAH.)') AH,.)*
(25)
Moreover, the optimal value of the problem defined in 6 is tr (v*).
31

---

Under review as a conference paper at ICLR 2023
Proof. As noted in the remark after Theorem 3.1, any optimal setting of the dual variables must be in the interior a neighborhood in which the representation Eq. (7) is valid. therefore permissible to differentiate this representation.
Diffcrentiating, we find:
@.r Ov, tr (TU*AT AU+) -t
(ATAU u
1
(U- (U A AT u
tr
2
tr (U A u.
2
1
(r (uTTU A
1
2 u, Xu,,
by defining X U AU (recalling the usage of the symbol X in Eq. (24)).
Therefore
0g(v) u Xu; - 1,
Ov:
and we have the stated expression for the gradient of the dual function.
Now, at maximizer of the dual function, this derivative must vanish. An equivalent condition
diagpart(H XH) I, and hence
tr (UX) = tr(H dia((v) " X) = ur(diag(v)) HHH))
XH)
Σ Vu-
(26)
so at the optimum v* in fact g(v*) En v*, u. establishing the second claim of our result.
Again using the observation that diagpart H XH,) = and so
diagpart(H,, XH,) diagpart(diag(v)H XH v.
Further, using the second claim of Corollary I.I, we can take
X X H. (HA AH.) H
and multiplying this by H. and H, on the left and right respectively yields H. H. (H.AAA H. HH VH,) $ and so we conclude for the optimal Lagrange multiplier v*,
v = diagpart ((H..A AHr))&)
(27)
1.2 LEMMAS AND COROLLARIFS
Lemma I.1. The set of positive-definite X such that sup u Xu < is bounded as subset of Raxa if and only if = (u) spans T
Proof. Suppose that D spans R" For PSD matrix, bound on the trace implies a bound on the elements; therefore it is sufficient to show that supneo u Xu S implics that the maximum eigenvalue of X is uniformly bounded for X PSD.
32

---

Under review as a conference paper at ICLR 2023
Take some set of vectors (u: )
D which span R". Fix some representation
ei
Oijug
Ujo
j
where is the ith standard basis vector. Take y of le norm I, and express:
y e
im1
Then for X satisfying our assumptions,
"
ly Xy| =
Σ :
wyse; Xej
=5 n² max
han
e Xe,
(28)
15tJ5n
Similarly,
le Xe,l =
onaga XuI
In² max 1Sk,/5
1n Xu:
nn²
max Isk,/5n
loa0,d (29)
k=t=
where the final inequality follows by the assumptions on X.
Now, since the & norm of y 1, the orthogonality of the e, imply that each [817 is most 1. Therefore:
y Xy
<n
max Istghiisn
lawajd
(30)
and we have sufficiency D spanning R.
For necessity, suppose D does not span R", Then there is some vector E span (2)+ of norm 1. Take any X such that supne u Xu S 1. Then, since y u 0 for all D. Y X + oy satisfies the same set of inequalities for any a..
Lemma L.2. Let U.V E ST Let ULUR a factorization of U such that UR VU, is PSD, and the following equation defines positive-defiitte matrix X:
U (Un.U.))
X
(31)
Then, this X solves the equation
XUX V or equivalently U U
Moreover, this positive-definite solution X is unique.
Proof. We will begin by showing that X as defined by Eq. (31) solves the equation XUX = V; then we will show that any two positive-defintte representations of the form Eq. (31) are in fact identical.
Notice that the representation fore U, = I = U Un, n. as implied by the Moore definition the Moore-Penrose pseudoin- verse. So:
Un implies that rank(U,,) 2 n and (un)(Un))))) 2 n. There-
33

---

Under review as a conference paper at ICLR 2023
XUX=XU;URT
-UUA(UURUU)) 'U') ULUR (UR())))))
=UA((URUU)) $ P (URVUZ)
We claim that (UnVU,)* +p PmU mu) PR(Ux) (UNVU,) = (URVU,) & In both cases, this can be seen by multiplying the left right appropriate by (UR)Uz) and noting P PR(UR) Un = UR. ULPPqut = Uz. Since all the terms here are symmetric, the appropriate equality follows by uniqueness of the symmetric matrix square root. Therefore:
XUX U =
The uniqueness of positive-defintt X solving XUX V follows from the uniqueness of the usual matrix square root. Indeed, assume positive-definite satisfies YUY V. Then:
(uV/YVV))) = U1/2VU1/22
Since the positive-definite square root is uniquely determined, Y Since U is invertible, Y uniquely determined as well, and we have =
/ is uniquely determined.
Corollary L1. Two particular instantiations of Lemma 1.2 are of interest. X the matrix geometric mean of U-1 and V (taking Ur UR R VU):
X U (U
(32)
and assuming the representation
H.H..
X H HH VH,) H
(33)
Proof. By cositive-definiteness of U and V, Eq. (32) is clearly positive definite; Eq. (33) may be seen to be positive definite via the SVD of the pseudoinverses involved. Symmetry again clear. Therefore both representations satisfy the assumptions of Lemma 1.2.
J ANALYSIS FOR SECTION 4
J.1 ADDITIONAL DETAILS
Defining the circulant matrix We consider the special case where A the prefix sum linear query matrix (loier-triangle matrix of ones). Then, define the corresponding circulant matrix
Up
U2n-1
01
V1
Up
02
A Acire
where
A [1..... 1. O.....O 0).
(34)
U2n-1
U2n-2
Vo_
is straightforward to verify ccire(in..)) A.
Defining the DFT
2n
-j2kka
Vk E [2n
v
DFT
v(a) exp
(35)
2n
34

---

Under review as a conference paper at ICLR 2023
Circulant matrices expressed using Fourier Transforms
Theorem J.1 (Adapted from Gray (2006)). Consider any circulant matrix Acire E RR2 Let F E
C2nx2n, where the k-th row of F is given by F(k: [ </n exp
325kk (-92kk a E (0.....22 2n 1}
2n
Then, Acire F EF, where E E C2nx22 is diagonal matrix with the diagonal being the DFT
(defined in Equation 35) of the first column of Acire. Here, the Hermimitian operation.
Privacy and utility guarantees In the following we provide the privacy guarantee and the main utiitty guarantee for the FFT mechanism defined in Algorithm 1.
Theorem J.2 (DP-Preeix Sum via FFT Privacy Guarantee). Algorithm is p-zCDP in the adaptive continuous release model.
Next, we analyze the utility of Algorithm I and show that it is nearly optimal in terms of the mean squared error (MSE) in the single-pass setting. First, we express the MSE Theorem J.3 below.
Theorem J.3 (DP-Prefix Sum via DFT Utility). The MSE achieved by Algorithm using the real and imaginary components of is
x² >
DFT 2
E MSE]
2pm
In the following, we will have an explict expression for ||v Finally, we will argue that Theorem J.3 is nearly optimal.
||
in terms of the problem parameters.
Corollary J.1. The expected mean squared error (MSE) is given by the following:
2
x²
E MSE)]
Σ
2pn2
T(a 1)
a=0
sin
2n
Near-optimal utility Here, show that Theorem J.3 is near-optimal in utility for the sintte-paticipaatio setting. To do this, we compare with a lower bound on the ex- pected MSE of any factorization-basedd mechanism from Henzinger al. (2022, Theorem 2):
2 + In (2ntt)++ lm(2n+1) 2
We find that the though our analytical upper bound in Corol- lary J.1 is 6x worse than the lower bound, the empirical noise added in Algorithm closely tracks the lower bound to within factor of becuse it only adds the real part of the noise. Results in Figure 14 of Appendix J.1.
2pm
2n
Showing near-optimal utility via MSE experiments
60
Analytic-OP-FFT Empirical-DP-FIT
Henzinger et al. 2022
30
2000
4000
6000
8000
10000
Figure 14: Algorithm 1 achieves near-optimal utility as measured by the analytic lower bound from Henzinger et al. (2022, Theorem 2).
J.2 PROOF OF THEOREM J.2
Theorem J.2 Restated. Algorithm is p-zCDP in the adaptive continuous release model.
35

---

Under review as a conference paper at ICLR 2023
Proof. First, consider the non-adaptive setting and the following mechanism, with parameters as defined in Algorithm 1,
Σ (Fxext + 12),
n2 |vDFT 1|2
(VE w)
where 2
(36)
Anp
-2CDP. To see this, we proceed by bounding pi for each coor- dinate [2m] defined in Equation 36. For brevity, let b Fxext- Consider two neighboring data
We claim that this satisfies
sets g and g', correspondingly, (b, Xex) and xexe). Then,
b' loc = [Xxext Xlx /2n
(37)
We will now prove zCDP guarantee independently for each of the 2n coordinates and then use standard zCDP composition (Bun Steinke, 2016). For any coordinate E {O...., 2n 1}.
1f Then by
adding noise composition, we have that
Neomplex (0, to b[i] satisfies pi-zCDP with P; ing
[]]
2n
k²
2n-1
122 D
(pi)
([]DFT(3])
(38)
4no
4no²
OFT
Therefore, setting o²
satisfies non-adaptive p-zCDP. Using the same o, prove the We have the following from Equation 36.
Anp
adaptive part using the same σ.
F (EFxett x)] F' V VEFxxt
1 V =
F VE
VIF +
N2 [|
Amp
(39)
Since, in Equation 39 spherical Gaussian, and the original query matrix A is lower triangular, by Theorem 2.1 in Denisov et al. (2022), the adaptive privacy guarantee follows.
J.3 PROOF OF THEOREM J.3
Theorem J.3 Restated. The MSE achieved by Algorithm using the real and imaginary compo- nents of is
x²2
DFT
[SS]]
2pm2
Proof. The MSE is given by the following:
v DFT
n22 ||| |
EMSE]]
E || ...,,.......
tr ([E]: n, ml))
(40)
n
2n²p
2n22
In equation 40, Σ[: n,: n)] refers to the top-left n x n submatrix of Σ.
PROOF OF COROLLARY J.1
Corollary J.1 Restated. Under the same setting as Theorem J.3, the MSE for Algorithm is the following
x²
E
MSE]]
n +
2pn2
(2a+
sin
2n
36

---

Under review as a conference paper at ICLR 2023
Proof. Recall the definition of DFT from Equation 35 and of v in Equation 34. is immediate that DDF [0] = 7.. For any lo 7 O, we have,
DFT k]
exp
2n
exp
(-jmk)
(41)
1 exp
= j2mk
1 exp
jark
From Equation 41, we have that when ls > 0 is even, DFT [k] = 0. For odd, we have
2
V DFT
[p]]
(42)
jank
(sin(Tk/
sin(TT// (2n)
exp
Combining these, the term
|||
||,
is
||DFT
(43)
sin π (2a + (2n))
J.5 PROOF OF THEOREM 4.1
Theorem 4.1 Restated. Under k participation, Algorithm satisfies (k? p)-2CDP.
Proof. The proof goes exactly Theorem J.2, except equation 37 gets replaced by the following:
ks
| b' lx
| Xlx)
(44)
2
U
K TWO RELATED FFT MECHANISMS.
The FFT mechanism presented in Section 4 can be understood as an application of complex-valued
matrix mechanism factorizing the prefix-sum matrix
B PF V
C= VIFE,
where and are appropriate embedding and projection matrices, respectively embedding an n- dimensional vector in the first n components of g²" and projecting those same first n components back to R",, and following this application by 'chopping off" the imaginary part of the noise. The entries of Σ may be computed exactly; they contain no purely negative entries, specifying the principal branch of the square root resolves the implicit ambiguity in the formulation above. This branch corresponds as well to the implementation of the complex square root in major software frameworks (e.g., NumPy).
All these operations are linear; and since everything begins and ends in the real domain, this mech- anism can be expressed as a real-valued mechanism. Therefore identical codepaths can be used for implementing experiments with the FFT, though notably without some special implementation of the mechanism, realizing the potential computational savings will not be immediate. In this small section, we translate this complex-valuee valued mechanism into two real-valued mechanism which can be integrated with the code backing the rest of the paper. These mechanisms differ in their decoding matrix B, and thus achieve different levels of loss. Both have efficient implementations, though with asymptotics differing by logarithmic factor. We implement and experiment with both of these mechanisms in the main body.
These two mechanisms share encoding matrix:
CF F.C.
37

---

Under review as a conference paper at ICLR 2023
which is real-valued by Lemma K.1. Note that the sensitivity of CF is identical to that of C for any notion of sensitivity expressible as Definition due to the unitary of the Fourier transform. Since this matrix is of shape [2m, nl], there is choice in computing the decoder B such that BCF represents the prefix-sum matrix. The two decoders we present helow correspond to two subtly distinct mechanisms.
A real-valued version of the mechanism presented in Section 4. One natural translation of the analysis in Section 4 (indeed, real-valued version of the precise operation de- scribed in Algorithm 1) may be computed by inserting a Fourier transform to match the inverse transform in Cp:
Mechanism 1:
Bp BF,
Clearly Cr BC, and Bp real-valued by Lemma K.1.
Proposition K.1. For any D, the mechanism described in Section 4 is distributionally equivalent to an upplication of the real-valued matrix mechanism with the factorization (Br, Cr), ) and satisfies the same privacy guarantees.
Proof. To show this result, by noting that CF and C have the same sensitivity, it suffices to show that it suffices to show:
F v Ez] (for z a sample from an isotropic complex Gaussian) is distributionally equiva- lent to PF V EbFb for b sample from real (isotropic) Gaussian with the same variance.
This is consequence of the distributional invariance of the Gaussian under unitary transformations:
R Vz)] R[F Fzz]
= F" /EFR
(as F" VF is real)
F" VFFF,
where the variances are as desired.
Note that the efficiency of the mechanism described in Section 4 carries over immediately to this factorization (Br, Cr): indeed, the capacity to compute the noise Brb with complexity n log(n) may be reasoned to directly, in similar manner.
This mechanism is not, however, the optimal one for the encoder Cr, and this subtlety has difficult downstream effects in integrating with real-valued factorization codepaths (e.g., see the discussion in Appendix D.4). We proceed show that the optimal decoder be used directly, only moderate loss of efficiency with sufficiently careful implementation.
A real-valued optimal decoder with complexity log log2(n). As noted the liter- ature (e.g. Section 3 of Denisov al. (2022)), for fixed encoder, the optimal decoder may always be computed in terms of an appropriate pseudoinversion of the encoder. Therefore, we may compute the optimal decoder for the encoder Cp, defining:
Mechanism 2:
B SCt.
where the prefix-sum matrix. Since CF real, its pseudoinverse is well, and Bp is also real-valued. Since Br can have more variance than Br, all the utility analysis of the DFT mechanism Section carries through as an upper bound for this factorization. Privacy of this mechanism is ensured by the fact that this mechanism reuses teh encoder Cr. The major way in which these mechanisms operationally differ comes down to the cost of computing the noise vector B where b represents sample from isotropic Gaussian distribution. Though we do not know of a complexity result which matches the decoder Br, we will show that the complexity cost which must be paid only logarithmically higher.
38

---

Under review as a conference paper at ICLR 2023
Proposition K.2. The mapping b Bropi where b E R", may be evaluated in O(n (n)) time.
Proof. First, notice that the matrix CF is one-to-one; indeed, this is immediately implied by the factorization S = BpCF. By Theorem 1.2.1 (P6) of (Campbell & Meyer, 1979), any one-to-one matrix T admits the following representation for its pseudoinverse:
T = (T TTTT) TT T
We compute:
t (C)CF) CF
(F'VEFE) F' F'VEFE)
(F (F VEFE)
(PF' FF" VEFE
F F'VFFF)
(PF (F'VIFE)
Now, the matrix PF is Toeplitz, since F [ is circulant, and P. E combine to select out the top-left n x n square of F F. Notice that PF [ FE is not circulant, and cannot therefore be diagonalized by the n-dimensional Fourier transform.
The development of Section 4 yield the representation:
PF
which implies that matrix- vector products with the matrix S may computed in n log n time by the use of the FFT. Similarly, matrix-vector products with (F'VEEE) may be computed in log n time.
Therefore the computational cost computing the mapping b + SC b can be upper bounded by the maximum of log and the cost of computing the mapping + (PFF
The cost of computing this mapping is, in turn, bounded by the cost of inverting general (full- rank) Toeplitz system, since (PF*|E|FE) v may be alternatively characterized as the solution to the equation PF FxE The computational cost of solving such system is known to be (n)) see, e.g., (de Hoog, 1987).
Lemma K.1. For real-valued vector v, let & represent its discrete Fourier transform. If'v as no purely real, negative entries, then letting J denote the (pointiise) principal branch of the square root and the matrix representation of the Fourier transform, the matrix F /VF is real-valued.
Proof. Conjugate symmetry of the DFT states that for a j-dimensional real- vallev vector x, x[m] = *[j - -m], and that the converse also holds-that has this symmetry, x real-valued. This can be seen examining the action of conjugation of on the Fourier transform x.
Now, by the assumptions on v and the choice of the principal branch of the square root', v has this conjugate symmetry, so does VV. Therefore there some real-valued vector such that ý = Vv. The matrix F* /VF represents convolution with y in the standard basis, and hence is real-valued.
'These assumptions can be avoided, though the cost of taking care in choosing the square root of the negative elements of & preserve the appropriate symmetry.
39

---

Under review as a conference paper at ICLR 2023
Remark. Lemma K. can be understood statement about the solvability of certain repeated- convolution equation over real-valued functions (the equation g * = f). We suspect that this fact has been observed in the harmonic analysis literature as general property of all Fourier trans- forms; we could find no reference. The symmetries discussed above take a slightly different form in the continuous and noncompact case (IE, Fourier transform on real-valued function on R4) and the finite-dimensee Fourier transform here, so we choose to prove this statement in this limited setting.
40


Reviews:
[{"review_id": "wbYtOXNP64", "reviewer": "Reviewer_PQTm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of privately releasing prefix sums in the adaptive continual release model via matrix factorization techniques. Their main results are 1.extension of prior work which was limited to single participation to general participation patterns and 2. a more efficient method based on fast Fourier transform. The authors conduct extensive experiments which show promising results over prior approaches.\n", "summary_of_the_review": "I think the topic of the paper is timely and the authors make interesting contributions with promising empirical results. The downsides are missing/unclear details as well as lack of coherence among parts of the paper, like the one based on FFT.", "strength_and_weaknesses": "Strengths\n\n1. The prefix-sum view of SGD and using matrix factorization techniques to privately release these have been instrumental in improving the utility in private machine learning tasks, especially in large-scale practical settings. Therefore, the problem that the authors study is important and the improvements can have immediate real-world impact in how private machine learning models are being trained.\n\n2. The paper is mostly written-well; it gradually formulates the problem, and builds towards the key ideas and proposed approach. \n\n3. The experimental results showcase improvement over prior approaches; for example they get a 5\\% improvement over DP-SGD with privacy amplification with sub-sampling.\n\nWeakness\n\n1.  The section on FFT seems half baked and not so related with the overall picture. The main goal in the paper to demonstrate empirical improvement but it seems to be that empirical results presented in the main text don't even use this method; correct me if wrong.\n\n\n2. $(k,b)$ participation - I did not fully understand the choice and use of assumption that a point participates once every $b$ iterations. It seems to me that it is only used to argue that $|\\Pi|=b$; in that case, why not simply explicitly assume this? If not, where is the additional structure useful?\n\n3. At parts, I felt that some details are missing in order to completely understand the arguments, or the authors expect the reader to be familiar with Denisov et al. (2022). For example, in Corollary 3.1, the optimal dual solution computed, but how to get the primal solution from here? It also is the case with some experimental details (see below). It would be helpful if the authors can make the content more self-sufficient.\n\n4. Experiments: I do not understand the description of algorithms MF1,6e and MF6,6e; for MF1,6e the authors say that they use Theorem 2.1 to use \"the single participation optimized matrix\", but Theorem 2.1 is about reducing $d$ dimensional instances to scalar instances; what am I missing here? About MF6,6e, it says, is \"our approach ..\" -- which theorem/procedure description should I be looking at for this?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oCOVbAvmdl", "reviewer": "Reviewer_6QXF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel differentially private mechanism with multiple participations. Specifically, the author simplify per-iteration\nvector contributions problem by using a sensitivity computing framework and rigorous proof is given. Under the problem reduction, a convex program for the construction of optimal matrix mechanisms is proposed, and a closed form solution for it is also provided. To further reduce computational consumption, a Fourier-transform-based mechanism is designed. In experimental part, full comparisons with prior matrix mechanism approaches and DPSGD demonstrates the effectiveness of the proposed method.\n", "summary_of_the_review": "See \"Strength And Weaknesses\"", "strength_and_weaknesses": "a)  This paper emphasises their contributions/novelties on existing differentially private(DP) mechanisms. The extension is reasoned and the solution method is proved, and the effectiveness of method is proved by extensive experiments on example-level DP and user-level DP.\n\nb)  Author applies differentially private (DP) mechanisms with matrix factorization to gradient-based machine learning, and promot the achievable privacy-utility-computation tradeoffs.\n\nc)  The formula proof of paper is rigorous and orderly, and the diagram of the experiment is also very intuitive.\n\nd)  In section 4,the time complexity is analyzed theoretically. Could the authors report the running time of the proposed algorithm in the experiment? In this way, we can intuitively justify that Discrete Fourier Transform helps reduce computation.\n\ne)  The transition from the background to the formula should be elaborated in more detail so that readers can understand more quickly.\n\nf)  In the conclusions part, the following can be added. For example, weaknesses of work and future work discussion.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8i-StOUcBm2", "reviewer": "Reviewer_rY9u", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors provide new differentially private (DP) mechanisms for gradient-based machine learning (ML) training involving multiple passes (epochs) of a dataset, substantially improving the achievable privacy-utility-computation tradeoff. They propose a framework for computing the sensitivity of matrix mechanisms under general participation patterns. They extend the results of Denisov et al. (2022) to the optimization problems corresponding to these generalized notions of sensitivity. They propose and analyze a computationally-efficient factorization based on the Fourier transform.\n\n", "summary_of_the_review": "In this paper, the authors introduce DP mechanisms for gradient-based machine learning training involving multiple passes of a dataset, substantially improving the achievable privacy-utility-computation tradeoffs. The key contribution is an extension of the online matrix factorization DP mechanism to multiple participations. I think the novelty of the paper is little, however they significantly improves the privacy-utility tradeoffs while maintaining practically feasible computation costs.", "strength_and_weaknesses": "Strength:\nThe authors prove a new theorem bounding sensitivity for multi-dimensional data contributions based on an extension of the Birkhoff-von Neumann theorem. It allows to reduce the problem to that of measuring sensitivity for scalar contributions alone. \n\nThey show that the algorithms proposed in Denisov et al. (2022) can be extended in present setting. \n\nTo reduce the cost, they propose and investigate an approach based on the Fast Fourier which is near optimal for the single-pass setting and can be efficiently extended to handle multiple passes.\n\nWeakness:\nThe techniques applied in the present paper based on the methods in Denisov et al. (2022). The authors extend it to the multi-dimensional and multi-participation setting. I think the novelty of the paper is less. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "2bTTcPFYAL", "reviewer": "Reviewer_SJLq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides new differentially private (DP) mechanisms for gradient-based machine learning training that involves multiple epochs of a dataset, and improves on the prior results. The algorithms are based on extensions of the matrix factorisation DP mechanism for different settings, such as user-level DP and multiple epoch regime. As listed in the introductions, there are four main contributions of this paper.\n1. It provides a new framework for analysing the sensitivity of the matrix mechanisms under a certain user-level DP setting. This involves proving a new theorem for high-dimensional contributions based on an extension of the Birkhoff-von Neumann theorem, allowing to reduce to a scalar problem, instead.\n2. It extends the results of Denisov' 22 to the optimisation problems corresponding to generalised notions of sensitivity.\n3. It also gives a computationally-efficient factorisation mechanism that is based on the Fourier transform, that it claims is near-optimal for the single-pass setting, and could be extended to multiple epochs.\n4. It also provides empirical evaluations and comparisons of their algorithms with prior matrix mechanism and DP-SGD, and claims to outperform these methods.", "summary_of_the_review": "For me, the weaknesses outweigh the strengths a bit here. I am open to changing my evaluation later, but for now, I think a few improvements could help with the quality of this work.\n\nUpdate: based on the responses, I have bumped the score.", "strength_and_weaknesses": "Strengths:\n1. The analyses of the sensitivity of the matrix mechanisms looks quite interesting and involved to me. I like the idea of incorporating these generalised cases of multiple contributions by a single user (user-level DP) because that is a much more real-world case.\n2. The reduction to the scalar case also looks cute! It appears to give a cleaner way of visualising what the sensitivity could be, and anticipating the amount of noise that would be needed for privacy.\n\nWeaknesses:\n1. My first complaint is not too severe, but it is about the writing of this paper. I think the writing looks a bit rushed and doesn't really give the best intuition of what or why something could be expected, or in other words, there are places where the technical discussion is not necessarily supported by enough \"English text\".I see that happening in Sections 3 and 4, mainly. It is a little hard to see in the theorems what certain expressions mean and what they entail. In Section 5, there isn't any such issue, but Figure 2 that lies on page 8, is decoded and explained at the end of page 9, which is a bit confusing and distracting.\n2. I'm not completely convinced by the empirical results in the main body of this paper. Here's my issue. The optimal (but possibly computationally-inefficient) algorithm seems to work really well compared to all other prior work and this paper's FFT-based mechanism, but it is not really practical when $n$ is large because of its high runtime. I think the point of the authors here might be to show the promise of their new generalisation, but right now, it is not exactly useful in practice.\n3. The more concerning issue for me is that the practical analogue (that is based on FFT) of their mechanism is not super accurate. In Figure 1, it doesn't look that impressive even for the more useful values of $\\varepsilon$ ($\\leq 10$). It seems to be quite close to the Kairouz'21 algorithm, except when $\\varepsilon$ is between $5$ and $7$. The optimal (but slower) algorithms does notably better in this regime though, but that doesn't seem impressive because that algorithm is not really practical in real-world applications. For the multiple epoch setting, it doesn't seem that useful either. Therefore, if this is one if the highlights of this paper, I'm a bit disappointed, to be honest.\n4. I don't understand why the authors chose to compare in regimes where $\\varepsilon$ is more than $10$ or too high to provide any useful privacy guarantee. We do expect most non-trivial DP algorithms to become accurate in that range anyway, so what is the point exactly?\n5. I wish the authors had plots in the paper comparing their FFT-based approach more with other prior work. I know they have plots in the appendix, but they're hard to read because the plots for the prior work are separate from those for this paper's algorithm.\n6. I understand that the focus of this work is mainly towards practical DP ML via tools like privatised versions of SGD, but I wish that there were more about other applications, as well. Maybe, that would have asked for a separate paper, so I'm not *that* concerned about this. Would appreciate the authors' input on this though.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject