acceptodds
Under review as a conference paper at ICLR 2027

DP-CGD: Efficient Noise Correlation for Differentially Private Model Training

12 views

Abstract

Differentially private stochastic gradient descent (DP-SGD) is the gold standard for training machine learning models with formal differential privacy guarantees. Several recent extensions improve its accuracy by introducing correlated noise across training iterations. Matrix factorization mechanisms are a prominent example, but they can require storing previously added noise vectors, leading to substantial memory overhead. In this work, we propose a new algorithm for correlated-noise private training that correlates noise only with the immediately preceding iteration and cancels a tunable portion of it. By regenerating the previous noise using a pseudorandom number generator rather than storing it, our method has essentially the same memory footprint as DP-SGD. We show that the computational overhead is minimal and empirically demonstrate improved accuracy over DP-SGD.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, private model training, matrix mechanism, correlated noise, memory efficiency

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_KHgGOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces DP-λCGD, a new correlated-noise variant of DP-SGD that aims to improve the privacy-utility tradeoff without the memory and runtime cost of existing correlated-noise methods. DP-λCGD uses a simple one-parameter family of noise correlations, where each step cancels a fraction of the noise added at the previous step. To avoid extra memory, the previous noise is regenerated from a stored random number generator state instead of being kept in memory. The paper provides a theoretical analysis of the error of the proposed method and a practical heuristic for choosing its parameter. Experiments on image and language models show that DP-λCGD has runtime close to DP-SGD and improves accuracy compared to DP-SGD and other correlated-noise baselines in several settings.

Critical strengths
  • The paper studies an important problem. Removing the memory overhead of correlated noise is practically relevant for large models.
  • The idea of regenerating the noise from a stored PRNG state is an interesting and uncommon approach.
  • The paper is generally well written, and the evaluation across different model sizes supports the efficiency claim.
Critical weaknesses
  • The novelty is not very significant. The correlation matrix is acknowledged to already appear in prior work (Choquette-Choo et al. 2024a, Pillutla et al. 2025, Kalinin et al. 2026), so the novelty largely reduces to treating λ as a tunable hyperparameter and using regeneration.
  • In the main comparison (Fig. 4a) on CIFAR-10, BLT and BISR (p=16) appear a lot stronger at several privacy levels. Even though the authors claim that BLT requires either storing a noise buffer or regenerating the full sequence, there is no empirical evidence that characterizes this tradeoff between BLT and DP-λCGD.
  • It appears that DP-λCGD needs to be tuned over λ which is dependent on task, batch size, number of epochs, etc. This is a big disadvantage compared to other baselines.
Questions for authors
  • How does the measured peak memory of DP-λCGD compare to BLT, BISR, and BandInvMF?
  • How should λ be selected when no public validation set is available, and how robust is the "2-4x smaller than amplified RMSE" rule on other tasks?
4 comments

We thank the reviewer for their time and valuable feedback! Below we address the concerns and questions raised.

>> On the novelty

We agree that the correlation Toeplitz matrix of DP-λ\lambdaCGD has appeared in the literature before, but we would like to emphasize that, to the best of our knowledge, we are the first to systematically study how the correlation structure can be tuned for the actual training accuracy in a practical setting. This is different from simply selecting the best λ\lambda based on RMSE. In particular, a major contribution of our paper is the empirical study of the discrepancy between the RMSE optimal, amplified RMSE optimal, and accuracy optimal choices of λ\lambda. The proposed factorization provides a simple, single parameter setting to study these questions, which we believe are important for understanding the practical behavior of correlated noise methods.

Another major contribution is noise regeneration, as the reviewer also acknowledges. This can be seen as complementary to our choice of correlation structure: DP-λ\lambdaCGD is particularly well suited for regeneration, as it requires regenerating only a single noise vector per iteration, while still providing substantial utility improvements over DP-SGD.

>> It appears that DP-λ\lambdaCGD needs to be tuned over λ\lambda which is dependent on task, batch size, number of epochs, etc.

We would like to clarify that task-specific tuning of λ\lambda is not required to use DP-λ\lambdaCGD. Our main point is that the metrics commonly used to construct noise factorizations, such as Root Mean Squared Error (RMSE), do not perfectly predict the training accuracy.

Like other factorizations, our factorization can be selected by optimizing RMSE. In particular, we observed that selecting λ\lambda based on amplified RMSE already gives performance reasonably close to the accuracy optimal one. Importantly, amplified RMSE can be computed without access to any training or validation data.

