acceptodds
Under review as a conference paper at ICLR 2027

Better Batches, Better Privacy: Random Allocation for DP-BandMF

Abstract

The current state of the art for batch selection and noise addition in differentially private training is a combination of BandMF (informally, DP-SGD where the noise added in two different steps can be correlated if the steps are within of each other) and privacy amplification by sampling with privacy accounting using Monte Carlo accounting. We identify and improve on some gaps in the past work on the combination of these techniques. First, the prior work for BandMF proposed batch selection strategies that were inspired by Poisson sampling, whereas for DP-SGD random allocation is known to outperform Poisson sampling. We address this by proposing and giving privacy analyses for new batch selection strategies for BandMF inspired instead by random allocation, which empirically outperform previous work. Second, Monte Carlo accounting typically requires drawing samples from a privacy loss distribution, introducing a large up-front cost for accounting. We demonstrate how to increase the throughput of sampling by making the sampling algorithm more amenable to GPU acceleration. Finally, previous work chose the correlation matrix for the noise and the batch selection strategy independently. We give a simple framework for choosing these parameters jointly, and demonstrate utility gains by accounting for privacy amplification in our choice of correlation matrix.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, privacy amplification

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_MxRqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studied the batch selection strategy for the differential privacy banded matrix factorization ( DP-BandMF) method. The paper proposed three new randomized batch selection strategies for DP-BandMF: Cyclic Random Allocation, Nested Random Allocation and Min Sep Random Allocation. Then the work established privacy analysis and computation analysis for the strategies. The authors evaluate their proposed strategies empirically compared with previous work on improved RMSE. Then they also studied DP-BandMF with Monte Carlo Accounting and show efficiency, GPU acceleration, and improved RMSE

Critical strengths
  1. The paper studied a interesting problem.

  2. The paper provided theoretical privacy analysis and computational analysis for its proposed batch selection strategies.

Critical weaknesses
  1. The writing is confusing, and acronyms are introduced without expansion or full-name explanations, such as DP-BandMF in the title and abstract.

  2. The paper contains a privacy analysis but no utility analysis.

  3. The contribution and novelty are limited. The main framework is DP-BANDMF proposed in previous work.

Questions for authors
  1. The privacy-utility tradeoff is important for DP work. Is it possible to provide a utility analysis like Section 3.2 in [1] for the new batch selection strategies for BandMF?

  2. Could you show that your strategies outperform other baselines on other metrics beyond RMSE?

[1].Liang, Hao, et al. "An improved privacy and utility analysis of differentially private sgd with bounded domain and smooth losses." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 40. No. 28. 2026.

5 comments

We thank the reviewer for their feedback; we respond to each point raised below:

W1 (Clarity & acronyms): We put a great deal of thought into the clarity of this paper, so we take this feedback seriously. We already define DP-BandMF in the first sentence of the abstract and explicitly define every batch selection strategy referenced throughout the paper in Section 2.3. Since the other two reviewers rated the paper’s presentation as clear and easy to follow, could the reviewer point us to specific passages or sections that felt confusing? We would be glad to clarify any specific parts during the discussion period and in the final revision.

