(Amplified) Banded Matrix Factorization: A unified approach to private training
Authors: Christopher A. Choquette-Choo
Arun Ganesh
Ryan McKenna
Hugh Brendan McMahan
J Keith Rush
Abhradeep Guha Thakurta
Zheng Xu
Venue: NeurIPS 2023 poster (2023)
Keywords: Machine Learning
Differential Privacy
Optimization
Private Machine Learning
Federated Learning
Privacy Amplification
Matrix Factorization
TL;DR: We propose a new class of banded matrix mechanisms that (a) are compatible with cross-device FL and (b) fully subsume amplified DP-SGD. This enables MF-DP-FTRL approaches to match or outperform DP-SGD across all $\varepsilon$.

Abstract: Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications in a variety of scenarios, but in both the centralized and federated settings there remain instances where either MF cannot be easily applied, or other algorithms provide better tradeoffs (typically, as $\epsilon$ becomes small).
In this work, we show how MF can subsume prior state-of-the-art algorithms in both federated and centralized training settings, across all privacy budgets. The key technique throughout is the construction of MF mechanisms with banded matrices (lower-triangular matrices with at most $\hat{b}$ nonzero bands including the main diagonal). For cross-device federated learning (FL), this enables multiple-participations with a relaxed device participation schema compatible with practical FL infrastructure (as demonstrated by a production deployment).  In the centralized setting, we prove that banded matrices enjoy the same privacy amplification results as the ubiquitous DP-SGD algorithm, but can provide strictly better performance  in most scenarios---this lets us always at least match DP-SGD, and often outperform it

(Amplified) Banded Matrix Factorization: A unified approach to private training
Christopher A. Choquette-Choo
Arun Ganesh
Google DeepMind cchoquette@gooqlee com
Google Research
arunganeshegoogle.coo com
Ryan McKenna Google Research
Brendan McMahan Google Research
Keith Rush
Google Research
mckennar@google..o com
mcmahan@google com
krush@google. com
Abhradeep Thakurta
Zheng Xu
Google DeepMind at athakurta@google..com
Google Research
xuzhengggooggle com
Abstract
Matrix factorization (MF) mechanisms for differential privacy (DP) have substan- tially improved the state-of-the-art in pivacy-utiltty-comuaaa applications in variety of scenarios, but in both the centralized and federated settings there remain instances where either MF cannot be easily applied, or other algorithms provide better tradeoffss (typically, we show how MF can subsume prior state-of-the-ane algorithms in both federated and centralized training settings, across all privacy budgets. The key technique throughout the construction of MF mechanisms with banded matrices (lower- triangular matrices with at most nonzero bands including the main diagonal), For with
tradeoff' ML
becomes small). In this work,
cross-device federated learning (FI.), this enables multiple-participatte relaxed device participation schema compatible with practical FL infrastructure (as demonstrated by a production deployment). In the centralized setting, we prove that banded matrices enjoy the same privacy amplification results as the ubiquitous SGD algorithm, but can provide strictly better performance most scenarios this lets us always at least match DP-SC DP-SGD, and often outperform it.
Introduction
We consider machine learning (ML) with DP in the centralized (datacenter) setting and the cross- device FI. setting, extending and improving matrix factorization (MF) mechanisms to advance the state-of-the-art in both. Given
batch gradients x; Edd for [n]] steps, the MF-DP-FTRL algorithm uses a noise generation matrix C-1 E 18 to return DP gradient estimates x; X; + [C-2z/ where z Raad has IID entries A/O o²) for suitable o O. The noise correlation induced by C-1 is key to the success of MF-DP-FTRI. Alg. and Sec. provide details and intuition, and Table in App. A summarizes notation and symbols.
Wee matrix factorization for the algorithmic design of DP mechanisms, and then these mechanisms general-purpose gradient-based private optimization algorithms. This of matrix factorization is unrelated machine learning settings such as collaborative filtering or recommender systems where the MI. problem itself involves matrix factorization [37, 51].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

