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

• Median RMSE improvement was 1.54× (up to 1.85×) over baseline and 1.31× (up to 1.36×) over prior state of the art.The proposed batch selection strategies improved utility across all evaluated settings.Source: §1 · p. 2
• The new DP-BandMF strategies enforce exact per-example participation counts and b-separation, with recurrence relations enabling Monte Carlo accounting.Source: §1 · p. 2
• Monte Carlo accounting exceeded 10^6 privacy-loss samples per second on an H100 GPU, a 50× to 100× speedup over CPU baselines.The implementation uses JAX and exploits batch-strategy structure and Toeplitz matrices.Source: §1 · p. 2
• Jointly optimizing a single-parameter class of strategy matrices under Monte Carlo accounting reduced RMSE by up to 13.4% versus fixed strategies.Source: §1 · p. 2

2.1 Differential Privacy, DP-SGD, and DP-MF

• DP-SGD clips per-example gradients and adds Gaussian noise, while DP-MF generalizes it with correlated noise; DP-BandMF uses a banded strategy matrix.The section assumes Toeplitz matrices for convenience; setting the DP-MF matrix to identity recovers DP-SGD.Source: §2.1 · pp. 2–3

2.2 Privacy Analysis and Monte Carlo Accounting

• Privacy analysis for DP-MF concerns high-dimensional output distributions; Monte Carlo accounting estimates hockey-stick divergence using samples and likelihood-ratio evaluations, but typically needs more than 1/δ samples.The sampling and likelihood-ratio primitives can be challenging when the participation vector has many possible values.Source: §2.2 · p. 3

2.3 Prior Batch Selection Strategies

• Poisson sampling gives random participation counts, whereas random allocation fixes each example’s number of selected batches and was proposed for DP-SGD.Poisson participation counts follow a Binomial distribution; their heavy right tail can degrade privacy.Source: §2.3 · p. 3
• Deterministic, Balls-In-Bins, Cyclic Poisson, and Min Sep Poisson strategies address b-separation or tractable analysis, but existing strategies satisfy at most two of three desirable properties.The three properties are fixed participation counts, b-separation, and maximum benefit from amplification.Source: §2.3 · p. 4

2.4 Related Work

• Related work spans privacy accounting, batch-selection assumptions and alternatives, correlated-noise matrix mechanisms, and methods for per-example gradient clipping.DP-MF noise can reduce prefix-sum error at the cost of increased error on individual gradients.Source: §2.4 · pp. 4–5

3 Batch Selection Strategies for DP-BandMF

• The section assumes b divides T, a b-banded Toeplitz strategy matrix, and a first-column norm of 1.The proposed family of strategies is analyzed under these assumptions.Source: §3 · p. 5

3.1 Design Principles

• The design principles prioritize fixed-K participation, b-separated schedules, randomness, and independent assignments with recursive structure for tractable Monte Carlo accounting.Fixed-K is described as the first-order predictor of the privacy-utility tradeoff; added randomization is second-order.Source: §3.1 · p. 5

3.2 Proposed Strategies

• Cyclic RA assigns examples to residue classes modulo b and selects exactly K eligible rounds uniformly, enabling near-exact privacy analysis via standard privacy loss distributions.It replaces the inner Poisson sampling in the cyclic framework with random allocation.Source: §3.2 · p. 6
• Nested RA randomizes each example’s residue class before selecting K eligible rounds, requiring Monte Carlo accounting because different moduli can affect the same output coordinates.It is otherwise identical to Cyclic RA.Source: §3.2 · p. 6
• Min Sep RA samples uniformly among K-round schedules with b-separated participations, but its expected batch sizes are larger near training’s beginning and end.A correction that fixes this batch-size behavior is described in Appendix B.Source: §3.2 · p. 6

3.3 Privacy Analyses

• Cyclic RA inherits a guarantee from DP-SGD random allocation, while Nested RA and Min Sep RA use likelihood-ratio recurrences for Monte Carlo accounting with O(T(K + log T)) computation.For cyclic RA, K-out-of-T satisfies any privacy guarantee of DP-SGD using K-out-of-T/b random allocation.Source: §3.3 · pp. 7–8

