Continual Release Moment Estimation with Differential Privacy

Thank you for your valuable comments. In the following, we answer your questions and will hopefully be able to address your remaining concerns.

Weaknesses:

> “ I don't truly see the "continual release" being used thoroughly.”

We 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$. What 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.

Questions:

> “How did they do the projection?”

We 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.

> “Minor typo”

Thank you for spotting the typos, it should be $n=200$. We will fix this in the revised version!

We thank the reviewer for the valuable questions!

Questions:

> “Do different values of $\lambda$ in $\lambda$-JME result in different Pareto frontiers?”

No, 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.

> “Could the authors discuss the computational efficiency of the proposed method”?

All 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.

> Interpretation of “privacy for free”

We 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.”

> Notation

Thank you for noticing this! We will fix it in the revised version.

We hope that our clarifications addressed your concerns, and that you will be able to support our work in the coming steps.

We thank the reviewer for the valuable comments and high score!

Questions:

> 1. “Could JME be extended to support higher-order moments?”

Thank 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.

> 2. “Are there principled ways to select them for arbitrary workloads?”

The 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.

>3. “Can JME be integrated with federated learning or decentralized streaming?”

Yes, 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.

We thank the reviewer for the valuable comments and high score!

Weaknesses:

> 1. “The improvement over baselines in the experiments seem to be more moderate…”

The 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.

> 2. “...the improvement over more traditional approaches.”

Indeed, 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.

Questions:

> 1. Notation. Thank you, we will fix it!

> 2.“Will it ever be more beneficial to use $C_1$ and $C_2$ other than the identity matrix I?”

It 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.

> 3. Why should $c_d$ remain a constant for $d\ge2$?

We 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.

> 4. What is the key difference between JME and CS?

Thank 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.