Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams
Authors: Serguei Denissov
Hugh Brendan McMahan
J Keith Rush
Adam Smith
Abhradeep Guha Thakurta
Venue: NeurIPS 2022 Accept (2022)
Keywords: federated learning
differential privacy
adaptive streams
machine learning
matrix mechanism
matrix factorization

Abstract: Motivated by recent applications requiring differential privacy in  the setting of adaptive streams, we investigate the question of optimal instantiations of the matrix mechanism in this setting. We prove fundamental theoretical results on the applicability of matrix factorizations to the adaptive streaming setting, and provide a new parameter-free fixed-point algorithm for computing optimal factorizations. We instantiate this framework with respect to concrete matrices which arise naturally in the machine learning setting, and train user-level differentially private models with the resulting optimal mechanisms, yielding significant improvements on a notable problem in federated learning with user-level differential privacy.

Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams
Sergey Denisov University of Masconsin-Madison denissov@wisc.c edu
H. Brendan McMahan Google Research mcmahan@google..o com
Keith Rush Google Research
krush@google..oom com
Adam Smith Boston University ads 22@bu. edu
Abhradeep Thakurta
Google Research at athnauurta@gggggeeccoom com
Abstract
Motivated by recent applications requiring differential privacy adaptive streams, we investigate optimal instantiations of the matrix mechanism [I] this setting. We prove fundamental thcoretical results the applicability of ma- trix factorizations to adaptive streams, and provide parameter-free fixed-point algorithm for computing optimal factorizations. We instantiate this framework with respect to concrete matrices which arise naturally in machine learning, and train user-level differentially private models with the resulting optimal mechanisms, yielding significant improvements in notable problem in federated learning with user-level differential privacy.
1 Introduction and background
important setting for private data analysis is that of streaming inputs and outputs-off often dubbed continual release. Hiding individual information is especially challenging in such settings since the arrival of one person's 's data may affect all future outputs of the system. A significant line of work formalizes differential privacy (DP, [2]) under continual release and builds algorithms that meet the resulting definition (e.g. [3-8]). One prominent application private, continual-rekhe algorithms to adapt iterative optimization algorithms such as SGD so that their outputs satisfy DP [7, 6, 9].
The problem of privately computing cumulative sums plays key role in both theory and applications. Given a set of input vectors (e.g., gradients) gi,..., 8n. with g: E Rd the task is to approximate the sequence of prefix this task form the core building block in DP algorithms for online PCA [10], online marginal estimation [4, 3, 11], online top-k selection [12], and training ML models [13, 6, 14], among others. For example, a common approach to private optimization is to add noise to the gradient estimates in SGD [15-17]. Kairouz [6] make the observation that the key DP primitive in such contexts not the independent estimation of individual gradients, but rather the accurate estimation of cumulative sums of gradients. Lowering the eтror of the DP algorithm's 's approximation to the cumulative sum translates directly to improved optimization.'
(g): gi g2, ........... gi + gn.) while satisfying DP. Solutions to
SSGD with constant learning rate 17 serves as an intuitive illustration: performing SGD on parameters starting from 0, the i-th iterate is simply 0, = -n Eim gi, where gi is the gradient computed on step i. That is, the learned model parameters 9 are exactly scaled version of the cumulative sum of gradients far. It is the total enror in these cumulative sums that matters most, the errr in the private estimates of each individual [6] for formal statement.
g.. See Theorem
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The structure of continual-releas algorithms imposes two major constraints: first, the algorithm must be computable online- that is, we must produce the output at a given time using only prior inputs and second, privacy analysis must account for adaptively defined inputs- that is, the guarantee should hold even against an adversary that selects inputs based on all previous outputs of the system. In learning applications, the privacy analysis must be adaptive even when the stream or raw training examples is fixed in advance, because the points at which we compute gradients depend adaptively on the output of the mechanism so far [14].
In this paper, we revisit the design of continual-releant algorithms for cumulative sums and related problems. We give new tools for analyzing privacy in the adaptive setting, new methods to design optimal (within a class) algorithms for summation-style problems, and applications to central prob- lems in private machine learning. Although we focus on learning as the primary application of our algorithmic and analytic tools, our techniques apply to a wide range of private computations over streaming data such as online monitoring [18, 19], tracking distributional changes over data streams [20], and detection of emerging trends [21].
Prior Approaches Prior approaches to DP approximation of cumulative sums fall broadly into two categories. First, in streaming settings, existing work is generally based on the binary-tree estimator [4, 3]. This estimator embeds the values to be summed as leaf nodes in a complete binary tree T, with internal nodes representing the sum of all leaves below them. The mechanism views the entire tree as the object to be privately released (ensuring privacy by adding independent noise to each node). An important refinement of Honaker [22] leverages the multiple independent noisy observations of correlated values to produce lower-variance estimates of the prefix sums. Kairouz et al. [6] apply Honaker's online variant, dubbed Honaker On inee to the sheeuuhhee-rgulriizelleeeeee approach to optimization [23-25]. The tree structure of these mechanisms allows for privacy analysis in the adaptive setting, as observed by [14] and formalized by [8].
The second, more general approach to cumulative sums has previously only been applied in offline settings, in which the input is received and outputs are produced as a single batch. The idea is to view cumulative sums as special case of linear query release (since each output a pre-specified linear combination of the inputs). In the offline setting, the tree- rreeb approaches can be viewed as instantiations of this widely-studied factorizatinn framework (as in, for example, [26, 1, 27-29]). To introduce the general matrix factorization approach, consider the task of computing a private estimate of linear mapping G + AG defined by matrix A E no (assumed to be full-rank throughout this work). Given any factorization A = BC, DP estimate of AG can be computed as
AG = B (CG + Z)
(1)
where Z represents a sample from a noise distribution D. Choosing 'D in way that appropriately depends on the sensitivity of the map G - CG. one can prove privacy of the noised vector CG + Z,
and hence of the mapping G + AG. For example, in the case of cumulative sums, the matrix A the lower-triangular matrix S with I's on and below the diagonal; the binary tree mechanisms correspond to a matrix C7 with one row per tree node (see Appendix A and Appendix C respectively). typical choice for the noise Z is select from a spherical Gaussian distribution.
focus of existing work (e.g. [1, 21-27999) is to choose the factorization BC to optimize some measure of overall accuracy (such total mean squared error) subject to privacy constraint. However (with the exception of the independent, parallel work of Fichtenberger et al. [30]²), streaming constraints and adaptive privacy were not explicitly considered. In the streaming setting, one naturally requires the jth element (row) of AG to be computable using only the first i elements (rows) of G. This corresponds to requiring that the linear operator of interest A has a lower-triangule structure when represented as a matrix, a requirement that is met by all the matrices under consideration in this work. Distributing the B in Eq. (1), we see AG = AG + BZ. As long as AG is lower triangular, then, any matrix mechanism can be implemented by an online algorithm, via the distribution induced by BZ. However, this observation does not address key problem: under what conditions is the resulting mechanism adaptively private?
Fichtenberger et al. [30] strive to get an analytical optimal leading multiplicative constant for the additive error achievable for the problem of continual observation under DP. We on the other hand focus on computation- ally estimating the optimal matrix factorization mechanism for the problem under DP. We leave the empirical comparison to the explicit construction in Fichtenberger et al. for future work.

---

DP estrrsaties di ceelic wath
UP antiemales of micreniim Lardles, of
HonaEer ONLLne
13579 13.53
Hossker delane
2411633 (3.20<)
Ienneer Full
5359 11.5491
Hoeaker Fall
3078147 (3.48c)
19t. Pretix 3an
3542
0st Profie bue
704914
Octsnal 516438 (8.71x)
50C0
50
202
320 240
Rocation
110 20.00
Figure 1: Left: Per-iteration squared error of three mechanisms for DP online prefix sums for 512. Honaker Online and Honaker Full correspond to DP binary tree aggregation with the streaming and full Honaker estimators (respectively), while Opt: Prefi the optimal matrix factorization. The tree-based mechanisms suffer from variability in the error due to the binary tree structure. Right: Squared error in the DP estimates of the iterates of momentum SGD for four mechanisms. Momentum is treated as post-processing of cumulative sums for the first 3 mechanisms, while Opt imal M (see Section 4).
Sum corresponds to
B C uses the optimal factorization of the momentum matrix
The applications to optimization raise their own set of critical questions: How can we efficiently compute such factorizations? Which linear operators are the appropriate ones to factorize in the case of SGD? Finally, can these factorizations actually produce improved privacy/accuracy tradeoffs for real-world machine learning tasks?
Contributions We provide a deeper understanding the matrix mechanism the adaptive stream- ing setting. We show that if Z in Eq. (1) is drawn from Gaussian distribution of appropriately computed variance, then the resulting mechanism is differentially private in the adaptive streaming setting, independent the structure of B and C. We make explicit connection here with the casier-to-sed privacy under adaptive streams of trinnuura factorizations. Furthermore, we show that this property is specific to the Gaussian mechanism, and does not extend to arbitrary noise distributions.
For natural notions of error and adjacency specified in Section 3, present fast and parameter-fiee fixed-point algorithm for computing optimal factorizations and prove local convergence guarantee for this algorithm, leveraging representations of optimal factorizations which are to our knowledge novel in the literature on the matrix mechanism. The optimal computed factorizations show significant improvement over existing flate-oftthe-e trrt---rt private streaming prefix sum methods [22], additionally removing the artifacts of the binary tree data structure (see Fig. 1). Furthermore, fixed-point algorithm can be two orders of magnitude more computationally efficient than existing optimization methods for the matrix mechanism [27] (though we did not explicitly compare McKenna et al. [28]), and provides direct bound the duality gap which allows precise stopping criteria.
Going beyond prefix sums (which correspond to constant learning rate SGD noted above), construct matrix mechanisms that directly encode more sophisticated optimization algorithms as linear operators gradients: in particular, arbitrary combinations of (data independent) learning rate schedules and momentum.
We compute optimal factorizations of these general matrices via fixed-poine iterations, and use them to train user-level differentially private language models on a canonical federated learning benchmark, showing that these factorizations significantly improve the privacy/utility curve (in fact, closing 2/3rds the gap to non-private training left by the previous state-of-the-art for single pass algorithms). For prefix sums, we show computationally--fiice structured matrices provide high-fidelity approximations to the optimal matrices, allowing implementations to scale essentially independent of the number of iterations
Notation and conventions Matrices will be denoted by bolded capital letters (e.g. A, B), with some symbols reserved for special matrices, notably S (prefix sums) and M (momentum, defined
3

---

in Section 4 and illustrated in Appendix A). Vectors will be denoted by bolded lowercase letters (e.g. x, y). For a real symmetric matrix A, the smallest and the largest eigenvalues are denoted by Amin (A) and ( For matrix A, A denotes the conjugate transpose and AT denotes the Hloore-Penross pseudoinverse; a star as in X* indicates a matrix that is optimal in way made clear by context. diagpart represents the operation of taking the diagonal elements of matrix; diag represents embedding a vector argument on the diagonal of a matrix. Additional notation is summarized in Appendix A.
2 Privacy for adaptive streams
In this section, we provide structural results that clarify the classes of mechanisms/algorithms for cumulative sums and other linear computations in the continual release model [4, 3] that remain private even when the inputs stream is defined adaptively. In the continual release model, mechanism receives a stream of inputs G = .g...... .n]] and produces a stream of outputs a1, an, where output a, is intended to approximate some function of the prefix gi...., gi and must be generated before gi+1 is received. We specify which parts of the input can depend on a single person's 's data via a neighbor relation N on data streams. Two streams neighbors if they differ in one person's data. For example, if one person's 's data directly affects exactly one input in the stream ("event-level privacy"), then we say two data streams are neighboring if they differ in exactly one element (that is, they are at Hamming distance 1).
The original works on continual release analyzed privacy in nonadaptive model: mechanism M (e, -)ddffferentlllly private [31, 32] for nonadaptive continual release if, for all pairs of adjacent data streams G, H. the corresponding distributions output streams MMG) and M(H) are (s, 6)- indistinguishable, denoted M() Re.8 M(H). That is, for all events E, we have Pr[M((G) e E] Pr(M(() E E) + å and Pr(M(() E) e Pr(M(G) E E) + d. (A variant of this definition tailored to differentially private gradient descent, with a precise instantiation of the neighborhood notion is presented in Definition J.1 in the appendix.)
In many use cases including those arising in iterative gradient- based optimization algorithms the nonadaptive model is inadequate, since the inputs g; may be generated in real time as function of previous outputs a a 1, To summarize the more general, adaptive definition [14, 8J. consider an adversary that aduptively defines two input sequences G = (g1 ................................ gn) and H = (h1..... h,) The adversary must satisfy the promise that these sequences correspond to neighboring data sets. The privacy game proceeds in rounds. At round t, the adversary generates g: and h, The game accepts these if the input streams defined so far are valid, meaning that there exist completions (gr+1...., ga) and (he+1,..., ..., h.)) so that ((g).... gr, 1..1, gn), (hi,.., he, hett, ..... h,)) E W. For example, in the case of event-level privacy, the game simply checks that the two streams differ in at most one position so far.
The game is parameterized by bit side e {0, 1} which is unknown to the adversary but constant throughout the game. The game hands either g: or h; to the mechanism M, depending on side. The mechanism's output a; is then sent to the adversary. The privacy requirement is that the adversary's views with side = O and side = 1 be (c, 5) indistinguishable. One can substitute other relevant notions of indistingushhability like those from CDP [33, 34], Renyi DP [35], Gaussian DP [36]. The mechanisms we consider generally satisfy Gaussian DP.
The nonadaptive version of the definition is weaker but easier to work with. is therefore natural to look for classes of mechanisms for which the two definitions are equivalent (and thus for which a nonadaptive privacy proof implics the more general guarantee). We first observe that such a transfer statement holds for "pure" cDD (in which 0). We defer all the proofs to Appendix D.
Proposition 2.1. Every mechanism that is (E, 0) nonadaptively DP in the continual release model satisfies the adaptive version of the definition, with the same parameters.
Unfortunately, not all privacy proofs for the nonadaptive model transfer to the adaptive setting. Indeed, we show that there are additive-noise mechanisms (which simply add noise from a pre- defined distribution to some function of the data) that are nonadaptively (e, 8)-DP, but not private in the adaptive setting (Appendix D.

---

Adaptive privacy for Gaussian noise addition mechanisms In Theorem 2.1 we show that every matrix mechanism with Gaussian noise addition that is (e. 6)-DP in the nonadaptive model is also private in the adaptive setting:
query matrix, and let A BC be any fuctorization with the following property: for any Iwo neighboring streams of vectors G. A. E Raxd we have C - | S k. Let Z (O 62 o with large enough so that M(G) AG + BZ = B(CG Z) satisfies (e, 0DP (or p-zCDP or p-Gaussian DP) in the nonaduptive continual release model. Then, M satisfies the same DP guarantee (with the same parameters) even when the rows of the input are chosen adaptively.
Theorem 2.1. Let A R be lower- triin-rraanlar full-- full-rank
To prove this we crucially use the rotational invariance of spherical Gaussian distribution, yielding distributional equivalence of an orbit of mechanisms: those factorizations expressible as BUU*C for U unitary. This observation can similarly be leveraged show a subtly distinct fact:
Proposition 2.2. For any factorization A = BC where A is lower-triangular, there exists factorization A = BC which induces distributionally equivalent matrix mechanism under Gaussian noise with B and C lower triangular. This factorization can be explicitly computed from A BC via an appropriate LQ decomposition. Normalizing to all-nonnegative entries on the diagonal, this factorization is unique.
3 Computing optimal factorizations
Once one writes down the matrix mechanism as in Eq. (1), it natural to seek factorizations that minimize the error AG - AG in some metric of choice. In this section we consider the expected squared reconstruction error of the estimate AG, which has previously been noted as appropriate formulation error for the setting of training private ML models [6, Theorem 5]. Further, for simplicity we restrict our attention to the single-pass setting. That is, for the remainder of the paper we will assume:
Definition 3.1. Two data matrices G and H in Bxxd will be considered be neighboring they differ by a single row, with the f--norm of the difference in this row at most Ç.
Under this notion of sensitivity, one can make the estimation of any query AG (c, D)-P via Theorem 3.1, which via Theorem 2.1 immediately extends to adaptive streams. It is worth mentioning that while we state the analytic vairance for the Normal distribution to satisfy (s, 5)-DP, in practice we arrive at the required (and tighter) variance via empirical privacy accounting methods like zero concentrated DP (zCDP) accounting [33], or privacy loss distribution (PLD) accounting [37].
Theorem 3.1 (Adapted from [I]. Consider a query matrix A E Raxx along with a fixed fac- torization A = B Baxn Cuxn with = maxxeen] [|C the maximum column norm of C. Let G nxd be a fixed (non- addative) data matrix with each row of G having E--norm at most S. The algorithm that oulputs B (CG + Z) with Z ~ N (0. 292(2200(1100+t)) axd satisfies (e, DDD
ex
In this setting, with ~ A (0. >2) nxd following Theorem 3.1 (which ensures a fixed level of privacy when ( = 1 for an arbitrary factorization factorization A = BC) the expected reconstruction error
can be computed directly as L(B, C) [1, Proposition 9], [27, Equation 3].
(2(C)= = maxx
and C(B.C) = (C) B
:E(I.......
As has been noted 27]. Eq. (2) can be manipulated to yield convex program, for which hand-tuned algorithms exist [27, Section 4]. Theorem 2.1 shows, for the first time, that arbitrary factorizations found by minimizing this optimization problem can be applied in the adaptive streaming setting.
We present an alternative characterization of these optima, which reformulates the optimization problem fixed-point problem. We show that simply iterating explicit mapping converges to this fixed point from an appropriate initialization, and observe numerically that the associated algorithm achieves fast, global convergence.
Since the PonrosPe pseudoinverse yields the minimal fo-n solution to a set of underdeter- mined linear equations [38, Theorem 1.] note that for fixed C term (of any dimensionality).
5

---

The sum of the elements of á represents a quantity of independent interest in quantum information, the so-called Jozsa fidelity [39, 40], while X' represents the matrix geometric mean of A A and diag(v) -1 [41, 42]. These connections give some hope that the fixed point of can be understood in this the optimal B may be expressed as B = ACt. Since A BC implies A = (a for any linear space of matrices V, we may express the optimization problem of interest as
min L (ACT. min 7 (CC))| CEV
min CEV CCV)+((C)1
|C
(3)
CEV
The properties of the problem Eq. (3) have been studied previously. In particular, [27, Section 3] studied symmetric version, transforming the problem as:
X
arg min F.
tr tr(AAAX-)
(4)
which essentially reparameterizes Eq. (3) (with V = =R" in terms of C'C. To recover a matrix- mechanism factorization of A, then, one may utilize any C such that X C²C, e.g. C V Proposition 2.2 can be used to construct lower-triangular factorization desired.
Yuan et al. [27] show: 1) Any solution X of Eq. (4) must have diagonal entries exactly 1. 2) Any solution X may be taken to be strictly within the positive-definit cone, with minimal eigenvalue bounded from below terms of the eigenvalues of A. 3) For any full-rank A, X + tr(A* 'AX is strictly convex symmetric, positive definite matrices. Therefore the solution to Eq. (4) is unique.
By analyzing Eq. (4) directly, we derive a characterization of solutions terms of an explicit fixed-point problem, with a corresponding bound on the optimality gap.
Theorem 3.2. The minimizer X of Eq. (4) is in one-to-one correspondence with the unique fixed point of the function @ R - R defined by
σ(v) = diagpart
(Vdiag(v)1/2 A diag(v)2/2
(5)
Letting
X(v) diag(v)-117 112 (diag(v) (oog(vv))/ A A diag(v) 1/2 diag(v) 11/2
(6)
for the fixed point v* of Eq. (5), that is <0v*)= = vt, we have X = Xvv)), and this pair (X*, v*) satisfies
A'A X' diag(("))
Further, for any RT, the objective value of the primal problem Eq. (4) is lower-bounded by
tr( (2))))) - -1)),
(8)
and this bound is tight for v
direct manner. We can show local, though not yet global, convergence of the iterates fixed point.
Theorem 3.3. ó defined in Eq. (5) is a local contraction around its fixed point in a suitable metric, and hence there neighborhood of this fixed point which iterates of converge to this fixed point. The precise norm of this contraction, and the size of the neighborhood in which convergence is guaranteed, can both be estimated in terms of minimun and maximum eigenvalues of A.
This result can be shown by linearizing the mapping around its fixed point and performing involved estimate of its Jacobian at the fixed point. As such, implied by Theorem E. which states that the linearization of á around its fixed point is contraction in suitable metric, and therefore the Banach fixed- fixed-point theorem applies.
Remark. Notably missing from quantification of the contraction is the dimension n. Indeed, the argument is dimension-independen in strong sense: applies to the suitably generalized definition of ó where A is any bounded linear operator Hilbert space with bounded inverse.

---

Algorithm DP Matrix Factorization SGD
Algorithm Heavy-ball momentum
1: Inputs:
1: Oo =- 0, mm :- for in 1,...:71 do
2: factorization M BC
3: overall learning rate
m. == 8-m,-1 + gi
4: noise level Ø, clipping norm Ç
4: 0, == 0,-1 m
5: examples Xi. i E (1.
6: 0 := 0 E R2d
7: Sample Z E R (a,l) ~ ~N(0 iid
8: for in 1...., n do
9: g V 1.. (00 xt)
G == g min
|
11:
Pg == -y (M.) Gpad +
B B Z)
Empirical performance of the fixed-point method Experimentally. iterating the mapping & is sufficient to converge to the global optimum extremely quickly from any initial point (modulo potential numerical issues in computing the matrix square root, discussed in Appendix E.4). Yuan et al. [27, Algorithm 1] design an algorithm with globally linear and locally quadratic convergence rate, with similar asymptotics to iterating ø (each dominated by n² term), though at the cost of introducing parameter T. Iterating Φ, on the other hand, is parameter-free We implemented [27, Algorithm 1] as well direct muddient-descentbeer canonical benchmark, we computed optimal factorizations of the 512 x 512 and 2048 x 2048 prefix- sum matrices S (Appendix G provides visualization of this optimal factorization). Our fixed-point algorithm was significantly faster than either of the alternatives to compute optima, computing lower-loss matrix for the larger problem in less than minutes than either alternative found in over 80 minutes. See Appendix E.4 for details. Further, via Eq. (8), our approach provides an optimality certificate that allows a precise specification of the stopping criteria terms of any target optimality gap. The speed and simplicity of our fixed-point algorithm was a significant enabler of the mechanism exploration presented in the next section.
method numerically compare convergence speed. As
4 The matrix mechanism for SGD
To define our gradient descent algorithm, let G E Raxd be the matrix of gradients, with row vector gi RR. xx the gradient observed on iteration after clipping norm most Ç; abuse notation slightly by writing G]ia..] E Raxd formed by taking the first rows of G, with zeros for the as-of-yet unobserved gradient rows for iterations i I,...,II n (the lower triangular structure of the matrices we consider will imply G[ VS G does not in fact change the value computed). With this notation, general template for private SGD algorithms. The power of this general formulation comes largely from the following privacy guarantee:
define Algorithm
Theorem 4.1. Under the "replace with zero" notion of differential privacy (in Defininition J.1 in the appendix) over examples (records) Xi, taking g = 0 when X; = I, Algorithm 1 (that releases the iterates (..a) satisfies equivalent (e, DDP the Gaussian mechanism with noise variance o² applied to records with &g sensitivity at most Sr where = max, C[a,]) is the maximum column norm of C, and Ç is the clipping norm.
Theorem 4.1 shows that the contribution of C to the loss Eq. (19) is reflected in the privacy guarantee of Algorithm 1, by determining the sensitivity of the matrix mechanism Eq. (I). The contribution of B determines the expected squared reconstruction error of the matrix mechanism, by definition. This quantification can in turn be converted by existing analytical methods to regret bound for convex losses:
Proposition 4.1 (Adaptation of Theorem C.I, Kairouz et al. [6]). In the setup of Algorithm 1, let M be the prefix-sum matrix S, and assume is convex with Ly-Lipschitz constant L. Let O, = 0 Op... For any 0* e gd
7

---

Mechanism
B
C
s.t. M BC
Honaker Online
MS
B
Cr
Equivalent to DP-FTRL of Kairouz et al. [6]
Honaker Full
MS
M
Cr
Opt Prefix Sum
MS B
C3s
for optimal = B
Optimal B
B
CM
for optimal M B CM
Table 1: Instantiations of Algorithm 1 for various factorizations of the SGD matrix M = BC.
a E ((( (x0) S nL?
1 24m
Lon B
(110112 110:11)
We now consider different instantiations of Algorithm Let S be the prefix-sum sum matrix as defined in Appendix A, and let CT be the matrix representation of the binary tree (Appendix C), so for appropriate choices the reconstruction matrices Bhs and Bar. S CT gives the Honaker Onl inne mehcanism, and S Ba gives the Honaker Full mechanism. In particular, using the Honaker Onl ne factorization in Algorithm recovers the non-momentum DP-FTRL algorithm of Kairouz et al. [6].
However, Kairouz al. [6] observed that for non-convex objectives, DP-FTRL with momentum provided superior privacy/accuracy tradeoffs. Given prefix sums, momentum can be implemented as post processing by estimating individual gradients/updates sums (multiplication by S ), and then passing these into a standard momentum SGD optimizer. We show that performance can be improved by directly incorporating momentum and a-priori learning rate schedules directly into the DP mechanism.
the difference of successive cumulative
basic but important observation is that momentum SGD gradients G + MG. We consider the classic momentum algorithm of Polyak [43], with per-iteration learning rates? ........ T/. and momentum E [0, 1), in Algorithm 2. Alternatively, we can express momentum SGD as a linear operator on the gradients:
be expressed linear map of
Proposition 4.2. For any 3 E 10, 2 1, per iteration learning rates m,.-... Aas define the lower-triangular matrix M Raxn the product of lower-triangular matrices M and M
n3 i2j
g--s i i
M 1. -1
M
and M (99
otherwise"
bJj
otherwise"
Then, for any matrix of of per-iteration gradients G E RRaxd with rows gi...., En]. the sequence of iterates O E Rand with rows ( produced by Algorithm 2 can equivalently be written -M..
apply the fixed-point algorithm of Section 3 to M to obtain optimal matrix mechanisms M BC. which indeed leads to improved performance." We can also convert mechanisms that produce DP prefix sums to produce momentum iterates via post processing: given any matrix mechanism for the prefix problem given factorization S BC, can convert this to mechanism for momentum M BC where B MS BB. Straightforward calculations show this representation equivalent to the "Momentum Variant" of DP-FTRL [6]. This allows us to consistently evaluate of the total variance (squared error) induced in the outputs by unit-variance
the mechanisms in noise Z in the mechanism via Eq. (2). Table summarizes the four instantiations of Algorithm I for any choise of M; note in particular that for 3 0 and fixed learning rate schedule π/: 1, M S. Fig. 1 compares the per-step squared error of the DP momentum iterates for these methods for 3 = 0 (prefix sums, as a constant 77 1 is used) and B 0.95.
Computational efficiency Some care is necessary for the efficient implementation of Algorithm 1, particularly the computation of Mf..: G B Z on line 11. First, observe that via Proposi- tion 4.2 we can efficiently compute the MG term via Algorithm 2, rather than as matrix operation.
'The schedule may be arbitrary, but must be chosen a priori a aateeindeeendent way. 'The definition M (8) is for the convenience, and is unrelated to the optimal factorization.

---

Priecyllccuracyy tradeoffs for different mechanisms
Comparing mechenisms.
schedules, and cohort
0.24
Optimal H B
0.25
Opt Pretix Sum
Non-private accuracy
Fonakar Full
accurao
Honaker Online
set
0.16
Optimal M
0.14
Out Prefix Sum
Pravious
0.12
Honaker Full
work accuracy
Honekor
0.10
0.21
0.8
constart
decay
cooldww
cooldown 167
Ir schedule
Figure 2: Test accuracy for the StackOverflow next-word-prediction task. grid search over client and server learning rates and momentum 9, with the best hyperparameters selected based validation set accuracy. We then re-ran 11 repetitions with the best hyperparameters and report the mean test set accuracy with confidence intervals. All models trained with 100 clients per round and constant learning rate schedule.
Figure 3: Test accuracy for mechanisms incorpo- rating learning rate decay in the manner of Sec- tion 4 at E = 18.9. The red horizontal line repre- sents test accuracy of previous state of the art at 18.9; highest horizontal line, test accuracy of non-private model. The final bar group shows learning rate cooldown with 167 clients/round, the maximum possible for a single training pass of 2048 training rounds.
This leaves the computation the noise B Bt..) Z. For applications to MI., could be 10 10 and with even n = 10 rounds (iterations) this might make the total calculation quite expensive if not prohibitive. With an efficient TensorFlow implementation, in our experiments with d 2048, we found we could compute the noise directly. However, for larger applications we show (in Appendix H) that one can compute structured matrices that -pploxapro the optimal B* for the prefix sum matrix while allowing for (d) calculation of the per-round noise vectors (on par with that of the binary tree mechanism, which can also provide computational efficiency with a careful implementation, see Table 2). The key is to observe the diagonal dominance of the optimal B' (see Appendix G), leading to an approximation B that is the sum of lower-triangular d-banded matrix with the remaining entries in the lower triangle extracted from a low-rank approximation computed via wew.atinnnnnsssst-uueess
10 and
Experimental results
The results of Sections and significantly expand the space of mechanisms which can be used in training ML models with differential privacy the single-pass setting. this section we demonstrate that these techniques can in fact significantly advance the state-of-the-. in private ML.
User-level privacy for language models Private training is particularly important for generative language models: training language models on data from the right distribution is critical for utility (e.g., user input in mobile keyboard [44, 45]), but this data is often privacy-sensitive. Further, language models have been shown be capable of memorizing training data [46-48]. this setting it is important to consider user-level DP, where the neighbor relation of the DP guarantee covers all of the training examples (tokens) from any one user, as opposed to single training example [49]. In setting, this corresponds to ensuring that each user's examples contribute update to a single row of X (Definition 3). This is accomplished by extending Algorithm in the natural way to Federated Averaging [50]: instead of single gradient, we take g; to be the sum of the individually- -ociuuallyy-iiipp--t---o- updates of all users (100 or 167 in our experiments) participating in the current round, with each user contributing single round over the course of training.
bounded fn-norm
For these reasons, we focused on the StackOverflow next-word prediction problem, introduced in [51] and publicly hosted in Fonsorrloo-Feeeratee (TFF) [52]. This task was explored extensively in [6], and serves as major benchmark in federated learning, used in [51, 6, 53-55), and others. The SterkOverflow dataset contains sufficiently many clients to support single-pas. -pss algorithms with 100

---

clients per round, similar to the baseline setup of [6]. For this reason, we are able to provide true (e, 6) privacy quantifications for the models we train."
Results We compare the four mechanisms of Table 1 on this problem; full experimental method- ology, as well as additional plots (e.g., for validation error vs. training rounds) are provided in Appendix I. Fig. 2 shows that even with constant learning rates, our matrix factorization approaches significantly outperform the previous state-of of-the--rt across a range of privacy E E's. Further, thanks to the results of Section 2, we able to apply the Honaker Full mechanism for comparison. Fig. 3 shows that applying learning rate decay (dropping the learning rate by 0.15x for the last 512 rounds) and learning rate cooldown (linearly dropping the learning rate from 1.0x to 0.05x over the last 512 rounds) show added improvements. These experiments all used 100 clients/round as in [6], but the rightmost bars shows increasing this 167 (the maximum possible for single pass of 2048 rounds) provides additional accuracy. In combination, these techniques close more than 2/3rds of the gap between private and con-private training.
Conclusions
We have shown the general upplicability of the Gaussian matrix mechanism to the adaptive streaming setting, introduced highly efficient mechanism of determining optimal (in the sense of total Eg error) matrix mechanisms, used this approach to directly incorporate momentum and learning rate schedules into the DP mechanism, and empirically demonstrated the resulting private SGD (or FedAvg in the federated setting) substantially improves on the state of the art for private MI..
While our focus has been on the application of these techniques to gradient-basee optimization algorithms, we emphasize that the problem of producing private estimates for linear queries in the adaptive streaming setting is a fundamental DP primitive of much broader applicability, as noted in the introduction, and our work immediately leads improvements in those applications well.
Finally, our work raises numerous natural follow-up questions which we hope will inspire subsequent work; sketch these in Appendix B.
Acknowledgements
We thank Zachary Charles, Thomas Steinke, Jonathan Ullman, Zheng Xu, and Anastasia Koloskova for their valuable feedback and insights. In particular Thomas pointed us to the Speyer's argument of the lower bound; Zach discussed several of the technical arguments with the authors; Jon provided helpful insights into alternate proofs of Theorem 2.1; Zheng provided valuable pointers to code which were able leverage; and Anastasia caught significantly dropped term in Proposition 4.1.
Adam Smith was supported in part by NSF award CNS-212066) and gifts from Apple and Google. Sergey Denisov was supported by NSF award DMS-2054465 and Van Vleck Professorship research award.
References
[1] Chao Li, Gerome Miklau, Michael Hay, Andrew Megregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24:757-781, 2015.
[2] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitiv- ity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-32732-55
[3] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. on Information Systems Security, 24:):26:1226:244 November 2011.
'With 342,477 users this dataset is still small compared to many real-worke world applications (e.g.. Gboard has billion downloads). The extrapolations verified by [49, 6] suggest the accuracy results of Fig. 3 would hold with (e 1 10 10-P if the population and cohort size (clients per round) were both scaled by 10x.
10

---

[4] 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 10), pages 715-724, 2010.
[5] 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.
[6] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In ICML, 2021.
[7] Adam Smith and Abhradeep Thakurta. (nearly) optimal algorithms for private online learning full-information and bandit settings. In Advances Neural Information Processing Systems, pages 2733-2741, 2013.
[8] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. ArXiv CoRR, abs/21 12.0221,.,0888, 2021. URL https: //apsi///rvvvv org/ abs 2112. 00828.
(9] Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In International Conference on Machine Learning, pages 32-40. PMLR, 2017.
[10] 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 annual ACM symposium on Theory of computing, pages 11-20, 2014.
[11] Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Answering range queries under local differential privacy. Proceedings of the VLDB Endowment, (0110):11261111 2019.
[12] Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. CoRR, abs/2103.16787, 2021. URL
https: http:s///wxxvvvrrr///o
16787.
[13] Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? In 20/7 IEEE Symposium on Security and Privacy (SP), pages 58-77. IEEE, 2017.
[14] Abhradeep Guha Thakurta and Adam Smith. (nearly) optimal algorithms for private online learn- ing in full-information and bandit settings. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL https: htt:::///oceeedeeeeeee neurips cc/ acc/pppr// pdf.
201
fda wtt2fffffalccoc.oo oa5.
[15] 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.
[16] 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 464 473, 2014.
the
[17] Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016. doi: 10.1145/2976749 2978318. URL wwtp:http//. /xx doi. htt.g//...1///975555 2997379.............
[18] Nirvan Tyagi, Yossi Gilad, Derek Leung, Matei Zaharia, and Nickolai Zeldovich. Stadium:
A distributed metadata -rivvaate messaging system. In Proceedings of the 26th Symposium Operating Systems Principles, pages 423-440, 2017.
[19] Úlfar Erlingsson, Ilya Mironov, Ananth Raghunathan, and Shuang Song. That which we call private, 2019.
11

---

[20] Matthew Joseph, Aaron Roth, Jonathan Ullman. and Bo Waggoner. Local differential privacy
for evolving data. Advances Neural Information Processing Systems, 31, 2018.
[21] Differential Privacy Team Apple. Learning with privacy at scale, 2017.
[22] James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2015.
[23] Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv: 2010.
[24] Brendan McMahan. Follow-the- follow-therregularizee wewee-rguuaadid-eeaaeeeee and mirror descent: Equivalence theorems and 11 regularization. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 525-533, 2011.
[25] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[26] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy, In STOC, 2010.
[27] Ganzhao Yuan, Yin Yang. Zhenjie Zhang, and Zhifeng Hao. Optimal linear aggregate query processing under approximate differential privacy. CoRR, abs/1602.04302, 2016. URL http: //aaxiv.orgg//ee
602. 04302.
[28] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. HDMM: optimizing error of high-dimensional statistical queries under differential privacy. CoRR, abs/2106. 1211200..2218, 2021. URL https::/arxxi...ot org/ abs/ 2106 12118.
[29] 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: / http:/oo...oogg////////// 111////..111133331111 3384297.
[30] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained complexity of differentially private continual observation, 2022. URL https: //arxiv. erg/ abs 2202 11205.
[31] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proc. of the Third Conf. Theory of Cryptography (TCC), pages 265-284, 2006. URL http: / dxx doi. wrg/or.../.....o.......o........ 111001011100111111111
[32] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology EUROCRYPT, pages 486-503, 2006.
[33] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. Theory of Cryptography Conference, pages 635-658. Springer, 2016.
[34] Cynthia Dwork and Guy N. Rothblum. Concentrated differential privacy. CoRR, abs//6/3.0188/7 2016.
[35] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[36] Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. CoRR, abs/1905.02383. 2019. URL http: / arxiv. wrt//ogg/////..oooooooo..../.. awwaaasss..... 02383.
[37] Antti Koskela, Joonas Jälkö, Lukas Prediger, and Antti Honkela. Tight differential privacy for discrete-valued mechanisms and for the subsampled gaussian mechanism using fft. In International Conference on Artificial Intelligence and Statistics, pages 3358-3366. PMLR, 2021.
[38] L.. Campbell and C. D. Meyer. Generalized inverses of linear transformations/ S. L. Camphell, C. D. Meyer. Pitman London San Francisco, 1979. ISBN 0273084224.
12

---

[39] Richard Jozsa. Fidelity for mixed quantum states. Journal of Modern Optics, 41(12):2315 2323. 1994. doi: 10. 1880005500044444552511 URL https: http:///ooo.oo//....ooo/// 1080/ 095003494 44521115.
[40] Yeong-Cherng Liang, Yu-Hao Yeh, Paulo E M F Mendonça, Run Yan Teh, Margaret D Reid, and Peter D Drummond. Quantum fidelity measures for mixed states. Reports on Progress in Physics, 82(7):076001, jun 2019. doi: 10. orq/ / 10. 1088/10111111 1118///1616663333 11663//bbcca ablca4.
URL https: /doi.
[41] Jimmie D. Lawson and Yongdo Lim. The geometric mean, matrices, metrics, and more. The American Mathematical Monthly, 108(9):797-812. 2001. doi: 10.1080000009990000000 11919815. URL https: //te:://doooi www.oioorg/1.... 0000///00002990..0//
[42] Ando Tsuyoshi Kubo, Fumio. Means of positive linear operators. Mathematische Annalen, 246: 205-224, 1979. URL http: / eudml...m.m..mmmm....mmmmm..m1.m org/ doc/ 63339.
[43] B.T. Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964. ISSN 0041-5553.
[44] 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, 111811111144,,, 2018. URL http: arxiv. org/ 1811. 11..... 03604.
[45] Swaroop Ramaswamy, Om Thakkar, Rajiv Mathews, Galen Andrew, H. Brendan McMahan, and Françoise Beaufays. Training production language models without memorizing user data, 2020.
[46] Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. The secret sharer: Evaluating and testing unintended memorization in neural networks. In Proceedings of the 28th USENIX Conference on Security Symposium, SEC 19, page 267-284, USA, 2019. USENIX Association. ISBN 9781 9391330699
[47] Congzheng Song and Vitaly Shmatikov. Auditing data provenance in text gext-eenerttion models. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 206,206,770 2019.
[48] Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss: Kather- ine Lee, Adam Roberts, Tom Brown, Dawn Song, Úlfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In 30th USENIX Se- curity Symposium (USENIX Security 21), pages 2633-2650. USENIX Association, August 2021. ISBN 978-1-9991133-243, URL https: /wwww usenix org/conference/ http/aaalniiii www.iniiiittttnnngg..gg..
[49] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. arXiv preprint arXiv: 2017.
[50] H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-effiien learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS 2017, 20-22 April 2017, Fort Lauderdale, FL, USA, pages 1273-1282, 2017. URL http: http:///ooceeedieee nggs .mlr wwl...rres//v55 mcmahan 7a html.
[51] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H. Brendan McMahan. Adaptive federated optimization. CoRR, abs/2003.00295. 2020. URL https: httpt:tt///aiiiiii http:://aaxvvvvi org abs 2003 00295.
[52] Alex Ingerman and Krzysztof Ostrowski. ated, Mar 2019.
Introducing tensorflow feder- http:///wg..tnssffoo.o.ooooo
URL
[53] Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On
large-cohort training for federated learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https: //tpr//v/eee/eeeeeeee/ee net/ htre//ormmmmmm -dt chhwh..
13

---

[54] Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konečný, Andrew Hard, and Tom Goldstein. Diurnal nocturnal? federated learning of muiti-branch networks from periodically shifting distributions. In International Conference on Learning Representations, 2022.
[55] Karan Singhal, Hakim Sidahmed, Zachary Garrett, Shanshan Wu, Keith Rush, and Sushant Prakash. Federated reconstruction: Partially local federated learning. CoRR, 0tbs/2002.03443 2021. URL https: /ttp://aaavvve/eeeeeeeeeeeeeev.a org/ abs / 2 02 03448.
[56] Salil Vadhan. The complexity of differential privacy. In Tutorials the Foundations of Cryptography, pages 347-450. Springer, 2017.
[57] Roger A. Horn and Charles R. Johnson.
Matrix Analysis. Cambridge Uni- URL http://wwe wwwp://wwwaaao.ccoooooooooooo com/
versity Press, 1990. ISBN 0521386322.
3D1 www.-xawwyssseeeerorrrr////2222a
3D202 35225332cccat11111666532aca22222
[58] Thomas Steinke. Composition of differential privacy &; privacy amplification by subsampling.
2022. URL
[59] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda-
tions and Trends in Theoretical Computer Science, 9(3-4):211-40 2014.
[60] Stephen Boyd and Lieven Vandenberghe, Convex Optimizationn Cambridge University Press, March 2004. ISBN 0521833787. URL http: httt:://www..r www. amazon, www/execcobideeeeeeeeeoooooooeoe redirect ctagucieellike - ASSI
[61] D.P. Bertsekas. Nonlinear Programming. Athena Scientific. 1999.
[62] Jorma Merikoski and Ravinder Kumar. Inequalities for spreads of matrix sums and products. Applied Mathematics E-Notes /electronic only], 4, 01 2004.
[63] Nathan Srebro, Jason Rennie, and Tommi Jaakkola. Maximum- Maximum-margin matrix factorization. In L. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 17. MIT Press, 2005. URL https: http::////cceeedeeeeeeeooe neurips...... cc/ hcc/papr////// pddf.
2004/E11eee06961133388 +at.eeaa.saaaaeeeeeeeee22333ea33
[64] Ychuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8), 2009, ISSN 0018-9162. doi: 10.1109/MC.2000.26... URL 263.
https: / doi htto/o0 11011111110
[65] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC). Association for Computing Machinery, 2013. ISBN 9781450320299.
[66] Google. ycar=2019.
Tensorflow-privacy.
[67] Om Thakkar, Galen Andrew, and H Brendan McMahan. Differentially private learning with adaptive clipping. arXiv preprint arXiv:1905.0387) 2019.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See e.g. Definition 3.1, where we
specialize the single-pass setting.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work is focused on private training of machine learning models.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] Our work explores technical methods to enable increased data minimiza- tion and provide greater (provable) privacy. As such, rather discuss some of the social reasons one might want to guarantee privacy to users.
2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [Yes] Results are stated in a self-contained manner.
(b) Did you include complete proofs of all theoretical results? [Yes] All results are proved in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Anonymized code in supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Included in supplementary material, appendix H.
(c) Did you report error bars (c.g.. with respect the random seed after running experi- ments multiple times)? [Yes] Details for generating these error bars can be found in appendix H, while the bars themselves are the main plots.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] These details can be found in the "Integration with federated learning' section in appendix H.
4. If you using existing assets code, data, models) curating/releusing
assets... (a) If your work uses existing assets, did you cite the creators? [Yes] We use public data available from
(TFF), and cited explicitly.
(b) Did you mention the license of the assets? [No] Our data hosted publicly by TFF, which handles the licensing.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] Yes, we' we've ve included code in the supplementary material. The code is available under Apache2, explicit in the code.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] Only publicly available data used in this paper.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] All data is publicly available.
15