W2 and Q1 (Utility analysis): First, note that RMSE is the standard utility metric for DP-MF. Even in papers that are more theory-focused (rather than application-focused as we are), RMSE is typically reported in place of an SCO bound (see e.g. Theorem 4 of https://arxiv.org/pdf/2505.12128). Second, getting a closed-form bound for σ that would be necessary to prove a theoretical RMSE or SCO bound requires computing a high-dimensional integral which is challenging; if it were not challenging, there would be no need for Monte Carlo accounting in the first place! In turn, any theoretical guarantees we could prove would be loose and in turn uninformative.

W3 (Novelty & simplicity): The reviewer is correct to point out that the paper builds on known building blocks (DP-BandMF, random allocation, Monte Carlo accounting), and we view the simplicity of our approach as a strength rather than a weakness: the batch selection strategies we propose are easy to implement, drop-in replacements for existing ones, and require no changes to standard DP training loops. At the same time, the empirical improvements are indisputably significant: 1.59x at the anchor (and up to 1.85x) lower RMSE than prior PLD-based state of the art (Cyclic Poisson), up to 1.24x lower RMSE than jointly optimized Balls-in-Bins. Moreover, making this simple idea practical required non-trivial theoretical contributions (Theorems 5, 6, and 8) and empirical / analytical contributions (Section 3.4, Section 4, and Section 5.3).

Q2 (Training metrics): Reviewer WZKG raised a similar point (see our response to Reviewer WZKG, W1); we repeat the relevant summary below for convenience.

We ran new fine-tuning experiments on a 2B Gemma 4 model on the PubMed dataset (N=80,000, T=512, K=8, δ=10-5, ε ∈ [1, 16]) and updated Section 5.3 of the paper with the full setup and results. Summarizing our main findings:

  • Fixed C (b=16): Under a fixed noise correlation strategy, the primary difference between batch selection strategy is the calibrated noise multiplier. Our smaller noise multipliers directly translate to better training losses, as expected. Specifically, Min Sep RA consistently outperforms all competing methods, matching Cyclic Poisson’s loss with 9% to 39% less privacy budget.
  • Optimized (b, C): Using optimized noise correlation strategies for each batch selection strategy, coupled with a noise-aware variant of AdamW, we found that lower expected RMSE consistently translates directly into lower training loss as well. Specifically, all five batch selection strategies we evaluated follow a shared linear trend (R2 = 0.995) when plotting RMSE vs. training loss. We find this result particularly interesting, as it partially addresses the RMSE vs. training performance gap in correlated-noise research, although we believe it warrants a standalone focused follow-up study. Appendix G.4 now contains more analysis into these results if it is of interest to the reviewer.

Thanks for the response. For the utility, I am not asking about the empirical utility. I am asking about theoretical utility analysis like Approximation Error in Theorem 4 of https://arxiv.org/pdf/2505.12128.

For the writing, I mean authors should give the full name of DP-BandMF, like Differentially Private Band Matrix Factorization.

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

The paper is about how to pick batches when training with banded matrix factorization (DP-BandMF). Existing options are Poisson-flavoured (Cyclic Poisson, Min Sep Poisson) or deterministic / Balls-in-Bins. The authors port random allocation (every example participates exactly K times, only the positions are random) into this setting and get three variants: Cyclic RA (random allocation inside the cyclic framework of Choquette-Choo et al. 2023, so the existing reduction to K-of-T/b DP-SGD applies), Nested RA (the residue class is also drawn at random) and Min Sep RA (uniform over all b-separated K-subsets of [T]). For the last two they write down likelihood-ratio recurrences (Eqs. 1 and 2) so Monte Carlo accounting works, at O(T(K + log T)) per sample. On top of that there is a JAX implementation of MC sampling/scoring that does roughly a million samples per second on an H100, and a joint search over the bandwidth b and the one-parameter Toeplitz family from McKenna (2025). Everything is evaluated on prefix-sum RMSE with formal MC calibration (about 10.7M samples per candidate σ at δ = 1e-5). Min Sep RA with the optimized strategy wins in every row of Table 1: median 1.31x (max 1.36x) over the best prior strategy in each setting, 1.54x (max 1.85x) over Cyclic Poisson. Appendix F notes that Min Sep RA has non-uniform expected batch sizes at large b and proposes a wraparound fix.

Critical strengths

The main thing I like is that the paper does one clean thing and does it properly. The three strategies are the obvious ones to try once you think about it, the schedule bijection (Prop. 2) and the two recurrences are simple, and the proofs in Appendix D are short enough that I could actually check them. Calibration is the formal MC procedure of Dong and Ganesh rather than a point estimate, so the Table 1 numbers are certified RMSE, not estimates. The "Std" columns are the right control: same Toeplitz matrix, only the sampling changes, and random allocation still buys about 12% over Cyclic RA and roughly 1.2x over Min Sep Poisson. That isolates the thing the paper is claiming.

Second, the engineering is not cosmetic. Formal calibration at δ = 1e-5 needs ~10^7 samples per σ and a sweep over up to 50 values of σ; being able to do that on a single GPU in minutes rather than on a CPU cluster changes who can use these methods. Appendix G.3 also makes a point I had not seen before: once accounting is MC-based, the optimal Toeplitz coefficients change (they decay faster, Fig. 6), so the strategy matrix and the batch selection have to be optimized together. Tables 4 and 5 contain everything needed to reproduce each cell.

Critical weaknesses
  1. There is no training experiment, only prefix-sum RMSE. The ethics statement even says "purely analytical evaluations". Earlier BandMF papers did run CIFAR-10 / StackOverflow, and this paper itself cites Koloskova et al. 2023 and Gu et al. 2025 for the fact that RMSE is an imperfect proxy for training loss. With gains over the best prior method of 1.2 to 1.36x, I want at least one learning experiment before accepting the "better privacy" framing.

  2. The comparison is tilted in a couple of places. Only the proposed methods get the joint (b, r) optimization of Section 4; Min Sep Poisson and Balls-in-Bins are also MC-accounted but are run with borrowed strategies, so some of the "Opt" gain belongs to the optimizer rather than to random allocation. The 1.85x headline comes from the K = 1 row, where footnote 5 admits Balls-in-Bins is the same algorithm (0.555 vs 0.54); the honest number is the 1.31x median, which the intro does state. I also could not work out whether the Min Sep RA entries in Table 1, Table 5 and Fig. 1b are the standard variant or the "Balanced" one from Appendix F. Figures 1a, 5 and 6 say Balanced, the tables say Min Sep RA. At the optimal b = 128 the standard variant's expected batch size swings by about 2x over the course of training (Fig. 4), which is not a detail for anyone who has to provision memory.

Questions for authors
  1. Which Min Sep RA variant is in Table 1, Table 5 and Fig. 1b? If it is the standard one, please report the balanced variant's RMSE and its MC throughput (the Appendix F recurrence is O(bKT), i.e. b times slower).

  2. Table 4 (Nested RA), rows ε = 8 and ε = 16, are identical to the same rows of Table 5 (Min Sep RA). From Table 1, Nested RA (Opt) at ε = 8 should be about 0.76 x 0.97 = 0.74 RMSE/K, not 0.70. Every other row of Tables 4/5 reconciles with Table 1, so I assume a copy-paste error, but please confirm. ε = 16 also does not appear in Table 1 at all.

  3. Can you run Min Sep Poisson with the Section 4 (b, r) optimization, so we can see how much of the Opt column is the optimizer? Any training experiment at matched (ε, δ), even a small one?

  4. How does Schuchardt and Kalinin (2026), sampling-free accounting for matrix mechanisms under random allocation, relate to Nested RA / Min Sep RA? If it covers them, the Ω(1/δ) sampling cost that motivates Section 3.4 goes away.

2 comments

We thank the reviewer for their constructive feedback, careful review, and for recognizing the clean scope and technical contributions of the paper. We updated the paper and appendix (changes highlighted in blue) and respond below:

W1 (Training experiments): The focus on prefix-sum RMSE was originally by design, as we wanted to do one clearly scoped thing thoroughly, as the reviewer noted. At the same time, the reviewer’s perspective is valid, especially given prior BandMF work showing RMSE is not always perfectly predictive of training performance.

To address this, we ran Gemma 4 2B fine-tuning on PubMed (N=80k, T=512, K=8, δ=1e-5, ε∈[1,16]) and added full details to Section 5.3:

  • Fixed C (b=16): Under a fixed noise correlation strategy, the primary difference between batch selection strategy is the calibrated noise multiplier. Our smaller noise multipliers directly translate to better training losses, as expected. Specifically, Min Sep RA consistently outperforms all competing methods, matching Cyclic Poisson’s loss with 9% to 39% less privacy budget.
  • Optimized (b, C): Using optimized noise correlation strategies for each batch selection strategy, coupled with a noise-aware variant of AdamW, we found that lower expected RMSE consistently translates directly into lower training loss as well. Specifically, all five batch selection strategies we evaluated follow a shared linear trend (R2 = 0.995) when plotting RMSE vs. training loss. We find this result particularly interesting, as it partially addresses the RMSE vs. training performance gap in correlated-noise research, although we believe it warrants a standalone focused follow-up study. Appendix G.4 now contains more analysis into these results if it is of interest to the reviewer.

W2, Q1, and Q3 (Baseline optimization): We initially tried to isolate the contribution of the batch selection strategy via the Std columns, where a fixed noise correlation strategy is applied across multiple samplers. However, as we were working out the details of our experimental setup, we realized that this approach certainly has limitations because different batch selection strategies interact differently with different bandwidths and Toeplitz coefficients. The reviewer makes a good suggestion here, and therefore to put all Monte Carlo methods on an even footing, we re-implemented Balls-in-Bins and Min Sep Poisson in JAX, consistently applied our Section 4 (b, r) optimization and formal calibration to all MC-based methods, and updated Table 1 in the paper (see also our response to Reviewer ucpr). Note that as a result, our reported RMSEs for Min Sep Poisson (Opt) are actually better than those in the original paper. Across all settings, Min Sep RA (Opt) remains the best-performing method, reducing RMSE by up to 11.5% over Min Sep Poisson (Opt) and up to 19.4% over Balls-in-Bins (Opt).

Q1 (Naming Inconsistency): We thank the reviewer for flagging the inconsistent “Balanced” naming in some figures. "Balanced RA" was an earlier working name that we replaced with "Min Sep RA", and we have updated the remaining figure labels to use "Min Sep RA" consistently. Throughout our tables we use the variant without random rotation for efficiency; in additional experiments we ran with random rotation, the RMSE differed by at most 1%, so this choice does not materially affect utility.

Q2 (Duplicate table rows): This was indeed a surprising artifact, and we thank the reviewer for catching it. In the submitted draft, those rows were accidentally populated from a stale copy-paste, and checking this also helped us identify a couple of entries in our ε ablation that had not been pulled from the right 10.75M-sample formal calibration runs. We re-ran all formal calibration scripts from scratch, and updated Tables 1, 4, and 5 accordingly. None of these updates affect any conclusions drawn in the paper.

Q4 (Sampling-free accounting): While we are not sure if the analysis of Schuchardt and Kalinin (2026) can be extended to Nested RA or Min Sep RA, we want to point out a few limitations of their work that do not make it a meaningful baseline to compare our work to. First, they bound the Renyi divergence, and doing accounting of Renyi divergence and then converting to (ϵ, δ)-DP is generally quite loose. Even their own experiments show their methods often overestimate the necessary noise multiplier. Second, the method that can sometimes be competitive with Monte Carlo accounting in their paper has time exponential in b (see Lemma 3.3 of their work; p in their paper is b in ours). In practice, as datasets and training runs grow larger, larger b becomes more preferable and this will exceed the O(1/δ) runtime of Monte Carlo accounting. In short, while their method is of interest when working with Renyi DP instead of approximate DP and when b is small, in practice Monte Carlo accounting is likely to be preferable both in terms of utility and efficiency.

Hi Reviewer WZKG, thanks again for the thoughtful review. With the discussion deadline coming up, we wanted to check whether our new experimental results adequately address your concerns, and if so, whether you would consider bumping your score to reflect that?

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

This paper studies batch selection and privacy accounting for DP-BandMF, an existing framework for differentially private training with noise correlated across iterations. Its main idea is to combine fixed per-example participation counts, as used in random allocation, with the minimum-separation constraints that make banded matrix mechanisms amenable to privacy amplification. The authors introduce Cyclic Random Allocation, Nested Random Allocation, and Minimum-Separation Random Allocation. For the latter two, they derive dynamic programs for evaluating likelihood ratios efficiently, enabling Monte Carlo privacy accounting. The paper also develops a GPU implementation and optimizes a one-parameter family of Toeplitz strategy matrices under the resulting accountant.

Critical strengths
  1. The paper addresses a useful interaction between participation control and correlated-noise privacy accounting. The motivation is coherent: controlling how often each example participates can improve privacy, but doing so within DP-BandMF requires preserving the separation structure needed for tractable accounting. The proposed strategies explicitly address both requirements. The design principles in Section 3.1 provide a clear explanation of why fixed participation counts, separation, and sufficient randomization should be considered together.
Critical weaknesses
  1. Section 5 gives the proposed optimized methods their own joint search over bandwidth and Toeplitz coefficients. In contrast, Balls-in-Bins receives a matrix optimized for deterministic batching, while Min Sep Poisson receives one optimized for Cyclic Poisson. This matters because the paper itself demonstrates that accounting for the interaction between the matrix and the sampler can materially change RMSE. Moreover, amplification-aware matrix optimization was already developed for Balls-in-Bins in prior work [1, Section 4.2]. The current comparison therefore does not directly establish an improvement over the strongest previously available optimized baseline. The reported gains may combine a better sampling distribution with an unequal optimization opportunity. A comparison using comparable matrix families, bandwidth searches, and calibration budgets is necessary to isolate the contribution of the proposed samplers.

  2. In Appendix A, Algorithm 2 uses δbase\delta_{\mathrm{base}} both as the true-divergence cutoff in the false-acceptance requirement of line 1 and as the empirical acceptance threshold in line 6. Without a strict separation between these thresholds, finite sampling does not generally provide the claimed uniformly small false-acceptance probability for mechanisms whose true divergence is arbitrarily close to, but above, δbase\delta_{\mathrm{base}}. The cited framework distinguishes an empirical threshold, an intermediate privacy bound, and the final privacy parameter. These distinctions need to be restored explicitly. There are also concrete inconsistencies in the balanced sampler’s scorer in Appendix F: the recurrence uses eℓloe^{\ell_{\mathrm{lo}}}, although ℓt\ell_t is defined as a likelihood ratio, and its infeasibility condition incorrectly excludes a valid singleton interval.

Reference

[1] Christopher A. Choquette-Choo, Arun Ganesh, Saminul Haque, Thomas Steinke, and Abhradeep Guha Thakurta. Near Exact Privacy Amplification for Matrix Mechanisms. International Conference on Learning Representations (ICLR), 2025.

Questions for authors

Could you please provide more comparison between the related works and your method?

2 comments

We thank the reviewer for their constructive feedback, careful reading of the paper, and for recognizing the motivation, design principles, and contributions of our work. We have updated the paper and appendix accordingly, with all changes highlighted in blue. We respond to each point individually below:

W1 (Joint baseline optimization): This is a good suggestion, and something we initially considered. We originally ruled out running joint (b, r) optimization for the prior methods because: (a) the prior Min Sep Poisson publication did not perform strategy optimization; (b) Balls-in-Bins did not have open-source code available for its matrix optimization (only for accounting); and (c) the existing open source numpy-based implementations in JAX Privacy made full (b, r) sweeps slow and impractical.

Nevertheless, the reviewer’s perspective is valid, so we went ahead and re-implemented both prior samplers in JAX, applied our Section 4 (b, r) optimization and formal calibration to them, and incorporated the apples-to-apples results directly into Table 1 of the updated paper. We also note that our Section 4 optimization achieves improvements for Balls-in-Bins comparable to (and in some settings exceeding) the maximum ~12% reduction reported by that work, without requiring gradient-based local optimization.

All main conclusions remain unchanged. Across all evaluated settings in Table 1, our Min Sep RA (Opt) method remains the best-performing overall. As expected, applying our Section 4 optimization to Balls-in-Bins and Min Sep Poisson narrows the gap, yet switching to Min Sep RA still yields up to an 11.5% RMSE reduction over Min Sep Poisson (Opt) and up to 19.4% over Balls-in-Bins (Opt). Also note that Min Sep Poisson (Opt) is technically a new method.

W2 (Minor paper typos): Thanks for catching the various mistakes in the writing!

  • The deltas in Line 1 of Algorithm 2 are flipped. We will correct this error, which will address the concern about separation.
  • We will also fix the incorrect eℓe^\ell term on Page 18.
  • Finally, the singleton interval claim is an artifact of a broader off-by-one error. The bound should be up−lo<(k−1)bup - lo < (k-1)b.

We want to remark that these are typos in the paper and we have checked that the correct algorithms/recurrences were used in the experiments, so the experimental results are not affected by these mistakes.

Q1 (Related work): We were unsure if you were asking about qualitative comparisons in our related work section or more/better quantitative comparisons in our experiments section, so we did both. We expanded Appendix B in the updated paper with a detailed discussion of the relationships between our method and prior BandMF and random-allocation work. Please see the updated Table 1 and Section 5.3 for additional empirical comparisons between our approach and prior work.

Hi Reviewer ucpr, since the discussion window closes soon, we wanted to check if our responses resolve the "Soundness" concerns you raised, and if so, would you consider raising your score along that axis?

Thank you again for the time you spent to review and provide feedback on our paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Reviewer R

We thank the Area Chair and all reviewers for their time, thoughtful evaluation, and for recognizing the strengths of the submitted paper. We have incorporated all feedback directly into the updated manuscript and appendix (see the revised PDF), with changes highlighted in blue. The feedback provided helped strengthen what we believe was already a strong paper, and we thank the reviewers for the role they played in improving it.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.