The advantage of our factorization is that its simple structure allows us to study the relationship between the factorization and actual training accuracy. Other factorizations generally do not provide such a simple mechanism for exploring this dependence. Moreover, there is no reason to expect that their fixed factorizations are universally optimal across different tasks, batch sizes, privacy levels, and numbers of epochs. They are typically selected by optimizing RMSE, given the number of iterations and separation, which does not necessarily reflect downstream training performance.

Therefore, we see the possibility of tuning λ\lambda for downstream accuracy as an additional flexibility of our method, rather than a requirement. In fact, we consider the study of the relationship between RMSE and practical training performance to be one of the major contributions of our paper.

>> How does the measured peak memory of DP-λ\lambdaCGD compare to BLT, BISR, and BandInvMF?

We are happy to provide an empirical comparison. In particular, BISR and BandInvMF have identical memory requirements for a fixed bandwidth (as they differ only in coefficients), so for simplicity, we report only BISR. BLT has approximately the same memory requirements as BISR with a stored noise history of bandwidth 5, while DP-λ\lambdaCGD corresponds to BISR with bandwidth p=2p=2.

We report the peak GPU memory usage when fine-tuning BERT-Base on IMDb with batch size 512 and physical batch size 16, corresponding to the fine-tuning experiments in Figure 6(a). We compare DP-SGD, DP-λ\lambdaCGD, BLT with buffer size 5, and BISR with bandwidth 16. The results are reported in the table below.

MethodRegenerated (GB)Stored on GPU (GB)
DP-SGD9.741–
DP-λ\lambdaCGD9.75210.575
BLT, (b=5b = 5)-11.857
BISR, (p=16p = 16)9.75216.281

With noise regeneration, DP-λ\lambdaCGD has almost identical memory usage to DP-SGD (additional overhead is due to the size of the largest parameter group used for noise generation). Both DP-λ\lambdaCGD and BISR (as well as BandInvMF) can benefit from efficient noise regeneration. In contrast, the noise correlation structure of BLT prevents the same practical regeneration, requiring the noise history to be stored in memory. In our experiment, this results in approximately 2.1 GB of additional memory usage compared with DP-λ\lambdaCGD with noise regeneration.

For larger models, this overhead can become particularly important. First, models that fit on a single GPU with DP-λ\lambdaCGD might not fit with BLT due to the additional memory requirements. Second, the memory saved by DP-λ\lambdaCGD can potentially be allocated to larger physical batch sizes, allowing faster training.

We have included the table in the revised manuscript; see Table 3.

>> “In the main comparison (Fig. 4a) on CIFAR-10, BLT and BISR (p=16) appear a lot stronger at several privacy levels”

We agree that BLT and BISR (p=16p=16) achieve higher accuracy at some privacy levels in Figure 4(a). However, this comes with additional memory or computational costs. Moreover, in the fine-tuning experiments (Figure 6), we do not observe substantial accuracy improvements from BLT or BISR over DP-λ\lambdaCGD. Our goal is to provide a favorable trade-off between accuracy, memory, and computational efficiency, rather than optimizing accuracy alone. DP-λ\lambdaCGD achieves substantial accuracy improvements over DP-SGD, while our runtime experiments show that its computational cost remains close to that of DP-SGD, particularly for larger models.

>> How should λ\lambda be selected when no public validation set is available, and how robust is the "2-4x smaller than amplified RMSE" rule on other tasks?

When no public validation set is available, we propose selecting λ\lambda based on amplified RMSE. This does not need access to any data and can be computed knowing only the number of iterations, number of epochs, batch size, and privacy level. As mentioned above, our experiments show that this choice already gives performance reasonably close to the accuracy-optimal λ\lambda.

The 2-4× rule of thumb is based on our CIFAR-10 and IMDb experiments (Figure 3), where the accuracy optimal choice is smaller than the amplified RMSE suggests for CIFAR-10 training, while the two coincide for fine-tuning on IMDb. During the rebuttal, we did additional experiments comparing fine-tuning of ViT-Base on CIFAR-100 and training WRN-16-4 from scratch on CIFAR-100. The results are consistent with our previous observations: the amplified RMSE-optimal values are almost optimal for fine-tuning, while for training from scratch, the optimal values are 2-4 times smaller (on the scale 1/(1−λ)1/(1-\lambda)). Please find the corresponding plots in Figure 7 of the updated manuscript.

We also realized that the wording of this rule was imprecise. We intended to say that, for training from scratch, the accuracy optimal choice is typically 2-4x smaller than the value suggested by the amplified RMSE (on the scale 1/(1−λ)1/(1-\lambda)), whereas for fine-tuning, we have not observed a significant difference. We have clarified the rule in the revised manuscript.