Reviews:
[{"review_id": "sopQB9Ve12I", "reviewer": "Reviewer_fTea", "summary": "The work analyzes the matrix mechanism in the adaptive streaming setting that Gaussian noise addition mechanism can be private in the adaptive streaming setting and designs a parameter-free ﬁxed-point algorithm to compute optimal factorizations for summation-style problems. Furthermore, the work provides user-level privacy experiment to see the improvement via the approach.\n", "questions": "I have no questions on the paper", "limitations": "The paper is well writing but not easy to understand, since the structure of it is not very clear.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Adaptive privacy analysis is essential and inevitable while most works on continual release analyzed privacy only in a nonadaptive setting.\n2. Theoretical results are solid to demonstrate efficiency and convergence of the proposed algorithm on the matrix mechanism, and DP in the adaptive streaming settings.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jJqTNw4c5Dx", "reviewer": "Reviewer_r9bX", "summary": "This paper studies the problem of private data analysis in the adaptive/streaming setting. More specifically, the authors provide a matrix factorization based method in this setting and apply it to SGD. The proposed method seems to be novel, and the empirical results look promising.", "questions": "The proposed method is novel, and I have the following concerns about the current paper:\n1. How the different factorizations will affect the privacy and utility trade-off?\n2. How the different factorizations will affect the convergence of SGD?\n3. Whether the method can be extended to the case with multiple data passes?\n4. In the experiments, how do you apply your method to FedAvg? Do you run several local steps and communicate the parameters, or do you just communicate the gradients? Do you only use one pass of the data? What is the number of communications of different methods?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed matrix factorization based method seems novel and can recover many existing methods for SGD.\n2. The authors provide an efficient algorithm to estimate the optimal factorization.\n\nWeaknesses:\n1. It is unclear how the general factorization will affect the privacy and utility trade-off when applying it to SGD.\n2. The method seems to be limited in the case that only one data pass.\n3. The extension of the current method to the FedAvg in the experiments is unclear.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ADXoAOgzw_e", "reviewer": "Reviewer_9W6b", "summary": "This work studies matrix mechanism which guarantees differential privacy over adaptive streams. The authors prove that Gaussian mechanism and $(\\epsilon, 0)$-DP mechanisms that are private for non-adaptive inputs are also private for adaptive inputs. The authors further characterize the expression for optimal matrix factorization. Based on the theoretical intuitions, the authors design a matrix mechanism for SGD which has superior performance than previous algorithms.", "questions": "Questions \n- For the fixed-point algorithm, what's the rough convergence rate, and what's the main difficulty in proving a formal convergence guarantee?\n- How would a sub-optimal matrix factorization affect algorithm performance? For example, if $\\phi$ is some distance $\\Delta$ away from the true optimum, is it possible to characterize the performance degredation?\n- Is it possible to prove convergence for SGD with matrix factorization on say, convex and strongly convex loss functions?\n\nTypos\n- Second to last line in Figure 1 caption: mechaism -> mechanism", "limitations": " Limitations and potential negative societal impact are adequately addressed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- Designing private algorithms for adaptive streaming is an important problem in differential privacy. The authors prove fundamental theoretical results for the matrix mechanism that lead to a practical algorithm for SGD which empirically outperform existing methods.\n- The paper is well structured and clearly written.\n\nWeakness\n- Some algorithms do not have formal theoretical guarantee.\n  - Convergence guarantee for the fixed-point optimization algorithm used in experiments.\n  - Effect of a sub-optimal matrix factorization on algorithm performance.\n  - Convergence rate for DP Factorization for SGD (Algorithm 1)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept