Continual Release Moment Estimation with Differential Privacy
Authors: Nikita Kalinin
Jalaj Upadhyay
Christoph H. Lampert
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Continual Release
Moment Estimation
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: A method for continually and privately estimating both the first and second moments of a data stream with reduced noise compared to naive approaches.

Abstract: We propose *Joint Moment Estimation* (JME), a method for continually and privately estimating both the first and second moments of a data stream with reduced noise compared to naive approaches. JME supports the *matrix mechanism* and exploits a joint sensitivity analysis to identify a privacy regime in which the second-moment estimation incurs no additional privacy cost, thereby improving accuracy while maintaining privacy. We demonstrate JME’s effectiveness in two applications: estimating the running mean and covariance matrix for Gaussian density estimation and model training with DP-Adam.

Continual Release Moment Estimation with Differential Privacy
Nikita P. Kalinin
Jalaj Upadhyay
Institute of Science and Technology Austria (ISTA) Klosterneuburg, Austria
Department of Computer Science
Rutgers University
nikita. wallinnniittt...m .c.at
Piscataway, NJ 08854, USA jalaj upa.hyyy@rutgeerr..... edu
Christoph H. Lampert
Institute of Science and Technology Austria (ISTA)
Klosterneuburg, Austria ch1 ac
Abstract
We propose Joint Moment Estimation (JME), method for continually and privately estimating both the first and second moments of data stream with reduced noise compared naive approaches. JME supports the matrix mechanism and exploits a joint sensitivity analysis to identify privacy regime in which the second-moment estimation incurs no additional privacy cost, thereby improving accuracy while maintaining privacy. We demonstrate JME's effectiveness in two applications: estimating the running mean and covariance matrix for Gaussian density estimation and model training with DP-Adam.
Introduction
Estimating the first and second moments of data a fundamental step in many machine learning algo- rithms, ranging from foundational methods, such linear regression, principal component analysis, or Gaussian model fitting, to mate-offttheaar neural network components, such as BatchNorm (23), and optimizers, such Adam [32]. Often, these estimates must computed and updated continu- ously, called the continual release setting [13] For example, this is the case when the data arrives sequentially and intermediate results are needed without delay, such as for sequential optimization algorithms like Adam, or for real-time systems in healthcare, finance, or recommendation systems. In such scenarios, ensuring the privacy of sensitive data, such as user information or medical records, is essential.
Differential Privacy (DP) is widely established formal notion of privacy that ensures that the inclusion or exclusion of any single individual's data has a limited impact on the output of an algorithm. Technically, DP masks sensitive information by adding suitably scaled noise, thereby creating a trade-off between privacy (formalized as a privacy budget) and utility (measured by the expected accuracy of the estimates). This trade-off becomes particularly challenging when more than one quantity is meant to be estimated from the same private data, as is the case when estimating multiple data moments. Done naively, the privacy budget has be split between the estimates, resulting in more noise and lower accuracy for both of them.
In this work, introduce estimate the first and second moments of vector-valued data without suffering from this shortcoming. Algorithmically, JME relies on the recent matrix factorization (MF) mechanism 33 for continual
method, Joint Moment Estimation (JME), that is able to privately
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Table I: Common workload matrices for moment estimation in 11 method
symbol
coefficients
prefix sum
E1
exponential (weight B)
Eg
standard average
V
11 k 1
sliding window (size k)
W
<iskiss
release DP to individually compute the first and the second moments the data, thereby making it flexible to accommodate variety of settings. For example, besides the standard uniform sum or weighted average across data items, exponentially weighted averages or sliding-window window estimates are readily possible. The key innovation of JME lies in our theoretical analysis of its properties. By jointly analyzing the sensitivity of the otherwise independent estimation processes, in combination with considering carefully calibrated trade-off between them, show that one estimate privately the second-moment matrix without having to increase the amount of noise required to keep the first moment private. In this sense, we obtain privacy of the second moment for free.
JME is practical and casily implemented using standard programming languages and toolboxes. We demonstrate this by showcasing two applications, classical and one modern. First, use JME for continual density estimation using a multivariate Gaussian model, c.g. we estimate the running mean and covariance matrix of a sequence of vector-valued observations. Our experiments confirm that JME achieves a lower Frobenius norm error for the covariance matrix in nigh-privacy regimes as well as a better fit the true distribution measured by the Kullback-Leible divergence. Second, we integrate JME into the Adam optimizer, which is widely used in deep learning. Here, as well, we observe that JME achieves better optimization accuracy than baseline methods in high-privacy and small-batch-size regimes.
2 Background
We study the problem of differentially private continually estimation of the pair of weighted sums of the first and second moments, see Section 6 for a discussion of related works. Specifically, consider a sequence of d-dimensional vectors 21....,ff E X, where X' {(I,....,. ..,) : 24 E Id A max; ||>:||p < {} for some fixed constant Ç > 0. At each step we aim privately estimate the following pair of sums:
Y Σ ata; E Rd and S
Σ Ba E Rdxd
for arbitrary coefficients of E IR and bf E R. This formulation includes many practical schemes; see T To express this problem compactly, we rewrite it matrix form. We collect the coefficients into lower triangular workload matrices, A (at) E R2xx and A₃ = (bf)ssi.gn E RR*x.
We stack the data as rows into matrix X E Raxd Then, all terms of the sums in ① can then be expressed compactly as Y A and S = A2(X X). where the second matrix consists of the data vectors stacked as rows, and denotes the Face-Splitiin Product or transposed Khatri-Rad -Ra X);5 = (x; e æ;)), = vec ), where & is the Kronecker product of two product 16 (X (XXXX); vectors.
To protect the privacy of individual data elements, we rely the notion of differential privacy, considering neighboring datasets as those differing by a single data point; see e.g., [14] for an introduction. Recently, series of works have developed effective methods for privately estimating individual matrices in the aforementioned product form by means of the mairix mechanism [35] 10
9 27
25 39 Its core insight that, in the continual release setting, outputs at later steps should require less noise to be made private than earlier ones because more data points contributed to their computation. One can exploit this fact by adding noise that is correlated between the steps instead of being independent. This way, at each step, some of the noise added at an earlier stage can be removed again, thereby resulting less noisy result without lowering the privacy guarantees.
22
20
We slightly abuse the notation and make S matrix of shape x of instead of a tensor of size x d x d.

---

Algorithm Joint Moment Estimation (JMB)
Require: stream of vectors -1.-...- Un E IRd with || |12 S S,
Require:
workload matrices A1, A2 E RRax
Require:
privacy parameters (c, 6)
Require:
noise shaping matrices C1, C2 E Rax= (invertible, decreasing column norm), defaults: Id
6 < noise strength for (e, 6)- Gaussian mechanism
and Cd for d d I/ scaling parameter A - [Cill==/((cd 22) with c1 11+555'
8 + []][iil1-12
|| joint sensitivity
21 [N(0, "" nxd Ln ~ [W o² ))
I/ 1st and 2nd moment noise
for 1. = 1,2....,17 do
8 r 14 + |CT Zı
[111..) and ti 0z t 24 & x4 + Z2] [p,]]
P. = Σ [Ai]esd S = 1 [Aallasa 83
1
yield
1=1
end for
Technically, the matrix mechanism relies an invertible noise shuping matrix C. For our theoretical results, we often also assume that C' has decreasing column norms, As the private estimate of product AX, one computes AX- = A(X + C- where is a matrix of i.i.d. Gaussian noise. This estimate is (e, d)differrenti private if the noise magnitude is least sens(CX] o,,6, where Te,8 denotes the variance required in the Gaussian distribution to ensure (e, 6)DD for sensitivity 1 queries] sens(-) denotes the sensitivity, which, for any function F, is defined as
sens (P) max [I (()-XXXX))lIII FXX')ll
where X ~ X' denote two neighboring data matrices, i.e. identical except for one of the data vectors.
3 Joint Moment Estimation (JME)
We now introduce our main algorithmic contribution: the Joint Moment Estimation (JME) algorithm for solving the problem of differentially private (weighted) moment estimation in a continual release setting. Algorithm D shows its pseudo-code. JME takes as input a stream of input data vectors, the weights for the desired estimate in the form of two lower triangular workload matrices, and privacy parameters e, 6 O. Optionally, it takes two noise-shaping matrices as input. If these are not provided, C = C₂ In x. can serve as defaults.
The algorithm uses the matrix mechanism privately estimate the weighted sums of vectors for both the first and second moments. At each step, the algorithm receives a new data point, Hy, it creates private version of both x; and F, @ x, by adding suitably scaled Gaussian noise. The noise shaping matrices, if provided, determine the covariance structure of the noise.
To balance between the estimates of the first moment and of the second moment, scaling parameter, X, is used. In Algorithm I this parameter is fixed such that the total sensitivity of estimating both moments is equal the sensitivity of just estimating the first moment alone. This implies that the overall noise variance to make both moment estimates private is equal to that needed to achieve the same level of privacy for the first moment. Consequently, the fact that also privately estimate the second moment does not increase the necessary noise level for the first moment, a property we call (second moment) privacy for free.
Note that privacy for free is a quite remarkable property of JME. Generally, when using the same data more than once for private computations, more noise for each of them is required to ensure the overall privacy, following, e.g., the composition theorems of DP [26). some situations, however, one might also prefer more flexible way to trade-off between the two moment estimates. For this, present X-MME in the appendix (Algorithm 3). a variant of JME that has as a free hyper-parameter.
Heer and in the following we do not provide formula for o..6, because closed-form expressions have been shown to be suboptimal in some regimes. Instead, we recommend determining its value numerically, such as in [5). For reference, typical values of a.,s lie between approximately 0.5 (low privacy, e.g. e 8, 6 = 10 1) and 50 (high privacy, e.g. 0.1, d 10-9).
3

---

Properties of JME For some inputs X = (zi,..., zn) E Raxd let Y = (Yi....,
".....,,y,, Yx) E R and (Si,.... S.) Rax be the matrices of their first and second moments after each step, and let E Baxdd be the private estimates computed by
y (Y....., Y.) E Raxd and $ Algorithm with workload matrix A and noise shaping matrix C. Then, we have the following.
Theorem 3.1 (Noise properties of JME). Y and S are unbiased estimates of and Their estimation noise, Y - Y and Š - S, has symmetric distribution.
Theorem 3.2 (Privacy of JME). Algorithm| iis (e, 8) diffferentially private.
Theorem 3.3 (Utility JME), For any input X, let ca as defined in Algorithm Then the expected approximation error of Algorithu for the first and second moments are
B - 1 = ol lles
(3)
ElIS S11 2ç² 2c2 Voido S [C2111=21AA2C; '
(4)
where || -1l1-2 denotes the maximum lg column norm of the given matrix.
Proof of Theorem 3.1 The statement follows from the fact that for any t = 1,..., n, JME's estimates it of and It @ Ty of @ are unbiased with symmetric noise distribution because they are constructed by adding zero-mean Gaussian noise.
The result follows using Gaussian mechanism once we show that the overall sensitivity of jointly estimating both moments has most 2c]|Cil|1-2, Algorithm
Proof sketch of Theorem 3.2
stated in
Definition 3.4. For any noise-shaping matrices C1 and C2 and any À > 0, we define the joint sensifivity of estimating the first and X-weighted second moment by
sup x-x (
O vic,)
X-X (x xxx-Xx x"
1
sens (C1,C2)
(5)
sup [X (X) + x X-X
X-X' X')
The following lemma (shown in the appendix) characterizes the values of the joint sensitivity function of X.
Lemma 3.5 (Joint Sensitivity). Assume that the matrices C1 and C2 have norm-decreasing column Then, for any X >> 0 holds:
(C211C2211222
sens
||
where || 111-12 denotes the maximum column norm, corresponding to the norm of the first column of C1 and C2, respectively. The function ra(v) is given by
8 (3 - ()T + +++ with T = V -- 2,
ifv> 1145.5 d= 1,
ra(u)= =
2v 20
if 21 d> 1,
4,
otherwise.
Algorithm ! uses the scaling parameter X = /CClI sensitivity of estimating both moment has the value C2 The choice of implies
so, by Lemma 3.5 the
that ra(ca) = 4, which yields (Cn, = s. This concludes the proof Theorem 3.2
'The decreasing column norm structure ensures that the optimum simultaneously achieved for the first columns of the matrices C₁ and Cz. This can be relaxed by solving a maximization problem over the column indices, which could be done numerically. Moreover, the matrices that we have in mind for practical tasks are Toeplitz, for which the corm-decreasing property is fulfilled naturally.

---

4000
Second Moment Error
A-ME
3000
2500
1500
1000
400
500
600
700
800
1000 1100
1200
First Moment Error
Figure 1: Approximation errors for the 1st and 2nd moments across three methods (see text for details): X-MME with A, IME with varying a parameters, and CS with varying 7 parameter. A-JME Pareto-dominates the other two methods.
Proof sketch of Theorem 3.3 The identities follow from the general properties of the matrix mecha- nism. For any input X, the output of Algorithm 1 for the first moment is Ý Y A Z1, where Z1 [W00, 2 Consequently, Y A1 Z1, and hence
Ez, 18 YIF | c 1 o
(8)
Equation follows by inserting $ = 2c1|Cill1-22 For the second moment, Equation
follows analogously using that the output of Algorithm is S S X A= Z- with Za [W(0, o2 + p
3.1 Comparison with alternative techniques
Besides JME, alternatives methods are possible that could be used to privately estimate the first and second moments. In this section, introduce
of them and discuss their relation JME.
Independent Moment Estimation (IME). straight-forward way to privately estimate first and second moments is to estimate and privatize both of them separately, where the necessary amount of noise is determined by the composition theorem of the Gaussian mechanism the appendix).
|I (see Algorithm in
IME resembles JME in the sense that (i) separate estimates of the moments are created, and (ii) the privatized results are unbiased estimators. However, it does not have JME's privacy free property, This is because IME relies on the composition theorem, so the privacy budget is split into two parts, one per estimate, where the exact split is hyperparameter of the method. As a consequence, IME's estimate of the first moment is always more noisy, and thereby of lower expected accuracy, than JME's. For the second moment, IME could in principle achieve lower noise than plain JME by adjusting the budget split parameter in an uneven way. This, however, would come at the expense of further increase in the error for estimating the first moment.
The following theorem establishes that X-JME, the variant of JME with adjustable À parameter offers a strictly better trade-off' than IME.
Theorem 3.6 (JME IME). For any 8, > O, X-JME Parmnatds IME with respect to the approximation error for the first vs second moment estimates.
The proof can be found in the appendix. Figure visualizes this property graphically.
Concatenate-and-sphe (CS). In the special case where the two noise shaping matrices are meant to be the same (e.g. the trivial case where both are the identity matrix), it is possible to use single privatization step for both moments. For this, one forms a new observation vector, Σ; by concatenating I, with vectorized (and potentially rescaled version of) 2; 2 F;- Then, one privatizes the resulting vector, taking into account that F; E dRd((+)) has higher dimension and larger norm than the original Ji; IRd. The result is split again into first and second order components, and the latter is unscaled. The result are private estimate of 2; and 2, Zs, from which the two weighted moment estimates
5

---

Apgrosimation Entor
FP Get exedt
101
Aporoximation Error
Deb cind)
FP Dobiciedl to
10'
Approse
107
Approuimation
101
107
201
101
10"
164
55F sigmas
10
35-1
12-
sigmas
sigmas
sigmas
(a) d = 1, trivial
(b) d 1, square root
(c) d 10 trivial
(d) = 10 square root
Figure Expected error of second moment estimation with JME versus PP with and without debiasing (A = E1 (prefix sum),
1000) In line with our analysis, for d = 1 JME consistently achieves higher quality than PP. For 1000, JME is preferable to PP in the high privacy regime. Furthermore, the square root matrix factorization substantially improves the quality of both methods.
be constructed. Algorithm in the appendix provides pseudocode for this concatenate-and (CS) method.
When applicable, CS is easy to implement and produces unbiased moment estimates. However, like IME, it has an unfavorable privacy-accuracy trade-off curve compared to JME, as formalized in the following theorem and shown in the appendix.
Theorem 3.7 (JME vs CS). For any e, X-JME Pareto-dominates CS with respect to the approximation error for the first vs second moment estimates.
Figure 1 visualizes these cases (Theorems 3.6 and 3.7 graphically in an exemplary setting (d 10, n 10, C C2 = A = E,, 0.,5 1/2).
Post-processing (PP). Post-processing (PP) is another easy-to-use method for joint moment estima- tion. It has appeared in the literature [40]. least in its naive form without the matrix factorization mechanism. For any I;, it first computes private estimate 2, by adding sufficient noise to it. It then sets ② := & @ Er which is automatically private by the postprocessing property of DP, and uses to estimate the second moment matrix without additional privacy protection. Algorithm in the appendix provides pseudocode.
Like JME, PP has the privacy-for-free property, i.e., the private estimate of the second moment does not reduce the quality of the first moment. In contrast to JME, however, PP's estimate of the second moments is not unbiased because the noise that added the first moment is squared during the process. It is possible to compensate for this by explicitly subtracting the bias, which can be computed analytically. The bias depends only on hyperparameters such as n, d, and o, and not on the private data X or the sampled noise used to protect it. Its exact expression can be found in equation (60).
For given privacy parameters, PP and JME use the same noise strength toprivatize the first moment and therefore their estimates are of equal quality. For the second moment, their characteristics differ between the low privacy (small noise variance) and the high privacy (large noise variance) regime. To allow for quantitative comparison, we derive characterizations of the approximation quality of PP.
Lemma 3.8 (Expected Second Moment Error for PP). Assume the same setting as for Theorem 3.3 except that we compute the estimates Y and Spp with the PP method. Let Q C- and EQ (Q) diag(QQ) (T) Then, the expected approximation error of the second moment satisfies:
sup El|S Sp - 16d(d + XEX
tr(A, A
- +8(d+ < sup tr((A} A₂ Q)xx") +16d0 ( tr A₂Ea)
XEX
For debiased PP, the term marked "bias" does occur.
In order get a better impression of the relation between PP and JME, we first study the special case of trivial factorization.
Corollary 3.9. Assume that JME and PP trivial factorizations, iee, Ci C2 T. Then, JME's expected approximation error for the second moment is
E S - -11 = 4cad2o2 02 A|
(10)

---

and the corresponding value for PP is
bias
sup EIJS - -Sprll = (opll)=(66(((( (16d(d+1)e) 1) 8(d + 1002
+16d 25 Σ (A22)18 (A.)1
XEN
where (A2))) is the row-wise summation of A2. For debiased PP, the term marked "bias" does not occur
Proof. The proofs follow directly from Theorem 3.3 and Lemma 3.8 by observing that ||C
[|C2ll1-2 = 1. In dimension d = 1, Ç = 1, JME has an error of 4c10 |l versus (320 16a?, A2llé for (debiased) PP. Since c₁ < for one-dimensional data, JME's error is always lower than PP's (see Figure for visual confirmation). In high dimensions (d > 1), the terms quadratic in dominate, so the comparison is between 80 & Alll for JME and o6. AllA22lli for PP. Consequently, least for 5 V2* JME achieves privacy with less added noise than PP.
In the regime of low privacy (oe.5 5 0) high dimension (d > 1), PP can be expected to result in higher accuracy estimates than JME, because the terms involving o²,6 make only minor contributions.
For settings with general noise shaping matrix, we cannot provide an exact comparison between PP and JME, because the supx-tent in Equation (9) has no closed-form solution. Instead, derive upper and lower bounds (Lemma D.2), and provide a numeric comparison in Figure
4 Applications
To demonstrate potential uses of JME, we highlight two applications: private Gaussian density estimation, a classical probabilistic technique, and private Adam optimization, which is common in deep learning. The proofs for all theoretical results can be found in the appendix.
Private Gaussian density estimation The maximum likelihood solutions to Gaussian density estimation from i.i.d. data, Zi,..., It famously is p(x) = =N(x; μr, Ee). where μ4 = 1 Di z; is the sample mean and Σ, Ei (+)(2; Pa) is the sample covariance. Using the alternative identity Σ. = + N. Majua one sees that the task can indeed solved continuous release setting and that only estimates of the first and second moments are required.
To do so privately, we use the averaging workload matrix
(af) with at 1 for < S and of = 0 otherwise, and we compute private estimates ç == VX (private mean) and Σ
V(X x) - (VX) (VX) (private covariance) using JME.
Note that ş7 is simply the first-moment vector above. It is therefore unbiased and the guarantees of Theorem 3.3 holds for it. However, Σ is not unbiased estimate because in its computation the noise within VX is squared. However, is possible characterize the bias analytically and subtract it if required. We provide the exact expression for the bias in equation (75 in the Appendix, where the debiased version referred to as JME (Dehiased).
The expected approximation error of f is identical to the one in Theorem 3.3 with A = V and = C2 I. The following Theorem establishes the approximation quality of the covariance estimate. In this and the following sections we denote = 20,,5, referring to the strength of the noise we add the first moment for ( 1 and trivial factorization.
Theorem 4.1 (Private covariance matrix estimation with JME), Assume that all input vectors have norm at most 1. Let be the results of the above construction, where privacy is obtained by running JME with noise strength and debiasing. Then it holds:
sup Xex
E 51 = (cad? + 2d + 2)02 Hn, + d(d 1)0 Hn.2.
(11)
with ca as in Theorem 3.3 and Hnmm = Σ
1 km
k=1
For comparison, we also analyze the case where the PP method is used privatize the covariance matrix, Epp == v(X= x) - (VX VX), where X are privatized entries of X. Again, the resulting biased estimate can be explicitly debiased, see Appendix (93) for the expression.
7

---

The following theorem states upper and lower bounds on the expected approximation error:
Theorem 4.2 (Private covariance matrix estimation with PP). Assume the same setting as for
Theorem 4.1 Let Epp be the result of the above construction, where privacy is obtained by running PP with noise strength a and debiasing. Let (in,d,o) == d(d + 1)o d(d + 1) Hn, Hn, 2(d + 1)o² H.,.- Then, for the expected ervor of the covariance matrix estimate it holds:
S(n,d, o) 2(d + H S sup EI - Eppll < S(n,d,o) XEX
(12)
and for PP it is d(d + n), Given that Hn = O(log n). while Hn.m < 2 /6 for m 2 2, the error introduced by PP logarithmically worse than JME. Figure numerical plot that confirms this observation. Note that our results match the lower bounds established by G. Kamath 2020 [30]. who proved that private covariance estimation in the Frobenius norm requires (2(d)) samples.
Comparison, In the high privacy regime (a > 1), the leading term for JME is c(d +
Private Adam optimization
The Adam optimizer [32], has become de-facto standard for optimization in deep learning. The defining property of Adam is its update rule, 0; + 0,-1 - omn// (Vu,+ +e), where a is a learning rate, and m, and i/ are exponentially running averages of computed model gradients and componentwise squared model gradients, respectively. In the context of our work, these quantities correspond to a weighted first-moment vector and the diagonal of the weighted second-moo moment matrix.
Previous attempts to make Adam differentially private relied on postprocessing 4 36). potentially with debiasing [42]. i.c. they privatized the model gradients and derived the squared values from these. We demonstrate that JME's approach of privatizing both quantities separately can be competitive alternative. Algorithm iin the Appendix shows the pseudocode.
contains some modifications compared to the original JME. In particular, we adjust JME only estimate and privatize the diagonal of the second moment matrix, which reduces the runtime and memory requirements. Interestingly, as the next theorem shows, having to estimate only the diagonal elements of the covariance matrix does not reduce the problem's 's sensitivity, so privatizing the estimates remains equally hard. This implies that our previous analyses, including the relation the baselines, remain valid.
Theorem 4.3. The sensitivity of JME, with the whole second-moment moment matrix (C,X, VAC2X X), and with just the diagonal terms (C, VXC2X are identical.
The proof can be found in the Appendix A.3 It does not follow from Lemma 3.5 and is significantly more intricate.
As in the previous cases, JME's for free property ensures that its expected approximation error of the first moment is identical to PP. The following theorem establishes the expected approximation errors of both methods for the computed second moments (i.e. the diagonal of the second moment matrix):
Lemma 4.4 (Comparison of IME and PP for DP-Adam). Let D (VI,..., Un) be the matrix of second moment estimates of the Adam algorithm. Denote by D = ;,....,,))) the private estimate
of computed by Algorithm 2 with trivial fuctorization and noise strength a, and let Dep be the analog quantity computed by DP-Adam with postprocessing. Then it holds:
Ez D- D112 2do ||
(13)
sup Ez Dpp D112 (2do* + 40²) ||A2ll2 -do 1 (A2) XEX
(14)
where A2 is the workload matrix obtained from the coefficients of Adam's 's exponentially weighted averaging operations. The term marked "bias" disappears if PP is debiased.
The proof of the first part follows directly from Theorem 3.3 The error for PP is computed separately
in Lemma D.5 in the appendix.
This lemma shows that as long as 2 1, the error introduced by JME is strictly lower than that of PP
(i.e. classic Adam (36)) and even the debiased version of PP (i.e. AdamBB (42). Figure 5
illustrates the relation in prototypical case.
8

---

Average KL Divergence
15.0
Average KL Divergence
PP
(Debiased)
30
PP (Debiased)
JME
25
JME
10.0
JME (Debiased)
JME (Deblased)
15
5.0
2.5
5
0.0
100
150
200
100
150
200
Steps
Steps
(a) 5, n 200,
(b) d = 10, n = 200, =
Figure 3: Approximation quality of JME and PP for private Gaussian density estimation as average and standard deviation over 1000 runs. In the sigh-privacy regime (a = 2 and a 4), JME achieves lower KL divergence than PP after 25 10 samples.
5
Experiments
Our main contributions in this work are both algorithmic and theoretical. Specifically, JME general purpose technique for moment estimation, which is promising for some scenarios and less promising for others. However, and integrated into standard machine learning pipelines. To demonstrate this, report the experimental result using Algorithm and Algorithm in two exemplary settings, reflecting the application scenarios described above.
also a practical algorithm that can be easily implemented
Private Gaussian density estimation. From given data distribution, p(x) = N (M, E), we sample
n = 200 data points and use either JME or PP to form a private estimates, (z) = Np, Ex), each step ..... n. of the continuous release process. To ensure positive definiteness, symmetrize JME's estimated covariance matrices and project them onto the positive definite cone. As postprocessing operation, this does not affect their privacy.
Figure shows the results, with the approximation quality, measured by the Kullback-Leibler (KL) divergence, (L Ipp), at each step, t, average and standard deviation over 1000 runs, with NO, T2) and E ~ Wa { la. 2d) (i.e. a Wishart distribution) in each case. One can see that in the high-privacy regime (here: = 2), on average, JME achieves better estimate of the true density than PP, with and without debiasing.
45-
Accuracy (%))
DP-Adam-Cip
Accuracy
DP-Adam-JME
20-
DP-Adam-PP (Debiased)
35-
APamd
DP AP-Adam Clp
15-
30.
DR-Adam-JMM
DP AP-AAda-PP (Debiased) DP-Adam.PP
10
10
Epoch
Epoch
(a) batchsize B B 256, 1.7
(b) batchsize B 1, 0.16
Figure 4: Results of private Adam training on CIFAR-10 experiments comparing four methods:
DP-Adam based PP (with and without debiasing). JME, and joint clipping, over 10 epochs. Left: for low to medium privacy, JME outperforms vanilla DP-Adam but is slightly worse than the debiased version. Right: for high privacy, JME is slightly better than the debiased version, whereas vanilla DP-Adam cannot handle the necessarily amounts of noise.

---

Private model training with Adam. We train convolutional network on the CIFAR-10 10 dataset with DP-Adam, which is privatized either with JME or PP. Because gradients could have arbitrarily large norm, we apply gradient clipping to a model-selected threshold in both methods. In addition, we include a heuristic baseline that uses the pencatteate-and-spee techniques in which not the norm of the gradient vector but the norm of the concatenation vector is clipped. While inferior to JME in the worst case, this might be beneficial for real data, so we include it in the experimental evalution.
The results in Figure confirm our expectations: in a setting with small noise variance (large batchsize, low privacy), DP-Adam-JME achieved better results than standard DP-Adam, but worse than the debiased variant of DP-Adam. If the noise variance is large (small batchsize, high privacy). DP-Adam-JMa slightly improves over the other methods. For detailed accuracy results, see Table 2 in the appendix with hyperparameters provided in Table 3
Related works
The problem of differentially private moments (and the related problem of covariance estimation) has rich history of development, with optimal results known in the central model of privacy [41 as well as the local model of privacy [Л. and also in the worst-case setting. Sheffet [40] proposes three differentially private algorithms for approximating the second-moment matrix, each ensuring positive definiteness. The related setting of covariance estimation has been studied in the worst-case setting when the data comes from a bounded & ball by several works for approximate differential 38 43 with the works of Amin et al. [3] and Kapralov & Talwar [3]] presenting pure differentially private algorithm. Covariance estimation is also used subroutine in mean- estimation work under various distributional assumptions [29]. However, none of these approaches directly applicable to the continual release model and they offer improvements over the Gaussian mechanism only in a very high privacy regime. Precise sensitivity amalysis, as a technique to improve differential privacy guarantees, has also been intensively used in the literature [4 44 24 333 The
privacy 12 15 37
matrix mechanism has also gained a lot of attention recently due to its application of continually
releasing prefix sums in private online optimization g 25 39 20
28 18 [9
7 Summary and Discussion
In this work we studied the problem of jointly estimating the first and second moment of a continuous data stream in differentially private way. We presented the Joint Moment Estimation (JME) method, which solves the problem by exploiting the recently proposed matrix mechanism with carefully tuned noise level. As result, JME produces unbiased estimates of both moments while requiring less noise to be added than baseline methods, at least in the high privacy regime. We applied JME to private Gaussian density estimation and model training with Adam, demonstrating improved performance in high-privacy regimes both theoretically and practically.
Despite the promising results, several open question remain. In particular, would like explore if postprocessing is indeed the optimal strategy in a low-privacy regime, or if a better privacy- utility trade-off is still possible. Furthermore, we plan to explore the possibility of problem-specific factorizations, which could be fused with the proposed method.
Acknowledgments
We thank Monika Henzinger for her valuable feedback and insightful discussions on earlier versions of this draft. We are also grateful to Mher Safaryan for his contributions to discussions on DP-Adam. Additionally, we thank Ryan McKenna for suggesting Joint Clipping as a baseline.
Jalaj Upadhyay's 's research was funded by the Rutgers Decanal Grant no. 302918, NSF CNS 2433628, Google Research Scholar Award, and Google Seed Fund Grant. A part of this work was done while visiting the Institute of Science and Technology Austria (ISTA).
Nikita Kalinin's 's research was funded in part by the Austrian Science Fund (FWF) [10.55776/COE12]
10

---

References
[1] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy, In ACM Conference Computer and Communications Security (CCS), 2016.
[2] D. Achlioptas and McSherry. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM), 54(2), 2007.
[3] K. Amin, T. Dick, A. Kulesza, A. Munoz, and S. Vassilvitskii. Differentially private covariance estimation. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
[4] R. Anil, B. Ghazi, V. Gupta, R. Kumar, and P. Manurangsi. Large-scale differentially private bert. Annual Meeting of the Association for Computational Linguistics (ACL), 2022.
[5] B. Balle and Y.-X. Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning (ICML), 2018.
[6] A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the SuLQ framework. In International Conference on Management of Data and Symposium on Principles Database and Systems (PODS), 2005.
[7] C. A. Choquette- Choqueette-Choo, K. Dvijotham, K. Pillutla, A. Ganesh, T. Steinke, and A. Thakurta. Corre- lated noise provably beats independent noise for differentially private learning. In International Conference Learning Representations (ICLR), 2024.
[8] C. A. Choquette-Chooe A. Ganesh, R. McKenna, H. B. McMahan, J. K. Rush, A. G. Thakurta, and X. Zheng. (Amplified) banded matrix factorization: A unified approach to private training. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
[9] C. A. Choquette-Choo, H. B. McMahan, Rush, and A. Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In International Conference on Machine Learning (ICML), 2023.
[10] S. Denisov, H. B. McMahan, Rush, Smith, and G. A. Thakurta. Improved Differential Privacy for SGD via optimal private linear operators on adaptive streams. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[11] C. Duchi, M. Jordan, and M. J. Wainwright. Local privacy and statistical minimax rates. In Symposium on Foundations of Computer Science (FOCS), 2013.
[12] K. D. Dvijotham, H. B. McMahan, K. Pillutla, T. Steinke, and A. Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In Symposium on Foundations of Computer Science (FOCS), 2024.
[13] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In Symposium on Theory of Computing (STOC), 2010.
[14] C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.
[15] C. Dwork, K. Talwar, A. Thakurta, and L. Zhang. Analyze Gauss: optimal bounds for privacy- preserving principal component analysis. Symposium on Theory of Computing (STOC), 2014.
[16] A. Esteve, E. Boj, and J. Fortiana. Interaction terms in distance-basee regression. Communica- tions in Statistics Theory and Methods, 2009.
[17] H. Fichtenberger, M. Henzinger, and Upadhyay. Constant matters: tine-grained error bound on differentially private continual observation. In International Conference on Machine Learning (ICML), 2023.
[18) M. Henzinger, N. P. Kalinin, and J. Upadhyay. Binned group algebra factorization for differen- tially private continual counting. 2025. arXiv preprint arXiv:2504.04398

---

[19] M. Henzinger, N. P. Kalinin, and J. Upadhyay. Normalized square root: Sharper matrix factoriza- tion bounds for differentially private continual counting, 2025. arXiv preprint arXiv:2509.144 143344
[20] M. Henzinger and J. Upadhyay. Improved differentially private continual observation using group algebra. In Symposium on Discrete Algorithms (SODA), 2025.
[21] M. Henzinger, J. Upadhyay, and S. Upadhyay. Almost tight error bounds on differentially private continual counting. In Symposium on Discrete Algorithms (SODA), 2023.
[22] M. Henzinger, J. Upadhyay, and S. Upadhyay. A unifying framework for differentially private sums under continual observation. In Symposium on Discrete Algorithms (SODA), 2024.
[23] S. Ioffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), 2015.
[24] M. Joseph, M. Ribero, and A. Yu. Privately counting partially ordered data. In International Conference Learning Representations (ICLR), 2025.
[25] P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and 7. Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning (ICML), 2021.
[26] P. Kairouz, S. Oh, and P. Viswanath. The composition theorem for differential privacy. In International Conference on Machine Learning 2015.
[27] N. Kalinin and C. H. Lampert. Banded square root matrix factorization for differentially private model training. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
[28] N. Kalinin, R. McKenna, J. Upadhyay, and C. H. Lampert. Back to square roots: An optimal bound on the matrix factorization error for multi-epoch differentially private sgd, 2025. arXiv preprint arXiv:2505. 12128.
[29] G. Kamath. The broader landscape of robustness in algorithmic statistics. arXiv preprint arXiv:2412.02670, 2024.
[30] G. Kamath, A. Mouzakis, and V. Singhal. New lower bounds for private estimation and generalized fingerprinting lemma. Conference on Neural Information Processing Systems (NeurIPS), 2020.
[31] M. Kapralov and K. Talwar. On differentially private low rank approximation. In Symposium on Discrete Algorithms (SODA), 2013.
[32] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations (ICLR), 2015.
[33] C. J. Lebeda. Better Gaussian mechanism using correlated noise. In Symposium on Simplicity in Algorithms (SOSA), 2025.
[34] C. J. Lebeda and L. Retschmeier. The correlated Gaussian sparse histogram mechanism. arXiv preprint arXiv:2412. 10357, 2024.
[35] C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi. The matrix mechanism: Optimizing linear counting queries under Differential Privacy. International Conference on Very Large Data Bases (VLDB), 2015.
[36] X. Li, F. Tramer, P. Liang, and T. Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations (ICLR), 2022.
[37] O. Mangoubi and N. Vishnoi. Re-analyze Gauss: Bounds for private matrix approximation via dyson brownian motion. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
[38] O. Mangoubi and N. K. Vishnoi. Private covariance approximation and eigenvalue-gap bounds for complex Gaussian perturbations. In Workshop on Computational Learning Theory (COLT), 2023.
12

---

[39] H. B. McMahan, K. Pillutla, T. Steinke, and A. Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In Symposium on Foundations of Computer Science (FOCS), 2024.
[40] O. Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory (ALT), 2019.
[41] A. Smith. Privacy-preserre statistical estimation with optimal convergence rates. In Sympo- sium on Theory of Computing (STOC), 2011.
[42] Q. Tang, Shpilevskiy, and M. Lécuyer. DP-AdamBC: Your DP-Adam actually DP-SGD (unless you apply bias correction). In Conference on Artificial Intelligence (AAAT), 2024.
[43] J. Upadhyay. The price of privacy for low-rank factorization. In Conference on Neural Information Processing Systems (NeurIPS), 2018.
[44] A. Wilkins, D. Kifer, D. Zhang, and Karrer. Exact privacy analysis the Gaussian sparse histogram mechanism. Journal of Privacy and Confidentiality, 2024.
13

---

well as A Proofs of the main theorems
In this section, provide proofs of Theorem 3.2 and Theorem
3.3 from Section
3
Theorem 4.3 from Section
A.1 Proof of Theorem 3.2 and Lemma
The privacy of Algorithm D follows from the properties of matrix mechanism [35 with precise
estimate the senxitivity the joint estimation process that we will introduce and discuss later in this section.
By means of the matrix factorization mechanism with A B1C1 and A2 B2C2, we write the joint moment estimate as,
Y 1 B o - B2) (03)-(xx+13)
0 (09)
) (Gx A+Cx(X,
(15)
where À 0 is arbitrary trade-off parameter that will adjust optimally later. To make the estimate private, we privatize the rightmost matrix in (15), which contains the data, by adding suitably scaled Gaussian noise. The subsequent matrix multiplication then acts private data, its result is also private.
It remains to show that the noise level specified in I suffices to guarantee (c, --privac
For this, we denote by X' = {(......, .n,) max, ||2, S S E Rd} be the set of input sequences where each d-dimensional vector has bounded & norm. The sensitivity of computation the maximal amount by which the result differs between two input sequences X, X' e X, which are identical except for single data vector at an arbitrary index (denoted by X X').
For JME, the relevant sensitivity is the one of the matrix we want to privatize, i.e. (in the squared form)
X-X X' (ov/c.) (x
sen, sup X-xi
xox-X X' X'
Sup[IC((X-X))) X') X||C2(X X' x~x!
X
(16)
Due to the linearity of the operations and the condition imposed by X X', most terms in (16 cancel out and the value of sens C2) simplifies into the solution of the following optimization problem.
Problem 1 (Sensitivity for Joint Moment Estimation).
max max
af
|| v1 +
(17)
||
where af = |I(C1):112 and B I1(C2);1l are the column norms of the matrices C₁ and C2, respectively.
To study Problem I we introduce as an intermediate object the formulation of in the special case of Ç = 1 and 0; 33 for i = 1, ..... n. treated as function of A:
ra(A)= max ||. v1 > y 2 vl 2
(18)
$1
11
The following theorems provide specific values for ra in the special case of 1 (Theorem A.I and for general d > (Theorem A.2
Theorem A.1 (d = 1). For any À > 0, holds:
i
11+5V4
(A)
(19)
1/ (3- 7) +1+A)
otherwise.
where T V1-2/1 Moreover, the function r (A) is a continuous function with respect to the parameter X > 0.
14

---

Theorem A.2 (Joint Sensitivity for Moments Estimation), For d >> 1 and À > 0:
4
if X 1 2:
(a(A)
(20)
2 2X
otherwise.
The proofs both theorems can be found further in the appendix. Theorem A.1 requires only straightforward optimization. For theorem [A.2 rewrite the Frobenius norm of the difference of Kronecker products and optimize over all possible values for (z. y)-
As corollary of Theorems A.1 and A.2 Problem T
we obtain characterization of the general solutions to
Corollary A.3 (Solution to Problem 1. Assume that the matrices C1 and C2 have norm-decreasing columns. Then, for any scaling parameter À > 0, it holds that
sens C2) (aa //a))
(21)
where va is specified in (99 or (20). and of and 87 are the squared norms of the first columns the matrices Cj and C2, respectively.
Proof. A straightforward calculation shows
sens C2)
sup == |= ISc
a 2/11== 10l1--y1::0 A3
X -
sup
| - vl12 +
x 0 x 1
v
(22)
||
ai
= ((a /
completing the proof of Corollary A.3
Corollary A.3 Simplies that the joint estimate
will be (c. -private, if we use noise of strength least, (arrra(A( 91/ox /on Ja..,, where ac.8 the noise strength required for the Gaussian
15
mechanism with sensitivity 1. This finishes the proof of the Lemma 3.5
The claim of Theorem 3.2 3.2 because Algorithm corresponds exactly to the above construction. only making use of the identity B(CX + Z) = A(X C-- 2), and for the special case of := X defined as
X of
(23)
37
with Cd = 2 > 1 and 11+5V5 for = 1, which the smallest values for A, such that
A 4. The sensitivity is then equal to sens (C1, C2) 2Ça1 2c||C1 111-2, where the of last identity holds because of C1 's decreasing column norm structure.
Td
We furthermore note that this value is exactly the sensitivity of estimating the first moment alone,
because
max X-XI
|
max max 0s a
y11² 4a
(24)
I....
This means that JME estimates the second moment without increasing the noise for the first moment, proving claim that obtain the second moment privacy for free.
A.2 Proof of Theorem 3
To prove Theorem 3.3
we have determine how the left-hand side of (5)) changes in expectation due to the added noise on the right-hand side. Due to the additive nature of the moment estimation process, we can do so explicitly.
For 21 ~ (o( it holds that
Ez|Y -
- =
(25)
15

---

Inserting B1 I and = 210e,6l|Ci111-22 Equation 3 follows. Analogously, for Zz ~
[W [W(0,o'1)dxe
1
d²o² B2Zz
Ez = = Ezll VX-
B lF.
(26)
X=
With o as above, Equation follows from B2 AzC2 and JME's specific choice of X 10
[0all
A.3 Proof of Theorem
The proof of Theorem goes similarly to 3.2 but now we estimate only the diagonal of the second moment matrix. We will show that the sensitivity remains unchanged by proving that the corresponding function (A( (18) also remains unchanged. Specifically:
diag (A) = sup
|| - u112 + >|| diag(2 @ 2) - diag(y @ 8)) = rr(A)
(27)
| las1
For simplicity, denote
diag( (x: @ x:).
In dimension 1, the two functions are identical by construction. In dimension d 2, we compute the new function explicitly using the following lemma:
Lemma A.4. Consider x, E I22, and let >> then,
diag (A) = 1
sup
[| - y112 o - yo
[4 12+21
if 1
2
(28)
| 11l
2X
if 2'
Next, we use dimension reduction argument to prove that diae (A) = diag (A) for all 2 2, via the following lemma:
Lemma A.S (Dimension Reduction). For any vectors x. y Rdd where dl 2 there exist vectors
x v E Rd-1 that for any X > 0 satisfies the inequality:
x
Al r ox y 211 S || - y + A||2 o x' - y o o/1122
(29)
We apply this lemma recursively to prove that r (A) lemma can be found later in the appendix.
diag
12
ding (A) for all 2 2. The proof of the
By combining these lemmas, we conclude the proof the theorem.
16

---

B
Additional materials
1611
Approximation Error
Approximation Error
(Deblased)
(Debiased)
10a
JME
10"
JME
107
107
10a
10º
10a
103
10
10a
10-2
10-1
10.
10a
sigmas
Sigmas
(a) trivial factorization
(b) square root factorization
Figure 5: Expected eтror of the estimated covariance vector for Adam with JME versus PP (d = 10%; 1000). JME provides better estimate in the mid high privacy regime.
PP lb
PP
Variance Error
10a
(Debiased)
Variance Error
10*
JME (Debiased)
PP (Debiased)
(Debiased)
10a
10a
101
10a
10a
10-1
10c
10:
10-1
10c sigmas
sigmas a
(a) 1, 1000
(b) 100, n 1000
Figure 6: Expected еπrог of the estimated covariance matrix with JME versus PP (with trivial factorizations). For d 1, JME consistently achieves quality better than or on par with PP. For d 100, JME is preferable to PP only in the high privacy regime.
201
201
20F
129
Approsimation Ereer
Abpp Perrocmmett comormtttoonn Enrer
127
Agprosimation
Approsemation
33" sigmas
32*
(a) d 100, - 0.9, C1 C2
(b) d 100, 8 0.9,
(c) d = 100, w 10, (d) d = 100, 10,
C = C2 = A 1/2
C C2 =
C C2
!/2
Figure 7: Expected error of second moment estimation with JME versus PP under different workload settings. The scenarios include exponential decay (8 0.9) and sliding window (w 10) workloads and d = 100, n 1000, both trivial and square root matrix factorization. In line with our analysis, incorporating matrix factorization significantly improves the quality of both methods, particularly in the high privacy regime.
17

---

Table 2: CIFAR-10 10 experiments with two different privacy budgets, e R 1.7 and s3 0.16 for 6 10 for four methods: DP-Adam with and without debiasing, JME, and Joint Clipping. The average and standard deviation errors are based on 3 runs.
Method
Epech
Epech
Epech
Epoch
Epock 5
Epoch 6
Epock
Epoch
Egoch
Epoch 10
21:25
28.30
0.36
25.78 0:70
- 0.55
2620 0.65
17.46 -:000
25.14
38.55 119
DPAAlm
10 25 0.511
10300400.55
10:5 0.56
10:54:000 0.35
10.19
-0:30-0000
10413 0:73
10:45 1:17
10.45 1:7
10:08 D8S
30.51
40.60 0.775
42:8:20.4
0.73
-..52-0.50
=0.00
0:23
44.76 0:26220222
44.44
54.21 1 0.95
41.58
1:54
45.20 0.41
46.91 1:25
48.06 0:36
46.38-008
48.26
2: LBs
48.36
42.81 1.075
68.53
DIAAm
26.55 039.2:044
3148 a 043
38.0
1.6
26.99.0..31
3 6.6
3:31
4833
1.333
41.41 1:
42/42..000
4300) 1: 0.56
Table Hyperparameters for CIFAR-10 Experiments. Medium-privace experiments use batch size of 256, compared to 1 in the high-privacy regime, while using noise multiplier of σ2, = 1 for the coddium-privase regime and σ.,6 8 for the high-privacy regime, JME and joint clipping require an additional hyperparameter-scallee which is optimized to find the best value for those runs. We also find it helpful to clip the updates; for this, we use the same clipping norm.
Noise Mult Batch Size Method
Ir
Scaling () r)
eps
Clip Norm
DP-Adam-IME 10-3
10-6
DP-Adam-Clip
10-3
0.5
10-6 6
e R 1.7
256
10
10
DP-Adam
10-3
10-8
DP-Adam-JMa
10
10
DP-Adam- Adam-Cllip
10
0.5
10 10-7
0.16
2
Op-AAam-Debiar
10-7
10-7
DP-Adam
10-7
10
18

---

C
Algorithms
Algorithm 2 Differentially Private JME Adam
Input: Initial model 0g E Fd dataset D. batchsize b, matrices Caa Cg. R model loss E(0, d). clipnorm Ç, noise multiplier σ., 2 0, learning rate a >> 0, and parameters 31 = 0.9, f2 = 0.999, & = 10-a
mo
first moment initialization.
00 -
// second moment initialization.
X, SA JJinn-senss Cap C3a)
// joint sensitivity
Z1 Z2 (0, 5
// noise generating
for i 1,2,.... do
S. + {di,..., dm} C select a data batch
9j - Vol(0,-11 11, 1,)) for ,,...,,
H2 - ΣØ=1 min (ainnli//llg//.... 1/11/111,111
G, - H₁ + c/c,, 3, [t.)
22, o + -1 Z2]
8g
m, f- m4-1 + (1 T
6- 32 + (1
B2)x2,
m. mi/ (1 8)
bias-correction // biascccorecttio
1/ /// -32)
0: 4 0
aam/(V/t) +
end for
Ensure: θ (01....,0,) 0n)
Algorithm 3 A-JME
Require: input stream vectors Ti...., In E Rd with ||æz|l2 < ( for Ç > 0 workload matrices A1 (a ) Ag = (b)) R=*0
Require:
Require: noise shaping matrices C1, C2 (lower triangular, invertible, decreasing column norms) (default: Iax))
Require: privacy parameters (c
o.,6 noise strength for (c, dd Gaussian mechanism
1/2
C||Gilli-221
// joint sensitivity
|C
Z1 [N(0, o² o0)
// 1st moment noise
Z2 [N a² 52
nxdxd
// 2nd moment noise
for t = 1.2..... do
................................
f - I4 + C Z [t.]]
It 24 2 X X- 1/2 Z2]
yield
p Σ 5
S. = Σ
Te & o*
k=1
end for
19

---

Algorithm 4 a-IME (IME with budget split parameter (0.1)
Require: input stream of vectors 2i,....
Rd with ||æ]|l S Ç for Ç > 0
Require: workload matrices A, = (af)), ) Ag = (bg) E Rexa
Require: noise shaping matrices C1, C2 (lower triangular, invertible, decreasing column norms)
(default: Iaxn)
Require: privacy parameters (c.
Require: a +- noise strength for (e. 8) Gaussian mechanism
Require: privacy trade-off (0, 1)
01 Va
81
211121
I/ sensitivity of 1st moment
21 ((8)) axd
// 1tt moment noise
02 Vi-a
82 V2 12c2 122
I/ sensitivity of 2nd moment // 2nd moment noise
Z2 [N(0, 22)))
axdxd
for t 1,2, ..... do
f. - 14 + |CT 71 [t..]
It 2 z₁ t 21 Zt
[02 [2l
yield
-= Σ o
S, = Σ
2 @ ok
==1
k=1
end for
Algorithm 5 7-CS (CS with 2nd moment rescaling parameter 0)
Require: input stream of vectors T1.
Rd with
Require: workload matrices A (at) e Ruxn
Require: input dimension d, bound on input norm Ç >> 0
Require:
privacy parameters (c.
Require:
(optional) noise shaping matrix C' (lower triangular, invertible, decreasing column norms) (default: Inxx)
0c,8 < noise strength for (c, d) Gaussian mechanism
+ 2(11 +52
sensitivity based norm of concatenated data
Z ~ [
axd(d+1)
// noise matrix for concatenated data
for t = 1,2,...,... do
F. = Tt, VTec( x, @ xx))
Ft Ey |C- []
yield
P Σ a p4 1ad
S. VF k=1
Σ bg (aaa)aaa
k=1
end for
20

---

Algorithm 6 PP
Require: input stream of vectors 31, .......... Jn Rd with ||æ|||2 s ( for ( > Require: workload matrices A₁ = (ak) A2 = (bf) E R
Require:
noise shaping matrix C₁ (lower triangular, invertible, decreasing column norms) (default: Iaxn)
Require: privacy parameters (e, 8)
0,,5 noise strength for (e, dd Gaussian mechanism
- 2c][Cill12>
I/ sensitivity of 1st moment
7 [N(0,02, 22) axd
// 1st moment noise
for t 1,2, do
f: + It + [ [|.t.]]
laxd x o. Ci
Σ
(CICT
bias term (optional)
k=1
It x + 84 8 f. be
t S. Σ
yield
-- Σ oi
2 2 ok
k=1
end for
21

---

D Technical Proofs
Definition D.1 (Face-Splitting Product). Let A (a Y== with as R& and (6]);= with E R The Pace-Splitting Product of A and B, denoted by A B, is defined as:
A (a: b, b,) (vec(a, ))=
(30)
where & denotes the Kronecker product, and vec denotes vectorization.
The result is matrix of size x (d1d2), where cach corresponds the vectorized Kronecker product a, and b; A few properties the Spelttppiniing Product that we will use further:
Bilinearity (B + C* A B A C' and (A B)+ + A
Associativity (A B) * C = A C).
Frobenius norm |A B| = |B Alle, even though A B + B A.
D.1
Bounds on the expected approximation error for PP with non-trivial factorization
Lemma D.2.
| S sup tr ((A) A2 C XXX) S o
(31)
xex
Proof of Lemma D.2 The proof elementary. For the lower bound. consider the specific choice for X (.),..., (nn) with all rows identical with ||x;|] = 1, such that X.X is the constant matrix of
all 1s. For the upper bound, we observe that [XX k. E [-1,1],, so
ir ((A} C )xxx) Σ[A] Ao C C CT T | bss S Σ
[Ag o
CT
i.j
(32)
Theorem A.1 (d = 1). For any X > 0, it holds:
(A) 4 (3 +1+
if 11+5v'
(19)
otherwise.
where VI- Moreover, the function T (A) is continuous function with respect to the parameter 0.
Proof. We recall that the function rı ri( is defined
ri (A) = sup [ x(xx2² ) |a|
(33)
Given the difference it is increasing function of + y therefore without any loss of generality can assume = 1. Then the derivative of this expression would give us
2(r - 1) + 21(x2 +))
(34)
The optimal value will depend on the roots of the quadratic polynomial. The determinant is 4X2 - 8A therefore for < there are no roots, the function is decreasing on the segment [-1, 1] reaching its
maximal value at = -1 with the value 4. Otherwise we have the following roots -1#/1-2/A We observe that for large > I we have the optimal x = 0 which corresponds the maximal value for
the second term. The maximum could be in both = -1 and -1+ -1+v112/7 therefore we will need to compare them. By substituting it into the expression get { 3) + 1 A), where = v 2/X. should compare this expression with find boundary when x -1 an optimal solution.
2
22

---

(7
(35)
We express 1/A 1
Therefore get the following inequality of variable 0 5 1:
1-72
1 1-
(7 (T
+
(3 -0--)-1------1--1------------1--
2
16
(1 + 7) [27 - 27- 2 - - + 327] (36)
16
1
(1 + + 107 + 50
16
Which is less than 0 for 7 < 2v5 s 11+5y5 = 2.77 which concludes the proof.
Theorem A.2 (Joint Sensitivity for Moments Estimation). For d >> and À >> 0:
[4 2 + 2A + 2A
if x 1 otherwise.
(a(A) =
2
(20)
Proof. First, decompose the Kronecker product follows:
x 1002 x - yul ||x=" yy² 11 tr(xx' xx²" - tr(xx" "orr"y"))> + vr(vvTrr²)
(37)
||0:12 + |byl - 2(xr, 2)
Similarly, the squared norm of difference is
| - v12 = | + 1lv122 2(x, v)-
(38)
Therefore, the objective function becomes
| - y/1 + a|| 69 x &
vl? = | 11 11v122 + || + Ally 13 2(x, y) 2X(x, u1 (39)
The first four terms are maximized when ||>||| = |l = 1, yielding 2 2\. The last two terms can then be optimized independently over the scalar product (x. in dimension d >> 1.
Let (z. .). where -1 < 1. The expression -23 2232 maximized at f = 1 when when 1. B 11, then -y and the objective function becomes 4. 2X the objective function is equal to 2 + 2A + 1 which concludes the proof.
1.4 or at
2X
Theorem 3.6 (JME IME). For any 8, X-MME Pareto-dominates IME with respect to the approximation error for the first vs second moment estimates.
Proof. We begin the proof with the following observation: X-JME and IME introduce additive noise to the first and second moments. Therefore, for the Frobenius approximation error, is sufficient to compare just the variances of the noise introduced by those methods. We use an instance of Gaussian mechanism, and the privacy guarantees are more appropriately characterized by the notion of Gaussian privacy. For the sake of the proof, assume that (e, dD- is equivalent to μ-GDP for a specific choice of μ. The sensitivity of X-JME depends on the dimensionality. Here, we assume d > 1 to address the hardest case, as d = 1 follows trivially.
To estimate and x @ æ simultaneously in a differentially private way via composition theorem, we need to split the privacy budget between the components. Using the Gaussian mechanism, we split the budget as -DPP for the first component and P2-GDP for the second component such that u + pē 2 The squared sensitivity of is 4 and the squared sensitivity of x & is 2
23

---

assuming | S Ç. Therefore, the variance of noise added to the first and second components is given by:
A5²
2
(40)
P 1 p4
Our analysis for JME yields the pair of variances, for 2ç2 2 4.
(2 2
(2 + 2XÇ² 2XC
ZAC
(41)
12
We aim to show that for a given variance the first component, our variance for the second component smaller. Specifically, we need to prove:
(2 + 2x + 2X
4ç²
(2 +
2x
where
(42)
2112
122 1
?
422
By substituting - 11
=
AC
into the inequality, obtain:
8XÇ=
2XC²
(43)
2 + 2AÇ + 2X
+
AC 2
2
8A2
Multiplying both sides by the denominator yields:
2xc² 2 2X
4.
(44)
2XÇ
Simplifying, we find Xc² > 1. which satisfied by the initial assumption.
Theorem 3.7 (JME vs CS). For any e, X-JME Pareto-dominates CS with respect to the approximation error for the first vs second moment estimates.
Proof. We begin the proof with the following observation: X-JME and CS introduce additive noise to the first and second moments. Therefore, for the Frobenius approximation error, it is sufficient to compare just the variances the noise introduced by those methods. We use an instance of Gaussian mechanism, and the privacy guarantees are more appropriately characterized by the notion proof, we assume that (c. d is equivalent to μ-GDP for specific choice of μ. The sensitivity of X-JME depends the dimensionality. Here, we assume >> to address the hardest case, as d = 1 follows trivially.
of Gaussian privacy. For the sake
We aim to show that Joint Moment Estimation (JME) introduces less noise to the (r 8 x) component than CS under the same privacy budget f-GDP. Specifically, we compare the variances in the second coordinate under the assumption that the noise variances in the first coordinate are equal.
The combined vector of x; and 2 x; be represented as:
(Ii, VT @ Xx))
(45)
where 0 is scaling parameter. If the input vectors z; bounded by ||r;|12 S Ç, the resulting vector will have le norm bounded by v + TÇ4, The squared sensitivity of the vector therefore: 4c²(1 + T2)). This results in the following variances for the first and second coordinates under noise
addition:
(1221 +(3) 45 (P(1+75))
(46)
122
TH2
For JME, we analyze the variances and obtain the pair variances as:
(2 + 2
x (2 + 2 x(x
(47)
12
X
where we assume <2>2
24

---

To compare the noise introduced to the second component, we aim to show:
+ 2
(1+
(48)
Ap²
TØ²
under the condition that the variances in the first component are equal:
(2 2 x
(1+
(49)
4²
4²
Given the equality, inequality is equivalent to X > Simplifying the equality in the first component gives:
1
2 2+2 +
+ 475
(50)
2C²x
Rearranging terms, we isolate 2(ax²
1 2 2(27 A
(51)
2
From the assumption <²> 2 1. we know that / < 1. For this inequality to hold, the term 2 + 2 - X) must also less than 1. Therefore, 2T À < 0, therefore т.
Thus, we conclude that for the same variance in the first component, JME introduces less noise variance the second component compared CS.
Lemma 3.8 (Expected Second Moment Error for PP). Assume the same setting for Theorem 3.3 except that we compute the estimates Y and Spp with the PP method. Let Q CT
and
Eq diag(Q Q) diag(Q)). Then, the expected approximation error of the second moment satisfies:
S|S Spr 112 = 16d(d + o Ar
sup XEX
bins
- 8(dd+
sup tr((AA A2 Q)xx²) +16do 2,65 11 tr Ag xex
For debiased PP, the term marked "bias" does not occur.
Proof. We aim to evaluate the expected squared Frobenius norm of the error:
sup ((X + CT 21) (X + (z)) A2(X x) XEX
2 sup E|i A1|A2((X X CT 1
+2 sup E(A2(X . A2) X))r
XEX
XEX
(52)
S2
A2l(A((CT 2i)
(CT
We compute those terms separately. We add component-wise independent Gaussian noise Z, (O, o²) to the first moment, where = 2(0.,6-
25

---

Step 1. Bound S1.
S sup Xex
12 X 11)
(A2) D(oT)arrZil
sup
E
XeX
k 2.
(A)),, (A2)k, X Σ (CT (t.,
= ssup
X
k=1
1.7 f1
(53)
d n
= sup
Σ (A2)),t) (A2) X Σ (CT
XEX
k= bj 4,5t2
= do'ICiili
((Ag )t. (AD)es) X
Xxx ((C )(. (CT))²2
sup XEX 11.22
do
sup tr((A3 A2 Q)Xx²) XEX
where Q= -C
Step 2. Bound S2.
S2 sup (A2 + CT A2), x))rr XEX
Σ [AA (EAA))ec Z1)es
sup
E
XeX
k=
1.
\=1
n
sup E
(A (1)
(A)k Zidean
(54)
XEX
k= i.j f2
n
sup E
Xe, (A))) Zta
XeX
j=1
sup B A2 (X CT 1 Si XEX
dd
d
Step Bounding S3 We expand this term:
S3 = 1| 1 21) (CT 2:)
2
(CT (z)ees
E
(, Zi)iss
A2)x, (b ( (55)
E
k= $1.9 3.3
(Az)k. (Az)ket
1=1 do
n
(A2)k.t (A2),, Σ
B(C " Zz)
k=16
1.
26

---

We now deal with two cases. When i = j, we compute:
B ' (CT (CT' 21)E
E Σ CTT (C (r + Σ (CT (CT,, (
r1#12
+ 2E
Σ
(CT ( (CT )000) (CT))
12. (CT (CT (Zi)
( (Z))
r1
(56)
= -300||Ci 1 Σ (CT (CT -fIiillii Σ (e (CT
r=1
112t2
+ +20"||Calli-2
Σ (Ci ( (0r Jenrs(Ci (CTT))ao)
r1712
= =o'|ICilli-220 Urans - 20 2C
On the other hand, when + j. then
"
2
B(C A I Z),, Z1)ta. =
)carr)
=o'|(Cilii-20
(57)
Using equation 566 and equation (57) in equation 55
we get
S3 = A2 (CT 21))(() (CT
2)))
= -d0 ΣV > (A2),,) (A2) (Qn,, Qra,s + (d 1)Q
k= 21
(58)
do'ICCili-o
Σ (A2)a.) (A2) (Qt Qr2,1 + (d 1)Q
k= 41.29
= do'ICCili tr A2 + d(d 1 tr A2 - Q)),
where Eq = dQag(Q) diag (Q).
Adding equation
53
equation
55
we obtain:
E|S Ser / d(d 1) tr(A] o
sup xex
2(d + 1)03 | sup tr((A} Ag Q)XX)
(59)
XeX
do' ATAAAA,E0)
Bias Correction.
The expectation of A2((CT (CTTICC))laa... introduces bias:
n
[EA2((CT Z1) Zi))k.as IE > (A2).,
D(C
t=1
= =
(A2) (C
=0 Σ (A2)
(60)
27

---

The Frobenius norm of this bias is:
d - ΣΣ> Σ (A2)a,, (A2)k, 2is Otzits
(61)
k= ==1j=110 11.22
=do"|C tr A2
If we subtract this bias from the estimate, will increase the error by the aforementioned quantity due to the Frobenius norm of the bias but will decrease the eπror by two scalar products with the A2((CT Z1) * (CT' Z))) term:
((A2((CT z1) (CT (A, Z1) (CT k))) | (1) (C ZI) (T
(62)
Thus, we can eliminate the last term (do*IIC 11 tr(A] AzEa)) in the error sum via bias correction. Substituting back = 2Ç0 we obtain the proposed equality.
We collect some useful proposition that would be useful for our analysis.
Proposition D.3. Let and X be given fixed matrix and Z be a Gaussian matrix of appropriate dimension. Then
EzI V2 d(d + 2)
(63)
k,t
Proof. Recalling the Face-Spll Sicce-Spitting product, we have
2
2
n
Ez V2 VZ
Ez
(VZ)
Ex Σ
Σ
V V Zei
Σ Zen
1=1
k=1
d
d
2
30 4
V + ΣΣ
Σ Vi,
+ 30
V2 V2.e
k= EgjJ
k= t=1 jit
= d(d + 2)0
(64)
This completes the proof of the proposition.
L
Proposition D.4. Let V and X be a given fixed matrix and Z be a Gaussian matrix of appropriate dimension. Then
Ez (VX))))( = 1 V2,, VX
(65)
Proof. The result follows using the following calculation:
d
Ez (VX). (VX) - (V2))
Ez
V k..) (V
1=1 i
Ez
(V (VZ)),;(VX)))
(66)
k=1
x
n
2
(VX)2 M.j
d E2l E2 VXI2
j=1
completing the proof.
28

---

Theorem 4.1 (Private covariance matrix estimation with JME). Assume that all input vectors have norm at most L. Let E be the results of the above construction, where privacy is obtained by running JME with noise strength a and debiasing. Then it holds:
sup XEX
E - - = (cad? + + 2) Hn, + d(d + 1) Hn.2
(11)
with ca as in Theorem 3.3 and Hn,m =
Σ
1
kmn k=1
Proof. We first recall that, if Z (H, Σ), then for any matrix A, we have AZ N(AA,, AEAT).
This implies that, when = and = 0, we have
A = ||A||/
(67)
Recall that f = (1 is a running mean and 3 = V(X (()(x ((-
[1)) is rumning covariance matrix, with independent noise Z1, Z2 =2(00 the clipping norm Ç I. and À X c7 as defined in equation (23) Using the associativity of Face-splitting
product and the Pythogorean theorem, we have
Ez, (V X + - - (V(X Z1) V(X + 2)) V(X X) + (VX) (
= -z |1- - (V2, - (VX) (VZ) (V2) (V
-Ez, 1/ (V/2) (VX) + 1z, (1V))) (VZ)))
+ +2Ez, ((V%) +V (VX))
= + 2E,, [[V2)) [ Ez,, (I(V 21) (V
+ 2B,, ((Z)) (VXX, (VZ1))
(68)
Using Proposition D.3 and Proposition D.4 we therefore have
E2,22 o X + A 1/2 - (V(X + Z1) V(X + Z)) - V(X X) + (VX)
(VX) 1|
2
cao d V + (1 1 Ex [I (V d(d 2)0* Σ
(1+
Σ V2.
(69)
Now using the properties of V, we have
2
n
|
Hn, and
11,
(70)
122
Using equation 770 in equation
we get
Ez, 2z V(X X + X - 1/2
(V(X Z1) V(X + Z1) - V(X X) + (VX) (VXII
1
= 2 1+ d
Ez, (1 21) + 2)
Σ
+ 2d
k22
k=1
k=1
= 2 [+ 2
Ez, (l()) - (VX) d(d + 2)00HHH22 Hn, +
20
(71)
Let Hn,c denote the generalized Harmonic sum, i.e., Hn,c -E 8- Therefore, we have 1/2 72) (V(X + 71) V(X + Z1) V(X X) + (VX) (V
E B2, 2o |V(X X + A 1/2
1 = 2 1 d
Ez, ( t ddd + 2) Hn. + 2 H,.
S(X)
(72)
29

---

Therefore to estimate x E E.. it suffices to estimate sup x S(X). We do it as follows:
k
2
sup S(X)
sup Ez, VV XEX
V = do² sup XEX
Σ
Xts
XEX
k=1
j=1
(73)
a
n
do sup XEX
Xtai = do²
do² Hn.l
f1:12
Plugging equation
in equation
72
we get the bound for the biased estimate:
o² (cad 2d 2n, + d(d + 2) 2),
(74)
Then we need to determine the bias term, all the first-order terms will result in 0 as the expectation over zero mean distribution, so the only term that introduces the bias is
EE (VZ1) ( (VZ)))). Ez, (VZz),. o²d
Σ [=1
k,t
(75)
[1 i=j is the Dirac-delta function.
where 6i=
0
otherwise
Then the unbiased approximation error is
Ez, 2. [VX o X + Z2) (V(X Z1 V(X + Z1) - V(X X) (VX) (VX)
(76)
Ez, (V Z1) (VZ,) )
We have already computed the first three terms inside the expectation. now compute the bias term error:
2
n
n
n
Ez (V21) (VZ,)
2
do
do Hn
(77)
j=1
Bias reduction procedure decreases the expected error of by
74)
Rz (VZ)) |EZ (VZ) (V
do
V2
k=1
do
do H
kza
k=1
(78)
Resulting in the final error of:
E - E11 (caul 2 2d 2)
Σ + díd + 1)
sup
XEX
(79)
k=1
oc 2d 2)H + d(d 1) Hn,
This completes the proof of the theorem.
Theorem 4.2 (Private covariance matrix estimation with PP). Assume the same setting as for
Theorem 4.1 Let Epp be the result of the above construction, where privacy is obtained by running PP with noise strength a and debiasing. Let S(n, d, a) = d(d + 1 Hn,1 d(d + 1) Hn, + 2(d + o)o² Hn.1. Then, for the expected error of the covariance matrix estimate it holds:
S(n, d, 0) 2(d + 1)0² Hn. I sup El Epr S S(n,d,))
(12)
XEX
30

---

Proof. Let us denote the covariance matrix estimated via Post- fost-Processing (PP) without bias correction
as 2pp Then, the approximation error has the following form:
5-b
B - E fا -E,,, + ) (X+ - (V(X + Z1) V(X - Z)) - V x) (VX) (VX)
-Ez (2 -2 (V(Z) Z1,, (V) (V2)) 1 (V X)
A + Ez, (V
A
V). 11)
-4Ez, (V o X), (V
A4
4 Ez (V
X), (VZ) (VX)) +2Rz, (1(V (VX) c
+ Ez, [[V)]
(VZz)
+ 21 ((V2)
(VX), (V (V2)))
(80)
The last three terms in the above expression evaluates to equation 722) Therefore, in what follows, we bound A₁ to Ag. Bounding A1:
2
A1 Ez, [[z Zi)l
Ez,
Am
d
d
3
VeLe, Va to
(81)
R,t
k=
jiml t=1
km
j= f2
km it
d(d 1)0d
h,t + do
Σ
1=1
Bounding Ag:
A2 = Ez, (V Z1), (V))) (VZ1))
Va, Vin(Z))ni(ii)ss) )
Σ (iaa(Zilss) )
(I VeslZibes)
Ez,
k=
d
d
n
(82)
30 4
V +
V3 hit +
Vk V2,12
d(d 1)0d
Rit do
VELt
Σ
V2
k=11=1
Bounding A3:
d
As = Ez, (( x)|l Ez,
Σ
Vi, (i)((i)s
= do
x2
E.t
1
j=1
(83)
Bounding As:
A = Ez, (V X), V(X Z1))
d
Σ Vv.c Vo.((Z)e,.Xe.) )
Σ VnollZiasooe
11
d
= Ez,
= 02 Σ
V22
Σ x2
1= i.j
k=
1=1
j=1
(84)
31

---

Bounding As:
As = Ez, (Z
X),((V)) . (V
n = Ez,
d
n
( Vancees)
Σ Vi (1)(s)
V (1.(ZZ)).. (Z))ss(ess
k=
(85)
11
n
n
0²
V22
Xt.)
Σ VieXees
j=1
Bounding Ag:
Ag = Rz, (2) X), (V (VX))
n Bz
( Vasll
VE (2))..
Σ Xes
k= 1.
(86)
d
do²
2
Rit Xt.
Ves
Plugging equation (1) to equation
86 in equation (80), we get
2
12
n
n n
EIE - S-pp11 = d(d + 1)0*
Vhe + do
Σ
Σ Vkse/
-2d(d- 1)
V
t=1
1=1
12
22o
VeLe
Kit
+ +((d+ 1)0²
X?
k= t=1
j=1
n Evnddes
1)o²
Xis
A=1j=1
2
+ 2(d++))
(VX) + d(d + 2)04
Σ
12 Σ
k=
1=1
(87)
Recalling that the matrix V is the averaging workload matrix V = (at) with of = for sist
and of = 0 otherwise, we get
n
E Σ Ehe 112 = d(d 1)0a
+ dno 2d(d+ + 1)o²
2do
k=1
d
(Etxas
k
+ 2 + 1)
4(d + 1)0²
Xt.
Xes
122
1.j
122
k
1=
j=1
k=
j=1
n
+ 1)o²
X1.
d(d 2) 1
n Loa
1
dld-1)o
+ a
122
k=1
k
1
+ +2(d+ + 1)02
X..)
Σ (X
Xind)
k 11.12
(x)
(88)
32

---

Since every tern except T2 (X) supxex E|J Eppll it suffices to bound the supremum of the inner difference over X:
) is independent of X, to compute both upper and lower bounds on
n1
A Σ 11
Tp = sup (X)
sup XEX XEX
Σ Xt.s
X
(X
Xtaut
(89)
|
11
Since the double sum is non-ne -egatiee,ee, this leads to a trivial upper bound Tn I Σ k Hn.1-
k=
For the lower bound, consider X; (-1) In this case, |X 1, but 1E X 1, so Tp. Therefore,
H Hn,3 S Tn S Hn,1.
(90)
Therefore, we have the following bounds for the upproximation error without a bias correction:
dno o' n
n
sup B 1 S d(d 1)o²
Σ
2(d + 1)
(91)
xex
k
sup E|JE - xex
- Eppll d(d - 1)0*
1
dno do
Σ
2 1)
2(d
1)o²
Σ
1
k
k.3
k=1
(92)
Now we will determine the bias term; let ر:=ه denote the Dirac-delta function, then the bias of Epp
a
(V Z1) Bz, (VZ)) (VZi)) = 020 Σ VA.
V2..
(93)
We also have the following set of equalities when Z1 is a Gaussian matrix.
d
2
n
Ez, (V2) (VZ))
do
(94)
k,t
km1
d
2
B2, V(Zi 21)
Vh,t
= dno
(95)
k=1j=1
(Ez, (VZ1) (VZ,), V(Z, Z,))r do Σ
Σ
v2
Σ Vhst
do
1
(96)
K
To remove the bias from the error we would need to add the following terms:
EE V(z Z1) + E2, 1 (V
- 2(E2, (VZ) (VZ,,,, (Z Z1))
-2Ez, ((VZ)) (VZI), Ez, (V Z1) (V
(Z2 (Z) (V2)), V(Zi Zi))
- -2Ez, (V Z1), (Z 21))F
=-1E2, V(Z Z
|B2, (VZ) (V | + 2(B2, (VZz) (VZ1). Ez, V(Zi Z1))
2
2
"
- Σ
do
+ 2do 4
Σ
V2 k.E
Σ Vh.e
k.t
k=1
k=1
A=1
n
1
4 do
+
2do
do Hn. do=Hnn. + 2 H
62
(97)
33

---

Combining everything together, we obtain:
E| Σ Eep | = d(d + 1)
V2.
2d(d + 1)0²
ΣD
R,t.
Rim
1=1
+ +((d 1)o
x2
1jj
y=1
(98)
4(d 1)0
Σ
Σ
k=1j=1
2
R
n1
12
+ +(d 1)0²2
Σ
(VX) + d(dd 1)0²
Σ
V22
Therefore,
sup B1JΣ Epp l122 < d(d + 1)o² " d(d+ 1)0 Hn, + 2(d + 1)0² Hn,1 and
(99)
xEx
sup 1B|20 - Epp li: 2 d(d + 1)0² Hn,1 d(d+ + 1)0² Hn. + 2(d + 1)o² 2n, - 2(d + 1)o² Hn,3. xex
(100)
which concludes the proof.
Lemma A.5 (Dimension Reduction). For any vectors E Rd, where d 2 3, there exist vectors
x', y E Rd-1 that for any À > 0 satisfies the inequality:
|| - y 3 A| r o x y vll2 S || 1' + Al|2o o x' - v/11.
(29)
Proof. We begin by selecting indices and j such that the corresponding components my from and Va 11 from y satisfy (x y (r} 5z 2 O. We can always find such indices because, by the pigeonhole principle for d 2 3, there will be pairs where either both xi 2 v/2 and 2² 2 vz. or both x? S v. and x3 S v². We can compare the impact of these components on the sum with the values 22 and -v o² + y3. which correspond to vectors in lower dimension. Consider the difference in the objective function and f( vi) defined below:
2 f(r,, vi) = (V22 23 u + g vi) = (x: y1)) + (zz 3² + X(2² v/ + M(r} n7)²
+ +1 [2) - vi vz)²
(101)
(102)
Note that f(x,, 9:) is the objective function. Now, after algebraic manipulation, we get
f(z,, (1) = =2 m7 + x3 /2 +3² + X(x; 22) v3) + 2x,y1 + 2xz 2 Ax² vt (z) - 20
(103)
(104)
where the first inequality follows from the Cauchy-Schwarl incquality and the second inequality is from the assumption that (x - y (=² 0/) > 0.
For this lemma, d 2 is indeed special case since it is possible to find of > vी and 23 < v2, for which the dimension reduction argument would not work.
Lemma A.4. Consider x, y I23 and let then,
diag (X) 12
sup Mills1
[| vll +
- - =
[4,
12+2X 21 + 2X
if |
if < 3
(28)
||
34

---

Proof. First, we consider the effect of the signs of the components of I and y. Multiplying both a; and y; by -1 does not change the value of the expression. If x; and yi have the same sign, then by flipping the sign of one of them, we increase the difference || yll2. while || x y yoll remains unchanged. Therefore, without loss of generality, we can assume x: = (211 322 and y = (-11, -V2) for positive I; and V4- Next, note that for a fixed difference | yll2. the functional increases as the sum 21 + 1/2 or 22 + y/2 increases. Thus,
||ا|| so 22 /1 =1. The norm of
assume
y. however, can be different. Therefore, we look for solution of the form (z1, / x1) and y (-
We now consider the functional in the statement of the lemma in the following form:
2
L2 (21, V1, 92) (21 + y1)
(V1 V1- 29 + y2) + +
+ -à) (105)
We now aim to prove that sup Lx 91. = 02222222 (X) in the constrained domain y11 2 0, 3/2 2 sf + v S 1.0 S < I. This analysis involves considering up to twenty-four different scenarios for optimization with boundaries, which, due symmetry, can be reduced to five distinct cases.
Case I: vf + v = 1, 21 > 0, 1/2 > O.
We can compute y/2 v1 v then the optimization functional is
La 11,91; v 1111j/ yp = (x) =1)² +
(V ( V1 5î + +A ((o--b)) v7)² + A Avi =7?)
2
x7
(106)
= 2 + 211911 + 2 1- 1- 1-
1 3 + 21 (2² vt
(107)
The cases where Φ = 0 or æ = with ||y|| = 1 are equivalent to the scenario where ||>||| = 1 and
y1 - 0, or 91 1, which we will consider later. For now, we proceed by computing the derivatives with respect to and æ1:
aLx r1, U1, V vi
2y1 v 1 x7
201
+ 4y1 (yf - -z²) = -0.
Oy
V1 1/1
(108)
0Lx
(21 y1, v v
2x1 / 1 yी
2y1
+ + > (2 - -ii==0 = 0.
Ox
v1 2f
We transform this system by summing and subtracting the equalities:
1/1 yn + æ1 219²
(x1 + v1)
+ 4X (x + vî) - 4Ay1 (311 + x1) xx)==00 =0,
VI yी V 22
(109)
(x1 y1) /1 o 21 + zivi
+ 41 -vi- 4Ay1 (x1 - yy) 0.
"ी /1 -1 x
J1 + y1 = 0 is not a solution under the constraints we are solving. However, y1 is solution for any X. From now on, consider yı * æ then we can divide
that gives La (21 31, /1- by the difference, leading to the system:
=it) -1=x
T191
+ 4A (x) -11² 0,
V1 v /1 of
(110)
1
+ x I1
41 (x1 + + O.
vी 27
We consider again the sum and difference to get:
201
2 +
161x1 0,
V1 5ी 17
(111)
+8A (of + +f) 0.
VI 5ी /1 x
35

---

We solve it for À to get the following equation:
(112)
(o} + vt) VT of
o
80
8V1
//
We transform into the form
101
2 +
1191
52 o + zivl
(113)
By squaring both sides and subtracting zty?. we obtain
4uiyy (xf + yf )
39 = x -
(114)
So, either of + vी= = 1, which implies y1 which we have already discussed. We have found another potentially optimal point y1 which we will further investigate. We now consider it as a function of one variable æ₁;
V
2
or or vी = 2x which implies y1-
/1
o7.
Cx 21 21 (11V11- 25 2², -2(1)
V
2 +t
+2 (1 (1-22)=))
(115)
Then the optimum is either 21 0, .1
with the value 4, or when the derivative
OLx Ø1: / 24
4x²
= 4/1 x7
16A2 (1
2x-
(116)
Or1
v1 x7
4(1 (2 (1 4A01 v
x7
0.
(117)
x
The first term gives #1 1 which results in Lx 4; otherwise, 4A 1- which V2
can solve by first denoting o new variable in the equation -2f + x2 quadratic formula, we find the optimal value sf, which is given by:
16X2 = 0. Using the
4X2'
(xf)
2\
4X2*
(118)
This solution exists only when A z. Substituting this root back into the function gives us
LA rq (x=))),,aa))) 4x (xT)² +2A -()))) 2A +
2 4,
2x
*
(119)
which constitutes the function r'2 ding (A).
Case II: y/ + y < 1, 9/, V2 (Interior).
For the optimum, is important that dy maximum would be that the Hessian is negative semi-definite: compute the second derivatives explicitly:
and 0C* Byg
But the necessary condition for the
&
< 0 and 82C,
< 0. We can
0yg
36

---

o
2 + 12Ay1
4 5
v S
(120)
Analogously, we can derive that v/
<
1-x 3
Then substituting this into the functional, we get:
2
Lx (1, (x1 + +2))++
xf + y2
Ma7 v¹)² + 2 x7 -)3)
(121)
1
$ 1 + v3
+사+ + 9
< (2)
(122)
Case III: 511 = 0,0 < 1/2 <
Lx(21. V1, v1, = x + (v1-
1/2
Aot + A1 11111(x)) x -
(123)
As continuous function of y/2 on an open domain, it can reach a maximum only when the second derivative is non-positee non-positive, which leads the same condition as in the previous case: y2 I 3 Since yı = S 3. this leads to the same conclusion.
1-2]
Case IV: = 0, 1/2 = O.
(x(11,0,0) = x + 1+ A(1 - -a
r2
diug (A).
(124)
Case V: yn 1,, 1/2 0.
1,0) = (x1 + 1)2 1 29 X(1 27)² + X(1 - 27)² = 2 2x1 + 2X(1 - =²
(125)
First, for S 3. we have:
(x 1,0) 5 2+ 2x + 54.
(126)
For 1 2. we have the following inequality:
(x 1,0) < 2 + 201 + 2X(1 xÿ)) = 25 - 2Ax 2 21
(127)
2X
This concludes the proof.
Lemma D.5 (Expected Second Moment Error with PP). Given the private estimation of the first
moment Ax + CT)17),, where A₁ B1C,, and the second moment A²(X CT 7n) (X Z1). Z1)) where A2 B2Cr, with independent noise Zi N ||Cilll-2o0) the clipping
norm& Ç = 1, d > 1, the expected squared Frobenius norm of the estimation error for the second moment satisfies:
sup Ppp - D1I2: = sup Ay + +T' Z1) (X (X+T 21) - A2 X)II
Xex
XEx
trA A2(Q Q))
+ + sup ur((A} A2 o Q)Xx*)
(128)
xex
+ do do MoaICilliip (A. A₂Ea)
bias
where Q= C and Eq diag Q) diag (Q).
37

---

Proof. We aim to evaluate the expected squared Frobenius norm of the error:
sup XEX
A2 + CT - (X + A2(X o x)ll
= 4 sup B|| (X o EI 1
Z1)
(CT
(129)
XEX
S2
We compute those terms separately.
S sup E A2
sup E. XEX
A2) X1. E (er
Xex
k=1j=1
k,2) (A2)km X Σ (CT (
(CT))))))))))))))))))))) 112.,1((11)) (2))
sup
Xex
k= j=1 f1.12
sup = =
Σ (A2)kst Xers
(e X2ad
Σ (CT))aa (C (CT))
XEX k= /=1 h1.t2
y=l
sup o 1-
((A2 ),,
(LCT ((
XEX
f1,62
= =o
sup ir((A] A2 0 Q)Xx*) XEx
(130)
where Q = ---
d
8 = Rl| 12 A2((CT 21) o 2))
E
Σ 1/=1
(22) (C 21)
k=1ø=1
(131)
d
E
71) (C) (
1
First, we compute:
a
B(C 1i), (CT = E Σ
E
Σ (CT
(CT (
(7)) (7
rr
2E
Σ (CT
mm (CT ( )1 (CT Desrr (2))),
-30*| 22 ( l8g.r
=
+ Σ (CT)) 1r,m 22
rifra
+2001|Call
Σ (
(CT") (CT))s Yesr De2r2
r13/12
of|[C]ll Quars 20 2 ICilli-2
(132)
38

---

Plugging it back, we get
"
B|| (1
Σ
Σ
(A2)a.t (A2)k.ta (Qr 2tat 2Q(
f1.f2
do
| +2
(A2)a. (1))),)(((1111)) Qt2t2 2Q((1(2)
k=1 f1.f2
1Clli tr AgEq) + 2do")|C tr A2(Q Q)),
(133)
where E = diag(Q) diag ( (Q)-
Adding these terms together we obtain:
Ez| Dpp D1I2 2do 2 11 A2QQ0
sup Xex
+ 402||C 11 1i
sup tr((A} A2 o Q)XX² xeX
(134)
+ do tr(A2 Aq)
Bias Correction.
The expectation of Aa((CT o (CT+2)))),, introduces a bias:
(A2((CT (CT = E (A2)
Σ (CT (er
1=1
=0>|IC1 ||2
(A2)
(135)
= Σ (12)),
The Frobenius norm of this bias is:
(CT
Σ
(Az)x. (Az)a. Quai Utziz
(136)
k= f=1 f1.t2
do (AA A2
If we subtract this bias from the estimate, it will increase the error by the aforementioned quantity due the Frobenius norm of the bias but will decrease the error by two scalar products with the A2((CT Z1) (CT Zi)) term:
(C)
()) (137)
Thus, eliminate the last term (do tr(A A2Fo)) in the via bias correction.
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper claims to solve the problem of joint moment estimation, which we do, and provide an extensive baseline comparison justify method.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The main limitation of our method is that, in certain circumstances such as with high-dimensional data-it only offers an advantage over post post-processing in high- accuracy regimes. We discuss this limitation in each new setting.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
40

---

Answer:
[Yes]
Justification: We recognize the importance of providing a theoretical justification and, to the best of our knowledge, fulfill this requirement.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide pseudocode for all the algorithms we use and believe they are easily reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
41

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No].
Justification: We provide pseudocode for all the algorithms we use and believe they are easily reproducible. However, we do not publish any source code at this time.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
oliccy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccpublle wwwpc//ggseeeeeeeec hetpc///uuudess/eeeuubuiiiii
(CodeSubiisss wwwaaabmmsssooni ssiiiiosiccyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All the experimental parameters can be found in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: For all plots with sufficient variability in the data points, we include error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
42

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: All our experiments require minimal resources and can be run on a single computer c.g., in Google Colab.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics atttps://neurre httpa//pppp...pppo/occccccccccda
Answer: [Yes]
Justification:
To the best of our knowledge, the paper conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Differential privacy-and, to a certain extent, privacy in general-is discussed in this paper, which we view as the area with the greatest potential social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
43

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
44

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer:[NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
45

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Our research is not related to LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
46


Reviews:
[{"review_id": "VZCOTfuj5i", "reviewer": "Reviewer_wMbD", "summary": "This paper proposed a new method named Joint Moment Estimation (JME) for continual differentially private estimation of the first and second moments of a stream of data in arbitrary number of dimensions. The method uses Gaussian noise. First and second moments are written both as matrix multiplications. Then their joint sensitivity is found, and Gaussian noise is added to both moments scaled according to the joint sensitivity. Key to reducing the noise level is to user different linear transformations and scaling factors on first and second moments to control the noise levels, hence making the joint sensitivity small. Consequentially, the second moment does not necessarily increase the noise level for the first moment. Results show improvements compared to more traditional approaches.", "questions": "1. This is a minor issue, but I believe the notation $||\\cdot ||_{1 \\rightarrow 2}$ has already been used before it becomes formally defined.\n2. In the joint sensitivity (and hence noise level computation) the matrices $C_1$ and $C_2$ only comes out in the $||\\cdot||_{1 \\rightarrow 2}$ norm. Is that the only thing abut them that affects the noise level? Will it ever be more beneficial to use $C_1$ and $C_2$ other than the identity matrix $I$?\n3. I find it a bit counter-intuitive that $c_d$ should remain a constant for every $d \\geq 2$, but I didn't have to time to go through the math calculations in the appendix. Do the authors have a more high-level explanation of that?\n4. The results of first moment not needing a bigger noise scale is surprising to me. I didn't check the math step by step so my confidence in this conclusion is not as high as it should be. What's the key difference between the joint sensitivity definition and the vector sensitivity in the CS method that lead to this result? For, when you concatenate the moments into a $d(d+1)$-dimension vector you can also apply the matrix $C_1$ and $C_2$, and $\\lambda$ coefficient first, then take the norm and add noise according to it. Or are they roughly equivalent? Do you have any high-level intuition for that?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1.  If I understand this correctly, the results in this paper indicates that by using approximate matrix multiplications and scaling on the Gaussian noise, we can add the same noise level to the first moment. The theoretical result is interesting and promising, since all privacy-budget splitting mechanisms should fail to achieve this. \n2. Even when the scaling factor $\\lambda$ does not give free second moment estimates, JME still pareto-dominates the IME algorithm.\n3. The paper studies the continuous computation of the moments, which adds to its importance and makes it applicable for a wider variety of practical problems.\n4. The algorithm is easily implementable.\n\nWeakness:\n1. The improvement over baselines in the experiments seem to be more moderate than the theory suggests. It seems that we would need $\\varepsilon$ to be really small for the new algorithm to beat the baseline in DP-Adam. I wonder why that is.\n2. Getting the second moment \"for free\" does not necessarily mean that its noise level is small, and some equations cannot be solved in closed form so it's hard to further characterize the improvement over more traditional approaches.", "was_revised": true, "final_justification": "I thank the authors for their response. It addresses some of my concerns. I remain positive about accepting the paper, but still have some confusion about intuition of the theoretical approaches, practicality of the algorithm, etc. Hence I will keep my current score.", "rebuttal": "We thank the reviewer for the valuable comments and high score! \n\n**Weaknesses:**\n\n\n**> 1. “The improvement over baselines in the experiments seem to be more moderate…”**\n\nThe theory suggests that JME would outperform DP-Adam when the noise is greater than $1$. However, since the noise is divided by the batch size, this requires us to focus on regimes with high privacy and small batch sizes. We, however, expect JME to perform better on problems with lower dimensionality, such as numerical optimization or low-dimensional regression tasks. We will include new experiments in the revised version.\n\n\n**> 2. “...the improvement over more traditional approaches.”**\n\nIndeed, such a comparison would be interesting. However, in the paper, we consider the setting of continual release, in which classical methods for private moment estimation are not applicable. \n\n\n**Questions:**\n\n\n**> 1. Notation. Thank you, we will fix it!**\n\n\n**> 2.“Will it ever be more beneficial to use $C_1$ and $C_2$ other than the identity matrix I?”**\n\nIt is true that if our goal were solely to minimize the noise per iteration, we would use identity matrices. However, our objective is to minimize the expected error and thereby maximize utility. In the utility analysis, the Frobenius norms of  $A_1 C_1^{-1}$ and $A_2 C_2^{-1}$​ also appear, which makes the choice of correlation matrices non-trivial. Henzinger et al. [A Unifying Framework for Differentially Private Sums under Continual Observation, SODA 2024] have shown that the matrix square root achieves near-optimal rates, at least for first-moment estimation.\n\n\n**> 3. Why should $c_d$ remain a constant for $d\\ge2$?**\n\nWe reduced the problem to an optimization over a pair of vectors $x, y \\in \\mathbf{R}^d$. The objective function can then be rewritten in terms of their scalar product $\\langle x, y \\rangle$ and their norms. In dimensions two and higher, we have independent control over the scalar product for given norms. In dimension one, this is not the case, which mainly accounts for the separation.\n\n\n**> 4. What is the key difference between JME and CS?**\n\nThank you for the question! In JME, we reduce sensitivity by observing that the worst cases for the first and second moments differ and cannot occur simultaneously. This means that analyzing them jointly allows us to reduce the added noise. In contrast, CS analysis basically considers the worst case for each moment separately."}, {"review_id": "QoUkgUsYfK", "reviewer": "Reviewer_ksfQ", "summary": "This paper introduces a novel method called Joint Moment Estimation (JME), designed for continual, differentially private estimation of both first and second moments of a data stream. JME is tailored for continual release settings—where estimates are updated as new data arrive—and is based on the matrix mechanism for differential privacy.\nThe key innovation lies in a joint sensitivity analysis, which reveals a privacy regime where the second moment can be estimated without additional privacy cost relative to the first moment. This property is described as “privacy for free” for the second moment. The paper provides both theoretical guarantees and empirical results. JME achieves better accuracy than baseline methods, especially in high-privacy or small-batch settings.", "questions": "1. Could JME be extended to support higher-order moments (e.g., skewness, kurtosis) in a similarly privacy-efficient way?\n2. How sensitive is JME’s performance to the choice of noise-shaping matrices , ? Are there principled ways to select them for arbitrary workloads?\n3. Can JME be integrated with federated learning or decentralized streaming?", "limitations": "The authors acknowledge that the method assumes bounded norm constraints on the data and relies on the matrix mechanism framework, which may not be straightforward for all users. Additionally, while the paper claims \"privacy for free\", this is bounded to the setting of joint sensitivity, and does not generalize to all DP compositions. Also, the performance is not extensively tested in large-scale or production scenarios.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThis paper makes strong theoretical and practical contributions by providing rigorous guarantees on privacy, utility, and unbiasedness for the proposed JME algorithm. It demonstrates that second-moment estimates can be achieved with \"privacy for free\" through careful joint sensitivity analysis. Moment estimation being a core component in many machine learning applications further highlights JME’s real-world relevance. Empirically and theoretically, JME is shown to Pareto-dominate existing baselines such as IME, CS, and PP across utility-privacy trade-offs. The algorithm's design—leveraging matrix mechanisms and Khatri-Rao products—is both mathematically elegant and clearly presented.\n\nWeaknesses:\nThe main limitations of the paper lie in its reliance on bounded input assumptions and noise-shaping matrices, which may be difficult to select or tune in practice. Additionally, the method has only been evaluated in relatively controlled or benchmark settings, lacking demonstrations in more complex, real-world machine learning pipelines. While the paper briefly mentions debiased post-processing as a baseline, it does not deeply explore its practical performance, and the theoretical complexity of the proposed approach may pose a barrier to broader adoption.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable comments and high score!\n\n\n**Questions:**\n\n\n**> 1. “Could JME be extended to support higher-order moments?”**\n\nThank you for the question! We believe that it is indeed possible to compute the sensitivity, at least to get an upper bound. We chose to focus on the first two moments, because these appear most commonly in practical methods, but an extension sounds like interesting future work. \n\n\n**> 2. “Are there principled ways to select them for arbitrary workloads?”**\n\nThe method is sensitive to the choice of the correlation matrix, and the identity matrix may not be the optimal choice. Matrix factorization remains an active area of research, and for certain commonly used matrices, near-optimal factorizations are already known. For instance, Henzinger et al. [A Unifying Framework for Differentially Private Sums under Continual Observation, SODA 2024] showed that the matrix square root of the workload matrix achieves near-optimal performance for prefix sum workloads, exponentially decaying weights, and several others. As a general approach, we recommend numerically optimizing over the workload matrix. This has been done efficiently, for example, in McKenna [Scaling Up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML, ICLR 2025]. We are happy to include this discussion in the revised version.\n\n\n**>3. “Can JME be integrated with federated learning or decentralized streaming?”**\n\nYes, JME is based on the matrix factorization mechanism, which can be implemented in a federated or decentralized manner. This has been applied, e.g. in [Bienstock et al, “DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning using Packed Secret Sharing”, arXiv 2410.16161]. However, such implementations would have been orthogonal to the contribution of our paper."}, {"review_id": "a1qmgi9uZE", "reviewer": "Reviewer_pJ83", "summary": "The paper proposes Joint Moment Estimation, a method for continual and differentially private estimation of both the first and second moments of streaming data. Unlike naive approaches that split the privacy budget between estimates, JME uses a joint sensitivity analysis to estimate the second moment without extra privacy cost—achieving what the authors call “privacy for free.” It is built upon the matrix mechanism and is adaptable to various settings (e.g., exponential weights or sliding windows). The authors prove JME's privacy and utility guarantees and show its practical benefits through applications to private Gaussian density estimation and differentially private Adam optimization, demonstrating better performance under high-privacy constraints compared to existing methods.", "questions": "- Figure 1: Pareto frontier behavior of \\$\\lambda\\$-JME. Do different values of \\$\\lambda\\$ in \\$\\lambda\\$-JME result in different Pareto frontiers? (Do all \\$\\lambda\\$-JME variants share the same frontier, or does the error trade-off change with \\$\\lambda\\$?) If so, how should we interpret the dominance order of \\$\\lambda\\_1\\$-JME versus \\$\\lambda\\_2\\$-JME when \\$\\lambda\\_1 < \\lambda\\_2\\$?\n\n- Could the authors discuss the computational efficiency of the proposed method, and compare it with the baselines?\n\n- Interpretation of “privacy for free”: In line 90, the paper states that “the total sensitivity of estimating both moments...” Can this be more precisely interpreted as “the sensitivity of a linear combination of the first and second moment estimates (parameterized by \\$\\lambda\\$)”? If so, clarifying this relationship could help make the core intuition of \"privacy for free\" more transparent.\n\n- The notation \\$\\Vert \\cdot \\Vert\\_{1\\to 2}\\$ appears before it is explained (e.g., in Algorithm 1), but its definition is given later in line 122. This makes the algorithm hard to parse on first read. It would improve readability to define or briefly explain this operator norm earlier.", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "- The paper is well-structured, with clear algorithmic descriptions.\n\n- The paper compares JME against multiple relevant baselines (IME, CS, PP).\n\n- For the weakness, please refer to the questions.", "was_revised": true, "final_justification": "The authors have addressed my concerns.", "rebuttal": "We thank the reviewer for the valuable questions!\n\n\n**Questions:**\n\n\n**>  “Do different values of $\\lambda$ in $\\lambda$-JME result in different Pareto frontiers?”**\n\nNo, this appears to be a misunderstanding. The Pareto frontier is computed by varying the trade-off parameters between first- and second-moment errors. For $\\lambda$-JME, this means varying $\\lambda$. For α-IME one varies the privacy split $\\alpha$, and for $\\tau$-CS the rescaling factor $\\tau$. The trade-off preferred in practice will depend on the final application, but our analysis shows that $\\lambda$-JME always is preferable, because it Pareto-dominates the other methods.\n\n\n**>  “Could the authors discuss the computational efficiency of the proposed method”?**\n\nAll methods that we discuss have the same computational complexity, which is linear in the number of steps and in the output dimension (i.e quadratic in the input dimension); the difference between the methods lies in the analysis of the added noise and the resulting error. This suggests that we can achieve the same privacy level with less noise, while the practical computations remain nearly identical. \n\n\n**>  Interpretation of “privacy for free”**\n\nWe are not sure what you mean by linear combinations, please correct us if we misinterpreted your comment. Note that the dimensionalities of the first and second moments differ: d and d², respectively, so it is not possible to combine them linearly. A more intuitive way to see the joint sensitivity is that we compute all intermediate first moments and all intermediate second moments, then concatenate them into a single large vector, with a scale factor multiplied to the second moment. We calculate the sensitivity of this vector (the change in its $\\ell_2$-norm when changing one input point) and apply the Gaussian Mechanism to the vector. Our main insight is that for a specific choice of the scaling parameter, the sensitivity of the concatenated vector equals that of the first moment alone. We refer to this phenomenon as **“privacy for free.”**\n\n\n**> Notation**\n\nThank you for noticing this! We will fix it in the revised version.\n\n\nWe hope that our clarifications addressed your concerns, and that you will be able to support our work in the coming steps."}, {"review_id": "pWHZqRETJA", "reviewer": "Reviewer_TFH7", "summary": "The authors propose a way to release both the first and second moments in a differentially private manner, concurrently. This is also specifically for data that is being continually released, that is streaming data. A standard approach to do such a thing is allocation some budget for each of the moments. As opposed to a standard approach the proposed work reformulates the problem as a matrix and do a joint privatization using the matrix mechanism.", "questions": "In section 5 it is mentioned that the covariance matrices are symmetrized and projected onto the cone. Can the authors elaborate on this. How did they do the projection? If there was some clipping of eigen values, how was the clipping constant chosen?\n\nI believe Figure 3 has an error as it states n=100 but the steps is 200.\n\nMinor typo on page 5 toprivatize -> to privatize\nMinor consistency issue, the appendix is referred to as both the \"Appendix\" and \"appendix\".", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "A large endeavor in DP is being able to save budget wherever possible. Being able to release a second summary statistic at no additional cost is a great strength. As a weakness, I don't truly see the \"continual release\" being used thoroughly. That is, it seems to me that the theorems do not take into account what happens at time t.", "was_revised": true, "final_justification": "My original assessment of the paper was true to the paper's quality. The discussion period shed light on some questions I had but my score still seems accurate.", "rebuttal": "Thank you for your valuable comments. In the following, we answer your questions and will hopefully be able to address your remaining concerns.\n\n\n**Weaknesses:**\n\n\n**> “ I don't truly see the \"continual release\" being used thoroughly.”**\n\n\nWe will clarify this in the manuscript: we follow the standard protocol for continual release DP, where the algorithm by design processes the input data in a stream, such that any moment estimate is available immediately after the corresponding data arrives. However, privacy analysis has to be done for the entire process, because privacy after step $T$, with all intermediate results available, is strictly more restrictive than privacy after any earlier step $t<T$. \nWhat additionally would be possible is to perform the utility analysis separately for each step $t$, not just for the final step. Our analysis can naturally be extended to intermediate steps:  we use the same noise multipliers as for the whole process, but compute the utility based on submatrices of $C_1$ and $C_2$ consisting of the first $t$ rows and columns. We will be happy to discuss this in the manuscript and restate our results for the $t$-th step.\n\n\n**Questions:**\n\n\n**> “How did they do the projection?”**\n\nWe see the clipping constant as a tunable (postprocessing) parameter. As a dissimilarity measure, the KL divergence is very sensitive to small eigenvalues, which should be clipped to ~1. We observed that both Post-processing and JME need similar clipping coefficients, thus we believe this problem is intrinsic when estimating the second moment, especially from when the number of steps is small, rather than a specific artifact of JME. \n\n\n**> “Minor typo”**\n\nThank you for spotting the typos, it should be $n=200$. We will fix this in the revised version!"}]

Author rebuttal:

Meta-review: This paper develops differentially private algorithms to simultaneously release the first and second moments from a data stream in a continual fashion in a matrix mechanism setting. They introduce an algorithm that Pareto dominates a budget-splitting approach for the two objectives of accuracy on the first moment and accuracy on the second moment, and show that in some settings, releasing the second moment does not increase the noise level for the first moment, therefore obtaining additional information “for free”. The algorithms are demonstrated on a Gaussian density estimation problem and model training with DP-Adam.

The reviewers were unanimously positive about the paper, with everyone rating it as borderline accept. They thought the paper was well structured and clear, found the result that the second moment can be obtained “for free” appealing. They found that the algorithms were practical, applicable to real problems, and showed clear improvements relative to appropriate baselines. 

There were some questions about how significant the empirical gains would be in more complex settings than the relatively controlled experiments in the paper, like real ML training pipelines. 

The rebuttal adequately addressed reviewer questions and clarified some misunderstandings.
Decision: Accept (poster)