3.4 Implementation Details

• ≈106 privacy loss samples per second and a 50–100× improvement over prior work make Monte Carlo accounting practical for smaller δ.The implementation exploits b-banded Toeplitz structure, fixed-K shapes, vectorized sampling, and a rolling buffer for the recurrence.Source: §3.4 · pp. 8–9

4 Optimizing DP-BandMF with MC Accounting

• The objective is expected total squared error on workload A, combining matrix-mechanism error with the minimum noise multiplier required for (ε, δ)-DP.The strategy matrix is restricted to a single-parameter Toeplitz family, C[i, 1] ∝ r + 1/i, used as a search-space heuristic.Source: §4 · p. 9
• Non-cyclic strategies require jointly optimizing bandwidth b, matrix C, and noise multiplier σ because privacy depends on C’s specific contents.For cyclic strategies, privacy depends only on maximum column norm and bandwidth, allowing C to be optimized separately for each b.Source: §4 · p. 9
• The search evaluates candidate bandwidths and uses a bounded one-dimensional search over r, then formally calibrates σ for the selected candidate.The objective uses a smaller Monte Carlo sample budget for estimation before the final calibration.Source: §4 · p. 9

5 Experiments

• The comparison normalizes expected or exact participation counts to K over T iterations and varies T, K, and ε around T = 1024, K = 4, and ε = 4.The study uses strategy-specific Toeplitz matrices and calibrates Monte Carlo methods with formal verification at δ = 10^-5, drawing 10,745,968 samples per candidate noise multiplier.Source: §5 · pp. 9–10, Table 2 · p. 10

5.1 RMSE Experiments

• 5–14%: Cyclic RA beats Cyclic Poisson among PLD-based methods, with an average improvement of about 11%.Cyclic RA consistently provides the best RMSE among the PLD-based methods, which are cheaper to calibrate.Source: §5.1 · p. 10, Table 3 · p. 11
• 15–85%: optimized Min Sep RA has the best RMSE across evaluated settings, followed by optimized Nested RA, relative to Cyclic Poisson.The improvement grows with larger T and smaller K.Source: §5.1 · p. 10, Table 3 · p. 11
• 12%: Nested RA and Min Sep RA gain this average over Cyclic RA with the same Toeplitz coefficients; optimized coefficients improve RMSE by 8.5% and 13.4%, respectively.The latter comparisons are against the standard Toeplitz coefficients.Source: §5.1 · p. 10
• Nested RA and Min Sep RA benefit from larger bandwidths without the trade-off needed to tune Cyclic Poisson and Cyclic RA.Cyclic Poisson and Cyclic RA reach optimal RMSE at b = 32, while Nested RA and Min Sep RA reach it at b = 128.Source: §5.1 · p. 11

5.2 Sampling Throughput

• 1.3M samples/second for Nested RA and 783K samples/second for Min Sep RA on an H100 GPU make strategy optimization and formal calibration feasible on one machine.The CPU implementation generates about 4K samples per second; the GPU results use the optimized implementation described in Section 3.4.Source: §5.2 · p. 11

6 Discussion and Future Work

• The proposed strategies improve RMSE across evaluated settings, with gains over prior PLD-based approaches as large as 1.85×.The paper frames this as a cohesive framework connecting random allocation and b-separation families.Source: §6 · pp. 11–12
• The discussion presents the optimized implementation as making Monte Carlo accounting orders of magnitude more efficient and more practical.Figure 2 reports RMSE as a function of b and sampling throughput on CPU and GPU, at T = 1024, K = 4, and ε = 4.0.Source: §6 · p. 12, Figure 2 · p. 12
• Formal calibration draws Ω(1/δ) samples per candidate σ; narrowing the initial σ0 could reduce evaluated candidates from roughly 50 to 2 or 3.The authors also describe Toeplitz optimization as coarse: bandwidths are restricted to powers of 2 and coefficients to a single-parameter family.Source: §6 · p. 12

AI Use Statement

• The authors report AI assistance for implementation, code health, figures, tables, and editing, but not for experimental design, the core theoretical framework, or primary proofs.They say AI proposed the random rotation construction to resolve biased batch size and that AI-assisted code and outputs were verified and tested.Source: AI Use Statement · p. 15