Dear Reviewer KHgG,

As the rebuttal period will end soon, we kindly ask you to clarify whether any of the concerns remain.

Best regards, Authors

I appreciate the response from the author. While most of my concerns are addressed, I still find the novelty to be limited. I will maintain my current score.

Reviewer_sMgaOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents a new noise correlation scheme for enhancing DP-SGD utility that does not require storing the noise for all the past iterations. The scheme is theoretically analyzed and empirically evaluated.

Critical strengths
  1. The scheme is well motivated. Obtaining a noise correlation scheme that reduces the memory cost has significant practical benefit.
  2. Literature review is good. The paper provides a sufficiently good discussion on related work, which enables the reader to get a decent understanding of the field.
Critical weaknesses
  1. Limited novelty. While the proposed Toeplitz correlation matrix alleviates the need for storing noise for all iterations, the scheme adds little to the original idea of using correlated noise. Moreover, Toeplitz strategy matrix was already studied in Kalinin & Lampert, 2024.
  2. Exponentially more costly. The proposed scheme incurs a factorization error that is exponentially large in nn compared to that of Kalinin et al., 2026. While we save in memory, we end up paying a huge cost in utility. This seems to defeat the purpose of correlation.
  3. Missing empirical comparison with baselines. There is no comparisons with the accuracy of the optimal correlation scheme (Kalinin et al., 2026).
Questions for authors
  1. Could the authors respond to the weaknesses above?
  2. How do we obtain the first inequality in (16)?
5 comments

We thank the reviewer for their time and valuable feedback! Below we address the concerns and questions raised.

>> On the novelty

We agree that the correlation Toeplitz matrix of DP-λ\lambdaCGD has appeared in the literature before, but we would like to emphasize that, to the best of our knowledge, we are the first to systematically study how the correlation structure can be tuned for the actual training accuracy in a practical setting. This is different from simply selecting the best λ\lambda based on RMSE. In particular, a major contribution of our paper is the empirical study of the discrepancy between the RMSE optimal, amplified RMSE optimal, and accuracy optimal choices of λ\lambda. The proposed factorization provides a simple, single parameter setting to study these questions, which we believe are important for understanding the practical behavior of correlated noise methods.

Another major contribution is noise regeneration, as the reviewer also acknowledges. This can be seen as complementary to our choice of correlation structure: DP-λ\lambdaCGD is particularly well suited for regeneration, as it requires regenerating only a single noise vector per iteration, while still providing substantial utility improvements over DP-SGD.

>> “The proposed scheme incurs a factorization error that is exponentially large”

It is true that DP-λ\lambdaCGD has asymptotically larger RMSE than the asymptotically optimal BISR factorization. However, in practice, for a finite number of iterations nn and participations (epochs) kk, the constant factors matter more. For instance, in the table below, we compare the RMSE of both methods and DP-SGD for different values of nn and k=5k=5. In particular, DP-λ\lambdaCGD has an RMSE within a factor of 3.13.1 of BISR, even for a very large number of iterations, while at the same time achieving an RMSE 14.914.9 times smaller than that of DP-SGD.

Methodn = 10n = 100n = 1,000n = 10,000n = 100,000
BISR4.5596.1077.7789.35611.039
DP-λ\lambdaCGD4.5596.35810.69118.87033.574
DP-SGD5.24415.89050.025158.122500.002

That said, throughout the paper we empirically show that RMSE is not a perfect predictor of training accuracy, even though it is the main metric used by previous matrix factorization methods. In particular, a larger RMSE does not necessarily imply worse training performance. Our experiments show that DP-λ\lambdaCGD achieves comparable utility to BandInvMF, BISR, and BLT in several settings, despite their lower RMSE and additional computational or memory costs; see Figures 4 and 6.

>> “There is no comparisons with the accuracy of the optimal correlation scheme”

We would like to clarify that we do compare with the Banded Inverse Square Root (BISR) factorization of Kalinin et al. (2026) [1], as well as their BandInvMF factorization. See Figures 4 and 6, where we report results for bandwidths p=2p=2 and p=16p=16. In particular, for λ=1/2\lambda=1/2, our proposed method is equivalent to BISR with bandwidth p=2p=2.

We would also like to emphasize that the optimality result of Kalinin et al. (2026) concerns the asymptotic RMSE, which does not necessarily translate into optimal downstream training accuracy, as we demonstrate in our experiments. Our comparisons focus on practically efficient bandwidths, since larger bandwidths require regenerating more noise vectors per iteration.