accurscy (56)
Teat accuraci (15)
60
Mechanism
23
DP-SCD ampl.
Mull--poch MF, ampl.
Multi opoch MF, no ampl. (Band) MF, amgl. (0urs]
(Band) MP. w/ ampl (Durs)
1.0
4.0
8.0
16,0
Privacy budget a
Privacy budget 5 10
(a) Centralized CIFAR-10
Centralized StackOverflow
Figure I: In the centralized setting, our BANDMF mechanism consistently performs at least as well as the best prior methods. LEFT, (A): At E 2 0.5, our BANDMF mechanism offers consistent utility benefits of around - 4 percentage points over either DP-SGD [1] or MULTI-EPOCH MF [15]. RIGHT, (B): BANDMF (bands = 9, 18, 32, and 64 for = 1 1-8 respectively) significantly outperform both (unamplified) MULTI-EPOCH MF and amplified DP-SGD.
In datacenter applications, precise control of the sampling/Shuffing of training data is possible, and so DP-SGD with privacy amplification [1] is one of the most popular ways to train machine learning models with formal privacy guarantees. However, Choquette-Chie that multi-epoch extension of the ME-DP-FTRL algorithm can outperform amplified DP-SGD in some settings, depending on the privacy and computational budget (typically larger budgets above and small number of training epochs). This leaves the state-of-the-aue for centralized DP training in the unsatisfactory state where one must try both algorithms be assured of the best performance.
et al. [15] recently demonstrated
In cross-device federated learning, devices choose when they are available to participate in training, and so precise sampling and shuffling is generally not possible (see Sec. for more details). Motivated by these limitations which make amplified DP-SGD infeasible, Kairouz et al. [35] developed the (tree- aggregation-base DP-FTRI. algorithm. Their DP-FTRI. does rely on (or benefit from) privacy amplification and instead adds carefully correlated noise to the gradients to boost utility. Denisov al. [17] proposed ME-DP-FTRL, replacing the tree-aggregation scheme of Kairouz al. [35] with a general matrix-factorizatio
mechanism. By optimizing over this space to find mechanisms with optimal error, substantial performance improvements were possible. However, the work of Denisov et al. [17] applies only to the single participation (single epoch) setting. Hence, for cross- FL the state-of-the-art also requires considering multiple algorithms: tree-aggregation-bee based DP-FTRL when devices may participate more than one time, or MF-DP-FTRL when devices participate only once. Importantly, the extension of MF-DP-FTRI to multiple epochs of Choquette- et [15] only applies in the centralized setting, as it again requires precise control of the participation pattern.
In this work, we address the limitations of ME-DP-FTRL (MF for short) noted above, and show that can, in fact, achieve across-the-board state-of-the-at performance in both settings across all e. To accomplish this, we define family of banded MI mechanisms, shown in Fig. 4 (c.f. Fig. 8 of App. D for visualizations of other factorization structures). We summarize our main contributions below.
Contributions for cross-device FL Here, the (k, particciiaioo schema of Choquette- Chhuo et al. which can be
[15] cannot be enforced. We propose a strict generalization. --min-scp-participaaee practically enforced by FL infrastructure. We show how efficiently and exactly bound the sensitivity for banded matrices in Thm. 2, allowing formal DP guarantees and the numerical optimization of optimal mechanisms (Sec. 4). These innovations lead to significant privacy-utiliis benefits a production deployment (Fig. 6 of Sec. 6). Our work also generalizes the sensitivity calculations of Choquette- Choo et al. [15] to provide a general apper-bound on b-min-sep ceain--s--pattiiiiieee seeppatticipationn sensitivity (Thm. 3), which allows the matrices of Choquette-Chor et al. [15] to be used in the FI. setting, as well as removing the need to exactly bound b before training (see Sec. 6 and App. K).
Contributions for centralized training The existing privacy amplification analysis of DP-SGD does not allow for the correlated noise that is applied in MF-DP-FTRL. Our paper introduces a novel partitioning of the BANDMF iterates into independent queries. This allows us to prove in Thm. 4 of Sec. that banded matrices enjoy the benefits of privacy amplification, and show that DP-SGD is special case, giving the best of both algorithms. This enables us to always pureto-dominate DP-SGD, unlike Choquette-Chneee CCho al. [15] which only does so for large enough e as observed in Fig, 1. Further, this allows us to improve on both baselines, between 1 4%-points. Informally:

---

DP-SGD
MF DP-FTRL
betch
clpped bolish gradient
mechariem culput &
cliped batch gradient
mecherism oulput X;
18 18 sal
X
Gaussian Mach
XI
X)
X]
8D
BDD
MF Mechanism
2
K
Gaussian Mech
X2
+
X2
(statefid rounds)
+ C7/221
K19
R
3
8DD
+
X3
Gaussian
Mach
X1
1.D
+
X
Figure 2: ME-DP-FTRL (Alg. 1) enables noise cancelling across steps, where DP-SGD does not. The entries J are mostly negative (in [0, (1)) in matrices C-1 we consider (see Fig. 8). Thus, the red terms show that MF-DP-FTRL "cancels out" noise added on earlier iterations. For simplicity, we assume C-1 has 1s on the main diagonal and entries Cj. otherwise, with z, [[s:]] the rows
Theorem (Informal version of Theorems and 5). Suppose we partition the dataset into b equal- size subsets, and in step each example in the (mod b) -th subset participates with probability Bb where there are m examples and the batch size is B. Then, b-banded n-iteration matrix mechanism with s b satisfies the same privacy guarantees as answering n/b queries on a dataset, where each element of the dataset is independently included in each query with probability Bb
As an example of Thm. 1, consider doing 2, 2,000 iterations of DP-SGD on CIFAR-10 10, which has m = 50, 000 examples, using a minibatch of B = -000 examples in each round. This has the same DP guarantees as answering 2, 000 queries using a subsampled Gaussian mechanism with sampling probability p = 500/50, 000 0.01. If we instead use, e.g.. BANDMF with i b= b = 10, our suggested sampling scheme is the following: Partition CIFAR-10 into 10 subsets of 5, 000 examples each, D1, D2... Do. In rounds 1, 11, 21... we sample 500 examples from Dj, in rounds 2, 12, 22... we sample 500 examples from D2. and on. We sample from each D, total of 2000/10- 200 times, and each time our sampling probability is 500/5000 = 0.1 within the subset. So Theorem shows = 10 BANDMF satisfies the same DP guarantees as answering 200 queries with p 0.1. As special case of Theorem 1, DP-SGD is simply MF with suitable diagonal matrix with b= 1, and thus Thm. recovers the privacy guarantees of DP-SGD with amplification by sampling. Empirically, we show that MF with amplification has privacy-utility tradeoffs that are no worse thun DP-SGD for all e, and often significuntly better as can seen Fig. 1.
Finally, we explore the computational tradeoffs of our approach. We find that banded matrices with catn---eppppatiipatiiooo are equally efficient optimize as those under (k, -paatticcipttion but significantly reduce the memory and time complexity of the per-iteration noise generation from O(n) to constant (b) (where often total steps n >> d). We will release all code with the final manuscript.
Related work The matrix mechanism (MF mechanism or MF) [40] has a rich history in offline, statistical queries [22, 28, 42, 62], with many applications including to online PCA [21], estimating marginals [22], and top-k selection [17]. Recently, this has been studied under the adaptive streaming setting, where privacy analysis must account for an adversary adaptively defining the inputs each step [17, 24]. Denisov et al. [17] showed a connection with the DP-FTRL algorithm of Kairouz et al. [35] and with DP MI broadly; they showed that computing optimal MF significantly improves the drivac--uility-comrraa
tradeoff's when making only a single pass (epoch) over the training data. results in DP ML by showing how to optimize MF under arbitrary passes over the training data. Henzinger and Upadhyay [29] study the problem of DP-continual observation [13, 20] and the explicit factorization of the workload matrix A that minimizes the completely bounded norm, which is only off from the optimal by an additive constant. The connection between DP empirical risk minimization [3, 4, 5, 7, 8, 9, 14, 16, 23, 25, 32, 36, 39, 45, 52, 53, 54, 57] and DP online regret minimization [2. 4, 5, 26, 33, 35] has been studied for long time. Asi et al. [5] demonstrated that DP-FTRL style algorithms [15, 15] achieve the best known regret in certain classes of online learning problems (a.k.a. the realizable regime). An important question that still remains open is whether DP-FTRL. style algorithms can obtain optimal population risk guarantees under DP [9].
Choquette- Chho et al. [15] showed that MF achieves state-of-the-
3

---

Algorithm ME-DP-FTRL and DP-SGD
Inputs: Initial model 01 E RR, dataset D examples, matrix C-1 E IR IRxx, noise z é Raxd with entries i..d. (0, o²), clipnorm
& DP-SGD is simply the case C- = the n x identity matrix.
for i 1,2,...,,7? do
Select a set S = (dl,...,dd.) (.....,,)]_)) ED > Respecting schema IT. possibly sampling, Alg.
g, = cllipp/vlllie clip(Voloss(d)) (d,, ()) for j [B], where clip(d, min(L:c/Id))
x; = Σ==1 8.)
x; x; 2[C-'ZJpa
D x is now a DP estimate of X
0, = (,,
> Any first-order optimizer can be used in place of SGDM
Matrix Factorization, Sensitivity, and Efficient Implementations
Let x E Raxd be a stream of model gradients, and let A e IR" be an appropriate linear query work- load (prefix-sums, a matrix encoding of stochastic gradient descent with momentum (SGDM) [17]). Matrix mechanisms use a factorization A BC to privately estimate the quantity Ax as
Ax B (Cx+z). z),
(1)
where z suitably calibrated noise to the sensitivity of the so-called 'query matrix' C.
Efficiently implementing MF-DP-FTRI. Eq. (1) can be re-arranged as ((x C-12). The multipli- cation by the linear operator A can now be viewed as post-procsssing of the noisy mechanism outputs x +=; in many cases, this postprocessing has efficient streaming implementation, e.g., simply passing gradients into a SGDM implementation. Thus, implementing ME-DP-FTRL is essentially equivalent DP-SGD. The only difference is that the per-iteration gradient x; is protected with noise (C-12|(s.) rather than [(t.)- Indeed, we see DP-SGD a special case simply by taking C = C - I.
Further, as long as the noise C-'z is computed correctly, the privacy guarantee holds, independent of the choice of A. Alg. gives the complete algorithm: with an appropriate choice of the matrix C-1 this algorithm captures DP-SGD, rre-aggregation DP-FTRL [35], as well as MF-DP-FTRL. [15, 17J. The multiplication of C-1 by Gaussian noise z RRaxd (which need never be fully materialized at once) is the critical step in the efficient implementation of MF. In App. J, we note this multiplication can be completed online for i-banded matrices (defined formally in Sec. 3) in time and memory (bd) per training iteration compared to (nd) for a non-banded matrix.
Multiple participations We adopt the formalisms for citiileepprtccipations of Choquette-Chov al. [15]. We assume there are m examples (or users in FL) in the database where B examples are selected on each step i e [n]. These B chosen examples are said to participate on this step i. The examples at each step are processed via any adaptive function, e.g., computing a gradient of the current model (which depends on the model parameter values) in Alg. 1. The per-example output vectors g e Rdd are each bounded l norm at most Ç (noting that our notions of sensitivity scale linearly in Ç. without loss of generality (WLOG) we take to be I in analysis below). These clipped vectors are then summed to yield x, Σ gj- The MF-DP-FTRI. mechanism releases the privatized estimates of x; in a streaming fashion. The multi-epoch setting occurs when m < n B, so that every example necessarily participates more than once.
Intuition for (anti-) correlaco noise in MF-DP-FTRI Fig. 2 compares DP-SGD and MF-DP-FTRI. To gain an intuition for why MF-DP-FTRL can perform better than DP-SGD, observe that vanilla SGD has iterates 0- 8g 7) E &; and hence when the noisy gradients &; are added, the CT.,) [ terms in MF-DP-FTRL serve cancel out some of the noise introduced on previous rounds. This reduces the total error in the final model (i.e., the prefix sums). However, this worsens the sensitivity of the mechanism >1 (as it for DP-SGD). This is because an adversary trying to learn x, via X1 can partially learn the value of z from X2, whereas in DP-SGD x and X2 are uncorrelated. This tradeoff what MF-DP-FTRL aims minimize. More details on this intuition are App. A.I.
IIn this case suitable pseudo-inverse C2 1 with noise 1 2xn

---

Adjacency and participation schemas DP requires notion of adjacent datasets. Two data streams x and are adjacent the data associated with any single example is altered. but not when this example participated. Thus, any x; where example dj participated can be changed subject to the constraint
||s (1) s Ç. However, the participation pattern does not change. A participation schema II gives the set of possible participation patterns π E II, with each я S [ni] indicating set of steps in which single example might participate. Let N be the set of all pairs of neighboring streams x and D := {x- - X (x,*) E ] represent the set of all possible deltas between neighboring x, x. We say D satisfies the participation schema if the indices of all nonzero rows in each Rodd matrix u 2 are subset of some π ПI. To illustrate this, single-participann
is represented as =1= (11), (2)). (2)....(11) [ and full-batch gradient descent (every-step) as =1= {[n]]). Choquette-Chir et al. [15] studied fixed-epoch-order participation, denoted (k, particiipation where each example participates at most l times, with any adjacent participations exactly steps apart: formally. II is the set of all such that [π| s k, and if π { .ig) indexed in increasing order, have Vj (2...., k). 1. - - b. For example (k=2, b=3) parttiiiiiiinnnoion has II= {{1, 4). (2,5). (3, 6)}} As discussed in Choquette- Choo et al. [15], this setting faithfully captures centralized multi-epoch ML training setups with single and every-step as special cases. We can now define the sensitivity of the matrix factorization mechanism
sensm (C)
sup |Cx- CX| sup Cul (x.8)=N
D
Optimizing factorizations Different factorizations A = BC can have very different performance in practice. Thus, in MF applications it is common to optimize over the space of factorizations, where the objective function is the expected total squared error on A, given L(B, C) = sensh |B| We define the expected root-mean-squant equaane error (RMSE) as av C(B, C)/n, where a is the standard deviation of the Gaussian noise. We take 1 when simply comparing mechanisms, (in Sec. 6), calibrate a to achieve specific (tP guarantees.
To facilitate optimization. utilizing the fact that the optimal-for -oruull--o---urd-e-reee decoder is AC [17], we note C(B, C) C(AC", C). The expected total squared error is invariant to scaling C by a constant, and hence it sufficient optimize under a sensitivity 1 constraint. Further expressing the sensitivity and error in terms of X = C C (note X is unrelated to the data x), we have
C(B, C) L(AC', C) = |AC* 1| tr|A 11
assuming sensn( C) 1 and A is in the rowspace of C. Thus, we arrive at:
Problem 1. The matrix factorization optimization problem is to solve the convex optimization
minimize X
tr[A AA subject to s s 1,
and then find C so that CT X.
CX e.g., via Cholesky decomposition.
3 A Participation Schema for FL and the Sensitivity of Banded Matrices
In cross-device FL, devices locally evaluate eligibility criteria to deterimine when they might par- ticipate in training [10, 34], for example only checking-in in to the coordinating server when they are plugged in, on unmetered wifi, and idle. This makes it practically difficult to enforce the (k, b)- participation of Choquette-Chon
et al. [15], where devices are assumed to participate at the same relative position in each epoch: devices are unlikely to meet the eligibility criteria during the nar- row windows of both step i and i + b. Further, precise sampling cannot provide the same level of privacy amplification in the centralized setting. Consider if 6500 devices are needed to complete round [59]. An extreme (but realistic depending on time of day) setting may have only 6500 devices meeting eligibility criteria. Thus, either the protocol proceed without any sampling/amplifcaute or wait until more devices are available; neither are desirable. We avoid amplification in the cross- device setting and instead proceed by addressing the question: Can MF-DP-FTRL be extended to the cross-device federated learning setting with multiple client participations?
With (k, b) -participation difficult to enforce in practice, our first challenge is to define a new par- ticipation schema with several properties: (a) the sensitivity of any matrix mechanism under this query can be bounded; (b) this bound is tight over an expressive class of matrices; (c) this bound
5

---

can be efficiently represented as constraint in a mathematical program so as to be able to find near-optimal factorization BC. In Defn. I, we propose of (k: b)partiicipation which can be practically enforced by cross-device FI. systems, thus enabling the distance between
a generalization
us to leverage BANDMF in this setting (see Sec. 6).² In --mi--se--partiippatie any two participations is at least b, rather than exactly b as in (k: 6) particippatin:
Definition 1. The b-min--ep-parrtcciaaton schema is given by
IT { = [7x] (i.5) S Em 11
Observe this participation schema is easy for devices to enforce: each device remembers the last step i in which it participated, and when it again becomes eligible, it checks in to the server, and participates in training as long as the current step is at least i + b; does not need to check in during a narrow (and unknown to the device) time window for specific step.
We now turn to computing sensitivity under [[(,,,)] = b, a fact Choquette-Choo et al. [15, Eq. 3] critically exploited when computing sensitivity via brute force computation of maximum over the elements in II. With
For (k: ((,.))-pl participaatin
we have [ = O (exp(n)), and hence any brute force approach which requires checking some value for all e II, will be impractical. Following the formalism of [15, Section 2], a participation schema II (plus specification of model dimension d) yields an expression for the sensitivity of the function x Cx assuming that the contributions of any given user the data structure x are restricted the rows in x indexed by some IT. By Prop. E.1 of App. E.2, independent of model dimension d, we show sensitivity for any schema may be bounded by
sensn (C)² S mmx Σ (1.)) well
Eq. (5) highlights several subtleties in computing sensitivity. First, is the challenge presented by the exponentially large number of patterns in 1I, Second is the question of tightness of the inequality in Eq. (5): how much are losing by effectively ignoring any cancellation in the matrix X?
Banded matrices Fortunately, banded matrices render Eq. (5) both exactly computable and tight (independent of dimension d). showing that II, satisfies the requirements of (b) and (c) above. We say a (general) matrix X is b-banded if for all i, E [mx. - jl 2 b implies X [(,)] O. While this is off-by-one from the bandwidth (X has bandwidth b 1), our definition will be useful it will be natural to match b-banded matrices with b-min- separation. Further, for b b-banded lower- triangara matrices (which will play a central role), b intuitively gives the number of bands the matrix.
For non-banded matrices, the right-hand side of Eq. (5) remains efficiently computable (but not easily expressible in mathematical program), enabling to provide nontrivial privacy guarantees for matrices which are not b banded under t-min-sep, showing that II, satisfies (a) as well. The key subroutine is Alg. which gives an efficient dynamic program for solving linear optimization over Il. Define (TT)& e 10.1)" 1)" by u(T); = 1 if т and O otherwise. Then, Alg. 3 solves
min (v, u(r)). rell,
This is the key subroutine in Alg, 4 and Alg. 5. Proofs for Thm. 2 and Thm. 3 are deferred to App. E.2. Theorem 2.
Let C & Rnxn be a lower-triangular matrix, and 1l, the Further, suppose K' upper-bounds the actual maximum number of participations that occurred in a data stream x (at worst, we may take k' s B
schema.
To 1) Then: (1) If is an upper-bound on the column norms of C, that is Vj E [m], |9 S K, and C is b-banded, then the sensitivity is bounded by w/W.. (2) C is b-banded, Alg. 5 invoked with Gram matrix X CTC and b, k as in the setup, exactly computes scns(C) (C) under schema HI in polynomial time for any dimension d.
Theorem 3. For an arbitrary (non-banded) C, let X = CTC and b, K' as in Thm. 2. Then Alg, 4 of App. E upper- -ounds sens( C) under schema HI, in polynomial time for any dimension d.
While b-min b-min-sep-pap www-sseppppppeee particiiiiiioo is required for the cross device FL setting, (k, b-rtt))ppiiipatiinnnn is preferred in centralized settings where it can be enforced and will also satisfy our BANDMF amplification guarantees leading to the empirical results show in Fig. 1.

---

4 Optimizing Banded Matrices
To enjoy the benefits of banded matrices within the framework of MF-DP-FTRL, we need design an algorithm that can efficiently optimize over the space of b-banded C matrices. To solve this problem, we will work in the domain of X = C, and utilize the following fact:
Proposition 4.1. Let X & IR be a b-banded symmetric positive definite matrix. Then there exists a lower triangular b-banded matrix E Raxn such that X = C.
Utilizing Prop. 4.1, we can modify Problem by introducing the constraint X [t.5] = if j| 2 8. This additional linear constraint preserves convexity of the optimization problem, and makes the sensitivity calculation tractable as well. However, it is still not immediately obvious how to solve the optimization problem, since we need to run the dynamic program defined in Alg. 5 of App. to compute sensitivity. For this reason, we impose the additional constraint that diag (X) 1. This constraint, together with bandedness, ensures that the squared sensitivity is equal to for all X by Thm. 2. The final optimization problem we seek to solve is stated below:
Problem 2. The matrix factorizaain optimization problem for banded matrices is to solve
minimize tr tr(A AX X
subject to diag (X) and X if -1
(6)
and then find C so that C' C X via Prop. 4.1.
We would like to remark on the similarity between Problem 2 and the Problem 1. The two problems are identical modulo the bandedness constraint, which is an equality constraint on individual entries of X. Therefore, existing commal-ppiimzztioon based solvers [43] for the single-participatiin matrix mechanism can be extended to optimize over this new space of matrices with little modification. Specifically, the only modification necessary to initialize to an appropriately banded feasible X matrix, like X I, and post-process the gradient w.r.t X by setting AL = 0 if ji jl 2 6 in each step. Since the equality constraints exactly specify individual entries 8X of X, Problem can be solved as an unconstrained optimization problem (over the remaining entries in X), using any number of off off-the-shelf unconstrained optimization algorithms." 4 As recommended by McKenna et al. [43], we use the LBFGS algorithm [12] to solve this problem.
version of
Remarks on the diag (X) constraint The constraint on diag (X) serves multiple purposes. First, diag (X) = 1 implies that [Cr,4] l2 1 for all i, i.c., that C has equal column norms. This ensures that BANDMF reduces DP-SGD when b 1. which is desirable. Second diag (X) = simplifies the optimization problem greatly, as the sensitivity computation for both (k, b) ppatticpaiiiiinononnnn and b-min-sep are trivial and tight under this constraint (Thm. 2 Claim (1)). Third, imposing this constraint does not drastically change the search landscape, cost much in terms of RMSE; see Table 2 for a comparison of matrices with and without this constraint, and Fig. for a visualization. Fourth, this constraint allows to solve a single optimization problem that is simultancously tailored for (k, b) pprrticiipation and seaii--sp-particppaee an optimization problem without the diag (X) 1 constraint, discuss how we solve it, and compare matrices generated with and without this constraint empirically.
In Appendices B and C, we formulate
5 Amplification for Banded Matrix Mechanisms
In the centralized setting where we can control the participation patterns of individual examples, the privacy guarantees of BANDMF can be amplified. We focus on amplification by sampling with fixed batch size in this section, but give a more general statement in App.
Existing privacy analysis of MF-DP-FTRL is based on the reduction to the batch release of the entire Cx z as a single Gaussian mechanism event [15, 17] so standard amplification techniques don't 't directly apply. Instead, for each participation by an example, we consider the set of rows in Cx affected by this participation as a Gaussian mechanism (see the groups of rows in Fig. 4). Then as
"Note that the constraint that X is positive definite is typically handled implicitly by taking sufficiently small step sizes to avoid violating that constraint [43, (43.
7

---

Independent D
Quary on examples step
Algorithm 2 Sampling scheme
Di..... D3 arbitrary partition of D.
b+j
for i= = 1, 1.2..... do
Quary on examples step b+y
j= (mod b) (b if i/b integer).
26+j
S -- random size B subset of Dj.
Quary on examples step 2brj
Compute x; on S. Release Cx z.
36-4
Query on examples
step 3b++j
b+j
2h+1
2b++
Figure 3: An example of our sampling scheme that gives privacy amplification for BANDMF.
Figure 4: Visualization of how can decom- pose BANDMF into independent queries when using Alg. Larger view in Fig. 10 of App. F,
long as the sets of rows corresponding to different participations do not interact, which is ensured by the bandedness of C. we can apply amplification them separately.
Observe from Fig. that the structure of BANDMF guarantees that the set of rows of Cx which disjoint sets. Thus, we use the following sampling scheme for determining which examples participate in each step which is made formal as Alg. 2. Let D1, D2,..., Dj be an arbitrary partition of D into b indexed subsets of size in |m/6] (for simplicity, we discard extra examples so all Dj have size exactly rī). In steps j. 6 j. j...., we will only use examples in Dj. Hence, participation follows (k, pparticciptiio for b= 6, because it optimal for (k: b) participation to have the number of bands 6 equal the ciin--eperation b, in the remainder of this section and the associated appendices we simply write instead of b. Within each of these steps, we sample size B subset of D, uniformly at random to use in computing
depend on each of X,, X2bb,.
Roughly speaking. Thm. 4 below shows that if we use Alg. 2, BANDMF satisfies any standard privacy guarantees satisfied by DP-SGD run for k rounds, where in each round we sample B examples from dataset of size m. In other words, it equivalent to running DP-SGD for 1/b times as many rounds, but with the sampling probability multiplied by b.
Theorem 4. Suppose C is b-banded and lower triangular, and the examples participating in each step are chosen according to Alg. Then BANDMF satisfies any standard DP guarantee satisfied by performing k sensitivity-K queries on dataset of size in using the Gaussian mechanism, where each query run on a random subset of examples of size B. K is the maximum column norm of C.
The key idea behind Thm. is the following: assume we have two datasets D, D' that differr in an example in Di (WLOG), i.e. the differing example can only participate in steps 1, b..+1..... (k--1,....,..)). Then by the banded structure of C and the standard technique of reducing adaptive queries to non- adaptive queries (see e.g. Claim D.1 in [17]), the first b rows of Cx (i.e., all the rows where examples in step influence the output) can be viewed as a query on the examples in D2 that were included in step 1, the next b rows can be viewed as an adaptively chosen query on the examples included in steps 1, and so on. See Fig. 4 for a visualization.
Generalization to other privacy amplification techniques Thm. in App. F.3 provides a strong a generalization of Thm. 4. It shows that shuffling, another common amplification technique often used for DP-SGD, can also be applied to our BANDMF. We also provide an explicit algorithm for accounting for amplification via sampling in terms of the dp_ app_account ing library [18], along with examples of concrete privacy parameters derived from these corollaries.
Optimizing the number of bands Thm. shows that different numbers of bands (with corre- sponding sampling scheme) give different privacy amplification guarantees. This implies given a particular privacy (or RMSE) target, one should optimize the number of bands to get the best RMSE (or privacy) possible. This can be done efficiently. Generally, for large values of c larger numbers of bands perform better, and as + 0, eventually amplification dominates so i becomes optimal. Details are App. F.4.
$ and our case, 1 always. 'Standard DP includes c-DP, (c,8)-DP, Rényi DP, zCDP, and Gaussian DP.
8

---

RMSE 3024
RMSE Ratio, 1024
004 R 8:4
3.00
WF
15
Mult-epoch PP; ampp
DP SCD, WT angt.
1:2
(flend w (Ours)
023-
0.25
Privacy Budget
RMSS
10
181
3.0
40
10"
101
10a
10
Epachs
Epochs
(a) DPD vs. MULTI-EPOCH MF (b) DP- vs Ampl. BANDMF
(c) RMSE vs Epochs at c= 1
Figure 5: Comparison between DP-SGD, MULTI-EPOCH MF, and BANDMF in terms of RMSE on the prefix-sum queries, for n = 1024 iterations, E E [ 16]. = 10- and epochs e [1, 1024]. Color indicates the ratio in RMSE between two mechanisms. Additional details in App. G.
Experiments
Our experiments example-level DP for image classification (of CIFARIO) and user-level DP for next word prediction (NWP) (of Stack Overflow NWP) focus on comparing our BANDMF with the existing of-th-of MULTI-EPOCH MF [15] and DP-SGD [1]. We finish by showing that BANDMF improves over state-of-the-ar [35] for a production mobile keyboard next word prediction model. In all cases, noise is calibrated using privacy loss distributions [38] to achieve the stated privacy guarantees for zero-out adjacency [35, 48], as implemented in [18]. Following the common convention, amplified results are based on privacy accounting for Poisson sampling, though shuffling was used in non-production training. We find BANDMF can outperform both mechanisms across wide range of privacy budgets to low
0.5. Past this, is no worse than either.
RMSE We begin by comparing DP-SGD with MULTI-EPOCH MF and BANDMF in terms of their RMSE (Sec. 2) the prefix workload. This is one measure for how much noise these mechanisms add during training, and is a reasonable proxy for learning performance.Obser there are regimes where DP-SGD outperforms MULTI-EPOCH MF and vice versa in terms of RMSE. When then number of epochs equals n,, DP-SGD reduces to full gradient descent (GD) (and there is no amplification benefit), and the optimal MF mechanism is close the identity matrix (that is, GD), and so the algorithms become almost identical (MF has a very small advantage, as the identity matrix not quite optimal for RMSE). However, as shown in Fig. 5(b), we see that BANDMF always at least as good as DP-SGD in terms of RMSE. The improvement is most potent in the lower number of epochs and higher regime, which is standard for large model training. In Fig. 5(c), we see that for fixed n as the number of epochs increases, all mechanisms enjoy improved RMSE, and BANDMF in fact reduces to DP-SGD in that regime (though BANDMF may be outperformed in RMSE by MULTI-EPOCH MF due to our imposed optimization constraint of constant diagonals in X).
in Fig. 5()) that
Centralized training with amplification Our full experimental setup described in App. H, and closely follows prior work [15]. We train for 20 epochs on CIFAR- 10, and tune all mechanisms to achieve their best performance for each e, using 12 repeated runs. Fig. ((a) shows that BANDMF with amplification and an optimized number of bands d can obtain utility benefits over both prior mechanisms. We find that for e E [2,5], BANDMF achieves a consistent s percentage point boost in performance over MULTI-EPOCH MF. Below e 2, where DP-SGD previously dominated, we find that BANDMF obtains benefit around 3 percentage points. These two findings show that BANDMF able to balance and leverage the benefits of both amplification and correlated noise effectively. As the budget gets smaller, we find that BANDMF is equivalent to DP-SGD.
We next consider the now-standard StackOverflow next- differential privacy, again following [15] (full details in App. I), in particular 2052 steps and 6 epochs, with 1000. The previous state-of-the the-t-rr for centralized training at c 2 2 corresponds to their MULTI-EPOCH MF.7 We again tune under amplification for optimal RMSE, selecting b = 9, 32, 64 for E = 1,2, 2,2,48 4, respectively. At = 16 we find MULTI-EPOCE MF is optimal. Fig. (bb) shows substantial improvements for combining amplification with MF for [1, 8]: Table 5 of App. gives the hyperparameters and accuracy values for this figure.
(NWP) task with user-level
7 All StackOverflow experiments use the 2=2052 matrices optimized with caall-oollmnoooo via Eq. (6) for MULTI-EPOCH MF, which observed to be minimally different in terms of RMSE and accuracy.
9

---

26
16.0
24
Accuracy smoothod
15.8
22
15.6
20
SGD
15.4
Singlespochh
Optinal TresAgg
15.2
18
Mutt epech MF
15.0
Orline TrowAgo
16
Band MF (Curs)
14.8
Band MF (Ours)
2.0
4.0
16.0
500
1000
1500
2000
Privacy budget
FL Training Round
(a) Simulated cross-device FI., SO NWP
(b) Production mobile keyboard training
Figure 6: BOTH:
Amplification is infeasible as outlined in Sec. and App. K. LEFT, (A): Cross- BANDMF, and MULTI-EPOCH MF (with the application to FL made possible by Thm. 3) outperform all prior work. RIGHT, (B): Evaluation accuracy of language model trained in real-world FL system. BANDMF achieves higher utility and a stronger (4.35, 10 --DP compared to the (6.69, 10 10-1000-00 -DP achieved by ONLINE TREEAGG [35].
device FL results under b-342- min-sep-paartiiipation
Cross-device federated learning We consider SO NWP again, but now assuming each user's data corresponds to the data on one device. We assume 2052 rounds and 6 epochs as above. Amplification generally not possible in the cross-device setting, and the prior oftte-of-theaar was (1) SINGLE- EPOCH MF of Denisov et al. [17] for single-epoch training (using B = 167 rather than B = 1000), and (2) OPTIMAL TREEAGG, which essentially takes the binary-tree matrix Cr, and instead of using Ciy- for noise generation (see Sec. 2). The b-min-sep- see--ppapaiiittiinnn sensitivity of Cy can still be calculated using the dynamic program of Kairouz et al. [35], while the use of Cl requires the machinery of Denisov et al. [17]; see e.g. the OPTDECODERIA HODDDEOHHHKKRRRRR results of Choquette-Chop et al. [15, Fig. 6]. Our Thm. 3 further sensitivity of the MULTI-EPOCH MF matrices
the less-efficient "online" estimator of Honaker [30], uses the pseudo-invers
enables an upper-bound on the b-min-sep-particiin
of Choquette-Chor et al. [15]; this incurs a penalty of about 15% (see Table 2 in App. C) compared
to (k, b)-sensitivity. Fig. 6(a) shows that our BANDMF and MULTI-EPOCH MF again outperform
prior baselines (though the previously untested multi-epoch OPTIMAL TREEAGG performs quite well); Table 4 gives the hyperparameters and accuracy values for this figure.
Application in production cross-device FL We fine-tune Spanish next word prediction model, pretrained on the multilingual C4 dataset [49, 60], with on-device user data using FL. Our setup follows [59], and is described in full in App. K. We compared to an existing implementation of the ONLINE TREEAGG algorithm of Kairouz et al. [35] (not the optimal version using Cf in simulation).
Both algorithms ran for 2000 training rounds. The BANDMF matrix was optimized for b 400 bands; however, the production system only allows approximate control of the separation between participations, and post-hoc we could only bound b by 390 rounds for ONLINE TREEAGG and 385 for BANDMF, necessitating the use of Thm. 3 for the analysis of BANDMF as b < b.
We used the same clients/round goal of 6500 for both, and tuned noise multipliers to achieve compa- rable RMSE, hence tuning for stronger privacy guarantee rather than improved accuracy. Fig. 6(b) shows our results, and we see BANDMF actually achieves a slight improvement in accuracy, possibly due learning-rate cooldown (which was only implemented for BANDMF). Our primary re- sult is then that we are able to improve the privacy guarantee from p=0. 2-..222-CCDPP for ONLINE TREEAGG to p=0.24-2CDP for BANDME, or (e=6.69, 5=10-10)----- -- to (c=4.35, 1=10-1")-DP De- tails of the privacy guarantee following the best practices of Ponomareva et al. [48] are in App. K.
7 Discussion and Limitations
In this paper, we proposed the BANDMF mechanism, which extends MF-DP-FTRI and enjoys the benefits of privacy amplification. This allows solely operate above the previous Pareto frontier defined by both amplified DP-SGD and MF-DP-FTRU in centralized training scenarios. Moreover, BANDMF well-suited to federated training scenarios, and improves state-of-the-art there as well. Additionally, the computational overhead of BANDMF is less than MF-DP-FTR, by a factor of l/.. It still has a bx time and space overhead compared DP-SGD, which can be prohibitive for very large models with billions of parameters. This is an interesting and important future research direction.
10

---

Acknowledgement
The authors thank the early feedback and discussion from Natalia Ponomareva, and the support of FL production training from Yanxiang Zhang and Yuanbo Zhang.
References
[1] Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and L. Zhang. Deep learning with differential privacy. In Proc. of the 2016 ACM SIGSAC Conf. on Computer and Communications Security (CCS'I6), pages 308-318, 2016.
[2] Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In International Conference on Machine Learning, pages 32-40. PMLR, 2017.
[3] Hilal Asi, Daniel Asher Nathan Levy, and John Duchi. Adapting to function difficulty and growth conditions in private optimization. In Advances Neural Information Processing Systems, 2021.
[4] Hilal Asi. Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private online prediction from experts: Separations and faster rates. arXiv preprint arXiv:2210.1335 13537, 2022.
[5] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Near-optimal algorithms for private online optimization in the realizable regime. arXiv preprint urXiv:2302.141:: 2023.
[6] Borja Balle, Peter Kairouz, H Brendan McMahan, Om Thakkar, and Abhradeep Thakurta. Privacy amplification via random check-ins. In NeurlPS, 2020.
[7] 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), pages 4644733, 2014.
[8] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pages 11279-11288, 2019.
[9] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint arXiv:2006. 002200000666444 04, 2020.
[10] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. arXiv preprint
2019.
[1]] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Crypiography Conference, pages 635-658. Springer, 2016.
[12] Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing, 16(5):1190-1200) 1995.
[13] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM
Trans. on Information Systems Security, 14(3):26:1-26222) November 2011.
[14] Kamalika Chaudhuri, Claire Monteleoni, and Anand Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(Mar): 10t9-110999 1109, 2011.
[15] Christopher A Choquette- Chho,, H Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. arXiv preprint arXiv:2211.06532 2023.
[16] Rishav Chourasia, Jiayuan Ye, and Reza Shokri. Differential privacy dynamies of langevin diffusion and noisy gradient descent. In Advances in Neural Information Processing Systems, 2021.
[17] Sergey Denisov, Brendan McMahan, Keith Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators on adaptive streams, 2022. URL https: /etess//rxxiiie www.wiiwwgggaaaaaaeeeaaeooe /2202. 02312083122.......
[18) DP Team. Google's differential privacy libraries., 2022, https: https://///ttt.tttte/ee ctw.ttttboooooooo..ooooooooooott cot.:/oglllo/ooooooooooooooooo differential-prie

---

[19] Jeremy Du Croz, Peter Mayes, and Giuseppe Radicati. Factorizations of band matrices using level 3 blas. In CONPAR VAPP IV: Joint International Conference on Vector and Parallel Processing Zurich, Switzerland, September 10-13, 1990 Proceedings, pages 222-231. Springer, 2005.
[20] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proc. of the Forty-Second ACM Symp. on Theory of Computing (STOC'IO), pages 715-724, 2010.
[21] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing, pages 11-20, 2014.
[22] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The Power of Factoriza- tion Mechanisms in Local and Central Differential Privacy, page 425-438. Association for Computing Machinery, New York, NY, USA, 2020. ISBN 9781450369794. URL
https: htt:://oo..org/////
1145/3355771.... 3384297.
[23] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in linear time. In Proc. of the Fifty-Secone ACM Symp. on Theory of Computing (STOC'20), 2020.
[24] Hendrik Fichtenberger. Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation, 2022. URL https: / /arxiv. org/abs/2202. 11205.
[25] Sivakanth Gopi, Yin Tat Lee, and Daogao Liu. Private convex optimization via exponential mechanism. arXiv preprint arXiv:2203.0026. 2022.
[26] Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. Advances in Neural Information Processing Systems, 26, 2013.
[27] Andrew Hard, Kanishka Rao, Rajiv Mathews, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. CoRR. abs/181 1.036044 2018. URL /ttt:://azxtee org/ abs 1 18111 03604.
[28]
Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, 2010.
[29] Monika Henzinger and Jalaj Upadhyay. Constant matters: Fine-grained complexity of dif- ferentially private continual observation using completely bounded norms. arXiv preprint arXiv:2202. 1200, 2022.
[30] James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26 27, 2015.
[31] Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole-Jean Wu, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, et al. Papaya: Practical, private, and scalable federated learning. Proceedings of Machine Learning and Systems, 4: 814-832, 2022.
[32] Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium Security and Privacy (SP), 2019.
[33] Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Proc. of the 25th Annual Conf. on Learning Theory (COLT), volume 23, pages 24.1-24.34
June 2012.
[34] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný. Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Pranceth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu,
12

---

and Sen Zhao. Advances and open problems in federated learning, CoRR, abs/1912.04977,
2019. URL http: /ttpii////aiv.v.///////o/ wwo.oro//aoo... /egg/bbs/at 1912. 04977.
[35] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng
Xu. Practical and private (deep) learning without sampling or shuffling. In ICMI,, 2021.
[36] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1, 2012.
[37] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, aug 2009. ISSN 0018-9162. doi: 10. 10.11099 10.1109/MC.2099
263. URL https: //oii. /tt/ 1109 MMC 200.0009.2.. 263.
[38] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight approximate differential privacy for discrete-valued mechanisms using fft, 2020.
[39] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth erm and sco in sub- quadratic steps. Advances in Neural Information Processing Systems, 34, 2021.
[40] Chao Li, Gerome Miklau, Michael Hay, Andrew Mcgregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24:757-781, 2015.
[41] Zitao Li, Bolin Ding, Ce Zhang. Ninghui Li, and Jingren Zhou. Federated matrix factoriza- tion with privacy guarantee. Proc. VLDB Endow., 15(4)9900-913, dec 2021. ISSN 2150- 8097. doi: 10.14778250555.5505553 URL htt.///ooiooooo/oo// org/ 14778//3787888 3503598.
[42] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Optimizing error of high-dimensional statistical queries under differential privacy. Proc. VLDB Endow.,
1 11(10):120611111 jun 2018. ISSN 2150-8097. doi: 10. 00.14778/3211753.3337766 URL
https://doi.c.. orr./...rr//o 10. 14771/7778/8 3231751 32317699
[43] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. Hdmm: Opti- mizing error of nigh-dimensional statistical queries under differential privacy. arXiv preprint arXiv:2106. 12/18, 2021.
[44] H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private language models without losing accuracy. CoRR, abs/ 2017. URL http: / //rxiiv..o org/ abs /1710. 06963.
[45] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv:/7100069655 2017.
[46] Nya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaus- sian mechanism. CoRR, abs/ 10530, 2019, URL /ecctp://axiie wwg.:iiiiorrreoooooo /aa/ /1908. 10530.
[47] Matthias Paulik, Matt Seigel, Henry Mason, Dominic Telaar, Joris Kluivers, Rogier van Dalen, Chi Wai Lau, Luke Carlson, Filip Granqvist, Chris Vandevelde, et al. Federated evaluation and tuning for on-device personalization: System design & applications. arXiv preprint 102v:2102.08803: 2021.
[48] Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H. Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Thakurta. How to dp-fy ml: A practical guide machine learning with differential privacy, 2023.
[49] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21((40):1-67, 2020. URL
http: / jmlr. org/papers /v21/20 074 47. htmll
[50] Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumnr, and H. Brendan McMahan. Adaptive federated optimization. CoRR, abs/2003.00295, 2020. URL https: http///axivvvv// orq/ / aabs/2003.a 00295.
[51] Hyejin Shin, Sungwook Kim, Junbum Shin, and Xiaokui Xiao. Privacy enhanced matrix factor- ization for recommendation with local differential privacy. IEEE Trunsactions on Knowledge and Data Engineering, 30(9):177--1782 2018. doi: 10. (0.109//KKDE.2018.2883333
13

---

[52] Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? 2017 IEEE Symposium on Security and Privacy (SP), pages 58-77. IEEE, 2017.
[53] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference Signal and Information Processing, pages 245-248. IEEE, 2013.
[54] Shuang Song, Om Thakkar, and Abhradeep Thakurta. Characterizing private clipped gradient descent convex generalized linear problems. arXiv preprint 201V::2000006783, 2020.
[55] Thomas Steinke. Composition of differential privacy & privacy amplification by subsampling, 2022.
[56] Maxime Vono, Nicolas Dobigeon, and Pierre Chainais. High-dimensional gaussian sampling: review and a unifying approach based on stochastic proximal point algorithm, 2021.
[57] Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey F. Naughton. Bolt-on differential privacy for scalable stochastic gradient descent- based analytics. In Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu, editors, Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD, 2017.
(58) Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher Choquette, Peter Kairouz, Brendan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of gboard language models with differential privacy, 2023.
[59] Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher A Choquette-Choo, Peter Kairouz, Brendan McMahan, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of ghoard language models with differential privacy. arXiv preprint arXiv:2305. 18465, 2023.
[60] Linting Xue, Noah Constant, Adam Roberts, Mihir Kale, Rami AI-Rfou, Aditya Siddhant, Aditya Barua, and Colin Raffel. mt5: massively multilingual pre-trained text-to-text trans- former. arXiv preprint arXiv:2010. 1194, 2020.
[61] Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ramage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv: 2018.
[62] Ganzhao Yuan, Yin Yang, Zhenjie Zhang, and Zhifeng Hao. Convex optimization for linear query processing under approximate differential privacy. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2005- 2014. 2016.
[63] Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konečný, Andrew Hard, and Tom Goldstein. Diumal nocturnal? federated learning of branch networks from periodically shifting distributions. In International Conference on Learning Representations, 2022.
14

---

A
Notation summary
Number of steps of the streaming linear query (SGD steps FL rounds)
m
Total number of records (examples or users) in the database/dataset
b
Minimum separation between participations; b allows participation in every step
6-banded matrix
A (general) matrix X is b-banded if for all i, [m]]. ji- 2 6 implies [i.)] We use refer to min-separation, and for example write b-banded when we set the number of bands equal to the min- separation; we use b-banded for number of bands possibly different than b.
k:
The maximum number of times any user might participate in training
Dimension of per-step user contributions (e.g., model size)
x, or Idd
Sum of per-example gradients (or per-user model updates) on step i
Raad
Stream of inputs x,, equiv. matrix with x; (so X; x(s:]) Clipping norm that limits the size of per-example contributions X Participation pattern, the set of steps that example participates in Participation schema, set of sets of steps (set of all π) example could participate in
<
s [m]]
II
(x x (x, x) E N), the set deltas between neighboring input streams
D
Corners of D when assumed to be polytope, 2 conv participation schema II with at most k participations, separated by exactly b steps
(k.bb--paticiipation
b-min-sep amii--ep-participane sep-participation
Relaxation of of (k, particciipatio where participations have separa- tion at least b
A e R
Lower-triangulan linear query matrix to be factorized as A = BC
M
Moore-Penrose pseudoinverse of matrix M
M
Transpose of M
[
The (i,j)th th entry matrix A
M and M
The thh row and jth column of M (numpy-styr style indexing) Convex hull of the set
conv (S)
[n]
(l....,n}
|
The Frobenius norm of matrix X
Table 1: Summary of notation
A.1
Intuition behind ME-DP-FTRL
Fig. 7 compares DP-SGD and MF- MF-DP-FTRL. To gain intuition for why MF-DP-FTRL can perform better than DP-SGD, observe that vanilla SGD has iterates 0, Og -1 Σt= &;, and hence when the noisy gradients &; are added, the C-1 [(.)] terms MF-DP-FTRI. serve to cancel out some of the noise introduced on previous rounds. The noise cancellation reduces the total error in all the prefix sums of gradients Σi_1 &; for [n]]. but also worsens the privacy guarantee of the mechanism, iee. increases its sensitivity. The privacy worsens as e.g., adversary trying to learn X via x; can partially learn the value of 2; from X2, whereas DP-SGD x and X; are uncorrelated. Hence there tradcoff between the total error and sensitivity (see next paragraph): DP-SGD sets C7,) 0
15

---

DP-SGD
MF DP-FTRL
betch
cipped bailsh gradient
mechanism cutput
clpped batch gradient
mecharism oulput X;
18 1a Sal
Gaussian Mach
Xi
X)
X]
80
BD
MF Mechanism
2
Gaussian Mech
X2
+
X2
(statefid rounds)
+ C7/
K19
6DD
+
X3
Gaussian
Mach
Xy
1.D
+
X
Figure 7: ME-DP-FTRL (Alg. 1) enables noise cancelling across steps, where DP-SGD does not. The entries J are mostly negative (in [0, (1)) in matrices C-1 we consider (see Fig. 8). Thus, the red terms show that MF-DP-FTRL "cancels out" noise added on earlier iterations. For simplicity, we assume C-1 has 1s the main diagonal and entries Ci. otherwise, with z, [[,:]
the rows
below the main diagonal, effectively minimizing sensitivity (assuming a fixed normalization of the main diagonal). but with a large total error due to no noise cancellation. On the other hand, MF-DP-FTRL can arrive at a better compromise between mechanism sensitivity and the total error. This is formalized in the optimization problem of Sec. 4.
Without a sampling assumption, the implied DP adversary knows which examples participated in batch S,, and for DP-SGD with uncorrelated noise, knows they only need to "attack" &, However, with MF-DP-FTRL, the information from S; can potentially be masked with larger amount of initial noise in &; which is then canceled out over subsequent rounds. "Spreading out" the release of information about batch S; over a larger number of iterations in this way can intuitively provide better privacy, while still allowing for accurate partial sums of gradients (and hence SGD iterates). This is, in loose sense, similar to the way SGD with sampling "hides" information about a particular example at randomly chosen iterations.
B Dropping the diag (X) constraint
As discussed in Sec. BANDMF by default imposes equal column norm constraint the generated factorization. In the optimization problem, this is accomplished by imposing the constraint diag (X) 1. In this section show how we can solve the optimization problem without this constraint for (k, 6) parrtiicipaiion This optimization problem is f'ormulated to minimize total squared error with respect to (k: b) participation, although principle the optimized matrices could be used in the b-min b-min-sep tmii--ep-paat sep-participation setting with some degradation in solution quality. Prop. B.1 provides an expression for efficiently computing the sensitivity of b-banded matrix.
Proposition B.1. Let X e S be a b-banded matrix, and let denote the (k, b) parrticiipanion schema. Then
sensm X)
max == 1=1.....
Σ diag (X) (X)
To integrate this expression into the optimization problem, we can replace the diag (X) = 1 constraint with linear constraints on diag (X). This modification does not affect the convexity of the problem, although it does slightly complicate the algorithms needed to solve it. To handle this new problem, our approach is to replace the gradient with respect to X at each iteration, with projected gradient, which is obtained by setting is Σý= diag( (AX s+ for all 1...., b, and setting diag( AX))+5bb diag( (A)) "1/k. This ensures that sensitivity does not change between iterations of the numerical optimization procedure.
For the reasons mentioned in Sec. 4, by default we impose the simpler constraint diag (Xa ) 1. In App. C. we provide some numerical comparisons between these two approaches. Specifically, the rows of Table 2 with Equal columa norms? (F)alse correspond to the approach described here; observe this results in slightly improved RMSE under (k: b) paartiiccintnonn compared the corresponding with Equal column norms? (True.
16

---

Matrix
Sensitivity
Error
Equal colum norms?
(k==6, 4= [15]
(A) RMSE under (l==6, b- [15]
(B) RMSE under
62342- U2342-minn-o 1----in--aa sep
62342- 1-2--in--a- sep (Ours)
Mcchanism
Bands i
k=1 [17]
(Ours)
(Ours)
OPTIMAL TREEAGG [30, 35]
0.32
1.00
1.00
1.53
1.53
DP-SGD [1]
1
T
0.41
1.00
1.00
9.63
9.63
(b=128) (Ours)
128
0.52
1.00
1.04
1.23
1.29
MF (4=128) (Ours)
128
T
0.41
1.00
1.00
1.27
1.27
(4=342) (Ours)
342
0.52
1.00
1.04
1.04
1.08
MF (b=342) (Ours)
342
T
0.41
1.00
1.00
1.05
1.05
[15]
0.50
1.00
$1.15
1.00
1.15
MF [15]
T
0.41
1.00
$1.13
1.01
1.14
Table 2: comparison of matrix mechanisms for n. 2052 under different participation pat- terns. Banded matrices are near-optimal under (k, particiiaiiio and best under b-min-sep- participation. Each error computed under the indicated measure of sensitivity. Thus, the error in column (B) can be obtained by multiplying the error in column (A) by the corresponding entry under 62342 sensitivity.
C Empirical evaluation of banded matrices
Table 2 compares the matrix mechanisms studied under different participation patterns normalized to have sensitivity sens( C) under (k=6, participation & is lowest as expected. With column normalization, sensitivity is also under mep--sep-pparrcipaatioon. We make the following observations:
The sensitivity under single
For the MF mechanisms, column normalization hurts RMSE for (k, parttiicipaaionn com- pared the approach of App. B (as it is additional constraint), but actually improves RMSE under b-min-sep-parteeeee -imii-se--partccpaatoon participation.
We conjecture that the (k, b) parrticipation optimized matrices (MF without column nor- malization, App. B) are optimal for the prefix-sum workload With this in mind, we see there is at most a small increase in RMSE for switching to the more challenging b-min-sep- participation schema (1.00 1.05). (as we further conjecture) the optimal matrices for prefix-sum in fact are k h-banded, the gap is even smaller (at most 1.04 - 1.05). Hence, at least for the prefix-sun workload A, there limited room for improvement in develop- ing optimization procedures that directly optimize over the larger feasible set offered by penii--ep-participattie
Using fewer than b bands does degrade performance on the RMSE metrie, with DP-SGD being the extreme case, yielding prefix sum estimates almost 10x worse than the MF mechanisms.
The results of Denisov et al. [17] imply that the binary-tree C matrix can in fact be used in the online setting, with the Monre-Penrose pseudo-inverse giving the optimal decoder for RMSE [15], corresponding the 'full' estimator of Honaker [30]. We include this in the table as a baseline, and see that it is in general outperformed by our MF mechanisms by about 1.5x in RMSE.
*This conjecture is not trivially true, as we still enforce a non- negativvty or orthogonality constraint; see Choquette-Chrr Choo et al. [15, Appendix 1.3). Hence the conjecture is that these constraints are already satisfied by the optimal matrix for this workload.
17

---

D Example structures of MF
Figs. 8 and 9 show the structure of some of the key matrix factorization approaches considered in this work. One can immediately see the impact of the (k: b) partiicipation schema in the optimal matrices, in particular for the con-banded MULTI-EPOCH MF matrices (the top-right matrices), where C contains diagonals of negative entries separated by b steps. In the bottom two rows, we see that requiring equal column norms ("EN-" for equal norms) has relatively minor impact on the structure of the matrices.
Single
(k-c)
03
36
0.1
-1
64
64
[K-BI opech MF
1.0
1.5
16
16
00
15
1.6
0.6
0.0
32
0.4
48
-0.5
02
1.0
0.
4.5
2,-4, EN-Band MF
[K-4, b- BJ Band MF c
(6- b-15] El--Badd MF
[k-4, &mm 16) Bund MF
32
02
32
32
0.2
48
-0.1
48
4B
6.1
54
3.0
0.0
64
0.0
0.0
16
36
32
32
48
64
16
32
4,
(t-4,
16
16
64
64
Figure 8: Factorizations for n2 64 of the prefix-sum workload (A taken to be the lower- trianttra matrix 1s). For each factorization BC, we show and its inverse C-!. as the inverse the matrix used in noise generation. Single-epoch is the approach of Denisov et al. [17], SGD is simply the identity matrix I (shown for completeness), and (k=8)-epoch MF and (A=4)-epoed are the MULTI-EPOCH: MF approach of Choquette- Chattee--hhoooo et al. [15] for and 4 epochs, respectively. For banded matrices (3rd and 4th rows), fix 4 epochs (b 16), and show i=8 and b=16 bands, with column normalization ("EN-") and without.
18

---

Optimal TreeAgg C
1.0
Optimal TreeAgg C
0
0.50
0.8
16
16
0.25
0.6
32
32
0.00
0.4
48
48
0.2
0.25
64
64
0.0
16
32
48
64
80
96
112
128
0
16
48 64
80 96 112 128
Figure 9: The transpose of binary-tree encoder matrix Cr, and its pseudoinverse C.y, which corresponds to the "full" or optimal decoder of Honaker [30]. This is the matrix used in OPTIMAL TREEAGG in Fig. 6[a].
E Algorithms and Analysis for Sec. 3
E.1
Algorithms
Algorithm (VECSENS): Maximum of (v, u) where is vector in the too unit ball satisfying IIg Inputs: min-separation b, vector v, max participations k Initialize F Runk for m = 1,...,k k do for i n,..... do
We use the convention that F[s,t] t] 0 s, are out-of out-of-bounds. m[i max (v: + Fli b, 1J, Fli 1, 1,ml)
return [[],k]
Algorithm 4 Efficient sensitivity upper bound for caain-sep-parttcipattio
Inputs: min-separation b, matrix X, max participations k Initialize F' 1i v 1?
for j = I....., do Vi VECSENS(b, X (c)
return VECSENS b, k,
Algorithm 5 Efficient sensitivity calculation for catn---sepppattiipttiion assuming X is b-banded. min- min-separation b, b-banded matrix X, max participations k. return / /VEcSENS(b,, diag(X),4)
Inputs:
E.2 Analysis
Proposition E.1. The sensitivity of C for given participation schema II may be expressed
sensiT (C)² max tr ([P,CTCP.. well nES
where P., represent the axis-aligned projection the set of rows indexed by that is, P i] = for i E n, and otherwise. Assuming that D represents a set of matrices with rows bounded by lo norm 1, this can be upper bounded by:
max [
wEll J.
where C. C. This upper bound tight when PPCCPP 0V and is independent of the dimension d of the rows of
19

---

Proof. Recall that II determines the rows of u which may be nonzero in the definition Eq. (2). Take some D, an element IR Rxx which therefore has nonzero rows only some set of indices NT.oote, clearly u u. P Px. and P P.Px.
Therefore
Cull = tr ([CPP,.)) ( =r PP C'CP (P,,C
(8)
=tr (tr((P C CP, [um"])
This implies the statement Eq. (7) by the definition of sensitivity and neighboring in our setting.
Now, let X == P&C* cP be the matrix formed by zeroing out the rows and columns not indexed by from X. Assume that every u D has row norms bounded by Expanding the trace in Eq. (7),
writing zij for the elements of X, and [ia:] for the jth row of u, we have
k (
tr x uu
Σ
3 Tig (ura)) U[a-)) s
Digl
[=1=1
which yields the claimed bound. When X, is elementwise nonnegative, taking Upa.] U[a:] for any unit vector shows the claimed tightness in this case.
Remark. This statement can be viewed as a partial extension of [15, Theorem G.I]. J. does not imply every case handled there, but also implies results which cannot be derived from that Theorem.
Proof of Thm. 2. Conclusion (1) is implied by (2), noting that the conditions on C imply that Alg. will return a value at most kv k in this setting,
For (2), let R" with entries c; [[.gg]] for i {0,...,, -
13. We have
sens (C)
max [Cu(T) max xell,
E SEA
Σ SEST
C4
well,
well,
where u(T) 10, is given by u(T); if and otherwise. The last equality follows from the orthogonality condition on sufficiently separated columns of C trivially implied by bandedness. It is straightforward verify the dynamic program of Alg. 3 constructs feasible which attains the maximum.
Proof of Thm. 3. Via Prop. E.1, the result follows from showing that Alg. 4 outputs a value least as large as E(t,))ex [ for any II, So let म be an element of HIg Note that VECSENS is monotonically increasing
values of the vector if v nonnegative, and therefore Alg. 4 is monotonically increasing in absolute values of X. Therefore we will have our conclusion (3) if we can show that, for X; the matrix formed by zeroing out all rows and columns of not indexed by ft, Alg. 4 returns the value E(is)er Xx,].. Yet this is straightforward by the characterization of VECSENS an oracle for computing the maximum of (v, u), where is vector in the too unit ball.
Proof of Prop. 4.1. The proof will be constructive. Let J be the exchange matrix defined
J
Let Y JXJ and note that Y symmetric and positive definite. Let Cholesky(Y)" and note that (1) H'H = Y by definition of Cholesky decomposition, (2) H is upper triangular, and (3) H is b-banded by Du Croz et al. [19].
20

---

We will show that for C = JHJ, we have (1) X CTC, (2) C is lower triangular, and (3) C is 5- b-banded.
For Claim (I) observe that:
C' C - (JHJ) (JHJ)
(JHJ)
= J'H
J(H H)J
=JYJ
= JJXJJ
X
For Claim (2) and (3), note that left-multiplying by reverses the rows and right-multipliing by reverses the columns, and therefore C(a,]] = Hn-ittnn-j+1
For Claim (2), we need show Cta 0 if j. If < then n n-in 1, and since H
upper triangular, we know H [x-i+1,8-++1] = 0, desired.
For Claim (3), need to show that C(.J] 0i [i b. Observe that (n---rittii |i-j] and therefore since H is b-banded, so is C.
This completes the proof.
F Additional Analysis for Sec. 5
In this section we prove our general amplification statement Theorem 5, of which Theorem 4 is corollary. Recall that we use instead of in this appendix since our sampling scheme enforces (k, b) particciiatoo Throughout this section, we slightly abuse notation by letting i (mod b) = instead of i/b integer.
F.1 Algorithms for Sampling
We first give the general sampling scheme (Alg. 6) well as sequence of queries (Alg. 7) that provides an upper bound on the privacy guarantees of DP-MF using this sampling scheme.
Algorithm Sampling scheme for banded DP-MF
Inputs: Dataset D, sampling distribution over ()(* noise standard deviation o. Di,..., Dr + arbitrary partition of D such that Vj |D,l m. Let D,
for each j.
for j -.. b do
Sample l sets index D, as (S,; ( ((k-))6))) ~ S, with S s [m]]
for i 1;,,,...,, do
Let jetji (mod b); compute x, by querying (dj, : E {.).
Let [x.....x,) x,," nxd release Cx with each entry of [[i,]] NN0,03).
> is lower-triangular, results can also be released in streaming fashion
Algorithm 7 Sequence of queries that bounds privacy of Alg.
Inputs: Dataset D (d1, d2....,.,dap d sampling distribution S over (
Sample ......... S₁) S.
for = 1,2,... k do
D, + (dy j
Perform (adaptively chosen) sensitivity A query on D, with noise o²)
21

---

Cx
Independent of D
j
Query on examples in step
b+j
Query on examples in step b+j
2b+j
Query on examples in step 2b+j
3b+j
Query on examples in step 3b+j
b+j 2b+j
3b+j
Figure 10: A visualization how we can decompose a banded matrix mechanism into independent queries on Dj (as in Alg. 7) under our sampling scheme.
F2 General Amplification Statement and Proof
Given the sampling scheme and query sequence, we can now state our general amplification statement: Theorem 5. Suppose C is b-banded and lower triangular, and the examples participating in each step are chosen according to Alg. 6 with given choice S. Then BANDMF satisfies any standard DP guarantee' satisfied by Alg. in App. F.l with maX4e[n] same choice S.
[Ce:l2 maX4e[1]
v VXi, and the
Proof. Consider two datasets D, D' that differ by an example contained in the partition subset Dj- We argue about the privacy of Cx z. For simplicity we assume is such that (k: 1)b j n; elements in Dj such that j does not satisfy this condition can potentially participate instead of k and in turn the privacy guarantee we can prove for these elements can only be stronger.
times
Since C is b-banded, can partition the of C into k subsets
R2, Rotj R2b+5 ... R(I-1)b+j: RR.
where Rí (resp. Rotj: Rab-j.. non-zero, and Rg = [n] x (R, u Rots U...). i.c., Rg are the rows not included in any of these sets, i.e. rows of where entries j. b j.... are all zero. The fact that lower- triangria and b-banded ensures that these subsets do not overlap, i.e., this is valid partition can be observed in Fig. 4.
()k+)))+)) denotes the set of rows in C for which the jth entry is
Let CR denote C restricted to the set of tinguishing D from D', each row of (Cx + 2) Rg = CR + ZR has a distribution indepen- dent of whether D D' was used. So it suffices to give privacy guarantees for outputting only (Cx + 2) R,, (Cx + 2.) BR,,)..., + z) R
in R. From the perspective of adversary dis-
We can decompose rows R, of Cx + follows:
(Cx+ (Cx+z)R; CR,x+ +R, CR, CR,X-j+ZA
(10)
Where x, denotes x with all rows except j zeroed out, and x denotes xj, i..., with row zeroed out. By the b-banded property of C, CR, x.j has 0 sensitivity to the examples in D& Dj. Then,
Standard DP includes c-DP,
Rényi DP. zCDP, and Gaussian DP.
22

---

by Eq. (10), for i Rg, we observe that the ith row of (Cx+ ()x+ Z)R, corresponds to an (adaptive) query made with fz-sensitivity e Ce, to the examples used in step j. i.c., those given by D, and Sj. and noise N(00.2)) So (Cx+ z) corresponds to sequence of adaptive queries on the examples used in step J. and answering this sequence of queries satisfies any standard privacy guarantee satisfied by answering single (scalar, adaptively chosen) query with sensitivity |Cez]l2 2 to the example chosen in step and noise N o0) by Claim D.I in [17].
The same logic applies to each of (Cx z) Regg...., (Cx 2) Rea- Putting it all together
and taking& max over the sensitivity of the individual queries, releasing Cx z satisfies any standard privacy guarantee satisfied by answering adaptively chosen queries, with sensitivity max Ceall2 the examples used in steps j, j...., (k 1)b + respectively. This is exactly Alg. 7 with the specified choice of A,
F.3 Corollaries of Thm.
We give here several corollaries of Thm. 5 that are interest.
Note that when b= 1, the partition contains a single subset, i.e., is the the entire dataset. In particular, in this setting Thm. 5 recovers the privacy guarantees of amplified DP-SGD under any amplification scheme, e.g. including the ones discussed below.
Equivalence to DP-SGD:
Amplification via sampling: To recover Thm. 4 from Thm. 5, we take the distribution over 2[th] corresponding to the uniform distribution over subsets of size B, and let S be the product of this distribution with itself times. This is equivalent to the following: in step i, we include each element of Dj (mod 6) independently with probability q. For this choice of S, Alg. 6 reduces to Alg. 2 and Thm. We next make the amplified privacy guarantee explicit terms of the dp ap_aacount ing Python library [18]. Given n, m, b and target per-step batch size B, could write a accaccuunttici ing. DpEvent capturing the privacy guarantees of the matrix factorization mechanism as follows:
Example F.1
gaussian_event = dp_accounting, GaussianDpEvenn (noise_multipliee q B / math. floor / b)
sampled_ _eent dp awc.ccccinnnnn wowsssonsammmmeeeeeeeeeaee.
q, gaussian_evenn
composed_ event dp_accounting Sel FComposedDpEvent sampled_event math. ceil (m b)
Example F.2. To give an example of the amplification guarantee, for simplicity assume n/b, m/b integer. If all column norms in C are 1, each of x has sensitivity 1, and each entry of has standard deviation o, then oulputting Cx + z satisfies (a, 20 -RDP.
Using Theorem 11 of [46] and Thm. foror appropriate choice of a and q. this improves to (a,q² 22.20 )-
RDP with amplification by sampling. In particular, if we have a target per-step batch size B, then should choose g Bb and if this choice of satisfies the conditions in [46] plugging this in gives (a, 2aB²bn
8mm RDDP. Notice that b = 1 recovers the privacy guarantees of DP-SGD with sampling probability B/m, and this privacy guarantee weakens as b increases.
Amplification via shuffling: Fix per-step batch size B. Then, suppose we shuffle the list of examples, and cyclically iterate over batches of size B in this list as the sets of examples to use in each step of matrix factorization. That is, we shuffle D into ordered list d, dg...., and in step i use examples d(t-1)B-1 (mod m) d(i-1)B+2 (mod m):.... ..... diB (mod m).
For simplicity let's consider the case where mB(Bb) is integer. In particular, this means in this shuffling scheme, each example appears once every m/ B steps, and for each of these steps i, i (mod b) is the same. Then this shuffling scheme is equivalent to the following: First, rather than choose arbitrary partition apply Thm. 5, we choose uniformly random partition into b subsets
23

---

of size m/b. Then, we choose S to be the distribution giving by shuffling [m/b] and then cyclically iterating over the shuffled list in batches of size B. Given this equivalence, we get the following:
Corollary F.I. Suppose the examples in matrix factorization are chosen by shuffling D and then iterating over batches of size B. If (n((B) is integer, then the matrix factorization mechanism satisfies any standard privacy guarantee satisfied by k adaptive scalar queries with sensitivity maX[[[]] Ceull2 and noise N NO,,0* o²), with the examples in each query given by shuffling dataset of size m/b and cyclically iterating over this list in batches of size B.
Example F.3. Consider the simplified case where m n, we choose a random permutation n, and in step i query example dz((). In this case, if all the column norms of C are 1, x's rows have sensitivity 1, we get that Cx+ z satisfies (c. -).P With e.g., the amplification for shuffled (t, -DPP mechanisms given by Theorem 5.1 of [6] and Cor. F.I, if e a constant, we instead get that Cx + z satisfies (e.0( (1ng(1/6)
vin(1/8)
and z 's entries have standard deviation o =0
8 O n 1/6) -DP.
F4 Optimizing the number of bands
Let oe,s(b) be the required Gaussian noise magnitude for b-banded MF run for iterations using e.g. Alg. 2 to achieve (e, 5)DP with per-step batch size B. Then, the expected total squared error introduced while achieving (e, 6)-DP with amplification can be calculated as
σe,6 (bb),, .C.)
where Cj is b-banded lower triangular matrix optimized via Problem 2. Generally, smaller values of b will allow for more amplification, and hence a smaller σ; however, this introduces a stronger set of constraints on the optimization problem, likely increasing the L term. Hence, the choice of b should be optimized. Fortunately, de,s(-) can be computed efficiently: Thm. 4 implies a procedure to compute e given a, 5, b, and then one can use binary search 10 and this procedure to find the o giving a desired e. In addition, one can pre-compute the optimal matrices C. for different numbers of bands. The search can be restricted to be (1, (1,2...., on n) since for b= = m we have |D}| B, i.e. Alg. 2 and Thm. 4 provide no privacy amplification.
B
B
Unlike the un un-amplified version of MF, now the best factorization depends on the privacy parameters de, The benefits of amplification are generally stronger for small e: For example, amplification by sampling with probability p roughly improves e to log( + p(e" 5 1)) (see e.g. Section 6 of [55]), which is approximately pe for 1, and approximately c- (1/(1/p)) ef 1/p. Hence, with smaller values of c, we expect the benefits of amplification to outweigh the benefits of correlated noise, in which case b = will be optimal. With larger values of e, we expect the benefits of correlated noise to outweigh the benefits of amplification, and in this regime b = n will be optimal. For moderate values of e, we expect the optimal b be somewhere in the middle.
E,5 Applying BANDME with Privacy Amplification
Consider the setup of Sec. with our CIFARI 10 setting described fully in App. H. As mentioned in that section, we use the convention that our privacy analysis will assume Poisson sampling, even though we are using passes over a shuffled dataset. We have m = 50, 000 and train for = 20 epochs with a batch size B = 500. Choquette- Chho et al. [15] lets bound the sensitivity and optimize matrices for this setting, however, without privacy amplification. Suppose we choose i 100. Because m/b = 500- B, we get that the sampling probability is 100% (see Example F.1) and thus get no benefits from amplification. For all b [1,100] we get amplification benefits which can be seen intuitively as follows.
i = 2, we get that there are two partitions D1, Dz. Then or first event will be the simultaneous release of X2, our second of x3, X4, and so on. Because each partition is of size DD m/b = 25, 000 and B- 500, we have a sampling probability q = 2%. Given our parameters, we also have d= = kmmm B = 2, 000, and so we must compose d/b- = 1, 000 events (as seen in Example F.1). Because in this setting each event is the batch release of steps of x, where each example participates at most
See for example the calibrate dp mwchanism function of DP Team [18].
24

---

once on each release, observe that we need only normalize the sensitivity of this mechanism under (A: = 1,b b= 2)-aaticcipation Generally, as increases we have higher sampling probability, but fewer events to compose, and vice versa. As can be seen, when i this reduces the standard accounting for DP-SGD. It can also be seen that we desire each Dj to be a non-overlapping partition of D. otherwise, single example may participate multiple times in the same event (and thus have a higher sampling probability).
G Additional RMSE Experiment Details
G.1 Optimal Number Bands
In this section, provide supplementary data surrounding the RMSE experiments in Fig. 5. Table shows the optimal number of bands for each (c, k) pair considered in the RMSE experiments. shows the general trend that decreases, & increases, the optimal number of bands decreases.
G.2 Explaining many-epoch setting
Observe in Fig. 5 that as BANDMF and MULTI-EPOCH MF incur similar RMSE as DP-SGD when the number of epochs increases.
This phenomenon occurs because the number of epochs changes, does the sensitivity of the X matrix, and subsequently the geometry of the optimization problem. By Eq. (5), we see that sensitivity be calculated where single user might participate. As the number of epochs increases, the number of entries of X that we have to sum up also increases. turns out that under the constraint of constant sensitivity, it is better to put more weight on the diagonal of X than the off-diagonal. This is an observation have made by solving this optimization problem numerically in a number of settings. Hence, as the number of epochs increases. X becomes more and more diagonally dominant, making the mechanism closer DP-SGD (X Identity).
sum of absolute values of entries of X corresponding iterations
c/h
4
8
16
32
64
128
256
512
1024
0.03125
1
1
0.0625
4
2
1
1
1
1
1
1
0.125
8
2
1
1
1
1
0.25
8
4
2
1
1
1
1
0.5
16
4
4
2
1
1
1.0
32
16
8
4
2
2
1
1
2.0
64
32
16
8
4
2
2
1
4.0
128
64
32
16
8
4
2
2
8.0
1024
512
256
32
16
8
4
2
16.0
1024
512
256
128
64
32
8
4
2
Table 3:
Optimal number of bands for each (c, pair, when 1024 and 8= 10
H Additional CIFAR-10 Experiment Details
H.1 Setup and Tuning
We tune all jobs on learning rate grid of coefficients in (1, 2. 5 on powers in [-2, 3]. We find that no momentum works best for DP-SGD and momentum=0.95 works best for ME-DP-FTRI mechanisms on average in tuning; though initial tuning found that tuning momentum well could lead to slightly better results at some budgets, we found that more refined grid of learning rates nearly always led fixed momentum being optimal, and so we fix this parameter. cooldown to 0.05x the initial learning rate over the last 500 steps of training improved all runs and so we fix this parameter. models trained for 20 epochs on CIFAR1O with batch size of 500. We repeat each setting 12 times and show 95% bootstrapped confidence intervals.
also found that a learning rate
25

---

H.2
Additional Figures
Ratio of Banded MF Errar with DP-SGD
Ratio of Banded MF Error with Op tptiial MF.
2.00
20.0
2.00
15.0
15.0
10.0
1.75
10.0
1.75
3.6
1.500
3.6
1.50
Optima
Privacy Budge:
3.2
1.225
Banded MF Better 8
3.2
1.25
2.5
1.00
2.5
1.00
2.3
2.3
2.1
0.75
2.1
0.75
1.2
1.0
-0.50
1.0
-0.50
0.5
0.5
-0.25
0.25
0.01
0.00
0.01
0.00
81
96
91
96
96
Number of Bands,
Number of Bands,
Figure 11: On CIFAR-10, BANDMF is at least as good as DP-SGD across all e, and often signifi- cantly better. BANDMF better than the prior MF-DP-FTRL from Choquette- Choo et [15] up to 5. We compare the ratio of the total enrrr (see Sec. 4) of B BANDMF with either mechanism. Lower values indicate that BANDMF is better. The yellow markers indicate the best BANDMF mechanism that was better for that budget if one existed. Unlike in Fig. 5(b), We only optimize the Band MF over E [0, n/k] which leads to regime around 5 where the it performs worse than the Multi- -ulti-epoch MF of Choquette-Cun Choo et al. [15].
55
DP-SCD, ampl
Mechanism
75
==z,, Nonprivate Baseline
Multi-epoch Mr. ampl.
Test accuraty 1960
(Band) ampl. (Curs)
40
30
20
Privacy budgel 6--
Privacy budget &u 10-
Figure 12:
Our banded matrices consistently perform at least as well as the best prior method observe significant utility benefits from the banded mechanism
in each range of e. Around around 2 percentage points over DP-SGD. We only optimize the Band MF over b [0, n/k] which leads to a regime around
where the it performs worse than the Multi-epoch MF of Choquette- Choo et al. [15]; i is equivalent to this approach modulo the sensitivity definition which we exclude emphasize the regime we improve on. Empirical setup App. H.
I Additional StackOverflow Wext-Word-Predictie Experiment Details
We follow the experimental setup for StackOverflow NWP from Denisov et al. [17] and Choquette- Choo et al. [15]. Except for SINGLE-EPOCH MF (which uses B 167 clients/round for epoch), all privacy guarantees and accuracy results are for epochs of training using 1000 clients/round for 2052 rounds (also I epoch). The matrices used in these experiments are included in Table 2.
For computational efficiency in estimating model accuracy given privacy guarantee, we actually compute in simulation updates from only 100 clients/round, and scale the noise multiplier by corresponding factor 1600
100 for SINGLE-EPOCH MF). This approach 100 for epoch experiments, 167
has been used previously [35, 44], and we independently verified has negligible impact on the estimates of accuracy figures we report. Tables and include the unscaled noise multipliers a for experiments.
26

---

RMSE prefix sum estimates predicts optimal server
Gradient arrers less predictive of good learning rates.
2.59
sever learning rate
1.0
learting rate
1.0
Ringle-eochh
Theelgg
0.345
Mulii coochh-oochhio
Mr. b- 542 (Duns)
0.12
0.12
1.0
2.0
0041
0.041
4.0
0.0
0.14
0.314
10nd
10a1
10aa
10nd
10-1
Effective prefie-sum RMSE during training
Effective gradient RMSE during training
Figure 13:
Correlation between optimal server learning rates 7) and the effective RMSE during training, see Eq. (11).
Optimizer and learning-rate tuning For all SO NWP experiments we use the FedSGDM opti- mizer [50]. This optimization approach first takes multiple local SGD steps (with learning rate 1.0 in our experiments) on the training data of each user in the batch (cohort) before clipping to Ç 1, summing, and passing the result x; into the DP mechanism which adds noise CC'z|raa IR on each iteration i. The resulting privatized sum is then divided by the batch size B and passed to the "server" (post-aggregation) optimizer. in our case SGDM with momentum parameter = 0.95 and learning rate Tis We find tuning 1/s depending on the noise level is critical. By using the computationally efficient approach mentioned above, we were able to conduct rigorous tuning over a learning rate grid of 1.7' for powers i in {-9..... 4}, estimating good initial guesses based prior work. Table 6 gives the full set of results, and Fig. 14 shows convergence as a function of the number of rounds (iters).
Learning rate warmup and cooldown Denisov et al. [17] found learning rate cooldown was effective, and Choquette- Choo et al. [15] found that zeroing-out client updates with large &oo norms was critical to stability in early training. We find that additionally introduing a learning-rate warmup schedule reduces the need for this zeroing-out (though we still enable it), and generally decreases the variance in training results. Hence, all of our experiments (for all algorithms) using linear learning rate warmup from 0.05%, to 1 1.01,, over the first 15% of rounds (309), and linear decay from 1.0m/, to 0.05m, over the last 25% of rounds (513).
Using RMSE to tune optimal server learning rates Fig. 13 plots the server learning rates ny from Table on the y-axis (with the optimal rates shown as larger symbols, and sub-optimal rates as small symbols, versus two different measures of the error for the DP mechanism on the x-axis: The left plot gives uses the effective prefix-sum RMSE (the objective we use for optimizing (banded) matrices C).
(Mechanism error) x noise- mwliimpiirr/ciiintss--rrreee
= VC(SC- CC/nxx/f
(11)
where S is the prefix-sum workload (lower-triangular matrix of ones) and a and are as given in Table 4. The right plot uses the RMSE in error of individual gradients, computed by replacing the L term in the above with C(IC-) C) where we take the workload A to be the identity matrix rather than the prefix sum matrix S.
We see a strong linear correlation between the prefix-sum RMSE and optimal learning rate the left plot; this does not hold for individual gradient enrors (right plot). Based on this, we use the following linear regression to choose learning rates for the non-federated (amplified) SO NWP experiments (still rounding to the nearest 1.7 for consistency):
log(n.) = -0.95 (L. - 4.64
This allowed us to estimate learning rates for the amplified experiments with a high degree of accuracy; Table 7 gives the final selected learning rates.
27

---

1=10
2.0
smoothed
Valrdatoon
14
2-4
Mochanism
24
Single epoch
Optimaa Treskgg
M. ti-epoch MF
Band MF. 342 (Ours)
1.5
Velidatonn
3.0
4.5
20
Validation
1.
1500
2000
250
1250
2000
Bar
Figure 14: Convergence plots for all cross-device federated learning simulation experiments.
28

---

Mechanism
clients per round
noise
Eval Accuracy (%, Smoothed)
Test Accuracy
B
mult.
1/
(%)
DP-SGD
1000
4.22468
0.0244
16.82
16.69
Single-epoch MF
167
4.22468
0.1197
20.29
20.44
Optimal TreeAgg
1000
4.22468
0.2035
21.15
21.25
Multi-epoch MF
1000
4.76079
0,2035
21.96
21.92
Band MF (Ours)
1000
4.22468
0.2035
22.12
22.05
DP-SGD
1000
2.23048
0.0414
18.70
18.42
Single-epoch MF
167
2
2.23048
0,2035
21.66
21.70
Optimal TreeAgg
1000
2.23048
0.3460
22.52
22.59
Multi-epoch MF
1000
2
2.51352
0,3460
23.15
23.04
Band MF (Ours)
1000
2.23048
0.5882
23.31
23.19
DP-SGD
1000
1.19352
0,0704
20.07
19.81
Single-epoch MF
167
4
1.19352
0,3460
22.94
22.90
Optimal TreeAge
1000
1.19352
0,5882
23.66
23.62
Multi-epoch MF
1000
4
1.34498
0,5882
24.19
24.02
Band MF (Ours)
1.19352
1,0000
24.35
24.16
DP-SGD
1000
0.65294
0.1197
21.26
21.08
Single-epoch MF
167
8
0.65293
0.5882
24.03
23.88
Optimal TreeAgg
1000
0.65294
1,0000
24.54
24.45
Multi-epoch MF
1000
8
0.73579
1,0000
24.95
Band MF (Ours)
1000
0.65294
1,0000
25.06
24.88
DP-SGD
1000
16
0.36861
0,3460
22,51
22.26
Single-epoch MF
167
16
0.36861
1,0000
24.80
24.62
Optimal TreeAgg
1000
16
0.36861
1.7000
25.15
25.14
Multi-epoch MF
1000
16
0.41539
1.7000
25.50
25.33
Band MF (Ours)
1000
16
0.36861
1.7000
25.59
25.41
Table 4: Parameters and metrics for simulated cross-device FL, Fig. 6[a]. The noise multipliers are calibrated to achieve the given c guarantees at 8=10-6 under b-342-min minn---ai--saaaaiiion The matrices scaled to have sensitivity under (x=6,b=342)) see Table and so larger noise multiplier a is necessary for the MULTI-EPOCH MF matrices. Test-set accuracy for MULTI-EPOCH MF at = 8 was unavailable. All BANDMF matrices use b=342. Note that is reported for reprodueibility purposes (it is the parameter passed Alg. 1), but it does not directly capture the noise added in either gradients x; or their cumulative sums as the noise z is linearly transformed by C-1 which varies across the mechanisms above.
29

---

Mechanism
clients per
noise
server
Eval Accuracy (%. Smoothed)
Test Accuracy
round B
mult. o
Ir 7/
(%)
DP-SGD, w/ ampl.
1000
1
0.37313
0.3460
22.50
22.22
Multi-epach ME, ampl.
1000
I
4.22468
0.2035
22.11
22.10
(Band) MF, w/ ampl. (Ours)
1000
1
0.79118
0.3460
23.11
22.83
DP-SGD, w/ ampl.
1000
2
0.30481
0.3460
22.89
22.62
Multi-epoch MF, no ampl.
1000
2
2.23048
0.3460
23.36
23.24
(Band) MF. w/ ampl. (Ours)
1000
2
0.64708
0,5882
24.01
23.71
DP-SGD, w/ ampl.
1000
4
0.25136
0.3460
23.27
22.94
Multi-epoch MF, no ampl.
1000
1.19352
0,5882
24.36
24.16
(Band) ME, w/ ampl. (Ours)
1000
0.52224 4
1.0000
24.67
24.42
DP-SGD, w/ ampl.
1000
8
0.20567
0,5882
23.59
23,30
Multi-epoch MF, no ampl.
1000
8
0.65294
1.0000
25.08
24.88
(Band) MF, w/ ampl. (Ours)
1000
8
0.43490
1.7000
25.26
24.99
DP-SGD, w/ ampl.
1000
16
0.16876
0.5882
23,96
23.61
Multi-epoch MF, no ampl.
1000
16
0.36861
1.7000
25.59
25.43
(Band) MF, w/ ampl. (Ours)
1000
16
0.36861
1.7000
25.59
25.43
Table 5: Parameters and metrics for centralized StackOverflow. Fig. 1(b). The noise multipliers are calibrated to achieve the given guarantees at 5=10-6 under b=342) 111-3442)--prriipattion assuming Poisson sampling for DP-SGD and BANDMF. For BANDMF, we tune b under amplification for optimal RMSE, selecting = 9, 18, 32, 64, 2052 for e 1, 4, 8, 16 respectively. For = 16, we have = 6, and hence BANDMF is identical to MULTI-EPOCH MF optimized with Eq. (6). Values of o are provided for reproducibility only, see comments on a from Table 4.
30

---

Eval Accuracy (%, Smoothed)
server Ir 7)+
0.0084
0.0143
0.0244
0.0414
0.0704
0.1197
0.2035
0.3460
0.5882
1.0000
1.7000
2.8900
4.9130
8.3521
Mechanism
DP-SGD
14.31
15.98
16.82
16.53
15,46
4.67
Single-epoch MF
20.16
20.29
19.68
1.0
Optimal TreeAgg
21.08
21.15
20.34
Multi-epoch MF
21.56
21.96
21.60
Band ME, 6=342 (Ours)
21.70
22.12
21.96
DP-SGD
16.20
17.88
18.70
18.22
17.75
15.52
Single-epoch MF
21.46
21.66
21.26
2.0
Optimal TreeAgg
22.40
22.52
21.87
Multi-epoch MF
22.80
23.15
22.96
Band MF, 342 (Ours)
23.27
23.31
22.57
31
DP-SGD
18.08
19.45
20.07
19.97
19.48
18.08
Single-epoch MF
22.66
22.94
22.60
4.0
Optimal TreeAgg
23.57
23.66
23.27
Multi-epoch MF
23.87
24.19
24.01
Band ME, 6=342 (Ours)
24.26
24.35
23.74
DP-SGD
20.61
21.26
21.24
20.89
20.00
Single-epoch MF
23.73
24.03
23.71
Optimal TreeAgg
24.52
24.54
24.15
Multi-epoch MF
24.72
24.95
24.77
24.17
Band MF, b=342 (Ours)
24.76
25.06
24.92
DP-SGD
22.39
22.51
22.17
Single-epoch MF
24.66
24.80
24.50
16.0
Optimal TreeAgg Multi-epoch MF
24.89
25.15
25.15
25.38
25.50
25.34
Band MF, 6-312 (Ours)
25.38
25.47
inf
DP-SGD
25,96
26.23
26.24
8.03
Table 6: Federated learning rate tuning for StackOverflow NWP. Validation accuracy smoothed over the final 400 rounds of training, used to select the best server learning rates for the comparison of test-set accuracy presented in Fig. 6[a].

---

Eval Accuracy (%,, Smoothed)
server Ir 7)s
0.1197
0.2035
0.3460
0.5882
1.0000
1.7000
2.8900
4,9130
Mechanism
DP-SGD
22.39
22.50
22.03
1.0
Multi-epoch MF
21.75
22.11
21.95
Band ME, 6=9 (Ours)
22.83
23.11
23.03
DP-SGD
22.70
22.89
22.66
2.0
Multi-epoch MF
22.89
23.36
23.26
Band ME, 6=18 (Ours)
23.80
24.01
23.77
DP-SGD
22.88
23.27
23.20
32
4.0
Multi-epoch MF
23.96
24.36
24.22
23.71
Band ME, b=32 (Ours)
24.52
24.67
24.43
DP-SGD
23.48
23.59
23.28
8.0
Multi-epoch MIF
24.79
25.08
24.98
24.55
Band ME, b=64 (Ours)
25.15
25.26
24.79
DP-SGD
23.85
23.96
23.72
Multi-epoch MIF
25.42
25.59
25.50
24.92
16.0
Band MF, b=342 (Ours)
25.37
25.55
25.45
24.90
Band ME, b=64 (Ours)
25.38
25.54
25,40
Table 7: Centralized learning rate tuning for StackOverflow NWP.. Validation accuracy smoothed over the final 400 rounds of training, used to select the best server learning rates for the comparison of test-set accuracy presented in Fig. 1(b). DP-SGD and BANDMF use amplification.

---

Algorithm 8 Banded Matrix Multiplication
Algorithm 9 Banded Inverse Multiplication
Input: b-Banded lower triangular matrix Ce TR RRn vector x E IR"
Input: b-Banded lower triangular matrix Ce R nxn veecto y R"
Output: Cx
Output: C-ly
for i I,..., do
for i= 1,..., do
y, Σ j-i-b-1 (p.s) return y
X; = (y: Σ 5 C(a,)xx))
return
Figure 15: Algorithms for matrix-vector and inverse matrix-vecta multiplication by banded matrix. To simplify the presentation, we use the convention that aut-of-bounde indexing into matrix or vector returns O.
J Efficient Multiplication and Inverse of Banded Matrices
Algorithms and 9 (Fig. 15) give algorithms for lower triangular banded matrix-vecto multiplication and inverse banded vettox multiplication. Note that both algorithms are compatible with the streaming nature of gradients. As soon as the next input x, is received, the algorithm can immediately output y;- Both algorithms require storing a state of size b, and run in O(n b) time. While the algorithms are described with respect to computing matrix-vector products, they can also be used to compute matrix-matre products where the right- hight-hand-side is a n d matrix by multiplying by each column independently. In this setting, these algorithms require O d) space and O(n b d) time. Both algorithms have appeared previously in the literature Monte Carlo methods, which have similar problem at their core to that of noise generation for MF; see e.g. [56, Section 2].
K
Application to a Real-World Cross-Device FL System
We train one-layer LSTM language model of ~2.4 million parameters in practical cross-device FL system following [58]. The model is used for predicting the next word of Spanish in a mobile virtual keyboard. We pretrain the model on public multilingual C4 dataset [49, 60), and then fine-tune with on-device user data in FL. In a common practical FL system, clients have to satisfy criteria like being charged, idle and connected to unmetered network to participate in round [10, 27, 31, 47], hence only a subset of clients can be reached and there is a strong diurnal pattern of client participation [61, 63]. It is very challenging hold fixed set of clients for evaluation, or develop random sampling for privacy amplification. Though the current implementation of client participation control is feasible through the client timer, the tuning of separation b in practice can be challenging. Therefore, the training of Fig. (b) can achieve smaller separation than in [58].
K.1 Reporting privacy guarantees
We follow the guidelines outlined in [48, Sec. 5.3] to report privacy guarantees.
DP setting. This central DP guarantee where the service provider is trusted to correctly implement the mechanism.
2. Instantiating the DP Definition
(a) Data accesses covered: The DP guarantee applies all well-behaved clients in single training run. We do not account for hyperparameter tuning, or the selection of the final model checkpoint using evaluation metrics or A/B testing in our guarantees. Public multilingual C4 data [49, 60] is used for pre-training.
(b) Final mechanism output: Only the final model checkpoint is released for use in pro- duction, however the mechanism's output technically the full sequence of privatized gradients, and so the guarantee also applies at this level, and hence all intermedi- ate models are protected (including those sent to devices participating in federated learning).
11 "Clients that faithfully follow the algorithm including participation limits. Due to the design of the algorithm. behhved client does not adversely affect the DP guarantee of any well-behaved clients.
33

---

(c)
Unit of privacy. Device-level DP is considered, i.e., the notion of adjaceney is with respect arbitrary training datasets on each client device, and the device might have an arbitrarily large local dataset containing arbitrary training examples. For user's with a single device, this corresponds directly to user-level DP; for devices shared with multiple users, this provides a stronger notion of DP than user-level; for user with multiple devices that happen to both participate training the model, the notion is weaker, but group privacy can be used to obtain user-level guarantee.
(d) Adjacency definition for "neigbouring" datasets: We use the zero-out definition [35]. This is a a special form of the add-or-remove definition, where neighboring data sets differ by addition/removal of single client. In the absence of client at any training step, we assume that the client's ' model update gets replaced with the all zeros vector. This assumption enforces subtle modification the traditional definition of the add/remove notion of DP which allows neighboring data sets to have the same number of records.
3. Privacy accounting details
(a) Type of accounting used: Both p-zCDP [11] accounting, and PLD accounting [18] for (e, DP are used.
(b) Accounting assumptions: Each client only participates limited times during the training, and there at least min-separation of b rounds between two consecutive participation of a client. This is enforced by timer on clients in the cross-device FI. system.
(c) The formal DP statement: The privacy guarantees are p=0.32-ZCDP and (e=6.69, 6=10-10)-DP for ONLINE TREEAGG, while BANDMF achieves p=0.24- zCDP and (c=4.35, 5=10-10)-DP.
(d) Transparency and verifiability: We going open source code based on Tensor- Flow Federated and Tensorflow Privacy. Key portions of the cross-device FL system will also open sourced.
34


Reviews:
[{"review_id": "9G6mJbXnD9", "reviewer": "Reviewer_2XT3", "summary": "The paper studies the problem of how to optimize the Matrix factorization (MF) mechanisms so that the effect of random noise can be minimized. The MF mechanisms can be applied in addition to the well-known DP-FTRL or similar online DP algorithms in machine learning training. This technique decomposes the query matrix A (e.g., a matrix encoding the prefix sum) into two matrices and adds noise to the intermediate matrix multiplicative result of the data and one of the decomposed matrices. It can potentially introduce less variance to the final results. The key idea of the paper is formulating the MF problem into an optimization problem. The authors show the sensitivity of the mechanism under some constraints of the participation schema and discuss how to derive the best decomposition in terms of minimizing the error profile because of the decomposition. Some experimental results are provided to demonstrate that the proposed mechanism is at least as good as the classic DP-SGD mechanism.", "questions": "Refer to the Weaknesses", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Generally speaking, this paper provides some in-depth results on the MF mechanism that can be interesting to the community.\n1. The authors provide an insightful analysis angle on how to optimize the MF mechanism.\n2. The authors derive the sensitivity of the MF mechanism under some additional assumptions about the participation schema of the users and the property of the original query matrix.\n3. The authors show how one should optimize the MF mechanism via decomposition and how the mechanism can enjoy privacy amplification via sub-sampling.\n", "weaknesses": "1. While the technical contributions are sufficient for building a good paper, the presentation in this paper makes readers somehow hard to follow. \n\n- MF mechanism is relatively new compared with the other DP mechanisms. So MF may be ambiguous if a reader is not familiar with the ancestors of this work (i.e., [14, 16]), as some readers may be confused DP MF problems (e.g. [1*, 2*]) with the MF mechanism at the first glance. Introducing problem formulation in (the beginning of) the introduction section may help readers evaluate and understand the value of the paper.\n- The explanation of why the MF mechanism can help and how the proposed methods are derived in this paper is not easy to follow. \n- It is unclear what are benefits one can get by following the participation schema and decomposition method proposed methods. There may be some discussion scattered around the paper, but a summary (via a table) comparing the results of this paper to the existing ones may deliver the results more directly to the readers.\n- The key algorithms are most deferred to the appendix. So main text itself is not self-contained and reader-friendly (readers have to jump between the main text and the appendix). At least some algorithms closely related to the main contribution of the paper, like the sampling scheme, should be stated in the main text, not just the theoretical results using this algorithm.\n\n2. Some experimental results may need further explanation. \n- Why the BANDMF and  MULTI-EPOCH MF tends to introduce a similar level of noise as DP-SGD when the number of epoch increases?\n- What is the exact RMSE for BANDMF, MULTI-EPOCH MF and DP-SGD in Figure 4? Also, how should one understand the relationship between RMSE and accuracy (From Table 5 in appendix, smaller noise in DP-SGD can have worse performance than ampl MF)?\n\n\n[1*]Hyejin Shin, Sungwook Kim, Junbum Shin, and Xiaokui Xiao. 2018. Privacy-enhanced matrix factorization for recommendation with local diferential privacy. IEEE Transactions on Knowledge and Data Engineering 30, 9 (2018), 1770–1782.\n\n[2*] Zitao Li, Bolin Ding, Ce Zhang, Ninghui Li, and Jingren Zhou. Federated Matrix Factorization with Privacy Guarantee. PVLDB, 15(4): 900 - 913, 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments, suggestions and questions.\n\n>**MF may be ambiguous**\n\nThis is an excellent point that we missed. We have added the following footnote on the first page: “\n\n“We use matrix factorization for the algorithmic design of DP mechanisms, and then use these mechanisms in general-purpose gradient-based private optimization algorithms. This use of matrix factorization is unrelated to machine learning settings such as collaborative filtering or recommender systems where the ML problem itself involves matrix factorization [37, 41, 51].\n“\n\n[37] Koren, Yehuda, Robert Bell, and Chris Volinsky. \"Matrix factorization techniques for recommender systems.\" Computer 42.8 (2009): 30-37.\n\n[41] Zitao Li, Bolin Ding, Ce Zhang, Ninghui Li, and Jingren Zhou. Federated Matrix Factorization with Privacy Guarantee. PVLDB, 15(4): 900 - 913, 2022\n\n[51] Hyejin Shin, Sungwook Kim, Junbum Shin, and Xiaokui Xiao. 2018. Privacy-enhanced matrix factorization for recommendation with local diferential privacy. IEEE Transactions on Knowledge and Data Engineering 30, 9 (2018), 1770–1782.\n\n>**Why the MF mechanism can help**\n\nSee the global response including the new figure, which is intended to address this question.\n\n>**The key algorithms are mostly deferred to the appendix:**\n\nPlease see the global response; MF-DP-FTRL pseudocode is now given early in the paper, and we have also restructured Section 5 so it is self-contained. As we attempt to add clarity to the other areas where the presentation was unclear, it would be extremely helpful to have specific line numbers or specific questions for any remaining issues\n\n>**Also, how should one understand the relationship between RMSE and accuracy (From Table 5 in appendix, smaller noise in DP-SGD can have worse performance than ampl MF)?**\n\nGenerally, lower RMSE in the estimates of cumulative sums of gradients correlates very well with learning accuracy (e.g., as demonstrated by its ability to predict good learning rates, Fig 11).  However, the noise multiplier sigma is not directly comparable between DP-SGD and MF: In DP-SGD this noise is added directly to the gradients, but in MF linear combinations of noise are added via $C^{-1}$, generally in such a way that some previous noise cancels out when gradients are summed across iterations (see also the new figure that illustrates this intuition). Thus, sigma is included in e.g. Table 4 and 5 for reproducibility (these are the actual parameters used to run the experiments), but not to directly facilitate algorithm comparisons.  We will clarify this in the paper.\n\n>**Importance of the Participation Pattern:** \n\nThe participation pattern we introduce, $b-min-sep$-participation, enables the main results and claims of our paper for the cross-device FL setting. Without this participation pattern, we would not be able to bound sensitivity in this setting. Note that, for the centralized ML setting, this participation pattern is not needed because (k,b)-participation can be enforced and will also satisfy our amplification guarantees. We have expanded the discussion before Definition 1 to the following:\n\n\n“In Defn. 1, we propose b-min-sep-participation, a generalization of (k,b)-participation which can be practically enforced by cross-device FL systems, thus enabling us to leverage BANDED-MF in this setting (Section 5).\\footnote{Note that, b-min-sep-participation is required for the cross-device FL setting. But, (k,b)-participation can be used in centralized settings where it can be enforced and it will also satisfy our BAND-MF amplification guarantees leading to the empirical results we show in Figure 1.} In b-min-sep-participation, the distance between any two participations is at least b, rather than exactly b as in (k,b)-participation:“\n\n>**Further explanation of experimental results**\n\nAs the number of epochs changes, so does the sensitivity of the encoder matrix C, and subsequently the geometry of the optimization problem.  By equation 5, we see that sensitivity can be calculated as a sum of absolute values of entries of X corresponding to iterations where a single user might participate.  As the number of epochs increases, the number of entries of X that we have to sum up also increases.  It turns out that under the constraint of constant sensitivity, it is better to put more weight on the diagonal of X than the off-diagonal.  This is an observation we have made by solving this optimization problem numerically in a number of settings. Hence, as the number of epochs increases, X becomes more and more diagonally dominant, making the mechanism closer to DP-SGD (X = Identity).  We  have added a version of this discussion to Section G.\n\nThe exact RMSE is shown in Fig 5(c), although we primarily looked at the relative RMSE between the different mechanisms in our interpretation of the results.  The exact RMSE is something we purposely omit in Fig 5(a-b) in favor of the RMSE ratio as it is a quantity that is more difficult to interpret directly.  One should generally expect RMSE and learning performance to correlate pretty well, as shown by [Kairouz et al, 2021].  Note that in Table 5, “sigma” should not be compared between mechanisms, as it has different interpretations for different mechanisms — the values are only included for reproducibility.  We added a comment on the header of table 5 to address this confusion, and we provide a more in depth discussion of this issue below.\n"}, {"review_id": "70gUxif2dg", "reviewer": "Reviewer_z4EU", "summary": "The authors present a novel mechanism explicitly designed for differentially private training. The mechanism considers the sensitivity of different participation schemes in the context of fixed datasets during differentially private training. The key contributions of this work can be summarised as follows:\n1. By accounting for the sensitivity of multistep participation schemes, the proposed mechanism eliminates the need for composition.\n2. The authors illustrate how matrix factorisation can benefit from privacy amplification through subsampling and shuffling.\n3. They propose a computationally efficient and precise implementation utilising b-banded matrices to compute sensitivity.\n4. Additionally, they introduce an optimisation technique to craft these b-banded matrices.\n\nThe authors provide theoretical proofs and compelling experimental results to support their claim that their approach outperforms DP-SGD accounting.\n", "questions": "* More of a high-level question for the authors. In this scenario in which composition is bypassed altogether, why is the Gaussian Mechanism the \"defacto\" mechanism? I might miss something, but I always associate the Gaussian mechanism with composition + l2 sensitivity. It seems the authors have some space to explore other mechanisms (possibly). I was curious if the authors thought more in detail about this; is the Gaussian mechanism optimal in this scenario?\n* A unique perspective on this paper is that most amplification techniques are derived by analysing the linear operator itself and not analysing the output distributions (common, for example, for the subsampled Gaussian mechanism). This is a very interesting view of this work, as it abstracts the noise distribution from the privacy amplification guarantees, giving a more general/decoupled view of privacy amplification in this case. Do the authors think it is possible to design linear operators further to improve privacy guarantees/utility tradeoffs (like other forms of amplification given by the operator's structure), or have we reached some optimal design?\n", "limitations": "* Increased  $O(b)$ multiplicative time/memory overhead compared to DP-SGD.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "* The paper effectively presents the problem, the proposed solution has a nice and clear structure, and the arguments flow in a natural way.\n* The related work is well-presented, providing context and the existing related work gap, namely if the matrix factorization can benefit from the same privacy amplification techniques as DP-SGD.\n* The experimental section is detailed, offering thorough explanations and interpretations of the results.\n* The paper elegantly recovers privacy amplification bounds from DP-SGD by carefully constructing the proposed linear operator.", "weaknesses": "* the current presentation is not self-contained, as it has plenty of references to the appendix/other related work. It is not ideal, as the main statements of the paper are a bit hard to fully understand without them. I know that space is a limiting issue, especially for well-detailed works like this, but please reconsider restructuring so that the main results (Theorem 2. and Theorem 4.) are possibly more easily to grasp without relying on the appendix this much.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback, comments, and questions.\n\n>**Make Paper Self-Contained:** \n\nThank you for these suggestions. We used the additional page to add in an informal proof to Theorem 2 and to add algorithm 4 to the main-text, with a description of how it works. We also have expanded on details elsewhere that may have been pushed to the appendix. Please see the global response describing how we restructured Theorem 4 / Section 5 so that section is self-contained.\n\n>**Optimizing Privacy-Utility Tradeoffs:**\n\nWe agree that the problem of choosing C with the benefits of amplification in mind is interesting and merits future work. Note that, if only using the amplification statement in this paper, the approach in “Optimizing the number of bands” is optimal under the diag(X) = 1 constraint: the resulting privacy guarantee only depends on n (fixed), the number of bands (we can try all choices simultaneously), and the column norms of C (fixed by the diag(X) = 1 constraint). Furthermore, under our sampling scheme this amplification statement is tight, since it captures a tight analysis for DP-SGD. It may be possible for a different sampling scheme one can derive an amplification statement that depends more on the structure of C, but deriving this amplification statement and optimizing C given this statement are likely to be difficult. \n\n>**Gaussian Mechanism Optimality:** \n\nThe fact that Gaussian mechanism is the optimal noise addition algorithm in our setting (with a generic choice of C, and one privatizes Cx as Cx + noise) stems from the fact that the $\\ell_2$-sensitivity of the complete mechanism (w.r.t. a single user) is bounded. (Results like [BUV14] have shown matching lower bounds.) Regarding the comment about avoiding composition, it is well known that (modulo adaptivity of the algorithm) the bound attained by bounding the overall $\\ell_2$ sensitivity, can also be achieved by [zCDP] composition and vice versa. Hence, the views are isomorphic. In addition, it is easier to work with Gaussians in the adaptive setting as prior works have shown that in Gaussian noise addition mechanism for SGD style algorithms, there is no difference between an adaptive and non-adaptive algorithm; this is not true for all mechanisms, as demonstrated by Appendix D.1 of [Denisov et al. 2022] . \n\n[BUV14] Bun, Mark, Jonathan Ullman, and Salil Vadhan. \"Fingerprinting codes and the price of approximate differential privacy.\" Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014.\n\n[zCDP] Bun, Mark, and Thomas Steinke. \"Concentrated differential privacy: Simplifications, extensions, and lower bounds.\" Theory of Cryptography Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2016.\n\n[Denisov et al. 2022] Denisov, Sergey, et al. \"Improved differential privacy for sgd via optimal private linear operators on adaptive streams.\" Advances in Neural Information Processing Systems 35 (2022): 5910-5924.\n"}, {"review_id": "BD6yW2yDdG", "reviewer": "Reviewer_T4Mk", "summary": "This paper proposes banded matrix factorization for differential privacy. It shows this new mechanism can be effectively applied to centralized and federated-learning settings (where individuals can choose when and how many times to participate in training). The main technical part is the $b$-minsep-participation schema that generalizes the $(k, b)$-participation proposed in Choquette-Choo et al. \n", "questions": "Can the authors clarify the argument given in line 224: \"Since we only have equality constraints on 224 individual entries of $X$, Problem 2 is essentially an unconstrained optimization problem\"? \n Are you saying that any constrained optimization problems with equality constraints are essentially unconstrained?   ", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The experiments in Sec 6 demonstrate that banded MF exhibits a very good improvement over multi-epoch MF and DP-SGD in the centralized settings, and almost coincides with (or improves modestly) the state-of-the-art performance in the federated learning.  ", "weaknesses": "While the presentation of the paper is good for the most part, there are some issues that can be improved. For instance, the notation $\\hat b$-banded matrices were used several times in the Abstract, Introduction, and Sec 2 without a precise (or even intuitive) definition [It was defined on Page 5!]. Also, $\\hat b$ and $b$ seem to be interchanged arbitrarily (which is really confusing); see for instance lines 62, 188, 189. (I understand that $\\hat b$ is taken to be equal to $b$ only in Sec 5, but not necessarily in the first 4 sections)\nAlso, Theorem 1 is rather cryptic: Do the \"equal-sized subsets\" mean batches of the same size? Does the partition change for each iteration (like typical SGD)? Is it not the case that $B b = m$? \n\nThis sentence (line 89-90) \"The connection between DP empirical risk minimization [3, 4, 5, 7, 8, 9, 13, 15, 21, 23, 30, 34, 36,90 40, 45, 46, 47, 49] and DP online regret minimization [2, 4, 5, 24, 31, 33] has been studied for a long time.\" is awkward. What is the point of this sentence? Why not directly citing some of those works that studied this connection!!\n\nWhat is SGDM in lines 95 and 101?\n\nThe argument in line 213 is not clear: How does Theorem 2 imply that $\\text{diag}(X) = 1$ and bandedness mean the squared sensitivity is equal to $k$? \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review, and for providing line numbers in your review. We greatly appreciate it!\n\n>**$\\hat{b}$ and b:** \n\nThank you for highlighting this issue.  We now informally define $\\hat{b}$-banded matrices in the abstract, and clarify the difference between b-min-sep and $\\hat{b}$-banded matrices around Theorem 1 in the main-text, including forward pointers to their visualizations. We have also checked that our use of b vs $\\hat{b}$ is consistent, using b to always refer to separation, and $\\hat{b}$ to refer to a number of bands not necessarily equal to separation; this is also now noted in the notation table. The reason the two can be taken to be the same in Section 5 is that setting $b=\\hat{b}$ is optimal for reasons that culminate in section 5.\n\n>**Theorem 1 “equal-sized subsets”:** \n\nThe subsets are separate from the notion of batches in ML; we first partition the dataset into non-overlapping subsets, and then sample batches from within each subset to perform each round of (DP-)SGD. The partitioning into these subsets is fixed across all iterations. We will add the following example to the text, which we believe will clarify both of these points:\n\n“As an example, consider doing 2000 iterations of DP-SGD on CIFAR-10 (which has 50,000 examples) using a minibatch of 500 examples in each round of DP-SGD. This instantiation of DP-SGD has the same DP guarantees as answering 2000 queries using a subsampled Gaussian mechanism with sampling probability 500/50000 = .01.\n\nIf we instead use, e.g., 10-banded DP-MF, our suggested sampling scheme is the following: Split CIFAR-10 into 10 subsets of 5000 examples each, D_1, D_2, … D_10. In rounds 1, 11, 21… we sample 500 examples from D_1, in rounds 2, 12, 22… we sample 500 examples from D_2, and so on. We sample from each subset a total of 2000/10 = 200 times, and each time our sampling probability is 500/5000 = .1 within the subset. So Theorem 1 shows this DP-MF satisfies the same DP guarantees as answering 200 queries with a subsampled Gaussian mechanism with sampling probability .1.“\n\n>**What is SGDM in lines 95 and 101?** \n\nMomentum-SGD, which we have clarified in the main-text.\n\n>**How does Theorem 2 imply diag(X) = 1 (Line 213)?** \n\nTheorem 2 guarantees that the sensitivity will be bounded by k\\sqrt{k’}. Recall that k is an upper bound on the column norms of C. Then diag(X) = 1 guarantees that k=1 and so by theorem 2, the squared sensitivity is bounded by k’^2. We did have a typo in the main-text which will be corrected: (k’ instead of k).\n\n>**Unconstrained Optimization with Equality Constraints (Line 224):** \n\nYes, because the equality constraints exactly specify some entries in X, we can simply consider a lower-dimensional unconstrained optimization that only considers the remaining entries in X. We have improved the wording in the paper to make this clear. \n\n>**Benefits in cross-device FL setting:**\n\n Thank you for highlighting our strong empirical performance in the central settings. We would like to clarify that we do also outperform significantly in the cross-device FL setting (and not just coincide) because we actually report a **tighter privacy budget for our work**. Thus, we achieve (small) benefits in utility as you noted, but significant benefits in privacy. For reference, we reduced the privacy budget from 6.69 to 4.35.\n\n>**Citations in Related Works:**\n\nThe point of these two lines (along with the citations) was to emphasize that there is a long line of work trying to understand the relationship between DP-online learning and DP-empirical risk minimization (DP-ERM). However, whether there is a tight connection between them is still an open question. Only recently, Asi et al. showed that DP-FTRL (a specific instantiation of the algorithmic framework in this paper) achieves the best known online learning regret. So, a natural question is whether our algorithmic framework is strong enough to obtain optimal DP-ERM/ excess population risk bounds purely from an online learning algorithm.\n\nWe will clarify this point more in the paper.\n"}, {"review_id": "oNXlls3pzo", "reviewer": "Reviewer_4QAc", "summary": "In this paper, the authors show how Matrix Factorization (MF) can subsume prior\nstate-of-the-art algorithms in both federated and centralized training settings, across all privacy\nbudgets. They apply the key technique: MF mechanisms with banded matrices. For both the\ncross-device federated learning setting and the centralized setting, the result in this paper\nimproves or generalizes previous results. In addition, the $\\hat{b}$-banded matrices\nsubstantially improve the memory and time complexity.", "questions": "See weakness.", "limitations": "No", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The problem of Matrix Factorization for Differential privacy is well-motivated.\n2. This paper is solid, the results look correct.\n3. The result improves or generalizes previous results.", "weaknesses": "The main result for the centralized setting is summarized in Section 5. However, it seems the\nresult for federated learning setting is not stated clearly. Is there a summary of the result for FL\nsetting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and positive feedback.\n\nOur main results for the cross-device FL setting are written in sections 3 and 4. To make this clearer, we have rewritten our contributions section in the introduction to clearly state the contributions separately for cross-device FL and for centralized training. The new text is in the global response.\n\nWe are happy to engage in more discussion if desired."}, {"review_id": "w8LHQxClvL", "reviewer": "Reviewer_UhEM", "summary": "Applying matrix factorization mechanism and balancing tradeoffs of the mechanism in differential privacy is a long living issue. This work constructs MF mechanism with banded matrices for both centralized and federated training setting across all privacy budgets. For federated setting, this work is compatible with real world federated learning devices. For centralized setting, banded matrices are on par with the same privacy amplification results of DP-SGD algorithm.", "questions": "1. Can you compare advantages and disadvantages of banded and unbanded matrix factorization for DP in FL setting?\n2. In the Theorem 1, what is n? Is n the number of iterations or other things else?\n3. In the Figure 1, it is hard to tell the difference of performance of Banded MF w/ amplification and multi-epoch MF w/o amplification. Why do you need amplification? What does the benefit of amplification for banded MF? \n4. What does the \\zeta mean for multiple participations? How does the \\zeta affect the participations?\n5. What is relationship between x, x tilde and u in equation 2?", "limitations": "1. This work has limited contribution on DP, because this work is more like an incremental work for multiple-epoch MF-DP-FTRL based on Choquette-Choo et al’s work to extend to federated learning setting.\n2. It is not clear why we should assume in the cross-device FL setting, (k,b)-participation is not feasible. I know it is good to have some assumptions in the real world. However, I am wondering if it is necessary to restrict the scenario into such the practical case.\n3. The MF optimization problem looks interesting and promising, but this work still needs more experiments, especially more datasets (at least three and other than small datasets like CIFAR10).\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Banded matrix factorization with amplification can outperform DP-SGD with amplification for centralized setting, and well-balance privacy-utility tradeoffs.\n2. With b-min-sep-participation, banded MF can optimize (k,b)-participation, and reduce linear memory/time complexity for per-iteration noise generation to a constant.", "weaknesses": "1. The bound of sensitivity of MF mechanism looks confusing although the first part looks tight (sup for C*x and C*x_tilde). See Question 5.\n2. Although this work considers FL in the practice, the dataset like CIFAR 10 seems quite outdated and the scale of CIFAR10 is too small, which is not enough to convince the community.\n3. Probably authors need to clarify questions I stated in the next sections.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review.\n\n>**(1) Advantages and disadvantages of BandMF in FL:** \n\nMost importantly, the only prior unbanded approach to be applicable to cross-device FL is the single-epoch work, which we significantly outperform Empirically, we show this on  SO-NWP, a large-scale, non-iid, and common FL benchmark in Figure 5 (a) as well as experiments in production setting in Figure 5 (b). \n\n>**(2) What is n in Theorem 1:** \n\nIt represents the number of iterations/steps of SGD. We will add this to the statement.\n\n\n>**(3) Benefits of Amplification in Figure 1:**\n\nWithout amplification, Multi-Epoch Matrix factorization performs worse than DP-SGD with amplification for small $\\epsilon$. This was shown in their work [14] and can be observed from Figure 1 (a) by comparing DP-SGD and Multi-Epoch MF. This is because in the small $\\epsilon$ regime, the benefits of amplification are larger than the benefits of correlated noise, and prior to our work there was no proven privacy amplification guarantee for DP-MF. Proving such a guarantee is thus what  enables us to significantly outperform DP-SGD in a larger regime of $\\epsilon$, and perform no worse than DP-SGD for all $\\epsilon$. Amplification allows us to obtain tighter privacy budgets $\\epsilon$ given the same protocol by accounting for how randomness in sampling can obscure data more. Importantly, this means that before our work, practitioners would need to implement both algorithms and check empirically which worked better for their setting; our work provides a single algorithm that is never worse, and often better. \n\nWe will add the following explanation to the introduction after we reference Figure 1:\n“\nEmpirically, we show that MF with amplification has privacy-utility tradeoffs that are no worse than DP-SGD for all, and often significantly betteras can be seen in Fig 1. This is in contrast to prior ME-MF work [14] which can be observed by DP-SGD outperforming it Fig 1.\n“\n\n>**(4) What does the \\zeta mean for multiple participations? How does the \\zeta affect the participations?:**\n\nLet's consider example-level DP / centralized training for simplicity. Then,  $\\zeta$ is the clip norm which bounds the per-example gradient $\\ell_2$ norm, exactly as in DP-SGD (see Alg 1). Thus, this controls the sensitivity only of that individual participation, and we require e.g. Thm 2 or Thm 3 to bound the total sensitivity. Note this is a different approach than DP-SGD, which does not explicitly bound the sensitivity to multiple participations, but instead uses DP composition across each participation (or amplification-via-sampling composition when sampling is done, and a fixed limit on participations is not present).\n\nThus $\\zeta$ does not influence the participation pattern, but does influence the final total sensitivity. \n\n>**What is the relationship between $x$, $\\tilde{x}$, and $u$ in equation (2)?**: \n\n**x** represents the stream of gradients, i.e., the outputs of SGD throughout ML training, *that satisfy the participation pattern $N$*. For example, in multi-epoch MF of [14], this would be all sequences where there are at most *k* non-zero entries that are separated by exactly *b* steps. **$\\tilde{x}$** represents the neighboring stream of gradients, i.e., replace all contributions by that single example with 0. This is required to bound the sensitivity as in DP analysis. This can be equivalently expressed as sampling **$u \\in \\mathfrak{D}$** if we define this **$\\mathfrak{D}$** to be the set of all deltas **$x - \\tilde{x}$**. This is described above equation (2), but are happy to make changes at your recommendation to improve the clarity.\n\n\n>**Limitations of Choquette-Choo et al. in the cross-device FL setting:** \n\nThe work of Choquette-Choo et al. [14] is not applicable to the cross-device FL setting, which we discuss in the introduction and the beginning of Section 3. Thus, there is a significant gap in performance in this setting, as can be observed in Figure 6 (a). We get over 1.5 percentage points in improvement over the existing state-of-the-art (Single-epoch MF), which showcases that our work leads to significant practical improvements that could not be ascertained otherwise.\n\n>**Benefits of Amplification and Figure 1:** \n\nWe have separated out our main contributions between those for cross-device FL and those for centralized settings. Please see the global response.\n"}]

Author rebuttal:
Thank you for your time in reviewing our work.

>**On intuition and improved organization.**

We have revised the paper to briefly describe the matrix mechanism in the first paragraph, and have additionally included a new figure to help provide intuition for the advantage of MF-DP-FTRL, as well as complete pseudocode for both MF-DP-FTRL and DP-SGD early in the paper (see attached pdf). We have also added the following text to provide additional intuition for our view of MF in ML:

The (new figure) compares DP-SGD and MF-DP-FTRL. To gain an intuition for why MF-DP-FTRL can perform better than DP-SGD, observe that vanilla SGD has iterates $\theta_t = \theta_0 - \eta \sum_{i=1}^t \hat{x_i}$, and hence when the noisy gradients $\hat{x_i}$ are added, the $C_{i,j}^{-1}$ terms in MF-DP-FTRL serve to \emph{cancel out} some of the noise introduced on previous rounds. The noise cancellation reduces the total error in all the prefix sums of gradients $\sum_{i=1}^t \hat{x_i}$ for $t \in [n]$, but also worsens the privacy guarantee of the mechanism, i.e. increases its sensitivity. The privacy worsens as e.g., an adversary trying to learn $x_1$ via $\hat{x_1}$ can partially learn the value of $\mathbf{z_1}$ from $\hat{x_2}$, whereas in DP-SGD $\hat{x_1}$ and $\hat{x_2}$ are uncorrelated. Hence there is a tradeoff between the total error and sensitivity (see next paragraph): DP-SGD sets $C_{i,j}^{-1}= 0$ below the main diagonal, effectively minimizing sensitivity (assuming a fixed normalization of the main diagonal), but with a large total error due to no noise cancellation. On the other hand, MF-DP-FTRL can arrive at a better compromise between mechanism sensitivity and the total error. This is formalized in the optimization problem of Sec 4.

Without a sampling assumption, the implied DP adversary knows which examples participated in batch $S_i$, and for DP-SGD with uncorrelated noise, knows they only need to “attack” $\hat{x_i}$. However, with MF-DP-FTRL, the information from $S_i$ can potentially be masked with a larger amount of initial noise in $\hat{x_i}$, which is then canceled out over subsequent rounds.  “Spreading out” the release of information about batch $S_i$ over a larger number of iterations in this way can intuitively provide better privacy, while still allowing for accurate partial sums of gradients (and hence SGD iterates). This is, in a loose sense, similar to the way SGD with sampling "hides" information about a particular example at randomly chosen iterations.


>**On reducing references to Appendix from Section 5:**

We agree with the reviewers that Section 5 will be easier to read without references to the appendix. We have rewritten the section so that it only refers to the sampling scheme in Algorithm 2 which is already in the main body, rather than the more generic sampling scheme in the appendix. In doing so we have cut or replaced all references to Algorithm 5, which is in the appendix. We have also rewritten Theorem 4 to explicitly say “satisfied by the composition of k subsampled Gaussian mechanisms with sampling probability bp.” instead of “satisfied by Algorithm 6 in App E.1”. This removes the need to refer to the appendix to understand the main algorithms/ideas of this section, with minimal changes to the overall structure/flow.

>**FL versus centralized ML contributions:**

We have now separated out our main contributions between those for cross-device FL and those for centralized ML in the introduction. This is shown below.


“
**Contributions for cross-device FL:**
Here, the (k,b)-participation schema of Choquette-Choo et al. [15] cannot be enforced.  We propose a strict generalization, b-min-sep-participation, and show how to efficiently and exactly bound the sensitivity for banded matrices in Thm. 2, allowing formal DP guarantees and the numerical optimization of optimal mechanisms (Sec. 4). Culminating from this, and because b-min-sep-participation can be practically enforced in FL infrastructure, we show that this leads to significant privacy-utility benefits in a production deployment (Fig. 6 of Sec. 6). Our work also generalizes the sensitivity calculations of Choquette-Choo et al. [15] to provide a general upper-bound on b-min-sep-participation sensitivity (Thm. 3), which allows the matrices of Choquette-Choo et al.[15]to be used in the FL setting, as well as removing the need to exactly bound b before training (see Sec. 6 and App. K).

**Contributions for centralized training:** The existing privacy amplification analysis of DP-SGD does not allow for the correlated noise that is applied in MF-DP-FTRL. Our paper introduces a novel partitioning of the SGD iterates into independent queries A crucial observation is that one can argue the DP for each data sample index independently, which in turn allows us to use different partitioning views. This allows us to prove in Thm. 4 of Sec. 5 that banded matrices enjoy the benefits of privacy amplification, and show that DP-SGD is a special case, giving us the best of both algorithms. This enables us to always pareto-dominate DP-SGD, unlike Choquette-Choo et al.[15] which only does so for large enough as observed in Fig. 1.  Further, this allows us to improve on both baselines, between 1−4%-points. Informally, our amplification result is: ...
“


Meta-review: In this paper, the authors propose a new optimization based method to reduce the effect of added noise for matrix factorization, and the proposed one can be applied to both centralized and federated scenarios. Analysis and experimental results demonstrate that the proposed one is better than (or at least as good as ) DP-SGD.  To this end, I recommend accepting this submission.

However, I do have some concerns regarding the writing and the potential impact on applications. For writing, it should be further improved as most of reviewers complain about it. I also suggest the authors to add more discussions about the potential applications to make it practical. 

Hope the authors find the discussions with reviewers useful and make this submission a better one.
Decision: Accept (poster)