A Monte Carlo Background

• For Monte Carlo calibration, each mechanism Mi is a DP-BandMF run with a different noise multiplier, and the mechanisms form a decreasing sequence of multipliers.The passage identifies the dominating pair P, Q using Theorem 1.Source: A Monte Carlo Background · p. 15
• The stated calibration algorithm and final run of the selected inner mechanism satisfy (ε, δ)-DP.The theorem is attributed to Dong and Ganesh [2026].Source: A Monte Carlo Background · p. 15

A.1 Sample Complexity of Monte Carlo Accounting

• At δ = 10^-5, formal calibration requires 10,745,967 samples per candidate σ, rounded to 11,000,000 in the experiments.Figure 3 plots the number of samples needed at different target δ values; its blue line uses δbase = 0.5δ.Source: §A.1 · p. 15, Figure 3 · p. 16
• The calibration procedure samples both directions of each candidate’s dominating pair, tests the estimates against δbase, and returns the preceding mechanism when a candidate fails.If the first candidate fails, calibration returns failure.Source: §A.1 · p. 16
• The blue Figure 3 line uses δbase = 0.5δ, the formal-calibration setting recommended by prior work and used in this paper.The figure compares sample requirements across target δ values.Source: Figure 3 · p. 16

B Biased Batch Sizes for Min Sep RA

• At b=128, the expected-batch-size bias is considerable, while it is negligible for b≤8 when T=1024 and K=4.The paper notes that b=128 is optimal in its setting, making the bias a potential practical concern.Source: B Biased Batch Sizes for Min Sep RA · p. 16, Figure 4 · p. 17
• A wraparound constraint prevents an early participation from also occurring late, and random rotation gives strictly uniform expected batch sizes across iterations.The procedure samples positive gaps summing to T, each at least b, then applies a uniform shift modulo T.Source: B Biased Batch Sizes for Min Sep RA · pp. 16–17
• The gap-and-shift procedure is equivalent to uniform sampling over subsets satisfying b-separation, including the wraparound constraint.The proof establishes equivalence by showing each valid subset has exactly K generating gap-and-shift choices.Source: B Biased Batch Sizes for Min Sep RA · p. 17
• The scoring dynamic program handles the random rotation by decomposing the numerator into b-separated-set sums, with overall P/Q runtime O(bKT).The recurrence evaluation adds an O(b) multiplicative overhead relative to Theorem 6; removing it is left for future work.Source: B Biased Batch Sizes for Min Sep RA · pp. 17–18

C.1 Optimized Toeplitz Parameters

• Tables 4 and 5 provide formal calibration parameters for reproducing the optimized Nested RA and Min Sep RA results.The tables include an anchor configuration at T=1024, K=4, and ε=4.0.Source: §C.1 · p. 18, Table 4 · p. 18, Table 5 · p. 19

C.2 Epsilon-Delta Trade-off Curves

• With coefficients optimized for Cyclic RA, Nested RA and Min Sep RA outperform PLD-based approaches on the (ε, δ) trade-off, and Min Sep RA is slightly better.When coefficients are optimized specifically for Min Sep RA, the gap widens substantially.Source: §C.2 · p. 19, Figure 5 · p. 19

C.3 Monte Carlo optimized Toeplitz Coefficients

• Under Monte Carlo accounting, Nested RA and Min Sep RA have more sharply declining optimal Toeplitz coefficients than cyclic methods.The paper attributes the difference to stronger amplification as coefficients drop faster; cyclic-method amplification is unaffected by coefficients when the column norm is fixed.Source: §C.3 · p. 20, Figure 6 · p. 20
• Faster coefficient decay reduces column dot products and increases privacy amplification; Min Sep RA benefits more because its x has more entropy than Nested RA's.The paper explains that high dot products between columns reduce the uncertainty gained by randomizing participation.Source: §C.3 · p. 20
• The optimal number of bands may differ between these batch selection strategies in some settings.This qualifies the comparison of their optimized coefficients.Source: §C.3 · p. 20