[1] Kalinin et al. “Back to Square Roots: An Optimal Bound on the Matrix Factorization Error for Multi-Epoch Differentially Private SGD.” ICLR 2026.

>> “How do we obtain the first inequality in (16)”?

We are happy to clarify this step and have added further explanations in the revised manuscript.

Expanding the squared norm, we get:

= \sum_{j=0}^{k-1}\left\lVert (C_\lambda)_{:,jb+1} \right\rVert_2^{2} + 2\sum_{0\le i<j\le k-1}\left\langle (C_\lambda)_{:,ib+1},(C_\lambda)_{:,jb+1} \right\rangle \ge \sum_{j=0}^{k-1}\left\lVert (C_\lambda)_{:,jb+1} \right\rVert_2^2.$$ The inequality holds because all entries of $C_\lambda$ are nonnegative for $0\le\lambda<1$, and therefore all pairwise inner products between its columns are also nonnegative.
Reviewer_sMgaOpenReview ↗

Follow-up to the rebuttal

Dear authors, thank you for responding to my concerns. My concern regarding the comparison to BLT accuracy has been addressed, and the concern regarding exponential cost has been partially addressed. However, my concern on novelty still remains and something on the tuning of λ\lambda is unclear.

On tuning of λ\lambda. It seems like λ\lambda is simply tuned by sweeping across all the possible values, while keeping track of the accuracies on validation dataset. First, this does not seem like a contribution (since that's a fairly standard way of hyperparameter tuning). Second, this tuning exposes the validation data to additional privacy threat (unless CC is assumed private in the threat model), which has not been discussed. This second point is related to a similar concern by another reviewer. The response to which (i.e., use RMSE) seems to conflict with authors' claim that RMSE is not a good metric for performance.

Dear Reviewer,

Thank you for your quick reply. We appreciate your follow-up questions and are happy to clarify.

On the tuning of λ\lambda. It is true that once we have the parameter λ\lambda to tune, the tuning procedure itself is standard: we sweep over a reasonably small set of values (10 values in our experiments). Our experiments also provide practical suggestions on which values of λ\lambda are reasonable to try. For instance, we observed that for fine-tuning tasks, one may not need to tune λ\lambda at all, but can simply select it based on the amplified RMSE. For training models from scratch, the optimal value is also in a predictable range relative to the one suggested by amplified RMSE, namely 2-4 times smaller on the 1/(1−λ)1/(1-\lambda) scale.

Our main contribution is that we propose a family of factorizations with a tunable parameter. Previous works on correlated noise DP training, such as BLT, BISR, BSR, BandMF, and BandInvMF, use fixed factorizations designed primarily to minimize RMSE. We propose a factorization that is flexible enough to adapt to a specific learning task, while giving most of the benefits of noise correlation and being as memory and time efficient as DP-SGD.

The novelty is the introduction of the tunable factorization, and our main contribution is a reasonably extensive study of the discrepancies between the task optimal, RMSE optimal, and amplified RMSE optimal values.

Regarding the privacy concern, we agree that if the validation data are private, then one must perform DP hyperparameter tuning, otherwise there is a privacy leakage. For consistency with prior work, and under the assumption that a similar public dataset would be available for validation in practical deployment, we assume the validation to be public. We agree that this assumption should be made clearer in the paper.

We find the idea of assuming CC to be private interesting, but we are not aware of a way to benefit from this assumption in the privacy accounting. So, we assume the matrix CC to be public.

Regarding RMSE as a metric, the relationship between RMSE and accuracy is nuanced. We do not claim that RMSE is unimportant; it gives a useful, approximate measure of performance. In particular, when the loss landscape is relatively "nice", e.g. when fine-tuning a large pretrained model, and the noise multiplier is small, RMSE can predict performance accurately, as we observed in our experiments. However, when the loss landscape is more complicated, as in training from scratch, and the noise level is higher, and especially when the amplification by subsampling is used, RMSE becomes a less reliable predictor of training performance.

In short, compared to DP-SGD without noise cancellation, having a low RMSE helps. However, once RMSE is already low, other factors can play an important role in determining training performance. The limitation of previous works is that their fixed factorizations do not allow us to easily study these effects or adapt the factorization accordingly. Our DP-λ\lambdaCGD provides this flexibility.

We hope these clarifications address your concerns, and we are happy to discuss further if anything remains unclear.

Reviewer_DA6VOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes DP-λ\lambdaCGD, a memory-efficient correlated-noise mechanism for differentially private model training. It uses a bandwidth-2 lower-triangular Toeplitz factorization, where the current noise cancels a tunable fraction of the previous noise. By saving and restoring the state of a counter-based GPU PRNG, the method regenerates the previous noise vector instead of storing a history of noise vectors. The paper analyzes RMSE/MaxSE properties and evaluates utility, runtime, and memory against DP-SGD and matrix-factorization baselines across image and language tasks.

Critical strengths
  1. Practical memory–compute trade-off. Regenerating only the previous noise vector is a simple way to reduce noise-buffer memory. The reported runtime overhead on larger models is small, which gives the method practical relevance.
  2. Useful one-parameter analytical framewrok. The λ\lambda-controlled framewrok enables systematic analysis of the mismatch between matrix-level proxy metrics and downstream model utility.
Critical weaknesses
  1. The baseline comparison is not fully tuning-matched. The proposed method searches multiple λ\lambda values on validation data, while some closely related factorization baselines use fixed theoretical settings. The reported advantage may therefore partly reflect tuning flexibility rather than the proposed mechanism itself.
  2. The implementation and reported tables needs further verification. The PRNG state rollback may use a dedicated generator independent of model stochastic operations. The anomalous BISR(p=16) RMSE entry in Table 2 could be checked against the original logs. The appendix column-normalization result is theoretically interesting but is not evaluated for downstream utility.
Questions for authors

(1) a comparison using a no-validation-tuning heuristic for λ\lambda, and/or allow the closest bandwidth-2 baselines a comparable tuning budget (2) noise regeneration use a dedicated PRNG instance, isolated from Dropout, data augmentation, and other stochastic model operations.

1 comment

We thank the reviewer for their time and high evaluation of our work! Below we address the remaining concerns.

>> “A comparison using a no-validation-tuning heuristic for λ\lambda, and/or allow the closest bandwidth-2 baselines a comparable tuning budget”

We are happy to provide an additional comparison where λ\lambda is selected by minimizing amplified RMSE, rather than being tuned on a validation set. Importantly, amplified RMSE can be computed without access to any data.

Methodε=1\varepsilon = 1ε=2\varepsilon = 2ε=4\varepsilon = 4ε=8\varepsilon = 8
DP-λ\lambdaCGD tuned48.32 ± 1.1249.08 ± 2.2052.52 ± 1.0357.69 ± 0.85
DP-λ\lambdaCGD not tuned45.76 ± 0.2046.13 ± 0.1746.89 ± 1.4753.54 ± 2.40
DP-SGD43.96 ± 1.1148.42 ± 0.3649.32 ± 1.3749.55 ± 1.36

In particular, we see that even without tuning, DP-λ\lambdaCGD outperforms DP-SGD in the high privacy regime (ε=1\varepsilon = 1) and the low privacy regime (ε=8\varepsilon = 8). In the intermediate regime, it performs slightly worse; we attribute this to the differences between the amplification schemes, Poisson for DP-SGD and Balls-in-Bins for the matrix mechanism, which benefit different privacy levels.

We would also like to emphasize that the flexibility to tune the correlation structure for actual training accuracy is one of our main contributions. Other factorizations generally do not offer such a simple mechanism to study the dependence of training accuracy on the correlation structure. We therefore see the possibility of tuning λ\lambda as a source of additional flexibility in our method, rather than a requirement.

>> The anomalous BISR(p=16) RMSE entry in Table 2 could be checked against the original logs

Thank you for pointing this out. Unfortunately, some of the values in the table were entered manually, and we made a typo: the correct value was supposed to be 30.2530.25, not 20.2520.25. We took this opportunity to rerun the entire table and also improve the way the values are computed.

Monte Carlo sampling introduces some variability in the estimated noise multiplier and, consequently, in the amplified RMSE. We now explicitly state that we use 10610^6 samples per run and add error bars based on three independent runs. Moreover, we now explicitly state that DP-SGD uses deterministic privacy accounting with Poisson subsampling. The new table (Table 1 in the new version) can be found in the updated manuscript.

>> The appendix column-normalization result is theoretically interesting but is not evaluated for downstream utility

We thank the reviewer for finding our result on column normalization interesting. While column normalization improves the RMSE theoretically, our numerical evaluation suggests that the improvement is very small in the training regimes we primarily consider. We therefore left this result in the appendix as an additional theoretical study of a simple extension of our method.

>>”noise regeneration use a dedicated PRNG instance, isolated from Dropout, data augmentation, and other stochastic model operations.”

Yes, our implementation already uses a dedicated PRNG for generating the DP noise, independent of other stochastic operations such as dropout, data augmentation, and batch sampling. Therefore, restoring its state to regenerate previous noise does not interfere with these operations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.