- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3(+1)
Read review
Paper summary
The paper considers the problem of using the matrix mechanism for answering prefix sum queries with differential privacy, with applications to DP ML. We are given an input stream (e.g. of gradients) G and add correlated noise C^{-1} Z, where Z is Gaussian noise and C is a "correlation matrix". The goal is to minimize the error of the prefix sums of the stream E C^{-1} Z, where E is the lower-triangular all-ones matrix while preserving differential privacy (which requires bounding some norm of C).
Typically memory is limited, so storing C^{-1} Z all at once is inefficient and we would like to be able to generate each row of C^{-1} Z in a streaming manner using limited memory. The authors are further interested in a setting where we can generate each row from scratch efficiently, rather than generating each row from the previous row. This is helpful since the 'noise state' can be saved as a few PRNG seeds rather than as full (high-dimensional) noise vectors, and also allows us to regenerate the noise efficiently if we need to restart in the middle of training due e.g. to device availability (past approaches might require running all previous iterations of noise generation to retrieve the noise state from the PRNG seeds). For this reason the authors focus on banded inverse matrices, i.e. C such that C^{-1} only has non-zero diagonals, which natively have these properties for noise generation.
They propose a family of banded-inverse matrices called -Banded Inverse Fractional Root (BIFR), parameterized by , where the entries of decay as . BIFR recovers the previous work of BISR at making it optimal for larger bandwidths , and matches the asymptotic error scaling of the prior work -CGD, which was designed for p = 2, but extends it to larger .
The authors conduct empirical studies demonstrating (i) the error (RMSE) of BIFR is much closer to that of the numerically optimized solution than other approaches (ii) how the choice of parameter effects the RMSE as well as model accuracy at different bandwidths (iii) how much the resulting mechanisms benefit from privacy amplification (iv) experimental comparisons on model training between different matrix factorizations in memory-limited settings. Namely, compared to other methods BIFR does well at high-epsilon regimes closest to practice.
Critical strengths
- The asymptotic error bound demonstrates that -BIFR unifies and subsumes results from past work. Providing unifying frameworks like -BIFR gives a cleaner overall understanding of the problem space, rather than having many seemingly disjoint results with separate intuition. Furthermore, I would characterize this primarily as a theory paper, so having a theoretical result subsuming and expanding beyond past work constitutes a meaningful contribution.
- The empirical studies are thorough, looking at a wide variety of factors. For example, comparisons on RMSE and model training between different methods, robustness of error/accuracy to the parameter, comparing the amplification in different settings, and more. These thorough studies both give better qualitative understanding of different methods, and also make it more useful for practitioners by identifying regimes where the gain is largest, and also the importance of certain parameters.
Critical weaknesses
- The practical significance of the method is somewhat limited. BIFR is not always the best performing method in the experiments. The main qualitative practical advantage of banded-inverse methods is the setting when the noise state is required to be low memory (a few PRNG keys) and also fast to regenerate. However, other methods which the authors mention as being less practical in these regimes due to regenerating more slowly are still used in practice (as a recent production example, see the use of BLTs in https://arxiv.org/abs/2609.31494) despite not satisfying these criteria, so it's not clear how common these restrictions are.
- In the empirical results, DP-SGD seems to be a highly competitive method even at larger , which seems to contradict past work (e.g. https://arxiv.org/abs/2306.08153) which observes DP-SGD is outperformed even by e.g. BandMF at almost all epsilons. It would be good to explain this discrepancy with past work, otherwise it's a bit hard to trust these empirical results. Even in the low-memory regime where DP-SGD would be more competitive, I would expect 2 bands to offer most methods enough flexibility to beat DP-SGD at high epsilons.
Questions for authors
- See above question on why DP-SGD performs so well in the experiments
4 comments
>> DP-SGD seems to be a highly competitive method
We note that DP-SGD was already competitive in the high-privacy regime () in the cited BandMF paper (McKenna, 2025), see Figure 1. Even at larger privacy budgets, the improvements in CIFAR-10 accuracy are relatively modest, on the order of a few percentages. Moreover, the larger improvements in their Figure 6 are shown in the federated learning setting without amplification, which is more favorable to matrix factorization and less comparable to our centralized experiments.
There are also several important differences between the experimental settings that may explain the observed discrepancy.
- BandMF optimizes the bandwidth for each privacy budget, whereas we consider fixed, predefined bandwidths to study the utility-memory tradeoff. These bandwidths are not necessarily optimal for every method and privacy budget.
- The privacy amplification schemes differ. DP-SGD benefits from tight accounting under Poisson subsampling, whereas the available Poisson accounting for general matrix mechanisms remains very loose. We use the Balls-in-Bins amplification, which provides tighter accounting for banded-inverse mechanisms but offers weaker amplification than Poisson subsampling. This difference limits the achievable improvements over DP-SGD, particularly in the high-privacy regime.
- The optimization procedures differ. In Appendix H.1, BandMF reports using momentum for matrix-factorization methods and no momentum for DP-SGD. In contrast, we do not use momentum in our CIFAR experiments to isolate the effect of noise correlation from the gradient correlation introduced by momentum.
We agree with the reviewer's intuition that even bandwidth can outperform DP-SGD at larger privacy budgets, as also shown in Figure 4 of the DP-CGD paper (Kalinin et al, 2026a), where was selected based on the validation accuracy. Our results similarly show higher accuracy than DP-SGD at (see Tables 2-5).
We believe these differences in bandwidth selection, privacy amplification, and momentum help explain the discrepancy with the results reported in BandMF.
Thanks to the authors for their response. The authors provide several compelling reasons why their empirical setting is different and the comparison between DP-SGD and BandMF may not align with prior work. I also appreciate the inclusion of the new empirical comparisons in terms of memory usage. These results are very useful for comparing the different methods across multiple dimensions besides just utility. I have raised my Soundness score accordingly.
However, some of my concerns still remain.
- First, the comparisons the authors make in terms of memory show BIFR with 4 bands is better in terms of efficiency than BLTs with 4 buffers. Again, I believe this is a useful result to show, to allow comparing the methods on multiple axes. However, this is in the setting of Figure 4a, where for smaller epsilons BLT has higher accuracy (sometimes by a non-trivial margin), and even for larger epsilons seems to be within the margin of error. In turn, it's plausible that despite BIFR achieving better efficiency in Tables 8-10, if we fix a time and memory constraint per iteration, BLTs still achieve the best utility, even if we convert the wins in efficiency for BIFR to wins in utility by e.g. using a larger batch size or more iterations of training (of course, the opposite is also plausible).
- Second, if DP-SGD is competitive we can also take the argument above in the opposite direction: In settings where DP-SGD is competitive, we should just use DP-SGD and then there's no need to track noise state at all, and perhaps this enables larger batch sizes or more iterations of training. If DP-SGD achieves the best utility, then the problem of picking the best of different MF variants is moot.
In short, while I think the authors' new results are valuable for comparing the different methods, and even if BIFR does not uniformly improve on BLTs it's a meaningful contribution that BIFR allows one to trade off on multiple axes with other DP-MF methods like BLTs, I don't feel the concern is fully gone and don't feel comfortable raising my overall review score accordingly.
Dear Reviewer,
We appreciate your feedback and kindly ask you to consider the following arguments, which we hope will address your remaining concerns.
Efficiency. We also compare -BIFR with 64 noise vectors in large scale VaultGemma fine-tuning (see Table 8 of the revised manuscript). With 64 bands, -BIFR achieves substantially greater noise cancellation and outperforms BLT. Our comparison was done using the same physical batch size, under which -BIFR was only 10% slower than BLT due to noise regeneration. However, the substantial memory savings offered by -BIFR allow for larger physical batch sizes, which could further improve runtime.
Utility. We agree that BLT and DP-SGD can outperform -BIFR, particularly in the high-privacy regime (). However, we believe that the boundary at which this occurs could be shifted through improved privacy accounting (in the comparison with DP-SGD) and a better tuning metric than amplified RMSE for selecting the bandwidth and (in the comparison with BLT). In other words, the exact boundary at which one method begins to outperform another is not necessarily fundamental and could potentially be improved through further research.
We also agree that DP-SGD should be preferred in high-privacy regimes where it outperforms -BIFR. However, we argue that these regimes may be less relevant to practical production deployments. For example, in the aforementioned work on practical deployment [Daly et al., 2026], the authors use a privacy budget of under concentrated DP. Converting this to -DP with yields . This corresponds to a low privacy regime, in which our -BIFR outperforms both BLT and DP-SGD by a meaningful margin; see Figures 4b and 5b.
We thank the reviewer for their thoughtful feedback and positive assessment of our theoretical and empirical contributions! We address the remaining concerns below.
>> On the practical significance
As correctly pointed out by the reviewer, our method belongs to the class of banded-inverse methods, which offer several advantages over the Buffered Linear Toeplitz (BLT) method.
Regarding the practical significance, we acknowledge the successful BLT deployment cited by the reviewer. However, we wish to emphasize that their reported models have only up to 10M parameters, making the storage of a few additional noise vectors relatively easy. In contrast, DP-SGD has already been used to train substantially larger models, such as the 1B parameter VaultGemma [1]. At this scale, storing multiple additional noise vectors becomes considerably more expensive, making efficient noise regeneration particularly appealing.
To show this advantage, we have done additional memory and runtime experiments, reported in Tables 8, 9 and 10 of Appendix A.2 of the revised manuscript (see also our response to reviewer yG27). In particular, when fine-tuning VaultGemma, γ-BIFR with p=64 and noise regeneration requires only 28.4 GB of GPU memory, compared with 44.2 GB for BLT, while causing only 10% additional runtime. The savings in memory can easily be translated into time savings by allowing larger physical batches to be used. In particular, we show a 29% reduction in time compared to BLT when using noise regeneration with a larger physical batch size that would otherwise not fit on a single GPU with BLT.
We also note that optimizing BLT with larger numbers of buffers can be challenging. In particular, the JAX_privacy implementation explicitly states that "the default of 3 is a good choice in general; large number of buffers can cause numerical instability in the optimization." [2]. The cited BLT deployment also uses only three buffers, leaving substantial utility gains on the table, particularly in the low-privacy regime, as shown in Figures 4 and 5 of our paper.
We therefore believe that banded-inverse methods offer a promising direction for scaling correlated noise private training to substantially larger models, while retaining theoretical guarantees and implementation simplicity.
[1] Sinha et al. “VaultGemma: A Differentially Private Gemma Model” 2025 arXiv:2510.15001
[2] https://github.com/google-parfait/jax_privacy/blob/main/jax_privacy/matrix_factorization/buffered_toeplitz.py#L958